Generalized Demographic Parity for Group Fairness
Authors: Zhimeng Jiang
Xiaotian Han
Chao Fan
Fan Yang
Ali Mostafavi
Xia Hu
Venue: ICLR 2022 Poster (2022)
Keywords: Generalized demographic parity
estimation error analysis

Abstract: This work aims to generalize demographic parity to continuous sensitive attributes while preserving tractable computation. Current fairness metrics for continuous sensitive attributes largely rely on intractable statistical independence between variables, such as Hirschfeld-Gebelein-Renyi (HGR) and mutual information. Statistical fairness metrics estimation relying on either tractable bounds or neural network approximation, however, are not sufficiently trustful to rank algorithms prediction bias due to lack of estimation accuracy guarantee. 
To make fairness metrics trustable, we propose \textit{\underline{G}eneralized \underline{D}emographic \underline{P}arity} (GDP), a group fairness metric for continuous and discrete attributes. We show the understanding of GDP from the probability perspective and theoretically reveal the connection between GDP regularizer and adversarial debiasing. To estimate GDP, we adopt hard and soft group strategies via the one-hot or the soft group indicator, representing the membership of each sample in different groups of the sensitive attribute. We provably and numerically show that the soft group strategy achieves a faster estimation error convergence rate. Experiments show the better bias mitigation performance of GDP regularizer, compared with adversarial debiasing, for regression and classification tasks in tabular and graph benchmarks.

Published as a conference paper at ICLR 2022
GENERALIZED DEMOGRAPHIC PARITY FOR GROUP FAIRNESS
Zhimeng Jiang' Xiaotian Han', Chao Fan', Fan Yang?, Ali Mostafavi', and Xia Hu² Teeas A&& University, "Rice University
ABSTRACT
This work aims generalize demographic parity to continuous sensitive attributes while preserving tractable computation. Current fairness metrics for continuous sensitive attributes largely rely on intractable statistical independence between variables, such Hirschfeld-Gebelene Seeadd--eeleii--eeeee Renyi (HGR) and mutual information. Statistical fairness metrics estimation relying on either tractable bounds or neural network approximation, however, are not sufficiently trustful to rank algorithms prediction bias due to lack of estimation accuracy guarantee. To make faimess metrics trustable, fairness metric for continuous and discrete attributes. We show the understanding of GDP from the probability perspective and theoretically reveal the connection between GDP regularizer and adversarial debiasing. To estimate GDP, we adopt hard and soft group strategies via the one-hot or the soft group indicator, represent- ing the membership of each sample in different groups of the sensitive attribute. We provably and numerically show that the soft group strategy achieves a faster estimation error convergence rate. Experiments show the better bias mitigation performance GDP regularizer, compared with adversarial debiasing, for regres- sion and classification tasks in tabular and graph benchmarks
propose Generalized Demographic Parity (GDP), group
INTRODUCTION
Fairness problem has attracted increasing attention in many rating, insurance pricing and college admission (Mchrabi et al.] 2021: Du et al.) [2020: Bellamy al. 2018). the adopted machine learning models encode and even amplify societal biases toward the group with different sensitive attributes. The majority of existing fairness metrics, such as de- mographic parity (DP) (Feldman et al.] 2015), equal odds (EO) (Hardt al., (016),, presumably consider discrete sensitive variables such as gender and race. In many real-world applications in- cluding urban studies and mobility predictions (Tessum al. 202T), however, individuals' sensitive attributes are unavailable due to privacy constraints. Instead, only aggregated attributes presenting in continuous distributions are available, and thus fairness requires unbiased prediction over neigh- borhood or region-level objects. Additionally, the sensitive attributes, such age and weight, are inherently continuous (Mary et al. 2019, Grari et al.) (0)). The widely existing continuous sensitive attributes stimulate further fairness metrics definition and bias mitigation methods.
applications, such as credit
Existing fairness metrics on continuous sensitive attributes rely on the statistical measurement of independence, such as firschfeld-Gebelei-- Renyi (HGR) maximal correlation coefficient (Mary et al. 2019) and mutual information (Jha et al. [02T]] Creager et al., 2019), which are computation- intractable due to the involved functional optimization. Note that the mutual information involves the ratio of probability density function, it is intractable to directly estimate mutual information via probability density function estimation due the sensitivity over probability density function, especially for the low probability density value. Previous works (Roh et al. 2200 Lowy et al. 2021] Cho al. 2220)) adopting mutual information or variations as regularizer, however, rely on tractable bound, or computationally complex singular value decomposition operation (Mary et al. 2019), or training- training-needed needed neural network approximation (Belghazi et al., 2018), such as Donsker- Varadhan representation (Belghazi et al.) 2018), variational bounds (Poole et al. 2019). Nevertheless, it is
Codess available at http://ggitallcomm/mmnengg//2zpp

---

Published as a conference paper at ICLR 2022
Global MVF avg
Giobal m+30 B/AWWH avg
GODP rrc
Local Global aug
ADP
AD
TV
28
Figure 1: Illustration of demographic parity definition for binary and quatemary sensitive attributes, and generalized demographic parity for continuous sensitive attribute. Markers * + represent av- erage prediction among specific discrete sensitive attributes, Red dashed line and blue solid line ~ represent prediction average among all data and that with specific sensitive attribute. TV(;)) represents weighted total variation distance.
unreliable adopt the mathematical bound of fairess metric to evaluate different algorithms since lower metrics bound does not necessarily imply lower prediction bias. A question raised:
Can we extend DP for continuous attributes while preserving tractable computation?
In this work, we provide positive answers via proposing generalized demographic parity (GDP) from regression perspective. Figure provides an illustrative example for DP and GDP. The local prediction average (blue solid curve ~) and the global prediction average (red dashed line --) represent the average prediction value given sensitive attributes and the whole data samples. respec- tively. The local and global prediction average should be consistent at any specific continuous sen- sitive attributes. Therefore, we define GDP, via the weighted total variation distance, to measure the distance between the local and global prediction average, where the weight is the probability density of continuous sensitive attributes. We also theoretically demonstrate the equivalence of GDP and DP for binary sensitive attributes, provide understanding of GDP from probability perspective, and reveal the bias mitigation methods connection between GDP regularizer and adversarial debiasing.
Although GDP is clearly defined on the unknown underlying joint distribution of prediction and sensitive attributes, only data samples, in practice, are available. To this end, we propose two GDP estimation methods, named histogram estimation (hard group strategy) and kernel estimation (soft group strategy) methods, where kernel estimation is provable with faster estimation error conver- gence rate w.r.t. data sample size. Specifically, histogram estimation manually divides continuous sensitive attributes into several disjointed and complementary sensitive attributes bins, and then each sample only belongs to one specific bin containing the sensitive attribute of the sample. In other words, the group indicator of the sample is one-hot. As for kernel estimation, instead of quan- tizing continuous sensitive attributes as several groups, the group indicator of the sample treated as a kernel function. In other words, to calculate the mean prediction value given specific sensi- tive attributes, group smoothing strategy adopted via soft indicator determined by the sensitive attribute distance between the sample sensitive attribute with target-speciis sensitive attribute.
In short, the contributions of this paper are:
We develop a tractable group faimesss metric GDP for continuous sensitive attributes. We theo- retically justify GDP via demonstrating the equivalence with DP for binary sensitive attributes, providing GDP understanding from probability perspective, and revealing the connection be- tween GDP regularizer and adversarial debiasing.
We propose histogram and kernel GDP estimation and provably demonstrate the superiority of kernel GDP estimation method with faster estimation error convergence rate w.r.t. sample size.
We experimentally evaluate the effectiveness and expansibility of GDP different domain benchmarks (e.g., tabular, graph, and temporal graph data), tasks (e.g, classification and re- gression tasks), and compositional sensitive attributes.
2
RELATED WORK
Machine Learning Fairness Fair machine learning targets bias mitigation for automated decision- making systems. Various fairness definitions, such as group fairness and individual fairness, have been proposed (Zemel et al. 2013). Group metrics, such DP and EO, measure prediction dif-
2

---

Published as a conference paper at ICLR 2022
ference between the groups with different sensitive attributes such as gender, age Louizos et al. 2016 Hardt et al. 2016). While pre- and post- proccescgsssnng methods have been proposed for fairness boosting, these methods can still lead to higher prediction bias (Barocas al. 2017) compared with in-processing methods, such as adding regularizer, adversarial debiasing and data augmentation. For example, the covariance between the predictions and sensitive attributes regularization are imposed to boost the independence in (Woodworth et al., (017). (Zafar et al. (011)) constrains the deci- sion boundaries of classifier minimize prediction disparity between different groups. Adversarial training has been originally proposed for deep generative modeling (Goodfellow et al., 2014)and has been introduced for prediction debias in representation learning (Zhao al. 20200 Beutel al.) 2017 Louppe et al. (017)) and transfer learning (Madras et al. 2018). Data augmentation, such as fair mixup (Chuang & Mrouch| 2020), can improve the generalization ability for fairness. Repre- sentation neutralization is proposed to boost fairness without sensitive attribute (Du et al. 2021).
non- parametric method to estimate the continuous probability density function of random variable (Davis et al. 2011 Parzen 1962). Given finite data samples, KDE smoothly estimate the probabil- ity function via weighted summation, where the weight is determined via kernel function (Epanech-) nikov 1969). Kernel regression is a non-parametric technique to estimate the conditional expecta- tion random variable [Nadaraya 1964). Nadaraya- Watton Kernel regression function estimator is proposed for regression via locally normalized weighted average in (Bierens) 1988), where the sample weight is determined by kernel function.
Kernel Density Estimation and Kernel Regression Kernel density estimation (KDE)
3 GENERALIZED DEMOGRAPHIC PARITY
Without loss of generality, we consider a binary classification task to predict the output variable Y given the input variable X, while avoiding prediction bias for sensitive attribute S. Define the input X E X C Rd, labels Y E {0, 1}. and machine learning model f : Rd - [o, 1] provides prediction score y = [(X). Fairness requires predictor Y to be independent of sensitive attribute S, regardless of continuous or discrete, i.c., P( 9) P(Ý O s) for any support value y and (Beutel et al., 2017). Since the independent constraint is difficult to optimize, the relaxed demographic parity (DP) (Madras et al. 2018 metries are proposed to quantitatively measure the predictor bias for binary sensitive attribute S E {0,1} 13. Formally, the demographic parity is defined as ADP- = E 18 = 0] Ey = 1]l, where R[[ represents variable expectation. For categorical sensitive attribute E S, work (Cho et al. 2020) introduces a fairesss metric, named difference w.r.t. demographic parity (DDP) ADDP = E.es [E|S = s] - EýJ}].
Although DP has been widely used to evaluate the prediction bias, it is still inapplicable for con- tinuous sensitive attributes since the data samples cannot be directly divided into several distinctive groups based on the sensitive attributes. Without loss of generality, attributes S E [0, 1] and propose GDP to extend tractable DP for continuous sensitive attributes. Assume the joint distribution of tuple (5, Y') is Ps,y (x, 5)), the local prediction average and global prediction average are defined as the prediction expectation given sensitive attribute $ = s and without any sensitive attribute condition, i.e., local prediction average m(s) - EEiiS = *] and
assume continuous sensitive
global prediction average mang Es[m(S)] = E[ respectively. Then, we adopt weighted total variation distance on local prediction average and global prediction average, where the weight is specified by the probability density function of the sensitive attribute. The formal definition of the discrepancy demographic parity for continuous sensitive attributes is as follows:
AGDP= = I'' [m(s) -maug Ps(S = s)ds Es[lm(S) -avgll
(I)
We also provide the connection of GDP and DP for binary sensitive attributes, which implies that GDP is equivalent to DP for binary sensitive attributes, as follows:
Theorem 1 (Connection between DP and GDP). For binary sensitive attribute S E f0,1), GPD and DP are equivalent except the coefficient only deperdentt on datasets. Specifically, the relation of AGDP and ADP satisfies AGDP = (Ps(S = 1) Ps(S = 0) ADP.
The proof of Theorem Tis is presented in Appendix A For categorical sensitive attributes, it is easy to EE i.e., GDP is weighted DDP for
obtain that AGDP- E.es Ps E)
3

---

Published as a conference paper at ICLR 2022
categorical sensitive attributes. In nutshell, GDP is natural fairness metric extension for binary and categorical sensitive attributes. Since the independence between prediction Y and sensitive at- tribute implies that the joint distribution Ps (s, ú) and product marginal distribution Ps (s) (ū) are the same, the bias can be measured by the distance of the joint distribution and product marginal distribution. Subsequently, we show the connection of GDP and prediction-weighhee total variation distance between these two distributions as follows:
Theorem 2 (Probability View of GDP). Assume the joint distribution of (Y,S) with support
[0, 112 is (s, Define the prediction-weighheed total variation distance as TVerea((P) (P),
,2)
So So (j. - p (ÿ. s)ldÿds. Then the proposed GDP for continuous senstive attribute is upper bounded by prediction- weighted total variation distance between the joint distribution and product marginal distribution:
AGDP = [/' ! (0PPs.lss.0 Ps) ( didss & TVpred Ps))
The proof of Theorem 2 is presented in Appendix B lower bound for grediction-weigheee total variation distance between these distributions and implies the necessity of GDP for bias measurement.
Theorem demonstrates that GDP is actually
4
GDP ESTIMATION
GDP defined based on the underlying joint distribution P (s.) of tuple (S, V), where S. E [0. 1]. The underlying joint distribution, however, unknown. Thus, we aim estimate GDP given samples {(s,, 9n). n E [N]], where [N] é [1..... .... To bridge this gap, we propose histogram GDP estimation and kernel GDP estimation methods based on different group strategies. Specifically, histogram GDP estimation hardly groups data samples via creating consecutive, non- overlapping intervals bins, and the local prediction average is estimated by the average prediction among the data samples in the bin. As for kernel GDP estimation, a soft group indicator, determined by the kernel function and sensitive attribute distance, is adopted to provide group smoothing strat- egy. Specifically, the local prediction average for target sensitive attribute is calculated via weighted prediction, where the sample with sensitive attribute close the target sensitive attribute possesses large weight.
Histogram GDP Estimation A histogram is originally approximate representation of the un- derlying data probability distribution via creating several consecutive, non-overlapping intervals or bins with, usually but not required, equal bandwidth. In this paper, we assume all bins with equal bandwidth h and the number of bins No. A A is an integer. In other words, the data tuples can be divided into N₁ groups, and the bin intervals are given by B1 = [0, h). B2 = h,, 2h). ".. BN, [(N, 1)h, 1]. Define indicator function T(A) as 1 if event A happens, otherwise is 0. Thereby, the group indicator wo (n, i) of sample (sn, 9n) for i - th bin is given by [[s,, E B.). Note that all bin intervals complementary; each sample belongs one and only one bin, i.e., the indi- cator vectors (n) = [wy, (n. 1).... (n, N₂)) for sample n is one-hot, which formally define the hard group strategy. The local prediction average and probability of sensitive attribute can be point-wisely estimated based on the empirical expectation and distribution. Specifically, for E B,, the local and global prediction average are given by
N I(sn E B,)os. for [Nu]; mang
N
n"
(s (sE
Σ
=
Di-
(2)
n=1
n=1
Similarly, the probability sensitive attribute given by Pb (s E B,) combine all estimations to calculate prediction bias as follows:
NN N
[(,,
Finally,
No.
ÅGDP(k)
Σ
t 8 E Ba)
miay Ps B,).
Kernel GDP Estimation Histogram GDP estimation provides hard group strategy via creating several bins. However, a tiny sensitive attribute perturbation can lead to different group indicators
4

---

Published as a conference paper at ICLR 2022
and thus histogram estimation is not robust sensitive attribute. On the other hand, data tuple not necessarily belongs to one group for continuous attributes. For example, the data sample with = 0.5 may have the same probability belonging to target sensitive attributes 0.4 and s 0.6.
Based on these observations, we propose kernel GDP estimation via group smoothing. Intuitively, when calculating local prediction average probability density function for target sensitive at- tribute, the tuple with more close attribute is entrusted higher weight. Specifically, we introduce a symmetric one-dimensional smoothing kernel function K(s) 2 satisfying normalized condition
[ (s)dss symmetry condition f sK (s)ds 0 and finite variance ofk _ 5 Ks(dss O. Define h > 0 as the kernel bandwidth. For target sensitive attribute s, the tuple weight for sample
with sensitive attribute Sn is given by w(sn, s) - A ( In short, kernel function provides the group smoothing strategy based sensitive attribute distance of tuple pair.
Given the smoothing kernel function K (s)), the local and global prediction average can be obtained via normalized weighted average (Nadaraya-Warte Watson kernel estimator) as follows:
(s)
N E On K(KK ()) E K(
mil aeg
2
N
Dn
(4)
Similarly, the probability of sensitive attribute is given by (0) combine all estimations calculate kernel GDP estimation follows:
Σ K((m)=).
Finally,
NA
4GDP(h) = (m)(s) mang (s)ds.
(5)
Estimation Error Analysis We provide the theoretical analysis on GDP estimation error and prove the superiority of kernel GDP estimation. Assume that each data sample is independent and identi- cally distributed random variables. Therefore, the estimated GDP is still a random variable, and we adopt the expectation of the mean squared error (MSE) to quantify the accuracy of the estimation method. Formally, the error of histogram estimation and kernel estimation are given by
Erthist = E|LAGP - MAGDP-AGDP!:
Ertkernel = E ÅGDP - AGDP(T]
(6)
where the expectation is taken across N tuples. Here, we provide asymptotic analysis estima- tion error and show the superiority of kernel GDP estimation in the following:
Theorem (Estimation Error Convergence Rate). Assume that the mean prediction function m(s), given sensitive attribute s, is smooth and satisfies L- Lipschitz condition D on local average |m(ss) m(s) ) S L|s s' for any s, the optimal bandwidth choice for histogram and kernel estimation methods are hiist = 3N) and hirnel = ONN :).. Additionally, the estimation error satisfy Errhist = (NN 3) and Errkernel = O(N )), where O()) is big O notation.
The proof of Theorem 3 is presented in Appendix
C The proof sketch is to separately provide upper bounds for the estimation error of local average and sensitive attribute probability density estimation. Finally, we combine these two estimations to obtain the estimation error for GDP.
Computation Complexity Analysis Since GDP calculation involves in integral operations, the ap- proximated numerical integration is usually adopted with M probing sensitive attribute. The com- plexity to calculate local prediction average and probability density at M probing sensitive attributes are O(M N) and thus, the complexity for histogram and kernel estimation both are O OMMN). In (Mary et al. 2019). intractable HGR coefficient equals second large singular value of distribution ratio matrix can be upper bounded by tractable chi-square distance between the joint distribution and marginal product distribution. Assume that there are M probing prediction, the complexity for two-dimensional probability density function estimation and SVD is (MP and O(M²), and that of the chi-square distance is O(M² Therefore, the computation complexity for HGR (M + N)). As for the neural based approximation for HGR or mutual information, the complexity for training is quite large compared with directly computation.
2 Lipschitz condition requires bounded gradient w.r.t. sensitive attribute and guarantees the rationale local average estimation based neighhor data samples.
5

---

Published as a conference paper at ICLR 2022
5 ANALYSIS ON GDP REGULARIZER AND ADVERSARIAL DEBIASING
With GDP bias measurement for continuous sensitive attributes, it is natural to add GDP regularizer to enforce fairness. Another bias mitigation adversarial debiasing, a two-player framework for predictor and adversary with regression task. We establish the connection between GDP regular- izer and adversarial debiasing. and demonstrate that adversarial debiasing with specific adversary regression objective is actually minimizing GDP implicitly.
GDP Regularizer: As reminder, our goal is to learn predictor Y f(X) that approximates the label Y for each input while reducing the prediction bias AGDP w.r.t continuous sensitive attributes S. It is natural to add GDP regularization to enforce fairness. Given the prediction loss
+AAGDP, where L could be regression classification task loss and À is the hyperparameter to control the trade-off between the prediction performance and prediction bias reduction.
fereed the fairness-enforcing objective function is min pr (
Ad Adversarial Debiasing: Adversarial debiasing is another natural method to ensure fair prediction via a two-player game between predictor and adversary. Specifically, the predictor ʃ yields pre- diction Y. and given prediction Y. the adversary g tries to predict continuous sensitive attributes g(Y) in regression task. Similar to adversarial debiasing (Louppe et al. 2017), we adopt the same classifier and adversary structure, where the input of adversary is the output of the clas- sifier. For objective function of adversary, we adopted the utility function proposed in (Madras) et al. 2018) to represent sensitive attribute prediction accuracy. In this case, the predictor aims to generate accurate prediction and fool the adversarial simultaneously. while adversary targets high utility for accurate sensitive attribute prediction. Let Lyred denote the prediction loss and Lads represent the adversarial utility. Then adversarial debiasing is trained following the min-max proce- dure min max Lpred (f + ALadv
( (9(f(x)), 5). Detine g" arg min Ladv (g (f()))),
9
as the optimal adversarial given predictor f. the min max procedure is simplified to the objective function min Cpred (f (x)) + XLad (g (f()))))
Theoretical Connection: We provide an inherent connection between GDP regularizer and adversarial debiasing. Specifically, we demonstrate that the optimal adversarial utility Ladv 9- ()) is actually the upper bound of GDP AGDP as long as the utility function in adversary is fadu ($, 5) = 1$ - S| in the following theorem:
Theorem 4 (GDP and Adversarial Debiasing Connection). Considering predictor V f(X) and adversary Š $= =g(Y), given adversary utility (Sde(S = 1 188 SS| and optimal adversary g", then GDP AGDP is bounded by the utility function Ludo (g" (f(X)), with optimal adversary,
i.e., Ladv (g (f) 2 AGDP.
The proof of Theorem is presented in Appendix F Intuitively, a fair classifier aims to minimize the adversary utility to make prediction fair, and thus induces lower GDP metric. Theorem 4 reveals the inherent connection between GDP regularizer and adversarial debiasing: adversarial debiasing behaviors like predictor loss optimization with GDP regularization, as long the adversary is op- timal. Additionally, such connection not only holds for underlying data distribution, but also for empirical data distribution. The proof sketch is similar via replacing underlying data distribution as empirical data distribution in the expectation operation. In practice, the alternative optimization is usually adopted in adversarial debiasing via alternatively updating either predictor or adversary each training step while keeping the other one fixed.
Work (Madras et al. 2018) adopts encoder-decnder structure for transferable representation learning. We only adopt utility function connect GDP and adversarial dehiasing (Louppe al. 2017).

---

Published as a conference paper at ICLR 2022
6 EXPERIMENTS
We evaluate the effectiveness and expansibility of GDP. First, show the lower GDP estimation error for kernel GDP estimation [ with group smoothing, compared to that histogram, via two synthetic experiments. We empirically evaluate the effectiveness and expansibility of kernel estima- tion for multiple prediction tasks, including classification and regression tasks, and multiple domain real-world datasets. including tabular, graph and temporal graph data (See Appendix H.Ip. More- over, the kernel estimation is also applicable for compositional continuous sensitive attributes. For fair comparison, we compare our method kernel, adding kernel GDP estimation regularization, with (a) vanilla: training with empirical risk minimization (ERM) without any regularization; (b) histogram: histogram estimation with continuous sensitive attribute; (c) adv: adversarial debiasing (Louppe al. (017);: (d) adv-bm: adversarial debiasing with binary-quantized sensitive attribute; (e) hgr: the upper bound HGR as regularizer (Mary et al. 2019); and (fhgr-bn: the upper bound of HGR regularizer with binary- binary-quantized sensitive attribute. Specifically, demonstrate the trade-off between prediction performance and GDP by varying the typer-parameter À. In particular, adopt accuracy (Acc) for classification task and mean absolute enror (MAE) for regression task. Details about the baselines and experimental setups for each dataset can be found in Appendix H.2
6.1 SYNTHETIC EXPERIMENTS
We test GDP estimation error and investigate the robustness for histogram and kernel estimation via two synthetic experiments. The goal is to investigate the effect of bandwidth choice and number of samples on GDP estimation error. For data generation, we first generate bivariate Gaussian distribution (u, Σ) for samples (S, Y), where expectation μ (0.5, 1.0) and covariance matrix Additionally, generate the samples based on ps, 9) s + ÿ if 8, S
0.5
Σ
0.5
2.0]
1, via seccepaance-rjeettee method (Wells et al. 2004). For estimation, we select two typical kernel functions (tricube and Aitchison-Aiie -ittenn kernel (Mussa 2013)) for local prediction average, and two kernel functions (linear and cosine kernel functions) for probability density function estimation.
Figure 2 shows the GDP estimation error w.r.t. bandwidth h and number of samples N for bivari- ate Gaussian distribution and second synthetic bivariate distribution, respectively. We observe that histogram GDP estimation error is highly sensitive to bandwidth choice, while kernel estimation robust to bandwidth and kernel function choice due to the flexibility of group smoothing. As for er- ror rate with number of samples, our experiments show the error rate curve for histogram and kernel estimation. It is that kernel estimation achieve the fast error convergence rate if searching the optimal bandwidth for each method. In addition, the estimation error result is almost the same for different kernel functions, which supports the theoretical results in Theorem
Telogrem
Figure 2: Demographic parity estimation error analysis with respect to bandwidth and number of samples for Gaussian distribution and second synthetic distributions.
6.2 EXPERIMENTS ON TABULAR DATA
Dataset:Wi We consider two benchmark tabular datasets, UCI Adult and Crimes, to evaluate the effec- tiveness of kernel estimation for classification and regression tasks. UCI Adult dataset contains more than 40, 000 individual information from 1994 US Census. The classification task is predict
Siine there not ground truth on underlying data distribution, we adopt reliable kernel-based estimated GDP as fairness metric in real-world datasets. https://arciie..iii wwwp:iiiiiiii...iidiiiii.e wtt..c..dddmmmm/tttttt/aaaatt
7

---

Published as a conference paper at ICLR 2022
whether person's 's income exceeds $50k yr (KOHAVI, 1996.. We consider normalized age sen- sitive attribute to measure the fairesss of algorithms. The Crime dataset includes 128 attributes for 1, 994 samples from communities in the US. The regression task is to predict the number of violent crimes per population in US communities. We adopt the black group ratio as continuous sensitive attribute. Model: We adopt two-layer selu networks model (Klambauer al., (017) with hidden size 50 and report the mean prediction performance and GDP with 5 running times.
va bermel
hipogram
adk
verill keme
hattgram
adv
hg:.0
hgt
adv
hgr
82
33
30
78
21
76
18
0.0
0.5
1.0
1.5
2.0 GDP
2.5
3.0
3.5
0.0
0.5
1.0
1.5
2.0 GDP
2.5
3.0
3.5
(a) Adult dataset
(b) Crimes Dataset
Figure 3: Mitigation performance on tabular dataset with kernel estimation and other baselines. (a)
The tradeoff between Accuracy (classification) and GDP for Adult dataset; (b) The tradeoff between MAE (regression) and GDP for Crimes dataset.
Results: We compare the bias mitigation performance, i.e., the tradeoff between prediction perfor- mance and GDP, of kernel estimation with other baselines for the two tabular datasets in Figure 3 The hyper-parameter in Eq. (5) controls the tradeoff between prediction performance and GDP. Specifically, choose accuracy metric for classification task in Adult dataset, and MAE metric for regression task in Crimes datset. For adversarial debiasing, we vary the regularization weights to obtain the tradeoff curve. Overall, we make the following observations: (a) kernel estimation outperforms all other baseline methods in terms of performance-fairess tradeoff curve for Adult and Crimes datasets. Specifically, kernel estimation can achieve more than 1% accuracy improve- ment if GDP is lower than 0.02 for adult dataset, and more than 2% MAE reduction for Crimes dataset: (b) kernel estimation has lower computation complexity compared with adversarial debias- ing. Kernel estimation and histogram decrease more than 50% running time on an average across all tabular dataset, which makes kernel and histogram estimation readily usable for large scale real- world datasets; (c) The histogram estimation and binary-quatize sensitive attribute would lead to mitigation performance drop for kernel estimation, adversarial debiasing and HGR. This fact implies the importance of order information in continuous sensitive attributes for bias mitigation. In addi- tion, we observe adversarial debiasing training and HGR are not stable and large paramett unnecessarily leads to bias mitigation.
6.3 EXPERIMENTS ON GRAPH DATA
Dataset: We consider two real-world graph datasets. Pokec-z and Pokec-n, sampled from a larger one Facebook-like social network Pokec Slovakia. User profiles contain gender, age, interest, ed- ucation, working field and etc. We treat the normalized age as the continuous sensitive attributes and the node classification task is to predict the working field of the users. Model: We use three graph neural network backbones, graph convolutional networks (GCN) (Kipf & Welling 2017). graph attention networks (GAT) (Veličković et al. 2018) and Simplifying graph convolutional networks (SGC) (Wu et al., 2019) with 64 feature dimensions. We train GNN with 200 epochs with 5 running times and report the average accuracy and GDP. In each trial, the dataset is randomly split into a training, validation, and test set with 50%. 25%, and 25% partition, respectively.
We compare the mitigation performance of kernel estimation with other baselines for two datasets with three backbones in Figure Similarly, kernel estimation consistently outperforms the other basclines by a large margin and -uuatiie sensitive attributes inevitably deteriorate the mitigation performance. Another observation is that GDP can be reduced at least 80% at the cost
Results:
TThe biggest difference hetween continuous and discrete sensitive attribute falls the existence of order information (Mary et al. 2019) for attribute values.
hhtpss//archive..ss.so uci wtt.s//www.....//aaaaccmannnnee.
8

---

Published as a conference paper at ICLR 2022
of 2% accuracy for kernel estimation in two datasets and three backbones, while results in larger accuracy drop for other baselines. Additionally, adversarial debiasing and HGR are also unstable during training and higher hyper-parameter may lead to larger GDP.
GCN
GAT
SGC
00
50-
25
15
1
GDP
GDP
GDP
15,50
10.00
Harspun
687.01
49.50
15"
90
75
70
60-
55
65
1.5
6.
1.0
15
30
33
20
GDP
GDP
Figure 4: Mitigation performance of GCN, GAT and SGC for Pokec-n and Pokec-z dataset.
6.4 EXPERIMENTS ON COMPOSITIONAL CONTINUOUS SENSITIVE ATTRIBUTES
Similarly, the same two benchmark tabular datasets are adopted to evaluate the effective- ness of kernel estimation for compositional continuous sensitive attributes. Specifically, treat the normalized age and education number for UCI dataset, and black group ratio and normalized age for Crimes dataset as compositional continuous sensitive attributes. evaluate bias mitigation per- formance. Model: We also adopt two-layer selu networks model with hidden size 50 with 5 running times and report the average mean prediction performance and GDP.
Dataset:
Results: Figure 5] shows bias mitigation performance between prediction performance and GDP. Again, kernel estimation consistently achieves better tradeoff compared with all other baselines, and Sinary-quantized compositional sensitive attribute leads to mitigation performance drop.
komd
Notogram
20v
como
hsttg
Dn
80
79
27
78
24
77
76
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
GDP
(a) Adult dataset
(b) Crimes Dataset
Figure 5: Mitigation performance for compositional sensitive attributes.
7 CONCLUSION
We generalize demographic parity fairness metric, named GDP, to continuous sensitive attributes while preserving tractable computation. We theoretically justify the unification of proposed GDP for continuous and discrete sensitive attributes, and show the necessity of GDP via demonstrating the connection with joint and product margin distributions distance. We also propose two GDP estimation methods, named histogram and kernel, with linear computation complexity via hard and soft group strategies, and provide corresponding estimation error analysis. For the superiority of kernel estimation, provably demonstrate the faster estimation error convergence rate compared with histogram estimation, and experimentally show better bias mitigation performances in multiple domains, multiple tasks and compositional sensitive attributes.

---

Published as a conference paper at ICLR 2022
8 ACKNOWLEDGEMENTS
We would like to sincerely thank everyone who has provided their generous feedback for this work. Thank the anonymous reviewers for their thorough comments and suggestions. This work was supported in part by X-Grant project, National Science Foundation I18-1939716, ISS-1900900, IIS- 1750074 grant, and JPMorgan Faculty Research Award.
REFERENCES
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness in machine learning. Nips tutorial, 1:2017, 2017.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. In International Conference on Machine Learning, pp. 531-540. PMLR, 2018.
Rachel KE Bellamy, Kuntal Dey, Michael Hind, Samuel C Hoffman, Stephanie Houde, Kalapriya Kannan, Pranay Lohia, Jacquelyn Martino, Sameep Mehta, Aleksandra Mojsilovic, et al. Ai fair- ness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias. arXiv preprint 1EXX::/810001943 2018.
Alex Beutel, Jilin Chen, Zhe Zhao, and Ed H Chi. Data decisions and theoretical implications when adversarially learning fair representations. arXiv preprint 10XXv:/70.0007777 2017.
HJ Bierens.
The nadaraya-watson kernel regression function estimator. Faculty of Economics and Business Administration, Vrije Universiteit Amsterdam Serie Research Memoranda, (1988-58), 1988.
US Census Bureau. American community survey 5-year data, 2021. URL https:
7/www. wwnsus..scc...oo. gov wwwp://..wwo......roaoo..... surveys wwwccsstteciiic wwttinnicallccouuuui doc.mentat on/
and ocl.ee/wwa...geoooaao..../aeeee.
html
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the
22nd acm sigkdd international conference on knowledge discovery and data mining, pp. 785-794, 2016.
Jaewoong Cho, Gyeongjo Hwang, and Changho Suh. A fair classifier using kernel density estima- tion. Advances in Neural Information Processing Systems, 01.15088-1509) 2020.
Ching- Yao Chuang and Youssef Mroueh. Fair mixup: Fairness via interpolation. In International Conference on Learning Representations, 2020.
Elliot Creager, David Madras, Jömn-Henri Jacobsen, Marissa Weis, Kevin Swersky, Toniann Pitassi, and Richard Zemel. Flexibly fair representation learning by disentanglement. In International conference on machine learning, pp. 1436-14 1445. PMLR, 2019.
Cuebiq. Data for good: Location intelligence for good our contribution to the scientific commu- nity, 2021. WtRLhtpss:: hwtp://wwwwwccooo wwwp:/twwwwwwww.wt//ptppt. com/ about datt - for-t/aaaaaaa-ooooolll
da Xu, chuanwei ruan, evren korpeoglu, sushant kumar, and kannan achan. Inductive representation learning on temporal graphs. In International Conference on Learning Representations, 2020.
Richard A Davis, Keh-Shin Lii, and Dimitris N Politis. Remarks on some nonparametric estimates of density function. In Selected Works of Murray Rosenblau, pp. 95-100. Springer, 2011.
Mengnan Du, Fan Yang. Na Zou, and Xia Hu. Fairness in deep learning: computational perspec- tive. IEEE Intelligent Systems, 2020.
Mengnan Du, Subhabrata Mukherjee, Guanchu Wang. Ruixiang Tang, Ahmed Hassan Awadallah, and Xia Hu. Fairness via representation neutralization. arXiv preprint arXiv:2106.15 126777 2021.
Vassiliy A Epanechnikov. Non paramerrit estimation of a multivariate probability density. Theory of Probability & Its Applications, 14(1):153-158, 1969.
10

---

Published as a conference paper at ICLR 2022
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubra- manian. Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international conference knowledge discovery and data mining, pp. 259-268,44 2015.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde- Mardey Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
Vincent Grari, Sylvain Lamprier, and Marcin Detyniecki. Fairness-aware neural rényi minimization for continuous features. Proceedings of the 29th International Joint Conference on Artificial Intelligence, IICAI'20.
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, Qingquan Song, Jundong Li, and Xia Hu. Geometric graph representation learning via maximizing rate reduction. In Proceedings of the Web Confer- ence, 2022.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning, Advances in neural information processing systems, 19:3315-3323, 2016.
Akshita Jha, Bhanukiran Vinzamuri, and Chandan K Reddy. Fair representation learning using interpolation enabled disentanglement. arXiv preprint arXiv:2108.0022 2021.
Zhimeng Jiang, Xiaotian Han, Chao Fan, Zirui Liu, Na Zou, Ali Mostafavi, and Xia Hu. FMP: Toward fair graph message passing against topology bias. arXiv preprint arXiv:2202.041877 2022.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In International Conference on Learning Representations (ICLR), 2017.
Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter. Self-normalizing neural networks. In Proceedings of the 31st international conference on neural information pro- cessing systems, pp. 972-981, 2017.
KOHAVI. Scaling up the accuracy of naive-bayes classifiers: decision-tree hybrid. In Second International Conference on Knowledge Discovery and Data Mining, 1996, pp. 202-207, 1996.
Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard S Zemel. The variational fair autoencoder. In ICLR, 2016.
Gilles Louppe, Michael Kagan, and Kyle Cranmer. Learning to pivot with adversarial networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp- 982-991, 2017.
Andrew Lowy, Rakesh Pavan, Sina Baharlouei, Meisam Razaviyayn, and Ahmad Beirami. Fermi: Fair empirical risk minimization via exponential r) ''eyi mutual information. arXiv preprint arXiv:2102.. 202.::200,,/2866, 2021.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In International Conference on Machine Learning, pp. 3384-3393. PMLR, 2018
Jérémie Mary, Clément Calauzenes, and Noureddine El Karoui. Faimess-aware learning for contin- uous attributes and treatments. In International Conference on Machine Learning, pp. 4p.4232-499. PMLR, 2019.
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM Computing Surveys (CSUR), 54(6):1333 2021.
Hamse Mussa. The aitchison and aitken kernel function revisited. Journal of Mathematics Re- search, 5(1):22, 2013.
Elizbar A Nadaraya. On estimating regression. Theory of Probability & Its Applications, 9(1): 141-142, 1964.
Emanuel Parzen. On estimation of a probability density function and mode. The annals of mathe- matical statisties, 33(3):1065-107 1962.
11

---

Published as a conference paper at ICLR 2022
Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On variational bounds mutual information. In International Conference on Machine Learning, pp. 5171- 5180. PMLR. 2019.
Yuji Roh, Kangwook Lee, Steven Whang, and Changho Suh. Fr-train: A mutual information-based approach to fair and robust training. In International Conference on Machine Learning, pp. 8147- 8157. PMLR, 2020.
Christopher W. Tessum, David Paolella, Sarah Chambliss, Joshua S. Apte, Jason Hill, and Julian D. Marshall. (inssub;2.5/ssuun polluters disproportionnatly and systemically affect people of color the united states. Science Advunces, 7(18)eabf4441, 2021. doi: 10.s126/sci abf4491. URLhttps: www.::ww.ii..................
wttp/////aaaaaaaa 10. (022//cciade abf4491
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Martin Wells, George Casella, and Christian P Robert. Generalized accept-reject sampling schemes. In A Festschrift for Herman Rubin, pp. 342 347, Institute of Mathematical Statistics, 2004.
Blake Woodworth, Suriya Gunasekar, Mesrob Ohannessian, and Nathan Srebro. Learning non- discriminatory predictors. In Conference Learning Theory, pp. 1920-19533 PMLR, 2017.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinherger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp. 6861-6871. PMLR, 2019.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna Gummadi. Fair- ness constraints: Mechanisms for fair classification. In Artificial Intelligence and Statistics, pp- 962-970. PMLR, 2017.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International conference on machine learning, pp. 325-333. PMLR, 2013.
Han Zhao, Jianfeng Chi, Yuan Tian, and Geoffrey J Gordon. Trade-off's and guarantees of adversarial representation learning for information obfuscation. Advances in Neural Information Processing Systems, 33, 2020.
Ling Zhao, Yujiao Song, Chao Zhang, Liu, Pu Wang, Tao Lin, Min Deng, and Haifeng Li. T-gen: A temporal graph convolutional network for traffic prediction. IEEE Transactions Intelligent Transportation Systems, 21(9))3848 388-8888,, 2019.
12

---

Published as a conference paper at ICLR 2022
A PROOF OF THEOREM
For binary sensitive attribute S {0, the probability of sensitive attribute follows Bernoulli
distribution (Ps(S 0), Ps(S 1)) 1)) Therefore, the global prediction average given by mang Ps(S 00m(0) Ps(5 (1) and GDP
AGDP
Ps(S 0) m()) mavg Ps(S 1) mm(1 mavy
Ps(S 0) m(0) ( Ps(S 11)
+Ps(S 1) Ps(S 0)m + -5 1)m(1) - (m()))
2Ps(S 0)P3(5 1))m(0) m(1)
= 25s(5 = 0)Ps(5 = 1)ADP.
where the coefficient (P = 0)Ps(S = 1) only depends on data. This fact demonstrates the applicabiliity of GDP for categorical sensitive attribute with discrete measure choice for sensitive attributes, and is equivalent to demographic parity for binary sensitive attribute.
B PROOF OF THEOREM 2
Notice that the fairness constraint ideally requires the independence of prediction Y and sensi- tive attribute S, i.e., the joint distribution and product margin distribution equals: Py.s(ū. 8) (s) (0). Aiming measure independence deviation, natural intuition is quantify the prob- ability deviation via the distance between the joint distribution and product margin distribution. We show the connection between the proposed GDP and prediction-weighteee total variation distance of these two distributions. Recall the definition of GDP, it is easy to obtain
AGDP
m(s) mavg Ps(S = s)ds
L
u (Pris(ylssd '/¹
ÿ. (u)dg Ps(S = s)ds
I.
i (Prr.((..s) Ps(s) Py (i) dg djds
I. I. i| Ps(s) dÿds
TV P
which completes the proof.
C PROOF OF THEOREM 3
Notice that histogram and kernel estimation require local prediction average and probability density function estimation for sensitive attributes, we start with the analysis on local prediction average and probability density function estimation, and then provide the proof of GDP error analysis.
C.1 PROOF FOR HISTOGRAM ESTIMATION
Recall that the number of bins is N₁, with same bandwidth h, and bins interval are given by B = [0, h), Bg 2h), BN, [[N, 1)h, 1]. Firstly, we will separately analyze the error for local prediction average and sensitive attribute probability. Next, these two estimation error results be combined for GDP estimation error.
13

---

Published as a conference paper at ICLR 2022
Since the continuous sensitive attributes is considered, defined the probability density function of sensitive attribute as ps(s). The estimated probability density function is given by:
N
(s E B.) (s))) = h
Σ ==1
1(8 E B:) for 8 E B;;
Nh
Subsequently, we define the pointwise MSE enror MSEP (s) to measure probability density fune- tion estimation error given sensitive attribute as follows:
hist
MSE hste( = (sl pss(s)
(8)
where the expectation took across N samples. Then we have following Lemma on optimal pointwise MSE error for probability density function:
Lemma 1. Assume the mean prediction function m(s), given sensitive attribute s, is smooth and satisfies L-Lipschitz condition [m(s) m(s) ) I Lls - s I for any 8,8. Given N ii.dd samples {(n, sn),n E [N]] then the optimal MSE error min E (s) is O(N 3), where the optimal bandwidth satisfies h* = O(N +) for any sensitive attribute s. As for the local prediction average, similarly, we have the estimated local prediction average as follows:
mss) = Σn n=1 I(sn E B.)an for s E B;; I(s, E B;)
E
Subsequently, we also define the pointwise MSE error MSE (s) measure local prediction average estimation error given sensitive attribute follows:
MSE
hist (s) = Ellm" m(s)
(10)
where the expectation took across N samples. Then we have following Lemma 2 on optimal pointwise MSE error for local prediction average:
Lemma 2. Assume the mean prediction function m(s), given sensitive attribute 8, is smooth and satisfies L-Lipschitz condition [m(s) m(s')l < L|s - s') for any s.s'. Define the bounded
prediction variance d²(s) I o², given sensitive attribute as d² A Evisl(Ý -S s). Given N i.i.d. samples {Wnn sn), n [N]}, then the optimal MSE error min MS E (s) is O(N-5). B). where the optimal bandwidth satisfies h* O(N à) for any sensitive attribute
Proof for histogram estimation: Based on the definition of MSE error in Eq. (6), we have
Errhist
EJÁGDP - AGDP(1]
SV
B
[s) mang 1igs (8) - [m((s) mang l (s) ds }
IA IN3
[Im²(s) margl 105 ps(s)) -mm(s) -mavy mm (mn((s))) maval (ss(s) ds }
2E [[[
(x) - riann 2ds)] .R| L// (5)((s) - ps(
1''' (m^(s)) - mss)) foadds+B//// [ Imiiin Mavo (s)ss)
+2 2
2 O 4+ + O(N
where inequality (a) holds due to absolute value inequality, inequality (b) holds due to layb, a2b2l < lajllb; 62l + |a_ 42). inequality (c) holds based on (a + 6)² < 2(a b²) and Cauchy-Schward Schwarz inequality, inequality (d) holds based on Lemmas (I) and (2). Note that the order of the optimal bandwidth are the same in Lemmas I and ().. the optimal bandwidth for minimizing GDP MSE is -
14

---

Published as a conference paper at ICLR 2022
C.2 KERNEL ESTIMATION
Recall that we assume that kernel function satisfies normalized condition f (s)dds = 1, symmetry
(sK(ssds 1 and finite variance of _
f f
> O. We also define 0% f K (y) dy.
Similarly, the probability density function of sensitive attribute is given by ps(s). The estimated
probability density function is given by:
N
8n
K
(11)
Nh
h
n=1
Subsequently, we define the pointwise MSE error MS MSEP function estimation error given sensitive attribute as follows:
kernet (s) to measure probability density
MSE hist (s) (s) ps)
(12)
where the expectation took across N samples. Then we have following Lemma 3 on optimal pointwise MSE error for probability density function:
Lemma 3. Given N iidd samples 8,), E [M]] then the optimal MSE error
min MS MSE (8) is O(N- where the optimal bandwidth satisfies h" O(N-E) for any sensitive attribute s.
As for the local prediction average, similarly, we have local prediction average estimation as follows:
E K(Tn=")) ")
(8)
(13)
Σ K ((=m==)
Subsequently, we also define pointwise MSE error M.S.ETE Kernet (8) measure local prediction aver- age estimation error given sensitive attribute s as follows:
MSE Kerner (s) (s) - m(s)
(14)
where the expectation is took across N samples. Then we have following Lemma 4 on optimal pointwise MSE error for local prediction average:
Lemma 4. Define the bounded prediction variance d²(s) S 0², given sensitive attribute s, as sn). MSE error min MSEEeenae (s) is O(NOO(NN)))))) -),, where the optimal bandwidth satisfies h = O(N-3)
(s) 2 Evisi(y - -sS = s]. Given N ii.d samples {(n,, n [N]}, then the optimal
for any sensitive attribute s.
Proof for kernel estimation: Based on the definition of MSE error in Eq. ( we have
ErTkernel
EJAADPP - AGDP
WV
/
E
(m)((s) mang (5) |m()) -maggl (s(()) ds)
IAS
[4
L/ [Im((s) -maull (1'((s)) - ps(())] - |mm(s) - -aag m (s) + Mavel pps(s) ds 21
}
2F L/ (*)(s) - -mang pds IF. (' (s)
- (ds
+2 2 E [1/[" -m) ( pssss/sss EE 1.// |matgg mang Pps(s)ds} }
(6)
2 O(N 1 N
where inequality (e) holds due to absolute value inequality, inequality (f) holds due to bayb,
a2b2l < |ai||b; - 621 + |a a2|162], inequality (g) holds based on (a + 6)2 < 2(a + 6²) and Cauchy-Schwer Schwarz inequality, inequality (h) holds based on Lemmas (3) and (4). Note that the order of the optimal bandwidth are the same in Lemmas 33) and 4h, the optimal bandwidth for minimizing GDP MSE is O
15

---

Published as a conference paper at ICLR 2022
D PROOF OF LEMMAS
D.1 PROOF OF LEMMA I
Proof. Note that there exists bias-variance tradeoff for M SEnd
(s), i.c.
hist
MSEN hist(s) (s) = (s) - ps(s))
(b))(()) Ps((s)
2
+ P -B))))))))))))
Bius (+)
Var (+)
Next we analyze the bias and variance for probability density function MSE. For the bias part, note that, for E B₁, the expectation of estimated probability density function satisfies:
fthh J.- Ps(s)ds = ps((s), s" B3;
h [fpb(s)] = } P(sn E B,)
where the last equality holds by the mean value theorem. Therefore, the bias satisfies
Bias pdf hist
(8) = [+)] ->s(s)
Lis- - S. Lh.
As for variance part, note that the variance of Bernoulli distribution with parameter p is p(1 p).
for 8 B,, we have the variance as follows,
1 1 N 1 D
P(s, E B,)[1 P(sn E B;)]
Varpdj pdf hist(s) (s)
Σ
II(s
I(s BJ)]
h
N
2
n=1
hps(s*) Ps(s*) 2h
Nh
Combining the bias and variance part, we have
hist (s) - h Ps(s*)
MSE hist ( (8) [Biaspal pilf (s))² + V Var paf
(15)
Nh
It is easy to obtain the optimal bandwidth ht- lower than [pa(s")
(Ps(a")
21AN 1 O(N -. and the minimized MSE is
-(N-))
2N
D.2 PROOF OF LEMMA 2
Proof. Note that the local prediction average by histogram, for Bü, is given by mns) I(,,,B,) NN EN (.), Define the normalized weight as w, (s.) Σ I(s,, EB, then local prediction
Ss,,
average is given by nns) = Σ wn (m,)), Similarly, we can obtain the bias and variance tradeoff for local prediction average error MS F / (s) follows,
M MS (s) Ellm" (s) - (s)
+ Em Elm h (s) (s) 2
Blmn (s)] - m(s)
=
Biaetigh (s)
Varbua (+)
For the bias part, based Lipschitz condition the mean prediction function, note that
EN (n((s) 1, we have
Bias
hist (s)
= Blrn (m))
Σ wn (n( - mi(s)]
N
Wn (sn) [mm(s))
m(s)]]
< Σ
wx (8x) = Lh.
(16)
n=1
16

---

Published as a conference paper at ICLR 2022
For the variance part, have variance for local prediction average as follows,
Σ m== I(sn E B.)(K, - m(sn))
V "arriee(s) (s) = B
Wn (n( )nn] = 1E
Im=1I(ssn 1[ E Bi)
I[ E B,)
No o²
(17)
Em I(5n B:))
(N/N2)² Nh
1=1
Combining the bias and variance part, we have
hist hist (8) < 1.2 o² Nh. It is easy to obtain the optimal bandwidth h- BLAN OON +). and the minimized MSE is
MSE (s)
[Bias No (8)] + Var
(18)
lower than
La 3 O(N-3).
2N
D.3 PROOF OF LEMMA 3
Proof. Note that there exists birs-variance tradcoff for M SSEd
kernel (8), i.c.
M SEnd (erne((s)
(s) {=
B[) Ps((s) + - -(pss))
Biast gernall (x)
Var kermat (s)
Next we analyze the bias and variance for probability density function MSE. For the bias part, the expectation of estimated probability density function satisfies:
N
[s] - +s((s) = E
K( 8n
8 (s)
Nh
h
n=
h B[K(
Sn -8)1 (35(s)
h
/
8n <(nn=>)ps(ss
(s)
/ K())ps(s + hy)dy - (s).
(19)
where the last equality holds by adopting transformation = im By Taylor expansion, when small, we have
[s(s + hyy = (s()) + hyp's(s + n²yy Ps(() + olh2)
(20)
Based ob Eqs. 119 and (20) have
Biass pff
(s)
[s) (s)
122 Kly)dy + hpps(s) / yk(y)dy +
2 p'((s) / (2K())d + o(h3) ooh?) ps(s)
ps(s)
1²0
ps);
(21)
2
As for the variance part, we have
N
V Pdf
kernet (s)
D
K( 8n 8 [(]
N1 DDK( 8n -
2 K[K (nn (0]
Nh
K2 8n 8 (pss(ss)dss N /
(" h
1
K (2(y)os(s + hyydy
NR
1
Ps(s)
/ (2(y)d + +(h)
k2(W)bs((s) + hy)'s(() + o(h)]dy
Nh.
Nh
ps())
+ of 1
K
N
(22)
Nh
17

---

Published as a conference paper at ICLR 2022
Combining the bias and variance part, we have
MSE
kernel (s)
[Bias pdf
kernel
[s)]² + V Var Varrey
kernel (s)
h (s)
20
o(h")) + 7
+
4
Nh
O(h')+ 0( N
(23)
Nh
It is easy to obtain that the optimal bandwidth Λ- = O(N 3), and thus, the minimized MSE is lower than O(N-$).
D.4 PROOF OF LEMMA
Recall that the mean prediction conditioned on sensitive attribute is given by m(s) = E| s]. we rewrite prediction as Y mSS) + where is the regression noise and satisfies
Proof.
Eie] = 0 and Elea|s = o Note that the prediction Y =m(s) + [m(() - m()}] e, we
have:
Σ
K
8n
1mn
1
K
8n
)m(s)
1 Nh
Σ
K Sn [m((s)) m(s)]
Nh
h
Nh
h
K( 8n1 - Pn -))en
Nh.
h
n=1
(s( + +m](s) + mm)()))
Based on Eq.
13
we have
mi (s)
ms(s)
m(s) m(s)
(24)
(s()) (s($)
Since Eie[S 0, we have the expectation of E[rr2(s)) since E[K =
E[K("r 6e |E(e s,.ll 0. As for the variance of msz()). we have
[s))
E|K(
Sn 5
)o² (8n)) 2
E
NN
h
h
K("
8n 88 )00 (s.
2h
h
Nh K(y)o + yh)ps(s + yh)ds,
0 (s)ps(s) ol
(25)
Nh
NT
Subsequently, we consider the expectation and variance of mi (s). Specifically, for expectation, have
[()r(ss)
E K 8n -
)
(m((s))m(()) - m(s))]
h
T. / K( h
1
( (m())))m(s)) ps (8n)ds
= / K(y) (mass + hwy) -m(s) ps hy)dy
/ K(y) (hym' (s)
h2h m mmmmm) (s) (ps(s) + hyp'ss)) o(h))dy
= , ( (s))p((s)
+ m mm(ss)ps(s)) + o(h?).
(26)
2
18

---

Published as a conference paper at ICLR 2022
As for the variance of m1 we have
[s)]
D K
on - () - m()))]
Nh2
2h / {x(( 8n (7 (m((s)) - (m(s)))((s))))))mm))))))))) -E/m(ss]} ps ps(sn)dss
h
No [K(y)hym' (1))-B]())]] (ps(s) + phrrs(o)dda (s)) Ps(s) Nh
1
/
+ ol 1 = 0(
)
1
Nh
Combining the bias and variance part, we have
M MS (s) = [Bias reg kernel (s)]² Varker kernel (s) S L2hh² + o² 50(h+)++
01 N (27)
Nh
Based on the inequality of arithmetic and geometric means, is easy to obtain the optimal bandwidth )),
h- = +N) and the minimized MSE is lower than O(N+ #).
E PROOF OF THEOREM 4
Given predictor Ý = f(X), adversary S = g( and adversary utility Lado (3,5) = 1-15 -1S- S). GDP and adversary utility are given by
AGDP Es
- -xxI(xx]]]]]]]]]]]]
Lade Es -
Intuitively. higher model prediction implies larger sensitive attribute if mean prediction function m(s) is more close to s compared with 1 s and vice versa. Therefore, we construct adversary 9 as follows:
f(x), f(x), Otherwise.
Es - m(S) < Es||s - (1 - (s)
# (f(X)) -
Suppose without loss of generality (WLOG) that EsI[S - m[]]]] < Es| - (1 m(S) ie., higher model prediction implies larger sensitive attribute. Then adversary utility given by
Ladv # (f(x)),
Exis [1 - -1s [xx1]]] s Es [1 |s Ex Es
Es 1-
where the inequality holds due to Jensen's 's inequality and convex function - for any constant
t. Next we show, under the constructive adversary 9, the adversarial utility Ladv 2 2 2 AGDP. Firstly, notice that, for any function mSS) E [0, 1] and S E [0, 1]. we have
IS - m(S) - Is (1 m(S))
< max { {11 m(S) + |1 (11-(1-20 (1- (1=)()))|
10 - (1-m(S)]= + 10- - -11 (1- (1-m(s)) = 1,
which implies that
Es 1 Is - mS]]]
2 [E||S m(S]] Es||s - (()m
1
2 Es [|S m()) + |s -(1 (1- -1-- m()))) = 2
1
1
As for the analysis on GDP, we consider the worst case of mean prediction function m(s) since GDP satisfies AGDP = EsI mm() - Es [m]]]]]]] Note that function |x]] is strictly convex and the solution to maximize a strictly convex function over all finite support given first moment is achieved by a distribution of two mass extreme points, GDP can achieve maximal value when m(S) is 0 or 1.
Define Ppos Es P m(S) = })] then [S)] Ppos and AGDP Ppos 1 Ppos)
(1
Ppos) Pyos < 1. Therefore, for the optimal adversary g², we have
Lado (0" ()((()),,)) 5)) > Lado (9 ()) 2 AGDP.
(28)
19

---

Published as a conference paper at ICLR 2022
F DATA STATISTICS
For fair comparision with previous work, we perform the classification and regression task on five datasets, including Crimes, Adult, Pokec-n, Pokec-z and Harris dataset. The first four dataset have been widely adopted to study the fairness problem in tabular data and graph data, while Harris dataset collected by ourself for temporal graph data. Table presents additional information on the real-world tabular, graph and temporal graph datasets. For task type column, "Reg" and "CIf" represents regression task and classification task, respectively.
Table 1: Statistical Information on Datasets
Task Type
# Nodes /Samples
Data Type
Dataset
# Edges
Features
Metric
Crimes
Reg
1994
121
MAE
Tabular
Adult
Clf
45222
13
Pokec-n
Cif
66569
729129
59
GDP
Graph
Pokec-z
Clf
67797
882765
59
Acc
Temporal Graph
Harris
Cif
4204
19946
36
G MORE DETAILS ON SYNTHETIC EXPERIMENTS
G.1 GDP CALCULATION
We firstly provide ground truth analysis in synthetic experiments so that we can evaluate propsoed two GDP estimation methods error. Considering bivariate Gaussian distribution with mean μ
[Mi, U2] and covariance matrix Σ
Jn
012
and note that covariance matrix is positive definite
021
d22
A11
A12
matrix, it is easy to obtain inverse covariance matrix Σ
where A22
and [>0
A21
X22
Au2 512 [
The joint distribution of (S,Y) follows Ps, 1)
exp
(- Au 2
2 A22(s - 22) + \12(s - n22)). Based on probability theory. we can have the condition
function P9)s(111 as follows:
Ps. (s,
1
X22
Aaaio A1gs A12/11
(ū]s)
exp
Ag2
Ps(s)
V
2x
2
Azz
N 01112 2 + 012(s
M1)
Tn
which means the mean prediction function m(s) density function of sensitive attribute is also Guassian with (N, ..). therefore, the GDP is
Notice that the probability
Zu
/ [m(s)= (s)ps(s)ds
AGDP
/ 012 (1)
(s 111)2 ds
2012
exp
0n
2
2011
v V2T0711
Next, we calculate GDP for the second synthetic probability density function (s, 0 < 8, 9 < It is easy to obtain the conditional probability P91s(()s) = st. if < 5 5 .+
and thus the mean prediction function m(s) = E = =s]
$o+
Similarly, the probability of 2+
20

---

Published as a conference paper at ICLR 2022
sensitive attribute is ps(s) +
2 if s. S 1. Thus, the GDP satisfies
|m(s)) - L.¹
2 +
AGDP =
(s
)ds 48
8 2 12
G.2 MORE SYNTHETIC EXPERIMENT RESULTS ON ESTIMATION ERROR
Figure 6 shows local prediction average and sensitive attribute probability density function estima- tion results for different kernel function choice. The top two subfigures show the local prediction average estimation error w.r.t. bandwidth choice. is seen that the tricube and aitchison aitken ker- nel function achieve better and robust local prediction average estimation compared with Gaussian kernel function. The mid subfigures show the local prediction average result for different sensitive attribute and bottom two subfigures shows probability density function estimation results with dif- ferent kernel and histogram choice. It is seen that kernel estimation possesses more smooth and accurate probability density function estimation.
regression
regression error
gaussian
gaussian
tricube
regression rsse
tricube
regression mse
107
aitchison aitken
aitchison aitken
30
10-1
2x10
3x10-24x1011
6x
bandwidth
bandwidth
Local regression
Local regression
2.5
ground truth
gaussian
0.64
Regression
tricube
Regression
1.5
aitchison_aiie aitken
0.60
ground truth
0.0
gaussian
tricube
0.56
-1.0
aitchison aitken
-4
-3
-2
-3
0.6
0.2
0.4
0.6
0.8
1.0
Sensitive attribute
Sensitive attribute
True
gaussian
cosine
linear
exponential
histgram
bandwidth=0.1
b.ndwidth=0.2
bandwidth=0.5
bandwidth=0.1
bandwidth:00
bandwidth=0.5
1.4
1.4
0.35
0.4
1.2
1.2
1.2
0.30
0.4
0.25
0.8
0.20
0.2
0.2
0.15
0.8
0.6
0.8
0.10
0.4
3.05
0.0
0.0
0.00
0.0
0.0
0.3
Sonsitive attrioute
Sensitive attripute
Sonsitive attribute
Sensitive attribute
Sensitive attributt
Figure 6: Local prediction average and sensitive attribute probability density function estimation error analysis with respect to the kernel bandwidth and number of samples for bivariate Gaussian distribution and second synthetic distributions.
21

---

Published as a conference paper at ICLR 2022
G.3 MORE SYNTHETIC EXPERIMENT RESULTS ON ROBUSTNESS
In this subsection, we aim to investigate the robustness of GDP estimation error over different mean and covariance parameters. Note that only the parameters expectation 1 [u,, U2]
[0.5, 1.0]
and covariance matrix Σ [o 012
0.5)
are adopted on synthetic experiments,
012 022
0.5
2.0]
adopt these parameters as default and only modify the one parameter to inspect GDP estimation error. Figures and show the GDP estimation error with mean parameters μl and μ1,, and covari- ance parameters dn, and 022 given the same data size 1000. We have two observations: (1) kernel-based GDP estimation methods consistently achieves lower estimation errors than histogram- based counterpart for any Gaussian distribution parameter, which further validates the superiority of kernel-based method. (2) kernel-based GDP estimation error almost the same for any kernel function pair choice, which validates our theoretical analysis in Theorem,
histogram tri- tri-cos aa lin aa-cos
0.036
GDP error
0.44
0.032
0.632
0.030
0.028
0,028
0.00
0.25
0.50
0.75
1.00
125
1.50
1.75
2.00
0.00
0.25
0.50
0.75
1.00
1.25
1.50
175
2.00
Mean
Mean
Hlz
Figure 7: GDP estimation error for different mean parameters
GDPcror crpor
Figure 8: GDP estimation error for different covariance parameters
H MORE DETAILS ON WORLD EXPERIMENTAL RESULTS
Many real-world data are organized as tabular, graph and temporal graph data. Various machine learning models and training strategy specifically developed for these data types (Chen & Guestrin 2016 Han et al. 2022, Jiang et al. 2022 Zhao et al., 2019). Our experiments demon- strate that the proposed GDP and corresponding regularizer can be adopted for these data types.
H.1 MITIGATION PERFORMANCE FOR TEMPORAL GRAPH DATA
The temporal graph data, provided by data intelligence company Cuebiq (Cuebiq 2021 is col- lected from anonymous human movement activities, including the coordinates and time of mobile devices at stop points, during August 2017 7 in Harris County (Houston) Texas, USA. To generate the temporal graph, we first divide the Harris County into several grid cells with equal size approxi- mately 1km x 1km. Each grid cell is treated as graph node, and temporal link between two nodes represents at least one user movement in hourly basis duration. The node features are generated from deco-apeograpphic data of the American Community Survey (ACS) 2014-2018 (5-year) data by the U.S. Census Bureau (Bureau (02T). the experiment, the white race ratio treated as continuous sensitive attributes and task is predict whether the income of each node is high
22

---

Published as a conference paper at ICLR 2022
low. We adopt temporal graph attention (TGAT) (da Xu et al. 2020 with map and product attention mechanism to efficiently aggregate temporal-topolee topological neighborhood features and report the mean prediction performance and GDP with 5 running times.
We compare the mitigation performance of kernel estimation and other baselines for private Harris dataset with two backbones in Figure 9 Simialrly, the hyper-parameter À control the tradeoff be- tween accuracy and GDP. Again, kernel estimation consistently outperforms the other baselines by a large margin and binary-quantize sensitive attributes inevitably deteriorate the mitigation perfor- mance.
histogram
adv
histogram
adv
67.5
67.5
65.0
65.0
62.5
62.5
60.0
60.0
57.5
57.5
55.0
55.0
52.5
52.5
50.0
0.0
0.2
0.4
0.6
0.8
1.0
1.2
0.0
0.2
0.4
0.6 0.8
1.0
1.2
1.4
GDP
GDP
Map
(b) Prod
Figure 9: Mitigation performance for temporal graph Harris dataset. (a) TGAT with map attention;
(b) TGAT with product attention.
H.2 PREDICTION PERFORMANCE AND GDP TRADEOFF CURVE DURING TRAINING
Training curve on tabular data: Aiming to inspect the dynamic prediction performance and GDP during model training, we provide prediction performance and GDP tradeoff curve for Adult and Crimes dataset in Figure I0, The left and right y-axis represent the prediction performance and GDP metric, respectively. It is seen that, for kernel or histogram as regularization, the hyperparameter can control the prediction performance and GDP tradeoff, while the training is highly unstable with large variance for adversarial debiasing. Additionally, kernel estimation as regularization possesses better bias mitigation performance for Adult and Crimes dataset.
Tuirnig
Tuaeng
202
22-
Figure 10: Prediction performance and GDP training curve for Adult (top) and Crimes (bottom) datasets with different hyperparameters.
Training curve on graph data: Figures and 12 demonstrates prediction performance and GDP tradcoff curve for Pokec-n and Pokec-z datasets using GCN and GAT model. is seen that, for
23

---

Published as a conference paper at ICLR 2022
kernel or histogram regularization, the hyperparameter control the prediction performance and GDP tradeoff, while the training is highly unstable with large variance for adversarial debiasing. Additionally, kernel estimation regularization possesses better bias mitigation performance for Pokec-n and Pokec-z datasets in GCN and GAT model.
progina
300
Figure 11: Prediction performance and GDP training curve for Pokec-n (top) and Pokec-z (bottom) datasets with GAT model.
1002
Traiing DROTE
Figure 12:
Prediction performance and GDP training curve for Pokec-n (top) and Pokec-Z (bottom) datasets with GCN model.
Training curve on temporal graph data: Figure 13 demonstrates prediction performance and GDP tradeoff curve for Harris datasets using TGAT with map and product attention mechanism. It is seen that, for kernel histogram as regularization, the hyperparameter can control the prediction perfor- mance and GDP tradeoff, while the training is highly unstable with large variance for adversarial debiasing. Additionally, kernel estimation as regularization possesses better bias mitigation perfor- mance for TGAT with map and product attention mechanism.
Training curve on compositional sensitive attribute: Figure 14 demonstrates prediction perfor- mance and GDP tradeoff curve for Adult and Crimes dataset. It is seen that, for kernel histogram as regularization, the hyperparameter can control the prediction performance and GDP tradeoff, while the training is highly unstable with large variance for adversarial debiasing. Additionally, ker- nel estimation as regularization possesses better bias mitigation performance for Adult and Crimes dataset.
24

---

Published as a conference paper at ICLR 2022
Inllag Aur.
a0.0
abgardd
Figure 13: Prediction performance and GDP training curve for TGAT with map (top) and product (bottom) attention mechanism with Harris data.
00.30.0
18:
10,30180
20v1812 10 1002
Figure 14:
Prediction performance and GDP training curve for Adult (top) and Crimes (bottom) datasets with compositional attributes.
I FUTURE WORKS
There several interesting future work related proposed GDP: other fairness metries, such as Equal Odds (EO), for continuous and discrete sensitive attributes. The connection between extended fairness metric and adversarial debiasing is also interesting. (2) Provide more fine- grained analysis on estimation error, including the exact optimal bandwidth and estimation error expression, the lower bound of the estimation error for histogram and kernel GDP estimation over all data distribution and model prediction, the estimation error analysis over compositional sensitive attributes. nnvessstee the better GDP estimation method with faster convergence guarantee.
25


Reviews:
[{"review_id": "sxbEkDMb4Fm", "reviewer": "Reviewer_s7Ek", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposes the generalized demographic parity (GDP). It aims to generalize the existing definition of demographic parity (DP) to incorporate continous sensitive attribute while preserving tractable computation. More specifically, GDP is defined as the weighted total variation distance between local prediction average and global prediction average, with the weights being the probability density function (PDF) of sensitive attribute. Based on the definition, histogram estimation and KDE are applied to estimate the distribution of sensitive attribute. In addition, the authors shows that, under certain assumptions, (1) GDP is equivalent to DP; and (2) GDP is the lower bound of adversarial utility by Madras et al. 2018. Experiments on several real-world datasets across different settings demonstrate the effectiveness of the proposed method against baseline methods. However, I have several concerns about this manuscript as shown below. \n\nConcerns\n- The authors claim that GDP is tractable. I wonder how it is tractable if we do not know the joint distribution of prediction and sensitive attribute (as claimed by the first few sentences in Section 4). \n- The proposed method uses histogram/KDE to estimate the distribution of sensitive attribute. Why cannot we use the same techniques (i.e., histogram/KDE) to estimate the distributions needed for calculating mutual information (e.g., joint distribution of prediction and sensitive attribute,  conditional distribution of prediction given sensitive attribute, or conditional distribution of sensitive attribute given predictions)? \n- The experiments are not convincing. (1) The authors established the relationship between GDP and adversarial debiasing by Madras et al. 2018. Why is there no experiments on comparing the performance between these two methods? (2) The paper barely discusses the work Louppe et al. 2017 but includes it as the only debiasing method for comparison. I wonder the justification behind the choice of baseline methods. (3) Mary et al. 2019 also works on debiasing the continuous sensitive attribute, yet there is no comparison. I believe certain justification is needed as well.\n- Some related works are missing (please see below). And I believe some of them should be included as baseline methods as well.\n\nReferences\n\n[Related to fairness with histogram model]\n\n* Kamishima, T., Akaho, S., Asoh, H., & Sakuma, J. (2012, September). Enhancement of the Neutrality in Recommendation. In Decisions@ RecSys (pp. 8-14).\n* Kamishima, T., Akaho, S., Asoh, H., & Sakuma, J. (2013, September). Efficiency Improvement of Neutrality-Enhanced Recommendation. In Decisions@ RecSys (pp. 1-8).\n\n[Related to fairness with KDE]\n\n* Cho, J., Hwang, G., & Suh, C. (2020). A fair classifier using kernel density estimation. Advances in Neural Information Processing Systems, 33, 15088-15099.\n\n[Related to fairness with mutual information]\n\n* Cho, J., Hwang, G., & Suh, C. (2020, June). A fair classifier using mutual information. In 2020 IEEE International Symposium on Information Theory (ISIT) (pp. 2521-2526). IEEE.\n* Roh, Y., Lee, K., Whang, S., & Suh, C. (2020, November). Fr-train: A mutual information-based approach to fair and robust training. In International Conference on Machine Learning (pp. 8147-8157). PMLR.\n* Lowy, A., Pavan, R., Baharlouei, S., Razaviyayn, M., & Beirami, A. (2021). FERMI: Fair Empirical Risk Minimization via Exponential R\\'enyi Mutual Information. arXiv preprint arXiv:2102.12586.", "summary_of_the_paper": "Please see main review.", "summary_of_the_review": "Overall, this paper is a bit unclear in some parts and lacks a thorough literature review. The experiments are not convincing enough as well. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hBNAlgJulqu", "reviewer": "Reviewer_zy7G", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\n1. The GDP is a generic fairness metric for both continuous and discrete protected attributes.\n2. The histogram and kernel estimations are computationally feasible. The error and complexity analysis of the two estimations show improvement.\n3. The connection of GDP and adversarial debiasing is built.\n4. The comprehensive experiments on multiple datasets show the efficiency and effectiveness of the kernel estimation of GDP.\n\nWeakness:\n\n1. There is a gap between the estimation of GDP and adversarial debiasing. Vanilla GDP relies on an unknown distribution which prevents its application. If the estimation is applied, it is unclear the relationship between $\\hat{GDP}$ and the adversary utility.\n2. It is unclear how to calculate the underlying GDP in the experiments, or it is just an estimation of GDP. Please clarify.\n", "summary_of_the_paper": "This paper proposes a generalized demographic parity for group fairness which is computationally feasible for both continuous and discrete protected attributes. Two estimations, histogram and kernel, are proposed for efficient estimation and the kernel estimation has faster estimation error governance. The connection between the GDP regularization and adversarial debiasing is built. The experiments on syntehtic/tabular/graph datasets show the effectiveness and efficiency of the GDP kernel estimation.", "summary_of_the_review": "This paper provides a generic fairness metric for both continuous and discrete protected attributes in various tasks. The kernel estimation has good error and complexity properties. The experimental comparison is comprehensive and well designed. \n\nThe connection between GDP and binary demographic parity is built, but I wonder about the relationship between GDP and discrete protected attributes with multiple values, e.g., intersectional fairness. The extension from binary to multiple to continuous would be more smooth.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "eapvNKskPjH", "reviewer": "Reviewer_Lp8E", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Comments:\nSection 1: Age is not a particularly successful example of a continuous attribute. A better example might be income differences (although it is not always legally protected, it is definitely of interest to decision-makers).\n\nSection 3: The definition of GDP is precise and relatively natural. However, some justification of this particular choice is necessary. What are potential other definitions? Why is this definition the most natural (and technically sound) extension of the categorical definition? Explaining in simple terms would help provide intuition for the reader. \n\nI think the theoretical foundations are a nice contribution of the paper. I would appreciate a proof sketch or intuition after each theorem. \n\nAlthough I understand that this might be part of follow-up work, I think it is important to include a discussion on how other metrics can be similarly extended to capture continuous attributes. Demographic parity is a natural first step, though.\n\nSection 6.1: why were these parameters chosen? Have robustness checks been performed and what were the results?\n", "summary_of_the_paper": "The paper is motivated by the need to account for continuous attributes in fair Machine Learning. In particular, it proposes a Generalized Demographic Parity metric (GDP), i.e., a group fairness metric that can work with both continuous and discrete variables. A key challenge in doing so is preserving tractable computation. \n\nTheoretically, GDP is defined via the weighted total variation distance and measures the distance between the local and global prediction average, where the weight corresponds to the pdf of the continuous sensitive attributes. Since the joint distribution between model prediction and sensitive attributes might not be available in practice, the paper also proposes two estimation methods: histogram estimation and kernel estimation. The former quantizes the continuous sensitive attributes into bins, whereas in the latter method the group indicator of the sample is treated as a kernel function. The kernel method leads to faster estimation error convergence rate in terms of sample size.\nThe paper provides an extensive evaluation with tabular, graph and temporal graph data, synthetic experiments, and classification and regression tasks. It is demonstrated experimentally that the kernel method has better bias mitigation performance.\n\n", "summary_of_the_review": "\nIn my opinion, the paper touches upon a very important and practical topic in fair ML. Not all attributes are categorical and privacy concerns might require fairness in a neighborhood or region of attributes. Thus, accounting for continuous variables in fairness definitions is crucial in many practical contexts.\n\nThe paper is methodologically sound. It provides a quite extensive theoretical justification and guarantees as well as a complete and convincing empirical evaluation with several datasets. It is well written and has the potential to lead to follow up work (both in terms of other definitions and also inspiring research on continuous attributes in fair ML). \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "H_c4Sbp-cFW", "reviewer": "Reviewer_dM4B", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper is well-written and easy to follow. I like the structure of this paper: it starts with a new definition for measuring fairness; introduces ways to estimate this fairness measure; and presents applications of this measure. However, my main concern is the technical novelty of this paper (see my detailed comments listed below). \n\n1. My main concern is the estimation error bound provided in Theorem 3. It seems that this result relies on a strong assumption (i.e., the prediction function is Lipschitz continuous w.r.t. the sensitive attribute) and it is unclear to me the order presented in this theorem is optimal. \n\n(1) [Strong assumption.] It is very hard for me to come up with a scenario where the Lipschitz condition is satisfied and the Lipschitz constant is small. Note that the Lipschitz constant will affect the optimal bandwidth choice and, potentially, the sample complexity. It would be great if the authors can provide an example to show that this Lipschitz condition is inevitable. \n\n(2) [Optimal order.] The order of estimation error given in Theorem 3 is O(N^{-4/5}). However, it is unclear to me if this is the optimal order. Can the authors derive some converse results to prove that this order cannot be improved anymore?\n\n2. [Intersectionality.] The authors only consider a single sensitive attribute. What if there are multiple sensitive attributes (e.g., age, weight, income, …). How does the number of sensitive attributes affect the estimation error bound in Theorem 3? Does the bound suffer from the curse of dimensionality in this case?\n\n3. The authors wrote in Theorem 3 “Under the optimal bandwidth choice, …”. Can the authors specify what the optimal bandwidth is?\n\n4. Can the authors include an error bar for each figure in the paper? ", "summary_of_the_paper": "This paper proposes a new extension of demographic parity when the sensitive attribute is continuous. It proposes two techniques to estimate this quantity from data. The authors also consider adding this quantity as a regularization term to control discrimination while designing machine learning models.", "summary_of_the_review": "The paper is interesting but the technical novelty may not be sufficient", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper offers an alternative formulation of demographic parity, named GDP, which makes it amenable to easier computation when the sensitive attribute is continuous. Analytically, the paper relates GDP to other notions, offers ways to estimate GDP from data, and establishes the convergence of these estimators. Experimentally, the paper adds the estimated GDP as a learning regularizer and establishes the accuracy-fairness tradeoff that results by using this method versus others.

The need to handle continuous sensitive attributes is well-motivated since they are ubiquitous. The direction of the paper is thus very pertinent. The experimental exploration of the paper is also strong, though reviewers initially raised questions of clarity of the relationship of GDP with adversarial debiasing. These are mostly addressed by the authors. One weakness of the paper that largely remains is whether the paper offers new conceptual insights. Indeed, demographic parity is simply a notion of independence between an algorithm’s output and sensitive attributes. Other independence metrics are dismissed in the paper as unreliable to compute. However, one reviewer correctly raises the concern that *under similar regularity conditions* to the ones establishing the convergence of the kernel GDP estimator, it is also possible to establish convergence of other independence metrics, that would equally capture demographic parity. Another reviewer also points out that such convergence would follow using standard non-parametric statistics techniques. Smoothed estimators of mutual-information are indeed available in the literature, with convergence guarantees even in the high-dimensional regime. The authors do not satisfactorily address this, casting doubt on the overall significance of the contribution.

That said, given the strong motivation behind the paper and the overall promise of the methodology, it may be worth sharing with the community. The authors are urged to address the above. Additionally, they are urged to be transparent about what the theory offers and what it doesn’t. For instance, the convergence results of GDP only tell us that we can use these estimators to audit the fairness of existing models. In other words, although the paper is touted as showing that GDP can be successfully used for learning, the evidence there is purely empirical: there is no learning guarantee simultaneously on the accuracy and fairness of GDP-penalized risk minimization.
Decision: Accept (Poster)