Precise sample covariance spectral norm error -- an RDT view

• URL: http://arxiv.org/abs/2607.14460v1
• Date: Thu, 16 Jul 2026 01:16:31 GMT
• Title: Precise sample covariance spectral norm error -- an RDT view
• Abstract summary: We develop a generic framework based on Random Duality Theory (RDT)<n>We establish complementary lower bounds by introducing a novel bilinear-quadratic RDT lower-bounding mechanism.<n>Our theoretical results are supplemented with numerical evaluations and simulations.
• Score: 2.538209532048867
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Inference and Uncertainty Quantification for Streaming $r$-PCA [0.40105987447353786]
  We address two open questions in streaming PCA via Oja's algorithm.<n>We prove a matching lower bound, up to logarithmic factors, across both dense-tail sparse-tail regimes.
  arXiv  Detail & Related papers  (2026-08-18T23:02:28Z)
• Variational Approximated Restricted Maximum Likelihood Estimation for Spatial Data [0.0]
  This research considers a scalable inference for spatial data modeled through Gaussian intrinsic conditional autoregressive (ICAR) structures.<n>We propose a variational restricted maximum likelihood (VREML) framework that approximates the intractable marginal likelihood using a Gaussian variational distribution.<n>By constructing an evidence lower bound (ELBO) on the restricted likelihood, we derive a computationally efficient coordinate-ascent algorithm for jointly estimating the spatial random effects and variance components.
  arXiv  Detail & Related papers  (2026-04-08T22:31:30Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  We propose a graph-based clustering algorithm that only relaxes the orthonormal constraint to derive clustering results.<n>To ensure a doubly constraint into a gradient, we transform the non-negative constraint into a class probability parameter.
  arXiv  Detail & Related papers  (2025-09-23T09:14:39Z)
• Spectrum-Aware Debiasing: A Modern Inference Framework with Applications to Principal Components Regression [1.342834401139078]
  We introduce SpectrumAware Debiasing, a novel method for high-dimensional regression. Our approach applies to problems with structured, heavy tails, and low-rank structures. We demonstrate our method through simulated and real data experiments.
  arXiv  Detail & Related papers  (2023-09-14T15:58:30Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  This paper establishes new convergence results for textitgeodesic strongly monotone games.<n>Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion.<n>Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  We study properties of random features (RF) regression in high dimensions optimized by gradient descent (SGD) We derive precise non-asymptotic error bounds of RF regression under both constant and adaptive step-size SGD setting. We observe the double descent phenomenon both theoretically and empirically.
  arXiv  Detail & Related papers  (2021-10-13T17:47:39Z)
• Oversampling Divide-and-conquer for Response-skewed Kernel Ridge Regression [20.00435452480056]
  We develop a novel response-adaptive partition strategy to overcome the limitation of the divide-and-conquer method. We show the proposed estimate has a smaller mean squared error (AMSE) than that of the classical dacKRR estimate under mild conditions.
  arXiv  Detail & Related papers  (2021-07-13T04:01:04Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  This paper introduces an analysis strategy based on derandomization, illustrated by applications to various concrete models. We provide numerical simulations of some of these lower bounds, and show a close relation to the actual performance of the Benjamini-Hochberg (BH) algorithm.
  arXiv  Detail & Related papers  (2020-05-07T19:59:51Z)

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.