RSN: Randomized Subspace Newton

arXiv1905.10874MaRDI QIDQ6319396FDOQ6319396

Dmitry P. Kovalev, Felix Lieder, Robert M. Gower, Peter Richtárik

Publication date: 26 May 2019

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).

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Large-scale problems in mathematical programming (90C06) Random matrices (algebraic aspects) (15B52) Stochastic approximation (62L20) Randomized algorithms (68W20) Analysis of algorithms (68W40) Methods of quasi-Newton type (90C53) Stochastic and other probabilistic methods applied to problems in solid mechanics (74S60)

This page was built for publication: RSN: Randomized Subspace Newton

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6319396)