The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound
Authors: Liam O'Carroll
Vaidehi Srinivas
Aravindan Vijayaraghavan
Venue: NeurIPS 2022 Accept (2022)
Keywords: non-convex optimization
semidefinite programming
Burer-Monteiro
manifold optimization
low-rank SDP

Abstract: 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.

The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound
Liam O'Carroll
Vaidehi Srinivas
Department of Computer Science
Department of Computer Science
Northwestern University Evanston, II. 60208
Northwestern University Evanston, II. 60208 haidehi@u.northweessee edu
Aravindan Vijayaraghavan Department of Computer Science
Northwestern University Evanston, IL 60208
aravindv@hootthwwstem.c edu
Abstract
The most widely used technique for solving large-scale semidefinite programs (SDPs) in practice is the non-con non-convex Burer-Monteire method, which explicitly maintains 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 of the SDP solution is above the Barvinok-Pataki bound (where globally optimal solution of rank at most is guaranteed to exist), a recent line of work established convergence to a global optimum for generic smoothed instances of the problem. However, it open whether there even exists an instance in this regime where the Burer-Monteiro method fails. We prove that the
method can fail for the Max-Cut SDP vertices when the rank is above the Barvinok-Patale bound (p 2 /2n). We provide family of instances that have spurious local minima even when the rank n//2. Combined with existing guarantees, this settles the question of the existence of spurious local minima for the Max-Ctt formulation all ranges of the rank and justifies the of beyond worst-case paradigms like smoothed analysis to obtain guarantees for the Montr-oonteiro method.
Introduction
Semidefinite programs (SDPs) are powerful algorithmic tool with wide-ranging applications in combinatorial optimization, control theory, machine learning and operations research. Notably, they yield optimal approximation algorithms for NP-hard problems like Max-Cut [GW95] and other constraint satisfaction problems [RagO8]. While interior-point algorithms and the ellipsoid method give polynomial time guarantees for solving semidefinite programs, memory becomes bottleneck for relatively modest instance sizes. This has prompted research into scalable semidefinite programming algorithms [MHA20] for recent survey.
One of the most popular methods for solving SDPs in practice is the one pioneered by Burer and Monteiro [BM03, BM05], which explicitly constrains the rank of the SDP solution for efficiency.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

This work: Spurious minima exist (no possible global convergence guarantee)
[WW20] possible global convergence guarantce for generic instances
[BVB18] Global convergence guarantee For generic instances
[BVB18] Global convergence guarantoc
p 0
P R 22n
TV
[Bar95, Parti] Above Barvinok-Pataki bound: (MC- optimal value same as (MC. SDP) optimal value
Combined with existing guarantees, our work settles the question of the existence of spurious local minima for (MC-BM) all ranges of the rank p.
Figure 1:
Consider the celebrated Goemans- Williamson SDP relaxation for Max-Cut [GW95]:
min X X
XA,
s.t. X2 = 1 for [n].
(MC-SDP)
x
Here g*x" denotes the set of all symmetric n. X matrices and the cost matrix A E S is typically the adjacency matrix of weighted graph. The above Goemans- Williamson SDP also gives a natural semidefinite programming relaxation for the Grothendieck problem [AN04], quadratic program- ming [Nes98, CWO4), variants of community detection problems [Abb17], and other combinatorial optimization problems; in many of these settings the matrix A may also have negative entries. Instead of maintaining a solution X Saxn, the Burer-Monteiro method explicitly maintains a low-rank solution of the form X = -YY where Y E RDx,, and aims to solve the following optimization problem:
min (A, TY YERnXp
(MC-BM)
s.t. ||X|||2 for E [n].
where Y, E IR denotes the ith row of Y,, taken as a column vector, and |enotes norm. We may also denote the objective of (MC-BM) as OBI(Y) = (A,YY We denote the feasible region
denotes the Fuclidean
Mn.p := {Y R"XP, : || = for i [n]]
(When n is clear from the context or unimportant, we may just write Mp.) Note that MM,, is product manifold since it can be viewed as a Cartesian product of unit spheres in IRP.
This formulation yields significant memory savings when < n by storing Y instead X and has the additional advantage of dropping the positive semidefiniteness constraint. On the other hand, (MC-BM) is a non-convex constrained optimization problem. Local optimization methods like Riemannian gradient descent and other heuristics for manifold optimization constrained optimization are used to solve this non-convex problem with surprisingly good empirical results [BM03, BM05]. This motivates the following question:
When does the Burer-Monteiro method converge to a globally optimal solution?
This question has attracted much recent interest on the theoretical front. It is known that when the rank bound p of the SDP solution is above the so-called Barvinok-Pataki bound 2 /2ni (more formally, p satisfies p(p+1) > ri), a globally optimal solution of rank at most is guaranteed to exist [Bar95, Pat98]. Moreover, below this bound, there exist instances for which (MC-BM) has spurious local minimum [WW20]. When the rank bound p is above the Barvinok-Pataki bound, Boumal, Voroninski, and Bandeira [BVB16. 16, BVB18) showed that for generic instances, 2 any second- order critical point Y of (MC-BM) is globally optimal for (MCBMM), and thus YY is optimal for
2
Note that SDP) can also be reformulated as maximization SDP where the cost matrix is the Laplacian matrix L D A, where D is the diagonal degree matrix. The two formulations equivalent since changing the diagonal the cost matrix just corresponds to adding constant to objective value each feasible point. By generic instances, we mean the guarantee holds for all cost matrices A E gexn except set of zero measure.

---

(MC-SDP) (their result also applies for broad class of SDPs with equality constraints). Under such conditions, known algorithms converge to second-order critical points of (MC-BM), and polynomial- time convergence guarantees can be shown for smoothed instances [BBJNT8 88 PJB18, 18,8, CM19).
On the other hand, for general cost matrices A, the best known bound only guarantees convergence to global optimum of the Burer-Monteiro method when > 2 [BVBI8, 18, Cor. 5.11J. For general cost matrices A of (MC-BM), there is large range for the rank bound p (v2n, where do not know whether the Burer-Montein method works. To the best of our knowledge, it was open whether there exists any instance (not specific to Max- Max-Cut) where the Burer- Montrroo method fails above the Barvinok-Pataki bound. In fact, the authors [BVB18) pose this question:
"It remains unclear whether or not a zero-measure set of cost matrices must be excluded. Resolving this question is key to gaining a deeper understanding of the relationship between (MC-SDP) and (MC-BM)."
_End of Section 6 in [BVB18), mutatis mutandis
Our main theorem resolves this question by constructing an instance of (MC-BM) with spurious local minimum (i.e., a local minimum which is not globally optimal) when p is as large as (n) (note that spurious local minimum is also spurious second order critical point). This result is contextualized in Figure 1.
Theorem 1. For any 2 4 and 2 p n/2, there exist cost matrices for which the associated instance of (MC-BM) has a spurious local minimum.
Combining Theorem with other existing results yields a clearer understanding of the optimization landscape and a characterization of the range of p for which (MC-BM) can have spurious local minima. Furthermore, our result justifies the use of beyond worst-case paradigms like smoothed analysis to obtain global convergence guarantees for the Burer-Monteiro method. (See also Appendix A for further discussion of prior work.)
We also empirically evaluate Theorem in Appendix G. Our experiments suggest that the spurious local minima we construct have significantly larger basins of convergence than our theoretical results guarantee.
Outline of paper. We begin with Section (Preliminaries) which provides necessary background for the construction of spurious local minima in Theorem 1. In Section 3, we list the main lemmas for Theorem and show how Thcorem follows. In Sections and 5, we discuss some of these lemmas in more detail. In particular, Section 4 sketches the proofs that first and second-order critical point. Section 5 contains the full proof that our construction yields a spurious local minimum, with the proofs of key sublemmas left to Appendix D. We present potential follow-up directions in Section 6 (Conclusion) and empirically evaluate Theorem in Appendix G.
construction yields spurious
Preliminaries
Section 2.1 gives an overview of the Riemannian geometry of (MC-BM). In Section 2.2, we use this geometry to give necessary conditions for local minimality and a characterization of global optimality. Section 2.3 provides an overview of Riemannian gradient descent, which is key to proving local minimality Theorem (see Section 5 for details). Section 2.4 contains definitions (including classes of matrices) used in the construction for Theorem I.
2.1 Riemannian derivatives
Mp is smooth embedded submanifold of Raxp [BVB18, Prop. 1.2], and is furthermore an embedded Riemannian submanifold of R=xp [Bou22, Def. 3.55] if we equip the linearizations of M, at each point (known as the tangent spaces-defined below) with restriction of) the inner product (---) on R=xp
Proposition 1 (Tangent space [BVB18, Lem. 2.1]). The tangent space Mp at Y Mp. denoted Ty Mp. is the following subspace of R
MyMp {U E RexP, U.) = 0,for [m]]
3

---

Here, E UR R denote the ith rows of and U respectively, taken as column vectors. (In other words, My is the space of matrices row-wise orthogonal to Y.) We call an element of TyMp a langent vector (at Y).
The Riemannian gradient at Y E Mp grad OBJ(Y), is the orthogonal projection of the classical Euclidean gradient at Y onto TyMp. which yields the following expression (see Appendix B):
grad OBJ(Y) - 2(A - diag(v))Y, where 1/2 = Σ Ass (Y, Vj) for all i E [n]]
(I)
(Note that v E R" is a function of Y. although we write v/ instead of, e.g., v(Y) when Y is clear from context.) We take (1) to be the definition of v from now on.
The Riemannian Hessian of OBJ to Ty M, given by the classical differential of (a smooth extension of) grad OBJ(Y), projected to the tangent space [Bou22, Cor. 5.16]. This yields (see Appendix B):
E Mp. Hess (Y)(Y), is linear, symmetric map from My
Hess OBJ(Y) = 2Projr (AA diag(v))U
for U Ty.Mp. where the linear map Projy R MyM, denotes the orthogonal projector Z||- In what follows, Hess OY)(Y)
onto TyM2 S Rnxp, i.e., Projy (Z) = argmin -U'-1I,
will only appear as part of a quadratic form, yielding the following cleaner expression:
(o),(())UU) for E MyMp, where we used the fact that (Projy (2), U3> = (2, U) for any Z E Ruxp, U e
(Hess (BU(Y) (2Projy ((A diag(v))U), U) = 2 (A
Ty Mp.
2.2 Necessary and sufficient conditions
Recall the definition of local (and global) minimum: Definition 1 (Local/global minimum). Consider the program
min fx)
ZED
where D C RRd DEDi is local minimum if there exists > O such that if E D and |18 - x:|| < we have f(z) S fly) x E is a global minimum if fxx S for all E D.
The following are standard necessary conditions for local optimality, and correspond to the first and second-order critical point criteria that need to be satisfied by any local minimum of (MC-BM) (see [BVB18, Prop 2.4]).
Proposition (First-order critical point [BVB18, Def. 2.3] and [WW20, Prop. 3D). Y Mp is first-order critical point for (MC-BM) if and only if grad OBJ(Y) = 2(A diag(v)) = Ó. Equivalently, Y E Mp is a firstordder critical point if and only if there exists X E In" such that (A - diag( A)) Y 0. If such X exists, it is unique and equal to given by (1).
Proposition 3 (Second-order critical point [WW20, Prop. 4]). A firt-orrer critical point Y E MM is additionally second-order critical point if and only if
(Hess OBJ(Y (BJ(Y)UU)UU) 2 (A diag(v), UUT) 20
for all U E My, and where v is given in (1), (This is equivalent to Hess OBJ(Y) > 0.)
We say critical point local minimum is spurious if it is not globally optimal. Finally, characterize which first-order critical points of (MC-BM) are globally optimal. Since second-order critical points and local minima are also first-order critical points, this also provides characterization of optimality for them.
Proposition 4 (Characterization of optimality for first-order critical points). A first-order critical point Y of (MC-BM) is globally optimal if and only if A diag(v) > 0, where v is given in (1).
While not framed precisely in this way, Proposition 4 follows directly from prior work (see Appendix for details). The proof involves a comparison between the criticality conditions of (MC-BM) and the Karush-Kuut Kuhn-Tuckee (KKT) conditions of (MC-SDP).

---

2.3 Riemannian gradient descent
The analogue gradient descent for optimizing over smooth manifold is Riemannian gradient descent (see [Bou22, Ch. 4] for an introduction), which yields analogous analyses and guarantees. It includes as part of its specification retraction [Bou22. Def. 3.47]. A rectraction on Mp associates to each point Y E Mp map Ry Mp + MM which converts movement in the tangent space to movement on the manifold Mp. We use the natural metric projection retraction [Bou22, Sec. argmin ZeM, II U) Zll. With this definition, it is easy to see that Ry (U) is Y +U followed by normalization of each row. This yields the following Riemannian gradient descent algorithm for (MC-BM):
5.12], defined for Y E Mp, U E Ty Mp as (U)
Input: Initializer ( Mp, step size 1) >
For f 0, 0,1,2,...
y(+1) Ryto (-ngrad (B)()
2.4
Construction-speccfie definitions
Finally, we give a few miscellancous technical definitions which will be used in our construction of spurious local minimum for (MC-BM).
Definition (Axial position). We call the matrix
[(n/2)
Y : (1(g/2)
E (M,.fa/2)
the axial position, where 1n/2 denotes the identity matrix in R
We use the term "axial position" because when we view (n.(n/2) Cartesian product of unit spheres in R2// Y corresponds to placing a single unit vector on both the negative and positive sides of each axis in R2//2
The following sets of matrices will be important in our construction:
Definition (Pseudo-PD, pseudo-PSD). We say matrix M $ is pseudo-PD rrpseudo-positiiv definite") if M(i > for all i E [ni,, where M[i gin-1)x(n-1) denotes the submatrix of M formed by removing the ith row and column. Similarly, we say that M E goxn is pseudo-PSD ("pseudo-positiee semidefinite" if [[i] ž ffr all [m].
Definition 4 (Strictly pseudo-PD, strictly pseudo-PSD), We say a matrix is M E SaxR is strictly pseudo-PD if is pseudo- but not positive semidefinite. We say M is strictly pseudo-PSD if pseudo-PSD but not positive semidefinite. (Note that in both cases we require M t O, not M + 0.)
Clearly every strictly pseudo-PD matrix is also strictly pseudo-PSD DSDu but the converse turns out to be false.
Proof of Theorem
In this section we prove Theorem 1. We focus on the case where n is even and n1/2 and construct cost matrices for which Y is spurious local minimum, since constructions for p n/2 can be easily extracted from the former by padding with zeros. Before this, as warm-up, we characterize those cost matrices for which Y is a spurious first and second-order critical point in the following two propositions. While not strictly necessary for the proof of Theorem 1, Propositions and have far simpler proofs and are interesting in their own right. An overview of the proofs is given in Section 4, and the full proofs can be found Appendix C.
Proposition's 5 (First-order critical point characterization for Y). For (MC-BM) when n/2, the axial position Y is a first-order critical point if and only if the cost matrix A takes the form
BB B
B B
A
+ diag(a)
(2)
for some 12 and B S1x3, Farthermore, Y is additionally spurious if and only if B + 0.
5

---

a,
b
d
b, d
Figure 2: A spurious minimum and corresponding global minimum for = 4, 2.
Proposition 6 (Second-order critical point characterization for Y). For (MC-BM) when = n1/2, the axial position Y is second-order critical point if and only if the cost matrix A takes the form
P P P
P diag(a)
for some E R" and pseudo-PSD P E x Furthermore, Y is additionally spurious if and only P strictly pseudo-PSD.
is not surprising that Propositions 5 and 6 allow you to arbitrarily change the diagonal of the cost matrix. Doing simply corresponds adding a constant the objective value each point and does not change the geometry of the problem."
Next, the following lemma provides a sufficient condition for Y to be a spurious local minimum. This is the most challenging of results prove, and give the proof and discuss the challenges involved Section 5. Key sublemmas are left to Appendix D.
Lemma (Local minimum condition for Y). For (MC-BM) when p n//2, the axial position Y is a local minimum if the cost matrix takes the form
M
M
A =
+ diag(a)
M
M
for some a En" and pseudo-PD M S Furthermore, Y is additionally spurious if M is strictly pseudo-PD.
Actualizing Lemma 1 to construct spurious local minimum requires the existence of strictly pseudo- PD matrices, which we posit the following lemma:
Lemma (Existence of strictly pseudo-PD matrices). The set of l x k strictly pseudo-PD matrices is nonempty for any k 2 2.
We provide constructions of strictly pseudo-PD matrices in Appendix E. Our main nonnegative construction takes the form UUT eTg, where U [ is random matrix. It is shown (UTT) > 0 for all with high probability. One can show that when e > 0 is sufficiently small, the 1k- x (k- 1) principal submatrices UU since UUT T is rank-deficient.
-ely Tels remain positive definite, while UU -ele T-ll y
We use Lemmas and 2 to prove Theorem 1:
Proof of Theorem Lemmas and imply that for even n such that n 2 4, there exists an instance of (MC-BM) with spurious local minimum when p n/2. To construct spurious local minimum for p < n//, we can simply use the construction for = 2p vertices and rank The entries of the cost matrix that correspond additional rows of elements of Mn.,p past n' can be set to 0, ensuring that these additional rows cannot affect the objective value. (See Appendix for details.)
One instantiation of our construction for 4,p 2 illustrated in Figure In this visualization. we think of the nonnegative cost matrix as the adjacency matrix of weighted graph, which is natural
One can easily check that the Riemannian derivatives at any point Y E MM remain unchanged since in (1) will act offset.

---

for (MC-BM). Each row of Y specifies the position of one of the vertices on the unit sphere in R" (for p= 2, the circle shown in gray). We illustrate "heavy" (higher weight) edges with solid lines, and "light" (lower weight) edges with dashed lines. Intuitively, each edge "pushes" its endpoints away from each other, with heavier edges pushing harder. We see by symmetry that this state is in equilibrium (each vertex is pushed equally clockwise and counter-clockwise)) so the gradient is O. Showing that this instance is indeed local minimum much more involved, and requires arguing that if the vertices were perturbed slightly, the heavy edges would still approximately cancel out, and the main force on the vertices would be the light edges pushing the pairs a, c and 6, d back to being diametrically opposite.*
4 Overview of the proofs of criticality (Propositions 5 and 6)
In this section we provide overviews of the proofs of Propositions 5 and 6, which characterize the cost matrices for which Y is spurious/optimal first and second-order critical point respectively (see Appendix C for the full proofs).
4.1 Overview of the proof of first-order criticality (Proposition 5)
Supposing the cost matrix A takes the form (2), one can set À +- where À E R. is the multiplier from Proposition 2, and then observe (A diag(A)) O, implying Y is a first-order critical point. For the other direction, one can show that if Y is a first-order critical point with associated multiplier E IR" (from Proposition 2), then (A - diag (A) 0 implies A - diag(A) must take the block
B B3 B B]
form
for some B E S5x Thus, A takes the form (2) with a + A.
To show Y is additionally spurious if and only if B A 0, note from above that if Y is first-order critical point, the unique associated multiplier À is equal to a. Recall from Proposition 2 that
B B
at first-order critical point, implying A diag(r) A diag(a)
B Such matrix is
B
positive semidefinite if and only is positive semidefinite, and Proposition 4 concludes the proof.
4.2 Overview of the proof of second-order criticality (Proposition 6)
Since every second-order critical point is first-order critical point, we assume the cost matrix A takes the form (2) and show that Y is additionally a second-order critical point if and only if
B is additionally pseudo-PSD. Recall from Section 4.1 that when Y is first-order critical point,
B B
Now, one can observe that an arbitrary element U Ty.Ma/2 must take the following form: Us Umn/2)+i,5 0 for all i E [n/2], and all other entries of U are arbitrary. Due to this, one can show that
A diag(v)
B
B
(Hess OBI(P) 2 (A diag(v), 20 for all U My.Mn/2
2 2 2
(
B
B uu 1) 2 for all Rí U...U Rm/2
B.
where R2 is the subspace of R." consisting of those vectors such that v; = Un/2) = Restricting
[
B[i]
u to only lie in R₁ in (4) is equivalent to the matrix
E ((n-2))(n-2) being positive
B
B[i]
semidefinite, which is equivalent to Bid being positive semidefinite. (Recall that B[j] denotes the submatrix of B formed by removing row i and column i.) Then (4), which takes the preceding statement over all i E [n/2], is equivalent to B being pseudo-PSD. (We note that the preceding portion of the proof is formalized in a slightly different way in Appendix C.) The second half of
Proposition (characterizing when the second-order critical point Y is spurious) follows immediately
"We provide an interactive visualization for the 2 and p = 3 cases at https://vaideh118913 github. www.burrrrrteeiii.
7

---

from the corresponding characterization in Proposition 5, since every second-orde critical point is first-order critical point.
5 Proof of local minimality (Lemma 1)
In this section we give the proof of Lemma 1. We first discuss the challenges involved and why classical techniques break down. We then state the two main sublemmas used in the proof of Lemma 1 (with proofs of these sublemmas left to Appendix D). Finally, we give the proof of Lemma 1 itself.
Challenges. Unfortunately, arguing about the value of the objective function at some point Y near Y is challenging, and classical techniques for proving that Y is a local minimum fail. For example, [WW20], which constructs spurious local minima for (MC-BM) when p < /2n, similarly first constructs spurious second-order critical points and then proves that they are additionally local minima. However, their proof follows because their spurious second-order critical points are non- degenerate [WW200, Def. 3]. which corresponds to the rank of the Riemannian Hessian being sufficiently high. We show in Appendix D (Proposition 9) that for any instance of (MC-BM) when p 2 v2n, all spurious second-order critical points are degenerate, meaning this approach will not work. Furthermore, there is no hope of using the positivity of a higher-order Riemannian derivative (e.g., the fourth derivative) to prove that Y is a local minimum, since it can be shown that all higher-order derivatives are degenerate. (See Appendix D for further discussion of these challenges.)
Overview and key sublemmas. Thus, we provide a novel approach involving Riemannian gradient descent (Section 2.3). For the first sublemma below, recall that a neighborhood of a point Y E Mp set of the form {Y's Mp ||Y Y'Il < E) for some O. The proof is given in Appendix D.
Lemma 3 (Convergence to point with the same objective value). In the setting of Lemma I with pseudo-PD M E x there exists neighborhood N S Ma/2 of Y and n/ > O depending only on the instance of (MC-BM) such that if you initialize Riemannian gradient descent (as specified in Section 2.3) with any step size < of at any point ( E N, it converges to a point such that OBJ(Y) = (Y).
Note that Lemma 3 does not imply convergence Y itself; this is not actually true due to the degener- acy mentioned above. Instead, we show in the proof of Lemma 3 that Y is an antipodal configuration,
&Ma/z for some G E I x Such antipodal configurations (of which i.., it takes the form [-G]
Y is one) all have the same objective value and correspond in particular to "flat" directions from Y. For given (0) it is not a priori clear which of these antipodal configurations it will converge to, so we argue convergence to some antipodal configuration.
In the proof of Lemma 3, we track convergence to an antipodal configuration via a potential + (G,
Mn/2 > 12 where + and only if the input is antipodal. We show that & decreases geometrically over the iterations of Riemannian gradient descent.
G2 (G2)
= ||G, + G2lla. (Here, G2 E x Clearly is
Next, we show via a smoothness argument that with sufficiently small step size, the objective is nonincreasing over the iterations of Riemannian gradient descent. The proof given in Appendix D.
Lemma 4 (OBJ is nonincreasing). There exists î > O depending only on the instance of (MC-BM) such that single iteration of Riemannian gradient descent (as specified in Section 2.3) with any step size 1) < ij cannot increase the objective value, regardless of the starting point.
Lemmas 3 and 4 imply (B) S OBJ(Y) OBJ(Y), and as result the neighborhood N in Lemma 3 certifies that Y is local minimum. The details follow:
Proof of Lemma 1. We first show that if M E x v is pseudo-PD, then is local minimum. We claim that the neighborhood N from Lemma 3 certifies that Y is local minimum. Indeed, let V E N, and initialize Riemannian gradient descent V with step size 7) < min (v/, i) with 7 defined as in Lemmas 3, 4. Per Lemma we know that Riemannian gradient descent will converge to
8

---

point V such that (Y) OVI(V). Since OBJ is continuous, convergence in iterates translates convergence in objective values, and thus the nonincreasing nature of Riemannian gradient descent from Lemma 4 implies OBI(V) & OBI(V). Then OBJ(Y) = OBI(V) = OBJ(V), and we are done.
Now we show that Y is additionally spurious M is strictly pseudo-PD. Indeed, this follows immediately from the last line of Proposition 5. (Recall that any local minimum is also a first-order critical point.)
6
Conclusion
We show that the Burer-Monteiro method can fail for instances of the Max-Cut SDP, for rank up to 2. To the best of our knowledge, prior to our work it was unknown whether the Burer-Monteiro method could fail for any instance of any SDP with rank above the Barvinok-Patte Pataki bound. We settle this question and thus justify the use of smoothed analysis to obtain guarantees for the Burer-Monteiro method.
There are many interesting potential follow-up directions to this work. We provide one construction of (MC-BM) instances with spurious local minima. Our construction has, and relies on, many interesting properties and symmetries. It is possible that some of these properties are necessary, and further analyzing this construction could give insight that allows us fully characterize spurious minima for (MC-BM) instances. Analyzing this construction could also help us understand this interesting threshold phenomenon for (MC-BM) when p = n/2-one dimension higher and there are not only no spurious local minima, there are no spurious second-order critical points at all. Another potential direction seeing if similar techniques can be used construct instances with spurious local minima for SDPs with other structures (not just Max-Cun Cut).
Lastly, we note that limitation of work is that it only points the existence of local minima, and does not give full characterization of when we can expect local minima to exist. We also note that since this theoretical result about optimization landscapes, do not foresee any adverse societal impacts of our work.
Acknowledgments and Disclosure of Funding
LO was supported by National Science Foundation (NSF) REU supplement associated with CCF- 1934931 and an undergraduate research grant from Northwestern University. VS and AV were also supported by the NSF under Grant Nos. CCF-1652491 CCF-193493I, and EECS-2216970. The authors thank the NeurIPS 2022 reviewers for helpful suggestions.
References
[Abb17] Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research. 18(1):6446-6 65331. 2017.
[AN04] Noga Alon and Assaf Naor. Approximating the cut-norm via grothendieck's 's inequality. In Proceedings of the sixth annual ACM symposium on Theory of computing, pages 72-80. ACM, 2004.
[Ba995] Alexander Barvinok. Problems distance geometry and convex properties of quadratic maps. Discrete & Computational Geometry, 13:189-202, 1995.
[BBIN18] Srinadh Bhojanapalli, Nicolas Boumal, Prateck Jain, and Praneeth Netrapalli. Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form. In COLT, 2018.
[BM03] Samuel Burer and Renato D. C. Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, volume 95, pages 329-357. 2003. Computational semidefinite and second order cone programming: the state of the art.
[BM05] Samuel Burer and Renato D. C. Monteiro. Local minima and convergence in low-rank semidefinite programming. Math. Program., 103(3, Ser. A):427-444, 2005.
[BMAS14] N. Boumal, B. Mishra, P-A. Absil, and R. Sepulchre. Manopt, Matlab toolbox for optimization manifolds. Journal Machine Learning Research, (6(4))1455 1459, 2014.

---

[Bou22] Nicolas Boumal. An introduction to optimization smooth manifolds. To appear with Cambridge University Press, June 2022.
[BVB16] Nicolas Boumal, Vlad Voroninski, and Afonso Bandeira. The non nonvex montero approach works on smooth semidefinite programs. In D. Lee, M. Sugiyama, U. Luxburg. I. Guyon, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
[BVB18] Nicolas Boumal, Vladislav Voroninski, and Afonso Bandeira. Deterministic guarantees burer- monteiro factorizations smooth semidefinite programs. Communications on Pure and Applied Mathematics, 73, 04 2018.
[CM19] Diego Cifuentes and Ankur Moitra. Polynomial time guarantees for the burer-monteiro method. arXiv: Optimization and Control, 2019.
[CW04] M. Charikar and A. Wirth. Maximizing quadratic programs: extending grothendieck's 's inequality.
In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 54-60, 2004.
[GW95] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6): 115-1145, nov 1995.
[MHA20] Anirudha Majumdar, Georgina Hall, and Amir Ali Ahmadi. Recent scalability improvements for semidefinite programming with applications in machine learning. control. and robotics. Annual Review of Control, Roboticx, and Autonomous Systems, 3(1):331-360, 2020.
[MMM017] Song Mei, Theodor Misiakiewiez, Andrea Montanari, and Roberto Imbuzeiro Oliveira. Solving sdps for synchronization and maxcut problems via the grothendieck inequality. In COLT, 2017.
[Nes98] Yu Nesterov. Semidefinite relaxation and nonconvex quadratic optimization. Optimization Methods and Software, 91-3))144-160, 1998.
[Pa198] Gábor Pataki. On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Mathematics Operations Research, 23(2):339-358, 1998.
[PJB18] Thomas Pumir, Samy Jelassi, and Nicolas Boumal. Smoothed analysis of the low-rank approach for smooth semidetinite programs. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[Rag08] Prasad Raghavendra. Optimal algorithms and inapproximability results for every esp? In Proceedings of the Fortieth Anmual ACM Symposium on Theory of Computing, STOC '08, page 245 2544, New York, NY, USA, 2008. Association for Computing Machinery.
[WW20] Irène Waldspurger and Alden Waters. Rank optimality for the Moner-Montciro factorization. SIAM J. Optim., 30(3):2577- 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the final paragraph of the conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See the final paragraph of the conclusion.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Our work does rely on any unproven assumptions conjectures.
(b) Did you include complete proofs of all theoretical results? [Yes] Full proofs that do not
fit in the main paper will be provided in the supplementary material (appendices).
10

---

3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] Link provided
in Appendix G.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix G.
(c) Did you report error bars (c.g.. with respect to the random seed after running experi- ments multiple times)? [N/A] We report all data generated.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] We do not report the runtime of our experiments, as this is not relevant to our claims.
4. If you using existing assets (e.g., code, data, models) curating/releasing
assets... (a) If your work uses existing assets, did you cite the creators? [Yes] We use the Manopt manifold optimization package [BMAS14).
(b) Did you mention the license of the assets? [N/A] The Manopt package is open source.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]


Reviews:
[{"review_id": "oQ9oTNB_pn4", "reviewer": "Reviewer_4PkM", "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.\n\nThis 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.", "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?\n\n(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?\n\nTypos:\n\nl173, M should be P\n\np19 starts mixing notation w_{ij} and M_{i,j} for the entries of M\n\nl623, the following display is missing a factor p\n\nl684, the following display is missing some constant factors\n\nl906, should this be \"P contained in *kernel* of Hess Obj(tilde{Y})\"?\n\nl934, rank k should be k-1\n\nl937, U in R^{k x k} should be {k x k-1}\n\nl942, k should be k-1, and l944, k+1 should be k\n\nl964, sigma_k should be s_k\n\nl1012 and the subsequent display, should > be <?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think this is an interesting paper, and would be supportive of its publication in NeurIPS.\n\nThe 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Toj_CvDgAw", "reviewer": "Reviewer_sULy", "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.", "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.\n\n", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n- *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.\n\n- *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.\n\n- *Clarity*: The paper is well-written and organized.\n\n# Weaknesses\n\n- 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. \n\n- *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. \n\n# Minor comments\n\n**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. \n\n**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.\n\n**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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TZL1l9UDLyN", "reviewer": "Reviewer_nF9P", "summary": "**Background for the paper** \n\nSemidefinite 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 \n$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): \n\\begin{align*}\n\\min_{Y\\in\\mathbb{R}^{n\\times p}, YY^\\top \\in\\mathcal{C}}C\\bullet YY^{\\top},\n\\end{align*} \nwhere $\\mathcal{C}$ is the constraint set for the original SDP with $m$ constraints. The benefit conferred by\nthis reduction is that (BM) uses $O(np)$ memory, whereas (SDP) uses $O(n^2)$. \n\n(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\nexists a rank-$\\sqrt{m}$ solution to (SDP). \n\nIn 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*. \n\n**What problem this paper studies** \n\nIn 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**. \n\nThe 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.\n\n", "questions": "Please see above. ", "limitations": "Please see above. ", "rating": 3, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nCould 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. \n\n---------------------------------------------------------------------------------------------------------------------------------------------------- \n\nAfter 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "R9v27EMha-a", "reviewer": "Reviewer_tXww", "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.\n\nThe 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)? \n\nQuite 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. \n", "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. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nThe 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: \n\nMei et al. \"Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality,\" COLT 2017.\n\nIndeed, 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. \n\nStill, 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept