Sub-Sampled Newton Methods I: Globally Convergent Algorithms
Farbod Roosta-Khorasani International Computer Science Institute, Berkeley, CA 94704 and Department of Statistics, University of California at Berkeley, Berkeley, CA 94720. Michael W. Mahoney
Abstract
Large scale optimization problems are ubiquitous in machine learning and data analysis and there is a plethora of algorithms for solving such problems. Many of these algorithms employ sub-sampling, as a way to either speed up the computations and/or to implicitly implement a form of statistical regularization. In this paper, we consider second-order iterative optimization algorithms, i.e., those that use Hessian as well as gradient information, and we provide bounds on the convergence of the variants of Newton’s method that incorporate uniform sub-sampling as a means to estimate the gradient and/or Hessian. Our bounds are non-asymptotic, i.e., they hold for finite number of data points in finite dimensions for finite number of iterations. In addition, they are quantitative and depend on the quantities related to the problem, i.e., the condition number. However, our algorithms are global and are guaranteed to converge from any initial iterate.
中文速览
大规模机器学习中常见的优化问题，光靠一阶梯度方法往往收敛慢，牛顿法等二阶方法虽然收敛更快，但在数据量和参数量都极大时，每次迭代都要计算完整的 Hessian 矩阵，代价高到几乎无法承受。本文提出了一类"子采样牛顿法（sub-sampled Newton methods）"：用随机矩阵浓度不等式保证对 Hessian 和梯度分别进行均匀随机采样后，曲率信息依然足够可靠；同时借助随机数值线性代数（RandNLA）中的近似矩阵乘法结果，确定了梯度子采样的正确策略，并进一步允许每步的线性方程组以近似解代替精确解，从而降低每轮迭代的实际计算量。分析给出了非渐近、定量的全局收敛保证——收敛率以条件数等问题参数明确表达，且算法从任意初始点出发均能收敛，而不依赖"已足够接近最优解"的局部假设。这是首批对子采样二阶算法在多种设置下给出完整定量全局收敛分析的工作，为大规模实际问题中安全使用二阶优化方法奠定了理论基础。
原文 arXiv:1601.04737;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1601.04737v3