Last-iterate convergence rates for min-max optimization

By Jacob D. Abernethy, Kevin A. Lai, Andre Wibisono. 2019

75 citations recorded by the source corpus.

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 previous work on global last-iterate convergence rates has been limited to 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 similar convergence rates for the Consensus Optimization (CO) algorithm of [MNG17] for some parameter settings of CO.

Subfields: Artificial Intelligence, Management Science and Operations Research, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “Abernethy et al. [2021] show that CO can be viewed as a perturbation of the deterministic Hamiltonian gradient descent (HGD) and explain how CO converges at the same rate as HGD, while Azizian et al. [2020] prove convergence of CO for μ-strongly monotone operators with positive singular values of th”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “, 2017) and Hamiltonian gradient descent (Balduzzi et al., 2018; Abernethy et al., 2019).”
The complexity of constrained min-max optimization (2020, background): “by [1]; and (II) some type of approximate local min-max solution.”
Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems (2020, methodology): “Abernethy et al. (2019) proved linear last-iterate convergence rates for Hamiltonian gradient descent when f belongs to a class of ‘sufficiently bilinear’ (possibly nonconvex-nonconcave) problems. Although their result does generalize the strongly convex-strongly concave and bilinear cases, it does ”
Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems (2020, background): “…recent surge in research on solving minimax optimization beyond the convex-concave regime [Sinha et al., 2017, Chen et al., 2017, Qian et al., 2019, Thekumparampil et al., 2019, Lin et al., 2018, Nouiehed et al., 2019, Abernethy et al., 2019], but they diﬀer from our work from various perspectives.”
Accelerating Smooth Games by Manipulating Spectral Shapes (2020, background): “Note that, choosing τ of this order is what is done by Abernethy et al. (2019) for (non-accelerated) CO.”
A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Differentiable Games (2020, methodology): “It has been analysed by Abernethy et al. (2019) as a perturbation of Hamiltonian gradient descent.”