Research map / Learning theory and algorithms / Fairness
Active Fourier Auditor for Estimating Distributional Properties of ML Models
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.
Proposes the Active Fourier Auditor (AFA), a black-box method that estimates robustness, individual fairness, and statistical parity of ML models via significant Fourier coefficients found with a Goldreich-Levin-style active search, without reconstructing the model.
Problem
Black-box auditing of distributional properties (robustness, individual fairness, group fairness) of ML models without reconstructing the model or assuming its class.
Approach
Express robustness, individual fairness and statistical parity as functions of the model's Fourier coefficients (via influence functions), then find the large coefficients adaptively with a dynamic Goldreich-Levin bucket search using black-box queries, yielding PAC estimates and sample complexity bounds.
Key results
- On statistical parity across 9 dataset-model configurations, AFA achieves the lowest error in all, e.g. 0.006 vs 0.077 for Uniform on COMPAS LR.
- For robustness at rho=0.30 on COMPAS LR with 1000 samples, AFA error is 0.078 vs 0.333 for Uniform.
- Theory: AFA's sample complexity is O(1/epsilon sqrt(log 1/delta)) for robustness and individual fairness and O(1/epsilon^2 log 1/delta) for group fairness; a lower bound of Omega~(delta/epsilon^2) is given for group fairness.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AFA instead of Uniform for statistical parity estimation | LR, MLP, and RF · COMPAS | estimation error: LR: 0.077 -> 0.006; MLP: 0.225 -> 0.147; RF: 0.077 -> 0.006 | Helped |
| Use AFA instead of Uniform for statistical parity estimation | LR, MLP, and RF · Student | estimation error: LR: 0.132 -> 0.030; MLP: 0.225 -> 0.147; RF: 0.077 -> 0.006 | Helped |
| Use AFA instead of Uniform for statistical parity estimation | LR, MLP, and RF · Drug | estimation error: LR: 0.254 -> 0.220; MLP: 0.116 -> 0.040; RF: 0.127 -> 0.120 | Helped |
| Use AFA instead of Uniform for robustness estimation | LR · COMPAS, ρ=0.25 | estimation error: 0.033 -> 0.016 | Helped |
| Use AFA instead of Uniform for individual fairness estimation | LR · COMPAS, ρ=0.25 | estimation error: 0.036 -> 0.029 | Helped |
| Use AFA instead of Uniform for robustness estimation | LR · COMPAS, ρ=0.30 | estimation error: 0.333 -> 0.078 | Helped |
| Use AFA instead of Uniform for individual fairness estimation | LR · COMPAS, ρ=0.30 | estimation error: 0.309 -> 0.047 | Helped |
| Use AFA instead of Uniform for robustness estimation | LR · COMPAS, ρ=0.35 | estimation error: 0.299 -> 0.139 | Helped |
| Use AFA instead of Uniform for individual fairness estimation | LR · COMPAS, ρ=0.35 | estimation error: 0.248 -> 0.092 | Helped |
Surprising findings
- Exact computation of large Fourier coefficients is NP-complete (reduction from Max2Sat), motivating the approximate approach.
- Reconstruct-then-estimate incurs error scaling with the reconstruction error divided by the minority group proportion.
Limitations
- Experiments are limited to binary classifiers on Boolean features in the main development; continuous and multi-class extensions are only briefly described.
- Group fairness estimation has a worse sample rate (1/epsilon^2) than robustness and individual fairness.
- Manipulation-proofness result is shown only for statistical parity.
Experimental setup
Datasets: COMPAS Student performance Drug consumption
Benchmarks: COMPAS Student Drug
Metrics: estimation error running time sample efficiency
Baselines: Uniform sampling CAL muCAL
Builds on: Goldreich-Levin algorithm Active Fairness Auditing (CAL) Gram-Schmidt Fourier basis for arbitrary distributions
Closest papers by meaning
- Fairness without Harm: An Influence-Guided Active Sampling Approach (NeurIPS 2024 · similarity 0.84)
- SMI: Statistical Membership Inference for Reliable Unlearned Model Auditing (NeurIPS 2026 · similarity 0.84)
- Cost Efficient Fairness Audit Under Partial Feedback (NeurIPS 2026 · similarity 0.83)
- Robust Sampling for Active Statistical Inference (NeurIPS 2025 · similarity 0.83)
- Reproduce, Replicate, Reevaluate. The Long but Safe Way to Extend Machine Learning Methods (AAAI 2024 · similarity 0.82)
- Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts (ICML 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.