Jan, 2018

随机梯度下降优化算法的强误差分析

PDF
TL;DR本文对随机梯度下降（SGD）优化算法进行了严格的强误差分析，并证明了在标准凸性类型的目标函数和 SGD 优化算法中出现的随机误差的松弛假设下，对于任意小的 ε 和任意大的 p，所考虑的 SGD 优化算法都会按照 1/2-ε 的阶数在强 L^p 意义下收敛到全局最小值。本文的证明重点在于首先运用动力系统中的 Lyapunov-type 函数理论技术开发出一般的 SGD 优化算法收敛技术，然后应用具有多项式结构的具体 Lyapunov-type 函数，并在出现在 Lyapunov-type 函数中的幂上执行归纳论证，以达到在强 L^p 意义下实现任意大 p 收敛率的目的。
发现论文，激发创造
  • （随机）梯度方法的统一最优分析

    证明在 L - 平滑度条件下，随机梯度下降的迭代收敛速度的数量级为 O (LR2exp [-(mu/4L) T]+sigma2/muT), 其中 sigma2 是随机噪声方差，且收敛速度与最佳已知的 GD 和 SGD 迭代复杂度匹配.

    Jul, 2019

  • 非凸优化中具有概率保障的随机梯度下降泛化误差界

    本文探讨了深度学习模型的一种优化方法 —— 随机梯度下降在泛化能力上的稳定性，提出了一种基于梯度方差的稳定性指标，并在此基础上分别分析了常规非凸损失函数、梯度主导性损失函数和带强凸规则化器的问题，得到了一系列改进的泛化误差界。

    Feb, 2018

  • 随机梯度算法的新收敛性特点

    本文对随机梯度下降法（SGD）的收敛性进行了分析，提出了一种新的假设随机梯度较真实梯度的范数更小的分析方法，并在多个情境下证明了 SGD 的收敛性，拓展了当前一类可达到收敛性的学习率。

    Nov, 2018

  • 解密 SGD 非凸收敛的神话与传说

    通过分析，本文展示了当总迭代次数足够大时，随机梯度下降法（SGD）的最终迭代中存在一个 ε- 稳定点，这是一个比现有结果更强的结论，并且可以在 SGD 的最终迭代中度量 ε- 稳定点的密度，同时对于目标函数和随机梯度的边界条件，我们恢复了经典的 O (1/√T) 渐进速率，此分析结果解决了与 SGD 的非凸收敛性相关的某些迷思和传说，并提出了一些有启发性的研究方向。

    Oct, 2023

  • 随机梯度下降在非凸问题中的几乎必然收敛

    本文针对随机梯度下降算法在非凸问题中的收敛性进行轨迹分析，首先证明了在广泛的步长策略范围内，SGD 生成的迭代序列保持有界并以概率 1 收敛，随后证明了 SGD 避开了严格的鞍点 / 流形的概率是 1，最后证明了算法在采用 Theta (1/n^p) 步长时收敛速度为 O (1/n^p)，这为调整算法步长提供了重要的指导建议，并且在 CIFAR 的 ResNet 架构中，展示了此启发式方法加速收敛的效果。

    Jun, 2020

  • 收敛于全局最优解的学习算法的稳定性和泛化性

    本文通过建立黑盒稳定性结果，仅依赖于学习算法的收敛和损失函数最小值周围的几何形态，为收敛到全局最小值的学习算法建立新的泛化界限，适用于满足 Polyak-Lojasiewicz（PL）和二次增长（QG）条件的非凸损失函数以及一些具有线性激活的神经网络，并使用黑盒结果来证明 SGD、GD、RCD 和 SVRG 等优化算法的稳定性在 PL 和强凸设置中具有可拓展性，同时指出存在简单的具有多个局部最小值的神经网络，在 PL 设置下 SGD 稳定，但 GD 不稳定。

    Oct, 2017

  • 通过扩散逼近对随机梯度下降算法进行时间均匀性弱误差分析

    本文介绍一种新的方法来扩展了扩散逼近的有效性，使得可以利用此方法对强凸目标函数的常步长随机梯度下降算法进行渐进行为的表征，从而使得扩散逼近的适用范围更广、更深入涵盖了数据科学中随机优化算法的应用。

    Feb, 2019

  • 随机梯度方法在梯度主导条件下的几乎必然收敛速率

    基于全局和局部梯度支配的随机梯度下降法收敛速度证明及其在监督学习和强化学习中的应用。

    May, 2024

  • SGD 和 Hogwild!：在无需有界梯度假设的情况下收敛

    该研究论文讨论了随机梯度下降算法的收敛性分析，提出了一种在异步并行环境下使用降低学习率机制的算法，并证明了其收敛性。

    Feb, 2018

  • 非强凸平稳随机逼近，收敛速率 O (1/n)

    本篇论文研究了关于随机逼近问题的现有算法，提出了两种新型随机梯度算法，并在回归和逻辑分类两种经典的监督学习问题上进行了测试，得到了较好的优化效果。

    Jun, 2013