Convergence rates of sub-sampled Newton methods

Abstract

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.

Cited by in corpus (27)

• Sub-Sampled Newton Methods I: Globally Convergent Algorithms
• Sub-Sampled Newton Methods II: Local Convergence Rates
• Shampoo: Preconditioned Stochastic Tensor Optimization
• Efficient Second Order Online Learning by Sketching
• An empirical analysis of the optimization of deep network loss surfaces
• Scalable Second Order Optimization for Deep Learning
• Second-Order Methods with Cubic Regularization Under Inexact Information
• Stochastic Variance-Reduced Cubic Regularized Newton Method
• Convergence of Newton-MR under Inexact Hessian Information
• Robust Frequent Directions with Application in Online Learning
• Stochastic Block BFGS: Squeezing More Curvature out of Data
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update
• A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization
• Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses
• Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT
• Parallel Stochastic Newton Method
• Newton-Stein Method: An optimization method for GLMs via Stein's Lemma
• SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums
• High-Dimensional Optimization in Adaptive Random Subspaces
• Minimizing Oracle-Structured Composite Functions
• Subsampled Optimization: Statistical Guarantees, Mean Squared Error Approximation, and Sampling Method
• Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach
• Non-PSD Matrix Sketching with Applications to Regression and Optimization
• Generalization of Quasi-Newton Methods: Application to Robust Symmetric Multisecant Updates
• Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions