Fair Wrapping for Black-box Predictions
Authors: Alexander Soen
Ibrahim Alabdulmohsin
Oluwasanmi O Koyejo
Yishay Mansour
Nyalleng Moorosi
Richard Nock
Ke Sun
Lexing Xie
Venue: NeurIPS 2022 Accept (2022)
Keywords: Fairness
post-processing
loss functions
boosting

Abstract: We introduce a new family of techniques to post-process (``wrap") a black-box classifier in order to reduce its bias. Our technique builds on the recent analysis of improper loss functions whose optimization can correct any twist in prediction, unfairness being treated as a twist. In the post-processing, we learn a wrapper function which we define as an $\alpha$-tree, which modifies the prediction. We provide two generic boosting algorithms to learn $\alpha$-trees. We show that our modification has appealing properties in terms of composition of $\alpha$-trees, generalization, interpretability, and KL divergence between modified and original predictions. We exemplify the use of our technique in three fairness notions: conditional value-at-risk, equality of opportunity, and statistical parity; and provide experiments on several readily available datasets.

Fair Wrapping for Black-box Predictions
Alexander Soen Australian National University alexander. soen@anu.
Ibrahim Alabdulmohsin
Sanmi Koyejo
Google Research ibomohsin@google com
Google Research
.oxender..oee@@au... edu. au
Stanford University
sanmik@google com
Yishay Mansour
Nyalleng Moorosi Google Research nyallenggroogle.c com
Richard Nock
Google Research
Google Research
Tel Aviv University
Australian National University
mansour@google.com com
richardnock@googgle.c
Ke Sun
Lexing Xie
Australian National University
Australian National University lexing xie@anu. edu. au
CSIRO's Data6l sunk@ieee. org
Abstract
We introduce new family of techniques to post-process ("wrap"") a black-box classifier in order to reduce its bias. Our technique builds on the recent analysis of improper loss functions whose optimization can correct any twist in prediction, unfairness being treated as twist. In the post-processing, we learn wrapper function which we define an a-tree, which modifies the prediction. We provide two generic boosting algorithms to learn a-trees. We show that our modification has appealing properties in terms of composition of a-trees, generalization, in- terpretability, and KL divergence between modified and original predictions. We exemplify the use of our technique in three fairness notions: conditional value- at-risk, equality opportunity, and statistical parity; and provide experiments on several readily available datasets.
Introduction
The social impact of Machine Learning (ML) has dramatic increase over the past decade enough so that the bias of model outputs must be accounted for alongside accuracy 14. 35 Considering the various number of fairness targets 20 and the energy and CO2 footprint ML
19 28 the combinatorics of training accurate and fair models is non-trivial. This is especially so
given the inherit incompatibilities of fairness constraints [17] and the underlying tension of satisfying fairness whilst maintaining accuracy. One trend in the field "decouples" the two constraints by post-processing pretrained (accurate) models achieve fairer outputs (35 Post-processing may be the only option if we have no access to the model's 's training data algorithm hyperparameters (etc.).
Within the post-processing approach, three trends have emerged: learning new fair model close the black-box, tweaking the output subject to fairness constraints, and exploiting sets of classifiers. the task class probability estimation [44] the estimated black-box is accurate but potentially unfair posterior X + [0, 1] which neither can be opened nor trained further. The goal is then to learn fair posterior Th from it. In addition to the black-box constraint, number of desiderata can be considered for post-prost post-procsssing Ideally in correcting black-box, we would want the approach have (flexibility) in satisfying substantially different fairness criteria, (proximity) of the learnt
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Black-box
Black-box Fair wrapper
Accuracy CVaR (Thm. 2)
EOO
a Uu
(Thm. 1) (Thm.
nu (x+)
a
nr(x)
Accuracy
CVaR
EOO
a'
Tu
X
?
nk(())
Figure
Summary of using different a-correction wrappers to obtain different fairness criteria guarantees. See Sections 5 and for full details on guarantees.
Th to the original πa. and meaningful (composability) properties if, e.g., The was later treated new black-box to be post-processed. To facilitate a specific style correction, we may also want the representation of the correction facilitate (explainability) for auditing the post-processing procedure and bounds on the increased model (complexity) of the final classifier T]-. In training the correction, algorithmically would also want guarantees for (convergence).
Our contribution satisfies the aforementioned desiderata its correction, representation, and algo- rithmic guarantees. By leveraging recent theory in improper loss functions, we utilize universal correction of black-box posteriors defined by the a-loss. This allows for a flexible correction which yields convenient divergence bounds between πe and Tu. convenient form for the Rademacher com- plexity of the class of Th and a simple composability property. Representation-winn learn are sisy-to-interpre tree-shaped functions that we define a-frees. Algorithmically speak- ing, we provide two formal boosting algorithms to learn a-trees building upon seminal results (1.5. We demonstrate
the corrections
algorithm for conditional value-at-risk (CVAR) 32 equality of opportunity (EOO), and statistical parity; as depicted in Fig. | Experiments are provided against five baselines on readily available datasets. All proofs and more experiments are in Appendix denoted SI.
2 Related Work
post-processing models to achieve fairness is one of three different categories in tackling the MI.
+ fairness challenge 35] Section 6.2]. Although other notions exist, e.g. individual fairness [12],
we limit analysis to group fairness, which concerns itself with ensuring that statistics of sub-
populations are similar. We further segment this cluster into three subsets: (I) approaches learning a
new model with two constraints; being close to the pretrained model and being fair [T6] 22 3d (II)
approaches biasing the output of the pretrained model at classification time, modifying observations :e]; ; and (III) techniques consisting of exploiting sets of models to achieve fairness II] None of these approaches formulates substantial guarantees on all of the desiderata in the introduction. Some bring contributions with the (flexibility) of being applicable to
for fairer outcomes [1] |4]
18
21
34]. Two of which provide the convenience of analytic conditions new faimess notions to fit in the approach 31 17]. However, for all of them, the algorithmic price-tag is unclear 7 [ or heavily depends on convex optimization routines [3I].
more than two fairness notions 7 31
3 provide strong guarantees regarding (proximity), w.r.t. consistency and generalization. To our knowledge, our approach of correcting prediction unfairness through improper losses 29] is new.
Setting and Motivating Example
Let X be a domain of observations, y = {-1,1} be labels and S is a sensitive attribute X. We assume that the modalities of S induce partition of X. We further let D denote the joint measure over X x y, M denote the marginal measure over X, and π = P = being the prior. We denote conditioning of M through subscript, e.g., M, for attribute subgroup 5 = s. We leave the -laleerra to be implicit (which assumed to be the same everywhere). As is often assumed in ML, sampling is ii..; make notational distinction between empirical and true measures to simplify exposition most of our results apply for both.
S denotes M. conditioned on sensitive
Consider the task of learning function [0. 1 to estimate the true posterior n (x:) IP(Y 1|X = œ in binary classification. For instance, we may want to predict the probability of hiring an applicant for company. Given the pointwise loss L (n(X), n' (X)), which determines the loss of

---

1.0
1.0
Age
25
00.5
0.5
0
< 0
0.0
0.5
1.0
0.0
2 E 1,1
((x)) Ground Truth
[a): Age 25
na(a): Age 25 A a <
Th(a)): Age < 25 A
((r]: Age 2 25
ni(a): Age < 25 =
[[(a)): Age < 25 =
Figure 2: Improving CVAR for toy hiring task with a-trees. An a-tree (left) transforms the posterior via 3 (middle); resulting in an input-dependent fairness correction the posterior Tu (right).
single example, the (total) risk is defined
L(n: M,n") = Ex-M (n(()))nnnxx))
(with slight abuse of notation). A low risk corresponds to good classification performance. this paper, we consider the risk determined by the log-loss:
(n: [n: (....n))
= E' [x) (X) + (1-n"(X)) log(1 - -X))] X-M
(2)
We now consider simple fairness problem, centered around the example of Fig. - Suppose that are given a black-box пJ which predicts hiring probabilities without considering fairness. Although the minimized total risk of ① might be small, there can be discrepancies in the performance between different subgroups. Instead of considering the total risk, the predictive performance of specific subgroups can be examined through the subgroup risk (n M,,n"), for a subgroup instance, we might want to examine the discrepancy of subgroup risks among the age of applications. natural fairness task would be to improve the worst performing subgroup, say Sw S.
S. For
To post-process unfairness, we want to learn a function a X -> which "wraps" тu and lowers the worst subgroup risk. We propose the following "wrapping". inspired by improper loss functions 29
n (x: a((a))
(x()))
nu (=())((m) + (1 (1-m( ())))<(()) E [0, 1].
Notice when (xx) 1 the resulting posterior the original nu (z). Importantly, 3 is flexible enough to transform any input black-box to any needed ny- Looking at Fig. 2 (left and middle), intuitively by setting different (2x) values, { "sharpens" (yellow, a > 1), "dampens" (blue, 0 < a < 1), or "polarity reverses" (red, a < () the original posterior πe To improve faimesss, we need a combination of these corrections to accommodate different subsets of the input domain (thus learning a(.) as function). We specifically learn ar-)) to be tree structure, which allows interpretable correction alongside other formal properties (Section 5
Definition 1. An a-tree is rooted, directed binary tree, with internal nodes labeled with observation variables. Oulgoing ares are labeled with tests over the nodes' variable. Leaves are real valued. A(Y) is the leafset of o-tree T. An a-Iree induces a correction over posteriors as per with T.
Our fairness problem is now learning an a-tree which provides a corresponding correction that improves the worst subgroup risk, i.e., (m presents such a process. In this hiring task example. the ground truth hiring rate is constant w.F.f. the inputs, 1 (a>) = 0.7. Despite this, the black-box n=()) unfairly depends on the age of applicants and incorrectly depends on noise feature 2.. By choosing (xx) per Fig. 2 (left), the correction changes п, to be closer to n improving the risk of the worst subgroup (alongside the other subgroup in this example): the worse-case loss improves from 1.09 to 0.62.
> [( M ".l,,,,""".. The entirety of Fig. 2
Although the faimess criteria discussed might be considered simple, the procedure of iteratively minimizing the worse performing subgroup can be used to improve the conditional value-at-risk (lower better) fairness criteria [32]:
CV) = [Ls[L (nc Ms. nT" | L(T Ms, n²) )) Lol.
(4)
3

---

Algorithm TOPDOWN (M, Th, To. B)
Input mixture M,, posterior Th, a-tree To. B E R
Step Y Yo
Step 2 while stopping condition not met do
Step 2.1 pick leaf X E A(T); // i.e. heaviest leaf
To
Faimess criteria depordant choioa of, TorDoww
TOPDoWN
Step 2.2: : ht arg minseac H(T h); M, n.); split using h² at X" Step 3 label leaves 7A E A(T):
Step 2.3 T < T(A",""
e (Ma, mc)
Picking To a stump on the fairness attribute allows finely tune growths of sub-a-trees to the fairness criterion at hand.
Figure 3:
T(A) = i
I/ a-value (5)
Output T:
where Lg is the risk value for the 3 quantile among subgroups, which is user-defined. The difference that CVAR,3 not only considers the worse case subgroup, but all subgroups above the Lg risk value (let these subgroups be 8z). One can simply iteratively improve all Sg, as done in the example of Fig. 2 Indeed, in the example, CVARg with 3 = 0.9 improves from 1.09 to 0.62 (which equivalent to worse-case loss in this case).
4 Growing Alpha-Trees
We now introduce the procedure to grow an a-tree via boosting algorithm TOPDOWN, Algorithm ToPDOwN be thought of as generalization of the standard decision tree induction used for classification [[5]. We first introduce relevant concepts from decision tree induction to explain ToPDOwN. We contextualize ToPDowN through its application in improving the CVAR criteria.
We first introduce a technical assumption for the black-box п, to be post-processed:
Assumption 1. The black-box prediction is bounded away from the extremes: 3B 0 such that Tm(n,) C [[1 + (x)(()))=
(a.s.).
(6)
Compliance with Assumption can be done by clipping the black-box's output with a user-fixed B making sure it is calibrated and then finding B.
Entropy- updates for fairness: An important component in standard decision tree induction is the edge function, which measures the label purity (proportion of positive examples) of decision tree node. We introduce generalization which considers the alignment purity of a black-box. Definition 2.
Let (uu) = log(u/(( (1((1 10---) u)) the logit of (0,1) 1) and i(u) = u(u)/ B a normalization which satisfies i(I) = [-1,1]. The alignment edge of M, and Tue is defined as,
e(M,, = EXxY)~,, (Yi(n,
where D, is the joint measure induced by M, and п. With Assumption e(M, nd) E [-1,1]
By replacing the normalized logit with constant 1. 7 reduces to measure of label purity used in regular classification. our case, 7 measures how well the black-box πu "aligns" with the true labels Y through the logit. This also takes into account the "confidence" of the black-box's predictions: for high alignment purity, predictions not only need correct but also to be highly confident (n, close the endpoints of I). Similar how the splits of decision tree classifier determined by the entropy tree's label purity, an a-tree splits based on its alignment entropy.
Definition 3. Given an a-tree Y with leafset A, when Assumption satisfied, the entropy of T is:
H(Y:M, n.)
EXWMArry [Hr nJl,
(8)
where H(q) = -gggog - (1 log(1 q). (2( H ((1+ e(M))n))/2), MX is M, conditioned to leaf X E A(T), and MA(T) a measure induced on A(Y) by leaf weights on M.
Theorem 1. For any M, Th. let Y's leaves follow
Then L(nr: m.) < M.
Algorithm Caan now be explained by repeatedly leveraging Theorem D Suppose that we have hypothesis set of possible splits H grow our a-tree. Denote T(), h) as the a-tree T split leaf

---

À E A(T) using test h. The inner loop within Step 2 is the process of finding the best possible leaf splits which helps to minimize the a-tree's entropy and reduce the risk as per Theorem The a-values of ① calculated in step 3 are those used to ensure Theorem | and 11 <- n. Algorithm improves CVAR by iteratively improving the a-tree's 's worst subgroup entropy H(T; accommodate for different 3 quantiles values for CVAR, TOPDOWN can be run repeatedly (replacing the initial input tree To) to progressively improve all E S3. Hence, to reduce CVAR, we basically
holds. By setting M, < Ms..
which as a surrogate improves the worst subgroup risk L. (nu M n*). To
use TOPDOwN with M, < M, (s 89) and n. +-
(CVAR)
As alluded to by the notation used to instantiate TOPDOwN, the inputs of the algorithm can be instantiated to optimize for fairness criteria beyond CVAR. This discussed in Section O In the usual ML setting, M,, 17. can be estimated from training sample (see Section
Initialization: In the procedure of improving CVAR, the worst subgroups can be iteratively improved. However, we also need to make sure that improvement of a subgroup does not adversely affect another subgroup (which could potentially harm CVAR instead). As such, we introduce an additional structure to the o-tree Y by tweaking the initial tree structure Yo used in ToPDOWN. Since the fairness attribute S partitions the dataset, a convenient choice of initializing the a-tree is to split by the subgroup modalities, as depicted in Fig. El As such, we grow separate sub-a-trees for each of the sensitive modalities. For CVAR, this allows the subgroup risk of individual subgroups to be tweaked without adversely affecting other subgroups.
5 Formal Properties
We move the formal properties of our approach. We first detail the background of improper loss functions which motivates our correction given in Section 3 We then present the formal properties of this correction. The useful properties of having a(.) represented by a tree structure is then discussed. Finally, we present convergence analysis of Algorithm and an alternative boosting scheme.
Can Tr as per B correct (any) potential unfairness? Yes. In short, this comes from recent theory in improper loss functions for class probability estimation (CPE) 29 We are interested in the pointwise minimizer (eventually set-valued) of:
tn(
arg inf L(u,n). wEJ0.1]
Dubbed as the Bayes tilted estimate of a loss l a ground truth (pointwise) posterior n. Common loss functions are proper: the ground truth value E (z(n) is an optimal response. However, in the case where cannot be trusted (for instance when is unfair), we may not want to default to imitating π. In addition we also want to make sure that the Bayes tilted estimate can fit to any desired (in our context, fair) target. The so-called l-loss th. which generalizes the (proper) log-loss, is a good candidate parameterized by a variable a. Its Bayes tilted estimate is the pointwise version of (3) for a & oo) and n + 1/2:
29 (n(n) is the set of optimal "responses" given
(10) Importantly for a-losses, for any n & {0, 1/2, 13 and any n' (0, 1), there exists a E R ITC such that fo- (n) [n'). This property, called twist-properner
te (n) = (n + (1-n)")
(29]. allows for any pointwise correction. ensures that given an initial
By extending a to a function (of x E X, as per (b), twist-propennn unfair posterior an appropriately learned (-) can correct any unfairness. This allows for (flexible) fairness post-processing - different a functions can be learned for different criteria (i.e., Fig. D..
Why use the Log-Loss? As per Section 3 we minimize the log-loss. We choose the log-loss for two reasons: @ it is strictly proper and so minimizing ( M, n.) (i.e., via TOPDOWN) "pushes" Ti towards target mi and @ it is the a-loss for a 1, so we are guaranteed that for the minimizer 1. With alternative (i.e. non-strictly proper) loss, we might have only "="
Th + TTu
Do we have guarantees on some proximity nr with respect to nu? Yes, with light assumptions. We examine the (proximity) of black-box and post-processed posteriors with the KL divergence 2
KL(T,,, Tri M) ف E(x,y) [log (dD,((X, Y()))
(11)
where D,, D, are the product measures defined from M and their respective posteriors. To bound the proximity [I]. we present setting (S1).
5

---

(S1) Assumption hoolds for some 0 < B S 3 and function a satisfies |a(x) 1| - 1/B (a.s.).
This setting lead to the following data independent proximity bound.
Theorem 2. For any M, (S1) implies KL(Mo, Mri M) S / exp(BB exp(-B)))
As an example, fix B = 3 for (S1). In this case, we want a(.) E [2/3, 4/3] (a.s.) which is a reasonable sized interval centered at 1. The clamped black-box box posterior's 's interval is approximately [0.04, 0.96], which is quite flexible and the distortion is upperbounded as KL Ti M) S 7..5 2.
Is the composition of transformations meaningful? Yes. The analytical form in brings the following easy-to-check (composabilityy property.
Lemma 1. The composition of any two wrapping transformations n. 9 ni 2 following equivalent to the single transformation πn "3 n/-
3 is
This gives an invertibility condition wrapping Th, with a' = 1/a recovers the original black-bor -box Tl--
Given some capacity parameter for Muy can easily compute that of nr? Yes, e-g., for decision trees. Such a question is particularly relevant for generalization. As we are using the log-loss ( relevant capacity notion to assess the uniform convergence of risk minimization for the whole wrapped model is the Rademacher (complexity)
B. We examine the following set of functions:
HG {nr mr(x)) given by with a, nuj V(a, n.)},
(12)
where we assume known the of functions from which n, trained. We now assume have a m-training sample 8 {( v1) ~ D) The empirical Rademacher complexity of a set of functions HC from X R. (3C) = Egg suPže5 E, [x,])(xx)]] (sampling uniform with a; [[-1,]] is a capacity parameter that yields efficient control of uniform convergence when the loss used is Lipschitz Theorem 7J, which is the case of the log-loss. To see how the a-tree affects the Rademacher complexity of classification using instead of Nu. suppose real-valued prediction based on TT is achieved via logit mapping, o Tu (12). Such mappings are common for decision trees (26].
d and denote Rg Rg(DD(d)) the empirical Rademacher complexity of decision trees of depth S d [3] and d' the maximum depth allowed for o-lrees. Then we have for H, in 12 Rs S Ri (DT(d d')).
Lemma 2. Suppose (nu} is the set of decision trees of depth
The proof is straightforward once we remark that elements in H, can be represented as decision trees, where we plug each leaf of n, copy of the a-tree Y.
Does Algorithm L have any convergence properties? Yes, it is a boosting algorithm. Following similar blueprint to classical decision tree induction, it comes with surprise that ToPDowN can achieve boosting compliant convergence. To show that TOPDOWN is a boosting algorithm, we need Weak Hypothesis Assumption (WHA), which postulates informally that each chosen split brings small edge over random splits for a tailored distribution.
Definition 4. Let E A(T) and D be the product measure on x y conditioned on X. The balanced product measure DiA at leaf X is defined (z = (x, u) for short):
(2) = 1- e-e(Mx, mi) yi(n.(=)) Dix(z).
(13)
e e(M,, n1)²
We check that SA dD' = because of Def. Our balanced distribution is named after 15 's: ours indeed generalizes theirs. The key difference comes from the change in setting, where we consider the alignment purity of leaf and not its label purity. The "fairness-free case" where i(.) is replaced by constant yields the original balanced distribution [15]. We now state our WHA.
Assumption 2. Let h >> be the function splitting leaf For y > then h y-witnesses the Weak Hypothesis Assumption (WHA) at X iff
E (X
(i)n.(()) h(X] 2 (ii) (M)
E (XY)>DDa
[1- h(X) < O.
Intuitively, (i) gives a condition on the split h's correlation with unfair posterior n. agreement with labels and (ii does the same for the confidence of nJ predictions. Similarly to the balanced

---

7p,6
(A:A: M..
1/2 4
M..A:M..n.)
1 bil
11
DINIII ef OAGA 1 (
112)
1/2
Figure 4: Left: Difference between the per-leaf bounds on risk L Lm,,; M, n.) using and Theorem (conservative scoring) and (TS) (audacious scoring). Details the proof of Lemma Right: A representation of the (p. puushup n", where 77(p) inf (XG, < 1/2 (Def. A All posteriors in [m(p). + 6] are mapped to 1/2 + o; others do not change. New posterior n , eventually reduces the accuracy classification for observations whose posterior lands in the thick red interval (z-axis).
distribution, in the fairness-fre free case where we only care about the label purity of splits, the WHA simplified that of [I5 i.e., only (i) matters. A further discussion on our balanced distribution and WHA is in the SI, Section MII We now state TOPDoWN's boosting compliant (convergence).
Theorem 3. Suppose (a) Assumption Tholds, (b) we pick the heaviest leaf to split at each iteration in Step 2.1 of ToPDowN and (c) By > 0 such that each split ht (Step 2.2) in Y y-witnesses the WHA. Then there exists a constant 0 such that We > if the number of leaves of Y satisfies
[A(T) (1/e) ((/e)clo(()//² then nr crafted from using TOPDowN's T achieves L(nri My. mi) S E.
Are there alternative ways of growing a-trees? Yes. Let us call conservative the scoring scheme in (5. There is alternative scoring scheme, which can lead to substantially larger corrections in absolute values, hence the naming, and yields better entropic bounds for the a-tree.
Definition 5. For any mixture M. and posteriors Tu. Th. let e (M, n.) and (M. be defined by
e n+, = Exx.y [max (0, + =Yi(n,
(14)
The audacious scoring schemes the leaves of the a-tree replaces
Step by:
e+ +Mx, no)
T())
YA AATA
e (M) + --MMM
Theorem 4. Suppose Assumption T holds and ler Hz(g) = H(g)/ log 2 (E [0, 1)), H being defined
in Definition For any leaf E A)T), denote for short:
1)
H2(A;M,,.) = log(2)
[1+(et+e)) H2
ex o
where let e = e² vb (+. Using audacious scoring, we get instead of Theorem !
L(T:: M. s Ex-MAc) M,,
(15)
While upperbounds in Theorem D and Theorem may look incomparable, it takes a simple argument show that (15) is never worse and can be much tighter.
Lemma 3. Va-tree Y, TExMMrrs (,, n)) s H(r;M.n..)
It thus comes surprise that using the audacious scoring also results in boosting result for ToPDoWN guaranteeing the same rates as in Theorem S It also takes a simple picture to show that the per-leaf' slack in Lemma can be substantial, slack which can be represented using simple picture, see Figure (left), following from the use of Jensen's 's inequality the Lemma's proof.
As audacious scoring is better boosting-wisg wise, is conservative scoring useful? Yes. If we only cared about accuracy, we would barely have any reason to use the conservative correction. Even thinking about generalization, the Rademacher complexity of decision trees is function of their depth so faster the convergence, the better R. Section 4. 4.1]. Adding fairness substantially changes the picture: some constraints, like equality of opportunity (Section 5 can antagonize accuracy to some extent. such a case, using the conservative correction can keep posteriors п, and n, close enough (Theorem so that fairness can be achieved without substantial sacrifice on accuracy.
7

---

Fairness and Societal Considerations
In this section, we present the fairness guarantees TOPDOWN can achieve, In particular, we provide a discussion about how Theorem 3 can guarantee minimization of the CVAR criteria. Furthermore, we provide alternative inputs to TOPDOWN which allows for EOO to be targeted as a fairness criteria. In we further present treatment of statistical parity. Lastly, we discuss how using
the SI Section I a-trees provides explainable corrections and how utilization of the sensitive attribute (as per Fig. can be circumvented.
Guarantees on CVaR: As discussed in previous sections, one way to improve the CVAR fairness criteria (as per (b) is to focus optimization on the worst treated subgroups. Given a specified quantile group / and the set of worse subgroups 8g, we can repeat (CVAR) until C (M.)) gets below a threshold or (more specifically) its worst tread group gets a risk below threshold (i.e., stopping criterion). Importantly, Theorem 3 provides a guarantee: to ensure CVAR, is below E, we simply need to boost for |S] times the tree size bound AAT)) given in Theorem R
Guarantees on EOO: EOO requires to smooth discrimination within an "advantaged" group, modeled by the label Y = 1 [1]. We say that n, achieves E-equality of opportunity iff a mapping h, of nr y (e.g. using the sign of its logit 1) satisfies
max P (x) 1] min P (x,(X) #ES X.P,
1] S E,
(16)
#ES X-P.
where Pe is the positive observations' measure conditioned to value S = s for the sensitive attribute. It is clear that EOO can be antagonistic to accuracy: the rate of advantage in the data D may not be equal among the subgroups. As such, unlike CVAR, we do not want to target the Bayes posterior n: f n" for EOO. Instead, we target skewed posterior which aims to improve the least advantaged subgroup, i.e., increasing 5 E arg min,e Px~P, (X) = 1]. Our strategy consists of picking a target posterior which skews part of the original nd to be more ad advantaged, thus reducing the LHS of
166 until
16 is satisfied] For this, we create a (p. 6ppusshp of n defined in SI Appendix I
Fig. (right) presents an example of pushup map. Notice that the pushup only changes the predicted probability of example which do not have a "confident prediction" (the interval [n(p), 1/2 + 8)). Intuitively, p controls how many examples are corrected and d controls how much the correction "pushes up" advantage, further discussion in SI Appendix ! We then run TOPDOWN using as mixture the positive measure conditioned to S = 8 and p = PP--,, [br(X)= 1] + + - 1), =
Ke/(K - 1), with K > 1 fixer. Thus, we do
Use TOPDOWN with M. + P and n. + n
(EOO)
Theorem 5. If TOPDOWN is run until L(n M, n)) S (e* (e+/2) + Ex-M. [X)),X))), then after the run we observe Px-P,, (X,(X) = 1] Px-P,- (X) = 1] S.
In the full context of EOO, in the optimization we should not wait to get the bound on (m M, n.). Rather, should make sure (a) we update arg min.es Px~P, (X)
1] (and thus s²) after each split in the a-tree and (b) we keep arg max PPx-r, [h+(X)= = 1] as is, to prevent switching targets and eventually composing pushup transformations for the same S = s", which would not necessarily comply with our theory. Notably, the guarantee presented in Theorem depends on the mapping fú and not the direct posterior nr. as typically considered 14. When taking threshold (sign of the logit), fyp can be interpreted as forcing the original posterior to be extreme values of 0 or 1.
Unlike the CVAR case, EOO (as per (17). SI) requires an explicit approximation of nn In practice, we find that taking a simple approximation of nn" still can yield fairness gains. However, if one does not want make such an approximation, one can adapt the statistical parity approach (detailed in SI, Section M. Similarly, if wants to consider the typical EOO definitions depending on posterior values, the target measure can be replaced (i.e., swapping measure M, with the positive examples P).
Explainability: a-trees using the initialization proposed in Section (and Fig. 3) allows for (explainability) properties similar to that of decision tree classifiers. Fixing sensitive attribute
If we instead reduce arg max.es PX--, (X) = 1] we get a symmetric strategy. The application informs which to use: if positive class implies money spending (e.g. loan prediction), then our strategy implies spending more money; while the latter aims to reduce money lent to achieve fairness.
8

---

CVaR
Equd Opportunity
Peteriot Moan Difference
0.7-
(Nan (lowe better)
0.02
EUO (lower battee)
MT (looee better)
0.6-
0.50-
0.2
0.4-
0.88
0.0
0.3-
10
13
16
10
22
25
26
31
10
13
16
c1
4
20
13
16
22
25
28
31
Auclacious (CVuR)
Audlacion (EGO)
BBox TNCVAR
DEED0
Conservative (CVaR)
Conservative (EOO)
Figure 5: ACS 2015 with Binary Sensitive Attribute and Random Forest Black-box: Evaluation of ToPDoWN over boosting iterations (x-axis) for different fairness criteria. 'c' on the x-axis denotes the clipped black-box. 'x' denote when a subgroup's 's a-tree is initiated (over any fold). The shade denotes + a standard deviation from the mean, this disappears when folds have early stopping.
8, the corresponding sub-a-tree Y, can be examined to scrutinize the correction done for the corresponding subgroup. If the splits of the a-tree are simple, similarly to standard decision tree classifiers, corresponding partitions of the input domain can be examined. Furthermore, the type of corrections can also be examined, as discussed in Section where corrections can be classified as "sharpening", "'ampening". or "polarity flipping" depending on the leaves' a-values.
Usage of sensitive attribute: classification for the fact that they require explicit access to the sensitive feature classification time B5 & 6.2.3]. Our basic approach to the induction of a-trees falls in this category (Fig. D but there simple way to mask the use of the sensitive attribute and the polarity of disparate treatment induces: it consists in first inducing decision tree to predict the sensitive feature based on the other features and use this decision tree as an alternative initialization to naively splitting on subgroups. We thus also redefine sensitive groups based on this decision tree thus alleviating the need to use the sensitive attribute in the a-tree. The use of proxy sensitive attributes in a similar manner has seen ample use in various domain such as health care K 5 and finance 1 We however note that its application in post-process and a-trees may not be appropriate across all domains
Post-processing methods have been flagged in the context of fair
X
7 Experiments
To evaluate TOPDOWN we consider three datasets presenting a range of different size / feature types, Bank and German Credit (preprocessed by AIF360 4 and the American Community Survey (ACS) dataset preprocessed by Folktables 9 The SI (pg 32 presents all results at length (including considerations on proxy sensitive attributes, distribution shift, and interpretabilityy, along with the different black-boxes considered (random forests and neural nets). We concentrate in the Section on the ACS dataset for income prediction in the state of CA and evaluate TOPDowN's application to various fairness criteria (as per Section 6 and SI pg 15) with Random Forests (RF). For these experiments, we consider age as a binary sensitive attribute with bin split at 25 (a trinary modality is deferred to the SI), For the black-box, we consider a clipped (Assumption with = 1) calibrated using Platt's method
23] The RF consists of an ensemble of 50 decision trees with a maximum depth of 4 and a random selection of 10% of the training samples per decision tree. Data is split into subsets for black-box training, post-processing training, and testing; consisting of 40:40:20 splits in 5 fold cross validation. For EOO, we utilize an out-of-the-box Gaussian Naive Bayes classifier from scikit-learn to approximate n².
random forest (RF) from scikit-less
Multiple fairness criteria We evaluate TOPDOWN for CVAR, equality of opportunity EOO, and statistical parity SP. The complete treatment of SP is pushed to SI (Sections [I] X SP aims to make subgroup's 's expected posteriors similar and is popular in a various post- post-processing methods [i I. The definition can be found in SI (pg)l 15) along with the strategy used in TOPDOWN. Conservative and audacious updates rules are also tested. For each of these TOPDOWN configurations, we boost for 32 iterations. The initial a-tree is initialized in Fig.
We compare against 5 baseline approaches. For CVAR we consider the in-processing approach (INCVAR) presented in 32 For EOO, consider derived predictor (DEREOO) [4. Our
2 PImplementation at: http:///ww./aaaaaaaacccc.o///aaa
wrappes
Public at: http:://ggstuub..om////////////

---

derived predictor modified for SP (DERSP) [4: and a randomized threshold optimizer approach (RTO) [. We denote the clipped black-box as BBOx. The experiments for CVAR and EOO are summarized in Fig. E the full plot with SP is presented at SI Fig. To For clarity we only plot the baselines and wrappers which are directly associated to each fairness criteria. We also plot the posterior mean difference between the data and debiased posteriors MD (0/1 loss) to examine the effects on accuracy.
SP baselines include an optimized score transformation approach (OST) 31
For CVAR, both conservative and audacious approaches decreases CVAR, which results in better CVAR values than both the original BBXx and in- in-orecssinng baseline INCVAR- wwich is good news since INCVAR directly optimizes CVAR. We note that there are cases in which the in-processing approach is better than ours (trinary sensitive attributes in SI), but this is expected given INC VAR's s optimization goal. Interestingly, the audacious update is superior in both CVAR and MD than the conservative update. This is also consistent for trinary sensitive attributes. Thus, the audacious update is desirable when optimizing CVAR. Another observation is that only one sensitive attribute subgroup's s a-tree is initialized (only one 'x'). This indicates that after 32 iterations the worse case subgroup does not change in the binary case.
For EOO, there huge difference between conservative and audacious updates as the former gets to the most fair outcomes of all baselines. Even if we used early stopping or pruning of the a-tree (taking an earlier iterations) the audacious update would fail at producing outcomes as fair as its conservative counterpart. Furthermore, the audacious update comes with significant degradation of accuracy MD. Furthermore, by looking at the iterations in which subgroup a-trees are initialized, the audacious update causes large (primarily bad) jumps in performance. This rejoins our remark on the interest of having a conservative update in Section 5 When compared to DERFOO, we find that the conservative TOPDOWN approach produces lower EOO. However, DEREOO tend to have better accuracy scores in MD. These observations are consistent with the trinary sensitive attribute (SI).
For SP, we can observe fairness results that can be on par with contenders for the conservative update, but observe substantial degradation of MD. This, believe, follows from simple plug-in instantiation of M, Th for the fairness notion in SI Section I| resulting in potentially harsh updates. In SI (pg 15). we discuss an alternative approach using ties with optimal transport.
8 Limitations and Conclusion
Given the context of fairness, it is important to highlight possible limitations of our approach and the potential social harm from such misuse. We highlight two of these for our TOPDOWN approach. Firstly, our approach has shown to have failure cases in small data cases. This can be seen in the experiments on German Credit dataset (SI. Section XII This, we believe, has a formal basis in approach. For instances, EOO requires accurate data posterior estimation which may be difficult in small data regimes. Secondly, ToPDOWN is of course not unilaterally better than all other post- post-prcessiig fairness approaches there is No Free Lunch. As such, we do not claim that our instantiation of TOPDOWN is optimal in CVAR, EOO, or SP. However, considering that such different fairesss models instantiated in the same algorithm can lead to competitive results with the respective state of the art, the avenue for improved instantiations or accurate extensions to new fairness constraints appears promising. We leave these for future work.
Acknowledgments and Disclosure of Funding
YM received funding from the European Research Council (ERC) under the European Union's s Horizon 2020 research and innovation program (grant agreement No. 882396), the Israel Science Foundation(grant number 993/17), Tel Aviv University Center for Al and Data Science (TAD), and the Yandex Initiative for Machine Learning at Tel Aviv University. AS and LX thank members of the ANU Humanising Machine Intelligence program for discussions on fairness and ethical concerns in AI, and the NeCTAR Research Cloud for providing computational resources, an Australian research platform supported by the National Collaborative Research Infrastructure Strategy.
10

---

References
[1] I. Alabdulmohsin and M. Lucic. A near-optimal algorithm for debiasing trained machine learning models. In NearlPS*34, 2021.
[2] S.-I. Amari and H. Nagaoka. Methods of Information Geometry. Oxford University Press, 2000.
[3] P.-L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. JMLR, 3:463-44 482, 2002.
[4] Rachel K. E. Bellamy, Kuntal Dey. Michael Hind, Samuel C. Hoffman, Stephanie Houde, Kalapriya Kannan, Pranay Lohia, Jacquelyn Martino, Sameep Mchta, Alcksandra Mojsilovic, Seema Nagar, Karthikeyan Natesan Ramamurthy. John Richards, Diptikalyan Saha, Prasanna Sattigeri, Moninder Singh, Kush R. Varshney, and Yunfeng Zhang. AI Fairness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias. IBM
J. Res. Dev., 63:4:1 4:15, 2019.
[5] David P Brown, Caprice Knapp, Kimberly Baker, and Meggen Kaufmann. Using bayesian imputation assess racial and ethnic disparities in pediatric performance measures. Health services research, 11(3)10955-1088 2016.
[6] Consumer Financial Protection Bureau. Using publicly available information proxy for unidentified race and ethnicity: A methodology and assessment. Washington, DC: CFPB, Summer, 2014.
[7] S. Corbett- E. Pierson, A. Feller, S. Goel, and A. Huq. Algorithmic decision making and the cost of fairness. CoRR, htss/701..02233 2017.
[8] Anupam Datta, Matthew Fredrikson, Gihyuk Ko, Piotr Mardziel, and Shayak Sen. Use privacy in data-driven systems: Theory and experiments with machine learnt programs. In 24th ACM SIGSAC, pages 1193-1210, 2017.
[9] Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. NeurlPS*34, 2021.
[10] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R.-S. Zemel. Fairness through awareness. In ITCS' 12, pages 214-226, 2012.
[11] C. Dwork, N. Immorlica, A.-T. Kalai, and M.-D.-M. Leiserson. Decoupled classifiers for group-fair and efficient machine learning. In Conference on Fairness, Accountability and Transparency, volume 81, pages 119-133. PMLR, 2018.
[12] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226, 2012.
[13] Allen M Fremont, Arlene Bierman, Steve I. Wickstrom, Chloe Bird, Mona Shah, José Escarce, Thomas Horstman, and Thomas Rector. Use of geocoding in managed care settings to identify quality disparities. Health Affairs, 24(2):516-522 2005.
[14] M. Hardt, E. Price, and N. Srebro. Equality of opportunity in supervised learning. In NeurlPS' 16. pages 3315-3323, 2016.
[15] M.J. Kearns and Y. Mansour. On the boosting ability of top-down decision tree learning algorithms. In Proc. of the 28 ACM STOC, pages 459-468, 1996.
[16] M.-P. Kim, A. Ghorbani, and J.-Y. Zou. Multiaccuracy: Black-box post- poocessoc for fairness in classification. In AAAI/ACM Conference on AI, Ethics, and Society, pages 247-254. ACM, 2019.
[17] Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. In 8th Innovations Theoretical Computer Science Conference (ITCS 2017). Schloss Dagssubl-Lcimmiizzzztrur fuer Informatik, 2017.
11

---

[18] P.-K. Lohia, K.-N. Ramamurthy, M. Bhide, D. Saha, K.-R. Varshney, and R. Puri. Bias mitigation post-processing for individual and group fairness. In ICASSP'19, pages 2847-2851. IEEE, 2019.
[19] K. Martineau. Shrinking deep learning's carbon footprint.
http:://eeas.itt.edd/20000
shr bbrinking-deep--eeeaae -eep-eea wtt----aaboooooooooeeeee footrroooootttttooo 2020.
[20] N. Mehrabi, Morstatter, N. Saxena, and A. Galstyan. A survey on bias and fairness in machine learning. ACM CSUR, 54:1-35, 2022.
[21] A.-K. Menon and R.-C. Williamson. The cost fairness in binary classification. In Conference on Fairness, Accountability and Transparency, volume 81, pages 107-118. PMLR, 2018.
[22] F. Petersen, D. Mukherjee, Y. Sun, and M. Yurochkin. Post-processing for individual faimesss. CoRR, abs/21 10. 13796, 2021.
[23] John Platt et al. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances in large margin classifiers, 10(3):61-74, 1999.
[24] M.-D. Reid and R.-C. Williamson. Information, divergence and risk for binary experiments. JMLR, 12:731 887,, 2011.
[25] R.-T. Rockafellar and S. Uryasev. Optimisation of conditional value-at-risk. Journal of Risk, 2:21-41, 2000.
[26] R. Schapire and Y. Singer. Improved boosting algorithms using confidence-rated predictions. In 9 COLT, pages 80-91, 1998.
[27] R. E. Schapire and Y. Singer. Improved boosting algorithms using confidence-rated predictions. MIJ, 37:297-336, 1999.
[28] E. Strubell, A. Ganesh, and A. McCallum. Energy and policy considerations for deep learning in NLP. In ACL'19, pages 3645-3651 2019.
[29] Sypherd, Nock, and L. Sankar. Being properly improper. In JCML'22, 2022.
[30] van Erven and P. Harremoës. Rényi divergence and kullback-leibler divergence. IEEE Trans. IT. 60:3797-3820, 2014.
[31] D. Wei, K.-N. Ramamurthy, and F. du Pin Calmon. Optimized score transformation for fair classification. AISTATS' volume 108, pages 1673-1683, 2020.
[32] Robert C. Williamson and Aditya Krishna Menon. Fairness risk measures. In International Conference Machine Learning, pages 6786-6797, 2019.
[33] B.-E. Woodworth, S. Gunasekar, M.-I. Ohannessian, and N. Srebro. Learning non-discriminatory predictors. In C7L volume 65, pages 1920-1953. PMLR, 2017.
[34] Forest Yang. Mouhamadou Cisse, and Oluwasanmi O Koyejo. Fairness with overlapping groups; a probabilistic perspective. Advances Neural Information Processing Systems, 33, 2020.
[35] M.-B. Zafar, I. Valera, M. Gomez-Rodriguez, and K.-P Gummadi. Fairness constraints: flexible approach for fair classification. JMLR, 20:75, 2019.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] At the end of the last page.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] In limitation section and corresponding Appendix sections.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All assumptions are stated in the Theorems, Lemmas, and Corollaries.
(b) Did you include complete proofs of all theoretical results? Yes] Full proofs are presented in the Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as URL)? [Yes] See code in supplementary material.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] Summary presented in main-text with further details Appendix.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] Error bars are present in all relevant plots.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Details present in Appendix [X]
4. If you are using existing assets (e.g., g.. code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] Data sources and baselines cited.
(b) Did you mention the license of the assets? [Yes] Yes, when available.
(c) Did you include any assets either in the supplemental material
URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [Yes] We use public datasets. For the newer dataset, we defer to the cited paper's Section.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [No] The datasets standard benchmarks used extensively in ML. For the newer dataset, we defer to the reference's 's Section.
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "edmmjdIl2I2", "reviewer": "Reviewer_tmha", "summary": "The paper proposes a post-processing mechanism to wrap black-box predictors such that their predictions become compatible with an ancillary criterion such as fairness. To this end, the authors propose to use so-called \"$\\alpha$-trees\", an adaptation of decision trees, to learn correction coefficients that are used to change the output probabilities of a black-box model in the desired way. They further introduce adaptations of their algorithm that enable wrappers that satisfy fairness notions such as conditional value at risk, equality of opportunity and statistical parity.\nTo demonstrate the efficacy of the proposed approach, the paper derives a number of bounds, for instance on the divergence of the wrapped predictor from it's black-box source as well as on the amount of unfairness in the adjusted outputs. In addition, empirical results are provided on commonly used datasets.", "questions": "- The analysis, in particular also the methodology to achieve fair outputs, relies on $\\eta^\\ast$, which in section 3, line 85 is defined as the true posterior, approximated from data. What does that mean? Using which approximation scheme? How is it related to some potential other, ground truth posterior? And most importantly, how is the assumption of having access to a true posterior realistic in practice? Without this quantity the fairness constraints in section 6 do not work. There are experiments in section 8, so there must be some way to approximate $\\eta^\\ast$, but I don't know how it's done (though there seem to be limitations with small datasets).\n- The proposed method for achieving fairness is based on splitting the $\\alpha$-trees at their root based on the different sensitive feature values. This means that data cannot be shared between the different sub-trees corresponding to different groups. Could this lead to issues in cases where some sub-groups are minorities and thus, insufficient training data for them is available? The minority-setting can be an issue in many scenarios where fairness is of concern.\n- Some concepts are not clear:\n    - The paper uses the term \"twisted\" posterior, but it's not fully clear to me what the characteristic property of a twist is and whether it just means \"bias\" in the conventional way used in the fairness literature, or whether there is some additional meaning to it. Could you clarify that?\n    - What is the mixture measure M introduced in section 3 and why do you need it?\n    - Regarding requirements (c) and (d), what do you mean by strong algorithmic guarantees (on what?) and what is meant by explainability, e.g. instance-based or for the whole model, about the difference of $\\eta_f$ from $\\eta_u$ or $\\eta_f$'s behavior in general, etc.?\n- Minor clarifications:\n    - Does theorem 2 imply that the loss is 0 when the conditions hold?\n    - It would be good to define the domain of $\\alpha$ in section 3. Not all values are permissible and I struggled to understand whether one would generally choose it from e.g. (0, 1), (-1, 1) (with exception of 0), $(-\\infty, +\\infty)$, etc.\n- Potential extension (I do not expect this to be included in this paper): the proposed method can be used to correct twists/biases in black-box predictions. It might be interesting to explore whether the technique can be used to tackle issues other than fairness as well, for example in the context of robustness, to correct for distribution shifts between training and deployment.", "limitations": "The main practical limitations I can see are the assumption of the availability of a true posterior and the problem having sufficient data for learning $\\alpha$-trees for minority groups. These issues are insufficiently addressed in the paper.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- The paper proposes a method to adjust the outputs of any black-box model to be compatible with a desired fairness goal. Having this ability is quite valuable given that the usage of pre-trained, off-the-shelf models is quite prevalent today which, however, may not be trained with any fairness considerations in mind.\n- The paper provides a solid theoretical analysis of the guarantees obtainable from the proposed algorithm along several dimensions, such as the divergence of the wrapped model from its source and the amount of residual unfairness in the wrapped predictions.\n\n### Weaknesses\n- The paper has a number of clarity issues:\n    - The intuition behind many definitions and results are not clear:\n        - Some results (e.g. theorem 1 and 2, lemma 3) propose bounds, but I have no intuition about what they mean. How strict are they? How strict are they relative to the strength of the assumptions made? This makes it hard to understand whether they are meaningful.\n        - Some definitions are unclear, see the questions part for more details.\n        - A lot of the analysis starts off by introducing some definitions or statements whose meaning only becomes clear later on. It would be very helpful to first provide an intuition, e.g. say what the goal of introducing a certain concept is and what idea it captures, for better understanding the analysis.\n    - In the intro, a number of desiderata for the post-processing process are introduced (a-f, and later g). While they mostly make sense, some (esp. c and d) are somewhat vague (see questions) and I am not sure what is meant by e.g. addressing them from a representation point of view and what the difference between the analytical and algorithmic perspective is. It feels like the points are also not addressed in a systematic manner, e.g. in section 4 (b) and (e,f) are mentioned and another point (g) is introduced, in section 5 (c) and (d, f) are mentioned. This scattering, in combination with the unexpressive names of the requirements makes it hard for me to keep track of them and make them overall not very useful. It would be helpful to formulate the requirements more clearly, address them in a more systematic way, and give them more meaningful names.\n    - The paper introduces a lot of concepts, esp. in section 3, which subsequently seem to be under-used. For instance, section 3 sets up core concepts using measure spaces, but then this level of abstraction seems to be unnecessary for the remaining paper. It appears like the exposition could be simplified by using more standard and simpler probabilistic notation instead. I did not check all the proofs in the appendix though, maybe this level of abstraction is needed there, but it comes at a high cost in terms of notational complexity which seems not immediately justified.\n    - Some concepts are introduced early (e.g. in section 3), but only instantiated a lot later in the paper, which makes it hard to understand them both when they first appear as well as when they are properly defined/used, because you need to go back and re-read their definitions. For example, $\\eta_t$ is introduced in section 4, but not really instantiated until section 6 and similarly for mixture measure M in section 3. It would be great to provide at least some intuition behind those concepts when first introducing them and ideally moving their introductions and instantiations closer together.\n- The implications of some of the theoretical results are unclear, i.e. what do the bounds mean? See clarity above for more details. This makes it hard to judge how useful the derived bounds are.\n- Some assumptions might be unrealistic for practical deployment, most importantly the assumption of having access to a true posterior $\\eta^\\ast$. See the first question for more details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_kluxkas-Z_", "reviewer": "Reviewer_4eKb", "summary": "The paper proposes a way to correct black-box models to fulfill certain notions of group fairness via post-processing.\nConcretely, the authors suggest to reweigh the posterior distribution of a classifier via a learned decision tree.\nTo this end, the potential bias of a black-box model is cast as a so-called twist. By considering a well-constructed loss, an untwisting function can be learned by minimizing this loss. The authors instantiate this for decision tree learning and three different notions of group fairness (conditional value at risk, equal opportunity, and statistical parity).\nTwo variants of their decision tree learning algorithm,  a conservative one, which sacrifices less accuracy to achieve fairness, and an audacious one, which allows larger changes in favor of fairness but potentially costing accuracy, are considered.\n\nThis is experimentally evaluated on tabular datasets. The proposed approach outperforms different baselines in terms of fairness notion.\nInterestingly, empirically it appears that the audacious and conservative versions don't exhibit the trade-off discussed above, but depending on the setting either one is strictly better (both in terms of fairness metric and accuracy).\n\n", "questions": "- Can you clarify which parts are your key contributions, especially compared to [24] and [14]?\n- What does MD (in Figure 4 and Section 8) measure? Is it the accuracy? If so, it seems bad for a binary task.\n\n", "limitations": "The authors provide a Limitation section, which seems to be adequate.\n", "rating": 4, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n## Strengths\n- Mathematically rigorous derivation.\n- Important/interesting use-case: e.g. finetuning a blackbox model to ensure fairness.\n\n## Weaknesses\n- Hard to read. (See \"Presentation\" below.)\n- Relation to some related work is unclear. (See \"Related\" below.)\n\n## Presentation & Evaluation\nWhile I appreciate the mathematical rigor I found the overall work hard to read.\nIn particular, I think the mathematical presentation almost hides the conceptual approach: i) get blackbox model, ii) train decision tree to debias the posterior. While the choice of loss to train the decision tree is theoretically well-motivated, in the end, it appears quite standard. \nSimilarly, it remains unclear what the exact contribution and what an instantiation of a prior approach is, e.g. TopDown from [14]. (Note: I don't think instantiating prior work to reach a particular goal is problematic.)\n\nFurther, on the first read, it was unclear to me that section 3 recounts background from [24] rather than a new contribution. At the same time, it appears not to be self-contained as binary task is taken from [24] without much explanation.\n\nI also found the evaluation section hard to read as all results are pressed in Figure 4. The selection of results is also quite small (although I appreciated the full additional results in the supplementary material). Lastly, it seems that the accuracy of the classifier is quite bad (see Questions below).\n\nMinor Presentation issues:\n- L240 \"of mapping\" seems to miss an article.\n- \"Limitations and conclusion\" (L335) does not have a section number.\n- While normally I don't mind if papers use modified vspace settings, it seems a little overdone here to the point where pages aver visually very dense. \n\n## Related Work\nThe paper does not discuss to which fairness notions it is limited to, i.e. group fairness, and how this relates to other notions of fairness, i.e. individual fairness, and how they are applied in the research community.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-5zvf98sPm7", "reviewer": "Reviewer_2a51", "summary": "This paper proposes a wrapper function in the post-processing to correct the classifier for fairness results. It adopts a previous paper that modifies the improper loss function to make it fair. The proposed boosting algorithm, called $\\alpha$-tree, corrects for fairness bias for three different notions: Conditional value at risk, Equality of opportunity, and Statistical Parity.", "questions": "I'm wondering why this algorithm is claimed to be interpretable? The only thing related is this method uses a tree-based model to correct for the bias. But an algorithm consisting of multiple trees like boosting or random forests can be equally complex as a DNN and thus should not be claimed interpretable.", "limitations": "None", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Disclaimer: I'm not an expert in fairness and the improper loss function and my expertise are in interpretability. I can not evaluate the theoretical section due to my incompetence, but this paper is mostly theoretical so my review will be quite shallow.\n\n# Strengths\n- Although the empirical performance is not as good as other methods, this wrapper method seems to be the first one that can adapt to different fairness criteria in a post-hoc way. And the conclusion also admits that.\n\n# Weaknesses\n- Questionable claim about interpretability.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept