凸$(L_0,L_1)$-光滑优化的方法:剪辑、加速与自适应
通过对Shor子梯度分析的推广,我们将子梯度方法的经典收敛速度理论扩展到可适用于非Lipschitz函数。我们证明了在任何具有局部Lipschitz性的凸函数中,确定性投影子梯度算法的全局O(1/√T)收敛速度。我们还表明,对于具有最多二次增长的凸函数,随机投影子梯度方法的收敛速度为O(1/√T),在强凸性或较弱的二次下限条件下,该速度可进一步提高至O(1/T)。
Dec, 2017
通过研究广义AdaGrad步长在凸和非凸设置中,本文证明了这些步长实现梯度渐近收敛于零的充分条件,从而填补了这些方法理论上的空白。此外,本文表明这些步长允许自动适应随机梯度噪声级别在凸和非凸情况下,实现O(1/T)到O(1/根号T)的插值(带有对数项)。
May, 2018
本文介绍了一种随机子梯度方法,该方法结合了动量项,能够在一类广泛意义下的非光滑、非凸和受约束的优化问题中建立一个特殊的李亚普诺夫函数,实现快速收敛。
Feb, 2020
本文提出了一种修剪随机梯度(子)梯度法(SGD)的收敛性研究,特别是对于具有快速增长次梯度的非光滑凸函数。研究表明,修剪对SGD的稳定性有益,并且修剪SGD算法在许多情况下具有有限的收敛速率。同时,我们还研究了带有动量的修剪方法的收敛性,并展示了新的Lyapunov分析证明了该方法在这类问题中具有最佳的收敛速率。数值结果验证了理论结果。
Feb, 2021
本文介绍了一种新的非均匀光滑条件下的优化方法,并开发出一种简单但有效的分析技术来限制沿轨迹的梯度,从而获得更强的凸优化和非凸优化问题的结果。我们通过这种新方法证明了(随机)梯度下降和Nesterov加速梯度法在这种一般的光滑条件下的收敛率,而不需要梯度剪裁,并允许在随机场景中的有界方差的重尾噪声。
Jun, 2023
通过理论和实验证明,Normalized Stochastic Gradient Descent with Momentum算法在没有先验知识的情况下可以实现(接近)最优复杂度,但复杂度中引入了一个依赖于(L_1)的指数项,这是不可避免的。同时,在确定性设置下,可以通过使用Gradient Descent with a Backtracking Line Search来抵消指数因子。这是首个在广义平滑条件下提出的无需参数设置的收敛结果。
Nov, 2023
该研究介绍了一种局部一阶平滑性oracle(LFSO),可以用于调整梯度下降方法的步长,从而改善全局和局部收敛性。通过应用LFSO于修正的一阶方法,可以在非强凸问题中实现全局线性收敛速度,从而提高了一般(加速)一阶方法的收敛率下界。
Nov, 2023
我们开发了一种梯度下降法的新次优性边界,该边界依赖于优化路径中的目标条件,而不是全局最坏情况下的常数。我们的证明关键在于方向平滑性,这是一种梯度变化的度量,我们用它来开发上界约束。通过求解隐式方程来最小化这些上界约束,我们展示了这些方程对于凸二次函数是容易解决的,并为两种传统步长提供了新的保证。对于一般函数,我们证明了Polyak步长和归一化梯度下降法尽管不使用方向平滑性的任何知识,但能够获得快速的路径相关性。逻辑回归上的实验证明,我们的收敛保证比基于L平滑性的传统理论更紧致。
Mar, 2024
本文提出了一种快速的随机拟牛顿方法,针对平滑性不均匀的情况,通过梯度剪切和方差减小,实现了最优的O(ε^(-3))样本复杂度,并通过简单的超参数调节实现了收敛加速,数值实验证明了该算法优于现有方法。
Mar, 2024