采用随机一阶方法找到梯度范数不超过 ε 的 ε- 稳定点的复杂度下界，使用具有有界方差的无偏随机梯度预言机访问光滑但可能非凸函数的一种模型，证明任何算法在最坏情况下需要至少 ε^-4 个查询才能找到 ε- 稳定点。对于噪声梯度估计满足均方光滑性质的更严格模型，我们证明了 ε^ -3 个查询的下界，建立了最近提出的方差缩减技术的最优性。

Dec, 2019

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

Oct, 2023

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

Feb, 2020

本文探讨了在随机凸优化问题中寻找近似驻点的 oracle 复杂度问题和其和全局 oracle 模型的关系，并提出了一种扩展的递归正则化算法以实现接近最优率，并揭示了 stochastic optimization 和 learning 的复杂度之间的一些惊人区别。

Feb, 2019

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

Feb, 2019

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

Feb, 2019

非凸优化中寻找近似驻点的计算和查询复杂性是本文的关键研究内容，其中包括在无约束域中寻找近似驻点的问题的 PLS 完备性、二维情况下的零阶算法以及近似驻点的查询复杂性的特征化，同时还研究了约束优化问题中寻找近似 KKT 点的查询复杂性，并指出约束优化中近似 KKT 点与无约束优化中近似驻点的对应关系。

Oct, 2023

该研究论文证明了在高维、潜在非凸函数上找到 ε- 稳态点的复杂性下界，并探讨了基于 Oracle 算法的复杂度测量方法，显示出梯度下降、三次正则化牛顿法和广义 p 次正则化在自然函数类中是最优的。

Oct, 2017

本文提出了使用混合随机估算器设计的混合随机梯度算法来解决非凸期望问题，该算法可以获得更好的复杂度，同时考虑不同的扩展，如使用自适应步长和不同的迭代方式。在使用两个非凸模型进行了多个数据集上的比较。

May, 2019

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

Jul, 2019