Distribution-free, Risk-controlling Prediction Sets

The exact concentration results are hopelessly conservative with only 35 calibration points.

“due to the small sample size (35 calibration and 36 test points), we only report results using the CLT bound, because the exact concentration results are hopelessly conservative with only 35 calibration points.”

In the protein structure prediction experiment, the CLT bound nearly controls the risk.

“Figure 15 shows the quantitative performance of the CLT, which nearly controls the risk.”

The PU bound has valid coverage in the unbounded settings considered.

“By contrast, the PU bound has valid coverage in these settings.”

In the MS COCO multi-label classification experiment, the conformal baseline returns larger prediction sets.

“In Figure 8, we find that the conformal baseline returns larger prediction sets.”

• cites [12]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

The CLT does not always have correct coverage, especially when the true mean is small, unless the sample size is large.

“First, we observe that the CLT does not always have correct coverage, especially when the true mean is small, unless the sample size is large.”

• AssumptionThe authors state this as an assumption: The loss is bounded above by one.

The CLT bound does not achieve the target coverage in most cases.

“The CLT bound is excluded in (b), because it does not achieve the target coverage in most of the cases.”

• Also stated in: § E ADAPTIVE SCORE RENORMALIZATION FOR POLYP SEGMENTATION · plain

  “The CLT bound is excluded in (b) because it does not achieve the target coverage in most of the cases.”

• Also stated in: § E ADAPTIVE SCORE RENORMALIZATION FOR POLYP SEGMENTATION · plain

  “The CLT bound is excluded in (b) because it does not achieve the target coverage in most of the cases.”

The WSR bound is not uniformly better than the HB bound.

“These results show that the WSR bound is not uniformly better than the HB bound, although it is still the best all-around choice for bounded losses.”

The HB bound is more likely to be tighter than the WSR bound, especially when the mean μ or the level δ is small.

“The HB bound is more likely to be tighter than the WSR bound, especially when the mean μ or the level δ is small.”

Generating set-valued predictions from a black-box predictor can control the expected loss on future test points at a user-specified level.

“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.”

• AssumptionThe authors state this as an assumption: For each λ, a pointwise upper confidence bound R+(λ) for R(λ) is available such that P(R(λ) ≤ R+(λ)) ≥ 1-δ.
• AssumptionThe authors state this as an assumption: The loss function satisfies the nesting property: S ⊂ S' ⇒ L(y,S) ≥ L(y,S').
• AssumptionThe authors state this as an assumption: The collection of set-valued predictors {Tλ} is nested: λ1 < λ2 ⇒ Tλ1(x) ⊂ Tλ2(x).
• AssumptionThe authors state this as an assumption: The data (Xi, Yi) are i.i.d.

The framework enables simple, distribution-free, rigorous error control for many tasks.

“This framework enables simple, distribution-free, rigorous error control for many tasks”

The approach provides explicit finite-sample guarantees for any dataset by using a holdout set to calibrate the size of the prediction sets.

“Our approach provides explicit finite-sample guarantees for any dataset by using a holdout set to calibrate the size of the prediction sets.”

• AssumptionThe authors state this as an assumption: The data (Xi, Yi) are i.i.d.

In the generalized setting, any set-valued predictor T with R(T) ≤ R(Tλ) has expected size at least that of Tλ given by Equation (11).

“Theorem 8 (Optimality of Set Predictors, Generalized Form).In the setting above, let T : X → Y be any set-valued predictor such that R(T ) ≤ R(T λ ), where T λ is given by Equation (11). Then, E[|T λ (X )|] ≤ E[|T (X )|].”

• AssumptionThe 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 μ.

When no finite-sample result is available, UCB calibration can still be used to get prediction sets with asymptotic validity.

“When no finite-sample result is available, we can still use the UCB calibration procedure to get prediction sets with asymptotic validity.”

For settings for which no finite-sample bound is available, an asymptotically valid upper confidence bound can be given.

“In addition, for settings for which no finite-sample bound is available, we give an asymptotically valid upper confidence bound.”

The greedy procedure of Algorithm 1 is approximately optimal for a large class of useful loss functions.

“The general greedy procedure is computationally convenient; moreover, it is approximately optimal for a large class of useful loss functions, as we will prove soon.”

The strong performance of the CLT in the small-sample regime suggests that the methodology can be applied to problems even with small calibration sets.

“The strong performance of the CLT in this small-sample regime is encouraging and suggests that our methodology can be applied to problems even with small calibration sets.”

In the setting of Theorem 1, if the loss is bounded by one, T_λsHoef is a (α,δ)-RCPS.

“Then, T λsHoef is a (α, δ )-RCPS.”

• AssumptionThe authors state this as an assumption: The loss is bounded above by one.

RCPS can incorporate less brittle loss functions, such as the false negative rate in Equation (12).

“By contrast, the RCPS method can incorporate less brittle loss functions, such as the false negative rate in Equation (12).”

The Pinelis-Utev inequality gives a tail bound for nonnegative random variables with bounded coefficient of variation.

“For nonnegative random variables with bounded coeffecient of variation, the Pinelis-Utev inequality gives a tail bound as follows:”

• cites [42]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Risk-controlling prediction sets (RCPS) produce prediction sets that provide distribution-free, finite-sample control of a general loss.

“We call our proposed technique risk-controlling prediction sets (RCPS).The idea is to produce prediction sets that provide distribution-free, finite-sample control of a general loss.”

Upper confidence bound calibration holds for any monotone R(λ) with a pointwise upper confidence bound R+(λ).

“Upper confidence bound calibration holds in more generality than the concrete instantiation above.The result holds for any monotone R(λ) with a pointwise upper confidence bound R+ (λ).”

Bentkus inequality states that for bounded loss, P(R(λ) ≤ t) ≤ e P(Binom(n, R(λ)) ≤ nt).

“P ( R(λ) ≤ t ) ≤ eP (Binom(n, R(λ)) ≤ nt ) ,”

• cites [5]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• AssumptionThe authors state this as an assumption: The loss is bounded above by one.

The central contribution of this work is a procedure to calibrate prediction sets to have finite-sample control of any loss satisfying a certain monotonicity requirement.

“The central contribution of this work is a procedure to calibrate prediction sets to have finitesample control of any loss satisfying a certain monotonicity requirement.”

A nontrivial upper confidence bound can be derived if the coefficient of variation c_v(λ) is known.

“This result shows that a nontrivial upper confidence bound can be derived if c v (λ) is known.”

• AssumptionThe authors state this as an assumption: For each λ, c_v(λ) ≤ c_v for some constant c_v.

If the loss L(Y, T_λ(X)) has a finite second moment for each λ, the CLT yields an asymptotic upper confidence bound for R(λ).

“Suppose the loss L(Y , T λ (X )) has a finite second moment for each λ.Then, since the losses for each λ are i.i.d., we can apply the CLT to get”

• AssumptionThe authors state this as an assumption: The loss L(Y, Tλ(X)) has a finite second moment for each λ.

If the exact conditional density p_{Y|X=x}(y) and exact ρx(y,S) are known, the prediction sets produced by Algorithm 1 have the smallest average size among all procedures that control the risk.

“Now, imagine that we know the exact conditional probability density, p Y |X =x (y), and therefore the exact ρ x (y, S).The prediction sets produced by Algorithm 1 then have the smallest average size among all procedure that control the risk, as stated next.”

• Also stated in: § 4.2 Optimality Properties of the Greedy Procedure · plain

  “Theorem 7 (Optimality of the Greedy Sets).In the setting above, let T : X → Y be any set-valued predictor such that R(T ) ≤ R(T λ ), where T λ is given by Algorithm 1.Then, E[|T λ (X )|] ≤ E[|T (X )|].”

• AssumptionThe 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.

The paper shows how to take any standard (non-set-valued) predictor and turn it into a set-valued predictor that works well with the calibration procedure.

“but we also show how to take any standard (non-setvalued) predictor and turn it into a set-valued predictor that works well with our calibration procedure.”

Under the loss L(y,S)=L_y 1{y not in S}, the sets returned by Algorithm 1 have the form Tλ(x)={y: ρx(y,∅) ≥ ζ(λ)}.

“In this case, the sets returned by Algorithm 1 have the form T λ (x ) = {y : ρx (y , ∅) ≥ ζ (λ)}.”

• AssumptionThe 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.

The Waudby-Smith-Ramdas bound R+_WSR(λ) is a (1-δ) upper confidence bound for R(λ).

“Then, R + WSR (λ) is a (1δ ) upper confidence bound for R(λ).”

• cites [59]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Hoeffding's inequality (tighter version) states that for bounded loss, for any t < R(λ), P(R(λ) ≤ t) ≤ exp{-n h1(t; R(λ))}.

“P R(λ) ≤ t ≤ exp{-nh 1 (t; R(λ))},”

• cites [26]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• AssumptionThe authors state this as an assumption: The loss is bounded above by one.

UCB calibration is always guaranteed to control the risk by Theorem 1.

“While UCB calibration is always guaranteed to control the risk by Theorem 1”

Under the conditions of Theorem 1, UCB calibration yields a set-valued predictor Tλ that is a (α, δ)-RCPS.

“That is, T λ is a (α, δ )-RCPS.”

• AssumptionThe authors state this as an assumption: For each λ, a pointwise upper confidence bound R+(λ) for R(λ) is available such that P(R(λ) ≤ R+(λ)) ≥ 1-δ.
• AssumptionThe authors state this as an assumption: The loss function satisfies the nesting property: S ⊂ S' ⇒ L(y,S) ≥ L(y,S').
• AssumptionThe authors state this as an assumption: The collection of set-valued predictors {Tλ} is nested: λ1 < λ2 ⇒ Tλ1(x) ⊂ Tλ2(x).
• AssumptionThe authors state this as an assumption: R(λ) is continuous.
• AssumptionThe authors state this as an assumption: The data (Xi, Yi) are i.i.d.

In the setting of Theorem 1, if L(Y,T_λ(X)) has finite second moment for each λ, then limsup P(R(T_λCLT)>α) ≤ δ.

“lim sup n→∞ P (R(T λCLT ) > α ) ≤ δ .”

• AssumptionThe authors state this as an assumption: The loss L(Y, Tλ(X)) has a finite second moment for each λ.

For losses of the form L(y;S)=∫_{z∈S^c} l(y,z)dμ(z), the optimal Tλ is given by Tλ(x)={z: E[l(Y;z)|X=x] ≥ -λ}.

“Then, the optimal T λ is given by T λ (x ) = {z : E[ℓ(Y ; z) | X = x] ≥ -λ},(11)”

• AssumptionThe 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 μ.

UCB calibration gives an RCPS even if the data used to fit the initial predictive model comes from a different distribution, provided calibration and test data come from the same distribution.

“The above result also implies that UCB calibration gives an RCPS even if the data used to fit the initial preditive model comes from a different distribution.The only requirement is that the calibration data and the test data come from the same distribution.”

• AssumptionThe authors state this as an assumption: The calibration data and test data come from the same distribution.

Upper confidence bounds as in Equation (3) can be developed under different conditions on the loss function, allowing UCB calibration for a variety of prediction tasks.

“In this section, we develop upper confidence bounds as in Equation (3) under different conditions on the loss function, which will allow us to use the UCB calibration procedure for a variety of prediction tasks.”

In summary, 1,000 to 10,000 calibration points are sufficient to generate prediction sets that are not too conservative, i.e., sets that have risk that are not far below the desired level α.

“In summary, 1,000 to 10,000 calibration points are sufficient to generate prediction sets that are not too conservative, i.e., sets that have risk that are not far below the desired level α.”

In the setting of Theorem 1, if the loss is bounded by 1, T_λWSR is a (α,δ)-RCPS.

“Then, T λWSR is a (α, δ )-RCPS.”

• AssumptionThe authors state this as an assumption: The loss is bounded above by one.

The calibration procedure applies to any set-valued predictor.

“The calibration procedure applies to any set-valued predictor”

The procedure returns sets that are guaranteed to keep average loss (risk) on future data below a user-specified level, under a set of assumptions that the paper makes explicit.

“Our procedure returns sets that are guaranteed to keep average loss (risk) on future data below a user-specified level, under a set of assumptions that we make explicit.”

• AssumptionThe authors state this as an assumption: For each λ, a pointwise upper confidence bound R+(λ) for R(λ) is available such that P(R(λ) ≤ R+(λ)) ≥ 1-δ.
• AssumptionThe authors state this as an assumption: The loss function satisfies the nesting property: S ⊂ S' ⇒ L(y,S) ≥ L(y,S').
• AssumptionThe authors state this as an assumption: The collection of set-valued predictors {Tλ} is nested: λ1 < λ2 ⇒ Tλ1(x) ⊂ Tλ2(x).
• AssumptionThe authors state this as an assumption: R(λ) is continuous.
• AssumptionThe authors state this as an assumption: The calibration data and test data come from the same distribution.
• AssumptionThe authors state this as an assumption: The data (Xi, Yi) are i.i.d.

If the calibration set is too small, the sets may be larger than necessary.

“if the calibration set is too small, then the sets may be larger than necessary.”

When the variance of L(Y_i, T_λ(X_i)) is small, the tail probability bound can be much tighter than that given by the Hoeffding-Bentkus bound.

“In general, when Var(L(Y i , T λ (X i ))) is small, the tail probability bound can be much tighter than that given by the Hoeffding-Bentkus bound.”

The proposed method calibrates any set-valued predictor so it is guaranteed to have risk below a user-specified level, i.e., so it satisfies Definition 1.

“This section introduces our proposed method to calibrate any set-valued predictor so it is guaranteed to have risk below a user-specified level, i.e., so it satisfies Definition 1.”

The current work expands the notion of tolerance regions to apply to a wider class of losses for set-valued predictors.

“In the current work, we expand the notion of tolerance regions to apply to a wider class of losses for set-valued predictors.”

For non-binary loss functions, the Hoeffding-Bentkus bound can be very loose because it does not adapt to the variance of L(Y_i, T_λ(X_i)).

“for non-binary loss functions, it can be very loose because it does not adapt to the variance of L(Y i , T λ (X i )).”

It is impossible to derive a nontrivial upper confidence bound for the mean of nonnegative random variables in finite samples without additional restrictions.

“Based on the well-known results of Reference [2], we can show that it is impossible to derive a nontrivial upper confidence bound for the mean of nonnegative random variables in finite samples without any other restrictions”

• cites [2]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

A method for modifying a black-box predictor to return a set of plausible responses limits the frequency of costly errors to a level chosen by the user.

“We introduce a method for modifying a black-box predictor to return a set of plausible responses that limits the frequency of costly errors to a level chosen by the user.”

A tail probability bound can be inverted to yield an upper confidence bound.

“This result shows how a tail probability bound can be inverted to yield an upper confidence bound.”

T_λCLT is an asymptotic RCPS.

“Then, T λCLT is an asymptotic RCPS, as stated next.”

• AssumptionThe authors state this as an assumption: The loss L(Y, Tλ(X)) has a finite second moment for each λ.

In the setting of Theorem 1, if the loss is bounded by one, T_λHB is a (α,δ)-RCPS.

“Then, T λHB is a (α, δ )-RCPS.”

• AssumptionThe authors state this as an assumption: The loss is bounded above by one.

In the setting of Theorem 1, if the loss takes values in {0,1}, then Tλbin is an (α,δ)-RCPS.

“Theorem B.1 (RCPS for Binary Variables).In the setting of Theorem 1, assume additionally that the loss takes values in {0,1}.Then, T λbin is a (α, δ )-RCPS.”

In the special case where the loss function takes values only in {0,1}, it is possible to select λ to control E[R(Tλ)] below a desired level α.

“In the special case where the the loss function L takes values only in {0, 1}, it is also possible to select λ to control the quantity E[R(T λ )] below a desired level α.”

In the binary loss case, a tight upper confidence bound can be obtained by extracting the relevant quantile of a binomial distribution.

“In this case, we can give a tight upper confidence bound by simple extracting the relevant quantile of a binomial distribution; see Reference [9] for other exact or approximate upper confidence bounds.”

• cites [9]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

The same tail probability bounds hold for R_id(λ) and therefore for R(λ) by Equation (17).

“Therefore, the same tail probability bounds hold for R id (λ) and thus R(λ) by Equation (17).”

RCPS apply to any existing model without retraining.

“Since they apply to any existing model without retraining, they are straightforward to use in many situations.”

UCB calibration tunes λ so we abstain from as few pairs as possible while guaranteeing that the probability of making a mistake on inputs for which we do not abstain is below the user-specified level α.

“The UCB calibration tunes λ so we abstain from as few pairs as possible, while guaranteeing that the probability of making a mistake on inputs for which we do not abstain is below the user-specified level α.”

For the class of all distributions supported on [0,∞) with finite mean, any function μ+ of n i.i.d. samples that is a (1−δ) upper confidence bound for the mean for every n and every such distribution must equal infinity with probability at least 1−δ.

“Proposition A.1 (Impossibility of Valid UCB for Unbounded Losses in Finite Samples).Let F be the class of all distributions supported on [0, ∞) with finite mean, and μ (F ) be the mean of the distribution F .Let μ+ be any function of Z 1 , . . ., Z n i.i.d.”

• cites [2]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

RCPS allow the user to automatically return valid instance-wise uncertainty estimates for many prediction tasks.

“To summarize, in contrast to the standard train/validation/test split paradigm that only estimates global uncertainty (in the form of overall prediction accuracy), RCPS allow the user to automatically return valid instance-wise uncertainty estimates for many prediction tasks.”

Concentration is a more general tool and can apply to a wider range of problems, such as uncertainty quantification for ranking.

“Concentration is a more general tool and can apply to a wider range of problems, such as the uncertainty quantification for ranking presented in Section 6.1.”

By Proposition 2, a (1−δ) upper confidence bound for R(λ) is R+bin(λ) = sup{R : g_bin(R(λ); R) ≥ δ}.

“By Proposition 2, we obtain a (1δ ) upper confidence bound for R(λ) as R + bin (λ) = sup R : д bin ( R(λ); R) ≥ δ .”

In the special case where ρx(y,S) does not depend on S, Tλ(x) from Algorithm 1 consists of the y ∈ Y whose conditional risk density exceeds a threshold ζ.

“In the special case where ρx (y, S) does not depend on S, T λ (x ) from Algorithm 1 is made up of the y ∈ Y whose conditional risk density exceeds a threshold ζ .”

In the ranking setting with any loss bounded by one, with probability at least 1-δ, R(Tλ) ≤ α.

“Theorem 9 (RCPS for Ranking).Consider the setting above with any loss function bounded by one.Then, with probability at least 1δ , we have R(T λ ) ≤ α.”

• AssumptionThe 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}.
• AssumptionThe authors state this as an assumption: In the ranking setting, the family of set-valued predictors satisfies the monotonicity property λ<λ' implies Tλ ⊂ Tλ'.
• AssumptionThe authors state this as an assumption: In the ranking setting, the loss function is bounded by one.

In the metric learning setting, if the loss function is bounded by 1, then with probability at least 1-δ, R(Tλ) ≤ α.

“Theorem 10 (RCPS for Metric Learning).In the setting above, suppose the loss function is bounded by 1.Then, with probability at least 1δ , we have R(T λ ) ≤ α.”

• AssumptionThe 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}.
• AssumptionThe authors state this as an assumption: In the metric learning setting, the family of set-valued metrics has the monotonicity property in Equation (13).
• AssumptionThe authors state this as an assumption: In the metric learning setting, the loss function is bounded by 1.

In the conformal calibration setting, the selected threshold λ yields E[R(Tλ)] ≤ α.

“Proposition C.1 (Validity of Conformal Calibration).In the setting above,”

• Also stated in: § C CONFORMAL CALIBRATION · plain

  “E[R(T λ )] ≤ α .”

• cites [46]Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• AssumptionThe 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.

For binary loss, P(R(λ) ≤ t) equals P(Binom(n, R(λ)) ≤ nt).

“P ( R(λ) ≤ t ) = P (Binom(n, R(λ)) ≤ nt ),”