Robust Confidence Intervals Using Side Information

We study how to construct implementable confidence intervals for the mean of a distribution with unknown, finite variance when an adversary may corrupt a constant fraction of the samples. Although robust mean estimation has been extensively studied, implementable confidence intervals remain elusive. We first observe that no asymptotically valid confidence interval of nontrivial width is possible without additional restrictions or side information. Our main result is that side information, in the form of machine learning predictions with bounded mean squared error (MSE), can enable confidence interval computation. At the core of our method is a reduction of variance estimation to an optimization problem. We prove that although the exact version of this problem is NP-hard, there is a polynomial-time additive approximation algorithm. Based on this result we develop an almost-linear time algorithm that provides an upper bound on the sample variance. We use this upper bound in our novel midpoint estimator and these together yield asymptotically valid confidence intervals uniformly over admissible adversaries. We complement our theoretical study with a series of experiments on the dataset introduced in Cen et al. (2025). We evaluate our method on real-world, bounded data, examining coverage and interval length across multiple corruption levels. Under two corruption strategies that directly try to distort the clean mean or variance of the observed samples, our method maintains coverage and non-trivial length under any considered corruption level less than 50%.