In this note, I give a brief overview of “The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound,” published in NeurIPS 2022.

Keywords: Non-convex optimization, rank-constrained semidefinite programming, optimization on smooth manifolds

Overview: Semidefinite programs (SDPs) are a powerful and expressive class of convex optimization problems with broad applications in combinatorial optimization, control theory, machine learning, and operations research. While classical convex optimization algorithms such as interior point methods have theoretical convergence guarantees to an approximate optimum, in practice they are only effective for moderate-size instances due to heavy memory requirements. Motivated by this bottleneck, the so-called Burer-Monteiro method is a popular heuristic for solving large-scale SDPs in practice, and there has been much recent interest in obtaining a better theoretical understanding of its empirical success.

The method, pioneered by Burer and Monteiro in the early 2000s [BM03, BM05], involves solving an SDP of the form

\[\begin{align} \label{eq:SDP} \tag{SDP} \begin{split} &\min_{X \in \mathbb{S}^{n \times n}} \langle C, X \rangle \\ \text{s.t. } &\langle B_i, X \rangle = b_i \text{ for all $1 \le i \le m$}, \\ &X \succeq 0, \end{split} \end{align}\]

by instead solving the factorized “reformulation”

\[\begin{align} \label{eq:BM} \tag{BM} \begin{split} &\min_{Y \in \mathbb{R}^{n \times p}} \langle C, YY^\top \rangle \\ \text{s.t. } &\langle B_i, YY^\top \rangle = b_i \text{ for all $1 \le i \le m$}. \\ \end{split} \end{align}\]

Here, \(C, B_i \in \mathbb{S}^{n \times n}, b_i \in \mathbb{R},\) where \(\mathbb{S}^{n \times n}\) denotes the set of \(n \times n\) symmetric matrices and \(\langle C, X \rangle := \mathrm{tr}(C^\top X)\) is the Frobenius inner product. Writing \(X = YY^\top\) automatically satisfies the positive semidefinite constraint \(X \succeq 0\) of (SDP), but restricts \(X\) to have rank at most \(p\). Here, \(p\), the number of columns of \(Y\), is a parameter we choose.

If \(\bar{Y} \in \mathbb{R}^{n \times p}\) is an optimum for (BM), the hope is that \(\bar{Y} \bar{Y}^\top \in \mathbb{S}^{n \times n}\) is an optimum for (SDP). Thus, the idea is to obtain \(\bar{Y}\) (and therefore \(\bar{Y} \bar{Y}^\top\)) by solving (BM) using nonlinear programming methods like ALM or manifold-based algorithms like Riemannian gradient descent or a Riemannian trust-region method. The advantage of solving (BM) instead of (SDP) is that when \(p \ll n\), we work with an \(n \times p\) factor rather than an \(n \times n\) matrix, which can yield significant time and memory savings, especially when the cost and constraint matrices are sparse. (As discussed above, memory is a serious bottleneck for large-scale SDPs.)

However, going from (SDP) to (BM) can be viewed as adding a rank constraint (\(\text{rank} (X) \le p\)) to (SDP), so it is not a priori clear whether

  1. the optimal value is preserved after introducing this rank constraint (in other words, whether there exists an optimal solution for (SDP) with rank at most \(p\)), and
  2. whether (BM) can be solved to global optimality, since it is a non-convex problem.

In regards to the first barrier, Barvinok and Pataki [Bar95, Pat98] showed that if the feasible region of (SDP) is compact, then there is a global optimum of rank at most \(\sqrt{2m}\). Thus, setting \(p \ge \sqrt{2m}\) is provably “safe” in regards to the first barrier (and \(\sqrt{2m} \ll n\) in the vast majority of applications). The second barrier is more serious, but it was shown in the seminal work of Boumal, Voroninski, and Bandeira [BVB16, BVB18] that when \(p \ge \sqrt{2m}\), all second-order critical points of (BM) are globally optimal for generic cost matrices \(C\). A second-order critical point is a point satisfying the first and second-order necessary conditions for a local minimum, but is not necessarily a local minimum. Here, “generic” means the guarantee holds for almost every cost matrix, with a possible exceptional set of measure zero. This kind of result (all second-order critical points are globally optimal) is often called “benign non-convexity” since several of the aforementioned nonlinear programming methods provably converge to second-order critical points.

Combining these results, for generic cost matrices and when \(p \ge \sqrt{2m}\), algorithms exist which provably converge to a global optimum \(\bar{Y}\) of (BM), for which \(\bar{Y} \bar{Y}^\top\) is a global optimum of (SDP). A line of follow-up work [BBJN18, PJB18, CM21] gives polynomial-time convergence guarantees for smoothed instances (namely, instances subjected to small random perturbations). However, it was unknown whether this “generic cost matrices” caveat was even necessary. Indeed, the authors of [BVB18] comment (p. 22) that resolving whether this restriction is necessary is key to gaining a deeper understanding of the relationship between (SDP) and (BM).

Our main result (Theorem 1) shows that this restriction is necessary by constructing instances of (BM) with spurious local minima (i.e., local minima which are not global minima) when \(p\) is as large as \(\Theta(m)\). Thus, a rank of order \(\sqrt{m}\) can be sufficient to represent a global optimum of (SDP), but (BM) can have suboptimal local minima even at ranks of order \(m\). We use a novel technique involving Riemannian gradient descent to prove local minimality, and furthermore, our construction is for one of the simplest and most canonical instances of (BM): that arising from the famed Goemans-Williamson Max-Cut SDP [GW95]. Our result also complements a nice result due to [BVB18] showing that when \(p\) is any larger than the value used in our main construction, there are provably no spurious second-order critical points for any cost matrix. That is to say, we “complete” the story of how benign the non-convexity of (BM) is for different ranges of the parameter \(p\).

At a high level, this work provides a more complete picture of the optimization landscape of (BM) (particularly the important instances arising from the Max-Cut SDP). Furthermore, it justifies the use of beyond worst-case paradigms like smoothed analysis to obtain global convergence guarantees for the Burer-Monteiro method.