CS Paper Radar

Anytime Valid Confidence Bands for Distribution Functions

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

cs.LG stat.ML ·submitted 2026-10-26 18:53 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Online Inference in Distributional Temporal-Difference Learning

cs.LG stat.ML ·2026-08-14 ·Yang Peng, Liangyu Zhang
theory similarity 0.58
Abstract · There is a technical error in "Step 3" of the proof of Theorem 4, section 4

We study online statistical inference for functionals of the return distribution under a fixed policy. The return distribution is estimated by nonparametric distributional temporal-difference learning from a single Markov trajectory. For the Polyak--Ruppert averaged estimator, we prove that its root-$T$ error converges weakly to a centered Gaussian random element in Cramér space. We also prove that, conditionally on the observed trajectory, the root-$T$ difference between the bootstrap and original averages converges weakly to the same Gaussian limit. These results justify bootstrap inference for smooth statistical functionals, including variance, CVaR, expected shortfall, and expectiles. For nonsmooth statistical functionals, we develop a local asymptotic theory for the estimated return CDF over $T^{-1/2}$-neighborhoods of finitely many thresholds, together with its bootstrap analogue. This theory allows us to conduct inference for nonsmooth statistical functionals characterized by CDF equations, including return quantiles.

0.34

Distribution-free inference on the number of changepoints

cs.LG stat.MLstat.ME ·2026-09-08 ·Rohan Hore, Aaditya Ramdas
theory similarity 0.55
Abstract · 34 pages, 3 figures, 1 table

Suppose we are given an ordered sequence of independent data whose distribution changes $K$ times at unknown locations, for some unknown $K \geq 0$. In this paper, we study the problem of performing distribution-free inference on $K$. First, we show an impossibility result: any distribution-free upper confidence bound on $K$ must be trivial and uninformative. Then, using conformal $p$-values, and under only the assumption that the data segments induced by the changepoints are exchangeable (within themselves) and mutually independent, we construct a finite-sample valid lower confidence bound on $K$, which we call the Conformal LOwer bound on Changepoint Count (CLOCC). We show that CLOCC is the only feasible way to provide a lower bound on $K$ under the stated assumptions, a property we refer to as its universality. We provide practical guidelines for choosing score functions that yield efficient and tight lower bounds. We evaluate CLOCC in several synthetic and real-data experiments, where it provides informative lower bounds on $K$, demonstrating its practical applicability.

0.39

Distributionally Robust Search: The Power of Information and the Limits of Moments

cs.DS cs.DM ·2026-11-03 ·Nicole Megow, Cliff Stein, Jose Verschae
theory similarity 0.55
Abstract · 43 pages, 5 figures

We study binary search for a target drawn from a distribution on $n$ ordered elements. The cost is the expected number of comparison queries. In our distributionally robust framework, the algorithm knows only an uncertainty set containing the distribution and minimizes its worst-case approximation ratio against an optimal strategy that knows the distribution. Collections of uncertainty sets capture different forms of information: quantiles, moments, general linear measurements, or approximate CDFs. This framework quantifies how much and what form of information is needed for near-optimal search. Our main result separates moments from general linear measurements. Although $n-1$ moments determine the distribution exactly, for every constant $δ\in(0,1)$, the first $n^{1-δ}$ exact moments can be as uninformative for search as no information: the worst-case approximation ratio remains $Ω(\log n)$. In contrast, for every constant $\varepsilon\in(0,1)$, $O(n^\varepsilon\log^4 n)$ suitably chosen linear measurements suffice for an $O(1/\varepsilon)$-approximation. The limitation lies in the measurements chosen, rather than linearity itself. Using LP duality and polynomial bounds of Rakhmanov and Bernstein, we construct distributions with identical moments and mass concentrated at different positions. For the upper bound, we combine dyadic sketches and Johnson--Lindenstrauss embeddings with a truncated median-search algorithm that converts uniform CDF approximation into search guarantees. Measuring information in bits, we prove a lower bound of $Ω(1/\varepsilon)$ on the approximation ratio for summaries of any form using at most $\frac12 n^\varepsilon\log n$ bits, for every sufficiently small constant $\varepsilon>0$. Quantiles match this within constant factors. For Kolmogorov balls of radius $n^{-\varepsilon}$ the optimal approximation ratio is $Θ(1/\varepsilon)$.

0.19

Limits of Confidence in Diffusion

cs.AI ·2026-09-17 ·Russ Webb, Amitis Shidani, Alice Bizeul, Dan Busbridge
similarity 0.53
Abstract

Discrete diffusion, including remasking and uniform-state samplers, generate a sequence by writing multiple token positions per step, drawing each from a per-position distribution and choosing which positions to write from those same distributions. For domains of general interest (pixels, phonemes, or words) there are inherent dependencies between tokens. We show that a step matches the training distribution only when the positions it writes are conditionally independent given the tokens already fixed, that no product of per-position distributions can match a dependent group, and that per-position distributions do not determine whether a group is dependent: two joint distributions can have identical per-position marginals while differing in which combinations of values occur. On ScanAndAdd, a synthetic task whose joint distribution is available in closed form, we verify that every group of two or more undetermined positions a confidence ranking writes is dependent, and measure the generated distribution to be $29\times$ the sampling-noise floor total variation while per-sample metrics are $1.0$.

0.52

Universality and Generalization of Causal Transformers Across Context Lengths

cs.LG math.OCstat.ML ·2026-09-28 ·Takashi Furuya, Maarten V. de Hoop, Gabriel Peyré
similarity 0.53
Abstract

Long contexts are central to modern transformer systems, but most expressivity results choose a different network for each fixed sequence length. We study whether one masked transformer can approximate causal token-to-token maps uniformly over sequences of arbitrary length sampling a fixed normalized horizon. To relate sampling resolutions, we model tokens by $α$-Hölder sequences or, more generally, a common modulus of continuity. Our notion of continuity across resolutions characterizes the causal families admitting uniform approximation on these compact input classes by a single transformer with length-independent parameters. The result extends to the infinite-length mean-field limit, where tokens form continuous curves and masked attention becomes a causal time integral. For bounded regression with target maps satisfying a $β$-smooth stability condition defined using regular test functions, quantitative approximation yields a generalization bound: exact empirical risk minimization over suitably sized bounded-weight transformers gives root mean-square prediction error $O((\log\log N/\log N)^{β/(d+2)})$ from $N$ iid labeled sequences. The bound holds at fixed confidence on the same sampling distribution, with $d$ the token dimension and no maximum-length factor. Finally, experiments on physical time series support the Hölder-regular token model at observed scales, with dataset-dependent fitted exponents, whereas text input embeddings provide a contrasting case. Native and dense sampling, shuffled controls, and refinement checks delimit this empirical regularity regime.

0.24

Conformal Prediction Regions for Continuous-Time Trajectories under Random Sampling

eess.SY ·2026-08-30 ·Joaquin Alvarez, Matteo Sesia, Jyotirmoy V. Deshmukh, Lars Lindemann
similarity 0.52
Abstract

Uncertainty quantification for continuous-time trajectories is a prerequisite in many safety-critical engineering domains. However, a major challenge in data-driven uncertainty quantification is that calibration trajectories are sampled only at discrete, often sparse, and random intervals. Standard conformal prediction methods typically fail to provide guarantees in between sampling times. In this work, we introduce a new technique to obtain valid conformal prediction regions for continuous-time trajectories that are sampled at discrete and possibly random times. To accomplish this goal, we make three contributions: (1) we provide an algorithm that leverages regularity properties of the underlying trajectories to obtain valid prediction regions in between samples, (2) we provide methods that estimate valid bounds on the aforementioned regularity properties from an additional high-frequency calibration dataset, and (3) we introduce and compare several algorithms to deal with random sampling times. Finally, we present experiments where we validate that our methods achieve valid coverage across the entire continuous trajectory.

0.26

Coverage Cliffs in Off-Policy Quantile Certification

cs.LG ·2026-10-15 ·Pauline Bourigault, Emmanuelle Bourigault
hot direction similarity 0.52
Abstract

We study when logged contextual-bandit data can certify an upper tail quantile for a policy selected from the same sample. We construct a PAC-Bayes Bernstein lower-confidence envelope for the target cumulative distribution function (CDF), simultaneous over a predeclared threshold grid and all data-dependent posteriors. The resulting procedure, TailCert, uses the envelope's first crossing of level p to return an atom-safe upper confidence bound on the selected posterior's pooled p-quantile (or inconclusive). It can also be used to select a policy under a certified tail constraint. The concentration ingredients are standard; the main theoretical contribution is a matched finite-class certification boundary comparing full logs with their joint weighted CDF indicators at a fixed threshold. On an explicit rare-action class, the required sample size grows linearly with the overlap factor W, logarithmically with policy-search and confidence complexity, and quadratically with the inverse CDF safety margin; the upper and lower bounds agree up to constants in the stated regime. On this class, the CDF reduction hides which actions exceeded the budget; retaining action counts restores the full-log rate. Simulations verify the predicted search-complexity shift, winner's-curse failure of naive reuse, and the power cost of splitting.

0.27

MiNCE: Nonparametric, Strongly Consistent Confidence Envelopes for Band-Limited Functions and their Smoothed Spectra

cs.LG math.STeess.SPstat.ME+1 ·2026-09-08 ·Balázs Csanád Csáji, Bálint Horváth
similarity 0.52
Abstract

Minimum-norm confidence envelope strategies offer a nonparametric approach to constructing nonasymptotic, simultaneous confidence regions for band-limited functions, exploiting the theory of Reproducing Kernel Hilbert Spaces (RKHS). While the finite-sample coverage guarantees of these envelopes have been established, their consistency has not been analyzed so far. In this paper, we study this construction, here termed the Minimum-Norm Confidence Envelope (MiNCE) framework, and establish the strong uniform consistency of the resulting bands, both for noise-free and noisy observation models, under mild assumptions on the measurement noises. We further extend this formulation to the frequency domain, deriving nonasymptotic, simultaneous, strongly uniformly consistent confidence bands for the smoothed spectra. Numerical experiments in nonparametric regression and spectral estimation empirically confirm our theoretical results, illustrating the contraction of the confidence envelopes toward the target function as the sample size increases.

0.29