本文提出了一个随机变体的经典算法 -- 立方正则化牛顿方法。该算法可以有效地避免鞍点问题,并在仅需要 $\mathcal {\tilde {O}}(\epsilon^{-3.5})$ 个随机梯度和随机海森向量乘积评估的情况下,为一般光滑的非凸函数找到近似的局部极小值。
Nov, 2017
本文介绍了一种应用于非凸优化的三次正则化牛顿法,并提出了自适应方差调整的方案,通过对随机矩阵的三到四阶矩的分析来实现二阶保证,进而降低黑塞矩阵样本的复杂度。
Nov, 2018
提出了一种 Stochastic Variance-Reduced Cubic regularization (SVRC) 算法的改进型,叫做 Stochastic Recursive Variance-Reduced Cubic regularization (SRVRC) 算法,该算法结合递归更新的半随机梯度和 Hessian 估计器,可以更快更好地找到一个(ε,sqrt(ε))- 近似局部极小值点。并且在这个基础上,我们进一步提出了一种基于 SRVRC 的无 Hessian 的算法:SRVRC$_{ext {free}}$,它只需要随机梯度和 Hessian 向量积运算,并且达到更好的运算速度。
Jan, 2019
该论文研究了优化非凸连续函数的问题,提出了一种名为 SSCN 的随机坐标二阶方法,通过在随机子空间应用立方正则化来降低使用二阶信息的计算复杂性,在高维场景中表现出了良好的适用性,并且通过提出自适应采样方案,实现了比传统一阶方法更快的速度。
Jun, 2024
本文提出一种基于子采样的方法,以降低 cubic regularization 方法的高计算复杂度,并利用浓度不等式提出相应的采样方案,从而在保证 cubic regularization 方法的全局和局部收敛性的同时,给出其全局收敛保证的首个子采样变体在非凸函数的设置中的实验证明。
May, 2017
我们提出了一种基于嵌套方差降低的新随机梯度下降算法,可用于解决有限个数个、非凸函数的优化问题,并且在平滑非凸函数上具有比现有算法更好的梯度复杂度。
Jun, 2018
我们提出了两种非常简单的随机二阶方法,用于最小化大量充分光滑和强凸函数的平均值。第一种是牛顿方法的随机变体(SN),第二种是具有立方正则化的牛顿方法的随机变体(SCN)。与现有的随机二阶方法不同,我们的方法没有这种缺点,例如,我们的方法的最简单的变体每次迭代只需要计算一个随机选择函数的梯度和海森矩阵。与大多数现有的随机牛顿和拟牛顿方法相比,人们的方法保证了比一阶 oracle 更快的本地收敛,同时适应了问题的曲率。有趣的是,我们的方法不是无偏的,因此我们的理论为设计新的随机方法提供了新的直觉。
Dec, 2019
该研究提出了一种名为 “Vite” 的基于 Stochastic Quasi-Newton 算法的优化方法,它利用一种现有的一阶技术来减少噪声和方差,并在大规模学习问题上取得了不错的结果。
Mar, 2015
本篇论文研究了非凸优化中高效到达稳定点的基本问题,并利用方差缩减技巧和适用于非凸优化的全新方差缩减分析提出一种首个非凸优化的一阶小批量随机算法,并在非凸损失函数和神经网络训练中表现出了有效性。
Mar, 2016
本文研究了立方正则化牛顿法在解决具有一致凸性目标的复合最小化问题时的迭代复杂度。在引入某种程度的二阶条件数的概念后,我们证明了在非退化情况下具有自适应正则化参数估计的方法具有线性收敛率。我们的算法自动实现了具有 H"older 连续的目标平滑部分的不同问题类别中均匀凸目标函数的全局最佳复杂度界限。作为我们发展的副产品,我们证明了牛顿法在具有一致有界二阶导数的强凸函数类上的全局迭代复杂度始终优于梯度法。
May, 2019