Distributed Randomized Algorithms for Convex and Non-Convex Optimization

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.
I'm 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, I was a Math+X postdoctoral fellow working with Emmanuel Candes at Stanford University. I received my Ph.D. in Electrical Engineering and Computer Science from UC Berkeley in 2016. My Ph.D. advisors were Martin Wainwright and Laurent El Ghaoui, and my studies were supported partially by a Microsoft Research PhD Fellowship.