Timezone: »

Probably Approximately Metric-Fair Learning
Gal Yona · Guy Rothblum

Fri Jul 13 12:50 AM -- 01:10 AM (PDT) @ A6

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.

Author Information

Gal Yona (Weizmann Institute of Science)
Guy Rothblum (Weizmann Institute of Science)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors