Monotone risk calibration and finite-sample deployment guarantees

Let $n,M\ge 1$, $B>0$, and $\alpha \in [0,B)$. Fix a deterministic strictly ordered grid $\mathrm{\Lambda }=\{{\lambda }_1<\cdots <{\lambda }_M\}\subset \mathbb{R}$ and a probability space $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$. For $i=1,\dots ,n+1$, let $W_i$ be a random element of $[0,B{]}^M$ with its Borel sigma-algebra, and write $L_i({\lambda }_j)=(W_i{)}_j$. The rows $W_1,\dots ,W_{n+1}$ are exchangeable when their joint law is invariant under every permutation of the $n+1$ row indices. The coordinates $L_i({\lambda }_j)$ are the losses of the finite decision family at observation $i$; in a prediction problem they may be obtained by applying each fixed prediction rule to that observation and evaluating a specified loss.

The family is loss-nested when, with probability one, $L_i({\lambda }_1)\ge \cdots \ge L_i({\lambda }_M)$ for every $i$. It is endpoint-safe at level $\alpha$ when, with probability one, $L_i({\lambda }_M)\le \alpha$ for every $i$. For any measurable selector $\widehat{\lambda }$ taking values in $\mathrm{\Lambda }$ and determined by the calibration rows $W_1,\dots ,W_n$, its marginal expected test risk is $\mathbb{E}[L_{n+1}(\widehat{\lambda })]$, with expectation over all $n+1$ rows. This expectation is finite because every loss lies in $[0,B]$. Here “nested” means nonincreasing loss on the specified grid; literal inclusion of prediction sets is not required.

Exchangeable random elements: exchangeability means invariance of the joint law under every coordinate permutation.

Random elements and real random variables: a random element is a measurable map from a probability space into a measurable space.

Expectation of a nonnegative or integrable random variable: the expectation of a bounded nonnegative loss is its Lebesgue integral against the probability measure.

Angelopoulos et al., Conformal Risk Control, §1.1

Angelopoulos, Barber, and Bates, Theoretical Foundations of Conformal Prediction, Chapter 2 §§2.1–2.2

Input a deterministic ordered grid $\mathrm{\Lambda }=\{{\lambda }_1<\cdots <{\lambda }_M\}$ with $M\ge 1$, a calibration size $n\ge 1$, a bound $B>0$, a target $\alpha \in [0,B)$, and calibration losses $L_i({\lambda }_j)\in [0,B]$ for $1\le i\le n$ and $1\le j\le M$. Also supply the prediction rule $d_{{\lambda }_j}$ associated with each grid point. For $j=1,\dots ,M$ in order, compute $T_j=\frac{{\sum }_{i=1}^n{L}_i({\lambda }_j)+B}{n+1}\mathrm{.}$ Return $({\lambda }_j,d_{{\lambda }_j},\text{pass})$ at the first index for which $T_j\le \alpha$. If no index passes, return $({\lambda }_M,d_{{\lambda }_M},\text{fallback})$. Monotonicity and the endpoint-safety assumption from the finite nested decision family are hypotheses for the risk theorem, not checks of the unobserved test loss.

Finite nested decision families and bounded risk: the grid, bounded loss array, loss-nesting convention, endpoint-safety condition, and marginal expected test risk.

Angelopoulos et al., Conformal Risk Control, §1.1, equation (4)

For every admissible input to the finite-grid risk-control rule, the rule returns a unique output after at most $M$ threshold tests; no loss monotonicity or endpoint-safety assumption is required for this assertion.

Let $n,M\ge 1$, $B>0$, and $\alpha \in [0,B)$. On a probability space $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$, let $W_1,\dots ,W_{n+1}$ be exchangeable random elements of $[0,B{]}^M$ with its Borel sigma-algebra, and write $L_i({\lambda }_j)=(W_i{)}_j$ on a deterministic grid $\mathrm{\Lambda }=\{{\lambda }_1<\cdots <{\lambda }_M\}$. Assume that, almost surely, $L_i({\lambda }_1)\ge \cdots \ge L_i({\lambda }_M)$ for every $i$ and $L_i({\lambda }_M)\le \alpha$ for every $i$. Apply the finite-grid risk-control rule to the first $n$ rows and let $\widehat{\lambda }$ be its selected parameter. Then $\mathbb{E}[L_{n+1}(\widehat{\lambda })]\le \alpha ,$ where the expectation is over all $n+1$ rows.

For a sub-sigma-algebra $\mathcal{T}\subseteq \mathcal{F}$, suppose the full matrix $W=(W_1,\dots ,W_{n+1})$, viewed in $([0,B{]}^M{)}^{n+1}$ with its product Borel sigma-algebra, has an actual regular conditional distribution $Q_{\omega }$ given $\mathcal{T}$. Suppose that, for almost every training outcome $\omega$, the section $Q_{\omega }$ is row-exchangeable and the same bounds, monotonicity, and endpoint hypotheses hold $Q_{\omega }$-almost surely. Then the same argument gives $\mathbb{E}[L_{n+1}(\widehat{\lambda })\mid \mathcal{T}]\le \alpha$ almost surely.

Finite nested decision families and bounded risk: finite grid, row exchangeability, bounded losses, loss monotonicity, endpoint safety, and marginal expected test risk.

Finite-grid conformal risk control: the first-passing calibration rule and maximum-grid fallback.

Regular conditional distribution: a conditional probability kernel satisfying the conditional-event identity.

Conditional expectation given a sigma algebra: a conditional-expectation version is characterized by its integrals over all conditioning events.

Angelopoulos et al., Conformal Risk Control, §2.1

Angelopoulos, Barber, and Bates, Theoretical Foundations of Conformal Prediction, Chapter 2 §§2.1–2.2

Let $n,M\ge 1$, $B>0$, and $\alpha \in [0,B)$. On a probability space $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$, let $W_1,\dots ,W_{n+1}$ be exchangeable random elements of $[0,B{]}^M$ with its Borel sigma-algebra, and write their coordinates as $L_i({\lambda }_j)$ on a deterministic grid $\mathrm{\Lambda }=\{{\lambda }_1<\cdots <{\lambda }_M\}$; do not assume the original rows are nonincreasing. Assume $L_i({\lambda }_M)\le \alpha$ almost surely for every $i$. Define the finite tail-maximum losses ${\tilde{L}}_i({\lambda }_j)={\max }_{j\le k\le M}{L}_i({\lambda }_k)\mathrm{.}$ Apply the finite-grid risk-control rule to the transformed calibration rows and let $\tilde{\lambda }$ be its selected parameter. Then $\mathbb{E}[L_{n+1}(\tilde{\lambda })]\le \alpha \mathrm{.}$ The expectation is over all calibration and test rows. If the rows have an actual regular conditional exchangeable law given a training sigma-algebra and the same bounds and endpoint condition hold almost surely in that law, the corresponding conditional expected-risk bound also holds almost surely.

Finite nested decision families and bounded risk: exchangeable loss rows, bounds, grid, endpoint safety, and expected test risk.

Finite-sample expected-risk control on a finite grid: finite-grid risk control for exchangeable coordinatewise nonincreasing rows.

Regular conditional distribution: the actual conditional probability kernel used for the conditional clause.

Conditional expectation given a sigma algebra: conditional expected risk is identified by its integrals on conditioning events.

Angelopoulos et al., Conformal Risk Control, §2.4, Corollary 1

The finite-grid theorem controls expected test loss after averaging over both the calibration rows and the test row. It is not a high-probability guarantee on the conditional risk after the realized calibration sample. For a two-state illustration, let $U\in \{0,1\}$ represent the realized calibration state with $\mathbb{P}(U=0)=\mathbb{P}(U=1)=1\mathrm{/}2$, let $\mathcal{T}=\sigma (U)$, and let the test loss $X$ equal $0$ when $U=0$ and $1\mathrm{/}2$ when $U=1$. Then the conditional risk $R=\mathbb{E}[X\mid \mathcal{T}]$ equals $X$, so $\mathbb{E}[R]=1\mathrm{/}4$ while $\mathbb{P}(R>1\mathrm{/}4)=1\mathrm{/}2$. Thus expected-risk control alone does not imply a high-probability bound on conditional risk. The finite-grid theorem and its monotone-envelope extension give no general risk bound conditional on an arbitrary subgroup event or covariates. They do give the corresponding conditional bound when the full loss matrix has an actual regular conditional law given the sigma-algebra generated by that information, its sections are exchangeable, and the applicable boundedness, nesting, and endpoint-safety assumptions hold almost surely under those sections. The results give no validity when the deployment distribution differs from the exchangeable calibration and test distribution or when arbitrary reuse of calibration rows breaks exchangeability. For a classifier on a random labeled input, let $Y$ and $\widehat{Y}$ be its true and predicted labels and let $C\in [0,1]$ be its measurable reported confidence. Top-label probability calibration means $\mathbb{E}[\mathbf{1}\{Y=\widehat{Y}\}\mid \sigma (C)]=C$ almost surely; this is a different claim and is not concluded here. Split conformal coverage controls the particular miscoverage event under its own exchangeability hypotheses; it is not a guarantee for every bounded loss. For nonmonotone losses, the finite tail-maximum theorem applies but can increase the loss and make the selected decision more conservative. The conditional form proved here for an independently trained model assumes an actual regular conditional exchangeable law of the calibration and test rows, with the stated hypotheses holding almost surely.

Finite-sample expected-risk control on a finite grid: expected test loss is averaged over calibration and test rows.

Finite-grid risk control by monotone envelopes: finite tail maxima dominate the original losses pointwise.

Split conformal marginal coverage: the exchanged split-score rank theorem controls marginal miscoverage under its stated conditional exchangeability hypotheses.

Regular conditional distribution: conditional distribution means a probability kernel satisfying the conditional-event identity.

Angelopoulos et al., Conformal Risk Control, §§1.2, 2.3–2.4, 4.1

Angelopoulos, Barber, and Bates, Theoretical Foundations of Conformal Prediction, Chapter 4

Shafer and Vovk, A Tutorial on Conformal Prediction, §§2.2, 3.1–3.2, 4.2–4.5