研究随机梯度下降在重尾噪声下的鲁棒性，发现其仍可保证收敛。
Bregman meets Lévy: Stochastic mirror descent with heavy-tailed noise in continuous and discrete time
- 用莱维过程建模重尾噪声下的连续镜像下降流
- 在凸目标下收敛时间与噪声阶数呈幂律关系，$\mathcal{O}(ε^{-p/(p-1)})$
- 适用于高噪声场景，适合优化理论和鲁棒学习研究者
我们研究了在重尾噪声下随机镜像下降（SMD）的鲁棒性，关注当输入为无限方差随机梯度时方法是否仍保持收敛性。为此，我们引入一个连续时间模型——由具有有限 $p$ 阶矩（$1 < p \≤ 2$）的中心化莱维噪声驱动的随机微分方程（SDE），称为莱维镜像流（LMF）。该模型自然作为重尾噪声下 SMD 的标度极限。当 $p < 2$（即重尾噪声情形）时，LMF 轨迹通常出现任意幅度的跳跃间断，若频繁则导致无限方差。尽管行为高度奇异，我们仍证明：在凸目标下，LMF 在 $\mathcal{O}(ε^{-p/(p-1)})$ 时间内达到 $ε$-最优；对于（相对）强凸目标，收敛时间为 $\mathcal{\tilde O}(ε^{-1/(p-1)})$。这些结果清晰刻画了频繁长跳对收敛的影响，并传递到多种 SMD 变体在重尾噪声下的匹配离散时间保证。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。