Caltech Young Investigators Lecture

Abstract

Semidefinite programs (SDPs) are a fundamental class of optimization problems with important recent applications in approximation algorithms, quantum complexity, robust learning, algorithmic rounding, and adversarial deep learning. We present a faster interior point method to solve generic SDPs with variable size n × n and m constraints in time

where ω is the exponent of matrix multiplication and δ is the relative accuracy. In the predominant case of m ≥ n, our runtime outperforms that of the previous fastest SDP solver, which is based on the cutting plane method. Our algorithm's runtime can be naturally interpreted as follows: O(√n log(1/δ)) is the number of iterations needed for our interior point method, mn² is the input size, and m^ω + n^ω is the time to invert the Hessian and slack matrix in each iteration. These constitute natural barriers to further improving the runtime of interior point methods for solving generic SDPs.

Bio

Swati is a final-year Ph.D. student at the University of Washington, Seattle, where she is advised by Prof. Yin Tat Lee. Her research focuses on developing provably efficient algorithms for structured classes of optimization problems including semidefinite programs, nonsmooth problems (convex and nonconvex), problems in applied linear algebra, and online resource-allocation. Prior to pursuing her Ph.D., she studied Electronics Engineering and worked as a signal processing engineer in the hardware electronics industry.

This lecture is part of the Young Investigators Lecture Series sponsored by the Caltech Division of Engineering & Applied Science.