本文研究了基于 Hessian 矩阵近似的非凸优化中信任域和立方正则化方法的变体。通过对不精确 Hessian 矩阵的渐进解和相应子问题的近似解,提供了迭代复杂度,以实现达到二阶最优条件的近似解,并且在现有文献中条件松弛。
Aug, 2017
本文研究了通过子采样获得渐进和海森矩阵的近似解来解决随机优化问题,提出了利用这些近似的 Newton-like 方法,并讨论了如何协调渐进和海森矩阵的准确度,得到期望中的超线性收敛速度。该文第二部分分析了一种利用共轭梯度方法近似求解线性系统的不精确 Newton 方法,并且采样的是海森矩阵而不是梯度(梯度被认为是精确的)。我们提供了一种基于 CG 迭代和海森矩阵近似质量的复杂度分析,并将其与采用随机梯度迭代而不是 CG 方法的方法进行了比较。最后,我们报告了初步的数值结果,说明了在 logistic 回归的机器学习应用中,不精确子采样牛顿方法的表现。
Sep, 2016
本文提出一种基于子采样的方法,以降低 cubic regularization 方法的高计算复杂度,并利用浓度不等式提出相应的采样方案,从而在保证 cubic regularization 方法的全局和局部收敛性的同时,给出其全局收敛保证的首个子采样变体在非凸函数的设置中的实验证明。
May, 2017
通过使用随机 TR 和 ARC 方法,我们可以在同时提供 Hessian 矩阵、梯度和函数值的不精确计算的基础上,减少每次迭代的传播开销,从而获得与之前研究中的准确计算同级别的迭代复杂度以实现近似二阶最优性,并通过有限和最小化问题中的随机采样技术满足不精确性的温和条件。数值实验支持这些发现,并表明我们的算法在进行相同或相似次数的迭代时,每次迭代所需的计算开销较当前的二阶方法更少。
Oct, 2023
本文论述了大规模优化问题中 Sub-sampling 的迭代算法,提供了 Hessian 和梯度子采样的收敛边界,使用随机数值线性代数来获得适当的采样策略,并为在大规模线性系统下近似更新的情况下的全局收敛结果提供了解决方案
Jan, 2016
提出了随机方差约减的立方正则牛顿法,应用于非凸优化问题。该方法在半随机梯度和半随机海森矩阵的基础上工作,具有较低的复杂度,并在各种非凸优化问题上得到了验证。
Feb, 2018
本文介绍了一种应用于非凸优化的三次正则化牛顿法,并提出了自适应方差调整的方案,通过对随机矩阵的三到四阶矩的分析来实现二阶保证,进而降低黑塞矩阵样本的复杂度。
Nov, 2018
非凸函数的最小化,利用近似正负曲率方向步长,相对不精确度度量梯度和 Hessian 矩阵,松弛一阶和二阶精度的耦合,通过马丁格尔分析和浓度不等式得到收敛性分析,并将算法应用于经验风险最小化问题。
本文提出了一个随机变体的经典算法 -- 立方正则化牛顿方法。该算法可以有效地避免鞍点问题,并在仅需要 $\mathcal {\tilde {O}}(\epsilon^{-3.5})$ 个随机梯度和随机海森向量乘积评估的情况下,为一般光滑的非凸函数找到近似的局部极小值。
Nov, 2017
本文研究了机器学习中基于不光滑正则化的各种优化问题,并提出了三种不精确的近端梯度算法,包括基本版本和 Nesterov 加速版本。理论分析表明,我们的不精确近端梯度算法可以在非凸情况下具有和精确近端梯度算法相同的收敛速度。实验结果证实了新算法在三个代表性非凸学习问题上的优越性。
Dec, 2016