Doubly-Regressing Approach for Subgroup Fairness
Authors: Kunwoong Kim
Kyungseon Lee
Jihu Lee
Dongyoon Yang
Yongdai Kim
Venue: ICLR 2026 Poster (2026)
Keywords: Algorithmic fairness
Subgroup
Adversarial learning
Data sparsity
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Algorithmic fairness is a socially crucial topic in real-world applications of AI.
Among many notions of fairness, subgroup fairness is widely studied when multiple sensitive attributes (e.g., gender, race, and age) are present.
However, as the number of sensitive attributes grows, the number of subgroups increases accordingly, creating heavy computational burden and data sparsity problem (i.e., subgroups with very small sample sizes).
In this paper, we develop a novel learning algorithm for subgroup fairness that resolves these issues by focusing on sufficiently large subgroups as well as marginal fairness (fairness for each sensitive attribute).
To this end, we formalize a notion of subgroup-subset fairness and introduce a corresponding distributional fairness measure called the supremum Integral Probability Metric (supIPM).
Building on this formulation, we propose the Doubly Regressing Adversarial learning for subgroup Fairness (DRAF) algorithm, which reduces a surrogate fairness gap for supIPM with much less computation than directly reducing supIPM.
Theoretically, we prove that the proposed surrogate fairness gap is an upper bound of supIPM.
Empirically, we show that the DRAF algorithm outperforms baseline methods on benchmark datasets, particularly when the number of sensitive attributes is large so that many subgroups are very small.

Published as a conference paper at ICLR 2026
DOUBLY-REGRESSING APPROACH FOR SUBGROUP FAIRNESS
Kunwoong Kim 11
Kyungseon Lee
Jihu Lee²
Dongyoon Yang'
Yongdai Kim
KAIST "Seoul National University 3SK Hynix Inc.
kwki m. cnl i ine@gmail.com (ppleeqq, rieky0426 60
dongycon, gangesk.com ydkim0903@@ga1
ABSTRACT
Algorithmic faimess is a socially crucial topic in real-world applications of AI. Among many notions of fairness, subgroup fairness is widely studied when mul- tiple sensitive attributes (e.g., gender, race, and age) are present. However, as the number of sensitive attributes grows, the number of subgroups increases accord- ingly, creating heavy computational burden and data sparsity problem (i.e., sub- groups with very small sample sizes). this paper, we develop novel learning algorithm for subgroup fairness that resolves these issues by focusing suffi- ciently large subgroups as well as marginal fairness (fairness for each sensitive attribute). To this end, we formalize notion of subgroup-subset faimess and introduce a corresponding distributional fairness measure called the supremum Integral Probability Metric (supIPM). Building on this formulation, we propose the Doubly Regressing Adversarial learning for subgroup Fairness (DRAF) algo- rithm, which reduces surrogate fairness gap for suplPM with much less compu- tation than directly reducing supIPM. Theoretically, we prove that the proposed surrogate fairness gap is an upper bound of supIPM. Empirically, we show that the DRAF algorithm outperforms baseline methods on benchmark datasets, par- ticularly when the number of sensitive attributes is large so that many subgroups are very small.
INTRODUCTION
Rapid deployments of AI models in socially consequential domains such as finance, hiring, and criminal justice have amplified the demand for faimess-aware predictions. Early definitions of al- gorithmic fairness predominantly focused on a single sensitive attribute, such as gender or race, requiring parity across these (marginal) protected groups However, faimess with respect single attribute is not sufficient to protect against discrimination at the intersections of multiple attributes. In partieular, the problem of fairness gerrymandering, where severe unfairness may remain on their intersections, even if faimess is satisfied on each marginal attribute, has been noticed (Kearns et al., 2018a b). For instance. while a lending model may equalize approval rates between men and women, the subgroup defined by "female and minority race" may still experience significantly lower approval rates. This illustrates the necessity of (intersectional) subgroup fairness.
To state subgroup fairness formally, suppose that the i-th individual is specified by its g-dimensional sensitive attribute s, {0, 13", where each coordinate (sensitive attribute) binary. Then, there are 24 subgroups, defined by
= = v), for v E {0,1)".
Subgroup fairness requires that the distributions of prediction values be similar (i.e., distributional fairness) across all 29 subgroups. However, when q is large, we may face major challenges: (i) data sparsity, when certain subgroups contain very few samples, model estimation on such sub- groups becomes unstable and inaccurate (Molina & Loiseau 2023); (ii) computational burden, the number of faimess constraints scales exponentially in
I Equal contribution.
Work done while Seoul National University.
* *Corrsponning author.

---

Published as a conference paper at ICLR 2026
Various learning algorithms for subgroup fairness have been proposed to resolve the aforementioned
two problems (Foulds et al. 2019b; Molina & Loiseau 2023 Foulds et al. 2019a (Shui et al. 2022
Maheshwari et al. [023] Hu et al. 2024), but there still several limitations. Existing algorithms
either do not guarantee the marginal fairness (i.e., fairness on each sensitive attribute) which may
lead to socially unacceptable prediction model, or would be computationally demanding when an
adversarial learning is required to measure fairness.
The aim of this paper is to develop learning algorithm for subgroup faimess which resolves data sparsity and computational burden simultaneously. To avoid data sparsity, we simply focus on active subgroups, i.e., subgroups whose sample sizes are not too small. Considering only active subgroups is statistically sound since empirical fairness on non non-active subgroups does not guarantee the fairness on the population level. novel part of our proposed learning algorithm to find prediction model which achieves (active) subgroup fairness and marginal fairness simultaneously in the context of distributional fairness, the strongest notion of fairness (see Section 3.1 for definition), without resorting on heavy computational burden.
For this purpose, we define a subgroup-subser W S {0, 1 as a union of certain subgroups, and focus on Dw Uvew D. Our approach enforces the distributional fairness over pre-selected subgroup-subsett whose sizes are not too small. Then, we design a novel adversarial training strat- egy termed doubly regressing adversarial learning, which learns prediction model without heavy computational burden but guarantees the distributional fairness for all pre-selected subgroup-subseed The doubly regressing adversarial learning algorithm requires only single discriminator regardless of the number of pre-selected subgroup-subsets and so computational demand is practically accept- able even when q is large. By including all active subgroups and marginal subgroups (subgroups corresponding to each sensitive attribute) into the set of pre-selected subgroup-subsets, we can ef- fectively achieve subgroup fairness and marginal fairness simultaneously.
The main contributions of this work can be summarized as follows:
1. We formalize subgroup-subsee fairness and introduce a measure for the distributional subgroup- subset faimess called the supremum Integral Probability Metric (supIPM).
2. We propose a surrogate fairness measure for supIPM which requires only single discriminator regardless of the number of subgroup-subsets, and develop an adversarial learning algorithm called Doubly Regressing Adversarial learning for Fairness (DRAF) algorithm" to learn an accurate and subgroup-subset fair prediction model.
3. Theoretically, prove that the proposed surrogate faimess measure becomes an upper bound of supIPM.
4. Empirically, we show that the DRAF algorithm outperforms baseline methods in benchmark datasets, with large margins when q is large so many subgroups are extremely small.
RELATED WORKS
Existing methods such as Kearns et al.] (2018b); Agarwal et al. (2018) aim to reduce prediction- based subgroup disparities (unfairness). In particular, Agarwal et al. (2018) proposed reduction- based approach for marginal fairness by solving a min-max game using Lagrangian multipliers, Kearns et al. (2018b) extended this framework to minimize the worst-case subgroup disparity. To mitigate data sparsity problem of tiny subgroups, Kearns et al.] (2018b a) employed weights proportional the sample size of each subgroup.
However, as the number of intersectional subgroups grows, these methods can become computa- tionally expensive. Moreover, they do not explicitly target distributional fairness (e.g., IPMed criteria), which is the focus of our work. While other approaches focus on other fairness notions, for example, Lai & Guan 2025) designed an adversarial learning-based method for equalized odds, they also differ from our focus on the distributional fairness.
A Bayesian method is proposed borrow information in large-size subgroups when estimating prediction models for siall-sized subgroups (Foulds et al. 2019a). These approaches, however, do not guarantee the marginal fairness (i.e., fairness on each sensitive attribute) which makes it difficult
Code available at http://///gtgttbb.co///rarroorpp
2

---

Published as a conference paper at ICLR 2026
to socially interpret the faimess of a prediction model. On the contrary. (Molina & Loiseau 2023) consider only the marginal fairees but it could be vulnerable to fairness genrymandering.
To resolve heavy computational burden, weak notions of fairness such as the DP (Demographic Par- ity) are employed in the fairness constraint (Kearns et al. 201 a) or post- processing techniques are used after learning a prediction model without fairness constraint (Hu et al. 2024). These methods, however, would yield suboptimal prediction models in view of other stronger faimess notions (e.g., distributional fairness) and/or prediction accuracy.
Our approach We propose an in-processing algorithm for distributional fairness on pre-selected subgroup-subsets whose sizes not too small. We formalize subgroup-subsel fairness and develop a computationally efficient adversarial algorithm to achieve the distributional fairesss.
3
SUBGROUP-SUBSET FAIRNESS
3.1 PROBLEM SETTING
We consider data points (xi,, Ve. 8;) with input vectors x; E X, output variables yi E y, and 8; = (Sil...., 8ta) E {0, denoting the q binary sensitive attributes. Let IP be the probability measure of (X, E X x y x {0, 1] and P,, be its empirical counterpart. Let F be the set of prediction models f : X' x 1] - R for 2 1. Here, c is the number of classes in classification problems (i.e., y = [1..... ,)). For a given prediction model J E F and 8 {0, 139, let J,,, be the conditional distribution of f(X) given S 8.
for regression problems (i.e., y = R), while
We say that f is (perfectly) subgroup-fair if f.s.,, E {0, 1) are all the same. To relax the perfect fairness, we define (i)-distributional) subgroup faimess gap for given deviance (h::,) between two probability measures as (f) = (0.)9 ( ), where Py,, is the marginal distribution of f(X). Then, we say f is rh- subbougo fair with level 8 2 0 if (f) I 6. The main goal of subgroup-fair learning is to find an accurate model among gi-subgroup-fii fair models with level 6.
Various kinds of deviances have been used in fair AL. Examples include (i) the original DP, where for given threshold 7 (binary classification) one considers ADP
|Pr( [XX,((X, 8) >
r|S = 8) - (x(f( -) 2 r) (Agarwal et al.
2018). (ii) the mean DP, defined as App(f)
[Ef s) $}{S = s) B(f(x.-)) (Madras et al.
2018
Donini et al. 2018). (iii) the distributional
DP, defined by distributional deviance 3/ such that
Fr.s ,.... 0 implies f.. PP f. [Jann
et al., 2020al Chzhen et al., 2020b] Silvia et al.
2020 Barata et al., 2021 Kim et al. 2025). Pop-
ularly used distributional DPs are Wasserstein distance, Maximum Mcan Discrepancy (MMD), Bullback-Leible divergence, and Kolmogorov-S -mirroo distance. Among these, distributional DP is the strongest one since it can imply other DPs. In subgroup faimess, the distributional DP has been less explored, partly because its computation would be demanding when is large.
There are large amounts of literature about subgroup fair learning algorithms (Kearns et al. 2018b a
Ursula Sebert-Johnson et al., 2018 Foulds et al. 2019b Tian et al. 2025), whose proposed meth- ods learn a prediction model by minimizing the empirical risk (c.g.. cross-entropy) subject to the constraint that empirical subgroup faimess gap A (f) is less than equal to 5. Here, empirical subgroup fairness gap An.. (J') is the fairness gap on the empirical distributions.
not easily applicable the case of large due to data sparsity and computational burden. Note that the number of subgroups grows expo- nentially in q and thus certain subgroups have too small amounts of data and so empirical subgroup fairness gap is not good estimator of population subgroup fairness gap. With a limited amount of data, there is no hope to be able to guarantee fairness on all subgroups. We could ignore subgroups with too small samples. but this naive approach does not ensure the marginal faireess which would not be acceptable. In addition, 29 number of computations of the deviance ei required to calculate subgroup fairness gap, and so easy-to casy-to-compute y/s (e.g., mean DP) have been used instead. Further- more, a subgroup-fair prediction model may not always satisfy the marginal fairness and thus would not be socially acceptable (see example in Section B.7). Hence, rather than considering all sub- groups, we focus only on subgroups whose sizes are sufficiently large and enforce faimess on such large subgroups. To do so, introduce a new faimess concept called subgroup-subset fairness, in the next subsection. We also provide a more detailed discussion regarding the connection between marginal and subgroup fairness in Section B.7
Existing subgroup-
learning algorithms, however,
3

---

Published as a conference paper at ICLR 2026
3.2 DEFINITION OF SUBGROUP- SUBSST FAIRNESS
To resolve the data sparsity problem, in this paper, we propose a new notion of subgroup fairness called subgroup-subsel fairness. The main idea of subgroup-subset faimess is to guarantee fairness on two disjoint subsets of sensitive attributes. To be more specific, we call any subset W of {0, 1 as a subgroup-subie and let Pj J.w be the distribution of f(X) conditional on S W and f. be its empirical counterpart. For given collection W of subgroup-subsee and deviance 1 we define
(f)(()= sup ('PP,,,,,,,.))) Wew
which we call the subgroup-subset fairness gap (with respect W). Then, we say f is subgroup- subset fair with level ó if A (v,((f) S
Choice of W If W consists of all subgroups. subgroup-subset fairness equal to subgroup fairness. To resolve data sparsity, we should only include large subgroups in W. In turn, to si- multaneously achieve the marginal fairness (i.e., fairness on each sensitive attribute), we add the marginal subgroups (i.e., Wj. {i Sij }f for E lg] and E {0. 1)) to W. In gen- eral, we can guarantee fairness for any subgroup-subsett of interest by adding those subgroup- subsets to W. For example, can guarantee the second-order marginal fairness (i.e., fairness on (2) = {i: (stg, 8,k) = ($1, $2)] for j. E [q] and ($1, 82) E {0, 1)3) by adding the cor- responding subgroup-subser
Similarly, we can consider the 1-th order marginal fairness for E [Ø]. Figure 17 in Section B.7 illustrates the hierarchical structure of subgroup-subset (from marginal subgroups to intersectional subgroups).
However, one may worry that the computation of A,.w becomes difficult when [W] is too large. In Section 4.2 we develop a computationally efficient adversarial learning algorithm for subgroup- subset fairness, where only a single discriminator is used regardless of the size of W. Furthermore, Table Section B.4 emppricclr supports the computational scalability of our proposed algorithm.
3.3 SUPREMUM IPM FOR SUBGROUP- FAIRNESS GAP
Integral Probability Metric (IPM) For group fairness with a single binary sensitive attribute (i.e..
1), the integral probability metric (IPM) (Müller 1997 Sriperumbudur et al. 2009) has been popularly used the deviation & (Chzhen et al. 22020a] Jiang et al. [020b]] Kim et al. 2022 2025
Kong et al. 2025) to ensure the distributional fairness, For given two probability measures Fo and
F1. the IPM with a given discriminator class {g _ + R} is defined as
/ a(w)Po((a)) - f g (()))(((r))
(PPo P.) = sup
geg
Various IPMs are defined by selecting the discriminator class G accordingly. Popular examples for are (i) the collection of 1-Liischitzz functions for Wasserstein distance (Villani) 2009); (ii) the unit ball of an RKHS for MMD (Gretton et al., 2012a); (iii) indicator functions over VC-bounded family for Total Variation (Shorack 2000).
Supremum IPM and its statistical property When v is IPMg, call A (-) supIPM. We denote supIPM and its empirical counterpart as Aw.g(-) (-) and An,w.g() (.), respectively. Theorem 3.1 whose proof is deferred to Section A.2 implies that the estimation error of An,w,s(+) does not depend heavily on the size of W but depends on the minimum size of the subgroup-subsets in W (or its complement): nyy minwe ew min min(nw, n- nw J, where nw = I(i: : 8, E WH. This result suggests that we can construct W as large as possible until nw is sufficiently large.
Let Rm (H) denote the empirical Rademacher complexity of given function class H with m sam- ples (see Definition I. for its detailed definition).
Theorem 3.1. Let W be a collection of subgroup-subsets and nw == Hi s; E Wor W e w. Assume that [| 8o < B, Vg E G. Then, we have for all f E F that
2 log (2m WI)
(f - -n.w.e(f) S 4R. F) + +B
(1)
nw
with probability at least 1 1/n, where nw
min min minnn nw). Wew
4

---

Published as a conference paper at ICLR 2026
In Section A.4
show that Raw (GoF)= = (0(1///))/m) for two cases of G and F, which indicates O( (o[[log([WW]]]))))
that the estimation error of w.,w,g that it would be reasonable to add only subgroup-subsets W with nw 2 yn into W for some small > 0. Then, it is guaranteed that the population fairness level locates within the O(y/og([W))//) range of the empirical fairness level. See Section 5.1
ignoring log n term. This suggests
how we choose 7 in practice.
Challenges in using SuplPM for subgroup-subset fairness A technical difficulty, however, exists in using SuplPM since computation of suplPM could be very demanding when W| is large. To be more specific, for given f and W, let Ộw. arg ga I.f To calculate SuplPM, we should find 9w.f for all W E W, which is computationally demanding when [W] large. We could avoid this problem by using the IPM which admits closed-form cal-
- (.=))l/.wv<dda (.w)(d)),,
culation. An example is the Maximum Mean Discrepancy (MMD) (Gretton et al. (2012b) However, computational cost of calculating supMMD O(W)n2) which still large when [W] and/or is large. In addition, the choice of the kernel function in MMD would not be easy.
In the following section, we propose novel surrogate subgroup-subsee fairness gap of supIPM which serves as an upper bound of suplPM and requires only a single discriminator to be computed.
4 DOUBLY REGRESSING ALGORITHM
4.1 A SURROGATE DEVIANCE FOR IPM
Fix W E W, and let yw,, := (s; E W) - be the indicator whether i-th observation belongs to W or not. To assess the fairness level of a given prediction model on W, standard method is to investigate the error rate of a classifier learned with f, := f(x,, s.) being input and yw., being the label, which is used for fair adversarial learning (Edwards & Storkey 2016 Madras et al.) 2018). That is, we look at oug Σ T(yw,; x g(ft) < 0). If J is fair on W, the distribution of on and W are similar and thus the miscclassification error becomes large.
Instead of the mis-classification error, we could consider the Residual Sum of Squares (RSS) supgeg Ex
o(.)))² The RSS is mathematically more tractable than the mis- classification eтror since the former is differentiable while the latter is not. This mathemat- ical tractability plays an important role when we extend surrogate measure of IPM for supIPM. A larger RSS implies a fairer f. An equivalent measure would be supSSR == sup,eg {Ei (yw.:: yw)"
(yw.s - =(f)))²), which is an analogy of the Sum of Squares of Regression (SSR) used in the regression analysis. This measure becomes small when f is fair.
related measure of supSSR is supgeg R2 W)g), where
W. = En (yw.i - ((1i))2 Σ (UW. kw) En (ww, - {(R))2 (2)
(UW,, )2
E (yw, )2)
which is an analogy of R2 in the regression analysis. This measure becomes also small when is fair. A surprising result is that a slight modification of Eq. (2) is equal to IPM, as stated in the following theorem. See Section A.2 for its proof.
Theorem 4.1. For given f E F. W S 13 and G, we have
Ee Dw )2 1= (ww. )2
IPM (P,,,, = sup (f. gEG
=
+
For given G, suppose that Gohs ((g(2))...., ((xa)) : :g 9] is linear space. Then و := arg mingeg E o(f)))² 2 is the projection of (yw.1...., vw..." onto Goos- In this case, R2 (f, W, 9) is the squared correlation between { and {](ft)), and moreover R² W, 2 RR. W. The additional term 2i (ww.
Σe (o( in R² (f, W.g) is introduced for Gots not being (ow, - Sw
a linear space. An interesting new implication of Theorem 4. is that the IPM is closely related to the correlation between the class label and the discriminator output.
5

---

Published as a conference paper at ICLR 2026
4.2 A SURROGATE DEVIANCE FOR SUPIPM: DOUBLY REGRESSING R
Theorem 4.1
implies (,, = supwew Suppes It (f. W,g), which is not easy to calculate because W is a numerical quantity, so gradient-based algorithm cannot be directly applied. To resolve this computational challenge, introduce smoother variant of Rº (J, W,g), called the Doubly Regressing R² (DR²) follows.
Suppose that W = {W1..... WM J. For each E [n]. define c; = [cI..... GM E (-1,1)"
with Cim (8; W mm) 1, m E [M]. Given predictor S, discriminator g, and weight vector
V E SMM, we define
(f..gg := EE (v g(fi)) Eir( [2))
Σi=1 2v)²
where Po - v & and 8 is the unit sphere on R The name 'Doubly Regressing" is used since regress input g(fi) and output v 'e simultaneously when calculating DR
Note that (f v. g) is equal ( Wm g) when ek: where e₁ is the vector whose entries are all O except the k-th entry being Thus, it is obvious that supIPM bounded as:
sup IPMg (PT F.W. P w--,)) An.w.g(f) v Wew
sup SEG,vESM
(f.
(3)
Based Eq. our proposed surrogate subgroup-subset fairness gap for suplPM is : = suPyES.vESM z-DR² (f. v,)) where
DRo,w.e(f)
1 + DR v)g
EDDR (f. log
D v, (J,v,g)l/2)
Here, we apply the Fisher's 2-transformation (Fisher, 1915) to D for numerical stability. We call DR,,w.e(f) the Doubly Regressing (DR) subgroup subset fairness gap. A smaller value of DR,,w.e(f) (f) indicates a higher level of subgroup-subsel fairness of f.
4.3 ALGORITHM: DOUBLY REGRESSING ADVERSARIAL LEARNING FOR FAIRNESS (DRAF)
Based on the DR gap, we introduce DRAF (Doubly Regressing Adversarial learning for Fairness) algorithm, which trains by minimizing "'= 135. f(x;, s;)) + ADRn,w.g( for given loss function (e.g., cross-entropy) and Lagrangian multiplier X. A key feature is that single discrimi- nator is used regardless of W.
In the learning algorithm, we iteratively train the prediction model f and the pair of discriminator y and weight vector v iteratively. At each iteration, we (i) update f by applying gradient descent algorithm to minimize - f s;)) + DD-DR (f, (f.v.g v.)) while and v are fixed, and then (ii) update g and v by applying a gradient ascent algorithm to maximize z-DR² (.. v,g) while f being fixed. Algorithm in Section B.2 below provides the outline our proposed algorithm.
EXPERIMENTS
In this section, empirically verify that DRAF successfully achieve both marginal and sub- group fairness: (i) it shows competitive performance to baseline methods for datasets with less sparse subgroups: (ii) it outperforms baselines for datasets with extremely sparse subgroups. After that, we conduct detailed analyses on the effect of managing W and the choice of discriminator.
5.1 SETTINGS
Datasets consider the following four benchmark datasets (three tabular datasets and text dataset) popularly used in algorithmic faimess research. See Section B. for more details.
ADULT (Tabular) (Becker & Kohavi 1996): The class label is binary, indicating whether the in- come is above 50kS. The input features are several demographic census features. For the sensitive attributes, consider sex, race, age, and marital-status, so that q 4.

---

Published as a conference paper at ICLR 2026
DUTCH (Tabular) (van der Laan 2000): The class label is binary, indicating the occupation level. The input features are several socio-economic features. For the sensitive attributes, we consider and age, so that q = 2.
CIVILCOMMENTS (Text) (Borkan et al. 2019): The class label is binary, indicating whether a given text comment is toxic or not. The input features are the embedded representations ex- tracted from the pre-trained DistilBERT model (Sanh et al. 2019). For the sensitive attributes, we and religion (christian/other),
consider (male/female/other),, race (black/whiteeasiin//ooff
which are non non-binary. resulting in 24 subgroup:?
The class label is binary, indicating whether the violent crime rate exceeds a threshold. The input features are community-lewe at- tributes covering demographics and economic indicators. For the sensitive attributes, we consider race, racial per-capita, and language/immigration variables so that q = 18.
COMMUNITIES (Tabular) (Redmond & Baveja 2002):
Table 1 summarizes the basic statistics of the four datasets and Figure 1 presents the distribution of subgroup sizes for the datasets. These statistics highlight the severity of data sparsity: in partieu- lar. COMMUNITIES suffers from extreme sparsity: the vast majority of subgroups contain very few samples. We construct a 60/20/20 split for train, validation, and test, respectively for the datasets except COMMUNITIES, Due to the extreme sparsity of certain subgroups in COMMUNITIES dataset, ensuring sufficient samples within the test set would be important, so we use with 50/10/40 ratios. We repeat this procedure five times randomly and report the average performance.
Table 1: Summary of datasets. "# Subgroup" indicates the possible maximum number of subgroups
(= 29). "# Actual Subgroup" indicates the actual number of subgroups in the datasets. "# Sparse subgroup" indicates the number of subgroups whose size is at most 1% of the total sample size n.
Dataset
Y1
q
# Subgroup
# Actual Subgroup
# Sparse subgroup
ADULT 48,842
4
16
16
2 0
DUTCH
60,420
2
1
1
CIVIL COMMENSSNNTS
3,365
(non-binary) 18
24
24
COMMUNITIES
1,994
144
1,180
1, 1,175
400
Semples
Samples
5000
10000
200
5080
30
Sabgroup Index
Subgroup Index
Subgruu P indes
Subgrouu Index
(a) ADULT
(b) DUTCH
(c) CIVILCOMMENTS
(d) COMMUNITIES
Figure 1: Number of samples per subgroup. The red horizontal line indicates yn used for the main
analysis in Section 5.3 The subgroup indices are assigned by sorting the subgroup sizes.
Model and Performance measures Since the four datasets are for binary classification tasks, consider
1 for the output dimension of the prediction model f. We consider single- layered MLP for f and apply the sigmoid activation at the output layer to return the prediction score between (0. 1]. Recall that f. = f (Iz s;) and let 9, 2I 2 1/2) - 1. We consider the accuracy Acc(f) E T(y = ú:) for the prediction performance of
For fairness performance, we consider the I-th order marginal fairness and subgroup fairness. For distributional fairness, we use the Wasserstein distance, but only for the first-order marginal sub- group only, as calculating it for higher-orders would be unstable due to data sparsity. To be more specific, let P == 1. Em I(): = 1) and P. := p, Ei,, ma I(i, = 1), E {0, be the overall and suhgroup-specifie ratios of positive prediction, respectively. For given order I [q], con- sider I, C [q] such that T.| = I. Let sx = (sts)ee E 10,1)' be the sensitive attribute sub-
vector of the i-th individual. For a given a {0, 13'. define p(a) := RL. Ene, I(g 1), where n == Ei [T. = a). Let iP,()) = Σi (,). For a given j E [q], define
"Our framework can be generalized easily for non-binary categorical sensitive attributes.
7

---

Published as a conference paper at ICLR 2026
(.lla()) P)) n007 Eissy=a 6y O),, where "j ( = Σi= (sy a) for {0, 1). Table describes ni
the fairness performance measures used in the experiments.
Table 2: Fairness performance measures used in experiments. MP, WMP, and SP are abbre-
viations of Marginal, Wasserstein Marginal, and Subgroup Parity, respectively. 'W indicates the I-Wasserstein distance between two probability measures on R.
Name
Meaning
Formula
(e)
MP
1-th order Marginal fairness
m Eo Pr.
WMP
Distributional Marginal fairness
max max
W
1s 0.
py).
W s.n psn
SP
Subgroup fairness
(0.
p..
Implementation details and Baseline methods We sweep À from 0.01 to 10.0 control the fairness level. For the discriminator G, we use the discriminator class used in sIPM (Kim et al. 2022) (i.e., composition of sigmoid and linear function). For W, we include the first and second- order marginal subgroups as well as subgroups whose sizes are larger than yn. To find an optimal value of 7, we plot Pareto-front lines (for many ys) between Ace and SP using validation data, compute the area under the lines, and then choose the one with the largest area. As result, we set y to 0.01, 0001, 0.2, and 0.001 for ADULT, CIVIECOMENNSS DUTCHI, and COMMUNITIES, respectively. We consider four existing approaches baselines: (i) Regularization (REG): this ap- proach reduces the marginal disparities for q-many sensitive attributes; (ii) GerryFair (GF) (Kearns P/;
et al. 2018a by: this approach reduces the (weighted) worst-case disparity max,e {0,1) R. (II) Sequentral (SEQ) (Hu et al.) 2024)): this approach sequentially maps the scores of a pre-trained fainsess- model in each subgroup common barycenter. See Section B.2 for more details.
5.2 RELATIONSHIP BETWEEN DR GAP AND SUPIPM
As theoretically shown in Theorem and Eq. 3. the DR gap (i.e., DR,,w.g(f)) and supIPM (i.e., w.g (f)) are closely related, i.c., small DR gap = small supIPM. To numerically confirm this relationship, we provide plots between the DR gap and supIPM in Figure 2 indicating that the DR gap is also numerically valid surrogate for suplPM (i.e., reducing DR yields small supIPM). Note that we use the supremum Wasserstein distance for supIPM.
ANE
6258
0208
0279
0258
0.50
0.500
300
300
07300
1058
2014
1300
600
0C3
3/00
030
0.11
100
0.55
8.30
0/12
1.00
Figure 2: Empirical relationship between the DR gap and suplPM on ADULT, DUTCII, CIVILCOM- MENTS, and COMMUNITIES datasets.
Moreover, Figure in Section B.3 empirically shows that the DR gap and suplPM are almost identical: after learning, the weight vector becomes nearly vertex of the simplex, that DR² DR² (f.v,g) v) (f, gm. in practice. This finding empirically supports the claim that the DR gap is valid surrogate for SupIPM.
5.3 PERFORMANCE COMPARISON
Trade-off between accuracy and fairness Figure compares the trade-off between fairness lev- els (SP and MP(1) and accuracies of the five methods. Since the fairness level is not controllable for SEQ and unfair model, their results are given as points instead of lines. Figure i Section B.4 presents similar results for other fairness measures (WMP and MP(2)). The main findings can be summarized as follows.
Datasets with less sparse subgroups (ADULT, DUTCH and CIVILCOMMENTS) For ADULT and DUTCH, the three methods REG, GF, and DRAF perform similarly on both first-order marginal
8

---

Published as a conference paper at ICLR 2026
0.85
dd
Duock
045
0.2
0.82
Leher
Heher
Urf
0.9
EDC
EDC
0147
1.89
Disch
Ovicommart
Communt
0.4
0.0
0.00
0.2
0/90
099
180
1922
0.55
1922
0.19
1927
36
Agx2
Figure 3: Trade-off between faimess level (top: SP, bottom: MP(1)) and accuracy.
and subgroup fairness. Note that the slight better performance of REG on ADULT is due to training-tes test data discrepancy: we observe that the three methods perform nearly the same on the training data. Specifically for CIVI.COMMENTS, REG underperforms GF and DRAF for SP, while GF slightly underperforms DRAF small MP(1), These results recommend using DRAF for achieving both subgroup and first-order marginal faimess, even on datasets with less sparse subgroups. Similar results on an additional dataset (ACSINCOME (Ding et al. 2022 are shown in Figure 8 in Section B.4
Datasets with sparse subgroups (COMMUNITIES): DRAF outperforms REG on both first-order marginal and subgroup fairness, and GF on first-order marginal faireess. These results suggest that reducing only first-order marginal fairness (REG) or only subgroup fairness (GF) would be suboptimal, and so DRAF is particularly effective when subgroups are sparse. See Table 3 in Section B.4 for similar results on subsampled ADULT dataset with sparse subgroups.
Correlation between subgroup fairness and first-order marginal fairness We analyze the cor- relation between subgroup fairness and first-order marginal fairness, to investigate how a given al- gorithm can simultancously control the both well. Figure 4 plots subgroup fairness (SP) versus first-order marginal fairness (MP(1) ) for DRAF, GF, and REG. To quantify the correlation, fit linear regression and calculate the SSE (Sum of Squared Errors). In most cases, the SSES for GF COMMUNITIES.
and REG are larger than that for DRAF, with the largest margin observed suggests that focusing solely on subgroup fairness (GF) or first-order marginal fairness (REG) does not guarantee the other, whereas DRAF can achieve both regardless of the sparsity, This highlights the benefit of DRAF: subgroup and first-order marginal fairness tend to behave together, so we can control both with a single À without unexpected fairness violation.
C20
methed NUMOO
wetho DAAl
Methed
Lan
100 1250
XSG ELL
REG
111
052
3.2
231
E27
2.003
0,000
2313
6.20
LBN 2002 GEZ aid cae 2000 601
Figure 4: Scatter plots between SP and MP with linear regression lines, and SSE on ADULT, DUTCH, CIVILCOMMENTS, and COMMUNITIES datasets.
5.4 EXTENSIONS OF DRAF
Multi-class classification We empirically discuss that DRAF is not limited to binary classifica- tion but can be extended to multi-class classification. Following Denis et al. (202)), which focuses on achieving fairness in multi-class classification task, we use COMMUNITIES dataset with five la-
bel classes and apply DRAF to the dataset. As shown in Table 5 in Scction B.5 DRAF achieves competitive performance compared to Denis et al. (024)).
Equalized Odds (EO) We also show that DRAF can be extended to EO, through slight modifi- cation in (f. v. g). We compare this modified DRAF for EO (DRAF-EO) with FairICP (Lai & Guan 2025). which is adversarial learning- based method for EO. Tables 7 and g in Section B.5
9

---

Published as a conference paper at ICLR 2026
suggest that the DRAF-EO performs competitive to FairICP, in terms of both marginal and subgroup fairness.
5.5 ADDITIONAL STUDIES
Excluding the marginal subgroups from W We investigate how the marginal fairness is affected when W excludes the marginal subgroups. First, Figure in Section shows that excluding first- order marginal subgroups could harm first-order marginal fairness even if subgroup fairness sat- isfied. This result emphasizes the need to include the marginal subgroups in W, to obtain socially acceptable subgroup-fair models (i.e., as well as marginally fair). Similarly, we consider W with- out the second-order marginal subgroups. Figure [I in Section B.6 shows that the second-order marginal fairness can be slightly worsen under such exclusion. Hence, we recommend including the second-order marginal subgroups in W as well, unless the optimization is numerical unstable.
Impact of y Another simple way to manage W is to control the minimum sample size of W E W (i.e., 7). As y increases, the sizes of subgroup-subsets become larger, hence W excludes higher- order marginal subgroups as well as more subgroups. Suppose that we choose to be larger than the sizes of higher-order marginal subgroups but smaller than those of first-order marginal subgroups. Such choice would achieve marginal faireess, but it may hamper higher-order marginal faireess. Section B.ppeiiiyy supports the claim by comparing performance with various rss Figures [2 and 13 show that too large could degrade second-order marginal as well as subgroup faireess.
We further analyze the effect of y by categorizing subgroups into large, medium, and small scales (using quantiles 0.3 and 0.6). [igure[4]jn in Section [B6 implies that (i) while large subgroups remain fair, (ii) medium subgroups require a moderate y to maintain fairness, (iii) and the fairness of small subgroups is not guaranteed even y is small.
In conclusion, since guaranteeing fairness on tiny subgroups is difficult, and we advise selecting a moderate y. This allows the model to achieve fairness for subgroups capable of generalization (i.e., those where fairness on the training data implies faimness on the test data, see Theorem 3.1
Choice of G In the main experiments, we consider the discriminator used in sIPM, which used for fair representation learning (Kim et al., 2022). We also consider two others: (i) ReLU IPM (RIPM, Park al. (2025) ) where discriminator functions are composition of ReLU and linear functions, and (ii) Hölder IPM (HIPM, WWang et al.] (2023)) which uses DNN discriminators. Fig- ure 15 in Section B.6 shows that sIPM is generally the best and most stable.
Robustness under noisy sensitive attributes To investigate the robustness of DRAF under noisy sensitive attribute setting, we conduct a controlled experiment on a modified ADULT dataset by synthetically building missing values into the sensitive attribute at certain rate (e.g., 1%). Existing methods (e.g.. GF) typically require complete subgroup information and therefore should discard samples whose sensitive attributes contain missing values. In contrast, DRAF still be applied partially to such samples: for samples whose sensitive attributes contain missing values, we impose fairness constraints only on subgroup-sul subsets that can be formed using the observed attributes, and ignore subgroup-sute subsets that involve any missing values. The results in Figure 16 in Section B.6 show that this partial DRAF approach is more robust than GF: it attains a better fairness-accuracy trade-off than GF, displaying the robustness of DRAF in the presence of noisy (missing) sensitive attributes.
CONCLUDING REMARKS
In this paper, we introduced a new notion of fairness called subgroup-subset fairness, and proposed a new adversarial learning algorithm for subgroup fairness. We empirically showed that the proposed algorithm particularly works well in scenarios where the data contain sparse subgroups.
A possible future work is to decompose subgroup fairness into low-order marginal faimess (similar to ANOVA decomposition) and control fairness via these components. This approach would improve stability under sparse subgroups and interpretability. One could theoretically derive an upper bound of subgroup fairness in terms of low-order marginal faimess.
10

---

Published as a conference paper at ICLR 2026
Ethics Statement We do not collect new human-subjer datasets; all the datasets used in this paper are publicly available. The faimess notions we employ in this paper (i.e., subgroup faimess and marginal fairness) are widely and popularly investigated in recent literature. Through these efforts, we believe this research helps mitigate potential discriminatory impacts, rather than introduce new ones, and positively influence the responsible use of Al in practice.
Reproducibility Statement We made efforts to ensure the reproducibility of our main findings: (i) We provide full proofs and mathematical definitions used in the theorems in Appendix. (ii) We include implementation details throughout the paper (the main body and Appendix), and add source code the supplementary materials.
Acknowledgements This work was partly supported by the Institute of Information & Communi- cations Technology Planning & Evaluation (IITP) grants funded by the Korea government (MSIT) (No. RS-2021- 1-12 1343, Artificial Intelligence Graduate School Program (Seoul National Univer- 2-22-112211844,, sity); No. RS-202 20--0022-JB I1220184, Development and Study of AI Technologies Inexpensively Con- form to Evolving Policy on Ethics) and by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2022R1 A5A7083908).
REFERENCES
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. A reduc- tions approach to fair classification. In International conference on machine learning, pp. 60-69. PMLR, 2018.
António Pereira Barata, Frank W. Takes, H. Jaap van den Herik, and Cor J. Veenman. Fair tree classifier using strong demographic parity, 2021.
Peter L.
margin bounds for neural networks. Advances in Neural Information Processing Systems (NeurIPS), 2017.
Bartlett, Dylan J. Foster, and Matus J. Telgarsky.
Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. DOI:
https://doi..rg/10... 1ttpg///0000222222X222000
Daniel Borkan, Lucas Dixon, Jeffrey Sorensen, Nithum Thain, and Lucy Vasserman. Nuanced metrics for measuring unintended bias with real data for text classification. In Companion Pro- ceedings of The 2019 World Wide Web Conference, 2019.
Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Fair regression with wasserstein barycenters. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Bal- can, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 7321-7331. Curran Associates, Inc., 2020a. URL http::ppps/prcceeeiiiiii .eer:eeeeeeeedd.eeeee.s...s...s ce/ pdf
Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Fair regression with wasserstein barycenters. Advances in Neural Information Processing Systems, 33: 7321-7331,
Christophe Denis, Romuald Elie, Mohamed Hebiri, and François Hu. Fairness guarantees multi- class classification with demographic parity. J. Mach. Learn. Res., 25(1), January 2024. ISSN
1532-4435.
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning, 2022.
04884
Michele Donini, Luca Oneto, Shai Devid, John Shawe-Taylor, and Massimiliano Pontil. Em- pirical risk minimization under fairness constraints. Advances in neural information processing systems, 31, 2018
Harrison Edwards and Amos Storkey, Censoring representations with adversary. In International Conference in Learning Representations (ICLR2016), pp. 1-14, May 2016. URL httpps:/
iclr. wwtarcciiii.e / www doku. 3F 1onpd3FFiiiioe wwd.iiicr21001 :ww.:mmmii....mm html, 4th International
Conference on Learning Representations, ICLR 2016 ; Conference date: 02-05-2016 Through
04-05-2016.
11

---

Published as a conference paper at ICLR 2026
R. A. Fisher. Frequency distribution of the values of the correlation coefficient in samples from an indefinitely large population. Biometrika, 10(4):507-52) 521, 1915. ISSN 00063444. URL http:
//www. jstor.str..... sttrg//taabeee331333333
James Foulds, Rashidul Islam, Kamrun Keya, and Shimei Pan. Bayesian modeling of intersectional faimess: The variance of bias, 2019a. URL https: /ttp///axiiiv.v. wttp/o/raabbbb..oooo 07255
James Foulds, Rashidul Islam, Kamrun Naher Keya, and Shimei Pan. An intersectional definition of fairness, 2019b. URL
08362
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola.
A kernel two-sample test. Journal of Machine Learning Research, 13(25):723-773, 2012a. URL
html
Arthur Gretton, Karsten M Borgwardt, Malte Rasch, Bernhard Schölkopf. and Alexander Smola.
A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012b.
Francois Hu, Philipp Ratz, and Arthur Charpentier. A sequentially fair mechanism for mul- tiple sensitive attributes. Proceedings of the AAAI Conference on Artificial Intelligence, 38 (11):12502-12510, March 2024. ISSN 2159-5399. doi: 10. 10.1699aaai.v v38.1...3311112211.. URL
http://dx: http:/xxxdoii.... wrg.ioor/..... 10. 1609/6699220 aaai. v38111..1111.....11 29144 29143
Ray Jiang, Aldo Pacchiano, Tom Stepleton, Heinrich Jiang, and Silvia Chiappa. Wasserstein fair classification. In Uncertainty in artificial intelligence, pp. 862-872. PMLR, 2020a.
Ray Jiang, Aldo Pacchiano, Tom Stepleton. Heinrich Jiang, and Silvia Chiappa. Wasserstein fair classification. In Ryan P. Adams and Vibhav Gogate (eds.), Proceedings of The 35th Uncer- luinty in Artificial Intelligence Conference, volume 115 of Proceedingy of Machine Learning Research, pp. 862-872. PMIR, 22-25 Jul 2020b. URL press/v115/jiagg22 html
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu, An empirical study of rich subgroup fairness for machine learning, 2018a.
081
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing faimess gerryman- dering: Auditing and learning for subgroup fairness. In International conference on machine learning, pp. 2564-2572. PMLR, 2018b.
Dongha Kim, Kunwoong Kim, Insung Kong, Ilsang Ohn, and Yongdai Kim. Learning fair repre- sentation with a parametric integral probability metric. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th Inter- national Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 1 11074-11101. PMLR, 17-23 Jul 2022. URL pttps::/procestt ngs. mml. press/vl vl 62 m2m.mb...mm...
Kunwoong Kim, Insung Kong, Jongjin Lee, Minwoo Chae, Sangchul Park, and Yongdai Kim. Fair- ness through matching. Transactions on Machine Learning Research, 2025. ISSN 2835-8856. URL htttps:///ppeeeeettt
net
net/ffruuu forum? iddc 1
Insung Kong, Kunwoong Kim, and Yongdai Kim. Fair representation learning for continuous sen- sitive attributes using expectation of integral probability metrics. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2025.
Yuheng Lai and Leying Guan. FairCCP Encouraging equalized odds via inverse conditional permu- tation. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu (eds.), Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 32228 32245.. PMLR, 13-19 Jul 2025. URL hnttps://ps http:s////occceiiiceeo ngs . ml mww.pprrss v267 / a 25b. html
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In International Conference on Machine Learning, pp. 3384-3393, PMLR, 2018.
12

---

Published as a conference paper at ICLR 2026
Gaurav Maheshwari, Aurélien Bellet, Pascal Denis, and Mikaela Keller. Fair without leveling down: A new intersectional faimess definition. In The 2023 Conference on Empirical Meth- ods in Natural Language Processing, 2023. URL https:/ http://///peeeviie...o net/ fer.ruuummtttttum forum? id=RubWYF BZbG
Mathieu Molina and Patrick Loiseau. Bounding and approximating intersectional faimess through marginal faimess, 2023.
05828
Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29(2):429 443, 1997. doi: 10.2307/1428011.
Yuha Park, Kunwoong Kim, Insung Kong, and Yongdai Kim. Relu integral probability metric and its applications, 2025. /ttp///psss///xxxo...oooo///a///
18897]
Michael Redmond and Alok Baveja. A data-driven software tool for enabling cooperative infor- mation sharing among police departments. European Journal of Operational Research, 141(3): 660-678, 2002.
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, distilled version of BERT: smaller, faster, cheaper and lighter. CoRR, abs/1910.011000 2019. URL http://
arxiv.orge htsp//bs/11111 01108
Galen R. Shorack. Probability for Statisticians. Springer- Verlae, New York, 2000. ISBN 978-0- 387-98945-6. doi: 10. 10.1099//98945.
Changjian Shui, Gezheng Xu, Qi CHEN, Jiaqi Li, Charles Ling, Tal Arbel, Boyu Wang, and Chris- tian Gagné. On learning fairness and accuracy on multiple subgroups. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.). Advances in Neural Information Pro- cexsing Systems, 2022. |tt /otp:::s//ppeeevieew net. forum? R=
Chiappa Silvia, Jiang Ray, Stepleton Tom, Pacchiano Aldo, Jiang Heinrich, and Aslanides John. A general approach to fairness with optimal transport. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 3633- 3640, 2020.
Bharath K. Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert R. G. Lanckriet. On integral probability metries, d-divergences and binary classification, 2009, URL
/eetps:/aaxxxr org/ abs abs////ss/900 2698
Huan Tian, Bo Liu, Tianqing Zhu, Wanlei Zhou, and Philip S. Yu. Multifair: Model fairness with multiple sensitive attributes. IEEE Transactions on Neural Networks and Learning Systems, 36 (3):5654-5667, 2025. doi: LLL09/TNNLSS.022.33388888
Paul van der Laan. Integrating administrative registers and household surveys. Netherlands Official Statistics, 15(2):7-15, 2000.
Cédric Villani. Optimal Transport: Old and New, volume 338 of Grundlehren der mathematischen Wissenschaften. Springer, Berlin, Heidelberg, 2009. ISBN 978-3-540-71049-3. doi: 10.1007/ 978-3-540-71050-
Jie Wang, Minshuo Chen, Tho Zhao, Wenjing Liao, and Yao Xie. A manifold two-sample test study: integral probability metric with neural networks. Information and Inference: A Journal of the IMA, 1877 06 2023. ISSN 2049-8772. doi: 10.1093/maiia/iaad01k URL
Úrsula Hěbert-Jlhnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum. Calibration for the ccomputaionally--cniiiabbll masses, 2018. URL https:t/////attt orggabs//710
08513
13

---

Published as a conference paper at ICLR 2026
APPENDIX
A THEORETICAL STUDIES
A.1 OMITTED DEFINITIONS AND NOTATIONS
Definition A.1 (Rademacher complexity). Let (ax) be the Rademacher random variables such that Pla; +1) F(a; =-1 1/2, independently. Let H be class of real-valued functions
on domain 2, and let 5 (Z1,-..5 2m) E 2th be fixed sample. The empirical Rademacher
complexity of on S is
(H = E
sup NEH
Σ oi h(z)) 1=1
(5)
where the expectation is taken over the Rademacher variables (o,)
Given a distribution P on 2, the Rademacher complexity of H with sample size m is
Rm (H) = Em (Rs(H))
E .m...... P Ry
sup Σ o. h(zz) WCH
(6)
2m
1=1
A.2 PROOFS
Fix f E F. By the definition of the supremum and the triangle inequality of Proof of Theorem 3.7
IPMs,
(o,(() - An),w(() sup (1 J.w, IP (.,)) sup
(IP f.Ws, P',,oo)
wew
weW
(7)
I sup (1 f,w, P (PP f.w, P Pj,w-)) weW
The first term in the right-hand-side can be re- re-written as
(PP f.w, (PT..)
sup
Ep (g) EEy,, (g)
gEG
(8)
Σg go [(x,, 8i)
sup gEG
E (go S)JS W)
nw
where nw = : 8; E W)]. Taking the supremum over E F and by Hoeffding's inequality combined with Rademacher symmetrization, we have with probability at least 8w.
2 2ogg(1 (1w))
(iP,,,, (T.w) S 2n (9 (GoF) + BV FEF
sup
for any 6w > O. An exactly same bound holds for We with nwe in place of nw Applying the union bound over all pairs (W, Wc with dw (/)2),]), and by the fact that nw, nw 2 nw mun nwe)
(ooweewwwwerrr nw }, we have
2 2 (2/W1/6)
sup (o(P,.: Pj,w) + (IP (.,,,P"..w))) 4Rmw (GoF) 2B JEF for all W W. Taking 5 = 1/n concludes the proof.
Proof of Theorem 4.1 Denote fo = f(x,, s1). Recall that yw, 21(ss E W) 1 ( {-1,1],i [n).. Then, we can rewrite
IPMg (P f.w, Py.w-) = sup gEG
Σ g(fi)
Σ g(fi)
V!W
Tw
ksw.,=1
and Lemma A.2 in Section A.3
concludes that
(yw.i UW )w(g(ff)
IPMg (F,,,, p...o) = sup geg
sup [R W. gEg
1 (BW.. f2w)2
14

---

Published as a conference paper at ICLR 2026
A.3 TECHNICAL LEMMAS
Lemma A.2. Fix C {g R + RJ. Let W be a given subset of (0, 139 and J; - I st), i [n].
For binary indicalor yw, = 28: W) - E [-1,,,, [m|, we have
1
Σ
g(fi)
Σ g(fi) Ei (uwa Dw (ffi) nwe kyw,
(9)
E (Uw, kw)2
T&W
kyw;==
for any g E 9, where Uw == Ei= MwA and g = 1 2i=19(fi)
Proof. We begin by rewriting
+ V/W
Σ g(fi)
UW
Σ g(fi)
+ 2
2
RW
NW BUw,
kyw
since nw = Ex
1
n+ E BW.
n(+ and mwe Eisw.:=1
WW..
x11 - Sw! Note that
(yw,) (w)
Σ
vw. 2ūw
yww + now Σ
==1
1=1
n 2īw (nw - nwe) nyn
(w =1 Σ ow.i = nw - -nw=)
(nw - nw=)²
(:: Vww
nw nw
= n
n
4nwnw-
2nw
2nw
(:11+ Dw
1 yw
n
n
n
(10)
Then, we expand
Yyw, (o(f)) -g) Σ
yw.i(ff)) - Σ yw.s Fw Σ ((f)) + nōw
i=1
i=1
1=1
Σ
s(f()
Σ
g(f() - 9 (nw - -ww)) - Uw (ng) + now
Byw,==1
Σ
s(ii)
Σ
s(fi)
(nw nww)
Σ
g(f))
-ww.=-1 g(ft)
Σ
lyw.
-nnw RW=)
Σ
s(fi) +
TWo 1
Σ g(fi)
TWW
koW. =1
TWW byw,:=-1
(11)
nW nwe
Σ o(fi)
nW nw
Σ s(ft)
n
n
kyw.==1
2nw
Σ
((ia)
2nw
Σ
s(ii)
n
kyw.
B-w.
2 2nw nw=
Σ g(fa)
Σ
g(fi)
nw
nw =w.
Ływ,=1
(BW.s )
Σ
g(fa)
Σ
o(fi)
nw
Tw kyw.
1=1
d:ww.==1
15

---

Published as a conference paper at ICLR 2026
where the last equality holds by Eq. (10). Dividing by E.(w; [w) get
Eim (yw.: bw) (o(fi) 9)
g(ii)
nwo Σ
olfi)
(12)
E,uwa - -Uw)
nwW isyw..
Using the fact that
(uw,s FW (g( 9)
E === (yw, &w (ffi)
Ex(ww yw))
Ex - -Vww
we conclude the proof.
A.4 EXAMPLES OF F AND G IN THEOREM 3.1
We introduce two examples that yields small Rademacher complexities Raw (GoF)= = (11/ (ww) so the uniform population-empirical gap in Theorem 3.1 shrinks rate (1/////)w up loga- rithm factor of n.
Example A.3 (Linear functions). Let G {gu(=) (u, ||u|22 < 1) and F = [sw (x. 8)
W 2xx 8) [|W]]2 I M), where 2(x, 8) E IR are fixed features with ||=(xr, s)l(2 S Bg for all (I, Then for all fw E F and 9u G. (guu fw (2, s)l = (u,, W W2(z, s)}l ||u|| W 11llll s)ll2 M M3, so the class is uniformly bounded by R := M Bg. Moreover,
Raw (9 F)
1 nw
E
sup I
TE
ru Wa)
B
sup W SI
Σ W 21
TW
nw
Egg
sup I[WISSM
|| 1l2
Σ
aw
M
aw ES
-
MB Vnw
11w
since ||2:|22 S B,. Consequently, for all F.
Av,(() - wn) 1 Vnw
4MB, + 2MB, /2 log 220g((2(11))
Example A.4 (Deep Neural Networks). Suppose G o F is ReLU Deep Neural Network (e.g.. and FF are both ReLU DNNs) with L-many layers and weight matrices At of spectral norms
St Aella and Frobenius norms
A for L [L]. Then, have Raw (g F) X Bartlett al. 2017). Further, g f is uniformly bounded,
Jww T se) EL ||Aell///
we have
C
Aw An
(0) Vnw
+
2R log(2n([W))
Vnw
for all f E F and constant C depending on the network parameters L and Ag.
16

---

Published as a conference paper at ICLR 2026
B EXPERIMENTS
B. DATASETS
ADULT (Tabular) (Becker & Kohavi 1996): We predict binarized income (2 50K) from demo- graphic information. For the sensitive attributes, we consider sex, race, age, and marital-status, so that 4.
The class label is binary, indicating whether the violent crime rate is above a threshold. For the sensitive attributes, consider 4 variables regarding race (racepetwhite, racepetblack, racepetasian, racepethisp). 6 racial per- capita variables (whitepercap. blackpercap, indianpercap, asianpereap, otherpercap, hisppercap), 8 language/imnigration related-variables (petnotspeakkengleel,, petforeignborn, petimmigrecent, petimmigrec5, petimmigrec8, petimmigrec10, petrecentimmig, petrecimmig5) so that q = 18.
COMMUNITIES (Tabular) (Redmond & Baveja 2002
DUTCH (Tabular) (van der Laan 2000): We predict binarized occupation from socio-economic features. For the sensitive attributes, we consider sex and age, so that q =
CIVN.COMMENTS (Text) (Borkan et al., 2019): We predict toxicity from user-generated comments. For the sensitive attributes, we consider sex (maleefemale/othhrr) race (back//whicc/ssiannotteee))) and religion (christian/other) so that q =
ACSINCOME (Tabular) (Ding et al. 2022): We predict binarized income level using nationwide census features. Sensitive attributes include sex, race (White, Black, Asian, Other), and marital- status, yielding 3.
B.2 IMPLEMENTATION DETAILS
We run all algorithms over five random seeds and report the average performance.
DRAF algorithm To control the fairness level, the Lagrangian multiplier À is swept over {0.00, 0.10. 0.20, 0.30, 0.40, 0.50, 0.60, 00, 0.80, 0.90, 1.00, 2.00, 3.00, 4.00, 5.000 10.00, 20.00). The candidate set of y is {0.001, 0.005, 0.01, 0.05, 0.10, 0.20, 0.30], and we choose an optimal one using the Pareto-from lines, mentioned in Section 5.1 We run DRAF with maximum of 200 epochs, and select the best model whose validation accuracy is the highest among the 200 epochs. Algorithm outlines the DRAF algorithm.
Baselines The fairness penalty of REG is the sum of group disparities: DP Damarg() Eie( n Ei=1 ft
1 Ti E fil, where 8t denotes the 1-th component of s; and mi
Di [(S..) = 1) for E [q]. The final objective is defined as H - [ [(x, + DP marg (f) for some CREG 2 O. We sweep the regularization parameter CREG over (0.001, 0.002, 0.005, 0.01, 0.05, 0.1, 0.2, 0.5, 0.7, 1.0, 2.0, 5.0, 10.0, 20.0, 50.0, 100.0} to trol the fairness level. Similar to DRAF, we run REG with a maximum of 200 epochs, and select the best model whose validation accuracy is the highest among the epochs.
For GF, since the official code and the released AIF360 package support only FP and FN (false positives and false negatives), re-implement GF for the demographic parity setting targeted in this paper. For fast and simple implementation, we apply a gradient-basee
optimization. The fair- ness penalty of GF is the (weighted) worst-group disparity: DP mux (f) = max.c ne (J), where (f) := p0. Pl. = E. H(g = 1}. and p. := n. Ex.,,, I(A: = 1}. The final objective is then defined as Σー (v,, f(z,, + CP (mm (f). Here, we sweep the regular- ization parameter Car over 00.1, 1.0,5.0. 20.0, 50.0, 200.0, 500.0, 1000.0, 5000.0) to control the fairness level. Note that, rather than taking maximum over we apply the softmax function to Pe DP, se (0,11 to make the optimization stable. Similar to DRAF we run GF with a maximum of 200 epochs, and select the best model whose validation accuracy is the highest among the epochs.
n
For SEQ, we re-implement the algorithm the original paper (Hu et al. 2024). That is, we first learn classifier without any faimess constraints, then sequentially post- process the prediction scores from
17

---

Published as a conference paper at ICLR 2026
each subgroups common barycenter. The learning rate used to learn the classifier is swept 10.001,0.0055, 0.01, 0.05, 0.10}.
Algorithm 1: DRAF algorithm
Input Training data { 86, yi) Mi)) Learning rates (Mets fgys fy), Number of iterations 7, and Faimess I Lagrangian multiplier X
Output: Model parameters 0 so that f fa. Discriminator parameters so that Jd. and Weight vector v
Initialize: fb. Φ t do. N Vo
do
for 1...., do Di fo(
end
Compute the classification loss: Lehs = Ei=1 CE(Di. Compute the fairness loss:
CE: cross-entropy
1 (J,
DR DR..w.s(f)) sup VESM
2-DR* (f.
sup log vES
Update the discriminator and the subgroup weight by gradient ascending:
@ + Φ + 1lg V < ProjeMM (v), (Projsw = unit sphere projection)
Update classifier:
0 0 T/cls VoLeis Anola VoDR
10 until convergence or T iterations; 11
Return 0, o,
B.3 RELATIONSHIP BETWEEN DR GAP AND SUPIPM
As Eq. shows that supIPM is upper bounded by DR and that DR² becomes equivalent to suplPM when the vector v lies vertex of the simplex (i.e., e for some k.). Thus, minimizing DR reduces the upper bound on supIPM and recovers supIPM when v (approximately) a vertex (Theorem 4.1.
We empirically support this claim (DR is almost equal to supIPM) by checking whether the learned is near vertex. To quantify how close the learned weight vector is to simplex vertex, ex || where eg denotes the k-th vertex
compute the Euclidean distance d(v) == minigkgM of the m--dimensional probability simplex. We collect [d(v)} over all runs and models, and plot their empirical distribution histogram. The resulting plots in F that d(v) is highly concentrated near zero as training proceeds, indicating that v empirically converges to (or very close to) simplex vertex well.
25
25
20-
20
20
15
15
Danccyy
8.00
8000
8.00
8.00
Figure 5: Histogram of d(v) CIVI.COMMENTE dataset for four time steps (left to right: 1st epoch, 5th epoch, 20th epoch, and 200th epoch).
B.4 PERFORMANCE COMPARISON
Trade-off between accuracy and fairness Figure 6 compares the trade-off between the distribu-
tional first-order marginal and the second-order marginal fairness levels (i.e., WMP and MP(2)) and
18

---

Published as a conference paper at ICLR 2026
accuracy. The results give the similar implications that observe from Figure Section That is, compared to the baseline methods (GF, REG, and SEQ), DRAF performs comparable on ADULT, DUTCH, shows slightly better performance CIVILCOMMENTS, and outperforms COMMUNITIES.
5.3
Durch
Oviconmara
Communt
0.44
040
0.00
Ukla
0.9
045
DRA
WFF
0.64
4.00
1klx:
048
19
0.3
No
HB0
DMF
ADULT
(h) DUTCH
(c) COVM.COSMENTS
(d) COMMUNITIES
Figure 6: Tff between faimess level and accuracy. (Top, Bottom) = WMP vs. Acc, MP(2) vs. Acc. We set y to 0.01 for ADULT, 0.001 for COMMUNITIES, 0.2 for DUTCII, and 0.01 for CIVILCOMMENTS, reflecting the sparsity of each dataset to determine the optimal value.
Analysis additional datasets
1. Synthetic ADULT dataset: In addition to COMMUNITIES dataset, we conduct a similar experi- ment using a synthetic variant of ADULT dataset with sparse subgroups. We construct a subsam- pled ADULT dataset called SPARSEADULT by selecting the five smallest subgroups (whose sizes are at least 192) from ADULT and randomly down- wwwn-samping them to smaller samples with sizes in [40, 60] (see Table
Table 3: Subgroup sample counts of the original ADULT and SPARSEADULLT datasets. Subgroup index starts at I with the smallest subgroup. The sizes for subgroups of index over 6 are the same.
Subgroup index
ADULT
SPARSEADULT
1
192
46
2
233
54
3
500
57
4
789
5
964
We then evaluate five algorithms on SPARSEADULT and report the trade-off results in Figure 7 Similar to the case for COMMUNITIES, it shows that DRAF preserves superior subgroup and marginal fairness performance, specifically for higher fairness range (c.g., small MP(1), WMP, and MP(2)), on SPARSEADULT
Spare 120t
Scures Adult
Spare 2207
Spares sdue
0.2
0.02
049
636
0.75
11
15
0.5
19
0.5
Figure 7: Trade-off between fairness level and accuracy on SPARSEADULT dataset. (Left to Right) MP(1), WMP, MP(2) vs. Acc. We set y 0.001.
2. ACSINCOME dataset: We also conduct experiments on an additional tabular dataset (ACS IN- COME, see Section B.T for the details of this dataset). The results reported in Figure 8 show that
19

---

Published as a conference paper at ICLR 2026
DRAF exhibits similar behavior these datasets the four datasets currently used, which further supports the empirical outperformance of DRAF.
6375
6350
677
0.72
2.30
0.300
Uniar
4 0.100
0.100
642
Fmn
0.25
100
130
088
Figure 8: Tra between fairness level and accuracy on ACSINCOME dataset. (Left to Right) {SP, MP(1), WMP, MP?2)) vs. Acc. We set to 0.001.
Scalability To assess the scalability of DRAF with respect to the number of subgroups (SS) = 29) we measure its running time as [S] increases. To do so, we construct toy dataset with n 216 and randomly assign sensitive attributes to the data. As shown in Table the runtime of DRAF increases only moderately even though the number of boggroup-subsed grows exponentially (by 27% when |S] grows from 2 to 2 2). This suggests that DRAF remains scalable in terms of computation time.
Table 4: Comparison of runtime of DRAF for various cases of |S| (100% for q = 4).
S 29
24
2
2
2
212
2
Runtime
100%
101%
106%
105%
105%
127%
B.5 EXTENSIONS OF DRAF
Extension to multi-class classification Here, we show that DRAF is not limited to binary clas- sification but can be extended to multi-class classification problem. We define the faimess measure in this setting as the maximum of the parity gaps across all classes, following Denis et al. (022)) and compare DRAF with the existing baseline method Denis et al. (2024). Following Denis al. (2024), we use COMMUNITIES dataset with five classes and binary sensitive attribute (binarized proportion of speaking english well).
Table 5: Comparison of performance for multi-class classification problem.
Ace
Max. of MP over classes
Unfair 2024
0.457
0.108
(Denis et all
0.365
0.056 0.380
DRAF V
0.054
As shown in results in Table DRAF achieves competitive fairness level compared to the baseline, while attaining a higher accuracy.
Extension to equalized odds In addition to demographic parity notion, we further verify that DRAF can be extended to other group fairness notions, e.g., equalized odds (EO). We modify
the DR penalty for EO as: DR v. = En (v c - (
Σn (vT (vT=)-H))² o(i))) -E 21: E Wm. Wi 1) - and DR (f, v. :- (Ea >T cu -w]]
Cim
Cim
21(ss; Wm. yi = 0) - 1, where the former is for TPR (True Positive Rate) and the latter is for FPR (False Positive Rate). Then, we minimize "'n "V,, s:)) + (a-DR (f. v.) + 2-DR (f.v.
where 3-DR2pR and 2-DR are the corresponding 2- transformations of DR (f, v. and A (f, v,g), respectively. We call this modified DRAF algorithm specially designed for EO as DRAF-EO.
For fairness performance, we consider marginal faimeess and subgroup fairness measures, similar to the main analysis on demographic parity (DP). Let n4 Σi= T(y 1), n Σm= T(y
20

---

Published as a conference paper at ICLR 2026
0), n+ Ei=1 I(y 1, 8), and n=- Σi=1 I(y 0,8; s). We also define
the positive prediction ratios P+ 1
no Eiy,11 1litt p- == n+. Σ =1 1(i
1), p- = R- - Liu = 1), and p_ == 1 D. 1(: = 1). Furthermore,
(a) (a) (a) PL) and P... P +.f.lla J.f.jlaaPP... ffila are defined similarly. Table describes
++ Pt.L L.
the fairness performance measures used in the experiments for EO.
Table 6: Fairness performance measures for EO.
Name
Meaning
Formula
TPR(0 (1)
I-th order TPR
max ZO
+ (a)
+,L - p-1
(0)
FPR
(-th order FPR
maXx. L/=1 E.
(0.1)
(2(4) - 1-1
(0)
WTPR
Distributional TPR
maxyely max
WI *1(P+.1510.
P+,),
WI (P: P.s.s11 P+,))
(1)
WFPR
Distributional FPR
maXje(wl max
W1
P-,)), W F.l11, P-.))
STPR
Subgroup TPR
max.e
D+. p+
SFPR
Subgroup FPR
p P_
For baseline method, we consider FairICP (Lai & Guan 2025 which is specially designed adversarial learning algorithm for EO in presence of subgroups. The results are given in Tables 7 and which show that DRAF-EO performs competitive to FairICP, enhancing the empirical supe- riority and flexibility of DRAF
Table 7: Comparison of marginal fairness (EO) on ADULT dataset.
Prediction-based
Distribution-based
Method
Acc
TPR
FPR
(FPR()
WTPR
WFPR
WIPR--WPPR
Unfair FairICP (Lai & Guan 2025
0.855
0.0993
0.0886
0.0940
0.0687
0.1183
0.0928
0.804
0.0342
0.0150
0.0238
0.0216
0.0214
0.0207
DRAF-EO
0.804
0.0155
0.0010
0.0082
0.0113
0.0087
0.0100
Table Comparison of subgroup fairness (EO) on ADULT dataset.
Method
Acc
STPR
SFPR
SIPR
Unfair FairICP Lai & Guan 2025
0.855
0.0565
0.0284
0.0422
0,804
0.0154
0.0043
0.0091
DRAF-ER EO
0.804
0.0056
0.0004
0.0030
21

---

Published as a conference paper at ICLR 2026
B.6 ADDITIONAL STUDIES
Excluding the marginal subgroups from W Let DRAF denotes the DRAF variant whose W does not include the first-order marginal subgroups. Figure 2 shows that, excluding first-order marginal subgroups from W (i.e., DRAF-.) can harm first-order marginal fairesss, even subgroup fairnsss is satisfied. Moreover, on COMMENTS dataset, DRAF-m and DRAF perform compa- rable in terms of MP(1, when MP not small, but DRAF significantly outperforms DRAF m in view of WMP. This observation suggests that achieving prediction- baaed fairness (e.g., MP does not necessarily guarantee distributional fairness (e.g., WMP), and it highlights the need to control distributional fairness as well, which DRAF aims at.
23.33
2
2
0.00
fece
041
0.01
Dut.t
Quetentayy
0.1
0453
0833
5.0
2.03
030
3.3
DM7
0.53
411
Queeettay
4.04
$11
533
3
3
4.09
Figure 9: Comparison of DRAF.. and DRAF in terms of SP (top), MP(1) (middle), and WMP (bottom). We set y to 0.2, 0.001, 0.2, and 0.05 for ADULT, DUTCH, CIVILCOMMENTS, and COM- MUNITIES dataset, respectively.
Note that, on COMMUNITIES dataset, DRAF.. and DRAF may ap- pear similar in terms of MP(1) however, it is because DRAF... fails to achieve moderate fairness levels (e.g.. [0.02, 0.2)). leaving no point on the Pareto-front line. See Figure 10 for evidence that controlling MP(1) is not numerically easy for DRAF... That is, a large drop in MP(1) is occurred at X = 0.2 and we observe that using À E [0.2, 0.3] does not provide intermediate fairness levels.
Commrrrbies
retes
0.1
08
0.
1.0
Similarly, we also consider W that excludes the second-order marginal subgroups. Let DRAF denotes the DRAF algorithm whose W does not include the second-order marginal subgroups. Figure [ shows that the second-order marginal fairness can be slightly harmed when excluding the second-order marginal sub- groups in W. On the other hand, including the second-order marginal subgroups in W does not sacrifice first-order marginal or subgroup fairness, while can contribute to improving the second-order marginal fairness. Hence, we basically recommend build- ing W to include all the first-order, the second-order, and subgroups.
Figure 10: A plot between and MP(1) for DRAF.. Fm on COMMUNITIES dataset. We vary E O.0,0..,..,,1..0
Adult
Mddt
Acul
0.82
0.22
0.82
0.00
Nethod
0.30
Unter
Unfer
0.72
0.78
piaF
0.78
DRAF
DMA
0.26
DSA
0.76
DRWT
1.5
3.0
45
10
15
25
13
20
SP
Figure 11: Comparison of DRAF -ma and DRAF in terms of subgroup fairness (left: SP), first-order marginal fairnsss (center: MP())), and the second-order marginal fairness (right: MP(?)) on ADULT dataset.
22

---

Published as a conference paper at ICLR 2026
vary Y {0.001, 0.0,,,.,0000,,,000.. 0.2, 0.3) and compare the performance. The results in Figure 12 show that a larger y (e.g.. 0.3) degrades subgroup faireess performance compared to small y (c.g.. 0.001). Conversely, since DRAF minimizes the worst disparity over subgroup-subsets in W, a small y may lead to slightly worse first-order marginal fairness than large 7 (e.g., 0.001 for COMM.CTSENNTS dataset), as it could focus on higher-order or subgroups rather than first-order marginal fairness for some cases.
Impact of y To support the claim in Section 5.5
Duld
Urifomenets
Desmant to
0.330
8om
Nedicc
3 0.43
Habic
Life
0.50
0.99
7-02
14
0:50
2.5
13%
150
3.5
0.58
964
042
0.1
6:3
0.8
DMM
0100
Destunt
084
0.00
0.3
Mobicd
0.75
0.000
0.000
043
0.00
689
0030
65
0.50
15
350
705
Figure 12: Impact of y for DRAF in terms of subgroup fairness SP (top) and first-order marginal fairness MP (bottom).
Figure 13 provides similar results for (i) the distributional first-order marginal fairness WMP and (ii) the second-order marginal fairness MP Similar to Figure 12] a too small y (e.g.. 0.001) may lead to slightly worse first-order marginal fairness than a larger 7, while too large 7 (c.g., 0.2 in COMMUNITIES dataset) would harm the second-order marginal fairness.
642
Acst
Dutth
Ovlcomment
Commontt et
0.25
689
0.000
0.70
pobk
pul
34
2.5
300
0.5
0.4
1210
652
0.00
0.5
Vedic
0.00
p10001
6.79
Unai
611
689
74
15
130
12.1
152
Figure 13: Impact of y for DRAF in terms of distributional first-order marginal fairness WMP (top) and second-order marginal fairness MP(2) (bottom).
To analyze the effect of y in more detail, we categorize subgroups by size (large, medium, and small) using 0.3, 0.6 quantiles and evaluate how their fairness levels on the test data changes as y varies. This subgroup-wise analysis provides a clearer view of how 7 influences fairness across different group sizes. To this end, we train an unfair model (learning without any fairness constraint) and fair model learned by DRAF for various values of 7. For every subgroup, we compute the disparities (unfairness levels) of the unfair model and the fair model, and then take their difference (subgroup unfairness of unfair model subgroup unfairness of fair model). A positive difference means that the subgroup treated more fairly by DRAF than by the unfair model, whereas a negative difference suggests the opposite. We then summarize these differences using boxplots, grouping subgroups into small, medium, and large categories by size.
The results in Figure 14 show that: (i) for large subgroups, the differences are positive across all values of 7 indicating that DRAF reliably improves fairness for these subgroups; (ii) for medium- sized subgroups, the differences tend to be close to but become positive as y decreases, suggesting that a too large 7 is undesirable for these groups; (iii) in contrast, for small subgroups, the differences concentrated around zero or negative with large
negative when y is large (e.g., 7 0.4),
23

---

Published as a conference paper at ICLR 2026
Y 0.01
Y-
Y-
Fair
CMr: in..in Subgrou Dispartess
Cfft: in Subgrouu Disparites
0.06
0.04
0.02
6.22
642
Subgroup
0.02-
0.42
0.42
-2.04
-0.05-
-0.00
Large
Large
Figure 14: Comparison of differences subgroup disparities (Diff. in Subgroup Disparities) be- tween the unfair model and the fair model trained by DRAF, categorized by subgroup size (small, medium, and large).
variations for all 7, indicating that we cannot reliably regard these tiny subgroups being treated fairly. This empirical result further supports our theoretical finding Theorem 3.1 that enforcing fairness on very tiny subgroups in the training data does not guarantee fairness for those subgroups on the test data.
Choice G For the discriminator class 9, we compare sIPM, RIPM, and HIPM for IPMg. in terms of the trade-off performance. See Figure 15] for the results on the four datasets. The key findings are: (i) sIPM (our default the main analysis) performs best in most cases, though RIPM slightly outperforms sIPM on COMMUNITIES; (ii) RIPM performs similarly to sIPM overall except for ADULT dataset; (iii) HIPM underperforms both sIPM and RIPM in most cases.
Accordingly, recommend using the more stable IPMs such sIPM and RIPM rather than HIPM, whose more complex discriminator architecture often leads to less stable training and suboptimal models.
Acst
Satth
Ouiconmar
Commun tiee
0.25
2002
0.75
0.80
cal jom
602
Lome)
035
(e4r Lone
0.150
DRV S9Mn
6.76
DRAI LERN)
(a) ADULT
(b) DUTCH
(c) CIVILCOMEENTS
(d) COMMUNITIES
04500
03:0
0280
Nathed
Pateed
0.75
Netol
EBM
038
18/6
LIN)
2012
Agrp
(e) ADULT
(f)
DUTCH
g
CIVI.COMMENTS
(h) COMMUNITIES
Figure 15: Trf between faimess level and accuracy with three IPMs (sIPM, RIPM, and HIPM)
for G. (Top, Bottom) SP vs. Acc, MP(1) Acc.
24

---

Published as a conference paper at ICLR 2026
Robustness under noisy sensitive attributes To investigate the robustness of DRAF under the noisy sensitive attribute setting, we construct a controlled experiment on modified ADULT dataset. We randomly build missing values into the sensitive attribute at rate 0.01. For the baseline GF, any column with at least one missing sensitive attribute is discarded, since GF requires complete subgroup define its faimess constraint/penalyy learn fair models. In contrast, DRAF can still be applied partially to samples with missing values. That is, for samples with missing sensitive attributes, we impose fairness constraints only on subgroup-subset. that can be formed using the observed attributes, and ignore subgroup-subset that involve any missing attributes. This approach can be formally described as follows.
For s ($.1..... Sig) E 1,0,1,NAJ the indicator for a subgroup-subset W E Wis
if s E W and 8i # NA,
C,W
-1,
s & and Sú # NA,
0, otherwise.
Thus the full vector is
c: = (c..w) wew
In other words, the missing sensitive attributes selectively zero out only the corresponding com- ponents of cr whose membership unknown, while subgroup-subsets defined solely by observed attributes remain active. The results in Togure[T]suugees that DRAF is more robust than the baseline (GF); it achieves better fairues-accuurac trade-off than GF, suggesting the robustness DRAF in presence of noisy (missing) sensitive attributes.
Adult
Adult
0.86
0.86
0.84
0.84
Acc
Acc
0.82
Method Unfair
0.82
Method
Unfair
GF
GF
0.80
DRAF v
DRAF
8
12
16
4.5
6.0
Mp(1)
x10-2
SP
Figure 16: Trade-off between fairness level and accuracy when 1% of the sensitive attributes 'Mar- ried' ADULT dataset are randomly set to missing. (Left, Right) = MP(!) vs. Acc, SP vs. Acc.
25

---

Published as a conference paper at ICLR 2026
B.7 DISCUSSION ON THE RELATIONSHIP BETWEEN MARGINAL AND SUBGROUP FAIRNESS
Achieving marginal fairness alone does not always guarantee subgroup fairness: even if each marginal subgroup treated fairly, certain intersections unions of sensitive groups may still suffer from unfairness (fairness gerrymandering; (Kearns et al., (018b)). Conversely, even if most subgroups are fairly treated, marginal fairness can still be violated when some groups are extremely sparse, so that fairness on the test data is not guaranteed (Theorem 3.1
This observation motivates our design simultaneously monitor both marginal fairness and sub- group fairness. Furthermore, we believe that, from an ethical and policy perspective, situation where most subgroups are fairly treated but a marginal subgroup (e.g.. 'all women') not, would be difficult to justify socially.
Figure 17 presents the overall hierarchy of subgroup-subsets, including marginal subgroups and (intersectional) subgroups, and highlights the subgroup- subseesss that DRAF focuses on. It also illus- trates that marginal fairness can be violated even when all (observed) subgroups appear to be treated fairly, especially when some subgroups are sparse.
$2
6600
4900 5100
2500
2'00
$2
X 5g
5g.
10000
= 3
3100
6900
2100
2800
255n
:250
2000 2.00
100
500
500 :550
2000
Automatically found by DRAF
active
inactive
550
5350
2550 4800
2100
(First-order) Marginal groups
(Second-order) Marginal groups
Intersectional Subgroups
y 0.07 = yn 700
Intersectional Subgroups
(First-order) Marginal groups
5₁ X
S1
fair
? no guarantee
$₃ X S2 X
$₁ 52
D
V fair
fair
Figure 17: (Top) Hierarchy of marginal subgroups and intersectional subgroups, with active sub- groups (whose sample sizes exceed a threshold) highlighted with beige color. Our proposed algo- rithm, DRAF, automatically identifies such active subgroups and enforces fairness on them. (Bot- tom) An visual illustration on the relationship between fairness guarantees from the intersectional subgroups to marginal subgroups.
26

---

Published as a conference paper at ICLR 2026
Example: subgroup fairness does not always imply marginal fairness Suppose 2. Assume that we are given the following configuration of dataset and predictions for a given f. We write the two sensitive attributes as E {0, 1} and b {0, 1), for simplicity.
Subgroup (a, b)
samples n(a, b)
positive predictions Topos (a, b) by I
Positive rate
p(a, Npos (a, b)
(0,0)
10
9
0.9
(0, 1)
10
0.9
(1,0)
10
0.1
(1,1) 10
0.1
The total sample size and the number of positively predicted samples are n = Ea, n(a, b) 40 and Rpos
L..o Apps (a, 20, respectively, hence the overall rate of positive prediction is
p
Bpus
20 0.5. Subgroup fairness level is then calculated as
40
max n(a, b) (0 b) p) = 0.25 x 0.9 - 0.5| = 0.1.
SP
(0.1))
On the other hand, we have n00, 0) + n00 1) = 20, P/po (0, + ppps (0, 1) = 18 so that Roo (0.0) (0.1)
0.9. Similarly, n11.0) 0) + 1),1) 20, pppss 0) Apos (1, so that Poor (poo 0.1. Thus, the first-order marginal fairness level for the sensitive attribute is
(0,00)++(001)
m21.0) (a(1))
0.4, which is relatively large.
27


Reviews:
[{"review_id": "96Eb6TOF8X", "reviewer": "Reviewer_gfUs", "summary": "This paper studies subgroup-subset fairness, whose goal is to ensure that a prediction model is fair on active subgroups that are not too small. The authors propose to use supremum integral probabilitiy metric (subIPM) for measuring subgroup-subset fairness. To make it easier to calculate supIPM, the authors propose a surrogate of supIPM named DR, which is the z transformation of a smoothed version (by another regression) of supIPM.", "questions": "Please see weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "S1. The motivation is clear, that the subgroup grows exponentially and that there could be data sparsity in subgroups that make the fairness measure not statistically meaningful.\n\nS2. Theoretical contents are in general clear to me (though I have questions listed in weaknesses part).", "weaknesses": "W1. A main argument of this paper is that we should use active subgroups to study subgroup-subset fairness. But from Figure 10, it seems that with varying $\\gamma$, the model doesn't seem to have much difference in performance. (There indeed are differences but just not very significant to me.) Could the authors provide more justifications on the impact of inactive subgroups for learning the fair model?\n\nW2. Following W1, the connection between Theorem 3.1 + Section A.4 and $|W| \\geq \\gamma n$ is a bit vague to me. Could the authors further elaborate on this?\n\nW3. For DR$^2$, the key idea is to regress $g(f_i)$ and $\\mathbf{v}^T c_i$. Could the authors provide more justification on why we can have this $\\mathbf{v}^T c_i$ as a smoothed $y_{W, i}$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5Q6md3ZCNl", "reviewer": "Reviewer_8N6S", "summary": "The paper proposes subgroup-subset fairness (enforce fairness only on sufficiently large subgroups plus all marginals) and an adversarial learner DRAF that optimizes a surrogate of a new fairness measure (supIPM) using a single discriminator; proves a generalization bound and that the surrogate upper-bounds supIPM; evaluates on ADULT, DUTCH, CIVILCOMMENTS, and a sparse COMMUNITIES dataset.", "questions": "Please see weakness.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Computational convenience: the paper proposes a novel metric for subgroup fairness, which only considers a representative subset of sensitive attributes, significantly bringing down the dimensions.\n2. Sound theoretical contribution: the authors have a rather complete theoretical analysis of their methods.", "weaknesses": "1. Experiments compare to REG, GerryFair, and a sequential post-processor, but these methods don't seem to get extensively discussed in the related work section, e.g., how the proposed method is different from [1]? Also, for multiple sensitive attributes especially in binary classification, there've also been some other literature around, e.g., [2] on binary classification with DP/EO constraints and [3] on EO with adversarial training fashion.\n2. “Subgroup-subset fairness” depends on the chosen W. Provide coverage guarantees: if all first-/second-order marginals are in W, what bound (if any) follows for full subgroup fairness? It would be beneficial if the authors can justify why some W is chosen while others are not (I'm imagining there could be some implied unfairness for unseen tiny groups).\n3. Datasets. I appreciate the comprehensive results on 4 datasets. However, ADULT is overused (e.g., see [4]); please consider newer tabular suites (ACS/Folktables, HMDA, LawSchool) or at least add some discussion on the limitations of these datasets (e.g., the label threshold for COMMUNITIES dataset).In addition, I feel the tasks for these four datasets are to some degree overlapping and limited, is the proposed method only working for binary classification or binary subgroups? If not, it could be more convicing experimenting on diverse learning tasks.\n4. Scalability. One novel point of this paper is that it avoid the exponentially large dimensions of subgroups. Is there any empirical evidence in terms of running time to support this claim? Or, how's the scalability regarding $|\\mathcal{S}|$? \n\n\n[1] Kearns, Michael, et al. \"Preventing fairness gerrymandering: Auditing and learning for subgroup fairness.\" International conference on machine learning. PMLR, 2018.\n[2] Agarwal, Alekh, et al. \"A reductions approach to fair classification.\" International conference on machine learning. PMLR, 2018. \n[3] Lai, Yuheng, Leying Guan. \"FairICP: Encouraging Equalized Odds via Inverse Conditional Permutation.\" International conference on machine learning. PMLR, 2025.\n[4] Ding, Frances, et al. \"Retiring adult: New datasets for fair machine learning.\" Advances in neural information processing systems 34 (2021): 6478-6490.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KP2KuXMjCQ", "reviewer": "Reviewer_bKec", "summary": "This paper addresses the challenge of subgroup fairness in machine learning, particularly when multiple sensitive attributes result in a large number of intersectional subgroups. Traditional fairness frameworks become impractical in such cases due to severe data sparsity and computational explosion.\n\nTo overcome these issues, the authors propose a new notion called subgroup-subset fairness, which ensures fairness across sufficiently large and socially meaningful subgroups while maintaining fairness for each attribute. They formalize this idea using the supremum Integral Probability Metric (supIPM) to measure distributional disparities and derive a computationally efficient surrogate formulation.\n\nBased on this, they introduce the Doubly Regressing Adversarial learning for Fairness (DRAF) algorithm, which enforces subgroup-subset fairness using only a single discriminator, avoiding the exponential cost of prior methods. Theoretical analysis shows that this surrogate metric upper-bounds the original fairness measure, providing guarantees without sacrificing efficiency.\n\nExperiments on benchmark datasets (ADULT, DUTCH, CIVILCOMMENTS, COMMUNITIES) demonstrate that DRAF achieves strong trade-offs between accuracy and fairness, particularly when data are sparse. The method successfully aligns subgroup and marginal fairness, offering both theoretical soundness and practical robustness.", "questions": "A natural question concerns how subgroup-subset fairness aligns with broader ethical objectives. Because the algorithm deliberately excludes minimal subgroups to ensure statistical stability, what ethical safeguards ensure that such exclusions do not marginalize vulnerable intersections? Could adaptive weighting schemes or uncertainty-aware selection criteria help mitigate this risk?\n\nAnother question arises from the interaction between marginal and subgroup fairness. The authors show that DRAF aligns these two fairness notions empirically, but it would be interesting to formalize the connection: under what theoretical assumptions does ensuring fairness on selected subgroup-subsets guarantee approximate fairness across all subgroups?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper’s major strength lies in its theoretical innovation coupled with practical feasibility. The authors do not simply modify existing fairness metrics but instead derive a new conceptual layer, which is subgroup-subset fairness. It realistically balances statistical soundness and social relevance. This idea acknowledges that enforcing fairness over all possible intersectional subgroups is statistically impossible, and instead directs fairness efforts toward meaningful, estimable subsets.\n\nAnother strength is the mathematical coherence. The connection between fairness and regression-based measures (through the doubly regressing 𝑅^2) transforms a complex adversarial fairness optimization problem into one that is differentiable and computationally manageable.\n\nFrom an algorithmic standpoint, DRAF’s design is efficient. By requiring only a single discriminator, the method retains adversarial flexibility without the exponential cost typical of subgroup fairness models.\n\nEmpirically, this paper includes multiple datasets with varying degrees of sparsity, showing that the method generalizes well.", "weaknesses": "While the theoretical development is solid, the paper’s presentation of empirical limitations could be more transparent. Although DRAF achieves strong results on several datasets, the analysis does not deeply explore why it performs better in certain settings or whether there are trade-offs when subgroup distributions overlap significantly. A more detailed analysis of failure cases would make the argument more comprehensive. For example, when subgroup definitions are noisy or when marginal fairness conflicts with subgroup fairness, how is the performance?\n\nThe paper briefly mentions the threshold parameter γ, which decides which subgroups are treated as “active.” However, this choice will strongly affect the fairness results. A clearer explanation or guideline on how to set γ properly would make the method easier to reproduce and evaluate fairly.\n\nAnother weakness is the limited discussion of the robustness of the DRAF. Since this surrogate replaces the original supIPM measure, it is important to know whether it consistently preserves the relative fairness ranking between models. In other words, if one model is fairer under supIPM, is it guaranteed to remain fairer under DR? The paper does not clarify this point. Without such an analysis, readers cannot be certain that the surrogate behaves reliably in all cases. The authors may provide some consistency conditions or give some counterexamples.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)