Convergence rates of sub-sampled Newton methods

By Murat A. Erdogdu, Andrea Montanari. 2015

167 citations recorded by the source corpus.

We consider the problem of minimizing a sum of $n$ functions over a convex parameter set $\mathcal{C} \subset \mathbb{R}^p$ where $n\gg p\gg 1$. In this regime, algorithms which utilize sub-sampling techniques are known to be effective. In this paper, we use sub-sampling techniques together with low-rank approximation to design a new randomized batch algorithm which possesses comparable convergence rate to Newton's method, yet has much smaller per-iteration cost. The proposed algorithm is robust in terms of starting point and step size, and enjoys a composite convergence rate, namely, quadratic convergence at start and linear convergence when the iterate is close to the minimizer. We develop its theoretical analysis which also allows us to select near-optimal algorithm parameters. Our theoretical results can be used to obtain convergence rates of previously proposed sub-sampling based algorithms as well. We demonstrate how our results apply to well-known machine learning problems. Lastly, we evaluate the performance of our algorithm on several datasets under various scenarios.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Optimization & Training

Citations in the corpus

Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “Erdogdu and Montanari (2015) propose the NewSamp method that subsamples the Hessian followed by a regularized truncated SVD to form the inverse Hessian approximation.”
An empirical analysis of the optimization of deep network loss surfaces (2016, background): “The speed of gradient-descent-based algorithms are generally measured on strictly convex, in particular, quadratic functions [5, 10, 22, 23, 25].”
Shampoo: Preconditioned Stochastic Tensor Optimization (2018, background): “, 2011; Kingma and Ba, 2014), a sketched version (Gonen and Shalev-Shwartz, 2015; Pilanci and Wainwright, 2017), or various estimations thereof (Erdogdu and Montanari, 2015; Agarwal et al., 2016; Xu et al., 2016).”
Exact and Inexact Subsampled Newton Methods for Optimization (2016, methodology): “Erdogdu and Montanari [10] study a Newton-like method where the Hessian approximation is obtained by first subsampling the true Hessian and then computing a truncated eigenvalue decomposition.”
Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses (2019, methodology): “In this paper, we argue that the three reasons above for not using Newton method can be circumvented to obtain competitive algorithms: (1) high absolute precisions are indeed not needed for machine learning, but faced with strongly ill-conditioned problems, even a low-precision solution requires sec”
Subsampled inexact Newton methods for minimizing large sums of convex functions (2018, background): “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].”
An investigation of Newton-Sketch and subsampled Newton methods (2017, methodology): “Second order optimization methods that employ Hessian subsampling techniques have been studied in [2, 5, 6, 13, 16, 18, 20–22].”
A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization (2018, methodology): “Erdogdu and Mon- tanari [25] derive convergence rates of a projected sub-sampled Newton method with rank thresholding.”
Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method (2017, methodology): “The philosophy also differs from stochastic second order methods such as subsampled Newton [9,25,28,29], incremental Hessian [10], stochastic dual Newton ascent [26], and stochastic quasi-Newton methods [14, 17–19, 21, 31].”
The Case for Full-Matrix Adaptive Regularization (2018, unknown): “…some are viable for large-scale implementation, these quasi-Newton methods, along with (subsampled, online, cubic-regularized) Newton methods [EM15, ABH17, LACBL16, HAK07, AAZB + 17, CDHS17] exhibit very diﬀerent dynamics than the standard optimizers in deep learning, and thus have not seen…”
Newton-Stein Method: An Optimization Method for GLMs via Stein's Lemma (2015, methodology): “This is because, important curvature information is generally contained in the largest few spectral features (Erdogdu and Montanari, 2015).”
Accelerating SVRG via second-order information (2015, background): “However, as noted in the recent work [6], a subsampled Hessian is able to capture accurate information only about the high curvature directions.”
Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy (2016, methodology): “They do improve convergence constants in ill-conditioned problems but they still converge at linear rates.”
Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage (2017, methodology): “The methods based on CGM only need the top eigenvector, so they perform less arithmetic per iteration.”
Sub-sampled Newton Methods with Non-uniform Sampling (2016, methodology): “As the mere evaluation of H(w) grows linearly in n, a natural idea is to use uniform sub-sampling {∇(2)fi(w)}i=1 as a way to reduce the cost of such evaluation [7, 19, 20].”
Diving into the shallows: a computational perspective on large-scale shallow learning (2017, methodology): “We note the work [EM15] which analyzed a hybrid first/second order method for general convex optimization with a rescaling term based on the top eigenvectors of the Hessian.”