Exact and Inexact Subsampled Newton Methods for Optimization

By Raghu Bollapragada, Richard H. Byrd, Jorge Nocedal. 2016

197 citations recorded by the source corpus.

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 Hessian to yield a superlinear rate of convergence in expectation. The second part of the paper analyzes an inexact Newton method that solves linear systems approximately using the conjugate gradient (CG) method, and that samples the Hessian and not the gradient (the gradient is assumed to be exact). We provide a complexity analysis for this method based on the properties of the CG iteration and the quality of the Hessian approximation, and compare it with a method that employs a stochastic gradient iteration instead of the CG method. We report preliminary numerical results that illustrate the performance of inexact subsampled Newton methods on machine learning applications based on logistic regression.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “To reduce the dependence on the number of training examples, sub-sampled Newton methods [58, 59, 9, 21, 69] sample a smaller batch of points and use it to form the subsampled Hessian in each iteration.”
Subsampled inexact Newton methods for minimizing large sums of convex functions (2018, methodology): “On the other hand several papers investigate the use of second order methods in this framework and demonstrate advantages in some important problems if the second order methods are correctly implemented, [5, 8, 9, 16, 30, 31, 33, 34].”
Convergence Analysis of Inexact Randomized Iterative Methods (2019, methodology): “In particular on inexact variants of the Sketch-Newton method and subsampled Newton Method for minimize convex and non-convex functions [48, 2, 4, 56, 57, 58].”
An investigation of Newton-Sketch and subsampled Newton methods (2017, methodology): “Term 1 was analysed in [3], which establishes the bound”
Lower Bounds for Higher-Order Convex Optimization (2017, background): “Notably, the fastest theoretical running times for both convex (Agarwal et al., 2016; Xu et al., 2016; Bollapragada et al., 2016) and nonconvex (Agarwal et al.”
A Subsampling Line-Search Method with Second-Order Results (2018, methodology): “The column median loss [8-10]s shows the median loss over the last two seconds of the run.”
Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses (2019, methodology): “Many techniques for approximating linear systems have been used to compute ∆̃λ, in particular sketching of the Hessian matrix via fast transforms and subsampling (see [25, 8, 2] and references therein).”
On the Effectiveness of Parameter-Efficient Fine-Tuning (2022, methodology): “To solve this problem, we adopt the widely used technique (Dembo et al., 1982; Ricotti et al., 1988; Bishop and Nasrabadi, 2006; Bollapragada et al., 2019; Xu et al., 2020; Yao et al., 2021b,a) of approximating the Hessian matrix with a diagonal matrix denoted as We also assume that H is positive…”
A Progressive Batching L-BFGS Method for Machine Learning (2018, methodology): “Progressive batching (sometimes referred to as dynamic sampling) has been well studied in the optimization literature, both for stochastic gradient and subsampled Newtontype methods (Byrd et al., 2012; Friedlander & Schmidt, 2012; Cartis & Scheinberg, 2015; Pasupathy et al., 2015; Roosta-Khorasani &”
Optimization Methods for Supervised Machine Learning: From Linear Models to Deep Learning (2017, methodology): “Several variants of subsampled Newton methods have been proposed and analyzed for solving (strongly) convex formulations of problem (11) [68, 69, 25, 9, 87].”
A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization (2018, methodology): “fﬁ- ciently large. If ng k is increased at a rate that is faster than geometric and we have nh k→∞, then we obtain r-superlinear convergence with high probability. Similar results were established in [13, 72, 97] for stochastic Newton-typemethods forsmooth optimizationproblems. Clearly, the rate of ”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “In particular on inexact variants of the Sketch-Newton method and subsampled Newton Method for minimize convex and nonconvex functions [172, 9, 14, 204, 205, 207].”
ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning (2020, methodology): “To resolve this, one could use inexact Newton method, where an approximate Hessian operator is used instead of the Full Hessian inverse [5, 15, 54, 55, 60].”
Quasi-Newton Methods for Deep Learning: Forget the Past, Just Sample (2019, methodology): “[4] Raghu Bollapragada, Richard H Byrd, and Jorge Nocedal.”