General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
Year: 2021

Abstract:
This paper considers the global geometry of general low-rank minimization problems 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 asymmetric problems if the rank-2 RIP constant δ is 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 a counterexample to show that the non-existence of spurious second-order critical points may not hold if δ is at least 1/2. In addition, for any problem with δ 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 δ is less than 1/3. The results of this paper significantly extend several existing bounds in the literature.

heading: 1 Introduction
text: Given the natural numbers n, m and r, consider the low-rank matrix optimization problems
min M∈Rn×n
fs(M) s.t. rank(M) ≤ r, MT = M, M 0 (1)
and
min M∈Rn×m
fa(M) s.t. rank(M) ≤ r, (2)
where the functions fs(·) and fa(·) are twice continuously differentiable. Problems (1)-(2) are referred to as the symmetric and the asymmetric problems, respectively. In addition, we call these problems linear if the objective function is induced by a linear measurement operator, i.e.,
f(M) = 12‖A(M)− b‖ 2 F
for some vector b ∈ Rp and linear operator A mapping each matrix M to a vector in Rp, where f(M) denotes either fs(M) 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 (NeurIPS 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 a 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-Shwartz et al., 2011; Axiotis & Sviridenko, 2020), which also require implementing SVD for r times in their algorithms.

heading: 1.1 Burer-Monteiro factorization and basic properties
text: 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 factorization approach is based on the observation that any matrix M ∈ Rn×m with rank at most r can be written in the form of UV T , where U ∈ Rn×r and V ∈ Rm×r. Then, the asymmetric problem (2) is equivalent to
min U∈Rn×r,V ∈Rm×r ha(U, V ), (3)
where ha(U, V ) := fa(UV T ). Similarly, the symmetric problem (1) is equivalent to
min U∈Rn×r hs(U), (4)
where hs(U) := fs(UUT ). 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 O(n2) or O(nm) to as low as O(rn) or O(r(n+m)) when r min{n,m}. However, the reformulated problems are highly non-convex, and NP-hard to solve in general. On the other hand, these problems share a specific non-convex structure, which makes it possible to 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 asymmetric problem are similar. Definition 1 (Recht et al. (2010); Zhu et al. (2018)). Given natural numbers r and t, the function fs(·) is said to satisfy the Restricted Isometry Property (RIP) of rank (2r, 2t) for a constant δ ∈ [0, 1), denoted as δ-RIP2r,2t, if
(1− δ)‖K‖2F ≤ [ ∇2fs(M) ] (K,K) ≤ (1 + δ)‖K‖2F
holds for all matrices M,K ∈ Rn×n such that rank(M) ≤ 2r, rank(K) ≤ 2t, where[ ∇2fs(M) ] (·, ·) is the curvature of the Hessian at point M .
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 a Gaussian model, Candès & Recht (2009) showed that O ( nr/δ2 ) samples are enough to ensure the δ-RIP2r,2r 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-specific 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, we 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 1 (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 + δ)/(1− δ). 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 fs(·) is said to satisfy the Bounded Difference Property (BDP) of rank 2r for a constant κ ≥ 0, denoted as κ-BDP2r, if∣∣[∇2fs(M)−∇2fs(M ′)] (K,L)∣∣ ≤ κ‖K‖F ‖L‖F holds for all matrices M,M ′,K, L ∈ Rn×n such that rank(M), rank(M ′), rank(K), rank(L) ≤ 2r.
It has been proven in Bi & Lavaei (2021, Theorem 1) that those functions satisfying the δ-RIP2r,2r property also satisfy the 4δ-BDP2r 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 a careful initialization so that the initial point is already in a 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 et al., 2018), which combined with the smoothness properties can guarantee the global polynomial-time convergence for various saddleescaping algorithms (Jin et al., 2017, 2018; Sun et 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 to the nonlinear asymmetric case. Moreover, a weaker geometric property, namely the non-existence of spurious (non-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-order necessary optimality conditions, and thus the result of the non-existence of second-order critical points implies the non-existence of spurious local minima. Under certain regularity conditions, this weaker property is 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 1 for a summary of the state-of-the-art results.
Most of the aforementioned papers are based on the following assumption on the low-rank critical points of the functions fs(·) and fa(·): Assumption 1. The function fa(·) has a first-order critical point M∗a such that rank(M∗a ) ≤ r. Similarly, the function fs(·) has a first-order critical point M∗s that is symmetric, positive semidefinite 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 a 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∗s and M ∗ a are the unique global minima of problems (1)-(2). Theorem 1 (Zhu et al. (2018)). If the functions fs(·) and fa(·) satisfy the δ-RIP2r,2r property, then the critical points M∗s and M ∗ a 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 ∈ Rr×r. 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 U∈Rn×r,V ∈Rm×r ρ(U, V ), (5)
where ρ(U, V ) := ha(U, V ) + µ
4 · g(U, V )
with a constant µ > 0 and the regularization term
g(U, V ) := ‖UTU − V TV ‖2F . 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 to the original problem (2) in the sense that any first-order critical point (U, V ) of problem (2) corresponds to a first-order critical point of problem (5) with balanced energy, i.e. UTU = V TV . Theorem 2 (Zhu et 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.

heading: 1.2 Contributions
text: 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, a 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 a limited number of samples available, either due to the constraints of specific applications or to the great expense of taking more samples. Hence, obtaining a sharper RIP bound is essential for many applications. We summarize our results in Table 1. More concretely, the contributions of this paper are three-folds.
First, we derive necessary conditions and sufficient conditions for the existence of spurious secondorder critical points for both symmetric and asymmetric problems. Using our necessary conditions, we show that the δ-RIP2r,2r property with δ ≤ 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 δ < 1/3 for asymmetric problems, and is a major improvement over Ge et al. (2016) and Li et al. (2019), which requires δ < 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 a small enough step size and a random initialization almost surely converges to 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 to the global minimum when δ ∈ (1/3, 1/2). When δ = 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 δ-RIP2,2 property with δ < 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 δ-RIP2r,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 et al. (2020) to approximate second-order critical points. With the strict saddle property and certain smoothness properties, a wide range of algorithms guarantee a global polynomial-time convergence with a random initialization; see Jin et al. (2017, 2018); Sun et 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.

heading: 1.3 Notation and organization
text: The operator 2-norm and the Frobenius norm of a matrix M are denoted as ‖M‖2 and ‖M‖F , respectively. The trace of matrix M is denoted as tr(M). The inner product between two matrices is defined as 〈M,N〉 := tr(MTN). For any matrix M ∈ Rn×m, we denote its singular values by σ1(M) ≥ · · · ≥ σk(M), where k := min{n,m}. For any symmetric matrix M ∈ Rn×n, we denote its eigenvalues by λ1(M) ≥ · · · ≥ λn(M). The minimal eigenvalue is denoted as λmin(·). For any matrix U , we use PU to denote the orthogonal projection onto the column space of U . For any matrices A,B ∈ Rn×m, we use A⊗B to denote the fourth-order tensor whose (i, j, k, `) element is Ai,jBk,`. The identity tensor is denoted as I. The notation M 0 means that the matrix M is symmetric and positive semi-definite. The sub-matrix Ri:j,k:` consists of the i-th to the j-th rows and the k-th to the `-th columns of matrix R. The action of the Hessian∇2f(M) on any two matrices K and L is given by [∇2f(M)](K,L) := ∑ i,j,k,`[∇2f(M)]i,j,k,`KijLk,`.
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.

heading: 2 Motivating Example: Singular Value Projection Algorithm
text: Before providing theoretical results for problems (4)-(5), we first consider the Singular Value Projection 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 ∈ Rn×m | rank(M) ≤ 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
Msym := {M ∈ Rn×n | rank(M) ≤ r, MT = M, M 0}. We assume without loss of generality that the gradient ∇f(·) is symmetric; see Appendix A for a discussion. The projection is given by only keeping components corresponding to the r largest
Algorithm 1 Singular Value Projection (SVP) Algorithm Input: Low-rank manifold M, initial point M0, number of iterations T , step size η, objective
function f(·). Output: Low-rank solution MT .
1: for t = 0, . . . , T − 1 do 2: Update M̃t+1 ←Mt − η∇f(Mt). 3: Set Mt+1 to be the projection of M̃t+1 ontoM via truncated SVD. 4: end for 5: return MT .
eigenvalues 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+ −M‖F = min K∈M ‖K −M‖F ,
where M+ is the projection of a matrix M . Henceforth,M stands forMsym orMasym, 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 1 converges linearly to the global minimum under the δ-RIP2r,2r property with δ < 1/3. Theorem 3. If function fs(·) (resp. fa(·)) satisfies the δ-RIP2r,2r property with δ < 1/3 and the step size is chosen to be η = (1 + δ)−1, then Algorithm 1 applied to problem (1) (resp. (2)) returns a solution MT such that MT ∈M and f(MT )− f(M∗) ≤ within
T :=
⌈ 1
log[(1− δ)/(2δ)] · log
[ f(M0)− f(M∗) ]⌉ iterations, where f(·) := fs(·) (resp. f(·) := fa(·)), M∗ is the global minimum, M0 is the initial point and d·e 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 a key inequality (13) for the subsequent proofs. We note that the above proof can be applied to other low-rank optimization problems with a suitable definition of the orthogonal projection. In Ha et al. (2020), it is proved that the unique global minimum is the only fixed point of the SVP algorithm if 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 a 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 is the main topic of the remainder of this paper.

heading: 3 No Spurious Second-order Critical Points
text: In this section, we develop necessary conditions and sufficient conditions for the existence of spurious second-order critical points of 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 the objective function to have a Lipschitz-continuous gradient. The first condition is satisfied by the gradient descent method applied to a large class of functions known as the KŁ-functions (Attouch et al., 2013). For the second condition, many objective functions that appear in applications, e.g., the `2-loss function, do not satisfy this condition. However, if the step
size is small enough, the special non-convex structure of the Burer-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 fs(·) and fa(·). The proof of this claim is similar to Theorem 8 in Jin et 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-order 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-order critical points when the δ-RIP2r,2r property is satisfied with δ < 1/3. In this work, we take a different approach to show that δ ≤ 1/3 is enough for the general case in both symmetric and asymmetric scenarios, and that δ < 1/2 is enough for the rank-1 case. Moreover, we prove that there exists a positive correlation between every second-order critical point and the global minimum when δ ∈ (1/3, 1/2). We also show that there may exist spurious second-order critical points when δ = 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 a function that satisfies the δ-RIP2r,2r condition and spurious second-order critical points below. Theorem 4. Let ` := min{m,n, 2r}. For a given δ ∈ [0, 1), there exists a function fa(·) with the δ-RIP2r,2r property such that problems (3) and (5) have a spurious second-order critical point only if 1− δ < (1 + δ)/2 and there exists a constant α ∈ (1− δ, (1 + δ)/2], a diagonal matrix Σ ∈ Rr×r, a diagonal matrix Λ ∈ R(`−r)×(`−r) and matrices A ∈ Rr×r, B ∈ Rr×r, C ∈ R(`−r)×r, D ∈ R(`−r)×r such that If CBT = 0 and ADT = 0, then there exists a function fa(·) with the δ-RIP2r,2r property such that problems (3) and (5) have a spurious second-order critical point.
(1 + δ) min 1≤i≤r Σii ≥ max 1≤i≤`−r Λii, Σ 0, Λ 0, 〈Λ, CDT 〉 = α [ tr(Σ2)− 2〈Σ, ABT 〉+ ‖ABT ‖2F + ‖ADT ‖2F + ‖CBT ‖2F + ‖CDT ‖2F ] , (6) tr(Λ2) ≤ α−1(2α− 1 + δ2) · 〈Λ, CDT 〉, 〈Λ, CDT 〉 6= 0.
Remark 1. We note that there may exist simpler forms of the above conditions. For instance, we may solve α via the condition in the second line of (6) and substitute into other conditions. In addition, the requirement that α ∈ (1− δ, (1 + δ)/2] may also be dropped without affecting the conditions. More specifically, the conditions in (6) are equivalent to
(1 + δ) min 1≤i≤r Σii ≥ max 1≤i≤`−r Λii, Σ 0, Λ 0, 〈Λ, CDT 〉 6= 0, tr(Λ2) ≤ 2 · 〈Λ, CDT 〉 − (1− δ2) [ tr(Σ2)− 2〈Σ, ABT 〉
+ ‖ABT ‖2F + ‖ADT ‖2F + ‖CBT ‖2F + ‖CDT ‖2F ] .
We state Theorem 4 in the current form since it helps with deriving corollaries more directly.
Intuitively, Λ 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-existence of spurious second-order critical points can be viewed as a property of the set of functions satisfying the RIP property, which is a convex set in an infinite-dimensional functional space. The conditions in (6) reduce the infinite-dimensional problem to a finite-dimensional 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 of the above theorem. The first corollary focuses on the rank-1 case. In this case, we can simplify condition
(6) through suitable relaxations to obtain a sharper bound on δ that ensures the non-existence of spurious second-order critical points. Corollary 1. Consider the case r = 1, and suppose that the function fa(·) satisfies the δ-RIP2,2 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 et 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 a second-order critical point for problem (5), since the asymmetric manifold Masym has a larger second-order critical cone than the symmetric manifoldMsym. However, it can be verified that the same example also has a spurious second-order critical point in the asymmetric case. For completeness, we verify the claim in the appendix.
It follows from Corollary 1 and Example 1 that the bound 1/2 is the sharpest bound for the rank-1 asymmetric case. The next corollary provides a marginal improvement to the state-of-the-art result for the general rank case, which derives the RIP bound δ < 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 r, suppose that the function fa(·) satisfies the δ-RIP2r,2r property. If δ ≤ 1/3, then both problems (3) and (5) have no spurious second-order critical points. In addition, if δ ∈ [0, 1/2), then every second-order critical point M̃ has a positive correlation with the ground truth M∗a . Namely, there exists a universal function C(δ) : (0, 1/2) 7→ (0, 1] such that
〈M̃,M∗a 〉 ≥ C(δ) · ‖M̃‖F ‖M∗a‖F .
For the general rank-r case, we construct a counterexample with spurious second-order critical points when δ = 1/2. Example 2. Let n = m = 2r. Now, we use the sufficiency part of Theorem 4 to construct a counterexample. We choose
δ := 1
2 , α :=
3 5 , Σ := 1 2 Ir, Λ := 3 4 Ir, A = B := 0r, C = D := Ir.
It can be verified that the conditions in (6) are satisfied and CBT = ADT = 0, which means that there exists a function fa(·) satisfying the δ-RIP2r,2r property for which problems (3) and (5) have spurious second-order critical points. We also give a 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 fs(·) to have the δ-RIP4r,2r property, which provides sub-optimal RIP bounds compared to a 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, 2r}. For a given δ ∈ [0, 1), there exists a function fs(·) with the δ-RIP2r,2r property such that problem (4) has a spurious second-order critical point only if 1− δ < (1 + δ)/2 and there exists a constant α ∈ (1− δ, (1 + δ)/2], a diagonal matrix Σ ∈ Rr×r, a diagonal matrix Λ ∈ R(`−r)×(`−r) and matrices A ∈ Rr×r, C ∈ R(`−r)×r such that
(1 + δ) min 1≤i≤r Σii ≥ max 1≤i≤`−r Λii, Σ 0, 〈Λ, CCT 〉 = α [ tr(Σ2)− 2〈Σ, AAT 〉+ ‖AAT ‖2F + 2‖ACT ‖2F + ‖CCT ‖2F ] , (7)
tr(Λ2) ≤ α−1(2α− 1 + δ2) · 〈Λ, CCT 〉, 〈Λ, CCT 〉 6= 0. If ACT = 0, then there exists a function fs(·) with the δ-RIP2r,2r property for which problem (4) has a 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.
Corollary 3. If function fs(·) satisfies the δ-RIP2r,2r property, then the following statements hold:
• If δ ≤ 1/3, then there are no spurious second-order critical points;
• If δ < 1/2, then there exists a positive correlation between every second-order critical point and the ground truth;
• If δ = 1/2, then there exists a counterexample with spurious second-order critical points;
• If δ < 1/2 and r = 1, then there are no spurious second-order critical points.
We note that the last statement serves as a generalization of the results in Zhang et al. (2019) to the nonlinear measurement case, and improves upon the bound in Bi & Lavaei (2021) by dropping the BDP constant.

heading: 4 Global Landscape: Strict Saddle Property
text: 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 at approximate second-order critical points for exponentially long time. To guarantee the global polynomial-time convergence, the following strict saddle property is commonly considered in the literature: Definition 3 (Sun et al. (2018)). Consider an arbitrary optimization problem minx∈X⊂Rd F (x) and let X ∗ denote the set of its global minima. It is said that the problem satisfies the (α, β, γ)-strict saddle property for α, β, γ > 0 if at least one of the following conditions is satisfied for every x ∈ X :
dist(x,X ∗) ≤ α; ‖∇F (x)‖F ≥ β; λmin[∇2F (x)] ≤ −γ.
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 c1(X ∗) > 0 and c2(X ∗) > 0 such that c1(X ∗) · ‖U − U∗‖F ≤ ‖UUT − U∗(U∗)T ‖F ≤ c2(X ∗) · ‖U − U∗‖F holds for all U ∈ X as long as ‖U − U∗‖F 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 Õ( −2) iterations with high probability if the Hessian of the objective function is Lipschitz. Namely, the algorithm returns a point x ∈ X such that
‖∇F (x)‖F ≤ O( ), λmin[∇2F (x)] ≥ −O( √ )
in Õ( −2) iterations with high probability. If we choose > 0 to be small enough such that O( ) < β and −O( √ ) > −γ, then the strict saddle property ensures that the returned point satisfies dist(x,X ∗) ≤ α 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-time 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 r. Assumption 2. The global optimum M∗a or M∗s has rank r.
It has been proved in Zhu et al. (2021) that the regularized problem (5) satisfies the strict saddle property if the function fa(·) has the δ-RIP2r,4r property with
δ < σr(M
∗ a ) 3/2
100‖M∗a‖F ‖M∗a‖ 1/2 2
.
Our results improve upon their bounds by allowing a larger problem-free RIP constant and requiring only the RIP2r,2r property (note that there are problems with RIP2r,2r property for which the RIP2r,4r property does not hold (Bi & Lavaei, 2021)). Our result can also be viewed as a robust version of the results in Ha et al. (2020).
Theorem 6. Suppose that the function fa(·) satisfies the δ-RIP2r,2r property with δ < 1/3. Given an arbitrary constant α > 0, if µ is selected to belong to the interval [(1− δ)/3, 1− δ), then there exist positive constants
1 := 1(δ, r, µ, σr(M ∗ a ), ‖M∗a‖F , α), λ1 := λ1(δ, r, µ, σr(M∗a ), ‖M∗a‖F , α)
such that for every ∈ (0, 1] and λ ∈ (0, λ1], problem (5) satisfies the (α, β, γ)-strict saddle property with β := min { µ( /r)3/2, λ } , γ := µ .
We note that the constraint µ ∈ [(1− δ)/3, 1− δ) is not optimal and it can be similarly proved that µ ∈ (δ, 1− δ) also guarantees the strict saddle property. The key step in the proof is to show that for every point (U, V ) at which the gradient of fa(UV T ) is small, it holds that
‖∇fa(UV T )‖22 ≥ (1 + δ)2σ2r(UV T ) + C · (1− 3δ)[fa(UV T )− fa(M∗a )], where C > 0 is a constant independent of (U, V ). This inequality can be viewed as a major extension of the non-existence of spurious second-order critical points when δ < 1/3 (Ha et al., 2020), which shows that every spurious second-order critical point (U, V ) satisfies
‖∇fa(UV T )‖22 > (1 + δ)σ2r(UV T ). We emphasize that our proof requires a new framework and is not a standard revision of the existing methods, which is the reason why sharper bounds can be established. By replacing ‖∇fa(M)‖2 with −λmin(∇fs(M)), the analysis for the asymmetric case can be extended to the symmetric case with minor modifications and the same bound follows. Theorem 7. Suppose that the function fs(·) satisfies the δ-RIP2r,2r property with δ < 1/3. Given an arbitrary constant α > 0, there exists a positive constant λ1 := λ1(δ, r, σr(M∗s ), ‖M∗s ‖F , α) such that for every λ ∈ (0, λ1], problem (4) satisfies the (α, β, γ)-strict saddle property with
β := λ, γ := 2λ.
The above bound is the first theoretical guarantee of the strict saddle property for the nonlinear symmetric problem.

heading: 5 Conclusion
text: In this work, we analyze the geometric properties of low-rank optimization problems via the nonconvex 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 a positive correlation between secondorder critical points and the global minimum for problems whose RIP constants are higher than the developed bound but lower than the fundamental limit obtained by the counterexamples. Finally, the strict saddle property is proved with a weaker requirement on 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.

Review summaries:
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.   The 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$.  Additionally, 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.

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 - the global minimizer of $f$ has low-rank (at most $r$) ; - the Hessian of $f$, when restricted to matrices with rank at most $2r$, satisfies the restricted isometry property with constant $\delta$.  The 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).  The main results are: - a general (more or less) necessary and sufficient condition for the existence of a function with a SSOCP (Theorems 4 and 5); - 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); - for arbitrary $r$, if $\delta\leq 1/3$, there is no SSOCP (Corollary 2; minor improvement over Ha et al (2020)); - for arbitrary $r$, if $1/3<\delta<1/2$, SSOCP are positively correlated with the ground truth (Corollary 2); - 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).

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.