# Bootstrapping the error of Oja's algorithm

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 70 references that are in the map.
- First posted on arXiv 28 Jun 2021.

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

- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [SGD without Replacement: Sharper Rates for General Smooth Convex Functions](https://mlsanity.com/paper/1903.01463/) (2019)
- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias](https://mlsanity.com/paper/2006.07904/) (2020)
- [Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm](https://mlsanity.com/paper/1602.06929/) (2016)
- [Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems](https://mlsanity.com/paper/1411.1134/) (2014)
- [An Improved Gap-Dependency Analysis of the Noisy Power Method](https://mlsanity.com/paper/1602.07046/) (2016)
- [Memory Limited, Streaming PCA](https://mlsanity.com/paper/1307.0032/) (2013)
- [Statistical inference using SGD](https://mlsanity.com/paper/1705.07477/) (2017)
- [Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates](https://mlsanity.com/paper/2102.03646/) (2021)
- [Convergence of Stochastic Gradient Descent for PCA](https://mlsanity.com/paper/1509.09002/) (2015)
- [The Fast Convergence of Incremental PCA](https://mlsanity.com/paper/1501.03796/) (2015)
- [Near-Optimal Stochastic Approximation for Online Principal Component Estimation](https://mlsanity.com/paper/1603.05305/) (2016)
- [AdaOja: Adaptive Learning Rates for Streaming PCA](https://mlsanity.com/paper/1905.12115/) (2019)
- [On the Optimality of the Oja's Algorithm for Online PCA](https://mlsanity.com/paper/2104.00512/) (2021)
- [Much Faster Algorithms for Matrix Scaling](https://mlsanity.com/paper/1704.02315/) (2017)
- [Estimating the Algorithmic Variance of Randomized Ensembles via the Bootstrap](https://mlsanity.com/paper/1907.08742/) (2019)
- [Error Estimation for Randomized Least-Squares Algorithms via the Bootstrap](https://mlsanity.com/paper/1803.08021/) (2018)
- [A Bootstrap Method for Error Estimation in Randomized Matrix Multiplication](https://mlsanity.com/paper/1708.01945/) (2017)
- [Error Estimation for Sketched SVD via the Bootstrap](https://mlsanity.com/paper/2003.04937/) (2020)

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

- [Streaming PCA for Markovian Data](https://mlsanity.com/paper/2305.02456/) (2023)
- [Oja's Algorithm for Streaming Sparse PCA](https://mlsanity.com/paper/2402.07240/) (2024)
- [Online covariance estimation for stochastic gradient descent under Markovian sampling](https://mlsanity.com/paper/2308.01481/) (2023)
- [Streaming Kernel PCA Algorithm With Small Space](https://mlsanity.com/paper/2303.04555/) (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)
- [Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression](https://mlsanity.com/paper/2302.09727/) (2023)
- [Error Estimation for Random Fourier Features](https://mlsanity.com/paper/2302.11174/) (2023)
- [Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δ](https://mlsanity.com/paper/2510.19734/) (2025)
- [Cheap Bootstrap for Fast Uncertainty Quantification of Stochastic Gradient Descent](https://mlsanity.com/paper/2310.11065/) (2023)

## Abstract (arXiv)

We consider the problem of quantifying uncertainty for the estimation error of the leading eigenvector from Oja's algorithm for streaming principal component analysis, where the data are generated IID from some unknown distribution. By combining classical tools from the U-statistics literature with recent results on high-dimensional central limit theorems for quadratic forms of random vectors and concentration of matrix products, we establish a weighted chi2 approximation result for the sin2 error between the population eigenvector and the output of Oja's algorithm. Since estimating the covariance matrix associated with the approximating distribution requires knowledge of unknown model parameters, we propose a multiplier bootstrap algorithm that may be updated in an online manner. We establish conditions under which the bootstrap distribution is close to the corresponding sampling distribution with high probability, thereby establishing the bootstrap as a consistent inferential method in an appropriate asymptotic regime.