On the Epistemic Limits of Personalized Prediction
Authors: Lucas Monteiro Paes
Carol Xuan Long
Berk Ustun
Flavio Calmon
Venue: NeurIPS 2022 Accept (2022)
Keywords: Fairness
Accountability
and Transparency
Information Theory
Predictive Models

Abstract: Machine learning models are often personalized by using group attributes that encode personal characteristics (e.g., sex, age group, HIV status). In such settings, individuals expect to receive more accurate predictions in return for disclosing group attributes to the personalized model. We study when we can tell that a personalized model upholds this principle for every group who provides personal data. We introduce a metric called the benefit of personalization (BoP) to measure the smallest gain in accuracy that any group expects to receive from a personalized model. We describe how the BoP can be used to carry out basic routines to audit a personalized model, including: (i) hypothesis tests to check that a personalized model improves performance for every group; (ii) estimation procedures to bound the minimum gain in personalization. We characterize the reliability of these routines in a finite-sample regime and present minimax bounds on both the probability of error for BoP hypothesis tests and the mean-squared error of BoP estimates. Our results show that we can only claim that personalization improves performance for each group who provides data when we explicitly limit the number of group attributes used by a personalized model. In particular, we show that it is impossible to reliably verify that a personalized classifier with $k \geq 19$ binary group attributes will benefit every group who provides personal data using a dataset of $n = 8\times10^9$ samples -- one for each person in the world.

On the Epistemic Limits of Personalized Prediction
Lucas Monteiro Paes* Harvard SEAS lucaspaesßg harvard.edu
Carol Xuan Long
Harvard SEAS
carol_longeg, harvard.edu
Berk Ustun
Flavio P. Calmon
University of California, San Diego berk@ucsd.edd
Harvard SEAS
flavio8seas harvard. edu
Abstract
Machine learning models often personalized by using group attributes that encode personal characteristics (c.g., sex, age group, HIV status). In such settings, individuals expect to receive more accurate predictions in return for disclosing group attributes to the personalized model. We study when we can tell that a personalized model upholds this principle for every group who provides personal data. We introduce a metric called the benefit of personalization (BoP) to measure the smallest gain in accuracy that any group expects to receive from personalized model. We describe how the BoP can be used to carry out basic routines to audit personalized model, including: (i) hypothesis tests to check that personalized model improves performance for every group; (ii) estimation procedures to bound the minimum gain personalization. We characterize the reliability of these rou- tines in finite-sample regime and present minimax bounds on both the probability of error for BoP hypothesis tests and the mean mean-squares -quared eгтоr of BoP estimates. Our results show that we can only claim that personalization improves performance for each group who provides data when we explicitly limit the number of group attributes used by personalized model. In particular, we show that it is impossible reliably verify that personalized classifier with will benefit every group who provides personal data using dataset of = 8 10 samples one for each person in the world.
binary group attributes
Introduction
Machine learning models often assign predictions on the basis of group attributes that denote personal characteristics. In medicine, for example, clinical prediction models account for characteristics that may protected (e.g., sex), sensitive (e.g., HTV status), or costly to acquire (e-g., presence of malignant tumor as determined via a biopsy) [3, 32]. Unlike lending or hiring, models that use personal characteristics in such applications are not subject to scrutiny due to an assumption that everyone would benefit from more accurate model [7, 31, 33]. In an effort to develop models that are as accurate as possible, practitioners use every piece information to maximize predictive accuracy over heterogeneous population.
The prevalence of machine learning models that use personal characteristies reflects belief that personalization will produce uniform gain in performance across all groups. In effect, individuals who provide personal data to models expect more accurate predictions in return. In practice, however,
"qqual contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

TRAINING DATA
AUDITING DATA
Group
A(hy))
R(hha)
R(ha)
R(hy)
R(h))
R(ho))
A((h)) R(A,))
Female, HR
4,989
15.6%
15,4%
-0.2%
5,072
15.0%
14.7%
-0.3%
Panala, W,
10.9%
0.6%
10.3%
Nale, Ny NR.
1,331
21 21
20.2%
-1.0%
1.292
20.7%
20.2%
-0.5%
Fenale, B.
16. 1%
15.6%
-0.5%
399
16.0%
15.3%
-0.8%
Famala, aWW, R.
265
21.1%
22.3%
1.1%
248
20.6%
19.4%
-1.2%
Hale, 10w, R.
587
25. 0%
23.0%
-2.0%
667
24.4%
21.6%
2.8%
Malle Wy NR
15,012
7%
22.0%
0.2%
14,939
21.1%
21.5%
0.4%
Halo, W. R
1,141
20.9%
23.0%
2.1%
1.158
19.3%
22.15
2.8%
Total 24,720
20.0%
20.1%
0.1%
24,720
19.3%
19.5%
0.2%
Table 1: Personalized models may not assign more accurate predictions for every group who provides personal data. Here, we show this effect for personalized classification task on the UCI Adult dataset [19] with three group attributes: Sex Race Immi Emmigratiin www.giintttttttu..m an [Female Male] x (White, NonWhite) x (Res ident, NonResi dent)... ). We fit personalized logistic regression model with a one-hot encoding of the group attributes hy. We then measure the gains to personalization with respect to a logistic regression model trained on dataset without group attributes - i.e., the generic model ht. Here, f((bt)) and R(ha) are the error rates of hyp and hop and R((ha) f((h,)) is the gain from personalization. As shown, the personalized model ht improves overall accuracy but assigns less accurate predictions for specific groups (highlighted in orange). Moreover, these effects arise on the training dataset and the auditing dataset [see 31, for other examples]. Our proposed metric- the benefit of personalization flags these instances by measuring the worst-case gain attain by any group (i.c.. -2.8% for the group Male, NW, R).
models trained with personal data do not necessarily assign more accurate predictions to all those who provide it. Standard techniques for empirical risk minimization use personal characteristies to improve performance
population level. However, these gains are not uniformly distributed across the groups who provide personal data, As shown in Table I, personalization can improve performance for some groups while reducing performance for others. These instances of "worsenalization" violate the implicit promise of personalization: namely, that each group who provides personal data will receive a tailored performance improvement in return. In practice, they prevalent, hard to detect, and hard to avoid underscoring the need to measure the gains of personalization [31].
Practitioners must measure the gains of personalization whenever they train a personalized model. As shown in Table 1, one only needs to estimate performance gains relative to generic model trained without group attributes, then report these gains for each group who provides personal data. Even as this audit is easy to carry out, it may not always produce clear recommendations. The estimated gains of personalization for specific group can change drastically if we have too few samples for that group. In fact, is not possible to detect if personalization helps or hurts at the group level - and by how much- without accounting for uncertainty. In practice, estimating the gains in personalization requires sufficient samples per group. When lacking, the reported gain may be just an illusion, justification to collect personal information and use the personalized classifier that stems from statistical fluctuations due to limited samples per group or, equivalently, the use of too many features that encode personal characteristics.
In this paper, we study when we can verify if personalization works as it should i... when a model that uses group attributes improves expected performance for every group who provides personal data. We derive informatiion-hhereet bounds to characterize the reliability of testing and estimation routines in this setting. We then use these bounds to identify epistemic limits in personalization i.e. conditions under which all testing and estimation routines are too unreliable to tell if personalization improves worsens performance for each group who provides personal data. Our results can serve as rules of thumb to inform a range of stakeholders - be it model developers who wish to build models that reliably benefits all groups, to auditors who wish to verify that this is indeed the case.
The main contributions of this work include:
1.
We introduce a metric called the benefit of personalization (BoP) - to evaluate the quality of personalization in model with group attributes. The BoP represents the minimum gain in accuracy that any group can expect from personalization. Measuring the BoP can flag instances where personalized model aligns with our basic expectations of personalization. A positive BoP indicates that each group can expect to receive more accurate predictions in exchange for their personal information. In contrast, a negative BoP indicates that some groups who provide personal information can expect to reccive worse predictions in return.

---

2. We design a hypothesis test to audit if personalized model violates fair use. We pair our test with an information-thhoree
limit on the error probability that holds for any hypothesis test that audits model for fair use. A rule of thumb is that the number of samples per group should exceed the number of groups for testing error to be small.
3. We characterize the statistical limits on the Mean Squared Error (MSE) of any estimate of BoP. Our results show that we cannot reliably estimate the benefit of personalization across groups for models that use more than 25 group attributes without further assumptions on the data distribution.
Related Work We study the performance of machine learning models that assign predictions on the basis of personalized characteristics. Our goal is to flag personalized models that assign unnecessarily inaccurate predictions to groups who provide personal data. This differs from the underlying goal of existing measures of individual fairness [i.e.. "treat similar individuals similarly"; 8] and group fairness [i.e., equalize performance across groups; 9, 13J, which can be broadly viewed as measures to achieve parity [i.e.. in that they seek to equalize predictions across individuals or equalize performance across groups 34]. Although parity is an appropriate notion of faimess in applications like lending and hiring, it is less suitable for applications with different ethical principles. For example, in medieine, the relevant principles are beneficence and non- maleefieeen [2]. In such settings, imposing parity may reduce performance for groups for whom the model performs well, rather than improving performance for groups for whom the model performs poorly [15, 22, 24, 25, 28). In contrast, measuring and reporting the benefit of personalization can ensure that we use personal data in ways that improve performance for all groups without inflicting harm on specific groups.
Our results are related to a growing stream of work on auditing machine learning models [see e.g., 6, 18, 26, 27, 29, 30]. We consider setting where estimate the performance of personalized model for a large number of intersectional groups known a priori [see e.g. 5, 10]. We characterize the reliability of this task when increasing the degree of personalization in finite sample regime. Reliable verification becomes increasingly challenging in this setting. Given that number of groups grows exponentially with each additional group attribute, one needs exponentially more samples to reliably estimate the gains of personalization for each group. This is, of course, expected and the motivation behind Hebert-Johnson et al. [14), Kearns et al. [17] who characterize the computational limits when auditing models with respect to parity-based metrics like equal opportunity and statistical parity under worst-case distributional assumptions. Here, we study the phenomenon in a setting where the number of samples is finite - e.g., because we are working with a dataset that is given [see e.g.. 1, 16, 19]. In this way, we can delineate fundamental limits on how many group attributes can be used for personalization before testing and estimation become too unreliable (see e.g., Corollary and Figure 1). What is surprising about our results is that, given finite sample, the information -hhooretcc maximum of group attributes that can be collected and still used to verify for a gain in personalization is, in fact, small: with more than 19 binary attributes, is statistically impossible to test a personalized model for gain in accuracy without further assumptions on the data distribution.
2 Measuring the Benefit of Personalization
In this section, we introduce formal definitions of fair use and the benefit of personalization.
2.1 Preliminaries
We start with an auditing dataset 'D A {(x;, gi, (ix)) of i.i.d. samples from data distribution Px,c,.. Each sample consists of a vector of features x; E X' (e.g. height, weight), a vector of group attribules gi (e.g. sex, HIV status), and a class label yı E y (e.g. incidence of stroke). Group attributes partition the dataset into groups of individuals with the same personal characteristics g: g. We use to denote group, and use Pg - Px.YIGG= Vgg E G to denote its conditional data distribution.
Assume that we are given a personalized classifier that uses group attributes hp : : x g + y and a generic classifier hy : X + y that does not. We assume that these models are trained on training dataset that is independent of the auditing dataset D. The group risk (or loss) of the classifiers for group g with respect to the loss function i : y x y + R is defined as:
E [E(((()), | G
if h: X X
R(h, g)
(1)
xE) G= if h: h:X
3

---

The empirical risk R(h, g) for each group is defined as:
Σ gg (1(())). Vi)
if h: if h y.
R(,, g)
A
(2)
E Lig.=g ((((x;, g).
Fig
where "g refers to the number of samples in group g.
Individuals who provide their personal characteristics a tailored gain in performance in return. In Definition 1, we frame these expectation in terms of collective preference guarantees that ensure fair use of group attributes [see 31, 33]
personalized classifier expect to receive
Definition 1 (Fair Use of Group Attributes). The personalized classifier h2 X x G + y ensures
the fair use of group attributes for group g E G with respect to the loss function É: y x y - R if
R(hp: g) S R(ho:g). g): (X. = gl (h,
(3)
G= Vg. g'.ges Eg.
(4)
Here, conditions in (3) and (4) reflect the collective preference guarantees of rationality and envy- freeness, respectively. These conditions capture the minimal expectations a group from a personal- ized model in applications where groups prefer more accurate models. Given a personalized classifier that satisfies the rationality condition (3), the average person in group g would prefer the predictions from personalized classifier hp those generic classifier hg. Moreover, given a personalized classifier that satisfies the envy-freeness condition (4), the average person in group g would prefer the predictions personalized for their group over predictions personalized for any other group g' * g. The paper focuses on ensuring the rationality condition as it reflects minimal conditions for personal characteristics to be used in classification task.
The generic classifier hg E H. can be the empirical risk minimizer over a training dataset Derain i.e.,
ho E arg min NEW
Σ {(h(x),)).
(x.g.v)EDtnn
where H is family of classification models (e.g., linear classifiers, random forests). Equivalently, hp E H can represent the personalized model that minimizes empirical risk over a training dataset that includes group attributes. In this case, the auditing dataset D (independent of Derain) can be used to empirically test whether (No, hp) guarantees fair use.
Example. Consider classification task where the goal is predict if patient suffering from cancer will experience a remission. In this setting, generic classifier hn may only use features that readily available in electronic health record. A personalized classifier hp may use these same features along with the group attributes G TumorType {A, B, C}. Here, personalized model that violates the rationality condition for group. e.g. g (3), would mean that patients may obtain more accurate predictions without undergoing an invasive procedure. In this case, patients should be informed of this fact when weighing the decision to provide more data. Moreover, doctor may choose to only perform such invasive procedure when it is expected to produce a more accurate diagnosis regardless of the result of the biopsy.
2.2 The Benefit of Personalization
The rationality condition that fair use enshrines is not necessarily met when models are trained using empirical risk minimization. When rationality is violated, personalization may improve performance across all groups, yet reduce performance for specific groups [see Table and 31]). Ideally, personalization lead to a gain - or at least not a loss - in performance regardless of the value of the group attribute g. When this is not the case, stakeholders must be informed that providing more personal information may not necessarily lead to (average) accuracy gains.
To quantify the gain in performance across all groups, we introduce a mathematical definition for the benefü of personalization (BoP). This metric a function of the personalized classifier htp the generic classifier hg. and the data distribution. The BoP captures the minimum change in loss from using a personalized classifier across all intersectional groups defined by g E G. Equivalently, the BoP guantifies the potential violation of the Rationality constraint in Definition 1.

---

Definition (Benefit of Personalization). Given fixed data distribution Px.G,Y and generic model hgg the benefit of personalization of personalized model hp relative to generic model hg is:
Thh, hp) - min R(ho. g) - -R(hp.
(5)
KEG
We refer to R(ho, g) hpp g) as the the per-group benefit for group g, and write 7 = (ho, when the parameters are clear from context.
When the benefit of personalization is positive but small, individuals may prefer to receive predictions from a generic model hg rather than personalized model hg. This would reflect settings where the expected gain in personalization would be insufficient to warrant the cost of collecting or disclosing personal information (e.g., when the information is costly or sensitive). Testing for the benefit of personalization (e.g., if y > <) is, on its own, insufficient: stakeholders must be made aware of the estimated gain in accuracy from reporting personal data and only provide their personal data when it leads to a sufficient gain in accuracy [31, 33). However, calculating the BoP exactly requires knowledge of the data distribution (see Def. 2) - a condition rarely met in practice. Therefore, is critical to understand how estimate the BoP given an auditing dataset D, well when this estimation may infeasible given a limited sample size or a large number of group attributes.
2.3 Assumptions
In the remainder of this work, we restrict our attention to classification tasks with binary outcome )' = (0, 1), and k binary group attributes G; G {0, 13. that specify d A | 2 groups. We assume that we work with an auditing dataset ID that contains _ [n/d] samples per group. This reflects an optimistic assumption in settings without prior knowledge of the data distribution Px.G.Y. In effect, measuring the benefit of personalization is more unreliable in tasks with disparate number of samples per group (see Appendix C.3).
We consider setting where the benefit of personalization measures the minimum gain in accuracy between a personalized classifier and its generic counterpart. This corresponds to selecting the 0-1 loss function Ely, hxx.)(x)))))))))) g))
& 1yy * h(x,g) g]] in (2). The resulting quantity can be expressed as
follows:
Tho, hp) = min Pr(Y = (X,g) G = g) - Pr(Y = (x) G = G)).
REG
where Pr(Y = hpp Our results can be generalized to settings where the BoP measures the minimum gain using other performance metrics, such as the false positive rate or false negative rate (see Supplementary Material Section B.1).
G -) P (X) G = g) is the gain in accuracy for group g.
Naturally, one would expect the personalized classifier hp and its generic counterpart hy to be trained in "good faith," i.e., they are not designed to underperform on a specific group. The BoP would not capture, for example, the case where both the personalized classifier and the generic classifier underperform on specific group it only reflects the relative gain in accuracy for each group by switching to a personalized classifier. this regard, the BoP complements existing group fairness metrics.
3 Testing with the Benefit of Personalization
In this section, we describe a hypothesis testing framework to check that a personalized model produces sufficiently large gain in performance for all groups. We then present information- theoretic bound on the reliability of this procedure for all hypothesis tests.
3.1 Hypothesis Testing Setup
In Definition 3, present one-sided hypothesis test to verify if a personalized model improves expected accuracy for every group who provides personal data.
Definition 3 (Hypothesis Test for Fair Use). Given personalized classifier hy, a generic classifier ho. and auditing dataset D, we verify whether (hp, ho) yields an gain in expected accuracy for
5

---

every group using a hypothesis test where:
Ho
+
min
R(ho, g) - R(hp g) < 0
geg
H1 : 726
min
R(ho g) R(hp, 26
gEG
Here, the null hypothesis Ho holds when a personalized model hp assigns predictions that are less accurate than those of a generic model ho for one or more groups. In contrast, the alternative hypothesis H1 holds when a personalized model hp assigns predictions that produce an expected gain in accuracy of for each group.
In principle, the value of should be set the minimal gain in expected accuracy that every group should receive from a personalized model. Setting e = 0 would flag a personalized model that assigns least one group. Setting a larger positive value would cost of providing personal information.
unnecessarily inaccurate predictions flag a personalized model where at least one group experiences gain that is too low to warrant the
The hypotheses can be tested using a range of procedures, including a bootstrap test [12, 23] and McNemar test [20]. Arguably the simplest procedure is threshold test, which would require estimating the BoP as shown in Table and reject Ho if 7 > c.
In what follows, we derive a bound on the reliability of the hypothesis test in Def. 3 that holds for all procedures. For clarity exposition, we represent the inputs and output for this hypothesis test as a decision function V/ (D, hyp ho + {0, I). where (D, Ap. ho, e) == 1 [Accept Hi]. Even as the setup above assumes that >> 0, our results will apply to settings where e O. When < 0, our results will characterize the reliability of an inverted setup with Ho 7 > 0 and H1 7 S e. The parameter is set to value that is arbitrarily close to - but not since the reliability of the hypothesis test requires separation between the regions Ho and H1.
3.2 Impossibility Results for Reliable Testing
We characterize the reliability of hypothesis tests in terms of their probability of error, defined below. Definition& 4 (Probability of Error), Consider auditing a personalized classifier by testing the hypothe- ses Ho and H₃ Def. 3. Given personalized classifier hp. generic classifier hu, auditing dataset D,
and threshold gain > 0, the probability of error of hypothesis test P. is defined as:
Pe
Pr (V, hp, bo. e) 1 Ho is True) + Pr (D, hp, ho, t) = 0 H1 is True)]
Type-T
Error Error
Type-II Error
The probability of error captures both the false positive rate and the false negative rate of given hypothesis test. If the probability of error of hypothesis test exceeds 50%, then this means that hypothesis test is as reliable as the outcome of an unbiased coin toss too unreliable to allow for verification. The next theorem and the main result in this section states a lower bound on the probability of eтror when testing if the BoP exceeds
Theorem 1 (Lower Bound on Probability of Error). Consider auditing a personalized classifier hp in comparison to generic classifier he on dataset DD drawn from an (wnknown) distribution with d groups, m = [n/d] samples per group. Moreover, let P. denote the probability of error The worst-case probability of error
for a hypothesis test as in Def. 4 with fixed c c [-0.5,0.5, over all pairs of data distributions (Px,c,y, Qx.G.)) where one distribution satisfies Ho and the other H1 denoted by Px.G.y G.Y v E Ho and Qx,G. E H1, respectively and all decision functions (D,h ho: c) {0, 1} satisfies
min W
P.2 Qxc.yelh
max Px
(1 (1+ (c+ 4
Vd
The minimax lower bound on the probability of eтror in Theorem represents the worst-case performance any hypothesis test without further assumptions on the data distribution. The minimax lower bound implies that for every decision function V. there exists pair of distributions one satisfying Ho and the other H, such that the probability of error for the hypothesis test will exceed the right-hand side of (6).

---

Max. Group Attributes
Max Groups
20%
5
5
?
B
10
11
13
14
16
17
12
34
56
191
335
1k
2k
9k
17k
75k
141k
10%
11
12
10
13
1k
12k
Threshold
2%
3
3
5
7
10
11
13
36
59
203
356
1k
2k
186
2
2
2
2
2
3
4
6
6
8
9
15
22
69
118
427
761
2
2
2
2
2
10
26
42
140
243
10K 50K 100K
1M
5M
10M
10K 100K SOOK
10M
Dataset Size (n)
Dataset Size (n)
Figure 1: Epistemic limits of personalization for binary classification tasks with group attributes. We identify limits the number of group attributes (left) and number of groups (right) to reliably test if personalized classifier provides an expected gain of accuracy greater than gain for every group using dataset with points. The limits correspond largest values needed to ensure min max P. S 1/2 under Theorem 1, and are computed using the same technique as Corollary (see Appendix B.2).
Proof Sketch. The proof of Theorem constructs the lower bound for the probability error for any decision function v/ by bounding the total variation distance of two distributions (belonging to different hypotheses) that are "difficult" to distinguish. We provide the full proof the supplementary material Section B.1.
Theorem characterizes the relationship between probability of error and the number of group attributes for personalization in settings with finite number of samples. Intuitively, as the number of groups becomes larger, we have fewer samples per group, and the likelihood of erring the hypothesis test increases. Using the minimax lower bound in Theorem we can delineate fundamental limit on maximum number of group attributes that we can include a personalized model test if every group benefits from personalization without making further assumptions the data distribution. In Corollary I, we highlight this limit for an idealized scenario where the dataset contains a sample for each person on Earth. In Figure we highlight the maximum number of binary group attributes (left) and groups (right) for multiple dataset sizes and threshold gains.
Corollary (Epistemic Limit Number of Group Attributes). Consider auditing a personalized auditing dataset
classifier hp to test if it provides gain of al least D with = 8 x 102 samples i.e. one for each person on Earth. If the personalized classifier uses more than k 2 19 binary group attributes, then for any hypothesis test there will exist a pair of probability distributions Px.G.Y Ho, Qx,., H, for which the test attains a probability of error that exceeds 50%, i.e.,
0.01 to each group
#2 19
min
max P. 2 Px.crrHl Qx.,
2
Phase Transition Theorem characterizes the relationship between the minimax probability of error in testing P. in terms of the threshold gain e, the number of groups d, and data points per group m. This relationship highlights a phase transition in the reliability testing. particular, we find that probability of error exceeds 1/2 whenever the number of samples per group exceeds the number of groups (see Figure 2). In the auditing setup in Corollary 1, the minimax lower bound on P. jumps from 13% to 97%
increase the number of binary group attributes from 18 to k 19. These phenomena highlight an informative rule thumb i.e., that testing is fundamentally unreliable in settings where the number of groups exceeds the number of samples per group.
Epistemic Limits. In Corollary we have shown that for a fixed dataset size (n = x 109) and a threshold gain (e 0.01) there is a limit on the number of binary group attributes to achieve reliable testing. In Figure 1 (left), generalize this result and show how the maximum number of

---

100%
100%
Minimax Probabiitty of Error
80%
80%
Minimax Probabiilty of
60%
60%
40%
20%
10
20
50
1000
200
500
1000
15
20 25
30
Data points
(m)
Number Dinary Attributes (k)
Figure 2: Minimax lower bound for the probability of error in hypothesis test. Illustration of the minimax lower bound of probability of error in Theorem (left). For fixed number of groups d' = 141 and e 0.01, when the number of samples per group decreases the probability of error in hypothesis test goes 100%. We have, in the y-axis, max (0. lower bound 6). Illustration the minimax lower bound probability of error in Theorem I (right). For a fixed sample size n = 8 x 10 (one sample per person in the world) and varying the number of binary attributes (A)) there is a phase transition for the minimax error probability in a hypothesis test in A 19 (orange line) predicted in Corollary 1.
binary attributes for reliable testing changes with the dataset size and threshold gain. Remarkably, without any further assumption, for dataset with at most 50k samples (usual in domains such as medicine) and c = 0.01 (just 1% accuracy gain in personalization), at most 3 binary group attributes can be used in order to ensure reliable auditing for the BoP for any data distribution. The limits in Figure are violated by many algorithms used in medicine (e.g. [4, 11]). ). Figure (right) we drop the assumption of binary group attributes and show the maximum number of groups to ensure reliable testing. Note that, in general, the number of groups when we drop the binary attributes assumption bigger than the number of groups generated by the binary group attributes. This is effect from rounding - i.c., when 2 > dmax but 2fmox < dmaxx where kmax is the maximum number binary group attributes and dmax is the maximum number of groups to ensure reliable testing.
We reiterate that the error bounds in Theorem and Corollary 1 hold in the minimax sense. These bounds are conservative estimates that may be relaxed given further assumptions on the data distribu- tion Px,co G.Y Moreover, the test in Def. 3 considers only two hypotheses for pre-specified c. Hence, this testing procedure assumes priori that the true BoP y cannot satisfy 0 <<< y < In practice, such prior information about the BoP may not be known, requiring 7 to be estimated directly from an auditing dataset DD
4 Estimating the Benefit of Personalization
In this section, we characterize information -tthoorttcc limits when estimating the benefit of personal- ization. We identify threshold number of group attributes beyond which, in general, it is impossible to estimate the BoP reliably.
4.1 Estimation Setup
We consider the problem of designing an estimator > for the BoP for dataset D. Our metric of choice the mean-square ervor (MSE) E - [?}] Our goal to characterize the minimal MSE (MMSE) across all possible data distributions i.c., without further assumptions on the data distribution. In particular, corresponding bounds allow practitioners to design a dataset collection that ensures priori reliable estimation of the BoP. Therefore, we analyze the minimax estimation error i.e., the best MMSE achievable across all data distributions, defined as
A/ha, hp)
inf sup E [[>-~>")) -
7'Ea(D) Px
where 7" E (D) denotes that y" is measurable with respect the distribution Pa. Px,G, of D.
To further motivate the definition of A, suppose that there exist functions 9i (d. m), g2(d, m) > 0 such that A S g1 (d, m), and A 2 (e, m). Recall that d is the number of groups and m is the number of samples per group. This implies that for every estimator y", there exists data distribution
8

---

Px,G.Y such that G2(d, m) < [( < 91 (d, In practice, this means that for any estimator there is distribution such that the MSE of the resulting BoP estimate will be bounded away from zero by 92(d, m). The main result in this section is Theorem 2, which gives explicit expressions for 91; 92-
For dataset with a fixed amount of samples (n), when the number of group attributes increases, the number of data points per group decreases. Intuitively, the estimation variance will be higher on the "more" personalized classifier because there are fewer samples per group. Theorem 2 gives a characterization for the order of the estimation error for the BoP.
Theorem 2 (Minimax bounds for the Estimation MSE), Given a dataset DD constants d, m E N such that 4 S d S 2m+ a generie (ba) and personalized (hp) classifier, the minimax estimation error for the benefit of personalization in (7) is such that:
log(d) log(4)
log(d)
log(m)
2 log(2) m
S Shoh, hpp)
+
(8)
16m
16m
m
m
Proof Sketch. The proof of Theorem 2 relies on two-point methods for minimax lower bounds. This result uses a generalized version of Le Cam's Lemma stated in Lemma 1 in the supplementary material (which is of independent interest) together with standard concentration inequalities. We provide the detailed proof in the supplementary material and discuss its implications in Section 4.2.
The bounds in Theorem 2 are illustrated in Figure 3 (right) in log scale. This figure suggests that even though the bounds in Theorem are in the minimax sense, they are close to the estimated MSE, especially the lower bound. In addition, in Figure 3 the minimax lower bound is not a lower bound for the MSE of the BoP estimation. This phenomenon expected and is consequence of the generality the minimax bounds that hold for all decision functions and estimators and inherently consider the worst-case distribution for each case. Additional knowledge of the underlying data distribution may result in more favorable trade-off between sample size, estimation error, and the number of group attributes.
4.2 Implications of the Limits of Estimating the BoP
Theorem 2 delineates a fundamental limit on the number of group attributes to estimate the BoP reliably. The lower (converse) bound in (8) captures the trade-off between the minimax MSE of an estimator, the number of group attributes, and the size of the dataset. In Corollary 2, we express this trade-off by identifying an upper bound for the number of group attributes required achieve precise (in the minimax MSE sense) BoP estimate for a fixed sample size.
Corollary 2 (Limits of Reliable Estimation). Given dataset D with samples, d 2 4 groups, m = n/d samples per group. 0 < < 1/16, and a generic and a personalized classifier. If d < 2m+ and A(ho, hp) S 5, the number of binary group attributes (k) satisfies,
16
(k - 2)2* < In2 nō.
Remark. For n = 8 x 10 (i.e., the approximate number of people on earth) and 5 = 0.05² (i.e., most 5% MSE), then one can only reliably estimate the BoP for a personalized model with most k < 25 binary group altributes.
The proof of Corollary 2 is a direct application of the Theorem 2 (see Appendix B.5 for the proof). Setting = 0.052 caps the square root of the MSE to 5%. In settings where the estimator 7 is unbiased, the result in Corollary 2 caps the variance of the estimator to at most 5%.
Corollary 2 gives a limit in the number of binary group attributes in order to ensure a 8-precision for the error in BoP estimation - i.e., to guarantee that A A(ho, hp) S 8. Eq. 9 can help practitioners decide the number of group attributes used by hy by (i) first setting target estimation precision g for the BoP, where 0 < 8 < 1/16, then (ii) determining the maximum number of group attributes by computing kmax = max (k E N; (k: - 2)2* <
16 no}. Note that, since our bounds are minimax, this renders conservative estimate the number of attributes used for personalization.
In
In general, one may expect that the maximum number of group attributes for a reliable test should exceed the maximum number of group attributes for reliable estimation. Our results in (6) and (8) show otherwise. This is an artifact of the fact that |y| [0, 1). Easier estimation for statistics with norm smaller than is simply an artifact of scale and follows from the Le Cam Lemma [21].

---

10a
Estimate
Minimax Upper bound
Minimax Lower bound
10
MSE actimate [log]
10
10-3
Rio e5p
250 z000
Data points per group (m)
Figure 3: Overview of estimation error for the BoP of personalized classifiers on semi-synthetic dataset built from the UCI Adult dataset [19]. We plot the MSE of BoP estimates
increase the number of samples per group, along with the minimax upper and lower bounds from Theorem 2 log-scale. Here, compute each estimate using 100 Monte Carlo iterations, and show 95% confidence intervals estimated bootstrap. As shown, the MSE decreases exponentially as the number of samples per group increases. The minimax bounds are close to the estimated values, especially the lower bound, which indicates that the worst-case data distribution considered in the minimax bound is approximates the empirical data distribution. The generality of the bounds implics that some knowledge the underlying data distribution may result in more favorable trade-off between sample size, estimation error, the number of group altributes. Here, the MSE in the BoP estimate below the minimax lower bounds, suggesting that the model's 's underlying distributions for each group are not quite the worst-case scenario.
5 Concluding Remarks
Personalized models should improve performance for all individuals who provide personal data. In this work, we introduced measure called the benefit of personalization (BoP) to verify this basic principle for classification models that are personalized using group attributes. Using the BoP, we characterized the reliability of testing and estimation procedures to verify this principle in practice. We then determined conditions under which testing and estimation were too unreliable to guarantee gains across groups. Our results highlight fundamental limits in our ability to tell personalization leads to gains in finite-sample sample settings. In particular, reliably determine a personalized model with 2 19 attributes benefits all groups who provide personal data dataset with making further assumptions on the data distribution. These limits can guide how to define and select group attributes to ensure reliable testing and estimation, allowing practitioners make informed decisions when personalizing models with characteristics that are protected, sensitive, or costly to acquire.
show that there is way to
10 samples (i.e., one per person in the world) without
This material based upon work supported by the National Science Founda- tion under grants CAREER 1845852, IIS 1926925, and FAI 2040880.
Acknowledgements.
10

---

References
[1] Angwin, J., Larson, J., Mattu, S., and Kirchner, L. (2016). Machine bias.
[2] Beauchamp, T. L., Childress, J. F., et al. (2001). Principles of Biomedical Ethics. Oxford University Press, USA.
[3] Bertsimas, D., Dunn, J., and Mundru, N. (2019). Optimal prescriptive trees. INFORMS Journal Optimization, 1(2):164-183.
[4] Bochner, B., Kattan, M., and Vora, K. (2006). Postoperative nomogram predicting risk of recurrence after radical cystectomy for bladder cancer. Journal of Clinical Oncology, 24(24):3967- 3972.
[5] Cabrera, A. A., Epperson, W., Hohman, F., Kahng, M., Morgenstern, J., and Chau, D. H. (2019). Fairvis: Visual analyties for discovering intersectional bias in machine learning. In 2019 IEEE Conference on Visual Analytics Science and Technology (VAST), pages 46-56. IEEE.
[6] Cen, S. and Shah, D. (2021). Regulating algorithmic filtering social media. Advances in Neural Information Processing Systems, 34.
[7] Chen, I., Johansson, D., and Sontag, D. (2018). Why Is My Classifier Discriminatory? In Advances in Neural Information Processing Systems.
[8] Dwork, C.,, Hardt, M., Pitassi, T., Reingold, O., and Zemel, (2012). Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226.
[9] Dwork, C. and Ilvento, C. (2018). Group fairness under composition. In Proceedings the 2018 Conference on Fairness, Accountability, and Transparency (FAT* 2018).
[10] Fitzsimons, J., Osborne, M., and Roberts, S. (2018). Intersectionality: Multiple group fairness in expectation constraints. arXiv preprint arXiv:1811.09966
[1I] Friberg, L., Rosenqvist, M., and Lip. G. Y. H. (2012). Evaluation of risk stratification schemes for ischaemic stroke and bleeding 182 678 patients with atrial fibrillation: the swedish atrial fibrillation cohort study. European Heart Journal, 12033):1500-1510.
[12] Hall, P. and Wilson, S. R. (1991). Two guidelines for bootstrap hypothesis testing. Biometrics, pages 757-762.
[13] Hardt, M., Price, E., and Srebro, N. (2016). Equality of opportunity in supervised learning. Advances neural information processing systems, 29.
[14] Hebert-Johnson, U., Kim, M., Reingold, O., and Rothblum, G. (2018). Multiclibraatio: Calibration for the (computationally-deeniffff masses. In Proceedings of the 35th International Conference on Machine Learning.
[15] Hu, L. and Chen, Y. (2019). Fair Classification and Social Welfare. wrXiv:195.00/14
arXiv preprint
[16] Ingels, S. J., Pratt, D. J., Herget, D. R., Burns, L. J., Dever, J. A., Ottem, R., Rogers, J. E., Jin, Y., and Leinwand, S. (2011). High school longitudinal study of 2009 (hsls:09): Base-year data file documentation. nees 2011-328.
[17] Kearns, M., Neel, S., Roth, A., and Steven Wu, Z. (2018). Preventing faimess gerrymandering: Auditing and learning for subgroup fairness. In Proceedings of the 35th International Conference on Machine Learning.
[18] Kilbertus, N., Rojas Carulla, M., Parascandolo, G., Hardt, M., Janzing, D., and Schölkopf, B. (2017). Avoiding discrimination through causal reasoning. Advances in neural information processing systems, 30.
[19] Kohavi, R. (1996). Scaling Up the Accuracy of Naive-Bayes Classifiers: Decision-Tee -Tree Hybrid. In KDD, pages 202-207.

---

[20] Lachenbruch, P. A. (2014). Mcnemar test. Wiley StatsRef: Statistics Reference Online.
[21] Le Cam, L. (1973), Convergence of estimates under dimensionality restrictions. The Annals of Statistics,
[22] Lipton, Z., McAuley, J., and Chouldechova, A. (2018). Does mitigating ml's impact disparity require treatment disparity? In Advances in Neural Information Processing Systems 31, pages 8135-8145.
[23] MacKinnon, G. (2009). Bootstrap hypothesis testing. Handbook of computational economet- rics, 183:213.
[24] Martinez, N., Bertram, M., and Sapiro, G. (2019). Faimess with minimal harm: A pareto-optimal approach for healthcare. arXiv preprint
[25] Martinez, N., Bertran, M., and Sapiro, G. (2020). Minimax pareto fairness: A multi objective perspective. In International Conference on Machine Learning, pages 6755-6764. PMLR.
[26] Nabi, R. and Shpitser, I. (2018). Fair inference on outcomes. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32.
[27] Neil, R. and Winship, C. (2019). Methodological challenges and opportunities in testing for racial discrimination in policing. Annual Review of Criminology. 2:73-98.
[28] Pfohl, S., Marafino, B., Coulet, A., Rodriguez, F., Palaniappan, L., and Shah, N. H. (2019). Creating fair models of atherosclerotic cardiovascular disease risk. In Proceedings of the 2019 AAAI/ACM Conference AI, Ethics, and Society, pages 271 178-
[29] Raji, I. D., Smart, A., White, R. N., Mitchell, M., Gebru, T.. Hutchinson, B., Smith-Loud, J., Theron, D., and Barnes, P. (2020). Closing the ai accountability gap: Defining an end-to-end framework for internal algorithmic auditing. In Proceedings of the 2020 conference fairness, accountability, and transparency, pages 33-44.
[30] Si, N., Murthy, K., Blanchet, J., and Nguyen, V. A. (2021). Testing group fairness via optimal transport projections. In International Conference on Machine Learning, pages 9649-9659. PMLR.
[31] Suriyakumar, V. M., Ghassemi, M., and Ustun, B. (2022). When personalization harms: Reconsidering the of group attributes in prediction.
[32] Taylor, S., Jaques, N., Nosakhare, E., Sano, A., and Picard, R. (2017). Personalized multitask learning for predicting tomorrow's mood, stress, and health. IEEE Transactions Affective Computing, 222::200-213.
[33] Ustun, B., Liu, Y., and Parkes, D. (2019). Fairness without harm: Decoupled classifiers with preference guarantees. In International Conference Machine Learning, pages 6373-6382.
[34] Zafar, M. B., Valera, I., Gomez Rodriguez, M., and Gummadi, K. (2017). Fairnsss beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In Proceedings of the 26th international conference on world wide web, pages 1171-1180.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 5
(c) Did you discuss any potential negative societal impacts of your work? [Yes] The purpose of the work is create positive societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Theorem and
(b) Did you include complete proofs all theoretical results? [Yes] Check supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material as URL)? [Yes]] Check supplementary material. All codes are provided.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] Check supplementary material. All training details are specified in the code.
(c) Did report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] Check supplementary material. All plots with randomness include confidence interval bars.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Check supplementary material. All experiments run Google Collab
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No] We are using standard and public dataset
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [No] We are using standard and public dataset
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "oD3sltitPG8", "reviewer": "Reviewer_bqZa", "summary": "The authors propose a new fairness notion called benefit or personalisation(BoP), in which a personalized classifer (i.e. a classifier that is specific to subgroups) is compared to a classifier that does not use group-membership for prediction. The authors propose a hypothesis testing framework and give a lower bound on the sample complexity for successful testing. The paper then shows tight upper and lower bounds on the MSE estimation of BoP. ", "questions": "How do you pick the baseline model? How do you make sure that the baseline model is not already biased against certain subgroups?\nCan we have personalization only for groups big enough?", "limitations": "I raised some concerns in the questions part. I think some warning about choosing the baseline model is required. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "strength:\n\nI like the idea of benefit of personalisation. As a fairness consideration it makes sense and I have not seen it in the literature. \nI agree with the opinion that this should be a consideration taken into account when deploying personalized predictions\n\nI think it was a great idea to make sample sizes concrete and comparing them to the number of people currently alive. I think this made the point very effectively and might be a helpful method when analyzing sample complexities in the context of fairness or human-centric ML in general.\nThe emphasis on giving a clear message to practitioners that derives from these theorems was appreciated.\n\nThe bounds of theorem 2 are tight, making them quite informative. \n\nseveral limitations of the paper are addressed\n\nthe paper is overall well written. The related work section is sufficiently detailed.\n\nweaknesses:\n\nIt is unclear to me what h_0 is. I think this is a crucial thing to discuss. A practitioner might devise a model that (while not explicitly using group information) might be bad on certain subgroups as a comparison. Using such a model as a bad-faith comparison is currently not discouraged or addressed in the paper. I think in practice it might also be unclear how to choose the baseline model. \n\nOne might come up with a model that uses the baseline model for certain groups in which there aren't enough samples. If the models are the same for those groups this might be checked deterministically, not needing any samples for this group. Thus testing could be more efficient in such cases. Groups might also be found via hierarchal clustering to account for group-size. This might solve the issue of having to test a number of groups which is exponential in the number of features. I think these alternative views should be highlighted in the paper. Assuming that each subgroup needs to be viewed independently and they cannot be grouped together might be misleading.\n\nguarantees are worst-case in the distribution; distributions in the real world might be nicer (this concern was raised by the authors themselves)\n----\n\nI think this line of work has a lot of potential and there are many parts I like about this paper. Ultimately I think there are still some unanswered questions at this point that I would wish the paper to address in its final version. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "XcAH8Rp_Dh", "reviewer": "Reviewer_h2Fj", "summary": "The authors propose a new metric, benefit of personalization (BoP), to quantify the minimum gain in accuracy by using group attributes across all subgroups for a prediction model. They also develop a hypothesis testing framework to test fair-use of group attributes. They develop an information-theoretic limit on the error probability for any hypothesis test which is auditing a model for fair-use. They also characterize the statistical limit on the MSE for any estimate of BoP. Finally they conduct experiments to demonstrate the behavior of the probability of error in testing for fair-use", "questions": "The major comment is on the definition of the benefit of personalization metric. I agree with Definition 1 (Fair Use) where we would expect for each $j$ the accuracy of the personalized model should be *equal* and/or greater than that of the group blind model. However, when defining BoP, taking the min over j, a lot of the information is actually lost.\n\nEspecially in the corner case where we benefit every group but one where we get equality, the gamma turns out to be zero since we are taking the minimum. Hence from the recommendation point of view, forcing the test on BoP > epsilon would not let us deploy any of these models where we are benefitting all group lest one (or a few).\n\nIn such situations, it is much more preferable to deploy a new personalized model to the other groups while keeping the base model for that group. Being able to quantify such a metric where are not actively harming a group, but making it better for the majority of others should be a good forward step.\n\nCan the authors throw some light on this nuance and actively discuss how to change the metric towards this direction? Also curious how the Information-Theoretic results will change with such a new metric. \n\n", "limitations": "The major limitation is on the recommendation based on the metric defined in this paper. The details are highlighted in the question above. But following the recommendation would make us miss a big corner case where in practice it is not possible to improve accuracy for each  group but possible for a wide range and keeping it same for others.\n", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and is easy to follow. The associated theoretical results look good. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["Discrimination / Bias / Fairness Concerns"]}, "extra_text": {}}, {"review_id": "GdAAgnO4y_Y", "reviewer": "Reviewer_2nKW", "summary": "The paper contributes to fairness literature by proposing a new metric, the benefit of personalization (BoP), to measure the benefit of including group attributes in a binary prediction model. The metric measures the worst-case improvement across subgroups, which is attractive in settings where parity is not a reasonable metric, but \"do no harm\" is an appropriate metric, such as healthcare. The paper considers two settings in which the metric may be used, hypothesis testing and estimation, and provides general characterizations on the reliability of the metric. Specifically, the paper bounds the worst-case error in hypothesis testing and the MSE of the BoP estimator relative to the number of sub-groups and the number of samples per subgroup. Intuitively, they show the BoP metric is more reliable as the number of samples per subgroup increases. These results are then used to characterize general rules of thumb on when BoP estimator is reliable for estimation or testing. Numerical experiments are provided throughout to highlight how well the BoP metric performs empirically in both testing and estimation settings.", "questions": "1. Is it possible that a smaller subset of group attributes produces positive BoP and all group attributes produces a negative BoP? For example, I can imagine a scenario that for 10 group attributes, there may exist a subset of the group attributes that improve classification accuracy of the machine learning model but including all 10 may decrease the classification accuracy of a subgroup. \n\n2. As a follow up to 1., is it possible to comment on the reliability of BoP in the setting that you perform the hypothesis test on different subsets of the group attributes? Can you just apply existing results in multiple hypothesis testing to do so? This would potentially allow you to identify the smaller subset of group attributes in question 1. \n\n3. Similar to 2., does the MSE result (Theorem 2) hold uniformly over different subsets of group attributes?\n\n4. Does focusing on accuracy for BoP guarantee improvements in the false negative and false positive rate? If not, can the BoP metric be modified to measure only false negatives or only false positives rather than accuracy? \n\n5. For Figure 2 Right, do you mean higher values of $\\| \\epsilon \\|$ have higher tolerance for mistakes in the test?  \n\n6. In Corollary 2, is there a reason that the 5% threshold was chosen as the default benchmark? It may be important to clarify the choice as it directly affects the maximum number of binary group attributes that still guarantee reliable estimation of BoP.\n\n\n", "limitations": "The authors mainly address limitations related to the drawbacks of their worst-case results in settings where stronger assumptions may be made on the underlying data distribution. There isn't a discussion of the negative societal impact of their work, but it is unclear if there is a specific society impact they can discuss. Perhaps further discussion can be made on why accuracy was chosen as the benchmark metric rather than something similar such as the false positive rate or false negative rate. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a well-written paper that provides an interesting metric, BoP, to address a rapid expansion of personalization in machine learning. The paper does a good job of overviewing the setting and the motivation for developing the metric and provides useful characterizations of the metric. By considering worst-case bounds, the paper can construct conservative rules outlining when the metric can be used to make the critical decision of whether or not to introduce group attributes into personalization machine learning models. The paper seems technically sound, and the results are well presented. \n\nThe main drawback of the paper may lie in the significance of the BoP itself, as it only considers the worst-case improvement of the machine learning models, which may be overly conservative. The BoP metric thus can only make the simple and coarse decision of introducing group attributes or not introducing group attributes to a model. In contrast, a potentially more exciting problem could be deciding which subgroups utilize and which subgroups do not utilize the machine learning model with group attributes. This example reflects a more granular version of the problem BoP tries to solve and captures the fair use problem similarly. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept