# A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm

arXiv: https://arxiv.org/abs/2202.09688 · HTML: https://mlsanity.com/paper/2202.09688/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 31 references that are in the map.
- First posted on arXiv 19 Feb 2022.

## Builds on (most cited first, 14 of 14)

- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Reducing Noise in GAN Training with Variance Reduced Extragradient](https://mlsanity.com/paper/1904.08598/) (2019)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021)
- [First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems](https://mlsanity.com/paper/1810.10207/) (2018)
- [Accelerated Schemes For A Class of Variational Inequalities](https://mlsanity.com/paper/1403.4164/) (2014)
- [An Optimal Multistage Stochastic Gradient Method for Minimax Problems](https://mlsanity.com/paper/2002.05683/) (2020)
- [Robust Accelerated Primal-Dual Methods for Computing Saddle Points](https://mlsanity.com/paper/2111.12743/) (2021)
- [A Stochastic Subgradient Method for Distributionally Robust Non-Convex Learning](https://mlsanity.com/paper/2006.04873/) (2020)
- [Convergence and Sample Complexity of SGD in GANs](https://mlsanity.com/paper/2012.00732/) (2020)

## Built on by (most cited first, 1 of 1)

- [Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements](https://mlsanity.com/paper/2306.16502/) (2023)

## Abstract (arXiv)

In this work, we consider strongly convex strongly concave (SCSC) saddle point (SP) problems min_x∈ℝdxmax_y∈ℝdyf(x,y) where f is L-smooth, f(.,y) is μ-strongly convex for every y, and f(x,.) is μ-strongly concave for every x. Such problems arise frequently in machine learning in the context of robust empirical risk minimization (ERM), e.g. textitdistributionally robust ERM, where partial gradients are estimated using mini-batches of data points. Assuming we have access to an unbiased stochastic first-order oracle we consider the stochastic accelerated primal dual (SAPD) algorithm recently introduced in Zhang et al. [2021] for SCSC SP problems as a robust method against gradient noise. In particular, SAPD recovers the well-known stochastic gradient descent ascent (SGDA) as a special case when the momentum parameter is set to zero and can achieve an accelerated rate when the momentum parameter is properly tuned, i.e., improving the kappa triangleq L/μ dependence from kappa2 for SGDA to kappa. We propose efficient variance-reduction strategies for SAPD based on Richardson-Romberg extrapolation and show that our method improves upon SAPD both in practice and in theory.