Research map / Learning theory and algorithms / Fairness
Fair Wasserstein Coresets
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 fair Wasserstein coresets (FWC), which generate synthetic representative samples with weights by minimizing Wasserstein distance under an empirical demographic parity constraint, solved via majority minimization with a FairWASP-based dual step.
Problem
Existing fair coreset and representative-sample methods optimize local properties (clustering cost, coverage) and do not evaluate how their synthetic samples affect downstream fairness-utility trade-offs; the paper targets fair synthetic coresets that preserve the original distribution for downstrea
Approach
Reformulates the Wasserstein coreset objective with demographic parity as linear constraints on sample weights, then uses majority minimization: a convex surrogate per iteration with an LP solved via cutting planes on the dual, and centroid-style updates of the synthetic features. Without fairness constraints it reduces to Lloyd's algorithm for k-means/k-medians.
Key results
- On the Adult LLM experiment, FWC few-shot examples reduced GPT-4 demographic disparity from 0.42 (zero shot) to 0.27, with accuracy dropping from 76.54 to 65.20.
- For GPT-3.5 Turbo, FWC few-shot examples lowered DP from 0.040 (zero shot) to 0.010 at accuracy 55.02 vs 53.55.
- Runtime grows near-linearly with dataset size n, from n=500 up to n=1,000,000 on synthetic data.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Provide 16 FWC examples with weights instead of zero-shot prompting | GPT-3.5 Turbo · Adult | DP: 0.040 $\pm$ 0.017 -> 0.010 $\pm$ 0.03 | Helped |
| Provide 16 FWC examples with weights instead of balanced few-shot examples | GPT-3.5 Turbo · Adult | DP: 0.019 $\pm$ 0.015 -> 0.010 $\pm$ 0.03 | Helped |
| Provide 16 FWC examples with weights instead of zero-shot prompting | GPT-3.5 Turbo · Adult | accuracy: 53.55 $\pm$ 0.87 -> 55.02 $\pm$ 1.26 | Helped |
| Provide 16 FWC examples with weights instead of balanced few-shot examples | GPT-3.5 Turbo · Adult | accuracy: 57.99 $\pm$ 1.88 -> 55.02 $\pm$ 1.26 | Hurt |
| Provide 16 FWC examples with weights instead of zero-shot prompting | GPT-4 · Adult | DP: 0.42 $\pm$ 0.016 -> 0.27 $\pm$ 0.04 | Helped |
| Provide 16 FWC examples with weights instead of balanced few-shot examples | GPT-4 · Adult | DP: 0.33 $\pm$ 0.09 -> 0.27 $\pm$ 0.04 | Helped |
| Provide 16 FWC examples with weights instead of zero-shot prompting | GPT-4 · Adult | accuracy: 76.54 $\pm$ 1.63 -> 65.20 $\pm$ 0.85 | Hurt |
| Provide 16 FWC examples with weights instead of balanced few-shot examples | GPT-4 · Adult | accuracy: 74.39 $\pm$ 2.86 -> 65.20 $\pm$ 0.85 | Hurt |
| Use FWC coresets rather than the compared coreset approaches | Downstream MLP classifier · Adult, German Credit, Communities and Crime, Drug | fairness-utility tradeoff | Helped |
| Use FWC as few-shot examples rather than zero-shot prompting | GPT-3.5 Turbo · Adult | DP: 75% | Mixed |
| Use FWC as few-shot examples rather than zero-shot prompting | GPT-4 · Adult | DP: 35% | Helped |
| Add FWC samples to the existing training data | Downstream models · Real datasets | fairness-utility tradeoff | Helped |
Surprising findings
- Few-shot examples from FWC cut GPT-4 disparity but cost substantial accuracy (76.54 to 65.20), an explicit fairness-utility tradeoff.
- Runtime rate increases beyond n of about 500,000 due to more iterations needed for convergence.
Limitations
- Downstream learning error bounds are not derivable since FWC samples are not i.i.d.
- Demographic parity is the only fairness criterion targeted; equalized odds left to future work.
- LLM experiments are limited to a single dataset, a 200-sample test set, and 16 examples due to compute constraints.
Experimental setup
Datasets: Adult German Credit Communities and Crime Drug synthetic dataset
Benchmarks: Adult German Credit Communities and Crime Drug
Metrics: demographic parity disparity AUC accuracy runtime
Baselines: Fairlets IndFair K-Median Coresets k-means k-medoids Uniform Subsampling
Builds on: FairWASP Lloyd's algorithm majority minimization Wasserstein coresets
Closest papers by meaning
- FairWASP: Fast and Optimal Fair Wasserstein Pre-processing (AAAI 2024 · similarity 0.89)
- Fairness without Harm: An Influence-Guided Active Sampling Approach (NeurIPS 2024 · similarity 0.85)
- AIM-Fair: Advancing Algorithmic Fairness via Selectively Fine-Tuning Biased Models with Contextual Synthetic Data (CVPR 2025 · similarity 0.85)
- Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems (ICLR 2025 · similarity 0.84)
- The Impact of Coreset Selection on Spurious Correlations and Group Robustness (NeurIPS 2025 · similarity 0.84)
- On Optimal Steering to Achieve Exact Fairness (NeurIPS 2025 · similarity 0.84)
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.