Vanilla CP has strongest assumption:
However, many assumption failures exist:
E.g.
Selective Bias “conditional from x”
Data Distribution shift between n and 1
⇒ Weighted CP, Known Acquisition CP
| Assumption on joint $f$ | How $(\ast)$ is handled | Weights | Knowledge required | Guarantee | |
|---|---|---|---|---|---|
| Vanilla CP | Permutation-invariant | $f$ cancels; count permutations equally | Uniform $\frac{1}{n+1}$ | None | Exact $1-\alpha$ |
| Weighted CP | $f = \prod_j w_j(v_j)\cdot g$, $g$ symmetric | $g$ cancels; permutations weighted by $\prod w_j$ | Data-dependent (likelihood ratios) | Likelihood ratio known/estimated | Exact, if ratio correct |
| ICML'24 | None (theory); known factorization into acquisition factors × symmetric factors (practice) | Computed exactly from $f$; symmetric factors cancel | Data-dependent (exact permutation probs) | Data acquisition process $p_{X_j\mid \text{past}}$ | Exact |
| Beyond Exch. | None | Never computed; error of ignoring it is bounded | Fixed, user-chosen | None (just a belief about where shift is mild) | Approximate: $1-\alpha - \sum \tilde{w}i d{\mathrm{TV}}$ |
| LP-robust CP | $f=P^{\otimes n}\otimes Q$ with $\mathrm{LP}\varepsilon(P,Q)\le\rho$: test law in an OT ball ($W\infty$ move $\le\varepsilon$ + TV mass $\le\rho$); $Q\not\ll P$ allowed | Never computed — bounded: ball pushed to 1-D score ball, DRO solved in closed form → level $+\rho$, threshold $+\varepsilon$ | Uniform (adapts level + threshold, not weights) | Two scalars $(\varepsilon,\rho)$ (estimable from test scores via 1-D OT); no ratios; needs $\rho<\alpha$ | $\ge 1-\alpha$ per-instance, uniform over ball (Cor 4.2 correction); vanilla at $\varepsilon=\rho=0$; TV at $\varepsilon=0$, $W_\infty$ at $\rho=0$ |
| RSCP (adv. robust CP) | Permutation-invariant for the latent clean data $(Z_1,\dots,Z_{n+1})$; observed test point is $\tilde{X}{n+1}=X{n+1}+\epsilon$, $|\epsilon|2\le\delta$, with $\epsilon$ arbitrary (adversarial, point-dependent) | $f$ cancels exactly as in vanilla CP — the shift never enters $(\ast)$ at all; it is absorbed in score space via a certified bound $\tilde S(\tilde X,y)\le \tilde S(X,y)+\delta/\sigma$, i.e., threshold inflation $Q{1-\alpha}+M_\delta$ | Uniform $\frac{1}{n+1}$ (unchanged) | Attack budget $\delta$ + a score with certifiable Lipschitz-type constant (constructed via randomized smoothing, $M_\delta=\delta/\sigma$); no knowledge of the attack algorithm or shifted distribution | Conservative $\ge 1-\alpha$, uniform over all $\ell_2$-bounded attacks; exact vanilla guarantee recovered at $\delta=0$ | | --- | --- | --- | --- | --- | --- | | ACI (Gibbs–Candès) | None — f arbitrary, non-stationary, even adversarial; f need not even be modeled | Never touched. (∗) is abandoned entirely: coverage does not come from rank/permutation probabilities under f, but from feedback control in level space — the online update αt+1 = αt + γ(α − errt) telescopes, forcing the running error rate to α regardless of f | Uniform (unchanged); adaptation happens in the quantile level 1−αt, not in the weights | None about f. Requires online feedback: Yt must be revealed after each prediction (to compute errt), plus a step size γ | Different object: long-run empirical frequency, not a probability. |1/T Σ errt − α| ≤ (max{α1, 1−α1} + γ)/(Tγ) a.s.; no per-instance P(Yt ∈ Ĉt) ≥ 1−α; errors may cluster in time | | DtACI (Gibbs–Candès '22, arbitrary shifts) | None — same as ACI: f arbitrary, non-stationary, adversarial; data can even be viewed as a fixed sequence (Thm 3.1 treats β₁,…,β_T as given) | Never touched, same level-space feedback control as ACI — but now two layers: k parallel ACI experts with step sizes γ₁<…<γ_k, plus an online expert-aggregation scheme that selects among their levels αᵗᵢ. The step size itself becomes a learned parameter, tuned by online convex optimization on the pinball loss ℓ(β_t, α_t) | Rank/permutation weights: uniform, unchanged. But data-dependent exponential weights reappear one level up: expert weights wᵗᵢ built from exp(−η·pinball losses) with a forgetting/mixing parameter σ — a recency-weighted mixture, so recent performance dominates the choice of γ | None about f. Online feedback of Y_t (as in ACI) + a candidate grid {γᵢ} and hyperparameters (η, σ), settable via a heuristic target window (e.g. |I| = 500). Crucially, the rate of distribution shift need not be known — removing ACI's key requirement that γ be tuned ∝ the (unknown) speed of change | Empirical-frequency object again, but upgraded from global to local: over every interval I, dynamic regret ≤ O(√(log|I|/|I|)) + O(√(Σ|αt−α{t−1}|/|I|)); under mild regularity (density of β_t bounded below, Lipschitz coverage map) this bounds |coverage − (1−α)| uniformly over all local windows — errors can no longer cluster in time. Long-run: 1/T Σ err_t → α exactly iff η_t, σ_t → 0; with constant η, σ, a small (practically negligible) bias may persist |