THE CONFERENCE
FOR AUTHORS
FOR PARTICIPANTS

Timezone: »

 
Talk
Breaking Locality Accelerates Block Gauss-Seidel
Stephen Tu · Shivaram Venkataraman · Ashia Wilson · Alex Gittens · Michael Jordan · Benjamin Recht

Sun Aug 06 08:48 PM -- 09:06 PM (PDT) @ Parkside 2
in Continuous optimization 2 »

Recent work by Nesterov and Stich (2016) 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.

[ PDF]  [ ss Summary/Notes]  [ Video] 

Author Information

Stephen Tu (UC Berkeley)
Shivaram Venkataraman (UC Berkeley)
Ashia Wilson (UC Berkeley)
Alex Gittens (UC Berkeley)
Michael Jordan (UC Berkeley)
Benjamin Recht (Berkeley)

Benjamin Recht is an Associate Professor in the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley. Ben's research group studies the theory and practice of optimization algorithms with a focus on applications in machine learning, data analysis, and controls. Ben is the recipient of a Presidential Early Career Awards for Scientists and Engineers, an Alfred P. Sloan Research Fellowship, the 2012 SIAM/MOS Lagrange Prize in Continuous Optimization, the 2014 Jamon Prize, the 2015 William O. Baker Award for Initiatives in Research, and the 2017 NIPS Test of Time Award.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors