General Procedure to Provide High-Probability Guarantees for Stochastic Saddle Point Problems

This paper considers smooth strongly convex and strongly concave stochastic saddle point (SSP) problems. Suppose there is an arbitrary oracle that in expectation returns an \(\epsilon \) $ϵ$ -solution in the sense of certain gaps, which can be the duality gap or its weaker variants. We propose a general PB-SSP framework to guarantee an \(\epsilon \) $ϵ$ small duality gap solution with high probability via only \(\mathcal {O}\big (\log \frac{1}{p}\cdot \text {poly}(\log \kappa )\big )\) $\mathcal{O}(log\frac{1}{p}·\text{poly}(log\kappa ))$ calls of this oracle, where \(p\in (0,1)\) $p\in (0,1)$ is the confidence level and \(\kappa \) $\kappa$ is the condition number. When applied to the sample average approximation (SAA) oracle, in addition to equipping the solution with high probability, our approach even improves the sample complexity by a factor of \(\text {poly}(\kappa )\) $\text{poly}(\kappa )$ , since the high-probability argument enables us to circumvent some key difficulties of the uniform stability analysis of SAA.