Approximating the Top Eigenvector in Random Order Streams

Praneeth Kacham, David P. Woodruff · 2024

Read Approximating the Top Eigenvector in Random Order Streams by Praneeth Kacham, David P. Woodruff (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-11963.txt.

Introduction

Praneeth Kacham and David Woodruff studied how to estimate the leading pattern in a huge data table when the table streams past row by row in random order. The target, the top eigenvector of the matrix formed from the data, underlies methods from ranking to compression. Memory is the constraint: the algorithm sees each row once and can keep only a sketch.

They show that when the top pattern stands out from the rest by a constant factor, a randomized method recovers a vector almost perfectly aligned with the true one. Its memory use is tied to the number of heavy rows. A matching lower bound proves that dependence on heavy rows is unavoidable. The result loosens the standout requirement that earlier arbitrary-order methods needed, and the authors also sharpen those methods' analysis.

Catalog record

CREATORPraneeth Kacham, David P. Woodruff
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-11963

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Approximating the Top Eigenvector in Random Order Streams Praneeth Kacham, David P. Woodruff Abstract When rows of an n × d n\times d matrix A A are given in a stream, we study algorithms for approximating the top eigenvector of the matrix A 𝖳 ​ A A^{\mathsf{T}}A (equivalently, the top right singular vector of A A ). We consider worst case inputs A 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 = σ 1 ​ ( A ) 2 / σ 2 ​ ( A ) 2 = Ω ⁡ ( 1 ) R=\sigma_{1}(A)^{2}/\sigma_{2}(A)^{2}=\Omega(1) , then there is a randomized algorithm that uses O ⁡ ( h ⋅ d ⋅ polylog ⁡ ( d ) ) O(h\cdot d\cdot\operatorname{polylog}(d)) bits of space and outputs a unit vector v v that has a correlation 1 − O ⁡ ( 1 / R ) 1-O(1/\sqrt{R}) with the top eigenvector v 1 v_{1} . Here h h denotes the number of heavy rows in the matrix, defined as the rows with Euclidean norm at least ‖ A ‖ 𝖥 / d ⋅ polylog ⁡ ( d ) \|A\|_{\mathsf{F}}/\sqrt{d\cdot\operatorname{polylog}(d)} . We also provide a lower bound showing that any algorithm using O ⁡ ( h ​ d / R ) O(hd/R) bits of space can obtain at most 1 − Ω ⁡ ( 1 / R 2 ) 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 = Ω ⁡ ( log ⁡ n ⋅ log ⁡ d ) R=\Omega(\log n\cdot\log d) requirement in a recent work of 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 are presented in a uniformly random order. We additionally show that the gap requirements in their analysis can be brought down to R = Ω ⁡ ( log 2 ⁡ d ) R=\Omega(\log^{2}d) for arbitrary order streams and R = Ω ⁡ ( log ⁡ d ) R=\Omega(\log d) for random order streams. The requirement of R = Ω ⁡ ( log ⁡ d ) R=\Omega(\log d) for random order streams is nearly tight for their analysis as we obtain a simple instance with R = Ω ⁡ ( log ⁡ d / log ⁡ log ⁡ d ) R=\Omega(\log d/\log\log d) for which their algorithm, with any fixed learning rate, cannot output a vector approximating the top eigenvector v 1 v_{1} . 1 Introduction We consider the problem of approximating the top eigenvector in the streaming setting. In this problem, we are given vectors a_{1},\ldots,a_{n}\in\mathbb{R}^{d} one at a time in a stream. Let A be an n\times d matrix with rows a_{1},\ldots,a_{n} . The task is to approximate the top eigenvector of the matrix A^{\mathsf{T}}A . Throughout the paper, we use v_{1}\in\mathbb{R}^{d} to denote the top eigenvector of A^{\mathsf{T}}A . We focus on obtaining streaming algorithms that use a small amount of space and can output a unit vector \hat{v} such that \langle\hat{v},v_{1}\rangle^{2}\geq 1-f(R) , where f(R) is a decreasing function in the gap R=\lambda_{1}(A^{\mathsf{T}}A)/\lambda_{2}(A^{\mathsf{T}}A) . Here \lambda_{1}(\cdot),\lambda_{2}(\cdot) denote the two largest eigenvalues. As the gap R becomes larger, the eigenvector approximation problem becomes easier and we therefore want more accurate approximations to the eigenvector v_{1} . If one is allowed to use \tilde{O}(d^{2}) 1 1 1 The notation \tilde{O}(f(n)) is used to denote the set of functions in O(f(n)\cdot\operatorname{polylog}(n)) . bits of space, we can maintain the matrix A^{\mathsf{T}}A=\sum_{i}a_{i}a_{i}^{\mathsf{T}} as we see the rows a_{i} in the stream, and at the end of processing the stream, we can compute the exact top eigenvector v_{1} . When the dimension d is large, the requirement of \Omega(d^{2}) bits of memory can be impractical (see e.g., applications that require a large value of d in Mitliagkas et al. (2013) .) Hence, an interesting question is to study non-trivial streaming algorithms that use less memory. In this work, we focus on obtaining algorithms that use \tilde{O}(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 et al. (2018) can be used to quickly obtain accurate approximations to the top eigenvector when the gap R=\Omega(1) . In a single pass streaming setting, we cannot run these algorithms as these iterative algorithms need to see the entire matrix multiple times. There have been two major lines of work studying the problem of eigenvector 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 0 and covariance \Sigma and the task is to approximate the top eigenvector of \Sigma using the samples. In this line of work, the sample complexity required for algorithms using O(d\cdot\operatorname{polylog}(d)) bits of space to output an approximation to {v}_{1} , is the main question. The algorithms are usually a variant of Oja’s algorithm ( Oja, 1982 ; Jain et al., 2016 ; Allen-Zhu and Li, 2017 ; Huang et al., 2021 ; Kumar and Sarkar, 2023 ) or the block power method ( Hardt and Price, 2014 ; 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 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, we 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 Approximation ( 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 \tilde{O}(d/\varepsilon) bits of space, output a unit vector u such that \displaystyle\|A(I-uu^{\mathsf{T}})\|_{\mathsf{F}}^{2}\leq(1+\varepsilon)\|A(I-v_{1}v_{1}^{\mathsf{T}})\|_{\mathsf{F}}^{2}. Although the vector u is a 1+\varepsilon approximate solution to the Frobenius norm Low Rank Approximation problem, it is possible that the vector u may be (nearly) orthogonal to the top eigenvector v_{1} . 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=\Omega(\log n\cdot\log d) , a variant of Oja’s algorithm outputs a unit vector \hat{v} such that \displaystyle\langle\hat{v},v_{1}\rangle^{2}\geq 1-\frac{C\log d}{R}-\frac{1}{\operatorname{poly}(d)} where C is a large enough universal constant. On the lower bound side, Price and Xun showed that any algorithm that outputs a vector \hat{v} satisfying \displaystyle\langle\hat{v},v_{1}\rangle^{2}\geq 1-\frac{1}{CR^{2}}, must use \Omega(d^{2}/R^{3}) bits of space while processing the stream. This lower bound shows that in the important case of R=O(1) , the correlation 2 2 2 We say that the value \langle u,v\rangle^{2} denotes the correlation between unit vectors

Read the complete text