Mar 8 (Wed) @ 10:00am: "Frameworks for High Dimensional Optimization," Palma London, PhD Computer Science, Caltech
Abstract
I present frameworks for solving extremely large, prohibitively massive optimization problems. Today, practical applications require optimization solvers to work at extreme scales, but existing solvers do not often scale as desired. I present black-box acceleration algorithms for speeding up optimization solvers, in both distributed and parallel settings. Given a huge problem, I develop dimension reduction techniques that allow the problem to be solved in a fraction of the original time, and simultaneously makes the computation amenable to distributed computation. Efficient, dependable and secure distributed computing is increasingly fundamental to a wide range of core applications including distributed data centers, decentralized power grid, coordination of autonomous devices, and scheduling and routing problems.
In particular, I consider two optimization settings of interest. First, I consider packing linear programming (LP). LP solvers are fundamental to many problems in supply chain management, routing, learning and inference problems. I present a framework that speeds up linear programming solvers such as Cplex and Gurobi by an order of magnitude, while maintaining provably nearly optimal solutions. Secondly, I present a distributed algorithm that achieves an exponential reduction in message complexity compared to existing distributed methods. I present both empirical demonstrations and theoretical guarantees on the quality of the solution and the speedup provided by my methods.
Bio
Palma London received the Ph.D. and M.S. degrees in Computer Science at Caltech. She received the B.S.E.E. in Electrical Engineering and B.S. in Mathematics at the University of Washington. Her work focuses on mathematical optimization and distributed algorithms. Her research has been supported by the NSF Graduate Research Fellowship, the Amazon Ph.D. Fellowship, and she was recently named a Rising Star in EECS.
Hosted by: ECE Department
Submitted by: Amy Donnelly <amymdonnelly@ucsb.edu>