[edit]
An $\widetilde\mathcal{O}(m/\varepsilon^3.5)$Cost Algorithm for Semidefinite Programs with Diagonal Constraints
[edit]
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:30693119, 2020.
Abstract
We provide a firstorder algorithm for semidefinite programs (SDPs) with diagonal constraints on the matrix variable. Our algorithm outputs an $\varepsilon$optimal solution with a run time of $\widetilde{\mathcal{O}}(m/\varepsilon^{3.5})$, where $m$ is the number of nonzero entries in the cost matrix. This improves upon the previous best run time of $\widetilde{\mathcal{O}}(m/\varepsilon^{4.5})$ by Arora and Kale. As a corollary of our result, given an instance of the MaxCut problem with $n$ vertices and $m \gg n$ edges, our algorithm returns a $(1  \varepsilon)\alpha_{GW}$ cut in the faster time of $\widetilde{\mathcal{O}}(m/\varepsilon^{3.5})$, where $\alpha_{GW} \approx 0.878567$ is the approximation ratio by Goemans and Williamson. Our key technical contribution is to combine an approximate variant of the AroraKale framework of mirror descent for SDPs with the idea of trading off exact computations in every iteration for variancereduced 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.
Related Material


