Breaking Locality Accelerates Block Gauss-Seidel

Abstract

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.

Presented at the 34th International Conference on Machine Learning (ICML 2017)

References in corpus (6)

• A Lyapunov Analysis of Momentum Methods in Optimization
• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• FALKON: An Optimal Large Scale Kernel Method
• Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation

Cited by in corpus (3)

• Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization
• A novel greedy Gauss-Seidel method for solving large linear least squares problem
• Stochastic Spectral and Conjugate Descent Methods