Sub-Sampled Newton Methods I: Globally Convergent Algorithms

By Farbod Roosta-Khorasani, Michael W. Mahoney. 2016

94 citations recorded by the source corpus.

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 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 and quantitative. Our algorithms are global and are guaranteed to converge from any initial iterate. Using random matrix concentration inequalities, one can sub-sample the Hessian to preserve the curvature information. Our first algorithm incorporates Hessian sub-sampling while using the full gradient. We also give additional convergence results for when the sub-sampled Hessian is regularized by modifying its spectrum or ridge-type regularization. Next, in addition to Hessian sub-sampling, we also consider sub-sampling the gradient as a way to further reduce the computational complexity per iteration. We use approximate matrix multiplication results from randomized numerical linear algebra to obtain the proper sampling strategy. In all these algorithms, computing the update boils down to solving a large scale linear system, which can be computationally expensive. As a remedy, for all of our algorithms, we also give global convergence results for the case of inexact updates where such linear system is solved only approximately. This paper has a more advanced companion paper, [42], in which we demonstrate that, by doing a finer-grained analysis, we can get problem-independent bounds for local convergence of these algorithms and explore trade-offs to improve upon the basic results of the present paper.

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.”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “(cid:13)(cid:13) (cid:13)(cid:13) (cid:13)(cid:13) (cid:13)(cid:13) For m = 1, our result (3) is the same as the stochastic Newton-type methods studied in (Roosta-Khorasani and Mahoney, 2016b, Xu et al., 2016, Pilanci and Wainwright, 2017).”
A Progressive Batching L-BFGS Method for Machine Learning (2018, background): “…well studied in the optimization literature, both for stochastic gradient and subsampled Newton-type methods (Byrd et al., 2012; Friedlander & Schmidt, 2012; Cartis & Scheinberg, 2015; Pasupathy et al., 2015; Roosta-Khorasani & Mahoney, 2016a;b; Bollapragada et al., 2016; 2017; De et al., 2017).”
Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method (2017, unknown): “These include subsampled Hessian (Erdogdu and Montanari, 2015; Pilanci and Wainwright, 2015; Roosta-Khorasani and Mahoney, 2016a,b), incremental Hessian updates (Gürbüzbalaban et al., 2015), stochastic dual Newton ascent (Qu et al., 2016), and stochastic quasi-Newton methods (Schraudolph et al.,…”
An investigation of Newton-Sketch and subsampled Newton methods (2017, methodology): “The search direction is the exact or inexact solution of the system of equations SSN methods have received considerable attention recently, and some of their theoretical properties are well understood [3, 8, 17].”
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].”
Sub-sampled Newton Methods with Non-uniform Sampling (2016, methodology): “In particular, [19, 20] consider a more general class of problems and, under a variety of conditions, thoroughly study the local and global convergence properties of sub-sampled Newton methods where the gradient and/or the Hessian are uniformly sub-sampled.”
ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning (2020, background): “There have also been multiple theoretical studies showing better convergence rate of second order based meth-ods [2, 3, 5, 10, 12, 13, 42, 52–54, 56, 60].”
A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization (2018, methodology): “ition (2.9) can be restrictive since an evaluation of the full objective function is required. However, similar descent conditions also appeared in other globalization strategies for smooth problems, [71, 92, 93, 96]. In the next section, we verify that Algorithm 1 using the proposed growth conditio”
Stochastic Block BFGS: Squeezing More Curvature out of Data (2016, methodology): “ubsampled gradient in calculating g t: Recently, there has been an eort to calculate H tusing subsampled Hessian matrices r2f T(x t), where T[n] is sampled uniformly at random and independently of S[6, 31]. The major diculty in this approach is that calculating r2f T(x t) can be computationally expe”
Newton-Stein Method: An Optimization Method for GLMs via Stein's Lemma (2015, background): “Set t = 0 and sub-sample a set of indices S ⊂ [ n ] uniformly at random.”
Subsampled inexact Newton methods for minimizing large sums of convex functions (2018, methodology): “Our analysis is strictly related to that developed in [5, 30, 31], where convergence of Inexact subsampled Newton methods is investigated both in probability [30, 31] and expectation [5].”
PyHessian: Neural Networks Through the Lens of the Hessian (2019, background): “For these problems, [10, 21, 43, 52] provide sketching/sampling techniques for Newton methods, where guarantees are established for sampling size and convergence rates; and [50–52, 55] show that sketching/sampling methods can significantly reduce the need for data in approximate Hessian computation.”
Exact and Inexact Subsampled Newton Methods for Optimization (2016, unknown): “Roosta-Khorasani and Mahoney [22, 23] derive global and local convergence rates for subsampled Newton methods with various sampling rates used for gradient and Hessian approximations.”