Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA

• URL: http://arxiv.org/abs/2506.12655v2
• Date: Sun, 20 Jul 2025 20:09:07 GMT
• Title: Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA
• Authors: Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar,
• Abstract summary: We propose a novel statistical inference framework for streaming principal component analysis (PCA) using Oja's algorithm.<n>We derive a sharp Bernstein-type concentration bound for elements of the estimated vector matching the optimal error rate up to logarithmic factors.<n>To efficiently estimate the coordinate-wise variance, we introduce a provably consistent subsampling algorithm.
• Score: 5.749787074942513
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a novel statistical inference framework for streaming principal component analysis (PCA) using Oja's algorithm, enabling the construction of confidence intervals for individual entries of the estimated eigenvector. Most existing works on streaming PCA focus on providing sharp sin-squared error guarantees. Recently, there has been some interest in uncertainty quantification for the sin-squared error. However, uncertainty quantification or sharp error guarantees for entries of the estimated eigenvector in the streaming setting remains largely unexplored. We derive a sharp Bernstein-type concentration bound for elements of the estimated vector matching the optimal error rate up to logarithmic factors. We also establish a Central Limit Theorem for a suitably centered and scaled subset of the entries. To efficiently estimate the coordinate-wise variance, we introduce a provably consistent subsampling algorithm that leverages the median-of-means approach, empirically achieving similar accuracy to multiplier bootstrap methods while being significantly more computationally efficient. Numerical experiments demonstrate its effectiveness in providing reliable uncertainty estimates with a fraction of the computational cost of existing methods.

Related papers

• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• Semiparametric conformal prediction [79.6147286161434]
  We construct a conformal prediction set accounting for the joint correlation structure of the vector-valued non-conformity scores.<n>We flexibly estimate the joint cumulative distribution function (CDF) of the scores.<n>Our method yields desired coverage and competitive efficiency on a range of real-world regression problems.
  arXiv  Detail & Related papers  (2024-11-04T14:29:02Z)
• Entrywise Inference for Missing Panel Data: A Simple and Instance-Optimal Approach [27.301741710016223]
  We consider inferential questions associated with the missing data version of panel data induced by staggered adoption. We develop and analyze a data-driven procedure for constructing entrywise confidence intervals with pre-specified coverage. We prove non-asymptotic and high-probability bounds on its error in estimating each missing entry.
  arXiv  Detail & Related papers  (2024-01-24T18:58:18Z)
• High Confidence Level Inference is Almost Free using Parallel Stochastic Optimization [16.38026811561888]
  This paper introduces a novel inference method focused on constructing confidence intervals with efficient computation and fast convergence to the nominal level. Our method requires minimal additional computation and memory beyond the standard updating of estimates, making the inference process almost cost-free.
  arXiv  Detail & Related papers  (2024-01-17T17:11:45Z)
• Robust Non-parametric Knowledge-based Diffusion Least Mean Squares over Adaptive Networks [12.266804067030455]
  The proposed algorithm leads to a robust estimation of an unknown parameter vector in a group of cooperative estimators. Results show the robustness of the proposed algorithm in the presence of different noise types.
  arXiv  Detail & Related papers  (2023-12-03T06:18:59Z)
• Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient Kernels [57.46832672991433]
  We propose a novel equation discovery method based on Kernel learning and BAyesian Spike-and-Slab priors (KBASS) We use kernel regression to estimate the target function, which is flexible, expressive, and more robust to data sparsity and noises. We develop an expectation-propagation expectation-maximization algorithm for efficient posterior inference and function estimation.
  arXiv  Detail & Related papers  (2023-10-09T03:55:09Z)
• Robust computation of optimal transport by $\eta$-potential regularization [79.24513412588745]
  Optimal transport (OT) has become a widely used tool in the machine learning field to measure the discrepancy between probability distributions. We propose regularizing OT with the beta-potential term associated with the so-called $beta$-divergence. We experimentally demonstrate that the transport matrix computed with our algorithm helps estimate a probability distribution robustly even in the presence of outliers.
  arXiv  Detail & Related papers  (2022-12-26T18:37:28Z)
• Robust leave-one-out cross-validation for high-dimensional Bayesian models [0.0]
  Leave-one-out cross-validation (LOO-CV) is a popular method for estimating out-of-sample predictive accuracy. Here we propose and analyze a novel mixture estimator to compute LOO-CV criteria. Our method retains the simplicity and computational convenience of classical approaches, while guaranteeing finite variance of the resulting estimators.
  arXiv  Detail & Related papers  (2022-09-19T17:14:52Z)
• Learning to Estimate Without Bias [57.82628598276623]
  Gauss theorem states that the weighted least squares estimator is a linear minimum variance unbiased estimation (MVUE) in linear models. In this paper, we take a first step towards extending this result to non linear settings via deep learning with bias constraints. A second motivation to BCE is in applications where multiple estimates of the same unknown are averaged for improved performance.
  arXiv  Detail & Related papers  (2021-10-24T10:23:51Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  We propose the amortized conditional normalized maximum likelihood (ACNML) method as a scalable general-purpose approach for uncertainty estimation. Our algorithm builds on the conditional normalized maximum likelihood (CNML) coding scheme, which has minimax optimal properties according to the minimum description length principle. We demonstrate that ACNML compares favorably to a number of prior techniques for uncertainty estimation in terms of calibration on out-of-distribution inputs.
  arXiv  Detail & Related papers  (2020-11-05T08:04:34Z)
• Outlier Robust Mean Estimation with Subgaussian Rates via Stability [46.03021473600576]
  We study the problem of robust outlier high-dimensional mean estimation. We obtain first computationally efficient rate with subgaussian for outlier-robust mean estimation.
  arXiv  Detail & Related papers  (2020-07-30T17:33:03Z)
• $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a Robust Divergence Estimator [95.71091446753414]
  We propose to use a nearest-neighbor-based $gamma$-divergence estimator as a data discrepancy measure. Our method achieves significantly higher robustness than existing discrepancy measures.
  arXiv  Detail & Related papers  (2020-06-13T06:09:27Z)

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.