Generalization Bounds for Stochastic Saddle Point Problems

MaRDI QIDQ6341979zbMATH OpenFDO

Authors Junyu Zhang, Mingyi Hong, Mengdi Wang, Shuzhong Zhang

Publication date 3 June 2020

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 $mathcalO(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.

This page was built for publication: Generalization Bounds for Stochastic Saddle Point Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6341979)