Recalibrating Many Questions with Few Labels: Minimax Rates and Identification Limits

Xiaoyu Li; Chiwun Yang

cs.LGOct 13, 2026

Recalibrating Many Questions with Few Labels: Minimax Rates and Identification Limits

Authors: Xiaoyu Li, Chiwun Yang

Organizations: University of New South Wales. · City University of Hong Kong.

Abstract

Many related prediction problems, which we call questions, come with few labels each. What information can be shared across them, and what is actually necessary for good decisions? We answer both for recalibration, motivated by decision models such as Jev (TypeSafe AI, 2026) that return a probability for any yes/no question a developer writes. A predictor reports a probability $P$ with output law $μ$ on $m$ questions, each with $n$ labels and a nondecreasing map $g_j(p)=\mathbb{P}(Y=1\mid P=p)$ ; the compound risk is the excess Brier score over the true maps, averaged over questions. Over maps within sup-distance $τ\le 1$ and total variation $V\le 2$ of one nondecreasing shape (fixed effects), the minimax compound risk is $(mn)^{-2/3}+\min\{τ^2,1/n\}+\min\{τ^2,V^2,(V/n)^{2/3}\}$ up to universal constants, for every non-atomic $μ$ . A pooled isotonic fit with a per-question correction sized once, on held-out labels of all questions, attains it without knowing $τ$ , $V$ or $μ$ ( $n\ge 2$ , $m\ge 3$ ); tuning each question on its own labels loses a factor of order $\min\{n,\log(m^2/n)\}$ when the maps differ by constants and $m^2/n$ is large. When the maps are drawn from an unknown prior (random effects), other questions need not identify the Bayes rule. The loss, the identification regret, is at most $2^{-n}$ once the law of a question's data is known, extending a bound of Skibinsky (1968) for coins, and in the worst case at least $β_\star^{-n}/(72\sqrt{n})$ at every finite $m$ , where $β_\star\approx 3.583$ . Beyond a few labels per question, what cannot be learned is nearly unnecessary. For constant maps (an uninformative predictor) and constant-map priors, the exponential base is exactly $β_\star$ , not the 4 suggested by the moment range; for monotone maps it lies in $[2,β_\star]$ .

Figures & tables

Result	Benchmark	$m$	Class	Bound	Tight?
What can be shared (fixed effects)
Thm. 3.2	minimax compound risk	every $m\geq 1$	$\Theta(\tau,V)$ , $\tau\leq 1$ , $V\leq 2$ , non-atomic $\mu$	$\mathfrak{M}_{m,n}(\tau,V;\mu)\asymp\Phi(m,n,\tau,V)$	yes, up to universal constants
Prop. 3.6	worst-case ratio $\kappa_{g_{0}}$ to $\Phi$	$m^{2}\geq 216n$	per-question rules, shift model $V=0$	best per-question rule: $\asymp\min\{n,\log(m^{2}/n)\}$ ; compound hold-out: $O(1)$ (non-atomic $\mu$ )	yes, in order
What is necessary for decisions (random effects)
Thm. 4.2	identification regret $\mathrm{Reg}_{n}$	$m=\infty$	$\mathcal{G}_{\mathrm{mono}}$ , every $\mu$	$\mathrm{Reg}_{n}(G;\mathcal{G}_{\mathrm{mono}})\leq 2^{-n}$ at every prior $G$ , guaranteed by the posterior mean of any data-equivalent prior	open: base in $[2,\beta_{\star}]$
Cor. 4.7	worst-case excess over $R^{*}_{n}$	every $m\geq 1$	$\mathcal{G}_{\mathrm{mono}}$ , every $\mu$	$\geq 1/(8\tbinom{2n}{n})$ and $\geq\beta_{\star}^{-n}/(72\sqrt{n})$	lower bound only (open problem 2, Sec. 6.2 )

Table 1: The results at a glance. Fixed effects : the maps are arbitrary members of the class; random effects : they are independent draws from a prior, and

m=\infty

means that the law of one question’s data is known. “In order”: up to universal constants, which are not optimized. Evidence grades ( Section 5 ): E1, seeded simulation sweep; E2, global search, values attained but optimality not certified; E3, exact rational arithmetic.

Panel of Figure 2 — Figure 2: The compound hold-out procedure of Definition 3.1 (iii) ( $m\geq 3$ , $n\geq 2$ ). The shape is learned from the pooled $A$ -halves of the other questions, each question fits its own constrained correction for every candidate $\lambda$ , and a single $\widehat{\lambda}$ , the size of the deviations, is chosen from the hold-out halves of all questions together. For $n=1$ or $m\leq 2$ the procedure is a plain isotonic fit ( Definition 3.1 (iv)).

Panel of Figure 3 — Figure 3: Which term of $\Phi$ dominates, for fixed $m,n$ with $m^{2}\gg n$ (schematic; logarithmic axes; boundaries up to constant factors, read off $\Psi$ in Theorem 3.2 ). The shift model $V=0$ is the left edge. In the two shaded regions the pooled isotonic fit alone attains the rate (for non-atomic $\mu$ ), since its risk is $O((mn)^{-2/3}+\tau^{2})$ ( Lemma B.4 , and $\lvert g_{j}-\bar{g}\rvert\leq 2\tau$ ); above them each question pays for its own offset ( $V\leq n^{-1/2}$ ) or for its own deviation ( $V\geq n^{-1/2}$ ). When $m^{2}\lesssim n$ the pooling term $(mn)^{-2/3}\geq 1/n$ absorbs the offset region.

Panel of Figure 4 — Figure 4: The two prices of an unknown prior, for priors on constant maps (schematic). On the identified set $[H]$ the risks depend on $H^{\prime}\in[H]$ only through the free moment $\int\theta^{n+1}dH^{\prime}$ , which ranges over an interval of length $\rho_{n}(H)\leq 4^{-n}$ , and the Bayes risk is a concave quadratic in it ( Skibinsky, 1968 , eqs. (8)–(9)) ; the risk of a fixed rule is affine in it, being linear in the moments of $H^{\prime}$ . The Bayes rule at the midpoint therefore has the tangent there as its risk, and its largest excess over the Bayes risk, at the endpoints, is the curvature term $(\rho_{n}/2)^{2}\sum_{s}\binom{n}{s}/b_{s}=\mathrm{Reg}_{n}(H;\mathcal{G}_{\mathrm{const}})$ of ( 4.2 ). Skibinsky’s gap, maximized over $[H]$ , is the whole range of the Bayes risk over the interval ( Skibinsky, 1968 , Theorem 1) ; when the vertex lies outside the interval, as for the numerical maximizers with $n\geq 4$ ( Remark 4.12 ), the range is $\rho_{n}(H)$ times the absolute slope at the midpoint and can be much larger.

Figure 5: Per-question versus compound tuning (numerical evidence, E1; 30 replications per configuration of the declared range). Each marker is one configuration, colored and shaped by

m

: the risk of a data-driven rule divided by the smallest risk among four fixed estimators (the pooled isotonic fit; the pooled fit plus a per-question mean shift; the two-stage estimator with the true

(\tau,V)

; per-question isotonic regression). (a), (b): one choice per question by two-fold cross-validation on that question’s labels, (a) among all four fixed estimators, (b) without the two-stage estimator. (c), (d): one choice for all questions by the cross-validation error summed over questions, (c) among the pooled fit, the pooled fit plus shift, per-question isotonic regression and the two-stage estimator on a fixed grid of seven radius pairs (no knowledge of

(\tau,V)

), (d) among all four fixed estimators. Panels (c) and (d) were added post hoc. The insets give the median and the maximum ratio over the range.

Figure 6: The constant-map identification regret against Theorem 4.8 (numerical evidence).

S_{n}

is the largest value of

\mathrm{Reg}_{n}(H;\mathcal{G}_{\mathrm{const}})

found by global search; each

S_{n}

is an exact-arithmetic lower bound on the supremum (E3), its optimality is not certified (E2). Filled markers: declared run (

n\leq 30

); open markers: post-hoc extension (

31\leq n\leq 60

). (a)

\beta_{\star}^{n}S_{n}

, the range

[1/(72\sqrt{n}),1]

allowed by Theorem 4.8 , and the arcsine regret

\beta_{\star}^{n}/(8\binom{2n}{n})

. (b) The local base

S_{n}/S_{n+1}

, with the base

4

of the moment range and

\beta_{\star}

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 7 — Figure 7: How the results depend on each other: an arrow points from a result to a result whose proof uses it (arrows implied by transitivity are omitted). Shaded boxes are the main statements; the dashed box is a cited theorem.

Probability Calibration

Probability calibration measures and improves whether predicted probabilities match observed outcome frequencies, supporting reliable decisions under uncertainty.

See all 134 papers

Oct 15, 2026

Sharp and Stable Label-Free Calibration Certificates from Logical Coherence

Query-conditioned probabilistic predictors answer logically related questions one at a time, and labels to check their calibration are often missing. For each restriction on what a bettor's stakes may use, a minimax theorem identifies, for finitely supported laws of the answers, the sharp label-free lower bound on the corresponding calibration residual. On bundles of different events its mean, marginal and joint stages can separate strictly, and a bundle's bound cannot be attributed to one question without assumptions on the others. The sharp marginal bound is discontinuous in the answers, and no label-free lower bound continuous in the Wasserstein distance stays within a constant factor of it. Lipschitz stakes give a stable bound, sharp for a smooth calibration residual and, for every positive Lipschitz constant, positive exactly when the sharp marginal bound is. On i.i.d. streams, projected online gradient ascent at fixed nodes gives fixed-horizon certificates whose shortfall is bounded by grid, learning and statistical terms, and predictable betting gives anytime-valid ones. In a preregistered study of four predictors on two data sets, all seven confirmatory certificates were positive (the eighth pair did not pass the pilot). A certificate shows only that calibration is at least this bad; zero means "not refuted".

Takahiro Kato

NP-hard, Inc.

Probability Calibration

Ask PDF

Oct 6, 2026

Performative Prediction with Selective Labels

Many social applications of machine learning exhibit performative effects: population behavior changes in response to deployed models. Performative prediction studies this interaction through a distribution map that relates each model to the population distribution it induces. One of the main results in this framework showed that repeated risk minimization (RRM), which updates models by retraining on the most recent data, can converge to a stable model that minimizes risk on its own induced distribution. However, existing analyses typically assume access to the complete distributions of features and labels after model deployment, ignoring the possibility of selective labels: observing labels only for the accepted subset of the population. In this work, we formalize performative prediction with selective labels and show that retraining only on observed data can misguide the retraining procedure and undermine the guarantees of convergence to a stable solution. We then propose a worst-case objective based on knowledge of a confidence interval on the probability of a positive label. Applying RRM to this objective permits us to remain within a bounded distance to the true stable point. Under a sensitivity assumption on the conditional label distribution, we further show how previously accepted data can tighten these confidence intervals over time. Experiments in a lending application with fairness regularization show that our robust optimization approach closely matches the performance of RRM with complete label access.

Giovani Valdrighi, Isabel Valera, Marcos Medeiros Raimundo

Instituto de Computação Universidade Estadual de Campinas Campinas, Brazil · Department of Computer Science Saarland University Saarbrücken, Germany

Performative Prediction Selective Labels

Ask PDF

Mar 16, 2026

Decomposing Probabilistic Scores: Reliability, Information Loss and Uncertainty

Calibration is a conditional property that depends on the information retained by a predictor. We develop decomposition identities for arbitrary proper losses that make this dependence explicit. At any information level

\mathcal A

, the expected loss of an

\mathcal A

-measurable predictor splits into a proper-regret (reliability) term and a conditional entropy (residual uncertainty) term. For nested levels

\mathcal A\subseteq\mathcal B

, a chain decomposition quantifies the information gain from

\mathcal A

\mathcal B

. Applied to classification with features

\boldsymbol{X}

and score

S=s(\boldsymbol{X})

, this yields a three-term identity: miscalibration, a {\em grouping} term measuring information loss from

\boldsymbol{X}

S

, and irreducible uncertainty at the feature level. We leverage the framework to analyze post-hoc recalibration, aggregation of calibrated models, and stagewise/boosting constructions, with explicit forms for Brier and log-loss.

Arthur Charpentier, Agathe Fernandes Machado

UQAM, Montréal, Canada · Kyoto University, Japan

Probability Calibration Uncertainty Decomposition Proper Scoring Rules

Ask PDF

Abstract

Probability Calibration

Explore similar work

Sharp and Stable Label-Free Calibration Certificates from Logical Coherence

Performative Prediction with Selective Labels

Decomposing Probabilistic Scores: Reliability, Information Loss and Uncertainty