The rate of convergence of Bregman proximal methods: Local geometry vs. regularity vs. sharpness
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916518826082304 |
|---|---|
| author | Azizian, Waïss Iutzeler, Franck Malick, Jérôme Mertikopoulos, Panayotis |
| author_facet | Azizian, Waïss Iutzeler, Franck Malick, Jérôme Mertikopoulos, Panayotis |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_08043 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The rate of convergence of Bregman proximal methods: Local geometry vs. regularity vs. sharpness Azizian, Waïss Iutzeler, Franck Malick, Jérôme Mertikopoulos, Panayotis Optimization and Control Machine Learning Primary 65K15, 90C33, secondary 68Q25, 68Q32 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. |
| title | The rate of convergence of Bregman proximal methods: Local geometry vs. regularity vs. sharpness |
| topic | Optimization and Control Machine Learning Primary 65K15, 90C33, secondary 68Q25, 68Q32 |
| url | https://arxiv.org/abs/2211.08043 |