Streaming PCA: Matching matrix bernstein and near-optimal finite sample guarantees for oja's algorithm

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

Research output: Contribution to journalConference article

30 Scopus citations

Abstract

In this paper we provide improved guarantees for streaming principal component analysis (PCA). Given A1, . . ., An ∈ Rd×d sampled independently from distributions satisfying E [Ai] = Σ for Σ > 0, we present an O(d)-space linear-time single-pass streaming algorithm for estimating the top eigenvector of Σ. 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 n1 Pi∈[n] Ai 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/gap where gap is the relative distance between the top two eigenvalues of Σ. We achieve these results through a novel analysis of the classic Oja's algorithm, one of the oldest and perhaps, most popular algorithms for streaming PCA. We show that simply picking a random initial point w0 and applying the natural update rule wi+1 = wi + ηiAiwi suffices for suitable choice of η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.

Original languageEnglish (US)
Pages (from-to)1147-1164
Number of pages18
JournalJournal of Machine Learning Research
Volume49
Issue numberJune
StatePublished - Jun 6 2016
Externally publishedYes
Event29th Conference on Learning Theory, COLT 2016 - New York, United States
Duration: Jun 23 2016Jun 26 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Streaming PCA: Matching matrix bernstein and near-optimal finite sample guarantees for oja's algorithm'. Together they form a unique fingerprint.

  • Cite this