PaperlayerView exact revision on arXiv

Source-linked AI summary

Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothness

Alokendu Mazumder, Ayaan Mohd, Harshit Rawat, Arnab Roy, Mayank Baranwal, Punit Rathore

arXiv:2609.30276v1cs.LGcs.SYeess.SY

TL;DR

Under generalized smoothness and heavy-tailed noise, AdaGrad’s adaptive metric may reflect rare noise shocks rather than the objective’s directional geometry. The paper analyzes the original same-step coordinate-wise update and shows that clipping repairs this failure, with a finite-horizon high-probability guarantee and near-optimal complexity up to logarithmic factors.

  • Problem

    The paper asks whether unclipped AdaGrad preserves the right adaptive geometry under generalized smoothness and heavy-tailed noise, where curvature can vary with gradient scale.

    Source: §1 · pp. 2–3

  • Method

    The analysis uses gradient clipping and a deterministic telescoping argument to control the same-step coordinate-wise AdaGrad update under generalized smoothness.

    Source: §4 · p. 7

  • Results

    The original clipped same-step AdaGrad update has a finite-horizon Euclidean stationarity guarantee with polylogarithmic confidence dependence and ˜O(ε−2) complexity, matching the Ω(ε−2) lower bound up to logarithmic factors.

    Source: §5 · p. 11

  • Takeaways & Limitations

    Clipping repairs the demonstrated geometry-miscalibration failure and stabilizes the adaptive metric’s directional scale along the trajectory.

    Source: §1.1 · p. 3, §4 · p. 7

    The stochastic gradients may be unbounded because the gradient noise can be unbounded.

    Source: §1.2.1 · p. 5

Abstract

from arXiv · show

We analyze the original same-step coordinate-wise AdaGrad under generalized smoothness and heavy-tailed noise with bounded variance. In this setting, local curvature may grow sub-quadratically with the gradient norm, and stochastic gradients are assumed to have only bounded conditional second moments. We show that unclipped AdaGrad can become \emph{anisotropically miscalibrated}: under heavy-tailed noise, the adaptive denominator can learn the geometry of rare noise shocks rather than the local curvature of the objective, leading to a persistent directional distortion that blocks finite-horizon Euclidean progress. We then prove that clipping repairs this failure mode. Our main result is a finite-horizon high-probability guarantee for the original non-lagged AdaGrad update, yielding $\frac1T\sum_{t=0}^{T-1}\|\nabla f(x_t)\|^2=\mathcal{O}\left(\frac{d\big(\sqrt{\log T} + \log \frac{1}{\delta}\big)}{\sqrt{T}}\right),$ and hence $\widetilde{\mathcal O}(\varepsilon^{-2})$ complexity. This shows that, for AdaGrad under heavy-tailed noise, clipping is a structural stabilizer of the adaptive geometry rather than merely a robustness heuristic.

1 Introduction

Generalized smoothness makes curvature trajectory-dependent, while heavy-tailed noise can cause AdaGrad’s adaptive metric to reflect noise rather than objective geometry. The paper shows that unclipped AdaGrad can mislearn this geometry and that clipping repairs the failure.

1 Introduction

  • Generalized smoothness allows curvature to scale with gradient magnitude, making local trajectory geometry more relevant than a single global curvature bound.AdaGrad’s coordinate-wise accumulator can adapt to observed gradient magnitudes, but under heavy-tailed noise rare shocks may dominate particular coordinates.Source: §1 · pp. 2–3

1.1 Our Contributions

  • Unclipped AdaGrad can mislearn the objective geometry under anisotropic heavy-tailed noise, while clipping repairs this failure and enables high-probability guarantees.The paper’s lower-bound construction uses a single rare shock to distort the denominator in the wrong coordinate and keep average Euclidean stationarity bounded away from zero.Source: §1.1 · p. 3, §1 · p. 3
  • The paper proves a finite-horizon guarantee for clipped AdaGrad under sub-quadratic generalized smoothness and heavy-tailed noise with bounded conditional second moments.The resulting complexity is e O(ε−2) with polylogarithmic dependence on the failure probability.Source: §1.1 · p. 4
  • Explicitly constructible stepsize, clipping-level, and warm-start bounds make ε-target Euclidean stationarity attainable within a strict parameter regime.The authors describe this as a complete non-asymptotic guarantee.Source: §1.1 · p. 4
  • A deterministic telescoping argument separates the historical metric from the same-step correction, addressing the dependence between the current gradient and adaptive denominator.The same-step dependence is a central obstacle in analyzing the original non-lagged update.Source: §1.1 · p. 4

1.2 Preliminaries

  • The setup assumes a differentiable, closed objective bounded below, and stochastic gradients formed from the true gradient plus potentially unbounded noise.The noise is conditionally mean-zero with bounded conditional second moment.Source: §1.2 · p. 4, §1.2.1 · p. 5

1.2.1 Generalized Smoothness

  • For generalized smoothness, bounded gradients along the trajectory yield a local smoothness constant and local quadratic bounds that support the analysis.The paper obtains trajectory gradient bounds through function-value control; the generalized class includes the classical and affine-smoothness cases.Source: §1.2.1 · pp. 4–5

2 Anistropic Miscalibration and The Failure of AdaGrad

The section establishes a finite-horizon failure of AdaGrad driven by anisotropic miscalibration: heavy-tailed noise can leave its adaptive geometry mismatched to the objective and prevent Euclidean progress.

2 Anistropic Miscalibration and The Failure of AdaGrad

  • For every T ≥ 2 and noise scale σ > 0, the lower-bound construction uses a stochastic oracle satisfying Assumption 3.It initializes x0 = (2, 1) and runs AdaGrad with d = 2, h = 1, yinit = 0, and ϵ0 = 1.Source: §2 · p. 5, §A.1 · p. 18
  • A heavy-tailed oracle can make the gradient norm exceed 1 at every iterate before horizon T, giving a finite-horizon failure of AdaGrad.The proof sketch attributes this to a rare shock that permanently inflates one coordinate's adaptive metric, while subsequent noiseless updates leave that coordinate stalled.Source: §2 · pp. 5–6
  • A rare shock in the first coordinate makes its adaptive metric grow to Ω(T), while the second coordinate contracts, producing a directional mismatch.The proof sketch says the first coordinate remains above 7/8 and the gradient norm stays above 1 for all t < T.Source: §2 · p. 6
  • The resulting obstruction is an irreversible collapse of AdaGrad’s geometry, making clipping necessary to prevent rare shocks from poisoning the adaptive denominator.The paper distinguishes this from slower concentration and describes clipping as the mechanism that removes the obstruction.Source: §2 · pp. 5–6

3 Related Work

Prior work studies adaptive methods under classical and relaxed smoothness, as well as clipping under heavy-tailed noise. The section situates this paper among those convergence analyses.

3 Related Work

  • Table 1 summarizes existing high-probability convergence results for AdaGrad.Source: Table 1 · p. 6
  • Clipped AdaGrad under generalized smoothness has a reported ˜O(T −1/2) average-gradient-norm stationarity guarantee.The accompanying note says this result assumes a uniformly upper-bounded objective and gives rates for α = 2.Source: §3 · p. 6
  • Prior work analyzes AdaGrad and Adam under classical smoothness, with extensions to nonconvex convergence and variants such as AMSGrad, Yogi, Padam, and AdaBound.The literature also studies adaptive methods under relaxed curvature conditions.Source: §3 · p. 6
  • Generalized and relaxed smoothness work extends curvature assumptions and studies AdaGrad’s convergence and coordinate-wise adaptivity, alongside results for Adam.The cited work includes (L0, L1)-smoothness, sub-quadratic generalized smoothness, and parameter-agnostic and mirror-descent methods.Source: §3 · p. 7
  • Clipping has been studied as a stabilizer under non-uniform curvature and heavy-tailed noise, including with momentum or normalization.The section identifies Chezhegov et al. [2025] as showing that clipping repairs heavy-tailed-shock vulnerability in AdaGrad/Adam-Norm with polylogarithmic confidence dependence.Source: §3 · p. 7

4 New Upper Bounds

The section establishes a high-probability finite-horizon stationarity guarantee for clipped same-step AdaGrad under generalized smoothness and heavy-tailed noise. Its analysis localizes the trajectory, controls the same-step correction, and calibrates the clipping and warm-start parameters.

4.1 Pathwise Localization

  • The analysis localizes the trajectory to a level set with an effective quadratic upper model, where gradients are bounded and updates stay within the generalized-smoothness neighborhood.Clipping bounds each clipped gradient, while the warm start supplies a lower bound on the adaptive denominator.Source: §4.1 · p. 8
  • Isolating the same-step penalty as a deterministic term lets the authors telescope and bound it pathwise, supporting high-probability analysis of the original update.This addresses the dependence between the current clipped gradient and the denominator used in its update.Source: §4.1 · p. 9

4.2 Calibrating Parameters

  • The matched warm start yinit = C^2 and ε0 = C sets D = 2C, removing harmful C-dependence from the same-step correction.This resolves the calibration conflict; the clipping-residual term then motivates a cubic clipping scale.Source: §4.2 · p. 10
  • Under Assumptions 1, 2, and 3, Theorem 1 gives clipped same-step AdaGrad a finite-horizon Euclidean stationarity result: T = Õ(ε⁻²) for ∥∇f(x_t)∥² ≤ ε.For all t = 0, ..., T, f(x_t) − f⋆ ≤ 2Δ0.Source: §4.2 · p. 11
  • The parameter schedule is a proof calibration, not a practical tuning prescription; it exhibits a regime controlling the residual, correction, and Euclidean conversion terms together.The authors present it as a constructive witness that the original update can be stabilized in the stated setting.Source: §4.2 · p. 11

5 Discussion of the Results and Conclusion

The discussion positions the result as a high-probability Euclidean guarantee for the original same-step coordinate-wise AdaGrad update in a more demanding noise and smoothness regime than prior analyses. Its complexity matches the non-convex stochastic lower bound up to logarithmic factors.

5 Discussion of the Results and Conclusion

  • The clipped same-step AdaGrad complexity matches the Ω(ε^-2) information-theoretic lower bound for standard non-convex stochastic optimization up to logarithmic factors.The result resolves this rate for the original coordinate-wise same-step update in the high-probability heavy-tailed setting.Source: §5 · p. 11
  • Prior coordinate-wise AdaGrad bounds with sharper dimension dependence assume classical L-smoothness, almost-sure bounded gradients, and sub-Gaussian noise.Other cited results analyze delayed coordinate-wise updates or scalar/norm-based AdaGrad rather than the original same-step coordinate-wise update.Source: §5 · p. 12
  • Earlier high-probability complexities for unclipped Adam/AdaGrad-type methods either depend inversely on δ or require sub-Gaussian or bounded noise.The latter noise assumptions are stronger than bounded variance.Source: §5 · p. 12

A.1 Anisotropic Miscalibration and Failure of AdaGrad

The lower-bound construction shows that a rare noisy coordinate can inflate AdaGrad’s adaptive denominator while gradients remain nonstationary across the finite horizon. It therefore illustrates anisotropic miscalibration rather than merely a slower rate.

A.1 Anisotropic Miscalibration and Failure of AdaGrad

  • The example uses a two-dimensional initialization x0 = (2, 1) and the original non-lagged AdaGrad update with specified unit step size and zero initial accumulator.The stated setup also sets ε0 = 1.Source: §A.1 · pp. 18–19
  • The construction’s stated outcome is anisotropic denominator inflation, with a finite-horizon stationarity average bounded away from zero.The lower-bound argument identifies this as a failure of Euclidean progress.Source: §A.1 · pp. 21–22
  • A stochastic oracle can produce gradients with norm greater than 1 at every iterate from 1 through T − 1 on an event in the construction.The proposition considers every horizon T ≥ 2 and noise scale σ > 0.Source: §A.1 · pp. 18, 22

A.2 Proofs of Auxiliary Lemmas

The auxiliary-lemma section introduces a predictable level-set stopping time and bounds the gradients before that stopping time.

A.1 Anisotropic Miscalibration and Failure of AdaGrad

  • Definition 2 introduces a predictable level-set stopping time for the analysis.Its indicator 1{t < τ} is measurable with respect to the prior filtration.Source: §A.2 · p. 23
  • The stopping rule’s predictability is expressed through the prior-filtration measurability of 1{t < τ}.This is the stated measurability property of the stopping-time indicator.Source: §A.2 · p. 23
  • Before τ, the objective gap is at most F, which yields the gradient bound ∥∇f(xt)∥ ≤ G.The passage attributes this bound to Definition 2 and Lemma 2.Source: §A.2 · p. 23

A.2.1 Proof of Lemma 3

The proof establishes a one-step descent result for same-step AdaGrad and begins bounding the terms needed to sum that result.

A.2.1 Proof of Lemma 3

  • Lemma 8 gives a one-step descent result with a same-step correction for each t < τ.Source: §A.2.1 · p. 23
  • The proof substitutes the same-step AdaGrad update into the descent inequality.Source: §A.2.1 · p. 23
  • It decomposes the clipped stochastic gradient into its conditional mean and clipped-noise component.Source: §A.2.1 · p. 23
  • The next step is to sum the one-step inequality and bound each resulting term separately.Source: §A.2.1 · p. 23

A.2.2 Bounding

The proof bounds the clipping residual using the local gradient bound and the conditional second-moment bound on the noise.

A.2.2 Bounding

  • For t < τ, the conditional second moment of the stochastic gradient is at most V = G^2 + σ^2.Source: §A.2.2 · p. 23
  • The clipping residual satisfies ∥r_t∥ ≤ ∥g_t∥^2/C.Source: §A.2.2 · p. 23
  • Consequently, its conditional expected norm is at most V/C for t < τ.Source: §A.2.2 · p. 23

A.2.3 Bounding P

This subsection bounds the cumulative same-step correction pathwise using the clipped update and a coordinatewise telescoping sum.

A.2.3 Bounding P

  • Lemma 11 gives a deterministic bound on the cumulative same-step correction for every sample path.Source: §A.2.3 · p. 24
  • Before τ, the local gradient coordinates are bounded by G and clipping bounds each clipped-gradient coordinate by C.Source: §A.2.3 · p. 24
  • Summing the coordinatewise terms telescopes, yielding the stated cumulative correction bound.Source: §A.2.3 · p. 24

A.2.4 Bounding P

The proof controls denominator sums and martingale fluctuations before establishing a high-probability Euclidean stationarity guarantee and discussing the level-set choice.

A.2.4 Bounding P

  • The lagged harmonic bound controls sums involving the growing denominator, and the pathwise bound applies it coordinatewise.Source: §A.2.4 · p. 24

A.2.5 Bounding P

  • The stopped clipped-noise martingale has zero mean, and a Freedman tradeoff bounds its fluctuations with high probability.Source: §A.2.5 · p. 25

A.2.6 High probability upper bound on Dt

  • A high-probability bound on total stopped clipped-gradient energy is used to bound the denominator norm.Source: §A.2.6 · p. 26

A.2.7 Proof of Lemma 5

  • The summed descent inequality separates clipping-residual, generalized-smoothness, and same-step-correction terms.Source: §A.2.7 · p. 27

A.3 Proof of Theorem 1

  • With probability at least 1 − δ, clipped same-step AdaGrad has finite-horizon Euclidean stationarity and ˜O(ε^-2) complexity for fixed problem parameters.The proof also states a ˜O(T^-1/2) convergence rate.Source: §A.3 · pp. 27, 28, 31

A.3.1 Discussion on specific choice of F ◦= 2∆0

  • The level F◦ = 2∆0 is an analytic convenience; choosing a much larger level can inflate local-geometry constants, while a tighter level shrinks feasibility slack and forces a smaller step size.Source: §A.3.1 · p. 32
Loading 2609.30276v1…