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

We thank the reviewer for the very positive evaluation of our paper and constructive feedback.

1:Analysis of Clip-Adam with $\beta_1 > 0$

A: We revisited our proof and generalized it to the case of $\beta_1 > 0$. The sketch of the proof with the key derivation is provided below. We promise to include the complete proof in the final version.

The main idea remains the same: we prove the descent lemma for the coordinate-wise approach as for the nonconvex case in scalar-wise form (Lemma C.3) and the rest of the proof follows the induction-based arguments (similarly to Theorem C.5). Applying smoothness and rewriting everything in the coordinate-wise form, we get an analog of formula (29) for Clip-AdaGradD and Clip-AdamD:

$f(x_{t+1}) - f(x_t) \leq \sum\limits_{i=1}^d\left[-\gamma \frac{\nabla_{t, i} m_{t,i}}{b_{t,i}} + \frac{L\gamma^2}{2}\frac{m_{t,i}^2}{b_{t,i}^2}\right].$

The next step is to derive an analog of formula (30) from page 26. We have:

$

-\nabla_{t,i} m_{t,i} &= -\beta_1 \nabla_{t,i} m_{t - 1,i} - (1 - \beta_1)\nabla_{t,i} g_{t,i} \\\\

&= -\beta_1 (\nabla_{t,i} - \nabla_{t-1,i}) m_{t - 1,i} -\beta_1 \nabla_{t-1,i} m_{t - 1,i} - (1 - \beta_1)\nabla_{t,i} g_{t,i} \\ &\leq \beta_1 |\nabla_{t,i} - \nabla_{t-1,i}| \cdot |m_{t - 1,i}| -\beta_1 \nabla_{t-1,i} m_{t - 1,i} - (1 - \beta_1)\nabla_{t,i}g_{t,i}.

$

Unrolling the recurrence and summing over $i$, we get

$-\sum\limits_{i=1}^d \frac{-\nabla_{t,i} m_{t,i}}{b_{t,i}} \leq -(1 - \beta_1)\sum\limits_{k=0}^t \beta_1^{t-k}\sum\limits_{i=1}^d\frac{\nabla_{k,i}g_{k,i}}{b_{t,i}} + \sum\limits_{k=0}^{t-1} \beta_1^{t-k} \sum\limits_{i=1}^d\frac{ |\nabla_{k+1,i} - \nabla_{k,i}| \cdot |m_{k,i}|}{b_{t,i}}.$

Applying Cauchy-Schwarz inequality to the last term in the right-hand side and then using $L$-smoothness, we obtain

$

\sum\limits_{k=0}^{t-1} \beta_1^{t-k} \sum\limits_{i=1}^d\frac{|\nabla_{k+1,i} - \nabla_{k,i}| \cdot |m_{k,i}|}{b_{t,i}} &\leq \sum\limits_{k=0}^{t-1} \beta_1^{t-k} \left(\sqrt{\sum\limits_{i=1}^d (\nabla_{k+1,i} - \nabla_{k,i})^2}\right)\left(\sqrt{\sum\limits_{i=1}^d\frac{m_{k,i}^2}{b_{t,i}^2}}\right) \\ &=\sum\limits_{k=0}^{t-1} \beta_1^{t-k} || \nabla f(x_{k+1}) - \nabla f(x_k)||\left(\sqrt{\sum\limits_{i=1}^d\frac{m_{k,i}^2}{b_{t,i}^2}}\right) \\ &\leq \sum\limits_{k=0}^{t-1} \beta_1^{t-k} L || x_{k+1} - x_k|| \left(\sqrt{\sum\limits_{i=1}^d\frac{m_{k,i}^2}{b_{t,i}^2}}\right) \\ &= L\gamma\sum\limits_{k=0}^{t-1} \beta_1^{t-k} \left(\sqrt{\sum\limits_{i=1}^d\frac{m_{k,i}^2}{b_{k,i}^2}}\right)\left(\sqrt{\sum\limits_{i=1}^d\frac{m_{k,i}^2}{b_{t,i}^2}}\right) \\ &\leq \frac{L\gamma}{c_m}\sum\limits_{k=0}^{t-1} \beta_1^{t-k} \sum\limits_{i=1}^d\frac{m_{k,i}^2}{b_{k,i}^2}.

$

Then, we plug this bound into the previous ones and get:

$f(x_{t+1}) - f(x_t) \leq -(1 - \beta_1)\gamma\sum\limits_{k=0}^t \beta_1^{t-k}\sum\limits_{i=1}^d\frac{\nabla_{k,i}g_{k,i}}{b_{t,i}} + \frac{L\gamma^2}{c_m}\sum\limits_{k=0}^{t} \beta_1^{t-k} \sum\limits_{i=1}^d\frac{m_{k,i}^2}{b_{k,i}^2}.$

Applying Lemma C.2 and summing over $t$, we derive the following bound:

$

(f(x_T) - f^\ast) - (f(x_0) - f^\ast) &\leq -(1 - \beta_1)\gamma\sum\limits_{t=0}^{T-1}\sum\limits_{k=0}^t \beta_1^{t-k}\sum\limits_{i=1}^d\frac{\nabla_{k,i}g_{k,i}}{b_{t,i}} \\\\

&+ \frac{L\gamma^2(1-\beta_1)}{c_m}\sum\limits_{t=0}^{T-1}\sum\limits_{k=0}^{t} \beta_1^{t-k} \sum\limits_{i=1}^d\sum\limits_{j=0}^k\beta_1^{k-j}\frac{g_{j,i}^2}{b_{k,i}^2}.

$

Then, similarly to the proof of Lemma C.3, we denote the coefficients in front of $\nabla_{r,i} g_{r,i}$ and $g_{r,i}^2$ as $-\gamma C_{r,i}$ and $A_{r,i}$ respectively. They have the following explicit formulas

$

-\gamma C_{r,i} &= -(1 - \beta_1)\gamma\sum\limits_{t=r}^{T-1}\frac{\beta_1^{t-r}}{b_{t,i}},\\
A_{r,i} &= \frac{L\gamma^2(1-\beta_1)}{c_m}\sum\limits_{t=r}^{T-1}\sum\limits_{k=r}^t\frac{\beta_1^{t - r}}{b_{k,i}^2}

$

After that, we follow exactly the same steps as in the proof of Theorem C.5 and get that for $\gamma \leq \frac{(1 - \beta_1)^2c_m^3 b_0}{2L}$ the following inequality holds:

$

\sum\limits_{t=0}^{T-1}\sum\limits_{i=1}^d \frac{\gamma C_{t,i}}{2}\nabla_{t,i}^2 &\leq (f(x_0) - f^\ast) - (f(x_T) - f^\ast) - \sum\limits_{t=0}^{T-1}\sum\limits_{i=1}^d (\gamma C_{t,i} - 2A_{t,i})\nabla_{t,i}\theta^u_{t,i} \\\\

&+ \sum\limits_{t=0}^{T-1} \sum\limits_{i=1}^d 2A_{t,i}(\theta^u_{t,i})^2 + \sum\limits_{t=0}^{T-1} \sum\limits_{i=1}^d \gamma C_{t,i}(\theta^b_{t,i})^2.

$

The rest of the proof follows very similar steps to the current proofs of Theorems C.5 and C.12 – from Theorem C.5 the same dependence on $1 - \beta_1$ follows, and from Theorem C.12 the dependence on $d$ is preserved.

2:In Theorem 3.3, $M \to \Delta$

A: Thank you for spotting the typo: should be $M$ in the upper bound.

We thank the reviewer for the constructive feedback that helped to improve our paper.

1:Time-dependent noise.

A: Thank you for spotting this. We will rewrite Assumption 1.1 to explicitly highlight that we allow time-dependent noise. Such assumptions are relatively standard for stochastic optimization with streaming oracle [1-3]. Moreover, many existing convergence upper bounds hold for time-varying noise as long as the corresponding moment bound is satisfied for each step [4-6]. We will add these clarifications to the final version of our paper.

2:Coordinate-wise methods & momentum.

A: In the abstract, we claim that we show that clipping fixes AdaGrad-Norm and Adam-Norm. In Section 1.1, we made a typo in line 65: it should be “without momentum” instead of “with momentum”. We also explicitly mention that Clip-AdaGradD and Clip-AdamD are analyzed without momentum. To address this limitation of our paper, we generalized our proofs for the methods with coordinate-wise stepsizes to the case of $\beta_1 > 0$ – please see our response to Reviewer GE8p. We promise to add the complete proof to the final version of our paper.

3:Lower bound & Assumption 1.4.

A: Our lower bounds can be extended to support Assumption 1.4, if we modify $f$ as follows:

$f(x) = \begin{cases}\frac{1}{2}x^2,& \text{if } |x| < \nu,\\\\ \nu\left(|x| - \frac{1}{2}\nu\right),& \text{if } \nu \leq |x| \leq D,\\ \nu\left(D - \frac{1}{2}\nu\right),& \text{if } |x| > D, \end{cases}$

where $D > |x_0| > \nu$. Then, the proofs remain the same, and the problem satisfies Assumption 1.4.

4:Lower bound & time-independent noise.

A: If we assume that the noise is i.i.d. for each step, e.g., the same as for $k = 0$ in formula (16), then for the provided example of function and oracle M-AdaGrad/Adam should also have inverse-power dependence on $\delta$ in their high-probability complextites – this is our conjecture. However, deriving the lower bounds for this case is technically more difficult because the explicit form of the iterates becomes more involved than in Lemma B.1 (due to the summation of the squared norms of stochastic gradients in the stepsize). We will discuss this more explicitly in the final version of the paper.

5: Why Assumption 1.4?

A: The main difficulty comes from the dependence of $b_t$ and $g_t$ in the methods without delayed stepsizes. The existing approaches typically use boundedness of the variance and the norm of the gradient (see Lemma 5.1 in [7]) or assume that the noise is sub-Gaussian [8] to tackle this issue. In the heavy-tailed noise regime, these assumptions do not hold. Therefore, we use Assumption 1.4, which is a relaxation of the assumption used in [9] (see also our discussion of Theorem 3.3 on page 7). More precisely, to decouple $b_t$ and $g_t$ in the analysis, we multiply the inequality above (67) by $b_t$. However, it eventually leads to the non-trivial weighted sum of function values: the first sum in the RHS of the first row on page 44. After small rearrangements, we get the term $\sum_{t=1}^T \left( \frac{b_t}{p_t} - \frac{b_{t-1}}{p_{t-1}} \right)(f(x_t) - f_\ast)$ that we estimate using Assumption 1.4. We are not aware of the alternative ways of analyzing versions of AdaGrad/Adam or closely related methods in the heavy-tailed noise regime.

6:On the hyper-parameters

A: For AdaGrad-Norm without clipping, similar results cannot be obtained with logarithmic dependence on $1/\delta$ due to Theorem 2.1. However, it is an interesting open question whether it is possible to show convergence for Clip-AdaGrad-Norm with a choice of hyper-parameters agnostic to $L,\sigma, \alpha$, and $R$, in the heavy-tailed noise regime. We leave this question for future work.

---

References:

[1] S. Ghadimi & G. Lan. Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization, II: Shrinking Procedures and Optimal Algorithms. SIOPT 2012

[2] N. J. A. Harvey et al. Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent. arXiv:1909.00843

[3] A. Sadiev et al. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. ICML 2023

[4] J. Zhang et al. Why are Adaptive Methods Good for Attention Models? NeurIPS 2020

[5] A. Cutcosky & H. Mehta. High-probability bounds for Non-Convex Stochastic Optimization with Heavy Tails. NeurIPS 2021

[6] T. D. Ngyen et al. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. NeurIPS 2023

[7] A. Défossez et al. A Simple Convergence Proof of Adam and Adagrad. TMLR 2022

[8] Z. Liu et al. High Probability Convergence of Stochastic Gradient Methods. ICML 2023

[9] S. Li & Y. Liu. High probability analysis for non-convex stochastic optimization with clipping. ECAI 2023

We thank the reviewer for the valuable feedback that helped improve our paper. The requested numerical experiments can be found here: https://anonymous.4open.science/r/Clip-Adam-Norm-and-Clip-AdaGrad-Norm-1E8A/ (folder "rebuttal").

1: Algorithm 1.

A: We will add "-norm" to method names in Algorithm 1. Section 1.3 provides coordinate-wise versions of AdaGrad/Adam.

2:Gap between experiments and theory.

A: We include coordinate-wise methods with $\beta_1 = 0$ in Appendix C.5 (end of Section 3). Our proofs now cover coordinate-wise stepsizes—see our response to Reviewer GE8p. In Section 2, our results hold in 1D, where coordinate-wise and norm/scalar versions coincide. Hence, the theory aligns well with quadratic problem experiments. The Clip-Adam experiment without delay, though not analyzed theoretically, complements our theory.

3:Why ALBERT?

A: Mosbach et al. (2020) motivate our choice. RoBERTa wasn't used with gradient clipping in their experiments. Due to computational constraints and the need for 100 runs per method for high-probability convergence, we used a smaller model (ALBERT) instead of BERT.

4:Small datasets.

A: We use two of three datasets from Mosbach et al. (2020). We can add results on larger datasets if the paper gets accepted.

5: Training loss.

A: New plots are available in the anonymized repository.

6: On Theorem 2.1.

A: Let us address your concerns on the example of AdaGrad with momentum (Theorem B.4). The same reasoning holds for other methods as well.

1. We focus on worst-case guarantees [1], estimating complexity for the worst possible problem given the method’s parameters. This allows a resisting oracle [2], where the problem depends on $\varepsilon$ and $\delta$. This is a classical approach.

2. We require $x_0 > \sqrt{2\varepsilon} + 3\gamma$. Since typically $\varepsilon, \gamma \ll 1$, this assumption is mild. The stepsizes in Theorems 3.1-3.3 do not contradict Theorem 2.1: the results are derived for different methods. For $R, \sigma, M, L, b_{-1} = O(1)$ and large $K$ in Theorem 3.3, Theorem B.4 applies.

3. The fact that AdaGrad/Adam lack logarithmic dependence on $1/\delta$ even for $\alpha = 2$ strengthens our results. Some works [3] label $\alpha = 2$ case as heavy-tailed. Our setting, where noise is zero except in the first iteration, reinforces our findings: a large first stochastic gradient drastically reduces stepsize.

4. The stochastic gradient noise is $\sigma \xi_k$, with $\mathbb{E}[\xi_0^2] = 1 \Longrightarrow \mathbb{E}[\sigma^2\xi_0^2] = \sigma^2$.

7: The noise in the quadratic experiment seems too large.

A: Figures 1, 3, and 4 show results for different $\gamma$. Methods with clipping consistently outperform those without. Additional experiments with lower noise (scaled by 100) and tuned stepsizes are in the anonymized repository.

8: Fine-tuning experiment?

A: Randomness stems from the seed that determines mini-batch sampling order.

9: Results from Kunstner et al. (2023)

A: We will discuss this paper in the final version. Their work shows Adam outperforming SGD even in full-batch settings -- this observation is unrelated to stochasticity. Our focus is on high-probability convergence of AdaGrad/Adam-based methods, showing that without clipping, they have poor high-probability complexities, similar to SGD. Thus, our results complement Kunstner et al. (2023) by highlighting the necessity of gradient clipping for high-probability convergence.

10:Scalar or coordinate-wise methods?

A: We analyze both scalar (norm) and coordinate-wise versions of AdaGrad/Adam, studying both in experiments.

11:Introduction.

A: We will rewrite the introduction for clarity on considered methods.

12:Definition of heavy-tailed noise.

A: The noise is heavy-tailed if it satisfies Assumption 1.1.

13:Discussion of Theorem 2.1.

A: We will expand the discussion, incorporating the points above.

14: Dependence of $K$ on $\varepsilon$ and $\delta$ in Theorems 3.1-3.3.

A: The complexity results are presented in a standard way for the optimization literature (e.g., see Theorem 2.4 from [4]). The hyperparameters also depend on $\varepsilon$ and $\delta$: even standard SGD with constant stepsize converges only to the neighborhood of the solution for strongly convex smooth problems, i.e., one has to choose the stepsize to be dependent on the target error. We also provide the rates in Appendix C (see Theorems C.5, C.7, C.9, C.12).

---

References:

[1] A. Nemirovsky & D. Yudin. Problem complexity and model efficiency in optimization. J. Wiley @ Sons, New York (1983)

[2] Y. Nesterov. Lectures on convex optimization. Springer (2018)

[3] E. Gorbunov et al. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. NeurIPS (2020)

[4] S. Ghadimi & G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization (2013)

Thank you for your time and positive feedback. We also thank you for your useful comments, which we have addressed below.

1:It’s not the specific settings but rather the scale that I’m concerned with. I believe the experiments can be much more comprehensive to claim a solid support of the theory results.

A: We agree that the scale of our experiments can be further improved, and we can provide additional numerical results for larger models and datasets. However, the main contribution of our paper is primarily theoretical. Therefore, we see our experimental results as complementary contributions extending theoretical findings.

2: The obvious weakness of this work is that the versions of Adam/AdaGrad are actually normed…

A: We point out that we also analyze coordinate-wise versions of AdaGrad and Adam (with $\beta_1 = 0$) in Appendix C.4, as explained in the very end of Section 3. Moreover, we generalized our proof to the case of $\beta_1 > 0$ (please, see our response to Reviewer GE8p). Unfortunately, due to the page limitations of the main part, we had to defer these results to the Appendix. If the paper gets accepted, we will use an additional page in the main part to discuss the results on coordinate-wise versions of AdaGrad and Adam with clipping in more detail. We also kindly ask you to check our response to Reviewer RQzs (comments 2 and 10).

3: I kind of received an impression that various versions of algorithms are analyzed not because they are all important but because they can be proved. It would be nice to see how the choice of conditions under which methods are analyzed is made, or why analyzing all of these would be worthwhile.

A: Thank you for mentioning this point of view. The main goal of this paper is to provide a comprehensive answer to the questions formulated on the second page, right before Section 1.1. In general, the answer could potentially depend on the choice of the convexity and the stepsizes. Therefore, we analyze both non-convex and convex problems and derive the results for the scalar (a.k.a. “-norm”) and coordinate-wise versions of AdaGrad and Adam with and without delayed stepsizes. We believe that the provided analysis is quite comprehensive and covers many different cases (though not all possible ones for the sake of having the paper of a reasonable length; see also our response to Reviewer RQzs, comment 10). That is, we believe that the main research questions formulated in the paper are adequately addressed, i.e., we show that standard AdaGrad and Adam (with and without delayed stepsizes) do not enjoy logarithmic dependence on $1/\delta$ in their high-probability complexities and clipping provably improves their high-probability convergence.

4:Numerical results for CLIP-Adam do not seem strong or much differentiated.

A: We believe that the main theoretical findings of this paper are properly illustrated and complemented by our numerical results. We kindly ask the reviewer to clarify the concern.