Abstract
This paper investigates the fundamental theoretical limits of data representations that simultaneously satisfy three criteria: utility for a downstream task, perfect demographic parity (fairness), and a specific compression rate. By leveraging information-theoretic tools such as the Functional Representation Lemma (FRL), the authors establish upper and lower bounds on the amount of task-relevant information that can be preserved in a representation that is strictly independent of a sensitive attribute. The work moves beyond traditional Markov chain assumptions, providing a more general framework for understanding the trade-offs between utility, privacy, and compression.
Introduction
In modern machine learning, ensuring fairness often involves achieving demographic parity, where a model's decisions are statistically independent of sensitive attributes such as race, gender, or age. However, practitioners face a complex three-way trade-off between:
- Utility: Maximizing information relevant to a specific task $T$.
- Fairness/Privacy: Ensuring the representation $Y$ contains zero information about a sensitive attribute $S$.
- Compression: Limiting the encoding rate $I(Y; X)$ to remove noise or meet bandwidth constraints.
While previous literature has explored pairwise trade-offs, this work addresses the regime of perfect fairness ($I(Y; S) = 0$) while explicitly considering compression constraints. The authors define the problem as an optimization of task information subject to independence and rate constraints.
Theoretical Framework
The authors frame the problem through two primary optimization objectives. The first seeks to maximize $I(Y; T)$ subject to $I(Y; S) = 0$ and a rate constraint $I(Y; X) \leq r$. The second variation, inspired by the "Conditional Fairness Bottleneck," focuses on maximizing task information that is not shared with the secret.
To derive bounds, the authors employ the Functional Representation Lemma (FRL) and its "Strong" variant. These tools allow for the construction of a representation $Y$ that is independent of $S$ while remaining maximally correlated with $T$. To satisfy specific compression rates $r$, they introduce randomization techniques that "mix" informative representations with constant values, enabling a smooth utility-rate trade-off.
Key Insights
- Equivalence of Fairness and Privacy: From an information-theoretic standpoint, achieving perfect demographic parity is mathematically identical to achieving perfect secrecy. The tools developed here apply equally to both fields.
- Generalization Beyond Markov Chains: Unlike many prior works, this study does not assume a rigid $S, T \to X \to Y$ Markov structure. This allows the results to apply to a broader range of data dependencies found in real-world structures.
- Tightness in Deterministic Regimes: A significant finding is that if the sensitive attribute $S$ is a deterministic function of the task $T$, the derived lower bounds are actually optimal (tight).
Results and Limits
The paper provides explicit mathematical formulas for utility bounds. A central finding is that the maximum utility $I(Y; T)$ is fundamentally capped by the conditional entropy $H(T|S)$. The results quantify the "utility cost" of compression, showing exactly how much task information must be sacrificed as the rate constraint $r$ is tightened. Furthermore, the authors identify specific high-rate regimes where the "Fairness Bottleneck" can be solved optimally, achieving the maximum possible utility allowed by the fairness constraint.
Conclusion and Future Work
This work establishes a rigorous foundation for perfectly fair compressed representations. However, several avenues for future research remain. The current analysis of the Conditional Fairness Bottleneck is limited to rates above a certain threshold. Additionally, while this paper focuses on perfect demographic parity, extending these tight bounds to approximate fairness or other metrics like "Equalized Odds" represents a significant next step for the field.
Summary updated