平坦最小值下固定步长SGD的缩放极限

# 恒定步长SGD在平坦最小值处的缩放极限 来源：https://arxiv.org/html/2607.16384 ###### 摘要 对于采用恒定步长\(\alpha\)的随机梯度下降\(SGD\)，以最小化器为中心的迭代不变分布描述了算法在长时间尺度上的行为。在强凸情况下，该不变分布具有熟悉的\(\sqrt{\alpha}\)缩放和当\(\alpha\downarrow 0\)时的高斯极限。我们证明，对于具有平坦最小值和(次)二次尾部的凸目标函数\(H\)，这种行为会发生根本变化。更具体地说，我们研究了由收缩驱动链生成的马尔可夫噪声下的SGD。对于每个足够小的恒定步长\(\alpha\)，我们证明了在由\(\alpha\)依赖度量诱导的Wasserstein距离下，存在、唯一且几何收敛到一个增广不变分布。当最小化器\(x_\star\)具有局部平坦指数\(m \ge 2\)，即当\(x \to x_\star\)时，\(\nabla^2 H(x) \asymp \|x - x_\star\|^{m-2} I_d\)，我们得到收缩界，因子为\(1 - c \alpha^{m-1}\)，其中\(c > 0\)为常数。这恢复了二次情况(\(m=2\))下的因子\(1 - c\alpha\)。然后我们分析小步长缩放极限。我们证明了不变分布集中在尺度\(\alpha^{1/m}\)上，并且缩放后的迭代弱收敛到随机微分方程\(dY_t = -h_0(Y_t) dt + \Sigma^{1/2} dB_t\)的平稳分布，其中\(h_0\)是最小化器处的极限漂移，\(\Sigma\)表示渐近协方差。这恢复了\(m=2\)时的高斯极限，并在平坦情况(\(m>2\))下通常给出非高斯的平稳极限。最后，我们给出了坐标可分离且具有不等平坦指数的目标的相应结果。††1佐治亚理工学院，*电子邮件：*[email protected] (https://arxiv.org/html/2607.16384v1/mailto:[email protected])††2佐治亚理工学院，*电子邮件：*[email protected] (https://arxiv.org/html/2607.16384v1/mailto:[email protected])††3佐治亚理工学院，*电子邮件：*[email protected] (https://arxiv.org/html/2607.16384v1/mailto:[email protected])###### 目录 1. 1引言 (https://arxiv.org/html/2607.16384#S1) 2. 2主要结果 (https://arxiv.org/html/2607.16384#S2)1. 2.1 Wasserstein距离下的几何遍历性 (https://arxiv.org/html/2607.16384#S2.SS1) 2. 2.2 小步长缩放极限 (https://arxiv.org/html/2607.16384#S2.SS2) 3. 2.3 坐标可分离目标 (https://arxiv.org/html/2607.16384#S2.SS3) 3. 3应用与数值实验 (https://arxiv.org/html/2607.16384#S3)1. 3.1 分位数和尾部风险估计中的局部平坦性 (https://arxiv.org/html/2607.16384#S3.SS1) 2. 3.2 鲁棒损失和逻辑损失下的次二次尾部 (https://arxiv.org/html/2607.16384#S3.SS2) 4. 4主要结果的证明 (https://arxiv.org/html/2607.16384#S4)1. 4.1 恒定步长SGD的分析 (https://arxiv.org/html/2607.16384#S4.SS1) 2. 4.2 缩放极限的分析 (https://arxiv.org/html/2607.16384#S4.SS2) 5. 5结论 (https://arxiv.org/html/2607.16384#S5) 6. A恒定步长收缩 (https://arxiv.org/html/2607.16384#A1)1. A.1 不动点原理 (https://arxiv.org/html/2607.16384#A1.SS1) 2. A.2 引理4.2的证明 (https://arxiv.org/html/2607.16384#A1.SS2) 3. A.3 预备估计 (https://arxiv.org/html/2607.16384#A1.SS3) 4. A.4 引理4.3的证明 (https://arxiv.org/html/2607.16384#A1.SS4) 5. A.5 引理4.4的证明 (https://arxiv.org/html/2607.16384#A1.SS5) 6. A.6 引理4.5的证明 (https://arxiv.org/html/2607.16384#A1.SS6) 7. A.7 推论2.9的证明 (https://arxiv.org/html/2607.16384#A1.SS7) 7. B缩放极限估计 (https://arxiv.org/html/2607.16384#A2)1. B.1 确定性缩放估计 (https://arxiv.org/html/2607.16384#A2.SS1) 2. B.2 驱动链遍历性和泊松方程 (https://arxiv.org/html/2607.16384#A2.SS2) 3. B.3 引理4.6的证明 (https://arxiv.org/html/2607.16384#A2.SS3) 4. B.4 引理4.7的证明 (https://arxiv.org/html/2607.16384#A2.SS4) 5. B.5 引理4.8的证明 (https://arxiv.org/html/2607.16384#A2.SS5) 6. B.6 引理4.9的证明 (https://arxiv.org/html/2607.16384#A2.SS6) 7. B.7 引理4.10的证明 (https://arxiv.org/html/2607.16384#A2.SS7) 8. C可分离扩展 (https://arxiv.org/html/2607.16384#A3)1. C.1 推论2.15的证明 (https://arxiv.org/html/2607.16384#A3.SS1) 2. C.2 推论2.17的证明 (https://arxiv.org/html/2607.16384#A3.SS2) 3. C.3 注记2.18的证明 (https://arxiv.org/html/2607.16384#A3.SS3) 9. 参考文献 (https://arxiv.org/html/2607.16384#bib) ## 1引言 随机逼近起源于基于噪声观测的递归寻根和优化方法[40 (https://arxiv.org/html/2607.16384#bib.bib40),24 (https://arxiv.org/html/2607.16384#bib.bib24),7 (https://arxiv.org/html/2607.16384#bib.bib7),27 (https://arxiv.org/html/2607.16384#bib.bib27),9 (https://arxiv.org/html/2607.16384#bib.bib9)]。经典理论使用递减步长并研究到目标点的几乎必然收敛。相比之下，在大规模优化中，通常长时间使用恒定或分段恒定步长。采用恒定步长和非退化梯度噪声时，最后的随机迭代通常不会收敛到最小化器。因此，研究算法生成的马尔可夫链的不变分布是自然的，它描述了最后迭代的平稳误差。对于光滑强凸目标，SGD的平稳误差已有很好的理解。它通常为\(\sqrt{\alpha}\)量级，并且经过\(\alpha^{-1/2}\)重缩放后，不变分布收敛到Ornstein–Uhlenbeck扩散的平稳分布，因此是高斯分布。这种图像出现在小步长渐近律[37 (https://arxiv.org/html/2607.16384#bib.bib37)]、恒定步长SGD的扩散近似[29 (https://arxiv.org/html/2607.16384#bib.bib29)]以及SGD类算法的平稳小步长刻画[12 (https://arxiv.org/html/2607.16384#bib.bib12)]中。补充的马尔可夫链分析在强凸背景下建立了不变测度展开、收敛和集中性[13 (https://arxiv.org/html/2607.16384#bib.bib13),30 (https://arxiv.org/html/2607.16384#bib.bib30)]。然而，二次情况并不代表所有凸目标。当确定性漂移在最小化器处以高于一阶的阶数消失时，不变分布的归一化及其缩放极限都会改变。本文研究的最小化器可能比二次情况更平坦的凸目标。在最小化器附近，确定性漂移可能满足\(\nabla^2 H(x) \asymp \|x\|^{m-2} I_d\)，\(m \ge 2\)，在维度\(d\)中，因此恢复力为\(\|x\|^{m-1}\)量级。同时，目标函数可能具有次二次尾部：对于\(1 \le \beta < 2\)，大\(\|x\|\)时的漂移可能仅增长为\(\|x\|^{\beta-1}\)。这些特征出现在标准统计目标中。当分布函数在目标概率水平处以更高阶穿越时，分位数估计提供了局部平坦性的典型例子。对于中位数和\(L_1\)回归，这种非正则局部行为由Knight[25 (https://arxiv.org/html/2607.16384#bib.bib25)]研究；他们的正则变化机制适用于由Koenker和Bassett[26 (https://arxiv.org/html/2607.16384#bib.bib26)]引入的一般分位数损失。同样的局部几何结构出现在条件风险价值(CVaR)的Rockafellar–Uryasev变分表示[41 (https://arxiv.org/html/2607.16384#bib.bib41)]中。次二次尾部出现在具有有界或次线性分数的鲁棒损失中，例如Huber型和广义Charbonnier损失[19 (https://arxiv.org/html/2607.16384#bib.bib19),11 (https://arxiv.org/html/2607.16384#bib.bib11),4 (https://arxiv.org/html/2607.16384#bib.bib4)]，以及逻辑损失[5 (https://arxiv.org/html/2607.16384#bib.bib5)]中。近期关于次二次SGD的工作处理了\(m=2\)且\(\beta<2\)的局部强凸情况[47 (https://arxiv.org/html/2607.16384#bib.bib47)]；\(m>2\)的情况需要不同的局部尺度和不同的收缩论证。我们强调整篇文章中使用的两个关键指数扮演的不同角色：局部平坦指数\(m\)决定了最小化器附近恢复漂移的阶数，因此决定了平稳缩放。尾部指数\(\beta\)决定了大\(\|x\|\)时的漂移以及控制游荡所需的权重函数。此外，我们考虑带马尔可夫噪声的SGD。一个驱动马尔可夫链\((\xi_n)_{n \ge 0}\)根据收缩递归演化，SGD迭代遵循\(X_{n+1}=X_n - \alpha\{h(X_n) + g(X_n, \xi_{n+1})\}\)，\(h=\nabla H\)。增广过程\((X_n, \xi_n)\)是马尔可夫的。这种表述不仅涵盖了具有独立同分布噪声的统计设置，也涵盖了时间相关数据流。 #### 挑战与主要贡献。在上述背景下分析SGD存在三个困难。首先，当\(m>2\)时，普通欧几里得收缩在最小化器附近退化，而这正是当\(\alpha \downarrow 0\)时不变分布集中的区域。其次，对于\(\beta < 2\)，二次Lyapunov函数与大\(\|x\|\)时的漂移不匹配。第三，在马尔可夫噪声下，当前迭代与驱动链的未来值相关，这阻止了直接的单步鞅论证。我们下面的主要结果解决了这些挑战。首先，对于小固定步长\(\alpha\)下SGD的收敛性，我们证明SGD迭代在适当选择的Wasserstein距离下以几何速度收敛到唯一的不变分布，收缩因子为\(1 - c \alpha^{m-1}\)，其中\(c > 0\)为常数。证明使用了Qu、Blanchet和Glynn[39 (https://arxiv.org/html/2607.16384#bib.bib39)]的度量，该度量由我们精心构造的Lyapunov权重函数\(V_\alpha\)诱导。权重函数包含两项，一项用于控制目标的次二次尾部，另一项用于控制近最小化器区域。此外，直接应用[39 (https://arxiv.org/html/2607.16384#bib.bib39)]的结果在我们的情况中不起作用，我们用一个新论证证明了SGD迭代的收缩。其次，在获得固定\(\alpha\)的不变分布后，我们随后确定其当\(\alpha \downarrow 0\)时的缩放极限。局部\(m\)阶平坦几何决定了归一化：SGD迭代集中在尺度\(\alpha^{1/m}\)上。然后，缩放极限由随机微分方程\(dY_t = -h_0(Y_t) dt + \Sigma^{1/2} dB_t\)的平稳分布给出，其中\(h_0\)表示极限漂移，\(\Sigma\)表示通过泊松方程论证确定的渐近方差。当\(m=2\)时，上述方程恢复为Ornstein–Uhlenbeck扩散，不变分布是高斯分布。当\(m>2\)时，漂移\(h_0\)是非线性的，平稳分布通常是非高斯的。我们注意到，Chen、Mou和Maguluri[12 (https://arxiv.org/html/2607.16384#bib.bib12)]数值上展示了非高斯四次缩放。Wang等人[43 (https://arxiv.org/html/2607.16384#bib.bib43)，第5节]猜想了一维平坦最小值的Gibbs近似具有相应的非标准缩放，并数值支持了它。我们的结果严格建立了多维设置中带马尔可夫噪声的缩放极限，确认并扩展了先前工作提示的现象。最后，对于坐标可分离的目标函数，我们提供了相应的恒定步长和缩放极限结果。值得注意的是，如果坐标具有不相等的局部平坦指数，则在与最大指数相关的公共尺度下，只有最平坦的坐标可以保持非零。表1 (https://arxiv.org/html/2607.16384#S1.T1)总结了主要结果中出现的情况。 表 1：主要结果所涵盖的主要特征。指数\(m\)是局部的，决定了不变分布的归一化和极限漂移\(h_0\)。指数\(\beta\)是全局的，决定了诱导度量的尾部部分。 #### 相关文献。经典的随机逼近文献研究递减步长和迭代平均，建立了几乎必然收敛和渐近正态性[40 (https://arxiv.org/html/2607.16384#bib.bib40),24 (https://arxiv.org/html/2607.16384#bib.bib24),16 (https://arxiv.org/html/2607.16384#bib.bib16),28 (https://arxiv.org/html/2607.16384#bib.bib28),42 (https://arxiv.org/html/2607.16384#bib.bib42),38 (https://arxiv.org/html/2607.16384#bib.bib38),7 (https://arxiv.org/html/2607.16384#bib.bib7),27 (https://arxiv.org/html/2607.16384#bib.bib27),9 (https://arxiv.org/html/2607.16384#bib.bib9)]。现代递减步长随机优化的非渐近分析包括[33 (https://arxiv.org/html/2607.16384#bib.bib33),32 (https://arxiv.org/html/2607.16384#bib.bib32),2 (https://arxiv.org/html/2607.16384#bib.bib2)]。这些结果涉及迭代收敛到优化器。这里的目标不同：对于恒定步长，最后迭代具有非平凡的不变分布，并且极限\(\alpha \downarrow 0\)是在平稳状态下取的。对于恒定步长，该算法被分析为马尔可夫链。Pflug[37 (https://arxiv.org/html/2607.16384#bib.bib37)]研究了随机优化的小步长渐近律。Mandt、Hoffman和Blei[29 (https://arxiv.org/html/2607.16384#bib.bib29)]发展了恒定步长SGD的二次扩散近似。Dieuleveut、Durmus和Bach[13 (https://arxiv.org/html/2607.16384#bib.bib13)]发展了光滑强凸SGD的不变测度和偏差展开。Merad和Gaïffas[30 (https://arxiv.org/html/2607.16384#bib.bib30)]在相关的强凸背景下证明了Wasserstein收敛和集中性。在不同的渐近机制中，Yu、Balasubramanian、Volgushev和Erdogdu[45 (https://arxiv.org/html/2607.16384#bib.bib45)]建立了固定步长下迭代平均的中心极限定理，以及对不变偏差的刻画。除了Pflug[37 (https://arxiv.org/html/2607.16384#bib.bib37)]的经典工作外，与我们不变分布的缩放极限最密切相关的近期工作是Chen、Mou和Maguluri[12 (https://arxiv.org/html/2607.16384#bib.bib12)]、Zhang等人[46 (https://arxiv.org/html/2607.16384#bib.bib46)]和Wang等人[43 (https://arxiv.org/html/2607.16384#bib.bib43)]。Pflug[37 (https://arxiv.org/html/2607.16384#bib.bib37)]和Chen、Mou和Maguluri[12 (https://arxiv.org/html/2607.16384#bib.bib12)]都首先过渡到恒定步长不变分布，然后令\(\alpha \downarrow 0\)以获得高斯极限。后一工作在光滑强凸、线性和收缩背景下获得了高斯极限，并数值展示了四次目标函数的\(\alpha^{1/4}\)缩放和非高斯极限。Zhang等人[46 (https://arxiv.org/html/2607.16384#bib.bib46)]建立了非光滑收缩随