The rate of convergence of Bregman proximal methods: Local geometry vs. regularity vs. sharpness
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Learning in games with continuous action sets and unknown payoff functionsMathematical Programming, 2018
- Projected Reflected Gradient Methods for Monotone Variational InequalitiesSIAM Journal on Optimization, 2015
- Robust Stochastic Approximation Approach to Stochastic ProgrammingSIAM Journal on Optimization, 2009
- Primal-dual subgradient methods for convex problemsMathematical Programming, 2007
- Interior projection-like methods for monotone variational inequalitiesMathematical Programming, 2005
- Mirror descent and nonlinear projected subgradient methods for convex optimizationOperations Research Letters, 2003
- Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman FunctionsSIAM Journal on Optimization, 1993
- Possible generalization of Boltzmann-Gibbs statisticsJournal of Statistical Physics, 1988
- A modification of karmarkar's linear programming algorithmAlgorithmica, 1986
- The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programmingUSSR Computational Mathematics and Mathematical Physics, 1967