Breaking Locality Accelerates Block Gauss-Seidel
For researchers in optimization and large-scale machine learning, this work provides a practical acceleration method for Gauss-Seidel that outperforms existing approaches in certain regimes.
The paper shows that breaking locality by using random coordinate sampling in non-accelerated Gauss-Seidel can outperform accelerated Gauss-Seidel with fixed partitioning. It then analyzes accelerated block Gauss-Seidel with random sampling, demonstrating speedups over non-accelerated Gauss-Seidel and conjugate gradient in large-scale ML tasks.
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.