Beyond Adult and COMPAS: Fair Multi-Class Prediction via Information Projection
Authors: Wael Alghamdi
Hsiang Hsu
Haewon Jeong
Hao Wang
Peter Winston Michalak
Shahab Asoodeh
Flavio Calmon
Venue: NeurIPS 2022 Accept (2022)
Keywords: group fairness
information projection
multi-class classification
new dataset

Abstract: We consider the problem of producing fair probabilistic classifiers for multi-class classification tasks. We formulate this problem in terms of ``projecting'' a pre-trained (and potentially unfair) classifier onto the set of models that satisfy target group-fairness requirements. The new, projected model is given by post-processing the outputs of the pre-trained classifier by a multiplicative factor. We provide a parallelizable, iterative algorithm for computing the projected classifier and derive both sample complexity and convergence guarantees. Comprehensive numerical comparisons with state-of-the-art benchmarks demonstrate that our approach maintains competitive performance in terms of accuracy-fairness trade-off curves, while achieving favorable runtime on large datasets. We also evaluate our method at scale on an open dataset with multiple classes, multiple intersectional groups, and over 1M samples.

Beyond Adult and COMPAS: Fair Multi-Class Prediction via Information Projection
Wael Alghamdi', Hsiang Hsu' Haewon Jeong' Hao Wang', P. Winston Michalak Shahab Asoodch", Flavio P. Calmon' John A. Paulson School of Engineering and Applied Sciences, Harvard University 2 Department of Computing and Software, McMaster University
Abstract
We consider the problem of producing fair probabilistic classifiers for multi-class classification tasks. We formulate this problem in terms of "projecting" pre- trained (and potentially unfair) classifier onto the of models that satisfy target group-fairness requirements. The new, projected model is given by post-prcessing the outputs of the pre-trained classifier by a multiplicative factor. We provide a parallelizable, iterative algorithm for computing the projected classifier and derive both sample complexity and convergence guarantees. Comprehensive numerical comparisons with state-of-the-ar benchmarks demonstrate that our approach main- tains competitive performance in terms accuracy-faimmn -firness trade-off curves, while achieving favorable runtime large datasets. We also evaluate method scale on an open dataset with multiple classes, multiple intersectional groups, and over IM samples.
1 Introduction
Machine learning (ML) algorithms are increasingly used to automate decisions that have significant social consequences. This trend has led to surge of research on designing and evaluating fairness interventions that prevent discrimination in ML models. When dealing with group fairness, fairness interventions aim to ensure that a ML model does not discriminate against different groups determined by, for example, race, sex, and/or nationality. Extensive comparisons between discrimination control methods be found in [BDH+15 18, FSV+19, WRC21]. As these studies demonstrate, there is still no "best" fairness intervention for MI, and the majority of existing approaches are tailored to either binary classification tasks, binary population groups, both. Moreover, discrimination control methods are often tested on overused datasets of modest sizes collected in either the US or Europe (e.g.. UCI Adult [3ic13] and COMPAS [ALMK16]).
Most fairness interventions in MI. focus on binary outcomes. this case, the classification output either positive negative, and group-fairnee metrics tailored binary decisions [HPS16]. While binary classification covers range ML tasks of socictal importance (c.g., whether to approve a loan, whether to admit student), there many cases where the predicted variable is not binary. For example, in education, grading algorithms assign one out of several grades to students. In healthcare, predicted outcomes frequently not binary (e.g., severity of disease).
We introduce a theoretically grounded discrimination control method called FairProjection. This method ensures group fairness in multi-class classification for several, potentially overlapping popula- tion groups. We consider group fairness metrics that are natural multi-class extensions of their binary
"quual contribution. Correspondence to: Wael Alghamdi and Flavio Calmon (alghamdi 0g, hww.ard.ad... edu and f flaviosseas harvard. edu). See Related Work and Table I for notable exceptions.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

classification counterparts, such as statistical parity [FFM* equalized odds [HPS16], and error rate imbalance [PRW* 17, Cho17]. When restricted two predicted classes, FairProjection per- forms competitively against state-of-the-art fairness interventions tailored to binary classification model-agnostic (i.e., applicable to any model class) and scalable to datasets that are orders of magnitude larger than standard benchmarks found in the fair MI. literature.
tasks. FairProjection
Our approach is based on an information -hhoorttictt formulation called information projection. We show that this formulation is particularly well-suited for ensuring faimess in probabilistic classifiers with multi-class outputs. Given probability distribution P and a convex set of distributions P, the goal of information projection is to find the "closest" distribution to P in P. The study of information projection can be traced back to [Csi75], which used KL-divergence to measure "distance" between distributions. Since then, information projection has been extended to other divergence measures, such as f-divergences [Csi95] and Rényi divergences [KS16, KS15). Recently, [AAW+20) 20] studied how to project a probabilistic classifier, viewed as conditional distribution, onto the set of classifiers that satisfy target
requirements. Remarkably, the projected classifier is obtained by multiplying (i.e., cost-processing) the predictions of the original classifier by a factor that depends on the group-fairness constraints.
Prior work on information projection relies on a critical-and sumption: the underlying probability distributions are known exactly. This infeasible in practical ML applications, where only set of training examples sampled from the underlying data distribution available. FairProjes jection fills this gap by using an efficient algorithm for computing the pro- jected classifier with finite samples. We establish theoretical guarantees for this algorithm in terms of convergence and sample complexity.
as-
Notably, our proposed fairness intervention is parallelizable (e.g., on a GPU). Hence, FairProjection scales datasets with the number of samples comparable the population of many US states (> 10t samples). We provide a TensorFlow [AAB+ 15] implementation of FairProjection and apply it to post-process the outputs of probabilistic classifiers to ensure group fairness.
We benchmark our post-processing approach against several tfate-of-the-att faimess interventions selected based on the availability of reproducible code, and qualitatively compare it against many others. Our numerical results are among the most comprehensive comparisons of fairness interven- tions to date. We present performance results on the HSLS (High School Longitudinal Study, used in [JWC22D, Adult [Lic13], and COMPAS [ALMK16] datasets.
We also evaluate FairProjection on dataset derived from open and anonymized data from Brazil's national high school exam the Exame Nacional do Ensino Médio (ENEM)-W wwith over 1 million samples. We made use of this dataset due to the need for large-scale benchmarks for evaluating fairness interventions in multi-class classification tasks. We also answer recent calls [BZZ 21, DHMS21] ]] for moving away from overused datasets such as Adult [Lic13] and COMPAS [ALMK16] We hope that the ENEM dataset encourages researchers in the field of fair ML to test their methods within broader contexts. 3
In summary, our main contributions are: (i) We introduce post-processing faireess intervention for multi-class classification problems that can account for multiple protected groups and is scal- able to large datasets; (ii) We derive finite-sample guarantees and convergence-rate results for our post-processing method. Importantly, FairProjection makes information projection practical without requiring exact knowledge of probability distributions: (iii) We demonstrate the favourable performance of our approach through comprehensive benchmarks against state-of-the--e fairness interventions; (iv) We put forth a new large-scale dataset (ENEM) for benchmarking discrimination control methods in multi-class classification tasks; this dataset may encourage researchers in fair ML to evaluate their methods beyond Adult and COMPAS.
Related work. We summarize key differentiating factors from prior work in Table and provide a more in-depth discussion in Appendix A.2.5. The fairness interventions that the most similar to [WRC20, WRC21, FST] and the pre- pre-processing method in [JN20].
ours are the
*Since (to the best of our knowledge) the ENEM dataset has not been used in fair ML, we provide in Appendix A.3 a datasheet for the ENEM dataset. The data can be found at [INE20], and code for pre-proes preppooesssing the data and the implementation of FairProjectioon can be found at http://lihuuboom/siimaaeeeeeeeee Frajopoottti.rooocciioin....

---

Feature
Method
Multiclass
Multigroup
Scores
Curve
Parallel
Rate
Metric
Reductions [ABD 18]
(M)EO
Reject-option [KKZ122]
SP, (M)EO
EqOdds [HPS16]
EO
LevEqOpp [CDH*
X
FNR
CalEqOdds [PRW+17] 17]
MEO
FACT [KCT20]
SP, (M)EO
Identifying" [JN20]
SP, (M)EO
FST [WRC20, WRC21]
X
SP. (M)EO
Overlapping [YCK20]
SP. (M)O
Adversarial [7LMI88]
N/A
SP, (M)EO
FairProjection (ours)
SP. (M)EO
Table Comparison between benehmark methods. Multiclass/mutigrouup implementation takes datasets with mulliclass/mlligrrupp labels; Scores: processes raw outputs probabilistic classifiers; Curve: outputs
fairness-accuaacy tradeoff curves (instead of a single point); Parallel: parallel implementation (e.g.. on GPU) is available; Rate: convergence rate sample complexity guarantee is proved; Metrie: applicable fairness metric, with SPatStatistiaal Parity, EO+>qqualized Odds, MEO++Mean EO. Since FairProj ection is post- post-processin method. we focus our comparison on post-processing faimess intervention methods, except for Reductions [ABD* 18J. which is a representative in in-processing method, and Adversarial [ZLM18). which we use to henchmark multi-class prediction. For comparing in- in-processing methods, see [LPB**2] Table 1].
The FST and [JN20] can be viewed as instantiations of FairProjecttoon when restricted to the binary classification setting and to cross-entropy (for FST) or KL--diergence (for [JN20]) as the f-divergence of choice. Thus, our approach generalization of both methods multiple f- divergences. Importantly, unlike our method, [JN20] requires retraining a classifier multiple times.
reductions approach for fair classification binary classification, the benchmarks in Section indicate that the reductions approach consistently achieves the most competitive faimess-accuracy trade-off compared to ours. FairProjection has two key differences from [ABD*18) 18]: it is not restricted to binary classification tasks and does not require refitting a classifier several times over the training dataset. These are also key differentiating points from [CHKV19], which presented a meta-algorithm for fair classification that accounts for multiple constraints and groups. The reductions approach was later significantly generalized in the GroupFair method by [YCK20] to account for overlapping groups and multiple predicted classes. Unlike [YCK20], we do not require retraining classifiers.
introduced in [ABD+ 18]. When restricted to
Several other recent fairness intervention methods consider optimizing accuracy under group-fairesss constraints. In [CJG+ 19], "proxy-Lagrangínn" formulation was proposed for incorporating non- differentiable rate constraints, including group fairness constraints. We avoid non-differentiabiliy issues by considering the probabilities (scores) at the output of the classifier instead of thresholded decisions. In [ZVRGIT] 17], a fairness-come conttrsse optimization was introduced that is applicable to margin-based classifiers (our approach can be used on any probabilistic classifier). In [CDPF+ 17] and [MW18] 18], the fairness-accurae trade-offs in binary classification tasks are characterized when the underlying distributions are known. A non-parity-Bo based fairness notion was proposed in [KGZ19], called "multiaccuracy." which aims to ensure high accuracy for all subgroups even when the group information is not given in the data. We limit our analysis to parity notions of group fairness. To circumvent the con-differentiabiliyy of frirpefairness constraints, approximate fairness constraints based on functionals found information theory have been explored in [LPB+21, Rényi mutual information]. [BNBR19 19, Rényi maximal correlation), and [PQC* 19, maximum mean discrepancy]. We avoid such non-differentiabiiiy issues by casting group fairness constraints in the score domain.
'JN220] mention that their method be applied to multi-clas class classification, but their reported benchmarks are only for binary classification tasks.
$ILLM18] is an in in-processing method unlike other benchmarks in the table. It does not take a pre-trained classifier an input.
3

---

Fairness Criterion
Statistical parity
Equalized odds
Overall accuracy equality
Py Pris=o
y (c) Priv=o (c)
p( Y -= Sa P( Y)
Expression
S
Sa
Py(c')
Table 2: Standard multi-class group fairness criteria; one fixes > O and iterates over all (a, c, E [A]] CoP.
Notation. Boldface Latin letters will always refer to vectors or matrices. The entries of vector are denoted by 2j. and those of matrix G by Gt.- The all-1 and all-O vectors are denoted by 1 and O. We set [N] {1, .N3 and R_ - [0, oo). The probability simplex over [AV] is denoted by A A {p RN, 1" p 1), and A x is its (relative) interior. If P is Borel probability measure over TR Z P random variable, and : IR R&K is Borel, then the expectation of f(Z) is denoted by [Z) = Rp[s] = [p] = Ez-r]s(Z)] We use the standard asymptotic notations O, O, and Q2
Problem formulation and preliminaries
Classification tasks. The essential objects in classification are the input sample space X, the predicted classes y. and the classifiers. We fix two random variables X and Y, taking values in sets X' and y & [C]. Here, (X, Y) is a pair comprised of an input sample and corresponding class label randomly drawn from X' x Y' with distribution Рx,y. A probabilistic classifier is function h : X + Ac, where he(z) represents the probability of sample x E falling in class c E V. Thus, h gives rise to Y-valued random variable Ý via the distribution Ppxx=z(c) he(r).
Group-fairness constraints. Let S be group attribute (e.g., race and/or sex), taking val- ues in S A [A]. ness criteria in Table 2. As observed by existing works [see, e.g., ABD+18, MW18, CHKV19, WRC20, A2J+ each of these fairness constraints can be written in the vector-inequality form [G][Gh] < 0 for a closed-form matrix- function G : X - RX For in- stance, for statistical parity, the G' matrix evaluated
[[A. We consider multi-class generalization of three commonly used group fair-
fixed individual 2AC rows indexed by co) E {0,1} x [A] x [C], where the (6, a, c')-th row is equal to ((c)),
E X has K
- (a + (-1)²) ee', with e1, e.. ,ec denoting the standard basis for RC_ The expressions for the G matrix corresponding to the other fairness metrics are given in Appendix 1.1.8, with a detailed derivation of statistical parity in Appendix A.1.9. Note that G depends on x,y. If the group attribute S is part of the input feature X, then PsIx.Y simply replaced with an indicator function. Otherwise, we approximate this conditional distribution by training a probabilistic classifier.
(-1))P(()--'E
Goal. Our goal to design an efficient post-processing method that takes a pre-trained classifier base that may violate some target group-fairness criteria and finds a fair classifier that has the most similar outputs (i.e.. closest utility performance) to that of h base
Fairness through informatiion-projectoon follows. For fixed search space H C
We formulate the faimess intervention problem as
A e
(h: : X Ac }. loss function err X
A + R.
and base classifier h base
A one seeks solve:
minimize err (te, h base) subject to Epx [Gh] S
(1)
hCH
The function err quantifies the "closeness" between the scores given by h and h base The constraint on h can encode any arbitrary statistical information about the joint distribution induced on the pair (X, Y), Specifically, any constraint Exx,* (x, F)] < O, where g : X x [C]- R may be recast in the form (1). Thus, solving the optimization (1) amounts to finding the minimal necessary perturbation to the base classifier h base to make it satisfy a given on-average constraint. Since we
We remark that our framework can be applied other fairness constraints, e.g., the ones in [WRC20].

---

consider raw output scores, we measure "closeness" via f-divergences:
hasee (X) )
(x(X)
(h, h base)
DD(hhll buse
Px) a Epx
Σ cE|C)
he
base(())
base (X)f
f(1), (2)
where f is a convex function over (0, oo). By varying different choices of f. we can obtain c.g., cross-entropy (CE, ftt) log f) and KL-divergence (f(t) = t log t). For chosen f-divergence, the optimization problem (1) becomes a generalization of information projection [Csi75].
Preliminaries on information-projeccion.. In recent work 20), an optimal solution for the information projection formulation (1) was theoretically characterized. We briefly describe this result next. Let? H A (h E C(2, Ac): infe, ho(x) > 0} and we introduce the following definition and assumption.
Definition 1. For p E Ac. Dimi (..)) denote the convex conjugate of Dy(-
Deonl (v. sup oJ Dy pp)
qEác
Assumption 1. Assume that: f (B), f(1) 0, f=00=====--- and f" for all 0: (ii) each Gk.e bounded, differentiable, and has bounded gradient; (iii) h base E H. and each hasse has bounded partial derivatives; and (iv) there is an h E H such that Epx [Gh] < 0.
Now, the solution for (1) can be obtained by simple "tilting" of the base classifier's output, as stated in the next theorem.
Theorem 1 ([AAW+20J). J base and G satisfy Assumption 1, and -Rd, then there is unique solution ht for the optimization problem (1) for the I-divergence objective (2). Furthermore, opt given by the tilt
Nopt haase (x:) & (ve(2; (x; X²) + (x;xx))
(I, x (C]:
where: (1) the finction & denotes the inverse of f'; (ii) the function v X RR - RRC is defined by v(x;; 2) A -(x))>;; (iii) the function 7 : x IRK + R characterized by the equation
E hare (x) 1 (va(2; X) + 7x; A))] 1; and (iv) X E R is any solution to the convex problem D
D min AERK
E [DD
v(x:A),
base (x))
If the underlying data distribution is known, Theorem yields expression for the projected classifier as a post-process sot-processing of the base classifier. However, in practice, we do not know the underlying distribution and have to approximate it from finite number of i.id. samples. In Section 3, first describe how we approximate the solution given in Theorem with finite samples. We then propose parallelizable algorithm to solve the approximation in Section 4.
3 A finite-sample approximation of information projection
In practice, Px is unknown and only data points X Thus, we propose the following faimess optimization problem. We search for a (multi-class) classifier h X + Ac that solves the following:
{XG)eENN] C X, drawn from Px. are available.
D, (h1] ( base |Px)+ + (ExBR [[a{(X)] + [bb12)
minimize hxx-1 Ac
a.x-RR S.--R.bbE bER
(6)
subject to Ep [G. (h + m2a)] S d2b
with Px being the empirical measure (e.g., obtained from a dataset), and T1, T2 > 0 prescribed constants. The terms and b are added to cireumvent infeasibility issues and aid convergence of our
Here, C(X, Ac) denotes the complete metric space of continuous functions from X' to c. equipped with the sup- sup-norm, i.e. ||h|] é sup.e.x [[/()))]], In addition, we restrict attention to classifiers bounded away from the simplex boundary simplify the proof of strong duality in Theorem 2 (see Remark I assumptions).
5

---

numerical procedure. We show in the following theorem that there is unique solution for (6), and that it is given by a tilt (i.e., multiplicative factor) of h hase The tilting parameter is the solution of diite-dimensional strongly convex optimization problem.
Theorem 2. Suppose Assumption I holds, and set Ç - (2)() There exists a unique solution hopt.NN to (6), and is given by the formula
Nopt.N (x: = (x))e(x))) (Velx;Xe,N) + r(:; x(,))), (2, EX [C],
with v, 2, as in Theorem 1, and XO,N E RRK is the unique solution to the strongly convex problem
D2,N - min Bp [Dgau) (o(X:A), h base (x)) T 2
(8)
AER
where NN - (G(X))/V,,.. ... G(XN)/VN,Ix) ERKX(NC+R)
Proof. See Appendix A.I.I.
Theorem shows that: strong duality holds between the primal (6) and (the negative of) the dual (8);
there is a unique classifier h opt.N minimizing our fairness formulation (6); there is a unique solution A.. to the dual (5); and there is an explicit functional form of h opt.N in terms of >² in (7).
Moreover, Theorem 2 yields a practical two-step procedure for solving the functional optimization in equation (6): (i) compute the dual variables À by solving the strongly convex optimization in (8);
(ii) tilt the base classifier by using the dual variables according to (7). This process is applied on real-world datasets using FairProjection (see Algorithm 1) in the next section.
The key distinctions between our formulation and Theorem are that we use the empirical measure Px (c.g., produced using a dataset with i.i.d. samples), we have a strongly convex dual problem in (8) (in contrast the convex program in (5)), and we prove strong duality in Theorem 2 (whereas an analogous strong duality is absent from the results of [AAW*20] 20)).
Remark 1. In practice, Assumption 1 is a limiting factor for Theorem 2 and Fai FairProjects jention. This is because: we are considering here a finite-set domain so continuity is automatic; we can perturb base by negligible noise to push it away from the simplex boundary; and the uniform classifier is strictly feasible. Nevertheless, Assumption simplifies the derivation of our theoretical results.
4 Fair projection and theoretical guarantees
We introduce a parallelizable algorithm. FairProjection, that solves (6) using N i.i.d. data points. We prove that its utility converges to D* (see (5)) in the population limit and establish both sample- complexity and convergence rate guarantees. Applying SairProjectio intervention problem in (1) yields the optimal parameters in (7) for post-processing (i.e., tilting) the output of a multi-class classifier in order to satisfy target fairness constraints.
to the group-fairness
The PdirProjection algorithm uses ADMM [BPC+ 11] to solve the convex program in (8). Recall that it suffices to optimize (8) for computing (6) as proved in Theorem 2. Algorithm presents the and its detailed derivation is given in Appendix 1.1. A salient feature of FairProj PairProjection is its parallelizability. Each step that is done for i varying over [N] can be executed for each separately and in parallel. In particular, this applies to the most computationally intensive step, the u.-upd step. We discuss next how the u.-update step is carried out.
steps of FairProjection
Inner iterations. One approach to carry out the inner iteration in Algorithm that updates v, is to study the vanishing of the gradient of + Dooni (v. P,) + <||w|12 + a. v (where & = (p + c)/2 and a; E C is some vector). In the KL-divergence case, D is given by log-sum-exp function, so its gradient is given by softmax function, and equating the gradient to zero becomes a exed-point equation. We give an iterative routine to solve this fixed point equation in Appendix 1.1.3.1, whose proof of convergence is discussed in the same section. Beyond the KL-divergence case, setting the gradient to zero does not seem to be an analytically tractable problem. Nevertheless, we may reduce the vector minimization in Line 6 of Algorithm to tractable I-immensional root-finding problem, as the following result aids in showing.

---

Lemma 1. For E A c. a E R and & > 0. if satisfies Assumption 1, we have that
min VER
D + E110o12 + a sup BER
-0
min pol
9c
(dc + 9c)2
+ 0qe-
(9)
4.20
Pc.
45
cE|C]
Proof. See Appendix A.1.3.2.
We note that the u,-upe steps for both KL. and CE (provided in detail in Appendix A.1.3.3) give, byproduct, the implicitly defined function ((;; (see the statements of Theorems 1-2).
Convergence guarantees. Our proposed algorithm, FairProjection, enjoys the following con- vergence guarantees. The output after the t-th iteration X (t) converges exponentially fast to A (see (8)).
Theorem 3. Suppose Assumption holds, and that the matrix (G(Xi))eE E RXNN has full row-rank. Let X N.N and (t) be the t-th iteration outputs of FairProjection the KL-divergence
case. Then, we have the exponential decay of errors [I Xt,rll2 = --0(() and h (1) (x) h hopt,((x)
(
(1=) uniformly in X as
Proof. See Appendix A.1.5.
Remark 2.
The full-rank assumption on the matrix (G((;))iEN E RKKNN can be ensured by adding negligible noise to Further, although Theorem is shown for the KL--divegeecc,, the proof directly extends to general f-divergences satisfying Assumption (see Appendix 1. for further discussions). Finally, we show in Theorem 3 in Appendix A.1.7 that carrying 2(log N) with regularizer (N--1/2), yields a parameter X C.N that works
iterations of FairProjection well for the population problem for information projection (5); this makes MairProjection have computational runtime of O(N log N).
Benefit of parallelization. The parallelizability of FairProjection provides significant speedup. In Appendix A.2.2, we provide an ablation study comparing the speedup due to parallelization. For the ENEM dataset (discussed next section), parallelization yields 15-fold reduction in runtime. In addition to the parallel advantage of FairProjection, its inherent mathematical approach is more advantageous than gradient-based solutions. When numerically solving the dual problem (8) (or any close variant) via gradient methods, the gradient of Dronj (the convex conjugate of divergence) must be computed. However, this gradient is tractable in only very limited number of relevant instances of f-divergences. FairProjects jectiiono tackles this intractability through having its subroutines be informed by Lemma 1 and the discussion preceding it.
Algorithm FairProjection for solving (8).
1: Input: divergence f. predictions (p, (X.)e(XX))epppp) constraints (G, & G(X.)) regularizer C, ADMM penalty p. and initializers À and (wi)ie
2: Output: hopt.N (x) & hhoe <<<(<;;)))))) A) + (x; A)).
3: Q + + 2N ELENG G.G.
4: for 1,2,
do
5: a: + w. + P
E [M]
6: v. + argmin Do ( P.P p-C ||lli +
e [N]
PERO
7: + G. (w, + v.)
[E[N]
8:
argmin LT QI + q"6
kEEK
9: w: w. p (v. + G.
[N]
10: end for

---

5 Numerical benchmarks
We present empirical results and show that FairProjection has competitive performance both in terms of runtime and fairness-accuus accuracy trade-off curves compared to benchmarks most notably the reductions approach in [ABD*18 18), which requires retraining. Extensive additional benchmarks and experiment details are reported in Appendix A.2.
Setup. We consider three base classifiers (Base): gradient boosting (GBM), logistic regression (LR), and random forest (RF), implemented by Scikit-learn [PVG* For FairProjjettin (the constrained optimization in (6)).
cross-entropy (FairProjectiors on-CE) and KL-divergence [FairProjection- as the loss function". We consider two fairness constraints: mean equalized odds (MEO) and statistical parity (SP) (cf. Table 2). Particularly, to measure multi-class performance, we extend the definition of MEO as
MEO = max max (TPP) (P) (FP) (8)) (52) iEY $1
(10)
where (s) = P(P - 8), and (s) = p(L = i i,s 8). The definition of multi-class statistical parity is provided in Appendix A.2.4.2. All values reported in this section are from the test set with 70/30 train-test split. When benchmarking against methods tailored binary classification, we restrict our results both binary and S since, unlike FairProjection competing methods cannot necessarily handle multi-class predictions and multiple groups
Datasets. We evaluate FairProjection and all benchmarks on four datasets. We use two datasets in the education domain: the high-school longitudinal study (HSLS) dataset [IPH+ 11, JWC22] and novel dataset ENEM [INE20] (details in Appendix A.2.1). The ENEM dataset contains Brazilian college entrance exam scores along with student demographic information and socio-economic questionnaire answers (e.g.. if they own a computer). After pre-processing, the dataset contains ~1144 ..4 million samples with 139 features. Race was used the group attribute S, and Humanities exam score is used as the label Y. The score can be quantized into an arbitrary number of classes. For binary experiments, we quantize Y into two classes, and for multi-class, we quantize
classes. The race feature S has 5 categories, but we binarize it into White and Asian (S 1) and others (S = 0). We call the entire ENEM dataset INEM-11.4M, We also created smaller versions of the dataset with 50k samples: ENEM-50K-2C (binary classes) and ENEM-50K (5 classes). For completeness, we report results on UCI Adult [Lic13] and COMPAS [ALMK16]]
Benchmarks. For binary classification experiments, we compare our method with five existing fair learning algorithms: Reduction [ABD+ 18), reject-option classifier [KKZ12, Rejection] cqualized-odds [HPS16, EqDads], calibrated equalized-odds [PRW+ 17, CalEgOdds], and leveraging equal opportunity ICDH+19, 19, LevEqUpp]." 10 The choice of benchmarks is based on the availability of reproducible codes. For the first four baselines, we use IBM AIF360 library [BDH*18] 18]. For Reduction on and Rejection on, we vary the tolerance to achieve different operation points on the trade-off curves. As EqDåds, CalEqOdds and LevEqUpp only allow hard equality constraint on equalized odds, they each produce single point on the plot (see Fig. 1). We include the group attribute as a feature in the training set following the same benchmark procedure described in [ABD+18 18, WRC21] for consistent comparison. For multi-class classification experiments, we did not find methods that can be easily compared against FairProjection and use the multi-class extensions of mean equalized odds and statistical parity. For the sake of completeness, the codes of adversarial debiasing [ZLM18, Adversarial], and compare our method against it. Note that Reduction [ABD+18) 18] and Adversarial [ZLM18] are in-processing methods, and the rest of the benchmark algorithms are post-processing methods like FairProjection. Additional comparisons to [KCT20] are given in Appendix 1.2.4.1.
modified
There are four methods in Table we did not include the experiments: FACT [KCT20]. Identifying [JN20], FST [WRC21], and Overlapping [YCK20], as explained in Appendix 1.2.1.3.
'We focus on PairProjection-CCC and random forest here; results for FairProjection KL and other models are in Appendix A.2.
9A datasheet (see [GMV+21] for ENEM given in Appendix A.3. "hanss//gghubb.ccom/oooooottttt Fairness.
8

---

ENEM
HSLS
Adult
COMPAS
0.88
0.68
0.65
Accuracy
Acsuracy
0.72
0.84
Azcuracy
0.60
0.64
0.71
0.82
0.70
0.55
0.63
0.80
0.1
0.2
0.05
0.10
0:15
0.025
0.050
0.2 Equalized Odds
Mean Equalized Odds
Mean Equalized Odds
Mean Equalized Odds
Base EqOodd
Rejection Reduction
Cel:gDods LevEqOpp
FarProjjction
Figure 1: Fairness-accuracy trade-off comparisons between FairPro jecrioo and baselines on ENEM- S0k-2C, HSLS, Adult and COMPAS datasets. For all methods, we used random forest as a base classifier. Note that EqOdds, CalEgOdds, and LevEgOpp only produce a single accuracy -firmcs trade-off point, whereas the rest of the methods are capable of producing the accuracy accuracy-fairness fairness trade-off curves by varying the fairness budget a for the group fairness criteria listed Table smaller corresponds lefter point on the accuracy-fairness trade-off curve.
Binary classification results. We compare FairProjection with benchmarks tailored to binary classification in terms of the MEO-accuracy trade-off on the ENEM-50K-2C, HSLS, Adult, and COMPAS datasets in Fig. 1. Each point is obtained by averaging 10 runs with different train-test splits. FairPro CdirProjection jection-ctniii curves were obtained by varying values (cf. Table 2). When = 1.0, the outputs of FairProjection CE are equivalent the base classifier RF.
We observe that FairProjection performances. On ENEM-50K-2 and HSLS datasets, although EqOdds achieves the best faimess, that fairness comes at the cost of 4% accuracy drop (additively). The other four methods, on the other hand, produce comparatively good fairesss with accuracy loss of < 1%. In particular, FairProjes curProjections action-CE has the smallest accuracy drop whilst improving MEO from 0.17 to 0.04 on HSLS. CalEq0dds requires strict calibration requirements and yields inconsistent performance when these requirements are not met. On ENEM-50K 2C and HSLS, LevEqUpp achieves com- parable MEO with slight accuracy drop, and on COMPAS, LevEqOpp performs equally well as FairProjee eeejeection on CE and Reduction. Note that with high fairness constraints (i.c., small tolerance). the accuracy of Rejection deteriorates.
and Reduction have the overall best and most consistent
Multi-Class results. We illustrate how FairProjection performs on multi-class prediction using HSLS and ENEM--0K-SC. For HSLS, we divided student math performance into quartiles and generated four classes. In Figure 2. plot fairness accuracy trade-off of PairProjections with logistic regression and adversarial debiasing [ZLM18, Adversarial). As their base classifiers different (Adversarial is a GAN- method), we plot accuracy difference compared to the base classifier instead of plotting the absolute value of accuracy !| FairProjection reduces MEO significantly with very small loss in accuracy. While Adversarial ial is also able reduce MEO with negligible accuracy drop, it does not reduce the MEO as much as FairProjection We show more extensive results with multi-group and multi-class (D) = 5, |S| 5) in Appendix A.2.4.2.
Runtime comparisons. To demonstrate the scalability of FairProjection in Table 3, we record and-XL with the five benchmarks on ENEM- 10MM-114MM 1.4M-2C. -2C, which is
the runtime of FairProjection the biggest dataset we have. These experiments were run on machine with AMD Ryzen 2990WX 64- thread 32-Core CPU and NVIDIA TITAN Xp 12-GB GPU. For consistency, we used the same faimess 0.01), base classifier (GBM), and train/test split, and each number is the average
metric (MEO, of 2 repeated experiments. EqOdds, LevEqOpp, and CalEqOdds are faster than PairProjection since they are optimized to produce one trade-off point (ef. Fig. 1). Compared to baselines that produce full fairness-accuracy trade-off curves (i.e., Reduction and Rejection), FairProject.i takes 25.3
has the fastest runtime. Also, the non- non-parallel implementation of FairProjection mins paraleeaaallii attains 15x speedup (detailed results in Appendix A.2.2). We further compare
Base accuracy for FairProjection 0.336, Adversarial 0.307. Random guessing accuracy 0.2.

---

0.001
0.001
Accuracy Difference
0.000
Acpuracy Difference
0.000
-0.001
-0.001
-0.002
-0.002
Adversarial FairPrejection
Adversarial
FairPrajection
0.05
0.10
0:15
0.20
0.10
0.15
0.20
Equalized Odds
Mcan Equalized Odds
(a) HSLS.
(b) ENEM-500 50K-5C.
Figure 2: Fairess- trade-off for multi- prediction HSLS and ENEM-50K-5C. FairProjection is FairProjection-CE with LR base classifier.
Reduction
Rejection
EqOdds [HPS16]
LppEgOpp
CalEqOdds [PRW+17
FairProjection (ours)
Method
[ABD* 18]
[KKZ12]
[CDH+ 19]
CE
KL.
Runtime
223.6
16.9
5.9
7.9
5.3
11.3
11.6
Table 3: Execution time of FairProjection on the ENEM- 44-2CC compared with five baseline methods
(time shown in minutes). Methods in bold capable of producing faimess-aaccuaacy trade-off curve. Methods are italicized have uniformly superior performance. the time to fit the base classifiers. base classifiers are given, the runtime of e.g. FairProj eeettinnnnkiee -KL is 1.63 mins. The runtimes are consistent with small standard deviations across repeated experiments.
time reported here FairProjection includes
the runtime results for the binary HSLS, which the second biggest dataset, with the baselines that produce full fairness-aceo accuracy trade-off curves. The runtimes for Reduction, Rejection and PairProjection cection-EE CE are 81.1 sec, 9.73 sec and 4.50 sec respectively again, FairProjection has the fastest runtime. For theoretical comparison between the runtime of FairProjection and Reduction, see Appendix A.2.3.
Final remarks and limitations
We introduce theoretically-grounde and versatile fairness intervention method, FairProjection, and showcase its favorable performance in extensive experiments. We encourage the reader to peruse theoretical result in Appendix A.1 and extensive additional numerical benchmarks in Appendix A.2. FairProjectio enjoys a fast runtime thanks its parallelizability. We also evaluate method on the ENEM dataset (see Appendix A.3 for a detailed description of the dataset). Our benchmarks are a step forward in moving away from the overused COMPAS and UCI Adult datasets.
is able to correct bias for muliigroup/multiclss datasets, and it
We only consider frirnesa and would be interesting to try to incorporate other fairness notions (e.g., individual fairness [DHP+12) into our formulation. We assume that h base a pre-trained accurate (and potentially unfair) classifier; accuracy of h base influences the performance of the projected classifier. Finally, the performance of FFFirPrrjectto jertion inherently constrained by data availability. Performance may degrade with intersectional increases of the number of groups, the number of labels, and the number of fairness constraints.
future research direction is understanding how the
Acknowledgement
thank the anonymous referees their careful critique, which helped improve the quality paper considerably. This material is based upon work supported by the National Science Foundation under grants CAREER 1845852, 1926925, FAI 2040880, CIF 1900750, an HDSI Bias award, gift from Oracle Research, and Meta Ph.D. Fellowship.
10

---

References
[AAB*15] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané. Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015, Software available from tensorflow.org.
[AAW+20 20] Wael Alghamdi. Shahab Asoodeh, Hao Wang. Flavio Calmon, Dennis Wei, and Karthikeyan Natesan Ramamurthy. Model projection: Theory and applications to fair machine learning. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2711-2716 2020.
[ABD* 18] Alckh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wal- lach. A reductions approach to fair classification. In International Conference on Machine Learning, pages 60-69. PMLR, 2018.
[ALMK16] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. ProPub- lica, 2016.
18] Rachel KE Bellamy, Kuntal Dey, Michael Hind, Samuel C Hoffmann, Stephanie Houde, Kalapriya Kannan, Pranay Lohia, Jacquelyn Martino, Sameep Mehta, Aleksandra Mojsilovic, et al. Ai fairness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias. arXiv preprint arXiv: 1810.0194, 2018.
[BNBR19] Sina Baharlouei, Maher Nouiehed, Ahmad Beirami, and Meisam Razaviyayn. Rényi fair inference. arXiv preprint arXiv: /906. /2005, 2019.
[BCC 11] Stephen Boyd, Neal Parikh, Eric Chu, Borja Pelcato, and Jonathan Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers Found. Trends Mach. Learn., 3(1):1-122, jan 2011.
[BZZ+21] Michelle Bao, Angela Zhou, Samantha A Zottola, Brian Brubach, Sarah Desmarais, Aaron Seth Horowitz, Kristian Lum, and Suresh Venkatasubramanian. It's COM- PASlicated: The messy relationship between RAI datasets and algorithmic fairness benchmarks. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1), 2021.
[CDH 19] Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Leveraging labeled and unlabeled data for consistent fair binary classification. Advances in Neural Information Processing Systems, 32, 2019.
[CDPF+ 17] Sam Corbett-Davies, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorith- mic decision making and the cost of fairness. In Proceedings of the 23rd ACM SICKDD International Conference on Knowledge Discovery and Data Mining, pages 797-806, 2017.
[CHKV19] L Elisa Celis, Lingxiao Huang, Vijay Keswani, and Nisheeth K Vishnoi. Classification with faimess constraints: A meta-algorithm with provable guarantees. In Proceedings of the conference on fairness, accountability, and transparency, pages 319-328, 2019.
[Cho17] Alexandra Chouldechova. Fair prediction with disparate impact: study of bias in recidivism prediction instruments. Big data, 5(2):153-163, 2017.
[CJG+19 19] Andrew Cotter, Heinrich Jiang, Maya R Gupta, Serena Wang, Taman Narayan, Seungil You, and Karthik Sridharan. Optimization with non-differentiable constraints with applications to fairness, recall, churn, and other goals. J. Mach. Learn. Res., 20(172):1 59, 2019.

---

[Csi75] Imre Csiszár. I-divergence geometry of probability distributions and minimization problems. The annals of probability, pages 146-158, 1975.
[Csi95] Imre Csiszár. Generalized projections for non-negative functions. Proceedings of 1995 IEEE International Symposium on Information Theory, page 6. IEEE, 1995.
[DHMS21] Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 6478-6490. Curran Associates, Inc., 2021.
[DHP*12] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 2 214-226, 2012.
[FFM+15] Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramannia. Certifying and removing disparate impact. In proceedings the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 259-268. 2015.
[FSV 19]
Sorelle A Friedler, Carlos Scheidegger, Suresh Venkatasubramaniann Sonam Choudhary, Evan P Hamilton, and Derek Roth. A comparative study of faireess- enteaccin interven- tions in machine learning. In Proceedings of the conference on fairness, accountability, and transparency, pages 329-338, 2019.
[GMV*21] Timnit Gebru, Jamie Morgenstern, Briana Vecchione, Jennifer Wortman Vaughan, Hanna Wallach, Hal Daumé lii, and Kate Crawford. Datasheets for datasets. Communi- cations of the ACM, 64(12):86-92, 2021.
[HPS16] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29:3315-3323, 2016.
[INE20] INEP. Instituto nacional de estudos e pesquisas educaionais anísio teixeira, microdados do ENEM. abertos/mmicrodados/eeee. 2020. Accessed: 2022-05-23.
[IPH+11] Steven Ingels, Daniel Pratt, Deborah R Herget, Laura J Burns, Jill A Dever, Randolph Ottem, James E Rogers, Ying Jin, and Steve Leinwand. High school longitudinal study of 2009 (hsls: 09): Base-year data file documentation. nees 201 1-328. National Center for Education Statistics, 2011.
[JN20] Heinrich Jiang and Ofir Nachum. Identifying and correcting label bias in machine learning. In International Conference on Artificial Intelligence and Statistics, pages 702-712. PMLR, 2020.
[JCC22] Haewon Jeong, Hao Wang, and Flavio Calmon. Fairness without imputation: A decision tree approach for fair prediction with missing values. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
[KCT20] Joon Sik Kim, Jiahao Chen, and Ameet Talwalkar. FACT: A diagnostic for group fairness trade-offs. In International Conference on Machine Learning, pages 5264 5274. PMLR, 2020.
[KGZ19] Michael P Kim, Amirata Ghorbani, and James Zou. Multiaccuracy: Black-box post- processing for fairness in classification. In Proceedings of the 2019 AAAI/ACM Confer- ence on AI, Ethics, and Society, pages 247-254, 2019.
[KKZ12] F. Kamiran, A. Karim, and X. Zhang. Decision theory for discrimination-awei classifi- cation. In 2012 IEEE 12th International Conference on Data Mining, pages 924-929. Dec 2012.
[KS15] M Ashok Kumar and Rajesh Sundaresan. Minimization problems based on relative a-entropy i: Forward projection. IEEE Transactions on Information Theory, (0556333 5080, 2015.
12

---

[KS16] M Ashok Kumar and Igal Sason. Projection theorems for the Rényi divergence on a-convex sets. IEEE Transactions on Information Theory, 62(9))4924 4935, 2016.
[Lic13] M. Lichman. UCI machine learning repository, 2013.
[LPB*21] Andrew Lowy, Rakesh Pavan, Sina Baharlouei, Meisam Razaviyayn, and Ahmad Beirami. Fermi: Fair empirical risk minimization via exponential Rényi mutual infor- mation. arXiv preprint arXiv:2102.12586 2021.
[MW18] Aditya Krishna Menon and Robert C Williamson. The cost of fairness binary classification. In Conference on Fairness, Accountability and Transparency, pages 107-118, PMLR, 2018.
[PQC* 19] Flavien Prost, Hai Qian, Qiuwen Chen, Ed H Chi, Jilin Chen, and Alex Beutel. Toward better trade-off between performance and fairness with kernel-based distribution matching. arXiv preprint arXiv: 11799, 2019.
[PRW*17] 17] Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. On fairness and calibration. arXiv preprint (Xi::/709.020122 2017.
[PVG*11] 11] Fabian Pedregosa, Gaäl Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
[WRC20] Dennis Wei, Karthikeyan Natesan Ramamurthy, and Flavio P Calmon. Optimized score transformation for fair classification. In 23rd International Conference on Artificial Intelligence and Statistics, 2020.
[WRC21] Dennis Wei, Karthikeyan Natesan Ramamurthy, and Flavio P Calmon. Optimized score transformation for consistent fair classification. Journal of Machine Learning Research, 22(258):1-78, 2021.
[YCK20] Forest Yang, Mouhamadou Cisse, and Oluwasanmi Koyejo. Fairness with overlapping groups: probabilistic perspective. Advances in Neural Information Processing Systems, 33, 2020.
[ZLM18] Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell, Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on Al, Ethics, and Society, pages 335-340, 2018.
[ZVRG17] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Fairness constraints: Mechanisms for fair classification. In Artificial Intelligence and Statistics, pages 962-970, 2017.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Sections 3-4 for theoretical results, and Section for experimental results.
(b) Did you describe the limitations of your work? [Yes] See 'Final remarks and limita- tions' in Section 6, and also the end of the "Group-fairness constraints' paragraph in Section 2.
(c) Did you discuss any potential negative societal impacts of your work? [Yes) See 'Final remarks and limitations' in Section 6, e.g., lack of samples could negatively impact performance.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump- tion and Remark
(b) Did you include complete proofs of all theoretical results? [Yes] See SM.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URLJ? [Yes] See SM.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See SM and main text.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] All results employ cross validation.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See numerical results section.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] Yes, details (including licenses) are in the SM.
(c) Did you include any new assets either in the supplemental material URL? [Yes] Yes, see SM.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] Yes, only publicly and freely available code was used.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [Yes] Yes. In particular, discussion regarding the ENEM dataset is available the SM.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "yUNE5b4EFhi", "reviewer": "Reviewer_3JtH", "summary": "The authors of this paper present an approach to tabular fairness problems beyond sinlge-class classification problems. The other main contribution of this work is the use of a new tabular dataset with over one million samples on Brazil’s national high school exam. The technical approach the authors take is within the post-processing line of research in the fairness domain where they innovate with an approach to account for multiple protected groups and which is scalable to larger datasets. \n", "questions": "Question: How would the authors believe their work would accommodate notions of intersectionality? Could the authors speak to the increasing work and critical analysis of algorithmic fairness through the lens of intersectionality (https://facctconference.org/static/pdfs_2022/facct22-28.pdf, https://facctconference.org/static/pdfs_2022/facct22-49.pdf, https://facctconference.org/static/pdfs_2022/facct22-122.pdf)\n\nSuggestion: I strongly suggest the authors tone down the language of “introducing” the dataset. According to the appendix, the authors were not involved in the data collection process and they merely link to the data. Suggesting that these authors “introduced” these data is irresponsible. A more honest phrasing would be that the authors “use” the existing dataset.\n", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work. ", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The innovation in the approach and solution for this paper are very high. I believe that this work will have moderate impact in the field and will spur further research on both the dataset and the parallelizable, multi-class approach. \n2. The use of the new dataset is much appreciated both for its size and need in this community which for too long has relied on Adult and COMPAS to prove new methods. The experimentation section adequately benchmarks available algorithms against these data as well.\n3. The paper includes an extensive theoretical section and convincing experimental results as well. \n\nWeaknesses:\n1. The authors could compare to more approaches which are not post-processing style fairness algorithms. However, I don’t believe this is necessary for this paper’s acceptance as I find it to be out of scope of the acceptability of this paper. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_FtojnmG9x2", "reviewer": "Reviewer_4NMe", "summary": "This paper introduces a procedure for improving the fairness of models in the multi-class classification setting using a technique called information projection. In practice, this technique involves reweighting the outputs of a pre-trained model. The authors provide a theoretical basis for the technique and empirically evaluate on multiple multi-class benchmark datasets. Additionally, they introduce a new, larger scale dataset of Brazilian high school assessments (1M examples) that is to be released with the paper.", "questions": "The questions I list here are ones that I think, if the authors were to clarify in the text, would strengthen the paper overall. \n \nWhat kinds of fairness constraints are not expressible in the form shown on line 119? That is to say, is the work limited to the criteria in table 2, and if not, what are the limits?\n\nIn figure 1, there are multiple points for each technique? It seems from line 280-281 that this is because of varying alpha. If so, please clarify in the caption of the figure. Additionally, it would be nice to indicate which direction changing alpha corresponds to moving on the curves.\n", "limitations": "The key limitation is the expressibility of the fairness constraint as an inequality. It would be good to get more clarity on which fairness metrics satisfy this. Additionally, the technique is limited to datasets where group membership is known. It would be interesting to know from the authors if there are any worst-case guarantees that can be made if the groups are only partially known, but this is more for interest rather than a necessary component of the paper. ", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The techniques introduced are an application of the information projection technique for the purposes of improving fairness of multi-class prediction systems. This work is original in multiple senses. First, it goes beyond much of the literature just by considering the multi-class setting as opposed to the typical binary setting. It introduces a new reweighting technique that is competitive with other existing techniques while generally scaling better for large datasets. In addition to the novelty of the technique itself, I found that the focus on a more complex setting and the addition of practical considerations like the runtime of the technique distinguish this work from others. Additionally, it introduces and releases a completely new benchmark dataset for the community. \n\nQuality: While I did not verify all of the proofs in the work, the presentation is high quality and claims are rigorously justified throughout. \n\nClarity: In general, the presentation was very clear. It was easy to get lost in the math in the middle of the paper, and I suggest that the authors move some of this material into the supplemental material. In particular, some of the introductory material on pages 3 and 4 on information projection could be moved, as well as the details of the theoretical guarantees of FairProjection on page 7. This will make the paper more easily digestible, and they are not necessary for understanding the empirical results shown later. \n\nSignificance: The results shown demonstrate improvement over existing techniques, both in the scope of their applicability (some of those compared to are only applicable in the binary case) and runtime constraints. With the release of code and data, it does seem that this work would be very usable by practitioners who work in the multi-class classification setting. Additionally, the newly released dataset should allow many new papers to benchmark against a tougher problem than currently exists in the literature. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "87iVtf06iG", "reviewer": "Reviewer_5rHq", "summary": "This paper proposes a post-processing method to generate fair multi-class classification models based on the information projection technique which formulates fairness as a linear projection-based constraint. Theoretical guarantees on the uniqueness and approximation quality of the optimal solution are derived, and experimental results on real-world data sets demonstrate effectiveness of the proposed method in both binary and multi-class classification tasks. \n\n", "questions": "1. Please clarify the definition of multi-class fairness. \n\n2. Please clarify how the formulated linear projection-based constraint achieves that definition. \n\n3. Please try to enrich the experimental results for the multi-class case. \n\nI will raise my score if the above questions are adequately addressed. ", "limitations": "Yes. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength \n- Fair multi-class classification is a timely and useful topic. \n- The proposed method looks novel and has theoretical guarantees. \n- The paper is well-written in general. \n\nWeakness \n- It is not explained how \"multi-class fairness\" is defined and how the formulated linear projection-based constraint achieves that. \n- A large portion of the experimental results focus on binary classification instead of multi-class classification. \n\n\nDetailed Comments\n\nOverall it looks like an acceptable paper. The idea of using information projection to model fairness looks novel and interesting, and theoretical guarantees are derived. \n\nMy main complaint is on the missing explanations of two things: (1) the definition of multi-class fairness, (2) how the formulated linear projection-based constraint achieved that (it is not explained in the supplementary material either). Please clarify them. \n\nExperimental results look a bit weak, because a large part of them focuses on the binary case and only Figure 2 is for multi-class classification. (Same pattern in the supplementary material.) I suggest authors expand experimental results on the multi-class case to support the main contribution of this paper. \n\nAlso, there are two existing fair multi-class classifiers in Table 1. Why only one of them is being compared in experiment? \n\nFinally, it might be helpful to discuss the fairness of h_base. My understanding is Theorem 4 suggests the trained model can well approximate the most accurate model h_base (probably to the optimum degree). If h_base is far from fairness, would the trained model still be fair? Or, would there be any conflict between this approximation and the formulated constraint?   ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5WEQTHyKg12", "reviewer": "Reviewer_RebA", "summary": "The authors tackle the problem of achieving probabilistic group fairness through post-processing. They propose a method based on information projections -- projecting an unfair classifier into the set of fair classifiers, which corresponds to a simple tilting. They propose an algorithm to solve this optimization problem, and derive sample complexity and convergence guarantees. The authors show that their method achieves competitive performance-fairness tradeoffs relative to baseline methods, while having a faster runtime, on both binary and multiclass tasks.", "questions": "Please address points 1-6 from above.", "limitations": "The authors adequately address most of the limitations in Section 6. I would recommend adding a sentence about how group fairness may not be desirable in the real world because it often leads to reduced utility for all groups [1, 2]. \n\n[1] Corbett-Davies, Sam, and Sharad Goel. \"The measure and mismeasure of fairness: A critical review of fair machine learning.\" arXiv preprint arXiv:1808.00023 (2018).\n\n[2] Hu, Lily, and Yiling Chen. \"Fair classification and social welfare.\" Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency. 2020.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe idea of achieving fair classification through information projection is novel to the best of my knowledge. The proposed method is intuitive, and the authors prove many important theoretical properties. It also achieves decent empirical results with low runtime. The paper is rigorous and well-written. \n\nWeaknesses:\n1. The method proposed is targeted towards achieving the probabilistic definitions of group fairness, whereas most other work in the algorithmic fairness literature deal with the thresholded (binary) case. The authors should briefly comment on how the two are related -- are there cases where one implies the other?\n2. The authors should comment briefly about how they selected their baselines. Why were some methods from Table 1 not used in the experiments, and why were [CJG+19] and others omitted from Table 1?\n3. Theorems 2 and 3 from the paper seem to be very similar to Theorem 3 from [AAW+20]. The authors should clarify how they differ.\n4. Any performance improvements of the proposed method over [ABD+18] is quite marginal (Fig 1), though there is a significant runtime improvement. How do the convergence or sample complexity guarantees of this method compare with FairProjection? Further, does the convergence rate of FairProjection depend on the number of groups?\n5. In Table 3, I would recommend adding in standard deviations, as well as showing these results for the other datasets as well.\n6. The multiclass results (Figure 2) are not particularly convincing as there is only one dataset and one baseline method. Are there any simple baselines or additional datasets that can be included?\n7. The authors should reference [1] in their related work, and potentially benchmark against this method.\n8. I would suggest being more specific in the title about the proposed method.\n\n[1] Kim, Michael P., 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. 2019.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept