Finding Simple Models of Complex Objects: From Regularity Lemmas to Algorithmic Fairness

Abstract

In this thesis, we study connections between the recent literature on multi-group fairness for prediction algorithms and previous well-known results in graph theory, computational complexity, additive combinatorics, information theory, and cryptography. Our starting point are the definitionsof multiaccuracy and multicalibration, which have established themselves as mathematical measures of algorithmic fairness. Multicalibration guarantees accurate (calibrated) predictions for every subpopulation that can be identified within a specified class of computations, whereas multiaccuracy is a strictly weaker notion which only guarantees accuracy on average. The task of building multiaccurate predictors is closely related to the well-known regularity lemma, which is an older result in computational complexity. This is a central theorem that has many important implications in different areas, including the weak Szemerédi regularity lemma in graph theory, Impagliazzo’s Hardcore Lemma in complexity theory, the Dense Model Theorem in additive combinatorics, computational analogues of entropy in information theory, and weaker notions of zero-knowledge in cryptography. The relationship between multiaccuracy and the regularity lemma thus implies that a multiaccurate predictor can prove all of these fundamental theorems. By formalizing this observation, we then ask: If we start with a multicalibrated predictor instead, what strengthened and more general versions of these fundamental theorems do we obtain? Through the lenses of multi-group fairness, we are able to cast the notion of multicalibration back into the realm of complexity theory and obtain stronger and more general versions of Impagliazzo’s Hardcore Lemma, characterizations of pseudoentropy, and the Dense Model Theorem. Moreover, along the way, we present a unified approach of all these fundamental theorems.