Last-Iterate Convergence Rates for Min-Max Optimization: Convergence of Hamiltonian Gradient Descent and Consensus Optimization
Abstract
While classic work in convex-concave min-max optimization relies on average-iterate convergence results, the emergence of nonconvex applications such as training Generative Adversarial Networks has led to renewed interest in last-iterate convergence guarantees. Proving last-iterate convergence is challenging because many natural algorithms, such as Simultaneous Gradient Descent/Ascent, provably diverge or cycle even in simple convex-concave min-max settings, and there are relatively few papers that prove global last-iterate convergence rates beyond the bilinear and convex-strongly concave settings. In this work, we show that the Hamiltonian Gradient Descent (HGD) algorithm achieves linear convergence in a variety of more general settings, including convex-concave problems that satisfy a "sufficiently bilinear" condition. We also prove convergence rates for stochastic HGD and for some parameter settings of the Consensus Optimization algorithm of Mescheder et al. (2017).
Cite
Text
Abernethy et al. "Last-Iterate Convergence Rates for Min-Max Optimization: Convergence of Hamiltonian Gradient Descent and Consensus Optimization." Proceedings of the 32nd International Conference on Algorithmic Learning Theory, 2021.Markdown
[Abernethy et al. "Last-Iterate Convergence Rates for Min-Max Optimization: Convergence of Hamiltonian Gradient Descent and Consensus Optimization." Proceedings of the 32nd International Conference on Algorithmic Learning Theory, 2021.](https://mlanthology.org/alt/2021/abernethy2021alt-lastiterate/)BibTeX
@inproceedings{abernethy2021alt-lastiterate,
title = {{Last-Iterate Convergence Rates for Min-Max Optimization: Convergence of Hamiltonian Gradient Descent and Consensus Optimization}},
author = {Abernethy, Jacob and Lai, Kevin A. and Wibisono, Andre},
booktitle = {Proceedings of the 32nd International Conference on Algorithmic Learning Theory},
year = {2021},
pages = {3-47},
volume = {132},
url = {https://mlanthology.org/alt/2021/abernethy2021alt-lastiterate/}
}