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

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

Problem Statement
The paper investigates the statistical limits of estimating the top eigenvector $v_0$ of a $d \times d$ population covariance matrix $\Sigma$ using online (streaming) algorithms. The data consists of $n$ independent and identically distributed (iid) samples $X_k \sim N(0, \Sigma)$. The study focuses on the high-dimensional regime where both the dimension $d$ and the sample size $n$ tend to infinity.

The specific model adopted is the Johnstone spiked covariance model, where $\Sigma = \theta^2 v_0 v_0^\top + I$. Here, $\theta > 0$ represents the signal strength, and the goal is to recover the principal direction $v_0$. The paper analyzes Oja's algorithm, a popular iterative method for online PCA, which updates a running estimator $\hat{v}_k$ using a step size $\delta/d$ upon observing each new sample $X_k$.

The central question addressed is: What is the precise relationship between $n$ and $d$ required for Oja's algorithm, starting from a random initialization, to achieve a non-zero asymptotic correlation (overlap) with the true eigenvector $v_0$?

Methodology
The authors employ a rigorous probabilistic analysis of the recursion governing the overlap $\rho_k = \langle \hat{v}_k, v_0 \rangle$. The methodology involves:

1. Recursive Decomposition: The update rule of Oja's algorithm is expanded using Taylor series approximations to derive a stochastic recursion for $\rho_k$. This recursion separates the deterministic drift (driven by the signal and step size) from the stochastic noise (martingale differences).
2. High-Dimensional Asymptotics: The analysis assumes $n, d \to \infty$ such that the ratio $n / (d \log d)$ converges to a constant $\gamma$. This scaling is chosen based on the observation that standard concentration inequalities are insufficient to capture the precise behavior in this regime.
3. Martingale Analysis: The stochastic terms are treated as martingale difference sequences. The authors utilize tools such as the Lyapunov Central Limit Theorem and discrete Gronwall lemmas to track the evolution of the overlap from the initial "noise floor" ($O(d^{-1/2})$) to a potential non-zero limit.
4. Phase Transition Characterization: The authors identify a critical threshold $\gamma^*$ that separates a subcritical phase (where overlap vanishes) from a supercritical phase (where overlap converges to a non-zero constant). They also analyze the critical window where $n \approx \gamma^* d \log d + \eta d$, deriving the limiting distribution of the overlap.
5. Extension to Spherical Gradient: The methodology is extended to a variant of Oja's algorithm using spherical gradients (as studied by Ben Arous et al., 2021) to demonstrate that the phase transition phenomenon is robust to this specific modification.

Key Contributions and Results

• The $n/d \log d$ Scaling: The primary finding is that for Oja's algorithm with random initialization, a non-zero asymptotic overlap is only possible if $n$ scales as $d \log d$. Specifically, if $n / (d \log d) \to \gamma$, there exists a critical threshold $\gamma^* = \frac{1}{2\delta(\theta^2 - \delta/2)}$ (assuming $\delta < 2\theta^2$).

  • Subcritical Phase ($\gamma < \gamma^*$): The overlap $|\langle \hat{v}_n, v_0 \rangle|$ converges in probability to 0.
  • Supercritical Phase ($\gamma > \gamma^*$): The overlap converges in probability to a deterministic constant $\rho^* = \sqrt{\frac{\theta^2 - \delta/2}{\theta^2(1 + \delta/2)}}$.
  • Critical Phase: At the threshold $n = \lfloor \gamma^* d \log d + \eta d \rfloor$, the overlap converges weakly to a non-degenerate random variable involving a standard normal $G$.

• Contrast with Offline PCA: The paper highlights a stark contrast with standard offline PCA. In offline PCA, the BBP (Baik-Ben Arous-Péché) phase transition occurs when $n/d \to \gamma$. Non-zero overlap is achievable with $n$ linear in $d$. In contrast, Oja's algorithm requires the extra $\log d$ factor. The authors attribute this to the high stochasticity inherent in the online updates, which requires $O(d \log d)$ steps to escape the initial noise floor.

• Optimal Step Size and Performance: The paper analyzes the dependence of $\gamma^*$ and $\rho^*$ on the step size $\delta$.

  • The threshold $\gamma^*$ is minimized (requiring the fewest samples) when $\delta = \theta^2$. At this optimal step size, $\gamma^* = 1/\theta^4$, which coincides exactly with the BBP threshold for offline PCA.
  • However, while this step size minimizes the time to reach a non-zero overlap, it does not maximize the quality of the final overlap. The limiting correlation $\rho^*$ is actually decreasing in $\delta$; thus, the optimal step size for speed yields a lower final correlation than smaller step sizes.

• Spherical Gradient Variant: The authors prove that a variant of Oja's algorithm using spherical gradients (which explicitly accounts for the manifold constraint) exhibits the exact same phase transition threshold $\gamma^*$, the same limiting overlap $\rho^*$, and the same critical distribution as the standard Oja's algorithm. This suggests the $\log d$ penalty is fundamental to the online nature of the problem rather than a specific artifact of the unnormalized update.

Significance and Claims
The paper claims to settle the question of the phase transition in Oja's algorithm in its completeness, providing precise constants and rates that were previously unknown or only bounded.

• Statistical Suboptimality: The work demonstrates that Oja's algorithm is statistically suboptimal compared to offline PCA in the high-dimensional regime. While offline PCA can succeed with $n = O(d)$, Oja's algorithm fails (converges to zero overlap) unless $n = O(d \log d)$.
• Nature of the Transition: The paper clarifies that the transition is not merely a matter of "loose" bounds in proofs but a fundamental property of the algorithm's dynamics. The extra $\log d$ factor is necessary for the algorithm to overcome the initial random initialization noise.
• Critical Behavior: The paper provides a detailed description of the "search phase" at criticality, showing that the transition from zero to non-zero overlap is governed by a random path defined by a Gaussian variable, rather than a deterministic trajectory.

The authors emphasize that these results are derived under the assumption of random initialization, contrasting with prior work that assumed "warm" starts (informative initialization), which can achieve recovery with $n = O(d)$. The findings suggest that for truly online settings with no prior knowledge of the signal direction, significantly more data is required than what is theoretically sufficient for batch processing.