Kernel-based Equalized Odds: A Quantification of Accuracy-Fairness Trade-off in Fair Representation Learning
Authors: Yijin Ni
Xiaoming Huo
Venue: NeurIPS 2025 poster ()
Keywords: Fair Representation Learning
Kernel Methods
Equalized Odds
Demographic Parity
Fairness-Accuracy Trade-off
Primary area: theory
TL;DR: We propose a kernel-based equalized statistic to quantify the accuracy-fairness trade-off among independence-, separation-, and calibration-based constraints, identifying the best suited criterion to preserve predictive accuracy.

Abstract: This paper introduces a novel kernel-based formulation of the Equalized Odds (EO) criterion, denoted as $\operatorname{EO}_k$, for fair representation learning (FRL) in supervised settings.
The central goal of FRL is to mitigate discrimination regarding a sensitive attribute $S$ while preserving prediction accuracy for the target variable $Y$. 
Our proposed criterion enables a rigorous and interpretable quantification of three core fairness objectives: independence ($\widehat{Y} \perp S$), 
separation—also known as equalized odds ($\widehat{Y} \perp S \mid Y$), and calibration ($Y \perp S \mid \widehat{Y}$). 
Under both unbiased ($Y \perp S$) and biased ($Y \not \perp S$) conditions, we show that $\operatorname{EO}_k$ satisfies both independence and separation in the former, and uniquely preserves predictive accuracy while lower bounding independence and calibration in the latter, thereby offering a unified analytical characterization of the tradeoffs among these fairness criteria.
We further define the empirical counterpart, $\widehat{\operatorname{EO}}_k$, a kernel-based statistic that can be computed in quadratic time, with linear-time approximations also available.
A concentration inequality for $\widehat{\operatorname{EO}}_k$ is derived, providing performance guarantees and error bounds, which serve as practical certificates of fairness compliance. 
While our focus is on theoretical development, the results lay essential groundwork for principled and provably fair algorithmic design in future empirical studies.

Kernel-based Equalized Odds: A Quantification of Accuracy-Pairness Trade-off in Fair Representation Learning
Yijin Ni
Xiaoming Huo
H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology ymi640gatech. eu
H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology huo@gatech. eu
Abstract
This paper introduces novel kernel-based formulation of the Equalized Odds (EO) criterion, denoted as EOA, for fair representation learning (FRL) in supervised settings. The central goal of FRL to mitigate discrimination regarding sensitive attribute S while preserving prediction accuracy for the target variable Y. Our proposed criterion enables a rigorous and interpretable quantification of three core fairness objectives: independence ( II. -)), separation-also known as equalized odds (Y IL S Y), and calibration (Y TL S Y). Under both unbiased (Y IL S) and biased (Y K.. S) conditions, we show that EO₃ satisfies both independence and separation in the former, and uniquely preserves predictive accuracy while lower bounding independence and calibration in the latter, thereby offering a unified analytical characterization of the tradeoffs among these fairness criteria. We further define the empirical counterpart, EO₃, kernel-base statistic that can be computed in quadratic time, with linear-time approximations also available. concentration
inequality for FO2 is derived, providing performance guarantees and error bounds, which serve as practical certificates of fairness compliance. While our focus on theoretical development, the results lay essential groundwork for principled and provably fair algorithmic design future empirical studies.
Introduction
As machine learning becomes increasingly integrated into social decision-make making (e.g., hiring, lending), ensuring algorithmic fairness has emerged as a critical challenge. Consider an input random variable X (e.g., applicant data), protected attribute S (c.g., gender, race), and a target variable Y (e.g., loan default). A naive approach might exclude S from model training. However, when X and statistically dependent (e.g., due to historical biases in education employment), models trained on X alone can still perpetuate discrimination by leveraging proxy features correlated with S.
Fair Representation Learning. Fair Representation Learning (FRL) addresses this issue by con- structing an intermediate representation := f(X) that preserves task-relevant information for predicting the target attribute Y while mitigating biases tied to the sensitive attribute S. Consider binary classification task with target Y (0, 1} and predictor y ~ Bernoulli(h (Z)). Existing ap- proaches to evaluating discrimination in FRI. primarily fall into three categories, each corresponding different statistical independence criterion:
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Independence (Y TT S) seeks to eliminate the dependence of the protected attribute S from the predictor, typically measured by Demographic Parity (DP, Dwork et [012) that is,
Pr(Y - =0]-
(1)
Separation ( TT S Y) requires equal prediction performance conditioned on the true label Y, instantiated the by Equalized Odds (EO, Hardt al. (0166) constraint, i.e.,
Pr(P = -111 Y = y. S. = 0) = Pr(P = Y = v, = =), 1), y E (0.
(2)
Calibration (Y TT S Y. Kleinberg 2018 ensures the scoring function h(Z) is equally
meaningful across groups, demanding
Pr(Y = l(Z)) 1,5 Pr(Y (()) -
which is equivalent to Y quantification of the calibration constraint, denoted DC Z,Y, for predictor h, is given as follows:
(Barocas al. 2023 Proposed in Shen et al. [2022]
/ P = y, = =) Pr(Y -
E ME(D,1)
y, (() = 1 5= 0)
Conflicting Fairness Objectives. Simultaneously satisfying independence, separation, and calibra- tion is fundamentally infeasible under realistic conditions, individually well-justified. As shown in Kleinberg (0018). these criteria can only be satisfied together in pathological cases: either when the target variable Y is independent of the sensitive attribute S, or when the predictor achieves perfect accuracy, i.e., Pr(EE[ Z E (0. 13) = 1. Such conditions rarely encountered in practice, especially in FRI., where representations downstream tasks with unknown objectives. Consequently, practitioners are forced to navigate trade- offs between fairness definitions, often lacking clear guidance on the balance between competing objectives (Chouldechoval (0016). Kleinberg (2018). Identifying and characterizing these trade-off's thus critical step toward advancing the development of fair and effective representations.
though each fairness constraint is
often transferred to
Accuracy Costs of Fairness. Beyond their inherent incompatibility. faimess constraints can impose significant costs predictive accuracy, presenting fundamental trade-off in FRL. The objective in FRL is to construct representations that preserve task-relevan information for downstream pre- diction while suppressing dependencies sensitive attributes. However, different fairness notions operationalize this objective in conflicting ways, often at the expense of accuracy. For instance, enforcing independence (Ý IL S) removes all information correlated with the sensitive attribute S, including predictive features, thereby excluding the optimal classifier y* that achieves perfect accuracy (Pr(i"* Y) 1, Hardt al. 2016)) in cases where Y V4. S. In contrast, the separation (EO) criteria address this limitation by conditioning fairness on the true label Y, enabling alignment with Y Yet, such criteria may violate calibration, lcading to systematic discrepancies in predicted probabilities across groups with the same outcome. These competing demands underscore the need for principled and quantitative framework to assess how different faimess constraints interact and affect predictive performance a gap this work aims to fill.
1.1 Main Contribution: A Quantification of Faiuuess-Accuracy Trade-off's
To systematically navigate the trade-offs between incompatible fairness constraints and their im- plications for predictive accuracy, we propose a kernel-based statistic, i.c.. EO₃, that quantifies these tensions within a unified framework. Our approach formalizes the divergence between con- ditional distributions associated with fairness notions such as independence, separation (EO), and calibration, allowing for precise measurement of how given representation deviates from each criterion. Crucially, our statistic also reflects the extent which fairness enforcement may distort task-relevan information, thereby linking fairesss violations to potential accuracy degradation in downstream tasks. This dual role diaaniigg fairness violations while accounting for predictive utility distinguisss our approach from existing methods. In what follows, we formally define the F.2, statistic, demonstrate its equivalence to a Maximum Mean Diserepancy (MMD) between reweighted group distributions, and analyze its thcoretical properties- properties-bighlihhiin its expressiveness,

---

its ability to quantify fairness fairness-cccuracy accuracy trade-offss under dataset bias, and its practical computability, We also derive a generalization bound for its empirical counterpart and show how it can serve as provable certificate for fairness-awan representation learning.
Technical Overview of F.Ox- Specifically, F.O, quantifies the maximum violation of the EO constraint Y TT S across predictors h Z + [0. 1] derived from an affine map of the unit ball in reproducing kernel Hilbert space (RKHS). Let Z. := Z S = s. and Py a = Pr(Y y S = s). Given reproducing kernel k 2 x Z + and its associated RKHS Hx: the EO2 metric is defined as the supremum of class- class-weighted expectation differences within the unit ball of HA:
FO, = sup [| [|ills
Bl 7 V + Pijo E 1y Zo 71) Y = 1]|
(4)
where || 1l,H, refers to the norm in RKHS HA. induced from kernel k. Let 2 = 2 =
The above definition is equivalent the MMD considering random variables {Pojo Zg +1100,))==0 As detailed in Lemma 2.2, an affine map of the unit ball in the RKHS formulates feasible set, i.c.
H. of predictors 2 + 0, 1J for the prediction of target variable Y. In other words, EO₃, measures the worst-case deviation from the weighted EO constraint across all admissible predictors E H.
Expressiveness of Unit Ball in RKHS. The affine-transfone transformed RKHS unit ball can be considered as a feasible set for the downstream task that ensures expressiveness for capturing Y E {0, 1 -eddeenne disparities, from the following two aspects:
By the representer theorem (Schölkopf et al. 2001 D. an RKHS contains hypothesis classes of kernel Support Vector Machines (SVMs), Gaussian processes, and PCA, which are standard tools in the machine learning context.
Pratical Coverage:
Universal Approximation With co-univeral kernels (e.g., Gaussian, Laplacian), the RKHS Ha densely spans the space of continuous functions vanishing at infinity (Sriperumbudur et al. (2010a]) That is. the elements in H₂ can approximate any bounded continuous predictor, including neural networks, to arbitrary precision.
Formalizing Fairness Trade-offs. Unlike existing frameworks that require heuristic selection among mutually incompatible criteria criteria-independdene (T). EO (2). or calibration (3) --our context-adaptive
EO2 automatically adjusts to the underlying dependency between Y and S. Specifically, given bounded reproducing kernel, i.e., sup, k(2, 2) S v. For simplicity, let v = 1/4. In distinct Y-S dependency structures, we have
Y TT S: When no inherent bias exists (Y independent of S). the minimization of EO2 enforces both the independence (1) and separation (EO) constraints @ Formally, considering the feasible set, i.e., H. of predictors for the downstream task, we have (Theorem 2.5
sup Dh Z,Y.S) EO2 (2,, bER
where H is derived from the affine image of the unit ball in an RKHS Hd (Lemma 2.2 To elaborate, (5) demonstrates that in bias-free regimes (Y IL S), the minimization of EO; enforces both the EO (2) and the independence constraints ① universally, Yh E H. Here, H. is the feasible set for predictors h: 2 + [0, 1] implementable in downstream tasks.
Y 1. S: In the case of data bias (Y-S dependency), EO₃ permits a quantifiable accuracy-fairness trade-off: under mild constraints, there exists constant c, such that (Theorem 2.5 2.6
csup DC 2, S) 2 sup (h; 2, S) 2 Pojo Puja [8 EO NEW
(6)
beet
This inequality illustrates the incompatibility of fairness criteria: when a representation 2 nearly satisfies the EO constraint (EO,, x 0) and retains nontrivial predictive power (3 > 0), both independence (DP) and calibration (DC) constraints must necessarily be violated. Here, the coefficient |Pojo Poju is quantification of the inherent dataset bias, and / represents the optimal balanced accuracy achievable under 5 = (Lemma 2.4
1 (Pr(Ý = 0 = 0, 1) Pr(y = = 1)) sup - 2
1 1+
kEH
value of / > 0 implies that supports better-than-random prediction. Moreover, enforcing the calibration constraint 3 for all downstream predictors h E H. entails satisfying independence, thus
3

---

imposing a stricter condition than independence alone. This makes calibration particularly costly in terms of preserving task-relevant signal. Lastly, since the Bayes-optimal classifier Y-hhhich achieves perfect accuracy, i.e., Pr(Y* Y) I-satifiies the EO constraint but violates the DP constraint (T) HHardt et al. 2016)), , the DP (and hence calibration) constraints are fundamentally at odds with predictive accuracy in biased settings. In contrast, EO, as quantified by F.O,, statistic, accommodates nontrivial predictive performance while explicitly characterizing faimess-accuracy trade-offs, making it the most appropriate constraint in such contexts.
Scalable Estimation via MMD. Our FO;; statistic admits a closed- form empirical estimator based on the MMD framework, enabling efficient evaluation. More specifically, let 2(*) : Poju + Pijo Z3 denote the Y -reweighted mixture distribution for group = s, where E {0. 1}. Given ng and nı (1) i..d. samples {=,²) |==1 and {23 Ti=1 from Z and 2 respectively, the empirical estimator for
EO₃ is given as follows:
Σ t 1z k(z
(0) Ede k(zi .2
(0) 2 2 Ro k(2, 2
22
EO
nn
1i (n)
This formulation enables direct integration with Stochastic Gradient Descent (SGD, Briol et al. 2019). Rychener et al. (0222) and is evaluable in O(n²) (Gretton et al. (2012) or even O(n) time (Zhao and Meng 20155] where n : ni n refers to the sample size of for the pairs (X, S, Y). In practice, can implement this i..dd sampling requirement via stratified bootstrap resampling.
Generalization Guarantees and Domain Adaptation. Our empirical estimator EO2 equipped with hyperparameter-free convergence when served as a penalty term of the objective function in FRL, ensuring that the employment of EO2 can help us justify the achievement for EO2, Specifically, building upon the uniform MMD error bound from Ni and Huo (2024). we prove a non-asymptotic error bound that holds uniformly over penalty coefficients and optimization trajectories, guaranteeing convergence of the empirical estimator to the population-les As a representative example, suppose the encoders f E F mapping from the input X to the representation Z are composed of feed-forward neural networks, V6 E
FOO, constraint as sample size increases.
(0, 1), we have (Theorem
2.10
(v log(d) + log(6 -1
Pr
sup SEF
EO
k - EO? So
2 1115 5,
n10 +11
where Ao. 12 refers to the sample sizes for 2 and 2(1), respectively, d refers to the input dimension. The logarithmic relationship between the deviation bound and the input dimension underscores EO's computational edge
traditional Integral Probability Metrics (IPMs) in tigh-diiensional tasks. Moreover, in cases where the input X is perturbed via a function transformation g(X). suppose fo g E F, VJ, the above upper bound remains valid, revealing the domain adaptation property of the proposed metric F.OR-
1.2 Related Works: The Limits of Achieving Multiple Group Fairness
To address the ambiguity in selecting fairness criterion, recent works have proposed metries that aim to approximate multiple faimesss notions simultancously. For example, it proposed in SShen et al. 2022 that the minimization through the following opposing objectives leads to the joint approximation of group fairness constraints embedded in independence separation (2) and
calibration 3 That is,
max (axxddr(Zzn - (z)
where Z. = 2 S. 2 = Z Y = y. drv refers to the Total Variation Distance (TVD). Similarly, Jang et al. 2024 design metric lower bounded by both DP (T) and EO violations.
However, these approaches conflict with fundamental impossibility results (Kleinberg 2018)) ) which show that independence, separation, and calibration cannot be satisfied simultaneously except in degenerate cases (e.g., Y S or perfect prediction). In particular, the formulation in Shen et al. [2022] assumes that the involved conflicting TVD terms, i.e., drv Zoo Z1) and drv Z can be simultaneously optimized, despite their inherent trade-off under distributional bias (Y / S). where the composite metric can never be minimized to zero. Similarly, the metric proposed in Jang

---

et a.. 2024] fails to account for the structural incompatibility between the DP ① and EO 2 metric biased settings (Y Tf S). As shown in (6) both criteria can only be simultaneously satisfied when the target variable becomes unidentifiable in subgroup S = 1. Consequently, to preserve the prediction accuracy, the lower bound of the proposed metric determined by the degree DP, which remains strictly positive under Y V. S.
In contrast, our method acknowledges this conflict and formalizes the trade-off's using a kernel-based statistic, EO2- It can be observed that our metric EO2 preserves the Bayes-optimal predictor in biased regimes and approximates both independence and EO in the unbiased case, providing principled approach to fairness constraint selection based on task-specific trade-offs.
1.3 Preference of MMD in FRL
Adversarial Training Structure in FRL. Adversarial training is an approach widely used FRL
(Beutel et al.] (2017). Madras et al. (2018). Zhao al. [219]] Kim and Cho (2020) considering the accuracy and fairness trade-off. Let an encoder f + map features X to representation
Z = f(X). J. A task head h Z + [o, 1] predicts the target attribute ~ Bernoullihh( (Z)))) while
discriminator d [0, 1] tries to recover the protected attribute from Z. The resulting min-max problem is
min max E[Lr(MZ2)))) AF(Cs(d(2), (AAC((())))) f. d
(8)
where Ly (e.g., cross-entropy) encourages predictive accuracy, Ls (e.g., logistic loss) penalizes information about S in Z, and À > controls the trade-off. At equilibrium, Z approximately independent of S, thereby approaching DP, i... h(Z) I. S. for any downstream prediction model h.
For comprehensive survey of FRL approaches, readers are referred to toCrrrato al., (2024).
Reducing Computation via IPM penalty. Replacing the adversarial maximization step in (8) with
an Integral Probability Metric (IPM) regularizer has gained wide attention in recent studies (Mary iet al. 2219), Kim et al. [2022]. Deka and Sutherland
(2023), 3 Kong et al.) (2025) ). Examples include
TVD (Shen al. 20222 ), MMD (Oneto al. [2020] Rychener et [2022]. Deka and Sutherland 2023 )) and the Wasserstein Distance (Gordaliza et al. [2019]). Notably, an IPM is defined as
supremum over specified function class F of real-valued functions. Specifically, given a pair of
random variables Zo and Z1 embedded in set 2, we have
dz(Za, 71) = sup [B[S(Z))] -[[(2))]] fer
which collapses the inner optimization into a single, closed-form loss term, climinating the full min-max game and reducing computational overhead. This substitution also yields tighter theoretical guarantees for DP (Kong et al. (2025)).
From TVD to MMD: A Practical Shift in Fairness Regularization. For binary classifica- tion, i.e., E (0, TVD the theoretically ideal IPM for enforcing demographic parity. Its specified function class Fry == (/ Z + 1]} is affine transformation of the set Ho..1 = {h:
(0, 1]] that comprises all probabilistic classifiers for the event Y 1. Despite its theoretical appeal, TVD suffers from critical limitations in practice. Most notably, its gradients vanish when the supports of the conditional distributions do not overlap-stalling optimization in high-dimensional imbalanced settings. This makes TVD ill-suited for gradient-based training in deep representation learning frameworks. These limitations have led to the widespread adoption of MMD computationally efficient and stable alternative.
2 Main Theoretical Results
In the following. we first provide the formal definition of our metric EO; and its technical explanation in Section 2.1 Given the formal definition, we discuss the relationships between our metric and the independence and calibration constraints Section 2.2 showing that both the biased (Y JLI S) and unbiased (Y M. S) cases, our metric is preferred choice. Regarding the algorithmic implementation, we provide the empirical estimator of our metric and discuss convergence rate when served as penalty term in the objective function in Section 2.3
5

---

2.1 Kernel-based EO Constraint
Given a characteristic reproducing kernel (Definition 4.2), from which the derived kernel mean
embeddings are injective, the EO constraint ( S Y. in the binary classification setting equivalent to the following condition:
=
y E {0.1}.
where pa == [ Z stands for the kernel mean embedding of the conditional representation Zy 8, y E [0. the following, instead computing the MMD for both the (f0 1و) and (#o- p1) pairs, consider the difference between the following weighted summation conditioned on Y and Y = 1, i.e.
Pojo - + P1
for 0, 1, where Py Pr(Y v/s = 8), s, E {0, 1}. The formal definition is given as follows:
Definition 2.1 (Weighted Equalized Odds via MMD). Let Hy be RKHS containing functions mapping from to I, and x Z be the corresponding reproducing kernel. Suppose is
characteristic as defined in Definition 4.3 we quantify the separation constraint, i.e., Y 11. $ S|Y, through the following expression:
E = 7A 1o +110 70. Po. 7i + 21)
2.2 Accuracy- Fairnes Trade-off
We start with the statement that the value of MMD can be considered as the supremum of the balanced accuracy for binary classification problem. In the following, we provide the involved function class, built from an affine map of the unit ball in an RKHS.
Lemma 2.2. Let H. be an RKHS containing functions mapping from Z to R. and k Z 2 be the corresponding reproducing kernel. Suppose sup, k(2, 2) S v. Let Ho. = {h: 2 [0, be the set containing all possible classifiers, H = [h ln(2) (hx 1)/2, 1 S 1112/ we have H. S Hjo.1]-
Proof of the above lemma is given Appendix 4.2
The formal definition of the balanced accuracy for binary classification problem is given follows: Definition 2.3 (Balanced Accuracy). Given an input random variable X E X and a binary target attribute Y E {0, 1}. Ler γ ~ Bernoulli(h()) be the prediction derived based on X, where X + [0, 1). The Balanced Accuracy (BA) of the predictor is measured by the following equation:
BA = (Pr(
= =
Considering the aforementioned function set, the following lemma provides the relationship between the value of MMD and the optimal balanced accuracy.
Lemma 2.4 (MMD and Optimal Balanced Accuracy). Let H. be an RKHS containing functions mapping from Z to R. and k Z x Z R be the corresponding reproducing kernel. Suppose sup, k(2, 2) S V, let 7 : {h h(2) = (hx + 1)/2, Il S -- -1/1/ Given a representation Z embedded in Z. sensitive attribute S {0, 1}, and a target attribute Y {0, 1). Then, the MMD between the conditional representation Z corresponds to the optimal balanced accuracy with respect the classifiers embedded in G. More specifically, have
Suppose "n (Zo Z1) S a, then
sup (A 2,5) 2 1/ 1/2 KEW
2. Suppose 7n (70, (7) 2 B, then
sup hh; Z,Y) 2+ 1-12-112 1/2
2:2-10011
4

---

Here, a 2 0 and B S //
Proof of the above lemma is referred to Appendix 4.3
Observed from the above lemma, it can be concluded that (i) The minimization of MMD over representation Z conditioned on the sensitive attribute S enforces the statistical indistinguishabiliy of predictions Y ~ Bernoulli(h(2) across sensitive groups, as quantified by the maximal predictive leakage of S under optimal balanced accuracy; (ii) To certify non-trivial predictive performance in downstream tasks, the MMD over representations Z conditioned on the target attribute Y must be bounded below by a positive constant. This guarantees the existence of predictor h + [o, 1] whose induced prediction y ~ (ernoulli(h(2)) can surpass random guessing.
In the following, we analyze the relationship between the independence constraint ①1 and the metric EO,, that represents the EO constraint (2) considering the supremum over the possible predictors h E H. where H is the feasible set induced by the unit ball in RKHS as given in Lemma 2.2 Combining the following result and the above observation regarding the relationship between MMD and prediction accuracy, we conclude that the metric EO2 is preferred choice considering the fairness accuraay trade-off.
Theorem 2.5 (Independence and EO). Let Hy be an RKHS containing functions mapping from Z to I. and k Z Z + be the corresponding reproducing kernel. Suppose sup, k(z,z) S v. Let H (h] h(=) = (z)(2) + 1).2. [ H. S v 1/222,, DP be given as ① we have
sup DP (h: Z.Y. S) (2v2/23- mo Zu. Z1).
(10)
MEW
Moreover, denote Pr(Y S s) as Pyls- Let EO be the weighted equalized odds constraint Suppose Y IL S. we have
given in Definition 2.7
sup Dh Z, S) (2 EOx (Z,
(11)
hEHl
In cases where 1 S, we have
sup (P; (,,, 2 (2)-1 '|Pojo Pojo (2), 21) - EO,(Z,Y,
(12)
REH
Proof of the above theorem referred to Appendix
This result underscores the inherent incompatibllity between independence (DP) and separation (EO) constraints when Y JL S. Formally, if an optimization procedure yields EO,, x the following lower bound holds:
sup DP 2 NeW
(2v)- 'Pojo
Poj 18,
where B := 7h (Z) Zi). Based on Lemma 2.4 7 (Z). Z quantifies the maximum achievable balanced accuracy for predicting Y given S
To ensure non-trivial predictive performance, i.e. the balanced accuracy is greater than 1/2, we require 3 > O. which strictly prohibits perfect independence, i.e., DP proposed in Hardt et al. 2016), , KKeinberg [018]_ In conclusion, we have (i) the minimization of the metric F.2, achieves both the independence and EO constraint simultaneously in the unbiased setting where Y IL S; (ii) the minimization of E'O, is preferred in the biased setting Y Jf S to ensure the prediction accuracy regarding the target attribute Y.
the biased setting (Y V4. S), aligning with the impossibility result
Theorem 2.6 (Independence and Calibration). Given characteristic reproducing kernels k. R x RIZZ + R. k [0. 1] x [0, 1] + R, and k(o.1) {0, 13 x 10, R. Let H. Hjo.1), and ((,1)) be the corresponding RKHSs. Let H @ ((u11) be the tensor product of space H1a and Hqu.1). equipped with a reproducing kernel function kjo. @ k(o,,), where ljo. @ k(o,1) 9). (u. v/)) ,,,,, u' (o))( n"), Yu, u' E [0, 1]. Vy. 3 {0, 13.
Suppose sup, k(z, 2) S v, sup,, Aoo. u) S Mo.1]. sup, (...,)(2.v)) S P(o.I). and id E Ho.1). where id the identity function. Let H. (h) h(2)) (ha(z) 1)/2, IhallH Sv 21-1/23. We have sup OC(h,YYS) heg
heg 1/2 1/2 ) sup (0. ((XA(Z)) OX, (v [0.1] (0.1))
1/2 1/2 id ( ) 4v [0.1] (0.1)
sup (h: 2, S,S
kER
7

---

Proof of the above theorem is referred to Appendix 4.5
As observed from the above theorem, the calibration constraint (DC) is linearly lower bounded by the independence (DP) constraint. Consequently, in biased regimes (Y M S), achieving calibration
requires suppressing DP below problem-dependent threshold. This creates two-fold conflict:
1. Accuracy-Fairnes, Paradox: An optimal predictor Y such that Pr(Y =) 1, violates the independence constraint, i.e., DP > 0, leading to the violation for DC constraint.
Violation of the EO constraint: Recall the contradiction between the EO and independence constraint as given in Theorem 2.5 In biased circumstance (Y J. S), requiring DC = 0 leads to lower bound for the EO constraint measured by EO,, corresponding to the fact that given the target attribute Y, the prediction made by the model relies on the sensitive attribute S.
Thus, in the biased setting Y JL S, EO emerges the preferred fairness criterion over both DP and DC.
2.3 Optimization Framework with Convergence Guarantees
Utilizing the aforementioned metrie EO₃ regularization constraint, formulate the supervised FRL problem as follows:
arg min (h AEOg s.t. Z f(X), b.f
(13)
where Soup is given supervised risk such the cross-entropy in this binary classification setting, EO₃ refers to the empirical estimate of EO2 as given in (7). and the multiplier 2 is a hyperpa- rameter controlling the relative magnitude of the fairness constraint. Here, to circumvent gradient -
instability caused by the square root function contained in the expression of EO employ EO₃ in the constraint instead.
To validate the empirical estimator EO2's 's efficacy as penalty term, we provide a uniform deviation bound between EO2 and EO2 under the following assumptions. First, regarding the encoder set F containing mappings from X' to Z to establish a representation Z, we require that its covering number is finite.
Assumption 2.7. Let F. be a finction set mapping from X. to 2, where Z E Rdd Ve > 0, suppose the covering number Ne; [loa) oo, where -1loo is a function norm defined as follows:
Il == inf ( sup If(x)) (u sc]
ZEX
The covering number Ne;; ||. II) is defined as the minimum cardinality of set Fe. such that df F, there exists a function Je E Fr, such that [[ - S.
Second, regarding the reproducing kernel involved in the establishment of the empirical estimator, we assume it is bounded and Lipsehitz.
Assumption 2.8. Let H be RKHS containing functions mapping from 2 to R. and k: 2 2 R be the corresponding reproducing kernel. Suppose the reproducing kernel ls is built under the following regularity conditions:
(Bounded). 3v > 0, s.t., sup k(2,2) Sv.
(Lipschitz). 31 > O, s.l., Vz E 2, the function k(.,2) E H is I-Lisschitz.
In the following, we provide the definition of Gaussian complexity, which will be a quantification considered in the deviation bound.
Definition 2.9 (Gaussian Complexity). The Gaussian complexity of set T C R is defined as follows:
G, (T) = Ee sup tET
Σ
Eili
(14)
where t "t.,..,,tt)? ltd. AO 1), Vi.
8

---

Based on Assumption 2.7 and 2.8 the technical statement for the uniform deviation bound is detailed as follows:
Theorem 2.10 (Uniform Concentration Inequality of MMD, LiMD,,Niaa and Huo 2024)). Given encoder
set F containing mappings from X' to 2, where 2 C Rd and Z = f(X) given a specified encoder
I J REF. F. Let J(X) = (oooo(()) + P1)oJ(())s denote the Y -reweighted mixture distribution
for group S where {0, Given no and nı ii.d samples f(X)") (0)
={((x)) ]==1
and f(X) (1) = (f(x.) (2) jmn from F(X) and f(x)")) respectively. Denote
no + n1
.PO no/n1, and p1 :- -n//n n//n. Given a reproducing kernel k. Z Z + R, where 2 E RR
Let (nX)F(X) be the empirical Gaussian complexity defined in (14) regarding the F(X)
((f(11) ..... (IIna) fF(O) have
...... f(In.) )0). 45 (0, 1), with probability at least 6, we
2 (fx()( (XX))(X)
sup FEF
log(2/0) 2ml max
1+ Po -1 1 PT
< 8y max (Po
PI ,i
[F)))
T1
7
Po
P1
Notably, the error bound established in the above theorem relies on the Gaussian complexity of the involved encoder set, whose computation involved supremum with respect to f F. In the following, we provide an error bound for the empirical estimator we obtained in (13). As a representative example, we establish the deviation bounds for neural network scenario as discussed in Proposition 4.7
Corollary 2.11 (Error Bounds for Empirical MMD). Let F be a function set mapping from to 2, where Z C Rdd Let f be the empirical estimator obtained in the optimization problem (13).
(0)
corresponding the representation Z (X) and its data matrices fi)X) and fü (X)
as defined in Theorem 2.10 Under the Assumption 2.8 there exist constants C2 Cz. such that v5 E (0, 1), with probability at least 1 5, have
(O(( S BO, E + C2y
In(2/0)
Suppose F is set of feed-forware neural networks given in Proposition probability at least 8, we have
4.7 v5 E (0, 1), with
(O((((X)) SEO + O (n-1/2
1/2 (1+ vln(2/6)))
Based on the above result, suppose EO (x(x)) S in the feed-forward neural network scenario, then v5 (0, 1), with probability at least 1 8, its expected value, i.e., the EO, metric, can be controlled
by 2 + O
(ll(2/))) confirming the convergence rate and the efficacy of the n 11/ 1/2 (1+
empirical estimator FO2 when adopted as a penalty term in FRI.
3 Conclusion
We present a kernel-based statistic, EOx, that quantifies the trade-off's between incompatible fairness constraints and predictive accuracy in representation lcarning. Unlike prior work that attempts to approximate multiple fairness notions simultaneously, our approach acknowledges their inherent conflict and provides principled way to measure and navigate it. Our metric EO; admits scalable empirical estimator, recovers DP (Independence, Equation (T) and EO (Separation, Equation (2) simultaneously in unbiased settings, and serves as the one that preserves the Bayes-optimal predictor under bias setting when compared to DP and DC (Calibration, Equation 3 metrics. This framework offers a practical and theoretically grounded tool for faimesss constraint selection in real-world applications. Our current work is theoretical. However, it lays the foundation for future empirical studies.

---

References
S. Barocas, M. Hardt, and A. Narayanan. Fairness and machine learning: Limitations and opportuni- fies. MIT press, 2023.
A. Beutel, J. Chen, Z. Zhao, and E. H. Chi. Data decisions and theoretical implications when adversarially learning fair representations. arXiv preprint arXiv: 2017.
F.-X Briol, A. Barp, A. B. Duncan, and M. Girolami. Statistical inference for generative models with maximum mean discrepancy. arXiv preprint arXiv:/906.055 2019.
M. Cerrato, M. Köppel, P. Wolf, and S. Kramer. 10 years of fair representations: Challenges and opportunities. CoRR, 2024.
A. Chatterjee and Bhattacharya. Boosting the power of kernel two-sample tests. Biometrika, 112())aaae0448 2025.
A. Chouldechova. Fair prediction with disparate impact: study of bias in recidivism prediction instruments. big data 5, 2 (2017), 153-163, 2016.
N. Deka and D. J. Sutherland. MMD-b-fair: Learning fair representations with statistical testing. In International Conference on Artificial Intelligence and Statistics, pages 9564-9576. PMLR, 2023.
C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226, 2012.
P. Gordaliza, E. Del Barrio, G. Fabrice, and J.-M. Loubes. Obtaining fairness using optimal transport theory. In International conference on machine learning, pages 2357-2365. PMLR, 2019.
A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
M. Hardt, E. Price, and N. Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
T. Jang, H. Gao, P. Shi, and X. Wang. Achieving fairness through separability: a unified framework for fair representation learning. In International Conference Artificial Intelligence and Statistics, pages 28-36. PMLR, 2024.
D. Kim, K. Kim, Kong, I. Ohn, and Y. Kim. Learning fair representation with a parametric integral probability metric. In International Conference on Machine Learning, pages 11074-11 PMIR, 2022.
J.-Y. Kim and S.-B. Cho. Fair representation for safe artificial intelligence via adversarial learning of unbiased information bottleneck. In SafeAI@ AAAI, pages 105-112, 2020.
J. Kleinberg. Inherent trade-offs algorithmic faimesss. In Abstracts of the 2018 ACM International Conference Measurement and Modeling of Computer Systems, pages 40-40, 2018.
I. Kong. K. Kim, and Y. Kim. Fair representation learning for continuous sensitive attributes using expectation of integral probability metrics. IEEE Transactions on Patter Analysis and Machine Intelligence, 2025.
D. Madras, E. Creager, T. Pitassi, and R. Zemel. Learning adversarially fair and transferable representations. In International Conference on Machine Learning, pages 3384-3393. PMLR, 2018.
J. Mary, C. Calauzenes, and N. El Karoui. Fairness-aware learning for continuous attributes and treatments. In International conference machine learning, pages 4382-4391. PMLR, 2019.
Y. and Huo. concentration inequality for maximum mean discrepancy (mmd)- based statistics and its application in generative models. arXiv preprint 4455, 2024.
10

---

L. Oneto, M. Donini, G. Luise, C. Ciliberto, A. Maurer, and M. Pontil. Exploiting MMD and sinkhorn divergences for fair and transferable representation learning. Advances Neural Information Processing Systems,
2020.
Y. Rychener, B. Taskesen, and D. Kuhn. Metrizing faimess.. arXiv preprint arXiv:2205. 2022.
B. Schölkopf, R. Herbrich, and A. Smola. A generalized representer theorem. In International conference on computational learning theory, pages 416 166466. Springer, 2001.
G. Shen. Complexity of feed-forward neural networks from the perspective of functional equivalence. arXiv preprint arXiv:2305. //417, 2023.
X. Shen, Y. Wong, and M. Kankanballi. Fair representation: Guaranteeing approximate multiple group faimess for unknown tasks. IEEE transactions on pattern analysis and machine intelligence, 45(1):525-555 538, 2022.
B. Sriperumbudur, K. Fukumizu, and G. Lanckriet. On the relation between universality, characteristic kernels and rkhs embedding of measures. Y. W. Teh and M. Titterington, editors, Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pages 773-780, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010a. PMLR. URL httpsttp::// htttps://pproeeednggs httppput//tppppp/oeeeeedii html
mlr Slllr.preeavvve sr http///rrppeuuuuuu11oo//o
B. K. Sriperumbudur, A. Gretton, K. Fukumizu, B. Schölkopf, and G. R. Lanckriet. Hilbert space embeddings and metrics on probability measures. The Journal of Machine Learning Research, 11: 1517-1561, 2010b.
B. K. Sriperumbudur, K. Fukumizu, and G. R. Lanckriet. Universality, characteristic kernels and rkhs embedding of measures. Journal of Machine Learning Research, 12(7), 2011.
7. Szabó and B. K. Sriperumbudur. Characteristic and universal tensor product kernels. Journal of Machine Learning Research, 18(233):1 2018.
H. Zhao, A. Coston, T. Adel, and G. J. Gordon. Conditional learning of fair representations. arXiv preprint
2019.
Zhao and Meng. Fastmmd: Ensemble of circular discrepancy for efficient two-sample test. Neural computation, 2745):134-1132, 2015.
4 Appendix
In the appendix, we will first provide the preliminaries prepare for the proofs we will discuss. More specifically, we first provide Table I to give an overview of formal definitions of existing quantifications for fairness constraints. Then, we provide the formal definition of MMD and RKHS, and discuss the relationship between MMD and TVD.
Afterwards, we provide the proofs for Lemma 2.2 2.4 Theorem 2.5 2.6 and 4.5
Finally, we present the concentration inequality of Gaussian complexity and its upper bound for neural networks supplementary material for our established error bounds.
To begin with, Table provides a quantification of the aforementioned fairness constraints in a binary classification setting, i.e., Y E {0, 1}.
4.1 Preliminary: RKHS and MMD
We review the basic idea behind MMD, which is quantify the discrepancy between the two distributions P and Q in terms of the largest difference in expectation between f(X) and fY), for X P and Y ~ Q, over functions / the unit ball a reproducing kernel Hilbert space (RKHS) defined on X. This is called the maximum mean discrepancy (MMD) between distributions P and Q, which can be conveniently estimated from the data terms of the pairwise kernel dissimilarities. For characteristic kernels, useful property of the MMD is that it takes value zero if and only if
11

---

Table 1: Existing fairnsss notions in a binary classification task [Shen et al. 2022 Table 1]. Y (ernoull((h(2)), Y, and S stand for empirical predictor, true label, and sensitive attribute, respectively.
Category
Definition
99)
DOpp(P, DR(P. DOdds(Y, SY
9 P S
DPC14, Y,8)
Eicoo.y [Pr(a_/PP((>> [Px(Y 1,M(2) ( Pryy (2)) 0)]
Y JL S
DNC(k, Y,5)=
1 Eicoo =, = = PP(Y = 0 h() = $
DC Y.S)=
(DPCI,, Y.5) DNC(A, Y.S))
distributions P and Q are the same. MMD has been used boost the power of two-sample tests Chatterjee and Bhattacharyal [2025]. We provide the formal definitions of RKHS and MMD, based on which our metric EO₃ is built.
Definition 4.1 (Reproducing Kernel Hilbert Space; RKHS). A Hilbert space, H. containing functions mapping from set X' is called Reproducing Kernel Hilbert Space (RKHS) if. Va E X, there exists a function urz E H. such that f H, we have
(S, f(x),
where (s, tH is the inner product in space H. The reproducing kernel k: X X' + R of is defined as follows:
k(x, v) = (P2x, Puy Var E X'.
Notably, given pair of random vectors, MMD reflects the RKHS norm between the kernel mean embeddings of the involved random vectors, that is,
Definition 4.2 (Kernel Mean Embedding, Sriperumbudur et al. 2011 2390). Let Hy an RKHS containing functions mapping from X to It, and k X x R. be the corresponding reproducing kernel. Given the set of all Borel probability measures defined on the topological space X, a measurable and bounded kernel, k, is said to be characteristic the following mapping is injective:
PHYps == k(.x))P(a.)
Here, μp E H. is called the kernel mean embedding of distribution P.
Definition 4.3 (Maximum Mean Discrepancy; MMD, Gretton al. 22012 Lemma 4). Let X and Y be random vectors taking values in X. Given reproducing kernel k X X I. the Maximum Mean Discrepancy (MMD) between and Y is defined as the Integral Probability Metric (IPM) induced by the unit ball of the associated reproducing kernel Hilbert space H. Formally.
MMD.,Gretton
(X, = sup 11
[E] (E)(()]],
where || 11 denotes the norm in H. Equivalently, let μx == E[k(, X)] and by = [B(k(,, Y)] be the kernel mean embeddings of X and Y, respectively. We have
Y) = ||xx - py
In cases where is a characteristic kernel as defined in Definition 4.2 7k (x,X, Y) if and only if the involved probability distributions are the same.
Theorem 4.4 (Upper bound of "/k via TVD, /riperumbudur et al. 2010b ). Assume sup, k(æ, x) S Dc, where k is measurable M. Then for any probability metrics P and embedded in set M. let X and ~ Q, we have
(X, Y) S 2//vdVV (xddy(XXY)) (X,Y),
where dry denotes the TVD.
12

---

4.2 Proof of Lemmal 2.2
Proof of Lemmal 2.2 Given the specified reproducing kernel as mentioned in the above lemma, let
1/2 H the corresponding reproducing kernel Hilbert space. Suppose h E H and || S 1112 let d be the inner product defined for the RKHS H. and || a be the norm defined based on the inner product. Then, based on the definition of reproducing kernel, we have
||A||/0
sup [n(2)]
=
sup =ERI
k/,, k(z, m)ml
Canchy Schwarz's
sup zERiZi
|| [1),x|1((22,)) -)
||/llx =
sup vk(z,2) 2)
sup sealz k(2,))
1.
That is, the map of is contained within [-1, 1]. Consequently, the map of (h + 1)/2 is contained within [0. 1].
4.3
Proof of Lemma 2.4
Proof of Lemma 2.4 Suppose T) Lu,
(Zu Z1) S a, then, based on Definition 4.3 we have
sup |
[E [[ - E [h(Z))]l S a.
Consequently, we have
[L [h()))] - E [n(2))]] S 50-1/2
sup Su-1//
+ 1
h+1 1
v-1/2
sup
E
(2o)
- E
(2n)
<
2 a,
S0-1//
2
That is,
E [g( E [[o(Z))]| < v-1/2a
Vgg Eg
Since 3~ (er)o we have
w-1/2a
0) - = 1
Ag Eg
2
Let S* be the optimal predictor with respective to the sensitive attribute S, based on the set G, then we have
Pr( 1|S 0) Pr 1|S =) 1)| = Pr( 1 = + Pr(s 0.5 0)
sup BA(h; 2,S) 1/- hEH
Consequently, suPher (h 2,S) < 12-2-1/2
On the other hand, suppose the representation is 3-discriminative with respect to MMD, then we have V (Z z 2 B.. Based on Theorem 4.4 we have (Zo Z ] 1122 Then, based on
1/2g
Shen et al. 2022 Proposition 2), we have sup, BA Z, Y) > 4
Moreover, since
drv < 1, we have 3 < 1/2
13

---

4.4 Proof of Theorem 2.5
Proof of Theorem 2.5
Suppose the feasible of the classifiers is given the function set as
defined in Lemma 2.4 i.e., 9 [g (h + 1)/2 h H. ||/|| S v v-1/2), where 1)/)((2)
(h(z) + 1)/2, Vz, then we can rewrite the possible maximal value the involved faimess notions as
follows:
Independence. To begin with, based on Bayes' law, Z. = Pr(Y = 0 S s) + Pr(Y
S = 2)2,, 0,
sup DP(P,,)) = sup NCH
Pr(Y, = 5 1) - = 1
NEH
E S = 1| E S = 0]
sup
kcH
sup
[[]((1)] - Eio(Zu))l
NEW
+h+1 (Z1)
h + 1
sup
E
E
Zo)
Sw-1//
2
1
sup
IE (M1)) [1)))0]]
2 |AlluSS- 1/2
= (2w1/2)-1
sup
[[[h(2,]] E(
= (2w1/2) 7 (Zo 21).
Separation.
sup DOpp(h;; 2,Y,5) ΛEи
sup
Pr(y = Y = 1,5 -
Pr(y = 1 y= = 1,5 = =0)
sup
E [[g - E [9(2])]
heH
IE [[(ztt]] [MZ))]]
sup
1 1/2
(z)
=
Similarly, we have SuPREи DR(h: 2.Y.S) = (221 (2,, Zz). Based on the upper bounds for SuPMEæ DOpp and SuPNEæ R DR, have SuPıCH DOdds suPлеи DOpp + supneh DR (2 Z!) + + (Z. 28)).
Lower and upper bounds. Recall Definition
4.2 we have
[|40
M1 M1llz 1|
Oooolo + Pijobb Pollta - Pilináll
Paoolol (1 Pojo)rb - Polino (1-Po)))ire (oli)uill
[Pojo 14) + (1 (m - -nt)
+ (Pojo Pop (uf - m
In cases where Y S. we have Pojo
Poj1- Consequently, 1l Millx
IPo - ( + (1 (eb - at)llxx Based on the triangle's inequality, we have
11mo-Mallæ 2 Z ( 2 Pi [2, / and||uo ll S Pojo Th (2. +P 2/).
Suppose Pojo Puj1. have
|Po M4 2 ( - -19) + (1- Poj -
lpojo Popll 111 villxl
4.5 Proof of Theorem 2.6
Proof of Theorem 2.6 We start with the following lemma, whose proof is referred to Appendix 4.6
14

---

Lemma 4.5 (Calibration and TVD). Considering the calibration notions, i.e, DPC, DNC, and DC, proposed in Shen al. (2022] (T We have
drv ((Y, h()) S = 0, (X,)
8 1) (D,(,,
dry (Y))())
5 = 0. (V,
S ==11 =1 2 (PC Y,S), and
dry ((Y)(())
S 0, (Y,)(2))
S =1 2 DNC(h, Y,S).
Return to the proof of Theorem 2.6 Since sup, (1, u) S Mo.11 and sup, k S M(.11) we have
sup ko.11 @ ((0,1)((u,))) (u,v)) (u.))
sup ko. u)k (o.1) (
(w.))
= sup ( u) sup (v.3)
y
= (0.1-
Note that DC(h,Y,S)) ddrv ((Y, 15 0. (Y, (Z))(2)) S 1). Based Theorem 4.4 we have
drv ((Y,(ZZ) 0,, |==1] 5=1
z (Vo1)((011)) 1112 k (()) |s = 0,(,))))) =111.
Consequently, we have
DC(h, Y,S)) 2 (M.1))( 1/2 1 1 ((Y, 5 (Y,)(2)) |S =).
From the definition MMD (Definition 4.3 we have
0k ((Y,(ZZ) S 0, (Y,) |S S== 1o Ef (Z)) S 0] M()((Y S= 1]].
sup
Consider the function set F ;= { f(,, u) g()), |لو| Ho. S 1}. Let be a constant function that maps every input to 1. V E F, based on the property of the tensor product RKHS Szabó and Sriperumbudur (2018), we have
|l 11
| [
Note that {0, 1} a finite space. Let K = k= (k(o.1) (t, (LsE)))) be the Gram's matrix. Consider the
vector = (01, TT s.t., 1 = (k(o,1) (0.-), ((o, (1, .)a. It can be observed that Ka = (1, 1)
For simplicity, denote (t, as ki.j. We have
1 [1 =
VaTKa
11,,))-((11))"
10,o + +h1,1 2ko,
K
= 1.
Consequently, we have [l 2 Combining the above results, we have
< 1, 1, F. That is, FC (h |1 700 $ 1).
@ko. ((Y,(Z))) S = 0, (Y,A((Z)) S S=
sup EY (())) $ 0] - EI / (2) |S == =1]]
fe
sup
B h(Z) S 0J - M()) |S= 1]I.
|| l
15

---

Let id be the identity map embedded in [0, 1]. Suppose id E Ho..1-- Considering every possible
predicting function E G. we have
sup |eal [1o.1|
ElA (Z) S = 0] BBg (Z) ==
sup SLIMI S0 ((((h(2)+))/)) 5 0] ([(((((2) [[ + 1)/2) $= 0] (l0((((2)+ 11/2) 8-
|| id
sup
1ol Sll id |o. [IA S 1/2
2 id [4
sup
(I())(( + 1)/2) $ = 0] (id((((()) 1)/2) S s- 11
||A Su-1/22 1/2
(2 id (0.1
sup
[B[h(Z) 5 = 0] - E(((2 S 1]]
I1hl 1
(2 id |2
-' 1/2 1/2
sup
[B[((2) S 01 - E()(2) S I
11 I
(2 id |
-1 -1/2 y/ (m( Zo, Z1)
|| id Hp..))
sup (h; Z,Y. keR
4.6 Proof of Lemma 4.5
Proof of Lemma 4.5
Recall the notions for calibration, i.e., DPC, DNC, and DC, proposed in Shen
al. 2022
(Table
DPC(h, Y,
= 1
t S =0))
xE(O.1]
(NC(h,Y,S) 2
Σ
|Pr(Y = = -) = = s 0)1.
[E(U,1]
DC(h, S, = (DPC(h, Y,S) DNC(h, Y,S)).
Based on the expressions listed above, have
drv ((V,(ZZ) S 0,, 1)
Σ [Pr(Y 1,) = 5 == Pr(Y = 1,)(Z) 1 1)
[E[0.]]
+ |Pr(Y = 0, = = 5= Pr(Y 0, f 1)1]
DPC(I, Y,S) DNC(L,Y,S)
2DC(,, Y,.).
Since 2 DC DPC + DNC, the next two inequalities can be derived.
4.7 Supplementary for Gaussian Complexity
In the following, we provide a concentration inequality for the Gaussian complexity, revealing that can be empirically estimated from a realization, simplifying its computation.
:= Proposition 4.6 (Concentration of Gaussian Complexity). Given a function class F= {h: : X H
2), where Z C Rdd Denote the set {f()) I F, E X3 2 as F(X). Let F(X) be a set in n
defined as F(X)= == {(f(X)).... f(X,...,((.) [E Let D(F(X)) := sup=, || z' be
the Euclidean width of the set F(X), Gnd(F(X)) be the Gaussian complexity of the set F FXX) as defined in (4). Then 48 E (0, 1). with probability at least 8, we have
(E,. f(Xi)) - Gad(F(X)) s DD((()))) ( nlog (5)
2
sup fEF 2m1
16

---

where& & ltd. N(Oss, Vi. Moreover, we have
nd 2
2 (
[Gx((F()) - -E|Gnd DD(((X)
log
Considering the where the feasible set of the encoders is formulated by neural networks, which is a common scenario in FRL. its covering number is finite, as shown in Theorem 2 of [2023]. corresponding the satisfaction of Assumption 2.7 In the following, we provide an upper bound for its Gaussian complexity in the following proposition.
Forward Neural Networks, Ni and Huo (2024) Proposition 18). Consider ferd-forward neural network with depth i, which is given by the function fin R2 + R defined as follows
Proposition 4.7 (Gaussian Complexities
(x) = (0) o. ..... (z) =1 (...0))))) (1)())))))))
.. where do d, d, = and ((6) = w for a specified matrix Rixd,-1, Here, for = I....,t- (k) Rdd-- Re is the k-th hidden layer consists of coordinate-wise composition of an activation function a + R and an affine map, namely, (x)) = o(W()x) for an given interaction matrix ((k) E Rd xds 1, Let the interaction matrices be the parameters to be tuned, the corresponding class of neural networks is given as follows:
F F
( (()
w. Ak
1,00
where for given matrix W, the || 111,00 norm is defined as 11,00 max, Σ, Wesl Suppose the activation function a is X-Lipschitz, let X = (X1...., "n)" E RRaxd, we have
G(F(X)) < (2W) 12--1v220 log(2dg) max
X2 k
i=1
NeurIPS Paper Checklist
Clains
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main contributions of this work are summarized the abstract: we propose novel kennel-based fairness constraint that performs effectively in both biased and unbiased settings, enabling quantification of trade-offs between fairness and accuracy as well as among multiple fairness criteria. Further details are provided in Section 1.1 of the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer 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.
It 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]
17

---

Justification: Although not highlighted explicitly, we have addressed the limitation by discussing the feasible set of classifiers considered this work-an an affine map of unit ball in RKHS. While this choice does not capture the full hypothesis space, it encompasses most practical classifiers and allows for efficient optimization via gradient descent. context, and its computable formula provides computable solution obtained by gradient descent. Details are included in Section 1.1 and 1.3.
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 create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results 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.
violations of
The authors should reflect on the scope of the claims made, e.g.. if the approach was only tested on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images taken in low lighting. Or a speech-to-teds 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 of 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, a worse outcome might be that reviewers discover limitations that aren't i acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
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: The assumption is either clearly stated in the corresponding theorem (Section 2.2) stated before the theoretical result (Section 2.3). The proofs are referred to the Appendix.
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 the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to 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 be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper does include any experiments.
Guidelines:
18

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution
dataset and/or model, the authors should describe the steps taken 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, if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (c.g., in the case of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a)If the contribution is primarily new algorithm, the paper should make clear how to reproduce that algorithm.
(b)lf the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c)lf the contribution is way to access this model for reproducing the results or a way to reproduce the model (e.g.. with an open-source dataset or instructions for how to construct the dataset).
model (e.g., large language model), then there should either be
(dJWe recognize that reproducibility may be tricky in some cases, in which case authors welcome to describe the particular way they provide for reproducibility. In the case of closed- source models, it may be that access to the model is limited in some way (e.g.. registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described supplemental material?
Answer: [NA]
Justification:
This paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines
Shiides/CodeSubmisse wwtbbbmmsssinno ssionPolicyy for more details.
While we encourage the release of code and data, understand that this might not be possible,
so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this central to the contribution (e.g.. for a new open-source benchmark).
The instructions should contain the exact command and environment needed run to reproduce the results. See the NeurlPS code and data submission guidelines (https: htcttp::/niips.ccppubllia guides/CodeeSumm ssi onPolicy) 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. If 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 as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
19

---

Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
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 level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
This paper does not include experiments.
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, confidence intervals, statistical significance tests, 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, or overall run with given experimental conditions).
The method for caleulating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard enror of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates).
If error bars are reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [NA]
Justification:
This paper does include experiments.
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 of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
20

---

Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
This paper conform, in every respect, to the NeurlPS Code of Ethics and preserve anonymity.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there a special consideration due to laws or regulations in their jurisdiction).
10Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This paper addresses fair representation learning, topic inherently tied to the social impact of machine learning systems. The proposed fairness constraint promotes equitable outcomes by ensuring that, conditional on the target variable, model predictions are independent of sensitive attributes. This directly contributes to mitigating discriminatory behavior in downstream applications.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or 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.. deploy- ment 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 to particular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses addition to attacks, mechanisms for moni- toring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
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 (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse 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 implementing safety filters.
21

---

Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
Liceenss for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected??
Answer: [NA]
Justification:
This paper does not use existing assets.
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, if possible, include a URL.
The name of the license (e.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, paperssi ppaperswithcode. thcode. com/cooo///coo//o datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14Crowdsourcing 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, well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
22

---

15 Instituttinal 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 on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. 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 NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such the institution conducting the review.
16Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if 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, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
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, or non-standard components.
Please refer to our LLM httppp///aeurii...ccc/oooooroota should should not be described.
for what
23


Reviews:
[{"review_id": "LArTsQ5f42", "reviewer": "Reviewer_akC3", "summary": "This paper proposes a kernel-based formulation of Equalized Odds (EO_k) for fair representation learning in a supervised setting (the authors focus on binary classification). The EO_k criterion provides a unified characterization of three core fairness objectives used in the literature: independence, separation (also called EO), and calibration. When the data is unbiased -- i.e., the target variable Y is independent of the protected attribute S -- EO_k satisfies both independence and separation. When the data is biased (Y is not independent of S), EO_k provides a controllable level of predictive accuracy while lower-bounding independence and calibration. The latter is the primary contribution of this work, as it formalizes and quantifies the trade-off between different fairness objectives, providing a parameter/knob to trade-off fairness enforcement with accuracy degradation.\n\nThe authors define the EO_k statistic and analyze its theoretical properties, including connecting it to Maximum Mean Discrepancy (MMD) of reweighted group distributions. The connection to MMD enables a closed-form approximation of the heuristic that runs in quadratic (or linear) time; this can be added as a penalty term to your fair representation learning objective. The authors also provide a concentration inequality with error bounds that can serve as a certificate of fairness compliance. The paper does not include empirical studies, which are planned for future work.", "questions": "1. Is there a small case study or experiment you can run (even repeating one from prior work) that demonstrates the effectiveness of EQ_k in practice? As I mentioned above, there are many practical properties of EQ_k that would be useful to validate. \n2. Can you walk through an example of how setting \\Beta > 0 leads to independence and calibration being violated? \n3. Can you summarize how your theoretical analysis would change if you generalized it to multi-class classification?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n\nThe motivation behind EO_k and the novel characterization it enables is clearly expressed. I really like how this statistic paints a clearer picture of the trade-off between the three fairness criteria (which are not achievable all at once except in degenerate cases). Your observation that independence and calibration are at odds with predictive accuracy makes a strong case for EO_k strong given its ability to accommodate predictive accuracy in a controllable way.\n\nI found Eq. 6 to be quite instructive, as it shows how satisfying EO perfectly necessarily leads to independence and calibration being violated. Therefore, to ensure some predictive accuracy, you set your \\Beta parameter to > 0. It would be helpful if you could explain in more detail how independence and calibration are violated when EO_k = 0.\n\nEO_k has a practical, closed-form approximation that can be applied as a penalty term to your learning objective. This approximation is compatible with SGD and comes with hyperparameter-free convergence guarantees. \n\n### Weaknesses:\n\nThe main weakness of this paper is that it has no case study or empirical validation of EO_k. There are many properties of EO_k that make it suitable for practical use: efficient closed-form approximation, hyperparameter-free convergence, controllable fairness/prediction accuracy trade-off, etc. But without any experiments, it is difficult to gauge the utility of these properties. I also think you will learn new things about EO_k when you try to apply it to a fair representation learning task. Although you make it clear that your focus is on theoretical development, even the main theory papers you build on (e.g., Dwork et al., Hardt et al.) include some case study or experiment. I'm also curious to see how the logarithmic relationship between deviation bound and input dimention plays out; you noted this as a computational advantage of EO_k over trasitional IPMs. \n\nIt would be helpful to recount the thought process that led to the design of EO_k. You partially explain this in Section 2.1, but then you immediatly jump to the \"weighted summation conditioned on Y\" without explaining how you arrived at that choice. \n\nThe \"universal approximation\" property of the RKHS (reproducing kernel Hilbert space) is quite strong, saying it can approximate any neural network predictor to arbitrary precision. Can you comment on the practical realizability of this approximation?\n\nWhich parts of your theoretical analysis would change if you went beyond binary classification to more general (multi-class) classification?\n\n### Additional comments:\n\n* It would be better to present Equations 1-3 in a more consistent way rather than attempting to follow the original formulations (e.g., the Z parameter in Demographic Parity is unused). \n* You define \"perfect accuracy\" for a predictor/classifier in two different ways mathematically (as a probability of a conditional expectation and as a probability); this adds unnecessary confusion.", "was_revised": true, "final_justification": "The theoretical and technical contributions of this paper are solid. It is perhaps unfortunate (or fortunate, depending on how you see it) that this work unifies multiple fairness criteria and enables a trade-off between accuracy and fairness, because the latter raises nontrivial ethical concerns that require more care to address. I (and I imagine the other reviewers) realize this standard may be higher than that of other papers published in the FRL field. Nevertheless, the lack of an ethically-cognizant empirical demonstration of EO_k's utility is not something to ignore.\n\nThe authors have done a case study on the HMDA 2017 dataset, as requested by the reviewers. Although the details of this study have not been provided, the reported results are promising and indicative of a methodology (e.g., via sweeping tunable parameters) for navigating the accuracy/fairness trade-off. I am increasing my score based on the expected merits of this study and the work done by the authors during this rebuttal. \n\nThere are two issues that remain, which I believe the authors can address via some rewriting. The first is to exposit the empirical study in an ethically-cognizant manner in the main body of the paper. The second is to reframe your contributions carefully based on the ethical concerns raised by reviewer XX and the ethics reviewers; please take their feedback seriously and restate/qualify your claims to mitigate potential harms in how practitioners might interpret them or adopt your methods. \n\nI understand that this paper is a borderline case. The authors should be proud of their work; the work they have done in the rebuttal and addressing the remaining issues above should yield a strong publication.", "rebuttal": ""}, {"review_id": "kgJHbhapw6", "reviewer": "Reviewer_NgDe", "summary": "This paper presents a kernel-based reformulation of the equality of odds fairness metric, which permits a quantifiable characterization of the fairness-accuracy trade-off in fair representations learning. This new definition, dubbed $EO_K$, allows characterization of sufficiency, independence, and calibration fairness desiderata, which authors carry out under two settings of ground truth label and sensitive label independence and lack thereof. Various theoretical results are provided, including a generalization guarantee, a bound on balanced accuracy based on a maximum mean discrepancy (MMD) formulation of $EO_k$, and quantified comparisons between the fairness desiderata.", "questions": "- Q1. Can you summarize the theoretical novelties that you have contributed? At times, I had difficulty pinpointing your original contributions from prior work.\n- Q2. Can you add quantitative comparisons to prior work in fairness-utility trade-offs? For instance, a Lagrangian approach such as FERMI [1] or an encoder-based fair representation learning approach such as FARE [2]? \n  \n  Note that FERMI is not a representation-based method, but the topic of fairness-utility tradeoff is well explored. It bears comparison across methodologies.  \n  \n  [1] A. Lowy, S. Baharlouei, R. Pavan, M. Razaviyayn, and A. Beirami, “A Stochastic Optimization Framework for Fair Risk Minimization,” Jan. 11, 2023, *arXiv*: arXiv:2102.12586. doi: [10.48550/arXiv.2102.12586](https://doi.org/10.48550/arXiv.2102.12586).  \n  [2] N. Jovanović, M. Balunović, D. I. Dimitrov, and M. Vechev, “FARE: Provably fair representation learning with practical certificates,” in *Proceedings of the 40th international conference on machine learning*, PMLR, 2023.  \n- Q3. Please comment on the W3 and consider adding an impact statement.", "limitations": "The paper would have benefited from empirical evaluations (even small-scale experiments on tabular data).", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Overall, I think this is a valuable contribution. The writing has issues that would limit its impact, however. Also, quantitative comparisons with prior theoretical works are missing. I will enumerate **S**trengths and **W**eaknesses. \n\n- **S1. The kernel-based approach is novel.** The formulation as an affine map of the unit ball in the RKKHS allows expression of the equalized odds violation as a total probability of disparities over classes in the proposed metric $EO_k$. This is interesting and scalable to more classes and (likely) multiple sensitive attributes.\n\n- **S2. Quantitative trade-off between various fairness definitions is interesting.** While prior work shows how satisfying different fairness metrics is impossible, those results mostly consider exact fairness (which in and of itself is often hard to enforce in reality, even for a single metric). Having a quantified trade-off using the presented method is a more granular extension to these results that I find useful.\n\n- **W1. The paper is disorganized and lacks flow.** The paper has three sections, with the third section being the conclusion, and the first section being the introduction. The introduction runs 5 pages and includes related work in two separate subsections. The discussion mixes in prior work with contributed work constantly, making assessment of the novelty and contribution difficult. Most sections and subsections miss proper transitions, which makes reading the paper quite difficult. More detailed feedback on this front:\n\t\t- I question the necessity of Section 1.3 (the second related work section discussing a plethora of prior work without clear motivation). All and all, regardless of the results, the paper is not in a publishable state.\n\t\t- Section 1.1 is unnecessarily dense and inapproachable. I understand the authors sought to summarize their results, but this is largely unhelpful.\n\n- **W2. Quantitative comparison to prior work is missing.** While there is plenty of qualitative comparison to prior work, I think the paper is missing quantitative comparisons with any meaningful baseline methods. In the absence of empirical results (which on its own is fine), I expected a rate comparison at the very least. This leaves important questions unanswered: for example, since the paper claims to achieve good fairness-accuracy trade-offs, does it Pareto dominate prior work in any meaningful capacity?\n\t    \n- **W3. $EO_k$ cannot resolve the tensions in choosing a proper fairness metric.** A non-technical weakness is that the paper suggests that the use of $EO_k$ resolves the issue of selecting a fairness criterion compared to prior work. In particular, the paragraph starting on Line 150 reads: \"To address the ambiguity in selecting a fairness criterion, recent works have proposed metrics that aim to approximate multiple fairness notions simultaneously... In contrast, our method acknowledges this conflict and formalizes the trade-offs using a kernel-based statistic, EOk.\"   \n\t    \n   However, choosing a proper fairness definition should be a function of the application and ideally based on a legal and philosophical discussion of the fairness required. Prior work [1] has shown that the impossibility of satisfying multiple fairness definitions is due to their opposing philosophies. Therefore, I think it is wrong to suggest a single technical fairness definition is appropriate for all applications, regardless of the social context it is being used. I'll flag this for an ethics review and invite the authors to reflect on this question from beyond a technical standpoint.  \n\t    \n     I am afraid making comparisons between fairness definitions easier, beyond its value as a research endeavor, is going to invariably make \"shopping around\" for a fairness definition worse. This is a classical reification that is prevalent in algorithmic fairness literature that we should be very consciously avoiding.  \n\t    \n    [1] H. Heidari, M. Loi, K. P. Gummadi, and A. Krause, “A Moral Framework for Understanding of Fair ML through Economic Models of Equality of Opportunity,” *arXiv:1809.03400 [cs, econ, stat]*, Sep. 2018, Accessed: Jun. 25, 2019. [Online]. Available: [http://arxiv.org/abs/1809.03400](http://arxiv.org/abs/1809.03400)", "was_revised": true, "final_justification": "We reviewers (as well as the AC) engaged in a fairly long discussion around this paper. The authors introduced a new case study and (finally) implemented their method. I think the paper requires a new introduction and a re-write incorporating the empirical results. This is a tall order for the rebuttal. I had given the paper a weak accept with medium confidence; given the scope of suggested changes,  I cannot give it a full accept, so instead I have increased my confidence score.", "rebuttal": "Thank you for your incisive feedback and for recognizing the novelty of our technical approach (S1, S2). Your comments on the paper's structure and positioning have been particularly constructive as we prepare our revision.\n\nWe believe the core of our disagreement on the paper's organization stems from the different frameworks through which the main message of a paper should be presented. Our initial structure was designed to mirror the logical progression of a theoretical proof: establishing formalisms, building up intermediate results, and culminating in the main characterization theorems.\n\nHowever, we fully appreciate your perspective that for a machine learning audience, this structure may obscure the main takeaways. A clear presentation of our results is paramount. Therefore, to better serve our readers, we will gladly adopt your advice and restructure the manuscript to front-load the primary contributions and their significance.\n\nTo clarify the points that the new structure will emphasize, we briefly summarize our core contributions below.\n\n## **Core Contributions & Theoretical Impact (W1 & Q1)**\n\nYou asked for a clearer summary of our theoretical novelties. The revised manuscript will be built around these central pillars, which we believe represent significant advances. Furthermore, our framework is designed with practical realities in mind. Unlike prior approaches that focus only on simultaneously achieving multiple fairness goals, our work explicitly addresses the more common and difficult scenario where these goals are mutually exclusive, providing a quantifiable path forward.\n\nOur core contributions are:\n\n- **A Foundational Unification Result:** Our work is the first to prove that in the crucial **unbiased case** (Y⊥⊥S), minimizing our single metric, EOk, is mathematically equivalent to achieving both Demographic Parity (DP) and Equalized Odds (EO) simultaneously (Eq. 5). This is a definitive resolution to the choice between these two core metrics in this setting.\n- **A Novel Quantification of Fairness Incompatibility:** In the biased case where fairness notions conflict, our framework is the first to deliver a formal inequality (Eq. 6) that quantifies this trade-off. We prove that to maintain high accuracy, enforcing one fairness goal (e.g., EO) necessitates a quantifiable violation of another (e.g., DP or DC).\n- **A General and Practical Framework:** We provide a valid empirical estimator for EOk whose convergence is guaranteed by established MMD theory, ensuring our theoretical contributions can be readily implemented.\n\n## **On Positioning and Quantitative Comparison (W2, Q2)**\n\nYour expectation for quantitative comparisons is logical. However, a direct comparison is difficult because our work addresses a fundamentally different, and arguably prior, research question than works like FERMI [1] and FARE [2].\n\nThe distinction is this: **Those works analyze the accuracy trade-off for a** ***single, pre-selected*** **fairness metric (e.g., DP). Our work tackles the more foundational problem of what to do when core fairness metrics like EO, DP, and DC are themselves in conflict.**\n\nTherefore, our contribution is not just a theoretical complement; it is an answer to a different question. We provide the theoretical justification for how to select a path forward when faced with competing fairness definitions, a scenario that precedes the fairness-accuracy trade-off analysis in other papers. We will make this crucial distinction explicit in the revised introduction and add an illustrative case study to demonstrate our theoretical results in practice.\n\n## **On the Scope and Framing of our Metric (W3, Q3)**\n\nYour point on the philosophical framing of fairness is well-taken. We want to be precise about what our metric, EOk, does and does not \"resolve.\"\n\n- **In the unbiased case, our metric** ***does*** **resolve the tension.** As stated above, our result in Eq. 5 provides a definitive technical solution that eliminates the need to choose between DP and EO when the data supports achieving both. This is a practical and powerful property.\n- **In the biased case, our metric provides a *principled path forward*.** We agree that no algorithm can make a moral choice. However, its unique technical advantage is that for practitioners who have already determined that EO aligns with their normative goals and that maintaining high predictive accuracy is a priority, our metric becomes the **principled technical choice**. It is the only common fairness objective that guarantees compatibility with the Bayes-optimal classifier, thereby eliminating the need to wander between conflicting metrics and providing a clear, justifiable path forward. We will add a Broader Impact statement to formalize this rigorous scope.\n\n-----\n\nWe thank you again for your constructive feedback. We are confident that these revisions will result in a clearer, more impactful paper that effectively communicates the substance of our work to a broad audience."}, {"review_id": "kWe6MHTLPp", "reviewer": "Reviewer_bR6s", "summary": "This paper proposes a fairness measure for fair representation learning, which is a kernel-based formulation of EO ($EO_k$) and provides theoretical properties of this new proposed formulation. This new formulation uses MMD to measure the differences in representations between two demographic groups, enabling rigorous and interpretable quantification of independence, separation (via EO), and calibration within a unified framework. The main contribution of the paper is to quantify the trade-offs between these mutually incompatible fairness constraints and to analyze their implications.", "questions": "- While the paper emphasizes that $EO_k$ is not designed to optimize all fairness metrics simultaneously but rather to quantify the trade-offs between them, this conceptual distinction remains abstract without concrete justification. Can the authors provide a realistic case or application where such trade-off quantification is actually useful? For example, how would a practitioner interpret or act on the value of $EO_k$ in a model selection or deployment scenario? More generally, how does $EO_k$ support fairness-aware decision-making beyond what simpler metrics (e.g., separate TPR/FPR gaps or post-hoc fairness curves) already provide? What specific limitations of existing fairness criteria does $EO_k$ address that cannot be handled using DP or EO? i.e., why is a new kernel-based fairness metric necessary?\n\n- In practical settings, fairness constraints are typically selected based on domain or specific requirements (e.g., some cases decision makers prefer equalized odds, some cases prefer accuracy parity), why is a unified definition preferable or more actionable?\n\n- Using kernel-based definition will increase computational cost compared with DP and EO, so what practical gains justify this additional complexity?", "limitations": "The authors did not discuss the limitations of their approach. The main limitations are outlined in Weakness Point 1 and further elaborated in the questions I have raised.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The new formulation is mathematically well-defined in a principled manner (Section 2.1), and the derivation of the generalization bounds and the closed-form empirical estimator is technically correct and solid.\n\nWeaknesses:\n- The main concern with this paper is the lack of empirical support (the submission contains no experiments, toy examples or any empirical validation). While the authors state that the work is theoretical, but provides a connection between theory and practice is still important. Without at least a simulated example demonstrating how $EO_k$ captures trade-offs in realistic scenarios, it's difficult to assess its practical significance. \n\n- Section 2 presents the main theoretical contribution, and the section reads like a disconnected sequence of tehnical points (defs, lemmas, bounds), each introduced in isolation without sufficient transitions or motivation. For example. section 2.1 introduces the formulation of $EO_k$ and after that immediately moves to its RHKS form with no clear intuition or example to help the reader undersatnd the object being defined. Lemma 2.2 and 2.4 define technical function classes and bounds, but the role in the overall framework is not explained until much later.  Also, the notations are compact and mathematical shorthand that obscure the main ideas and reduce the readability. After reading Section 2, it is still unclear what the main theoretical message is beyond a set of bounds and definitions. The paper would benefit greatly from: (1) adding a motivating paragraph at the beginning of Section 2; (2) add some clear transitions between subsections to explain why each result is introduced and (3) maybe provide a summary paragraph at the end that synthesizes the theoretical results and explains their implications for fair representation learning.\n\n- The necessity of using kernel-based MMD to formulate fairness constraints is not well justified. This design choice introduces additional complexity. In practice, simpler and more model-agnostic alternatives are often more interpretable and widely adopted.\n\n- Similar to the above one, while the theoretical unification of multiple fairness definitions is interesting from a statistical perspective, in practice, practitioners typically select one or two fairness notions based on task requirements. The need to balance all three (independence, separation, and calibration) is not sufficiently motivated, and the paper lacks examples where such trade-offs arise naturally or meaningfully. In other words, the paper introduces $EO_k$ without sufficiently motivating the limitations of existing metrics or demonstrating that this new formulation enables better fairness–accuracy trade-offs in practical tasks. It remains unclear what real-world problems $EO_k$ solves that cannot already be addressed with existing fairness constraints.", "was_revised": true, "final_justification": "I appreciate the authors’ detailed response, which addressed most of my questions. After also reading the comments from the other reviewers, I have decided to raise my score. I strongly encourage the authors to revise the paper as outlined in their rebuttal, particularly by restructuring it to make several key points more explicit. This will greatly enhance the paper’s clarity and accessibility for a broader audience. I have raised my score as a final justification of my initial evaluation.", "rebuttal": "Thank you for your detailed review and for acknowledging the technical soundness of our formulation. Your feedback has been instrumental in helping us identify where the manuscript's presentation needs to be strengthened. Your core concerns about motivation, structure, and practical justification all point to a single root cause: our draft implicitly assumes familiarity with the context of recent Fair Representation Learning (FRL) research.\n\nTo resolve the issues you raised, our main revision will be to restructure the paper around a clear \"Problem-Solution\" narrative, making this context explicit. Below, we outline how this new structure will directly address the points you raised.\n\n### **1. Motivation and Structure (W1, W2, Q1)**\n\nYou correctly noted that the paper currently lacks a strong motivational thread (W1) and that Section 2 can read as a disconnected set of technical points **(W2)**. This is a direct result of us not adequately setting the stage.\n\nThe revised paper will resolve this by dedicating a new introduction paragraph upfront to the well-established problem our work solves:\n\n- **The Problem:** The machine learning community requires methods for *in-training fairness enforcement*. Post-hoc auditing metrics like TPR/FPR gaps (your **Q1**), while vital for evaluation, are non-differentiable and cannot be used directly in gradient-based optimization. This is the central motivation for FRL and, by extension, our work.\n- **The New Structure:** By establishing this \"in-training vs. post-hoc\" problem first, the technical details in Section 2 will no longer appear disconnected. Instead, they will be clearly framed as the necessary mathematical foundation for building our proposed solution. To further underscore the practical significance, we will also add a small-scale experiment demonstrating our method in a simulated application. The experimental results are referred to the rebuttal for Reviewer akC3.\n\n### **2. Complexity and Computational Cost of metric $\\mathrm{EO}_k$ (W3, Q3)**\n\n- You raised a crucial question about whether the complexity of our kernel-based method is justified over simpler alternatives and what its computational cost is **(W3, Q3)**.\n\n  Our revision will clarify that the relevant comparison is not to simple post-hoc metrics, but to other *in-training* enforcement methods. This context is key:\n\n  - **Superiority over Adversarial FRL:** The standard approach using adversarial networks is known to be unstable and computationally expensive. Our MMD-based approach replaces this complex min-max problem with a stable, closed-form objective, thereby *reducing* the effective computational burden and instability of training.\n  - **Advantages over other IPMs:** Furthermore, even when compared to other advanced Integral Probability Metrics (IPMs) used in fairness literature, our choice of MMD offers distinct advantages. It admits a simple, closed-form estimator and enjoys favorable generalization error bounds, making it not just a stable alternative to adversarial methods, but a computationally efficient and theoretically reliable choice among modern IPMs.\n\n### **3. Practical Preference and Actionability (W4, Q2)**\n\nFinally, you asked why our \"unified definition\" is preferable or more actionable in practice **(W4, Q2)**. This is the core value proposition of $\\mathrm{EO}_k$, which the revised structure will highlight as the \"payoff\" of our framework.\n\nOur revision will dedicate a paragraph to the unique, practical advantages that make $\\mathrm{EO}_k$ a more principled choice for practitioners:\n\n- **Reduces Practitioner Burden:** In the common unbiased case, that is, the target attribute $Y$ is independent with the sensitive attribute $S$, $\\mathrm{EO}_k$ resolves the difficult choice between enforcing Demographic Parity (DP) or Equalized Odds (EO) by satisfying both simultaneously with a single objective.\n- **Aligns Fairness with Accuracy:** In the more complex biased case where the target attribute $Y$ is related with the sensitive attribute $S$, our method is unique among common fairness criteria in that it does not automatically discard the Bayes-optimal (most accurate) classifier. This provides a path to fairness with a lower \"accuracy cost.\"\n- **Simplifies Optimization:** Our metric serves as a smooth, differentiable surrogate for the core concept of Equalized Odds, making a difficult-to-optimize constraint practical for modern training pipelines.\n\n------\n\nWe are confident that by restructuring the manuscript to explicitly present this context and problem-solution narrative, the motivation, justification, and significance of our contributions will be clear. Thank you again for providing the precise feedback needed to make our paper more impactful."}, {"review_id": "Sm2EWBYxSw", "reviewer": "Reviewer_4aTM", "summary": "This paper proposes a kernel-based Equalized Odds (EQ) criterion for characterization fairness in machine learning. An empirical estimator is provided to estimate the kernel EQ, and the author establishes theoretical guarantees for the estimator as well as fairness-accuracy tradeoffs.", "questions": "Does kernel misspecification lead to false fairness claims using the proposed criterion?", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "## Strengths\n  - The proposed kernel-based EQ could be a useful extension of EQ with robust theoretical guarantees.\n  - An empirical estimator is provided for calculating the kernel EQ which is practical and scalable.\n  - The authors show desirable theoretical guarantees for fairness-accuracy tradeoffs as well as convergence of the empirical estimator. \n\n## Weaknesses\n\n  - The proposed fairness criterion and the associated results are dependent on the given kernel. If the kernel is misspecified, the criterion may yield false fairness claims. Kernel misspecification could be less relevant for prediction tasks, but a concern for a criterion. \n  - Kernel-based equalized odds and fairness-accuracy tradeoffs have already been studied in literature. Potential missing related work: \nTan et al.,  Learning Fair Representations for Kernel Models. AISTATS, 2020", "was_revised": true, "final_justification": "The authors address my concern and I maintain my score.", "rebuttal": "Thank you for your thoughtful review and for recognizing the technical soundness of our proposed framework, its theoretical guarantees, and its practical estimator. You raise two important technical points regarding kernel misspecification and the relationship to prior work by Tan et al. (2020). We welcome the opportunity to clarify both, as they are central to the contribution of our paper.\n\n### **1. On the Robustness of Our Criterion to Kernel Choice**\n\nYou raise an excellent and fundamental question: \"Does kernel misspecification lead to false fairness claims using the proposed criterion?\" This is a crucial point that we touch upon in **Lines 88-97**, where we discuss the expressiveness of the function class defined by the kernel. We appreciate the opportunity to elaborate on this, as we recognize our initial explanation may have been too concise.\n\nThis concern is at the heart of all kernel-based distribution measures, and our framework relies on a powerful, standard resolution from the literature:\n\n- **The Role of Characteristic Kernels:** Our proposed metric, $\\mathrm{EO}_k$, is a kernel-based Integral Probability Metric (IPM) that is defined using a **characteristic kernel** (e.g., Gaussian RBF), as is standard for MMD-based metrics. The established theory for these kernels (c.f., Sriperumbudur et al., 2010b) provides a strong guarantee: the corresponding Reproducing Kernel Hilbert Space (RKHS) is rich enough that the IPM will be zero *if and only if* the underlying distributions are identical. This is the core principle we allude to in **Lines 88-97** when discussing the richness of the unit ball of the RKHS.\n- **Implication for Fairness Claims:** Consequently, a \"false fairness claim\"—where our $\\mathrm{EO}_k$ metric is zero but the conditional distributions of the representations are truly different—is theoretically avoided. With a sufficiently flexible characteristic kernel, whose parameters can be set via standard practices like the median heuristic, $\\mathrm{EO}_k$ provides a reliable and robust measure of fairness violations.\n\n**Action:** We see now that this point is critical and deserves more prominence. In our revision, we will expand upon the discussion in Lines 88-97 to explicitly state the reliance on characteristic kernels to make this theoretical foundation unambiguous for the reader.\n\n### **2. Clarifying Our Contribution Relative to Tan et al. (2020)**\n\nWe appreciate you highlighting Tan et al. (2020). While it is an important paper on FRL for kernel models, our work addresses a fundamentally different research question and provides a complementary set of insights. The distinctions are crucial:\n\n1. **Focus of Analysis (Fairness vs. Fairness):** Our primary contribution is a theoretical characterization of the **incompatibility between multiple fairness criteria** (EO, DP, and DC). We prove that under data bias, enforcing EO necessitates a quantifiable violation of the others. Tan et al., in contrast, analyze the trade-off between a single fairness notion and predictive accuracy.\n2. **Nature of the Trade-off Analysis:** Our technical approach derives analytical lower bounds on these cross-metric fairness violations. Theirs is a geometric approach based on subspace projections. These are different and non-overlapping analytical tools that address different aspects of the fairness landscape.\n3. **Core Problem Setting:** Most critically, our work operates in the standard group fairness setting where the sensitive attribute S is available at training time (a prerequisite for defining EO). Tan et al. address the distinct and challenging problem of learning fair representations **without access to S** at training time.\n\n**Action:** While both papers use kernel methods, they tackle different problems with different tools. Our paper's novelty lies in its distribution-level characterization of fairness-fairness trade-offs. We will revise our related work section to include a discussion of Tan et al. and articulate these clear distinctions.\n\n------\n\nWe hope this response clarifies these two important technical aspects of our work. We are confident that by incorporating these clarifications into the manuscript, the novelty and rigor of our contributions will be even more apparent. Thank you again for your constructive engagement."}]

Author rebuttal:

Meta-review: The paper studies representation learning. It builds on the two fair classification criteria of equalized odds (EO) and demographic parity (DP), as well as the usual ML criterion of classification accuracy. When learning a representation followed by a classifier, these three criteria might come in conflict, and the paper examines the tradeoff among them. 

More specifically, the paper proposes a new kernel-based criterion for evaluating a representation, called EO_k. (Note that the representation itself can have an arbitrary form, as can the classifier that reads the representation; it is only the measure EO_k that necessarily uses a kernel k.) EO_k is based on differences of expectations of unit-norm functions in the RKHS, conditioning on label values or sensitive attribute values — reminiscent of other kernel-based statistical measures like MMD.

The paper shows that EO_k enables a form of tradeoff among DP, EO, and accuracy. For a population, (1) in the case that a protected attribute S is independent of the label variable Y, a representation that minimizes one of the EO_k measures will enforce both DP and EO for any of a wide set of classifiers acting on that representation. And (2), in the general case where S and Y may be dependent, the choice of kernel k lets us trade off accuracy, DP, and EO; the paper presents bounds on the relationship.

The paper also defines an empirical estimator of EO_k, which can be computed in time quadratic in the size of a training set, and has a linear-time approximation. The same tradeoffs as above apply, but now with (in)dependence, accuracy, DP, and EO evaluated empirically on the training set, instead of population versions. The paper shows a convergence rate of empirical EO_k to population EO_k. In finite samples, of course, a sampling error remains for all of the measures (EO_k, EO, DP, accuracy); a discussion of how these errors can affect the tradeoff would have been helpful, particularly since there is selection bias when we optimize for any combination of the empirical measures.

The paper points out that, if we use a universal kernel, the EO_k criterion in principle tells us something about any downstream classifier based on the learned representation. This guarantee is somewhat misleading, though: the choice of kernel can make the norm of a given smooth function vary widely — even to the point where a kernel-based measure effectively ignores this function, especially in comparison to the sampling error from any reasonably-sized dataset.

As noted by the ethics reviewers, the paper takes too narrow a view of the problem of fair classification or representation learning: it assumes we are given a training dataset that we cannot influence, and our only problem is to decide on a representation or a decision rule that will be applied to identically distributed test points. In reality, there are a lot of decisions to be made on both sides of this narrow version of the problem: e.g., how we collect and label the data, what we choose to predict, and how we use the predictions. 

By skipping these surrounding decisions, the paper precludes a discussion of how they interact with the paper’s proposed solution: for example, how would labeling bias in the training data influence the tradeoff among EO, DP, and accuracy on new data *without* the labeling bias, and how would EO_k perform in this situation? How would common data quality problems like distribution shift influence the ability of EO_k to make its tradeoff effectively? A full discussion of these questions would likely be impossible, but the paper also shouldn’t ignore them.

During the author response period, the authors responded to the ethics feedback and analyzed a new case study. This study is informative in some directions: it demonstrates that the new method can obtain not-far-off-optimal values for all of DP, EO, and training accuracy simultaneously, and also that the Gaussian kernel is effective in this case, without a strong sensitivity to bandwidth. However, the new case study still doesn’t examine the broader version of the problem: e.g., it doesn’t address the questions at the end of the previous paragraph.

The final decision depends on two things: first, technical contribution, and second, how well the authors will be able to incorporate the ethics feedback into the final version of the paper. From reviewer scores and discussion, the technical contribution is somewhere near the borderline for acceptance based on correctness and interest. I judge it to be above the bar, though competition is fierce at NeurIPS, so the bar may move based on space constraints. For the ethics feedback, I have good hope that the final version of the paper can incorporate it, and also that having the authors present at NeurIPS would facilitate valuable interactions and follow-up; but my confidence in this judgement is low since we didn’t manage a full discussion to convergence during the rebuttal process.
Decision: Accept (poster)