Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper considers the problem of minimizing a convex function f of symmetric n-by-n matrices X over the space P(n,k) of orthogonal projectors on all k-dimensional subspaces of R^n. A special case is PCA but the formulation allows for generalized forms of PCA (robust, sparse, etc). The natural iterative method to approach this problem is projected gradient descent applied to the original problem min f(X) s.t. X\in P(n,k), in which we need to project on P(n,k) (which requires SVD) in every iteration. The paper proposes a low-rank iterative method applied to the problem min f(Q*Q') s.t. Q'*Q=I, Q is n-by-k, which requires only one QR factorization in every iteration (this can be seen as approximating SVD by doing only one iteration of the orthogonal iterations method). To analyze this method, the paper also considers an SDP relaxation of the original problem, in which P(n,k) is replaced with its convex hull F(n,k) (the Fantope), which has an SDP description.

The contribution of the paper is a theoretical analysis of the low-rank iterative method. The key concept is  the "eigengap" of a solution X to the SDP relaxation, which is the difference between the k-th and (k+1)-th largest eigenvalues of the gradient \nabla f(X) (a symmetric matrix). It is proved that existence of an optimal solution to the SDP with non-zero eigengap is equivalent to strict complementarity of a pair of primal-dual solution to the SDP (Theorem 1) and implies that the SDP has a unique optimum with rank k (hence, the SDP relaxation is tight) (Theorem 2).

The main contribution is a convergence result for the low-rank iterative method (Theorem 3), which says the following: If the SDP relaxation have a non-zero eigengap and the initial point Q1 of the method is such that Q1*Q1' is within a given (small) ball around the optimal SDP solution, then the method converges linearly to the global optimum of the original problem.

Almost all the rest of the paper is devoted to a sketch of the proof of Theorem 3. At the end of the paper, there are brief numerical experiments on random data, showing that the convergence rates of the projected-gradient method and the low-rank method are almost the same (but, as written above, the latter needs only one QR factorization rather than SVD factorization in each iteration).
strengths_and_weaknesses: This is an interesting formulation of the low-rank method, which requires only one QR (rather than SVD) factorization per iteration.

The theoretical analysis is interesting. However, its novelty is only incremental, given the prior work [5] and [8,9].
Moreover, its impact is rather weak: if the initial point of the low-rank method is not within a small ball of the optimal solution (which we of course do not know without solving the SDP), the results (Thm 3) give no guarantees of convergence to the global optimum.

The text is easy to understand, but its clarity and organization should be improved. In particular, it would be more helpful if all longer proofs were moved to a supplement and the saved space was used to explain the consequences of the theoretical results in more detail. E.g., the questions I raise in the "Questions" part could be discussed.

The numerical experiments are very brief. I believe that more numerical experiments might clarify some issues as I suggest in the "Questions" part. Moreover, experiments on data from real applications might better show the properties of the method.

In summary, I think that the main ideas are interesting but I am not sure if the current contribution and its form are good enough for this conference. I believe that giving the paper more time and effort to develop would result in a better and more mature paper.

Minor remarks:
- Perhaps, it would be useful in the theoretical analysis to consider one more iterative method, namely projected gradient method applied to the problem min f(Q*Q') s.t. Q'*Q=I, Q is n-by-k. This method requires orthogonal projection to the space of n-by-k matrices with orthonormal columns (i.e., the nearest linear isometry problem), which requires SVD. Perhaps, method (3) can be more directly seen as an approximation to this method than to method (2). But I may be wrong, this is just a suggestion.
- I'd use a different symbol than \partial for the total derivative in (3), such as {\rm d}.
- Typo in Lagrange function below line 101, (X) should be f(X).
- In Definition 1, I believe that disjunction (\vee) should be conjunction (\wedge).
questions: 1. Can it happen (assuming a nonzero eigengap assumption) that the rank of Z_{t+1} is smaller than k in (3)? If so, the QR factorization must do some random choice. Is the iteration valid then?

2. Can fixed points of iterations (3) be described in some simple way, such as a closed formula?

3. Does there hold also the opposite implication in Theorem 1, i.e., is it true that if a (optimal) solution to the SDP (4) has rank k then it has a nonzero eigengap?

4. Does it hold that if the SDP relaxation (4) is tight (i.e., some of its optimal solutions has rank k), then problem (1) has no local minima that are not global minima (where "local minimum" has the obvious meaning here as a local minimum of a function on a set)? Note, this could be easily supported or disproved by numerical simulations.

5. A very related question: Suppose some optimal solution to the SDP has a nonzero eigengap but the initial point Q1 to method (3) does not satisfy the other assumption of Theorem 3 (i.e., Q1*Q1' is not within the given ball around the optimal solution to the SDP). Does it mean that method (3) may not converge at all, can converge to the global optimum but with sub-linear rate, or converge to a point that is not the global optimum? Some of these options could (and should) also be supported or disproved by numerical experiments.
limitations: The impact of the main theoretical result (Theorem 3) is rather weak, see above.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this work, the authors studied the problem of finding a $k$-dimensional subspace problem: $\min f(\mathbf{Q}\mathbf{Q}^T)\ \text{s.t.}\ \mathbf{Q}^T\mathbf{Q} = \mathbf{I}$, where $f$ is convex and smooth. They studied the relationship between the convex relaxation-based method and the non-convex method with the gradient orthogonal iterations under a strict complementarity assumption. Based on this, they showed that the non-convex gradient method converges locally with a linear rate. They also showed the linear convergence of the non-convex projected gradient method and the Frank-Wolfe method for solving this problem.
strengths_and_weaknesses: Strengths: (${\bf 1}$) Subspace recovery is a fundamental problem in machine learning. This paper studied the convergence rate of different methods for solving  the subspace problem: $\min f(\mathbf{Q}\mathbf{Q}^T)\ \text{s.t.}\ \mathbf{Q}^T\mathbf{Q} = \mathbf{I}$. Unlike existing approaches that assume $f$ admits a special structure or considers an underlying generative model, they proposed a deterministic condition, i.e., strict complementarity, which seems new and interesting. 

(${\bf 2}$)  Overall, the paper is well-written and easy to follow. I think that the authors made good enough technical contributions to the convergence analysis of the first-order methods for solving subspace optimization problems.

(${\bf 3}$)  This work bridges convex and non-convex methods for subspace optimization problems via a strict complementarity condition. In particular, linear convergence can be established through this bridge. 

Weaknesses: (${\bf 1}$)  In Assumption 1, the authors imposed an eigen-gap condition, i.e., $\lambda_{n-k}(\nabla f(\mathbf{X}^*)) - \lambda_{n-k+1}(\nabla f(\mathbf{X}^*)) \ge \delta$ for some $\delta > 0$, on an optimal solution $ \mathbf{X}^*$ to the problem: $\min f(\mathbf{X})\ \text{s.t.}\  \mathbf{I} \succeq \mathbf{X} \succeq \mathbf{0},\ \mathrm{Tr}( \mathbf{X}) = k$. From the authors' introduction, this condition is closely related to the complementarity condition of the KKT system of Problem (4) (see Theorem 2). It looks strange that studying convergence rate of a method for solving a problem by imposing condition onto its optimal solution. On the other side, the authors mentioned the error-bound condition. According to [29], the error-bound condition holds for many general problems.  However, the authors in this work cannot give a concrete example so that Assumption 1 holds like [29]. 

(${\bf 2}$)  In general, the numerical simulations are not convincing. For example, in the left figure of Figure 1 in Section 4, the y-axis should be plotted on a log scale. The current scale cannot demonstrate the linear convergence of the tested method. Besides, the authors should also report the convergence rate of the Frank-Wolfe method to support Theorem 5. 


questions: 
(${\bf 1}$)  The authors mentioned that strictly complementarity is closely related to the error-bound condition (see Ref [29, 6]). It is known that the error-bound condition also implies linear convergence of the first-order method under some mild conditions. Does Assumption 1 imply the error bound of Problem (4)? It would be great if the authors elaborate on the relationship between them. 

(${\bf 2}$) According to Theorems 3 and 4, the authors only showed the linear convergence of function values. According to the results in [29] and $\textbf{Attouch and Bolte (2009)}$, they can show linear convergence of the sequence generated by the studied methods. Could the authors show the linear convergence of the sequence?

$\textbf{Attouch and Bolte (2009)}$: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming, 116(1), 5-16.

(${\bf 3}$) Lemma 4 shows quadratic growth of Problem (4). According to [6], quadratic growth is equivalent to the error bound under a mild condition. Maybe, the following proofs could be simplified using the results in [6] and [29] when the error bound of Problem (4) is available. Please check it. 
limitations: Yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: For optimization problem of finding a $k$-dimensional subspace, iterative schemes derived from both non-convex and convex formulations are developed in the literature. In this paper, based on a strict complementarity condition, the authors proved local linear convergence of several schemes, including non-convex projected gradient descent and gradient orthogonal iteration. For the obtained convergence results, the starting point of the schemes need to be close enough to the solution. 
strengths_and_weaknesses: The main contribution or strength of the paper is theoretical analysis. That is, proving local linear convergence of non-convex projected gradient descent, gradient orthogonal iteration and Frank-Wolfe methods, which is based on connecting the non-convex model and convex one. 

To me, there are several limitations of the obtained results:
 - Assumption 1 requires a parameter which cannot be verified before solving the problem. What happens if $k$ is chosen relatively large enough such that $\lambda_{n-k}=\lambda_{n-k+1} = 0$, should this be a problem to concern?
 - All the convergence rate theorems require the starting point of the numerical schemes to be closely enough to the solution, which is not discussed how to achieve this in practice. Hence making the local convergence result limited. It is also not elaborated what exactly is the "warm-start" strategy.
 - Lemma 3 the "quadratic growth" assumption basically is the weaker strong convexity assumption, the authors should discuss its connections/differences compared to existing approaches. 
questions: A small question, how to choose $k$ in practice?

The paper is not well-written overall, and the authors should polish the paper thoroughly. 
 - line 5, what does "among others" mean?
 - line 7 "or ," to ", or"
 - line 12, the whole sentence "Our result ..." i guess needs rephrase.
 - line 24 "include among other..."
 - For the footnotes, please unify the starting letter in capital. 
 - line 34"] however" to "]. However"
 - "aka" to "a.k.a."
 - line 59 "efficient implementation of will...", of what will?
 - line 81, "(2))" and ". $^3$"
 - line 188 $X \in \mathcal{F}\_{k}$, should be $\mathcal{F}\_{n,k}$?
 - page 8, Lemma 6,8,9 are not appear in the main paper.
limitations: Not applicable here.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the k-dimensional subspace problem, which is a nonconvex problem over the orthogonal matrix set. An efficient projection gradient method using QR decomposition is studied. The main contribution is that the strict complementarity is shown to be equivalent to the eigen-gap condition. Moreover, under the eigen-gap condition, the projection gradient method is shown to be linearly convergent. 
strengths_and_weaknesses: 
Strengths:
This paper studies a general setting of k-dimensional subspace problem. The local linearly convergence under strict complementarity is interesting.

Weaknesses:
1. The symbol << is not standard, please use $\ll$ (\ll) instead
2. To use the KKT conditions, the slater's condition should be verified though it is obviously satisfied if k<n. 
3. The numerical experiments do not show the linear convergence, since the linear convergence rates are  important results in this paper. 
4. The linear convergence rate of projected gradient method for k-dimensional subspace problem is extensively studied in recent years. The strict complementarity or eigen-gap condition could be strong in some settings. For example, Liu et al. 2019 studies the quadratic problem on Stiefel manifold. But the do not need that the eigenvalues are distinct [Theorem 1, Liu et al. 2019]. Some discussions will be helpful. 

Liu, H., So, A. M. C., & Wu, W. (2019). Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods. Mathematical Programming, 178(1), 215-262.
questions: no
limitations: Not applied.
review_title: null

Meta-review: metareview: The submitted work presents a local linear convergence guarantee for a projected gradient descent (PGD) algorithm on an explicit parameterization of the Stiefel manifold. Such a guarantee is easy to make if the convex objective f is assumed to be strongly convex. Instead, this work considers allowing f to be non-strongly convex. Under a strict complementarity assumption, which this paper shows is equivalent to an eigen-gap condition, the authors prove that the problem enjoys a standard quadratic growth condition that allows PGD to converge at a linear rate. 

Reviewers Lsrb, tL19, Fujo concur that the theoretical contribution is worthy of publication. The past few years have seen a large number of local linear convergence guarantees by directly optimizing the factor matrix $U$ in the low-rank factorization $X=UU^T$, but all of these work have assumed some notion of strong convexity or restricted strong convexity. Indeed, I remark here that local linear convergence is actually lost in many of these cases (e.g. matrix sensing) if the objective f is not (restrictedly) strongly convex. In comparison, the present work allows f to be an arbitrary smooth convex function, while showing that local linear convergence is surprisingly still possible under a strict complementarity condition.

However, the impact of the work is obfuscated by repeated assertions to the practical aspects of the proposed algorithm, which in my opinion are difficult to defend. The authors repeatedly assert that their nonconvex algorithm requires only a single QR decomposition, and therefore "much faster and simpler to implement". This may be the case, but the actual reduction in the number of QR decompositions is only a logarithmic factor $O(\log(1/\epsilon))$ under the eigen-gap assumption. On the other hand, global convergence is lost with the nonconvex formulation, and random initialization leads to sublinear convergence in practice. Reviewer mnGb remarks that the numerical experiments are very brief, and do not make a strong case for the practical aspects of the algorithm. 

Nevertheless, the technical novelty of the analysis pushes this paper towards acceptance. In the camera-ready version, the authors are advised to: 
* Revise their summary of contributions to better compare with existing techniques in the literature, as outlined by Reviewers Lsrb, tL19, Fujo; 
* Expand on their experimental section to answer the questions posed by Reviewer mnGb on global convergence, the existence of bad local minima. Answers to these questions can and should be supported or disproved by numerical experiments.


confidence: Certain
Decision: Accept