On the convergence of mirror descent beyond stochastic convex programming - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Optimization Année : 2020

On the convergence of mirror descent beyond stochastic convex programming

Résumé

In this paper, we examine a class of nonconvex stochastic opti- mization problems which we call variationally coherent , and which properly includes all quasi-convex programs. In view of solving such problems, we focus on the widely used stochastic mirror descent (SMD) family of algorithms, and we establish that the method’s last iterate converges with probability 1 . We further introduce a localized version of variational coherence which ensures local convergence of SMD with high probability. These results contribute to the landscape of nonconvex stochastic optimization by showing that quasicon- vexity is not essential for convergence: rather, variational coherence, a much weaker requirement, suffices. Finally, building on the above, we reveal an interesting insight regarding the convergence speed of SMD: in variationally coherent problems with sharp minima (e.g. generic linear programs), the last iterate of SMD reaches an exact global optimum in a finite number of steps (a.s.), even in the presence of persistent noise. This result is to be contrasted with existing work on black-box stochastic linear programs which only exhibit asymptotic convergence rates.
Fichier principal
Vignette du fichier
NonConvexMD.pdf (6.21 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01643346 , version 1 (07-12-2020)

Identifiants

Citer

Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Stephen Boyd, Peter W. Glynn. On the convergence of mirror descent beyond stochastic convex programming. SIAM Journal on Optimization, 2020, 30 (1), pp.687-716. ⟨10.1137/17M1134925⟩. ⟨hal-01643346⟩
298 Consultations
97 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More