An $\tilde{\mathcal{O}}(m/{\epsilon }^{3.5})$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints

Abstract

We study semidefinite programs with diagonal constraints. This problem class appears in combinatorial optimization and has a wide range of engineering applications such as in circuit design, channel assignment in wireless networks, phase recovery, covariance matrix estimation, and low-order controller design. In this paper, we give an algorithm to solve this problem to $\epsilon$-accuracy, with a run time of $\tilde{\mathcal{O}}(m/{\epsilon }^{3.5})$, where $m$ is the number of non-zero entries in the cost matrix. We improve upon the previous best run time of $\tilde{\mathcal{O}}(m/{\epsilon }^{4.5})$ by Arora and Kale. As a corollary of our result, given an instance of the Max-Cut problem with $n$ vertices and $m\gg n$ edges, our algorithm when applied to the standard SDP relaxation of Max-Cut returns a $(1-\epsilon ){\alpha }_{GW}$ cut in time $\tilde{\mathcal{O}}(m/{\epsilon }^{3.5})$, where ${\alpha }_{GW}\approx 0.878567$ is the Goemans-Williamson approximation ratio. We obtain this run time via the stochastic variance reduction framework applied to the Arora-Kale algorithm, by constructing a constant-accuracy estimator to maintain the primal iterates.

Improved explanations (propagating changes from the conference version)

References in corpus (2)

• A direct formulation for sparse PCA using semidefinite programming
• Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU