Unverified 2026

Phase-aware Oja preconditioner

Implementation & benchmark of arXiv:2607.23914 — The Phase Transition in Online PCA Depends on $n/d\log(d)$, not $n/d$

Usefulness5/10
Difficulty5/10
Novelty7/10

Source paper: The Phase Transition in Online PCA Depends on $n/d\log(d)$, not $n/d$ arXiv:2607.23914 ⓘ · analyzed Aug 30, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Use Oja's streaming eigenvector estimate on a parameter block's incoming gradient stream, but activate its rank-one preconditioning correction only after the mathematically predicted d log d sample threshold. Before that point, the estimate is treated as unreliable and the optimizer remains close to AdamW or SGD. This prevents early noisy spectral directions from destabilizing training while retaining an O(d)-memory alternative to storing a full gradient covariance matrix.

Formulas

$$\tilde{v}_{k}=\tilde{v}_{k-1}+\frac{\delta}{d}\langle X_{k},\tilde{v}_{k-1}\rangle X_{k},\qquad \hat{v}_{k}=\frac{\tilde{v}_{k}}{\|\tilde{v}_{k}\|_{2}}.$$
$$\Sigma=\theta^{2}v_{0}v_{0}^{\top}+I_d,\qquad \gamma_* = \frac{1}{\delta(2\theta^{2}-\delta)_+},\qquad \rho_* = \sqrt{\frac{(\theta^{2}-\delta/2)_+}{\theta^{2}(1+\delta/2)}}.$$
$$n_{\mathrm{crit}}(d,\delta,\hat\theta)=\frac{d\log d}{\delta(2\hat\theta^{2}-\delta)}\quad\text{for }0<\delta<2\hat\theta^2,$$
$$\alpha_n=\sigma\!\left(\frac{n-n_{\mathrm{crit}}}{\tau n_{\mathrm{crit}}}\right),\qquad g'_n=g_n-\alpha_n\,\frac{\langle g_n,v_n\rangle}{\hat\lambda_n+\varepsilon}\,v_n.$$

Mathematical statement

For samples X_k distributed as N(0, Sigma), with Sigma = theta^2 v_0 v_0^T + I_d, v_0 in the unit sphere S^(d-1) is the population top eigenvector, theta^2 is its excess eigenvalue, d is the block dimension, and Oja uses step size delta/d. The paper's recursion is tilde(v)_k = tilde(v)_(k-1) + (delta/d) <X_k, tilde(v)_(k-1)> X_k, followed by normalization. In the regime n/(d log d) -> gamma, alignment is asymptotically zero for gamma < gamma_* and approaches rho_* for gamma > gamma_*. The critical ratio is gamma_* = 1/[delta (2 theta^2 - delta)_+], and the limiting overlap is rho_* = sqrt((theta^2 - delta/2)_+ / [theta^2 (1 + delta/2)]), where (x)_+ = max(x, 0). The controller uses n_crit = d log(d) / [delta (2 hat(theta)^2 - delta)] when 0 < delta < 2 hat(theta)^2, and gradually activates a rank-one optimizer correction near this threshold.

Implementation notes

Integrate this into the optimizer's second-moment path for one or more large parameter blocks, such as the query or key projection of a Transformer layer or a convolutional channel block. Flatten each minibatch gradient into g_k in R^d, maintain an Oja vector v_k, and use it to identify the dominant gradient-covariance direction without storing a d by d matrix. For every minibatch: first compute g_k; update v by v <- v + (delta/d) (v^T g_k) g_k; normalize v by v <- v / (||v||_2 + 1e-8); and increment the sample counter n. Estimate the top Rayleigh quotient with lambda_hat_raw = (v^T g_k)^2 and smooth it using an exponential moving average. Estimate the isotropic residual variance with sigma_hat_squared = EMA((||g_k||_2^2 - (v^T g_k)^2) / max(d - 1, 1)), then set theta_hat_squared = max(lambda_hat - sigma_hat_squared, 0). If 2 theta_hat_squared is larger than delta, compute n_crit = d log(d) / [delta (2 theta_hat_squared - delta)]; otherwise disable the spectral correction. Define alpha_n = sigmoid((n - n_crit) / (tau n_crit)), with tau between 0.1 and 0.5. Replace the raw gradient by g'_n = g_n - alpha_n (g_n^T v_n) v_n / (lambda_hat + epsilon), then pass g'_n to AdamW, or apply this correction to the AdamW update itself. Clip lambda_hat and theta_hat_squared to robust percentile ranges because minibatch gradients are non-Gaussian. The paper supplies the Oja recursion and phase-threshold formula; all covariance, spike, and overlap quantities are estimated empirically. First test on synthetic gradients g_k = theta z_k v_0 + xi_k, where z_k is standard normal and xi_k is standard isotropic Gaussian noise, using d equal to 512 and 2048. Compare AdamW, always-on Oja correction, and the gated method. Then test a small Transformer on TinyStories or CIFAR-10. Success requires fewer early loss spikes, equal or better final loss, and lower memory than a dense covariance preconditioner. Ablate the log(d) threshold and the sigmoid gate to check whether the predicted transition explains the benefit rather than generic warmup.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.