Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper introduces three new algorithms for making gradient small in (finite-sum) the convex setting: (1) the first algorithm comes with a new parameter setting for OGM-G, matching the lower bound in the deterministic setting. (2) the second algorithm combines loopless-SVRG with OGM framework (3) the third algorithm is an accelerated SVRG with adaptive regularization, matching the lower bound up to logarithmic terms. 
main_review: Originality: I believe the ideas and algorithms are original. 

Clarity: The paper is well organized and easy to read. 

Significance: Finding near-stationary point in convex setting is a critical task and has been explored by many previous work.

Comments
1. My largest concern is the improvement over previous work is incremental. The analysis of OGM-G under a potential function has appears in Diakonikolas and Wang, 2021, although the potential function is not exactly the same. The second algorithm is not optimal in either $n$ or $\epsilon$ in minimizing the gradient norm. The third algorithm does not improve over regularized Katyusha in the complexity. Although it does not require the knowledge of constant such as $R_0$ it still requires to know $L$.

2.  I think one of the drawbacks of algorithm 2 may be that it still needs to prefix the total iteration $N$. 

3. Although the second algorithm can be used to both finding small function value and small gradient norm, it outputs different points based on different criterion (last iterate when using optimal gap and a random iterate when using gradient norm). Is it possible to output a point with both small function value and gradient norm?

4. The paper only provides the experiment for algorithm 3 and the comparisons with the state-of-the-art are missing. Since the complexities of algorithms does not improve over the previous algorithms, it benefits to do experiments to compare the performance. 

Minor comments 

5. In Remark 3.2.1, the last iterates converge follows directly from Theorem 3.2 with $\delta_{N+1} = 2$, which directly implies the minimum gradient norm is small.

6. It would be interesting to explore algorithm without regularization to achieve the lower bound with IDC setting. 

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies efficient methods for finding near-stationary points ($||\nabla f(x)|| \le \epsilon$) of a convex (finite-sum) function. The authors nicely introduce main reasons for the need of such research, and their three main contributions are as follows.

First, this paper provides variants of OGM-G that is an optimal method for finding a near-stationary point for a smooth convex function under the initial bounded-function condition (IFC). In specific, Proposition 3.1 complements the complexity of OGM-G (with and without a change of coefficient at the last iteration). In addition, a memory-saving variant of OGM-G was studied, which does not require computing coefficients in advance. 

Second, based on OGM and the loopless SVRG, the authors propose Acc-SVRG-G. With the two-stage parameter choice under the initial bounded-distance condition (IDC), it has fast rates for minimizing both the gradient norm and the function value for the first time. 

Third, with adaptive regularization, the Acc-SVRG-G achieves the best existing rates (by the regularized Katyusha) up to a logarithmic factor, in terms of minimizing the gradient norm, under both IDC and IFC. The proposed R-Acc-SVRG-G has advantage over the regularized Katyusha, since it does not require the knowledge of $R_0$ and $\Delta_0$. 
main_review: As stated in the beginning of the abstract, finding near-stationary points of convex optimization has not received attention, although it is fundamentally important. I think this paper nicely fills in the gap. In specific, developing variants of OGM-G is a nice complement to OGM-G, especially Proposition 3.1 and the relaxation of (P). A more interesting contribution of this paper is the development of both Acc-SVRG-G and R-Acc-SVRG-G. The latter achieves the best existing rates up to a logarithmic factor, while not requiring the knowledge of the (usually unavailable) initial constant, which is new and important.

I only have couple of minor comments.
- line 37: NAG having a suboptimal rate for minimizing the gradient does not seem to be a sufficient reason for saying that finding near-stationary point is a "harder" task.
- line 46: NAG + OGM-G is missing in the "IDC + IFC" case, unlike the Katyusha + L2S. Its variant is later mentioned in Corollary 3.2.1, so it would be nice to mention NAG + OGM-G at some point.
- line 73: I am curious here whether the function value complexity of Acc-SVRG-G is comparable to the best existing complexity.
- line 118, 254, 258: Note that a very recent paper below (appeared after the submission deadline) found a potential function for OGM-G and its proximal variant.
J. Lee, C. Park, E. K. Ryu, ``"A geometric structure of acceleration and its role in making gradients small fast,'' arXiv:2106.10439.
- line 123: OGM-G only has a convergence guarantee on the last iterate, and the authors claim that this can be resolved by M-OGM-G. However, Theorem 3.2 with a bound on the weighted sum of all iterates does not fully resolve the issue of OGM-G as I hoped from the line 123. 
- line 135: In footnote 5, shouldn't it be local solutions, rather than approximate solutions?
- line 143: What do you mean by "Algorithm 2 converges optimally on the last iterate"?
- line 149: It is minor, but it would be nice to have a square in the gradient norm, so that it is consistent with the IFC case.
- line 177: $f(x_0) - f(x^*)$ -> $\Delta_0$?
- line 183: Is there any intuition behind the "warm-up phase", besides the two-stage proof in Appendix? This isn't used for R-Acc-SVRG-G. Would it be useful?
- line 191: Is the analysis for the low accuracy regime meaningful? (I might just being not familiar with such analysis.) Does Acc-SVRG-G with different parameter choice or any other existing method (like Katyusha) have a larger complexity for such regime?
- line 208: Which rate should I compare here?
- line 213: I kind of understand that such termination conditions indicate the poor quality of the current estimate $\delta_t$. Could you explain it in more details?
limitations_and_societal_impact: - In Section 4, since previous section studied OGM-G for finding near-stationary point, I was expecting the Acc-SVRG-G to be built upon (or related to) OGM-G (other than NAG and OGM). Also, while Section 3 mainly assumes IFC (then IDC), Section 4 mainly assumes IDC. Although the resulting analysis is interesting, I found Sections 3 and 4 to be somewhat disconnected. 

- The parameters for R-Acc-SVRG-G is relatively complicated, but this seems inevitable.

- A numerical experiment in comparison to L2S, SAG, SVRG in Appendix A looks promising, but it is not sufficient in the eyes of practitioners. The authors did not compare with other algorithms that require fixing the accuracy $\epsilon$, but still one can compare methods in terms of the number of computational complexity to achieve the accuracy. (Note that I am not asking for further experiments, since the paper is theory-oriented.)
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: This paper proposes several optimization algorithms: 1. a memory-saving variant of OGM-G (by the way, could the authors provide the full name of OGM-G?); 2, a new accelerated SVRG (full name?); 3, Near-Optimal Accelerated SVRG with Adaptive Regularization. Analysis of convergence rate is provided.
main_review: For the vanilla OGM-G, a reformulation is provided, and the convergence of the norm of gradient with the speed of O(1/N) is derived.

For the Memory-Saving OGM-G, the convergence rate O(1/N) is obtained for the minimum norm of gradient across the iterations 1, ..., N.

For accelerated SVRG, in terms of the norm of gradient, convergence rate O(1/N^1.5) is derived; in terms of function value, the convergence rate of O(1/N) is derived. (is K in this section the count N in previous sections? Would it be better to unify the notations?)

For Near-Optimal Accelerated SVRG with Adaptive Regularization, analysis is done around two initial value conditions, the first is Initial bounded-Function Condition (IFC), i.e., the function value at the initial guess is not too far away from the global minimum; the second condition is Initial bounded-Distance Condition (IDC), i.e, the initial guess is not too far away from one of the global optimizers.
limitations_and_societal_impact: Limitations: not seen

Societal Impact: solid improvement of the optimization algorithms discussed, and therefore a better service to different application scenarios.
review_title: null

Meta-review: The paper considers algorithms to find near stationary points ( $\\| \nabla f(x) \\| \\le \epsilon $ ) for convex finite-sums, as opposed to finding points with small objective value $f(x) - \\min_y f(y) \\le \\epsilon$. They propose three new algorithms.  As one reviewer said during discussion (and seconded by another reviewer), they liked that the proposed M-OGM-G method is produced from a computer-aided method (PEP-style ideas being a new field of optimization), they agree the proof for Acc-SVRG-G is very non-trivial, and also that this problem (of near stationary points) is of interest and has not seen enough attention.

Reviewer 3GpM gave the paper a very high score, but explained more in discussion that this was mainly due to the apparent correctness of the math, and not necessarily to be interpreted as an overall score (in terms of contribution).

The dominant concern of all reviewers (including 3GpM) was that the paper is too incremental. For each of the three algorithms, there are specific improvements, but some of these are slight.  Even the most positive reviewer, 3GpM, was less enthusiastic after reading the author(s) response to reviewer hnRP, as this makes it sound like the improvement is incremental.

Looking at the paper myself, the paper is nicely written, and I like the fact that it reviews recent literature. But it's really a collection of a few small improvements, and I don't think these "sum" up to be equivalent to a major result.  This is nice work, but the end result is just not particularly exciting.  My suggestion is the the authors submit this work, with only minor changes, to a slightly lower tier venue, as I think the work deserves to be published but just not necessarily in a tier-1 venue.
Decision: Reject