Stochastic optimizers often face gradient noise with heavy tails, meaning occasional huge outliers whose variance may be infinite. The usual defense is to clip large gradients. Clipping, however, brings its own parameter: the threshold, and how fast it should grow over time. Existing theory sets that growth from the noise's tail index $p$, the highest moment of the noise that is finite. Nobody knows $p$ for a real problem. This proposal asks whether an adaptive optimizer such as Adam can set its clipping threshold from its own running estimate of gradient magnitude, multiplied by one fixed, slowly growing factor. The goal is a threshold that needs neither $p$ nor the distance to the solution, and that still comes with a proof that the iterates converge with probability one.
The opportunity sits between two recent results that do not meet. Almost Sure Convergence of Nonlinear Stochastic Approximation Under General Moment Conditions proves almost-sure convergence under noise with only a $p$-th moment, $p\in(1,2)$. It does this with a truncation threshold that depends on the unknown distance to the fixed point, and only for scalar step sizes and contractive operators. A Comprehensive Framework for Analyzing the Convergence of Adam proves almost-sure and last-iterate convergence of Adam's per-coordinate step sizes, but only when the noise has finite variance. The proposal is to build and analyze the method that both results point toward, and to measure whether it actually removes $p$ and the threshold scale as things a practitioner must tune.
Core Claim
Clip each coordinate of the stochastic gradient at $\tau_t\sqrt{\hat v_{t-1,i}}$. Here $\hat v_{t-1,i}$ is Adam's own exponential average of past squared clipped gradients for coordinate $i$, and $\tau_t=c\,(t+K)^{\kappa}$ is a deterministic growth factor with exponent $\kappa$ and constants $c, K$. The conjecture has two parts:
- Universal exponent. Because the gradient's scale is learned online, there is a single choice of $\kappa$, together with Adam's usual decaying step size, that gives $\|\nabla f(x_t)\|\to 0$ almost surely for every tail index $p\in(1,2]$. The required setting is smooth nonconvex $f$ with unbiased noise whose conditional $p$-th moment grows at most like the gradient. That growth condition is the $p$-th-moment analogue of the "ABC" variance condition in Jin et al.
- Insensitive constant. The scale constant $c$ then affects only constants in the analysis, not whether the method converges.
The second part is the parameter-sensitivity claim. The first is the asymptotic guarantee.
Why the threshold matters is captured by two elementary truncation bounds. For noise $\epsilon$ with $\mathbb{E}|\epsilon|^p\le M$ and threshold $B$, the bias of clipping and the second moment of the clipped noise satisfy
$$\big|\mathbb{E}[\epsilon\,\mathbf{1}\{|\epsilon|>B\}]\big|\le M/B^{p-1},\qquad \mathbb{E}[\epsilon^2\,\mathbf{1}\{|\epsilon|\le B\}]\le M\,B^{2-p}.$$
A martingale proof via the Robbins–Siegmund theorem must make the step-weighted sums of both terms finite. Both terms involve $p$, and the balance also depends on the scale $M$. This is why Provably Robust Temporal Difference Learning for Heavy-Tailed Rewards, which proves high-probability (not almost-sure) bounds for linear temporal-difference learning, ties its clipping schedule to $p$.
The hypothesis is that a threshold normalized by $\sqrt{\hat v}$ absorbs $M$ automatically. It may also partially absorb $p$, because under heavy tails $\hat v$ itself grows with the clipping level. If that coupling makes the effective bias–variance balance self-correcting, the remaining deterministic exponent can be fixed once for all $p$. If it does not, the project will instead locate exactly which $p$ values a given $\kappa$ covers. That is a sharpness result in the spirit of Nguyen et al.'s Theorem 2.2, which shows almost-sure convergence fails when the step exponent is at most $1/p$.
Relation to Prior Work
Two papers supply the proof machinery.
- Truncation side. Nguyen et al. contribute the state-dependent truncation analysis and the matching impossibility result. We drop their dependence on the unknown distance to the fixed point and their restriction to scalar steps on a contractive map.
- Adaptive side. Jin et al. contribute a Lyapunov function containing a dynamic scaling factor that cancels the instability of per-coordinate step sizes. We must extend it to a setting where the second-moment estimate is driven by clipped, heavy-tailed gradients and is not bounded in advance.
Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation bounds expected squared gradients for Adagrad- and AMSGrad-type methods with biased gradients. It shows the bias is harmless if it decays faster than $n^{-1/4}$. Clipping is exactly a decaying bias, so this result motivates the design and suggests the rate we should expect. However, it gives expectation bounds rather than almost-sure ones, and it requires the bias schedule to be known. Here the bias schedule is generated by the data.
Two adaptive-parameter papers motivate the concern that adaptivity can simply move the tuning burden to a new constant.
- Second-Order Step-Size Tuning of SGD for Non-Convex Optimization proves almost-sure convergence for a curvature-adapted scalar step. It still needs a hand-set step for regions of negative curvature, and it assumes bounded variance.
- BiSLS/SPS shows that adaptive step sizes can recover from initial step sizes that are wrong by orders of magnitude. Its line-search variant lacks a proof precisely because its gradients are biased.
These papers are why we treat sensitivity to $c$ and $K$ as a measured outcome rather than an assumption.
Research Program
The theoretical work proceeds in three stages.
- Scalar, contractive case. Replace Nguyen et al.'s distance-based threshold with the observable $\sqrt{\hat v_t}$-normalized threshold. Note that $1+\|x_n\|^2$ and $1+\|x_n-x^*\|^2$ are equivalent up to constants, so the distance dependence alone is easy to remove. The real work is replacing their $p$-dependent step-exponent window with a fixed $\kappa$. Determine for which $p$ almost-sure convergence holds.
- Per-coordinate case. Move to Adam's per-coordinate preconditioning on smooth nonconvex objectives. Adapt the Jin et al. Lyapunov function so that its scaling factor tracks the clipped second-moment estimate. Control the cross term between the clipping bias and the preconditioner using a first-hitting-time decomposition.
- Counterexamples. Construct scalar heavy-tailed examples showing where vanilla Adam (no clipping) and fixed-threshold clipped Adam fail to converge almost surely. This establishes that the adaptive threshold is doing real work.
The empirical work implements the method as a small modification to Adam. Its cost is one comparison per coordinate. It is applied both to neural network training and to linear temporal-difference learning with per-coordinate step sizes.
Baselines
Naive reference. The do-nothing reference is plain stochastic gradient descent with the Robbins–Monro schedule $a/(t+K)$ and no clipping. Its exponent of 1 already exceeds $1/p$ for every $p>1$, so it is the most honest "already solved" point. The cost is that the scale $a$ must be tuned.
Off-the-shelf adaptive. Vanilla Adam with $\beta_2\to1$ is the setting Jin et al. analyze under finite variance. We run it with the same step-size schedule as our method.
Strongest existing method. This is the dynamic clipping of Cayci and Eryilmaz, given oracle knowledge of the true $p$. It is the only method in the file with guarantees under infinite-variance noise. That paper reports qualitatively that robust temporal-difference learning converges smoothly where standard temporal-difference learning diverges on its 256-state Markov reward process with Pareto noise at $p=1.2$. No reported numerical error was found on Lacuna for that benchmark, so we will reproduce it.
Ablations. Two ablations isolate the key ingredient:
- Adam with a fixed global-norm clipping threshold tuned by grid search, which is current practice.
- Our method with $\hat v$ replaced by a constant, which keeps the growth factor but removes the self-normalization.
Fairness and the success criterion. Every method gets the same data, the same number of gradient evaluations, and the same tuning budget of 20 configurations over its free constants. Oracle-$p$ clipping receives $p$ for free on top of that budget. "Beating" the strongest baseline means two things together. First, our method matches oracle-$p$ clipping's final error within seed noise across $p\in\{1.1,1.2,1.5,1.8,2.0\}$ without being told $p$. Second, its range of $c$ that converges, measured in decades, is at least as wide as the range of the clipping constant that converges for the oracle method.
Why not just…?
Why not just use the step size $a/n$ without clipping? In the scalar contractive case it already converges almost surely for any $p>1$ by Nguyen et al.'s theorem, so it is a genuine threat. Our answer is empirical and specific: we expect its range of $a$ that converges to be narrow and dependent on $p$. The BiSLS/SPS experiments show that misscaled static step sizes stall or diverge. If our sensitivity sweep shows $a/n$ is as robust to its scale as our method is to $c$, the practical claim fails and only the per-coordinate theory remains.
Why not just use vanilla Adam, since dividing by $\sqrt{\hat v}$ already shrinks steps after an outlier? This is the most dangerous alternative. Infinite-variance noise inflates $\hat v$, which may act as automatic clipping. If our counterexample construction fails and vanilla Adam converges almost surely in every heavy-tailed experiment, we will report that as the main result: a theorem that Adam is tail-robust without modification. The clipping proposal would then be dropped.
Why not just tune a fixed clipping threshold by grid search? A fixed threshold leaves a bias that does not vanish, so the iterates settle near the solution rather than at it. Within a finite horizon, though, it may look fine. We therefore run horizons ten times longer than the tuning horizon and test whether the gradient norm keeps decreasing.
Proposed Experiments
Synthetic Markov reward process. We use the 256-state process with 128 features and Pareto reward noise from Cayci and Eryilmaz, plus their 256-state circular random walk. We sweep $p$ over the values above. Metrics are:
- the fraction of 50 seeds whose value error is still decreasing at $10^7$ steps;
- the largest excursion of the error;
- the final error.
Synthetic nonconvex problems. We use the ResNet-20 CIFAR-10 and CIFAR-100 setups and the MNIST autoencoder from Castera et al., with symmetric Pareto noise injected into minibatch gradients so that $p$ is controlled. Metrics are training loss, test accuracy, and the sensitivity window in $c$ and $a$. Castera et al. report only qualitative results ("better results than SGD, RMSprop, or ADAM"); no reported number on Lacuna, so baselines are rerun.
Decisive checks. Three outcomes would decide the project:
- Our method stays convergent across all $p$ with one fixed $\kappa$, while constant-normalized clipping fails at small $p$ for the same $\kappa$.
- The counterexample for vanilla Adam reproduces numerically.
- The width of the convergent range of $c$ does not shrink as $p$ decreases toward 1.
Failure of the first check with success of the others would reduce the contribution to a map of which $p$ values each $\kappa$ covers. Failure of the second would turn the project into the vanilla-Adam robustness theorem.
References
- Almost Sure Convergence of Nonlinear Stochastic Approximation Under General Moment Conditions
- A Comprehensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD
- Provably Robust Temporal Difference Learning for Heavy-Tailed Rewards
- Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation
- Second-Order Step-Size Tuning of SGD for Non-Convex Optimization
- BiSLS/SPS: Auto-tune Step Sizes for Stable Bi-level Optimization