Anytime Valid Confidence Bands for Distribution Functions

Bror Hultberg, Dave Zachariah, Antônio H. RibeiroarXiv 2026 · arXiv

TL;DR

This paper introduces a new framework for constructing confidence bands for cumulative distribution functions (CDFs) that remain valid at any point in time and across all values in the domain. By using a data-driven partitioning scheme—essentially treating observations as nodes in a binary search tree—the authors provide tight, transformation-invariant bounds that work even when data points are arbitrarily dependent on their own history.

What Problem Does This Paper Address?

In many modern applications like online decision-making, adaptive experiments, or sequential monitoring, we deal with a stream of data where observations are not independent and identically distributed (i.i.d.). The distribution of a new data point might depend on everything that happened before it.

Standard statistical tools for estimating a CDF usually assume i.i.d. data and a fixed sample size. If you try to monitor a CDF "anytime" (checking the results as each new data point arrives), you run into the "multiple testing" problem: the more you look, the more likely you are to see a false pattern. Furthermore, if the distribution is changing over time, you can't estimate the distribution of a single future point; instead, you must target the time-averaged conditional distribution.

The challenge is to create confidence bands that are simultaneously valid over all possible values ($v$) and all possible times ($t$), without making restrictive assumptions about how the data is generated.

Methods

The authors propose a general "Refinement and Charge" framework based on martingale theory. The core idea is to recursively partition the space of observations as new data arrives.

  1. Data-Driven Refinement: Instead of using a fixed grid, the method uses the observations themselves to split the domain into smaller cells. In one dimension, this process is identical to building a binary search tree. Each new observation $X_s$ splits the interval it falls into.
  2. Charge Schemes: To maintain anytime validity, the authors assign a "charge" (a weight) to each cell in the partition. These charges are designed so that the sum of weighted exponential deviations forms a nonnegative supermartingale.
  3. Ville’s Inequality: By applying Ville’s inequality to this supermartingale, they guarantee that the probability of the true time-averaged CDF ever leaving the confidence band is bounded by a pre-specified level $\alpha$ (e.g., 0.05).
Example of the data-driven partition building a tree structure. Each new observation splits an existing interval into two.

The framework is highly flexible and was extended to handle:

  • Counterfactual CDFs: Using importance weighting for off-policy evaluation.
  • Right-Censored Data: Common in survival analysis where some events haven't happened yet.
  • Multivariate CDFs: Using "box cuts" to partition higher-dimensional spaces.

Datasets

The paper evaluates the method using several synthetic data streams designed to test specific edge cases:

  • i.i.d. Beta and Uniform distributions: To compare against classical baselines.
  • Non-stationary Pólya Urns: A process where the distribution explicitly changes based on past observations, creating heavy dependence.
  • Simulated Survival Data: High-risk and low-risk groups with random censoring to test the right-censored framework.

Key Insights and Ideas

  • Search Depth as Complexity: A brilliant "aha moment" in the paper is that the width of the confidence band for a specific value $v$ is determined by the search depth of $v$ in the binary search tree of observations. If many observations are near $v$, the tree is deep, the resolution is high, and the band is tight.
  • Transformation Invariance: Because the cells are defined by the relative order of observations rather than their absolute values, the 1D bands are invariant under any strictly increasing transformation (like taking the log of the data). You don't need to know the transformation in advance.
  • Adaptive Resolution: Unlike prior methods (like Mineiro & Howard, 2023) that use fixed dyadic grids, this data-driven approach automatically puts more "resolution" where the data actually is. If your data is concentrated between 0.1 and 0.2, the bands will naturally become tighter in that specific region.

Key Results

The authors compared their bands against the state-of-the-art "MH" bands (Mineiro & Howard, 2023).

  • Instance Optimality: In scenarios where data is highly concentrated (e.g., a Beta distribution with high parameters), the new bands are significantly tighter because they adapt to the data's location, whereas fixed-grid methods waste "error budget" on empty regions.
  • Convergence Rates: For i.i.d. continuous data, the bands shrink at a rate of $O(\sqrt{\log t / t})$, which is nearly optimal for anytime-valid sequences.
  • Robustness to Non-stationarity: In the Pólya urn experiments, the bands successfully tracked the time-varying average distribution while maintaining coverage.
Comparison of band widths. Panel (a) shows how the new method (blue) maintains a consistent width across different data concentrations, while the fixed-grid baseline (orange) fluctuates.

Limitations and Future Work

  • Adversarial Sensitivity: The width guarantee is "instance-dependent." An adversary who knows your target $v$ could theoretically place observations in a way that maximizes the search depth $N_t(v)$, making the bands wider (though still valid).
  • Rate Gap: Under arbitrary dependence, the $\sqrt{\log t / t}$ rate is slightly slower than the iterated-logarithm rate ($\sqrt{\log \log t / t}$) achievable in strictly i.i.d. settings. It remains an open question if this gap is fundamental for dependent data.
  • Complex Censoring: While the paper covers right-censoring, the authors suggest that extending the framework to interval censoring or more complex missing data patterns is a promising next step.

Summary updated

Abstract

Nonparametric inference often requires characterizing an unknown function, such as a cumulative distribution function (CDF), across its entire domain rather than a specific point. We develop confidence bands for distribution functions of a data stream that are valid simultaneously over all times and all points, even when each observation may depend arbitrarily on the past. We begin by deriving such bands for the time-averaged conditional CDF and show how their widths are determined by the depth of a binary search tree. We then show that this result is an instance of a framework through which one can construct valid confidence bands uniformly over time and over an arbitrary index set for any indexed family of time-averaged distribution functions. We illustrate the framework on importance-weighted and right-censored CDFs, as well as multivariate CDFs.
BibTeX
@misc{hultberg2026anytime,
  author = {Bror Hultberg and Dave Zachariah and Antônio H. Ribeiro},
  title = {{Anytime Valid Confidence Bands for Distribution Functions}},
  year = {2026},
  eprint = {2610.36149},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.36149},
}
Figure