[2312.17223] Complexity-Theoretic Implications of Multicalibration
source link: https://arxiv.org/abs/2312.17223
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Computational Complexity
Complexity-Theoretic Implications of Multicalibration
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.
| Subjects: | Computational Complexity (cs.CC); Computers and Society (cs.CY) |
| Cite as: | arXiv:2312.17223 [cs.CC] |
| (or arXiv:2312.17223v1 [cs.CC] for this version) | |
| https://doi.org/10.48550/arXiv.2312.17223 |
Submission history
From: Sílvia Casacuberta [view email][v1] Thu, 28 Dec 2023 18:53:21 UTC (899 KB)
Recommend
-
8
Type theoretic replacement & the n-truncation This post is to announce a new article that I recently upl...
-
10
08:20 本周灰度BTC增持2312.26枚 BCH增持13298.26枚 据统计，本周灰度信托累计增持2312.26枚BTC（+0.004%）、13298.26枚BCH（+0.05%）、25498.77枚LTC（+0.02%）、20798.92枚ETC（+0.002%）。本周ETH无增持。
-
10
SHAP (SHapley Additive exPlanations) is a game theoretic approach to explain the output of any machine learning model. It connects optimal credit allocation with local explanations using the classic Shapley...
-
2
The Game Theoretic Trap of Cancel Culture — and How to Beat it
-
5
Vague Convergence in Measure-theoretic Probability Theory - Equivalent ConditionsIntroductionIn analysis and probability theory, one studies various sort of convergences (of random variables) for various reasons...
-
7
[Submitted on 1 Dec 2023] What if an SQL Statement Returned a Database? Download PDF Every SQL statemen...
-
4
Pensieve: 2312 2023-12-23 19:18 这个月读书方面继续放假, 全在读之前读过的网络小说. 读完了全职高手, 正在读
-
5
Mathematics > Combinatorics [Submitted on 5 Dec 2023] Conway's Game of Life is Omniperiodic
-
3
Computer Science > Data Structures and Algorithms [Submitted on 20 Dec 2023] O(loglogn) Passes is Optimal for Semi-Streaming Ma...
-
3
Computer Science > Computational Complexity [Submitted on 5 Dec 2023] XOR Lemmas for Communication via Marginal Information...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK