A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm

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.