Adaptive Robust Confidence Sets in High Dimensions

arXiv:2610.15723v1 Announce Type: cross 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^{-Omega(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.

Source: arXiv cs.LG | 2026-10-14