强生长条件下随机梯度下降的快速收敛
本文研究了随机梯度下降在随机情形下的最优性。结果表明,对于光滑问题,算法可以达到最优的 O (1/T) 收敛速率,但对于非光滑问题,平均收敛速率可能真的是 Ω(log (T)/T),而这不仅仅是分析的产物。反过来,我们展示了一种简单的平均步骤修改方法,足以恢复到 O (1/T) 收敛速率,而无需对算法做出任何其他改变。此外,我们还给出了支持我们发现的实验结果,并指出了开放性问题。
Sep, 2011
本文提出将 Subgradient 方法中的 Polyak 步长推广到随机梯度下降中,并证明了该算法可以在非渐进情况下以更好的速率收敛于优化解,该算法在训练深度神经网络等问题上表现良好。
Mar, 2019
通过研究表明,在现代机器学习中,采用具有极高表现力的模型进行训练,可以实现完全拟合或内插数据,从而得到零训练损失。我们证明,采用恒定步长随机梯度下降法(SGD)与 Nesterov 加速法具有相同的收敛速度,适用于凸和强凸函数。同时,我们发现,SGD 可以在非凸情况下像全梯度下降法一样高效地找到一阶稳定点。最后,我们通过对合成和真实数据集的实验验证了我们的理论发现。
Oct, 2018
我们在插值条件下证明了随机 Nesterov 加速的新的收敛速度。不同于以往的分析,我们的方法可以加速任何在期望中取得足够进展的随机梯度方法。证明使用估计序列框架进行,适用于凸函数和强凸函数,并且可以轻松推广到满足强生长条件的加速 SGD。在这种特殊情况下,我们的分析将强生长常数的依赖性从 ρ 减小到√ρ,相对于以前的工作来说,这一改进相当于最坏情况下条件数的平方根,并解决了对于随机加速的保证可能不如 SGD 的批评。
Apr, 2024
证明在 L - 平滑度条件下,随机梯度下降的迭代收敛速度的数量级为 O (LR2exp [-(mu/4L) T]+sigma2/muT), 其中 sigma2 是随机噪声方差,且收敛速度与最佳已知的 GD 和 SGD 迭代复杂度匹配.
Jul, 2019
本篇论文研究了关于随机逼近问题的现有算法,提出了两种新型随机梯度算法,并在回归和逻辑分类两种经典的监督学习问题上进行了测试,得到了较好的优化效果。
Jun, 2013
本文基于凸优化中函数是光滑和非光滑组合的形式,证明了一种适用于大类凸优化问题的随机近端梯度算法收敛性质,其避免了平均化和理论研究中常见但实际中不一定满足的有界性假设,证明了一系列强、弱收敛性结果,并得到了期望意义下的 $O (1/n)$ 的有界性结果。
Mar, 2014
使用随机梯度下降来最小化 Lipschitz 函数和强凸函数但不一定可微的问题,证明了在 T 步随机梯度下降后,最终迭代的误差高概率为 O (log (T)/T);同时构造了一个函数,证明了在确定性梯度下降中,最终迭代的误差为 Ω(log (T)/T);然后证明了在采用后缀平均法的情形下,它的高概率误差界是优化函数相关类别中的最优界(O (1/T));最后证明了对于 Lipschitz 和凸函数 class,使用随机梯度下降解决此问题后,最终迭代的误差高概率为 O (log (T)/sqrt (T))
Dec, 2018