RSN : Randomized Subspace Newton.

Résumé Nous développons une méthode de Newton randomisée capable de résoudre des problèmes d'apprentissage avec des espaces de caractéristiques de très grande dimension, ce qui est un cadre commun dans des applications telles que l'imagerie médicale, la génomique et la sismologie. Notre méthode exploite l'esquisse ran-domisée d'une nouvelle manière, en trouvant la direction de Newton contrainte à l'espace couvert par une esquisse aléatoire. Nous développons une théorie de convergence linéaire globale simple qui s'applique à pratiquement toutes les techniques d'esquisse, ce qui donne aux praticiens la liberté de concevoir des approches d'esquisse personnalisées adaptées à des applications particulières. Nous réalisons des expériences numériques qui démontrent l'efficacité de notre méthode par rapport à la descente de gradient accélérée et à la méthode complète de Newton. Notre méthode peut être considérée comme un raffinement et une extension aléatoire des résultats de Karimireddy, Stich et Jaggi [18].