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.
- 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.
- 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.
- 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).
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.
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