Understanding Fairness Surrogate Functions in Algorithmic Fairness
Authors: Wei Yao
Zhanke Zhou
Zhicong Li
Bo Han
Yong Liu
Venue: Accepted by TMLR ()

Abstract: It has been observed that machine learning algorithms exhibit biased predictions against certain population groups. To mitigate such bias while achieving comparable accuracy, a promising approach is to introduce surrogate functions of the concerned fairness definition and solve a constrained optimization problem. However, it is intriguing in previous work that such fairness surrogate functions may yield unfair results and high instability. In this work, in order to deeply understand them, taking a widely used fairness definition—demographic parity as an example, we show that there is a surrogate-fairness gap between the fairness definition and the fairness surrogate function. Also, the theoretical analysis and experimental results about the “gap” motivate us that the fairness and stability will be affected by the points far from the decision boundary, which is the large margin points issue investigated in this paper. To address it, we propose the general sigmoid surrogate to simultaneously reduce both the surrogate-fairness gap and the variance, and offer a rigorous fairness and stability upper bound. Interestingly, the theory also provides insights into two important issues that deal with the large margin points as well as obtaining a more balanced dataset are beneficial to fairness and stability. Furthermore, we elaborate a novel and general algorithm called Balanced Surrogate, which iteratively reduces the “gap” to mitigate unfairness. Finally, we provide empirical evidence showing that our methods consistently improve fairness and stability while maintaining accuracy comparable to the baselines in three real-world datasets.

Published in Transactions on Machine Learning Research (04/2024)
Understanding Fairness Surrogate Functions in Algorithmic Fairness
Wei Yao
wei, Fer.gyo@@ru.edd
Gooling School of Artificial Intelligence
Renmin Universily of China, Beijing
Beijing Key Laboralory of Big Dota Management and Analysis Methods, Beijing
Zhanke Zhou
cszkzhoon&compp.hbbuu. edu.
TMLR Group, Department of Computer Science Hong Kong Baptist University
Zhicong Li
Chicongli@ruc.etuu.rr
Gooling School of Artificial Intelligence Renmin University of China, Beijöng Beijing Key Laboratory of Big Dota Management and Analysis Methods, Beifing
Bo Han
bhanml@comp..kbu. edu.hk
TMLR Group, Department of Computer Science Hong Kong Baptist University
Yong Liu
Hugonnggaitrruc.etu.co
Gooling School of Artificial Intelligence Renmin Universily of China, Beijing
Beijöng Key Laboralory of Big Dala Management and Analysis Methods, Beijing
Reviewed on OpenReview: https://openvroiee.nee//// or wtw. Tlaz
Abstract
has been observed that machine learning algorithms exhibit biased predictions against certain population groups. To mitigate such bias while achieving comparable accuracy, promising approach is to introduce surrogate funetions of the concerned fairness definition and solve constrained optimization problem. However, is intriguing in previous work that such fairness surrogate functions may yield unfair results and high instability. In this work, in order to deeply understand them, taking a widely used fairness defnition-demmorraae demographic parity as an example, we show that there is a perrogate-fairees gap between the fairness definition and the fairness surrogate function. Also, the theoretical analysis and experimental results about the "gap" motivale us that the fairness and stability will alfected by the points far from the decision boundary, which is the large margin points issue investigated in this paper. To address it, we propose the general sigmoid surrogate simultancously reduce both the surrogale-fairness gap and the variance, and offer rigorous fairness and stability upper bound. Interestingly, the theory also provides insights into two important issues that deal with the large margin points as well as obtaining a more balanced dataset are beneficial to fairness and stability. Furthermore, we elaborate a novel and general algorithm called Balanced Surrogate, which iteratively reduces the "gap" mitigate unfairness. Finally, we provide empirical evidence showing that our methods consistently improve fairness and stability while maintaining accuracy comparable to the baselines in three wealwworld datascts.
indicates equal contribution. indicates the corresponding author.

---

Published in Transactions on Machine Learning Research (04/2024)
Sigmoid
1.75
Sigmoid
2.5
Hinge
Hinge
Log Sigmoid
1,50
Log Sigmoid
2.0
Covariance Proxy
Covariance Proxy
Ours: General Sigmold
1.25
Ours: General Sigmoid
1.5
Indicator
Indicator
1.00
1.0
0.75
0.50
0.0
0.25
0.00
-0.5
-3 -2
-1
2
-3
-2
0
(a) Surrogate Punctions
(b) Surrogate-Fairee Gap
Figure 1: (a) Some examples of fairness surrogate functions. The closer the surrogtte functions are to the in- dicator function, the better they represent DP. More details are introduced in Scction 3.2. (b) The surrogate- lairness gap of different surrogate functions. It measures the difference ween surrogate funcciins and the indicator function. There is much smaller gap for our general sigmoid surrogate.
1 Introduction
Recently, increasing attention has been paid to the fairness issue in supervised machine learning. That is, although the classifiers seek higher accuracy, some groups with certain sensitive features (e.g., sex, age) may be unfairly treated, which raises ethical problems (Julia Angwin & Kirchner, 2016; Mchrabi et al., 2021; Caton & Haas, 2020). One can be litigated for committing adverse impacts his/her decision-making process disproportionatel treats groups with sensitive attributes (Barocas & Selbst, 2016).
To quantitatively measure the extent fairness violation, a usual way adopting the fairness definition, demographic parity (DP), which requires the decision makers to accept roughly equal proportion of each group (Barocas et al., 2019). Existing methods follow the fairness-aware manner of solving constrained optimization problem, where the learning objective is integrated with the standard loss and fairness con- straint. To incorporate DP into the constraint, fairness surrogate functions are used to replace the indicator function, which is intractable for gradient- based algorithms (Lohaus et al., 2020; Bendekgey & Sudderth, 2021) (refer to Figure 1(a) for some examples). To date, various surrogate functions have been proposed to incorporate fairness definitions inlo constraints (Wu et al., 2019; Goh et al., 2016; Padh et. al., 2021; Zafar et al., b;;7a;b;e; Bendekgey & Sudderth, 2021). They are widely applied in various machine learning do- mains, such differential privacy (Ding et al., 2020), meta-learning (Zhao et al., 2020), and semi-supervised learning (Zhang et al., 2020). Unfortunately, these surrogate functions encounter two risks. One risk is that if these fairness constraints are used, even when the constraints are perfectly satisfied, there is no guarantee whether DP is satisfied (Lohaus et al., 2020). And the fairness surrogate functions may lead to even unfair solutions (Radovanović et al., 2022). Moreover, another risk arises from the high variance issue observed in existing fairness-aware algorithms with surrogate functions (Friedler et al., 2019), rendering them unstable for deployment under fairness requirements (Ganesh et al., 2023).
In this paper, evaluate these multifarious surrogate functions in algorithmic fairness with both rigorous theorems and extensive experiments. Firstly, stress the importance of the Suurrogate-fairnsss gap", which is the disperity between the fairness surrogate function and the fairness definition. It is the decisive factor of whether the fairness surrogale function can lead to fair outcomes and should be minimized. Addi- tionally, we delve into the variance of the substitute for DP, highlighting the adverse impact of unbounded surrogates on stability. Drawing upon the inherent property of the surrogate-fairnes gap and instability, we conduct an in-depth examination of the large margin points issue within the context of unbounded surrogate functions. To reduce the "gap", propose two solutions to improve the existing surrogate func-
2

---

Published in Transactions on Machine Learning Research (04/2024)
tions: theoretically motivated fairness surrogate function named general sigmoid with upper bounds of the violation of DP, and novel algorithı called the balanced surrogale to iteratively reduce the gap during training.
Our analysis is general for fairness surrogate functions in the case of a common fairness definitio, DP. Additionally, we employ a widely recognized covariance proxy (Zafar et al., 2017c) as an illustrative instance of fairness surrogate function. In particular, we first derive the violation of DP for the fairness surrogate functions in Section 4. The violation of DP depends on two factors: the surrogate function itself and the surrogate- fairness gap. The "gap" (shown in Figure 1(b)) directly determines whether surrogate function is an appropriate substitute for DP. Secondly, we explore the variance of the surrogate function in Section 4.1, emphasizing the detrimental impact of unbounded surrogates on stability. Furthermore, driven by the "gap" and variance, we recognize that large margin points- those data points lying significantly distant from the decision houndary-posse challenges functions. This observation is validatod through a case study on three real-world datasets in Section 4.2. With Cheoretical motivations, we introduce the general sigmoid surrogale in Section 5.1 to address large margin points and simultaneously bound the "gap" and variance. We theoretically demonstrate that there is reliable fairness and stability guarantee for it. Interestingly, the theorems also shed light on the importance of a balanced dataset for both fairness and stability. Furthermore, in Section 5.2, we propose balanced surrogates, a novel and general algorithm that iteratively reduces the "gap" to improve fairness. It is a plug-and-play learning paradigm for the naive aware training framework using fairness surrogate functions. In the experiments in Section 6 using three real-world datasets, our methods generally enhance fair predictions and stability, while maintaining accuracy comparable to the baselines. Overall, our main contributions are throc-fold:
constraining the fairness and stability for unbounded surrogate
We demonstrate the importance of Surrogate-farreess Gap for fairness surrogate functions and pro- vide an analysis of the variance. We emphasize the importance for researchers to consider the impact of the large margin points issue on the fairness and stability of unbounded suroggte functions.
We propose General Sigmoid Surrogate and demonstrate that it achieves fairness and stability guar- antees. The theoretical results further provide insights to the community that large margin points issue needs be solved and balanced dataset is beneficial to obtain fairer and more stable classifier.
We present Balanced Surrogate, a novel and general method that iteratively reduces the "gap" to improve the fairness of any fairness surrogate functions.
2 Related Work
Fairness-aware Algorithms. To mitigate bias, there are various kinds of classical fair algorithmss, most of which fall into three categories: pre-processing, in-processing, and post-processing. The pro-processing method is to learn fair representation that tries to remove information correlated to the sensitive feature while preserving other information for training, e.g., (Calders et al., 2009; Kamiran & Calders, 2011; Zemel et al., 2013; Feldman et al., 2015; Calmon et al., 2017). The downstream tasks then use the fair representation instcad of the original biased dataset. The post-processing mothod is to modify the prediction results to satisly the fairness definition, e.g., (Kamiran et al., 2012; Fish el al., 2016; Hardt et al., 2016). The in- processing method is to remove unfairness during training. Some intuitive and easy-to-use ideas involve applying fairness constraints (Goh et al., 2016; Zafar et al., 2017a;b;c; Bechavod & Ligett, 2017; Wu et al., 2019; Bendekgey & Sudderth, 2021; Padh et al., 2021) and adding a regularization term to penalize unfairness (Kamishima et al., 2012; Berk et al., 2017; Agarwal et al., 2018; Lohaus et al., 2020; Shui et al., 2022b). Refer to Appendix C.1 for other fairness- aware in in-processing approaches. Our paper focuses on in-processing methods, with a particular emphasis on fairness surrogate functions, which are widely used in fairness constraints and fairness regularization methods mentioned above.
Fairness Surrogate Functions. Although many existing popular surrogates work well in practice, for example, linear (Donini et al., 2018; Agarwal et al., 2018; Bechavod & Ligett, 2017), ramp (Goh et al.,
3

---

Published in Transactions on Machine Learning Research (04/2024)
2016; Zafar et al., 2017b), convex-concave (Zafar et al., 2017a), hinge (Wu et al., 2019), sigmoid and log- sigmoid (Bendekgey & Sudderth, 2021). They suffer from the same issue: there is not fairness guarantee for them (Lohaus et al., 2020). And using fairness constraints or regularization can unxpectedly yield unfair solutions (Radovanović et al., 2022). Refer to Appendix C.2 for a meticulous overview of existing works, most of which present counterexamples for analysis. The high variance issue has been observed existing fairness-aware algorithms (Ganesh et al., 2023), including the instability of the covariance proxy (Friedler et al., 2019). In this paper, in addition to empirically showing counter-examples, we both theoretically and empirically underscore the significance of the surrogate- fairness gap and variance, which are fundamental factors contributing to the two aforementioned problems, respectively. Our general sigmoid surrogate is shown to deal with the large margin points to simultaneously reduce both the surrogate- gap and the variance. There is also fairness and stability upper bound for it, which is crucial in this field (Gallegos el al., 2023; Mehrabi et al., 2021; Caton & Haas, 2020). Additionally, in order to reduce the gap, we also devise a balanced surrogate approach further improve the fairness and stability of surrogate functions, which may deserve a deeper exploration in this field for future work.
3 Preliminaries
3.1
Fairness-aware Classification
Note the general purpose of fairness-aware classification is to find classifier with minimal accuracy loss while satisfying certain fairness constraints. For simplicity, we set up the problem the binary classification task with only a binary-sensitive feature: with the training set S= (xx, M)) consisting of feature vectors x; E Rd and the corresponding class labels Y E {0,1}, one needs to predict the labels of a test set. Let (x) denotes the signed distance between the feature vector x and the decision boundary parameterized by 0. Given point x; in the test sct, a classifier will prodict it as positive if do (x;) > and zero if dg dg(x;) S 0. Among the features of x, there one binary sensitive attribute = E [-1,+11 (e.g., sex, race, age).
As introduced in Section 1, widely used fairness definition is called the demographic parity (DP) (Mehrabi et al., 2021; Caton & Haas, 2020). It states that each protected class should receive the positive outcome at equal rales, i.e.,
((dx(x) > 0/2 = +1) = (x) > 0/2 = -1).
And further, the difference of demographic parity (DDP) metric (Lohaus et al., 2020) can be used to measure the degree to which demographic parity is violated:
DDP (x) > 0|= = +1) P(do(x) 0|z --1.
Then, with this metric, whether a classifier satisfies demographic parity can be determined by the condition DDP| & e, where e 2 0 is a given threshold.
3.2 Surrogate Functions
We divide the training set into four classes according to the predicted labels and sensitive features:
Ni. {(x; u) E S do (x,) 0, 24 +1},
Ni. {(x;, v:) S dx(xx) > 0, = -1],
No.- = ((x;, E S da (x,) - 0, = +1},
No. (xx,, E S dg (x;) S 0, = -1}.
where N1a, N16, Noa: Nos are sizes of Naa respectively. To consider DDP as fairness constraints for optimization, the probability in it cannol be computed directly, so frequency is used to estimate them:
Nia
N1
DDPs
Nia Noo E(xa))Nii Ado(x)>0 EixsnENNuNNo Ido(x)>0 No Nob
No Nos
Nia + Noa
where 11: : - (0, 1) is the indicator function that returns 1 if the condition is true and 0 otherwise.
4

---

Published in Transactions on Machine Learning Research (04/2024)
In application, DDPs usually serves as substitute for DDP to judge the fairness of classifier. However; due to (d)())> intractable to directly incorporate DDPs into constraints for gradient gradient-based algorithms. So smooth surrogate function R is used to replace 1a(())0 with ((dg(x)))
(DPs( = Lixmeen (d)(())
E(xnjeNiuNo ((do(x))
(2)
Nia + Noa
Ni8 + Non
Then DDPs(1) can be incorporated into constraints as (DPs(d) S 6, where is the threshold. In this way, the fairness-awan aware classification problem becomes a feasible constrained optimization problem.
One popular fairness surrogate function is covariance prozy (CP), which is introduced by (Zafar et al., 2017c). Empirical study shows that CP can reflect the difference of demographic parity and can be incorporated constraints for fairness-aware classification problem (Ding et al., 2020; Zhao et al., 2020; Zhang et al., 2020). We defined a general version it as
1 Σ (4 z))(d)(x))). 1=1
(ous(Ø)
(3)
where 2 is the mean of z over the training set. If 6(z)= z, the equation (3) recovers the original definition of CP in (Zafar et al., 2017c). Also, (D) Cous(ø) and the proof can be found in Appendix A.1. It means that the original CP is equivalent to the linear surrogale function xxx) 2, which is also explained in previous work (Lohaus et al., 2020; Bendekgey & Sudderth, 2021). We provide theoretical results for DDPs(o) the main paper, and extend them to Cous(o) in Appendix A.2 with the same conclusions.
4 The Surrogate Gap
We first emphasize the importance of surrogate-fairness gap, and then point out two issues: instability (Section 4.1) and large margin points (Section 4.2), which may influence the surrogale-fairnest gap.
Firstly, we connect DDPs and DDPs(0) together, and build the surrogate- fairness gap between them. Proposition 1. Define the magnitude of the signed distance by Do(x), i.e., Do(x) = [x)(x)]- It satisfies:
DDPs HDPS-DDPSCC Eixm)eNiuUNa [Adoi))>0 ((dis))o-((d((x)))) (dd(()))
E(xiieN [ddo())0 - ((ds (4)
Nia + Noa
NI + Nos
surrogate- fairness gap
There is furrogate-firress gap between DDPs s and DDPs(0) For DDPs(0), it can serve as fairness constraint or regularization in the algorithm. The algorithm will automatically find a solution that penalizes large (o)) Unfortunately, it is different for the "gap", which comes from the inherent difference be- tween the indicator function and the fairness surrogate function. For the ideal case o(z) 1x>0, which means that (x)) 11 (x)>>>> the gap is wero and reducing the constraint or regularization term DDPs(0)
is equivalent to reducing DDPs). However, for any surrogate function o, the gap will be inevitably intro- duced unless Φ(x) 1. When the surrogate-fainees gap is small enough, there is fairness guarantee for the classifier. In practice, Figure 1(b) shows the surrogale-fairness gap of different fairness surrogate func- tions, including CP (which equivalent to linear surrogate function) (Zafar et al., 2017c), hinge (Wu et al., 2019), log-sigmoid as well sigmoid (Bendekgey Sudderth, 2021), and our general sigmoid surrogate. It suggests that unbounded surrogate functions tend exhibit a larger parogaaoo-airnees gap. The bounded surrogate functions, such sigmoid and general sigmoid, both exhibit bounded "gap".
5

---

Published in Transactions on Machine Learning Research (04/2024)
4.1 Instability
The variance of DDPs (0) is Var (DDPs(0) F. (DDPs(()) - (DDPss (0)) [R(DDP
)} If choose bounded
surrogate <(x) E [0, then (0) |-1, 11, which means that Var (DDPs(o)) s(()) [0, 1]. Therefore,
there an stability guarantee for DDPs(6) if o(x) E =[0,1]. However, if we choose unbounded surrogate function (such as <(xx) = x E [-o0, +oo| for the original CP), the resulting values of Φ(z) are not constrained within the range [0, 1]. Therefore, we cannot conclude that DDP E [-1, Consequently, we also cannot conclude that Var (DDPs(0)) E 10. As a result, there is no longer a stability guarantee for D(Ps(
To summarize the aforementioned problems, incorporating DDPs(0) into fairness regularization and con- straints to indirectly minimize DDPs may encounter difficulties for two reasons. Firstly, due to the existence of the surrogate-fairnes gap, minimizing (DPs(() is not equivalent to minimizing DDPs. Secondly, if un- bounded surrogate functions are employed, the uncontrollable variance of DDPs(() makes it even more challenging to be an appropriate estimator of DDPs
4.2 The Large Margin Points
In this section, we emphasize the trouble of large margin points, which may influence the surrogate-fairnes gap. In this paper, the points with too large Dx(x) are called large margin points and others are normal points. Unfortunately, we regret to assert that these large margin points may simultancously worsen the first two issues mentioned above. To illustrate, we take CP (linear surrogate <(x) x) as an example. For three famous real-world data sets, Adult (Kohavi, 1996), COMPAS (Julia Angwin & Kirchner, 2016) and Bank Marketing (S. Moro & Rita, 2014), provide the boxplot of dx(x) in the test set in Figure 2. The experimental details are in Appendix B.2. There are three main observations in Figure 2: (i) Most of the points are near the decision boundary. (ii) Over 5% points are large margin points for Adult and COMPAS. (ini) Almost all the large margin points are predicted as positive class.
Firstly, for the surrogate-fainen fairness gap problem, the gap in Equation (1) may be amplified in the presence of such large margin points. For example, Figure 2 shows that most of the large margin points are predicted positive, so there is not tight bound for E(.,)) do(x) and Σ Exx,))eA, do(x). Also, Figure suggests that the points with negative prediction exhibit a relatively smaller dg (x)) comparing to those points with positive prediction. Thus, E(x.)eNG. dx(x) and E(KW)NNG dx(x) bounded (for instance, In Figure 2(b),
we have E(x:))ENo. do(x)] I 2No.). Therefore, there is still not a tight bound for Exxx))eN de(x) and Mix.iieNiLLVin dx)), which may load to a large surrogate-fairnss gap in Equation (1). Finally, the surrogate- surrogate-lairness lairness gap becomes large, constraining the fairness surrogate function is inconsistent with the specific fairness definition, which may lead to unfair result.
Secondly, regarding the instability issue, while the majority of points are close to the decision boundary, small number of large margin points contribute to the increased variance of do(x), thereby influencing both DDPs(0) and Var (DDPs()). The presence of large margin points, along with the use of an unbounded surrogate function, surpasses the constraint on Var (DDPs()) and may result in unstable fairness guidance for the classifier. These analytical insights above will be further validated through our experiments.
5 Our Approach
We devise the general sigmoid surrogate function with fairness and stability guarantees in Section 5.1. The thcory suggests that addressing the large margin points issue and obtaining a more balancod datasct contribute to fairer classifier. Then we present our balanced surrogates in Section 5.2, which a novel iterative approach to reduce the "gap" and thus improving fairness.
6

---

Published in Transactions on Machine Learning Research (04/2024)
10
Signed Distance
Signed Destancs
Signed Distancs
10
-10
+160
-16u]
+160
-1/6
+100
+6)
1661
+10)
Hull
+
116)
Predicted Label
Predicted Label
Predicted Label
(a) Adult.
(b) COMPAS.
(c) Bank.
Figure 2: The boxplot for the unconstrained logistic classifier (u) and logistic classifier with fairness con- straints using linear surrogate (c) in three datasets. +1 and -1 represent the predicted label. The red dashed line means dø dx(x)
The orange line in the box is the median. The circles outside the box are large margin points. The rates of large margin points are 7.61%, 5.12% and 0.82% respectively.
5.1 General Sigmoid Surrogates
We generalize sigmoid function as
G(z) = =(wz).
(5)
where (x) is the sigmoid function and > is the parameter. The general sigmoid surrogate is flexible because of the adjustable w. Moreover, of paramount importance, it achieves a much lower surrogate-fairnes gap, making it more consistent with DP, which is shown in Figure 1(b). Additionally, it enjoys stability guarantees as values fall within the range [0, 1], ensuring that Var (DDPs(G)) e [0,1].
5.1.1 Fairmess Guarantees
The following Theorem provides the upper bound DDPs when G(Do(x)) is close to for all the points under the DDPs(() fairness constraint.
Theorem 1. We assume that GxD)(x)) E [11-9: y, 1], where 7> 7.0. 0. Vc > 0, of DDPs(G) S c, then it holds:
1 DDPs s 5 +7
(6)
The proof can be found in Appendix A.3. The first term similar to that in (4). Now with the assumption G(Ds(x)) E [1 - 7, 1], the gap here can be limited to a small range of variation. the general sigmoid surrogates limit (x)) to around so that y small enough, then there are fairness guarantees for the classifier. In contrast, the gap for CP influenced by the magnitude of Dx(x) for every large margin point and thus hard to be bounded.
Remark. In Appendir D.2, considering CP, provide extensions of Theorem to other five fairness definitions: three kinds of disporate mistrentment (Theorem 5-10 in Appendir D.2) and balance for positive (negative) class (Theorem 11-12 in Appendir D.4). In particular, CP is generalized to disparate mistreatment (Zafur et al., 2017a), and we theorelically devise the form of CP to beller meet with disparate mistrealment, which is empirically validated in (Zafar et al., 2019).
However, in some cases, we do need to guarantee that the assumption G()) E 1 - -,, 1] holds for all the points. So the theorem below relaxes the assumption by giving the upper bound of DDPs when most of the points satisfy the assumption in Theorem 1.
Theorem 2. We assume that ls points satisfy G(Do(x)) 10,1->] and others satisfy G(D,(x)) [1-7,1]
where > 0. Ve > 0, is [DPs(G) < then il holds:

---

Published in Transactions on Machine Learning Research (04/2024)
1 DDPs S z
Nia + Noa +
k.
No6 Nob
relazation factor
The proof can found in Appendix A.4. Comparing Theorem with Theorem 2, the relaxation of the assumption produces an extra relaxation factor. According to Theorem 1, if w is large, then y can be small enough, thus leading to classifier with fairness guarantee. But an arbitrarily too large makes training more challenging because of the diminished gradient magnitude for general sigmoid surrogate. Theorem 2 tells us that we need not to assume that all points satisfy G(D,(x)) E [1 7. 1]. Few points violating the assumption (a small k) can also be tolerated. So it supports the idea that we do not have to choose large w because a relatively small w can also guarantec fairness.
5.1.2 Insights from the Theorems
Large Margin Points Issue. An obvious takeaway of Theorem 2 is that addressing the large margin points issue makes k lower and thus obtaining a tighter bound of DDPs While Bendckgey Sudderth (2021) also explores the influence of outliers on the model under fairness constraints, their theoretical analysis in primarily centers on loss degeneracy under fairness constraints, whereas paper aims to establish upper bounds concerning fairness.
Balanced Dataset. Another interesting take-away of Theorem 1-2 is that we need a balanced dataset to obtain a fairer classifier. The approximately same number between two sensitive groups contributes to a tighter DDPs upper bound. First of all, for Theorem the coefficient of satisfies No. The equality holds if and only if Ni. + No. = Ni. + No., which means that the two sensitive groups share the equal sizo. Therefore, a more balanced dataset will obtaín a tighter DDPs upper bound. Similarly, comparing to Theorem 1, discover that those k points in Theorem 2 relaxed the original bound by a relaxation factor. The coefficient. of the relaxation factor 3 Nia+No + Ni++Nos 2 2, and the equality holds if and only if N1a + Nu. N1s + Nus. So, if we use a balanced dataset, then N1a + Noa and N1s + Nos are close to each other, thus making the fairness bounded tighter. The imbalance issue also applies to other surrogates and one can balance the dataset in advance to achieve better fairness performance.
N²
1.
N
N
Notably, certain theoretical investigations illuminate the positive impact of balanced dataset on fostering fairness in machine learning. For example, the impossibility theorem (Bell et al., 2023) in fairness literature states that, in the context of binary classification, equalizing some specific set of multiple common perfor- mance metrics between protected classes impossible, except in two special cases: a perfect predictor and equal base rate (Chouldechova, 2017; Kleinberg et al., 2017: Pleiss et al., 2017). Furthermore, the reduction of variation in group base rates has been demonstrated to yield diminished lower bound for separation gap and independence gap (Liu et al., 2019). Moreover, minimizing the difference in base rales results in a decreased lower bound for joint eтror across both sensitive groups (Zhao & Gordon, 2022). In contrast, our Theorem 2 provides an elucidation from the perspective of upper bound. It implies that a more balanced datasot results in a tighter upper bound on the violation of DP.
Remark. In Appendir A.6, Theorem 4 shows that Var (DDPs) S ( No n.). Therefore, it also high- lights the advantage of balanced dataset in reducing variance.
5.2 Balanced Surrogates
The naive fairnoss-aware training framework can be formulated as
min L(0, x, v) + p DDPs(0), where L(0,x,1) = Exxyess ((0,x, x0) is the empirical loss over the training set, f is a convex loss function, (DPs(() the fairness regularization, and p > is the coefficient.. Recall in Proposition that whether
(8)
8

---

Published in Transactions on Machine Learning Research (04/2024)
DDPs(() is an appropriate estimation of DDPs depends on Φ. And as stated in Proposition 1, the fairness surrogate function directly affects the burrogate-fiirnes fairness gap. Thus, the existence of such "gap" motivates that it is still necessary to reduce "gap" to improve fairness.
Our balanced surrogates approach mitigates unfairness by treating different sensitive groups differently using parameter being updated during training. The key idea of the updating procedure is making the magnitude of "gap" " as small as possible. It is a general plug-and-play learning paradigm for training framework using fairness surrogate functions like (8); which is validated in the experiments.
Specifically, we consider different surrogates for two sensitive groups, i.c.,
(xx)))
2 +1.
(do(xx)) (x)())
(9)
2 -1
With (9), we rewrite (DPs(o) as:
DDPs(0) E(x.iENs.uNa. @r (do(xx)
E(x,)eN (2(do(x)) N16 + Nos
(10)
Nia + Noa
For simplicity, we assume
Φ2(x) = (z)
(11)
where A 2 0 is the balance factor to be updated to reduce the gap. Our objective is
DDPs DDPs(0) = O,
(12)
which is equivalent to surrogate-fairnes gap of zero. Plug equations (1), (10) and (11) into the equation (12), we then solve for x:
(Nis + Not) Ei (1 - (Ni1.-os - N1.)
(13)
(Nia + Noo) ExxxIeNNNNN 0r (x)()))
In this way, we first specify Φi in (9), initiate À do and train unconstrained classifier with the produced 0, the start point of the iteration. Then iteratively solve (8) and compute (13) until convergence. In order to avoid oscillation and accelcrate the convergence, we use exponential smoothing for A:
Xx x== (1-
No,
1= 0. t= 1,2,,... ,N ..,
(14)
Where X; comes from (13) after iterations, de is the result of X; after exponential smoothing and 0 I a S is the smoothing factor. Notice that À < 0 is meaningless, so when this happens, we abandon this algorithm and set de to 1, which recovers (8). When the difference of X between two successive iterations less than termination threshold 7,, the algorithm is over. If we choose the smoothing factor a and the termination threshold 7 properly, then the loop will terminate after few runs. The algorithmie representation of the balanced surrogates can be found in Appendix B.1.
6 Experiments
6.1
Experimental Setup
Dataset. We use three real-world datasets: Adult (Kohavi, 1996), Bank Marketing (S. Moro & Rita, 2014) and COMPAS (Julia Angwin & Kirchner, 2016), which are commonly used in fair machine learning (Mchrabi et al., 2021).
Adult. The Adult dataset contains 48842 instances and 14 attributes. The goal is prodicting whether the income for a person is more than $50,000 year. We consider sex the sensitive feature with values male and female.

---

Published in Transactions on Machine Learning Research (04/2024)
0.07
0.08
Sqrncil
Bignoud
Bgrnci
Licur
0.07
Sirrad
0.000
Sgreed
Hirg
Genera
General Stgnoii
0.06
0.04
0.04
0.008
0.01
0.01
0.000
Accurayy
Accuracy
Adult.
(b) Bank.
(c) COMPAS.
Figure 3: Results of different surrogate functions.
0.045
Canrena Siggosit
Log Siymass
Unear
Hinge
noild
0.030
Hingo
Sirnckt
Connral Sayreic
Linea
Log S groud
Faimeede
0.008
0.008
Hing
Genvenal S giald
Segnuu
Unear
Sigroii
0.040
0.025
0.004
0,002
0.000
0.755 0.800
0.815
0.59
Accuracy
Acouracy
Accuracy
(a) Adult.
(b) Bank.
(c) COMPAS.
Figure 4: Results of applying balanced surrogate to different surrogate functions. The arrow starts with the result of surrogate and ends with the result of the same surrogate function using balanced surrogate method.
Bank. The Bank Marketing dataset contains 41188 instances and 20 input features. The goal is predicting whether the client will subscribe term deposit. We follow (Zafar et al., 2017c) and consider age as the binary sensitive attribute, which is discretized into the case whether the client's age is between 25 and 60 years.
COMPAS. The COMPAS dataset was compiled to investigate racial bias in recidivism prediction. The goal is predicting whether criminal defendant will be recidivist in two years. We use only the subset of the data with sensitive attribute Caucasian or Antriaan.
Baseline. In addition to an unconstrained logistic regression classifier (denoted as 'Unconstrained), we compare our general sigmoid surrogate (denoted as 'General Sigmoid') with other four surrogate functions below, which have also appeared in Figure 1.
Linear surrogate (equivalent to CP) 6(z) (Zafar et al., 2017c) (denoted as 'Lincar').
Hinge-like surrogate (xx) = max (x + 1,0) (Wu et al., 2019) (denoted as 'Hinge').
Sigmoid surrogate ((z) (x)) (Bendekgey & Sudderth, 2021) (denoted as 'Sigmoid').
Log-sigmoid surrogate 6(x) = log (=go(-z) (Bendekgey & Sudderth, 2021) (denoted as 'Log- Sigmoid').
6.2 Learning Fair Classifiers
We conduct two main experiments. One is the comparison among general sigmoid surrogate and other surrogate functions classification tasks. The other validating the effect of balanced surrogates method
10

---

Published in Transactions on Machine Learning Research (04/2024)
by applying it to different surrogate functions. Following Bendekgey & Sudderth (2021), linear classifier is used as the base classifier. The dataset is randomly divided into training set (70%), validation set (5%) and test set (25%). The parameter setting is discribed in Appendix B.3. We report two metrics on the test set: DDPs| (lower is better) and accuracy (higher better), and standard deviation is shown for the metrics.
6.3 Main Results
The results are in Figures 3-4. Refer to Appendix B.5 for specific numerical results of all three datasets.
General Sigmoid Surrogate. In Figure 3, on the one hand, we observe that the general sigmoid surrogate achieves better fairness than unbounded surrogale functions (Log sigmoid, Linear and Hinge), which indicates that the general sigmoid surrogate does effectively shorten the surrogate-fairness gap and therefore improve fairness. On the other hand, comparing to the sigmoid surrogate function, our proposed surrogate not only further reduces the gap, but it is also more flexible due to the parameter w. Moreover, it is intriguing to note that the variance of fairness and accuracy of general sigmoid surrogate is also comparatively smaller than other surrogate functions, demonstrating its superiority in terms of stability. It offers a simple solution to the long-standing high variance issue observed in existing lairness-aware algorithms (Friedler et al., 2019; Ganesh et al., 2023). We provide some theoretical analysis on variance to Appendix A.6. Exploring automated methods scarch for a suitable parameter w for improved fairness performance while reducing variance presents an intriguing avenue for future research.
Balanced Surrogates Method. In Figure 4, we observe that balanced surrogates method succeeds in improving fairness of unbounded surrogate functions but sometimes slightly compromising fairness of bounded surrogate functions. For the reason of this phenomenon, fairness-aware algorithms aim to reduce DDPs. Firstly, fairness regularization aims at lowering DDPs( Secondly, the key idea of balanced
surrogates is to reduce the magnitude of "gap" DDPs - (DPs(()) thus indirectly lower DDPs (because |ppps
DDPs s | + pDPs - DDPs(0)). However, an infinitesimal DDPs is not always better. In Appendix A.5, we show in Theorem 3 that there is still a discrepancy between DDPs s and DDP, indicating that small enough DDPs is not equivalent to a small IDDP]. When the "gap" is large (such as the un- bounded surrogate functions), balanced surrogates method can effectively reduce "gap" and achieves fairer result. But when the "gap" is limited (such as sigmoid and general sigmoid), an infinitesimal magnitude of "gap" may sometimes undermine fairness instead. Interestingly, similar to the stability enhancement observed in general sigmoid surrogate, the numerical results in Appendix B.5 also show that our balanced surrogates method attains smaller variance compared to other surrogate functions. Incorporating mechanisms such as the balanced surrogate method into existing fairness-awaa aware algorithms to enhance both fairness and stability is also a promising direction.
In Appendix B.6, we also compare our methods with other two in-processing methods: reduction (Agar- wal et al., 2018) and adaptive sensitive reweighting (Krasanakis et al., 2018). The promising results also demonstrate the superiority of our methods.
6.4 Experimental Verification for the Theoretical Insights
Large Margin Points Issue. The boxplot with our general sigmoid surrogate is shown in Figure 8 in Appendix B.7. Recall that with an unbounded surrogate function ø, the large margin points will influence the "gap". Now they have minor impact on the "gap" mentioned before because they are bounded (G(D((x)) < 1). Furthermore, the two edges almost overlap, indicating that the variation of D (x) is small, contributing to more stable results. Overall, the general sigmoid surrogate successfully deals with the large margin points, mitigating both the aurroaate-firneet fairness gap and instability simultaneously.
Balanced Dataset. From the perspective of sensitive attribute, the Adult dataset is an imbolanced dataset: there 32650 male instances and 16192 female instances. The ratio of the two groups is approximately
11

---

Published in Transactions on Machine Learning Research (04/2024)
0.05
General Sigrncdd
Gonnicl Siyrrndd
0.07
Genere Sirradd
Lineer
0.05
Down: G
Down Upp
Faimess
Up:
UpC
Faimess
Up
UpcL
0.025
0.020
0.03
0.02
0.015
0.02
0.76
0.77
0.75
0.79
0.50
0.81
0.M
0.46
0.88
0.00
0.92
060
0.61
0.02
0.63
0.54
0.5
Accuracy
Accuracy
Accuracy
(8) Adult.
(b) Bank.
(c) COMPAS.
Figure 5: The result of balanced dataset. "G" and "L" indicates general sigmoid surogate and linear surro- gate, respectivcly. "Up" and "Down" correspond to upsampling and downsampling, respectively.
2:1. The Bank Marketing and COMPAS datasets also suffer from the imbalance issuc. The ratio of the two groups are 39210:1978 (about 20:1) and 3175:2103 (about 3:2), respectively. Such imbalanced datasets lead a loose bound in Theorem We randomly split. the dataset into training set (70%) and test set (30%). According the number of minority group, we conduct two experiments: Downsampling and Upsampling, which means randomly downsampling (upsampling) the majority (minority) group in the original training set and form the new training set to make two demographic groups more balanced. Refer to Appendix B.4 for the details of our sampling schemes. The test set is partitioned in advance so that it is still imbalanced. We choose an unbounded surrogate function: Linear, and our bounded surrogate: general sigmoid.
The results Figure show that downsampling the majority group and upsampling the minority group contribute to a balancod datasct and fairer result. However, in our experiments here, downsampling will lead to reduction of the training set, and upsampling will lead to replication of the training set, which may cause underfitting and overfitting problems, respectively. So the accuracy sometimes decreases. In conclusion, before fairnoss-aware training, we suggest using fair data augmentation strategies to obtain balancod dataset, such as Fair Mixup (Chuang & Mrouch, 2021), and algorithms designed to address data imbalance, such as SMOTE (Chawla et al., 2002).
7 Conclusion
In this paper, we research on surrogate functions in algorithmic fairness. We derive the surrogate-fairnss gap to indicale the difference bet ween fairness surrogate function and With boxplots, we find that unbounded surrogates are especially faced with the large margin points issue, which further amplify the "gap" and instability. To address these challenges, we propose general sigmoid surrogate with theoretically validatod fairness and stability guarantees to deal with large margin points. The theoretical analysis further provides insights to the community that dealing with the large margin points issue well obtaining balanced dataset contribute to fairer and more stable classifier. We further elaborate balanced surrogates method, which is an iterative algorithm to reduce the gap during training. It is also applicable to other lairness surrogate functions. Finally, our experiments using three real-world datasets not only validate the insights of our theorems, but also show that our methods get better fairness and stability performance.
8 Broader Impact and Ethics Statement
This study concentrates on better understanding the fairness surrogate functions in machine learning. Im- portantly, if someone claims the fairness guarantee of using unbounded fairness surrogate functions, is worthy of suspicion and further investigation because of the surrogate-fairnes gap issue discussed in this paper. Furthermore, the motivation of our general sigmoid surrogate and balanced surrogate methods are both centered on improving the fairness performance.
12

---

Published in Transactions on Machine Learning Research (04/2024)
We acknowlodge the sensitive nature of our study and guarantee adherence to all applicable legal and ethical standards. Our research is conducted within a safe and controlled setting to protect real-world systems' security, Only researchers who have received the appropriate clearance can access the most confidential parts of our experiments. Such measures are implemented to preserve the integrity of our rescarch and to reduce any potential risks associated with the experiments.
Acknowledgement
We sincerely appreciate the anonymous reviewers for their helpful suggestions and constructive comments. WY, ZCL and YL were supported by the National Natural Science Foundation of China ANO.62076234);; the Beijing Natural Science Foundation NN0.4222029); the Intelligent Social Governance Interdisciplinaryy Plat- form, Major Innovation & Planning Interdisciplinary Platform for the "Double First Class" iative, Renmin University of China; the Beijing Outstanding Young Scientist Program (NO. JXO.BJJWYYJH1122 2019900000001100000000999 the Public Computing Cloud, Renmin University of China; the Fundamental Research Funds for the Cen- tral Universities, and the Research Funds Renmin University of China (NO. (NO.202103011 20.22000::19)) the Huawei- Renmin University joint program on Information Retrieval; the Unicom Innovation Ecological Cooperation Plan; the CCF Huawei Populus Grove Fund; and the National Key Research and Development Project N.O.2022YFB703311 ZKZ and BH were supported by the NSFC General Program No. 62376235, Guang- dong Basic and Applied Basic Research Foundation Nos. 2022A1515011657 and 2024A151501232
References
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Tlge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprinl Xrx:::2303.00 08774, 2023.
Alckh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reductions approach to fair classification. In Proceedings of the 35th International Conference on Machine Learning, 2018.
Solon Barocas and Andrew D Selbst. Big data's disparate impact. California law review, pp. 671-732, 2016.
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. fairmlbook.org, 2019.
Yahav Bechavod and Katrina Ligett. Penalizing unfairness in binary classification. arXiv preprint arXiv:1707. 1707000077004 2017.
Andrew Bell, Lucius Bynum, Nazarii Drushchak, Tetiana Zakharchenko, Lucas Rosenblatt, and Julia Stoy- anovich. The possibility of fairness: Revisiting the impossibility theorem in practice. In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Trunsparency, pp. 400-4 000-422,44 2023.
Harry Bendekgey and Erik B. Sudderth. Scalable and stable surrogates for flexible classifiers with fairness constraints. In Advances in Neural Information Processing Systems, 2021.
Richard Berk, Hoda Heidari, Shahin Jabbari, Matthew Joseph, Michael Kearns, Jamie Morgenstern, Seth Neel, and Aaron Roth. A convex framework for fair regression. In Fairness, Accountability, and Trans- parency in Machine Learning (FATML), 2017.
Marc-Etienne Brunet, Colleen AlkalayHHoulibar Ashton Anderson, and Richard Zemel. Understanding the origins of bias in word embeddings. In International conference machine learning, pp. 803-811 2019.
Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. In 2009 IEEE International Conference on Data Mining Workshops, 2009.
Flavio P. Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R. Varshney. Optimized pre-processing for discrimination prevention. In Advances in Neural Information Processing Systems, 2017.
13

---

Published in Transactions on Machine Learning Research (04/2024)
Simon Caton and Christian Haas. Fairness in machine learning: A survey, arXiv preprint arXiv:2010.0405. 2020.
Junyi Chai and Xiaoqian Wang. Fairness with adaptive weights. In International Conference on Machine 2022.
Learning, pp.
Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16:321 357, 2002.
Trene Chen, Fredrik D Johansson, and David Sontag. Why is my classifier discriminatory? Advances in neural information processing systems, 31, 2018.
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5(2):153-163, 2017.
Ching-Yau Yao Chuang and Youssef Mrouch. Fair mixup: Fairness via interpolation. In Proceedings of the International Conference on Machine Learning, 2021.
André F Cruz, Pedro Saleiro, Catarina Belém, Carlos Soares, and Pedro Bizarro. Promoting fairness through hyperparameter optimization. In 2021 IEEE International Conference on Data Mining (ICDM), pp. 1036- 1041, 2021.
Jiahao Ding, Xinyue Zhang, Xiaohuan Li, Junyi Wang, Rong Yu, and Miao Pan. Differentially private and fair classification via calibrated functional mechanism. Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
Michele Donini, Luca Oneto, Shai Ben-David, John S Shawe-Taylor, and Massimiliano Pontil. Empirical risk minimization under fairness constraints. In Advances in Neural Information Processing Systems, 2018.
Sanghamitra Dutta, Dennis Wei, Hazar Yueksel, Pin- Yu Chen, Sijia Liu, and Kush Varshney. Is there a trade- off between fairness and accuracy? perspective using mismatched hypothesis testing. In International conference on machine learning, pp. 2803 2813. PMLR, 2020.
Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian. Certifying and removing disparate impact. In Proceedings of the 21th ACM SIGKDD International Con- [erence on Knowledge Discovery and Data Mining, 2015.
Benjamin Fish, Jeremy Kun, and Ádám D. Lelkes. A confidence-basse approach for balancing fairness and accuracy. In Proceedings of the 2016 SIAM International Conference on Data Mining, 2016.
Sorelle A Friedler, Carlos Scheidegger, Suresh Venkatasubramaniann, Sonam Choudhary, Evan P Hamilton, and Derek Roth. A comparative study of ehianeis-enhancing interventions in machine learning. In Pro- ceedings of the conference on fairesss, accountability, and transparency, pp. 329-338, 2019.
Isabel O Gallegos, Ryan Rossi, Joe Barrow, Md Mchrab Tanjim, Sungchul Kim, Franck Dernoncourt, Tong Yu, Ruiyi Zhang, and Nesreen K Ahmed. Bias and fairness in large language models: A survey. arXiv:2309. 00770, 2023.
Prakhar Ganesh, Hongyan Chang, Martin Strobel, and Reza Shokri. On the impact of machine learning randomness on group fairness. In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency, pp. 1789 1800, 2023.
Gabriel Goh, Andrew Cotter, Maya Gupta, and Michael P Friedlander. Satisfying real-world goals with dataset constraints. In Advances in Neural Information Processing Systems, 2016.
Moritz Hardt, Eric Price, and Nathan Srebro. Equality of opportunity in supervised learning. In Proceedings of the 30th International Conference on Neural Information Processing Systems, 2016.
Max Hort, Zhenpeng Chen, Jie M Zhang, Federica Sarro, and Mark Harman. Bia mitigation for machine learning classifiers: A comprehensive survey. arXiv preprint arXi::2007.0000 2022.
14

---

Published in Transactions on Machine Learning Research (04/2024)
Surya Mattu Julia Angwin, Jeff Larson and Lauren Kirchner. Machine bias: There's software used across the country to predict future criminals. and it's biased against blacks. propublica, 2016. URL https:
//www.propublica.or http:pubiiiaooograaiiiieeeeee//e machinee bias-risk-asseee seskk-assssmeenss--eee in- criminal-sentencingg
Faisal Kamiran and Toon Calders. Data pre-processing techniques for classification without discrimination. Knowledge and Information Systems, 2011.
Faisal Kamiran, Asim Karim, and Xiangliang Zhang. Decision theory for discrimination-awaare classification. Tn 2012 TEFE 12th International Conference on Data Mining, 2012.
Toshihiro Kamishima, Shotaro Akaho, Hideki Asoh, and Jun Sakuma. Fairness-aware classifier with prej- udice remover regularizer. In Proceedings of the 201 2th European Conference on Machine Learning and Knowleddge Discovery in Dalabases Volume Port 11, 2012.
Enkelejda Kasneci, Kathrin Seßler, Stefan Küchemann, Maria Bannert, Daryna Dementieva, Frank Fischer, Urs Gasser, Georg Groh, Stephan Günnemann, Eyke Hüllermeier, et al. Chatgpt for good? on opportunities and challenges of large language models for education. Learning and individual differences, 103:102274, 2023.
Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. In Innovations in Theoretical Computer Science (ITCS), 2017.
Ron Kohavi. Scaling up the accuracy of nayve-bayes classifiers: A decision-tree hybrid. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, 1996.
Emmanouil Krasanakis, Eleftherios Spyromitros-Xioute Symeon Papadopoulos, and Yiannis Kompatsiaris. Adaptive sensitive reweighting to mitigate bias in fairness-aware classification. In Proceedings of the 2018 world wide web conference, pp. 853-862, 2018.
Preethi Lahoti, Alex Beutel, Jilin Chen, Kang Lee, Flavien Prost, Nithum Thain, Xuezhi Wang, and Ed Chi. Fairness without demographics through adversarially reweighted learning. Advances in neural information processing systems, 13:728-7400 2020.
Yingji Li, Mengnan Du, Rui Song, Xin Wang, and Ying Wang. survey on fairness in large language models. arxiv preprint Xix: 10149, 2023.
Zachary Lipton, Julian McAuley, and Alexandra Chouldechova. Does mitigating ml's impact disparity require treatment disparity? Advances in neural information processing systems, 31, 2018.
Lydia T Liu, Max Simchowitz, and Moritz Hardt. The implicit fairness criterion of unconstrained learning. In International Conference on Machine Learning, pp. 4051-4060, 2019.
Yang Liu, Yuanshun Yao, Jean-Francois Ton, Xiaoying Zhang, Ruocheng Guo Hao Cheng, Yegor Klochkov, Muhammad Faaiz Taufiq, and Hang Li. Trustworthy 1lms: a survey and guideline for evaluating large language models' alignment. ar preprint or Xrxi:22308. 05374, 2023a.
Yiheng Liu, Tianle Han, Siyuan Ma, Jiayue Zhang, Yuanyuan Yang, Jiaming Tian, Hao He, Antong Li, Mengshen He, Zhengliang Liu, et al. Summary of chatgpt-related research and perspoctive towards the future of large language models. Meta-Radioooggy 2023b.
Michael Lohaus, Michael Perrot, and Ulrike Von Luxburg. Too relaxed to be fair. In Proceedings of the 37th International Conference on Machine Learning, 2020.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and trans- ferable representations. In International Conference on Machine Learning, pp. 3384 3393, 2018
Gaurav Maheshwari and Michaël Perrot. Fairgrad: Fairness aware gradient descent. Transactions on Machine Learning Research, 2023.
15

---

Published in Transactions on Machine Learning Research (04/2024)
Vien V Mai and Mikael Johansson. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. In International Conference on Machine Learning, pp. 7325-7335, 2021.
Ninarch Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM Computing Surweys, 54:1-35, 2021.
Raghav Mehta, Changjian Shui, and Tal Arbel. Evaluating the fairness of deep learning uncertainty estimates in medical image analysis. In Medical Imaging with Deep Learning, pp. 1453 1492. PMLR, 2024.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Kirtan Padh, Diego Antognini, Emma Lejal-Glaude, Boi Faltings, and Claudiu Musat. Addressing fairness in classification with model-agnostic multi-objective algorithm. In Proceedings of the Thirty-Seventh Conference Uncertoinly in Arlificial Intelligence, 2021.
Dana Pessach and Erez Shmueel.. Algorithmic fairness. Machine Leurning for Dala Science Handbook: Dala Mining and Knowledge Discovery Handbook, pp. 367-886, 2023.
Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. On fairness and cali- bration. In Advances in Neural Information Processing Systems, pp. 5684-569) 2017.
Sandro Radovanovié, Boris Delibasié, and Milija Suknović. Do reach desired disparate impact with in-processing fairness techniques? Procedia Computer Science, 214:257-264, 2022.
Yuji Roh, Kangwook Lee, Steven Whang, and Changho Suh. Sample selection for fair and robust training. Advances in Newral Information Processing Systems, 34:815 827, 2021a.
Yuji Roh, Kangwook Lee, Steven Euijong Whang, and Changho Suh. Fairbatch: Batch selection for model fairness. In International Conference on Learning Representations, 2021b.
P. Cortez S. Moro and P. Rita. A dala-driven approach to predict the success of bank telemarketing, 2014.
URL https:/ bottps://archins www.:eeeisss.uieeuuuee. wwt.ee//dmmmaasttt////////////// toakkeiarktting
Changjian Shui, Qi Chen, Jiaqi Li, Boyu Wang, and Christian Gagné. Fair representation learning through implicit path alignment. In Proceedings of the 39th International Conference Machine Learning, volume 162, pp. 20156 20175, 2022a.
Changjian Shui, Gezheng Xu, Qi Chen, Jiaqi Li, Charles X Ling, Tal Arbel, Boyu Wang, and Christian Gagné. On learning fairness and accuracy on multiple subgroups. Aduances in Neurol Information Processing Systems, 35:34121-3411 -4413,, 2022b.
Changjian Shui, Justin Szeto, Raghav Mehta, Douglas L Arnold, and Tal Arbel. Mitigating calibration bias without fixed attribute grouping for improved fairness in medical imaging analysis. In International Conference on Medical Image Computing and Computer-Assitted Intervention, pp. 189-198. Springer, 2023.
Arun James Thirmavuukarasu, Darren Shu Jeng Ting, Kabilan Elangovan, Laura Gutierrez, Ting Fang Tan, and Daniel Shu Wei Ting. Large language models in medicine. Nature medicine, 29(8):1930-15) 10t.0-999999,,,,,, 2023.
Saeid Tizpaz-Naari, Ashish Kunar, Gang Tan, and Ashutosh Trivedi. Fairness-aware configuration of machine learning libraries. In Proceedings of the 44th International Conference on Software Engineering, pp. 909 920, 2022.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Nikolay Bash- lykov, Sounya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. aixiv preprint S5k3:2307.092888 2023.
Mingyang Wan, Daochen Zha, Ninghao Liu, and Na Zou. In-processing modeling techniques for machine learning fairness: A survey. ACM Transactions on Knowledge Discovery from Data, 17(3):1 27, 2023.
16

---

Published in Transactions on Machine Learning Research (04/2024)
Boxin Wang, Weixin Chen, Hengzhi Pei, Chulin Xie, Mintong Kang. Chenhui Zhang, Chejian Xu, Zidi Xiong, Ritik Dutta, Rylan Schaeffer, et al. recodingtrust: A comprehensive assessment of trustworthiness in gpt models. In Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023.
Yongkai Wu, Lu Zhang, and Xintao Wu. On convexity and bounds of fairness-awaro classification. In The World Wide Web Conference, 2019.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna Gummadi. Fairness beyond disparate treatment & disparate impact. Proceedings of the 26th International Conference World Wide Web, 2017a.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, Krishna P. Gummadi, and Adrian Weller. From parity to preferenco-basee based notions of fairness in classification. In Proceedings of the 31st International Conference on Newral Information Processing Systems, 2017b.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P. Gummadi. Fairness con- straints: Mechanisms for fair classification. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017c
Muhammad Bilal Zafar, Isabel Valera, Manuel Comez-Rodriguees and Krishna P. Gummadi. Fairness con- straints: A flexible approach for fair classification. Journal of Machine Learning Research, 2019.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In Proceedings of the 30th International Conference Machine Learning, 2013.
Daochen Zha, Zaid Pervaiz Bhat, Kwei-Herng Lai, Fan Yang, Zhimeng Jiang, Shaochen Zhong, and Xia Hu. Data-centric artificial intelligence: A survey. arXiv preprint orXiv:2303.1011 2023.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAT/ACM Conference on AI, Ethics, and Society, pp. 335-340, 2018.
Tao Zhang, Tianqing Zhu, Mengde Han, Jing Li, Wanlei Zhou, and Philip S. Yu. Fairness constraints in semi-supervised learning. arXiv preprint arXiv:2009.061 2020.
Chen Zhao, Changbin Li, Jincheng Li, and Feng Chen. Fair meta-learning for few-shot classification. Tn 2020 IEEE International Conference Knowledge Graph (ICKG), 2020.
Han Zhao and Geoffrey Gordon. Inherent tradeoffs in learning fair representations. The Journal of Machine Learning Research, 23)22522722252, 2022.
17

---

Published in Transactions on Machine Learning Research (04/2024)
Contents
1
Introduction
2
2 Related Work
3
3 Preliminaries
4
3.1 Fairness-aware Classification
4
3.2
Surrogate Functions
4
4
The fainness Gap
5
Instability
4.2
The Large Margin Points
6
Our Approach
6
5.1
General Sigmoid Surrogates
5.1.1
Fairness Guarantees
7
5.1.2
Insights from the Theorems
8
5.2
Balanced Surrogates
Experiments
9
6.1
Experimental Setup
6.2
Learning Fair Classifiers
10
6.3 Main Results
11
6.4
Experimental Verification for the Theoretical Insights
11
7
Conclusion
12
8 Broader Impact and Ethics Statement
12
A Proof for the Main Paper
20
A.1 Analysis about CP
20
A.2 Extension from Fairness Surrogate Functions to CP
21
A.3 Proof of Theorem
22
A.4 Proof of Theorem 2
23
A.5 Risk Bound
24
A.6 Variance Analysis
26
B Further Experimental Details and Results
28
B.1 The Balanced Surrogates Algorithm
28
B.2 Details in Figure
29
18

---

Published in Transactions on Machine Learning Research (04/2024)
B.3
The Parameters..
29
B.4
Upsampling and Downsampling
30
B.5
Numerical Results of Figure 3-4
30
B.6 Comparing with Other Fairness-aware Algorithms
B.7 Boxplots with General Sigmoid Surrogate
31
C Other Related Work
31
C.1 Faire Algorithms
31
C.2 Fairness Surrogate Functions
32
D Extension to Other Fairness Definitions
33
D.1 Fairness Definitions..
33
D.1.1 Disparate Mistreatment
D.1.2 Balance for Positive (Negative) Class
33
D.2 Deeper Understanding of the Covariance Proxy for Disparate Mistreatment
33
D.3 Proof for Appendix D.2
34
D.3.1 Overall Accuracy Equality
35
D.3.2
False Positive Error Rate Balance
37
D.3.3 False Negative Error Rate Balance
39
D.4
Deeper Understanding of the Covariance Proxy for Balance for Positive (Negative) Class
42
D.5 Proof for Appendix D.4
42
D.5.1 Balance for Positive Class
42
D.5.2 Balance for Negative Class
44
E Further Analysis
45
E.1 Fairness Surrogate Functions in the Future
45
E.2 The Insights for Large Langnage Models
45
E.3 Biased Estimation of CP
46
E.4 Proof of Section E.3
46
E.5 When are CP and General Sigmoid Surrogate Close Each Other?
47
E.6 Proof of Theorem 14
48
19

---

Published in Transactions on Machine Learning Research (04/2024)
Appendix
In the appendix, due to the length limit of every line, M...)) Ld)(x) is denoted as Exiawo. ]xx(sss for better presentation because it prevents endless line breaks.
We summarize the frequently used notations in Table 1:
Table 1: The most frequently used notations in this paper.
Notations
Meanings the training set the size of the training set feature vector of a data point the corresponding label the corresponding sensitive attribute
S
N
y
the parameters of the classifier
do(x)
the signed distance between the feature vector and the decision boundary
Dx(x)
the absolute value of dx(x)
ó(-)
the surrogate function
G(-)
general sigmoid surrogate function
Nia
the set of data points with positive prediction and positive sensitive attribute the size of Ni.
Nia
TP+
the number of data points with positive prediction and positive sensitive attribute
DDP
the difference of demographic parity
DDPs
an estimation of DDP
(DPs(
the constraint/reguuarizatin term with fairness surrogate function ø
(ou)(o)
the covariance proxy
U1a
The number of points satisfying (DD(x)) E (0, in Wia
P())
the predicted probability
A Proof for the Main Paper
A.1 Analysis about CP
In this subsection, we finish the proof of DDPs(0) x Co)s(o).
Now this is the proof for the claim that, when degenerating oxx) (it a linear function), we have DDPs(0) Covs(o). It is step-by-stey derivation of (3).
1
(2 - (x)
N
Conglo), where =x.
20

---

Published in Transactions on Machine Learning Research (04/2024)
2)
Σ
dx(x:) + (-1-x)
Σ dx(xi)
Noa
NihiNos
Nia Noa
Ni6 Nob
do(xi) (-1-
Nía + Noa
N1b Nob
Σ
Σ Nov.Noo
do(xi)
N
N
NiniNoa
2 N2
(Nib + Nob) Σ
do(x:) (Nia Noa)
Σ dx(x;))
NiawNaa
Nis
2NN + Nua) (NV1 + Nos)
ENinwNoa do(x;)
ENisdon do(x;)
(15)
N
Nia + Noa
N16 + Nob
constant Sj<l
DDPs(d), where ((x)=x.
The proof is complete.
Furthermore, in fact, we have (DPs(() & Cous(Φ) holds for all ø. But for the original CP (Zafar et al., 2017c), p(z) = x is the default. So the original CP equivalent to linear surrogate because d(x) = z. Similar proof is also explained in previous work (Lohaus al., 2020; Bendekgey & Sudderth, 2021), where they call it "linear relaxations".
A.2 Extension from Fairness Surrogate Functions to CP
This subsection aims to restate the theoretical analysis about DDPs(0) in Proposition 1 and Theorem 1-2 from the perspective of (o))(Ø) From the above derivations, we have
Coos(o)= 2(N1. Noa) + Nos) DDPs(0).
N2
constant
Therefore, the theoretical analysis about (() in Proposition 1 and Theorem 1-2 in the main paper can be naturally extended to Cous(o). Just by substituting the equation above into Proposition and Theorem 1-2, we restate them below:
Proposition (Restatement). Define the magnitude of the signed distance by Do(x), i.e., Do(x) [do(x)] Let ((x) = and S1a- En.. ()))(x;))TT. Ex.. (o(Do(x)) - 1) and il is similar for Nob, 11
satisfies:
N
Tia Soa Tia Sob
DDPs 2(N1a + No1) + Nos)
(ows(()-
(16)
Nia + Noa Ni + Nob
surrogate- fairressss gap
Theorem (Restatement). We assume that G(Do(x)) E ( 7, where 7 0. We >0 0, (oo(C) Se,
then it holds:
N2
DDPs < 4(Nia + NN1 + Nob) +7.
Theorem 2 (Restatement). We assume that points satisfy G(Do(x)) E [0,1 7 and others satisfy
G(Dg(x)) [1- 7, 1], where 7 > 0. We > 0, if (oo(G) S e, then it holds:
2² DDPs I 4(Nia + No.) + Nob)
c +
2 Nia + No. + No + Nos
k.
relazation factor
21

---

Published in Transactions on Machine Learning Research (04/2024)
The restatement of them does not affect the analysis the main paper since DDPs(0) x (o)
A.3 Proof of Theorem 1
Proof sketch. Firstly, absolute value inequality is used to derive the upper bound of DDPs given the upper bound of ( Secondly, the assumption G(Do(x)) e [1 (1-7,11 is used to derive lighter bound of DDPs to complete the proof.
Proof. If o passes through the origin and increases monotonically, then according to the sign of do(x), we have
DDPs(0) ENin.o. o(do(x;)) ENin.on ((d((x)))
Nia + Noa
Noo Nob
ENs ((Do(xi)) ENo, ((Do(xi) END ((Do(x)) ENao ((Da(xi))
(17)
Nia + Noa
NI6 + Nos
We define Tia = ENT, (Da(x)) Nia = EN (o(o(xx)) 1). It is similar for Tio, Toas Tob. We now analyze the term in (17) by limiting it with a parameter 8 > 0:
DDPs(0) Eni, o(Do(x:)) - -nn.. o(Do(xi))
ENu, o(Do(x;)) - ENoo o(Do(xi))
58 (18)
Nia + Noa
No0 + Nob
Nia Noa
N16 Nos
Noo - Nia + ENI. ol ((Do(x))) - ENao ((Do(x))
+
Nia + Noa
No6 + Nos
Nia + Noo
Nis - Nob ENO, ((Do(x:)) + ENn, o(Do(x:))
<8
N1b + Nob
N1. Noa
N16 Nob
Nia + Noa
NI6 + Nos
Noa Nia + En,, (x)))x - ENO. ((Di(x)))
< ++
Ni0 + Noa
Nis - Nob ENOo (xDo(x;)) + Ena. ((Do(x;))
N1s Nos
Ni. Noa
N16 Nos
Nia + Non
NI + Nos
(ENia p(Do(x.)) - -Naa) -EEna o(Do(x;)) Noa)
<5+
Nia Noa
EEno (DD())) No.) - (ENr, o(Do(x;)) - -Nb)
Nbb + Nob
Nia - -Na
No NoA1
Tia Toa
Tos Tin
8
+
Nia + Nos
NI + No
Nia Now
NI8 Nos
Nia
Nia
Nib
(1- Ni6 Ni + Nob
1
Nia + Nou
Nia + Nua
N1 + Nos
Tia
Toa
+ Tob Tib
< 8 +
Nia + Noa
NiG Nos
Nia
Ni6
1 1 (6+
Tia Ton
Tos Tip
DDPs
(19)
Nia Noe
No Nob
2
Nia Nua
No Nos
22

---

Published in Transactions on Machine Learning Research (04/2024)
The process of mathematical derivation for (19) mainly includes basic algebraic operations, equivalent sub- stitution and absolute value inequalities. The inequality (19) will be used later to prove (20)-
Now we begin to use the assumption G(Do(x)) E [1-71 G(Do(x)) E [1 [1-21 y, + 7]. the theorem holds with the relaxed version, then also holds for the orig- inal assumption. We replace the above & with general sigmoid G.
7, 1]. A relaxed version of such assumption is
With G(Dg(x)) E [1 7, + 7), Tia E Nia and Toa [-Noo Noae] hold. In other words, Tu--Tau Nia+Non [- and Tie E 11 71, which means that:
Nos
Tia - Toa
Top Tis
+
E [0,22]]
Nia + Noa
NI6 Nob
So with (19), we have
DDPs
Nia
Ni
1
8
Tie Toa
+ Tor Tib
)
2 +%
1
(20)
Nia + Noa
N16 + Nob
2
Nia + Noa
N16 + No8
2
Now we set 8 = combine (20) with (18), and obtain the conclusion: Ve > 0, if DDPs have
S then we
DDPs S 5
The proof is complete.
A.4 Proof of Theorem 2
Proof sketch. The difference between Theorem 1 and Theorem 2 mainly lies in the assumption of Do (x).
Therefore, Equation (19) can be also used here because it is independent with the assumption. Consequently, the task of the proof is providing a tighter bound than Equation (19). The process of derivation mainly includes basic algebraic operations.
Proof. The number of points satisfying (x) E [0, - 7] in the four groups are denoted
Ula: Una Un,, Una respectively. So there holds of ((Dx(x)) - 1 [-1,-n] for them and ((D)(x)) 1 E [-7, 0]
for others. Note that
Ula + Ubb + Una + Uns k.
We have
Tia = -(M(Do(x)-1)) 1)) E [-U (Nia - U1a)7 -Ua7),,
Nia
and it is similar for Tio, Too, Tos. So
Tia Toa
-NN1a7 U1a + (U1a + Uoa)y Nuay + Una - (U1a + Uva)
Nia + No
Nia + Noo
Nia + Noo
For the lower bound:
Nia7 U1o + (U1a + Uoa)
-N1a7
(U10 + Uou) U10
N1a + Noa
Nia Noo
NIa + Noa
(U1o + -Va)Yy U1o
> 7
Nia + Noo
Una
2 --7- Nia + -Noe
k
2 7 Ni. + No.
(21)
23

---

Published in Transactions on Machine Learning Research (04/2024)
For the upper bound:
Y + Usa - (Uia + Uoa)?
Noa7
Una - -U1a + U
N1a + Noa
Nia Noa
Nia Noa
Una (U10 Upaly
Sy
Nia + Noa
Uoa
S
Nia +Noa
k
2 Nia Noa
(22)
Therefore, we have
Tia - Too
k
+
N1a + Noa
Nia + Noa
Nia + Noa
and
Tob Tio
k
-7-
Nib + Nob 7
Nis + No6
Nib + Nos
So
Tia Toa
Tih N16 + Nob
Tos
I 27 +
k.
(23)
N1. + Noa
Nia No.
No6 + Nob
The last step is similar to Appendix A.3, but relaxation term is added. Combining (19) and (23) together, we have
+ 1 ( 2 Ni + Noa + NI + Nos
{ k.
DDPs
S - - +
The proof is complete.
A.5
Risk Bound
We show the risk bound of DDP, and then provide some discussion about the surrogate function in opti- mization.
Theorem 3. For a given conslant 6 > 0, there holds:
p ((DDDP - DDP st) 2 21-6. 6,
where = V In v -1-
Proof. We know that
ENia.Non Ado(x)20
ENis 1d)())>0
E DDPs)
E
Nia + Non
Nib + Nos
Exm.No E(Ido(s))2))
ENnno B(Id((x)20)
Nia + Noa
Nib + Nob
Emanion [((aa(x)=0)==+1))
ENiowia E(L E(Lde(x)>0/==--)
Ni. + Noa
No + Nos
E(14(()20)==-1>> -{((1(())))))==--))
P(dg(x) > 0/2 +11 - ((do(x) 0/2= = 1)
DDP.
24

---

Published in Transactions on Machine Learning Research (04/2024)
Since the indicator function satisfies [p] E [0, 11, so according to the Hoeffding inequality,
P(DDPs- DDP & 2 11 -expp ( (-212
We set = 2 (-2t so that t= / In V = = (x)))) Substitute them into Theorem above, we prove the result.
]
Fairness guarantee. From the above theorem, one can see that, with probability more than 1 - 6, the discrepancy between the DDPs and DDP can be small enough with the order O VN Also, Proposition 1 and Theorem 3 together tell us that with a big dataset (N is large), if DDPs(() and the gap are both small enough, then we can state with a high probability that the classifier satisfies the fairness constraint.
Recall that (D))(Ø) is used for optimization, DDP the real fairness criterion, and DDPs an estimator of DDP. Therefore, it is crucial to theoretically build a bound between the practice (DDPs(0)) and the objective (DDP). To address this issue, note that:
DDPs(0) DDP < DDPs(0)- DDPs
DDPs -
surrogate-fairuees risk bound of DDP
Therefore, we have an very large dataset (a small risk bound DDP) and an appropriate surrogate function with fairness guarantee (a bounded surrogato-fairness gap), then there is thcorctical guarantee for (
Is infinitesimal DDPs better? However, although the discrepancy between the DDPs and DDP can small enough, the discrepancy still exists, which means that a classifier with DDPs may not satisfy DDP x The principle is similar for ERM (Empirical Risk Minimization): a small enough empirical loss may lead to overfitting so that an infinitesimal loss is not always better. Therefore, an infinitesinal DDPs is also not always better.
The surrogate loss function in machine learning. In machine learning, surrogate loss function is an auxiliary function used during optimization, which is easier to optimize than the original objective function. Some examples of surrogate loss functions are in Figure 6. Surrogate loss functions are particularly useful when dealing with complex or non-differentiable objective functions. The idea to approximate the difficult parts of the objective with a surrogate that has more tractable propertics (like smoothness or convexity) for optimization algorithms. Here are some examples:
Surrogate loss functions are often smooth and convex, even the original objective is not. This allows for the use of gradient-based optimization techniques, which speed up the learning process.
Use in various algorithms: Surrogate loss functions used in various machine learning algorithms, including support vector machines (where the hinge loss function acts as surrogate for the 0-1 loss function), boosting methods (which build surrogate to focus on examples that are hard to predict).
Loss approximation: In classification, surrogate loss functions are used to approximate the original loss function. For example, logistic loss and hinge loss are surrogates for the 0-1 loss function in logistic regression and support vector machines, respectively.
Surrogate loss functions and fairness surrogate functions. The foundation of fairness surrogate function similar the surrogate loss function: both of them aim to approximate the 0-1 function. When minimizing the loss function, there are two kinds of insights to choose surrogate functions:
25

---

Published in Transactions on Machine Learning Research (04/2024)
Zero-one loss
Hinge
7
Log loss
Squared hinge loss
Modified Huber loss
6
(1)
4
2
2
-3 -2
11
0
3
t
Figure 6: The surrogate loss functions v in machine learning. The figure is adapted from this link.
Upper bound of 0-1 function: Taking surrogate loss functions as an example. As suggested Figure 6, all of these surrogate loss functions are upper bounds of 0-1 function. Therefore, when the loss function is minimized to small value, there is generalization guarantee for the classifier (Mohri et al., 2018). Unfortunately, as suggested in Figure 1, the fairness surrogate functions mentioned in existing work are not upper bounds of 0-1 function.
Estimator of 0-1 function: As shown in Figure 1, we aim to better estimate the 0-1 function for fairness. Our empirical results show that our general sigmoid estimation performs fairer results.
Overall, believe that the fairness community can be inspired by machine learning and optimization. How to design belter fairness surrogate functions is intriguing. Insights from surrogate loss functions may be promising in the fairness community for future work.
A.6 Variance Analysis
-1). We assume that each dataset consisting of N points is independently drawn from dataset distribution. The variance is computed over the dataset distribution. Then there holds:
Theorem 4. Let Na Nıa Noa, No N1b Nos. Pa = P== =1)= P(do(x) 0|= P()
Var (DDPs) <
11(1 1
(24)
No No
Proof. Using the equation Var(x) EEx²) (Ex)), we have
(ENin.Non Ldo(x)20
ENis.ii 1x)())
Var (DPs)) =Var
Nia + Noa
Ni + Nos
26

---

Published in Transactions on Machine Learning Research (04/2024)
ENiawiin 1d((x)2
ENiuNoo 1x)(x)>0
2
E
E E(DDPs
(25)
Nia + Noa
NIb Nob
=DDP
where
ENiuNow Ido(x)>0)
ENiu.Nos dd(())>0
2(EN Now
(do())))))
T= E
Nia + Noa
N16 + Nos
(N1a Nua (Na)(N1 + Nub)
Ti
T2
With the linearity of expectation, we deal with the three terms in T respectively. First of all,
E(T (Nia Noa )
E
Σ
dx(())
(26)
NouwNe
and
E
Σ Nin.No
Il dx)
2
Var
Σ
dd0(0)20
+
E Σ 1x)
Nia
NinNNo
2
Σ Nra:Naa
Var (1ds(x)20)
Σ
E (1de(x)200
NiawNa
2
Σ
Var (166()))0/==+11+ +
Σ E (166(x)201==--)
NiusNaa
NiuuNan
(Nia Var (1ax())00)==11) + (Nia + Noa) (P((d(xx > 0/2 +1)]²
(27)
Also,
Var (1do(x)20|==t1) = =(1d)(x))0==+11) (E(1 (B())))))))())(
= =B(La(()>00==+11 - (p(d6(x) > 0/2 = +1))
P(do(x) > 0/2 =+1) (P(do(x) 0|2 +1))
(28)
Combining (26), (27) and (28), we have
E(Ti) (1 Nia + Noa
(P(do(x) 10=+10 =11)3 Nia + Noa
P(do(x) > ===+1).
(29)
Similarly, we have
E(T2) = (1-== No + Noo
1
(P(do(x) > 0/2 -1))² + No + No6
((do(x)>00 0|==
(30)
Finally, because of the fact that
Σ ld)()))0
(x)
Ninwoon
Nio
27

---

Published in Transactions on Machine Learning Research (04/2024)
Σ dx) E
Σ ddolx))0 + Cov
Σ
1 dx))0)
E
ddo(x)20
Ninwon
Nissooo
NiowNaa
Nos.Nos
=(Nia + Noa) ((do(x) > 0/2 = +1) (N16 + P(do(() > 0/2 -1)
Σ
E
Cou (Ido(x)20)==41, L (x)=)))))==-1
Nua Nin..Nos
(Naa + ((do)() > 0|2 = +1) (Ni6 + Noo) > 0/2 -1),
we have
2 T No. (2 Noo [x)())=0) (Nia + Noa) (N + Nob)
B(T3) =E
2(N1a + -No) > 0/2 +1) (N + Not) 0/2 =-1
(Nia + Noo (NVr + Nob)
PpP.Pb.
(31)
Overall, combining (29),(30)((1) with (25), we have:
Var (DPss
(T)i + E(Tb) IE(T3) (DDP)²
1
1
1
p2 +
Pa +
1
PS
+
Pb -PP.P.
(Pa - Pb) P
Na.
No
No.
Nb.
B(Ts)
DDP
B(Th)
E(Ta)
1
1
p2
PS
Po +
Pb
Na
No
N
Nb
1
1 y2
(Po 1
+
(Pa
(Pa + P. = 1)
4
Na
No
Na
2
N
2
1
+
Paa 3
(32)
4
N
No
Na
No.
2
For the maximum variance, Pa takes the value 3, and the maximum variance is
max Var (DPss) ]
1
(33)
No
No
When Pa = 0 or Pa 1, there holds Var (DDPs) = 0. Furthermore, the result also provides insights into the advantages of balanced dataset for stability.
We place the computation of Var (DDPs) for the convenience of researchers interested in exploration. For example, designing alternative surrogate functions and algorithms based on these expressions to reduce variance could be an intriguing avenue for research.
B Further Experimental Details and Results
B.1
The Balanced Surrogates Algorithm
The process of balanced surrogates is shown in Algorithm Computations associated with x, cost O(N). Consider solving (8) gives rise to O(M) computations. So Algorithm costs O((M + N)).
28

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithu 1: Balanced Surrogates
Input: Training set y:)
Initialization: Balance factor surrogate function Φ1, termination threshold 7, maximum iterations and other parameters.
3: Train unconstrained classifier and obtain the model parameter Og-
4: Time step t O.
5: repeat
1=1+1.
Solve the optimization problem (8) (start at 0p)- Compute i 1,.,,,,,. N and Nia: Nis, No Nob.
Obtain X, via (13).
10:
Obtain d by exponential smoot hing via (14).
11:
if A S 0 then
12:
Set A 1.
13:
end
14: until AA, A sn T or d 5
15: Output: de, de dx(x;), 1,, , and Nia: Nib, No Nob.
Discussion of motivation of this algorithm. One may question the motivation of balanced surrogate that the learning algorithm will try to find a balance between the empirical loss and the fairness regularization, and it may suffice use the upper bound of DDPs as the fairness regularization. In order to clarify it, we provide more discussion of motivation of the balanced surrogate algorithm.
We believe that previous algorithms with fairness regularization aim to find balance between the empirical loss and the fairness regularization. However, in this paper, we want to uncover the issue that when we use fairness surrogate functions as the constrainn//rgguaariatiio the constraint constraint/reguulrizza regulariztilnnnnnn and the true fairness definition. Therefore, we emphasize that some widely used fairness surrogate function, such as the unbounded surrogates analyzod this paper, may not serve as an appropriate regularization because of the surrogate-fairness gap.
there will be a surrogate-fairness gap bet ween
Thus, focusing fairness surrogate functions, provide the balanced surrogate algorithm to reduce the gap, thus trying to help fairness surrogate functions to achieve a better fairness performance. In the experiments, the balanced surrogate method consistently helps the unbounded surrogates (log-sigmoid, linear, and hinge surrogates) to be fairer, while it benefits the bounded surrogates (sigmoid and the general sigmoid surrogate) in most cases. suggests that reducing the gap is useful for unbounded surrogates. In this case, it may not suffice to use the unbounded upper bound of DDPs However, when we use bounded surrogates, making the gap infinitesimal may not always be beneficial to fairness. In this case, such phenomenon may be in line with your concern. Overall, how to strike a balance between the gap and the surrogate function for better fairness intriguing, but may be outside the scope of this work.
B.2 Details in Figure 2
The datasets are mentioned in Section 6. We randomly split each dataset into train (70%) and test (30%) set. Then for each dataset, we train two logistic regression classifiers, one the unconstrained classifier and the other is the constrained optimization problem (Zafar et al., 2017c) with covariance threshold.
B.3
The Parameters
General sigmoid surrogate.
The regularization coefficient À in (8) lies in the grid (0.1,0.2,-....
The parameter w general sigmoid is chosen from {1,2, 4, 16) according the fairness perfor- mance on the validation set.
29

---

Published in Transactions on Machine Learning Research (04/2024)
Balanced surrogate.
The smoothing factor a = 0.9.
The termination threshold 0.01.
Discussion of hyper-parameters in our algorithms. Indeed, our approaches do require some addi- tional hyper-parameter tuning:
For to in general sigmoid, as shown in our experimental settings in the appendix, it is selected from {1, 2, 4, 8, 16} according to the fairness performance on the validation set. Thus, it requires selecting an approximate range for
For the regularization coefficient 7, it is conventional in machine learning to adjust it. Our experi- ments also require selecting an approximate range for it.
The smoothing factor a, and termination threshold n are hyper-parameters, but fix them and never change them throughout our experiments.
For y in the balanced surrogate approach, it does not require any hyper-parameter tuning because automatically specified the algorithm.
Therefore, in our experiments, only consider tuning two hyper- preer-paraeetes: and 7. And optimization tools (such as hyperopt may be useful to aid the cost of hyper-parameter tuning.
B.4 Upsampling and Downsampling
For Adult and COMPAS, the imbalance issue is not too severe (about 2:1 and 3:2, respectively), balance between different demographic groups by randomly selecting samples and form the new training dataset such that samples in each group are of the same number. However, for Bank Marketing, the ratio of two groups approaches 20:1, so the sampling scheme for Adult and COMPAS not suitable because it will cause 19 copies of the minority groups (overfitting). As result, we only incorporate extra copy of the minority group into the training set when upsampling.
B.5
Numerical Results of Figure 3-4
Full results are in Table 2. Standard deviation is shown for the metrics.
B.6
Comparing with Other Fairness-aware Algorithms
In addition to CP (Zafar et al., 2017c) (denoted as 'Lincar'), we compare with two other popular in- in-processing fairness-aware methods: reduction approach (Agarwal et al., 2018) (denoted as 'reduction') and adaptive sensitive reweighting (Krasanakis et al., 2018) (denoted as 'ASR'), which are not based on fairness surrogate functions. The results are shown in Figure
In the Bank dataset, our general sigmoid surrogate and balancod surrogate approaches consistently achieve much better fairness performance than 'reduction' and 'ASR' while maintaining comparable accuracy.
In the COMPAS dataset, our approaches always achieve better fairness performance than others while maintaining comparable accuracy.
In the Adult dataset, our methods achieve better fairness than 'AR'' while maintaining comparable accuracy.
https://gthaah.co///yppooog
30

---

Published in Transactions on Machine Learning Research (04/2024)
Table 2: Experimental results.
Datasets
Methods
Accuracy
DDPs
Unconstrained
0.838 + 0.009
0.182 + 0.018
Linear
0.810 + 0.031
0.060 + 0.020
B B-Lieear
0.815 = 0.017
0.053 + 0.010
Log-Sigmoit
0.808 = 0.018
0.052 + 0.025
B-Log- -og-Siimoid
0.801 = 0.018
0.041 = 0.020
Adult
Hinge
0.808 + 0.018
0.051 + 0.025
B-Hinge
0.803 = 0.016
0.042 = 0.019
Sigmoid
0.802 = 0.015
0.033 + 0.011
B-Sigmoid
0.802 = 0.012
0.037 = 0.012
General Sigmoid
0.805 + 0.013
0.029 + 0.010
B-General Sigmoid
0.803 + 0.007
0.037 + 0.016
Unconstrained
0.910 + 0.004
0.192 + 0.003
Linear
0.892 + 0.005
0.037 + 0.041
B-Linear
0.891 + 0.005
0.032 + 0.039
Log-Sigmooi
0.894 = 0.007
0.043 = 0.038
B-Log-Sigmoid
0.892 + 0.005
0.040 + 0.037
Bank Marketing
Hinge
0.891 + 0.005
0.035 + 0.037
B-Hinge
0.889 + 0.005
0.029 + 0.046
Sigmoid
0.889 = 0.004
0.021 + 0.044
B-Sigmoid
0.888 + 0.004
0.024 + 0.042
General Sigmoid
0.889 + 0.003
0.014 + 0.031
B-General Sigmoid
0.889 + 0.002
0.013 + 0.027
Unconstrained
0.666 0.020
0.281 0.035
Linear
0.636 + 0.009
0.039 + 0.022
B- B-Linear
0.626 = 0.009
0.035 = 0.013
Log-Sigmoid
0.629 + 0.012
0.039 + 0.021
0.626 = 0.010
0.036 + 0.021
COMPAS
Hinge
0.625 + 0.009
0.033 + 0.021
B-Hinge
0.624 = 0.008
0.033 + 0.021
Sigmoid
0.629 0.006
0.034 + 0.013
B-Sigmoid
0.626 = 0.009
0.031 - 0.017
General Sigmoid
0.627 + 0.010
0.030 + 0.018
B- B--Gneral Sigmoid
0.626 + 0.009
0.029 + 0.016
Overall, it suggests that methods are very competitive among these in in-processing methods. We leave the comparative study between our methods and other in- in-processing methods for future work. We hope that our supplementary experiment helps people better understand the advantages of our approach.
B.7 Boxplots with General Sigmoid Surrogate
Boxplots for three datasets with general sigmoid surrogate shown in Figure
C Other Related Work
C.1 Fairness-aware Algorithms
Our paper focuses on fairness surrogate functions from the in-processing methods. In addition to the afore- mentioned fairness constraints (Zafar al., 2017a;c) and fairness regularization (Bendekgey & Sudderth, 2021), there are also various kinds of fairness-aware in-processing methods in the community. For example,
31

---

Published in Transactions on Machine Learning Research (04/2024)
0.06
General Sigmoid
Ceneral Sigmoid Billncad Suriogate
Ba unoed Surroguta
0.06
Reduction
Redurtion
0.05
ASR
Falmess
0.04
Faimess
0.04
0.04
0.03
General Sigmod Bullanced
0.02
0.02
0.02
Roduction
0.92 0.93
0.60
0.61
0.62
0.63
0.64
0.65
0.66
Accuracy
Accuracy
Accuracy
(a) Adult.
(b) Bank.
(c) COMPAS.
Figure 7: Results of other in in-processing methods.
1.00
1.00
1.00
0.70
0.76
0.75
Distance
0.00
0.50
Dislance
0.00
0.00
0.00
0.00
0.25
0.20
0.20
0.50
1.00
1.00
1.00
Predicted
Predicted Label
Predicted Label
Adult.
Bank.
(c) COMPAS.
Figure 8: Boxplots for three datasets with general sigmoid surrogate. +1 and -1 represent the predicted label. The red dashed line mcans do (x) = 0. The orange line in the box is the median. The median line and the edges of the boxplot almost overlap with the box itself.
fair adversarial learning (Zhang et al., 2018; Madras al., 2018), fair reweighing (Krasanakis al., 2018; Lahoti et al., 2020; Chai & Wang, 2022: Maheshwari & Perrot, 2023), fair sample selection (Roh et al., 2021a;b), and hyper-parameter optimization (Cruz et al., 2021; Tixpaz-Niari et al., 2022). In addition to DP, there are also fairness-aware algorithms for other fairness definitions, such as sufficiency (Shui et al., 2022a). And there are many other application sconarios, such as medical image analysis (Mchta et al., 2024; Shui et al., 2023).
To gain a comprchensive undcrstanding of fairness-aware algorithms machine learning, thorough surveys are conducted in Mehrabi et al. (2021); Caton & Haas (2020); Hort et al. (2022); Wan al. (2023); Pessach & Shmueli (2023), providing broader view of these algorithms.
C.2 Fairness Surrogate Functions
For CP, even when the empirical covariance equals 0, there is no guarantec whether demographic parity is already satisfied (Zafar et al., 2019; Bendekgey & Sudderth, 2021; Wu et al., 2019; Lohaus et al., 2020). These papers give different counterexamples to explain it. Zafar et al. (2019) provides a simple example explaining that covariance constraints may perform unfavorably in the presence of large margin points. Bendekgey & Sudderth (2021) generates a synthetic dataset and observes that the decision boundary shifts dramati- cally when extreme large margin point is added. Wu et al. (2019) provides two examples, respectively, to show that satislying DDPs and Cous(Ø) constraints are not necessarily related. Lohaus et al. (2020) draws heatmaps to illustrate that some popular surrogates do not manage to capture the violation of fair- ness reasonably. Radovanovié al. (2022) also conducts extensive results to show that optimizing the loss function given the fairness constraint or regularization for unfairness can surprisingly yield unfair solutions for Adult (Kohavi, 1996) and COMPAS (Julia Angwin & Kirchner, 2016) datasets. Instead of presenting the
32

---

Published in Transactions on Machine Learning Research (04/2024)
counterexamples in previous work, systematically point out the large margin points issue for covariance proxy as well as other unbounded surrogate functions with theoretical consideration.
D Extension to Other Fairness Definitions
To begin with, in Section D.1, we review the considered fairness definitions: disparate mistreatment, and balance for positive (negative) class. After that, in Section D.2, provide deeper understanding of CP for disparate mentreatment. The proof of the statements is in Section D.3. Finally, in Section D.4, we provide a deeper understanding of CP for balance for positive (negative) class. The corresponding proof is in Section D.5.
Since the only difference between the linear surrogate and the CP dateset-specific constant, the results this paper about CP also applicable for linear surrogate, As a result, by just replacing the linear surrogate function with other surrogate functions, we can obtain the same results for other surrogate functions.
D.1 Fairness Definitions
D.1.1 Disparate Mistreatment
It is set of definitions based both predicted and actual outcomes. Disparate mistreatment can be avoided if misclassification rate for different sensitive groups of people are the same. It can be specified w.r.t. variety of misclassification metrics and each one corresponds to a kind of fairness definition. Note that it comes out in (Zafar et al., 70),,), and it includes some famous fairness notions, such as equality of opportunity. We list some examples used in this work below:
Overall accuracy equality:
To satisfy the definition, Overall Misclassification Rate (OMR) should be the same for protected and umpro- tected group, i.e.
P(ğ + u/2 1) P(ù + g/z 1).
False positive error rate balance:
To satisfy the definition, False Positive Rate (FPR) should be the same for protected and unprotected group, i..,
P P(O
- = P(O + u/ +1, =
False negative error rate balance:
To satisfy the definition, False Negative Rate (FNR) should be the same for protected and unprotected group, i.e.,
P - 1-y-- P(g + u/æ +1,y=
D.1.2 Balance for Positive (Negative) Class
These two definitions consider the actual outcome as well as the predicted probability P(da(x) > 0/z = +1). Balance for positive class states that average predicted probability should be the same for those from positive class in protected and umprotected groups, i.e.,
P(do(x) > 0/2 = +1) = ((de(x) > 0|z = -1).
Replace dx)x) 0 with (x) < 0 above and we can get the definition of balance for negative class.
D.2 Deeper Understanding the Covariance Proxy for Disparate Mistreatment
In this part, we deal with disparate mistreatment. We denote S certain set depending on each definition of disparate mistreatment. Notice that we have to consider misclassified points. In other words, the true label
33

---

Published in Transactions on Machine Learning Research (04/2024)
Table 3: The corresponding go x) for each fairness definition and the set used for summation. For the first three lines, (Zafar al.; 2017a) only gives the form of go x) and S defaults to the whole training set. We supplement it by providing for each definition. For the remaining two lines, design the specific forms of xy, and 5 for these two definitions. It is extension work for the covariance proxy in algorithmic fairness.
Fairness Definitions
(V. x)
Overall accuracy equality
min (0, ydo (x:)
((1,, yi)l 1, 2......
False positive error rate balance
min (0, 1_ ydo (x))
{(24, M/4) B/: = -1,, 1,,2 = 1,2.... 2....... N
False negative error rate balance
min (0 1+ ydo (x))
{(14, W/3 M// = +1,1 1,2..,,N N
Balance for positive class
(x
{(ri, W:lly; +1, 1,2.,, N
Balance for negative class
dx)
[1r,, 9:)
N]
y should be considered. So go x) is used replace dg(x). First of all, we prove that, with the assumption Do(x) 1, if N Es(z, 2 2)g0 (y, = then it perfectly satisfies the corresponding fairness definition. In the first three rows in Table 3, the specific forms of go(y,)) and S are given for each kind of definition of disparate mintr. It is somewhat similar to (Lohaus el al., 2020) because they also discover that the covariance proxy proposed by (Zafar et al., 2017a) is equivalent to convex-concave surrogates. Secondly, we extend Theorem to these three fairness definitions. Our general sigmoid surrogate can also be used for disparate mint and we leave for future work.
Note that no matter what the definition of disparate mistreatment is, S defaults the whole training in (Zafar et al., 2017a). But contend that it does not match their expected fairness definitions. The authors correct it in (Zafar et al., 2019), so our proof can also serve as an explanation of the correction. Our proof is in Appendix D.3.
D.3 Proof for Appendix D.2
The proof process below is similar to that between the proxy and disparate impact. We provide the proof for the three fairness definitions of disparate mistreatment one by onc. Before the proof, for the convenience of the notation, we divide the training set into 8 groups as follows:
34

---

Published in Transactions on Machine Learning Research (04/2024)
Table 4: 2 = +1
Table 5: 2 -1
Predicted
Predicted
+1
-1
+1
Actual
Actual
+1
TP+
TN+
+1
TP-
TN-
-1
FP+
FN-
-1
FP-
FN-
For looking up different misclassification metrics conveniently, we provide the confusion matrix below:
Table 6: Confusion matrix
Predicted
+1
-1
Actual
True Positive(TP)
False Negative(PN) FOR F. TN
PPV TP TFT TPR = TP+FN
+1
FNR = TP-FN
False Positive(FP) FP FDR TP
True Negative (TN) NPV TN TNNN
FPR FP+TN
TNR TN+EP
D.3.1 Overall Accuracy Equality
Theorem 5. If classifier satisfies + >>=i (2g - Z)go(y: x;) = O, where (o min(0, min(0,yyd(x))), then there holds
Do (x) (x) -=
Equal OMR in protected and unprotected group is equivalent to:
#ign(Do(x)) (gx(D(()))gf()===+
sign(Do(x)), =-1===11
Proof.
go x) =min(0, ydo(x))
y = 9 (correclly classified)
(d)
y + 9 (misclassified)
y = 9 (correctly classified
Dx(x)
y + ÿ (misclassified)
N
1
(2: x),)(y.x:)
N
Σ
(o(x))
N
TN IP.
Σ
2:Do(zz) -2
Σ
Do
N
TN FPN.TN
FNN .PP
1
Do(x.) Σ
Do(xi)
N
FN
TN_
35

---

Published in Transactions on Machine Learning Research (04/2024)
TP+ + TN+ + FP- +N, TP- TN- FP- FFN
E
Do(xi)
N
2
(TP+ + + FP+ FN+)
Σ Do(x.) ( (TP-+ FP_ FN-) Σ TN ,PI
Do(zi)
N2
TN FP
2(TP+ +TN+ +P+ + +FN))(TPPP... +TN- + -P-++NN +FN-)
N
ETN, Do(z:) TP- +TN- + FP- +NN_ TP- +TN+ + FFP + FN++
ΣTN_ PP_ Do(z))
2 +TN, + +FP+ + (TP- + +TN- + FP- + FN-) (Do(x) 971))111==11
Dx(x) ot 11/0)==41) (34)
N2
We set the formula above equal to zero there holds
Dø( 4/0le=+1 (x y=0(==-1
Equal OMR in protected and umprotected group means PÚù + u/a = +1) -P(0 + u/2 = -1), i.c.
TN_+FP_ +TN +FP +FN TP, +PP FFN, It is equívalent to
TN +FP-
sign (Do())) u+ = sign(Do(x)) y=
So we complete the proof.
Corollary 1. We assume that Dx(x) = 1. If a classifier satisfies 1 Ei (z: - z)go(u, = 0, where go(y.x) m0n ydg(x)), then it perfectly meets with overall accuracy equality.
Proof. The method is similar to that for disparate impact. We just substitute Do(x) with sigm(Do(x) and understand that this corollary is true.
Theorem 6. We assume that Dx(x) E E - 7, 7]. Ve 0, if the prozy satisfies:
N
Σ
E)ga(y, xi)
<E
N
2=1
where go (y. x) (dd)), then the violation of overall accuracy equality satisfies:
N
IP =1) P(O v/z
2(TP + +TN + FPP + FN- TN_ FP_ + FN_) Et
TN FPP
TN +FP+
7
TP- +TN_ FP-+FNN
TP++TM +FP+ + FFN
Proof. It connected to the theorem above.
N
Σ
2 - (vg xi) <E
N
1=1
2(TP, + +TN + FP + FN.)(PT + +NN + FP- + FN_)
N2
ETN_FF. Do(xs)
ETNY,F Do(xi)
<E
TP_ +TN +PP FN_ TP, + + +FP, + FN.
36

---

Published in Transactions on Machine Learning Research (04/2024)
ETN_,FP_ Do(a;) TP- TN- + FP- + FNN
ETNL,FP_ Do(as) TP+ + TN2 + FP+ + FN+
N
2(T +TN, + FP+ + (TP + -NN- + + FNN
TN_ +PP-
TN + FP+
TP- +TN + PP- FN-
TP, TN, + PN
N
2(TP+ + +TN, + FP+ FN (TP- + TN- + +P- EP, (Do(z,) 1))
,TN_ (Do(z)) 1I)
(35)
TP- - -NN + FFN TP+ +TN + +PP+ + FN+
If Dx(x) -1-7, + ?/, then Du(x) E 1-7,7/, which means that:
ΣTN- FP. (Do(a;) 1)
ΣTN. (Do(1;) 1)
TP- +TN + FPP +FN-
TP+ TNN + FP+ + FN+
TN + FPP
TN + +FP+ TP, +NN,
TP- +TN- + PP-+ +
)
Notice that:
TN + FP_ PP( # u/ع +1) P(g -1 TP- TN_ FP- FN
TN, + FP, TP, + TN + FP- +FN
So by combining these formulas together and we can complete the proof.
D.3.2 False Positive Error Rate Balance
Theorem 7. S denotes the set of points which satisfy -1 in the whole training set and ge(y. N E(2 ()) x;) = 0, then there holds:
min(0, yd)) Tf classifier satisfies 1
5
(x u ==tly==1 Do -1,0)==1,,==-
Equal FPR in protected and unprotected group is equivalent to:
sign (o()) y =+t1v=-111 (f0 sign(Do(x)) ==
Proof.
go(y, =min(0, 1 ydo
2
ydd(xx)
1
9 = +1 (false positive)
others
(x)
-1 = +1 (false positive)
0
others
1
Σ (2i - 2)go xi)
N
1
Σ
(z (a- Do)
N
PP,.FP_
37

---

Published in Transactions on Machine Learning Research (04/2024)
E 2,Do(ri)= -
Σ Da(si)
N
PP
PPP.PP
1
E
- E Do(xi)
F -
E Dolas)
N
FP4 + PN + FP-+ FN- FP,,PP-
FP+
PP-
2(FP+ (FA)
EEFDDDoum Dolas) Err. Do(a:))
N(PP+ FN, PP-+FN_
FP++FN FP-+FN
2(FP+ + (N))(FP++PN. N(FP++ + + +P-+FNN)
(Do(x) (00l))/0)===1.1==
-Do(x) (+0
(36)
Set this equal to zero and the formula above becomes:
Do (x(x) v+
Do 1+01===1.0---
Equal FPR in protected and unprotected group satisfies
FP_
FP. FP. +FN which means
FP,
sign (x()) y +-+-==11 sign (iggn(s(xx)) ==
So we complete the proof.
Corollary 2. denotes the of points which satisfy y 1 in the whole training set and go x)
min(0, yz)) We assume that Do(x) If classifier satisfies N ((2 z)go(y.x,) 0, then it meets with folse positive error rate balance.
Proof. We just replace (x) with sign(D((x)) prove the result.
Corollary 3. We assume that Da(x) If a classifier satisfies + E xy,) 0, where goly.x) x) = m0, - yda(x)) then it does not meet with false positive error rate balance.
Proof.
2i 2)go(y, xi)
N
Σ
(2, - (o)(z))
N
PP.
1
Σ
(2 -%)
N
FP_
Σ
Σ z
N
PP.,FP
FP,.FP.
(FP + --FF) (FP++FP.) TP. +TN_ + FP, + FNN,
H
N
N
2
CCTPP- + +TN_ FP_ FN.) G(TP, TN, FP, FN+))
(37)
N2
Set this equal to zero and the formula above becomes:
FP
FP_
TP++TN, +P +FN TP- +TN_ FP_ FFN
38

---

Published in Transactions on Machine Learning Research (04/2024)
However, equal FPR in protected and umprotected group satisfies the formula:
FP+ F +N
FP_
FP- +
the two equations do not match. The proof complete.
Theorem 8. We assume that Dx E [1 7, + 71. Ve 0, if the prozy satisfie::
c =)90(U, <e
N
where go (y. x) = min(0, -22 ydo
then the violation of false positive error rate balance satisfies:
N(FP+ +N, + +PP +FN-)
IP( # = +1, = +1,y==1) - P(ù + -1 -
2(FP+ FN+) FNN)
FP_ FP++FN+ FP_ +FN 7
FP+ +
(38)
Proof.
(24 2)g0(y,x.) x²)
<6
N
8
ΣFp, Do(x,)
EFP_ Da(ax))
+F
FP+ + FN
FP- +FN-
2(FP+ (FN. +FN
FP+
FP-
N(FP+ FN+ +FP-+
FP+ + FN+
FP_ FN
2(FP, FN+) FN_)
EFP. (Do(e)) 11 ΣFP. (Do(x:) -
+
(39)
FP+ + FN+
FP-+FN-
If Dx(x) [1 111,,,1 7. 1,1+111 +7,, then Do(x) 1 1- which means that:
EFP, (Do(z)) 1) EFP (Do(z;)-11 FP. + FN+
FP.
FP.
FN PP-+ 7
FP- FNN
Notice that
FP+
FP. FP +N_
P +1, = -1) - -/ FP++FN
So by combining these formulas together and complete the proof.
D.3.3 False Negative Error Rate Balance
Theorem 9. S denotes the set of points which satisfy +1 in the whole training set and go
min(0, yx)) If classifier satisfies & [x () x;) = 0, then there holds:
(x(x) of Do(x) 1
Equal FNR in protected and umprotected group is equivalent to:
39

---

Published in Transactions on Machine Learning Research (04/2024)
Proof.
9o xx) mmin(0, 1 y ydo (x))
ydo
+1, -1 (false negative)
others
- (x(x)
+1,0 = -1 (false negative)
others
1
(ai - xV,0(,,
N
1
Σ -a)=))
N
TN+,TN_
1
Σ DDD(xi)-2 - Σ Da(a;)
N
.N
TN+,NN-
Σ
Do(x;) Σ
Do(z)) TP+ + TN+ + TTP +TN- TN+
TP+ +TN, - F-F
E Do(a:)
N
TN+
TN-
2(TP- + (TN)(TP_+TNN
ΣTN, Dola;)
ETN. Do(as)
N(TP, + TN, +TP_
TP++TN, TP- PP-+TN_
2(TP- TN.)
(f0l - -Do(x) -f
(40)
=
N(T+ +NN + TT-+TNN
Set this equal to zero and the formula above becomes:
D& (10 (=(x))//0===-->>
Equal FNR in protected and unprotected group satisfies TN
TN TP++TN+ TP_+TN_> which means
sign (a(x)) x))
= sign( DD (x)()))) -
So we complete the proof.
Corollary 4. denoles the set of points which satisfy y = +1 in the whole training set and go x)
min(0, 1+ " ydo)))) We assume that Do(x) 1. classifier satisfies n E(z 2)go x;) 0, then it
meets with false negative error rate balance.
Proof. We just replace Dx(x) with sign(Do(x)) to prove the result.
Corollary 5. We assume that Do(x) = If a classifier satisfies N EN 2)go(y, x;) 0, where goly, x) = m0, 1 ydxxx)) then it does not meet with false negalive error rale balance.
Proof.
N (2: (1,xx)
i=1
Σ (Doz)
N
T
40

---

Published in Transactions on Machine Learning Research (04/2024)
Σ
(
N
TN+
Σ
N
TN+,IN-
TN,
(TN+ - TN-)- (TN +TN_) TP+ + + FP+ + FN+ -PP
TN_
FP_ FN-
N
N
2
[T (TP- + TN_ + FP_ +FN_) TTP + +N + FP, + FN.))
(41)
N2
Set this equal to zero and the formula above becomes:
TN+
TN
TP+ + TN+ -FPP
TP- TN- FP- + FN
However, equal FNR in protected and unprotectod group satisfics the formula:
TN+ TP- +TN+ TP- +N
TN-
the two equations do not match. The proof is complete.
Theorem 10. We assume that Dx(x) E [1 7, 1 + 71. VE > O, if the prozy satisfies:
1
(= (===2)90(1) xi) <E
N
where go (y. x) m0n 14" yds (x)), then the violation of false negative error rate balance satisfies:
2
N(TP+ + TN, + TP- + TN-).
IP( # yzz +1, y- +) P μ/ 1, y +1)1
2(TP, + -
TN, TN-
(42)
TP-+TN, TP- +T
Proof.
E (2 x)go(y,
<E
N
ETN. Do(x,)
ETN_ Do(xs)
N(TP- TN, +TP +TN-)
TP+ + -NN+
TP_ +TN-
2(TP + + TN.)
(P
TN+
TN_
N(TP- +TN, TTN-
TP+ + TN+
TP- +NN
2(TP, (TN-)(TP- +TN_)
ΣTN, (Do(a,) 11 ETN (Do(z;) -1 1)
(43)
TP++ +TN
TP- + TTN
If (x(x) E - 1,1+%) +7],
then Do(x) - 1 [1 which means that:
ETN. (Do(xs) 1) Erv. (Do(1:)-1) -11] TP. +NN+
TN- + TP, +NN TP- +TN_
TN_
TP- + +NN
Notice that
TN
TN_ TP- + TN
PP + w/= = - =
TP, + TN.
So by combining these formulas together and complete the proof.
41

---

Published in Transactions on Machine Learning Research (04/2024)
D.4 Deeper Understanding of the Covariance Proxy for Balance for Positive (Negative) Class
In this section, we deal with balance for positive/negaatie class. These two fairness definitions prepared for probabilistic classifiers, which are different from previous issues, Many probabilistic classifirs do not model the decision boundary directly, so it is hard to relate the proxy to these two definitions. To solve this problem, we creatively link do (x) and the prediction probability P(de(x) > 0 = +1) together using an assumption.
To begin with, we first consider the relationship between dx(x) and the prediction probability P(do(x)
0| +1). Imagine that there exists decision boundary for probabilistic classifiers. For probabilistic classifier, the positive prediction result is the same as P(do(x) > 0/ +1) > 2 i.e., P(do(x) > 0 = +1) 3 > O. Similarly, for margin- classifiers, it is equivalent to dg (x) > Thus, do(x) and (xdg(x) 0/2 +1) share a similar relative trend, but the values of them are not in the same range. dx(x) R while (x) > 0/ = +1)
E 2-
This suggests that we can view probabilistic classifiers as special margin- based classifiers, They find the location of the decision boundary, and the same time, learn a mapping f 2. 2] from dg dx(x) P(dg(x)= > 0/2 = +1) 2/2 In other words,
1 f(do(x)) = ((da(x) > 012=0 = +1) 2
It is challenging to find the mapping f directly. However, intuitively, we know some properties of it. is a bounded and monotonically increasing function which passes through the origin. Thus, we can design a function é to approximately reflect the trend of f. For example, Φ(x) = =(x)- We assume
1 ((dx(x)) (xds(x) 0 +1) ~'
and prove that if 1 -))0(=) x,) O, then it perfectly satisfies the corresponding fairness definition. The specific forms of S and go x) for these two fairness notions are shown in the last two lines in Table 3. To the best our knowledge, we are the first to connect. the proxy these two definitions. Please refer Appendix D.5 for proof details.
N
Although the assumption is strong, we aim to provide the basis for future work about how to choose suitable @ to approximate f. thereby inspiring the research community. We believe that it can be an interesting direction of future work for these fairness definitions based on predicted probability.
D.5 Proof for Appendix D.4
D.5.1 Balance for Positive Class
Theorem 11.
denotes the set of points which satisfy y +1 the whole training set and go x)
[-2 11 and it is an odd 14 (x). We assume that ((do(x)) (x) 0/2 +1) 2. where & R ++ 1-
function. If classifier salisfies N Es(z 2)0(go x.)) = 0, then it perfectly meets with balance for posilive class.
Proof.
+ y
go(u, x)
dx(x)
2
(x(x)
y == +1 others
0
Do(x)
y - +1 (true positive)
-Do(x)
y= +1 -1 (false negative)
others
42

---

Published in Transactions on Machine Learning Research (04/2024)
1
(2t 2)0(g0(y,x)) x:))
N
5
(a (==2)o(do(z)))
N
TP,, "N,,NN,,TP.I1
(z - (D)((t))) - E (===))((D((a))
TTP
TN .N
Σ (()=)((D(())))- Ea (d-
E ((-1= -(-1-3)(D0(s))
PP-
TN+
TP-
TN-
(1 2)
Σ o(Do(ae))
Σ ((Do(12)) +(-1-2)
Σ
(Doola)))
Σ
N
TP+
TN-
TP
TN
2(T + TN,, +PP +NN-
N
(TP- +NN)
Σ
((DoZz) - [D(o((z))) - +TN+
Σ TP
o(Do(zi))
Σ
o(Do(z)))
TP
TN
TN
(44)
Note that TP+ + TN++TT+ +TN represents the number of points in the training that belong to the positive class, it is constant. Set this formula equal to zero and it becomes:
ETP, o(Do(z.)) - -ErN, ((Do(z.)) Erp. d(Dolz)) -Erx. ((Do(z;)) TP+ + TNN
(45)
TP- +TN
We notice that:
ETP, ((Do(z)) - ETN, o(Do(zi)
((do(I;) +1
TP+ + TTN Etp. o(Do(z:)) - -Ern- o(Do(zi))
Φ(dr(I;)) :-1
TP- +TN-
so if ((do(x)) = P(do(x) > 0/= =
= +1) 2/4 then:
P(do(x) > 0/2 0|2= +1) ΣTP. ((Do(a:)) - -ENN, ((Do(z))
+
TP- +P++TN
2
P(do(x) > 0/2 -1) Etp. ((D((z)) - -ErN- ((Do(a)))
(46)
TP- +TN-
With the equations (45) and (46), we get:
((do(x) > 0|2= +1) 1)= P(do(x) > -1)
which perfectly meets with balance for positive class. The proof is complete.
43

---

Published in Transactions on Machine Learning Research (04/2024)
D.5.2 Balance for Negative Class
Theorem 12.
S denotes the set of points which satisfy = -1 in the whole training set and go x) 1 (x)) We assume that (x)) = (x)o(x) < == =11 1/2 where & R R [-2. 2] and it an odd
function. If classifier satisfies N Σ (24 (yo x:)) = 0, then it perfectly meets with balance for negative class.
Proof.
- y
go (v,
do (x)
2
dx(xx)
y =-1 others
0
do(x)
- 1, +1 (false positive)
dx(x)
y = -1, = (true negative)
others
(z 2) Φ (go (v.x:))
N
S
Σ
(z) (Do (x:))
N
FP..ENN.
Σ
(Do
E () (x:))
N
FP.
FN+,FN-
1
Σ 2 - Σ () (xii) Σ
(Do (x:)) Σ 2)
(51-2) (x:))
N
FP+
FN-
FP-
FN-
1
(1 (1-Z)
Σ (Do Σ (Do()))) +(-1-2)
Σ
(Do Σ
(Do (Do (T.))
N
FPI
FN
FP
FN
2 (FP+- + FN+ FP- +FN-)
N
(FP_ - FN_)
Σ (DDo
Σ (De (FP+ FN+) FN+
Σ FP
s (Do (Do (zi)) - E
(Do (Do(ttt)) (x.)))
FPP
FN
(47)
Note that FP- + +F++FFF FNN represents the number of points in the training set that belong to the negative class, so it is a constant. Set this formula equal to zero and it becomes:
Erp, ((D((x:)) - ErN, (DD(())) Err. ((Do(s,)) - Errn ((D((z))) FP+ + FN+
(48)
FP-+FN
We notice that:
Epp, ((Do(ai)) EENN, )(Do(z:))
(d)(x)) ==t
FP, FFN
44

---

Published in Transactions on Machine Learning Research (04/2024)
EFp. o(Do(zi)) -FNN @(Do(r)))
((dg(x)) 6=-1
FP- FN-
so if ((do(x)) = P(do(x) < 01===111 - 2) then:
P(do(x) < =0 = +1) EFp, ((Do(I.) - -EPN, o(Do(a,))
1
FP+ + FN+ P(do(x) <0 -1) ΣFp. o(Do(z,)) - EEN ((Do(z:))
1
FP- PP+F
With the equations (48) and (49), we get:
P(do(x) < 0/2 = +1) P(do(x) < <0 = -1)
which perfectly meets with balance for negative class. The proof is complete.
7
E Further Analysis
We provide some interesting results and analysis about this rescarch. While the analysis may not have a direct impact on the main body of the paper, they could serve as potential directions for further exploration.
E.1 Fairness Surrogate Functions in the Future
The goal of fairness surrogate functions in this paper is to approximate the indicator function. As can be seen in Figure 1, we propose the general sigmoid surrogate to better approximate it comparing to existing surrogate functions. However, in practice, the effect of surrogate function is also related to the dataset. We believe that more complex and even dynamic no-linear functions can used. Such no-linear mapping can be learned hope that our work will help researchers better understand the fairness surrogate functions. We also hope that have inspired interested researchers invent fairness surrogate functions that can automatically fit the data distribution. We leave such interesting exploration for future work.
neural network to automatically fit the flexible and complex mapping for each datasot. We
E.2 The Insights for Large Language Models
Recently, as the capabilitios of Large Language Models (LLMs) have increased, they are remarkably powerful, transcending traditional boundaries in technology and innovation (Achiam al., 2023; Touvron el al., 2023). These advanced models harness vast amounts of data to understand and generate human-like text, solve complex problems with nuanced insights, and even create content that feels genuincly human-crafted (Liu et al., 2023b). Their applications span from enhancing natural language processing to driving advancements in fields like healthcare (Thirunavukarasu et al., 2023) and education (Kasneci et al., 2023), showcasing a transformative potential for both industry and society at large. While LLMs' fairness has become a focal point of widespread attention (Wang et al., 2023), one may ask how the insights in this paper can be extended to LLMs..
Generally, adapting the conclusions from this paper to large language models (LLMs) involves recognizing the complexity of biases these models can inherit from datasets (Brunet et al., 2019). For LLMs, identifying biases requires sophisticated analysis tools that understand language use and cultural contexts. To our knowledge, this issuc remains an unsolved challenge and has not yet been thoroughly explored (Li et al., 2023; Liu et al., 2023a). Addressing these biases involves not just algorithmic adjustments, but also curating training data, refining model architectures, and implementing continuous feedback loops to identify and mitigate bias. This approach may even emphasize the need for multidisciplinary efforts, combining technical, ethical, and social perspectives to enhance fairness in LLMs. Also, the task considered in this paper is discrininative, while L.LM is widely used in generative task. Machine learning focuses algorithms
45

---

Published in Transactions on Machine Learning Research (04/2024)
learning from data to make predictions decisions, whereas natural language processing (NLP) involves understanding, interpreting, and generating human language.
Although addressing unfairness in LLMs is crucial but goes a long way, we believe that some insights in this machine learning paper is also beneficial and enlightening for the NLP community. For example, our theoretical analysis highlights the risks of unbounded functions causing instability. Tt reminds us that when we pre-train LLMs or conduct Al alignment, we may consider some theoretically bounded loss function to mitigate drastic fluctuation during training. Techniques like gradient clipping are also recommended for theoretical analysis as well as the experiments also shed
stability (Mai & Johansson, 2021). Furthermore, light on the advantage of balanced datasct. Additionally, our findings emphasize the benefits of balanced datasets, suggesting that pre-training language models with data balanced across sensitive attributes may enhance fairness. Also, we may need careful consideration of data proportions in reinforcement learning from human feedback when we align LLM with human values, particularly fairness.
E.3 Biased Estimation of CP
It serves as a further analysis of CP. But because of the limited space, it does not appear in the main paper. The original CP is Cov [[ 2)dg(x)], where is the mean of over the training set. The expectation can not be computed directly, so its empirical form Cov = # Σ (z, - F)do (x;) is proposed to estimate the expectation. We found that Coe mentioned earlier a biased estimator of Cov. The unbiased one is
N-I -=>d(<x)))(( (x.). The proof of can be found in Appendix E.4. But does not significantly impacts the results since N is large in the reality.
First, we will give some preroquisites for the proof. The expectation of 2x)o(x;) is different for i and j:
B(2d6(x)) Es [x(d(())) i i
i=
B(z,do(xy))
(49)
Because if i = j, each 2x;) is independent of each other, so in this case, E(z,do(x))) = E(=do(x)). If * j, then 24 and do(x;) are independent, so we derive that E(z,dg(x,)) = Ez (x)).
It frequently used the proof later. With this, now we can start the proof.
E.4 Proof of Section E.3
Proof.
N
E
N
1=1
1
B (22))(xx)))
Σ
B[Zdg
N
N
N
=E(2do (x))
El(
2g (x,))
N
N
iml
j=1
1
=E(2do (x))
Ei2 do (x,))
N
1
1
-E(2d6(x))
Ezg Exo(x;)
N2 N B[)d
N
1=1
1
N-
=E(2((x))
Ez Ede(x)
N E[2do (x))
N
46

---

Published in Transactions on Machine Learning Research (04/2024)
N [B(zd((x)) 1Ez [x)]
N Cov.
(50)
Also, we show the risk bound of Cov is O (xx)) below.
Theorem 13. We assume that Dx(x) is bounded by B, i.e., Do(x)= S 3. Then for a given constant 5 > 0, the inequality below holds:
P P(Cov Coou st) 1 - 6,
Cool
where t
V 1282 In
N V 1y-
Proof.
N
(2 -2- 2)do()) E [LB,U UB]
N
N (2 - (x)do(x)) 2 N (0 (0-2)82 2 N
N
- 3 = LB(Lower Bound)
N
N
N
N (2: - 2))o(x;) S N -
(1 - -)
3 U BUppre pper Bound)
N 1
According the Hoeffding incquality,
Pl|Cou- Cool 1 20)11 2exp (UB I.B)2
-2
-(N - 1)2t2
1 - exx
2N
Let exp
2 2N
), we get that t 288 In 3 / VN
N 0 7
E.5 When are CP and General Sigmoid Surrogate Close to Each Other?
We show that the number of large margin points determines how close the general sigmoid surrogate is to CP. Under mild conditions, if there are limited number of large margin points, then the general sigmoid surrogate is close to CP. Our general sigmoid surrogate is designed to address large margin points. However, when these points are scarce or even nonexistent, general sigmoid surrogate becomes close to conventional method like CP.
In the domain fair machine learning, numerous studies have consistently underscored the pivotal role of data (Mchrabi et al., 2021: Caton & Haas, 2020), with a particular focus on theoretical insights (Chen al., 2018; Lipton al., 2018; Dutta et al., 2020). From this perspective, the theorem underscores the importance of data, suggesting that if can mitigate the impact of these large-margin points either before during the model training process, it may also contribute to the better accuracy and fairness even don not use general sigmoid surrogate. This theorem expresses the following vision for data-centric AI (Zha et al., 2023): If we can deal with the data very well, maybe we do not have to use complex or even sophisticated algorithms that requires careful fine-tuning.
Thcorem 14. We assume that l points satisfy G(Do(x)) E [S. and others satisfy G(Do(x)) [0, <), then there holds:
&
2 w (oo(2,d((x)) - Coo(z, G(dg(x))) < 0(m) + (1 1 )(())
(51)
47

---

Published in Transactions on Machine Learning Research (04/2024)
where Q(x) = -ww--G(r) The proof is provided in Appendix E.6. The key motivation of Theorem 14 is that the general sigmoid function is close to linear function when approaches 0. If [Cov(z, do dx(x)) <, which means that w0wCo da (x)) S we. Then we have [Cou(z, (((d(()))) S ] we + A Q + +(1 (1- ((())
Remark. Taking Figure 2(b) as an ezample, the result show that & 5.12%. 2. If we choose w = 3, then for the right hand side of (51), we have [Q(H) + (1- N (Q(() 0.038, which means that the results of bounding the general sigmoid surrogate and bounding CP are close to each other.
E.6 Proof of Theorem 14
Proof. To start with, notice that
sign(x) = 21 x>0
where sign(x):
13 returns the sign of x. So we can replace Ldo(x)>0 with sign(d)(x)) (x)) in (2).
have
Nia
N
DDPs
N1a + Now NI + Not
Nia- Nua N16 Nob
2 Nia + Nos No6 + Nos
ENia sign(do(x)) ENio sign(de (x)) (x)))
Nia + Noa
Nis Nos
EM sign(de(x)) ENi..o. sign(de(x))
x
(52)
Nia + Noa
No + Nos
Furthermore, we can design new family of surrogates & to approximate the sign function instead of the indicator function. They are cquivalent to each other, but an odd function is more convenient for the proof. So we use G(x)) = (wrr) - instead of G(x) o (wr) in our proof.
Before the proof, we first review some properties of general sigmoid surrogate. We notice that we have lim
dG(x) 2wg(wx) dr
1
2
where g(x) = (1te=j So the theorem is intuitively reasonable because when & approaches 0, the gradient approaches a fixed number, and thus the function itself approaches linear function. Now we start the proof.
We know that g(x) monotonically increases when S 0 and decreases when æ >> O. So g(x) S g0 = 1 Now we consider a linear function L(x)= = wx and let Q(x) = L(x) - G(x)) to measure the gap between the two functions. So we have
dQ(x) dr 2 2wg( wx)) s 0,
which means that Q(x) monotonically decreases in R. Notice that Q(0) 0, we have Q(x) S when 2 0 and (xx) 2 0 when < O. And Q(z) is odd function because Q(-z) -Q(x). According to these properties of (ar), we know that [Q(x)] monotonically increases in [0, +o0).
Then there holds:
N
1
W
Σ
(2 Z)do(xi)
Σ
(2 =)G((((xx))
N
1=1
N
Σ
(2: 2) (vd((x))) (x))(x))))
N
Σ
12g 2
(udo(x;) - GG(ob(x;)
N -
48

---

Published in Transactions on Machine Learning Research (04/2024)
N
wdd (x,) - G(d)(x)))
N
2
1
(x(d)(x)))
N
1=1
1
Qx)o(x)))
1
< N - 1 [kQ(M) + (N - =)Q(())
b: Q()) (1 k
N )(())
(53)
The proof is complete.
49


Reviews:
[{"review_id": "iEYoJUgHDi", "reviewer": "Reviewer_AFbU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. The writing in this paper is very clear, making it easy to understand.  \n\n2. The motivation behind this study is well-defined. It addresses how current algorithms tackle fairness issues by employing the conventional notion of demographic parity in a constrained optimization framework. The paper provides a theoretical critique of these methods, pointing out their tendency to produce unfair solutions. As a response, it introduces a theoretically solid surrogate function for fairness and develops an algorithm that leverages this function. The theoretical foundation for the motivation is robust, and the efficiency of the proposed algorithm is convincingly demonstrated.  \n\n3. The experimental results validate the method's efficacy and establish a solid groundwork for future research.\n\nWeaknesses\n\n1. Although this paper aims to address the surrogate-fairness gap and variance issues with demographic parity, I think more discussion is needed for other fairness criteria to enlarge the impact of this paper.\n\n2. The conditions required for the theoretical analysis should be combined with practical cases. I think this paper needs more discussion of the real-world scenarios.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Previous studies have revealed that machine learning algorithms can generate biased outcomes for certain population groups, particularly those identified by sensitive features. To tackle this problem, some research has introduced the concept of demographic parity and developed algorithms that aim to balance the learning goals with fairness constraints. However, these approaches can sometimes lead to outcomes that are still biased. This paper demonstrates a significant issue: the existence of a gap between the intended fairness definitions and the surrogate functions used to approximate fairness. As a result, current algorithms might not effectively minimize disparities among different groups. Moreover, this paper highlights the negative effects of using unbounded surrogate functions on the stability of these solutions. To overcome these challenges, the paper introduces two innovative approaches: a theoretically grounded surrogate function for fairness, termed the general sigmoid, which comes with upper bounds for demographic parity and variance, and a new algorithm known as the balanced surrogate. This algorithm is designed to iteratively narrow the fairness gap throughout the training process. Comprehensive experiments validate the efficiency of the proposed methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I believe the figure could benefit from being slightly enlarged to enhance its clarity.\n\n2. The conclusions of this paper can be adapted to explore fairness concerns within large language models, offering insights on identifying and addressing biases in these systems. Authors are encouraged to discuss it.\n\n3.  In section 4.1, we need some intuition and clarifications to understand how to build the surrogate-fairness gap between DP and CP.  \n\n4. Could we use other non-linear functions to replace with sigmoid in section 5.1?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "SOzSGaoscd", "reviewer": "Reviewer_SXtY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths:*\n1. To my knowledge, the study of the surrogate-fairness gap, as well its theoretical study, are new. This gives insights regarding a multitude of empirical observations from previous works.\n2. A new class of surrogates is proposed, which allows to fix, to a certain degree, the large-margin issue.\n3. An empirical method is then developped to reduce the surrogate-fairness gap, with particular emphasis on group imbalance.\n4. Empirically, it is demonstrated that the proposed method results in improved fairness with similar accuracy against other fairness-surrogate-based methods.\n\n*Weaknesses:*\n1. The proposed approach can require significant additional hyperparameter tuning (need of tuning two more hyperparameters, $w$ and $\\lambda$). It is not so clear how this would interfere with the usual hyperparameter tuning, that can itself promote fairness (see e.g., [1-2]).\n2. The \"instability issue\" is not so convincing. In particular, using bounded surrogates that make the empirical covariance bounded in [0, 1] only partly fix the problem: bounding a difference of probability by a value between 0 and 1 is not always informative.\n3. Empirical evaluation of the method focuses on methods that use fairness surrogate. While it is true that the proposed method compares positively to fairness-promoting methods of the same type, many alternatives exist. It would be appreciated if authors can briefly compare with one or two of these methods (e.g., reweighting-based methods, that, similarly to the approach proposed in 5.2, reweight samples based their sensitive attribute, see [3-4] and references therein).\n4. The paper is not always very clear, and clarity of exposition could be improved (see Requested Changes section).\n\n*Question for mathematical derivation:*\n- In the proof of Theorem 4, after the sentence \"Finally, because of the fact that\": samples are drawn independently so covariance is indeed zero, but the expectation of the product becomes sum of expectations, which seems to be an error. I believe similar (although a bit different) results can be achieved even with fixing this error, but it should be fixed.\n\n*References:*\n\n[1] Cruz, André F., et al. \"Promoting fairness through hyperparameter optimization.\" 2021 IEEE International Conference on Data Mining (ICDM). IEEE, 2021.\n\n[2] Tizpaz-Niari, Saeid, et al. \"Fairness-aware configuration of machine learning libraries.\" Proceedings of the 44th International Conference on Software Engineering. 2022.\n\n[3] Krasanakis, Emmanouil, et al. \"Adaptive sensitive reweighting to mitigate bias in fairness-aware classification.\" Proceedings of the 2018 world wide web conference. 2018.\n\n[4] Maheshwari, Gaurav, and Perrot, Michaël, FairGrad: Fairness Aware Gradient Descent, TMLR 2023.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the impact of using surrogate functions for fairness. It unveils the *surrogate-fairness gap* phenomenon, showing that common surrogates are increasingly biased as points are classified with larger margins and sensitive groups are imbalanced. The paper introduces a new class of surrogate functions, that are less sensitive to the large-margin issue, together with a procedure to better handle imbalanced distributions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. It seems that there is a problem in the proof of Theorem 4 (see previous section). Can the author either explain (i) why the current derivation is true, or (ii) fix it?\n2. The paper is quite difficult to read, in particular:\n   - The three issues, (i) fairness surrogate-gap, (ii) instability and (iii) large margins, are of different nature. It seems that the true problem (which, I believe, is very interesting and informative) studied in the paper is the fairness-surrogate gap. Then, instability and large-margin points are only factors that influence the gap.\n   - The proposed methods are not always clearly introduced. For instance, Eq. (2), that introduces a major contribution of the paper, is introduced without discussion and look like a small digression.\n   - Notations are not all defined, or are difficult to follow. In particular:\n     - Sums like $\\sum_{N_{1a}, N_{0a}}$ (e.g. in Eq. (2)) are not properly defined (what is $x$, $x_i$?).\n     - DDP surrogate depends on the choice of $\\phi$ and on the data, which is not clear from the notation. Additionally, Eq. (5) is not properly defined. Should it be the sum over empirical values $x_1, \\dots, x_n$, or population loss?\n     - In Appendix, it seems notations $U_{1a}$, $U_{1b}$, $U_{0a}$ and $U_{0b}$ are not defined.\n     - Notations A, B, C, D, E, F, G, H in Appendix B.4 are quite confusing, why not use FP etc.? Similarly, the $\\bar{prob}_{criterion}$ notation is sometimes confusing.\n   - Appendix is difficult to read, with proofs being delayed and delayed between different sections of the appendix.\n   - To me, sentences like \"To date, according to Google Scholar, this article has garnered over 1,000 citations.\" sound a bit odd in a research paper.\n   - The sentence \"So there is no guarantee whether DP is already satisfied even when the empirical Cov is minimized to zero\" it not clear: there is some level of guarantee, provided surrogate-fairness gap is small (which we are not able to control).\n3. Some related work is missing, in particular regarding hyperparameter tuning and reweighting to handle imbalanced group (see references in Weaknesses section).\n4. Regarding empirical evaluation: I would appreciate to see comparison with a fairness-promoting method that is not based on surrogates. Nonetheless, I understand this requires additional work, and this is not so critical regarding acceptance.", "broader_impact_concerns": "No ethical issues are discussed within the paper, and I'm not sure it is relevant to discuss it. Although not critical, it could possibly be mentioned that proper understanding of the surrogate-fairness gap can prevent malicious parties from claiming a method they use is fair, while it only guarantees results on a fairness surrogate.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tzVVWDR9UY", "reviewer": "Reviewer_oKgk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nThe paper rigorously analyzes the surrogate-fairness gap, deriving the upper bound of the gap for the proposed general sigmoid surrogate under certain conditions. It is particularly noteworthy that it further derives a bound under a related condition. The experiments demonstrate the efficacy of the general sigmoid surrogate.\n\nWeakness:\n\nIn most theoretical results of the paper, the covariance proxy $\\hat{Cov}$ rather than $\\tilde{DDP}$ is analyzed. For example, Proposition 1 shows the gap between $\\hat{DDP}$ and $\\hat{Cov}$, and Theorem 1 shows the upper bound of $\\hat{DDP}$ given that $\\hat{Cov}$ is bounded. This is not very intuitive since $\\tilde{DDP}$ is a direct surrogated approximation to $\\hat{DDP}$ and people may be more interested in the gap just caused by applying the surrogate function. \n\nProposition 1 shows the gap between $\\hat{DDP}$ and $\\hat{Cov}$. However, the surrogate-fairness gap is a term that also depends on the decision model and the surrogate function. In other words, the surrogate-fairness gap may be correlated with $\\hat{Cov}$. This makes the proposition less meaningful as it is not that clear that minimizing $\\hat{Cov}$ cannot minimize $\\hat{DDP}$. Ideally, we may expect the gap to be independent with $\\hat{Cov}$. \n\nIn Section 5.2, the authors propose a method for minimizing the difference between $\\hat{DDP}$ and $\\tilde{DDP}$. I am confused about the purpose of doing that. Since $\\tilde{DDP}$ is added as a regularization in the loss function, it will not be minimized during training. Instead, the learning algorithm will try to find a balance between the empirical loss and the fairness regularization. In that case, why do we want to make $\\tilde{DDP}$ exactly equal to $\\hat{DDP}$? It suffices to use the upper bound of $\\hat{DDP}$ as the fairness regularization.\n\nThe surrogate function is closely related to the risk bound of the optimization, i.e., whether the true loss can be optimized when the surrogated loss is minimized. The authors may also comment on that regarding the proposed general sigmoid surrogate.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the gap between the true fairness metric and the surrogated fairness metric in fair machine learning. The paper specifically studies the covariance proxy and theoretically proves the gap. The paper also identifies two additional issues, namely instability and the large margin point issue. The paper then proposes the general sigmoid surrogates and proves the upper bound of the true fairness. Insights are drawn from the bound. Finally, the paper proposes a balanced surrogate approach by minimizing the gap iteratively during training. Experiments show that the proposed general sigmoid surrogates can achieve better fairness performance. The balanced surrogates, however, may or may not improve fairness across different cases.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "What is the difference between $DDP$ and $\\hat{DDP}$? Is $\\hat{DDP}$ an estimation of $DDP$ based on the data? Please clarify that.\n\nUsing the number of citations to demonstrate the importance of a fairness metric is not considered professional in a research paper.\n\nThe authors may comment on the influence of the general sigmoid surrogate on the risk bound.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackled an important issue in algorithmic fairness - how to measure unfairness. Most existing algorithmic fairness papers simply claim that fairness is improved by smaller fairness surrogates value. Does this really improve the actual fairness? This paper considered the gap between the surrogate fairness metrics and actual fairness. Detailed theoretical analysis and experiments are conducted. 

**Decision**: All the reviewers appreciated the paper and voted for acceptance. This AE supports this decision.
Decision: Accept (poster)