2302/2302.03791.md

Title: How to Trust Your Diffusion Model: A Convex Optimization Approach to Conformal Risk Control

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

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 1Introduction 2Background 3How to Trust Your Diffusion Model 4Experiments 5Conclusions License: CC BY 4.0 arXiv:2302.03791v3 [stat.ML] 27 Dec 2023 How to Trust Your Diffusion Model: A Convex Optimization Approach to Conformal Risk Control Jacopo Teneggi1 2 3 Matthew Tivnan4 J. Webster Stayman4 Jeremias Sulam 1 4 3 Abstract

Score-based generative modeling, informally referred to as diffusion models, continue to grow in popularity across several important domains and tasks. While they provide high-quality and diverse samples from empirical distributions, important questions remain on the reliability and trustworthiness of these sampling procedures for their responsible use in critical scenarios. Conformal prediction is a modern tool to construct finite-sample, distribution-free uncertainty guarantees for any black-box predictor. In this work, we focus on image-to-image regression tasks and we present a generalization of the Risk-Controlling Prediction Sets (RCPS) procedure, that we term 𝐾 -RCPS, which allows to (i) provide entrywise calibrated intervals for future samples of any diffusion model, and (ii) control a certain notion of risk with respect to a ground truth image with minimal mean interval length. Differently from existing conformal risk control procedures, ours relies on a novel convex optimization approach that allows for multidimensional risk control while provably minimizing the mean interval length. We illustrate our approach on two real-world image denoising problems: on natural images of faces as well as on computed tomography (CT) scans of the abdomen, demonstrating state of the art performance.

1Introduction

Generative modeling is one of the longest standing tasks of classical and modern machine learning [12]. Recently, the foundational works by Song and Ermon [50], Song et al. [52], Pang et al. [43] on sampling via score-matching [27] and by Ho et al. [23] on denoising diffusion models [49] paved the way for a new class of score-based generative models, which solve a reverse-time stochastic differential equation (SDE) [53, 2]. These models have proven remarkably effective on both unconditional (i.e., starting from random noise) and conditional (e.g., inpainting, denoising, super-resolution, or class-conditional) sample generation across a variety of fields [61, 17]. For example, score-based generative models have been applied to inverse problems in general computer vision and medical imaging [29, 32, 31, 59, 55, 54], 3D shape generation [62, 60, 42], and even in protein design [25, 16, 58, 28].

These strong empirical results highlight the potential of score-based generative models. However, they currently lack of precise statistical guarantees on the distribution of the generated samples, which hinders their safe deployment in high-stakes scenarios [26]. For example, consider a radiologist who is shown a computed tomography (CT) scan of the abdomen of a patient reconstructed via a score-based generative model. How confident should they be of the fine-grained details of the presented image? Should they trust that the model has not hallucinated some of the features (e.g., calcifications, blood vessels, or nodules) involved in the diagnostic process? Put differently, how different will future samples be from the presented image, and how far can we expect them to be from the ground truth image?

In this work we focus on image-to-image regression problems, where we are interested in recovering a high-quality ground truth image given a low-quality observation. While our approach is general, we focus on the problem of image denoising as a running example. We address the questions posed above on the reliability of score-based generative models (and, more generally, of any sampling procedure) through the lens of conformal prediction [44, 57, 38, 48, 3] and conformal risk control [10, 4, 5] which provide any black-box predictor with distribution-free, finite-sample uncertainty guarantees. In particular, the contribution of this paper is three-fold:

1.

Given a fixed score network, a low-quality observation, and any sampling procedure, we show how to construct valid entrywise calibrated intervals that provide coverage of future samples, i.e. future samples (on the same observation) will fall within the intervals with high probability;

2.

We introduce a novel high-dimensional conformal risk control procedure that minimizes the mean interval length directly, while guaranteeing the number of pixels in the ground truth image that fall outside of these intervals is below a user-specified level on future, unseen low-quality observations;

3.

We showcase our approach for denoising of natural face images as well as for computed tomography of the abdomen, achieving state of the art results in mean interval length.

Going back to our example, providing such uncertainty intervals with provable statistical guarantees would improve the radiologist’s trust in the sense that these intervals precisely characterize the type of tissue that could be reconstructed by the model. Lastly, even though our contributions are presented in the context of score-based generative modeling for regression problems—given their recent popularity [33, 61, 18]—our results are broadly applicable to any sampling procedure, and we will comment on potential direct extensions where appropriate.

1.1Related work Image-to-Image Risk Control

Previous works have explored conformal risk control procedures for image-to-image regression tasks. In particular, Angelopoulos et al. [6] show how to construct set predictors from heuristic notions of uncertainty (e.g., quantile regression [34, 45]) for any image regressor, and how to calibrate the resulting intervals according to the original RCPS procedure of Bates et al. [10]. Kutiel et al. [35] move beyond set predictors and propose a mask-based conformal risk control procedure that allows for notions of distance between the ground truth and predicted images other than interval-based ones. Finally, and most closely to this paper, Horwitz and Hoshen [26] sketch ideas of conformal risk control for diffusion models with the intention to integrate quantile regression and produce heuristic sampling bounds without the need to sample several times. Horwitz and Hoshen [26] also use the original RCPS procedure to guarantee risk control. Although similar in spirit, the contribution of this paper focuses on a high-dimensional generalization of the original RCPS procedure that formally minimizes the mean interval length. Our proposed procedure is agnostic of the notion of uncertainty chosen to construct the necessary set predictors.

2Background

First, we briefly introduce the necessary notation and general background information. Herein, we will refer to images as vectors in ℝ 𝑑 , such that 𝒳 ⊂ ℝ 𝑑 and 𝒴 ⊂ ℝ 𝑑 indicate the space of high-quality ground truth images, and low-quality observations, respectively. We assume both 𝒳 and 𝒴 to be bounded. For a general image-to-image regression problem, given a pair ( 𝑥 , 𝑦 ) drawn from an unknown distribution 𝒟 over 𝒳 × 𝒴 , the task is to retrieve 𝑥 ∈ 𝒳 given 𝑦 ∈ 𝒴 . This is usually carried out by means of a predictor 𝑓 : 𝒴 → 𝒳 that minimizes some notion of distance (e.g., MSE loss) between the ground truth images and reconstructed estimates on a set { ( 𝑥 𝑖 , 𝑦 𝑖 ) } 𝑖

1 𝑛 ∼ 𝒟 𝑛 of 𝑛 pairs of high- and low-quality images. For example, in the classical denoising problem, one has 𝑦

𝑥 + 𝑣 0 where 𝑣 0 ∼ 𝒩 ⁢ ( 0 , 𝜎 0 2 ⁢ 𝕀 ) is random Gaussian noise with variance 𝜎 0 2 , and one wishes to learn a denoiser 𝑓 such that 𝑓 ⁢ ( 𝑦 ) ≈ 𝑥 .

2.1Score-based Conditional Sampling

Most image-to-image regression problems are ill-posed: there exist several ground truth images that could have generated the same low-quality observation. This is easy to see for the classical denoising problem described above. Instead of a point predictor 𝑓 —which could approximate a maximum-a-posteriori (MAP) estimate—one is often interested in devising a sampling procedure 𝐹 : 𝒴 → 𝒳 for the posterior 𝑝 ⁢ ( 𝑥 | 𝑦 ) , which precisely describes the distribution of possible ground truth images that generated the observation 𝑦 . In real-world scenarios, however, the full joint ( 𝑥 , 𝑦 ) is unknown, and one must resort to approximate 𝑝 ⁢ ( 𝑥 | 𝑦 ) from finite data. It is known that for a general Itô process d ⁢ 𝑥

ℎ ⁢ ( 𝑥 , 𝑡 ) ⁢ d ⁢ 𝑡 + 𝑔 ⁢ ( 𝑡 ) ⁢ d ⁢ 𝑤 that perturbs an input 𝑥 into random noise [30], it suffices to know the Stein score ∇ 𝑥 log ⁡ 𝑝 𝑡 ⁢ ( 𝑥 ) [2, 39] to sample from 𝑝 ⁢ ( 𝑥 ) via the reverse-time process

d ⁢ 𝑥

[ ℎ ⁢ ( 𝑥 , 𝑡 ) − 𝑔 ⁢ ( 𝑡 ) 2 ⁢ ∇ 𝑥 log ⁡ 𝑝 𝑡 ⁢ ( 𝑥 ) ] ⁢ d ⁢ 𝑡 + 𝑔 ⁢ ( 𝑡 ) ⁢ d ⁢ 𝑤 ¯ ,

(1)

where ℎ ⁢ ( 𝑥 , 𝑡 ) and 𝑔 ⁢ ( 𝑡 ) are a drift and diffusion term, respectively, and d ⁢ 𝑤 and d ⁢ 𝑤 ¯ are forward- and reverse-time standard Brownian motion.5 Furthermore, if the likelihood 𝑝 ⁢ ( 𝑦 | 𝑥 ) is known—which is usually the case for image-to-image regression problems—it is possible to condition the sampling procedure on an observation 𝑦 . Specifically, by Bayes’ rule, it follows that ∇ 𝑥 log ⁡ 𝑝 𝑡 ⁢ ( 𝑥 | 𝑦 )

∇ 𝑥 log ⁡ 𝑝 𝑡 ⁢ ( 𝑦 | 𝑥 ) + ∇ 𝑥 log ⁡ 𝑝 𝑡 ⁢ ( 𝑥 ) which can be plugged-in into the reverse-time SDE in Equation 1 to sample from 𝑝 ⁢ ( 𝑥 | 𝑦 ) .

Recent advances in generative modeling by Song and Ermon [50], Song et al. [53] showed that one can efficiently train a time-conditional score network 𝑠 ⁢ ( 𝑥 ~ , 𝑡 ) to approximate the score ∇ 𝑥 log ⁡ 𝑝 𝑡 ⁢ ( 𝑥 ~ ) via denoising score-matching [27]. In this way, given a forward-time SDE that models the observation process, a score network 𝑠 ⁢ ( 𝑥 ~ , 𝑡 ) ≈ ∇ 𝑥 log ⁡ 𝑝 𝑡 ⁢ ( 𝑥 ~ ) , and the likelihood term 𝑝 ⁢ ( 𝑦 | 𝑥 ~ ) , one can sample from 𝑝 ⁢ ( 𝑥 | 𝑦 ) by solving the conditional reverse-time SDE with any discretization (e.g., Euler-Maruyama) or predictor-corrector scheme [53]. While these models perform remarkably well in practice, limited guarantees exist on the distributions that they sample from [37]. Instead, we will provide guarantees for diffusion models by leveraging ideas of conformal prediction and conformal risk control, which we now introduce.

2.2Conformal Prediction

Conformal prediction has a rich history in mathematical statistics [57, 44, 56, 8, 9, 22].6 It comprises various methodologies to construct finite-sample, statistically valid uncertainty guarantees for general predictors without making any assumption on the distribution of the response (i.e., they are distribution-free). It particular, these methods construct valid prediction sets that provide coverage, which we now define.

Definition 2.1 (Coverage [48]).

Let 𝑧 1 , … , 𝑧 𝑚 , 𝑧 𝑚 + 1 be 𝑚 + 1 exchangeable random variables drawn from the same unknown distribution 𝒬 over 𝒵 . For a desired miscoverage level 𝛼 ∈ [ 0 , 1 ] , a set 𝒞 ⊆ 2 𝒵 that only depends on 𝑧 1 , … , 𝑧 𝑚 provides coverage if

ℙ ⁢ [ 𝑧 𝑚 + 1 ∈ 𝒞 ] ≥ 1 − 𝛼 .

(2)

We remark that the notion of coverage defined above was introduced in the context of classification problems, where one is interested in guaranteeing that the true, unseen label of a future sample will be in the prediction set 𝒞 with high probability. It is immediate to see how conformal prediction conveys a very precise notion of uncertainty—the larger 𝒞 has to be in order to guarantee coverage, the more uncertain the underlying predictor. We refer the interested reader to [48, 3] for classical examples of conformal prediction.

In many scenarios (e.g., regression), the natural notion of uncertainty may be different from miscoverage as described above (e.g., ℓ 2 norm). We now move onto presenting conformal risk control, which extends the coverage to any notion of risk.

2.3Conformal Risk Control

Let ℐ : 𝒴 → 𝒳 ′ be a general set-valued predictor from 𝒴 into 𝒳 ′ ⊆ 2 𝒳 . Consider a nonnegative loss ℓ : 𝒳 × 𝒳 ′ → ℝ measuring the discrepancy between a ground truth 𝑥 and the predicted intervals ℐ ⁢ ( 𝑦 ) . We might be interested in guaranteeing that this loss will be below a certain tolerance 𝜖 ≥ 0 with high probability on future, unseen samples 𝑦 for which we do not know the ground truth 𝑥 . Conformal risk control [10, 4, 5] extends ideas of conformal prediction in order to select a specific predictor ℐ that controls the risk 𝔼 ⁢ [ ℓ ⁢ ( 𝑥 , ℐ ⁢ ( 𝑦 ) ) ] in the following sense.

Definition 2.2 (Risk Controlling Prediction Sets).

Let 𝒮 cal

{ ( 𝑥 𝑖 , 𝑦 𝑖 ) } 𝑖

1 𝑛 ∼ 𝒟 𝑛 be a calibration set of 𝑛 i.i.d. samples from an unknown distribution 𝒟 over 𝒳 × 𝒴 . For a desired risk level 𝜖 ≥ 0 and a failure probability 𝛿 ∈ [ 0 , 1 ] , a random set-valued predictor ℐ : 𝒴 → 𝒳 ′ ⊆ 2 𝒳 is an ( 𝜖 , 𝛿 ) -RCPS w.r.t. a loss function ℓ : 𝒳 × 𝒳 ′ → ℝ if

ℙ 𝒮 cal ⁢ [ 𝔼 ( 𝑥 , 𝑦 ) ∼ 𝒟 ⁢ [ ℓ ⁢ ( 𝑥 , ℐ ⁢ ( 𝑦 ) ) ] ≤ 𝜖 ] ≥ 1 − 𝛿 .

(3)

Bates et al. [10] introduced the first conformal risk control procedure for monotonically nonincreasing loss functions, those that satisfy, for a fixed 𝑥 ,

ℐ ⁢ ( 𝑦 ) ⊂ ℐ ′ ⁢ ( 𝑦 ) ⟹ ℓ ⁢ ( 𝑥 , ℐ ′ ⁢ ( 𝑦 ) ) ≤ ℓ ⁢ ( 𝑥 , ℐ ⁢ ( 𝑦 ) ) .

(4)

In this way, increasing the size of the sets cannot increase the value of the loss. Furthermore, assume that for a fixed input 𝑦 the family of set predictors { ℐ 𝜆 ⁢ ( 𝑦 ) } 𝜆 ∈ Λ , indexed by 𝜆 ∈ Λ , Λ ⊂ ℝ ¯ ≔ ℝ ∪ { ± ∞ } , satisfies the following nesting property [22]

𝜆 1 < 𝜆 2 ⟹ ℐ 𝜆 1 ⁢ ( 𝑦 ) ⊂ ℐ 𝜆 2 ⁢ ( 𝑦 ) .

(5)

Denote 𝑅 ⁢ ( 𝜆 )

𝔼 ⁢ [ ℓ ⁢ ( 𝑥 , ℐ 𝜆 ⁢ ( 𝑦 ) ) ] the risk of ℐ 𝜆 ⁢ ( 𝑦 ) and 𝑅 ^ ⁢ ( 𝜆 ) its empirical estimate over a calibration set 𝒮 cal

{ ( 𝑥 𝑖 , 𝑦 𝑖 ) } 𝑖

1 𝑛 . Finally, let 𝑅 ^ + ⁢ ( 𝜆 ) be a pointwise upper confidence bound (UCB) that covers the risk, that is

ℙ ⁢ [ 𝑅 ⁢ ( 𝜆 ) ≤ 𝑅 ^ + ⁢ ( 𝜆 ) ] ≥ 1 − 𝛿

(6)

for each, fixed value of 𝜆 —such that can be derived by means of concentration inequalities (e.g., Hoeffding’s inequality [24], Bentkus’ inequality [11], or respective hybridization [10]).7 With these elements, Bates et al. [10] show that choosing

𝜆 ^

inf { 𝜆 ∈ Λ : 𝑅 ^ + ⁢ ( 𝜆 ′ ) < 𝜖 , ∀ 𝜆 ′ ≥ 𝜆 }

(7)

guarantees that ℐ 𝜆 ^ ⁢ ( 𝑦 ) is an ( 𝜖 , 𝛿 ) -RCPS according to Definition 2.2. In other words, choosing 𝜆 ^ as the smallest 𝜆 such that the UCB is below the desired level 𝜖 for all values of 𝜆 ≥ 𝜆 ^ controls the risk al level 𝜖 with probability at least 1 − 𝛿 . For the sake of completeness, we include the original conformal risk control procedure in Algorithm 2 in Appendix B.

Equipped with these general concepts, we now move onto presenting the contributions of this work.

3How to Trust Your Diffusion Model

We now go back to the main focus of this paper: solving image-to-image regression problems with diffusion models. Rather than a point-predictor 𝑓 : 𝒴 → 𝒳 , we assume to have access to a stochastic sampling procedure 𝐹 : 𝒴 → 𝒳 such that 𝐹 ⁢ ( 𝑦 ) is a random variable with unknown distribution 𝒬 𝑦 —that hopefully approximates the posterior distribution of 𝑥 given 𝑦 , i.e. 𝒬 𝑦 ≈ 𝑝 ⁢ ( 𝑥 | 𝑦 ) . However, we make no assumptions on the quality of this approximation for our results to hold. As described in Section 2.1, 𝐹 can be obtained by means of a time-conditional score network 𝑠 ⁢ ( 𝑥 ~ , 𝑡 ) and a reverse-time SDE. While our results are applicable to any sampling procedure, we present them in the context of diffusion models because of their remarkable empirical results and increasing use in critical applications [61, 17].

One can identify three separate sources of randomness in a general stochastic image-to-image regression problem: (i) the unknown prior 𝑝 ⁢ ( 𝑥 ) over the space of ground-truth images, as 𝑥 ∼ 𝑝 ⁢ ( 𝑥 ) , (ii) the randomness in the observation process of 𝑦 (which can be modeled by a forward-time SDE over 𝑥 ), and finally (iii) the stochasticity in the sampling procedure 𝐹 ⁢ ( 𝑦 ) . We will first provide conformal prediction guarantees for a fixed observation 𝑦 , and then move onto conformal risk control for the ground truth image 𝑥 .

3.1Calibrated Quantiles for Future Samples

Given the same low-quality (e.g., noisy) observation 𝑦 , where will future unseen samples from 𝐹 ⁢ ( 𝑦 ) ∼ 𝒬 𝑦 fall? How concentrated will they be? Denote ℐ : 𝒴 → 𝒳 ′ a (random) set-valued predictor from 𝒴 ⊂ ℝ 𝑑 into a space of sets 𝒳 ′ ⊆ 2 𝒳 over 𝒳 ⊂ ℝ 𝑑 (e.g., 𝒳

[ 0 , 1 ] 𝑑 , 𝒳 ′ ⊆ 2 [ 0 , 1 ] 𝑑 ). We extend the notion of coverage in Definition 2.1 to entrywise coverage, which we now make precise.

Definition 3.1 (Entrywise coverage).

Let 𝑧 1 , … , 𝑧 𝑚 , 𝑧 𝑚 + 1 be 𝑚 + 1 exchangeable random vectors drawn from the same unknown distribution 𝒬 over 𝒳 ⊂ ℝ 𝑑 . For a desired miscoverage level 𝛼 ∈ [ 0 , 1 ] , a set ℐ ⊆ 2 𝒳 that only depends on 𝑧 1 , … , 𝑧 𝑚 provides entrywise coverage if

ℙ ⁢ [ ( 𝑧 𝑚 + 1 ) 𝑗 ∈ ℐ 𝑗 ] ≥ 1 − 𝛼

(8)

for each 𝑗 ∈ [ 𝑑 ] ≔ { 1 , … , 𝑑 } .

We stress that the definition above is different from notions of vector quantiles [13, 15] in the sense that coverage is not guaranteed over the entire new random vector 𝑧 𝑚 + 1 but rather along each dimension independently. Ideas of vector quantile regression (VQR) are complementary to the contribution of the current work and subject of ongoing research [21, 14, 47].

For a fixed observation 𝑦 , we use conformal prediction to construct a set predictor that provides entrywise coverage.

Lemma 3.2 (Calibrated quantiles guarantee entrywise coverage).

Let 𝐹 : 𝒴 → 𝒳 be a stochastic sampling procedure from 𝒴 ⊂ ℝ 𝑑 into 𝒳 ⊂ ℝ 𝑑 . Given 𝑦 ∈ 𝒴 , let 𝐹 1 , … , 𝐹 𝑚 , 𝐹 𝑚 + 1 be 𝑚 + 1 i.i.d. samples from 𝐹 ⁢ ( 𝑦 ) . For a desired miscoverage level 𝛼 ∈ [ 0 , 1 ] and for each 𝑗 ∈ [ 𝑑 ] , let 𝑙 ^ 𝑗 , 𝛼 , 𝑢 ^ 𝑗 , 𝛼 be the ⌊ ( 𝑚 + 1 ) ⁢ 𝛼 / 2 ⌋ / 𝑚 and ⌈ ( 𝑚 + 1 ) ⁢ ( 1 − 𝛼 / 2 ) ⌉ / 𝑚 entrywise calibrated empirical quantiles of 𝐹 1 , … , 𝐹 𝑚 . Then,

ℐ 𝛼 ⁢ ( 𝑦 ) 𝑗

[ 𝑙 ^ 𝑗 , 𝛼 , 𝑢 ^ 𝑗 , 𝛼 ]

(9)

provides entrywise coverage.

The simple proof of this result is included in Section A.1. We remark that, analogously to previous works [6, 26], the intervals in ℐ 𝛼 ⁢ ( 𝑦 ) are feature-dependent and they capture regions of the image where the sampling process 𝐹 ⁢ ( 𝑦 ) may have larger uncertainty. The intervals in ℐ 𝛼 ⁢ ( 𝑦 ) are statistically valid for any number of samples 𝑚 and any distribution 𝒬 𝑦 , i.e. they are not a heuristic notion of uncertainty. If the sampling procedure 𝐹 is a diffusion model, constructing ℐ 𝛼 ⁢ ( 𝑦 ) is agnostic of the discretization scheme used to solve the reverse-time SDE [53] and it does not require retraining the underlying score network, which can be a time-consuming and delicate process, especially when the size of the images is considerable. On the other hand, constructing the intervals ℐ 𝛼 ⁢ ( 𝑦 ) requires sampling a large enough number of times from 𝐹 ⁢ ( 𝑦 ) , which may seen cumbersome [26]. This is by construction and intention: diffusion models are indeed very useful in providing good (and varied) samples from the approximate posterior. In this way, practitioners do typically sample several realizations to get an empirical study of this distribution. In these settings, constructing the intervals ℐ 𝛼 ⁢ ( 𝑦 ) does not involve any additional computational costs. Furthermore, note that sampling is completely parallelizable, and so no extra complexity is incurred if a larger number of computing nodes are available.

3.2A Provable Approach to Optimal Risk Control

In this section, we will revisit the main ideas around conformal risk control introduced in Section 2.3 and generalize them into our proposed approach, 𝐾 -RCPS. Naturally, one would like a good conformal risk control procedure to yield the shortest possible interval lengths. Assume pixel intensities are normalized between [ 0 , 1 ] and consider the loss function

ℓ 01 ⁢ ( 𝑥 , ℐ ⁢ ( 𝑦 ) )

1 𝑑 ⁢ ∑ 𝑗 ∈ [ 𝑑 ] 𝟙 ⁢ [ 𝑥 𝑗 ∉ ℐ ⁢ ( 𝑦 ) 𝑗 ] ,

(10)

which counts the (average) number of ground truth pixels that fall outside of their respective intervals in ℐ ⁢ ( 𝑦 ) . The constant set-valued predictor 𝒰 ⁢ ( 𝑦 )

[ 0 , 1 ] 𝑑 would trivially control the risk, i.e. 𝑅 01 ⁢ ( 𝜆 )

𝔼 ⁢ [ ℓ 01 ⁢ ( 𝑥 , 𝒰 ⁢ ( 𝑦 ) ) ]

0 . Alas, such a predictor would be completely uninformative. Instead, let { ℐ 𝜆 ⁢ ( 𝑦 ) } 𝜆 ∈ Λ , Λ ⊂ ℝ ¯ be a family of predictors that satisfies the nesting property in Equation 5. In particular, we propose the following additive parametrization in 𝜆

ℐ 𝜆 ⁢ ( 𝑦 ) 𝑗

[ 𝑙 ^ 𝑗 − 𝜆 , 𝑢 ^ 𝑗 + 𝜆 ]

(11)

for some lower and upper endpoints 𝑙 ^ 𝑗 < 𝑢 ^ 𝑗 that may depend on 𝑦 . For this particularly chosen family of nested predictors, it follows that the mean interval length is

𝐼 ¯ ⁢ ( 𝜆 )

1 𝑑 ⁢ ∑ 𝑗 ∈ [ 𝑑 ] ( 𝑢 ^ 𝑗 − 𝑙 ^ 𝑗 ) + 2 ⁢ 𝜆 ,

(12)

a linear function of 𝜆 . Moreover, we can instantiate 𝑙 ^ 𝑗 and 𝑢 ^ 𝑗 to be the calibrated quantiles with entrywise coverage, i.e. ℐ 𝜆 𝛼 ⁢ ( 𝑦 )

[ 𝑙 ^ 𝑗 , 𝛼 − 𝜆 , 𝑢 ^ 𝑗 , 𝛼 + 𝜆 ] .

For such a class of predictors—since the ℓ 01 loss is monotonically nonincreasing—the original RCPS procedure (see Equation 7) is equivalent to the following constrained optimization problem

𝜆 ^

arg ⁡ min 𝜆 ∈ Λ ⁡ 𝐼 ¯ ⁢ ( 𝜆 ) s.t. 𝑅 ^ 01 + ⁢ ( 𝜆 ′ ) < 𝜖 , ∀ 𝜆 ′ ≥ 𝜆

(P 1 )

which naturally minimizes 𝜆 . However, optimizing the mean interval length over a single scalar parameter 𝜆 is suboptimal in general, as shown in Figure 1. With abuse of notation—we do not generally refer to vectors with boldface—let { ℐ 𝝀 ⁢ ( 𝑦 ) } 𝝀 ∈ Λ 𝑑 be a family of predictors indexed by a 𝑑 -dimensional vector 𝝀

( 𝜆 1 , … , 𝜆 𝑑 ) that satisfies the nesting property in Equation 5 in an entrywise fashion. A natural extension of Equation 11 is then

ℐ 𝝀 ⁢ ( 𝑦 ) 𝑗

[ 𝑙 ^ 𝑗 − 𝜆 𝑗 , 𝑢 ^ 𝑗 + 𝜆 𝑗 ] ,

(13)

from which one can define an equivalent function 𝐼 ¯ ⁢ ( 𝝀 ) . In particular, using the calibrated intervals as before, define

ℐ 𝝀 𝛼 ⁢ ( 𝑦 )

[ 𝑙 ^ 𝑗 , 𝛼 − 𝜆 𝑗 , 𝑢 ^ 𝑗 , 𝛼 + 𝜆 𝑗 ] .

(14)

Note now that ℓ 01 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) ) is entrywise monotonically nonincreasing. For fixed vectors 𝝀 ~ ∈ ℝ 𝑑 and 𝜼 ∈ ℝ 𝑑 in the positive orthant (i.e., 𝜼 ≥ 0 , entrywise), denote 𝚲 ~

𝝀 ~ + 𝜔 ⁢ 𝜼 , 𝜔 ∈ Λ the set of points on a line with offset 𝝀 ~ and direction 𝜼 parametrized by 𝜔 . Then, the 𝑑 -dimensional extension of (P 1 ) becomes

𝝀 ^

arg ⁡ min 𝝀 ∈ 𝚲 ~ ⁢ ∑ 𝑗 ∈ [ 𝑑 ] 𝜆 𝑗 s.t. 𝑅 ^ 01 + ⁢ ( 𝝀 + 𝛽 ⁢ 𝜼 ) < 𝜖 , ∀ 𝛽 ≥ 0 .

(P 𝑑 )

We include an explicit analytical expression for 𝑅 ^ 01 + ⁢ ( 𝝀 + 𝜼 ) in Appendix C. Intuitively, 𝝀 ^ minimizes the sum of its entries such that the UCB is smaller than 𝜖 for all points to its right along the direction of 𝜼 parametrized by 𝛽 . We now show a general high-dimensional risk control result that holds for any entrywise monotonically nonincreasing loss function ℓ (and not just ℓ 01 as presented in (P 𝑑 )) with risk 𝑅 ⁢ ( 𝝀 ) , empirical estimate 𝑅 ^ ⁢ ( 𝝀 ) and respective UCB 𝑅 ^ + ⁢ ( 𝝀 ) .8

(a) 𝜇

[ − 1 , 1 ] 𝑇 . (b) 𝜇

[ − 2 , 0.75 ] 𝑇 . Figure 1:Pictorial representation of the suboptimality of the choice of a single scalar parameter 𝜆 w.r.t. the mean interval length. 𝒮 cal ∼ 𝒩 ⁢ ( 𝜇 , 𝕀 2 ) 𝑛 , 𝑛

128 , and ( ℐ 𝝀 ) 𝑗

[ − 1 − 𝜆 𝑗 , 1 + 𝜆 𝑗 ] , 𝝀

( 𝜆 1 , 𝜆 2 ) . For 𝜖

𝛿

0.1 , 𝑅 ^ 01 + ⁢ ( 𝝀 ) is obtained via Hoeffding-Bentkus hybridization. Green areas indicate regions where 𝑅 ^ 01 + ⁢ ( 𝝀 ) ≤ 𝜖 , and conversely for red regions. 0(a) Shows that when features are concentrated symmetrically around the intervals, minimizing 𝜆 1

𝜆 2

𝜆 (blue star) minimizes the mean interval length, while 0(b) shows that in the general case, the optimal 𝝀 (orange star) may have 𝜆 1 ≠ 𝜆 2 . Δ highlights the gain in mean interval length obtained by choosing the orange star instead of the blue one. Theorem 3.3 (Optimal mean interval length risk control).

Let ℓ : 𝒳 × 𝒳 ′ → ℝ , 𝒳 ′ ⊆ 2 𝒳 , 𝒳 ⊂ ℝ 𝑑 be an entrywise monotonically nonincreasing function and let { ℐ 𝛌 ⁢ ( 𝑦 )

[ 𝑙 ^ 𝑗 − 𝜆 𝑗 , 𝑢 ^ 𝑗 + 𝜆 𝑗 ] } 𝛌 ∈ Λ 𝑑 be a family of set-valued predictors ℐ : 𝒴 → 𝒳 ′ , 𝒴 ⊂ ℝ 𝑑 indexed by 𝛌 ∈ Λ 𝑑 , Λ ⊂ ℝ ¯ , for some lower and upper bounds 𝑙 ^ 𝑗 < 𝑢 ^ 𝑗 that may depend on 𝑦 . Given 𝚲 ~

𝛌 ~ + 𝜔 ⁢ 𝛈 , 𝜔 ∈ Λ , for fixed 𝛌 ~ ∈ ℝ 𝑑 and 𝛈 ∈ ℝ 𝑑 , 𝛈 ≥ 0 , if

𝝀 ^

arg ⁡ min 𝝀 ∈ 𝚲 ~ ⁢ ∑ 𝑗 ∈ [ 𝑑 ] 𝜆 𝑗 s.t. 𝑅 ^ + ⁢ ( 𝝀 + 𝛽 ⁢ 𝜼 ) < 𝜖 , ∀ 𝛽 ≥ 0

(15)

then ℐ 𝛌 ^ ⁢ ( 𝑦 ) is an ( 𝜖 , 𝛿 ) -RCPS and 𝛌 ^ minimizes the mean interval length over 𝚲 ~ .

The proof is included in Section A.2. Since ℓ 01 is entrywise monotonically nonincreasing, it follows that the solution to (P 𝑑 ) controls risk. The attentive reader will have noticed (as shown in Figure 1) that the constraint set 𝑅 ^ 01 + ⁢ ( 𝝀 ) ≤ 𝜖 need not be convex. Furthermore, and as shown in Figure 1(b), ℓ 01 is not convex in 𝝀 . Hence, it is not possible to optimally solve (P 𝑑 ) directly. Instead, we relax it to a convex optimization problem by means of a convex upper bound9

ℓ 𝛾 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) )

1 𝑑 ⁢ ∑ 𝑗 ∈ [ 𝑑 ] [ 2 ⁢ ( 1 + 𝑞 ) 𝐼 ⁢ ( 𝝀 ) 𝑗 ⁢ | 𝑥 𝑗 − 𝑐 𝑗 | − 𝑞 ] + ,

(16)

where 𝑞

𝛾 / ( 1 − 𝛾 ) , 𝛾 ∈ [ 0 , 1 ) , 𝐼 ⁢ ( 𝝀 ) 𝑗

𝑢 ^ 𝑗 − 𝑙 ^ 𝑗 + 2 ⁢ 𝜆 𝑗 , 𝑐 𝑗

( 𝑢 ^ 𝑗 + 𝑙 ^ 𝑗 ) / 2 , and [ ⋅ ] +

max ⁡ ( 0 , ⋅ ) . As shown in Figure 1(a), the hyperparameter 𝛾 controls the degree of relaxation by means of changing the portion of the intervals [ 𝑙 ^ 𝑗 , 𝑢 ^ 𝑗 ] where the loss is 0. This way, 𝛾

0 retrieves the ℓ 1 loss centered at 𝑐 𝑗 , and lim 𝛾 → 1 ℓ 𝛾

∞ if ∃ 𝑗 ∈ [ 𝑑 ] : 𝑥 𝑗 ∉ [ 𝑙 ^ 𝑗 , 𝑢 ^ 𝑗 ] and 0 otherwise.

(a) ℓ 01 , ℓ 𝛾 as a function of 𝑥 . (b) ℓ 01 , ℓ 𝛾 as a function of 𝜆 . Figure 2:Visualization of ℓ 01 ⁢ ( 𝑥 , ℐ 𝜆 ⁢ ( 𝑦 ) ) and ℓ 𝛾 ⁢ ( 𝑥 , ℐ 𝜆 ⁢ ( 𝑦 ) ) for ℐ 𝜆 ⁢ ( 𝑦 )

[ 0.50 − 𝜆 , 1.50 + 𝜆 ] , 𝛾 ∈ { 0 , 0.5 , 0.9 } . In 1(a) 𝜆

0 , and in 1(b) 𝑥

1.6 .

While one can readily propose a convex alternative to (P 𝑑 ) by means of this new loss, we instead propose a generalization of this idea in our final problem formulation

𝝀 ~ 𝐾

arg ⁡ min 𝝀 ∈ Λ 𝐾 ⁢ ∑ 𝑘 ∈ [ 𝐾 ] 𝑛 𝑘 ⁢ 𝜆 𝑘 s.t. 𝑅 ^ 𝛾 ⁢ ( 𝑀 ⁢ 𝝀 ) ≤ 𝜖 ,

(P 𝐾 )

for any user-defined 𝐾 -partition of the [ 𝑑 ] features—which can be identified by a membership matrix 𝑀 ∈ { 0 , 1 } 𝑑 × 𝐾 where each feature belongs to (only) one of the 𝐾 groups with 𝑛 𝑘 ≔ | { 𝑗 ∈ [ 𝑑 ] : 𝑀 𝑗 ⁢ 𝑘

1 } | , ∑ 𝑘 ∈ [ 𝐾 ] 𝑛 𝑘

𝑑 . As we will shortly see, it will be useful to define these groups as the empirical quantiles; i.e. set 𝑀 as that assigning each feature to their respective 𝑘 th quantile of the entrywise empirical loss over the optimization set (which is a vector in ℝ 𝑑 ). We remark that the constrain set in (P 𝐾 ) is defined on the empirical estimate of the risk of ℐ 𝝀 ⁢ ( 𝑦 ) and it does not involve the computation of the UCB. Then, (P 𝐾 ) can be solved with any standard off-the-shelf convex optimization software (e.g., CVXPY [19, 1], MOSEK [7]).

Our novel conformal risk control procedure, 𝐾 -RCPS, finds a vector 𝝀 ^ 𝐾 that approximates a solution to the nonconvex optimization problem (P 𝑑 ) via a two step procedure:

1.

First obtaining the optimal solution 𝝀 ~ 𝐾 to a user-defined (P 𝐾 ) problem, and then

2.

Choosing 𝛽 ^ ∈ Λ such that

𝛽 ^

inf { 𝛽 ∈ Λ : 𝑅 ^ 01 + ⁢ ( 𝑀 ⁢ 𝝀 ~ 𝐾 + 𝛽 ′ ⁢ 𝟏 ) < 𝜖 , ∀ 𝛽 ′ ≥ 𝛽 }

and return 𝝀 ^ 𝐾

𝑀 ⁢ 𝝀 ~ 𝐾 + 𝛽 ^ ⁢ 𝟏 .

Intuitively, the 𝐾 -RCPS algorithm is equivalent to performing the original RCPS procedure along the line 𝑀 ⁢ 𝝀 ~ 𝐾 + 𝛽 ⁢ 𝟏 parametrized by 𝛽 . We remark that—as noted in Theorem 3.3—any choice of 𝜼 ≥ 0 provides a valid direction along which to perform the RCPS procedure. Here, we choose 𝟏 because it is precisely the gradient of the objective function. Future work entails devising more sophisticated algorithms to approximate the solution of (P 𝑑 ).

Algorithm 1 𝐾 -RCPS 1:  Input: risk level 𝜖 ≥ 0 , failure probability 𝛿 ∈ [ 0 , 1 ] , calibration set 𝒮 cal

{ ( 𝑥 𝑖 , 𝑦 𝑖 ) } 𝑖

1 𝑛 of 𝑛 i.i.d. samples such that 𝑛

𝑛 opt + 𝑛 RCPS , membership function ℳ , family of set-valued predictors { ℐ 𝝀 ⁢ ( 𝑦 )

[ 𝑙 ^ 𝑗 − 𝜆 𝑗 , 𝑢 𝑗 + 𝜆 𝑗 ] } 𝝀 ∈ Λ 𝑑 , initial (large) value 𝛽 max , stepsize d ⁢ 𝛽

0 . 2:  Split 𝒮 cal into 𝒮 opt , 𝒮 RCPS 3:   𝑀 ← ℳ ⁢ ( 𝒮 opt ) 4:   𝝀 ~ 𝐾 ← SOLVE-PK ⁢ ( 𝒮 opt , 𝑀 ) 5:   𝝀 ← 𝑀 ⁢ 𝝀 ~ 𝐾 + 𝛽 max ⁢ 𝟏 6:   𝑅 ^ 01 + ⁢ ( 𝝀 ) ← 0 7:  while  𝑅 ^ 01 + ⁢ ( 𝝀 ) ≤ 𝜖  do 8:      𝝀 prev ← 𝝀 9:      𝝀 ← 𝝀 − ( d ⁢ 𝛽 ) ⁢ 𝟏 10:      𝝀 ← [ 𝝀 ] + 11:      𝑅 ^ 01 ⁢ ( 𝝀 ) ← 1 / 𝑛 RCPS ⋅ ∑ ( 𝑥 𝑖 , 𝑦 𝑖 ) ∈ 𝒮 RCPS ℓ 01 ⁢ ( 𝑥 𝑖 , ℐ 𝝀 ⁢ ( 𝑦 𝑖 ) ) 12:      𝑅 ^ 01 + ⁢ ( 𝝀 ) ← UCB ⁢ ( 𝑛 RCPS , 𝛿 , 𝑅 ^ 01 ⁢ ( 𝝀 ) ) 13:  end while 14:   𝝀 ^ 𝐾 ← 𝝀 prev 15:  return 𝝀 ^ 𝐾

Algorithm 1 implements the 𝐾 -RCPS procedure for any calibration set 𝒮 cal

{ ( 𝑥 𝑖 , 𝑦 𝑖 ) } 𝑖

1 𝑛 , any general family of set-valued predictors of the form { ℐ 𝝀

[ 𝑙 ^ 𝑗 − 𝜆 𝑗 , 𝑢 ^ 𝑗 + 𝜆 𝑗 ] } 𝝀 ∈ Λ 𝑑 , any membership function ℳ : { 𝒳 × 𝒴 } 𝑛 → { 0 , 1 } 𝑑 × 𝐾 , and a general UCB ⁢ ( 𝑛 , 𝛿 , 𝑅 ^ ⁢ ( 𝝀 ) ) that accepts a number of samples 𝑛 , a failure probability 𝛿 , and an empirical risk 𝑅 ^ ⁢ ( 𝝀 ) and that returns a pointwise upper confidence bound 𝑅 ^ + ⁢ ( 𝝀 ) that satisfies Equation 6. We remark that, following the split fixed sequence testing framework introduced in Angelopoulos et al. [4] and applied in previous work [36], the membership matrix and its optimization problem (P 𝐾 ) are computed on a subset 𝒮 opt of the calibration set 𝒮 cal , such that the direction 𝑀 ⁢ 𝝀 ~ 𝐾 + 𝛽 ⁢ 𝟏 along which to perform the RCPS procedure is chosen before looking at the data 𝒮 RCPS

𝒮 cal ∖ 𝒮 opt . We note that 𝐾 -RCPS allows for some of the entries in 𝝀 ^ 𝐾 to be set to 0, which preserves the original intervals such that—if they are obtained as described in Section 3.1—they still provide entrywise coverage of future samples at the desired level 𝛼 .

We now move onto showcasing the advantage of 𝐾 -RCPS in terms on mean interval length on two real-world high dimensional denoising problems: one on natural images of faces as well as on CT scans of the abdomen.

4Experiments (a)CelebA dataset, 𝜎 0 2

1.0 , 𝛼

0.10 . (b)AbdomenCT-1K dataset, 𝜎 0 2

0.4 , 𝛼

0.20 . Figure 3:Calibrated quantiles ℐ 𝛼 ⁢ ( 𝑦 ) computed on 128 samples from 𝐹 ⁢ ( 𝑦 ) for noisy inputs 𝑦 with noise level 𝜎 0 2 . The difference 𝑢 ^ 𝛼 − 𝑙 ^ 𝛼 represents intervals sizes (i.e., larger intervals indicate larger uncertainty).

As a reminder, the methodological contribution of this paper is two-fold: ( 𝑖 ) we propose to use the calibrated quantiles ℐ 𝛼 ⁢ ( 𝑦 ) as a statistically valid notion of uncertainty for diffusion models, and ( 𝑖 ⁢ 𝑖 ) we introduce the 𝐾 -RCPS procedure to guarantee high-dimensional risk control. Although it is natural to use the two in conjunction, we remark that the 𝐾 -RCPS procedure is agnostic of the notion of uncertainty and it can be applied to any nested family of set predictors { ℐ 𝝀 ⁢ ( 𝑦 ) } 𝝀 ∈ Λ 𝑑 that satisfy the additive parametrization in Equation 13. Therefore, we compare 𝐾 -RCPS with the original RCPS algorithm on several baseline notions of uncertainty: quantile regression [6], MC-Dropout [20], N-Con 𝑓 ⁢ 𝑓 ⁢ 𝑢 ⁢ 𝑠 ⁢ 𝑖 ⁢ 𝑜 ⁢ 𝑛 [26], and naive (i.e., not calibrated) quantiles. We focus on denoising problems where 𝑦

𝑥 + 𝑣 0 with 𝑣 0 ∼ 𝒩 ⁢ ( 0 , 𝜎 0 2 ) , on two imaging datasets: the CelebA dataset [40] and the AbdomenCT-1K dataset [41]. In particular—for each dataset—we train:

•

A time-conditional score network 𝑠 ⁢ ( 𝑥 ~ , 𝑡 ) ≈ ∇ 𝑥 log ⁡ 𝑝 𝑡 ⁢ ( 𝑥 ~ ) following Song et al. [53] to sample from the posterior distribution 𝑝 ⁢ ( 𝑥 | 𝑦 ) as described in Section 2.1, and

•

a time-conditional image regressor 𝑓 : 𝒴 × ℝ → 𝒳 3 following Angelopoulos et al. [6] such that 𝑓 ⁢ ( 𝑦 , 𝑡 )

( 𝑞 ^ 𝛼 / 2 , 𝑥 ^ , 𝑞 ^ 1 − 𝛼 / 2 ) , where 𝑥 ^ ≈ 𝔼 ⁢ [ 𝑥 ∣ 𝑦 ] minimizes the MSE loss between the noisy observation 𝑦 and the ground truth 𝑥 , and 𝑞 ^ 𝛼 / 2 , 𝑞 ^ 1 − 𝛼 / 2 are the 𝛼 / 2 and 1 − 𝛼 / 2 quantile regressors of 𝑥 , respectively [34, 45, 6].

Both models are composed of the same NCSN++ backbone [53] with dropout 𝑝

0.10 for a fair comparison. We then fine-tune the original score network 𝑠 ⁢ ( 𝑥 ~ , 𝑡 ) according to the N-Con 𝑓 ⁢ 𝑓 ⁢ 𝑢 ⁢ 𝑠 ⁢ 𝑖 ⁢ 𝑜 ⁢ 𝑛 algorithm proposed by Horwitz and Hoshen [26] such that—similarly to the image regressor 𝑓 —the resulting time-conditional predictor 𝑠 ~ ⁢ ( 𝑦 , 𝑡 )

( 𝑞 ^ 𝛼 / 2 , 𝑞 ^ 1 − 𝛼 / 2 ) estimates the 𝛼 / 2 and 1 − 𝛼 / 2 quantile regressors of 𝑥 . Finally, in order to compare with MC-Dropout, we activate the dropout layers in the image regressor 𝑓 at inference time, and estimate the mean 𝑥 ¯ and standard deviation 𝜎 ^ over 128 samples 𝑥 ^ 1 , … , 𝑥 ^ 128 . To summarize, we compare 𝐾 -RCPS and RCPS on the following families of nested set predictors:

Quantile Regression (QR)

ℐ 𝝀 , QR ⁢ ( 𝑦 ) 𝑗

[ 𝑥 ^ 𝑗 − 𝜆 𝑗 ⁢ ( 𝑞 ^ 𝛼 / 2 ) 𝑗 , 𝑥 ^ 𝑗 + 𝜆 𝑗 ⁢ ( 𝑞 ^ 1 − 𝛼 / 2 ) 𝑗 ] ,

(17)

where 𝑓 ⁢ ( 𝑦 , 𝑡 )

( 𝑞 ^ 𝛼 / 2 , 𝑥 ^ , 𝑞 ^ 1 − 𝛼 / 2 ) .

MC-Dropout

ℐ 𝝀 , MC-Dropout ⁢ ( 𝑦 ) 𝑗

[ 𝑥 ¯ 𝑗 − 𝜆 𝑗 ⁢ 𝜎 ^ 𝑗 , 𝑥 ¯ 𝑗 + 𝜆 𝑗 ⁢ 𝜎 ^ 𝑗 ] ,

(18)

where 𝑥 ¯ , 𝜎 ^ are the sample mean and standard deviation over 128 samples 𝑥 ^ 1 , … , 𝑥 ^ 128 obtained by activating the dropout layers in the image regressor 𝑓 .

N-Con 𝑓 ⁢ 𝑓 ⁢ 𝑢 ⁢ 𝑠 ⁢ 𝑖 ⁢ 𝑜 ⁢ 𝑛 10 We compare two different parametrizations—multiplicative and additive:

ℐ 𝝀 , Conffusion multiplicative ⁢ ( 𝑦 ) 𝑗

[ ( 𝑞 ^ 𝛼 / 2 ) 𝑗 𝜆 𝑗 , 𝜆 𝑗 ⁢ ( 𝑞 ^ 1 − 𝛼 / 2 ) 𝑗 ]

(19)

and

ℐ 𝝀 , Conffusion additive ⁢ ( 𝑦 ) 𝑗

[ ( 𝑞 ^ 𝛼 / 2 ) 𝑗 − 𝜆 𝑗 , ( 𝑞 ^ 1 − 𝛼 / 2 ) 𝑗 + 𝜆 𝑗 ] ,

(20)

where 𝑠 ~ ⁢ ( 𝑦 , 𝑡 )

( 𝑞 ^ 𝛼 / 2 , 𝑞 ^ 1 − 𝛼 / 2 ) is the fine-tuned score network by means of quantile regression on 1000 additional samples.

Naive quantiles

ℐ 𝝀 , naive ⁢ ( 𝑦 ) 𝑗

[ 𝑙 ^ 𝑗 − 𝜆 𝑗 , 𝑢 ^ 𝑗 + 𝜆 𝑗 ] ,

(21)

where 𝑙 ^ , 𝑢 ^ are the naive (i.e., not calibrated) 𝛼 / 2 and 1 − 𝛼 / 2 entrywise empirical quantiles computed on 128 samples from the diffusion model.

Calibrated quantiles

ℐ 𝝀 𝛼 ⁢ ( 𝑦 ) 𝑗

[ 𝑙 ^ 𝑗 , 𝛼 − 𝜆 𝑗 , 𝑢 ^ 𝑗 , 𝛼 + 𝜆 𝑗 ]

(22)

where 𝑙 ^ 𝛼 , 𝑢 ^ 𝛼 are the entrywise calibrated quantiles computed on 128 samples from the diffusion model as described in Equation 9 (see Figure 3 for some examples).

(a)CelebA dataset ( 𝛼

0.10 , 𝜖

0.10 ). (b)AbdomenCT-1K dataset ( 𝛼

0.20 , 𝜖

0.05 ). Figure 4:Example optimal 𝝀 ^ 𝐾 for 𝐾 ∈ { 4 , 8 , 32 } , 𝑛 opt

256 , and 𝑑 opt

100 with respective conformalized uncertainty maps ℐ 𝝀 ^ 𝛼 ⁢ ( 𝑦 )

[ 𝑙 ^ 𝑗 , 𝛼 − ( 𝜆 ^ 𝐾 ) 𝑗 , 𝑢 ^ 𝑗 , 𝛼 + ( 𝜆 ^ 𝐾 ) 𝑗 ] . With probability at least 90 % no more than 𝜖 portion of the ground truth pixels will fall outside of ℐ 𝝀 ^ 𝛼 on future, unseen samples.

We include further details on the datasets, the models, and the training and sampling procedures in Appendix D. The implementation of 𝐾 -RCPS with all code and data necessary to reproduce the experiments is available at https://github.com/Sulam-Group/k-rcps.

We compare all models and calibration procedures on 20 random draws of calibration and validation sets 𝒮 cal , 𝒮 val of length 𝑛 cal and 𝑛 val , respectively. We remark that for the 𝐾 -RCPS procedure, 𝑛 opt samples from 𝒮 cal will be used to solve the optimization problem (P 𝐾 ). It follows that for a fixed 𝑛 cal , the concentration inequality used in the 𝐾 -RCPS procedure will be looser compared to the one in the RCPS algorithm. We will show that there remains a clear benefit of using the 𝐾 -RCPS algorithm in terms of mean interval length given the same amount of calibration data available (i.e., even while the concentration bound becomes looser). In these experiments, we construct the membership matrix 𝑀 by assigning each feature 𝑗 ∈ [ 𝑑 ] to the respective 𝑘 th , 𝑘

1 , … , 𝐾 quantile of the entrywise empirical estimate of the risk on 𝒮 opt . Furthermore, even though (P 𝐾 ) is low-dimensional (i.e., 𝐾 ≪ 𝑑 ), the number of constraints grows as 𝑑 ⁢ 𝑛 opt , which quickly makes the computation of 𝝀 ~ 𝐾 inefficient and time-consuming (e.g., for the AbdomenCT-1K dataset, 𝑑 ⁢ 𝑛 opt ∼ 10 8 when 𝑛 opt

128 , a mild number of samples to optimize over). In practice, we randomly subsample a small number of features 𝑑 opt ≪ 𝑑 stratified by membership, which drastically speeds up computation. In the following experiments, we set 𝑑 opt ∈ { 50 , 100 } and use 𝐾 ∈ { 4 , 8 , 32 } , which reduces the runtime of solving the optimization problem to less than a second for both datasets. Finally, we pick 𝛾 that minimizes the objective function over 16 values equally spaced in [ 0.3 , 0.7 ] . The choice of these heuristics makes the runtime of 𝐾 -RCPS comparable to that of RCPS, with a small overhead to solve the reduced (P 𝐾 ) problem (potentially multiple times to optimize 𝛾 ).

Figure G.1 shows that all combinations of notion of uncertainty and calibration procedures control the risk, as promised. In particular, we set 𝛿

0.10 for both datasets, and 𝜖

0.10 , 0.05 for the CelebA and AbdomenCT-1K dataset, respectively. We repeat all calibration procedures over 20 random samples of 𝒮 cal , 𝒮 val , with 𝑛 val

128 , and 𝑛 cal

640 or 𝑛 cal

512 for the CelebA or AbdomenCT-1K dataset, respectively. Figure 4 showcases some example 𝝀 ^ 𝐾 ’s obtained by running the 𝐾 -RCPS procedure with 𝐾

4 , 8 , and 32 quantiles alongside their respective conformalized uncertainty maps from 𝒮 val . We can appreciate how for both datasets, 𝝀 ^ 𝐾 captures information about the structure of the data distribution (e.g., eyes and lips for the CelebA dataset, and the position of lungs and the heart for the AbdomenCT-1K dataset). Finally, we compare all baselines and calibration procedures in terms of the guarantees each of them provide and their mean interval length. In particular, we report whether each notion of uncertainty provides guarantees over a diffusion model or not. Note that naive and calibrated quantiles are the only notions of uncertainty that precisely provide guarantees on the samples from a diffusion model. Furthermore, calibrated quantiles are the only method that ensures entrywise coverage on future samples on the same noisy observation. For 𝐾 -RCPS, we perform a grid search over 𝑛 opt ∈ { 128 , 256 } , 𝑑 opt ∈ { 50 , 100 } , and 𝐾 ∈ { 4 , 8 , 32 } , and we report the optimal results in Table 1. For both datasets, 𝐾 -RCPS provides the tightest intervals among methods that provide both entrywise coverage and risk control for diffusion models. When relaxing the constraint of entrywise coverage, 𝐾 -RCPS still provides the tightest intervals. Across the uncertainty quantification methods that do not relate to a diffusion model, we found that 𝐾 -RCPS with naive sampling provides better results on the CelebA dataset. For the AbdomenCT-1K dataset, N-Con 𝑓 ⁢ 𝑓 ⁢ 𝑢 ⁢ 𝑠 ⁢ 𝑖 ⁢ 𝑜 ⁢ 𝑛 with multiplicative parametrization and RCPS provides slightly shorter intervals compared to Con 𝑓 ⁢ 𝑓 ⁢ 𝑢 ⁢ 𝑠 ⁢ 𝑖 ⁢ 𝑜 ⁢ 𝑛 with additive parametrization and 𝐾 -RCPS. However, we stress that the intervals provided by N-Con 𝑓 ⁢ 𝑓 ⁢ 𝑢 ⁢ 𝑠 ⁢ 𝑖 ⁢ 𝑜 ⁢ 𝑛 are computed for a fine-tuned model that is different from the original diffusion model, and thus provide no guarantees over the samples of the original model. We found that N-Con 𝑓 ⁢ 𝑓 ⁢ 𝑢 ⁢ 𝑠 ⁢ 𝑖 ⁢ 𝑜 ⁢ 𝑛 with multiplicative parametrization underperforms on the CelebA dataset because the lower bounds do not decay fast enough, and the loss is concentrated on features whose ( 𝑞 ^ 𝛼 / 2 ) 𝑗 / 𝜆 𝑗

𝑥 𝑗 .

5Conclusions Table 1:Comparison of all notions of uncertainty with RCPS and 𝐾 -RCPS in terms of guarantees provided and mean interval length over 20 independent draws of 𝒮 cal . We refer the reader to Appendix E for a detailed discussion of the comparison with the Con 𝑓 ⁢ 𝑓 ⁢ 𝑢 ⁢ 𝑠 ⁢ 𝑖 ⁢ 𝑜 ⁢ 𝑛 framework. Uncertainty Diffusion model? Entrywise coverage? Risk control? Calibration procedure Mean interval length CelebA AbdomenCT-1K QR ✗ ✗ ✓ RCPS 0.4843 ± 0.0121

0.2943 ± 0.0060

MC-Dropout ✗ ✗ ✓ RCPS 0.6314 ± 0.0109

0.2810 ± 0.0013

N-Con 𝑓 ⁢ 𝑓 ⁢ 𝑢 ⁢ 𝑠 ⁢ 𝑖 ⁢ 𝑜 ⁢ 𝑛

— multiplicative ✗ ✗ ✓ RCPS 0.6949 ± 0.0084

0.1126 ± 0.0020

— additive ✗ ✗ ✓ RCPS 0.3314 ± 0.0040

0.1164 ± 0.0024

— additive ✗ ✗ ✓ 𝐾 -RCPS 0.3131 ± 0.0056

0.1136 ± 0.0019

Naive quantiles ✓ ✗ ✓ RCPS 0.2688 ± 0.0068

0.1518 ± 0.0016

Naive quantiles ✓ ✗ ✓ 𝐾 -RCPS 0.2523 ± 0.0052

0.1374 ± 0.0019

Calibrated quantiles ✓ ✓ ✓ RCPS 0.2762 ± 0.0059

0.1506 ± 0.0014

Calibrated quantiles ✓ ✓ ✓ 𝐾 -RCPS 0.2644 ± 0.0067

0.1369 ± 0.0016

Diffusion models represent huge potential for sampling in inverse problems, alas how to devise precise guarantees on uncertainty has remained open. We have provided (i) calibrated intervals that guarantee coverage of future samples generated by diffusion models, (ii) shown how to extend RCPS to 𝐾 -RCPS, allowing for greater flexibility by conformalizing in higher dimensions by means of a convex surrogate problem. Yet, our results are general and hold for any data distribution and any sampling procedure—diffusion models or otherwise. When combined, these two contributions provide state of the art uncertainty quantification by controlling risk with minimal mean interval length. Our contributions open the door to a variety of new problems. While we have focused on denoising problems, the application of these tools for other, more challenging restoration tasks is almost direct since no distributional assumptions are employed. The variety of diffusion models for other conditional-sampling problem can readily be applied here too [61, 17]. Lastly—and differently from other works that explore controlling multiple risks [36]—ours is the first approach to provide multi-dimensional control of one risk for conformal prediction, and likely improvements to our optimization schemes could be possible. More generally, we envision our tools to contribute to the responsible use of machine learning in modern settings.

Acknowledgments

The authors sincerely thank Anastasios Angelopoulos for insightful discussions in early stages of this work, as well as the anonymous reviewers who have helped improve our paper.

References Agrawal et al. [2018] ↑ Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd.A rewriting system for convex optimization problems.Journal of Control and Decision, 5(1):42–60, 2018. Anderson [1982] ↑ Brian DO Anderson.Reverse-time diffusion equation models.Stochastic Processes and their Applications, 12(3):313–326, 1982. Angelopoulos and Bates [2021] ↑ Anastasios N Angelopoulos and Stephen Bates.A gentle introduction to conformal prediction and distribution-free uncertainty quantification.arXiv preprint arXiv:2107.07511, 2021. Angelopoulos et al. [2021] ↑ Anastasios N Angelopoulos, Stephen Bates, Emmanuel J Candès, Michael I Jordan, and Lihua Lei.Learn then test: Calibrating predictive algorithms to achieve risk control.arXiv preprint arXiv:2110.01052, 2021. Angelopoulos et al. [2022a] ↑ Anastasios N Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster.Conformal risk control.arXiv preprint arXiv:2208.02814, 2022a. Angelopoulos et al. [2022b] ↑ Anastasios N Angelopoulos, Amit Pal Kohli, Stephen Bates, Michael Jordan, Jitendra Malik, Thayer Alshaabi, Srigokul Upadhyayula, and Yaniv Romano.Image-to-image regression with distribution-free uncertainty quantification and applications in imaging.In International Conference on Machine Learning, pages 717–730. PMLR, 2022b. ApS [2019] ↑ MOSEK ApS.The MOSEK optimization toolbox for MATLAB manual. Version 9.0., 2019.URL http://docs.mosek.com/9.0/toolbox/index.html. Barber et al. [2021] ↑ Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan J Tibshirani.Predictive inference with the jackknife+.The Annals of Statistics, 49(1):486–507, 2021. Barber et al. [2022] ↑ Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan J Tibshirani.Conformal prediction beyond exchangeability.arXiv preprint arXiv:2202.13415, 2022. Bates et al. [2021] ↑ Stephen Bates, Anastasios Angelopoulos, Lihua Lei, Jitendra Malik, and Michael Jordan.Distribution-free, risk-controlling prediction sets.Journal of the ACM (JACM), 68(6):1–34, 2021. Bentkus [2004] ↑ Vidmantas Bentkus.On hoeffding’s inequalities.The Annals of Probability, 32(2):1650–1673, 2004. Bishop and Nasrabadi [2006] ↑ Christopher M Bishop and Nasser M Nasrabadi.Pattern recognition and machine learning, volume 4.Springer, 2006. Carlier et al. [2016] ↑ Guillaume Carlier, Victor Chernozhukov, and Alfred Galichon.Vector quantile regression: an optimal transport approach.The Annals of Statistics, 44(3):1165–1192, 2016. Carlier et al. [2020] ↑ Guillaume Carlier, Victor Chernozhukov, Gwendoline De Bie, and Alfred Galichon.Vector quantile regression and optimal transport, from theory to numerics.Empirical Economics, pages 1–28, 2020. Chernozhukov et al. [2017] ↑ Victor Chernozhukov, Alfred Galichon, Marc Hallin, and Marc Henry.Monge–kantorovich depth, quantiles, ranks and signs.The Annals of Statistics, 45(1):223–256, 2017. Corso et al. [2022] ↑ Gabriele Corso, Hannes Stärk, Bowen Jing, Regina Barzilay, and Tommi Jaakkola.Diffdock: Diffusion steps, twists, and turns for molecular docking.arXiv preprint arXiv:2210.01776, 2022. Croitoru et al. [2022] ↑ Florinel-Alin Croitoru, Vlad Hondru, Radu Tudor Ionescu, and Mubarak Shah.Diffusion models in vision: A survey.arXiv preprint arXiv:2209.04747, 2022. Croitoru et al. [2023] ↑ Florinel-Alin Croitoru, Vlad Hondru, Radu Tudor Ionescu, and Mubarak Shah.Diffusion models in vision: A survey.IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023. Diamond and Boyd [2016] ↑ Steven Diamond and Stephen Boyd.CVXPY: A Python-embedded modeling language for convex optimization.Journal of Machine Learning Research, 17(83):1–5, 2016. Gal and Ghahramani [2016] ↑ Yarin Gal and Zoubin Ghahramani.Dropout as a bayesian approximation: Representing model uncertainty in deep learning.In international conference on machine learning, pages 1050–1059. PMLR, 2016. Genevay et al. [2016] ↑ Aude Genevay, Marco Cuturi, Gabriel Peyré, and Francis Bach.Stochastic optimization for large-scale optimal transport.Advances in neural information processing systems, 29, 2016. Gupta et al. [2022] ↑ Chirag Gupta, Arun K Kuchibhotla, and Aaditya Ramdas.Nested conformal prediction and quantile out-of-bag ensemble methods.Pattern Recognition, 127:108496, 2022. Ho et al. [2020] ↑ Jonathan Ho, Ajay Jain, and Pieter Abbeel.Denoising diffusion probabilistic models.Advances in Neural Information Processing Systems, 33:6840–6851, 2020. Hoeffding [1994] ↑ Wassily Hoeffding.Probability inequalities for sums of bounded random variables.In The collected works of Wassily Hoeffding, pages 409–426. Springer, 1994. Hoogeboom et al. [2022] ↑ Emiel Hoogeboom, Vıctor Garcia Satorras, Clément Vignac, and Max Welling.Equivariant diffusion for molecule generation in 3d.In International Conference on Machine Learning, pages 8867–8887. PMLR, 2022. Horwitz and Hoshen [2022] ↑ Eliahu Horwitz and Yedid Hoshen.Conffusion: Confidence intervals for diffusion models.arXiv preprint arXiv:2211.09795, 2022. Hyvärinen and Dayan [2005] ↑ Aapo Hyvärinen and Peter Dayan.Estimation of non-normalized statistical models by score matching.Journal of Machine Learning Research, 6(4), 2005. Ingraham et al. [2022] ↑ John Ingraham, Max Baranov, Zak Costello, Vincent Frappier, Ahmed Ismail, Shan Tie, Wujie Wang, Vincent Xue, Fritz Obermeyer, Andrew Beam, et al.Illuminating protein space with a programmable generative model.bioRxiv, 2022. Kadkhodaie and Simoncelli [2021] ↑ Zahra Kadkhodaie and Eero Simoncelli.Stochastic solutions for linear inverse problems using the prior implicit in a denoiser.Advances in Neural Information Processing Systems, 34:13242–13254, 2021. Karatzas et al. [1991] ↑ Ioannis Karatzas, Ioannis Karatzas, Steven Shreve, and Steven E Shreve.Brownian motion and stochastic calculus, volume 113.Springer Science & Business Media, 1991. Kawar et al. [2021a] ↑ Bahjat Kawar, Gregory Vaksman, and Michael Elad.Snips: Solving noisy inverse problems stochastically.Advances in Neural Information Processing Systems, 34:21757–21769, 2021a. Kawar et al. [2021b] ↑ Bahjat Kawar, Gregory Vaksman, and Michael Elad.Stochastic image denoising by sampling from the posterior distribution.In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1866–1875, 2021b. Kazerouni et al. [2022] ↑ Amirhossein Kazerouni, Ehsan Khodapanah Aghdam, Moein Heidari, Reza Azad, Mohsen Fayyaz, Ilker Hacihaliloglu, and Dorit Merhof.Diffusion models for medical image analysis: A comprehensive survey.arXiv preprint arXiv:2211.07804, 2022. Koenker and Bassett Jr [1978] ↑ Roger Koenker and Gilbert Bassett Jr.Regression quantiles.Econometrica: journal of the Econometric Society, pages 33–50, 1978. Kutiel et al. [2022] ↑ Gilad Kutiel, Regev Cohen, Michael Elad, and Daniel Freedman.What’s behind the mask: Estimating uncertainty in image-to-image problems.arXiv preprint arXiv:2211.15211, 2022. Laufer-Goldshtein et al. [2022] ↑ Bracha Laufer-Goldshtein, Adam Fisch, Regina Barzilay, and Tommi Jaakkola.Efficiently controlling multiple risks with pareto testing.arXiv preprint arXiv:2210.07913, 2022. Lee et al. [2022] ↑ Holden Lee, Jianfeng Lu, and Yixin Tan.Convergence for score-based generative modeling with polynomial complexity.arXiv preprint arXiv:2206.06227, 2022. Lei and Wasserman [2014] ↑ Jing Lei and Larry Wasserman.Distribution-free prediction bands for non-parametric regression.Journal of the Royal Statistical Society: Series B (Statistical Methodology), 76(1):71–96, 2014. Liu et al. [2016] ↑ Qiang Liu, Jason Lee, and Michael Jordan.A kernelized stein discrepancy for goodness-of-fit tests.In International conference on machine learning, pages 276–284. PMLR, 2016. Liu et al. [2018] ↑ Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang.Large-scale celebfaces attributes (celeba) dataset.Retrieved August, 15(2018):11, 2018. Ma et al. [2021] ↑ Jun Ma, Yao Zhang, Song Gu, Cheng Zhu, Cheng Ge, Yichi Zhang, Xingle An, Congcong Wang, Qiyuan Wang, Xin Liu, et al.Abdomenct-1k: Is abdominal organ segmentation a solved problem.IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021. Metzer et al. [2022] ↑ Gal Metzer, Elad Richardson, Or Patashnik, Raja Giryes, and Daniel Cohen-Or.Latent-nerf for shape-guided generation of 3d shapes and textures.arXiv preprint arXiv:2211.07600, 2022. Pang et al. [2020] ↑ Tianyu Pang, Kun Xu, Chongxuan Li, Yang Song, Stefano Ermon, and Jun Zhu.Efficient learning of generative models via finite-difference score matching.Advances in Neural Information Processing Systems, 33:19175–19188, 2020. Papadopoulos et al. [2002] ↑ Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman.Inductive confidence machines for regression.In European Conference on Machine Learning, pages 345–356. Springer, 2002. Romano et al. [2019] ↑ Yaniv Romano, Evan Patterson, and Emmanuel Candes.Conformalized quantile regression.Advances in neural information processing systems, 32, 2019. Ronneberger et al. [2015] ↑ Olaf Ronneberger, Philipp Fischer, and Thomas Brox.U-net: Convolutional networks for biomedical image segmentation.In International Conference on Medical image computing and computer-assisted intervention, pages 234–241. Springer, 2015. Rosenberg et al. [2022] ↑ Aviv A Rosenberg, Sanketh Vedula, Yaniv Romano, and Alex M Bronstein.Fast nonlinear vector quantile regression.arXiv preprint arXiv:2205.14977, 2022. Shafer and Vovk [2008] ↑ Glenn Shafer and Vladimir Vovk.A tutorial on conformal prediction.Journal of Machine Learning Research, 9(3), 2008. Sohl-Dickstein et al. [2015] ↑ Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli.Deep unsupervised learning using nonequilibrium thermodynamics.In International Conference on Machine Learning, pages 2256–2265. PMLR, 2015. Song and Ermon [2019] ↑ Yang Song and Stefano Ermon.Generative modeling by estimating gradients of the data distribution.Advances in Neural Information Processing Systems, 32, 2019. Song and Ermon [2020] ↑ Yang Song and Stefano Ermon.Improved techniques for training score-based generative models.Advances in neural information processing systems, 33:12438–12448, 2020. Song et al. [2020a] ↑ Yang Song, Sahaj Garg, Jiaxin Shi, and Stefano Ermon.Sliced score matching: A scalable approach to density and score estimation.In Uncertainty in Artificial Intelligence, pages 574–584. PMLR, 2020a. Song et al. [2020b] ↑ Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole.Score-based generative modeling through stochastic differential equations.arXiv preprint arXiv:2011.13456, 2020b. Song et al. [2021] ↑ Yang Song, Liyue Shen, Lei Xing, and Stefano Ermon.Solving inverse problems in medical imaging with score-based generative models.arXiv preprint arXiv:2111.08005, 2021. Torem et al. [2022] ↑ Nadav Torem, Roi Ronen, Yoav Y Schechner, and Michael Elad.Towards a most probable recovery in optical imaging.arXiv preprint arXiv:2212.03235, 2022. Vovk [2015] ↑ Vladimir Vovk.Cross-conformal predictors.Annals of Mathematics and Artificial Intelligence, 74(1):9–28, 2015. Vovk et al. [2005] ↑ Vladimir Vovk, Alexander Gammerman, and Glenn Shafer.Algorithmic learning in a random world.Springer Science & Business Media, 2005. Watson et al. [2022] ↑ Joseph L Watson, David Juergens, Nathaniel R Bennett, Brian L Trippe, Jason Yim, Helen E Eisenach, Woody Ahern, Andrew J Borst, Robert J Ragotte, Lukas F Milles, et al.Broadly applicable and accurate protein design by integrating structure prediction networks and diffusion generative models.bioRxiv, 2022. Xie and Li [2022] ↑ Yutong Xie and Quanzheng Li.Measurement-conditioned denoising diffusion probabilistic model for under-sampled medical image reconstruction.arXiv preprint arXiv:2203.03623, 2022. Xu et al. [2022] ↑ Jiale Xu, Xintao Wang, Weihao Cheng, Yan-Pei Cao, Ying Shan, Xiaohu Qie, and Shenghua Gao.Dream3d: Zero-shot text-to-3d synthesis using 3d shape prior and text-to-image diffusion models.arXiv preprint arXiv:2212.14704, 2022. Yang et al. [2022] ↑ Ling Yang, Zhilong Zhang, Yang Song, Shenda Hong, Runsheng Xu, Yue Zhao, Yingxia Shao, Wentao Zhang, Bin Cui, and Ming-Hsuan Yang.Diffusion models: A comprehensive survey of methods and applications.arXiv preprint arXiv:2209.00796, 2022. Zeng et al. [2022] ↑ Xiaohui Zeng, Arash Vahdat, Francis Williams, Zan Gojcic, Or Litany, Sanja Fidler, and Karsten Kreis.Lion: Latent point diffusion models for 3d shape generation.arXiv preprint arXiv:2210.06978, 2022. Appendix AProofs

In this section, we include the proofs for the results presented in this paper. Herein, denote ℐ : 𝒴 → 𝒳 ′ a set-valued predictor from 𝒴 ⊂ ℝ 𝑑 into a space of subsets 𝒳 ′ ⊆ 2 𝒳 for 𝒳 ⊂ ℝ 𝑑 .

A.1Proof of Lemma 3.2

Let 𝐹 : 𝒴 → 𝒳 be a stochastic sampling procedure from 𝒴 to 𝒳 such that for a fixed 𝑦 ∈ 𝒴 , 𝐹 ⁢ ( 𝑦 ) is a random vector with unknown distribution 𝒬 𝑦 . We show that for a desired miscoverage level 𝛼 ∈ [ 0 , 1 ] , the entrywise calibrated empirical quantiles ℐ 𝛼 ⁢ ( 𝑦 ) 𝑗

[ 𝑙 ^ 𝑗 , 𝛼 , 𝑢 ^ 𝑗 , 𝛼 ] defined in Equation 9 provide entrywise coverage as in Definition 3.1. That is, for each 𝑗 ∈ [ 𝑑 ] ≔ { 1 , … , 𝑑 }

ℙ ⁢ [ 𝐹 ⁢ ( 𝑦 ) 𝑗 ∈ ℐ 𝛼 ⁢ ( 𝑦 ) 𝑗 ] ≥ 1 − 𝛼 .

(23) Proof.

The proof is a variation of the classical split conformal prediction coverage guarantee (see Angelopoulos and Bates [3], Theorem D.1). Let 𝐹 1 , … , 𝐹 𝑚 , 𝐹 𝑚 + 1 be 𝑚 + 1 i.i.d. samples from 𝐹 ⁢ ( 𝑦 ) . For a desired miscoverage level 𝛼 ∈ [ 0 , 1 ] and for each 𝑗 ∈ [ 𝑑 ] denote

𝑙 ^ 𝑗 , 𝛼

inf { 𝑙 : | { 𝑘 : ( 𝐹 𝑘 ) 𝑗 ≤ 𝑙 } | 𝑚 ≥ ⌊ ( 𝑚 + 1 ) ⁢ 𝛼 / 2 ⌋ 𝑚 }

(24)

and

𝑢 ^ 𝑗 , 𝛼

inf { 𝑢 : | { 𝑘 : ( 𝐹 𝑘 ) 𝑗 ≤ 𝑢 } | 𝑚 ≥ ⌈ ( 𝑚 + 1 ) ⁢ ( 1 − 𝛼 / 2 ) ⌉ 𝑚 }

(25)

the ⌊ ( 𝑚 + 1 ) ⁢ 𝛼 / 2 ⌋ / 𝑚 and ⌈ ( 𝑚 + 1 ) ⁢ ( 1 − 𝛼 / 2 ) ⌉ / 𝑚 entrywise calibrated empirical quantiles of 𝐹 1 , … , 𝐹 𝑚 . Assume that for each 𝑗 ∈ [ 𝑑 ] , the first 𝑚 samples are ordered in ascending order, i.e. ( 𝐹 1 ) 𝑗 < ⋯ < ( 𝐹 𝑚 ) 𝑗 such that

𝑙 ^ 𝑗 , 𝛼

( 𝐹 ⌊ ( 𝑚 + 1 ) ⁢ 𝛼 / 2 ⌋ ) 𝑗 and 𝑢 ^ 𝑗 , 𝛼

( 𝐹 ⌈ ( 𝑚 + 1 ) ⁢ ( 1 − 𝛼 / 2 ) ⌉ ) 𝑗 .

(26)

Note that by symmetry of ( 𝐹 1 ) 𝑗 , … , ( 𝐹 𝑚 ) 𝑗 it follows that ( 𝐹 𝑚 + 1 ) 𝑗 is equally likely to fall between any of the first 𝑚 samples. That is, for any two indices 𝑚 1 < 𝑚 2

ℙ ⁢ [ ( 𝐹 𝑚 + 1 ) 𝑗 ∈ [ ( 𝐹 𝑚 1 ) 𝑗 , ( 𝐹 𝑚 2 ) 𝑗 ] ]

𝑚 2 − 𝑚 1 𝑚 + 1 .

(27)

Instantiating the above equality with ℐ 𝛼 ⁢ ( 𝑦 ) 𝑗

[ 𝑙 ^ 𝑗 , 𝛼 , 𝑢 ^ 𝑗 , 𝛼 ] yields

ℙ ⁢ [ ( 𝐹 𝑚 + 1 ) 𝑗 ∈ ℐ 𝛼 ⁢ ( 𝑦 ) 𝑗 ]

ℙ ⁢ [ ( 𝐹 𝑚 + 1 ) 𝑗 ∈ [ 𝑙 ^ 𝑗 , 𝛼 , 𝑢 ^ 𝑗 , 𝛼 ] ]

(28)

= ℙ ⁢ [ ( 𝐹 𝑚 + 1 ) 𝑗 ∈ [ ( 𝐹 ⌊ ( 𝑚 + 1 ) ⁢ 𝛼 / 2 ⌋ ) 𝑗 , ( 𝐹 ⌈ ( 𝑚 + 1 ) ⁢ ( 1 − 𝛼 / 2 ) ⌉ ) 𝑗 ] ]

(29)

= ⌈ ( 𝑚 + 1 ) ⁢ ( 1 − 𝛼 / 2 ) ⌉ − ⌊ ( 𝑚 + 1 ) ⁢ 𝛼 / 2 ⌋ 𝑚 + 1

(30)

≥ ( 𝑚 + 1 ) ⁢ ( 1 − 𝛼 ) 𝑚 + 1

1 − 𝛼

(31)

which concludes the proof. ∎

A.2Proof of Theorem 3.3

Recall that for a calibration set 𝒮 cal

{ ( 𝑥 𝑖 , 𝑦 𝑖 ) } 𝑖

1 𝑛 of 𝑛 i.i.d. samples from an unknown distribution 𝒟 over 𝒳 × 𝒴 , a loss function ℓ : 𝒳 × 𝒳 ′ → ℝ , and a family { ℐ 𝝀 ⁢ ( 𝑦 ) } 𝝀 ∈ Λ 𝑑 of set-valued predictors indexed by a 𝑑 -dimensional vector 𝝀

( 𝜆 1 , … , 𝜆 𝑑 ) ∈ Λ 𝑑 , Λ ⊂ ℝ ¯

ℝ ∪ { ± ∞ }

𝑅 ⁢ ( 𝝀 )

𝔼 ( 𝑥 , 𝑦 ) ∼ 𝒟 ⁢ [ ℓ ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) ) ] and 𝑅 ^ ⁢ ( 𝝀 )

1 𝑛 ⁢ ∑ ( 𝑥 𝑖 , 𝑦 𝑖 ) ∈ 𝒮 cal 𝑛 ℓ ⁢ ( 𝑥 𝑖 , ℐ 𝝀 ⁢ ( 𝑦 𝑖 ) )

(32)

denote the risk of ℐ 𝝀 ⁢ ( 𝑦 ) and its empirical estimate on the calibration set, respectively. Furthermore, let 𝑅 ^ + ⁢ ( 𝝀 ) be a pointwise upper confidence bound (UCB) such that for each fixed 𝝀 ∈ Λ 𝑑 and ∀ 𝛿 ∈ [ 0 , 1 ]

ℙ ⁢ [ 𝑅 ⁢ ( 𝝀 ) ≤ 𝑅 ^ + ⁢ ( 𝝀 ) ] ≥ 1 − 𝛿

(33)

as presented in Equation 6. Equivalently to Definition 2.2, for a risk level 𝜖 ≥ 0 , we say that ℐ 𝝀 ⁢ ( 𝑦 ) is an ( 𝜖 , 𝛿 ) -RCPS if

ℙ 𝒮 cal ⁢ [ 𝑅 ⁢ ( 𝝀 ) ≤ 𝜖 ] ≥ 1 − 𝛿 .

(34)

Given fixed vectors 𝝀 ~ ∈ ℝ 𝑑 and 𝜼 ∈ ℝ 𝑑 , 𝜼 ≥ 0 , denote 𝚲 ~

𝝀 ~ + 𝜔 ⁢ 𝜼 , 𝜔 ∈ Λ the line with offset 𝝀 ~ and direction 𝜼 parametrized by 𝜔 . We show that for entrywise monotonically nonincreasing loss functions and for the family of set-valued predictors of the form ℐ 𝝀 ⁢ ( 𝑦 )

[ 𝑙 ^ 𝑗 − 𝜆 𝑗 , 𝑢 ^ 𝑗 + 𝜆 𝑗 ] , for some lower and upper bounds 𝑙 ^ 𝑗 < 𝑢 ^ 𝑗 that may depend on 𝑦 , if

𝝀 ^

arg ⁡ min 𝝀 ∈ 𝚲 ~ ⁢ ∑ 𝑗 ∈ [ 𝑑 ] 𝜆 𝑗 s.t. 𝑅 ^ + ⁢ ( 𝝀 + 𝛽 ⁢ 𝜼 ) < 𝜖 , ∀ 𝛽 ≥ 0

(35)

ℐ 𝝀 ^ ⁢ ( 𝑦 ) is an ( 𝜖 , 𝛿 ) -RCPS. We start by reminding the following definitions.

Definition A.1 (Entrywise monotonically nonincreasing function).

A loss function ℓ is entrywise monotonically nonincreasing if, for a fixed 𝑥 , ∀ 𝑗 ∈ [ 𝑑 ]

ℐ ⁢ ( 𝑦 ) 𝑗 ⊂ ℐ ′ ⁢ ( 𝑦 ) 𝑗 ⟹ ℓ ⁢ ( 𝑥 , ℐ ′ ⁢ ( 𝑦 ) ) ≤ ℓ ⁢ ( 𝑥 , ℐ ⁢ ( 𝑦 ) ) .

(36) Definition A.2 (Entrywise nesting property).

A family of set predictors { ℐ 𝝀 ⁢ ( 𝑦 ) } 𝝀 ∈ Λ 𝑑 is entrywise nested if, for a fixed 𝑦 , ∀ 𝑗 ∈ [ 𝑑 ]

𝜆 𝑗 , 1 < 𝜆 𝑗 , 2 ⟹ ℐ [ 𝜆 𝑗 , 1 , 𝝀 − 𝑗 ] ⁢ ( 𝑦 ) 𝑗 ⊂ ℐ [ 𝜆 𝑗 , 2 , 𝝀 − 𝑗 ] ⁢ ( 𝑦 ) 𝑗 ,

(37)

where [ 𝜆 𝑗 , 𝝀 − 𝑗 ] is the vector that takes value 𝜆 𝑗 in its 𝑗 th entry and 𝜆 − 𝑗 in its complement − 𝑗 ≔ [ 𝑑 ] ∖ { 𝑗 } .

Proof.

The proof is a high-dimensional extension of the validity of the original RCPS calibration procedure. Note that the family of set-valued predictors { ℐ 𝝀 ⁢ ( 𝑦 )

[ 𝑙 ^ 𝑗 − 𝜆 𝑗 , 𝑢 ^ 𝑗 + 𝜆 𝑗 ] } 𝝀 ∈ Λ 𝑑 satisfies the entrywise nesting property in Definition A.2. For 𝝀 ^ chosen as in Equation 35, denote 𝐿 : Λ → ℝ the one-dimensional function such that

𝐿 ⁢ ( 𝛽 )

𝑅 ⁢ ( 𝝀 ^ + 𝛽 ⁢ 𝜼 ) and 𝐿 ^ + ⁢ ( 𝛽 )

𝑅 ^ + ⁢ ( 𝝀 ^ + 𝛽 ⁢ 𝜼 ) .

(38)

It follows that 𝐿 is monotonically nonincreasing because ℓ is entrywise monotonically nonincreasing by assumption, and 𝜼 belongs to the positive orthant. Furthermore, ℙ ⁢ [ 𝐿 ⁢ ( 𝛽 ) ≤ 𝐿 ^ + ⁢ ( 𝛽 ) ] ≥ 1 − 𝛿 by definition of 𝑅 ^ + ⁢ ( 𝝀 ) . Denote

𝛽 *

inf { 𝛽 ∈ Λ : 𝐿 ⁢ ( 𝛽 ) ≤ 𝜖 }

(39)

and suppose 𝑅 ⁢ ( 𝝀 ^ )

𝐿 ⁢ ( 0 ) > 𝜖 . By monotonicity of 𝐿 it follows that 𝛽 * > 0 , and by definition of 𝝀 ^ , 𝐿 ^ + ⁢ ( 𝛽 * )

𝑅 ^ + ⁢ ( 𝝀 ^ + 𝛽 * ⁢ 𝜼 ) < 𝜖 . However, since 𝐿 ⁢ ( 𝛽 * )

𝜖 and ℙ ⁢ [ 𝐿 ⁢ ( 𝛽 * ) ≤ 𝐿 ^ + ⁢ ( 𝛽 * ) ] ≥ 1 − 𝛿 , we conclude that this event happens with probability at most 𝛿 . Hence, ℙ ⁢ [ 𝑅 ⁢ ( 𝝀 ^ ) ≤ 𝜖 ] ≥ 1 − 𝛿 and ℐ 𝝀 ^ ⁢ ( 𝑦 ) is an ( 𝜖 , 𝛿 ) -RCPS.

Lastly, it is easy to see that 𝝀 ^ minimizes the mean interval length 𝐼 ¯ ⁢ ( 𝝀 ) over 𝚲 ~ . Note that

𝐼 ¯ ⁢ ( 𝝀 )

1 𝑑 ⁢ ∑ 𝑗 ∈ [ 𝑑 ] ( 𝑢 ^ 𝑗 − 𝑙 ^ 𝑗 ) + 2 ⁢ ∑ 𝑗 ∈ [ 𝑑 ] 𝜆 𝑗 ,

(40)

and the statement follows by definition. ∎

A.3Proof that ℓ 𝛾 is a convex upper bound to ℓ 01 (see Equation 16)

Recall that for a family of set-valued predictors { ℐ 𝝀 ⁢ ( 𝑦 )

[ 𝑙 ^ 𝑗 − 𝜆 𝑗 , 𝑢 ^ 𝑗 + 𝜆 𝑗 ] } 𝝀 ∈ Λ 𝑑 indexed by a 𝑑 -dimensional vector 𝝀

( 𝜆 1 , … , 𝜆 𝑑 ) ∈ Λ 𝑑 , Λ ⊂ ℝ ¯ ≔ ℝ ∪ { ± ∞ } for some general lower and upper bounds 𝑙 ^ 𝑗 < 𝑢 ^ 𝑗 that may depend on 𝑦 , we define ℓ 𝛾 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) ) to be

ℓ 𝛾 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) )

1 𝑑 ⁢ ∑ 𝑗 ∈ [ 𝑑 ] [ 2 ⁢ ( 1 + 𝑞 ) 𝐼 ⁢ ( 𝝀 ) 𝑗 ⁢ | 𝑥 𝑗 − 𝑐 𝑗 | − 𝑞 ] + ,

(41)

where 𝑞

𝛾 / ( 1 − 𝛾 ) , 𝛾 ∈ [ 0 , 1 ) , 𝐼 ⁢ ( 𝝀 ) 𝑗

𝑢 ^ 𝑗 − 𝑙 ^ 𝑗 + 2 ⁢ 𝜆 𝑗 , 𝑐 𝑗

( 𝑢 ^ 𝑗 + 𝑙 ^ 𝑗 ) / 2 , and [ 𝑢 ] +

max ⁡ ( 0 , 𝑢 ) . First, we show that ℓ 𝛾 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) ) is convex in 𝝀 for 𝝀 ≥ 0 .

Proof.

Note that ℓ 𝛾 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) ) is separable in 𝝀 . Hence, it suffices to show that ℓ 𝛾 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) ) is convex in each entry 𝜆 𝑗 . That is, we want to show that

ℓ 𝛾 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) ) 𝑗

[ 2 ⁢ ( 1 + 𝑞 ) 𝑢 ^ 𝑗 − 𝑙 ^ 𝑗 + 2 ⁢ 𝜆 𝑗 ⁢ | 𝑥 𝑗 − 𝑐 𝑗 | − 𝑞 ] +

(42)

is convex in 𝜆 𝑗 . Note that:

•

The term 1 / ( 𝑢 ^ 𝑗 − 𝑙 ^ 𝑗 + 2 ⁢ 𝜆 𝑗 ) behaves like 1 / 𝜆 𝑗 , hence it is convex for 𝜆 𝑗 ≥ 0

− ( 𝑢 ^ 𝑗 − 𝑙 ^ 𝑗 ) / 2 ,

•

𝐶

2 ⁢ ( 1 + 𝑞 ) ⁢ | 𝑥 𝑗 − 𝑐 𝑗 | is nonnegative, hence 𝐶 ⋅ 1 / ( 𝑢 ^ 𝑗 − 𝑙 ^ 𝑗 + 2 ⁢ 𝜆 𝑗 ) is convex,

•

𝑞 does not depend on 𝜆 𝑗 , hence 𝐶 ⋅ 1 / ( 𝑢 ^ 𝑗 − 𝑙 ^ 𝑗 + 2 ⁢ 𝜆 𝑗 ) − 𝑞 is still convex, and finally

•

the positive part [ 𝑢 ] +

max ⁡ ( 0 , 𝑢 ) is a convex function of its argument, hence [ 𝐶 ⋅ 1 / ( 𝑢 ^ 𝑗 − 𝑙 ^ 𝑗 + 2 ⁢ 𝜆 𝑗 ) − 𝑞 ] + is convex.

We conclude that ℓ 𝛾 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) ) 𝑗 is convex in each entry 𝑗 ∈ [ 𝑑 ] for 𝜆 𝑗 ≥ 0 , hence ℓ 𝛾 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) ) is convex for 𝝀 ≥ 0 . ∎

Note that ℓ 𝛾 is an upper bound to ℓ 01 by construction. One can see that ∀ 𝝀 , ℓ 𝛾 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) ) ≥ ℓ 01 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) ) .

Proof.

We will now show that ℓ 𝛾 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) ) 𝑗 ≥ ℓ 01 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) ) 𝑗 entrywise. To this end, we will show that both functions attain the same value (i.e., 1) at the extremes of the intervals (i.e., 𝑙 ^ − 𝝀 and 𝑢 ^ + 𝝀 ), and use the fact that ℓ 𝛾 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) ) 𝑗 is convex nonnegative.

First, note that ∀ 𝝀 , it holds that

ℓ 𝛾 ⁢ ( 𝑙 ^ − 𝝀 , ℐ 𝝀 ⁢ ( 𝑦 ) ) 𝑗

ℓ 𝛾 ⁢ ( 𝑢 ^ + 𝝀 , ℐ 𝝀 ⁢ ( 𝑦 ) ) 𝑗

[ 2 ⁢ ( 1 + 𝑞 ) 𝐼 ⁢ ( 𝝀 ) 𝑗 ⋅ | 𝐼 ⁢ ( 𝝀 ) 𝑗 2 | − 𝑞 ] +

1 ,

(43)

ℓ 01 ⁢ ( 𝑙 ^ − 𝝀 , ℐ 𝝀 ⁢ ( 𝑦 ) ) 𝑗

ℓ 01 ⁢ ( 𝑢 ^ + 𝝀 , ℐ 𝝀 ⁢ ( 𝑦 ) ) 𝑗

1 .

(44)

Furthermore,
ℓ 01 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) ) 𝑗

0 , ∀ 𝑥 𝑗 ∈ [ 𝑙 ^ 𝑗 − 𝜆 𝑗 , 𝑢 ^ 𝑗 + 𝜆 𝑗 ]

(45)

by definition. We conclude that ℓ 𝛾 upper bounds ℓ 01 because ℓ 𝛾 is convex, nonnegative, it intersects ℓ 01 at 𝑙 ^ − 𝝀 and 𝑢 ^ + 𝝀 (for which both losses are equal to 1), and ℓ 01 is exactly 0 between 𝑙 ^ 𝑗 − 𝜆 𝑗 and 𝑢 ^ 𝑗 + 𝜆 𝑗 . ∎

Appendix BRisk Controlling Prediction Sets (RCPS) [10]

In this section, we present the original RCPS procedure presented in Bates et al. [10]. Let ℓ : 𝒴 × 𝒴 ′ → ℝ , 𝒴 ′ ⊆ 2 𝒴 be a monotonically nonincreasing loss function (see Equation 4) over 𝒳 ⊂ ℝ 𝑑 and 𝒴 ⊂ ℝ 𝑑 , and let { ℐ 𝜆 ⁢ ( 𝑦 ) } 𝜆 ∈ Λ , Λ ⊂ ℝ ¯ be a family of set-valued predictors ℐ : 𝒴 → 𝒳 ′ that satisfies the nesting property in Equation 5. Here,

Algorithm 2 summarizes the original conformal risk control procedure introduced in Bates et al. [10] for a general bounding function UCB ⁢ ( 𝑛 , 𝛿 , 𝑅 ^ ⁢ ( 𝜆 ) ) that accepts the number of samples in a calibration set 𝒮 cal

{ ( 𝑥 𝑖 , 𝑦 𝑖 ) } 𝑖

1 𝑛 of 𝑛 i.i.d. samples from an unknown distribution 𝒟 over 𝒳 × 𝒴 , a failure probability 𝛿 ∈ [ 0 , 1 ] , the empirical estimate 𝑅 ^ ⁢ ( 𝜆 )

1 / 𝑛 ⋅ ∑ 𝑖

1 𝑛 ℓ ⁢ ( 𝑥 𝑖 , ℐ 𝜆 ⁢ ( 𝑦 𝑖 ) ) evaluated on 𝒮 cal , and that returns a pointwise upper confidence bound 𝑅 ^ + ⁢ ( 𝜆 ) that satisfies

ℙ ⁢ [ 𝑅 ⁢ ( 𝜆 ) ≤ 𝑅 ^ + ⁢ ( 𝜆 ) ] ≥ 1 − 𝛿

(46)

as presented in Equation 6. For example, for losses bounded above by 1, Hoeffding’s inequality [24] yields

𝑅 ^ + ⁢ ( 𝜆 )

UCB ⁢ ( 𝑛 , 𝛿 , 𝑅 ^ ⁢ ( 𝜆 ) )

𝑅 ^ ⁢ ( 𝜆 ) + 1 2 ⁢ 𝑛 ⁢ log ⁡ ( 1 𝛿 ) .

(47)

In practice, tighter alternatives exist (see Bates et al. [10], Section 3.1 for a thorough discussion).

Algorithm 2 ( 𝜖 , 𝛿 ) -RCPS (see [6], Algorithm 2) 1:  Input: risk level 𝜖 ≥ 0 , failure probability 𝛿 ∈ [ 0 , 1 ] , calibration set 𝒮 cal

{ ( 𝑥 𝑖 , 𝑦 𝑖 ) } 𝑖

1 𝑛 of 𝑛 i.i.d. samples, monotonically nonincreasing loss function ℓ , family of nested set-valued predictors { ℐ 𝜆 } 𝜆 ∈ Λ , Λ ⊂ ℝ ¯ , initial (large) value 𝜆 max , stepsize d ⁢ 𝜆

0 . 2:   𝜆 ← 𝜆 max 3:   𝑅 ^ + ⁢ ( 𝜆 ) ← 0 4:  while  𝑅 ^ + ⁢ ( 𝜆 ) ≤ 𝜖  do 5:      𝜆 ← 𝜆 − d ⁢ 𝜆 6:      𝑅 ^ ⁢ ( 𝜆 ) ← 1 / 𝑛 ⋅ ∑ ( 𝑥 𝑖 , 𝑦 𝑖 ) ∈ 𝒮 cal ℓ ⁢ ( 𝑥 𝑖 , ℐ 𝜆 ⁢ ( 𝑦 𝑖 ) ) 7:      𝑅 ^ + ⁢ ( 𝜆 ) ← UCB ⁢ ( 𝑛 , 𝛿 , 𝑅 ^ ⁢ ( 𝜆 ) ) 8:  end while 9:   𝜆 ^ ← 𝜆 + d ⁢ 𝜆 10:  return 𝜆 ^ Appendix CComputing the UCB

In this section, we include a detailed analytical example on how one can compute the UCB 𝑅 ^ 01 + ⁢ ( 𝝀 + 𝜼 ) by means of concentration inequalities. Recall that, for a family of nested set predictors { ℐ 𝝀 ⁢ ( 𝑦 ) } 𝝀 ∈ Λ 𝑑 indexed by a vector 𝝀

( 𝜆 1 , … , 𝜆 𝑑 ) , the 01 loss ℓ 01 ⁢ ( 𝑥 , ℐ 𝝀 ⁢ ( 𝑦 ) ) counts the number of pixels in 𝑥 that fall outside of their respective intervals in ℐ 𝝀 ⁢ ( 𝑦 ) . For example, choosing ℐ 𝝀 ⁢ ( 𝑦 ) 𝑗

[ 𝑙 ^ 𝑗 − 𝜆 𝑗 , 𝑢 ^ 𝑗 + 𝜆 𝑗 ] as proposed in Equation 11, given a vector 𝜼

( 𝜂 1 , … , 𝜂 𝑑 ) yields

ℓ 01 ⁢ ( 𝑥 , ℐ 𝝀 + 𝜼 ⁢ ( 𝑦 ) )

1 𝑑 ⁢ ∑ 𝑗 ∈ [ 𝑑 ] 𝟙 ⁢ [ 𝑥 𝑗 ∉ [ 𝑙 ^ 𝑗 − ( 𝜆 𝑗 + 𝜂 𝑗 ) , 𝑢 ^ 𝑗 + ( 𝜆 𝑗 + 𝜂 𝑗 ) ] ] .

(48)

Then, 𝑅 01 ⁢ ( 𝝀 + 𝜼 )

𝔼 ⁢ [ ℓ 01 ⁢ ( 𝑥 , ℐ 𝝀 + 𝜼 ⁢ ( 𝑦 ) ) ] denotes the risk of ℐ 𝝀 + 𝜼 and its empirical estimate over a calibration set 𝒮 cal

{ ( 𝑥 𝑖 , 𝑦 𝑖 ) } 𝑖

1 𝑛 of 𝑛 i.i.d. samples from an unknown distribution 𝒟 over 𝒳 × 𝒴 is

𝑅 ^ 01 ⁢ ( 𝝀 + 𝜼 )

1 𝑛 ⁢ ∑ 𝑖 ∈ [ 𝑛 ] ℓ 01 ⁢ ( 𝑥 𝑖 , ℐ 𝝀 + 𝜼 ⁢ ( 𝑦 𝑖 ) ) .

(49)

In turn, for a user-specified failure probability 𝛿 ∈ [ 0 , 1 ] , the UCB 𝑅 01 + ⁢ ( 𝝀 + 𝜼 ) can be obtained by means of common concentration inequalities. For example, Hoeffding’s inequality implies

𝑅 ^ 01 + ⁢ ( 𝝀 + 𝜼 )

𝑅 ^ 01 ⁢ ( 𝝀 + 𝜼 ) + 1 2 ⁢ 𝑛 ⁢ log ⁡ ( 1 𝛿 ) .

(50) Appendix DExperimental Details

In this section, we include further experimental details. All experiments were performed on a private cluster with 8 NVIDIA RTX A5000 with 24 GB of memory.

D.1Datasets (a)CelebA dataset. (b)AbdomenCT-1K dataset. Figure D.1:Example images. D.1.1CelebA dataset

The CelebA dataset [40] (available at http://mmlab.ie.cuhk.edu.hk/projects/CelebA.html) contains more than 200 × 10 3 , 178 × 218 pixel images of celebrity faces with several landmark locations and binary attributes (e.g., eyeglasses, bangs, smiling). In this work, we center-crop all images to 128 × 128 pixels and normalize them between [ − 1 , 1 ] .

D.1.2AbdomenCT-1K dataset

The AbdomenCT-1K dataset [41] (available at https://github.com/JunMa11/AbdomenCT-1K) comprises more than 1000 abdominal CT scans (for a total of more than 200 × 10 3 , 512 × 512 pixel individual images) aggregated from 6 existing datasets. Scans are provided in NIfTI format, so we first convert them to their Hounsfield unit (HU) values and subsequently window them with the standard abdomen setting (WW = 400, WL = 40) such that pixels intensities are normalized in [ 0 , 1 ] and they represent the same tissue across images.

Figure D.1 shows some example images for both datasets.

D.2Models

Recall that in this work, we train both:

•

A score network 𝑠 ⁢ ( 𝑥 ~ , 𝑡 ) ≈ ∇ 𝑥 log ⁡ 𝑝 𝑡 ⁢ ( 𝑥 ~ ) to sample from 𝑝 ⁢ ( 𝑥 | 𝑦 ) as introduced in Section 2.1, and

•

a modified time-conditional image regressor 𝑓 : 𝒴 × ℝ → 𝒳 3 such that 𝑓 ⁢ ( 𝑦 , 𝑡 )

( 𝑞 ^ 𝛼 / 2 , 𝑥 ^ , 𝑞 ^ 𝛼 / 2 ) , where 𝑥 ^ ≈ 𝔼 ⁢ [ 𝑥 ∣ 𝑦 ] and 𝑞 ^ 𝛼 / 2 , 𝑞 ^ 1 − 𝛼 / 2 are the entrywise 𝛼 / 2 and 1 − 𝛼 / 2 quantile regressors of 𝑥 [34, 45, 6], respectively.

Both models are implemented wit the same U-net-like [46] backbone: NCSN++, which was introduced by Song et al. [53] (code is available at https://github.com/yang-song/score_sde). We use the original NCSN++ configurations presented in Song et al. [53] for the CelebA dataset and, for the AbdomenCT-1K dataset, for the FFHQ dataset (available at https://github.com/NVlabs/ffhq-dataset) given the larger image size of 512 × 512 . For the image regressor 𝑓 , we use the original implementation of the quantile regression head used in Angelopoulos et al. [6] (available at https://github.com/aangelopoulos/im2im-uq) on top of the NCSN++ backbone. This allows us to maintain a time-conditional backbone and extend the original image regressor presented in Angelopoulos et al. [6] to all noise levels as the score network.

D.3Training D.3.1Data Augmentation

For both datasets, we augment the training data by means of random horizontal and vertical flips, and random rotations between [ − 𝜋 / 2 , 𝜋 / 2 ] degrees.

D.3.2Forward SDE (a)CelebA dataset. (b)AbdomenCT-1K dataset. Figure D.2:Example of perturbed images via the forward SDE. The final level of noise is 𝜎 2

1 .

Recall that in this work, we are interested in solving the classical denoising problem where 𝑦

𝑥 + 𝑣 0 is a noisy observation of a ground truth image 𝑥 perturbed with random Gaussian noise with known variance 𝜎 0 2 . As done by previous works [50, 51, 54, 31], we model the observation process with a variance exploding (VE) forward-time SDE

d ⁢ 𝑥

d ⁢ [ 𝜎 2 ⁢ ( 𝑡 ) ] d ⁢ 𝑡 ⁢ d ⁢ 𝑤 where 𝜎 ⁢ ( 𝑡 )

𝜎 min ⁢ ( 𝜎 max 𝜎 min ) 𝑡 , 𝑡 ∈ [ 0 , 1 ]

(51)

such that 𝜎 ⁢ ( 0 )

𝜎 min and 𝜎 ⁢ ( 1 )

𝜎 max . In particular, we set 𝜎 min

0 and 𝜎 max

90 for the CelebA dataset and 𝜎 max

1 for the AbdomenCT-1K dataset. It has been shown [53] that the above forward-time SDE is equivalent to the following discrete Markov chain

𝑥 𝑡

𝑥 𝑡 − 1 + 𝜎 𝑡 2 − 𝜎 𝑡 − 1 2 ⁢ 𝑧 , 𝑧 ∼ 𝒩 ⁢ ( 0 , 𝕀 ) , for 𝑡

1 , … , 𝑁

(52)

and { 𝜎 𝑖 } 𝑖

0 𝑁 noise levels. That is, 𝑥 𝑡

𝑥 + 𝑧 𝑡 , where 𝑧 𝑡 ∼ ( 0 , 𝜎 𝑡 2 ) . Figure D.2 shows some example images from both datasets perturbed via the forward SDE described in this section.

D.3.3Denoising Score-matching

Here, we briefly describe the loss function used to train the time-conditional score network 𝑠 ⁢ ( 𝑥 ~ , 𝑡 ) . Denote 𝜃 ∈ Θ the parametrization of 𝑠 , then, following Song and Ermon [50], Song et al. [53], we have 𝑠 ⁢ ( 𝑥 ~ , 𝑡 )

𝑠 𝜃 * ⁢ ( 𝑥 ~ , 𝑡 ) , where

𝜃 *

arg ⁡ min 𝜃 ∈ Θ 𝔼 𝑡 ∼ 𝑈 ⁢ ( 0 , 1 ) [ 𝜉 ( 𝑡 ) 𝔼 𝑥 ∼ 𝑝 ⁢ ( 𝑥 ) , 𝑥 ⁢ ( 𝑡 ) | 𝑥 [ ∥ 𝑠 𝜃 ( 𝑥 ( 𝑡 ) , 𝑡 ) − ∇ 𝑥 log 𝑝 𝑡 ( 𝑥 ( 𝑡 ) | 𝑥 ) ∥ 2 ] ]

(53)

= arg ⁡ min 𝜃 ∈ Θ ⁡ 𝔼 𝑡 ∼ 𝑈 ⁢ ( 0 , 1 ) ⁢ [ 𝜉 ⁢ ( 𝑡 ) ⁢ 𝔼 𝑥 ∼ 𝑝 ⁢ ( 𝑥 ) , 𝑥 ⁢ ( 𝑡 ) | 𝑥 ⁢ [ ‖ 𝑠 𝜃 ⁢ ( 𝑥 ⁢ ( 𝑡 ) , 𝑡 ) + 𝑥 ⁢ ( 𝑡 ) − 𝑥 𝜎 ⁢ ( 𝑡 ) ‖ 2 ] ] ,

(54)

where 𝜉 ⁢ ( 𝑡 ) ∝ 𝜎 2 ⁢ ( 𝑡 ) and 𝑈 ⁢ ( 0 , 1 ) is the uniform distribution over [ 0 , 1 ] .

D.3.4Quantile Regression (a)CelebA dataset. (b)AbdomenCT-1K dataset. Figure D.3:Example of results with the modified image regressor.

Similarly to above, we briefly describe the loss function used to train the modified time-conditional image regressor 𝑓 . Denote 𝜃 ∈ Θ the parametrization of 𝑓 , and recall that for a desired 𝛼 quantile and its respective quantile regressor 𝑞 ^ 𝛼 , the quantile loss function [34, 45, 6] ℓ 𝛼 ⁢ ( 𝑥 , 𝑞 ^ 𝛼 ) is

ℓ 𝛼 ⁢ ( 𝑥 , 𝑞 ^ 𝛼 )

𝛼 ⁢ ( 𝑥 − 𝑞 ^ 𝛼 ) ⋅ 𝟙 ⁢ [ 𝑥

𝑞 ^ 𝛼 ] + ( 1 − 𝛼 ) ⁢ ( 𝑞 ^ 𝛼 − 𝑥 ) ⋅ 𝟙 ⁢ [ 𝑥 ≤ 𝑞 ^ 𝛼 ] .

(55)

For the image regressor 𝑓 , we set 𝛼

0.10 and use the original implementation of the quantile regression head from Angelopoulos et al. [6] (available at https://github.com/aangelopoulos/im2im-uq) which minimizes the multi-loss objective

ℒ ⁢ ( 𝑥 , 𝑓 ⁢ ( 𝑦 , 𝑡 ) )

ℓ 𝛼 / 2 ⁢ ( 𝑥 , 𝑞 ^ 𝛼 / 2 ) + ( 𝑥 − 𝑥 ^ ) 2 + ℓ 1 − 𝛼 / 2 ⁢ ( 𝑥 , 𝑞 ^ 1 − 𝛼 / 2 )

(56)

on top of the NCSN++ backbone. This allows us to maintain a time-conditional backbone and extend the original image regressor presented in Angelopoulos et al. [6] to all noise levels as the score network. Then, 𝑓 ⁢ ( 𝑦 , 𝑡 )

𝑓 𝜃 * ⁢ ( 𝑦 , 𝑡 ) where

𝜃 *

arg ⁡ min 𝜃 ∈ Θ 𝔼 𝑡 ∼ 𝑈 ⁢ ( 0 , 1 ) [ ℒ ( 𝑥 , 𝑓 ( 𝑥 ( 𝑡 ) , 𝑡 ) ] .

(57) D.4Sampling (a)CelebA dataset. (b)AbdomenCT-1K dataset. Figure D.4:Example of images sampled via Algorithm 3.

Here, we briefly describe the sampling procedure used in this work to solve the conditional reserve-time SDE

d ⁢ 𝑥

[ ℎ ⁢ ( 𝑥 , 𝑡 ) − 𝑔 ⁢ ( 𝑡 ) 2 ⁢ ∇ 𝑥 log ⁡ 𝑝 𝑡 ⁢ ( 𝑥 | 𝑦 ) ] ⁢ d ⁢ 𝑡 + 𝑔 ⁢ ( 𝑡 ) ⁢ d ⁢ 𝑤 ¯

(58)

where 𝑦 is the initial noisy observation with known noise level 𝜎 0 2 , and 𝑔 ⁢ ( 𝑡 )

d ⁢ [ 𝜎 2 ⁢ ( 𝑡 ) ] / d ⁢ 𝑡 , ℎ ⁢ ( 𝑥 , 𝑡 )

0 as in Equation 51. Although several different discretization schemes exist [53], we use the classical Euler-Maruyama discretization [30] since the contribution of this work is not focused on improving existing diffusion models. Recall that for a general Itô process

d ⁢ 𝑥

ℎ ⁢ ( 𝑥 , 𝑡 ) ⁢ d ⁢ 𝑡 + 𝑔 ⁢ ( 𝑡 ) ⁢ d ⁢ 𝑤 ,

(59)

its Euler-Maruyama discretization with step Δ ⁢ 𝑡 is

𝑥 𝑡 + 1

𝑥 𝑡 + ℎ ⁢ ( 𝑥 , 𝑡 ) ⁢ Δ ⁢ 𝑡 + 𝑔 ⁢ ( 𝑡 ) ⁢ Δ ⁢ 𝑡 ⁢ 𝑧 , 𝑧 ∼ 𝒩 ⁢ ( 0 , 𝕀 ) .

(60)

Furthermore, under the forward SDE described in Equation 51, and as shown by previous works [32, 31, 29], it holds that

∇ 𝑥 log ⁡ 𝑝 𝑡 ⁢ ( 𝑥 ⁢ ( 𝑡 ) | 𝑦 )

∇ 𝑥 log ⁡ 𝑝 𝑡 ⁢ ( 𝑥 ⁢ ( 𝑡 ) ) + 𝑦 − 𝑥 ⁢ ( 𝑡 ) 𝜎 0 2 − 𝜎 2 ⁢ ( 𝑡 ) .

(61)

We conclude that the reverse-time Euler-Maruyama discretization of the conditional SDE above is

𝑥 𝑡 − 1

𝑥 𝑡 + 𝑔 𝑡 2 ⁢ [ ∇ 𝑥 log ⁡ 𝑝 𝑡 ⁢ ( 𝑥 𝑡 ) + 𝑦 − 𝑥 𝑡 𝜎 0 2 − 𝜎 𝑡 2 ] ⁢ Δ ⁢ 𝑡 + 𝑔 𝑡 ⁢ Δ ⁢ 𝑡 ⁢ 𝑧 , 𝑧 ∼ 𝒩 ⁢ ( 0 , 𝕀 ) .

(62)

Algorithm 3 implements the sampling procedure for a general score network 𝑠 ⁢ ( 𝑥 ~ , 𝑡 ) .

Algorithm 3 Denoising Reverse-time SDE 1:  Input: observation 𝑦 , initial noise level 𝜎 0 , 𝜎 max , 𝜎 min , number of steps 𝑁 2:   𝑡 0 ← ( log ⁡ 𝜎 0 − log ⁡ 𝜎 min ) / ( log ⁡ 𝜎 max − log ⁡ 𝜎 min ) 3:   Δ ⁢ 𝑡 ← 1 / 𝑁 4:   𝑛 ← ⌊ 𝑡 0 / Δ ⁢ 𝑡 ⌋ 5:   𝑥 𝑛 ← 𝑦 6:  for  𝑖

𝑛 , … , 1  do 7:     Draw 𝑧 𝑖 ∼ 𝒩 ⁢ ( 0 , 𝕀 ) 8:      𝑡 𝑖 ← 𝑖 ⁢ Δ ⁢ 𝑡 9:      𝜎 𝑖 ← 𝜎 min ⋅ ( 𝜎 max / 𝜎 min ) 𝑡 𝑖 10:      𝑔 𝑖 ← 𝜎 𝑖 ⋅ 2 ⁢ log ⁡ ( 𝜎 max / 𝜎 min ) 11:      𝑥 𝑖 − 1 ← 𝑥 𝑖 + 𝑔 𝑖 2 ⁢ [ 𝑠 ⁢ ( 𝑥 𝑖 , 𝑡 𝑖 ) + ( 𝑦 − 𝑥 𝑖 ) / ( 𝜎 0 2 − 𝜎 𝑖 2 ) ] ⁢ Δ ⁢ 𝑡 + 𝑔 𝑖 ⁢ Δ ⁢ 𝑡 ⁢ 𝑧 𝑖 12:  end for 13:  return 𝑥 0 Appendix EComparison with Conffusion

In this section, we discuss the differences between the Con 𝑓 ⁢ 𝑓 ⁢ 𝑢 ⁢ 𝑠 ⁢ 𝑖 ⁢ 𝑜 ⁢ 𝑛 framework proposed by Horwitz and Hoshen [26] and the contributions of this paper. Although similar in spirit and motivation, the two are fundamentally different and address separate and distinct questions. Con 𝑓 ⁢ 𝑓 ⁢ 𝑢 ⁢ 𝑠 ⁢ 𝑖 ⁢ 𝑜 ⁢ 𝑛 deploys ideas of quantile regression [34] to fine-tune an existing score network and obtain an image regressor equipped with heuristic uncertainty intervals. Such intervals can then be conformalized to provide risk control. On the other hand, our 𝐾 -RCPS is a novel high-dimensional calibration procedure for any stochastic sampler and any notion of uncertainty (i.e., it is agnostic of the notion of uncertainty), including diffusion models and quantile regression. In this paper, we present 𝐾 -RCPS for diffusion models given their remarkable performance in solving inverse problems via conditional sampling.

In order to contextualize the choices of parametrization for the families of set predictors in Equations 19 and 20, we highlight a gap between the presentation of Con 𝑓 ⁢ 𝑓 ⁢ 𝑢 ⁢ 𝑠 ⁢ 𝑖 ⁢ 𝑜 ⁢ 𝑛 in the arXiv paper available at https://arxiv.org/abs/2211.09795v1 and the official code release in https://github.com/eliahuhorwitz/Conffusion. In particular Section 3.2 of Horwitz and Hoshen [26] introduces the following family of set predictors:

ℐ 𝝀 , Conffusion arXiv ⁢ ( 𝑦 ) 𝑗

[ 𝜆 𝑗 ⁢ ( 𝑞 ^ 𝛼 / 2 ) 𝑗 , 𝜆 𝑗 ⁢ ( 𝑞 ^ 1 − 𝛼 / 2 ) 𝑗 ] ,

(63)

which does not satisfy the nesting property in Equation 5. It is easy to see that—without any further assumptions—as 𝜆 𝑗 increases, ℐ 𝝀 , Conffusion arXiv ⁢ ( 𝑦 ) 𝑗 does not cover the interval [ 0 , 1 ] and the 01 loss in Equation 10 is not entrywise monotonically non-increasing. This renders the RCPS procedure (and most calibration procedures) not applicable as presented in the arXiv paper. While this family of set predictors is thus not applicable, we resorted to the authors’ GitHub release where such parametrization is different (see https://github.com/eliahuhorwitz/Conffusion/blob/fffe5c946219cf9dead1a1c921a131111e31214e/inpainting_n_conffusion/core/calibration_masked.py#L28). More precisely, the GitHub implementation reflects the multiplicative parametrization presented in Equation 19, which does indeed satisfy the entrywise nesting property. Finally, we additionally propose the additive parametrization in Equation 20 to showcase how 𝐾 -RCPS is agnostic of the notion of uncertainty and it can be used in conjunction with Con 𝑓 ⁢ 𝑓 ⁢ 𝑢 ⁢ 𝑠 ⁢ 𝑖 ⁢ 𝑜 ⁢ 𝑛 .

Appendix FErratum of Theorem 3.3

In this section, we address the differences between the version of Theorem 3.3 presented in this manuscript and the published paper available at https://proceedings.mlr.press/v202/teneggi23a.html, which contains a small typo. We include the two theorems side-by-side with differences highlighted.

Theorem (This manuscript). Let ℓ : 𝒳 × 𝒳 ′ → ℝ , 𝒳 ′ ⊆ 2 𝒳 , 𝒳 ⊂ ℝ 𝑑 be an entrywise monotonically nonincreasing function and let { ℐ 𝛌 ⁢ ( 𝑦 )

[ 𝑙 ^ 𝑗 − 𝜆 𝑗 , 𝑢 ^ 𝑗 + 𝜆 𝑗 ] } 𝛌 ∈ Λ 𝑑 be a family of set-valued predictors ℐ : 𝒴 → 𝒳 ′ , 𝒴 ⊂ ℝ 𝑑 indexed by 𝛌 ∈ Λ 𝑑 , Λ ⊂ ℝ ¯ , for some lower and upper bounds 𝑙 ^ 𝑗 < 𝑢 ^ 𝑗 that may depend on 𝑦 . Given 𝚲 ~

𝛌 ~ + 𝜔 ⁢ 𝛈 , 𝜔 ∈ Λ , for fixed 𝛌 ~ ∈ ℝ 𝑑 and 𝛈 ∈ ℝ 𝑑 , 𝛈 ≥ 0 , if
𝝀 ^

arg ⁡ min 𝝀 ∈ 𝚲 ~ ⁢ ∑ 𝑗 ∈ [ 𝑑 ] 𝜆 𝑗 s.t. 𝑅 ^ + ⁢ ( 𝝀 + 𝛽 ⁢ 𝜼 ) < 𝜖

∀ 𝛽 ≥ 0 , then ℐ 𝛌 ^ ⁢ ( 𝑦 ) is an ( 𝜖 , 𝛿 ) -RCPS and 𝛌 ^ minimizes the mean interval length over 𝚲 ~ .

 

Theorem (Published paper). Let ℓ : 𝒳 × 𝒳 ′ → ℝ , 𝒳 ′ ⊆ 2 𝒳 , 𝒳 ⊂ ℝ 𝑑 be an entrywise monotonically nonincreasing function and let { ℐ 𝛌 ⁢ ( 𝑦 )

[ 𝑙 ^ 𝑗 − 𝜆 𝑗 , 𝑢 ^ 𝑗 + 𝜆 𝑗 ] } 𝛌 ∈ Λ 𝑑 be a family of set-valued predictors ℐ : 𝒴 → 𝒳 ′ , 𝒴 ⊂ ℝ 𝑑 indexed by 𝛌 ∈ Λ 𝑑 , Λ ⊂ ℝ ¯ , for some lower and upper bounds 𝑙 ^ 𝑗 < 𝑢 ^ 𝑗 that may depend on 𝑦 . For a fixed vector 𝛈 ∈ ℝ 𝑑 , 𝛈 ≥ 0 , if
𝝀 ^

arg ⁡ min 𝝀 ∈ Λ 𝑑 ⁢ ∑ 𝑗 ∈ [ 𝑑 ] 𝜆 𝑗 s.t. 𝑅 ^ + ⁢ ( 𝝀 + 𝛽 ⁢ 𝜼 ) < 𝜖

∀ 𝛽 ≥ 0 , then ℐ 𝛌 ^ ⁢ ( 𝑦 ) is an ( 𝜖 , 𝛿 ) -RCPS, and 𝛌 ^ minimizes the mean interval length.

Reason for the differences

The domain of the optimization problem in the published paper, i.e. 𝝀 ∈ Λ 𝑑 , does not reflect the pointwise coverage guarantee provided by 𝑅 ^ + . That is, for each fixed 𝝀 ∈ Λ 𝑑 , ℙ ⁢ [ 𝑅 ⁢ ( 𝝀 ) ≤ 𝑅 ^ + ⁢ ( 𝝀 ) ] ≥ 1 − 𝛿 . To solve the optimization problem over 𝝀 ∈ Λ 𝑑 , 𝑅 ^ + should provide uniform coverage, i.e. ∀ 𝝀 ∈ Λ 𝑑 , ℙ ⁢ [ 𝑅 ⁢ ( 𝝀 ) ≤ 𝑅 ^ + ⁢ ( 𝝀 ) ] ≥ 1 − 𝛿 .

Effect on results

We remark that the changes in Theorem 3.3 do not affect the 𝐾 -RCPS procedure nor the results presented in the published version of the paper.

Appendix GFigures

This section contains supplementary figures.

(a)CelebA dataset. (b)AbdomenCT-1K dataset. Figure G.1:Empirical estimates of risk over 20 random draws of 𝒮 cal . All combinations of notion of uncertainty and calibration procedure successfully control risk at level 𝜖

0.10 , 0.05 for the CelebA and AbdomenCT-1K dataset, respectively, with probability at least 1 − 𝛿 , 𝛿

0.10 . 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.

Report Issue Report Issue for Selection