Streaming PCA for Markovian Data
This work addresses the challenge of performing inference on stationary distribution parameters when data can only be sampled via MCMC, offering a more efficient solution for scenarios with Markovian dependence.
The paper tackles the problem of streaming PCA for data sampled from a Markov chain, aiming to estimate the top eigenvector of the stationary distribution's covariance matrix. It achieves the first sharp convergence rate for Oja's algorithm on the full data, eliminating a logarithmic dependence on sample size compared to downsampling methods.
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.