Adaptive Robust Confidence Sets in High Dimensions
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 dO(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.
Related
- Adaptive Confidence Sets for Nonparametric Density Estimation under Local Differential Privacy
- Variance-adaptive Chernoff bounds: nonasymptotically valid, asymptotically sharp confidence sets for unbounded means
- Sequential Confidence Sets for Coverage-Constrained Conformal Model Selection
- Bootstrap Confidence Sets for the Number of Components in Finite Mixture Regression Models
- Fractal dimensions and quasisymmetric packing-minimalities of some homogeneous Moran sets
BibTeX
@misc{diakonikolas2026adaptive,
title = {{Adaptive Robust Confidence Sets in High Dimensions}},
author = {Ilias Diakonikolas and Chao Gao and Daniel M. Kane and Yuetian Luo},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15723},
eprint = {2610.15723},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15723},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Adaptive Robust Confidence Sets in High Dimensions
AU - Ilias Diakonikolas
AU - Chao Gao
AU - Daniel M. Kane
AU - Yuetian Luo
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15723
UR - https://arxiv.org/abs/2610.15723
AB - 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.
ER -