arXiv preprint ·
Adaptive Robust Confidence Sets in High Dimensions
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study adaptive confidence sets for mean vectors of multivariate Gaussians with identity covariance under Huber contamination when the contamination proportion is unknown. We show that an information-theoretically optimal adaptive confidence set can be constructed by simultaneously quantifying uncertainty across all one-dimensional projections. The resulting confidence set achieves the optimal diameter and reveals a substantial adaptation cost compared with the minimax estimation error. Although statistically optimal, this construction is computationally infeasible. We establish a Statistical Query (SQ) lower bound showing that achieving diameter $O(m^{-1/2})$ requires either exponentially many queries or query tolerance $d^{-Ω(m)}$. Thus, in contrast to robust mean estimation, adaptation to the unknown contamination proportion incurs both a statistical cost and a computational barrier within the SQ framework. Finally, we give a low-degree moment-matching algorithm that constructs an adaptive confidence set using $d^{O(m)}$ samples and time. Its diameter bound contains an additional $O(m^{-1/2})$ term beyond the information-theoretic rate, matching the dependence on $m$ in the SQ lower bound. Together, these results characterize the statistical limits of adaptive robust confidence sets under Huber contamination and quantify a computational barrier within the SQ framework.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Statistics Theory
Explicit Bounds on Hoffman Constants for Sparse Polyhedral Regularizers
Limit Theory for Online Expectile Estimation under Short and Long Range Dependence
When do explicit penalties improve flow matching?
Distributional Regression for Arbitrary Response Variables Using ReLU Neural Networks
Reflected Proximal Dynamics for Accelerated High-Accuracy Log-Concave Sampling
Get the few papers worth your time in Statistics Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.