From Pseudorandomness to Multi-Group Fairness and Back
Abstract
We identify and explore connections between the recent literature on multi-group fairness for prediction algorithms and the pseudorandomness notions of leakage-resilience and graph regularity. We frame our investigation using new, statistical distance-based variants of multicalibration that are closely related to the concept of outcome indistinguishability. Adopting this perspective leads us naturally not only to our graph theoretic results, but also to new, more efficient algorithms for multicalibration in certain parameter regimes and a novel proof of a hardcore lemma for real-valued functions.
Cite
Text
Dwork et al. "From Pseudorandomness to Multi-Group Fairness and Back." Conference on Learning Theory, 2023.Markdown
[Dwork et al. "From Pseudorandomness to Multi-Group Fairness and Back." Conference on Learning Theory, 2023.](https://mlanthology.org/colt/2023/dwork2023colt-pseudorandomness/)BibTeX
@inproceedings{dwork2023colt-pseudorandomness,
title = {{From Pseudorandomness to Multi-Group Fairness and Back}},
author = {Dwork, Cynthia and Lee, Daniel and Lin, Huijia and Tankala, Pranay},
booktitle = {Conference on Learning Theory},
year = {2023},
pages = {3566-3614},
volume = {195},
url = {https://mlanthology.org/colt/2023/dwork2023colt-pseudorandomness/}
}