Generalization Bounds for Stochastic Saddle Point Problems

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 $\mathcal{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.

References in corpus (4)

• Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning
• Primal-Dual $\pi$ Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems
• A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise
• Lower Bound On the Computational Complexity of Discounted Markov Decision Problems

Cited by in corpus (1)

• Variational Policy Gradient Method for Reinforcement Learning with General Utilities