Sub-Sampled Newton Methods I: Globally Convergent Algorithms

Abstract

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.

References in corpus (5)

• Convergence rates of sub-sampled Newton methods
• Sub-Sampled Newton Methods II: Local Convergence Rates
• Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence
• Simultaneous Source for non-uniform data variance and missing data
• Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments

Cited by in corpus (36)

• Sub-sampled Newton Methods with Non-uniform Sampling
• A Progressive Batching L-BFGS Method for Machine Learning
• Sub-Sampled Newton Methods II: Local Convergence Rates
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• A Stochastic Line Search Method with Convergence Rate Analysis
• Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study
• PyHessian: Neural Networks Through the Lens of the Hessian
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Inexact Non-Convex Newton-Type Methods
• Stochastic Variance-Reduced Cubic Regularized Newton Method
• Robust Frequent Directions with Application in Online Learning
• Inexact Newton Methods for Stochastic Nonconvex Optimization with Applications to Neural Network Training
• An inexact subsampled proximal Newton-type method for large-scale machine learning
• A Stochastic Quasi-Newton Method with Nesterov's Accelerated Gradient
• Stochastic Block BFGS: Squeezing More Curvature out of Data
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• Stochastic Second-order Methods for Non-convex Optimization with Inexact Hessian and Gradient
• Regularization by Denoising Sub-sampled Newton Method for Spectral CT Multi-Material Decomposition
• Stochastic Second-Order Optimization via von Neumann Series
• Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
• Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation
• GPU Accelerated Sub-Sampled Newton's Method
• Newton-ADMM: A Distributed GPU-Accelerated Optimizer for Multiclass Classification Problems
• Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling
• LocalNewton: Reducing Communication Bottleneck for Distributed Learning
• Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method
• Randomized Approach to Nonlinear Inversion Combining Simultaneous Random and Optimized Sources and Detectors
• Parallel Stochastic Newton Method
• Differentiable Visual Computing
• Inefficiency of K-FAC for Large Batch Size Training
• Revisiting Sub-sampled Newton Methods
• Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods
• Low Rank Saddle Free Newton: A Scalable Method for Stochastic Nonconvex Optimization
• Convex optimization based on global lower second-order models
• Scalable Approximations for Generalized Linear Problems
• Curvature-Exploiting Acceleration of Elastic Net Computations