mlsanityData to 7 Oct 2026

Bootstrapping the error of Oja's algorithm

arXiv 2106.14857 ↗First posted 28 Jun 2021math.ST stat.ME stat.MLcited by 11

Not on the map. Why?

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.

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

Builds on

20 of 70 references.

References · 20

  1. 2016Statistical Inference for Model Parameters in Stochastic Gradient Descentcited by 71
  2. 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 59
  3. 2013The Noisy Power Method: A Meta Algorithm with Applicationscited by 58
  4. 2020An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Biascited by 45
  5. 2016Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithmcited by 29
  6. 2014Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problemscited by 25
  7. 2016An Improved Gap-Dependency Analysis of the Noisy Power Methodcited by 24
  8. 2013Memory Limited, Streaming PCAcited by 21
  9. 2017Statistical inference using SGDcited by 21
  10. 2021Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updatescited by 21
  11. 2015Convergence of Stochastic Gradient Descent for PCAcited by 17
  12. 2015The Fast Convergence of Incremental PCAcited by 15
8 more
  1. 2016Near-Optimal Stochastic Approximation for Online Principal Component Estimationcited by 11
  2. 2021On the Optimality of the Oja's Algorithm for Online PCAcited by 11
  3. 2017Much Faster Algorithms for Matrix Scalingcited by 10
  4. 2019AdaOja: Adaptive Learning Rates for Streaming PCAcited by 10
  5. 2019Estimating the Algorithmic Variance of Randomized Ensembles via the Bootstrapcited by 10
  6. 2018Error Estimation for Randomized Least-Squares Algorithms via the Bootstrapcited by 6
  7. 2017A Bootstrap Method for Error Estimation in Randomized Matrix Multiplicationcited by 5
  8. 2020Error Estimation for Sketched SVD via the Bootstrapcited by 5

Built on by

Cited by year

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

11 papers.

  1. 2023Streaming PCA for Markovian Datacited by 9
  2. 2024Oja's Algorithm for Streaming Sparse PCAcited by 9
  3. 2023Online covariance estimation for stochastic gradient descent under Markovian samplingcited by 7
  4. 2023Streaming Kernel PCA Algorithm With Small Spacecited by 5
  5. 2025Low-Precision Streaming PCAcited by 3
  6. 2024Spectral Guarantees for Adversarial Streaming PCAcited by 2
  7. 2025Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCAcited by 2
  8. 2023Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regressioncited by 1
  9. 2023Error Estimation for Random Fourier Featurescited by 1
  10. 2025Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δcited by 1
  11. 2023Cheap Bootstrap for Fast Uncertainty Quantification of Stochastic Gradient Descentcited by 0