Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence

Abstract

We propose a randomized second-order method for optimization known as the Newton Sketch: it is based on performing an approximate Newton step using a randomly projected or sub-sampled Hessian. For self-concordant functions, we prove that the algorithm has super-linear convergence with exponentially high probability, with convergence and complexity guarantees that are independent of condition numbers and related problem-dependent quantities. Given a suitable initialization, similar guarantees also hold for strongly convex and smooth objectives without self-concordance. When implemented using randomized projections based on a sub-sampled Hadamard basis, the algorithm typically has substantially lower complexity than Newton's method. We also describe extensions of our methods to programs involving convex constraints that are equipped with self-concordant barriers. We discuss and illustrate applications to linear programs, quadratic programs with convex constraints, logistic regression and other generalized linear models, as well as semidefinite programs.

References in corpus (11)

• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares

Cited by in corpus (23)

• Sub-sampled Newton Methods with Non-uniform Sampling
• Sub-Sampled Newton Methods I: Globally Convergent Algorithms
• Sub-Sampled Newton Methods II: Local Convergence Rates
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Efficient Second Order Online Learning by Sketching
• Second-Order Stochastic Optimization for Machine Learning in Linear Time
• Inexact Non-Convex Newton-Type Methods
• Structured adaptive and random spinners for fast machine learning computations
• Statistical Inference for the Population Landscape via Moment Adjusted Stochastic Gradients
• Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms
• Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices
• Stochastic Second-Order Optimization via von Neumann Series
• Long-Step Path-Following Algorithm for Quantum Information Theory: Some Numerical Aspects and Applications
• DUAL-LOCO: Distributing Statistical Estimation Using Random Projections
• Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling
• Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses
• Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method
• Revisiting Sub-sampled Newton Methods
• Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data
• Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods
• TripleSpin - a generic compact paradigm for fast machine learning computations
• Scalable Approximations for Generalized Linear Problems
• Exploiting the Structure via Sketched Gradient Algorithms