📊 statistics

Doubly-Regressing Approach for Subgroup Fairness

This paper addresses the computational and data sparsity challenges of subgroup fairness with multiple sensitive attributes by proposing the DRAF algorithm, which leverages a novel subgroup-subset fairness formulation and a surrogate fairness gap to efficiently achieve fairness guarantees while outperforming existing baselines.

Original authors: Kunwoong Kim, Kyungseon Lee, Jihu Lee, Dongyoon Yang, Yongdai Kim

Published 2026-01-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Kunwoong Kim, Kyungseon Lee, Jihu Lee, Dongyoon Yang, Yongdai Kim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a judge trying to make sure a hiring algorithm is fair.

The Old Problem: The "Too Many Groups" Trap
In the past, fairness meant checking if men and women got hired at the same rate. That's easy. But what if you also need to check for race, age, and education level? Suddenly, you aren't just checking two groups; you are checking thousands of tiny combinations (e.g., "older women of a specific race with a college degree").

This creates two big headaches:

The "Empty Room" Problem: Some of these tiny groups have almost no people in the data. It's like trying to judge the quality of a restaurant based on a single review. You can't trust the result.
The "Math Overload" Problem: Checking thousands of groups at once requires so much computer power that it becomes impossible to run efficiently.

The Paper's Solution: The "Smart Filter" (DRAF)
The authors, Kunwoong Kim and his team, propose a new method called DRAF (Doubly Regressing Adversarial learning for Fairness). Think of it as a smart filter that solves both problems at once.

Here is how it works, using simple analogies:

1. Ignoring the "Ghost Towns" (Solving Data Sparsity)

Instead of trying to check every single tiny group (even the ones with only one or two people), DRAF says, "Let's only check the groups that have enough people to give us a reliable answer."

The Analogy: Imagine you are checking the water quality of a city's rivers. You don't test the tiny, dry puddles that appear after a storm because they don't tell you much. You only test the main rivers and the large tributaries. DRAF focuses on these "large rivers" (groups with enough data) to ensure the water is clean.

2. The "Double-Check" System (Solving Computational Burden)

Usually, to check fairness, you might need a different "inspector" (a computer program called a discriminator) for every single group you are testing. If you have 1,000 groups, you need 1,000 inspectors. That's slow and expensive.

DRAF uses a clever trick called "Doubly Regressing."

The Analogy: Instead of hiring 1,000 different inspectors, DRAF hires one super-inspector who is very flexible. This inspector carries a special "adjustable lens."
- When looking at the "Men" group, the lens adjusts to see that specific angle.
- When looking at the "Women of a specific race" group, the lens shifts instantly to see that angle.
- The computer doesn't need to build a new inspector for every group; it just tweaks the settings of the one existing inspector. This makes the process incredibly fast, even with thousands of groups.

3. The "Safety Net" (Ensuring Marginal Fairness)

There is a risk that if you only check the big groups, you might accidentally ignore the rules for the main categories (like just "Men" vs. "Women").

The Analogy: DRAF builds a safety net. It forces the system to check the big groups and the main categories simultaneously. It ensures that the "Men" group is fair, the "Women" group is fair, and the specific combinations are fair, all at the same time.

What Did They Find?

The team tested this on real-world data (like hiring, loan approvals, and crime statistics).

When data is messy: In datasets where many groups were tiny and sparse (like the "Communities" dataset with 18 different attributes), DRAF was much better than existing methods. It managed to be fair without crashing the computer or making bad guesses based on tiny data.
When data is clean: Even when data wasn't sparse, DRAF performed just as well as the best existing methods.

In Summary
The paper introduces a new way to make AI fair that is smarter about which groups it checks (ignoring the tiny, unreliable ones) and more efficient at checking them (using one flexible inspector instead of thousands). This allows us to build fairer AI systems even when we have complex data with many different types of people.

Technical Summary: Doubly-Regressing Approach for Subgroup Fairness

1. Problem Statement

The paper addresses the challenge of achieving subgroup fairness in machine learning when multiple sensitive attributes (e.g., gender, race, age) are present. While marginal fairness (fairness across individual attributes) is well-studied, it fails to prevent "fairness gerrymandering," where severe discrimination persists at the intersections of multiple attributes (Kearns et al., 2018a;b).

Formally, with $q$ binary sensitive attributes, there are $2^q$ subgroups. Enforcing distributional fairness across all these subgroups faces two critical barriers:

Data Sparsity: As $q$ increases, many subgroups contain very few samples, leading to unstable model estimation and inaccurate fairness guarantees (Molina & Loiseau, 2023).
Computational Burden: The number of fairness constraints scales exponentially with $q$ . Existing adversarial approaches that attempt to measure fairness across all subgroups become computationally intractable.

Furthermore, existing methods often fail to simultaneously guarantee marginal fairness (fairness on each individual attribute) and subgroup fairness, or they rely on weaker fairness notions (e.g., Demographic Parity) that do not ensure distributional fairness.

2. Methodology

2.1 Subgroup-Subset Fairness

To resolve data sparsity, the authors propose focusing only on "active" subgroups—those with sufficient sample sizes—while explicitly including marginal subgroups (subgroups defined by single sensitive attributes) to ensure marginal fairness.

They formalize subgroup-subset fairness, where a "subgroup-subset" $W$ is a union of specific subgroups. The goal is to enforce distributional fairness over a pre-selected collection of subgroup-subsets $\mathcal{W}$ where sample sizes are not too small.

2.2 Supremum Integral Probability Metric (supIPM)

The authors introduce a distributional fairness measure called the supremum Integral Probability Metric (supIPM). For a collection of subgroup-subsets $\mathcal{W}$ , the fairness gap is defined as:
$\Delta_{\psi, \mathcal{W}}(f) = \sup_{W \in \mathcal{W}} \psi(P_{f,W}, P_{f,W^c})$
where $\psi$ is a deviance measure (specifically IPM). The authors prove that the estimation error of the empirical supIPM depends on the minimum sample size within the subsets ( $n_W$ ) rather than the total number of subsets $|\mathcal{W}|$ , justifying the focus on active subsets.

2.3 Doubly Regressing Adversarial Learning (DRAF)

Directly optimizing supIPM is computationally expensive because it requires finding a separate discriminator for every $W \in \mathcal{W}$ . To overcome this, the authors propose a surrogate fairness gap based on Doubly Regressing $R^2$ (DR2).

Theoretical Foundation: They establish a relationship between IPM and the coefficient of determination ( $R^2$ ) in a regression setting where the input is the model prediction and the output is a label indicating subset membership.
The Surrogate: They define a Doubly Regressing $R^2$ measure, $DR^2(f, v, g)$ , which simultaneously regresses the discriminator output $g(f(x))$ and a weighted combination of subset indicators $v^\top c_i$ .
Key Innovation: The proposed algorithm, DRAF (Doubly Regressing Adversarial learning for Fairness), optimizes a surrogate gap defined as:
$DR_{n, \mathcal{W}, \mathcal{G}}(f) := \sup_{g \in \mathcal{G}, v \in S_M} \tilde{z}\text{-}DR^2(f, v, g)$
Crucially, this formulation requires only a single discriminator $g$ and a weight vector $v$ , regardless of the number of subgroup-subsets $|\mathcal{W}|$ . This reduces the computational complexity from exponential to linear with respect to the number of subsets.
Optimization: The algorithm trains the predictor $f$ and the discriminator/weight pair $(g, v)$ in an alternating min-max fashion. Theoretical analysis proves that this surrogate gap serves as an upper bound for the true supIPM.

3. Key Contributions

Formalization of Subgroup-Subset Fairness: A new fairness notion that balances the need for intersectional fairness with the practical constraints of data sparsity by focusing on active subgroup-subsets and marginal groups.
Introduction of supIPM: A distributional fairness measure for subgroup-subsets, accompanied by a theoretical bound on its estimation error.
DRAF Algorithm: A computationally efficient adversarial learning algorithm that uses a single discriminator to approximate supIPM via a doubly regressing $R^2$ surrogate. The authors prove this surrogate is an upper bound of the target metric.
Empirical Validation: Demonstration that DRAF outperforms baseline methods (Regularization, GerryFair, Sequential mapping) particularly in scenarios with high-dimensional sensitive attributes and sparse subgroups.

4. Experimental Results

The authors evaluated DRAF on four benchmark datasets: ADULT, DUTCH, CIVILCOMMENTS, and COMMUNITIES (the latter having $q=18$ and extreme sparsity).

Performance on Sparse Data: On the COMMUNITIES dataset, where most subgroups are extremely small, DRAF significantly outperformed baselines in both subgroup fairness (SP) and first-order marginal fairness (MP(1)). Baseline methods like GerryFair (focused on worst-case subgroup disparity) or Regularization (focused on marginal disparity) failed to achieve both simultaneously.
Accuracy-Fairness Trade-off: DRAF achieved competitive accuracy-fairness trade-offs across all datasets. In less sparse datasets (ADULT, DUTCH), it performed comparably to or better than baselines.
Correlation Analysis: Experiments showed that DRAF effectively controls both subgroup and marginal fairness simultaneously, whereas methods focusing on only one dimension often degrade the other.
Robustness: The method demonstrated robustness to noisy (missing) sensitive attributes, as it can apply fairness constraints only to observable subgroup-subsets without discarding samples.
Extensions: The approach was shown to extend to multi-class classification and Equalized Odds (EO) fairness constraints.

5. Significance and Claims

The paper claims that DRAF provides a practical solution to the "curse of dimensionality" in subgroup fairness. By shifting the focus from all $2^q$ subgroups to a curated set of active subgroup-subsets and utilizing a single-discriminator surrogate, the method resolves the dual issues of data sparsity and computational intractability.

The authors emphasize that their approach ensures distributional fairness (the strongest notion of fairness) without resorting to weaker metrics like Demographic Parity. They argue that ignoring small subgroups is statistically sound for population-level fairness, provided that marginal fairness is explicitly enforced. The work concludes that DRAF enables the deployment of fair AI models in complex, real-world scenarios with multiple sensitive attributes where previous methods were either computationally prohibitive or statistically unstable.