mlsanityData to 7 Oct 2026

On Optimal Probabilities in Stochastic Coordinate Descent Methods

arXiv 1310.3438 ↗First posted 13 Oct 2013stat.ML cs.DC math.OCcited by 14

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 3; 2023: 3; 2024: 1; 2025: 1; 2026: 1.

14 papers.

Sort:

  1. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  2. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  3. 2021Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimizationcited by 21
  4. 2022GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexitycited by 17
  5. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  6. 2021Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniquescited by 9
  7. 2024FRUGAL: Memory-Efficient Optimization by Reducing State Overhead for Scalable Trainingcited by 7
  8. 2021SGD with Coordinate Sampling: Theory and Practicecited by 4
  9. 2022L-SVRG and L-Katyusha with Adaptive Samplingcited by 1
  10. 2023Importance Sampling for Stochastic Gradient Descent in Deep Neural Networkscited by 1
  11. 2023Enhanced Federated Optimization: Adaptive Unbiased Client Sampling with Reduced Variancecited by 1
  12. 2022Variance Reduction is an Antidote to Byzantines: Better Rates, Weaker Assumptions and Communication Compression as a Cherry on the Topcited by 0
2 more
  1. 2025A stochastic gradient descent algorithm with random search directionscited by 0
  2. 2026Exploring New Frontiers in Vertical Federated Learning: the Role of Saddle Point Reformulationcited by 0