RSN: Randomized Subspace Newton

Abstract

We develop a randomized Newton method capable of solving learning problems with huge dimensional feature spaces, which is a common setting in applications such as medical imaging, genomics and seismology. Our method leverages randomized sketching in a new way, by finding the Newton direction constrained to the space spanned by a random sketch. We develop a simple global linear convergence theory that holds for practically all sketching techniques, which gives the practitioners the freedom to design custom sketching approaches suitable for particular applications. We perform numerical experiments which demonstrate the efficiency of our method as compared to accelerated gradient descent and the full Newton method. Our method can be seen as a refinement and randomized extension of the results of Karimireddy, Stich, and Jaggi (2019).

21 pages, 3 figures

References in corpus (7)

• OpenML: networked science in machine learning
• Efficient Second Order Online Learning by Sketching
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
• A new framework for the computation of Hessians
• Randomized Block Cubic Newton Method

Cited by in corpus (1)

• A probabilistic generative model for semi-supervised training of coarse-grained surrogates and enforcing physical constraints through virtual observables