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

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


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.

Original languageEnglish
Title of host publicationInternational Conference on Machine Learning, 23-29 July 2023
EditorsAndreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, Jonathan Scarlett
Place of PublicationLondon UK
PublisherProceedings of Machine Learning Research (PMLR)
Number of pages18
Publication statusPublished - 2023
EventInternational Conference on Machine Learning 2023 - Honolulu, United States of America
Duration: 23 Jul 202329 Jul 2023
Conference number: 40th
https://proceedings.mlr.press/v202/ (Proceedings)
https://icml.cc/Conferences/2023/Dates (Website)


ConferenceInternational Conference on Machine Learning 2023
Abbreviated titleICML 2023
Country/TerritoryUnited States of America
Internet address

Cite this