Apr, 2020

关于经典拟牛顿法超线性收敛的新结果

PDF
TL;DR本文对凸性 Broyden 类的经典拟牛顿方法的本地超线性收敛进行了新的理论分析，从而得到了这些方法收敛速度的当前已知估计的显着改进，特别地，我们表明，Broyden-Fletcher-Goldfarb-Shanno 方法的相应速度仅取决于问题维数及其条件数的对数乘积。
local superlinear convergenceclassical quasi-newton methodsconvex broyden classconvergence ratesbroyden-fletcher-goldfarb-shanno method
发现论文，激发创造
  • 具有更快超线性收敛速度的增量拟牛顿方法

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

    Feb, 2024

  • 带有非渐进性超线性收敛速率的有限记忆贪婪拟牛顿法

    本研究提出了一种有界存储拟牛顿方法（LG-BFGS），通过在控制存储需求的情况下利用过去的曲率信息来实现非渐近超线性收敛，并在速度和存储需求之间找到了一种平衡。

    Jun, 2023

  • 带有线性和加速亚线性收敛速率的正则化凸优化的近端拟牛顿方法

    本文针对复合优化问题中一般且高效的不精确近端拟牛顿算法，在强凸目标函数下分析了其精确和不精确执行的收敛性质，并建立了一个简单的停止标准来改善其实用性。同时，对基于 FISTA 的近端拟牛顿算法进行加速，并与传统算法进行比较和分析，结果表明加速并没有带来任何好处。

    Jul, 2016

  • 在线有限内存 BFGS 算法的全局收敛性

    证明了解决大规模机器学习中随机目标优化问题的在线随机有限内存版本的 Broyden-Fletcher-Goldfarb-Shanno 拟牛顿法全局收敛性，数值实验证明其优于随机梯度下降算法。

    Sep, 2014

  • 随机拟牛顿更新是线性收敛的矩阵求逆算法

    研究发展了一类随机算法、其在矩阵反演、变量度量和大数据时代中的预处理等领域的应用，并成功实现并证明了块变量的几种拟牛顿法的随机版本，其中 AdaRBFGS 在大规模问题上表现卓越。

    Feb, 2016

  • 拟牛顿法：一个新方向

    该研究论文提出了新的概念，即将许多拟牛顿方法解释为贝叶斯线性回归的近似，为传统算法的某些缺点提供了解释，并展现了一种新的非参数拟牛顿方法，它能够以类似于以前版本的计算成本来更有效地利用可用的信息。

    Jun, 2012

  • 具有全局复杂度分析的实用不精确近端拟牛顿方法

    提出了一种稀疏优化的通用框架，使用了二阶信息和有限的 BFGS Hessian 逼近，通过坐标下降的方法解决问题，并对其全局收敛率进行了新颖的分析。

    Nov, 2013

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

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

    Dec, 2019

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

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

    Dec, 2014

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

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

    Feb, 2017