通过长步长可证明更快的梯度下降算法
使用常数步长的梯度下降算法应用于线性可分数据的逻辑回归,证明了在初始震荡阶段后,算法能够在 a 步的时间内实现 O (1/(aT)) 的收敛速率,从而在总步数为 T 的情况下,通过积极地调整步长可以达到 O (1/T^2) 的加速损失,无需使用动量或变化的步长调度器。
Feb, 2024
通过研究广义 AdaGrad 步长在凸和非凸设置中,本文证明了这些步长实现梯度渐近收敛于零的充分条件,从而填补了这些方法理论上的空白。此外,本文表明这些步长允许自动适应随机梯度噪声级别在凸和非凸情况下,实现 O(1/T)到 O(1 / 根号 T)的插值(带有对数项)。
May, 2018
通过改变步长序列,可以加速原始的梯度下降方法,并导致不断增大的误差,因此我们提出了一个问题:是否存在可以在任意停止时间下加速经典的 $\mathcal {O}(1/T)$ 收敛速度的梯度下降步长安排?
Jun, 2024
使用随机梯度下降来最小化 Lipschitz 函数和强凸函数但不一定可微的问题,证明了在 T 步随机梯度下降后,最终迭代的误差高概率为 O (log (T)/T);同时构造了一个函数,证明了在确定性梯度下降中,最终迭代的误差为 Ω(log (T)/T);然后证明了在采用后缀平均法的情形下,它的高概率误差界是优化函数相关类别中的最优界(O (1/T));最后证明了对于 Lipschitz 和凸函数 class,使用随机梯度下降解决此问题后,最终迭代的误差高概率为 O (log (T)/sqrt (T))
Dec, 2018
本论文提出一种简单的统计程序,可以有效地检测恒定步长随机梯度下降法的转换和稳定阶段,从而快速获得收敛结果。这种统计程序在人工数据集和实际数据集上表现出最先进的性能,即便目标函数为二次时,传统的 Pflug 检验方法也不能提供足够的诊断。
Jul, 2020
本文研究了针对非强凸问题的梯度下降、均值梯度下降以及重球法等算法的加速,表明可以将这些算法重新表述为常数参数二阶差分方程算法,并提供了详细的稳定性分析和显式常数的稳定性结果。同时,本文还讨论了噪声梯度情况下的情况,并给出了一种新的算法。
Apr, 2015
本文考虑优化一个平滑凸函数,该函数是一组可微函数的平均数,在每个梯度的范数受到平均梯度范数的线性约束的假设下,证明了基本的随机梯度方法具有 O (1/k) 的收敛速度,并且在强凸条件下具有线性收敛速度。
Aug, 2013
本文提供一个简明的证明,只需遵循两个规则即可自动化梯度下降:1)不要过快增加步长,2)不要超出局部曲率;通过遵循这些规则,可以得到对局部几何条件自适应的方法,收敛保证只取决于解的附近的平滑度,因此收敛于任何凸问题中,包括可以最小化任意连续两次可微的凸函数的问题,本文将探讨该方法在一系列凸和非凸问题上的性能。
Oct, 2019
本文针对随机梯度下降算法在非凸问题中的收敛性进行轨迹分析,首先证明了在广泛的步长策略范围内,SGD 生成的迭代序列保持有界并以概率 1 收敛,随后证明了 SGD 避开了严格的鞍点 / 流形的概率是 1,最后证明了算法在采用 Theta (1/n^p) 步长时收敛速度为 O (1/n^p),这为调整算法步长提供了重要的指导建议,并且在 CIFAR 的 ResNet 架构中,展示了此启发式方法加速收敛的效果。
Jun, 2020