Complexity-Theoretic Implications of Multicalibration
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914890119118848 |
|---|---|
| author | Casacuberta, Sílvia Dwork, Cynthia Vadhan, Salil |
| author_facet | Casacuberta, Sílvia Dwork, Cynthia Vadhan, Salil |
| contents | We present connections between the recent literature on multigroup fairness for prediction algorithms and classical results in computational complexity. Multiaccurate predictors are correct in expectation on each member of an arbitrary collection of pre-specified sets. Multicalibrated predictors satisfy a stronger condition: they are calibrated on each set in the collection. Multiaccuracy is equivalent to a regularity notion for functions defined by Trevisan, Tulsiani, and Vadhan (2009). They showed that, given a class $F$ of (possibly simple) functions, an arbitrarily complex function $g$ can be approximated by a low-complexity function $h$ that makes a small number of oracle calls to members of $F$, where the notion of approximation requires that $h$ cannot be distinguished from $g$ by members of $F$. This complexity-theoretic Regularity Lemma is known to have implications in different areas, including in complexity theory, additive number theory, information theory, graph theory, and cryptography. Starting from the stronger notion of multicalibration, we obtain stronger and more general versions of a number of applications of the Regularity Lemma, including the Hardcore Lemma, the Dense Model Theorem, and the equivalence of conditional pseudo-min-entropy and unpredictability. For example, we show that every boolean function (regardless of its hardness) has a small collection of disjoint hardcore sets, where the sizes of those hardcore sets are related to how balanced the function is on corresponding pieces of an efficient partition of the domain. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_17223 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Complexity-Theoretic Implications of Multicalibration Casacuberta, Sílvia Dwork, Cynthia Vadhan, Salil Computational Complexity Computers and Society We present connections between the recent literature on multigroup fairness for prediction algorithms and classical results in computational complexity. Multiaccurate predictors are correct in expectation on each member of an arbitrary collection of pre-specified sets. Multicalibrated predictors satisfy a stronger condition: they are calibrated on each set in the collection. Multiaccuracy is equivalent to a regularity notion for functions defined by Trevisan, Tulsiani, and Vadhan (2009). They showed that, given a class $F$ of (possibly simple) functions, an arbitrarily complex function $g$ can be approximated by a low-complexity function $h$ that makes a small number of oracle calls to members of $F$, where the notion of approximation requires that $h$ cannot be distinguished from $g$ by members of $F$. This complexity-theoretic Regularity Lemma is known to have implications in different areas, including in complexity theory, additive number theory, information theory, graph theory, and cryptography. Starting from the stronger notion of multicalibration, we obtain stronger and more general versions of a number of applications of the Regularity Lemma, including the Hardcore Lemma, the Dense Model Theorem, and the equivalence of conditional pseudo-min-entropy and unpredictability. For example, we show that every boolean function (regardless of its hardness) has a small collection of disjoint hardcore sets, where the sizes of those hardcore sets are related to how balanced the function is on corresponding pieces of an efficient partition of the domain. |
| title | Complexity-Theoretic Implications of Multicalibration |
| topic | Computational Complexity Computers and Society |
| url | https://arxiv.org/abs/2312.17223 |