# Accelerated Mini-Batch Stochastic Dual Coordinate Ascent

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 May 2013.

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

- [Robust Training in High Dimensions via Block Coordinate Geometric Median Descent](https://mlsanity.com/paper/2106.08882/) (2021)
- [Provable Generalization of Overparameterized Meta-learning Trained with SGD](https://mlsanity.com/paper/2206.09136/) (2022)
- [Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delays](https://mlsanity.com/paper/2106.12261/) (2021)
- [Adaptive Stochastic Gradient Descent for Fast and Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2208.03134/) (2022)
- [Utilizing Redundancy in Cost Functions for Resilience in Distributed Optimization and Learning](https://mlsanity.com/paper/2110.10858/) (2021)
- [Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity](https://mlsanity.com/paper/2208.03811/) (2022)
- [Impact of Redundancy on Resilience in Distributed Optimization and Learning](https://mlsanity.com/paper/2211.08622/) (2022)
- [Efficient Continual Finite-Sum Minimization](https://mlsanity.com/paper/2406.04731/) (2024)
- [Differentially Private Random Block Coordinate Descent](https://mlsanity.com/paper/2412.17054/) (2024)
- [Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weighting](https://mlsanity.com/paper/2506.12444/) (2025)
- [Randomized batch-sampling Kaczmarz methods for solving linear systems](https://mlsanity.com/paper/2511.09872/) (2025)

## Abstract (arXiv)

Stochastic dual coordinate ascent (SDCA) is an effective technique for solving regularized loss minimization problems in machine learning. This paper considers an extension of SDCA under the mini-batch setting that is often used in practice. Our main contribution is to introduce an accelerated mini-batch version of SDCA and prove a fast convergence rate for this method. We discuss an implementation of our method over a parallel computing system, and compare the results to both the vanilla stochastic dual coordinate ascent and to the accelerated deterministic gradient descent method of citenesterov2007gradient.