Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation

Abstract

We consider stochastic second-order methods for minimizing smooth and strongly-convex functions under an interpolation condition satisfied by over-parameterized models. Under this condition, we show that the regularized subsampled Newton method (R-SSN) achieves global linear convergence with an adaptive step-size and a constant batch-size. By growing the batch size for both the subsampled gradient and Hessian, we show that R-SSN can converge at a quadratic rate in a local neighbourhood of the solution. We also show that R-SSN attains local linear convergence for the family of self-concordant functions. Furthermore, we analyze stochastic BFGS algorithms in the interpolation setting and prove their global linear convergence. We empirically evaluate stochastic L-BFGS and a "Hessian-free" implementation of R-SSN for binary classification on synthetic, linearly-separable datasets and real datasets under a kernel mapping. Our experimental results demonstrate the fast convergence of these methods, both in terms of the number of iterations and wall-clock time.

arXiv commentAISTATS, 2020

References in corpus (17)

• Optimizing Neural Networks with Kronecker-factored Approximate Curvature
• A Linearly-Convergent Stochastic L-BFGS Algorithm
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• Convergence rates of sub-sampled Newton methods
• Stop Wasting My Gradients: Practical SVRG
• Sub-Sampled Newton Methods I: Globally Convergent Algorithms
• Sub-Sampled Newton Methods II: Local Convergence Rates
• On exponential convergence of SGD in non-convex over-parametrized learning
• Big Batch SGD: Automated Inference using Adaptive Batch Sizes
• Kalman-based Stochastic Gradient Method with Stop Condition and Insensitivity to Conditioning
• A Variance Reduced Stochastic Newton Method
• Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
• Variable Metric Stochastic Approximation Theory
• Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization
• Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses
• On the Acceleration of L-BFGS with Second-Order Information and Stochastic Batches
• Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance

Cited by in corpus (3)

• Fast Linear Convergence of Randomized BFGS
• CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
• Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions