General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
Authors: Haixiang Zhang
Yingjie Bi
Javad Lavaei
Venue: NeurIPS 2021 Poster (2021)
Keywords: Low-rank matrix optimization
global convergence
non-convex optimization
geometric analysis

Abstract: This paper considers the global geometry of general low-rank minimization problems via the Burer-Monterio factorization approach. For the rank-$1$ case, we prove that there is no spurious second-order critical point for both symmetric and asymmetric problems if the rank-$2$ RIP constant $\delta$ is less than $1/2$. Combining with a counterexample with $\delta=1/2$, we show that the derived bound is the sharpest possible. For the arbitrary rank-$r$ case, the same property is established when the rank-$2r$ RIP constant $\delta$ is at most $1/3$. We design a counterexample to show that the non-existence of spurious second-order critical points may not hold if $\delta$ is at least $1/2$. In addition, for any problem with $\delta$ between $1/3$ and $1/2$, we prove that all second-order critical points have a positive correlation to the ground truth. Finally, the strict saddle property, which can lead to the polynomial-time global convergence of various algorithms, is established for both the symmetric and asymmetric problems when the rank-$2r$ RIP constant $\delta$ is less than $1/3$. The results of this paper significantly extend several existing bounds in the literature. 

General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
Haixiang Zhang
Yingjie Bi Department of IEOR University of California, Berkeley
Department of Mathematics University of California, Berkeley
Berkeley, CA 94704 maiixiang.zhangBeekkkle edu
Berkeley, CA 94704 yingjäebißberkel.. edu
Javad Lavaei
Department of IEOR
University of California, Berkeley
Berkeley, CA 94704 eevaee@berkeeey.. edu
Abstract
This paper considers the global geometry general low-rank minimization prob- lems via the Burer-Monteiro factorization approach. For the rank-1 case, we prove that there is no spurious second-order critical point for both symmetric and asym- metric problems if the rank-2 RIP constant ō less than 1/2. Combining with a counterexample with = 1/2, we show that the derived bound is the sharpest possible. For the arbitrary rank-r case, the same property is established when the rank-2r RIP constant ó is at most 1/3. We design counterexample to show that the non-existence of spurious second-order critical points may not hold if 5 is at least 1/2. In addition, for any problem with 5 between 1/3 and 1/2, we prove that all second-orde critical points have a positive correlation to the ground truth. Finally, the strict saddle property, which can lead to the polynomial-time global convergence of various algorithms, is established for both the symmetric and asymmetric problems when the rank-2r RIP constant is less than 1/3. The results of this paper significantly extend several existing bounds in the literature.
Introduction
Given the natural numbers n, m and r, consider the low-rank matrix optimization problems
min MERuxa
(M) s.t. rank(M) Sr, MT = M, M =
and
min Ja(M) s.1. rank(M) Sr, MeRexm
where the functions f.(-) and f-) are twice continuously differentiable. Problems (1)-(2) are referred to the symmetric and the asymmetric problems, respectively. In addition, call these problems linear if the objective function is induced by a linear measurement operator, i.e.,
f(M) 1 (IA((M) bll?
for some vector b E I&P and linear operator A mapping each matrix M to vector in RP, where fMM) denotes either fa() or fa (M). Those problems not fitting into the above model are called nonlinear. One common example with non-linearity is the one-bit matrix sensing problem; please see Zhu et al. (2018); Li et al. (2019); Zhu et al. (2021) for more concrete discussions. Low-rank
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

optimization problems arise in a wide range of applications, e.g.. matrix completion (Candès & Recht, 2009: Recht et al., 2010). phase synchronization (Singer, 2011; Boumal, 2016). and phase retrieval (Shechtman et al., 2015); see Chen & Chi (2018); Chi et al. (2019) for an overview of the topic. To overcome the non-convex rank constraint, one may resort to convex relaxations. The approach of replacing the rank constraint with nuclear norm regularization is proven to provide the optimal sample complexity (Candès & Recht, 2009; Recht et al.. 2010; Candès & Tao, 2010). However, solving the convexified problems involves computing a Singular Value Decomposition (SVD) in each iteration and results in heavy computational burdens; see the numerical comparison in Zheng & Lafferty (2015). Along with the issue of large space complexities, the convexification approach is impractical for large-scale problems. Therefore, it is important to design efficient alternative methods with similar theoretical guarantees. Another line of works generalizes techniques from Orthogonal Matching Pursuit (OMP) to the low-rank matrix problem (Shalev-Shward et al., 2011; Axiotis & Sviridenko, 2020), which also require implementing SVD for times in their algorithms.
1.1 Burer-Monteiro factorization and basic properties
Instead of directly solving convex relaxations of problems (1)-(2), we consider a computationally efficient approach, namely the Burer-Monteiro factorization (Burer & Monteiro, 2003). The factor- ization approach is based on the observation that any matrix M E R= with rank at most r can be written in the form of UVT, where U E Raxr and V E Rmxr, Then, the asymmetric problem (2) is equivalent to
min UER VeRmxr
ha (U,
(3)
where (U, fa(VVT)) Similarly, the symmetric problem (I) equivalent to
min hU),
(4)
where h2(U) (.) The Burer-Monteiro factorization provides a natural parameterization of the low-rank structure of the unknown solution, and reformulates problems (1)-(2) as unconstrained optimization problems. In addition, the number of variables reduces from (n²²) or ((m)) to as low highly
as (rn) or Or((n + m)) when r min(n,m) m). However, the reformulated problems non-convex, and NP-haard to solve in general. On the other hand, these problems share a specific non-convex structure, which makes possible utilize the structure and design efficient algorithms to find a global optimum under some conditions. In addition to the special structure, a regularity condition, named the Restricted Isometry Property, can be used to guarantee the convergence of common iterative algorithms. We state the following two definitions only in the context of the symmetric problem since the corresponding definitions for the asymmetrie problem are similar.
Definition (Recht al. (2010); Zhu et al. (2018)). Given natural numbers and t,, the function fs(+) said to satisfy the Restricted Isometry Property (RIP) of rank (2r, 21) for a constant E [0, 1), denoted as 5-RIP 2r, if
(1 K) < [ (MM) (K $ (1+ 5)
holds for all matrices M, K E Rax. such that rank(M) < 2r, rank((( (V (:-) is the curvature of the Hessian at point M.
< 2t, where
The RIP condition appears in a variety of applications of the low-rank matrix optimization problem. For instance, in the case of linear measurements with Gaussian model, Candès & Recht (2009) showed that O (nr (er/62) samples are enough to ensure the 6-RIP property with high probability. Please see the survey paper by Chi et al. (2019) for more examples. In certain applications, even the RIP condition cannot be established over the whole low-rank manifold, we are able to establish similar strongly convex and smooth conditions on part of the manifold. If the iteration points of algorithms are constrained to or regularized (either explicitly or implicitly) towards those benign regions, the proof techniques in this work may still be applicable. Examples include the phase retrieval problem (Ma et al., 2018) and the matrix completion problem (Chen et al., 2020). However, the analysis of the case when the strong convexity does not hold is usually application-specifc and cannot be generalized to general low-rank problems. Moreover, the RIP assumption is standard in the literature of general low-rank matrix optimization problem. Furthermore, if we drop the strong convexity assumption, are unable to achieve linear convergence in general (Bhojanapalli et al., 2016a). The

---

work by Zhang et al. (2019) shows that the existence of RIP is enough to obtain guarantees on the local landscape of the problem and the size of this local region depends on the RIP constant that can be anything between 0 and I (however, the provided bounds on the RIP constant are not sharp). Although we aimed to obtain sharp bounds on the RIP constant for global landscape of the problem in this paper, we believe that our analysis can be adopted to obtain sharp RIP bounds for local regions. We leave the precise derivation to a future work since it needs a number of lemma and we have space restrictions. We note that the RIP property is equivalent to the restricted strongly convex and smooth property defined in Wang et al. (2017); Park et al. (2018); Zhu et al. (2021) with the condition number (1 + 6) - 6). Intuitively, the RIP property implies that the Hessian matrix is close to the identity tensor when the perturbation is restricted to be low-rank. This intuition naturally leads to the following definition.
Definition 2 (Bi & Lavaei (2021)). Given a natural number r, the function fa(.) is said to satisfy the Bounded Difference Property (BDP) of rank 2r for constant A 2 O, denoted as k- 2-. if
[a(M f((M) (K,L) S ||||||||||||
holds for all matrices M, M", K, T E Rax= such that rank rank(M), rank( rank(K) (K), rank(L.) S 2r.
has been proven in Bi Lavaei (2021, Theorem 1) that those functions satisfying the E-RIPrr.2.
property also satisfy the 48-BDP2, property. With the RIP property, there are basically two categories of algorithms that can solve the factorized problem in polynomial time. Algorithms in the first category require careful initialization so that the initial point is already in small neighbourhood of a global optimum, and a certain local regularity condition in the neighbourhood ensures that local search algorithms will converge linearly to a global optimum; see Tu et al. (2016); Bhojanapalli et al. (2016a); Park et al. (2018) for a detailed discussion. The other class of algorithms is able to converge globally from a random initialization. The convergence of these algorithms is usually established via the geometric analysis of the landscape of the objective function. One of the important geometric properties is the strict saddle property (Sun al., 2018), which combined with the smoothness properties can guarantee the global polynomial-time convergence for various saddle- escaping algorithms (Jin et al., 2017, 2018; Sun al., 2018; Huang & Becker, 2019). For the linear case, Ge et al. (2016, 2017) proved the strict saddle property for both problems (3)-(4) when the RIP constant is sufficiently small. More recently, Zhu et al. (2021) extended the results the nonlinear asymmetric case. Moreover, a weaker geometric property, namely the non-existence of spurious (non-g global) second-order critical points, has been established for both problems when the RIP constant is small (Li et al., 2019; Ha et al., 2020). We note that second-order critical points are points that satisfy the first-order and the second-ordes necessary optimality conditions, and thus the result of the non- non-existence of second-order critical points implies the non- non-existence of spurious local minima. Under certain regularity conditions, this weaker property also able to guarantee the global convergence from a random initialization without an explicit convergence rate (Lee et al., 2016; Panageas& & Piliouras, 2016). Please refer to Table for a summary of the state-of-the-ar results.
Most of the aforementioned papers are based on the following assumption on the low-rank critical points of the functions f-)) and f-):):
Assumption 1. The function (-) has a first-order critical point M such that
S r.
Similarly, the function f-)- has a first-order critical point M; that is symmetric, positive semi- definite and of rank at most r.
This assumption is inspired by the noiseless matrix sensing problem in the linear case for which the non-negative objective function becomes zero (the lowest value possible) at the true solution. This is natural property of the matrix sensing problem for nonlinear measurement models as well. Under the above assumption and the RIP property, Zhu et al. (2018) proved that M and M are the unique global minima of problems (1)-(2).
Theorem (Zhu et al. (2018)). !f the functions fa(:) and fa(-) satisfy the 5-RIP 2r.2r property, then the critical points Mq and M; are the unique global minima of problems (1)-(2).
Given a solution (U*, V*) to problem (3), we observe that (U*P.V*P-T) is also a solution for any invertible P prxt_ This redundancy may induce an extreme non-convexity on the landscape of the objective function. To reduce this redundancy, Tu et al. (2016) considered the regularized problem
min UEBEXT. Ve
P(U V),
(5)
3

---

Table Comparison of the state-of-the art results and our results. Here d2r:2r and K are the 2r.22 and 2D constants of (-) or fa(:,, respectively. Constant a a(Ma)) E (0, 1) only depends on M
2r:20
No Spurious Second-order Critical Pts.
Strict Saddle Property
Problem Setups
Existing
Ours
Existing
Ours
ò2.2 < Zhang al., 2019)
Rank-1
Linear
82 <
Sym.
62.2 < 4+0(K)
2-0(s)
Nonlinear
82, <
(Bi & Lavaci, 2021)
Rank-1 Asym.
Linear & Nonlinear
82,2
82 (Ge al., 2016)
82 10
Rank-r Sym.
Linear
82 S
(Ge et al., 2017)
62n,2 <
82 < (Li et al., 2019)
Nonlinear
82r,2r
82
82,,2r 3
82r,2r 20
Rank-r Asym.
Linear
(Ha al., 2020)
62 $
(Ge et al., 2017)
62n,2 <
82r.2r < 1
82r,4r a(M{)
Nonlinear
82r,2r S
82 <
(Ha al., 2020)
(Zhu et al., 2021)
where
: - /
4 v(U,V)
with constant a > and the regularization term
V) -
The regularization term is introduced to balance the magnitudes of U and V Zhu et al. (2018) showed that the regularization term does not introduce bias and thus problem (5) is equivalent the original problem (2) in the sense that any first-order critical point (U, V) of problem (2) corresponds
first-order critical point of problem (5) with balanced energy, i.e. U =VVV.
Theorem 2 (Zhu al. (2018)). Any first-order critical point (U*, V*) of problem (5) satisfies (U*)TU* = (V*)TV** Moreover, problems (2) and (5) are equivalent.
Detailed optimality conditions for problems (1)-(5) are provided in the appendix.
1.2 Contributions
In this work, we analyze the geometric properties of problems (4)-(5). Novel analysis methods are developed to obtain less conservative conditions for guaranteeing benign landscapes for both problems. We note that, unlike the linear measurements case, the RIP constant of nonlinear problems may not concentrate to 0 as the number of samples increases. Therefore, sharper RIP bound leads to theoretical guarantees that hold under less stringent statistical requirements. In addition, even if the RIP constant concentrates to 0 when more samples are included, there may only be limited number of samples available, either due to the constraints of specific applications or to the great expense of taking more samples. Hence, obtaining sharper RIP bound is essential for many applications. We summarize our results in Table I. More concretely, the contributions of this paper are three-folds.
First, we derive necessary conditions and sufficient conditions for the existence of spurious second- order critical points for both symmetric and asymmetric problems. Using our necessary conditions, we show that the 6-RIP property with 8 < 1/3 is enough to guarantee the non-existence of such points. This result provides a marginal improvement to the previous work (Ha et al., 2020), which developed the sufficient condition d < 1/3 for asymmetric problems, and is a major improvement over Ge al. (2016) and Li et al. (2019), which requires 6 < 1/5 for symmetric problems. With this non-existence property and under some common regularity conditions, Lee et al. (2016); Panageas &

---

Piliouras (2016) showed that the vanilla gradient descent method with small enough step size and a random initialization almost surely converges a global minimum. We note that the convergence rate was not studied and could theoretically be exponential in the worst case. In addition, by studying our necessary conditions, we show that every second-order critical point has a positive correlation the global minimum when ò E (1/3, /2). When 8 1/2, a counterexample with spurious second-order critical points is given by utilizing the sufficient conditions. We note that the sufficient conditions can greatly simplify the construction of counterexamples.
Second, we separately study the rank-1 case to further strengthen the bounds. In particular, we utilize the necessary conditions to prove that the 6- 8-RIP2,2 property with 6 < 1/2 is enough for the non-existence of spurious second-order critical points. Combining with a counterexample in the ó = 1/2 case, we conclude that the bound ò < 1/2 is the sharpest bound for the rank-1 case. Our results significantly extend the bounds in Zhang et al. (2019) derived for the linear symmetric case to the linear asymmetric case and the general nonlinear case. It also improves the bound in Bi & Lavaei (2021) by dropping the BDP constant.
Third, we prove that in the exact parametrization case, problems (4)-(5) both satisfy the strict saddle property (Sun et al., 2018) when the 8-RIP 2r.2r property is satisfied with < 1/3. This result greatly improves the bounds in Ge et al. (2017); Zhu et al. (2021) and extends the result in Ha al. (2020) to approximate second-order critical points. With the strict saddle property and certain smoothness properties, wide range of algorithms guarantee a global polynomial-tnn time convergence with a random initialization; see Jin et al. (2017, 2018); Sun al. (2018); Huang Becker (2019). Due to the special non-convex structure of our problems and the RIP property, it is possible to prove the boundedness of the trajectory of the perturbed gradient descent method using a similar method as in Jin et al. (2017). Since the smoothness properties are satisfied over a bounded region, combined with the strict saddle property, it follows that the perturbed gradient descent method (Jin et al., 2017) achieves a polynomial-time global convergence when ō < 1/3.
1.3 Notation and organization
The operator 2-norm and the Frobenius norm of matrix M denoted |M and [M respectively. The trace of matrix M is denoted as tr( (M). The inner product between two matrices is defined as (M, N)
TM N). For any matrix M R=xm denote its singular values by an (M) 2 ... 2 (M), where == min (n, (n, m). For any symmetric matrix M E R we denote its eigenvalues by X1 (M) N 2 (M). The minimal eigenvalue is denoted as Amin (-). For any matrix U, we use Py to denote the orthogonal projection onto the column space of U. For any matrices A, B E Raxxm we use A @ B denote the fourth-order tensor whose ji k; E) element is Ar, Br.e- The identity tensor is denoted as I. The notation M > 0 means that the matrix M is symmetric and positive semi-definite The sub-matth matrix Resj,kst consists of the i-th the j-th rows and the k-th the ê-th columns of matrix R. The action of the Hessian (MM) on any two matrices K and L is given by (MM)) L) = E.j.,, (V2 [MM)).,,... Lx,E-
In Section 2. the Singular Value Projection algorithm is analyzed as an enlightening example for our main results. Sections 3 and 4 are devoted to the non-existence of spurious second-order critical points and the strict saddle property of the low-rank optimization problem in both symmetric and asymmetric cases, respectively.
2 Motivating Example: Singular Value Projection Algorithm
Before providing theoretical results for problems (4)-(5), we first consider the Singular Value Pro- jection Method (SVP) algorithm (Algorithm 1) as a motivating example, which is proposed in Jain et al. (2010). The SVP algorithm is basically the projected gradient method of the original low-rank problems (1)-(2 via the truncated SVD. For the asymmetric problem (2), the low-rank manifold is
Masym
{M E R=xm| rank(M) S r)
and the projection is given by only keeping components corresponding to the r largest singular values. For the symmetric problem (1), the low-rank manifold is
Maym := {M _ rank(M) Sr, MT M, M =)
We assume without loss of generality that the gradient VS(-) is symmetric; see Appendix for discussion. The projection is given by only keeping components corresponding to the r largest
5

---

Algorithm Singular Value Projection (SVP) Algorithm
Input: Low-rank manifold M, initial point Mo. number of iterations T, step size y,, objective function f(-).
Output: Low-rank solution Mr.
for 0, .......... T 1 do
2: Update M4+1 f Mr 7/V (M)).
3: Set M to be the projection of Mc+1 onto M via truncated SVD.
4: end for
5:
return Mr.
cigenvalues and dropping all components with negative eigenvalues. Since both low-rank manifolds are non-convex, the projection solution may not be unique and we choose an arbitrary solution when it is not unique. We note that the above projections are orthogonal in the sense that
|| M
min KEM
||-- -M]]F:
where M+ is the projection of a matrix M. Henceforth, M stands for Maym or Masym, which should be clear from the context. Although each truncated SVD operation can be computed within O(nmr) operations, the constant hidden in the O(.) notation is considerably larger than 1. Thus, the truncated SVD operation is significantly slower than matrix multiplication, which makes the SVP algorithm impractical for large-scale problems. However, the analysis of the SVP algorithm, combining with the equivalence property given in Ha et al. (2020), provides some insights into how to develop proof techniques for problems (4)-(5).
We extend the proof in Jain et al. (2010) and show that Algorithm converges linearly the global minimum under the 8 8-RIP2n22 property with 5 < 1/3.
Theorem 3. If function f.) (resp. fa(-)) satisfies the 6-RIP property with 5 1/3 and the step size is chosen be 1j (1 + 8) -) then Algorithm applied problem (1) (resp. (2)) returns
solution My such that Mr E M and ((M)) - -(M** S e within
f(Ma) f(MM)
.log
logl - -))((25))
iterations, where ==) fa()) (resp. f6) = fa))), M is the global minimum, Mg is the initial point and [-] is the ceiling function.
The proof is almost identical to that in Jain et al. (2010) except that we have replaced the quadratic function with the RIP bounds. However, the result of the proof provides key inequality (13) for the subsequent proofs. We note that the above proof can be applied to other low-rank optimization problems with suitable definition of the orthogonal projection. In Ha al. (2020), it is proved that the unique global minimum is the only fixed point of the SVP algorithm the RIP constant ò is less than 1/3. However, the above paper has not proven the linear convergence (as done in Theorem 3). This difference leads to a strengthened inequality in the following analysis, which further serves as an essential step in proving the strict saddle property. The results in this section provide hint that the landscape may be benign when the RIP constant is smaller than 1/3 and we may be able to establish linear convergence under this condition, which the main topic of the remainder of this paper.
3 No Spurious Second-order Critical Points
In this section, we develop necessary conditions and sufficient conditions for the existence of spurious second-order critical points problems (4)-(5). Besides the non-existence of spurious local minima, the non-existence of spurious second-order critical points also guarantees the global convergence of many first-order algorithms with random initialization under certain regularity conditions (Lee et al., 2016; Panageas & Piliouras, 2016). More precisely, we require the iterates of the algorithm to converge to a single point and objective function to have Lipschitz-continuous gradient. The first condition is satisfied by the gradient descent method applied to a large class of functions known as the Kt.-functions (Attouch al., 2013). For the second condition, many objective functions that appear in applications, e.g., the fg loss function, do not satisfy this condition. However, if the step

---

size is small enough, the special non-convex structure of the Murer-Monteiro decomposition and the RIP property ensure that the trajectory of the gradient descent method stays in a compact set, where the Lipschitz, condition is satisfied due to the second-order continuity of the functions (+).) and (a(+). The proof of this claim similar to Theorem in Jin al. (2017) and is omitted here. Therefore, the non-existence of spurious second-order critical points can ensure the global convergence of the gradient descent method for many applications.
The non-existence of spurious second-order critical points has been proved in Ge et al. (2017); Zhu et al. (2018) for problems with linear and nonlinear measurements, respectively. Recently, Ha et al. (2020) proved a relation between the second-orde -odder critical points of problem (3) or (5) and the fixed points of the SVP algorithm on problem (2). Using this relation, they showed that problems (3) and (5) have no spurious second-org -order critical points when the 6-RIP 2r.2r property is satisfied with 8 < 1/3. In this work, we take a different approach to show that 8 I 1/3 is enough for the general case in both symmetric and asymmetric scenarios, and that ō < 1/2 is enough for the rank-1 1 case. Moreover, we prove that there exists a positive correlation between every second-order critical point and the global minimum when 6 E (1/3, 1/2). We also show that there may exist spurious second-order critical points when 8 = 1/2 for both the symmetric and asymmetric problems, which extends the construction of such examples for the linear symmetric rank-1 problem in Zhang et al. (2018) to general cases. We first give necessary conditions and sufficient conditions for the existence of function that satisfies the 5- 6-RIP2r,22 condition and spurious second-orde critical points below.
Theorem 4. Let Ê == min(m, n. 2r.. For a given E [o, 1), there exists a function fa(-) with the 8-RIP 2r.27 property such that problems (3) and (5) have a spurious second-ordd critical point only if 1 1- 8 < (1 + 2) and there exists a constant a E (1 - 8, (1 + 5)/2). a diagonal matrix E E Rixt, a diagonal matrix A E (((--)x(t-r) and matrices A E R B E RTXT, C. E (t-r-r) D [ ( such that
Cf = and ADT = 0, then there exists a function fa(.) with the 8-RIP property such that problems (3) and (5) have spurious second-order critical point.
(1+ min Σg 2 max Ast Σ 0, A AZ 0. isigr Isist=r
(A,C a [rT(²)) - ABE + |AB 11 + ||AD 1 +1CBB +|CD
(6)
tr((9) S a -20 - 1 11+ 82) (A,CD") (A,CD") #
Remark 1. We note that there may exist simpler forms of the above conditions. For instance, we may solve a via the condition in the second line of (6) and substitute into other conditions. In addition, the requirement that E (1 5, (1 + 8) may also be dropped without affecting the conditions. More specifically, the conditions in (6) are equivalent to
(1+ min Σn 2 max Age, Σ20,A00 (A,CD") #0, Iiisr
isist-r
tr (r(33) < 2 (A.CD") -8) (0((1(2))) -(22))
+ +1IAB* + IAD + +ICDDT1B]
We state Theorem 4 in the current form since it helps with deriving corollaries more directly.
Intuitively, A and Σ correspond to the singular values of the second-order critical point and the gradient at the second-order critical point, respectively. Matrices A, B, C, D correspond to the SVD of the global optimum. The original problem of the non non-existence of spurious second-order critical points can be viewed a property of the of functions satisfying the RIP property, which is convex set in an diinttedi functional space. The conditions in (6) reduce the problem to a dimens-ommlii problem by utilizing the optimality conditions and the RIP property, which provides a basis for solving these conditions numerically. We note that the conditions in the third line of (6) are novel and serve as an important step in developing strong theoretical guarantees. Although the conditions in (6) seem complicated, they lead to strong results on the non-existence of spurious second-order critical points. We provide two corollaries below to illustrate the power the above theorem. The first corollary focuses on the rank-1 case. In this case, can simplify condition
7

---

(6) through suitable relaxations to obtain sharper bound on å that ensures the non-existence of spurious second-order critical points.
Corollary 1. Consider the case = 1, and suppose that the function fa(-) satisfies the 8-RIP
property with ò < 1/2. Then, problems (3) and (5) have no spurious second-order critical points.
The following example shows that the counterexample in Zhang et al. (2019) designed for the symmetric case also works for the asymmetric rank-1 case.
Example 1. We note that Example 12 in Zhang al. (2019) shows that problem (4) may have spurious second-order critical points when = 1/2. In general, a second-order critical point for problem (4) is not second-order critical point for problem (5), since the asymmetric manifold Masym has a larger second-ordet critical cone than the symmetric manifold Maym However, it can be verified that the same example also has spurious second-order critical point the asymmetric case. For completeness, we verify the claim in the appendix.
It follows from Corollary 1 and Example that the bound 1 1/2 is the sharpest bound for the rank-1 asymmetric case. The next corollary provides a marginal improvement to the state-of-the-ar result for the general rank case, which derives the RIP bound 5 < 1/3 (Ha et al., 2020). In addition, we prove that there exists a positive correlation between every second-order critical point and the global minimum when å < 1/2.
Corollary 2. Given an arbitrary v, suppose that the function fa(:) satisfies the 6-RIP property. 8 & 1/3, then both problems (3) and (5) have no spurious second-order critical points. In addition, i E 10),, then every second-order critical point M has positive correlation with the ground truth My. Namely, there exists a universal function C(6) : (0, 1/2) + (0, 1] such that
(M, MM) 2 C(6) M | ||[M
For the general rank-r case, we construct counterexample with spurious second-order critical points when 8 = 1/2.
Example 2. Let n = m 2r. Now, we use the sufficiency part of Theorem 4 to construct a counterexample. We choose
3
3 - A= 0r, C=D==A.
=
E 3 A A:
2
It can be verified that the conditions in (6) are satisfied and CBT AD" = O, which means that there exists a function fa(.) satisfying the 5-RIP2r:2r property for which problems (3) and (5) have spurious second-order critical points. We also give direct construction with linear measurements in the appendix. This example illustrates that Theorem 4 can be used to systematically design instances of the problem with spurious second-order critical points.
Before closing this section, we note that similar conditions can be obtained for the symmetric problem (4). Although there exists a natural transformation of symmetric problems to asymmetric problems (see the appendix), the approach requires the objective function f.).) to have the 8-RIP4 4r,2r property, which provides sub-optimal RIP bounds compared to direct analysis. We give the results of the direct analysis below and omit the proof due to the similarity to the asymmetric case.
Theorem 5. Let := min(n, n, 2r}. For a given
E [o, 1), there exists a function fa(:) with the 2- property such that problem (4) has a spurious second-order critical point only if 1 - < (1 + 6)/2 and there exists a constant a E (1 - 8, (1 + 6)/2), a diagonal matrix E E grxr, a diagonal matrix A E ((((-r)((e-r) and matrices A E Brxr C E (e-r)xr xr such that
(1+8) 8) min En 2 max Ass. Σ 0, 15ist-r
Isisr
(A, (A, =
2(E,
|| + 21AA 11 + |[CC"1|]]
tr(A²) (2a - 11+ (A, CC (A, #0.
If ACT = O, then there exists function f.(-) with the 8-RIP property for which problem (4) has spurious second-order critical point.
Compared to Theorem 4, the diagonal matrix is not enforced to be positive semi-definite. The reason is that the eigenvalue decomposition is used instead of the singular value decomposition in the symmetric case, and therefore some eigenvalues can be negative. Similarly, we can obtain the non-existence and the positive correlation results for the symmetric problem.
8

---

Corollary 3. functio fo(:) satisfies the 8-RIP property. then the following statements hold:
f S 1/3, then there are no spurious second-order critical points;
I < 1/2, then there exists a positive correlation between every second-order critical point and the ground truth:
If 1/2, then there exists counterexample with spurious second-order critical points;
. Ifā < 1/2 and r 1, then there are spurious second-order critical points.
We note that the last statement serves as generalization of the results in Zhang et al. (2019) to the nonlinear measurement case, and improves upon the bound Bi & Lavaei (2021) by dropping the BDP constant.
4
Global Landscape: Strict Saddle Property
Although the non-existence of spurious second-order critical points can ensure the global convergence under certain regularity conditions, it cannot guarantee a fast convergence rate in general. Saddle-point escaping algorithms may become stuck approximate second-order critical points for exponentially long time. To guarantee the global polynomial-tine convergence, the following strict saddle property commonly considered in the literature:
Definition (Sun et al. (2018)). Consider an arbitrary optimization problem min F(x) and let X' denote the set of its global minima. It is said that the problem satisfies the (a., 3, -ttriitt saddle property for a, B,y > 0 if at least one of the following conditions satisfied for every X:
dist X²) S oF;
[V(())] 2 B; Amin
F(+) -7- --7
For the low-rank problems, we choose the distance to be the Frobenius norm in the factorization space. This distance is equivalent to the Frobenius norm in the matrix space in the sense that there exist constants e1 (X*) ) > 0 and e2 (x') > such that
(xx)) IIU - U = |IU0T U' S -2(x")) 1---0-U0 U-
holds for all U X' long |IU U| is small and X is bounded (Tu et al., 2016). A similar relation holds for the asymmetric case.
In Jin et al. (2017), it has been proved that the perturbed gradient descent method can find an approximate second-order critical point in Ö(e iterations with high probability if the Hessian of the objective function is Lipschitz. Namely, the algorithm returns a point x e X' such that
FV & O(c). Amin (V=F(( 2 -((Ve)
in (2) iterations with high probability. If we choose > 0 to be small enough such that O(e) < and -0(v²) > -7, then the strict saddle property ensures that the returned point satisfies (ist S a with high probability. We note that the Lipschitz continuity of the Hessian can be similarly guaranteed by the boundedness of trajectories of the perturbed gradient method, which can be proved similarly as Theorem 8 in Jin et al. (2017). Since the smoothness properties are satisfied over a bounded region, we may apply the perturbed gradient descent method (Jin et al., 2017) to achieve the polynomial-timg global convergence with random initialization.
In this section, we prove that problems (4) and (5) satisfy the strict saddle property with an arbitrary > 0 in the exact parameterization case, i.e., when the global optimum has rank
Assumption 2. The global optimum M or M has rank
has been proved in Zhu et (2021) that the regularized problem (5) satisfies the strict saddle property if the function (-) has the 8-RIP2r.4r property with
(M333//2
8 <
100 Aa
Our results improve upon their bounds by allowing a larger problem-free RIP constant and requiring only the RIP property (note that there are problems with RIP property for which the RIP property does not hold (Bi & Lavaei, 2021)). Our result can also viewed as a robust version the results in Ha et al. (2020).

---

Theorem 6. Suppose that the function fa(:) satisfies the 8-R1P2r.2r property with 5 < 1/3. Given an arbitrary constant a > if y is selected belong the interval [[1 (1-6))3 6)/3, 5). then there exist positive constants
6 c1,,, (M MIM A = A O, (|
such that for every E E1) and E (0, problem (5) satisfies the (ax, B, 7)-strict saddle property with
B : min min ((e/r))/2
jee
We note that the constraint E [(1 - 6)/3. 1 - 5) is not optimal and it can be similarly proved that ja (6, 1 8) also guarantees the strict saddle property. The key step in the proof is show that for every point (U, V) at which the gradient fa (UVV) is small, holds that
(1 -1-(1-- V Vfa("V)) 2 (1+ + + C.
ff (f)(f((vv))
(MM))
where C is constant independent of (U, V). This incquality can be viewed as major extension of the non non-exiieee eeieexistenne of spurious second-order critical points when 8 < 1/3 (Ha et al., 2020), which shows that every spurious second-orde critical point (U, V) satisfies
VV I (1+8)o?(UV").
We emphasize that our proof requires a new framework and not a standard revision of the existing methods, which is the reason why sharper bounds can be established. By replacing fa (M))2l with -mmin fM,(()), the analysis for the asymmetric case can be extended the symmetric case with minor modifications and the same bound follows.
Theorem 7, Suppose that the function fs(:) satisfies the 8-RIP2r,22 property with 5 < 1/3. Given an
arbitrary constant O, there exists a positive constant X1 = (ā, (o, (MG),, [|M] [.) such that for every X E X1], problem (4) satisfies the (a,, 3, 7))-riict saddle property with
8 X 7 == 2X.
The above bound is the first theoretical guarantee of the strict saddle property for the nonlinear symmetric problem.
5
Conclusion
In this work, we analyze the geometric properties of low-rank optimization problems via the non- convex factorization approach. We prove novel necessary conditions and sufficient conditions for the non-existence of spurious second-order critical points in both symmetric and asymmetric cases. We show that these conditions lead to sharper bounds and greatly simplify the construction of counterexamples needed to study the sharpness of the bounds. The developed bounds significantly generalize several of the existing results. In the rank-1 case, the bound is proved to be the sharpest possible. In the general rank case, we show that there exists positive correlation between second- order critical points and the global minimum for problems whose RIP constants higher than the developed bound but lower than the fundamental limit obtained by the counterexamples. Finally, the strict saddle property is proved with weaker requirement the RIP constant for asymmetric problems. The paper develops the first strict saddle property in the literature for nonlinear symmetric problems.
Acknowledgments and Disclosure of Funding
This work was supported by grants from AFOSR, ARO, ONR, NSF and C3.ai Digital Transformation Institute.
References
Hedy Attouch, Jérôme Bolte, and Benar Fux Svaiter. Convergence of descent methods for semi- algebraic and tame problems: proximal algorithms, forwardd splitting, and regularized Gauss-Seidel methods. Mathematical Programming, (7(1):91-129,201 2013.
10

---

Kyriakos Axiotis and Maxim Sviridenko. Sparse convex optimization via adaptively regularized hard thresholding. In International Conference on Machine Learning, pp. 452-462. PMLR, 2020.
Srinadh Bhojanapalli, Anastasios Kyrillidis, and Sujay Sanghavi. Dropping convexity for faster PMLR, 2016a.
semi-definite optimization. In Conference on Learning Theory, pp.
Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro. Global optimality local search for low rank matrix recovery. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 3880-3888, 2016b.
Yingjie Bi and Javad Lavaei. On the absence of spurious local minima in nonlinear low-rank matrix recovery problems. In International Conference on Artificial Intelligence and Statistics, pp. 379-387. PMLR, 2021.
Nicolas Boumal. Nonconvex phase synchronization. SIAM Journal on Optimization, 26(4):2355- 2377, 2016.
Samuel Burer and Renato DC Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, 95(2):329-357 2003.
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun- dations of Computational mathematics, 9(6):117-772, 2009.
Emmanuel Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory, 5665):003322080, 2010.
Chen, Dekai Liu, and Xiaodong Li. Nonconvex rectangular matrix completion via gradient descent without 00 regularization. IEEE Transactions Information Theory, 66(9):5806-5811, 2020,
Yudong Chen and Yuejie Chi. Harnessing structures in big data via guaranteed low-rank matrix estimation: Recent theory and fast algorithms via convex and nonconvex optimization. IEEE Signal Processing Magazine, 35(4):14-31, 2018.
Yuejie Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factorization:
An overview. IEEE Transactions on Signal Processing, 67(20):5239-5265 2019.
Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. Advances in Neural Information Processing Systems, pp. 2082229919999 1-2989, 2016.
Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning, pp. 1233-1242. PMLR, 2017.
Wooseok Ha, Haoyang Liu, and Rina Foygel Barber. An equivalence between critical points for rank constraints versus low-rank factorizations. SIAM Journal on Optimization, 30(4):2927-2955, 2020.
Zhishen Huang and Stephen Becker. Perturbed proximal descent to escape saddle points for non- convex and non-smooth objective functions. In INNS Big Data and Deep Learning conference, pp. 58-77. Springer, 2019.
Prateek Jain, Raghu Meka, and Inderjit Dhillon. Guaranteed rank minimization via singular value projection. In Proceedings of the 23rd International Conference on Neural Information Processing Systems-Voluue Volume 1, pp. 935, 2010.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pp. 1724 1732. PMLR, 2017.
Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference On Learning Theory, pp. 1042-1085. PMLR, 2018.
Jason D Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent only converges minimizers. In Conference learning theory, pp. 1246-1257. PMLR, 2016.

---

Qiuwei Li. Zhihui Zhu, and Gongguo Tang. The non-convex geometry of low-rank matrix optimiza- tion. Information and Inference: Journal of the IMA, 8(1):51-96, 2019.
Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference on Machine Learning, pp. 3345-33545 PMLR, 2018.
Ioannis Panageas and Georgios Piliouras. Gradient descent only converges to minimizers: Non- isolated eritical points and invariant regions. arXiv preprint orXiv:/605.004400 2016.
Dohyung Park, Anastasios Kyrillidis, Constantine Caramanis, and Sujay Sanghavi. Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably. SIAM Journal on Imaging Sciences, 11(4):1165-2244, 2018.
Benjamin Recht, Maryam Fazel, and Pablo Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471-501 2010.
Shai Shalev-Shwartz Alon Gonen, and Ohad Shamir. Large-scale convex minimization with low- rank constraint. In Proceedings of the 28th International Conference on International Conference on Machine Learning, pp. 329-336, 2011.
Yoav Shechtman, Yonina C Eldar, Oren Cohen, Henry Nicholas Chapman, Jianwei Miao, and Mordechai Segev. Phase retrieval with application to optical imaging: a contemporary overview. IEEE signal processing magazine, 12(3):77-109,201 2015.
Amit Singer. Angular synchronization by eigenvectors and semidefinite programming. Applied and computational harmonic analysis,
2011.
Ju Sun, Qing Qu, and John Wright. A geometric analysis of phase retrieval. Foundations of Computational Mathematics, 18(5):1131-119,, 2018.
Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Ben Recht. Low-rank solutions of linear matrix equations via Procrustes flow. In International Conference Machine Learning, pp. 964-973. PMLR, 2016.
Lingxiao Wang, Xiao Zhang, and Quanquan Gu. A unified computational and statistical framework for nonconvex low-rank matrix estimation. In Artificial Intelligence and Statistics, pp. 981-990. PMLR, 2017.
Richard Y Zhang, Cédric Josz, Somayeh Sojoudi, and Javad Lavaei. How much restricted isometry needed in nonconvex matrix recovery? In NeurlPS, 2018.
Richard Y Zhang, Somayeh Sojoudi, and Javad Lavaei. Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery. Journal of Machine Learning Research, 20( 14):1-34, 2019.
Qinqing Zheng and John Lafferty. A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements. In Proceedings of the 28th International Conference on Neural Information Processing Systems- Volume 1, pp. 109-117, 2015.
Zhihui Zhu, Qiuwei Li, Gongguo Tang, and Michael B Wakin. Global optimality in low-rank matrix optimization. IEEE Transactions on Signal Processing, 66( 66(13)3314,3362, 2018
Zhihui Zhu, Qiuwei Li, Gongguo Tang, and Michael Wakin. The global optimization geometry of low-rank matrix optimization. IEFE Transactions on Information Theory, 67(2):1308-1331 2021.
12


Reviews:
[{"review_id": "zZ-a4RW0agc", "reviewer": "Reviewer_mEBV", "summary": "This paper studies low-rank matrix recovery problems, where a loss function is optimized, which satisfies the restricted isometry property. The paper considers a formalization based on matrix factorization, as it is typically studied in non-convex optimization.  The paper is concerned with the question when the landscape of the problem is “nice”, i.e. when are there no spurious second-order saddle points and when does the loss landscape have the strict saddle property.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_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": "The paper improves both in the linear and non-linear upon existing work, both also for symmetric and non symmetric matrices. Moreover, the paper is clearly written and easy to read. Although the result Is “only” of theoretical interest, I feel that this is a strong paper, which merits publication.\n\nI do not see any particular strong weakness, but I only have the following remarks:\n-It might be helpful for the reader if the authors could make precise what they mean by “the problems are equivalent” in Theorem 2\n-In the formulation of Theorem 4 it is required that alpha \\in (1-delta,(1+delta)/2]. Is this a typo?! The interval is the empty set.\n-typo in l. 319 “gradient decent”\n-I think it might be helpful for the reader if the authors could motivate the non-linear formulation by some particular example.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "Not applicable", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "nENB1ftkV0P", "reviewer": "Reviewer_b54e", "summary": "This paper studies low-rank matrix optimization, in particular solving $\\underset{M\\in\\mathbb{R}^{m\\times n}}{\\min} f(M)$ under a rank constraint $\\mathrm{rank}(M) \\leq r$, where $f$ is a convex function. This captures a lot of problems like matrix completion, phase retrieval, etc. \n\nThe authors assume that $f$ is smooth and strongly convex along directions of rank $2r$, where $r$ is the rank of the global minimizer, and establish results in terms of the Restricted Isometry Property (RIP) constant $\\delta_{2r}$ of $f$. The main contribution of the paper is to establish sharper upper and lower bounds on $\\delta_{2r}$, under which every saddle point has a strictly negative eigenvalue, which by known results implies that the function be efficiently optimized using gradient descent. Specifically, the positive results work as long as $\\delta_{2r} \\leq 1/3$ and there are counterexamples when $\\delta_{2r} \\geq `1/2$.\n\nAdditionally, the authors show that their results transfer to the case when the matrix $M$ is constrained to be symmetric PSD, strengthening previous results, and also strengthen the RIP upper bound to $\\delta_{2} \\leq 1/2$ in the case of rank-1 matrices.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_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": "**Originality**\n\nTo the best of my knowledge, the results are original. I find such structural results interesting, as they immediately imply convergence of a large family of gradient descent-based algorithms. That said, the RIP condition seems restrictive, and I wonder if one can achieve similar (but weaker) structural results after dropping the strong convexity assumption.\n\n**Quality**\n\nThe results of the paper look correct to me. I have the following comments/suggestions to make:\n\n* In the introduction, the authors mention convex relaxation approaches as the only alternatives for the problem of low-rank optimization. However, this is ignoring another line of work, which uses a technique similar to Orthogonal Matching Pursuit (OMP) (and variants) but generalized to the low-rank matrix domain. Additionally, some of these algorithms don't require a singular value thresholding of the solution, and also do not require a constant RIP upper bound (with the caveat of relaxing the rank constraint). Such results can be found in the following papers:  \n[1] Shai Shalev-Shwartz, Alon Gonen, Ohad Shamir: Large-Scale Convex Minimization with a Low-Rank Constraint. ICML 2011: 329-336  \n[2] Kyriakos Axiotis, Maxim Sviridenko: Local Search Algorithms for Rank-Constrained Convex Optimization. ICLR 2021\n\n* In Theorem 3, it should be clarified in which sense the proof of Jain et al. (2010) is extended. Apart from the fact that it works for general functions rather than quadratic, is there some other difference in the statement? Also, a high level sentence on how the proof differs would be useful.\n\n* In Corollary 2, what does the fact that the solution is positively correlated with the optimal solution imply? What is the practical significance of this property?\n\n**Clarity**\n\nThe writing in the main body is good and accurate. Unfortunately, the proofs in the appendix are very technical without providing some sort of intuition. I have the following suggestions:\n\n* The authors should add a short explanation on how the proofs work at a technical level. In particular, what are the new technical insights compared to Ha et al. (2020) and Zhu et al. (2021)?\n\n* I couldn't exactly figure out how the regularization term in (5) helps in the analysis. It would be helpful if the authors could include a short (technical) explanation on why it is necessary for their analysis.\n\n* The statements of Theorems 4 and 5 are not clear. Various symbols such as $\\Sigma, \\Lambda$ are defined but are not related to the function $f_a(\\cdot)$. These should be fixed, and also a short description of what each condition means or why it is important would be helpful.\n\n**Significance**\n\nI think that the results are significant in that they are the first structural results that show that gradient descent can _efficiently_ solve a large family of low-rank optimization problems via the Burer-Monterio factorization approach.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A potential limitation is the constant RIP upper bound that is required, which seems like a strong assumption. Also, the strict saddle point results (Section 4) require the additional non-trivial assumption that the global optimizer has low rank. This is not usually the case in practice, because of noise.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "ZVDg2DYGJMo", "reviewer": "Reviewer_ogYY", "summary": "This article considers the problem of minimizing a function $f$ over the set of matrices, either in the symmetric case ($f$ is defined for symmetric semidefinite positive matrices only) or in the asymmetric one ($f$ is defined over the set of all matrices with prescribed dimensions). It is assumed that\n- the global minimizer of $f$ has low-rank (at most $r$) ;\n- the Hessian of $f$, when restricted to matrices with rank at most $2r$, satisfies the restricted isometry property with constant $\\delta$.\n\nThe authors introduce the corresponding \"factorized\" version of $f$ ($U \\to f(UU^T)$ in the symmetric case, $(U,V) \\to f(UV^T)$ in the asymmetric one, possibly with an additional regularizer - here, $U$ and $V$ have r columns) and try to establish conditions on $\\delta$, as tight as possible, which guarantee that the factorized version has no spurious second-order critical point (SSOCP).\n\nThe main results are:\n- a general (more or less) necessary and sufficient condition for the existence of a function with a SSOCP (Theorems 4 and 5);\n- when $r=1$, if $\\delta<1/2$, there is no SSOCP; the constant $1/2$ is tight (Corollary 1; known in the symmetric case, novel in the asymmetric one);\n- for arbitrary $r$, if $\\delta\\leq 1/3$, there is no SSOCP (Corollary 2; minor improvement over Ha et al (2020));\n- for arbitrary $r$, if $1/3<\\delta<1/2$, SSOCP are positively correlated with the ground truth (Corollary 2);\n- if $\\delta<1/3$, $f$ has the strict saddle property (in the symmetric case, or for the regularized version in the asymmetric one) (Theorems 6 and 7).", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_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": "I think this is a good article, notably for the following two reasons:\n1) The link between the RIP constant of a function and the non-existence of SSOCP for its factorized version has raised significant interest in the last years, and this article almost closes the question, by considering the most general setting (non-linear functions, symmetric or asymmetric case) and providing almost tight answers (only Corollary 2 is not tight, because of the gap between $1/3$ and $1/2$). The contribution of this article is therefore susceptible, in my opinion, to be of interest for a relatively wide audience.\n2) From a technical point of view, it seems to me that this article is perfectly correct. (I did not find the time to read the thirty pages of proofs, but still read around half of them, and did not see any possible issue.)\n\nHowever, in my opinion, this article also suffers from the following two drawbacks:\n1) It seems to me that the question of finding the optimal RIP constant which guarantees the non-existence of SSOCP is very theoretical (although I admit it is a natural one). Indeed, in concrete settings, it is in general difficult to determine whether a function satisfies the RIP, and for which constant. The RIP is also not the only property which determines the existence or non-existence of SSOCP: there are functions which do not satisfy the RIP but for which no SSOCP exists. This slightly narrows down the implications of the presented results for concrete applications.\n2) The presentation of the results and proofs does not seem optimal to me, which I think could reduce the impact and \"reusability\" of the article.\n     1) In my opinion, Theorem 4 (which is the first \"main\" theorem) is too complicated to be easily understandable and reapplicable. It seems to me that the authors should try to simplify it into a simpler set of necessary and sufficient conditions. For instance, I think that the following property is equivalent to the one of Theorem 4 (I include a proof at the end of the review):\n$$\\begin{gather*}\n\\mbox{There exists diagonal matrices }\\Sigma, \\Lambda\\mbox{ and matrices }A,B,C,D\\mbox{ such that}\n\\\\\\\\\n(1+\\delta)\\min_i \\Sigma_{ii} \\geq \\max_i \\Lambda_{ii}, \\Sigma \\succ 0, \\Lambda \\succeq 0,\\\\\\\\\n\\mathrm{Tr}(\\Lambda^2) \\leq 2 \\langle \\Lambda, CD^T\\rangle - (1-\\delta^2)\n(\\mathrm{Tr}(\\Sigma^2)-2 \\langle\\Sigma,AB^T\\rangle + ||AB^T||^2_F + ||AD^T||^2_F + ||CB^T||_F^2 + ||CD^T||_F^2), \\\\\\\\\n\\langle \\Lambda, CD^T \\rangle \\ne 0.\n\\end{gather*}$$\nWhy not replace the property in Theorem 4 by this simpler one? And there may be further simplifications which I have not seen.\n     2) I found the proofs a bit painful to read. No intuition or high-level description is provided. To me, it looked like a long sequence of computations and technical arguments seemingly coming out of nowhere. I think this will make it difficult for other researchers to reuse some of the proof techniques.\n     3) I found Section 4 (about the strict saddle property) quite confusing. I may have missed something, but my impression is that under very mild additional assumptions (continuity of the Hessian of f, for instance), the non-existence of SSOCP directly implies that, for all $\\alpha$, there exists $\\beta,\\gamma$ such that Problem (4) (or (5)) has the $(\\alpha,\\beta,\\gamma)$-strict saddle property. (This can be shown with standard continuity arguments.) As a consequence, from my understanding, what is non-trivial in Theorems 6 and 7 is that $\\beta$ and $\\gamma$ only depend on $f$ through a limited set of properties (RIP constant, rank of the global minimizer ...). But this is not discussed in the article; I was therefore unable to fully understand the interest of Theorems 6 and 7.\n     4) Section 2, presented as a \"motivating example\", seems a bit unrelated with the rest of the article. Theorem 3 is not an example or a particular case of one of the subsequent results. And since the proof is not even sketched outside the appendix, it does not provide insights into proof techniques which will be used in the following sections.\n     5) I did not understand the small insight into the proof of Theorem 6 provided on page 9. I did not understand what the equation after line 345 meant, why it implied the result, and I did not find it in the appendix.\n\nIn addition, I have the following minor remarks:\n- The expression \"necessary and sufficient conditions for the existence of spurious second-order critical points\" can be slightly misleading. I think that something like \"necessary and sufficient conditions for the existence of a function with the $\\delta$-RIP and a spurious second-order critical point\" would be more precise.\n- Page 2, line 43: shouldn't \"$O(n)$\" and \"$O(n+m)$\" be \"$O(rn)$\" and \"$O(r(n+m))$\"?\n- Page 2, line 47: I disagree with \"is required\", since convergence can occur even when the RIP does not hold; I would rather say something like \"can be used\".\n- Page 2, line 54, \"the curvature of the Hessian\": why not simply \"the Hessian\"?\n- Page 3, lines 88-89: \"the result of second-order critical points\" is unclear to me.\n- Page 5, line 188: shouldn't there be a logarithmic term inside \"$O(nmr)$\"?\n- Page 5, line 189: I did not find that \"matrix multiplication\" was a very clear comparison point (especially with no precision on the size of the multiplied matrices).\n- Page 5, line 191: \"combining\" $\\to$ \"combined\".\n- Page 6, line 211: \"iteration points\" $\\to$ \"iterates\"?\n- Page 6, line 218: \"Burer-Monterio\" $\\to$ \"Burer-Montero\"\n- Page 6, line 237: \"there exist\" $\\to$ \"there exists\"\n- Page 7, line 245: \"a basis of\" $\\to$ \"a basis for\"?\n- Page 7, line 282, as well as the corresponding section of the appendix: why does the symmetric function need to satisfy $RIP_{4r,2r}$ and not $RIP_{4r,4r}$?\n- Page 8, equation after line 316: I think this is only true if $||U-U^*||_F$ is small *and $\\mathcal{X}^*$ is bounded*.\n- Page 8, lines 324 to 326: this assertion is not clear enough. The boundedness of the trajectories does not ensure that the Hessian is Lipschitz continuous without any assumption on $f$ besides the fact that it is twice differentiable. (If the Hessian is discontinuous at $0$, for instance, it is not Lipschitz continuous over any set containing $0$, even if trajectories are bounded.)\n- Page 13, Theorem 8: in my opinion, \"first-order critical point\" should be defined. Since the constraint set of Problem (1) is not a manifold, I do not think there is a fully standard definition.\n- Theorem 9, equation after line 503: I think \"$\\sigma_r(\\tilde{U})$\" should be \"$\\sigma_r(\\tilde{U})^2$\".\n- Page 13, line 506: \"the goal\" $\\to$ \"Since the goal\"?\n- Page 13, lines 511, 515, 518: \"hold\" $\\to$ \"holds\"\n- Page 16, line 583: $\\alpha$ should be defined as $\\frac{2\\delta}{1-\\delta}$.\n- Page 16, line 591: \"that\" $\\to$ \"that the\"?\n- Sufficiency part of the proof, starting on page 19: why not set $U=\\left(\\begin{smallmatrix}I_{2r}\\\\\\\\ 0_{n-2r,2r}\\end{smallmatrix}\\right), V=\\left(\\begin{smallmatrix}I_{2r}\\\\\\\\ 0_{m-2r,2r}\\end{smallmatrix}\\right)$? This would slightly simplify the definitions.\n- Page 21, line 686: \"$\\sigma(\\tilde{M})$\" should be \"$\\sigma_r(\\tilde{M})$\".\n- Appendix D.3: I think that the definition of $V$ has been forgotten.\n- Page 24, equation after line 748: \"$\\forall Z\\in\\mathbb{R}^{n\\times m}$\" should come before \"there exists\", since $c$ can depend on $Z$.\n- Page 24, equation after line 740: I think that there should be absolute values (otherwise the right-hand side can be negative, if $t>1$, for instance).\n- Page 25, equation after line 784: I do not understand the reason for taking the minimum with $\\frac{1}{3}$.\n\nProof of the \"simpler property\": if the property in Theorem 4 holds, then the simpler one also does. Conversely, let us assume that the simpler one holds. We set\n$$\\alpha = \\frac{\\langle \\Lambda, CD^T \\rangle}{\\mathrm{Tr}(\\Sigma^2)-2 \\langle\\Sigma,AB^T\\rangle + ||AB^T||^2_F + ||AD^T||^2_F + ||CB^T||_F^2 + ||CD^T||_F^2}.$$\nWith this definition, the three lines of Inequality (6) are true. We must only verify that $1-\\delta< \\alpha < \\frac{1+\\delta}{2}$.\n\nThe third line of the simpler property can be rewritten as $||X_1|| \\leq \\delta ||X_2||$, where\n$$X_1=\\begin{pmatrix}AB^T-\\Sigma & AD^T \\\\\\\\ CB^T & CD^T-\\Lambda \\end{pmatrix},\\qquad\nX_2=\\begin{pmatrix}AB^T-\\Sigma & AD^T \\\\\\\\ CB^T & CD^T \\end{pmatrix}.$$\nAs a consequence, by Cauchy-Schwarz,\n$$\\alpha = \\frac{\\langle X_2-X_1,X_2\\rangle}{||X_2||^2} = 1 - \\frac{\\langle X_1,X_2\\rangle}{||X_2||^2} \\geq 1-\\delta$$\n(and we can show that equality is impossible.)\n\nFor the inequality $\\alpha < \\frac{1+\\delta}{2}$, we set\n$$X_3 = \\begin{pmatrix}\\Sigma&0\\\\\\\\0&\\frac{\\Lambda}{1+\\delta}\\end{pmatrix},\\qquad\nX_4 = \\begin{pmatrix}A\\\\\\\\C\\end{pmatrix} \\begin{pmatrix}B^T&D^T\\end{pmatrix}.$$\nFrom the first line of the simpler condition, the projection of $X_3$ onto the set of rank $r$ matrices is\n$$X_5 = \\begin{pmatrix}\\Sigma&0\\\\\\\\0&0\\end{pmatrix},$$\nwhich means that\n$$\\begin{gather*}\n||X_3-X_5||^2 \\leq ||X_3-X_4||^2 \\\\\\\\\n\\iff\n(1+\\delta)^{-2}\\mathrm{Tr}(\\Lambda^2) \\leq (1+\\delta)^{-2}\\mathrm{Tr}(\\Lambda^2) - \\frac{2}{1+\\delta} \\langle \\Lambda, CD^T\\rangle + ||X_2||^2 \\\\\\\\\n\\iff \\alpha \\leq \\frac{1+\\delta}{2}.\n\\end{gather*}$$\n(Again, one can show that equality is impossible.)\n\n**Added after author feedback:**\n\nI thank the authors for their feedback. On the interest of the Restricted Isometry Property, I do agree with the authors regarding the applications mentionned in their response. I do not agree with the fact that RIP \"captures the complexity of the class of all operators\". However, it does not make the question considered by the authors uninteresting. I simply think it is of more theoretical than practical interest.\n\nRegarding the presentation issues mentioned in my first review, I was a bit disappointed by the first response provided by the authors, as explained during the discussion. The second response was more convincing for me, but a bit too vague to be fully convincing.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable to this article.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "BOF6XviINWN", "reviewer": "Reviewer_vdzf", "summary": "\nThis paper considers the global geometry of general low-rank minimization problems via the Burer-Monterio factorization approach. Compared to the existing state-of-the-art results, this work improves the RIP constant required for the general low-rank minimization problem to have a global benign landscape.  ", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_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": "\nThis paper considers the global geometry of general low-rank minimization problems via the Burer-Monterio factorization approach. \n(1) Compared to the existing state-of-the-art results, this work improves the RIP constant required for the general low-rank minimization problem to have a global benign landscape.  \n(2) The theoretical analyses are sound. This work unifies the theoretical framework for both symmetric and nonsymmetric cases. The sufficiency of the RIP bound is theoretically proved and the necessity is justified by a constructed example.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "(1) The work is motivated by the high computational complexity of the Singular Value Projection (SVP) Algorithm. However, without theoretical or empirical comparisons, it is not clear why the Burer-Monterio factorization approach achieves better overall computational complexities. I think the Burer-Monterio factorization approach has better computation complexity within per iteration, but might require high iteration complexities.\n\n(2) It is not clear why there is a gap between the RIP constants for the rank-1 case and the rank-r case. ", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides improved analysis for both symmetric and asymmetric low-rank optimization problems via the Burer-Monterio factorization approach. Specifically, based on the assumption that the problem satisfies restricted isometry property (RIP), this paper provides much tighter RIP constants for ensuring the following three cases: (1) non-existence of spurious second-order critical point, (2) strict saddle property, and (3) the existence of a counterexample that has spurious second-order critical points. On the other hand, reviewers pointed out that the current presentation of the main results (like Theorem 4) appears too complicated and could be simplified and improved. Also, the analysis cannot be applied to other low-rank optimization problems (e.g., phase retrieval) that have no RIP. 

Overall, all reviewers appreciate the technical contribution of this paper and agree that the merits outweigh the pitfalls, so I recommend accept. Nevertheless, please modify the paper accordingly to improve the presentation and highlight the limitation of RIP-based analysis in the introduction while mentioning some practical problems (e.g., quantum state tomography) that obey RIP.
Decision: Accept (Poster)