# Probably Approximately Metric-Fair Learning

arXiv: https://arxiv.org/abs/1803.03242 · HTML: https://mlsanity.com/paper/1803.03242/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2018.

## Built on by (most cited first, 29 of 29)

- [Aligning AI With Shared Human Values](https://mlsanity.com/paper/2008.02275/) (2020)
- [A Survey on Intersectional Fairness in Machine Learning: Notions, Mitigation, and Challenges](https://mlsanity.com/paper/2305.06969/) (2023)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [A Sociotechnical View of Algorithmic Fairness](https://mlsanity.com/paper/2110.09253/) (2021)
- [An Algorithmic Framework for Bias Bounties](https://mlsanity.com/paper/2201.10408/) (2022)
- [Learning fair representation with a parametric integral probability metric](https://mlsanity.com/paper/2202.02943/) (2022)
- [An Axiomatic Theory of Provably-Fair Welfare-Centric Machine Learning](https://mlsanity.com/paper/2104.14504/) (2021)
- [Omnipredictors for Constrained Optimization](https://mlsanity.com/paper/2209.07463/) (2022)
- [Surfacing Biases in Large Language Models using Contrastive Input Decoding](https://mlsanity.com/paper/2305.07378/) (2023)
- [SoK: Machine Learning Governance](https://mlsanity.com/paper/2109.10870/) (2021)
- [Toward Operationalizing Pipeline-aware ML Fairness: A Research Agenda for Developing Practical Guidelines and Tools](https://mlsanity.com/paper/2309.17337/) (2023)
- [Individually Fair Learning with One-Sided Feedback](https://mlsanity.com/paper/2206.04475/) (2022)
- [SLIDE: a surrogate fairness constraint to ensure fairness consistency](https://mlsanity.com/paper/2202.03165/) (2022)
- [Monotone Individual Fairness](https://mlsanity.com/paper/2403.06812/) (2024)
- [Towards a Responsible AI Development Lifecycle: Lessons From Information Security](https://mlsanity.com/paper/2203.02958/) (2022)
- [Metric-Fair Classifier Derandomization](https://mlsanity.com/paper/2206.07826/) (2022)
- [Fair Without Leveling Down: A New Intersectional Fairness Definition](https://mlsanity.com/paper/2305.12495/) (2023)
- [Intersectional Fairness via Mixed-Integer Optimization](https://mlsanity.com/paper/2601.19595/) (2026)
- [Computability, Complexity, Consistency and Controllability: A Four C's Framework for cross-disciplinary Ethical Algorithm Research](https://mlsanity.com/paper/2102.04234/) (2021)
- [Non-Comparative Fairness for Human-Auditing and Its Relation to Traditional Fairness Notions](https://mlsanity.com/paper/2107.01277/) (2021)
- [Toward a Fairness-Aware Scoring System for Algorithmic Decision-Making](https://mlsanity.com/paper/2109.10053/) (2021)
- [Comparing Apples to Oranges: Learning Similarity Functions for Data Produced by Different Distributions](https://mlsanity.com/paper/2208.12731/) (2022)
- [Identifying, measuring, and mitigating individual unfairness for supervised learning models and application to credit risk models](https://mlsanity.com/paper/2211.06106/) (2022)
- [A Flexible Fairness Framework with Surrogate Loss Reweighting for Addressing Sociodemographic Disparities](https://mlsanity.com/paper/2503.16836/) (2025)
- [Toward Substantive Intersectional Algorithmic Fairness: Desiderata for a Feminist Approach](https://mlsanity.com/paper/2508.17944/) (2025)
- [Sy-FAR: Symmetry-based Fair Adversarial Robustness](https://mlsanity.com/paper/2509.12939/) (2025)
- [Equitable Evaluation via Elicitation](https://mlsanity.com/paper/2602.21327/) (2026)
- [Representation Fidelity:Auditing Algorithmic Decisions About Humans Using Self-Descriptions](https://mlsanity.com/paper/2603.05136/) (2026)
- [A Geometric Theory of Robust Fairness Audits](https://mlsanity.com/paper/2608.24818/) (2026)

## Abstract (arXiv)

The seminal work of Dwork em et al. [ITCS 2012] introduced a metric-based notion of individual fairness. Given a task-specific similarity metric, their notion required that every pair of similar individuals should be treated similarly. In the context of machine learning, however, individual fairness does not generalize from a training set to the underlying population. We show that this can lead to computational intractability even for simple fair-learning tasks. With this motivation in mind, we introduce and study a relaxed notion of em approximate metric-fairness: for a random pair of individuals sampled from the population, with all but a small probability of error, if they are similar then they should be treated similarly. We formalize the goal of achieving approximate metric-fairness simultaneously with best-possible accuracy as Probably Approximately Correct and Fair (PACF) Learning. We show that approximate metric-fairness em does generalize, and leverage these generalization guarantees to construct polynomial-time PACF learning algorithms for the classes of linear and logistic predictors.