Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates

Abstract

We present two new remarkably simple stochastic second-order methods for minimizing the average of a very large number of sufficiently smooth and strongly convex functions. The first is a stochastic variant of Newton's method (SN), and the second is a stochastic variant of cubically regularized Newton's method (SCN). We establish local linear-quadratic convergence results. Unlike existing stochastic variants of second order methods, which require the evaluation of a large number of gradients and/or Hessians in each iteration to guarantee convergence, our methods do not have this shortcoming. For instance, the simplest variants of our methods in each iteration need to compute the gradient and Hessian of a {\em single} randomly selected function only. In contrast to most existing stochastic Newton and quasi-Newton methods, our approach guarantees local convergence faster than with first-order oracle and adapts to the problem's curvature. Interestingly, our method is not unbiased, so our theory provides new intuition for designing new stochastic methods.

arXiv comment16 pages, 2 figures, 3 algorithms, 2 theorems, 7 lemmas; to be presented at the NeurIPS workshop "Beyond First Order Methods in ML"

References in corpus (18)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• A Universal Catalyst for First-Order Optimization
• A Linearly-Convergent Stochastic L-BFGS Algorithm
• Optimization with First-Order Surrogate Functions
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• Proximal-Proximal-Gradient Method
• Minimizing Uniformly Convex Functions by Cubic Regularization of Newton Method
• Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
• A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite-Sum Structure
• One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods
• Adaptive Stochastic Variance Reduction for Subsampled Newton Method with Cubic Regularization
• A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions
• MISO is Making a Comeback With Better Proofs and Rates
• How Good is SGD with Random Shuffling?
• A Proximal Stochastic Quasi-Newton Algorithm

Cited by in corpus (5)

• Distributed Second Order Methods with Fast Rates and Compressed Communication
• Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning
• Convex optimization based on global lower second-order models
• SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters