The rate of convergence of Bregman proximal methods: Local geometry vs. regularity vs. sharpness
This work provides theoretical insights into optimization algorithm performance, addressing a foundational problem in machine learning and optimization, but it is incremental as it builds on existing Bregman method frameworks.
The paper analyzes the convergence rates of Bregman proximal methods for variational inequalities, showing that rates depend on the Legendre exponent of the Bregman function, with linear convergence for zero exponents and sublinear for non-zero ones, and specific examples like entropic regularization achieving linear rates in sharp directions.
We examine the last-iterate convergence rate of Bregman proximal methods - from mirror descent to mirror-prox and its optimistic variants - as a function of the local geometry induced by the prox-mapping defining the method. For generality, we focus on local solutions of constrained, non-monotone variational inequalities, and we show that the convergence rate of a given method depends sharply on its associated Legendre exponent, a notion that measures the growth rate of the underlying Bregman function (Euclidean, entropic, or other) near a solution. In particular, we show that boundary solutions exhibit a stark separation of regimes between methods with a zero and non-zero Legendre exponent: the former converge at a linear rate, while the latter converge, in general, sublinearly. This dichotomy becomes even more pronounced in linearly constrained problems where methods with entropic regularization achieve a linear convergence rate along sharp directions, compared to convergence in a finite number of steps under Euclidean regularization.