Fair Classification with Efficient and Post-hoc Controllable Fairness-Accuracy Trade-off Maaya Sakata∗1,2 and Kazuto Fukuchi†1,2
arXiv:2606.28097v1 [cs.LG] 26 Jun 2026
1
University of Tsukuba, Japan 2 RIKEN AIP, Japan June 29, 2026 Abstract
Post-hoc controllability of fair machine learning models, the ability to control the trade-off between fairness and accuracy after training, is valuable for practical deployment. Existing post-processing methods provide such post-hoc controllability but often suffer from significant accuracy degradation, whereas in-processing methods achieve efficient trade-offs but require computationally expensive retraining for each change in trade-off ratio. To achieve both post-hoc controllability and efficient trade-offs, we propose a novel fair classification algorithm that learns effective feature representations to improve the trade-off efficiency of post-processing fair classifiers, by a gradient-based optimization approach. Experimental results on real-world datasets demonstrate that our method achieves trade-off efficiency comparable to, or even surpassing, in-processing methods, without requiring any retraining.
1
Introduction
While machine learning (ML)-based systems play a critical role in real-world decision making across various domains due to their strong predictive performance, these systems can suffer from inherent biases that lead to unfair outcomes. Indeed, many researchers have reported discriminatory outcomes of real-world ML-based systems against certain protected groups, such as those defined by gender, race, and age. For example, Amazon discontinued the development of an ML-based hiring system after it was found to exhibit gender bias (Dastin 2018). Similar issues have been reported across various domains, including hiring (Fabris et al. 2025) and criminal justice (Angwin et al. 2016). Mitigating these biases in ML systems is in high demand; however, it must be achieved while carefully managing the trade-off between predictive accuracy and fairness. Accuracy and fairness are often in tension, as improvements in fairness may come at the cost of reduced predictive performance. In practice, high accuracy is critical for business utility, including long-term user retention and profitability, whereas fairness is essential for meeting legal requirements and maintaining public trust in the systems and their owners. Therefore, ML systems should be designed to enable administrators to flexibly adjust the balance between accuracy and fairness according to their operational needs. ∗ [email protected], Corresponding author † [email protected], Corresponding author
1
Motivated by these demands, many researchers have developed fair ML frameworks that enable control over the fairness-accuracy trade-off through a prescribed parameter. For instance, some approaches enforce the fairness by incorporating the constraint on the permissible level of unfairness into the training objective, where the trade-off is controlled by specifying a predefined unfairness limit (Zafar et al. 2017; Celis et al. 2021). Other approaches penalize the training objective by the degree of the model unfairness, allowing the trade-off to be adjusted via a multiplicative penalty parameter (Olfat et al. 2020; Bendekgey et al. 2021; Yang et al. 2023). In both cases, the resulting model is strictly tailored to the specific trade-off parameter chosen at the outset of the optimization process. The desired trade-off between accuracy and fairness may need to be adjusted after a model has been deployed. The following example underscores the practical importance of enabling post-deployment adjustment of the accuracy–fairness trade-off. Example 1 (Regulatory Compliance in LLMs). Consider a scenario involving the deployment of a Large Language Model (LLM). A company may initially set a trade-off parameter δ1 to align with existing AI guidelines. Suppose that several months after the service begins, the guidelines are updated to mandate stricter fairness standards, rendering the original setting δ1 non-compliant and necessitating an update to a new parameter δ2 . However, retraining the model to accommodate this shift is often practically impossible due to the immense computational investment required. For models of this scale, retraining the entire network solely to adjust a trade-off parameter is economically and practically infeasible. We refer to the ability to modify the trade-off after training as post-hoc controllability of the fairness-accuracy trade-off. Existing fair machine learning approaches either lack post-hoc controllability or achieve it only at the cost of an inefficient fairness–accuracy trade-off. For example, post-processing–based fair learning algorithms achieve fairness by adjusting a trained model and therefore provide post-hoc controllability. However, they often suffer from a suboptimal trade-off efficiency (Woodworth et al. 2017). In contrast, approaches such as in-processing methods enforce fairness during training and can achieve highly efficient trade-offs, but adapting to a new trade-off parameter typically requires costly retraining the model. Our contributions The primary goal of this paper is to develop a fair classification algorithm that enables the post-hoc controllability of the fairness-accuracy trade-off while maintaining high trade-off efficiency. Our contributions are summarized as follows: • We theoretically analyze the accuracy improvement of post-processed classifiers when the required fairness level is relaxed and characterize the intermediate feature properties that governs trade-off efficiency. Specifically, we show that post-processed classifiers achieve more efficient trade-offs when features are more concentrated near the decision boundary of the most fair classifier. This theoretical result provides a guiding design principle for our proposed method. • We develop a novel representation learning algorithm, Guidance to Fairest-Boundary (GFB), to improve the trade-off efficiency of post-processed classifiers. Motivated by our theoretical analysis, the learning objective penalizes the distance of features from the decision boundary of the most fair classifier. The resulting formulation leads to a bi-level optimization problem. • We develop a practical gradient-based optimization procedure to solve the proposed bi-level learning problem. Specifically, we adapt the Moving-Average SOBA (MA-SOBA) (Chen et al. 2024) algorithm to our setting and address the challenge of computing gradients for the proposed
2
learning objective. • We conduct experiments on real-world datasets to compare our method with the existing inprocessing and post-processing approaches. The results show that our method consistently outperforms the post-processing baseline by achieving more efficient fairness–accuracy trade-offs, while also attaining competitive performance relative to in-processing methods without requiring computationally expensive model retraining.1 All omitted proofs are deferred to the appendices.
2
Related Work
As fairness requirements or operational policies are likely to evolve continuously in practice scenarios, post-hoc controllability is essential for real-world deployment. From this perspective, post-processing methods naturally provide the post-hoc controllability, as they allow trade-off parameters to be adjusted at inference time. A representative class of approaches assigns group-specific thresholds to the prediction scores of a trained classifier to satisfy prescribed fairness criteria (Menon et al. 2018; Pathiraja et al. 2023; Xian et al. 2023; Zeng et al. 2024). However, the theoretical analysis by Woodworth et al. (2017) shows that under the constraint of equalized odds, one of the fairness definition, post-processing cannot achieve optimal accuracy. This limitation is unlikely to be specific to equalized odds and may also arise under other fairness metrics. Similar post-processing ideas are extended to regression problems. For demographic parity constrained regression, Chzhen et al. (2022) fully characterized the fairness-risk trade-off in a minimax sense. Building on this line of work, Fukuchi (2025) further showed that, under demographic parity, the entire family of minimax-optimal predictors can be generated via post-processing from a single meta-optimal predictor. In contrast, for classification problems, a complete characterization of the demographic parity trade-off remains open, with existing results limited to special settings (Zhao et al. 2022). In-processing methods can achieve efficient fairness-accuracy trade-offs by explicitly incorporating trade-off parameters into the optimization process, but they generally lack the post-hoc controllability. For example, some methods enforce fairness through optimization constraints (Zafar et al. 2017; Donini et al. 2018; Cotter et al. 2019), while others introduce penalty terms into the loss function to discourage fairness violations (Kamishima et al. 2012; Fukuchi et al. 2013; Baharlouei et al. 2024); in both of cases, the trade-off parameters are embedded in the training process. Additionally, some approaches obtain efficient trade-offs by leveraging multi-objective optimization (Liu et al. 2022) or bi-level optimization (Yazdani-Jahromi et al. 2024), where the trade-off is governed by a predefined parameter. Adapting these methods to a new trade-off parameter typically requires full retraining of the model, posing a significant barrier to flexible deployment. Recently, Taufiq et al. (2024) applied the YOTO framework (Dosovitskiy et al. 2020) to fair machine learning, enabling efficient and post-hoc controllable trade-offs with a single model. By explicitly conditioning the model on the trade-off parameter, YOTO allows a single model to approximate the entire Pareto frontier without retraining separate models for different trade-off setting. However, this flexibility comes at the cost of increased model complexity. In particular, YOTO-based approaches inherently require substantially larger model capacity to realize their full potential. Empirical results reported in Dosovitskiy et al. (2020) show that, in order for a single YOTO model to match the performance of models trained separately for individual trade-off parameters, the network typically needs to be approximately twice as wide as those fixed-weight models. As a consequence, despite 1 The code repository is available at https://github.com/maayasakata/guidance-to-fairest-boundary.
3
avoiding repeated training, YOTO incurs higher inference-time computational cost compared to post-processing methods. Our approach combines the strengths of both in-processing and post-processing. It learns effective feature representations such that subsequent post-processing at any target fairness level yields high trade-off efficiency. This enables efficient and flexible adjustment of the fairness-accuracy trade-off without the need for model retraining.
3
Preliminaries
3.1
Fair Classification Problem
We consider a fair binary classification problem. Let X ∈ X , A ∈ {0, 1}, and Y ∈ {0, 1} be random variables representing a feature vector, binary sensitive attribute, and binary label, respectively. A probabilistic classifier f is a measurable function from X × {0, 1} to [0, 1], where the output represents the probability that the predicted label equals 1. We denote the prediction produced by f by Ŷf , i.e., P (Ŷf = 1|X, A) = f (X, A) almost surely. Let F denote the set of all measurable functions X × A → [0, 1]. Given a set of n i.i.d. observations S = {(xi , ai , yi )}ni=1 drawn from a distribution D, the learner’s goal is to construct a family of classifiers (fc )c∈C ⊆ F indexed by a set of trade-off parameters C ⊂ R that achieve the efficient fairness-accuracy trade-offs. Trade-off efficiency of a family of classifiers (fc ) is characterized by the induced set of fairness-accuracy metrics pairs, denoted by T ((fc )) = {(Acc(fc ), |DDP(fc )|}. Here, Acc denotes the accuracy metric, for which we adopt the standard classification accuracy; namely, Acc(fc ) = P (Ŷfc = Y ). DDP denotes the fairness metric based on demographic parity (DP) (Pedreshi et al. 2008), which deems a classifier f ∈ F fair if its predicted label is independent of the sensitive attribute. Formally, f satisfies DP if P (Ŷfc = 1 | A = 1) = P (Ŷfc = 1 | A = 0).
(1)
To quantify deviations from Eq. (1), we use the difference of demographic parity (DDP) (Cho et al. 2020; Zeng et al. 2024), defined as DDP(fc ) = P (Ŷfc = 1 | A = 1) − P (Ŷfc = 1 | A = 0). A larger value of Acc (closer to 1) indicates higher accuracy, a smaller value of |DDP(fc )| (closer to 0) corresponds to greater fairness. In this work, we aim to develop a fair learning algorithm whose resulting trade-off, T (fc ), approximates the optimal trade-off T ∗ (F) as closely as possible while providing post-hoc controllability. Here, post-hoc controllability refers to the ability to adapt to different trade-off parameters at inference time with a computational cost no greater than a single forward pass, without retraining the model. The optimal trade-off T ∗ (F) is characterized by the Pareto front. In our context, this Pareto front consists of all achievable pairs (Acc(f ), |DDP(f )|) that are not dominated by any other solution. We say that a solution f ′ is dominated by another solution f , denoted by f ′ ⪯ f , if Acc(f ) > Acc(f ′ ) and |DDP(f )| ≤ |DDP(f ′ )|
or
4
Acc(f ) ≥ Acc(f ′ ) and |DDP(f )| < |DDP(f ′ )|.
Following Xu et al. (2023), the Pareto front is defined as o n T ∗ (F) = Acc(f ), |DDP(f )| f ∈ F , ∄f ′ ∈ F such that f ⪯ f ′ , where F denotes the set of all measurable functions. For notational simplicity, we henceforth write pa := P (A = a) and ηa (x) := P (Y = 1 | X = x, A = a) and denote the logit of ηa (x) by za (x).
3.2
Fair Bayes-Optimal Classifier
A point on the Pareto front T ∗ (F) can be obtained as the solution to the following optimization problem: fδ∗ ∈ arg max Acc(f ) s.t. |DDP(f )| ≤ δ. (2) f ∈F
We refer to fδ∗ as the fair Bayes-optimal classifier. Under the assumption that ηa (X) has a density on [0, 1], this classifier is equivalent to ft∗ (x, a) = I
pa − (2a − 1)t za (x) > − log pa + (2a − 1)t
,
(3)
for an appropriately chosen t (Menon et al. 2018; Zeng et al. 2024), where I(·) denotes the indicator function. Eq. (3) employs the logit representation derived from the original formulation based on the conditional class probability ηa (x). The parameter t is selected as t∗δ = arg min{|t| : |DDP(ft∗ )| ≤ δ}.
(4)
t
When t = 0, the classifier corresponds to the unconstrained Bayes-optimal classifier. For notational convenience, we define the threshold in Eq. (3) as τa (t) = − log
3.3
pa − (2a − 1)t . pa + (2a − 1)t
(5)
FairBayes
FairBayes (Zeng et al. 2024) is a post-processing method building upon the theory of fair Bayesoptimal classifiers and uses the fairness tolerance δ described in Section 3.2 as its trade-off parameter. To realize the analytical solution ft∗∗ in practice, FairBayes empirically estimates the unknown δ distributional quantities appearing in Eq. (3) and substitutes them with empirical counterparts. Training phase: estimating the logit functions The training phase seeks to estimate the optimal logit functions za , which are approximated using a parametric model za (x; θza ), where θza denotes the model parameters. These parameters are estimated by solving the following empirical risk minimization problem: θzERM = arg min Lpred (θza ; a), a θza
where, for each group a ∈ {0, 1}, Lpred (θza ; a) =
1 X ℓ yi , za (xi ; θza ) . na i:a =a i
5
(6)
Algorithm 1: PostProcess(z0ERM , z1ERM , δ, S) Require: estimated logit functions z0ERM , z1ERM , trade-off parameter δ Ensure: estimated threshold parameter t̂δ 1: Estimate group priors by p̂a ← na /n. 2: Compute τ̂a (t) and fb0ERM using Eq. (7). ERM [ 3: Compute DDP(Z(θ ), 0) using Eq. (8). za ERM [ ), 0) ≤ δ then 4: if DDP(Z(θ z a
5: t̂δ (θzERM ) ← 0. a 6: else 7: Solve Eq. (9) via binary search. 8: end if ) 9: return t̂δ (θzERM a
Pn Here, na = i=1 I(ai = a) denotes the number of samples in group a, and ℓ(·, ·) is loss function, such as the cross-entropy loss and focal loss (Lin et al. 2020). For notational simplicity, we use zaERM (x) as shorthand for za (x; θzERM ). a Prediction phase: estimating the thresholds Given a trade-off parameter δ, the goal in the prediction phase is to estimate t∗δ , and consequently, the corresponding optimal classifier ft∗∗ . Alg. 1 δ summarizes the steps of the entire prediction-phase procedure, which we denote by PostProcess(·). Alg. 1 first constructs estimates of ft∗ . Since estimates of the logit functions za are already obtained in the training phase as zaERM , the remaining quantities to be estimated are the group-dependent thresholds τa . Using the approximation p̂a = na /n, these thresholds are estimated (Alg. 1, lines 1–2) as p̂0 + t p̂1 − t τ̂0 (t) = − log , τ̂1 (t) = − log . (7) p̂0 − t p̂1 + t Using these thresholds, the estimates of ft∗ are then given by ftERM (x, a) = I za (x; θzERM ) > τ̂a (t) . a Next, the parameter t∗δ is estimated through an empirical approximation of Eq. (4). Given a vector Z ∈ Rn containing the estimated logit values for all observations, DDP for classifiers induced by thresholding at τ̂a (t) is estimated as 1 X 1 X [ I Zi > τ̂1 (t) − I Zi > τ̂0 (t) , DDP(Z, t) = n1 i:a =1 n0 i:a =0 i
(8)
i
where Zi denotes the i-th component of Z. The estimate of t∗δ corresponding to a given logit vector Z is then obtained as n o [ t̂δ Z = arg min |t| : DDP(Z, t) ≤ δ . (9) t
[ is monotone non-increasing in t, this optimization can be efficiently solved via binary Since DDP [ each of search (Alg. 1, lines 3–9). This procedure requires at most O(log n) evaluations of DDP,
6
Figure 1: Comparison of algorithmic flows: (a) FairBayes and (b) the proposed method. which has cost O(n), resulting in an overall complexity of O(n log n). This is substantially more computationally efficient than retraining a model. Once the estimate of t∗δ via PostProcess(·) in Alg. 1, the resulting classifier is obtained by substituting ⊤ this estimate into ftERM . Let Z(θzERM ) = zaERM (x1 ), . . . , zaERM (xn ) ∈ Rn denote the logit vector a 1 n for the logit functions zaERM . The estimate of t∗δ is then given by t̂δ Z(θzERM ) , which we also denote a by the shorthand t̂δ θzERM . The final classifier is therefore fbt̂ERM . a (θ ERM ) δ
4
za
Proposed Method
In this section, we present our novel fair classification algorithm, Guidance to Fairest-Boundary (GFB). Our method builds upon a theoretical analysis of the relationship between the trade-off efficiency of the post-processed classifier and the data distribution (Section 4.1). While existing results characterize the trade-off efficiency of the optimal classifier under the underlying distribution, our analysis additionally captures the trade-off efficiency achieved when the optimal classifier is applied to a different distribution. Based on our theoretical analysis, GFB learns transformed feature representations to achieve high trade-off efficiency. Fig. 1 compares the procedures of FairBayes and our proposed method. Our method maintains post-hoc controllability by adopting the same post-process as FairBayes during inference (right in Fig. 1), while simultaneously improving the trade-off efficiency by learning appropriate latent representations during training (left bottom in Fig. 1). We also present a practical gradient-based optimization algorithm for our proposed method based on the Moving-Average SOBA (MA-SOBA) framework (Chen et al. 2024), described in Section 4.3. To adapt this framework to our objective, we address the challenges that arise in computing gradients for our learning objective.
7
(a) Distribution with poor trade-off efficiency
(b) Distribution with good trade-off efficiency
Figure 2: Effect of distributional structure on trade-off efficiency. The horizontal and vertical axes denote |2ηa − 1| and pa Fa (ηa ), respectively, where Fa (·) denotes the cumulative distribution function conditioned by A = a. Yellow regions indicate the values of the Accdep at tolerance δ. While the figure above depicts a specific scenario where |2κ0 (δ) − 1| = |2κ1 (δ) − 1|, the conclusion holds true even in general cases, despite the visualization becoming more complex.
4.1
Theoretical Analysis of Trade-off Efficiency and Data Distribution
This subsection presents a theoretical result characterizing the trade-off efficiency of a post-processed classifier under changes in the data distribution. Specifically, consider a random variable corresponding a transformed feature vector X ′ ∈ X ′ , and let κa (δ) : [0, 1] → R be a monotonic function of fairness tolerance δ such that the distance |κa (δ) − 0.5| increases as the tolerance δ becomes more stringent. We define a post-processed classifier fδη based on ηA (X ′ ) by employing κa (δ) as its decision threshold: fδη (x′ , a) = I ηa (x′ ) > κa (δ) . (10) The following theorem characterizes the trade-off efficiency of the generalized classifier fδη : Theorem 1 (Accuracy dependence on the fairness tolerance δ). For any classifier of the form in Eq. (10), its accuracy satisfies Acc(fδη ) = Acc(f0η ) + Accdep (fδη ), where
h i Accdep (fδη ) = EX ′ ,A I(ηA (X ′ ) ∈ IA (δ)) 2ηA (X ′ ) − 1 ,
and Ia (δ) :=
i min κa (δ), κa (0) , max κa (δ), κa (0) .
Thm. 1 shows that the accuracy of fδη decomposes into a δ-independent term and a δ-dependent term. Since the trade-off efficiency is affected solely by the δ-dependent term, Accdep characterizes the trade-off efficiency. Here, IA (δ) denotes the interval such that ηa (x′ ) ∈ Ia (δ) if and only if fδη (x′ , a) ̸= f0η (x′ , a). Importantly, this theorem applies to any classifier of the form in Eq. (10). In the DDP case, it coincides with Eq. (3) by setting κa (δ) = σ(τa (t∗δ )), up to the change of input domain from X to X ′ . Extensions to other fairness metrics are discussed in Appendix A.3.
8
Thm. 1 suggests that higher trade-off efficiency is achieved when the distributions of ηa (X ′ ) are concentrated near κa (0), the most fair threshold, thereby increasing Accdep . Fig. 2 illustrates the values of Accdep under two representative distributions, where the areas of the yellow regions correspond to Accdep (fδη ). The red and blue lines represent PX ′ |A=0 (η0 (X ′ ) ≤ κ0 (δ)) and PX ′ |A=1 (η1 (X ′ ) ≤ κ1 (δ)), respectively, as functions of δ along the horizontal axis. The two distributions of ηa (X ′ ) outside of Ia (1) are identical, whereas within Ia (1), the distribution in Fig. 2b is more concentrated near κa (0) than that in Fig. 2a. Accordingly, Fig. 2 shows that the yellow area associated with Fig. 2b is larger than that associated with Fig. 2a. These observations suggest a key design principle for achieving superior trade-off efficiency: reshaping the distribution so that ηa (X ′ ) concentrates near the most fair threshold κa (0) increases the value of Accdep .
4.2
Training Algorithm
In this subsection, we present the training algorithm for GFB. Motivated by the analyses in Section 4.1, we introduce a parametrized transformation ga (·; θga ) : X → X ′ from X to X ′ and optimize its parameters during training so that the resulting distribution of ηa (X ′ ) is concentrated near κa (0). By integrating representation learning during training with post-processing at inference, GFB achieves superior fairness-accuracy trade-offs while remaining post-hoc controllability. 4.2.1
Design of Distribution-Shaping Loss Lgen
We train the transformation such that the resulting logits 1) are concentrated near the most fair threshold and 2) achieve high predictive accuracy. To this end, we introduce parameters θza for za (·; θza ), which estimates the logits from transformed features. Our learning objective is defined over the logits induced from parameters θga and θza and consists of two terms corresponding to these goals, defined as Lgen (θga , θza ; a) = (1 − λ)Ldist θga , θza ; a + λLpred θga , θza ; a . Here, Ldist and Lpred corresponds to two objectives, weighted by λ. Distance loss Ldist The function Ldist encourages the logit distribution within the interval to concentrate near the most fair threshold. Let J(τ ) denote the interval in the logit space corresponding to IA (1) for a given threshold τ , defined as J(τ ) = min 0, τ , max 0, τ . We measure the proximity of a logit within J(τ ) to the threshold τ by ( |τ − z|, z ∈ J(τ ), D(z, τ ) = (11) 0, otherwise. Based on this function, Ldist is given by 1 X Ldist (θga , θza ; a) = D za ga (xi ; θga ); θza , τ̂a t̂0 (θga , θza ) , na i:a =a i
⊤ n where t̂0 (θga , θza ) is shorthand for t̂0 (Z(θga , θza )), and Z(θga , θza ) = (z̃1 , . . . , z̃n ) ∈ R is the induced logit vector with entries z̃i = zai gai (xi ; θgai ); θzai .
9
Prediction loss Lpred The function Lpred measures the prediction loss of the induced logits and is defined as i 1 X h Lpred (θga , θza ; a) = ℓ yi , za (ga (xi ; θga ); θza ) . na i:a =a i
This term promotes high predictive accuracy of the resulting prediction model. 4.2.2
Overall Formulation
We now present the overall learning objective of our training algorithm. To ensure that za (·; θza ) serves as an accurate logit predictor, we choose θza to minimize the predictive loss. Specifically, for given transformation parameters θga , the selected parameter is defined as θzGFB (θga ) = arg min Lpred θga , θza ; a . a θza
The transformation parameters θga are then learned by minimizing the function Lgen evaluated at θzGFB (θga ), yielding a min Φ(θga ) := Lgen θga , θzGFB (θga ); a . a θ ga
An equivalent bi-level optimization formulation is given by min Lgen θga , θza ; a , s.t. θza = arg min Lpred θga , θza ; a . θga ,θza
θ za
(12)
We cannot directly apply standard gradient-based optimization algorithm, such as gradient descent, to solve Eq. (12), as it is a constrained optimization problem. Nevertheless, in practice, one may wish to employ the gradient-based optimization techniques, particularly when ga and za are modeled using deep neural networks. Accordingly, in the subsequent subsection, we present a gradient-based optimization algorithm for solving Eq. (12).
4.3
Optimization Procedure
In this subsection, we present a gradient-based optimization algorithm for solving Eq. (12), highlighting its practical applicability. We adopt MA-SOBA (Chen et al. 2024), a gradient-based bi-level optimization algorithm, to address Eq. (12). However, computing the gradient of the the outer objective Ldist poses two key challenges: (i) the distance metric D(z, τ ) in Eq. (11) is discontinuous, and (ii) the threshold parameter t̂0 (·) is defined as the minimizer under a discontinuous constraint [ = 0. To address these challenges, we introduce smooth proxy functions to approximate of DDP discontinuous components and derive the analytical gradient of t̂0 . MA-SOBA MA-SOBA is an optimization algorithm for bi-level optimization problems that relies solely on gradients of the inner and outer objective functions, avoiding explicit Hessian inversion (Chen et al. 2024). Specifically, MA-SOBA maintains auxiliary variables that approximate the product of the inverse Hessian and the gradient. It then iteratively performs simultaneous updates of the inner, outer, and auxiliary variables using a moving-average scheme. Details, including convergence, are provided in Appendix B.
10
Once the proposed method is formulated as a bi-level optimization problem, we leverage the MASOBA framework to iteratively update the inner variable θza , the outer variable θga , and the auxiliary variable wa . At each iteration k, the update directions for these variables are computed as inner: Dza (θgka , θzka , wak ) = ∇2 Lpred (θgka , θzka )
(13)
aux: Dwa (θgka , θzka , wak ) = ∇222 Lpred (θgka , θzka )wak − ∇2 Lgen (θgka , θzka )
(14)
Dga (θgka , θzka , wak ) = ∇1 Lgen (θgka , θzka ) − ∇212 Lpred (θgka , θzka )wak .
(15)
outer:
Here, ∇1 and ∇2 denote the gradient operators with respect to the first and second arguments, respectively. The operators ∇212 and ∇222 correspond to differentiating with respect to the first and then second arguments, and the second and then second arguments, respectively, yielding Jacobian matrices. Computing ∇1 Lgen and ∇2 Lgen via the chain rule requires evaluating gradients of a non-differentiable component and a component defined by the minimizer of a non-differentiable function, as discussed above. To enable gradient-based optimization, we address these gradient computation challenges. Smoothing the distance metric The distance metric D(z, τ ) is non-differentiable due to the discontinuity at z = 0. To resolve this, we approximate the indicator function I(z ∈ J(τ )) by replacing it with a smooth function w(z) : R → [0, 1], such as a sigmoid function. We then define the smooth surrogate as D̂(z, τ ) = w(z) · |z − τ |. Analytical derivation of the threshold gradient To compute the gradient of t̂0 , we need to [ and the gradient computation of a function defined as a address both the non-continuity of DDP [ we replace the indicator functions with a minimizer. To handle the non-differentiability of DDP, smooth, monotonically increasing function ψ : R → R. While our focus in this work is DDP, the following derivation applies to a broad class of disparity measures. To maintain this generality, we introduce a generalized formulation that encompasses DDP. Let Sa ⊆ {1, . . . , n} be an arbitrary subset of sample with sensitive attribute A = a. Further, let γa (t) be a continuous and monotonic threshold function satisfying the additional technical assumptions detailed in Appendix C.2. We define the general surrogate disparity function as: 1 X 1 X ϕ(Z; t) = ψ Zi − γ1 (t) − ψ Zi − γ0 (t) . (16) |S | |S | 1
0
i∈S1
i∈S0
[ by setting Sa = {i : ai = a} and γa (t) = τ̂a (t). This formulation reduces to the smooth DDP Extensions to other fairness metrics are discussed in Appendix A.3. Under this surrogate, t̂0 is replaced by a mapping Z → arg mint {|t| : ϕ(Z; t) = 0}. The following theorem characterizes the gradient of such a function. Theorem 2 (Implicit Gradient of t). Let ϕ(Z, t) be the surrogate disparity function defined in Eq. (16). Assume that a function ψ is continuously differentiable satisfying ψ ′ (u) > 0 for all u ∈ R. Then, for every Z ∈ Rn , there exists a unique parameter t(Z) satisfying ϕ(Z, t(Z)) = 0. Moreover, t(Z) is differentiable with respect to Z, and its gradient is given by ∇1 t(Z) = −
∇1 ϕ(Z, t(Z)) . ∇2 ϕ(Z, t(Z))
11
Algorithm 2: Overall Procedure of GFB Require: Dataset S, number of step K, stepsizes {αak , βak , γak }, moving-average parameter ρka ∈ (0, 1), trade-off parameter δ. Ensure: Fair classifier fδGFB (x, a). 0 1: Initialize θg0a , θz0a / wa ← 0, h0a ← 0 for a ∈ {0, 1}. 2: Training Phase: Learning ga and za 3: for k = 0, . . . , K − 1 do 4: Sample a minibatch Bak ∼ S. 5: vak ← za ga (x; θgka ); θzka for (x, y) ∈ Bak . 6: Compute tk from v0k , v1k 7: Outer: θgk+1 ← θgka − αak hka . (Eq. (15)) a 8: Inner: θzk+1 ← θzka − βak Dza (θgka , θzka , wak ). (Eq. (13)) a k+1 9: Aux: wa ← wak − γak Dwa (θgka , θzka , wak ). (Eq. (14)) 10: Moving avg: hk+1 ← (1 − ρka ) hka + ρka Dθga (θgka , θzka , wak ). (Eq. (25)) a 11: end for 12: Prediction Phase: Threshold search 13: zaGFB ← za (ga (·; θgKa ); θzKa ) 14: t̂δ ← PostProcess(z0GFB , z1GFB , δ, S) 15: Compute τ̂a (t̂δ ). 16: return fδGFB (x, a) = I zaGFB (xa ) > τ̂a (t̂δ ) .
By replacing non-smooth components with smooth surrogates and leveraging gradient computation in Thm. 2, we can solve Eq. (12) using MA-SOBA. Algorithm 2 summarizes the complete pipeline of the proposed approach, spanning both the training and inference phases.
5
Experiments
To demonstrate the effectiveness of our method, we conduct experiments on several real-world datasets and compare it with existing in-processing and post-processing methods.
5.1
Experimental Setup
Comparison methods In our experiments, we compare the proposed method with several competitive baselines: EPO (Mahapatra et al. 2020) (multi-objective optimization), FairBiNN (YazdaniJahromi et al. 2024) (bi-level optimization), YOTO (Taufiq et al. 2024) (in-processing), and FairBayes (Zeng et al. 2024) (post-processing). EPO and FairBiNN lacks the post-hoc controllability, whereas both YOTO and FairBayes provide the post-hoc controllability. Datasets Experiments were conducted on four datasets: two image datasets, CelebA (Liu et al. 2015) and UTKFace (Zhang et al. 2017), and two tabular datasets, Adult (Kohavi 1996) and COMPAS (Angwin et al. 2016). The target labels and sensitive attributes for each dataset are summarized in Table 3 of Appendix D.2. Evaluation metrics We evaluate classification accuracy (Acc) and the absolute demographic parity difference (|DDP|) as the accuracy and fairness metrics, respectively. The reported values are 12
Figure 3: Illustration of the standard HV and inverted HV. The yellow region represents the standard HV, which evaluates favorable trade-off coverage, where larger values are better. The green region represents the inverted HV, which evaluates the extent of poorly performing trade-off solutions, where smaller values are better. averages over 5 runs. To quantify the fairness-accuracy trade-off, we use two hypervolume-based metrics: standard HV and inverted HV, as illustrated in Fig. 3. Both metrics measure an area relative to a reference point, but place the reference point in opposite directions. The standard HV uses a reference point at the worst corner, corresponding to low Acc and high |DDP|. The inverted HV uses a reference point at the best corner, corresponding to high Acc and low |DDP|. Details of the computation are provided in Appendix D.3. Larger standard HV indicates better coverage of favorable trade-off solutions, while smaller inverted HV indicates fewer poorly performing solutions. A method with high standard HV but also high inverted HV cannot be considered efficient over the entire trade-off curve, since it produces poor solutions for some trade-off parameters despite obtaining favorable ones for others. Together, larger standard HV and smaller inverted HV indicate more efficient and stable trade-off behavior. Although both metrics are sensitive to the choice of reference point, the ranking of methods remains largely unchanged under different settings; see Appendix D.5.3 for details.
5.2
Results
Figures 4a–4d show the fairness-accuracy trade-off of each method. The horizontal axis represents Acc, with higher values toward the right, while the vertical axis represents DDP, with greater fairness toward the bottom. Thus, a trade-off curve closer to the bottom-right region indicates a more efficient fairness-accuracy trade-off. Each point corresponds to a specific trade-off parameter. For YOTO, FairBayes, and GFB, a single model is trained once on the training dataset and then evaluated on the testing dataset under 10 different trade-off parameters in a post-hoc manner. Since EPO and FairBiNN do not provide post-hoc controllability, each reported point for these methods corresponds to a separately trained model. Table 1 and Table 2 summarize the mean HV values and inverted HV values computed from these trade-offs, respectively. Additional statistics are provided
13
(a) CelebA
(b) UTKFace
(c) Adult
(d) COMPAS
Figure 4: Fairness-accuracy trade-off curves for each dataset. The horizontal and vertical axes represent accuracy and DDP. in Appendix D.5.2. First, we compare our method with post-hoc controllable methods, FairBayes and YOTO. As shown in Fig. 4, except for the comparison with FairBayes on Adult, GFB is located below or to the right of those of FairBayes and YOTO across all datasets. This indicates that GFB generally achieves lower DDP at comparable accuracy, or higher accuracy at comparable DDP, resulting in a more efficient fairness-accuracy trade-off. Consistent with this observation, our method attains higher HV and lower inverted HV than both methods across all datasets, indicating that GFB achieves more efficient trade-offs while also avoiding poorly performing trade-off points. To achieve this improvement, GFB employs a bi-level training procedure, which slightly increases the training cost compared with FairBayes and YOTO. We report the wall-clock training time and the cost of post-hoc trade-off adjustment in Appendix D.5.1. Next, we compare our method with the in-processing method EPO. As shown in Table 1, GFB achieves higher HV than EPO on CelebA, UTKFace, and Adult, whereas EPO obtains higher HV on COMPAS. This shows that GFB outperforms EPO in terms of HV on most datasets, while EPO has an advantage on COMPAS. However, as shown in Fig. 4, the trade-off curve of GFB lies to the right of, or close to, that of EPO across all datasets including COMPAS, indicating that GFB achieves comparable or higher accuracy at similar DDP levels. Furthermore, GFB achieves lower inverted HV than EPO across all datasets, suggesting that GFB produces fewer poorly performing trade-off points. Overall, GFB is competitive with EPO in trade-off performance while additionally providing post-hoc controllability that EPO does not offer. Next, we compare our method with another in-processing method, FairBiNN. On CelebA and Adult, the trade-off curves of GFB are located to the right of, or close to, those of FairBiNN, and GFB achieves higher HV on both datasets. These results suggest that GFB attains a more efficient fairness-accuracy trade-off than FairBiNN on CelebA and Adult. On UTKFace and COMPAS, FairBiNN achieves higher HV than GFB, indicating its advantage under the HV metric. However, the curve-level comparison shows a more nuanced picture. Although the trade-off curves of FairBiNN extends further downward, GFB is often located to the right of, or close to, FairBiNN within the vertical range where both methods have solutions; this tendency is particularly visible on UTKFace. Moreover, GFB achieves lower inverted HV than FairBiNN across all datasets, indicating that FairBiNN can obtain highly favorable trade-off points that increase HV while producing poorly performing points for some trade-off parameters. In contrast, GFB avoids such poor points and maintains a more stable trade-off curve overall.
14
Table 1: Comparison of Hypervolume. Values are reported as mean ± standard deviation. EPO
FairBiNN
YOTO
FairBayes
GFB (Ours)
CelebA 0.7733 ± 0.060 0.6919 ± 0.045 0.6068 ± 0.146 0.7257 ± 0.026 0.8198 ± 0.005 UTKFace 0.8455 ± 0.024 0.8876 ± 0.024 0.7481 ± 0.078 0.8202 ± 0.020 0.8581 ± 0.025 Adult 0.7237 ± 0.072 0.7553 ± 0.055 0.6492 ± 0.047 0.7850 ± 0.041 0.8007 ± 0.038 COMPAS 0.8191 ± 0.060 0.8409 ± 0.074 0.6442 ± 0.133 0.7598 ± 0.084 0.8164 ± 0.038 Table 2: Comparison of inverted Hypervolume. Values are reported as mean ± standard deviation. Lower values are better. EPO
FairBiNN
YOTO
FairBayes
GFB (Ours)
CelebA 0.4563 ± 0.180 0.3829 ± 0.057 0.3223 ± 0.228 0.2622 ± 0.017 0.2268 ± 0.003 UTKFace 0.4443 ± 0.383 0.2579 ± 0.060 0.1558 ± 0.058 0.1556 ± 0.016 0.1010 ± 0.019 Adult 0.4801 ± 0.054 0.3507 ± 0.035 0.4314 ± 0.076 0.2529 ± 0.027 0.2514 ± 0.028 COMPAS 0.2207 ± 0.036 0.2155 ± 0.048 0.3661 ± 0.109 0.1724 ± 0.032 0.1398 ± 0.030
6
Conclusion
In this paper, we propose a novel fair classification method that provides the post-hoc controllability while achieving high trade-off efficiency. Our algorithm combines representation learning during training with post-processing at inference. Experiments on real-world datasets demonstrated the effectiveness of our approach. We also note several limitations and future directions. First, although the framework supports several fairness metrics, it does not cover all notions; extending it to equalized odds remains an important direction. Second, our current framework is restricted to binary sensitive attributes and binary labels. Extending it to multiclass classification and intersectional groups defined by multiple sensitive attributes is an important future direction. However, such extensions require substantial technical development, as fair Bayes-optimal classifiers in these settings no longer admit simple thresholding structures (Xian et al. 2023). Addressing these extensions would further broaden the applicability of our framework.
Acknowledgements This work was partly supported by JSPS KAKENHI Grant Numbers JP26K02874 and JP23H00483.
Impact Statement This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
15
References Kohavi, Ron (1996). Scaling up the accuracy of Naive-Bayes classifiers: a decision-tree hybrid. In: Proceedings of the Second International Conference on Knowledge Discovery and Data Mining. KDD’96. Portland, Oregon: AAAI Press, pp. 202–207. Zitzler, Eckart and Lothar Thiele (1998). Multiobjective optimization using evolutionary algorithms — A comparative case study. In: Parallel Problem Solving from Nature — PPSN V. Ed. by Agoston E. Eiben, Thomas Bäck, Marc Schoenauer, and Hans-Paul Schwefel. Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 292–301. isbn: 978-3-540-49672-4. doi: 10.1007/BFb0056872. Pedreshi, Dino, Salvatore Ruggieri, and Franco Turini (2008). Discrimination-aware data mining. In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’08. Las Vegas, Nevada, USA: Association for Computing Machinery, pp. 560–568. isbn: 9781605581934. doi: 10.1145/1401890.1401959. Kamishima, Toshihiro, Shotaro Akaho, Hideki Asoh, and Jun Sakuma (2012). Fairness-Aware Classifier with Prejudice Remover Regularizer. In: Machine Learning and Knowledge Discovery in Databases. Ed. by Peter A. Flach, Tijl De Bie, and Nello Cristianini. Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 35–50. isbn: 978-3-642-33486-3. doi: 10.1007/978-3-642-33486-3_3. Fukuchi, Kazuto, Jun Sakuma, and Toshihiro Kamishima (2013). Prediction with Model-Based Neutrality. In: Machine Learning and Knowledge Discovery in Databases. Ed. by Hendrik Blockeel, Kristian Kersting, Siegfried Nijssen, and Filip Železný. Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 499–514. isbn: 978-3-642-40991-2. doi: 10.1007/978-3-642-40991-2_32. Liu, Ziwei, Ping Luo, Xiaogang Wang, and Xiaoou Tang (2015). Deep Learning Face Attributes in the Wild. In: 2015 IEEE International Conference on Computer Vision (ICCV), pp. 3730–3738. doi: 10.1109/ICCV.2015.425. Angwin, Julia, Jeff Larson, Surya Mattu, and Lauren Kirchner (2016). Machine Bias: There’s Software Used across the Country to Predict Future Criminals. And It’s Biased against Blacks. url: https://www.propublica.org/article/machine- bias- risk- assessments- in- criminalsentencing. Hardt, Moritz, Eric Price, and Nati Srebro (2016). Equality of Opportunity in Supervised Learning. In: Advances in Neural Information Processing Systems. Ed. by D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett. Vol. 29. Curran Associates, Inc. Corbett-Davies, Sam, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq (2017). Algorithmic Decision Making and the Cost of Fairness. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’17. Halifax, NS, Canada: Association for Computing Machinery, pp. 797–806. isbn: 9781450348874. doi: 10.1145/3097983.3098095. Woodworth, Blake, Suriya Gunasekar, Mesrob I. Ohannessian, and Nathan Srebro (2017). Learning Non-Discriminatory Predictors. In: Proceedings of the 2017 Conference on Learning Theory. Ed. by Satyen Kale and Ohad Shamir. Vol. 65. Proceedings of Machine Learning Research. PMLR, pp. 1920–1953. Zafar, Muhammad Bilal, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P. Gummadi (2017). Fairness Constraints: Mechanisms for Fair Classification. In: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. Ed. by Aarti Singh and Jerry Zhu. Vol. 54. Proceedings of Machine Learning Research. PMLR, pp. 962–970. Zhang, Zhifei, Yang Song, and Hairong Qi (2017). Age Progression/Regression by Conditional Adversarial Autoencoder. In: 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4352–4360. doi: 10.1109/CVPR.2017.463. Dastin, Jeffrey (2018). Insight – Amazon scraps secret AI recruiting tool that showed bias against women. url: https : / / www . reuters . com / article / us - amazon - com - jobs - automation -
16
insight/amazon-scraps-secret-ai-recruiting-tool-that-showed-bias-against-womenidUSKCN1MK08G. Donini, Michele, Luca Oneto, Shai Ben-David, John S Shawe-Taylor, and Massimiliano Pontil (2018). Empirical Risk Minimization Under Fairness Constraints. In: Advances in Neural Information Processing Systems. Ed. by S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett. Vol. 31. Curran Associates, Inc. Ishibuchi, Hisao, Ryo Imada, Yu Setoguchi, and Yusuke Nojima (2018). How to Specify a Reference Point in Hypervolume Calculation for Fair Performance Comparison. In: Evolutionary Computation 26.3, pp. 411–440. issn: 1063-6560. doi: 10.1162/evco_a_00226. eprint: https://direct.mit. edu/evco/article-pdf/26/3/411/1552321/evco_a_00226.pdf. Menon, Aditya Krishna and Robert C. Williamson (2018). The cost of fairness in binary classification. In: Proceedings of the 1st Conference on Fairness, Accountability and Transparency. Ed. by Sorelle A. Friedler and Christo Wilson. Vol. 81. Proceedings of Machine Learning Research. PMLR, pp. 107–118. Perez, Ethan, Florian Strub, Harm de Vries, Vincent Dumoulin, and Aaron Courville (2018). FiLM: Visual Reasoning with a General Conditioning Layer. In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 32. 1, pp. 3942–3951. doi: 10.1609/aaai.v32i1.11671. Cotter, Andrew, Heinrich Jiang, Maya Gupta, Serena Wang, Taman Narayan, Seungil You, and Karthik Sridharan (2019). Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals. In: Journal of Machine Learning Research 20.172, pp. 1–59. Cho, Jaewoong, Gyeongjo Hwang, and Changho Suh (2020). A Fair Classifier Using Kernel Density Estimation. In: Advances in Neural Information Processing Systems. Ed. by H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin. Vol. 33. Curran Associates, Inc., pp. 15088–15099. Dosovitskiy, Alexey and Josip Djolonga (2020). You Only Train Once: Loss-Conditional Training of Deep Networks. In: International Conference on Learning Representations. Lin, Tsung-Yi, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár (2020). Focal Loss for Dense Object Detection. In: IEEE Transactions on Pattern Analysis and Machine Intelligence 42.2, pp. 318–327. doi: 10.1109/TPAMI.2018.2858826. Mahapatra, Debabrata and Vaibhav Rajan (2020). Multi-Task Learning with User Preferences: Gradient Descent with Controlled Ascent in Pareto Optimization. In: Proceedings of the 37th International Conference on Machine Learning. Ed. by Hal Daumé III and Aarti Singh. Vol. 119. Proceedings of Machine Learning Research. PMLR, pp. 6597–6607. Olfat, Matt and Yonatan Mintz (2020). Flexible Regularization Approaches for Fairness in Deep Learning. In: 2020 59th IEEE Conference on Decision and Control (CDC), pp. 3389–3394. doi: 10.1109/CDC42340.2020.9303736. Bendekgey, Henry C and Erik Sudderth (2021). Scalable and Stable Surrogates for Flexible Classifiers with Fairness Constraints. In: Advances in Neural Information Processing Systems. Ed. by M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan. Vol. 34. Curran Associates, Inc., pp. 30023–30036. Celis, L. Elisa, Lingxiao Huang, Vijay Keswani, and Nisheeth K. Vishnoi (2021). Fair Classification with Noisy Protected Attributes: A Framework with Provable Guarantees. In: Proceedings of the 38th International Conference on Machine Learning. Ed. by Marina Meila and Tong Zhang. Vol. 139. Proceedings of Machine Learning Research. PMLR, pp. 1349–1361. Chzhen, Evgenii and Nicolas Schreuder (2022). A Minimax Framework for Quantifying Risk-Fairness Trade-off in Regression. In: The Annals of Statistics 50.4, pp. 2416–2442. doi: 10 . 1214 / 22 AOS2198.
17
Dagréou, Mathieu, Pierre Ablin, Samuel Vaiter, and Thomas Moreau (2022). A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. In: Advances in Neural Information Processing Systems. Ed. by S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh. Vol. 35. Curran Associates, Inc., pp. 26698–26710. Jovanovic, Raka, Antonio P. Sanfilippo, and Stefan Voß (2022). Fixed Set Search Applied to the Multi-Objective Minimum Weighted Vertex Cover Problem. In: Journal of Heuristics 28.4, pp. 481– 508. issn: 1572-9397. doi: 10.1007/s10732-022-09499-z. Liu, Suyun and Luis Nunes Vicente (2022). Accuracy and fairness trade-offs in machine learning: a stochastic multi-objective approach. In: Computational Management Science 19.3, pp. 513–537. doi: 10.1007/s10287-022-00425-z. Zhao, Han and Geoffrey J. Gordon (2022). Inherent Tradeoffs in Learning Fair Representations. In: Journal of Machine Learning Research 23.57, pp. 1–26. Pathiraja, Bimsara, Malitha Gunawardhana, and Muhammad Haris Khan (2023). Multiclass Confidence and Localization Calibration for Object Detection. In: 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 19734–19743. doi: 10.1109/CVPR52729. 2023.01890. Xian, Ruicheng, Lang Yin, and Han Zhao (2023). Fair and Optimal Classification via Post-Processing. In: Proceedings of the 40th International Conference on Machine Learning. Ed. by Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett. Vol. 202. Proceedings of Machine Learning Research. PMLR, pp. 37977–38012. Xu, Shizhou and Thomas Strohmer (2023). Fair Data Representation for Machine Learning at the Pareto Frontier. In: Journal of Machine Learning Research 24.331, pp. 1–63. Yang, Jenny, Andrew A. S. Soltan, David W. Eyre, Yang Yang, and David A. Clifton (2023). An adversarial training framework for mitigating algorithmic biases in clinical machine learning. In: npj Digital Medicine 6.1, p. 55. doi: 10.1038/s41746-023-00805-y. Badar, Maryam, Sandipan Sikdar, Wolfgang Nejdl, and Marco Fisichella (2024). FairTrade: Achieving Pareto-Optimal Trade-Offs between Balanced Accuracy and Fairness in Federated Learning. In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. 10, pp. 10962–10970. doi: 10.1609/aaai.v38i10.28971. Baharlouei, Sina, Shivam Patel, and Meisam Razaviyayn (2024). f-FERM: A Scalable Framework for Robust Fair Empirical Risk Minimization. In: International Conference on Learning Representations. Ed. by B. Kim, Y. Yue, S. Chaudhuri, K. Fragkiadaki, M. Khan, and Y. Sun. Vol. 2024, pp. 36594– 36607. Chen, Xuxing, Tesi Xiao, and Krishnakumar Balasubramanian (2024). Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions. In: Journal of Machine Learning Research 25.151, pp. 1–51. Taufiq, Muhammad Faaiz, Jean-François Ton, and Yang Liu (2024). Achievable Fairness on Your Data With Utility Guarantees. In: Advances in Neural Information Processing Systems. Ed. by A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang. Vol. 37. Curran Associates, Inc., pp. 140405–140450. doi: 10.52202/079017-4457. Yazdani-Jahromi, Mehdi, Ali Khodabandeh Yalabadi, AmirArsalan Rajabi, Aida Tayebi, Ivan Garibay, and Ozlem Garibay (2024). Fair Bilevel Neural Network (FairBiNN): On Balancing fairness and accuracy via Stackelberg Equilibrium. In: Advances in Neural Information Processing Systems. Ed. by A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang. Vol. 37. Curran Associates, Inc., pp. 105780–105818. doi: 10.52202/079017-3355. Zeng, Xianli, Edgar Dobriban, and Guang Cheng (2024). Bayes-Optimal Classifiers under Group Fairness. arXiv: 2202.09724 [stat.ML].
18
Fabris, Alessandro, Nina Baranowska, Matthew J. Dennis, David Graus, Philipp Hacker, Jorge Saldivar, Frederik Zuiderveen Borgesius, and Asia J. Biega (2025). Fairness and Bias in Algorithmic Hiring: A Multidisciplinary Survey. In: ACM Trans. Intell. Syst. Technol. 16.1. issn: 2157-6904. doi: 10.1145/3696457. Fukuchi, Kazuto (2025). Meta Optimality for Demographic Parity Constrained Regression via PostProcessing. In: Proceedings of the 42nd International Conference on Machine Learning. Ed. by Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu. Vol. 267. Proceedings of Machine Learning Research. PMLR, pp. 18024–18046. Kim, Myung Jun, Félix Lefebvre, Gaëtan Brison, Alexandre Perez-Lebel, and Gaël Varoquaux (2025). Table Foundation Models: on knowledge pre-training for tabular learning. In: Transactions on Machine Learning Research. issn: 2835-8856.
19
A
Extended Details for Section 3
A.1
Pareto Front
The set T ∗ is characterized by the concept of the Pareto front. In our context, the Pareto front consists of all achievable pairs (Acc(f ), |Dis(f )|) that are not dominated by any other solution. Here, Dis(f ) denotes a disparity measure associated with the corresponding fairness metric, where values closer to zero indicate higher fairness. The Pareto front is defined as n o T ∗ (F) = Acc(f ), |Dis(f )| f ∈ F, ∄f ′ ∈ F such that f ⪯ f ′ , where F denotes the set of all measurable functions.
A.2
Fairness Metrics
In the main body, we mainly focus on Demographic Parity (DP). However, several other fairness metrics are also commonly used. In this subsection, we introduce the fairness metrics, in addition to DP, that are covered by our theoretical analysis. Equal Opportunity (EOp) (Hardt et al. 2016) EOp requires a classifier fc to achieve the same true positive rate across sensitive groups: P (Ŷfc = 1|Y = 1, A = 1) = P (Ŷfc = 1|Y = 1, A = 0).
(17)
To quantify deviation from Eq. (17), the difference of equal opportunity (DEOp) is commonly used and is defined as DEOp(fc ) = P (Ŷfc = 1|Y = 1, A = 1) − P (Ŷfc = 1|Y = 1, A = 0). A smaller value of |DEOp(fc )|, closer to 0, indicates greater fairness. Predictive Equality (PE) (Corbett-Davies et al. 2017) PE requires a classifier fc to achieve the same false positive rate across sensitive groups: P (Ŷfc = 1|Y = 0, A = 1) = P (Ŷfc = 1|Y = 0, A = 0).
(18)
To quantify deviation from Eq. (18), the difference of predictive equality (DPE) is commonly used and is defined as DPE(fc ) = P (Ŷfc = 1|Y = 0, A = 1) − P (Ŷfc = 1|Y = 0, A = 0). A smaller value of |DPE(fc )|, closer to 0, indicates greater fairness.
A.3
Fair Bayes-Optimal Classifier
As discussed in Section 3.2, the classifier in Eq. (2) is originally defined using the conditional class probability ηa (x) = P (Y = 1 | X = x, A = a). Under the assumption that ηa (X) has a density on [0, 1], fair Bayes-optimal classifiers for the fairness metrics considered in this work can be written as group-dependent threshold rules (Menon et al. 2018; Zeng et al. 2024): ftDis (x, a) = I ηa (x) > κDis (19) a (t) , 20
where Dis ∈ {DP, EOp, PE} denotes the fairness metric, and κDis a (t) is a group-dependent threshold controlled by the scalar parameter t. When t = 0, the DP classifier reduces to the unconstrained Bayes-optimal rule with decision threshold 1/2, which achieves the highest possible accuracy. In our framework, we reformulate this classifier in terms of logits za (x) = log(ηa (x)/(1 − ηa (x))). Equivalently, Eq. (19) can be written as ftDis (x, a) = I za (x) > γaDis (t) ,
γaDis (t) := log
κDis a (t) . 1 − κDis a (t)
Zeng et al. (2024) show that fair Bayes-optimal classifiers for other fairness metrics, such as EOp and PE, also admit analogous threshold-based forms. The corresponding thresholds are summarized below. For DP, the threshold is κDP a (t) =
1 (2a − 1)t + , 2 2pa
pa = P (A = a).
(20)
For Equal Opportunity (EOp), the threshold is κEOp (t) = a
pa,1 , 2pa,1 − (2a − 1)t
pa,1 = P (A = a, Y = 1).
(21)
Therefore, the corresponding logit threshold is (2a − 1)t . 1− pa,1
γaEOp (t) = − log
(22)
For Predictive Equality (PE), the threshold is κPE a (t) =
pa,0 + (2a − 1)t , 2pa,0 + (2a − 1)t
pa,0 = P (A = a, Y = 0).
(23)
Therefore, the corresponding logit threshold is γaPE (t) = − log
pa,0 pa,0 + (2a − 1)t
.
(24)
For each fairness metric, the parameter t is chosen so that the corresponding disparity constraint is satisfied. Specifically, for a given tolerance δ, t is selected to achieve arg min{|t| : |Dis(ftDis )| ≤ δ}. t
B
Moving-Average SOBA (MA-SOBA)
B.1
Comprehensive Framework
MA-SOBA (Chen et al. 2024) is a fully single-loop algorithm for solving stochastic bilevel optimization problems that builds on the Stochastic Bilevel Algorithm (SOBA) (Dagréou et al. 2022). Their
21
goal is to solve the following optimization problem, such that g and f represent the lower-level and upper-level functions, respectively min Φ(x) := f (x, y ∗ (x)) x∈X
s.t. y ∗ (x) = arg ming(x, y). y
We first review the SOBA algorithm and its limitations, and then describe how MA-SOBA addresses these challenges. SOBA introduce an auxiliary variable to approximate the product of the Hessian and a gradient, and simultaneously update the inner y, outer x, and auxiliary variables z using SGD steps. Let xk , y k , and z k denote the values of the respective variables at iteration k. Their update rules are given as follows: y k+1 = y k − βk ∇2 g(xk , y k ) n o z k+1 = z k − γk ∇222 g(xk , y ∗ (xk ))z k − ∇2 f (xk , y ∗ (xk ) n o ≈ z k − γk ∇222 g(xk , y k )z k − ∇2 f (xk , y k ) n o xk+1 = xk − αk ∇1 f (xk , y ∗ (xk )) − ∇212 g(xk , y ∗ (xk ))z ∗ (xk ) = xk − αk ∇Φ(xk ) n o ≈ xk − αk ∇1 f (xk , y k ) − ∇212 g(xk , y k )z k Here, αk , βk , and γk denote the step sizes. Since the inner variable y k is updated using only a single SGD step at each iteration, it generally does not coincide with the exact solution y ∗ (xk ). As a consequence, the stochastic gradient used in the update of the auxiliary variable z is biased. Similarly, the hypergradient ∇Φ(xk ) is also subject to bias. To mitigate the bias in hypergradient estimation, MA-SOBA incorporates a moving-average mechanism into the update rules. Specifically, MA-SOBA introduces a sequence of variables {hk } that aggregates past biased stochastic hypergradients. The update is given by n o hk+1 = (1 − θk )hk + θk ∇1 f (xk , y k ) − ∇212 g(xk , y k )z k . (25) Here, θk denotes the weight parameter of the moving average. MA-SOBA then replaces the update rule for x with one that uses the averaged hypergradient: xk+1 = xk − αk hk , thereby mitigating the bias induced by inexact inner updates.
B.2
Convergence Analysis
We provide a brief discussion on the convergence of the MA-SOBA optimizer used in our framework. Following the theoretical analysis by Chen et al. (2024), MA-SOBA is guaranteed to converge under the following standard assumptions: 1. First-order Lipschitz continuity of the outer objective and second-order Lipschitz continuity of the inner objective. 2. Strong convexity of the inner objective. 3. Boundedness of the gradient at the optimal solution of the inner problem. Assumptions 1 and 3 can be satisfied by choosing a doubly differentiable ψ with bounded first and second derivatives. In our experiments, we use the sigmoid function as ψ, which satisfies these 22
conditions. Assumption 2 requires the ERM objective to be strongly convex with respect to the model parameters, which is generally not satisfied in practice. However, we note that local strong convexity around local minima may suffice for convergence, as gradient-based optimization typically remains within such local region. The local strong convexity can be further encouraged in practice, e.g., by incorporating weight decay.
C
Proofs
C.1
Proof of Thm. 1
Theorem C.1 (Accuracy dependence on the fairness tolerance δ). The accuracy of classifiers of the form in Eq. (10) satisfies Acc(fδη ) = Acc(f0η ) + Accdep (fδη ), where
h i Accdep (fδη ) = EX ′ ,A I(ηA (X ′ ) ∈ IA (δ)) 2ηA (X ′ ) − 1 ,
and Ia (δ) :=
i min κa (δ), κa (0) , max κa (δ), κa (0) .
Proof. IA (δ) denotes the interval such that ηa (x′ ) ∈ Ia (δ) if and only if fδη (x′ , a) ̸= f0η (x′ , a). Specifi cally, When δ is sufficiently large, κa = 0.5 holds, and thus IA (1) = min(0.5, κa (0)), max(0.5, κa (0)) . For a fixed (X ′ , A), we consider the probability that the prediction of the Bayes-optimal classifier, Ŷf1η , coincides with the true label Y : P Ŷf1η = Y | X ′ , A . If ηA (X ′ ) > 0.5, the classifier predicts
Ŷf1η = 1, and this probability equals P (Y = 1 | X ′ , A) = ηA (X ′ ). If ηA (X ′ ) ≤ 0.5, the classifier predicts Ŷf1η = 0, and the probability equals P(Y = 0 | X ′ , A) = 1 − ηA (X ′ ). Hence, the probability that the prediction matches the true label is given by 1 + |2ηA (X ′ ) − 1| P Ŷf1η = Y | X ′ , A = max(ηA (X ′ ), 1 − ηA (X ′ )) = . 2 Now, fδη with a shifted threshold ηA (X ′ ) > κa (δ). The conditional probability consider the classifier P Ŷfδη = Y | X ′ , A depends on whether the prediction of fδη coincides with that of Bayes-optimal classifier f1η . If Ŷfδη = Ŷf1η , the conditional probability is max(ηA (X ′ ), 1 − ηA (X ′ )). On the other hand, if Ŷfδη ̸= Ŷf0η , it becomes 1 − |2ηA (X ′ ) − 1| P Ŷfδη = Y | X ′ , A = min(ηA (X ′ ), 1 − ηA (X ′ )) = . 2 Therefore, the accuracy of most fair classifier f0η can be written as 1 + |2ηA (X ′ ) − 1| 1 − |2ηA (X ′ ) − 1| η ′ ′ I(ηA (X ) ∈ / IA (1)) + EX ′ ,A I(ηA (X ) ∈ IA (1)) . Acc(f0 ) = EX ′ ,A 2 2
23
For a given tolerance δ, the predicted label Ŷfδη agree with Ŷf1η on the interval IA (δ). Accordingly, the accuracy of fδη satisfies 1 − |2ηA (X ′ ) − 1| Acc(fδη ) = Acc(f0η ) − EX ′ ,A · I(ηA (X ′ ) ∈ IA (δ) 2 1 + |2ηA (X ′ ) − 1| + EX ′ ,A · I(ηA (X ′ ) ∈ IA (δ) 2 = Acc(f0η ) + EX ′ ,A [|2ηA (X ′ ) − 1| · I(ηA (X ′ ) ∈ IA (δ)] = Acc(f0η ) + Accdep (fδη ).
Corollary C.1 (Applicability to Standard Fairness Metrics). The threshold functions κa (t) corresponding to DP, EOp, and PE, given in Eqs. (20), (21) and (23), satisfy the conditions required in Thm. 1. Specifically, for each fairness metric, the threshold κa (δ) varies monotonically with the fairness tolerance δ, and the distance |κa (δ) − 0.5| increases as the fairness constraint becomes more stringent, i.e., as δ decreases. Moreover, the corresponding fair Bayes-optimal classifier can be written in the form of Eq. (10). Consequently, Thm. 1 holds for DP, EOp, and PE. Proof. The classifiers for DP, EOp, and PE all admit the threshold form in Eq. (10), with thresholds given in Eqs. (20), (21) and (23). For each metric, differentiating the corresponding threshold functions shows that κ1 and κ0 vary monotonically in opposite directions with respect to the scalar threshold parameter. Moreover, at the unconstrained point, the thresholds reduce to 0.5, and moving toward a stricter fairness constraint shifts the thresholds away from 0.5. Hence, the conditions required in Thm. 1 are satisfied, and the theorem applies to DP, EOp, and PE.
C.2
Proof of Thm. 2 (Implicit Gradient of t)
Before stating our main result regarding the existence and uniqueness of the optimal parameter t, we formalize the necessary assumptions on the mapping function ψ and the threshold functions τa (t). Assumption C.1 (Strict Monotonicity of ψ). The mapping function ψ is strictly increasing such that ψ ′ (u) > 0 for any u ∈ R. Let T ⊂ R be the maximal open interval consisting of all parameters t for which the threshold functions γa (t) are strictly well-defined and yield finite real values for both a ∈ {0, 1}. Formally, we define this feasible domain as: T = {t ∈ R | γ0 (t) ∈ R and γ1 (t) ∈ R} = (p− , p+ ), where the boundaries p− and p+ naturally arise from the domain restrictions inherent to the definitions of γa (t). Over this interval T , we assume the following properties for the threshold functions: Assumption C.2 (Continuity). γ0 (t) and γ1 (t) are continuous on T . Assumption C.3 (Monotonicity). γ1 (t) is monotonically increasing and γ0 (t) is monotonically decreasing with respect to t.
24
Assumption C.4 (Sufficient Separation). There exist parameters within the open interval T that completely separate the shifted scores Zi − γa (t) between the two groups. Specifically, there exist t1 , t2 ∈ T such that for all i with ai = 1 and j with aj = 0, the following inequalities hold: Zi − γ1 (t1 ) < Zj − γ0 (t1 )
and
Zi − γ1 (t2 ) > Zj − γ0 (t2 ).
With these assumptions in place, we guarantee the existence and uniqueness of the threshold shifting parameter. Lemma 1 (Existence and uniqueness of t). Let ϕ be the surrogate fairness metric defined in Eq. (16). Suppose Assumptions C.1, C.2, C.3, and C.4 hold. Then, for any score vector Z ∈ Rn , there exists a unique parameter t∗ ∈ T that satisfies ϕ(Z, t∗ ) = 0. Proof. • Uniqueness. Fix any Z ∈ Rn . Since γ1 (t) is strictly increasing and γ0 (t) is strictly decreasing on T , and ψ ′ (u) > 0 for all u ∈ R, ψ(Zi − γ1 (t)) is strictly decreasing in t and ψ(Zi − γ0 (t)) is strictly increasing in t. Therefore, ϕ(Z, t) is strictly decreasing in t, and hence the equation ϕ(Z, t) = 0 has at most one solution. • Existence. Fix any Z ∈ Rn . We evaluate the limits of ϕ(Z, t) at the boundaries of T . (i) We first show that ϕ(Z, t) < 0 for some t ∈ T . Under the above assumptions, there exists a parameter t1 ∈ T that satisfies Zi − γ1 (t1 ) < Zj − γ0 (t1 ) for all i ∈ S1 and for all j ∈ S0 . Since ψ is a strictly monotonically increasing function, this order is strictly preserved: ψ Z − γ (t ) < i 1 1 ψ Zj − γ0 (t1 ) . Taking the average over each group, we have 1 X 1 X ψ Zi − γ1 (t1 ) < ψ Zj − γ0 (t1 ) . |S1 | |S0 | i∈S1
j∈S0
Consequently, at this t = t1 , we obtain ϕ(Z, t1 ) =
1 X 1 X ψ Zi − γ1 (t1 ) − ψ Zj − γ0 (t1 ) < 0. |S1 | |S0 | i∈S1
j∈S0
This confirms that there exists some t ∈ T such that ϕ(Z, t) < 0. (ii) We then show that ϕ(Z, t) > 0 for some t ∈ T . Under the above assumptions, there exists a parameter t2 ∈ T that satisfies Zi − γ1 (t2 ) > Zj − γ0 (t2 ) for all i ∈ S1 and for all j ∈ S0 . Sinceψ is a strictly monotonically increasing function, this order is strictly preserved: ψ Zi − γ1 (t2 ) > ψ Zj − γ0 (t2 ) . Taking the average over each group, we have 1 X 1 X ψ Zi − γ1 (t2 ) > ψ Zj − γ0 (t2 ) . |S1 | |S0 | i∈S1
j∈S0
Consequently, at this t = t2 , we obtain ϕ(Z, t2 ) =
1 X 1 X ψ Zi − γ1 (t2 ) − ψ Zj − γ0 (t2 ) > 0. |S1 | |S0 | i∈S1
j∈S0
This confirms that there exists some t ∈ T such that ϕ(Z, t) < 0. Since ϕ(Z, t) is continuous on T and there exist t1 , t2 ∈ T such that ϕ(Z, t1 ) > 0 and ϕ(Z, t2 ) < 0), the Intermediate Value Theorem guarantees the existence of at least one t ∈ T such that ϕ(Z, t) = 0. 25
Proposition C.1 (Derivation of the local gradient ∇1 t(Z)). Suppose Assumptions C.1, C.2, C.3, and C.4 hold. The function ϕ : Rn × R → R is continuously differentiable. For any Z0 ∈ Rn , let t0 = t(Z0 ) be the unique solution guaranteed by Lemma 1, so that ϕ(Z0 , t0 ) = 0. Since ψ ′ (u) > 0, we have ∇2 ϕ(Z0 , t0 ) ̸= 0. Therefore, by the Implicit Function Theorem, there exist a neighborhood U ⊂ Rn of Z0 and a neighborhood V ⊂ R of t0 , and a unique continuously differentiable local function t̃ : U → V such that ϕ(Z, t̃(Z)) = 0 ∀Z ∈ U. Moreover, its gradient is given by ∇1 t̃(Z) = −
∇1 ϕ(Z, t̃(Z)) . ∇2 ϕ(Z, t̃(Z))
(26)
Proof. By assumption, the function ϕ is continuously differentiable. For any Z0 ∈ Rn , let t0 = t(Z0 ) be the unique solution such that ϕ(Z0 , t0 ) = 0, whose existence and uniqueness are guaranteed by Lemma 1. Moreover, since ψ ′ (u) > 0, we have ∇2 ϕ(Z0 , t0 ) ̸= 0. Therefore, all the conditions of the Implicit Function Theorem are satisfied. As a result, there exists a neighborhood U of Z0 and a unique continuously differentiable local function t̃ : U → R such that ϕ(Z, t̃(Z)) = 0 for all Z ∈ U , and its gradient is given by Eq. (26). Having established the general theoretical guarantees, we now demonstrate that the threshold functions derived from common fairness metrics, specifically Demographic Parity (DP), Equal Opportunity (EOp), and Predictive Equality (PE), naturally satisfy Assumptions C.2, C.3, and C.4. Corollary C.2 (Applicability to Standard Fairness Metrics). The threshold functions γa (t) corresponding to DP, EOp, and PE satisfy Assumptions C.2, C.3, and C.4. Consequently, by Lem. 1, for Z ∈ Rn , there exists a unique optimal parameter t∗ ∈ T that strictly satisfies the fairness constraint ϕ(Z, t∗ ) = 0 for each of these metrics. Proof. We prove this corollary by verifying that the threshold functions for each fairness metric satisfy the required assumptions. Demographic Parity. For DP, the logit threshold functions γaDP (t) are given in Eq. (5). The feasible domain is T = (−p, p), where p = min(p0 , p1 ). This domain ensures that the arguments of the logarithms are strictly positive. • Continuity (Assumption C.2). For any t ∈ T , the log arguments in γaDP (t) are positive. Hence, γaDP (t) is continuous on T as a composition of continuous functions. • Monotonicity (Assumption C.3). The derivatives of the threshold functions with respect to t are 2p0 2p1 < 0, ∇1 γ1DP (t) = > 0. ∇1 γ0DP (t) = − (p0 − t)(p0 + t) (p1 − t)(p1 + t) Since t2 < p2 ≤ p2a for all t ∈ T , the denominators are positive. Therefore, γ1DP (t) is strictly increasing and γ0DP (t) is strictly decreasing, satisfying Assumption C.3. • Sufficient Separation (Assumption C.4). Assume without loss of generality that p = p1 ≤ p0 .
26
(i) As t → p from the left, γ1DP (t) → ∞. Thus, Zi − γ1DP (t) → −∞ for all i ∈ S1 . On the other hand, the group-0 terms do not diverge to −∞; in particular, γ0DP (t) remains finite if p1 < p0 , and diverges to −∞ if p1 = p0 . In either case, there exists t1 ∈ T such that Zi − γ1DP (t1 ) < Zj − γ0DP (t1 )
for all i ∈ S1 , j ∈ S0 .
(ii) As t → −p from the right, γ1DP (t) → −∞. Hence, Zi − γ1DP (t) → ∞ for all i ∈ S1 . Meanwhile, the group-0 terms do not diverge to +∞; if p1 < p0 , γ0DP (t) remains finite, and if p1 = p0 , γ0DP (t) → ∞. Therefore, there exists t2 ∈ T such that Zi − γ1DP (t2 ) > Zj − γ0DP (t2 )
for all i ∈ S1 , j ∈ S0 .
Thus, Assumption C.4 holds for DP. Equal Opportunity. For EOp, the logit threshold functions γaEOp (t) are given in Eq. (22). The feasible domain is T = (−p0,1 , p1,1 ), which guarantees that the logarithm arguments are positive. • Continuity (Assumption C.2). Throughout T , the log arguments in γaEOp (t) are strictly positive. Therefore, γaEOp (t) is continuous on T . • Monotonicity (Assumption C.3). Differentiating the two threshold functions gives ∇1 γ0EOp (t) = −
1 < 0, p0,1 + t
∇1 γ1EOp (t) =
1 > 0. p1,1 − t
Since −p0,1 < t < p1,1 , both denominators are positive. Hence, γ1EOp (t) is strictly increasing and γ0EOp (t) is strictly decreasing, as required. • Sufficient Separation (Assumption C.4). (i) As t → p1,1 from the left, γ1EOp (t) → ∞, while γ0EOp (t) converges to a finite value. Consequently, Zi − γ1EOp (t) → −∞ for all i ∈ S1 , whereas Zj − γ0EOp (t) remains bounded for all j ∈ S0 . Thus, there exists t1 ∈ T such that Zi − γ1EOp (t1 ) < Zj − γ0EOp (t1 )
for all i ∈ S1 , j ∈ S0 .
(ii) As t → −p0,1 from the right, γ0EOp (t) → ∞, while γ1EOp (t) remains finite. Therefore, Zj − γ0EOp (t) → −∞ for all j ∈ S0 , and there exists t2 ∈ T such that Zi − γ1EOp (t2 ) > Zj − γ0EOp (t2 )
for all i ∈ S1 , j ∈ S0 .
Thus, Assumption C.4 holds for EOp. Predictive Equality. For PE, the logit threshold functions γaPE (t) are given in Eq. (24). The feasible domain is T = (−p1,0 , p0,0 ), which ensures that the logarithm arguments are strictly positive. • Continuity (Assumption C.2). For every t ∈ T , the denominator pa,0 + (2a − 1)t is positive. Hence, γaPE (t) is continuous on T . • Monotonicity (Assumption C.3). The derivatives are ∇1 γ0PE (t) = −
1 < 0, p0,0 − t
∇1 γ1PE (t) =
1 > 0. p1,0 + t
Since −p1,0 < t < p0,0 , both denominators are positive. Therefore, γ1PE (t) is strictly increasing and γ0PE (t) is strictly decreasing. 27
• Sufficient Separation (Assumption C.4). (i) As t → p0,0 from the left, γ0PE (t) → −∞, while γ1PE (t) remains finite. Thus, Zj − γ0PE (t) → ∞ for all j ∈ S0 . Hence, there exists t1 ∈ T such that Zi − γ1PE (t1 ) < Zj − γ0PE (t1 )
for all i ∈ S1 , j ∈ S0 .
(ii) As t → −p1,0 from the right, γ1PE (t) → −∞, while γ0PE (t) remains finite. Consequently, Zi − γ1PE (t) → ∞ for all i ∈ S1 . Therefore, there exists t2 ∈ T such that Zi − γ1PE (t2 ) > Zj − γ0PE (t2 )
for all i ∈ S1 , j ∈ S0 .
Thus, Assumption C.4 holds for PE. Since all three fairness metrics satisfy the continuity, monotonicity, and sufficient separation assumptions, the proof is complete.
D
Experiments
D.1
Comparison methods
FairBayes FairBayes (Zeng et al. 2024) is a post-processing method derived from the theory of fair Bayes-optimal classifiers. It controls the balance between fairness and accuracy without requiring retraining by identifying the decision boundaries corresponding to specific trade-off parameters δ. To realize the fair bayes-optimal classifier ft∗∗ in practice, FairBayes empirically estimates the unknown δ distributional quantities in Eq. (3). Training phase: FairBayes learns group-dependent logit functions zaERM by empirical risk minimization with cross-entropy loss, and the learned logits are fixed thereafter. Prediction phase: Group-dependent thresholds τa (tδ ) are applied to the logits, where tδ is chosen to satisfy |DDP| ≤ δ. Using empirical estimates of group priors p̂a = na /n, the thresholds are given by Eq. (7). The parameter t̂δ is obtained by solving Eq. (9). EPO (Exact Pareto Optimal search). EPO (Mahapatra et al. 2020) is a multi-objective optimization method that controls the descent direction across multiple objectives in order to obtain a specific solution on the Pareto front corresponding to a given trade-off parameter. Since EPO is not originally proposed in the context of the trade-off between fairness and accuracy, we adapt it to this setting by defining task-specific objective functions. Specifically, we introduce two objective functions: Lacc for prediction accuracy and Lddp for fairness. Lacc follows the same definition as in Eq. (6), while Lddp is defined as a smooth approximation of DDP. Concretely, the indicator function in DDP is approximated by a scaled sigmoid function σ(·), and we define Lddp (f ) =
1 X 1 X σ(k f (xi , 1)) − σ(k f (xi , 0)) . n1 i;a=1 n0 i;a=0
The trade-off between these objectives is controlled by a reference vector v. Let vacc and vddp denote the components of the reference vector for the two objectives. EPO performs optimization by updating the model in a search direction that satisfies the weighted condition vacc Lacc = vf air Lddp and minimizes the weighted loss Lw (f ) = vacc (f ) Lacc (f ) + vddp (f ) Lddp (f ). 28
FairBiNN (Fair Bilevel Neural Network) FairBiNN (Yazdani-Jahromi et al. 2024) is a bilevel optimization framework for obtaining solutions on the fairness-accuracy trade-off corresponding to a given trade-off parameter. FairBiNN treats the accuracy loss Lacc as the upper-level objective and the fairness loss Lddp as the lower-level objective. We define Lacc and Lddp in the same way as in the EPO formulation. The optimization problem is formulated as ∗ ∗ min Lacc f (θacc , θddp ) s.t. θddp ∈ arg min Lddp f (θacc , θddp ) . θacc
θddp
Here, θacc and θddp denote the parameters of the accuracy and fairness layers, respectively. FairBiNN partitions a single neural network into accuracy and fairness layers, which are optimized separately according to their respective objectives. During training, θacc and θddp are updated alternately at each mini-batch. The trade-off between fairness and accuracy is controlled by a scaling parameter η ∈ R that scales the fairness loss during the fairness update. Different trade-off solutions are obtained by varying η, where larger values place greater emphasis on fairness. Consequently, FairBiNN requires training a separate model for each trade-off solution. YOTO (You Only Train Once). YOTO (Taufiq et al. 2024) is an in-processing method applied the original You Only Train Once framework (Dosovitskiy et al. 2020) to fair machine learning, aiming for the entire Pareto front with a single neural network. Following the terminology in (Taufiq et al. 2024), we refer to their adaptation as YOTO throughout this paper. YOTO incorporates the trade-off parameter λ directly as an input to the model via Feature-wise Linear Modulation (FiLM) (Perez et al. 2018). In this architecture, a FiLM layer applies an affine transformation to a given intermediate feature vector h: FiLM(h | λ) = γ(λ) ⊙ h + β(λ), where the scale γ(λ) and shift β(λ) are generated by a hypernetwork conditioned on λ. This mechanism allows the model to dynamically adapt its behavior to any given value of λ. In our experiments, following YOTO framework, we optimizes a λ-conditioned objective function: Lyoto (f, λ) = Lacc f (·; λ) + λLddp f (·; λ) . where f (·; λ) denotes a classifier conditioned on λ. The accuracy loss Lacc and the fairness loss Lddp are defined in the same way as in the EPO formulation. To ensure the model learns to represent classifiers across the entire trade-off range, the parameter λ is sampled at each iteration from a log-uniform distribution over [10−6 , 10].
D.2
Datasets
We summarize the target labels and sensitive attributes for each dataset in Table 3. CelbeA dataset The CelebA dataset (Liu et al. 2015) consists of 202,599 face images annotated with 40 binary facial attributes. In our experiments, we use “Attractive” as the prediction target. The sensitive attribute is gender.
29
Table 3: Summary of datasets, target labels, and sensitive features used in our experiments.
Target label (Y ) Sencitive Attrbute (A)
CelebA
UTKFace
Adult
COMPAS
Attractive Gender
Age ≥ 30 Gender
Income ≥ 50K Gender
2-year recidivism Race (Caucasian and others)
UTKFace dataset The UTKFace dataset (Zhang et al. 2017) contains over 20,000 face images labeled with age, gender, and race. We define the prediction task as determining whether an individual’s age is 30 or above. The sensitive attribute is gender. Adult dataset The Adult dataset (Kohavi 1996) is a tabular dataset comprising demographic and occupational attributes such as age, profession, and education level. The prediction task is to determine whether an individual’s annual income exceeds $50, 000. The sensitive attribute considered in this work is gender. COMPAS dataset The COMPAS dataset (Angwin et al. 2016) is a tabular dataset used for recidivism risk prediction in the criminal justice system. It contains features such as age, race, and prior criminal history. The prediction task is to determine whether a defendant will reoffend within two years. The sensitive attribute is race, which we binarize into Caucasian and non-Caucasian groups.
D.3
Metric
The fairness-accuracy trade-off efficiency is quantified using the hypervolume (HV) (Zitzler et al. 1998) over Acc and |DDP|. In this setting, the objective space is two-dimensional. Before defining the standard HV and the inverted HV used in our experiments, we first introduce a general hypervolume function. For an arbitrary trade-off set T and reference point r, the hypervolume function is defined as the area of the union of rectangles spanned by r and each solution in T (Badar et al. 2024): |T | [ HV T, r = Λ2 [ r, q(fi ) ] , i=1
where q(fi ) = (Acc(fi ), |DDP(fi )|) denotes the i-th solution in trade-off set T and |T | denotes the number of solutions in T . Here, [r, q(fi )] is the axis-aligned rectangle defined by r and q(fi ), and S|T | i=1 [r, q(fi )] denotes the union of these rectangles. The operator Λ2 (·) denotes the two-dimensional Lebesgue measure, which corresponds to the area of the region. In our experiments, we set the reference point following the procedure described in Jovanovic et al. (2022), which builds on Ishibuchi et al. (2018). We first define the reference point for standard HV, denoted by rstn = (racc , rddp ). Let Tj,s denote the non-dominated solutions S of the trade-off set obtained by algorithm j with seed s. The objective values of all solutions in j,s Tj,s are normalized to the range [0, 1] based on the extreme solutions observed across all algorithms and seeds. The reference point for the standard HV is then defined as racc = −
1 , N −1
rddp = 1 +
30
1 . N −1
(27)
Here, N = maxj,s |Tj,s | denotes the maximum number of non-dominated solutions among all compared algorithms and seeds. Thus, the reference point is obtained by shifting one unit of size 1/(N − 1) beyond the nadir point of the normalized objective space. The standard HV of a trade-off set T is then defined as HV (T, rstn ). ′ ′ Next, we define the reference point for inverted HV, denoted by rinv = (racc , rddp ). Let T̄j,s denote the set of non-Pareto-front, i.e., dominated, solutions obtained by algorithm j with seed s. We normalize these solutions using the same normalization procedure as above. Let N ′ = maxj,s |T̄j,s | denote the maximum number of dominated solutions among all compared algorithms and seeds. The reference point for the inverted HV is then defined as ′ racc =1+
1 , N′ − 1
′ rddp =−
1 . N′ − 1
Accordingly, the reference point is obtained by shifting one unit of size 1/(N ′ − 1) beyond the ideal corner of the normalized objective space, i.e., high accuracy and low DDP. The inverted HV of a trade-off set T is then defined as HV (T, rinv ). In the main experiments, each trade-off curve is evaluated using 10 trade-off parameters; therefore, both N − 1 and N ′ − 1 are at most 9. For the sensitivity analysis, we vary N − 1 and N ′ − 1 over 30 logarithmically spaced values from 2 to 80 and examine how the rankings of the methods change in Appendix D.5.3.
D.4
Implementation Details
D.4.1
Loss Function
For all methods, we adopt the Focal Loss (Lin et al. 2020) as the loss function ℓ to address the inherent class imbalance in datasets. Originally proposed for dense object detection to reduce the dominance of easy-to-classify background examples, the Focal Loss is defined as FL(pt ) = −(1 − pt )γ log(pt ), where pt is the model’s estimated probability for the ground-truth label, defined as ( p, if y = 1, pt = 1 − p, otherwise, with p being the model’s estimated probability for the class with label y = 1. By introducing the focusing parameter γ, the loss effectively down-weights the contribution from easy examples and directs the optimization toward hard, underrepresented ones. Note that γ = 0 reduces to standard cross-entropy. D.4.2
Trade-off parameter selection
For a fair comparison, we evaluate the trade-offs obtained under ten different trade-off parameters for each method. For the proposed method and FairBayes, the trade-off is controlled by the fairness tolerance δ, and the corresponding thresholds are determined using a holdout set. Specifically, we first compute the DDP at the Bayes-optimal threshold 0, denoted by δmax , and then uniformly sample ten fairness tolerances δ from the interval [0, δmax ]. 31
For EPO, trade-off parameters are the reference vectors. Following Mahapatra et al. (2020), we use ten reference vectors that are evenly spaced in angle between (vacc , vddp ) = (1, 0) and (0, 1). For YOTO, trade-off parameters are the weighting parameter λ. We first compute the DDP obtained at λ = 0 and denote it by δmax . We then uniformly sample ten target fairness tolerances δ from the interval [0, δmax ]. For each target δ, we estimate the corresponding λδ via a binary search on a logarithmic scale over the range λ ∈ [10−6 , 10], such that the resulting classifier attains a DDP value close to the target tolerance δ. Different trade-off points are obtained by performing inference with the classifier conditioned on λδ . D.4.3
Network Architecture
For image datasets, we use a ResNet-18 backbone pre-trained on ImageNet, followed by a two-layer multilayer perceptron (MLP). The MLP classifier consists of two fully connected layers with ReLU activation, mapping the ResNet feature representation to a scalar logit. In the proposed framework, the ResNet-18 backbone is treated as the distribution transformation g, while the MLP serves as the classification head f . Conversely, baseline methods treat the entire network as a single classifier. For YOTO, we replace the standard MLP with a FiLM-conditioned MLP to enable trade-off conditioning. Following Taufiq et al. (2024), the hypernetwork used to generate the FiLM parameters γ(λ) and β(λ) is implemented as a four-layer MLP. For FairBiNN, we adopt the same overall network architecture and apply the layer-partitioning strategy of Yazdani-Jahromi et al. (2024). Specifically, the early and intermediate blocks of the ResNet-18 backbone are treated as the first accuracy component, the final residual block group of ResNet-18 is treated as the fairness component, and the subsequent MLP classifier is treated as the second accuracy component. For tabular datasets, we utilize TARTE (Kim et al. 2025), a Transformer-based foundation model, as a fixed feature extractor. Following the architecture in Kim et al. (2025), we feed the readout token’s representation into an MLP classifier. We use a 7-layer MLP for Adult and a 5-layer MLP for COMPAS. In our method, the final two layers of the MLP act as the classification head f , with the preceding layers serving as the transformation module g. For baseline comparisons, the entire MLP is treated as f , and for YOTO, it is replaced with a FiLM-conditioned architecture. The hypernetwork is implemented as a two-layer MLP, consistent with the configuration in Taufiq et al. (2024). For FairBiNN, we use the same TARTE-based architecture and partition the trainable MLP layers following Yazdani-Jahromi et al. (2024). Specifically, we split the trainable MLP after TARTE into three parts: early accuracy layers, intermediate fairness layers, and a final accuracy head. The fairness layers correspond to the later transformation layers placed before the final accuracy head, while the remaining trainable layers are treated as accuracy layers. D.4.4
Hyperparameter Tuning
For the proposed method and FairBayes, we select the model that achieves the largest HV on the validation set. To compute HV, we first evaluate the DDP at the Bayes-optimal threshold 0 and denote it as δmax . We then construct a trade-off curve by uniformly sampling 50 fairness tolerances δ ∈ [0, δmax ]. To ensure a consistent comparison across epochs, the reference point for the validation HV is fixed at the worst-case point (racc , rddp ) = (0, 1). For EPO, we select the model that minimizes the weighted loss on the validation set. For YOTO, we select the model that minimizes the validation loss. A single model is conditioned on a weighting parameter λ, which does not directly correspond to the fairness tolerance δ. While it is in principle possible to evaluate validation HV by fixing a set of λ values, this would require performing inference for each λ over the entire validation set at every epoch, resulting in a substantially higher computational cost. 32
Table 4: Wall-clock time (seconds) on the CelebA dataset for all methods (averaged over 5 seeds). * per parameter for EPO/FairBiNN/YOTO, 10 parameters for FairBayes/GFB. EPO Train Adaptation Inference*
FairBiNN 3
4.58 × 10 same as above 5.72 × 100
3
2.24 × 10 same as above 5.88 × 100
YOTO 3
1.77 × 10 0 5.03 × 100
FairBayes
GFB (Ours)
3
2.98 × 103 5.16 × 10−2 5.55 × 100
1.78 × 10 5.10 × 10−2 5.52 × 100
Table 5: Wall-clock time (seconds) on the UTKFace dataset for all methods (averaged over 5 seeds). * per parameter for EPO/FairBiNN/YOTO, 10 parameters for FairBayes/GFB. EPO Train Adaptation Inference*
D.4.5
FairBiNN 3
1.49 × 10 same as above 1.52 × 100
2
7.67 × 10 same as above 1.61 × 100
YOTO 2
5.75 × 10 0 1.56 × 100
FairBayes
GFB (Ours)
2
9.61 × 102 9.38 × 10−3 1.66 × 100
5.65 × 10 9.66 × 10−3 1.43 × 100
Computing Environment
The core software stack consisted of Python 3.12.3 and PyTorch 2.6.0a0. For GPU acceleration, we utilized CUDA 12.8 with NVIDIA driver version 535.183.01. All computations and model training were performed on an NVIDIA A100-SXM4-40GB GPU.
D.5
Additional Experimental Results
D.5.1
Training Cost
We evaluated computational time on all datasets, as shown in Tables 4 to 7. In these Tables, “Train” reports the training time for 100 epochs, excluding hyperparameter tuning, “Adaptation” denotes the additional computation time required when changing the trade-off parameter (threshold estimation for FairBayes/GFB, retraining for EPO), and “Inference” denotes the time required to produce predictions on the test set. For FairBayes and GFB, the training time includes one forward pass on a holdout set used for threshold estimation to compute logits. The training time of GFB is approximately 1.2-1.7 times longer than that of FairBayes. However, we believe that this moderate increase in training cost does not undermine the overall benefits of our method. In particular, GFB consistently outperforms FairBayes and YOTO across all datasets with smaller standard deviations in most cases. This suggests that GFB provides a more stable trade-off performance. Moreover, after training, GFB retains the lightweight post-hoc adjustment of FairBayes Table 6: Wall-clock time (seconds) on the Adult dataset for all methods (averaged over 5 seeds). * per parameter for EPO/FairBiNN/YOTO, 10 parameters for FairBayes/GFB. EPO Train Adaptation Inference*
FairBiNN 2
1.15 × 10 same as above 4.82 × 10−1
YOTO
2
1.02 × 10 same as above 6.36 × 10−1
33
1
7.89 × 10 0 5.19 × 10−1
FairBayes
GFB (Ours)
1
1.07 × 102 1.60 × 10−2 5.11 × 10−1
7.51 × 10 1.61 × 10−2 5.06 × 10−1
Table 7: Wall-clock time (seconds) on the COMPAS dataset for all methods (averaged over 5 seeds). * per parameter for EPO/FairBiNN/YOTO, 10 parameters for FairBayes/GFB. EPO Train Adaptation Inference*
FairBiNN 1
6.71 × 10 same as above 4.11 × 10−1
YOTO
1
5.48 × 10 same as above 5.44 × 10−1
1
4.78 × 10 0 4.19 × 10−1
FairBayes
GFB (Ours)
1
6.09 × 101 5.53 × 10−3 4.35 × 10−1
4.90 × 10 5.58 × 10−3 4.61 × 10−1
and achieves shorter inference time than YOTO. These results suggest that, despite the additional training cost, GFB remains practical for settings where the desired fairness–accuracy trade-off may change after deployment. Compared with in-processing methods, GFB consistently requires less training time than EPO. On the other hand, GFB takes approximately 1.04–1.33 times longer to train than FairBiNN. However, unlike EPO and FairBiNN, which require retraining when the trade-off parameter changes, GFB only needs lightweight threshold adaptation after training. As shown in Tables 4 to 7, this adaptation is substantially faster than retraining and enables efficient post-hoc control of the fairness-accuracy trade-off. Considering the consistent improvements over FairBayes and YOTO discussed above, together with the practical benefit of post-hoc controllability, we regard the additional training cost of GFB as acceptable. D.5.2
Quartile Analysis of HV and Inverted HV Differences
To assess the reliability of the results across random seeds, we report the mean and quartiles of the seed-wise differences for both HV and inverted HV in Tables 8 and 9, respectively. All values are computed as GFB minus the corresponding competitor. For HV, positive values indicate that GFB achieves higher HV, whereas negative values indicate that the competitor achieves higher HV. When all quartiles are positive, GFB consistently outperforms the competitor across seeds; when all quartiles are negative, the competitor consistently achieves higher HV. Mixed signs among the quartiles indicate that the relative performance varies across seeds. For inverted HV, negative values indicate that GFB achieves lower inverted HV. When all quartiles are negative, GFB consistently has fewer poorly performing dominated solutions than the competitor across seeds. Compared with EPO, all quartiles are positive on CelebA and Adult, indicating that GFB consistently achieves higher HV across seeds on these datasets. On UTKFace, only the first quartile is negative, while the median and third quartile are positive. This suggests that GFB generally outperforms EPO, although the advantage is not uniform across all seeds. On COMPAS, only the third quartile is positive. This indicates that EPO achieves higher HV in typical runs, although GFB outperforms EPO in some seeds. However, the inverted HV comparison in Table 9 provides a complementary view: all quartiles are negative on COMPAS, meaning that GFB consistently achieves smaller inverted HV than EPO across seeds. Thus, although EPO has an advantage in terms of standard HV on COMPAS, GFB avoids poorly performing trade-off points more consistently. Overall, these results suggest that GFB is competitive with, and often outperforms, EPO, while additionally providing post-hoc controllability. We next compare GFB with FairBiNN. On CelebA and Adult, all quartiles are positive, showing that GFB consistently achieves higher HV across seeds. On COMPAS, only the third quartile is positive, 34
Table 8: Comparison of hypervolume differences (mean and quartiles). Q1 , Q2 , and Q3 denote the first, second, and third quartiles, respectively. All values denote differences from GFB (GFB − competitor); positive values indicate that the proposed method performs better. Dataset
Method
Mean
Q1
Q2
Q3
CelebA
vs. EPO vs. FairBiNN vs. FairBayes vs. YOTO
0.0465 0.1279 0.0941 0.2130
0.0692 0.0891 0.0874 0.1087
0.0695 0.1100 0.0927 0.2060
0.0808 0.1759 0.0976 0.2877
UTKFace
vs. EPO vs. FairBiNN vs. FairBayes vs. YOTO
0.0125 -0.0295 0.0379 0.1100
-0.0316 -0.0428 0.0184 0.0545
0.0321 -0.0313 0.0259 0.1415
0.0513 -0.0131 0.0673 0.1632
Adult
vs. EPO vs. FairBiNN vs. FairBayes vs. YOTO
0.0770 0.0452 0.0157 0.1515
0.0481 0.0170 0.0203 0.1247
0.0829 0.0426 0.0244 0.1443
0.0844 0.0564 0.0306 0.1671
COMPAS
vs. EPO vs. FairBiNN vs. FairBayes vs. YOTO
-0.0027 -0.0238 0.0566 0.1722
-0.0408 -0.0331 -0.0151 0.1260
-0.0243 -0.0284 0.0019 0.1854
0.0552 0.0047 0.1459 0.2894
indicating that FairBiNN achieves higher HV in typical runs, while GFB outperforms FairBiNN in some seeds. On UTKFace, all quartiles are negative, showing that FairBiNN consistently achieves higher HV across seeds. Overall, GFB achieves higher HV than FairBiNN on CelebA and Adult, remains competitive on COMPAS, and underperforms on UTKFace. Nevertheless, The inverted HV comparison provides a complementary view. As shown in Table 9, all quartiles of the inverted HV differences are negative across all datasets, indicating that GFB consistently achieves smaller inverted HV than FairBiNN across seeds. This suggests that, although FairBiNN shows an advantage under the standard HV metric on COMPAS and UTKFace, GFB more consistently avoids poorly performing dominated solutions. These results suggest that GFB provides a more stable trade-off curve overall, while additionally offering post-hoc controllability, which FairBiNN does not provide. We then compare GFB with YOTO. All quartiles of the HV differences are positive across all datasets. This indicates that GFB consistently achieves higher HV than YOTO across seeds. Moreover, the inverted HV differences are negative for all datasets, showing that GFB also avoids poorly performing dominated solutions more consistently. Thus, GFB clearly outperforms YOTO in terms of both HV and inverted HV. Finally, we compare GFB with FairBayes. All quartiles are positive on CelebA, UTKFace, and Adult, indicating that GFB consistently achieves higher HV across seeds on these datasets. On COMPAS, only the first quartile is negative, while the median and third quartile are positive. This suggests that GFB generally achieves higher HV than FairBayes, although the advantage is not uniform across all seeds. Nevertheless, GFB achieves a higher mean HV with a smaller standard deviation, suggesting more favorable and stable performance overall on COMPAS. The inverted HV comparison provides further evidence for this interpretation. Against FairBayes, all quartiles of the inverted
35
Table 9: Comparison of inverted Hypervolume differences (mean and quartiles). Q1 , Q2 , and Q3 denote the first, second, and third quartiles, respectively. All values denote differences from GFB (GFB − competitor); positive values indicate that the proposed method performs better. Dataset
Method
Mean
Q1
Q2
Q3
CelebA
vs. EPO vs. FairBiNN vs. FairBayes vs. YOTO
-0.2295 -0.1561 -0.0354 -0.0955
-0.3732 -0.1569 -0.0461 -0.0620
-0.1988 -0.1466 -0.0300 0.0139
-0.1032 -0.1375 -0.0218 0.0150
UTKFace
vs. EPO vs. FairBiNN vs. FairBayes vs. YOTO
-0.3432 -0.1569 -0.0546 -0.0548
-0.7351 -0.1557 -0.0766 -0.0976
-0.0696 -0.1443 -0.0556 -0.0673
-0.0606 -0.1169 -0.0553 -0.0456
Adult
vs. EPO vs. FairBiNN vs. FairBayes vs. YOTO
-0.2287 -0.0993 -0.0015 -0.1800
-0.2617 -0.1145 -0.0103 -0.1630
-0.2257 -0.0976 -0.0101 -0.1619
-0.1831 -0.0798 0.0090 -0.1515
COMPAS
vs. EPO vs. FairBiNN vs. FairBayes vs. YOTO
-0.0809 -0.0756 -0.0326 -0.2263
-0.1011 -0.0798 -0.0464 -0.2937
-0.0714 -0.0756 -0.0419 -0.2009
-0.0678 -0.0645 -0.0383 -0.1565
HV differences are negative across all datasets, indicating that GFB more consistently avoids poorly performing trade-off points. We also examine the standard deviations reported in Table 1 and Table 2 to assess variability across random seeds. For HV, GFB shows small standard deviations on most datasets; in particular, it achieves the smallest standard deviation on CelebA, Adult, and COMPAS. A similar trend is observed for inverted HV, where GFB again shows small standard deviations, including the smallest value on CelebA and COMPAS. These results suggest that the proposed boundary-concentration mechanism improves the fairness-accuracy trade-off over post-hoc controllable methods without introducing additional variability across random seeds. D.5.3
Sensitivity Analysis of HV and inverted HV
We further analyze the sensitivity of both HV and inverted HV rankings to the choice of the reference point. Specifically, we vary the distance between the reference point and the trade-off curves and examine how the rankings change. To do so, we vary the value of N − 1 in the reference-point construction in Eq. (27) over logarithmically spaced values from 2 to 80. As shown in Fig. 5, the HV rankings remain unchanged on CelebA and Adult, and only limited changes are observed on UTKFace and COMPAS. We observe a similar trend for the inverted HV: although slight ranking changes appear on COMPAS and some curves overlap on datasets other than CelebA, the rankings do not change substantially across the examined range of reference points. These results suggest that the main conclusions drawn from HV and inverted HV are not strongly affected by the choice of the reference point.
36
(a) CelebA
(b) UTKFace
(c) Adult
(d) COMPAS
Figure 5: Sensitivity of HV to the reference-point choice. The horizontal axis represents the proximity of the reference point to the trade-off curves, represented by N − 1, and the vertical axis represents the HV value. The star marks the value used for the main HV results in Table 1.
(a) CelebA
(b) UTKFace
(c) Adult
(d) COMPAS
Figure 6: Sensitivity of inverted HV to the reference-point choice. The horizontal axis represents the proximity of the reference point to the trade-off curves, represented by N − 1, and the vertical axis represents the inverted HV value. The star marks the value used for the main inverted HV results in Table 2.
37