# Stochastic Dual Coordinate Ascent with Adaptive Probabilities

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2015.

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

- [Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/2206.07082/) (2022)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [SGD with Coordinate Sampling: Theory and Practice](https://mlsanity.com/paper/2105.11818/) (2021)
- [Information FOMO: The unhealthy fear of missing out on information. A method for removing misleading data for healthier models](https://mlsanity.com/paper/2208.13080/) (2022)
- [Learning Theory of the SVRG: Generalization and Convergence Analysis](https://mlsanity.com/paper/2605.28513/) (2026)

## Abstract (arXiv)

This paper introduces AdaSDCA: an adaptive variant of stochastic dual coordinate ascent (SDCA) for solving the regularized empirical risk minimization problems. Our modification consists in allowing the method adaptively change the probability distribution over the dual variables throughout the iterative process. AdaSDCA achieves provably better complexity bound than SDCA with the best fixed probability distribution, known as importance sampling. However, it is of a theoretical character as it is expensive to implement. We also propose AdaSDCA+: a practical variant which in our experiments outperforms existing non-adaptive methods.