Fair Representation Learning with Controllable High Confidence Guarantees via Adversarial Inference
Authors: Yuhong Luo
Austin Hoag
Xintong Wang
Philip S. Thomas
Przemyslaw A. Grabowicz
Venue: NeurIPS 2025 poster ()
Keywords: Fair Representation Learning
Statistical Guarantees
Controllable Guarantees
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We introduce a representation learning framework that provides high-confidence fairness guarantees with controllable error thresholds and confidence levels via adversarial inference.

Abstract: Representation learning is increasingly applied to generate representations that generalize well across multiple downstream tasks. 
Ensuring fairness guarantees in representation learning is crucial to prevent unfairness toward specific demographic groups in downstream tasks.
In this work, we formally introduce the task of learning representations that achieve high-confidence fairness. 
We aim to guarantee that demographic disparity in every downstream prediction remains bounded by a *user-defined* error threshold $\epsilon$, with *controllable* high probability.
To this end, we propose the ***F**air **R**epresentation learning with high-confidence **G**uarantees (FRG)* framework, which provides these high-confidence fairness guarantees by leveraging an optimized adversarial model. 
We empirically evaluate FRG on three real-world datasets, comparing its performance to six state-of-the-art fair representation learning methods. 
Our results demonstrate that FRG consistently bounds unfairness across a range of downstream models and tasks.

Fair Representation Learning with Controllable High Confidence Guarantees via Adversarial Inference
Yuhong Luo
Austin Hoag Sony AI New York, NY, USA austin www.hhaaagn......o.. com
Rutgers University New Brunswick, NJ, USA lwoorutgers.eerr edu
Xintong Wang Rutgers University
Philip S. Thomas University of Massachusetts
New Brunswick, NJ, USA
Amherst, MA, USA pthomasOcs umass edu
xintong. wangorutgers.com edu
Przemyslaw A. Grabowicz 1,2
University College Dublin, Ireland
University of Massachusetts, Amherst, MA, USA przemek. graboviczouccd.d
Abstract
Representation learning is increasingly applied to generate representations that generalize well across multiple downstream tasks. Ensuring fairness guarantees representation learning is crucial to prevent unfairness toward specific demographic groups in downstream tasks. In this work, we formally introduce the task of learning representations that achieve high-confidence fairness. We aim to guarantee that demographic disparity in every downstream prediction remains bounded by user-defined error threshold e, with controllable high probability. To this end, we propose the Fair Representation learning with high-confidence Guarantees (FRG) framework, which provides these high-confidence faimess guarantees by leveraging an optimized adversarial model. We empirically evaluate FRG on three real-world datasets, comparing its performance to six state-of-the-att fair representation learning methods. Our results demonstrate that FRG consistently bounds unfaimess across range of downstream models and tasks. The source code for FRG available at: https: //t:::////ttt....// com/ JamesLuoyh/FRG
1 Introduction
In every prediction task, machine learning algorithms assume two distinct roles: the data producer and
the data consumer 19 48 75.. The data consumer's role make accurate predictions using the data provided by the data producer. While the data producer may distribute raw data, it is common to generate new representations via representation learning for the input data that are used predictors in downstream tasks. When multiple data consumers' prediction tasks involve inputs of the same type, such as natural language text images, the data producer can generate general representations that are predictive to multiple subsequent tasks. This is an increasing trend with examples including the Variational Eito-En (VAE) 38 or recent language models such as BERT [16] and GPT-4 [58). which are widely used as bases for downstream text classification tasks [3]
While representation learning can benefit various downstream predictions, it is also susceptible the risk of producing unintended undesirable behaviors in the downstream tasks, specifically, generating predictions that are unfair toward disadvantaged demographic groups. Especially in critical
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

domains, such as loan underwriting 19], hiring [53] and criminal sentencing 4 the consequences of algorithmic bias may severely impact individuals. To address these concerns, researchers have proposed fair representation learning (FRL), emphasizing that fairness should be the responsibility of the data producer who generates the representations [48] 75), rather than the data consumer who uses them. By ensuring fairness at the representation level, the data producer guarantees fairesss across all downstream tasks, allowing the representations to be safely used by any data consumer.
Extensive prior work in FRL has shown effectiveness in promoting faimess for specific downstream tasks. Some methods (2 26 48 [51 estimate upper bounds for the unfairness across all downstream models and tasks based on the training dataset. However, there is no guarantee that these estimations give true upper bounds. These bounds can be underestimated because of overfitting to the training and validation sets. Thus, when their models are deployed on unseen test data, they can fail the desired fairness requirements. This calls for statistical guarantees such as high-confidence guarantees.
figh-conniience guarantees are required to ensure that the unfairness across all downstream models and tasks will be consistently bounded with high probabilities. In many areas of supervised learning, providing high-confidence guarantees is considered essential for ensuring the fairness, privacy, and safety of the learning algorithm [1 of FRL as the absence of such guarantees can lead to undesired behaviors across multiple downstream applications. In FRL, a method called FARE [33 provides certificates that the downstream unfairness will be bound by some threshold with high probability. However, how to let users explicitly control the error thresholds and confidence levels jointly for the high-confidence guarantees is unexplored.
18
43 70]. This need becomes even more critical in the context
We propose Fair Representation learning with high-confidence Guarantees (FRG), the first work to our knowledge that guarantees with high confidence that the output representation models are "fair" according to user-specified thresholds of unfairness and confidence levels. The fairness criterion we focus on is demographic parity (DP) [19. a group fairness notion (the extension to equal opportunity and equalized odds will be discussed in Appendix C.. A fair representation model ensures that, across arbitrary downstream tasks and models, the largest difference in positive prediction rate- denoted as AD (defined in Sec. 3 - is bounded by an error threshold ε E [o, 1]. Thus, once a user designates threshold for ADP and confidence level. FRG guarantees with high confidence that any (including adversarial) downstream tasks and models using the representations generated by its learned representation model will not exceed the threshold Equivalently, the representation models output by FRG will have a high probability of satisfying the desired fairness constraint even when applied to a worst-case adversarial downstream model.
FRG consists of three major components: (1) the candidate selection component proposes a represen- tation model that will likely satisfy the fairness constraint with high probability; (2) the adversarial inference component aims to utilize the representations learned by the proposed model adversarially predict the sensitive attributes to maximize ADP; and (3) the fairness test component establishes high-confidence upper bound on the worst-case downstream App based on the "optimal" adversarial prediction to determine whether the proposed model passes the test and should be returned.
We provide theoretical justification for the high-confidence fairness guarantees based on the assump- tion that the fairness test has access to an optimal adversary (defined in Sec. (5) which is approximated with optimization. We find direct mapping between ADP and the absolute covariance between the sensitive attributes and the predictions, so the optimal adversary can be achieved by maximizing the absolute covariance. Alternatively, it is possible find a high-confidence upper bound via the upper bounds on APP as derived by previous work (26 68) to avoid relying on training an optimal adversary. However, our study shows that these upper bounds are typically loose and thus impractical for establishing guarantees while preserving utility (Appendix MM. Specifically, there exists non-trivia gap between App and its theoretical upper bound (as demonstrated in Appendix Figure and 13
In experiments, we use three real-world datasets each with 2-3 tasks to verify that FRG can indeed be used to learn fair representation models that satisfy the faimess criteria with the desired high probability. Compared to FRG, six state-of-the-art (SOTA) FRLs either violate the fairness constraints with non-trivial probability (at least 0.1) achieve lower predictive performance than FRG.
2 Related Work
Fair representation learning (FRL) has been studied for at least decade 75 While stream of FRL studies optimizing the representations for a specific downstream task 10
67 74 77).
numerous FRL methods learn general representations 2 30 52 that are fair, even when downstream

---

tasks are unknown or unlabeled. One category of these methods draws inspiration from information
and probability theory 126
35
45
63
68 72 One work explores the use of
distance covariance
44 Some methods can limit downstream unfairness by constraining the
total variation distance between the representation distributions of different groups [5] 48 66 76].
Other approaches promote independence from sensitive attributes through penalizing Maximum
Mean Discrepancy [I5] 47 [6] or statistical dependence [25] [1]. meta-learning [57]. PCA
42),
learning a shared feature space between groups [1), or disentanglement [14 46
55 A stream
of work uses adversarial training that limits the adversary's 's performance in predicting sensitive
attributes [20 22 36 60, 71. Different from these methods, FRG constructs high-confidence
guarantees based on a separately trained adversary without joint optimization with the primary objective under fairness constraints, which is considered more reliable than adversarial training.
66 76 prove upper bounds on the unfairness of all downstream models and tasks. These bounds can be estimated and verified with training and validation set. However, these bounds may fail to generalize to an unseen test set. Some other works [5] 23 33 provide statistical guarantees for test data. For example, FARE [33] provides practical certificates that serve as high-confidence upper bounds on downstream unfairness. Different from these methods, our framework provides an explicit way to control both the confidence level and error threshold for all downstream models, and yields tighter empirical bounds (Section 6).
Some FRI.s provide theoretical analyses. Several works 26
Furthermore, in this study we focus on group faimess [9 (7]. one of the most widely used fairness measures, including in legal setting, c.g., the New York City Local Law 144 on Automated Employment Decision Tools and in the EEOC's rule of 80% hiring rates across sensitive groups
focus on another important measure, i.e., individual fairesss, without providing high confidence guarantees. Finally, some prior work [28] 43 70 provides
Some prior works [40 41
59 64
high-confidence guarantees for fair classification, but does not explore representation learning.
3 Preliminaries
We first introduce notations for representation learning and the unfairness measure we focus on. Let X be a random variable denoting the feature vector, and S random variable denoting sensitive attributes. D = {X., S.) denotes dataset with i.i.d. data samples, where each (X,, has the same joint distribution as (X, S). Let D be the set of all D's, á E 4 be the representation model parameters, and do be the representation model parameterized by é. We define as the representation for SX where Z ~ (o(-IX, S) and Z E TR.
The learned representation will be used for subsequent supervised learning downstream tasks. We denote the label for such a downstream task as the random variable Y. The objective in downstream task is to predict Y given (X, It is common to use Z in place of (X, S) as input to downstream model R + R. Let Y == r()) denote the prediction of Y by model r. We call Ý the downstream prediction. There can be multiple downstream tasks that make use of the same representation Z.
The goal is to learn a fair representation model that ensures specified notion of fairness across downstream tasks and models. In this work, we focus on binary classification taske and a widely used group fairness objective called demographic parity (DP) 19] The extension to Equal Oppertunity and Equalized Odds will be discussed in Appendix C Below we formally defin a measure of demographic disparity of how unfair downstream model T is under DP.
Definition 3.1 (Demographic disparity measure). Let ADP(T, Φ) represent the measure of unfairness in the downstream predictions Y produced by model + when using representation parameters Φ Specifically, ADP (7, 6) Prr(Ý- = 1|$ 1) - Pr(ý 1|5 = 0)}-
For simplicity, we assume that Y and S are binary, and this definition can be generalized to non-binary settings. When S is non-binary, (T Φ) is defined as the maximum absolute difference between the conditional probabilities, Pr(y = 1[S), with any pair of values of S g (Appendix A).
Problem Formulation
This section formulates the task of representation learning with high-confidence fairness guarantees.
FRG can be easily extended to provide similar guarantees for non binary classification and regression by limiting Cov(S, 2). We focus on binary classification due to its prevalence in literature and legal systems.
3

---

{,
Candidate Selection
Pc
Fairness Test
D
Adversarial Interence
Dj
Ø or NSF
Figure 1: An overview of the FRG framework. Given a dataset D, with prohability 8. FRG generates an "s-fair" representation model, or returns NSF if such a model cannot be found. See Section for discussion.
fair representation model should ensure with high confidence that the representations generates will not lead to unfairness for downstream tasks. Specifically, representation model is fair if and only if results fair predictions (as defined in Def.3.11 for every possible downstream model and downstream task. That is, for all downstream tasks and all ADP(T; Φ) must be upper-bounded by small constant, E. We define an "s-fair" representation model as follows.
Definition 4.1 ("e-fair" representation model). Representation model ye E-fair with parameter & E [0, 1] if and only if ADP(T, +) S E, for every downstream model and downstream task.
We define a representation learning algorithm a : D - & be an algorithm that takes data set as input and produces representation model parameters as output. In this paper, we aim to provide a representation learning algorithm such that any representation model it learns is guaranteed to be e E-fair under Def. 4.1 with high confidence. Such an algorithm has the following formal definition.
Definition 4.2 (A representation learning algorithm with high-confidence fairness guarantees). Given 1), (0, 1), and dataset D, representation learning algorithm a is said to provide 1 - 5 confidence g-fairness guarantee if and only if Pr (ox (a(D)) S 0) 2 - 5, where 9s (6) == sup, ADP(A) 6) E.
Observe that ds is an E- E-fair representation model if and only if (o) S O (Def. 4.1. Therefore, any algorithm under Def. 4.2 guarantees that any representation model with parameters learned by this algorithm has at least I-6 probability to be an E-fair representation model. Algorithms of this form can generally be categorized as Seldonian algorithms (70). This guarantee implies that even in the worst case (when downstream models are adversarial), any resulting representation model should not fail the f-iiresss constraint with probability larger than 8.
Special case: unachievable e-fair representation models. We note that some scenarios, may not be possible for any non-degenerate algorithm to ensure fairness with the specified confidence 1- 6, e.g., when e, 6, and the amount of training data are all very small. In such cases, we allow the algorithm to output No Solution Found (NSF) way of indicating that it is unable to provide the required confidence that the learned representation will be fair given the amount of data has been provided. To indicate that it is always fair for the algorithm to return NSF, we set 9s (ω) O. However, an algorithm constantly returns MSF, it is no value. We empirically evaluate the probability of returning solution (i.e., not NSF) in Section 6
5 Methodology
We now introduce our proposed framework. i.e., Fair Representation learning with high-confidence Guarantees (FRG). It is the first representation learning algorithm that provides user-defined high-confidence fairness guarantee. An overview of FRG is provided in Fig.
FRG consists of three major components: candidate selection, adversarial inference and fairness test. First, we present high-level summary of the algorithm before discussing each component in detail. FRG first splits the data D into disjoint sets, De and Dy. Candidate selection uses D. to optimize and propose candidate solution &c. We train an adversarial model to predict sensitive attributes using the representations D. as learned by the model qø. The faimess test uses predictions made by the adversarial model on Dj to evaluate whether d. can satisfy ge (Φ.) < 0 on future unseen data with sufficient confidence. Finally, FRG returns o. if the fairness test is passed and NSF otherwise. While it is the faimesss test that ensures the high-confidence guarantees, an effective candidate selection that reasons about the fairness test procedure is needed to maximize the likelihood of passing the test.
In this section, we first define an optimal adversary and propose an effective optimization for the adversarial model to achieve approximation of the optimum. We then introduce the fairness

---

test assuming the access to an oracle optimal adversary. Lastly, we provide details for a candidate selection that proposes candidates that aim pass the fairness test and achieve high expressiveness.
5.1 Adversarial Inference
To learn an adversarial downstream model Tady that best predicts the sensitive attribute S, we generate the representations for De using proposed candidate representation model 4e_ input to Tadv We define an optimal adversary adv to be one that maximizes the ÅDP (Def. 5.T), and prove in Theorem 5.2 that when both S and Y are binary, there exists a mapping between App and the absolute covariance between y and S (denoted as |Cov(Y, S) The extension to non-binary sensitive attributes is provided Appendix D
Definition 5.1 (Optimal adversary). Given representation model gø. downstream model T an optimal adversary if and only if Ta E arg max, ADe(T, 6).
Theorem 5.2. Suppose S, E 10, 1] are Bernoulli random variables. We have ØD =
[Cov(Y (S) Proof. See Appendix B Sa
we have Tady E arg max, [Cov(Y, 5S] arg max, ADp(T, ()) Intuitively. the worst-case DP is achieved when the adversary is optimal either in predicting S or 1 S, and thus achieves either max, Cov(Y, S) or min, Cov(Y, S) (that are inversely correlated). In practice (Sec. [). we find it sufficient to train an approximately optimal adversary to predict based on Z using traditional gradient-basee optimization strategies. We train Tadv with representations and sensitive attributes from De. which will then be used by the fairness test to evaluate on Dy.
Following Theorem 5.2
5.2 Fairness Test
The fairness test aims to evaluate whether a candidate solution de induces a fair representation model with high confidence. In this section, we propose constructing a high-confidence upper bound on Ie (6), assuming access to an optimal adversary Taay (Def. 5.1). which in practice will be approximated by the adversarial model. If this high-confidence upper bound most zero, then we can conclude that 9a (ō) < O with confidence 1 5. We then detail the evaluation process for candidate solution &e and show that it satisfies the 5 confidence e-fairness guarantee.
5.2.1 1 confidence upper bound on (e)
We detine U. (L,D) + R to be such a function that produces 1 - 8 confidence upper bound. Specifically, for (0 Dy).
Pr Pr(ge()) s Ue(o, DT)) 2 21-1 - 5.
The overall idea is to get unbiased estimates of Pr(i = y|S 8) of all combinations of y and 8, construct confidence intervals on these probabilities, and then compose these intervals to form the confidence upper bound on 9e. It takes two different approaches to compute Ue when the sensitive attribute S is binary v.s. multiclass due to their different definitions of ADP (Def. and De..(..I). We will provide the approach for multi-class S in Appendix (F and focus on the binary case here.
We follow these steps. First, for each data point (X,, St) E Ds, we feed Z; ((X,, Si) to the optimal adversary Take which aims to infer S, and get output Y. We separate D, into D and Dy.s=1 such that all points in D has S = 0 and all points in Dj.s= has S = 1. Each
pair ((x²*) (6(h) (x((k) , s((t)) can then be used to create a pair of unbiased estimates of Pr(Y 1|s = s) where s E {0, 1}, denoted as (1|s) Thus, m i.id. unbiased estimates of Pr(Y = 1|s = s) can be obtained by sampling m pairs, i.e., ([[p*)(1[s))
Pr(ý = 1|5 8) for any k E [1...., m.. By linearity of expectation [70]. they form m unbiased point estimates of Pr(Y = 1|5 = 0) - Pr(Y = -15 = 1) which will be used to construct confidence intervals on Pr(Y- = 1|S = 0) - Pr(( = 1|5 1).
Second, we apply standard statistical tools such as Student's t-test 69), Hoeffding's 's inequality (2 etc., to construct 1 - -6 confidence interval (CI) [ct, cu] on Pr(Ý = 1 0) Pr(ý = 1|$ = 1) using (1) - (1)1) (p0mm(((00))) - p((m) (1) Finally, the 1 - 5 confidence upper bound of
9. = sup, sup, Pr(Y 1|$ 0) - Pr( 1|$ 1)] - can be obtained by taking max([c:), |cul)
5

---

Note that we use 6/2 to obtain each of Q and Cu to ensure that the bound on absolute value holds with probability at least 8 via the union bound.
While our framework flexible to the techniques for achieving Cls, our experiments (Sec. 6 use the Student's s t-test as it is well understood and used across the sciences for high-risk applications (e.g.. biomedical research 50 We include the procedure for constructing the confidence bounds with
Student's s t-test in Appendix G and more discussion on other variants of CIs in Appendix H
5.2.2 Evaluation of candidate solutions
Suppose the faimess test gets candidate solution de and Uc( Df) S O, it follows that there is at least confidence - that 9- (=(0e) S 0 (Inequality I Then, the fairness test concludes with least 1 8 confidence that go. is an E-fair representation model, and de passes the test. If, however, (dr D,) > 0, then the algorithm cannot conclude that Is (Φx) S 0 with high confidence. Therefore, the fairness test concludes that there is not sufficient confidence that qó. is an e-fair representation model, and de fails the test.
Finally, if &e passes the faimess test, FRG outputs de. Otherwise, it outputs NSF. When @ fails, we do not search for and test another representation model because this would result in the well- known "multiple comparisons problem." In this case, each run of the fairness test can be viewed as hypothesis test for determining whether the representation is fair with sufficient confidence.
5.2.3 Theoretical Analysis
In this section, we prove that the fairness test with access to an optimal adversary (Def. 5.1 provides FRG with the desired high confidence e-fairness guarantee, i.c., the probability that produces representation that is not e-fair for every downstream task and model is at most 6.
Theorem 5.3. Suppose faimess test finds U& (Ø, Df), a confidence upper bound of ge (0) for arbitrary o, then FRG provides 1 - confidence e-fairness guarantee. Proof. See Appendix E
5.3 Candidate Selection
Candidate selection searches for a representation model using De and proposes candidate solution Φ. for the fairesss test. Recall that the fairness test provides the desired 1 confidence s-fairness guarantee (Def. 4.2 regardless of the choice of candidate selection (Theorem 5.3). However, candidate selection is considered ineffective if most its proposed solutions fail the fairness test, which will lead to a high probability of returning NSF. In this section, we introduce an effective selection of candidates that are both likely to pass the fairness test and highly expressive.
5.3.1 Predicting Whether a Candidate Solution Will Pass the Fairness Test
Candidate selection proposes a candidate solution de that predicts will pass the fairness test. Such prediction should leverage the knowledge of the exact form of the fairness test as much possible, except using dataset De instead of D,, i.e., checking whether (de Dz) S O. There are two differences practice because the candidate selection repeatedly searches for the candidate solution.
First, for efficiency, cannot fully optimize for adversarial downstream model from scratch for every candidate searched. Thus, after initializing an adversary fadv. for each candidate searched, we take [1, 10) gradient steps hyperparameter) for optimizing Fadv. without reinitialization.
Second, repeatedly use the same dataset D. to construct high confidence upper bounds and thus, may overfit to D... resulting in an overestimation of the confidence that the candidate solution will pass the fairness test and causing more NSF. One way to mitigate this issue is inflate the confidence interval used in candidate selection. We multiply the confidence upper bound by a where a 2 is hyperparameter, i.c., Ú=(0.. D.) = aU=( Dz) (Appendix L provides a case to show why such
inflation could be critical in reducing the chance of getting NSF). We find Ü (Ø... D.). the inflated 1 - confidence upper bound on ga (Φc), following a similar procedure as Sec. 5.2.1 and use the constraint Ü (0., D.) < 0 to find a candidate solution that reasons about the faimess test to increase the likelihood of passing.
5.3.2 Optimizing for a Candidate Solution With Constrained Objective
In addition to candidate solutions that are likely to pass the fairness test, candidate selection also favors solutions that have high expressiveness, so that the representations they generate are effective for downstream tasks. We achieve this without being limited to a specific learning algorithm. We support most parameterized representation learning architectures proposed in previous work, including the

---

Predict Income
Predict Gender (Adversarial task)
1.
1.0
3.0
0.70
Probabiity of solution
0.8
AlIC
0:65
Average
0.6
0.6
Probabiltty Sue
Average 4.0
Probabiliy Axe
0.0
0:60
04
0.55
0.2
0.50
0.0
0.0
0.0
0.04
0.00
0.32
0.38
0.04
0.05
0.32
0.38
0.04
0.08
0.32
0.15
0.04
0.00
0.2
0.
0.04
0.08
0.12
0.30
supervised
LMIF?
LAFTR
ICVAE
Figure 2: The evaluation on the Adult dataset. The target label is income and the sensitive attribute is gender. We vary E (0.04, 0.08, 0.12, 0.16]. 8 is fixed at 0.1. The four plots the left are: (1) the average AUC; (2) the average Ape: (3) the fraction of trials that returns solution excluding MSF; (4) the fraction of trials that violates (Dr(T, Φ) S s on the ground truth dataset. The AUC and ADP on the adversarial task are on the right.
based methods 38 471, contrastive learning methods (26 55]. etc. In our experiments, we focus on adaptation of VAE 47 to construct the objective function that candidate selection optimizes. Specifically, we define X ~ Z, as the generative model for with input (Z, S), parameterized by 0. Let IIL denote KI. Kl-divergence, and p(Z) be standard isotropic Gaussian prior, i.c., p) (V, I). where I is the identity matrix. Overall, we define the candidate selection process as approximating solution the constrained optimization problem:
max E (Z)xxs)))) log po (X|Z,S) KIL (gol (||X, ())p(()) 6,0
s.t. Úz(ò, Dz) S
(2)
We propose using gradient-based optimization to approximate an optimal solution (0, Φ). When gradient-based optimizers are used, the inequality constraint can be incorporated into the objective using the KKT conditions. That is, we find saddle-poing of the following Lagrangian function:
[(0, d; A) == - g. (21x.9) log X (2, s)] + KKL go
KKL (Z)x, S)]lp(2)) + \ū Da):
where A 2 0 is a learnable Lagrange multiplier. Note that after each gradient step in the optimization, we need to update the adversary fndy as mentioned above before evaluating Üo(ó, D.).
This candidate selection procedure does not require any supervision. However, if downstream task with labels is given, supervised loss (e.g.. binary cross-entropy) can be applied to C(O, Φ; X) to improve the downstream predictions. We evaluate FRG both with and without supervision in Sec. 6
6 Experiments
Here, we evaluate the performance and fairness of FRG, focusing on the following research questions. RQ1: Do the empirical results align with our expectation that FRG produces s-fair representation models with high confidence? In other words, is Ape of all downstream models and tasks upper- bounded by a desired e with high probability? To address this question, we estimate the probabilities of violating the constraint ADe(T, Φ) S using results from multiple runs of the algorithm with different training sets. RQ2: Can FRG learn expressive representations that are useful for downstream predictions? We evaluate the prediction performance on datasets with 2-3 downstream tasks using the area under the ROC curve (AUC), and compare its values across methods achieving similar demographic disparity bounds. RQ3: Would FRG frequently result in NSF avoid unfairness even with sufficient data and reasonable values of e and 5 due to an ineffective candidate selection? To address this question, we evaluate the probability that FRG provides solution other than NSF.
6.1 Experiment Setup
Datasets. We use three real-world datasets each with at least two downstream tasks, including the adversarial tasks that predict the sensitive attributes: UCI Adult (6] and Income (California only, commonly known as Retiring Adult) [17] both with 2 downstream tasks, and Heritage Health [4 with 3 downstream tasks. All downstream tasks and sensitive attributes are listed per dataset in Appendix Table [] including their basic statistics (see details in Appendix []. For each dataset, we use the first downstream task for hyperparameter search and validation, and the last task adversarial task predicting the sensitive attribute.
7

---

Predict Age
Predict Gender (Adversarial task)
0.73
1.0
0.P0
08
Probabilty of souutio
02
Juerape AUC
0.65
Average
0.6
Avenag
0.6
9.
Probsbiitt
Probaaiity
0.60
0.50
22
0.2
02
0.50
0.0
0.04
0.00
0.12
0.16
0.00 0.04
0.12
0.16
2.00 0.32 0.04
0.18
0.00 0.04
0.22
0.10
0.02 0.04
0.22
0.16
0.04 0.00 0.22 0.16
supervised
LAFTR
BARE
CFAIR
Figure 3: The evaluation the Health datasct with sensitive attribute gender. The original target task predicting Here, we show the transfer learning capabilities on predicting age.
Charlson Index is in Appendix Figure 5
Baselines. We consider six competitive FRL baselines. LAFTR 48 proposes limiting the unfairness
of arbitrary downstream classifiers with adversarial training. ICVAE [54
uses upper- bound of
the mutual information between S and Y as regularizer. LMIFR
[68 uses Lagrangian Multipliers
to encourage a representation model to satisfy constraints that upper-bound the mutual information between S and Y. CFAIR [76) adopts balanced error rate (BER) and conditional learning to achieve parity. FCRL [26] proposes controlling parity via contrastive information estimators. FARE (33) provides high- Sigh-confidence certificates with representations drawn from discrete distributions with finite support for downstream unfairness. All methods except FARE estimate upper bounds of ADP on arbitrary downstream models using training data, which may not generalize to unknown test data.
For the Adult and Health datasets we train LAFTR, FCRL, CFAIR, and FARE in a supervised manner using the first downstream tasks (Appendix Table I because their model architectures rely on a supervised downstream task and avoiding it causes large performance decreases. CVIB, LMIFR are unsupervisedly trained without a labeled downstream task. For these two datasets, we train FRG with supervision (denoted as FRG__uupervin
and without supervision (denoted as FRG). For the Income dataset, all models are trained with a supervised loss because the task is difficult for all models.
Evaluation process. For each dataset, we split the data into training (Dirin). validation (Dva)), and test (Dest) sets according to ratio 0.6:0.2:0.2 For FRG, we sample 10% of the training set to be D for fairness test and let candidate selection use the remaining 90% as De. We run experiments across 4-5 different e's. We fix 5 = 0.1 for the main experiment, i.e., want the probability of violating the constraint to be at most 0.1 and provide additional study on various 0's in Appendix Figure g In one experiment, we train all methods 20 rimes with different randomly drawn training sets to get 20 representation models, which will then be applied to all downstream tasks. We report averages over the 20 trials for AUC, ADP, the probability of returning solution, and the probability of failing the constraint (DP(T, r Φ) S e. All figures plot the error bars evaluated with standard deviations.
Hyperparameter tuning. The goal of hyperparameter tuning is to find a set of parameters that achieve high downstream performance while satisfying (T) S E. Thus, we use validation sets of the first downstream tasks (Appendix Table [) for tuning. We repeat the training for each parameter set at least 3 times. The first evaluation criterion is whether the constraint ADP(T, Φ) S is satisfied. If finding a set of parameters that satisfies the constraint is impossible, we select the one that achieves the smallest App. For FRG, we also prioritize the parameters that achieve the lowest probability of returning NSF. If there are ties, we choose the parameter set that achieves the highest average AUC. We note that the architectures and hyperparameters for the downstream models are consistent across methods for fair comparison. More details are provided in Appendix
6.2 Result and Discussion
The experiment results for the three datasets are provided in Figures 2 3 and For Health, the evaluation of the targeted downstream task is provided in Appendix Figure
Overall, both FRG and gee_ssuervieed can maintain ApP S E with a sufficiently high probability (at least 0.9). In contrast, most baseline methods cannot consistently satisfy e-faimess with high probability across all datasets. For baseline methods, we observe that a smaller & causes a larger probability of failing the constraint. They also tend to fail on the adversarial tasks, in contrast to FRG (rightmost panels in Figures 3 and Thus, FRG provides high-confidence fairness guarantees across tasks for different s's (RQ1). To answer RQ2, we highlight that FRG can match or outperform
8

---

Predict Income
Predict Marital S. (Adversarial lask)
0.00
0.75
0.
0.8
Average AUC
0.70
Average Our
0.55
0.6
Probuct City of
0.6
Probabitty
0.6
Average
0.4
Proboghiity
0.0
0.4
0.4
0.4
0.4
0.
0.00
0.2
260.22 32. 12.0.400..0
0160.240 126.005.4
0:100:00.22.0000
0.160.26C
40
0.160.24
2.322.4.220.4000 0.320
PRO suparviscd
LATTR
IDVAR
cf FARE
FRRE
CTAIR
Figure 4: The evaluation on the Income dataset. The target label is income and the sensitive attribute is marital status which has 5 classes, We vary E E (0.16, 0.24, 0.32, 0.40, 0.48).
baselines in terms of prediction performance (AUC). Compared with baselines that achieve ADP S with high probability (ICVAE for Adult and Health, and FARE), FRG tends to yield higher AUC, especially when E small. Further comparisons of the tradeoff between AUC and Apr in Appendix K confirm that FRG tends to achieve the highest AUC among the methods that achieve App S & with high probability. Furthermore, FRG also keeps a high probability of returning solution (at least 0.9) over all datasets, which demonstrates the effectiveness of our candidate selection and addresses RQ3.
Comparison between FARE and FRG. Similar to FRG, FARE can also achieve high probability of satisfying the fairness constraint across all datasets. While FARE does not support user-defined s's, we use hyperparameter search (as discussed) manipulate its high probability upper-bound of App- However, these certificates are loose and often several times larger than the desired (compare the "s of FARE" with the z-axes in Figures 3 and 4. Additionally, even through this hyperparameter search, FARE does not certify fairness with enough granularity, i.e., the same certificates are given to multiple s's. Perhaps FARE's use of representations drawn from a discrete distribution with a finite support limits the representations' variability. In contrast, FRG provides the high confidence guarantees and achieves accurate downstream models even for small user-specified E's.
On the primary downstream tasks (left Figures and 5). All methods use the first tasks in Table as the target task for hyperparameter search such that the models do not violate the fairness constraints on validation sets. Even though baseline methods including LMIFR, LAFTR, FCRL and CFAIR can satisfy the constraints on the validation set, they still fail with large probability on the test set for the same task. In contrast, FRG and FARE can still keep ApP low with high probability. This suggests that their theoretical upper bounds estimated using the training dataset overfit. Even with hold-out validation set, it is still possible to underestimate the App for new test datasets. In comparison, FRG's high-confidence guarantees include statistical testing with held-out data, Dy, which automatically tests for and avoids unfair models resulting from overfitting.
On the adversarial tasks (right Figures 3 and 4). Here, we check whether the learned represen- tations can be used to adversarially infer sensitive attributes. Compared to other downstream tasks, the failure rates have increased for baseline methods (including LMIFR, LAFTR, FCRL, ICVAE, CFAIR), especially when E is small. Even though these methods provide an estimated upper bound for App in the worst case, the fairness constraints are still violated on these adversarial tasks due to the lack of high-confidence guarantees. However, FRG and FARE satisfy the constraints for unknown adversarial tasks, and FRG provides high-confidence user-defined fairness guarantees.
On transfer learning (left Figure 3). We first note that we use unsupervised learning for FRG, LMIFR and ICVAE on the Adult and Health datasets. So their performances on income prediction for Adult (left Fig. 2 and Charlson Index prediction (Appendix Fig. 5) for Health can also be used to demonstrate their transferability. Here, we focus on left Fig. where task-specific labels are not exposed during training to all methods. Several baselines (LMIFR, ICVAE and LAFTR) increase their probability of violating the constraints compared to their performance on the target task that predicts Charlson Index. This may be the effect of overfitting the fairness constraint to a specific downstream task while not generalizing to all tasks. When the task is different, the sensitive information in the same representations can be exploited. Most supervised methods yield the lowest AUC scores (FARE, LAFTR, CFAIR). This may suggest that transferring the representations to different task can hurt the prediction for supervised learning approaches.

---

Supervised v.s. unsupervised FRG. On the Adult and the Health datasets, although the supervised FRG performs slightly better than the unsupervised one, the improvement is insignificant. We hypothesize that while supervision helps, more predictive candidate can also expose more sensitive information, making it easier to violate the fairness constraints. When the candidate selection aims to control Üg( Do) I O, the better-performing candidate may not be selected. In some cases when candidate selection returns the better performing candidate, it can still fail the fairness test and be replaced by NSF if U2 (0.. Dy) > 0 (e.g., on the Adult dataset when E is small).
We further study the effect of different confidence levels E {0.01, 0.05, 0.1, 0.15) (Appendix Figure8.. The performance and the ADP are similar when e is small on both the target and adversarial tasks. On the target task, as gets large, e.g., E 0.16, the performance for the larger is marginally better than for the small 6 while the App's 8 are still similar. Overall, by increasing 6, one might gain a marginal improvement in the prediction accuracy or performance but the cost of reducing the confidence in the fairness guarantees. Finally, study varying a' in Appendix [ Other evaluation metrics including FI, Average Accuracy, Equal Opportunity Difference, Equalized Odds Difference are provided in Appendix Figures
T0 and 1T
Conclusion and Limitations
In this work, we introduced FRG, an FRL framework that provides high-confidence fairness guaran- tees, ensuring that demographic disparity for all downstream models and tasks is upper-bounded by a user-defined eиror threshold and confidence level. Our work is substantiated with theoretical analysis, and our empirical evaluation demonstrates FRG's effectiveness across various downstream tasks.
The theoretical guarantees FRG make several assumptions. First, we assume all data samples are i..dd Second, the use of Student's t-test assumes the point estimates of y are normally distributed, which requires large sample such that CLT holds. Third, we assume access to an optimal adversary (Def. 5.T that uses representations input to predict the sensitive attributes to maximize App- We approximate it with an independently trained model.
In the future, FRG can be extended provide guarantees related measures of fairness, privacy [8] safety, robustness or concept erasure (7]. While FRG can account for label shift and concept drift because our guaranteed constraint on demographic disparity does not require any assumptions about the distribution of the downstream labels, future work could study guarantees under distributional shifts in features X and/or sensitive attributes S. Future work could also consider other approaches without assuming access to optimal adversary (Appendix M
Acknowledgments
This work is supported by the National Science Foundation under grant no. CCF-2018372, by gift from the Berkeley Existential Risk Initiative, and by Rutgers SAS Research Grant in Academic Themes. Philip S. Thomas and Przemyslaw A. Grabowicz took similar advising roles on this project. The authors would also like to thank Linjum Zhang at Rutgers for the time to review and discuss this work.
10

---

References
[1] Martin Abadi, Andy Chu, lan Goodfellow, H. Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, page 308-318 2016. doi: (0.1145/2976749.297833
[2] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna M. Wallach. A reductions approach fair classification. In ICML, 2018.
[3] T. W. Anderson. Confidence limits for the value of an arbitrary bounded random variable with a continuous distribution function. Bulletin of The International and Statistical Institute, 43: 249-251, 1969.
[4] Julia Angwin, Jeff Larson. Surya Mattu, and Lauren Kirchner. Machine bias. ProPublica, May 2016. URL htttps://ww.pprogt machine- sise-bias-aaee clas-risk-asee aissk-assesmments-- in- www.--riiinaa-ssttteniiiiii
org/article/
[5] Mislav Balunović, Anian Ruoss, and Martin Vechev. Fair normalizing flows. In ICIR, 2022.
[6] Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. DOI: https//ddb.orr/1022443////3
[7] Nora Belrose, David Schneider-Joseph, Shauli Ravfogel, Ryan Cotterell, Edward Raff, and Stella Biderman. Leace: Perfect linear concept crasure in closed form. In NeurIPS, 2023.
[8] Sarah Bird, Miro Dudik, Richard Edgar, Brandon Hor,, Roman Lutz, Vanessa Mi- lan, Mehrnoosh Sameki, Hanna Wallach, and Kathleen Walker. Fairlearn: A toolkit for assessing and improving fairness in ai. Technical Report MSR-TRR-2000-32, Mi- crosoft, 2020. URL https: //wp:::///wwww./ mi crosoft. htt.:a/t....aoaaeeee//////eeaata
fairlearn- a- too assessing- -nd-eiinn------------- imp.oving--aairress--iiii----- htt.://aaa.a.ai..ooooooooooooaaa in-ai//
[9] Nanette Bymes. Artificial intolerance. MIT Technology Review, March 2016. URL https
[10] Flavio Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney. Optimized pre-processing for discrimination prevention. Guyon, U, Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30, 2017.
[11] Flavio du Pin Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R. Varshney. Data pre-processing for discrimination prevention: Information -theoortti optimization and analysis. IEEE Journal of Selected Topics in Signal Processing. 12(5):1 106- 1119, 2018. doi: 10. 10.1109/SSTSP221888886633
[12] Mattia Cerrato. Alexander Köppel, Marius Segner, and Stefan Kramer. Fair group-shared representations with normalizing flows. In ICLR, 2021.
[13] Xi Chen, Ali Zeynali, Chico Camargo, Fabian Flöck, Devin Gaffney, Przemyslaw Grabowicz, Scott Hale, David Jurgens, and Maltia Samory. Semeval-2022 task 8: Multilingual news article similarity. In Proceedings of the 16th International Workshop on Semantic Evaluation (SemEval-2022), pages 1094-100, 2022.
[14] Elliot Creager, David Madras, Bvern-Henrik Jacobsen, Marissa Weis, Kevin Swersky, Toniann Pitassi, and Richard Zemel. Flexibly fair representation learning by disentanglement. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 1436-1445. PMLR, 2019.
[15] Namrata Deka and Danica J. Sutherland. Mmd-b-fair: Learning fair representations with statistical testing. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, 2023.
[16] Jacob Devlin, Ming-Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 181111100000 10.044855 2019.

---

[17] Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. In NeurIPS, 2021.
[18] Cynthia Dwork. Differential privacy. Automata, Languages and Programming, pages 1-12. Springer Berlin Heidelberg.
[19] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. Proceedings of the 3rd Innovations Theoretical Computer Science Conference, ITCS 12, page 214-226, 2012. ISBN 9781450311151.
[20] Harrison Edwards and Amos Storkey. Censoring representations with an adversary. In Interna- tional Conference Learning Representations, 2016.
[21] Yanai Elazar and Yoav Goldberg, Adversarial removal of demographic attributes from text data. In EMNLP, 2018.
[22] Rui Feng, Yang Yang, Yuehan Lyu, Chenhao Tan, Yizhou Sun, and Chunping Wang. Learning fair representations via an adversarial framework. In CoRR, 2019.
[23] Xavier Gitiaux and Huzefa Rangwala. Learning smooth and fair representations. In AISTATS. 2021.
[24] Paula Gordaliza, Eustasio Del Barrio, Gamboa Fabrice, and fairness using optimal transport theory. Kamalika Chaudhuri and Ruslan Salakhutdinov. editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2357-2365 PMLR, 2019.
Loubes. Obtaining
[25] Vincent Grari, Oualid El Hajouji, Sylvain Lamprier, and Marein Detyniecki. Learning unbiased representations via rényi minimization. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, page 749-764, 2021.
[26] Umang Gupta, Aaron M Ferber, Bistra Dilkina, and Greg Ver Steeg. Controllable guarantees for fair outcomes via contrastive information estimation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, page 7610-7619, 2021.
[27] Moritz Hardt, Eric Price, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems, volume 29, 2016.
(28) Austin Hoag, James E. Kostas, Bruno Castro da Silva, Philip S. Thomas, and Yuriy Brun. Seldonian toolkit: Building software with safe and fair machine learning. 2023 IEEF/ACM 45th International Conference on Softwre Engineering: Companion Proceedings (ICSE- Companion), pages 107-111, 2023, doi: LLL.9IISSE-Coomanioonne
2023.00035
[29] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, (1:301):13-300 1963. doi: 10.2307/2282952.
[30] Max Hort, Zhenpeng Chen, J Zhang, Federica Sarro, and Mark Harman. Bias mitigation for machine learning classifiers: A comprehensive survey. ArXiv, abs/2207.070 070668, 2022.
[31] Ayush Jaiswal, Daniel Moyer, Greg Ver Steeg, and Premkumar AbdAlmageed, Wael andNatara- jan. Invariant representations through adversarial forgetting. In AAAI Conference on Artificial Intelligence, 2020.
[32] Taeuk Jang, Hongchang Gao, Pengyi Shi, and Xiaoqian Wang. Achieving fairness through separability: A unified framework for fair representation learning. In Proceedings The 27th International Conference on Artificial Intelligence and Statistics, 2024.
[33] Nikola Jovanović, Mislav Balunović, Dimitar I. Dimitrov, and Martin Vechev. Fare: Provably fair representation learning with practical certificates. In ICML, 2023.
[34] Kaggle. Health heritage prize, 2012. URL https: :/hb::://wwwww.. kaggle com/ c/hhp
[35] Peter Kairouz, Jiachun Liao, Chong Huang, Maunil Vyas, Monica Welfert, and Lalitha Sankar. Generating fair universal representations using adversarial models. IEEE Transactions on Information Forensics and Security, volume 17, pages 1970-1985, 2022.
12

---

[36] Dongha Kim, Kunwoong Kim, Insung Kong, Ilsang Ohn, and Yongdai Kim. Learning fair representation with a parametric integral probability metric. In ICML, 2022.
[37] Yin-Young Kim and Sung-Bae Cho. Fair representation for safe artificial intelligence via adversarial learning of unbiased information bottleneck. In SafeAl@ AAAI, page 105-112, 2020.
[38] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint 1111v:1312.6114, 2013.
[39] Matthaus Kleindessner, Michele Donini, Chris Russell, and Muhammad Bilal Zafar. Efficient fair pea for fair representation learning. In Pruceedings of The 26th International Conference on Arlificial Intelligence and Statistics, 2023.
[40] Preethi Lahoti, Krishna Gummadi, and Gerhard Weikum. Operationalizing individual fairness with pairwise fair representations. In Proceedings of the VLDB Endowment, volume 13, pages 506 518, 2019. doi: 10. 00.14778/3372716.33777
[41] Preethi Lahoti, Krishna P. Gummadi, and Gerhard Weikum. ifair: Learning individually fair data representations for algorithmic decision making. In International conference on data engineering (icde)., page 1334-1345, 2019.
[42] Junghyun Lee, Gwangsu Kim, Matt Olfat, Mark Hasegawa-Johnson, and Chang D. Yoo. Fast and efficient aamd-based fair pea via optimization over stiefel manifold. In AAAI, 2022.
[43] Puheng Li, James Zou, and Linjun Zhang. Fairee: Fair classification with finite nample and distribution-fred guarantee. In CoRR, 2022.
[44] Ji Liu, Zenan Li, Yuan Yao, Feng Xu, Xiaoxing Ma, Miao Xu, and Hanghang Tong. Fair representation learning: An alternative mutual information. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '22, page 1088-1097, 2022.
[45] Shaofan Liu, Shiliang Sun, and Jing Zhao. Fair transfer learning with factor variational auto- encoder. In Neural Processing Letters, page 1-13, 2022.
[46] Francesco Locatello, Gabriele Abbati, Tom Rainforth, Stefan Bauer, Bernhard Schölkopf, and Olivier Bachem. On the fairness of disentangled representations. In NeurIPS, 2019.
[47] Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard Zemel. The variational fair autoencoder. In 4th International Conference on Learning Representations (ICLR), 2016.
[48] David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3393-3393. PMLR, 2018
[49] A. Maurer and M. Pontil. Empirical bernstein bounds and sample variance penalization. In In Proceedings of the Twenty-Second Annual Conference on Learning Theory, pages 115-124, 2009.
[50] John H McDonald. Handbook of biological statistics, volume 2. sparky house publishing Baltimore, MD, 2009.
[51] Daniel McNamara, Cheng Soon Ong, and Robert Williamson. Provably fair representations. arXiv preprint 1xXiv:110.003944 2017.
[52] Ninarch Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM Computing Surveys, 54:1-35, 2021.
[53] Claire Cain Miller. Can an algorithm hire better than human? The New htteees.coo/221500/2220 upssot//
York Times, June 2015. URL. pistps://wntt can Ban-an-aa awgorithn sereeebeteerreee than- a human, html
13

---

[54] Daniel Moyer, Shuyang Gao, Rob Brekelmans, Aram Galstyan, and Greg Ver Steeg. Invariant representations without adversarial training. In Advances in Neural Information Processing Systems, volume 31, 2018.
[55] Changdae Oh, Heeji Won, Junhyuk So, Taero Kim, Yewon Kim, Hosik Choi, and Kyungwoo Song. Learning fair representation via distributional contrastive disentanglement. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, page 1295-1305, 2022.
[56] Luca Oneto, Michele Donini, Giulia Luise, Carlo Ciliberto, Andreas Maurer, and Massimiliano Pontil. Exploiting mmd and sinkhorn divergences for fair and transferable representation learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 15360-15370, 2020.
[57] Luca Oneto, Michele Donini, Massimiliano Pontil, and Andreas Maurer. Learning fair and trans- ferable representations with theoretical guarantees. In 2020 JEEE 7th International Conference on Data Science and Advanced Analytics (DSAA), pages 30 30-39, 2020.
[58] OpenAL. Gpt-4 technical report. arXiv preprint arXiv:2303.087741 2023.
[59] Momchil Peychev, Anian Ruoss, Mislav Balunović, Maximilian Baader, and Martin Vechev Latent space smoothing for individually fair representations. In ECCV, 2022. doi: 10.1007/ 978- 11883-031--1778-922 31.
[60] Tao Qi, Fangzhao Wu, Chuhan Wu, Lingjuan Lyu, Tong Xu, Zhongliang Yang. Yongfeng Huang, and Xing Xie. Fairvfl: A fair vertical federated learning framework with contrastive adversarial learning. arXiv preprint arXiv:2206.0322 2022.
[61] Novi Quadrianto and Oliver Sharmanska, Viktoriia Thomas. Discovering fair representations in the data domain. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
[62] Miriam Rateike, Ayan Majumdar, Olga Mineeva, Krishna P. Gummadi, and Isabel Valera. Don't throw it away! the utility of unlabeled data in fair decision making. In 2022 ACM Conference on Fairness, Accountability, and Transparency, page 1421-1433, 2022.
[63] Proteek Chandan Roy and Vishnu Naresh Boddeti. Mitigating information leakage in image representations: A maximum entropy approach. CVPR, 2019.
[64] Anian Ruoss, Mislav Balunovic, Marc Fischer, and Martin Vechev. Learning certified individu- ally fair representations. Advances Neural Information Processing Systems, volume 33, pages 7584-7596, 2020.
[65] Mhd Hasan Sarhan, Abouzar Navab, Nassir Eslami, and Shadi Albarqouni. Fairness by learning orthogonal disentangled representations, In ECCV, 2020.
[66] Xudong Shen, Yongkang Wong, and Mohan Kankanhalli. Fair representation: Guaranteeing approximate multiple group fairness for unknown tasks. In CoRR. abs/2109.00545 2021.
[67] Changjian Shui, Qi Chen, Jiaqi Li, Boyu Wang, and Christian Gagné. Fair representation learning through implicit path alignment. In International Conference on Machine Learning. volume 162, 2022.
[68] Jiaming Song, Pratyusha Kalluri, Aditya Grover, Shengjia Zhao, and Stefano Ermon. Learn- ing controllable fair representations. International Conference on Artificial Intelligence and Statistics (AISTATS), 99:2164-2173) 2019.
[69] Student. The probable error of mean. Biometrika, 6.1:1-25, 1908. doi: 10.2307/2331554.
[70] Philip S. Thomas, Bruno Castro da Silva, Andrew G. Barto, Stephen Giguere, Yuriy Brun, and Emma Brunskill. Preventing undesirable behavior of intelligent machines. Science, 366(6468): 999-1004, November 2019. doi: 10. (0.11266sciemec.aag331
14

---

[71] Chuhan Wu, Fangzhao Wu, Tao Qi, and Yongfeng Huang. Semi-fairvae. Semi-supervised fair representation learning with adversarial variational autoencoder. arXiv preprint arXiv:2204.00536, 2022.
[72] Qizhe Xie, Zihang Dai, Yulun Du, Eduard Hovy, and Graham Neubig. Controllable invariance through adversarial feature learning. In Advances in Neural Information Processing Systems, 2017.
[73] Yilun Xu, Shengjia Zhao, Jiaming Song, Russell Stewart, and Stefano Ermon. A theory of usable information under computational constraints. In ICLR, 2021.
[74] Meike Zehlike, Philipp Hacker, and Emil Wiedemann. Matching code and law: Achieving algo- rithmic fairness with optimal transport. Data Mining and Knowledge Discovery, Forthcoming. 2019.
[75] Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representa- tions. In ICMI., 2013.
[76] Han Zhao, Amanda Coston, Tameem Adel, and Geoffrey J. Gordon. Conditional learning of fair representations. In International Conference Learning Representations, 2020.
[77] Wei Zhu, Haitian Zheng, Haofu Liao, Weijian Li, and Jiebo Luo. Learning bias-invariant repre- sentation by crops-sample mutual information minimization. In Proceedings of the TEEF/CVF International Conference Computer Vision, page 15002-15012, 2021.
15

---

A AP for Multi-class Sensitive Attributes
Definition A.1 (Ape for multiclass S). We define App for multi-class sensitive attributes S E S
where [ > 2 as follows.
DP 6) max Pr(Y 1|8 = Pr(Y 1|s - 5)
(4)
It follows from the implementation by Bird et al. 8
B Proof of Theorem 5.2
To prove (D)(F, [Covis.8) we first prove the following lemma. To simplify the notations in Var(S)
the proofs, we define Pa,h = Pr(y a, S = b] where a, {0, 1}. Lemma B.1. Suppose S,Y {0, 1} are Bernoulli random variables.
Cov(Y, 5) = Pr(y
Pr = 0,5 0] - Pr(y = 0 0,5 =
(5)
P1,120.0 P1.0Po,1.
(6)
Proof.
Cov(Y, = -
(by definition of covariance)
(7)
= -Eu Pg.s (j () 8) - Pr[y = - Pr 1]
(8)
1/.5
P1,1 Priý Pr(S 1]
P1,1 (P1,1 (11.) + Po.1)
(10)
= P1,1 P1,1PO,1 PI.IPI.0 PI,1PI,1 - 11.0
(11)
(1 Pa.1 PL.D PI.1) P1.0Po.1
(12)
P1,1Po,0 P1,0Po.1
(13)
Completing the proof.
Theorem B.2 (Theorem
5.2 restated), Suppose S, 8 {0,1) are Bernoulli random variables. Then
[Cov(Y.S))
ADP(T,
Var(S)
Proof.
ADP(T, Φ)
= Pr(Ý = =| = -Pr(P = 1 = 0)
(By Def. 3.1
(14)
P1,1
P1.0
(15)
Pr(S = 1) Pr(S = 0)
PII Pr(S = 0) - P1.0 Pr(S=
(16)
Pr(S 1) Pr(S = 0)
1
P1,1Po.0 P1.1P1.0 P1.0Po.1 11.01.11
(17)
Var(S)
1
P1,1P0.0 P1.0P0.1
(18)
Var(S)
[Cov(Ý, S)
(By Lemma B.1
(19)
Var(S)
Completing the proof.
16

---

C Extension to Equal Opportunity and Equalized Odds
In this section, we demonstrate that FRG can be extended to other group fairness metrics beyond demographic disparity (App), specifically, Equal Opportunity Difference (AROp) and Equalized Odds Difference (ABOD), with the assumption that the downstream task's labels are available. We start with their formal definitions.
Definition C.1 (Equal Opportunity Difference).
=) (TO Φ) == -,,
1/5 - 0,Y =1)
(20)
(T = 1).
(21)
Definition C.2 (Equalized Odds Difference).
(Pr( = 1155= -Pr(P = 1| 0, 0, w
ABOD(T, (T) = max
(22)
vE{0,1}
= max ADr(T,olY = =), ADI(T, o/ = =0)
(23)
Here ADP(T. = y) for y E {0.1} represents the ADP under the conditional distribution S|Y y). Empirically, it is the ADP evaluated on the data samples whose downstream la- bels satisfy Y = y.
Thus, following the same procedure introduced in Sec. Jn the data samples whose Y = 1, FRG can produce representation models that satisfy AEOD(T, Φ) ADP(T, o|Y = 1) S with probability at least (1 6).
By splitting ō in half, FRG (Sec. 5 can generate a representation model that satisfies ADe(T, ofY = 1) S E and (T Y 0) S E, each with probability least (1 (1-6) 6/2)). By union bound, such a
representation model satisfies AEOD 6) max (DP(T, obY 1), ADr(T, o|Y =0) S with
probability at least (1 -). 5).
D
The relationship between ApP and [Cov(Ý, for non-binary sensitive attributes
The standard definition of covariance is not applicable to non-binary categorical random variables like the sensitive attributes. The reason that the covariance takes the numerical values of random variable into account but the numerical values of the sensitive attribute has actual meaning. However, we can define auxiliary random variables for S for each pair of sensitive categories i.j E S, to represent S as set of binary indicator variables, such that covariance approach enables the application of FRG to the setting of non- binary sensitive attributes S.
be applied. This
Suppose E S where [S] > 2. Create one indicator variable Si for each pair of j E where if S and S if S =
i o such that 5 E {0, 1} and b S. We will first prove the lemma below before stating the main theorem.
j. We denote Po,6 Pr[f a, S = where
Lemma D.1. Cov(Ý, Styls (i.j))
PP (P=3)))-(((3)))"
Proof. Following the same proof as Lemma B.1 in Appendix B, have
SonY,St,la (i.j})
(24)
=Pr[f = 1, = 1S (r.]] = 0. = o (i.HH
(25)
0|5 1,5%
0, = 1|S E (i.))
(26)
=Pr(ý- 1,5 j (, ((.j)
(27)
- -Pr(ý = 1,5 -
-0,5 = =]sS e {i,1].
(28)
Since Pr[S E (i,)) = Pr(S - Pr(S = j). Lov(Y,Style E (i.s)) = -
(Pr(S=))+P((S-))
17

---

Demographic disparity can be defined separately for each pair of sensitive categories, i,j E S, as ApP Pr(Y = 1|s = i) - Pr(Y = 1|5 = = Then, we can limit ADP = max,,j AP, to
ensure demographic parity with respect any pair of sensitive categories relationship between ADp and Cov(Y, ( {i,5))-
[.. Next, we provide the
Theorem D.2.
Pr(S = i) Pr(S =) + Pr(S P
5) Pr(S = 1) |oov( Sty1iE (6.1
(DP(T, 6) max 2
where i,j E S and i o
Proof.
ADP(T, 0) max
= 5) Pr(Y = 1|8 = i) Pr(y = =|5
(29)
Pr(f' = 1,5 i) Pr(ř =1,5=1
maax %
(30)
Pr(S=1)
Pr(S=
Pr(f = 1,S Pr(S = 1) Pr(f = j)
max
(31)
Pr(S 1) Pr(S =
-mxx 1.j
Pl.Po.s + PI.PP.. P1.jPo, P1,P1.
(32)
Pr(S = i) Pr =
-max
Pr(S i) Pr(S j) PI.PPo.. PL.jPo.i
(33)
= (Pr(S = i) + pr(S= 5)) P1.PP.J Pl.5Po.s
-max +
(34)
Pr(S = i) Pr(S =) (Pr(S = Pr(S j))²
max (2+ Pr(S 5) + Pr(SS -r((s=]) Cov(YP, )
Pr(S =)
E (i,j
(35)
This completes the proof. Using this relationship, the optimal adversary can be approximated for non-binary sensitive features.
For instance, suppose that Pr(S = 1) = [S| for all i. Then, App is minimized when the predicted label Ý does not provide any information differentiating any pair of i and j E S. On the other hand, App is maximized if there exists a pair of and j such that Y is maximally correlated with S conditioning on S (i.j).
E
Proof of Theorem
5.3
Theorem E.1 (Theorem 5.3 restated). Suppose fairness test finds ÚØ Df), 1 confidence upper bound of ge()) for arbitrary 6. then FRG provides 1 - ô confidence e-fairness guarantee.
Proof. By Def. 4.2 if FRG satisfies Pr (g-()()) - 0) 2 1 5, then FRG provides the desired 1 confidence c fairness guarantee. We prove by contradiction that Pr (g=(((D) S 0) > 1
if a corresponds to FRG and a ((D) corresponds to the representation model parameters returned by FRG when run on dataset D.
We begin by assuming the result is false and then derive a contradiction. The beginning assumption
5- 5. By contrapositive, we have Pr (g)(a( > 0) 2 8. By the construction of FRG, (D) either NSF or the proposed candidate solution de E $. Notice that ge (a(aD)) > 0 if and only if a(D) does not return NSF but returns d instead, i.e., a(D) = é.. The fairness test in FRG returns o, if and only if ('.. D,) S 0 (Sec. (.2).. Therefore, the following events are equivalent (Pr(A, B) denotes the joint probability of A and B):
is that Pr (ge (a ()) I 0) < 1-44
(gs (a(D)) 0)
(36)
+ (a:()(D) > 0,a(DD = oc, (pe Df) < ()
(37)
+ (g.())) Ue(W.,
d.).
(38)
The joint event (g. Ue( Dy), a(D) = 6c) implies (g= (6e) > Ue Ue(oc, Dy)). Therefore,
Pr (0.) > Ue(do, Dj)) Pr (0.) Us( Dy) aLD) o.) 2 8.
18

---

However, by construction of the fairness test and assuming the evaluated high confidence upper
bound Ug Dj) ) is correct, Pr (g=(0.) Ue D,)) 2 1 (Inequality TT. which implies Pr (g=(0e) > (6 Dạ)) < 5. This gives a contradiction, completing the proof.
We note that this theorem true for any choice of candidate selection, as the proof assumes the candidate solution de is arbitrary.
F Computing UE(Ø, Dj) for Multi-class Sensitive Attributes
Suppose 5 EE where |S| > 2. To evaluate an estimate of Ü, Dy), we need to find the worst-case APP
We first feed Z; = ((2, S:) for each data point in D to ady- Since the adversarial predictor predicts the sensitive attribute, both the sensitive attribute and the label are multi-class. Thus, we obtain predicted probability distribution of Y; such that Eees Pr(Y, = s Z.) = 1 (we apply softmax to the output of the multi-layer perceptron to get these probabilities). By splitting Dj into |S] groups where according to their sensitive attributes, we can get unbiased estimate (denoted as f (slj) of Pr(Y = j) with sample (x j. Y, =).
Following a similar procedure in Sec. 5.2.1 we draw m unbiased estimates of Pr(Y s =) for each j E S. Then we apply statistical tools (Student's t-test, for example) to construct a 8/|5|2 confidence interval (CT) [ca(s,j), cx j)] on Pr(ý a|S j) with 6/(2())² on both sides.
Finally, we set (6, Dy) = max, (max, (cu(s, ming (c((s,))) -E
We prove the correctness below.
Theorem F.1. Suppose Pr(Ý = s|S = has 1- 8/1512 confidence interval (cr(s, cu(s) with the confidence equally split on both sides for each s, E |S), and suppose Y is the optimal adversarial prediction that causes the maximum App, then
Pr(ge(d) $ - maxx(max(cu(ss))) min(c((s, k)) =] 1-
Proof. Suppose Pr(ř s|S j) has 1 8/|5|2 confidence interval (c, cu(s, [), with the confidence equally split on both sides, then Pr[Pr(Y = s|S = j) S a(s, s 8/(2[S)²) and Pr[Pr((' = s|$ = j) 2 (s) & (2) for each s,j E |S].
By the union bound, we have Pr(ming Pr(r 8SS = k) < min: ca(s, k)] < 8/(())) and Pr|maxy Pr(Ý = s = j) 2 max, cu (s. s 8/(2 for each S.
By the union bound, we have Pr(max, Pr(ý s 1) ming Pr(ý s|S k) z maxy (s min, (s, k)] < 8 for each E S.
By the union bound again, we have
Pr|max(max Pr(f = s|S = j) min = s|S5 k)) 2 max(max eu (s. max(maxc_(s.))) min (s k)) s
Assuming the adversary is optimal, we have
Ge (x) = sup ADP(T, Φ) -
(39)
max Pr(r = 1 j) - Pr(r = 1|$ = k) -
(40)
J.KES
max Pr = 1|S j) - min Pr (Ý 1|5 = k) -
(41)
jES
kES
< max Pr(ý s|S
min PrrP s|S k)) E,
(42)
SES
JES
kES
where the predicted class s, the sensitive attribute classes j and result in the worst-case differences over this group of samples.
19

---

Dataset
Seusitive group)
Downstream tasks
Size
PriSt
Adult
Gender (2)
Incoree. Gennder
41K
0,332, 0.668
Health
Gender (2) CI. Age. Gender
55K
0,553, 0.447
Income
Incomne
195K
0.02. 0.09,
Table 1: Summary of dataset statistics. For each dataset, the first task is used for hyperparameter search and validation, and the last task is an adversarial task that predicts the sensitive attribute. The bold in the last column indicates the fraction of positive labels for the adversarial tasks. C.I. stands for Charlson Index.
Then
Pr(ge(d) 2 (oo((axxcu(ss)) - min ci k)) =E]
(43)
Pr(max(mmg Pr(y = a|S = min Pr(y = = = k)) - JES max(maxxcuss.5) min (s, =
(44)
kES
2 a ,
(45)
8..
(46)
Thus, Pr(ge(o) S
miin(((ss))) s| 2 1- [
G Using Student's T-test to Construct Confidence Intervals
We construct the 1 confidence intervals of random variable p using Student's t-test provided
m samples á with the following steps: (1) Compute the sample mean P m Σk= ((8) where
k E [1...., m]: (2) Compute the sample standard deviation ā = m Σx= (p(A) p) (3)
Compute - 5 confidence lower bound ej and - 8/2 confidence upper bound C2 on Pe (Ø) using â
Student's t-test. That c = p ym 11 and c. = p + v 1-/2 where m/2./2m
the 100(1 5/2) percentile of the Student's 's t-distribution with m 1 degrees of freedom. Student's t-test assumes the data to normally distributed, and thus m needs to be sufficiently large for the guarantees to hold (following the central limit theorem (CLT)).
H Different Techniques for Obtaining Confidence Bounds
The statistical confidence interval method in our framework modular such that researchers can substitute alternatives depending on their -emain-specific needs.
We note that prior work, including the faimess experiments in Thomas et al. 770] employed the Student's t-test for similar guarantees and demonstrated that the t-test yielded sufficiently conservative failure rates in practice. In our work, we observed similar behavior across datasets. Other than the student's t-test, we have explored Hoeffding's s inequality (29] but found its bounds to be overly conservative for our datasets, limiting its practical utility.
Different statistical tools for obtaining confidence bounds can have different tradeoffs. For instance: one could consider bounds based on the Dyvoetzky-Kieee Kiefer-Wolfowe (DKW) inequality 3 which are less sensitive to distributional tails or empirical Bernstein bounds [49] which leverage sample variance. One could also explore bootstrap-based intervals, which empirically approximate sampling distributions.
We think that rigorous comparison of confidence interval methods (e.g.. parametric vs. non- parametric, bootstrap, etc.) is beyond the scope of this paper and merits its own study. Future work could systematically evaluate these alternatives to identify optimal bounds for specific applications.
I Datasets
The dataset statistics are listed in Table | The first dataset is the UCI Adult dataset o which contains information of over 40,000 adults from the 1994 US Census. The sensitive attribute we consider is gender, and the targeted downstream task is to predict whether an individual earns more than $50K/year.
The second dataset Heritage Health The targeted downstream task is to predict Charlson Comorbidity Index, and we consider gender as a sensitive attribute. We include an additional
https://www http://wwwwkkglll.cooo/cooooo/
20

---

Predict Charlson Index
20
1.2
1180
Probabiltt 3f solution
AUCC
04
Probobblleyy
02
0.3
046
FRG
suprrvsed
IMIFR
ICVAF
cot FARE
PARE
CAAIR
Figure 5: The evaluation the Health dataset. The target label is Charlson Index. We vary (0.04, 0.08, 0.12, 0.16). 8 is fixed 0.1.
downstream task that predicts age. Ages above 50 have positive labels, and ages below 50 have negative labels.
The third dataset we use ACSIncome 17 includes data collected by the US Census across all states. We use the California dataset collected 2018. The sensitive attribute is marital status, which has five classes: married, widowed, divorced, separated, and never married. The targeted downstream task is to predict whether an individual has income above $50,000.
J Hy Hyperparameter Tuning
In our hyperparameter tuning process, we adjust various parameters, including the step sizes (for the primary objective, the Lagrange multipliers, and the adversarial predictor), the initial Lagrange multipliers, the weight of the regularizers, the number of epochs, etc. The primary objective of hyperparameter tuning is not only to find set of hyperparameters for the algorithm that minimizes App. Instead, our goal is to find hyperparameters that allow the algorithm to consistently provide representation model that is e-fair with as high expressiveness as possible. Thus, one should not tune hyperparameters separately for each of the training datasets we created. When we reuse the same training or validation set for hyperparameter search, we end up evaluating App multiple times on the same training or validation set. As a result, ADP evaluated on the model trained with the chosen hyperparameters may provide biased estimation of ADP on unseen future data. Consequently, the estimation of the probability ADP S E will also be biased. Therefore, we create additional datasets for hyperparameter tuning and adopt the same hyperparamters on different training datasets of the same size.
For baselines, create validation sets by sampling 20% of the training data, while for FRG, evaluate the models using the fairness test datasets (i.e., D, in Sec. Sec.5.2). We tune each algorithm with grid search according the metrics evaluated on the validation sets (for baselines) or the fairness test sets (for FRG). For the Health dataset, as there are multiple downstream tasks, we only assume the Charlson Index labels are available for hyperparameter tuning.
For FRG and SRG_superv,,,d, set the hyperparameter a study of various a's in Appendix [
in the main experiment. We provide
Note that we set the minimum allowed step size for the primary objective to 10-6 and the minimum number of epochs 100. This choice is motivated by the fact that an algorithm with an excessively small step size may have minimal impact on optimizing the primary objective and could potentially produce random representations that lack utility for downstream predictions, despite being highly likely to be fair.
We also note that use the same number of dimensions for representation Z (Z = 50 for Adult and Health and Z = 100 for Income) and the same hidden size for the downstream MLP for fair comparison. We use cross-entropy loss for all downstream models and Adam optimizer for all optimizations.
The detailed choices of hyperparameters for each of the datasets, the unfairness thresholds e's, and the baselines are provided with config files the source code.
21

---

K The Tradeoff Between the Prediction Performance and Fairness
Health Predict
Health Predict Age
FRG supervised
FRG supervieed
FRG
0.10
LAFTR
LATTR
0.06
PCRU
ICWAE
0.08
ICWE
PCR
CHAIR
CFAIR
0.06
8 0.04
0.04
0.02
0.02
0.00
0.00
0.50
0.55
0.60
0.65
0.70
0.75
0.90
0.50
0.55
0.60
0.65
0.70
0.75
AUC
AUC
Adult Dataset Predict Income
Income Dataset Precict Incame
supervised
supervised
Q
FRG
LKIFR
0.20
LHIFR
0.4
LAFTR
LAFTR
FCRL
FCRL
FARE
0.15
FARE
ITO
CFAIR
CFAI
0.2
0
0.05
0.00
0.0
AUC
Figure 6: The tradeoff between AUC and App the Adult (bottom left), the Health (top left and top right) and the Income dataset (bottom right). FRG and FRG supervised achieve the best tradeoff in Adult and are comparable to the best baselines in other datasets. Notice that even though some basclines achieve better tradcoff' (e.g., FCRL, LMIFR, CFAIR in Health and CFAIR in income). they have high probabilities of violating the fairness constraints, especially the adversarial downstream tasks (right Figures and
In Figure 6 the tradcoff between AUC and ADP for each dataset is plotted. FRG and FRG RRe_supereieed achieve the best tradeoff in Adult and are comparable to the best baselines in other datasets. These results confirm that FRG and FRG supervised are competitive in prediction performance while maintaining low App. Other than FRG and FRG DRGG_sppervised the baselines that achieve optimal tradeoff for one downstream task could achieve worse App in the adversarial tasks. For example, FCRL, CFAIR and LAFTR in the Health dataset and CFAIR in the Income dataset achieve the best tradeoff in targeted downstream tasks, but violate the fairness constraints consistently in the adversarial task (right Figures 3 and 4. There are only 1-3 points for FARE because their use of discrete distribution with finite support lowers the variability of the representations, which is an issue discussed in Comparison between FARE and FRG Section 6.2
L Evaluating the impact of a
We highlight again that the choice of the confidence inflation hyperparameter a does not affect the validity of the high-confidence faimess guarantees. Here we evaluate different choices of a a's in Figure / with = 0.1. There are only minor differences in the performance and no impact on acceptance rates. Therefore, in this case, may conclude that overfitting has not occurred. In our main experiment, we keep a = 2 for all evaluations.
However, we think it is important to point out potential overfitting if we do not inflate the confidence upper bound in candidate selection, especially when the constraint is restrictive. For example, when we set e = 0.035 and 5 0.01, with results in Table when a closer 1.0, leads to a higher probability of returning NSF. This is the case when the candidate solution overfits
22

---

Solution found
Avg. AUC
Avg. Anp
1.0
1.25
1.5
0.0
1.75
0.9
0.59
0.02
2.0
1.0
0.59
0.02
2.25
0.50
2.75
0.50
3.0
1.0
0.50
0.0
Table 2: On the Adult dataset with
0.035 and 0.01.
Predict Income
Predict Gender (Adversarial task)
D645
0640
0.0
08:
DINESE
05502
0,0000
0820
06-
OUETE
Prozbbrry
0.4
0.00
0420
60
654 65e Max
856 DLS ALM
ULS
0,0000
MO. 2.0.80 MUP
M. 3.0 uneap
MO UnMuD
2G.25, MD
MO 10.15.M0 MDC
mc. m. Jrsi
MG. 10
ARC 100
Figure 7: The study of the hyperparameter a on Adult dataset with 6 0.1. vary 0.01, 0.1, 0.15. FRG_o_sup and FRG_a_unsup denotes FRG trained respectively.
without supervision
the training data and overestimating the confidence that it can pass the fairness test. When is larger is more likely to return solution. However, the performance can be affected because the candidate solution will be more conservative and may give higher confidence than required to satisfy the fairness constraint.
23

---

Predict Income
0640
0.09
4.0
0435
0.08
Probabilltty solution
807
Avdragt AUG
Aver Gre
0.00
0.20
94
04
0833
0.02
0.01
0.00
004
0.00
0.03
0.10
Predict Gender (Adversarial task)
0.300
DC020
144
1.0
0.292
0.8
Fuerage AVC
Avorage Aur
0.492
Probabiliy
Probabiltoy
0.404
04
0.4992
00005
2
5,000
0.04 040
0
0
1L04
1:00
D.22 D.06
DC0 DCB
0.22 0.28
0.04 0.08 0.12 0.36
LAMD
MC ursup
100_0.00_3.p
1NG, 0.00 Mrrupp
10G_0AL
Figure 8: The study of the confidence level 8 on the Adult dataset. We vary ó e (0.01, 0.05, 0.1, FRG 5 sup and FRG 8 unsup denotes FRG trained with and without supervision respectively.
Predict Income
Rrorege ACE
Eorp
0.15
0.70
03
0.30
2
0.8%
0.00
60
037
074
0.00
17
015
5nd
D08
017
002
017
Predict (Adversarial task)
0.32
0.87
8A
0.8
Iveroge AUC
A.2
Avcroge ACC
DUDS
2.
Avstage BOC
0.25
RUB2
g
0.02
0.5
670
0.0
500
6.54
300
032
0.66
504
0G0
632
5.55
PRG
UNIF
ECRL
of
CEAIR
Figure 9: Additional metries including F1, Average Accuracy (ACC), Equal Opportunity Difference (EOPP), Equalized Odds Difference (EODD) for the evaluation the Adult dataset.
24

---

Predict Age
06:
Avtrage 8OP
643
05
Averrgg
0.00
Avarage
2.00
602
3.00
032
Predict Charison Index
3.50
6.0
3.00
0.8
Aeerege EOR
Zeerage
085
0044
0.52
0.8
0.6
0.35
Predict Gender (Adversarial task)
0.82
0.32
Aetrago ACC
0.25
Ret agoo EGPP
Amerage 1030
0.72
0.23
Arangge
0.93
0.3
61
033
00
5.6
032
5.16
6.2
MGG uugeuuer
UMIFA
LAITA
ICVE
PCR
MANE
IARE
CEAIR
Figure 10: Additional metrics including FI, Average Accuracy (ACC). Equal Opportunity Difference (EOPP). Equalized Odds Difference (EODD) for the evaluation on the Health dataset.
Predict Income
Predict Marital S. (Adversarial task)
0.80
1.0
0.7
0.75
0.9
0.8
ACC
0.70
Average
0.4
Auerage
0.8
Average
0.3
0.7
0.2
0.1
0.6
0.60
0.40
0.15
0.24
0.32
0.40
0.48
0.16
0.24
0.32
0.40
0.48
FRG superviseed
FARE
FARE
CFAIR
Figure 11: Additional metrics including Fl, Average Accuracy (ACC) for the evaluation on the Income dataset.
25

---

M A Case Study: Using a Mutual Information-based Upper-bound for Constraining APP to Avoid the Assumption of Optimal Adversary
Different from the proposed method in the main text that uses the worst-case ApP achieved by an oracle adversarial predictor to upper-bound ADP, we provide an alternative method that uses a mutual information (MI)-based upper bound for constraining App. Although the alternative method (named FRG-MI) does not rely on an oracle adversarial predictor for providing the guarantees, the upper- bound on App is so loose that the method is shown impractical (the constraint is too conservative to provide good utility). In the following subsections, we will first introduce the MI-based bound on
strictly increasing convex function of App as derived by [26] (Appendix M.I) p. As the alternative method shares similar components with FRG, including the candidate selection component and
the fairness test component, we will document the changes these components in Appendix MM.2
and M.3 while referring to the main methods (Sec. (5) for the repeated details. In Appendix M.44 we prove that FRG-MI also provides a 8 confidence e fairness guarantees (Def. (.2) as FRG
does. In Appendix M.5] we evaluate FRG-MI empirically to show that it may not be suitable for practical use. Finally, we discuss several other alternatives one might consider for upper-bounding ADP (Appendix M.6).
M.1 Mutual information bounds demographic parity
The demographic-pan haappphiic-ppitt-aaa parrty- based measure (Def. (.1] is specified for downstream models. Since want representation model to guarantee fairness for every possible downstream model and downstream task, we consider using mutual information-basee upper-bound on ADP. Gupta et al. [26] derived a bound for ADP(T, (T, Φ) that removes the dependency on the downstream model т. Specifically, Gupta et al. [26] showed that the mutual information between the representation and the sensitive attributes, denoted by [(Z; S), can be used limit the demographic parity of downstream models.
Property M.1 (Relation of mutual information to (DP(T. For all downstream models r in all
downstream tasks,
(2; 2 (AAP((T d)),
where vb is strictly increasing non-negative convex function derived by 26 and the details of which are in Appendix N.2 Proof. See the work of 266].
Notice that Property M.1 does not provide a direct upper bound on Ap o). Instead, it provides an upper bound on strictly incressing non-negative convex function of ADe(T, Φ). We use this property in the next section to guarantee fairness for representation models with high confidence.
M.2 The modified fairness test compared to Section 5.2
Different from Section 5.2 we now avoid the adversarial predictor but use Property M.4 to develop
high-confidence upper-bound for ge))). In this section, we first develop (Ø) where (Ø) <
only if ge (Ø) < O, and propose evaluating ge (Ø) < 0 to provably determine whether a representation
model á is s-fair, i.e., (d) < 0. We then follow similar procedure as Sec. 5.2 construct
high-confidence upper bound on ãe (Ø) instead of 9r (ő)) We follow Sec. 5.2 for the evaluation process for candidate solution de using this high-confidence upper bound.
mutual-infformatio---ass evaluation. Our goal is evaluate whether ge (Ø) S 0 with high confidence. However, estimating (e) sup, ADP(T, の) is intractable because it requires knowledge of all downstream models and all downstream tasks. To remove the dependency on downstream models, we apply Property M. and evaluate whether T(Z: r)(E) < 0 instead of
sup, (D Φ) - & S 0 (1/ is derived by Gupta et al. (26) and defindd in Appendix N.2 Intuitively, when the mutual information between the representation and the sensitive attribute is low, it is hard for any model to predict S' given Z with high accuracy. Therefore, any downstream model that does not explicitly aim to predict S is even less likely to take advantage of the sensitive attribute to produce unfair predictions. Theoretically, evaluating ((Z:S) ()()) I 0 can provably determine the =- e-fimmess of ó under Def. 4.1 We postpone the theoretical analysis to Appendix. M.4
Unfortunately, computing / [(:; S) is intractable because it requires marginalizing the joint distribution of (X, 5, Z) over feature vector X, and so even this approach remains intractable. Multiple previous works have derived tractable upper bounds T(Z:S), which we discuss in detail in Appendix 1.6.1
Let i(2; S) be one of these tractable upper bounds on (Z; Then, we define
(Ø) = ī(Z;S) ((5).
(47)
26

---

With this upper bound, we now evaluate the e-fairness of o by evaluating (Ø) S O. In Lemma M.2 we prove if Pr (āe (o()) s 0) 2 6, then algorithm provides the desired high-confidence fairness guarantee.
1 1- å confidence upper bound on ge (o). We follow two steps similar to Sec. 5.2 to compute a 1 - 6 confidence upper bound on 9e (Ø). (1) Obtain m i..d. unbiased estimates "it)....,. g(m)) of āe (6) using D,. i.e. [[gh]] = (6) for any j E [l..... ml. (2) Apply standard statistical tools such as Student's 1-test [69] or Hoeffding's inequality (20 to construct 1 - confidence upper bound on
(Ø) using g(1) -....g(m) We also use Student's 's t-test for our experiments (Appendix M.
Similar to Sec. 5.2 we define U²= (Φ, D) + E to be such function that produces 8
confidence upper bound. Specifically, for (6 Dr), we have the following.
Pr (T()=()) < ('(
(48)
The remaining steps for evaluating the candidate solution are equivalent to those of Sec. 5.2
M.3
The modified candidate selection compared to Section 5.3
The candidate selection procedure is not changed from Section 5.3 except now it estimates the alternative high-confidence upper bound U (D) We can also avoid the adversarial training process for estimating the upper bound as we can adopt the same procedure as in the fairness test.
M.4 Theoretical analysis
In this section we prove that FRG-MI is a representation learning algorithm that provides the desired high confidence c- f-iimess guarantee, i.e., the probability that it produces representation that is not e-fair for every downstream task and model
most 5.
We first prove in Lemma M.2 that if an algorithm a satisfies Pr (āe (a(D) < < 1 6, then algorithm provides the - ò confidence e-fairness guarantee described in Def. 4.2 We then prove in Theorem M.3 that FRG-MI indeed satisfies Pr (āe (a(D)) S 1 ö. Altogether, we can conclude that FRG guarantees with 1 - 5 confidence that ADP(T, (()) is bounded by e for any T (recall that here a corresponds FRG-MI and (DD) corresponds the representation model parameters returned by FRG-MI when run on dataset D).
Lemma M.2. !f algorithm a satisfies Pr (a D)) < 0) 2 1 - 6, then algorithm a provides the 1 ô confidence e-fairness guarantee described in Def.
4.2
Proof. Suppose Pr (ā. (a (D) 00) 8. By Eg. 47
Je (a (a( I(z;5) v)E)) > ((
(E). By property M. 1 1(2;5) 2 sup, (T a (D))). So. the event (āe (D) < 0) implies
that( (2; -
((E) & 0), which further implies (sup- v ((Dpr(, a(D)) (5s) S 0). Using the
fact that th is strictly increasing in [0, 1] (Appendix N.2 have the following equivalent events:
sup sup al (D)) (b(c) =0))=0)
(49)
(osu (T, (D))) S (t)
(50)
((D) Aop (D) st)
(51)
Sop( - 5
(52)
(a()) 20).
(53)
It follows that Pr (r-(((D)) < 0) > Pr (r)(((D) < the desired 1 8 confidence e-fairness guarantee described in Def. 4.2 completing the proof.
0) 1-8. So, FRG-MI (algorithm a) provides
Theorem M.3. FRG-MI provides the 8 confidence E-fairness guarantee described in Def. 4.2
Proof. By Lemma M.2 if FRG-MI satisfies Pr (r(ge (a())) < 0) 2 1 - 8, then FRG-MI provides
the desired 8 confidence s-faimess guarantee. Following the same proof for Theorem 5.3 in
Appendix F we can prove by contradiction that when a represents FRG-MI, Pr (aD)) 5 2
1 1-d 8.
27

---

10
Hiz:51
(Z;58)
10
2
6ap
Cap
1
Gap
2
Cup
10
(Arr((T.)))
10
Age
Figure 12: Using the Adult dataset (details in Appendix. [ we run L-MIFR [6 with different hyper-parameters find representation models that achieve different Apr Ø). For each of the representation model, we record the corresponding tractable upper bound T(Z;5) by Song et al. (8 Section 2.2], denoted as 7, (Z; S), and make the scatter plot in blue. We plot the function 4²()) (Appendix N.2) in red. We highlight that there exists gap between I (2; S) and v (r,(r, 6)). which consists of two gaps. (2; S) - i(2; S) and ((2:5) < (ADe(T, ()). and it can be observed empirically shown by the plot. As ADP decreases, the gap between (2; S) and (D(DD(( 6)) increases.
Adult
0.2,
0.1, = (2: 0.0044
Averaoe AUC
Average A.r
Probabiltyy Solution
Probabiitty
0.2
0.7
0.200
0.80
0.175
0.6
0.75
0.150
0.125
0.03
0.000
0.3
0.755
0.60
0.2
0.53
10a
Amount of data
Amount of data
Amaunt of data
Amount cata
Figure 13: We give an example of employing FRG-MI to provide high-confidence fairness guarantees (Def, 4.2 on the Adult dataset, including VAE as baseline.
M.5 Experiments
We first visualize in Fig. 12 and confirm that the gap between (Z; and (/AAPP( Φ)) indeed exists empirically and the gap increases App approaches O.
We then evaluate FRG-MI that provides high-confidence fairness guarantees (Def. 4.2) on the Adul dataset. For demonstration purposes, we select & 0.2 and 5 = 0.1, which means that FRG-MI guarantees with 90% confidence that downstream models do not violate ADp(T, o) s 0.2. is worth 0.2 is smaller than both the App calculated with the true labels (0.26),
noting that the selected and the upper bound on ADP calculated with the prediction labels from a predictor that achieves equalized odds [76] Theorem 3.1J. We estimate Pr(S 1) R 0.668 from the dataset, which yields (e))) Re 0.0044. We incorporate the constraint 1, (2; S) S (EE) guarantee e e-faimess with 1 8 confidence (Z; denotes the upper bound / (Z; derived by Song et al. [68 Section 2.2]). We include vanilla VAE without any fairness consideration as a baseline. The amount of training data used varies from 10%, 15%, 25%, 40%, 65% 100% of the original data.
show the result Fig. 13 demonstrated the second and fourth plots, FRG-MI violates constraint (pp(T, Φ) < 0.2 with probability smaller than 0.1, whereas VAE violates the constraint
with a probability larger than 0.1 when it uses less than 65% of the training data. According to the third plot, FRG-MI can also return solutions (i.c., not NSF) for all the trials.
28

---

Nonetheless, the constraint (2: < (E)) is overly conservative, which leads to relatively low AUC on average, as illustrated in the first plot. Additionally, the fourth plot demonstrates FRG-MI's ability to consistently keep App near zero. Hence, applying an even stricter & constraint on FRG-MI for high-confidence fairness guarantees is impractical and unnecessary.
We further analyze the gap between (Z; and (suup, ADP(T, o)) in Appendix O and the gap between (2) and [ 5) in Appendix P
M.6 Other alternatives for upper- bounding ApP
So far we have discussed using mutual information to upper bound ADP (the violation of the demographic parity constraint), and ensure the e-fairness of a representation model with high confidence (Sec. (.2) Since [(2; S) is intractable, in Appendix [M6..] we review four tractable upper bounds on T(;5)) and also discuss why in our experiments we adopt the first upper bound, (Z; S)), derived by Song et al. [68 Section 2.2]. We then test whether (2; S (b() to obtain the desired fairness guarantee (Eq. 47p.
Because mutual information can be intractable, one might consider alternative methods for bound- ing App. In Appendix M...2] we explore potential alternatives for upper bounding Adp but find limitations that prevent the adoption of these methods in FRG.
M.6.1 The Tractable Upper Bounds on SZ:
To our best knowledge, there four tractable upper bounds on mutual information T(Z; S) as derived by previous work [26 54 688. Next, we discuss these approaches and their limitations. Although our general approach is compatible with any upper bound mutual information, given the limitations of each method, we consider the first of the two approaches (ī (Z; S) below) by Song al. 668 the most suitable in practice. Thus, we only adopt (Z( in our experiments.
Song et al. (68 proposed two upper bounds on SZ:
(Z; the first upper bound derived by 68, Section 2.2]. We denote the first upper bound as S): and (2; > (2; > I(Z;5) S) 688 Section 2.2]. This is a theoretically guaranteed upper bound. We discuss the limitation of this upper bound in Appendix PP that using this upper bound may diminish the expressiveness of the representations. However, we still find it effective for FRG to limit ADP by E in experiment (Sec. (
S); the second upper bound derived by (68, Section 2.3]. Song et al. 68 proposed a tighter upper bound compared to Z (2; S), which we denote as I2(Z;S), S). However, it requires adversarial training, and the true upper bound can only be obtained when the adversarial model approaches global optimality. This is not ideal because if the adversarial model is under-performing, we may under-estimate the upper bound to (Z; S), and guaranteeing Zs: < (EE) does not guarantee I(Z; 8) < voE) or e-fairness. This result has also been confirmed by prior work including Elazar and Goldberg [21] Gupta et al. (26), Xu et al. (73 and Gitiaux and Rangwala (23]
iz( the upper bound derived by Moyer et al. (54) Moyer et al. (54 found S) = X) H(X[S) + H(X| 2, S) where H denotes entropy. They proposed ig- noring the unknown positive constant term H (X|S) and using the reconstruction error, i.e.,
- -Bx,(21x.5)
to be an upper bound of H(X [54] Equations 2-7]. Let
(z( = X(Z 12 log (X Moreover, it can be difficult to estimate
the gap 5) ((: S) because (1) (X(SS) is hard to estimate; (2) Iz( is sensitive to the performance of the reconstruction model.
S): the upper bound derived by Gupta al. [26]. Gupta et al. 26 observed that T(Z; = T[Z; + T(2; T(Z; S|S). They then derived lower bound for the term 5) can be upper-bounded. Specifically, they T(Z; X|S) using constrative estimation so that T(2:5)
eJ(x22.5) proved X[2; > Ep(x,2,5) log -m c/((x....m)))) where p(X, S) is the joint distribution of (x, Z,S). Xi.... .MM Px]s. Pxis is the conditional distribution of X given S, and f is an arbitrary function (26) Proposition 5J. Since the distribution Px|s is unknown, the authors use the X pairs in the dataset as samples from this conditional distribution. When making a point estimate of the expectation, they use one sample from the dataset to evaluate the numerator, and use M samples from the same dataset to evaluate the denominator. This means that the estimation of
29

---

the expectation can be biased because the point estimates are not independent. Empirically, we also observe this issue and find that tends to result in over-estimates of [Z; and under-estimates of S)) Given how these terms are used in the expression for ((:5)) this results in bounds on mutual information that do not hold.
M.6.2 Alternative Methods for Upper-bounding App
One might consider alternative methods for bounding App because mutual information can be intractable and there can be a significant gap between mutual information and g (A) (that is, the upper bound can be loose). Several alternative methods have been proposed, which can provide bounds on Ape using bounds on the total variation between the conditional distributions Pr.e (Y|S 0) and (Y S
48 66 76.. However, to our knowledge, there is not known function such as db (Appendix N.2 that expresses the relation between the total variation and demographic parity, so total variation cannot be used to upper bound sup, ADp(T, Φ) with a specific In other work, Jovanović al.
33 Section 5] proposed a practical certificate that upper bounds sup, ADP(T, Φ).
However, their method requires Z to be discrete random variable, which is restrictive for general representation learning. Therefore, these methods are not suitable for our framework as they cannot be used to learn E-fair representation models with high-confidence guarantee.
N Details of Property M.1
Gupta et al. [26] has derived Property M.1 where [Z: an upperbound for a strictly increasing
non-negative convex function in ADP of any т, which we denote as th. Gupta et al. [26) has also found that when [(2; 5) = 0, th ())nPPT, Φ)) = 0 and ADp(T, 6) = O. We now define vi in detail by first introducing helper function f.
Definition N.1 (A helper function f).
2
2V
V2
V4
1/6
S(V) = max log
+
+
2 2
2 - V
2
36
288
with domain V E [0, 2).
Definition N.2 (function & with parameter ADP(T, Φ)). When is binary, and f follows Def. N.I
(T 6)) = (1- (T x)) f((1 -P) x))
where æ PS 1) with P. the marginal distribution of S E (0, 1).
When S is multinomial with K classes,
4 (ADP(TT x)) = (T)
min Tk, k=1....K
where P.SS = k)) with P, as the marginal distribution of S E (1..... K].
K}.
O The Non-trivial Gap between SZ; and (sup, ADP (T, 6))
In this section, we analyze the non-trivial gap between T(Z;SS) and (suu,, ADP(T, , Φ)) that makes it difficult for any algorithm to obtain e-faimesss.
As shown by Gupta et al. 26 Figure 6], there tends to be significant gap between ((2; 8) and (sup, ADP(T, Φ)). Using their Figure 6 as an example, when I(Z; = 0.035, ATP(T, Φ) ~ 0.15 and (P Φ)) = 0.0025. So, to ensure that ADr(T, Φ) < 0.15 with high confidence using the zi- babd bound on mutual information, one must ensure that I(Z;S) < 0.0025 with high confidence. However, in reality ensuring that ADp(T, b) S 0.15 only requires T(Z:S) S 0.035. Obtaining solution that satisfies S( < 0.0025 is far more difficult than obtaining solution that satisfies T(Z; & 0.035, and hence using the bi-da bound on mutual information results in exceedingly conservative bounds on App.
P The Non-trivial Gap between (Z; and I S)
In this section we analyze the non-trival gap between (2; and T(Z:S) where 7, (2: (Ap- pendix I. h is one of the upper bounds to T(Z:S) as derived by Song et al. 68 Section 2.2]. We begin by analyzing the gap between [(2; X, S) and ((Z I(Z ((2
30

---

S( = = between and Z given S, which is closely related the primary objective we hope to maximize. Overall, we have the following:
((X)S) - H() = Z|s) This is the mutual information
T(2:5) <I(Z;X,5)
(54)
=I(Z,5) [(X
(55)
<1((2;5)
(56)
Although using constraint (); S (E)) encourages both ((Z and 1X;; to be small which seems to diminish the expressiveness the representation model, we show empirically that is effective for upper bounding mutual information and the App of the downstream tasks with high probability experiment (Sec. M.5).
31

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We claimed that FRG provides high-confidence fairness guarantees for rep- resentation learning where both the threshold for unfairness and the confidence level are user-specified. This claims justified with Sections 6
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We specified our limitations in Section and 7 Specifically The theoretical guarantees of FRG make several assumptions. First, assume all data samples are i.i.d. Second, the use of Student's 's t-test assumes the point estimates of g are normally distributed, which requires large sample such that CLT holds. Third, assume access to optimal adversary (Def. 5. that uses representations as input to predict the sensitive attributes maximize ADP- We approximate with independently trained model. Lastly, the guarantee is only applicable for controlling App but not other fairness metrics such as Equal Opportunity or Equalized Odds.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms
and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
32

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide proofs Theorems 5.2 and 5.3 Appendix and assumptions are stated in the theorem statements.
The
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: We provide the complete specification our method in Section Regarding the empirical evaluation, we provide detailed descriptions for the experiment setup, the baselines, the datasets, and the hyperparameter tuning in Section Appendix [nd
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
33

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The source code is provided in anonymous github repo with links provided in the abstract and in the supplementary material submitted. The datasets are open source. The instruction for downloading the data is provided in the README file in the source code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
ciiiaps.cc/uullcc/ggi
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the training and test details (including data splits, hyper parameters, how they were chosen, type of optimizer, etc.) are clearly specified in Section 6 and Appendix The detailed choices of hyperparameters for each of the datasets, the unfairness thresholds s's, and the baselines are provided with config files in the source code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
34

---

7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We repeat each experiment at least 20 times. Each data point in the figures is accompanied by error bars. The error bars are calculated with the .td () function in the pandas library. We mentioned in Section 6 about how error bars are calculated.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етrоr rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The GPU used is one NVIDIA A16, and we use 128 CPUs with the model AMD EPYC 9354 32-Core Processor.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htttps:/neuurpps. http:///waaarrpp.cpppppp//taaaaa
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Guidelines:
35

---

The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We have sufficiently discussed both the potential positive societal impacts and negative societal impacts. The positive impacts
provide high-confidence fairness guarantees for representation learning, which is critical for lots of applications (Section [T. However, there are limitations we have discussed in Section which may affect the effectiveness of the guarantees. For example, if the test data is under a distributional shift from the training data, the guarantees may no longer hold.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks because neither new data pretrained models are released.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided relcasing unsafe images.
36

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The original papers that produced the code packages and datasets are properly cited. The URL to the datasets are included.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide source code in anonymized URL in abstract and the supplementary material. The details about training, license, limitations, etc., are provided in the README file of the source code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
37

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy lattps://neuripe http//rrrrp.ccccooofeeeeeeee//// for what should or should not be described.
38


Reviews:
[{"review_id": "NLfNxiqQbd", "reviewer": "Reviewer_xgom", "summary": "This paper formally introduces the task of learning representations that achieve high-confidence fairness. Then it presents a novel framework FRG that learns fair representations for all downstream tasks based on demographic parity.  It guarantees with high confidence that the output representation models are fair according to user-specified thresholds of unfairness and confidence levels. Experiments on three real-world datasets demonstrate that FRG consistently bounds unfairness across a range of downstream models and tasks.", "questions": "Besides the questions in the Weaknesses, I also have the following questions:  \n- Does the proposed method apply to other supervised fairness metrics, such as equal opportunity and equalized odds?\n- What are the computational tradeoffs? Can you compare training time with otherbaselines?\n- The details of the model architecture and parameter settings are missing in the paper.\n- In line 189, you mentioned \"In practice (section 6), we find it sufficient to train an approximately optimal adversary to predict S based on Z\". Can you elaborate more? Does the choice of adversary design affect this statement?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n- This paper identifies a practical gap, a lack of high-confidence guarantees in current fair representation learning approaches. And it extends fairness guarantees to all downstream tasks and models. The studied problem is interesting and significant.\n- Experiments on the three datasets and a range of tasks demonstrate the effectiveness of the proposed framework in both fairness and useful representation learning.\n- The paper is clearly written and easy to follow. \n\nWeaknesses:\n- The theoretical analysis in section 5.2.3 assumes access to an optimal adversary. Although FRG approximates the adversary, it might not always be realistic in practice. Is there theoretical support for the guarantee of obtaining the optimal adversary, such as requirements for model complexity and training data size?\n- Repeated training of adversaries and statistical testing introduces a computational burden. While not prohibitive, this could limit real-world scalability. The author should also present a comparison of the computation cost/time.\n- The presentation of the experimental results is poor. In Figure 3, I can hardly see the blue line, which is the performance of the proposed method.\n- The choice of datasets is limited, and some of them are outdated. For the adult dataset, you should better use this updated one: \"Retiring Adult: New Datasets for Fair Machine Learning\"", "was_revised": true, "final_justification": "My concerns on the adversary choice, questions on the training cost, and generalization to other fairness metrics are properly addressed.", "rebuttal": "We thank Reviewer xgom for carefully reviewing our work and appreciating the significance of the studied problem and the delivery of the writing and experiment. We provide detailed discussions below to address your concerns.\n\n---\n\n## Q1: The assumption of access to an optimal adversary might not be realistic. Is there theoretical support for the guarantee of obtaining the optimal adversary?\nOur theoretical analysis does assume access to an optimal adversary, as pointed out throughout the paper. We address this concern as follows.\n\nFirst, we *empirically validate that our adversary is a sufficiently strong proxy for the optimal one*. The adversary is approximated by training an MLP to maximize $|$Cov$(\\hat{Y}, S)|$ (Sec. 5.1). This architecture, despite its simplicity, achieves very high AUC, > 98% AUC for each dataset, on the adversarial task when representations are learned without fairness considerations. Our experimental results suggest that the adversary achieved with gradient optimization is sufficient to obtain a valid high-confidence upper bound on the unfairness of arbitrary downstream tasks.\n\nSecond, a guarantee for an optimal adversary *can be provided by restricting the model and the representation complexities*. This approach was taken by FARE[2], which replaces the representation model with the fair decision tree to restrict the representation to be drawn from a discrete distribution with a finite support. While this approach can guarantee access to the \"optimal adversary\" defined in [2] and provide a theoretically guaranteed upper-bound on $\\Delta_{\\text{DP}}$, the limitations of FARE will be carried over. In experiment (Sec. 6.2) , we found that FARE can only produce limited variations of representations, so it cannot control the tradeoff between performance and fairness with enough granularity. A lot of times, it is impossible to find a representation model that satisfies the fairness constraints when $\\epsilon$ is small, while it is still possible for FRG (Figures 2 and 3). Essentially, this approach violates the controllability, which limits the practicality.\n\nThird, we note that the question of how to provide theoretical guarantees for obtaining or bounding the performance of optimal adversary is *a common challenge faced by the field*. For example, Feng et al. [7] derived a bound to the accuracy of the optimal Lipschitz-continuous adversary, but the bound is non-tractable in practice. Similar assumptions of access to optimal adversaries have been used extensively by previous works (e.g., [1-6]). Thus, we believe a solution to this challenge merits its own study.\n\nFinally, we also *developed an approach that does not require optimal adversary*, using a Mutual Information (MI)-based upper-bound on $\\Delta_{\\text{DP}}$ (Appendix K). This approach gives a theoretically guaranteed upper-bound on $\\Delta_{\\text{DP}}$ across arbitrary downstream models and tasks that does not assume optimal adversary. However, experiment shows that this upper-bound can be significantly loose (Figure 12) and thus enforcing fairness constraint on this upper-bound is non-practical (Figure 13).\n\nThank you for raising this important question. We will incorporate a summary of this discussion in the limitations section in our revision.\n\n---\n\n## Q2: Does the choice of adversary design affect the guarantee (the claim in line 189)?\nThank you so much for pointing out that this was not clear. We think the choice of the adversary **will** affect the robustness of the guarantee. One should choose an adversary that achieves high performance on the adversarial task. If a weak model is chosen, it will not approximate the optimal adversary well. In our implementation, we use an MLP with one hidden layer and tunable hidden sizes as the adversary. We think this architecture is strong enough for the datasets we have tested. We have also verified that this architecture will lead to high prediction performance (> 98% AUC across our three datasets) of the adversarial task if the representations are learned without fairness consideration. We think the optimal adversary is well approximated such that even on the adversarial downstream tasks, we can still guarantee fairness while the baselines cannot. In general, we think the best choice of the adversary would vary case by case and be informed by the prediction performance on the adversarial task. While these notes are purely empirical, how to provide a theoretical bound on optimal adversary is still an active research problem as discussed in Question 1. We will make sure to clarify the choice of the adversary design in our revision.\n\n---\n\n## Q3: Repeated training of adversaries and statistical testing introduces a computational burden. What is the computation cost compared to baselines?\nWhile the training of the adversary and the fairness test introduce some computational overhead, they are *very small* (around 5% of the overall runtime) compared to the training time of the representation model (95% of the runtime). Here is an example for the Income dataset. We train the representation models with 500 epochs across all baselines. The overall runtime of FRG is 330s, which includes training the adversary, representation model, and the fairness test. Training the adversarial model takes 16s (4.8%), the fairness test takes only 0.06s (0.02%), while training the representation takes about 95% of the runtime. Here is a comparison with the baselines: CFAIR takes 303s, ICVAE takes 1021s, LMIFR takes 336s, LAFTR takes 326s, FARE takes 41s (only one call to fit the decision tree). Thus, *we think the computation cost is not a concern*. In the revised manuscript, we will include a short paragraph clarifying this.\n\n---\n\n## Q4: The presentation of the experimental results is poor. In Figure 3, the blue line is hard to see.\nThanks for raising this concern. We *have increased the marker sizes and used new marker shapes for FRG* and they appear much more visible now. We will make sure the final version shows the results as clearly as possible. To address your concern, the blue line achieves very similar results to the orange line, which is also our proposed approach but with supervised loss, thus they overlap. They always satisfy the fairness constraints.\n\n---\n\n## Q5: The choice of datasets is limited, and some of them are outdated. For the adult dataset, you should better use this updated one: \"Retiring Adult: New Datasets for Fair Machine Learning\"\nThanks for the suggestion. To clarify, ***we have included the new Retiring Adult dataset you mentioned***. We call the new dataset the \"Income\" dataset (citation [17] in the manuscript) to differentiate from the traditionally used \"Adults\" dataset. In total, we have included three distinct datasets, each with 2-3 downstream evaluations, which matches most previous works. We will clarify this naming convention in the revision to avoid any confusion.\n\n---\n\n## Q6: Does the proposed method apply to other supervised fairness metrics, such as equal opportunity and equalized odds?\nThis is an insightful question. Indeed, the proposed method ***can be applied to Equal Opportunity (EOP) and equalized odds (EOD) with simple modification***, but it requires that the outcome labels, Y, for the downstream task of concern are available to compute EOP and/or EOD. We will use EOP as an example. $\\Delta_{\\text{EOP}}(\\tau,\\phi) \\coloneqq |\\Pr(\\hat{Y} = 1 |S =1,Y=1) -  \\Pr(\\hat{Y} = 1 | S = 0,Y=1)|$. This is equivalent to $\\Delta_{\\text{DP}}(\\tau,\\phi|Y=1)$. The rest follows, except we only consider the subset of the data where $Y=1$ when constructing the high-confidence upper-bound. Similarly, $\\Delta_{\\text{EOD}}(\\tau,\\phi) = \\max(\\Delta_{\\text{DP}}(\\tau,\\phi|Y=0), \\Delta_{\\text{DP}}(\\tau,\\phi|Y=1))$ which one can also construct the high-confidence upper-bound using our framework by splitting $\\delta$ in half for each of $\\Delta_{\\text{DP}}(\\tau,\\phi|Y=0)$ and $\\Delta_{\\text{DP}}(\\tau,\\phi|Y=1).$\n\nIn the revised manuscript, we will clarify how our approach can be used to constrain EOP and EOD. However, we note that the high-confidence upper bound requires outcome labels, Y, from a specific downstream task, so in this context the guarantee can be applied only to that task, which *might not be generalized to arbitrary downstream tasks*, as is the case for the DP (demographic parity). This is a common limitation to existing approaches as well (e.g.,[2-3]).\n\n---\n\n## Q7: The details of the model architecture and parameter settings are missing in the paper.\nSorry that the details of the parameter settings are not included in the paper. We use different hyperparameters for different $\\epsilon$'s and datasets. We included all of the hyperparameter choices for each of the settings in the config JSON files in the source code provided (as mentioned in Appendix H “Hyperparameter Tuning” referenced in the main text, line 333). The model architecture of our method is discussed in Sec. 5, and the downstream model architecture is discussed in Appendix H. To improve readability, we will also add a summary table of the key hyperparameters choices to the appendix in our revision.\n\n---\n\nThank you again for reviewing the work, and we will be happy to discuss any further questions you may have.\n\n#### [1] Gupta et al. Controllable guarantees for fair outcomes via contrastive information estimation. AAAI 21.\n\n#### [2] Jovanović et al. Fare: Provably fair representation learning with practical certificates. ICML 23.\n\n#### [3] Song et al. Learning controllable fair representations. AISTATS 19.\n#### [4] Madras et al. Learning adversarially fair and transferable representation. ICML 18.\n\n#### [5] Kairouz et al. Generating fair universal representations using adversarial models. IEEE TIFS 22.\n\n#### [6] Zhao et al. Conditional learning of fair representations. ICLR 20.\n\n#### [7] Feng et al. Learning fair representations via an adversarial framework. CoRR 19."}, {"review_id": "Ao3jycYnoj", "reviewer": "Reviewer_yn4p", "summary": "This paper introduces Fair Representation learning with high confidence Guarantees (FRG), which is an algorithm for learning models that are guaranteed to be fair in terms of demographic parity when applied to downstream tasks with high probability. The high-level idea applied by FRG is to first train a candidate model (e.g. a variational autoencoder modified with a fairness constraint) using part of the data and then train an adversary that aims to predict protected attributes using the representations from the candidate model. The adversary is used to check whether the candidate model provides the guarantees specified by the user. More specifically, the adversary is used to estimate the fairness bounds based on small data samples (data pairs) using a statistical test (e.g., student-t). Under some assumptions on the data samples, the number of samples, and the accuracy of the adversary, the paper shows that the theoretical guarantee on fairness is achieved. In the experiments, FRG is compared against six baselines in terms of downstream fairness and accuracy using three datasets. The results show that FRG achieves better accuracy than alternatives that are able to guarantee downstream fairness with high probability.", "questions": "Q1. Are there non-trivial fairness vs. quality tradeoffs with the guarantees provided in the paper? Is it possible to provide a more comprehensive view of such tradeoffs to demonstrate the practical use of the proposed solution?\n\nQ2. How realistic are the assumptions considered in the paper and how robust is the method to small violations of such assumptions that might occur in real datasets.\n\nQ3. How is Theorem 5.2 useful in the paper?", "limitations": "The limitations are discussed in the paper.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n- The paper addresses a relevant problem.\n- The paper is well-written and its motivation is clear.\n- The experimental results support the main conclusions in the paper.\n\n**Weaknesses:**\n- The accuracy of the proposed approach seems too low when fairness bound is tight\n- There is little discussion about the assumptions of the proposed model\n- It is not clear how theorem 5.2 is used in the paper (compared to DP)\n\n**Detailed comments:**\n\nThis is an interesting paper addressing a relevant problem but with some clarifications needed regarding its assumptions and experiments. I will detail my main concerns here.\n\n*Accuracy:* The accuracy results for FRG reported in Figure 2 seem very low when epsilon is small. This might be a limitation of the dataset, the model, or it could be justified theoretically. It would be helpful to understand the source of the error to some extent. In particular, one can assume that there are no practically useful models that can provide the type of guarantees considered in this paper. \n\n*Assumptions:* The main assumptions of the proposed approach are listed in the limitations but some discussion is needed regarding how realistic these assumptions are and whether they are expected to hold for the datasets considered. In particular, the assumption of an optimal adversary seems unrealistic, so a stronger result would bound the bounds in terms of how close the adversary is to optimal or in terms of the adversary model and the data used to train it. A synthetic dataset could be useful to clarify this.\n\n*Theorem 5.2:* It was not clear to me why Theorem 5.2 is useful in this paper. Does it provide any benefit compared with the original definition of Demographic Parity?", "was_revised": true, "final_justification": "I believe this paper makes an interesting contribution towards fair machine learning by incorporating confidence guarantees into fairness assessments. My original review was positive (accept) and the authors have clarified my questions during the rebuttal. My suggestions for improving the paper were the following:\n\n1) Adding some discussion about what values of confidence lead to practical accuracy values on real datasets;\n\n2) Providing some intuition on why it is easier to maximize the covariance instead minimizing demographic parity (Theorem 5.2).", "rebuttal": "Thank you so much for carefully reviewing and appreciating our work and raising insightful questions. We address your concern as follows.\n\n---\n\n## Q1: The accuracy of the proposed approach seems too low when the fairness bound is tight (Figure 2).\nWe think your comment is insightful. On the Adults dataset, when the fairness constraint is strict, e.g., $\\epsilon <= 0.08$, the AUCs of our method are around 60-63% which are *better than all baselines that satisfy the constraints* (ICVAE and FARE). Referring to Appendix Figure 6, we can see that our method achieves the best fairness and accuracy tradeoff. So we agree with you that one can assume there are no practically useful models that can provide such a strict guarantee. In this case, we think it is due to a small $\\epsilon$.\n\n---\n\n## Q2: There is little discussion about the assumptions of the proposed model. How realistic these assumptions are and whether they are expected to hold for the datasets considered? \nThanks for the comments. Our main assumptions are provided in Section 7 which include (1) data samples are i.i.d., (2) Student's t-test assumes CLT holds, (3) access to an optimal adversary is available.\n\nRegarding (1), the guarantee could be sensitive to some distributional shifts. If the test dataset has a different distribution of (X,S), the guarantee that the representation model is fair with high probability may no longer hold. However, the guarantee is robust to label shifts because the label is not necessary when learning the representation model and constructing the high-confidence upper bounds. That is, if the test dataset has a different distribution of label Y or distribution of Y conditioned on (X,S), the guarantee will still hold.\n\nRegarding (2), we think this assumption is not very sensitive for most datasets. Our guarantee seems robust for datasets of various sizes (from 41k to 195k). While the t-test assumes normality, it is relatively robust to violations of this assumption, even with small sample sizes, as long as the data are not severely skewed or contain extreme outliers [1].\n\nRegarding (3), we think the choice of the adversary **will** affect the robustness of the guarantee. One should choose an adversary that achieves high performance on the adversarial task. If a weak model is chosen, it will not approximate the optimal adversary well. In general, we think the best choice of the adversary would vary case by case and be informed by the prediction performance on the adversarial task. While these notes are purely empirical, how to provide a theoretical bound on optimal adversary is still an active research problem and could be studied by future works (this is discussed in the response to Question 1 by Reviewer xgom).\n\nWe will provide an extended discussion of each assumption in our revision.\n\n#### [1] de Winter, J., Using the Student's t-test with extremely small sample sizes, Practical Assessment, Research, and Evaluation 18(1): 10. 2013.\n\n---\n\n## Q3: It is not clear how Theorem 5.2 is used in the paper. What is the benefit compared to $\\Delta_{\\text{DP}}$?\nThanks for pointing out that this was not clear. Theorem 5.2 is not used to prove that FRG provides the high-confidence fairness guarantees. However, it inspires our choice of the adversarial objective. We define the optimal adversary to be one that maximizes $\\Delta_{\\text{DP}}$. In Theorem 5.2, we show that maximizing $\\Delta_{\\text{DP}}$ is equivalent to maximizing $|$Cov$(\\hat{Y} , S)|$. Thus, this gives justification that optimizing the adversary with the objective of maximizing $|$Cov$(\\hat{Y} , S)|$ can approximate the optimal adversary. Empirically, we show that our design of the adversarial prediction is effective in providing the desired guarantees. We will be sure to clarify this in our revision.\n\n\n---\n\n## Q4: Are there non-trivial fairness vs. quality tradeoffs with the guarantees provided in the paper?\nThanks for raising this question. The fairness vs utility tradeoff for each dataset is provided in Appendix Figure 6. Our method achieves competitive tradeoffs compared to the baselines. Specifically, on the Adults dataset, FRG achieves the pareto frontier of this tradeoff.\n\n---\n\nThank you again for reviewing the work, and we will be happy to discuss any further questions you may have."}, {"review_id": "SywscGmzEf", "reviewer": "Reviewer_XhGo", "summary": "The paper introduces Fair Representation learning with high confidence Guarantees(FRG), a framework that learns fair representations with high confidence. The fairness tolerance and confidence level are user-specified. The framework provides this guarantee for any downstream task and model that uses the learned representation. FRG splits the training dataset into a candidate-selection set and a fairness-test set. Then, FRG uses the candidate selection set to train a representation learning model. The paper utilizes the VAE-style objective and adds a fairness proxy constraint to ensure the learned representations satisfy the fairness constraint. After the candidate model is provided, FRG trains an adversarial model that tries to estimate sensitive attributes using the learned representation. The authors show that the adversary that maximizes the covariance between prediction and sensitive attribute is equivalent to maximizing the demographic parity(DP) gap. Lastly, the framework uses the fairness-test set to provide confidence bounds on the worst-case DP gap using the Student t-test intervals. If the test fails, the framework returns that no solution was found(NSF). The experiments cover multiple real-world datasets, multiple tasks, and comparisons with baselines.", "questions": "Please see the weaknesses section.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- To the best of my knowledge, this is the first fair representation learning method offering user-controllable fairness tolerance and confidence certification on any downstream task that is required to be DP fair.\n- The experiments section is quite comprehensive, the authors compare their method with multiple baselines and provide enough ablation studies. Their method performs better than the baselines in terms of satisfying the fairness violation, and the AUC and accuracy values are similar to the baseline models. They also report the frequency of returning NSF.\n- The theoretical results are supported by clear assumptions and easy-to-follow proofs.\n\nWeaknesses\n- The adversarial inference utilizes the relationship between the DP gap and the covariance between the predicted sensitive attribute and the true sensitive attribute. It is not clear to me how this will generalize for other fairness notions, such as equal opportunity or equalized odds.\n- The student-t confidence bound relies on CLT; there is no study on how this affects small per-group sample sizes. The CLT approximation could behave poorly. \n- In the experiments section, the FRG and baseline methods use the same number of training samples. The baselines use another dataset for validation, but FRG uses this dataset for both validation and fairness testing. I think that for a fair comparison, the fairness-test dataset should be picked among the training samples. \n\nOther comments:\n- The paper is well written, except for a few parts. I think that the section confidence upper bound on fairness violation(5.2.1) is a bit confusing; the pairing part can be explained better. Also, the part where the confidence bound hyperparameter for training, $\\alpha$, can be explained better, is it just the previous $\\hat{U}=\\alpha U$?\n- Line 206, mulitclass --> multiclass\n- Line 259, hyperparamtr --> hyperparameter\n- Line 648, reference to equation 32 doesn't look correct to me.", "was_revised": true, "final_justification": "I think that this paper has more positive sides than negative sides. The authors replied to all reviewers in detail.", "rebuttal": "Thank you so much for carefully reviewing our work and appreciating our novelty, the empirical and theoretical results. We address your concern as follows.\n\n---\n\n## Q1: How will the relationship between $\\Delta_{\\text{DP}}$ and $|\\text{Cov}(\\hat{Y}, S)|$ generalize to equal opportunity or equalized odds?\nThanks for raising this question. We proved in Theorem 5.2 that $\\Delta_{\\text{DP}}(\\tau,\\phi) =|\\text{Cov}(\\hat{Y}, S)|/\\text{Var}(S)$. This ***can be extended to equal opportunity (EOP) and equalized odds (EOD) with simple modification***,  but it requires that the outcome labels, Y, for the downstream task of concern are available. \n\nEOP difference can be defined as $\\Delta_{\\text{EOP}}(\\tau,\\phi) \\coloneqq |\\Pr(\\hat{Y} = 1 |S =1,Y=1) -  \\Pr(\\hat{Y} = 1 | S = 0,Y=1)|$. Thus, this is equivalent to $\\Delta_{\\text{DP}}(\\tau,\\phi|Y=1)$. Then, following the same proof, we can conclude that $\\Delta_{\\text{EOP}}(\\tau,\\phi) = |\\text{Cov}(\\hat{Y}, S | Y = 1)|/\\text{Var}(S|Y=1)$. That is, the same relationship holds under the additional condition that $Y=1$.\n\nSimilarly, EOD difference can be defined as $\\Delta_{\\text{EOD}}(\\tau,\\phi) \\coloneqq \\max(|\\Pr(\\hat{Y} = 1 |S =1,Y=0) -  \\Pr(\\hat{Y} = 1 | S = 0,Y=0)|, |\\Pr(\\hat{Y} = 1 |S =1,Y=1) -  \\Pr(\\hat{Y} = 1 | S = 0,Y=1)|)$  which is equivalent to $\\max(\\Delta_{\\text{DP}}(\\tau,\\phi|Y=0), \\Delta_{\\text{DP}}(\\tau,\\phi|Y=1))$. It is also equivalent to $\\max(|\\text{Cov}(\\hat{Y}, S | Y = 0)|/\\text{Var}(S|Y=0), |\\text{Cov}(\\hat{Y}, S | Y = 1)|/\\text{Var}(S|Y=1))$.\n\nWe will make sure this is thoroughly discussed in our revision.\n\n---\n\n## Q2: The student-t confidence bound relies on CLT; there is no study on how this affects small per-group sample sizes. The CLT approximation could behave poorly.\nThanks for raising this question. This is a reasonable concern when the data size is extremely small. While student-t assumes normality, there is a study that shows that it is relatively robust to violations of this assumption, even with small sample sizes, as long as the data are not severely skewed or contain extreme outliers [1]. In our experiment, we show that the guarantee is robust to various data sizes (41k to 195k). However, if this assumption is violated, our framework is *flexible to other choices of statistical tools* such as Bootstrap Confidence Intervals, as mentioned in Appendix F for constructing the confidence bounds.\n\nWe will extend the discussions on this assumption in our revision.\n\n---\n\n## Q3: The baselines use another dataset for validation, but FRG uses this dataset for both validation and fairness testing. I think that for a fair comparison, the fairness-test dataset should be picked among the training samples.\nThank you for the suggestion. We agree this is a potential weakness in our original setup. We have now completed this new experiment, where the fairness-test set $D_f$ is created from a 10% split of the training data, while keeping all other settings unchanged. The key finding is that our results are robust to this change. The accuracy and fairness outcomes are nearly identical to our original findings (Figure 2-5). We believe that the main reason for this is that the final unseen test set was used identically and fairly across all methods under the old setup. Since the ultimate measure of performance and fairness generalization is on this test set, our central conclusions about FRG's effectiveness hold. We will update the experiment figures accordingly in our revision. \n\n\n---\n\n## Q4: The pairing part in Sec. 5.2.1. can be explained better. The part where the confidence bound hyperparameter for training, α, can be explained better, is it just the previous $\\hat{U}=\\alpha U$?\nThanks for the suggestions for improving the clarify of our approach.\nRegarding the pairing approach, we essentially want to retrieve $m$ pairs of unbiased estimates for each of $\\Pr(\\hat{Y} = 1|S = 0)$ and $\\Pr(\\hat{Y} = 1|S = 1)$. They can form $m$ unbiased point estimates of $\\Pr(\\hat{Y} = 1|S = 0) - \\Pr(\\hat{Y} = 1|S = 1)$. These point estimates will be used to construct confidence intervals on $\\Pr(\\hat{Y} = 1|S = 0) - \\Pr(\\hat{Y} = 1|S = 1)$ by applying statistical tools such as Student’s t-test. We will break down these steps further to make it more digestible.\n\nYou are correct that $\\hat{U}=\\alpha U$. The hyperparameter $\\alpha$ is used to inflate the high-confidence upper bound $U$ such that the candidate selection is less likely to overfit to $U$, which may result in more NSF. We will clarify this in our manuscript.\n\n---\n\nWe thank you again for your help in improving our manuscript. We will incorporate your other comments in our revision."}, {"review_id": "C84PvKE9uJ", "reviewer": "Reviewer_5EpJ", "summary": "The paper proposes FRG, a framework for fair representational learning that guarantee specific high confidence fairness bounds for any downstream task. The works achieves this by proposing a adversarial inference component and statistic fairness test.", "questions": "Please see the question in the weakness field (included for clarity).", "limitations": "Yes.", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strength\n\n1. The authors addresses a gap in the research field, indicating that existing methods provide empirical or estimates fairness guarantees without formalized proof.\n\n2. The authors' theoretical proof between demographic parity and covariance seems sounds, with reasonable foundation for adversarial inference\n\n3. The author provides sufficiently strong empirical evaluation \n\n## Weakness \n\nAlthough I am not a expert in this field:\n\n1. The authors strong emphasis on demographic parity seems limiting, noting that there exist other popular fairness measurements such as equal opportunity and equalized odds (multiple fairness measurements are often considered in the fairness measure literature for such works). How does this work fair for other fairness measurements?\n\n2. The authors proposes a strong IID assumption of the data. Although the assumption is fair for theoretical study, I am concern on the distribution shift between training and deployment. More empirical test could be provided to address this concern.\n\n3. The authors proposed solution requires a multi-stage pipeline, which could potential be very computational heavy for large and datasets and complex task. How scalable is such a solution?\n\n4. Additionally, how should one consider the thresholds $\\epsilon$ and $\\delta$?", "was_revised": true, "final_justification": "The authors have responded to my queries. I am not an expert in this field and therefore I will retain my assessments.", "rebuttal": "Thank you so much for carefully reviewing our work and appreciating our novelty, the empirical and theoretical results. We address your concern as follows.\n\n---\n\n## Q1: How can this work be extended for other fairness measurements including equal opportunity and equalized odds?\nThis is an insightful question. Indeed, the proposed method can be ***applied to Equal Opportunity (EOP) and equalized odds (EOD) with simple modification***, but it requires that the outcome labels, Y, for the downstream task of concern are available to compute EOP and/or EOD. We will use EOP as an example. $\\Delta_{\\text{EOP}}(\\tau,\\phi) \\coloneqq |\\Pr(\\hat{Y} = 1 |S =1,Y=1) -  \\Pr(\\hat{Y} = 1 | S = 0,Y=1)|$. This is equivalent to $\\Delta_{\\text{DP}}(\\tau,\\phi|Y=1)$. The rest follows, except we only consider the subset of the data where $Y=1$ when constructing the high-confidence upper-bound. Similarly, $\\Delta_{\\text{EOD}}(\\tau,\\phi) = \\max(\\Delta_{\\text{DP}}(\\tau,\\phi|Y=0), \\Delta_{\\text{DP}}(\\tau,\\phi|Y=1))$ which one can also construct the high-confidence upper-bound using our framework by splitting $\\delta$ in half for each of $\\Delta_{\\text{DP}}(\\tau,\\phi|Y=0)$ and $\\Delta_{\\text{DP}}(\\tau,\\phi|Y=1).$\n\nIn the revised manuscript, we will clarify how our approach can be used to constrain EOP and EOD. However, we note that the high-confidence upper bound requires outcome labels, Y, from a specific downstream task, so in this context the guarantee can be applied only to that task, which might not be generalized to arbitrary downstream tasks, as it is the case for the DP (demographic parity). This is a common limitation to existing approaches as well (e.g., [1-2]).\n\n#### [1] Jovanović et al. Fare: Provably fair representation learning with practical certificates. ICML 23.\n#### [2] Song et al. Learning controllable fair representations. AISTATS 19.\n\n---\n\n## Q2: The IID assumption of the data is a concern to the distribution shift between training and deployment.\nWe think this is an insightful question. We assume the data are i.i.d. and we agree it could be a concern to some distribution shift. If the test dataset has a different distribution of $(X,S)$, the guarantee that the representation model is fair with high probability may no longer hold. However, the guarantee is robust to label shifts because the label is not necessary when learning the representation model and constructing the high-confidence upper bounds. If the test dataset has a different distribution of label $Y$ or distribution of $Y$ conditioned on $(X,S)$, the guarantee will still hold.\n\nWe think that addressing different kinds of distribution shifts of input $(X,S)$ is beyond the scope of our work. Future work can study approaches to construct a high-confidence upper bound with the provided knowledge of the distribution shifts. For example, the shift could be bounded, the shift may occur only to $S$ but not to $X$, the shift may be periodic, etc.\n\nWe will include this discussion in our revision.\n\n---\n\n## Q3: The authors proposed solution requires a multi-stage pipeline, which could potential be very computational heavy for large and datasets and complex task. How scalable is such a solution?\nOur method requires additional steps for learning the adversary and for performing the fairness test compared to traditional methods. While the training of the adversary and the fairness test introduce some computational overhead, they are ***very small*** (around 5% of the overall runtime) compared to the training time of the representation model (95% of the runtime). Here is an example for the Income dataset. We train the representation models with 500 epochs across all baselines. The overall runtime of FRG is 330s, which includes training the adversary, representation model, and the fairness test. Training the adversarial model takes 16s (4.8%), the fairness test takes only 0.06s (0.02%), while training the representation takes about 95% of the runtime. Here is a comparison with the baselines: CFAIR takes 303s, ICVAE takes 1021s, LMIFR takes 336s, LAFTR takes 326s, FARE takes 41s (only one call to fit the decision tree). Thus, we think the computation cost is not a concern. In the revised manuscript, we will include a short paragraph clarifying this.\n\n---\n\n## Q4: How should one consider the thresholds $\\epsilon$ and $\\delta$?\nThis is an insightful question. Intuitively, our framework guarantees that any (including adversarial) downstream tasks and models using the representations generated by its learned representation model will have $\\Delta_{\\text{DP}} <= \\epsilon$ with probability at least 1-\\delta. How to choose thresholds $\\epsilon$ and $\\delta$ will vary case by case. If one wants the guarantee to hold with a high probability, one should set a small $\\delta$. If one wants to enforce a strict parity constraint, one should set a small $\\epsilon$.\n\n---\n\nThank you again for reviewing the work, and we will be happy to discuss any further questions you may have."}]

Author rebuttal:

Meta-review: This submission proposes FRG, a framework for fair representation learning with controllable high-confidence guarantees via adversarial inference. The paper received consistently positive ratings from all reviewers who recognized its novel approach to providing statistical guarantees for fairness across arbitrary downstream tasks.

Reviewers initially raised concerns about the optimal adversary assumption, computational overhead, and experimental setup. The authors provided thorough responses including empirical validation of adversary quality, demonstration of minimal computational overhead, and additional experiments with modified data splits showing robust results. The theoretical extensions to other fairness metrics and non-binary attributes further strengthen the work's applicability.

The work addresses an important gap in fair representation learning by providing statistical guarantees rather than empirical estimates, with practical controllability through user-specified thresholds. The theoretical framework is sound, the empirical validation is comprehensive, and the author responses demonstrate thorough engagement with reviewer feedback.

I recommend **ACCEPT**.
Decision: Accept (poster)