Generalization Bounds for Stochastic Saddle Point Problems

2020/06/03 by Junyu Zhang, Zhang, Junyu, Mingyi Hong +5
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Reinforcement Learning in Robotics #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2006.02067

openalex publication_date 2020/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Train faster, generalize better: Stability of stochastic gradient descent
• Fast rates with high probability in exp-concave statistical learning
• Lower Bound On the Computational Complexity of Discounted Markov Decision Problems
• Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems
• Stability and Convergence Trade-off of Iterative Optimization Algorithms
• Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Łojasiewicz Condition
• A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise
• A Stochastic Composite Gradient Method with Incremental Variance Reduction
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization

Related

• Fast convergence of sample-average approximation for saddle-point problems
• A Central Limit Theorem for Algorithmic Estimator of Saddle Point
• Stochastic Saddle Point Problems with Decision-Dependent Distributions
• Dealing with unbounded gradients in stochastic saddle-point optimization
• Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap