Mirror Descent 超越欧几里得稳定性：初始化敏感性的指数级分离

# 初始化敏感性的指数级分离：镜像下降超越欧几里得稳定性

来源：https://arxiv.org/html/2606.11431

## 镜像下降超越欧几里得稳定性：初始化敏感性的指数级分离

Shira Vansover-Hager  
布拉瓦特尼克计算机科学与人工智能学院，特拉维夫大学；  
\{shirav,schliserman,ofirs4\}@mail.tau.ac.il.

Ofir Schlisselberg¹  
Tomer Koren  
布拉瓦特尼克计算机科学与人工智能学院，特拉维夫大学，以及谷歌研究院；  
[email protected].

###### 摘要

镜像下降（Mirror Descent, MD）将梯度下降（Gradient Descent, GD）推广到欧几里得几何之外，并最近作为强化学习中的 KL 正则化策略优化和 LLM 后训练的透镜重新出现。这引出了一个基本鲁棒性问题，对可重复性和可靠性至关重要：MD 动力学对其输入的敏感性如何？我们关注初始化，它本身通常是一个预训练或已对齐的模型。众所周知，二次正则化的 MD（包括 GD 和马氏几何）对于凸光滑目标是稳定的。我们展示了一个鲜明对比：一旦正则化子是非二次的，MD 对初始化的敏感性可能比 GD 呈指数级更敏感，即使正则化子在欧几里得范数下是良条件的。我们给出了一个三维构造，包含一个凸光滑目标和一个强凸、光滑、良条件的正则化子，其中初始的 ε 扰动在 TT 步镜像下降（步长 η）后迅速放大到 min{polylog⁻¹(1/ε), ε e^{Ω(ηT)}}。对于单形上的规范 KL 正则化 MD，我们证明即使线性目标也能在高维或近边界区域中将初始 ε 扰动呈指数级快速放大。最后，我们证明，向锚点添加一个 Bregman 正则化项可以稳定动力学，同时基本保留优化保证，并且锚点的选择至关重要：锚定在初始化点只能部分缓解不稳定性，而锚定在一个固定点则能产生更稳定的机制。

## 1 引言

镜像下降（MD）（Nemirovski and Yudin, 1983；Beck and Teboulle, 2003）是一种基本优化范式，它根据参数空间的几何形状调整其更新。其更新通常写作 \(w_{t+1} = \arg\min_w \{\eta \langle \nabla F(w_t), w \rangle + D_R(w, w_t)\}\)，其中 \(D_R\) 是由正则化子 \(R\) 诱导的 Bregman 散度，η 是步长。该更新在惩罚根据 \(R\) 指定的几何偏离的同时，优化目标的局部线性化。著名实例包括梯度下降（Nesterov, 1998）和乘法权重更新（Littlestone and Warmuth, 1994；Freund and Schapire, 1997；Arora et al., 2012）。这些动力学的稳定性在现代机器学习中日益重要。MD 已重新成为强化学习（Schulman et al., 2015, 2017；Akkaya et al., 2019）和 LLM 后训练（Ouyang, 2022；Shao et al., 2024）中 KL 正则化策略优化的有用透镜。在此类设置中，优化通常从预训练、监督微调或以其他方式对齐的模型初始化。因此，预训练数据、随机性或检查点选择的变化会扰动初始化本身，并可能影响最终模型。这引出了一个对可重复性和可靠性至关重要的基本鲁棒性问题：在 TT 个顺序步骤后，镜像下降动力学能将初始化中的小扰动放大多少？我们通过“初始化稳定性”的视角来研究这个问题：在算法起点受到 ε 扰动的情况下，TT 步算法输出的最坏情况变化。等价地，这是算法输出作为初始化函数的局部最坏情况鲁棒性或有限时间敏感性概念。

对于欧几里得几何中的二次正则化，答案是众所周知的。该类别包括梯度下降和马氏几何，对于凸光滑目标，这些算法被证明是非常稳定的：小的初始化扰动在轨迹和最终输出中都保持小（Hardt et al., 2016）。对于非欧几里得镜像映射，所知甚少。与二次正则化情况的一个关键区别在于正则化子的条件数：如果镜像映射是病态的，一个小的原始扰动可能对应于更新所用几何中的更大位移。相反，人们可能希望均匀良条件的镜像映射表现得像二次映射一样，并保留其有利的稳定性。本文的核心发现是，这种希望是错误的：即使对于凸光滑目标，**一般的镜像下降可能比梯度下降对初始化敏感得多**。

我们在两个互补的机制中建立这一现象，将非二次几何的作用与病态的附加影响分离开来。首先，我们证明指数级不稳定性并不仅仅是病态正则化子的人为产物。在赋有通常 ℓ₂ 范数的三维欧几里得空间中，我们构造了一个凸光滑目标和一个强凸、光滑、良条件（非二次）的正则化子（均相对于该范数），其中初始化的 ε 扰动被放大因子 \(e^{Ω(ηT)}\)，直到 \(\widetilde{Θ}(1)\) 的饱和标度。即使对于保证 MD 能优化目标的步长选择，这一现象也可能发生。这意味着与二次正则化和标准梯度下降所享受的稳定性之间存在指数级分离。

其次，我们研究单形上的规范熵几何，其中 \(R(w) = \sum_i w_i \log w_i\)，\(D_R\) 是 KL 散度。该几何是经典乘法权重方法和现代策略优化及模型后训练中 KL 正则化更新的基础。这里，条件化机制更直接可见：负熵在低质量坐标附近的 ℓ₁ 几何中是高度病态的，我们证明仅此一点就能驱动即使对于线性目标也呈指数级放大。由此产生的下界在高维机制中均匀适用于所有单形初始化，也涵盖了低维中的近边界初始化。值得注意的是，这种不稳定性甚至可能出现在 MD 仍收敛到最小化子的步长范围内。我们用一个匹配的熵 MD 指数级上界，以及一个扩展到在线优化和 RL 中常见的更一般的 Legendre 正则化子（Cesa-Bianchi and Lugosi, 2006）来补充这个下界。

最后，我们提出问题：能否在不放弃 MD 的几何和通用性的情况下减轻这种不稳定性？为此，我们引入了 MD 的两种变体，通过向参考点添加一个额外的 Bregman 正则化项来稳定算法。首先，受实用设置（如 KL 正则化微调）的启发，其中优化过程从同时作为参考点的预训练模型初始化（例如 Ouyang, 2022；Shao et al., 2024），我们研究了**初始化锚定 MD**。在这种方法中，额外的正则化项由到初始化点的 Bregman 距离给出。我们证明，在良条件设置中（假设正则化子也是光滑的），该变体实现了初始化稳定性 \(O(ε + 1/\sqrt{T \log T})\) 以及优化误差 \(O(\log T/T)\)。然而，在病态设置中，由于其对初始化点处正则化子局部光滑度的依赖，该变体的保证可能变得空洞。为了克服这一点，我们引入了第二种变体，**固定锚点 MD**，其中 Bregman 正则化锚定在一个与初始化无关的固定参考点上。我们证明，即使对于病态正则化子，该方法仍然稳定，实现了 \(O(1/T)\) 的初始化稳定性，同时保留了 MD 的优化保证（最多对数因子），优化误差为 \(O(\log(T)/T)\)。这些结果将 Attia 和 Koren（2022）的正则化稳定视角从一致稳定性扩展到初始化稳定性。

综合而言，我们的结果表明，当 MD 被用作现代优化流水线的建模抽象时，初始化敏感性应被视为一个首要考虑因素。在 KL 正则化策略优化或 LLM 后训练中，起始参考模型中的微小差异可以通过仅几个顺序更新迅速放大，即使初始模型具有显著熵，这种情况也可能发生。同时，Bregman 正则化算法表明这种敏感性并非不可避免：通过在同一几何中添加额外的正则化，可以改善稳定性，同时保持优化速率（最多对数因子）。

### 1.1 贡献总结

更详细地，我们在本文中的主要贡献如下。

- • 我们证明，即使在低维、良条件的欧几里得几何中，MD 已经表现出指数级初始化敏感性。具体而言，在维度 d=3 中，相对于标准 ℓ₂ 范数，我们构造了一个凸光滑目标和一个强凸、光滑、良条件的非二次正则化子，使得 MD 具有初始化不稳定性 \(Ω\left(\min\{\operatorname{polylog}^{-1}(1/ε), ε e^{Ω(ηT)}\}\right)\)。这给出了与二次正则化的指数级分离：对于二次 MD（包括梯度下降和马氏几何），初始化扰动在整个算法轨迹中保持有界为 \(O((β/α) ε)\)。
- • 对于单形上的规范熵/KL 几何，我们给出了 MD 初始化稳定性的尖锐刻画，该稳定性同样是 ηT 的指数级。我们证明，负熵 MD 可以将 ε 扰动放大 \(Ω(\min\{1, ε e^{ηT}\})\)，即使对于线性目标也是如此。在高维机制 d ≥ 1/ε 中，该结果对所有初始化都成立；同样的结果也涵盖了低维中近边界的极端初始化。我们用一个匹配的熵 MD 指数级上界，以及一个扩展到在线优化和 RL 中核心的 Legendre 正则化子来补充它。

我们提出了两种 Bregman 正则化的 MD 变体来缓解初始化不稳定性。第一种，**初始化锚定 MD**，添加一个以初始化为中心的 Bregman 正则化项。在良条件设置中（正则化子也是光滑的），它实现了初始化稳定性 \(O(ε + 1/\sqrt{T \log T})\) 和优化误差 \(O(\log(T)/T)\)；然而，对于病态正则化子，其保证可能变得空洞。第二种变体，**固定锚点 MD**，添加一个以与初始化无关的固定参考点为中心的 Bregman 正则化项。该方法也能处理病态正则化子，实现了初始化稳定性 \(O(1/T)\)，同时保留了 MD 的收敛保证（最多对数因子），优化误差为 \(O(\log(T)/T)\)。

| 算法 | 类型 | 域 | 正则化子 | 假设 | 界 | 参考 |
|------|------|-----|----------|------|----|------|
| MD | 上界 | 凸 | 二次，κ-条件 | η ≤ α/L | \(O\left(\frac{β}{α} ε\right)\) | Hardt et al. (2016)（见定理 10） |
| MD | 下界 | 凸 | 欧几里得，κ=O(1)，非二次 | – | \(Ω\left(\min\{\operatorname{polylog}^{-1}(\frac{1}{ε}), ε e^{Ω(ηT)}\}\right)\) | 定理 1 |
| MD | 下界 | 单形 | 负熵 | d ≥ 1/ε 或 w₀ᵐⁱⁿ ≤ ε | \(Ω\left(ε e^{ηT}\right)\) | 定理 2 |
| MD | 上界 | 单形 | 负熵 | – | \(O\left(ε e^{O(ηT)}\right)\) | 定理 3 |
| 初始化锚定 MD (算法 1) | 上界 | 凸 | κ=O(1) | – | \(O\left(ε + 1/\sqrt{T \log T}\right)\) | 定理 4 |
| 固定锚点 MD (算法 2) | 上界 | 凸 | – | – | \(O(1/T)\) | 定理 6 |

**图 1：** 初始化稳定性界概览。其中 w₀ 表示初始化，w₀ᵐⁱⁿ 表示 w₀ 的最小坐标，ε 表示初始化扰动，T 为优化时域，η 为步长，L 为目标的光滑参数，α, β 为正则化子的强凸和光滑参数，κ=β/α。

### 1.2 相关工作

##### 镜像下降和非欧几里得优化。
镜像下降几十年来一直是优化和在线学习的核心；例如，参见 Shalev-Shwartz (2025)；Bubeck (2015)；Hazan (2016)；Beck (2017) 的教科和综述处理。最近的工作继续完善其优化和遗憾保证，包括用于相对光滑目标的随机 MD (D’Orazio et al., 2021) 和带有近似更新的在线 MD (Schlisselberg et al., 2025)。其他工作研究 MD 的隐式偏差：在随机过参数化问题中，Azizan et al. (2021) 证明 MD 收敛到在 Bregman 散度下最接近初始化的全局最小化子，而 Sun et al. (2022, 2023) 刻画了其在线性可分分类中的最大间隔偏差。我们的关注点不同：我们研究 MD 对其初始化扰动的动力学敏感性。