Research map / Learning theory and algorithms / Sample complexity

A Geometric Analysis of PCA

NeurIPS 2025 · Learning theory and algorithms › Sample complexity · approach: Statistical-query lower bounds · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Treats PCA as an M-estimator on the Grassmannian, proving a CLT for the principal subspace error and an asymptotic excess-risk characterization, plus a non-asymptotic bound via self-concordance of the block Rayleigh quotient.

Problem

Characterizing the excess reconstruction risk of PCA (asymptotically and non-asymptotically) for general data distributions, beyond plug-in perturbation and ERM uniform-convergence bounds that are not tight.

Approach

View PCA as an M-estimator on the Grassmannian; prove the negative block Rayleigh quotient is generalized self-concordant along geodesics from its minimizer with maximal principal angle below pi/4, yielding a sharp non-asymptotic excess-risk bound matching the asymptotic Gaussian characterization.

Key results

• Under an eigengap and finite-moment condition, n times the excess risk of PCA converges in distribution to (1/2) times the squared Frobenius norm of a Gaussian matrix H.
• The non-asymptotic bound holds with probability 1-delta once n exceeds a distribution-dependent threshold, giving excess risk at most 75/(n delta) times the sum over i,j of E[<u_{k+i},X>^2 <u_j,X>^2]/(lambda_j - lambda_{k+i}).
• For the spiked covariance model with Gaussian noise, the asymptotic excess risk quantiles are characterized explicitly in terms of eigenvalues and noise variance.

Surprising findings

• The asymptotic risk term depends on the distribution only through second-order projections of X onto top and bottom eigenvectors, and the analysis needs only finite fourth moments rather than Gaussianity.

Limitations

• Requires an eigengap condition lambda_k > lambda_{k+1}; relaxing it is left open.
• Global step of the non-asymptotic analysis (sample complexity via Davis-Kahan, max angle below pi/4) is likely loose.
• Does not directly cover kernel PCA or functional PCA, nor high-dimensional regimes; the bound degrades under heavy tails.

Experimental setup

Metrics: excess reconstruction risk asymptotic quantiles of excess risk

Baselines: Davis-Kahan perturbation bounds Gaussian PCA excess-risk analysis Reiss and Wahl / recent projector-based PCA bounds

Builds on: Bach's self-concordance for logistic regression Davis-Kahan theorem Absil et al. optimization on matrix manifolds

Closest papers by meaning

• Refined Complexity of PCA with Outliers (ICML 2019 · similarity 0.86)
• Intrinsic Grassmann Averages for Online Linear and Robust Subspace Learning (CVPR 2017 · similarity 0.86)
• Subspace Recovery from Heterogeneous Data with Non-isotropic Noise (NeurIPS 2022 · similarity 0.86)
• Fun with Flags: Robust Principal Directions via Flag Manifolds (CVPR 2024 · similarity 0.85)
• Efficient Sparse PCA via Block-Diagonalization (ICLR 2025 · similarity 0.84)
• Fast and Provable Algorithms for Sparse PCA with Improved Sample Complexity (ICML 2025 · similarity 0.83)