Tolerance-Based Fairness Auditing: Violation Certification and Sensitivity Screening

Jie Tang; Chuanlong Xie; Lixing Zhu

stat.MLOct 1, 2026

Tolerance-Based Fairness Auditing: Violation Certification and Sensitivity Screening

Authors: Jie Tang, Chuanlong Xie, Lixing Zhu

Organizations: School of Statistics, Beijing Normal University, Zhuhai, Guangdong 519087, China

Abstract

As artificial intelligence is increasingly deployed, algorithmic unfairness has raised growing concerns and intensified demands for transparent fairness auditing. In practice, the tolerable degree of algorithmic unfairness depends on the specific legal, ethical, or application context. Given a prespecified tolerance threshold, an important statistical question is how to determine whether a group disparity exceeds the allowable tolerance across different auditing objectives. To address this problem, we develop a unified tolerance-based fairness auditing framework for two complementary auditing objectives: violation certification, which prioritizes control of false violation declarations, and sensitivity screening, which prioritizes reducing missed violations. For the first objective, we develop a constrained empirical likelihood test for formal settings that uses least-favorable-point calibration and can be combined with false flagging rate control for simultaneous subgroup auditing. For the second objective, we develop split empirical likelihood and adjusted split empirical likelihood tests using an adaptive boundary-proxy principle for early-warning settings. Numerical experiments show the distinct error-control--sensitivity trade-offs of these procedures. A COMPAS analysis illustrates the framework in predictive fairness auditing.

Figures & tables

Figure 1 : The theoretical limiting rejection probabilities of the EL, CEL, SEL, and ASEL statistics, together with the CEL2, SEL2, and ASEL2 variants. The threshold is set to $0.1$ , with $\alpha=\alpha_{1}=0.05$ and $\alpha_{2}=0.08$ .

Panel of Figure 2 — Figure 2 : Rejection frequency plots under the symmetric normal model: (a)–(d) correspond to $n=30,100,300,1000$ with $N(\epsilon,1)$ data. The horizontal gray line is the nominal level $\alpha=0.05$ and the vertical dashed line marks $\epsilon=0.25$ .

Panel of Figure 3 — Figure 3 : Rejection frequency plots under the heavy-tailed Student $t$ model: (a)–(d) correspond to $n=30,100,300,1000$ with $t(3)+\epsilon$ data. The horizontal gray line is the nominal level $\alpha=0.05$ and the vertical dashed line marks $\epsilon=0.25$ .

Panel of Figure 4 — Figure 4 : Rejection frequency plots under the right-skewed exponential design $\mathrm{Exp}(\frac{1}{\epsilon})$ : (a)–(d) correspond to $n=30,100,300,1000$ . The horizontal gray line is the nominal level $\alpha=0.05$ and the vertical dashed line marks $\epsilon=0.25$ .

$N(\epsilon,1)$					$\mathrm{Exp}(1/\epsilon)$
$\epsilon$	CEL-BH	SEL-BH	ASEL-BH	$t$ -BH	$\epsilon$	CEL-BH	SEL-BH	ASEL-BH	$t$ -BH
0.00	0.00	0.23	0.30	0.00	0.00	-	-	-	-
0.05	0.00	0.18	0.26	0.00	0.05	0.00	0.32	0.32	0.00
0.10	0.00	0.23	0.38	0.00	0.10	0.00	0.25	0.25	0.00
0.15	0.01	0.28	0.56	0.01	0.15	0.00	0.26	0.26	0.00
0.20	0.04	0.18	0.70	0.03	0.20	0.00	0.40	0.42	0.00

Table 1 : Empirical FFR under the global null

\pi_{1}=0

. Bold entries correspond to the tolerance boundary.

$N(\epsilon,1)$					$\mathrm{Exp}(1/\epsilon)$
$\delta$	CEL-BH	SEL-BH	ASEL-BH	$t$ -BH	$\delta$	CEL-BH	SEL-BH	ASEL-BH	$t$ -BH
0.05	0.0092	0.0319	0.1562	0.0054	0.05	0.1042	0.1408	0.3692	0.0058
0.20	0.1165	0.1785	0.4638	0.0908	0.10	0.5988	0.5635	0.6931	0.2827
0.25	0.2854	0.3238	0.5858	0.2485	0.15	0.8735	0.8415	0.8896	0.7496
0.35	0.6235	0.6123	0.7915	0.5912	0.20	0.9619	0.9446	0.9596	0.9127
0.50	0.9112	0.8881	0.9496	0.8973	0.25	0.9915	0.9858	0.9896	0.9796

Table 2 : Empirical power for selected configurations with

\pi_{1}=1

Panel of Figure 5 — Figure 5 : Empirical FFR and power under the normal (top) and exponential (bottom) designs. The dashed lines mark the nominal FFR level $0.05$ .

Nominal level	EL	CEL	SEL	ASEL
90%	0.0212	0.0251	0.0209	0.0235
95%	0.0180	0.0212	0.0175	0.0235

Table 3 : Lower bounds for the African-American group at nominal levels 90% and 95%.

Panel of Figure 6 — Figure 6 : Pointwise inversion regions for the COMPAS PPV disparity of each African-American subgroup relative to the entire Caucasian reference group. Top row: 90% nominal level and bottom row: 95% nominal level.

Panel of Figure 7 — Figure 7 : Pointwise inversion regions for the COMPAS PPV disparity of each subgroup formed by intersections of age and sex relative to the entire Caucasian reference group. Top row: 90% nominal level and bottom row: 95% nominal level.

Panel of Figure 8 — Figure 8 : Pointwise inversion regions for the COMPAS PPV disparity of each female subgroup defined by the intersection of race and age relative to the overall PPV among defendants receiving a positive COMPAS prediction. Top row: 90% nominal level; bottom row: 95% nominal level. Six race–age intersection subgroups are omitted because the corresponding cell sizes fall below the minimum of $n=8$ : $\!<25$ , Hispanic ; $\!<25$ , Other ; $25$ – $45$ , Hispanic ; $25$ – $45$ , Native American ; $>45$ , Hispanic ; and $>45$ , Native American .

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 12 — Figure A.1 : Rejection-frequency behavior for lower-tail tolerance auditing under the symmetric normal model and the heavy-tailed Student $t$ model: (a)–(b) correspond to $n=100,1000$ under the normal model, and (c)–(d) correspond to $n=100,1000$ under the heavy-tailed Student $t$ model. The horizontal gray line is the nominal level $\alpha=0.05$ . The vertical dashed line marks the null boundary.

Explore similar work

Fairness Auditing: Lower Bounds on Company Manipulation
Aug 1, 2026Rachit Verma, Padala Manisha, Sujit GujarFairness Audits Algorithmic Fairness
Indian Institute of Technology Gandhinagar · International Institute of Information Technology Hyderabad
Sequential Fairness Auditing with Limited Output Access
Jun 29, 2026Ioannis Pitsiorlas, Martha V. Sourla, Marios KountourisFairness Audits Algorithmic Fairness
EURECOM, France · DaSCI, University of Granada, Spain
How Reliable are Fairness Audits with Unreliable Data?
Jun 28, 2025Yash Vardhan TomarFairness Audits False-Negative Rate
Purdue University

Aug 1, 2026, cs.LGJ/K move · Enter open · S save

Fairness Auditing: Lower Bounds on Company Manipulation

Rachit Verma, Padala Manisha, Sujit Gujar

Indian Institute of Technology Gandhinagar · International Institute of Information Technology Hyderabad

Fairness Audits Algorithmic Fairness Model Auditing Lower Bounds

Open paper AskPDF arXiv

Fairness audits are increasingly mandated in high-stakes applications such as hiring, lending, and automated decision-making. Recent work has established fundamental impossibility results for black-box fairness auditing, showing that sufficiently expressive models can evade any auditing strategy. We complement these results by quantifying the extent of unavoidable post-audit manipulation under finite audit resources. We formulate fairness auditing as a min-max optimization between a computationally unbounded company and a budget-constrained auditor. We study two auditing regimes: (i) a budgeted auditor that certifies fairness using a fixed-size audit set, and (ii) a budgeted α-tolerant auditor that additionally requires the audit set to estimate the fairness of the certified model within an α approximation. For both settings, we derive explicit lower bounds on the worst-case post-audit demographic parity deviation as functions of the audit budget, group imbalance, and fairness tolerance. Finally, we empirically illustrate these theoretical limits using simple audit-set construction heuristics with linear and neural network classifiers. Our results demonstrate that increasing audit resources reduces, but does not eliminate, the scope for post-audit manipulation, highlighting fundamental limitations of finite-budget fairness certification.

Abstract

Explore similar work

Fairness Auditing: Lower Bounds on Company Manipulation

Sequential Fairness Auditing with Limited Output Access

How Reliable are Fairness Audits with Unreliable Data?