AdaGrad under heavy-tailed noise: symmetry, asymmetry and damping

Yang, Hanyu

doi:10.5281/zenodo.23225828

AdaGrad under heavy-tailed noise: symmetry, asymmetry and damping

Symmetric heavy-tailed noise is easy for AdaGrad. Lopsided noise makes it climb uphill, and that makes Liu's slower rate the true worst case. Damping repairs it gradually.

DOI 10.5281/zenodo.23225828 · PDF · alphaXiv · illustrated post · source and figures · CC BY 4.0 · preprint, 8 Oct 2026 · ORCID 0009-0005-0419-4070

Liu (ICML 2026) proved that AdaGrad converges under heavy-tailed noise with a finite p-th moment; when the objective is only bounded below, his rate is vacuous for p ≤ 4/3, and asked whether the threshold 4/3 is real. It is real, and it is caused by asymmetry: with symmetric noise the rate is T^{−(p−1)/(2p)} for every p, while with general noise and small damping (3p−4)/(4p) is sharp for every step size.

Abstract

We ask how fast AdaGrad drives the average gradient norm to zero on smooth nonconvex problems when the stochastic gradient has only a finite p-th moment, 1 < p ≤ 2. With symmetric noise the rate is T^{−(p−1)/(2p)} for every p, and this is sharp at a fixed step size. With general noise and small damping, Liu's slower exponent (3p−4)/(4p) is sharp for every step size, and for p ≤ 4/3 no polynomial rate holds. The cause is a climb: asymmetric noise pushes AdaGrad uphill, and the height it gains pays for a long descent that heavy-tailed noise makes slow. Damping limits that height. For damping λ = σT^α and a fixed step size we find the exponent across the whole window: it grows linearly in α wherever it is positive, and becomes the symmetric one at α = (2−p)/p. The matching upper bounds come from Liu's own lemmas with the damping retained.

Results

Rate exponents r with R_T ≈ T^−r up to logarithms, at a fixed step size unless stated.

noise	damping λ = σT^α	rate exponent	where
symmetric	any fixed λ > 0	(p−1)/(2p)	Theorem 3.1
general	α ≤ (2−p)/(2p)	(3p−4)/(4p); none for p ≤ 4/3; every step size	Corollary 4.2
general	(2−p)/(2p) ≤ α ≤ (2−p)/p	(pα+2p−3)/(2p) where ≥ 0	Corollary 5.2(i)
general	(2−p)/p ≤ α ≤ 1/p	(p−1)/(2p)	Corollary 5.2(ii)

Rate exponent against the damping exponent alpha for p = 1.2, 1.5 and 1.8: each curve is flat, rises linearly, then stays at the symmetric exponent; for p = 1.2 the flat part is at zero. — Rate exponent under general noise at a fixed step size, against the damping exponent α, up to α = 1/p. Dots mark α = (2−p)/(2p) and α = (2−p)/p.

Why symmetry helps

AdaGrad divides by a quantity containing the current gradient, so an unbiased gradient need not give an unbiased step. If the noise is symmetric, the expected step still points downhill, however large the noise. Steps on which the noise dominates cannot pile up: each has probability at least 1/4 of multiplying λ²+v_t by 3/2, so their expected number is logarithmic.

Why asymmetry hurts

On a gentle slope the noise usually takes a small value that reverses the sign of the gradient. A rare, large value restores the mean, but AdaGrad cuts that step to length at most γ. In the paper's instance the rare value has probability 1/(4N) with N = ⌊T/2⌋, so with probability above 1/2 it never occurs.

Left: the observed gradient is -0.2 with probability 0.9 and 11.8 with probability 0.1, mean +1. Right: after dividing by sqrt(1+g^2) the steps are -0.196 and 0.996, mean -0.077. — A one-step toy example, not from the paper: update x − γh with h = g/√(v+g²), γ = 1, λ = 0, accumulated v = 1; true gradient 1, noise −1.2 with probability 0.9 and +10.8 with probability 0.1. The gradient is unbiased, but the expected move is +0.077: uphill.

The height gained pays for a long descent, on which symmetric Pareto noise grows the accumulator and slows every step. Balancing the climb against the descent gives exactly Liu's exponent (3p−4)/(4p).

Top: the objective f rises along a gentle slope to a crest, then falls steeply. Bottom: its derivative is minus kappa on the gentle part and epsilon on the steep part. — The hard instance, drawn for illustration. Starting at x₁, tilt noise drives the iterate up the gentle slope; left of b, symmetric Pareto noise stalls it on the steep part.

What it does not establish

Failure on a fixed problem: the worst-case instance is chosen after the algorithm parameters and may depend on the horizon. On bounded objectives Liu's Theorem 4.2 gives convergence.
A bound on the best iterate: the lower bounds are for the average gradient norm.
The rate after tuning the step size with the horizon for (2−p)/p < α ≤ 1/p: there the rates match for each fixed step size only.
The same penalty with one common noise law for the whole run: the hard oracle uses two noise laws and picks one by position. This is the open question of the paper.

The matching upper bound is Liu's own argument for his Lemma A.2, run with the damping kept, followed by his Lemma A.3. The paper is AI-assisted; its section on the use of AI tools says how. It has not been peer reviewed.