(随机)梯度方法的统一最优分析
通过利用指数步长和随机线性搜索等技术,使得随机梯度下降算法适应不同噪声水平和问题相关的常数,可以在强凸函数的条件下,取得与理论最优相近的收敛速度,同时能够有效地处理噪声和数据不凸的情况。
Oct, 2021
本文研究了随机梯度下降在随机情形下的最优性。结果表明,对于光滑问题,算法可以达到最优的 O (1/T) 收敛速率,但对于非光滑问题,平均收敛速率可能真的是 Ω(log (T)/T),而这不仅仅是分析的产物。反过来,我们展示了一种简单的平均步骤修改方法,足以恢复到 O (1/T) 收敛速率,而无需对算法做出任何其他改变。此外,我们还给出了支持我们发现的实验结果,并指出了开放性问题。
Sep, 2011
本文对随机梯度下降(SGD)优化算法进行了严格的强误差分析,并证明了在标准凸性类型的目标函数和 SGD 优化算法中出现的随机误差的松弛假设下,对于任意小的 ε 和任意大的 p,所考虑的 SGD 优化算法都会按照 1/2-ε 的阶数在强 L^p 意义下收敛到全局最小值。本文的证明重点在于首先运用动力系统中的 Lyapunov-type 函数理论技术开发出一般的 SGD 优化算法收敛技术,然后应用具有多项式结构的具体 Lyapunov-type 函数,并在出现在 Lyapunov-type 函数中的幂上执行归纳论证,以达到在强 L^p 意义下实现任意大 p 收敛率的目的。
Jan, 2018
本文探讨了在没有光滑假设的情况下,以及通过运行平均方案将 SGD 迭代转换为具有最佳优化精度的解决方案的性能,并证明了对于凸非光滑目标函数,最后一个 SGD 迭代的次优性的程度随 T 的轮次按 O(log(T)/sqrt(T))缩放,对于非光滑强凸情况,次优性的程度随 T 按 O(log(T)/ T)缩放。此外,本文提出了一种新的简单平均方案,并提供了一些实验说明。
Dec, 2012
通过分析,本文展示了当总迭代次数足够大时,随机梯度下降法(SGD)的最终迭代中存在一个 ε- 稳定点,这是一个比现有结果更强的结论,并且可以在 SGD 的最终迭代中度量 ε- 稳定点的密度,同时对于目标函数和随机梯度的边界条件,我们恢复了经典的 O (1/√T) 渐进速率,此分析结果解决了与 SGD 的非凸收敛性相关的某些迷思和传说,并提出了一些有启发性的研究方向。
Oct, 2023
使用随机梯度下降来最小化 Lipschitz 函数和强凸函数但不一定可微的问题,证明了在 T 步随机梯度下降后,最终迭代的误差高概率为 O (log (T)/T);同时构造了一个函数,证明了在确定性梯度下降中,最终迭代的误差为 Ω(log (T)/T);然后证明了在采用后缀平均法的情形下,它的高概率误差界是优化函数相关类别中的最优界(O (1/T));最后证明了对于 Lipschitz 和凸函数 class,使用随机梯度下降解决此问题后,最终迭代的误差高概率为 O (log (T)/sqrt (T))
Dec, 2018
本文考虑优化一个平滑凸函数,该函数是一组可微函数的平均数,在每个梯度的范数受到平均梯度范数的线性约束的假设下,证明了基本的随机梯度方法具有 O (1/k) 的收敛速度,并且在强凸条件下具有线性收敛速度。
Aug, 2013