The literature on fairness in machine learning has yet to settle on definitions. At a high level, there are two families of fairness definitions. "Individual" definitions of fairness ask for semantically meaningful constraints that bind at the level of individuals. When these constraints are defined with respect to the unknown labels, they are often impossible to satisfy. "Statistical" definitions of fairness ask for equality of some error metric (like false positive rate) evaluated over "protected" populations. These are easy to check and satisfy, but don't provide guarantees to individuals.

We show that some of the benefits of both definitions can be obtained if one posits a distribution on problems, in addition to a distribution on datapoints. For example, one may ask that the error rates of false positive rates be equalized between every pair of individuals, where now the "rate" is an average over problems, and not an average over people. This now corresponds to a meaningful promise to individuals. We give oracle-efficient algorithms for optimizing classification error subject to this constraint, and prove generalization bounds over -both- distributions (so that we can make promises both to new individuals and over new problems).

Joint work with Michael Kearns and Saeed Sharifimalvajerdi.