Stochastic Variance Reduced Primal–Dual Hybrid Gradient Methods for Saddle-Point Problems - Weixin An; Yuanyuan Liu; Fanhua Shang; Hongying Liu (Mathematics)
Recently, many stochastic Alternating Direction Methods of Multipliers (ADMMs) have been proposed to solve large-scale machine learning problems. However, for large-scale saddle-point problems, the state-of-the-art (SOTA) stochastic ADMMs still have high per-iteration costs. On the other hand, the stochastic primal–dual hybrid gradient (SPDHG) has a low per-iteration cost but only a suboptimal convergence rate of <semantics>𝒪(1/<msqrt>S</msqrt>)</semantics>. Thus, there still remains a gap in the convergence rates between SPDHG and SOTA ADMMs. Motivated by the two matters, we propose (accelerated) stochastic variance reduced primal–dual hybrid gradient ((A)SVR-PDHG) methods. We design a linear extrapolation step to improve the convergence rate and a new adaptive epoch length strategy to remove the extra boundedness assumption. Our algorithms have a simpler structure and lower per-iteration complexity than SOTA ADMMs. As a by-product, we present the asynchronous parallel variants of our algorithms. In theory, we rigorously prove that our methods converge linearly for strongly convex problems and improve the convergence rate to <semantics>𝒪(1/S2)</semantics> for non-strongly convex problems as opposed to the existing <semantics>𝒪(1/S)</semantics> convergence rate. Compared with SOTA algorithms, various experimental results demonstrate that ASVR-PDHG can achieve an average speedup of <semantics>2×∼5×</semantics>.