acceptodds
Under review as a conference paper at ICLR 2027

High-Probability Convergence of Clipped SGD under Heavy-Tailed Noise and -Smoothness

Abstract

Gradient clipping is widely used in language-model training to control heavy-tailed gradient noise and can improve convergence guarantees over stochastic gradient descent **SGD** under -smoothness. Under these joint conditions, a central challenge is to obtain high-probability guarantees without exponential dependence on , where bounds the initial distance to a minimizer. We resolve this challenge for convex objectives, establishing, to the best of our knowledge, the first such guarantees for standard **Clip-SGD**. We assume unbiased stochastic gradients with bounded central -th moment, . Our bounds have only polylogarithmic dependence on the inverse failure probability and recover known deterministic generalized-smoothness rates when the noise vanishes, as well as the standard high-probability rate under heavy-tailed noise in the classical -smooth setting. The convex rate is attained by a computable output that averages iterates whose sampled stochastic gradients are not clipped, requiring neither function values nor extra oracle calls. At constant confidence, we establish a matching lower bound for **Clip-SGD** with any fixed stepsize and clipping level, showing that our convex stochastic rate is optimal up to logarithmic factors in the iteration budget. Our upper-bound analysis uses a directional clipping-bias bound to absorb part of the bias into the progress generated by the clipped population gradient, avoiding an exponentially large local smoothness constant. We also obtain nonconvex high-probability guarantees that recover the noiseless rate, match the classical-smooth stochastic iteration rate when , and have no explicit dependence in the asymptotically dominant stochastic term.

Primary area:
optimization
Keywords:
stochastic optimization, gradient clipping, generalized smoothness, Clip-SGD, high-probability convergence, heavy-tailed noise

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_Uv4QOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies high-probability convergence of standard clipped SGD under heavy-tailed stochastic gradient noise and ((L_0,L_1))-smoothness. Its main contribution is a convex convergence guarantee that avoids exponential dependence on (L_1R_0), assuming unbiased gradients with a bounded central (\alpha)-th moment for (\alpha\in(1,2]). A directional clipping-bias bound allows part of the bias to be absorbed into the optimization progress. The paper also provides a computable output obtained by averaging iterates whose observed gradients are not clipped, and a lower bound matching the convex stochastic rate up to logarithmic factors for fixed-parameter Clip-SGD. An additional nonconvex analysis recovers known deterministic and classical-smooth iteration rates. Validation is entirely theoretical, through upper bounds, lower-bound constructions, and comparisons with existing guarantees; no numerical experiments are provided.

Critical strengths

1.The convex result addresses a meaningful gap for the standard algorithm. Existing guarantees under generalized smoothness either impose stronger noise assumptions, change the sampling scheme, or risk exponentially large constants when reduced to classical smoothness. Analyzing the same stochastic gradient for both clipping and updating under only a bounded central moment is a substantive extension. The directional bias bound explains how this difficulty can be handled without uniformly bounding the population gradient over the localization region.

2.The paper goes beyond an unobservable best-iterate bound. The gradient-based selection rule produces an implementable output without function evaluations or additional oracle calls. The complementary lower bound strengthens the contribution by showing that the stochastic dependence is nearly tight within the fixed-parameter Clip-SGD class, even when arbitrary transcript-based output rules are allowed.

Critical weaknesses

1.The optimality result has a restricted algorithmic scope. Theorem 3 establishes near-optimality for Clip-SGD with a fixed stepsize and clipping level, rather than for stochastic first-order optimization generally. It therefore does not establish whether the leading (L_1R_0) dependence is intrinsic to the oracle model or can be avoided by adaptive methods. The paper acknowledges this restriction, but it limits the broader significance of the optimality conclusion.

2.The practical implications of the prescribed tuning remain uncertain. The clipping threshold and stepsize depend on problem quantities including the noise moment parameters, smoothness constants, and an initial-distance bound. The computable output removes the need for function evaluations, but does not resolve access to these tuning quantities. Without a robustness analysis or numerical illustration, it is difficult to judge how informative these prescriptions are when only conservative estimates are available. This is a limitation of applicability rather than a reason to dismiss the theoretical contribution.

Questions for authors

1.Clarification: Can Theorem 2 be stated using conservative upper bounds on (L_0,L_1,R_0,\sigma)? What rate and iteration requirement result when these bounds substantially overestimate the actual quantities?

2.Clarification: Is selection by the observed clipping test essential to the guarantee, or is it primarily needed by the proof? Is there an example under the stated assumptions where averaging all iterates fails to achieve the same rate?

3.Clarification: In the nonconvex guarantee, at what iteration scale does the term without explicit (L_1) or confidence dependence dominate the other terms? An explicit crossover condition would help assess the finite-budget significance of this improvement.

1 comment

We thank the reviewer for the careful review and the constructive questions. We address the points raised by the reviewer below.

W1. Algorithmic scope of the optimality result.

We agree that Theorem 3 is a lower bound for Clip-SGD with a fixed stepsize and clipping level, not for all stochastic first-order methods, and that it does not decide whether the (L1R0)(α−1)/α(L_1R_0)^{(\alpha-1)/\alpha} factor is intrinsic to the oracle model. The purpose of Theorem 3 is to show that this factor is a worst-case limitation of fixed-parameter Clip-SGD, not an artifact of our analysis.

Theorem 3 holds for every fixed (γ,λ)(\gamma,\lambda), even when chosen with knowledge of L0L_0, L1L_1, R0R_0, σ\sigma, α\alpha, KK and δ\delta, and for every output computed from the observed iterates and stochastic gradients, including the last iterate and any average. Hence, under the conditions of Theorem 3 and up to logarithmic factors in KK, the factor cannot be removed for Clip-SGD with a constant stepsize and clipping level by a sharper analysis, a better tuning or a different output. This remains relevant even if a method with adaptive parameters were shown to avoid the factor: the factor would then be a limitation of fixed-parameter Clip-SGD that can be bypassed only by changing the algorithm. We believe this is useful to the community, as it separates the limitations of the method from those of its analysis. Designing an adaptive method that avoids the factor without introducing additional hyperparameters or other drawbacks that Clip-SGD does not have remains an open question.

W2 & Q1. Tuning with conservative estimates.

We thank the reviewer for this point. Please see our answer to Reviewer 1KFv (W1) for details. In short, yes: Theorem 2 holds with any upper bounds Lˉ0≥L0\bar L_0\ge L_0, Lˉ1≥L1\bar L_1\ge L_1, σˉ≥σ\bar\sigma\ge\sigma, any bound R0≥∥x0−x⋆∥R_0\ge\lVert x_0-x^\star\rVert, and any αˉ∈(1,α]\bar\alpha\in(1,\alpha], used both in the parameter choices and in the iteration condition. For fixed α\alpha, KK and δ\delta, if these bounds overestimate the true quantities by factors of at most κ≥1\kappa\ge1 and KK satisfies the corresponding iteration condition, the error bound grows by at most κ3\kappa^3 and the L1R0L_1R_0 part of the iteration requirement by at most κ2\kappa^2; a smaller αˉ\bar\alpha preserves the guarantee, with the slower stochastic rate K−(αˉ−1)/αˉK^{-(\bar\alpha-1)/\bar\alpha}. Our answer to Reviewer 6t1x (W2) describes how L0L_0 and L1L_1 can be estimated in practice.

Q2. Is selection by the observed clipping test essential?

Please see our answer to Reviewer xCzV (Q2) for details. In short, selection is needed in our analysis only for the iteration condition, not for the rate: with the parameters of Theorem 2, the uniform average of all iterates achieves the same rate if, in addition, K≥4096Mδ4K\ge4096M_\delta^4, where Mδ=max⁡(L1R0,log⁡(12/δ))M_\delta=\max(L_1R_0,\log(12/\delta)). We do not claim that this stronger condition is necessary.

Q3. Crossover in the nonconvex bound.

Up to the constant 470424704\sqrt2, Theorem 4 bounds the averaged gradient norm by the largest of four terms: T1=L0Δ0K,T2=cG0ℓδK,T3=((cG0ℓδ)α−1σαKα−1)12α−1,T4=((L0Δ0)α−1σαKα−1)13α−2,T_1=\sqrt{\tfrac{L_0\Delta_0}{K}},\quad T_2=\tfrac{cG_0\ell_\delta}{K},\quad T_3=\Big(\tfrac{(cG_0\ell_\delta)^{\alpha-1}\sigma^\alpha}{K^{\alpha-1}}\Big)^{\frac1{2\alpha-1}},\quad T_4=\Big(\tfrac{(L_0\Delta_0)^{\alpha-1}\sigma^\alpha}{K^{\alpha-1}}\Big)^{\frac1{3\alpha-2}},

where c=4/νc=4/\nu (ν≈0.567\nu\approx0.567), G0=L1Δ0+L0Δ0G_0=L_1\Delta_0+\sqrt{L_0\Delta_0} and ℓδ=log⁡(e/δ)\ell_\delta=\log(e/\delta). For large KK, the largest term is T4T_4, which has no explicit dependence on L1L_1 or δ\delta.

To see when this happens (assuming L0Δ0>0L_0\Delta_0>0 and σ>0\sigma>0), let z=σL0Δ0z=\frac{\sigma}{\sqrt{L_0\Delta_0}} and g=4ν(1+L1Δ0/L0)log⁡eδ,g=\frac4\nu\Big(1+L_1\sqrt{\Delta_0/L_0}\Big)\log\frac e\delta, so that zz measures the noise level and gg collects the dependence on L1L_1 and δ\delta. A direct computation shows that T4T_4 is the largest term exactly when K≥max⁡{z−2, g3α−2α−1zαα−1}.K\ge\max\Big\lbrace z^{-2},\ g^{\frac{3\alpha-2}{\alpha-1}}z^{\frac{\alpha}{\alpha-1}}\Big\rbrace.

The first condition means T4≥T1T_4\ge T_1, the second means T4≥T3T_4\ge T_3, and together they also give T4≥T2T_4\ge T_2. For α=2\alpha=2, the condition is simply K≥max⁡{z−2,g4z2}K\ge\max\lbrace z^{-2},g^4z^2\rbrace.

In words: L1L_1 and δ\delta only affect how large KK must be before this regime starts. After that, the bound is 47042T44704\sqrt{2}T_4, which has no explicit dependence on L1L_1 or δ\delta, although they still appear in the choice of the parameters.

Reviewer_6t1xOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper establishes high-probability guarantees under heavy-tailed gradient noise and (L0,L1)(L_0,L_1)-smoothness of the population loss.

Critical strengths

The paper shows that Clip-SGD achieves high-probability convergence under (L0,L1)(L_0,L_1)-smoothness and heavy tailed gradient noise without exponential dependence on L1R0L_1R_0.

The authors also show that the same convergence rate can be achieved by a computable output constructed solely from the stochastic gradients already queried by Clip-SGD.

The authors show that the rate is optimal up to logarithmic factors in the iteration budget for the fixed-parameter Clip-SGD.

Critical weaknesses

Despite these strengths, I have the following concerns. While I recognize the theoretical focus of the paper, the authors should also address the practical implementation of the proposed method. For example:

As shown in Tables 3 and 4, the step size and clipping threshold depend on R0,L0,R_0, L_0, and L1.L_1. Thus, achieving the stated bound requires prior knowledge of these parameters.

Could the authors provide guidance on how to estimate the parameters L0L_0 and L1L_1, which characterize the population loss? Such guidance would improve the practical applicability of the proposed algorithm.

Although the authors provide examples of functions that are (L0,L1)(L_0,L1)-smooth but not L-smoth, could they also examine loss functions arising in machine learning that have this property? Such examples would strengthen the practical relevance of the results and further motivate the analysis of this class of functions.

Could the authors provide a synthetic example demonstrating that the L-smooth assumption alone is insufficient for standard (L-smooth based) Clip-SGD to converge, whereas the proposed Clip-SGD converges under (L0,L1)(L_0,L_1) assumption?

Questions for authors

N/A.

4 comments
AuthorsOpenReview ↗

Rebuttal [1/3]

We thank the reviewer for the positive assessment of our results. Below, we address the points raised by the reviewer.

W1. Prior knowledge of R0R_0, L0L_0 and L1L_1.

We thank the reviewer for this point. Please see our answer to Reviewer 1KFv (W1).

W2. Estimating L0L_0 and L1L_1.

They can be estimated along a short run of the method, following [1, Appendix H.3]. For each step dk=xk+1−xkd_k=x_{k+1}-x_k (skipping steps with dk=0d_k=0), we evaluate the gradient at the points xk+τdkx_k+\tau d_k, τ∈{1/m,2/m,…,1}\tau\in\lbrace1/m,2/m,\dots,1\rbrace, for a large integer mm, and record L^k=max⁡τ∥∇f(xk+τdk)−∇f(xk)∥∥τdk∥,gk=max⁡τ∥∇f(xk+τdk)∥.\hat L_k=\max_{\tau}\frac{\lVert\nabla f(x_k+\tau d_k)-\nabla f(x_k)\rVert}{\lVert\tau d_k\rVert},\qquad g_k=\max_{\tau}\lVert\nabla f(x_k+\tau d_k)\rVert.

The number L^k\hat L_k measures how fast the gradient changes along the step, and gkg_k is the largest gradient norm we observed on the step. With stochastic gradients, each gradient is replaced by an average over a large batch, using the same batch for all points of the step.

Assumption 2 says that, between two points xx and yy, the gradient changes by at most (L0+L1sup⁡u∈[x,y]∥∇f(u)∥)∥x−y∥\big(L_0+L_1\sup_{u\in[x,y]}\lVert\nabla f(u)\rVert\big)\lVert x-y\rVert. With exact gradients and large mm, gkg_k is close to the largest gradient norm on the step, so L^k≤L0+L1gk\hat L_k\le L_0+L_1g_k approximately. Hence, if we plot the points (gk,L^k)(g_k,\hat L_k), as in [1, Figure 1], they lie approximately below the line g↦L0+L1gg\mapsto L_0+L_1g, whose slope is L1L_1 and whose intercept is L0L_0.

We first fit a line a+bga+bg to the points by least squares and take its slope, L1=max⁡{b,0}L_1=\max\lbrace b,0\rbrace. Some points lie above this line, so we move it up just enough to be above all of them, which gives L0=max⁡{0,max⁡k(L^k−L1gk)}L_0=\max\lbrace0,\max_k(\hat L_k-L_1g_k)\rbrace.

This has been done for modern models: [2] splits the parameters into blocks, one per network layer, computes such estimates for each block while training NanoGPT-124M and a CNN, and fits (L0,L1)(L_0,L_1) by least squares with an extra penalty when the line is below a point [2, Appendix E.2]. The stepsizes obtained from these estimates are close to values found by hyperparameter tuning in earlier work [2, Sections 2.2 and 5.1].

These are estimates for practical tuning. They come from a finite set of points, so they do not prove that Assumption 2 holds everywhere, while our guarantees require valid upper bounds. Multiplying the estimates by a safety factor makes the choice more conservative but does not certify the bounds. When the chosen bounds are valid, overestimating them costs only the polynomial factor discussed in our answer to Reviewer 1KFv (W1).

[1] J. Zhang, T. He, S. Sra, and A. Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. ICLR 2020.

[2] A. Riabinin, E. Shulgin, K. Gruntkowska, and P. Richtárik. Gluon: Making Muon & Scion great again! (Bridging theory and practice of LMO-based optimizers for LLMs). arXiv:2505.13416, 2025.

AuthorsOpenReview ↗

Rebuttal [2/3]

W3. Machine-learning losses that are (L0,L1)(L_0,L_1)-smooth but not LL-smooth.

We first note that (L0,L1)(L_0,L_1)-smoothness is informative even when ff is also LL-smooth. In that case, LL must bound the local smoothness everywhere in the region of interest, including where the gradient is largest, so it can be much larger than L0L_0: on a ball of radius R0R_0 around a minimizer, it can scale as L0eL1R0L_0e^{L_1R_0}. Fixed-step gradient descent tuned with LL uses a stepsize of order 1/L1/L throughout the run, even where the local smoothness is close to L0L_0, and can therefore be very slow, whereas methods that adapt to the gradient norm, such as clipping, exploit the smaller local smoothness; W4 gives a numerical example.

Losses poorly described by LL-smoothness.

  • Language models. In experiments on training LSTM language models, [1] observed that the local smoothness grows with the gradient norm and is strongly correlated with it [1, Figure 1]. A single constant LL must cover the largest observed local smoothness and can therefore substantially overestimate it at many other iterates. The bound L0+L1∥∇f(x)∥L_0+L_1\lVert\nabla f(x)\rVert captures this behavior: it allows the local smoothness to grow with the gradient norm.

Losses that are (L0,L1)(L_0,L_1)-smooth but not LL-smooth.

  • Poisson regression. Given data zi∈Rdz_i\in\mathbb R^d and observed counts yi∈{0,1,2,… }y_i\in\lbrace0,1,2,\dots\rbrace, Poisson regression minimizes f(x,c)=1n∑i=1n(ec+zi⊤x−yi(c+zi⊤x))f(x,c)=\frac1n\sum_{i=1}^n\Big(e^{c+z_i^\top x}-y_i(c+z_i^\top x)\Big) over x∈Rdx\in\mathbb R^d and c∈Rc\in\mathbb R. This function is convex but not globally LL-smooth, since ∂2f/∂c2=1n∑iec+zi⊤x→∞\partial^2f/\partial c^2=\frac1n\sum_ie^{c+z_i^\top x}\to\infty as c→∞c\to\infty. It is (L0,L1)(L_0,L_1)-smooth with L0=AyˉL_0=A\bar y and L1=AL_1=A, where A=1+max⁡i∥zi∥2A=1+\max_i\lVert z_i\rVert^2 and yˉ=1n∑iyi\bar y=\frac1n\sum_iy_i [3, Proposition A.1].
  • Phase retrieval. Its objective is a quartic polynomial, hence not LL-smooth (see [4, Section 3, Example 1]). It satisfies the generalized smoothness condition of [4] with exponent 2/32/3 (see [4, Proposition 3.3]), which implies (L0,L1)(L_0,L_1)-smoothness since t2/3≤1+tt^{2/3}\le1+t.

[3] R. Okazaki, S. Yagishita, and H. Hino. Adaptive normalized gradient method for (L0,L1)(L_0,L_1)-smooth problems: Estimating problem parameters as a region. arXiv:2610.27681, 2026.

[4] Z. Chen, Y. Zhou, Y. Liang, and Z. Lu. Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization. ICML 2023.

AuthorsOpenReview ↗

Rebuttal [3/3]

W4. A synthetic example.

To isolate the effect of the smoothness assumption, we use the noiseless case σ=0\sigma=0, where Clip-SGD becomes Clip-GD. We run Clip-GD with two parameter choices, both taken directly from theory, with no tuning:

  • the parameters of the standard analysis for convex LL-smooth problems [5, Theorem 3.1, Case 3];
  • the parameters of our Theorem 2.

Problem. For r>0r>0, let f(x)=ex−x−1for x≤r,f(x)=e^{x}-x-1\quad\text{for } x\le r,

f(x)=er−r−1+(er−1)(x−r)+12er(x−r)2for x>r.f(x)=e^{r}-r-1+\big(e^{r}-1\big)(x-r)+\tfrac{1}{2}e^{r}(x-r)^2\quad\text{for } x>r.

For x>rx>r, we replace ex−x−1e^{x}-x-1 by its second-order Taylor expansion at rr, so f′′(x)=min⁡{ex,er}f''(x)=\min\lbrace e^{x},e^{r}\rbrace. Therefore:

  • ff is convex and LL-smooth with L=erL=e^{r}, which is huge for large rr. This is also its smoothness constant on the ball around x⋆x^\star used in [5, Theorem 3.1].
  • ff is (1,1)(1,1)-smooth: for x≤rx\le r, f′′(x)=ex=1+f′(x)≤1+∣f′(x)∣f''(x)=e^{x}=1+f'(x)\le1+|f'(x)|; for x>rx>r, f′′(x)=er≤1+f′(x)f''(x)=e^{r}\le1+f'(x), since f′(x)≥er−1f'(x)\ge e^{r}-1.
  • f≥0f\ge0 and f(0)=0f(0)=0, so x⋆=0x^\star=0 and f⋆=0f^\star=0.

We start at x0=rx_0=r (so R0=rR_0=r), take r∈{10,20,30,40}r\in\lbrace10,20,30,40\rbrace and δ=0.01\delta=0.01, and run K=3⋅106K=3\cdot10^{6} iterations. This KK satisfies the iteration condition of Theorem 2 for every rr.

Parameters.

  • [5, Theorem 3.1, Case 3]: the stepsize must satisfy γ≤min⁡{1/(80LA),γσ}\gamma\le\min\lbrace1/(80LA),\gamma_\sigma\rbrace, where A=log⁡(4(K+1)/δ)≈20.9A=\log(4(K+1)/\delta)\approx20.9 and γσ\gamma_\sigma is proportional to 1/σ1/\sigma, and the clipping level is λ=R0/(40γA)\lambda=R_0/(40\gamma A). For σ=0\sigma=0, γσ\gamma_\sigma is infinite, so we take the largest allowed stepsize, γ=1/(80LA)≈6⋅10−4e−r\gamma=1/(80LA)\approx6\cdot10^{-4}e^{-r}. Then λ=2LR0\lambda=2LR_0, which is larger than every gradient along the run, since ∣f′(xk)∣≤er−1|f'(x_k)|\le e^{r}-1. So clipping never happens, and the method is just gradient descent with a very small stepsize. Its output is xˉK=1K+1∑k=0Kxk\bar x_K=\frac{1}{K+1}\sum_{k=0}^{K}x_k.
  • Our Theorem 2 with (L0,L1)=(1,1)(L_0,L_1)=(1,1): for σ=0\sigma=0, λ=L0R0/M=1\lambda=L_0R_0/M=1, since here M=max⁡{L1R0,log⁡(12/δ)}=R0M=\max\lbrace L_1R_0,\log(12/\delta)\rbrace=R_0, and γ=ν/16≈0.035\gamma=\nu/16\approx0.035. Its output x^K\widehat x_K is the average of the iterates with ∣f′(xk)∣≤λ|f'(x_k)|\le\lambda.

Results. The table shows f−f⋆f-f^\star at the starting point, at the last iterate xKx_K, and at the output of each method.

rrf(x0)f(x_0)[5, Thm. 3.1]: last[5, Thm. 3.1]: xˉK\bar x_KTheorem 2: lastTheorem 2: x^K\widehat x_K
102.2⋅1042.2\cdot10^{4}9.29.22929<10−15<10^{-15}1.4⋅10−111.4\cdot10^{-11}
204.9⋅1084.9\cdot10^{8}2.7⋅1052.7\cdot10^{5}7.3⋅1057.3\cdot10^{5}<10−15<10^{-15}1.5⋅10−111.5\cdot10^{-11}
301.1⋅10131.1\cdot10^{13}6.0⋅1096.0\cdot10^{9}1.6⋅10101.6\cdot10^{10}<10−15<10^{-15}1.5⋅10−111.5\cdot10^{-11}
402.4⋅10172.4\cdot10^{17}1.3⋅10141.3\cdot10^{14}3.6⋅10143.6\cdot10^{14}<10−15<10^{-15}1.5⋅10−111.5\cdot10^{-11}

With the parameters of [5, Theorem 3.1], the error stays large: after 3⋅1063\cdot10^{6} iterations, it is still above f(x0)/104f(x_0)/10^{4}, where f(x0)=er−r−1f(x_0)=e^{r}-r-1 grows exponentially with rr. With the parameters of Theorem 2, the error is below 10−1510^{-15} at the last iterate and below 2⋅10−112\cdot10^{-11} at x^K\widehat x_K, for every rr. The theoretical bounds show the same gap: for r=40r=40, the bound of [5, Theorem 3.1], 2R02/(γ(K+1))2R_0^2/(\gamma(K+1)), is 4.2⋅10174.2\cdot10^{17}, larger than f(x0)f(x_0), while the bound of Theorem 2 is 0.120.12.

Why. The stepsize of [5, Theorem 3.1] must be smaller than 1/L=e−r1/L=e^{-r} everywhere, even near x⋆x^\star, where the curvature is only about 11. The parameters of Theorem 2 (γ≈0.035\gamma\approx0.035 and λ=1\lambda=1) do not depend on rr: clipping shortens the steps only where the gradient is large.

[5] A. Sadiev, M. Danilova, E. Gorbunov, et al. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. ICML 2023.

Thank you for the responses, much appreciated, I will maintain the score.

Reviewer_xCzVOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the high-probability convergence of standard clip-SGD for a (L0,L1)(L_0,L_1) generalized smooth convex objectives under heavy-tailed gradient noise. The authors' main contribution is to obtain a high-probability upper bound without exponential dependence on L1R0L_1R_0 through a tighter analysis, where R0R_0 is bounded to the initial distance to a certain minimizer.

Critical strengths
  1. The paper is well written, especically for the proof overview.

  2. The authors provide a lower bound to demonstrate the tightness of the upper bound, particularly the dependency on L1R0L_1R_0.

  3. The key ingredients for the proof of Theorem 1 is interesting. Instead of decomposing the overall bias gt−∇f(xt)g_t - \nabla f(x_t) into biased and unbiased components as previously done, the authors analyze the bias between the clipped population gradient and the population gradient, then get a novel inequality, which is represented in Lemma 9. The proof eliminates the need that requires a uniform bound on the local region ∥∇f(x)∥\|\nabla f(x)\|, which in previous literature showed exponential growth in L1R0L_1R_0.

Critical weaknesses
  1. Comparing the upper and lower bounds provided by the authors, the lower bound has an additional denominator term log⁡(eK)\log(eK), which indicates that there is room for improvement in at least one of the upper or lower bounds.

  2. The hard instance that the authors rely on in the lower bound proof is (1,L1)(1,L_1)-smooth, which makes the given lower bound unable to recognize the dependence on the smoothness parameter L0L_0.

  3. Neither the best-iterate output corresponding to Theorem 1 nor the average output of un-gradient clipped samples corresponding to Theorem 2 is consistent with the historical average output in most previous literature.

  4. Judging from the selection of algorithm parameters listed in Tables 3 and 4, the authors seem to have fixed the time horizon KK (γ\gamma and λ\lambda were not set to time-varying.). This should be explicitly stated in the theorems' formulation.

  5. To reach the desired bound, both Theorems 1 and 2 require fine-tuning γ\gamma and λ\lambda based on the tail parameter pp, which is usually unknown in practice.

  6. The article does not include any synthetic or real-world experiments, but given that it is a theoretical article, I personally think the lack of experiments is acceptable.

Questions for authors

Regarding the statement "for every fixed γ,λ>0\gamma,\lambda>0" in Theorem 3, which represents the lower bound result, I am not sure what "fixed" means here and whether this matches the γ,λ>0\gamma,\lambda>0 settings of Theorems 1 and 2.

  1. Could the author add a discussion on the high-probability upper bound of (1/K)∑k=1K(f(xk)−f⋆)(1/K)\sum_{k=1}^K (f(x_k)-f^\star), and clarify whether this upper bound is consistent with the upper bounds represented in Theorems 1 and 2?

  2. Could the authors offer some discussion and comparison of the results from recent related work [r1] (NIPS 2026)?

[r1] On the Last-Iterate Convergence of Clipped Gradient Methods, https://arxiv.org/abs/2610.21026.

3 comments
AuthorsOpenReview ↗

Rebuttal [1/3]

We thank the reviewer for the careful and detailed review and the constructive questions. We address the weaknesses first and then the questions.

W1. The log⁡(eK)\log(eK) gap between Theorems 2 and 3.

We agree, and our optimality claim is stated accordingly, up to logarithmic factors. Let Mδ=max⁡(L1R0,log⁡(12/δ))M_\delta=\max(L_1R_0,\log(12/\delta)) as in Table 1. Since max⁡{L1R0/log⁡(eK),log⁡(12/δ)}≥Mδ/log⁡(eK)\max\lbrace L_1R_0/\log(eK),\log(12/\delta)\rbrace\ge M_\delta/\log(eK), the stochastic terms of Theorems 2 and 3 differ by at most a factor log⁡(eK)(α−1)/α≤log⁡(eK)\log(eK)^{(\alpha-1)/\alpha}\le\sqrt{\log(eK)}, up to absolute constants. This factor affects only the L1R0L_1R_0 part; the dependence on log⁡(1/δ)\log(1/\delta) matches. For comparison, high-probability guarantees for clipped methods are commonly stated up to polylogarithmic factors in KK and 1/δ1/\delta, as in [1, 2] (the O~\tilde O rates in Table 1), whereas our upper bound itself contains no log⁡K\log K factor.

The purpose of Theorem 3 is to establish the necessity of the parameter dependence in the stochastic term of Theorem 2. In particular, under its stated conditions, the polynomial dependence (L1R0)(α−1)/α(L_1R_0)^{(\alpha-1)/\alpha} is necessary, up to logarithmic factors, for Clip-SGD with any fixed stepsize and clipping level. The current analysis establishes this while remaining simple, at the cost of the logarithmic gap quantified above.

W2. Extending Theorem 3 to general L0L_0.

We thank the reviewer for this point. The normalization L0=1L_0=1 in Theorem 3 is without loss of generality, and we have added Remark 1 after Theorem 3 to make this explicit. The argument is a rescaling: if f=L0hf=L_0h and the stochastic gradients of ff are L0L_0 times those of hh, then Clip-SGD on ff with (γ,λ)(\gamma,\lambda) and Clip-SGD on hh with (L0γ,λ/L0)(L_0\gamma,\lambda/L_0) produce the same iterates, since γclip(L0Hk,λ)=L0γclip(Hk,λ/L0)\gamma\mathrm{clip}(L_0H_k,\lambda)=L_0\gamma\mathrm{clip}(H_k,\lambda/L_0), where HkH_k is the stochastic gradient of hh at xkx_k. Consequently, the lower bound of Theorem 3 holds for every L0>0L_0>0 with the same right-hand side, provided its iteration condition holds with σ\sigma replaced by σ/L0\sigma/L_0. Thus L0L_0 enters only the iteration condition, consistent with the stochastic term of Theorem 2, which does not depend on L0L_0.

W3. Output rules and the historical average.

Please see our answer to your second question (Q2), where we discuss the historical average and our choice of output.

W4. Fixed horizon.

We thank the reviewer for this remark. We have added the choices of the stepsize γ\gamma and the clipping level λ\lambda to the statements of Theorems 1 and 2, making explicit that they are constant across iterations and depend on the horizon KK.

W5. Knowledge of the tail parameter.

We thank the reviewer for this point. Please see our answer to Reviewer 1KFv (W1), where we discuss the dependence of our parameter choices on α\alpha and the other problem parameters.

W6. Experiments.

We thank the reviewer for considering the absence of experiments acceptable for a theoretical paper. We have nevertheless added a synthetic example in our answer to Reviewer 6t1x (W4). On a function that is (1,1)(1,1)-smooth and LL-smooth with an exponentially large LL, it compares Clip-GD with the parameters of the standard LL-smooth analysis and Clip-GD with the parameters of our Theorem 2.

AuthorsOpenReview ↗

Rebuttal [2/3]

Q1. Meaning of "fixed" in Theorem 3.

Fixed means that γ\gamma and λ\lambda are constant across iterations and, together with the output rule, are chosen before the instance: they may depend on KK, δ\delta, L1L_1, R0R_0, σ\sigma and α\alpha. This covers the choices in Theorems 1 and 2, but not adaptive or time-varying stepsizes and clipping levels.

[1] O. Gaash, K. Y. Levy, and Y. Carmon. Convergence of clipped SGD on convex (L0,L1)(L_0,L_1)-smooth functions. NeurIPS 2025.

[2] A. Sadiev, M. Danilova, E. Gorbunov, et al. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. ICML 2023.

Q2. High-probability bound on 1K∑k(f(xk)−f⋆)\frac1K\sum_k(f(x_k)-f^\star) and the historical average.

The average of objective gaps cannot match Theorem 2 in general, for any method. The uniform average of the iterates, however, achieves the rate of Theorem 2 under a stronger iteration condition; in our analysis, selection serves only to obtain the weaker iteration condition of Theorem 2, not the rate.

Average of objective gaps. All terms of 1K∑k=0K−1(f(xk)−f⋆)\frac1K\sum_{k=0}^{K-1}(f(x_k)-f^\star) are nonnegative, so this average is at least its first term, Δ0/K\Delta_0/K, for every method and every choice of stepsizes and clipping levels. Under (L0,L1)(L_0,L_1)-smoothness, Δ0\Delta_0 is not controlled by L0R02L_0R_0^2. For example, f(x)=L0L12(eL1∣x∣−L1∣x∣−1)f(x)=\frac{L_0}{L_1^2}\big(e^{L_1|x|}-L_1|x|-1\big) on R\mathbb R is convex and (L0,L1)(L_0,L_1)-smooth, since f′′=L0+L1∣f′∣f''=L_0+L_1|f'|; with x0=R0x_0=R_0, it has Δ0=L0L12(eL1R0−L1R0−1)\Delta_0=\frac{L_0}{L_1^2}\big(e^{L_1R_0}-L_1R_0-1\big), which exceeds L0R02L_0R_0^2 by a factor of order eL1R0/(L1R0)2e^{L_1R_0}/(L_1R_0)^2. Hence, without noise (σ=0\sigma=0), where Theorem 2 gives O(L0R02/K)O(L_0R_0^2/K), this average exceeds that bound by the same factor, whatever the schedule.

Uniform average of the iterates. Let xˉK=1K∑k=0K−1xk\bar x_K=\frac1K\sum_{k=0}^{K-1}x_k and Mδ=max⁡(L1R0,log⁡(12/δ))M_\delta=\max(L_1R_0,\log(12/\delta)). With the stepsize and clipping level of Theorem 2, xˉK\bar x_K achieves the rate of Theorem 2 if K≥4096Mδ4K\ge4096M_\delta^4, in addition to the iteration condition of Theorem 2. The argument has three steps.

Step 1: few iterates have large gradients. On the localization event in the proof of Theorem 2 (Appendix C.2), ∥xk−x⋆∥≤2R0\lVert x_k-x^\star\rVert\le2R_0 for all k<Kk<K and ∑k=0K−1⟨qk,xk−x⋆⟩≤8R02/(5γ)\sum_{k=0}^{K-1}\langle q_k,x_k-x^\star\rangle\le 8R_0^2/(5\gamma), where qk=clip(∇f(xk),λ)q_k=\mathrm{clip}(\nabla f(x_k),\lambda); every term of this sum is nonnegative by convexity. Let C\mathcal C be the set of indices 0≤k<K0\le k<K such that ∥∇f(xk)∥≤λ\lVert\nabla f(x_k)\rVert\le\lambda. By Lemma 4, each index outside C\mathcal C contributes at least νλ2/[2(L0+L1λ)]\nu\lambda^2/[2(L_0+L_1\lambda)], so with the parameters of Theorem 2,

K−∣C∣≤2(L0+L1λ)νλ2⋅8R025γ≤5125ν2Mδ2.K-|\mathcal C|\le\frac{2(L_0+L_1\lambda)}{\nu\lambda^2}\cdot\frac{8R_0^2}{5\gamma}\le\frac{512}{5\nu^2}M_\delta^2 .

Thus only O(Mδ2)O(M_\delta^2) iterates have a population gradient above the threshold, and K≥4096Mδ4K\ge4096M_\delta^4 ensures ∣C∣≥K/2|\mathcal C|\ge K/2.

Step 2: the average over C\mathcal C is accurate. Let yK=∣C∣−1∑k∈Cxky_K=|\mathcal C|^{-1}\sum_{k\in\mathcal C}x_k, used only in the analysis. Since qk=∇f(xk)q_k=\nabla f(x_k) on C\mathcal C, convexity gives

f(yK)−f⋆≤1∣C∣∑k∈C(f(xk)−f⋆)≤8R025γ∣C∣≤16R025γK.f(y_K)-f^\star\le\frac1{|\mathcal C|}\sum_{k\in\mathcal C}\big(f(x_k)-f^\star\big)\le\frac{8R_0^2}{5\gamma|\mathcal C|}\le\frac{16R_0^2}{5\gamma K}.

Step 3: transfer to xˉK\bar x_K. By localization, DK:=∥xˉK−yK∥=∥1K∑k∉C(xk−yK)∥≤4R0(K−∣C∣)/K=O(R0Mδ2/K)D_K:=\lVert\bar x_K-y_K\rVert=\lVert\frac1K\sum_{k\notin\mathcal C}(x_k-y_K)\rVert\le4R_0(K-|\mathcal C|)/K=O(R_0M_\delta^2/K), and the condition K≥4096Mδ4K\ge4096M_\delta^4 ensures L1DK≤1/4L_1D_K\le1/4. Combining the gradient bound of Lemma 3 with (L0,L1)(L_0,L_1)-smoothness on the segment [yK,xˉK][y_K,\bar x_K] and Young's inequality yields

f(xˉK)−f⋆≤4(f(yK)−f⋆)+4L0DK2=O(R02γK+L0R02Mδ4K2).f(\bar x_K)-f^\star\le4\big(f(y_K)-f^\star\big)+4L_0D_K^2=O\Big(\frac{R_0^2}{\gamma K}+\frac{L_0R_0^2M_\delta^4}{K^2}\Big).

The condition K≥4096Mδ4K\ge4096M_\delta^4 makes the second term at most a constant multiple of L0R02/KL_0R_0^2/K, so substituting the parameter choices gives, with probability at least 1−δ1-\delta,

f(xˉK)−f⋆=O(max⁡{L0R02K, σR0(MδK)(α−1)/α}).f(\bar x_K)-f^\star=O\Big(\max\Big\lbrace\frac{L_0R_0^2}{K},\ \sigma R_0\Big(\frac{M_\delta}{K}\Big)^{(\alpha-1)/\alpha}\Big\rbrace\Big).

The quartic condition is sufficient for this argument; we do not claim that it is necessary.

Why we use the selected output. The selected output of Theorem 2 keeps the sharper transient while remaining fully computable: like the uniform average, it needs no additional oracle calls or function values, since the selection uses stochastic gradients already queried. Gaash et al. [1, Algorithm 1] use an analogous output, averaging iterates selected by their observed clipping test.

AuthorsOpenReview ↗

Rebuttal [3/3]

Q3. Comparison with [3].

We thank the reviewer for pointing out this recent work, which raises an interesting open question: whether high-probability last-iterate guarantees for Clip-SGD can be obtained under (L0,L1)(L_0,L_1)-smoothness and heavy-tailed noise. We have updated the related work in Section 2, added a detailed comparison in Appendix A, and mentioned this question in the Conclusion.

[3] proves high-probability last-iterate rates for Clip-SGD under heavy-tailed noise with bounded α\alpha-th moment, for convex and strongly star-convex objectives that are either Lipschitz or LL-smooth, using stepsize and clipping-level schedules that depend on the known horizon KK. It improves the earlier last-iterate result of [4] for convex LL-smooth objectives, which is horizon-free but has a slower stochastic rate, of order K−2(α−1)/(3α)K^{-2(\alpha-1)/(3\alpha)}. Our work is complementary:

  • Smoothness. In the smooth case, both works assume LL-smoothness, which corresponds to L1=0L_1=0 in our setting; [3] also treats Lipschitz objectives, which we do not consider. We address (L0,L1)(L_0,L_1)-smoothness with L1>0L_1>0, where the main difficulty is to avoid an exponential dependence on L1R0L_1R_0.
  • Rates for L1=0L_1=0. In the convex LL-smooth case under classical noise, the stochastic term of [3] is of order σD(log⁡(1/δ)/K)(α−1)/α\sigma D(\log(1/\delta)/K)^{(\alpha-1)/\alpha}, with D=∥x0−x⋆∥D=\lVert x_0-x^\star\rVert. Our Theorem 2 with L1=0L_1=0 gives the same order, σR0(log⁡(12/δ)/K)(α−1)/α\sigma R_0(\log(12/\delta)/K)^{(\alpha-1)/\alpha}, for an averaged output instead of the last iterate.
  • Output and parameters. [3] uses time-varying parameters for the last iterate, whereas we use a constant stepsize and clipping level with an averaged output, and complement it with a lower bound for this fixed-parameter method (Theorem 3).

[3] Z. Liu. On the last-iterate convergence of clipped gradient methods. arXiv:2610.21026, 2026.

[4] S. Chezhegov, D. A. Parletta, A. Paudice, and E. Gorbunov. High-probability bounds for the last iterate of clipped SGD. ICLR 2026.

Reviewer_1KFvOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper establishes high-probability guarantees for standard Clip-SGD under heavy-tailed noise and (L0,L1)(L_0,L_1)-smoothness. The convex rate avoids exponential dependence on L1R0L_1R_0 and is attained by a computable output. A lower bound shows that, under the stated iteration conditions, the convex stochastic rate is optimal up to logarithmic factors in the iteration budget for Clip-SGD with any fixed stepsize and clipping level. The paper also provides a convergence analysis for nonconvex objectives in Appendix.

Critical strengths
  1. The paper presents a solid theoretical analysis.
  2. The paper is also well written and well organized, with clearly stated assumptions and main results, and proof overviews that make the analysis easy to follow.
Critical weaknesses

My main concern is whether the theoretical results provide useful insights into practical language-model training.

  1. The practical implications of the improved convex guarantee could be better clarified. Although the paper specifies a theoretical choice of the clipping level λ\lambda, it remains unclear how the improved L1R0L_1R_0 dependence can inform the selection of the clipping level in practical training, particularly when the required problem parameters are unknown.

  2. The results are established in a general stochastic optimization framework under standard smoothness and noise assumptions. While the paper also provides nonconvex guarantees, their implications for training concrete models—such as even simplified fully connected neural networks or Transformers—remain unclear.

Questions for authors

I also have some questions.

  1. Could the authors clarify the respective roles of the clipping mechanism and the bounded central moment assumption (Assumption 3) in the L1R0L_1R_0 dependence of the convex stochastic rate? Specifically, for α=2\alpha=2, does this polynomial dependence remain unavoidable, up to logarithmic factors in KK, for fixed-parameter Clip-SGD under the sub-Gaussian condition in Eq. (2), with the same noise scale σ\sigma?

  2. Can the guarantee for the averaged gradient norm 1K∑k=0K−1∥∇f(xk)∥\frac{1}{K}\sum_{k=0}^{K-1}\Vert{}\nabla f(x_k)\Vert{} in Theorem 4 be converted into a high-probability bound on ∥∇f(xoutK)∥\Vert{}\nabla f(x_{\mathrm{out}}^K)\Vert{} for a computable output xoutKx_{\mathrm{out}}^K (analogous to x^K\hat{x}_K in Theorem 2), without degrading the convergence rate?

  3. It is difficult to assess the relative advantages of the guarantees from Table 1 alone, since they rely on different algorithm variants, noise assumptions, and sufficient iteration conditions. Drawing on Section 1.2 and Appendix C.3, could the authors include the algorithm variant, gradient oracle calls per iteration, and sufficient iteration condition for each row in Table 1, and clarify how these differences affect the comparison?

If the authors can address the weaknesses and my questions above, I will be happy to raise my score after also considering the other reviews during the rebuttal phase.

5 comments
AuthorsOpenReview ↗

Rebuttal [1/3]

We thank the reviewer for the constructive comments and for appreciating our theoretical analysis. We address each point below.

W1. Practical implications when parameters are unknown.

The choices of γ\gamma and λ\lambda in Theorems 1–2 use L0,L1,R0,σ,αL_0,L_1,R_0,\sigma,\alpha. This is standard: earlier high-probability analyses of clipped methods likewise set the stepsize and clipping level using bounds on smoothness, noise, and initial distance (e.g., [1] and [2]). Exact values are not needed. As in Section 1.1, R0R_0 denotes any valid upper bound on ∥x0−x⋆∥\lVert x_0-x^\star\rVert, so the exact initial distance is never required. For the remaining quantities, it suffices to use upper bounds Lˉ0≥L0\bar L_0\ge L_0, Lˉ1≥L1\bar L_1\ge L_1, σˉ≥σ\bar\sigma\ge\sigma and any moment exponent αˉ∈(1,α]\bar\alpha\in(1,\alpha]. With these values, Assumptions 2–3 still hold; for αˉ\bar\alpha, this follows from Jensen's inequality. Theorems 1–2 therefore apply with (Lˉ0,Lˉ1,σˉ,αˉ)(\bar L_0,\bar L_1,\bar\sigma,\bar\alpha) in place of (L0,L1,σ,α)(L_0,L_1,\sigma,\alpha), both in the parameter choices and in the sufficient iteration conditions.

The cost of conservative choices is polynomial. Fix α,K,δ\alpha,K,\delta, and suppose Lˉ0,Lˉ1,σˉ\bar L_0,\bar L_1,\bar\sigma and R0R_0 exceed L0,L1,σL_0,L_1,\sigma and ∥x0−x⋆∥\lVert x_0-x^\star\rVert, respectively, by factors of at most κ≥1\kappa\ge1. Then, provided KK satisfies the corresponding iteration condition, the error bound in Theorem 2 increases by at most κ3\kappa^3, and the L1R0L_1R_0 contribution to its iteration requirement by at most κ2\kappa^2. A smaller moment exponent αˉ\bar\alpha preserves the guarantee, with the slower stochastic rate K−(αˉ−1)/αˉK^{-(\bar\alpha-1)/\bar\alpha}. By comparison, a reduction to classical smoothness can introduce exponential dependence on L1R0L_1R_0 even with exact parameters.

Removing parameter knowledge entirely has a provable cost in closely related settings:

  • Convex, non-smooth. Suppose the initial distance to the optimum and a bound LL on the stochastic gradients, with E∥g∥2≤L2\mathbb E\lVert g\rVert^2\le L^2, are each known only up to a factor ρ\rho. After TT stochastic gradients, the error level that any method guarantees with probability 1−δ1-\delta is then, on some problem, at least of order min⁡(ρ,T/log⁡(1/δ))\min(\rho,\sqrt{T/\log(1/\delta)}) times the best level achievable when both quantities are known [3, Theorem 3]. In [4], a method is called tuning-free if, given only lower and upper bounds on the problem parameters, it matches optimally tuned SGD up to polylogarithmic factors. For convex Lipschitz problems on unbounded domains, no method is tuning-free, even with bounded noise [4, Theorem 3].
  • Convex, smooth. This is our setting with L1=0L_1=0. For convex LL-smooth problems on unbounded domains, no method is tuning-free, even with bounded noise [4, Theorem 2].
  • (L0,L1)(L_0,L_1)-smooth, nonconvex. Without any knowledge of L0L_0 or L1L_1, normalized SGD with momentum reaches an average expected gradient norm of order O~((eL12(Δ0+L0)+σ)/T1/4)\tilde O\big((e^{L_1^2}(\Delta_0+L_0)+\sigma)/T^{1/4}\big) under bounded variance [5, Theorem 2]. The dependence on TT is optimal up to logarithmic factors, but the constant is exponential in L12L_1^2; tuning the stepsize with L1L_1 removes it [5, Proposition 3]. Some exponential dependence on L1L_1 is also unavoidable for normalized momentum methods with stepsizes η/ta\eta/t^{a}, a≥1/2a\ge1/2, that do not use L1L_1, already in the deterministic setting [5, Theorem 6].
  • Heavy-tailed noise, LL-smooth, nonconvex. Under a bounded central α\alpha-th moment, mini-batch normalized SGD with stepsize and batch size depending only on TT needs O((Δ04+L4)/ε4+(σ/ε)2α/(α−1))O\big((\Delta_0^4+L^4)/\varepsilon^4+(\sigma/\varepsilon)^{2\alpha/(\alpha-1)}\big) samples to reach an average expected gradient norm ε\varepsilon [6, Proposition 1], and this is tight for that method with polynomial stepsizes and batch sizes [6, Theorem 2]. With tuned parameters, it needs only O((Δ0L/ε2)(1+(σ/ε)α/(α−1)))O\big((\Delta_0L/\varepsilon^2)(1+(\sigma/\varepsilon)^{\alpha/(\alpha-1)})\big) samples, which is optimal [6, Corollary 3].

Requiring valid bounds, at a polynomial cost for loose ones, is therefore a reasonable tradeoff. Empirical estimates can guide this choice but do not certify that the bounds are valid.

[1] O. Gaash, K. Y. Levy, and Y. Carmon. Convergence of clipped SGD on convex (L0,L1)(L_0,L_1)-smooth functions. NeurIPS 2025.

[2] A. Sadiev, M. Danilova, E. Gorbunov, et al. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. ICML 2023.

[3] Y. Carmon and O. Hinder. The price of adaptivity in stochastic convex optimization. COLT 2024 (full version: arXiv:2402.10898).

[4] A. Khaled and C. Jin. Tuning-free stochastic optimization. ICML 2024.

[5] F. Hübler, J. Yang, X. Li, and N. He. Parameter-agnostic optimization under relaxed smoothness. AISTATS 2024.

[6] F. Hübler, I. Fatkhullin, and N. He. From gradient clipping to normalization for heavy tailed SGD. AISTATS 2025.

AuthorsOpenReview ↗

Rebuttal [2/3]

W2. General framework and relevance to language-model training.

Our paper is primarily theoretical, and its assumptions are motivated by language-model training: heavy-tailed gradient noise was observed in BERT pre-training [7], and curvature growing with the gradient norm was observed when training LSTM language models [8]. Under these assumptions, the paper closes a gap in the theory of a fundamental method: high-probability guarantees for standard Clip-SGD without exponential dependence on L1R0L_1R_0, together with a nearly matching lower bound for its convex stochastic rate. We view these theoretical results as complementary to empirical studies.

Noise model and algorithm. The closest prior work [1] analyzes Clip-SGD under sub-Gaussian noise, a strong assumption under which large noise values are exponentially unlikely, and requires two independent samples per step; their experiments show no advantage of this double sampling for the same number of stochastic gradients, and they list convergence without it as future work [1, Sections 4 and 5]. We analyze the standard single-sample update under heavy-tailed noise, which has been observed in language-model training [7]. This setting is harder: a single clipping level must both control the noise and limit the steps where the curvature is large, which creates a tradeoff with generalized smoothness (see Q1).

Nonconvex objectives. The paper also gives a unified high-probability guarantee for nonconvex objectives satisfying our assumptions (Theorem 4, Appendix D). It bounds the average gradient norm along the Clip-SGD iterates, recovers the deterministic rate under (L0,L1)(L_0,L_1)-smoothness when σ=0\sigma=0, and recovers the rate known for LL-smooth objectives under heavy-tailed noise when L1=0L_1=0. For fixed problem parameters and confidence, with L0Δ0>0L_0\Delta_0>0 and σ>0\sigma>0, its asymptotically dominant term, ((L0Δ0)α−1σαKα−1)1/(3α−2),\left(\frac{(L_0\Delta_0)^{\alpha-1}\sigma^\alpha}{K^{\alpha-1}}\right)^{1/(3\alpha-2)}, has no explicit dependence on L1L_1. Since Theorem 4 controls an average over the iterates, we also added Corollary 3, which returns a single iterate with the same guarantee up to a constant factor (see Q2).

Scope. These observations motivate our assumptions, but do not establish that they hold for a particular fully connected network or Transformer.

[7] J. Zhang, S. P. Karimireddy, A. Veit, S. Kim, S. J. Reddi, S. Kumar, and S. Sra. Why are adaptive methods good for attention models? NeurIPS 2020.

[8] J. Zhang, T. He, S. Sra, and A. Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. ICLR 2020.

First part: Q1. Roles of clipping and Assumption 3 in the L1R0L_1R_0 dependence.

We thank the reviewer for this insightful question. It motivated us to develop a new analysis under sub-Gaussian noise, now in Appendix F of the revised paper.

The extra L1R0L_1R_0 factor comes from the combination of the noise assumption and generalized smoothness, through the clipping tradeoff: a single threshold must both control heavy-tailed noise and limit steps where curvature is large. Neither ingredient alone produces it: the factor vanishes when L1=0L_1=0, and under sub-Gaussian noise it leaves the rate. Two results for the same fixed-parameter Clip-SGD make this precise.

How clipping interacts with the noise. Clipping replaces the stochastic gradient GkG_k by the estimator clip(Gk,λ)\mathrm{clip}(G_k,\lambda), whose norm is at most λ\lambda. Its variance is therefore at most λ2\lambda^2, even when GkG_k has infinite variance, which Assumption 3 allows for α<2\alpha<2. The price is that this estimator is biased, with a bias bound that decreases as λ\lambda grows. Under (L0,L1)(L_0,L_1)-smoothness, λ\lambda also controls the step length where curvature is large, so a larger λ\lambda requires a smaller stepsize, γ≲1/(L0+L1λ)\gamma\lesssim1/(L_0+L_1\lambda).

Under Assumption 3, the factor is necessary. Assumption 3 bounds only a moment, so rare but very large noise values can occur at any iteration, and the tradeoff between bias and stepsize persists throughout the run. Balancing it gives the stochastic term σR0(Mδ/K)(α−1)/α\sigma R_0(M_\delta/K)^{(\alpha-1)/\alpha} of Theorem 2, with Mδ=max⁡(L1R0,log⁡(12/δ))M_\delta=\max(L_1R_0,\log(12/\delta)); the L1R0L_1R_0 part comes from this tradeoff and the log⁡(12/δ)\log(12/\delta) part from the confidence level. Under its stated conditions, Theorem 3 shows that no fixed stepsize and clipping level can improve this dependence, up to logarithmic factors in KK. Its noisy hard instances use an oracle that returns zero with probability 1−p1-p and the gradient scaled by 1/p1/p otherwise; this oracle satisfies Assumption 3 but is not sub-Gaussian at scale σ\sigma.

AuthorsOpenReview ↗

Rebuttal [3/3]

Second part: Q1 (continued). The sub-Gaussian case. Under sub-Gaussian noise (Eq. (2)) with the same σ\sigma, the factor disappears from the rate. Large noise values are then exponentially unlikely: on an event of probability at least 1−δ/21-\delta/2, all noise values are bounded, and on this event the run splits into two phases. While the gradient is large, the objective decreases at every step; afterwards, clipping is inactive, so the updates coincide with ordinary SGD updates. With parameters chosen for this regime, the same algorithm and the same output x^K\hat x_K as in Theorem 2 satisfy, with probability at least 1−δ1-\delta (Corollary 4),

f(x^K)−f⋆=O(L0R02K+σR0log⁡(2eK/δ)log⁡(2/δ)K).f(\hat x_K) - f^\star = O\left(\frac{L_0R_0^2}{K} + \sigma R_0\sqrt{\frac{\log(2eK/\delta)\log(2/\delta)}{K}}\right).

This matches Gaash et al. [1] up to logarithmic factors, with one oracle call per iteration instead of two. The price is a longer transient: L1R0L_1R_0 moves to the iteration requirement K≥(1+L1R0)2max⁡{2048,(1+log⁡K)/log⁡(2/δ)}K \ge (1+L_1R_0)^2\max\lbrace 2048, (1+\log K)/\log(2/\delta)\rbrace, which is quadratic up to logarithmic factors, as in [1]. Such a transient is not specific to noise: already in the deterministic case, (L0,L1)(L_0,L_1)-GD with smoothed clipping requires K=Ω(1+(L1R0)2)K=\Omega(1+(L_1R_0)^2) (Table 1, note (2)), and refined analyses replace (L1R0)2(L_1R_0)^2 by L1R0log⁡(e+L1Δ0/(L0R0))L_1R_0\log(e+L_1\Delta_0/(L_0R_0)), which is again of order (L1R0)2(L_1R_0)^2 when Δ0\Delta_0 is exponentially large in L1R0L_1R_0 (Appendix C.3). Under Assumption 3, Theorem 2 instead has a transient of the same refined form, L1R0log⁡(12eδ(1+KΔ0L0R02))L_1R_0\log\big(\tfrac{12e}{\delta}(1+\tfrac{K\Delta_0}{L_0R_0^2})\big), logarithmic in Δ0\Delta_0.

Q2. A computable output for Theorem 4.

Yes; see the new Corollary 3 (Appendix D.3). It turns the average-gradient guarantee of Theorem 4 into a guarantee for a single computable point, at the cost of only a logarithmic factor in the number of oracle calls. The idea is simple: by Theorem 4, at least half of the iterates satisfy ∥∇f(xk)∥≤2ε\lVert\nabla f(x_k)\rVert\le2\varepsilon, where ε\varepsilon is the bound of Theorem 4 with δ/3\delta/3 in place of δ\delta. We sample ⌈log⁡2(3/δ)⌉\lceil\log_2(3/\delta)\rceil iterates uniformly with replacement, estimate their gradient norms by a median of block averages of fresh stochastic gradients, and return the one with the smallest estimate. Then P(∥∇f(xoutK)∥≤4ε)≥1−δ,\mathbb P\left(\lVert\nabla f(x^K_{\mathrm{out}})\rVert \le 4\varepsilon\right) \ge 1-\delta,

using at most K(1+32log⁡(3e/δ))K(1+32\log(3e/\delta)) oracle calls in total and no function values.

Q3. Comparing the rows of Table 1.

Table 1 lists the noise assumption of each row (deterministic, sub-Gaussian, or bounded central α\alpha-th moment). We have added numbered notes giving, for each row, the method analyzed, the oracle calls per iteration, and the sufficient iteration condition. We also clarify that KK counts iterations: [1] uses 2K2K oracle calls, whereas standard Clip-SGD uses KK. The comparison is then as follows.

  • Sub-Gaussian noise. Standard Clip-SGD now matches [1] up to logarithmic factors (Corollary 4), with half the oracle calls and a comparable iteration condition, quadratic in L1R0L_1R_0 up to logarithmic factors.
  • Bounded central α\alpha-th moment (our main setting). The guarantee of [1] does not cover this setting. Our rate has the extra factor Mδ(α−1)/αM_\delta^{(\alpha-1)/\alpha}, with Mδ=max⁡{L1R0,log⁡(12/δ)}M_\delta=\max\lbrace L_1R_0,\log(12/\delta)\rbrace, which is necessary for fixed-parameter Clip-SGD up to logarithmic factors in KK (Theorem 3). In exchange, our iteration condition, K=Ω(log⁡2(12/δ)+L1R0log⁡(12eδ(1+KΔ0L0R02)))K = \Omega\big(\log^2(12/\delta) + L_1R_0\log\big(\tfrac{12e}{\delta}(1 + \tfrac{K\Delta_0}{L_0R_0^2})\big)\big), depends on the initial objective gap only logarithmically and can be much smaller than a uniformly quadratic condition in L1R0L_1R_0.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.