Tight Complexity Bounds for Optimizing Composite Objectives
We provide tight upper and lower bounds on the complexity of minimizing the average of m convex functions using gradient and prox oracles of the component functions. We show a significant gap between the complexity of deterministic vs randomized optimization. For smooth functions, we show that accelerated gradient descent (AGD) and an accelerated variant of SVRG are optimal in the deterministic and randomized settings respectively, and that a gradient oracle is sufficient for the optimal rate. For non-smooth functions, having access to prox oracles reduces the complexity and we present optimal methods based on smoothing that improve over methods using just gradient accesses.
The authors provide some complexity bounds on problems that are interested in optimizing composite functions of the form F = \frac{1}{m} \sum_{i=1}^{n} f_i when one knows 0th and 1st order terms: f_i(x),\nabla f_i(x) and \Prox_{f_i}(x,.).  Then, the paper produces a very long tiresome results on what can be said on the complexity of optimization procedures in several different frameworks (smooth, non smooth, deterministic, stochastic, upper bounds, lower bounds).  The paper then proposes a very (very) long supplementary material that gathers bibliographic comments and proofs of the proposed results.
I am not able, from a theoretical point of view, to produce a reliable judgement of the paper. However, I can comment several drawbacks:  1) If I understand the global motivation of saying something in each situation for a journal paper, for a brief contribution in a conference proceedings, such a work is very painful for the referee. If you imagine I have to read 7 papers like this one in one month, you can easily conclude that it is not possible for me to produce a constructive reading of this work: 28 pages of a very very NOT self-contained paper, with an excessive abuse of acronysms and without any motivation in the beginning of the introduction. It results in a very boring enumeration of a potpourri of results.  2) The paper is not motivated at any moment. It lacks of real focus on a particular motivated example. Please, reduce the size of the supplementary material and just prove one or two result with a clear example, a clear simulation, a clear state of the art and a clear discussion. The paper does not contain at least one of this point above.  3) The way the paper is written is far from being standard for a mathematician: for example, the lines from 101 to 106 are not written rigorously  (even though I believe the results being true).  Minor comments:  Line 115: strange sentence. Line 123: "Using the Lemma allows us to" -> change the sentence Line 123-135: I am not fan of this paragraph, with an enumeration of non horizon free methods:  most of  penalty terms involve highly dependent terms with respect to generally unkwnown parameters. Line 158: othonormal Line 161: the following truncations of EQUATION (6) Supp material: reduce the 20 pages to 3/4 pages!!!