牛顿法三次正则化在最小化一致凸函数中的应用
介绍了三次正则化方法及其改进的全局收敛性和局部二次收敛性。同时,介绍了一种弱化的错误界条件来证明方法的局部二次收敛性,使得该方法能处理出现退化情况的问题,并将其应用于相位恢复和低秩矩阵恢复的非凸优化问题。
Jan, 2018
本文提出了一个随机变体的经典算法 -- 立方正则化牛顿方法。该算法可以有效地避免鞍点问题,并在仅需要 $\mathcal {\tilde {O}}(\epsilon^{-3.5})$ 个随机梯度和随机海森向量乘积评估的情况下,为一般光滑的非凸函数找到近似的局部极小值。
Nov, 2017
提出了随机方差约减的立方正则牛顿法,应用于非凸优化问题。该方法在半随机梯度和半随机海森矩阵的基础上工作,具有较低的复杂度,并在各种非凸优化问题上得到了验证。
Feb, 2018
我们开发了 Cubically regularized Newton 方法的一阶 (无 Hessian 矩阵) 和零阶 (无导数) 的实现,用于解决一般的非凸优化问题,通过有限差分逼近导数。我们在算法中使用了一种特殊的自适应搜索过程,同时适应正则化常数和有限差分逼近的参数。此方法不需要知道实际的 Lipschitz 常数。此外,我们还为算法增加了惰性 Hessian 更新,重复使用之前计算的 Hessian 近似矩阵进行多个迭代。具体地,我们证明了新的一阶 Hessian-free 方法的全局复杂度界为 O (n^1/2 * ε^-3/2) 个函数和梯度评估,并且零阶无导数方法的函数评估复杂度界为 O (n^3/2 * ε^-3/2),其中 n 是问题的维度,ε 是梯度范数的期望精度。这些复杂度界显著提高了关于 n 和 ε 的联合依赖的先前已知界,用于一阶和零阶非凸优化。
Sep, 2023
该论文研究了优化非凸连续函数的问题,提出了一种名为 SSCN 的随机坐标二阶方法,通过在随机子空间应用立方正则化来降低使用二阶信息的计算复杂性,在高维场景中表现出了良好的适用性,并且通过提出自适应采样方案,实现了比传统一阶方法更快的速度。
Jun, 2024
研究了带有准自共轭平滑成分的复合凸优化问题,通过使用基本的牛顿法结合梯度正则化,提出了一种简单而高效的算法,并应用于多个实际问题,包括逻辑回归、软最大和矩阵缩放,无需对目标函数进行额外的假设,并且获得了快速全局线性收敛率。
Aug, 2023
该研究介绍了一种新的子空间三阶正则牛顿方法,其在解决凸优化问题时具有与维度无关的全局收敛速度,并且在特定谱条件下能恢复到完全维度的三阶正则牛顿方法的收敛速度,数值实验表明该方法比现有的随机子空间方法收敛更快,尤其在高维问题上。
Jan, 2024
使用基于牛顿方法和线性共轭梯度算法的迭代算法来最小化平滑非凸目标函数,在 Hessian 矩阵的负曲率方向上显式检测和利用,可以证明该算法与 1980 年代开发的 Newton-conjugate 梯度程序非常接近,但包括了增强功能,以证明收敛到满足近似一阶和二阶最优条件的点的最坏情况复杂度结果,这些复杂度结果与文献中已知的二阶方法的最佳结果相匹配。
Mar, 2018
我们提出了两种非常简单的随机二阶方法,用于最小化大量充分光滑和强凸函数的平均值。第一种是牛顿方法的随机变体(SN),第二种是具有立方正则化的牛顿方法的随机变体(SCN)。与现有的随机二阶方法不同,我们的方法没有这种缺点,例如,我们的方法的最简单的变体每次迭代只需要计算一个随机选择函数的梯度和海森矩阵。与大多数现有的随机牛顿和拟牛顿方法相比,人们的方法保证了比一阶 oracle 更快的本地收敛,同时适应了问题的曲率。有趣的是,我们的方法不是无偏的,因此我们的理论为设计新的随机方法提供了新的直觉。
Dec, 2019
本文介绍了一种应用于非凸优化的三次正则化牛顿法,并提出了自适应方差调整的方案,通过对随机矩阵的三到四阶矩的分析来实现二阶保证,进而降低黑塞矩阵样本的复杂度。
Nov, 2018