Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 
The paper provides a lower bound on the iteration complexity of any full batch algorithm in stochastic convex optimization. In particular, they show that for every T, there exists a function (which depends on T) for which the suboptimality in terms of excess risk for any full batch algorithm run for T steps is lower bounded by 1/T^{1/4}. The proof technique extends upon the lower bound construction of Amir et. al. 2021 [1] for the iteration complexity of GD algorithm, and is based on a span based argument. 

main_review: I support accepting the paper. The main reasons for a low score are: 

(1. ) SGD vs ERM: We already know from earlier works that Empirical risk minimizing (ERM) solutions may fail to have low suboptimality at the population level (for eg. in [14], [25]).  Full batch descent algorithms find the ERM solution. I do not see a lot of motivation in proving lower bounds for algorithms which go towards solutions which we know may not generalize. 

(2.) Iteration complexity vs work: We know that SGD is statistically optimal for stochastic convex optimization. Furthermore, it is also optimal work wise. It is easy to see that running event 1 iteration of GD is as expensive as running SGD to convergence. Why should we care about lower bounds for full batch algorithms for which we already know that even 1 iteration is worse than the optimal and easy to implement algorithm. 

(3.) GD with projection vs without projection: In the paper, the authors run GD with projection and compare the suboptimality of the returned solution with the minimizer in the unit norm ball. In practice, we generally run SGD / GD without projection? Is there any hope to extend the lower bounds for full batch methods run without the projection step. 

(4.) Statement of the results: 

(a) The authors should add in the main body that the function depends on T (as the parameters and the problem dimension are chosen depending on the value of T).  

(b) I am confused by the way the result is presented in Theorem 3.1. If we look at the proof at the end of page 9, we see that there is an extra \beta-dependent term multiplying (1/4 - \eps^2 T) which is data dependent. This term can be arbitrarily small and has been hidden in the proof of Theorem 3.1. One can simply get rid of this term by setting \eps = 1/T^{1/4} which the authors should do. This would just give a lower bound of 1/T^{1/4} in Theorem 3.1. 

The paper is well written otherwise. It might be useful to explicitly state the upper / lower bounds on \gamma_1 and \gamma_2 in various lemmas in the main body.  

limitations_and_societal_impact: NA
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work studies the generalization performance of algorithms in stochastic convex optimization. Specifically, the authors study the full-batch algorithms where only full gradient and function value information are accessible. By constructing a hard instance of the objective function, the authors show that any full-batch algorithm needs at least $\Omega(1/\epsilon^4)$ iterations to obtain an $\epsilon$-risk function, while stochastic algorithms such as SGD only need $O(1/\epsilon^2)$. 
main_review: This paper shows that there exists a separation between full-batch algorithms and stochastic algorithms in the generalization performance of empirical minimization. Such a separation has been well studied in the pure optimization setting, and this work is the first to study such a problem in the generalization setting. The presentation is clear and easy to understand. The proof is technically sound. Some of my comments are as follows. 

- It is a bit hard to tell the significance of the proposed result. On the one hand, the lower bound result reveals that full-batch algorithms will be sample-inefficient compared with SGD, which is not studied in previous works. On the other hand, such a phenomenon is not surprising, since similar separation results have already been studied in previous works studying optimization errors. The tool the authors used is standard (hard instance by  Nemirovski et. al), and it is not clear how the authors contribute given existing works.

- For the use of random rotation matrices, there are some additional works studying optimization lower bounds which also use them. The authors may want to highlight these works in the main text. 

[1] Fang, C., Li, C. J., Lin, Z., & Zhang, T. (2018). Spider: Near-optimal non-convex optimization via stochastic path integrated differential estimator. arXiv preprint arXiv:1807.01695.

[2] Zhou, D., & Gu, Q. (2019, May). Lower bounds for smooth nonconvex finite-sum optimization. In International Conference on Machine Learning (pp. 7574-7583). PMLR.

[3] Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., & Woodworth, B. (2019). Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv:1912.02365.
limitations_and_societal_impact: The authors discuss the limitations and there is no negative societal impact about their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers a problem where one is trying to find an input that minimizes the expected value of a function that one has sample values of. Its goal is to show that algorithms that only have the ability to query the gradient of the average of the samples at specified points may need more queries than a function that can check the gradient on individual samples. In order to do that, the paper finds a class of probability distributions over functions for which any algorithm that gains information on the functions only by querying the gradient of the average of the sampled function needs $\Omega(1/\epsilon^4)$ queries to get within $\epsilon$ of the minimum expected loss.
main_review: As far as I can tell, this never actually proves that one can get a loss within $\epsilon$ of the optimum in $o(1/\epsilon^4)$ queries if one is not restricted to working with the averaged gradient, which means it does not actually prove the separation result in the abstract. The lower bound on the number of queries needed to get near the minimum is much less interesting without the contrast than it would be with it.

This appears to mostly use known techniques to prove the bound. The idea of bounding what one can learn from the gradient reminds me of statistical query bounds, although those would be weaker in that they would use a distorted form of the gradient. The organization is mostly fine, although separating the lemmas in section 4 from their proofs is confusing.

----------------------------------edit--------------------------

The textbook the authors mention in their rebuttal contains the positive half of the separation. So, I am now recommending that this paper be accepted.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper the authors prove an error lower-bound for full-batch first-order algorithms. This is a generalization of the bound given in Bassily et al. [2]. This new bound of the authors
- is true for a wider class of functions : GD and SGD, non-smooth and convex 
- implies that to get an $\epsilon$-risk, full-batch methods require at least $\Omega (1/\epsilon^4)$ iterations
This shows the advantage of stochastic methods like SGD which only require $\Omega (1/\epsilon^2)$ iterations to reach the same risk.
main_review: The authors clearly explain the background of Stochastic Convex Optimization (SCO) and present existing results and bounds. The authors also underline the fact that their bound is valid for a large family of algorithms (GD, projected GD, with smooth or non-smooth regularization, etc).
To extend their results to general full-batch algorithms, they apply a classical technique described in section 4.3 where they use a random high-dimensional embedding and apply the previous bound on a modified objective.

**Comment after rebuttal**

In view of the reviews and the discussions, the authors clarified their technical contribution compared to [1] and presented how this generalization could be applied to many 1st order methods including Nesterov's acceleration, CG etc.

Thus, I will increase my score to 7. 
limitations_and_societal_impact: This paper is theoretical only. No experiments are provided, even to illustrate the different bounds.  

This paper is a bit out of my standard scientific scope.
review_title: null

Meta-review: During the discussion phase, all reviewers and the AC found the results are interesting and novel enough for a presentation at NeurIPS. The paper has presented some solid results and bring new insights about negative results of full batch methods.  


Decision: Accept (Poster)