Linear Last-iterate Convergence in Constrained Saddle-point Optimization

Chen-Yu Wei; Chung-Wei Lee; Mengxiao Zhang; Haipeng Luo

doi:10.48550/arxiv.2006.09517

Back

Linear Last-iterate Convergence in Constrained Saddle-point Optimization

Preprint

Open access

Linear Last-iterate Convergence in Constrained Saddle-point Optimization

Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang and Haipeng Luo

arXiv (Cornell University)

03/19/2021

DOI: 10.48550/arxiv.2006.09517

Files and links (1)

url

https://doi.org/10.48550/arXiv.2006.09517View

Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative Weights Update (OMWU) for saddle-point optimization have received growing attention due to their favorable last-iterate convergence. However, their behaviors for simple bilinear games over the probability simplex are still not fully understood - previous analysis lacks explicit convergence rates, only applies to an exponentially small learning rate, or requires additional assumptions such as the uniqueness of the optimal solution. In this work, we significantly expand the understanding of last-iterate convergence for OGDA and OMWU in the constrained setting. Specifically, for OMWU in bilinear games over the simplex, we show that when the equilibrium is unique, linear last-iterate convergence is achieved with a learning rate whose value is set to a universal constant, improving the result of (Daskalakis & Panageas, 2019b) under the same assumption. We then significantly extend the results to more general objectives and feasible sets for the projected OGDA algorithm, by introducing a sufficient condition under which OGDA exhibits concrete last-iterate convergence rates with a constant learning rate whose value only depends on the smoothness of the objective function. We show that bilinear games over any polytope satisfy this condition and OGDA converges exponentially fast even without the unique equilibrium assumption. Our condition also holds for strongly-convex-strongly-concave functions, recovering the result of (Hsieh et al., 2019). Finally, we provide experimental results to further support our theory.

Computer Science - Computer Science and Game Theory

Computer Science - Learning

Statistics - Machine Learning

Details

Title: Subtitle: Linear Last-iterate Convergence in Constrained Saddle-point Optimization
Creators: Chen-Yu Wei - University of Southern California
Chung-Wei Lee
Mengxiao Zhang - University of Southern California
Haipeng Luo - Southern California University for Professional Studies
Resource Type: Preprint
Publication Details: arXiv (Cornell University)
DOI: 10.48550/arxiv.2006.09517
eISSN: 2331-8422
Language: English
Date posted: 03/19/2021
Academic Unit: Business Analytics
Record Identifier: 9984701828602771

Metrics

1 Record Views