2208/2208.02814.md

Title: Conformal Risk Control

URL Source: https://arxiv.org/html/2208.02814

Markdown Content: Back to arXiv

This is experimental HTML to improve accessibility. We invite you to report rendering errors. Use Alt+Y to toggle on accessible reporting links and Alt+Shift+Y to toggle off. Learn more about this project and help improve conversions.

Why HTML? Report Issue Back to Abstract Download PDF Abstract 1Introduction 2Theory 3Examples 4Extensions 5Conclusion

HTML conversions sometimes display errors due to content that did not convert correctly from the source. This paper uses the following packages that are not yet supported by the HTML conversion tool. Feedback on these issues are not necessary; they are known and are being worked on.

failed: scalerel failed: mdframed failed: biblatex failed: apptools

Authors: achieve the best HTML results from your LaTeX submissions by following these best practices.

License: arXiv.org perpetual non-exclusive license arXiv:2208.02814v4 [stat.ME] 13 Jun 2025 \addbibresource

bibliography.bib \AtAppendix \AtAppendix

Conformal Risk Control Anastasios N. Angelopoulos1, Stephen Bates1, Adam Fisch2, Lihua Lei3, and Tal Schuster4 ( 1University of California, Berkeley 2Massachusetts Institute of Technology 3Stanford University 4Google Research ) Abstract

We extend conformal prediction to control the expected value of any monotone loss function. The algorithm generalizes split conformal prediction together with its coverage guarantee. Like conformal prediction, the conformal risk control procedure is tight up to an 𝒪 ⁢ ( 1 / 𝑛 ) factor. We also introduce extensions of the idea to distribution shift, quantile risk control, multiple and adversarial risk control, and expectations of U-statistics. Worked examples from computer vision and natural language processing demonstrate the usage of our algorithm to bound the false negative rate, graph distance, and token-level F1-score.

1Introduction

We seek to endow some pre-trained machine learning model with guarantees on its performance as to ensure its safe deployment. Suppose we have a base model 𝑓 that is a function mapping inputs 𝑥 ∈ 𝒳 to values in some other space, such as a probability distribution over classes. Our job is to design a procedure that takes the output of 𝑓 and post-processes it into quantities with desirable statistical guarantees.

Split conformal prediction \citepvovk2005algorithmic,papadopoulos2002inductive, which we will henceforth refer to simply as “conformal prediction”, has been useful in areas such as computer vision \citepangelopoulos2020sets and natural language processing \citepfisch2020efficient to provide such a guarantee. By measuring the model’s performance on a calibration dataset { ( 𝑋 𝑖 , 𝑌 𝑖 ) } 𝑖

1 𝑛 of feature-response pairs, conformal prediction post-processes the model to construct prediction sets that bound the miscoverage,

ℙ ⁢ ( 𝑌 𝑛 + 1 ∉ 𝒞 ⁢ ( 𝑋 𝑛 + 1 ) ) ≤ 𝛼 ,

(1)

where ( 𝑋 𝑛 + 1 , 𝑌 𝑛 + 1 ) is a new test point, 𝛼 is a user-specified error rate (e.g., 10%), and 𝒞 is a function of the model and calibration data that outputs a prediction set. Note that 𝒞 is formed using the first 𝑛 data points, and the probability in (1) is over the randomness in all 𝑛 + 1 data points (i.e., the draw of both the calibration and test points).

In this work, we extend conformal prediction to prediction tasks where the natural notion of error is not simply miscoverage. In particular, our main result is that a generalization of conformal prediction provides guarantees of the form

𝔼 ⁢ [ ℓ ⁢ ( 𝒞 ⁢ ( 𝑋 𝑛 + 1 ) , 𝑌 𝑛 + 1 ) ] ≤ 𝛼 ,

(2)

for any bounded loss function ℓ that shrinks as 𝒞 ⁢ ( 𝑋 𝑛 + 1 ) grows. We call this a conformal risk control guarantee. Note that (2) recovers the conformal miscoverage guarantee in (1) when using the miscoverage loss, ℓ ⁢ ( 𝒞 ⁢ ( 𝑋 𝑛 + 1 ) , 𝑌 𝑛 + 1 )

𝟙 ⁢ { 𝑌 𝑛 + 1 ∉ 𝒞 ⁢ ( 𝑋 𝑛 + 1 ) } . However, our algorithm also extends conformal prediction to situations where other loss functions, such as the false negative rate (FNR) or F1-score, are more appropriate.

As an example, consider multilabel classification, where the 𝑌 𝑖 ⊆ { 1 , … , 𝐾 } are sets comprising a subset of 𝐾 classes. Given a trained multilabel classifier 𝑓 : 𝒳 → [ 0 , 1 ] 𝐾 , we want to output sets that include a large fraction of the true classes in 𝑌 𝑖 . To that end, we post-process the model’s raw outputs into the set of classes with sufficiently high scores, 𝒞 𝜆 ⁢ ( 𝑥 )

{ 𝑘 : 𝑓 ⁢ ( 𝑋 ) 𝑘 ≥ 1 − 𝜆 } . Note that as the threshold 𝜆 grows, we include more classes in 𝒞 𝜆 ⁢ ( 𝑥 ) —i.e., it becomes more conservative. In this case, conformal risk control finds a threshold value 𝜆 ^ that controls the fraction of missed classes, i.e., the expected value of ℓ ⁢ ( 𝒞 𝜆 ^ ⁢ ( 𝑋 𝑛 + 1 ) , 𝑌 𝑛 + 1 )

1 − | 𝑌 𝑛 + 1 ∩ 𝒞 𝜆 ⁢ ( 𝑋 𝑛 + 1 ) | / | 𝑌 𝑛 + 1 | . Setting 𝛼

0.1 would ensure that our algorithm produces sets 𝒞 𝜆 ^ ⁢ ( 𝑋 𝑛 + 1 ) containing ≥ 90 % of the true classes in 𝑌 𝑛 + 1 on average.

1.1Algorithm and preview of main results

Formally, we will consider post-processing the predictions of the model 𝑓 to create a function 𝒞 𝜆 ⁢ ( ⋅ ) . The function has a parameter 𝜆 that encodes its level of conservativeness: larger 𝜆 values yield more conservative outputs (e.g., larger prediction sets). To measure the quality of the output of 𝒞 𝜆 , we consider a loss function ℓ ⁢ ( 𝒞 𝜆 ⁢ ( 𝑥 ) , 𝑦 ) ∈ ( − ∞ , 𝐵 ] for some 𝐵 < ∞ . We require the loss function to be non-increasing as a function of 𝜆 . Our goal is to choose 𝜆 ^ based on the observed data { ( 𝑋 𝑖 , 𝑌 𝑖 ) } 𝑖

1 𝑛 so that risk control as in (2) holds.

We now rewrite this same task in a more notationally convenient and abstract form. Consider an exchangeable collection of non-increasing, random functions 𝐿 𝑖 : Λ → ( − ∞ , 𝐵 ] , 𝑖

1 , … , 𝑛 + 1 . Throughout the paper, we assume 𝜆 max

△ sup Λ ∈ Λ . We seek to use the first 𝑛 functions to choose a value of the parameter, 𝜆 ^ , in such a way that the risk on the unseen function is controlled:

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ] ≤ 𝛼 .

(3)

We are primarily motivated by the case where 𝐿 𝑖 ⁢ ( 𝜆 )

ℓ ⁢ ( 𝒞 𝜆 ⁢ ( 𝑋 𝑖 ) , 𝑌 𝑖 ) , in which case the guarantee in (3) coincides with risk control as in (2).

Now we describe the algorithm. Let 𝑅 ^ 𝑛 ⁢ ( 𝜆 )

( 𝐿 1 ⁢ ( 𝜆 ) + … + 𝐿 𝑛 ⁢ ( 𝜆 ) ) / 𝑛 . Given any desired risk level upper bound 𝛼 ∈ ( − ∞ , 𝐵 ) , define

𝜆 ^

inf { 𝜆 : 𝑛 𝑛 + 1 ⁢ 𝑅 ^ 𝑛 ⁢ ( 𝜆 ) + 𝐵 𝑛 + 1 ≤ 𝛼 } .

(4)

When the set is empty, we define 𝜆 ^

𝜆 max . Our proposed conformal risk control algorithm is to deploy 𝜆 ^ on the forthcoming test point. Our main result is that this algorithm satisfies (3). When the 𝐿 𝑖 are i.i.d. from a continuous distribution, the algorithm satisfies a lower bound saying it is not too conservative,

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ] ≥ 𝛼 − 2 ⁢ 𝐵 𝑛 + 1 .

(5)

We show the reduction from conformal risk control to conformal prediction in Section 2.3. Furthermore, if the risk is non-monotone, then this algorithm does not control the risk; we discuss this in Section 2.4. Finally, we provide both practical examples using real-world data and several theoretical extensions of our procedure in Sections 3 and 4, respectively.

1.2Related work

Conformal prediction was developed by Vladimir Vovk and collaborators beginning in the late 1990s \citepvovk1999machine, vovk2005algorithmic, and has recently become a popular uncertainty estimation tool in the machine learning community, due to its favorable model-agnostic, distribution-free, finite-sample guarantees. See [angelopoulos-gentle] for a modern introduction to the area or [shafer2008tutorial] for a more classical alternative. As previously discussed, in this paper we primarily build on split conformal prediction \citeppapadopoulos2002inductive; statistical properties of this algorithm including the coverage upper bound were studied in [lei2018distribution]. Recently there have been many extensions of the conformal algorithm, mainly targeting deviations from exchangeability \citeptibshirani2019conformal,gibbs2021adaptive,barber2022conformal,fannjiang2022conformal and improved conditional coverage \citepbarber2019limits,romano2019conformalized,guan2020conformal,romano2020classification,angelopoulos2020sets. Most relevant to us is recent work on risk control in high probability \citepvovk2012conditional, bates2021distribution,angelopoulos2021learn and its applications \citep[][inter alia]Park2020PAC,fisch2022conformal, schuster2021consistent, schuster2022confident, sankaranarayanan2022semantic, angelopoulos2022image, angelopoulos2022recommendation. Though these works closely relate to ours in terms of motivation, the algorithm presented herein differs greatly: it has a guarantee in expectation, and neither the algorithm nor its analysis share much technical similarity with these previous works.

To elaborate on the difference between our work and previous literature, first consider conformal prediction. The purpose of conformal prediction is to provide coverage guarantees of the form in (1). The guarantee available through conformal risk control, (3), strictly subsumes that of conformal prediction; it is generally impossible to recast risk control as coverage control. As a second question, one might ask whether (3) can be achieved through standard statistical machinery, such as uniform concentration inequalities. Though it is possible to integrate a uniform concentration inequality to get a bound in expectation, this strategy tends to be excessively loose both in theory and in practice (see, e.g., the bound of  [anthony1993result]). The technique herein avoids these complications; it is simpler than concentration-based approaches, practical to implement, and tight up to a factor of 𝒪 ⁢ ( 1 / 𝑛 ) , which is comparatively faster than concentration would allow. Finally, herein we target distribution-free finite-sample control of (3), but as a side-note it is also worth pointing the reader to the rich literature on functional central limit theorems \citepdavidson2000functional, which are another way of estimating risk functions.

2Theory

In this section, we establish the core theoretical properties of conformal risk control. All proofs, unless otherwise specified, are deferred to Appendix B.

2.1Risk control

We first show that the proposed algorithm leads to risk control when the loss is monotone.

Theorem 2.1.

Assume that 𝐿 𝑖 ⁢ ( 𝜆 ) is non-increasing in 𝜆 , right-continuous, and

𝐿 𝑖 ⁢ ( 𝜆 max ) ≤ 𝛼 , sup 𝜆 𝐿 𝑖 ⁢ ( 𝜆 ) ≤ 𝐵 < ∞ ⁢  almost surely .

(6)

Then

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ] ≤ 𝛼 .

(7) Proof.

Let 𝑅 ^ 𝑛 + 1 ⁢ ( 𝜆 )

( 𝐿 1 ⁢ ( 𝜆 ) + … + 𝐿 𝑛 + 1 ⁢ ( 𝜆 ) ) / ( 𝑛 + 1 ) and

𝜆 ^ ′

inf { 𝜆 ∈ Λ : 𝑅 ^ 𝑛 + 1 ⁢ ( 𝜆 ) ≤ 𝛼 } .

(8)

Since inf 𝜆 𝐿 𝑖 ⁢ ( 𝜆 )

𝐿 𝑖 ⁢ ( 𝜆 max ) ≤ 𝛼 , 𝜆 ^ ′ is well-defined almost surely. Since 𝐿 𝑛 + 1 ⁢ ( 𝜆 ) ≤ 𝐵 , we know 𝑅 ^ 𝑛 + 1 ⁢ ( 𝜆 )

𝑛 𝑛 + 1 ⁢ 𝑅 ^ 𝑛 ⁢ ( 𝜆 ) + 𝐿 𝑛 + 1 ⁢ ( 𝜆 ) 𝑛 + 1 ≤ 𝑛 𝑛 + 1 ⁢ 𝑅 ^ 𝑛 ⁢ ( 𝜆 ) + 𝐵 𝑛 + 1 . Thus,

𝑛 𝑛 + 1 ⁢ 𝑅 ^ 𝑛 ⁢ ( 𝜆 ) + 𝐵 𝑛 + 1 ≤ 𝛼 ⟹ 𝑅 ^ 𝑛 + 1 ⁢ ( 𝜆 ) ≤ 𝛼 .

(9)

This implies 𝜆 ^ ′ ≤ 𝜆 ^ when the LHS holds for some 𝜆 ∈ Λ . When the LHS is above 𝛼 for all 𝜆 ∈ Λ , by definition, 𝜆 ^

𝜆 max ≥ 𝜆 ^ ′ . Thus, 𝜆 ^ ′ ≤ 𝜆 ^ almost surely. Since 𝐿 𝑖 ⁢ ( 𝜆 ) is non-increasing in 𝜆 ,

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ] ≤ 𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ′ ) ] .

(10)

Let 𝐸 be the multiset of loss functions { 𝐿 1 , … , 𝐿 𝑛 + 1 } . Then 𝜆 ^ ′ is a function of 𝐸 , or, equivalently, 𝜆 ^ ′ is a constant conditional on 𝐸 . Additionally, 𝐿 𝑛 + 1 ( 𝜆 ) | 𝐸 ∼ Uniform ( { 𝐿 1 , … , 𝐿 𝑛 + 1 } ) by exchangeability. These facts combined with the right-continuity of 𝐿 𝑖 imply

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ′ ) ∣ 𝐸 ]

1 𝑛 + 1 ⁢ ∑ 𝑖

1 𝑛 + 1 𝐿 𝑖 ⁢ ( 𝜆 ^ ′ ) ≤ 𝛼 .

(11)

The proof is completed by the law of total expectation and (10). ∎

2.2A risk lower bound

Next we show that the conformal risk control procedure is tight up to a factor 2 ⁢ 𝐵 / ( 𝑛 + 1 ) . Like the standard conformal coverage upper bound, the proof will rely on a form of continuity that prohibits large jumps in the risk function. Towards that end, we will define the jump function below, which quantifies the size of the discontinuity in a right-continuous input function 𝑙 at point 𝜆 :

𝐽 ⁢ ( 𝑙 , 𝜆 )

lim 𝜖 → 0 + ⁢ 𝑙 ⁢ ( 𝜆 − 𝜖 ) − 𝑙 ⁢ ( 𝜆 )

(12)

The jump function measures the size of a discontinuity at 𝑙 ⁢ ( 𝜆 ) . When there is a discontinuity and 𝑙 is non-increasing, 𝐽 ⁢ ( 𝑙 , 𝜆 ) > 0 . When there is no discontinuity, the jump function is zero. The next theorem will assume that the probability that 𝐿 𝑖 has a discontinuity at any pre-specified 𝜆 is ℙ ⁢ ( 𝐽 ⁢ ( 𝐿 𝑖 , 𝜆 ) > 0 )

0 . Under this assumption the conformal risk control procedure is not too conservative.

Theorem 2.2.

In the setting of Theorem 2.1, further assume that the 𝐿 𝑖 are i.i.d., 𝐿 𝑖 ≥ 0 , and for any 𝜆 , ℙ ⁢ ( 𝐽 ⁢ ( 𝐿 𝑖 , 𝜆 ) > 0 )

0 . Then

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ] ≥ 𝛼 − 2 ⁢ 𝐵 𝑛 + 1 .

2.3Conformal prediction reduces to risk control

Conformal prediction can be thought of as controlling the expectation of an indicator loss function. Recall that the risk upper bound (2) specializes to the conformal coverage guarantee in (1) when the loss function is the indicator of a miscoverage event. The conformal risk control procedure specializes to conformal prediction under this loss function as well. However, the risk lower bound in Theorem 2.2 has a slightly worse constant than the usual conformal guarantee. We now describe these correspondences.

First, we show the equivalence of the algorithms. In conformal prediction, we have conformal scores 𝑠 ⁢ ( 𝑋 𝑖 , 𝑌 𝑖 ) for some score function 𝑠 : 𝒳 × 𝒴 → ℝ . Based on this score function, we create prediction sets for the test point 𝑋 𝑛 + 1 as

𝒞 𝜆 ^ ⁢ ( 𝑋 𝑛 + 1 )

{ 𝑦 : 𝑠 ⁢ ( 𝑋 𝑛 + 1 , 𝑦 ) ≤ 𝜆 ^ } ,

where 𝜆 ^ is the conformal quantile, a parameter that is set based on the calibration data. In particular, conformal prediction chooses 𝜆 ^ to be the ⌈ ( 𝑛 + 1 ) ⁢ ( 1 − 𝛼 ) ⌉ / 𝑛 sample quantile of { 𝑠 ⁢ ( 𝑋 𝑖 , 𝑌 𝑖 ) } 𝑖

1 𝑛 . To formulate this in the language of risk control, we consider a miscoverage loss 𝐿 𝑖 Cvg ⁢ ( 𝜆 )

𝟙 ⁢ { 𝑌 𝑖 ∉ 𝒞 ^ 𝜆 ⁢ ( 𝑋 𝑖 ) }

𝟙 ⁢ { 𝑠 ⁢ ( 𝑋 𝑖 , 𝑌 𝑖 )

𝜆 } . Direct calculation of 𝜆 ^ from (4) then shows the equivalence of the proposed procedure to conformal prediction:

𝜆 ^

inf { 𝜆 : 1 𝑛 + 1 ⁢ ∑ 𝑖

1 𝑛 𝟙 ⁢ { 𝑠 ⁢ ( 𝑋 𝑖 , 𝑌 𝑖 ) > 𝜆 } + 1 𝑛 + 1 ≤ 𝛼 }

inf { 𝜆 : 1 𝑛 ⁢ ∑ 𝑖

1 𝑛 𝟙 ⁢ { 𝑠 ⁢ ( 𝑋 𝑖 , 𝑌 𝑖 ) ≤ 𝜆 } ≥ ⌈ ( 𝑛 + 1 ) ⁢ ( 1 − 𝛼 ) ⌉ 𝑛 } ⏟ conformal ⁢ prediction ⁢ algorithm .

(13)

Next, we discuss how the risk lower bound relates to its conformal prediction equivalent. In the setting of conformal prediction, [lei2018distribution] proves that ℙ ⁢ ( 𝑌 𝑛 + 1 ∉ 𝒞 𝜆 ^ ⁢ ( 𝑋 𝑛 + 1 ) ) ≥ 𝛼 − 1 / ( 𝑛 + 1 ) when the conformal score function follows a continuous distribution. Theorem 2.2 recovers this guarantee with a slightly worse constant: ℙ ⁢ ( 𝑌 𝑛 + 1 ∉ 𝒞 𝜆 ^ ⁢ ( 𝑋 𝑛 + 1 ) ) ≥ 𝛼 − 2 / ( 𝑛 + 1 ) . First, note that our assumption in Theorem 2.2 about the distribution of discontinuities specializes to the continuity of the score function when the miscoverage loss is used:

ℙ ⁢ ( 𝐽 ⁢ ( 𝐿 𝑖 Cvg , 𝜆 ) > 0 )

0 ⟺ ℙ ⁢ ( 𝑠 ⁢ ( 𝑋 𝑖 , 𝑌 𝑖 )

𝜆 )

0 .

(14)

However, the bound for the conformal case is better than the bound for the general case in Theorem 2.2 by a factor of two. We do not know whether this factor of 2 is improvable. However, this factor is of little practical importance, as the difference between 1 / ( 𝑛 + 1 ) and 2 / ( 𝑛 + 1 ) is small even for moderate values of 𝑛 .

2.4Controlling general loss functions

We next show that the conformal risk control algorithm does not control the risk if the 𝐿 𝑖 are not assumed to be monotone. In particular, (3) does not hold. We show this by example.

Proposition 2.1.

For any 𝜖 , there exists a non-monotone loss function such that

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ] ≥ 𝐵 − 𝜖 .

(15)

Notice that for any desired level 𝛼 , the expectation in (3) can be arbitrarily close to 𝐵 . Since the function values here are in [ 0 , 𝐵 ] , this means that even for bounded random variables, risk control can be violated by an arbitrary amount—unless further assumptions are placed on the 𝐿 𝑖 . However, the algorithms developed may still be appropriate for near-monotone loss functions. Simply ‘monotonizing’ all loss functions 𝐿 𝑖 and running conformal risk control will guarantee (3), but this strategy will only be powerful if the loss is near-monotone. For concreteness, we describe this procedure below as a corollary of Theorem 2.1.

Corollary 1.

Allow 𝐿 𝑖 ⁢ ( 𝜆 ) to be any (possibly non-monotone) function of 𝜆 satisfying 6. Take

𝐿 ~ 𝑖 ⁢ ( 𝜆 )

sup 𝜆 ′ ≥ 𝜆 ⁢ 𝐿 𝑖 ⁢ ( 𝜆 ′ ) , 𝑅 ~ 𝑛 ⁢ ( 𝜆 )

1 𝑛 ⁢ ∑ 𝑖

1 𝑛 𝐿 ~ 𝑖 ⁢ ( 𝜆 ) and  ⁢ 𝜆 ~

inf { 𝜆 : 𝑛 𝑛 + 1 ⁢ 𝑅 ~ 𝑛 ⁢ ( 𝜆 ) + 𝐵 𝑛 + 1 ≤ 𝛼 } .

(16)

Then,

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ~ ) ] ≤ 𝛼 .

(17)

If the loss function is already monotone, then 𝜆 ~ reduces to 𝜆 ^ . We propose a further algorithm for picking 𝜆 in Appendix A that provides an asymptotic risk-control guarantee for non-monotone loss functions. However, this algorithm again is only powerful when the risk 𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ) ] is near-monotone and reduces to the standard conformal risk control algorithm when the loss is monotone.

3Examples

To demonstrate the flexibility and empirical effectiveness of the proposed algorithm, we apply it to four tasks across computer vision and natural language processing. All four loss functions are non-binary, monotone losses bounded by 1 . They are commonly used within their respective application domains. Our results validate that the procedure bounds the risk as desired and gives useful outputs to the end-user. We note that the choices of 𝒞 𝜆 used herein are only for the purposes of illustration; any nested family of sets will work. For each example use case, for a representative 𝛼 (details provided for each task) we provide both qualitative results, as well as quantitative histograms of the risk and set sizes over 1000 random data splits that demonstrate valid risk control (i.e., with mean ≤ 𝛼 ). Code to reproduce our examples is available at the following GitHub link: https://github.com/aangelopoulos/conformal-risk.

3.1FNR control in tumor segmentation Figure 1:FNR control in tumor segmentation. The top figure shows examples of our procedure with correct pixels in white, false positives in blue, and false negatives in red. The bottom plots report FNR and set size over 1000 independent random data splits. The dashed gray line marks 𝛼 .

In the tumor segmentation setting, our input is a 𝑑 × 𝑑 image and our label is a set of pixels 𝑌 𝑖 ∈ ℘ ⁢ ( { ( 1 , 1 ) , ( 1 , 2 ) , … , ( 𝑑 , 𝑑 ) } ) , where ℘ denotes the power set. We build on an image segmentation model 𝑓 : 𝒳 → [ 0 , 1 ] 𝑑 × 𝑑 outputting a probability for each pixel and measure loss as the fraction of false negatives,

𝐿 𝑖 FNR ⁢ ( 𝜆 )

1 − | 𝑌 𝑖 ∩ 𝒞 𝜆 ⁢ ( 𝑋 𝑖 ) | | 𝑌 𝑖 | ,  where  ⁢ 𝒞 𝜆 ⁢ ( 𝑋 𝑖 )

{ 𝑦 : 𝑓 ⁢ ( 𝑋 𝑖 ) 𝑦 ≥ 1 − 𝜆 } .

(18)

The expected value of 𝐿 𝑖 FNR is the FNR. Since 𝐿 𝑖 FNR is monotone, so is the FNR. Thus, we use the technique in Section 2.1 to pick 𝜆 ^ by (4) that controls the FNR on a new point, resulting in the following guarantee:

𝔼 ⁢ [ 𝐿 𝑛 + 1 FNR ⁢ ( 𝜆 ^ ) ] ≤ 𝛼 .

(19)

For evaluating the proposed procedure we pool data from several online open-source gut polyp segmentation datasets: Kvasir, Hyper-Kvasir, CVC-ColonDB, CVC-ClinicDB, and ETIS-Larib. We choose a PraNet \citepfan2020pranet as our base model 𝑓 and used 𝑛

1000 , and evaluated risk control with the 781 remaining validation data points. We report results with 𝛼

0.1 in Figure 1. The mean and standard deviation of the risk over 1000 trials are 0.0987 and 0.0114, respectively.

3.2FNR control in multilabel classification Figure 2:FNR control on MS COCO. The top figure shows examples of our procedure with correct classes in black, false positives in blue, and false negatives in red. The bottom plots report FNR and set size over 1000 independent random data splits. The dashed gray line marks 𝛼 .

In the multilabel classification setting, our input 𝑋 𝑖 is an image and our label is a set of classes 𝑌 𝑖 ⊂ { 1 , … , 𝐾 } for some number of classes 𝐾 . Using a multiclass classification model 𝑓 : 𝒳 → [ 0 , 1 ] 𝐾 , we form prediction sets and calculate the number of false positives exactly as in (18). By Theorem 2.1, picking 𝜆 ^ as in (4) again yields the FNR-control guarantee in (19).

We use the Microsoft Common Objects in Context (MS COCO) computer vision dataset \citeplin2014microsoft, a large-scale 80-class multiclass classification baseline dataset commonly used in computer vision, to evaluate the proposed procedure. We choose a TResNet \citepridnik2020tresnet as our base model 𝑓 and used 𝑛

4000 , and evaluated risk control with 1000 validation data points. We report results with 𝛼

0.1 in Figure 2. The mean and standard deviation of the risk over 1000 trials are 0.0996 and 0.0052, respectively.

3.3Control of graph distance in hierarchical image classification Figure 3:Control of graph distance on hierarchical ImageNet. The top figure shows examples of our procedure with correct classes in black, false positives in blue, and false negatives in red. The bottom plots report our minimum hierarchical distance loss and set size over 1000 independent random data splits. The dashed gray line marks 𝛼 .

In the 𝐾 -class hierarchical classification setting, our input 𝑋 𝑖 is an image and our label is a leaf node 𝑌 𝑖 ∈ { 1 , … , 𝐾 } on a tree with nodes 𝒱 and edges ℰ . Using a single-class classification model 𝑓 : 𝒳 → Δ 𝐾 , we calibrate a loss in graph distance between the interior node we select and the closest ancestor of the true class. For any 𝑥 ∈ 𝒳 , let 𝑦 ^ ⁢ ( 𝑥 )

arg ⁡ max 𝑘 ⁡ 𝑓 ⁢ ( 𝑥 ) 𝑘 be the class with the highest estimated probability. Further, let 𝑑 : 𝒱 × 𝒱 → ℤ be the function that returns the length of the shortest path between two nodes, let 𝒜 : 𝒱 → 2 𝒱 be the function that returns the ancestors of its argument, and let 𝒫 : 𝒱 → 2 𝒱 be the function that returns the set of leaf nodes that are descendants of its argument. We also let 𝑔 ⁢ ( 𝑣 , 𝑥 )

∑ 𝑘 ∈ 𝒫 ⁢ ( 𝑣 ) ⁢ 𝑓 ⁢ ( 𝑥 ) 𝑘 be the sum of scores of leaves descended from 𝑣 . Further, define a hierarchical distance

𝑑 𝐻 ⁢ ( 𝑣 , 𝑢 )

inf 𝑎 ∈ 𝒜 ⁢ ( 𝑣 ) ⁢ { 𝑑 ⁢ ( 𝑎 , 𝑢 ) } .

For a set of nodes 𝒞 𝜆 ∈ 2 𝒱 , we then define the set-valued loss

𝐿 𝑖 Graph ⁢ ( 𝜆 )

inf 𝑠 ∈ 𝒞 𝜆 ⁢ ( 𝑋 𝑖 ) ⁢ { 𝑑 𝐻 ⁢ ( 𝑦 , 𝑠 ) } / 𝐷 ,  where  ⁢ 𝒞 𝜆 ⁢ ( 𝑥 )

⋂ { 𝑎 ∈ 𝒜 ⁢ ( 𝑦 ^ ⁢ ( 𝑥 ) ) : 𝑔 ⁢ ( 𝑎 , 𝑥 ) ≥ − 𝜆 } ⁢ 𝒫 ⁢ ( 𝑎 ) .

(20)

This loss returns zero if 𝑦 is a child of any element in 𝒞 𝜆 , and otherwise returns the minimum distance between any element of 𝒞 𝜆 and any ancestor of 𝑦 , scaled by the depth 𝐷 . Thus, it is a monotone loss function and can be controlled by choosing 𝜆 ^ as in (4) to achieve the guarantee

𝔼 ⁢ [ 𝐿 𝑛 + 1 Graph ⁢ ( 𝜆 ^ ) ] ≤ 𝛼 .

(21)

For this experiment, we use the ImageNet dataset \citepdeng2009imagenet, which comes with an existing label hierarchy, WordNet, of maximum depth 𝐷

14 . We choose a ResNet152 \citephe2016deep as our base model 𝑓 and used 𝑛

30000 , and evaluated risk control with the remaining 20000 . We report results with 𝛼

0.05 in Figure 3. The mean and standard deviation of the risk over 1000 trials are 0.0499 and 0.0011, respectively.

3.4F1-score control in open-domain question answering Figure 4:F1-score control on Natural Questions. The top figure shows examples of our procedure with fully correct answers in green, partially correct answers in blue, and false positives in gray. Note that due to the nature of the evaluation, answers that are technically correct may still be down-graded if they do not match the reference. We treat this as part of the randomness in the task. The bottom plots report the F1 risk and average set size over 1000 independent random data splits. The dashed gray line marks 𝛼 .

In the open-domain question answering setting, our input 𝑋 𝑖 is a question and our label 𝑌 𝑖 is a set of (possibly non-unique) correct answers. For example, the input

𝑋 𝑛 + 1

“Where was Barack Obama Born?”

could have the answer set

𝑌 𝑛 + 1

{ “Hawaii”, “Honolulu, Hawaii”, “Kapo’olani Medical Center” }

Formally, here we treat all questions and answers as being composed of sequences (up to size 𝑚 ) of tokens in a vocabulary 𝒱 —i.e., assuming 𝑘 valid answers, we have 𝑋 𝑖 ∈ 𝒵 and 𝑌 𝑖 ∈ 𝒵 𝑘 , where 𝒵 := 𝒱 𝑚 . Using an open-domain question answering model that individually scores candidate output answers 𝑓 : 𝒵 × 𝒵 → ℝ , we calibrate the best token-based F1-score of the prediction set, taken over all pairs of predictions and answers:

𝐿 𝑖 F1 ⁢ ( 𝜆 )

1 − max ⁡ { F1 ⁢ ( 𝑎 , 𝑐 ) : 𝑐 ∈ 𝒞 𝜆 ⁢ ( 𝑋 𝑖 ) , 𝑎 ∈ 𝑌 𝑖 } ,

 where  ⁢ 𝒞 𝜆 ⁢ ( 𝑋 𝑖 )

{ 𝑦 ∈ 𝒱 𝑚 : 𝑓 ⁢ ( 𝑋 𝑖 , 𝑦 ) ≥ 𝜆 } .

(22)

We define the F1-score following popular QA evaluation metrics \citepsquad, where we treat predictions and ground truth answers as bags of tokens and compute the geometric average of their precision and recall (while ignoring punctuation and articles { “a”, “an”, “the” } ). Since 𝐿 𝑖 F1 , as defined in this way, is monotone and upper bounded by 1 , it can be controlled by choosing 𝜆 ^ as in Section 2.1 to achieve the following guarantee:

𝔼 ⁢ [ 𝐿 𝑛 + 1 F1 ⁢ ( 𝜆 ^ ) ] ≤ 𝛼 .

(23)

We use the Natural Questions (NQ) dataset \citepnq, a popular open-domain question answering baseline, to evaluate our method. We use the splits distributed as part of the Dense Passage Retrieval (DPR) package \citepdpr. Our base model is the DPR Retriever-Reader model \citepdpr, which retrieves passages from Wikipedia that might contain the answer to the given query, and then uses a reader model to extract text sub-spans from the retrieved passages that serve as candidate answers. Instead of enumerating all possible answers to a given question (which is intractable), we retrieve the top several hundred candidate answers, extracted from the top 100 passages (which is sufficient to control all risks of interest). We use 𝑛

2500 calibration points, and evaluate risk control with the remaining 1110 . We report results with 𝛼

0.3 (chosen empirically as the lowest F1 score which typically results in nearly correct answers) in Figure 4. The mean and standard deviation of the risk over 1000 trials are 0.2996 and 0.0150, respectively.

4Extensions

In this section, we discuss several theoretical extensions of our procedure.

4.1Risk control under distributional shift

Suppose the researcher wants to control the risk under a distribution shift. Then the goal in (3) can be redefined as

𝔼 ( 𝑋 1 , 𝑌 1 ) , … , ( 𝑋 𝑛 , 𝑌 𝑛 ) ∼ 𝑃 train , ( 𝑋 𝑛 + 1 , 𝑌 𝑛 + 1 ) ∼ 𝑃 test ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ] ≤ 𝛼 ,

(24)

where 𝑃 test denotes the test distribution that is different from the training distribution 𝑃 train that ( 𝑋 𝑖 , 𝑌 𝑖 ) 𝑖

1 𝑛 are sampled from. Assuming that 𝑃 test is absolutely continuous with respect to 𝑃 train , the weighted objective (24) can be rewritten as

𝔼 ( 𝑋 1 , 𝑌 1 ) , … , ( 𝑋 𝑛 + 1 , 𝑌 𝑛 + 1 ) ∼ 𝑃 train ⁢ [ 𝑤 ⁢ ( 𝑋 𝑛 + 1 , 𝑌 𝑛 + 1 ) ⁢ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ]

≤ 𝛼 ,

(25)

where  ⁢ 𝑤 ⁢ ( 𝑥 , 𝑦 )

𝑑 ⁢ 𝑃 test ⁢ ( 𝑥 , 𝑦 ) 𝑑 ⁢ 𝑃 train ⁢ ( 𝑥 , 𝑦 ) .

When 𝑤 is known and bounded, we can apply our procedure on the loss function 𝐿 ~ 𝑛 + 1 ⁢ ( 𝜆 )

𝑤 ⁢ ( 𝑋 𝑛 + 1 , 𝑌 𝑛 + 1 ) ⁢ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ) , which is non-decreasing, bounded, and right-continuous in 𝜆 whenever 𝐿 𝑛 + 1 is. Thus, Theorem 2.1 guarantees that the resulting 𝜆 ^ satisfies (25).

In the setting of transductive learning, 𝑋 𝑛 + 1 is available to the user. If the conditional distribution of 𝑌 given 𝑋 remains the same in the training and test domains, the distributional shift reduces to a covariate shift and

𝑤 ⁢ ( 𝑋 𝑛 + 1 , 𝑌 𝑛 + 1 )

𝑤 ⁢ ( 𝑋 𝑛 + 1 )

△ 𝑑 ⁢ 𝑃 test ⁢ ( 𝑋 𝑛 + 1 ) 𝑑 ⁢ 𝑃 train ⁢ ( 𝑋 𝑛 + 1 ) .

In this case, we can achieve the risk control even when 𝑤 is unbounded. In particular, assuming 𝐿 𝑖 ∈ [ 0 , 𝐵 ] , for any potential value 𝑥 of the covariate, we define

𝜆 ^ ⁢ ( 𝑥 )

inf { 𝜆 : ∑ 𝑖

1 𝑛 𝑤 ⁢ ( 𝑋 𝑖 ) ⁢ 𝐿 𝑖 ⁢ ( 𝜆 ) + 𝑤 ⁢ ( 𝑥 ) ⁢ 𝐵 ∑ 𝑖

1 𝑛 𝑤 ⁢ ( 𝑋 𝑖 ) + 𝑤 ⁢ ( 𝑥 ) ≤ 𝛼 } .

(26)

When 𝜆 does not exist, we simply set 𝜆 ^ ⁢ ( 𝑥 )

max ⁡ Λ . It is not hard to see that 𝜆 ^ ⁢ ( 𝑥 ) ≡ 𝜆 ^ in the absence of covariate shifts. We can prove the following result.

Proposition 4.1.

In the setting of Theorem 2.1,

𝔼 ( 𝑋 1 , 𝑌 1 ) , … , ( 𝑋 𝑛 , 𝑌 𝑛 ) ∼ 𝑃 train , ( 𝑋 𝑛 + 1 , 𝑌 𝑛 + 1 ) ∼ 𝑃 test ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ⁢ ( 𝑋 𝑛 + 1 ) ) ] ≤ 𝛼 .

(27)

It is easy to show that the weighted conformal procedure \citeptibshirani2019conformal is a special case with 𝐿 𝑖 ⁢ ( 𝜆 )

𝟙 ⁢ { 𝑌 𝑖 ∉ 𝒞 𝜆 ⁢ ( 𝑋 𝑖 ) } where 𝒞 𝜆 ⁢ ( 𝑋 𝑖 ) is the prediction set that thresholds the conformity score at 𝜆 . Thus, Proposition 4.1 generalizes [tibshirani2019conformal] to any monotone risk. When the covariate shift 𝑤 ⁢ ( 𝑥 ) is unknown but unlabeled data in the test domain are available, it can be estimated, up to a multiplicative factor that does not affect 𝜆 ^ ⁢ ( 𝑥 ) , by any probabilistic classification algorithm; see [lei2020conformal] and [candes2023conformalized] in the context of missing and censored data, respectively. We leave the full investigation of weighted conformal risk control with an estimated covariate shift for future research.

Total variation bound

Finally, for arbitrary distribution shifts, we give a total variation bound describing the way standard (unweighted) conformal risk control degrades. The bound is analogous to that of [barber2022conformal]for independent but non-identically distributed data (see their Section 4.1), though the proof is different. Here we will use the notation 𝑍 𝑖

( 𝑋 𝑖 , 𝑌 𝑖 ) , and 𝜆 ^ ⁢ ( 𝑍 1 , … , 𝑍 𝑛 ) to refer to that chosen in (4).

Proposition 4.2.

Let 𝑍

( 𝑍 1 , … , 𝑍 𝑛 + 1 ) be a sequence of random variables. Then, under the conditions in Theorem 2.1,

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ] ≤ 𝛼 + 𝐵 ⁢ ∑ 𝑖

1 𝑛 TV ⁢ ( 𝑍 𝑖 , 𝑍 𝑛 + 1 ) .

If further the assumptions of Theorem 2.2 hold,

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ] ≥ 𝛼 − 𝐵 ⁢ ( 2 𝑛 + 1 + ∑ 𝑖

1 𝑛 TV ⁢ ( 𝑍 𝑖 , 𝑍 𝑛 + 1 ) ) .

4.2Quantile risk control

[snell2022quantile] generalizes [bates2021distribution] to control the quantile of a monotone loss function conditional on ( 𝑋 𝑖 , 𝑌 𝑖 ) 𝑖

1 𝑛 with probability 1 − 𝛿 over the calibration dataset for any user-specified tolerance parameter 𝛿 . In some applications, it may be sufficient to control the unconditional quantile of the loss function, which alleviates the burden of the user to choose the tolerance parameter 𝛿 .

For any random variable 𝑋 , let

Quantile 𝛽 ⁢ ( 𝑋 )

inf { 𝑥 : ℙ ⁢ ( 𝑋 ≤ 𝑥 ) ≥ 𝛽 } .

Analogous to (3), we want to find 𝜆 ^ based on ( 𝑋 𝑖 , 𝑌 𝑖 ) 𝑖

1 𝑛 such that

Quantile 𝛽 ⁢ ( 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ 𝛽 ) ) ≤ 𝛼 .

(28)

By definition,

Quantile 𝛽 ⁢ ( 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ 𝛽 ) ) ≤ 𝛼 ⟺ 𝔼 ⁢ [ 𝟙 ⁢ { 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ 𝛽 )

𝛼 } ] ≤ 1 − 𝛽 .

As a consequence, quantile risk control is equivalent to expected risk control (3) with loss function 𝐿 ~ 𝑖 ⁢ ( 𝜆 )

𝟙 ⁢ { 𝐿 𝑖 ⁢ ( 𝜆 )

𝛼 } . Let

𝜆 ^ 𝛽

inf { 𝜆 ∈ Λ : 1 𝑛 + 1 ⁢ ∑ 𝑖

1 𝑛 𝟙 ⁢ { 𝐿 𝑖 ⁢ ( 𝜆 )

𝛼 } + 1 𝑛 + 1 ≤ 1 − 𝛽 } .

Proposition 4.3.

In the setting of Theorem 2.1, (28) is achieved.

[snell2022quantile] considers the high-probability control of a wider class of quantile-based risks which include the conditional value-at-risk (CVaR). It is unclear whether those more general risks can be controlled unconditionally. We leave this open problem for future research.

4.3Controlling multiple risks

Let 𝐿 𝑖 ⁢ ( 𝜆 ; 𝛾 ) be a family of loss functions indexed by 𝛾 ∈ Γ for some domain Γ that may have infinitely many elements. A researcher may want to control 𝔼 ⁢ [ 𝐿 𝑖 ⁢ ( 𝜆 ; 𝛾 ) ] at level 𝛼 ⁢ ( 𝛾 ) . Equivalently, we need to find an 𝜆 ^ based on ( 𝑋 𝑖 , 𝑌 𝑖 ) 𝑖

1 𝑛 such that

sup 𝛾 ∈ Γ 𝔼 ⁢ [ 𝐿 𝑖 ⁢ ( 𝜆 ^ ; 𝛾 ) 𝛼 ⁢ ( 𝛾 ) ] ≤ 1 .

(29)

Though the above worst-case risk is not an expectation, it can still be controlled. Towards this end, we define

𝜆 ^

sup 𝛾 ∈ Γ 𝜆 ^ 𝛾 ,  where  ⁢ 𝜆 ^ 𝛾

inf { 𝜆 : 1 𝑛 + 1 ⁢ ∑ 𝑖

1 𝑛 𝐿 𝑖 ⁢ ( 𝜆 ; 𝛾 ) + 𝐵 𝑛 + 1 ≤ 𝛼 ⁢ ( 𝛾 ) } .

(30)

Then the risk is controlled.

Proposition 4.4.

In the setting of Theorem 2.1, (29) is satisfied.

4.4Adversarial risks

We next show how to control risks defined by adversarial perturbations. We adopt the same notation as Section 4.3. [bates2021distribution] (Section 6.3) discusses the adversarial risk where Γ parametrizes a class of perturbations of 𝑋 𝑛 + 1 , e.g., 𝐿 𝑖 ⁢ ( 𝜆 ; 𝛾 )

𝐿 ⁢ ( 𝑋 𝑖 + 𝛾 , 𝑌 𝑖 ) and Γ

{ 𝛾 : ‖ 𝛾 ‖ ∞ ≤ 𝜖 } . A researcher may want to find an 𝜆 ^ based on ( 𝑋 𝑖 , 𝑌 𝑖 ) 𝑖

1 𝑛 such that

𝔼 ⁢ [ sup 𝛾 ∈ Γ 𝐿 𝑖 ⁢ ( 𝜆 ; 𝛾 ) ] ≤ 𝛼 .

(31)

This can be recast as a conformal risk control problem by taking 𝐿 ~ 𝑖 ⁢ ( 𝜆 )

sup 𝛾 ∈ Γ 𝐿 𝑖 ⁢ ( 𝜆 ; 𝛾 ) . Then, the following choice of 𝜆 leads to risk control:

𝜆 ^

inf { 𝜆 : 1 𝑛 + 1 ⁢ ∑ 𝑖

1 𝑛 𝐿 ~ 𝑖 ⁢ ( 𝜆 ) + 𝐵 𝑛 + 1 ≤ 𝛼 } .

(32) Proposition 4.5.

In the setting of Theorem 2.1, (31) is satisfied.

4.5U-risk control

For ranking and metric learning, [bates2021distribution] considered loss functions that depend on two test points. In general, for any 𝑘 > 1 and subset 𝒮 ⊂ { 1 , … , 𝑛 + 𝑘 } with | 𝒮 |

𝑘 , let 𝐿 𝒮 ⁢ ( 𝜆 ) be a loss function. Our goal is to find 𝜆 ^ 𝑘 based on ( 𝑋 𝑖 , 𝑌 𝑖 ) 𝑖

1 𝑛 such that

𝔼 ⁢ [ 𝐿 { 𝑛 + 1 , … , 𝑛 + 𝑘 } ⁢ ( 𝜆 ^ 𝑘 ) ] ≤ 𝛼 .

(33)

We call the LHS a U-risk since, for any fixed 𝜆 ^ 𝑘 , it is the expectation of an order- 𝑘 U-statistic. As a natural extension, we can define

𝜆 ^ 𝑘

inf { 𝜆 : 𝑘 ! ⁢ 𝑛 ! ( 𝑛 + 𝑘 ) ! ⁢ ∑ 𝒮 ⊂ { 1 , … , 𝑛 } , | 𝒮 |

𝑘 𝐿 𝒮 ⁢ ( 𝜆 ) + 𝐵 ⁢ ( 1 − ( 𝑛 ! ) 2 ( 𝑛 + 𝑘 ) ! ⁢ ( 𝑛 − 𝑘 ) ! ) ≤ 𝛼 } .

(34)

Again, we define 𝜆 ^ 𝑘

𝜆 max when the right-hand side is an empty set. Then we can prove the following result.

Proposition 4.6.

Assume that 𝐿 𝒮 ⁢ ( 𝜆 ) is non-increasing in 𝜆 , right-continuous, and

𝐿 𝒮 ⁢ ( 𝜆 max ) ≤ 𝛼 , sup 𝜆 𝐿 𝒮 ⁢ ( 𝜆 ) ≤ 𝐵 < ∞ ⁢  almost surely .

Then (33) is achieved.

5Conclusion

This generalization of conformal prediction broadens its scope to new applications, as shown in Section 3. The mathematical tools developed in Section 2, Section 4, and the Appendix may be of independent technical interest, since they provide a new and more general language for studying conformal prediction along with new results about its validity.

Acknowledgements

The authors thank Christopher Yeh for pointing out that the factor of 2 in Theorem 2.2 may not be tight, correcting an error in an earlier draft. The incorrect proposition stating that it was tight has been removed; the tightness of this factor remains an open question. The authors would like to thank Nicolas Christianson, Amit Kohli, Sherrie Wang, and Tijana Zrnić for comments on early drafts. A. A. would like to thank Ziheng (Tony) Wang for helpful conversations. A. A. is funded by the NSF GRFP and a Berkeley Fellowship. S. B. is supported by the NSF FODSI fellowship and the Simons institute. A. F. is partially funded by the NSF GRFP and MIT MLPDS.

\printbibliography Appendix AMonotonizing non-monotone risks

We next show that the proposed algorithm leads to asymptotic risk control for non-monotone risk functions when applied to a monotonized version of the empirical risk. We set the monotonized empirical risk to be

𝑅 ^ 𝑛 ↑ ⁢ ( 𝜆 )

sup 𝑡 ≥ 𝜆 ⁢ 𝑅 ^ 𝑛 ⁢ ( 𝑡 ) ,

(35)

then define

𝜆 ^ 𝑛 ↑

inf { 𝜆 : 𝑅 ^ 𝑛 ↑ ⁢ ( 𝜆 ) ≤ 𝛼 } .

(36) Theorem A.1.

Let the 𝐿 𝑖 ⁢ ( 𝜆 ) be right-continuous, i.i.d., bounded (both above and below) functions satisfying (6). Then,

lim 𝑛 → ∞ ⁢ 𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ 𝑛 ↑ ) ] ≤ 𝛼 .

(37)

Theorem A.1 implies that an analogous procedure to 4 also controls the risk asymptotically. In particular, taking

𝜆 ~ ↑

inf { 𝜆 : 𝑅 ^ 𝑛 ↑ ⁢ ( 𝜆 ) + 𝐵 𝑛 + 1 ≤ 𝛼 }

(38)

also results in asymptotic risk control (to see this, plug 𝜆 ~ ↑ into Theorem A.1 and see that the risk level is bounded above by 𝛼 − 𝐵 𝑛 + 1 ). Note that in the case of a monotone loss function, 𝜆 ~ ↑

𝜆 ^ . However, the counterexample in Proposition 2.1 does not apply to 𝜆 ~ ↑ , and it is currently unknown whether this procedure does or does not provide finite-sample risk control.

Appendix BProofs

The proof of Theorem 2.2 uses the following lemma on the approximate continuity of the empirical risk.

Lemma 1 (Jump Lemma).

In the setting of Theorem 2.2, any jumps in the empirical risk are bounded, i.e.,

sup 𝜆 𝐽 ⁢ ( 𝑅 ^ 𝑛 , 𝜆 ) ⁢ ≤ 𝑎 . 𝑠 . ⁢ 𝐵 𝑛 .

(39) Proof of Jump Lemma, Lemma 1.

By boundedness, the maximum contribution of any single point to the jump is 𝐵 𝑛 , so

∃ 𝜆 : 𝐽 ⁢ ( 𝑅 ^ 𝑛 , 𝜆 )

𝐵 𝑛 ⟹ ∃ 𝜆 : 𝐽 ⁢ ( 𝐿 𝑖 , 𝜆 )

0 ⁢  and  ⁢ 𝐽 ⁢ ( 𝐿 𝑗 , 𝜆 )

0 ⁢  for some  ⁢ 𝑖 ≠ 𝑗 .

(40)

Call 𝒟 𝑖

{ 𝜆 : 𝐽 ⁢ ( 𝐿 𝑖 , 𝜆 )

0 } the sets of discontinuities in 𝐿 𝑖 . Since 𝐿 𝑖 is bounded monotone, 𝒟 𝑖 has countably many points. The union bound then implies that

ℙ ( ∃ 𝜆 : 𝐽 ( 𝑅 ^ 𝑛 , 𝜆 )

𝐵 𝑛 ) ≤ ∑ 𝑖 ≠ 𝑗 ℙ ( 𝒟 𝑖 ∩ 𝒟 𝑗 ≠ ∅ )

(41)

Rewriting each term of the right-hand side using tower property and law of total probability gives

ℙ ⁢ ( 𝒟 𝑖 ∩ 𝒟 𝑗 ≠ ∅ )

𝔼 ⁢ [ ℙ ⁢ ( 𝒟 𝑖 ∩ 𝒟 𝑗 ≠ ∅ | 𝒟 𝑗 ) ]

(42)

≤ 𝔼 ⁢ [ ∑ 𝜆 ∈ 𝒟 𝑗 ℙ ⁢ ( 𝜆 ∈ 𝒟 𝑖 | 𝒟 𝑗 ) ]

𝔼 ⁢ [ ∑ 𝜆 ∈ 𝒟 𝑗 ℙ ⁢ ( 𝜆 ∈ 𝒟 𝑖 ) ] ,

(43)

Where the second inequality is because the union of the events 𝜆 ∈ 𝒟 𝑗 is the entire sample space, but they are not disjoint, and the third equality is due to the independence between 𝒟 𝑖 and 𝒟 𝑗 . Rewriting in terms of the jump function and applying the assumption ℙ ⁢ ( 𝐽 ⁢ ( 𝐿 𝑖 , 𝜆 ) > 0 )

0 ,

𝔼 ⁢ [ ∑ 𝜆 ∈ 𝒟 𝑗 ℙ ⁢ ( 𝜆 ∈ 𝒟 𝑖 ) ]

𝔼 ⁢ [ ∑ 𝜆 ∈ 𝒟 𝑗 ℙ ⁢ ( 𝐽 ⁢ ( 𝐿 𝑖 , 𝜆 ) > 0 ) ]

0 .

(44)

Chaining the above inequalities yields ℙ ( ∃ 𝜆 : 𝐽 ( 𝑅 ^ 𝑛 , 𝜆 )

𝐵 𝑛 ) ≤ 0 , so

ℙ ( ∃ 𝜆 : 𝐽 ( 𝑅 ^ 𝑛 , 𝜆 ) > 𝐵 𝑛 )

0 . ∎

Proof of Theorem 2.2.

If 𝐿 𝑖 ⁢ ( 𝜆 max ) ≥ 𝛼 − 2 ⁢ 𝐵 / ( 𝑛 + 1 ) , then 𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ] ≥ 𝛼 − 2 ⁢ 𝐵 / ( 𝑛 + 1 ) . Throughout the rest of the proof, we assume that 𝐿 𝑖 ⁢ ( 𝜆 max ) < 𝛼 − 2 ⁢ 𝐵 / ( 𝑛 + 1 ) . Define the quantity

𝜆 ^ ′′

inf { 𝜆 : 𝑅 ^ 𝑛 + 1 ⁢ ( 𝜆 ) + 𝐵 𝑛 + 1 ≤ 𝛼 } .

(45)

Since 𝐿 𝑖 ⁢ ( 𝜆 max ) < 𝛼 − 2 ⁢ 𝐵 / ( 𝑛 + 1 ) < 𝛼 − 𝐵 / ( 𝑛 + 1 ) , 𝜆 ^ ′′ exists almost surely. Deterministically, 𝑛 𝑛 + 1 ⁢ 𝑅 ^ 𝑛 ⁢ ( 𝜆 ) ≤ 𝑅 ^ 𝑛 + 1 ⁢ ( 𝜆 ) , which yields 𝜆 ^ ≤ 𝜆 ^ ′′ . Again since 𝐿 𝑖 ⁢ ( 𝜆 ) is non-increasing in 𝜆 ,

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ′′ ) ] ≤ 𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ]

(46)

By exchangeability and the fact that 𝜆 ^ ′′ is a symmetric function of 𝐿 1 , … , 𝐿 𝑛 + 1 ,

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ′′ ) ]

𝔼 ⁢ [ 𝑅 ^ 𝑛 + 1 ⁢ ( 𝜆 ^ ′′ ) ]

(47)

For the remainder of the proof we focus on lower-bounding 𝑅 ^ 𝑛 + 1 ⁢ ( 𝜆 ^ ′′ ) . We begin with the following identity:

𝛼

𝑅 ^ 𝑛 + 1 ⁢ ( 𝜆 ^ ′′ ) + 𝐵 𝑛 + 1 − ( 𝑅 ^ 𝑛 + 1 ⁢ ( 𝜆 ^ ′′ ) + 𝐵 𝑛 + 1 − 𝛼 ) .

(48)

Rearranging the identity,

𝑅 ^ 𝑛 + 1 ⁢ ( 𝜆 ^ ′′ )

𝛼 − 𝐵 𝑛 + 1 + ( 𝑅 ^ 𝑛 + 1 ⁢ ( 𝜆 ^ ′′ ) + 𝐵 𝑛 + 1 − 𝛼 ) .

(49)

Using the Jump Lemma to bound ( 𝑅 ^ 𝑛 + 1 ⁢ ( 𝜆 ^ ′′ ) + 𝐵 𝑛 + 1 − 𝛼 ) below by − 𝐵 𝑛 + 1 gives

𝑅 ^ 𝑛 + 1 ⁢ ( 𝜆 ^ ′′ ) ≥ 𝛼 − 2 ⁢ 𝐵 𝑛 + 1 .

(50)

Finally, chaining together the above inequalities,

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ] ≥ 𝔼 ⁢ [ 𝑅 ^ 𝑛 + 1 ⁢ ( 𝜆 ^ ′′ ) ] ≥ 𝛼 − 2 ⁢ 𝐵 𝑛 + 1 .

(51)

∎

Proof of Proposition 2.1.

Without loss of generality, we assume 𝐵

1 . Assume 𝜆 ^ takes values in [ 0 , 1 ] and 𝛼 ∈ ( 1 / ( 𝑛 + 1 ) , 1 ) . Let 𝑝 ∈ ( 0 , 1 ) , 𝑁 be any positive integer, and 𝐿 𝑖 ⁢ ( 𝜆 ) be i.i.d. right-continuous piecewise constant (random) functions with

𝐿 𝑖 ⁢ ( 𝑁 / 𝑁 )

0 , ( 𝐿 𝑖 ⁢ ( 0 / 𝑁 ) , 𝐿 𝑖 ⁢ ( 1 / 𝑁 ) , … , 𝐿 𝑖 ⁢ ( ( 𝑁 − 1 ) / 𝑁 ) ) ∼ 𝑖 . 𝑖 . 𝑑 . Ber ⁢ ( 𝑝 ) .

(52)

By definition, 𝜆 ^ is independent of 𝐿 𝑛 + 1 . Thus, for any 𝑗

0 , 1 , … , 𝑁 − 1 ,

{ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ∣ 𝜆 ^

𝑗 / 𝑁 } ∼ Ber ⁢ ( 𝑝 ) , { 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ∣ 𝜆 ^

1 } ∼ 𝛿 0 .

(53)

Then,

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ]

𝑝 ⋅ ℙ ⁢ ( 𝜆 ^ ≠ 1 )

(54)

Note that

𝜆 ^ ≠ 1 ⟺ min 𝑗 ∈ { 0 , … , 𝑁 − 1 } ⁡ 1 𝑛 + 1 ⁢ ∑ 𝑖

1 𝑛 𝐿 𝑖 ⁢ ( 𝑗 / 𝑁 ) ≤ 𝛼 − 1 𝑛 + 1 .

(55)

Since 𝛼

1 / ( 𝑛 + 1 ) ,

ℙ ⁢ ( 𝜆 ^ ≠ 1 )

1 − ℙ ⁢ ( 𝜆 ^

1 )

1 − ℙ ⁢ ( for all  ⁢ 𝑗 ,  we have  ⁢ 1 𝑛 + 1 ⁢ ∑ 𝑖

1 𝑛 𝐿 𝑖 ⁢ ( 𝑗 / 𝑁 ) > 𝛼 − 1 𝑛 + 1 )

1 − ( ∑ 𝑘

⌈ ( 𝑛 + 1 ) ⁢ 𝛼 ⌉ 𝑛 ( 𝑛 𝑘 ) ⁢ 𝑝 𝑘 ⁢ ( 1 − 𝑝 ) ( 𝑛 − 𝑘 ) ) 𝑁

1 − ( 1 − BinoCDF ⁢ ( 𝑛 , 𝑝 , ⌈ ( 𝑛 + 1 ) ⁢ 𝛼 ⌉ − 1 ) ) 𝑁

As a result,

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ]

𝑝 ⁢ ( 1 − ( 1 − BinoCDF ⁢ ( 𝑛 , 𝑝 , ⌈ ( 𝑛 + 1 ) ⁢ 𝛼 ⌉ − 1 ) ) 𝑁 ) .

(56)

Now let 𝑁 be sufficiently large such that

( 1 − ( 1 − BinoCDF ⁢ ( 𝑛 , 𝑝 , ⌈ ( 𝑛 + 1 ) ⁢ 𝛼 ⌉ − 1 ) ) 𝑁 )

𝑝 .

(57)

Then

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ) ]

𝑝 2

(58)

For any 𝛼

0 , we can take 𝑝 close enough to 1 to render the claim false. ∎

Proof of Theorem A.1.

Define the monotonized population risk as

𝑅 ↑ ⁢ ( 𝜆 )

sup 𝑡 ≥ 𝜆 ⁢ 𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝑡 ) ]

(59)

Note that the independence of 𝐿 𝑛 + 1 and 𝜆 ^ 𝑛 ↑ implies that for all 𝑛 ,

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ 𝑛 ↑ ) ] ≤ 𝔼 ⁢ [ 𝑅 ↑ ⁢ ( 𝜆 ^ 𝑛 ↑ ) ] .

(60)

Since 𝑅 ↑ is bounded, monotone, and one-dimensional, a generalization of the Glivenko-Cantelli Theorem given in Theorem 1 of [dehardt1971generalizations] gives that uniformly over 𝜆 ,

lim 𝑛 → ∞ ⁢ sup 𝜆 | 𝑅 ^ 𝑛 ⁢ ( 𝜆 ) − 𝑅 ⁢ ( 𝜆 ) | ⁢ → 𝑎 . 𝑠 . ⁢ 0 .

(61)

As a result,

lim 𝑛 → ∞ ⁢ sup 𝜆 | 𝑅 ^ 𝑛 ↑ ⁢ ( 𝜆 ) − 𝑅 ↑ ⁢ ( 𝜆 ) | ⁢ → 𝑎 . 𝑠 . ⁢ 0 ,

(62)

which implies that

lim 𝑛 → ∞ ⁢ | 𝑅 ^ 𝑛 ↑ ⁢ ( 𝜆 ^ ↑ ) − 𝑅 ↑ ⁢ ( 𝜆 ^ ↑ ) | ⁢ → 𝑎 . 𝑠 . ⁢ 0 .

(63)

By definition, 𝑅 ^ ↑ ⁢ ( 𝜆 ^ ↑ ) ≤ 𝛼 almost surely and thus this directly implies

lim sup 𝑛 → ∞ ⁢ 𝑅 ↑ ⁢ ( 𝜆 ^ 𝑛 ↑ ) ≤ 𝛼 a.s. .

(64)

Finally, since for all 𝑛 , 𝑅 ↑ ⁢ ( 𝜆 ^ 𝑛 ↑ ) ≤ 𝐵 , by Fatou’s lemma,

lim 𝑛 → ∞ ⁢ 𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ 𝑛 ↑ ) ] ≤ lim sup 𝑛 → ∞ ⁢ 𝔼 ⁢ [ 𝑅 ↑ ⁢ ( 𝜆 ^ 𝑛 ↑ ) ] ≤ 𝔼 ⁢ [ lim sup 𝑛 → ∞ ⁢ 𝑅 ↑ ⁢ ( 𝜆 ^ 𝑛 ↑ ) ] ≤ 𝛼 .

(65)

∎

Proposition 4.1.

Let

𝜆 ^ ′

inf { 𝜆 : ∑ 𝑖

1 𝑛 + 1 𝑤 ⁢ ( 𝑋 𝑖 ) ⁢ 𝐿 𝑖 ⁢ ( 𝜆 ) ∑ 𝑖

1 𝑛 + 1 𝑤 ⁢ ( 𝑋 𝑖 ) ≤ 𝛼 } .

(66)

Since inf 𝜆 𝐿 𝑖 ⁢ ( 𝜆 ) ≤ 𝛼 , 𝜆 ^ ′ exists almost surely. Using the same argument as in the proof of Theorem 2.1, we can show that 𝜆 ^ ′ ≤ 𝜆 ^ ⁢ ( 𝑋 𝑛 + 1 ) . Since 𝐿 𝑛 + 1 ⁢ ( 𝜆 ) is non-increasing in 𝜆 ,

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ⁢ ( 𝑋 𝑛 + 1 ) ) ] ≤ 𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ′ ) ] .

Let 𝐸 be the multiset of loss functions { ( 𝑋 1 , 𝑌 1 ) , … , ( 𝑋 𝑛 + 1 , 𝑌 𝑛 + 1 ) } . Then 𝜆 ^ ′ is a function of 𝐸 , or, equivalently, 𝜆 ^ ′ is a constant conditional on 𝐸 . Lemma 3 of [tibshirani2019conformal] implies that

( 𝑋 𝑛 + 1 , 𝑌 𝑛 + 1 ) ∣ 𝐸 ∼ ∑ 𝑖

1 𝑛 + 1 𝑤 ⁢ ( 𝑋 𝑖 ) ∑ 𝑗

1 𝑛 + 1 𝑤 ⁢ ( 𝑋 𝑗 ) ⁢ 𝛿 ( 𝑋 𝑗 , 𝑌 𝑗 ) ⟹ 𝐿 𝑛 + 1 ∣ 𝐸 ∼ ∑ 𝑖

1 𝑛 + 1 𝑤 ⁢ ( 𝑋 𝑖 ) ∑ 𝑗

1 𝑛 + 1 𝑤 ⁢ ( 𝑋 𝑗 ) ⁢ 𝛿 𝐿 𝑖

where 𝛿 𝑧 denotes the Dirac measure at 𝑧 . Together with the right-continuity of 𝐿 𝑖 , the above result implies

𝔼 ⁢ [ 𝐿 𝑛 + 1 ⁢ ( 𝜆 ^ ′ ) ∣ 𝐸 ]

∑ 𝑖

1 𝑛 + 1 𝑤 ⁢ ( 𝑋 𝑖 ) ⁢ 𝐿 𝑖 ⁢ ( 𝜆 ^ ′ ) ∑ 𝑖

1 𝑛 + 1 𝑤 ⁢ ( 𝑋 𝑖 ) ≤ 𝛼 .

(67)

The proof is then completed by the law of total expectation. ∎

Proposition 4.2.

Define the vector 𝑍 ′

( 𝑍 1 ′ , … , 𝑍 𝑛 ′ , 𝑍 𝑛 + 1 ) , where 𝑍 𝑖 ′ ⁢ ∼ 𝑖 . 𝑖 . 𝑑 . ⁢ ℒ ⁢ ( 𝑍 𝑛 + 1 ) for all 𝑖 ∈ [ 𝑛 ] . Let

𝜖

∑ 𝑖

1 𝑛 TV ⁢ ( 𝑍 𝑖 , 𝑍 𝑖 ′ ) .

By sublinearity,

TV ⁢ ( 𝑍 , 𝑍 ′ ) ≤ 𝜖 .

(68)

It is a standard fact that (68) implies

sup 𝑓 ∈ ℱ 𝟙 ⁢ | 𝔼 ⁢ [ 𝑓 ⁢ ( 𝑍 ) ] − 𝔼 ⁢ [ 𝑓 ⁢ ( 𝑍 ′ ) ] | ≤ 𝜖 ,

(69)

where ℱ 𝟙

{ 𝑓 : 𝒵 ↦ [ 0 , 1 ] } . Let ℓ : 𝒵 × Λ → [ 0 , 𝐵 ] be a bounded loss function. Furthermore, let 𝑔 ⁢ ( 𝑧 )

ℓ ⁢ ( 𝑧 𝑛 + 1 ; 𝜆 ^ ⁢ ( 𝑧 1 , … , 𝑧 𝑛 ) ) . Since 𝑔 ⁢ ( 𝑍 ) ∈ [ 0 , 𝐵 ] ,

| 𝔼 ⁢ [ 𝑔 ⁢ ( 𝑍 ) ] − 𝔼 ⁢ [ 𝑔 ⁢ ( 𝑍 ′ ) ] | ≤ 𝐵 ⁢ 𝜖 .

(70)

Furthermore, since 𝑍 1 ′ , … , 𝑍 𝑛 + 1 ′ are exchangeable, we can apply Theorems 2.1 and 2.2 to 𝔼 ⁢ [ 𝑔 ⁢ ( 𝑍 ′ ) ] , recovering

𝛼 − 2 ⁢ 𝐵 𝑛 + 1 ≤ 𝔼 ⁢ [ 𝑔 ⁢ ( 𝑍 ′ ) ] ≤ 𝛼 .

(71)

A final step of triangle inequality implies the result:

𝛼 − 2 ⁢ 𝐵 𝑛 + 1 − 𝐵 ⁢ 𝜖 ≤ 𝔼 ⁢ [ 𝑔 ⁢ ( 𝑍 ) ] ≤ 𝛼 + 𝐵 ⁢ 𝜖 .

(72)

∎

Proposition 4.3.

It is left to prove that 𝐿 ~ 𝑖 ⁢ ( 𝜆 ) satisfies the conditions of Theorem 2.1. It is clear that 𝐿 ~ 𝑖 ⁢ ( 𝜆 ) ≤ 1 and 𝐿 ~ 𝑖 ⁢ ( 𝜆 ) is non-increasing in 𝜆 when 𝐿 𝑖 ⁢ ( 𝜆 ) is. Since 𝐿 𝑖 ⁢ ( 𝜆 ) is non-increasing and right-continuous, for any sequence 𝜆 𝑚 ↓ 𝜆 ,

𝐿 𝑖 ⁢ ( 𝜆 𝑚 ) ↑ 𝐿 𝑖 ⁢ ( 𝜆 ) ⟹ 𝟙 ⁢ { 𝐿 𝑖 ⁢ ( 𝜆 𝑚 )

𝛼 } → 𝟙 ⁢ { 𝐿 𝑖 ⁢ ( 𝜆 )

𝛼 } .

Thus, 𝐿 ~ 𝑖 ⁢ ( 𝜆 ) is right-continuous. Finally, 𝐿 𝑖 ⁢ ( 𝜆 max ) ≤ 𝛼 implies 𝐿 ~ 𝑖 ⁢ ( 𝜆 max )

0 ≤ 1 − 𝛽 . ∎

Proposition 4.4.

Examining (30), for each 𝛾 ∈ Γ , we have

𝔼 ⁢ [ 𝐿 ⁢ ( 𝜆 ^ , 𝛾 ) ] ≤ 𝔼 ⁢ [ 𝐿 ⁢ ( 𝜆 ^ 𝛾 , 𝛾 ) ] ≤ 𝛼 ⁢ ( 𝛾 ) .

(73)

Thus, dividing both sides by 𝛼 ⁢ ( 𝛾 ) and taking the supremum, we get that sup 𝛾 ∈ Γ 𝔼 ⁢ [ 𝐿 ⁢ ( 𝜆 ^ , 𝛾 ) 𝛼 ⁢ ( 𝛾 ) ] ≤ 1 , and the worst-case risk is controlled. ∎

Proposition 4.5.

Because 𝐿 𝑖 ⁢ ( 𝜆 , 𝛾 ) is bounded and monotone in 𝜆 for all choices of 𝛾 , it is also true that 𝐿 𝑖 ~ ⁢ ( 𝜆 ) is bounded and monotone. Furthermore, the pointwise supremum of right-continuous functions is also right-continuous. Therefore, the 𝐿 𝑖 ~ satisfy the assumptions of Theorem 2.1. ∎

Proposition 4.6.

Let

𝜆 ^ 𝑘 ′

inf { 𝜆 : 𝑘 ! ⁢ 𝑛 ! ( 𝑛 + 𝑘 ) ! ⁢ ∑ 𝒮 ⊂ { 1 , … , 𝑛 + 𝑘 } , | 𝒮 |

𝑘 𝐿 𝒮 ⁢ ( 𝜆 ) ≤ 𝛼 } .

Since 𝐿 𝒮 ⁢ ( 𝜆 max ) ≤ 𝛼 , 𝜆 ^ 𝑘 ′ exists almost surely. Since 𝐿 𝒮 ⁢ ( 𝜆 ) ≤ 𝐵 , we have

𝑘 ! ⁢ 𝑛 ! ( 𝑛 + 𝑘 ) ! ⁢ ∑ 𝒮 ⊂ { 1 , … , 𝑛 + 𝑘 } , | 𝒮 |

𝑘 𝐿 𝒮 ⁢ ( 𝜆 )

≤ 𝑘 ! ⁢ 𝑛 ! ( 𝑛 + 𝑘 ) ! ⁢ ∑ 𝒮 ⊂ { 1 , … , 𝑛 } , | 𝒮 |

𝑘 𝐿 𝒮 ⁢ ( 𝜆 ) + 𝐵 ⋅ ∑ 𝒮 ∩ { 𝑛 + 1 , … , 𝑛 + 𝑘 } ≠ ∅ , | 𝒮 |

𝑘 1

𝑘 ! ⁢ 𝑛 ! ( 𝑛 + 𝑘 ) ! ⁢ ∑ 𝒮 ⊂ { 1 , … , 𝑛 } , | 𝒮 |

𝑘 𝐿 𝒮 ⁢ ( 𝜆 ) + 𝐵 ⁢ ( 1 − 𝑘 ! ⁢ 𝑛 ! ( 𝑛 + 𝑘 ) ! ⁢ ∑ 𝒮 ⊂ { 1 , … , 𝑛 } , | 𝒮 |

𝑘 1 )

𝑘 ! ⁢ 𝑛 ! ( 𝑛 + 𝑘 ) ! ⁢ ∑ 𝒮 ⊂ { 1 , … , 𝑛 } , | 𝒮 |

𝑘 𝐿 𝒮 ⁢ ( 𝜆 ) + 𝐵 ⁢ ( 1 − ( 𝑛 ! ) 2 ( 𝑛 + 𝑘 ) ! ⁢ ( 𝑛 − 𝑘 ) ! ) .

Since 𝐿 𝒮 ⁢ ( 𝜆 ) is non-increasing in 𝜆 , we conclude that 𝜆 ^ 𝑘 ′ ≤ 𝜆 ^ 𝑘 if the right-hand side of (34) is not empty; otherwise, by definition, 𝜆 ^ 𝑘 ′ ≤ 𝜆 max

𝜆 ^ 𝑘 . Thus, 𝜆 ^ 𝑘 ′ ≤ 𝜆 ^ 𝑘 almost surely. Let 𝐸 be the multiset of loss functions { 𝐿 𝒮 : 𝒮 ⊂ { 1 , … , 𝑛 + 𝑘 } , | 𝒮 |

𝑘 } . Using the same argument in the end of the proof of Theorem 2.1 and the right-continuity of 𝐿 𝒮 , we can show that

𝔼 ⁢ [ 𝐿 { 𝑛 + 1 , … , 𝑛 + 𝑘 } ⁢ ( 𝜆 ^ 𝑘 ′ ) ∣ 𝐸 ]

𝑘 ! ⁢ 𝑛 ! ( 𝑛 + 𝑘 ) ! ⁢ ∑ 𝒮 ⊂ { 1 , … , 𝑛 + 𝑘 } , | 𝒮 |

𝑘 𝐿 𝒮 ⁢ ( 𝜆 ) ≤ 𝛼 .

The proof is then completed by the law of iterated expectation. ∎

Report Issue Report Issue for Selection Generated by L A T E xml Instructions for reporting errors

We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:

Click the "Report Issue" button. Open a report feedback form via keyboard, use "Ctrl + ?". Make a text selection and click the "Report Issue for Selection" button near your cursor. You can use Alt+Y to toggle on and Alt+Shift+Y to toggle off accessible reporting links at each section.

Our team has already identified the following issues. We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.

Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion, and welcome developer contributions.