A scalable Frank-Wolfe-based algorithm for the Max-Cut SDP

Chi Bach Pham; Wynita Griggs; James Saunderson

A scalable Frank-Wolfe-based algorithm for the Max-Cut SDP

Chi Bach Pham, Wynita Griggs, James Saunderson

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

Abstract

We consider the problem of solving large-scale instances of the Max-Cut semidefinite program (SDP), i.e., optimizing a linear function over n×n positive semidefinite (PSD) matrices with unit diagonal. When the cost matrix is PSD, we show how to exactly reformulate the problem as maximizing a smooth concave function over PSD matrices with unit trace. By applying the Frank-Wolfe method, we obtain a simple algorithm that is compatible with recent sampling-based techniques to solve SDPs using low memory. We demonstrate the practical performance of our method on 10⁶ ×10⁶ instances of the max-cut SDP with costs having up to 5 × 10⁶ non-zero entries. Theoretically, we show that our method solves problems with diagonally dominant costs to relative error ϵ in O(nϵ⁻¹) calls to a randomized approximate largest eigenvalue subroutine, each of which succeeds with high probability after O(log(n)ϵ⁻¹/²) matrix-vector multiplications with the cost matrix.

Original language	English
Title of host publication	International Conference on Machine Learning, 23-29 July 2023
Editors	Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, Jonathan Scarlett
Place of Publication	London UK
Publisher	Proceedings of Machine Learning Research (PMLR)
Pages	27822-27839
Number of pages	18
Volume	202
Publication status	Published - 2023
Event	International Conference on Machine Learning 2023 - Honolulu, United States of America Duration: 23 Jul 2023 → 29 Jul 2023 Conference number: 40th https://proceedings.mlr.press/v202/ (Proceedings) https://icml.cc/Conferences/2023/Dates (Website)

Conference

Conference	International Conference on Machine Learning 2023
Abbreviated title	ICML 2023
Country/Territory	United States of America
City	Honolulu
Period	23/07/23 → 29/07/23
Internet address	https://proceedings.mlr.press/v202/ (Proceedings) https://icml.cc/Conferences/2023/Dates (Website)

Access to Document

523531408-oaFinal published version, 563 KB

https://proceedings.mlr.press/v202/pham23a

Cite this

Pham, C. B., Griggs, W., & Saunderson, J. (2023). A scalable Frank-Wolfe-based algorithm for the Max-Cut SDP. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, & J. Scarlett (Eds.), International Conference on Machine Learning, 23-29 July 2023 (Vol. 202, pp. 27822-27839). Proceedings of Machine Learning Research (PMLR). https://proceedings.mlr.press/v202/pham23a

Pham, Chi Bach ; Griggs, Wynita ; Saunderson, James. / A scalable Frank-Wolfe-based algorithm for the Max-Cut SDP. International Conference on Machine Learning, 23-29 July 2023. editor / Andreas Krause ; Emma Brunskill ; Kyunghyun Cho ; Barbara Engelhardt ; Sivan Sabato ; Jonathan Scarlett. Vol. 202 London UK : Proceedings of Machine Learning Research (PMLR), 2023. pp. 27822-27839

@inproceedings{4a8613ba4210421cba0056dc328335a4,

title = "A scalable Frank-Wolfe-based algorithm for the Max-Cut SDP",

abstract = "We consider the problem of solving large-scale instances of the Max-Cut semidefinite program (SDP), i.e., optimizing a linear function over n×n positive semidefinite (PSD) matrices with unit diagonal. When the cost matrix is PSD, we show how to exactly reformulate the problem as maximizing a smooth concave function over PSD matrices with unit trace. By applying the Frank-Wolfe method, we obtain a simple algorithm that is compatible with recent sampling-based techniques to solve SDPs using low memory. We demonstrate the practical performance of our method on 106 ×106 instances of the max-cut SDP with costs having up to 5 × 106 non-zero entries. Theoretically, we show that our method solves problems with diagonally dominant costs to relative error ϵ in O(nϵ−1) calls to a randomized approximate largest eigenvalue subroutine, each of which succeeds with high probability after O(log(n)ϵ−1/2) matrix-vector multiplications with the cost matrix.",

author = "Pham, {Chi Bach} and Wynita Griggs and James Saunderson",

note = "Funding Information: The authors would like to thank Pablo Parrilo for helpful discussions at the early stages of this work. JS is the recipient of an Australian Research Council Discovery Early Career Researcher Award (project number DE210101056) funded by the Australian Government. Publisher Copyright: {\textcopyright} 2023 Proceedings of Machine Learning Research. All rights reserved.; International Conference on Machine Learning 2023, ICML 2023 ; Conference date: 23-07-2023 Through 29-07-2023",

year = "2023",

language = "English",

volume = "202",

pages = "27822--27839",

editor = "Andreas Krause and Emma Brunskill and Cho, {Kyunghyun } and Barbara Engelhardt and Sivan Sabato and Jonathan Scarlett",

booktitle = "International Conference on Machine Learning, 23-29 July 2023",

publisher = "Proceedings of Machine Learning Research (PMLR)",

address = "United States of America",

url = "https://proceedings.mlr.press/v202/, https://icml.cc/Conferences/2023/Dates",

}

Pham, CB, Griggs, W & Saunderson, J 2023, A scalable Frank-Wolfe-based algorithm for the Max-Cut SDP. in A Krause, E Brunskill, K Cho, B Engelhardt, S Sabato & J Scarlett (eds), International Conference on Machine Learning, 23-29 July 2023. vol. 202, Proceedings of Machine Learning Research (PMLR), London UK, pp. 27822-27839, International Conference on Machine Learning 2023, Honolulu, Hawaii, United States of America, 23/07/23. <https://proceedings.mlr.press/v202/pham23a>

A scalable Frank-Wolfe-based algorithm for the Max-Cut SDP. / Pham, Chi Bach; Griggs, Wynita ; Saunderson, James.
International Conference on Machine Learning, 23-29 July 2023. ed. / Andreas Krause; Emma Brunskill; Kyunghyun Cho; Barbara Engelhardt; Sivan Sabato; Jonathan Scarlett. Vol. 202 London UK: Proceedings of Machine Learning Research (PMLR), 2023. p. 27822-27839.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - A scalable Frank-Wolfe-based algorithm for the Max-Cut SDP

AU - Pham, Chi Bach

AU - Griggs, Wynita

AU - Saunderson, James

N1 - Conference code: 40th

PY - 2023

Y1 - 2023

N2 - We consider the problem of solving large-scale instances of the Max-Cut semidefinite program (SDP), i.e., optimizing a linear function over n×n positive semidefinite (PSD) matrices with unit diagonal. When the cost matrix is PSD, we show how to exactly reformulate the problem as maximizing a smooth concave function over PSD matrices with unit trace. By applying the Frank-Wolfe method, we obtain a simple algorithm that is compatible with recent sampling-based techniques to solve SDPs using low memory. We demonstrate the practical performance of our method on 106 ×106 instances of the max-cut SDP with costs having up to 5 × 106 non-zero entries. Theoretically, we show that our method solves problems with diagonally dominant costs to relative error ϵ in O(nϵ−1) calls to a randomized approximate largest eigenvalue subroutine, each of which succeeds with high probability after O(log(n)ϵ−1/2) matrix-vector multiplications with the cost matrix.

AB - We consider the problem of solving large-scale instances of the Max-Cut semidefinite program (SDP), i.e., optimizing a linear function over n×n positive semidefinite (PSD) matrices with unit diagonal. When the cost matrix is PSD, we show how to exactly reformulate the problem as maximizing a smooth concave function over PSD matrices with unit trace. By applying the Frank-Wolfe method, we obtain a simple algorithm that is compatible with recent sampling-based techniques to solve SDPs using low memory. We demonstrate the practical performance of our method on 106 ×106 instances of the max-cut SDP with costs having up to 5 × 106 non-zero entries. Theoretically, we show that our method solves problems with diagonally dominant costs to relative error ϵ in O(nϵ−1) calls to a randomized approximate largest eigenvalue subroutine, each of which succeeds with high probability after O(log(n)ϵ−1/2) matrix-vector multiplications with the cost matrix.

UR - http://www.scopus.com/inward/record.url?scp=85174402877&partnerID=8YFLogxK

M3 - Conference Paper

AN - SCOPUS:85174402877

VL - 202

SP - 27822

EP - 27839

BT - International Conference on Machine Learning, 23-29 July 2023

A2 - Krause, Andreas

A2 - Brunskill, Emma

A2 - Cho, Kyunghyun

A2 - Engelhardt, Barbara

A2 - Sabato, Sivan

A2 - Scarlett, Jonathan

PB - Proceedings of Machine Learning Research (PMLR)

CY - London UK

T2 - International Conference on Machine Learning 2023

Y2 - 23 July 2023 through 29 July 2023

ER -

A scalable Frank-Wolfe-based algorithm for the Max-Cut SDP

Abstract

Conference

Access to Document

Other files and links

Realising the potential of hyperbolic programming

Cite this

A scalable Frank-Wolfe-based algorithm for the Max-Cut SDP

Abstract

Conference

Access to Document

Other files and links

Projects

Realising the potential of hyperbolic programming

Cite this