快速非凸优化的随机三次正则化
提出了随机方差约减的立方正则牛顿法,应用于非凸优化问题。该方法在半随机梯度和半随机海森矩阵的基础上工作,具有较低的复杂度,并在各种非凸优化问题上得到了验证。
Feb, 2018
本文介绍了一种应用于非凸优化的三次正则化牛顿法,并提出了自适应方差调整的方案,通过对随机矩阵的三到四阶矩的分析来实现二阶保证,进而降低黑塞矩阵样本的复杂度。
Nov, 2018
本文提出一种基于子采样的方法,以降低 cubic regularization 方法的高计算复杂度,并利用浓度不等式提出相应的采样方案,从而在保证 cubic regularization 方法的全局和局部收敛性的同时,给出其全局收敛保证的首个子采样变体在非凸函数的设置中的实验证明。
May, 2017
该论文研究了优化非凸连续函数的问题,提出了一种名为 SSCN 的随机坐标二阶方法,通过在随机子空间应用立方正则化来降低使用二阶信息的计算复杂性,在高维场景中表现出了良好的适用性,并且通过提出自适应采样方案,实现了比传统一阶方法更快的速度。
Jun, 2024
我们提出了两种非常简单的随机二阶方法,用于最小化大量充分光滑和强凸函数的平均值。第一种是牛顿方法的随机变体(SN),第二种是具有立方正则化的牛顿方法的随机变体(SCN)。与现有的随机二阶方法不同,我们的方法没有这种缺点,例如,我们的方法的最简单的变体每次迭代只需要计算一个随机选择函数的梯度和海森矩阵。与大多数现有的随机牛顿和拟牛顿方法相比,人们的方法保证了比一阶 oracle 更快的本地收敛,同时适应了问题的曲率。有趣的是,我们的方法不是无偏的,因此我们的理论为设计新的随机方法提供了新的直觉。
Dec, 2019
本研究旨在探讨优化非光滑非凸正则化器下的平滑非凸损失函数的随机梯度方法。我们提出了两种简单的随机梯度算法,对于有限总和和一般随机优化问题,相较于现有技术水平,其具有更优的收敛复杂度。同时,我们在经验风险最小化中比较了两种算法的实际表现。
Jan, 2019
本文研究了立方正则化牛顿法在解决具有一致凸性目标的复合最小化问题时的迭代复杂度。在引入某种程度的二阶条件数的概念后,我们证明了在非退化情况下具有自适应正则化参数估计的方法具有线性收敛率。我们的算法自动实现了具有 H"older 连续的目标平滑部分的不同问题类别中均匀凸目标函数的全局最佳复杂度界限。作为我们发展的副产品,我们证明了牛顿法在具有一致有界二阶导数的强凸函数类上的全局迭代复杂度始终优于梯度法。
May, 2019
通过使用随机 TR 和 ARC 方法,我们可以在同时提供 Hessian 矩阵、梯度和函数值的不精确计算的基础上,减少每次迭代的传播开销,从而获得与之前研究中的准确计算同级别的迭代复杂度以实现近似二阶最优性,并通过有限和最小化问题中的随机采样技术满足不精确性的温和条件。数值实验支持这些发现,并表明我们的算法在进行相同或相似次数的迭代时,每次迭代所需的计算开销较当前的二阶方法更少。
Oct, 2023
提出了一种 Stochastic Variance-Reduced Cubic regularization (SVRC) 算法的改进型,叫做 Stochastic Recursive Variance-Reduced Cubic regularization (SRVRC) 算法,该算法结合递归更新的半随机梯度和 Hessian 估计器,可以更快更好地找到一个(ε,sqrt(ε))- 近似局部极小值点。并且在这个基础上,我们进一步提出了一种基于 SRVRC 的无 Hessian 的算法:SRVRC$_{ext {free}}$,它只需要随机梯度和 Hessian 向量积运算,并且达到更好的运算速度。
Jan, 2019