# Breaking Locality Accelerates Block Gauss-Seidel

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jan 2017.

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

- [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025)
- [Stability properties of gradient flow dynamics for the symmetric low-rank matrix factorization problem](https://mlsanity.com/paper/2411.15972/) (2024)
- [Accelerated Evolving Set Processes for Local PageRank Computation](https://mlsanity.com/paper/2510.08010/) (2025)
- [BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning](https://mlsanity.com/paper/2610.13382/) (2026)

## Abstract (arXiv)

Recent work by Nesterov and Stich showed that momentum can be used to accelerate the rate of convergence for block Gauss-Seidel in the setting where a fixed partitioning of the coordinates is chosen ahead of time. We show that this setting is too restrictive, constructing instances where breaking locality by running non-accelerated Gauss-Seidel with randomly sampled coordinates substantially outperforms accelerated Gauss-Seidel with any fixed partitioning. Motivated by this finding, we analyze the accelerated block Gauss-Seidel algorithm in the random coordinate sampling setting. Our analysis captures the benefit of acceleration with a new data-dependent parameter which is well behaved when the matrix sub-blocks are well-conditioned. Empirically, we show that accelerated Gauss-Seidel with random coordinate sampling provides speedups for large scale machine learning tasks when compared to non-accelerated Gauss-Seidel and the classical conjugate-gradient algorithm.