Adaptive Gradient Descent without Descent
Yura Malitsky, Konstantin Mishchenko
math.OC, cs.LG, math.NA, stat.ML
2019-10-22
Malitsky 与 Mishchenko 用两条只看梯度的规则免去步长调节,凸问题里即使全局光滑常数为无穷也能收敛,不调参就压过 GD 与 Nesterov。
梯度下降是最老的优化方法,也是现代机器学习的基石。它的更新只有一行 x{k+1} = xk − λ∇f(xk),但用起来卡在一个老问题上:步长 λ 怎么选。教科书给的上界是 λ < 2/L,其中 L 是梯度的全局 Lipschitz 常数,也叫全局光滑常数。这个 L 把人逼到两难。一方面,很多函数根本没有有限的全局 L:指数、对数、x 的 p 次方(p>2)、矩阵分解的目标函数、立方正则子问题,这些都只在局部光滑,L 算出来是无穷,标准理论直接失效。另一方面,就算 L 有限,你也得估准它,估偏一倍就可能发散,调参本身就是一笔人人要交的税。
已有的逃生路线各有代价。线搜索要额外消耗梯度求值;Adagrad、Adam 这类在线方法是给随机场景设计的;Polyak 步长效果好却需要事先知道最优值 f,实务里根本拿不到;Barzilai-Borwein 用相邻两步梯度估步长,常常很快,但没有收敛保证,换个数据集就可能爆炸。步长问题是优化里最古老的麻烦,这篇要正面解决它。
作者提出 AdGD,对梯度下降做了一处极小的改动。每步只用梯度算两个上界,取较小者当步长。第一条规则是步长别涨太快:λk² ≤ (1 + θ{k-1})λ{k-1}²,其中 θk = λk/λ{k-1}。第二条是别跨过局部曲率:λk ≤ 2‖xk − x{k-1}‖ / ‖∇f(xk) − ∇f(x{k-1})‖。
第二条里那个比值 ‖∇f(xk) − ∇f(x{k-1})‖ 除以 ‖xk − x{k-1}‖,正是割线斜率,也就是当前位置局部 Lipschitz 常数的估计。步长因此跟着你脚下的曲率走,不按全局最坏情况打折。整个过程不用函数值,不用线搜索,默认 x0=0、λ0=1e-10,不需要任何针对问题的调参。
真正反常规的是证明。标准梯度下降的收敛证明都搭在 descent lemma 上:它要求每一步函数值都下降,而这一步恰好就是需要全局 L 有限的地方。这篇扔掉了 descent lemma,改用 Cauchy-Schwarz 不等式加凸性的两步 Lyapunov 能量分析,引理同时跟踪 x{k+1}、xk、x{k-1} 三步。正因为不假设每步下降,局部光滑就够了。这是这篇给领域的最大礼物:descent lemma 一直是承重墙,它证明这堵墙可以拆掉,由此开出了「无需下降」的分析路线。
凸问题里,即便全局 L 为无穷,只要解附近局部光滑,方法就收敛,速率匹敌梯度下降的 O(1/ε)。强凸问题匹敌 O(κ log 1/ε),κ 是条件数 L/μ。随机版本 AdSGD 在强凸有限和问题上拿到 O(κ² log 1/ε),比已知最优多一个 κ,这是不为预知 L 付的代价。
| 设置 | 结果 |
| 逻辑回归(mushrooms/covtype/w8a) | 不调参就压过 GD 与 Nesterov |
| 矩阵分解(Movielens 100K,r=10/20/30) | 目标非凸且非全局光滑;GD/Nesterov 需近最优手调步长、翻倍即发散,AdGD 无需调参 |
| ResNet-18 / DenseNet-121(Cifar10) | AdSGD 在训练损失相同时测试精度高于 SGD,但前 75 个 epoch 更慢、更噪 |
| Armijo 线搜索单步成本 | 约为 AdGD 的 2 倍;Nesterov 线搜索约 4 倍 |
对照里 Barzilai-Borwein 换个数据集就发散,Polyak 步长得喂 f。在「不调参」这条上,AdGD 几乎没有对手。
步长调参是每个做优化的人都要交的税,而全局光滑假设在教科书二次型之外经常不成立。一个即插即用、不需要 L、能跑在只局部光滑问题上、还常常直接赢的梯度下降,是实打实有用的工具。更值钱的是那套证明技术:它示范了 descent lemma 这块承重墙可以被拆掉,催生了一串「无需下降」的分析。需要诚实的是,这是 2019、2020 年的凸优化结果,不是新出的 LLM 技巧;它的价值在于是一把干净的基础工具,而把它重新带回来的讨论,正好围绕这条步长规则里的常数。
作者自己点了三处。一,无非凸理论:他们不知道任何能避开 descent lemma 的通用非凸一阶方法。二,他们能证的速率只匹敌梯度下降,可实验里 AdGD 常常快得多,这个差距没人解释得了。三,扩展到带非光滑正则项的复合、近端问题并不直接。神经网络实验里早期 epoch 又慢又噪。而且「连 L=∞ 都收敛」只对凸问题成立,矩阵分解和神经网络上那些漂亮的赢面都是实验结果,没有理论保证。