From Pseudorandomness to Multi-Group Fairness and Back
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.
Code (0)
등록된 구현이 없습니다.
Tasks
FairnessLEMMASimilar Papers 제목 키워드 기반
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness
We prove several results giving new and stronger connections between learning, circuit lower bounds and pseudorandomness. Among other results, we show a generic learning speedup lemma, equivalences between various learni…
LEMMAFairness Perceptions in Regression-based Predictive Models
Regression-based predictive analytics used in modern kidney transplantation is known to inherit biases from training data. This leads to social discrimination and inefficient organ utilization, particularly in the contex…
FairnessregressionOptimal Detection for Language Watermarks with Pseudorandom Collision
Text watermarking plays a crucial role in ensuring the traceability and accountability of large language model (LLM) outputs and mitigating misuse. While promising, most existing methods assume perfect pseudorandomness. …
A fairness-aware extension of Stochastic Multicriteria Acceptability Analysis for ranking
Fairness has become a central concern in ranking problems involving individuals or social groups, particularly under the Responsible Artificial Intelligence agenda. In Multi-Criteria Decision Analysis, Stochastic Multicr…
Fair Performance Metric Elicitation
What is a fair performance metric? We consider the choice of fairness metrics through the lens of metric elicitation -- a principled framework for selecting performance metrics that best reflect implicit preferences. The…
Fairness