mlsanityData to 7 Oct 2026

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

arXiv 2208.05925 ↗First posted 11 Aug 2022cs.LGcited by 19

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). Builds on 25 of its 38 references that are in the map. First posted on arXiv 11 Aug 2022.

Builds on

25 of 38 references.

References · 25

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  4. 2017Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observabilitycited by 143
  5. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  6. 2022AUC Maximization in the Era of Big Data and AI: A Surveycited by 100
  7. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  8. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 71
  9. 2019Stochastic AUC Maximization with Deep Neural Networkscited by 61
  10. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 61
  11. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 55
  12. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 46
13 more
  1. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  2. 2019A Decentralized Parallel Algorithm for Training Generative Adversarial Netscited by 43
  3. 2018Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimizationcited by 40
  4. 2018First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problemscited by 33
  5. 2019The Complexity of Making the Gradient Small in Stochastic Convex Optimizationcited by 33
  6. 2021Stochastic Bias-Reduced Gradient Methodscited by 25
  7. 2022Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimizationcited by 22
  8. 2021Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexitycited by 21
  9. 2022The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimizationcited by 20
  10. 2021Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimizationcited by 15
  11. 2017Boosting the Actor with Dual Criticcited by 14
  12. 2020Gradient Free Minimax Optimization: Variance Reduction and Faster Convergencecited by 11
  13. 2021On the Initialization for Convex-Concave Min-max Problemscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 1; 2024: 3; 2025: 2; 2026: 12.

19 papers.

Sort:

  1. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 13
  2. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  3. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 10
  4. 2024Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexitycited by 4
  5. 2024Second-Order Min-Max Optimization with Lazy Hessianscited by 4
  6. 2024A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problemscited by 3
  7. 2026Solving Stochastic Fixed-Point Equations with High Probabilitycited by 3
  8. 2026Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularizationcited by 3
  9. 2026An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascentcited by 2
  10. 2026How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyondcited by 1
  11. 2025Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexitycited by 0
  12. 2026Accelerated and Stable Convergence with Anchored Generalized Optimistic Methodcited by 0
7 more
  1. 2026Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalitiescited by 0
  2. 2026Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Mapscited by 0
  3. 2026Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalitiescited by 0
  4. 2026Optimal High-Order Methods for Solving Monotone Variational Inequalitiescited by 0
  5. 2026Polyak-Type Extragradient Methods for Monotone Root-Finding Problemscited by 0
  6. 2026Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexitycited by 0
  7. 2026Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Findingcited by 0