PaperlayerView exact revision on arXiv

Source-linked AI summary

Statistical Inference for Fairness Auditing

John J. Cherian, Emmanuel J. Candès

arXiv:2305.03712v2stat.MEcs.CYcs.LG

TL;DR

Average model performance can conceal subgroup disparities, while limited-group tests and localized audits often lack statistical guarantees. The paper develops bootstrap-based methods for certifying and flagging disparities; its bounds can hold simultaneously across a collection of groups under stated conditions.

  • Problem

    High average accuracy can conceal substantial subgroup performance disparities, while tests over limited groups and localized audits often lack statistical guarantees.

    Source: §1 · p. 1

  • Method

    The paper uses bootstrap-based simultaneous inference to construct bounds for group disparities and support certification and flagging.

    Source: §1 · p. 1, §3.1.1 · pp. 7–8

  • Results

    Under bounded-metric and finite-VC-dimension conditions, the proposed lower bounds are asymptotically valid simultaneously for all groups in the collection.

    Source: §3.1.1 · p. 8

  • Takeaways & Limitations

    Auditors can use held-out model predictions to flag harmful disparities and certify adequate subpopulations without white-box model access.

    Source: §1 · p. 1

    The Boolean certification method has asymptotic family-wise error rate exactly α only when every group has the same disparity.

    Source: §3.1.2 · p. 10

Abstract

from arXiv · show

Before deploying a black-box model in high-stakes problems, it is important to evaluate the model's performance on sensitive subpopulations. For example, in a recidivism prediction task, we may wish to identify demographic groups for which our prediction model has unacceptably high false positive rates or certify that no such groups exist. In this paper, we frame this task, often referred to as "fairness auditing," in terms of multiple hypothesis testing. We show how the bootstrap can be used to simultaneously bound performance disparities over a collection of groups with statistical guarantees. Our methods can be used to flag subpopulations affected by model underperformance, and certify subpopulations for which the model performs adequately. Crucially, our audit is model-agnostic and applicable to nearly any performance metric or group fairness criterion. Our methods also accommodate extremely rich -- even infinite -- collections of subpopulations. Further, we generalize beyond subpopulations by showing how to assess performance over certain distribution shifts. We test the proposed methods on benchmark datasets in predictive inference and algorithmic fairness and find that our audits can provide interpretable and trustworthy guarantees.

1 Introduction

Average model performance can conceal substantial subgroup disparities, while limited-group tests and localized audits often lack statistical guarantees. The paper develops methods to certify adequate subpopulations and flag harmful disparities, illustrating conditional-coverage guarantees and COMPAS disparity audits.

1 Introduction

  • Prior audits often test only limited subgroup sets, which can miss disparities in smaller groups, while localized disparity methods have few statistical guarantees.Considering many metrics across rich subgroup collections also makes finding some disparity unsurprising.Source: §1 · p. 1
  • The audit needs only model predictions on held-out data, not white-box access, to certify adequate subpopulations and flag harmful disparities.The held-out predictions are called an audit trail.Source: §1 · pp. 1–2

1.1.1 Certifying conditional coverage

  • With 95% confidence, no sub-interval of length 1 has conditional coverage below 80.2%, and none of length 2 below 83.0%.The simultaneous bounds cover the specified endpoint grid; the example includes 1,275 intervals, and the finite restriction can be relaxed.Source: §1.1.1 · p. 3

1.1.2 Flagging false positive rate disparities

  • On COMPAS data for 6,781 individuals, the method flags demographic groups whose false-positive rate among Y=0 cases exceeds the overall Y=0 rate by more than 0.05, controlling expected false-discovery proportion at 10% asymptotically.Source: §1.1.2 · pp. 3–4

2 Set-up and notation

The setup defines performance disparity as a group-conditional metric differing from a target. Audits use held-out data and instantiate this definition for metrics such as false positive rate and conditional coverage.

2 Set-up and notation

  • A performance disparity occurs when a prediction rule’s group-conditional mean metric differs substantially from a target value.The audit tests or bounds the group-wise disparity.Source: §2 · p. 4
  • For false positive rate auditing, the metric is the indicator of a high-risk prediction among negatives, with the population false positive rate as target.The method tests whether a subgroup’s disparity exceeds 0.05.Source: §2 · p. 4
  • For conditional coverage, the metric indicates whether the outcome lies in the prediction set, and the target is 0.9.The example lower-bounds disparity over intervals with endpoints on a specified grid.Source: §2 · p. 4
  • The audit requires a hold-out data set, or audit trail; when the target is unknown, its estimator is assumed consistent and asymptotically linear.The estimator is assumed to have a plug-in form based on known features and a differentiable function.Source: §2 · p. 4

3 Certifying performance

This section develops bootstrap-based methods for certifying group performance disparities with simultaneous guarantees, including for small groups. It illustrates the approach through synthetic audits and a COMPAS analysis of PPV disparities across race, sex, and age intersections.

3.1.1 Bound certification

  • A naive bootstrap correction can be inaccurate for small groups and overly conservative; rescaling instead yields usable lower bounds across more group sizes, though unscaled bounds can be tighter for the largest groups.The procedure stabilizes the bootstrap process by multiplying by P(G) · Pn(G); variance shrinkage supports uniform consistency, and the authors recommend w0 = ∞ unless variance adaptivity is critical.Source: §3.1.1 · pp. 5–8, Figure 3 · p. 7
  • Under bounded loss, finite-VC group classes, and a non-constant loss residual on some non-empty group, the bootstrap lower bounds are simultaneously valid asymptotically at level 1 − α.Coverage converges to exactly 1 − α under any data-generating distribution; the paper reports minimal nominal-versus-realized coverage gaps even at small sample sizes.Source: §3.1.1 · p. 8

3.1.2 Boolean certification

  • Boolean certification offers computational benefits, including efficient optimization over some infinite group classes, but its asymptotic FWER equals α only when every group disparity is at the threshold.Unlike the confidence-set guarantee, its FWER need not equal α under other data-generating distributions.Source: §3.1.2 · pp. 9–10

3.2.1 Synthetic validation

  • In synthetic experiments, nominal FWER matched or exceeded realized FWER for large samples, while rescaling improved confidence-bound power over unscaled bounds.When disparities were not near the testing threshold, nominal FWER could substantially overestimate the realized level; both bound algorithms attained nominal coverage in large samples.Source: §3.2.1 · pp. 10–11, Table 1 · p. 12, Table 2 · p. 12

3.2.2 Certifying COMPAS

  • A 90% lower confidence bound certifies that high-risk African-American defendants are at least 1.87% more likely to recidivate than high-risk Caucasian defendants, addressing the claim in.The audit compares positive predictive values among defendants classified as high-risk.Source: Figure 5 · p. 13, §3.2.2 · p. 13
  • 90% confidence intervals for COMPAS PPV disparity validate Northpointe’s parity claims for several, but not all, African-American subpopulations.The intervals are simultaneously valid across subpopulations formed by intersections of race, sex, and age.Source: §3.2.2 · p. 13
  • Younger male subpopulations appear to have higher COMPAS PPV than the Caucasian target group.Source: §3.2.2 · p. 13

4 Flagging performance disparities

The section uses BH-based FDR control to flag underperforming groups, then applies it to Folktables and COMPAS. The experiments report conservative FDR on Folktables and localized FPR and PPV disparities among COMPAS subgroups.

4.1 Methods

  • False discovery rate control bounds the expected proportion of issued flags that are false, a weaker guarantee than simultaneous validity.The paper motivates FDR because false flags are less problematic than false certificates, and expects most groups to satisfy the null.Source: §4.1 · p. 14
  • For finite group collections, BH(α) on marginal p-values asymptotically controls FDR at α for disjoint groups or binary metrics with overlapping groups.The stated result also assumes group probabilities and conditional variances are bounded away from zero, with θP known in advance.Source: §4.1 · pp. 14–15
  • For an infinite group collection, the authors recommend splitting the audit data: discover interpretable groups on one split and validate flags on the other.A regression tree is one example for defining the groups to test.Source: §4.1 · p. 15

4.2.1 Folktables

  • Across 1,000 trials, estimated FDR stayed below the nominal 0.1 bound at every tested sample size for all three Folktables tasks.The authors attribute the conservative estimates to null p-values being conservative because the null hypothesis rarely holds with equality.Source: §4.2.1 · p. 15, Table 3 · p. 16

4.2.2 COMPAS

  • Nearly every under-25 COMPAS subgroup is flagged for higher false positive rates, localizing the disparity among African-American defendants and suggesting it affects young defendants more generally.Figure 6a also reports that most under-25 subpopulations suffer the disparity.Source: §4.2.2 · p. 16, Figure 6 · p. 16
  • The audit flags subpopulations with PPV at least 5% below average, including Females, Females under 25, and Caucasian females under 25.Only these three nested groups are flagged.Source: §4.2.2 · p. 16, Figure 6 · p. 16

5 Beyond subpopulations

The paper extends auditing from subpopulations to distribution shifts by using non-negative tilts, including RKHS functions, and gives bootstrap-based guarantees for rich function classes. In a synthetic example, it bounds conditional coverage for a complex subgroup while the audit may be conservative in small samples.

5.1 Methods

  • Generalizing from binary indicators to non-negative tilts enables auditing over certain infinite-VC function classes, including RKHS unit balls and VC classes of tilts.Examples of the latter include non-negative polynomials and bounded monotone tilts over a single covariate.Source: §5.1 · p. 17
  • For a suitably chosen RKHS, its functions can approximate any smooth tilt on a compact covariate domain, supporting guarantees for essentially arbitrary groups and covariate shifts.The paper relates subpopulation audits to distribution shifts indexed by indicator tilts and describes querying shifts in the audited collection.Source: §5.1 · pp. 16–18
  • The RKHS bootstrap optimization can be reduced to computing the top eigenvalue of a low-rank matrix using a representer-theorem reduction.The method bounds the supremum over non-negative unit-ball functions by the supremum over the unrestricted unit ball.Source: §5.1 · p. 18
  • A rescaling analogous to the earlier method is possible for RKHS auditing, but its bootstrap computation is prohibitively expensive.The paper provides the rescaling and algorithm in Appendix D.Source: §5.1 · p. 18

5.2 Empirical results

  • In small samples, the RKHS audit may be conservative, with the realized percentile sometimes exceeding the nominal level.Table 4 reports realized percentiles of the bootstrap critical value across 200 trials; the nominal percentile is 0.9.Source: §5.2 · p. 19, Table 4 · p. 19
  • 84.0% conditional coverage was lower-bounded for a union of three sub-intervals, with bounds simultaneously valid over infinitely many tilts at 90% confidence.The union was approximated by a Gaussian RKHS function with bandwidth σ = 0.5.Source: §5.2 · p. 19, Figure 8 · p. 20

A Connections to fairness

The appendix shows how the auditing procedures apply to group fairness criteria by translating their requirements into disparities over groups. It describes certification and flagging approaches for equalized-odds-style rates and multicalibration, while individual-fairness auditing is left as a possible extension.

Multicalibration

  • The formal multicalibration definition excludes groups below a threshold, whereas the auditing methods do not exclude groups by size a priori.A threshold in the rescaled certification method can make confidence sets narrower for groups above it without preventing queries for other groups.Source: A Connections to fairness · p. 24
  • For multicalibration, the method forms groups by intersecting each subgroup with predicted-value bins and bounds the maximum absolute calibration disparity across them.It can also flag a subgroup if any bin-level null is rejected using the Benjamini–Hochberg procedure.Source: A Connections to fairness · p. 24

Equalized odds

  • Equalized-odds auditing can run separate audits for false-positive and true-positive rate disparities, then combine the two outputs using the worse bound or certificate.The two audits use α/2 each; the passage notes the union bound is practically tight because their data sets are disjoint.Source: A Connections to fairness · pp. 24–25

Individual fairness

  • Individual fairness concerns whether similar inputs receive similar treatment, but it cannot be tested using sampled model predictions as stated.The paper notes that bootstrap methods for U-statistics and processes could support an extension to measures defined over pairs of data points, without developing it here.Source: A Connections to fairness · p. 25

B.1 Notation and review

This appendix reviews empirical-process notation and the convergence conditions used in the paper’s arguments. It connects the Donsker property to uniform convergence and, for indicator classes, to finite VC dimension.

B.1 Notation and review

  • The empirical distribution Pn is formed from n i.i.d. samples, and Pn[f] and P[f] denote empirical and population expectations.The centered empirical process maps functions to √n(Pn − P)[f].Source: §B.1 · p. 25
  • A P-Donsker function class has an empirical process that converges in distribution to a tight Gaussian limit in ℓ∞(F).The passage states that a Donsker class is also P-Glivenko-Cantelli.Source: §B.1 · p. 25
  • For classes of indicators indexed by groups, the Donsker property is equivalent to the group class having finite VC dimension, under the stated measurability conditions.The appendix cites this equivalence as Lemma B.1.Source: §B.1 · p. 25

B.2 Proofs of certification theorems

The appendix supplies technical ingredients for the certification results, including quantile regularity and uniform consistency of the rescaling estimator. It also extends the target-estimation assumptions to estimators with asymptotic linear expansions.

B.2 Proofs of certification theorems

  • The target-estimation setup extends beyond differentiable functions of sample means to estimators that admit bootstrappable asymptotic linear expansions.The stated generalization includes a maximum-likelihood estimator as an example.Source: §B.2 · p. 26
  • If the limiting Gaussian process has positive variance for some index, the distribution functions of its supremum and infimum are continuous and strictly increasing on the positive and negative reals, respectively.This regularity supports consistency of the bootstrap quantile estimate used in the main theorem.Source: §B.2 · p. 26
  • Under the stated assumptions, the reciprocal estimated scaling factor converges uniformly over groups to its population counterpart.The lemma assumes positive finite variance, finite VC dimension, and positive p* and w0.Source: §B.2 · p. 27
  • The appendix establishes that uniform consistency by controlling the variance and group-frequency terms over the group class.It uses finite-VC Glivenko–Cantelli properties and finite-moment conditions for the influence function.Source: §B.2 · p. 30

Bound certification

The section establishes simultaneous lower confidence bounds for group disparities and justifies their bootstrap critical value. The guarantee holds under bounded loss, finite VC dimension, and a non-constant loss contrast in at least one non-empty group.

Bound certification

  • The lower confidence bound is formed by subtracting a bootstrap critical-value adjustment, t*, scaled by the estimated variability and group mass.The construction defines t* through Algorithm 6 and uses the estimated scale ŝ(G).Source: Bound certification · pp. 30–31
  • Under bounded L, finite VC dimension, and a non-constant L − θ̂ over at least one non-empty group, ε_lb(G) is an asymptotic (1 − α)-lower confidence bound simultaneously valid for all G.The theorem’s proof establishes bootstrap consistency and consistency of the estimated critical quantile.Source: Bound certification · pp. 30, 33
  • The bootstrap process is asymptotically equivalent to the process defining the probability of interest, supporting the critical-value construction.The proof uses Donsker-class arguments, the continuous mapping theorem, and quantile consistency.Source: Bound certification · p. 33

Boolean certification

Boolean certification uses a bootstrap critical value to test whether a group’s disparity exceeds a threshold. Under finite variance, finite VC dimension, and a non-constant loss contrast in at least one non-empty group, the certificates are simultaneously valid.

Boolean certification

  • Algorithm 7 bootstraps a rescaled critical value for deciding whether to issue a Boolean certificate.The proof shows the bootstrap distribution consistently estimates the limiting distribution used to set that critical value.Source: Boolean certification · pp. 33, 35
  • Under finite variance for L, finite VC dimension of G, and non-constant L − θ̂ over at least one non-empty group, issued certificates are simultaneously valid with probability 1 − α.Source: Boolean certification · p. 33
  • When every group has disparity ε(G) = ε, the looseness in the upper bound on Type I error disappears and t* achieves exact Type I error control.Source: Boolean certification · p. 36

B.3 Alternative certification goals

The certification procedures extend to upper bounds, confidence intervals, and interval certification. The interval task tests whether a group’s absolute disparity is below the specified threshold.

B.3 Alternative certification goals

  • For upper confidence bounds or certification that ε(G) < ε, the procedure reverses the sign of t* and certifies when the adjusted estimate is below ε.Source: §B.3 · p. 36
  • For confidence intervals, the method bootstraps the absolute process and uses its estimated (1 − α)-quantile to construct the confidence set.Source: §B.3 · p. 36
  • Interval certification tests |ε(G)| ≥ ε by testing both one-sided nulls and certifies the group only when both are rejected.The paper also calls this a “bioequivalence” null.Source: §B.3 · p. 36

C Flagging audits

The flagging procedure applies the Benjamini–Hochberg method to group p-values to control the asymptotic false discovery rate under specified conditions. Its justification uses asymptotic Gaussian statistics with non-negative covariance, while control for two-sided testing is not proved.

C Flagging audits

  • The group disparity estimates are asymptotically multivariate normal when group probabilities and conditional variances are bounded away from zero.The p-values are marginally asymptotically valid for the listed one-sided and two-sided null hypotheses.Source: C Flagging audits · p. 37
  • The BH(α) procedure asymptotically controls the false discovery rate at level α for mutually disjoint groups or binary outcomes with overlapping groups.The proof establishes asymptotic PRDS for the one-sided p-values in these cases.Source: C Flagging audits · p. 38
  • In both supported cases, the test statistics have an asymptotic multivariate Gaussian distribution with non-negative covariance, yielding PRDS p-values.Source: C Flagging audits · p. 38
  • FDR control for the two-sided null is unproved, although substantial violations are described as challenging to obtain in practice when PRDS does not hold.Source: C Flagging audits · p. 38

D Auditing distribution shifts

The distribution-shift analysis extends beyond VC classes and develops RKHS-based simultaneous confidence bounds, establishing bootstrap validity under stated regularity conditions.

Loading 2305.03712v2…