Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm

By Prateek Jain, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, Aaron Sidford. 2016

140 citations recorded by the source corpus.

This work provides improved guarantees for streaming principle component analysis (PCA). Given $A_1, \ldots, A_n\in \mathbb{R}^{d\times d}$ sampled independently from distributions satisfying $\mathbb{E}[A_i] = \Sigma$ for $\Sigma \succeq \mathbf{0}$, this work provides an $O(d)$-space linear-time single-pass streaming algorithm for estimating the top eigenvector of $\Sigma$. The algorithm nearly matches (and in certain cases improves upon) the accuracy obtained by the standard batch method that computes top eigenvector of the empirical covariance $\frac{1}{n} \sum_{i \in [n]} A_i$ as analyzed by the matrix Bernstein inequality. Moreover, to achieve constant accuracy, our algorithm improves upon the best previous known sample complexities of streaming algorithms by either a multiplicative factor of $O(d)$ or $1/\mathrm{gap}$ where $\mathrm{gap}$ is the relative distance between the top two eigenvalues of $\Sigma$. These results are achieved through a novel analysis of the classic Oja's algorithm, one of the oldest and most popular algorithms for streaming PCA. In particular, this work shows that simply picking a random initial point $w_0$ and applying the update rule $w_{i + 1} = w_i + \eta_i A_i w_i$ suffices to accurately estimate the top eigenvector, with a suitable choice of $\eta_i$. We believe our result sheds light on how to efficiently perform streaming PCA both in theory and in practice and we hope that our analysis may serve as the basis for analyzing many variants and extensions of streaming PCA.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Parallelizing Stochastic Approximation Through Mini-Batching and Tail-Averaging (2016, methodology): “In particular, possible future directions could include understanding mini-batching thresholds and effects for stochastic approximation with the Logistic Loss using the framework of [16], more general convex functions [9] and for PCA using the framework of [30].”
Differentially Private Matrix Completion, Revisited (2017, methodology): “In particular, we use Oja’s algorithm [30], which computes top eigenvectors of a matrix with a stochastic access to the matrix itself.”
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, methodology): “The idea of Neon was built upon Oja’s iteration for principal component estimation (Oja, 1982), and its global convergence rate was proved to be near-optimal (Li et al., 2017; Jain et al., 2016).”
Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU (2017, background): “[23] obtained an optimum formula for ε when B has a large gap between its first two leading eigenvalues; and they raised it as an open question in the case without any eigengap assumption.”
Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification (2016, methodology): “The proofs turn out to be tedious for γ ∈ γ b, max 2 , γ b, max and can be found in the initial version of this paper Jain et al. (2016b) and these were obtained through generalizing the operator view of analyzing SGD methods introduced by D´efossez and Bach (2015).”
A survey on data preprocessing for data stream mining: Current status and future directions (2017, background): “A novel analysis of theorethical properties of Oja’s streaming PCA was discussed in [100].”
Online Factorization and Partition of Complex Networks From Random Walks (2017, unknown): “Our method is also related to the class of online eigenvalue decomposition methods for representation learning [1, 10, 22, 2, 8].”