梯度下降的非均匀平滑性
通过非统一的平滑性和非统一的 Lojasiewicz 不等式,提出了一些新的方法,用于更快地达到全局最优点,在强化学习和监督学习中表现出了广泛的适用性及实验效果。
May, 2021
这篇文章研究了在有界局部次梯度变化情况下的非光滑优化问题,定义了目标函数的类别,包括传统优化问题中基于目标函数的 Lipschitz 连续性或梯度的 Holder/Lipschitz 连续性的函数,并且包含了既不是 Lipschitz 连续也没有 Holder 连续梯度的函数类别。研究结果表明在传统的优化问题类别中,所定义的类别参数能够得到更为精细的复杂度界限,并恢复了最坏情况下的传统 oracle 复杂度界限,同时对于不是最坏情况的函数通常能够得到更低的 oracle 复杂度。此外,该文章还强调了在并行计算环境中非光滑优化的复杂度与次梯度集合的平均宽度有关。
Mar, 2024
我们开发了一种梯度下降法的新次优性边界,该边界依赖于优化路径中的目标条件,而不是全局最坏情况下的常数。我们的证明关键在于方向平滑性,这是一种梯度变化的度量,我们用它来开发上界约束。通过求解隐式方程来最小化这些上界约束,我们展示了这些方程对于凸二次函数是容易解决的,并为两种传统步长提供了新的保证。对于一般函数,我们证明了 Polyak 步长和归一化梯度下降法尽管不使用方向平滑性的任何知识,但能够获得快速的路径相关性。逻辑回归上的实验证明,我们的收敛保证比基于 L 平滑性的传统理论更紧致。
Mar, 2024
利用可适应性光滑函数的概念和 Bregman 基础的近端梯度方法,在解决具有复杂目标函数的非凸、非光滑最小化问题时,实现全局收敛。
Jun, 2017
本文提出了一种快速的随机拟牛顿方法,针对平滑性不均匀的情况,通过梯度剪切和方差减小,实现了最优的 O (ε^(-3)) 样本复杂度,并通过简单的超参数调节实现了收敛加速,数值实验证明了该算法优于现有方法。
Mar, 2024
本文研究了解决光滑的非强凸约束优化问题的一些一阶方法的收敛率,提供了一些松弛的强凸条件并证明了它们对于多种一阶方法的线性收敛是足够的,最后证明了所提出的松弛强凸条件涵盖了求解线性系统、线性规划和线性约束凸问题的重要应用。
Apr, 2015
该研究提出了一种新颖的自适应步长方法来解决随机梯度下降(SGD)中的问题,通过利用我们识别出的可追踪的量(梯度的 Lipschitz 常数和搜索方向的局部方差的概念),我们的发现为随机优化提供了几乎无需调参的算法,该算法在应用于二次问题时具有可证明的收敛性质,并在经典图像分类任务中展现出真正的问题自适应行为。我们的框架还可以包含预处理器,从而实现对随机二阶优化方法的自适应步长的实现。
Nov, 2023
使用随机梯度下降来最小化 Lipschitz 函数和强凸函数但不一定可微的问题,证明了在 T 步随机梯度下降后,最终迭代的误差高概率为 O (log (T)/T);同时构造了一个函数,证明了在确定性梯度下降中,最终迭代的误差为 Ω(log (T)/T);然后证明了在采用后缀平均法的情形下,它的高概率误差界是优化函数相关类别中的最优界(O (1/T));最后证明了对于 Lipschitz 和凸函数 class,使用随机梯度下降解决此问题后,最终迭代的误差高概率为 O (log (T)/sqrt (T))
Dec, 2018
本文介绍了一种新的非均匀光滑条件下的优化方法,并开发出一种简单但有效的分析技术来限制沿轨迹的梯度,从而获得更强的凸优化和非凸优化问题的结果。我们通过这种新方法证明了(随机)梯度下降和 Nesterov 加速梯度法在这种一般的光滑条件下的收敛率,而不需要梯度剪裁,并允许在随机场景中的有界方差的重尾噪声。
Jun, 2023
本研究考虑在没有标准 Lipschitz 连续性假设的随机弱凸优化问题中,基于新的自适应正则化(步长)策略,我们展示了一类广泛的随机算法包括随机次梯度法在具有恒定错误率的情况下保持 O (1/√K) 的收敛速率。我们的分析基于弱假设:Lipschitz 参数可以由 ||x|| 的一般增长函数界定,或通过独立随机样本进行局部估计。
Jan, 2024