Heavy-Tailed Stochastic Optimization

Momentum

2 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 22

Oct 7, 2026math.OC

Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping

Heavy-tailed noise has been widely observed in modern machine learning, motivating the use of methods like gradient clipping and normalization. While these methods are well understood in centralized settings, much less is known in decentralized ones, where applying a nonlinearity to local gradients affects both optimization and consensus. Recent works on decentralized non-convex optimization have studied both clipping and normalization under heavy-tailed noise, with clipping yielding suboptimal rates and normalization needing local momentum or mini-batches to converge. This raises the question: can a baseline decentralized method using a nonlinearity achieve optimal convergence rates under heavy-tailed noise? We answer affirmatively with clipped decentralized SGD (

\mathtt{DSGD}

). For smooth non-convex costs under bounded

p

-th moment noise,

p \in (1,2]

, we show that clipped

\mathtt{DSGD}

achieves order-optimal rates both with high probability and in expectation. Moreover, we establish a linear speed-up in the number of agents, which, to our knowledge, has not been shown for decentralized methods with clipping. The key technical ingredient is a sharp analysis of the consensus gap that exploits the structure of clipping, relegating network effects to higher-order terms. Our results highlight an important distinction between clipping and normalization in decentralized settings: while normalized

\mathtt{DSGD}

can fail to converge, clipping retains magnitude information, enabling

\mathtt{DSGD}

to be convergent and order-optimal. Numerical experiments validate our theory.

Aleksandar Armacki, Haoyuan Cai, Ali H. Sayed

Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland

Decentralized Optimization Stochastic Gradient Descent Heavy-Tailed Stochastic Optimization Nonconvex Stochastic Optimization Gradient Clipping

Ask PDF

Sep 24, 2026stat.ML

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

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.

Wei Biao Wu

Nonconvex Stochastic Optimization Stochastic Optimization Convergence Stochastic Gradient Descent Heavy-Tailed Stochastic Optimization

Ask PDF

Sep 14, 2026cs.LG

Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and H"{o}lder Smoothness

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"older continuous gradients,

s\in(0,1]

, and gradient noise satisfying only a bounded

\alpha

-th moment condition for

\alpha\in(1,2]

. We establish three convergence results. Firstly, that standard SGD converges at rate

O(T^{-s/(1+s)})

whenever

\alpha\ge1+s

, extending the classical nonconvex SGD rate to heavy-tailed noise and H"older smoothness simultaneously. Secondly, we analyze

\delta

-regularized gradient clipping (

\delta

-GClip), a provable trainer of wide and deep nets, and establish a stationarity rate of

O(T^{-2s(\alpha-1)/[(1+s)(2\alpha-1)]})

under the same condition. Thirdly, we analyze standard gradient clipping (G-Clip) and show that it recovers the above rate for

\alpha\ge1+s

while in the very heavy-tailed regime

\alpha<1+s

, it has a convergence rate

O(T^{-2s(\alpha-1)/[(\alpha-1)+s(2\alpha-1)]})

--- the first convergence guarantee in this regime for any stochastic gradient based method.

Misbah Uz Zaman, Anirbit Mukherjee

Department of Mathematics and Statistics Indian Institute of Science Education and Research Kolkata · Department of Computer Science The University of Manchester

Gradient Clipping Nonconvex Stochastic Optimization Heavy-Tailed Stochastic Optimization Stochastic Gradient Descent

Ask PDF

Jul 29, 2026cs.LG

The Convergence Behavior of Adam under Heavy-Tailed Noise

We establish the first convergence guarantees for the plain vector-form Adam optimizer under heavy-tailed stochastic noise. While several Adam variants are known to achieve optimal iteration complexity in bounded-variance nonsmooth nonconvex optimization, little is understood about their behavior when stochastic gradients admit only a bounded

p

-th central moment for some

p \in (1,2]

, a setting increasingly observed in modern deep learning. To address this gap, we generalize the recent online-to-nonconvex conversion framework to accommodate heavy-tailed martingale-difference noise. Building on this generalized framework, we develop a discounted regret analysis for Adam, without restrictive parameter coupling. Our results show that Adam converges to

(ρ,ε)

-stationary points under heavy-tailed noise. However, it exhibits a suboptimal iteration complexity and

p

-dependent convergence, a suboptimality that persists even in the bounded-variance case (

p=2

). Specifically, the

ε

-dominant term in the iteration complexity for reaching in-expectation stationarity is

T=\mathrm{O}\left(Δρ^{1/2}(G+σ)^{\frac{5p}{3p-4}}ε^{-\left(\frac{5p}{3p-4}+\frac{3}{2}\right)}\right)

for

p\in(\frac{4}{3},2]

, which simplifies to

T=\mathrm{O}(ε^{-13/2})

when

p=2

. When the domain radius is known and used to control the online-learner output, a standard setup in related literature, the convergence rate improves to match the optimal complexity. In this case, the

ε

-dominant iteration complexity is

T=\mathrm{O}\left(Δρ^{1/2}(G+σ)^{\frac{p}{p-1}}ε^{-\left(\frac{p}{p-1}+\frac{3}{2}\right)}\right)

for

p\in(1,2]

, which simplifies to

T=\mathrm{O}(ε^{-7/2})

when

p=2

. These findings provide new theoretical insight into the robustness and limitations of Adam in heavy-tailed regimes.

Yijiang Pang

Michigan State University, East Lansing, USA

Nonconvex Stochastic Optimization Heavy-Tailed Noise Stochastic Optimization Convergence Adaptive Gradient Methods Heavy-Tailed Stochastic Optimization

Ask PDF

Jul 29, 2026cs.LG

Parameter-Free Dynamic Regret under Heavy-Tailed Noise

We study online convex optimization with one unbiased stochastic subgradient per round and noise having a finite

p

-th central moment, where

p\in(1,2]

is unknown. For a bounded convex domain of diameter

D

, subgradients bounded by

G

, noise scale

σ

, and comparator path length

P_T

, let

Λ_T=1+P_T/D

. A single algorithm, using none of

G,σ,p,P_T

, attains expected dynamic regret

O_p\left(\min\{GD\sqrt{TΛ_T}+σDT^{1/p}Λ_T^{(p-1)/p},\,GDT\}\right)

against every fixed comparator sequence. Restarted AdaGrad experts produce the noise-path exponent

(p-1)/p

, and a prior favoring longer restart intervals removes horizon-dependent logarithmic overhead. We give an explicit bound uniform in

p

; its logarithm-free form has noise coefficient

O(1+\log(p/(p-1)))

, while the static-regret constant is universal. The analysis requires only marginal noise moments and permits dependent errors. Complete pathwise proofs retain both the expert-loss range and the gradient energies preceding comparator movement. Matching lower bounds hold on every bounded convex domain of positive diameter, under the same gradient-only information model. Together with a path-budget-tuned upper bound, they characterize the minimax rate with universal constants, including its linear-regret saturation.

Vaneet Aggarwal

Purdue University

Online Convex Optimization Dynamic Regret Minimization Minimax Regret Heavy-Tailed Noise Adaptive Gradient Methods Heavy-Tailed Stochastic Optimization

Ask PDF

Jul 28, 2026cs.LG

Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise

We study stochastic optimization with heavy-tailed gradient noise. We first propose a novel quantum mean estimator for multivariate heavy-tailed random variables that achieves lower query complexity than optimal classical estimators in the low-dimensional regime. We further develop an unbiased quantum mean estimator by applying a generalized multi-level Monte Carlo technique. We prove quantum lower bounds showing that, when the dimension

d

of the random vector is small and can be viewed as a constant, our quantum estimators are optimal up to logarithmic factors. We further derive stronger dimension-dependent lower bounds for tail index

p>4/3

, showing that a nontrivial dependence on the dimension is unavoidable in the low-dimensional regime. Based on these estimators, we propose a quantum normalized stochastic gradient descent method (

\texttt{QNSGD}

), which finds an

ε

-stationary point using

\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{5p-4}{2p-2}}\big)

queries to the quantum stochastic gradient oracle. For a convex objective function, we propose a quantum projected stochastic gradient descent method (

\texttt{QPSGD}

), which computes a solution with

ε

-optimal solution using

\tilde{\mathcal{O}}\big(\sqrt d\,ε^{-\frac{3p-2}{2p-2}}+ε^{-2}\big)

queries in expectation. These sharper bounds improve upon the classical lower bounds

Ω\big(ε^{-\frac{3p-2}{p-1}}\big)

for nonconvex problems and

Ω\big(ε^{-\frac{p}{p-1}}\big)

for convex problems in the low-dimensional regimes

d\lesssimε^{-\frac{p}{p-1}}

and

d\lesssimε^{-\frac{2-p}{p-1}}

, respectively.

Bin Luo, Chengchang Liu, Jonathan Allcock +2

The Chinese University of Hong Kong · Westlake University · Tencent Quantum Laboratory

Nonconvex Stochastic Optimization Heavy-Tailed Noise Quantum Machine Learning Heavy-Tailed Stochastic Optimization

Ask PDF

Jul 9, 2026cs.LG

Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalization

Stochastic gradient descent (SGD) is a cornerstone of modern optimization. While its performance under heavy-tailed noise is often addressed through specialized modifications such as gradient clipping or normalization, we investigate a more fundamental question: how does vanilla SGD, particularly with momentum, perform in the presence of heavy-tailed noise? In this paper, we refine existing convergence results for vanilla SGD and, more importantly, provide the first comprehensive convergence analysis of vanilla SGD with momentum for strongly convex, convex, and nonconvex objectives, without employing any gradient control mechanisms. Our results demonstrate that the obtained convergence rates are inferior to the optimal rates achieved by clipped or normalized variants of SGD, thereby revealing inherent limitations of vanilla methods under heavy-tailed noise. The theoretical findings are supported by experiments on synthetic functions.

Ryusei Yamada, Naoki Sato, Hideaki Iiduka

Meiji University, Japan

Heavy-Tailed Noise Stochastic Optimization Convergence Heavy-Tailed Distributions Heavy-Tailed Stochastic Optimization Stochastic Gradient Descent

Ask PDF

Jun 24, 2026cs.LG

High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence

We study first-order methods for smooth objectives satisfying the Polyak-Łojasiewicz (PL) condition when gradient samples are generated by an exogenous Markov chain. In the light-tailed setting, prior uniform-in-time high-probability bounds for ordinary Stochastic Gradient Descent (SGD) under a standard growth envelope scale as

\widetilde{O}(t_{mix}^2/k)

, leaving a gap with the

\widetilde{O}(t_{mix}/k)

expectation bounds. We close this gap using a lag-blocking argument to establish a uniform high-probability guarantee with a leading stochastic term of

\widetilde{O}(t_{mix}/(k+K_0))

under geometric mixing. We prove this linear dependence on the mixing time is optimal via a matching

Ω(σ^2 t_{mix}/k)

lower bound on a quadratic objective driven by a persistent two-state chain. We then extend this framework to heavy-tailed Markovian gradients satisfying a stationary finite-

p

-moment condition,

p \in (1,2]

. We design an all-samples clipped block method that uses every Markov transition while mitigating Markovian bias. Under a transition budget

T

, this algorithm achieves a high-probability stochastic error of

\widetilde{O}(σ_p^2(t_{mix}/T)^{2(p-1)/p})

. We establish a matching lower bound by reducing PL optimization to heavy-tailed mean estimation for a sticky Markov chain. Ultimately, this work tightly characterizes the optimal polynomial dependence on mixing time for light-tailed PL-SGD, and the optimal heavy-tail exponent and effective-sample-size dependence in the robust regime.

Dhruv Sarkar, Aprameyo Chakrabartty, Vaneet Aggarwal

Indian Institute of Technology Kharagpur · Mohamed bin Zayed University of Artificial Intelligence · Purdue University

Stochastic Optimization Optimization Convergence Analysis Heavy-Tailed Noise Stochastic Optimization Convergence Heavy-Tailed Distributions Heavy-Tailed Stochastic Optimization+1

Ask PDF

Jun 24, 2026cs.LG

Is Variational Monte Carlo Robust? Sharp Moment Thresholds and Heavy-tailed Stochastic Optimization

Variational Monte Carlo (VMC) is a central algorithm in electronic structure theory and has gained renewed importance through modern neural-network ansätze such as FermiNet. At its core, VMC seeks ground states by minimizing the Rayleigh quotient by stochastic optimization. In this work, we show that the resulting stochastic optimization problem is intrinsically governed by the nodal geometry of the underlying wave function. More precisely, we establish that properties of the nodal set determine the integrability of the local energy and gradient estimators that drive VMC. For broad and practically relevant ansatz classes, including Slater-Jastrow wave functions with variable-exponent Slater-type orbitals, we prove that these estimators are generically heavy-tailed and fail to admit higher moments. At the same time, for general analytic ansätze, we prove weak moment bounds for the relevant estimators and identify precise low-moment regimes, showing how generic and degenerate nodal structures lead to different integrability thresholds. Building on this analysis, we introduce a new robust variant of VMC

\unicode{x2013}

coined PS-Clip-VMC

\unicode{x2013}

which is based on clipping both the local energy and the gradient random variable. We prove that PS-Clip-VMC converges both in expectation and with high probability in the weak moment regime of VMC. Preliminary experiments for training FermiNet on Atoms with up to 18 electrons suggest that PS-Clip-VMC is significantly more robust than standard methods.

Philipp Grohs, Davide Nobile

Faculty of Mathematics, University of Vienna · RICAM, Austrian Academy of Sciences

Stochastic Optimization Quantum Chemistry Quantum Many-Body Physics Heavy-Tailed Stochastic Optimization

Ask PDF

Jun 22, 2026cs.LG

Open Problem: Is AdamW Effective Under Heavy-Tailed Noise?

AdamW is the de facto optimizer for training large language models (LLMs), yet the theory behind it still lives mostly in finite-variance regimes. This is increasingly unsatisfying, as empirical evidence indicates that stochastic gradient noise in LLM pretraining is typically heavy-tailed. Recent work shows that sign-based optimizers such as Lion and Muon achieve sharp heavy-tailed rates, and that AdaGrad can also converge under heavy-tailed noise. However, no rigorous convergence theory for AdamW has yet been established in this regime. Can AdamW converge under the same heavy-tailed assumptions, or does its second-moment accumulator create a genuine obstruction? We formulate this as an open problem, prove a positive weighted-metric benchmark, and give a corridor lower-bound mechanism showing how denominator memory can hide large gradients.

Dingzhi Yu, Hongyi Tao, Yuanyu Wan +2

1Nanjing University · 2Zhejiang University · 3Fudan University

Stochastic Optimization Heavy-Tailed Noise Stochastic Optimization Convergence Heavy-Tailed Distributions Adaptive Gradient Methods Heavy-Tailed Stochastic Optimization

Ask PDF

Jun 21, 2026cs.LG

Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm

Federated learning (FL) is an emerging distributed machine learning paradigm that enables local devices to jointly train a global model while keeping data decentralized and private. We propose a variance-reduction based algorithm, VRA-FedSGD, for FL in the presence of heavy-tailed gradient noise and communication noise, where these noises are prevalent in large-scale machine learning over wireless networks and Internet of Things deployments. VRA-FedSGD employs a momentum variance reduction technique together with a nonlinear mapping to mitigate heavy-tailed gradient noise, and uses a variance-reduced aggregation mechanism to suppress heavy-tailed communication noise. In the mean sense, VRA-FedSGD achieves a convergence rate of {\small

\mathcal{O}\left(K^{-(p-1)/(2p-1)}\right)

} for nonconvex objective functions, where

p

is the tail index of heavy-tailed noise. In the almost sure sense, VRA-FedSGD achieves a convergence rate of

\tilde{\mathcal{O}}\left(K^{-(1-1/(p-ε))}\right)

for strongly convex objective functions, where

ε

is an arbitrarily small constant. Simulated experiments on a logistic regression problem with real-world data verify the effectiveness of VRA-FedSGD.

Shengchao Zhao, Yongchao Liu

School of Mathematics, China University of Mining and Technology, Xuzhou, China · School of Mathematical Sciences, Dalian University of Technology, Dalian, China

Stochastic Optimization Nonconvex Stochastic Optimization Heavy-Tailed Noise Variance Reduction Heavy-Tailed Stochastic Optimization Federated Learning

Ask PDF

Jun 21, 2026cs.LG

Distribution-Aware Robust Bilevel Optimization: Quantile-Guided Huber Updates in Two-Timescale Stochastic Approximation

Bilevel optimization (BLO) is fundamental to hierarchical decision-making but suffers from critical instability under heavy-tailed stochastic noise. Existing variance-reduction techniques typically rely on myopic magnitude checks, which fail to distinguish informative geometric signals from impulsive outliers. To resolve this, we propose \textbf{RQ-TTSA} (Robust Quantile-guided TTSA), a distribution-aware framework that leverages historical gradient buffers to estimate rolling quantiles for adaptive Huber-style clipping, effectively preserving local optimization geometry while strictly bounding effective variance. Theoretically, we provide a convergence analysis for quantile-guided TTSA under nonconvex-strongly convex assumptions with infinite-variance noise (

p \in (1,2]

), deriving a rate of

\mathcal{O}(T^{-\frac{p-1}{3p-2}})

that recovers optimal dependence on the heavy-tailed parameter. Empirically, across six diverse tasks, spanning heterogeneous vision benchmarks, dynamic games under momentum poisoning, and offline reinforcement learning, RQ-TTSA consistently outperforms state-of-the-art baselines by eliminating divergence spikes and ensuring stable convergence. Our method demonstrates significant robustness to hyperparameter variations and incurs negligible computational overhead (

\approx 2.7\%

increase), validating distribution-aware gradient control as a practical and necessary component for reliable bilevel learning.

Zhiyu Li, Xi Xuan, Davide Carbone

University of Science and Technology of China Hefei, China · City University of Hong Kong Hong Kong SAR, China · Laboratoire de Physique de l’École Normale Supérieure, Université PSL, CNRS, Sorbonne Université, Université de Paris Paris, France

Stochastic Optimization Stochastic Approximation Bilevel Optimization Two-Timescale Stochastic Approximation Heavy-Tailed Stochastic Optimization

Ask PDF

Jun 12, 2026math.OC

Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success

Non-Euclidean optimisation methods with matrix-valued updates, such as Muon and Scion, have recently shown strong empirical performance for training Transformer models, yet their theoretical advantages over Euclidean methods remain poorly understood. We address this gap in the heavy-tailed non-convex regime, where stochastic gradients have bounded

p

-th central moments,

p \in (1,2]

. We show that certain non-Euclidean methods achieve optimal sample complexity under stronger stationarity measures, while Euclidean methods incur additional dimension-dependent costs. As a consequence, for

m \times n

matrices, Muon finds an

\varepsilon

-stationary point in nuclear norm within

\mathcal{O}\left(\min\{m, n\} \frac{Δ_1 L}{\varepsilon^2} \left(\frac σ\varepsilon \right)^{\frac p {p-1}}\right)

samples, absorbing heavy-tailed noise without extra dimension dependence, unlike Euclidean methods. We further prove this sample complexity, including its dimension dependence, is optimal for all first-order methods under nuclear-norm stationarity. Experiments on large language models support our theory. Surprisingly, our results suggest that other Schatten geometries beyond the spectral geometry of Muon can perform competitively in certain settings.

Florian Hübler, Thomas Pethick, Suvrit Sra

Department of Computer Science, ETH Zurich, Switzerland · Department of Mathematics, Technical University of Munich, Germany · Munich Center for Machine Learning (MCML)

Stochastic Optimization Nonconvex Stochastic Optimization Heavy-Tailed Noise Muon Optimizer Stochastic Optimization Convergence Matrix Optimization+1

Ask PDF

Jun 2, 2026math.OC

Bregman meets Lévy: Stochastic mirror descent with heavy-tailed noise in continuous and discrete time

We study the robustness of stochastic mirror descent (SMD) under heavy-tailed noise, focusing on whether the method retains its convergence guarantees when run with infinite-variance stochastic gradient input. To address this question in a principled manner, we begin by introducing a continuous-time model of SMD as a stochastic differential equation (SDE) driven by a centered Lévy noise process with finite

p

-th order moments,

1 < p \leq 2

. This scheme -- which we call the Lévy mirror flow (LMF) -- arises naturally as the scaling limit of SMD in the presence of heavy-tailed noise. In particular, when

p < 2

-- the heavy noise regime -- the trajectories of LMF generically exhibit jump discontinuities of arbitrary magnitude which, if frequent enough, lead to infinite variance. Nonetheless, despite this highly singular behavior, we show that LMF attains

ε

-optimality within

\mathcal{O}(ε^{-p/(p-1)})

time in the convex case, and within

\mathcal{\tilde O}(ε^{-1/(p-1)})

time for (relatively) strongly convex objectives. These guarantees provide a transparent characterization of the impact of frequent long jumps on the convergence of the process, and percolate to a series of matching discrete-time guarantees for several variants of SMD under heavy-tailed noise.

Pierre-Louis Cauvin, Panayotis Mertikopoulos

Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.

Stochastic Optimization Stochastic Differential Equations Heavy-Tailed Noise Mirror Descent Stochastic Optimization Convergence Heavy-Tailed Distributions+1

Ask PDF

May 30, 2026math.OC

In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise

Many stochastic gradient methods are believed not to converge when the noise in stochastic gradients has only a finite

p

-th moment for

p\in\left(1,2\right)

, a setting known as the heavy-tailed noise assumption. However, some recent studies have found that Stochastic Gradient Descent (

\textsf{SGD}

), without any modification to its update rule, can surprisingly converge in expectation for convex problems with bounded domains, highlighting the potential of classical stochastic gradient methods. Inspired by this recent progress, we provide a comprehensive study of stochastic optimization under heavy-tailed noise and establish new in-expectation convergence results for Stochastic Mirror Descent (

\textsf{SMD}

) and Accelerated Stochastic Mirror Descent (

\textsf{ASMD}

) in convex optimization, and for

\textsf{SGD}

and Stochastic Gradient Descent with Momentum (

\textsf{SGDM}

) in nonconvex optimization. Notably, our results not only hold without algorithmic changes but also avoid restrictive assumptions, such as bounded domains, imposed in prior work. More importantly, our analysis provides a new, elegant, and powerful framework for studying heavy-tailed stochastic optimization, opening a new route to understanding first-order stochastic gradient methods.

Zijian Liu

Stern School of Business, New York University

Stochastic Optimization Nonconvex Stochastic Optimization Stochastic Optimization Convergence Heavy-Tailed Stochastic Optimization Stochastic Gradient Descent

Ask PDF

May 23, 2026cs.LG

Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

This paper considers the nonconvex nonsmooth problem in which the objective function is Lipschitz continuous. We focus on the stochastic setting where the algorithm can access stochastic function value evaluations with heavy-tailed noise, which is prevalent in many popular machine learning applications. We propose a stochastic zeroth-order algorithm that refines the framework of online-to-nonconvex conversion by clipping the two-point gradient estimator. The theoretical analysis shows that our algorithm can find a

(δ, ε)

-Goldstein stationary point with zeroth-order oracle complexity of

{\mathcal O}(d^{\frac{p}{2(p-1)}}δ^{-1}ε^{-\frac{2p-1}{p-1}})

, where

d

is the problem dimension and

p\in(1,2]

is the order of bounded moments. Note that our dependence on dimension

d

matches the best-known results of stochastic zeroth-order optimization for finding the sub-optimal solution of a stochastic convex nonsmooth problem. In addition, our dependence on accuracy parameters

δ

and

ε

is consistent with that of the best-known stochastic first-order algorithms for stochastic nonconvex nonsmooth problems. Finally, we conduct numerical experiments to demonstrate the effectiveness of the proposed method.

Zhuanghua Liu, Luo Luo

Stochastic Optimization Gradient Clipping Zeroth-Order Optimization Heavy-Tailed Noise Nonconvex Optimization Nonsmooth Convex Optimization+1

Ask PDF

May 18, 2026math.OC

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Many tasks in modern machine learning are observed to involve heavy-tailed gradient noise during the optimization process. To manage this realistic and challenging setting, new mechanisms, such as gradient clipping and gradient normalization, have been introduced to ensure the convergence of first-order algorithms. However, adaptive gradient methods, a famous class of modern optimizers that includes popular

\mathtt{Adam}

and

\mathtt{AdamW}

, often perform well even without any extra operations mentioned above. It is therefore natural to ask whether adaptive gradient methods can converge under heavy-tailed noise without any algorithmic changes. In this work, we take the first step toward answering this question by investigating a special case,

\mathtt{AdaGrad}

, the origin of adaptive gradient methods. We provide the first provable convergence rate for

\mathtt{AdaGrad}

in non-convex optimization when the tail index

p

satisfies

4/3<p\leq2

. Notably, this result is achieved without requiring any prior knowledge of

p

and is hence adaptive to the tail index. In addition, we develop an algorithm-dependent lower bound, suggesting that the existing minimax rate for heavy-tailed optimization is not attainable by

\mathtt{AdaGrad}

. Lastly, we consider

\mathtt{AdaGrad}\text{-}\mathtt{Norm}

, a popular variant of

\mathtt{AdaGrad}

in theoretical studies, and show an improved rate that holds for any

1<p\leq2

under an extra mild assumption.

Zijian Liu

Stern School of Business, New York University

Stochastic Optimization Nonconvex Stochastic Optimization Heavy-Tailed Noise Stochastic Optimization Convergence Heavy-Tailed Distributions Adaptive Gradient Methods+1

Ask PDF

May 18, 2026math.OC

Scale-Invariant Neural Network Optimization: Norm Geometry and Heavy-Tailed Noise

A growing lesson from neural network optimization is that optimizer design should respect how the model is parametrized. The layerwise input-output structure of neural networks motivates scale-invariant optimizers, such as Muon and Scion, whose updates also support hyperparameter transfer. At the same time, stochastic gradient noise in deep learning is often far from sub-Gaussian and may exhibit heavy tails. These observations have shaped recent algorithmic principles for training neural networks, yet their joint theoretical consequences are underexplored. In particular, it remains unclear what dimension dependence is unavoidable for gradient-based methods given the problem class is defined by input-output norm and under heavy-tailed noise, and whether higher-order smoothness can accelerate training. We study these questions through nonconvex smooth stochastic optimization over

\mathbb R^{m\times n}

equipped with general norms and under

p^\mathrm{th}

-moment heavy-tailed noise, where the goal is to achieve an

ε

-stationary point in the dual norm. Our first contribution is a dimension-dependent lower bound: when

\frac{\max\{m,n\}}{(\min\{m,n\})^2}

is large enough, any gradient-based method requires

Ω(\min\{m, n\}ε^{-\frac{3p-2}{p-1}})

oracles for the problem class defined by the spectral norm, which is a common input-output norm. We prove that a scale-invariant Scion method with the spectral norm can achieve the matching upper bound of

O(\min\{m, n\}ε^{-\frac{3p-2}{p-1}})

. To exploit higher-order smoothness, we propose a transported Scion method and improve the bound to

O(\min\{m, n\}ε^{-\frac{5p-3}{2p-2}})

when the Hessian is Lipschitz. Finally, we incorporate heuristics into our transported method and evaluate it across multiple architectures and model sizes, demonstrating its flexibility and compatibility with neural network training.

Jiayu Zhang, Tianyi Lin

Department of Industrial Engineering and Operations Research Columbia University

Stochastic Optimization Neural Network Optimization Nonconvex Stochastic Optimization Heavy-Tailed Noise Stochastic Optimization Convergence Heavy-Tailed Stochastic Optimization

Ask PDF

May 12, 2026cs.LG

Gradient Clipping Beyond Vector Norms: A Spectral Approach for Matrix-Valued Parameters

Gradient clipping is a standard safeguard for training neural networks under noisy, heavy-tailed stochastic gradients; yet, most clipping rules treat all parameters as vectors and ignore the matrix structure of modern architectures. We show empirically that data outliers often amplify only a small number of leading singular values in layer-wise gradient matrices, while the rest of the spectrum remains largely unchanged. Motivated by this phenomenon, we propose spectral clipping, which stabilizes training by clamping singular values that exceed a threshold while preserving the singular directions. This framework generalizes classical gradient norm clipping and can be easily integrated into existing optimizers. We provide a convergence analysis for non-convex optimization with spectrally clipped SGD, yielding the optimal

\mathcal{O}\left(K^{\frac{2 - 2α}{3α- 2}}\right)

rate for heavy-tailed noise. To minimize hyperparameter tuning, we introduce layer-wise adaptive thresholds based on moving averages or sliding-window quantiles of the top singular values. Finally, we develop efficient implementations that clip only the top

r

singular values via randomized truncated SVD, avoiding full decompositions for large layers. We demonstrate competitive performance across synthetic heavy-tailed settings and neural network training tasks.

Alexander Yukhimchuk, Mladen Kolar, Martin Takáč +1

MBZUAI · University of Southern California

Stochastic Optimization Gradient Clipping Nonconvex Stochastic Optimization Heavy-Tailed Stochastic Optimization Stochastic Gradient Descent

Ask PDF

May 8, 2026math.OC

Robust stochastic first order methods in heavy-tailed noise via medoid mini-batch gradient sampling

We consider a first order stochastic optimization framework where, at each iteration,

K

independent identically distributed (i.i.d.) data point samples are drawn, based on which stochastic gradients can be queried. We allow gradient noise to be heavy-tailed, with possibly infinite variances. For the considered heavy-tailed setting, many algorithmic variants have recently been proposed based on gradient clipping or other nonlinear operators (e.g., normalization) applied over noisy gradients. In this paper, we take an alternative approach and propose a novel stochastic first order method dubbed Robust Stochastic Gradient Descent with medoid mini-batch gradient sampling, R-SGD-Mini for short. The core idea of R-SGD-Mini is to split the

K

-sized data batch into

M

distinct data chunks, form for each chunk the stochastic gradient, and update the solution estimate with respect to the stochastic gradient direction of the chunk that is medoid of gradients of all data-chunks. Under a general class of symmetric heavy-tailed gradient noises and a standard non-convex setting, we establish explicit bounds on the expected time-averaged squared gradient norm. More precisely, we show that the latter quantity converges at rate

\mathcal{O}(T^{-1})

to a small neighborhood of zero; we explicitly characterize this neighborhood in terms of noise and algorithm's parameters. Moreover, if the time horizon is known in advance, we establish the rate of

\mathcal{O}(T^{-\frac{1}{2}}).

Furthermore, when clipping is incorporated, we obtain convergence guaranties in the high-probability sense and recover the same rate. Experimental results indicate that R-SGD-Mini and its clipped variant consistently perform favorably compared to SGD, clipped SGD and Median-of-Means based methods.

Manojlo Vukovic, Dusan Jakovetic

Faculty of Technical Sciences, University of Novi Sad, Novi Sad, Serbia · Faculty of Sciences, University of Novi Sad, Novi Sad, Serbia

Stochastic Optimization Nonconvex Stochastic Optimization Heavy-Tailed Noise Stochastic Optimization Convergence Heavy-Tailed Distributions Heavy-Tailed Stochastic Optimization+1

Ask PDF

May 7, 2026math.OC

Muon with Nesterov Momentum: Heavy-Tailed Noise and (Randomized) Inexact Polar Decomposition

Most first-order optimizers treat matrix-valued parameters as vectors, ignoring the intrinsic geometry of hidden-layer weights in neural networks. Muon addresses this mismatch by updating along the polar factor of a momentum matrix, but its theoretical understanding has lagged behind practice. In particular, practical implementations incorporate Nesterov momentum, compute the polar factor only approximately, and operate with stochastic gradients that may be heavy-tailed. We close this gap by developing a convergence theory for Muon with Nesterov momentum and inexact polar decomposition in non-convex matrix optimization under heavy-tailed noise. Our analysis builds on a unified framework for inexact polar decomposition that captures practical iterative approximations such as Newton-Schulz and quantifies how their errors propagate through the optimization dynamics. Under this framework, we establish an optimal iteration and sample complexity of

O \left(\varepsilon^{\frac{-(3α-2)}{(α-1)}} \right)

for finding an

\varepsilon

-stationary point, where

α\in(1,2]

denotes the heavy-tail index. For the inexact-polar setting with

σ_1=0

, we also provide guarantees that do not require prior knowledge of

α

. We analyze a randomized low-rank polar decomposition that is substantially more efficient than full-space methods while remaining compatible with our theory. Numerical experiments further demonstrate the effectiveness of the proposed inexact and randomized variants.

Sayantan Choudhury, Xiaoran Cheng, Martin Takáč +2

MBZUAI · Penn State University · Georgia Institute of Technology +1

Stochastic Optimization Momentum Methods Gradient Descent Nonconvex Stochastic Optimization Muon Optimizer Matrix Optimization+1

Ask PDF

Oct 13, 2025math.OC

Accelerated stochastic first-order method for convex optimization under heavy-tailed noise

We study convex composite optimization problems, where the objective function is given by the sum of a prox-friendly function and a convex function whose subgradients are estimated under heavy-tailed noise. Existing work often employs gradient clipping or normalization techniques in stochastic first-order methods to address heavy-tailed noise. %In this paper, we demonstrate that a vanilla stochastic algorithm---without additional modifications such as clipping or normalization---can achieve optimal complexity for these problems. In this paper, we analyze the first-order oracle complexity of vanilla stochastic algorithms---without additional modifications such as clipping or normalization---for solving these problems. In particular, we establish that an accelerated stochastic proximal subgradient method achieves a first-order oracle complexity for finding an approximate optimal solution in expectation that is universally optimal for smooth, weakly smooth, and nonsmooth convex optimization, as well as for stochastic convex optimization under heavy-tailed noise. Moreover, we derive high-probability first-order oracle complexity bounds for the accelerated stochastic proximal subgradient method under heavy-tailed and sub-Weibull noise, respectively. Numerical experiments are further provided to illustrate the numerical behavior of the methods.

Chuan He, Bowen Li, Zhaosong Lu

Department of Mathematics, Linköping University, Sweden · Department of Industrial and Systems Engineering, University of Minnesota, USA

Stochastic Optimization Heavy-Tailed Noise Heavy-Tailed Stochastic Optimization

Ask PDF

Momentum

Related topics

Latest papers 22