New connections between algorithmic fairness, complexity theory, and learning theory

In this talk, we will present connections between the recent literature on multigroup fairness for prediction algorithms and previous classic results in computational complexity, information theory, additive combinatorics, and learning theory.

In the first part we will focus on the connections to complexity theory. Our starting point is the observation that the existence of low-complexity multiaccurate predictors, as recently defined by Hébert-Johnson, Kim, Reingold, and Rothblum (2018) in the context of algorithmic fairness, is exactly what is given by the complexity-theoretic Regularity Lemma shown by Trevisan, Tulsiani, and Vadhan (2009). In our work, we ask what are the corresponding implications if we start with the stronger statement that low-complexity multicalibrated predictors exist, as proven by Hébert-Johnson et al. Using multicalibrated predictors, we obtain stronger and more general versions of the Hardcore Lemma (Impagliazzo, 1995), the Dense Model Theorem (Green-Tao 2004, Tao-Ziegler 2006, Reingold-Trevisan-Tulsiani-Vadhan 2008), and the equivalence of conditional pseudo-min-entropy and unpredictability (Vadhan-Zheng 2013).

In the second part, we will discuss how multicalibration is related to a new paradigm for loss minimization called omniprediction, which is able to construct a predictor that can optimize any loss function in a pre-specified class of loss functions simultaneously. Through this connection, we are able to recover and generalize previous constructions of optimal reliable classifiers, which are classifiers that are also given the option to abstain, as first defined by Kalai, Kanade, and Mansour in 2009. We further clarify the connections between multiaccuracy and multicalibration, complexity theory, and agnostic learning through reductions between hardcore set constructions and agnostic boosting.

This talk is based on the paper “Complexity-Theoretic Implications of Mulicalibration”, co-authored with Cynthia Dwork and Salil Vadhan (to appear in STOC 2024), and on ongoing work with Varun Kanade.