# An optimal scheduled learning rate for a randomized Kaczmarz algorithm

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 45 references that are in the map.
- First posted on arXiv 24 Feb 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Phase Retrieval via Randomized Kaczmarz: Theoretical Guarantees](https://mlsanity.com/paper/1706.09993/) (2017)
- [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)
- [Faster randomized block Kaczmarz algorithms](https://mlsanity.com/paper/1902.09946/) (2019)
- [An Asynchronous Parallel Randomized Kaczmarz Algorithm](https://mlsanity.com/paper/1401.4780/) (2014)
- [Single Projection Kaczmarz Extended Algorithms](https://mlsanity.com/paper/1504.00231/) (2015)

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

- [Randomized Kaczmarz with geometrically smoothed momentum](https://mlsanity.com/paper/2401.09415/) (2024)

## Abstract (arXiv)

We study how the learning rate affects the performance of a relaxed randomized Kaczmarz algorithm for solving A x ≈ b + varepsilon, where A x =b is a consistent linear system and varepsilon has independent mean zero random entries. We derive a learning rate schedule which optimizes a bound on the expected error that is sharp in certain cases; in contrast to the exponential convergence of the standard randomized Kaczmarz algorithm, our optimized bound involves the reciprocal of the Lambert-W function of an exponential.