SGD 对超参数模型的更快收敛和快速收敛，及加速感知器

Oct, 2018

SGD 对超参数模型的更快收敛和快速收敛，及加速感知器

Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron

Sharan Vaswani, Francis Bach, Mark Schmidt

TL;DR通过研究表明，在现代机器学习中，采用具有极高表现力的模型进行训练，可以实现完全拟合或内插数据，从而得到零训练损失。我们证明，采用恒定步长随机梯度下降法（SGD）与 Nesterov 加速法具有相同的收敛速度，适用于凸和强凸函数。同时，我们发现，SGD 可以在非凸情况下像全梯度下降法一样高效地找到一阶稳定点。最后，我们通过对合成和真实数据集的实验验证了我们的理论发现。

Abstract

Modern machine learning focuses on highly expressive models that are able to fit or interpolate the data completely, resulting in zero training loss. For such models, we show that the stochastic gradients of common loss functions satisfy a strong growth condition. Under this condition,

machine learning stochastic gradient descent convergence rate loss function perceptron algorithm

发现论文，激发创造

关于非凸过参数化学习中 SGD 的指数收敛

该文研究了使用随机梯度下降方法学习的大型过度参数化模型的收敛速度，并证明了当损失函数为凸函数或满足 Polyak-Lojasiewicz 条件的广泛非凸函数类时，常数步长下 SGD 可以实现指数收敛。

Nov, 2018

关于 Nesterov 加速梯度方法在随机设置下的收敛性

研究了 Nesterov 加速梯度方法在随机逼近和有限和设置下的表现，发现使用通常的步长和动量参数，该方法在后者可能发散，进而阐明了这种方法在此情况下可能失败的原因。

Feb, 2020

基于插值的随机加速梯度下降算法的快速收敛

我们在插值条件下证明了随机 Nesterov 加速的新的收敛速度。不同于以往的分析，我们的方法可以加速任何在期望中取得足够进展的随机梯度方法。证明使用估计序列框架进行，适用于凸函数和强凸函数，并且可以轻松推广到满足强生长条件的加速 SGD。在这种特殊情况下，我们的分析将强生长常数的依赖性从 ρ 减小到√ρ，相对于以前的工作来说，这一改进相当于最坏情况下条件数的平方根，并解决了对于随机加速的保证可能不如 SGD 的批评。

Apr, 2024

插值的威力：理解 SGD 在现代超参模型学习中的有效性

本文旨在正式解释当代机器学习中观察到的 SGD 快速收敛现象。我们重点观察现代学习架构是过参数化的，并且被训练用于通过将经验损失（分类和回归）驱动到接近零的插值数据。我们表明，这些插值方案允许 SGD 快速收敛，与全梯度下降迭代次数相当。对于凸损失函数，我们获得了与全梯度下降相似的 “迷你批次” SGD 的指数收敛界限。关键的迷你批次大小可以视为有效迷你批次并行化的限制，并且几乎独立于数据大小。

Dec, 2017

面向极小化问题：超参数问题 SGD 的快速收敛

本文提出在插值范式内的正则条件，使得随机梯度方法与确定性梯度方法具有相同的最坏迭代复杂度，同时仅在每次迭代中使用单个采样梯度（或一个小批量）。最后，我们证明了我们的条件在训练具有线性输出层的足够宽的前馈神经网络时成立。

Jun, 2023

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

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

Oct, 2023

强生长条件下随机梯度下降的快速收敛

本文考虑优化一个平滑凸函数，该函数是一组可微函数的平均数，在每个梯度的范数受到平均梯度范数的线性约束的假设下，证明了基本的随机梯度方法具有 O (1/k) 的收敛速度，并且在强凸条件下具有线性收敛速度。

Aug, 2013

利用动量加速随机梯度下降优化过参数化学习

本文介绍了一种名为 MaSS 的算法，它使用与 SGD 相同的步长，但具有比 SGD 更快的加速收敛速度。该算法解决了 Nesterov SGD 的不收敛问题，并分析了收敛速度和最优超参数对于 mini-batch size 的依赖性。实验结果表明，MaSS 算法在多个深度网络架构中均表现出比 SGD、Nesterov SGD 和 Adam 更优秀的性能。

Oct, 2018

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

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

Jun, 2020

非凸世界中 SGD 的更好理论

本篇论文使用类似于期望光滑性假设的新方法来研究随机梯度下降法在非凸优化中的收敛率，并在考虑多种采样策略和小批量大小的情况下，探讨有限和优化问题的影响。

Feb, 2020