Convergence linéaire des méthodes du gradient et du gradient proximal sous la condition de Polyak-Łojasiewicz.

En 1963, Polyak a proposé une condition simple qui est suffisante pour montrer un taux de convergence linéaire global pour la descente de gradient. Cette condition est un cas particulier de l'inégalité de Łojasiewicz proposée la même année, et elle ne nécessite pas de convexité forte (ou même de convexité). Dans ce travail, nous montrons que cette inégalité Polyak-Łojasiewicz (PL), beaucoup plus ancienne, est en fait plus faible que les principales conditions qui ont été explorées pour montrer des taux de convergence linéaires sans convexité forte au cours des 25 dernières années. Nous utilisons également l'inégalité PL pour donner de nouvelles analyses de la descente de coordonnées et du gradient stochastique pour de nombreuses fonctions non fortement convexes (et certaines non convexes). Nous proposons en outre une généralisation qui s'applique aux méthodes de gradient proximal pour l'optimisation non lisse, conduisant à des preuves simples de convergence linéaire pour les machines à vecteurs de support et les moindres carrés régularisés L1 sans hypothèses supplémentaires.