MMDec, 2019

具有本地简单线性二次速度的随机牛顿和立方牛顿方法

PDF
TL;DR我们提出了两种非常简单的随机二阶方法，用于最小化大量充分光滑和强凸函数的平均值。第一种是牛顿方法的随机变体（SN），第二种是具有立方正则化的牛顿方法的随机变体（SCN）。与现有的随机二阶方法不同，我们的方法没有这种缺点，例如，我们的方法的最简单的变体每次迭代只需要计算一个随机选择函数的梯度和海森矩阵。与大多数现有的随机牛顿和拟牛顿方法相比，人们的方法保证了比一阶 oracle 更快的本地收敛，同时适应了问题的曲率。有趣的是，我们的方法不是无偏的，因此我们的理论为设计新的随机方法提供了新的直觉。
stochastic second-order methodsnewton's methodcubically regularized newton's methodconvergenceproblem curvature
发现论文，激发创造
  • 快速非凸优化的随机三次正则化

    本文提出了一个随机变体的经典算法 -- 立方正则化牛顿方法。该算法可以有效地避免鞍点问题，并在仅需要 $\mathcal {\tilde {O}}(\epsilon^{-3.5})$ 个随机梯度和随机海森向量乘积评估的情况下，为一般光滑的非凸函数找到近似的局部极小值。

    Nov, 2017

  • 随机方差减少的立方正则化牛顿法

    提出了随机方差约减的立方正则牛顿法，应用于非凸优化问题。该方法在半随机梯度和半随机海森矩阵的基础上工作，具有较低的复杂度，并在各种非凸优化问题上得到了验证。

    Feb, 2018

  • 立方正则化子空间牛顿法用于非凸优化

    该论文研究了优化非凸连续函数的问题，提出了一种名为 SSCN 的随机坐标二阶方法，通过在随机子空间应用立方正则化来降低使用二阶信息的计算复杂性，在高维场景中表现出了良好的适用性，并且通过提出自适应采样方案，实现了比传统一阶方法更快的速度。

    Jun, 2024

  • Newton Sketch：一种具有线性二次收敛率的线性时间优化算法

    该研究提出了一种随机化的二阶优化方法 ——Newton Sketch，使用随机投影或子采样 Hessian 实现近似牛顿步。对于自共轭函数，该算法证明具有超线性收敛和指数高概率，与条件数和相关问题独立的收敛和复杂度保证。对于适当的初始化，即使在没有自共轭的情况下，也可以保证类似的保证对于强凸和光滑的目标。我们还描述了将我们的方法扩展到具有自共轭屏障的凸约束程序。我们讨论和说明了其应用于线性程序，带有凸约束的二次程序，逻辑回归和其他广义线性模型以及半定规划的扩展问题。

    May, 2015

  • 非凸随机优化的随机拟牛顿方法

    本文介绍了基于随机梯度信息的非凸随机优化的随机拟牛顿方法，分别从框架、随机化和具体方法方面进行了研究，并提供了数值结果证明其高效性。

    Dec, 2014

  • 随机区块立方牛顿法

    通过随机块三次牛顿方法和近端算子，成功优化了三个可微，二次可微和非光滑项的凸函数求和问题，并在多个机器学习问题中实现了成功的优化。

    Feb, 2018

  • 锐化的惰性增量拟牛顿法

    本文提出了一种 Sharpened Lazy Incremental Quasi-Newton (SLIQN) 方法，旨在解决在大规模自然语言处理等复杂应用领域中，快速且高效地求解凸函数的优化问题。通过将经典的 BFGS 更新规则与贪婪法相结合，以及采用惰性更新策略，该方法取得了显著优于其他基于增量算法的类欧几里得方法的结果。

    May, 2023

  • 牛顿法三次正则化在最小化一致凸函数中的应用

    本文研究了立方正则化牛顿法在解决具有一致凸性目标的复合最小化问题时的迭代复杂度。在引入某种程度的二阶条件数的概念后，我们证明了在非退化情况下具有自适应正则化参数估计的方法具有线性收敛率。我们的算法自动实现了具有 H"older 连续的目标平滑部分的不同问题类别中均匀凸目标函数的全局最佳复杂度界限。作为我们发展的副产品，我们证明了牛顿法在具有一致有界二阶导数的强凸函数类上的全局迭代复杂度始终优于梯度法。

    May, 2019

  • 具有更快超线性收敛速度的增量拟牛顿方法

    本文提出了一种更高效的准牛顿方法，它将对称秩 - 1 更新纳入增量框架中，从而得到了不依赖条件数的局部超线性收敛速率。此外，我们通过在 Hessian 近似上应用块更新来提升方法，以实现更快的局部收敛速率。数值实验表明，所提出的方法明显优于基准方法。

    Feb, 2024

  • IQN：一种具有局部超线性收敛速率的增量拟牛顿方法

    本文提出一种增量式拟牛顿方法来最小化一个可用 n 个平滑和强凸函数表示的目标函数，该方法是一种随机和增量方法，每次迭代的成本与 n 无关，其收敛特性介于确定性和随机拟牛顿方法之间，利用聚合信息和泰勒展开近似函数、周期性更新目标函数等特性实现了在最优解局部范围内的局部超线性收敛率。

    Feb, 2017