Une approche plus simple de l'optimisation accélérée : la moyenne itérative rencontre l'optimisme

Récemment, plusieurs tentatives ont été faites pour étendre l'algorithme accéléré de Nesterov à l'optimisation stochastique lisse et à variance réduite. Dans cet article, les auteurs montrent qu'il existe une approche plus simple de l'accélération : appliquer des algorithmes d'apprentissage en ligne optimistes et interroger l'oracle du gradient à la moyenne en ligne des itérations d'optimisation intermédiaires.

En particulier, ils resserrent un résultat récent de Cutkosky (2019) pour démontrer théoriquement que la moyenne des itérations en ligne entraîne un écart d'optimisation réduit, indépendamment de l'algorithme impliqué. Ils montrent qu'en combinant soigneusement cette technique avec des algorithmes d'apprentissage en ligne optimistes génériques existants, on obtient les taux d'accélération optimaux pour l'optimisation d'objectifs fortement convexes et non fortement convexes, éventuellement composites, avec des oracles du premier ordre déterministes ou stochastiques. Les auteurs étendent ensuite cette idée à l'optimisation à variance réduite. Enfin, ils fournissent également des algorithmes universels qui atteignent le taux optimal pour les objectifs composites lisses et non lisses simultanément sans réglage supplémentaire, généralisant les résultats de Kavis et al. (2019) et résolvant un certain nombre de leurs problèmes ouverts.

Cet article a été publié lors de la 37e conférence internationale sur l'apprentissage automatique(ICML).