精确和非精确子采样牛顿法优化

Sep, 2016

Exact and Inexact Subsampled Newton Methods for Optimization

Raghu Bollapragada, Richard Byrd, Jorge Nocedal

TL;DR本文研究了通过子采样获得渐进和海森矩阵的近似解来解决随机优化问题，提出了利用这些近似的 Newton-like 方法，并讨论了如何协调渐进和海森矩阵的准确度，得到期望中的超线性收敛速度。该文第二部分分析了一种利用共轭梯度方法近似求解线性系统的不精确 Newton 方法，并且采样的是海森矩阵而不是梯度（梯度被认为是精确的）。我们提供了一种基于 CG 迭代和海森矩阵近似质量的复杂度分析，并将其与采用随机梯度迭代而不是 CG 方法的方法进行了比较。最后，我们报告了初步的数值结果，说明了在 logistic 回归的机器学习应用中，不精确子采样牛顿方法的表现。

Abstract

The paper studies the solution of stochastic optimization problems in which approximations to the gradient and Hessian are obtained through subsampling. We first consider Newton-like methods that employ these approximations and discuss how to coordinate the accuracy in the gradient and

stochastic optimization newton-like method conjugate gradient hessian approximation machine learning

发现论文，激发创造

不精确非凸牛顿类型方法

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

Feb, 2018

子采样牛顿法 I：全局收敛算法

本文论述了大规模优化问题中 Sub-sampling 的迭代算法，提供了 Hessian 和梯度子采样的收敛边界，使用随机数值线性代数来获得适当的采样策略，并为在大规模线性系统下近似更新的情况下的全局收敛结果提供了解决方案

Jan, 2016

Newton-Sketch 和子采样 Newton 方法的研究

本文研究了在解决变量数量和数据点数量都很大的有限和最优化问题的 Newton 法的背景下，两种数据空间维数缩减方法：Hessian 子采样和随机 Hadamard 变换。通过一系列数字实验和 Hessian 子采样方法的复杂性分析，揭示了使用共轭梯度方法相对于随机梯度迭代方法的优势。

May, 2017

子抽样牛顿法 II：局部收敛速率

考虑到大型数据的拟合应用中需要解决高维参数的大量函数之和的优化问题，本文运用子采样的方式以提高计算效率，并分析了牛顿方法中的 Hessian 矩阵和梯度的子采样对收敛速度的影响。

Jan, 2016

高效的子采样 Gauss-Newton 和自然梯度方法用于训练神经网络

使用 Levenberg-Marquardt 的 Gauss-Newton 和自然梯度方法，解决深度神经网络大量变量和海量数据集所产生的非凸优化问题，证明方法能够有效实现并提出数值结果。

Jun, 2019

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

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

May, 2015

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

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

Aug, 2017

次采样牛顿法的收敛速率

本文提出了一种结合子抽样技术与低秩逼近，收敛速度可与牛顿法相媲美但迭代成本较小的随机批量算法，且具有较强的鲁棒性和复合收敛速度，同时也能用于先前被提出的子抽样算法，并且应用于多个著名机器学习问题的数据集上，具有更好的效果。

Aug, 2015

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

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

Nov, 2018

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

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

Nov, 2013