Publications

1. The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound
Joint work with Vaidehi Srinivas and Aravindan Vijayaraghavan.
NeurIPS 2022.
[arXiv] [recorded mini talk]

Overview: The Burer-Monteiro method is a popular heuristic for solving semidefinite programs (SDPs) in practice. We study the optimization landscape of this non-convex problem and construct a family of instances with high-rank spurious local minima, thereby justifying the use of beyond worst-case paradigms like smoothed analysis to obtain global convergence guarantees. A more detailed overview is available here.