stat.MLAug 18, 2026

Inference and Uncertainty Quantification for Streaming rr-PCA

Authors: Haoshu Xu, Hongzhe Li

Organizations: University of Pennsylvania

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We address two open questions in streaming PCA via Oja's algorithm: sharp operator-norm convergence for general rank under sub-Gaussian data, and distributional inference for the resulting subspace estimator. Existing convergence analyses, even in the rank-one case, either assume bounded data or leave non-vanishing remainder terms that prevent adaptation to a polynomially vanishing tail spectrum, while existing distributional results are confined to the rank-one case. Our convergence theory removes these remainder terms and yields a sharp rate. In the dense-tail spiked covariance regime, this rate matches the minimax rate up to logarithmic factors. More generally, we prove a matching lower bound, up to logarithmic factors, across both dense-tail and sparse-tail regimes under a mild nondegeneracy condition. The analysis yields a linearization of Oja's iterates, which in turn enables a high-dimensional Gaussian approximation for the general-rank subspace estimation error with an explicit limiting covariance. We also establish a row-wise Gaussian approximation over convex sets for the aligned difference, recovering prior rank-one results as special cases. For practical inference, we develop an online multiplier bootstrap algorithm and prove its consistency. Beyond streaming PCA, our techniques contribute to Gaussian approximation and bootstrap inference for nonconvex stochastic approximation.

Figures & tables

ReferenceRankTail assumptionOperator-norm error rate
[ 14 ]r=1r=1Boundedλ1(1∨ν2)Δmin⁡1n\tfrac{\lambda_{1}(1\vee\nu_{2})}{\Delta_{\min}}\sqrt{\tfrac{1}{n}}
[ 20 ]r=1r=1Sub-Gaussianλ1ν2Δmin⁡1n\tfrac{\lambda_{1}\nu_{2}}{\Delta_{\min}}\sqrt{\tfrac{1}{n}}
[ 26 ]r=1r=1Finite momentsλ1(1∨ν22)Δmin⁡1n\tfrac{\lambda_{1}(1\vee\nu_{2}^{2})}{\Delta_{\min}}\sqrt{\tfrac{1}{n}}
[ 13 ]r≥1r\geq 1Boundedλ1(1∨ν22)Δmin⁡r2n\tfrac{\lambda_{1}(1\vee\nu_{2}^{2})}{\Delta_{\min}}\sqrt{\tfrac{r^{2}}{n}}
Oursr≥1r\geq 1Sub-Gaussianλ1(ν∞∨ν2)Δmin⁡rn\tfrac{\lambda_{1}(\nu_{\infty}\vee\nu_{2})}{\Delta_{\min}}\sqrt{\tfrac{r}{n}}
Table 1: Comparison of operator-norm guarantees for ∥sin⁡Θ(Un,U∗)∥\|\sin\Theta(U_{n},U_{*})\| . Existing results are translated into our notation under Assumption 1 ; for bounds involving auxiliary distribution-dependent or boundedness parameters, we display their sharp sub-Gaussian specialization justified in Appendix A . Logarithmic factors are suppressed. The displayed rate for our method concerns the nonzero-tail regime of Theorem 1 . When \rank(Σ)=r\rank(\Sigma)=r , Theorem 2 gives geometric convergence to zero.
Figure 1: Q–Q plots comparing the bootstrap and sampling distributions for n=5000n=5000 , d=500d=500 , r=3r=3 , cη=2c_{\eta}=2 and β∈{1,4}\beta\in\{1,4\} .
 β=0.5\beta=0.5β=1\beta=1β=4\beta=4
Mean ±\pm Std coverage0.914±0.0270.914\pm 0.0270.930±0.0280.930\pm 0.0280.948±0.0210.948\pm 0.021
Table 2: Empirical coverage rates for different β\beta ’s over 200 Monte Carlo trials.
Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

 H{\cal H} -levelProjected to Rr\mathbb{R}^{r}
 unwhitenedwhitenedunwhitenedwhitened
summandξi\xi_{i}ξ~i\widetilde{\xi}_{i}ξu,i=Tu(ξi)\xi_{u,i}=T_{u}(\xi_{i})ξ~u,i=Tu(ξ~i)\widetilde{\xi}_{u,i}=T_{u}(\widetilde{\xi}_{i})
covarianceΞi\Xi_{i}Ξ~i\widetilde{\Xi}_{i}TuΞiTu∗T_{u}\Xi_{i}T_{u}^{*}TuΞ~iTu∗T_{u}\widetilde{\Xi}_{i}T_{u}^{*}
cum. cov. (finite)Γn\Gamma_{n}Γ~n\widetilde{\Gamma}_{n}Γu,n=TuΓnTu∗\Gamma_{u,n}=T_{u}\Gamma_{n}T_{u}^{*}Γ~u,n=TuΓ~nTu∗\widetilde{\Gamma}_{u,n}=T_{u}\widetilde{\Gamma}_{n}T_{u}^{*}
cum. cov. (limit)Γ\GammaΓ~\widetilde{\Gamma}Γu=TuΓTu∗\Gamma_{u}=T_{u}\Gamma T_{u}^{*}Γ~u=TuΓ~Tu∗\widetilde{\Gamma}_{u}=T_{u}\widetilde{\Gamma}T_{u}^{*}
Appendix
Table 3: Notation for summands and covariances.
β\betaMin10%20%30%40%50%60%70%80%90%Max
0.50.50.8400.8800.8900.8970.9060.9100.9200.9300.9300.9400.970
110.8600.8990.9100.9200.9200.9300.9340.9400.9500.9600.990
440.9000.9200.9300.9300.9400.9400.9500.9500.9600.9700.970
Appendix
Table 4: Quantiles across rows of the row-specific empirical coverage rates at nominal level 0.950.95 over 200 Monte Carlo trials.
β\betaMin10%20%30%40%50%60%70%80%90%Max
0.50.50.9431.0521.1071.1211.1561.1891.2141.2571.2921.3481.431
110.8991.0171.0491.0631.0821.1071.1381.1691.1971.2401.343
440.9120.9640.9871.0021.0181.0331.0581.0751.1021.1401.228
Appendix
Table 5: Quantiles across rows of the fitted slopes of the row-specific Q–Q plots against the χr2\chi_{r}^{2} distribution.
Figure 2: Row-specific Q–Q plots of the standardized quadratic statistic against the χr2\chi_{r}^{2} distribution for m=1,2m=1,2 and β∈{0.5,1,4}\beta\in\{0.5,1,4\} . The diagonal line represents exact agreement. Columns correspond to β=0.5,1,4\beta=0.5,1,4 , and rows correspond to m=1,2m=1,2 .
More in this topic

Principal Component Analysis

Principal component analysis (PCA) finds orthogonal directions of greatest variance for data compression, visualization, denoising, and feature discovery.

See all 67 papers

Explore similar work

CardsList

  1. Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy

    Sep 22, 2026Anming Gu, Syamantak Kumar, Kevin Tian +1Principal Component AnalysisDifferential Privacy

    University of Texas at Austin

  2. Rotation-Based Subspace Tracking for Robust Kernel PCA on Streaming Data

    Sep 14, 2026Kris Lokere, John FossacecaPrincipal Component AnalysisStreaming Algorithms

    Harvard University, Cambridge, MA, USA · George Washington University, Washington, DC, USA

  3. Inference of Online Newton Methods with Nesterov's Accelerated Sketching

    Apr 25, 2026Haoxuan Wang, Xinchen Du, Sen NaStochastic ApproximationSecond-Order Optimization

    School of Industrial and Systems Engineering, Georgia Institute of Technology.