可分离数据上的随机梯度下降：固定学习率的精确收敛

Jun, 2018

可分离数据上的随机梯度下降：固定学习率的精确收敛

Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate

Mor Shpigel Nacson, Nathan Srebro, Daniel Soudry

TL;DR本文探讨了采用 SGD 进行机器学习的收敛性问题，特别是在采用线性可分数据及单调函数损失函数的情况下，证明了 SGD 在固定非零学习率的条件下可以收敛至零损失，对于分类问题中的单调函数损失函数（例如对数损失），每次迭代权重向量趋向于 $L_2$ 最大裕度向量，且损失以 $O (1/t)$ 的速率收敛。

Abstract

stochastic gradient descent (SGD) is a central tool in machine learning. We prove that SGD converges to zero loss, even with a fixed (non-vanishing) learning rate - in the special case of homogeneous linear classifiers<

stochastic gradient descent linear classifiers monotone loss functions logistic loss convergence

发现论文，激发创造

可分数据上梯度下降的收敛性

对采用严格单调尾部的损失函数（如对数损失）在可分离数据集上利用梯度下降时的隐式偏差进行了详细研究，证明了对于一大类超多项式尾部损失，梯度下降迭代可以收敛到任意深度的线性网络的 L2 最大边距解。

Mar, 2018

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

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

Oct, 2018

分离数据梯度下降的隐式偏差

本研究发现，在无正则化的逻辑回归问题、线性可分数据集上，使用均匀线性预测器的梯度下降法会收敛于最大间隔解的方向。收敛速度缓慢，方法适用于其他单调递减的损失函数、多类别问题和某些受限情况下的深层网络训练。此研究还可帮助理解模型的隐式正则化和其他优化方法。

Oct, 2017

可分数据下的逻辑回归梯度下降收敛速率

本文证明了在使用可变学习率运行梯度下降时，对于逻辑回归目标函数，损失 f (x) ≤ 1.1・f (x*) + ε，其中误差 ε 按迭代次数指数下降，并按任意固定解决方案 x* 条目大小的多项式下降。该文还将这些思想应用于稀疏逻辑回归，在那里它们导致了稀疏误差交换的指数改进。

Jun, 2023

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

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

Nov, 2018

（随机）梯度方法的统一最优分析

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

Jul, 2019

梯度方法在可分数据上永不过拟

本文论述了使用梯度方法和指数损失训练线性预测器时，预测器的收敛方向渐近地趋向于最大边缘预测器，但无论迭代次数有多大，标准梯度方法（特别是梯度流、梯度下降、随机梯度下降）永远不会过拟合可分数据集。

Jun, 2020

凸 SGD: 泛化无需提前停止

我们研究了在紧致集合上的光滑凸函数中使用随机梯度下降的泛化误差，并展示了当迭代次数 T 和数据集大小 n 以任意速率趋近于零时，我们第一次得到了一个消失的泛化误差界，该界与步长 αt=1/√t 成比例，泛化能力不需要强凸性。

Jan, 2024

非凸学习的随机梯度下降算法 (无需假设梯度有上限)

本文研究证明了随机梯度下降在非凸学习中，无需统一梯度有界性假设也能达到最优收敛率的情况，并在一定程度上对于一般非凸目标函数和梯度主导的目标函数实现了几乎必然收敛。特别地，在方差为零的情况下可以得到线性收敛。

Feb, 2019

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

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

Oct, 2023