On the rate of convergence of Bregman proximal methods in constrained variational inequalities

Waïss Azizian (1, 2) , Franck Iutzeler (1) , Jérôme Malick (1) , Panayotis Mertikopoulos (2)

1 DAO - Données, Apprentissage et Optimisation
2 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems

We examine the last-iterate convergence rate of Bregman proximal methods - from mirror descent to mirror-prox - in constrained variational inequalities. Our analysis shows that the convergence speed of a given method depends sharply on the Legendre exponent of the underlying Bregman regularizer (Euclidean, entropic, or other), a notion that measures the growth rate of said regularizer near a solution. In particular, we show that boundary solutions exhibit a clear separation of regimes between methods with a zero and non-zero Legendre exponent respectively, with linear convergence for the former versus sublinear for the latter. This dichotomy becomes even more pronounced in linearly constrained problems where, specifically, Euclidean methods converge along sharp directions in a finite number of steps, compared to a linear rate for entropic methods.

Mots clés: Bregman methods; Variational inequalities

Domaines: Optimisation et contrôle [math.OC]

Waïss Azizian, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos. On the rate of convergence of Bregman proximal methods in constrained variational inequalities. 2022. ⟨hal-03873992⟩