Skip navigation

2017-11-15 14:00:00 2017-11-15 15:00:00 America/New_York Research Seminar Series - Ruoyo Sun Assistant Professor, Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana-Champaign WALC 2087

November 15, 2017

Research Seminar Series - Ruoyo Sun

Event Date: November 15, 2017
Hosted By: School of Industrial Engineering
Time: 2:00 - 3:00 PM
Location: WALC 2087
Contact Name: Leza Dellinger
Contact Phone: 765-494-5444
Contact Email: lrdellin@purdue.edu
Open To: All
Priority: No
School or Program: Industrial Engineering
College Calendar: Show
Assistant Professor, Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana-Champaign

"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. 

Second, in an effort to extend the idea of decomposition to constrained problems, there has been much interest 
in analyzing multi-block ADMM. However, cyclic multi-block ADMM was recently found to be possibly divergent. 
We prove that RP-ADMM (randomly permuted ADMM) converges in expectation for solving linear systems. As 
some byproducts, we prove that RP-CD is at least n times faster than cyclic CD, and propose a new Bernoulli randomization scheme. 

 

Photo of Ruoyu SunBIO

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.