The Phase Transition in Online PCA Depends on $n/d\log(d)$, not $n/d$
arXiv:2607.23914
2026
Training
1 ideas extracted · analyzed Aug 30, 2026
What the math gives to ML
The paper gives a sharp finite-sample warning for streaming spectral learning: Oja's algorithm does not achieve reliable alignment after merely O(d) samples, but requires O(d log d) samples under the spiked covariance model. The transferable asset is an explicit relationship between feature dimension, step size, spike strength, and the sample budget needed before an online low-rank estimate becomes trustworthy. This can make neural-network spectral trackers phase-aware: delay or attenuate low-rank preconditioning and compression until the tracker crosses its predicted alignment threshold, instead of treating the current online eigenvector as reliable from the first minibatches.
Ideas from this paper
Unverified
2026
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.
Useful5/10
Difficulty5/10
Novelty7/10