Inversion matricielle stochastique accélérée : General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization.

Résumé Nous présentons le premier algorithme randomisé accéléré pour la résolution de systèmes linéaires dans les espaces euclidiens. Un problème essentiel de ce type est le problème d'inversion de matrice. En particulier, notre algorithme peut être spécialisé pour inverser les matrices définies positives de telle sorte que tous les itérés (solutions approximatives) générés par l'algorithme sont eux-mêmes des matrices définies positives. Cela ouvre la voie à de nombreuses applications dans le domaine de l'optimisation et de l'apprentissage automatique. Comme application de notre théorie générale, nous développons les premières mises à jour quasi-Newton accélérées (déterministes et stochastiques). Nos mises à jour conduisent à des approximations plus agressives de l'inverse du Hessian, et permettent des gains de vitesse par rapport aux règles classiques non accélérées dans les expériences numériques. Des expériences de minimisation empirique du risque montrent que nos règles peuvent accélérer la formation de modèles d'apprentissage automatique.