# Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm

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

## Key facts

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

## Built on by (most cited first, 30 of 133)

- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [Reasonable Effectiveness of Random Weighting: A Litmus Test for Multi-Task Learning](https://mlsanity.com/paper/2111.10603/) (2021)
- [How catastrophic can catastrophic forgetting be in linear regression?](https://mlsanity.com/paper/2205.09588/) (2022)
- [High-dimensional limit theorems for SGD: Effective dynamics and critical scaling](https://mlsanity.com/paper/2206.04030/) (2022)
- [Tackling System and Statistical Heterogeneity for Federated Learning with Adaptive Client Sampling](https://mlsanity.com/paper/2112.11256/) (2021)
- [On Linear Stability of SGD and Input-Smoothness of Neural Networks](https://mlsanity.com/paper/2105.13462/) (2021)
- [Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis](https://mlsanity.com/paper/2105.01650/) (2021)
- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)
- [Provable convergence guarantees for black-box variational inference](https://mlsanity.com/paper/2306.03638/) (2023)
- [Distributed Second Order Methods with Fast Rates and Compressed Communication](https://mlsanity.com/paper/2102.07158/) (2021)
- [Swift Sampler: Efficient Learning of Sampler by 10 Parameters](https://mlsanity.com/paper/2410.05578/) (2024)
- [Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensions](https://mlsanity.com/paper/2206.07252/) (2022)
- [Reweighting Augmented Samples by Minimizing the Maximal Expected Loss](https://mlsanity.com/paper/2103.08933/) (2021)
- [GraB: Finding Provably Better Data Permutations than Random Reshuffling](https://mlsanity.com/paper/2205.10733/) (2022)
- [Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Data](https://mlsanity.com/paper/2206.00737/) (2022)
- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods](https://mlsanity.com/paper/2102.09700/) (2021)
- [Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization](https://mlsanity.com/paper/2101.02696/) (2021)
- [Large Batch Experience Replay](https://mlsanity.com/paper/2110.01528/) (2021)
- [Adaptive Importance Sampling meets Mirror Descent: a Bias-variance tradeoff](https://mlsanity.com/paper/2110.15590/) (2021)
- [On the fast convergence of minibatch heavy ball momentum](https://mlsanity.com/paper/2206.07553/) (2022)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [On Riemannian Stochastic Approximation Schemes with Fixed Step-Size](https://mlsanity.com/paper/2102.07586/) (2021)
- [DIGEST: Fast and Communication Efficient Decentralized Learning with Local Updates](https://mlsanity.com/paper/2307.07652/) (2023)
- [From Continual Learning to SGD and Back: Better Rates for Continual Linear Models](https://mlsanity.com/paper/2504.04579/) (2025)
- [Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime](https://mlsanity.com/paper/2507.11274/) (2025)
- [Convergence and concentration properties of constant step-size SGD through Markov chains](https://mlsanity.com/paper/2306.11497/) (2023)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [On the Last Iterate Convergence of Momentum Methods](https://mlsanity.com/paper/2102.07002/) (2021)

## Abstract (arXiv)

We obtain an improved finite-sample guarantee on the linear convergence of stochastic gradient descent for smooth and strongly convex objectives, improving from a quadratic dependence on the conditioning (L/μ)2 (where L is a bound on the smoothness and μ on the strong convexity) to a linear dependence on L/μ. Furthermore, we show how reweighting the sampling distribution (i.e. importance sampling) is necessary in order to further improve convergence, and obtain a linear dependence in the average smoothness, dominating previous results. We also discuss importance sampling for SGD more broadly and show how it can improve convergence also in other scenarios. Our results are based on a connection we make between SGD and the randomized Kaczmarz algorithm, which allows us to transfer ideas between the separate bodies of literature studying each of the two methods. In particular, we recast the randomized Kaczmarz algorithm as an instance of SGD, and apply our results to prove its exponential convergence, but to the solution of a weighted least squares problem rather than the original least squares problem. We then present a modified Kaczmarz algorithm with partially biased sampling which does converge to the original least squares solution with the same exponential convergence rate.