W. Azizian, F. Iutzeler, J. Malick, and P. Mertikopoulos. Working paper.
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. More precisely, we show that boundary solutions exhibit a clear separation of regimes between methods having zero and non-zero Legendre exponent, with linear convergence for the former versus sublinear for the latter. This dichotomy becomes even more pronounced in linearly constrained problems where, in particular, Euclidean methods converge along sharp directions in a finite number of steps, compared to a linear rate for entropic methods.
arXiv link: https://arxiv.org/abs/2211.08043