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 ran-domized 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 [18].
Document type :
Conference papers
Complete list of metadatas

Cited literature [33 references]  Display  Hide  Download

https://hal.telecom-paristech.fr/hal-02365297
Contributor : Robert Gower <>
Submitted on : Friday, November 15, 2019 - 1:09:29 PM
Last modification on : Wednesday, November 20, 2019 - 1:37:06 AM

File

1905.10874.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02365297, version 1

Collections

Citation

Robert Gower, Dmitry Kovalev, Felix Lieder, Peter Richtárik. RSN: Randomized Subspace Newton. Conference on Neural Information Processing Systems, Dec 2019, Vancouver, Canada. ⟨hal-02365297⟩

Share

Metrics

Record views

7

Files downloads

6