Large Gaps Between Gauss-Seidel Type Methods and Randomized Versions


A simple yet powerful idea for solving large-scale optimization problems is to iteratively solve smaller subproblems. The applications of this idea include Gauss-Seidel (G-S) method, Kaczmarz method, coordinate descent (CD) method and ADMM. We will prove that for all these methods, there are large gaps between the deterministic cyclic versions and the randomized versions.

In the first part of the talk, we show an O(n^2) gap in the convergence rate for CD/G-S/Kaczmarz methods. Such a gap has been noticed in the existing theoretical results, but was rarely observed in practice and thus considered to be a theoretical artifact. We show that cyclic CD, Gauss-Seidel method and Kaczmarz method can be O(n^2) times worse than their randomized versions in the worst case, thus validating the existence of this gap. As many modern algorithms are based on randomized CD, an interesting open question is whether the same complexity can be achieved by deterministic algorithms. 

In the second part of the talk, we show a gap between divergence and convergence for ADMM. It was recently discovered that ADMM with 3 blocks can be divergent. Interestingly, if we randomly permute the update order at each cycle, ADMM always converges in practice. In theory, we prove the expected convergence of RP-ADMM (randomly permuted ADMM) for solving linear systems. Our result also shows a large gap between sampling without replacement (random permutation) and sampling with replacement since the latter does not converge for ADMM. 


Aug. 01st, 2017

14:30 ~ 15:30


Ruoyu Sun, University of Illinois at Urbana-Champaign


Room 308, School of Information Management & Engineering, Shanghai University of Finance & Economics

Edit This Entry