Kernel-based Equalized Odds: A Quantification of Accuracy-Fairness Trade-off in Fair Representation Learning

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.

1. On the Robustness of Our Criterion to Kernel Choice

You 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.

This concern is at the heart of all kernel-based distribution measures, and our framework relies on a powerful, standard resolution from the literature:

• 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.
• 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.

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.

2. Clarifying Our Contribution Relative to Tan et al. (2020)

We 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:

1. 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.
2. 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.
3. 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.

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.

We 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.

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.

To 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.

1. Motivation and Structure (W1, W2, Q1)

You 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.

The revised paper will resolve this by dedicating a new introduction paragraph upfront to the well-established problem our work solves:

• 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.
• 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.

2. Complexity and Computational Cost of metric $\mathrm{EO}_k$ (W3, Q3)

• 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).

  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:

  • 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.
  • 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.

3. Practical Preference and Actionability (W4, Q2)

Finally, 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.

Our revision will dedicate a paragraph to the unique, practical advantages that make $\mathrm{EO}_k$ a more principled choice for practitioners:

• 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.
• 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."
• 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.

We 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.

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.

We 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.

However, 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.

To clarify the points that the new structure will emphasize, we briefly summarize our core contributions below.

Core Contributions & Theoretical Impact (W1 & Q1)

You 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.

Our core contributions are:

• 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.
• 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).
• 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.

On Positioning and Quantitative Comparison (W2, Q2)

Your 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].

The 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.

Therefore, 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.

On the Scope and Framing of our Metric (W3, Q3)

Your 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."

• 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.
• 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.

We 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.

Thank you for your constructive feedback. Per your suggestions, we have added empirical validation and further clarifications below.

1. Empirical Validation and Case Study (in response to Q1)

Part 1: Validation of the $\mathrm{EO}_k$ Generalization Bound

First, we empirically validated our generalization bound.

• Experimental Setup: We conducted a simulation using synthetically generated data with injected bias. For various data dimensions ($d$) and sample sizes ($n$), we compared the empirical $\mathrm{EO}_k$ (calculated on a sample) to its true population value (calculated on 10,000 samples). The $\mathrm{EO}_k$ metric itself was computed using a Maximum Mean Discrepancy (MMD) with an RBF kernel ($\gamma=0.1$). The empirical error, defined as the absolute difference between the empirical and population $\mathrm{EO}_k$, was averaged over 5 trials for each setting.

• Results: The following results confirm our theoretical analysis is sound and that the empirical error respects the theoretical scaling rate of $\sqrt{\log(d)/n}$.

Part 2: Case Study on Practical Trade-offs

We also conducted a case study on the Adult Census dataset ('sex' as the sensitive attribute) using an MLP model with an MMD-based fairness regularizer. The results show our method ($\lambda=50.0$) achieves a Pareto improvement over the baseline:

2. Example of Trade-offs when $\mathrm{EO}_k = 0$ (in response to Q2)

You asked for the mathematical reasoning for how forcing predictive power ($\beta > 0$) leads to fairness violations when $\mathrm{EO}_k = 0$.

Assume we start from a representation where Equalized Odds holds ($Z \perp S | Y$, so $\mathrm{EO}_k = 0$). Now, consider a biased dataset where $Y \not\perp S$. If we seek a model with perfect predictive power ($\beta = 1$), then its prediction $\hat{Y}$ must equal the true outcome $Y$.

1. Violation of Demographic Parity (DP): Given $\hat{Y}^* = Y$, the DP violation is:

DP = |Pr(Y_hat* = 1 | S=1) - Pr(Y_hat* = 1 | S=0)| = |Pr(Y = 1 | S=1) - Pr(Y = 1 | S=0)|

Since the dataset is biased ($Y$ is dependent on $S$), this difference is greater than 0.

2. Violation of Disparate Calibration (DC): Given $h(Z) \perp S | Y$, we can derive the DC value:

Again, since the dataset is biased, this is greater than 0.

3. Extension to Multi-Class Classification (in response to Q3)

The extension is non-trivial. Our binary trick $\mathbb{E}[h(Z)] = \Pr(\hat{Y}=1)$ fails in the multi-class setting. There, the predictor $h(Z)$ outputs a score vector, and the prediction $\hat{Y}$ is the result of a non-linear $\operatorname{argmax}$ operation. The expected score for a class is therefore no longer equivalent to the probability of predicting that class.

We hope these additions and clarifications have adequately addressed the reviewer's concerns. We are grateful for the opportunity to improve our manuscript.