Research map / Learning theory and algorithms / Fairness
Fair Classification with Partial Feedback: An Exploration-Based Data Collection Approach
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 an exploitation-exploration framework for partial-feedback classification that collects outcome labels for negatively predicted groups under an FDR constraint, with fairness-aware exploration and exploitation, and proves FDR, improvement, and convergence guarantees.
Problem
Classifiers trained only on outcomes of positively classified samples (partial feedback) receive biased, incomplete data, so they can be erroneous and unfair across groups, while exploring by positively classifying many samples causes high false positives.
Approach
Each iteration splits the domain into an exploit region (well-observed points, classified by a reweighted, FDR-constrained classifier) and an explore region, from which a number of points are positively classified via a sampling strategy g tied to the classifier and group proportions; the number of explored points is set so the overall FDR stays below alpha.
Key results
- On Adult (race), the framework with both fairness constraints achieves average revenue 74.1k with FDR 0.15 and TPR disparity 0.06, versus 75.7k for Opt-offline (FDR 0.14, TPR disparity 0.12) and 44.9k for Kilbertus et al.
- Rateike et al. baseline achieves FDR 0.12 but negative average revenue (-17.2k) on Adult race due to many early false positives.
- Theory: the framework satisfies alpha-FDR (up to O(epsilon)) per iteration, group-wise utility is non-decreasing across iterations up to epsilon, and converges to the optimal offline classifier under the FDR constraint.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add exploit fairness constraint (ablation) | Partial-feedback framework · Adult Income (race) | revenue (in thousands): 71.5 -> 73.0 | Helped |
| Add explore fairness strategy (ablation) | Partial-feedback framework · Adult Income (race) | revenue (in thousands): 71.5 -> 74.7 | Helped |
| Add both exploit and explore fairness constraints (ablation) | Partial-feedback framework · Adult Income (race) | TPR disparity: 0.08 (0.05) -> 0.06 (0.04) | Helped |
| Add explore fairness strategy (ablation) | Partial-feedback framework · German Credit (gender) | revenue (in thousands): 6.4 -> 9.4 | Helped |
| Add exploit fairness constraint (ablation) | Partial-feedback framework · German Credit (gender) | statistical rate: 0.07 (0.06) -> 0.04 (0.04) | Helped |
| Add exploit fairness constraint (ablation) | Partial-feedback framework · Adult Income (gender) | revenue (in thousands): 75.6 -> 78.1 | Helped |
| Add exploit fairness constraint (ablation) | Partial-feedback framework · Adult Income (gender) | TPR disparity: 0.15 (0.04) -> 0.07 (0.03) | Helped |
| Use fairness constraints during exploration and exploitation (ablation) | Partial-feedback framework · Adult Income (race) | revenue (in thousands): 71.5 -> 74.1 | Helped |
| Use exploration to collect outcome data | Partial-feedback framework · Adult Income | TPR | Helped |
Surprising findings
- Yang et al. and Rateike et al. baselines yield negative cumulative revenue on Adult despite low statistical rate or TPR disparity, because of many false positives.
Limitations
- Sample complexity depends linearly on domain size |D|, which can be large; theory relies on i.i.d. assumptions adjusted for adaptive collection.
- Experiments use simulated partial feedback on static datasets with a single logistic-regression classifier and small German Credit dataset (resampled).
Experimental setup
Datasets: Adult Income German Credit
Benchmarks: Adult Income German Credit
Metrics: revenue FDR statistical rate TPR disparity group-wise TPR
Baselines: Kilbertus et al. Yang et al. Rateike et al. Opt-offline Fair-clf
Builds on: Kilbertus et al. stochastic classifiers for exploration Yang et al. adaptive data debiasing Rateike et al. fairness-aware online decision making
Closest papers by meaning
- Cost Efficient Fairness Audit Under Partial Feedback (NeurIPS 2026 · similarity 0.87)
- Characterizing Fairness Over the Set of Good Models Under Selective Labels (ICML 2021 · similarity 0.87)
- 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.86)
- Learning Fair Policies for Multi-Stage Selection Problems from Observational Data (AAAI 2024 · similarity 0.85)
- Understanding Fairness and Prediction Error through Subspace Decomposition and Influence Analysis (NeurIPS 2025 · similarity 0.85)
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.