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

Oct, 2017

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

Oct, 2023

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

Dec, 2019

研究了随机梯度下降（SGD）算法在最小化光滑、可能非凸函数梯度范数方面的迭代复杂度，结果表明，Ghadimi 和 Lan 的上限不能得到改进，除非做出额外的假设，即使对于凸二次函数，也是如此；此外还表明，对于非凸函数，SGD 最小化梯度的可行性需要根据所选择的最优性标准而定。

Oct, 2019

研究非光滑、非凸的 Lipschitz 目标函数在具有噪声函数评估的条件下生成 $(\delta,\epsilon)$- 稳定点的复杂性，提出的算法具有 $O (d\delta^{-1}\epsilon^{-3})$ 的复杂度和最优收敛速率。

Jul, 2023

通过使用只需要计算梯度的加速梯度方法，该论文提出了一种快速求解具有 Lipschitz 连续的一阶和二阶导数的非凸优化问题的算法，该方法相较于梯度下降算法在复杂度和精度上都表现更优。

Nov, 2016

我们研究了非光滑非凸目标在分散随机优化中找到 ($\delta,\epsilon$)- 稳定点的有限时间分析。我们提出了一种称为 ME-DOL 的新算法，并在不同环境中建立了样本复杂性。我们证明了该算法在光滑非凸目标中恢复了最优收敛速度的在线至非凸技术，并扩展了分析到非光滑设置，建立在随机平滑和 Goldstein - 次微分集的属性上。我们在一阶设置中建立了 $O (\delta^{-1}\epsilon^{-3})$ 的样本复杂度，这是我们所知道的第一次对于分散非光滑非凸随机优化的有限时间保证（无弱凸性），与其最优集中对应。我们进一步证明了在不使用方差减少的零阶预言机设置时相同的速率。

Jun, 2024

本文介绍了一些带有或没有耦合的非凸优化模型，使用了相关的优化算法，如条件梯度和 ADMM， 为专门处理非凸和非光滑优化问题的理论和算法的发展提出了一步。通过数值实验，证明了这些算法的高效性，特别是在张量鲁棒 PCA 的场景下。

May, 2016

我们介绍了一种新的零阶算法，用于非凸和非光滑目标的私有随机优化。给定一个大小为 M 的数据集，我们的算法确保（α，αρ²/2）-Rényi 差分隐私，并找到一个（δ，ε）- 稳定点，只要 M=Ω^(~)[(d/(δε³)) + (d^(3/2)/(ρδε²)) ]。这与其非私有的零阶模拟的最优复杂度相匹配。值得注意的是，尽管目标不是光滑的，只要 ρ ≥ √(d)ε，我们就有了 “免费” 的隐私。

Jun, 2024

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

Feb, 2019