Local Linear Convergence of Gradient Methods for  Subspace Optimization via Strict Complementarity
Authors: Ron Fisher
Dan Garber
Venue: NeurIPS 2022 Accept (2022)
Keywords: subspace recovery
principal component analysis
convex optimization
Frank-Wolfe
low-rank
robust PCA
nonconvex optimization
strict complementarity
first-order methods

Abstract: We consider optimization problems in which the goal is to find a $k$-dimensional subspace of $\mathbb{R}^n$, $k<<n$, which minimizes a convex and smooth loss. Such problems generalize the fundamental task of principal component analysis (PCA) to include robust and sparse counterparts, and logistic PCA for binary data, among others. This problem could be approached either via nonconvex gradient methods with highly-efficient iterations, but for which arguing about fast convergence to a global minimizer is difficult or, via a convex relaxation for which arguing about convergence to a global minimizer is straightforward, but the corresponding methods are often inefficient. In this work we bridge these two approaches under a strict complementarity assumption, which in particular implies that the optimal solution to the convex relaxation is unique and is also the optimal solution to the original nonconvex problem. Our main result is a proof that a natural nonconvex gradient method which is \textit{SVD-free} and requires only a single QR-factorization of an $n\times k$ matrix per iteration, converges locally with a linear rate. We also establish linear convergence results for the nonconvex projected gradient method, and the Frank-Wolfe method when applied to the convex relaxation.

Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementarity
Ron Fisher
Dan Garber
Technion Israel Institute of Technology
Technion Israel Institute of Technology Haifa, Israel 3200003
Haifa, Israel 3200003
ronfisher@campus technion.c. ac ai.il
dangar@technion. ac iil
Abstract
We consider optimization problems in which the goal is to find k-dimensional subspace R", k << n,, which minimizes convex and smooth loss. Such problems generalize the fundamental task of principal component analysis (PCA) include robust and sparse counterparts, and logistic PCA for binary data, among others. This problem could be approached either via nonconvex gradient methods with highly-efficient iterations, but for which arguing about fast convergence to global minimizer is difficult or, via convex relaxation for which arguing about convergence to global minimizer is straightforward, but the corresponding methods are often inefficient in high dimensions. In this work we bridge these two approaches under a strict complementarity assumption, which in particular implies that the optimal solution to the convex relaxation unique and is also the optimal solution to the original nonconvex problem. Our main result is a proof that natural nonconvex gradient method which is SVD-free and requires only a single QR-factorization with linear rate. We also establish linear convergence results for the nonconvex projected gradient method, and the Frank- Wolfe method when applied to the convex relaxation.
an n x & matrix per iteration, converges locally
Introduction
We consider the problem of finding k-dimensional subspace of RR << n, which minimizes given objective function, where we identify subspace with its corresponding projection matrix. That is, we consider the following optimization problem:
min f(X) subject
X E (QQ E gank Q
Throughout this work and unless stated otherwise, we assume that f(-) convex, 8-smooth (gradient Lipschitz) and, for ease of presentation, we also assume that the gradient V V.(()) is symmetric matrix over the space of n x n symmetric matrices Srlll
Problems of interest that fall into this model include among others robust counterparts of PCA, which are based the smooth and convex Huber loss (see concrete examples in Section 4h logistic PCA 15), and sparse PCA (26). Note that in Problem [ we are interested in the low-dimensional subspace itself (as opposed the projection of the data onto it, in many other formulations), which is important for instance when the end goal is to perform dimension reduction, which is one of the most important applications of PCA-style methods.
in case gradient not symmetric matrix at some point X S", then denoting it by V nossym ((X). always take its symmetric counterpart V fXX) (VV nf (X) + V Vousymm (X) and, unless stated otherwise, our derivations throughout this work will remain the
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Motivated by high -inensninnsioal problems, we are interested in highly efficient (in particular in terms of the dimension n) first-order methods for Problem I Moreover, we are interested in establishing, at least locally, fast convergence to the global minimizer, despite the fact that Problem ① is nonconvex. Subspace recoveryloptimizztion problems similar to Prohlem
① have received significant interest in 2 however, different from these works, our approach will not assume that f f() admits a very specific structure (e.g., a linear or quadratic function), or will be based on specific underlying statistical model. Instead, we will be interested in deterministic conditions that may hold for quite general f(-) (which is convex and smooth), and may render quite wide variety of problems "well-posed" for efficient optimization.
recent years, see for instance 25
28 4 17
18
11
16
22
We begin by briefly describing two natural dimension-efficeen first-order methods for tackling Problem (I. One such method is the nonconvex projected gradient method which follows the dynamies:
X(+1 f PI, X 7/4 (X)))
where IIp,,..1 [-] denotes the Euclidean projection onto the set Pr,,e (note that since this set nonconvex, in general, the projection need not be unique). and 17: > 0 is the step-size. Given the gradient Vf(),). the runtime to compute X,+1 dominated by the computation of the projection. the Euclidean projection is given by the projection matrix which corresponds to the span of the top k eigenvectors of the matrix X 77. (XX,). While accurate computation of this projection requires (thin) singular value decomposition (SVD) of n matrix, which amounts to (1z²)) runtime, it can also be approximated up to sufficiently small error using fast iterative methods, such as the well-known orthogonal iteration method [T0] (aka subspace iteration method (24). The orthogonal iteration method finds a n x & matrix Q with orthonormal columns which approximately span the subspace spanned by the & leading eigenvectors of a given positive semidefinite n X matrix A, by repeatedly applying the iterations:
well known that
(Q, R) + OR-FACTORIZE( AQ). where QR- (R-FACTORIZE( denotes the QR factorization of matrix, i.e., Q E TRa has orthonormal columns. Every iteration of this method takes in worst case only (kn)²) time. When the gradient V fX,, admits a favorable structure such as sparsity or a low-rank factorization, the runtime to approximate the projection onto Pn, using the orthogonal iteration method could be significantly improved.
Another natural approach to tackle Problem T to exploit the fact that each X E Pr., could be factored as X QQ T. Q E ma*k having orthonormal columns, and to apply gradient steps w.r.t. this factorization. This leads to the following dynamics, which we refer to as Gradient Orthogonal Iteration:
Qf(QQT)
Z,11 <- Q 1}.
=Q 7: V.(. Q
8Q
Q
(Q+11, R(+1) + QR- (2-FACTTRIZEE():
(3)
where the QR--QC---aiiii factorooiizttinn step is required to ensure that Q++1 Q.4,1 is also a projection matrix.
As opposed to the Dynamics 1 which as discussed, an efficient implementation of will require to run QR- -ased iterative method to compute the Euclidean projection onto Pn,, on each iteration, the Dynamics (3) only requires single QR factorization per iteration, and thus, given the gradient matrix f Q.Q.). ). the next iterate Q++1 can be computed in overall O(n2k) 2)) time. As mentioned above, this runtime could be further significantly improved if the multiplication (f(Q, Q.)Q, could be carried out faster than kn)²k) (for instance when the gradient sparse or admits a low-rank factorization), since all other operations require only O Okk2n) time (e.g., factorizing of Z.+1).
Obtaining provable guarantees on the fast local convergence of the Dynamics 3 a global optimal solution of Problem ① is the main contribution of this work.
While both Dynamics B apply efficient iterations, since they are inherently nonconvex, arguing about their convergence to a global optimal solution of [I is difficult in general. An alternative is to replace Problem ① with a convex counterpart, for which, arguing about the convergence of first-order methods to a global optimal solution is well understood. Consider the convex set set Fn,, = conv conv(Pn,.)) (Pr,.). where conv(-) denotes the convex-hull operation. FFrikinnFF........ k is also called the Fantope and it is known to admit the following important characterization: Fr, = (X E @ I X Z 0, Tr(X)
k). where A t 0 denotes that A is a positive semidefinite matrix (PSD), see for instance 20 This leads to the
2

---

convex problem:
min f(X) subject to X F [X I X Tr(x = kj.
(4)
A well known first-order method applicable to is the Frank-Wolfs method (aka conditional gradient) [2]. which for the convex Problem follows the dynamies:
f arg min mig VEP...A
Tr(V(((X)))) X (1 Xr The V. n E [0,
(5)
It follows from Ky Fan's maximum principle 77 that computing V, amounts to computing the projection matrix onto the span of the eigenvectors corresponding to the & smallest eigenvalues of Vf(x)), and hence can be carried out efficiently using the orthogonal iterations method or similar methods, similarly to the computation of the projection in ( discussed above. Note however that the Frank-Wolfe iterates will not be, in general, low rank, and only yield a O(1/t) convergence rate
12
1.1
The eigengap assumption and strict complementarity
We now turn to discuss our only non-completely standard assumption on Problems (I. which will underly all of our contributions, and in particular will facilitate our local linear convergence rates. Assumption (Main assumption). An optimal solution X to the convex Problem is said to satisfy the eigen-gay gap assumption with parameter 5 > 0. if (
- fX*) 8.
Assumption iin particular implies the following theorem which states that the convex relaxation exactly recovers the unique and optimal solution to the nonconvex Problem ① This is one aspect in which Assumption
! captures "well-posed" instances of Problem (I). The proof is in the appendix.
Theorem 1. If an optimal solution X to Problem 4 satisfies Assumption 2 with some parameter 8 > then it has rank k, i.e., X E Pn and it is the unique optimal solution both Problem and Problem
Assumption is tightly related to the convex Problem through the concept of strict- complementarity. which a classical concept in constrained continuous optimization theory [] A similar connection between eigengap in the gradient at optimal solution and strict comple- mentarity has been already established in [5] for low-rank matrix optimization problems, where the underlying convex set is either the nuclear norm ball of matrices the set of PSD matrices with unit trace. Now we establish a similar relationship for the convex relaxation 4 and the Fantope, which is slightly more involved. Let write the Lagrangian of the convex Problem 4
L(X, Z, Z2, s) f(X) (Z1 X) (Z2, I- ---X8 X s (Tr(X) k),
where the dual matrix variables Z1, Z2 are constrained to be PSD, i.e., Z, 2 0, 2
The KKT conditions state that X*, (Z,, Ziz, 8*) are corresponding optimal primal-dual solutions if and only if the following conditions hold:
= z Dz + s"I X 0, Tr(X*) = k Z ž 0, =0 2. 2.
3. (Z, , IZ, - x") 0.
Condition 3 is known complementarity. Since Zí, Z3 are PSD and 0 3 X* 3 I, this further implies that Zi = =0, Z3 X*) = 0, which turn implies that
range(X") S nullspace(Z))
Lange(I-Xx) S nullspace (Zz))
Definition 1. pair of primal-dual solutions X*, (Zi, ZiiZii f Problem 4 is said to satisfy strict
complementarity, if range X*) = nullspace Z V range(1 (I X*) = nullspace (Zi), which is the
same as: rank(Zi) n rank(X*) rank ZZj
rrankx*)).
Theorem 2. If an optimal solution X for Problem 44h with rank(X*) )- k satisfies strict comple-
mentarity for some corresponding dual solution, then (n-x(V((X)))
- (V (VX()*)) > O. Conversely, if an optimal solution X* for Problem Eb satisfies
( xn==+1((
0, then satisfies strict complementarity for every
corresponding dual solution.
We note that one can also consider projection-base based first-order methods for Problem H such as the projected gradient method, however in general, the projection onto the Fantope F.. will not be low-rank matrix and hence its computation will require expensive SVD computation (see details in the sequel).

---

The proof is given in the appendix. Strict complementarity has played a central role in several recent works, both for establishing linear convergence rates for first-order methods, e.g., [2] g [5], and improving the runtime of projected gradient methods due to SVD computations, for low-rank matrix optimization problems, e.g.,
9
1.2 Additional related work
Efficient gradient methods for low-rank nonconvex optimization have received significant interest in recent years, here we mention only a few. [2 21 gave deterministic guarantees on the local convergence global minimizer of factorized gradient descent for certain low-rank optimization problems, under the mild assumption that a low-rank global minimizer exists. However, these results cannot capture constraints such those in our Problem which encode projection matrices. [ which considers nonconvex gradient methods for low-rank statistical estimation, also considers constraints that cannot capture projection matrices in Problem An exception is specific case they consider of linear objective functions. Moreover, even for linear functions such as the specific sparse PCA objective they consider, their analysis requires several non-trivia conditions hold (e.g. local descent, local smoothness etc), which they only show to hold under Gaussian data.
1.3 Notation
Throughout this work we let ||-|| denote the Euclidean norm for vectors IR and the spectral norm (largest singular value) for matrices in Rm*x or S". We let I|-|I denote the Frobenius (Euclidean) norm for matrices. For a matrix E S", we let (X) denote the ith largest eigenvalue of X. We let ( denote the standard inner- mner-product for both spaces R and S".
Overview of Results
2.1 Main result
Our main novel contribution is the proof of the following theorem regarding the local linear conver- gence of the gradient orthogonal iteration 3 the optimal solution of Problems 4
Theorem 3. [Local linear convergence of gradient orthogonal iteration] Suppose Assumption
?
holds true for some optimal solution X* to Problem 4 with some parameter > Let G supxeF.,,
[X-]]] Consider the sequence (Qr)z1 generated by Dynamics with fixed
step-size Tt = 17 = max for all t 2 1, and when initialized with Q1 E Pn,k such that
QT
X || S min(1, (1, /0l 2(1+n8) Then, we have that
8(1 5(1-1) 40 max G)
VI 11 1: (0000))))000000)000000))0))1)) ((x*) exp
(S(QIQ)
While, as stated above, this is not the first work to consider strict complementarity conditions for bridging convex and nonconvex methods for low-rank optimization, previous works such as B 9 13 consider gradient methods that rely on (nearly) exact (low-rank) SVD computations on each iteration, whereas Theorem considers the more efficient SVD-free Dynamics B.. that requires only a single QR-factorization of an x k matrix per iteration, which is much faster and simpler to implement, Accordingly, the proof is also considerably more challenging and requires new ideas.
2.2 Additional results
We also prove the following two theorems regarding the local linear convergence of the projected gradient Dynamics ( and the Frank- Wolfe Dynamics (5). These extend the results in ( g from optimization over the set of positive semidefinite matrices with unit trace to the Fantope.
Theorem 4. [Local linear convergence of nonconvex PGDJ Suppose Assumption ? holds true for some optimal solution X* to Problem 4 with some parameter > 0. Consider the sequence
(X+)221 generated by Dynamics Q with fixed step-size Tr. 1) 1/3 3 for all i > 1, and when
initialized with X₁ Fn.k such that [X X" X= < 5 Then, for all t > 1 it holds that
43.

---

1. rank( (111 = k and thus, given X, and VX(),)) Xe+1 can be computed via rank-k SVD,
2. f(X)) (OX))-(XX))) f(X*) S - expl -000)))))
Theorem 5. [Local linear convergence of Frank- Wolfe] Suppose Assumption 1 holds true for some optimal solution X* Problem
4
with some parameter 5 > O. Consider the sequences when Ue is chosen via line-search. Then, there exists
{(X,, Ve) generated by Dynamics
To = (k(3/6)²) such that.
Vt 2 To: f(X++1) -(())(() (f(X)) - F(X+)) -f(x))-((()))(
minf
6 1
1
123' 2
Moreover, for all 2 1, the rank-k matrix Vt satisfies || - x 0 182 83 ( ((x)))
-
What if Assumption 1 fails? In case Assumption does not hold or holds with negligible parame- ter 6, not all is lost, since by considering weaker versions of Assumption I which consider eigen-gaps between higher eigenvalues,
can still guarantee that X* (an optimal solution to Problem ④ has low rank, and that at least the projected gradient method (when applied to Problem 4 locally, will require only low-rank SVD to compute the projection onto the Fantope, while guaranteeing the standard convergence rate of O(1/t) (not linear rate as when Assumption
| holds).
Theorem 6. Let X Fn, Js be some optimal solution Problem 4 and let μn 2 F2 ...4An denote the eigenvalues of - vV -XX(""))
Let r be the smallest integer such that 2 k and per - pr+1 > 0. Then, it holds that rank (x) ) < r. Moreover, consider the projected gradient dynamics w.nt. Problem
4 given by, Xi+1 < I [ 8 V- For any r' fr...., 1}, if X - X*Ir S
P.. 11, then it holds that, 4/
1. Vt 2 1, rank(X (x+1) Sr', i.e. given X, and (X(,), X++1 can be computed via a rank-r' SVD.
2. (X+he2 converges with the standard PGD rate: ((x)
- xt))
Remark 1. Note that via the parameter r', Theorem D offfers a flexible tradeoff between the radius of the ball in which PGD needs be initialized in (increasing r' increases the radius), and the rank of the iterates which in lurn, implies an upper-bound on the rank of SVD computations required for the projection, which controls the runtime of each iteration.
Remark 2. Theorem may be in particular interesting when f(-) is subspace-monotont in the sense that for any two subspaces S₁ C S2 S R" and their corresponding projection matrices P1, P2 S", it holds that f(P2) S I) In this case, given an optimal solution X* to the convex Problem 4 with eigen-decomposition X* = =>ie X.u.u, when k < << n, using a projection matrix P -E u.u. which satisfies [(P") S minxxeP,, ((X) may be of interest. For instance, it is not hard to show that f()) of the form f(X) = Ei (1]q. -xqil), where 9i(-) )) is monotone non non-decregiing and { R", subspace-mononee
The complete proofs of Theorems
5 as well as additional results, are given in the appendix.
Below give the main ideas in the proof of Theorem
3
Proof Sketch of Theorem
3.1 Preliminaries
Lemma 1 (Euclidean projection onto the Fantope). Let X E S" and consider its eigen decom-
position X Ei uu.. The Euclidean projection Ny,,, [ is given by: Ty [X] =
Ei=1 75t (0),,u where 7t= (0) E 7, (0) = k. Moreover, Vr E (k..... 1] it holds that rank (X)) S is and
min(max(7 - 0, 0), 1). and A satisfies the equation
only if EL= min(% - 1rr1,1) k. Remark 3. Lemma I iimplies that if rank( X) < r, then only the top r components in the SVD of X needed to compute II [X), iee. rank-r SVD of X. Moreover, given the rank-(r +1) 1) SVD,
can check the condition Ei= min(%; Yrt1, 1) k, to verify whether the projection has rank
5

---

The following lemma lower bounds, under Assumption DI the radius of the ball around the unique optimal solution X inside-which, the PGD mapping w.r.t. the Fantope Fn,& with a fixed step-size, guaranteed to produce rank-k matrices, i.e., matrices in Pr.K. which means that it coincides precisely with the PGD mapping w.r.t. the nonconvex set Pa, given by the Dynamies
Lemma 2. Let X E Fu,k be an optimal solution to Problem 4 which satisfies Assumption
y with 110
some parameter > O, and let 1j > For any X E Fo,k which satisfies
X X 1| S
2(1 + n5)
it holds that rank X V/ (X))) = k.
The following lemma establishes that under Assumption I Problem has a quadratic growth property. This property is known to facilitate linear convergence rates of gradient methods 19 14. Lemma 3 (Quadratic Growth). Let X E Fn, be optimal solution Problem
4 for which
Assumption holds with some å > O. Then, VX E Fr, ||| X S 3 (f(x) f(x)).
3.2 Gradient Orthogonal Iteration Analysis
We outline the proof of our main algorithmic result the local linear convergence result of the
gradient orthogonal iteration 3 given Theorem 3 For convenience, we rewrite the Dynamics ? as Algorithm below which also introduces notation that will be helpful throughout the analysis. Throughout this section we also introduce the auxiliary sequence (X+)221 Fn,K given by: X =
Y1 and X II Y v)Y)) for all 1.
At a high- level, our analysis of Algorithm relies on the following two components:
1. Using Lemma 2 we can argue that, in the proximity of X", rank = k. i.e., X, E Po,k- This implies that X, is the projection matrix onto the span of top k eigenvectors of W.
2. We view Qr as the outcome of applying one iteration of the orthogonal iterations method IT 24 to W, (see also discussion in the Introduction). Combined with the previous point, this allows to argue that Y, = Q Q is sufficiently close to the projected gradient update X,, which drives the convergence.
Algorithm 1 Gradient Orthogonal Iteration
I: initialization: Y1 = Q for some Q1 E Rank such that Q Q1 = II
2: for t = 1, 2... do
3: We+1 < Y, - 17 f(Y,)
4: (Qr+1; Re+1) QR- QR-FACTORIZE W ++1 Q:) (that is Q++1 B W Qa)
5: Yo+1* Q411
6: end for
The following key lemma establishes the connection between the sequence {Y, 121 produced by
Algorithm|] [ and the corresponding sequence of exact projected gradient steps X, J1z1- The proof
relies on original extension of the classical orthogonal iteration method (see [
Lemma 4, Fix some iteration t 2 1. Suppose that < 1/G, X E Pn.k. and [ Yelle <
/2. It holds that, ||x+11
Y
X 1.
-- Y.I7%
[-n
Proof of Lemma
Let us write the eigen-decomposiitonn of W
Y. - (Y())) as:
A
0
W = VAV = IV2
V
A2
V2
where V1 E Bank A1 E k correspond to the largest i eigenvalues.
(V. Q.) ( nG )² | Q.
)2
The main part of the proof will be to prove that | Qe+1l
Note that by definition of X we have that,
X,41 arg min X W
arg mig IX- XeP..k
W++1 arg max W W411) V.VI. (b) XEP...
XeF

---

where (a) follows from the assumption of the lemma that X,+1 E Pu,k, and (b) follows since all matrices in Pn, have the same Frobenius norm. This further implies that
KI
min (V. (V Ae
Σ X: (VV Σ SVV. Vi)
i=1
2 Q.Q. -( - ((--)))(V) Vi) 2 Tr Y,) - (k (6+11
(k- - X 1 Y.1l.) - -(--1)-1-
Y.
(6)
Thus, under the assumption that [X41 - Yolle < V2, we have that (VI Q:) is invertible. Since (Q+11, R(+1) is the QR factorization of Wc+1Qu Qt. using the eigen- seeen-ecomposition of W we can write Q++1R441 = VAV Q. Multiplying both sides from the left by we get,
Q0+1
A 0
Q+
R
V2 Q++1
A2
V
Q
which leads to the two equations:
A V Q. = VT R
(7)
A₂ V Q V. Q.+1
(8)
Under the assumption that 17 < 1//G, using Weyl's inequality have that A (W+1))
2 Aa (Y,))) (V))) > 0, and so A₁ is invertible. Since from (6) we have that miin (V] Q+) >
0, it follows that rank V, Q:) = k and thus, from Equation 7 we have that V Q4+1 and R,+1
are both invertible and we can write R,+1 = (VT Q++1)+++00 V, Q
Multiplying both sides of Equation from the right with R we get
V Q++1= = V2 Q (4)
As V QVTQ).) V.QQH.
Now this to bound [ Q++1 13:
V Q | = || (V Q.) Q
Qull (AL+1(We+1))
(V] (
V
Q
(b) min (V] Q.) Ax
where (a) follows from the inequalities ||A|| < min Bl) A || ||| [
and (b) follows from the eigen-decomposition since VI, Q++1 both have orthonormal columns, it holds that [[V, Q ll2 <
|AB 2| S |||||||| ||//2 [|2
W and by noting that
We upper- upuer-bound bound Ak+1( (W+1)/A&(WA
by using Weyl's inequality as follows:
X (W4+1) X + -A(V/((X))) 1 1-nG n/3¹ (Y, + (-V((X)))
76
(W(W)) <
(10)
where we have used the fact that Y, E Pr, and so \ (Y,) = (.)+1((,))))) 0. Plugging
10 into
indeed obtain,
G/
IIV Q 11
( n/G
(11)
2 min (V.
Now, for the final part of the proof, we note that V Q VV
Tr( X k ( X Y l and similarly, JIV Qdl
[| Y. Plugging these observations and into I1
we obtain the lemma.
The following lemma is the main step in the proof of the convergence rate of Algorithm
7

---

Lemma 5. Let us denote h4 = f({); f(X') for all t 2 1. Fix some iteration of Algoritium
and suppose that 17 S max[2;c]] X,+1 Pak. and that [X++1 Yellr 1. Denote the constants
Co Co= - 2 2 n
T-y
2
nó C 1-2n8 2Co(1+)))) It holds that, he41 S (1 4(1+0:)
has where ō > 0 is
the constant from Assumption 0
1
Proof. Using the B-smoothness of f(X), for any X E Fr, and $ it holds that
f(x) - f(Y,) + X Y, Vf(Y.) + 2n
X Y.ll?
00 f(X)) + (X Y, Vf(Y.)) -1 (Y,, Y. X)
= =(Y)) "Y, X, Y, - -V(Y))
(12)
where (a) follows since using the fact that Y, E Pn,k. we have that for any E Frn it holds that |X| - k Y. (Y,, Y.).
Since X,+1 II,,,. - -)V]((Y)] arg minxeF, |X - (V))) and by the assumption of the lemma that X,-1 E Pn,,., using the first-order optimality condition, it can be shown that for all E FR,K: (X++1 - 2, Y, T/e (VY)() 2 0, see Lemma
This implies that for
all Z E Fr,k:
(Ye+1, Y. (VV((Y)) (X++1, Y, ,)(()))) (X+11 1in1-Y-1 Y Y. -
2
(Z, Y. -VS()) - (X++1 - YAI1 -.-Y,,VVV. ,VV)(Y)) 2
(Z. Y, -Vf(())) || - -1++
(13)
where the last inequality is due to Lemma 8 which uses again the facts that X.+1 E P and X,+1
argminxe.... 1X-(Y= (Y, n I which in turn imply that X arg maxxeP..... (X, Wr+1), and recalling that W = Y, (VY,).(..)
Setting X = Y,+11 in 12) and plugging-in
we have that for any Z E Fr, it holds that,
((Y++)) - f(Y,) + ((Y, Z, ((Y))) + [X+11 Y 112 (W++all))
= f(Y,) + (Z Y,-Y, Vf(Y.) + _ Z Y.1.
1
X Y 11: | Wetall
21
1
1 + n/
f(Y,) + (Z - Y. vf(Y)) + 21j
7 - 11 +
|X+1 - Y 1 (14)
"
where the last inequality is due the following upper-bound WW+1l12: |W ||2 |Y: 7)VS())))l S Yr|l2 + /X lla $1+10 1+ In partieular, setting Z (1 Y, + +xx* " for some a E [0, 1]. we get that
1 + n/
f(Y++1) S f(Y)) + a Y. Vf(Y))
X Yell.- +
X - Yo+1l??.
2n
Subtracting f(X*) from both sides, using the convexity of f(-), and Lemma 3 gives
h & 811 a1-a+ a
1 nG
170 h +
X - Y.
Setting a = n202 (note that since S 1/G, we have that a E [0, 1)), gives
het1 < (1- 110 h +
1 1 nG
X
(15)
We now continue to upper-bound the term [X,+1 Y 13. Using Lemma 9 which apply standard arguments in the analysis of first-order methods, that rely only on the facts that X,+1 = =I,,,, Y, v/ f(Y)) and that f.) is smooth and convex, we have that
X Y.
n3 1- (U(Y.)-((x++))
(16)
8

---

Let us set Z = X(41 in 14
to obtain that
+ X141 - Yell? 1 +
((Y(1) 1 f(X)) + (x+1 Y, vf((.))
X - Y44111
21)
|X Yell,+ + 1 n
S 5((++1))
|X Y441l1
2n
"
where the last inequality is due to convexity of f(.). Rearranging and using Lemma A along with the notation Co
nG
we have f(X++1) 2 f(Y++)) - - + Co(1 + n/G)) |X Yell?.
1-nG
Plugging into
16 we obtain
X Y, S n3 ((X.))((X++1))
7
1 ( Co(1 + n(6)) -
Y.113)).
and rearranging obtain
21/(11 - 11+1)
X Y.
<
1- n3 (J(Y,) ((+++1) 2(1 17,3) 2Co n/))
(++c0(1+7 18)
Using Lemma again we have, [| - Y(+1 1|3
1-2n8 2Co(1+nG] (h: h2+1). Plug
2nCh
ging back into 15 we obtain ho+1 < (1 ná
hes + T T-2 (1+ (/v: - -/441). Denoting
2(1+nG)Cs
C1 T-2n3 3 (Ca we finally obtain h4+1 S 1+ (1 rf + Ci h: (1
2(1+nG)CC
178
l1,, as
x(1+C1)
required. The only thing left is to choose a feasible step size. We have to require: - 211.3 - 2C (1-
n/))= > 0. The latter holds for any max
4 Numerical Simulations
Due to lack of space, some of the implementation details and results are deferred to the appendix. We consider two models for robust recovery of low-dimensional subspace from noisy samples: spiked covariance model, and 2. sparsely corrupted entries model. In both models we minimize robust loss based on the Huber function, which is convex and smooth, over the Fantope. We generate random instances and solve them to high precision (duality gap < 10-10) and take the resulting point X as the optimal solution. We measure the eigen- gap in V VX(*) (as Assumption compare the recovery error w.r.t. the naive PCA solution X PCA which simply computes the leading subspace of the empirical covariance. The results are given in Table [ For both models the recovery error is significantly lower than that of naive PCA, which demonstrates the usefulness of the chosen models. We see that the eigen-gap gap assumption indeed holds with substantial values of
D and we
Noise prob.
0.05
0.1
0.2
0.3
0.4
0.5
J. Model I: spiked covariance 4
Eigen gap (d)
3.21
2.87
2.36
2.04
1.501
1.03
|X
P|[
0.0047
0.0075
0.012
0.016
0.022
0.0298
XPCA P
0.045
0.072
0.115
0.157
0.212
0.292
1 Model 2: sparsely corrupted entries J.
Eigen-gap (8)
5.72
5.49
5.15
4.81
4.38
3.79
|X
-Plle
0.049
0.067
0.097
0.111
0,134
0,148
|XeC P|
0.148
0.199
0.291
0.335
0.401
0.439
Table 1: Recovery and eigen-gap results for the spiked covariance and sparsely corrupted entries models with varying noise probabilities. P is the projection matrix onto the ground truth subspace. n 100, k = 10, sample size m 500. Results are averages of 20 i.i.d. experiments.
We additionally test the empirical convergence of nonconvex PGD (Dynamics 2 and the gradient orthogonal iteration method (GOI, Dynamies (3) on the two models. We initialize both methods with the PCA solution X XPCA and use the same fixed step-size for both. We examine the convergence

---

of both methods in terms of recovery error and approximation error (W.... the objective function). Additionally, to showcase the benefit of avoiding exact SVD computations (as employed by non- convex PGD) and using only single QR factorization per iteration (as in GOI), we compare the runtimes of GOI and nonconvex PGD, but we exclude the time it takes to compute the gradient on each iteration and only account for the time it takes to perform either rank - k SVD factorization, where both algorithms were implemented in Python and we have used the built-in functions TUMPY. EIGII and NUMPY.LINALC QR to compute thin-SVDs and QR factoriza- tions, respectively. Finally, we verify during the run of nonconvex PGD, that on each iteration, the projection onto Pu, is indeed the same the projection onto the Fantope Fr,k (see Remark 3 which suggests that nonconvex PGD indeed converges to the global minimum.
QR
The results for the spiked covariance model are given in Figure I (the results for the sparsely corrupted entries model are very similar and given in the appendíx). It can be seen that indeed the distance between the iterates of the two methods decays very quickly and so the graphs of the recovery and approximation errors of both methods coincide. We see that both methods demonstrate a linear convergence rate (w.rt. the objective). We also see the significant savings in runtime when replacing a thin-SVD computation (in nonconvex PGD) with only a single QR factorization (in GOI).
LoS sopros earor
601
Log spprox, 8
0.33
30
2 0.2
IX
Iteration
Heration
TeecSocons)
Figure 1: Convergence of PGD and GOI for the spiked covariance model with p 0.1. 1st and 3rd panels from the left show the recovery error (P is the ground truth projection matrix) and approximation error w.r.t. objective value of PGD, respectively. Convergence of GOI is omitted since it coincides with that of PGD. 2nd panel from the left shows the distance (in Frobenius norm) between the iterates of PGD (X,) and those of GOI (Y,). The rightmost panel shows the approximation error (in log scale) vs. time, when only the time to compute matrix factorizations is taken into account.
Importance of warm-start initalization: We examine the performance of nonconvex PGD over Pr, (Dynamics ( for the spiked covariance model considered above, but this time, when initialized with a random (uniformly distributed) projection matrix. We compare with convex PGD which optimizes over the Fantope Fa, and uses a full-rank SVD to compute the projection. We use the same step-size as before. We see in Figure 2 (right panel) two trends. First, we clearly see that PGD w.r.t. P.,,k and Fr, produce very different iterates which in particular implies that, as opposed to the case of warm-star initializaion, the projections of convex PGD onto the Fantope, throughout most of the run are not rank-k. Second, we see that nonconvex PGD is significantly slower than convex PGD. Thus, while both methods eventually converge to the same error, this suggests that far from a global minimizer, the behaviour of nonconvex gradient methods is indeed significantly different than in the local proximity of one, which supports the fact that our theoretical guarantees only hold local neighbourhood of a minimizer.
Full -ank SVD Rankiik SVD
Objective value
7,005
Objective value
303
7,000
20
100
Figure 2: Convergence of PGD for the spiked covariance model with p = 0.1 over the Fantope F,,,k with full-rank SVD, and over Pr.,k with rank-k SVD, when initialized with the PCA solution (left panel) and with random initialization (right panel). In the left panel the plots exactly coincide.
Acknowledgements
This research was supported by the ISRAEL SCIENCE FOUNDATION (grant No. 2267/22).
10

---

References
[1] Farid Alizadeh, Jean-Pierre Haeberly, and Michael L. Overton. Complementarity and nonde- generacy in semidefinite programming. Mathematical programming, 77(1):111-123 1997.
[2] Srinadh Bhojanapalli, Anastasios Kyrillidis, and Sujay Sanghavi. Dropping convexity for faster semi-definite optimization. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume Proceedings of Machine Learning Research, pages 530-582, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR.
[3] Sébastien Bubeck. Convex optimization: Algorithms and complexity. arXiv preprint 40X 2014.
[4] Yudong Chen and Martin Wainwright. Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv preprint arXiv:1509.0300 1500000099, 2015.
[5] Lijun Ding, Yingjie Fei, Qiantong Xu, and Chengrun Yang. Spectral frank-wolfe algorithm: Strict complementarity and linear convergence. In International Conference on Machine Learning, pages 2535-2544. PMLR, 2020.
[6] Dmitriy Drusvyatskiy and Adrian Lewis. Error bounds, quadratic growth, and linear conver- gence of proximal methods. Mathematics of Operations Research, 43(3):919 948, 2018.
[7] Ky Fan. On a theorem of weyl concerning eigenvalues of linear transformations Proceedings of the National Academy of Sciences of the United States of America, 35(1 1):652, 1949.
[8] Dan Garber. Linear convergence of frank-wolfe for rank-one matrix recovery without strong convexity. arXiv preprint arXiv:19/2.01440 2019.
[9] Dan Garber. On the convergence of projected-gradee methods with low-rank projections for smooth convex minimization over trace-norm balls and related problems. SIAM Journal on Optimization, 31(1):727-7533 2021.
[10] Gene H Golub and Charles F Van Loan. Matrix computations. johns hopkins studies in the mathematical sciences.
[11] Moritz Hardt and Ankur Moitra. Algorithms and hardness for robust subspace recovery. In Conference on Learning Theory, pages 354-375. PMLR, 2013.
[12] Martin Jaggi. Revisiting fralk-wolff: Projection-Fie free sparse convex optimization. In Interna- fional Conference on Machine Learning, pages 427-435. PMLR, 2013.
[13] Atara Kaplan and Dan Garber. Low-rank extragradient method for nonsmooth and low-rank matrix optimization problems. Advances in Neural Information Processing Systems, 34, 2021.
[14] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewic. condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795-811 1. Springer. 2016.
[15] Andrew J Landgraf and Yoonkyung Lee. Dimensionality reduction for binary data through the projection of natural parameters. Journal of Multivariate Analysis, 180: 14668, 2020.
[16] Gilad Lerman and Tyler Maunu. Fast, robust and non-convex subspace recovery. Information and Inference: A Journal of the IMA, 7(2):277-336, 2018.
[17] Gilad Lerman and Tyler Maunu. An overview of robust subspace recovery. Proceedings of the IEEE, 10808);1300-1410, 2018
[18] Tyler Maunu, Teng Zhang, and Gilad Lerman. A well-tempered landscape for non-convex robust subspace recovery. Journal of Machine Learning Research, 20(37), 2019.
[19] Necoara, Yu Nesterov, and Francois Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical PropaatiiiaPPPPraaaina Programming, 201,,

---

[20] Michael L Overton and Robert S Womersley. On the sum of the largest eigenvalues of symmetric matrix. SIAM Journal on Matrix Analysis and Applications, 13(1):41-45 1992.
[21] 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):2165 2204,, 2018.
[22] Prasad Raghavendra and Morris Yau. List decodable subspace recovery. In Conference on Learning Theory, pages 3206-3226. PMLR, 2020.
[23] Mostafa Rahmani and George Atia. Randomized robust subspace recovery and outlier detec- tion for high dimensional data matrices. IEEE Transactions on Signal Processing, 65(6):1580- 1594, 2016.
[24] Yousef Saad. Numerical methods for large eigenvalue problems: revised edition. SIAM, 2011.
[25]
Ohad Shamir. Fast stochastic algorithms for svd and pea: Convergence properties and convexity. In International Conference on Machine Learning, pages
PMLR, 2016.
[26] Vincent Vu, Juhee Cho, Jing Lei, and Karl Rohe. Fantope projection and selection: near- optimal convex relaxation of sparse pea. Advances in neural information processing systems, 26, 2013.
[27] Yi Yu, Tengyao Wang, and Richard Samworth. A useful variant of the davis -ahann theorem for statisticians. Biometrika, (02(2):315-325 2015.
[28] Dejiao Zhang and Laura Balzano. Global convergence of a grassmannian gradient descent algorithm for subspace estimation. In Artificial Intelligence and Statistics, pages 1460-1468. PMLR, 2016.
[29] Zirui Zhou and Anthony Man-Cho So. A unified approach to error bounds for structured convex optimization problems. Mathematical Programming, 165(2):689-72)) 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] The details in the experimental section allow to reproduce the results exactly
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
12

---

(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "ueK5JRbsiQV", "reviewer": "Reviewer_tL19", "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. ", "questions": "A small question, how to choose $k$ in practice?\n\nThe paper is not well-written overall, and the authors should polish the paper thoroughly. \n - line 5, what does \"among others\" mean?\n - line 7 \"or ,\" to \", or\"\n - line 12, the whole sentence \"Our result ...\" i guess needs rephrase.\n - line 24 \"include among other...\"\n - For the footnotes, please unify the starting letter in capital. \n - line 34\"] however\" to \"]. However\"\n - \"aka\" to \"a.k.a.\"\n - line 59 \"efficient implementation of will...\", of what will?\n - line 81, \"(2))\" and \". $^3$\"\n - line 188 $X \\in \\mathcal{F}\\_{k}$, should be $\\mathcal{F}\\_{n,k}$?\n - page 8, Lemma 6,8,9 are not appear in the main paper.", "limitations": "Not applicable here. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nTo me, there are several limitations of the obtained results:\n - 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?\n - 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.\n - Lemma 3 the \"quadratic growth\" assumption basically is the weaker strong convexity assumption, the authors should discuss its connections/differences compared to existing approaches. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "sLucwT_3DJ", "reviewer": "Reviewer_mnGb", "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.\n\nThe 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).\n\nThe 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.\n\nAlmost 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).", "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?\n\n2. Can fixed points of iterations (3) be described in some simple way, such as a closed formula?\n\n3. 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?\n\n4. 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.\n\n5. 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.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is an interesting formulation of the low-rank method, which requires only one QR (rather than SVD) factorization per iteration.\n\nThe theoretical analysis is interesting. However, its novelty is only incremental, given the prior work [5] and [8,9].\nMoreover, 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.\n\nThe 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.\n\nThe 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.\n\nIn 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.\n\nMinor remarks:\n- 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.\n- I'd use a different symbol than \\partial for the total derivative in (3), such as {\\rm d}.\n- Typo in Lagrange function below line 101, (X) should be f(X).\n- In Definition 1, I believe that disjunction (\\vee) should be conjunction (\\wedge).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dm8i53cfXko", "reviewer": "Reviewer_Lsrb", "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.", "questions": "\n(${\\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. \n\n(${\\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?\n\n$\\textbf{Attouch and Bolte (2009)}$: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming, 116(1), 5-16.\n\n(${\\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", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\n(${\\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.\n\n(${\\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. \n\nWeaknesses: (${\\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]. \n\n(${\\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. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GAE9tE7Dixe", "reviewer": "Reviewer_FuJo", "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. ", "questions": "no", "limitations": "Not applied.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\nThis paper studies a general setting of k-dimensional subspace problem. The local linearly convergence under strict complementarity is interesting.\n\nWeaknesses:\n1. The symbol << is not standard, please use $\\ll$ (\\ll) instead\n2. To use the KKT conditions, the slater's condition should be verified though it is obviously satisfied if k<n. \n3. The numerical experiments do not show the linear convergence, since the linear convergence rates are  important results in this paper. \n4. 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. \n\nLiu, 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept