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

Abstract

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 \gamma\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 $\Sigma=\theta^2 v_0v_0^\top+I\in\mathbb{R}^{d\times d}$, and run Oja's algorithm with step size $\delta/d$ on $n$ iid samples $X_k\sim\mathcal{N}(0,\Sigma)$, with output $\hat v_n$. Then, as $n,d\to\infty$ with $n/d\log d\to\gamma\in(0,\infty)$, we establish a phase transition: $|\langle\hat v_n,v_0\rangle|\to 0$ when $\gamma<\gamma_*$, and $\to\rho_*$ when $\gamma>\gamma_*$. Here $\rho_*=\rho_*(\theta,\delta)=\sqrt{(\theta^2-\delta/2)_+/\theta^2(1+\delta/2)}$ and $\gamma_*=\gamma_*(\theta,\delta)=1/2\delta(\theta^2-\delta/2)_+$. Further, at criticality, when $n=[\gamma_*d\log d+\eta d]$ and $d\to\infty$, $\eta\in\mathbb{R}$, the correlation is random: $|\langle\hat v_n,v_0\rangle|\stackrel{w}{\to}\rho_*|G|\exp(\eta/2\gamma_*)/\sqrt{\rho_*^4+G^2\exp(\eta/\gamma_*)}$ where $G\sim\mathcal{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.