Bregman meets Lévy: Stochastic Mirror Descent with Heavy-Tailed Noise in Continuous and Discrete Time¶

会议: ICML 2026
arXiv: 2606.03769
代码: 无
领域: optimization
关键词: 重尾噪声, 随机镜像下降, Lévy过程, 收敛率, 凸优化

一句话总结¶

本文提出 Lévy Mirror Flow（LMF）——一种由 Lévy 噪声驱动的随机镜像下降连续时间 SDE 模型，证明即使在无穷方差的重尾梯度噪声下，SMD 仍保持收敛保证（凸情形 \(O(\varepsilon^{-p/(p-1)})\)，强凸情形 \(\tilde{O}(\varepsilon^{-1/(p-1)})\)），并将连续时间结果无缝传递到离散时间算法。

研究背景与动机¶

领域现状：随机镜像下降（SMD）及其变体是凸随机优化中最经典的一阶方法之一，核心思想是用非欧几何的 Bregman 散度替代欧氏投影，从而在约束优化中获得接近维度无关的收敛保证。现有理论分析几乎全部建立在梯度噪声轻尾（有限方差）的假设之上。

现有痛点：大量实证表明，深度神经网络训练中的梯度噪声呈重尾分布（\(\alpha\)-稳定分布），从 CNN 到 LLM 再到强化学习均有报道。当梯度噪声方差为无穷大时，标准 SGD 甚至在一维二次函数上就可能发散。现有连续时间分析（随机镜像流 SMF）仅处理布朗噪声驱动的扩散 SDE，其轨迹连续且增量高斯，完全无法刻画重尾场景下的"大跳跃"行为。

核心矛盾：重尾噪声导致的无穷方差使得经典 Itô 公式（依赖二阶矩有限）失效，且 Fenchel 耦合函数仅 Lipschitz 光滑而非 \(C^2\)，标准随机分析工具链断裂。

本文目标：建立一个从连续时间到离散时间的统一理论框架，严格证明 SMD 在重尾噪声下的收敛性、集中性与首达时间保证。

切入角度：将 SMD 的噪声源从布朗运动替换为中心化 Lévy 过程（\(p\) 阶矩有限，\(1 < p \le 2\)），由此产生的 SDE 自然允许无穷方差和任意大小的跳跃不连续，更忠实地描述重尾训练动态。

核心 idea：用 Lévy 噪声驱动的镜像流（LMF）作为重尾 SMD 的连续时间代理模型，开发新的弱 Itô 公式处理非 \(C^2\) 凸函数，建立透明的收敛率表征后向离散时间传递。

方法详解¶

整体框架¶

输入为凸优化问题 \(\min_{x \in X} f(x)\)，其中 \(X\) 为紧凸集。优化器通过黑箱梯度预言机获取随机梯度 \(g_t = \nabla f(x_t) + U_t\)，噪声 \(U_t\) 仅有 \(p\) 阶矩有限（\(1 < p \le 2\)），方差可为无穷。方法分两层展开：(1) 连续时间层定义 LMF 并建立收敛/集中/首达时间理论；(2) 离散时间层分析 SDA、LMD、SMD 三种 SMD 变体，证明离散界可分解为"连续时间项 + 离散化项"。

关键设计¶

Lévy Mirror Flow (LMF):
- 功能：提供重尾噪声下 SMD 的连续时间理论模型
- 核心思路：将经典随机镜像流的布朗噪声替换为 Lévy 过程 \(L(t)\)，定义对偶空间 SDE \(dY(t) = -\nabla f(X(t))dt + dL(t)\)，原始迭代 \(X(t) = Q(\eta(t)Y(t))\)。Lévy 过程由 Lévy-Itô 分解为三部分：扩散分量 \(M(t)\)（布朗）、短跳分量 \(S(t)\)（有界跳跃）和无界跳分量 \(U(t)\)（\(p\) 阶矩有限但方差可无穷）。噪声强度被拆解为 \(\sigma^2_{\text{tame}} = \sigma^2_0 + \sigma^2_{\text{short}}\) 和 \(\sigma^p_{\text{heavy}} = \sigma^p_{\text{long}}\)，从而在收敛率中清晰呈现轻尾与重尾部分的独立贡献
- 设计动机：布朗驱动的 SMF 轨迹连续且增量高斯，无法刻画重尾噪声的"大跳跃"行为。LMF 自然作为 SMD 在重尾噪声下的缩放极限出现，能同时处理无穷方差和任意大跳跃
弱 Itô 公式（Weak Itô Formula）:
- 功能：为非 \(C^2\) 的凸函数建立适用于 Lévy 驱动过程的随机微积分链式法则
- 核心思路：经典 Itô 引理要求函数二阶连续可微，但 Fenchel 耦合 \(F(q,y) = h(q) + h^*(y) - \langle y, q \rangle\) 仅为 Lipschitz 光滑。作者先对 \(F\) 做磨光（mollification），再推导只以不等式形式成立的弱 Itô 公式，处理 Lévy 跳跃带来的二阶跳跃项时利用噪声的 \(p\) 阶矩有限性而非二阶矩来控制无界跳跃
- 设计动机：这是整个分析的技术核心——没有该工具，Lévy 跳跃项无法在能量函数 \(E(t) = F(q, \eta(t)Y(t))/\eta(t)\) 的演化中被控制。据作者所知，该结果在随机分析文献中是全新的
连续—离散统一分析框架:
- 功能：将连续时间收敛保证无缝传递到离散时间算法
- 核心思路：对离散时间的 SDA（Stochastic Dual Averaging）、LMD（Lazy Mirror Descent）和 SMD 三种变体，在相对光滑性 \(f(x') \le f(x) + \langle \nabla f(x), x'-x\rangle + LD(x',x)\) 假设下建立收敛率。所有离散界均可分解为"连续时间项 + \([f(x_1) - \min f]\) 离散化项"，后者随迭代自然消失
- 设计动机：相对光滑性与 Bregman 几何天然兼容，可处理梯度在约束集边界处发散的情况（如 Poisson 逆问题、熵正则最优传输），而标准 Lipschitz 光滑性不适用

实验关键数据¶

主要理论结果对比¶

设定	算法	收敛率	备注
凸 + 连续时间	LMF, \(\eta(t) = 1/t^{1/p}\)	\(O(1/t^{(p-1)/p})\)	\(p=2\) 退化为经典 \(O(1/\sqrt{t})\)
凸 + 离散时间	SDA, \(\eta_t = \beta/t^{1/p}\)	\(O(1/T^{(p-1)/p})\)	与连续时间速率匹配
强凸 + 连续时间	LMF, 常数 \(\eta\)	几何收敛至 \(O(\delta^2_\eta)\) 球	\(\delta^2_\eta\) 随 \(\eta\) 和噪声强度缩放
强凸 + 离散时间	SDA, 常数 \(\eta\)	\(\tilde{O}(\varepsilon^{-1/(p-1)})\) 达 \(\varepsilon\)-最优	比遍历率 \(O(\varepsilon^{-p/(p-1)})\) 更优
强凸相对 + 离散	LMD, \(\gamma_t = \beta/t\)	\(O(1/t^{p-1})\)（\(p < 1+\beta\mu\)）	分三段依 \(p\) 与 \(\beta\mu\) 关系而变

理论保证类型对比¶

保证类型	连续时间定理	离散时间定理	关键量
遍历收敛	Theorem 1	Theorem 5	时间平均 \(\bar{X}(t)\)
集中不等式	Theorem 2	Theorem 7	停留时间占比 \(\mu_T(B_\delta)\)
首达时间	Theorem 3	Theorem 8	\(\tau_\delta = \inf\{t: \\|X(t)-x^*\\| \le \delta\}\)
末迭代收敛	Theorem 4	Theorem 6/9	\(E[\\|x_t - x^*\\|^2]\)

关键发现¶

重尾噪声使收敛率从 \(O(1/\sqrt{t})\) 退化为 \(O(1/t^{(p-1)/p})\)，退化程度随 \(p\) 平滑变化，且完全由长跳项 \(\sigma^p_{\text{heavy}}\) 控制
尽管 LMF 轨迹有任意大的跳跃不连续和无穷方差，SMD 仍保持收敛——Bregman 结构的约束机制有效"吸收"了长跳
离散时间界与连续时间界的定量匹配验证了 LMF 作为重尾 SMD 代理模型的忠实性
数值实验在简单二维强凸函数上验证了 \(f(\bar{x}_T)\) 按幂律衰减，重尾（\(\alpha = p = 3/2\)）比轻尾（\(\alpha = p = 2\)）收敛更慢但仍收敛

亮点与洞察¶

弱 Itô 公式的通用性：该工具不仅服务于本文，对任何需要分析 Lévy 驱动优化的后续工作都有直接价值——它将 Itô 随机微积分的链式法则从 \(C^2\) 函数 + 布朗运动推广到 Lipschitz 凸函数 + Lévy 过程
噪声解耦设计：将 Lévy 噪声拆分为 \(\sigma_{\text{tame}}\)（轻尾）和 \(\sigma_{\text{heavy}}\)（重尾）两部分，使收敛率中能独立追踪各噪声源的贡献，这种"诊断式"分析思路可迁移到自适应优化器设计中（如根据噪声尾部指数 \(p\) 自动调节学习率 \(\eta \propto 1/t^{1/p}\)）
连续到离散的"加法分解"：所有离散界 = 连续时间项 + 离散化项，提供了一种系统化的分析范式——先在连续时间中建立干净的收敛保证，再处理离散化误差

局限与展望¶

强凸情形的离散时间率 \(\tilde{O}(\varepsilon^{-1/(p-1)})\) 未匹配 Zhang et al. 的下界 \(\Omega(\varepsilon^{-p/[2(p-1)]})\)，作者猜测通过更换能量函数可以改进
理论假设要求约束集 \(X\) 紧凸，且需要梯度预言机的噪声满足鞅差条件和 \(p\) 阶矩有限——对无约束或开集优化不直接适用
数值实验仅在简单二维函数上验证，缺少深度学习实际训练的大规模实证
未探索 LMF 在采样问题（如约束空间上的 Langevin 动力学）中的应用潜力