Towards Practical Mean Bounds for Small Samples

My Phan, Philip Thomas, Erik G. Learned-MillerICML 2021 · OpenReview

Introduction

In statistics, estimating the mean ($\mu$) of an unknown distribution from a small sample is a notoriously tricky problem. When dealing with large datasets, the Central Limit Theorem (CLT) allows practitioners to comfortably rely on the Student’s $t$-distribution. However, for small samples (e.g., $n < 30$), the CLT only applies if the underlying data is strictly Gaussian. If the data is skewed, relying on a $t$-test can significantly under-report the error, leading to statistical "guarantees" that fail in practice.

To mitigate this risk, researchers often turn to "distribution-free" bounds, such as Hoeffding’s inequality. While mathematically robust, these bounds are notoriously "loose"—producing intervals so wide they are often useless for practical decision-making. For over 50 years, the Anderson bound (1969) has been considered the gold standard for the tightest possible distribution-free bound for small samples.

This paper introduces a new family of distribution-free upper confidence bounds (UCBs) that finally breaks that ceiling. By assuming only that the distribution lies within a known interval $[a, b]$, the authors provide a method mathematically guaranteed to be tighter than or equal to both the Anderson bound and Hoeffding’s inequality.

Methodology

The authors propose a novel framework for constructing UCBs centered around an ordering function $T$. The approach breaks down into several key components:

1. Induced Mean and Stairstep CDFs: They utilize a "stairstep" cumulative distribution function (CDF), denoted as $G_{\mathbf{x}, \ell}$, to define an "induced mean." This function maps a given sample and a vector of probabilities to a specific mean value.

The stairstep CDF function $G_{x, \ell}(x)$ used to define the induced mean.

This discrete stairstep function acts as a conservative approximation of the true, unknown continuous distribution function $F(x)$, ensuring the resulting bounds remain valid regardless of the underlying data shape.

Relationship between the true continuous CDF $F(x)$ and the stairstep function $G_{x, \ell}(x)$.

2. Sample Ordering: They introduce a scalar-valued function $T(x)$ to create a total ordering of all possible samples within the sample space.

3. The Bound: The new UCB is defined as the $(1-\alpha)$-quantile of a specific random quantity ($b_{D,T}$), derived from the ordering function and the induced mean.

4. Computation: Unlike Hoeffding’s inequality, this new bound does not have a simple closed-form equation. Instead, the authors employ a Monte Carlo approach combined with Linear Programming. By sampling from a uniform distribution and solving a linear optimization problem for each sample, they can estimate the bound to high precision.

A major theoretical contribution of the paper is proving that if $T$ is chosen to be Anderson’s bound itself, the new method is guaranteed to be at least as tight as Anderson’s. Furthermore, if $T$ is chosen to be the $l_2$ norm of the sample, the bound becomes even tighter for many practical distributions.

Experimental Validation

As a theoretical statistics paper, the authors evaluate their method using synthetic distributions rather than static real-world datasets. This allows them to test the bounds across specific data shapes where the CLT is known to fail for small $n$. They tested on:

  • Beta(1, 5): A heavily right-skewed distribution.
  • Uniform(0, 1): A symmetric distribution.
  • Beta(5, 1): A heavily left-skewed distribution.

Key Results

  • Dominating the Classics: The paper proves their bound "dominates" Anderson’s and Hoeffding’s. In statistical terms, dominance means the bound is strictly tighter (or equal) for every possible sample, not just tighter on average.
  • Coverage Guarantee: The authors mathematically prove that their bound maintains the requested confidence level ($1-\alpha$) for any distribution on the interval $[a, b]$, regardless of sample size.
  • Failure of Student’s $t$: Simulations confirmed that for small samples of skewed data (like Beta(1, 5)), the Student’s $t$-test failed to maintain its coverage guarantee—the true mean fell outside the bound more often than the 5% allowed by $\alpha=0.05$. The new bound, however, remained strictly valid.
  • Tightness: In simulations ranging from $n=10$ to $n=50$, the new bound (specifically when using the $l_2$ norm for $T$) was significantly tighter than Anderson’s, Maurer & Pontil’s, and Hoeffding’s bounds.

Limitations and Future Work

While the theoretical guarantees are strong, the method does have practical limitations:

  • Computational Complexity: Because the method requires solving numerous linear programs via Monte Carlo simulation, it is computationally heavier than simple formulas like Hoeffding's. While it only takes a few seconds for $n=50$, it could become a bottleneck for very large sample sizes or real-time applications.
  • Support Knowledge: The bound strictly requires knowing the support interval $[a, b]$ of the data. If these absolute minimum and maximum bounds are unknown or estimated poorly, the mathematical guarantees may be compromised.
  • Choice of $T$: While the $l_2$ norm proved highly effective in simulations, the authors suggest there may be even better choices for the ordering function $T$ that could yield tighter bounds for specific, known classes of distributions.

Ultimately, this method provides a much-needed middle ground between the dangerous optimism of the $t$-test and the overly cautious pessimism of traditional distribution-free bounds, offering a practical new tool for small-sample statistics.

Summary updated

Abstract

Historically, to bound the mean for small sample sizes, practitioners have had to choose between using methods with unrealistic assumptions about the unknown distribution (e.g., Gaussianity) and me...
BibTeX
@inproceedings{phan2021towards,
  author = {My Phan and Philip Thomas and Erik G. Learned-Miller},
  title = {{Towards Practical Mean Bounds for Small Samples}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=9v4zKK_1lbx},
}
Figure