Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this paper, the authors provide a solid convergence analysis which suggest Adam can converge to stationary points by picking proper $\beta_1$ and $\beta_2$ after fixing $n$. The conclusion is proved without assumption of bounded gradient.  The analysis can provide new insights for tuning Adam. 
strengths_and_weaknesses: Strengths: 
+ The authors provide a through convergence analysis for the well-known unconvergence issus of Adam.  By picking large $\beta_1$ and $\beta_2$ after fixing $n$, the authors prove Adam can converge to stationary point of the specific function class given by Assumption 2.1 and Assumption 2.2. 
+ Compared to the divergence counterexamples provdied by [1], the target function is generalized to a larger class.  

Weaknesses: 
+ However, some prior works [2] have provided the similiar conclusion that, after fixing the unconvergen counterexamples in [1], tuning larger $\beta_1$ and $\beta_2$ can make Adam converge. Meanhwile, they provide an equation to descibe the relation between $\beta_1$, $\beta_2$ and $C$ (the divergence cirtical point in [1]). Even so, their analysis is contrained on the convex finite-sum problem in [1] and not generalized. The analysis in paper would be more general. Can authors explain more comparison and strengths over them? 
+ Theorem 3.1 depends on Assuption 2.2 which contrain the variance of stochastic gradients. However, the unconvergence of Adam emerges only when variance is large [1]. Would Theorem 3.1 mean that Adam converge when gradient variance is within the constrains in Assumption 2.2? Can author analyze the behavior of Adam and how to tune $\beta_1$ and $\beta_2$ when gradient variance is large enought to diverge Adam? 

[1] On the Convergence of Adam and Beyond. ICLR 2018. 
[2] AdaShift: Decorrelation and Convergence of Adaptive Learning Rate Methods. ICLR 2019. 
[2] Adaptive Gradient Methods with Dynamic Bound of Learning Rate. ICLR 2019. 
questions: In the unconvergence counterexample provided by Reddi et al, 2018, the gradient variance is coupled with the number of target functions, i.e. $n$. Can authors explain more about how to decouple $n$ and gradient variance in your analysis? 
limitations: Some prior works have provided similar conclusion that tuning large $\beta_1$ and $\beta_2$ can make Adam converge. Even so, this paper provides a more solid and through analysis on generalized function class.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the Adam algorithm and proves that randomly shuffled Adam converges to the neighborhood of stationary points when 1st and 2nd-order momentum parameters satisfy that $\beta_1 < \sqrt{\beta_2} < 1$ and $\beta_2$ is sufficiently large. The analysis does not rely on the bounded gradient assumption. The divergence behavior of Adam is also studied, where it is shown that when $\beta_2$ is small, Adam can diverge to infinity for a large region of $(\beta_1, \beta_2)$.
strengths_and_weaknesses: The convergence analysis of Adam is an important topic, and the claim made in this paper advances the understanding in this regard. The paper is well-written and easy to follow, and the graphic illustrations are nice. Some discussions on the comparison with existing works look redundant, especially those repeatedly emphasizing the removal of the bounded gradient assumption and the difference between the current work and the result in Reddi et al. (2018). I think these should be more condensed. 

The theoretical analysis seems to be novel, though there might be some issues as will be discussed below. I'm willing to adjust the score if the questions are addressed.
questions: Some comments and questions are as follows.

1. The font of some figure legends is too small, e.g., Figure 1(a, b, c), Figure 2, and Figure 4. The axis labels like beta1 and beta2 should be replaced with $\beta_1$ and $\beta_2$.
2. In Theorem 3.1, is $T$ fixed? What is the dependence of $\beta_2$ on $T$?
3. Theorem 3.1 only shows that the loss gradient will become smaller in expectation, and there is still a gap between the convergence of $\mathbb{E}[||\nabla f(x_{k,0})||]$ and the actual convergence of $x_{k,0}$. How to resolve this?
4. As shown in Figure 4(c), the training loss does not seem to converge even for large $\beta_2$?
5. In the statement of Lemma G.6, $\alpha$ is a random variable, but the left-hand-side of the equations after line 996 are expectations, so why can they be bounded by a random variable?
6. In Appendix G.3 for the proof of Lemma G.3,  $\frac{\partial_\ell f(x_{k,0})}{\sqrt{v_{k,0}}}$ should be $\frac{\partial_\ell f(x_{k,0})}{\sqrt{v_{\ell,k,0}}}$ instead? Similarly for the subsequent proofs.
7. When controlling term (a) in the equation after line 1156, in the first inequality where Lemma G.12 is applied, there is a problem with the second term. Due to the indicator $\tilde I_{k, k-1}$, we have $\max_i |\partial_\ell f_i(x_{k,0})| \geq Q_k$ which is a lower bound on the absolute value, and this does not lead to an upper bound on the absolute value of the second term, so the inequality is wrong here. Did I miss anything? If not, how to fix this?


---
Minor issues:

1. In the statement of Lemma F.3, it should be $|\partial_\ell f_{\tau_k, i}(x_{k, i+1}) - \partial_\ell f_{\tau_k, i}(x_k,i)|$?
2. Unify terms like $1+\beta_1+\beta_1^2 + \cdots$ and $1 + \beta_1 + \cdots + \beta^\infty$ (define this properly).

limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This manuscript studied the Adam algorithm in the finite-sum setting: the number of samples is fixed in advance and Adam can pick $(\beta_1,\beta_2)$ according to it. The authors showed that under the case $\beta_1<\sqrt{\beta_2}<1$ and large $\beta_2$, Adam can converge to the stationary point under strong growth conditions and without bounded gradient assumption. When $\beta_2$ is small, the authors also identified a region of $(\beta_1,\beta_2)$ such that Adam diverges. Some simple experiments on standard benchmark datasets are provided to justify the theoretical findings.
strengths_and_weaknesses: Strengths: 
1. The paper studied an important problem: the convergence of Adam in the finite-sum setting and the number of summands in the objective function is known in advance.
2. The paper is generally well-written.
3. The proof idea is clearly presented.

Weaknesses:
1. While the results are interesting, I doubt the significance and the logical flow of this result. 

(1). The paper does not convey important messages about the convergence of Adam compared with Reddi et al. 2018. In particular, Reddi et al. 2018 studied Adam in the online convex optimization setting: they provided regret guarantees and non-convergence of average regret. However, this paper can only guarantee Adam's convergence with the strong growth condition and only to a stationary point. I don't see why the framework of finite-sum optimization and the knowledge of $n$ (i.e., the number of samples) would be so important to differentiate this paper from Reddi et al. 2018. 

For example, it might be possible that in the particular case of  $\beta_1<\sqrt{\beta_2}<1$ for Adam, the average regret does not converge but Adam indeed converges to a stationary point in the online learning setting such as Reddi et al. 2018 (where $n$ is not available). To show the fundamental advantage of finite-sum optimization and the knowledge of $n$, the authors are expected to show something like this: for an online nonconvex optimization problem, Adam with $\beta_1<\sqrt{\beta_2}<1$ with large $\beta$ and any other parameter choice (i.e., learning rate) cannot even converge to a stationary point in polynomial time, but the finite-sum version of this problem can indeed converge in polynomial time.

(2). The convergence to stationary point only when $D_0=0$ in Theorem 3.1. What is the relationship between $D_0=0$ in Assumption 2.2 and the bounded gradient? We know that Adam can converge if we have a bounded gradient (e.g., Guo et al. 2021).

2. Experiments are rather weak. The authors did not perform an ablation study in terms of $n$ (i.e., the number of training samples). Since this is the main message of the paper, the authors are expected to show that without the knowledge of $n$, Adam would diverge due to inappropriate hyperparameter choice (e.g., learning rate, $\beta_1$ as in Theorem 3.1).



questions: 1. Why this paper's message is important compared with Reddi et al. 2018? Why the knowledge of $n$ in finite-sum optimization is so important? What does the result look like in the online nonconvex optimization and finite-sum convex optimization setting?  

2. The regret minimization might fail in certain regimes of $\beta_1,\beta_2$, but it might also converge to a stationary point without the knowledge of $n$ or even in an online setting. I don't know why Theorem 3.1 is so important since it is not comparable with Theorem 4 of Reddi et al. 2018. To establish the importance of the finite-sum setting, the authors need to provide a hardness result in an online learning setting in terms of non-convergence to a stationary point in polynomial time. 

3. What is the relationship between $D_0=0$ in Assumption 2.2 and the bounded gradient? We know that Adam can converge if we have a bounded gradient (e.g., Guo et al. 2021).

4. How does the knowledge of $n$ affect the results theoretically and empirically?

If these concerns can be addressed, I am happy to increase my score.


======POST REBUTTAL======

Thank you for the authors's response. I have read other's reviews as well. My main concern still remains with the finite-sum structure, but I  decided to change my evaluation a bit after reading the rebuttal.
limitations: N/A
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proves that Adam with hyper-parameters $\beta_1 \leq \sqrt{\beta_2}<1$ and large $\beta_2$ converges to a neighborhood of stationary points under mild assumptions on the function class and if Strong Growth Condition is satisfied, it converges to stationary point. Specifically, they argue that analyzing Adam with large $\beta_1$ which results in large momentum is harder and previous works could not manage to handle non-zero $\beta_1$. 
strengths_and_weaknesses: This paper is superbly written and the proofs, although being long, are managed to be as clear as possible. The writing style is excellent and helps reader understand the main ideas, specially the long proofs. I checked all the proofs, except for pages 56-58 and 60-64. Except for some typos, which do not affect the results, I could not find any flaw. I really like how you manage to use color-ball method and finite vs infinite sum argument in your work. Also as pointed out in several places, you explain the short-comings of previous work in analyzing non-zero $\beta_1$.The removal of bounded gradient assumption and sticking to Assumption 2.1 which encompasses SGC and constant variance assumptions also looks entertaining. Example of giving convex functions in prop. 3.3 when Adam diverges in a relatively large region is also instructive: small $\beta_2$ is dangerous. examples on practical networks also corroborate the analytic results. This piece of work seems to have important contribution for analyzing methods with momentum like Adam and as pointed in conclusion, it paves the way for much more intricate convergence analysis of Adam and its effectiveness compared to SGD. I highly recommend this paper to be accepted.
questions: Question:
1) in lines 123-124, can you tell me (intuitively) why SGC is reasonable in overparametrized regime?can you point out to more literature (if any) regarding SGC?

2) You say in line 98 that in your theoretical analysis you let $\epsilon$ be an arbitrary non-negative constant including 0, but in proofs I couldn't catch that. It seems to me you just set it to 0. Please explain.
 
3) in line 625, is it like you can $\beta_1=0$ and large $\beta_2$ can converge repeating the proof of Reddi? or is it a fundamentally different approach?

4) in lines 196-199, I can't understand why smaller batchsize needs a larger $\beta_2$. The bound $\gamma_1(n)$ increases with n, so it seems to me that smaller $n$ has smaller $\gamma_1(n)$ hence smaller $\beta_2$ is okay.
 
Grammatical Typos:

line 93, randomly. line 125, converge "to". line 161, require. line 205, "and". line 262, "red". line 328, "reduces". line 509, "some more". line 597 and 622, "require".  line 658, "as". line 677, "an". line 690, converge"s". line 732, this. line 732, "a" instead of "an". 

Math typos:

line 225 and 699, I think for $i>0$, $f_i(x)=1/2(x+2)^2"+"3/2$. 

line 291, equation 3, why there is no sign of $v_{k,0}$ in r.h.s (which is the case in equation 4) ?

line 311, definition of $m_{l,k,i}$ should have $f_\tau$ rather than $f$.

bottom of page 22, $\beta_2$s in nominators may change to $\beta_1$.This also occurs in line 734, first line.

line 725, first line, $j=0$.

line 739, I feel a missing $1\sqrt{k}$ in r.h.s. Also in line 740, there might be a missing $n$ in r.h.s. because of the summation.

just above line 789, definition of $v$ should have $\beta_2$ rather than $\beta_1$.

line 793, eq 17, $f_{\tau_{k,i+1}}(x_{k,i})$ should change to $f_{\tau_{k,i}}(x_{k,i+1})$, which is corrected in line 795.

line 815, $x_k - x_{k+1}$ instead of $x_{k+1} - x_{k}$.

line 837, 2nd line, based on eq (18) there might be a missing $\frac{1}{\sqrt{1-\beta_2}}$, which just affects $F_1$.

in the lines following line 1052, the subscript $\ell$ is missing. you can note that in the beginning of Appendix $G_3$ to prevent confusion.

equation at the bottom of page 40, based on Lemma F.3 you may have an extra factor of $n$, as Lemma F.3 deals with $f_\tau$ rather than $f$.

bottom of page 46, $-\frac{1}{\sqrt{k}}$.

in equation 45, I feel like $f_0$ should cancel out in all epochs, just like epoch 0.

in lines 1159 and 1166, Lemma G.12 gives $\beta_2^n$ in denominator rather than nominator. Please correct it.

line 1163, second equation, it is $ (F_{l,k}) _{k-1}$.
limitations: regarding negative societal impact, as authors pinpoint, training neural nets for illegal use is the main concern of this kind of work.
review_title: null

Meta-review: metareview: This paper proves that the vanilla Adam algorithm can converge to a stationary point with properly chosen $\beta_1$ and $\beta_2$ if the number of samples $n$ is fixed, in contrast to the well-known non-convergence example by Reddi et al. This result has a clear conceptual message, which justifies the use of vanilla Adam, and it's worth sharing the result with the ML community. The reviewers find the presentation and the analysis to be of high quality as well.
confidence: Certain
Decision: Accept