Polynomial time guarantees for the Burer-Monteiro method
Authors: Diego Cifuentes
Ankur Moitra
Venue: NeurIPS 2022 Accept (2022)
Keywords: Semidefinite programming
Burer-Monteiro
Low rank factorization

Abstract: The Burer-Monteiro method is one of the most widely used techniques for solving large-scale semidefinite programs (SDP). The basic idea is to solve a nonconvex program in $Y$, where $Y$ is an $n \times p$ matrix such that $X = Y Y^T$. We show that this method can solve SDPs in polynomial time in a smoothed analysis setting. More precisely, we consider an SDP whose domain satisfies some compactness and smoothness assumptions, and slightly perturb the cost matrix and the constraints. We show that if $p \gtrsim \sqrt{2(1{+}\eta)m}$, where $m$ is the number of constraints and $\eta>0$ is any fixed constant, then the Burer-Monteiro method can solve SDPs to any desired accuracy in polynomial time, in the setting of smooth analysis. The bound on $p$ approaches the celebrated Barvinok-Pataki bound in the limit as $\eta$ goes to zero, beneath which it the nonconvex program can be suboptimal. Our main technical contribution, which is key for our tight bound on $p$, is to connect spurious approximately critical points of the nonconvex program to tubular neighborhoods of certain algebraic varieties, and then estimate the volume of such tubes.

Polynomial time guarantees for the Burer-Monteiro method
Diego Cifuentes
Ankur Moitra
School of Industrial and Systems Engineering
Department of Mathematics Massachusetts Institute of Technology
Georgia Institute of Technology
Atlanta, GA 30332
Cambridge, MA 02139 moitra@mit.edn
diego. cifuentes@isye. watplsyyy.gatt..eeee.
Abstract
The Burer-Monteiro method is one the most widely used techniques for solving large-scale semidefinite programs (SDP). The basic idea is to solve nonconvex program in Y, where is an n X P matrix such that X YY". We show that this method can solve SDPs in polynomial time in smoothed analysis setting. More precisely, we consider an SDP whose domain satisfies some compactness and smoothness assumptions, and slightly perturb the cost matrix and the constraints.
We show that if 2 21(1-m)m where is the number of constraints and ! >> O is any fixed constant, then the Burer-Monteiro method can solve SDPs to any desired accuracy in polynomial time, in the setting of smooth analysis. The bound on approaches the celebrated Harvinok-Pattae bound in the limit as goes zero, beneath which it the nonconvex program can be suboptimal. Our main technical contribution, which is key for our tight bound on is to connect spurious approximately critical points of the nonconvex program tubular neighborhoods of certain algebraic varieties, and then estimate the volume of such tubes.
Introduction
Let S" be the set of nxn symmetric matrices. Given matrices A C S" and a vector be RT consider the semidefinite program (SDP):
min X
C
X
s.t. A(X) =b X
(SDP)
where A: S" + m X (A1 ... An X) is linear map and the notation X > 0 in indicates that is positive semidefinite (PSD) matrix. Also consider the least squares SDP
min Xes"
[|A(X)
b11?
s.t.
X
(SDP
Though interior point methods solve SDP and (SDP PL polynomial time, they often have memory problems for large values of n. The Burer-Monteiro method [11 is one of the most widely used procedures for large scale problems. Several papers have worked in understanding the practical success of this method, e.g.. 12 Although various results have been shown, they all fall short of showing that one can reach an approximately optimal solution of (DPPVSDPL in polynomial time. This paper provides the first polynomial time guarantees for the Burer-Monteine method.
The Burer-Monteiro method consists in writing X -YYT for some gaxp, and solving nonconvex optimization problem in terms of Y. For (SDP) we get the problem
min C YYT Y
MT (Y R A(YYT) b},
(BM)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

and for (SDP) we get the unconstrained problem
min Y YEREXP
[A(YY)) - -b]..
(BMc)
We focus now on problem (SDP), though our results apply to (SDP as well. Let r(k) == [++1)
be the k-th triangular number. It is known that problems (SDP) and (MM) have the same optimal
value for any such that r(p) 2 m,; this is known as the Barvinok- -Pakkii bound [3 29]. But due
to nonconvexity, local optimization methods may converge critical point of (BM) which is not
globally optimal (34). In this paper we are mainly interested in 2nd-order critical points (abbreviated as 2-critical points).
Problem BM has been well studied, most remarkably in the sequel of papers (5 9 10 30J. Boumal
et al. 19 [0]
showed that (BM) has no spurious 2-critical points when T(p) > m, assuming that the feasible set 27 is a smooth manifold and that the cost matrix C is generic. Hence, the Burer-Monteiro method converges to the global optimal solution as long as the cost C is outside certain "bad" set, which has measure zero. However, this analysis only applies to the limit points. The follow up works (5) and (30) provide finite-iteration guarantees, though for values of p larger than the Barvinok-Pai Pataki bound. They introduce a smoothed analysis (32) setting in which the cost matrix C is subject to small random perturbation of magnitude a. Such perturbation ensures that C' stays outside the "bad" region, so the limit points are globally optimal. They then argue that certain notions of approximate criticality for BM) guarantee approximate optimality for SDP) when (p)) Z m log(Sl(/R1/1)) T))
Despite the earlier work, the question of whether the pletely solve problem (SDP) in polynomial time has not been yet resolved. The works (0) do not provide end-to-end polynomial time guarantees and make structural assumptions the problem, as will be further discussed in the related work section. In particular, finding a feasible solution to (SDP) that could serve as initial point is complicated and practically relevant problem, but it has not been addressed before. In addition, the lower bound on is qualitatively wrong, as it is not only larger than the Barvinok-Patail bound, but also gets worse the magnitude of the perturbation decreases.
method can be used to com-
In order to fully solve (SDP). we propose a 2-stage procedure. First, solve (BM to either get a point Yo that is approximately feasible, i.e.. A(YoY,))) se b, or to prove that such point exists. Second, solve (BM) to get an approximately optimal point, starting with point Y, from the first stage. We prove that this scheme is successful when (p)) (1+7))m, for arbitrary constant 7) > 0.
The next theorem provides polynomial time guarantees for the second stage. The complexity is with respect to the setting of a smoothed analysis, in which the cost matrix C' is perturbed.
Theorem 1 (SDP) in polytime). Let p such that T()) > (1+m)m, for fixed n > 0. Apply random perturbation of magnitude a to the cost matrix C. Assume that Mi is compact and smooth (LICQ holds). Solve (BM) using a constrained optimization method with 2nd-order guarantees (e.g.. Theorem 4 initialized at an approximately feasible point Yo. Then, after poly a -1) iterations, we get a point Y such that Y Y approximately optimal for (SDP) with high probability. A more detailed version of this result, with explicit optimality and complexity constants, appears in Theorem 9
Note that our bound on p does not depend on the magnitude of the perturbation, as opposed to earlier works. This improved bound relies on technical novelty of this paper, namely, using sophisticated tools from real algebraic geometry for concentration bounds. Indeed, we characterize the presence of spurious approximately critical points through tubular neighborhoods of algebraic varieties, and make use of effective bounds for the volume of such tubes [4[23] (7]. On the other
hand, (9 [0] uses simple dimension arguments, while (5 30 rely on random matrix theory.
The following theorem provides polynomial time guarantees for the first stage. We again consider a smoothed analysis setting, but this time perturbing the matrices A; that define the linear map A.
SSP P in polytime). Let p such that T(p) > (1+n)m, for a fixed 1) > Apply a random perturbation of magnitude o to the constraint map A. Assume that the sublevel sets {Y: : ||A(YY*)-bi]] S a} are compuct. Solve (MM using an unconstrained optimization method with 2nd-order guarantees (e.g. {15] 16)). Then, after poly(n, iterations, we gel point Y such that YYT is approximately optimal for (SDP with high probability. more detailed version of this result, with explicit optimality and complexity constants, appears in Theorem 10
Theorem 2
2

---

Theorems and 2 together provide end-to-end guarantees for solving (SP)). with polynomial smoothed analysis complexity. The main assumptions are that p slightly above the Barvinok Pataki bound, while the feasible set is compact and smooth. In the general case, we require that both C, A are slightly perturbed. If feasible point of the (SDP) is known, then Theorem T Jalone enough.
We point out that problem (SDPL) is a matrix sensing problem which is of interest in its own right, independent of its connection to SDP feasibility. The guarantees from Theorem 2 apply even if the optimal value of (SDPL) is strictly positive (i.e., there is no X with =())=b). There are earlier
works 6 2 26) proving global optimality guarantees for the nonconvex problem (BM w.). but they all rely on the restricted isometry property (RIP). To the best of our knowledge, Theorem provides
the first global guarantees for (BML that do not rely on RIP.
Related work
We first discuss (SDP). Early work by Burer and Monteiro [12 and by Journée et al. 22 gave strong indications that BBM) has spurious critical points above the Barvinok-Pataki bound. A formal proof was given by Boumal et al. [5.9] under a genericity assumption. Subsequent work by Bhojanapalli et al. [5] and Pumir et al. (30] investigated the case of approximately critical points under smoothed analysis. The Barvinok-Paati
bound was recently shown to be optimal up to lower order terms for general SDPs (34), though for structured families of SDPs smaller rank might 19 extended the results from 99) to SDPs with multiple PSD constraints.
suffice 28) The paper
28
The works [5] 30) are the closest to this paper, but they do not provide end-to-end polynomial guarantees for solving general SDPs (nor is claimed). In particular, neither of them discuss initialization or feasibility. The paper [30] relies on Riemannaian optimization, which is only practical for very special SDPs (like the maxcut SDP). In the general case, the retraction operator is penalized version of (SDP). It has the crucial catch that they require a preprocessing step that in general is as hard as solving another SDP. Since solving auxiliary SDP is required, it fails explain why the BM method improves over general SDP solvers. In addition, the optimality guarantees in (5) are with respect to the solution of the penalized problem. Translating their results into polynomial time guarantees with respect to the original SDP is nontrivial due to interdependence between the penalty parameter, the perturbation magnitude, and the target precision" In contrast, our paper does provide end-to-end polynomial time guarantees, and even better, our results hold down to the Barvinok-Patte bound.
computationally intractable. The paper (5) relies
Problem SDP. (g) has been well studied in the matrix sensing community. Bhojanapalli et al. [6] showed that (BM has no spurious local minima under the RIP condition, and they also provided polynomial time guarantees. Similar results have been derived later, e.g., [22] Note that RIP is a very strong assumption about the condition number of the linear map A, particularly since the RIP constant needs to be small (35). In contrast, our result in Theorem 2 simply assumes small perturbation around a worst-case instance A. The comparison of smoothed analysis with RIP is akin to assuming that matrix has nonzero smallest singular value (and getting bounds that depend on inverse polynomials on this quantity), rather than assuming its condition number is close to one.
2 Critical points in nonlinear programming
Unconstrained case.
Consider the optimization problem
min yER"
[wv),
(Pin)
with f Rd + R twice continuously differentiable. A vector y E R" is a 2nd-order critical point for (Pun)) ) abbreviated 2-critical, if fzy) = o. v²f(g) 2 O. Practical optimization algorithms
cannot obtain a solution satisfying these equations exactly. Hence, we relax these conditions.
Definition 1. Given E2, E R,, vector y is approximatel 2-critical (AC) for (Pun if:
|Vf(') E1,
v² 2 -
(I)
'Translating optimality guarantees of the penalized problem to the original SDP requires tuning the penalty
parameter μ. The straightforward choice is μ 0)), where is the target precision. This leads to high
Lipschitz numbers, complicating the complexity analysis (c.g., Theorem 3 does not apply). In addition, (5)
Thm 13] constraints the perturbation magnitude by o² > 0/2 > 11121112-1) Hence, the results
seem require large perturbations, while in smoothed analysis we interested in small perturbations.
3

---

[f(il) There is an algorithm that, when initialized evaluations of f, h and their derivatives to produce an Several algorithms for unconstrained optimization with provable convergence guarantees are known. Recent work has focused on deriving algorithms with finite-time guarantees. In particular, the trust region method computes an (E1, ( #2)-AC point in ((max{E " ")) iterations [16], and the
adaptive regularization with cubics (ARC) method takes (mmax -2 E2 ()) iterations [15). We
formally state the result for the ARC method.
Theorem 3 ( (15) D. Assume that there exists a > 0 such that a point yo with f(0) I a is known, and the functions J. V. V f are uniformly bounded and Lipschitz continuous the set {y f(y) S a... The ARC method initialized at yo requires O (max{=; -2 ==="") iterations to produce an F21A point y. Furthermore, each iteration requires O(1) evaluations of f and its derivatives.
Constrained case.
Consider the nonlinear program
min f(V), D. (v E TRT. h(v) 0}, VEMR
(Pcon)
with R +R" R twice continuously differentiable. The Lagrangian function is [yy (1))))))(() A vector y R is 2-crifical point if there are multipliers À Rm satisfying some first order and second order optimality conditions. As before, for practical optimization we need consider notion of approximate criticality.
Definition 2. Given E2) E R approximately 2-critical (AFAC) for Poon if:
7 14,, pair (y. A) is (E, (E, appprxxiiaall feasible
||((y)] S Eu,
LV A) S E1,
(2a)
n² my L(U. A)u 2 -E (Vu: |||| 11, /
(2b)
In the constrained case, for local minima to be critical point need some regularity conditions. One such condition is the linear independence constraint qualification (LICQ), that states that Vh(y) full rank. This equivalent to M1 being smooth at y for the case of complete intersections (i.e., codim 2t = m). We next introduce a quantitative version of LICQ.
Definition 3. For 0> 0, say that Q-LICQ holds at if the singular values of Vh(y) are at least ø.
Several local optimization methods for (P con with provable convergence guarantees are known. In particular, augmented Lagrangians [T] and trust-region methods (20) $15.4] converge to 2-critical points. Recent work has focused on finding algorithms with finite-time guarantees. The complexity of computing approximately 1-critical points was studied in, e.g.,
18 2T].
As for approximately 2-critical points, we only aware of [14 (1. But both papers a different 2nd-order condition, which is not easy to translate into our setting. Nonetheless, in Theorem 4 below show that AFAC points can be computed in polynomial time. The proof of this theorem is in Appendix A and relies on a variant of the method from [1]. To the best of our knowledge, this is the first polynomial time bound for computing 2-critical points using the standard notions of criticality.
Theorem 4. Assume that there exist B, E IR,, such that a point yo in the set Mg {y [(b()))
is known, the functions f. f. f. Vh; r² (i E (m]) are uniformly bounded and Lipschitz continuous on Mg, and g- e-LICQ holds at all y E Mg. Let E1,) E RR.. 7 E R, such that
ED S B,
1151,
E I
1 R E0E2.
72 2
(3)
TO
where RA 2+2 L : = max,
at yo. requires O (max(=0 E -2 E E2
(EFT)-AFAC pair (y, A), with ||]|| S Rx.
Remark. Theorem Jassumes that g-LICQ holds everywhere in Mg, an assumption which can only be guaranteed when 9 is very small. Hence the initial point yo must be approximately feasible.
3 Optimality of critical points of (BM)
In this section we will show that problem BM has no spurious approximately feasible approxi- mately critical (AFAC) points with high probability. This means that any AFAC point of (BM) is approximately optimal for (SDP). We consider smoothed analysis setting in which the constraint

---

variables A, b are fixed, and the cost matrix C' is subject to small random perturbation. We will restrict our attention AFAC pairs (Y, A) of bounded norm. Hence, we assume that ||||| S Ry and ||a|| S R, for some fixed constants Ry, Rx-
crucial step toward theorem is a geometric characterization of the spurious AFAC points in terms of tubes around algebraic varieties. We then take advantage of known effective bounds for the volume of such tubes [4 227.
From now on, we use the Frobenius norm for all matrices.
3.1 Spurious approximately critical points
The optimality conditions for (SDP) are well known: (A) is the following slack matrix
where
S(A) = A- E S",
and A' :. 1m- - A Ee ArA is the adjoint of A. We now relax the optimality conditions.
Definition 4. Let = (Eu, E1, E2) e _ A pair (X, is e-approximately optimal for SDP if:
||A(X) bll cu.
||S(A) S E1,
x S(2) = -E2 In
It is known that e-approximately optimal solution is at distance O(Ieell) from optimal solution under nondegeneracy assumptions
33). We can also give a simple bound on the optimality gap.
Lemma 1. If X) is e-approximately optimal for (SPP) then
C. S C X + coll-|| E1 E + 82 Xllv
4 feasible X.
Proof. The lemma follows from the following equations:
C A A(X) S()) X A (82la) x = 3-b--2/|Xi|vn
x.b X- X(X(()) |Â [[X]|] 2 X -
A A(X(X)= X-X(X) S()) X ||((A) C -
We proceed to problem BM) This is special instance of the nonlinear program
with f(Y)
pon
C. YY and h(Y) = A(YY") ) - b. The Lagrangian function is L A) = S(
YY + 6
The criticality conditions for (BM obtained by specializing (2).
Definition 5. Let (5o, E1, 22) R 7ER+. A pair (Y, is (e, A)-AF for BM if:
|A(YY))) - bll ED. |S(A)Y| EI,
(5a)
S(A) UU 2 2- (VUER"XP |0||= [A(UY")) ST).
(5b)
We are ready to formalize the concept of spurious critical points.
Definition 6. Let Ry, RA E ER_ be fixed and let (Y, such that ||Y| S Ry and ||^]| S Rx. Given = -Eo, (1,,)1,E2) E R 7 RR, (Y, is spurious (-FFAC if (Y,A) is (e,7)-AFAC for (BM) but (YYT, X) is not e' approx. optimal for (SDP) for g' :- (Eo, Ry A pair (Y, spurious exactly critical if the above holds for e =0, 0,7=0 0.
3.2 Statement of the theorem
We present the main result this section. Let A, be fixed, and let C' be obtained from a random perturbation of magnitude around some fixed C. Concretely, C' is uniformly distributed on the Frobenius ball (,(C) C S of radius a centered at C. Consider the set EE,7 C S", consisting of all cost matrices for which there is spurious AFAC point:
Ce, {C e S" A( spurious (E, 7)-AFAC pair).
We show that if 7(p) m, then the probability Pr[C Ee,n] + 0 as the ratio 51/7 - 0.
5

---

Theorem 5 (critical + optimal), Let p such that T(p)>m. LetEER YER,, Let C be uniformly distributed on the Frobenius ball (C) Then
Pr[C' E GE,7 Σ 4e (-()) (3x) (An /o)
where 8 ==ll||ll/> and == Rx RA provided that ó < <o/4//0 a/4n".
The following corollary shows that when the stronger condition T(p) > (1 (1+7))m holds, where a fixed constant, then we can derive high probability bound while maintaining polynomially bounded. Its proof is a straightforward manipulation.
Corollary 1. Consider the setup from Theorem
5
Assume that r(p) 2 (1+7)m + nyt and 8 S
(1/3k) (a (Ann / for some n, > 0. Then Pr|C E Ban S 4e (0/12kn2))
3.3 Tubes around varieties
Our proof of Theorem 5 relies on geometric characterization of the set 6,,-- Such characterization is known for the case E = 0 O, corresponding to exactly critical points. It was shown in (10), see also [19), that the existence of a spurious exactly critical point implies that C' lies in a certain algebraic variety of g", as follows:
3 (spurious exactly critical point)
C' S Sn-p + Im
where -h = (X: rank X S n-pp a variety of bounded rank matrices, and Im A" is the linear space spanned by ....., Am- Hence, we have that Co.0 C Sh-p + Am. When r(p) > m, the variety S Sn Im A" is properly contained in S It follows that 60,0 has measure zero and hence, for generic C, there are no spurious exactly critical points.
We show below that for approximately critical points the situation is analogous, except that we need consider tubular neighborhood around the variety S
A".
Definition 7. Given W C S", 5 E TR,, let tubes W = {X E S" :W W.t.t |X- W| s 6).
Proposition 1. Let 6 == =1 A|llA|//> and Bx = E ||l|| S R2). Then
Ee,7 C tubes (S p) + (Bx).
The next lemma is the key ingredient for Proposition I shows that Y a spurious AFAC point, then its smallest singular value o (Y) is bounded from below. This is generalization of a previous result by Burer and Monteiro [12] about exactly critical points. An analogue of this lemma is found in 30 Lem.3.2] for the case where Eo = 0.
If (Y) S 7/1AA|]. then YYT is el- approximately optimal for SDP with E' = (co, Ry
Lemma 2. Let Y be an (EAA)-AFAC point of (MM
Proof. Let (Y, A) satisfy (5). and let us show that (YYT, A) satisfies (4) The first three conditions
in 4 are easy check. We proceed show the last S(A) - Given unit vector u R
we need to show that u² (())u2 E22. There is unit vector E E such that |Y = (Y The
matrix U U== satisfies ||U||= - and
JUY & ||
Then |A(UY>)]] so by (bb) we have
-82 s S(X)+UUT
|= (())u) nt S(A)u.
Proof of Proposition 1
Let C - be,y, so there a spurious (E, AFAAC pair (Y, By Lemma must have o, / ||| Let S = 5()), and note that / by 5a Then
di -h-
( S (1S(11/,(M)) <,
(6)
so that C' A(A)+ tubes tubes((hh_)) +A

---

By Proposition the set of "bad" cost matrices e,, is contained in a tube around a variety. To prove Theorem we need an upper bound on the probability mass of this tube. The computation of integrals over tubes has long history in differential geometry (23). Effective bounds for these integrals were shown in 27]; they were used for smooth analysis the first reference. We will use the following recent bound.
Theorem
[4, Thm.1.1J) Let C. IR be a real variety of codimension e defined by polynomials of degree most D. Let be uniformly distributed the Euclidean ball B, (i) TR. If the ratio 0/5 2 (4D+1)(k-00 (k-)). then we have that Pr(æ E tubes (V) I 4c(4k:D5o)),
c)2
Let Bx I be the ball of radius R1 centered at zero. Consider e-net A of Bx, where e = 0/||A11. It is known that (3Rx/e)m = (3k/8)m) points suffices. Observe that
Proof of Theorem 5
(Bx) C A"(tube, (W)) c tubes (A (N)),
(7a)
Ce, C tubes (S A C (S. p
(7b)
Recall that 8 is a variety codimension rp) defined by equations of degree n n-p+1. For any l E N. Theorem gives
Pr(C-A E (ube)s(S",,)) < 4<(sr())/0--t1))/))) < 4e(4n28/o))
Finally, the union bound gives
Pr[C E Ben) S #W- E (St < (3k/8)" 4e (4n (4n"8/a)
4 Optimality of critical points of (BML)
In this section we will show that BBM has no spurious approximately critical (AC) points with high probability. This means that any AC point of (BM is approximately optimal for (SDP Hence, we can solve the least squares problem (SDP)) ta to global optimality using the Burer-Monteiro method. Note that if (SDP) feasible, then the optimal value (SDP) is zero. Nevertheless, the results of this section apply to an arbitrary instance of (SDPL) even if the optimal value is nonzero. Appendix contains the proofs the lemmas, propositions, and theorems from this section.
We proceed to formalize the notion of spurious critical points. The optimality conditions for the 0, > ((X) > 0, where S(X) is the gradient of the
convex problem (SDP)) are: S(X) least squares objective function f(X) = ||A(x)-bl]3
S(X) Vf(X) 2.4" 2.4' (A())))) E S".
We call X approximately optimal either A(X) Ru or the above conditions are almost satisfied.
Definition 8. Let (5o, 81, 52) E matrix X 0 is e-approximately optimal for (SDPt. if
||A(X)bb] ca or (IIS(X)XI < and S(X) > -82 In).
(8)
The following lemma bounds the optimality gap for the second case in 8). Lemma 3. Let X ES4 such that [|S(X)8] & 5(X)= 2 -e2nn Then
f(8) S f(X) E /ivn E2 X1Ivn
The
problem BM is special instance of the unconstrained optimization prob- lem (Pun) The criticality conditions for BM are obtained by specializing (..
Definition 9, Let (2), Y <R is (E1, aappooxixxi 2-critical (AC) for (BM if
SCYYTYYI $ Eι.
(9a)
S(YYT) . UUT + 44[A(UYT))I -22 (VUER"XD, [)]==
(9b)
We are ready to formalize the concept of spurious critical points.
Definition 10. Let Ry E R4 be fixed and let Y with ||Y|| < Ry. Given e (Ea, E1, E2) E R3, Y spurious e-AC is (01, ACC for BM but YYT is not apppoxx optimal for (DD))) (g) for e' = (E,, RyE1, 552). ) Y is spurious exactly critical if the above holds for 0.
7

---

We assume here that b E IR' is fixed, and we vary the linear map A. We identify A with the tuple of matrices AA.....Am)) and hence view it as an element of the Euclidean space (S") We assume that A is uniformly distributed on the Euclidean ball (A) c (8") of radius a centered at A. Consider the set o C (8*) consisting of all A for which there is spurious AC point:
de = { (s")" .YY spurious e-AC point).
We show that if (D) m, then the probability Pr[A E de] + the ratio E1 / 0.
Theorem 7 (critical feasible). Let p such that ((p)>m, and E R2. Let A be uniformly distributed on the Euclidean ball B. (A). Then
Pr[Ac E de) & 4e 5T (3x) (2n
where = EI = 2(R,, R RA, and RA = || provided that 8 < OE0/ Ann Anêm.
As before, we can derive a high probability bound when =(p) > (1 (1)m)..
Corollary 2. Consider the setup from Theorem 7 Assume that T (p)) 2 (1+1) m ntt, Eu 2 po and Then Pr[ E Ae) S 4e (po² /6kn"m))
8 < (1/3x) (2n" m for some 17, t,
As in Section 3 our proof of Theorem Feellee on geometric characterization of the spurious AC points. First consider the simpler case of spurious exactly critical points 0). The following equation is a consequence of our analysis:
(spurious exactly critical point)
S pn-p Im_4" is nontrivial.
This implies that the set do has measure zero when (p)> In order to handle the case e >> 0 we rely again on tubular neighborhoods, as stated next.
Proposition 2. Let = RA/ V Dx == (MER Tm 250 Then for A E de we have that Lubes(S) (Sh (AA #
R 2(R [6[]).
Polynomial time guarantees
We ready to derive polynomial time guarantees for the Burer-Monteiro method. The proof of Theorem relies on two facts: (i) the method from Theorem finds an AFAC point of (BM) in polynomial time; (ii) Corollary shows Cohollary[sshows that AFAC point of (BM) is approximately optimal for (SDP) with high probability. Hence, the Burer-Monter method solves (SDP) in polynomial time in the setting of smooth analysis. The proof of Theorem 2 is analogous, except that it relies on Theorem 3 and corollary 2
Appendix provides explicit complexity estimates for solving (SDP) and SDP)s using the Burer- Monteiro method, indicating the precise optimality guarantees of the output.
Experiments
We present experimental results complement our theorems. We rely on the library NLopt [24] (MIT license) to solve the nonlinear problem (BM). Concretely, we use the augmented Lagrangian method (ALM) implemented in NLopt (which is based [8], and we the preconditioned truncated Newton method as the subroutine. We also rely on the commercial solver Mosek for SDPs.
For our first experiment we consider random SDP with planted solution. More precisely, we take 7, a matrix Xo E g50, Xo 2 0 of rank r E 7, 12), and generate a random SDP for which Xo is an optimal solution. To do so, and then find a cost matrix C' the normal cone of Xo- We generate 100 random SDPs for each r We solve these SDPs with the Burer-Monteirg method, using different values of p (the rank of Y) and random initializations. The initial points are matrices with i.i.d. normalized Gaussian entries. Figure [ shows the percentage of experiments solved correctly for each value of and p. We regard an experiment as "correct" the criticality conditions from are satisfied.
generate ;= -(r) random constraints that are satisfied at Xo.
Figure | illustraaes that there is sharp phase transition at the Barvinok-Patale bound the Barvinok- bound, the Buner-Monteiro method solves most instances. Beneath the Barvinok- Pataki bound, it is not just that our techniques stop working, but that the method itself usually
Above

---

100
Experiments solved (%)
20
F-4
r-3
6-2
r+1
r+2
r+3
the factor matrix
Figure 1: Performance of the BM method for random SDPs with planted solution of rank r.
fails. Note that previous work [ 30
required p to be larger than 3r/v2. However, we see from
experiments that the phase transition is much sharper than this. Observe that, even for p r, the number of experiments solved is always below 100%. Nonetheless, the number of bad instances seems get smaller for larger values of p. This agrees with result from Theorem 5
For the second experiment we fix the parameters n := 50, m := 28, and p == r= Among the 100 random SDPs considered in Figure I we take instance for which the Burer-Monteiro problem performed badly. We then perturb this seemingly bad SDP by adding varying amounts of noise For each noise level solve 70 random experiments, in which both the perturbations and the initializations are random. The perturbations consist adding to each matrix a random matrix with i.i.d. Gaussian entries scaled by the noise level. Figure summarizes the results obtained.
100
50,
m.
28, p p=r=7
Original SDP (a=0)
Perturbed SDP (a=0.2)
109
60
Criticality residual
Experiments solved
2
60
10
40
20
10
mean std
meaan
std
0.04
0.08
0.12
0.16
0.2
6
10
12
10
12
magnitude
(a) Fraction of SDPs solved
(b) Iteration progress
Figure 2: Performance of the BM method after perturbing "bad" SDP with different levels of noise.
Figure 2a shows the percentage of instances for which the Burer-Montein method succeeded for each noise level. The percentage with respect the random perturbation and the random initialization. For the unperturbed problem (a = 0) the method succeeds only for 52% of the random initializations. This percentage increases
add noise. For = 0.2 the method succeeds 87% of the time. Figure 2b shows the progress of the algorithm for the cases a = 0 and a = 0.2. The progress is measured terms the residual of the criticality conditions. The figure shows the mean and standard deviation of the residual for each iteration of ALM.
Figures 2a and 2b illustrate the advantages of smoothing badly behaved SDP. Theorem predicts that the complexity the algorithm is proportional to a -d for some exponent d. So for a fixed number of iterations N, we should set the noise level proportional to N-1/ However, our bounds were shown for the algorithm from Theorem We do not know if they also apply to ALM.

---

7 Discussion
We study the Burer-Monteiro method for solving the problems (SDP) and SDDP b.). We provide the first polynomial time guarantees, using smoothed analysis setting. Previous analyses for (SDP) did not provide end-to-end guarantees and made structural assumptions on the problem instance, while previous work for (SDP)) relied on the RIP condition, strong assumption.
The main technical novelty of this paper is the use of volumes of tubular neighborhoods of varieties for deriving concentration bounds. This allows our results to hold even as p approaches the Barvinok- Pataki bound arbitrarily close. Although the Barvinok-Pateee there are better bounds for some special classes of SDPs. An important open question is whether our results could be extended to allow for smaller values of p in those special classes.
bound is optimal for general SDPs,
The Burer-Monteiro method is not a single algorithm, but a family of algorithms, one for each local optimization method for solving BM). Similarly, our guarantees Theorems I and apply for any local method with 2nd order guarantees. The only method we are aware that provably computes AFAC points of (BM) efficiently is the one in Theorem 4 It would be interesting to extend our results to classical optimization methods, such as ALM, which have robust implementations.
Acknowledgments and Funding Disclosure
Ankur Moitra was supported in part by a Microsoft Trustworthy Al Grant, NSF CAREER Award CCF-1453261, NSF Large CCF-1565235, David and Lucile Packard Fellowship, an Alfred P. Sloan Fellowship and an ONR Young Investigator Award.
References
[1] Roberto Andreani, Ernesto G Birgin, José Mario Martínez, and María Laura Schuverdt. Second- order negative-curvature methods for box-constrained and general constrained optimization. Comput. Optim. Appl., 45(2):200-233 2010.
[2] Afonso S Bandeira, Nicolas Boumal, and Vladislav Voroninski. On the low-rank approach for semidefinite programs arising in synchronization and community detection. In Proc. Conf. Learn. Theory, pages 361-382, 2016.
[3] Alexander I. Barvinok. Problems distance geometry and convex properties of quadratic maps. Discrete Comput. Geom.,
1995.
[4] Saugata Basu and Antonio Lerario. Hausdorff approximations and volume of tubes of singular algebraic sets. Mathematische Annalen, 2022.
[5] Srinadh Bhojanapalli, Nicolas Boumal, Prateek Jain, and Pranceth Netrapalli. Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form. In Conf. Learn Theory, pages 3243-3270, 2018.
[6] Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Global optimality of local search for low rank matrix recovery. In Adv. Neural Inf. Process. Syst., pages 3873-3881, 2016.
[7] Ernesto G Birgin, JL Gardenghi, José Mario Martinez, Sandra A Santos, and Ph L Toint. Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models. SIAM J. Optim., 26(2):951 2016.
[8] Ernesto G Birgin and José Mario Martínez. Improving ultimate convergence of an augmented Lagrangian method. Optim. Methods Software, 23(2):177-195, 2008.
[9] Nicolas Boumal, Vlad Voroninski, and Afonso Bandeira. The non-convex Muner-Monteiro approach works on smooth semidefinite programs. In Adv. Neural Inf. Process. Syst., pages 2757-2765 2016.
[10] Nicolas Boumal, Vladislav Voroninski, and Afonso Bandeira. Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs. Commun, Pure Appl. Math., 2019.
[11] Samuel Burer and Renato DC Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program., 95(2):329-357, 2003.
10

---

[12]
Samuel Burer and Renato DC Monteiro. Local minima and convergence in low-rank semidefinite programming. Math. Program., 103(3)427-4444 2005.
[13] Peter Bürgisser, Felipe Cucker, and Martin Lotz. The probability that slightly perturbed numerical analysis problem is difficult. Math. Comput., 77(263):1559-15555 2008.
[14] Coralia Cartis, Nicholas IM Gould, and Ph L Toint. Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization. J. Complexity, 2018.
[15] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function-and derivativee-vallutiio complexity. Math. Program., 130(2):295-319, 2011.
[16] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Complexity bounds for second-order optimality in unconstrained optimization. J. Complexity, 28(1):93-108, 2012.
[17] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. On the evaluation complexity of cubic regularization methods for potentially rank-deficient nonlinear least-squares problems and its relevance constrained nonlinear optimization. SIAM J. Optim., 23(3):1553-1574 2013.
[18] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. On the complexity of finding first- order critical points in constrained nonlinear optimization. Math. Program., 144((-2)93--166 2014.
[19] Diego Cifuentes. On the Burer-Monteiro method for general semidefinite programs. Optimiza- fion Letters, pages 1-11, 2021.
[20] Andrew R Conn, Nicholas IM Gould, and Ph L Toint. Trust region methods, volume 1 of MOS-SIAM Series Optim. SIAM, 2000.
[21] Frank E Curtis, Daniel P Robinson, and Mohammadreza Samadi. Complexity analysis of trust funnel algorithm for equality constrained optimization. SIAM J. Optim., 1832):553--156, 2018.
[22] Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: unified geometric analysis. Proc. Ini. Conf. Mach. Learn., pages 1233-1242, 2017.
[23]
Alfred Gray. Tubes, volume 221. Birkhäuser, 2012.
[24] Steven G. Johnson. The NLopt nonlinear-optimzzan package. Available at httt:://ggtthu
com/stevent htmm//teeennj/nooppp 2019.
[25] Michel Journée, Francis Bach, P-A Absil, and Rodolphe Sepulchre. Low-rank optimization the cone of positive semidefinite matrices. SIAM J. Optim., 20(5):237--2351, 2010.
[26] Qiuwei Li and Gongguo Tang. The nonconvex geometry of low-rank matrix optimizations with general objective functions. In IEEE Global Conf. Signal Inf. Process., pages 1235-1239, 2017.
[27] Martin Lotz. On the volume of tubular neighborhoods of real algebraic varieties. Proc. Am. Math. Soc., 143(5):1875-188))))) 2015.
[28] Song Mei, Theodor Misiakiewicz, Andrea Montanari, and Roberto Imbuzeiro Oliveira. Solving SDPs for synchronization and maxcut problems via the Grothendieck inequality. In Proc. Conf.
Learn. Theory, pages 1476-1515, 2017.
[29] Gábor Pataki. On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper: Res., 23(2):339-358; 1998.
[30] Thomas Pumir, Samy Jelassi, and Nicolas Boumal. Smoothed analysis of the low-rank approach for smooth semidefinite programs. In Ady. Neural Inf. Process. Syst., pages 2287-2296, 2018.
[31] Mehmet Fatih Sahin, Armin Eftekhari, Ahmet Alacaoglu, Fabian Latorre, and Volkan Cevher. An inexact augmented Lagrangian framework for nonconvex optimization with nonlinear constraints. Proc. Neural Inf. Process. Syst., 32:13965-13977, 2019.
[32] Daniel A Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. JACM, 513333855-463 2004.
[33] Jos F Sturm. Error bounds for linear matrix inequalities. SIAM J. Optim., 10(4):1228-1248
2000.
[34] Irene Waldspurger and Alden Waters. Rank optimality for the Burer-Monteiro factorization. SIAM Journal on Optimization, 30(3):2577-2622, 2020.

---

[35] Richard Zhang, Cédric Josz, Somayeh Sojoudi, and Javad Lavaei. How much restricted isometry
needed in nonconvex matrix recovery? In Adv. Neural Inf. Process. Syst., pages 3586-5597, 2018.
12

---

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] In the discussion section.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work is theoretical, providing polynomial time guarantees for well established methodology.
We do not see any negative societal impacts.
(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 of assumptions of all theoretical results? [Yes] All theorems have full assumptions. Explicit complexity estimates for Theorems 1 and 2 are given in the Appendix.
(b) Did you include complete proof' of theoretical results? [Yes] Some of the proofs are in the Appendix.
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 as URL)? [Yes]] In supplementary material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(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]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [No]
We do develop any new assets.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We use random data for the experiments. (e) Did you discuss whether the data you 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, if 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 participant compensation? [N/A]
13


Reviews:
[{"review_id": "ipEb8v3Fcde", "reviewer": "Reviewer_Vu42", "summary": "This paper studies optimization of a general class of SDPs having a linear objective and general linear constraints, using the nonconvex Burer-Monteiro method. It is known that for the BM formulation in dimension n x p, if the rank p and the number of constraints m satisfy the Barvinok-Pataki bound p(p+1)/2 > m, then for generic cost matrices the BM optimization has no spurious second-order critical points, and its global minimum also minimizes the original SDP. The main result of this paper is a more quantitative statement on polynomial-time convergence of optimization algorithms in a smoothed analysis framework, showing that if the cost and constraint matrices are uniformly distributed over balls of radius sigma, and if p(p+1)/2 > (1+eta) m for any fixed constant eta > 0, then an optimization algorithm for the BM problem succeeds in finding an approximate minimizer of the SDP in poly(n, sigma^{-1}) time.\n\nThis is shown by characterizing the set of cost matrices for which the BM problem has a near second-order-critical point that is not near-optimal for the SDP, and showing that this set belongs to a thin tube around the measure-zero variety that was previously identified as potentially leading to spurious local optimizers of the BM objective. The volume of this tube is bounded using generic results from algebraic geometry, leading to a statement that the smoothed cost matrix w.h.p. does not admit such a spurious near-critical-point. On this high-probability event, the author(s) show that a generic optimization algorithm can compute a near second-order-critical point in polynomial time, which must then be near-optimal. The algorithm requires a p.s.d. initialization that nearly satisfies the equality constraints, which in general may be difficult to obtain. Thus the author(s) also analyze the optimization of a second unconstrained least-squares SDP using the BM approach, which may be used to obtain such an initialization. This second analysis smooths instead over the constraint matrices, and uses a similar algebraic-geometric proof technique.", "questions": "(1) The statements of Theorems 1 and 2 feel a bit too informal and imprecise. It might be clearer to either make them more precise, or to explicitly qualify them as informal versions and provide references to their more formal statements in the supplement.\n\n(2) In the end-to-end guarantee, SDP_{ls} needs to be solved to near-optimality such that Y falls into the set M_beta where the LICQ bound holds, but (unless I missed it) the paper doesn't seem to quantify how small beta needs to be. Is it possible to make a statement about this---e.g. can beta^{-1} be shown to be poly(n, sigma^{-1}), so that it indeed suffices to run the optimization of SDP_{ls} for polynomial time?\n\nMore minor clarifications:\n\nDo the authors mean to write the second equality in Proposition 1? I don't see why this is an equality, and also it doesn't seem to be used in the subsequent proof.\n\ndisplay after l582, the second = should also be >=\n\ndisplay after l660, what are eps_0', eps_1', and eps_2' here?", "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 the paper makes a nice contribution to the literature. The main results are perhaps not too surprising, but they do seem to take some work and insight to obtain, especially down to the sharp Barvinok-Pataki threshold. Defining the right notions of \"near-criticality\" for these SDPs in a way that connects both to the volume-of-tubes arguments being used and to rigorous polynomial-time guarantees for optimization algorithms seems a bit subtle, and for example required the development and analysis of a new variant of a generic second-order optimizer with equality constraints (Theorem 4). The proofs are clean, the paper resolves a very natural question, and I think it's above the bar for NeurIPS.", "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": "WeLGejCRT6I", "reviewer": "Reviewer_1Yjq", "summary": "This work studies the complexity of the Burer-Monteiro method for solving semidefinite programs (SDP). They show that in the smoothed analysis setting (initiated by the seminal work of Spielman and Teng), under some assumptions (certain parameter regimes, compactness, etc), the algorithm terminate in polynomial time. In more details, the Burer-Monteiro method is a nonconvex practical method for solving SDPs, that is useful in applications. For SDP, it can be thought of as trying to directly compute the Cholesky decomposition X = YY^T of the desired PSD matrix variable X. The Barvinok-Pataki bound gives a bound on the dimensions of Y (can be thought of as the rank) above which this approach should work. Prior work has considered various settings and studied when optimization methods based on this approach will succeed and not get stuck on local optima. Also, the smoothed analysis setting has been considered before (although with stronger bounds on the rank) and termination guarantees were obtained. Other works have obtained polynomial runtime guarantees, under various assumptions such as the restricted isometry property. In this work, they obtain polynomial time guarantees for the B-M method under various analytic assumptions and in the smoothed-analysis setting, getting almost close to the Barvinok-Pataki bound.\n\nThe full method analyzed here has two stages, first to get a feasible point and then use it as initialization to get an optimal point. In the first stage, under random perturbations on the constraint matrices and other analytic assumptions, 2nd-order methods are shown to terminate in polynomial time (theorem 2). In the second stage, under random perturbations to the cost-matrix and various analytic assumptions, it's shown that 2nd-order methods terminate in polynomial time (theorem 1). Together, this shows polynomial complexity of the B-M method in the smoothed analysis setting, with explicit bounds derived in Appendix C. Both these assumptions crucially assume that the rank is above the Barvinok-Pataki bound. The proofs contain a few parts, including a robust method (modified from prior works) to compute critical points, and arguing that spurious critical points do not exist in the smoothed analysis setting when the random permutation is uniform over a ball. For the latter, the analysis involves integrals over tubes, which has been estimated in prior works. Finally, simple experiments were conducted showing how the B-M method performs around the Barvinok-Pataki bound. And in cases when the algorithm failed, further experiments show random perturbations help, giving support to the theory developed here.", "questions": "Some questions were raised above. \n- How important is it that the perturbations are uniform? What happens if some other perturbation distribution is used?\n- Correctness of algorithms are measured based on criticality conditions (L301). It should be clarified why this is reasonable\n- In L584, the sentence seems incomplete", "limitations": "Limitations of the theoretical results are implicit in the assumptions made. Negative societal aspects are not raised because since this is primarily a theoretical paper.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis is a very well-written and interesting work that basically offers good evidence why the Burer-Monteiro method works well. Related work is cited well and proper acknowledgement is given where necessary (e.g. L481, L511). To the best of my knowledge, this work is the first to obtain fully polynomial runtime guarantees close to the Barvinok-Pataki bound. Like the authors clarified, other works gloss over certain details such as initialization. The main technical tool is utilizing known bounds on integrals over tubes, while prior works have used simple linear algebra or random matrices. This technical idea is simple but seems new in this setting.\n\nWeaknesses:\n\nThe main limitation is that the experiments conducted in this work are not very convincing but this is offset by the fact that the primary contribution of this work is theoretical. In other words, the experiments ofer some evidence to support the theory but are not necessarily very exhaustive. For example, the SDPs are generated randomly satisfying the feasibility of a chosen point. Is it possible that this randomness implicitly helps the B-M 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": {}}, {"review_id": "W_QZIJSShII", "reviewer": "Reviewer_EwVj", "summary": "**Background for the paper** \n\nConsider a general semidefinite program, \n\\begin{align*}\n\\min_{X \\in \\mathcal{C}}C\\bullet X, \n\\end{align*} where $\\mathcal{C} = {X\\succeq 0, \\mathcal{A}(X) - b \\in 0^{m_1} \\times \\mathbb{R}_+^{m_2}}$. \n\nIn this summary, we shall refer to this problem as (SDP). The linear operator\n$\\mathcal{A}(X):\\mathbb{R}^{n\\times n}\\rightarrow\\mathbb{R}^{m}$ (where $m = m_1 + m_2$ is the total number of linear constraints) has as its $i$'th element,\n$A_{i}\\bullet X.$ 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*} \n\nThe 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 a solution to (BM) also gives one for (SDP). This follows from the celebrated result of Barvinok and Pataki (independently obtained) that there\nexists a rank-$\\sqrt{m}$ solution to (SDP). \n\n**What problem this paper studies (and solves)** \n\nThe tradeoff to the above-mentioned memory saving, though, is that (BM) is a non-convex\nproblem. Therefore, standard convex optimization algorithms do not give any provable theoretical guarantees for obtaining a global minimum of (BM). This is at odds with the tremendous empirical success that (BM) has found in real-world SDPs, and much effort has been expended on explaining this success. \n\nThis paper **gives the first polynomial\ntime guarantee (in the smoothed analysis setting)  that solving (BM) also solves (SDP)**. Here, by \"solving (BM)\", we mean finding a second-order critical point. \n\nPrevious works include the following. Boumal, Voroninski, and Bandeira\nproved that *asymptotically*, (BM) has no spurious 2-critical points under certain technical\nassumptions on the problem and when $\\tau(p)\\geq m.$ However, practical\noptimization methods do not attain exact 2-criticality. Pumir, Jelassi,\nand Boumal gave guarantees with approximate criticality, with worse\nbounds on $\\tau(p)$ than guaranteed by Barvinok-Pataki. Finally, there's the work of Bhojanapalli, Boumal, Jain, Netrapalli, that provides similar guarantees for the penalized (SDP). \n\nThis paper's specific contribution is to **provide a polynomial-time guarantee that solving (BM) (under the Barvinok-Pataki limit) provides a solution to (SDP)**. ", "questions": "1. My main question to the authors is to please clarify how the paper compares against the result of Bhojanapalli, Boumal, Jain, and Netrapalli mentioned in the paper. Thank you. ", "limitations": "N/A ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**ORIGINALITY** \n\nI believe this paper scores highly on originality. At the heart of their result are the following two sub-results. \n\n1. Theorem 4, which gives a polynomial-time bound on computing 2-AFAC points. The algorithm this theorem is based on first finds an approximately feasible point, then iteratively minimizes a Lagrangian-style function and updates its guess of the minimum. \n2. Theorem 5, which proves that a 2-AFAC point for (BM) is approximately optimal for (SDP). To do so, the paper characterizes the set of spurious AFAC points (i.e., the set of symmetric $C$ such that the tuple $(Y, \\lambda)$ is a spurious AFAC pair) geometrically. A characterization of the simpler set of EFAC points may be done via simply the KKT conditions and simple arguments about appropriate subspaces. However, extending this to AFAC points is highly non-trivial and requires technical machinery such as computing the volume of tubular neighbourhoods around certain varieties. \n\n**QUALITY**\n\nI think, while the contributions are significant, the paper can improve its quality of related literature review. Given that a lot of the work done on this problem involves subtle differences of definition of criticality, I think that a critical piece of content missing from this paper's current version is a detailed comparison against some other (already published) works. \n\nFor example, I think the paper must clearly explain why the work of Bhojanapalli, Boumal, Jain, and Netrapalli doesn't already give the stated result (albeit using a different technique; I agree that this paper's technique is novel). In particular, maybe the paper should elaborate on lines 99-102 a bit more: how is solving the penalized version that different from solving the paper's version? I'll be happy to increase my score on this aspect (and, thus, the overall score) if this were explained well. (I agree that BBJN may not have explicitly provided a final runtime but it's perhaps still possible to trivially deduce it from there; so I think it's important to understand why this isn't the case). \n\n**CLARITY**\n\nThe paper is generally quite clearly written and well motivated. \n\n**SIGNIFICANCE**\n\nThe work is of great significance. SDPs are useful in a plethora of fields, and (BM) is a standard technique used to solve them in practice. A theoretical understanding of *why* (BM) works despite the inherent non-convexity could not only inspire faster algorithms for SDPs, but also provide a deeper understanding of non-convex algorithms in general. \n\n\n\n\n", "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": "4dyPREVxTvY", "reviewer": "Reviewer_yGpw", "summary": "The authors propose the Burer Monteiro method to solve an SDP problem in polynomial time up to any degree of accuracy. In the Burer Monteiro method, the idea is to write a symmetric matrix as $YY^{T}$ which then leads to a non-convex program. The primary technique is by slight perturbation of the cost matrix and the constraints so that they avoid a measure zero \"bad set\". The authors show that under certain assumptions, spurious approximately critical points can be avoided by using sophisticated techniques from real algebraic geometry.", "questions": "1) What is the main advantage that is obtained by writing the SDP in form of BM? Also, how is the BM_{ls} problem solved in order to get a feasible solution Y? It would be good to write down the exact optimization algorithms for solving BM and BM_{ls}. \n\n2) Why is it necessary to go through this route? Can the same optimization techniques for solving BM_{ls} and then BM be used to solve SDP_{ls} and then SDP directly?", "limitations": "There are no apparent limitations", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written. Unfortunately, I am not very well-versed in this area to point out weaknesses.", "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