2022/08/11 by Lesi Chen, Luo Luo, Chen, Lesi +1 · 5 citations
Computer Science · Engineering · Mathematics · #Computer science #Convergence (economics) #Extension (predicate logic) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and ELM #Mathematical optimization #Mathematics #Minimax #Optimization problem #Oracle #Point (geometry) #Regular polygon #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Stochastic optimization
paper · pdf · doi:10.48550/arxiv.2208.05925
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2022/08/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We study the problem of finding a near-stationary point for smooth minimax optimization. The recently proposed extra anchored gradient (EAG) methods achieve the optimal convergence rate for the convex-concave minimax problem in the deterministic setting. However, the direct extension of EAG to stochastic optimization is not efficient. In this paper, we design a novel stochastic algorithm called Recursive Anchored IteratioN (RAIN). We show that the RAIN achieves near-optimal stochastic first-order oracle (SFO) complexity for stochastic minimax optimization in both convex-concave and strongly-convex-strongly-concave cases. In addition, we extend the idea of RAIN to solve structured nonconvex-nonconcave minimax problem and it also achieves near-optimal SFO complexity.