An Õ(m/ε^3.5)-Cost Algorithm for Semidefinite Programs with Diagonal Constraints

We provide a first-order algorithm for semidefinite programs (SDPs) with diagonal constraints on the matrix variable. Our algorithm outputs an ε-optimal solution with a run time of Õ(m/ε^3.5), where m is the number of non-zero entries in the cost matrix. This improves upon the previous best run time of Õ(m/ε^4.5) by Arora and Kale (2007). As a corollary of our result, given an instance of the Max-Cut problem with n vertices and m ≫ n edges, our algorithm returns a (1−ε)α_GW cut in the faster time of Õ(m/ε^3.5), where α_GW ≈ 0.878567 is the approximation ratio by Goemans and Williamson (1995). Our key technical contribution is to combine an approximate variant of the Arora-Kale framework of mirror descent for SDPs with the idea of trading off exact computations in every iteration for variance-reduced estimations in most iterations, only periodically resetting the accumulated error with exact computations. This idea, along with the constructed estimator, are of possible independent interest for other problems that use the mirror descent framework.