随机梯度方法在梯度主导条件下的几乎必然收敛速率
本篇论文研究了关于随机逼近问题的现有算法,提出了两种新型随机梯度算法,并在回归和逻辑分类两种经典的监督学习问题上进行了测试,得到了较好的优化效果。
Jun, 2013
证明在 L - 平滑度条件下,随机梯度下降的迭代收敛速度的数量级为 O (LR2exp [-(mu/4L) T]+sigma2/muT), 其中 sigma2 是随机噪声方差,且收敛速度与最佳已知的 GD 和 SGD 迭代复杂度匹配.
Jul, 2019
本文对随机梯度下降法(SGD)的收敛性进行了分析,提出了一种新的假设随机梯度较真实梯度的范数更小的分析方法,并在多个情境下证明了 SGD 的收敛性,拓展了当前一类可达到收敛性的学习率。
Nov, 2018
本文考虑优化一个平滑凸函数,该函数是一组可微函数的平均数,在每个梯度的范数受到平均梯度范数的线性约束的假设下,证明了基本的随机梯度方法具有 O (1/k) 的收敛速度,并且在强凸条件下具有线性收敛速度。
Aug, 2013
本文基于凸优化中函数是光滑和非光滑组合的形式,证明了一种适用于大类凸优化问题的随机近端梯度算法收敛性质,其避免了平均化和理论研究中常见但实际中不一定满足的有界性假设,证明了一系列强、弱收敛性结果,并得到了期望意义下的 $O (1/n)$ 的有界性结果。
Mar, 2014
本文对随机梯度下降(SGD)优化算法进行了严格的强误差分析,并证明了在标准凸性类型的目标函数和 SGD 优化算法中出现的随机误差的松弛假设下,对于任意小的 ε 和任意大的 p,所考虑的 SGD 优化算法都会按照 1/2-ε 的阶数在强 L^p 意义下收敛到全局最小值。本文的证明重点在于首先运用动力系统中的 Lyapunov-type 函数理论技术开发出一般的 SGD 优化算法收敛技术,然后应用具有多项式结构的具体 Lyapunov-type 函数,并在出现在 Lyapunov-type 函数中的幂上执行归纳论证,以达到在强 L^p 意义下实现任意大 p 收敛率的目的。
Jan, 2018
对于大部分基于凸优化的统计 $M$- 估计器,我们分析了解决这些问题的渐进收敛速度,并在高维框架中工作,我们定义了适当限制的条件,并证明了这些条件适用于各种统计模型,我们的理论保证了项目的概率几何收敛速度不断提高,最高可达到模型的统计精度,这个结果比以往收敛结果更加尖锐,这适用于 $M$- 估计器和各种统计模型,展现了高维估计中统计精度和计算效率的有趣联系。
Apr, 2011
本研究论文探讨了随机梯度下降(SGD)方法及其变种在训练非光滑激活函数构建的神经网络中的收敛性质,提出了一种新的框架,分别为更新动量项和变量分配不同的时间尺度。在一些温和条件下,我们证明了我们提出的框架在单一时间尺度和双时间尺度情况下的全局收敛性。我们展示了我们提出的框架包含了许多著名的 SGD 类型方法,包括 heavy-ball SGD、SignSGD、Lion、normalized SGD 和 clipped SGD。此外,当目标函数采用有限和形式时,我们证明了基于我们提出的框架的这些 SGD 类型方法的收敛性质。特别地,在温和的假设条件下,我们证明了这些 SGD 类型方法以随机选择的步长和初始点找到了目标函数的 Clarke 稳定点。初步的数值实验表明了我们分析的 SGD 类型方法的高效性。
Jul, 2023