Statistics Department Seminar Series: Mert Pilanci, Assistant Professor, Electrical Engineering & Computer Science, University of Michigan

With the advent of massive data sets, machine learning, artificial intelligence and information processing techniques are expected to bring unprecedented and transformative capabilities in engineering and sciences across a variety of fields. However, existing algorithms for mathematical optimization, which is one of the critical core component in these techniques, often prove ineffective for scaling to the extent of all available data. 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 surprisingly shows that the most widely used form of random projection is, in fact, statistically sub-optimal. 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 special structure of random projection, 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. We prove that the randomized second order optimization method with a suitable initialization recovers the global optimum 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.