A Complexity-Theoretic Perspective on Algorithmic Fairness

Wednesday, June 19, 2019 - 11:30am - 12:20pm
Lind 305
Omer Reingold (Stanford University)
A prominent concern, in the age of machine learning and data analysis, is that left to their own devices, algorithms will propagate - even amplify - existing biases. Common definitions of fairness are group-based, typically requiring that a given statistic be equal across a few demographic groups, socially identified as deserving protection. Such definitions tend to be easy to study and satisfy but tend to provide exceedingly weak protection from unfair discrimination. This motivated the introduction of definitions that aim at individual-level protections. Such protection is much stronger and more nuanced but harder to satisfy.

We will discuss a recent sequence of results, where protection is provided to a large collection of populations, defined complexity-theoretically. This gives a surprising approach to a question that has been debated by a variety of scientific communities – which population should be protected? Our approach suggests protecting every group that can be identified given the data and our computational limitations, which in a sense is the best we can hope to do. We will discus this approach in different contexts as well as its relation to pseudorandomness.

Based on joint works with Cynthia Dwork, Úrsula Hébert-Johnson, Michael P. Kim, Guy Rothblum and Gal Yona.