A Randomized Block-Coordinate Primal-Dual Method for Large-Scale Stochastic Saddle Point Problems

We consider (stochastic) convex-concave saddle point (SP) problems with high-dimensional decision variables, arising in various applications including machine learning problems. To contend with the challenges in computing full gradients, we employ a randomized block-coordinate primal-dual scheme in which randomly selected primal and dual blocks of variables are updated. We consider both deterministic and stochastic settings, where deterministic partial gradients and their randomly sampled estimates are used, respectively, at each iteration. We investigate the convergence of the proposed method under different blocking strategies and provide the corresponding complexity results. Although the best-known computational complexity result for computing a saddle point with $\epsilon$ primal-dual gap for deterministic primal-dual methods using full gradients is $\mathcal{O}(\max {\{m,n\}}^2/\epsilon )$, where m and n denote the dimensions of primal and dual variables, respectively, we show that our proposed randomized block-coordinate method achieves an improved complexity of $\mathcal{O}(mn/\epsilon )$ assuming a coordinate-friendly structure on the problem. Moreover, for the stochastic setting where a mini-batch sample gradient is utilized, we show a computational complexity of $\tilde{\mathcal{O}}(m^2{n}^2/{\epsilon }^2)$ through acceleration. Finally, almost sure convergence of the iterate sequence to a saddle point is established.

Funding: N. Serhat Aybat was supported by the Office of Naval Research [Grant N00014-24-1-2666].

Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoo.2024.0056.