Breaking Locality Accelerates Block GaussSeidel
[edit]
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:34823491, 2017.
Abstract
Recent work by Nesterov and Stich (2016) showed that momentum can be used to accelerate the rate of convergence for block GaussSeidel 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 nonaccelerated GaussSeidel with randomly sampled coordinates substantially outperforms accelerated GaussSeidel with any fixed partitioning. Motivated by this finding, we analyze the accelerated block GaussSeidel algorithm in the random coordinate sampling setting. Our analysis captures the benefit of acceleration with a new datadependent parameter which is well behaved when the matrix subblocks are wellconditioned. Empirically, we show that accelerated GaussSeidel with random coordinate sampling provides speedups for large scale machine learning tasks when compared to nonaccelerated GaussSeidel and the classical conjugategradient algorithm.
Related Material


