mlsanityData to 7 Oct 2026

On the Complexity of a Practical Primal-Dual Coordinate Method

arXiv 2201.07684 ↗First posted 19 Jan 2022math.OC cs.LG stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

We prove complexity bounds for the primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD), which has been shown to obtain good practical performance for solving convex-concave min-max problems with bilinear coupling. Our complexity bounds either match or improve the best-known results in the literature for both dense and sparse (strongly)-convex-(strongly)-concave problems.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 16 of its 25 references that are in the map. First posted on arXiv 19 Jan 2022.

Builds on

16 of 25 references.

References · 16

  1. 2015Coordinate Descent Algorithmscited by 218
  2. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  3. 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
  4. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 46
  5. 2019Variance Reduction for Matrix Gamescited by 37
  6. 2014Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimizationcited by 30
  7. 2017Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applicationscited by 29
  8. 2013Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimizationcited by 19
  9. 2020Coordinate Methods for Matrix Gamescited by 15
  10. 2015A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functionscited by 11
  11. 2020Random extrapolation for primal-dual coordinate descentcited by 10
  12. 2021Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sumscited by 10
4 more
  1. 2021Coordinate Linear Variance Reduction for Generalized Linear Programmingcited by 10
  2. 2015A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimizationcited by 8
  3. 2019On the convergence of stochastic primal-dual hybrid gradientcited by 8
  4. 2020Accelerated Dual-Averaging Primal-Dual Method for Composite Convex Minimizationcited by 2

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 2; 2024: 1; 2025: 1.

6 papers.

  1. 2022Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applicationscited by 27
  2. 2022Stochastic Constrained DRO with a Complexity Independent of Sample Sizecited by 16
  3. 2023A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimizationcited by 3
  4. 2024Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noisecited by 2
  5. 2023FedDRO: Federated Compositional Optimization for Distributionally Robust Learningcited by 1
  6. 2025Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximizationcited by 1