Title: Bregman Meets L\'evy: Stochastic Mirror Descent Under Heavy-Tailed Noise in Continuous and Discrete Time

Abstract: This paper investigates the resilience of stochastic mirror descent (SMD) when subjected to heavy-tailed noise, specifically examining whether the algorithm’s convergence properties hold even when the stochastic gradient inputs possess infinite variance. To answer this rigorously, we first formulate a continuous-time representation of SMD as a stochastic differential equation (SDE) driven by a centered L\'evy noise process characterized by finite $p$-th order moments, where $1 < p \leq 2$. We term this framework the L\'evy mirror flow (LMF), as it emerges naturally as the scaling limit of SMD in environments dominated by heavy-tailed disturbances.

In the heavy-noise regime, defined by $p < 2$, the trajectories of LMF typically display jump discontinuities of unbounded size. When these jumps occur with sufficient frequency, they result in infinite variance. However, we demonstrate that despite this highly singular behavior, LMF achieves $\epsilon$-optimality in $\mathcal{O}(\epsilon^{-p/(p-1)})$ time for convex problems, and in $\mathcal{\tilde O}(\epsilon^{-1/(p-1)})$ time for (relatively) strongly convex objectives. These results offer a clear characterization of how frequent long jumps influence process convergence and translate into corresponding discrete-time guarantees for various SMD variants operating under heavy-tailed noise conditions.

Source: arXiv Generated at: 2026-06-03 00:00:00 UTC