Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: **Background for the paper** 

Semidefinite programs (SDPs) form a popular class of convex programs but suffer from large input size in most useful settings. To circumvent this issue of size, Burer and Monteiro proposed expressing the problem variable as 
$X=YY^{\top},$ for some $Y\in\mathbb{R}^{n\times p}$ and, instead of (SDP), solving the following proxy problem, which we refer to as (BM): 
\begin{align*}
\min_{Y\in\mathbb{R}^{n\times p}, YY^\top \in\mathcal{C}}C\bullet YY^{\top},
\end{align*} 
where $\mathcal{C}$ is the constraint set for the original SDP with $m$ constraints. The benefit conferred by
this reduction is that (BM) uses $O(np)$ memory, whereas (SDP) uses $O(n^2)$. 

(BM) clearly lies in a lower rank space than (SDP), and therefore it shouldn't necessarily be the case that solving (BM) solves (SDP). However, it turns out that when $p$ (in the size of $Y$ above) satisfies $p  = O(\sqrt{m})$, then the solution set of (BM) also contains that o (SDP), following the celebrated result of Barvinok and Pataki (independently obtained) that there
exists a rank-$\sqrt{m}$ solution to (SDP). 

In opposition to the memory saving, an immediate disadvantage of the formulation of BM is its non-convexity. Standard convex optimization techniques therefore fail to provide convergence guarantees. There has been a flurry of recent work (Boumal-Voroninski-Bandeira, Bhojanapalli-Boumal-Jain-Netrapalli, Cifuentes, and Cifuentes-Moitra) that provide polynomial-time guarantees for the BM formulations of various classes of SDPs, *in the smoothed analysis setting*. 

**What problem this paper studies** 

In the line of work mentioned above, ``smoothed analysis'' is central to the theorem statements. In other words, all the guarantees provided by those papers exclude a set of cost matrices. (The reason for this is that those papers prove their guarantees by applying a small perturbation to the cost matrices and showing that the probability of the algorithm ending up in a set of spurious critical points --- matrices that are (second-order) stationary points for BM but do not correspond to solutions to the original SDP --- is vanishingly small.) **The question posed by this paper is if such an exclusion is necessary**. 

The paper then provides an affirmative answer to this question by an explicit construction of such an SDP.  It uses tools from Riemannian calculus to substantiate a point being a second-order stationary point while its corresponding point being suboptimal for the original SDP.


strengths_and_weaknesses: Based on my current understanding of the paper's contribution, my preliminary review is rejection. This is because my understanding is that this problem has been solved by Bhojanapalli-Boumal-Jain-Netrapalli (http://proceedings.mlr.press/v75/bhojanapalli18a/bhojanapalli18a.pdf). See the paragraphs after Corollary 4 and also the formal statement in Theorem 5. 

Could the authors please explain to me how their result differs from this one? It's highly likely that I'm misunderstanding the contribution, in which case I want to learn what I'm missing (and I'll of course update my score accordingly!). I look forward to reading the authors' response. 

---------------------------------------------------------------------------------------------------------------------------------------------------- 

After the rebuttal: it's clear that I am missing the key contribution here. I am going to try to figure this out but, for now, will change my confidence score since I am no longer confident of my original assessment. I hope I can better understand this work's contribution, but if that doesn't happen soon enough, I'll request the AC to ignore my input. 
questions: Please see above. 
limitations: Please see above.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work studies the Burer-Monteiro method, a nonconvex method for solving semidefinite programs (SDPs) that have only equality constraints and whose solution is a $n \times n$ PSD matrix of rank $p$. The solution to the Burer-Monteiro method is known to coincide with the original SDP when the rank is above the Barvinok-Pataki bound $p \gtrsim \sqrt{2n}$. Although the Burer-Monteiro problem is noncovex, it is known to be solvable in polynomial time in a smoothed analysis setting when $p \gtrsim \sqrt{2n}$, and it is known to be solvable in polynomial time for worst-case instances when $p > n/2$. The main result of this paper constructs worst-case instances for the max-cut SDP for all ranks $\sqrt{2n} \lesssim p \leq n/2$ whose corresponding Burer-Monteiro problem has spurious local minima, and hence gradient-descent type approaches fail to solve this problem. This suggests that the use of beyond-worst case analysis frameworks is necessary for proving the efficiency of the Burer-Monteiro method.
strengths_and_weaknesses: # Strengths

- *Significance*: The Burer-Monteiro has attracted interest in recent years, and it has remained open whether or not a smoothed analysis setting was necessary for polynomial time algorithms above the Barvinok-Pataki bound.

- *Quality/originality*: The proof of existence of local minima relies on a notion of (strictly) pseudo-PSD matrices and a careful analysis of Riemannian gradient descent. In my view these ideas are interesting and the technical level is moderately high.

- *Clarity*: The paper is well-written and organized.

# Weaknesses

- I do not see any major weaknesses. I just have a quibble in the next bullet about how the contribution of this paper is phrased. 

- *Clarity*: I find the phrase "The Burer-Monteiro method fails..." to be confusing. It's not clear what it means to "fail" since solving the Burer-Monteiro optimization problem solves the original SDP in a certain regime. The real problem is that the Burer-Monteiro solution may not be efficiently computable. This paper gives evidence of computational hardness by demonstrating the presence of spurious local minima in worst-case instances, but it does not strictly rule out some other clever polynomial time algorithm from solving the max-cut Burer-Monteiro problem. 

# Minor comments

**1.** I think it would improve the clarity of this paper to first introduce the Burer-Monteiro method in general (ie for general SDPs with linear equality constraints and rank p solutions) and then specialize to the max-cut problem. 

**2.** The preliminaries are introduced abruptly, and if the paper is read linearly, it is not clear initially why some of them are needed. Either (i) a high-level sketch of the proof of Theorem 1 before the preliminary section or (ii) a short sentence for each preliminary describing why it is needed (eg: we use Riemannian gradient descent to prove existence of local minima) could help with this.

**3.** The notation $ p \gtrsim \sqrt{2n}$ might be confused with $ p = \Omega( \sqrt{2 n} )$, although the latter is not what is meant here.
questions: **1.** The method for proving existence of local minima uses Riemannian gradient descent. Are there other works that use a similar technique?
limitations: **1.** The authors do not foresee negative societal impacts, and I agree with this assessment.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the landscape of the Burer-Monteiro optimization problem corresponding to the classical Goemans-Williamson SDP relaxation of Max-Cut. It was known that for generic edge weights, the Burer-Monteiro optimization over n x p matrices has no spurious second-order critical points once the rank constraint exceeds the Barvinok-Pataki bound, p(p+1)/2 >= n. However, it was unknown whether there exist particular edge weight matrices for which spurious second-order critical points or local maximizers can exist.

This work provides an explicit construction of a class of (signed) edge weight matrices, for which the BM-optimization of size 2p x p has a spurious local maximizer. By zero-padding, this construction extends also to the BM-optimization of size n x p for any n >= 2p. The construction is to posit a specific matrix Y = [I; -I] in R^{2p x p} as the candidate for the spurious local maximizer, and to then characterize those edge weight matrices for which this Y is a first-order critical point, second-order critical point, and spurious local maximizer, respectively. The characterizations of first-order and second-order criticality are simpler and based upon explicit forms of the Riemannian gradient and Hessian. However, as the Hessian is rank-deficient for p = n/2 and there is an entire sub-manifold of local minimizers containing Y, a more involved geometric argument that explicitly shows convergence of Riemannian gradient descent to this submanifold is used to argue that Y is a local minimizer. Experiments are provided in the appendix that explore the basin of attraction of this local minimizer.
strengths_and_weaknesses: I think this is an interesting paper, and would be supportive of its publication in NeurIPS.

The result is a bit limited in scope, in that it studies only the specific Goemans-Williamson SDP, and constructs only a specific type of local optimum for BM-optimization of this SDP. However, I find the identification of this particular type of local optimizer Y (the axial position matrix) to be insightful, and it is nice that the construction works all the way to the sharp threshold p = n/2. The analysis to show that it is a local optimizer, rather than just a second-order critical point, is also non-trivial due to the rank degeneracy of the Hessian, and I think it develops an interesting proof idea. Overall, I think the paper is insightful, well-written, and resolves a question whose answer was previously unknown in this literature.
questions: (1) The author(s) describe the non-negativity of the probabilistic construction of the cost matrix as an advantage---but since the problem has been formulated with min <A,X> rather than max <A,X>, wouldn't having all negative (rather than positive) entries correspond more naturally to instances of Max-Cut on graphs? Is it known whether there exists a matrix A with all negative entries, for which BM has a spurious local minimizer?

(2) The detailed discussions of the proofs of Lemmas 4 and 5 on lines 287-308 are a bit hard to follow, and I don't know if they add much value to the paper. I do find some of the results on the basins of attraction in Appendix F to be interesting, and it might be nice to move some portion of this to the main text. One question here is---for the 75% of trials that converge to spurious minimizers, are they converging to antipodal points, or are they discovering other types of local minima?

Typos:

l173, M should be P

p19 starts mixing notation w_{ij} and M_{i,j} for the entries of M

l623, the following display is missing a factor p

l684, the following display is missing some constant factors

l906, should this be "P contained in *kernel* of Hess Obj(tilde{Y})"?

l934, rank k should be k-1

l937, U in R^{k x k} should be {k x k-1}

l942, k should be k-1, and l944, k+1 should be k

l964, sigma_k should be s_k

l1012 and the subsequent display, should > be <?
limitations: Yes
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: Large SDPs are costly to solve via interior point methods. Therefore, there is great interest in techniques that are much faster and achieve nearly optimal results. Burer-Monteiro (BM) is one such method: it seeks a SDP solution -- a $n \times  n$ matrix $X$ -- which has rank $k$, and parameterizes $X=V^TV$, where $V$ is $k \times n$. $V$ is then optimized, and the SDP constraints then become restrictions on the rows of V.

The present paper studies the BM method for the well-known SDP relaxation of MaxCut. Specifically, the main question is whether local maxima of BM correspond to global maxima of the SDP. The focus is on the regime $k(k+1)/2>n$. In this regime, there exist rank k solutions that are optimal for the (full rank) SDP. However, standard BM is only guaranteed to find local maxima. The question then becomes: is it always the case that a local maximum for BM is a global maximum also (and thus a global optimum for the SDP)? 

Quite simply, this paper shows that the answer is *no* in general, for a large range of $k$ up to $n/2$. This is shown by an explicit construction, and nicely complements a result by Boumal, Voroninski and Bandeira that showed that the answer is *yes* for "generic" instances of the MaxCut SDP. The present paper also shows that there " bad"  local maxima are stable for gradient ascent. 

strengths_and_weaknesses: The main strength of the present paper is that it in some sense finishes the "landscape analysis" of BM for the MaxCut SDP. This is an interesting result that has strong connections with important recent work. The construction in the proof is nice and original. The analysis of how the objective function behaves around the "bad local minimum" is also interesting, and uses the machinery of Riemannian optimization as well as probabilistic arguments. 

The main weakness is that in some sense we expect local optimization methods to do quite well, as second-order local minima of Burer-Monteiro are nearly optimal for the SDP. This is shown in: 

Mei et al. "Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality," COLT 2017.

Indeed, a rank-k local maximum achieves the SDP maximum up to a (1-O(1/k)) error, whenever the SDP instance comes from a weighted graph (with nonnegative weights on the edges). For $k\geq \sqrt{2n}$ (as considered here) this means that the rank-k solutions are close to the full rank ones. Since MaxCut involves a rounding with an approximation factor anyway, one could argue that the (small) extra error from Met et al is not very substantial. 

Still, to be clear, I think this is a strong paper, that in a way finishes an important line of research on how "benign" BM is as a SDP solution method. 
questions: This is an optional question, but can any of the SO(d) synchronization tasks in the paper by Mei et al be similarly analyzed (ie. there are "natural" instances where SDP and local solutions of the low-rank BM are far apart)?
limitations: See the weakness above. My only comment is that the contribution by Mei et al should be discussed.
review_title: null

Meta-review: metareview: The Burer-Monteiro method is widely used for solving large scale semidefinite programs. It works based on replacing an $n \times n$ positive semidefinite matrix $X$ with $Y Y^T$ where $Y$ is $n \times p$. This has the benefit that it is more space efficient to store $Y$ than $X$, but it transforms a convex optimization problem into a nonconvex one. Above the Barvinok-Pataki bound (an analogue of the notion of a basic feasible solution for semidefinite rather than linear programming) we are at least guaranteed that there is a low-rank optimal solution. But does the nonconvex problem have spurious critical points? Recent works have studied the critical points under a smoothed analysis model, and shown that the Burer-Monteiro method works almost down to the Barvinok-Pataki bound. The main contribution of this paper is to complete the analysis of the landscape, by showing that without smoothing, even for the MAX-CUT SDP, there are spurious critical points even for $p = n/2$. One reviewer had doubts about the relationship to the work of Bhojanapalli-Boumal-Jain-Netrapalli, but I found the author reply to be convincing that the setting and techniques are fundamentally different. The other reviewers were uniformly positive. This is a nice contribution to the literature on the Burer-Monteiro method. 

As a comment to the authors, I would suggest elaborating on the connection to the work of Mei et al. I agree that showing the global and local optima are close in objective value can be somewhat orthogonal to showing that the SDP recovers e.g. some underlying clustering in community detection. This provides a further justification why it is important to understand the loss landscape, and not just bound the suboptimality of any locally optimal solution. Indeed, from what I remember of the Mei et al. paper, the locally optimal solutions do not get non-trivial performance for the associated community detection problem, so I think investigating this further and explaining it would be helpful, since these are subtle distinctions. 
confidence: Certain
Decision: Accept