Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2405.03219 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
Inhaltsangabe:
- This paper considers smooth strongly convex and strongly concave (SC-SC) stochastic saddle point (SSP) problems. Suppose there is an arbitrary oracle that in expectation returns an $ε$-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 $ε$ small duality gap solution with high probability via only $\mathcal{O}\big(\log \frac{1}{p}\cdot\text{poly}(\log κ)\big)$ calls of this oracle, where $p\in(0,1)$ is the confidence level and $κ$ 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}(κ)$, since the high-probability argument enables us to circumvent some key difficulties of the uniform stability analysis of SAA.