Technical Summary: Bregman Meets Lévy: Stochastic Mirror Descent with Heavy-Tailed Noise

1. Problem Statement

The paper investigates the robustness of Stochastic Mirror Descent (SMD) and its variants when subjected to heavy-tailed noise with infinite variance. Standard convergence analyses for SMD typically assume "tame" noise (finite variance, light-tailed, often Gaussian). However, empirical evidence in deep learning, reinforcement learning, and large language models suggests that gradient noise often follows heavy-tailed distributions (e.g., $\alpha$-stable distributions), leading to infinite variance.

The core challenge is that standard stochastic calculus tools, particularly Itô's formula, rely on the continuity of sample paths and finite second moments. When noise is heavy-tailed ($p < 2$), the resulting stochastic processes exhibit jump discontinuities of arbitrary magnitude and infinite variance, rendering classical diffusion-based analyses inapplicable. The authors ask: Does SMD retain convergence guarantees under such singular, heavy-noise regimes?

2. Methodology

Continuous-Time Modeling: The Lévy Mirror Flow (LMF)

To address the problem in a principled manner, the authors introduce a continuous-time model called the Lévy Mirror Flow (LMF). This is a Stochastic Differential Equation (SDE) formulation of SMD driven by a centered Lévy noise process $L(t)$ with finite $p$-th order moments ($1 < p \le 2$).

The LMF is defined as:
$$\begin{aligned} dY(t) &= -\nabla f(X(t)) dt + dL(t) \\ X(t) &= Q(\eta(t)Y(t)) \end{aligned}$$
where $Q$ is the mirror map induced by a Bregman regularizer $h$, and $\eta(t)$ is the learning rate.

Unlike standard Stochastic Mirror Flows (SMF) driven by Brownian motion (which have continuous paths and finite variance), the LMF under Lévy noise exhibits:

1. Heavy-tailed increments: Non-Gaussian noise.
2. Infinite variance: Possible when $p < 2$.
3. Jump discontinuities: Sample paths are càdlàg (right-continuous with left limits) and can exhibit jumps of arbitrary magnitude.

The Lévy process $L(t)$ is decomposed via the Lévy-Itô decomposition into:

• A diffusion component (Brownian motion).
• A short-jump component (bounded jumps).
• A long-jump component (unbounded jumps), which drives the heavy-tailed behavior.

Discrete-Time Analysis

The authors analyze discrete-time variants of SMD, specifically Stochastic Dual Averaging (SDA) and Lazy Mirror Descent (LMD), under the same heavy-tailed assumptions. They establish a correspondence between the discrete algorithms and the continuous LMF, showing that discrete bounds decompose into a continuous-time term plus a discretization error.

Technical Innovation: Weak Itô Formula

A primary technical hurdle is that the Fenchel coupling (the energy function used to analyze mirror descent) is generally Lipschitz continuous but not $C^2$ smooth. Standard Itô's formula requires $C^2$ smoothness. Furthermore, the presence of unbounded jumps prevents the use of standard estimates based on quadratic variations.

To overcome this, the authors derive a weak Itô formula for convex, $L$-smooth functions relative to general Lévy-type integrators. This tool allows them to bound the evolution of the energy function despite the lack of $C^2$ regularity and the presence of infinite-variance jumps.

3. Key Contributions and Results

A. Continuous-Time Convergence (LMF)

The paper establishes convergence rates for the time-averaged process $\bar{X}(t)$ under the LMF:

1. Convex Case:

   • The time-averaged process attains an $\epsilon$-approximate solution within time $O(\epsilon^{-p/(p-1)})$.
   • The convergence rate deteriorates smoothly as $p$ decreases from 2 (tame) to 1 (heavy).
   • The bound explicitly separates the contribution of "tame" noise (diffusion/short jumps) and "heavy" noise (long jumps).

2. Strongly Convex Case:

   • Concentration: The iterates concentrate within an "uncertainty ball" of radius $\delta_\eta$ around the optimum. The fraction of time spent outside this ball scales as $O(\delta_\eta^2/\delta^2)$.
   • Hitting Time: The expected time to reach a $\delta$-neighborhood of the optimum is $O(\delta^{-2p/(p-1)})$ in the heavy-noise regime.
   • Last-Iterate Convergence: Under relative strong convexity (with respect to the Bregman function $h$), the iterates converge to the optimum in mean square at a geometric rate to the uncertainty ball, and the last iterate achieves $\epsilon$-optimality in $\tilde{O}(\epsilon^{-1/(p-1)})$ time.

B. Discrete-Time Convergence (SDA/LMD)

The authors translate these continuous results to the discrete setting:

• Ergodic Convergence: For relatively smooth convex functions, SDA achieves an $\tilde{O}(\epsilon^{-p/(p-1)})$ ergodic convergence rate, matching the continuous-time bounds.
• Strongly Convex Case: For functions strongly convex relative to $h$, SDA converges in mean square to an uncertainty ball. The last-iterate complexity is $\tilde{O}(\epsilon^{-1/(p-1)})$.
• Discretization Gap: The discrete-time bounds consist of the continuous-time guarantee plus a term stemming from the discretization step, confirming the LMF as a faithful proxy for the discrete algorithm.

C. Comparison with Existing Literature

• The results generalize previous bounds for SMD under "uniform smoothness" (Nemirovski & Yudin) to the heavy-tailed regime.
• The paper notes that while the derived rates for strongly convex functions ($\tilde{O}(\epsilon^{-1/(p-1)})$) are sharper than ergodic rates, they do not match the lower bounds of Zhang et al. [117] ($\Omega(\epsilon^{-p/[2(p-1)]})$). The authors attribute this discrepancy to the difference in problem settings: their analysis assumes relative strong convexity over a bounded domain where gradients may be unbounded (due to steep regularizers), whereas the lower bounds in [117] assume bounded gradients.

4. Significance and Claims

The paper claims the following significance:

1. Robustness of SMD: Stochastic Mirror Descent remains remarkably robust under heavy-tailed noise. Despite the presence of infinite-variance jumps, the method retains convergence guarantees, though the rates depend explicitly on the tail index $p$.
2. Faithful Proxy: The proposed Lévy Mirror Flow (LMF) serves as a faithful continuous-time proxy for studying SMD in the heavy-noise regime. The qualitative and quantitative agreement between continuous and discrete results validates the use of Lévy SDEs to model and analyze heavy-noise optimization.
3. New Analytical Tools: The derivation of a weak Itô formula for non-$C^2$ convex functions under Lévy noise is a novel contribution to stochastic analysis, enabling the analysis of optimization dynamics where standard Itô calculus fails.
4. Geometric Insight: The results highlight the importance of relative strong convexity and relative smoothness (with respect to the Bregman regularizer) in handling heavy noise, particularly when the regularizer is "steep" (e.g., entropy on the probability simplex), causing gradients to blow up at the boundary.

The authors conclude that their work opens new directions for research, including tightening the convergence rates for relative strong convexity and applying the LMF framework to sampling from constrained spaces.