On the Complexity of Nonconvex-Strongly-Concave Smooth Minimax Optimization Using First-Order Methods

The problem of minimax optimization arises in a wide range of applications. When the objective function is convex-concave, almost the full picture is known. However, the general nonconvex-concave setting is less understood. In this work, we study the complexity of nonconvex-strongly-concave minimax optimization using first-order methods. First, we provide a first-order oracle complexity lower bound for finding stationary points of nonconvex-strongly-concave smooth min-max optimization problems. We establish a lower bound of Ω ( √ 𝜅𝜖⁻²) for deterministic oracles, where 𝜖 defines the level of approximate stationarity and 𝜅 is the condition number, which matches the existing upper bound achieved in (Lin et al., 2020b) up to logarithmic factors. For stochastic oracles, we provide a lower bound of Ω (︀√ 𝜅𝜖⁻² + 𝜅 ¹/³ 𝜖 ⁻⁴)︀ . Second, we study the specific first-order algorithm, gradient descent-ascent (GDA). We show that for quadratic or nearly quadratic nonconvex-strongly-concave functions under our assumptions, two-time-scale GDA with appropriate stepsizes achieves a linear convergence rate. Then we also extend our result to stochastic gradient descent-ascent (SGDA).

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2021

Author dc:creator

• Li, Haochuan

Advisors dc:contributor.advisor

• Jadbabaie, Ali
• Rakhlin, Alexander

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/138938

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/138938