Post-hoc bias scoring is optimal for fair classification
Authors: Wenlong Chen
Yegor Klochkov
Yang Liu
Venue: ICLR 2024 spotlight (2024)
Keywords: group fairness
post-hoc fair classification
Bayes optimal classifier
accuracy-fairness trade-off
Primary area: societal considerations including fairness, safety, privacy

Abstract: We consider a binary classification problem under group fairness constraints, which can be one of Demographic Parity (DP), Equalized Opportunity (EOp), or Equalized Odds (EO). We propose an explicit characterization of Bayes optimal classifier under the fairness constraints, which turns out to be a simple modification rule of the unconstrained classifier. Namely, we introduce a novel instance-level measure of bias, which we call bias score, and the modification rule is a simple linear rule on top of the finite amount of bias scores. Based on this characterization, we develop a post-hoc approach that allows us to adapt to fairness constraints while maintaining high accuracy. In the case of DP and EOp constraints, the modification rule is thresholding a single bias score, while in the case of EO constraints we are required to fit a linear modification rule with 2 parameters. The method can also be applied for composite group-fairness criteria, such as ones involving several sensitive attributes. We achieve competitive or better performance compared to both in-processing and post-processing methods across three datasets: Adult, COMPAS, and CelebA. Unlike most post-processing methods, we do not require access to sensitive attributes during the inference time.

Published conference paper at ICLR 2024
POST-HoC BIAS SCORING IS OPTIMAL FOR FAIR
CLASSIFICATION
Wenlong Chen
Yegor Klochkov
Imperial College London wenlong. chen21 Satten21@@mmeet @imperiaa al ac.uk
ByteDance Research yegor 11 woc.hoovbyyeeddrceeccomm
Yang Liu
ByteDance Research yang. www.1luu1100 wewull@yytedanee... com
ABSTRACT
We consider a binary classification problem under group fairness constraints, which can be one of Demographic Parity (DP), Equalized Opportunity (EOp), Equalized Odds (EO). We propose an explicit characterization of Bayes optimal classifier under the fairness constraints. which turns out to be simple modifica- tion rule of the unconstrained classifier. Namely, we introduce a novel instance- level measure of bias, which call bias score, and the modification rule is simple linear rule on top of the finite amount of bias scores. Based on this char- acterization, we develop post-hoc approach that allows to adapt faimess constraints while maintaining high accuracy. In the case of DP and EOp con- straints, the modification rule thresholding a single bias score, while in the case of EO constraints we are required to fit a linear modification rule with 2 parame- ters. The method can also be applied for composite group-faimen fairness criteria, such as ones involving several sensitive attributes. We achieve competitive or better performance compared to both in-processing and post-processeeee three datasets: Adult, COMPAS, and CelebA. Unlike most post-processing meth- ods, we do not require access to sensitive attributes during the inference time.
methods across
INTRODUCTION
With MI. algorithms being deployed in more and more decision-making applications, it is crucial to ensure fairness in their predictions. Although the debate on what is fairness and how to measure is ongoing (Caton & Haas, 2023), group fairness measures are utilized in practice due to the simplicity of their verification (Chouldechova, 2017; Hardt et al., 2016a), and they conform to the intuition that predictions should not be biased toward specific group of the population. In practice, is desirable to train classifiers satisfying these group fairness constraints while maintaining high accuracy.
Training classifiers that maintain competitive accuracy and satisfy group fairness constraints mains a challenging problem, and it often requires intervention during the training time. popular approach (Zafar et al., 2017; 2019) suggests relaxing these constraints of discrete nature score- based differentiable constraints, thus utilizing gradient-based optimization methods. This approach very flexible and can be used in broad set of applications (Donini et al., 2018; Cotter al., 2019; Rezaei et al., 2021; Wang et al., 2021; Zhu et al., 2023). Another popular method suggests dynam- ically reweighting observations during training (Agarwal al., 2018). In vision tasks, researchers propose to use more sophisticated techniques, such as synthetic image generation (Ramaswamy al., 2021) and contrastive learning (Park et al., 2022).
Another strategy proposes to modify unconstrained classifiers in a post-hoc manner (Hardt et al., 2016a; 6a; Jiang et al., 2019; Jang et al., 2022). Unlike the in-processing methods, these methods allow one to adapt to faimess constraints after the model is trained. These modifications are much cheaper
Equal contribution.
Work done during internship ByteDance Research.

---

Published a conference paper at ICLR 2024
and more feasible in industrial settings, where very large datasets are utilized and complicated al- gorithms are used to train the target classifier. However, the existing solutions typically require knowledge of the sensitive attribute during the inference time. For instance, Hardt et al. (2016a) propose to modify a score-based classifier in the form Y(X) = {{(()) > of to a group-specific thresholding rule Y(X, A) = (R(()) > (1). Similar approaches are also taken by Jiang et al. (2019); Jang et al. (2022). This is impractical for real-world applications where sensitive attributes during inference are inaccessible due to privacy protection.
Most of the existing methods aim at debiasing a classifier, whether with in-processing post- processing method. We ask a more general question: how can we flexibly adjust a classifier to achieve the best accuracy for given level of faimess? For binary classification problem, Menon & Williamson (2018) study this question from a theoretical perspective, that is, when one knows the ground truth distribution p(Y, A|X), they derive the Bayes-optimal classifier satisfying fairness constraints. Unfortunately, Menon & Williamson (2018) only cover two cases of fairness measures: Demographic Parity and Equalized Opportunity. In this paper, we close this gap and derive the Bayes-optimal classifier for general group fairness metrics, which include the case of Equalized Odds. Our analysis also allows using composite fairness criteria that involve more than one sensitive attribute at the same time. See other related references in Section 5.
We interpret our solution as modification of (unconstrained) Bayes optimal classifier based on a few values that we term "bias scores", which in turn can be thought of as a measure of bias on in- stance level. For instance, think of reducing the gender gap university admissions. Bhattacharya al. (2017) show that such gap reduction typically happens at the expense of applicants with border- line academic abilities. In terms of classification (passed/ not passed), this corresponds to the group where we are least certain in the evaluation of one's 's academic abilities. This suggests that evaluation of bias on instance level should not only take into account prediction and group membership, but also uncertainty in the prediction of target value. Our bias score not only conforms to this logic, but thanks to being part of Bayes optimal classifier, it is also theoretically principled. In particular, for the case of Demographic Parity constraints, we show that the optimal constrained classifier can be obtained by modifying the output of the unconstrained classifier on instances with largest bias score. When Equalized Odds constraints are imposed. or more generally a composite criterion, the optimal modification is a linear rule with two or more bias scores.
Based on our characterization of the optimal classifier, we develop a practical procedure to adapt any score- score-based classifier to faimess constraints. In Section 4, we show various experiments across three benchmarks: Adults, COMPAS, and CelebA. We are able to achieve better performance than the in- in-processing methods, despite only being able to adapt to the group-fairness constraints after training. We also provide competitive results when compared to post- pot-processiig methods (Hardt et al., 2016a; Jiang et al., 2019), which require knowledge of sensitive attribute during inference.
We summarize our contributions as follows. Firstly, we characterize the Bayes optimal classifier under group fairness constraints, which generalizes Menon & Williamson (2018) in the sense that Menon & Williamson (2018) can be viewed as a special case in our framework, where the constraint is only single faimess criterion (e.g. Demographic Parity). Nevertheless, our formulation is more convenient and intuitive thanks to the interpretable bias score. Secondly, our characterization can work with composite fairness criterion (e.g. Equalized Odds) as constraint, which has not been established before to our knowledge. Thirdly, based on this characterization, we propose a post- processing method that can flexibly adjust the trade-off between accuracy and fairness and does not require access to test sensitive attributes. Empirically, our method achieves competitive or better performance compared with baselines.
1.1 PRELIMINARIES
In this work, we consider binary classification, which consists of many practical applications that motivate machine fairness research (Caton & Haas, 2023). We want to construct a classifier ý (XX) for a target variable Y E {0, 1} based on the input X. Apart from the accuracy of a classifier, are concereed with faimess measurement, given that there is sensitive attribute A, with some underlying population distribution over the triplets (X, Y, A) ~ Pr in mind. We assume that the sensitive attribute is binary as well. We generally focus on three popular grimp- criteria:
2

---

Published conference paper at ICLR 2024
Demographic Parity (DP) (Chouldechova, 2017) is concerned with equalizing the probability of positive classifier output in each sensitive group,
DP(Ý: A) Pr(Y A 0) Pr(Y (|A=1)]
(1)
Equalized Odds (EO) was introduced in Hardt et al. (2016a). Unlike DP which suffers from explicit trade-off between faimess and accuracy in the case where Y and A are correlated, this criterion is concerned with equalizing the false positive and true positive rates in each sensitive
group,
EOOY; A) = max g=0,1
Pr(y = 1/4 1|A= = Y
= =) - Pr 1|1 = 1,Y
-,y= v)
(2)
Equality of Opportunity (EOp) was also introduced by Hardt al. (2016a), and it measures the disparity only between true positive rates in the two sensitive groups,
EYp(Y; A) Pr(Y = 1/A 0, =) Pr(Y 11 11/-
(3)
BAYES OPTIMAL FAIRNESS CHARNESS-CONSTRAINGE CLASSIFIER
For given distribution over Pr ~ (X, Y), the Bayes optimal unconstrained classifier has the form ((X) = 1 1(p(Y = x|x) > 0.5} in the sense that it achieves maximal accuracy. Although is not generally possible to know these ground-truth conditional probabilities (p(Y 1[X)) in practice, such characterization allows one to train probabilistic classifiers, typically with cross-entropy loss. Here we ask what is the optimal classifier when the group fairness restrictions are imposed. Namely, which classifier Y (X)) maximizes the accuracy Acc(Y) = Pr(Y = Y)) under the restriction that particular group fairness measure below given level
We are interested in either DP, EOp, or EO constraints, as described in the previous section. For the sake of generality, we consider the following case of composite criterion. Suppose, have several sensitive attributes AI,..., Ax and for each of them we fix values ak, by so that need to equalize the groups (Aę = dx and {Ax = by) J. other words, our goal to minimize a composite criterion represented by a maximum over set of disparities,
CC(Y)
max j=I....KK
Pr(( = 1|4, = ax) - -Pr(r = 1|A, = bb))
This general case covers DP, EOp, and EO, as well as composite criteria involving more than one sensitive attribute. Let give few examples.
Example 1 (Demographic Parity). For the case of DP (see Eq. 1), it is straighfforward: take A AE {0, 1}, a1 = O, b1 = L, and then with K = 1, CC(Y) = DY)
Example (Equalized Opportunity and Equalized Odds). Suppose we have a sensitive attribute A E {0, 1}, then the Equalized Opportunity criterion (Eq. 2), can be written in the form of Eq. 4 with A = (A, a1 = (0, 1), and bj = =1,
For the Equalized Odds, can write it composite criterion with K = 2 by setting A A2 (A, Y), and setting a = (0, 0), b, = (), 02 (0, by = (1, in Eq. 4.
Example 3 (Two and more sensitive attributes). We could be concerned with fairness with respect to two sensitive attributes A, B simultaneously (for instance, gender and race). In this case, we want to minimize the maximum of two Demographic Purilies, which looks as follows
max((Pr(f = -1/A= max(Pi((=11AA0)) Pr = 1|A -1|A=1//.PPM- =|| -P(( = ([[V=1[B11]p
If we have three DPs, we will have K two different sensitive attributes, we would have K 4, etc.
Eq. 4; if we are interested a maximun over EO's for
Given a specified fairness level 8 > O, we want to find the optimal classifier Y()), possibly ran- domized, that is optimal under the composite criterion constraints
Acc(L) Pr(r = YY)
CC(Y) & 6.
(5)

---

Published conference paper at ICLR 2024
We will be searching the solution in the form modification the Bayes optimal unconstrained classifier. Recall that in our notation, Y = y(X) denotes the Bayes optimal unconstrained classifier {[p(1[X) > 0.5}. We "reparametrize" the problem by setting k(X) = Pr(Y + Y|X) as the target function. In other words, given arbitrary function x(X) [0, I]. define the modification ((X) of (X) by drawing Z Be(r((X) and outputting
Y,
=
Y=
1-
Z ==1
We call such function <(X) a modification rule. With such reparameterization. the accuracy of modified classifier can be rewritten as
Acc(V) Acc(P) -
x| represents the confidence of the Bayes optimal unconstrained classifier Y on the instance X (see Section A.I for detailed derivation), A similar representation holds for the value of the composite criterion. Specifically, recall the criterion is of the form CC(Y) - max K (Cx(Y)), )}. where
where (x)) 2p(Y
C&(Y) Pr(V = 1|Ax = =a)) Pr(P = 1|Ax -b))
We can rewrite it
Cx = -C(()) / (a00-/(f((x())))))) fx(x))(())dP(())
(6)
|p(A2 ax p(Ax = x)
fx(X) = (2Ý 1)
(7)
Pr(A= = ax) Pr(A# = by)
These two expressions suggest that modifying the answer on point with low confidence (X) makes the least losses in the accuracy, while modifying the answers with higher absolute value of
(x) makes largest effect on the parity values, although this has to depend on the sign. This motivates us define modification rule on the relative score,
$ [x(() rxX)
(Instance-Level Bias Score):
which we refer to bias score. It turns out that the optimal modification rule, i.e. one corresponding to the constrained optimal classifier in Eq. 5, simple linear rule with respect to the given K bias scores. We show this rigorously in the following theorem. We postpone the proof to the appendix, Section A.I.
Theorem Suppose that all fanctions fu.M are square intrrr-iteerralee and the scores sy(X) fx(X) ((X)) have joint continuous distribution. Then, for any ó > O, there is an optimal solu- tion defined Eq. that is obtained with a modification rule of the form,
x(x)=1 =
x(X)
Σ Z4SK (X) >1
This result suggests that for the case of DP, EOp, or EO, given the ground-truth probabilities p(Y,Al A|X), we only need to fit parameter for either of Demographie Parity and Equalized Oppor- tunity, which essentially corresponds to finding a threshold, and fit a linear rule in two dimensions for the Equalized Odds. Below we consider each of the three faimeess measures in detail.
Demographic Parity.
In the case of DP constraint, we have single bias score of the form,
p(4 0|X) p(A= 1|X]
s sX)
(() (28 -
(10)
Pr(A=0)
Pr(A=1)
and since there is only score, the modification rule is simple threshold rule of this bias score x(X) ((x(X/ 1}. We note that t can positive or negative, depending on which group has the advantage, Section A.I. This allows make linear comparison of fairness on the
4

---

Published conference paper at ICLR 2024
instance level. That is, departing from a fairness measure defined on a group level, we derive bias score that measures fairness on each separate instance. For example, in the context of university ad- missions (Bhattacharya al., 2017), 7, our bias score conforms with the following logic: is more fair to admit student who has high academic performance (lower ry(X)) )) than one who has borderline performance (higher ()))) even though they are both equally likely to come from the advantagcous
group (same f(X)). We note that the problem of measuring fairness and bias on instance level has recently started to attract attention, see Wang et al. (2022); Yao & Liu (2023).
Equality of Opportunity. Here we also have the advantage of having a simple threshold rule, corresponding to the score function,
1 (28 - -A = 1 = 1[X) (x) (28
8 (X)
Pr(A=0,y Pr(A=
group-awars thresholding). Let us consider the case where there is one-to-one correspondence A = A(X). This is equivalent to the case of observed sensitive altribute, and it is trivial to check that our method turns into a group-aware thresholding and becomes obliv- ious (Hardt al., 2016a; Jang al., 2022) (i.e., the flipping rule doesn't 't depend on interpretation of individual features any more). Indeed, in such case we have p(A = a,Y = 1[X) = p(Y
Remark 2.1 (Comparison
=1), where ( = =.) therefore s(X) 2p( =1||=] {ax)(A(X) = =0 + ( = 1}}, ag = 1/(A = 0, = 1) > and 01
p(Y=1|X0
1, = 0. Then for given ts, the final decision rule turns into (XX A) = 1(p(Y= = 1|X) > ta}. where tA 0.5 aa5t/a/Att, 2)
Let us consider the case of optimizing under Equalized Odds constraint in detail. In this case, we need to know the ground-truth conditional probabilities p(Y, A(X), and we obtain two scores for k = 0, 1,
Equalized Odds.
p = A= p(Y = A= s (X) 7(X) 128 - 13 Pr(Y = k A Pr(Y = k 11
(II)
Our goal is then to find a linear rule in the bias embedding space (so(X), 81 (X)), which on vali- dation, achieves the targeted equalized odds, while maximizing the accuracy. Notice that here the problem is no longer a simple threshold choice as in the case of DP-constrained classifier. We still need fit a cointrss- classifier, only we have dramatically reduced the complexity of the problem to dimension K = 2, and we only have to fit a linear classifier.
We demonstrate the modification rule in the case of EO constraints with the following synthetic data borrowed from Zafar et al. (2019) [Section 5.1.2 as example:
= P(X = 1, = 0) = /V(((.),, 55, 1,
p(X = 1 1) -V
5)),
P(X = 0, A = 0) = (V[[11, [5, 1,),),,, P(X 0, 1) 1) -
5))
(12)
We sample 500, 100, 100, 500 points from each of groups (Y, (1,0), (1, (0, (0,1), 1), respectively, so that Y and A are correlated. Next, we fit a logistic linear regression with 4 classes to estimate p(Y, A|X) and calculate the scores according the formulas Eq. 11. In Figure 1a, we show the scatter plot of the scores (su(X), $1 (X)), with the corresponding group marked by different colors. Figures 1b-le show the optimal flipping rule, with color encoding x(X) evaluated with the discretized version of the linear program, while the red line approximately shows the optimal linear separation plane. We observe that some of the points that we had to flip for the restriction EO < 5 = 0.15, are unflipped back when the restriction is tightened to EO < ó = 0.01. It indicates that unlike in the case of DP restriction, there is no unique score measure that can quantify how fair is the decision made by trained classifier.
3 METHODOLOGY
In practice, especially for deep learning models, unconstrained classifiers are usually of the form Y = [ > 0.5}, with the conditional probability trained using the cross-entropy loss. Our characterization of the optimal modification rule naturally suggests a practical post-processing algorithm that takes fairness restriction into account: assume that are given auxiliary model for
5

---

Published conference paper at ICLR 2024
either (X) (in the case of DP constraints) or A(X) (in the case of EOp and EO constraints). We then treat these estimated conditionals as ground-truth conditional distributions, plugging them into Eq. 8 to compute the bias scores, and modify the prediction Y correspondingly with a linear rule over these bias scores. We propose to fit the linear modification rule using a labeled validation set. We call this approach Modification with Bias Scores (MBS) and it does not require knowing test set sensitive attribute since the bias scores are computed based on the estimated conditional distributions related to sensitive attribute (j( A X)) or pY, A X)) instead of the empirical observations of sensitive attribute. Here we demonstrate the algorithms in detail for the two cases where DP and EO are the fairness criteria.
Post- post-processing algorithm with DP constraints. In this case, we assume that we have two mod- els p( and ((A (which in the experiments are fitted over the training set, but can be pro- vided by third party as well) to estimate the ground truth p(Y| and p(A(X) respectively. We then define the bias score as follows:
f(x) 8(X) ((X) = (2)(X) - 13 [(A=D]X) #(==1|)
Pr(A=0) Pr(A=1)
(13)
20(Y = (X)]XX- -1
where Pr(A= = i) (i = 0, 1) can be estimated by computing the ratio of the corresponding group in the training set. We search for the modification rule of the form x(X) 1(5(X)/t > 1}, so that the resulting (x) = 1{5(X)/t S IxY( + {$(()/t > 1)(1 - (X)) satisfies the DP constraint, while maximizing the accuracy. For this, we assume that we are provided with labeled validation dataset {x,,, A.) Neal and we choose the threshold such that the validation accuracy is maximized, while the empirical DP evaluated on it is S 8. To find the best threshold value, we simply need go through all Neat candidates t = s(X;), which can be done in O log Neat) time. See detailed description in Algorithm in the appendix, Section B.
Post-processing algorithm with EO constraints. In this case, we require an auxiliary model ((Y,A|X) with four classes. This allows us to obtain the 2D estimated bias score (s,( (X)),, where
8o(X) = fo(x) (x) -1 =(A=0.-=|xx) ((=_LY=0X)
Pr(A=0,Y=0) Pi(A=I,Y
((X)
25(Y = (X))XX) -1
(14)
(X) 13 2(A=0,Y=1 ((A=LY=IX)
(x,) = (x)
Pr(A=0,Y=1) Pi(A=LY=I)
f(.))
2p(Y = -(X))X)-
where each of the Pr(A = a, Y y) is again estimated from training set. We are searching for linear modification rule =(X) = 1 ( > 1} that for a given validation set satisfies the empirical EO constraint while maximizing the validation accuracy. We consider two strategies to choose such a linear rule.
In the first approach, we take subsample of points (X of size M < Nual and consider all (MM1))) possible linear rules passing through any two of these points. For each of these rules, we evaluate the EO and accuracy among ones satisfying EO < 6. The total complexity of this procedure is ( N A formal algorithm is summarized in Algorithm 2 in the appendix, Section B.1.
validation set, then choose maximal accuracy
We also consider a simplified version, where we fix a set of K equiangular directions w = (cos(2rr K), sin(Trjj ()) for j 0, O..... 1. Then, for a score (p + w w1&1 (X) simply need to choose a threshold, following the procedure in the DP case, where we evaluate the EO and accuracy dynamically. The time complexity in OoKNo log Noat), see details in Algo- rithm 3. Section B.I in the appendix.
and A|X) must agree in or- der for Theorem I to hold, in the sense that p(Y = p(Y, 0Jx) + 1] However, the form of the algorithms itself. which only requires "plug-in" estimators b and P(Y, A(X) for ground- truth X)) and p(Y. A(X) respectively, does require strict agreement between Y X)) and b(Y.A| for it to run. In practice, we can employ xX) p(Y, A(X) that were trained sepa- rately, and can run the algorithm even in the case where the auxiliary model p(Y, A\X) was
Remark 3.1. Note that as functions of X, the probabilities

---

Published conference paper at ICLR 2024
Y-1.A-
-00
-40
-60
Y- 0.0
-00
-60
-40
50 -50
50
-50
50
(a)
(b)
(c)
Figure 1: (a) Scatter plot of the scores for synthetic distribution Eq. 12. (b) Separation
plane for the optimal flipping rule x corresponding EO S == 0.115 and (c) 8 0.01.
pretrained by a third party on another dataset similar the one of interest. E.g. we conduct an experiment where the auxiliary model is based on CLIP (Radford et al., 2021) in Section C.3.
Sensitivity analysis. Here we investigate the sensitivity of our method to inaccuracy in the esti- mated conditional distributions. We first provide theoretical analysis, which takes into account two sources of error: approximation of the ground-truth conditional distributions p(Y|X) and p(A[X) by, say parametric models, and the sampling error in evaluation of the accuracy and DP on valida- tion. The details regarding the conditions and omitted constants deferred to the appendix. See precise formulation and the proof in Section E, which also includes general composite criterion.
Theorem (Informal). Suppose that we have estimations of conditional distributions X)Y x(A[X) (or $(Y, A(X) when using EO constraint), and assume that
(Y(( P(YIX) S,
Blp(A - p(A[X) Se ELP(Y, A(X)ss
(for DP),
(for EO).
Let be the algorithm obtained with Algorithm I (Algorithm for EO). Then, with high probability
Acc(E) - Acc(P) S Vē + V Neat)/ Nual,
DP(Ý) S / (log Neat) / Naat= (EO(Ý) 8 S v (log Nvat)/Neul
Moreover, we include three ablation studies appendix C, where less accurate ( ((A or P(Y A[X) are deployed to examine the robustness of the post-processing modification algorithm. We find that our post-procsssing algorithm still retains the performance even when (X) ((A or p(Y, A(X) are moderately inaccurate.
EXPERIMENTS
We evaluate MBS on real-world binary classification tasks with the following experimental set-up.
Datasets.
We consider three benchmarks:
Adult Census (Kohavi, 1996), UCI tabular dataset where the task is to predict whether the annual income of an individual is above $50,000. We randomly split the dataset into a training, validation and test set with 30000, 5000 and 10222 instances respectively. We pre-process the features according to Lundberg & Lee (2017) and the resulting input X is a 108-dimensional vector. We use "Gender" the sensitive attribute:
COMPAS (Angwin et al., 2015), a tabular dataset where the task is to predict the recidivism of criminals. The dataset is randomly split into training. validation and test set with 3 3166, 1056 and 1056 instances respectively. The input X consists normal features (e.g. age and criminal history) and we choose "Race" as the sensitive attribute;
7

---

Published conference paper at ICLR 2024
Jarg 1.
123
g46
26.3
566
5.0 383
37a
30
124
10.0
2.
10:20
10.0
252
1010
(a)
(b)
(c)
(d)
Figure 2: Accuracy (%) Demographic Parity (DP) (%) trade-off's on (a) Adult Census and (b) COMPAS; Accuracy (%) vs Equalized Odds (EO) (%) trade-offs on (c) Adult Census and (d) COMPAS. Desired ō co (unconstrained), 10%, 5%, and 1 1%.
CelebA (Liu et al., 2015), a facial image dataset containing 200k instances each with 40 binary attribute annotations. We follow the experimental setting as in Park et al. (2022): choose "Autractive", "Big nose", and "Bag Under Eyes" as target attributes, and choose "Male" and "Young" sensitive attributes, yielding 6 tasks in total, and we use the original train-validation- test split.
Network architectures and hyperparameters. We use an MLP for Adult Census and COMPAS datasets, with hidden dimension chosen to be 8 and 16 respectively. For each CelebA experiment, we use ResNet-18 (He et al., 2016). For experiments with DP constraints, we train two models X( and pi (X) to predict the target and sensitive attributes respectively, while for experiments with EO constraints, we only train one model but with four classes p(Y, A(X), with each class corresponding to one element in the Cartesian product of target and sensitive attributes.
Baselines. For experiments on Adult Census and COMPAS, we compare MBS with Zafar et al. (2017) (Z17), Jiang et al. (2019) (J19) ppost-procsssing version, for experiments with DP con- straints) and Hardt et al. (2016a) (H16) (for experiments with EO constraints). For CelebA, we additionally compare with Park et al. (2022) (P22), which is strong baseline tailored to fair facial attribute classification on CelebA. We report the averaged performance from 3 independent runs for all methods.
Evaluations & metrics. We consider both Demographic Parity (DP) and Equalized Odds (EO) as fairness criteria. We select the modification rules x(X) over the validation set according to the algorithms in Section 3. We consider three levels of constraints for the fairness criteria: 8 = 10%, 5%, and 1%, and we set M in Algorithm described in Section 3 to be 3000, 600 and 5000 for experiments with EO as fairesss criterion on Adult Census, COMPAS and CelebA, respectively. Then we report the test set accuracy and DP/EO computed based on the post-processed test predictions after modification according to x(X).
4.1 EXPERIMENTS WITH DP AS FAIRNESS CRITERION
We consider experiments with DP as fairness criterion on Adult Census and COMPAS datasets, and compare MBS with Z17 and J19 (J19). The results reported in Figures 6a-2b. One can MBS consistently outperforms Z17 for both datasets in the sense that given different desired levels (ō's) of DP, MBS tends to achieve higher accuracy. Furthermore, while Z17 requires retraining the model each time to achieve a different trade-off between accuracy and DP, we are able to flexibly balance between accuracy and DP by simply modifying predictions of a single base model according to different thresholds of the bias score. For Adult Census, the x(X) estimated over validation set is robust when evaluated over test set since the DPs for test set are either below the desired 8's or close to it. For COMPAS. the performance seems to be relatively low as one can see relatively large drop in accuracy when DP is reduced. Although MBS still outperforms Z17 in this case, achieves worse performance than J19 and since the validation set is small (1056 instances), the x(X) estimated over is not robust as there is a relatively big gap between DPs on test set and the specified 8's. The decline of performance 5278 instances), and the number of training examples is insufficient for reliable estimation both xY and pl A|
COMPAS is not surprising since COMPAS is small dataset (with only
8

---

Published conference paper at ICLR 2024
Test accuracy (ACC) (%) and EO (%) on CelebA for all six combinations of target and sensitive attributes: (a, m), (a, y), (b, m), (b, y), (e, m), and (e, under different desired levels (8's) of EO (%) constraints. Boldface is used when MBS is better than P22 both in terms of accuracy and EO.
Table 1:
(a, m)
(a,
(b.
m)
(b, y)
(e, m)
(e,
8 ACC
EO
ACC
EO
ACC
EO
ACC
EO
ACC
EO
ACC
EO
DG
81.9
23.8
82.0
24.7
84.1
44.9
84.5
21.0
85.2
19.0
85.6
13.7
10
80.9
6.7
79.7
10.9
83.5
8.4
84.3
10.6
85.0
8.2
85.1
9.5
5
80.1
2.2
78.2
6.6
83.3
4.3
84.2
4.1
84.7
5.6
85.1
5,4
1
79.3
4.0
76.9
2.0
83.2
1.7
83.6
2.4
83.1
1.7
83.6
1.8
H16
71.7
3.8
71.4
3.4
78.2
0.5
80.1
1.3
80.2
1.7
81.7
1.6
P22
79.1
6.5
79.1
12.4
82.9
5.0
84.1
4.8
83.4
3.0
83.5
1.6
4.2
EXPERIMENTS WITH EO AS FAIRNESS CRITERION
To evaluate the performance of MBS when the fairness criterion is EO, we again consider Adult Census and COMPAS datasets and the results are reported in Figures 6b-2d. The observation is sim- ilar to that in experiments with DP constraints. We again achieve better trade-off between accuracy and EO than Z17 for both datasets. Although H16 can also significantly reduce EO, similar to J19 the DP-based experiments, it is not able to adjust the balance between EO and accuracy and thus is less flexible than MBS. Both MBS and Z17 achieve relatively low performance for small dataset COMPAS, which we again believe it is due to unreliable estimation of p(Y, A|X) with small dataset. Similar to J19, HI Hassumees access to the sensitive in test, and thus will not be affected by unreliable inference the test sensitive attribute.
In addition, evaluate MBS more challenging dataset, CelebA, following the same set-up as in P22. Here we denote the target attributes "Attractive", "Big-Nose". "Bag.Under_Eyerr as "a", "b" and "e" respectively, and the sensitive attributes "Male" and "Young" "m" and "y" respectively. The results are reported in Table 1. MBS tends to achieve better trade-off than Hi6, whose accuracy is severely hurt across all tasks. MBS is able maintain high accuracy and meanwhile achieve competitive or even smaller EO. Furthermore, MBS consistently achieves better or competitive performance when compared with P22. To our knowledge, their method is one of the state-of state-of-the -o--th----rrrrr the methods for fair learning on CelebA. We additionally report validation metrics and standard error across independent runs in Appendix D.
5 RELATED LITERATURE
We mention some recent work on Bayes optimal classifiers under approximate faimess constraints. Menon & Williamson (2018) consider cost-aware binary classification, followed by a series of sults that characterize sensitive attribute-awee aware fair classifiers. These include DP constraints with either binary or multi-class target and either binary or multi-class sensitive attribute Denis et al. (2021); Xian et al. (2023); Gaucher et al. (2023). Zeng et al. (2022) additionally considers other group fairness metrics. These papers do not cover cases of Equalized Odds and Composite Criterion. Implementations in Denis et al. (2021); Zeng et al. (2022) are based on closed form expressions the threshold weights, while our MBS treats the bias scores as features.
6 CONCLUSION
To the best of our knowledge, we have for the first time characterized the Bayes optimal binary classifier under composite group fairness constraints, with post-hoc modification procedure applied to unconstrained Bayes optimal classifier. Our result applies to popular faimess metrics, such as DP, EOp, and EO as special cases. Based on this characterization, we propose a simple and effective prscesrocssiing method, MBS, which allows to freely adjust the trade-off between accuracy and fairness. Moreover. MBS does not require test sensitive attribute, which significantly broadens its application in real-world problems where sensitive attribute is not provided during inference.

---

Published conference paper at ICLR 2024
ACKNOWLEDGMENTS
We are grateful to the anonymous referees for valuable feedback that helped to improve the presenta- tion, extend experiments and theoretical results. We are thankful to our former collegue Muhammad Faaiz Taufiq for plenty of fruitful conversations. We also thank Yingzhen Li for her valuable com- ments on the manuscript.
REPRODUCIBILITY STATEMENT
Details for the experimental set-up are provided the beginning of Section 4, and the code can be found at https:://g www.coocc//eeeee chemm/cheww000mmm (at.m/////iassaee /iaasceree
REFERENCES
Alckh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reduc- tions approach to fair classification. In International conference on machine learning, pp. 60-69. PMLR, 2018. pages 1, 28
J. Angwin, J. Larson, S. Mattu, and L. Kirchner. Machine bias: There's 's soft- ware used across the country to 272 predict future criminals. And it's biased against blacks. 2015. URL https: https://wwwww.ooppb..
org/ artiice/ pages 7
Debopam Bhattacharya, Shin Kanaya, and Margaret Stevens. Are university admissions academi- cally fair? Review of Economics and Statistics, 99(3):449 464, 2017. pages 2,
Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification: A survey of some recent advances. ESAIM: probability and statistics, 9:323-375, 2005. pages 23
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learn- ing Research, 2:499-526, 2002. pages 23
Simon Caton and Christian Haas. Fairness in machine learning: A survey. ACM Computing Surveys, 2023. pages 1,
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5(2):153-163, 2017. pages 1,
Andrew Cotter, Heinrich Jiang, Maya R Gupta, Serena Lutong Wang, Taman Narayan, Seungil You, and Karthik Sridharan. Optimization with non-differentiable constraints with applications to fairness, recall, churn, and other goals. J. Mach. Learn. Res., 20(172):1-59, 2019, pages I
Christophe Denis, Romuald Elie, Mohamed Hebiri, and François Hu. Fairness guarantee in multi- class classification. arXiv preprint 10X::2009.1344. 2021. pages 9, 24
Michele Donini, Luca Oneto, Shai Ben-David, John Shawe-Taylor, and Massimiliano Pontil. Em- pirical risk minimization under fairness constraints. Advances in neural information processing systems, 31, 2018. pages
Solenne Gaucher, Nicolas Schreuder, and Evgenii Chzhen. Fair learning with wasserstein barycen- ters for non-decomposable performance measures. In International Conference on Artificial In- telligence and Statistics, pp.
PMLR, 2023. pages 9
Moritz Hardt, Eric Price, and Nathan Srebro. Equality of opportunity in supervised learning. The Conference Neural Information Processing Systems (NeurIPS), 2016a. pages 2, 3, 8, 9, 21. 22
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochas- tic gradient descent. In International conference on machine learning, pp. 1225-1234. PMLR, 2016b. pages 23
10

---

Published conference paper at ICLR 2024
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In IEEE conference on computer vision and pattern recognition (CVPR), 2016. pages 8
Tianyang Hu, Wenjia Wang, Cong Lin, and Guang Cheng. Regularization matters: A nonparamet- ric perspective on overparametrized neural network. In International Conference on Artificial Intelligence and Statistics, pp. 829-837. PMLR. 2021. pages 24
Taeuk Jang, Pengyi Shi, and Xiaoqian Wang. Group-aware threshold adaptation for fair classifica- tion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 6988-6995, 2022. pages 1, 2,
Ray Jiang, Aldo Pacchiano, Tom Stepleton, Heinrich Jiang, and Silvia Chiappa. Wasserstein fair classification. In Conference on Uncertainty in Artificial Intelligence, 2019, pages 2,
Yegor Klochkov and Nikita Zhivotovskiy. Stability and Deviation Optimal Risk Bounds with Con- vergence Rate O11/n). Advances in Neural Information Processing Systems, 34:5065-5076, 2021. pages 23
Ron Kohavi. Scaling up the accuracy of naive- naive-bayes classifiers: A decision-tree hybrid. Knowledge Discovery and Data Mining, 1996. pages 7
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In International Conference Computer Vision (ICCV), 2015. pages 8
M. Lundberg and S. I. Lee. unified approach interpreting model predictions. Advances in neural information processing systems, 2017. pages
Enno Mammen and Alexandre B Tsybakov. Smooth discrimination analysis. The Annals of Statis- tics, 2786):1888-1829 1999. pages 23
Aditya Krishna Menon and Robert C Williamson. The cost of fairness in binary classification. In Conference on Fairness, accountability and transparency, pp. 107-118. PMLR, 2018 pages 2,
Sungho Park, Jewook Lee, Pilhyeon Lee, Sunhee Hwang. Dohyung Kim, and Hyeran Byun. Fair contrastive learning for facial attribute classification. In The IEEE/CVE Conference Computer Vision and Pattern Recognition (CVPR), 2022. pages 1, 8, 9, 21, 22
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference machine learning, pp- $748-8763. PMLR, 2021. pages? 7
Vikram V Ramaswamy, Sunnie SY Kim, and Olga Russakovsky. Fair attribute classification through latent space de-biasing. Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 9301-9310, 2021. pages
Ashkan Rezaci, Anqi Liu, Omid Memarrast, and Brian D Ziebart. Robust fairness under covariate shift. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9419- 9427, 2021. pages
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer, 2009. ISBN 978-0- 387-79051-0. pages 24
Vladimir Vapnik. Statistical learning theory. John Wiley & Sons, Chichester. 1998. pages 23, 26
Jialu Wang, Yang Liu, and Caleb Levy. Fair classification with group-dependent label noise. In Proceedings of the 2021 ACM conference on fairness, accountabillry, and transparency, pp. 526- 536, 2021. pages 1
Jialu Wang, Xin Eric Wang, and Yang Liu. Understanding instance-level impact of faimesss straints. In International Conference on Machine Learning, pp. 231 1411142333 231300. PMLR, 2022.
pages 5
11

---

Published conference paper at ICLR 2024
Ruicheng Xian, Lang Yin, and Han Zhao. Fair and optimal classification via post- post-processing. In International Conference on Machine Learning, pp. 37977-38012. PMLR, 2023, pages
Yuanshun Yao and Yang Liu. Understanding unfairness via training concept influence. arXiv preprint arXiv:2306. 77228, 2023, pages 5
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Fair- ness constraints: Mechanisms for fair classification. In Artificial intelligence and statistics, pp- 962-970. PMIR, 2017. pages 1, 8,9
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriquez and Krishna P Gummadi. Fair- ness constraints: A flexible approach for fair classification. The Journal of Machine Learning Research, 30(1))273722778 2019. pages 5,
Xianli Zeng, Edgar Dobriban, and Guang Cheng. Bayes-optimal classifiers under group fairness. arXiv preprint arXiv:220..09724, 2022. pages 9, 15, 24
Zhaowei Zhu, Yuanshun Yao, Jiankai Sun, Hang Li, and Yang Liu. Weak proxies are sufficient and preferable for fairnsss with missing sensitive attributes. 2023. pages
12

---

Published conference paper at ICLR 2024
A PROOF OF THEOREM
A.1 SIMPLE PROOF FOR THE CASE OF DEMOGRAPHIC PARITY
For the sake of exposition, we first show simple proof for the case of demographic parity. Observe that,
fa (1-x (1- = F[x)dP((X)
Acc(Y) =not modifying term)
/ x(X)(1 p(Y -((X)xx))
(modifying term)
=Acc(8)+ + x x(X)11 - 22 ((X)I))(PI(XX)
= =Ace(") - ((X3M()))P(())
Let us now write how the demographic parity changes after we modify the answers. We use notation DP2 to denote a signed demographic parity that measures difference between positive output for groups A = 0 and A = 1, so that the actual DP is the absolute value of DP+. We have,
/ DP1(1= = Pr(y = |r((P=11xg) -1/))
p(A x|X) p(A=1|X) dPP((X)
Pr(A 0) Pr(A=1) =
= - ( [
0|x) p(A
1|xx
dPr(()
[Pr(A= =0 Pr(A = 1)
= =DP x(())
ppA== p(1 1
Pr(A = Pr(A = d'Pr(X):
here DP1 (Y) corresponds to the parity of the original classifier Ý. W.l.o.g., assuming that DP1 (Ý) is positive (i.e., A = 0 is the advantaged group based on the unfair ÿ), to decrease the DP maximally, we should sooner reject points with higher score
p( p 0 (4=11X)
f(x) = 128 - t}
Pr(A=0) 0) Pr(A=1)
It suggests when YX)) = 1, we should sooner modify the prediction (from to 0) for X that is more likely to come from the advantaged group favoured by the original unfair classifier, and when ((X) = 1, we should sooner modify the prediction (from 0 to 1) for X that is more likely to come from the disadvantaged group based the original unfair classifier. Similarly, if DPI is negative, we should modify those points with lowest score. Notice that we always should modify points with sign equal that of DP unless it is not possible, then we have reached ideal parity DP+ (x) = O. Recall that in order to reduce the accuracy the least, we should modify on the points with lowest confidence (X). The relative change then is quantified by the ratio sXX) f(X)/n(X). Turns out, we can prove that the optimal rule correponds to xx() = 1 (x(X) > 1) (when DP1 (V) > O, otherwise we should look for x(X) 1{s(X) < t}) by repeating the steps of famous Neyman- Pearson lemma, where we replace the probability of null and alternative hypothesis with rxX), f(X), respectively.
Indeed, by contradiction, assume there is a separate rule xe' that achieves the same accuracy but smaller DP+, so we have that
(d(())x(x)))(())
o, and (xX)))x(())())))((( <
We assume that f(X) is non-negative everywhere where both x(X) and x'(X) are non-negative, otherwise it corresponds to modifying a good answer points from disadvantaged group. Let us denote m(X)= = (x'( - =(X))n(X) and r(X) = f(x)/n(X). Then, we have that where xXX) < 0 we have r(X)= 2 s and where m(X)
have r(X) So, weight negative
13

---

Published conference paper at ICLR 2024
points with smaller and positive score, hence contradiction. More, rigorously,
f m (m())((x)dPP(x)) / mxXX))((])]((mxxx)))))))))))) 0))P(()
ml (x))))
m(X)sl(m(X)) O)dP)(X)) ( m(X))s(m(X) O)dPr(X)
A.2 COMPLETE PROOF OF THEOREM
First, let expand the derivation in Eq. 6. We have,
p(Ax (x(x)
p(A, by (X)
Cx(8) Pr(YY 1
dPPr(X)
Pr(AA = ax)
Pr(Ax [A = bb)
=G - -f 1 |xx))22(0==11 = 1
[p(Ax =a axlx) X)
p(AA 1aabbbalpp bx
dPr(X)
Pr(As = ax)
Pr(As = bb)
= (f00- ((X))x(X)))Pi(()
where we set C% = (r) Therefore, our optimization problem can be formulated as a linear problem functions (xX)
Acc(P)- Acc(Y) ((X))(())PP((x)
min x(X)e
t.
/ {XX)) +
(((X)(())PP(X)) - 6
To prove Theorem 1, is left to apply the following technical lemma. Lemma Suppose, we have functions fi(X)...., (X),,, (XX), and probability measure over X E X. Consider the optimization problem measurable functions x(X) taking values in [0, 1].
(,,m) min, where (f.g) = ((X)g(X)))((( Suppose, the following conditions hold:
s.t.
fk) bk. k=
A. all functions fk, are from L2(P);
B. there is a strictly feasible solution, in the sense that there is a function K' (X) E [0, 1] such that (K', Sk) byi
C. for any R4, we have that P(En 2xfx(X) + n(X) 0) = Notice that this weaker version of the condition that (fi/n...., JK JK/T1) (T) has continuous distribution.
TRK and an optimal solution of the Then, there is
R(X) =1 Σ <xf4()) ((x))>(()
n(X)
Furthermore, 2 E R can be any solution to the problem min bT 2 ((=T
Notice, that thanks to 8 > 0, the restrictions can be met with strict inequalities by the modification rule x(X) = 1pp(Y = 1 < 0.5] which corresponds to the constant classifier y = 1. Fur- thermore, note that we have in total 2K restrictions, one for each of functions fk. ffx). and the resulting vector 2 in Eq. 9 therefore can have negative values, unlike the vector z in the above lemma.
14

---

Published conference paper at ICLR 2024
Remark A.1. Zeng al. (2022) refer to the generalized Seyman-Pearsee lemma, which looks very similar to the lemma above. In their formulation however, it is required that such 21..... ..... 2B exist that turn all inequality constraints into equalities. We avoid this requirement by using linear programming duality. In general, the optimal 21,....22 do not have to satisfy all constraints as equality, which extends the range of cases where our lemma can be applied.
Proof of Lemma I. Consider an operator F
(P(
R.K such that FR
((f1,R) R)...., ... (fK. k))². Below we write that a vector I satisfies a 2 0 if all its coordinates are non-negative, i.c E F for some With some abuse of notation will also say that
F Σ. Su. Denote S+ the set of L2 functions with pointwise non-negative values. Our problem reads as follows,
max max- (1, k)
s.t.
RES+, 1-KES+, FRS..
Consider the dual problem,
min = + (2, S.
s.t.
ZERK + A F
(15)
We have the duality property, for any feasible x primal and 2, dual, have
- (n, x) S = (A, x) S < (X,
In the linear programming these inequalities are called slackness condition. Assume for moment, that strong duality holds, i.e. there is x and z, À such that all inequalities turn into equalities. Then, both pairs are and 2, X are optimal for their linear programs. Furthermore.
R) = 0,
(R,2 -
Furthermore, it is straightforward to see that the optimal solution should satisfy almost everywhere
= (F" -). where for function (XX we denote its negative part 9 (x(X)== max(0, (X()). Simply observe that we must minimize each X(X) independently, while satisfying the condition = F(X) + 7| X)+ + X(X)= 2 0. Therefore, we have that the set {X F + + À >> 0} the same
as [X = F + > 0}. up to difference of probability O. So,
say that z F 17 > 0 yields
= P-a.s. and = + < yields = P-a.s. Assuming P(= + 17 0) = 0, we have that there is an optimal solution that has form 1f2 + 0}.
Now let us show the strong duality property. Consider the value v* = min Tb ((2 F + -)-,1), which is the optimal value in the dual problem, thanks to the identity for the optimal X given z. Thanks to its closed form, we show that stable w.r.t. the perturbations in the inputs F, that can reduce our problem finite dimensional linear programming (LP), where strong duality is known to hold.
Step 1 (bounded 2). First let show that any optimal is bounded. Since for the primal problem the feasible set has non-empty interior, we have that for every E p
a b + ((a) F) 0,
and notice that this is continuous function of a E Rk (follows from fo E L1). Therefore, the following number strictly positive
ZF
a T ((a 1)_,1)>0.
(16)
||]|| -1 1.20
Let us show by contradiction that any optimal solution = 2 to dual problem satisfies ||ж||| s (1ll 12/ Assume ||=|| > (lz), 2F. We have that for La with |a|| 1.
La LaTb ((La) TF F n) I(a ((a F), 1)) (n+ 1) (m-,1)
as long as L > (1ll. 1p. Since the objective value (n-.1) can be achieved with = 0 in the dual problem, so an optimal z must have norm smaller or equal to (Inl, 1)
Step 2 (discrete approximation). Next, consider step approximations of F and n in the following form. Select some partition I U... U Tas X, and set (x) = Em feom 1(X E Im) ,ñ() = Σm 7m 1(X E J. in way that || flll, I and [[ fa Tel S The fact that fE, E La is
15

---

Published conference paper at ICLR 2024
enough to find such approximation, however, since we require fk: Lg we can also assume that vi [ E mm]. fkm = E[fx(X) E Im]. where each In assumed have non-zero
probability. Let us consider,
i = min T b ((2 -)) =20
22 for sufficiently An optimal to this problem is bounded by ((/)), +))+)/((2r=)) ke) S . small We therefore can assume that both problems are minimized in [0, DJK instead of R for some D that does not depend on (small enough) E.
We have then (denoting by ý an optimal solution for 7) that
ë= b ((= -) 2 =Tb+ ((= + f))
DKE.
Similarly, 0 DKe. Let us look at the approximation of the primal problem. Let u' and correspondingly be the optimal values of the objective in the original and discrete problem. Let us take the discrete function ((X)= = Emm Km 1[ E [ where Rm is the elements of the vector that solves the discrete problem. Then, u² 2 (RR, 11) = - (R, 17) úi where we used the fact that averages over each interval In. Thanks to the strong duality of LP, for the discrete problem we
have that ū e. Thus, have shown that u² 2 ū ė 2 5* DKe, while u" v" is already guaranteed by weak duality. Sending E to zero proves the required strong duality property.
B PRACTICAL ALGORITHM
B. ALGORITHMS
Here we present the detailed algorithms we used in our experiments for DP and EO, particularly, for the choice of linear rule. In each case, we assume that validation set {(X,, Y,, A.)) Neal is given, based on which we choose the rule satisfying empirical fairness restrictions, whilst maximizing the empirical accuracy.
For the case of DP restrictions, we assume that we are given models ((Y ((A as well as evaluated probabilities Pr(A 0), Pr(A 1), which we can either evaluate on bigger training dataset (in case we have such access), or on the validation dataset. After we calculate the corre- sponding scores ((X.),
consider rearrangement 8(Xi,) 2 ... 8(Xix..) and test the thresh- olds s(Xi) ) one after the other. When move to the next candidate s(X,,+.) only need to spend (11) time updating the current empirical DP and accuracy. See detailed procedure in Algorithm
For the case of EO restrictions, we assume that we are given models X(Y P(Y, A|X), which two functions that do not necessarily agree as probability distributions. We also assume that we are given evaluated probabilities Pr(Y y, A a), a, E [0, Then, we calculate the corresponding scores $o. (X+). In order to choose the linear rule of the form s(X) 1 (up (X) + wi (X) > f} we consider two strategies. In the first one, we observe that we can restrict the search only lines that pass through two validation points, which exhaust the search of all possible pairs of accuracy and EO on validation. This, however, requires O(N3) to evalueate, so we consider an option to M sub-samples and only consider the corresponding MM - 1)/2 lines passing through every two of them. See pseudo-code in Algorithm 2.
For another option, fix K possible directions (wb, wi R such that w fi 1, and then for each of them consider the score x(X) = wo (X) x w & (X). This way we only need to choose the optimal thresholds c, similar the case of DP. By doing for each of the K directions, we can approximate the best line in O(NNeat log Nuat) time (which includes sorting the score values). See detailed procedure in Algorithm 3.
C ABLATION STUDIES
Here consider two ablation studies examine the robustness of our method when the estimated conditional distributions are inaccurate. We demonstrate it with DP as fairness criterion, and we report the mean and standard error of the results from 3 independent runs.
16

---

Published conference paper at ICLR 2024
Algorithm Algorithm for DP
Input: d: desired constraint for DP,
[(X,, Y,, A,) Noui, validation set, i=l
X. ())
evaluated Pr(AA = 0). Pr(A=11 =
Output: Threshold t" for modification rule x(X) 1(8(X) > }
1: Compute {Y; = 1(p(Y 1|x,) > 0.5) M.st
2: acc = AAc(Y)
3: counts[a] calculate frequency of Y = 1 in two groups A = 0,1
4: Compute {$(,) Neal based on p(Y] ({A[X), and Pr(A)
5: Compute argsort IDX [1...., NNa.i in ascending order, such that s(x,,) s(Xi,+1)
6: Best accuracy ACCmmax =
7: for in IDX do
8: set candidate t = ((x)
9: acc = acc + (1 (1 21 21 Yj)) counts[A,] counts s [Ay] Nodl -2Y,)
> Update accuracy > Update counts for group A A
dp counts [0]/Pr(A = 0) counts (1i/tttsssAPPAP/
12: if dp < 5 and acc > ACC max then
13:
=t
D Update best candidate
14:
ACCmax
15:
end
16:
end for
17:
return e*
C.I CORRUPTED p X) AND P(A[X)
In the first ablation study, we consider manually adding noise to ((|]X) and p(A For each X, sample from uniform distribution U Unif( (-n, the corruption (a is chosen to be 0, 0.01,... 0.1).
with controlling the intensity of In Figures 3 and 4, we plot the post-processed test target accuracy (Y) and post-proce tos--prcessed test DP after selecting the modification threshold on validation set based on corrupted X)Y and X)) for Adult Census and CelebA (with target "Attractive" and sensitive attribute "Male") respectively. Across all corruption intensity a, test DP still tends to be below or fluctuate around its desired constraints o's, while we only incur minor drop test target accuracy (within % across most a's). This demonstrates the robustness our post- processing algorithm even when the estimated conditional distributions do not match the ground- truth well.
83.0
10
82.8
82.5
Accuracy (56)
82.2
8=10%
8-5%
82.0
6-1%
4
81.8
81.5
0.00
0.02
0.04
0.06
0.08
0.10
0.10
(a) Accuracy (Y) (%)
(b) DP (%)
Figure 3: Test set performance of our method with corrupted ((Y and p(4 on Adult Census dataset.
17

---

Published conference paper at ICLR 2024
Algorithm 2 Algorithm for EO
Input: d: desired constraint for EO,
M: the number random samples from the validation set {(X,, Y,, A N validation set,
[(Y] p(Y, )(
evaluated Pr(Y y, - a), E {0,1}
Output: Linear modification rule xxX)
1: Compute f8; [ppY 1|x;) > ( Nuat
2: Compute
Ji=1 based on X)) p(Y, A|X) and Pr(Y,
3: Randomly sample .M instances from the validation set: {(X, Ym) mn)
4: Construct the set of linear rules to search with index:
size: M(M-1)
5:
SM (kx.1){& <1, k,1= 1...... MM
6: Best accuracy ACCmax = 0
7: for (k, in SM do
8:
1e(h (X)
(1(X) (x }
( ( xox(()=o(
9:
for = 1,... Naal do
if x (X,, then
11:
Y;
D Modify when (8.0 (X.)
12:
else
13:
Y = Y
b Do not modify when (4.1) (X,)
= (X,)
14:
end if
15:
end for
16:
Compute validation ACC(1.(k.)) and (xO(.(())) based Y
17:
if (k))()))) < 5 and ACC(1(()))) ACCmas then
18:
x(X) = (X), ACC (CC()e(k)))
19:
end
end for
21:
return x(X)
77
10
76
8
Arcuracy (%)
75
DP
74
73
6=5%
2
6=
0.0
0.00
0.02
0.04
0.06
0.08
0.10
0.00
0.02
0.04
0.06
0.08
0.10
(a) Accuracy (V) (%) vs
(b) DP (5) vs
Figure 4: Test performance of method with corrupted ((Y|X) and p(AIX)
CelebA dataset (target: "Attractive", sensitive attribute: "Male").
C.2 STRONGLY REGULARIZED ((A())
In the second ablation study, we reduce the discrimination power of the sensitive classifier by train- ing ((AAX) with stronger regularization. Specifically, for CelebA (target "Attractive" and sensitive attribute "Male"), we train multiple sensitive classifiers with different weight decay X increasing from 0.001 to 0.1. Figure plots the test accuracy of sensitive model ş AA] X), post-processed test
18

---

Published conference paper at ICLR 2024
Algorithm 3 Alternative algorithm for EO
Input: ò: desired constraint for EO, [(X,, Y;, A,)) Neud; validation set, i=l
X) p(Y, A
evaluated Pr(Y y. a), a E {0,1}
Output: Threshold t* and direction (wy. wf) for modification rule x(X) 1( +
& > }"
1: Compute {Y; (p 1|x;) > J
Nust
2: counts g a| = calculate frequency of Y 1 in all four groups (Y, (y,
3: Compute (X:), 81 (X.)) Neat based on pXY|X), p(Y, A(X), and Pr(Y, A)
4: Fix set of directions WK- {(wb w1 ) )ak= RR,, (1(wb) (8) w
(k) )||
5: Best accuracy ACCmax
6: for (wo, w1) in WK do
7: acc = AY)(Y)
8: Compute scalar scores 8(X;) (X,) wis1 (X;)
9: Compute argsort IDX = {i,,.... &N...) in ascending order, such that s(Xi,) 2 8(X1541)
for j in IDX do set candidate t = {(x))
11:
12:
Update accuracy count y,, A,] count Aj] + NoJ 2\,) Update counts group Ay)
+ Noa (1 21 =)})
eo0 count [0. 0//Pi(Y = 0, A = 0) count (0, 11/Pr(Y 0, A A=
14:
15:
eo1 = count(1, On/ntt1o//Pr((--- 1, 0) count [1, 11/Pr(Y = A, 1)
e0 max(eo0, eo1)
17:
if eo < 5 and acc > ACCmax then
18:
ACCmax = acc
b update best candidate
19:
t" =
20:
(wō, wf) = (wo, w1)
21: end if
22: end for
23:
end for
24:
return Modification rule x(X) = =1 1( + (X) > tー}
target accuracy (ý), and post- postepercessed DP after modification against À respectively. One can see that as À increases, the sensitive accuracy given by x(A[X) drops. However, with less accurate ((AAX), post-processed target accuracy (Y) and DP after modification does not seem be notice- ably hurt. Interestingly, when increases moderately, although ((A(X) becomes less accurate, the post-processee target (Ý) accuracy can even be improved. This further confirms the robustness of our processoe modification algorithm.
27.0
6-13%
9-56
765
2014
19
37.3
2663
66.5
25.0
765
45.
0.22
0.24
0.06
5.03
0.00
(a) Accuracy (A) (%)
(b) Accuracy (Y)) (%) vs
DP (%)
Figure 5: Test set performance of our method based on p(A[X) trained with different weight decay on CelebA dataset (target: "Attractive", sensitive attribute: "Male").
19

---

Published conference paper at ICLR 2024
C.3 SHOO CLIP AS AUXILIARY MODEL
Table 2: Experiment with CLIP: Accuracy (%) and Equalized Odds (EO) (%) CelebA with target attribute "Attractive" and sensitive attributes "Male". Main un- constrained model X( is trained on CelebA, while auxiliary model p(Y, A A is evaluated from CLIP's similarity to text prompts.
ACC
EO
00
81.1
27.8
10
81.0
10.0
Validation
5
80.4
5.0
1
80.0
1.0
81.6
24.1
10
80.5
6.2
5
79.9
1.0
Test
1
79.1
5.4
Here, consider for CelebA the classification problem with target "Attractive" and sensitive at- tribute "Male", with EO constraints imposed. We train only the target model p(Y on the original CelebA data, while the pair A(X) is evaluated from CLIP. Namely, consider the following prompts,
prompt_11 "a photo of Attractive Male"
prompt_10 "a photo of Attractive Female"
prompt_01 "a photo Unattractive Male"
prompt_0l "a photo of Unattractive Female"
For given prompt and image X, let sim(X, prompt) denotes the CLIP's similarity, We consider the following probabilities,
exp(sim(X, prompt-ij) Σ (.je(( exp(sim(X X, prompt if)
P(Y i j|X)
We then feed these two models into Algorithm 3. Results are reported in Table 2.
D RESULTS IN TABLES
We present numerical results (meantstandard error) for all experiments on CelebA in tables.
20

---

Published conference paper at ICLR 2024
Table 3: Accuracy (%) and Equalized Odds (EO) (%) on CelebA with target attribute "Attractive" and sensitive attributes "Male" under different desired levels (ō's) of EO (%) constraints. Boldface is used when MBS better than Park et al. (2022) both in terms of accuracy and EO.
6
ACC
EO
00
81.320.1
26.8
10
80.8+001
9.9+0.0
Validation
5
80.2+002
5.0+0.0
1
79.6=
0.7
Hardt et al. (2016a)
71.3+1011
0.5
00
81.910.3
23.810.8
10
80.9+0.2
6.74
5
80.1+0033
2.2+
Test
1
79.3=0.3
4.0+0.44
Hardt et al. (2016a)
71.720.3
3.820.2
Park et al. (2022)
79.1
6.5+0.4
Table 4: Accuracy (%) and Equalized Odds (EO) (%) on CelebA with target attribute "Attractive" and sensitive attributes "Young" under different desired levels (8's s) of EO (%) constraints. Boldface is used when MBS is better than Park et al. (2022) both in terms of accuracy and EO.
ACC
0O
81.3+0.0
27.
10
80.2.0.11
10.0+1.00
Validation
5
79.2:1..1
4.910.1
1
78.2+0.2
1.0+0.0
Hardt al. (2016a)
70.4
0.4
82.0=0.0
24.7+00.8
10
79.710.1
10.9
5 1
78.2=#0.0
6.6+0.8
Test
76.9+0.0
2.0+0.7
Hardt al. (2016a)
71.4+10.3
3.440.7
Park et al. (2022)
79.1
12.4
Table 5: Accuracy (%) and Equalized Odds (EO) (%) on CelebA with target attribute "Big_Nose" and sensitive attributes "Male" under different desired levels (ō's) of EO (%) constraints. Boldface is used when MBS is better than Park et al. (2022) both in terms of accuracy and EO.
ACC
EO
82.910.6
43.3+2.1
10
82.7+0.1
9.910.1
Validation
82.3++0.1
5.0+0.00
81.8++0.1
0.9+0.0
Hardt et al. (2016a)
76.240.2
0.5+0.2
8
84.1#0.1
44.9+22.5
10
83.510.2
8.4.1.22
83.
4.3+--0
Test
83.2
1.740.3
Hardt et al. (2016a)
78.240.0
0.5+0.0
Park al. (2022)
82.910.4
4.710..5
21

---

Published conference paper at ICLR 2024
Table 6: Accuracy (%) and Equalized Odds (EO) (%) on CelebA with target attribute BBig.Nose and sensitive attributes "Young" under different desired levels (d's) of EO (%) constraints. Boldface is used when MBS better than Park et al. (2022) both in terms of accuracy and EO.
6
ACC
EO
00
03.5
21.5+0.1
10
83.3#0.00
9.7+0.1
Validation
5
83.0=0.1
4.940.1
1
82.2=0.2
1.0+0.0
Hardt et al. (2016a)
79.0=1.00
0.6.0.11
00
84.520.1
21.0=0.1
10
84.3+0.1
10.6+-0.6
5
84.2+0.1
4.1+0.88
Test
1
83.6=0.2
2.4+0.6
Hardt et al. (2016a)
80.1
1.340.3
Park et al. (2022)
84.1
4.8+0.3
Table 7: Accuracy (%) and Equalized Odds (EO) (%) on CelebA with target attribute BBag_Under_Eii and sensitive attributes "Male" under different desired levels (6's) of EO (%) constraints. Boldface is used when MBS is better than Park al. (2022) both in terms of accuracy and EO.
ACC
84.5=0.0
19.8+3.8
10
84.41:..0
8.3
Validation
5
84.2400.1
5.010.0
1
82.3+0.1
1.0+0.0
Hardt al. (2016a)
79.8=0.2
0.4
85.220.1
19.0#3.7
10
85.0+0.0
8.240.7
5 1
84.7=0.11
5.6+0.2
Test
83.1#0.0
1.740.2
Hardt al. (2016a)
80.2+0.2
1.740.4
Park et al. (2022)
83.4
3.0.0.44
Table 8: Accuracy (%) and Equalized Odds (EO) (%) on CelebA with target at- tribute "Bag Under__yee and sensitive attributes "Young" under different desired levels (6's) of EO (%) constraints. Boldface is used when MBS is better than Park al. (2022) both in terms of accuracy and EO.
ACC
EO
0C
84.6+0.1
18.2+1.1
10
84.6=0.0
9.9+0.0
Validation
5
84.4+000
5.0+0.00
1
83.0+0.11
1.0+0.0
Hardt et al. (2016a)
81.120.2
0.5+0.2
00
85.6+10.3
13.7+1.9
10 5 1
85.1
9.5+1.0
85.110.0
5.4.0.5
Test
83.610.2
1.8+0.3
Hardt et al. (2016a)
81.7+0.2
1.610.5
Park al. (2022)
83.5+0.3
1.6+0.3
22

---

Published conference paper at ICLR 2024
E SENSITIVITY ANALYSIS FOR COMPOSITE CRITERION
For the sake of convenience, we assume that the classes are valued as {-1, +11 instead of 0, 1. In
such a case, the unconstrained optimal classifier that has the form Y (*()) = sign(f(Y = -0.))
and constrained optimal classifiers have form Y (X) sign (E, (X5; - 1). i.e. ones
that have highest accuracy subject to restriction CC I 6.
In the MBS implementation (Section 3), we replace the unknown ground-truth probabilities p(Y|X) and p(A AIX) for EO) with their estimations, which we denote as p(Y]X) and ((A(X) (Ø(Y, A)))), respectively. The empirical version of the unconstrained classifier has the form Y(X) = sign(f(Y = 1[x) - 0.5) and we are looking for a classifier of the form Yx(X) = ((X)sign(2 (X) - 1), i.e. our goal is to fit set of k parameters 7= (75) E RR Recall that the composite criterion has the form Eq. 4, and the score functions are defined in Eq. 8, Eq. 7.
We assume that we choose the score weights Y = (n...., ?rk) based on the observed validation sample {(X,, Y, A1; Azi.... | of size N by maximizing the corresponding empirical ac- curacy, while maintaining the restriction on empirical parity. Set,
1
Acc(Y)
1[,, 1[y= = +(X.).
N
==1
CC(P) = mAx jSk
(Y)
N
1(Ax = az}
1(A; = b,}
3,00 = N
Σ
(V())=++))
=
Pr(Aje = =a)
Pr(Aji = b,)
For given level 8 > 0 we fit the parameters validation follows
arg max (Ace((x) DP(()) S 63.
(17)
The goal of this section is demonstrate that, if we provided an accurate enough estimate f and a sufficiently large validation set N, we can have guaranties for the empirically derived estimator (X)). We deliberately do not touch the question of what the estimation error of p(Y, A could be. which may depend on various factors such as training sample size, input dimensionality, and complexity of the parametrized model (Vapnik, 1998; Boucheron et al., 2005), as well as the training algorithm (Bousquet & Elisseeff, 2002; Hardt et al., 2016b; Klochkov & Zhivotovskiy, 2021).
Theorem 2. Assume the following set of conditions:
1. We have estimation of conditional probabilities that satisfy moment bounds (for p 2 1),
EV/1E(Y = 1|x) - p(Y = 1|X)P S Sp,
E / =a,(X) p(A, b, S Epp
Vj 1, ......... k
EV"MAA, bb,xx) - -((A- = bb,())p S Ep
Vj= = -1...., k;
2. The distribution satisfies the margin assumption (x) > 17" for all X (known as Mammen- Tsybakov condition (Mammen & Tsybakov, 1999));
3. All groups have significant size: we have Pr(Aj = a,), Pr(A, =,, 2 Po:
4. Score distribution regularity: the distribution of scores s(X) (s (X), ................................ sk (X)) is supported on a ball {s E R² ||s|| < B); Moreover, for every || = 1, the density of
Y s(X) is bounded by constant
5. The weights corresponding to optimal Yद under CC(Y;) S 5/2 satisfy lh S R:
,Po, There is a constant C =C(ii, Po, L, R, B,ō), such that, for any r E (0, 1) that satisfies,
t log((N//r) + (Vkep) 1-
c
S
(18)
N
23

---

Published conference paper at ICLR 2024
we have that, with probability at least r,
Acc(Y²) 2 Ace (0) C ((Vkk))
k log(kkN/)
(19)
klog(kN//)
(C(Y)) CV
N
where Acc (e) the accuracy of the optimal classifier under the constraints CC S
Before move requires that we have good estimation of probabilities in the form of moment bound. We note that bounds of this form often appear in theoretical analysis of non-parametric regression Tsybakov (2009), including ones based on neural networks Hu et al. (2021), Although they are standard in non-parane non-parametric regression, there no way to verify them in practice without making structural assumption about the underlying distribution. The margin condition is very popular in Statistical Learning Theory, and in our particular case, it allows controlling the accuracy of the estimator under perturbations of the conditionals. We note that Denis et al. (2021) also assume form of margin condition for the multi-class fair classification. The third condition is somewhat realistic and simply makes sure have appropriate criterion evaluation based the validation sample. The fourth condition a stronger version the condition Theorem 1, where we require that the distribution of 7 s(X) is continuous. We prefer to have much stronger version to avoid technical difficulties in the proof. As for the fifth condition, is pretty much guaranteed that the vectors " are bounded, which we show for instance as part of the proof (see Eq. 16 and the line below it). However, it is hard to precisely characterize the value of / based on characteristic of this distribution, so we prefer state condition.
the proof, let briefty comment each condition. The first condition
Furthermore we note that practical implementations based on Bayes optimal classifiers are often based on closed form derivations of the optimal weights Denis al. (2021); Zeng al. (2022). We do not provide these, instead our method treats the bias scores as features when fitting the modification rule. As a result, the error of estimation of the conditionals does not propagate as much into the fairness constraint. See also some empirical studies in Appendix C.
Proof. We compare the accuracy and composite criterion of Y and Yy in three steps:
1. Approximation population level: we bound the discrepancy in the population statistics (Acc and CC) of estimators Y, and Y, i.c. how the difference between conditionals
(x) and its estimation propagates into the accuracy and composite criterion.
2. Approximation on validation set: we then compare the population statistics and validation statistics (Acc, CC) simultaneously for all estimators Y; Yz-
3. Connecting validation and population: once the first two steps done, the stan- dard trick in empirical process theory to connect the classifiers that are optimal in popula- tion and in validation.
Step 1 (approximation on population level). We first check how the population accuracy and DP compare between the optimal (X)) and the one based on the estimated probabilities {X).
For the unconstrained classifiers, thanks to the margin condition, we have by Markov inequality:
Pr(Ý # Y Pr(p(Y]x) 0.5 < x( or p(Y]x) 0.5 < ((Y)x))
< Pr(pp(Y XX) >
In particular, this implies that Ace(Y)) 2 Acc(Y') (ep In order to compare the accuracies
of constrained classifiers, we need further compare the modification rules. Denote (X) sign(y) s(X) 1} for the ground truth score, and consider empirically derived rule (X)
24

---

Published conference paper at ICLR 2024
sign(y' (XX)) - 1}, where 6(X) are derived by replacing p(A, azlx) and p(A, b,(X) with p(A; = 0zlX) and i(Aj = by X), respectively. Let also (X),, ri() be the corresponding substitutes for [z(X), (X)) We have,
Pr(Hi RT) = -Pr(7' s(X)
= -Pr ((X) E [1 [1+7' (s(()=((sxx))))))))))>< - ((X)): 11)
(P [1/||/| (s(X) - s(X): 1/|lr/l),,
where we denote the normalized weights 7 >/ Taking the union with the opposite inequality, we get that
Pr(my # Ry) S Pr T s(X) E [1/l||| - 1 (s(x)) I7 -(()))))
(20)
To proceed, we want to bound the value v (xx) - & () Firstly, it is straightforward to see that E' E//1/7 11"² s 2pp. For the f-score, we see that
ا 118 + 1 - a = x,1xx)++ 1
lo(A = - Po
b = 6,1x)1
Pu so that by the triangle inequality,
Po
1S -10 S -1
FE 11¹
+ +2p Ep S
32p
Po'j"
Then, we can write
E'/10A (s(X) - 8(X))) s E//D
L(f+ - 85)5
+ EE/DD
n [ Σ
17
3
p/2
- - 1/
2v
Σ 1f3 f312
k//p |17
1/
"
Pot)
3/ Ep.
Porj"
Using the Markov inequality, this gives us the bound for any r E (0, 1),
Pr 17 - ((X))))(xx)1-- Sr-1 5vk
Por Ep 2 pp.
Using the moment bound on 1) - r). we can also lowerbound i)
4Ep
Pr(A 2 n"" /2) < Pr 7| n2)
11t
Taking the union bound of the two last displays, we get that
GV4- po(n~))00 Sp
45 p
Pr -(x(x))s(xx]lle
p.
11
Now, we can plug this back into Eq. 20. We get that,
Pr(Ni + Re)) -1 6v
45 p
P
Po(n") yz Ep + rd +
Optimizing 112LVkee/(pmm((( we get that
1-1/(#11
LVKEe po(1)²}3
4 p
P
Pr(ky + Roy) S 24
+
n1
25

---

Published conference paper at ICLR 2024
We now can derive using the triangle inequality,
[Ace((g) - Acc(Y)) & Pr(Vy + v2))
- Pr(Y + Y") + Pr(ni + Rn)
1-1/(pt1)
4ēp
P
LVKEp po(TT*)2
$ 2
+4
112
$ L, (v -
(21)
where we assume that Ep 24 24max(LL/pp))) (ponn)/pp))))))))))))))))) (I 1). Similarly,
7²/4 (condition Eq. 18) and set L1 = 4/1/" +
(CC(K)) CC(G))) & max (C,(g)) C,(5,) s ro Pr(Y, # xYG) Ta T2(Vke))) 2
;
where L2 -2=10 Po L
Step (approximation on validation set). The next step is derive uniform bounds for the empirical accuracy and CC. We have,
N
Acc(VG) = 2N
(, -x)
11) 2
1=1
1
Acc(VG)) = 2N
Y (x.)) s(X;) 1) +
1=1
and notice that Evst Ace Yn)= Ace(Yr) and Ewat Ace())) Aec(( where we conventionally denote Evst as the expectation (and below Prest for probability) w.r.t. the validation sample.
Lemma 2 (Vapnik (1998), Theorem 5.3). Suppose, we have bounded function f(Z) E [-1. 1], and k arbitrary functions 91 (X), (2)))((((,.).))))))))))))) ..... 9..(.9(.. (X), and consider class of functions (X)
(.........e.
f(Z) sign (2, 739, (2) 1} Y R. Let X1, XI,..., XN be i...d. Then, we have with probability 1 - 5 that for each y
Σ 12,2,) 1 EA,(2) s &LoV klog((N/0)
N
Proof. We simply need observe that the shatter coefficient of set (X)(X) < 7 is bounded by (N +1)+t1 then apply Theorem 5.3 from Vapnik (1998).
For 7 = (X,Y) set S(2) = v(xV1/2, gz(7) = x,(X) to control the ac- curacy of Yx(X) and f(z) = (x)x)//2, (z(Z) = s;(X), to control the accu-
racy of (x)). Furthermore, for Z
Pr(A, b(A (X.,,A)....AAA)) we can set f(Z)
Ý(X) [Pr(A, = - = =
/2, g(Z) sign(yT 1) get concentration of disparity C, for (X)),, ), and similarly for Y (X). Overall, we have that for any E (0, each of the bounds holds
<log(N/r) N klog(N/r))
Acc(Yr)) Acc({²) S LoV
W. P.
2 1--
AcC(Y;)) - Acc(Y;))
S Loo
w.p. 21-r
N
A: llgg(N/r)
(3,(5,) - c,(Kg)
< Lopo
w.p. 21-r
N
A: llg((N/r)
(,00)) (C)7)))(()))))))
S Loppt
w. p.
21-r
N
26

---

Published conference paper at ICLR 2024
we take r/k for the bound on each C3 and then take a union bound, we obtain a bound on the difference in the composite criterion. Overall, we have that with probability at least 1 - r,
(/rr(N/r) N
Acc(V,) - Aca(TT))
s Lo
(l/g(N/r)
) - Aco(X;)) s $
N
k klo((kN/r)
(0(P)) - cc(rg) T
N
1 klog(kN/r))
(C(Y))- -C(x))
LLa
N
where we set L3 = LoPo" Vlg 4.
Step 3 (connecting validation and population). Let y corresponds optimal Y under CC((G) S and denote its accuracy (6).. Then, let y corresponds to the the optimal (c)();)) under the constraint CC(Y;) S 8 - e. the end this section we show that
Acc(Y?)) = Acc" (6- c) 2 Ace cR for c c<8/2,
(22)
and let us assume for now that it is true. Set = La klog(kN/r) ,2 L28p 1-t--1((+1) +2. and note that by assumption Eq. 18, 8/2. Then, CC(Kx)) S CC(Kx)+ Lav klog(kN/H)
CC(Y))+ + 6, which means that the problem Eq. feasible, and also Acc(Yz) 2 Acc((Ga)) 2
Fg. 21 Acc(Y)) - 62 Acc - -)) Finally, it implies that Acc(Y²) 2 Acc (6) - (2 R) CC((4) v 61
Acc(Vrr)) -1 2
Substituting e, 61, we finally get the bound stated in Eq. 19.
Check of Eq. 22. Let denote 7o be (some) optimal set of weights, corresponding to the classifier that maximizes the accuracy under restriction CC(()) & 5. We show that for e < 6,
Acc(ā e) Acc(8)= < ell76-ell1.
which thanks to condition 5. yields Eq. 22. 22. To show that, we need to recall the proof of Theorem 1, where Ys comes from the dual LP problem (Lemma 1), and the value Acc" (6) corresponds to the maximal objective in the primal and minimal objective in the dual LP. Changing ó + simply
1; where 1 denotes -1s
means that we change the vector
Eq. 15 to a new Inew
-
column with A ones. Let new nnw denotes the solution to dual LP with 6 replaced by gnew in Eq. 15. Then, since in the dual LP the constraints do not depend on b, the value geew Xnew serves an upperbound for the old problem. Therefore, Acc(ō) Acc(E E) new (bnew - < ellys-ell el since the corresponding Ya-g has the coordinates 2j - 2jtk-
27

---

Published conference paper at ICLR 2024
F COMPARISON WITH REDUCTION METHOD (AGARWAL ET AL., 2018)
Here, we include Reduction method (Agarwal al., 2018) additional baseline, and we use the same network architecture and hyperparameters as for the other methods.
83.0
82.0
82.0
Accuracy (%6
81.0
Accuracy
80.0
79.0
78.0
78.0
MBS (Ours)
MBS (Ours)
Agarwal
Agarwal et al.
77.0
Zafar et
Zafar et all
76.0
Jiang
Hardt et al.
0.0
2.5
75
10.0
12.5
15.0
17.5
12.0
DP 1%)
ED (%)
(a)
Figure 6:
Accuracy (%) vs (a) Demographic Parity (DP) (%) and
(b) Equalized Odds (EO) trade-offs on Adult Census.
Desired
(unconstrained), 10%, 5%, and 1%.
28


Reviews:
[{"review_id": "2egQQo7uSg", "reviewer": "Reviewer_in91", "summary": "This paper deals with the problem of fair classification where the goal is to find the classifier with maximum possible accuracy under constraints on the disparity in the performance of the classifier across groups with different values for some protected attributes. The paper proposes a post-hoc approach to achieve this. \n\nFor binary classifiers: First, an unconstrained Bayes optimal classifier (Y'(X)), which maximizes accuracy, is learned. Then post-hoc, a modification rule is used to obtain a fairness constrained Bayes optimal classifier (Y''(X)) by modifying the output of Y'(X). This modification is done by mapping each instance to a probability with which the fairness constrained classifier disagrees with the unconstrained classifier. \n\nThe paper proposes a definition of such a modification rule which is defined by an instance-level bias score which the authors propose, together with a measure of the uncertainty of the unconstrained classifier on a given instance. \n\nThe authors propose definitions of the bias score for each of three popular fairness constraints, and show how the resulting modification rules leads to classifiers that satisfy the fairness constraints. The authors point out that unlike previous works, their approach enables us to find classifiers satisfying Equalized Odds fairness constraints.", "questions": "None", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper proposes a novel way to modify the output of the unconstrained Bayes optimal classifier post-hoc in order to satisfy fairness constraints. While this approach has been previously studied, I believe the instance-level bias scores are novel.\n- The main significant technical contribution is the ability to satisfy Equalized Odds fairness constraints.\n- Besides these, the characterization of the optimal modification rule in Theorem 1, which has the form of a linear combination of bias scores, one for each protected attribute is also very interesting. In particular, this enables the approach in Section 3 where together with an auxiliary model that estimates the values for the protected attributes, the bias score for examples in the test set can be computed without access to the values of the protected attributes.\n- Together, I think the conceptual and technical contributions are both interesting and significant, and the topic is clearly relevant to ICLR and the research community working on fairness in ML.", "weaknesses": "- No major weakness apart a few issues with the writing and minor typos that can be fixed with a revision.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wEWOoVTdMv", "reviewer": "Reviewer_ErzV", "summary": "This paper considers the problem of fair learning through post-processing: given an arbitrary predictor, we would like to post-process its predictions such that the new predictions satisfy a notion of group fairness, say demographic parity, while maintaining good accuracy. Standard methods for fairness through post-processing come up with a predictor that takes the sensitive attribute as input, and therefore, requires access to sensitive attributes at test time. This is not desirable because, in practice, laws and regulation might prohibit access to sensitive information. This paper introduces a new post-processing method that does not require this access; instead, it works with a conditional distribution of sensitive attributes (conditioned on all other features). More formally, let $(X,A,Y)$ represent features, sensitive attributes, and labels. Given a base classifier $\\hat{Y} (X)$, a conditional distribution $\\hat{P} (A,Y|X)$, the paper introduces an efficient algorithm that gives us a new classifier $\\hat{Y}’ (X)$ that satisfies a desired notion of fairness, while approximately preserving the accuracy of $\\hat{Y}$. They experiment with their proposed algorithm on Adult, COMPAS and CelebA data sets and find that in most cases their proposed algorithm outperforms (some) existing fair learning algorithms.", "questions": "-Do the theoretical results rely on the fact that $\\hat{Y}$ is the Bayes optimal classifier. $\\hat{Y}$ is introduced as the Bayes optimal on page 3 but later on is used as any predictor. It would’ve been better if $\\hat{Y}$ was initially introduced as any predictor that we’d like to post-process its predictions.\n\n-Can the validation data set be used to learn the conditional distributions? In practice we only have a pre-trained classifier and do not necessarily have pre-trained conditional distributions. If your method allows using the same validation set to learn these distributions, then all you’d need is the pre-trained classifier, increasing the flexibility of the proposed method.\n\n-The title of the paper seems misleading. What does “optimal” mean here? Post-processing algorithms are known to be sub-optimal in general because their guarantees are benchmarked against the base classifier (e.g., see your theorem on page 7). Theoretically, in-processing methods achieve the optimal tradeoff between accuracy and fairness because they directly solve the constrained optimization problem instead of looking at the specific class of models that are derived by post-processing another model. This does need a clarification in the paper.\n\n-Why does Hardt et al. (2016) have lower performance than your proposed method in the experiments? Hardt. et al. (2016) solves the same post-processing problem with the extra flexibility that the sensitive attribute can be used as an input to the model. Shouldn’t that just lead to better accuracy/fairness tradeoff?\n\n-------\nI will increase my score if questions/weaknesses discussed above are addressed properly.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-A key challenge in fair learning is access to sensitive attributes. This paper acknowledges the fact that sensitive attributes may not be accessible in practice, and therefore, proposes a post-processing algorithm that does not require such access. To the best of my knowledge, the proposed method is original and has significant impact.\n\n-The authors accompany their theoretical guarantees with an extensive experimental analysis to show the efficacy of their algorithm.\n\n-The paper is well-written and is easy to read.", "weaknesses": "-While the proposed method does not require access to sensitive attributes at test time, it still requires the conditional distribution of sensitive attributes $P(A|X)$, or a good estimate of it. It is not clear if this complies with laws and regulations: a company can still use their model of $P(A|X)$ to get good estimates of individual’s sensitive attribute. I’d like to see a discussion of this in the paper as well.\n\n-Overall, the assumption that we have access to $P(Y, A|X)$, or a good estimate of it, could be strong in practice. For example, if I know a good estimate for $P(Y|X)$, I might as well use that as my predictor. Also, how are these conditional distributions learned? In practice, we observe every $x$ only once, so these probabilities are 0 or 1 on observed data, unless we work with parametric models like logistic regression. But which parametric model should we use here when the underlying unknown data distribution could be arbitrary? Also, how are these models chosen in your experiments?\n\n-The paper claims that the performance of their method is better than “in-processing methods”. Is it better than all in-processing methods or just a few? This sounds like a very strong claim because, generally speaking, in-processing methods do achieve better performance than post-processing methods. Additionally, the most popular in-processing method for fair learning is given by Agarwal et al. 2018 (titled: \"A reductions approach to fair classification\"). Unfortunately, their algorithm is not included in the benchmarks for experiments. I would like to see a comparison of the two methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jzXAiP1yYq", "reviewer": "Reviewer_cdR8", "summary": "The paper characterizes the optimal classifier under fairness constraints as a simple postprocessing modification rule over the Bayes optimal classifier. Comparison with standard baselines demonstrates competitive results on three datasets.", "questions": "- Is the base model used by MBS the same as those used by the baselines? Are the Zafar et al. (2017) results of Fig. 2 based on a constrained MLP?\n- How was $p(Y,A|X)$ estimated when using MBS on CelebA?\n- Do you see any reason why Hardt et al. (2016) would outperform on the Fig. 2 results, and achieve such lacklustre results on Table 1? Given that we see some variance/unreliability on fairness for MBS with $\\delta=1$, can the even stricter constraint target by Hardt et al. (2016) (which uses $\\delta=0$, right?) be related to its underperformance?\n- Could you please clarify the main differences to Zeng et al. (2022), as it seems to tackle exactly the same problem.\n> [Zeng, Xianli, Edgar Dobriban, and Guang Cheng. \"Bayes-optimal classifiers under group fairness.\" arXiv preprint arXiv:2202.09724 (2022).]\n\nMinor:\n- Ticks for horizontal axes in Figures 3, 4 and 5 are miss-labeled.\n  - Also, clarify that corrupted $p(Y|X)$ is the left figure, and $p(A|X)$ the right figure in the legend or plot titles.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Novel characterization of the optimal fairness-constrained classifier as a \"simple\" modification rule over the Bayes optimal classifier.\n  - Group-specific thresholding (Hardt et al., 2016) is a specific case of this rule where the sensitive attribute data is known at inference time; proving that simple thresholding is optimal for DP and EO when this information is known (with Bayes optimal scores).\n  - Specific examples given for DP, EO, and equalized odds.\n- The proposed method does not need explicit access to the sensitive attributes at inference time, but can also be given this information if available.\n- Experiments conducted with relevant baselines on three well-known datasets, supporting the main paper claims.\n- Additional sensitivity analysis and ablation studies on the robustness of the method to miss-estimated $p(A|X)$ or $p(Y|X)$.", "weaknesses": "- No code or results files are provided for the experiments; neither an implementation for the proposed method. This is largest point against the current version of the paper, as properly reviewing the work required checking some experimental details.\n\n- Given that postprocessing baselines achieve Pareto dominant results in Fig. 2 (expectedly, as they have access to the sensitive attribute at inference time), it would be interesting to add partially relaxed results for these baselines for a more direct comparison (as done for the Zafar method).\n\nSome comments regarding the CelebA results on Table 1:\n- The proposed method is fitted with relaxed fairness constraint fulfillment ($\\delta > 0$), while baselines are not ($\\delta=0$). This does not seem to be a completely fair comparison.\n- I'd find the small metric differences more meaningful if the \"bolded results\" rule were based on pair-wise statistical significance tests.\n  - e.g., the bolded results of Table 5 are perhaps not significant.\n\nOther notes:\n- The compatibility with multiple over-lapping sensitive sub-groups (Example 3) is definitely a major advantage, but no experiments are shown for this evaluation setting.\n- It'd be interesting to test against a simple baseline of using Hardt et al. group-specific thresholding using the same estimated $p(A|X)$ instead of the true sensitive attributes at inference time.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gkjBJ5J1mA", "reviewer": "Reviewer_v53s", "summary": "This paper proposes a post-processing method for achieving fairness on binary classification problems, which leverages a representation result for the Bayes optimal fair classifier as a (linear) function of the bias scores, which are given by a function of several conditional probabilities.  The results cover the fairness criteria of DP, EO and EOp, can handle multiple sensitive attributes, and most notably, is applicable to the attribute-unaware setting (i.e., sensitive attribute is not observed during inference).\n\n---\n\nPost-rebuttal: I have increased my score, although I feel the assumptions for theorem 2 are unnecessarily strong/complicated.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- As mentioned in the summary, the results are general in that they cover DP, EO and EOp, can handle multiple sensitive attributes, and most notably, is applicable to the attribute-unaware setting (i.e., sensitive attribute is not observed during inference).\n- The framework is flexible in allowing for composite criteria.\n- The authors provides some qualitative interpretation of the representation result (theorem 1), namely the bias score, which practitioners may find helpful.\n- Paper is well-written, and the main body is mostly easy-to-follow.\n\nAll in all, I like the representation result, which I think is neat in that it encompasses many learning settings, but my rating is limited by my opinion that the current version of the manuscript is incomplete, as detailed in the weaknesses.", "weaknesses": "1. It is not mentioned how nonbinary sensitive attributes are handled.\n\n\t- Related: How is the sensitive attribute of \"race\" in the COMPAS experiments, which can be one of three categories (African-American, Caucasian, Other), handled?\n\n1. I am skeptical about the scalability of the proposed method to large datasets and more sensitive attributes.  It appears that the time complexity would scale exponentially in the number of sensitive attributes, i.e., $M^{K}$.\n\n\t- I see that $M$, the number of samples on which the decision boundaries are considered, is set to no more than 5000 in the experiments.  But practical ML datasets nowadays can contain tens of thousands to millions of examples.\n\t- Could the authors also report and compare the running time of their code?\n\t- Also, if $M<N_\\textrm{val}$ is used for selecting the boundaries, then there should be a term involving $M$ in Theorem 2 (more on Theorem 2 below)?\n\n1. Theorem 2 is very important as it provides fairness guarantees for the classifier obtained through the procedure.  But the result looks wrong to me, and seems to have a discrepancy with Algorithm 1.  The proof is also very hard to read, containing several typos.\n\n\t- DP should depend on $\\epsilon_p$ (attributed to the error in $\\hat p(A=1\\mid X$), but this dependency is absent in eq. 14.  Digging into the proof, I see that it is hidden with the statement that \"$\\epsilon=\\epsilon_1+\\epsilon_2$, and assume that it is smaller than $\\delta/2$\".  Why is this assumption justified?\n\t- In the paragraph preceding eq. 15, what is $\\hat Y_{t'}$?  Should it be $\\check Y_{t'}$?  And what is $\\check Y_{t'}^*$ in the paragraph following eq. 15?  Should it be $\\check Y_{t'}$?\n\t- Following the above, I don't get why $DP(\\check Y_{t'})+\\epsilon \\leq \\delta$ but not $3\\delta/2$, given that \"let $t'$ corresponds to... under the constraint that $DP(\\check Y_{t'})\\leq \\delta-\\epsilon$\".\n\t- I don't get why $DP(\\check Y_{\\hat t})\\leq \\delta -\\epsilon_1$, how is $\\check Y_{\\hat t}$ related to $\\check Y_{t'}$?\n\t- Finally, Theorem 2 only proves results for DP.  What about EO, EOp, and composite criteria?\n\t- Please also justify the assumptions made; are they practical?\n\n1. In the experiments, the authors compared their proposed post-processing algorithm to ones that are attribute-aware, but their algorithm is run in attribute-unaware mode.  The authors should have compared to those algorithms by running their algorithm in the same attribute-aware mode.  In this sense, the current set of experiments is incomplete.\n\n1. The conclusions drawn from the ablation study in section D.2 do no make sense to me.  How is accuracy related to the error $\\mathbb E|\\hat p(A=1\\mid X) - p(A=1\\mid X)|$ in Theorem 2?  In fact, regularization could in fact be reducing the aforementioned error despite huring accuracy.  One way to measure this is, e.g., using reliability diagrams.  The conclusion in D.2 that \"this further confirms the robustness of our post-processing modification algorithm\" does not make sense.\n\n1. Some clarifications would be helpful:\n\n\t- Example 3 does not imply subgroup fairness, i.e., intersecting groups.\n\t- When introducing the composite criterion, it is also useful to mention that some fairness criteria are incompatible with each other (e.g., DP vs. EO).\n\n1. Related work on the Bayes optimal fair classifier in the attribute-aware setting (via post-processing) are missing, e.g., [1, 2, 3, 4].\n\n[1] Denis et al. Fairness guarantee in multiclass classification. 2023.  \n[2] Zeng et al. Bayes-Optimal Classifiers under Group Fairness. 2022.  \n[3] Gaucher et al. Fair learning with Wasserstein barycenters for non-decomposable performance measures. AISTATS 2023.  \n[4] Xian et al. Fair and Optimal Classification via Post-Processing. ICML 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)