On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyond

We thank the reviewer for the review.

The convergence rates use classical and elementary tools (smoothness inequalities, stopping time in the stochastic setting) that already exist in the literature. For instance, similar convergence rates were established in Li et al., 2023a. The authors highlight some differences (section 4.1) with the related works but the arguments seem wrong or irrelevant.

We kindly request the reviewer to illustrate more on why "The authors highlight some differences (section 4.1) with the related works but the arguments seem wrong or irrelevant" as we found no supporting evidence for this claim in the review.

Some mathematical parts are wrong. For instance, the authors consider the regularization parameter to be zero but this leads to divisions by zero in the proofs (see for instance line 857) with no further assumption.

The claim "this leads to divisions by zero in the proofs" is wrong. $\nu_t$ can't be zero, as in Algorithm 1 we have described that $\nu_0 \in \mathbb{R}^+$ and since $\nu_t = \beta_2 \nu_{t-1} + (1-\beta_2) g_t^2$, one can easily prove $\nu_t > 0$ by induction.

The lower bounds are based on trivial and degenerate situations, especially in the stochastic setting. The lower bound function (Theorem 10 in Appendix) is based on a gradient noise which image by the gradient is not integrable, thus leading to a vacuous bound (all expectations become infinite). For instance, it does not depend on the smoothness parameters, which was the motivation stated in the introduction. Exhibiting the lower bounding function in the main text would make the presentation more honest and transparent. Lower bounds found in the literature are based on constructions that are much more sophisticated because they exhibit more restrictive properties (stability, gradient boundedness, etc.); see, for instance, Carmon et al., Arjevani et al.

We believe the reviewer has completely misunderstood our results of lower bounds. First of all, the result does depend on the smoothness parameter -- that the smoothness parameter is unbounded is why SGDM fails to converge (if assuming uniformly smoothness, SGDM is guaranteed to converge under proper hyperparameters, which is a folktale). Secondly, it is not our purpose to make the construction "much more sophisticated". Our purpose is to show the separation between SGDM and Adam.

Dear reviewer,

For instance the square dependence on the function value does not appear in Wang et al. You mention the issue of having lambda = 0 in Li et Al. 2023a. but in your work this is traded against the dependence on nu_0., this is the same.

For Wang et al.: the stated rate for Wang et al. is calculated from their Theorem 2 by minimizing their bound with respect to a, b, c (which is rather straightforward). Nevertheless, we will increase the calculation in the revised version.

For Li et al., we never claim that having lambda \ne 0 is an issue in Li et al, but rather "presents a convergence rate that depends polynomially on 1/\lambda" (line 196 in our paper) is. Our bound does not have a dependence over $1/\nu_0$, as can be seen from lines 1609-1618.

Your results can basically be retrieved from Li et Al 2023a by applying Cauchy Schwarz inequality on their bound.

This claim is WRONG and if the reviewer insists not, we kindly request the reviewer to illustrate in details. A basic fact is, that Theorem 4.1 in Li et al. uses the bounded noise assumption $|g_t-G_t| \le \sigma$ almost surely, while our assumption uses a much looser assumption of noise, allowing $\vert g_t - G_t \vert$ to be linear in $\vert G_t \vert$ in expectation. Such a gap is impossible to be bridged by simply "applying Cauchy Schwarz inequality on their bound".

Indeed the proof works with nu0 positive but it does not appear in the paper.

IT DOES APPEAR IN THE PAPER. Please see line 149 in algorithm 1.

My point about the lower bound is that you consider a degenerate case which is not relevant because it falls outside the setting of your upperbound ( expectations are infinite).

We are confused as to why it falls outside the setting of our upper bound. Kindly ask the reviewer to illustrate. As we described in Theorem 4, the lower bound result uses the same set of assumptions as theorem 3, and the results are also in the same form: Theorem 3 uses $1/T \sum E \Vert \nabla f(w_t) \Vert$, which naturally leads to an upper bound of $\min E \Vert \nabla f(w_t) \Vert$, while Theorem 4 presents a lower bound of $\min E \Vert \nabla f(w_t) \Vert$ and matches Theorem 3.

Dear Reviewer,

"negociate some boundedness assumptions compared to past works" is not incremental, as the main contribution of this COLT paper is doing so for AdaGrad "The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance".

Nevertheless, we never claim "negociate some boundedness assumptions compared to past works" is a main contribution of our work. If the reviewer still remembers, it is just a response to the reviewer's claim "Your results can basically be retrieved from Li et Al 2023a by applying Cauchy Schwarz inequality on their bound.".

how come $\nu_0$ has to be chosen positive and at the same time, the bound does not depend on $\nu_0$

We never claim that the bound does not depend on $\nu_0$ -- line 1609 shows there is a dependence over $\tilde{\nu}_1$, which in turn leads to the dependence over $\nu_0$. Also, in line 1509 the reviewer can see the bound positively correlates with $\nu_0$, which means if the reviewer chooses $\nu_0$ much smaller, the bound becomes even better (in coefficients).

About your lower bound, if the conditional expectation of the gradient is infinite then it cannot be upper bounded in expectation. You proof only require to build the lower bound function on the first iterate, it is then obvious that something is going wrong here.

We don't understand the reviewer's point here. Does the reviewer agree that the lower bound result uses the same set of assumptions as the upper bound result? Also, there is a misunderstanding that our proof only applies to the first iterate, from line 1628 to line 1662, the proof applies to all iterate. We kindly request that if the reviewer believes that the proof is wrong, the reviewer needs to point out the specific line of proof where it is wrong, instead of saying that "it is then obvious that something is going wrong here."

Dear reviewer,

we don't understand your point here -- you seemingly refer to that the considered "convergence" is not the same for the upper bound and lower bound result, right?

To be clear:

• For the upper bound, we consider $1/T \sum_t E \Vert \nabla f(w_t) \Vert$.

• For the lower bound, we consider $min E \Vert \nabla f(w_t) \Vert$.

The reviewer seems to suggest that these two measures are not the same, right? But this is not a problem -- we have $min E \Vert \nabla f(w_t) \Vert \le 1/T \sum_t E \Vert \nabla f(w_t) \Vert$ -- that means if we have a lower bound for $min E \Vert \nabla f(w_t) \Vert$, we will immediately have a lower bound for $1/T \sum_t E \Vert \nabla f(w_t) \Vert$. Similarly, if we have an upper bound for $1/T \sum_t E \Vert \nabla f(w_t) \Vert$, we will immediately have an upper bound $min E \Vert \nabla f(w_t) \Vert$.

The above reasoning shows, although our upper bound is in $1/T \sum_t E \Vert \nabla f(w_t) \Vert$, it trivially leads to an upper bound in $\min E \Vert \nabla f(w_t) \Vert$; the same for the lower bound -- the current lower bound also trivially leads to a lower bound in $\min E \Vert \nabla f(w_t) \Vert$.

Therefore, both comparisons in $\min E \Vert \nabla f(w_t) \Vert$ and $1/T \sum_t E \Vert \nabla f(w_t) \Vert$ lead to the separation of SGDM and Adam.

This is not short cut, and we prove something stronger -- the stronger version of the upper bound, i.e., $1/T \sum_t E \Vert \nabla f(w_t) \Vert$, and the stronger version of lower bound, i.e., min E \Vert \nabla f(w_t) \Vert.

You can try it yourself: compute averaged expected gradients on your lower bounding function and you will see that it cannot be upper bounded in this sense.

We have to say we have been very confused by the reviewer's comment... Why do we need to upper bound the average expected gradient? Isn't it our goal to lower-bound it? If the reviewer is referring to the lower bound, the concerns should be resolved by the above reasoning.

Since the authors haven't addressed my concerns about the proof of Theorem 3 yet, I modified my rating of this paper. I will re-evaluate the paper after receiving the updates from the authors.

2. On the restrictions: Maybe we got the reviewer wrong, but the restrictions of $\beta_2$ and $\beta_1$ has already been captured in line 1102 $\beta_2 = 1- \eta^2 (...)^2$. Similar for the reviewer's first two questions.

3. For the optimal solution of $\beta_2$: we only intend to indicate the "existence" of the optimal hyperparameters that make Adam's convergence meet the lower bound. In practice, there is more direct practice such as grid search to get the optimal hyperparams.

4. Extension to Adam: We thank the reviewer for the suggestion. We will include a detailed explanation on how to extend the result to coordinate-wise Adam in the revised version of this paper.

We want to thank the reviewer for the careful review sincerely. Also, sorry for the late response -- the authors just got time to carefully read the reviews today.

1. For theorem 3: thanks for pointing it out and you are correct. We missed the third term in the proof and apologize for that. Nevertheless, the third term itself is easy to bound (a similar proof can be found in eq. (13) in "Closing the Gap Between the Upper Bound and the Lower Bound of Adam’s Iteration Complexity"). Specifically, this term can be bounded as $\frac{\beta_1 \eta(1-\beta_2)\sigma_0^2}{1-\beta_1/\sqrt{\beta_2}} \Vert G_t\Vert \Vert m_{t-1}\Vert \frac{1}{\sqrt{\tilde{\nu}_t {\nu}\_{t-1} }(\sqrt{\tilde{\nu}_t} + \sqrt{ {\nu}\_{t-1}})} \le O(\Vert G_t\Vert^2/\sqrt{\tilde{\nu}_t}) + O(\eta\sigma_0\sqrt{1-\beta_2}/(1-\beta_1)^2 \Vert m\_{t-1}\Vert^2 /\nu\_{t-1})$. The two terms on the right side all appear at eq. (13), line 1269 (the latter one has a different footscript $t-1$, but this does not matter as the latter we take summation of t), and thus the rest of the proof is the same. We will include the missing proof in the latter version.