# Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Sep 2014.

## Built on by (most cited first, 30 of 31)

- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformers](https://mlsanity.com/paper/2412.12444/) (2024)
- [Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction](https://mlsanity.com/paper/2103.08280/) (2021)
- [Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling](https://mlsanity.com/paper/2112.15199/) (2021)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap](https://mlsanity.com/paper/2302.12909/) (2023)
- [Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums](https://mlsanity.com/paper/2102.13643/) (2021)
- [Coordinate Linear Variance Reduction for Generalized Linear Programming](https://mlsanity.com/paper/2111.01842/) (2021)
- [Quasi-Newton Methods for Saddle Point Problems and Beyond](https://mlsanity.com/paper/2111.02708/) (2021)
- [Unbiased Gradient Low-Rank Projection](https://mlsanity.com/paper/2510.17802/) (2025)
- [DIPPA: An improved Method for Bilinear Saddle Point Problems](https://mlsanity.com/paper/2103.08270/) (2021)
- [On the Complexity of a Practical Primal-Dual Coordinate Method](https://mlsanity.com/paper/2201.07684/) (2022)
- [Scaff-PD: Communication Efficient Fair and Robust Federated Learning](https://mlsanity.com/paper/2307.13381/) (2023)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization](https://mlsanity.com/paper/2206.08573/) (2022)
- [A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes](https://mlsanity.com/paper/2406.00274/) (2024)
- [Efficient and Robust Regularized Federated Recommendation](https://mlsanity.com/paper/2411.01540/) (2024)
- [Cyclic Coordinate Dual Averaging with Extrapolation](https://mlsanity.com/paper/2102.13244/) (2021)
- [Decentralized Stochastic Variance Reduced Extragradient Method](https://mlsanity.com/paper/2202.00509/) (2022)
- [Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problems](https://mlsanity.com/paper/2209.04604/) (2022)
- [Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization](https://mlsanity.com/paper/2303.16279/) (2023)
- [A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization](https://mlsanity.com/paper/2312.02277/) (2023)
- [Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry](https://mlsanity.com/paper/2411.05198/) (2024)
- [Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization](https://mlsanity.com/paper/2206.14981/) (2022)
- [Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization](https://mlsanity.com/paper/2505.21944/) (2025)
- [Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity](https://mlsanity.com/paper/2208.03811/) (2022)
- [Understanding Accelerated Gradient Methods: Lyapunov Analyses and Hamiltonian Assisted Interpretations](https://mlsanity.com/paper/2304.10063/) (2023)
- [Accelerated Doubly Stochastic Gradient Algorithm for Large-scale Empirical Risk Minimization](https://mlsanity.com/paper/2304.11665/) (2023)
- [Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approach](https://mlsanity.com/paper/2410.14592/) (2024)
- [Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization](https://mlsanity.com/paper/2506.15387/) (2025)

## Abstract (arXiv)

We consider a generic convex optimization problem associated with regularized empirical risk minimization of linear predictors. The problem structure allows us to reformulate it as a convex-concave saddle point problem. We propose a stochastic primal-dual coordinate (SPDC) method, which alternates between maximizing over a randomly chosen dual variable and minimizing over the primal variable. An extrapolation step on the primal variable is performed to obtain accelerated convergence rate. We also develop a mini-batch version of the SPDC method which facilitates parallel computing, and an extension with weighted sampling probabilities on the dual variables, which has a better complexity than uniform sampling on unnormalized data. Both theoretically and empirically, we show that the SPDC method has comparable or better performance than several state-of-the-art optimization methods.