RSN: Randomized Subspace Newton - Télécom Paris Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

RSN: Randomized Subspace Newton

Résumé

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].
Fichier principal
Vignette du fichier
1905.10874.pdf (889.35 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02365297 , version 1 (15-11-2019)

Identifiants

  • HAL Id : hal-02365297 , version 1

Citer

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

Partager

Gmail Facebook X LinkedIn More