"Large Gaps Between Gauss-Seidel Type Methods and Randomized Counterparts"

ABSTRACT

A simple yet powerful idea for solving large-scale computational problems is to iteratively solve smaller subproblems. The applications of this idea include coordinate descent (CD), POCS (Projection onto Convex Sets) and ADMM. The most existing results are based on the sampling-with-replacement update order. We analyze the classical Gauss-Seidel order and the popular random permutation order (sampling-without-replacement).  

First, we show that the cyclic versions of G-S/CD/POCS methods can be O(n^2) times slower than their randomized counterparts in the worst case. Such a gap has been noticed in existing theoretical results but was often considered to be a theoretical artifact. We show that this gap indeed exists and establish the worst-case complexity of these methods. 

BIO

Ruoyu Sun is an assistant professor in the Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana-Champaign. Before joining UIUC, he was a visiting scientist at Facebook AI Research and was a postdoctoral researcher at Stanford University. He earned his PhD in EE from the University of Minnesota, and his BS in Math from Peking University. He has won second place in the INFORMS George Nicholson Student Paper Competition, and an Honorable Mention in the INFORMS Optimization Society Student Paper Competition. His research interests lie in large-scale optimization and non-convex optimization for machine learning.