AM Seminar: Randomized Algorithms for Convex and Non-convex Optimization

Speaker Name: 
Mert Pilanci
Speaker Title: 
Assistant Professor
Speaker Organization: 
Stanford University
Start Time: 
Monday, March 18, 2019 - 4:00pm
End Time: 
Monday, March 18, 2019 - 5:00pm
Location: 
BE 372
Organizer: 
Abhishek Halder

Abstract

With the advent of massive data sets, machine learning and information processing techniques are expected to bring transformative capabilities to a variety of fields.  However, existing algorithms often prove ineffective when scaled to extremely large datasets, especially in  mathematical optimization which is one of the critical components in these methodologies. This talk introduces our recent work on random projection methods in the context of distributed
optimization of convex and non-convex objectives to address this challenge. First, we establish the theoretical relation between complexity and optimality in convex optimization. We provide a general information-theoretic lower bound on any method that is based on random projection, which demonstrates the statistical sub-optimality of traditional methods. We then present a novel method, which iteratively refines the solutions to achieve statistical optimality and generalize our method to optimizing arbitrary convex functions of a large data matrix. We also discuss distributed variants of the random projection methods which can be considered as a novel improvement of the Alternating Directions Method of Multipliers (ADMM) for distributed optimization. Moreover, due to the construction of random projections, it is possible to speed up computation even further using dedicated hardware implementations such as graphical processing units (GPUs). Secondly, we consider a general class of non-convex optimization problems that arise in neural networks and prove global optimality under mild assumptions. We demonstrate that the proposed methods enable solving large scale convex and non-convex machine learning, statistical inference and inverse problems orders of magnitude faster than existing methods.

Bio

Mert Pilanci is an assistant professor of Electrical Engineering at Stanford University. He received his Ph.D. in Electrical
Engineering and Computer Science from UC Berkeley in 2016. Prior to joining Stanford, he was an assistant professor of Electrical Engineering and Computer Science at the University of Michigan. In 2017, he was a Math+X postdoctoral fellow working with Emmanuel Candès at Stanford University. His research interests are in large scale machine learning, optimization, and information theory.