# Randomized Kaczmarz with geometrically smoothed momentum

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 35 references that are in the map.
- First posted on arXiv 17 Jan 2024.

## Builds on (most cited first, 14 of 14)

- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods](https://mlsanity.com/paper/1712.09677/) (2017)
- [On the insufficiency of existing momentum schemes for Stochastic Optimization](https://mlsanity.com/paper/1803.05591/) (2018)
- [Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition](https://mlsanity.com/paper/2208.09585/) (2022)
- [On the fast convergence of minibatch heavy ball momentum](https://mlsanity.com/paper/2206.07553/) (2022)
- [An Accelerated Randomized Kaczmarz Algorithm](https://mlsanity.com/paper/1310.2887/) (2013)
- [Randomized Kaczmarz converges along small singular vectors](https://mlsanity.com/paper/2006.16978/) (2020)
- [Sampling Kaczmarz Motzkin Method for Linear Feasibility Problems: Generalization & Acceleration](https://mlsanity.com/paper/2002.07321/) (2020)
- [Faster randomized block Kaczmarz algorithms](https://mlsanity.com/paper/1902.09946/) (2019)
- [On adaptive stochastic heavy ball momentum for solving linear systems](https://mlsanity.com/paper/2305.05482/) (2023)
- [Randomized Douglas-Rachford methods for linear systems: Improved accuracy and efficiency](https://mlsanity.com/paper/2207.04291/) (2022)
- [An optimal scheduled learning rate for a randomized Kaczmarz algorithm](https://mlsanity.com/paper/2202.12224/) (2022)
- [Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems](https://mlsanity.com/paper/2307.06627/) (2023)
- [Adaptive Bregman-Kaczmarz: An Approach to Solve Linear Inverse Problems with Independent Noise Exactly](https://mlsanity.com/paper/2309.06186/) (2023)

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

- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [Randomized Kaczmarz Methods with Beyond-Krylov Convergence](https://mlsanity.com/paper/2501.11673/) (2025)
- [Perfect Parallelization in Mini-Batch SGD with Classical Momentum Acceleration](https://mlsanity.com/paper/2605.18609/) (2026)

## Abstract (arXiv)

This paper studies the effect of adding geometrically smoothed momentum to the randomized Kaczmarz algorithm, which is an instance of stochastic gradient descent on a linear least squares loss function. We prove a result about the expected error in the direction of singular vectors of the matrix defining the least squares loss. We present several numerical examples illustrating the utility of our result and pose several questions.