The Phase Transition in Online PCA Depends on $n/d\log(d)$, not $n/d$

High dimensional statistical theory has established the importance of constant aspect ratio, when the number of dimensions (d) and samples (n) satisfy n,d\to\infty with n/d\to γ\in(0,\infty), in understanding the limits of canonical estimation problems. In particular, for estimating the top eigenvector of a d\times 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 Σ=θ^2 v_0v_0^\top+I\in\mathbb{R}^{d\times d}, and run Oja's algorithm with step size δ/d on n iid samples X_k\simN(0,Σ), with output \hat v_n. Then, as n,d\to\infty with n/d\log d\toγ\in(0,\infty), we establish a phase transition: |\langle\hat v_n,v_0\rangle|\to 0 when γ<γ_, and \toρ_ when γ>γ_. Here ρ_=ρ_(θ,δ)=\sqrt{(θ^2-δ/2)+/θ^2(1+δ/2)} and γ=γ_(θ,δ)=1/2δ(θ^2-δ/2)+. Further, at criticality, when n=[γd\log d+ηd] and d\to\infty, η\in\mathbb{R}, the correlation is random: |\langle\hat v_n,v_0\rangle|\stackrel{w}{\to}ρ_|G|\exp(η/2γ_)/\sqrt{ρ_^4+G^2\exp(η/γ_)} where G\simN(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.