2023/03/30 by Quoc Tran-Dinh, Tran-Dinh, Quoc
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Matrix Theory and Algorithms #Optimization and Control (math.OC) #Optimization and Variational Analysis
paper · pdf · doi:10.48550/arxiv.2303.17192
openalex publication_date 2023/03/30 · openalex created_date 2023/04/05 · openalex updated_date 2026/07/28
The extragradient (EG), introduced by G. M. Korpelevich in 1976, is a well-known method to approximate solutions of saddle-point problems and their extensions such as variational inequalities and monotone inclusions. Over the years, numerous variants of EG have been proposed and studied in the literature. Recently, these methods have gained popularity due to new applications in machine learning and robust optimization. In this work, we survey the latest developments in the EG method and its variants for approximating solutions of nonlinear equations and inclusions, with a focus on the monotonicity and co-hypomonotonicity settings. We provide a unified convergence analysis for different classes of algorithms, with an emphasis on sublinear best-iterate and last-iterate convergence rates. We also discuss recent accelerated variants of EG based on both Halpern fixed-point iteration and Nesterov's accelerated techniques. Our approach uses simple arguments and basic mathematical tools to make the proofs as elementary as possible, while maintaining generality to cover a broad range of problems.