Approximating the Top Eigenvector in Random Order Streams
Authors: Praneeth Kacham
David Woodruff
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Streaming Algorithms
Top Singular Vector
PCA
Random Order Streams
Primary area: optimization

Abstract: When rows of an $n \times d$ matrix $A$ are given in a stream, we study algorithms for approximating the top eigenvector of $A^T A$ (equivalently, the top right singular vector of $A$). We consider worst case inputs $A$ but assume that the rows are presented to the streaming algorithm in a uniformly random order. We show that when the gap parameter $R = \sigma_1(A)^2/\sigma_2(A)^2 = \Omega(1)$, then there is a randomized algorithm that uses $O(h \cdot d \cdot \text{polylog}(d))$ bits of space and outputs a unit vector $v$ that has a correlation $1 - O(1/\sqrt{R})$ with the top eigenvector $v_1$. Here $h$ denotes the number of ``heavy rows'' in the matrix, defined as the rows with Euclidean norm at least $\|{A}\|_F/\sqrt{d \cdot \text{polylog}(d)}$. We also provide a lower bound showing that any algorithm using $O(hd/R)$ bits of space can obtain at most $1 - \Omega(1/R^2)$ correlation with the top eigenvector. Thus, parameterizing the space complexity in terms of the number of heavy rows is necessary for high accuracy solutions.

Our results improve upon the $R = \Omega(\log n \cdot \log d)$ requirement  in a recent work of Price. We note that Price's algorithm works for arbitrary order streams whereas our algorithm requires a stronger assumption that the rows are presented in a uniformly random order. We additionally show that the gap requirements in Price's analysis can be brought down to $R = \Omega(\log^2 d)$ for arbitrary order streams and $R = \Omega(\log d)$ for random order streams. The requirement of $R = \Omega(\log d)$ for random order streams is nearly tight for Price's analysis as we obtain a simple instance with $R = \Omega(\log d/\log\log d)$ for which Price's algorithm, with any fixed learning rate, cannot output a vector approximating the top eigenvector $v_1$.

Approximating the Top Eigenvector in Random Order Streams
Praneeth Kacham" Google Research pkacham@google.com com
David Woodruff
Carnegie Mellon University dwoodruffcs. cmu. edu
Abstract
When rows of an x d matrix A are given in stream, we study algorithms for ap- proximating the top eigenvector of the matrix A (equivalently, the top right sin- gular vector of A). We consider worst case inputs A but assume that the rows are presented to the streaming algorithm in uniformly random order. We show that when the gap parameter R. 0₁ (A)² /02( (A)² (1),, then there a randomized algorithm that uses O(h d polylog d)) bits of space and outputs a unit vector v that has correlation 1 O(1/ with the top eigenvector d1 Here / denotes the number of heavy rows the matrix, defined as the rows with Euclidean norm least A|F / / d polylog(d). We also provide lower bound showing that any algorithm using (hd/ R) bits of space can obtain at most Q(1 R²) correla- tion with the top eigenvector. Thus, parameterizing the space complexity in terms the number of heavy rows is necessary for high accuracy solutions.
Our results improve upon the R 22llg n log d) requirement in a recent work Price and Xun (FOCS 2024). We note that the algorithm of Price and Xun works for arbitrary order streams whereas our algorithm requires a stronger assumption that the rows presented in uniformly random order. We additionally show that the gap requirements in their analysis can be brought down to R 2(log" d) for arbitrary order streams and R = 2llog d) for random order streams. The requirement of R 2(log d) for random order streams is nearly tight for their analysis as we obtain a simple instance with R = 22oog d/ log log d) for which their algorithm, with any fixed learning rate, cannot output vector approximating the top eigenvector d1-
Introduction
We consider the problem of approximating the top eigenvector in the streaming setting. In this problem, we are given vectors d1....: On E I one at time in a stream. Let A be an matrix with rows .1...., an The task is to approximate the top eigenvector of the matrix AT A. Throughout the paper, we use V1 E Rd to denote the top eigenvector of A A. We focus on obtaining streaming algorithms that use small amount of space and can output unit vector è such that v1)2 f (R), where fRR) is decreasing function in the gap R = x (AT A) A). Here A1 A2(-) denote the two largest eigenvalues. As the gap R becomes larger, the eigenvector approximation problem becomes easier and we want more accurate approximations to the eigenvector t1.
one is allowed to use Odd2) bits space, we can maintain the matrix ATA = Σ, a.a as we the rows a; in the stream, and the end of processing the stream, top eigenvector vn. When the dimension d is large, the requirement of 2(d2) bits of memory can be
compute the exact
Work done while the author was student at Camegie Mellon University.
"The notation ((((n) is used to denote the of functions in ((((n) polylog(n)).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

impractical (see e.g., applications that require a large value of d in Mitliagkas et al. (2013).) Hence, an interesting question to study non-trivial streaming algorithms that use less memory. In this work, we focus on obtaining algorithms that use ((d) bits of space.
In the offline setting (where the entire matrix A is available to us), fast iterative algorithms such as Gu (2015); Musco and Musco (2015); Musco al. (2018) can be used to quickly obtain accurate approximations to the top eigenvector when the gap R = 91(). In single pass streaming setting, we cannot run these algorithms these iterative algorithms need to see the entire matrix multiple
times.
There have been two major lines of work studying the problem of cigenvector approximation and the related Principal Component Analysis (PCA) problem in the streaming setting with near-linear in d memory. In the first line of work, each row encountered in the stream is assumed to be sampled independently from an unknown distribution with mean O and covariance E and the task is to ap- proximate the top eigenvector of Σ using the samples. In this line of work, the sample complexity required for algorithms using (d (od-poyyog(())) bits of space to output an approximation to U1, is the main question. The algorithms are usually a variant of Oja's algorithm (Oja, 1982; Jain al., 2016; Allen-Zhu and Li, 2017; Huang et al., 2021; Kumar and Sarkar, 2023) or the block power method (Hardt and Price, 2014 4; Balcan et al., 2016). We note that Kumar and Sarkar (2023) relax the i.i.d. assumption and analyze the sample complexity of Oja's 's algorithm for estimating the top eigenvector in the Markovian data setting.
The other line of work studies algorithms for arbitrary streams appearing in an arbitrary order. In this setting, want algorithms to work for any input stream given in any order. A problem closely related to the eigenvector estimation problem is the Frobenius-norm Low Rank Approxima- tion (Clarkson and Woodruff, 2017; Boutsidis et al., 2016; Upadhyay, 2016; Ghashami et al., 2016). The deterministic Frequent Directions sketch of Ghashami et al. (2016) can, using ((d/s) bits of space, output a unit vector u such that
|| uu ")II S (1++))lA(() - D
Although the vector is a + E approximate solution the Frobenius norm Low Rank Approxi- mation problem, is possible that the vector u may be (nearly) orthogonal to the top eigenvector v1. Hence the Frequent Directions sketch does not guarantee top eigenvector approximation. Recently, Price and Xun (2024) study the eigenvector approximation problem in arbitrary streams and obtain results in terms of the gap R of the instance. Price and Xun prove that when R 22log n log d), a variant of Oja's ija's&a algorithm outputs unit vector é such that
C'logd R
( 21 2
poly
where C' is large enough universal constant. On the lower bound side, Price and Xun showed that any algorithm that outputs a vector è satisfying
1
(6, v1) 21 CR
must use ((FFRR)) bits of space while processing the stream. This lower bound shows that in the important case of R (1), the correlation' that can be obtained by an algorithm using Ö(d) bits of space is at most a constant less than 1. Thus, the current best algorithms for arbitrary streams work only when
2loog n log d) and for the important case of R = O(1), there are no existing algorithms requiring significantly fewer than d² bits of memory. They also give a lower bound on the size of mergeable summaries for approximating the top eigenvector.
We identify an instance with n = Olog d/ log log where the algorithm of Price and Xun fails to produce vector with even constant correlation with the vector V1- This shows that their algorithm or other variants of Oja's algorithm may fail to extend to the case when R = 0(1). We further show that the algorithm of Price and Xun fails produce such vector even when the rows in our hard instance are ordered uniformly at random, showing that even randomly ordered streams can be hard solve for variants of Oja's S algorithm.
In this work, we focus on algorithms that work on worst case inputs while assuming that the rows of A are uniformly randomly ordered. This model is mid-way between the i.i.d. setting and the
We say that the value (u, 2 denotes the correlation between unit vectors and

---

arbitrary order stream setting in terms of the generality of streams that can be modeled. We note that number of works (Munro and Paterson, 1980; Guha et al., 2005; Chakrabarti et al., 2008; Guha and McGregor, 2009; Assadi and Sundaresan, 2023) have previously considered streaming algorithms and lower bounds for worst case inputs with random order streams, as it is a natural model often arising in practical settings. Our algorithms are parameterized in terms of the number of heavy rows in the stream. See Gupta and Singla (2021) for gentle introduction to the random-order model. We define a row as to be heavy if ||ai]l2 2 ||Al|// /poolologg(d)) Note that in any stream of rows, by definition, there are most d polylog(d) (d) heavy rows. We state our theorem informally below:
Theorem 1.1.
Let a1.....,0 On IRd be a randomly ordered stream and let A denote the n d (A (A
matrix with rows given by a1...., an- If R = X1 A) A2/22( C' and the number of heavy rows in the stream is at most h, then there a streaming algorithm using O(h d polylog(d) (d) bits of space and outputting a wnit vector satisfying
A) > for a large enough constant
(6, 2 1
with probability 2 4/5.
Our algorithm is a variant of the block power method. Along the way, we also improve the gap requirements in the results of Price and Xun (2024). We show that by subsampling a stream of rows, the algorithm of Price and Xun can be made to work even when the gap R is M(log" d) in arbitrary order streams, improving on the (log n log d) requirement in their analysis. We also show that in random order streams, a gap of 2(oog d) is sufficient for their algorithm, though our algorithm improves on this and works for even a constant gap.
Similar to the lower bound of Price and Xun, we show that any algorithm for random order streams must use Sh d/ Rt) bits of space to output a vector e satisfying (0, v1)² 2 1 - 1/CIP where C is a constant. We summarize the theorem below.
Theorem 1.2. Consider an arbitrary random order stream a1..... On with the gap parameter (A))
(2( R. Let h be the number of heavy rows in the stream. Any streaming algorithm that outputs a unit vector i such that
(0,01)² 21 1/CR
for a large enough constans C, with a probability 2 1 - (1/2)R+1 over the ordering of the stream and its internal randomness, must use 27h d/ d/R) bits of space.
The randomized power method (Gu, 2015) algorithm to approximate the top eigen- vector samples random Gaussian vector g and iteratively computes the vector v = (A A)'g for I == O(log d) iterations and shows that when the gap R is large, v/ e/|lv||2 is good approximation for v1. Thus, the algorithm needs to see the quadratic form AT A multiple times and hence, it cannot be implemented in the single-pass, streaming setting of this paper.
Techniques.
Assume that the stream is randomly ordered and that there are no heavy rows. Our key observation that if the stream is long enough, then we can see / approximations B) B, of the quadratic form ATA. A. Here the matrices B,,.. ..... B, are formed by sampling and rescaling the rows of the matrix A and importantly, the rows of Bi,..., , B, do not overlap in the stream, that is, they appear one after the other. Thus we can compute o' (B. B2) (B) B₁) g for the starting vector g in a single pass over the stream. We prove that such matrices B, exist using the row norm sampling result of Magdon- Ismail (2010). Now, the main issue is to show that o'/l|e" [| a good approximation the top eigenvector 11. We crucially use a singular value incquality of Wang and Xi (1997) to prove that B, - AT Alla I < A|/2 for all j suffices for e' o//l| //|e'll2 to be good approximation to U1.
The above analysis assumes that there are no heavy rows. Indeed, suppose that matrix A has a row a with a large Euclidean norm which is orthogonal to all the other rows. Also assume that the top eigenvector of the matrix A is in this direction. Since, the matrices B,,..., B, substreams of the matrix A, at most one of the matrices B, can have the row a and hence the vector e' w//le//l2 2l will not be a good approximation to a/ /|alll. the top eigenvector. Thus, we need to handle
non-overlapping
NNte that AT A x = E, (a,, 2)aa
We use bold symbols to denote random variables.
3

---

the heavy rows separately. We show that, by storing all the rows with Euclidean norm larger than ||A||// / /d polylog(d) and running the above described algorithm on the remaining set of rows, we can obtain good approximation to the top eigenvector.
Our lower bound (Theorem 1.2) shows that any single-pass streaming algorithm must use space proportional the number of heavy rows, and therefore our procedure that handles the heavy rows separately gives near-optimal bounds.
Finally, the norm sampling technique of Magdon Ismail (2010) serves general technique to reduce the number of rows in the stream while (approximately) preserving the top eigenvector. We use this observation to improve the R 22 log d) for arbitrary streams in Price and Xun (2024) R 22(lg"" d). We then show that assuming uniformly random order, the analysis of Price and Xun (2024) can be improved to show that R = 2llog d) suffices. Thus, for random order streams, techniques before our work can be used approximate the top eigenvector when the gap R = 2ilog d). Our work improves upon this to give an algorithm that works for streams with R = 2(1).
Implications practice. Often, in practical situations, can assume that the rows being streamed are sampled independently from a nice-enough distribution, in which case Oja's algorithm, discussed, can approximate the top eigenvector accurately given enough samples. However, inde- pendence and assumptions on the covariance matrix can be very strong assumptions in some cases and in such cases, our algorithm only requires that the order of the rows in the stream be uniformly random, in which case we output an approximation with provable guarantees.
Organization. We first introduce the row-norm sampling procedure to obtain approximate quadratic forms. The proof slight modification of that of Magdon-Ismmai (2010). The only dif- ference is that we instead consider version that samples each row in the input independently with some appropriate probability and keeps the rows that are sampled after scaling appropriately. We then introduce and analyze our block power iteration algorithm when all rows have roughly the same Euclidean norm, and then extend it to the general case, which our main result. Finally, we provide lower bound showing that (tdd/ It) bits of space is necessary to obtain constant correlation with the top eigenvector. Due to space constraints, of our proofs are placed the appendix.
2 Power Method with Approximate Quadratic Forms
In this section, we present and analyze our algorithm for approximating the top eigenvector of ATA when the rows of A are presented to the algorithm in a uniformly random order.
We first show a row sampling technique that reduces the number of rows in the stream. The row- norm sampling technique for approximating the quadratic form AT with spectral norm guarantees was given by Magdon-Isma Ismail (2010). The technique works irrespective of the order of the rows.
2.1 Sampling for Row Reduction
Theorem 2.1. Let A be an arbitrary n x d matrix. Given E 10, 10 matrix such that for each E [n], we independently set Qu = 1/ yPi with probability pt and otherwise. for all i,
R let Q be n x n diagonal
||.. 1aa
p: 2 min 1,C
logd)
QAI22 S =|[A|i. With probability at least 1 1//p/pp/ poly(d), the matrix has most O(E-² fie-2plog non-zero entries, where p ||A|A//||||3 denotes the stable rank of matrix A.
then with probability 1- 1/ ||AT A AT
Note that given the value of ||A||,, the sampling procedure in this theorem can performed a stream. Additionally, as the original stream is uniformly randomly ordered, the sub-sampled stream also uniformly randomly ordered assuming that the sampling independent of the order of the rows.

---

end Given that all of the non-zero entries of the matrix have absolute value at least 1/ poly(nd) and at most poly(nd), we have that ||A|| lies in the interval [1/ poly(nd), poly(nd).. Thus, we can guess the value of || as 2* poly(nd) for i = O..... (log(nd)) and one of these values must be 2-approximation to || 13, and thus sub-sampling the rows using that guess satisfies the conditions in the above theorem. We can run the streaming algorithms on all the streams simultaneously to obtain (log nd) vectors uj...... Wooo nd) as the candidates for being an approximation to the top eigenvector. From Theorem 2.1, the candidate vector uj computed on the stream obtained by sampling the rows with the correct probabilities is a good approximation to the top eigenvector, and therefore ||A uy is large for that value of j. Thus, the vector u, with the largest value ||4 uy ll is good approximation to the top eigenvector 01 If G' is Gaussian matrix with 2 d) rows, then for all Uj, we can approximate | u2]l2 up to a e factor using ||G A "y ll by the Lonnson-Lindeestrraus. lemma. Additionally, the matrix G' A can be maintained in the stream using O( 2 log d) bits (when we see a row a, we sample an independent Gaussian vector g; and add g.a. to an accumulator maintain G A). Thus, the end of processing the stream, we can compute vector U that has a large value ||A 2y 111 and hence is good approximation for vi.
If can process each created stream using s bits of space, then the overall space requirement is O(s log(nd) + d polylog(d) bits, using (ss) bits for each guess for the value of || and Odd polylog(d)) bits for storing Gaussian sketch of the matrix with & = 1/ polylog(d).
2.2 Random-Order Streams with bounds on Norms
Algorithm 1: Approximate Eigenvector for Streams with no Large Norms
Input: An n matrix with n On p(A) log" d/E"), max; ||a:|/// min; || S n
Output: A vector z
+ [2 log d)
2 Compute G in the stream where G is a Gaussian matrix with O( 2og d) rows
3 for p 1,2, 4..., .d simultaneously do
p - C2nploge d/ne?
11 S 1/(5t) for p p32
2p ~ (O, 1)d
for j 1,..... .......... do
yj - Bin [, p)
if y, > 2mp then
return
10
end
// The matrix (2 corresponds to Bj in the analysis. acc +0 for fori=: (1) (2)))p2p) + I,.... (j-1) (2mp) + y, do
11
12
13
acc < acc + (a,, 2p)
14
1/ Here acc = BJ B,
15
2p - acc
16
2p zp/ ||2|||2
end
end
19
return arg max ze| 21..2. (I AA)=|2
We now present the analysis the block power method for random order streams assuming that the Euclidean norms of all the rows in A are close to each other. We later remove this assumption. Suppose there exists a parameter 77 such that (max, (a.ll3)((min, |a, [3] I 17. If ry is close to then all the rows in the stream have roughly the same norm.
Let p Cap (d) We can see that for any row a; the stream,
|| log d <
"11
Cuplog d
C
E² A
E² [A
log d $
ne²
p.
5

---

Thus, is greater than the probability with which we need to sample each row in the row-norm sampling result Theorem 2.1. Now if we perform such a sampling of the rows of A, we sample Bin(n, p) number of rows, which is tightly concentrated around np Cnp log d. Thus, if we first sample y ~ Bin(n, p) and then consider the first y number of rows in the random order stream, then we will have sampled from a distribution satisfying the requirements in Theorem 2. and can therefore obtain a matrix B such that
B Al S E/
Thus, assuming that the rows appear in a uniformly random order lets us show that the first y rows of the stream can be used compute an approximation to the quadratic form A A. We will now show that we can obtain O(log d) such quadratic forms in the stream given that the stream is long enough.
Assume that the number of rows in the stream n M(n log" d/s²). We partition the stream into t = (log d) groups as follows: the first 2np rows are placed the group 1, the second 2np rows are placed in the group 2, and so on. Note that since n = (np log d/e²), we can form & such groups. Since the rows are uniformly randomly ordered, the joint distribution of the rows appearing in group is the same as that of the joint distribution of the rows appearing in group 2 and so on. Let P1..... y/: ~ Bin(n. p) be drawn independently. With probability 2 1 - 1/ poly(d), we have y; S (3/2)mp for all i. For = I.....tt. .t. let B; be the matrix formed by the first y; rows in group i. Using union bound, we have that with probability 2 1/ poly(d), for all i = 1,...,t,
p A A - B.B.Bll l. S =.
Conditioned on the above event, we will now show that running the power method on the blocks B,,..., B, lets us approximate the top singular vector of the matrix
Assumption 2.2. We assume that a (A)/o2(A) 2
Lemma 2.3. Let e > p/loyy(d) be an accuracy parameter and I. = 22llog d) be the number of iterations. Let E S e/t² for a small constant e. Suppose Bı...., B, all satisfy I|AT A B B3ll2 S e||A||e for e < 1/5. If g is a rundom vector sampled from the Gaussian distribution, then the unit vector
(BTB.) ........ (BB Bi)g
é = [I(B, ..)....PB)) B1)g
satisfies
(0, 2 1 C'tNEE
with probability 2 9/10 for large enough constant C². Here vn denotes the top right singular vector of the matrix A.
To prove this lemma, our strategy to show that the matrix product M = (B) ... (B B₁) has stable rank close to 1 - meaning it has one very large singular value and the rest of the singular values are small. We can then argue that the vector = Mg/ M| is in the direction of the top singular vector M. Using the fact that of (BJ singular vector of M must have a large correlation with Uy Therefore, it follows that the vector d has a large correlation with en as well. As part of the proof, we crucially use an inequality from Wang and Xi (1997).
By) 2 (1 - =)]I for all j. we show that the top
If t (log d) and 1/ poly(d) I c/(log d)2, then the above lemma shows that has large correlation with the top singular vector V1. Using this lemma, we show that Algorithm I can be used obtain an approximation for ii in random order streams with bounded norms.
Theorem 2.4. Let a 2 1/ poly(d) be an accuracy parameter. Let 17 be parameter such that
max; ||
< m. If the number of rows in the stream Q(a 4, .((A) 17 log" 6 d), where p(A)
min: 1
Bin(n, p) denotes the binomial distribution with parameters and p.

---

||A||/|||| and the rows in the stream are ordered uniformly ar random, then we can compute vector i using the block power method that satisfies
1( 0)|² 1 2111
with probability 2 4/5 2 2. The algorithm uses Old (olyloooogg())/a)) bits of space.
M(x $ pn log d), we have 30(==3p)) log" d). Now consider the execution of Algorithm 1 on matrix A, with parameters 17 and Let p 2 be such that p(A)/2 S p S p(A), and consider the execution in the algorithm with parameter p. Using Theorem 2.1, with probability 2 1 - 1/ poly(d), the algorithm
Proof. Set è a²/C'log" d for a large enough constant C. Assuming
computes matrices ....... B, such that for all j E (t).
1 B A Ale S E|/A
p
Noting that 2p (B, B.) B.)
B//ll B.) (B) B B1)gl12, by Lemma 2.3, we have with
B [B
probability 2 29/10 that
(zp: v1)
1t C"IV 21-a.
Thus, for o which satisfies p(A)/2 S p p(A), the algorithm computes a vector 2p that has large correlation with the vector v1 Since the algorithm does not know the exact value of p. it computes an approximation for ||A=|] for all = E 12. 24..... Za J. First, we condition on the fact that with probability 2 1- 1-1ppoly(dd) for all Zi. || 12 (1 + e)ll A2; Since (zp: v1)² ) 2 (1 - a),, we note that |GAzzl (1 (1-=)( a)oi (A)². Now, for the vector returned by the algorithm,
we have | 2 0(=)) (A) which implies that
(z, 01 - + (1 (z, v1 (A)2
2 | 2 a1-a (1--a00(3)o
R
and therefore (z, )1 2 2 1 3a since R 2 2.
2.3 Random Order Streams without Norm Bounds
Assuming that the random order streams are long enough, Theorem 2.4 shows that if all the squared row norms are within r factor, then the block power method outputs a vector with a large corre- lation with the top eigenvector of the matrix A A. For general streams, the factor could be quite large and hence the algorithm requires very long streams output an approximation Vi-
heavy rows, i.c., with Euclidean norm larger than ||-A]/// /d polylog (d), then the row norm sampling procedure in Theorem 2.1 can be used to convert any randomly ordered stream of rows into uniformly random stream of rows that all have the same norm. The norm sampling procedure computes a probability p; = min(1, Ce Ce- "||a, log d/ (/[))|()) and samples the row a; with probability p.. If sampled, then the row a, is scaled by 1/ From Theorem 2.1, have that the top eigenvector of the quadratic form of the sampled-and-rescall approximation the top eigenvector A A when the gap R is large enough. Suppose p; < 1. If the row a, is sampled, we then have
If there
submatrix is good
||0// Vpill2 = E||A||2
VClogd
Thus, if < 1 for all i, then all the sampled-and-rescate therefore, we can run the algorithm from Theorem 2.4 by setting 7 Note that p; 1 only ||a:1|2 2 e² || Cloogd) Since we assumed that there are no heavy rows, there is no row with p: = as long as 8 2 1/ polylog(d). Thus, using Theorem 2.4 on the row norm sampled substream directly gives us a good approximation to the top eigenvector. However, in general, the streams can have rows with large Fuclidean norm. We will now state our theorem and describe how such streams can be handled.
rows have the same Euclidean norm and
7

---

Theorem 2.5. Let A be an n x d matrix with its non-zero entries satisfying 1/ poly(d) < | poly(d), and hence representable using Ollog d) bits of precision. Let R = 01
Assume 2 S R < C₁ log" d. Let h be the number of rows in A with norm at most ||A|/// Vd polylog(d)
where polylog(d) = log d for a large enough universal constant C2. Given the rows of the matrix A in a uniformly random order, there an algorithm using (--l--))--polyllo(dd log n) bits space and which outputs a vector è such that with probability 2 4/5, i satisfies (0, v1)² 2 1 - 8/VR, where is the top eigenvector of the matrix A A
The key idea in proving this theorem is to partition the matrix A into Anewy and Anght. where Abeavy denotes the matrix with the heavy rows and Anght denotes the matrix with the rest of the rows of A. Since we assume that there are at most h heavy rows, we can store the matrix Anewv using O(h - polylog(d) (d) bits of space. Now consider the following two cases: (i) || Aheavy I|2 2
|)
or (ii) || Aeavy ll2 < (1 - B)] All2 for some parameter 33. In the first case, we can show that the top cigenvector to of Abeayy Ancavy is good approximation for 01. Since, we store the full matrix Aneavy, we can compute u exactly at the end of the stream. Suppose || Il2 < (1 B)]|_A|22. By the triangle inequality, we have ||-Aughe ll2 > $1|AA|22. If we set large enough compared to 1/R, then we can show that the top eigenvector u' of Alght is a good approximation of v/, From the above discussion, since all the rows of Atight are light, we can obtain a stream using Theorem 2.1 such that all the rows have the same norm and additionally. the top eigenvector of this stream is good approximation for u' and therefore V1. We then approximate the top eigenvector of the new stream using Theorem 2.4. Setting 3 appropriately, we show that this procedure can be used to compute a vector i satisfying (0, 22)² 2 1 - O(1/V(())))) proving the theorem.
3 Lower Bounds
Our algorithm uses Ö(h- d) space when the number of heavy rows in the stream is h. We want to argue that it is nearly tight. We show the following theorem.
Theorem 3.1. Given dimension d, let and R be arbitrary with S h S d and R2 h2-h- h- (d)). Consider algorithm A with the following property:
Given any fixed matrix n x d matrix A with O(h) heavy rows and gap on (A)2 (A)2 2 R. in the form of a uniform random order stream, the algorithu A outputs unit vector such that, with probability 2 1 (1/2)4Bt+4 44+ over the randomness of the stream and the internal randomness of the algorithm, ((,, e1)1² 2 1 1o/-o//
c/ R².
If e is small enough constant, then the algorithu A must use 12(h d/R) bits of space.
The theorem shows that a streaming algorithm must use S2(hd/ R)) bits of space assuming that with high probability, it outputs a vector with a large enough correlation with the top eigenvector of AA A when the rows are given in random order stream.
Our proof uses the same lower bound instance as that of Price and Xun (2024). The key difference from their proof is that our lower bound must hold against random order streams.
4 Improving the Gap Requirements in the Algorithm of Price and Xun
4.1 Arbitrary Order Streams
As discussed in Section 2.1, we can guess an approximation of || in powers of 2 and sample at most Od d/e²) rows in the stream obtain matrix B, in the form of a stream, satisfying
B B AT A|2 ellA with a large probability. Using Weyl's inequalities, we obtain that
(B [ B) - (A A) + = and oi (B 2 (1 (AT
implying R' = a 2 (1-
= 1/(2R) S 1/2, we note R' 2 R/3. Letn' = - d log d) be the number of rows in the matrix B and note that R' = 2(log n' -og d)
assuming R = ?(log" df. Hence, running the algorithm of Price and Xun the rows of the matrix
8

---

B, we compute a vector é for which
log d CR
160, of1 21
poly(d)
with a large probability, where of is the top cigenvector of the matrix Bº B. We now note that if V1 denotes the top eigenvector of the matrix A A, then (01 (()),1)) 2 - O(1RR) which therefore implies that with large probability,
K0, 11) logd
CR
Thus, sub-sampling the stream using row norm sampling and then running the algorithm and Xun (2024), we obtain an algorithm for arbitrary order streams with a gap S2(log d).
of Price
4.2 Random Order Streams
Lemma 3.5 in Price and Xun (2024) can be tightened when the rows of the stream are uniformly randomly ordered. Specifically, want bound the following quantity:
(as, Po)
where P = I T denotes the projection away from the top eigenvector, and 0:-1 is a function of 01; , We have
E (a, Po.11) (a, 2 a1...., a,-11]
Given that the first i - rows are d1,.... 0. assuming uniform random order, we have
E((a; Pūş-1)² 001,...;;-11. n - --++1
P(A ajal ai-10 1 Pi--1
02(A)²
1
Hence E[(a; 16 S (0(((A) <<>(A))/(mii))) and E| Pi;-1)? S 02 (1 n). Price and Xun define 1) (2)) as d2 and in that notation, we obtain v) Σ Σi= (a,, P 10oz + log n) with probability 2 9/10 by Markov's inequality. In the proof of Lemma 3.6 in Price and Xun (2024), if // 20(1 + log, n), we obtain log | 1l2 2 01. Now, 0r 2 O(log d) ensures that the Proof of Theorem 1.1 in their work goes through.
Using the row-norm sampling analysis from the previous section, we assume n poly(d) and therefore gap of Oloo d) between the top two eigenvalues of ATA is enough for Oja's algorithm to output vector with a large correlation with the top eigenvector random order streams.
Hard Instance for Oja's Algorithm
At high level, the algorithm of Price and Xun (2024) runs Oja's algorithm with different learning rates and the event that the norm the output vector with each of the learning rates 1) is small, then the row with the largest norm is output. The algorithm is simple and can be implemented using an overall space of Old polylog(d)) bits.
The algorithm initializes Zg g where g is random Gaussian vector. The algorithm streams through the rows aj...., an and performs the following operation
2, 21-1 7) (5-1,a0)00
The algorithm computes the smallest learning rate when || l| is large enough, and then outputs either 2,/ >, 2l or a/||a||2 as an approximation to the eigenvector of the matrix ATA. A. Here denotes the row in A with the largest Euclidean norm.
The following theorem shows that at gaps < O(log d/ log log d)) we cannot use Oja's algorithm with fixed learning rate 77 to obtain constant correlation with the top eigenvector.

---

Theorem 5.1. Given dimension d, a constant > O, a parameter M, for all gap parameters R Og d/ log log d) there a stream of vectors a1, .......,0. On IR' with nt O(R + M) such that:
1. 01 (A)) 2 R/2, and
2. Oja's algorithu with any learning rate n) M fails output unit vector i that satisfies, with probability 2 9/10,
1(0, 01)
where U1 is the top eigenvector of the matrix A.A.
Moreover, the result holds irrespective of the order in which the vectors .1....y On are presented to the Oja's algorithm. We will additionally show that even keeping track of the largest norm vector insufficient to output vector that has a large correlation with 11.
Acknowledgements
The authors were supported in part by Simons Investigator Award and NSF CCF-2335412. D. Woodruff was visiting Google Research while performing this work.
References
Zeyuan Allen-Zhu and Yuanzhi Li. First efficient convergence for streaming k-PCA: global, gap- free, and near-optimal rate. In 2017 IEEE 58th Annual Symposium Foundations of Computer Science (FOCS), pages 487-492. IEEE, 2017. 2
Sepehr Assadi and Janani Sundaresan. (Noisy) gap cycle counting strikes back: Random order streaming lower bounds for connected components and beyond. In Proceedings the 55th Anmual ACM Symposium Theory of Computing, pages 183-195, 2023. 3
Maria-Florina Balcan, Simon Shaolei Du, Yining Wang, and Adams Wei Yu. An improved gap- dependency analysis of the noisy power method. In Conference on Learning Theory, pages 284- 309. PMLR, 2016.
Christos Boutsidis, David P Woodruff, and Peilin Zhong. Optimal principal component analysis in distributed and streaming models. In Proceedings of the forty-eightt annual ACM symposium on Theory of Computing, pages 236-249, 2016. 2
Amit Chakrabarti, Graham Cormode, and Andrew McGregor. Robust lower bounds for communi- cation and stream computation. In Proceedings of the fortieth annual ACM symposium Theory of computing, pages 641-650, 2008.
Kenneth L Clarkson and David P Woodruff. Low-rank approximation and regression in input spar- sity time. Journal of the ACM (JACM), 63(6):1-45. 2017. 2
Mina Ghashami, Edo Liberty, Jeff M Phillips, and David P Woodruff. Frequent directions: Simple and deterministic matrix sketching. SIAM Journal on Computing, 45(5):1762-1792, 2016. 2
Ming Gu. Subspace iteration randomization and singular value problems. SIAM Journal on Scientific Computing, (73))A113-AA111 2015. 3,
Sudipto Guha and Andrew McGregor. Stream order and order statistics: Quantile estimation in random-order streams. SIAM Journal on 3 38(5):2044-2059, 2009. 3
Sudipto Guha, Andrew McGregor, and Suresh Venkatasubramanian. Streaming and sublinear ap- proximation entropy and information distances. arXiv preprint cx/0508122, 2005.
Anupam Gupta and Sahil Singla. Random-order models. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms, chapter Oxford University Press, 2021. doi: 10.1017/ 9781 108637435. URL httph:: http:::///xxviooo/ wwwp:/iv.oorogggoo pdf 2000. 12159.
10

---

Moritz Hardt and Eric Price. The noisy power method: A meta algorithm with applications. Ad- vances neural information processing systems, 27, 2014.
De Huang, Jonathan Niles-Weed, and Rachel Ward. Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates. In Conference on Learning Theory, pages 2463-2498. PMLR, 2021. 2
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 Conference on learning theory, pages 147-11664 PMLR, 2016.
Syamantak Kumar and Purnamrita Sarkar. Streaming pca for markovian data. In Advances in Neural Information Processing Systems, volume 36, 2023. 2
Malik Magdon-lsmail, Row sampling for matrix algorithms via non-commutative bernstein bound. arXiv preprint arXiv: 00.0000000.55 0587, 2010. 3, 4
Ioannis Mitliagkas, Constantine Caramanis, and Prateek Jain. Memory- -imitedd, streaming PCA. In Advances in Neural Information Processing Systems, volume 26, 2013. 2
J Ian Munro and Mike S Paterson. Selection and sorting with limited storage. Theoretical computer science, 12(3):315 335-32,, 1980.
Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster approximate singular value decomposition. Advances in neural information processing systems, 28, 2015.
Cameron Musco, Christopher Musco, and Aaron Sidford. Stability of the lanezos method for matrix function approximation. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1605-1624, SIAM, 2018. 2
Erkki Oja. Simplified neuron model as principal component analyzer. Journal of mathematical biology, 15:267-273, 1982. 2
Eric Price and Zhiyang Xun. Spectral guarantees for adversarial streaming PCA. In FOCS, 2024. 3, 4, 8, 9, 15
Joel A Tropp. An introduction to matrix concentration inequalities. Foundations and Trends@ in Machine Learning. 8(1-2):1-230) 2015. 12
Jalaj Upadhyay. Fast and space-optimal low-rank factorization in the streaming model with appli- cation in differential privacy. arXiv preprint
2016. 2
Bo- Ying Wang and Yan Xi. Some inequalities for singular values of matrix products. Linear algebra and its applications, 264: 164:109-115, 1997. 3, 6,

---

A Omitted Proofs
A.1 Proof of Theorem 2.1
Proof. Let X, denote an indicator random variable which denotes if Qu is nonzero. Note E X = P: and X1, 1...... Xn, are independent. Define a x d random matrix Y, (xs/pt-1)an a, denotes the i-th row of A. We note that
- 1)a,a, where
A A'A- A QA= Σ (xt/p: 1)a,a,
Y
2=1
We use the Matrix Bernstein inequality (Tropp, 2015) bound | 11ll.. We first uniformly
upper bound |Y .12 If p: L, by definition Yall2 = 0 with probability 1. Let * 0. Then
1/ - )) 12 - || l2/p: I e²l |/ loo d with probability
We now bound
Σ, El 212..
Σ
E ;1 = Σ B[(L/p: a| 122,a
E
Σ
(1/p: 1)]la; 1)]la11/2.4 12a:a
kp:
a [a
cp, C a 2 log
s²
| 1
A A
C'log d
which implies || Σ. E 2l < | (C d). Now, we obtain
8 //A////2
Pr[l
Σ 112 2 A $
2d exp
e3AAI//(CCog d) + =² 2all////lllg (CClogd)
Cloo d
S 2d exp
2 + e/3) e/1))
I 2 6(1+e/3), then Pr| [|||] Σ, 112 2 |||
S 1 - 22/d² which implies that with probability
2 1 - 1idd, IIATA A QA S =
Now, the number of non-zero entries in the matrix Q is equal to Σ, X We note Σ x <
C p log d. By a Chernoff bound, we obtain that Σ, X; = Oee-2p log d) with probability
1/ 1/ poly(d).
A.2 Proof of Lemma 2.3
Proof. Define M == B,) .. (B)))...(BBBBB B1). Our strategy is to show that if 01 is the top singular vector of the matrix A, then || M la is comparable M|] given that o1 (A)) 2 2. We can then prove the lemma using simple properties of the Gaussian vector
av + A where A 1 Vi. We note that v7 (B] B,)²1 a. We have a B B, 2 (1 - (A)² using the fact that [|B] B, ATAlle S =||AA| and of A = σ1 (A)² = |A.... If we show that A is small, then the vector (BJ By) 8));1 is oriented in direction very close to that of u1. Note that
For arbitrary j. let (B] B3)01
[I(B] BB)oill S 1BTT Bllla S (1+ (A))
a² + +| which implies | < ((1+5)² (1- (1==)))o = (A)) and [[BB =
and thus || S (450 (A)2. Now.
JMMelll 01l12
[[B B1) ... (i)))...BBBBBBBBBBB BB edon (BE,, + A1)l12
... BI 2 (B] BLui, 21 u1) B.) ... ... B, 1 (B 11
2 ((1 (4)3)) B,) (B_ B. ) (A) B,) ... (B__, B, 112
12

---

Expanding similarly, we obtain
|| T v1ll2 2 (1- (N==))(() (A))
Assuming e S e/t for a small constant c, we note that (1-e)' 2 (1-2 and (1+8)' s (1+ (1+21e) 21e) which implies
| U1 l2
[I B1) ... (B. B,) 2 (1 21 - 41)))o1(A)2
We shall now show bound on || || = [I(BB B.) B,)ll which lets us show that the unit vector e is highly correlated with v1. To bound the quantity [| we first note the following facts:
1. Byl12 = (1 + e)or(A)?, and
2. (33 B,) - + < (1/4+ (A) by our gap assumption.
Now, we use the following theorem.
Theorem A.1 ((Wang and Xi, 1997, Theorem 3(i))). For any r > 0 and any matrices A Ab
(o, AO) Σ o..)
Applying the above theorem with r 2, we obtain
B.) ... (B) Bi)l (1 + o1) + (d 1)(1L)+ =)
S + (t)) 3 (A))
When 2 log(d/E), we have [I B.) ... BII S (1 + 4te + ())i We now use the following lemma.
Lemma A.2. Let g be Gaussian random vector with each of the components being an independent standard Gaussian random variable. Let è MMg/ MM 22 For any unit vector v, with probability 2 4/5,
1
2
M M
1 C
for a large enough universal constant C.
Proof. Since u is unit vector, we can write || have
l0 Mgl ve
vo MMgll. Hence, we
Mg
1o,o\/==
|Mall 1+
111 (1-orT)Mall 10 Mg
We note that uT Mg NO, ( and E[] vu ouT)MMll3 tr(M
vo
|M [ vll. L. By union bound, with probability 2 4/5, we have
[|T vo Mg | Mg
S c || - |
||
for large enough constant C. Therefore, with probability 2 4/5, we get that
K0, (0. 2
1 + C |M MTVil
T vil
Applying the above lemma for M (B. B₂) (BT Bi) and U1 we obtain
11,11)122 T+IVV
with probability 2 4/5.
13

---

A.3 Proof of Theorem 2.5
Proof. Partition the matrix A into Anght and Anewy. where Anewry is the submatrix with rows a, such that |a:l22 > ||Al// / polylog(d) and Anghi is the remaining rows. From our assumption, the number of rows in Anewy is at most h. Note that given uniformly random stream of rows of A, we can obtain a uniformly random stream of rows of Angin by just filtering out the rows in Anewvy
A) 2 for parameter 3 to be chosen later. Let v be the top singular vector of the matrix Anewy. Note
Suppose, Aneeay vi 2l2 2 (1
A v 112 2 Meavy 1 2
Aneway v1 2 (1 1
and therefore we have (v1, 01)² 2 43, assuming R 2 2. Thus, while processing the stream, we can store all the heavy rows and at the end of the stream compute the top right singular vector of Aneavy, in order to obtain good approximation for V1.
Suppose A U0 ll2 < A1-3) This implies AAight 12 > || Aleary vi 1B 1-11 If we set 2/ R, we have
T1 (Aligh) 02( (Alighh)2
B| (A() 2 2.
Let v be the top singular vector of Anght- We will describe how to approximate of. Consider apply- ing the row norm sampling procedure with parameter E to the matrix Anght Given a row ag E Aught the corresponding sampling probability p; is given by
Clogg d
||a:122 C'log d ||A1]//(d polylog(d))
C
Pj s2 Aligh
E² 22
32 polylog(d)
Assuming that 8² 2 1/ polylog(d), we obtain that p; < 1 for all the rows in the matrix Atight Let Biigtt be the matrix obtained after applying the row norm sampling procedure the matrix Anigt- Note that p( right)
Aiggg))) and the number of rows in Blight is O(p( Aiiht) log a-²), and therefore (pp B Bught) -log 3). Setting = = a²/ log 5/2 d, we obtain that the number of rows the matrix B is (aa 4, p. B (iihht) -log d) and thus assuming s?,32 = a²8² log d 2 1/ polylog(d), we can use Theorem 2.4 to obtain vector i satisfying
1) 2 30.
30.
We will now show that of has large correlation with 01 which then implics é has a large correlation with U1 Since ||Aughhl la 2 ||Al|2 - ||Ancayy 12 2 A|| ||Ang = Alight o/ 2 3||AA|
Consider the following upper bound on || v/ 1
|r 12
Anght 1/
Aight ((11, v1) 01 + (I 11 w )o
(v1, o Atight 01 + Arigi [ vn )e
< (1 + 0) (Vi, x1))2 Al vn + (1 + 1/0) 1 ||ighh (T- - e )
for any 0 > Using the fact that the rows of the matrix Alighr are a subset of the rows of the matrix A and that [|A(I - 01 (1 ||2 - = (A) = 01 (A)/VR, R, we have
of - -1- x1)
| 112 < (1 +) 0)- (01, 01 10.:=-11-Auua ||-Augh 11 + (1 + 1/0)
R
= (11, 01) + 0) ||Angall - (1+ 1/0)
R)
(1 1/0) of/R
which implies
A 11 11+1
0. |l l12
(1 0) Anghhl - (1 + 1/)
(1 + 0) Aiihu
(1 + 1/0)aa
2 1 0 (1 1/0)/R3
using the fact that ||Angha 113 2 BBoG. Now assuming R3 2 and picking = =2/(R3 1), we obtain
4R,3
4
(01, 0110012211
1- 1- (1 R3)²
R3
14

---

We therefore have
4 R3
(0,0 v1)² 2 1
4a.
Setting 1/VR and 1/VR, we satisfy all the requirements assuming that R I polylog(d) and obtain vector satisfying (6, m1)² 1 8118/v// /R. When || A I|2 2 (1 B) we already
have a vector = top eigenvector of Aneary that satisfies 01)² 2 1 - 48 2 4/VR. Thus, in both the cases, we obtain vector satisfying (é, 21)² 2 1000011///)))
The procedure described requires knowing the approximate values of ||A||F. |Aight Since, assume that all the non-zero entries of the matrix have an absolute value at least 1/ poly(d) and most poly the values ||A|| ||-illl lie in the interval [1/ poly(d), poly(od)))) Hence, using (log nd) guesses each for | and |[iggulle and using a Gaussian sketch A similar to that in Algorithm I, we obtain vector satisfying the guarantees in the theorem.
A.4 Proof of Theorem 3.1
Proof. For each [b] let æ1,...., Fy drawn independently and uniformly at random from
[+1,-1}* Let ~ [b] be drawn uniformly at random, and for an integer k to be chosen later, let 91..... V/ E Rd be vectors that share the first (1 717 coordinates with the vector Dg. Each of the last elements of each of V1...... . Yv sampled uniformly random from the set { {+1, -1): }-
Define 21,.... # such that for j S h 2j æy and for j >> h, let z, リーーh
Now consider the stream 2.,.... t4+ Price and Xun argue that when k 2 4R, the gap of this stream is at least R with large probability over the randomness used in the construction of the stream. Let π [h + k] + [h + k] be uniformly random permutation independent of i. Consider the following event
π (i) < h/2 and Thh + 1), T + k)) > h/2.
We have that the probability of the event & is
h/2 k h/2 k k-1 h+ h
h/2 +
h/2
2 (1/2)k+1
h+1
Let St be the set of permutations that satisfy the above event. Therefore we have Pr. E S 2 11/22k+1 If the probability of failure, ö, of the algorithm A satisfies 8 S (1/2)k+4, we have that
Pr JT. internal randomness
[A succeeds on (1))) ( E St] 2 4
Let Smid be the state the algorithm after h/2 steps and Sna be the final state of the algorithm. The randomness in Sän is from the following sources: (i) randomness of the vectors Zi...., Eb. (ii) the index é E [M]. (iii) the vectors yı,..., y3- (iv) the permutation π, and (v) the internal randomness of the algorithm. From here on, condition the event & i.e., that the permutation E S, We will not explicitly mention that all entropy and information terms in the proof are conditioned on E. Since (i) < h/2, have
Síin is conditionally independent 21{(1 - 7) d 1: given 8mid-
Using the data processing inequality, we obtain that
( x; [11 7) d + 1 d) I(Snni x4 7)) d+ 1: d)).
When & S. cd/ R2, k 4R, 1/4 and S k2 for a small constant, we have as in the proof of Theorem 1.5 in Price and Xun (2024) that,
I(Smn: x;5(1 - 7) + 1 : d) 2 Q(d/R)
which now implies
[(Smid) ai (11 7) d + d) (d/R).
Note that conditioned on the event E, the distribution of uniform over - n (1), π (h/2) ). We now prove the following lemma:
15

---

Lemma A.3. Let 1..... Ye be independent random variables. Ler i ~ [e] be uniform random variable independent of X. We have
((x: Y1) 1(X; 2 (x)xx)( logg e).
Proof. By definition, we have
1(x: HYY))) H(Y; X).
Now, note that HY))) & HYY,))) (, ( HY; | logg ( +(. We now
lower bound HY;; X). Since conditioning always decreases entropy, we obtain
H(Y; X) H i.
As X is independent of i, we have
H(Y: x 2 H(Y X) H(Y, X) + H(Y (X)
&
which then implies
[(x H()) H(Y,) +... H(Y)) H(Y, X) + H(Y X)
E
< + (X: Y1) + + (1X;; Y.)
Since (t) = loog we have the proof.
Using this lemma,
I [8midd xx 1(1)(11 - 7) d d)) + ... [(8midi 2t "x-1(//2[(11-))
-1 -d d ++: :dd)
= (h/2)- ((mmid 2il(1 7) d + 1: d 10g2(h/2))
2 (hhdd/ R) h logg h.
Lemma A.4. If xxXY Y are independent, then I(2; (X,Y) 2 () I(Z; Y).
Proof.
I(Z - Y) Z).
Z)
= -(X) +
Now, we note that for any three random variables X, Y. Z, we have H((x, Y) Z) < 11( Z) + H(Y Z) which proves the lemma.
Using the independence of .1..... 24 conditioned on the event E, we obtain
[S8mid ( 1()) (1))((1111111) 7) d + 1 d]. ... 2x 11122)((1111111011111111111 -1) d + 1: d))) 2 (R) h logg h
which then implies
H(smiu) 2 ((hd/R)
using the fact that R = (d). Finally, we have max |mmid| 2 Mhhd/ R). Here |amial is the number of bits used in the representation of the state miid-
A.5 Proof of Theorem 5.1
Proof. Our instance consists of the following vectors:
1. R copies of the vector (1/VR)e1,
2. copy of the vector (1 (1/VR E)e2, and
3. copics of the vector (1/va R)e3.
16

---

where a = 2M. Let A be a matrix with rows given by the stream of vectors defined above. We note that the matrix A has rank and the non-zero eigenvalues of the matrix A A are 1, 1/(R E), 1/R and therefore the gap A (1 A)/ (A and the row with the largest norm is (1/vR e)e2. Thus, the row with the largest norm is not useful to obtain correlation with the true top eigenvector é1.
R E. The top eigenvector of the matrix A e1
Consider execution of Oja's ' algorithm with learning rate r7 on the above stream of vectors. The final vector 2n can be written as
Fn - (1+ 2
Reeet) R 22 Ra
(
(1+
- e2el
vo-
For j E [d], let 2ij denote the j-th coordinate of the vector 2; so that we have
R
2x1
+
201.
11
2n2
1
202:
and
R E
2n3
1 +
2003
Ra
2M, we have n/Ra I 1/2 and therefore (1 + RR) 2 exp(n/2Ra:) and (1 + n/ Ra) 2 exp(n/2R).
We note that Enj = 2ay for all j > 3. Since
Recall that we want to show that (zn, en)l < c||za|1e ll2 with a large probability. Suppose otherwise and that with probability 2 1/10, have (2n; ei)l <l zm|122 cll(O, 0, O, 204, 20a)
Since, 2o is initialized to be random Gaussian, we have [| 0, 0, 204..... 2od) ll2 vd/2 with probability - exp(- d). Thus, we have with probability 2 1/11 that,
| 2 evd/2
which implies the learning rate must satisfy
(1 (1+n/R) d' dd///2
since |201| < 10 with probability 2 99/100. Hence r7 2 R((ddV/)//R 1). Now consider
(2n, (/)l/((2nx e.)]. We have
(Zn,
exp(n/R) R)
=03
(Zn, e1)l
(1+ 7/ R)
2001
With probability 2 95/100, we have 1/C < 1203 |201| now consider the expression
s C' for large enough constant C. We
exp(n/R) R)
(1 + n/ R)
The expression is minimized at 1 R² R and is increasing in the range " [R² - R, oo). When, R = O(log d/ log log d), we have that R² R < R((d/d/2)1/R - 1) and therefore for all 2 R((c'd1/231/R 1). we have
exp(n/R) cxp((cdd/2)11/ (1+ /
2 e 1/2
When R O(lg d/ loglog d), we have
exp(n/R) R)
(1 + m/ Ry poly(d)
which then implies (z,, ez) our assumption that (zn, e1) 2 cl|2x112
(2 e1)l poly(d)/CC with probability 2 95/100 which contradicts
17

---

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: Our paper purely theoretical studying space-efficient algorithms for approx- imating the top eigenvector. We prove all the claims made in the abstract and introduction.
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 motivation as long as it 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: We do not have specific limitations section but we do qualify all the state- ments noting the assumptions that need to be made to prove that our algorithms work.
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 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 (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated 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 a few datasets or with a 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 ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably provide closed captions for online lectures because fails to 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 ad- dress problems of privacy and faireess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers dis- cover limitations that aren't acknowledged in the paper. The authors should their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community, Re- viewers 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 a complete (and correct) proof?
18

---

Answer: [Yes]
Justification:
We include all the proofs in the main body and 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 theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: No experimental results are given this paper.
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 is a specific model and empirical evaluation, may 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 a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibilityy may be tricky in some cases, in which case thors are welcome to 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., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
19

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/ jublic/guides/Cdeer
wwiiisssiooliiii for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
//iis. htppppulcggidiee /odee Surmissiissssi iiiimisssioiii wwwiisssssooooooo ionoolicy) 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. only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at 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 run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
20

---

The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 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 figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as 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 failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
http:///pp.p.ppbblc///ccteieeeee ines?
Answer: [Yes]
Justification: Results in this paper purely theoretical. While the algorithms proposed in this paper may be used with potentially negative consequences, the authors are unaware of such uses.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethies.
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., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative so- cictal impacts of the work performed?
Answer: [No]
Justification: Our work studies algorithms for the top eigenvector estimation problem. Our work is purely theoretical. While our algorithms may be used to impact society in negative way, unaware of such usecases.
Guidelines:
The answer NA means that there no societal impact of the work performed.
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.
21

---

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 spe- cific 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 a 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 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 unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use the model, for example by re- quiring that users adhere to usage guidelines restrictions 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 is 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 are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: [NA]
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.
license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswi thcode. com/datased has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
If assets are released,
22

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is 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 documenta- tion provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mmodll as part their submissions via structured templates. This includes details about training, license, lim- itations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember 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 pa- per include the full text instructions given to participants and screenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
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 contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, cura- tion, 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 or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research
with human subjects.
Depending the country in which research is conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.
23


Reviews:
[{"review_id": "fjIWkkgP2c", "reviewer": "Reviewer_yHif", "summary": "Given a stream of $n$ data-points $a_1, a_2, \\dots, a_n \\in \\mathbb{R}^d$, this paper studies the problem of approximating the top eigen-vector of the matrix $A^T A$ at the end of the stream, where $A \\in \\mathbb{R}^{n \\times d}$ is the data-matrix with rows of the matrix corresponding to the data-points. This is the same problem as approximating the first principal component in PCA. Prior work on this problem by Price (2023) gave an algorithm that works with some worst-case guarantees i.e. both the data-points and the order of the data-points can be chosen by the adversary. This paper is the first to study the setting where although the data-points can be chosen arbitrarily by the adversary, the order of arrival of the data-points is uniformly at random. For this setting, the paper provides an algorithm with improved guarantees over the algorithm by Price. Additionally, they also provide a lower bound for streaming algorithms for the random-order arrival model.", "questions": "How do the guarantees in this paper extend to the setting where you need to approximate not just the top eigen-vector, but the top $k$ principal components, for some arbitrary value of $k$? I understand that this might not be straight-forward to answer, but at the very least, it would be nice to have a conclusion or future directions section at the end of the paper, with a brief discussion on this.\n\nMinor editing comment:\nFor the paper “Syamantak Kumar and Purnamrita Sarkar. Streaming PCA for Markovian data.”, please use the Bibtex citation from the official NeurIPS website instead of Google Scholar. The current citation reads as NeurIPS 2024, but it actually appeared in NeurIPS 2023..", "limitations": "Primarily a theory paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Originality: First paper to study the problem of approximating the top eigen-vector in the random-order arrival setting.\n\nQuality and Clarity: Overall well-written paper.\n\nSignificance: The paper can certainly do a better job of motivating the problem. This paper is primarily a theory paper but since the problem studied is closely related to PCA, which is obviously very important in practical applications, it is easy to imagine scenarios where the algorithm described in this paper can be implemented. For example, in the case of PCA for population genetics, where the dimensionality of the data (number of genetic markers) can exceed 10 million, and the number of samples in standard datasets like UK Biobank is of the order of hundreds of thousands, you could imagine running this algorithm in one-pass to approximate the top principal component, running it on a second pass to approximate the second principal component, and then using a third pass to map all the points using these two components (most PCA studies in population genetics papers just use 2 components as they are easy to visualize in papers). Even otherwise, as multiple papers on the closely-related \"Streaming PCA\" problem have appeared in past iterations of NeurIPS and other related conferences, this paper is  clearly relevant to NeurIPS.", "weaknesses": "Paper needs to do a better job motivating the problem. This is a submission to NeurIPS, not COLT. Clearly, the paper has interesting technical contributions but I think this might be a major weakness for the paper. Some suggestions for the same:\n\nIt would be nice for the introduction of the paper to have at least a few lines motivating the case for high-dimensional d and why the distinction between $d^2$ and $d$ is something which matters in real-world applications. For example, see the paper “Memory Limited, Streaming PCA” by Mitliagkas, Caramanis, and Jain, which appeared in NeurIPS 2013: “In certain high-dimensional applications, where data points are high resolution photographs, biometrics, video, etc., $p$ often is of the order of $10^{10}$ - $10^{12}$, making the need for $O(p^2)$ memory prohibitive. At many computing scales, manipulating vectors of length $O(p)$ is possible, when storage of $O(p^2)$ is not.”\n\nA great reference to add on line 80 would be the book chapter by Gupta and Singla titled “Random-Order Models” which appeared in the book “Beyond Worst-Case Analysis” edited by Tim Roughgarded.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the reference suggestions. We will add them to the introduction in the final version.\n\n> How do the guarantees in this paper extend to the setting where you need to approximate not just the top eigen-vector, but the top $k$ principal components, for some arbitrary value of $k$?\n\nIn practice, one can do $k$ passes over the data and by projecting away the vectors computed in the previous rounds, we can obtain approximations to the top $k$ singular vectors. But we do not have any guarantees on how good such approximations are. The main reason is that the approximation guarantee i.e., $\\langle\\hat{v}, v_1\\rangle^2 \\ge 1 - 1/\\sqrt{R}$ that we obtain in the first pass is not sufficient to ensure that the gap between the top 2 singular values of the “residual stream” i.e., of the vectors $(I-\\hat{v}\\hat{v}^T)a_1, \\ldots, (I-\\hat{v}\\hat{v}^T)a_n$ is large enough for the algorithm to work.\n\nIt is an interesting open question to extend our algorithm or obtain an algorithm using a different approach for k-SVD for the worst case input matrices $A$ presented to the algorithm in a uniform random order. We note that the work of Price also only applies to the top eigenvector and the same open question applies there as well.", "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": "f3lqDqDomY", "reviewer": "Reviewer_Yww1", "summary": "This paper is concerned with estimating a direction that is well-correlated with the top eigenvector $v_1$ of a matrix where the rows $a_1, \\dots, a_n$ are streamed to us in uniformly random order. To make this well-defined, a gap assumption is required, i.e., that $R \\coloneqq \\lambda_1(A^{\\top}A)/\\lambda_2(A^{\\top}A) \\gg 1$. A successful algorithm is one that returns an estimate vector that is $1 - o_{R}(1)$ correlated with $v_1$ while using at most $\\widetilde{O}(d)$ space. Note that if we are allowed to use $d^2$ space, then the problem is trivial, as we can simply maintain $A^{\\top}A$. Thus, one of the main challenges is to figure out how to estimate $v_1$ when we are not allowed to remember too many of the rows we have seen so far.\n\nThe main result is an algorithm that uses $\\widetilde{O}(hd)$ space and outputs a unit vector $u$ such that $\\langle u, v_1 \\rangle \\ge 1-C/\\sqrt{R}$ for some universal constant $C$, and where $h$ denotes the number of \"heavy\" rows (those that contribute at least a $\\sim 1/d$ fraction to the Frobenius norm of $A$). This dependence on $h$ is essentially optimal, as the authors give a lower bound saying that any algorithm that outputs a vector with at least $1-1/R^2$ correlation must use $hd/R$ space.\n\nThe main technical contribution is to observe that if the rows of $A$ are randomly permuted and streamed to us, then in some sense, we can see $\\sim \\log d$ spectral approximations to $A$ in disjoint contiguous windows of the stream. Thus, the power method can be simulated by adding $a_i\\langle a_i, u \\rangle$ to the estimate in each round. To actually form the spectral approximations and implement this with low space, the authors use a row sampling result which says that one only needs to choose and reweight $\\sim \\rho/\\varepsilon^2$ rows of $A$ to form a decent spectral approximation to $A$, where $\\rho$ denotes the stable rank of $A$. So, the authors use the row sampling result to form $\\log d$ many spectral approximations to $A$ and then simulate the power method on these approximations. The final result follows from showing that the top eigenvector of the spectral approximations is reasonably well correlated with the top eigenvector of $A$, which itself follows from standard eigenvector perturbation tools and the gap assumption. \n\nAlthough this does not immediately work for heavy rows (e.g. consider a more difficult scenario where there is one row orthogonal to all the other rows in the matrix, it has large norm, and it witnesses $v_1$, then we must remember it), the simple fix is to just identify heavy rows on the fly and store those exactly. As mentioned earlier, this linear dependence on the number of heavy rows is necessary.", "questions": "None", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The problem is a very natural one and the random order stream of a worst-case matrix is a nice assumption that allows one to get more optimistic results while not trivializing the question.\n\nThe algorithm is really simple and easy to interpret. The solution/analysis are very elegant. The writing is also clear. Finally, the idea and execution are pretty insightful.", "weaknesses": "In order to implement the row sampling result, we need an estimate on the operator norm of $A$. The authors fix this by assuming that the coordinates of the inputs are between $1/poly(nd)$ and $poly(nd)$ and then maintaining $\\log(nd)$ copies of the algorithm in parallel. This is not too big of a deal, but I wish this assumption were made more explicit towards the beginning of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5vYCZJGIx4", "reviewer": "Reviewer_CKd4", "summary": "The paper studies the problem of approximating the top eigenvector of $A^T A$ when rows of an $n \\times d$ matrix $A$ are given in a stream. The authors consider worst-case inputs $A$ but assume the rows are presented in a uniformly random order.\nThey show that when the gap parameter $R = \\sigma_1(A)^2 / \\sigma_2(A)^2 = \\Omega(1)$, there is a randomized algorithm using $O(h \\cdot d \\cdot \\text{polylog}(d))$ bits of space that outputs a unit vector $v$ with correlation $1 - O(1/\\sqrt{R})$ with the top eigenvector $v_1$.\nHere, $h$ denotes the number of \"heavy rows\" in the matrix, defined as rows with Euclidean norm at least $|A|_F / \\sqrt{d \\cdot \\text{polylog}(d)}$. The authors provide a lower bound showing that any algorithm using $O(hd/R)$ bits of space can obtain at most $1 - \\Omega(1/R^2)$ correlation with the top eigenvector. Their results improve upon the $R = \\Omega(\\log n \\cdot \\log d)$ requirement in a recent work by Price. The authors' algorithm is based on a variant of the block power method. They also show improvements to the gap requirements in Price's analysis for both arbitrary order and random order streams. \nThe techniques involve row sampling, concentration inequalities, and careful analysis of the power method with approximate quadratic forms.", "questions": "How does your algorithm compare with Price's algorithm in practice? \n\n### Typos \n- line 123, centralized equation, $CR^2$ should be $(CR^2)$. \n- line 124, $a/\\|a\\|_2$ should be $v/\\|v\\|_2$.\n- line 144, $td/R$ should be $hd/R$.\n- line 4 of Algorithm 1, $n\\epsilon^2$ should be $(n\\epsilon^2)$.\n- line 10 of Algorithm 1, $A_{j\\cdot (2np):j\\cdot (2np)+y_j}$ should denote the rows in the range $j\\cdot (2np):j\\cdot (2np)+y_j$, right? $j$ should be $j-1$, then.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper introduces a novel algorithm to approximate the top eigenvector in random order streams, a significant advancement over previous methods that required multiple passes over the data or had more stringent conditions. One of the key strengths is its method for handling heavy rows in the matrix. By storing the rows with large Euclidean norms separately and processing the remaining rows, the algorithm ensures an accurate approximation of the top eigenvector​. \nThe algorithm achieves near-optimal space complexity, using $O(h \\cdot d)$ space where $h$ is the number of heavy rows, which is shown to be nearly tight. Moreover, The paper improves upon the gap requirements needed for the algorithm to work. It reduces the gap $R$ from $\\Omega(\\log n \\cdot \\log d)$ to $\\Omega(\\log^2 d)$ for arbitrary order streams and from $\\Omega(\\log d)$ to constant for random order streams. The use of row norm sampling as a general technique to reduce the number of rows while preserving the top eigenvector is a versatile approach.", "weaknesses": "The main weakness of this work is the lack of empirical validation. Given the simplicity of their algorithm and the ease of generating synthetic matrices with a given sequence of singular values, it should be easy to perform experiments to compare it with Price's approach and provide insight into its practical effectiveness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments.\n\n> Separation in Practice\n\nIn section 5 of the paper, we give a synthetically constructed instance for which Price’s algorithm does not give a good approximation to the top singular vector. For instances observed in practice, it seems harder to show such a separation. In many practical instances, the observations i.e., the rows are sampled from a nice enough distribution for which earlier analyses of Oja’s algorithm show very good approximability of the top eigenvector.", "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": "DzRmPR7gY3", "reviewer": "Reviewer_S42D", "summary": "The paper studies the problem of finding the top eigenvector of a matrix in the streaming model. The problem is: given a sequence of d-dimensional rows a_1, a_2, ..., a_n of a matrix A, approximately compute the top eigenvector v_1 of A^TA. The algorithms gets a single pass over the stream of input rows, must use subquadratic (in d) space, and should output an approximation \\hat v_1 to v_1. \n\nExisting works on this problem have the following natural idea at their core: initialize a vector z\\in R^d to be zero, and then, upon receiving a row a_i, set z\\gets z+ \\eta a_i^T z a_i for some learning rate \\eta. One can either keep a fixed learning rate, or use a combination: the latter is done in Price's algorithm from a few years ago, which computes an approximation \\hat v_1 that is at least 1-O(log d/R) correlated with v_1, where R is the eigenvalue gap \\sigma_2(A^TA)/\\sigma_1(A^TA). Price also showed that a 1-O(1/R^2) correlation requires almost quadratic in d space. \n\nThe author(s) result is that in random streams, the correlation bound can be improved to 1-O(1/\\sqrt{R}). They complement their algorithmic result with a lower bound for Price's algorithm -- this is basically an adaptation of Price's lower bound to random order streams. They also provide certain impossibility results for fixed rate Oja's algorithm.\n\nThe main algorithmic technique is clean. The main point is that the fact that the stream is randomly ordered implies that its substreams contain good spectral approximations to the original matrix -- this is by standard spectral concentration bounds (after removing heavy entries). Due to the spectral gap assumption the top eigenvectors of these rescaled submatrices are close to v_1. Thus, one can run the power method on the substreams, of which there are quite a few. Thus, a good convergence can be obtained.", "questions": "None.", "limitations": "None.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. The authors provide a clean analysis of a very natural algorithm for top eigenvector computation in data streams.  This is definitely worth publishing.", "weaknesses": "W1. I am not sure how novel the idea of using substreams that concentrate around A as steps in the power iteration is. If it is, then this is a very nice paper. Otherwise it can be seem more as a sharpening of Price's result.\n\nW2. The author(s)' overview of related work on random streams is not up to date. From their list of citations if seems that there was no work done on random streams between 2009 and 2023. See, for example, https://arxiv.org/pdf/2110.10091 and references therein.\n\nW3. I find it strange the author(s) use an unpublished result (Magdon-Ismail, 2010) from 14 years ago for the concentration bound that their analysis relies on. I recommend looking at Joel Tropp's survey on matrix concentration for a more formal reference.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for suggestions on citations for the random order model. We will add more references in the final version of the paper.\n\n>  Using substreams for quadratic approximation\n\nWhen each row of the stream is independently sampled from a distribution, Hardt and Price analyze a similar block power method. In that case, it is much easier to argue that the substreams concentrate around the covariance matrix. But, in our case, we assume that the rows of the matrix are fixed and the only randomness is in the order the rows are presented to the streaming algorithm. This makes the problem quite different to the one considered by Hardt and Price and hence the techniques used to achieve our proofs are different as well.\n\n> Using Magdon-Ismail’s result\n\nWe used the manuscript of Magdon-Ismail as the main reference since it directly has the result in the form we require. But we agree that citing Tropp’s work would be useful for the readers. We will include a citation in the final version of the paper.", "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:

Meta-review: This paper studies the problem of approximating the top eigenvector of the matrix in the random order data stream model. Both upper and lower bounds are provided.

All reviewers agreed that the problem studied is natural, and that the random order stream is a reasonable model for obtaining more optimistic results. It is also very nice that the space complexity of the proposed algorithm is nearly optimal.
Decision: Accept (spotlight)