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

Understand

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.