aiqbench analysis
This research establishes that Stochastic Mirror Descent retains convergence guarantees even under heavy-tailed noise with infinite variance, provided the noise process has finite $p$-th order moments. By modeling the algorithm as a continuous-time Lévy mirror flow, the authors derive explicit bounds on the time required to reach $\epsilon$-optimality despite jump discontinuities in the trajectory. These theoretical findings offer a robust framework for optimizing non-smooth objectives in environments prone to extreme outliers, bridging the gap between singular stochastic dynamics and practical discrete-time implementations.
Bregman meets L\'evy: Stochastic mirror descent with heavy-tailed noise in continuous and discrete time
arXiv:2606.03769v1 Announce Type: cross Abstract: 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\'evy noise process with finite $p$-th order moments, $1 < p \leq 2$. This scheme -- which we call the L\'evy 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 $\epsilon$-optimality within $\mathcal{O}(\epsilon^{-p/(p-1)})$ time in the convex case, and within $\mathcal{\tilde O}(\epsilon^{-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.
Abstract: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 $\epsilon$-optimality within $\mathcal{O}(\epsilon^{-p/(p-1)})$ time in the convex case, and within $\mathcal{\tilde O}(\epsilon^{-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.
Optimization and Control (math.OC); Machine Learning (cs.LG); Probability (math.PR)
arXiv:2606.03769 [math.OC]
(or arXiv:2606.03769v1 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2606.03769 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 290 words
Related coverage
Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise
arXiv · Jul 29, 2026
The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization
arXiv · Sep 9, 2026
Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationarity
arXiv · Oct 6, 2026
On the Last-Iterate Convergence of Clipped Gradient Methods
arXiv · Oct 16, 2026