# Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization

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

## Key facts

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

## Built on by (most cited first, 19 of 19)

- [Improving Self-Supervised Learning by Characterizing Idealized Representations](https://mlsanity.com/paper/2209.06235/) (2022)
- [Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions](https://mlsanity.com/paper/2206.07252/) (2022)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [Learning with Smooth Hinge Losses](https://mlsanity.com/paper/2103.00233/) (2021)
- [FedToken: Tokenized Incentives for Data Contribution in Federated Learning](https://mlsanity.com/paper/2209.09775/) (2022)
- [RECAPP: Crafting a More Efficient Catalyst for Convex Optimization](https://mlsanity.com/paper/2206.08627/) (2022)
- [Adaptive Client Sampling in Federated Learning via Online Learning with Bandit Feedback](https://mlsanity.com/paper/2112.14332/) (2021)
- [On the Complexity of a Practical Primal-Dual Coordinate Method](https://mlsanity.com/paper/2201.07684/) (2022)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [A Stochastic Bundle Method for Interpolating Networks](https://mlsanity.com/paper/2201.12678/) (2022)
- [Structured Convolutional Kernel Networks for Airline Crew Scheduling](https://mlsanity.com/paper/2105.11646/) (2021)
- [Variance-Reduced Conservative Policy Iteration](https://mlsanity.com/paper/2212.06283/) (2022)
- [Multiple Locally Linear Kernel Machines](https://mlsanity.com/paper/2401.09629/) (2024)
- [FedAPM: Federated Learning via ADMM with Partial Model Personalization](https://mlsanity.com/paper/2506.04672/) (2025)
- [Learning Large Scale Sparse Models](https://mlsanity.com/paper/2301.10958/) (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)
- [Accelerating Single-Pass SGD for Generalized Linear Prediction](https://mlsanity.com/paper/2603.01951/) (2026)

## Abstract (arXiv)

We introduce a proximal version of the stochastic dual coordinate ascent method and show how to accelerate the method using an inner-outer iteration procedure. We analyze the runtime of the framework and obtain rates that improve state-of-the-art results for various key machine learning optimization problems including SVM, logistic regression, ridge regression, Lasso, and multiclass SVM. Experiments validate our theoretical findings.