PaperlayerView exact revision on arXiv

Source-linked AI summary

Anytime Valid Confidence Bands for Distribution Functions

Bror Hultberg, Dave Zachariah, Antônio H. Ribeiro

arXiv:2610.36149v1stat.MLcs.LG

TL;DR

The paper addresses how to construct confidence bands for distribution functions across all points and times when observations may depend arbitrarily on the past. It uses a data-driven refinement framework to build bands for running averages of conditional distributions, with threshold costs tied to search-tree depth. The framework also covers importance-weighted, right-censored, and multivariate CDFs.

  • Problem

    The challenge is obtaining confidence bands uniformly over time and the index for a running average of conditional means without assumptions on dependence.

    Source: §2 · p. 2

  • Method

    A single supermartingale on a data-driven refinement constructs simultaneous bands, with each probe paying for refinements of its own cell.

    Source: §4.1 · p. 3, §8 · p. 8

  • Results

    The resulting bands are valid over all times and points under arbitrary dependence, and for thresholds the uniformity cost is the probe's binary-search-tree depth.

    Source: §8 · p. 8

  • Takeaways & Limitations

    The framework also covers importance-weighted, right-censored, and multivariate distribution functions, and its bands are invariant to fixed strictly increasing transformations.

    Source: §8 · p. 8

    The width depends on observation order; under exchangeable data its rate p log t/t is slower than the i.i.d. iterated-logarithm rate, and whether this gap is necessary remains open.

    Source: §8 · p. 8

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper seeks confidence bands for the running average of conditional CDFs, uniformly over time and all thresholds, when observations may depend arbitrarily on the past. It develops a broader framework for indexed functions and applies it to several distribution-function targets.

1 INTRODUCTION

  • The target is the time-averaged conditional CDF: individual conditional distributions may be difficult to estimate, while the average changes as each new conditional distribution enters.In the i.i.d. case, the average reduces to the fixed population CDF.Source: §1 · p. 1
  • The paper seeks confidence bands for this average that are simultaneously valid over every threshold and every time.Source: §1 · p. 1
  • For an arbitrary indexed family of observable functions, the framework yields bands whose width combines cell discretization error with the code length of refinements, rather than a cost growing with the index set.Source: §1 · pp. 1–2
  • For real-valued thresholds, the bands cover the running average of conditional CDFs without requiring i.i.d. data, with logarithmic-in-time uniformity cost for i.i.d. continuous data.Source: §1 · p. 2
  • The framework also yields bounds for importance-weighted CDFs with possibly unbounded weights, right-censored CDFs with a known censoring law, and multivariate CDFs.Source: §1 · p. 2

2 PROBLEM FORMULATION

The problem is to infer the running average of conditional means from a data stream using bands valid uniformly over time and the index. The challenge is achieving index-wise uniformity without assumptions on dependence.

2 PROBLEM FORMULATION

  • The target is the running empirical average from the observed stream, with bands required to cover the time-varying function uniformly over its index and time.Source: §2 · p. 2
  • Time-uniform martingale concentration can give bands at each fixed index, but simultaneous uniformity over indices without dependence assumptions is the central challenge.Source: §2 · p. 2
  • Under arbitrary dependence, uniform convergence can fail even asymptotically; for threshold functions, the empirical CDF may not converge uniformly to the running-average conditional CDF.Source: §2 · p. 2

3 RELATED WORK

Prior work develops anytime-valid inference, CDF bands for fixed or time-varying targets, and tools for understanding uniform convergence under dependence. The paper builds on time-varying CDF bands while replacing fixed discretization with a data-driven construction.

3 RELATED WORK

  • Anytime-valid inference uses nonnegative supermartingales, with later work providing general tools for confidence sequences and related procedures.Source: §3 · p. 2
  • For i.i.d. data, classical CDF bands are fixed-time, while later methods provide time-uniform bands over quantile level or a monotone process's argument.Source: §3 · p. 2
  • Off-policy CDF bands have been studied at fixed times, with a later time-uniform analogue [Chandak et al., 2021; Huang et al., 2021; Waudby-Smith et al., 2024].Source: §3 · p. 2
  • Mineiro and Howard (2023) give time- and value-uniform bands for the temporal-average CDF using fixed dyadic discretization; this paper instead uses data-driven refinement and obtains invariance to fixed strictly increasing transformations.Source: §3 · p. 2
  • Under dependent data, sequential complexity governs uniform convergence; threshold functions have infinite Littlestone dimension, so a uniform law need not hold.Source: §3 · pp. 2–3

4 RESULTS FOR CDF

The paper constructs CDF bands by recursively refining probe intervals, with validity across time and probes and widths governed by local split depth. It also develops a variance-adaptive version of the bands.

4.1 Confidence bands for CDF

  • Each observation can split the interval containing a probe, and the resulting tree makes the probe's local split count its binary-search depth.Only observations strictly inside the current interval refine it; observations outside leave it unchanged.Source: §4 · p. 3, §4.1 · pp. 3–4
  • The CDF band is valid uniformly over time and probe values for the time-averaged conditional CDF.Theorem 4.2 gives this validity guarantee.Source: §4.1 · p. 3
  • With uniformly random observation ranks, the local split count is O(log t) almost surely, and the band shrinks under the stated assumptions.For example, the rank condition holds for i.i.d. continuous observations or exchangeable observations with almost surely continuous de Finetti mixands.Source: §4.1 · p. 4
  • A fixed λ leaves a non-vanishing width term, so the construction grids λ and allocates miscoverage across the resulting bands.The grid allows adaptation to probe-specific local complexity without fixing λ in advance.Source: §4.1 · p. 4

4.2 Variance adaptivity

  • The variance-adaptive construction evaluates the Bernoulli MGF exactly, retaining dependence on the unknown parameter through its average without requiring that parameter to be known.The resulting band is valid uniformly over time and probe values for the time-averaged conditional CDF.Source: §4.2 · pp. 4–5

5 REFINEMENT AND CHARGE SCHEMES

The framework represents an indexed family of functions through recursively refined cells and assigns charges along their paths. This yields a nonnegative supermartingale and, in turn, confidence bands valid simultaneously over time and probes.

5 REFINEMENT AND CHARGE SCHEMES

  • For a bounded family indexed by an arbitrary probe set, the framework constructs bands using a refinement scheme and charges assigned to its cells.The observable functions may vary over time and adapt to the process history.Source: §5 · p. 5
  • A refinement scheme recursively partitions probes into cells, with each probe tracing a path and the partition fixed before the next observation.A distinguished symbol records steps when a cell does not divide.Source: §5 · p. 5
  • Envelopes bound deviations within cells, while a charge scheme assigns edge weights whose products give each path's weight.The covering cost for an infinite probe set is paid one node at a time.Source: §5 · pp. 5–6
  • The charge condition makes the aggregate across refinement paths a nonnegative supermartingale, yielding a confidence band valid simultaneously over time and probes.The master band applies to any charge scheme at λ > 0 with probability at least 1−α.Source: §5 · p. 6
  • The general result turns function inference into choosing a suitable refinement scheme and charge scheme.The confidence bounds are obtained by applying the master band to deviations and their sign reversals.Source: §5 · p. 6

6 OTHER DISTRIBUTION FUNCTIONS

The framework extends anytime-valid bands from ordinary CDFs to counterfactual, right-censored, and multivariate distribution functions. These applications retain validity uniformly over time and values under their stated conditions.

6 OTHER DISTRIBUTION FUNCTIONS

  • The applications illustrate the framework’s extension from its master result to families of distribution functions beyond the ordinary CDF.The section introduces importance-weighted counterfactual CDFs, right-censored survival functions, and multivariate CDFs.Source: §6 · p. 6, §6.1 · p. 6, §6.2 · p. 7

6.1 Counterfactual CDF

  • Importance weighting yields bands for counterfactual CDFs uniformly over time and values, without an upper bound on the weights.The weights are nonnegative and have conditional mean one.Source: §6.1 · pp. 6–7

6.2 Right-censored data

  • For right-censored data, two-sided bands cover the running average of conditional survival functions when censoring is conditionally independent, its law is known, and the censoring survival probability at the horizon is positive.The upper bound uses inverse event-observation probabilities; the lower bound weights subjects still observed at each threshold by inverse probabilities of remaining observed that long.Source: §6.2 · p. 7

6.3 Multivariate CDF

  • For multivariate CDFs, the bands hold simultaneously over time and all probes, with each coordinate cut costing ln 2 and no assumption on dependence between observations.The bands are invariant under coordinatewise strictly increasing transformations.Source: §6.3 · p. 7

7 NUMERICAL EXPERIMENTS

The experiments illustrate the bands on ordinary, counterfactual, and right-censored distributions, including settings where data distributions change over time. For transformed i.i.d. continuous data, the proposed band is invariant at a given quantile level, while the comparator’s band changes.

Numerical experiment setup

  • The experiments compare bands tightened by a closure step with Mineiro and Howard (2023), using the authors’ reference implementation; each panel shows one run except Figure 2(c), which shows two.The closure is applied only to the proposed bands and leaves the comparator’s bands essentially unchanged.Source: §7 · p. 7

Importance weights and censoring

  • Figure 3 illustrates bands for an importance-weighted counterfactual CDF and a right-censored survival function, including a censored-data comparison that ignores censoring.The survival-function example has 40% censoring; the comparison is shown at t = 10^4.Source: §7 · p. 8, Figure 3 · p. 8

CDF

  • For i.i.d. continuous samples, the proposed band at a quantile level is unchanged by strictly increasing transformations, while the Mineiro–Howard band changes with distribution scale or concentration.Figure 2 varies Beta concentration and uniform scale using the same underlying uniforms within each panel.Source: §7 · pp. 7–8, Figure 2 · p. 8

8 DISCUSSION

The paper presents a framework for confidence bands valid over all times and points without assumptions on dependence between observations. Its width guarantee is instance-dependent, and the authors identify open extensions and describe their use of generative AI tools.

8 DISCUSSION

  • A single supermartingale on a data-driven refinement gives uniform validity, with each probe paying for refinements of its own cell.For thresholds, this cost is the search depth of the probe in the observations’ binary search tree.Source: §8 · p. 8
  • The width guarantee depends on observation order: trending streams can inflate the cost, and under exchangeable data the rate p log t/t is slower than the i.i.d. iterated-logarithm rate.Whether the gap is necessary for validity under arbitrary dependence remains open.Source: §8 · p. 8
  • The authors identify extensions to other censoring forms and estimation losses as possibilities, while noting that effective refinements in those settings require further study.They also flag connections between sequential refinement, coding, and information theory for future exploration.Source: §8 · p. 8

AI use statement

  • Generative AI tools assisted theory development, experimental implementation, code and figure generation, and editing; authors reviewed the work and checked proofs and code.The authors state they did not use these tools to interpret results.Source: AI use statement · p. 9

A PROOF ROADMAP

The proof roadmap organizes results around a shared master band and two charge templates. The generic charge schemes rely on refinements that make probe functions constant within cells and control their deviations.

A PROOF ROADMAP

  • The proof roadmap shows which results each main-text result uses, with the master band and two charge templates as shared machinery.Template A applies to bounded families and Template B to nonnegative families; later panels build from these templates.Source: Figure 4 · p. 12, A PROOF ROADMAP · p. 12

B MISSING PROOFS §5

  • The master-supermartingale proof bounds conditional expectations by splitting address levels and using nonnegative terms, yielding a simultaneous band through Ville’s inequality.The proof handles empty cells separately; for nonempty cells, the inner expectation is bounded by one.Source: B MISSING PROOFS §5 · p. 13

C GENERIC CHARGE SCHEMES

  • A homogeneous refinement makes each probe function constant on every refined cell, separating observed from unobserved deviation.The coarsest such refinement divides cells into level sets; finer refinements are also permitted.Source: C GENERIC CHARGE SCHEMES · p. 14
  • For a [0, 1]-valued variable with conditional mean at most p, its conditional exponential moment is bounded by e^Λp(λ), where Λp(λ) is increasing and concave in p.The associated Bernoulli cumulant K(λ, p) lies between zero and λ^2/8.Source: C GENERIC CHARGE SCHEMES · p. 14

C.1 Template A for bounded families

This section develops anytime confidence-band templates for bounded, nonhomogeneous, and nonnegative indexed families, with guarantees accounting for path code length and, without homogeneity, within-cell oscillation. It also describes a half-open refinement for threshold families that supports homogeneous weighted thresholds under stated conditions.

C.1 Template A for bounded families

  • For bounded homogeneous families, Template A gives confidence bands holding simultaneously for every time and index, in Hoeffding and exact forms.The construction counts observations that divide an index’s cell as 0; each path also incurs the code length of its split sequence.Source: §C.1 · pp. 15–16
  • Template A permits adaptive split weights, whose path cost is the code length of the index’s moves through the refinement.Sequential probability assignments can favor frequently observed moves; the paper gives Krichevsky–Trofimov weights as an example.Source: §C.1 · p. 16

C.2 Template A without homogeneity

  • Template A′ removes homogeneity, allowing cells to be split at measurable or deterministic points, at the cost of accounting for within-cell variation.The construction bounds each child using its maximum and compares the observation with its minimum over the parent cell.Source: §C.2 · p. 16
  • Without homogeneity, two-sided band width comprises average cell oscillation plus a path code-length term; for thresholds, oscillation is the fraction of dividing steps.Smaller cells reduce oscillation, while fewer divisions reduce code length.Source: §C.2 · p. 18

C.3 Template B for nonnegative families

  • For nonnegative families that may be unbounded, Template B uses a one-step betting argument to construct anytime bands without requiring homogeneity.It requires measurable, finite child upper bounds and uses a predictable centering and a nonnegative floor.Source: §C.3 · p. 19
  • For homogeneous nonnegative families, Template B yields a simpler band by choosing a floor at nond division steps and an admissible floor at divisions.Setting the floor to 0 at divisions recovers Template A’s adjusted observations.Source: §C.3 · p. 20

D THE HALF-OPEN THRESHOLD REFINEMENT

  • The next section begins by interpreting the half-open threshold construction as a refinement scheme and directs readers to Figure 1 for intuition.Source: D THE HALF-OPEN THRESHOLD REFINEMENT · p. 21
  • Cells are half-open intervals between consecutive distinct observations, and a cell splits exactly when the new observation falls in its interior.The split creates [l, Xs) and [Xs, r).Source: D THE HALF-OPEN THRESHOLD REFINEMENT · p. 21
  • Nt(v) counts comparisons in a binary search tree of distinct observed values, inserted by first appearance, searching right when a node x satisfies x ≤ v.Repeated values and observations outside v’s current cell do not add comparisons.Source: D THE HALF-OPEN THRESHOLD REFINEMENT · p. 21
  • After each split, the new observation lies in no resulting cell, while every v remains in its half-open cell.These endpoint properties let threshold indicators be read from cell endpoints.Source: D THE HALF-OPEN THRESHOLD REFINEMENT · p. 21
  • For nonnegative, measurable weights with finite conditional expectation, both weighted threshold families are homogeneous on each cell and its split children.On an unsplit cell the indicators are constant; on split children the weighted indicators take values 0 or Ws as specified by the left or right side.Source: D THE HALF-OPEN THRESHOLD REFINEMENT · p. 21
  • The weighted cell minima are Ws1{Xs ≤ l} for f and Ws1{Xs ≥ r} for g, and both families satisfy Assumption C.2.Their conditional means are F_s^W and H_s^W.Source: D THE HALF-OPEN THRESHOLD REFINEMENT · p. 21
  • Because F_s^W is nondecreasing and H_s^W is nonincreasing, their cell infima occur at l and at the left limit at r, respectively; on unbounded cells the minima and infima are zero.The right-endpoint limit for H_s^W follows by dominated convergence with dominating variable Ws.Source: D THE HALF-OPEN THRESHOLD REFINEMENT · p. 21

E MISSING PROOFS §4

The proofs establish confidence bands for the time-averaged conditional CDF that are valid uniformly over time and thresholds, with width reflecting refinement costs and, for thresholds, binary-search behavior. They also establish importance-weighted bands whose tightness can depend on the choice of centering.

E MISSING PROOFS §4

  • Theorem 4.9’s band is valid simultaneously for all times and thresholds for the time-averaged conditional CDF.The proof constructs lower and upper bounds using threshold indicators and combines their coverage.Source: E MISSING PROOFS §4 · p. 23
  • The band adapts to the spread of the averaged distribution at a threshold, which is small in its tails, without estimating that spread.The proof distinguishes this spread from an average of conditional variances; under nonstationarity, the gap can be large.Source: E MISSING PROOFS §4 · p. 24

F IMPORTANCE-WEIGHTED CDF

  • Importance-weighted bands are tighter when their centering better predicts the observed indicator contribution.Valid centerings are predictable, lie in [0, 1], and are constant on the current cells; the section describes discounted running means and prior guesses as options.Source: F IMPORTANCE-WEIGHTED CDF · pp. 25–26
  • With conditional mean weights normalized to one, Theorem F.3 gives importance-weighted CDF bands valid simultaneously over time and thresholds.The theorem allows centerings and split weights in constructing the bounds.Source: F IMPORTANCE-WEIGHTED CDF · p. 26

G RIGHT-CENSORED DATA

For right-censored data, the paper constructs time- and threshold-uniform bands for the time-averaged survival and event-time CDFs using weighted probes on a refinement of the threshold space. The results allow dependent lifetimes across subjects and can be extended beyond the usual positivity condition, with capping effects depending on the band construction.

Assumptions and positivity

  • The censored-data construction assumes conditional independence of lifetime and censoring times, with positive censoring survival through τ; Proposition G.8 removes the positivity condition.Without positivity, the lower bound applies at thresholds with at least one subject who has positive probability of remaining uncensored.Source: G RIGHT-CENSORED DATA · pp. 28, 30

Bands for censored CDFs and survival

  • Theorems G.3 and G.5 provide bands simultaneously over all times and thresholds for the event-time CDF and survival function, respectively.The event probe uses inverse-censoring weighted event indicators, while the at-risk probe estimates survival directly.Source: G RIGHT-CENSORED DATA · pp. 28–29

Combining the bounds

  • Theorem G.6 combines the event-side and survival-side bounds to hold simultaneously with probability at least 1 − α.It applies Theorems G.3 and G.5 at level α/2.Source: G RIGHT-CENSORED DATA · p. 30

Bands without positivity

  • The bands without positivity cover the time-averaged survival function for all times and thresholds where at least one subject remains potentially observable.The stated domain is v > 0 with n_t(v) ≥ 1.Source: G RIGHT-CENSORED DATA · p. 30

Capped weights

  • Each choice of c gives a supermartingale band holding with probability at least 1 − α, so c must be fixed before seeing data; for Theorem G.3 and Proposition G.8, capping lowers lower bounds and raises upper bounds.Capping tightens both bounds of Corollary G.7.Source: G RIGHT-CENSORED DATA · pp. 31–32

H MULTIVARIATE CDF

The multivariate construction refines the probe space into boxes so each observation makes the joint-CDF indicator constant on the resulting cells. The experiments describe how closure is used and compare the bands across ordinary and importance-weighted CDF settings.

H MULTIVARIATE CDF

  • In d dimensions, a box is cut only when the observation’s upper orthant intersects but does not contain it, and only along coordinates where the observation lies strictly inside.If m coordinates are cut, exactly 2^m pieces are nonempty; the resulting refinement is homogeneous for the joint-CDF indicator and its complement.Source: H MULTIVARIATE CDF · pp. 33–34

I DETAILS OF THE NUMERICAL EXPERIMENTS

  • The experiments use α = 0.05, combine bands over a grid of λ values, and apply monotone and cross-time closure, which matters when the threshold band is not monotone.The threshold bands’ width can jump when a probe’s cell splits.Source: I DETAILS OF THE NUMERICAL EXPERIMENTS · p. 35

I.1 CDF Bands

  • For continuous i.i.d. data, the proposed band at a quantile level depends on relative order rather than the distribution, while MH band width grows with b and varies with xmax in the reported comparisons.The paper attributes the MH changes to paying for dyadic-grid points, including deeper levels and points farther from zero.Source: §I.1 · pp. 35–36

I.2 Importance-Weighted CDF

  • In the importance-weighted experiment, the weighted target is the running average of the conditional CDFs for the weight-4 urn, whereas the factual running-average CDF mixes both urns.The two nonstationary urns reinforce their own histories and can concentrate at opposite ends of [0, 1].Source: §I.2 · p. 36

I.3 Censored Data

The censored-data experiment models lifetimes whose group composition depends on previously observed events, so the lifetimes are not i.i.d. It uses independent exponential censoring and distinguishes the target survival function from the survival function of the observed censored times.

Group-specific lifetimes

  • The high-risk group has exponential lifetimes with mean 0.7 and median 0.49, while the low-risk group has Weibull lifetimes with median 1.57.The high-risk group has the larger hazard on (0, τ).Source: §I.3 · p. 36

Adaptive group composition

  • The high-risk share is 0.2 + 0.6q_s, where q_s is the recent fraction of observed events by time 1, making the lifetimes non-i.i.d.The share uses the last 100 subjects, or all earlier subjects when s ≤ 100.Source: §I.3 · p. 36

Censoring and target

  • Independent Exp(0.5) censoring yields 40% censored lifetimes, and the comparison band based on observed times targets their survival function rather than S_t.The experiment sets τ = 3, for which K_s(τ) = e^-1.5 ≈ 0.22.Source: §I.3 · p. 36

Related papers

Loading 2610.36149v1…