# PAC-Bayesian Generalization Guarantees for Fairness on Stochastic and Deterministic Classifiers

arXiv: https://arxiv.org/abs/2602.11722 · HTML: https://mlsanity.com/paper/2602.11722/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 46 references that are in the map.
- First posted on arXiv 12 Feb 2026.

## Builds on (most cited first, 16 of 16)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Fairness in Machine Learning: A Survey](https://mlsanity.com/paper/2010.04053/) (2020)
- [AI Fairness 360: An Extensible Toolkit for Detecting, Understanding, and Mitigating Unwanted Algorithmic Bias](https://mlsanity.com/paper/1810.01943/) (2018)
- [Quantifying Social Biases in NLP: A Generalization and Empirical Comparison of Extrinsic Fairness Metrics](https://mlsanity.com/paper/2106.14574/) (2021)
- [PAC-Bayes Analysis Beyond the Usual Bounds](https://mlsanity.com/paper/2006.13057/) (2020)
- [Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithm](https://mlsanity.com/paper/1503.08329/) (2015)
- [Second Order PAC-Bayesian Bounds for the Weighted Majority Vote](https://mlsanity.com/paper/2007.13532/) (2020)
- [FFB: A Fair Fairness Benchmark for In-Processing Group Fairness Methods](https://mlsanity.com/paper/2306.09468/) (2023)
- [A General Framework for the Practical Disintegration of PAC-Bayesian Bounds](https://mlsanity.com/paper/2102.08649/) (2021)
- [Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound](https://mlsanity.com/paper/2106.12535/) (2021)
- [Leveraging PAC-Bayes Theory and Gibbs Distributions for Generalization Bounds with Complexity Measures](https://mlsanity.com/paper/2402.13285/) (2024)
- [Fairness Overfitting in Machine Learning: An Information-Theoretic Perspective](https://mlsanity.com/paper/2506.07861/) (2025)
- [A Framework for Bounding Deterministic Risk with PAC-Bayes: Applications to Majority Votes](https://mlsanity.com/paper/2510.25569/) (2025)

## Abstract (arXiv)

Classical PAC generalization bounds on the prediction risk of a classifier are insufficient to provide theoretical guarantees on fairness when the goal is to learn models balancing predictive risk and fairness constraints. We propose a PAC-Bayesian framework for deriving generalization bounds for fairness, covering both stochastic and deterministic classifiers. For stochastic classifiers, we derive a fairness bound using standard PAC-Bayes techniques. Whereas for deterministic classifiers, as usual PAC-Bayes arguments do not apply directly, we leverage a recent advance in PAC-Bayes to extend the fairness bound beyond the stochastic setting. Our framework has two advantages: (i) It applies to a broad class of fairness measures that can be expressed as a risk discrepancy, and (ii) it leads to a self-bounding algorithm in which the learning procedure directly optimizes a trade-off between generalization bounds on the prediction risk and on the fairness. We empirically evaluate our framework with three classical fairness measures, demonstrating not only its usefulness but also the tightness of our bounds.