# Generalization Bounds for Stochastic Saddle Point Problems

arXiv: https://arxiv.org/abs/2006.02067 · HTML: https://mlsanity.com/paper/2006.02067/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2020.

## Built on by (most cited first, 28 of 28)

- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Certified Minimax Unlearning with Generalization Rates and Deletion Capacity](https://mlsanity.com/paper/2312.10336/) (2023)
- [Differentially Private SGDA for Minimax Problems](https://mlsanity.com/paper/2201.09046/) (2022)
- [Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimization](https://mlsanity.com/paper/2206.00363/) (2022)
- [Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks](https://mlsanity.com/paper/2209.09298/) (2022)
- [Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problems](https://mlsanity.com/paper/2104.02988/) (2021)
- [What is a Good Metric to Study Generalization of Minimax Learners?](https://mlsanity.com/paper/2206.04502/) (2022)
- [Stability and Generalization for Markov Chain Stochastic Gradient Methods](https://mlsanity.com/paper/2209.08005/) (2022)
- [Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap](https://mlsanity.com/paper/2302.12909/) (2023)
- [A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learning](https://mlsanity.com/paper/2206.01132/) (2022)
- [Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm](https://mlsanity.com/paper/2310.20369/) (2023)
- [Differentially Private Worst-group Risk Minimization](https://mlsanity.com/paper/2402.19437/) (2024)
- [Beyond the Return: Off-policy Function Estimation under User-specified Error-measuring Distributions](https://mlsanity.com/paper/2210.15543/) (2022)
- [Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimization](https://mlsanity.com/paper/2205.14278/) (2022)
- [Stochastic Saddle Point Problems with Decision-Dependent Distributions](https://mlsanity.com/paper/2201.02313/) (2022)
- [Continuous Invariance Learning](https://mlsanity.com/paper/2310.05348/) (2023)
- [OLLIE: Imitation Learning from Offline Pretraining to Online Finetuning](https://mlsanity.com/paper/2405.17477/) (2024)
- [Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms](https://mlsanity.com/paper/2307.03357/) (2023)
- [Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization](https://mlsanity.com/paper/2310.17759/) (2023)
- [Stability and Generalization of Differentially Private Minimax Problems](https://mlsanity.com/paper/2204.04858/) (2022)
- [Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to K-Level Stochastic Optimizations](https://mlsanity.com/paper/2407.05286/) (2024)
- [Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry](https://mlsanity.com/paper/2411.05198/) (2024)
- [Towards Sharper Risk Bounds for Minimax Problems](https://mlsanity.com/paper/2410.08497/) (2024)
- [Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicity](https://mlsanity.com/paper/2410.20649/) (2024)
- [Randomized Pairwise Learning with Adaptive Sampling: A PAC-Bayes Analysis](https://mlsanity.com/paper/2504.02957/) (2025)
- [Everywhere Learning: Artificial Intelligence with Pointwise Constraints](https://mlsanity.com/paper/2606.01557/) (2026)
- [Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization](https://mlsanity.com/paper/2609.20327/) (2026)
- [Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2610.19322/) (2026)

## Abstract (arXiv)

This paper studies the generalization bounds for the empirical saddle point (ESP) solution to stochastic saddle point (SSP) problems. For SSP with Lipschitz continuous and strongly convex-strongly concave objective functions, we establish an O(1/n) generalization bound by using a uniform stability argument. We also provide generalization bounds under a variety of assumptions, including the cases without strong convexity and without bounded domains. We illustrate our results in two examples: batch policy learning in Markov decision process, and mixed strategy Nash equilibrium estimation for stochastic games. In each of these examples, we show that a regularized ESP solution enjoys a near-optimal sample complexity. To the best of our knowledge, this is the first set of results on the generalization theory of ESP.