CS Paper Radar

Conformal Prediction at Performative Equilibrium: The Price of Performativity

Ahmed Mahrous, Roberto Di Pietro

cs.LG math.ST ·submitted 2026-11-03 17:58 UTC · v1
theoryhot direction

Abstract

Conformal prediction gives finite-sample coverage when calibration and test points are exchangeable, but exchangeability can fail when deployment changes the data distribution. We study conformal prediction in performative settings, where the deployed predictor affects the data distribution, and seek prediction sets valid at performative equilibrium: coverage must hold under $D(f^\star)$ for a performatively stable predictor $f^\star$. Under total-variation $L$-sensitivity of the distribution map, we prove a phase transition at $L=1$. If $L \ge 1$, no finite-sample procedure can uniformly guarantee both equilibrium-valid coverage and nontrivial prediction sets. If $L<1$, the minimax excess miscoverage over informative procedures is $\widetildeΩ(1/((1-L)\sqrt{n}))$, implying a sample-complexity inflation of order $1/(1-L)^2$ for fixed excess miscoverage. Our main technical tool is a transfer theorem: any procedure returning a predictor within $\varepsilon$ of equilibrium yields equilibrium-valid coverage up to an additive $L\varepsilon$ term after split-conformal calibration. We instantiate the theorem with two retraining algorithms: a model-free method for discretizable classes and a parametric tail-averaged method that matches the $n$- and $L$-dependence of this rate up to logarithmic factors. Experiments, including semi-synthetic credit scoring, demonstrate the predicted threshold behavior and scaling laws.

Comment
45 pages, including supplementary material

Closest papers

Nearest neighbours by meaning across the whole index.

The cost of enforcing long-run coverage: a phase transition in online conformal prediction

cs.LG math.STstat.ML ·2026-11-16 ·Yu Gui, Rina Foygel Barber, Cong Ma
theory similarity 0.66
Abstract

Consider an online prediction setting, where at each time, we are given a new feature vector and asked to provide a prediction interval or prediction set that will likely contain the corresponding response. In this setting, if the data points are i.i.d. (or more generally, exchangeable), conformal prediction provides a mechanism for building valid prediction sets around the output of any trained model, offering coverage probability $\geq 1-α$ at each time $t$. In practice, however, issues such as distribution drift, changepoints, or other challenges may cause violations of the i.i.d. assumption. In this adversarial setting, online conformal prediction methods can still offer guarantees on long-run empirical coverage. However, there is a trade-off between these two types of goals: enforcing tight constraints on long-run empirical coverage to protect against the adversarial setting can lead to unstable oscillations in the instantaneous training-conditional coverage in the i.i.d. setting. In this work, we seek best-of-both-worlds algorithms that aim to minimize cumulative error in instantaneous training-conditional coverage when in the i.i.d. setting, while also offering long-run empirical coverage guarantees in the adversarial setting. Specifically, consider a condition that requires long-run empirical coverage to deviate from the target level $1-α$ by at most $\mathcal{O}(T^{-β})$, for some $β\in[0,1]$. We prove that this family of conditions can be described with a phase transition. For $β\in[0,\frac{1}{2}]$, it is possible to construct algorithms satisfying such a constraint in the adversarial setting, while offering the same instantaneous coverage performance as split conformal prediction if the data is in fact i.i.d. On the other hand, for $β\in(\frac{1}{2},1]$, this type of condition comes at a cost, and does not achieve best-of-both-worlds behavior.

0.09

The Price of Hard Coverage Constraints in Online Conformal Prediction

cs.LG math.STstat.ML ·2026-11-17 ·Mingrui Liu
similarity 0.65
Abstract

Conformal prediction provides distribution-free uncertainty quantification, but in sequential deployment, standard coverage guarantees can still allow substantial fluctuations in the number of miscoverages over time. We study an online setting in which prediction sets are produced one round at a time and the cumulative number of miscoverages must stay within a prescribed budget throughout deployment.Such a hard coverage guarantee can be enforced by enlarging prediction sets, but how much additional prediction-set size is fundamentally necessary remains unclear. We characterize this unavoidable efficiency cost over $T$ prediction rounds. Remarkably, the cost persists even with i.i.d.\ data, a known score distribution, and perfect knowledge of the population-optimal prediction set. Under suitable regularity conditions relating coverage and prediction-set size, we determine the minimum cumulative excess prediction-set size required by any online method satisfying the hard coverage constraint. This minimum cost is $Θ(\log T)$ for expected cost at a fixed time known in advance, $Θ(T^{1/3})$ for the largest expected cost over all fixed times up to $T$, and $Θ(\sqrt{T})$ for the expected worst realized cost when the evaluation time is chosen in hindsight. We further show that these rates can be attained using past scores, without knowing the score distribution. Thus, even perfect statistical knowledge does not make sequential reliability free.

0.09

Finite-Sample Optimal Conformal Prediction Sets under Covariate Shift

cs.LG stat.MLmath.COmath.PR+1 ·2026-10-27 ·Zhongyang Li
theory similarity 0.63
Abstract

We study conformal prediction under covariate shift with a known covariate density ratio, seeking prediction sets with minimum expected length under the target distribution. For every calibration sample size, we prove that the rule combining the inverse conditional-density score with randomized weighted conformal calibration minimizes this expected length among all rules valid over the full weighted-exchangeability class. We approximate the oracle using quantile and kernel histograms, including forest-weighted estimators, and select estimators and tuning parameters by resampling to estimate calibrated target length. On a bounded response domain, we bound excess length linearly in $L^1$ density error at fixed calibration size, without requiring a uniform positive lower bound on the true density. We also bound selection-pool and resampling errors. Under explicit growth conditions, the selected procedure approaches the same oracle while the calibration size remains fixed. Experiments on 36 known-density configurations and four public regression datasets compare coverage, prediction-set length, and runtime with existing methods. In targeted low-coverage and strong-shift comparisons, inverse-density selection yields shorter mean sets in most cases and lower mean runtime than the evaluated weighted baselines, with some differences in achieved coverage.

0.13

Conformal Prediction for Distribution-to-Distribution Regression

cs.LG cs.AI ·2026-11-04 ·Trung-Khang Tran, Tuan A. Hoang, Viet-Hoang Tran, Tan M. Nguyen
code/data similarity 0.62
Abstract

Conformal Prediction (CP) provides a model-agnostic framework for constructing finite-sample prediction sets with coverage guarantees and has become a tool for reliable decision-making in high-risk settings. Recent advances have extended Split Conformal Prediction to increasingly complex learning problems, including multilabel, high-dimensional, and functional outputs. In this work, we study CP for Distribution-to-Distribution Regression, a setting of growing interest across many application domains. We show that a naive application of Split CP yields prediction sets that, while marginally valid, are non-interpretable, e.g., lacking a well-defined volume or a tractable sampling procedure, and of limited practical value. To overcome this, we propose a new conformal framework that operates in an orthogonal basis space, producing interpretable prediction sets while preserving coverage guarantees. We further develop an adaptive variant with asymptotic conditional coverage under mild assumptions. Empirical results on synthetic and real-world datasets validate the effectiveness of the proposed approach. The code is publicly available at https://github.com/tuanhacs/conformal_d2d.

0.19

Rolling Conformal Prediction in Sequential Model Training

cs.LG math.STstat.MEstat.ML ·2026-09-22 ·Chen Cheng, Ruiting Liang, Rina Foygel Barber
similarity 0.62
Abstract · 42 pages, 5 figures

We introduce Rolling Conformal Prediction (rolling-CP), a distribution-free predictive inference method for the setting of sequential model training. Specifically, given a data stream $(X_1,Y_1),(X_2,Y_2),\dots$, at each time $n$ the trained model may depend on the observed history $\{(X_i,Y_i)\}_{i<n}$. This setting arises naturally in modern sequential training, including one-pass training over massive datasets and continual fine-tuning or test-time adaptation of language models during deployment. Rolling-CP first calibrates each incoming observation against the current predictor and then rolls it into future training. In this way, we avoid the need for data splitting. Remarkably, although the models at times $n=1,2,\dots$ may have entirely different properties and accuracy levels, for exchangeable data it is nonetheless possible to establish a guarantee of marginal coverage, with a familiar universal factor-two guarantee (a worst case guarantee of $1-2α$ coverage, as compared to the target level $1-α$), without any assumptions of stability or any restrictions on the model training process. For i.i.d. data streams, we further prove high-probability training-conditional validity uniformly over time; under stability conditions, coverage guarantees sharpen towards $1-α$. Numerical experiments on sequential regression, multiclass SGD, and one-pass neural-network training further demonstrate the practical effectiveness of rolling-CP.

0.33

Distribution-free inference on the number of changepoints

cs.LG stat.MLstat.ME ·2026-09-08 ·Rohan Hore, Aaditya Ramdas
theory similarity 0.62
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

The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

cs.LG ·2026-10-18 ·Guangjian Zhang
theory similarity 0.61
Abstract · 92 pages

Pointwise replicability asks that two independently trained predictors, using the same random seed, agree at each fixed query with high probability. We determine its optimal agnostic sample complexity on finite and countable domains. For every nonempty binary class of finite VC dimension $d\ge1$, the required number of independent examples is $Θ\!\left(\frac{d}{ρ^2α^2}+\frac{\log(1/β)}{α^2}\right)$, uniformly over independent accuracy, failure, and disagreement parameters $α,β,ρ\in(0,1/10)$. The learner returns one binary function, may be improper, and uses unrestricted shared randomness. Its sample budget is fixed before observing data, and the replicability guarantee includes queries of zero marginal mass. The main construction combines an ensemble of empirical-risk minimizers with a smooth, signal-dependent risk decomposition. A single shared phase selects the final binary predictor. Record times certify its weak-signal risk, while a uniform bound protects the strong-signal risk at that same selected time. A phase-comparison theorem controls the actual shared-seed execution under simultaneous changes in the marginals and risk coefficients. A rare repair step then makes the confidence cost additive. Together with matching lower bounds, this removes the remaining logarithmic overhead and parameter restrictions in the general countable-domain sample-complexity problem. This extended version also retains the earlier explicit constructions and their proofs, including proper learning for VC-one classes, the full finite-atom class, a faster realizable bound, and counterexamples that separate restrictions of particular algorithms from restrictions of the learning problem.

0.30

A Unified Perspective on Conformal Prediction and Wasserstein Distributionally Robust Optimization for Uncertainty Quantification

cs.LG math.OCeess.SY ·2026-08-30 ·Kehan Long, Yiqi Zhao, Pol Mestres, Lars Lindemann, Nikolay Atanasov +1 more
similarity 0.60
Abstract

Uncertainty quantification from finite data is central to machine learning, optimization, and automation systems, where decisions must remain reliable under limited samples and test-time distribution shift. Conformal prediction (CP) and distributionally robust optimization (DRO) offer two complementary approaches: CP constructs data-dependent prediction sets with distribution-free finite-sample validity under exchangeability, while DRO optimizes worst-case performance over an ambiguity set around an empirical distribution. We develop a unified probabilistic perspective on CP and DRO by viewing both as ways to turn finite calibration data into a data-dependent quantile estimator that a test score falls below with high probability. From this perspective, CP and DRO correct the empirical quantile along two coordinates of the same family of estimators: CP inflates the quantile level, whereas DRO shifts the quantile value through an ambiguity radius. Both methods provide the same calibration-conditional guarantee for the true distribution, requiring the target coverage to hold with high probability over the calibration sample. Their constructions differ, however: CP uses a closed-form, distribution-free level correction, while DRO uses a value-space correction whose certified radius depends on properties of the unknown distribution and additionally guarantees coverage uniformly over the ambiguity set. This distinction emerges in the tails of the score distribution. Because CP relies on sparse upper-tail order statistics of the calibration samples, its level inflation barely moves the estimator when those samples are dense near the target quantile but overshoots when they are sparse, whereas a well-chosen DRO radius corrects in value space and may avoid this overshoot.

0.30