# On Optimal Probabilities in Stochastic Coordinate Descent Methods

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

## Key facts

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

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

- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [Stochastic Extragradient: General Analysis and Improved Rates](https://mlsanity.com/paper/2111.08611/) (2021)
- [Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization](https://mlsanity.com/paper/2102.07245/) (2021)
- [GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity](https://mlsanity.com/paper/2210.16402/) (2022)
- [Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions](https://mlsanity.com/paper/2302.14043/) (2023)
- [FRUGAL: Memory-Efficient Optimization by Reducing State Overhead for Scalable Training](https://mlsanity.com/paper/2411.07837/) (2024)
- [Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques](https://mlsanity.com/paper/2106.03524/) (2021)
- [SGD with Coordinate Sampling: Theory and Practice](https://mlsanity.com/paper/2105.11818/) (2021)
- [Variance Reduction is an Antidote to Byzantines: Better Rates, Weaker Assumptions and Communication Compression as a Cherry on the Top](https://mlsanity.com/paper/2206.00529/) (2022)
- [Enhanced Federated Optimization: Adaptive Unbiased Client Sampling with Reduced Variance](https://mlsanity.com/paper/2310.02698/) (2023)
- [L-SVRG and L-Katyusha with Adaptive Sampling](https://mlsanity.com/paper/2201.13387/) (2022)
- [Importance Sampling for Stochastic Gradient Descent in Deep Neural Networks](https://mlsanity.com/paper/2303.16529/) (2023)
- [A stochastic gradient descent algorithm with random search directions](https://mlsanity.com/paper/2503.19942/) (2025)
- [Exploring New Frontiers in Vertical Federated Learning: the Role of Saddle Point Reformulation](https://mlsanity.com/paper/2602.15996/) (2026)

## Abstract (arXiv)

We propose and analyze a new parallel coordinate descent method---`NSync---in which at each iteration a random subset of coordinates is updated, in parallel, allowing for the subsets to be chosen non-uniformly. We derive convergence rates under a strong convexity assumption, and comment on how to assign probabilities to the sets to optimize the bound. The complexity and practical performance of the method can outperform its uniform variant by an order of magnitude. Surprisingly, the strategy of updating a single randomly selected coordinate per iteration---with optimal probabilities---may require less iterations, both in theory and practice, than the strategy of updating all coordinates at every iteration.