Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper proves a better complexity lower bound for stochastic PIFO optimizers on the problem of finite-sum minimization. The paper assumes that the objective function is the sum of n individual loss functions. It further assumes that (1) the optimizer initializes at a fixed point, and (2) at each iteration, it randomly and independently selects one loss function to update the parameter vector. 

To prove the desired lower bound, the paper constructed a group of special loss functions, such that each individual loss depends on only 2 coordinates of the parameter vector (except for the regularization term). By this construction, if the parameter vector is initialized at 0, then the number of non-zero coordinates of it will grow slowly enough so that the parameter vector will stay in some low-dimensional subspace unless a large number of iterations is performed. Using this construction, the authors prove the lower bound for 4 different configurations of optimization problems.

Overall, I think the results are very interesting. Similar ideas (the diagonal matrix used in this paper) have been widely adopted in proving complexity lower bound. The novelty of this paper appears to be that the diagonal matrix is partitioned into n groups to define the individual loss functions. Despite the tight lower bound, the assumption (1) and (2) above seems to be restrictive, but they are necessary for the analysis of this paper. If we allow the optimizer to initialize at a random point, or if the optimizer can adaptively choose the loss function at each iteration based on the parameter trajectory, then the analysis framework no longer applies. This is probably the main limitation of this work.

review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: ** Summary
The paper derives a novel lower bound on the complexity of optimizing finite-sum convex functions (under different assumptions) using algorithms that have access to point-wise evaluation of the function, its gradient, and proximal information. 

** Overall evaluation
Finite-sum convex functions are very common in machine learning problems and how the optimization complexity scales with their properties (e.g., condition number) and the number of components (e.g., number of samples in typical ML problems) is a very important question. This paper addresses the question from a lower bound point of view, showing that there is no proximal incremental first-order algorithm that can optimize such functions at an accuracy level of epsilon in less than a term which depends linearly with number of components n and sqrt(k) (k being the condition number). The paper fills an existing gap in the literature and it achieves two very interesting results:
1- The lower bound now matches an existing upper bound for Point-SAGA, showing that no better algorithm can exist (at least in a worst-case sense). 
2- This result also illustrate that proximal algorithms are not necessarily more powerful than first-order methods that only access the gradient of the function. This is also very interesting, as it was still an open question whether proximal information could possibly give an advantage.

The paper is also well written, although some elements could be improved:
1- Def 2.4: the authors consider algorithms where the sampling distribution cannot adapt through iterations. Although this is standard, I am wondering whether adaptivity may buy anything in the performance or whether the lower bound applies to adaptive algorithms as well.
2- Although similar constructions to create worst-case functions were used before in deriving complexity lower bounds, it would be useful to have an intuition about the specific choice made in eg Eq.5/6 and how this enables the refined analysis presented in the paper.
3- More in general, I encourage the authors to illustrate how their techniques compare and differ from previous lower bound proofs.
4- In all theorems, the analysis is done by linking the dimension d to all other parameters of the problem. As pointed out by the authors, the requirements on the dimensionality in the theorems of this paper are milder than previous results. It would be helpful to illustrate how the lower bound would behave when the dimensionality changes and provide an intuition about the specific choice in the theorems
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: The authors prove lower bounds on the number of queries required for optimizing sums of convex functions.  They consider more powerful queries than the usual queries that provide function evaluation/gradient pairs for chosen summands.  As was done in [1] (which is cited in the submission), in this work algorithms can also get the answer to a
"prox query" solving a regularized optimization problem for the chosen summand at the chosen point.  For different classes of functions obtained through smoothness and (strong) convexity constraints, the lower bounds are on
the number of queries needed by an algorithm to guarantee to approximate the minimum.

The main result is for the case that the summands are mu-strongly convex and L-smooth.  Bounds for this case are often
given in terms of kappa = L/mu.  An upper bound of O( (n + sqrt(kappa n) ) log(1/eps)) is known, and
[1] had proved a lower bound of Omega( n + sqrt(kappa n)  log(1/eps)), which matches the second term of the upper bound, but leaves a log-factor gap for the first.  This paper proves an Omega( (n + sqrt(kappa n) ) log(1/eps))  lower bound, but for a restricted class of algorithms that fix a probability distribution over the summands ahead of time, and randomize by repeatedly sampling independently at random from this fixed distribution.  The iterates of the algorithm are also constrained to be in the span of the answers to previous queries.  Thus, this new result is incomparable in strength with the result in [1].  Also, the authors of this paper mention early in the paper that kappa is often large relative to n.
But even if kappa is on the same order as n, the second term of the upper bound dominates the first, and is matched by the lower bound in [1].

The authors point to some new techniques in their analysis.  I can see some new elements, but my knowledge of the previous work in this area is not deep enough to evaluate technical novelty very well.

I have some question about the extent to which this work is in scope for ICLR.  An argument could go that since stochastic gradient methods are so important to deep learning, study of the foundations and limitations of those methods is in scope.
But a lower bound for the convex case seems to be stretching this a little far.  

This seems like a somewhat incremental contribution that would be of interest to a smallish subset of ICLR attendees.

[1] Blake Woodworth and Nathan Srebro. Tight complexity bounds for
optimizing composite objectives. In NIPS, 2016.
review_title: Official Blind Review #1

Meta-review: The paper considers a lower bound complexity for the convex problems. The reviewers worry about whether the scope of this paper fit in ICLR, the initialization issues, and the novelty and some other problems.
Decision: Reject