机器学习的非凸优化：梯度、随机性和鞍点

ICMLFeb, 2019

机器学习的非凸优化：梯度、随机性和鞍点

On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points

Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, Michael I. Jordan

TL;DR本文研究梯度下降和随机梯度下降等算法在机器学习中的应用，分析了这些算法在非凸优化问题中收敛到驻点的情况，提出了变形的算法可以更高效地避免出现维数灾难，从而沟通了理论和实践。

Abstract

gradient descent (GD) and stochastic gradient descent (SGD) are the workhorses of large-scale machine learning. While classical theory foc

gradient descent stochastic gradient descent machine learning nonconvex optimization stationary points

发现论文，激发创造

非凸世界中 SGD 的更好理论

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

Feb, 2020

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

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

Oct, 2023

非凸随机梯度下降逃离鞍点的尖锐分析

本文将通过对随机梯度下降进行深入分析，证明当目标函数满足梯度 Lipschitz、Hessian-Lipschitz 和发散噪声假设时，SGD 能够在 O（ε^ -3.5）次随机梯度计算中逃离鞍点并找到（ε，O（ε^ 0.5））- 近似二阶稳定点，从而推翻了 SGD 至少需要 O（ε^ - 4）的经典信念。此类 SGD 速率与大多数采用其他技术的加速非凸随机优化算法的速率相匹配，如 Nesterov 的动量加速，负曲率搜索，以及二次和三次正则化技巧。本文的新型分析为非凸 SGD 提供了新的见解，并可潜在地推广到广泛的随机优化算法类。

Feb, 2019

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

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

Feb, 2019

一个替代观点：随机梯度下降在何时逃离局部极小值？

本文研究证明随机梯度下降算法可以在一些非凸函数下工作，这说明了为什么 SGD 在神经网络中工作得非常好。

Feb, 2018

梯度下降法在逃离鞍点时可能需要指数级的时间

本文研究了梯度下降法遇到鞍点问题，提出加入微扰可以提高非凸优化的效率，其在理论上和实验上均得到了支持。

May, 2017

高维推断中的非凸损失在线随机梯度下降

研究了 SGD 算法在高维参数空间下最简单在线版本的性能，通过对样本数量的阈值来确定参数估计的一致性，其阈值是多项式维度的，取决于信息指数。