# Streaming PCA for Markovian Data

arXiv: https://arxiv.org/abs/2305.02456 · HTML: https://mlsanity.com/paper/2305.02456/

## Key facts

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

## Builds on (most cited first, 24 of 24)

- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [Learning with little mixing](https://mlsanity.com/paper/2206.08269/) (2022)
- [First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate](https://mlsanity.com/paper/1607.07837/) (2016)
- [Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm](https://mlsanity.com/paper/1602.06929/) (2016)
- [Estimating the Mixing Time of Ergodic Markov Chains](https://mlsanity.com/paper/1902.01224/) (2019)
- [On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/2102.00185/) (2021)
- [Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates](https://mlsanity.com/paper/2102.03646/) (2021)
- [Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation](https://mlsanity.com/paper/2002.02584/) (2020)
- [Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness](https://mlsanity.com/paper/2003.10973/) (2020)
- [Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learning](https://mlsanity.com/paper/2002.02873/) (2020)
- [AdaOja: Adaptive Learning Rates for Streaming PCA](https://mlsanity.com/paper/1905.12115/) (2019)
- [Bootstrapping the error of Oja's algorithm](https://mlsanity.com/paper/2106.14857/) (2021)
- [History PCA: A New Algorithm for Streaming PCA](https://mlsanity.com/paper/1802.05447/) (2018)
- [Generalization Error Bounds on Deep Learning with Markov Datasets](https://mlsanity.com/paper/2201.11059/) (2021)
- [Online matrix factorization for Markovian data and applications to Network Dictionary Learning](https://mlsanity.com/paper/1911.01931/) (2019)
- [Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation](https://mlsanity.com/paper/1510.08896/) (2015)
- [Dimensionality Reduction for Stationary Time Series via Stochastic Nonconvex Optimization](https://mlsanity.com/paper/1803.02312/) (2018)
- [Data Sampling Affects the Complexity of Online SGD over Dependent Data](https://mlsanity.com/paper/2204.00006/) (2022)
- [Federated Principal Component Analysis](https://mlsanity.com/paper/1907.08059/) (2019)

## Built on by (most cited first, 9 of 9)

- [Black-Box k-to-1-PCA Reductions: Theory and Applications](https://mlsanity.com/paper/2403.03905/) (2024)
- [Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint](https://mlsanity.com/paper/2310.18593/) (2023)
- [Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA](https://mlsanity.com/paper/2506.12655/) (2025)
- [Low-Precision Streaming PCA](https://mlsanity.com/paper/2510.22440/) (2025)
- [Spectral Guarantees for Adversarial Streaming PCA](https://mlsanity.com/paper/2408.10332/) (2024)
- [Implicitly Normalized Online PCA: A Regularized Algorithm with Exact High-Dimensional Dynamics](https://mlsanity.com/paper/2512.01231/) (2025)
- [Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy](https://mlsanity.com/paper/2609.26508/) (2026)
- [Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecomposition](https://mlsanity.com/paper/2602.13759/) (2026)
- [High-dimensional Adaptive MCMC with Reduced Computational Complexity](https://mlsanity.com/paper/2604.09286/) (2026)

## 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.