Research map / Learning theory and algorithms / Sample complexity

Sub-Gaussian Confidence Intervals for Heavy-Tailed Data: Characterizing the Limits of Inference

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Optimal mean estimation and subsampling

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that sub-Gaussian confidence intervals for the mean under finite variance can be adapted to unknown variance only when a lower bound on an "effective sample size" parameter alpha_n is known, and gives a MoM-based interval of length sigma*sqrt(log(1/delta)/(n alpha_n)) with matching lower bounds.

Problem

Constructing computable, non-asymptotic confidence intervals for the mean of a finite-variance distribution with unknown variance, achieving sub-Gaussian length; existing universal intervals do not exist and prior methods need approximate symmetry of sample means.

Approach

Introduces an effective-sample-size parameter alpha_{n,delta}(xi) (truncated second moment mass of the standardized variable) that interpolates between easy and impossible regimes; uses median-of-means for the mean and a blockwise median-of-means variance estimate to build intervals of optimal length n*alpha_n-scaled, with a matching two-point mixture lower bound showing non-adaptivity to alpha_n.

Key results

• Proposed adaptive interval (alpha_n=0.25 fixed) keeps empirical miscoverage below nominal delta across alpha in {1,0.25,0.1}, while DLLO substantially exceeds nominal miscoverage as alpha decreases.
• Theory: interval length of order sigma*sqrt(log(1/delta)/(n alpha_n)) is achievable and optimal over the class P_{alpha_n}; adaptation to alpha_n is impossible without knowing a lower bound.
• Proposition: without a lower bound on alpha_n, testing/intervals with finite length are impossible (risk equals 1) for the class of all finite-variance distributions.

Surprising findings

• Under P^(2) with unknown sigma, no finite-length adaptive confidence interval exists for any n, so the rate cannot be improved without a known alpha_n lower bound.
• Within the class with alpha_n of order log(1/delta)/n, all optimal adaptive intervals have length of order sigma, so they do not shrink with n.

Limitations

• Requires a known lower bound alpha_n on the effective sample size to construct the interval.
• Numerical experiments are limited to a single stress-test mixture family and the constants were calibrated by hand.
• Extension to R^d is left open.

Experimental setup

Datasets: synthetic Gaussian mixture distributions constructed in the lower-bound proof

Benchmarks: synthetic mixture distributions with alpha in {1, 0.25, 0.1}

Metrics: empirical miscoverage mean interval length

Baselines: DLLO (Devroye et al.) Student-t interval

Builds on: median-of-means DLLO confidence intervals (Devroye et al.)

Closest papers by meaning

• All-Purpose Mean Estimation over R: Optimal Sub-Gaussianity with Outlier Robustness and Low Moments Performance (ICML 2025 · similarity 0.86)
• Asymptotically Log-Optimal Bayes-Assisted Confidence Sequences for Bounded Means (NeurIPS 2026 · similarity 0.86)
• A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers (NeurIPS 2024 · similarity 0.85)
• Relaxed Quantile Regression: Prediction Intervals for Asymmetric Noise (ICML 2024 · similarity 0.85)
• Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD (NeurIPS 2024 · similarity 0.85)
• Robust Statistical Estimators with Bounded Empirical Sensitivity (NeurIPS 2026 · similarity 0.84)