Méthodes de Newton globalement convergentes pour les pertes autoconcordantes généralisées mal conditionnées.

Résumé Dans cet article, nous étudions les algorithmes d'optimisation convexe à grande échelle basés sur la méthode de Newton appliquée aux pertes autoconcordantes généralisées régularisées, qui comprennent la régression logistique et la régression softmax. Nous prouvons d'abord que notre nouveau schéma simple basé sur une séquence de problèmes avec des paramètres de régularisation décroissants est globalement convergent, que cette convergence est linéaire avec un facteur constant qui n'évolue que logarithmiquement avec le nombre de conditions. Dans le cadre paramétrique, nous obtenons un algorithme avec la même échelle que les méthodes régulières du premier ordre mais avec un comportement amélioré, en particulier dans les problèmes mal conditionnés. Deuxièmement, dans le cadre de l'apprentissage automatique non paramétrique, nous fournissons un algorithme explicite combinant le schéma précédent avec les techniques de projection de Nyström, et nous prouvons qu'il atteint des limites de généralisation optimales avec une complexité temporelle d'ordre O(ndf λ), une complexité mémoire d'ordre O(df 2 λ) et aucune dépendance du nombre de conditions, généralisant les résultats connus pour la régression des moindres carrés. Ici, n est le nombre d'observations et df λ est le nombre de degrés de liberté associé. En particulier, il s'agit du premier algorithme à grande échelle pour résoudre les régressions logistiques et softmax dans le cadre non-paramétrique avec de grands nombres de condition et des garanties théoriques.