Probably Approximately Metric-Fair Learning

Abstract

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.

Published in International Conference on Machine Learning (ICML) 2018

References in corpus (5)

• Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness
• Data Decisions and Theoretical Implications when Adversarially Learning Fair Representations
• A Convex Framework for Fair Regression
• Fairness Through Computationally-Bounded Awareness
• Online Learning with an Unknown Fairness Metric

Cited by in corpus (19)

• Prediction-Based Decisions and Fairness: A Catalogue of Choices, Assumptions, and Definitions
• Fairness in Machine Learning
• Aligning AI With Shared Human Values
• A Framework for Understanding Sources of Harm throughout the Machine Learning Life Cycle
• Online Learning with an Unknown Fairness Metric
• Machine learning fairness notions: Bridging the gap with real-world applications
• Average Individual Fairness: Algorithms, Generalization and Experiments
• Two Simple Ways to Learn Individual Fairness Metrics from Data
• Review of Mathematical frameworks for Fairness in Machine Learning
• Toward Operationalizing Pipeline-aware ML Fairness: A Research Agenda for Developing Practical Guidelines and Tools
• SenSeI: Sensitive Set Invariance for Enforcing Individual Fairness
• Envy-Free Classification
• Moment Multicalibration for Uncertainty Estimation
• SoK: Machine Learning Governance
• Sample Complexity of Uniform Convergence for Multicalibration
• Metric-Free Individual Fairness in Online Learning
• Preference-Informed Fairness
• An Axiomatic Theory of Provably-Fair Welfare-Centric Machine Learning
• Realizable Learning is All You Need