Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization

2022/08/11 by Lesi Chen, Luo Luo, Chen, Lesi +1 · 3 citations
Computer Science · Engineering · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and ELM #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2208.05925

openalex publication_date 2022/08/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Solutions of Two-stage Stochastic Minimax Problems
• Solving Convex-Concave Problems with O(ε^-4/7) Second-Order Oracle Complexity
• Pushing the Complexity Boundaries of Fixed-Point Equations: Adaptation to Contraction and Controlled Expansion

Related

• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• An Optimal Multistage Stochastic Gradient Method for Minimax Problems
• Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum
• Stochastic Approximation Proximal Subgradient Method for Stochastic Convex-Concave Minimax Optimization
• Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimization