Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence
This provides a faster optimization method for large-scale problems in machine learning and convex programming, though it is incremental as it builds on existing Newton-type methods.
The authors tackled the problem of high computational cost in second-order optimization by proposing Newton Sketch, a randomized algorithm that approximates Newton steps using projected or sub-sampled Hessians. They proved it achieves super-linear convergence with high probability for self-concordant functions, with complexity independent of condition numbers, and demonstrated lower complexity than Newton's method in implementations.
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.