EE Systems Seminar
Randomized Algorithms for Convex and Non-Convex Optimization
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.
Contact: Liliana Chavarria at 626-395-4715 firstname.lastname@example.org