CoChat
Sign Up
Cited by 147Adversarial Robustness in Machine LearningMachine Learning and AlgorithmsMachine Learning and Data Classification

The DOI matches its Crossref record; 70 of the 70 references it cites were found in a registry or an index; none of the 22 sources its claims cite is checked for support yet.

Distribution-free, Risk-controlling Prediction Sets

Open access
Bates, Stephen, Angelopoulos, Anastasios, Lei, Lihua, Malik, Jitendra, Jordan, Michael·2021·Journal of the ACM
DOI 10.1145/3478535
Open this paper in CoChat — free accountOpen PDF

Abstract

While improving prediction accuracy has been the focus of machine learning in recent years, this alone does not suffice for reliable decision-making. Deploying learning systems in consequential settings also requires calibrating and communicating the uncertainty of predictions. To convey instance-wise uncertainty for prediction tasks, we show how to generate set-valued predictions from a black-box predictor that controls the expected loss on future test points at a user-specified level. Our approach provides explicit finite-sample guarantees for any dataset by using a holdout set to calibrate the size of the prediction sets. This framework enables simple, distribution-free, rigorous error control for many tasks, and we demonstrate it in five large-scale machine learning problems: (1) classification problems where some mistakes are more costly than others; (2) multi-label classification, where each observation has multiple associated labels; (3) classification problems where the labels have a hierarchical structure; (4) image segmentation, where we wish to predict a set of pixels containing an object of interest; and (5) protein structure prediction. Last, we discuss extensions to uncertainty quantification for ranking, metric learning, and distributionally robust learning.

Overview

AI snapshot

Written from the paper’s full text.

TL;DR

The paper introduces risk-controlling prediction sets (RCPS), a distribution-free, finite-sample method to turn any black-box predictor into set-valued predictions whose expected loss is below a user-specified level with high probability. It develops upper-confidence-bound calibration, concentration inequalities for bounded and unbounded losses, and demonstrates the framework on five large-scale prediction tasks.

Key findings

  • RCPS calibration chooses the smallest nested set parameter \(\lambda\) such that a pointwise upper confidence bound on risk stays below \(\alpha\) for all larger \(\lambda\), yielding a \((\alpha,\delta)\)-RCPS guarantee (Theorem 1).
  • For bounded losses, the Waudby-Smith–Ramdas bound is recommended for non-binary losses; for binary losses, the exact binomial bound should be used. For unbounded losses, the Pinelis–Utev bound gives valid coverage under bounded coefficient of variation, while the CLT bound is tighter but lacks finite-sample guarantees and undercovers heavy-tailed distributions.
  • The greedy set construction is approximately optimal: under loss forms \(L(y,S)=L_y 1\{y\notin S\}\) and more general \(L(y;S)=\int_{z\in S^c}\ell(y,z)d\mu(z)\), it has smallest average set size among risk-controlling predictors (Theorems 7 and 8).
  • Experiments report risk control on ImageNet classification with class-varying loss (30,000 calibration, 20,000 evaluation points, 100 splits, \(\alpha=\delta=0.1\)), MS COCO multi-label classification (4,000 calibration, 1,000 test, \(\alpha=\delta=0.1\)), hierarchical ImageNet classification (\(\alpha=0.05,\delta=0.1\)), polyp segmentation (1,781 examples, 1,000 calibration, \(\alpha=\delta=0.1\)), and protein structure prediction on 71 CASP-13 test points (35 calibration, 36 test, \(\alpha=2\)Å, \(\delta=0.1\)).

Methods

  • Split data into a training set and a calibration set; fit an arbitrary black-box predictor \(f\) on the training set, then use only calibration points to calibrate a nested family of set-valued predictors \(T_\lambda\) with monotone loss.
  • Construct upper confidence bounds for risk via concentration inequalities: Hoeffding, Hoeffding–Bentkus, empirical Bernstein, Waudby-Smith–Ramdas, exact binomial for binary losses, Pinelis–Utev for unbounded losses, and an asymptotic CLT bound; numerical simulations use one million replicates to compare coverage and median gap.
  • Evaluate on five tasks using ImageNet with ResNet-152/ResNet-18, MS COCO with TResNet, polyp segmentation datasets with PraNet, and AlphaFoldv1 distograms for protein structure, reporting risk and set sizes over random splits.

Limitations

  • The paper states that unbounded losses require regularity conditions such as bounded coefficient of variation; Proposition A.1 shows no nontrivial finite-sample upper confidence bound exists for nonnegative random variables without restrictions.
  • The CLT bound lacks finite-sample coverage guarantees and undercovers in simulations, especially for small means and heavy-tailed distributions; the protein experiment uses only 35 calibration and 36 test points and reports only the CLT bound because exact concentration results are “hopelessly conservative” at that sample size.
  • The protein experiment uses semi-synthetic data because ground-truth distance data was unavailable, and the greedy optimality results assume exact conditional density and specific loss forms, whereas practice uses plug-in estimates.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1145/3478535

Cites

70 of 70 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

0 of 22 cited sources checked · 0 supported · 0 flagged

Show all 65 claims

  • It may state two separate claims as one. 24
  • Probably not a substantial claim. 22
  • The quote only partly states this claim. 1
41 of 41

  • The authors state this as an assumption.

    There exists λmax ∈ Λ such that R(λmax)=0.

    “We further assume that there exists an element λ max ∈ Λ such that R(λ max ) = 0.”

  • The authors state this as an assumption.

    For each λ, a pointwise upper confidence bound R+(λ) for R(λ) is available such that P(R(λ) ≤ R+(λ)) ≥ 1-δ.

    “We assume that we have access to a pointwise upper confidence bound (UCB) for the risk function for each λ: where R + (λ) may depend on (X 1 , Y 1 ), . . ., (X n , Y n ).”

  • The authors state this as an assumption.

    The loss function satisfies the nesting property: S ⊂ S' ⇒ L(y,S) ≥ L(y,S').

    “We require that the loss function respects the following nesting property: S ⊂ S =⇒ L(y, S) ≥ L(y, S ).(2)”

  • The authors state this as an assumption.

    The collection of set-valued predictors {Tλ} is nested: λ1 < λ2 ⇒ Tλ1(x) ⊂ Tλ2(x).

    “We further suppose we have a collection of such set-valued predictors indexed by a one-dimensional parameter λ taking values in a closed set Λ ⊂ R ∪ {±∞} that are nested, meaning that larger values of λ lead to larger sets: λ 1 < λ 2 =⇒ T λ 1 (x ) ⊂ T λ 2 (x ).(1)”

  • The authors state this as an assumption.

    R(λ) is continuous.

    “Suppose Equation (3) holds pointwise for each λ, and that R(λ) is continuous.”

  • The authors state this as an assumption.

    The calibration data and test data come from the same distribution.

    “The only requirement is that the calibration data and the test data come from the same distribution.”

  • The authors state this as an assumption.

    The data (Xi, Yi) are i.i.d.

    “Let (X i , Y i ) i=1, ...,m be an independent and identically distributed (i.i.d.) set of variables”

  • The authors state this as an assumption.

    For each λ, c_v(λ) ≤ c_v for some constant c_v.

    “suppose in addition that for each λ ∈ Λ, c v (λ) ≤ c v for some constant c v .”

  • The authors state this as an assumption.

    The loss L(Y, Tλ(X)) has a finite second moment for each λ.

    “assume additionally that L(Y , T λ (X )) has a finite second moment for each λ.”

  • The authors state this as an assumption.

    The loss is bounded above by one.

    “We begin with the case where our loss is bounded above and, without loss of generality, we take the bound to be one.”

  • The paper relies on this without support.

    Black-box predictive algorithms are rarely accompanied by reliable uncertainty quantification.

    “Problematically, however, these algorithms are rarely accompanied by reliable uncertainty quantification.”

  • The paper relies on this without support.

    Prediction failures will often be silent ones, particularly in high-consequence settings.

    “Thus, prediction failures will often be silent ones, which is particularly alarming in high-consequence settings.”

  • The paper relies on this without support.

    Black-box prediction will be with us for some time to come.

    “it is clear that black-box prediction will be with us for some time to come.”

  • The authors state this as an assumption.

    The predictor px(y) is an estimate of p_{Y|X=x}(y).

    “We assume that our predictor is px (y), an estimate of p Y |X =x (y), and we let ρx (y, S) = L(y, S) px (y).”

  • The authors state this as an assumption.

    The loss function has the simple form L(y,S)=L_y 1{y not in S} for constants L_y.

    “Suppose our loss function has the simple form L(y, S) = L y 1 {y S} , for constants L y .”

  • The authors state this as an assumption.

    The loss takes the form L(y;S)=∫_{z∈S^c} ℓ(y,z)dμ(z) for some nonnegative ℓ and a finite measure μ.

    “Suppose our loss takes the form L(y; S) = z ∈S c ℓ(y, z)dμ (z), for some nonnegative ℓ and a finite measure μ.”

  • The authors state this as an assumption.

    In the ranking setting, we have an i.i.d. sequence of points (X1,Y1),...,(Xm,Ym), where Y∈{1,...,k}.

    “We assume we have an i.i.d.sequence of points, (X 1 , Y 1 ), . . ., (X m , Y m ), where Y ∈ {1, . . ., k }.”

  • The authors state this as an assumption.

    In the ranking setting, the family of set-valued predictors satisfies the monotonicity property λ<λ' implies Tλ ⊂ Tλ'.

    “We assume that we have a family of such predictors satsifying the following monotonicity property: λ < λ =⇒ T λ (x 1 , x 2 ) ⊂ T λ (x 1 , x 2 ).(13)”

  • The authors state this as an assumption.

    In the metric learning setting, we have an i.i.d. sequence of points (X1,Y1),...,(Xm,Ym), with Y={1,...,k}.

    “We next consider the problem of supervised metric learning, where we have an i.i.d.sequence of points (X 1 , Y 1 ), . . ., (X m , Y m ), with Y = {1, . . ., k }.”

  • The authors state this as an assumption.

    In the metric learning setting, the family of set-valued metrics has the monotonicity property in Equation (13).

    “We assume that we have a family of such set-valued metrics that have the monotonicity property in Equation (13).”

  • The authors state this as an assumption.

    In the metric learning setting, the loss function is bounded by 1.

    “In the setting above, suppose the loss function is bounded by 1.”

  • The authors state this as an assumption.

    In the ranking setting, the loss function is bounded by one.

    “Consider the setting above with any loss function bounded by one.”

  • The authors state this as an assumption.

    The family of sets Tλ is such that the minimal element in the score definition exists with probability one.

    “where we assume that the family of sets T λ is such that the minimal element exists with probability one.”

  • The paper relies on this without support.

    The general case where Y is not binary has not been explicitly dealt with in prior work.

    “To the best of our knowledge, the general case where Y 2 Y has not been explicitly dealt with, so we record this mild generalization here.”
24 of 24

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

  • Protein distance matrices cannot have strictly positive diagonals

    Minor

    The label space requires positive elements throughout, but each diagonal entry represents the distance from a residue to itself, which is zero.

  • Polyp examples disagree on the number of polyps per image

    Minor

    Section 5.4 says all 20 selected images contain at least two polyps, whereas the Figure 12 caption says its top two rows contain a single polyp per image.

2 of 2

Citations

Cites

Flagged first, then by citations

Research works printed but not linked: 22

  1. Angelopoulos Anastasios Nikolas, International Conference on Learning Representations (ICLR).
  2. 10.5555/3454287.3455291 · DOI
  3. Cauchois Maxime, 2020, Duchi
  4. 10.5555/2354409.2355033 · DOI
  5. Grycko Eugen, Information and Classification
  6. Gupta Chirag, 2020, Ramdas
  7. Izbicki Rafael, 2019, Stern
  8. Lei Lihua, 2020, Candès
  9. Lin Tsung-Yi, European Conference on Computer Vision. Springer, 740–755
  10. Madry Aleksander, 2018, International Conference on Learning Representations (ICLR).
  11. 10.5555/1148466.1148472 · DOI
  12. Maurer Andreas, 2009, Conference on Learning Theory (COLT).
  13. Park Sangdon, 2020, International Conference on Learning Representations (ICLR).
  14. Park Sangdon, 2021, International Conference on Learning Representations (ICLR).
  15. 10.5555/3454287.3454605 · DOI
  16. Romano Yaniv, 2020, International Conference on Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (Eds.), 33
  17. Senior Andrew W., 2020, et al
  18. 10.5555/3454287.3454514 · DOI
  19. Vovk Vladimir, 2012, Asian Conference on Machine Learning, 25
  20. 10.5555/645528.657641 · DOI
  21. 10.5555/1062391 · DOI
  22. Vovk Vladimir, 2020, Ninth Symposium on Conformal and Probabilistic Prediction and Applications, Alexander Gammerman, Vladimir Vovk, Zhiyuan Luo, Evgueni Smirnov, and Giovanni Cherubin (Eds.), 128

Cited by

Sorted by citations

See all 147

Related

See all

Metadata

Authors
Bates, S., Angelopoulos, A., Lei, L., Malik, J., & Jordan, M.
Affiliations
  • University of California, Berkeley (US)
  • Stanford University (US)
ORCID
Venue
Journal of the ACM
Publisher
Association for Computing Machinery (ACM)
Published
2021-09-30
Volume
68
Issue
6
Pages
1-34
ISSN
  • 0004-5411 (ISSN-L)
  • 1557-735X
DOI
10.1145/3478535
OpenAlex
W3118640283
Semantic Scholar
e343f1517f038da090a78159363d14cdad5ddc35
Cited by
144
References
63
Citations by year
2026: 48 · 2025: 27 · 2024: 25 · 2023: 21 · 2022: 8 · 2021: 14
FWCI
5.90
Type
journal article
Language
en
Open access
Licence
Locations
  • Journal of the ACM (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation Graduate Research Fellowship Program and a Berkeley Fellowship
  • Army Research Office (W911NF-16-1-0368)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Adversarial Robustness in Machine Learning
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Data Classification
Keywords
prediction sets, uncertainty quantification, finite-sample guarantees, risk control, multi-label classification, hierarchical classification, image segmentation, protein structure prediction, metric learning

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

A language model drew the claims from the paper on 2026-10-22, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-10-22 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review