Precise sample covariance spectral norm error -- an RDT view
Mihailo Stojnic
math.ST, cs.IT, math.PR, stat.ML
Submitted: 2026-07-16
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study the sample covariance error of centered Gaussians.
Terminology
Abstract
We study the sample covariance error of centered Gaussians. A remarkable breakthrough [66] established the correct error scaling order and explicitly revealed the critical role of both the effective rank and the true covariance spectrum. In this work, we move beyond scaling characterizations and determine the precise limiting value of the error's spectral norm. To do so, we develop a generic framework based on Random Duality Theory (RDT). Within this framework, we first determine closed-form, explicit RDT-based upper bounds. We then establish complementary lower bounds by introducing a novel bilinear-quadratic RDT lower-bounding mechanism. By combining this mechanism with a two-replica systems bounding strategy, we show that our lower and upper bounds match in large-dimensional contexts. Our theoretical results are supplemented with numerical evaluations and simulations, demonstrating an excellent agreement already for problem sizes on the order of thousands.
Sources
- Concentration via chaining method and its applications
- Concentration Inequalities for Sample Cross-Covariances
- Exact bounds for some quadratic empirical processes with applications
- Various thresholds for $\ell_1$-optimization in compressed sensing
- Regularly random duality
- Fully bilinear generic and lifted random processes comparisons
- Generic and lifted probabilistic comparisons -- max replaces minmax
Related papers
- Conformal Prediction for Dyadic Regression Under Complex Missingness
- Sharp Asymptotic Theory of Maximum Likelihood Estimation for Gaussian Processes with an RBF Kernel
- Bentkus-type asymptotic e-values
- High-Dimensional Asymptotics of Differentially Private PCA
- A proximal gradient algorithm for composite log-concave sampling
- KL Convergence Guarantees for Score diffusion models under minimal data assumptions