Timezone: »

The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound
Liam O'Carroll · Vaidehi Srinivas · Aravindan Vijayaraghavan

Thu Dec 01 02:00 PM -- 04:00 PM (PST) @ Hall J #837
The most widely used technique for solving large-scale semidefinite programs (SDPs) in practice is the non-convex Burer-Monteiro method, which explicitly maintains a low-rank SDP solution for memory efficiency. There has been much recent interest in obtaining a better theoretical understanding of the Burer-Monteiro method. When the maximum allowed rank $p$ of the SDP solution is above the Barvinok-Pataki bound (where a globally optimal solution of rank at most \(p\) is guaranteed to exist), a recent line of work established convergence to a global optimum for generic or smoothed instances of the problem. However, it was open whether there even exists an instance in this regime where the Burer-Monteiro method fails. We prove that the Burer-Monteiro method can fail for the Max-Cut SDP on $n$ vertices when the rank is above the Barvinok-Pataki bound ($p \ge \sqrt{2n}$). We provide a family of instances that have spurious local minima even when the rank $p = n/2$. Combined with existing guarantees, this settles the question of the existence of spurious local minima for the Max-Cut formulation in all ranges of the rank and justifies the use of beyond worst-case paradigms like smoothed analysis to obtain guarantees for the Burer-Monteiro method.

Author Information

Liam O'Carroll (Northwestern University)

I'm currently a fourth-year undergraduate at Northwestern University and am planning to start a PhD in the fall of 2023. I'm broadly interested in theoretical computer science, especially areas involving applications of analysis, including the mathematical foundations of machine learning, deep learning, and optimization.

Vaidehi Srinivas (Northwestern University)
Aravindan Vijayaraghavan (Northwestern University)

More from the Same Authors