Recalibrating Many Questions with Few Labels: Minimax Rates and Identification Limits
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 gj(p)=ℙ(Y=1| P=p); the compound risk is the excess Brier score over the true maps, averaged over questions. Over maps within sup-distance τ≤ 1 and total variation V≤ 2 of one nondecreasing shape (fixed effects), the minimax compound risk is (mn)−2/3+min{τ2,1/n}+min{τ2,V2,(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≥ 2, m≥ 3); tuning each question on its own labels loses a factor of order min{n,log(m2/n)} when the maps differ by constants and m2/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 β⋆−n/(72√n) at every finite m, where β⋆≈ 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 β⋆, not the 4 suggested by the moment range; for monotone maps it lies in [2,β⋆].
Related
- Conformalized Quantile Regression and Minimax Limits of Fixed-Score Calibration under Known Covariate Shift
- Debiased Inference for AI-Generated Data without Gold-Standard Labels: Identification via Multiple Imperfect Measurements
- Learning Sparse Support under Differential Privacy: Adaptive Algorithms and Minimax Limits
- When Is a Relevance Threshold Statistically Resolvable? Minimax Limits for Effect Classification
- Detecting a Shift Is Not Enough: Exact Minimax Limits of Linear Representation Repair
BibTeX
@misc{li2026recalibrating,
title = {{Recalibrating Many Questions with Few Labels: Minimax Rates and Identification Limits}},
author = {Xiaoyu Li and Chiwun Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18488},
eprint = {2610.18488},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18488},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Recalibrating Many Questions with Few Labels: Minimax Rates and Identification Limits
AU - Xiaoyu Li
AU - Chiwun Yang
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18488
UR - https://arxiv.org/abs/2610.18488
AB - 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)=ℙ(Y=1| P=p); the compound risk is the excess Brier score over the true maps, averaged over questions. Over maps within sup-distance τ≤ 1 and total variation V≤ 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≥ 2, m≥ 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 β_⋆^−n/(72√n) at every finite m, where β_⋆≈ 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 β_⋆, not the 4 suggested by the moment range; for monotone maps it lies in [2,β_⋆].
ER -