Individually Fair Gradient Boosting
Authors: Alexander Vargo
Fan Zhang
Mikhail Yurochkin
Yuekai Sun
Venue: ICLR 2021 Spotlight (2021)
Keywords: Algorithmic fairness
boosting
non-smooth models

Abstract: We consider the task of enforcing individual fairness in gradient boosting. Gradient boosting is a popular method for machine learning from tabular data, which arise often in applications where algorithmic fairness is a concern. At a high level, our approach is a functional gradient descent on a (distributionally) robust loss function that encodes our intuition of algorithmic fairness for the ML task at hand. Unlike prior approaches to individual fairness that only work with smooth ML models, our approach also works with non-smooth models such as decision trees. We show that our algorithm converges globally and generalizes. We also demonstrate the efficacy of our algorithm on three ML problems susceptible to algorithmic bias.

Published as a conference paper at ICLR 2021
INDIVIDUALLY FAIR GRADIENT BOOSTING
Alexander Vargo
Fan Zhang
Department of Mathematics
School of Information Science and Technology
University of Michigan
ShanghaiTTehl University
ahsvargo uniiimuuiiiin ch. edu
zhangf an 4 wwwnghaitteeteeeeee weech edu. cn
Mikhail Yurochkin
Yuekai Sun
IBM Research
Department of Statistics
MIT-IBM Watson Al Lab
University of Michigan yueka @umi ch, edu
mi khaillll yurochkiii i bomm.mmm.......... com
ABSTRACT
We consider the task of enforcing individual fairness in gradient boosting. Gradient boosting is popular method for machine learning from tabular data, which arise often in applications where algorithmic fairness is a concern. At a high level, our approach is a functional gradient descent (distributionallyy) robust loss function that encodes our intuition of algorithmic fairness for the ML task at hand. Unlike prior approaches to individual fairesss that only work with smooth ML models, our approach also works with non-smooth models such as decision trees. We show that our algorithm converges globally and generalizes. We also demonstrate the efficacy of our algorithm on three MI. problems susceptible to algorithmic bias.
INTRODUCTION
In light of the ubiquity of machine learning (ML) methods in high-stakes decision-making making and support roles, there is concern about ML models reproducing or even exacerbating the historical biases against certain groups of users. These concerns are valid: there are recent incidents in which algorithmic bias has led to dire consequences. For example, Amazon recently discovered its ML-based resume screening system discriminates against women applying for technical positions (Dastin, 2018).
In response, the ML community has proposed myriad of formal definitions of algorithmic fairness. Broadly speaking, there are two types fairness definitions: group fairness and individual fairness (Chouldechova & Roth, 2018). In this paper, focus enforcing individual faimess. At high- level, the idea of individual fairness the requirement that a fair algorithm should treat similar individuals similarly. For while, individual fairness was overlooked in favor of group fairness because there is often no consensus on which users are similar for many MI tasks. Fortunately, there a flurry of recent work that addresses this issue (Ilvento, 2019; Wang et al., 2019; Yurochkin et al.. 2020; Mukherjee et al., 2020a). In this paper, we assume there is fair metric for the ML task at hand and consider the task of individually fair gradient boosting.
Gradient boosting, especially gradient boosted decision trees (GBDT), is popular method for tabular data problems (Chen & Guestrin, 2016). Unfortunately, existing approaches to enforcing individual fairness are either not suitable for training non-smooth ML models (Yurochkin et al., 2020) or perform poorly with flexible non- con-meramttric MI. models. We aim to fill this gap the literature. Our main contributions are:
1. We develop a method to enforce individual fairness in gradient boosting. Unlike other methods for enforcing individually fairness, our approach handles non-smooth ML models such as (boosted) decision trees.
2. We show that the method converges globally and leads to ML models that are individually fair.
We also show that it is possible to certify the individual fairness of the models posteriori.
3. We show empirically that our method preserves the accuracy of gradient boosting while improving widely used group and individual fairness metrics.

---

Published as a conference paper at ICLR 2021
2 ENFORCING INDIVIDUAL FAIRNESS IN GRADIENT BOOSTING
Consider a supervised learning problem. Let X C Rd be the input space and y be the output space. To keep things simple, we assume y {0, 1), but our method readily extends to multi-class classification problems. Define 2 = X' x {0. 1. We equip A' with a fair metric d, that measures the similarity between inputs. The fair metric is application specific, and we refer to the literature on fair metric learning (Ilvento, 2019; Wang et al., 2019; Yurochkin et al., 2020) for ways of picking the fair metric. Our goal is to learn an ML model f: - {0, 1] that is individually fair. Formally, we enforce distributionally robust fairness (Yurochkin et al., 2020), which asserts that an MI model has similar accuracy/performance (measured by the loss function) on similar samples (see Definition 2.1).
One way to accomplish this is adversarial training (Yurochkin et al., 2020; Yurochkin & Sun, 2020). Unfortunately, adversarial training relies on the smoothness of the model (with respect to the inputs), so it cannot handle non-smooth ML models (e.g. decision trees). We address this issue by considering a restricted adversarial cost function that only searches over the training examples (instead of the entire input space) for similar examples that reveal violations of individual fairness. As shall see, this restricted adversarial cost function is amenable to functional gradient descent, which allows us to develop a gradient boosting algorithm.
2.1 ENFORCING INDIVIDUAL. FAIRNESS WITH A RESTRICTED ADVERSARIAL. COST FUNCTION
We first review how to train individually fair ML models with adversarial training (see Yurochkin et al. (2020) for more details) to set up notation and provide intuition on how adversarial training leads to individual faimess. Let F be set of ML models, let e y x y - IR. be a smooth loss function (see Section 3 for concrete assumptions on E) that measures the performance of an ML model, and let D {( y/: )=
be a set of training data. Define the transport cost function
((11,)1) (I2, U2)) de (2) + 00 1 (V1#v2)
(2.1)
We see that c((x1, 31), (zz, 82)) is small iff Dı and are similar (in the fair metric dz)) and y/1 = V/2 In other words, is small iff two similar examples are assigned the same output. Define the optimal transport distance W (with transport cost e) on probability distributions on 2:
(PP,, Pa) A infnec(e,.PP) Jaxz c(21, 22 22)
(21, 22),
where C(P,, P2) is the set of couplings between P1 and P2 (distributions on 2 x Z whose marginals P1 and P2). This optimal transport distance lifts the fair metric (points in) the sample space to distributions on the sample space. Two distributions are close in this optimal transport distance iff they assign mass to similar areas of the sample space Z. Finally, define the adversarial risk function
(f( A supr: w(r.).) Ep((((()))))
(2.2)
where P. is the data generating distribution and > 0 is a small tolerance parameter. The adversarial risk function looks for distributions on the sample space that (i) are similar to the data generating distribution and (ii) increases the risk of the ML model f. This reveals differential performance of the MI. model on similar samples. This search for differential performance is captured by the notion of distributionally robust fairness:
Definition 2.1 (distributionally robust fairness (DRF) (Yurochkin et al., 2020)). An ML model h: X + y is disttrbbbuuul robustly fair (DRF) WRT the fair metric de iff
supp:w {(z, h)) 5.
(2.3)
In light of the preceding developments, natural cost function for training individually fair ML models is the adversarial cost function:
(f( & sup W.P.:W Er(((())
(2.4)
where Pn is the empirical distribution of the training data. This is the empirical counterpart of (2.2), and it works well for training smooth ML models (Yurochkin et al., 2020). Unfortunately, (2.4) is hard to evaluate for non- non-smooth ML models: it is defined as the optimal value of an optimization y) is not available because the MI. model is non-smooth.
problem, but the gradient 0, (f)(
2

---

Published as a conference paper at ICLR 2021
To circumvent this issue, we augment the support of the training set and restrict the supremum in
(2.4) to the augmented support. Define the augmented support set Do ê {(x,, W.), (2,, 1 y1)) and the restricted optimal transport distance WD between distributions supported on Do:
WD(Pi, P1, P2) _ inf inf. Jzxz c(21, 221 #2).
where Co(Pi, P2) is the set of distributions supported on Do x Do whose marginals are P1 and P2. We consider the restricted adversarial cost function
L(f) _ supr: (D(,,,)) (p(((f(X), Y),,
(2.5)
where 0 is small tolerance parameter. The interpretation of (2.5) is identical to that of (2.4): it searches for perturbations to the training examples that reveal differential performance the ML model. On the other hand, compared to (2.4), the supremum in (2.5) is restricted to distributions supported on 'Do. This allows us to evaluate (2.5) by solving a (finite-dimensional) linear program (L.P). As we shall see, this LP depends only on the loss values {[ [1(())))) v4) and (((())) vs). it is possible to solve the LP efficiently even if the ML model f is non-smooth. This is the key idea in this paper.
Before delving into the details, we note that the main drawback of restricting the search to distributions supported on Do is reduced power to detect differential performance. If the ML model exhibits differential performance between two (similar) areas of the imput space but only one area is represented in the training set, then (2.4) will detect differential performance but (2.5) will not. Augmenting the support set with the points {x,, 1 - y4) partially alleviates this issue (but the power remains reduced compared to (2.4)). This is the price we pay for the broader applicability of (2.5).
2.2 FUNCTIONAL GRADIENT DESCENT ON THE RESTRICTED ADVERSARIAL COST FUNCTION
Gradient boosting is functional gradient descent (Friedman, 2001), so key step in gradient boosting is evaluating Øÿ
aL where the components of j R are U; _ f(x).. By Danskin's 's theorem, we have aL 0g: 8f(:)) supp:: [p(e(((x)) y1)l = Eyey SW [((f( v)) P (Zt, 3),
(2.6)
where P is distribution that attains the supremum in (2.5). We note that there is no need to differentiate through the ML model f in (2.6), so it is possible to evaluate the functional gradient for mon-smooth ML models. It remains to find Pa. We devise a way of finding p by solving linear program.
We start with simplifying observation: if 222,, oo for any 2, E Do and 2j E D, then any weight at zj cannot be transported to 2, Thus, we will only focus on the pairs (z, 2j) E Do x D with o(z,, 2,) co. Let C E Raxa be the matrix with entries given by Cas = c((x; (z), v5)) = de (x), We also define the class indicator vectors y² E {0, 1)m by
y
yj = and y = 1, -y'
y¹.
(2.7)
0 9i For any distribution on Do. let Pi, = P([(rr k))) for k E 10. Then, the condition that WD(P, Px) & is implied by the existence of matrix IT such that
1. Ill T with I' = (II E R7*" x (I. < e, II 1, 11m
2. II )u.. and II 8 = (P......, P.,u).
Further define the matrix R E g2x" by Rúj {(f(zz), Uソ) this is the loss incurred if point j with label yj is transported to point i. With this setup, given the current predictor f. we can obtain a solution II" to the optimization as the solution to the linear program (in n² variables)
11 arg Hiel (R, 11).
(2.8)
Then the optimal distribution Pa on Do is given by P* (((x,, (([x,,)), k))) = (1I -y"), An outline of the full gradient boosting procedure is provided in Algorithm 1.
is important to note that we have made no assumptions about the class of candidate predictors F in finding the optimal transport map II in (2.8). In particular, F can contain discontinuous functions for example, decision trees or sums of decision trees. This allows us to apply this fair gradient boosting algorithm to any class F of base classifiers.
3

---

Published as a conference paper at ICLR 2021
Algorithm Fair gradient boosting
1: Input:
Labeled training data {zz Ue) |2 class of weak learners H: initial predictor fut search radius e; number of steps T; sequence of step sizes (9; fair metric d₂ on X
2: Define the matrix C by Cigj + (z;, x.y). do 4: Define the matrix RG by (Re)kz = ((fe(z)).
3: for 0, ....,,
5: Find I E arg maxner (Re, II;; and set ( k) +- (IT; . yy
6: Fit a base learner bg E H to the set of pseudo-residuals { (z)((1)) Jist (see (2.6)).
OL
7: Let Je+1- fe + anlt
8: end for
9: return fr
2.3 RELATED WORK
Enforcing individual fairness. There line of work that seeks to improve fairness guarantees for individuals by enforcing group fairness with respect to many (possibly overlapping) groups (Hébert-Johnson al., 2017: Kearns al., 2017; Creager et al., 2019; Kearns et al., 2019; Kim et al., 2019). There is another line of work on enforeing individual fairness without access to fair metric (Gillen al., 2018; Kim al., 2018; 8; Jung et al., 2019; Kearns et al., 2019). This line of work circumvents the need for a fair metric by assuming the learner has access to an oracle that provides feedback on violations of individual fairness. Our work part of a third line of work on enforcing individual fairness that assumes access to fair metric (Yurochkin et al., 2020; Yurochkin & Sun, 2020). The applicability of these methods has broadened thanks to recent work on the precursor task of learning the fair metric from data (Ilvento, 2019; Lahoti al., 2019; Wang et al., 2019; Mukherjee et al., 2020b). Unfortunately, these methods are limited to training smooth ML models.
Adversarial training and distributionally robust optimization. Our approach to fair training is also similar to adversarial training (Goodfellow et al., 2014; Madry et al., 2017), which hardens MI. models against adversarial attacks. There two recent papers fitting robust non-parametric classifiers (including decision trees) (Yang et al., 2019; Chen et al., 2019) but neither are applicable to enforcing individual faimess in gradient boosting. Our approach is also instance of distributionally robust optimization (DRO) (Blanchet et al., 2016; Duchi & Namkoong, 2016; Esfahani & Kuhn, 2015; Lee Raginsky, 2017; Sinha et al., 2017; Hashimoto al., 2018).
Before moving on, we remark that the key idea in this paper cannot be applied to adversarial training of non-smooth ML models. The goal of adversarial training is make ML model robust to adversarial examples that are not in the training set. The restriction to the augmented support set in (2.5) precludes such adversarial examples, so training with (2.5) does not harden the model against adversarial examples. On the other hand, long as the training set is diverse enough (see Assumption 3.3 for a rigorous condition to this effect), is possible to reveal differential performance in the ML model by searching over the augmented support set and enforce individual fairness.
3 THEORETICAL RESULTS
We study the convergence and generalization properties of fair gradient boosting (Algorithm 1). The optimization properties are standard: fair gradient boosting together with a line search strategy converges globally. This is hardly surprising in light of the global convergence properties of line search methods (see (Nocedal & Wright, 2006, Chapter 3)), so we defer this result to Appendix A.
The generalization properties of fair gradient boosting less standard. We start by stating the assumptions on the problem. The first two assumptions are standard in the DRO literature (see Lee & Raginsky (2017) and Yurochkin al. (2020)).
Assumption 3.1 (boundedness of input space). diam < 20
Assumption 3.2 (regularity of loss function). (i) is bounded: S E(f, & BVJEF,2EZ. (ii) Let & {((f.)) ff e F} denote the class of loss functions. C is We w2- -ipschitz with respect to dz: [C[, (1), {(J, (22, w))l S w2d. (xd, x2) for all 02 E X, y E y and f F.
4

---

Published as a conference paper at ICLR 2021
Additionally, the support of the data generating distribution P. should cover the input space. Oth- erwise, the training data may miss areas of the input space, which precludes detecting differential treatment in these areas. Similar conditions appear in the non-pariee com-aaametric classification literature, under the name strong density condition (Audihert & Tsybakov, 2007).
x..) = {ar E X dz < r] be the dg-ball of radius v around xx in X. There constants 5 > 0 and d such that P. (Ba, (r, )) 2 8r for any < 1.
Assumption 3.3. Let Ba, (r,
The lower bound or in Assumption 3.3 is motivated by the volume of the Euclidean ball of radius in Rdd being proportional to rd. For bounded input space X, Assumption 3.3 implies the probability mass assigned by P. to small balls is always comparable (up to the small constant 8) to the probability mass assigned by the uniform distribution on X. We note that this assumption is close the goal of Buolamwini & Gebru (2018) in their construction of the Pilot Parliaments Benchmark data.
Theorem 3.4. Under Assumptions 3.1, 3.2, and 3.3, we have
1
2wydiam((2)
suP (T(f) - (,) Sp (2/(2d)
W2 +
+
(3.1)
VE
Vn
The first term on the right side of (3.1) is the discrepancy between and Le, while the second term is the discrepancy between Le and L, (recall (2.2) and (2.4)). The second term is well-studied in the DRO literature (Lee & Raginsky, 2017; Yurochkin et al., 2020), so we focus on the first term, which captures the effect of restricting the search space in the supremum in (2.5) to the augmented support set Do- We see the curse of dimensionality in the slow n1/124, convergence rate, but this unavoidable. For the restricted search for differential performance on Dn emulate the search on X. the size of 'Do must grow exponentially with the dimension d. This leads to the exponential dependence on in the first term.
We note that it is possible for the dimension d in Assumption 3.3 to be smaller than dim (X)). Intuitively, the fair metric dæ ignores variation in the inputs due to the sensitive attributes. This variation is usually concentrated in a low-dimensional set because there are few sensitive attributes in most ML tasks. Thus the metric effectively restricts the search this -iwdimensional space, so the effective dimension of the search is smaller. In such cases, the convergence rate will depend on the (smaller) effective dimension of the search.
One practical consequence of Theorem 3.4 is it is possible to certify posteriori that (non-smooth) MI. model is individually fair by checking the empirical performance gap
L(F) - - (((())) vs).
(3.2)
As long the (non-adversariall empirical risk converges to its population value, Theorem 3.4 implies
supyez [L(f) - ((
(I,(F) Ep. [p,((((()) & 0.
(3.3)
In other words, the (empirical) performance gap L(/) - (((x)) yi) generalizes. Thus it is possible for practitioners to certify the worst-case performance differential of ML model (up to an eтror term that vanishes in the large sample limit) by evaluating (3.2).
4 SCALABLE FAIR GRADIENT BOOSTING
A key step in the fair gradient boosting Algorithm 1 is finding the worst-case distribution p This entails solving a linear program (LPP in n² variables (n is the size of the training set). It is possible to use an off off-th LP solver to find P*, but solving an LP in n² variables per iteration does not scale to modern massive datasets. In this section, we appeal to duality to derive a stochastic optimization approach to finding the worst-case distribution. At a high level, the approach consists of two steps:
1. Solve the dual of (2.8). The dual is a univariate optimization problem, and it is amenable to stochastic optimization (see (B)..)). Computational complexity O(n).
2. Reconstruct the primal optimum from the dual optimum. Computational complexity is O(n²).
We see that the computational complexity of this step is O(n²), which is much smaller than the complexity of solving an I.P in n² variables. This two-step approach is similar the dual approach
5

---

(IT" -y);, There are multiple Published as a conference paper at ICLR 2021
to solving (unrestricted) DRO problems. Due to space constraints, summarize the two steps in Algorithm and defer derivations to Appendix B. We also include in Appendix an entropic regularized version of the approach that sacrifices exactness for additional computational benefits.
We remark that it is possible to achieve further speedups by exploiting the properties the fair metric. We start by observing that the cost of recovering the primal solution (step 10 in Algorithm 2) dominates the computational cost of Algorithm 2. Recall the search for differential performance is restricted by the fair metric a small set of points. This implies the argmax step 10 of Algorithm 2 is restricted to a few points that are similar to Iÿ in the fair metric. This can be seen from the corresponding argmax expression: if Ci large, is unlikely be a solution neighbors of each point can be computed in advance and re-used during training. This further reduces the cost of recovering the primal solution from ( (1m)), where m is the maximum number of neighbors of point. With this heuristic it should be possible to train our algorithm whenever the vanilla GBDT feasible.
argmax. The
We now state the full fair gradient boosting algorithm that combines the framework presented in Section 2.1 with the preceding stochastic optimization approach to evaluating the worst-case distribution. We refer to the GBDT method as TreeBoost; this can be replaced with any GBDT algorithm. In every boosting step in Algorithm 3, we find the optimal transport map II using Algorithm 2. We then boost for step using the GBDT training methods on the augmented data set Do weighted according to the distribution given by P P({ hyperparameters that be tweaked in the GBDT model (e.g. the maximum depth of the trees in F); we represent this by including a list of GBDT parameters as an input to Algorithm 3.
Algorithm 2 SGD find optimal dual variable 17" and approximate II"
1: Input: Initial 1/1 > 0; cost matrix C; loss matrix R; tolerance batch size B; step sizes on O.
2: repeat
3: Sample indices j1, Ji,... jBB uniformly random from [I....n)
4: Let RG < columns Ji.... JB of R. Let C. t- columns .Jn of C. (Re, Ct E RBxB)
5: Let (v) +- 11 +
max; Raj Ci
6: 7/+1 f max 1/2 at 2n
w. (n)3
7: until converged
8: Set IT be
matrix of zeros; 17" is the final value from above.
9: for j = 0 to n do
Choose
arg max;R.) 11 Oej and He 1.
11: end for return II
Algorithm Fair gradient boosted trees (BuDRO)
1: Input: Data D = {0,, 3:) W perturbation budget e; loss function E; fair metric dN on X:
number of boosting steps T: GBDT parameters p. batch size B
2: Let Do = { (rr, |- U (2;, 1) 1) and define C' by Cik +- dz, rx).
3: Let fu
CrreBBosst.Train
data =Do Steps =1) (Run one step of plain boosting
4: for t = to T do
5: Define R by R. E(fe, (I,, v1)).
6: Construct II, following Algorithm 2 with inputs C, R, and B
7: Let wi be the concatenation of II y and II, 1..yv. yy
8: Let fr+1 + TreeBoost. wer.eBoos...Tii(p..... fú, data =Do, weights w Steps =1).
9: end for
10: Return fr.
EXPERIMENTS
We apply BuDRO (Algorithm 3) to three data sets popular in the faimesss literature. Full descriptions of these data sets and a synthetic example are included in Appendix C. Timing information is also found in Appendix C.6. BuDRO uses the XGBoost algorithm (Chen & Guestrin, 2016) for the GBDT

---

Published as a conference paper at ICLR 2021
method, and f is the logistic loss. These experiments reveal that BuDRO is successful in enforcing individual fairness while achieving high accuracy (leveraging the power of GBDTs). We also observe improvement of the group fairness metrics.
Fair metric. Recall that a practical implementation of our algorithm requires a fair metric. We consider the procedure from Yurochkin et al. (2020) to learn the fair metric from data. They propose metric of the form (2 x2) = (a) Z2, Q(2) - Ø2)), where Q is the projecting matrix orthogonal to some sensitive subspace. This sensitive subspace is formed by taking the span of the vectors orthogonal to decision boundaries of linear classifiers fitted to predict a (problem specific) set of protected attributes (e.g. gender, race or age). The idea behind this procedure that the sensitive subspace captures variation in the data due to protected information of the individuals. A fair metric should treat individuals that only differ in their protected information similarly, i.e. distance between pair of individuals that only differ by component in the sensitive subspace should be 0.
Comparison methods. We consider other possible implementations of fair GBDT given existing techniques in the literature. As mentioned previously, due to the non-differentiabiiiyy of trees, the majority of other individual fairness methods are not applicable to the GBDT framework. For this reason, we limit our analysis to fair data preprocessing techniques before applying vanilla GBDT method. We report the results when considering two preprocessing techniques: project that climinates the protected attributes and projects out the sensitive subspace used for the fair metric construction (Yurochkin et al., 2020), and reweigh that balances the representations of protected groups by assigning different weights to the individuals (Kamiran & Calders, 2011).
Evaluation metrics. To evaluate the individual fairesss of each method without appealing to the underlying fair metric (i.e. to avoid giving our method and project an unfair advantage at test time, and to verify generalization properties of the fair metric used for training), we report data-specific consistency metrics. Specifically, for each data set, we find set of attributes that are not explicitly protected but are correlated with the protected attribute (e.g. is s__usbband or is__iff wife when gender is protected) and vary these attributes create artificial counterfactual individuals. Such counterfactual individuals are intuitively similar to the original individuals and classifier output should be the same for all counterfactuals to satisfy individual fairness. We refer to classification consistency as the frequency of classifier changing its predictions the aforementioned counterfactuals.
We also examine group fairness for completeness. We consider the group fairness metrics introduced in De-Arteage et al. (2019). Specifically, we compute the differences in TPR and TNR for each pro- tected attribute, and report the maximum (GAPMax) and the root-mean root-mean-squared statistics (GAPRMS) of these gaps. See Appendix C for full description of all comparison metrics.
5.1 GERMAN CREDIT
The German eredit data set (Dua & Graff, 2017) contains information from 1000 individuals; the ML task is to label the individuals as good or bad credit risks. We treat age as the protected attribute in the German data set. The age feature not binary; this precludes the usage fair methods that assume two protected classes (including the reweighing preprocessing technique). In the United States, it is unlawful to make credit decisions based on the age of the applicant; thus, there are distinct legal reasons to be able to create classifier that does not discriminate based on age.
For the fair metric, we construct the sensitive subspace by fitting ridge regression on age and augment it with an indicator vector for the age coordinate (see Appendix C.3). This subspace is also used for data preprocessing with the project baseline. For the individual fairness consistency evaluation we consider varying personal status feature that encodes both gender and marital status (S-cons).
Table 1: German credit: average results over 10 splits into 80% training and 20% test data.
Age gaps
Method
BAcc
Status cons
GAPMax
GAPRMS
BuDRO
.715
.944
.185
.151
Baseline
.723
.920
.310
.241
Project
.698
.600
.188
.144
Baseline NN
.687
.826
.234
.179
7

---

Published as a conference paper at ICLR 2021
We present the results in Table (see Table 5 for enror bars). To compare classification performance we report balanced accuracy due to class imbalance in the data. The baseline (GBDTs with XGBoost) is the most accurate and significantly outperforms baseline neural network (NN). The BuDRO method has the highest individual fairness (S-cons) score while maintaining a high accuracy and improved group fairness metrics. Preprocessing by projecting out the sensitive subspace is not as effective as BuDRO in improving individual fairness and also can negatively impact the performance.
5.2 ADULT
The Adult data set (Dua & Graff, 2017) another common benehmark in the fairness literature. The task is to predict if an individual earns above or below $50k per year. We follow the experimental setup and comparison metrics from the prior work on individual fairness (Yurochkin et al., 2020) studying this data. Individual fairness is quantified with two classification consistency measures: one with respect to relationship status feature (S-cons) and the other with respect to the gender and race (GR-cons) features. The sensitive subspace is learned via logistic regression classifiers for gender and race and augmented with unit vectors for gender and race. Note that the project preprocessing baseline is guaranteed to have perfect GR-cons score since those features explicitly projected out; it is interesting to assess if it generalizes to S-cons, however.
Table Adult: average results over splits into 80% training and 20% data. NN. SenSR and Adversarial Debiasing (Zhang et al., 2018) numbers are from Yurochkin et al. (2020).
Individual fairness
Gender gaps
Race gaps
Method
BAcc
S-cons
GR-cons
GAPMax
GAPRMS
GAPMax
GAPRMS
BuDRO
.15
.944
.957
.146
.114
.083
.072
Baseline
.844
.42
.913
.200
.166
.098
.082
Project
.787
881
.079
.069
.064
.050
Reweigh
.784
.853
.949
.131
.093
.056
.043
Baseline NN
829
.888
.655
.216
.179
.105
.089
SenSR
.789
934
.944
.087
.068
.067
.055
Adv. Deb.
.815
.807
.841
.110
.082
.078
.070
The results are in Table 2 (see Table 7 for error bars). The baseline GBDT method is again the most accurate; it produces poor gender gaps, however. BuDRO is less accurate than the bascline, but the gender gaps have shrunken considerably, and both the S-cons and GR-cons very high. Project and reweighing produce the best group fairness results; however, their S-cons values are worse than the baseline (representing violations of individual fairness), and they also result in significant accuracy reduction.
Comparing the results from Yurochkin et al. (2020), BuDRO is slightly less accurate than the baseline NN, but improves on all fairness metrics. BuDRO matches the accuracy of adversarial debiasing and greatly improves the individual fairness results there. Finally, BuDRO improves upon the accuracy of SenSR while maintaining similar individual fairness results. We present additional studies of the trade-off between accuracy and fairness Figure 3 of Appendix C.4.I.
Overall, this and the preceding experiment provide empirical evidence that BuDRO trains individually fair classifiers while still obtaining high accuracy due to the power of GBDT methods.
5.3 COMPAS
We study the COMPAS recidivism prediction data set (Larson et al., 2016). The task is to predict whether a criminal defendant would recidivate within two years. We consider r ce (Caucasian not-Caucasian) and gender (binary) protected attributes and use them to learn the sensitive subspace similarly to previous experiments. Due to smaller data set size, instead of Algorithm 2, we considered entropy-regularized solution to (2.8) presented in Appendix B. The individual faimess consistency measures are gender consistency (G-cons) and coniisonns (R-cons).
The results collected in Table 3 (see Table 9 for error bars). COMPAS is data set where NNs outperform GBDT in terms of accuracy. but this results in poor group and individual fairness measurements. A NN trained with SenSR shows similar accuracy BuDRO, but worse performance
8

---

Published as a conference paper at ICLR 2021
Table 3: COMPAS: average results over 10 splits into 80% training and 20% test data.
Individual fairness G-cons
Gender gaps
Race gaps
Method
Acc
R-cons
GaPMax
GAPRMS
GaP
GAPRMS
BuDRO 0.652
1.000
1.000
0.099
0.124
0.125
0.145
Baseline
0.677
0.944
0.981
0.180
0.223
0.215
0.258
Project 0.671
0.874
1.000
0.150
0.190
0.185
0.230
Reweigh
0.666
0.788
0.813
0.207
0.245
0.069
0.092
Baseline NN
0.682
0.841
0.908
0.246
0.282
0.228
0.258
SenSR 0.652
0.977
0.988
0.130
0.167
0.159
0.179
Adv. Deb.
0.670
0.854
0.818
0.219
0.246
0.108
0.130
both in group and individual fairness. We conclude that even in problems where neural networks outperform GBDT, BuDRO is an effective method when taking faimess into consideration.
SUMMARY AND DISCUSSION
We developed gradient boosting algorithm that enforces individual fairness. The main challenge of enforcing individual fairness is searching for differential performance in the ML model. and we overcome the non-smoothness of the MI. model by restricting the search space to finite set. Unlike most methods for enforcing individual fairness, our method accepts non-smooth MIL models. We note that the restricted adversarial cost function developed for fair gradient boosting may be used to audit other non-smooth ML models (e.g. random forests) for differential performance, but we defer such developments to future work. Theoretically, we show that the resulting fair gradient boosting algorithm converges globally and generalizes. Empirically, we show that the method preserves the accuracy of gradient boosting while improving group and individual fairness metrics.
ACKNOWLEDGEMENTS
This paper is based upon work supported by the National Science Foundation (NSF) under grants no. 1830247 and 1916271. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the NSF.
REFERENCES
Julia Angwin and Jeff Larson. Bias in criminal risk scores is mathematically inevitable, researchers say. Propublica, available at: https://goo. gl/S3Gwen (accessed March 2018). 2016.
Yves Audibert and Alexandre B. Tsybakov. Fast learning rates for plug-in classifiers. An- nals of Statistics, 35(2):608-633 633, April 2007. ISSN 0090-5364, 2168-8966. doi: 10.1214/ 00905360600000012.1.
Rachel K. E. Bellamy, Kuntal Dey, Michael Hind, Samuel C. Hoffman, Stephanie Houde, Kalapriya Kannan, Pranay Lohia, Jacquelyn Martino, Sameep Mehta, Aleksandra 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. arXiv: [cs], October 2018
Jose Blanchet and Karthyek R. A. Murthy. Quantifying Distributional Model Risk via Optimal Transport. arXiv:1604.01 [math, stat], April 2016.
Jose Blanchet, Yang Kang, and Karthyek Murthy, Robust Wasserstein Profile Inference and Applica- tions to Machine Learning. 1610v:1610.05000 (math, stat], October 2016.
Amanda Bower, Laura Niss, Yuckai Sun, and Alexander Vargo. Debiasing representations by removing unwanted variation due to protected attributes. arXiv: 1807.0047) [cs], July 2018.

---

Published as a conference paper at ICLR 2021
Joy Buolamwini and Timnit Gebru. Gender Shades: Intersectional Accuracy Disparities in Commer- cial Gender Classification, In Proceedings of Machine Learning Research, volume 87, pp. 77-91, 2018.
Hongge Chen, Huan Zhang, Duane Boning, and Cho-Jui Hsieh, Robust decision trees against adversarial examples. ArXiv, 0ens/192..1660,, 2019.
Tianqi Chen and Carlos Guestrin. XGBoost: A Scalable Tree Boosting System. Proceedings the 22nd ACM SIGKDD International Conferencee on Knowledge Discovery and Data Mining KDD '1, pp. 785-794, 2016. doi: 10. 01..1144/293672229997777
Alexandra Chouldechova and Aaron Roth. The Frontiers of Faimess Machine Learning. arXiv:1810.08810 [cs, stat], October 2018.
Elliot Creager, David Madras, Jörn-Henrik Jacobsen, Marissa A. Weis, Kevin Swersky, Toniann Pitassi, and Richard S. Zemel. Flexibly fair representation learning by disentanglement. ArXiv, 0ass/996.025899 2019.
Jeffrey Dastin. Amazon scraps secret AI recruiting tool that showed bias against women. Reuters, October 2018.
Maria De-Arteaga, Alexey Romanov, Hanna Wallach, Jennifer Chayes, Christian Borgs, Alexandra Chouldechova, Sahin Geyik, Krishnaram Kenthapadi, and Adam Tauman Kalai. Bias in Bios:
A Case Study of Semantic Representation Bias in a High-Stakes Setting. Proceedings of the Conference on Fairness, Accountability, and Transparency FAT* '19, pp. 120- 128, 2019. doi: 10. 00.11445/328555003287722
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://
archive..cs..ci.eduuaa
John Duchi and Hongseok Namkoong. Variance-based regularization with convex objectives. Journal of Machine Learning Research, October 2016.
Peyman Mohajerin Esfahani and Daniel Kuhn, Data-driven Distributionally Robust Optimization Us- ing the Wasserstein Metric: Performance Guarantees and Tractable Reformulations. Mathematical Programming, May 2015.
Anthony W Flores, Kristin Bechtel, and Christopher T Lowenkamp. False positives, false negatives, and false analyses: A rejoinder to machine bias: There's software used across the country to predict future criminals. and it's biased against blacks. Fed. Probation, 80:38, 2016.
Jerome H. Friedman. Greedy function approximation: gradient boosting machine. The Annals of 2001. ISSN 0090-5364, 2168-8966. doi: 10.1124//os/1111111 watps///13113331
Statistics,
Sahaj Garg, Vincent Perot, Nicole Limtiaco, Ankur Taly, Ed Huai hsin Chi, and Alex Beutel. Counterfactual fairness text classification through robustness. AIES '19, 2018.
Aude Genevay, Marco Cuturi, Gabriel Peyré, and Francis Bach. Stochastic Optimization for Large- scale Optimal Transport. In NIPS (ed.), NIPS 2016 Thirtieth Annual Conference on Neural Information Processing System, Proc. NIPS 2016, Barcelona, Spain, December 2016. URL https: httppp/////a..aaieeeeeeeeee htt.::/vwwwwuueete.e..eeeaeeee httpp///...accccceeeeeeerrrrrraa -tt.ttee..../aa1-1111166444 01321664.
Stephen Gillen, Christopher Jung, Michael Kearns, and Aaron Roth. Online Learning with an Unknown Fairness Metric. 18Xiv:1802.06996 [cs], February 2018.
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnessing Adversarial Examples. arXiv preprint 4rXiv:1412.6577 December 2014.
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness Without Demographics in Repeated Loss Minimization. arXiv: 080018000.0010 [cs, stat], June 2018.
Úrsula Hébert-Johnson Michael P. Kim, Omer Reingold, and Guy N. Rothblum. Calibration for the caamputatooaally-ddenffaaabl Masses. arXiv e-prints, art. 1111:1111881/11 Nov 2017.
10

---

Published as a conference paper at ICLR 2021
Christina Ilvento. Metric Learning for Individual Fairness. arXiv:1906.00250 [cs, stat], June 2019.
Abdul Jerri. Introduction to integral equations with applications. John Wiley & Sons, 1999.
Christopher Jung, Michael J. Kearns, Seth Neel, Aaron Roth, Logan Stapleton, and Zhiwei Steven Wu. Eliciting and enforcing subjective individual fairness. CoRR, 1abo//990511066 2019, URL http::/arxxv.orrg/ http://....rraa/////..11555
Faisal Kamiran and Toon Calders. Classifying without discriminating. 2009 2nd International Conference Computer, Control and Communication. IEEE, February 2009. doi: 10.1 10.1109/ ic4.2009.4909 4909197. URL https:/ /ttp:///////.///////////////////
Faisal Kamiran and Toon Calders. Data preprocessing techniques for classification without discrimination. Knowledge and Information Systems, 33(1):1-33, December 2011. doi: 1.11007//1011--01--4404
URL htts::/: http:::://dooorrog/// 01110000000011111111000444100000
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness. arXiv e-prints, art. arXiv: 1111.05144, Nov 2017.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. An empirical study of rich subgroup fairness for machine learning. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* '19 pp. 100-109, New York, NY, USA, 2019. ACM. ISBN 978- URL http: http:p///dii.acmoog/1.....
1-4503-6125-5. doi: 10. 10.1145/3287550032877335 $287560.3287592.
Michael Kearns, Aaron Roth, and Saeed Sharifi- Maaaiii-Malajerrdi.. Average Individual Fairness: Algorithms, Generalization and Experiments. arXiv e-prints, art. arXiv:1905. May 2019.
Michael Kim, Omer Reingold, and Guy Rothblum. Fairness through computationally-bounn bouunded awareness. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Dasa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. ciates, Inc., 2018. URL httptt:::p/ppppr.s.p...... httpppppcccpppp////33333 fapperr/733-faireeeeee -nt throghh
Curran Asso-
Michael P. Kim, Amirata Ghorbani, and James Zou. Multiaccuracy: Black-box post-processing for fairness in classification. Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, AIES 19, pp. 247-254, New York, NY, USA, 2019. ACM. ISBN 97--1-943---6632222 doi: 10.114553306618.33/ 14287. URL http:tp:/aaa......oo///11111111/
Preethi Lahoti, Krishna P. Gummadi, and Gerhard Weikum. Operationalizing individual fairness with pairwise fair representations. ArXiv, abs/1907.01439, 2019.
Jeff Larson, Surya Mattu, Lauren Kirchner, and Julia Angwin. How we analyzed the compas recidivism algorithm. ProPublicu (5 2016), 9, 2016.
Jaeho Lee and Maxim Raginsky. Minimax Statistical Learning with Wasserstein Distances. 17X.v:1705.07815 [es], May 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks. arXiv:1706.000 06083 [cs, stat],
June 2017.
Llew Mason, Jonathan Baxter, Peter L Bartlett, Mareus Frean, al. Functional gradient techniques for combining hypotheses. Advances in Neural Information Processing Systems, pp. 221-246. 1999.
Debarghya Mukherjee, Mikhail Yurochkin, Moulinath Banerjee, and Yuekai Sun. Two simple ways to learn individual faimess metrics from data, 2020a.
Debarghya Mukherjee, Mikhail Yurochkin, Moulinath Banerjee, and Yuekai Sun. Two simple ways to learn individual faimesss metrics from data. In International Conference on Machine Learning, July 2020b.
11

---

Published as a conference paper at ICLR 2021
Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer Series in Operations Research. Springer, New York, 2nd edition, 2006. ISBN 978-0-387-300003--
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikít-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830. 2011.
Flavien Prost, Nithum Thain, and Tolga Bolukbasi. Debiasing Embeddings for Reduced Gender Bias in Text Classification. MrXiv:1908.0240 [cs, stat), August 2019.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying Some Distributional Robustness with Principled Adversarial Training. arXiv: 10571 [cs, stat], October 2017.
Hanchen Wang, Nina Grgic-Hlaca, Preethi Lahoti, Krishna P. Gummadi, and Adrian Weller. An Empirical Study on Learning Fairness Metrics for COMPAS Data with Human Supervision. arXiv: 10255 [cs], October 2019.
Hanchen Wang, Nina Grgic-Hlaca, Preethi Lahoti, Krishna P. Gummadi, and Adrian Weller. An Empirical Study on Learning Fairness Metrics for COMPAS Data with Human Supervision. arXiv e-prints, art. Xrxiv: 1910 10.55, Oct 2019.
Yao- Yuan Yang, Cyrus Rashtchian, Yizhen Wang, and Kamalika Chaudhuri. Adversarial examples for non-parametric methods: Attacks, defenses and large sample limits. ArXiv, abs/1906.03310, 2019.
Mikhail Yurochkin and Yuekai Sun. SenSel: Sensitive Set Invariance for Enforcing Individual Faimess. arXiv:2006. 14168 [cs, star), June 2020.
Mikhail Yurochkin, Amanda Bower, and Yuekai Sun. Training individually fair ML models with sensitive subspace robustness. In International Conference on Learning Representations, Addis Ababa, Ethiopia, 2020.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In AIES '18, 2018.
12

---

Published as a conference paper at ICLR 2021
A PROOFS OF THEORETICAL RESULTS
A.1 NUMERICAL CONVERGENCE RESULTS
In this section, we focus on analyzing the numerical convergence of our boosting algorithm. To do so, we will work in the framework similar to that found in previous boosting literature (e.g. Mason et al. (1999)). To be concrete, we assume that y C R. Then, we consider all base classifiers to be of the form h: (II,,..., En 7 Y and thus treat base classifier h as a vector h E I=" (precisely, h = (h(z1)..... ((ne)....,,,(,,,)) h(
". Moreover, we define the vector y = [y1...... Dno] E R". In this framework, the loss e takes the form l: I" x R" R. defined by E(f.y) - Li=1 { V4). We abuse notation and write [ff) for the robust loss function; this is a functional on IR" since it only depends the values f(); for I2 {x1, ................. F-n
In this context, given a functional F: R - R, the functional derivative F the gradient of F. Additionally, || denotes the standard Euclidean norm R"
We require several assumptions for these results:
Assumption A.1. (i) is convex as well as first- and second-order differentiable with respect to f. (ii) For any v E R", E is W1 -ipschhit differentiable, meaning there exists constant 0 such that for any f, E R
VV(f.v) - vē(f, v)ll S w1 fll.
The assumption that the loss is convex restrictive, and only invoke it here to show global convergence. In section 3, we also assume the loss function is bounded. This pair of assumptions (convexity and boundedness) space (see Assumption 3.1).
particularly restrictive because we have in mind bounded input
We additionally require the following assumption, which is standard in the gradient descent literature (Nocedal & Wright, 2006). Essentially, we suppose that our boosting algorithm moves in a sufficient descent direction each iteration. That is, the weak learner can ensure the angle between the searching direction and the functional gradient is bounded.
Assumption A.2. There is value 6 >> O, such that Algorithm can find a function h, with
(VL(f)) h.) 02 = [F) [b,]| 2 for all 1.
(A.1)
The following convergence result is consequence general results on the convergence of functional gradient descent algorithm for minimizing cost functionals (Mason et al., 1999). It states that, with specific step-size, Algorithm will converge to some classifier l
Theorem A.3. Under Assumptions A.I and A.2, suppose we run Algorithum with step-sizes
(f)(f.) hd)
ar W1 [, 1
(A.2)
Then, the optimization converges, i.e.: lim ((f))) 0.
t-+00
This framework also results in the following, which shows that we obtain a global optimal solution. Theorem A.4. Under Assumptions A.I and A.2, suppose {fe) is the sequence generated by Al- gorithm I with step-size given by (A.2). Then, any stationary point {fe) is the global optimal solution.
The specific step-size presented above is only required for analyzing the convergence properties of Algorithm 1, which can be easily replaced by step-size selected by some line search methods.
We begin the proof of numerical results by providing following preparatory properties of the cost functional L.
Lemma A.5. Under Assumption A.I, it holds
(i) L convex, first- and second-order differentiable with respect
13

---

Published as a conference paper at ICLR 2021
(ii) is a di that is VI((F) VI((f) s will fll
(A.3)
for any f
Proof of Lemma A.5. For part (i), recall L(f) PT ((f(fy)) combining with Assumption A.1 (i), have
(L(r)= (Piag())e(C) and L() - (iag(()V
where diag(P P) is diagonal matrix with (diag(P)) P. for i 1, ... Since P E [0, 1]" and
Ei=1 P. = 1, L(f) is a linear combination of {ff,, y:). Therefore, L is a convex functional of f.
For part (ii), according to Assumption A. ((i), {(f, y) is -Lipscchitz differentiable with respect yielding
(f, S w1
(A.4)
Given any f E F, it holds
V L(F)I = (
x ||diag( P)]l (f)
(A.5)
M W1:
where the first inequality follows from Gahwhy-Schwarz inequality and the second inequality follows from Assumption (A.4) and P [0, 1]". Combining (A.5) with the mean value theorem (for
functionals) (Jerri, 1999), it holds
[V VL(f)I ( c) 11.11 1 ff-fl
Swill | fll.
where e [0, 1]. completes the proof.
Proof of Theorem A.3. By Lemma A.5, have following lower bound for the difference between two successive loss functions:
wi(ar)
L(f.) [(fe+1) 2 L(f.)
[(ff))(((VL()))) h₂)
||b,
2
(ax))
= =aa<(VL(f) h.)
2 |
We choose (VL(f,b).) wi b,]l
as (A.2) to make the greatest reduction, which yields
[V)(f)), h,)
L(G) - L(f
(A.6)
2w1 [
Combining (A.6) with the sufficient decrease condition
(A.1), we have
82 (
L(f,) - L(f(+))
(A.7)
2w1
Summing up both sides of (A.7) from 30, we have
2
2w1 (L(f.) L(f++t)) <
2w1
VVL
<
L(fo) < oo,
82
where the second inequality follows by f, 2 0 for all 4, yielding
lim V ((f,) = 0. 100
14

---

Published as a conference paper at ICLR 2021
Proof of Theorem A.4. Suppose f. is stationary point of {f(). We prove this theorem by contradic- tion by assuming that we can find a point f lin(F) such that L(f) Lf.)).
The directional derivative of L at f. the direction f f, given by
L(C. + <(f - 4(,))
(VL( f -
ff) f.)= lim <10
Since convex, it holds
(L(F) + (1 (1- () - L(fe)
(VL,C),f-f, lim
c10
S
((f- I(f.) <.
Therefore, VL((.) o O, which makes the contradiction.
A.2 PROOFS OF GENERALIZATION ERROR BOUNDS
Proof of Theorem 3.4. Under Assumptions 3.1, 3.2, 3.3, we have the following result from Proposi- tion 3.2 in Yurochkin et al. (2020) (recall Equations (2.2) and (2.4))
Le(f) - L,(( - as
000
Then, our proof is completed by showing L converges to Le uniformly in F. It has been shown (Blanchet & Murthy, 2016) that the dual to the optimization Le defined in (2.4) is given by
n
Ly(h) inf de X20
Σ sup [(((x). 31) + Ad2 (z. zz). Ze
(A.8)
n
Likewise, calculations (see Appendix B.3) reveal that the dual (2.5) is given by
L(h) = inf AE- 1 X
Σ
max (ai........)
{(h(z). + Xd x;)
(A.9)
We thus need to establish bound on
1
8n- = inf de
Σ
sup ((h(z), vi) + (x,
A20
x
inf
λ
max (aL
{(h(z), v.) + (x,
(A.10)
X
#
To do so, let Xn be a minimizer of (A.9). Then, we have that
8n < Anc
sup ((h(x). v.) + X (x)
#EX
An + max
((h(x). (x,
EI......
E(h(z), vi) + da sup {(h(2), + An (A.11)
max ......))
xEN
Define map T' on D such that T(x;) argsupzex ((b(z), v.) An By assumption, have that
x })) 2 8/
(A.12)
Thus, the probability of the event ((rI,.... In. n nU B (Txx)) = 03 (i.e. the event that there points in the training data in B, 1/20 (T(x;)) most (1 11 n(1 - 8/22
15

---

Published as a conference paper at ICLR 2021
Thus assume that, for each there is point (2f, D such that x; E Bn-1/za Then, continuing from (A.11), we have that
on
((h(z;)) ui)
-d) (T(T(
(A.13)
12
Wyd (at T(x:) + (d
d(T( (A.14)
W2
(indiam(X))
(A.15)
n 1/2d
1/2dd
W2
2wadiam (X)
(A.16)
n2/2d
n n1/2d
In line (A.14), we use the fact that is wz-Lipschitz with respect to d, (Assumption 3.2(ii). In
line (A.15) 15), we use the fact that at E BB-1/2z (T(r:)) with the triangle inequality (to get that d(æt. 24) d(T(()), 244 S d(æ; ())))) and with the fact that dxT( xx) diam( Finally, Finally
in line (A.16), we apply Lemma A.1 from Yurochkin et al. (2020) which asserts that 0 S An S 22 This completes the proof of the desired result.
Compared to most theoretical studies of distributionally robust optimization, the proof of Theorem 3.4 is complicated by the restriction of the c-transform to the sample 'D in (A.9). This complication arises because the max over the sample is generally (much) smaller than the max over the sample space due to the curse of dimensionality. This discrepancy between the max over the sample and the max over the space space is responsible for the dependence of the rate of convergence on the dimension of the feature space in Theorem 3.4.
B FURTHER IMPLEMENTATION CONSIDERATIONS
Here we present method based on entropic regularization that can be used quickly obtain an approximate solution to the linear program in Equation 2.8. Moreover, this method requires only simple matrix computations; thus, we are able to implement TensorFlow for quick GPU computations.
also possible to quickly find the solution to the dual the linear program (2.8). Obtaining the primal optimizer II* from the dual solution, however, can be difficult. For this reason, the Sinkhorn- based entropic regularization method runs significantly more quickly than the dual method in our implementations if we insist using complementary slackness to determine the exact primal optimizer II In practice, we can quickly obtain an approximation to II from the dual solution, however (Algorithm 2). A diseussion of the dual method can be found in Section B.3.
B. ENTROPIC REGULARIZATION
Equation (2.8) an optimization problem over probability distributions. Thus, it is reasonable to regularize the objective function in Equation (2.8) with the entropy of the distribution.
Formally, detine the matrix by Ri,j E(f, (Ix,, vj)) this is the loss incurred if point j with label yj is transported to point i. Moreover, define the matrix C by C₁₁ = dZ (z,, and let denote regularization parameter. With this notation, including entropic regularization, the problem becomes:
II' arg max R, IT) > (log
(B.1)
Her
where II) (I,,).
Adding the entropy of to the objective encourages the optimizer II" to be less sparse than the (low entropy) optimizer of the original optimal transport problem. Note that it is not inherently desirable to find a sparse optimizer II", since we only consider the marginals of II" while boosting. Coming close maximizing the original objective (R, IT*) is far more important than sparsity.
16

---

Published as a conference paper at ICLR 2021
We follow the Sinkhorn method to develop solution to the problem (B.1). The Lagrangian is given by
C(I,, X, Σ
Rayll,
Σ (Tg( Mi - -, Tly - - m =m Ciglles - r) (B.2)
so that at the optimum we have
ac
Rij - Y - (ogoo(())ss)) - X3 - -n =
(B.3)
ally
which means that
IT exp( Raj (tsp//))xxxppppppp 1) Tepeeppp-CCpppp -nnCis/))
(B.4)
Now, define matrices V and K and a vector by the following expressions:
Vi = exp(R.g/n))
K exp( exp(-nnCt//1) (//))/))))))))) and
Mj = exp( - - 1).
By definition, we have that IT, = Viy Ky and that V is constant (it does not depend on any of the variables of the Lagrangian). Exploiting the constraints of the set I (see the text before (2.8)), see that u can be written in terms of K:
En IK.K K - " n K.
1
(B.5)
Thus, the solution II depends only on K. Since K is determined completely by the Lagrange multiplier 7) we need only to find the value of 7 that makes the other constraint of the set I tight:
E E
[ o K(n) & V)==e.
(B.6)
where A @ B denotes entrywise (Hadamard) product of the matrices A and B. We use a root finding algorithm to determine the optimal value of ry: specifically, we find the root of m(1) - -C @ K( ((T) @ V)u. In our experiments, the bisection or secant methods generally converge in only around to 20 evaluations of m1).
A fast method for evaluating m(1) is presented in Algorithm 4. It consists of simple entrywise matrix operations (entrywise multiplications and exponentiations): this highly amenable to processing on GPU, and we have implemented this Sinkhom-based method with TensorFlow. In Algorithm 5, provide a method for using the optimal root v/ to obtain the coupling matrix following Equation (B.4).
Algorithm 4 Fast evaluation of Sinkhorn objective
1: Input: 7) 2 0; cost matrix C: loss matrix R: tolerance e; regularization strength 7,
2: Let T f- exp(ppp R// nC//2) (entrywise exponentiation)
3: Let u (/(n1 T T) (entrywise reciprocation)
4: return 1
Algorithm 5 Find II* using entropic regularization via (B.4)
1: Input: cost matrix C:; loss matrix R:; tolerance e; regularization strength ?.
2: Let 17" be the root of Algorithm 4 with fixed inputs C, R, and 7
3: Let S + exp(2t/
1y" C/7).
4: Let u 1/(n1, S).
5: Define 1I by 11g S.juy.
6: return II
17

---

Published as a conference paper at ICLR 2021
B.2 STOCHASTIC GRADIENT DESCENT FOR FINDING 77" WITH ENTROPIC REGULARIZATION
Although the Sinkhorn-based method presented above is fast, note that is still not especially scalable, as it requires holding at least Assuming double precision floating point arithmetic, each of these matrices requires more than 10 GB of memory when is approximately
matrices (R and C) in memory at the same time.
10
Thus, following Genevay et al. (2016), we express the determination of the optimal dual variable ' as the minimization of an expectation over the empirical distribution Pn; thus, is possible to leverage stochastic gradient descent (with bini-batching) to quickly find the optimal dual variable 17 while using a small amount of memory.
To develop this expression, note that the Lagrangian dual to the problem (B.1) is given by
min max C(TT, X, m) 220
(B.7)
where C is defined in Equation (B.2). The optimal value of I1 for the inner maximum established in Equation (B.4). Using this optimal value, we that
1
log(11; (1) (Big A3- - -n((i)) -1
(B.8)
and we can use this calculate that
c(II", = 1
Σ
A3 +
n 1 En + Σ exp Σ u1
Rij - nn
1
ij
(B.9)
To minimize this with respect (which is unconstrained) we set
i (C(II' A)) 0x,
1 n [
(-~)
Σ exp
Rij
nni -1)
exp
(B.10)
7
which means that
-13 \3
1
Rij -nCis -1)
Σ exp
exp
n
7
Rij -n - 1))
2j = 7 7 log y
log
Σexp exp
Thus, substituting into (B.9), calculate that
Rig n PugssnCis -1)
C(II", X" ,) ;))== 7 + Σn nC log Σ exp
log 1 n
(B.11)
3
The value 7) 2 that minimizes (B.11) is the same as the minimizer of
min ((in) ne + 7 log Σen exp (BU. v)) 1nlh )) 920
(B.12)
?
where we ignored some constants that don't affect the minimizing value 17" and substituted in the definitions of R.j and Cij (see the paragraph at the start of Section B)
The problem B.12 amenable to minimization via stochastic gradient descent (SGD) this is presented in Algorithm 6. In every descent step of Algorithm 6, we are only working with subset of the columns of It and C. Thus, R and may be stored anywhere (or even computed on-the-fly) they do not need to be kept in RAM or sent to the GPU memory. Thus, this SGD version can be used for essentially arbitrarily large data sets. Empirically. we also observe good results from running only few gradient descent steps obtain approximation to 17" in every boosting step; this allows the SGD method to run as quickly as (or more quickly than) the normal Sinkhorn method (Algorithm 4). To find the final transport map II, we use Algorithm 5, before.
18

---

Published as a conference paper at ICLR 2021
Algorithm 6 SGD to find optimal dual variable with entropic regularization vj*
1: Input: Starting point 1)i > 0; cost matrix C; loss matrix R; tolerance regularization strength
7; batch size B, step sizes Oz > 0.
2: repeat
3: Sample indices fi.....jaa uniformly at random from ..I......
4: Let R2 < columns Ji..... jB of R. Let C. columns J1 ......... jB of C. [R,, C. R=
5: Let w/ (1) + sum all elements in column j of exp (Re ,/Cr)) (entrywise exponentiation)
6: 7 ma Tle are aryan شيك log wf (1)
}
7: until converged
B.3 DUAL OF ROBUST EMPIRICAL LOSS FUNCTION L
Although the algorithms presented in the preceding section run quickly and can handle arbitrarily large imputs, they only obtain an approximation the true optimal transport map (due the entropic regularization). Here, we present a method to quickly obtain the solution to the dual of the original linear program (2.8). We find that constructing the transport map II" from the knowledge of the dual optimum is difficult; however, there are quick methods to produce reasonable approximations to II* from the knowledge of the dual solution.
Following standard methods, the dual of the linear program (2.8) is given by:
n ΣE
inf en + a n20
(B.13)
j=1
s.t. Uj 2 Ruj - Cny for all i
Which can be simplified to:
n Σ j=1
inf En
max Rig C
(B.14)
420
Define (T) = max; Rgg - CCy and let (() = en E"= (z(1) denote the dual objective function from (4). Note that each (n) is monotone decreasing convex piecewise linear function of 1). In addition, since Cj = O, we have that lim \n(1) 2 Rys: that is, the X, are positive and eventually become constant.
This means that the infimum (over 17) will either occur at = or at one of the corners of one of the >Ú (a corner is value of 77 such that there exist i and ig, i * iz. with R,, n Righ "Cis = max; Raj CyCay; i.e. at least two the lines that define Xj are intersecting and creating point where (n) is not differentiable). Thus, it is theoretically possible exactly obtain the optimizer 17* by enumerating and testing all of these corners.
In practice, have found that it is quicker to approximate 1) by noticing that an element of the subgradient for (n)) is given by
e- E I
in arg max Rig T)Ciz.
(B.
Thus, a bisection method can be implemented to approximate the point 17* such that d M(n) < 0 for dr 7) < 17" and dr (n) for y) > 17". This is the corner that we are looking for. Using a bisection method (or similar) guarantees that we only need small fixed number (=s 30) of subgradient computations in every boosting step.
Complementary slackness can directly exploited to quickly find the desired solution IT" to the original discrete SenSR LP from the dual optimizer 1)* if the following conditions hold:
1. There is an index j such that the point 17" = arg min (() is a corner of A with arg max; Raj 1/" Gtyl = 2 (only two of the lines that define X; intersect at 1).).
19

---

Published as a conference paper at ICLR 2021
2. For all & * j, the point 17" is not comner of A (i.e. arr max, Ras Cs 1).
These conditions are based on the fact that, for all and j. Hly is the primal variable corresponding to the constraint V/ 2 R. r/Caj in the dual (B.13). Condition implies that, for all * j. there is value of t such that i n and ;
for all # t. Then, condition implies that there are only two nonzero values in column j of II.. These two nonzero values must sum to and the constraint (C, _I) must be satisfied. With the complete knowledge of the other values of II", this results in two linear equations with two unknowns (the two remaining nonzero values of IT*), and this system can be easily solved to give the exact solution IT".
Similar tricks can be applied to rapidly solve for II" when slightly more entries are candidates for being nonzero (according to complementary slackness). Unfortunately, since dg is fair distance (and thus it usually ignores several directions in 2), it is often the case that there are multiple individuals x, o x; in the training data such that (3,, x;y) 0 (i.e. there a significant number of off- dfagona entries of C' that are 0). In practice, we have observed that these points also often produce the same predicted value fx,,) fzz after the first step of boosting. This results in situation where complementary slackness presents a complicated system of equations for obtaining the primal optimizer IT".
Thus, in order to maintain efficient boosting algorithm in practice, we use the dual optimizer ") to construct approximation I't to the primal optimizer IT* using the following heuristic: for all randomly select & in arg Ra 17" Cij and let Il;; 1. That is, in each column, randomly select one of the candidate nonzero entries (according to complementary slackness) and set it to A in fI. This approximation IÍ actually is an interpretable transport map: each point in the training data is mapped (completely) to another point in the training data. We present the construction of IT using Algorithm in the main text, and we use Algorithm in our experiments on the German credit data set the Adult data set in Section 5. An outline of the full dual method (not using SGD) is presented in Algorithm 7. Although it is not exactly clear as to how good (or bad) of an approximation II is to II", our experimental results show that is functional.
Algorithm 7 Find Il using the dual formulation (following (B.15))
1: Input: cost matrix C: loss matrix R: tolerance e; root tolerance 8
2: Use the bisection method (or something similar) to find value 1) such that for all ry
sup(e 1 Σ, Ctyy iz arg max, R.y 7 } < 0 when 17 < n7"' 6
inf(e - A/2 Σ, Cigs in E arg max, Raj - C > 0 when v > 1 +
3: Obtain 11 using steps 8-13 of Algorithm 2.
4: return II
C EXPERIMENTAL DETAILS
In this section, we provide the details of the experiments using the BuDRO algorithm. We start with a synthetic motivation, then discuss the three data sets that are presented the main text.
C.I SYNTHETIC MOTIVATION
Consider a data set with two features. 21 and x2. Suppose that the one feature Ti is protected and the other feature 22 is can be used for making fair decisions. For example: our task may be to decide which individuals to approve for a loan. The protected feature I1 may correspond to the percentage of nonwhite residents in the applicant's zip code, and the other feature 22 may correspond to the applicant's 's credit score (or some other fair measure of credit worthiness). In this case, we can approximate fair metric d, by the difference in the second feature: the fair distance between the two individuals (x9, 2z)) and (af,, 2r)) is given by dz (<=f, 2g9), (2), xx)) = |= z2)l-
We synthetically constructed such data set in the following manner: 150 individuals were indepen- dently drawn from the same centered normal distribution. Let R be a rectangle of minimum area containing the 150 points; let T, be the line passing through the top right corner and the bottom left
20

---

Published as a conference paper at ICLR 2021
(a) Naive boosted classifier
(b) Fair boosted classifier
Figure I: Comparison of GBDT classifiers without (a) and with (b) the fairness constraints introduced this paper. The classifiers output a probability in [0, 1] these probabilities are discretized binary labels to create classification. In the figures, red points are individuals with true label and blue points are individuals with true label 1. The darker red areas correspond to lower output probabilities and the darker blue areas correspond to higher output probabilities. The arrows in (b) indicate the transport map corresponding to the fairness constraint for the previous boosting step.
corner of R and La be the line passing through the top left corner and the bottom right corner of R. 125 of the samples were chosen (uniformly at random) to belong to majority white neighbourhoods: these individuals were labeled if they were below L1 and if they were above L1, and then they were all shifted to the left (by 2, so that the highly white cluster is centered at (-2, 0)). The remaining 25 individuals make up the majority nonwhite cluster: they were classified according to L2 and then centered at (2, 0).
In Figure 1. we show such an example of this setup. The red points in the figure correspond to individuals that are labeled O; these represent individuals that should be declined for the loan (e.g. they have defaulted on a loan, with these data collected in the past to make future predictions). The blue points are individuals that are labeled I and represent people who should be approved (e.g. they have paid back loan in the past). The horizontal axis represents the percentage of nonwhite residents in an individual's ss zip code, while the vertical axis is taken some fair measure of credit worthiness.
The naively trained GBDT classifier in Figure ((a) shows high accuracy on this synthetic data set, but it is unfair requiring that individuals from neighbourhoods containing medium to high percentages of nonwhite individuals obtain significantly higher credit score than those in very racially homogeneous neighbourhoods. Applying our individually fair gradient boosting algorithm to the data set, however, results in fair classifier (visualized in Figure 1 (bb)). The credit score threshold for loan acceptance is consistent across the different racial make ups of zip codes. This provides synthetic visualization of the performance of the BuDRO method, and suggests that it is working as we have described.
As tangent: note that the clusters in this example are generated in symmetric manner. This is case where the unfaireess in the naively trained classifier is coming from lack of data and push for extra accuracy rather than specific inherent bias in the data.
C.2 DETAILS COMMON TO ALL EXPERIMENTAL DATA SETS
Fair metric We follow one of the methods presented (Yurochkin et al., 2020) construct fair metrics for the experimental data sets. Specifically, for given data set, we determine finite set T of protected directions in X. In a similar fashion to the synthetic example in C.I, changes in these protected directions should intuitively ignored by a fair measure. Thus, the fair metric d, is defined by projecting onto the orthogonal complement of (T) and considering the Fuclidean
21

---

Published as a conference paper at ICLR 2021
distance the projected space. In particular, let A sTan(T)) and proj(A) denote the projection onto A. Then,
de (21, = II((T - -pro((A) (x1 - x2))l22
(C.1)
The protected directions are determined in a similar fashion for each experimental data set. In particular, each data set contains (one or more) protected attributes: the indicator for each protected attribute is included in the set of protected directions'.
We additionally obtain one or more extra protected directions in the following manner. For fixed protected attribute (e.g. gender). we remove the feature from the data set and train a linear model on the edited data set to predict the removed feature g (we use logistic regression with l regularization of strength 0. when g is binary; ridge regression with cross validation is used for a non-binary feature g). Let be the normal vector to the separating hyperplane corresponding to this linear model: we include w in T,, the set of protected directions.
For example, on the Adult data set, we consider both the gender and race features as protected attributes (both features are binary, see the description in Section 5). The set 7 for Adult then contains three protected directions. Two of these protected directions are given by eg. the indicator vector of the gender r feature, and er, the indicator vector of the race feature. We obtain the third protected direction w by removing the gender feature from the data set and training logistic regression on this edited data set with targets given by the gender feature. Several of the features in the Adult data set (such as the is 1s__uubann and is is_wi_ fe categories of the velation senshinshhpp feature) are highly predictive of gender. Combined with the gender imbalance in the data set, this allows for logistic regression to be able to predict gender with nearly 80% accuracy on a (holdout) test set. We thus take to be the normal vector the separating hyperplane discovered during this logistic regression.
Note that a metric defined in this way will assign a distance of 0 between two individuals that differ only in the protected attributes (e.g. gender race) but are identical in all other features. Additionally, the difference 21 22 between two individuals is nearly parallel to one of the logistic regression directions u, then d(x11, 222 will also be small. For example, on the Adult data set, the vector (defined in the previous paragraph) exhibits comparatively high support on the is s__husband and is is_wi wi fe categories of the relationshi T1 has wife- = and T2 has husband = 1, then dy (x1, 22) will be small.
feature. Thus, if 21 and 22 are identical except that
This fair metric dz is approximation about all protected features, and only makes a heuristic approximation to reduce differences between true race and gender groups of individuals.
actual fair metric on X:: it does not capture information
Comparison methods Here we give an overview of the ML methods that we compare to BuDRO. Please refer to the included code for full information about the hyperparameter grids that we consider; see the respective data set sections for further information about training details and the optimal hyperparameter choices.
We consider three boosting methods in addition to BuDRO: baseline GBDTs, projecting, and reweiging. Our implementations of these methods all use the XGBoost framework (Chen & Guestrin, 2016). The GBDT hyperparameters that we consider are:
max_depth, the maximum depth of the decision trees used as weak learners;
lambda, an Eg regularization parameter;
min wair_weight, tree regularization parameter; and
eta, the XGBoost learning rate.
We additionally examine the effects of boosting for different numbers of steps. We always present the results of reweighing using the default XGBoost hyperparameters.
The projecting preprocessing method functions by eliminating the entire protected subspace from the data set before training a vanilla GBDT (see, for example Bower al. (2018), Yurochkin et al. (2020), Prost et al. (2019)). In particular, using the notation from the discussion of fair metrics (above), we project all of the data onto the orthogonal complement of sTa as a preprocessing step. This has
'The indicator for an attribute is vector with only one nonzero entry; that nonzero entry appears in the attribute that indicating.
22

---

Published as a conference paper at ICLR 2021
the effect that the final classifier will be completely blind to differences in the protected directions in T. Our experiments (see e.g. Table 2) show that this is not enough to produce an individually fair classifier: changes attributes that are highly correlated with elements of 'I' are still used to make classification decisions.
Reweighing is presented in Kamiran & Calders (2011). Essentially, this method functions by assigning weights to the individuals in the training data. These weights are chosen to force protected group status to appear statistically independent to the outcomes in V. Then a GBDT is trained on the reweighted data. This is inherently group fairness method (the data are weighted to match a group fairness constraint) that cannot be used when the protected attribute does not take a finite number of values. We use the default XGBoost parameters along with reweighing to generate the values that are presented in the main text.
To test if GBDT classifiers are useful on the tabular data sets that we consider here, we also train (naive) one-layer (100 unit) fully connected neural networks on all data sets. For the Adult and the COMPAS data sets, we additionally compare to the SenSR method from Yurochkin et al. (2020) and the adversarial debiasing method from Zhang et al. (2018). The SenSR method creates an individually fair neural network through stochastic gradient descent on robust loss similar to the one considered in this work. Adversarial debiasing is based on minimizing the ability to predict the protected attributes from knowledge of the final outputs of predictor, and also draws ideas from robustness in machine learning. It is constructed to provide improvements to statistical group faimess quantities rather than for the creation of an individually fair classifier.
Evaluation metrics We evaluate the ML methods with a type of individual fairness metric that we define below, also discussed Section 5 of the main text. It is not generally true that individual fairness will imply group fairness: it will depend on the group fairness constraint in question as well as the fair metric de on X. We thus also report several group fairness metries to allow for comparison with other methods in the literature; it remains future work to establish the precise conditions under which individual fairness will imply group fairness.
The specific group fairness metrics that we consider here are GAPMax and GAPRMS, as introduced in De- Arteaga al. (2019). Suppose that there are two groups of individuals, labeled by g (a protected group) and 1 (a privileged group). Then, given true outcomes Y and predicted outcomes Y, we consider a statistical fairness gap defined by
Gap, = P( = y/Y = v. =.9=0) P( =
for each possible outcome y E y. Note that large value of |Gap,l corresponds (correctly) assigning the outcome to a larger fraction of individuals belonging one of the groups than the other. For example, suppose that y = {0, 1}. with an indicating favorable outcome. Then, a large value of |Gapı/ means that our classifier is able to identify the successful individuals from one group at higher rate than is able to identify the successful individuals from the other. Thus, large values of Gap,, indicate unfair performance by the classifier at the level of groups We then define
GAPMax = max |Gap,
yEy
(C.2)
GAPRMS = |
Gap,
VEY
difficult to evaluate the individual fairness of an ML model since we only have access to an approximation to a true fair distance on X' (we cannot, for example, consider pairs of training points that are definitely close to each other). We expect that the fair metrics considered in this work are good approximations to true fair metrics; nonetheless, we still desire to evaluate the individual fairness of an ML model in a way that is agnostic to the choice of approximate fair metric. For this reason, we construct counterfactual pairs of individuals (that is, pairs of individuals that differ only in certain protected attributes) from the input data. Intuitively, these counterfactual pairs should be treated the same way by any individually fair classifier (they should be 'close" according to the true fair metric)."
Thhis is somewhat debatable. For example, does flipping gender but keeping all other attributes the same truly result in an equivalent individual of a different gender?
23

---

Published as a conference paper at ICLR 2021
We thus examine how often these counterfactual individuals assigned to the same outcome. These evaluation criteria are inspired by Garg et al. (2018), which examined changes in predicted sentiment when changing one word in sentence.
Specifically, suppose an attribute g takes values in a set V. To measure the consistency of the predictor with respect to (the "g-consistency of f"), we construct [V] copies of the test data. These copies are altered so that the value of the attribute g is constant on each copy and so that each value in V is represented in copy of the data. We then apply f to each copy of the data obtain [V] vectors of predicted outcomes ,i,,... V/ Dj E y"m The g-consistency of f is then the fraction of individuals who are assigned the same outcome in every copy of the data set. That is, it the fraction of indices i such that (91); (ú2); =... (9 v))..
C.3 GERMAN CREDIT
German credit is a data set that is commonly evaluated in the fairness literature (Dua & Graff, 2017). It contains information about 20 attributes (seven numerical, 13 categorical) from 1000 individuals; the MI. task is to label the individuals as good or bad credit risks. Several of the features, such as amount_ing sann_ii__savinngssssss and ical but have been recorded as categorical. Additionally, some of the other features, such as and
oyment, are numer-
htstt_histtttsstetee sss are categorical but could be considered to be ordered (for example, "all credits paid" is better than "past delays in payments" which is better than "account critical"). In some analyses, these ordered categorical features are converted integers; for the purposes of this analysis, features (which results in 62 features in our input data). We additionally standardize each numerical feature (that is, center by subtracting the mean and divide by the standard deviation). None of the data points are removed.
one-hot encode all of the categorical
We treat age numerical feature that we standardize) the protected attribute in the German credit data set. In order to report the group fairness metrics, we consider two protected groups: one group consists of individuals who are younger than 25, the other group consists of those who are 25 or older. This split was proposed by Kamiran & Calders (2009) to formalize the potential for age discrimination with this data set.
Fair distance For the German credit data set, we consider two protected directions, the first of which is the indicator vector ea of the age attribute. Additionally, following the framework described in C.2, we eliminate the age attribute from the data and use ridge regression to train a classifier to predict age from the other features (we use the default parameters in the RidgeCV class from the scikit-leax package, version 0. 0.21.3 (Pedregosa et al., 2011)). The second protected direction w is a normal vector to the hyperplane created by ridge regression (i.e. it is the vector of ridge regression coefficients).
Evaluation metrics As discussed above, we consider the GaPrMS and GаPmaX for binarized version of the age attribute.
For an individual faimess metric, we cannot examine an age consistency, since age is a numerical feature. German credit contains a categorical personal_statia feature that encodes some information about gender and marital status?, however. After one-hot encoding, we find that several of the personal_staae
categories are well-correlated with the age attribute according to ridge regression. Specifically, the ma vo separateeee category is positively correlated with age (the ridge regression coefficient has an average of 0.26 over our 10 train/test splits) and the male serale_marriiee wwwriedd dowwed feature is negatively correlated with age (the ridge regression coefficient has average of -0.25). Since this personal status attribute can be considered to be protected attribute, we examine a consistency measure based on this personal __sttttuu attribute as described in C.2. We refer to this consistency measure status consistency (or S-cons).
Method training and hyperparameter selection The labels of the German credit data are quite unbalanced (only 30% of the labels are 1). We thus train all ML methods to optimize the balanced
'The personal_status categories are maie maje_s ngle, ma male_marry rrwar/wie/// dowed, ma leee_ sewpee/deeeppa.eeeeeeeae fema lemmll__iine singenglle e, and female e lelleeddvvvree vovceedd///ooooooooo /etpce/dd//paaaee weparateddmmaaee /tt///arreddd.
24

---

learning rate of Published as a conference paper at ICLR 2021
accuracy. For the GBDT methods (baseline, projecting, and BuDRO), this is accomplished by setting 0.7 the ratio of zeros to ones in the labels of the the XGBoost parameter scale_ Leaaae__s_______________________ soos_weihtt to 0.3 training data. For naive (baseline) NNs, we sample each minibatch to contain equal numbers of points labelled O and labelled 1.
For both the baseline GBDT classifier and the projecting method, search over grid of GBDT hyperparameters on ten 80% train/20% test splits, and choose the set of hyperparameters that optimizes the average balanced test accuracy over those ten splits. See C.2 for the parameters that we tune and the code for the values that we consider. For BuDRO, we tune parameters by hand on one 80% train/20% split. We use the dual implementation to find the optimal transport map (without SGD, see Algorithm 7): thus the only extra hyperparameter to consider is the perturbation budget e. The data Table are collected by averaging the results obtained using the optimal hyperparameter choices across 10 new 80% train/20% test splits (the same splits for each method). The optimal hyperparameters are presented in Table 4.
Table 4: Optimal XGBoost parameters for German credit data set. For BuDRO, we also used a pertubation budget of 1.0.
Method
max _ex___pphhhh
lambda
min weinweeight
eta
steps
Baseline
10
1000
0.5
105
Projecting
4
7
2000
2
0.5
111
BuDRO
4
1.0
1/80
0.005
90
We also train a neural network on the German credit data set (see Appendix C.2 for a description of the architecture). We find that we consistently obtain high accuracy when 10-1 and run for 4100 epochs (without any & regularization).
Results Table 5 reproduces the data from the main text (averages over ten 80% train/20% test splits) including standard deviation values.
Table Results on German credit data set. We report the balanced accuracy in the second column.
These results are based on 10 splits into 80% training and 20% test data.
Age gaps
Method
BAAc
Status cons
GAPMax
GAPRMS
BuDRO
0.71520.032
0.074-0.025
0.18510.055
0.151
Baseline
0.723
0.920=0.022
0.310#0.159
0.241
Project
0.694+0.024
0.960=0.029
0.188
0.144::0.064
Baseline NN
0.687#0.031
0.826=0.028
0.234
0.179:0.093
C.4 ADULT
The Adult data set (Dua Graff, 2017) another commonly considered benchmark data set in the algorithmic fairness literature. After preprocessing and removing entries that contain missing data, we consider subset of Adult containing information about 11 demographic attributes from 45222 individuals. Each individual labelled with binary label that is if the individual makes less than $50000 per year and if the individual makes more than $50000 per year. In our preprocessing, we standardize the (five) continuous features and one-hot encode the (six) categorical features, resulting in 41 total features that we use in our analysis. These features include several attributes that could be considered protected, such as age (continuous). relat a wwwsip_sttttaoooooooooopoeepeoee status (categorical), gender (binary), and race (here consider a binary white non-white race feature). For this experiment, we choose to construct a predictor f for the labels that fair according to the gender and race attributes.
As mentioned in the main text, we exactly follow the experimental set-up as described in Yurochkin al. (2020) for the Adult data set. In particular, we do not remove the gender and race attributes from the training data. This helps to produce an adversarial analysis (how fair can the method become when it is explicitly training on gender and race).
25

---

Published as a conference paper at ICLR 2021
The fair distance on Adult is described in detail in C.2. Briefly, we consider three protected directions: Eg. the indicator for the gender attribute; cy, the indicator for the race attribute; and w, the normal vector to the separating hyperplane obtained via logistic regression trained to predict the gender attribute from the other attributes.
Fair distance
Evaluation metries As previously mentioned, consider both gender and race protected attributes on the Adult data set; thus we report GaPMax and GaPRMS for both the gender and race features separately.
We examine two types of counterfactual individual fairness metrics. The first we refer to as spouse consistency (S-cons). The S-cons is determined by creating two copies of the data: one in which every point belongs to the husband category of the relation relationship susshppsstauus feature and the other in which every point belongs to the wife category. Unlike the framework described in C.2, we do not consider all categories of the re relationshis atttnsshipsssttttti status us feature. To be concrete, two altered copies of the data are used to obtain two vectors of predicted outcomes 1/ and 8" and the S-cons is the fraction of outcomes that are the same in these two vectors. Explicitly, S-cons is calculated as Li; D."h = d² H. Intuitively, the S-cons measures how likely an individual is to be assigned to a different outcome simply from labeling themselves
wife rather than husband.
The other evaluation metric is the gender and race consistency (GR-cons), which involves four copies of the input data. Each copy is altered that the gender and r race features are constant on that copy of the data, and so that each copy has a different combination of the race and gender feature from the other three copies. We then apply the classifier to each copy of the data, produce four vectors of predicted outcomes Di E {0, 1)" , = 0, 1, 1,2.3. The GR-cons is defined as the fraction of outcomes that are the same in all of the Y/-
Method training and hyperparameter selection The labels for the Adult data set are unbalanced (only about 25% of people make more that $50000 per year) and thus all methods are again trained for balanced accuracy. For the GBDT methods (Baseline, projecting, BuDRO) this is accomplished by setting the XGBoost parameter s scale_pos_we labels of the training data. The data from the other methods (baseline NNs, SenSR, and adversarial debaising) are obtained from Yurochkin et al. (2020); see that work for further information about the method training.
to be the ratio of zeros ones in the
The baseline GBDT and projecting methods were trained optimize balanced test accuracy over a grid of hyperparameters on one 80% train/20% test seed. The optimal hyperparameters discovered in this way were then used to collect data on ten different 80% train/20% test splits: the average of the results on the test data from these new train/test splits are presented in Table 2 in the main text (see Table 7 for information about standard error). The optimal GBDT parameters are presented in Table 6.
Table 6: Optimal XGBoost parameters for the Adult data set. For BuDRO, we also used perturbation budget of 0.4. The value of min_wwwwwee www.eetthttt for BuDRO is computed relative to the size of an 80% training set, which contains 36177 individuals.
Method
max_ dee_h
lambda
min [in__eight
eta
steps
Baseline
3
0.01
0.5
0.05
816
Projecting
8
0.5
0.5
0.05
668
BuDRO
14
10-4
1/36177
0.005
180
BuDRO was implemented using the Dual SGD formulation to find the optimal transport map II as described in Algorithm 2. This involves several additional hyperparameters that we set in the following ways: an initial guess of the dual variable (set to 0.1), a batch size (set to 200), a number of SGD iterations (set to 100), momentum parameter (set to 0.9), and an SGD learning rate (set to 10 10-4). The optimal perturbation budget e was found to be 0.4. See C.4.1 for more information about the hyperparameter selection on Adult.
26

---

Published as a conference paper at ICLR 2021
C.4.1
FURTHER RESULTS
Table reproduces the results from the main text (averages over 10 80% train/20% test splits) including standard deviations. Only the data collected from GBDT methods are reproduced in Table 7; the data from other methods were obtained from Yurochkin et al. (2020). See Yurochkin al. (2020) for information about the standard error in these values.
Table 7: Results on Adult. We report the balanced accuracy in the second column.
Individual fairness
Gender gaps
Race gaps
Method
Acc
S-cons
GR-cons
GAPMax
GAPRMS
GAPMa
GAPPMS
BuDRO
81310.00S
.94410.013
.957
14610.012
.11410.013
.833 10.010
002110.07
Bascline
8844+00.033
942+0.007
.11==00088
2000+0.006
.166+00008
.09:+00013
.822=00013
Project
.787110.005
881:10.079
110.000
.079:00022
.069:100118
064410002
.050-00016
Reweigh
.784+:0.005
.833+0.010
949=0.009
.131+00021
.093++0.015
.056
.043:0.022
100
Cog dee
0.13
0.10
Gender gap
Geuder gap MAX
Roce gap RMS
Race MAX
1260
0.20
0.50
1.90
0.915
0.95
0258
0.75
6.700
0.85
8:512
rectmey
Balenssd uasumatyy
(a)
Minimize average GapRMs
(b) Mininize race GaPRMS
0.2
0.00
0175
0.70
0.75
0U5
2,500
0033
0.52
0
0.753
0.29
0,603
Belaneed
Beluoral srrteaary
(c)
Minituize gender GaPRMS
(d) Maximize S-cons
Figure 2: Faimess measures at given accuracy levels for the BuDRO method the Adult data considered over 10 train/test splits. The results from each choice of hyperparameters are averaged all train/test splits before being grouped into accuracy bins. The plotted points the ones from each bin that optimize the specified quantity ((a) average GaPRMS- (b) race GaPrMS- (c) gender GapRMS+ (d) spouse consistency). Error bars represent one standard deviation. Empirically, the gender gaps were harder to reduce than the race gaps. The S-cons in all of these pictures never drops below 94%.
We illustrate the fairness BuDRO different accuracy levels in Figures 2 and 3. The data in Figure 2 was also used to guide hyperparameter selection for the BuDRO method on the Adult data set.
Before analyzing the information in these figures, we provide a description of how they were generated. We separate the accuracy axis (horizontal) into bins of a fixed width (here, the bin size is 0.0016). We then consider ten 80% train/20% test splits of the data set, and explore a grid of hyperparameters for each of these train/test splits (see the included code for the specific hyperparameter grids that we examined). The results from each choice hyperparameters are averaged (over all ten train/test splits) and are placed in the bin containing the average accuracy: the error bars in the figures correspond to the standard error from this averaging.
In Figure 2, present four figures: each figure is obtained by determining the set of hyperparameters in each accuracy bin that optimize the average (over the 10 seeds) of a given fairness quantity (on the test set). Thus, each figure contains the data from approximately 30 hyperparameter selections (one for each bin, different for each figure). For example, in Figure 2(c), each point was obtained from the classifier constructed using the hyperparameters that minimize the gender GAPrMs in
27

---

Published as a conference paper at ICLR 2021
the corresponding accuracy bin. In similar fashion, Figure 2(a) is constructed by selecting the hyperparameters from each accuracy bin that minimize the average of the race GAPRMS and the gender GAPRMS- In all of the plots, the S-cons never drops below 94%, and the GR-cons remains similarly high; thus, we do not focus on the consistency measures here.
In the following analysis, concentrate on minimizing the gender GAPRMS (Figure 2(c)) due to the fact that the gender gaps were significantly more difficult to shrink than the race gaps in Figure In fact, seen in Table 2, the baseline classier exhibits fairly small race gaps even though is trained with knowledge of the race feature. In real-world use, however, it is not clear which faimnsss quantity a user would be required to optimize: thus, Figure 2 presents picture of the different trade-offs involved.
The BuDRO data in Table was collected from ten different (new) 80% train/20% test splits, using hyperparameters chosen by examining Figure 2(c). We were interested in finding a point with high accuracy and high spouse consistency; thus, we examined hyperparameters corresponding to the points in the accuracy range 0.81 to 0.825 and looked for patterns in these hyperparameters, We attempt this generalization to make hyperparameter selection slightly more realistic: it seems willfully ignorant to disregard all of this data when selecting hyperparameters for our final tests, and it is at least plausible that a user could find some of these generally good hyperparameters via hand-tuning. This results in the set of BuDRO hyperparameters that were presented in Table 6. See additionally the code for more details about the selected hyperparameters.
In Figures 2(a) and (c), we observe trade-off between accuracy and fairness with the BuDRO method. That is, by decreasing accuracy (which generally corresponds to increasing the perturbation parameter e), we able decrease the group fairness gaps, all a high level of S-cons. Thus. it is possible to chose parameters to produce smaller group fairness gaps (with potentially lower accuracy) the application calls for that.
DuDRO
Danno
Verdle CDD0
Vorrh cIIT
1120
Phopecing
0:33
Provetine
Grnstor RMS
Brwighin
0.2
6.9
0.85
0/5
0.22
081
0.28
1.78
0.52
0,84
Beleneed acrmncy
Balanoei nectanncy
(a)
(b)
Figure 3: The accuracy vs fairness trade-off of BuDRO when compared to other baseline boosting algorithms on the Adult data set. All lines are chosen to minimize gender GaPRMS- (a) contains comparison of the Gender gap RMS. The BuDRO line also appears in Figure 2(c). (b) contains a comparison of the S-cons. Error bars represent one standard deviation.
Figure includes comparison of the BuDRO method some other baseline boosting methods to further illustrate the trade-off between accuracy and fairness. Each point in Figure 3 is chosen to be the one from the accuracy bin that minimizes the gender GaPRMS-
This figure is constructed specifically to explore how fair we can make a classifier at given (fixed) levels of accuracy. The vanilla GBDT method always produces high accuracy classifiers (in the hyperparameter grid that we consider). This comes with large group fairness gaps that we are unable to decrease. On the other hand, the projecting method always produces good group fairness gaps, but we are unable to obtain high accuracy with this method. Finally, the reweighing method can obtain high accuracy with low fairness gaps, but it never produces an acceptable S-cons.
Figure 3 suggests that BuDRO is better method than projecting at all accuracy levels Adult: at any accuracy level, BuDRO matches the group fairness gaps produced by projecting while improving upon the (consistency of the) individual faimess metrie. Projecting always produces a classifier with small group fairness gaps. Unlike projecting, however, BuDRO can also be used to construct more accurate classifier if we are allow for slightly larger group fairness gaps. Depending on the
28

---

Published as a conference paper at ICLR 2021
requirements of the application (e.g. as defined by law other application specific fairness goals), this allows for more flexibility in the creation of individually fair and accurate classifiers.
It is also interesting to observe how the BuDRO curve in Figure 3 meets the curve for Vanilla GBDTs. Specifically, as the curves meet, the gender gap of the BuDRO method is increasing, while the gender gap of the Vanilla GBDT curve appears to be slightly decreasing. We speculate that this is due the fact that the grid of hyperparameters used in the construction of Figure 3 does not contain values of smaller that 0.1. That is, the value of does not go down O, we can not expect precisely recover the baseline results. Essentially, we force a small perturbation in the data while also pushing for high accuracy. Thus, it appears that the high accuracy points in the Figure correspond to solutions that are obtained by improving race fairesss without significantly improving gender fairness (see also Figure 2(c) the race fairness always remains small). These high accuracy cases apparently find a perturbation that is mostly along the race axis.
Overall, these figures provide further evidence that the BuDRO method creates an individually fair classifier while still obtaining high accuracy (on tabular, structured data like Adult) due to the ability to leverage powerful GBDT methods.
C.5 COMPAS
The COMPAS recidivism prediction data set, compiled by ProPublica (Larson et al., 2016), includes information on the offenders' gender, race, age, criminal history (charge_ for_arrest. number cetabbe_prior_.. www.prrrrrste wtlppprrrffeaaaaeeerreeereeeeeee offenses), and the risk_score assigned to the offender by COMPAS. ProP- ublica also collects whether or not these offenders recidivate within two years as the ground truth. More details and discussions of the data set can be found in Angwin & Larson (2016); Flores et al. (2016).
We remove the siss_score attribute, standardize the nunber cember_priorte prior_offenses attribute and one-hot encode the age attribute, yielding the final data set of 5278 individuals with 7 features.
Since there are only seven features (with only one continuous feature) in the COMPAS data, there many different pairs of individuals (i.j) with the same similarity distance Ct.-- Then, there can be lot of different solutions while finding e arg max, Appendix B.2 and Algorithm 7). Therefore. we consider the entropic regularization form (B.1) of the linear program (2.8), and solve it using the fast Sinkhorn method in Algorithm 4 and 5.
r7" Cis when using the dual method (see
Fair metric We define three protected directions: Eg. the indicator vector of gender, er, the indicator vector race, and protected direction w obtained by eliminating the race attribute and training the logistic regression for binary label race on the edited data set. Then, we follow the steps for computing the projection matrix A = span(eg: Cr, w] and calculating the fair distances dz in (C.1) for all pairs of individuals.
Evaluation metrics We evaluate the methods using several individual faimnsss metrics, as well as some group fairness metrics. For group fairness metrics, we report GAPMax and GAPRMS for race and gender separately. We consider two counterfactual individual fairness evaluation measures on COMPAS based on the two protected attributes ra ce and gender (which are both binary). Therefore, we can make the counterfactual examples by flipping the protected attributes. For example, we generate two copies of the data set: one with all individuals are female, the other with all individuals are male. Then the gender consistency (G-cons) is obtained by calculating the fraction of the same classified outcomes on two copies. The race consistency (R-cons) can be calculated in a similar way.
Method training and hyperparameter selection We compare to the same methods that were considered on Adult: baseline GBDT, projecting, and reweighing (based on XGBoost); and bascline NN, SenSR, and adversarial debiasing (based on neural networks).
The results reported are averaged over ten random training (80%) and testing (20%) splits of the data set. We implement the adversarial debiasing methods (in the adversari wttrsairrll_dbbb__aaalaallaaaeee debiesiiissseeee aas ing class from the IBM's AIF360 package, version 0. 3.2.2 (Bellamy al., 2018)) with the default hyperparameters, and combine the implementation of reweighing (in the rewe reweighin iiiiii class from AIF360 with default hyperparameters) with running XGBoost (default parameters) for 100 boosting
29

---

Published as a conference paper at ICLR 2021
steps. For the baseline GBDT and projecting, select hyperparameters by splitting 20% of the training data into a validation set and evaluating the performance on the validation set. For Baseline NN, SenSR and the BuDRO methods, manually train the hyperparameters and use the resulting hyperparameters for computing the averaged results of 10 restarts.
train/test split
We report the optimal hyperparameters for the GBDT methods in Table 8. For these methods, 1 lambda is 10-h, and min min_chhid sii__childweegghhhe_e weight is 0.1 0.1/Prain where Urain is the number of training salll__os_weiigee
samples. We set scale s_p_ee____________ _et__psssss______e whitht to for projecting and the baseline, to be the ratio of zeros to ones in the labels of the training data for BuDRO. The optimal perturbation budget for BuDRO is 0.12.
Table 8: Optimal XGBoost parameters for COMPAS data set.
Method
max depth
eta
steps
Baseline
3
x 10
1600
Projecting
7.5 x 10
2000
BuDRO
1.5 10-5
68
For the neural network based methods, the optimal hyperparameters are described below. For baseline NN: learning rate = x 10-6, number of epochs 27000. For SenSR: perturbation budget 0.01, epoch 2000, full epoch 10, full learning rate 0.0001, subspace epoch 10, subspace learning rate = 0.1.
Results
The results in Table with the associated standard deviations of BuDRO and the comparison methods are shown in Table 9.
Table 9: Results on COMPAS data set. These results are based on 10 random splits into 80% training and 20% test data.
Individual fairness
Gender
Race gaps
Method
Acc
G-cons
R-cons
GAPMax
GAPR
GaPMaw
GAPRMS
BuDRO
0.652:0.012
10.000.0000
1.0000.0000
0.124:0.0553
0.09910.037
0.14510.028
0.125=0.021
Baseline
0.677:00014
0.94410.038
0.901
0.223=00055
0.180=00044
0.25=00.066
0.215=0.046
Project
0.6711:0.02
0.873
1.00010.0000
0.189=0.040
0.150=0.030
0.230=0.043
0.185=0.033
Reweigh
0.666-10.020
0.788:00003
0.81311.047
0.245
0.207.0.046
0.092
0.069=0.019
Baseline
0.682:10.011
00:02
0,907100027
0.28220.043
0.24620.028
0:25210:555
0.228-0:047
SenSR
0.652:10.018
0.977:10.029
0.988 10.0116
0.167
0.129:0.047
0.17910.039
0.159-0.032
Adv.
0.6714-0.016
0.854+0.002
1..08--0.088
0.246-0.064
0.219+00051
0.130-00.05
0.108-0.059
C.6 METHOD TIMING INFORMATION
Table 10 contains the training runtimes of the vanilla GBDT and the BuDRO methods. The runtimes of the other fair GBDT methods (projecting and reweighing) are dominated by the time required for rumning vanilla GBDT after preprocessing; thus, the runtimes for these methods are omitted here. The results show that the BuDRO method as defined in Algorithm (i.e. using SGD find dual solution with (n²)) time required to recover the primal solution) is scalable to large problems.
Table 10: Average runtime for training, including standard deviations. The number in parentheses is the number of trials used to compute the average. In all trials, the hyperparameters (including the number of boosting steps) were examined during the generation of the data presented in Section 5. Each baseline GBDT trial ran for 1000 boosting steps on 4 CPUs. BuDRO ran for 500 steps on CPUs German credit, 200 steps using 2 CPUs on COMPAS, and 200 steps using 4 CPUs and GPU on Adult.
Problem size
Time (seconds)
Data set German credit
training samples
features
Baseline GBDT
BuDRO
800
62
6.5 4 0.3 (10)
105.0 25.5 (480)
COMPAS
4222
7
17.5 = 0.7 (10)
154.9 + 4.5 (10)
Adult
36177
41
201.6 5.4 (10)
1455.9 263.2 (6)
30


Reviews:
[{"review_id": "XTQT3njZEjs", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### POST-REVISION\n\nThanks for the revisions made to the paper, particularly for elaborating on the heuristic to speed-up the inner subroutine, and the clarification on the generalization bound.\n\nAlso thanks for the running time numbers. Would be great if you could report them in the paper (if you haven't already).\n\nI'm revising my score for the paper to 7.\n**********\n\nThe paper presents an interesting idea to train boosted decision trees to satisfy individual fairness constraints (for a pre-specified similarity metric \"d_x\"). The prior gradient-based method of Yurochkin et al. for individual fairness constraints does not apply to non-continuous (or non-smooth) models such as decision trees. The authors borrow the same distributionally robust loss setup as Yurochkin et al, where the goal is to minimize classification performance over all distributions that are close to empirical distribution, with the closeness measured in terms of the similarity metric \"d_x\" (via the optimal transport distance). However, unlike the prior method which works with the dual formulation, the authors show how one solve the primal problem directly with functional gradient descent as long as the \"supremum\" over distributions in robust loss function can be computed efficiently. They then show how the supremum can be computed using an LP. Interestingly, by directly computing the supremum, the resulting gradient boosted training does not require the model to be continuous in its inputs. The authors provide generalization bounds and experiments on three benchmark fairness datasets.\n\nPros:\n- Training individually fair models is still a nascent area of research, and so the paper makes a valuable contribution to this subarea of ML fairness.\n- The trick the authors use to accommodate non-continuous models by directly applying functional gradient descent to the distributionally robust loss function is pretty neat.\n\nCons:\n- The main concern is the scalability of the approach. Each iteration of the gradient boosted training requires solving an LP with n^2 variables, where \"n\" is the number of training points. The authors provide a solver for the LP (based on some practical tricks) which requires O(n^2) computation, but even this does not seem scalable for large problems. \n- I think the main difficulty in scaling up the proposal is having to perform operations on n x n matrices to compute the supremum (e.g. R, C, \\Pi in Alg 2). But I guess in practice, you may be able to reduce the storage costs, exploit sparsity patterns (via the proposed regularization) and avoid having to visit all the matrix entries (e.g. using the fact that you only care about examples within a minibatch while performing SGD).  Would be great if you could provide some run-time numbers for your approach for different dataset sizes.\n- The generalization bound has an exponential dependence on the dimension \"d\". The authors say this is unavoidable because of the  relaxation they introduce to the original robust loss where they replace the original dataset with an augmented dataset. How important is the use of the augmented dataset \"D_0\" to the working of the gradient boosted training (the exponential dependence on \"d\" seems like a heavy price to pay to enable this relaxation)? I understand that this was needed to ensure that you only need to compute gradients for the loss \\ell w.r.t. the scores f(x) and not w.r.t. the labels \"y\", but I wonder if there's any another way to handle the labels without worsening the generalization bound.\n\nFinally, I have one other questions about the generalization bound Thm 3.4:\n- In your proof, you seem to make use of the dual formulation for the robust loss L. But would you need the model to be continuous in its inputs for strong duality to hold? In other words, looking at proposition 1 in Sinha et al. (2018), the equality between the primal and dual objectives seem to require some form of continuity assumption on the loss \"l\" as a function of \"x\". Indeed Assumption 3.2 in your paper does assume the loss is Lipschitz continuous but wouldn't this require the model to be continuous in its inputs?\n\nOther comments/questions:\n- Sec 2.2: I thought the joint distribution was over \"D_0 × D_0\" from the previous subsection, but you mention \"D_0 x D\" here. Is \"D\" the un-augmented training distribution?\n- Convergence of functional gradient descent (Appendix A.1): I think assumption A.2 assumes that the base learners are rich enough to model a close approximation to the gradients ∇L(f). I'm not too familiar with the analysis of gradient boosted DTs, but is there an interpretation of gradient boosting where line 6 in Alg 1 is seen as a \"projection step\", so that you don't have to make a strong assumption about the base learners? In other words, can gradient boosting be seen as a form of functional gradient descent with a projection step (the only difficulty I guess is that the projection happens before the update step in line 7)\n- Proof of Theorem 3.4 in Appendix A.2: Does \"L_f\" actually mean \"L_e\"? What does the notation \\pi_i(D) denote (I might have missed this from earlier in the appendix)? \n- Typo in page 3, para 1: y_1 -> y_i?", "extra_scores": {}, "extra_text": {}}, {"review_id": "FJrkfL3HdsU", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a non-smooth method to enforce individual fairness in gradient boosting. To deal with the non-smoothness of the model, it restricts the optimal transport distance to that defined on an augmented training support set and thus reduces the search of a worst-case distribution to solving an LP problem, where an approximate solution can be found efficiently by SGD on the dual space. The authors provide convergence and generalization properties of the algorithm, and demonstrate its improvement of group and individual fairness metrics in several numerical experiments.\n\nThe paper is well established and written. The proposed method is novel and the experiment results look promising.\n\nComments and Questions:\n1. It seems that this method can be readily extended to multi-class classification problems. Does this method work with continuous output space? What would be the augmented set like?\n2. The definition of W_D above (2.4) looks confusing as it is exactly the same as W. We may want to highlight the distinction as it is defined on the augmented support set.\n3. A typo in (2.5) where there is no summation over i?\n4. The definition of R is confusing, is it just \\ell(f(x_i), y_j)?\n5. How long does it take to run BuDRO on the three experiments, and compared to other methods?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5Z289OzI2-j", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors presented in the submission a thorough study on enforcing the aggregated individual fairness with non-differentiable ML models. The proposed method generates individually fair and robust ML models in a minimax fashion among all possible samples that are close to the true distribution w.r.t. a given fair metric. They introduce the augmented support and transfer the standard gradient descent to a gradient descent in the functional space anchored by the augmented support to optimize the adversarial risk function with non-smooth ML models, e.g. decision trees. Solid theoretical guarantees and convincing empirical study results are provided to support their claims. The paper is highly completed, well-structured (though a bit dense given the page limit) and well-written - a clear accept.\n\nThe only major issue in my opinion is that the submission lacks the formal definition and discussion regarding \"individual fairness\", which is defined on the second page as \"f(x_1) \\approx f(x_2) if d_x(x_1, x_2) is small\" for a classifier \"f: X \\to {0,1}\". This \\approx is unclear under this binary classification setting, and the definition leaves me with the impression that it means two close examples by the fair metric should have similar predictions.\n\nHowever such understanding seems problematic and inaccurate throughout the rest of the paper. Decision trees are almost certain to have a value jump near the boundary of any node, therefore any quantification of the definition (e.g. I am thinking of a \\epsilon-\\delta argument that |f(x_1)-f(x_2)| < \\delta when d_x(x_1, x_2) < \\epsilon for fixed \\epsilon and \\delta) above has to deal with the case when d_x(x_1, x_2) is small but x_1 and x_2 are in two nodes in any single tree in the GBDT ensemble. Also, the restricted empirical adversarial cost function (2.4) appears more like a robust cost function that guarantees the model accuracy for all possible data generating process similar to the truth (which is the d_x part), whereas it has no reference to \"f(x_1) \\approx f(x_2)\". \n\nAfter (2.4) I feel the individual fairness in the paper might actually mean that \"two close examples by the fair metric should be equally accurate\", which seems to make more sense given the transportation between similar examples and the risk being the sole optimization target. If this is the case, it might be worth pointing it out at the beginning of the section. \n\nOther than that, it is a very smooth experience of reading the paper.  \n  \nMinor and editorial issues:\n\n1.  Though stated by the authors that \"our method readily extends to other supervised learning setting\", the theoretical discussion and the empirical study covered in the paper are both based on solving a binary classification problem. \n\n2. Assumption A.1 requires the loss $l$ is convex, while Assumption 3.2 requires $l$ to be bounded. These two points together make the loss constant unless, e.g., f(x) is uniformly bounded for all f \\in \\mathcal{F}. In such case, to achieve convergence and generalizability simultaneously, GBDTs might need to be bounded, which undermines Assumption A.2. The interaction between the assumptions seems non trivial and is worth its own discussion. \n\n3. Page 14, Proof of Theorem, \"Under Assumptions A.1(iii)-(v)\". Assumptions A.1 (iii) - (v) seem missing?\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a method to train boosted decision trees to satisfy individual fairness. All of the reviews suggest that this paper is well-written and gives novel techniques for solving an interesting problem. The authors have addressed most of the concerns raised by the reviewers during their response. However, the authors should follow a suggestion in the reviews and include the running time in the empirical evaluation.
Decision: Accept (Spotlight)