CS Paper Radar

Coordinatewise Epsilon for Adam under Heavy-Tailed Noise

Jeonseong Kim, Chenglin Fan

cs.LG ·submitted 2026-11-06 15:26 UTC · v1
benchmarktheory

Abstract

Adam estimates second moments coordinatewise, but typically adds the same scalar $\varepsilon$ to every denominator. We study how this shared $\varepsilon$ affects convergence when noise and curvature vary across coordinates. Under coordinatewise finite-$p$ noise moments, $p\in(1,2]$, choosing $\varepsilon_i$ from the noise and curvature bounds for each coordinate attains the heavy-tailed $\ell_1$-stationarity benchmark $O(T^{-\frac{p-1}{3p-2}})$, matching the known optimal time exponent for smooth nonconvex stochastic optimization. For $1<p<2$, Adam with a shared $\varepsilon_t$ admits a lower bound of order $Ω(T^{-\frac{p-1}{2p}})$. This lower bound holds for every predictable scalar choice of $η_t$, $β_{1,t}$, $β_{2,t}$, and $\varepsilon_t$, precluding a dimension-uniform benchmark rate for this class.

Comment
32 pages

Closest papers

Nearest neighbours by meaning across the whole index.

On the Convergence of Vanilla Adam under Heavy-Tailed Noise and Index Sampling

cs.LG ·2026-11-02 ·Kanata Oowada, Hideaki Iiduka
similarity 0.70
Abstract

Understanding how stochastic gradient noise affects the convergence of Adam is an important problem in stochastic optimization, particularly when the noise exhibits heavy-tailed behavior. In this paper, we investigate the convergence of vanilla Adam in both the expected risk and the empirical risk minimization, focusing on the effects of heavy-tailed noise and its relationship to index sampling. For the expected risk minimization, we establish convergence guarantees under Hölder smoothness and bounded $\mathfrak{p}$-th moment assumptions, allowing stochastic gradient noise with infinite variance. Our analysis provides explicit upper bounds on the expected squared gradient norm and shows that the iteration-dependent convergence term decays more slowly as $\mathfrak{p}$ decreases. For the empirical risk minimization, we establish asymptotic and non-asymptotic convergence guarantees and demonstrate that heavy-tailed population noise can deteriorate convergence bounds through dataset-dependent constants as the dataset size increases. Furthermore, under Lipschitz smoothness, we formulate multistage Adam with practical learning rate schedules and demonstrate that increasing batch sizes can reduce index-sampling noise and improve convergence guarantees and SFO complexity. Numerical experiments support our theoretical findings on the effects of heavy-tailed noise and the computational benefits of increasing batch sizes.

0.07

Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness

cs.LG math.OCstat.ML ·2026-09-11 ·Misbah Uz Zaman, Anirbit Mukherjee
hot direction similarity 0.67
Abstract · 46 pages, 2 figures

Classical convergence guarantees for stochastic gradient methods typically assume Lipschitz-smooth objectives and finite-variance gradient noise, both frequently violated in practice. In contrast, we study nonconvex stochastic optimization under the joint relaxation of these assumptions: objectives with $(L,s)$-Hölder continuous gradients, $s\in(0,1]$, and gradient noise satisfying only a bounded $α$-th moment condition for $α\in(1,2]$. We establish three convergence results. Firstly, that standard SGD converges at rate $O(T^{-s/(1+s)})$ whenever $α\ge1+s$, extending the classical nonconvex SGD rate to heavy-tailed noise and Hölder smoothness simultaneously. Secondly, we analyze $δ$-regularized gradient clipping ($δ$-GClip), a provable trainer of wide and deep nets, and establish a stationarity rate of $O(T^{-2s(α-1)/[(1+s)(2α-1)]})$ under the same condition. Thirdly, we analyze standard gradient clipping (G-Clip) and show that it recovers the above rate for $α\ge1+s$ while in the very heavy-tailed regime $α<1+s$, it has a convergence rate $O(T^{-2s(α-1)/[(α-1)+s(2α-1)]})$ --- the first convergence guarantee in this regime for any stochastic gradient based method.

0.25

Near-Optimal Last-Iterate Convergence of SGD in the Smooth Interpolation Regime

cs.LG ·2026-10-18 ·Matan Schliserman, Tomer Koren
theory similarity 0.66
Abstract

We study the last iterate of stochastic gradient descent (SGD) with a constant stepsize on smooth convex objectives in the low-noise and interpolation regimes, where the variance $σ_\star^2$ of the stochastic gradients at the optimum is small or zero. We establish that after $T$ steps of SGD on $β$-smooth convex losses with any constant stepsize $0<η<2/β$, the last iterate attains expected excess risk $\widetilde O\bigl(\tfrac{1}{η(2-βη)^3T}+\tfracη{(2-βη)^4}σ_\star^2\bigr)$, which gives the rate $\smash{\widetilde O(1/T)}$ for every constant stepsize in the interpolation regime ($σ_\star=0$), matching the $Ω(1/T)$ lower bound up to logarithmic factors and improving upon the $O(1/\sqrt T)$ rate of Attia et al. (2026) for $η=1/β$. Our analysis is based on a new technique, which compares the second moments of the stochastic gradients along the SGD trajectory across only logarithmically many time scales. For quadratic losses in the interpolation regime, an adaptation of this technique gives an $O(1/T)$ rate for every constant stepsize, extending the recent optimal rate for the randomized Kaczmarz method of Derezinski and Dong (2026) to stepsizes above the greedy stepsize with an arguably simpler proof.

0.12

The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise

cs.LG ·2026-10-24 ·Yuxing Peng, Zhiqing Tang, Weijia Jia
code/data similarity 0.64
Abstract · 44 pages, including appendices and references. Lean 4 proofs of Theorems 2, 4, and 8 and of the known-horizon bound of Theorem 1, and the sc…

We study the last iterate of clipped SGD, and of every rule that queries its current iterate and steps along the resulting stochastic gradient, when training is stopped at a data-dependent time, so that guarantees must hold at all times simultaneously. On smooth convex objectives under heavy-tailed noise with a bounded central $p$th moment, $1<p\le2$, we determine the optimal time-uniform rate of these rules. A clipped SGD schedule without horizon or confidence inputs attains $\tilde O(t^{-β_p})$ at all times, with $β_p=2(p-1)/(3p-1)$, also almost surely, and no such rule attains $\tilde O(t^{-r})$ for any $r>β_p$, even with adaptive step sizes and thresholds. This rate lies between the optimal rate $O(T^{-α_p})$ for a known horizon $T$, $α_p=(p-1)/p$, and the previous time-uniform rate $\tilde O(t^{-2(p-1)/(3p)})$ (Chezhegov et al., ICLR 2026); under finite variance, the exponents are $1/2$, $2/5$, and $1/3$. Their conjecture that a better schedule reaches the optimal rate thus holds with a known horizon (Liu; Jiang et al.) but fails without one. Querying gradients at the running average attains $\tilde O(t^{-α_p})$ at all times, whereas heavy-ball momentum with geometric forgetting and polynomially bounded steps cannot improve on $β_p$.

0.21

Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds

cs.LG stat.ML ·2026-09-24 ·Wei Biao Wu
theory similarity 0.64
Abstract

Uniform noise-moment bounds exclude stochastic gradients whose variability increases with the iterate. We study ordinary, single-sample stochastic gradient descent for smooth, lower-bounded, possibly nonconvex objectives under distance-dependent conditional moments. Under second moments alone, a direct descent--displacement argument yields $T^{-1/3}$ expected average squared-gradient stationarity with a horizon-dependent stepsize. An explicit oracle-complexity corollary matches the known smooth Blum--Gladyshev (BG-0) lower bound, including the $Lb_2Δ^3\varepsilon^{-6}$ and $LΔσ^2\varepsilon^{-4}$ stochastic terms, where $Δ$ is the initial objective gap and $σ^2+b_2\|x-x_1\|^2$ bounds the variance. Thus unchanged SGD attains the minimax stochastic complexity in this second-moment class. For $p>2$, predictable localization and a Hilbert-space Fuk--Nagaev inequality yield a high-probability bound separating logarithmic variance and polynomial rare-shock contributions. The localization radius is derived from the recursion: no bounded-iterate assumption, clipping, normalization, momentum, or increasing batch size is needed. We also give increasing-confidence rates, an objective-gap-growth refinement recovering root-$T$ stationarity, and stochastic $L^p$-Lipschitz examples. The broad BG-0 optimality statement is distinguished from the smaller mean-square-smooth class, in which additional oracle structure permits faster algorithms.

0.21

Weak-$L^α$ Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails

cs.LG math.OC ·2026-10-20 ·Alyona Nekrasova, Makar Sidorov, Savelii Chezhegov, Alexander Gasnikov, Margarita Preobrazhenskaia +2 more
similarity 0.64
Abstract

Gradient clipping is a key tool for obtaining high-probability convergence guarantees for stochastic first-order methods under heavy-tailed noise. Existing analyses typically assume a bounded central moment of order $α\in(1,2]$, which excludes distributions with tails of order $u^{-α}$ at the critical exponent. In this paper, we consider smooth convex optimization under affine heavy-tailed noise, whose scale may grow with the gradient norm. We derive high-probability convergence guarantees for clipped SGD (Clip-SGD) and its accelerated variant Clip-SSTM under a weak-$L^α$ tail condition, which is strictly weaker than the corresponding moment bound. For $1<α<2$, the clipping bounds have the same powers of the clipping level as in the moment case, and both methods attain the additive stochastic rate $K^{-(α-1)/α}$. The gradient-dependent noise contributes a faster-decaying term of order $K^{-2(α-1)/α}$, up to logarithmic factors. At $α=2$, we characterize the additional logarithmic factor on the Lorentz scale and establish its necessity for the additive error at fixed confidence. We also analyze Clip-SGD with prescribed clipping levels and derive finite-horizon guarantees for reaching a neighborhood determined by the clipping bias. For additive noise, matching lower bounds show that this neighborhood is unavoidable, up to constants and the natural error cap. Numerical experiments with Pareto noise illustrate the theoretical results.

0.25

A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise

cs.CC math.OCcs.LG ·2026-08-10 ·Jikai Jin
theory similarity 0.64
Abstract

We prove a sharp lower bound for smooth nonconvex stochastic optimization with uniformly bounded gradient noise. In the \(K=1\) fresh-sample model, every randomized adaptive algorithm requires $$Ω\left( \frac{ΔL}{ε^2} + \frac{ΔLσ^2}{ε^4} \right)$$ queries to find a point with expected gradient norm at most \(ε\). This matches the standard upper bound and, to the best of our knowledge, resolves the question raised by [Arjevani et al. 2023] of whether almost-surely bounded oracle error permits a better rate than bounded variance. The proof was independently generated with GPT-5.6 Sol in Codex's Ultra mode during a two-hour session. The human author supplied the prompt and was responsible only forchecking the proof and revising and polishing the manuscript.

0.38

Second-Moment Memory in Coordinatewise Adam

cs.LG ·2026-08-16 ·Jeonseong Kim
theory similarity 0.63
Abstract · 10 pages

Adam retains a moving average of past squared gradients in its denominator, but the optimization cost of this memory is not well understood. We show that second-moment memory can itself suppress progress toward the optimum even under finite-variance stochastic gradients. For a simple two-point oracle, the expected positive normalized update is $O(M_2^{-1/2})$ after an initialization transient, where $M_2=(1-β_2)^{-1}$ is the second-moment memory length. We convert this directional bound, under the stated memory and stepsize scaling, into an average-stationarity lower bound of the same order on a smooth convex problem with normalized gap, smoothness, and variance. Long second-moment memory can slow optimization even when the gradient noise has finite variance.

0.40