# Faster Coordinate Descent via Adaptive Importance Sampling

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Mar 2017.

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

- [Adaptive Client Sampling in Federated Learning via Online Learning with Bandit Feedback](https://mlsanity.com/paper/2112.14332/) (2021)
- [SGD with Coordinate Sampling: Theory and Practice](https://mlsanity.com/paper/2105.11818/) (2021)
- [Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport](https://mlsanity.com/paper/2103.05857/) (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)
- [Accelerated Markov Chain Monte Carlo Using Adaptive Weighting Scheme](https://mlsanity.com/paper/2408.12888/) (2024)

## Abstract (arXiv)

Coordinate descent methods employ random partial updates of decision variables in order to solve huge-scale convex optimization problems. In this work, we introduce new adaptive rules for the random selection of their updates. By adaptive, we mean that our selection rules are based on the dual residual or the primal-dual gap estimates and can change at each iteration. We theoretically characterize the performance of our selection rules and demonstrate improvements over the state-of-the-art, and extend our theory and algorithms to general convex objectives. Numerical evidence with hinge-loss support vector machines and Lasso confirm that the practice follows the theory.