mlsanityData to 7 Oct 2026

Streaming PCA for Markovian Data

arXiv 2305.02456 ↗First posted 3 May 2023math.ST cs.LG stat.MLcited by 9

Not on the map. Why?

Abstract (arXiv)

Since its inception in 1982, Oja's algorithm has become an established method for streaming principle component analysis (PCA). We study the problem of streaming PCA, where the data-points are sampled from an irreducible, aperiodic, and reversible Markov chain. Our goal is to estimate the top eigenvector of the unknown covariance matrix of the stationary distribution. This setting has implications in scenarios where data can solely be sampled from a Markov Chain Monte Carlo (MCMC) type algorithm, and the objective is to perform inference on parameters of the stationary distribution. Most convergence guarantees for Oja's algorithm in the literature assume that the data-points are sampled IID. For data streams with Markovian dependence, one typically downsamples the data to get a "nearly" independent data stream. In this paper, we obtain the first sharp rate for Oja's algorithm on the entire data, where we remove the logarithmic dependence on the sample size, n, resulting from throwing data away in downsampling strategies.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 24 of its 44 references that are in the map. First posted on arXiv 3 May 2023.

Builds on

24 of 44 references.

References · 24

  1. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  2. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  3. 2018On Markov Chain Gradient Descentcited by 63
  4. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  5. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 37
  6. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 35
  7. 2022Learning with little mixingcited by 33
  8. 2016First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Ratecited by 31
  9. 2016Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithmcited by 29
  10. 2019Estimating the Mixing Time of Ergodic Markov Chainscited by 24
  11. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 22
  12. 2021Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updatescited by 21
12 more
  1. 2020Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximationcited by 19
  2. 2020Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomnesscited by 18
  3. 2020Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learningcited by 15
  4. 2021Bootstrapping the error of Oja's algorithmcited by 11
  5. 2019AdaOja: Adaptive Learning Rates for Streaming PCAcited by 10
  6. 2018History PCA: A New Algorithm for Streaming PCAcited by 9
  7. 2021Generalization Error Bounds on Deep Learning with Markov Datasetscited by 9
  8. 2019Online matrix factorization for Markovian data and applications to Network Dictionary Learningcited by 8
  9. 2015Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computationcited by 5
  10. 2018Dimensionality Reduction for Stationary Time Series via Stochastic Nonconvex Optimizationcited by 5
  11. 2022Data Sampling Affects the Complexity of Online SGD over Dependent Datacited by 5
  12. 2019Federated Principal Component Analysiscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 2; 2025: 3; 2026: 3.

9 papers.

  1. 2024Black-Box k-to-1-PCA Reductions: Theory and Applicationscited by 7
  2. 2023Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpointcited by 5
  3. 2025Low-Precision Streaming PCAcited by 3
  4. 2024Spectral Guarantees for Adversarial Streaming PCAcited by 2
  5. 2025Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCAcited by 2
  6. 2026Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacycited by 1
  7. 2025Implicitly Normalized Online PCA: A Regularized Algorithm with Exact High-Dimensional Dynamicscited by 0
  8. 2026Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecompositioncited by 0
  9. 2026High-dimensional Adaptive MCMC with Reduced Computational Complexitycited by 0