Research map / Learning theory and algorithms / Fairness

Intersectional Fairness via Mixed-Integer Optimization

NeurIPS 2026 · Learning theory and algorithms › Fairness · approach: Fair allocation and selection · 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.

Proves SPSF and MSD detect the same most-unfair intersectional subgroup, and uses mixed-integer optimization with lazy cutting-plane constraints to train interpretable classifiers (linear, DNF) under intersectional fairness.

Problem

Marginal fairness can hide bias in intersections of protected attributes; detecting the most unfair intersectional subgroup and training classifiers that bound intersectional bias is computationally hard due to exponentially many subgroups.

Approach

Shows that maximizing SPSF and maximizing MSD (subgroup discrepancy between positively and negatively classified samples) identify the same most-unfair subgroup, and uses MIO with lazy constraint generation (cutting planes) to enforce intersectional fairness constraints for interpretable models without enumerating all subgroups.

Key results

• Conjunction-based subgroups maximizing SD and SPSF coincide, consistent with the proven equivalence.
• MIO finds subgroups with notably higher unfairness than GerryFair on linear subgroups across the ACS datasets, even with 5-minute runs.
• Training with FPSF constraints keeps training violation near the 0.01 threshold with modest accuracy loss; lazy cuts needed at most 47 subgroups versus millions available.

Surprising findings

• MSD as a direct training objective underperforms SPSF/FPSF, largely due to the O(n) additional variables and constraints.
• Introducing a sparsity term zeroes about 54% (76% with linear subgroups) of coefficients with comparable accuracy.

Limitations

• MIO is inherently limited in scalability; training complex classifiers is computationally expensive.
• Conjunction subgroups assume discrete protected attributes, requiring discretization of continuous attributes like age.
• Fairness guarantee holds on training data; test-set FPSF violations occasionally slightly exceed the threshold.

Experimental setup

Datasets: ACS Income ACS Public Coverage ACS Mobility ACS Employment ACS Travel Time

Benchmarks: ACS Income ACS Public Coverage ACS Mobility ACS Employment ACS Travel Time

Metrics: SPSF violation FPSF violation MSD accuracy F1 score number of cuts

Baselines: GerryFair unconstrained MIO classifier MSD

Builds on: Statistical Parity Subgroup Fairness Maximum Subgroup Discrepancy GerryFair

Closest papers by meaning

• Searching for Unfairness in Algorithms’ Outputs: Novel Tests and Insights (AAAI 2025 · similarity 0.89)
• Intersectional Unfairness Discovery (ICML 2024 · similarity 0.88)
• Understanding challenges to the interpretation of disaggregated evaluations of algorithmic fairness (NeurIPS 2025 · similarity 0.87)
• Fairness-Accuracy Trade-Offs: A Causal Perspective (AAAI 2025 · similarity 0.87)
• FairPFN: A Tabular Foundation Model for Causal Fairness (ICML 2025 · similarity 0.87)
• Size-adaptive Hypothesis Testing for Fairness (NeurIPS 2025 · similarity 0.87)