On Learning Fairness and Accuracy on Multiple Subgroups
Authors: Changjian Shui
Gezheng Xu
Qi CHEN
Jiaqi Li
Charles Ling
Tal Arbel
Boyu Wang
Christian Gagné
Venue: NeurIPS 2022 Accept (2022)
Keywords: algorithmic fairness
deep learning
social aspects of machine learning

Abstract: We propose an analysis in fair learning that preserves the utility of the data while reducing prediction disparities under the criteria of group sufficiency. We focus on the scenario where the data contains multiple or even many subgroups, each with limited number of samples. As a result, we present a principled method for learning a fair predictor for all subgroups via formulating it as a bilevel objective. Specifically, the subgroup specific predictors are learned in the lower-level through a small amount of data and the fair predictor. In the upper-level, the fair predictor is updated to be close to all subgroup specific predictors. We further prove that such a bilevel objective can effectively control the group sufficiency and generalization error. We evaluate the proposed framework on real-world datasets. Empirical evidence suggests the consistently improved fair predictions, as well as the comparable accuracy to the baselines.

On Learning Fairness and Accuracy on Multiple Subgroups
Changjian Sh.,4 Gezheng Xu Qi Chen'
Jiaqi Li
Charles X. Ling Tal Arbel Boyu Wang
Christian G
Centre for Intelligent Machines, McGill University
Mila, Quebec Al Institute
Department of Computer Science, University of Western Ontario
Institute Intelligence and Data, Université Laval
SCIAAR AI Chair
Abstract
We propose analysis in fair learning that preserves the utility of the data while reducing prediction disparities under the criteria of group sufficiency. We focus on the scenario where the data contains multiple limited number of samples. As a result, we present a principled method for learning fair predictor for all subgroups via formulating it as a bilevel objective. the lower-level, the subgroup-specific predictors are learned through small amount of data and the fair predictor. In the upper-level, the fair predictor is updated be close to all subgroup specific predictors. We further prove that such bilevel objective can effectively control the group sufficiency and generalization error. We evaluate the proposed framework real-world datasets. Empirical evidence suggests the consistently improved fair predictions, as well as the comparable accuracy to the baselines.
many subgroups, each with
Introduction
Machine learning has made rapid progress in sociotechnical systems such as automatic resume screening, video surveillance, and credit scoring for loan applications. Simultaneously. has been observed that learning algorithms exhibited biased predictions on the subgroups of population 2 For example, the algorithm denies loan application based on sensitive attributes such as gender, race, or disability, which has heightened public concerns.
To this end, fair learning is recently highlighted mitigate prediction disparities. The high-level idea is quite straightforward: adding fair constraints during the training 3 As result, fair learning principally gives rise two desiderata. On the one hand, the fair predictor should be informative to ensure accurate predictions for the data. On the other hand, the predictor is required to guarantee fairness avoid prediction disparities across subgroups. Therefore, it is crucial to understand the possibilities and then design provable approaches for achieving both informative and fair learning.
Clearly, achieving both objectives depends predefined fair notations. Consider demographic parity D as the fair criteria, which necessitates the independence between the predictor's output s(X) and the sensitive attribute (or subgourp index) A. Thus, if the sensitive attribute A and the ground-truth label Y are highly correlated, it is impossible to learn a both fair and informative predictor.
To avoid such intrinsic impossibilities, alternative fair notions have been developed. In this work. we focus on the criteria of group sufficiency [1 4 which ensures that the conditional expectation of ground-truth label (E)Y) (X),, Al) is identical across different subgroups, given the predictor's output. Notably, the risk of violating group sufficiency has arisen a number real-world scenarios.
Equua contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

E.g., in medical artificial intelligence, the machine learning algorithm is used to assess the clinic risk, and guide decisions regarding initiating medical therapy. However, [ 6 revealed a significant racial bias in such algorithms: when the algorithm predicts the same clinical risk score f(X) for white and black patients, black patients are actually at a higher risk of severe illness: [XY] A black] > (X), A = white]. The deployed algorithms have resulted in more referrals of white patients to specialty healthcare services, resulting in both spending disparities and racial bias [5].
In summary, this work aims to propose a novel principled framework for ensuring group sufficiency, as well as preserving an informative prediction with a small generalization error. In particular, we focus on one challenge scenario: the data includes multiple or even a large number of subgroups, some with only limited samples, as often occurs in the real-world. For example, datasets for the self-driving car are collected from wide range of geographical regions, each with limited number of training samples 77]. How can we ensure group sufficiency as well as accurate predictions? Specifically, our contributions are summarized as follows:
Controlling group sufficiency We adopted group sufficiency gap to measure fairness w.r.t. group sufficiency of a classifier f (Secl3), and then derive an upper bound of the group sufficiency gap (Theorem D. Under proper assumptions, the upper bound controlled by the discrepancy between the classifier f and the subgroup Bayes predictors. Namely, minimizing the upper bound also encourages an informative classifier.
Sg
Qs
S g
S2
Algorithmic contribution Motivated by the upper bound of the group sufficiency gap. we develop principled algorithm. Concretely, we adopt a randomized algorithm that produces a predictive-distributioo Q over the classifier (f ~ Q) to learn informative and fair classification. We further formulate the prob- lem as a bilevel optimization (Sec. (5.3), as shown in Fig (1) In the lever, the subgroup specific dataset S. and the fair sifiiiive-distibuttion Q are used to learn the subgroup specific distrbbioe Q., where Q is regarded as an informative prior for learning limited data within each subgroup. Theorem 5.1 formally demonstrates that under proper assumptions, the lower- level loss can effectively control the generalization error. (2) In the upper-level, the fair -iittiiveed Q is then updated to be close to all subgroup specific ceddiitive-distributiii to minimize the upper bound of the group sufficiency gap.
Figure 1: Illustration of the proposed algorithm. Consider three subgroups St, S2, S3, e.g., datasets for three different races. The proposed algorithm is then formulated as a bilevel optimiza- tion to learn an informative and fair prediciieeddistriuutio Q. In the lower-level (cyan), we learn the subgroup specific predictive- distribution Q" from dataset S. (limited samples) and the prior Q. In the upper-level (brown), Q is then updated to be as close to all of the learned subgroup spe- cific Q' as possible.
in order
Empirical justifications The proposed algorithm is applicable to the general parametric and differentiable model, where we adopt the neural network in the implementation. We evaluate the proposed algorithm on two real-world NLP datasets that have shown prediction disparities w.r.t. group sufficiency. Compared with baselines, the results indicate that group sufficiency has been consistently improved, with almost no loss of accuracy. Code is available at https: //tgttubb...//t/// com/ htt///uueeeeg//AS
2 Related Work
Algorithmic fairness Fairness has been attached great importance and widely studied in various applications, such as natural language processing [8-10] natural language generation [[H.3.. computer vision [54] and deep learning [16] Then various approaches have been proposed in algorithmic fairness. They typically add fair constraints during the training procedure, such as demographic parity or equalized odds (18 Apart from this, other fair notions are adopted such as accuracy parity [24] 25), which requires each subgroup to attain the same accuracy; small prediction variance [26 271. which ensures small prediction variations among the subgroup; or small prediction loss for all the subgroups [1) Furthermore, based on the concept of Independence (e.g. demographic parity A 1 ((X)) or conditional independence (e.g. equalized odds A 1. s(X)/y or group sufficiency A 1 YI)(X), another popular line fair learning is then naturally integrated with information theoretical framework through adding mutual information constraints such as [32 33).

---

Understanding fairness-aceuracy trade-off As for the theoretical aspect. [3] further investigated
the relation of fairness (demographic parity) and algorithmic stability. [35] formally justified the
inherent trade-off between fairness (w.r.t. demographic parity and equalized odds) and accuracy,
whereas the analysis conducted for the binary sensitive attribute with the population loss. [36
studied the fair-accuracy trade-off in the multi-task learning.
Group sufficiency The fair notion of group sufficiency has recently been highlighted in various
real-world scenarios such as health [6] and crime prediction 4 37]. Specifically, [38] demonstrated
that under proper assumptions, group sufficiency can be controlled in the unconstraint learning. However, this conclusion may not necessarily always hold in the overparameterized models with
limited samples per subgroup, where [6] [39 40 essentially revealed the prediction disparities between the different subgroups in the unconstraint learning. [41] recently studied the fair selective classification w.r.t. group sufficiency through an information theoretical framework, while the theoretical guarantee is unknown. In contrast, our proposed lower-level loss within the paper can provably control the generalization error, and the upper-level loss controls the group sufficiency gap. Besides, close notion to the group sufficiency is the probability calibration [42], which is defined as [[ = f(x) in binary classification. We will empirically show the probability calibration could be consistently improved within our framework, whereas the analysis on finite samples and its theoretical relation with group sufficiency remains still opening [3
Bi-level optimization in fairness Bi-level optimization seeks to solve problems with a hierarchical structure. Namely, two levels of optimization problems where one task is nested inside another [44 Several ideas related to bi-level optimization have been proposed in the context of fair-learning. For instance, we could design min-max optimization to learn fair representation when considering demographic parity (DP) or equalized odds (EO) 199 32 25 In this context, a representation function aims to minimize the loss caused by the discriminator in the lower-level. Simultaneously, in the upper-level, discriminator could be introduced to maximize the loss. Then fair representation could be enforced through the bi-level optimization. Besides, if the accuracy and its variants are tracked as the metrics for each subgroup 112. the bi-level objective could also be deployed in controlling the loss [55 or the prediction variance [27]. where the lower-level's goal is to minimize the loss for each subgroup and the upper-level's goal is to estimate the prediction disparities. In our paper, we theoretically justified a novel bi-level optimization perspective: controlling group sufficiency and accuracy. Simultaneously, other bi-level optimization and its relevant meta-learning algorithms could be further considered in the fair learning such as recurrent based gradient updating 466, layer-wise wise transformation [47 or implicit gradient based approach [48)
3 Preliminaries
We assume the joint random variable Y, A) follows an underlying distribution D(X, A,)), where X E X' is the input, Y E y' is the label, and the scalar discrete random variable A E AA denotes the sensitive attribute (or subgroup index). For instance, A represents gender, race, or age. We also denote [X as the conditional expectation of Y. which is essentially function of X. EA,x(=] is denoted as the expectation on the marginal distribution of D(A, X). Throughout the paper, we consider binary classification with Y' = {0, 1J. We further define the predictor as a scoring function f:X- + [0, 1] that maps the input into a real value in [0, 1]. is worth mentioning that in general f(X) & y since fXX is continuous. We then introduce group sufficiency and group sufficiency gap. Definition 3.1 (Group sufficiency
4 38 A predictor f satisfies group sufficiency with respect to the sensitive attribute A if EY [f()] (XY) A).
Intuitively, given a output score of the predictor f(X) the conditional expectation of Y is invariant across different subgroups. Namely, conditioning on the specific subgroup A = a does not provide any additional information about the conditional expectation of Y. Then we could naturally define group sufficiency gap.
Definition 3.2 (Group sufficiency gap (8)) ). The group sufficiency gap of predictor f is defined as: [[E[[| E|Y
Suf,- x |
Specifically, Suf, measures the extent of group sufficiency violation, induced by the predictor J. which is taken by the expectation over (X, A). Clearly, Suf, = 0 suggests that / satisfies groups sufficiency and vice versa. For completeness, we also discuss other popular group fairesss criteria: demographic parity and equalized odds.
3

---

Definition 3.3 (Demographic Parity (DP)), A predictor f satisfies the demographie parity with respect the sensitive attribute if:
Demographic Parity (DP), also known as statistical parity or independence rule, emphasizes that the expectation of the output score f(X) independent of A. [ further revealed that if A H Y. group sufficiency and demographic parity could not be simultaneously achieved.
Definition 3.4 (Equalized Odds (EO) [8].. A predictor f satisfies the equalized odds with respect A if: [[ = E(
Equalized odds (EO) emphasizes the conditional expectation of output f is invariant w.r.t A, given the ground truth Y. [ 37 reveal that if D A) > 0 and A / Y, group sufficiency and equalized odds can not both hold.
The analysis reveals a general incompatibility between group sufficiency and DP/EO when A J. Y, which often occurs in practice. Besides, DP/EO based criteria generally suffers the well-known fair accuracy trade-off [32]: enforcing the fair constraint degrades the prediction performance. This paper depicts that under the criteria of group sufficiency, these objectives could be both encouraged.
Upper bound of group sufficiency gap
To derive the theoretical results, we first introduce the group Bayes predictor.
Definition 4.1 (A-group Bayes predictor). The A-group Bayes predictor flayes is defined as: fA (X) E[
Bayer
The A-group Bayes predictor is associated with the underlying data distribution D(X, Y, A). Given the fixed realization X x, A a, have playees (a)) E z, A a]. which suggests the ground truth conditional data generation subgroup = a. By adopting RBaye (z)). we could derive the upper bound of group sufficiency gap w.r.t. any predictor f:
Theorem 4.1. Group sufficiency gap Suf, is upper bounded by: Suf, S Ax - - fRayerr Specifically, if A takes finite value (|AA < +20) and follows uniform distribution with D(A - a) 1/) Then the group sufficiency gap is further simplified as:
Suf
4
Σ
Exlls
Baaee A
The proof is inspired by 38
Specifically, Theorem 4.1 reveals that the upper bound of group sufficiency gap depends on the discrepancy between the predictor f and A-group Bayes predictor Bayes X). Namely, given different subgroups A the optimal predictor f ought to be closed to all the group Bayes predictors Bayes (X). Va E A.
Underlying assumption Theorem also reveals underlying assumptions w.r.t. the data generation distribution D(X, Y. A) for achieving a small group sufficiency gap. If f pBayes for each subgroup A a quite similar, then minimizing the upper bound yields small group sufficiency gap Suf,. For example, consider the extreme scenario if the A-group Bayes predictors are identical w.r.t. A, E| defined on the marginalized distribution D(X, Y). The upper bound recovers the difference between the predictor f and standard Bayes predictor. If we use probabilistic framework to approximate predictor f(X) ~ [X (i.e, training the entire dataset without any fair constraint), both group sufficiency gap and prediction error (since Bayes predictor optimal) will be small, which consistent with (38). On the contrary, if A-group Bayes predictors are completely arbitrary with high variance for A, both group sufficiency gap and prediction error are large and it would be impossible for informative prediction.
a) [X] Va A, where E [X] is the conventional Bayes predictor
5 Principled Approach
Based on the upper bound, we propose a principled approach learn the predictor that achieves both small generalization error and group sufficiency gap.

---

5.1 Upper bound in randomized algorithm
To establish the theoretical result, we consider a randomized algorithm that learns a predictive- distribution Q over scoring predictors from the data. For instance, if we consider Bayes framework, the predictor drawn from the posterior distribution f Q. the inference, the predictor's output formulated the expectation of the learned predictive-distriuutoon Q: f(X) = Exjo-(j-
In practice, it is infeasible to optimize over all the possible distributions. Then should restrict the predictive-diitribttion Q within a distribution family Q E 2 such as Gaussian distribution. We also denote Q% E Q as the optimal prediction-distribution w.r.t. A = under binary cross- entropy loss within the distribution family 2: Q argminq. eQ f.Q.. CB In generally Q + fBayes(c (xr, A = a). since the distribution family Q is only the subset all possible distributions (shown in Fig. 2 We then extend the upper bound in the randomized algorithm.
Corollary 5.1. The group sufficiency gap Suf, in randomized algorithm w.r.t learned predictive- distribution Q is upper bounded by:
2 A
Suf S
(KLQ2
/KUIUIDUVXXAA= a))
Optimization
Approximation
Where KL is the Kullback-Leibler divergence. Corollary decomposed into two terms, showing in 2
5.1
further reveals that the upper bound is
Optimization term The optimization term is the average KL divergence between the learned distribution Q and optimal predictive-distribtttin Q% for each subgroup A = Minimiz- ing the optimization term implies that the learned distribution Q will be both fair and informative for the prediction, because it aims to minimize the upper bound of the group sufficiency gap Suf, and be close to the optimal predictive-distriutie w.r.t. each = a.
D(YIX, A
Qi D(V|X,A=))
Figure 2: Illustration of optimiza- tion and approximation term. In the binary subgroup A = {a. b). the op- timization term to find Q E Q to minimize the discrepancy between (Q", Q7). The upproximation term is solely based on the distribution family Q (brown region). If the predefined Q has rich expressive power, the approximation treated small constant.
Approximation term The approximation term is the average KL divergence between the optimal distribution Q* and the underlying data generation distribution. Given the distribution family Q. is a unknown constant. Besides, the distribution family Q has rich expressive power such deep neural- network, the approximation term will small [49]. However, an extreme large distribution family Q could simultancously yield a potential overfitting on finite samples. In this paper, the neural network is adopted and the approximation term is assumed to be a small constant. Thus, controlling Suf, implies minimizing the optimization term.
5.2 Challenge in learning limited samples
In practice, we only have access to finite or even limited samples in each subgroup, rather than the underlying distribution D. We denote S, ((* , ) as the observed data w.r.t. subgroups A = which are i.i.d. samplings from the underlying distribution D(r, yl A = a). We also denote
the empirical binary cross entropy loss w.r.t A
(BCF(() m Σ i=1 [Ip log (f(f))
(1 vf) log(1 - f(x;))) Then a straight approach is to minimize the empirical term Q::
i= = argmin Bj,-e, (BCC((a))
(1)
Then Q is updated through minimizing the average KL KL-divergence: Σ. KL(Q:IIQ) from learned Q; However, this idea generally does not work in our setting, because each subgroup contains limited number of samples. Therefore, a straight minimization leads to overfitting for each subgroup and generalization error E. f~4: LBCB()) is quite large, showing in Fig.
5

---

5.3 Q as an informative prior
We have demonstrated that Q can achieve both fair and informative prediction. Therefore, we regard Q as a prior information for minimizing the loss, yielding a bilevel objective.
min Σ (l.(121))) A
(Upper-level)
QE@
s.t. Q2 q.
(FCE(fa) + XKL(Qu Va e A
(Lower-level)
Where À > 0 is the lower-level, aim to learn Qa for each E A. Different from Eq. I the loss in lower-level adds a regularization term (L(QaIIQ) as an informative prior in learning Q given a fixed predictive- distribution Q. Moreover, Theorem 5.1 formally justified that optimizing the lower-level loss is to minimize the upper bound of the generalization error. (2) the upper-level, Q is updated through minimizing the average KI. divergence between different Qa which controls the upper bound of Sufy.
The proposed loss is typical bilevel optimization. (1) In the
Theorem 5.1 (Generalization enror bound). Supposing that datasets {Sa ) with Sa [lat, yt )m are i.i.d. sampled from D(x, y|A = a), the binary cross entropy (BCE) loss is upper bounded by L, Qa E Q is any learned distribution from datuset Sa and Q E O is any distribution. Then with high probability
8 with V5 (0, 1), we have:
1 A
Σ
E janQu
Fa
BCE (Fa)
S
Σ A
E
Qa
ARGE (fa)
VIAlm
L.
Σ v /L(QQ. +
1og(1/8)
| m
(3)
Discussions The proof is inspired by PAC-Bayes theorem such as 50 52
Secpficially, Theorem
5.1] the generalization error in the lower-level is upper bounded by three terms. (a) Term (1) is
the average empirical prediction error, which corresponds to the first term in the lower-level loss. (b) Term (2) indicates the average KL-divergence between the learned subgroup distribution Qa and the
prior distribution Q, which corresponds to the second term in the lower-level loss. The combination of term (1-2) recovers the averaged lower-level loss w.r.t.
Thus optimizing the lower-level loss
could control the generalization error. (c) When the confidence 8 is fixed, term (3) will converge if
|A|m +00. Moreover, even if m (the sample size each subgroup) is quite small, sufficient large number of subgroups |A| can also ensure the convergence of term (3).
For the sake of simplicity, assumed the identical samples size in each subgroup Sa, while the theoretical result can be extended to subgroups with different samples ma.
5.4 Practical Implementations
In this section, we develop a practical learning algorithm that can be applied to wide range of differentiable and parametric models, including neural networks.
Parametric models We choose the Isotropic Gaussian distribution (with diagonal covariance matrix) as the distribution family Q, where the mean and covariance are set as d-dimensional parameter. Thus need to learn the parameter (0, or) for fair and informative Q E Q. As for the subgroup A a, we learn parameters (0.. ...) for Q Q. It is worth mentioning that the Isotropic Gaussian distribution is selected for its computational efficiency in the optimization. We can use any distribution as long as the density function is differentiable with respect to the parameters.
For the single predictor f. we use parametric neural-network models and assume f is parameterized by a d-dimensional vector Rd. denoted as fw. Then fw Q is equivalent to sampling the model parameter from the predictive-distribttion Q: w NO, σ²) = II. (O o² [i]).. Since Q is Isotropic Gaussian, each element i in the parameter w [i] follows a 1-dimensional Gaussian. Following the same line, fw. ~ Q" can be modeled analogously: w. (V.0... o² I (V. (ltl).
In Theorem 5.1 differences are the square norm of KL divergence and setting the specific hyper- parameter: À= A/m.

---

Algorithm Fair and Informative Learning for Multiple Subgroups (FAMS)
1: Input: Parameters w.r.t. distribution Q:(0, ²²), datasets {Sa), A.
2: for Sampling a subset of {Sa). where a E A' _ A do
3: #H# Solving the lower-level ####
4: Fix Q, optimizing the loss w.r.t. Qu =N(0.,,0.0 o.) through SGD for each a E A
F Fwa Qu
LBCE (f + AKL(QalIQ))
5: Obtaining the solution Qu E A'.
6: ### Solving the upper-level ###
7: Fix Qa with E A', optimizing the loss w.r.t. Q through SGD: 1 [Ar E. (L(C.11
8: Obtaining updated parameter (0, o²) in
9: end for Return: Parameter of distribution Q: (0, 2²)
As result, learning the distribution Q is equivalent to learning parameter (0, o) in the bilevel objective.
Gradient Estimation Based on the previous setting, we aim optimize the bilevel objective
to obtain the parameter of Q: (0, σ). We use stochastic gradient descent (SGD) to optimize the parameters. In the lower-level, the loss in Sec. [.3 is composed by the empirical prediction error and KL divergence term. The KL divergence has closed form that can be differentiated efficiently. Specifically, since Q and the subgroup specific Q are factorized Gaussian, the KI. divergence takes simple closed form and the gradient be easily calculated: KL(QAIIQ)
d Limi log aili T + + -(1)) -1
EBCE (fw.). the term (BCE (Fw.) non-linear for w, rendering the expectation intractable in the computation. To this end, we adopt the paraameteriiztion trick [53] [54] in computing the gradient w.r.t. the expectation term. The trick is based on describing the Gaussian distribution W. NN o²)) as first drawing (0, and then applying the deterministic function wa(O., o..) Oa + o. @ (@ is element-wise product) to approximate the sampling. Then the gradient term can be estimated as:
Re-parametrization trick As for the prediction error E QQ
(o...o.. l...) (f V(o....))EE-- (o.)) (BC (0..o.))) where the expectation can approximated by Monte-Carle sampling w.r.t. For a fixed sample c, the gradient can be computed through backpropagation. In the upper-level, the KL divergence has a closed form, thus it easy to update the parameter Q through backpropagation.
Proposed Algorithm Based on the analysis, the algorithm is shown in Algorithm. D for solving the bilevel objective in Sec. [.3 Specifically, we adopt the alternating optimization. Namely, in the lower-level, we fix Q and optimize the subgroup specific predictor Q" through SGD. Then in the upper-level, we fix the learned Q² and update Q. Since we may face many subgroups, at each training epoch, randomly sample a subset A' such that AA|| << |A] for the memory saving.
Inference In the inference, we use the Monte-Carlo method to sample the weights of the neural network from distribution NN, o²), then averaging the output w.r.t. different sampled weights approximate (xx BBja
6 Experiments
6.1 Experimental Setup
Dataset: Amazon review We adopt Amazon review dataset (55 40
which aims to predict
sentiment (classification) from the review. The datasets consist of large-scal scale users. Each user has limited number of reviews, ranging from to 400. The user is then treated subgroup, and has been observed that standard training can lead to prediction disparities in several (56) The
7

---

ERL
2.35
F5C5
F5C3
D40
B8D
0.9
Accesc
Sungrep Ind0e
MassProticee Prieeity
(a) Accuracy-Suti y
(b) Sufy on each subgroup
(c) Probability Calibration
Figure 3: Amazon Review dataset. (a) Boxplot accuracy and group sufficiency gap Suf, with 5 repeats: median, 75th percentile and minimum-manee maximuu value. (b) Group sufficiency gap subgroup ==00 a, which is the difference between
and (fX), ( a). We visualize the top-9 users' group sufficiency gap in ERM, whereas the result for all users is delegated to the Appendix. (c) Probability calibration curve over repeats with mean and standard deviation. ie (f(X), (XX)). The proposed approach demonstrated a consistently improved probability calibration.
experiment is adapted from the protocol of [40] Specifically, we convert the original review score (ranging from 1-5) to the binary label: the positive review (score 2 4) and negative review (score S. 3). We draw and then fix 200 users from the original dataset, which includes the training, validation, and test sets. In the implementation, we first adopt DistilBERT (57) to learn the embedding with dimension 768, Then we adopt fw and fww the four-layer fully connected neural network, where and w. Qa Additional experimental details are delegated to the Appendix.
Dataset: Toxic Comments We also use the toxic comment dataset 588 to predict the text com- ment being toxic or not, which has shown the significant performance degradation on specific cob-populations. Following [58], we select race as sensitive attribute, which includes Black, White, Asian and Latino & others (4 subgroups). We also follow the same setting as the original dataset [40. which has the separate training, validation, and test sets. Since toxic comments are marked by multiple annotators, we decide that the comment is toxic if marked by least half of the annotators. In the implementation, we adopt the DistilBERT 57 as the embedding with output dimension I 768, Then we also adopt fw and fw, the four-layer fully connected neural network, with the same network structure as Amazon. Additional details are delegated to the Appendix.
Baselines We compare with following baselines. (1) ERM: training a deep model without con- sidering the sensitive attribute. (2) SNN. Since we adopt randomized algorithms the paper, we additionally compare the stochastic neural network through the vanilla training from the whole dataset. Namely, find coadictive-distriiutte
Σ. Ey~qCu CRCF (f). (3) EIIL 43 proposed an IRM based approach to promote the group sufficiency. (4) FSCS 411 adopted the conditional mutual information constraint / (A,, (l)))) to promote the sufficiency. (5) DRO 24.. A ce-weighting approach assign the importance of the task. Indeed, DRO does not provably guarantee group sufficiency, while it encourages identical losses. All the experiments are repeated five times.
to minimize
Computing Suf, Since f(X) is continuous, the group sufficiency gap is calculated by splitting the output of predictor into multiple intervals [0, 1] and computing the conditional expectation within each interval, as detailed in Appendix.
6.2 Experimental Results
We visualize the results in Fig. 3 for Amazon review product and Fig. for toxic comment.
Accuracy and Fairness The accuracy and group sufficiency gap are depicted in Fig. 3(a) and Fig. 4(a) In Amazon review, the accuracy in the proposed approach has a slight decrease, compared with ERM.

---

EEL
Gne SuPoain 10
2.1%
A10
F5C3
D80
MaasProticee Preeeity
Suggrep now
(a) Accuracy-Suff
(b) Sufy on each subgroup
(c) Probability Calibration
Figure 4: Toxic dataset. (a) Boxplot accuracy and group sufficiency gap Suf, with repeats: median, 75th percentile and subgroup A o, which is the difference between E|y ff and B| (f()), A a). (c) Probability calibration over 5 repeats with mean and standard deviation. i.e probability calibration for each subgroup is delegated to Appendix.
value. (b) Group sufficiency gap on the specific
where the
While the group sufficiency gap has improved by 3.0%, showing significant improvement in the fairness. In toxic comments, the accuracy in proposed approach is nearly identical to the baseline, whereas group sufficiency gap has been significantly improved by 3.0-3.5%.
Group sufficiency gap on the specific subgroup To gain better understandings of group sufficiency gap, we visualize group sufficiency gap on specific subgroup A = a, i.e the discrepancy between the [f (conditional expectation on the entire data) and f expectation subgroup A a). Lee Ex [[E[(]S(X)] E[Y]S(X),
al (conditional
a]l]-
In Amazon review dataset, visualize the top-9 users' sufficiency gap in ERM, shown in Fig. 3(b) where the gap of entire users delegated to the Appendix. The proposed approach significantly reduces the group sufficiency gap of in most subgroups. The similar trend also observed in Toxic dataset, as shown in Fig. 44b) where the proposed approach has the nearly identical and small group sufficiency gap for each race. contrast, the baselines exhibit significant group sufficiency bias on the Asian and Latino & other races.
Probability Calibration A related concept to group sufficiency is the probability calibration [42], which is defined as [[[]J(() = (X) in the binary classification. We visualize the probability sufficiency of Amazon review in Fig. 3(c) and Toxic comments in Fig. [{c] The results suggest that the proposed approach demonstrates consistently better probability calibration on the whole data. We then visualize the probability calibration for each subgroup, as shown the Appendix, where the results reveal the improved probability calibration for each subgroup.
400
Figure 5: Analysis. Accuracy-Suff curve under different À in Amazon review dataset.
Other sensitive attributes in Toxic comments Apart from adopting race as sensitive attribute, we also consider other possible sensitive attributes such gender and religion, and the results are showed in the Appendix. The results in other sensitive attributes are similar to race, with improved fairness and loss on accuracy.
Influence X. Fairness and accuracy can be simultaneously achieved. Theorem 5.1 suggests that there exists optimal À in the generalization error bound. Then changed the value of À in Amazon dataset, as shown in Fig. 5
When À - 0, the subgroup specific parameters are simply learned from the limited samples within each subgroup. Then the fair predictor could not learn proper prior from the subgroup specific predictor with significant generalization error. Mcanwhile, the group sufficiency gap is also large,

---

which is consistent with [3 overfitting generally degrades the group sufficiency. When À is set between [0.2, 1]. the generalization enror is small (with high accuracy) and group sufficiency gap kept small, implying that both fairness and accuracy can be achieved. In contrast, if we set large value for À O, the predictor unable to learn from the data but from the random prior Q. The prediction will be completely random (accuracy = 55% when À 50). When the predictor outputs random guess, different from demographic parity (DP) or equalized odds (EO), the group sufficiency gap is also large. The analysis reveals that there exists an optimal for simultaneously achieving accuracy and group sufficiency.
7 Conclusion
We conducted a novel analysis by simultaneously learning informative and fair classifier for multiple or even many subgroups. We derived a novel principled algorithm. We further theoretically justified the generalization error and fair guarantees the proposed framework. The empirical results in two real-world datasets demonstrated the effectiveness in both preserving the accuracy, as well as group sufficiency.
Discussion on Limitations
We proposed the analysis on learning group sufficiency and informative predictors, and developed a principled approach for it. Simultancously there are several limitations to the proposed theory and algorithm. (1) In general, group sufficiency and DP/EO incompatible. Controlling group sufficiency, for example, would cause DP/EO degradation. This would be problematic if DP/EO were preferred in practice.
(2) We also assumed that the ground truth A-Bayes predictors would be similar across groups. However, this assumption could be violated, resulting in a highly non-trivial scenario. Thus, in order evaluate the conditional distribution shift, need consider new setting by collect sufficient data per subgroup.
Acknowledgments and Disclosure of Financial Support
We appreciate constructive feedback from anonymous reviewers and meta-reviewers. We also would like to thank Jun Xiao for the discussion and proof-reading the manuscript. C. Shui and C. Gagné acknowledge support from NSERC-Canada and the Canada CIFAR Chairs in AI. G. Xu, J. Li, C. Ling and B. Wang supported by Natural Sciences and Engineering Research Council of Canada (NSERC), Discovery Grants program. T. Arbel is supported by International Progressive Multiple Sclerosis Alliance, the Canada Institute for Advanced Research (CIFAR) Artificial Intelligence Chairs program, the Natural Sciences and Engineering Research Council Canada. Q. Chen is supported by China Scholarship Council.
References
[1] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. fairml- book.org, 2019.
org
[2] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing faimesss gerryman- dering: Auditing and learning for subgroup fairness. International Conference on Machine Learning, pages 2564-2572. PMLR, 2018.
[3] Michele Donini, Luca Oneto, Shai Ben-David John Shawe-Taylor, and Massimiliano Pontil. Empirical risk minimization under fairness constraints. arXiv preprint arXiv:1802.0886 2018
[4] Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5(2):153-163, 2017.
[5] Darshali A. Vyas, Leo G. Eisenstein, and David Jones. Hidden plain sight reconsidering the use of race correction in clinical algorithms. New England Journal of Medicine, 383 (9),874-882, 2020. doi: 10. 1..1056////MMm20047700 URL. https://ddot http::://oi..oo////// oro//0..10050 NE.JMms2004740
10

---

[6] Ziad Obermeyer, Brian Powers, Christine Vogeli, and Sendhil Mullainathan. Dissecting racial bias in an algorithm used manage the health of populations. Science, 366(6464):447- 453, 2019. doi: 10.1 126/scienne..ax22442 URL httphtts:/// /twttps://ww..... wttp:://wwwwss.nneeeeeeeeeee science wttpe/////////////oooo///
1126/science.o .ax233 aax2342
[7] Frank van Praat, So, here's the problem with self-driving cars. 2020.
[8] Shivashankar Subramanian, Afshin Rahimi, Timothy Baldwin, Trevor Cohn, and Lea Frermann. Fairness-aware class imbalanced learning. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 2045-2051, 2021. doi: 10. 10.18653/v1/20211 emnlp-main. 155.. URL
155
[9] Ilias Chalkidis, Tommaso Pasini, Sheng Zhang, Letizia Tomada, Sebastian Felix Schwemer, and Anders Søgaard. Fairlex: A multilingual benchmark for evaluating fairness in legal text processing. CoRR, abs/2203.07228, 2022.
[10] Andrew Gaut, Tony Sun, Shirlyn Tang, Yuxin Huang, Jing Qian, Mai ElSherief, Jieyu Zhao, Diba Mirza, Elizabeth Belding, Kai-Wei Chang, and William Yang Wang. Towards understanding gender bias in relation extraction. In Proceedings of the 58th Anmual Meeting of the Association for Computational Linguistics, pages 2943-2953 Online, 2020. Association for Computational Linguistics.
[11] Emily Sheng, Kai-Wei Chang, Prem Natarajan, and Nanyun Peng. Societal biases in language generation: Progress and challenges. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli, editors, Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, ACL/JJCNLP 2021, (Volume 1: Long Papers), Virtual Event, August 1-6, 2021, I, pages 4275- 4293. Association for Computational Linguistics, 2021.
[12] Umang Gupta, Jwala Dhamala, Varun Kumar, Apury Verma, Yada Pruksachatkun, Satyapriya Krishna, Rahul Gupta, Kai-Wei Chang, Greg Ver Steeg, and Aram Galstyan. Mitigating gender bias in distilled language models via counterfactual role reversal. arXiv preprint MrXiv:2203.12574 2022.
[13] Danielle Saunders, Rosie Sallis, and Bill Byme. First the worst: Finding better gender transla- tions during beam search. CoRR, abs/2104.07429, 2021.
[14] Sangwon Jung, Donggyu Lee, Taeeon Park, and Taesup Moon, Fair feature distillation for visual recognition. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19.25, 2021, pages 2021.
Computer Vision Foundation IEEE,
[15) Zhiheng Li and Chenliang Xu. Discover the unknown biased attribute of an image classifier. In 2021 IEEE/CVF International Conference on Computer Vision, ICCV 2021, Montreal, QC, Canada. October 10-17, 2021. pages 14950-14959, IEEE, 2021. doi: 10. 109/ICCC48922.. 2021.01470. URL https: /oii org 10. 1109/ 1109/ 2021 01470
[16] Dora Zhao, Angelina Wang, and Olga Russakovsky, Understanding and evaluating racial biases in image captioning. In 202/ IEEF/CVF International Conference Computer Vision, ICCV 2021, Montreal, QC, Canada, October 10-17, 2021, pages 14810- 44810-14820. IEFF, 2021.
[17] Xuan-Son Vu, Thanh Nguyen, Duc- Duc-Trong Le, and Lili Jiang. Multimodal review generation with privacy and fairness awareness. In Donia Scott, Núria Bel, and Chengqing Zong, editors, Proceedings of the 28th International Conference on Computational Linguistics, COLING 2020, Barcelona, Spain (Online), December 8-13, 2020, pages 425. International Committee on Computational Linguisties, 2020.
[18] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29:3315-3323, 2016.
[19] Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork, Learning fair representa- tions. In International conference machine learning, pages 325-333. PMLR, 2013.

---

[20] Sahil Verma and Julia Rubin. Fairness definitions explained. In 2018 ieee/acm international workshop on software fairness (fairware), pages 1-7. IEEE, 2018.
[21] Ray Jiang, Aldo Pacchiano, Tom Stepleton, Heinrich Jiang, and Silvia Chiappa. Wasserstein fair classification. In Uncertainty in Artificial Intelligence, pages 862-872. PMLR, 2020.
[22] Michael Feldman. Computational fairness: Preventing machine-learned discrimination. PhD) thesis, 2015.
[23] Flavio P Calmon, Dennis Wei, Bhamukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney, Optimized pre-processing for discrimination prevention. In Proceedings of the 31st International Conference on Neural Information Prooonororooo Processing Systems, pages 3995-4004, 2017.
[24] Shiori Sagawa*, Pang Wei Koh*, Tatsunori B. Hashimoto, and Percy Liang. Distributionally robust neural networks. In International Conference on Learning Representations, 2020. URL httpp://openreeves: mett/forummddrryyuuuuua
[25] Han Zhao, Amanda Coston, Tameem Adel, and Geoffrey J Gordon. Conditional learning of fair representations. arXiv preprint arXiv: / /9/0.07 162, 2019.
[26] Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning, arXiv preprint 1rXiv:1905.104440 2019.
[27] Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pages 6357-6368. PMLR, 2021.
[28] Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographics in repeated loss minimization. In International Conference on Machine Learning, pages 1929-19388 PMLR, 2018.
[29] Natalia Martinez, Martin Bertran, and Guillermo Sapiro. Fairness with minimal harm: A pareto-optimal approach for healthcare. arXiv preprint arXiv:1911.06935, 2019.
[30] Ananth Balashankar, Alyssa Lees, Chris Welty, and Lakshminarayanan Subramanian. What fair? exploring pareto-efficiency for fairness constrained classifiers. arXiv preprint arXiv: 1910. /4/20, 2019.
[31] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez and Krishna P Gummadi. Fairness constraints: A flexible approach for fair classification. The Journal of Machine Learning Research, 20(1):2737-2778, 2019.
[32] Jiaming Song, Pratyusha Kalluri, Aditya Grover, Shengjia Zhao, and Stefano Ermon. Learning controllable fair representations. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2164-2173. PMLR, 2019.
[33] David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In International Conference on Machine Learning, pages 3384 3384-3393. PMLR, 2018
[34] Lingxiao Huang and Nisheeth Vishnoi. Stable and fair classification. In International Conference on Machine Learning, pages 2879-2890. PMLR, 2019.
[35] Sanghamitra Dutta, Dennis Wei, Hazar Yueksel, Pin-Y Yu Chen, Sijia Liu, and Kush Varshney. Is there a trade-off between fairness and accuracy? a perspective using mismatched hypothesis testing. In International Conference Machine Learning, pages 1803-28133 PMLR, 2020.
[36] Yuyan Wang, Xuezhi Wang, Alex Beutel, Flavien Prost, Jilin Chen, and Ed H Chi. Under- standing and improving fairness-accurac trade-off's in multi-task learning. arXiv preprint arXiv:2106.00 02705. 2021.
[37] Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. On fairness and calibration. arXiv preprint 1rXiv:1709.020111 2017.
12

---

[38] Lydia T. Liu, Max Simchowitz, and Moritz Hardt. The implicit faimesss criterion of un- constrained learning. Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceed- ings of the 36th International Conference on Machine Learning, volume 97 of Proceed- ings of Machine Learning Research, pages 4051-4065 PMLR, 09-15 Jun 2019. URL
htttp://pproceedings .mrg.ss..rr... press/ Ptress/v9//iine v97/1iu19f html
[39] Changjian Shui, Qi Chen, Jiaqi Li, Boyu Wang, and Christian Gagné. Fair representation learning through implicit path alignment. In ICML, 2022.
[40] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. Wilds: A benchmark of in mn-the-wild wild distribution shifts. In International Conference on Machine Learning, pages 5637-5664. PMLR, 2021.
[41] Joshua K Lee, Yuheng Bu, Deepta Rajan, Prasanna Sattigeri, Rameswar Panda, Subhro Das, and Gregory W Wornell. Fair selective classification via sufficiency. International Conference on Machine Learning, pages 6076-6086. PMLR, 2021.
[42] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning, pages 1321-1330. PMLR, 2017.
[43] Elliot Creager, Jörn-Henrik Jacobsen, and Richard Zemel. Environment inference for invariant learning. In International Conference on Machine Learning, pages 2189-2200 PMLR, 2021.
[44] Risheng Liu, Jiaxin Gao, Jin Zhang, Deyu Meng, and Zhouchen Lin. Investigating bi-level optimization for learning and vision from unified perspective: survey and beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 1-1, 2021. doi: 10.1 109/ TPAML.2021.3132674
[45] Manish Raghavan, Solon Barocas, Jon Kleinberg, and Karen Levy. Mitigating bias in algorith- mie hiring: Evaluating claims and practices. In Proceedings of the 2020 conference on fairness, accountability, and Iransparency, pages 469-481, 2020.
[46] Atilim Gunes Baydin, Barak A. Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic differentiation in machine learning: survey. Journal of Machine Learning Research, 18(153):1-45 2018. http:t org/papers/v18/17- html
[47] Eunbyung Park and Junier B Oliva. Meta-curvature. Advances Neural Information Processing Systems, 32, 2019.
[48] Changjian Shui, Qi Chen, Jiaqi Li, Boyu Wang, and Christian Gagné. Fair representation learning through implicit path alignment. arXiv preprint vrXiv:2205.13316 2022.
[49] Shai Shalev-Shward and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[50] Anastasia Pentina and Christoph Lampert. A pac-bayesian bound for lifelong learning. In International Conference on Machine Learning, pages 991-999. PMLR, 2014.
[51] Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended pac-bayes theory. In International Conference on Machine Learning, pages 205-214. PMLR, 2018
[52] Qi CHEN, Changjian Shui, and Mario Marchand. Generalization bounds for meta-learning: An information theoretic analysis. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL hhtpps //openrevies net:/oouum2.-992225522.
[53] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint 1rXiv:1312.61 14, 2013.
[54] Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. International Conference on Muchine Learning, pages 1613-1622. PMIR, 2015.
13

---

[55] Jianmo Ni, Jiacheng Li, and Julian McAuley. Justifying recommendations using distantly- labeled reviews and fine-grained aspects. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (FMNIP-IJCNIP)), pages 188-197, 2019.
[56] Allison Koenecke, Andrew Nam, Emily Lake, Joe Nudell, Minnie Quartey, Zion Mengesha, Connor Toups. John Rickford. Dan Jurafsky, and Sharad Goel. Racial disparities in automated speech recognition. Proceedings of the National Academy of Sciences, 117(14);7844-788) 2020.
[57] Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint arXiv:1910.0110,, 2019.
[58] Daniel Borkan, Lucas Dixon, Jeffrey Sorensen, Nithum Thain, and Lucy Vasserman. Nuanced metrics for measuring unintended bias with real data for text classification. In Companion proceedings of the 2019 world wide web conference, pages 491-500, 2019.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A]. You are strongly encouraged include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/amswers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The proposed theoretical analysis
is restricted in the randomized algorithm.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We study the algorithmic fairness. It is worth noting that ensuring group sufficiency may degrade other fair criteria such as DP/EO.
(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] In the paper and Appendix.
(b) Did you include complete proofs of all theoretical results? [Yes] Appendix.
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 URL)? [Yes] We provided the code for the reproduction.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the source code.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] We visualize the Boxplot of the results.
14

---

(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)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "g1_-YTEliQ", "reviewer": "Reviewer_2NvT", "summary": "This paper discussed learning group sufficiency and accuracy for multiple subgroups. More specifically, it can have many subgroups and limited samples for each subgroup, which is a practically realistic and challenging task. The authors proposed a bi-level optimization to learn the fair predictor, and further derived several theoretical results to justify that both group sufficiency and accuracy could be controlled. The empirical performance demonstrated better fairness and accuracy of the proposed approach.", "questions": "It would be great if the author could address the questions in weakness and comments.", "limitations": "This paper discussed the limitations in the checklist.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n1.\tThe fairness topic discussed in this paper is interesting and important: when and how we could simultaneously achieve fairness (groups sufficiency) and accuracy (small generalization error). \n2.\tBased on the theoretical analysis, this paper derived a novel fair learning approach. Besides, extensive empirical results demonstrated the superiority of the proposed approach. \n3.\tIn general, the paper is clearly written and well presented.\nWeaknesses and comments:\n1.\tThis paper mainly focused on group sufficiency as the fairness metric. Is it possible to derive similar results under criteria of demographic parity or equalized odds? What are the potential challenges for other fair metrics? Under these settings, is it still possible to achieve both fairness and accuracy for many subgroups?\n2.\tThe regularization coefficient $\\lambda$ seems to have a joint optimal value in 0.1-2. Could you elaborate more on why both fairness and accuracy drop when $\\lambda$ is large?\n3.\tIs it possible to assume the general gaussian distribution rather than isotropic gaussian in the proposed algorithm? What is the difference?\n4.\tCan the proposed theoretical analysis be extended for a regression or segmentation task? For example, could we obtain the same results as the classification task?\n5.\tCould you explain a bit more on the intuition of group sufficiency? Is there any relation to the well-known sufficient statistics?\n        Other comments:\n1.\tCould we extend the protected feature $A$ to a vector form? For instance, $A$ represents multiple attributes.\n2.\tIn the Introduction part, the authors introduced a medical therapy instance to present the importance of group sufficiency. Could you explain a bit more about the difference between sufficiency and DP/EO metrics in the real-world application scenarios?\n3.\tIn line 225 and line 227, the mathematical expression of gaussian distribution is ambiguous.\n4.\tIn section 4.4, it mentions the utilization of Monte-Carlo sampling method. I am curious about the influence of different sampling numbers.\n\n\n================================================\nThanks the effort from the authors, and I am satisfied with the rebuttal. I would like to raise my score to 8.", "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": "fbCrXphbHX6", "reviewer": "Reviewer_wL7w", "summary": "This paper presents an approach for learning predictors that have a small 'sufficiency' gap. Here the sufficiency gap is a difference that measures how invariant a predictor is across different subgroups.  The paper gives a theorem that bounds the sufficiency gap of a predictor in terms of the bayes optimal classifier. The proposed bound is then specified to the learned/randomized predictor in a separate corollary leading to 1) an optimization term and 2) an approximation term. Finally, the paper gives a bilevel optimization formulation for learning a predictor that has small sufficiency gap. In the lower level objective, the goal is to learn group specific predictors that while the upper level loss updates a global objective that tries to make the predictor as 'close' as possible to each of the subgroup predictors learned by the lower level problem. The bilevel formulation is compared to other baselines on different datasets where it has favorable performance.", "questions": "The main questions that I have a listed in the weakness section above. The ones I would like to hear the authors opinion on are 1) Challenge with different structural groups and 2) Feasibility.", "limitations": "An explicit discussion of limitations is not in the draft; perhaps this can be included in the next iteration.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n- **Studies Important Problem & Proposes an Interesting Solution**: The paper studies an important but open problem of learning predictors that have low sufficiency gap. The bilevel formulation presented is also interesting and is a relatively new way to approach the problem.\n\n- **Interesting Generalization Error Bound**: Theorem 4.1 gives a generalization error bound of learning group-based predictors, which is also an interesting result.\n\n- **Empirical Performance**: The results and comparison do seem to show that the bilevel formulation here either compares favorably or outperfoms other methods.\n\n\n## Weaknesses\nNone of the weaknesses here are really disqualifying, but could be easily addressed in the paper.\n\n- **Limited Samples**: The paper motivation of the paper is that there are only limited samples in each subgroup; however, how can there only be limited samples if one still has to learn a predictor for that subgroup? In practice, I don't think this approach works with only a limited number of samples. However, this issue is a matter of semantics.\n\n- **Feasibility**: It is unclear how such group based approaches will scale with the number of groups. If $\\vert \\mathcal{A} \\vert = 100$, is this approach even feasible? There is an assumption here that the $ \\mathcal{A}$ partitions the available samples, but in practice you can have a sample be the intersection of two protected attributes, i.e., race and gender. In practice, poor performance often persists for the groups that happen to be intersection of protected attributes.\n\n- **Link From Theorems to Bilevel Formulation**: It is not clear to me how the propositions and theorems in the paper suggest a bilevel formulation. It is still possible to relax the bilevel problem into a single objective with several penalties for each group. Not sure what in the theorems really necessitates a bilevel formulation.\n\n\n- **Take away from the theorems**: Several of the theorems are in terms of the bayes optimal classifier for either a group or all data. Since the bayes classifier is usually infeasible to compute in practice, it is a bit hard to translate these insights to practice.\n\n\n- **Challenge with different structural groups**: I wonder if the authors can speak to issues that occur when, say two groups just have different structural properties. Consider a 1-d case where a group of points have two regression parameters with positive slope, but the other groups has true parameters with negative slope. I am not sure how the formulation will handle that. Perhaps this is a limitation of the current setup?\n\n- **Missing Literature on Bilevel Optimization**: There is an emerging rich literature on bilevel optimization that this paper did not reference or discuss. Once can often solve these problems with implicit differentiation or unrolling(as is done here). A discussion of these points is needed here.", "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": "d8vcf0IyJS", "reviewer": "Reviewer_Qbu1", "summary": "This paper presents a method for learning a fair predictor which is designed for scenarios where the data contains multiple subgroups, each with limited number of samples. This method formulates the subgroups fair predictor question as a bilevel objective. \n\npost-rebuttal\nThank you for the clarifications. I will raise my score to 7.", "questions": "(1) Need optimal $\\lambda$ to be tuned by hand for each dataset?\n(2) As I described in the weakness part, I think it's not a fair comparison in Figure 3(a). Could you please show the group sufficiency gap for each dataset with the same accuracy?\n(3) How does the number of subgroups influence the final result.", "limitations": "The author didn't described the limitations of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": " Strengths:\n(1) The paper proposed a novel method and provides solid prof. \n(2) The paper's framework seems technically sound. The gradient estimates seem reasonable to me. \n(3) The paper focuses on group sufficiency gap to measure fairness\nWeaknesses:\n(1) For Figure 3(a), though the method could achieve a lower group sufficiency gap, the accuracy is worse. I think this result is not enough to show the benefit because of the trade off between accuracy and fairness. \n(2) The bilevel optimization idea is not very novel as there are some existing works such as Ditto[1].\n[1] Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pages 6357–6368. PMLR, 2021.", "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": "Xl5pH_x9wTs", "reviewer": "Reviewer_WyD4", "summary": "This paper considers the multiple subgroups scenario in the binary classification task. In order to avoid the inherent trade-off between accuracy and fairness (with fairness criteria such as DP and EO), authors focus on the group sufficiency, which requires that conditional expectation of $Y$ is invariant across different sub-groups. The proposed method is theoretical justified. Several theoretical results including the generalization error and the upper bound on the group sufficiency gap are derived. Based on the upper bound on the group sufficiency gap of the randomized algorithm, a machine learning algorithm is proposed to mitigate the bias of a model while not losing the informativeness. The idea of the novel bilevel optimization algorithm is to train an individual fair predictor by training the subgroup-specific predictors and then aggregating them. The idea of the novel bilevel optimization algorithm is to train an individual fair predictor by training the subgroup-specific predictors and then aggregating them. This allows to achieve superior performance over the other baselines on Amazon review, Toxic comment datasets.", "questions": "* Through the proof of proposition 3.1, it was confirmed that the suggested group sufficiency gap can be achieved to zero with $f^{Bayes}$. However, since $\\mathbb{E}[Y|f^{Bayes}(X,A_1)] = \\mathbb{E}[Y|f^{Bayes}(X,A_2)]$ is not generally satisfied, the invariance of conditional expectation for different subgroups is not established ($A_1$ and $A_2$ denotes two different groups). In other words, even if ${Suf}_{f}$=0, that conditional expectation of ground-truth label given predictor output ($\\mathbb{E}[Y|f^{Bayes}(X,A_i), A_i]$) is invariant to the different groups is not guaranteed, which seems undesirable when considering the introduction background of Group sufficiency (line 30-32).\n* The assumption that the Bayes-predictors for each group are the same seems to be strong, and the use of different classifiers for each group seems to have induced this phenomenon, what do you think?\n* In the algorithm, $Q$ is used as an informative prior, but it seems that $Q$ may not be informative at the beginning of learning. I wonder if there is an experimental result or discussion for that. (Adaptively allocating lambda values according to the epoch may be a way.)\n* DRO is a method that considers the worst-group accuracy, so it does not seem surprising that it is not effective in reducing the group sufficiency gap compared to the proposed method. It would be good to add a comment on the background of using DRO as a baseline.", "limitations": "It is mentioned that the main theoretical analysis is restricted to the randomized algorithm. It is noted that while Group sufficiency is improved, other fairness criteria such as DP/EO can be deteriorated. Also, authors mentioned that if the variance of Bayes predictors is large, the fair prediction model derived from the proposed algorithm may not that effective.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[Strength]\n* The paper is cleary written and the proposed bilevel optimization algorithm based on the theoretical results is original.\n* It is quite meaningful that a model can achieve accuracy and fairness simultaneously under the Group sufficiency criterion unlike DP/EO (However, this appears to be achievable only when $f$ is similar)\n* It is a great advantage that it can be applied to a variety of datasets, including NLP datasets (in typical fairness methods, there is often no scalability for diverse data types).\n* From the group sufficiency of the $A$-group Bayes predictor, it is shown that the model can achieve both informativeness and fairness, simultaneously (Proposition 3.1).\n* In theorem 3.2, an upper bound of the group sufficiency gap of any predictor $f$ is derived.\n* Based on the theorem 3.2, an upper bound for the randomized algorithm is proposed. (Corollary 4.1).\n* In theorem 4.1, the generalization error bound corresponding to the lower-level of the proposed algorithm is drawn.\n\n[Weakness]\n* In order for $Q$ to be informative and fair prediction, $f^{Bayes}$ should be similar, which seems to be a strong assumption in practical scenario.\n* In algorithm 1, subset $A'$ is sampled for memory saving at each epoch, however, as this type of sampling is quite unfamiliar, it would be better to discuss further.\n* Given that it can be applied to various datasets, the additional experimental results on vision datasets will have the effect of highlighting strengths of this paper.\n* Experimental results on commonly used datasets in fairness literature such as COMPAS and Adult can be considered. (In these datasets, it seems possible to compare the proposed algorithm with baselines such as FSCS and EIIL.)\n* It would be good to conduct an ablation study on using $Q$ as an informative prior.\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": {}}]

Author rebuttal:

Decision: Accept