# The Phase Transition in Online PCA Depends on n/dlog(d), not n/d

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 35 references that are in the map.
- First posted on arXiv 27 Jul 2026.

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

- [Scaling Limit: Exact and Tractable Analysis of Online Learning Algorithms with Applications to Regularized Regression and PCA](https://mlsanity.com/paper/1712.04332/) (2017)
- [AdaOja: Adaptive Learning Rates for Streaming PCA](https://mlsanity.com/paper/1905.12115/) (2019)
- [Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA](https://mlsanity.com/paper/2506.12655/) (2025)
- [Universality of high-dimensional scaling limits of stochastic gradient descent](https://mlsanity.com/paper/2512.13634/) (2025)

## Abstract (arXiv)

High dimensional statistical theory has established the importance of constant aspect ratio, when the number of dimensions (d) and samples (n) satisfy n,d→∞ with n/d→ γ∈(0,∞), in understanding the limits of canonical estimation problems. In particular, for estimating the top eigenvector of a d× d population covariance matrix from n iid samples, the BBP phase transition gives a precise threshold -- a simple functional of the aspect ratio -- such that the top sample principal component attains nonzero asymptotic correlation with the truth only when the leading population eigenvalue exceeds it. In this paper, we show that for online / streaming algorithms the story is very different, and constant aspect ratio is insufficient for nonzero overlap. We study Oja's algorithm, the most popular method for online PCA. Let Sigma=θ2 v0v0^top+I∈ℝd× d, and run Oja's algorithm with step size δ/d on n iid samples Xk~N(0,Sigma), with output hat vn. Then, as n,d→∞ with n/dlog d→γ∈(0,∞), we establish a phase transition: |langlehat vn,v0rangle|→ 0 when γ<γ_*, and →ρ_* when γ>γ_*. Here ρ_*=ρ_*(θ,δ)=√(θ2-δ/2)_+/θ2(1+δ/2) and γ_*=γ_*(θ,δ)=1/2δ(θ2-δ/2)_+. Further, at criticality, when n=[γ_*dlog d+η d] and d→∞, η∈ℝ, the correlation is random: |langlehat vn,v0rangle|stackrelw→ρ_*|G|exp(η/2γ_*)/√ρ_*4+G2exp(η/γ_*) where G~N(0,1). This is in stark contrast to ordinary high dimensional PCA, where nonzero overlap is possible at constant n/d and improves as n/d increases.