Variance-adaptive Chernoff bounds: nonasymptotically valid, asymptotically sharp confidence sets for unbounded means
Abstract
Consider the classical statistical problem of sub-Gaussian mean estimation under martingale dependence: given n observations with conditional mean μ and a known conditional sub-Gaussian proxy s>0, we seek a nonasymptotically valid confidence interval for μ. The usual Chernoff interval has half-width s√(2log(2/α)/n); it neither adapts to the actual standard deviation σ≤ s nor attains the Gaussian quantile z1−α/2. We construct an analytically closed-form nonasymptotically-valid interval under martingale dependence whose endpoints, at every iid law with σ> 0, agree almost surely to first order with X̅n±σz1−α/2/√n. The two new building blocks are a sub-Gaussian exponential supermartingale with an \emph{empirical} quadratic variance and a cubic correction term, and a sub-Gaussian continuation supermartingale, the former delivering variance adaptivity ("Empirical-Bernstein'' for unbounded data), the latter also providing the Gaussian quantile ("Empirical-Berry-Esseen'' for unbounded data). The same constructions yield a closed-form time-uniform confidence sequence with asymptotically unimprovable half-width σ√(2loglog n/n). We also give closed-form multivariate ellipsoids with the true-covariance chi-square limit, and extend the scalar Gaussian and LIL constructions to handle heavy-tailed settings where one only knows a bound on any absolute central moment of order greater than two. Experiments show substantial width reductions when the true variance is smaller than the implied variance bound, at small loss in the boundary cases. The surprising (to us) takeaway message is: given any more than two moments, one can construct fully data dependent nonasymptotic confidence sets for the mean that are asymptotically efficient.
Related
- Why Does Adaptive Batching Help LLM Pretraining? A Perspective from Unbounded Variance
- Score-based confidence intervals for variance-covariance parameters in linear mixed models
- A Localized Core-Tail Fourier-Laguerre Frame Method with Adaptive Frequency Detection for Unbounded-Domain Problems
- Adaptive confidence intervals with missing data
- FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventions
BibTeX
@misc{ramdas2026varianceadaptive,
title = {{Variance-adaptive Chernoff bounds: nonasymptotically valid, asymptotically sharp confidence sets for unbounded means}},
author = {Aaditya Ramdas and Diego Martinez-Taboada},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.42058},
eprint = {2610.42058},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.42058},
}
RIS
TY - UNPB
TI - Variance-adaptive Chernoff bounds: nonasymptotically valid, asymptotically sharp confidence sets for unbounded means
AU - Aaditya Ramdas
AU - Diego Martinez-Taboada
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.42058
UR - https://arxiv.org/abs/2610.42058
AB - Consider the classical statistical problem of sub-Gaussian mean estimation under martingale dependence: given n observations with conditional mean μ and a known conditional sub-Gaussian proxy s>0, we seek a nonasymptotically valid confidence interval for μ. The usual Chernoff interval has half-width s√(2log(2/α)/n); it neither adapts to the actual standard deviation σ≤ s nor attains the Gaussian quantile z_1−α/2. We construct an analytically closed-form nonasymptotically-valid interval under martingale dependence whose endpoints, at every iid law with σ> 0, agree almost surely to first order with X̅_n±σz_1−α/2/√n. The two new building blocks are a sub-Gaussian exponential supermartingale with an \emph{empirical} quadratic variance and a cubic correction term, and a sub-Gaussian continuation supermartingale, the former delivering variance adaptivity ("Empirical-Bernstein'' for unbounded data), the latter also providing the Gaussian quantile ("Empirical-Berry-Esseen'' for unbounded data). The same constructions yield a closed-form time-uniform confidence sequence with asymptotically unimprovable half-width σ√(2loglog n/n). We also give closed-form multivariate ellipsoids with the true-covariance chi-square limit, and extend the scalar Gaussian and LIL constructions to handle heavy-tailed settings where one only knows a bound on any absolute central moment of order greater than two. Experiments show substantial width reductions when the true variance is smaller than the implied variance bound, at small loss in the boundary cases. The surprising (to us) takeaway message is: given any more than two moments, one can construct fully data dependent nonasymptotic confidence sets for the mean that are asymptotically efficient.
ER -