Timezone: »

Poster
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.