mlsanityData to 7 Oct 2026

From Pseudorandomness to Multi-Group Fairness and Back

arXiv 2301.08837 ↗First posted 21 Jan 2023cs.LG cs.CCcited by 13

Not on the map. Why?

Abstract (arXiv)

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 variants of multicalibration based on statistical distance and closely related to the concept of outcome indistinguishability. Adopting this perspective leads us not only to new, more efficient algorithms for multicalibration, but also to our graph theoretic results and a proof of a novel hardcore lemma for real-valued functions.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 10 of its 47 references that are in the map. First posted on arXiv 21 Jan 2023.

Builds on

10 of 47 references.

References · 10

  1. 2016Inherent Trade-Offs in the Fair Determination of Risk Scorescited by 582
  2. 2014Convex Optimization: Algorithms and Complexitycited by 569
  3. 2017Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairnesscited by 381
  4. 2018Multiaccuracy: Black-Box Post-Processing for Fairness in Classificationcited by 221
  5. 2020Outcome Indistinguishabilitycited by 74
  6. 2021Omnipredictorscited by 71
  7. 2020Moment Multicalibration for Uncertainty Estimationcited by 63
  8. 2022Loss Minimization through the Lens of Outcome Indistinguishabilitycited by 61
  9. 2021Online Multivalid Learning: Means, Moments, and Prediction Intervalscited by 48
  10. 2022Low-Degree Multicalibrationcited by 44

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 5; 2025: 7; 2026: 1.

13 papers.

Sort:

  1. 2024On Computationally Efficient Multi-Class Calibrationcited by 16
  2. 2024When is Multicalibration Post-Processing Necessary?cited by 16
  3. 2024Omnipredictors for Regression and the Approximate Rank of Convex Functionscited by 14
  4. 2025How Global Calibration Strengthens Multiaccuracycited by 8
  5. 2025When does a predictor know its own loss?cited by 7
  6. 2024Active Fourier Auditor for Estimating Distributional Properties of ML Modelscited by 6
  7. 2025Generalized and Unified Equivalences between Hardness and Pseudoentropycited by 5
  8. 2025Improved Bounds for Swap Multicalibration and Swap Omnipredictioncited by 4
  9. 2025Calibration through the Lens of Indistinguishabilitycited by 4
  10. 2026An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Phi-Regret Minimizationcited by 3
  11. 2024Rules, Cases, and Reasoning: Positivist Legal Theory as a Framework for Pluralistic AI Alignmentcited by 2
  12. 2025Supersimulatorscited by 2
1 more
  1. 2025Sample-efficient Multiclass Calibration under ℓp Errorcited by 1