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

• URL: http://arxiv.org/abs/2607.23914v2
• Date: Thu, 30 Jul 2026 15:07:34 GMT
• Title: The Phase Transition in Online PCA Depends on $n/d\log(d)$, not $n/d$
• Abstract summary: High dimensional statistical theory has established the importance of constant aspect ratio.<n>Online / streaming algorithms are different, and constant aspect ratio is insufficient for nonzero overlap.
• Score: 1.827510863075184
• License: http://creativecommons.org/licenses/by/4.0/
• 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 γ\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\sim\mathcal{N}(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\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.

Related papers

• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
  arXiv  Detail & Related papers  (2026-03-20T01:53:44Z)
• Sparse Linear Regression is Easy on Random Supports [20.128442161507582]
  We are given as input a design matrix $X in mathbbRN times d$ and measurements or labels $y in mathbbRN$.<n>We find that if the support of $w*$ is chosen at random, we can get prediction error $epsilon$ with roughly $N = O(klog d/epsilon)$ samples.
  arXiv  Detail & Related papers  (2025-11-09T03:48:21Z)
• The Algorithmic Phase Transition in Symmetric Correlated Spiked Wigner Model [0.0]
  We study the computational task of detecting and estimating correlated signals in a pair of spiked Wigner matrices.<n>An algorithm can leverage the correlation between the spikes to detect and estimate the signals even in regimes where efficiently recovering either $x$ from $X$ alone or $y$ from $Y$ alone is believed to be computationally infeasible.
  arXiv  Detail & Related papers  (2025-11-08T15:23:44Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
  We show that the Monotonic Value Omega (MVP) algorithm achieves a variance-aware gap-dependent regret bound of $$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land mathttVar_maxtextc$.
  arXiv  Detail & Related papers  (2025-06-06T20:33:57Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  It is shown for the first time that this assumption is not required for convergence and finer results.<n>Rates of convergence are obtained for the standard algorithm and for estimates obtained via the averaging technique of Polyak and Ruppert.<n>Results from numerical experiments illustrate that $beta_theta$ may be large due to a combination of multiplicative noise and Markovian memory.
  arXiv  Detail & Related papers  (2024-05-28T05:11:05Z)
• The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning [6.416429054645991]
  Theory and application of approximation (SA) have become increasingly relevant due in part to applications in optimization and reinforcement learning.<n>This paper takes a new look at SA with constant step-size $alpha>0$, defined by the recursion, $$theta_n+1 = theta_n+ alpha f(theta_n,Phi_n+1)$$ in which $theta_ninmathbbRd$ and $Phi_n$ is a Markov chain.
  arXiv  Detail & Related papers  (2023-09-06T12:22:32Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
  arXiv  Detail & Related papers  (2023-04-17T10:38:08Z)
• A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance \& heterogeneous noise [2.019622939313173]
  We revisit heavy-tailed corrupted least-squares linear regression assuming to have a corrupted $n$-sized label-feature sample of at most $epsilon n$ arbitrary outliers. We propose a near-optimal computationally tractable estimator, based on the power method, assuming no knowledge on $(Sigma,Xi) nor the operator norm of $Xi$.
  arXiv  Detail & Related papers  (2022-09-06T23:37:31Z)
• Faster Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk [28.431572772564518]
  We consider the problem of sampling from a $d$-dimensional log-concave distribution $pi(theta) propto e-f(theta)$ constrained to a polytope $K$ defined by $m$ inequalities. Our main result is a "soft-warm'' variant of the Dikin walk Markov chain that requires at most $O((md + d L2 R2) times MDomega-1) log(fracwdelta)$ arithmetic operations to sample from $pi$
  arXiv  Detail & Related papers  (2022-06-19T11:33:07Z)
• Spiked Covariance Estimation from Modulo-Reduced Measurements [14.569322713960494]
  We develop and analyze an algorithm that, for most directions $bfu$ and $nu=mathrmpoly(k)$, estimates $bfu$ to high accuracy using $n=mathrmpoly(k)$ measurements. Numerical experiments show that the developed algorithm performs well even in a non-asymptotic setting.
  arXiv  Detail & Related papers  (2021-10-04T02:10:47Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  We consider the problem of learning a latent $k$-vertex simplex $KsubsetmathbbRdtimes n$, given access to $AinmathbbRdtimes n$. We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$.
  arXiv  Detail & Related papers  (2021-05-17T16:40:48Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  In compressed sensing, the restricted isometry property (RIP) on $M times N$ sensing matrices guarantees efficient reconstruction of sparse vectors. We investigate the exact average-case time complexity of certifying the RIP property for $Mtimes N$ matrices with i.i.d. $mathcalN(0,1/M)$ entries.
  arXiv  Detail & Related papers  (2020-05-22T16:55:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.