Quantile Risk Control: A Flexible Framework for Bounding the Probability of High-Loss Predictions
Authors: Jake Snell
Thomas P Zollo
Zhun Deng
Toniann Pitassi
Richard Zemel
Venue: ICLR 2023 poster (2023)
Keywords: distribution-free uncertainty quantification

Abstract: Rigorous guarantees about the performance of predictive algorithms are necessary in order to ensure their responsible use. Previous work has largely focused on bounding the expected loss of a predictor, but this is not sufficient in many risk-sensitive applications where the distribution of errors is important. In this work, we propose a flexible framework to produce a family of bounds on quantiles of the loss distribution incurred by a predictor. Our method takes advantage of the order statistics of the observed loss values rather than relying on the sample mean alone. We show that a quantile is an informative way of quantifying predictive performance, and that our framework applies to a variety of quantile-based metrics, each targeting important subsets of the data distribution. We analyze the theoretical properties of our proposed method and demonstrate its ability to rigorously control loss quantiles on several real-world datasets.

Published as a conference paper at ICLR 2023
QUANTILE RISK CONTROL: A FLEXIBLE FRAME- WORK FOR BOUNDING THE PROBABILITY OF HIGH- LOSS PREDICTIONS
Jake C. Snell" Princcton University
Thomas P. Zollo
Zhun Deng
Columbia University
Columbia University
js2523@princet on edu
tpz21056co1img col www.aooa.baa.....ooo........aaal edu
2d2322 ( coolecolllna coooumbaa...m edu
Toniann Pitassi
Richard Zemel
Columbia University
Columbia University
& University of Toronto
& University of Toronto zemelêce cs. umbia edu
toniècs. col umbia edu
ABSTRACT
Rigorous guarantees about the performance of predictive algorithms are neces- sary order to ensure their responsible use. Previous work has largely focused on bounding the expected loss of a predictor, but this is not sufficient in many risk- this work, we propose a flexible framework to produce a family of bounds on quantiles of the loss distribution incurred by a predictor. Our method takes advantage the order statistics of the observed loss values rather than relying on the sample mean alone. We show that a quantile an informative way of quantifying predictive per- formance, and that framework applies to variety of quantile-based metrics, each targeting important subsets of the data distribution. We analyze the theoret- ical properties of proposed method and demonstrate its ability rigorously control loss quantiles on several real-world datasets.
sensitive applications where the distribution errors important.
INTRODUCTION
Learning-baat based predictive algorithms have great opportunity for impact, particularly in domains such as healthcare, finance and government, where outcomes carry long-lasting individual and so- cietal consequences. Predictive algorithms such as deep neural networks have the potential to au- tomate plethora of manually intensive tasks, saving vast amounts of time and money. Moreover, when deployed responsibly, there is great potential for a better decision process, by improving the consistency, transparency, and guarantees of the system. As just example, recent survey found that a majority radiologists anticipated that Al-based solutions will lead to fewer medical errors, less time spent each exam, and more time spent with patients (Waymel et al.) 2019). In order to realize such benefits, it is crucial that predictive algorithms are rigorously yet flexibly validated prior deployment. The validation should be rigorous in the sense that it produces bounds that can be trusted with high confidence. It should also be flexible in several ways. First, we aim to provide bounds on a variety of loss-related quantities (risk measures): the bound could apply to the mean loss, or the 90th percentile loss, or the average loss of the 20% worst cases. Furthermore, the guar- antees should adapt to the difficulty of the instance: easy instances should have strong guarantees, and as the instances become harder, the guarantees weaken to reflect the underlying uncertainty. We also want to go beyond simply bounding the performance of a fixed predictor and instead choose the optimal predictor from set of candidate hypotheses that minimizes some target risk measure.
Validating the trustworthiness and rigor given predictive algorithm a very challenging task. One major obstacle is that the guarantees output by the validation procedure should hold with spect to any unknown data distribution and across a broad class of predictors including deep neural
Work done while University of Toronto and Vector Institute.

---

Published as a conference paper at ICLR 2023
arg toin (5) bSN
A-all
3 3-C
Bnine Pu VaR Intersal Fog
Fo
For
F L.LAA
Prom Brone
(a) Bounding multiple QBRMs with P.- (p).
(b) Selecting the optimal h" with target risk measure.
Figure 1: An overview of our quantile risk control framework. Given n validation samples KI....,,, drawn i.idd from the loss distribution with CDF F we produce a upper confidence bound (p) on the true quantile function (p) inf F(x) 2 p). (a). The same bound on the quantile function can be used to bound multiple quantile-based risk measures. (b). An upper bound F 1,6 is computed for the quantile function of the loss distribution of each pre- dictor h H. and the one minimizing R (h) So (p)) 1, (p) dp is selected. Here the target measure is the 3-VaR.
upper confidence bound the target risk measure
networks and complicated black-box algorithms. Recent work has built upon distribution-free uncer- lainty quantification provide rigorous bounds for single risk measure: the expected loss (Bates) et al. 2021 Angelopoulos et al. 2021). However, to our knowledge there has been no work that unifies iustrribtion-fire control of set of expressive risk measures into the same framework.
Our key conceptual advancement is to work with lower confidence bounds on the cumulative distri- bution function (CDF) of predictor's loss distribution a fundamental underlying representation. We demonstrate that a lower bound on the CDF can be converted to an upper bound on the quan- tile function. This allows can be expressed as weighted integrals of the quantile function, known as quantile-based risk mea- sures (QBRM) (Dowd & Blake 2006). QBRMs are broad class of risk measures that include expected loss, value-at-rish (VaR), conditional value-at-risk (CVaR) (Rockafellar & Uryasev 2000), and spectral risk measures (Acerbi) (002). Our approach inverts a one-sided goodness-of- statistic to construct a nonparametric lower confidence bound on the loss CDF for each candidate predictor. Furthermore, our confidence lower bounds hold simultaneously across an entire set of candidate predictors, and thus can be used as the basis for optimization of target risk measure. For example, our approach can be used to choose a threshold or set thresholds on the scores produced by a complicated black-box prediction algorithm. Figure T illustrates an overview of our framework.
framework to seamlessly provide bounds for any risk measure that
deep neural network with respect to four representative risk measures. (1). The expected loss is the mean loss over the test distribution. (2). The 3- VaR measures the maximum loss incurred on a specific quantile, after excluding mean loss for the worst 1 - 3 proportion of the population. (4), Finally, the VaR-interval can be interpreted optimizing an uncertain loss quantile that belongs known range, i.e., for range of B values. We compare various methods for controlling these risk measures, including novel one that is tailored to the CVaR and VaR-interval settings, and show that our approach bounds the loss CDF well across all scenarios. We also demonstrate how our framework can be used to achieve fairness by equalizing a target risk measure across groups within the population.
We conduct experiments on real-world datasets where the goal to tune the threshold
proportion of high-loss outliers. (3). The 3-CVaR measures the
Our work unifies the rigorous control of quantile-based risk measures into a simple yet expres- sive framework grounded in lower confidence bounds on the loss CDF Unlike previous approaches which only target a single risk measure, our approach provides flexible and detailed understand- ing of how predictive algorithm will perform after deployment. We provide a family of bounds that hold for any quantile-based risk measure, even those not optimized for prior to deployment. Practitioners using our method can thus easily and confidently respond to inquiries from regulators and other key stakeholders, thereby building trust between organizations deploying predictive algo- rithms and the individuals whose líves are affected by them. This rigorous and flexible validation is an important step towards the responsible use of predictive algorithms in order benefit society.
2

---

Published as a conference paper at ICLR 2023
2 BACKGROUND & RELATED WORK
Distribution-free uncertainty quantification. This line of work originated with conformal pre- diction (Vovk et al. 2005 Shater & Vovk 2008), which seeks to produce coverage guarantees: prediction sets or prediction intervals that are guaranteed to contain the target output with high prob- ability. Conformal prediction offers lightweight algorithm that can be applied on top of complex predictors to obtain provable coverage guarantees. Recent work has generalized conformal predic- tion to bounding the expected loss with respect to more complex loss functions (Bates et al. [02T] Angelopoulos et al., 2021). Like these works, we also interested in provable distribution-fie free guarantees for general loss functions. While previous work focuses on bounding the expected loss, part of our contribution lies in bounding the loss for quantiles of the data distribution. Angelopouloss
& Bates 2022) offer an accessible overview of distribution- free uncertainty quantification.
Empirical processes. Several methods consider the relationship between the empirical and true CDF. The DKW inequality (Dvoretzky et al.) 1956) generates CDF- confidence bounds. Later variants (Massart 1990 Naaman (021) provide tighter bounds or generalize wider settings. The confidence bound provided by the DKW inequality is closely related to the Kolmogorov-Smingg (KS) test (Massey] [95I] classic test of goodness of fit. The KS test has low power for detecting deviations in the tails and so other variance-weighte tests of goodness of fit address this, c.g., Anderson & Darlin (1952); Cramér (1928) order handle extreme tails, Berk & Jones (1979) propose statistic which looks for the most statistically significant deviation. |Moscovich et al. (2016) and Moscovich| (2020) study properties of the Berk-Jones statisties and provide methods for fast computation. To our knowledge, none of these techniques have been used as in our work, to produce bounds on quantiles of the loss distribution incurred by predictor. For more background on quantile functions, the reader may refer to (Shorack 2000 Chapter 7). For an overview of empirical processes, Shorack & Wellner (2009) is a comprehensive reference.
Risk metrics. A number of approaches have been used to estimate confidence intervals for timated risk measures. Our focus is on a broad class of quantile-based risk measures (QBRMs), which includes VaR, CVaR, and spectral risk measures. The value-at-risk the B level (3-Vat VaR) has long been used to express the risk associated with an investment and represents the maximum loss that the investment will incur with probability B. Conditional value-at-risk (CVaR) (Rockafellar & Uryasev 2000) represents the mean loss incurred in the tail of the distribution. The work of Dowd (2010) inspires us; it presents a general approach for estimating confidence intervals for any type of quantile-base risk measure (QBRM). Here we construct confidence bounds on the loss CDF in order to bound such measures for the general problem of predictor selection.
PRELIMINARIES
In this section, we introduce our problem formulation and briefly discuss previous approaches that rigorously bound the expected loss. We then review quantile-based based risk measures (QBRMs), an expressive class of risk measures that includes VaR, CVaR, and spectral risk measures.
3.1 PROBLEM SETUP& & NOTATION
We assume the presence of a black-box predictor : 2 + 5 that maps from an input space to a space of predictions D. We also assume a loss function y) x y + E that quantifies the quality of a prediction Y with respect to the target output Y. Let (Z, Y) be drawn from an unknown data distribution D over x y and define the random variable X A {(h(Z), Y) to be the loss induced by h on D. Recall that the cumulative distribution function (CDF) of random variable X is defined F(x) P(X < x). Our goal is produce rigorous upper bounds on the risk R(F) for rich class of risk measures R E R. given a set of validation loss samples X1m { For detailed summary of the notations we used this paper, please refer to Table 4in Appendix
3.2 DISTRIBUTION-FREE CONTROL OF EXPECTED LOSs
Previous work has investigated distribution-free rigorous control of the expected loss. Recall that F is the CDF of the loss X. Expected loss may be defined as R(F) & E[X]. These methods
3

---

Published as a conference paper at ICLR 2023
typically involve constructing confidence region based on the sample mean X Σ== X; within which the true expected loss will lie with high probability. For example, suppose that E 2 E) & exp(-2ned This may be inverted to provide an upper confidence bound on the expected loss: P(R(P) < ltt (X 2
[0, 1] and let μ & ] Hoeffding's 's inequality states that P(u
1 1-6, 6, where R* (X1m) = the BieeffdingBeentuus inequality (Bates et al. 202T), have also been used control the expected loss. Methods in this class differ primarily in how they achieve simultaneous control of multiple predictors: RCPS (Bates et al. (20IT) does so by assuming monotonicity of the loss with respect to one-dimensional space of predictors and Learn then Test (LTT) (Angelopoulos et al. 202Tb applies a Bonferroni correction in order to achieve family-wise error rate control (Lehmann Romano, 2008 Sec. 9.1).
2m log 3- More sophisticated concentration inequalities, such as
3.3
QUANTILE BASED RISK MEASURES
Unlike previous work that considers only expected loss, we consider class of risk measures known quantile-based risk measures (QBRMs) (Dowd Blake 2006). Recall that the quantile function defined as F- Fp)(p) - inf(x: F(x) p).
Definition (Quantile-based Risk Measure). Let vi(p) be a weighting function such that (p)) 2 0 and So (p) dp 1. The quantile-base risk measure defined by vp is
(F) A S (()F dp.
(1)
Several representative QBRMs are shown in Table T The expected loss targets the overall ex- pectation across the data distribution, whereas the VaR targets the maximum loss incurred by the majority of the population excluding a (1 3) proportion of the population as outliers. CVaR on the other hand targets the worst-off/highest loss tail of the distribution. Finally, the VaR-Interval is valuable when the precise cutoff for outliers is not known. Other QBRMs, egg., spectral risk mea- sures (Acerbi 2002), can easily be handled by framework, but do not consider them here.
Risk Measure
Weighting Function (p)
Expected loss B-VaR
1
8p(p)
p B
3-CVaR
<pp)
1-8-
0,
otherwise
Bmin S S. Bmax
[miin [max] VaR-Itevalll
((p)
otherwise
Table 1: Several quantile- based risk measures and their corresponding weight functions (see Defini-
tion 1). See Figure I for visualizations. The Dirac delta function centered at / is denoted by dg.
4 QUANTILE RISK CONTROL
In this section we introduce our framework Quantile Risk Control (QRC) for achieving rigorous con- trol of quantile-based risk measures (QBRM). QRC inverts a one-sided goodness-of-fh test statistic to produce lower confidence bound on the loss CDF. This can subsequently be used to form family of upper confidence bounds that hold for any QBRM. More formally, specify a confidence level 8 E (0, 1) and let X(1) ... < X()) denote the order statistics of the validation loss samples. QRC consists of the following levhl steps:
1. Choose a one-sided test statistic of the form - minigisn s:(((())) where F the (unknown) CDF of Xı,..., X
4

---

Published as a conference paper at ICLR 2023
2. Compute the critical value sæ such that P(S 2 86) 1 - 8.
3. Construct a CDF lower confidence bound
Fn
defined
by
coordinates
bX(1),bi)..... (n), bn), where b, _ (ss).
4. For any desired QBRM defined by weighting function v, report Ry (Fa) the upper con- fidence bound on (F).
We show below that in fact P(R (P) S (&)())) 1- 8 for any QBRM weighting function dh. If the target weighting function is known a priori, this information can be taken into account when choosing the statistic S. QRC can also be used to bound the risk of multiple predictors simultane- ously by setting the critical value to 8' _ 8/m, where is the number predictors.
Novelty of QRC. There are two primary novel aspects of QRC. The first is the overall framework that uses nonparametric CDF lower confidence bounds as an underlying representation to simultane- ously bound any QBRM. Previous works in distribution- the mean and VaR, but our knowledge none have focused on either the CVaR or VaR-interval. On the other hand, Dowd (2010) shows how to bound QBRMs given CDF estimate but does not pro- vide the tools to bound the CDF from a finite data sample. QRC brings these two ideas together by leveraging modern goodness-of-fi test statistics produce high-quality nonparametric CDF lower bounds from finite data. The second novel aspect of QRC is our proposed forms a truncated Berk-Jones statistic (Appendix C) which refocus the statistical power of standard Berk-Jones to target either the CVaR (one-sided truncation) or VaR-interval (two-sided truncation).
uncertainty quantification have targeted
4.1 CDF LOWER BOUNDS ARE RISK UPPER BOUNDS
We begin by establishing that lower bound G on the true loss CDF incurred by a predictor can be used to bound (F) (F) for any quantile- based risk measure weighting function. However, when we only have access finite sample X1m need to consider lower confidence bounds (LCB) on the CDF, For CDFs F and G. let F
denote F(x) 2 G(x) for all E RR We call F, (1 - LDDF-LCBB for any F, F,P(FZ 2 8, where F,, is a function of X1:1 ridd F.
Theorem 1. Let and be CDFs such that Z G. Then Rus (F) S Rus (G) for any weighting function (p) as defined in Definition Moreover, suppose that Fn, is a (1 8)-CDF-LCB. Then
P(R (F) & Rg((F)) 2 1-66 8.
4.2 INVERTING GOODNESS-OF-TH STATISTICS TO CONSTRUCT CDF LOWER BOUNDS
Our technique centers around producing a set of lower confidence bounds on the uniform order statisties, and using these bound F. Let UI. Un and U(0, 1) and let U() ... < Un))) denote the corresponding order statistics. Consider a one-sided minimum goodness-of-fit (GoF) statistic of the following form:
S min s;(U())) IsiSa
where .1...., [0, 1] R are right continuous monotone nondecreasing functions. This statistic can be used to determine a set of constraints on a CDF as follows.
Theorem 2. Let 96 fr P(S 2 r) 2 1- 8). where
(0, 1) and defined above. Let X1...., Xn aid F, where F is an arbitrary CDF and let X(1) S... < X(n)) be the corresponding
order statistics. Then P(yi (a) 2 s )ss)) 2 6, where Vs R. s (s) inf, s((u) 8) is the generalized inverse of s;-
We use the constraints given by Theorem 2 form a (1 (1- CDF-LCB via conservative completion of the CDF. An illustration of the process can be found in Figure 2
4.3 CONSERVATIVE CDF COMPLETION
Here show how constraints generated by Theorem to form lower bound on F via the so-called conservative completion of the CDF (Learned-Mie Miller & Thomas 2020). This defines the "lowest lower bound" of F given constraints.
5

---

Published as a conference paper at ICLR 2023
10
0.5
0.9
Xx.
Unu by
00
301
Mkg
Qup
dey
Oux
Man
0.5
loss
Figure 2: Example illustrating the construction of a distribution- free CDF lower bound by bound- ing order statistics. On the left, order statistics U(I)...., U(() are drawn from a uniform distri- bution. On the right, order statistics X X(I)....,XX', (n) are drawn from an arbitrary distribution (in this case gamma distribution). and the corresponding Berk-Jones CDF lower confidence bound is shown as G. Our distribution-free method gives bound b; each sorted order statistic such that the bound depends only on i, as illustrated in the plots for i = (shown in orange). On the left, 1000 realizations of U(I).... (())-..... (()) shown in blue. On the right, 1000 empirical CDFs (x) A 1 E 1(X; I æ} are shown in blue, and the true CDF F is shown in red.
Theorem 3. Let F be an arbitrary CDF satisfying F(x;)) 2 b, for all i E {l..... n), where x S S In and 0 < bi S...5 bn 1. Let us denote (Ii, T2, ,I,) and b (bi, b2, bn) and let x+ E R U do be an upper bound on X ~ F, i.e. F(x*) 1. Let (xx,)(()) be defined as 0 i < I1; b, if II < 2:41 {1,2,
1}: bn in II< xt; and 1 if if S x.
Then, F G(x.))-
Corollary 1. Let S be a test statistic defined as equation 2 and recall ss inf P(S 2 r) 1) Let XI...., Xn rid F. where F is an arbitrary CDF and let X()) S... S ((n) be the where
corresponding order statistics. Then with probability least F = G (1 (s)))
X(1m)) A (X.))...., (m)) and s 2 (51 (ss)
(ss)).
Thus we now have way to construct lower confidence bound on F given the order statis- ties of a finite sample from F that is defined by set of functions 51...., ,.....,,pp. 8g- In other words,
Fn & G ((x(m)))+ (s.)) is a (1 - 5)-CDF-LCB and can be used to select a predictor to minimize risk measure as in Section 4.4 We also refer to as the critical value and it can be computed efficiently by bisection using software packages, e.g. |Mocovvchh (022)), that compute the one-sided non-crossing probability.
Several standard tests of uniformity may viewed as instances of the minimum-type statistic defined in equation 2 For example, the one-sided Kolmogorov-Smirne (KS) statistic and the Berk- Jones statistic, which achieves greater tail sensitivity. later sections, we use the term Order Stats to refer to modified Berk-Jones statistic where only single order statistic is used. This method along with some classical ones (e.g. DKW inequality) can be adapted to handle a VaR interval combined with Bonferroni correction. Please see more detailed discussion in Appendix B
4.4 BOUNDING MULTIPLE PREDICTORS SIMULTANEOUSIA
We now suppose that we have a finite set of predictors 7. defined by set of functions applied to the output of a complex algorithm such as a deep neural network. Let ø be an arbitrary black box function and let f1..... fm be a set of functions, e.g. different thresholding operations. Then the set of predictors is H {t, o é.... tm o o). The loss r.v. for random predictor h E H. is denoted by X ph and the corresponding validation loss samples are X
Theorem 4. Suppose that F, is (1 8/(H CDF-LCB. Then P(vh H. Fh F1) 8.
Theorem Theorem44implies that we can simultaneously produce a lower confidence bound on each predictor's loss function with probability at least 6. given that F,, a (1 - -////)/CDF--LLC. From the set of predictors H. our framework selects hü with respect target weighting function vi(p)
h e arg min R.g. (F
(3)
hCH

---

Published as a conference paper at ICLR 2023
By Theorem P(R & (gx(Fx) 2 1 - 6, including v/ * vb This means that we are able to bound any quantile-based risk metric, even if it was not targeted during optimization.
Remark 1. One of our main contributions concerns novel poodness-offft statistics. We introduce Iwo forms of truncated Berk-Jones statistic that are useful for targeting specific ranges of quantiles. These are discussed in detail in Appendix
5 EXPERIMENTS
We perform experiments to investigate our Quantile Risk Control framework as well as our particular novel bounds. First, we test the value of the flexibility offered by QRC by studying the consequences of optimizing for a given target metric when selecting a predictor. This motivates the need for strong bounds rich set of QBRMs, and thus we next examine the strength of our novel truncated Berk-Jones method for bounding quantities like the VaR Interval and CVaR. Finally, we present experimental results across the complete canonical set of metrics (Mean, VaR, Interval, and CVaR) in order to understand the effects of applying the full Quantitative Risk Control framework.
Our comparisons are made using the point-wise methods: Learn Then Test-Hoeffding Bentkus (LttHB); RCPS with Waudby-Smite Saaih----- (Order Stats). We also compare goodness of fit-based methods: Kolmogorov-Smimoo (KS); Berk- Jones (BJ); and truncated Berk-Jones (One-sided BJ, Two-sided BJ); all as described in previous sections. Our experiments span a diverse selection of real-world datasets and tasks. First, we vestigate our framework in the context of common image tasks using state of the art computer vision models and the MS-COCO (Lin et al. 2014) and CIFAR-I00 (Krizhevsky) 2009) datasets. MS-COCO is multi-label object detection dataset, where the presence of 80 object classes detected and more than one class may be present in a single instance. CIFAR- is a single-label image recognition task, which we perform in the challenging zero-shot classification setting using CLIP (Radford et al. 202T). In addition, we conduct a natural language processing experiment us- ing the Go Emotions (Demszky al. (020) dataset and fine-tuned BERT model (Devlin et al.) 2018). where the goal is to recognize emotion in text and a single instance may have multiple la- bels. Finally, we evaluate the interaction between our method and subgroup fairness using the UCI Nursery dataset (Dua & Grafi, 2017), where applicants are ranked for admissions to school. While all methods are theoretically guaranteed, bounds on the true CDF or risk may be violated with some probability given by 5. We analyze how these violations occur in Appendix [F.6.4] Full details for all datasets, models, and experiments can be found in Appendix F. All experiments focus on producing prediction sets, as is typical in the distribution
Ramdas bound WRc))WSR); DKW; and Order Statistics
uncertainty quantification (DFUQ) setting (Vovk)
ctt al. 20055 Shafeer & Vovk 2008, Bates et al., 2021 Angelopoulos et al. 2021). and are run for 1000 random trials with ò= 0.05. Code for our experiments is publicly available"
5.1 VALUE OF OPTIMIZING FOR TARGET METRIC
A main feature of the QRC framework is the flexibility to target a range of metrics, including: Expected-value (Mean); 3-R (VaR); [3min -aRaa-VaR-Inneeee (VaR-Interval); and CVaR. The results presented here demonstrate the importance of that flexibility by showing that in order to produce the best bound on given risk measure, it is important optimize for that metric when selecting predictor.
Using the MS-COCO, CIFAR- 100, and Go Emotions classification tasks, we record the guaranteed Mean, VaR, VaR Interval, and CVaR given by the Berk-Jones bound when targeting each of these risk measures to choose a predictor. The bound is applied on top of pre-trained model that produces a per-class score, i.e. W- = Φ( Z),, where W E RRK and K is the number of classes. A prediction set is formed by selecting all classes with a score least some value Ý { W 2 t). Therefore a predictor is described by its corresponding threshold, and our algorithms choose the predictor that minimizes the target metric according to the bound produced by given method. See Appendix E..7 for more details on the predictor space. Performance is measured using balanced accuracy metric, which evenly combines sensitivity and specificity measures, where sensitivity encourages larger prediction set sizes and specificity encourages smaller set sizes (see Appendix E.2 for an exact description). Refer to Table for MS-COCO results and Appendix Table for CIFAR- 100 and Go
jakeseseell /qquaattnn1//qutniiiiia 1e- ak- control

---

Published as a conference paper at ICLR 2023
CLIP/CIFAR-100
Go Emotions
Lazz Guarantee
0.25
0.15
0.10
OrderStats
One-sided
Two-sided
OrderStats
One-sided
TWo two-sided
Figure 3: Results for bounding the quantities of the VaR for various methods. The average test loss over all trials is plotted in red.
Emotions results. Targeting given metric in predictor selection gives the tightest bounds on that metric in all experiments. This highlights the significance of our QRC framework, which produces bounds over predictors for a diverse set of targeted risk measures such as the VaR Interval or CVaR.
Dataset
Target
Mean
VaR
Interval
CVaR
MS-COCO VaR
Mean
0.088 + 0.003
0.203 0.014
0.211 0.011
0.472 + 0.017
0.101 = 0.006
0.179 # 0.010
0.191 0.011
0.460 = 0.017
Interval
0.100 # 0.007
0.181 0.011
0.189 0.011
0.458 0.017
CVaR
0.107 = 0.014
0.190 0.016
0.197 = 0.015
0.453 = 0.015
Table Results on MS-COCO illustrating trade-offss between targeting different metries in predictor selection and the guarantees that can be issued for each metric given by the selected bound. We use Berk-Jones bound, and bold results are best for a given metric.
5.2 TRUNCATED BERK-JONES VS. EXISTING METHODS
Next, compare the strength of our truncated Berk-Jones bounds for the VaR-Interver and CVaR to existing methods for bounding these quantities for hypothesis selection. As opposed to the previous experiment, here fix single threshold prior running the experiment, in order isolate the strength of the bounds from the randomness induced by multiple predictors. Results are shown in Figure 3 Appendix Figure [5] and Figure 4 with further explanation below. The truncated Berk- Jones method consistently gives the best bounds, especially on the CVaR.
Image and Text Classification. Our novel truncated Berk-Jones bounds can be used to control the loss for diverse range of tasks, datasets, and loss functions. Here we examine the strength of these bounds for bounding quantities of the VaR on multi-label image (MS-COCO) and text (Go Emotions) classification tasks, as well single-label zero-shot image classification (CIFAR-100), For MS-COCO object detection, Vat-Interval evaluated in [0.85, 0.95). and CVaR calculated with 3 = 0.9. For zero-shot classification CIFAR- 100 and emotion recognition in Go Emotions, the -aR-Interval is bounded in [0.6, 0.9]. Results are shown in Figure 3 and Appendix Figure 5 Across all tasks and datasets, the modified Berk-Jones bound consistently gives loss guarantee that lowest, and thus closest to the actual loss for this fixed predictor.
Fair Classification. Williamson & Menon (2019) proposed CVaR notion of fairness that be viewed as the worst-case mean loss for subgroups of a particular size. Thus we consider a fairness problem, and show how framework can be applied generate predictor that optimizes CVaR, or worst-case outcomes, individually with respect to each group according to some protected attribute. We employ the UCI Nursery dataset (Dua & Graff 2017). multi-class classification problem where categorical features about families are used to assign a predicted rank to an applicant
Y E {1...., 5) ranging from "not recommended" (Y 1) "special priority" (Y 5). We measure a class-dependent weighted accuracy loss. Our sensitive attribute is family's 's financial status. Applicants are separated based on this sensitive attribute, and we apply the methods to and evaluate each group ("convenient" and "inconvenient") separately. Exact specifications of the loss function, dataset, and other experiments details can be found in Appendix E.S Results for the fair classification experiment standing and Group have inconvenient. Applying the truncated Berk-Jones bound individually to each group leads to the best CVaR among all methods for both groups
reported in Figure 4 where Group 1 have convenient financial
8

---

Published as a conference paper at ICLR 2023
Group
Group 2
ClaR Guarante
0.4
0.3
0.2
0.2
OrderStats
One-sided B)
OrderStats
One-sided
Figure 4: Results for bounding the CVaR for each group in Nursery with , = 0.9.
5.3 MS-COCO EXPERIMENTS ALL RISK MEASURES
For our final experiment compare the performance of various bounding methods across the full canonical set metrics (Mean, VaR, Interval, and CVaR) when selecting a predictor. We perform this experiment using MS-COCO and balanced accuracy risk measure, and apply Bonferroni correction to according to the size of the predictor space.
Results bounding the CVaR and VaR Interval reported in Table 3 while all results are shown in Appendix Table Tables include the target metric used to choose a predictor, bounding method, guarantee returned on the validation set, and loss quantity observed on the test set. As expected, RepsWSRR gives the tightest bound on the Mean, while the point-wise Order Statistics method out- performs the GoF-based methods on bounding a single VaR metric. When bounding VaR-Interval or the CVaR, which is a focus of our work, the truncated Berk-Jones bounds achieves the lowest loss guarantee. In general, the best guarantees have best actual loss, although the difference can be small (or none) as all methods may choose the same or similar predictors around that which minimizes the target risk measure on the validation set.
Method
Guarantee
Actual
Method
Guarantee
Actual
DKW
1.0
0.500 = 0.000
DKW
0.744 0.005
0.146 0.012
OrderStats
0.454 0.015
0.208 + 0.011
OrderStats
0.189 0.011
0.138 0.007
CVaRR
KS
0.971 + 0.002
0.228 + 0.022
Interval
0.581 0.008
0.144 0.013
BJ
0,453 + 0.015
0,208 + 0.011
BJ
0.189 0.011
0.138 0.007
One-sided BJ
0,419 = 0.015
0.207 = 0.010
One-sided BJ
0.183 0.010
0.137 0.006
Two-sided BJ
0.182 0.010
0.137 0.006
Table 3: Results for experiments with MS-COCO Object Detection bounding CVaR and the VaR Interval. Best results are in bold.
DISCUSSION
Our experimental results (see Section 5land Appendix E..6 show that: (1) in order to achieve tight bound on a target risk measure, a predictor should be selected based on that risk measure; and (2) the truncated Berk-Jones bounds are more effective than previous methods for bounding the VaR- Interval and CVaR. While methods that focus on the mean or particular 3-R value can give a tighter bound when that target metric is known beforehand, key advantage of Quantile Risk Control comes from the flexibility to change the target metric post hoc, within some range, and still maintain a valid bound. Though there are some ways to convert between these classes (e.g.. Mean Quantile with Markov's Inequality: CVaR is directly our experiments. This makes QRC well-suited to scenarios which a stakeholder may want to issue guarantee several guarantees from single predictor, when an external auditor may change system reporting requirements. A natural extension this work is to consider returning multiple predictors with algorithm. In this case, while the target metric may not be known beforehand, we could produce multiple predictors that optimally bound specific points in the range, instead of a single predictor that gives the best bound average the range.
upper bound on VaR), these are weak shown by

---

Published as a conference paper at ICLR 2023
ETHICS STATEMENT
Some care needs to be taken ensure that the guarantees under our framework are clear, in that they do not apply to every individual in the test distribution and only hold if test examples are drawn from the same distribution as validation examples.
REPRODUCIBILITY STATEMENT
Our code is publicly available on Github. For all experiments, datasets and splits are specified, and we use publicly available pre-trained models for feature extraction when possible.
ACKNOWLEDGMENTS
The authors would like to thank Marc-Ftienne Brunet, Anastasios Angelopoulos, and anonymous reviewers for their useful comments. Resources used in preparing this research part, by the Province of Ontario, the Goverment of Canada through CIFAR, and companies spon- soring the Vector Institute (https: htt:///etoriisssiitcciess also supported by NSERC and Simons Foundation Collaborative Research Grant 733782.
provided, in
witpartners/ ). This project is
REFERENCES
Carlo Acerbi. Spectral measures risk: coherent representation of subjective risk aversion. July 2002.
Journal of Banking & Finance,
Theodore W. Anderson and Donald A. Darling. Asymptotic theory of certain "goodness of fit"
criteria based on stochastic processes. The Annals of Mathematical Statistics, pp. 193-212, 1952.
Anastasios N. Angelopoulos and Stephen Bates. A Gentle Introduction to Conformal Prediction and Distribution-Frie Uncertainty Quantification. arXiv:2107.07511 January 2022.
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. 1rXiv:2110.01052, November 2021.
Stephen Bates, Anastasios Angelopoulos, Lihua Lei, Jitendra Malik, and Michael Jordan. Distribution-free risk-controlling prediction sets. J. ACM, 68(6), sep 2021. ISSN 0004-5411. doi: 10.1145/3478535.
Robert H. Berk and Douglas H. Jones. Goodness-offfit test statistics that dominate the Kolmogorov statistics. Zeitschrift für Wahrscheinlicheeissheorii und Verwandte Gebiete, 47(1))47-59 1979.
Harald Cramér. On the composition of elementary errors: First paper: Mathematical deductions.
Scandinavian Actuarial Journal, 1928(1):13-74, January 1928.
Dorottya Demszky, Dana Movshovitz-Atiaa, Jeongwoo Ko, Alan Cowen, Gaurav Nemade, and Sujith Ravi. GoEmotions: A dataset of fine-grained emotions. In Proceedings of the 58th An- nual Meeting of the Association for Computational Linguistics, pp. 4040-4054, Association for Computational Linguistics, July 2020.
Jacob Devlin, Ming-Wes Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv.1810.04805, 2018.
Kevin Dowd. Using Order Statistics to Estimate Confidence Intervals for Quantile-Based Risk Measures. Journal of Derivatives, 17(3):9-14, 2010.
Kevin Dowd and David Blake. After VaR: The Theory, Estimation, and Insurance Applications of Quantile-Based Risk Measures. Journal of Risk & Insurance, 73(2):193-22,, June 2006.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://archive. /archie..
ics. uct edu/ml
10

---

Published as a conference paper at ICLR 2023
Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pp. 642-669, 1956.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report,, University of Toronto, Department of Computer Science, 2009.
Erik Learned-Miller and Philip S. Thomas. A New Confidence Interval for the Mean of a Bounded 90.006088, November 2020.
Random Variable.
Erich L. Lehmann and Joseph P. Romano. Testing Statistical Hypotheses. Springer Texts in Statis- tics. Springer New York, New York, NY, 2008. ISBN 978-1-4419-3178-5
Tsung-Yi Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zimicck. Microsoft COCO: Common Objects in Context. David Fleet, Tomas Pajdla, Bernt Schicle, and Tinne Tuytelaars (eds.). Computer Vision ECCV2014, volume 8693, pp. 740-755. Springer International Publishing. 2014.
P. Massart. The Tight Constant in the Khoeezzk-KKiefe--Woffovvi Inequality. The Annals of Prob- ability, 18(3): 1269 1283, 1990.
Frank J. Massey, Jr. The Kolmogorov-Smimmo test for goodness of fit. Journal of the American Statistical Association, 46(253):68-78 78, 1951.
Amit Moscovich. Fast calculation of p-values for one-sided Kolmogorov-Smirnov type statistics. arXiv:2009.04954 049944 2020.
Amit Moscovich, Boaz Nadler, and Clifford Spiegelman. On the exact Berk-Jones statistics and their p-value calculation. Electronic Journal of Statistics, 10(2):2329-2354, 2016.
Michael Naaman. On the tight constant in the multivariate Dioretaly-Kiede-Woffoiii incquality. Statistics Probability Letters, 173:109088, 2021.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8748-8763. PMLR, July 2021.
Tal Ridnik, Hussam Lawen, Asaf Noy, Emanuel Ben Baruch, Gilad Sharir, and Itamar Friedman. Tresnet: High performance gpu-dedicated architecture. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), pp. 4400-1409, January 2021.
R. Tyrrell Rockafellar and Stanislav Uryasev. Optimization of conditional value-at-risk. The Journal of Risk, 2(3):21-41, 2000.
Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(12)371-422, 2008
Galen Shorack. Probability for Statisticians. Springer Texts in Statistics. Springer-Verlag. New York, 2000. ISBN 978-0-387-98953-2.
Galen R. Shorack and Jon A. Wellner. Empirical Processes with Applications to Statistics. Society for Industrial and Applied Mathematics, January 2009. ISBN 978-0-89871-68449
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer Science & Business Media, 2005.
Q. Waymel, S. Badr, X. Demondion, A. Cotten, and T. Jacques. Impact of the rise of artificial intelligence in radiology: What do radiologists think? Diagnostic and Interventional Imaging, 10066):37-3366, June 2019.
11

---

Published as a conference paper at ICLR 2023
Robert Williamson and Aditya Menon. Fairness risk measures. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th Interationall Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6786-6797. PMLR, June 2019.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jemiie, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: State-of-the-an natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pp. 38-45. Association for Computational Lin- guistics, October 2020.
12

---

Published as a conference paper at ICLR 2023
A NOTATION
Symbol
Meaning
2
Input space.
Target output space,
Prediction space.
h
A predictor mapping from 2 to y
D
Data distribution over 2 x
(Z,Y)
Random variables representing input-target pairs drawn from D.
EY (Y
Loss incurred by predicting y E ) when the ground truth is Y E y. Random variable representing ((h(2), Y). This is the loss incurred by applying pre- dictor h input Z when the ground truth is Y. The superscript may be dropped when the predictor being referred to is clear from context.
Xh
ph
The cumulative distribution function (CDF) of X", also referred to as the loss CDF,
defined as F* (x) & P(X* <.).
F-15
Quantile function defined F-1 A inf(x: F*())= 2 p). Risk measure quantifying the risk associated with loss CDF F. Weighting function defining quantile-based risk measure (see Definition A sequence of loss random variables X1,..., X,-
R(F)
(())
The i-th order statistic of X Order statistics satisfy X(1) .... S (().
F Z G' denotes F(x) 2 G(x) for all x E R.
A lower confidence bound on Fh as function of x,...., X
F-1.A
The upper confidence bound F-1.h corresponding to Ft.
Table 4: Summary of the notation used in this paper.
B INTERPRETING STANDARD TESTS OF UNIFORMITY AS MINIMUM-TYPE STATISTICS S
Several standard tests of uniformity may be viewed as instances of the minimum-type statistic S de- fined in equation 2 For example, the one-sided Kolmogorov- Smiiroo (KS) statistic with the uniform as the null hypothesis can be expressed as D A maxigign
U(s)
minigisn UU/ 100-,, -.)
which can be viewed as D SS where su(u) = u n. The Berk-Jones statistic achieves greater tail sensitivity by taking advantage of the fact that the marginal distribution of U(a) is Beta(i, i + 1). which has lower variance in the tails. The one-sided Berk-Jones (BJ) statis- tic is defined as M & minigign (o (i, i 1), where [z,a, b) is the CDF of Beta(a, b) evaluated at æ. This be recognized as S where su(u) I,(i, n + 1), the inverse of which can be efficiently computed using standard software packages.
Standard distribution-fres one-sided confidence bounds for quantiles involve selecting the minimal order statistic that bounds the desired quantile level with high probability. We use the term Order Stats refer modified Berk-Jones statistic where only a single order statistic is used. An analogous approach can be taken using the DKW incquality (see Appendix [E.] for details). These methods can be adapted to handle a VaR interval by simultaneously bounding multiple quantile levels, e.g. using grid over the interval [8min, }max], via Bonferroni correction.
C NOVEL TRUNCATED BERK-JONES STATISTICS
One of our main contributions concerns novel goodness-of-fh statistics. Here we introduce two forms of a truncated Berk-Jones statistic, targeting range of quantiles. The first form targets a one-sided range of quantiles [Amin: 1). The key idea is to drop lower order statistics that do not affect the bound F-1 (33in). We define the truncated one-sided Berk-Jones M 2
mingsssu TU (i, n + 1), which can be realized by using (1) = Tu(i, i+ 1) for k < i
13

---

Published as a conference paper at ICLR 2023
and st( 1 otherwise. For given Smins define k2 (Amia) - minfk 6k (sx) 2 Pmin): where 5g is the critical value of - Bisection search be used compute k- and thus the in- version of M MM (Bmm)) provides a CDF lower bound targeted at quantiles Bmin and above. The truncated two-sided Berk-Jones variant targets quantile interval [Smin 3max] and is defined as M & minagige (0)) (i, - 1). It first computes k" (Bmia) as in the one-sided case and then removes higher order statistics using the upper endpoint of & minfe st (58 where k is the corresponding critical value.
k= x) 2 9max),
8
D PROOFS
D.1 PROOF OF THEOREM 1
Proof. Consider (p). By the definition of the quantile function, G(G-1 p. By the relationship between F and G. we therefore have (p) 2 G(G 2 P. where the first inequality follows from F G. Applying F-1 both sides vields F (FIG (p))) 2 F (p). But 2 F-11FFF (x)) (see e.g. Proposition on p. 6 offShrack & Wellner (2009)) and thus G (p) (p). Then we have Ryp (P) < Ry(G by Definition |
The event that F > C(X1.,) 1.m) implies so
that (F) I (G) by Theorem Since the antecedent holds with probability at least must the consequent.
D.2 PROOF OF THEOREM 2
Proof. For readability, we first discuss the case when the CDF F is continuous and strictly increas- ing. After that, we demonstrate how to extend our argument more general case.
Continuous and strictly increasing F. If F is continuous and strictly increasing, we know F is bijective and the inverse function J. (p) is well-defined. Moreover, for X F, we have F(X) is of the same distribution as uniform random variable U. That is because
P(F(X) p) = P(X < F-)
In addition, by the monotonicity of F, F preserves ordering, which means ((X()) is of the same distribution Utg for all [n]. So, we have
P ( ((X()) 2 st (s6)) P (Vi, U1A 2 85 (
Now recall that
s min (((())) 1si5n
Given the definition of ss. we know that
P(S 88) 2 1
In addition, by the definition s7 ... 2 $6, then we have that U1o 2 8, (88) for all E (1....,n). Combined together, have
P (Vi, F(X() 2 ., (86)) P (vi, U 2 2 (s6)) 2 P 88) 2 d.
General F. For general F, recall we define a generalized inverse function F F-1(p) A inf
F(x) 2 p}. Notice that for a generalized inverse function F-1, we have F FU) is of the same distribution as X That is because
P(F-1(U) 5c) (c) P(U < F(c)) F(c).
We want to remark that the above formula holds for general F' and the first equality directly follows from the definition of the generalized inverse function F-1, Moreover, F-1 preserves ordering (by definition of the quantile function), iee. F-1 (U()) I ... < F- (U(n)) Thus, we have X(1) is of the same distribution (U)(
F
14

---

Published as a conference paper at ICLR 2023
By Proposition 1, eq. 24 p.5 of Shorack & Wellner (2009), we have that
Fo F- (1)
for any / E [0, 1] and any CDF F (this can obtained directly from the definition of F-1 also can go beyond CDF, but we here only restrict ourselves in the case that F is a CDF). Therefore we have
(UF))( UW 8 (58)-
Combined with the fact that (()) is of the same distribution as F F (U())) for all i E [m], we have
P (Vi, F(X()) 2 o, (ss) P (vi, F(F (U)) 2 (ss))
P (vi, U(a 2 s, s (ss)) 2 PSS 2 ss)
2 1 - 5.
D.3. PROOF OF THEOREM 3
Proof. When x. < 21, F(x) 2 0. For any i E (1,2,... ,n,,, since F(x;) 2 b; thus, for x E (xn, (i+1), F(x) 2 F(x:) d; (#n-1 is considered as at here). Lastly, if x x+ F(x) 1.
Combined together, we have F(x) 2 (z).)
D.4 PROOF OF COROLLARY
Proof. Notice that by Theorem which implies
if F(X)) 2 s; (ss), then we have F(x) G (1
P(F(s) G (ea)) 2 P( P(vii 2 8, 2
Then, by Theorem 2 P F(X()) 2 of ( 2 1- - 6.
D.5 PROOF OF THEOREM 4
Proof. The claim follows by applying a union bound argument over h H:
P(3h E H F* & c(x+t)) = P(Fh a C(xt..))) s
hEW
E EXPERIMENTAL DETAILS
E. DKW METHOD FOR QUANTILE DISTRIBUTION-FREE UPPER CONFIDENCE BOUNDS
distribution upper confidence bound on F F can be constructed by using a one-sided version
of the DKW inequality (Dvoretzky et al. 1956 Massart
1990). Define the empirical distribution
function as (x)
1 ET IfX; < r]. Then for every E 2 2n log 2, by the DKW inequality,
e)
P sup (x) - F(x)) 2 s FER
we let = exp(-22 22n ?), then we have E = v 2n log 1 and the above condition holds for any 8 < 1/2.
Proposition 1. Let X(1) .... S X(n) denote the order statistics of Xi...., X where X; F for all i nI. Let k n (3+ 2n log 1 Then for v 2n log $ and 1/2.
P(F-1(B) s x(w) - 8.
15

---

Published as a conference paper at ICLR 2023
Proof. Observe that (X) for i fl.....n). Thus for & defined above, we have
(x) +
V
2n
log
8
But with probability at least 1 - 8, we have
F(r) 2 FT(
log
2n
for all x E R. Thus ((F(X())) 2 8) 2 1 1 + P(F (3) S X(a) 2 1 11-66 8, where the latter
follows from the property that F-1 o F(r) S x (see e.g. Proposition 3 on p. 6 of Shorack & Wellner 2009
E.2 DEFINITIONS OF LOss FUNCTIONS
Balanced accuracy is computed as follows, where Y is the prediction set, is the set ground truth labels (which in this case will always be single label), and K is the number of classes:
L( = (Sens(Y, Y) + Spec(Y, Y)), where
2
Sens(Ý, (ons),Y)...)) 1 Y |Y|
and Spec(Ý,Y)) Y) K |Y| I \ Y
K Y
E.3 MS-COCO EXPERIMENT DETAILS
MS-COCO (Lin et al. 2014) is a large object detection dataset with 80 different categories where an image may contain or classes of objects and thus may have one more ground truth labels. Class scores are extracted using TResNet (Ridnik et al. (02T). Results are averaged over 1,000 trials, where in each trial 2,000 datapoints are randomly split into 500 validation and 1,500 test points. VaR is targeted with 3 = 0.9, while the Interval and CVaR target the ranges [0.85, 0.95] and [0.9, 1.0), respectively. KS and BJ bound the Mean by targeting the loss for the entire range [0.0, 1.0]. Point-wise methods (DKW, OrderStats) are used to bound intervals by calculating VaR upper bounds over a grid of values within the range of interest using a Bonferroni correction for the grid size. The grid size is 10 for the VaR Interval, and 50 for CVaR.
E.4 CIFAR- AND Go EMOTIONS EXPERIMENT DETAILS
We use multi-monn CLIP Radford al. 202 embedding model in order to perform zero-shot image classification on the CIFAR- 100 dataset using the method described Radford et al. (2021). CIFAR- 100 features images of 100 different classes, and the test split. Our feature extractor is the VIT-B/32 version of CLIP available on Hugging Face (Wolf al. 2020).
the 10,000 examples available in
Go Emotions Demszky et al. 2020) is dataset of comments from Reddit where binary labels are given for 28 different fine-grained emotion categories and each comment may have one or more positive labels. 5,427 examples are drawn from the test set, and our base classifier is bert-base- uncased model fine-tuned on the train split, again available on Hugging Face (Wolf al. 2020).
Experiments are run for 1,000 trials with 500 validation examples randomly selected and the rest of the dataset used for testing. Balanced accuracy loss bounded in the VaR-Interval [0.6, 0.9 in both cases. For zero-shot CLIP, point-wise methods are run over a grid of 50 / values, and for Go Emotions the grid size is also 50.
E.5 FAIRNESS EXPERIMENT
We measure a class-varying weighted accuracy loss:
I(Ý, (1 (1 Spec(Ý, Y)) uy Sens(Ý,Y)
16

---

Published as a conference paper at ICLR 2023
COCO (Interval)
COCO (CVaR)
Los Guarante
0.200
CVoR. Guarantee
0.175
0.3
0.150
0.125
OrderStats
One-sided [)
Two-sided Bj
Figure 5: Results for bounding the quantities of the VaR for various methods. The average test loss over all trials is plotted in red.
where R$ is vector of class weights representing the importance of sensitivity for each test item's class label. This allows for user flexibilityy, where for instance school could prefer to be more sensitive towards detecting good students. To demonstrate this, we perform our experiments with μ = (0.5, 0.6, 0.7, 0.9.
We use 8,683 samples from the UCI Nursery train split, including examples from both groups, to train a logistic regression classifier to predict prospective student's admission ranking. our bounding experiments, 4,000 samples from the original test split are used for validation and testing, split evenly between the groups, with 500 examples from each group taken randomly for validation each trial. Point-wise methods with those examples with the highest loss, we focus on bounding the CVaR in the range [0.9, 1.0).
with beta grid size of 50. Since fairness is often concerned
E.6 ADDITIONAL RESULTS
E.6.1
VALUE OF OPTIMIZING FOR TARGET METRIC
Results for additional experiments highlighting the value of optimizing for a given target metric
shown in Table
Dataset
Target
Mean
VaR
Interval
CVaR
CIFAR-100
Mean
0.156 + 0.007
0.507 + 0,009
0.507 + 0.016
0.664 0.009
VaR
0.202 = 0.024
0.411 # 0.028
0.433 0.020
0.651 0.015
Interval
0.200 = 0.022
0.418 # 0.031
0,429 0.020
0.647 + 0.017
CVaR
0.353 = 0.126
0.466 + 0.038
0.468
0.627 0.007
Go Emotions
Mean
0.147 = 0.007
0,503 + 0.091
0.700 +.057
VaR
0,178 = 0.016
0.230 # 0.023
0.312 0.029
0.627 0,030
Interval
0.195 + 0.021
0.257 + 0.027
0.289 - 0.026
0.589 + 0.027
CVaR
0.241 + 0.044
0.314 + 0.050
0.323 0.045
0.570 0.026
Table 5: CIFAR-100 and Go Emotions results illustrating trade-offs between targeting target differ- ent metrics in predictor selection and the guarantees that can be issued for each metric given by the selected bound. We use the Berk-Jones bound, and bold results are best for given metric.
E.6.2 TRUNCATED BERK-JONES vs. EXISTING METHODS
Results for bounding a single predictor on MS-COCO are shown in Figure
E.6.3
MS-COCO EXPERIMENTS ON ALL RISK MEASURES
All results for MS-COCO experiments comparing the performance of various bounding methods across the full canonical set of metrics (Mean, VaR, Interval, and CVaR) are reported in Table
E.6.4 VIOLATIONS OF Loss GUARANTEES AND LOWER CONFIDENCE BOUNDS
Tables and g show violations of both the loss guarantee and the CDF lower confidence bound returned by each method for subset of the MS-COCO experiments in Section 5.3 and the CIFAR-
17

---

Published as a conference paper at ICLR 2023
Method
Guarantee
Actual
Method
Guarantce
Actual
LtdH
0.097 0.004
0.048 0.001
DKW
0.744 = 0.005
0.146
RepsWSR
0.055 0.003
0.048 0.001
OrderStats
0.189 0.011
0.138000007
Mean
KS
0.142 0.003
0.048 + 0.001
Interval
KS
0,381 = 0.008
0.144
BJ
0.088 + 0.003
0.048 + 0.001
BJ
0,189
0.138 = 0.007
0.007
One-sided BJ
0.183 0.010
0.137 = 0,006
Two-sided BJ
0.182
0.137 0.006
LttHB
0.968 0.036
DKW
1.0
0.500 0.000
DKW
0.287 0.023
0.150
OrderStats
0.454
0.208 = 0.011
VaR
OrderStats
0.166 + 0.010
0.132 # 0.004
CVaRR
KS
0,971 0.002
0.228 = 0.022
KS
0.287 + 0.023
0,150 0.020
BJ
0.453 = 0.015
0.208 = 0.011
BJ
0.179 0.010 0.010
0.134 # 0.006
One-sided BJ
0,419 = 0.015
0.207 = 0.010
Table 6: Results for experiments with MS-COCO Object Detection and canonical metrics. Best results in bold, except for actual mean where all methods produced the same loss.
100 and Go Emotions experiments in Section 5.2 space of predictors, while that in Table 8 uses single fixed predictor.
The experiment in Table involves bounding
We can make few observations from these results. First, specific loss measures violated less frequently than CDF lower confidence bounds. A CDF violation occurs whenever the true CDF lies below the CDF-LCB at any point. But many risk measures average over range of quantiles, or only focus on certain quantiles. In that case, it is possible for the CDF bound to be violated but not the risk measure guarantee. Next, specific loss distributions may be better behaved in practice than the theory accounts for. We deal with distribution methods, meaning that they hold for any possible loss distribution with only minimal assumptions (e.g. the loss is bounded). If certain properties of the loss distribution were known (for example, it belongs to Beta distribution with unknown parameters), then we could in theory take this into account to produce tighter bounds. Since ours are distribution-free there should be some distribution for which our bounds tight, but it may not be the particular loss distribution we encounter. A similar phenomenon occurs with e.g. Hoeffding's inequality, where the bound is only tight when the probability mass is concentrated on the endpoints. Finally, bounding multiple predictors simultaneously affects the bounds, as shown by the difference in violation levels between Tables 7 and 8 Applying the union bound multiple predictors assumes that they are independent. But in practice the predictors may be highly correlated, meaning that the ordinary Bonferroni correction is overly conservative.
Metric
Method
Loss Viol.
LCB Viol.
VaR Interval
DKW
0.000
0.000
OrderStats
0.001
0.004
KS
0.000
0.000
BJ
0.001
0.002
One-sided-BI
0.001
0,007
Two-sided-BB
0.001
0.006
CVaR
DKW
0.000
0,000
OrderStats
0.000
0,002
KS
0.000
0.000
BJ
0.000
0.003
One-sided-By
0.000
0.005
Table 7: Violations of loss guarantees and lower confidence bounds for MS-COCO dataset when using bounding methods to select a predictor with ó = 0.05.
E.7
PREDICTOR SPACE
For each experiment trial and random data split, we test a finite sample of 500 linearly spaced thresh- olds (or predictors) the validation set. For computational efficiency, upper and lower bounds
18

---

Published as a conference paper at ICLR 2023
Dataset
Method
Loss Viol.
LCB Viol.
CIFAR-100
DKW
0.000
0.000
OrderStats
0.000
0.004
KS
0.000
0.031
BJ
0.000
0.020
One-sided-Bl
0,000
0,026
Two-sided-Be
0.002
0.041
Go Emotions
DKW
0.000
0.001
OrderStats
0.000
0.007
KS
0.000
0.028
BJ
0.000
0.021
One-sided-Bi
0.003
0.041
Two-sided-BJ
0.005
0.043
Table 8: Violations of loss guarantees and lower confidence bounds for CIFAR-100 and Go Emo- tions datasets when using fixed predictor with ò 0.05.
set the maximum and minimum values of the scores over the entire dataset, although this could easily be replaced by the maximum and minimum value the scores on the validation set alone. Results are measured on the test data using the predictor with the best guarantee for particular target metric.
19


Reviews:
[{"review_id": "v5xwFoBPWf0", "reviewer": "Reviewer_Zm2X", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces a framework for measuring and optimizing for quantile-based risk functions, which go beyond the standard practice of measuring and optimizing for the average (expected) loss function. The framework allows one to optimize for any quantity expressed as an integral over the quantile function of the loss; common examples include Value-at-Risk (VaR), Conditional Value-at-Risk (CVaR), and VaR-Interval. These quantile-based risk functions tend to be used to measure something closer to the worst-case loss, rather than the average loss. This is useful when planning to guard against tail risk in a setting where an ML model is deployed.\n\nThe paper introduces a novel way to define a lower confidence bound (LCB) on the loss function's cumulative distribution function (CDF), which equivalently produces an upper confidence bound on the loss function's quantile function (the quantile function is the inverse CDF), which produces an upper confidence bound on any quantile-based risk function.", "summary_of_the_review": "Overall, I like this area of study, and I find the proposed technique to be interesting and potentially useful. I like that the technique can be used on any set of pre-trained, black-box models, and that it can be used to select the model that optimizes a given quantile-based functions of a loss. However, that the bounds that are produced seem quite loose in some cases, which makes me question whether practitioners would actually trust that the method is giving useful (tight) bounds.", "strength_and_weaknesses": "Strength:\n* The technique is widely applicable for any quantile-based risk function and any set of black-box ML models that produce prediction functions.\n\nWeaknesses:\n* The 95% confidence bound on the CDF displayed in Figure 2 looks very conservative, given 1000 samples. I wonder whether there are alternate methods to produce tighter bounds on the CDF.\n* Some of the bounds in the empirical section appear to be quite loose, with a 1.5 to 2x gap between the bound and the actual metric (e.g., Mean and CVaR in Table 2, and both results in Table 3). Whether this has practical implications would depend on whether the technique is being used to produce tight bounds on the metrics, or only to select the best model among several candidates.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "D5yO42Ilhrw", "reviewer": "Reviewer_yK7n", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new framework for obtaining bounds on quantiles of the loss distribution of a given predictor. The method uses a lower bound on the CDF to obtain high-confidence bounds on the quantile loss profiles of the predictor. ", "summary_of_the_review": "The proposed framework for quantile loss uncertainty estimation is quite nice, but the paper needs to be updated to showcase the empirical utility of this framework.", "strength_and_weaknesses": "Strength\nThe framework produced by the paper generalizes exisitng known frameworks for quantifying uncertainty in classifier predictions. The paper is quite well written and easy to follow, and the arguments are supported by both theoretical and empirical results.  \n\nWeakness\nWhile the paper doe sa good job of laying the foundations of the framework, it does not stand out on from either the theoretical or the empirical perspective.\n- From a theoretical standpoint, most of the theoreems (1, 2, 3) are simple extensions of known results on CDFs and concentration inequalities. There is no discussion on what the challenges were in proving these results, and while they are essential to establish the framework, they do not provide new novel insights. \n- From the empirical side of things, this framework can be quite impactful. Currently, the paper focusses on results for COCO object detection and UCI datasets. There is very little difference in the actual performance when using any of the methods in the literature (Table 2, 3) - why is this the case? \n- Quantile losses are typically used when data is very noisy (say finance time series) or when there are robustness issues to be dealt with. It looks like some of the methods might be more useful in those scenarios and trying out the proposed methods for such applications would strengthen the paper. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8riCE_qtbrK", "reviewer": "Reviewer_Vv5L", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a method to characterize, at validation time, the extreme deviation of a predictor and possibility using this characterization to select among a subset of these predictors, e.g., by adjusting a threshold. The deviation is measured through notions such as value-at-risk, i.e., the value of a given high quantile. The method consists of lower bounding the CDF of the risk with high probability. Experiments are given to illustrate the use of the technique.", "summary_of_the_review": "The paper bridges many interesting ideas, even if not majorly novel. The significance of the results is a bit weak, as some straightforward approaches can compete with it. That said, the paper is an insightful contribution to the efforts of characterizing and mitigating risks of predictors in machine learning, and may be worthwhile to share with the community.", "strength_and_weaknesses": "### Strengths\n\n* Characterizing the performance of a predictor in the extremes, in addition to in average, can help mitigate risks. This is particularly important for life-threatening or society-disturbing applications of machine learning. This paper addresses this directly by formulating it as a characterization and control of the quantiles of the risk.\n\n* The general methodology provided to derive CDF bounds based on goodness-of-fit statistics provides many useful insight. In particular, the benefits of finer bounds deeper in the tail are evident, especially for integral-type quantile metrics where inaccuracies accumulate. In general, the paper opens up opportunities to bring more ideas from statistics into machine learning.\n\n * The paper is organized and written very well.\n\n### Weaknesses\n\n* The use of quantiles to control the risk of predictors is not in itself new, as it is shared by many uncertainty quantification techniques. Order statistics always naturally show up in this context. The technical contributions are also quite straightforward, since connections between CDFs and quantiles through inversion is standard. However, this is counterbalanced by the clarity of combining the many ideas, and the emphasis on some of the new insights, like the use of the truncated Berk-Jones statistics to get finer bounds in the tail.\n\n* The significance of the contributions is a bit debatable. It is not clear how much better the novel aspects of this methodology help. For example, my first insight when I started reading the paper was to just use the empirical process lower bounds, i.e., the Dvortesky-Kiefer-Wolfowitz-Massart inequality, by capping it left and right. It tourns out the paper considers this as one of the baselines, and it does perform mostly equivalently to the best proposed approach. I think examples where the new contributions show more striking gains (which I believe exist, since these should do much better in the tail) can help bring out more of the significance of this work. For instance, it is worth elaborating more on when integral metrics like CVaR are most appropriate, since this is where the new stuff shines.\n\n* Generally, it feels that too much of the core contributions currently resides in the appendix. This may be okay for proofs, but when it comes to experimental results, they should be in the main text (namely I’m talking about the fairness experiments results.)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3wCT0jATIHd", "reviewer": "Reviewer_xSdZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes a method to bound a notion of risk that is measured in terms of quantiles, called \"quantile-based risk measures (QBRM)\". For a given predictor, a distribution over loss values is induced, and this paper shows that a lower bound of the CDF of this distribution serves as an upper bound of any QBRM of this predictor. They further show that it's possible to uniformly lower bound the CDF of the loss distribution for a set of predictors, which further serves as an upper bound to any QBRM for all predictors, especially the optimized predictor. The CDF bound can be derived via various minimum-type test statistics. Empirical results compare the tightness of the bounds produced by a suite of test statistics, various QBRM's, and demonstrate the guarantees are generally met.", "summary_of_the_review": "While I think this paper addresses an interesting and relevant problem and proposes a sound method, it's also a little difficult to tell the significance of the empirical results. I am looking forward to the author's response.", "strength_and_weaknesses": "The paper is coherent, well-written and addresses an interesting and seemingly novel problem of bounding quantile-based measures of risk (as opposed to the usual definition of risk, which takes the expectation). The arguments made in developing the proposed method seems sound. \n\nRegarding the empirical results, however, I'm not sure if it tells a convincing case for the usefulness of the bounds.\nFirst off, there's not much of a comparison to be done here, since the proposed method of bounding QBRM's is applied with all methods (i.e. test statistics), and they all seem to have close to 0 violation of their guarantees. The newly proposed Truncated-BJ statistic does tend to produce tighter bounds. What was the alpha value used? Is 0% violation actually expected, or are all of the bounds too loose? Also, it's also difficult to tell how significant the difference is between the upper bound and the actual values for each metric. Can you scan different values of alpha? Lastly, if using a specific test statistic and applying the proposed QBRM bound leads to a bound that is way too loose, would it be considered a fault of the test statistic or the bounding method? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster