Probably Approximately Metric-Fair Learning

By Guy N. Rothblum, Gal Yona. 2018

93 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Prediction-Based Decisions and Fairness: A Catalogue of Choices, Assumptions, and Definitions (2018, background): “Rothblum and Yona relax the metric fairness condition [113]: • ( α 1 , α 2 , γ ) Approximate metric fairness: | {z } Informally, they say a person is α 2 -discriminated against if the fraction of people treated γ -diﬀerently from them exceeds α 2 .”
Fairness Through Computationally-Bounded Awareness (2018, background): “Rothblum and Yona [22] study fair machine learning under a different relaxation of metric fairness, which they call approximate metric fairness.”
The Frontiers of Fairness in Machine Learning (2018, background): “rom a speciﬁc learnable family, this kind of feedback is suﬃcient to obtain an optimal regret bound to the best fair classiﬁer while having only a bounded number of violations of the fairness metric. [RY18] consider the case in which the metric is known, and show that a PAC-inspired approximate vari”
Multiaccuracy: Black-Box Post-Processing for Fairness in Classification (2018, background): “These works fit into the larger literature on fairness in learning and prediction tasks [2, 7, 8, 11, 19, 26, 33], discussions of the utility-fairness tradeoffs in fair classification [1, 3–5, 20, 25].”
Preventing undesirable behavior of intelligent machines (2019, background): “Rothblum and Yona [122] extended this definition by introducing approximate metric fairness, which incorporates a tolerance parameter, γ, to obtain PAC-style generalization bounds on metric fairness.”
Individual Fairness in Pipelines (2020, background): “There is a wide variety of work concerning fairness in machine learning [9, 14, 25, 17, 3, 18, 26, 22, 10, 16, 15, 11, 12, 20, 19, 4, 24, 5].”
A Framework for Understanding Unintended Consequences of Machine Learning (2019, background): “• Individual Fairness (Louizos et al., 2015; Yona and Rothblum, 2018) requires that individuals who are similar with respect to the prediction task are treated similarly.”
Aligning AI With Shared Human Values (2020, background): “However, similarity has been defined in terms of an arbitrary metric; some have proposed learning this metric from data (Kim et al., 2018; Gillen et al., 2018; Rothblum and Yona, 2018), but we are not aware of any practical implementations of this, and the required metrics may be unintuitive to huma”
Individual Fairness in Hindsight (2018, background): “ compelling notion of fairness was proposedin the inﬂuential work of Dwork et al. (2012) in the context of classiﬁcation in supervised learning, and has since been studied under several settings (see Yona and Rothblum 2018, Dwork and Ilvento 2018, Heidari and Krause 2018). The key idea is to introdu”
Eliciting and Enforcing Subjective Individual Fairness (2019, background): “Finally, Rothblum and Yona [2018] prove similar generalization guarantees to ours in the context of individual-metric fairness.”