On the rate of convergence of Bregman proximal methods in constrained variational inequalities
Authors:
- Franck IutzelerFIFranck Iutzeler
- Jérôme MalickJMJérôme Malick
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemsMathematical Programming, 2019
- A simplified view of first order methods for optimizationMathematical Programming, 2018
- Learning in games with continuous action sets and unknown payoff functionsMathematical Programming, 2018
- Dual extrapolation and its applications to solving variational inequalities and related problemsMathematical Programming, 2006
- Interior projection-like methods for monotone variational inequalitiesMathematical Programming, 2005
- Information-based complexity of linear operator equationsJournal of Complexity, 1992
- Possible generalization of Boltzmann-Gibbs statisticsJournal of Statistical Physics, 1988
- A modification of the Arrow-Hurwicz method for search of saddle pointsMathematical Notes, 1980
- Ergodic convergence to a zero of the sum of monotone operators in Hilbert spaceJournal of Mathematical Analysis and Applications, 1979
- On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert spaceJournal of Mathematical Analysis and Applications, 1977