# The rate of convergence of Bregman proximal methods: Local geometry vs. regularity vs. sharpness

arXiv: https://arxiv.org/abs/2211.08043 · HTML: https://mlsanity.com/paper/2211.08043/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 15 references that are in the map.
- First posted on arXiv 15 Nov 2022.

## Builds on (most cited first, 2 of 2)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)

## Abstract (arXiv)

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.