A faster interior point method for semidefinite programming

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. This paper presents a faster interior point method to solve generic SDPs with variable size n times n and m constraints in time begin{equation-} tilde{O}(sqrt{n}(mn{2}+m{omega}+n{omega}) log(1 epsilon)), end{equation-} where omega is the exponent of matrix multiplication and epsilon is the relative accuracy. In the predominant case of m geq n, our runtime outperforms that of the previous fastest SDP solver, which is based on the cutting plane method [JLSW20]. Our algorithm's runtime can be naturally interpreted as follows: O(sqrt{n} log(1 epsilon)) is the number of iterations needed for our interior point method, mn{2} is the input size, and m{omega}+n{omega} 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.