Fairness Overfitting in Machine Learning: An Information-Theoretic Perspective

Mismatch in Fairness Definitions for the Multiclass Problem

In our original formulation for the binary case, the prediction function $f =\hat{Y}$ outputs values in $\{0,1\}$ (i.e., a=1). For multiclass problems, we allow $f$ to take values in a bounded range $[0,a]$; however, the choice of $a$ does not affect the upper bound in our fairness guarantees.

To illustrate this in the context of Equalized Odds (EO), consider our use of the Total Variation (TV) loss as a fairness measure. For each true label $y \in \{0,1,2,3\}$, we define the TV loss as follows:

$\ell^{F_S}\_E(w,S \mid Y=y) = \frac{1}{2}\sum\_{c=0}^{3}\Bigl|P(\hat{Y}=c\mid Y=y,T=0)-P(\hat{Y}=c\mid Y=y,T=1)\Bigr|,$ which in practice is approximated by $\ell^{F_S}\_E(w,S \mid Y=y) = \frac{1}{2}\sum\_{c=0}^{3}\left|\frac{n\_{0,y,c}}{n\_{0,y}+2}-\frac{n\_{1,y,c}}{n_{1,y}+2}\right|.$ We then define an aggregate function over the true labels: $g(z_u) = \sum\_{y\in\{0,1,2,3\}} \ell^{F\_S}\_E(w,z_u \mid Y=y)$. Our analysis shows that $\sup\_{z\_u,\tilde{z}\_u^i} |g(z\_u)-g(\tilde{z}\_u^i)| \le \frac{2}{\min\_{(t,y)}\{n^{Z\_u}\_{t,y}+2\}}$ The key point is that—even if the prediction function $f$ is allowed to take any value in $[0,a]$—changing one sample affects the probability estimates (and hence the TV loss) by at most a fixed amount (i.e., at most 1) regardless of $a$. In other words, while $f$’s output may be scaled by $a$, the impact on the fairness loss (measured in terms of probability differences) remains unchanged.

Thus, our technical arguments extend naturally to the multiclass setting. We acknowledge that our previous explanation did not clearly separate the role of the prediction magnitude (bounded by $a$) from the fairness loss itself, and we appreciate the opportunity to clarify that the fairness definitions (including EO) are applicable to the multiclass case under our bounded prediction assumption.

Is the square-integrability assumption to apply the Efron-Stein inequality respected?

Thank you for carefully reading the proof. You are correct that the Efron-Stein inequality assumes square-integrability, and we acknowledge that this assumption was not explicitly stated in Lemma 2 in the paper. However, in our case, this assumption is naturally satisfied because all the random variables involved are bounded. Specifically, as $f$ is bounded ($f<a$), the loss function $l$, for which we apply the Efron-Stein inequality through Lemma 2 (Eq. 65 or Eq 82), is also bounded ($l<a$ see Eq. 190-191 ). Since any bounded random variable is square-integrable, this guarantees that the assumption is met. Formally, we have:
$|l| \leq a.$ To verify square-integrability, we need to show that $\mathbb{E}[l^2] < \infty$. Since $l$ is bounded. We have $X^2 \leq a^2$ Taking expectations on both sides, $\mathbb{E}[l^2] \leq \mathbb{E}[a^2] = a^2 < \infty.$ Thus, our loss is always square-integrable. Therefore, the conditions for applying the Efron-Stein inequality are fully satisfied in our setting.

We will include this clarification and add the assumption explicitly to Lemma 2 in the revised version of the paper to ensure completeness. Given that this addresses your concern, we kindly ask you to reconsider your score. We appreciate your openness to revisiting your evaluation and would be happy to discuss any further points if needed.

Related work:

Thank you for highlighting the related work on generalization guarantees in fair machine learning. We will address these references in the revision. However, while (Woodworth et al., 2017; Agarwal et al., 2018) derive generalization guarantees for loss functions corresponding to DP and EO within specific algorithms, our work targets a more general algorithmic framework in the DP and EO setting—even when using other loss functions. Moreover, their guarantees primarily focus on overall sample complexity, whereas our bounds incorporate not only the total sample size but also additional factors such as the properties of the learning algorithm, the particular loss function, the dataset characteristics, and, importantly, the group balance in the dataset.

More closely related work is Oneto et al. (2019), which derives a generalization bound in Theorem 1 for fairness generalization with randomized algorithms. However, their bound, being a KL-divergence bound, can not be computed and evaluated in practice for any realistic setting. In contrast, our bounds—particularly Theorem 5—are computable, even for modern deep neural networks. This ensures that our results are not only theoretically rigorous but also practical and computable, allowing us to study fairness generalization errors in real-world settings. We will incorporate this discussion into the paper and revise our claim accordingly.

Thank you for catching the typos. We will fix all these typos and the flipped axis labels iof the Figure in the final version.

We appreciate your thoughtful question about deriving lower bounds within our theoretical framework, especially considering existing challenges in achieving group-level fairness notions like Equalized Odds (EOdds). In our work, we focus on understanding how fairness measures observed during training generalize to new, unseen data. While our framework sheds light on the behavior of fairness interventions and their generalization properties, directly deriving explicit lower bounds for the fairness-accuracy trade-off, particularly for specific notions like EOdds, is fundamentally different. In particular, Information-theoretic bounds, including ours, rely on the Donsker-Varadhan variational representation for upper-bound generalization error. Hence, deriving a lower bound would require an alternative variational formulation that directly lower bounds the difference in expectation between the joint distribution and the product of marginals of the specific loss function, which is not trivial.

Regarding the impossibility results, as you've noted, prior research has shown that it's often impossible to satisfy all group-level fairness criteria simultaneously. For instance, Chouldechova (2017) and Kleinberg et al. (2017) discuss inherent trade-offs between different fairness measures. Additionally, Tang and Zhang (2022) highlight that achieving EOdds depends on specific data distribution properties; when these aren't met, deterministic classifiers may struggle to attain EOdds without incorporating randomness into their predictions. The key distinction is that impossibility results establish lower bounds on the population risk for different fairness loss functions, while our contribution provides upper bounds on fairness generalization error. Notably, a model can have low generalization error but still perform poorly in terms of fairness on the population level.

An interesting parallel future direction would be to explore connections between different fairness generalization bounds—for instance, relating DP-fairness generalization error to EO-fairness error. We will incorporate this discussion in the future directions section.

We sincerely appreciate the reviewer’s thoughtful feedback on our work. Below, we address each concern point by point.

Motivation: We respectfully disagree that there is a lack of motivation to study fairness generalization. As demonstrated in Figure 1, i) Compared to ERM, when fairness interventions are applied, the generalization error can become particularly significant (e.g., HSCI or PRemover), indicating that these techniques introduce generalization challenges that need further investigation. ii) In certain cases—especially with low-data— the fairness generalization error can be as high as 10–30% of the fairness training loss, which is significant. iii) Different fairness methods exhibit varying generalization behaviors, suggesting that multiple factors influence fairness generalization. Understanding these variations is essential for developing principled approaches to mitigating fairness-related overfitting.

Experiments: We kindly refer the reviewer to lines 397-404. Estimating our proposed bound follows the well-established protocol (Harutyunyan et al. 2021; Wang & Mao 2023) and particularly Dong et al. (2024), where permutation-based bounds have been proposed for standard generalization error. The main difference is that here: i) we are targeting a fairness loss. ii) MI terms involve a continuous variable.

Q: $a$ and $m$ in practice?
A: $a$ in our paper is the upper bound of the predictor function f. Since in this paper, we consider mainly the binary case {-1,1}, a=1 and does not require any estimation. We will clarify this in the final version.
$m$ is a hyperparameter. Like in our experiments, we recommend setting m=n−1 for practical reasons. ​
Q: Re-training model for each permutation?
A: No, computing the bound does not require retraining for each permutation. It only involves evaluating mutual information estimates over different subsets, with a computational complexity similar to Dong et al. (2024).

Insights from theory:
Theoretical: In this paper, we take a significant step toward addressing fairness generalization errors by deriving the first rigorous computable bounds in the MI and CMI settings, using a novel bounding technique. Our results demonstrate that models generalize differently depending on the fairness approach used, as they memorize the different data attributes (V) at different scales. Furthermore, our bounds shed some light on how data balance influences fairness overfitting.
Practical: Beyond these theoretical insights, generalization bounds can also inform practical strategies for improving fairness performance. As a proof of concept, our results suggest that balanced representation (1/H(n_0,n_1)) reduces fairness generalization errors. To validate this, we experimented with batch-balancing, demonstrating that this indeed improves generalization further confirming our theoretical finding. Note that from this perspective, our work can be seen as a theoretical guarantee for the previous works on data balancing highlighted by the reviewers. Additionally, for example, our findings suggest that controlling the MI term—such as by introducing gradient noise during training—could further improve fairness generalization.

Q: assumptions on A?
A: A learning algorithm is a randomized mapping from the training data $S$ to the model weights $W$. Similar to other information-theoretic studies (e.g., Harutyunyan et al., 2021), we make no assumptions about A.

Q: How to interpret the experimental results? the bound is tight?
A: In general, the primary goal of generalization bounds is not solely tightness—achieving this requires strong additional assumptions—but rather to provide theoretical insights into generalization behavior and capture the key factors. Information-theoretic bounds are generally among the tightest in learning theory. For instance, Wang & Mao (2023) (in Figure 2) report bounds that, while sometimes over four times larger than the observed empirical generalization error, remain valid and notably tighter than previous results, as they successfully capture the overall trends.
In the context of fairness, using prior bounding techniques would yield overly loose bounds that fail to provide meaningful insights into fairness dynamics (see our discussion on Lemma 1). In contrast, our work introduces a novel bounding technique that not only results in tighter fairness bounds compared to previous techniques—e.g., Theorem 1 is tighter than Lemma 1 by a factor of $1/\sqrt{n}$​—but also reveals fairness-specific properties, such as the influence of class balance (n0,n1​). Empirically, our derived bounds consistently track the observed fairness generalization error across different models and datasets, further validating their effectiveness.

Q: p-value?
A: The p-value for the scatter plot is 3.43×10⁻¹⁶, indicating an extremely strong statistical significance further validating our bounds.

We will fix the typos suggested by the reviewer.