Oja's Algorithm for Streaming Sparse PCA
Authors: Syamantak Kumar
Purnamrita Sarkar
Venue: NeurIPS 2024 poster (2024)
Keywords: Streaming PCA
Oja's Algorithm
Sparse PCA
Support Recovery
Entrywise Bounds
Primary area: optimization
TL;DR: We give a O(d) space, O(nd) time algorithm for Streaming Sparse PCA via a novel analysis of Oja's Algorithm followed by thresholding

Abstract: Oja's algorithm for Streaming Principal Component Analysis (PCA) for $n$ data-points in a $d$ dimensional space achieves the same sin-squared error $O(r_{\mathsf{eff}}/n)$ as the offline algorithm in $O(d)$ space and $O(nd)$ time and a single pass through the datapoints. Here $r_{\mathsf{eff}}$ is the effective rank (ratio of the trace and the principal eigenvalue of the population covariance matrix $\Sigma$). Under this computational budget, we consider the problem of sparse PCA, where the principal eigenvector of $\Sigma$ is $s$-sparse, and $r_{\mathsf{eff}}$ can be large. In this setting, to our knowledge, *there are no known single-pass algorithms* that achieve the minimax error bound in $O(d)$ space and $O(nd)$ time without either requiring strong initialization conditions or assuming further structure (e.g., spiked) of the covariance matrix.
We show that a simple single-pass procedure that thresholds the output of Oja's algorithm (the Oja vector) can achieve the minimax error bound under some regularity conditions in $O(d)$ space and $O(nd)$ time.  
We present a nontrivial and novel analysis of the entries of the unnormalized Oja vector, which involves the projection of a product of independent random matrices on a random initial vector. This is completely different from previous analyses of Oja's algorithm and matrix products, which have been done when the $r_{\mathsf{eff}}$ is bounded.

Oja's Algorithm for Streaming Sparse PCA
Syamantak Kumar'
Purnamrita Sarkar2
Department of Computer Science, UT Austin
Departmentt of Statisties and Data Sciences, UT Austin syamantak@utexas. edu, purna. sarkarCaustin utexas edu
Abstract
Oja's algorithm for Streaming Principal Component Analysis (PCA) for data- points in a dimensional space achieves the same sin-squared error Ofret/n) as the offline algorithm in O(d) space and (nnd) time and single pass through the datapoints. Here Teff is the effective rank (ratio the trace and the principal eigenvalue of the population covariance matrix Σ). Under this computational budget, we consider the problem of sparse PCA, where the principal eigenvector of Σ is s-sparse, and reff be large. In this setting, no known single-pass algorithms that achieve the minimax error bound in (d) space and ((nd) time without either requiring strong initialization conditions assuming further structure (e.g., spiked) of the covariance matrix. We show that simple single-pass procedure that thresholds the output of Oja's algorithm (the Oja vector) can achieve the minimax error bound under some regularity conditions (dd) space and O(nd) time. We present nontrivial and novel analysis of the entries of the unnormalized Oja vector, which involves the projection of product independent random matrices on random initial vector. This is completely different from previous analyses of Oja's 's algorithm and matrix products, which have been done when the reff bounded.
knowledge, there are
Introduction
Principal Component Analysis (PCA) [Pea01 [o103] is classical statistical method for data analysis and visualization. Given a dataset (Xth= where X; E RR,, sampled independently from
distribution with mean zero and covariance matrix Σ, the goal in PCA is to find the directions that explain most of the variance in the data. It is well known [Wed72] JJK 16, Ver10 that the leading eigenvector, ô, of the empirical covariance matrix, E, provides an optimal tail conditions on the datapoints.
rate under suitable
Computing è can be inefficient for large sample sizes, and dimensions d. Oja's algorithm Oja82a offers a comparable error rate in ((nd) time and O(d) space. Going back to the Canadian psychologist Donald Hebb's 's research [Heb49] it has attracted lot of attention in theoretical Statisties and Computer Science communities (JK+ 16 AZL17 CYWZ18) YHW18 HW 19a HNW21 MP22
Mon22 Mon22 HNWW21] In these works, the error metric is the sin' 2 error between the estimated vector and the principal eigenvector of Σ (true population eigenvector v1). Notably, [JJK 16), (ZL17), and (HNW21] establish that Oja's algorithm achieves the same O /T) sin-squared error as the offline algorithm that estimates the top eigenvector of the empirical covariance matrix.
However, when the effective rank, relr. of Σ (defined as Tr(E)/ ||E| is large, PCA has been shown to be inconsistent [Pau07] JM09, [L09]. This setting comes up in sparse PCA problems, when 81 is s-sparse (i.c. has only nonzero entries). Let |I-llo denote the to norm, i.c, the count of non-zero vector entries. Then, sparse PCA can be formally framed as the optimization problem:
D Spaase :=
arg max wERd
Σ (x
under constraints
||w|| = 1, ||l]o =
(1)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Sn-oquared Enror with Timestops
Dary faymiie di Becker Thesk wit Dle)
03
01
Timestepo
(a)
Figure 1: Comparison of Sparse PCA algorithms for identifying Ieading eigenvector, v1, operating in O (d)
space and O (nd) time with population covariance matrix specified in [QLR19]. Section 5.1. Figure (a) plots [1009 (Purple), [XXIS (Black), [WL16] (Orange) and our proposed Algorithm 2 (Blue) for d = 1000, with error bars over 100 random runs. Figure (b) shows an image of the covariance matrix with d 100.
In general, without further assumptions, Problem IT is non-convex and NP-hard [WA066] as reduces to subset selection in ordinary least squares regression.
VL12 CMW13) showed a O (a²s log (d) /n) minimax lower bound for the sin? error 1 (v ?)
where o² = Ands - Here Å > 22 2 .. are the eigenvalues of Σ. Extensive research has
been conducted on optimal offline algorithms for sparse PCA, some of which are convex relaxation- based [RR3 dBEGO8 VCLR13 (SLO77 ZX18 DMMW17 AWO8 Ma13 CMW13) Others
involve iterated thresholding [JNSSIO Ma13 YZ13, where truncated power-method is analyzed along to achieve sparsity. For brevity, we only describe algorithms that fit within the computation budget in consideration, i.e., (nd) time, O (d) space. For detailed comparison, see Table and Appendix Section A.
Support recovery algorithms in (nd) time, O(d) space: Consider the spiked covariance model
Σ Σ Maaa + la
sE|r]
where la is the identity matrix, vs > 0, and v, are sparse. For the general case, we only assume Vi is s-sparse. When r = 1, Ex are the largest for i E 5. Diagonal thresholding essentially estimates E; within our computational budget and uses thresholding to recover the support [J109) AW08). However, as we will show, without knowing the support sizes in each eigenvector and the number of spikes, this algorithm can fail, even in a spiked setting with r > 1. Also, for r = 1, [BPP18] show how to adapt black-box algorithm for sparse linear regression for support recovery.
Sparse PCA algorithms in (nd) time, O (d) space: The streaming sparse PCA algorithms proposed by [XX15] and [WL16] require an initialization with a sufficiently large [u 01 Ω (1)
(local convergence), which can be hard to find for large and a general Σ. See Table I for details.
In light of this lack of ((d)) time, ((d) space globally convergent algorithms for sparse PCA, we ask the following question in this work:
Goal: Is there a single-pass algorithm that, under a general Σ with s-sparse U1, outputs achieving the minimax sin? error (1 (1)))) with O(d) space. ((n)) time, without strong initialization?
We provide surprisingly simple answer to the above question:
Theorem 1.1 (Informal). For suitable range of the effective rank Teft and the ratio X X2, there exists a single pass algorithm A that recovers the support of 01 using Oja's 's algorithm, operates under (d) space, (nnd time and returns i with the minimax optimal sin? error, O (o?3 log (d) //n,for a general covariance matrix.
2

---

Our contributions:
1. I.Suport recovery: We show, for general E with the only constraint of s-sparse oo that the top entries of the Oja vector in magnitude include the true support with high probability. The Oja vector is initialized by random unit vector.
2. Sparse PCA: We use the recovered support to achieve a minimax optimal sparse PCA algorithm.
3. Entrywise analysis: Our analysis is nontrivial and novel because it deviates from existing analyses of matrix products and streaming PCA [HNWTW20 [W [SW21 Lia23 which require
/x or Teff to be bounded obtain the O(1/n) sin error rate.
Paper(s)
\1/Xo
Σ
Global
Space
Time
sin error
conv.?
Johnstone and Lu [L099]
I+o
Spiked
(d)
(nd)
(1)
s log (d)
SDP-based
VCLR13
1 (+)
General
(d=)
(n d
n
dBEG08
Shen et al. [SSM13]
((d)),c 0
General
Y
O(d²)
O
o(1)
log (d)
Ma, Cai et al. MM11
1+2(1)
Spiked
O (de)
O (nd²)
O
[CMW13)
log (d)
Yuan and Zhang YZ13
1+0(1)
General
N
O (d?)
o (nd?)
O
n
log (d)
Yang and Xu YX15
(1)(1)
Spiked
N
O (d)
0 (nd)
Wang and Lu [L16
(1)
Spiked
(d)
(nd)
o
(1)
Oja's Algorithm 16)
(1)
General
O (d)
(nd)
'eff
s" log (d)
Deshp et al. [DM 16
1+)
Spiked
o (d')
(nd²)
n
s" log (d)
Qiu et (Cor 2) [QLR99
1 o1)
General
o (d')
(nd?)
n
d² log (d) /n log (d)
Qiu et al. (Th. 4) [QLR19)
1 +1)(1)
General
o (d')
(nd²)
Gataric al. (Th. 2)
11
Spiked
O (d²)
(nd2)
n
(GWS20
log (d)
Our work
+ (1)
General
Y
O (d)
O (nd)
O
Table Comparison of sparse PCA algorithms for estimating U1, based on various parameters. We require Assumptions
I and
2
The other algorithms may be valid under weaker assumptions. For ease
of comparison, fix A
Ω (1) and Fer log(n) O (1) for results in this table.
Xa
n
In Figure Ib for a simple spiked model with r time and O(d) algorithms in Table Our thresholded and renormalized Oja algorithm outperforms all other algorithms operating under the same computational budget. The diagonal thresholding algorithm ( (JL09),, which is successful for the special case of r 1, has large error in the general case.
show the relative performances of all (nd)
We now present an outline of our paper. We start by describing the problem setup and assumptions in Section 2 Then we present our main results in Section 3 which includes results for Support
'The authors do state the runtime explicitly. The algorithm, stated, requires least ((nd") computation.
TTe authors require \1/A2
O(v log d/n)
When there are m spikes, Thm 2 of [GWS20] requires A = 2 order, storing the empirical covariance matrix is computationally more efficient.
( t dl log(d). When and on are the

---

Recovery (Section B.1. Sparse PCA (Section 3.3) and Entrywise Deviation bounds (Section 3.5 for the Oja vector. Finally, we provide sketch of the proof along with the techniques used in Section
Problem setup and preliminaries
Notation. We use E to denote expectation and [n]] for [I....,n}. The matrix multiplication constant denoted as 2.372. X TL represents statistical independence between random variables X and Y. The E² norm for vectors and operator norm for matrices is I1-ll2- the count of nonzero vector elements (E" norm) is Il-lly- and the Frobenius norm for matrices is II-lI For E Rd, R S [d], [UJR E R is the truncated vector with entries outside R set to O. Ia E Rdxd is the identity matrix, with jth column e; E Rdx1 For any set T S [d], 4r E Rgddd is defined as Ir (1,5) [ E T) = j), where 1()) is the indicator random variable. (A, B) = Tr(A" B) represents the matrix inner product. Ô and f represent order notations with logarithmic factors. We start by defining subgaussianity for multivariate distributions.
Definition 2.1. A random mean-zero vector X Ted with covariance matrix E is a ouo--uubuusssa random vector (a 0) if for all vectors E Rd, we have E (exp (v" x) I exp (o 2v/2).
Equivalently, 3 L > O, such that Vp [E 1 X Vo
This definition of subgaussianity has been used in contemporary works on PCA and covariance estimation (See for example (MZ20] JLT20 DKPP23] and Theorem 4.7.1 in [Ver1)). We operate under the following two assumptions, unless otherwise specified,
ULT20
Assumption (Subgaussianity). (Xilie(m) are of independent and identically distributed a- subgaussian vectors IR with covariance matrix Σ == E [X,X7].
We denote the cigenvectors of D as U1, U- and the corresponding eigenvalues as b > A 2 Xd- Define V1 == [02, u3. ... val E (d-1) and A2 E R (d- (dd-1)x(d-1) = diag (A2, λ3, Ad).
Assumption 2 (Sparsity and Spectral gap). We assume that max
Tr(Ag) I log(ns and A1-A2
- S /c/ (nj for absolute constant > 0. The leading eigenvector, U1, satisfies ||0|lo S A
with support set S {i: 81 (i) + 0}.
Remark 2.2. We note that Assumption allows for ret to be as large as d, given a sufficiens eigengap. This can be observed by setting A = A2(1 + 9n,) for some In > O. Note that Tr(Aa) X d I
min ++ reff 1 t.d). If gn. S then,
max 1, In d1 x2
Tr(A2)
< 1
11 In
(1 (1+ gn
min
Teff; -d
2 2 min
Teff
d
$ 2rett/ 92
In In
In
In
2gn.
2gn
If gn > 1, then,
1 Tr(22)
Tr(A2)
max
_
gn. A
X2
A2
In
therefore, both cases, as long as d < to hold.
n8e. logn' Feff can be as large as d, while allowing for Assumption
Oja's algorithm with constant learning rate. With a constant learning rate, 7), and initial vector, up. Oja's algorithm [jj882b), denoted as Oja ((Xthee)) n,, u.). performs the updates, u4 + For convenience of analysis, we also define VI E [n]. 1
(I + xxxxX
ue-1; Wt
Be
B = (I= (I+ -x----1X]]) ... (. (I+ Bo= =I
(3)
'The results developed in this work follow if instead of subgaussianity, the moment bound holds p p 8.

---

3
Main results
We present our main contributions in two stages. Firstly, in Section we demonstrate that with an upper bound on the support size, the top elements of the Oja vector include the support with constant probability, which can be enhanced using boosting procedure (SuscessBoost) described in Section 3.4] Secondly, in Section 3.3 we use the support to extract the eigenvector and provide a
sin² error guarantee. Section 3.5 details our results on bounding the entrywise deviation of the Oja vector, which are crucial to our proofs and of independent interest. Detailed proof's are in the Appendix, Sections A.4 and A.5 with the learning rate, 17, specified in Lemma A.2.4
3.1
Support recovery
Algorithm 1 OjaSupportRecovery (EX) kk.))
1: Input: Dataset (Xi)ee(n) Cardinality parameter k: 2 8, learning rate rj > 0
2: N (0.
3: 0 + Oja ((Xi)ie(m) 77, .7.30)
4: 3 Indices of & largest values of [6]
5: return
Algorithm 1 provides an estimate, 3, of the true support set, S. It computes the Oja vector and returns the set of indices corresponding its k largest entries in absolute value. Our key result in Lemma 3.1 discusses the recovery of the support set, S, for any k 2 s, without requiring exact knowledge of the it provides set S 2 S with probability at least 0.9.
sparsity parameter s. Using Algorithm 1
Lemma 3.1 (s-Agnostic Recovery). Under Assumptions 2 for min; ln (i) 5
A
A
nz
3log(n) S + OjaSupportteecoerr ((X))sEmm) k, == m(A1->a) with k 2 satisfies, P (S S
> 0.9.
If A s, i.e, the size of the support is exactly known, then we can improve the result of Lemma 3.1
to obtain an estimator, 3, of the support set with high probability. Theorem 3.2 provides the corresponding guarantees. The SuccessBoost algorithm uses geometric aggregation on subsets returned from A rrun on log(1/5) disjoint subsets of the data and is described in Section 3.4
Theorem 3.2 (High probability support recovery). Let Assumptions 7 hold. For dataset D = {Xilie(m) let A be the randomized algorithm which computes S +
OjaSupportRecovery ((X))sem)) k. where 7
3 3log(n) "n(1-AA and k = Then, for d (0, 1),
min; |on (i)l 5
\> ( S +- SuccessBoost ( ((Xi)sefa) A..)) satisfies,
P S)
For comparison, existing support recovery algorithms for general E are known for convex-relane -onvex-relxxation- based algorithms like the SDP-based algorithm of [LV15). These require much larger computational budget than ours. In Section 3.3 we show how to use the s-agnostic support recovery in Lemma [31] to perform Sparse PCA and obtain sin? 2 error guarantee, where the final high probability error bound obtained using similar probability -obabbiittyboootingg argument. For the learning rate, we follow the convention in related work ([BDF13) XHS* 18 JJK+16 AZLI7 HNWW21] and choose the optimal value of the learning rate, which requires the knowledge of a - Ag. We believe an educated guess of 7 would lead to consistency at the cost of suboptimal error bound.
3.2 Comparison with other support recovery algorithms
We note that (see Table [p. for the spiked model with r (Eq 2 JL09 and AW08 provide diagonal thresholding algorithm for support recovery using O (d) space and O (nd) time
To achieve
a high-probability guarantee for the estimated support set, S. of the form PP ($=S) > 1 - ó, they
'The algorithm proposed in AW08 allows for slight generalization of the spiked model in Eq 2
5

---

require (Proposition 1, (AW08) T2 = S2 (s² log (d) + log (t)). In comparison, Theorem 3.2 requires larger sample size.
Remark 3.3. In practice, will not know whether E is spiked general. So, can always augment our support recovery algorithm by taking a union of the support from the Oja vector and diagonal thresholding. still maintaining (nd) time and (d)) space.
However, diagonal thresholding only works for the spiked model with a single spike, which our results do not require. It is easy to construct a E where the elements in the support of an eigenvector with a small eigenvalue have a larger magnitude than those of e1 (Eq A.13). Here the diagonal thresholding method fails (see Figure Ta and Proposition 3.4) The explicit construction and the proof of Proposition 3.4 are available in the Appendix Section A.2 Figure a) plots the sin error due
to difffrent Sparse PCA algorithms operating in O (d) space and O (nd) time on such a covariance matrix, 2, which is visualized in Figure a).
Proposition 3.4 (Lower bound for diagonal thresholding). Let Assumption hold. For any diagonal- thresholding algorithm, A. performing support recovery with sparsity parameter such that n Q (o 2² log (d)), there exists covariance matrix E with principal eigenvector, vi, ||ollo such that, IP S =
d0
may seem that if r in Eq 2 is small, and the sparsity parameters of each Us S r are known, then diagonal thresholding would work. However, in general, can be as large d and the union of supports of by can be [d].
3.3 Sparse PCA
In this section, describe our results for Sparse PCA, which use the support recovery guarantees developed Section 3.1 For the results in this section, we split the dataset D = (X))ie()) into two halves and estimate the support using the first half as <
3 3log(n) OjaSupportRecovery ((Xi)se()) k, n(A: X2) and input, 2 s. The second half of the samples are then used to compute the estimated sparse eigenvector. Algorithm Deeteibbes general procedure for Sparse PCA given access to estimated support set, S. We start with an intuitive procedure in Theorem 3.5 which runs Oja's algorithm on the data and then uses the support to truncate the estimated eigenvector.
Algorithm 2 TruncateOja (Xiileem) A,
Input:
Dataset (Xilvenn) estimated support set S C [d]. Algorithm A, Parameters +
2: 6 + A ((Xi)
[6]
3: Ötruncvec
||0]||||
4: return ttruncvec
Theorem 3.5 (Vector Truncation). Let Assumptions 1 and hold and k. 2 s. For dataset D =
(Xi)eem and wp N 10, let be the randomized algorithm which computes ttruncvec
TrjncateOja ((Xihe(s..) Oja, {n, wn, where 17 = SuccessBoost ((Xi)ie(m) A, d-10) satisfies,
3log(n) m0A1-Xa) Then, for min, ly (i)
d
A: log" (d)
sin (8,m) & C"
X1 -x
n
with probability at least 1 1- where C" is an absolute constant.
Remark 3.6 (Limitation). Existing inconsistency results on PCA (JL09) provide threshold for signal strength (A >22/\r, >ı, below which, the principal eigenvector of E is asymptotically orthogonal
to vi- We believe a similar result may hold for the Oja vector, which leads the signal strength condition in Assumption 2

---

Note that the rate obtained in Theorem 3.5 nearly matches the minimax lower bound proved in [VL12] CMW13), up to a factor of Az X and log (d) and has optimal dependence on s, and n. A
limitation of Algorithm 2 is that it uses the estimated support, S, at the very end after computing the estimated eigenvector enhance the signal by truncation. Instead, one may run Oja's algorithm datapoints restricted to the recovered support in the beginning.
To this end, we use the algorithm in [Lia23] (denoted by OptimalOja, see Proposition A.5.3 for subgaussian data, which uses an iteration-dependent sequence of step-sizes {7h (1))ej))) [Ejn]'
We run Algorithm 2 with OptimalOja as the procedure to do sparse PCA. This leads to the minimax error rate, shown in Theorem 3.7 The high probability bounds in Theorem 3.5 and 3.7 both the support recovery guarantees derived in Section 3.1 and the boosting procedure described in Section 3.4 Detailed proofs for both results can be found in Appendix Section A..]
Theorem 3.7 (Data Truncation). Let Assumptions [ and 2 hold and k
For dataset D = (Xitee(a) and wo N (0, I). let A be the randomized algorithm which computes Orruncvec f
TruncateOja {LXils) (E(g.n) S, OptimalOja, [(ne)e .wo
Then for min; |v (i)
A1 A1-12 (.4 $) ū + SuccessBoost ((x))ss A, d dd satisfies,
A1
k log (d)
sin² (0, S C"
(A1 x2)
n
with probability at least 1 d where C" 2 is an absolute constant.
Remark 3.8. Algorithm 2 with both Oja and OptimalOja as input procedures require a simple initialization vector wo N (0, 1). In contrast, the block stochastic power method-ber based algorithm presented in XYX15) provides local convergence guarantees (see Theorem 1) requiring a block size of O (s log (d)). They provide initialization procedure, but the theoretical guarantees achieve such an initialization require block size Q2 (d). (YZ13) also require close enough initialization. In the particular setting of a single-spiked covariance model, they require |w] Un u1|= Ω2 (1). In comparison for Algorithm
2 3.7 it suffices have ww Un
with probability at least 1 5 (see Lemma A.2.1 Ve
3.4 Probabilistic boosting
In this section, deseribe generic procedure for boosting the success probability of given randomized algorithm, AA (also see [KLL=23) 23)). AA satisfies Definition 3.9, then its probability can be boosted using this procedure. The formal guarantees of the boosting procedure are provided in Lemma 3. 10 (proof in Appendix Section A.2 It divides the data evenly into log (+) buckets 16 runs A each bucket and aggregates the results Via pairwise comparisons.
Definition 3.9. Let T be a set with metric p and A be randomized algorithm which takes as input i.i.d datapoints D = {X,) and possibly additional statistically independent parameters and returns an estimate q T, which satisfies I (p (g. 2 c) < 1 for a fixed q- E T. Then, A is said to be constant success oracle with parameters 1D,0T,p0 .P. gx,e), denoted as A ConstantSuccessOradee (D,6, T, c).
Algorithm 3 SuccessBoost
(Xi) A.
I: Input: Dataset D = (Xilve(m) A == ConstantSucceesOOrade (D,0, Required
failure probability 5
2: Return An estimate q E such that P (()
3: S 30g (t), n/S
4: E [S], l: < A A ((XBO-D+))e ,, O,T.p.9.:e) C, + (t' E [S] (ge, qr) < 26}
5: If 3g. such that [c,] /S > 0.4 Return q: Else Return 1
For simplicity, assume S, B in Algorithm integers.
7

---

Compansinn of with trnertoaa
20
15
-iitay jurr
(1 s
--atry pupport (epeirrorr)
ot 03144
10
110 230 430
1300
200
250
Tirasdacs
Timossopo
(a)
(b)
Figure 2: We use 2 used in [QLR19], Section 5.1. (a) Variation of log (le Baual) for E S and E (y-axis) with (z-axis) for a fixed unit vector is set as Theorem 3.5 and grows from to 1000. The lines labelled "sample" plot log(le; N, ), whereas "population" curves plot log [e] B,, D)- (b) Variation of log ()) B,, Bx] and log (vf B,, B, v1) (g-axis) with n E [300] (r-axis). We also plot log of the bound of Br, B as in WK 16) and 2n log (1 m1a1) for comparison.
Lemma 3.10 (Geometric ConstantSuccessOracle (D,0)e(DD,,7,, P,,,T,PP e) (Definition
Aggregation
for Boosting). Let A 3.9 for dataset D = (Xi)een)
Then
for 8 (0, 1). q
SuccessBoost ((X))ve(m) A. satisfies (g. (q.9.) S 3c) 6.
3.5 Entrywise deviation of the Oja vector
To analyze the success probability of recovering the indices S, we will define the following event, E = {S C $3. We now upper bound IP (E"). Define an element of the unnormalized Oja vector as
r3 e B, uo. i [d]. Here ug N (0, I) is the initialization used Algorithm Observe that
+ Brn > 0 such that {Vi E S, IM T.)
Aifi:
S. To
s - s}
or equivalently,
0 - vT, 0, (3i Inls T.) 1 >
Therefore, for any fixed
0, 8d
e
T, T.UUUK
We will, therefore, be interested in the tail behavior r; for E S and S. Before presenting our theorems, we will use Figure to emphasize the daunting nature of what we aim to prove. Consider X
the quantity [ra [uo]
= E [c] Bu mo]. We use
C + to denote XX CCs A.
E rr [u] = o [B,] U1 1 uo + e TE [Ba] V1 VT do
[ [e] ua (0 + 7))"" + Ic. V
unl (1+1)2)*
For i E S
+ lef V VT un (1 7)22)"
For i
Thus, traditional wisdom would make us hope that the elements, Tú, will concentrate around their respective expectations, whose absolute values are off by ratio (er()) 11 [cxp(nn(AA) X2)).
However, Figure a shows that while the elements in the support seem close to their expectation, those not in support are, average, much larger than their expectation. First, note that elementwise analysis of the Oja vector has not been done even in the low dimensional regime where Taf Tet/n - 0. In this regime, there is very recent related work for eigenvectors the empirical covariance matrix Σ [FW22] which are not applicable here. In the high-dimensional case, an analog can be drawn with elements E, which concentrate around their mean individually. Yet, || Σ not small. Thus, thresholding Σ obtains consistent estimates of y under sparsity assumptions [B09 DM
Nov23)
similar principle applied by [SSML]] where the eigenvector of E is truncated. They assume that n is fixed, and A1/X2 = da - x: as d -> xo. In comparison, our analysis is about products of random matrices, not sums, and hence, completely different. We will show that 0 (i), even when i S, do not concentrate. But for suitably chosen threshold, They are large with high probability,

---

whereas those outside S are much lower with high probability. Proving this is also difficult because the analysis involves the concentration of the projection product of independent high dimensional matrices on some initial random vector. Lemma 3.11 establishes exactly that for elements in the support.
Lemma 3.11 (Tail bound support). Fix a (0.1,1), Define the event G == {10 uu - ye
and
threshold T == V2e min (1) + n Let the learning rate be set as in Lemma 3.1 Then, for an absolute constant Cи > 0,
VE P [niss Tm(g) ( Ch nd1 logg (n) + m/
A
ty d2 11 (i)
Our next result provides a bound for i S.
Lemma 3.12 (Tail bound outside support). Fix a 8 (0.1,1). Let the learning rate be set in
Lemma 3.7 and define the threshold Tn := 72c minges 01 (i) [1 + md1)". Then, for min, (o (i)
Ω
A A1 A2
and an absolute constant CT > 0 we have,
A1 X2 ) )00))))) minies. 21 (i)²
27
Vi &
P(r Tn) Cr
n²>7
The proofs of Lemmas 3.11 and 3.12 are based on tail-bounds involving the second and fourth moments of r, := e/ B,, uo. The details of obtaining the tail bounds are deferred to the Appendix Section A.3 The results developed this section are used to analyze the support recovery and sin?
error guarantees provided in Section 3.1 and 3.3 We provide brief proof sketch in Section
4 Proof technique
In this section, we outline the proof techniques for the entrywise deviation bounds in Lemmas 3.1 3.12 These bounds are crucial for analyzing both the support recovery results (Lemma [3.1 and Theorem 3.2) and the sparse PCA results (Theorems a.d The proof involves deriving bounds on the expectation and second moment of uz B,U B, ug. where U E Rdx is a fixed matrix and uo ~ (O, I). It then applies Chebyshev's inequality to obtain the tail bound. For the proof sketch, we use U = ei. but we maintain general notation for broader applicability in Theorem 3.5 For our results, we also need to bound this quantity with U Is (see Lemma A.5. for details). Our techniques to bound E[ug B, U uo) are detailed Section 4.1
4.1 Solving linear system of recursions
One can show that (see Lemma A.2.1l in Appendix),
E [ BL Bauo] [o] B Badi] +
[Tr (VT BTBTUT
(5)
We start by showing how to bound Or, and 8n. Before dive into our techniques, we note that the analysis of Oja's algorithm [J]K+16] in the non-sparse setting provides some tools that we could potentially use here. Using the recursion from Lemma 9 in JJK 16). we get
|E BBUUT B
exp(2nn)) + V) |0UT|,
(6)
where is a variance parameter defined as || [A1 - () - 1 Lemma A.2.3 shows that for o-subgaussian X (definition 2.1).
V E [A (A 2)
[A [A] | < 22 Tr(E) + X
This provides an upper bound on c., S | [B, B. While this bound tight when rarr bounded by a constant, in the high dimensional setting (Assumption 2 considered in this work, this bound too loose. This is evident from Figure B), which plots E [BB B for U = along with the bound achieved using Eq 6 labeled as Jain et al. (2016). Note that the plots are in

---

the log- scale so difference in the slopes translates to significant multiplicative difference. This warrants a more fine ane-ggained analysis of an.
Let us examine On more closely to obtain a finer bound. Using the structure of the matrix product,
Bn, from Eq 3 have:
On Cn-1 2n + 1 X,, v1) (X, BU
Now, as a consequence of subgaussianity (see Lemma A.2.2) for K == (2L2o")², with the Cauchy- Schwartz inequality, the second term in the RHS can be bounded further using:
E Xx = KΛЛ. E B,-,B,-U Bh 1x,)
Fn-1
Therefore, using the above bound along with the eigen- degeomcccompoiiioonn E baany + +VA..
On - (1 + 21/ 1 Xi) an-1 4
(7)
Similarly, 8n can also be upper bounded as follows:
3n < (1 2njA2 + L Tr (E)) 3n-1 412 Tr ap-1
(8)
Note that upper bounding and eliminating a,-1 or - from Eq respectively, would simplify the recursion but lead to weaker bound as in Eq 6 Therefore, we solve Eq and as system of linear recursions in Cx and Bn.
Cn Bn
+ 2TA11 + +0 (T) ((T(E))
O (A1d2) + 2mA2 O (1p2 T((1))
an-1 Bn-1)
Estimating elements pm, where the defined 2 x matrix, is crucial. Wi192 gives a compact expression for these elements using År (P) and A2(P). Under our assumptions, we have P1 > P22- naive upper bound on A1 (P) using Weyl's inequality [Die15] is + 2nd1 + cg Tr(E), similar to Eq 6 Since recursions like Eq 9 are common in analysis, we provide general solution in
Lemma A.2.5
(detailed in the Appendix Section A.2).
An important consequence of this is that we now have the following bounds on a, for U = I:
an S (1 + 2n/11 + 2 x²) (1 O(p)1))
(10)
which is much tighter than Eq/6in in our high-dimensional regime. Furthermore, observing Figure (
we see that Eq 10 presents much tighter upper bound, matching (1+ + 17A1)²2 2 up to constant factors.
Recall that the bounds obtained in this section deal with a,, S,. defined in Eq 5 A similar
system of recursions can be obtained get tight bounds on E [ B UU
B,
and
Tr (VEBAUUTBAN B details of which we defer to the Appendix Lemmas A.2.9
A.2.10
5 Conclusion
Oja's algorithm for streaming PCA has been extensively studied in the recent theoretical literature, typically assuming that / is bounded or a slowly growing covariance matrix effective rank Teft. This paper addresses the high-dimensional sparse PCA setting where the effective rank reff can be as large as n/log n while v1 is s-sparse. In this context, while there has been a vast body of work that achieves minimax error bounds, we unaware of any single-pass algorithm that works O(nd) time, (dd) space, on a general Σ, without any strong initialization. Surprisingly, our thresholded estimator achieves the minimax error bound of O(s log d/n). whereas the error rate of Oja's ' algorithm is O(ran/n) Empirically, the elements of the unnormalized Oja vector do not concentrate in this regime. Through independent random matrices on and its orthogonal subspace, we show that the entries of the Oja vector within the support of 01 are large, while those outside are much smaller.
analysis that uncouples the projection of a product of
A Acknowledgments and Disclosure of Funding
We gratefully acknowledge NSF grants 2217069, 2019844, and DMS 2109155. We thank Kevin Tian for his valuable insight on geometric aggregation and boosting and the anonymous reviewers for their valuable feedback.
10

---

References
[APW22] Emmanuel Abbe, Jianqing Fan, and Kaizheng Wang. An lp theory of pea and spectral clustering. The Annals of Statistics, 50(4):2359-2338) 2022.
[AW08] Arash A Amini and Martin J Wainwright. figh-dimensional analysis of semidefinite relaxations for sparse principal components. In 2008 IEEE international symposium on information theory, pages 2454-2458. IEEE, 2008.
[AZL11]] Zeyuan Allen-Zhu and Yuanzhi Li. First efficient convergence for streaming k-pea: a global, gap-free, and near-optimal rate. 20/7 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 487-492. IEEE, 2017.
[BB19] Matthew Brennan and Guy Bresler. Optimal average-case reductions sparse pea: From weak assumptions to strong hardness. In Conference on Learning Theory, pages 469 470. PMLR, 2019.
[BDF13] Akshay Balsubramani, Sanjoy Dasgupta, and Yoav Freund. The fast convergence of incremental pca. C. J. C. Burges, Bottou, M. Welling, Z. Ghahramani, and Q. Weinberger, editors, Advances in Neural Information Processing Systems 26, pages 3174-3182. Curran Associates, Inc., 2013.
[BKW20] Afonso S Bandeira, Dmitriy Kunisky, and Alexander S Wein. Computational hardness of certifying bounds constrained pea problems. In //th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151, page 78. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2020.
[BL09] Peter J. Bickel and Elizaveta Levina. Covariance regularization by thresholding. arXiv: Statistics Theory, 2009.
[BPPI8] Guy Bresler, Sung Min Park, and Madalina Persu. Sparse pea from sparse linear regression. Advances in Neural Information Processing Systems, 31, 2018.
[BR13] Quentin Berthet and Philippe Rigollet. Optimal detection of sparse principal components in high dimension. 2013.
[CMW13) T Tony Cai, Zongming Ma, and Yihong Wu. Sparse pea: Optimal rates and adaptive estimation. 2013.
[CYWZ18] Minshuo Chen, Lin Yang, Mengdi Wang, and Tuo Zhao. Dimensionality reduction for stationary time series via stochastic nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018
[dBEGO8] Alexandre d' Aspremont, Francis Bach, and Laurent El Ghaoui. Optimal solutions for sparse principal component analysis. Journal of Machine Learning Research, 97)), 2008.
[De115] Rainer Dietmann. Weyl's inequality and systems of forms. Quarterly Journal of Mathematics, 66(1):97-100, 2015.
[НKPР23] Ilias Diakonikolas, Daniel Kane, Ankit Pensia, and Thanasis Pittas. Nearly-linear time and streaming algorithms for outlier-robust pea. In International Conference on Machine Learning, pages 7886-7921. PMLR, 2023.
[DKWB233 Yunzi Ding, Dmitriy Kunisky, Alexander S Wein, and Afonso Bandeira. Subexponential-time algorithms for sparse pea. Foundations of Computational Mathematics, pages 1-50, 2023.
[DM+ 16] Yash Deshp, Andrea Montanari, et al. Sparse pea via covariance thresholding. Journal of Machine Learning Research, 17(141):1 -1, 2016.
[DMMW17] Santanu S. Dey, Rahul Mazumder, Marco Molinaro, and Guanyi Wang. Sparse principal component analysis and its Ierelaxation, 2017.
11

---

[GMZ17] Chao Gao, Zongming Ma, and Harrison H Zhou. Sparse cea: Adaptive estimation and computational barriers. 2017.
[GWS20] Milana Gataric, Tengyao Wang, and Richard J Samworth. Sparse principal component analysis via axis-aligned random projections. Journal of the Royal Statistical Society Series B: Statistical Methodology, 82(2))329-359) 2020.
[Heb49] Donald O. Hebb. The organization of behavior: A neuropsychological theory. Wiley, New York, June 1949.
[H]S Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, and Ruizhe Zhang. Solving sdp faster: A robust ipm framework and efficient implementation. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 233-244. IEEE, 2022.
[HNW21] De Huang, Jonathan Niles-Weed, and Rachel Ward. Streaming k-pea: Efficient guarantees for oja's algorithm, beyond rank-one updates. CoRR, abs/2102.03646, 2021.
[HNWTW20] De Huang, Jonathan Files-Weed, Joel A. Tropp, and Rachel Ward. Matrix concentration for products, 2020.
[HNWW21] De Huang, Jonathan Niles-West Weed, and Rachel Ward. Streaming k-pea: Efficient guarantees for oja's algorithm, beyond rank-one updates, 2021.
[HW19a] Amelia Henriksen and Rachel Ward. AdaOja: Adaptive Learning Rates for Streaming PCA. arXiv e-prints, page 1905.:199..122.. May 2019.
[HW19b] Amelia Henriksen and Rachel Ward. Concentration inequalities for random matrix products. arXiv e-prints, page 1xXiv:197.008833 July 2019.
[JJK + 16] Prateek Jain, Chi Jin, Sham Kakade, Praneeth Netrapalli, and Aaron Sidford. Streaming pea: Matching matrix bernstein and near-optimal finite sample guarantees for oja's algorithm. In Proceedings of The 29th Conference Learning Theory (COLT), June 2016.
[JK Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. A faster interior point method for semidefinite programming. In 2020 IEEE 61st annual symposium on foundations of computer science (FOCS), pages 910-918. IEEE, 2020.
[J] Arun Jambulapati, Syamantak Kumar, Jerry Li, Shourya Pandey, Ankit Pensia, and Kevin Tian. Black-box k-to-I-pca reductions: Theory and applications. Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory. volume 247 of Proceedings of Machine Learning Research, pages 2564 2607. PMLR, 30 Jun-03 Jul 2024.
[JL09] lain M. Johnstone and Arthur Yu Lu. On consistency and sparsity for principal components analysis in high dimensions. Journal of the American Statistical Association, 104(486):682-66) 693, 2009. PMID: 20617121.
[JT220] Arun Jambulapati. Jerry Li, and Kevin Tian. Robust sub- -abb-gaussinn principal component analysis and width-indeppndeet schatten packing. Advances in Neural Information Processing Systems, 33: 13:15589-15700 2020.
[JM09] Sungkyu Jung and J. S. Marron. PCA consistency in high dimension, low sample size context. The Annals of Statistics, 37(6B):4104 111110441110000 4130. 2009.
[J Michel Journée, Yurii Nesterov, Peter Richtárik, and Rodolphe Sepulchre. Generalized power method for sparse principal component analysis. 11:1175533, mar 2010.
J. Mach. Learn. Res.,
[Jo103] Ian T Jolliffe. Principal component analysis. Technometrics, 45(3):276, 2003.
12

---

[KLL Jonathan Kelner, Jerry Li, Allen X Liu, Aaron Sidford, and Kevin Tian. Semi-random sparse recovery in nearly-lineat time. In The Thirty Sixth Annual Conference on Learning Theory, pages 2352-2398. PMLR, 2023.
[Lia23] Xin Liang, On the optimality of the oja's algorithm for online pea. Statistics and Computing, 33(3):62, 2023.
[LSH222] Hanbyul Lee, Qifan Song, and Jean Honorio. Support recovery in sparse pea with incomplete data. Advances in Neural Information Processing Systems, 35:27321- 27332, 2022.
[LSW21] Robert Lunde, Purnamrita Sarkar, and Rachel Ward. Bootstrapping the error of oja's algorithm. Advances in Neural Information Processing Systems, 34:6240-622 6252, 2021.
[LV15] Jing Lei and Vincent Q Vu. Sparsistency and agnostic inference in sparse pea. 2015.
[Ma13]
Zongming Ma. Sparse principal component analysis and iterative thresholding. The Annals of Statistics, 41 (2):772 801, 2013.
[Mac08] Lester Mackey. Deflation methods for sparse pea. Advances in neural information processing systems, 21, 2008.
[Mon22] Jean-Marie Monnez. Stochastic approximation of eigenvectors and eigenvalues of the q-symmetric expectation of random matrix. Communications Statistics-Theor and Methods, pages 1-15, 2022.
[MP22] Nikos Mouzakis and Eric Price. Spectral guarantees for adversarial streaming pea, 2022.
[MWA06] Baback Moghaddam, Yair Weiss, and Shai Avidan. Generalized spectral bounds for sparse Ida. In Proceedings of the 23rd international conference on Machine learning, pages 641-648. 2006.
[MZ20] Shahar Mendelson and Nikita Zhivotovskiy. Robust covariance estimation under 1.4112 norm equivalence. 2020.
[Nov23] Gleb Novikov. Sparse pea beyond covariance thresholding. arXiv preprint arXiv:2302. 2023.
[Oja82a] Erkki Oja. Simplified neuron model as principal component analyzer. Journal of Mathematical Biology, 15(3):267-273, November 1982.
[Oja82b] Erkki Oja. Simplified neuron model principal component analyzer. Journal of mathematical biology, 15:267-273, 1982.
[Pau07] Debashis Paul. Asymptotics of sample eigenstructure for a large dimensional spiked covariance model. Statistica Sinica, pages 1617-1642, 2007.
[Pea01] Karl Pearson.
Liii. on lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 2(1 2(115:599557, 1901.
[QLR19] Yixuan Qiu, Jing Lei, and Kathryn Roeder. Gradient- sparse principal component analysis with extensions online learning, 2019.
[SSM11] Dan Shen, Haipeng Shen, and J. S. Marron. Consistency of sparse pea in high dimension, low sample size contexts. J. Multivar. Anal., 115:317-333, 2011.
[SSM13] Dan Shen, Haipeng Shen, and James Stephen Marron. Consistency of sparse pea in high dimension, low sample size contexts. Journal of Multivariate Analysis, 1 11::317-333, 2013.
[STL07] Bharath K. Sriperumbudur, David A. Torres, and Gert G. Lanckriet. Sparse eigen methods by d.c. programming. In Proceedings of the 24th International Conference on Muchine Learning, ICML. '07, page 831-838, New York, NY, USA, 2007. Association for Computing Machinery.
13

---

[VCLR13] Vincent Q Vu, Juhee Cho. Jing Lei, and Karl Rohe. Fantope projection and selection: A near-optimal convex relaxation of sparse pea. In C.J. Burges, Bottou, M. Welling, 7. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[Ver10] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027 2010.
[Ver18] Roman Vershynin. High-Dimensional Probability. Cambridge University Press, Cambridge, UK, 2018.
[VL12] Vincent Vu and Jing Lei. Minimax rates of estimation for sparse pea in high dimensions. In Neil D. Lawrence and Mark Girolami, editors, Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, volume 22 of Proceedings of Machine Learning Research, pages 1278-1286, 1286, La Palma, Canary Islands, 21-23 Apr 2012. PMLR.
[Wai19] Martin J Wainwright. High-dinenssooal statistics; A non-asymptotic viewpoint, volume 48, Cambridge university press, 2019.
[Wed72] Per-Ake Wedin. Perturbation bounds in connection with singular value decomposition. BIT Numerical Mathematics, 12:99-111, 111, 1972.
[Wi192] Kenneth S. Williams. The nth power of 2 x 2 matrix. Mathematics Magazine, 65(5):336-336, 1992.
[WL16] Chuang Wang and Yue M. Lu. Online learning for sparse pea in high dimensions: Exact dynamics and phase transitions, 2016.
[XHS 18] Peng Xu, Bryan He, Christopher De Sa, Joannis Mitliagkas, and Chris Re, Accelerated stochastic iteration. volume 84 of Proceedings of Machine Learning Research, pages 58-67, Playa Blanca, Lanzarote, Canary Islands, 09-11 Apr 2018. PMLR.
[YHW18] Puyudi Yang, Cho-Jui Hsieh, and Jane-Ling Wang. History pea: new algorithm for streaming pea. arXiv preprint arXiv:/802.00 102.:48002.05447,, 2018.
[YX15] Wenzhuo Yang and Huan Xu. Streaming sparse principal component analysis. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 494-503, Lille, France, 07-09 Jul 2015. PMLR.
[YZ13] Xiao-Tong Yuan and Tong Zhang. Truncated power method for sparse eigenvalue problems. Journal of Machine Learning Research, 14(4), 2013.
[XX18] Hui Zou and Lingzhou Xue. A selective overview of sparse principal component analysis. Proceedings the IEEE, 101(5) 2018.
14

---

A Appendix
The Appendix is organized follows:
Section A.
provides further details about related work
2. Section A.2
provides
useful results used in subsequent analyses
3. Section A.3
provides Entrywise deviation bounds for the Oja vector (Lemmas 3.11
3.12
4. Section A.
proves convergence Support Recovery results (Lemma 3.1 Theorem 3.2)
5. Section A.5
proves convergence of Sparse PCA results (Theorems 3.5 3.7)
6. Section A.6
provides another alternative way of truncation using value-based thresholding
(Theorem A.6.1)
A.1 Further details on related work
There has been a lot of work on computational computational hardness of sparse PCA [GZZ17 DKWB2) B22 BKW20)
BB19
Minimax optimal Sparse PCA algorithms with global convergence: These consist of SDP-based algorithms such [AW08] [VCLRI3 [BEGG))) which do not scale well in high-dimensions (see
BR13 Wai19].. The state-of-the-art SDP solvers 20 HJS+22) currently have a runtime 2 (n d²), where z 2.732 is the matrix multiplication exponent. Algorithms proposed in
Ma13, CMW13 [IRSSO] DM 16 involve forming the entire (d x d) sample covariance matrix,
which itself be challenging from the perspective of space and time complexity. Furthermore,
Ma13 CMW13 DM 16) have been analyzed under the spiked covariance model in 1 [QLR19]
propose computationally efficient modification of the Fantope projection-based algorithm of [VCLR13, which requires (rd²) space, and M(nd) time.
Single-pass online sparse PCA algorithms with (df) storage and ((nd²) time [QLR19 also
provide single-past passe- online algorithm and state that this algorithm (Theorem 4) is the first to provably obtain the global optima in streaming setting withou any initialization, under a general L. However,
this method requires (df)) storage, O(nd²) time, and the estimation error is O
d"
(Theorem 4,
Vn
QLR19) The algorithm does d sparse linear regression problems achieve this.
Support recovery algorithms with (dd) storage and O(nd²) time: LV15 LSH22
use an
SDP--aasdd approach and [PPT8]] use sparse linear regression for support recovery.
More details on streaming PCA algorithms [XX15) provides an online block version of the truncated power method in Y under the spiked model (Eq 2 They require initialization up with a sufficiently large jug u1 t 12 (1) (local convergence). Their proposed initialization with streaming PCA algorithm until reaching a specific accuracy threshold. for which there is no known theoretical guarantee under the spiked high- high-dimensional setting. [WL16] provides an analysis of streaming sparse PCA under Eq 2 via partial differential equations (PDE), but they only prove asymptotic convergence. Similar to YYA1], they also require |wg v 1 - 2 (1) which can be hard to find in high dimensions for a general Σ. Recent results provide black-box way obtain the top-k principal components (k-PCA) given an algorithm to extract the top eigenvector (see [al) which could be employed treating our algorithm as a I-PCA oracle (see [JKL+24] Mac08)). We believe that our analysis can be extended to obtain top-k principal components simultancously via QR decomposition and thresholding.
A.2 Useful results
Lemma A.2.1. (Fact 2.9 (DKPP23) For any symmetric d x d. matrix A, we have Var [2T Az] 1/ I is PSD matrix, then for any 3 > 0, holds that
P.-N(o.) [I Az 8T) 2 Ve3
Proof. We give short proof here. Since symmetric matrix, let A PAPT where P an orthonormal matrix and A is a diagonal matrix. Then, denoting y pf we note that y N (0, f).
15

---

Therefore,
IT Az PAPT 2 = y = Σ AMl
Therefore,
d
d
Ez-N(o.)) Az] = By-NNonn
A
Σ
A = (A)
and
d
27
d
d
Ez~N(o.n)
A(=)A2)*] By-N(O.N
Σ
Ey--(o.1)
Σ
+
Σ
1=1
d
3
X2 + Σ
A,1 2 2T= + Tr (A)2
1=1
To get the tail lower bound, note that it trivially follows if 3 > (0, 1). We have
1. Therefore we proceed with
PP PanA((,11) S = PyNN(O.))
Σ
S
A1
1=1
d
d
AoVi ))
<
E
exp
t
8
A
Σ
,t>0 0
1=1
1=1
exp
4
Σ
X
E
exp
Σ
1=1
d
d
= exp
tB
Σ
A
(1+ + 2A,t)
1=1
/=1
Let t
2 >En1" de (3 -1). Then,
1
P.-N(o.1) [2T S (TT( exx
1-8 3
d
1+
(
3 - 1
2
Σ X;
E=1
1-8
1
- 1)
< exp
1+
2
3
1 - 3
VB 3
exp
2
S e/
Hence proved.
Lemma A.2.2. Let X E Rdd be a o-subgaussian random vector with covariance matrix Σ. Then, for any matrix M RRdx and any positive integer p 2 2,
E [ MM MM)x)"
x)r < (I'20p)) Tr EM")
Proof. Let the eigendecompposition of M be PAPT, Define Y : Pf' Then,
E (MT =E
Σ Xwi
Σ
2hs (A.11)
ki, k ka
yi
to - Ka 2220
16

---

Therefore,
2h
E
2kg
# using Holder's inequality since
$)
E
yi
2kg
h:
p.
1=1
1=1
1=1
y
(A.12)
Using the definition of sub sub-suussiine gaussianity (Definition 2.1 we have,
y
E
(of pd x) x
=E ((Pe:) x) 2p
6 (vp) 20 (I 2p
P (c? SP:)) )
Susbstituting in Eq A. 12 we have,
E
yi
2k.
II At
2 (e, PTEPe)) ki
d = O1'202p)) p))
(Die) pm p' IPei) k
Substituting in A.11 we have,
d
E (x { MMxx)) & (I'O?p)
Σ
II (Tee:p" ki i=1
ki, ka)
Ay + Rog to Aid my
11. R2 20
(L'OOp)²
( ((EExrere
11) 1))² -( (M"
-1'O'p))
T pT pT Σ
1=1
Hence proved.
Lemma A.2.3. Let X E Rd be o-subaaussian random vector with covariance matrix Then,
| (xx])) 4 Tr
Proof. For any fixed unit vector Rdd, have
d E (xx7)
u (x*x) xT
(XTx)) E (XT
E
E [XTx)²]
E [XT xuux))]
s (2L302)
l1 (2) Tr (u)
< (2120022 X1 Tr(E)
where we used Lemma A.2.2 with p 2 and M =
17

---

Proposition 3.4 (Lower bound for diagonal thresholding). Let Assumption 2 holld For any diagonal- thresholding algorithm, A. performing support recovery with sparsity parameter such that n Ω (o log (d)), there exists covariance matrix E with principal eigenvector, vi, l|vilo such
that, IP S 0) do
Proof. Let s be a multiple for ease of analysis. Consider a dataset with a covariance matrix,
1
2: Bruiu 32u20l
B3U2U2
1,
233 2.1,3g 2.234
2
48
3
Vi
[s] (1)
E
102 (1)
V
4s 5s
5s
Vi E
(i)
=
Vi E
28
044 (i)
=
(A.13)
3 3
3
where
Based on Eq
A.13 we have for,
2'
3
i E (1,
S]
Di,
2
48
3/2
3/1
ie
+
+
2
2s
48 58
1
383
1
381
ie
E
+
+
3
3
2
2
2.1s
58 28
1
33
3/
i
Eig =
2 +
2.2s
1
i (2s, d] 11, 2
Note that the largest eigenvalue of Σ, \ = 31 + 2. Let 4, := 100 \1 from Wai19], we have, for the empirical covariance matrix. E,
log(d) Using Lemma 6.26
IP
max (JE|d
و (1.50 2 2/n)
1
d1a
Define the event, & = max complexity bound on n, under event E
E (i.j) - E(,j)) s In and note that due to the sample
ΣS max Σgs 2 min Σ. 2 max Σg, (x
min
vE[1,s]
EE 1,
8>/2s
Therefore, under event E, the largest diagonal entries of E are i e (s, 2s). and therefore, |å Ssss-> which completes our proof.
Lemma 3.10 (Geometric Aggregation
for Boosting). ConstantSuccessOraade (D, 0, T. (..c) (Definition 3.9 for dataset D = {Xi)eeml)
Let A
Then
for 8 (0, q + SuccessBoost ((X:)aetn) A.8) satisfies P (pp (p(g. (g. $ 3c) 2 1 - 5.
Proof. Consider the indicator random variables X := 1 (p 9.) s c). Let p = and
300 (1) for convenience of notation. Then, Vi [r]. P P 1) 2 1 - p. Define the set
S:= (i::: [r] 1}. We note that using standard Chernoff bounds for sums of independent Bernoulli random variables, for E 1),
TP (1S|5 (1 E ([S)) < exp (- O [|S]]
2
18

---

We have, E ||]] 2 r (1 p) using linearity of expectation. Therefore,
0² (1 p)
P P(SS (1 - 0) (1 p) - exp
2
P P(SS| (19 (1- 2 exp (- (1 (-11pp) p)r
1
for 0 ==
(A.14)
200
10
Recall that Algorithm 3 defines as:
q qs such that | E (r) (g: 9₁) s 2cHl
2 0.9 -p) p)
(A.15)
r
Note that the definition of & does not require knowledge of and it can be computed by calculating p(.) error between all distinct (2) pairs (gis 93) 15)
Let be the event ([S}> notation. Let us now operate conditioned on E. Note that conditioned on &, such always exists since any point in S is a valid selection of q. This is true since
(19 - p) r} and denote ;= (19 for convenience of
(gi, 93) S p (4: q-) + (g) q-) S 2e
Here we used the property of the event & and the triangle inequality for p. We further have, conditioned on using triangle inequality for some i E S
(.) S p (ā. (.), S 3e
(A.16)
Therefore, we have
P (()( = PP))) 9.) P (1)
= ( P (p..).)) 2 3c(E9) using Eq A.16
$ (E9)
(1-p)
$ exp
using Eq A.14
200
which completes our proof.
16 log (n)
Lemma A.2.4 (Learning rate schedule). Let the learning rate be set as == n (A1 - 22)
for
1 min { vo C J..
1
positive constant K > O. For constant
S 8x
let
max {1, A1 X2 f d x2 log (n)
Aa
Tr (A2)
on
A1
S
VV log² (n)
A1 x2
ff 2 2+((1), n = Ω (s2 log (d)), the following hold:
(A1)22) 1. 1 C TT(a))
2. Cn S min { Ai Tr(Aa) TY(A2)
3. Cnpn 5
4. exp (-rny (A1 - -22) < nd1 for 2 SF
where C = 100 (I + 1.202) + 16. We state another useful restatement of Claim (1) used in subsequent analysis,
30 E (0.5, 1), (1 (1- 0) (A, X2) + 50L o = 50L*0* log (n) 1/22 Tr (E)
Proof.
22 Tr (A2)
log (n) Tr (A2)
X2
1) A1 A22
S kc
A1 A2 A1
A/2
19

---

Therefore, the first claim follows for c S 1 For the second claim, XO
CnA1 = xC'log (n) X1 n () A2)
I nCc vn
S
where the last inequality holds for c 4xC and 1. Furthermore we have
Cr = C x (log(n)
1 (A1 x2) Tr (r S RCC S 4
where the last incquality holds for KCc S 3. Note that n/C' & min
[A 1 In/on }
1 1
imply 4nC s
V Tr(Aa)
For the third claim, we have
RC log (n) A1 (A1 - X2)
C²'lo (n)
d1
2 )²
Crf nd
S Cn²ce² S
n
A1
X2
where the last inequality holds when es Next, we have the last claim,
VaNaC
1
exp (-rnn (A1 -22) exp (orklog (n)) =
Therefore, it suffices to ensure
1
K log (n) (io) KA1 log (n)
7h
n2
7
(A1 X2)
where (iv) follows since
2 as A > A2 Therefore, we require
(A1-A2)
k log (n)
n
n
which holds for 2 + (1) and sufficiently large n.
Lemma A.2.5. For constants c1, c2 c3, C1, 0, consider the following system of recursions
an S { an + d1
+ Bn < (1 + cmd2 + c1 A2 Tr (Σ)) Bn-1 + c Tr (E) an-1
Let 30 E (0.5, 1). which satisfies 0 (1 0) (A1
+ c cn7d2 TI (E) and
4cges n A2 Tr
( A
)
2
2211
TT(())
0(11 (((2-222) Az)
11, 4np1
S
0i (d1 - -x2)
Then we have,
an S Ai (P)"
ag + tn
20gd1
3 + ag
G5
(10(11 - -x2)
0
3n S Bodo (P)"+ n
205d1
a
Tr (Σ)
+ 30
43
1 1
))]
x (P)"
ci (>1 - -x2)
A1
C4
8
where
-1 -np -P) - - S
C3Cs
17 X
1-
C4
0
(P) -1 cipp- - c A2 Tr
(2))
v
C3C5
2²
1 0
0
20

---

Proof. Writing the recursions in matrix form, we have
(nn (n
(1 eird C37 X1 (x)
( + e
A31R1112
an-1
1+ + can' X2 Tr (x)
3n-1
(A.17)
Define
P:= ( 1+ onyd + 2 C A Tr (2)
co 1+amd + car X2 TT (E)
Then : 1 + CinM, where
\1 + und unn1 (E)
endida 22 + andz Tr (T))
M =
and u := 02 v x
C4 01
w
6
We now compute eigenvalues of M. The trace and
determinants are given as
T A + A2 + fpti + TE)
D = Aida + ni (x (x) - ud1) + uav u Ar Tr - v Tr(E)
Next we compute - D.
T D= (A1 222) + 19
(u)
22 (x + uAI)
2
172 (udp + xd22 (E()))
(ux-ww)) - >/>R12 Tr (E)
(A1 X2)²
smnda T+()))
( (1 A2 +
227122 Tr Tr(E) 27 (
2
2
+ +muu}
-1 (Y1
+ muda
+ vw
ut
17 1/21i>2 Tr (2 (2)
2
4
2
1 ((A1 - 12) 12
Tr (E))² 2 + nud?
(()1 - A2) amda TT (E) +
(1²27 + 4owd22 Tr (E)).
4
2
4
[(A1 A2) Am Tr (2)) + munr 2 + vwn X7 Tr (2)
Let (A1 22) smde Tr Tr(E) + nunr 0 (A1 A2) for 0 E (0,
T2
0 (>1 >22²²
D
+ +wny 2 Tr (Σ)
4
8² (>1 22)²
1 X2 Tr
f
4
0 (Ai -22)
Let y'ondd A2 Tr(E)) 6-(A1- -xa)
< 1. Then, using the identity 1 1- 1 5 $1+ for x (0,1) we have,
2 (A1 - x2) (1
vn Tr (E)) 02 (A1 - 222)
T2
(>1 x2) (1+
27 207 Tr (Σ) 02 (A1 X²)
[1-
<
D
4
2
(A.18)
Let us simplify
n 22 Tr(E) 0²(2 =x²)²
using the definition of 0. We have
vv TF
(1 0)
0 (>1 -22)²
02 (21 X2)
02 (A1 Az)²
21

---

Let (1 -1- 0) 2 (A1 -22' Then.
49u22
0
goow\f>2 Tr Tr(
nown
1 1 A
Ampula
2/4 (A1 12)
8 (A1 - -²2
2r
0
0 (A1 -22)
koaara
4nju2f
- 0 +
28x
(A1 - -12)
I t Mw
1
(A.19)
0
Then, using Eq
A.18 and A.19 the eigenvalues of M are given as \1 (M) = 7 +
T
D and
22 (M) = 2
I
T such that
A1 (M) -11--un -unii, [22 X2 mnd2 Tr (E)
ww
1 1 0
x
0
The eigenvalues of P are given as A (P) == 1 + c1 (M) and X2 (P) = 1 + ci c17122 (M). Then we have,
D1 (P) - c21 = AA (P) - Pı.al -
C3 1 A1
1 -
(A.20)
C4
0
C3
1
(P) -1 -1d Ao Tr [ = Aa (P) P2.2
<
(A.21)
C4
0
We then use the result from the matrices X and Y
Wi192 to compute la and any Bn. To compute P", we first compute
No (P]I X = P-
1
Pi. (2)
P2.2 X2 (P) )
PL
d (P) - (P)
X1 (P) (P)
P2.1
Y P P-1
1
()1 (P) P1,1
P1
d (P) - À1 (P) x2)
- P2.1
A1 (P) P2.2
Then, p==
= À1 (P)" X + Ao (P)"Y, Y, which gives
pa = Pin - bn
P1,20n
P2. 12
P2 bn
where
A1 (P)" - ->e(P)))
bn = (1) (P)) d2 AP) A2 (P)
A11
an
(P) - 222
A1 (P) -P) xP)
a0 Bg
Therefore, for you
we have
(Ai(P))- -22 (P) - (P)
(P)))"
A (P) do (P)
On = p" you (1oP1.1 + (oP1a
- d2
A1 (P) X2 (P)
(A.22)
(PI( - (> ->a(P))))
A (P) - d2 (P)n-1
8n PT yo P2.1 + P22))
>1 (P) - dz >p)
A1 (P) x2 (P)
(A.23)
22

---

Therefore, using Eq A.20 and Eq A.21I
On S <ao (P)"+ +
Po + ag
c3Cs
11
1 -
AA (P)" - 22 (P)
(P) (2())
C1
a0di (P)" +
Boezn X 00
Cycs
11 2
1 1 0
A1 (P) (1p))- (P)
X2 A1 (P) -22
(A.24)
64
Bn S 8022 (P)"
a0l22,1 + 90
C3Cs 1f >2
(1-1)
A1 (P)" (P)"->a(P))
44
11 (P) - -22
= - (P)
anos1 2 \1 Tr () + 30
C3
11
(1-2) ) (
0
\ (P)) - A2 (P)))
c4
d (P) - A2 (P)
(A.25)
Recall that using Eq A.20 and Eq A.21
A) (P) - (p)) 2 IP1.1 - P2.1 20y0s
11-0)
17 {1
C4
20303
(1 0
(1--)
= ccn((AA) - 22) - 2 TT (2i) + muld)
rp ?²>9
(00
0
=c,0n (A1 - ->2) 20363 1/2 X²
1 1
c4
0
1
20 (A1 -22)
2
Substituting in Eq
24 and Eq A.25 we have,
On S A1 (P)
00 + 1/11
20gd1
(80 80 + a0
G5
1 0
)
(2 - -x2)
C4
0
3n S Sod2 (P)
nA
c,0 (X1 -22) x2)
20921
00
Tr (2)
X
+ 30
C4
C3
1
0
x1 (P)"
Hence proved.
Lemma A.2.6. Let U E Rdxm then, for all 1 > 0, under subgaussianity (Definition 2. and the
step-size satisfying (1 - 0) (A1 - 22) + 21 A1 = 2L 1122 20 Tr (E) for 0 E 2 have
then we
( -22) )
2A1
(1-2))
EE BLNT S Sn a0 + t11
Bo + a0
0
2\1
Tr (r(E)
1
E (T B S 300 + 1111 ((11 x22)
000
+
30
X
0
where Bn is defined in Eq
0g = ATUUTT 01 Bg 0o=Th To VU and
(1-0
b 1- 41,00,12111 <AT.001/227
8
1/2 - 1- 2n/ - 44 1F < S4L504,2273
(1-0
Proof. Let an := := 1,E [Tr BAUU (Tr (uf (B
: E
(UT [ Tr (V such that
an + Bn (
23

---

Define An := X and let Fr, denote the filtration for observations i E [n]. Then,
On A of BAUU" B v2l
=A (of (I+ + An)) Bn -U BU
=On-1 + +n A
1n (x
=0n-1 + 1 E [u - _ -
+
[11 Xn X "1)
112-UUU 1 X
On (1 + 21 + 1 1 R
[1]] X,, x 0) (X, Bn U0 B -
-n-1 (1+ + 21 + 10 p
(uf Xn X v1) (x, Bn U0 SUTTBU xn) Fn-11
50n-1 (1+ ) + A
E
(uf (of
Fn-1 Fn
E
Bn- 1U B=) Fn-
=0 (1 21/21) + 1 1B
18 [X x,)) Fn
E
UUU B. Fn
S 50 (1 21 + 4n ~ TI (E, v1 [r (2,, Bn- BT using Lemma A.2.2
with p
=0n-1 (1+ 21) + L
(B Tr (llll + V1AV21 Bn Bn- BTT))
(1+ 2m + 4n²² -²0²2²²) On + 40
(A.26)
and similarly,
3, = Tr (VV
BN Aa)
= IE Tr
-E Tr (A2V7 A Bn.
UU B 1 + 2n Tr (AU +
+ B
Tr [1 VT A, By UU B A
= B
U0 Tr UU 1
( X.. (X BU-BUUU B xx))
= + 2n/B TTr (A3V]
UU 1
E
(X Bn-BUUU B Xn) Fa-1
S <11+ + 27/22 Bn-1 T5
E
VVVVAAVVXX Fn-1
E
(XI Bn- -UT BT R-
xm)²
F
< (1 + 2nd)) 3,-1 + 4ny
4n 26 Tr (DVIA2 E Tr (EBn- BTT1
using Lemma A.2.2
with p = 2
= (1 + 21 + 4n Tr (A3) 41 T² Tr (A2) an-1
< (1 27/22 + 2, X2 Tr (A2)) 8n-1 4n 0 Tr (A3) On-
(A.27)
Writing the recursions in a matrix form, we have
(+ - 2 + 4 Ln Tr (A33
4
(nn-1) Ba-1
1+ 2n + 4n L Tr (Az)
(A.28)
Bnn
The result then follows by using Lemma A.2.5
Lemma A.2.7. Let U E dRdm then, for all t > 0, under subgaussianity (Definition 2. l and the
step-size satisfying (1 0) (A1 X2) + 2 An 2L 0 n/2 Tr (E) for 0 E [ then have
2X1
(30 + 00
1 (2-1)]
E
Tu B B/ S / a0 11d1
0(A1 -x2)
2x1
Tr Tr
( 0
E
Tr (VT BUUU" BBUUUBAAV]]]] < 3072 +
n/11
+ 8o
0 ((1
xz)
A1
0
24

---

where Bn is defined in Eq 3 - uTU 1, pu= = Ir (VTUUTV1) and
7/1 1 1 21j11 4I''011> <400OAP 1-0
11-8
72 21 AL'' Tr 44
Proof. Let On := E [Tr (vE
(VF (V B.UUTB Define A, == : B,
X, X and let Fr, denote the filtration for observations i E [r]] Then,
On E [uf U [1]
E [v (I + nAn) Ba- YU (T
=On-1 + +nn [u] An Bn 1U- B 1 + + [ An UU B Anvi]
=ax-1 + 2nB [o] BB UU' - + [[0] X 1 v1) Bn_ xx)]
an-1 (1 + 11 + T
[0] Xxx (X B UU B -
0n-1 (1 + 21 + B
E
(of X u1) (Xx B, UU Xn) Fi-m
Snn (1+ 21/>1) + T
E
(of (u
Fn-1 E
BUU x,)) Fn-1
-a,- (1+ 21/>1) + T
18
(X X.,
Fn-1 E
(XT U0 B
B F
00n-1 (1 11+ 21 + 4n L'
(E E
Tr (E, BU B })] using Lemma A.2.2
with p 2
0n (1+ 2n + +44
(B
+VA227 U
{1++2m) + 4n bo
(A.29)
and similarly,
sn = E IT UTB BUUUUBBB
=E [Tr (VT + nAn) Bn Bn- ( V1)]
[Ir (VT Bn- B 22 [Tr (V?
(F B
2n
E [Tr (V? A, Bn UU A.
= 3 + En [Tr (V"'BB.- B V1)] + + [V]
BU
= Bm-- + E7/ Tr UU B. 1 (U +
E
Bn (x V BU UUT F
< (1 + 211/2) 3n R IR
(X VF
Fn-1
IF
(xx
(n-BBBUUU B BA_ xx)²² F
< (1 + 2m/22 3n-1 + 4nj² L (EVI E Tr (EBn-IUU* -U Bh using Lemma A.2.2
with p 2
= (1 + 27/2 + L X2 Tr (A2)) pn-1
+ 4nj
L
0 Tr (A2) an-) an-1
(A.30)
The result then follows by using Lemma A.2.5
Lemma A.2.8. For all (. O, under subgaussianity (Definition 2.1 p. let U E Rdxmm Let the step-size n be set according to Lemma A.2.4 then we have,
oo (eBBUUTBTT..)
2m
ao + nd1
0(1 - -x2)
2A
)
)
(00 (80+a0 a0
(1-0))
E Tr (VT BV
B.UU
Soo2 + 1/11 ((12 )x2)
2A1
Tr Tr(E)
+ :o
1 - 0
[9
A1
25

---

where Bn is defined in Eq = uuU u1 :u= = Ir (VPUUTV1) and
P1 1- 2nd1 - 2 $ (17-)
P2 1 27,22 - 5007 L (x) 0 1 0
Proof. Let Op E Bo Bn == E Tr (VI BRUU B Then, using
Lemma A.2.9 we have,
On S (1 + 47 + 100 2 x1) On + 1000) L'o Va 10n-11nn- + 600 6 L
and using Lemma A.2. we have,
Bn (1 + 4m/2 + 100n/ L' 0 d2 Tr (2)) 8n ( V Van-18n- + 600n) 2 L' afan-1
Define On
== Van and bn = VBn Then using v x S 1 2. we have
On - 1 + 4mp1 + 1000)
25 X²
$ (1 21d11 + 50m an 25 1.2 X²
bn 1
+ 4 b 6E)nn-1 +5mm/² 2 2
$ (1 21/ + 501 Tr (E:) bn 2,2 2
The result then follows from Lemma
Lemma A.2.9. For all > 0, under subgaussianity (Definition 2.1. let U Rdxm on E (oT BU uz /²]. Bn = IE [T (VFB,,, BUU V
2 and 0² I 1 then
On S (1+ And1 + 100, *x7) an-1 100y) L X² x2 /on-ann11n 13n-1 + 600 4 1 08 X1
where Bn is defined in Eq
Proof. Let An = X,, XT and F, denote the filtration for observations i E [n]. Then,
an E (uf B, By }1
72 =E (uf BnT - BTT + 2nu? A, Bn 2 A, BnBTTLUU B An
-o (1 + 4n111 + 4n7 E (uf A, By, UU- BT-
T
+ +2, [1 Bn UU Byr 1i) (of AnBr. UV BY Bn
+ 41) 3 E [1] A, Br UUT BT 1 11) (N) B, UU B Am.1)
T
+ + E (of B, An
(A.31)
T4
26

---

For T1.
T = E [If An B
- E [x Xx) (x, Bn- B ii Bn B xn))
[ of Xn) (X Bn- B Bn B UU UU" ( Fa-1] E
s E
E (XT Fn-1 E
B BT Xn)² X
2
Fi-
5 < Tr (Enye)) E Tr (o |
B 1- using Lemma A.2.2 with p p=
= =4 -
1| Bn- 10 BT-1)l
S AAL'''Naan-- &L' Ir (V1V
U'- BT + of Bn B VL Bn- 1
V1 VLV Bn- B--J I + [uf BU 11) Tr (U' B
< 4 a 21 2 18n-1
For T2
T2 = E B U (U A, UU
E 1T B B
" Ant)) [Fn-1]]
E [( B UU [x fann Xn, (x Bn
B UU
[-n1
< (oFBn-1UU -U- B -0,TBB-B / B (XTe xx)
Fn- E
(x7 Bn UUT 2 xx) 2 1F
UUTBTT
< <ATA0AB [1f 10 Bht 11)) Tr (EmreT) v Tr (EBn- 1) using Lemma A.2.2 with p 2
=4I'0 fan- + 4T, X1 E [[u]
Bn- _ 11) Tr (V A21 B B B-11
S 44It0\2ann1 + 4I, ^21 [1f Bn- B 1 Tr (V1 V BU- BT [1]
< <4L x + 4L 2 aa
For T3.
T3 = E [iv] An Br B BY (v 1 Anvi)]
= E (x) 3 (X Bn B B (x Bn- BL
<
E
B BY
BhT || 1 B
E
E
X M xx)) (X BU Xn)
Fn
- BTt 1ill2
< E
E
(XT o1 (XT xn)
|n-1 1
E (XT BUT Fn-1 | B²r 01 112
(3 1LTR Tr (Ba- By E)
2 (uf BUU BU 11)) using Lemma A.2.2 with = 3
<
=2(3630))) xi (2fan-1 + ABE
(of Bn- Br
B vi)) 1/2 Tr (VF BUU By 3
27

---

=2 =3(32002) +
V A112 1 Tr (VT BTTBn-IU -UT Vi)
E
V3112202idd TI (V Bn- B Bi-IVi)
V3112202
A1 - Tr BU 3nL20²
$
x (3L"
+n(322
A (VF Bn-
B BT v1)
-3(3200)) x1 (3I20²) dIde E [o] Ba-
UUT TF BV
+3(33200) XPAGE
Tr [V] Bn-
BT [1)²
22(31203) 1p0m-1 + (3L202)² 21d2
1m-1 1 2213Bm-1
For 14
T4 E
(uf A, - BTT An A1
(X v1 Xn) (X. Byt Xn) )
=E E
X x,) 2 (X, ( Bn UT B Fn
=E
E
$ (4 E
(uf (uT Fu-1
Tr (Bn-IUUT BTT ))
Fu-1
s (4L3O7)* E IV (o12001)* E Tr (Bn- 21) Fn-1
using Lemma A.2.2 with p
(AL'O-)* A
V (Ir (Bn- (BUT
(AL' ' AB
(Ir (Bn- VI-VVA + A Tr (Bn-1UU (U- =
=2(42 ' X (22 + 11
Substituting in Eq A.31 along with using n \₁ S we have,
On < <(1+ 4m 100n² =*002)) an-1 100m² L Va + 6007 LLd 11 21
Hence proved.
Lemma A.2.10. For all > O. under subgaussianity (Definition 2.1 let U E Rdxm
E (of B.UUT
BuUUT B vn )). Bn E (VF B Vi)
and n1202 S
On
{ Axi:T : VAi Tr()))
min
then
8n < (1 + 4m12 + 100n) log (n) L Tr (E)) Ba-1 1001 (n) L2o221 Tr (E)) Von, Van-18n-
+ +600n² log² (n) * Xpan-1
where Bn is defined in Eq
Proof.
Let An = X and F. denote the filtration for observations i [n].
Let
an-1:= := Ir (VT B (Z
DT B,)D1
:-
Tr (VT A, B, BU A,V1
28

---

Then.
Bn
E
Tr (VT BBUU" B )9
=
E
2mp 2 + 11) )²]
3 + 4m 4n² E
Tr (VT A, Bn-UUUU B B V1)² 2
T1
+ +22 R [r (VT 1n- B V1) Tr (VI An BU
+ +41 E
Ir BV BI V1) Tr An 1U 1
Tb
+ + E
Tr (VT An Bn UU BU AI 27
(A.32)
T4
For Tı,
T =
Tr (VTA,, A B UU BTT V
(xx] B B VIV? xx,) )² )
E
VP Br By X, 1 1/7 X, [1]
S E
E
BT- 1 Xn VV' Xm 11 Fn-1
< E
E B BU X Fn-1 E V Xn 112 Fm-1
< (2L'0")' IT (VF BU- EBa-I Bh vi) Tr (VF )] using Lemma A.2.2 with p = 2
< (2L307) [Tr (V Bn- BTT (MrV + v21)2 Un- V1) Tr (V['v1))
< (2L'03) (228n-1 + a
For T2.
T2 = E [T B (" AnVi))
=E [Tr (VF Bn U0 BV) [ Bn UU' (X Vi X.)]
=E Tr BU
E
BU Xm) (X V V Fn-1
< E Tr (VT BU-TBUUU B V1) /
B (XI 1 xa)² Fn-1 E (X x²)² F
< (2L303) E [Tr (VT BU- TA (U BUT Tl (v[VV1),
= (21203)'II(AA)) Tr (VF B Tr (U Bf + +VAeVH) Bn-
< (2L'02)2 Tr (228n-1 + \I AiVan-18n- 18n-1
29

---

where in (i) we used Lemma A.2.2 with p p= 2. For Ts,
T3 = E Tr (V? An Bn UU V Tr (VT An An Ba-1AnV))
EE [Xx, Bn UU T Vi X..) (x Bn- xn) (X
S EE
| By x $
| Xm | By V1 112]
1
E
1 B x 12
x,, 11
Fn-1|
| B Vi 2
S E
E
U BTT x 112 Fn-1
E
VT Xm 11
Fn-1
| B V1 112
EE
(x Bx- BU BUTBB-UUUBB Xn) EE
Fn-1 E (X
Fr-11]
1 B V
< (31202) 3 R TT BTT BB
1 TT (VTVV1) $ | BTT n- Villa]
using Lemma A.2.2 with p = 3
(3L202)
Tr BU
[
(of (A B )i)
+ 2 Tr (Vf UU B B0
()) | B Vi
) TT E (uf B UU B v1) 3 Tr Bn-UUU B V
+2(3L'03) 2/ (A2) E Tr (V B, -U B V1)
-3(320)) X (A2) [ BU. B v1) 1
Tr (VT
B (UB.B.UUBBBL
+3(330) 2/ Tr (A2) $ E Tr BVF By VU V.))
-3(3200)) X (A2) $
TI (VEBA--UUBB (of BU- UU 1i)
+2(36203)) 2 (A2) $ E [VVVIB..UUUU""__V.).
< 23(33000) X1 Tr (A2)² Van-18n-1 + 2 (3I"0²) X² Tr (A2) an- + 23(3200) 23 Tr TA2)) Ba-1
For T4,
T4 = E
Tr (VI A, B BU BU
BT AnVi)"
E
(X* Bn B VIVVVII
E
E
(X B B x,)²² (X v, vFxx)) Fm
UUT Fr-1 E (XXVVITXX.) Fn-1
<
E
E
(UT BT EB_- 10) TT (VTEV,) )²] s (41120)) Tr (A2)* 2 [Tr (U (U'B2 (Nreiuf + Vi AaV2)) Un=
< (4L3
$2 II) (Dian-1 123n-1)
Substituting in Eq A.32 along with using yyL²0² < 1 min x Tr( Vx1 Tr
we have,
Bn < (1 + 4n/2 1000""1'00 A2 Tr (E)) 8n 100n 2 2 Tr (Σ)
On 88-188n11
+ 600n7 L N
Hence proved.
30

---

Lemma A.2.11. Let U E Raxm and ~ N (0, Id), then for all n 2 0 we have
E B UU SUUTBBBuu E [ B UUT B + (VT
Proof.
E
U0 B
T UU
uo
E Tr (uo A, UU vo)
E [E [Tr (U" BB, moug U) [Bm]]
E [Tr (U" B, Loon [Bn] U]]
E | (UT B, uouu U)
E Tr BU)
E [Tr (U* B u B + [T (U" BVV
= E [u] UU m + E Tr (V? B UU BLV
Lemma A.2.12. Let U E Rdxm and N (0, Ta). then for all 2 0 we have
(UU" Bruo) 2 6E (bf B..)) + 6E Tr (V UUT B.V1)'
Proof. Let the eigendecomposition of UU Bn for fixed Bn be given PAP such that Pp = pI = / and A 0. Denote uo u and y == p Therefore,
E (ug UU Br
= E
PAPTu) u) 2
d
= E
X [uA]] + Σ
A [
(A.33)
1=1
Note that E PTB [u] 0, E 1yy"
P uux p= pT p Therefore, y N (0,
Therefore, [ and [u:'}] = [y
[
= 1. Therefore.
E
BUT 20)) 2]= =3 Σ
x2 + Σ X
(A.34)
1=1
i
Substituting in Eq A.33
we have
d
E
u1g T UU Bnuo)²
21
= Σ
X² +
Σ
Mdd
Ardj
d
27
$ 3E
X
Tr (B.UUT B²)
3E
( (of UU Bavi) (
3E
6 E
(UT Buoi) ( (VT
31

---

A.3 Proofs of entrywise deviation of Oja's vector
We first state some useful results here. Let og = =1 (1) b0- Tr (VT c 7 V=)= = 1 in (i) Let
the learning rate, 77, be set according to Lemma A.2..4 Note that S exp (z), Vz E R. From Lemma A.2.7 we have
E
[bf Bnei) s 21 1 +88 "
ao ant
411
(bu + aw))
(A1 - -122
471
S (2m + 8L 40 + 111
(bo + a0)
(A1 A2)
(A.35)
E [rr (VT Br Brese T B }]
s bo (1+ (1+21)22 + 1L A/ A2 Tr (E) + 4L 11"00"1217
471
Tr (Σ)
b0) )1 (1 (1+27>) + +8L
+ nd
(A1
(>1-10) X2)
40
s bo exp (2mmid2
4I, "I==0"nn'ng Tr (Σ) +1.
421
Tr (Σ)
+ ni
bo exp (2mmd) 8L 80"00'1''0 0
(A1 x2)
À1
(A.36)
Similarly, from Lemma A.2.8 and using (a + b)² I 2a. + +2b?, we have
E (of Bacs) 9 $ (1 2 + 1000400)227) 2n
a0 + 1121 ( 4h1
x2) ) (bo + av)
2
(11 (x2)
(A2 - 2x2) ) (bo + ao)
4h11
2
exp (4nm)) + 2000''0'
40 1/111
(A.37)
E Tr (VF Bneee )
< 2b (1 + 21/22 + 550 X2 (E) + 50L*04,222 2n
2 n1 ( 2\1
Tr (2)
+ 60 (t-20)
(1 - 2Td11 + 1,22 20
0(21 A2)
40
X
$ 2bg exp (4mmd2= + 1000 nL
4 0 X2 Tr (Σ) + 100L o² 22n²n2?)
4x1
+ bn Tr (E)
+ nd
(>1 (A1- A2)
a0
X
exp (4mmA + 200L
(A.38)
Finally, noting that (1 + x+) 2 exp (r x²) Yo 2 0, we have
E (bea))))
R 7u Bnes] )² 0n (1)² (1 m/11)) )m 2 v1 (i)² exp (2mmá1 2n)"
(A.39)
Now we are ready to provide proofs of Lemmas 3.11 and 3.12
Lemma 3.11 (Tail bound in support). Fix a 8 e (0.1, 1). Define the event G == threshold Tn == 5_ for absolute constant Ch > 0.
|u un
ye
5
and
V2e min
+ Let the learning rate be set as in Lemma 3.1 Then,
WES, P Irils Tn G)()) ())
s Ch ydi log (n) + +ndi
A1
1
{1
A2
(1)2
11
32

---

Proof of Lemma 3.17 Let do = avi + rrg for uT = 0 and = 2 01, and b = up T1 E R for
some vector 1 orthogonal 21. Then Vi S.
mms Tn - r S و + (eBu)) S T
a² (ef Bnui)² 2 + +b2 (ef Brul) )² S Tm
= a² (e) Bnui)
)
?
S 7
(A.40)
Then,
P Imils 9) SP a² (e (e." Bnui)
S -m 9
uusin Eg A.40
ET
P
(ef Buu))
9
82
=P (cf (ef
CT
(A.41)
82
For convenience of notation, define Yn == _ nn and qi = le. B, v1 Then,
(et BBu)) x
eT
P (q: S 7n)
82
z PP (Ig: EE [q:] 12
E [qs] 7n); [qs]
PP (/q: - IE [4:] I
IE
E [q E [q.]
using Chebyshev's inequality
(A.42)
(ITE) [a:] 1-7m)²
E [(u] BTT esee B1)) - E [of B e:
(A.43)
B [uf BTd e.] | 1 v2
(minses/v (1) + )²)
T;
We now bound T; using Eq A.35 and Eq A.39 as
exp (2mmA1 + 8L 1 n)))
(i)² + n11 (( 4A1
(A1-)z) -22 )] -01 (i)² (1+) 2n
T, I
(101 (1)
min 11 (i) 1) (1 + 1721)2²
exp (2nmd1 8L 0 n2)))
01 (i)² + n/1 (A1 (A1-Aa)
121
01 (i)² exp (2mmi 2072
(lw) (i)
2 minies (1) (i)
2
exp (2mm)))
-21
exp (4 + 1) n>
U1 (1)2 + 1711
(A1 (A1- ( )]
4A1
11 (i)
(I01 (-) min:esly (x) 1)2
2
The second inequality follows from the fact that 1 + x 2 exp(x - x²)) for 2 0. Note that for E (0, 1), exp. < 1 + 2r. Therefore, for (8L + 2) nd < 1. we have
(exp (AT.A + 1) n2 - 1) in (i)² + 3m121
14,
(11-22)
T, <
(11 (i) min 11 (i) ²
4 AALLO* 1) 12 ni (1)² + 3nd11
4h1 (11-12))
<4
21 (i)²
3//i1 (Ai-
+ +1) (1
=4
+
U1 (i)2
The result then follows by using Claim(2) in Lemma A.2.4
33

---

We next provide the proof of Lemma 3.12
Lemma 3.12 (Tail bound outside support), Fix a å (0.1, Let the learning rate be in
Lemma 3./ and define the threshold Tn = 5 min Un (i) [1 + nd1)". Then, for min; |01 (t)
Ω
A1 A2
and absolute constant CT > O have,
$ (r]/ Tm) CT ?²>? A X2 )x)²
)
27
82 min "1 (i)²
Proof of Lemma 3.12 Note that for i $ S, 0n 0, b. = 1. Therefore, we have,
411 1 B e B s exp (4mmd) + 2000 1))2))))))))) nd1 (A1 - -M)))2)) )}²
using Eg A.37
(A.44)
Tr (V] B ce B s 2exp (4mm>2 + 100m log (n) L X2 (Σ) 1000
(A1 4h1
(
) exp (4mn11 + 200L"
+ nd
using Eq A.38
(A1
(A.45)
f B esee Bavi] S exp (2mmt2) + 8L 8L8 11²(1())))) 1//11 ((11 (1>((1a111))
4 )
using Eq A.35
(A.46)
E
Tr (V B e B v1)] S exp (2mmd2 + AL o 122 Tr + 4L"00122213
4h1
) exp (2mmA1 + 8L 0 n)nn))
n/11
(21
-x2)
using Eq A.36
(A.47)
82
min (1)) (1 (1+ m)1)"² 2
5²
min u1 (1)²)
exp (2mm)) 20)² using Eq A.39
2e
EES
2e
ies
(A.48)
Define
0= T. E [r?]
(A.49)
Note that using Assumptions
16end1
(A1
3 3log (n)
128cA1
768e
log (n)
< 82
x
min:es U1
(i)²
(A1 - )2)
minggs 8i (1)
minges vi (i)²
where the last inequality follows for sufficiently large mentioned in the theorem statement.
Therefore, using Eq A.46 and A.47 along with Claim (3) from Lemma A.2.4 gi is bounded
82 min in (1)²) exp (2mmA1 -212n2)) - exp (2mnd2 + - Tr + 41.00112227) iES
2
4e
2 exp (2mmd11 - 2n7) (8)
(min (1)2) - exp (-0mn (A1 - 22))
de
ies
28a
vin (1)²) exp (2mmd) 20721)))
2 96
(A.50)
ies
34

---

where the last inequality used Claim (4) from Lemma A.2.4 Therefore, we have,
P (1r)> Tw.) = IP (r? > n
= IP (r? - E [r]]
> n - [r]],
< IP (Ir? E [r]]]
>> - B since from Eq A.50 y; 2 0
E (17 - IE [r]
(FR E (r2))
E [r]] - E [r3]
(T2 E (r?1)
(vo BI c Buya) 21 -E [uō B c B,,yo]
E
Rg (A.51)
minies U1 (1)²) (1 + 1//1)" (E vo By e:e? Bayol)
We now bound R. Therefore,
E
(vo BTT in Ciee Buyo)²
R,
min (1)²) (1 (1+ - (IE [y Bhe e,e Buyel
6 (B (of B ete, BrU1) +E Tr (VT B ere, Bav1)²)
msn e1 (i)²
(1 m/)1)) ) [u] BT. c v1
[T (VF c,ce B vi))
22
where uses Lemmas A.2.11 and A.2.12 Denote the numerator and denominator R2 as N (R.)
and D (R:). For the numerator N (R,) using Eq A.44 and A.45 we have
4A1
2
2 3 exp exp (A1 X2))
N (R.) S 18 a/i1
exp (4mm) + 200 4 22)))))) (1+
(A1
A2)
4h1
]
s 20
nd1
cxp (4mm>1 + 2000
(A1 - (2))
where the last inequality follows from Claim (4) in Lemma A.2.4 For the denominator D (Rt), using A.50
8t
min 0 (1)) exp (4mmA1 2))))2))))
D (R.) of
20c
Recall that for x E (0, 1), cxp (x) + 2z. Therefore, for (100L + 2) n)2 S 1 which holds
due to Claim (2) from Lemma A.2.4, substituting in Eq A.5I we have
400e² (4\1)²
TP [|mr Tn) S
1222
(A.52)
84 (minges of) (A1 )²))
A.4 Proof of convergence for support recovery (Lemma 3.1 Theorem
3.2
We start with the proof of Lemma 3.1
Lemma 3.1 (s-Agnostic Recovery). Under Assumptions
12 for min; wng (i) π
A1- (14) (
A
$ - OjaSupportRecovery ((X:)ietm) k, = 3 31)g(1)
-2)) with satisfies, S 2 0.9.
Proof. Let 8 = { $ and set = 1. for this proof. We upper bound P PEE))
Define
50
Ts = e, B, E [d]. Observe that
E 3r. 0 such that ( E S. Im/2 T.) N Im T.))l s)
35

---

or equivalently,
8 VTn > 0, (3i In n.) g
Therefore, for any fixed > 0
0 E S. Tm Uffiii S. ss
Let g bound,
5 { 109 lof/uoo2z
vel } and threshold Tp = v2c
min u1 (i) [1 + n711"".
Using union-
((89) (13i E 8, Inls T. + P (1(i : i E S.
mr/2 Tr H| > k - -)
< (13i E 8, 111l m.))) Eigs (1r:12 Tm)
using Markov's inequality
k-s+1
P 3i JiE S, T. 0/(0) +P())) 3i S, Tn g
Σ Eigs P (1r/22 nn)
-s+1
Eigs (1r Tn)
(P)) +P
3i BiES, S. Tn 9 +
k-s+1
Ligs P P(rr |r:|2/ Tm)
<P((9) + ΣE P
Insls Tm
9
--st1
iES
Eies IP (Iri|2 Tm
$ SP)()) +
Σ
P
[m/s
Tm ④
+
h - -
iES
72
T.
Using Lemma 1 we have P (99) S 5. We bound Ti and T2 using Lemmas 3.11 and 3.12 respectively. Therefore,
(A1 d1
(( < Cn ndii (11) + t1111
x2)
(i)
VES
27
d1
)²
+ Cr 1/2?
(d ad-s) 8)
Xx
82 minies vı (i)
< 56
where the last inequality follows by using the bound on n.
Next, using Lemma 3.1 we prove Theorem 3.2
Theorem 3.2 (High probability support recovery). Let Assumptions 7
2 hold. For
dataset D (Xi)ee(n) let A be the randomized algorithm which computes S + OjaSupportRecovery ( ((X))eem)) k. where 1) n(A1->a) and k: 8. Then, for (0, (0,
3log(n)
min; [1 (i) Ø xy -x (15 ))). S + SuccessBoost (Xitiet))) .A)6) satisfies,
(
P ( SS) 2-
Proof. Consider the set T (8 S C [d]|s|= $s with the associated metric (S) 1S # S').
Then, Lemma 3.1 shows that the ConstantSuccessOraceel (D, 2.O.T.P.. S,0) (Definition 3.9
randomized algorithm, A is
Therefore, the result follows from Lemma 30
36

---

A.5 Proof of convergence for sparse PCA (Theorems 3.5 3.7
We start by providing the proof of Theorem 3.5 Section A.5.1 and then provide the proof of Theorem in Section A.5.2
A.5.1 Proof of theorem 3.
Let 0 =
B Mi B
Then, for any subset S S S (obtained from a support recovery procedure such as
woll
Algorithm the corresponding output of a truncation procedure with respect to S is given
[ 5
13
1g uD
trunc
(A.53)
1
Bn wo
2
We first prove general and flexible result that bounds the sin² error function of B,, (see Eq 3 and analyze the performance of Vtrune by viewing it as a power method on wo followed by truncation using the set in the following result.
Lemma A.S.1. Let Bu, and virune be defined as in Eq that S IL Bn, wo. then with probability at least - 6
3 and Eq A.53 respectively. For S S [d] such
sin² (Etrunc: 01) Colog (1) 82
Tr
BT (Ig 1321e7 11 Bn
of B ss Bu
Bn
where C is an absolute constant and 6 E (0, 1).
Proof. Using the definition of sin² error,
11 T I= Bn wo |33
wi Bi (13 1ggioo BawD
sin? (Vtrunc, 21) 1-
(A.54)
w/ B 1 13
For the denominator, with probability at least
(1 8), we have
82
8² BTBBI
w/ B 13 w/ B /nsssnBBnnn. Bg
Tr
B Bn)
I Buri
(A.55)
e
where (t) follows from Lemma A.2.1 For the numerator, using (2 from Lemma 3.1 of [JJK 16). with probability at least (1 8). we have
(1) Tr B (1s - 13vee B,,
w/ B [1g Ige1e 1g) B BR S Colog
(A.56)
Combining Eq A.35 and Eq A.56 with Eq A.54 completes our proof.
Lemma A.5.1 provides an intuitive sketch of our proof strategy. Following the recipe proposed
C Clog( (
Tr B (I-- Loviv (a) B..) For upper- of B B.
in JJK 16). show how to upper-bound en
6²
5n8
bounding the numerator, we bound E Tr B 1/3 - Lzv1u? 1s)
B,
and use Markov's 's inequality,
To lower-bound the denominator, we lower-bound E
upper-bound the variance E (uT snn and finally use Chebyshev's 's inequality. A formal analysis is provided in
of BA sns B,
the following theorem
Theorem A.5.2 (Convergence of Truncated Oja's Algorithm). Let S C [d] be the estimated support set, such that S 1L Bn, we (see Algorithm 2). Consider any event E solely dependent on the randomness of S. Define:
W3: = E [/ Ig 13 1 G3 E [1s-- E|]
On = of Wgrn. 3o = Tr (VF Po == of Ggm, 40 = Th (VFCgVi
37

---

Fix 8 E (0.1,1).
Set the learning rate as = 3log(n) x()1- Then, under Assumption 2 for
A (on(n) and pu (1+ + 16) S + 271118 (1a--2a)) ) we have with probability at least
21-22
1 PP (
C' C'log (3)
X1
ao (1 21 Ir (E)) 2n
sin? (Utrune, u1)
83
X X2
Po
where Vtrunc is defined in Eq A.53 and C" > 0 is an absolute constant.
Proof of Theorem A.5.2 We first note that from Lemma A.5.1 with probability at least 1-6 8,
Cloog (1)
Tr
B 1/ Izuio Br
sin (Vtrunc. m) v 2²
(A.57)
of BB s sn
Next, we bound X. conditioned on the event E. Using Markov's 's inequality, we have with probability at least 1 - 6,
Tr
BT
(/3 - 13-1go1 13) Bn)
E
Ir
BT (13 (geieils) Br, E
8
of Bi (13 -/- E
Br E
E
Tr VF (33-1o BnV1) 3
of W W3 Broi E
Tr (VFBB W W3Bnk))) +
using S IL. B,
(A.58)
8
Note that (1+ S exp Vor R. From Lemma A.2.7
we have
of B W3B. s {1+ 2m + =8
ap + nd11 (A1 -N2)
4h1 )
)
(80 + an)
(A.59)
Tr Vi BT (WWBaVV
I Bu (1 + 27/22 + A4L (T)) +
411
TT + 30
+ 1
(1 + 21A11 + xT7
(>1 X2)
A1
T2
4
exp (2mm)1 + 8L 4 " 12))
80)
(a1 A2)
+ 30 exp (-20mm (21 22)))
a0
Tr (T + 80) (
4A1
< 2exp (2mmA1 + 81 0 7
mnd)
1//1
(A.60)
X1
()1 Xz)
where the last inequality follows due to Lemma A.2.4
Substituting Eq A.59 and Eq A.60 in Eq on the event E,
A.58 we have with probability least (1 - 6). conditioned
12A, (oo (1 + 2n Tr (E)) + 20)21
exp (2mmA1 + 0T,20413222)
Tr [.TT (13 (3) Bn)
(A1 (Ai-
8
(A.61)
38

---

Similarly, for the denominator we have with probability at least conditioned on the event &
8 using Chebyshev's 's inequality.
E
ut B
B U1
3
of B B 2
of B
U1
3
1
5
oi Bu
B u1 E
5
(A.62)
Recall that po = E
1 sss 8
vn.
Using the argument from Lemma 11 from
UJK 16 and
S IL Ba.
E of BuI
ns
3
E of
B
I
$ E
B 01
2 po exp (2nm)) 41/(127) (A.63)
This is since the base case of their recursion,
JJJ + 16 has of Iuj which is 1, but we have
E
sus 3 which is defined po-
Next, using Lemma A.2.8 noting that of sus + Tr VF (vFlensk)) Tr m'(ss))
have,
BT T Bal L B
< (1 + 21/21 + 100I4097227) 2n
+ nn If
-22) -2))
411
Tr
I 1sss
(11
$ <(1+ 27/11 + 1000 2n
sttl + oefisnsi
(x)-)
4h1
-22)
4h1
421
27
S Lexp(4mmda + 200L'0 x Po
()1 21/21810 Po +
(-1- -x²)
+ 11118
(A1 - dx)
(A.64)
where in the last inequality, we used ouft s )² s of sss S 1. For convenience of notation, define
4h1 ) +(nis ndis (A1 A2) )) < )) (A1 (M1))
4A1
Po 2nd1spo
where we used 17ii8
4A (A1-)a))
< y (due to Lemma A.2.4 and Po S 1.
Substituting Eq
A.63 and Eq A.64 in Eq
A.62 and we have with probability at least (1 8).
39

---

conditioned on E of BrG
1
Po exp (2mpA11 nn))
1
+x n22
exp (11001 4)
v8 V
p6
2 exp (2nmX) 4nf229f)
(1 + 2 2100L 4) 17 nf
v0
D6
pb
Po exp (2mn)1 2172117)
(100L - 4) n2
v8
Pb
Po
(8)) Pu
exp (2mmA1 4n))
(A.65)
2
where (i) we used (100L + 4) nrnn S and x (0, 1), exp (x) S + 2x. For (ii),
suffices to have
Φ - Po
2
8
Φ
8
(100L'0* + 4) 1 v
Pú
Po
16
which is further ensured by,
1 + 2mpis
(A1-Aa)
41
4mdi 8
(Ai-
4h
(100L + 4) 12
po max
1
5 16
v8
81
Note that for the choice of 1), and 8
I0. we have using Lemma A.2.4
1
+
21
4A [A1-A0]
AmA18
(Ai
42
A2)
(100L4
+4) n2
8V
v8
16
for sufficiently large n. Therefore, we only ensure that Po is greater than the first term in the theorem statement. Finally, let
C' C'log (2)
A
ao (1 + 2n Tr (E) + 27
83 A1 - A2
Using Eq A.6l and Eq A.65 and substituting in Eq
A.57
we have with probability at least 1 - 26,
conditioned on E, x S &, or equivalently
x 2
< 25. Therefore,
P(x 2 2) = P x ( + (
122
SP
P
x 2 2 + +P(E9) s 28 P
The proof follows by making smaller by a constant factor.
With Theorem A.5.2 place, we are ready to finally provide the proof of one of our main results,
Theorem 3.5
Theorem 3.5 (Vector Truncation). Let Assumptions 7 and 2 hold and l 2 s. For dataset =
(Xi)een) and wo .' 10, let A be the randomized algorithm which computes étruncvec f-
3log(n) TruncateOja ((Xthie( (g.m] Sja,, Oja, (17, wot). where 17 = -2)) Then, for min; lal (i)
ō +- SuccessBoost (1 ((x))se))) A. dd-1) satisfies.
A1
A: log" (d)
sin ( < C"
A1 -
with probability at least 1 - 10 where C 0 is absolute constant.
40

---

Proof. Let E == Shi S $ and set : for this proof. Consider the following variables from
Theorem A.5.2
W = E [/ Ig 13 18], G3:= [ (3:=x('sns El
0g = = W 1 := Tr (VT TT po = of G3r1 20 = TT (VTCgV1)
Since |S|= k, therefore,
8 = 1r (VIWsV S Tr (Ws) s Ir (5) h
(A.66)
Furthermore, under event & Sni S { Therefore,
e1 (i) log (n)
oj G3u1 2
Σ v1 (1) = Σ
using definition of Sp (A.67)
REShi
S
To verify the assumption on po mentioned in Theorem A.5.2 it sufficient ensure
20
<(1
log (n)
2)
8 n/As
+
A1
A2
which is true by the definition of 7) and n (see Lemmal A.2.4.. Lastly,
oi Ig (uf )²
cg = W = E
< - E 1g El using of /z"1 S
< 1 Σ 1i (i)2
since Sn S S
iESH
log (n)
Σ
(i)²
(A.68)
SW
Therefore, using bounds on 3p Po and on from Eqs A.66 with Theorem A.5.2 with probability at least
A.67 and A.68
respectively, conjunction
C' log (t)
5
sin 2 (Uojay U1) <
(A.69)
83
X
A2
Using Lemma 3.1 TP (8))= < 55. The result then follows using Eq A.69 and setting smaller by constant.
A.5.2 Proof of theorem 3.7
We first state the result from Lia23
achieving the optimal sin' error rate for Oja's Algorithm.
Proposition A.5.3 (Optimal Rate for Oja's Algorithm with Subgaussian Data (Theorem 3.1, Lia23] ))
Let {Xi]iejm) be i.i.d samples from a subgaussian distribution (Definition 2.1 with covariance matrix, E, leading eigenvector U1 and eigengap, A1 >a > Then, there exists an algorithm OptimalOja which operates in O (d) space, O (nd) time, processes one datapoint at a time, and returns an estimate é which satisfies, with probability at least 1 5, (0,
sin? (0,01) SC A1d2 dlogg (+)
(A1 - 22))
where C' is an absolute constant.
Theorem 3.7 (Data Truncation). Let Assumptions T and 2 hold and k 8. For dataset D = (Xiheem) and wo N (0, 1), let A be the randomized algorithu which computes tcruncvec t
41

---

TruncateOja
{(xx1s) sE(#.n]
S, OptimalOja, ffm he( mub
Then for min; (01 (i)
d $1 }). Ü+ + SuccessBoost (( ((itveem) A d 10 satisfies, A1-1a nz
\1
k log (d)
sin? (Ū, v1) I C"
(A1 x2)
with probability at least d where C 2 0 is an absolute constant.
{ $..
Proof. Let 8 == Define the event 3
Using Lemma 3.1 we have that
P (E) 2 -
Let X = sin? (Otrumever, u1) and & := C. A1
& *log(t) (+) for absolute constant C >> 0. Therefore, (Ar 22)²
x E {
+ +P P 8
< P
x 2 {E)
+ +P(
$ P
x268
+
(A.70)
Therefore, next we bound sin (0trunevec: U1 E
Therefore, we seek bound the sin? error
after truncating the data using the true support, S. Note that
E [[ [s] = A + IIVVLAVVI
Therefore, after truncation, the leading cigenvector and eigenvalue are preserved, and the second largest eigenvalue is most X2. Furthermore, the truncated distribution is still subgaussian, and therefore Proposition A.5.3 is applicable here and we have with probability at least 1 - 5,
sin? (êtrumcvec: U1) S
(A.71)
Eq (0.70) and (A771) show that is a ConstantSuccessOOrade (D, (7, k), T, O (k log (d) /n))
(Definition 3.9 for the set T {u: u Rd ||u||| 1} with the metric p pu, Juu
vo
F 1/ |sin v)). The result then follows from Lemma 3.10
A.6
Alternate method for truncation
In this section, we present another algorithm for truncation, based on value-based thresholding. complementary to the technique described in Section 3 The proof technique uses the same tools as the ones deseribed Section 3 Both Algorithm and may be of independent interest depending on the particular use-case and constraints of the particular problem. Theorem A. provides the convergence guarantees for Algorithm 4 Note that compared to Theorem 3.5] Theorem A. provides better guarantee for the sample size. However, this comes at the cost of the sparsity of the returned vector, ooja-thresh not being a controllable parameter. We can however show that the support size of toja-thresh is (s) in expectation. For the purpose of this proof, let
d: :::EE S, (1) log(d)
Sm
Theorem A.6.1 (Convergence of Tja-hhresholded. Let oojathhresh S be obtained from Set the learning rate as π =
Algorithm
3 3lg A2)
Define threshold Yo >=>))==))) ))) have
3 minees
(V1 (11 + n. Then for H minneey 21(3)
4v2c
E
| < O' and with probability least Z1
A1 (,,,,,,)))))) -
2 max {s, log (d)) log (d)
sin? (Boja- SC"
Sn S $
where C² 0 > 0 are absolute constants.
42

---

Algorithm 4 Oja-Thresholded ((X)) 7n.
1: Input: Dataset (ett learning rate 7) > 0, truncation threshold Yn
2: Set bn 0 and choose yo, wo ~ / (0,1) independently
3: for in range[1, 3 do
4:
+ [I + v) )9t-1
5: Un +
bn log (1)))
6:
Tloella
Wt
7: end for
8: S +
Set of indices, E [d]. such that log (lef Hol) + bn log (7r) 2 0.
9: 1 + Oja (Ex:) 27, wo)
10: oja-thresh
11: return
i foja-thresh
S
Proof. Consider the setting of Theorem A.5.2
Set == for this proof and let & be the event
lof vol2 Vel
5. }. By Lemma A.2.1 P (E) 2 8. Recall the definitions,
W3: E 1/ Is 1g g) G3:=B (
ag == of Wzen, 8 = Ir (VIWzVi) po = Ggo
We upper bound on. 3 and lower bound Po under the setting of Algorithm of B,Do, [d]. For oo: Po. have
Define Y; =
(u (o[Izu)) 2
) E
au WgW E
of Ize1
E
of 1311 (1
of 1zu1) E
< - E
1i 13
I
[ using of Igoi $ 1
Σ
21 (i)² P
( (iESiiE
E8
Σ 11 (i) i (
(A.72)
ES
Po = of GTGu
of Bsss v1
Σ ur P (1E3)ES(E))
iE
Un (i)² p ( ( 3:1
= 1
Σ
(A.73)
iES
43

---

Therefore, for both cip Po. we seek upper bound Eies 11 ( P i Si e s|e)
We have
Σ 01 (1) @ (
Σ 21
(1)
i i (=
+ Σ
es (1)
( (
ES
VE
KEStSh
s slog (n)
Σ
1 (1)
i (
n
iES(SN
s slog (n)
Σ
v ( F
|r/l Mn S s|$)
n
iES(SN
(0) slog (n)
A1
1
+ +CH Σ
v1 (i)
nd1 log (n)) + nd
n
A1 x2
U1 (i)
BES)SH
s slog (n)
Al
CHπd log + CHnd1s'
(A1 - x2)
1 s CHHA log (n)} S 2
log (n)
using l0 (1) 12
i E Shi
For So we have
i 8 - -E (i) P iE ii $
8o - E
Tr
W
=
Σ
P
KE
iES
$
Σ P
E
5/
Σ
[ 1 u (1)² P iE E ()= = ===
(ES()
i (EEEE) + 1
i08
iES
iES
P ((r 2/m)
Σ P
[r//2 Yhe 3
+ 13-1= 1= Σ
+
(()
igS
IP ((ri/2 7n.
+ 1, since IP (g) 1-8
igS
A1 d1 [
2 )
$ $2Cr
7 (d - 8) + using Lemma 3.12
Xo
82 min U1 (i)2
< 2s, using bound on n
The result then follows using Theorem A.5.2 and substituting the bounds on on, Bo and po. Finally, note that using a similar argument as Theorem 3.5 we have
Sm & S1E) - Σ
i t S: E Sma E)
ieSu
Σ P
|rik
miteee))
S SCH
End log (n) + t111
n
d1
A1
Xx2
21 (i)
RES
iESm
A1 T1
1
S CHndis log (n) + CHnAi
56
X2
Ui (i)
SES
using the sample size bound on n.
44

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We present a O (d) space and O (nd) time algorithm for Sparse PCA for general covariance matrices.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section 3.2 shows that we handle general covariance matrices in nearly linear time, albeit a worse sample size.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
45

---

Answer: [Yes]
Justification:
All Proofs in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Figure and Figure 2 contains the experimental setup in the caption. Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
46

---

Question:
Does the paper provide open access to the data and code, with sufficient instructions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We make the code for our experiments available in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips. //nips.cc/pplee wttpcccpppppccceeeeeee.ee..c.lct guides/
http:/uuuuieeeeeeeebiabeeeeeee hat////ooeeeessseeeeeeeeee SesSSuumiisionii wwwsssoiiccciioicccooooociisiiii for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Figure la and Figure 2 contains the experimental setup in the caption.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Our experiments were performed single Macbook Pro M2 2022 CPU with 8 GB RAM.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" the results are accompanied by error bars, confidence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
47

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative етгог rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: Figure provides error bars over 100 random runs. Figure plots average over 10 runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Fthics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///wwaaapcc.oooo/oo/aaattaa
Answer: [Yes]
Justification:
We abide by the NeurlPS Code of Ethics in our work.
Guidelines:
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
48

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not release any models
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: There are no datasets or existing codebases used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
49

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, datasets.paperssiii wwwppppppttthhhoco thcode www.coo//aaaa/o datasets
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets to require documentation or licensing.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We only use simulated data for our experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
We do have experiments with crowdsoureing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
50

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
51


Reviews:
[{"review_id": "5obhUq9fRF", "reviewer": "Reviewer_pD6C", "summary": "The paper studies Principal Component Analysis with O(d) space and O(nd) time, where n is the number of datapoints and d is their dimensionality.\n\nThe authors provide the first single-pass algorithm that under a general \\Sigma matrix whose top principal vector is s-sparse, manages to find a close enough vector in the sense of the sinus-squared error. Their main theorem is Th. 1.1. which states that under a structural assumption on the effective rank (ratio of the trace and the principal eigenvalue of the population covariance matrix Σ) not being too large (the function involves the spectral gap and the top eigenvalue).\n\nTheir algorithm relies on Oja's algorithm and the authors show that w.h.p. the Oja vector when initialized by a random unit vector, will actually converge to an output whose top k entries in terms of magnitude will include the true support of the s-sparse v_0. Then, the authors can ue the recovered support and achieve minimiza optimal sparse PCA, thus improving upon several prior works.", "questions": "Some typos: \n-matrix multiplication constant is not 2.732 as written.", "limitations": "-", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+very interesting and well-motivated problem\n\n+clean framework and clean algorithm\n\n+novel analysis and simple algorithm that improves upon several prior works", "weaknesses": "-no serious weaknesses", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your kind words regarding the problem statement considered, the simplicity and performance of our algorithm, and the novelty of our analysis. We will correct the matrix multiplication constant to ~2.372 based on recent developments (see [a]). \n\nReferences:\n\n[a] Williams, Virginia Vassilevska, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. \"New bounds for matrix multiplication: from alpha to omega.\" In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3792-3835. Society for Industrial and Applied Mathematics, 2024.", "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": "", "extra_scores": {}}, {"review_id": "4nlpUrlwrI", "reviewer": "Reviewer_zu7o", "summary": "The paper studies the problem of streaming sparse PCA under iid data. That is, we have $x_1,...,x_n \\sim \\mathcal D$ iid vectors in $\\mathbb R^d$ which are revealed to us in an online fashion. We want to estimate the top eigenvector of $\\Sigma = \\mathbb E[xx^\\intercal]$. We assume that this top eigenvector $v_1$ is $s$-sparse, for $s = O(\\frac{n}{\\log(n)})$. The error between the real and estimated top eigenvector is computed using the $\\sin^2$ error metric $(1-\\langle v_1, \\tilde v_1\\rangle^2)$. \n\nThis paper shows that Oja's algorithm can be used to both find the support of $v_1$ and the values in $v_1$ (assuming we are given some value $k \\geq s$ and correctly choose a step size parameter).\nThis algorithm runs in $O(nd)$ time and $O(d)$ space.\nThe key technical assumptions made are:\n- The data is iid subgaussian\n- The sparsity of $v_1$ is $s = O(\\frac{n}{\\log (n)})$\n- The effective dimension (ratio of trace to spectral norm) of the covariance matrix is at most $O(\\frac{n}{\\log(n) \\sigma^2})$ where $\\sigma^2 = \\frac{\\lambda_1}{\\lambda_1 - \\lambda_2} \\cdot \\frac{\\lambda_2}{\\lambda_1 - \\lambda_2}$ measures the (square) of the singular value gap between the top two eigvals of $\\Sigma$.\n- The smallest nonzero entries of the (unit vector) top eigevnector $v_1$ is $\\tilde\\Omega(\\frac{d^{1/8}}{n^{1/4}})$.\n\nIn contrast to prior works, this work achieves better $\\sin^2$ error that prior $O(nd)$ time algorithms and $O(d)$ space algorithms. It also makes no assumption about the quality of the starting vector (i.e. it's not a local convergence result, it's a global convergence result).\n\nThe results are essentially all theoretical, with one experiments used to show that Oja works well here, and another used to elucidate which theoretical bounds are loose.", "questions": "None of these are game-breaking, and many of these are minor typos. Feel free to ignore whatever feels unfair to you. But, do at least make the notation for the initial vector consistent and make the figures easy to read.\n\n1. Annoyingly, the authors __very often__ swap the symbols $y_0$, $u_0$, $w_0$, and $z_0$. Please fix this.\n1. Figure 1 is too hard to read. The letters are too small. The axes have no labels. The error is negative somehow (if it's plotting $\\pm1$ standard deviation, which is making the error bars negative, consider using 25th and 75th quantiles instead?).\n1. It's not clear if Lemma 3.1 and Theorem 3.2 allow us to use over/underestimates of $\\eta$, or if the theorems are very tied to that exact value of $eta$. Seems worth discussing.\n1. It's not clear why Theorem 3.2 requires $k=s$ instead of $k\\geq s$. Discussing this would be nice. Returning a vector whose support is $\\log(1/\\delta)$ times larger than $s$ seems fine to me, if that's the issue here.\n1. Prop 3.4 is written a bit unclearly, namely around the \"with sparsity parameter, $n=$\" part, since $n$ is not a sparsity parameter.\n1. Theorems 3.5 and 3.7 uses failure probability $d^{-10}$, which is fine I guess? But why not just use a $\\delta$?\n1. Remark 3.6 seems like it might make more sense to have back around assumption 2\n1. Section 3.4 strikes me as a very standard analysis style. Not sure why you point to [KLL+23] specifically. You can say it's standard, and point to [KLL+23] as an example of this, maybe? If I'm missing something and it's not standard, lemme know.\n1. Figure 2 is also too hard to read, especially in print. The letters are too small. The series look too much like each-other. The y-axis should be more specific in the error. It's not really clear what the dotted / population lines are showing -- is it $\\log(E[e_i^\\intercal B_n u_0])$, or is it $E[\\log(e_i^\\intercal B_n u_0)]$? Is it something else? What exactly does \"error\" mean here?\n1. Line 221 can use $E[r_i | u_0]$ imo\n1. Idk why equation (4) uses absolute values and $\\pm$ on the non-top-eigenvalue terms. Isn't $E[B_n]$ PSD, and thus the second term guaranteed to be nonnegative?\n1. Line 221 maybe mention that $E[B_n] = (1+\\eta \\Sigma)^t^?\n1. Line 232 this line about [SSM11] taking $\\lambda_1 = d^\\alpha \\rightarrow \\infty$ is kinda confusing because it's not a scale-invariant claim. Is it like a condition number that's getting large?\n1. Line 238 should mention that Section 4 explains the technique a bit more in detail\n1. Line 247 should really point to Section 4 as well, explaining the technique in a bit more detail\n1. [Line 256] If you have space, it'd be nice to understand why Theorem 3.5 needs a more general argument that $U = e_i$.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is a nice contribution to the literature, and it's well written. Sparse PCA is an important problem, and handling it in low space and time is important as well. The error metrics and assumptions are all reasonable. The paper is written clearly. It's just sorta all around solid.\n\nThe result is original in that it has a clear goal: achieve the $\\sin^2$ error of large-space or large-time algorithms (those that use $\\omega(nd)$ time or $\\omega(d)$ space), but only using $O(nd)$ time and $O(d)$ space. It's especially nice that a pretty naive application of Oja's algorithm can achieve this.\n\nThere's also some nice novelty in the proof technique, which bounds the 2nd and 4th moments of the entries of the output of Oja's algorithm. In particular, the authors tighten a bound from the prior work by designing and solving a system of linear recurrences. A cool math setup that I do not often see.\n\nI'm not an expert in the sparse pca world, not the streaming pca world, and certainly not streaming sparse pca. That said, assuming the authors are not omitting any relevant prior works, this results on low error in very low space and time seems pretty cool. It seems like a particularly nice step in the sparse PCA literature.", "weaknesses": "There's a few notation inconsistency issues, some minor gripes. Nothing I'm really worried about. I'll push it all to the \"questions\" section below.\n\nI accept this paper for publication.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your kind and detailed feedback and comments about the clarity and presentation of our work, the novelty of our analysis, and the significance of our contribution to the Sparse PCA literature. We will correct all the typographical issues pointed out and will not address them here individually. We answer your primary concerns and suggestions below:\n\n**[Re: $y_0, u_0, w_0$, and $z_0$]:** Thank you for pointing it out. We will take care to fix them in the final manuscript.\n\n**[Re: Over/under estimates of $\\eta$]:**: For step-sizes, we follow the convention in (Balsubramani et al. (2015), De Sa et al. (2015), Jain et al. (2016), Li et al (2017), Allen-Zhu et al. (2016)), Huang et al. (2021), where Oja’s algorithm is analyzed without sparsity and the optimal learning rate requires knowledge of the gap, $\\lambda_{1} - \\lambda_{2}$, and other model parameters to get the statistically optimal rate. Our sin-squared error roughly is of the form $O\\left(\\eta\\lambda_1+\\exp(-n\\eta(\\lambda_1-\\lambda_2)\\right)$. The optimal eta ensures that the first term dominates yielding our optimal error rates. However, a small $\\eta$ resulting from plugging in an upper bound on the eigengap $\\lambda_1-\\lambda_2$ may make the second term dominate leading to a suboptimal sin-squared error. We will clarify this further.\n\n**[Re: Figure 1(a) and 2(a), (b)]:** We have provided revised figures in the global author rebuttal document along with detailed explanations of each axis and the legend followed. Figure 1(a) plots the sine-squared error with iterations of the algorithm. The error bars currently represent standard deviations across 100 runs, leading to a negative error. We have now fixed that to plot the 25th and 75th percentile bars in the revised figure and added labels to the axes.\nFigures 2 (a), and (b) have also been revised with a larger font size and clear axis labels. The y-axis in Figure 2(a) has been corrected to read the “value” of the referenced quantity instead of “error” and dotted lines have been removed to avoid confusion. The line width has been increased to enhance clarity. The lines labelled “sample” plot $\\log(|e_{i}^{\\top}B_{n}u_{0}|)$, whereas the “population” curves plot $\\log(|\\mathbb{E}[e_{i}^{\\top}B_{n}u_{0}]|)$.\n\n**[Re: $k \\geq s$ in Theorem 3.2]:** Our probability boosting argument for Algorithm 3 requires a distance metric, such that when the true support $S\\in \\hat{S}$, $d(S,\\hat{S})\\leq \\epsilon$ for some small $\\epsilon>0$. And not only that, we also crucially need that $d(S,\\hat{S})\\leq \\epsilon$ implies that $\\hat{S}$ contains $S$. This is easily done for $k=s$ since the metric is just the indicator function, which returns 0 if two sets are equal and 1 otherwise. With $k \\geq s$, we were as of yet unable to create such a metric that would be amenable to boosting to high probability.\n\n**[Re: Prop 3.4]:** Thank you for pointing that out. It should read “with sparsity parameter s, such that n = …”\n\n**[Re: Failure probability and $d^{-10}$]:** This is primarily to show that the failure probability can be $\\frac{1}{\\mathsf{poly}(d)}$ without affecting the sample complexity or the error by more than a constant multiplicative factor.\n\n**[Re: Section 3.4 and [KLL+23]]:** Although Section 3.4 is reminiscent of a standard median-of-means type analysis, we were unaware of other existing algorithms that extended this framework to vectors, apart from techniques such as the geometric median(also suggested by Jain et al. (2016) for probability boosting), which may or may not return a sparse vector. One advantage of [KLL+23] is that they choose a vector from the given set.\n\n**[Re: Eq(4) and absolute value terms]:** As described on Line 221, the $\\pm$ notation is used here to describe the bound on the deviation. That’s why the second term has an absolute value, which is an upper bound on the deviation.\n\n**[Re: Line 232 involving [SSM11]]:** Thank you for pointing this out. Yes, you are indeed correct, this is indeed a condition number since the second eigenvalue is 1 here. We will clarify this in the revised manuscript.\n\n**[Re: General argument for $U=e_i$]:** We use other matrices in place of U, such as U=I_S, in the proof to handle truncation assuming knowledge of the true support. Lemma A.5.1 provides a sketch of which terms come into play and the corresponding values of U which are important. We included that in the appendix in the interest of space and can provide a brief sketch in the extended manuscript after revision.", "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": "", "extra_scores": {}}, {"review_id": "3jgNREXFZF", "reviewer": "Reviewer_jbhG", "summary": "The work proposes a one pass Ojas' algorithm which can achieve minimax error bound for high dimensional sparse PCA under standard technical conditions.", "questions": "Q: Can something be said along the lines of these results for other top eigenvectors of $\\Sigma$ (not just $v_1$)?", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is extremely well written. The proposed one-pass Oja's algorithm is novel with detailed convergence analysis and convincing numerical experiments to support author's claims. I appreciate the thorough literature review highlighting how the current paper improves on over the previous works (in particular Table 1). The relaxation on effective rank assumption is particularly notable in the results. The mathematical ideas in the proofs are easy to follow and contain several new techniques.", "weaknesses": "In general, I like the paper as it is quite clear and mathematically sound. In some minor places, the exposition can be slightly improved by defining terminologies before using them (for instance please define $\\sin^2$ error before referring).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your kind words regarding our presentation, the novelty of our algorithm, the motivation of our problem, and the contribution to literature. We address your primary concerns below:\n\n**[Re: Top-k principal components]** Recent results provide a black-box way to obtain k-PCA given an algorithm to extract the top eigenvector (see [a]) which could be employed treating our algorithm as a 1-PCA oracle. This deflation-styled approach has also been proposed in [b] in the context of Sparse PCA. \n\nWe also believe that an analysis such as [c] can be extended to the sparse setting to obtain top-k principal components simultaneously via QR decomposition and thresholding. This could be an interesting direction for future work.\n\nReferences: \n\n[a] Jambulapati, A., Kumar, S., Li, J., Pandey, S., Pensia, A. &amp; Tian, K.. (2024). Black-Box k-to-1-PCA Reductions: Theory and Applications. Proceedings of Thirty-Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:2564-2607.\n\n[b] Mackey, Lester. \"Deflation methods for sparse PCA.\" Advances in neural information processing systems 21 (2008).\n\n[c] Allen-Zhu, Zeyuan, and Yuanzhi Li. \"First efficient convergence for streaming k-pca: a global, gap-free, and near-optimal rate.\" In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 487-492. IEEE, 2017.", "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": "", "extra_scores": {}}, {"review_id": "vfWi5XezNm", "reviewer": "Reviewer_qSPb", "summary": "This paper studies the problem of finding the top eigenvector from samples.\nGiven $n$ samples drawn from a distribution whose mean is $0$ and covariance matrix is $\\Sigma\\in\\mathbb{R}^{d\\times d}$, we would like to find a vector $\\hat{v}$ based on these $n$ samples such that $\\hat{v}$ and the top eigenvector of $\\Sigma$, $v$, have a small $\\sin^2$ error which is defined as $1-\\langle\\hat{v},v\\rangle^2$.\nFurthermore, we assume that the sparsity of $v$ is $s$ and hence we expect the output $\\hat{v}$ also has sparsity $s$.\nThe goal in this paper is to design a single pass algorithm using $O(nd)$ time and $O(d)$ space such that the error is minimized.\nOja's algorithm is a well known algorithm for finding the top eigenvector and works as follows.\nIn the $t$-step, we iteratively update our current solution towards the $t$-th sample.\nThe authors applied Oja's algorithm to achieve the goal and showed that the error is at most $O(\\frac{\\sigma_*^2 s\\log d}{n})$ where $\\sigma_*^2$ depends on the top two eigenvalues.", "questions": "Note:\n\n- Line 31: $r_{\\textsf{eff}}$ is not defined yet in the main text.", "limitations": ".", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problem seems to be a natural question and well-motivated.\n\n- The general presentation is good.\nThe readers of all levels of expertise should be able to follow the main idea in this paper.", "weaknesses": "- In terms of techniques, the main idea is to apply the known Oja' algorithm.\nI am not sure if there are any fundamental new ideas introduced in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your kind words regarding the motivation of our problem and the simplicity of the presentation. We address your primary concerns below:\n\n**[Re: Novelty of fundamental ideas]:** While our algorithm builds on top of Oja’s algorithm, hard thresholding of Oja’s vector for Sparse PCA has not been proposed or analyzed before. We introduce several novel ideas in this analysis and respectfully disagree with the claim of the lack of fundamental new ideas in our work. In what follows, we describe the motivation for the problem considered in our work, how it compares with relevant works under the computational and statistical regime of interest, and bring out the new ideas involved in our analysis. \n\n### Importance of the Problem Setting\n*Motivation*: Sparse PCA has been a long-standing problem, with many algorithms being proposed in the literature, motivated both by theoretical ideas and practical applications. It has seen a lot of interest from the Computer Science and Statistics communities. Table 1 in our paper provides a detailed summary of various important contributions over the last two decades, along with their statistical performance as a function of various computational and model parameters.\n\n*Problem Statement*: In this paper, we consider a variant of the problem that has been relatively unexplored in the literature - *Can Sparse PCA be performed at the statistically optimal rate in linear time and space, without placing strong structural assumptions on the population covariance matrix?*. The only papers which operate under this tight statistical and computational budget, to the best of our knowledge, are Johnstone and Lu [JL09], Yang and Xu [YX15], and Wang and Lu [WL16]. However, all of them require a spiked population covariance model for their analysis. Figure 1(a) compares the performance of these algorithms on a population covariance model which slightly deviates from the spiked model and shows how critical this assumption is for their performance.\n\n*Our Contribution*: This question on the efficiency of PCA, without sparsity, has been asked before (see e.g. Jain et. al [2016]) and Oja's algorithm has emerged as one of the clear winners, achieving the statistically optimal rate under tight computational and space constraints. However, its extension under the sparsity assumption is challenging and has not been analyzed before. In fact, this algorithm, despite its simplicity, has not been proposed in its current form in the literature before. We therefore believe that this algorithm and its analysis provide a valuable step in the direction of **computationally and space-efficient Sparse PCA** algorithms which work without strong assumptions on the data distribution. \n\n### Novel Ideas in Our Analysis\n\n1. We would like to point out that the analysis of thresholding, as pointed out by all other reviewers, is very different and novel, diverging significantly from analyzing regular Oja’s algorithm. In particular, it introduces a tight analysis of a system of linear recurrences, which is novel, as pointed out by Reviewer zu7o. \n\n2. Our analysis further offers theoretical insights into the behavior of the entries of the Oja vector, which, to the best of our knowledge, has not been attempted before. In particular, Lemma 3.13 and 3.14 provide the first results of their kind and show that although the entries of the Oja vector do not concentrate, it is indeed possible to show a tail-bound on their deviation.\n\n3. The closest algorithm to our work that we are aware of analyzes soft-thresholding of the Oja vector under a stronger assumption on the covariance model and an initialization close to the population eigenvector (see Wang and Lu, 2016). Furthermore, they provide a PDE-based asymptotic analysis of the problem, whereas our work provides a sharp and non-asymptotic rate of convergence.\n\n**[Re: Definition of $r_\\mathsf{eff}$]:** We define $r_\\mathsf{eff}$ in Lines 4-5.", "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": "", "extra_scores": {}}]

Author rebuttal:
We want to first thank all the reviewers for their valuable suggestions and insightful feedback. We believe we have addressed nearly all of their main technical questions. In what follows, we will address some important points each reviewer has raised. We will correct all the typographical issues pointed out and will not address them here.

### **Re: Over/under estimates of $\eta$ (Reviewer zu7o)**

 For step-sizes, we follow the convention in (Balsubramani et al. (2015), De Sa et al. (2015), Jain et al. (2016), Li et al (2017), Allen-Zhu et al. (2016)), Huang et al. (2021), where Oja’s algorithm is analyzed without sparsity and the optimal learning rate requires knowledge of the gap, $\lambda_{1} - \lambda_{2}$, and other model parameters to get the statistically optimal rate. Our sin-squared error roughly is of the form $O\left(\eta\lambda_1+\exp(-n\eta(\lambda_1-\lambda_2)\right)$. The optimal eta ensures that the first term dominates yielding our optimal error rates. However, a small $\eta$ resulting from plugging in an upper bound on the eigengap $\lambda_1-\lambda_2$ may make the second term dominate leading to a suboptimal sin-squared error. We will clarify this further.

### **Re: $k \geq s$ in Theorem 3.2 (Reviewer zu7o)**

 Our probability boosting argument for Algorithm 3 requires a distance metric, such that when the true support $S\in \hat{S}_1$, $d(S,\hat{S}_1)\leq \epsilon$ for some small $\epsilon>0$. And not only that, we also crucially need that $d(S,\hat{S})\leq \epsilon$ implies that $\hat{S}$ contains $S$. This is easily done for $k=s$ since the metric is just the indicator function which returns 0 if two sets are equal and 1 otherwise. With $k \geq s$, we were as yet unable to create such a metric that would be amenable to boosting to high probability.

### **Re: Top-k principal components (Reviewer jbhG)**

 Recent results provide a black-box way to obtain k-PCA given an algorithm to extract the top eigenvector (see [a]) which could be employed treating our algorithm as a 1-PCA oracle. This has also been proposed in [b]. We also believe that an analysis such as [c] can be extended to the sparse setting to obtain top-k principal components simultaneously via QR decomposition and thresholding. This could be an interesting direction for future work.

### **Re: Novelty of fundamental ideas] (Reviewer qSPb)**

 While our algorithm builds on top of Oja’s algorithm, hard-thresholding of Oja’s vector for Sparse PCA has not been proposed or analyzed before. The closest algorithm analyzes soft-thresholding under a stronger assumption on the covariance model and an initialization close to the population eigenvector (see Wang and Lu, 2016). We would also like to point out that the analysis of thresholding, as pointed out by all other reviewers, is significantly different from analyzing regular Oja’s algorithm. In particular, it introduces a tight analysis of a system of linear recurrences, which is novel, as pointed out by Reviewer zu7o.  Our analysis offers theoretical insights into the behavior of the entries of the Oja vector, which, to the best of our knowledge, has not been attempted before. Please refer to the reviewer rebuttal for a more detailed response.

References: 

[a] Jambulapati, A., Kumar, S., Li, J., Pandey, S., Pensia, A. & Tian, K.. (2024). Black-Box k-to-1-PCA Reductions: Theory and Applications. Proceedings of Thirty-Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:2564-2607 Available from https://proceedings.mlr.press/v247/jambulapati24a.html.

[b] Mackey, Lester. "Deflation methods for sparse PCA." Advances in neural information processing systems 21 (2008).

[c] Allen-Zhu, Zeyuan, and Yuanzhi Li. "First efficient convergence for streaming k-pca: a global, gap-free, and near-optimal rate." In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 487-492. IEEE, 2017.

Meta-review: All four reviewers were positive, though one of them barely so who was a little concerned that the algorithm was straightforward and the contribution is fairly theoretical (and for a fairly narrow task).  Taking that into account, it still appears to be a solid contribution, and certainly theoretical analyses are welcome in NeurIPS. The theoretical contribution itself is clearly described, and at least one reviewer was impressed by the techniques.  Overall, the reviewers thought it was a good paper with no major flaws, and thus I'm happy to recommend acceptance.
Decision: Accept (poster)