2022/10/17 by Pouria Mahdavinia, Mahdavinia, Pouria, Yuyang Deng +5 · 5 citations
Computer Science · Engineering · Mathematics · Medicine · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optical Imaging and Spectroscopy Techniques #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.LG #math.OC #stat.ML
paper · pdf · doi:10.48550/arxiv.2210.09382
arxiv created 2022/10/17 · openalex publication_date 2022/10/17 · arxiv updated 2022/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Despite the established convergence theory of Optimistic Gradient Descent Ascent (OGDA) and Extragradient (EG) methods for the convex-concave minimax problems, little is known about the theoretical guarantees of these methods in nonconvex settings. To bridge this gap, for the first time, this paper establishes the convergence of OGDA and EG methods under the nonconvex-strongly-concave (NC-SC) and nonconvex-concave (NC-C) settings by providing a unified analysis through the lens of single-call extra-gradient methods. We further establish lower bounds on the convergence of GDA/OGDA/EG, shedding light on the tightness of our analysis. We also conduct experiments supporting our theoretical results. We believe our results will advance the theoretical understanding of OGDA and EG methods for solving complicated nonconvex minimax real-world problems, e.g., Generative Adversarial Networks (GANs) or robust neural networks training.