Distributed Randomized Algorithms for Convex and Non-Convex Optimization

Speaker: Mert Pilanci
Affiliation: University of Michigan, Ann Arbor

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 phaseless imaging problems, 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.

Biography:  Mert Pilanci is an Assistant Professor in the Department of Electrical Engineering and Computer Science at the University of Michigan, Ann Arbor. Prior to joining University of Michigan, he was a Math+X postdoctoral fellow working with Emmanuel Candes at Stanford University.  He received his Ph.D. degree in Electrical Engineering and Computer Science from UC Berkeley in 2016 under the joint supervision of Prof. Martin Wainwright and Prof. Laurent El Ghaoui.  He received the B.Sc. and M.S. degrees both in electrical and electronics engineering from Bilkent University, Ankara, Turkey, in 2008 and 2010. He is a recipient of the Microsoft Research PhD Fellowship.  His research interests are machine learning, optimization, statistics, information theory and signal processing.

For more information, contact Profs. Lieven Vandenberghe () or Christina Fragouli ()

Date(s) - Feb 22, 2018
11:00 am - 12:30 pm

EE-IV Shannon Room #54-134
420 Westwood Plaza - 5th Flr., Los Angeles CA 90095