开放问题:梯度下降的逐步收敛速度
通过研究广义 AdaGrad 步长在凸和非凸设置中,本文证明了这些步长实现梯度渐近收敛于零的充分条件,从而填补了这些方法理论上的空白。此外,本文表明这些步长允许自动适应随机梯度噪声级别在凸和非凸情况下,实现 O(1/T)到 O(1 / 根号 T)的插值(带有对数项)。
May, 2018
我们研究了在紧致集合上的光滑凸函数中使用随机梯度下降的泛化误差,并展示了当迭代次数 T 和数据集大小 n 以任意速率趋近于零时,我们第一次得到了一个消失的泛化误差界,该界与步长 αt=1/√t 成比例,泛化能力不需要强凸性。
Jan, 2024
通过研究表明,在现代机器学习中,采用具有极高表现力的模型进行训练,可以实现完全拟合或内插数据,从而得到零训练损失。我们证明,采用恒定步长随机梯度下降法(SGD)与 Nesterov 加速法具有相同的收敛速度,适用于凸和强凸函数。同时,我们发现,SGD 可以在非凸情况下像全梯度下降法一样高效地找到一阶稳定点。最后,我们通过对合成和真实数据集的实验验证了我们的理论发现。
Oct, 2018
本文针对随机梯度下降算法在非凸问题中的收敛性进行轨迹分析,首先证明了在广泛的步长策略范围内,SGD 生成的迭代序列保持有界并以概率 1 收敛,随后证明了 SGD 避开了严格的鞍点 / 流形的概率是 1,最后证明了算法在采用 Theta (1/n^p) 步长时收敛速度为 O (1/n^p),这为调整算法步长提供了重要的指导建议,并且在 CIFAR 的 ResNet 架构中,展示了此启发式方法加速收敛的效果。
Jun, 2020
本文研究了针对非强凸问题的梯度下降、均值梯度下降以及重球法等算法的加速,表明可以将这些算法重新表述为常数参数二阶差分方程算法,并提供了详细的稳定性分析和显式常数的稳定性结果。同时,本文还讨论了噪声梯度情况下的情况,并给出了一种新的算法。
Apr, 2015
使用随机梯度下降来最小化 Lipschitz 函数和强凸函数但不一定可微的问题,证明了在 T 步随机梯度下降后,最终迭代的误差高概率为 O (log (T)/T);同时构造了一个函数,证明了在确定性梯度下降中,最终迭代的误差为 Ω(log (T)/T);然后证明了在采用后缀平均法的情形下,它的高概率误差界是优化函数相关类别中的最优界(O (1/T));最后证明了对于 Lipschitz 和凸函数 class,使用随机梯度下降解决此问题后,最终迭代的误差高概率为 O (log (T)/sqrt (T))
Dec, 2018
研究随机梯度下降法(SGD)在强凸目标函数上的收敛性,证明了 ICML 2018 和 2019 提出的降低步长的速率序列在每次迭代后的收敛速度与我们的下限相差不到 32 倍,为最优状态;该下限相较于现有工作大约高出了因子 775×d,其中 d 是维度。
Oct, 2018
本文考虑优化一个平滑凸函数,该函数是一组可微函数的平均数,在每个梯度的范数受到平均梯度范数的线性约束的假设下,证明了基本的随机梯度方法具有 O (1/k) 的收敛速度,并且在强凸条件下具有线性收敛速度。
Aug, 2013
使用常数步长的梯度下降算法应用于线性可分数据的逻辑回归,证明了在初始震荡阶段后,算法能够在 a 步的时间内实现 O (1/(aT)) 的收敛速率,从而在总步数为 T 的情况下,通过积极地调整步长可以达到 O (1/T^2) 的加速损失,无需使用动量或变化的步长调度器。
Feb, 2024