Distribution-Free Statistical Dispersion Control for Societal Applications
Authors: Zhun Deng
Thomas P Zollo
Jake Snell
Toniann Pitassi
Richard Zemel
Venue: NeurIPS 2023 spotlight (2023)
Keywords: societal dispersion
distribution-free uncertainty quantification

Abstract: Explicit finite-sample statistical guarantees on model performance are an important ingredient in responsible machine learning.  Previous work has focused mainly on bounding either the expected loss of a predictor or the probability that an individual prediction will incur a loss value in a specified range.  However, for many high-stakes applications it is crucial to understand and control the \textit{dispersion} of a loss distribution, or the extent to which different members of a population experience unequal effects of algorithmic decisions. We initiate the study of distribution-free control of statistical dispersion measures with societal implications and propose a simple yet flexible framework that allows us to handle a much richer class of statistical functionals beyond previous work. Our methods are verified through experiments in toxic comment detection, medical imaging, and film recommendation.

Distribution-Free Statistical Dispersion Control for Societal Applications
Zhun Deng zhun. ddcold@mmbloooo aoccolmbia.... edu Columbia University
Thomas Zollo tpz21058columbia. edu Columbia University
Jake C. Snell
js2523@princeton edu Princeton University
Toniann Pitassi toni cs.columbia.cuu
Richard Zemel
zemel columbia edu
Columbia University
Columbia University
Abstract
Explicit finite-sample statistical guarantees model performance are important ingredient in responsible machine learning. Previous work has focused mainly on bounding either the expected loss of a predictor or the probability that an individual prediction will incur a loss value in specified range. However, for many high-stakes applications it crucial to understand and control the dispersion of loss distribution, or the extent to which different members of a population experience unequal effects of algorithmic decisions. We initiate the study of distribution-free control of statistical dispersion measures with societal implications and propose a simple yet flexible framework that allows us to handle a much richer class of statistical functionals beyond previous work. Our methods are verified through experiments in toxic comment detection, medical imaging, and film recommendation.
Introduction
Learning-basee predictive algorithms are widely used in real-world systems and have significantly impacted our daily lives. However, many algorithms are deployed without sufficient testing or thorough understanding of likely failure modes. This is especially worrisome in high-stakes application areas such as healthcare, finance, and autonomous transportation. In order to address this critical challenge and provide tools for rigorous system evaluation prior deployment, there has been a rise in techniques offering explicit and finite-sample statistical guarantees that hold for any unknown data distribution and black-box algorithm, paradigm known iistribution-frre uncertainty quantification (DFUQ). M. a framework is proposed for selecting model based on bounds expected loss produced using validation data. Subsequent work (30] goes beyond expected loss to provide distribution- free control for a class of risk measures known as quantile- based risk measures (QBRMs) [8] This includes (in addition to expected loss): median, value-at-rist (VaR), and conditional value-at-risk (CVaR) 23 For example, such a framework can be used to get bounds on the 80th percentile loss the average loss of the 10% worst cases.
While this is important progress towards the sort of robust system verification necessary to ensure the responsible use of machine learning algorithms, in some scenarios measuring the expected loss value-at-risk not enough. As models are increasingly deployed in areas with long-lasting societal consequences, should also be concerned with the dispersion of error across the population, or the extent to which different members a population experience unequal effects decisions made based model's 's prediction. For example, system for promoting content social platform may offer less appropriate recommendations for the long tail of niche users in service of small set
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

of users with high and typical engagement, shown in [1)] This may be undesirable from both business and societal point of view, and thus it is crucial rigorously validate such properties in an algorithm prior to deployment and understand how the outcomes disperse. To this end, we offer novel study providing rigorous distribution-feet guarantees for broad class of functionals including key measures of statistical dispersion in society. We consider both differences in performance that arise between different demographic groups as well as disparities that can be identified even if one does not have reliable demographic data or chooses not to collect them due to privacy or security concerns. Well-studied risk measures that fit into our framework include the Gini coefficient [3 and other functions of the Lorenz curve as well as differences in group measures such as the median [5]. See Figure 4 for a further illustration of loss dispersion.
Loss CDF
Lorenz Curves
Group Differences
f12
Group
LOsS Share
0.6
Croup
Line of Equamty
0.
000 0.2
0.4 0.
0.0
1.0
0.
0.4
0.6
0.8
1.0
h1
L,055
Figure 1: Example illustrating how two predictors (here h1 and h2) with the same expected loss can induce very different loss dispersion across the population. Left: The loss CDF produced by each predictor is bounded from below and above. Middle: The Lorenz curve is popular graphical representation of inequality in some quantity across population, in our case expressing the cumulative share of the loss experienced by the best-off / proportion of the population. CDF upper and lower bounds can be used to bound the Lorenz curve (and thus Gini coefficient, a function of the shape of the Lorenz curve). Under /2 the worst-off population members experience most of the loss. Right: Predictors with the same expected loss may induce different median loss for (possibly protected) subgroups in the data, and thus we may wish to bound these differences.
In order to provide rigorous guarantees for socially important measures that go beyond expected loss or other QBRMs, we provide two-sided bounds for quantiles and nonlinear functionals of quantiles. Our framework is simple yet flexible and widely applicable to rich class of nonlinear functionals of quantiles, including Gini coefficient, Atkinson index, and group-hasee measures of inequality, among many others. Beyond our method for controlling this richer class of functionals, we propose a novel numerical optimization method that significantly tightens the bounds when data is scarce, extending earlier techniques (1 30), We conduct experiments on toxic comment moderation, detecting genetic mutations in cell images, and online content recommendation, to study the impact of our approach to model selection and tailored bounds.
To summarize our contributions, we: (1) initiate the study of distribution-free control of societal dispersion measures; (2) generalize the framework of [30] to provide bounds for nonlinear functionals of quantiles; (3) develop novel optimization method that substantially tightens the bounds when data scarce; (4) apply our framework to high-impact NLP, medical, and recommendation applications.
Problem setup
We consider black-box model that produces an output Ž on every example. Our algorithm selects predictor h, which maps an input Z E Z to prediction h(Z) E ÿ. A loss function é 5 x y + IR quantifies the quality of prediction Ý ) with respect to the target output y Y. Let (Z be drawn from an unknown joint distribution P over Z x V. We define the random variable x : ((h(Z), Y) as the loss induced by f on P. The cumulative distribution function (CDF) of the random variable X is F*(x)= := P(X < x). For brevity, we sometimes use X and F when we do not need to explicitly consider h. We define the inverse of CDF (also called inverse CDF) F as F-(p) inf F(x) 2 p} for any p E R. Finally, we assume access to set of validation samples (Z, Y) = ((Z), .... (Z,, Yn)) for the purpose of achieving distribution-fre CDF control with mild assumptions the loss samples X1m. We emphasize that the "distribution-free

---

requirement is on (Z, 1).,, instead of X1:s because the loss studied on the validation dataset is known to us and we can take advantage properties of the loss such as boundedness.
3 Statistical dispersion measures for societal applications
In this section, we motivate our method by studying some widely-used measures of societal statistical dispersion. There are key gaps between the existing techniques for bounding QBRMs and those needed to bound many important measures of statistical dispersion. We first define a QBRM:
Definition 1 (Quantile-based Risk Measure). Let (p)) be a weighting function such that (p)) 2 0 and So (p) dp 1. The countile-basee risk measure defined by up is
(F) = [: of
A QBRM is linear functional of FT, but quantifying many common group-based risk dispersion measures (e.g. Atkinson index) also involves forms like nonlinear functions of the (inverse) CDF nonlinear functionals of the (inverse) CDF, and some (like maximum group differences) further involve nonlinear functions of functionals of the loss CDF. Thus a much richer framework for achieving bounds is needed here.
For clarity, we use the context, and summarize the building blocks below: (i) nonlinear functions of J, i.e. E(J); (ii) functionals in the form of integral of nonlinear functions of J. i.e. I (p))(((()))
generic term denote either the CDF F or its inverse F depending on
for a weight function sb; (iii) composed functionals as nonlinear functions of functionals for the functional 7 (J) with forms in (ii), i.c. <(T (J)) for a non-linear function Ç.
3.1 Standard measures of dispersion
We start by introducing some classic non non-group- grooppbbase measures of dispersion. Those measures usually quantify wealth consumption inequality within social group (or population) instead of quantifying differences among groups. Note that for all of these measures we only consider
non-negative losses X, and assume that Jo F F-(p)dp
Gini family of measures. Gini coefficient
33 34 is canonical measure of statistical dispersion,
used for quantifying the uneven distribution of resources or losses. It summarizes the Lorenz curve introduced in Figure From the definition Lorenz curve, the greater its curvature is, the greater inequality there exists, the Gini coefficient is measuring the ratio of the area that lies between the line of equality (the 45 line) and the Lorenz curve the total area under the line of equality.
Definition (Gini coefficient). For a non-negative random variable X. the Gini coefficient is 12 (2p - 1)F (p)dp
- -
G(X)
2EX
So F-(p)dp
where X' is an independent copy of X. G(X) E [0, 1). with O indicating perfect equality.
Because of the existence of the denominator in the Gini coefficient calculation, unlike in QBRM we need both an upper and lower bound for F- (see Section 4.1.1.. In the appendix, we also introduce the extended Gini family.
A Atkinson index. The Atkinson index 2 [9 is another renowned dispersion measure defined on the non-negative random variable X (e.g., income, loss), and improves over the Gini coefficient in that is useful in determining which end of the distribution contributes most the observed inequality by choosing an appropriate mequality-aversiin becomes more sensitive to changes the lower end of the income distribution
parameter 2 O. For instance, the Atkinson index increases.
Definition (Atkinson index). For nen-tegative random variable X, for any e 2 0, the Atkinson index is defined as the following if & + 1:
[E
(F-- fo F-(ddd
A(E,X) :=11-
1
[[X]
'This assumption is included for concise description, but not necessary. We also 0/0 0.
3

---

for = 1, X) := A(c, which will converge to form involving the geometric mean of X. A(E,X) E [0, 11, and indicates perfect equality (see appendix for details).
The form of Atkinson index includes nonlinear function of F i.e. (F-)=-e, but this type of nonlinearity is easy to tackle since the function is monotonic w.r.t. the range F (see Scction(4.2.1)
Remark 1. The reason we study the CDF of and not X1-$ that it allows us to simultaneously control the Atkinson index for all e's.
In addition, there are many other important measures of dispersion involving more complicated types of nonlinearity such as the quantile of extreme observations and mean of range. Those measures widely used in forecasting weather events or food supply. We discuss and formulate these dispersion measures in the appendix.
3.2 Group-based measures of dispersion
Another family of dispersion measures refer to minimizing differences in performance across possibly overlapping groups in the data defined by (protected) attributes like race and gender. Under equal opportunity [11. false positive rates are made commensurate, while equalized odds [1]] aims to equalize false positive rates and false negative rates among groups. More general attempts to induce fairly-dispersed outcomes include CVaR fairness (32 and multi-calibration [5). Our framework offers the flexibility to control wide range of measures of group CDF Fg i.e. T(F)), as well as the variation of ((E)) between groups. As an illustration of the importance of such bounds, [5] finds that the median white family in the United States has eight times as much wealth as the median black family; this motivates a dispersion measure based on the difference in group medians.
A Absolute/quadratee difference of risks and beyond. The simplest way measure the dispersion of a risk measure (like median) between two groups are quantities such as (T(Fg) T(Fg) ( ) or
(F(F)) )l². Moreover, one can study ((T((F))) -TFr)) for some general nonlinear functions.
These types of dispersion measures are widely used in algorithmic faimess II 20]
CVaR-fairness risk measure and its extensions. In [32), the authors further consider distribu- tion for each group, Pg. and distribution over group indices, Pixx. Letting CVV CVaRa, (Z) := Ez~pa [Z|Z> > for any distribution Pz. they define the following dispersion for the expected loss of group y (i.e. 1g == Ex-P, [X) for 10:
Dov.o (Py) = CV CVaRa, (Ug - EggPii ('l)-
natural extension would be Dev,a (F())) for general functional T(Fg), which we can write in a more explicit way 23
Dev. (T(F)) min
p
T-a P
(T(F)) - -0lx} E.g (T(ga)]
The function [T(Fg) - pl+ nonlinear function of T(F)). but it a monotonie function when p is fixed and its further composition with the expectation operation is still monotonic, which can be easily dealt with.
Uncertainty quantification of risk measures. In 4. the authors study the problem of un- certainty of risk assessment, which has important consequences for societal measures.They Theey for- mulate a deviation-based approach to quantify uncertainty for risks, which includes forms like: Pe(Piax) == (ETT (F,)) for different types of nonlinear functions Examples include vari- ance uncertainty quantification, where Ey-P (T(Fg) - B. T(Fg)) and (5. (a))] ==
Io (a)) to quantify how sensitive the a- VaR value is w.r.t its parameter a for some non-negative weight function sb.
4 Distribution-free control of societal dispersion measures
In this section, we introduce simple yet general framework to obtain rigorous upper bounds on the statistical dispersion measures discussed in the previous section. We will provide high-level summary of our framework in this section, and leave detailed derivations and most examples to the

---

appendix. Our discussion will focus on quantities related to the inverse of CDFs, but similar results could be obtained for CDFs.
In short, our framework involves two steps: produce upper and lower bounds on the CDF (and thus inverse CDF) of the loss distribution, and use these to calculate bounds on chosen target risk measure. First, we will describe our extension of the one-sided bounds in [30] to the two-sided bounds necessary to control many societal dispersion measures of interest. Then we will describe how these CDF bounds can be post-processed to provide control on risk measures defined by nonlinear functions and functionals of the CDF. Finally, we will offer novel optimization method for tightening the bounds for a chosen, possibly complex. risk measure.
4.1 Methods to obtain confidence two-sided bounds for CDFs
For loss values (X.) let (1)) .... S (x))) denote the corresponding order statistics. For the uniform distribution over [0.1], i.e. 4(00, 1), let U......
. Un an u(0,, 1) denote the corresponding order statistics U(1) .... - (n)- We will also make use of the following:
Proposition 1. For the CDF F of X, if there exists CDFs Fu, FL such that Fu F then we have F = F= = Fu-
We use (Frs 11 F2 to denote (1 -ccondiieeee bound pair ((1 8)-CBP,, which satisfies
P( n,U =F= P6 2
We extend the techniques developed in [3]. wherein one-sided (lower) confidence bounds on the uniform order statistics are used to bound F. This done by considering a one-sided minimum goodness-of-fit (GoF) statistic of the following form: S == millgiss ((((()) where 81,...,
8n
[0 + IR are right continuous monotone nondecreasing functions. Thus, IP(Vi ((X()) 2
8, (s6)) 1 8, for $5 fr P(S 2 r) 2 5}. Given this step function defined by $1...., 8n. easy to construct As L. via conservative completion of the CDF [0 found that Berk-Jones bound could be used to choose appropriate 's, and is typically much tighter than using the Dvoretzky-Kiefer-We Wollfoit (DKW) inequality to construct a bound.
4.1.1 A reduction approach to constructing upper bounds of CDFs
Now we show how we can leverage this approach to produce two-sided bounds. In the following lemma we show how a CDF upper bound can be reduced to constructing lower bounds.
Lemma 1. For 0 < L1 & L2 ... S I,, Pfi: (() 2 L,)
then, have
P(Vi: lim ++ F(X() e) S In-i41) 1411 > 6.
Furthermore, let R(x) be defined as 1 Ln if <. X()) Ln if X Sx x Xor i {1,2, 1); if (()) I Then, F F-1 R.
Thus, we can simultaneously obtain ( L. F%.)) by setting L, = 1,, (sx) and applying (different) CDF conservative completions. In practice, the CDF upper bound can be produced via post-processing of the lower bound. One clear advantage of this approach is that avoids the need to independently
produce pair of bounds where each bound must hold with probability 8/2.
4.2 Controlling statistical dispersion measures
Having described how to obtain the CDF upper and lower bounds (fr L, Fr we next turn using these to control various important risk measures such as the Gini coefficient and group differences. We will only provide high-level descriptions here and leave details to the appendix.
4.2.1 Control of nonlinear functions of CDFs
First we consider bounding {(F-), which maps F to another function of IR.
We also loosely consider a non non-negative increasing function F such that lome- F(x)= = 1, but F(x) < for any real value CDF.
5

---

Control for a monotonic function. We start with the simplest case, where & is a monotonic function in the range of X. For example. if & is an increasing function, and with probability at least Fa. = F F f then further by Proposition 1 we have that ((F)))) = {(F-) = < (( holds with probability at least 6. This property could utilized to provide bounds for the Gini coefficient or Atkinson index by controlling the numerator and denominator separately as integrals of monotonic functions of F-.
Example 1 (Gini coefficient). If given a (1 - 8)-CBP (F n, Fu,u) and F = 0 we can provide the following bound for the Gini coefficient. Notice that
Jo (2p 1)F (p)dp
So 2pF 2FF (p)dp
((X)
So (p)dp
So F (p(p)
Given F know
FT(p) (p) 2 0 (since we only consider non-negative losses, i.e. X is always non-negative),
G(X)= 2 Jor 2p) So Fr.
with probability at least
Control for absolute and polynomial functions. Many societal dispersion measures involve absolute-valus functions, e.g., the Hoover index or maximum group differences. We must also control polynomial functions of inverse CDFs, such in the CDFs of extreme observations, For any polynomial function (08) = Σ OgS* if & is odd, 8* is monotonic w.r.t. 8; if k is even, s = |s|
Thus, we can group 0 according to the sign of O% and whether is even or odd, and flexibly the upper and lower bounds already established for the absolute value function and monotonic functions to obtain an overall upper bound.
Example 2. If we have (1),(F)) (Fa), Ty (Fa)) such that (F,) S <T(F)) S (F,) holds for all g consider, then we can provide high probability upper bounds for
g(T(Fg)) T))
for any polynomial functions or the absolute function E. For example, with probability at least 1 5
T(Fg,) max (F - TF
Control for a general function. To handle general nonlinearities, introduce the class of functions of bounded total variation. Roughly speaking, if a function is of bounded total variation an interval, it means that its range is bounded on that interval. This is a very rich class including all continuously differentiable or Lipchitz continuous functions. The following theorem shows that such functions can always be decomposed into two monotonic functions.
Theorem 1. For (,,,,, (..)) if is function with bounded total variation the range of X, there exists increasing functions fI, f2 with explicit and calculable forms, such that with probability at least 8, (FF-) f fi f2
As an example, recall that studies forms like
L S(F (a))(()(a))
quantify how sensitive the a- VaR value is w.r.t its parameter a. For nonlinear functions beyond polynomials, consider the example where e" + e This can be readily bounded since it is mixture of monotone functions.
'This can be easily achieved by taking truncation over 0. Also, the construction of E in Section A.2 always satisies this constraint.

---

4.2.2 Control of nonlinear functionals of CDFs and beyond
Finally, we show how our techniques from the previous section can be applied to handle the general form Jo {(T(F=(a))
where can be general function (not necessarily non-negative) and & can be a functional of the inverse CDF. To control {(T(F=))) we can first obtain two-sided
bounds for T(F-) if 7 ( ) is in the class of QBRMs or in the form of (xp) (FF (p) )dp for some nonlinear function & (as in ( We can also generalize the weight functions in QBRMs from non negative to general weight functions once we notice that tú can be decomposed into two non-nee nog-negttvve functions, i.e. for terms like max tb, O) (p))dp by adopting an upper bound for {(F
max p.. 0) max 0}. Then, we can provide upper bounds
4.3 Numerical optimization towards tighter bounds for statistical functionals
Having described our framework for obtaining CDF bounds and controlling rich families of risk measures, we return to the question of how to produce the CDF bounds. One drawback of directly using the bound returned by Berk-Jones is that is not weight function aware, i.e., it does not leverage knowledge of the target risk measures. This motivates the following numerical optimization method, which shows significant improvement over previous bounds including DKW and Berk-Jones bounds (as well as the truncated version proposed in (30).
Our key observation that for any S L1 -... S. S m! S._ drn JL." drn-1 f dr1, where the right-hand side integral is a function of [T;) and its partial derivatives can be calculated exactly by the package in [2]] Consider controlling
we have P(Vi, ((X 2 L.) Z
So ((p) ((p))-(p)d as an example. For any {T,)]=] satisfying P(Vi, ((X()) 2 L,) 2 one can use conservative CDF completion to obtain P i.e.
L. ((W)E(P n.
Ih
(v))dp = E((
(()dp, Li-1
where Ln+1 is 1, Lo = O, and X ((++1) = oo or known upper bound for X. Then, we can formulate tightening the upper bound an optimization problem:
a+1 min ((( (L.).. 1=1
(" w(p)dp 1i-1
Th
such that (VV, (( 2 21 and 0 S L..... Ln S 1. We optimize the above problem with gradient descent and a simple post pestpproeessig procedure to make sure the obtained {L.32 strictly satisfy the above constraints. In practice, we re- parameterize {La)r_ with network do that maps random seeds function of the L, 's and transform the optimization objective from [L,}²_ to 0. We find that simple parameterized neural network model with 3 fully-connected hidden layers dimension 64 is enough for good performance and robust to hyper-paramete settings.
7" inf ntv( [. (0) - 7.... [.)( - 7, 1) 2 6.7200 0}.
Notice that there is always feasible solution. We can use binary search efficiently find (a good approximate of) y
5
Experiments
With our experiments, we aim to examine the contributions of our methodology in two areas: bound formation and responsible model selection.
5.1 Learn then calibrate for detecting toxic comments
Using the CivilComments dataset 6 we study the application of our approach to toxic comment detection under group-based fairness measures. CivilComments is large dataset of online comments
7

---

labeled for toxicity as well as the mention of protected sensitive attributes such as gender, race, and religion. Our loss function the Brier Score, a proper scoring rule that measures the accuracy of probabiliisic predictions, and we work in the common setting where a trained model is calibrated post-hoe to produce confidence estimates that are more faithful to ground-truth truth label probabilities. We use a pre-trained toxicity model and apply Platt scaling model controlled by single parameter to optimize confidence calibration. Our approach is then used to select from set of hypotheses, determined by varying the scaling parameter in the range (0.25, 2] (where scaling parameter recovers the original model). See the Appendix for more details on the experimental settings and our bound optimization technique.
5.1.1 Bounding complex expressions of group dispersion
First, we investigate the full power of our framework by applying it to a complex statistical dispersion objective. Our overall loss objective considers both expected mean across groups as well as the maximum difference between group medians, and can be expressed as: C = (F, + Asupg.gr (I2(Fg) - T2(F'g)),, where Ti is expected loss and T2 is smoothed version of a median (centered around 3 = 0.5 with spread parameter a = 0.1). Groups are defined by intersectional attributes: I G {black female, white female, black male, white male]. We use 100 and 200 samples from each group, and select among 50 predictors. For each group, we use our numerical optimization framework optimize bound O Ti (Fe) + +TfF)) using the predictor (and accompanying loss distribution) chosen under the Berk-Jones method. Results are shown in Table T We compare our numericalll-optimizze bound (NN-Opt.) to the bound given by Berk-Jones as well as an application of the DKW inequality to lower- wever-buundigg- CDF.
Our framework enables to choose a predictor that fits our specified faimess criterion, and produces reasonably tight bounds given the small sample size and the convergence rate of yn. Moreover, there is a large gain in tightness from numerical optimization in the case where n = 100. especially with respect to the bound on the maximum difference in median losses (0.076 vs. 0.016). These results show that single bound can be flexibly optimized to improve on multiple objectives at once via our numerical method, key innovation point for optimizing bounds reflecting complex societal concerns like differences in group medians S
Table 1:
Applying our full framework to control an objective considering expected group loss as well as a maximum difference in group medians for 100 and n 200 samples.
n 100
n 200 Max Diff.
Method
Exp. Grp.
Max Diff.
Total
Exp. Grp.
Total
DKW BJ
0.36795
0.90850
1.27645
0.32236
0.96956
1.29193
0,34532
0.07549
0.42081
0.31165
0.00666
0.31831
NN-Opt. (ours)
0.32669
0.01612
0.34281
0.30619
0.00292
0.30911
Empirical
0.20395
0.00004
0.20399
0.20148
0.00010
0.20158
5.1.2 Optimizing bounds on measures of group dispersion
Having studied the effects of applying the full framework, we further investigate whether our method for numerical optimization can be used get tight and flexible bounds on functionals of interest. First, 3-CVaR is a canonical tail measure, and we bound the loss for the worst-off - proportion of predictions (with is useful when a range of quantiles of interest is known but flexibility to answer different queries within the range is important. Finally, we consider worst-quantile weighting function (p()) = p. which penalizes higher loss values on higher quantiles, and study a smooth delta function around = 0.5, a more robust version of median measure. We focus on producing bounds using only 100 samples from particular intersectionally-defiee and all measures are optimized with the same hyperparameters. The bounds produced via numerical optimization (NN-Opt.) are compared to the bounds in [30] (as DKW has been previously shown to produce weak CDF bounds), including the typical Berk-Jones bound as well as truncated version tailored to particular quantile ranges. See Table and the Appendix for results.
0.75). Next, we bound a specified interval of the VaR (00.5, 0.9). which
protected group, in this case black females,
8

---

The numerical optimization method induces much tighter bounds than Berk-Jones on all measures, and also improves over the truncated Berk-Jones where is applicable. Further, whereas the truncated Berk-Jones bound will give trivial control outside of [8min: Smaz], the numerically-optimizze bound not only retains reasonable bound on the entire CDF, but even improves on Berk-Jones with respect to the bound on expected loss in all cases. For example, after adapting to CVaR, the numerically- optimized bound gives a bound on the expected loss of 0.23, versus 0.25 for Berk-Jones and 0.50 for Truncated Berk-Jones. Thus numerical optimization produces both the best bound in the range of interest as well as across the rest the distribution, showing the value adapting the bound to the particular functional and loss distribution while still retaining the distribution-fri free guarantee.
Table 2: Optimizing bounds on measures for protected groups.
Method
CVaR
VaR-Interval
Quantile- Weighted
Smoothed-
Berk-Jones
0.91166
0.38057
0.19152
0.00038
Truncated Berk-Jones
0.86379
0.34257
NN-Opt. (ours) 0.85549
0.32656
0.17922
0.00021
5.2
Investigating bounds on standard measures of dispersion
Next, we aim explore the application of our approach to responsible model selection under non-group-based fairness measures, and show how using our framework leads to a more balanced distribution of loss across the population. Further details for both experiments be found in the Appendix.
5.2.1 Controlling balanced accuracy in detection of genetic mutation
RxRx1 B1] is task where the input is 3-channel image of cells obtained by fluorescent microscopy, the label indicates which of 1, 1,139 genetic treatments the cells received, and there is a batch effect that creates challenging distribution shift across domains. Using model trained on the train split of the RxRx1 dataset, we evaluate our method with an out-of-distribution validation set to highlight the distribution- frrer nature of the bounds. We apply threshold to model output in order to produce prediction sets, or sets of candidate labels for a particular task instance. Prediction sets are scored with balanced accuracy metric that equally weights sensitivity and specificity, and our overall objective is: L = Ti (F) + (F)) where T; is expected loss, T2 is Gini coefficient, and À = 0.2. We choose among 50 predictors (i.e. model plus threshold) and use 2500 population samples produce our bounds. Results are shown in Figure
Cum. Loss Share
Expected
Expected-Gin Eqqulity
Loss
Poporedi
Expeced
02
0.5
0.00
10
10
Threshold
Figure 2: Left: Bounds on the expected loss, scaled Gini coefficient, and total objective across different hypotheses. Right: Lorenz curves induced by choosing hypothesis based on the expected loss bound versus the bound on the total objective. The y-axis shows the cumulative share of the loss that is incurred by the best-off / proportion of the population, where perfectly fair predictor would produce a distribution along the line T.
The plot on the left shows how the bounds on the expected loss Tj, scaled Gini coefficient XT2, and total objective vary across the different hypotheses (i.e. model and threshold combination for producing prediction sets). The bold points indicate the optimal threshold choice for each quantity. On the right is shown the Lorenz curves (a typical graphical expression of Gini) of the loss distributions induced by choosing hypothesis based on the expected loss bound versus the bound on the total objective. Incorporating the bound on Gini coefficient in hypothesis selection leads to more equal loss distribution. Taken together, these figures illustrate how the ability to bound non-group based

---

dispersion measure like the Gini coefficient can lead to less skewed outcomes across a population, key goal in socictal applications.
5.2.2 Producing recommendation sets for the whole population
Using the MovieLenns dataset [12. we test whether better control on another important non non-group based dispersion measure, the Atkinson index (with e = 0.5), leads to a more even distribution of loss across the population. We train user/item embedding model, and compute loss that balances precision and recall for each set of user recommendations. Results are shown in Figure Tighter control of the Atkinson index leads to a more dispersed distribution of loss across the population, even for subgroups defined by protected attributes like age and gender that are unidentified for privacy or security reasons.
Atkisson
018
Bound
Cum LIVe CQAee
Malk
of couality
equaiity
0.31
030
Throshool
Figure 3: We select two hypotheses ho and hı with different bounds on Atkinson index produced using 2000 validation samples, and once again visualize the Lorenz curves induced by each. Tighter control on the Atkinson index leads to more equal distribution of the loss (especially across the middle of the distribution, which aligns with the choice of c). highlighting the utility of being able to target such a metric in conservative model selection.
Related work
The field of distribution-fee uncertainty quantification has its roots in conformal prediction (77 The coverage guarantees of conformal prediction have recently been extended and generalized to controlling the expected loss of loss functions beyond coverage [I3. The framework proposed by 30 offers the ability to select predictors beyond expected loss, to include a rich class of quantile- based risk measures (QBRMs) like CVaR and intervals of the VaR; they also introduce a method for achieving tighter bounds on certain QBRMs by focusing the statistical power of the Berk-Jones bound certain quantile range. Note that these measures cannot cover the range of dispersion measures studied in this work.
There is rich literature studying both standard and group-based statistical dispersion measures, and their use in producing fairer outcomes machine learning systems. Some work in fairness has aimed achieving coverage guarantees across groups [24 25 but to our knowledge there has not been prior work exploring controlling loss functions beyond coverage, such as the plethora of loss functions aimed at characterizing fairness, which can be expressed group-based measures (cf. Section 3.2). Other recent fairness work has adapted some of the incquality measures found in economics. [32 aims enforce that outcomes not too different across groups defined by protected attributes. and introduces a convex notion of group CVaR, and (24] propose a DFUQ method of equalizing coverage between groups. 119 studies distributional inequality measures like Gini and Atkinson index since demographic group information is often unavailable, while 7 use the notion of Lorenz efficiency to generate rankings that increase the utility of both the worst-off users and producers.
7 Conclusion
In this work, we focus on a rich class of statistical dispersion measures, both standard group- based, and show how these measures can be controlled. In addition, we offer a novel numerical optimization method for achieving tighter bounds on these quantities. We investigate the effects of applying our framework via several experiments and show that our methods lead to more fair model selection and tighter bounds. We believe our study offers a significant step towards the sort of thorough and transparent validation that is critical for applying machine learning algorithms to applications with socictal implications.
10

---

Acknowledgements
We thank the Google Cyber Research Program and ONR (Award N00014-23-1-2466) for their generous support. J. Snell gratefully acknowledges financial support from the Schmidt DataX Fund Princeton University made possible through major gift from the Schmidt Futures Foundation.
References
[1] 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:21 10.01052, November 2021.
[2] Anthony Atkinson et al. On the Measurement of Inequality. Journal of Economic Theory, 2(3):244-263, 1970.
[3] Stephen Bates, Anastasios Angelopoulos, Lihua Lei, Jitendra Malik, and Michael Jordan. Distribution-Free Risk-Controlling Prediction Sets. arXiv:2101.0270: August 2021.
[4] Mohammed Berkhouch, Ghizlane Lakhnati, and Marcelo Brutti Righi. Spectral Risk Measures and Uncertainty. arXiv preprint
2019.
[5] Neil Bhutta, Andrew Chang, Lisa Dettling, and Joanne Hsu. Disparities in Wealth by Race and Ethnicity in the 2019 Survey of Consumer Finances. FEDS Notes, 2020, 09 2020.
[6] Daniel Borkan, Lucas Dixon, Jeffrey Sorensen, Nithum Thain, and Lucy Vasserman. Nuanced metrics for measuring unintended bias with real data for text classification. In Companion proceedings of the 2019 world wide web conference, pages 491-500, 2019.
[7] Virginie Do, Sam Corbett-Davies. Jamal Atif, and Nicolas Usunier. Two-Sided Fairness in Rankings via Lorenz Dominance. Advances in Neural Information Processing Systems, 34:8596-8608, 2021.
[8] Kevin Dowd and David Blake. After VaR: The Theory, Estimation, and Insurance Applications of Quantile-Bar Basee Risk Measures. Journal of Risk & Insurance, 73(2):193-22 June 2006.
[9] Chengyue Gong and Xingchao Liu. Bi-Objective Trade-off with Dynamic Barrier Gradient Descent. Advances in Neural Information Processing Systems, 2021.
[10] Laura Hanu and Unitary team. Detoxify. Github. https:/ggitnub.ccmmmumaaaaa/a/ae 2020.
[11] Moritz Hardt, Eric Price, and Nati Srebro. Equality of Opportunity in Supervised Learning. Advances Neural Information Processing Systems, 29, 2016.
[12] Maxwell F Harper and Joseph A Konstan. The Movielens Datasets: History and Context. ACM Transactions on Interactive Intelligent Systems, 5(4): 2015.
[13] HO Hartley and HA David. Universal Bounds for Mean Range and Extreme Observation. The Annals of Mathematical Statistics, pages 85-99, 1954.
[14] Ursula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Calibration for the ceamputationally-ddeniifii Machine Learning, pages 1939-1948. PMLR, 2018.
Masses. In International Conference on
[15] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing Fairness Gerry- mandering: Auditing and Learning for Subgroup Fairness. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 2564-2572. PMLR, 2018.
[16] Bruce P Kennedy, Ichiro Kawachi, and Deborah Prothrow-Stith Income Distribution and Mortality: Cross-Sectional Ecological Study of the Robin Hood Index in the United States. British Medical Journal,
1996.

---

[17] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga. Richard Lanas Phillips, Irena Gao, Tony Lee, Etienne David, Ian Stavness, Wei Guo, Berton A. Farnshaw, Imran S. Haque, Sara Beery, Jure Leskovec, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang. WILDS: A Benchmark of in-the- Wild Distribution Shifts, 2021.
[18]
Ananya Kumar, Percy S Liang, and Tengyu Ma. Verified Uncertainty Calibration. Advances in Neural Information Processing Systems, 32, 2019.
[19] Tomo Lazovich, Luca Belli, Aaron Gonzales, Amanda Bower, Uthaipon Tantipongpipat, Kris- tian Lum, Ferenc Huszar, and Rumman Chowdhury. Measuring Disparate Outcomes of Content Recommendation Algorithms with Distributional Inequality Metrics. Patterns, 108)8000568, 2022.
[20] Jean- Yves Le Boudec. Rate Adaptation, Congestion Control and Fairees: A Tutorial. Web Page, November, 4, 2005.
[21] Amit Moscovich, Boaz Nadler, and Clifford Spiegelman. On the Exact Berk-Jones Statistics and Their p- Value Calculation. Electronic Journal of Statistics, 10(2):239-2354,, 2016.
[22] John Platt et al. Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods. Advances in Large Margin Classifiers, 10(3):61-74, 1999.
[23] Tyrrell Rockafellar, Stanislav Uryasev, al. Optimization of Conditional Value-at-Risk. Journal of Risk, 2:21-42, 2000.
[24] Yaniv Romano, Rina Foygel Barber, Chiara Sabatti, and Emmanuel Candès. With Malice Toward None: Assessing Uncertainty via Equalized Coverag. Harvard Data Science Review, 2(2):4, 2020.
[25] Yaniv Romano, Stephen Bates, and Emmanuel J. Candès. Achieving Equalized Odds by Resampling Sensitive Attributes. arXiv:2006.04290 June 2020.
[26] Halsey Lawrence Royden and Patrick Fitzpatrick. Real Analysis, volume 32. Macmillan New York, 1988.
[27] Glenn Shafer and Vladimir Vovk. A Tutorial on Conformal Prediction. Journal of Machine Learning Research, 9(3), 2008.
[28] Galen R. Shorack and Jon A. Wellner. Empirical Processes with Applications to Statistics. Society for Industrial and Applied Mathematics, January 2009.
[29] Anthony F Shorrocks. The Class Additively Decomposable Inequality Measures. Economet- rica: Journal of the Econometric Society, pages 613-625, 1980.
[30] Jake C Snell, Thomas P Zollo, Zhun Deng, Toniann Pitassi, and Richard Zemel. Quantile Risk Control: A Flexible Framework for Bounding the Probability of High-Loss Predictions. International Conference Learning Representations (ICLR), 2023.
[31] James Taylor. Berton Earnshaw, Ben Mabey, Mason Victors, and Jason Yosinski. Rxrxl: An Image Set for Cellular Morphological Variation Across Many Experimental Batches. In International Conference on Learning Representations (ICLR), volume 22, page 23, 2019.
[32] Robert Williamson and Aditya Menon. Fairness Risk Measures. In International conference on machine learning. pages 6786-6797. PMLR, 2019.
[33] Shlomo Yitzhaki. Relative Deprivation and the Gini Coefficient. The Quarterly Journal of Economics, 93(2):321-324, 1979.
[34] Shlomo Yitzhaki and Edna Schechtman. The Gini Methodology: a Primer on a Statistical Methodology. Springer, 2013.
12

---

Appendix
Broader impact. The broader impact of the proposed framework is significant, as it extends the ability to gain trust in machine learning systems. However there are important concerns and limitations.
Focus performance metrics In this paper we propose range of performance metrics, which extend well beyond standard metrics concerning expected loss. However, in many situations these metrics are sufficient to capture the effects of the machine learning system. Often a number of different metrics are required to provide a clearer picture of model performance, while some effects are difficult to capture in any metric. Also, while the measures studied offer the ability to more evenly distribute a quantity across population. they do not offer guarantees individuals. Finally, achieving more equal distribution of the relevant quantity (e.g., loss or income) may have negative impacts on some segments of the population.
Limitations These are summarized in the Conclusion but expanded upon here. An important assumption in this work, and in distribution-fres uncertainty quantification more generally, that the examples seen in deployment those in the validation set that are used to construct the bounds. Although this is an active area of research, here we make this assumption, and the quality of the bounds produced may degrade if the assumption is violated. A second limitation is that the scope of hypotheses and predictors we can select from is limited, due to theoretical constraints: correction must be performed based on the size of the hypothesis set. Finally, the generated bounds may not be tight, depending on the amount of available validation data and unavoidable limits of the techniques used to produce the bounds. We did some comparisons to Empirical values of the measures we obtained bounds for in the experiments; more extensive studies would be useful to elucidate the value of the bounds in practice.
drawn from the same distribution as
Organization of the Appendix. (1) Appendix we provide detailed statements and derivations
of our methodology presented Section 4.2. including how to obtain bounds for those measures
mentioned in Section 3] (2) in Appendix B we introduce further societal dispersion measures, beyond
those presented in Section 3 and corresponding bounds; (3) in Appendix [C] we investigate the
extension of our results to multi-dimensional settings; (4) lastly, in Appendix and we provide
more complete details and results from our experiments 5
A Derivations and proofs for bounding methods
Section A.I
we first consider how to control, or provide upper bounds on, various quantities when F- F,, which are constructed by {X,} such that
we are given (F n.L.
P(P. 3 = f 2 1
where the randomness is taken over {X,
Then, in Section A.2 we will show how we obtain (F F..T)) by extending the arguments in 33) In addition, we show details in Section A.2.2 on how we go beyond the methods in (30 and provide numerical optimization method for tighter bounds.
Proof of Proposition We briefly describe the the proof for Proposition [ The proof is mainly
based [30], but we include it here for completeness. Notice for any non-decreasing function
G: R.R.. + R (not just a CDF), there exists the (general) inverse of G as G (-(p) = inf x G(x) 2 p) for any p E R.
Proposition 2 (Restatement of Proposition For the CDF F of X, there exists two increasing functions Fu, FL such that Fu Z F Z FL, then we have FI 2 F 2 Fū.
Proof. For any two non-decreasing function G(p) and C(p), by the definition of the general inverse function, G(G (p) 2 p. If C. ž G. we therefore have C (p)) 2 G(G-(p)) 2 p. Applying C- to both sides yields C' (C (p))) C- (p). But > C- C(x) (see e.g. Proposition 3 on p.
13

---

of (28) and thus G' 2 (p). Plugging in F and Fu as G and C, this can yield F > Fo. The other direcion is similar.
A.1
Control of nonlinear functions of CDFs (Section 4.2.1)
A.1.1 Control for monotonic functions
Recall that start with the simplest where is monotonic function in the range of X. Is straightforward to have the following claim.
Claim 1. If we have n. 3 F increasing function, then
F with probability at least 1 - 5 for some & (0, 1). if is an
<(F = ((F-)( =(FF))(((F.))))
with probability at least 1 8. Similarly, if is a decreasing function, then E(F:))) 3 E(F-) z E( ((F2,7) with probability at least 5.
We show how this could be applied to provide bounds for Gini coefficient and Atkinson index by controlling the numerator and denominator separately as integrals of monotonic functions of FT
Example 3 (Gii coefficient). If given a (1 6)-CBP (F n.L:
F Fn,y) and F n.L 2 0f we can provide
the following bound for the Gini coefficient. Notice that
(2p 1)F So F (p)dp
So 2pF 2pF (p)dp
G(X)
So F (p)dp
Given F (p) 2 0 (since we only consider non-negative losses, i.e. X is always non-negative), we know
g(X) < So 20
1,
So (
with probability at least 1 8.
Example 4 (Atkinson index). First, we present the complete version of Atkinson index. Namely,
1o (F))'))))
e f 8
A(e,X)
Do (p)dp expl. In(F (p))dp) e=
fo (-)dd
Notice that for & 2 0, (-)²- and In(-) are increasing functions, thus, for Arkinson index and (1 (1-
CBP (F5 Fo F(. if n. = 0, let us define Xe, = (1)
ife 2 0,
Sd F (p)dp
1; exp( lul In(P:
if = Then, with probability at least - 6, (E, X) is an upper Jg f0 (p)do
bound for A(E, X) for all e E [0, 1).
As mentioned in Remark I instead of calculating bounds separately for each simple post-processing enables us to efficiently issue family of bounds.
Example (CVaR fairness-risk measures and beyond). Recall thatfor a E (0, 1),
p+ - Eg-P.. (T(g)) - pl+) (TgrPa(((FE))
(ev.)(T(Fg)) = min PCR
The function [T(F,) pl+ is an increasing function when p is fixed and its further composition
with the expectation operation is still increasing. If we have (F)), T (F₂)) such that (Fy) S
"This can be easily achieved by taking truncation over 0. Also, the construction of E in Section A.2 always satisies this constraint.
14

---

T(Fg) - (Fg) for all g with probability at least 1 8. then we have
D (T(()))(F))) S min PER { p 1 I-a B (Fg) pl+
1
Byw (T))())))) (Fa)),
and the first term of RHS can be minimized easily since it is convex function of
A.1.2 Control for absolute and polynomial functions
Recall that if $s S 8 S sU. then
8y, (s. 2 0} ---7 sy 1 (su S =0} S |s| max[[sol:
More generally, for any polynomial function (ss) = Ex=0 axs". Notice if is odd, st is monotonic w.r.t. and can bound
((s) S
Σ
U +
Σ
04 k
{Rr is add, 2020)
(A is add, ag <0
+
Σ
Og max max(1s2]* |801 (
Σ
ax(5 2 03 1 S 00)
(A: even, on 201
{k is even, or <0
So, for 6(F-), we can plug in P. and T to replace and to obtain an upper bound with probability at least (1 - 8). The derivation for the lower bound is similar. We summarize our results as the following proposition.
Proposition 3. given (1 - 8)-CBP, then with probability at least 1 - 5, (Pro L. n.U
F
Fo 1f n. 0} F 1 n. - 03 3 [F max 1
Moreover, for any polynomial function (ss) = Ek=o s we have
Φ(F 3
Σ
on ( +
Σ
on (
(k odd, 2x20)
(k add, cx
Σ
OKk max | |,,,7.11
(A is even, or 20}
Σ
an (
(f
1 S 00) n. n.U 2 0}
(Ir is even, <0}
Example 6. If we have (F)),, such that (F,) S (TFF)) S T holds for all g consider, then we can provide high probability upper bounds for
E(T(F,,) )))
for any polynomial functions or the absolute function E. For example, with probability at least 1 6,
(T(Fg) T(Fg2)) S max(1T - (F. ( (Faa)))
We will further show in Appendix B how results applied to specific examples.
A.1.3 Control for a general function
To handle general non-linearity, we need to introduce the class of functions of bounded variation on certain interval, which is very rich class that includes all the functions that are continuously differentiable or Lipchitz continuous on that interval.
Definition (Functions of bounded total variation (6)).. Define the set of paritions on [a, bj as
{ (ro, X1, ... ) a partition of (a, b) satisfying x, S fori all 0 < n 1}.
$I(F)) here is one of the functionals in the form we studied, so that we can provide upper and lower bounds for it.
15

---

Then, the total variation of continuous real-valued function ç. defined on (a, b] C IR is defined as
(E
sup Σ (((ma)))- -
FEll 1-0
where IT is the set of all partitions, and we say a function is of bounded variation, i.e. & E BV((a, b)) iff (E) < 0C.
Recall that X 2 0 in cases, then, for E(F-), Theorem (A restatement formal version of Theorem For a (1 - -)-CBP (F F n, for
have the following bound.
any p [0, such that the total variation of & is finite on [0, 1. (p)), then
Vo F.
(E) Vo (.
E(F (p))
(E) + E ((PA
Moreover, i is continuously differentiable on [0, F (p)), we can express Vi (E) as Jo (s) for any x E [0, F (p))
Proof. By the property of functions of bounded total variation 226 if is of bounded total variation on [0, f L. (p)), then, we have that: for any I E [0, f5- n. (p))
{(x) = Vo (5) (Vi (5) E(x))
where both f1(x) (E) and f2(2) VØ (5) {(x) are increasing functions. Moreover,
(E) = /
de ds
(s) ds
if & is continuously differentiable.
Thus, by taking advantage the monotonicity, we have
((F S Vo P. (p)
(E) Vo (
(E) (
So, if & is of bounded variation the range of X, then
S(FT) N Vo P. (5) Vo #s
(5) ((F):)) = fF(F). f2(F%
A.2 Methods to obtain confidence two-sided bounds for CDFs (Section 4.1
We provide details for two-sided bounds and our numerical methods in the following.
A.2.1 The reduction approach to constructing upper bounds of CDFs (Section 4.1.1
We here provide the proof of Lemma] I
Lemma 2 (A restatement & formal version of Lemma D. For O S L1 La ... S In < since
P(vi: : ((X()) Z Ta) Z P(Vi: U(o 2 T.)) by (30), if we further have P(Vi U(s) 2 La) 2 1 - 6,
then we have
P(vi: : lim F(X() e) s 1 Ln (11) 2 1-6 8. --
Furthermore, les R(x) be defined as
Lns for <X11)
1 Ln-1s for X(1) S x < X
R(x)
1 Lı
for ((n-1) ((n)
for X(n) $ x.
Then, F 3 R.
16

---

Proof. Notice that for given order statistics (x) let IP (X denote the probability taken over the randomness of (X and Px denote the probability taken over the randomness of X, which is an independent random variable drawn from F. Let us denote B -X, and (G) as the i-th order statistic for samples { {-x,)==1- easy to see that B(n-i41) - (())) We also denote Pn as the probability taken over the randomness of B, and Fn as the CDF of B.
(((1)) (Vi: lim () -c) Ln i+1) = P(x (A) Px (X X(1) In-it1)
c-0
PP (Vi Px -X(()) > Ln-i+t)
_P( (AI: PB (B S B((n-tt)) > In-it1)
=P(Vi: : FB FB (U (n(nit))) Ln-
2PPVi: ((ni++1) Ln-i+1).
where we use the fact that Fg (U(n)++1) is of the same distribution as B(n-i+1) and the last inequality follows from Proposition eq. 24 on p.5 of (28).
Notice that P(Vi: U (m-+++)) Ln 1----- i+1) P(Vi: : (n-)+1)
(+1) In-i-1), and according to 30 and our assumption, PP(V: ()) L,) 2 (vv: (1) L.) 21-6.
The conservative construction of R satisfies R ž F straightforwardly if vi: lime- F(X() <) s
1 1 L, (111)) holds. Thus, we know R = F with probability at least 1 - 6. Our proof is complete.
Uniform Distribution
Empirical Distribution
68
8
60
X(3
X(2
Xit)
Xiti
Xili
X(]
Xist
Xist Xum M01 M020
LOSS
Figure 4: Example illustrating the construction of distribution-free CDF lower and upper bounds by bounding order statistics. On the left, order statistics are drawn from a uniform distribution. On the right, samples are drawn from real loss distribution, and the corresponding Berk-Jones CDF lower and upper bound are shown in black. Our distribution- method gives bound b and (*) on each sorted order statistic such that the bound depends only i, as illustrated in the plots for i (shown in blue). On the left, 1000 realizations of (()), ..... [()) are shown yellow. On the right, 1000 empirical CDFs are shown in yellow, and the true CDF [ shown in red.
A.2.2 Details of numerical optimization method (Section
Now, introduce the details of our numerical optimization method. Recall that one drawback of the QBRM bounding approach that is not weight function aware: when controlling fo ( (p)dp for non-negative weight function tb, the procedure ignores the structure of vi, as it first obtains fd6 then provides an upper bound Jo (bp) F.:z (p)dp.
n.
Our numerical approach can overcome that drawback and can also easily be applied to handle mixtures of multiple functionals. The bounds obtained by our method are significantly tighter than those provided by methods in (30 the regime of small data size. Notice that the small data size regime is the one people care about because when the data size is large, all the bounds we discussed will converge to the same value, and the gap between different bounds will shrink to as the data size grows.
17

---

First, by |? and Proposition 1, eq. 24 on p.5 of (28), we have for any 0 S L1 S ... S Ln S
P(Vi, ((X 2 L.) 2 P(ii, USA 2 Li)
2 n! [" din Inn
/ dxi,
dxn-1
where the right-hand side integral is function of {Li) and its partial derivatives can be exactly calculated by the package in [21]. Specifically, the package in [2I] enables us to calculate
dxn S.m..
dxn-1 Jrn
12,,,22 Las 1):
dr
In
for any positive integer Notice that the partial derivative of v(LI, L2, ... L is:
LLn 1) with respect to
Or,0 S, L2, ,,,, fr dxn
dxn-1"
dx
dri+1
lm
Ii-i
I441
( dri-1'"
Li
dr
Jn
Li-1
-L((ii
:; L,),
which we can also use the package in [2 calculate the partial derivatives.
Consider providing upper or lower bounds for fo ( (p)dp for non -egaatitvve weight function eb as an example. For any { satisfying (Vi, F(X(o) L.) 2 1 8, one can use conservative CDF completion in 30 to obtain F F i.e. fo (F)))(F
Σ E(Xg)) Sty (p)
where Ln+1 is 1, Lo = 0, and ((m+1) = oo or known upper bound for Then, we can formulate tightening the upper bound an optimization problem:
a+1 Σ (() 1d) <p)ddp
min (L
such that
P(Vi, ((X() 2 L.) 21 and 0 .... S. 11.
Similarly, for the lower bound, construct 5 Fn then, we can study the following lower bound for fo (ip) F (pp)dpp
the CDF completion mentioned in Theorem I and
a
/ hn- JEn- 4(p)dp
Σ
(((())
where ((o)
Parameterized model approach. Notice the above optimization problem formulation has a draw- back: if more samples are drawn, i.e. increases, then the number of parameters need to optimize also increases. In practice, we re-parameterize {L: as the following:
Tx(0) Σ exp((o(0)))
T カ 1+ exp(ov(g;))
where y: are random Gaussian seeds. This is of the same spirit as using random seeds in generative models. We find that a simple parameterized neural network model with fully-connected hidden layers of dimension 64 is enough for good performance and robust to hyper-parameter settings. Take the upper bound optimization problem as an example; using the new parameterized model, we have
n+1
7c(0)
min Σ (0)
(()())
( (p)dp
(I)
18

---

such that
n!
n d
dx 2 6,
(0) where Lg = 0, Ln+1 1, X (n+1) = oo or known upper bound for X. We can solve the above optimization problem using heuristic methods such as (9].
(0)
Post-procee post-processing for a rigorous guarantee for constraints. Notice that we may not ensure the constraint n! (L,()) dr'n - (6) dzn-1 SL(() Li(0; dz 2 - is satisfied in the above optimization because may surrogates like Langrange forms in optimization processes. To make sure the constraint strictly satisfied, we can do the following post post-processing: let us denote the obtained L ss by optimizing
(T) as (,)). Then, we look for 7" E [0, L0) such that
x = inf (l)(( - -.. ,., 7, 6,7 0}.
Notice there is always feasible solution as when 7 [.n(())
nlv (L) 7, -. (0) 1) P(ii, U(6 2 0) =1 and v(Li (0) - ..... (0) 7, is a decreasing function of 7. We can use binary search efficiently find (a good approximate of) y*
B Other dispersion measures and calculation
B.1 Lorenz curve & the extended Gini family
the main context, Lorenz curve has been mentioned reference to Gini coefficient and Atkinson index. To be more complete, we further demonstrate the definition of Lorenz curve in its mathematical form.
Lorenz curve.
Definition (Lorenz curve). The definition of Lorenz curve is a function: for t E [0,
fe F F- (p) dp
C(t)
So dp)
We obtain lower bound and upper bound function for the Lorenz curve. Given (1 6)-CBP (F6 LF F8 F,,y) and F F ž 0. we can construct lower bound function 2 (t):
(t) = Se¹ i dp
Fo P (v) dp
and an upper bound can be obtained by
fo p (v) dp
c (x)
So ps. (p) dp
With probability least 1 5, the true Lorenz curve sits between the upper bound function and the lower bound function for all t E [].
The extended Gini family. The Gini coefficient can further give rise to the extended Gini family, which is family of variability and inequality measures that depends on one parameter the extended Gini parameter. The definition is follows.
Definition (The extended Gini family 34). The extended Gini coefficient given by
G(v, ((v -vCov(X, [1 1(
E[X]
=1 So (1 F
So (p)ddp
where v/ > 0 is the extended Gini parameter and Cov(,, is the covariance.
19

---

For the extended Gini coefficient, choosing different v/ss corresponds to different weighting schemes applied to the vertical distance between the egalitarian line and the Lorenz curve; and the standard Gini coefficient.
Given 6)-CBP (F kn,0) and F
O,
construct upper bound for g. Let
() : v S - p) F
fo F (D)
then 0 (v. X) = (P) with probability at least 1 - 8.
B.2
Generalized entropy index
The generalized entropy index (29 is another measure of inequality in population. Specifically, the definition is: for real number a
E
# -
a(a-1)
xx
G)
2X
In
EX
)
a==1
E
[n( xx
if a
not hard to further expand the expressions and write the generalized entropy index as:
T|a-T So
[(
FT()
-
-1] dp, a # 0,1
F-)ddp
(p)dp)
C)(a,X):= ==
Sh
F (p)
In (D)
To FP (p)dp) dp, if a a=
To (p)dp
-S [n(
FT (p) r (p)dpp
dp,
if 0.
Notice that (.)o is a monotonic function for the case a + 0, 1, and In(.) is also a monotonic function, the bound be obtained similarly as in the case of Atkinson index. For instance, for >> given a (1 8)-CBP (F Fb,u).
ala -0a-1).
(T,
[
( dp ala 1) I.') [
F (D)
-1 dp.
[T 1 F
-
Other cases be tackled in similar way, which we will reiterate here.
B.3
Hoover index
The Hoover index [16] equal to the percentage of the total population's income that would have to be redistributed to make all the incomes equal.
Definition (Hoover index). For a non-negative random variable X, the Hoover index is defined as
H(X) = 1/ FF (p) So (T) dp
250 F- (p)dpp
Hoover index involves forms like 1F-- u1 for μ F (p)dp. This type of nonlinear structure can be dealt with the absolute function results mentioned in Appendix A.1.2
For Hoover index and a (1 5)-CBP (F FM Fi,,), ), let us define
(X) fo' max [ - (p) - fo pd. n.
(1) (g)dgl. F - So (g)dgllp)
2 2S p (p)dp
Then, with probability at least 8, (u X) X) is upper bound for (X)..
20

---

B.4 Extreme observations & mean range
For example, city may need to estimate the cost of damage to public amenities due to rain in certain month. The loss for each day of a month is X1. .xx i.d drawn from F, and the administration the losses in a month so that they can accurately
hopes estimate and control the dispersion allocate resources. This involves quantities such as range (max X; min Xj) or quantiles of extreme observations (ma X;). The CDF of extreme observations such as max(e(K) X; involves a nonlinear function i.e. (F(z)))
Example 7 (Quantiles of extreme observations). The CDF of maxie(M] X; is Fh: Thus, by the result of Appendix A.1.2 givee (1 CBPC (F Pá and t Fo. = Fh, = 0. with probability at least 0,
(F 3 3 = (F
We also have
(F2,0** 3 F 3 (f
Similarly, for mingem X the CDF is 1 (1 F),, thus, we have
1 1- 1- n 3 F 3 (1 12.
We also want to emphasize, even if. X is not necessarily non-negative, we can apply the polynomial method in Appendix 1.1.2 F and F
Example (Mean range). By [I3), if we further have prior knowledge that X is of continuous distribution, the mean of max X4 miijje(k] X3 can be expressed as:
k F (x) - ph (x)) = J. F (V)(L (p)) - F* (F= (p)))d
Notice that both F and F are increasing. Thus, if given a (1-8)CCB (F Fò Fr,)). F8 n. ł 0, then with probability at least 1 -, 8,
[. i (1 (D)) (F2,7)) (L.,)) (F
is an upper bound of the mean range.
There many other interesting societal dispersion measures that could be handled by framework. such as those [1). For example, they study tail share that captures "the top 1% of people own X share of wealth", which could be easily handled with the tools provided here. We will leave those those examples to readers.
C Extension to multi-ddimensionl cases and applications
We briefly discuss extending approach to multi-dimensional losses. Unfortunately, there is not a gold-standard definition of quantiles in the multi-dimensional case, and thus we only discuss functionals of CDFs and provide an example. For multi-dimensional samples (X,)=n. each of dimensions, i.e. X, = (Xi, ... Xi). for any k-dimensional vector z (æ1, , Fk), define
empirical CDF
" n
(x)
where we abuse the notation A to mean all of X, coordinates are smaller than x's. By classic DKW inequality, we have with probability at least 1-6 6.
In(k(n + 1)/8)
(x) ((()))F(x)]
2n
Meanwhile, can further adopt Frechet-Hoeffeding bound, which gives,
max (1 1 + F((x)),) < F(w) < min(Fi(z)),, ... Fx()))
21

---

where F3 is the CDF of the i-th coordinate. Then, we can construct (R F5/k() n.U such that
(F 3 F with probability at last 1 - 6/k. Thus, by union bound,
max k +
F (rx). & F(x) min ( (21), (x1,,
(xx)
A (rx))
for all with probability last 8.
have
In(k((n 1)/6)
F(x) 2 max (1 ks +
F (x)) 0,,),
2n
B8/kk (æx), Fx(x)) + [Ink((n + +1)6)
F(x)= S min f./kk11 FF (z1),
n.U
2n
with probability at last 1 28.
Example 9 (Gini correlation coefficient 34 random variable X and Y are defined as
The Gini correlation coefficient for two non-negative
SS (FxY(L,))) - (x(x)) (xdFF(())
Tx, Fo Coo(XXFx(XX) Fx(
Cxu(X,Fx(X))
where Fx, Fy are marginal CDFs of X,Y and Fx, the joint CDF One can use the multi- dimensional CDF bounds and our previous methods to provide bounds for the Gini correlation coeffiecient.
D Experiment details
This section contains additional details for the experiments in Section We set ō = 0.05 (before statistical corrections for multiple tests) in all experiments unless otherwise explicitly stated. When- perform correction for the size of the
bounding measures multiple hypotheses, hypothesis set. Additionally, when we bound measures on multiple distributions (e.g. demographic groups), also perform correction. Our code will be released publicly upon the publication of this article.
D.1
CivilComments (Section 5.1
Our set hypotheses are a toxicity model combined with a Platt scaler 22 where the model is fixed and we vary the scaling parameter in the range [0.25, 2] while fixing the bias term to O. We use a pre-trained toxicity model from the popular python library Detoxify [0 and perform Platt Scaling using code from the python library released by [8] A Platt calibrator produces output according to:
h(v) + exp (we +
where w, b are learnable parameters and is the log odds of the prediction. Thus form hypothesis set by varying the parameter w while fixing b to 0. Examples are drawn from the train split of CivilComments, which totals 269,038 data points.
The loss metric for our CivilComments experiments the Brier Score. For n data points, Brier score is calculated as:
L == Σ (1: o;)²
1=1
where f. is prediction confidence and 0, is the outcome (0 1).
22

---

D.1.1 Bounding complex objectives (Section 5.1.1
We randomly sample 100,000 test points for calculating the empirical values in Table and draw our validation points from the remaining data. We perform a Bonferroni correction on à = 0.05 for the size of the set of hypotheses as well as the number of distributions on which we bound our measures (in this case the number of groups, 4). We set À = 1.0.
Numerical optimization details (including training strategy and hyperparameters) are the same as Section 5.1.2. explained below in Appendix D.1.2 For each group we optimize the objective
O (P2) + (FFg))
where , is the CDF bound for group, Tj is expected loss, and T3 is smoothed version of median with a = 0.01 (see Appendix D.1.2 and Figure 5
For comparison, the DKW inequality is applied to get a CDF lower bound, which is then transformed an upper bound via the reduction approach in Section 4.1.1 To get the lower bound b/ we set:
# points $
log(3 :
6/ max(0, (0,
n
2n
D.1.2 Numerical optimization examples (Section 5.1.2)
We parameterize the bounds with fully connected network with 3 hidden layers of dimension 64. The n gaussian seeds are of size 32, which is also the input dimension for the network. Training performed in two stages, where the network is first trained approximate Berk-Jones bound, and then optimized for some specified objective O. In both stages of training we aim to push the training error to zero or as close as possible (i.e. "overfit"), since we are optimizing bound and do not seek generalization. The model is first trained for 100,000 epochs to output the Berk-Jone bound using a mean- -uearrd error loss. Then optimization on O is performed for a maximum of 10,000 epochs, and validation is performed every 25 epochs, where we choose the best model according to the bound on O. Both stages of optimization use the Adam optimizer with a learning rate 0.00005, and for the second stage the constraint weight is set to À = 0.00005. We perform post-processing to ensure the constraint holds (see Section A.2.2). For some denominator m (in our case m 10%) we
set 2 3 and check the constraint until it is satisfied.
This approach is applied both the experiments in Section 5.1.1 and Section 5.1.2
Details on the DII.1 In Section 5.2 we set ò = 0.01 and our
objective for Section 1. are above in Appendix D.I.1 metries for optimization are described below:
CVaR CVaR is a measure of the expected loss for the items at or above some quantile level B. We set 0.75, and thus bound the expected loss for the worst-off 25% of the population.
VaR-Interval the event that different stakeholders are interested the VaR for different quantile levels 88, we may want to select a bound based on some interval of the VaR [Smin: Smar]. We perform our experiment with Amin = 0.5, 3.ma = 0.9, which includes the median (3 = 0.5) through the worst-case loss exluding small batch of outliers (3 = 0.9).
Quantile-Weighted We apply a weighting function to the quantile loss (p)) = p. such that the loss incurred by the worst-off members of a population are weighted more heavily.
Smoothed Median We study more robust version of a median:
1 a
(p 3)
(p:
exp(
a²
with 3 = 0.5 and a = 0.01, similar to normal distribution extremely concentrated around its mean. See Figure 5 for illustration of such weighting.
D.2 Bounds on standard measures (Section 5.2
This section contains additional details for the experiments in Section 5.2
23

---

0.399
0,500
6502
p
Figure 5: Plot smoothed median function with 3 0.5 and = 0.01
D.2.1 RxRx1 (Section 5.2.1
We use the code released by [7 to pre-train a model on the train split of RxRx1 [31] and we evaluate algorithm the OOD val split with 9854 total samples. We randomly sample 2500 items for use in validation (bounding and model selection). and use the remainder the data points for illustrating the empirical distribution induced by the different hypotheses. The thresholds which are combined with the pre-trained model to form our hypothesis set are evenly spaced in [-8, 0] under the log transformation with base 10, thus leaving the thresholds in the range [10-8, 1].
Balanced accuracy calculated as:
I(Ý, = =1 (Sens((Y, Y) + Spec(Ý, Y)), where
Sens(Ý. Y) Y nyl and Spec(Ý, Y) k Y Y
Y
k Y
where Y the set of ground truth labels (which in this experiment will always be one label), y is set of predictions, and is the number of classes.
D.2.2 MovieLens-1M (Section 5.2.2
MovieLens-IM IM [12] is publicly available dataset. We filter all ratings below 5 stars, typical pre- pre-processing step, and filter any users with less than 15 5-star ratings, leaving us with 4050 users. For each user, the 5 most recently watched items added to the test set, while the remaining (carlier) items are added to the train set. We train a user/item embedding model using the popular python recommender library LightFM with WARP ranking loss for 30 epochs and an embedding dimension of 16.
For recommendation set f we compute loss combining recall and precision against user test set of size k:
L= ol, (f,1) - (t) where
4(,1))= =1
Σ 1 and (f,1)) 1El
= =1 I(ien)
ief
where a 0.5. We randomly sample 1500 users for validation, and use the remaining users to plot the empirical distributions. The 100 hypotheses tested are evenly spaced between the minimum and maximum scores of any user/item pair in the score matrix.
hacrppr//gtthab.mmmmp-lllbbbbbbp
24

---

E
Additional results for numerical optimization (Section 5.1.2)
Figure compares the learned bounds Gopt to the Berk-Jones (GBJ) and Truncated Berk-Jones (G (GBJ-1 bounds, as well as the empirical CDF of the real loss distribution.
CVaR
VaR Interval
1.0
Femp
1.0
Fenp
0.8
Gypt
0.8
Gipt
Gaj
Otj-1
LOSS
0.6
Git-t
0.4
0.5
0.7 0.8
8 0.9
1.0
0.5
0.6 0.7
0.8
0.9
B
Figure 6: Learning tighter bounds functionals of interest for protected groups. On the left, bound is optimized for CVaR with 3 = 0.75, and on the right a bound is optimized for the VaR Interval [0.5, 0.9). In both cases the optimized bounds are tightest on both the target metric well as the mean, illustrating the power of adaptation both to particular quantile ranges as well as real loss distributions.
25


Reviews:
[{"review_id": "Jy2fE0uPoi", "reviewer": "Reviewer_DzT2", "summary": "The paper proposes a methodology for distribution-free confidence intervals for a wide class of dispersion measures. This is motivated by validating the performance of machine learning algorithms with respect to more complex notions of performance, such as group-based measures of loss balance or the Gini coefficient of the allocation of the losses. This paper studies the problem in more generality than previous work, which focused on losses that are empirical means of quantities or quantile-based risk measures. The paper demonstrates the proposed methodology on several solid benchmark tasks.", "questions": "Theorem 1 seems like the technical core. Is this impression correct? If so, more commentary about the functions f_1 and f_2 would be helpful. These exist in principal, but for which cases are they actually tractable?\n\nThere is currently some notational pain with the overloading of \\xi. Sometimes it is a function R to R, sometimes it is a functional. 4.1 is titled \"Control of nonlinear functions ...\" but then starts off with \"xi(F^-) which maps F^- to another function of R\", which is interpretting it as a function. However, later on it is said that xi is monotonic, which is invoking the interpretation of xi as a function R to R rather than a function. Similarly, 4.2 is about \"control of nonlinear functionals\" but then in the integral expression in line 183, F^- is evaluated at alpha, which means this expression is uses \\xi as a function, not functional.  I don't doubt that it's all correct, but it was hard for me to read at first. It would help the object \\xi is defined explicitly somewhere, so that exactly what type of object (function vs functional) it is is stated. \n\nMinor:\n-- Berk-Jones and DKW should be cited.\n-- I know of two other references in the conformal prediction literature that use uniform bounds on the CDF like Berk-Jones; https://arxiv.org/abs/2104.08279 and https://arxiv.org/abs/2304.06158 . These works are somewhat technically related, although I understand the use of the bounds on the loss distribution is conceptually different than using the bounds on the conformal score function.\n\n", "limitations": "The authors do a good job explaining the context and limitations of their work. I would say the main limitation is that these techniques (like most techniques in this field) do not handle distribution shifts, and are assuming an iid data sample. This is explicitly addressed in the conclusion.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The problem is well-motivated, and the need for such guarantees about (dispersion) risk measures is convincing. Such techniques would help audit and verify aspects of the performance of machine learning algorithms. I find the introduction and abstract to be clear and set the scene well.\n\nThe work involves some non-trivial mathematics, and it is a formidable technical extension of previous work. A reader of previous work would not be able to apply it to the risk measures studied herein without this manuscript.\n\nThe examples are serviceable and demonstrate the breadth of the proposed method.\n\n", "weaknesses": "My main concern is with the technical presentation in Section 4. I am fairly knowledgeable about this literature, but I still found it challenging to read at first. The authors have a lot of technical content to cover with limited space, so right now much of it is deferred to the appendix. I understand that this is challenging, and I appreciate all the work that has gone into this draft. Nonetheless, I hope this can be improved in the next iteration. In general, my opinion is probably too much content for the amount of space that is currently allocated, so perhaps more space can be made for this section.\n\nMy first suggestion is that the authors state the desired property of the output of their algorithm explicitly at the beginning of Chapter 4 or perhaps earlier -- if I understand correctly the goal is to give a 1-delta confidence interval for some risk measure. The output of the algorithm is this confidence interval. This is in contrast to some other works in risk control and conformal prediction, where the output of the algorithm is a choice of a parameter that controls the coverage rate or other risk level. When the authors of this work use the word \"control\" in the abstract and at various other points, I was initially confused as to what they meant. \n\nSecondly, it's not immediately clear what the proposed algorithm is when reading section 4. The section seems quite compressed, and as a result the reader is left with a lot of work to put together the pieces from the relatively lean presentation. I would find it helpful to see an algorithm environment or pseudocode explaining exactly the steps to compute the upper bound for at least one of the cases considered.\n\nIt goes without saying that when it comes to presentation choices, it is somewhat a matter of taste. I understand the authors may wish to go a different direction than my suggestions above. Still, iterating on this initial draft would be very helpful. In good faith, I'm giving the paper a score of \"7\" in anticipation that the final version incorporates some improvements to the presentation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and overall positive feedback. Here, we provide answers to your concerns and questions point by point.\n\n**C1:**...main concern is with the technical presentation in Section 4...have a lot of technical content to cover with limited space, so right now much of it is deferred to the appendix...\n\n**A1:** Thank you, we agree with your assessment of this section and plan a significant revision.\n\n**C2:** My first suggestion is that the authors state the desired property of the output of their algorithm explicitly at the beginning of Chapter 4...if I understand correctly the goal is to give a 1-delta confidence interval for some risk measure...This is in contrast to some other works in risk control and conformal prediction, where the output of the algorithm is a choice of a parameter that controls the coverage rate or other risk level.... \n\n**A2:** We use the term control in the same way as these other works -- our framework can be applied to choose a hypothesis that best controls some risk measure. We will clarify this in the revision. We would like to point out a distinction between how we exercise this control versus other recent approaches, notably ``learn then test\" [1]. In both, as you state, the most important step is to provide a ($1-\\delta$)-confidence upper bound for some risk measure for a given hypothesis $h$.\nIn [1] they first fix a risk level $\\alpha$ and output all hypotheses whose risk (their risk is defined as the mean of some loss function) is upper bounded by $\\alpha$.\nOur algorithm iterates over all members in $\\mathcal H$ and selects a hypothesis $h$ corresponding to the smallest risk upper bound. But we our framework can naturally be used in their setting since we also obtain bounds for risks and those bounds hold simultaneously for all hypotheses with high probability.\n\n[1] Angelopoulos et.al. ``Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control.\"  \n\n**C3:** ...it's not immediately clear what the proposed algorithm is when reading section 4. The section seems quite compressed, and as a result the reader is left with a lot of work to put together the pieces from the relatively lean presentation. I would find it helpful to see an algorithm environment or pseudocode...\n\n**A3:** Thanks for the great suggestion to summarize our algorithm in pseudo-code -- we will include this in our revision. Our algorithm can utilize any method that produces high probability two-sided bounds for the underlying CDF, where Berk-Jones and our numerical optimization bounds are two examples. The pseudo-code will make this clear.\n\n**C4:** Theorem 1 seems like the technical core. Is this impression correct? If so, more commentary about the functions $f_1$ and $f_2$ would be helpful. These exist in principal, but for which cases are they actually tractable?\n\n**A4:** You are right that Theorem 1 is one of our main results. This result can extend existing results in the literature to bound the loss beyond means and quantile-based risks. \nWe have a formal version of Theorem 1 in Appendix line 513-517.\n$f_1$ and $f_2$ are quite tractable, under mild assumptions. For example, if $\\xi$ is continuously differentiable, $f_1(x)=\\int^x_0|\\frac{d\\xi}{ds}(s)|ds$ and $f_2(x)=f_1(x)-\\xi(x)$.\n\n**C5:** There is currently some notational pain with the overloading of $\\xi$......Berk-Jones and DKW should be cited...\n\n**A5:** Thanks for your other suggestions for revisions and notation clarifications. And for the pointers to missing citations. We will include these in our revision.\n\n"}, {"review_id": "T9WNivkUzI", "reviewer": "Reviewer_6JyR", "summary": "Given a trained predictor, this paper proposes a framework for bounding various measures of dispersion of the loss distribution.\n\nThe approach taken here is similar to that of conformal prediction, where one uses a calibration set to estimate the distribution of the loss. In this paper, the authors use the empirical CDF of the loss function on the calibration set to build confidence bands for the true (unknown) CDF. These confidence bands can then be used to obtain bounds on the dispersion measure of interest.  This approach is demonstrated on several measures of dispersion: Gini coefficient, Atkinson index, difference of group medians, and others.\n", "questions": "* In many applications, one is given a finite dataset to work with. In which case, under the current paper's framework there is a need to decide how to split the data into a primary training set and an additional calibration set (which the authors refer to as validation set, however this term is different from that used in relation to cross-validation). Are there any guidelines that you can provide on this matter? e.g. minimal size of the calibration needed set to achieve a certain error.\n\n* Using a fully-connected NN to parameterize the confidence boundaries in the optimization seems like overkill. I suggest that the authors try a much simpler parameterization, such as low-degree polynomials or using the first few elements of a Fourier series. This should be sufficient to express any smooth boundary accurately and is likely to converge faster due to the smaller number of parameters.", "limitations": "* This paper only considers one-sided confidence bands for the CDF and the bounds on dispersion that result from them. In some cases it may be sensible to consider two-sided confidence bands but this point is not discussed in the paper. It seems that the repeated integration method for one-sided bands on which this paper is based can only be used for computing one-sided bands. I think this limitation should be at least mentioned.  One could approximate a two-sided 1-alpha level boundary by combining an upper and lower band at the level of 1-alpha/2. However, this is not optimal (and is also not mentioned in the paper). Note that there are methods in the literature that compute two-sided confidence bands for the CDF that are based on similar ideas and they could be incorporated in some manner into the framework presented in the paper (but this is too much to ask for in a revision!).\n\n* Distribution shift is not mentioned anywhere, though I don't see this as a clear limitation of the proposed framework. Depending on the type of distributional change, one might be able to construct wider confidence bands that take it into account.\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* This paper addresses an important class of problems.\n* The proposed methodology has a broad scope as it is applicable to any ML system and any data distribution (so long as it is i.i.d. and no distribution shift has occurred).\n* The method should be easy to incorporate into standard ML packages and workflows. Thus, it has a high potential impact on ML practice.\n* In terms of originality, this is a moderate contribution and seems mostly like a follow-up paper to [1]. However its applicative focus is sufficiently different. Also, it contains some technical novelty. Chiefly, the gradient-based optimization approach for the construction of tight confidence bands for a given dispersion measure.\n* On the experimental front, the proposed approach is demonstrated on a diverse set of dispersion measures and data sets, showing its real-world applicability.\n\n[1] Jake Snell, Thomas P Zollo, Zhun Deng, Toniann Pitassi, Richard Zemel. \"Quantile Risk Control: A Flexible Framework for Bounding the Probability of High-Loss Predictions\" ICLR (2023).\n\n", "weaknesses": "The results in this paper are based on the construction of confidence bands for the CDF of the loss and in particular on the use of goodness-of-fit statistics for the construction of these bands. This idea is well-known in the field of statistics and the authors should do a better job of connecting with that literature. In particular, the paper [2] from 1995 proposed constructing confidence bands for the CDF using the Berk-Jones statistic, just like the baseline used in the current paper, but is not cited.\n\nMinor points for improvement:\n1. The fonts used in the figures are a bit small.\n2. The notation in Section 2 is confusing. I believe it would be better to use the standard notation: X for inputs and Y for outputs. Z can be used for loss(h(X),Y).\n3. The last paragraph of Section 3 is a bit much. Consider breaking it down and providing specific simple examples for clarity.\n4. Page 4, line 139: a space is missing in \"measures.They\"\n\n[2] Art Owen. \"Nonparametric likelihood confidence bands for a distribution function\". Journal of the American Statistical Association (1995)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive suggestions and overall positive feedback. We will revise our paper according to your helpful suggestions and will include the important citations we missed. Here, we provide answers to your other concerns point by point.\n\n**C1:** In many applications... under the current paper's framework there is a need to decide how to split the data into a primary training set and an additional calibration set (which the authors refer to as validation set... are there any guidelines that you can provide on this matter? e.g. minimal size of the calibration needed set to achieve a certain error.\n\n**A1:** While data splitting was an important issue in some older work in Conformal Prediction, we adopt the setting used in most recent work in distribution-free uncertainty quantification (DFUQ) [1,2].  In this setting, we start with a pre-trained blackbox model, and only need to use a validation dataset to calibrate and choose a hypothesis (for example, a threshold), without considering the training process for the blackbox model. \n\n[1] Snell et. al. \"Quantile Risk Control: A Flexible Framework for Bounding the Probability of High-Loss Predictions.\"\n\n[2] Angelopoulos et.al. ``Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control.\"\n\n**C2:** Using a fully-connected NN to parameterize the confidence boundaries in the optimization seems like overkill. \n\n**A2:** Thank you for the suggestion.  We implemented a polynomial model with different levels of complexity for comparison.  For $L_1,L_2,..., L_n$, we sample $n$ one-dimensional Gaussian seeds denoted as $s_1,s_2,...,s_n$. Then:\n$\\phi_{\\theta}(s_i)=\\theta_0+\\theta_1 s_i + \\theta_2 s_i^2 + ... + \\theta_k s_i^k.$\n\nResults with the polynomial model after some hyperparameter tuning are reported in Table 1 in the PDF attached in the aruthor rebuttal.  Overall we see mixed performance from the polynomial parameterization.  It produces the best bound on the smoothed-median metric, and performs better than Berk-Jones on CVaR.  However, it fails to produce a better bound than Berk-Jones for the other two metrics.\n\nOverall, we find the neural network to be easy to implement and optimize -- importantly, the same set of parameters are used for learning bounds on all target metrics in Sections 5.1.1 and 5.1.2.  Further, the networks can be trained in a few minutes on a single small GPU. While other parameterizations are possible, and sufficient hyperparameter tuning may lead to better performance across the board for the polynomial method, we believe the neural network is a good choice based on the robust results it produced in our experiments and the reasonable compute and memory costs.\n\n**C3:** This paper only considers one-sided confidence bands for the CDF and the bounds on dispersion that result from them...\n\n**A3:** Our framework indeed can provide two-sided bounds. This is illustrated in \nFigure 1, where we plotted two-sided bounds for Lorenz curve. Lemma 1 converts the lower bound of CDF obtained by [1] to an upper bound; both bounds hold simultaneously without incurring any inflation factor. We will clarify this in the revision.\n\n**C4:** Distribution shift is not mentioned anywhere, though I don't see this as a clear limitation of the proposed framework...\n\n**A4:** We did mention the assumption of consistency of the validation and test distributions as a limitation of the work. We agree that this is an important consideration.\n\n\n\n\n\n\n\n\n"}, {"review_id": "RRTEGt1oLh", "reviewer": "Reviewer_Jihe", "summary": "The paper demonstrates how to give distribution-free probabilistic control of certain statistical dispersion measures that are relevant in societal applications. An example is the GINI coefficient.\n\nThe paper technically builds on and slightly extends the work of Snell et al., which shows how to control quantile-based risk measures.", "questions": "N/A, just let me know if I have misunderstood anything above.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Congratulations to the authors on the great paper. It is the best in my batch of 6.\nI am familiar with the line of work on quantile-based risk measures, and am happy to see it used in such an interesting application domain.\nThe GINI coefficient and friends are a unique set of application domains, with large practical importance. Though I do not necessarily see large methodological novelty from the statistical point of view in this paper, I do believe that it has the potential for large impact in the social sciences (politics/economics, etc.) if the techniques are adopted.\n", "weaknesses": "I will be an advocate for the paper's acceptance, but I would really encourage the authors to do a major rewrite during the revision stage. The writing and presentation needs work, in my opinion.\nI have taken careful notes below. They are a bit stream-of-consciousness, so please forgive me for the tone.\n\nWRITING FEEDBACK:\n\nSection 4 reads really strangely to me right now.\nIt contains essentially no technical content, but is written in a technical way.\nIt’s more of an advertisement for the appendix. But it is vague, so I do not understand what has been proven, and what technical tools were used to do that until after I read the appendix (which 99% of your readers will NOT do).\nE.g. Under “Control for absolute and polynomial functions” you say “we can control these” but don’t give a formal statement saying what that means. Also, is it a corollary of some main result, or is it a bespoke proof? We don’t know until we read the appendix.\nFor that reason, I’m not really learning anything from section 4 as a reader, which is not good.\nIf you need to make space, cut 4.3 which is not important for main text.\n There are many places where the math just doesn’t make sense, and false statements are made, which makes the paper confusing. (To be clear, I believe all the statements are formally true, but not always for the reason given.) Examples:\n(1) “building blocks mentioned above as linear functionals of J: (i) nonlinear functions of J, i.e. \\xi(J)”. What is this supposed to mean? J represents either F or F^- so \\xi is a functional, not a function right? And you’re saying it’s nonlinear, so how can it be linear? As a side note, this “building blocks” section really didn’t work for me in terms of clarifying the later examples. It is so mathematical! Who are you writing for, a theorist, an applied statistician, or a social scientist? You have to decide, because the latter does not know what a function of a functional is, and the middle one doesn’t care and will probably be turned off by that language in my honest opinion.\n\nAs an alternative, just say that you are trying to control “functions of a whole CDF, like the GINI coefficient.” You can delineate the exact distinctions later when you’ve already made your main piont. “nonlinear function of a functional” and similar language is definitely distracting, not helping.\n\n(2) Under “Control for a monotonic function”, this does not hold because of Proposition 1. Proposition 1 is a deterministic statement, and you need Proposition 3 to make the probabilistic statement. This is confusing because it is obviously false to say that “by proposition 1 you have X with probability 1-\\delta”.\n\n(3) The statement of Proposition 3 is false. The second line holds only with high probability.\n\n(4) In Appendix C, it’s not “By classic DKW inequality” — it should say “By the classic DKW inequality and a Union bound/Bonferroni correction” because the classic DKW inequality does not have a k in it. Also, I find this subsection uninteresting and would consider greatly shortening it by just stating “you can use Bonferroni correction” and then giving the example.\n\nThe paper strikes a strange balance of being needlessly complex while presenting almost no theoretical detail in the main manuscript. It is fine to defer the most general form to the appendix, but in my honest opinion, the hybrid that is happening now is not very effective. Here are a few suggestions and places where I think the writing is ineffective.\n\n(1) Simplify superscripts and subscripts. The letter “F” gets way too many superscripts/subscripts/hats. It is hard for an unfamiliar reader to keep track of what’s happening. But it can be simplified with essentially no loss: for example, because you never write F_{n/2} or F^{delta/2} at all in the main paper, it suffices to remove those scripts entirely.\n\n(2) Remove technical minutiae. Remark 1 can be removed and the same point can be made as a half-sentence somewhere. Don’t use J as a generic notation for F or F^-, it’s very confusing. \n\n(3) I would add at least one actual technical result in the main body of the paper. Everything is in the appendix right now. I definitely respect the reasoning behind that choice, but right now it really isn’t working. The reality is that the paper is very mathematical, but without some clear theoretical statement (Theorem 2 from appendix would suffice), it’s not clear what the main result is and why it works. Furthermore, things like Proposition 1 do not help. Proposition 1 is obvious (does not require proof) and it isn’t directly connected to any of the claims you make in the paper. It should definitely be in the appendix. Whereas Theorem 2 is your main hammer, so you should highlight it. And you should explicitly state somewhere that the \n\nThe sentence starting with “Roughly speaking, a function of bounded total variation…” is totally out of place given how technical the previous parts of the section have been.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We really appreciate your careful examination, thoughtful and overall positive feedback. We will address your comments below.\n\n**C1:** ...I would really encourage the authors to do a major rewrite during the revision stage. The writing and presentation need work...\n\n**A1:**  Thank you for your suggestions on presentation, in particular with respect to Section 4. We agree with your assessment of this section and plan a significant rewrite incorporating the suggestions.\n\nMeanwhile, for $\\xi$, we realize that our formulation can be confusing. $\\xi$ can be viewed as a function of $F$ or a function of $F(x)$ for some fixed $x$. If we view $\\xi$ as a function of $F$ that induces $\\xi(F(\\cdot))$, then it is a function of a function, i.e. a functional. But $\\xi$ is also a mapping from $R$ to $R$ once we fix an input $x$ and view $F(x)$ as a scalar. We will rewrite and clarify this point.\n\n\nWe will also add $1-\\delta$ in proposition 3 and simplify the subscripts and superscripts for estimators of $F$ in different cases. Again, thanks for your careful examination! As for Appendix C, we indeed should say ``by classic multi-dimensional DKW inequality in [2]\". Appendix C meant to say we should take the best between multi-variate DKW and Frechet-Hoeffeding bounds and we will shorten that as suggested.\n\nLastly, for a general answer, we agree with all the points brought up. Specifically, we agree that Section 4, for example, Section 4.1 is written in a hand-waving way because we put all the details in Appendix. We are also grateful for your suggestion about removing remark 1 and writing out the formal statement of Theorem 1 in a technical and formal way as suggested. These will all be reflected in our revision.\n\n[2] Naaman et. al. \"On the tight constant in the multivariate Dvoretzky–Kiefer–Wolfowitz inequality\" "}, {"review_id": "c7RIN3ec98", "reviewer": "Reviewer_21Hg", "summary": "This study extends the literature on distribution-free uncertainty quantification by providing bounds for various statistical dispersion measures, particularly those commonly employed in fairness evaluations of algorithms. The authors enhance the theoretical foundation by introducing additional results that allow bounding any functions with bounded total variation on the cumulative distribution function (CDF). Additionally, they propose a numerical optimization technique that achieve tighter bounds than previous methods. Empirical experiments validate the effectiveness of these tighter bounds and their relevance to ensuring fairness in model selection.", "questions": "See weaknesses +:\n\n* I understand that the numerical optimization gives tighter bounds, but how do you ensure that these bounds are valid?", "limitations": "Limitations were adequately addressed by the authors.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses an existing gap in the literature on bounding other functions of the observed loss of an algorithm beyond means and QRBMs [1]. This is particularly relevant in the case of group-based measures that often appear in fairness analyses. The technical results that enable this are insightful and the proposed numerical optimization algorithm looks promising. The comprehensive empirical evaluation of the proposed methodology is commendable and provides valuable insights.\n\n[1] Jake C Snell, Thomas P Zollo, Zhun Deng, Toniann Pitassi, and Richard Zemel. Quantile risk control: A flexible framework for bounding the probability of high-loss predictions. arXiv preprint arXiv:2212.13629, 2022.", "weaknesses": "1. Significance\n\n\tI am a bit torn on the significance of this contribution. The contribution is two-fold: provide the theoretical underpinnings for bounds of other types of functions on the CDF and provide a numerical optimization method that gives tighter bounds than the truncated Berk-Jones introduced in [1]. However, the technical results are not particularly insightful or novel and the bounds provided by the numerical optimization are comparable with the truncated Berk-Jones ones. On the other hand, the immediate relevance to fairness applications is noteworthy and this practical relevance alone makes the work valuable and suitable for presentation at the conference.\n\n2. Paper structure\n\n\tThe writing in its current form lacks sufficient focus and intuition. The authors include many results in the main paper, while relegating most of the technical and experimental insights to the appendix. Consequently, the paper becomes excessively dense in certain sections. To address this, I would suggest narrowing the focus to a select few measures and demonstrating how the novel results apply, while providing intuitive explanations. The remaining measures could be included in the appendix. Similarly, a more extensive discussion on the numerical optimization method would greatly enhance the paper's clarity. By adopting these suggestions, the paper can strike a better balance between comprehensive coverage and presenting key insights effectively.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and overall positive feedback. Here, we provide answers to your concerns point by point.\n\n**C1:** I am a bit torn on the significance of this contribution...\n\n**A1:** We agree that our main focus is to extend existing methods to address societal applications more than technical novelty.\nWe appreciate your recognition of our work's value with respect to algorithmic fairness.\n\n**C2:** The writing in its current form lacks sufficient focus and intuition...\n\n**A2:** We agree that our presentation of the material needs to be revised to better balance clarity and technical depth. Thanks for the suggestion about narrowing the focus and also discussing the numerical method more extensively. These will all be reflected in our revision.\n\n**C3:** I understand that numerical optimization gives tighter bounds, but how do you ensure that these bounds are valid?\n\n**A3:** Thanks for bringing up this point. We addressed this important question in the main paper but will highlight it in the revision. In lines 218-219 we have a post-processing procedure to ensure the bounds are valid. In Appendix A.2.2 between line 558-565, we provide details on how to post-process. This can be implemented simply via a binary search.\n"}]

Author rebuttal:
We thank all four reviewers for their constructive and positive feedback, and for thinking our paper addresses important applications, has the potential for significant impact on social science, and addresses existing gaps in the literature on bounding the observed loss beyond means and quantile-based risks.

We are very grateful for the extensive useful suggestions on how to improve the presentation, especially for Section 4.  Although we cannot upload a revised draft during the rebuttal phase due to the NeurIPS policy, we plan to modify our paper accordingly. We also address concerns (**C**) and provide our answers (**A**) for each reviewer individually below.

In addition, we attach a PDF for extra experimental results.

Meta-review: All reviewers agree that the paper makes a substantial and interesting contribution to the area of construction distribution free confidence intervals for a class of practically important problems.
Decision: Accept (spotlight)