mlsanityData to 14 Oct 2026

Towards Sharper Risk Bounds for Minimax Problems

arXiv 2410.08497 ↗First posted 11 Oct 2024cs.LG stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

Minimax problems have achieved success in machine learning such as adversarial training, robust optimization, reinforcement learning. For theoretical analysis, current optimal excess risk bounds, which are composed by generalization error and optimization error, present 1/n-rates in strongly-convex-strongly-concave (SC-SC) settings. Existing studies mainly focus on minimax problems with specific algorithms for optimization error, with only a few studies on generalization performance, which limit better excess risk bounds. In this paper, we study the generalization bounds measured by the gradients of primal functions using uniform localized convergence. We obtain a sharper high probability generalization error bound for nonconvex-strongly-concave (NC-SC) stochastic minimax problems. Furthermore, we provide dimension-independent results under Polyak-Lojasiewicz condition for the outer layer. Based on our generalization error bound, we analyze some popular algorithms such as empirical saddle point (ESP), gradient descent ascent (GDA) and stochastic gradient descent ascent (SGDA). We derive better excess primal risk bounds with further reasonable assumptions, which, to the best of our knowledge, are n times faster than exist results in minimax problems.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 37 of its 65 references that are in the map. First posted on arXiv 11 Oct 2024.

Builds on

37 of 65 references.

References · 37

  1. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  2. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  3. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  4. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  5. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
  6. 2018A Convergence Analysis of Gradient Descent for Deep Linear Neural Networkscited by 184
  7. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  8. 2016Variance-based regularization with convex objectivescited by 155
  9. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  10. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
  11. 2016Identity Matters in Deep Learningcited by 109
  12. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
25 more
  1. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
  2. 2019Sharper bounds for uniformly stable algorithmscited by 93
  3. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 92
  4. 2019On the convergence of single-call stochastic extra-gradient methodscited by 89
  5. 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
  6. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 77
  7. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 76
  8. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 63
  9. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 60
  10. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 58
  11. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
  12. 2020Train simultaneously, generalize better: Stability of gradient-based minimax learnerscited by 44
  13. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  14. 2017Algorithmic stability and hypothesis complexitycited by 39
  15. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 36
  16. 2017Robust Optimization for Non-Convex Objectivescited by 35
  17. 2018First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problemscited by 34
  18. 2020Stochastic Hamiltonian Gradient Methods for Smooth Gamescited by 32
  19. 2020Generalization Bounds for Stochastic Saddle Point Problemscited by 28
  20. 2018Graphical Convergence of Subgradients in Nonconvex Optimization and Learningcited by 17
  21. 2022What is a Good Metric to Study Generalization of Minimax Learners?cited by 16
  22. 2017Empirical Risk Minimization for Stochastic Convex Optimization: O(1/n)- and O(1/n2)-type of Risk Boundscited by 15
  23. 2019Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Ratecited by 14
  24. 2020Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theorycited by 13
  25. 2018Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditionscited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problemscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Dealing with unbounded gradients in stochastic saddle-point optimization
  2. 2025Can SGD Handle Heavy-Tailed Noise?
  3. 2026On the Stability and Generalization of First-order Bilevel Minimax Optimization
  4. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning
  5. 2021Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems
  6. 2024Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetry
  7. 2026Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization
  8. 2021Machine Unlearning via Algorithmic Stability