Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps

DOI10.1137/1.9781611977585.CH18arXiv2301.03931OpenAlexW4315779683MaRDI QIDQ6423017FDOQ6423017

Authors: Volkan Cevher, Georgios Piliouras, Ryann Sim, Stratis Skoulakis 

Publication date: 10 January 2023

Abstract: In this paper we present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems while requiring a simple and intuitive analysis. Similarly to the seminal work of Nemirovski and the recent approach of Piliouras et al. in normal form games, our work is based on the fact that the update rule of the Proximal Point method (PP) can be approximated up to accuracy $epsilon$ with only $O(log1/epsilon)$ additional gradient-calls through the iterations of a contraction map. Then combining the analysis of (PP) method with an error-propagation analysis we establish that the resulting first order method, called Clairvoyant Extra Gradient, admits near-optimal time-average convergence for general domains and last-iterate convergence in the unconstrained case.

Full work available at URL: https://doi.org/10.1137/1.9781611977585.ch18

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

This page was built for publication: Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6423017)