Bootstrapping The Error Of Oja’S Algorithm

on YouTube ↗36m

" summary

Proves that n times the sin^2 error of Oja’s streaming PCA output follows a weighted χ2 approximation and gives conditions (eigengap, learning-rate regime with ηt≈η/n, η≈log n) under which the approximation holds; tools are Hoeffding/U‑statistic decompositions, high‑dimensional CLT for quadratic forms and matrix concentration; proposes an online multiplier bootstrap that keeps B Gaussian‑weighted Oja replicates updated using XT XT^T − X_{t−1}X_{t−1}^T scaled by 1/√2 and shows bootstrap consistency when there is variance decay (simulations match theory; flat spectra fail).

AI-written summary · about

" chapters (16)

1. 0:00Start
2. 0:35Peter and Nancy
3. 1:29Collaborators
4. 1:59Outline
5. 2:26PCA as an optimization problem
6. 4:03A SGD type algorithm
7. 7:28Prior work: Analysis of Oja's algorithm
8. 11:11Building intuition with scalars
9. 14:06The matrix case
10. 15:22Sin squared error
11. 18:15The main theorem
12. 19:18Implications of Theorem 1
13. 20:34An online bootstrap algorithm
14. 24:31Final online bootstrap algorithm
15. 25:30Result for bootstrap
16. 26:14Some experiments

" related talks

• 39mMemory Limited, Streaming PCAConstantine Caramanis · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 34mError Estimation for Randomized Numerical Linear Algebra: Bootstrap MethodsMiles Lopes · Randomized Numerical Linear Algebra and Applications 2018
• 31mRealizing RobustnessGautam Kamath · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 49mApproximate Message Passing Algorithms For Orthogonally Invariant ModelsZhou Fan · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 53mDesigning Robust LearnersJacob Steinhardt · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 01h 03mSampling for Linear Algebra, Statistics, and Optimization IMichael Mahoney · Foundations of Data Science Boot Camp 2018
• 33mTradeoffs in Large Scale Learning: Statistical Accuracy vs. Numerical PrecisionSham Kakade · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 40mOptimally Weighted PCA for High-Dimensional Heteroscedastic DataLaura Balzano · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)