🤖 machine learning

Convergence of Steepest Descent and Adam under Non-Uniform Smoothness

本文确立了在曲率是目标函数值的仿射函数这一非均匀光滑性假设下，最速下降法以及 Adam 和 RMSProp 等自适应方法，在处理诸如逻辑回归、Softmax 策略梯度以及特定神经网络等问题时，比传统的梯度下降法和其他变体能够实现可证明的更快线性收敛速率。

原作者： Sharan Vaswani, Yifan Sun, Reza Babanezhad

发布于 2026-06-01

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Sharan Vaswani, Yifan Sun, Reza Babanezhad

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图在一片广袤、多雾的山谷中寻找最低点。这个山谷代表了机器学习问题中的“损失景观”（loss landscape），你的目标是尽可能快地到达底部（即最佳解）。

长期以来，科学家们一直认为这个山谷就像一个平滑、可预测的碗。他们认为，无论你身处何处，地面的陡峭程度大致都是相同的。这使得计算出向下的最佳路径变得非常容易。

然而，这篇论文指出，现实世界的机器学习山谷要混乱得多。它们不是均匀的碗状，而是崎岖不平、高低错落的地形，其陡峭程度会随着高度的变化而剧烈波动。有时地面是平坦的，有时则是陡峭的悬崖。

作者在这篇论文中引入了一种描述这种复杂地形的新方法。他们称之为非均匀平滑性（Non-Uniform Smoothness）。他们不再说“地面总是这么陡”，而是说“地面的陡峭程度与你的高度直接相关”。如果你在高处，地面可能非常陡峭；如果你在低处，地面可能会变得平缓。

以下是他们关于如何在这种特定地形中导航的研究发现：

1. “符号”策略 vs. “全步长”策略

想象一下，你有两种下山的方式：

梯度下降 (GD)： 你观察地面，感受坡度，然后朝着那个方向迈出一大步。你的步长取决于坡度的陡峭程度。
符号梯度下降 (Sign GD)： 你忽略坡度的大小，只看方向。你只是朝着地面下降的方向迈出一个固定大小的小步。

论文表明，对于某些类型的山谷（例如逻辑回归或强化学习中发现的山谷），“符号”策略实际上更快。因为地形如此不均匀，根据坡度采取全步长可能会导致你越过目标（overshoot）或陷入停滞。通过仅仅朝着正确的方向迈出稳定的小步，你可以更高效地穿过混乱。这就像是在崎岖的小路上行走：有时候，采取稳健的小步比根据岩石看起来有多陡峭来尝试大跨步跳跃更为明智。

2. “自适应”徒步者 (RMSProp 和 Adam)

你还有另外两位徒步者：RMSProp 和 Adam。他们是“聪明”的徒步者，拥有对近期所见地形的记忆。

如果他们刚刚走过一段非常陡峭、颠簸的路段，他们会记住这一点，并在下次行走时减小步长以确保安全。
如果他们走过了一段平坦的路段，他们会记住这一点，并加大步长以提高速度。

论文证明，对于一类特定的问题（例如在可以被轻易分离的数据上训练某些两层神经网络），这些聪明的徒步者可以全程保持恒定且快速的速度直到抵达底部。他们不需要像其他方法那样大幅度减速或改变策略。他们是“在理论上比更快的”旧方法（如 AdaGrad 或 AMSGrad）更高效的，因为后者在接近底部时往往会过度减速。

3. “下界”（为什么其他方法较慢）

为了证明他们的观点，作者设置了一个特定的、简单的测试案例：一维逻辑损失（一个非常基础的数学问题）。他们展示了对于这种特定的地形：

梯度下降 (GD)、重球动量法 (Heavy-Ball Momentum)、AdaGrad 和 AMSGrad 在数学上被迫移动得非常缓慢。它们的移动速度在接近目标时会显著下降。
然而，RMSProp 和 Adam 却能保持快速的线性速度。

想象一场比赛，其他跑者都被一根绳子拴住了，随着接近终点，绳子越勒越紧，迫使他们不得不减速。而 RMSProp 和 Adam 则拥有一种特殊的机制，让他们在冲向终点的过程中始终保持全速冲刺。

“重大胜利”总结

新地图： 他们创建了一张更好的地图（ $(H_0, H_1)$ -NS 假设），描述了地面的陡峭程度如何随高度变化。这张地图比旧地图更能拟合许多现实世界的机器学习问题。
更快的徒步者： 他们证明了“符号梯度下降 (Sign GD)”以及智能自适应方法（RMSProp/Adam）是应对这种特定地图的最佳工具。
结论： 对于逻辑回归中分离数据或训练简单神经网络等问题，自适应方法（RMSProp/Adam）在理论上保证比传统方法（GD, AdaGrad）更快。

简而言之，这篇论文解释了为什么我们今天在 AI 中使用的自适应算法如此有效：它们完美地契合了我们试图攀爬的那些具有“非均匀”特征的山谷形状。

技术摘要：非均匀平滑性下最速下降法与 Adam 的收敛性

问题表述

本文研究了针对如下形式的无约束最小化问题 $\min_{\theta \in \mathbb{R}^D} f(\theta)$ 的一阶优化方法的收敛性分析。作者关注一类具有非均匀平滑性 (Non-Uniform Smoothness, NS) 和梯度支配性 (Gradient Domination)（也称为 Łojasiewicz 条件）特征的特定目标函数。

核心假设被称为 $(H_0, H_1)$ -NS，它假定 Hessian 矩阵的谱范数由目标值的仿射函数上界约束：
$\|\nabla^2 f(\theta)\|_{p \to q} \leq H_0 + H_1 f(\theta)$
其中 $H_0, H_1 \geq 0$ ，且 $p, q \geq 1$ 为对偶范数。该假设推广了先前的 NS 假设（例如 Zhang 等人，2020b），后者将 Hessian 限制在梯度范数范围内。作者认为， $(H_0, H_1)$ -NS 能更好地模拟机器学习中的损失景观，包括逻辑回归、广义线性模型、Softmax 策略梯度以及某些两层神经网络。

此外，分析假设目标函数满足非均匀 Łojasiewicz (NL) 条件，该条件通过函数次优性来下界化梯度范数：
$\|\nabla f(\theta)\|_q \geq \mu(\theta) [f(\theta) - f^*]^\tau$
该条件意味着最小化梯度范数会导致函数值的最小化，这一性质在许多凸问题和结构化非凸问题中均成立。

方法论

本文推导了三种算法类别在 $(H_0, H_1)$ -NS 和 NL 假设下的收敛保证：

归一化最速下降法 (Normalized Steepest Descent, NSD)： 包括符号梯度下降 (Sign GD)、归一化梯度下降 (Normalized Gradient Descent) 以及基于 Gauss-Southert 规则的符号坐标下降 (Sign Coordinate Descent)。
确定性对角 RMSProp： 在不进行偏差修正的情况下进行分析。
确定性对角 Adam： 在不进行偏差修正的情况下进行分析，特别是在满足 $\beta_1 \leq \beta_2$ 的条件下。

该方法论依赖于建立 $(H_0, H_1)$ -NS 函数的结构性质，例如函数和梯度范数的乘性 Lipschitz 界。这些性质使作者能够在不需要维度相关常数或全局凸性的情况下，界定目标函数的下降量。证明过程采用了两阶段分析：

第一阶段： 当次优性较大时（具体为 $f(\theta) > H_0/H_1$ ）， $H_1 f(\theta)$ 项占主导地位，允许使用恒定步长实现线性收敛。
第二阶段： 当次优性较小时（ $f(\theta) \leq H_0/H_1$ ）， $H_0$ 项占主导地位，需要更小的步长，并导致较慢的、依赖于 Łojasiewicz 指数 $\tau$ 的次线性收敛速率。

核心贡献

1. $(H_0, H_1)$ -NS 函数的结构性质
作者将现有结果从欧几里得范数推广到了任意 $(p, q)$ 算子范数。他们证明了 $(H_0, H_1)$ -NS 蕴含了函数和梯度范数的乘性 Lipschitz 界。该框架使得在不假设梯度有界或凸性的情况下分析 RMSProp 和 Adam 成为可能。

2. 归一化最速下降法 (NSD) 的收敛性
论文证明了 NSD 方法（包括 Sign GD 和 Sign CD-GS）实现了与维度无关的收敛速率。

对于 $H_0 = 0$ 的问题（例如可分逻辑回归、指数损失），NSD 使用恒定步长实现线性收敛。
对于 $H_0 > 0$ 的问题，NSD 先线性收敛至 $O(H_0/H_1)$ 邻域，随后进入较慢的阶段。
重要性： 对于可分逻辑回归和 Softmax 策略梯度，证明了 Sign GD 在恒定步长下能实现线性收敛，其表现与带有线搜索的 GD 相当，并优于恒定步长的 GD。

3. RMSProp 与 Adam 的收敛性
作者推导了在这些假设下，确定性对角变体 RMSProp 和 Adam 的首个与维度无关的线性收敛速率。

结果： 对于处理可分数据的某一类两层神经网络，RMSProp 和 Adam 在具有恒定超参数和动量参数的情况下实现线性收敛。
新颖性： 不同于以往通常需要凸性或梯度有界的著作，这些结果适用于满足特定 NS 和 NL 条件的非凸目标函数。

4. 自适应方法的区分
论文提出了一个理论下界，表明在 $(H_0, H_1)$ -NS 假设下，RMSProp 和 Adam 证明比 AdaGrad、AMSGrad、梯度下降 (GD) 和 Heavy-Ball 动量法更快。

示例： 对于一维逻辑损失，作者证明了 GD、Heavy-Ball、AdaGrad 和 AMSGrad 存在 $\Omega(1/T)$ 的次线性下界。
对比： 在相同的设置下，RMSProp 和 Adam 实现了指数（线性）收敛速率。这为 RMSProp 和 Adam 在特定机器学习任务中优于 AdaGrad 和 AMSGrad 的实际表现提供了理论依据。

结果与启示

本文的理论结果适用于几种经典的机器学习问题：

可分数据上的逻辑回归： Sign GD 和 Sign CD-GS 使用恒定步长实现线性收敛。RMSProp 和 Adam 也实现线性收敛，而 GD 证明明显较慢。
Softmax 策略梯度： NSD 方法实现了与专门为此类问题设计的算法相匹配的线性收敛速率。
两层神经网络： 对于具有特定激活函数和可分数据的网络，RMSProp 和 Adam 在恒定超参数下实现线性收敛。

重要意义

该论文声称提供了 RMS 函数下 RMSProp 和 Adam 的首个既与维度无关、又不依赖凸性或梯度有界的收敛保证。通过识别出一类自然函数，其中自适应方法 (RMSProp, Adam) 严格优于非自适应方法 (GD, Heavy-Ball) 以及其他自适应变体 (AdaGrad, AMSGrad)，这项工作为这些优化器在深度学习中的经验成功提供了理论基础。作者建议这些技术可以扩展到其他方法，如基于动量的最速下降法和 Lion，并计划在未来工作中将其推广到随机设置。