Generalization Bounds for Stochastic Saddle Point Problems
arXiv:2006.02067
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 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.
References in corpus (11)
- Train faster, generalize better: Stability of stochastic gradient descent
- Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning
- Stability and Convergence Trade-off of Iterative Optimization Algorithms
- Primal-Dual Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems
- A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise
- Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
- Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity
- Average Stability is Invariant to Data Preconditioning. Implications to Exp-concave Empirical Risk Minimization
- Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Łojasiewicz Condition
- Lower Bound On the Computational Complexity of Discounted Markov Decision Problems
- Fast rates with high probability in exp-concave statistical learning