Clipping Improves Adam and AdaGrad when the Noise Is Heavy-Tailed

Thank you for your thorough review and remarks. We are grateful that you emphazise the strengths of our work.

Weaknesses

The authors stated “Adam can be seen as Clip-SGD with momentum and iteration-dependent clipping level"

Indeed, Adam can be interpreted as some variant of Clip-SGD with momentum and time-varying clipping level. This is so because Adam has a parameter $\beta_1$, responsible for the momentum, and also a scaling factor normalizing the step direction in some way. Our results show that latent clipping (built into Adam or AdaGrad) is not sufficient, i.e., it does not allow us to deal with noise with heavy tails (to be more precise, our lower bounds in Theorems 5-8 show the absence of a logarithmic factor, which we would like to see in the bounds for the required number of iterations for convergence with high probability). This demonstrates why latent clipping in the Adam/AdaGrad methods is not enough to deal with heavy-tailed noise.

Some comparisons of results are...

Thank you for your thoughtful comment. We will add a table with comparison of study of methods with and without clipping under different assumptions on stochasticity a little bit later.

Questions

1. Yes, the later refers to LLMs as it was observed that stochastic gradients of these models exhibit heavy-tailness property. Another well-studied example is GANs. It is not the case that all the models have heavy tailed noise in stochastic gradients, but, in particular, for both LLMs and GANs, clipping is essential to make their training stable and our work explain why this is case from the theory point of view.
2. Here we refer to the case of stochasticity with heavy tails.
3. We suppose that we already describe the meaning of the phrase “Adam can be seen as Clip-SGD with momentum and iteration-dependent clipping level” in the Weaknesses section.

We are grateful for your thorough review and comments. Thank you for acknowledging strengths of our paper.

Weaknesses

On negative results

We kindly disagree with this point. Indeed, the choice of $\beta_2$ as $1 - \frac{1}{T}$ is natural for the following reason - the divergence of the Adam method has already been shown in [3]. That is why, in order to show the advantage of Adam/AdaGrad with clipping over non-clipped versions, we need to consider exactly the same parameter $\beta_2$ as in the study of theoretical guarantees of convergence of Adam/AdaGrad with clipping (see Theorems 2-4). As for the constraint on the initial distance, it seems to us to be intuitive - it indicates that our starting point is not very close to the solution.

As for $\Omega(*poly*(\varepsilon^{-\frac{1}{2}}))$, we agree with the reviewer - our lower bounds suggest that the method converges. But this is what we need. Theorem 1 (see proof in Appendix, Theorems 5-8) says that the number of iterations required for high-probability convergence necessarily depends on $\frac{1}{\delta}$ in some power, that is, there is no logarithmic factor of $\frac{1}{\delta}$. This is enough to demonstrate the advantage of clipped Adam/AdaGrad over unclipped methods.

If we discuss [1], Remark 1 demonstrates that SGD with heavy-tailed noise can diverge. But it does not say that it will always diverge. To understand this fact it is enough to see that the divergence in [1] is shown in the paradigm of convergence on mathematical expectation, i.e. SGD diverges on mathematical expectation. But in our work we consider convergence with high probability. And, to repeat, to demonstrate the outperformance of clipped Adam/AdaGrad over unclipped ones, the consideration of Theorems 5-8 (combined into Theorem 1 in the main part) is sufficient (see the explanation above).

On results regarding clipping

Thank you for this important clarification. The logarithmic factor is written in the parameter $A$ for Theorems 2, 3 and 4 for convenience, since from our point of view they are rather large. The proof of each of these theorems has a convergence bound that depends on $\gamma$ (see Appendix). After substituting $\gamma$ as given in theorems’ formulations, we can get a bound for the required number of iterations in terms of $\tilde{\mathcal{O}}$, where the logarithmic factor is hidden.

If we discuss the use of delayed stepizes, it is worth noting that this technique is not new. First, it is worth noting [3], where the instability of Adam behavior was studied. To combat this instability, the AMSGrad method was proposed, which is based on the idea of delayed stepsizes: it is enough to refer to the algorithm and look at the $\hat{v}_t$ update. The only thing worth clarifying is that the delayed stepsize has a slightly different structure. Moreover, delayed stepsizes can be mentioned in studies of distributed systems and parallelization, but that is beyond the scope of our study.

Finally, let us discuss the result from [2]. As it has already been noticed, in [2] a similar result was obtained, except for a small difference. In fact, in this difference lies the whole difference of the considered problems. Indeed, let us turn to [2]. The convergence of AdaGrad with clipping is given in Theorem 13, which states that assumptions are made on the $L$-smoothness of the empirical risk, its uniform boundedness and boundedness of $\alpha$-th moment. Therefore, in the worst case, these assumptions imply the boundedness of $\nabla f_{\xi}(x)$ , meaning that the noise is bounded and, thus, sub-Gaussian. At the same time, AdaGrad analysis is already available for such noise (see [4]), and without clipping. That is, in [2] clipping for AdaGrad is applied unreasonably, since the polylogarithmic factor can be achieved without it under the assumptions made by the authors of [2]. Furthermore, we already discussed the result from [2] in our paper (see Discussion of the results after Theorem 4).

References

[1] Zhang J, Karimireddy S P, Veit A, et al. Why are adaptive methods good for attention models?

[2] Li S, Liu Y. High Probability Analysis for Non-Convex Stochastic Optimization with Clipping.

[3] Sashank J. Reddi, Satyen Kale & Sanjiv Kumar. On The Convergence of Adam and Beyond.

[4] Zijian Liu. High Probability Convergence of Stochastic Gradient Methods.

Dear Authors,

Sorry for the delayed reply. I have read carefully of your rebuttal and I agree that the negative result is meaningful as $\beta_2 = 1-1/T$ commonly appears. I think that the concern comes from whether other setups of $\beta_2$, such as $1-1/t$ or $1-1/\sqrt{t}$ or any general setup that closes to one may still lead to a polynomial order of $\delta$. That's the reason why I think that Theorem 1 is limited. You comment that $1-1/t$ could be derived easily. I hope that this may be written down clearly in the new version if possible.

Second, I hope to see a clear motivation for adding the delayed step-size as I do not see it clearly from the rebuttal. I do not agree that it's a very common mechanism.

Third, I want to remind you that there are some recent works studying the high probability of AdaGrad and Adam with logarithm order of $\delta$, see e.g., [1,2].

However, I recognize the value of this paper and thank you for the authors' detailed response. I will raise my score to 5.

References.

[1] Kavis A, Levy K Y, Cevher V. High probability bounds for a class of nonconvex algorithms with adagrad stepsize. ICLR, 2022.

[2] Yusu Hong and Junhong Lin. Revisiting Convergence of AdaGrad with Relaxed Assumptions. UAI 2024.

We are grateful for your review and comments. Thank you for emphasizing the strengths of our work.

Weaknesses

Not analyzing Adam, but a twin of Adagrad:

We kindly disagree with the provided statetement. To the best of our knowledge, $\beta_2$ close to $1$ is a common choice for analysis of Adam, e.g., see [1]. Furthermore, looking at the results of [2], it is clear that the constraint on $\beta_2$ is $\beta_2 \geq 1 - \mathcal{O}(\frac{1}{n^2})$, where $n$ is the size of the entire dataset (see Theorem 3.1). Even if we choose $\beta_2$ for $n = 1000$, this parameter does not correlate with what is used in practice. And, to be more precise, in most cases $\beta_2 = 1 - 1/K$ is smaller than $\beta_2$ from [2]. This means that $\beta_2$ cannot be called a constant. Therefore, we kindly disagree that our Adam analysis would be weaker when compared to prior work.

Analyzed scalar-coefficient clipped version

We kindly disagree with the point that scalar-coefficient and vector-coefficient versions are quite different. Indeed, we can look at [3], where, for example, AdaGrad and AdaGrad-norm under Subgaussian noise are investigated. The ideas of the proofs are the same, except for the usage of norm for AdaGrad-norm and coordinate notation for AdaGrad. Nevertheless, we agree that it's worth renaming AdaGrad to AdaGrad-norm (Adam too) to avoid misunderstanding.

Contribution

We appreciate the reviewer's feedback. Our work focuses on analyzing Adagrad-Norm and Adam-norm with clipping and demonstrates its effectiveness under heavy-tailed noise, which is a known practical challenge in optimization. While this differs from the original Adam, our analysis highlights critical insights into the role of clipping in adaptive methods. As noted earlier, the scalar-coefficient and vector-coefficient approaches share similar proof techniques, and our findings remain relevant to practitioners aiming to improve optimizer stability. We will revise the terminology in the manuscript to ensure clarity and alignment with our analysis.

References

[1] Manzil Zaheer. Adaptive Methods for Nonconvex Optimization

[2] Yushun Zhang. Adam Can Converge Without Any Modification On Update Rules

[3] Zijian Liu. High Probability Convergence of Stochastic Gradient Methods

I've read the authors' response, but it is not convincing.

1. "To be more precise, in most cases, 1 - 1/K is smaller than $\beta_2$ from [2]. This means that cannot be called a constant":

This comment does point out a gap between theory and practice, but the conclusion is not acceptable. For finite-sum problem where n is fixed, any parameter that only depends on n is a constant. In contrast, K is a changing parameter, which is more like a diminishing stepsize in classical analysis of gradient descent or stochastic gradient descent. One could say there is a gap between the constant in [2] and the practically used constant (a common thing in theory), and one can even say in a changing-sample-size problem 1-g(n) is not a constant, but one cannot say it is not a constant in the setting of fixed-n finite-sum problem.

There are a few more examples to illustrate the point on "constant" v.s. "non-constant" in optimization. For instance, there are many optimization algorithms (including but not limited to affine scaling method, a few distributed optimization methods, etc.) whose convergence for constant stepsize are proved for small stepsize, while in practice people used large stepsize. In this example, one could say there is a gap between the constant in theory and the constant in practice, but one cannot say the theory for these methods do not prove the result for a constant.

Another example is SGD's constant stepsize v.s. diminshing stepsize: it is well known that diminishing stepsize like 1/sqrt{K} is needed for SGD for finite-sum optimization to converge, and some researchers argued that 1/sqrt{K} is larger than the stepsize used for some practial problems. Howver, it is considered a good contribution when researchers proved that SGD with constant stepsize can converge under certain conditions -- people do not need to consider whether the constant of the proof is smaller than 1/sqrt{K} or not, as the first step towards convegence of constant-stepsize SGD. The precise charaterization of the constant is left to future work. Again, in this example, one could say there is a gap between the constant in theory and the constant in practice, but one cannot say the theory for these methods do not prove the result for a constant.

"We kindly disagree with the point that scalar-coefficient and vector-coefficient versions are quite different; we can look at [3], where, for example, AdaGrad and AdaGrad-norm under Subgaussian noise are investigated. The ideas of the proofs are the same, except for the usage of norm for AdaGrad-norm and coordinate notation for AdaGrad."

This response is NOT convincing. The paper [3] is just analyzing one specialized setting (under a certain set of assumptions), and in this setting, for "scalar-coefficient and vector-coefficient", the ideas are the same do not mean in general the two settings are the same. I think the naming of analyzed algorithm should be more rigorous, and not be renamed just based on the authors' understanding of proof techniques.

After careful thought, I think the authors might not get the essence of my original comment and the response has led to a less relevant path. I'd like to clarify a bit more, since this may be useful for the community.

My original comment says: "The analyzed algorithm with 1-1/K is essentially Adagrad." Let me clarify a bit. Consider three setttings of beta2 for Adam.

Setting A1 (diminshing 1 - beta2): Adam with beta2 = 1-1/k where k is the iteration index. It can be viewed as Adagrad, as this is the increasing-beta2 setting. The correspondence to Adagrad is not hard to show.

Setting A2 (MaxIter-dependent constant beta2): The analyzed algorithm with beta2 = 1-1/K where K is the pre-fixed iteration index is Adagrad: This is a fixed-beta2 setting, but the algorithm will stop at K iterations.

Setting A3 (constant beta2 convergence): [3] Adam with large enough constant beta2 converges to stationary points, under strong growth condition.

The three settings remind me of the settings in SGD (for convex case, for simplicity):

Setting S1 (diminshing stepsize convergence): SGD with diminishing stepsize eta = 1/sqrt{k} converges to an error 0.
The two settings are somewhat "equivalent" to each other.

Setting S2 (MaxIter-dependent stepsize): SGD with constant stepsize eta = 1/sqrt{K} converges to an error g(K);

Setting S3 (constant stepsize convergence): SGD with constant stepsize converges to error 0 under strong growth condition.

I know that some researchers like to quote S1 for SGD, and some like to quote S2 for SGD.
I'd like to explain a bit my interpretations of the three settings of Adam, based on the analogy with the three settings of SGD:

1. In SGD, S2, the convergence to a non-zero error for MaxIter-dependent eta = 1/sqrt{K}, can be somehow "transferred to" S1, the asymptotic convergence of SGD with diminishing eta = 1/sqrt{k}.
2. In Adam, it might be the case that A2, the convergence to a non-zero error for MaxIter-dependent beta2 = 1 - 1/K, can be "transferred to" A1, the asymptotic convergence of Adam with beta2 = 1 - 1/k.
   This convergence is less surprising since people already know Adagrad converges.
3. S3, the convegence of Adam with beta2 = iteration-independent constant, is more like the result of S3 for SGD: it is a fundamentally different asymptotic convergence result from S1&S2.

Due to the impression of "equivalence" of S1 and S2, I thought Setting A1 and A2 are somewhat "transferrable", and claimed Setting A1 (in this paper) is essentially Adagrad (via the bridge of A2).

That being said, I did not spend time to show A1 and A2 would be "equivalent". I still think it is possible (based on reading the proof of Adam with 1-1/K, it does not seem as tricky as the one in [3]), but since I did not show the equivalence, I made the following modifications to the original review: i) the sentence "The analyzed algorithm with 1-1/K is essentially Adagrad" in the original review is changed to "The analyzed algorithm with 1-1/K might just be Adagrad (note that for beta2 = 1/1/k, the algorithm becomes Adagrad, but for beta2 = 1 -1/K, it requires more discussion)"; ii) "a variant of Adagrad" changed to "perhaps a variant of Adagrad".

I hope someone (maybe the authors, or other follow-up researchers) can clarify the relation between A1 and A2 for Adam. I'd be happy to see both positive or negative relations.

**Additional point: **

1. Even putting aside the discussion on beta2, the authors did not make a convincing argument of NOT changing the name to Adam-Norm, as mentioned in the previous comment.

2. The authors said in response "We will revise the terminology in the manuscript to ensure clarity and alignment with our analysis." ---I checked the revised version (the authors have chance to modify PDF), the name Adam has not been changed to Adam-norm.

We are grateful for your thorough review and comments. Thank you for your remarks about strengths of our paper.

Weaknesses

The author's statement on the probability convergence results corresponding to different methods is not clear enough, even though these results are similar.

Thank you for this comment. If we understood the question correctly, we are talking about Theorem 1. Due to space constraints, we decided to present our results in the main part as a unified theorem (Theorem 1) that combines Theorems 5-8. If you are talking about Theorems 2-4, please clarify what is unclear.

The main theoretical results of this paper are based on the assumption of local smoothness of the optimization objective, even in convex cases, which is too strong.

We graciously disagree with this point. Indeed, one almost always makes the assumption of $L$-smoothness of the target function to provide convergence guarantees, e.g., see Nemirovski et al. (2009) [2.11], Ghadimi & Lan (2012)[1.2], and Li & Orabona (2020)[A] ,for, which is, in general, a stronger assumption than ours, because we only assume $L$-smoothness only in some set $Q$ instead of $\mathbb{R}^d$. However, we realize that you are most likely referring to assumptions such as $(L_0, L_1)$-smoothness, e.g., Zhang et al., 2019: https://arxiv.org/abs/1905.1188. We provide discussion about smoothness assumption on lines 133-136. However, please note that the main idea of our work is not to extend the class of problems under consideration in terms of smoothness, but to understand the behavior of adaptive state-of-the-art methods in the case of stochasticity with heavy tails.

Questions

In the introduction section, you cited some viewpoints from previous literature to illustrate that Adam and Clip-SGD have similar clipping effects for stochastic gradients. so, "it is natural to conjecture that clipping is not needed in Adam/AdaGrad" . Your theorem 1 emphasizes that Adam/AdaGrad without clipping do not have a high probability convergence complexity with polylogarithmic dependence on \delta even when the variance is bounded, rather than the divergence of Adam when the noise is heavy-tailed?

If we understood the question correctly, the answer to your question is yes. Theorem 1 shows that if Adam/AdaGrad methods converge with high probability, then there will be a factor of $\frac{1}{\delta}$ instead of $\log\left(\frac{1}{\delta}\right)$ in the bound on the number of iterations required for convergence. And in fact, this is enough to say that the clipped versions of Adam/AdaGrad do handle heavy-tailed noise in terms of convergence with high probability (since the $\log\left(\frac{1}{\delta}\right)$ factor occurs for the clipped versions) compared to Adam/AdaGrad without clipping.

In the discussion section of Theorem 1, you stated that “We also conjecture that for $\alpha<2$ one can show even worse dependence on ε and δ forAdam/AdaGrad…”. Have similar conjectures been mentioned in previous literatures, or can an informal analysis be provided?

Similar analysis arose, for example, in [1], except only that convergence is demonstrated by mathematical expectation. Moreover, to obtain similar results as in Theorems 5-8 for $\alpha < 2$, one can most likely use the same proof schemes but with modified noise - for example, unbounded discrete random variable with existing $\alpha$-moment. But, it is worth noting that this is not necessary if even for $\alpha =2$ there is, as we show, already a negative result.

References

[1] Zhang J, Karimireddy S P, Veit A, et al. Why are adaptive methods good for attention models?