Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: 
This 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.  
main_review: 
This paper considers the global geometry of general low-rank minimization problems via the Burer-Monterio factorization approach. 
(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.  
(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.
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.

(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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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
- 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).
main_review: I think this is a good article, notably for the following two reasons:
1) 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.
2) 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.)

However, in my opinion, this article also suffers from the following two drawbacks:
1) 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.
2) 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.
     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):
$$\begin{gather*}
\mbox{There exists diagonal matrices }\Sigma, \Lambda\mbox{ and matrices }A,B,C,D\mbox{ such that}
\\\\
(1+\delta)\min_i \Sigma_{ii} \geq \max_i \Lambda_{ii}, \Sigma \succ 0, \Lambda \succeq 0,\\\\
\mathrm{Tr}(\Lambda^2) \leq 2 \langle \Lambda, CD^T\rangle - (1-\delta^2)
(\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), \\\\
\langle \Lambda, CD^T \rangle \ne 0.
\end{gather*}$$
Why not replace the property in Theorem 4 by this simpler one? And there may be further simplifications which I have not seen.
     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.
     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.
     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.
     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.

In addition, I have the following minor remarks:
- 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.
- Page 2, line 43: shouldn't "$O(n)$" and "$O(n+m)$" be "$O(rn)$" and "$O(r(n+m))$"?
- 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".
- Page 2, line 54, "the curvature of the Hessian": why not simply "the Hessian"?
- Page 3, lines 88-89: "the result of second-order critical points" is unclear to me.
- Page 5, line 188: shouldn't there be a logarithmic term inside "$O(nmr)$"?
- 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).
- Page 5, line 191: "combining" $\to$ "combined".
- Page 6, line 211: "iteration points" $\to$ "iterates"?
- Page 6, line 218: "Burer-Monterio" $\to$ "Burer-Montero"
- Page 6, line 237: "there exist" $\to$ "there exists"
- Page 7, line 245: "a basis of" $\to$ "a basis for"?
- 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}$?
- Page 8, equation after line 316: I think this is only true if $||U-U^*||_F$ is small *and $\mathcal{X}^*$ is bounded*.
- 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.)
- 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.
- Theorem 9, equation after line 503: I think "$\sigma_r(\tilde{U})$" should be "$\sigma_r(\tilde{U})^2$".
- Page 13, line 506: "the goal" $\to$ "Since the goal"?
- Page 13, lines 511, 515, 518: "hold" $\to$ "holds"
- Page 16, line 583: $\alpha$ should be defined as $\frac{2\delta}{1-\delta}$.
- Page 16, line 591: "that" $\to$ "that the"?
- 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.
- Page 21, line 686: "$\sigma(\tilde{M})$" should be "$\sigma_r(\tilde{M})$".
- Appendix D.3: I think that the definition of $V$ has been forgotten.
- 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$.
- 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).
- Page 25, equation after line 784: I do not understand the reason for taking the minimum with $\frac{1}{3}$.

Proof 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
$$\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}.$$
With this definition, the three lines of Inequality (6) are true. We must only verify that $1-\delta< \alpha < \frac{1+\delta}{2}$.

The third line of the simpler property can be rewritten as $||X_1|| \leq \delta ||X_2||$, where
$$X_1=\begin{pmatrix}AB^T-\Sigma & AD^T \\\\ CB^T & CD^T-\Lambda \end{pmatrix},\qquad
X_2=\begin{pmatrix}AB^T-\Sigma & AD^T \\\\ CB^T & CD^T \end{pmatrix}.$$
As a consequence, by Cauchy-Schwarz,
$$\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$$
(and we can show that equality is impossible.)

For the inequality $\alpha < \frac{1+\delta}{2}$, we set
$$X_3 = \begin{pmatrix}\Sigma&0\\\\0&\frac{\Lambda}{1+\delta}\end{pmatrix},\qquad
X_4 = \begin{pmatrix}A\\\\C\end{pmatrix} \begin{pmatrix}B^T&D^T\end{pmatrix}.$$
From the first line of the simpler condition, the projection of $X_3$ onto the set of rank $r$ matrices is
$$X_5 = \begin{pmatrix}\Sigma&0\\\\0&0\end{pmatrix},$$
which means that
$$\begin{gather*}
||X_3-X_5||^2 \leq ||X_3-X_4||^2 \\\\
\iff
(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 \\\\
\iff \alpha \leq \frac{1+\delta}{2}.
\end{gather*}$$
(Again, one can show that equality is impossible.)

**Added after author feedback:**

I 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.

Regarding 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.
limitations_and_societal_impact: Not applicable to this article.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 

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.
main_review: **Originality**

To 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.

**Quality**

The results of the paper look correct to me. I have the following comments/suggestions to make:

* 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:  
[1] Shai Shalev-Shwartz, Alon Gonen, Ohad Shamir: Large-Scale Convex Minimization with a Low-Rank Constraint. ICML 2011: 329-336  
[2] Kyriakos Axiotis, Maxim Sviridenko: Local Search Algorithms for Rank-Constrained Convex Optimization. ICLR 2021

* 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.

* 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?

**Clarity**

The 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:

* 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)?

* 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.

* 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.

**Significance**

I 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.
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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

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.

I do not see any particular strong weakness, but I only have the following remarks:
-It might be helpful for the reader if the authors could make precise what they mean by “the problems are equivalent” in Theorem 2
-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.
-typo in l. 319 “gradient decent”
-I think it might be helpful for the reader if the authors could motivate the non-linear formulation by some particular example.

limitations_and_societal_impact: N/A
review_title: null

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)