Learning Certified Individually Fair Representations

Anian Ruoss, Mislav Balunovic, Marc Fischer, Martin T. Vechev

Abstract: Fair representation learning provides an effective way of enforcing fairness constraints without compromising utility for downstream users. A desirable family of such fairness constraints, each requiring similar treatment for similar individuals, is known as individual fairness. In this work, we introduce the first method that enables data consumers to obtain certificates of individual fairness for existing and new data points. The key idea is to map similar individuals to close latent representations and leverage this latent proximity to certify individual fairness. That is, our method enables the data producer to learn and certify a representation where for a data point all similar individuals are at $\ell_\infty$-distance at most $\epsilon$, thus allowing data consumers to certify individual fairness by proving $\epsilon$-robustness of their classifier. Our experimental evaluation on five real-world datasets and several fairness constraints demonstrates the expressivity and scalability of our approach.

Introduction

Machine learning models often inherit or amplify human biases, leading to discriminatory outcomes in sensitive domains such as credit scoring, hiring, and criminal risk assessment. While "statistical fairness"—ensuring groups have similar average outcomes—is a common metric, it provides no guarantees for individuals. Individual fairness, the principle that similar individuals should be treated similarly, is a more robust goal but has historically been difficult to enforce and mathematically certify.

A significant challenge exists in the common "producer-consumer" data pipeline. A data producer (e.g., a credit bureau) transforms raw data into a representation, which a data consumer (e.g., a bank) then uses for downstream predictions. The consumer may wish to ensure their model is fair but often lacks access to the original sensitive attributes or the specific similarity metrics used by the producer. This work introduces LCIFR, the first framework designed to bridge this gap by providing modular certificates of individual fairness.

The LCIFR Framework

The LCIFR system involves three primary roles: a regulator who defines fairness constraints, a producer who encodes the data, and a consumer who classifies it. The core innovation lies in reframing individual fairness as a local robustness problem within a latent space.

The LCIFR producer-consumer pipeline for learning and certifying individually fair representations.

As illustrated in Figure 1, the process follows a modular path:

  1. Logical Enforcement: The regulator defines similarity using logical constraints (e.g., "two individuals are similar if they differ only by race"). The producer uses the DL2 tool to translate these constraints into a differentiable loss function, training an encoder to map similar individuals into a small $\ell_\infty$-ball of radius $\delta$ in the latent space.
  2. Producer Certification: For any given data point, the producer calculates the smallest radius $\epsilon$ in the latent space that encompasses all individuals logically defined as "similar" to that point. This is solved exactly using Mixed-Integer Linear Programming (MILP).
  3. Consumer Certification: The producer passes the latent representation $z$ and the radius $\epsilon$ to the consumer. The consumer then proves that their classifier is robust—meaning it yields the same output for every point within that $\epsilon$-radius ball. If robustness is proven (again via MILP), the entire end-to-end system is certified as individually fair for that specific individual.

Experimental Evaluation

The researchers evaluated LCIFR on six real-world datasets: Adult (income), Compas (recidivism), Crime (violent crime levels), German (credit risk), Health (mortality), and Law School (bar exam passage). The evaluation focused on the trade-off between predictive accuracy and the percentage of individuals for whom fairness could be mathematically certified.

Accuracy and certification rates for LCIFR vs. baseline across various datasets and constraints.

As shown in Figure 2, LCIFR achieves massive gains in certification rates compared to standard training. For instance, on the Crime dataset under noise constraints, certification jumped from 7.4% to 66.9%. Notably, these gains come with minimal impact on accuracy. On the Adult dataset, LCIFR achieved 100% certification for categorical constraints while maintaining over 83% accuracy. Furthermore, the method proved efficient; despite the use of MILP, the average certification time per input was less than one second for most datasets.

Key Insights and Conclusion

LCIFR demonstrates that individual fairness can be effectively managed by "squeezing" similar individuals together in a latent space, allowing downstream users to treat fairness as a geometric stability problem. This approach offers transferable fairness, where a representation made fair for one task (e.g., mortality prediction) remains fair and useful when transferred to related tasks (e.g., specific medical condition prediction).

While the current implementation scales to networks with hundreds of hidden neurons, future work is needed to apply these exact certificates to massive "foundation models." Additionally, the framework's success depends on the regulator's ability to provide a socially sufficient definition of similarity. Despite these challenges, LCIFR represents a major step toward verifiable and modular fairness in machine learning pipelines.

Summary updated

Abstract

Fair representation learning provides an effective way of enforcing fairness constraints without compromising utility for downstream users. A desirable family of such fairness constraints, each requiring similar treatment for similar individuals, is known as individual fairness. In this work, we introduce the first method that enables data consumers to obtain certificates of individual fairness for existing and new data points. The key idea is to map similar individuals to close latent representations and leverage this latent proximity to certify individual fairness. That is, our method enables the data producer to learn and certify a representation where for a data point all similar individuals are at $\ell_\infty$-distance at most $\epsilon$, thus allowing data consumers to certify individual fairness by proving $\epsilon$-robustness of their classifier. Our experimental evaluation on five real-world datasets and several fairness constraints demonstrates the expressivity and scalability of our approach.
BibTeX
@inproceedings{ruoss2020learning,
  author = {Anian Ruoss and Mislav Balunovic and Marc Fischer and Martin T. Vechev},
  title = {{Learning Certified Individually Fair Representations}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=Pe-aGb1XfF},
}
Figure