# Probabilistic Verification of Fairness Properties via Concentration

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Dec 2018.

## Built on by (most cited first, 30 of 45)

- [Trustworthy AI: A Computational Perspective](https://mlsanity.com/paper/2107.06641/) (2021)
- [Causality-based Neural Network Repair](https://mlsanity.com/paper/2204.09274/) (2022)
- [Fair Normalizing Flows](https://mlsanity.com/paper/2106.05937/) (2021)
- [Individual Fairness Guarantees for Neural Networks](https://mlsanity.com/paper/2205.05763/) (2022)
- [Fairify: Fairness Verification of Neural Networks](https://mlsanity.com/paper/2212.06140/) (2022)
- [Latent Space Smoothing for Individually Fair Representations](https://mlsanity.com/paper/2111.13650/) (2021)
- [Probabilistic Verification of Neural Networks Against Group Fairness](https://mlsanity.com/paper/2107.08362/) (2021)
- [CertiFair: A Framework for Certified Global Fairness of Neural Networks](https://mlsanity.com/paper/2205.09927/) (2022)
- [Algorithmic Fairness Verification with Graphical Models](https://mlsanity.com/paper/2109.09447/) (2021)
- [Automatic Fairness Testing of Neural Classifiers through Adversarial Sampling](https://mlsanity.com/paper/2107.08176/) (2021)
- [FairProof : Confidential and Certifiable Fairness for Neural Networks](https://mlsanity.com/paper/2402.12572/) (2024)
- [Certifying Some Distributional Fairness with Subpopulation Decomposition](https://mlsanity.com/paper/2205.15494/) (2022)
- [Certifying Counterfactual Bias in LLMs](https://mlsanity.com/paper/2405.18780/) (2024)
- [Monitoring Algorithmic Fairness](https://mlsanity.com/paper/2305.15979/) (2023)
- [Verifying Fairness in Quantum Machine Learning](https://mlsanity.com/paper/2207.11173/) (2022)
- [Certifying the Fairness of KNN in the Presence of Dataset Bias](https://mlsanity.com/paper/2307.08722/) (2023)
- [Monitoring Algorithmic Fairness under Partial Observations](https://mlsanity.com/paper/2308.00341/) (2023)
- [Fairness Testing of Deep Image Classification with Adequacy Metrics](https://mlsanity.com/paper/2111.08856/) (2021)
- [Provable Fairness for Neural Network Models using Formal Verification](https://mlsanity.com/paper/2212.08578/) (2022)
- [Specifying and Testing k-Safety Properties for Machine-Learning Models](https://mlsanity.com/paper/2206.06054/) (2022)
- [Explainable Global Fairness Verification of Tree-Based Classifiers](https://mlsanity.com/paper/2209.13179/) (2022)
- [Adversarial Sampling for Fairness Testing in Deep Neural Network](https://mlsanity.com/paper/2303.02874/) (2023)
- [Stream-Based Monitoring of Algorithmic Fairness](https://mlsanity.com/paper/2501.18331/) (2025)
- [FETA: Fairness Enforced Verifying, Training, and Predicting Algorithms for Neural Networks](https://mlsanity.com/paper/2206.00553/) (2022)
- [Uncertainty Quantification for Neurosymbolic Programs via Compositional Conformal Prediction](https://mlsanity.com/paper/2405.15912/) (2024)
- [Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound](https://mlsanity.com/paper/2405.17556/) (2024)
- [FairQuant: Certifying and Quantifying Fairness of Deep Neural Networks](https://mlsanity.com/paper/2409.03220/) (2024)
- [Certifying Fairness of Probabilistic Circuits](https://mlsanity.com/paper/2212.02474/) (2022)
- [FairSense: Long-Term Fairness Analysis of ML-Enabled Systems](https://mlsanity.com/paper/2501.01665/) (2025)
- [A Tale of Two Approximations: Tightening Over-Approximation for DNN Robustness Verification via Under-Approximation](https://mlsanity.com/paper/2305.16998/) (2023)

## Abstract (arXiv)

As machine learning systems are increasingly used to make real world legal and financial decisions, it is of paramount importance that we develop algorithms to verify that these systems do not discriminate against minorities. We design a scalable algorithm for verifying fairness specifications. Our algorithm obtains strong correctness guarantees based on adaptive concentration inequalities; such inequalities enable our algorithm to adaptively take samples until it has enough data to make a decision. We implement our algorithm in a tool called VeriFair, and show that it scales to large machine learning models, including a deep recurrent neural network that is more than five orders of magnitude larger than the largest previously-verified neural network. While our technique only gives probabilistic guarantees due to the use of random samples, we show that we can choose the probability of error to be extremely small.