带有非均匀采样的子采样牛顿方法

Jul, 2016

带有非均匀采样的子采样牛顿方法

Sub-sampled Newton Methods with Non-uniform Sampling

Peng Xu, Jiyan Yang, Farbod Roosta-Khorasani, Christopher Ré, Michael W. Mahoney

TL;DR考虑使用面向低秩分解的凸函数 F (w) 最小化问题，提出一种基于不均匀子采样和不精确更新的随机牛顿型算法来降低计算复杂度，研究了两个基于块范数平方和块部分杠杆分数的非均匀采样分布，理论和实验都表明此类算法具有线性 - 二次收敛率，相较于现有方法，具有更低的计算复杂度和更好的计算鲁棒性。

Abstract

We consider the problem of finding the minimizer of a convex function $F: \mathbb R^d \rightarrow \mathbb R$ of the form $F(w) := \sum_{i=1}^n f_i(w) + R(w)$ where a low-rank factorization of $\nabla^2 f_i(w)$ is readily available. We consider the regime where $n \gg d$. As second-orde

convex function randomized newton-type algorithms non-uniform sampling linear-quadratic convergence rate computational complexity

发现论文，激发创造

次采样牛顿法的收敛速率

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

Aug, 2015

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

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

Jan, 2016

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

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

Jan, 2016

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

本文提出了一种快速的随机拟牛顿方法，针对平滑性不均匀的情况，通过梯度剪切和方差减小，实现了最优的 O (ε^(-3)) 样本复杂度，并通过简单的超参数调节实现了收敛加速，数值实验证明了该算法优于现有方法。

Mar, 2024

不精确非凸牛顿类型方法

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

Feb, 2018

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

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

Nov, 2018

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

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

Jun, 2019

非凸优化的子采样三次正则化

本文提出一种基于子采样的方法，以降低 cubic regularization 方法的高计算复杂度，并利用浓度不等式提出相应的采样方案，从而在保证 cubic regularization 方法的全局和局部收敛性的同时，给出其全局收敛保证的首个子采样变体在非凸函数的设置中的实验证明。

May, 2017

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

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

Jun, 2024

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

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

Sep, 2016