该研究论文证明了在高维、潜在非凸函数上找到 ε- 稳态点的复杂性下界,并探讨了基于 Oracle 算法的复杂度测量方法,显示出梯度下降、三次正则化牛顿法和广义 p 次正则化在自然函数类中是最优的。
Oct, 2017
本文将通过对随机梯度下降进行深入分析,证明当目标函数满足梯度 Lipschitz、Hessian-Lipschitz 和发散噪声假设时,SGD 能够在 O(ε^ -3.5)次随机梯度计算中逃离鞍点并找到(ε,O(ε^ 0.5))- 近似二阶稳定点,从而推翻了 SGD 至少需要 O(ε^ - 4)的经典信念。此类 SGD 速率与大多数采用其他技术的加速非凸随机优化算法的速率相匹配,如 Nesterov 的动量加速,负曲率搜索,以及二次和三次正则化技巧。本文的新型分析为非凸 SGD 提供了新的见解,并可潜在地推广到广泛的随机优化算法类。
Feb, 2019
采用随机一阶方法找到梯度范数不超过 ε 的 ε- 稳定点的复杂度下界,使用具有有界方差的无偏随机梯度预言机访问光滑但可能非凸函数的一种模型,证明任何算法在最坏情况下需要至少 ε^-4 个查询才能找到 ε- 稳定点。对于噪声梯度估计满足均方光滑性质的更严格模型,我们证明了 ε^ -3 个查询的下界,建立了最近提出的方差缩减技术的最优性。
Dec, 2019
本文研究了梯度方法在凸优化中的收敛行为,证明了仅满足某些线段上的 Lipschitz 连续性和强凸性条件时,其复杂度可达到已知的最优值。同时,利用切线条件和投影的约束得到了更为松弛的条件,并应用于稀疏优化问题中构造更快的求解算法。
Mar, 2013
本篇论文研究了非凸优化中高效到达稳定点的基本问题,并利用方差缩减技巧和适用于非凸优化的全新方差缩减分析提出一种首个非凸优化的一阶小批量随机算法,并在非凸损失函数和神经网络训练中表现出了有效性。
Mar, 2016
本文介绍了一种新的非均匀光滑条件下的优化方法,并开发出一种简单但有效的分析技术来限制沿轨迹的梯度,从而获得更强的凸优化和非凸优化问题的结果。我们通过这种新方法证明了(随机)梯度下降和 Nesterov 加速梯度法在这种一般的光滑条件下的收敛率,而不需要梯度剪裁,并允许在随机场景中的有界方差的重尾噪声。
Jun, 2023
针对非凸优化中最小最大优化问题,本研究提出了利用高效的 Hessian - 向量乘积的新型修正动量算法,建立了收敛条件并证明了所提算法的迭代复杂度为 O (ε^{-3})。通过在实际数据集上进行鲁棒的逻辑回归的应用验证了该方法的有效性。
Jun, 2024
非凸函数的最小化,利用近似正负曲率方向步长,相对不精确度度量梯度和 Hessian 矩阵,松弛一阶和二阶精度的耦合,通过马丁格尔分析和浓度不等式得到收敛性分析,并将算法应用于经验风险最小化问题。
Oct, 2023
本文提出了一种快速的随机拟牛顿方法,针对平滑性不均匀的情况,通过梯度剪切和方差减小,实现了最优的 O (ε^(-3)) 样本复杂度,并通过简单的超参数调节实现了收敛加速,数值实验证明了该算法优于现有方法。
Mar, 2024
本研究介绍了一种新的 Nesterov 加速梯度下降法的变体,以应对光滑非凸函数的最小化问题,证明其收敛速度可以接近凸函数,在处理非凸函数方面具有优异的性能,并在此基础上提出了一种基于负曲率的证明非凸性的方法,在具有 Lipschitz 连续梯度和黑塞矩阵的情况下,可以在较少的梯度和函数计算次数内找到目标点。
May, 2017