Sub-Sampled Newton Methods II: Local Convergence Rates

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

86 citations recorded by the source corpus.

Many data-fitting applications require the solution of an optimization problem involving a sum of large number of functions of high dimensional parameter. Here, we consider the problem of minimizing a sum of $n$ functions over a convex constraint set $\mathcal{X} \subseteq \mathbb{R}^{p}$ where both $n$ and $p$ are large. In such problems, sub-sampling as a way to reduce $n$ can offer great amount of computational efficiency. Within the context of second order methods, we first give quantitative local convergence results for variants of Newton's method where the Hessian is uniformly sub-sampled. Using random matrix concentration inequalities, one can sub-sample in a way that the curvature information is preserved. Using such sub-sampling strategy, we establish locally Q-linear and Q-superlinear convergence rates. We also give additional convergence results for when the sub-sampled Hessian is regularized by modifying its spectrum or Levenberg-type regularization. Finally, in addition to Hessian sub-sampling, we consider sub-sampling the gradient as way to further reduce the computational complexity per iteration. We use approximate matrix multiplication results from randomized numerical linear algebra (RandNLA) to obtain the proper sampling strategy and we establish locally R-linear convergence rates. In such a setting, we also show that a very aggressive sample size increase results in a R-superlinearly convergent algorithm. While the sample size depends on the condition number of the problem, our convergence rates are problem-independent, i.e., they do not depend on the quantities related to the problem. Hence, our analysis here can be used to complement the results of our basic framework from the companion paper, [38], by exploring algorithmic trade-offs that are important in practice.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, 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 Computational Theory and Mathematics

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.”
Optimization Methods for Large-Scale Machine Learning (2016, background): “If done appropriately, Hessian subsampling is robust and effective [2, 28, 122, 132].”
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).”
Sub-Sampled Newton Methods I: Globally Convergent Algorithms (2016, methodology): “As a result, the local rates of the companion paper, SSN2 [42], coupled with the global convergence guarantees presented here, provide globally convergent algorithms with fast local rates (e.”
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).”
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): “Next, recall that in Table 1, we summarize the per-iteration complexity needed by our algorithm and other similar methods [20, 1, 18] to achieve a given local linear convergence rate.”
Do Subsampled Newton Methods Work for High-Dimensional Data? (2019, methodology): “If the loss function of (1) is non-quadratic, the Hessian matrix Ht changes with iteration, and we can only guarantee fast local convergence, as well as the prior works [Roosta Khorasani and Mahoney, 2016; Xu et al., 2016].”
A Survey of Optimization Methods From a Machine Learning Perspective (2019, methodology): “It estimates the product Hv by some technique, and thus is called “Hessian free”.”
Exact and Inexact Subsampled Newton Methods for Optimization (2016, methodology): “As in [1, 10, 21, 23, 26] this method employs the full gradient and approximates the Hessian by subsampling.”
A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization (2018, methodology): “A similar strategy was also used in [71, 72, 92, 97] for the analysis of pure, sub-sampled Newton methods for smooth optimization problems.”
Stable architectures for deep neural networks (2017, background): “A specific question is if the improvements in the forward propagation and regularization proposed in this paper will lead to better generalization properties of subsampled second-order methods such as [9, 36].”
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].”
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): “…A4 (Bounded Moments of Iterates) There is a constant γ > 0 such that for any iterate w k generated by the SSN-CG method (2.2) – (2.5), Assumption A1 has been weakened in [18] so that only the full Hessian ∇ 2 F is assumed positive definite, and not the Hessian of each individual component ∇ 2 F i .”