Research map / Learning theory and algorithms / Fairness

Cost Efficient Fairness Audit Under Partial Feedback

NeurIPS 2026 · Learning theory and algorithms › Fairness · approach: Fairness-constrained classification · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Initiates fairness auditing under partial feedback with a new cost model penalizing labels of negatively classified individuals, giving near-optimal rejection-sampling audit for black-box models and a cheaper MAP-oracle-based audit for exponential-family mixtures.

Problem

Auditing a classifier's equalized odds when true labels are observed only for positively classified individuals, and acquiring labels for negatives incurs feature and default costs.

Approach

A cost model charging per-feature and per-negative-label costs; a rejection-sampling audit that estimates conditional quantities per group matches a cost lower bound in the black-box setting; under exponential-family mixtures, truncated-sample parameter estimation plus an approximate MAP oracle lets the auditor avoid paying for most negative labels.

Key results

• RS-Audit achieves a provably near-optimal audit cost in the black-box setting, matching a lower bound up to log factors.
• Exp-Audit's cost term for negative labels is independent of epsilon, while RS-Audit's cost grows as epsilon shrinks.
• Abstract reports the proposed algorithms consistently outperform natural baselines by around 50% in audit cost on Adult Income and Law School.

Surprising findings

• The natural baseline that requests labels for all negatively classified individuals can be strictly suboptimal in cost.

Limitations

• Mixture-model guarantees require structural and separation assumptions (log-concavity, strong convexity, separation).
• Experiments cap tau at 1000 for RS-Audit for runtime reasons.
• Only logistic regression classifiers are evaluated.

Experimental setup

Datasets: Adult Income Law School Admission synthetic spherical Gaussian mixture

Benchmarks: Adult Income Law School Admission synthetic mixture data

Metrics: equalized odds difference estimate audit cost number of samples

Baselines: Naive baseline audit (request all negative labels)

Builds on: learning from truncated samples MAP oracles for spherical Gaussian mixtures

Closest papers by meaning

• Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness (ICML 2018 · similarity 0.88)
• Fair Classification with Partial Feedback: An Exploration-Based Data Collection Approach (ICML 2024 · similarity 0.87)
• Monotone Individual Fairness (ICML 2024 · similarity 0.86)
• Fairness without Harm: An Influence-Guided Active Sampling Approach (NeurIPS 2024 · similarity 0.86)
• Arbitrariness and Social Prediction: The Confounding Role of Variance in Fair Classification (AAAI 2024 · similarity 0.85)
• A Sequentially Fair Mechanism for Multiple Sensitive Attributes (AAAI 2024 · similarity 0.85)