Sep, 2023

带有延迟近似 Hessian 矩阵的正则化牛顿方法的一阶和零阶实现

PDF
TL;DR我们开发了 Cubically regularized Newton 方法的一阶 (无 Hessian 矩阵) 和零阶 (无导数) 的实现，用于解决一般的非凸优化问题，通过有限差分逼近导数。我们在算法中使用了一种特殊的自适应搜索过程，同时适应正则化常数和有限差分逼近的参数。此方法不需要知道实际的 Lipschitz 常数。此外，我们还为算法增加了惰性 Hessian 更新，重复使用之前计算的 Hessian 近似矩阵进行多个迭代。具体地，我们证明了新的一阶 Hessian-free 方法的全局复杂度界为 O (n^1/2 * ε^-3/2) 个函数和梯度评估，并且零阶无导数方法的函数评估复杂度界为 O (n^3/2 * ε^-3/2)，其中 n 是问题的维度，ε 是梯度范数的期望精度。这些复杂度界显著提高了关于 n 和 ε 的联合依赖的先前已知界，用于一阶和零阶非凸优化。
cubically regularized newton methodnon-convex optimization problemsfinite difference approximationsadaptive search procedureglobal complexity bound
发现论文，激发创造
  • 牛顿法三次正则化在最小化一致凸函数中的应用

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

    May, 2019

  • 非凸优化中不精确 Hessian 信息的牛顿类型方法

    本文研究了基于 Hessian 矩阵近似的非凸优化中信任域和立方正则化方法的变体。通过对不精确 Hessian 矩阵的渐进解和相应子问题的近似解，提供了迭代复杂度，以实现达到二阶最优条件的近似解，并且在现有文献中条件松弛。

    Aug, 2017

  • 快速非凸优化的随机三次正则化

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

    Nov, 2017

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

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

    Feb, 2018

  • 不精确非凸牛顿类型方法

    提出了非凸问题的近似解决方案；采用了三次正则化和信任域算法的不精确变体，并且可以应用于有限和问题，通过随机子采样法对梯度和 Hessian 进行适当精度逼近，实现了计算效率与最优迭代复杂度的权衡。

    Feb, 2018

  • 非凸优化的加速方法

    通过使用只需要计算梯度的加速梯度方法，该论文提出了一种快速求解具有 Lipschitz 连续的一阶和二阶导数的非凸优化问题的算法，该方法相较于梯度下降算法在复杂度和精度上都表现更优。

    Nov, 2016

  • Krylov 立方正则牛顿：一种无维度收敛速度的子空间二阶方法

    该研究介绍了一种新的子空间三阶正则牛顿方法，其在解决凸优化问题时具有与维度无关的全局收敛速度，并且在特定谱条件下能恢复到完全维度的三阶正则牛顿方法的收敛速度，数值实验表明该方法比现有的随机子空间方法收敛更快，尤其在高维问题上。

    Jan, 2024

  • 适应性随机方差减少的子采样牛顿方法与立方正则化

    本文介绍了一种应用于非凸优化的三次正则化牛顿法，并提出了自适应方差调整的方案，通过对随机矩阵的三到四阶矩的分析来实现二阶保证，进而降低黑塞矩阵样本的复杂度。

    Nov, 2018

  • 无梯度的零阶方法高效避免鞍点

    本文研究了非凸优化中的无导数算法，利用有限差分器进行梯度逼近，最终提出了一种使用嘈杂的零阶方法来避免鞍点的算法，并在收敛速度上达到了与精确梯度接近的性能。

    Oct, 2019

  • 非凸随机零阶优化：处理约束、高维度和鞍点

    本文提出了针对非凸和凸优化的零阶随机逼近算法，并关注解决约束优化、高维设置和避免鞍点等问题。我们探索了结构稀疏假设的优点，并提出了一种使用零阶信息的被截断随机梯度算法和一种避免鞍点的算法，并讨论了它们的收敛率。

    Sep, 2018