Heavy-Tailed Stochastic Optimization

Follow this topic Ask about this topic

The field studies how to optimize noisy objectives when gradient estimates can contain rare, very large shocks, often with finite moments but infinite variance. Common approaches include clipping or normalizing gradients, robust minibatch estimators, adaptive methods, and mirror descent; complementary analyses ask when ordinary SGD and momentum work without modifying their updates. Results cover convex and nonconvex problems as well as constrained, distributed, and Markovian settings, with guarantees for expected convergence, high-probability error, and last iterates. A central tension is that clipping can control outliers and improve guarantees but also introduce bias, while unclipped or adaptive methods may converge more slowly or require stronger assumptions.

Latest papers

37 papers7 papers in the last four weeks, up 17% on the four weeks before. 0.0% of all new papers.

Robust stochastic first order methods in heavy-tailed noise via medoid mini-batch gradient sampling
May 8, 2026Manojlo Vukovic, Dusan JakoveticStochastic Optimization Nonconvex Stochastic Optimization
Faculty of Technical Sciences, University of Novi Sad, Novi Sad, Serbia · Faculty of Sciences, University of Novi Sad, Novi Sad, Serbia
Muon with Nesterov Momentum: Heavy-Tailed Noise and (Randomized) Inexact Polar Decomposition
May 7, 2026Sayantan Choudhury, Xiaoran Cheng, Martin Takáč +2Stochastic Optimization Momentum Methods
MBZUAI · Penn State University · Georgia Institute of Technology +1
Optimal Rates for Pure $\varepsilon$ -Differentially Private Stochastic Convex Optimization with Heavy Tails
Apr 7, 2026Andrew LowyHeavy-Tailed Stochastic Optimization Differential Privacy
CISPA Helmholtz Center for Information Security
Muon Converges under Heavy-Tailed Noise: Nonconvex Hölder-Smooth Empirical Risk Minimization
Mar 16, 2026Hideaki IidukaNonconvex Stochastic Optimization Muon Optimizer
Department of Computer Science Meiji University 1-1-1 Higashimita, Tama-ku, Kawasaki-shi, Kanagawa 214-8571 Japan
Asynchronous Heavy-Tailed Optimization
Feb 20, 2026Junfei Sun, Dixi Yao, Xuchen Gong +3Stochastic Optimization Heavy-Tailed Stochastic Optimization
University of Chicago · Work done at Meta.
RanSOM: Second-Order Momentum with Randomized Scaling for Constrained and Unconstrained Optimization
Feb 6, 2026El Mahdi Chayti, Mohamad FakhouriFrank-Wolfe Algorithms Second-Order Optimization
Machine Learning and Optimization Laboratory (MLO) EPFL, Switzerland
Accelerated stochastic first-order method for convex optimization under heavy-tailed noise
Oct 13, 2025Chuan He, Bowen Li, Zhaosong LuStochastic Optimization Heavy-Tailed Noise
Department of Mathematics, Linköping University, Sweden · Department of Industrial and Systems Engineering, University of Minnesota, USA

May 8, 2026J/K move · Enter open · S save

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

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

Open paper AskPDF arXiv

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.