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

Yin Tat Lee, Swati Padmanabhan
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3069-3119, 2020.

Abstract

We provide a first-order 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 non-zero 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 Max-Cut 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 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-lee20c, title = {An $\widetilde{\mathcal{O}}(m/\varepsilon^{3.5})$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints}, author = {Lee, Yin Tat and Padmanabhan, Swati}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {3069--3119}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/lee20c/lee20c.pdf}, url = {https://proceedings.mlr.press/v125/lee20c.html}, abstract = {We provide a first-order 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 non-zero 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 Max-Cut 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 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. } }
Endnote
%0 Conference Paper %T An $\widetilde\mathcal{O}(m/\varepsilon^3.5)$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints %A Yin Tat Lee %A Swati Padmanabhan %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-lee20c %I PMLR %P 3069--3119 %U https://proceedings.mlr.press/v125/lee20c.html %V 125 %X We provide a first-order 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 non-zero 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 Max-Cut 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 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.
APA
Lee, Y.T. & Padmanabhan, S.. (2020). An $\widetilde\mathcal{O}(m/\varepsilon^3.5)$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:3069-3119 Available from https://proceedings.mlr.press/v125/lee20c.html.

Related Material