Fair Classification by Direct Intervention on Operating Characteristics
Authors: Kevin Jiang
Edgar Dobriban
Venue: ICLR 2026 Poster (2026)
Keywords: algorithmic fairness; post-processing; linear-fractional constraints; minimal interventions; constrained optimization
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: We develop new classifiers under group fairness in the attribute-aware setting for binary classification with multiple group fairness constraints (e.g., demographic parity (DP), equalized odds (EO), and predictive parity (PP)). 
We propose a novel approach based on directly intervening on the operating characteristics of a pre-trained base classifier, by: 
(i) identifying optimal operating characteristics using the base classifier's group-wise ROC convex hulls; 
(ii) post-processing the base classifier to match those targets.
As practical post-processors,
we consider randomizing a mixture of group-wise thresholding rules subject to minimizing the expected number of interventions. 
We further extend our approach to handle multiple protected attributes and multiple linear fractional constraints.
On standard datasets (COMPAS and ACSIncome), 
our method simultaneously 
satisfies approximate DP, EO, and PP with few interventions and a nearly optimal drop in accuracy; and compare favorably to previous methods.

Published as a conference paper at ICLR 2026
FAIR CLASSIFICATION BY DIRECT INTERVENTION ON OPERATING CHARACTERISTICS
Kevin Jiang & Edgar Dobriban
Department of Statistics and Data Science University of Pennsylvania Philadelphia, PA 19104, USA {kojiang, wwbribannnna.oo. @wharton upenn. edu
ABSTRACT
We develop new classifiers under group faimess in the attribute-awar setting for binary classification with multiple group fairness constraints (e.g., demographic parity (DP), equalized odds (EO), and predictive parity (PP)). We propose novel approach, applicable to linear fractional constraints, based on directly intervening on the operating characteristics of pre-trained base classifier, by (i) identify- ing optimal operating characteristics using the base classifier's group-wise ROC convex hulls and (ii) post-processing the base classifier to match those targets. As practical post-processors, we consider randomizing a mixture of group-wise thresholding rules subject to minimizing the expected number of interventions. We further extend our approach to handle multiple protected attributes and mul- tiple linear fractional constraints. On standard datasets (COMPAS and ACSIn- come), our method simultaneously satisfies approximate DP, EO, and PP with few interventions and near-oracle drop in accuracy; comparing favorably to previous methods.
INTRODUCTION
Modern machine learning systems inherit and can amplify historical and measurement biases present in data, raising concerns in high-stakes applications such as criminal justice, credit, hiring, and healthcare (see e.g.. Barocas & Selbst) 2016, Obermeyer et al.] 2019, Raghavan et al.) 2020] Chouldechova & Roth 2020; Fuster al. 2022 etc). These concerns have galvanized the field of algorithmic fairness (see c.g., Barocas et al. 2023), which formalizes fairness criteria and devel- ops methods to enforce them.
One broad family of metrics, termed group fairness criteria, requires that a performance metric of model is equal across protected groups (e.g., race, gender, age). These performance metries often motivated by legal rulings, regulatory guidance, and broader normative considerations (e.g..
anti-discrimination norms, Hardt al. (2016); Verma & Rubin (2018); Barocas al. (2233)
Methods designed to ensure group fairness can be roughly categorized into three categories based on where they intervene in the training pipeline: pre-processing intervenes on the training data via methods like reweighing/sampling, causal inference, and adversarial debiasing (see e.g., Salazar
al. 2021 Zhang Sang, 2020; Zeng et al. 2024 Plečko al. 2024 etc); in-processing modilies
the learner $ objective or model architecture (see e.g.. Zhang et al.) 2018a Agarwal et al. 2018
Cho et al. 2020 etc); and post-processing alters the predictions of fixed learned model (see e.g.,
Hardt et al. 2016 Alghamdi et al. 2022 Xian & Zhao 2024 etc). These methods have found broad
applications (see e.g., Jammalamadaka Itapu 20233 Weerts al. 2023 Mackin et al.
2025 etc).
In parallel, policy and litigation have highlighted the desire to simultaneously satisfy multiple fair- ness constraints (e.g., analyses surrounding the COMPAS model, see Larson & Angwin (2016); Dieterich et al. (2016)). However, incompatibility results in the literature show that perfect compli- ance across sufficiently many metrics is generally impossible except in special cases (Chouldechoval 2017 Kleinberg 2018 Defrance & De Bie 2025). Consequently. many works adopt approximate group fairess, where a model's s performance across groups are only required to be approximately equal (see, e.g., Celis
e.g.. et a (2019) : Zeng al. (2024))

---

Published as a conference paper at ICLR 2026
Our contributions. In this work, we develop new classifiers aiming for approximate group fair- ness for binary classification with multiple group fairness constraints (e.g., demoorappiic parity (DP), equalized odds (EO), and predictive parity (PP)), long they have a linear fractional represen- tation related to that considered in Celis et al. (201)). Our novel approach directly intervenes on the operating characteristics of a pre-trained base classifier, by: (i) identifying optimal operating characteristics using the base classifier's 's group-wise receiver operating characteristic (ROC) convex hulls; and then (ii) post-processing the base classifier match those targets. We extend our ap- proach to handle multiple protected attributes and multiple linear fractional constraints. On standard datasets (COMPAS and ACSIncome), our method simultaneously satisfies approximate DP, EO, and PP. They lead to few changes to the predictions made by the original classifier and a nearly optimal drop accuracy; comparing favorably to previous methods.
RELATED WORK
Both empirically and theoretically, it is known that satisfying multiple fairness constraints can be challenging (Chouldechoval 2017 Kleinberg 2018 Majumder
2023 Defrance & De Bie 2025). Bell et al.]] (2023) show that, in principle, there may exist classifiers that achieve approximate fairness for multiple constraints. However, this assumes the existence of classifiers that can satisfy an arbitrary assignment of labels to the test set, and also requires tuning population-level quantities that are typically out of our control.
In highly relevant work, Celis et al. 2019) propose a meta-algorithm based on optimization perspective in the space classifiers. Our approach differs fundamentally, since we rely on the geometry of the realizable regions traced by the convex hull of each group's 's ROC curve. Hsu ict al. (2022) develop post-processing methods based on mixed-integer linear programming for a more granular notion of fairness, equalizing group rates across scores/predicted probabilities as opposed to binary labels. Their definitions reduce to ours when using two bins. With this approach, empirically, our method outperforms those from Celis al. (2019) and Hsu et al. (022).. Due to space limitations, additional related work is reviewed in Section A.
3 PROBLEM SETUP
We consider fair binary classification problem where two types of feature are observed | the usual feature X E X' and the protected featurr A E A which we take to be discrete, with A {1, , m). m 2 2. We would like to achieve non-discrimination with respect to the protected groups, defined by the values E A of the protected feature. The features and binary label are distributed according to (X, A, Y) IP. Given pre-trained probabilistic predictor 8 X A -> [0, 1] and an i.i.desampled post-processing se D post = {(x;, a;, H drawn from P. we seek to develop a (possibly randomized) classifier f f: X A A {0, 1} that minimizes the population risk L(S) (Xe(J(X, A), Y)J, for a loss é (0, 1) y + R subject to K 2 1 fairness constraints.
To impose fairness constraints, we consider equalizing certain group performance functions Gk.as which reflect the performance of the classifier over protected groups We focus on loss functions and group performance rates which can be expressed as ratios of linear combinations of a classifier's true positive rate (TPR) and false positive rate (FPR); as well as the associated false negative rate (FNR) and true negative rate (TNR), for each group a E A:
TP). 1
FPR, (f) = Pr(f=1 Y-0, A=a); TNR.
(NR := TPR.
== (f)= 1- (f)
(I)
We consider the following class of group performance functions, special case of more general notions from Celis et al. (2019), but encompassing many common fairness metrics, see Table
We dafer the extension for multiple classes to $4.4
2In the post-procetd processing literature for faimess, this has heen alternatively called holdout calibration
set (Pleiss et al. 2017 Hansen et al. 2024).
'When it is clear which classifier the group-wise operating characteristics are tied to, we will sometimes omit the classifier from the argument, writing, for instance TPR,, etc.
2

---

Published as a conference paper at ICLR 2026
Table 1: Fairness metrics covered by L.FIL group performance metrics
metric
type
coefficients (iāx, Čk.a)
Demographic parity (DP)
linear
No. 17 = =0,00000,,0..
Equal opportunity (TPR parity)
linear
7 (1,0,0)ū (0,0,1)
Predictive equality (FPR parity)
linear
7 (0.1,0); (0,
Equalized odds (TPR & FPR parity)
linear pair
Predictive parity (PPV parity)
lin. frac.
7 = 0,0:0, 00 (Ma, 1 1 ka. 0)
False omission rate (FOR) parity
lin. frac.
γ = (-Ra, 0, Ta); (- -1 n.).
Accuracy parity
linear
== (Ta, -01 ra), Ta): 00)
Here, Nu Pe(Y=1 A=a) demotes group prevalence/hase rate.
frac.) metrics, demominator
positivity is required: for PPV, TPR,, + (1 JPPR, O (nonzem selection); for FOR, m,(1 TPR.) =a)( 11 FPR.) > 0
(nonzero nom selection).
Definition 3.1 (LF group performance functions). For each group and constraint linear frac- tional (LF) group performance function Gk.a is defined as
Gk,a(f) = au Pa) (ūx pa)
with P. ==
aF Pa) 0,
where a, Uka 3 coefficient vectors that may depend the underlying population distri- bution, but not on the classifier f. A linear group performance function Gk,a(f) = (ūk, Pa) is obtained when ūk = ()) selects the constant component only.
Linear fractional (linear) fairnes constraints are functions of only linear fractional (linear) group performance functions. For instance, demographic parity (Calders et al.) (2009) is linear fairness constraint, since it requires GDP, (f) - a (f) for all a F a', where the group-wirs wise selection rate is, with To Pr(Y=1 =1 A-a),
(TDP a: Pa) (UDP, a Po)
- =f)(a())PP((-111 A=a) Ta TPR, + TT FPPR
with uDP,a a = (Tay 1 na, 0), TPP = (0, 00) Predictive parity (Chouldechova 2017 is linear fractional constraint, since it requires Gpp.a - Gpp,a' (f) for all 7 a', where the positive predictive value is
T. TPR.
(ūrr Pa) (ŪPP,a: Pa)
GPF Pr(Y=1 A=a) ( Ta TPR, (1 T. FPR.
where up (Ta, O, 0), ěPp.a = (T., Ta, 0), with denominator (UPp, Pa) Pr(f=1 A=a) for groups with nonzero selection rate.
Moreover, since satisfying multiple fairness constraints exactly may be impossible (Chouldechoval
2017 Kleinberg 2018 Defrance & De Bie 2025), consider 5-approximate fairness, e.g.,
(Xian & Zhao 2024 Zeng et al., 2024). This requires pairwise differences of group performance functions differ by more than dz 2 0: |G,,a(f) Gk (f)l s 8z. Va # a', k E [K], where we further collect all the user-specified disparities 62 as single vector 5 E [0,
We consider loss functions that are linear combination of linear group performance functions L(f) = EaEA (aa Pa), Pa = (TPR., FPR,, 1)T, 1,,%% E RR3 Altogether, on the population level, our fairness constrained optimization problem is then
'The usual nisclassification rate L()) EoEAPa Pa [Ta TPR.) + +( ]FPR] Pr (S(X.A) # y), can he recovered by taking coefficients % to be % (-PowayPa Pa -aa) TT) Po Pr(A=a), Pr(Y=1] A=a).
3

---

Published as a conference paper at ICLR 2026
Population-level Optimal Classification with Linear Fractional Fairness Constraints
min 1
Σ (aa)
s.t. max [Gk,af) Gk. (f)l 8k, k [K],
(2)
aEA
(i (f())) Gk,a(f) a Pa (f))
(T Pa())) O, Va, k; Pa(f) (T)
where %a E Id are fixed loss-coefficient vectors; Wk Uk,a R are fixed coefficient vectors for constraint & [K] and group E A: and òù 2 0 are prescribed faimess tolerances for each & E [K].
The Bayes optimal regression function 7o takes values, for all x, na(x) = Pr(Y=1|X=z, A=a), E A. We call classifier f X' x A + {0, group-wise thresholding rule (GWTR) if it thresholds Te at group-specifte values ta. a E AA::
f(r, a) = 1 (x) > ta) for some to E [0.1),
(3)
In what follows, we will be considering the convex hull of ROC curves, which case points on the hull are obtained by allowing mixture of thresholding rules.
Definition 3.2 (Mixed-GWTR), A (possibly randomized) classifier f X A {0, is mixed-
GWTR for each group a E A, there is a finite index set Ja. thresholds {ta.j E [0. je., and nonnegative weights (Na,i with Eje,, Aa_- 1, such that
((((2, = a1, 1
Σ Aay 1 (na(x) > la.s). JEJa
(4)
For broad family of fairness constraints defined by linear fractional group performance functions, an optimal solution to the population problem equation 2 can be realized by a GWTR with suitable thresholds {ta- JoEA (Celis al. 2019). This result, however, is not directly practicable, as it only describes the optimum at the level of the unknown population from which the data has been sampled, and presumes access the regression functions 7/a- In practice, one must estimate these functions as well as TaEA- Due to this estimation step, in challenging situations when the sample size is small, the feasibility constraints can possibly become infeasible. We will see experimentally that this step can indeed be highly noise-sensitive.
FAIR CLASSIFICATION VIA ROC FEASIBILITY REGIONS
Motivated by the above observations, our approach relies on the following two steps.
(A) Restricting to post-processors. Given pre-trained probabilistic predictor X'x - [0. 1 intended approximate the label probabilities and a prot-pproessing set D post = {(0,, ai, y: y:) 1im consider post-processors obtained from s:
F = (s; Dpoa) = (f(;aa) obtained from s(: a) and Dpost (and possibly randomized)). (5)
(B) Moving to operating characteristic space. Instead of optimizing over functions S. we di- rectly work with their group-wise operating characteristics (or, rates). For each group a, define the realizable (or post post-processing) ROC region
Ra (s) = (Ipr, fpr) 3f Fxsuch that (FR. (tpr, fpr)
(6)
Allowing randomized thresholding in Definition 3.2 ensures that the of achievable rates start- ing from any given s is convex; so RR, (s) coincides with the convex hull of the ROC points generated by thresholding s(,
Hence, to restrict post-proccee processor, we equivalently require the classifier's group rate vectors to lie in its ROC convex hull (see 1
4

---

Published as a conference paper at ICLR 2026
Fair classification via operating characteristic feasibility regions (ROCF). Our method, ROCF, departs from traditional post-procsssing methods (and associated direct threshold search) by directly working with operating characteristics. We work with post-processors, constraining each group rates lie in the (population) realizable ROC region (s) (see $4. for the population setting and 1..2.1 for its empirical convex hull analog).
We next provide an overview of the steps. Due to space considerations, some details are presented in the supplementary material. For clarity, we also provide the full end-to-end implementation of our procedure for the setting of controlling for single fecrr-fractioal and linear constraint in A.3.3
4.1 RATE-SPACE REFORMULATION & POST-PROCESSING CONDITION
Let Pa = (TPR., F.R.. 1)T be as before, and define the lifted realizable set Rs(s) == {o = (tpr, fpr, 1) (tpr, fpr) E (s)}. To incorporate the post-processing constraint, and to move to the cow-dimessional space of operating characteristics, we reformulate equation to the form:
Population-level Optimal Fair Classification via Proe-srr Operating Characteristics
min (Falac
Σ (Ta,
S.t.
max 0,0 E. GR,a(pa) Gk,a' (px)) S on, k [K];
aEA
(u Pa) (Uk,a Pa)
(po)
(Ue.as Pa) 0, Va Pa E Ra(s), A
4.2 OPERATING CHARACTERISTIC FEASIBILITY REGIONS AND CENTROID-BASBD LINEARIZATION
The objective from equation 7 can be non-convex in {Po JosA due the linear fractional group performance constraints. Following Celis et al. (209)) and Xian & /hao (2024). we note that ensur- ing bounded pairwise differences (Gk, Gk,a' 6g is equivalent to the existence of a centroid Oe E [0, 1] with |Ga,a gkl d for all E A. Thus, to reduce the number of constraints, for each constraint after the introduction of the centroids, we split the constraints: Let K2 and KLE denote the indices of linear and linear fractional fairness constraints, respectively, so that KC2 LJ XCFF = [K].
[K], introduce a centroid @g. Moreover, since pure linear constraints stay linear
Linear constraints via centroids. For l KL, the disparity constraint in equation 7 is equivalent to the existence of centroid qu such that 7 < (Üz,a, (Pa) Is < inequalities in (Pa, (k), so we can treat q& as a decision variable while still having an LP.
&y 7. Va E A. These are linear
fractrnfractional constraints via fixed centroids. For k E KIF. write Uka(P) (ūk, p) and
Vk,a == (ūk,a, p). Assuming Vk,a 0, the centroid form (Uk,a (F,) 9al I by is equivalent to the pair of linear inequalities
-4) (p.) (ge- + (4) Va.( S O, (1x --4 VK. (Pa) - URa(Pa) SO, Va A.
(8)
Thus, for any fixed centroid qu: the linear fractional constraint becomes linear in Pa. Given o (qe)keKur, the set T(Ø 5) of { (aataeA satisfying the above constraints is called operating characteristic feasibility region (see Definition A.6), which we simply refer to as feasibility region for convenience.
Inner linear program for fixed linear fractional centroids. Given centroids {qx hELF, we obtain the following linear optimization problem in the rate variables Pa and the linear-centroids gk. with R., from the beginning of Section 4. and Vi (p) (ii P) from above equation 8
5

---

Published as a conference paper at ICLR 2026
Inner Optimization for Fixed Linear Fractional Centroids
min heek
Σ
(aa Pa) :8.t s.t. By S (ūk,,a,o) 94 S 22 E A,
aEA
(9)
equation 8
holdd & Vi,a (Pa) > O, wk E KIF; Pa Ea,
Moreover, at the population level R. is convex. If represented polyhedrally (as will be the case empirically via convex hulls in (A.2.I). then equation 9 a linear program. In practice, for stability purposes, we additionally enforce that the denominators are strictly bounded away from zero via the linear constraints Va (p,) 2 Ek Va A, k E KLF, for negligibly small positive constants (e.g., Ek = 1e-7 and see I.
Outer search over linear fractional centroids. For each linear fractional constraint KLF. we restrict the centroid to a compact interval Qs C (0, 1) that is consistent with pos--prcessing and denominator positivity, i.e., choices of qu for which equation 8 hoolds. We show later in $A.4 that we can take Q = [ōx/ 2, 1 - 52. We call these admissible centroids.
We then search over q Q = IIEELFF Q4 (e.g., via a coarse grid search) and solve the inner linear program (cf. equation g at each q. The explicit construction of Qx and the exact linear bands for common LF metrics (c.g., predictive parity) are deferred to the supplementary material (see $A.5.1
This outer search for fixed values of linear fractional centroids is justified by the following theorem (proof is deferred to Appendix A..4).
Theorem 4.1. Define the value function such that Φ(q) is the optimal objective value of equa-
tion for any q E I KErl, Then, the value of the optimization problem from equation 7 is equal minge @ DQq). Moreover, can find optimizer |PaleEA of the objective in equation by
selecting any minimizer q E arg mingeo & (()) and then optimizing the objective in equation at q¹
Empirical region search over ROC-hull supports. Given the post- post-processing set, we search over plug-in ROC-hull supports and solve modest-sized LPs for centroid cenrood--peecfii feasibility. feasibility guard ensures that, when needed, tolerances are minimally relaxed (see $ for details).
The following theorem demonstrates that the minimizer of our empirical region search procedure has Ö(1/vn) rate of convergence to the optimal faintess-oonsraained minimizer of equation 7 in risk error and fairness attainment, for any fixed probabilistic predictor. We will suppose that the feasible set of the population-level fairness-constrale let gº (aa be an optimizer Denote the objective value of equation 7 for group-wise lifted
problem from equation 7 is nonempty, and operating characteristic rates @ = {Pa JaeA as ((e) EnEA(fe
Theorem 4.2. Let 8: X' x A + [o, 1] be a fixed probabilistic predictor and let Drost be an i.i.d. poxt-processing sample with group and group-label specific sample sizes nh and Ba.yy respectively, with Paiin == mina.y Ne,y for a E A and y E 1). Also, let ē (pa JoEA be the lifted operating characteristics returned by our empirical region search procedure (i.e., Algorithm 2 in $A.2.1 with grid steps he for each linear-fractionl centroid and with En as the denominator guards. For ò > 0. define for j E 1),
4m log 5
4mK
Ma
+
C.
log
(10)
2na
2na
5
where C O is universal constant that depends only on {uk,a Uk JoEAAE but not on Do.j; m. K, or 8. Then, with probability at least - -,
( - _(())
Σ (7a.1 + no,0) + acAA
Σ ha + max Ek
kEKEP
KE
kEKiF
We neither require the upstream probabilistic predictor s(2, a) to be well-calibrated nor close to the Bayes- optimal regression function Pr(Y =1|X x, a).

---

Published as a conference paper at ICLR 2026
for every fairness metric l E KLF UKL max Gk.alPu) Gk, (Po:) S 8ū max(Na,1 + 77,00).
a,
Thus, if Amin 2 5- (og(m//0) and Ex h4 S then both the fairesss slack and the excess risk are OE)). Furthermore, in the (idealized) special case where the probabilistic predictor coincides with the Bayes-optimal regression function, Theorem implies that our region search procedure achieves the canonical ((1/vn) parametric rate of convergence the Bayes-optimal operating characteristics, both in risk minimization and fairness attainment.
In brief, the proof relies on uniform convergence of the empirical ROC hulls via the DKW inequality (see, e.g., Dvvretzkyy et al., 1956] Massart 1990, and Lemma AA.7) and Lipschitz control of both linear and linear-fractional fairness constraints (Lemma A.8); for space considerations, the full proof is deferred to $4.4.2
4.3 CONSTRUCTING CLASSIFIERS
We now seek to construct classifiers that achieve the optimal rates. Since there are many classifiers that can achieve any operating characteristic. the practitioner impose additional desiderata such as minimizing the expected number interventions, which we define as label flips from the base classifier f(U) (see A..311.. Here, we propose two versions of an approach for this problem.
4.3.1 RANDOMIZATION PROCEDURE
Take the base post-processor f(() be mixed-GWTR (see equation 4 whose operating point lies on the boundary of the convex hull of the empirical ROC curve, i.e., for all x, a:
f(0) a) = (1 10--,,) 0a)1 (s(2, a) 2 th,a) + 0g (s(x, a) 2 t++1,a)
0g E [0.
(1I)
where tn+la 2 th a 1.a E Ha are two adjacent points on the support of the empirical convex hul (ef. $A.2.1p. Let, for all x, a. (x) := Pr(f(0) 1 X x, A a) be the positive prediction rate of the base post-processor, and denote the operating characteristics of f()) as !PR! = Pr(f(0)=1
Y=1, A=a), !PR!") Pr(f("=1 Y=0, A=a), FNR 1
TPR(") (0) TNR (0) (TPR,, FPR.). ) e.g. outputs from Algorithm
F The group-wise optimal operating characteristics are fixed values
Then the final classifier that does not depend the inputs æ. This transformation also shifts the operating char- acteristics of f()) towards the non-random classifier. There are several possible ways implement this transformation, and here we discuss two.
f randomizes f(0) aiming to "regularize" or "shrink" Ja towards a
LabelFlipping flips the mixed-GWTR GWTR labels with outcome- deeendedd probabilities Pa.y Pr(f 1 A = a, ( = y)) y E {0, 1}. The final prediction is distributed as a Bernoulli random variable with success probability
Pr (ī(r, = X x, A A= Pa.0 -aax)ax)) - (a,)
(12)
This induces linear map on the operating characteristics:
TPR, Pa. TPR. Pa.0 TPR(") FPR, = = (0) + + (1 (1-FPR())
(13)
Fixing the bascline post-pree prssesrocessor and the target operating points uniquely determines the free pa- rameters of the randomization procedure (i.e., the flipping probabilities Pa,y for LabelF1 (elppppingg)
Geometrically, the set of operating characteristics attainable by equation [3 is the triangle spanned by the baseline hull point (TPR (0) FPR (0) and the trivial classifiers (tpr, fpr) = (1, 1) and (0, O) (equivalently (0, 1) and (1, 0) in the (FNR, FPR)-plane).
Since H. is constructed solely from a probabilistic predictor and a post-procsssing set, and we add ran- domization implicit in the mixing parameter 0g. (()) indeed valíd post-processor (cf. equation

---

Published as a conference paper at ICLR 2026
Since f(0) is mixed-GWTI in equation
11 its operating point along any hull edge can be
parameterized by a single mixing parameter 6a E
[0, 1] between adjacent supports (h, h-1):
FNR (0) 0.0 = (1 - 0a) FNRR
(h)
+ 0,FNR (1+1) FPR (0) 0, = (1 0g FPR! + 0 0.FPR! (14)
Thus, the linear map from equation 13 gives the 2 x 2 system
FPR FNR.
FPR
1 - FPR 0.0 (0) FNR a,0
Pa. (P.
0,0 (0)
(15)
1 m.
FNR
0,0
whose determinant is det(() FPR (0) 0.0
+ FNR (0)
0.0 1, which is zero only when the post-processor
has degenerate ROC curve. Consequently, given a target operating characteristic (FNR., FPR.
and fixed mixing parameter 0., the parameters of randomization are uniquely determined by the rate-matching equations when det (0) + O with feasibility requiring 0 S Pa.o(f), Pa, s 1. We present the details of minimizing interventions with this label flipping scheme in Section A.3.2
Remark 4.3. While Hardt et al. (2016) considered label flipping and threshold search in some spe- cial cases, they did these separately; which limits the set of operating points their classifier can attain. More recently, HHsu al. (2022) used label flipping randomization on top of GWTRs to simultaneously satisfy multiple fairness constraints. However, their procedure implicitly fixes the group- wise thresholds at the medians of the group-specific probabilistic predictor scores. These thresholds are overly restrictive, as the set of operating characteristics attainable from label flipping may not include the optimal operating point (see 5.11
4.4 MULTIPLE PROTECTED ATTRIBUTES & MULTIPLE CLASSES
Our method directly supports multiple protected attributes and can also be generalized to handle multiple classes, following common definitions of multiclass group fairness that generalize the bi- nary class setting (Alghamdi et al. 2022. Xian & Zhao 2024 see, e.g..); see AA.333 for details.
5 EXPERIMENTAL RESULTS
We evaluate our method on standard empirical datasets, aiming to simultaneously satisfy demo- graphic parity (DP); equality of opportunityTPR parity (EOpp), see Hardt et al. (2016); predictive equality/PPR parity (PE4), see [Corbett-Davies et al. (011)): predictive parity (PP), see Choulde- chova 2017]; and possibly false omission rate parity (FOR-parity), see Barocas et al. 2023) while maximizing accuracy. Enforcing both 0F0pp and ōpz, approximate fairness is equivalent to enforcing max (Epppp )PEq} app-oxipoe fairness for equalized odds (EO), see Hardt et al. (0116).
Due to space constraints, we defer full implementation details, training hyperparameters, and ex- baseline settings the appendix $A.5 We use the COMPAS (Larson & Angwin] 2016). Lawschool (Wightman] 1998 Fabris et al. 2022). BiasBi (De-Arteaga et 20,11 Raviogel al. 2020), and ACSIncome (Ding et al. al.| (021) datasets, with TRAIN/PSST/EEST- 30//SST=30///////
split: TRAIN fits s (using three-layer neural net), and POST fits all procepsrcessoos. We report accuracy and five fairness metries (DP, EOpp. PEq, PP, FOR- parity,,,, aggregating mean results over 50 random seeds, along with standard deviations.
Baselines We compare with two post-processing methods that seek to simultaneously control LF fairness constraints (META (Celis et al., (019) and MFOpt (Hsu et al. (002)), and one state-of- the-art post-processing method that controls for linear fairness constraints (LPP, (Xian Zhao 2024 In addition, record the performance of the unconstrained probabilistie classifier
"Although we focused on fairness constraints expressible as pairwise differences in LF/L functionals, our procedure for constructing classifiers provides recipes match any given target operating characteristics that li the convex hull the empirical ROC curve of base probabilistic predictor s. subject to minimizing the expected number interventions (Algorithm (5).
'The first three linear constraints, while the latter
LF constraints (see
We omit comparisons with popular in nn-proceesing algorithms (e.g.. Agarwal et al. 2018 Zhang et al.
2018b) since Xian & Zhao (2024) demonstrate their method compares favorably against state-of oh-the-art in- processing algorithms; and, in-rrocessigg methods generally do not support controlling for the
constraints consider here.
8

---

Published as a conference paper at ICLR 2026
Table 2: Performance on the for (A) COMPAS ([Al=2) and (B) ACSIncome (-A|=5). The disparities
oee, 020p: Opgy ōpp are controlled level 0.05 whenever they are active. Interv. the empirical intervention rate on the test set (see Definition A.3 Cells in green indicate that the faimesss constraint is satisfied within two standard deviations at the nominal level, whereas cells in red indicate violation. Entries in the Oracle rows shaded in lighter colors denote that they not practically feasible baselines.
COMPAS (1.4)
Method
EOpp
PEg
FOR
Interv.
Baseline
0.68 0.01
0.28
0.05
0.27
0.05
0.19
0.05
0.07 + 0.04
= 0.02
+
Oracle
0.62 1 0.02
0.04
1 0.01
0.03
1'0.22
0.05
1 10000
0.05 1 0.00
0.16 Σ 0.02
NIA
ROCF-LF (ours)
0.61 0.02
0.05
0.03
0.03
0.03
0.05
0.03
0.07 + 0.04
0.15 = 0.02
0.06 +
MFOOi
0.63 0.01
0.26
1.04
0.35
0.21
10.0
0.08
1.08'E 0.04
0.07 = 0.003
0.13'' 0.02
META
0.50 0.02
0.05
0.17
0.05
0.16
0.04
0.18
0.06 +: 0.19
0.15 = 0.05
0.00 + 0.00
LPP-DP
0.67 + 0.01
0.06
_ 0.03
0.04
4.00
0.03
0000
0.13 0.03
0.09
= 0.03
0.00 I 0.00
EO
0.67 0.01
0.10
0.04
0.09 0.04
0.04
0.03
0.14 1 0.03
0.08
0.03
0.00 1 0.00
(B) ACSIncome
(|A|=5)
Method
Acc
DP
EOpp
PFg
PP
FOR
Intery.
Baseline
0.79 0.00
0.25
0.01
0.02
0.02
::
1:
Oracle
0.69 1: 0.01
0.05
1 0.00
0.05 + 0.00
0.03 + 0.01
0.05 + 0.00
0.23 :: 0.01
N/A
ROCF-LF (ours)
0.69 0.01
0.05
1:
1
LPP DP
0.78 1. 0.00
0.06
0.01
0.07
1 0.01
0.09
1 0.01
0.35 1 0.01
0.15 1. 0.01
0.00 1. 0.00
LPP-EO
0.78 0.00
0.12 0.01
0.06
0.02
0.06 0.01
+:
0.14 -
+
(Raseline) and an infeasible oracle post-processor with operating characteristics returned by RegionSearch- FG (Algorithm) 3) using the true labels of the TEST set as an upper bound.
Results. We present the primary results here in the main text and leave additional experimental results to the appendix (see Tables and 6 in $A.6. and $A.6.3)
5.1 APPROXIMATE FAIRNESS FOR DP, EOPP, PEQ, AND PP
We impose four constraints (DP, EOpp. PEq, and PP) simultaneously, controlling for 8-approximate fairness at either the level 6,=0.05 (for COMPAS and ACS (CCToo) or 6;=0.02 (for Lawschool) across all Results are shown in Tables 2 and S where our method ROCF-LE LF refers to the Habe1Flipping minimimum intervention algorithm (cf. Algorithm
Results. First, we observe that our method controls all four disparity metrics. Among the baselines, only META achieves this on the COMPA4 AS dataset, and no other baseline achieves it on the other datasets. However, META exhibits much larger accuracy drop than our method. The reason for the performance gap might be that they aim to optimize in the space of classifiers, whereas our method achieves an advantage by working directly with the operating characteristics. Moreover, on both examples, we observe that our method has accuracy close to the oracle.
Inevitable trade-offs. Since even the oracle method exhibits an accuracy drop, this suggests that faimess/acccracy trade-offss when imposing all four constraints might be unavoidable in our exam- ples. This is in contrast with simpler settings where we only impose fewer constraints Xian & Zhao 2024) Celis et al. 2019 Baumann et al. (2022).
Interventions. We also observe that the number of interventions is small, around 6% for COMPAS, 1% for Lawschool, 0.5% for BiasBios, and 3% for ACSIncome for our method.
Scalability. Our method scales well to the much larger AnSIncome dataset, demonstrating both practical computational runtimes (see {A.6.2) and attaining the nominal disparity levels across all fairness constraints. The latter is to be expected, since our method can better approximate the population level feasibility region and the realizable ROC region R, (s) (ef. equation 6) with better trained probabilistic predictor and a larger post-processing set.
5.2 TWO LINEAR FRACTIONAL CONSTRAINTS: ADDING FALSE OMISSTON RATE PARITY
False omission rate parity. We consider satisfying an additional linear fractional constraint, the false omission rate parity (FORtparity), along with two linear constraints. For these experiments,

---

Published as a conference paper at ICLR 2026
Table 3: Performance on the test for (A) Lawschool ([Al=2) and (B) ACSIncome ([A|=5). The same protocol as in Table 2 0.10 (for ACSIncome).
used, except duopps Ayy and 6POR are controlled at either level 0.03 (for Lawschool) or
Lawschool ([A[==2)
Method
Acc
DP
EOpp
PFq
PP
FOR
Intery.
Buseline
0.79 1: 0.00
0.07 1: 0.01
0.11 1: 0.02
0.03 1: 0.01
0.04 1: 0.02
0.04 1: 0.00
0.00 1 0,00
Oracle
0.16 4:
0.02 0.01
::
N/A
ROCE-LF (ours)
0.58 +: 0.04
0.15 1 0.02
0.03 1 0.01
0.16 1: 0.03
0.02 1: 0.01
0.03 1: 0.01
0.01 1 0.01
PPPpPpppp
(B) ACSIncome (|A|=5)
Method
Acc
DP
EOpp
PEg
PP
FOR
Interv.
Baseline
0.78 + 0.01
0.24 + 0.01
0.25 + 0.03
0.09 + 0.02
0:23 + 0.03
0.08 + 0.01
0.00 + 0.00
Oracle
0.57 1: 0.00
0:48 1'0005
0.10 0.01
0.57
0.08
0.10 1 0.00
0.10 1 0.000
ROCF-LF (ours)
0.56
0.49
0.11
0.59
0.11
0.05 + 0.01
EPpp
0.79 1 0.000"
"oT3"1 1'001
"0.TT" 0:61
0.06 0.01
633 T0.00
6112 1 T'00
0.30 1.00000
increase the tolerance level to either 8-0.10 (for COMPAS and ACSIncome), 5-0.05 (for BiasBios), 8=00.3 (for Lawschool) and exclude PEq and either DP EOpp, since often find that the empirical feasibility region fss, Prsss) (see Remark A.1 empty when con- trolling at a smaller 5 level (cf.$ 5.1 Indeed, additionally satisfying a low level of FOR-parity substantively nontrivial: Majumder et al. (2023) show through extensive empirical studies that fairness metrics cluster differently, with FOR-parit separating from DP/EO and PP.
Methods compared. Existing baselines do explicitly support this configuration
of the box:
Hsu et al. (002)) only handles 8-approximate DP, EO, and PP, and, while Celis et al. (019) can, in principle, encode any combination of LF/L fairness constraints, their released code does not implement FOR-parity (Keswani et al. 2019). Consequently, we report results only for our method (ROCF-LF), the optimal operating point (Oracle), e), and the linear post-pnn post-processing method of Xian & Zhao (2024) that only controls for demographic parity equality of opportunity (LPP-DP/ /BOpp). The latter is included merely as a strong recent baseline from the literature, and emphasize that it does not aim to ensure predictive parity and false omission rate parity.
Results. Table reports results for the Lawschool with binary protected attributes and AC- SINCOME dataset with multiple protected attributes. As we can see, our method controls all three fairness constraints at the desired level, while achieving a near-oracle accuracy. This reinforces the effectiveness of our method. In contrast, the FOR coR-tarity; which is reasonable as it does not aim do so. Moreover, we observe a substan- tial eccuracy-fairnes. tradeoff of 21 22-22 percent across both datasets. This suggests that satisfying fairness across multiple protected attributes for multiple LF constraints difficult (Table
method does not control PP and/or
Sensitivity Analysis. We also conduct sensitivity analysis on the granularity of the grid search used for the dinear-fractions constraints (cf. (cf. $4.2). We observe that using a grid size of 25 or 50 achieves near-oracle level performance and often attains the nominal disparity levels, while exhibit- ing a nearly 20 fold decrease in computational time compared to the full grid search with 100 points; for space considerations, full results are deferred to $A.6.3
6 DISCUSSION
In this paper, we proposed an approach for fair classification with linear fractional approximate fairness constraints, which relied on reformulating the goal in the space of the operating character- isties of the classifiers and then designing fairness interventions at that level. We observed that our method compares favorably existing baselines in experiments. An important direction for future work is that the proposed randomization approaches may randomize any individuals, but it could be of interest to design intervention policies that restrict randomization to only a subpopulation.
10

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY STATEMENT
All experimental details, including dataset information, preprocessing, and evaluation protocols, provided in Section 5 [Appendix A.5] and Appendix A.6 An anonymous GitHub repository, containing the implementation of our ROCF method, baseline methods, and code to reproduce all experiments, is available this repository] All theoretical results and assumptions are stated in Sections 3 | with complete proofs provided in Appeeddix A.4.
ETHICS STATEMENT
Our work falls in the broad area of ethical machine learning. However, our contribution is purely technical and does not make any specific recommendations that might have ethical implications. Instead, our contribution is to develop powerful algorithms that enable practitioners to achieve al- gorithmic fairness contexts that were not possible due technical constraints in the past; by efficiently incorporating multiple group fairness constraints that were previously hard to simultane- ously satisfy.
REFERENCES
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. A reduc- tions approach fair classification. In International conference machine learning, pp. 60-69. PMLR, 2018.
Wael Alghamdi, Hsiang Hsu, Haewon Jeong, Hao Wang, Peter Michalak, Shahab Asoodeh, and Flavio Calmon. Beyond adult and compas: Fair multi-class prediction via information projection. Advances in Neural Information Processing Systems, 13:38747-38700 2022.
Alex M Andrew. Another efficient algorithm for convex hulls in two dimensions. Information processing letters, 95):216-- 1979.
Solon Barocas and Andrew D. Selbst. Big data's disparate impact. California Law Review, 104(3): 671-732, 2016.
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and machine learning: Limitations and opportunities. MIT press, 2023.
Peter L Bartlett and Marten H Wegkamp. Classification with reject option using hinge loss. Journal of Machine Learning Research, 98), 2008
Joachim Baumann, Anikó Hannák, and Christoph Heitz. Enforcing group faimess in algorithmic decision making: Utility maximization under sufficiency. In Proceedings of the 2022 ACM Con- ference on Fairness, Accountability, and Transparency, pp. 2315-2326, 2022.
Andrew Bell, Lucius Bynum, Nazarii Drushchak, Tetiana Zakharchenko, Lucas Rosenblatt, and Julia Stoyanovich. The possibility of fairness: Revisiting the impossibility theorem in practice. In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency. pp- 400-422, 2023.
J Frédéric Bonnans and Alexander Shapiro. Springer Science & Business Media, 2013.
Perturbation analysis of optimization problems.
Ludwig Bothmann, Susanne Dandl, and Michael Schomaker. Causal fair machine learning via rank- preserving interventional distributions. arXiv preprint arXiv:2307.12797, 2023.
Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. 2009 IEEE International Conference on Data Mining Workshops, pp. 13-18.
IEEE, 2009.
L Elisa Celis, Lingxiao Huang. Vijay Keswani, and Nisheeth K. Vishnoi. Classification with faireess constraints: A meta-an algorithm with provable guarantees. In Proceedings of the conference on fairness, accountability, and transparency, pp. 319-328, 2019.

---

Published as a conference paper at ICLR 2026
Jaewoong Cho, Gyeongjo Hwang, and Changho Suh. A fair classifier using kernel density estima- tion. Advances in neural information processing systems, 33:15088-1509) 2020.
Edwin KP Chong, Wu-Sheng Lu, and Stanislaw H Zak. An Introduction to Optimization: With Applications to Machine Learning. John Wiley & Sons, 2023.
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5(2):153-163, 2017.
Alexandra Chouldechova and Aaron Roth. A snapshot of the frontiers of faimess in machine learn- ing. Commun, ACM, 63(5):82-89, April 2020.
Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on information theory, 16(1):41 2003.
Sam Corbett- Corbett-Davies, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic deci- sion making and the cost of fairess.. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 797-806. Association for Computing Machinery, 2017.
Maria De-Arteaga, Alexey Romanov, Hanna Wallach, Jennifer Chayes, Christian Borgs, Alexandra Chouldechova, Sahin Geyik, Krishnaram Kenthapadi, and Adam Tauman Kalai. Bias in bios: A case study of semantic representation bias in high-stakes setting. In proceedings of the Confer- ence on Fairness, Accountubility, and Transparency, pp. 120-128, 2019.
MaryBeth Defrance and Tijl De Bie. Maximal combinations faimess definitions. Journal of Artificial Intelligence Research, 82:1495-155 1579, 2025.
Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. Qlora: Efficient finetuning of quantized llms. Advances in neural information processing systems, 36: 10088-10115,, 2023.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. Proceedings of NAACI.HILT, 2019.
William Dieterich, Christina Mendoza, and Tim Brennan. Compas risk scales: Demon- strating accuracy equity and predictive parity performance of the compas risk scales in broward county. Technical report, Northpointe Inc., Research Department, July 2016. URL https://go volarisqrouppppoooooooooooo com/ rs/ 430 411143300---0--000 / images/ ProPubli callca_Cooo hatcccaa__oeearrraaaaaaa
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. Advances in neural information processing systems, 34:6478-644 6490, 2021.
Jacques Andre Dupreez and Olivia McDermott. The use of predetermined change control plans to enable the release of new versions of software as medical device. Expert Review of Medical Devices, 2263):261-275, 2025.
Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pp. 642-669, 1956.
Alessandro Fabris, Stefano Messina, Gianmaria Silvello, and Gian Antonio Susto. Algorithmic fairness datasets: the story far. Data Mining and Knowledge Discovery, 366))2207--252, 2022.
Andreas Fuster, Paul Goldsmith-Pinkhann Tarun Ramadorai, and Ansgar Walther. Predictably un- equal? the effects of machine learning on credit markets. The Journal of Finance, 77(1):5 2022.
Yonatan Geifman and Ran Yaniv.. Selective classification for deep neural networks. Advances in neural information processing systems, 30, 2017.
Piet Groeneboom. Grenander functionals and cauchy's 's formula. Scandinavian Journal of Statistics, 48(1):275-2944 2021.
12

---

Published as a conference paper at ICLR 2026
Lara Groves, Jacob Metcalf, Alayna Kennedy, Briana Vecchione, and Andrew Strait. Auditing work: exploring the new york city algorithmic bias audit regime. In Proceedings of the 2024 ACM Conference Fairness, Accountability, and Transparency, pp. 1107-1120, 2024.
Faisal Hamman and Sanghamitra Dutta. A unified view of group fairness tradeoff's using partial in- formation decomposition. In 2024 IEEE International Symposium on Information Theory (ISIT), pp. 219-219. IEEE, 2024.
Dutch Hansen, Siddartha Devic, Preetum Nakkiran, and Vatsal Sharan. When is multicalibration post-processing necessary? Advances in Neural Information Processing Systems, 37:38383- 38455, 2024.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
Hoda Heidari, Vedant Nanda, and Krishna Gummadi. On the long-term impact of algorithmic decision policies: Effort unfairness and feature segregation through social learning. arXiv preprint arXiv:1903.01209 2019.
Brian Hsu, Rahul Mazumder, Preetam Nandy, and Kinjal Basu. Pushing the limits of fairness impossibility: Who's the fairest of them all? Advances in Neural Information Processing Systems, 35:32749-32766 2022.
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al. Lora: Low-rank adaptation of large language models. ICLR, 12):3, 2022.
Krishna Ravali Jammalamadaka and Srikanth Itapu. Responsible ai automated credit scoring systems. Al and Ethics, 3(2):485-495, 2023.
Vijay Keswani, L. Elisa Celis, Lingxiao Huang, and Nisheeth K. Vishnoi. Fairclas- sification: Fair classification algorithms. https: /ttps://gitte htt//ggttttt thub. com/vi jaykeswann/ FairClassification 2019. GitHub repository; accessed 2025-09-11.
Jon Kleinberg. Inherent trade-offs in algorithmic fairness. In Abstracts of the 2018 ACM Interna- lional Conference on Measurement and Modeling of Computer Systems, pp. 40-40, 2018
Jeff Larson and Julia Angwin.
Technical
response to northpointe. ProP-
ublica, July 2016.
URL
technical wwwpaaaaaaeeeeeeeeeeeeeeeeeeeeee
nort northpointe
Charlotte Leininger, Simon Rittel, and Ludwig Bothmann. Overcoming fairness trade-offs via pre- processing: A causal perspective. arXiv preprint arXiv:2501.147100 2025.
Shaina Mackin, Vincent J Major, Rumi Chunara, and Remle Newton-Dame Post-processing meth- ods for mitigating algorithmic bias in healthcare classification models: An extended umbrella review. BMC Digital Health, 3(1):26, 2025.
Suvodeep Majumder, Joymallya Chakraborty, Gina R Bai, Kathryn T Stolee, and Tim Menzies. Fair enough: Searching for sufficient measures of fairness. ACM Transactions on Software Engineer- ing and Methodology, 32(6):1-2) 2023.
Pascal Massart. The tight constant in the dvoretzky-kiefer-woffovii inequality. The annals of Probability, pp. 1269-1283, 1990.
Ziad Obermeyer, Brian Powers, Christine Vogeli, and Sendhil Mullainathan. Dissecting racial bias in an algorithm used to manage the health of populations. Science, 366(6464))447-453, 2019.
Joseph o' RRurree Computational geometry in C. Cambridge university press, 1998.
Drago Plečko, Nicolas Bennett, and Nicolai Meinshausen. fairadapt: Causal reasoning for fair data preprocessing. Journal of Statistical Software, 110:1-35, 2024.
Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. On fairness and calibration. Advances in neural information processing systems, 30, 2017.
13

---

Published as a conference paper at ICLR 2026
Peter Quell, Anthony Graham Bellotti, Joseph L Breeden, and Javier Calvo Martin. Machine learn- ing and model risk management. Model Risk Manager's International Association org), 2021.
Manish Raghavan, Solon Barocas, Jon Kleinberg, and Karen Levy. Mitigating bias in algorithmic hiring: Evaluating claims and practices. In Proceedings of the 2020 conference on fairness, accountabillit, and transparency, pp. 469 481, 2020.
Shauli Ravfogel, Yanai Elazar, Hila Gonen, Michael Twiton, and Yoav Goldberg. Null it out: Guard- ing protected attributes by iterative nullspace projection. arXiv preprint w001v:2004.07660 2020.
Daniele Regoli, Alessandro Castelnovo, Nicole Inverardi, Gabriele Nanino, and Ilaria Penco. Fair enough? map of the current limitations of the requirements to have fair algorithms. arXiv preprint arXiv:2311. 12435, 2023.
Teresa Salazar, Miriam Seoane Santos, Helder Araújo, and Pedro Henriques Abreu. FAWOS: Fairness-aware oversampling algorithm based on distributions of sensitive attributes. IEEE Ac- cess, 9:8 9:81370-81379, 2021.
Sahil Verma and Julia Rubin. Fairness definitions explained. In Proceedings of the international workshop software faimnes,, pp. 1-7, 2018.
Avyukta Manjunatha Vummintala, Shantanu Das, and Sujit Gujar. Froc: Building fair roc from trained classifier. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 26373 26381, 2025.
Luping Wang, Sheng Chen, Linnan Jiang, Shu Pan, Runze Cai, Sen Yang, and Fei Yang. Parameter- efficient fine-tuning in large language models: survey of methodologies. Artificial Intelligence Review, 5822)227, 2025.
Hilde Weerts, Miroslav Dudik, Richard Edgar, Adrin Jalali, Roman Lutz, and Michael Madaio. Fair- learn: Assessing and improving fairness of Al systems. Journal of Machine Learning Research, 24(257):1-8, 2023.
Linda F. Wightman. Lsac national longitudinal bar passage study. LSAC Research Report Series LSAC-98-01, Law School Admission Council, 1998.
Ruicheng Xian and Han Zhao. A unified post-pron post-processing framework for group fairness in classifi- cation. arXiv preprint arXiv:2405. 240500050 2024.
Meike Zehlike, Alex Loosley, Häkan Jonsson, Emil Wiedemann, and Philipp Hacker. Beyond in- compatibility: Trade-offs between mutually exclusive fairness criteria in machine learning and law. Artificial Intelligence, 340: 104280, 2025.
Xianli Zeng, Guang Cheng, and Edgar Dobriban. Bayes-optimal fair classification with linear dis- parity constraints via pre-, in-, and post-processing. arXiv preprint arXiv:2402.028117 2024.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adver- sarial learning. In Proceedings of the 2018 AAAI/ACM Conference AI, Ethics, and Society, pp.
335-340, Association for Computing Machinery, 2018a.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adver- sarial learning, In Proceedings of the 2018 AAAI/ACM Conference AI, Ethics, and Society, pp. 335-340, 2018b.
Yi Zhang and Jitao Sang. Towards accuracy-fairness paradox: Adversarial example- based data augmentation for visual debiasing. In Proceedings of the 28th ACM International Conference on Multimedia, pp. 3346-435. 2020.
A APPENDIX
Usage of LLMs. Open-Al's ChatGPT 5-thinking model helped with the code implementation of the algorithm COCF-LE MF MFOpt, and META, and with viewing summarizing the raw result files; was also used to help format equations and tables during the writing process.
14

---

Published as a conference paper at ICLR 2026
A.1 ADDITIONAL RELATED WORK
Recent work by Zehlike et al. (2225) interpolates only between accuracy equality, false negative and false positive rate parity, leveraging optimal transport. Theoretical work by Hamman & Dutta (2024) studies the tradeoff between demographic parity, equalized odds, and predictive parity using partial information decomposition by fixing one of the fairness metrics and exploring the tradeoffs between the other two, without explicitly designing classifiers. Intervening on ROC curves has also been used ensure forms fairness different from the ones that we consider in this paper (Vummintala et al. 2025).
Beyond our focus on post-processing methods, there are also pre- and in- processinn methods that seek to modify the training process or dataset. Some of these aim simultaneously control broad set of disparity measures by removing the dependence the protected attribute on (X, Y) (Zhang
ct al.
2018a
Bothmann et al. 2023 Plečko et al. 2024 Leininger et al. 2025
Post-processing is attractive when retraining is impractical or constrained by governance, cost, or lonency-conditios that have become increasingly common with generative AI (Hu et al. 2022 Dettmers et al., 2023) Wang et al. 2025) and with deployed models in regulated domains (e.g..
eredit, hiring, healthcare; Quell al. (2021); Groves et al. (2024); Dupreez & McDermott (2025
A.2 ADDITIONAL METHODOLOGICAL DETAILS
A.2.1 EMPIRICAL REGION SEARCH OVER ROC-HIUL SUPPORTS
We instantiate the empirical analog of equation 7 by searching over linear fractional centroids for the best post-processing operating points from each group's 's empirical ROC convex hull. More formally, let the plug-in estimates of the operating characteristics in equation] D on the postprocessing set Dpost be
N 1 (a; a = 1),
N
Ra.1
na,0
1 (a: = =,,y; = =0), na Ba,1 + 1a
1=1
t=1
TPR, (f)
(aa 0, 1) 1 1(f(I;;;; 1),
Ra,1 i=1
N
FPR
(a: a, = 0) =0
([f az) = =)
Ba.0
FN).()) = TPR. (/),
-
= 1 - -P-. (J).
--FPR.. (16)
Then, for each E A, we form the group-wise empirical ROC {(TPR, ()) probabilistic predictor scores s(2;, a;) and labels on the post- post-processing set by setting
()) )
FPR. se..).)) from the
((و (I, a) == (rank, (s(z, a)) S j),
j [na]
in equation 16 where rank, (s(x, a)) := 1+
(a, = a, s(z, ai) > s(x, a)). We then retain
the upper convex hull vertices H. {(TPR (3) FPR lies for some index set S, C [ma]] (e.g.- using Andrew's monotone chain algorithm (Andrew) 1979 Rourke 1998),, and construct lifted operating characteristic vectors p(()) = (TPR, a FPR, 1)T from Rl. The set of all lifted operating characteristics vectors is termed the empirical ROC (convex) hull (s)s..
Since any operating characteristic in (s) is as linear combination of the convex hull support points, we enforce post-pros post-processing by introducing convex weights {>a.s Iyes, that satisfy
Σ JES.
Aas 1,
Aa.s 2 O,
Pa = Σ Ao.s
Ex.ss -6())
(17)
JES.
"If scores are tied, then ties can be broken by a deterministic rule (e.g., via lexicographic ordering) so that exactly j group-a points satisfy f() (2,, a.) 1.
15

---

Published as a conference paper at ICLR 2026
where Pa are the (lifted) operating points (TPR,, FPR.: 1)T
Finally, we form empirical plug-in coefficients for Ta: uk Us.a (c.g., replace Ta by R.). The result- ing optimization problem and full procedure for finding the optimal operating points is presented in Algorithm 2 (RegienSearch)
Remark A.1. The region of operating points specified by the constraints of the inner LP (i.e., the linear fractional/linear faimess constraints and post-processing constraint) in Algorithm 2 is the empirical analog of the centroid-specific population-level feasibility region 3 s, 5) discussed in
$ We call the union of this centroid specific region over the set of admissible centroids (cf. $4.2) the empirical feasibility region 3(s. 5: poss).
Remark A.2. Each inner problem is modest-sized LP with EaeA + [Kt] decision variables. The number of linear constraints is often smaller: |A|| + 1 for the simplex and post-processing per group, /rr for the linear centroid bands, [rrF for the LF bands, and [A||[Cr.Fl for the denominator checks.
Since the hull support sizes |Sa] are typically small (see c.g., Groeneboom 2021). each LP solve is fast in practice, so that the overall runtime is dominated by the low-dimensional outer search over linear fractional centroids. We report computational runtimes in $A.6.2
A feasibility guard. To ensure that produce classifier even when RegionSearch does not yield a feasible operating point, one can wrap expansion policies around Regi iriinnnSarh proce- dure of Algorithm 2 that increase the nominal disparity levels until feasible point is found. Here, we introduce two simple expansion policies that are intuitive and that we find have worked well in practice.
a-expansion policy: On a high level, if Algorithm 2 is infeasible with the initial, user-specified tolerances, we re-solve Algorithm with fairness tolerances that uniformly relaxed by an expan- sion factor of a. By performing bisection search on an appropriately designed interval for a, our RegionSearch guaranteed produce feasible operating point, from which we can construct a classifier (per $4.3).
More formally, given user-specified tolerances (6 keKy UKGLE define ō((x) == {adu (akK] for a 2 Let the unconstrained/baslline per-group operating points be, for A. Ji E arg minjes. (Ta. and phase
م!ام)_ These are the solution of RegionSearch with no
fairness constraints 12
The corresponding baseline group performance functions are then
(ū Pa Sbase'
base gE,a
( phass)
:=
base Tka
(whenever (ūk,a, Pa
phasey EK),
(ux. Ph Phase
with baseline disparity measures A, == max, glase mina base, Ae == max, k,a
base mina base k,a
Now, note that we can recover the baseline operating points Ph with M(ani), where ani the maximum ratio between the baseline disparity measures and the nominal disparity levels. That is, upper bound for the expansion parameter is Ohi max maxieKiLKLe A
Thase by re-solving RegionSearch
By design, (Phase] JaEA is feasible at a Ohi and feasibility is monotone in a: if the inner LP of RegionSSerrch feasible at a, it remains feasible for any a' 2 a. We therefore bisect on
E [Mi, qni) [1, mni) by setting, at each step, <- (ato + 0mi)/2, re-solving Algorithm 2 with 5(a), and updating the search interval appropriately. For completeness, the full wrapper algorithm is provided in Algorithm (RegionSeazee FG).
This feasibility guard produces classifier while minimally relaxing the user-specified tolerances. In our experiments. it rarely activates; when it does, the expansion parameter is relatively small (c.g., a== 1.04 and see $A.6.Ip.
A ---crementall policy. While the a-expansion policy uniformly scales all fairness tolerances, it can be useful practice to selectively relax only a subset of constraints. To support this use case, we
The objective is linear in the operating characteristics, optimum Pa
plase occurs hull vertex.
16

---

Published as a conference paper at ICLR 2026
introduce an alternative expansion policy that enlarges the nominal disparities for chosen pair of constraints until feasibility is restored.
For example, suppose the user wishes to preserve the nominal disparity levels for all constraints except two: a linear constraint constraint j KLF (e.g., predictive Parity). Let their user-specifted tolerances be dg and 8j. If RegionSearch is infeasible under these nominal tolerances, we generate a sequence of incre- mentally relaxed tolerances
Kr (c.g., equality of opportunity) and a lincar-fractiona
((m)) = 02 m Tjk-
6fm² : 6y m T/5
0, 1,
where 7 0 and 1 0 are user-selected step sizes that govern how quickly each constraint relaxed. We allow a and ny to differ (c.g., 7k = le-2 and f = 5e-3), thereby encoding cymmmettrcchon-unffooo preferences such relaxing equality of opportunity twice as quickly as predictive parity.
At iteration m, we re-solve Algorithm 2 using the updated tolerances (o(m) 5(m)) while keeping all other fairness constraints fixed their original user-specified levels. Feasibility is monotone in once Algorithm@beconee constraints are only being relaxed. The procedure therefore terminates at the smallest m for which feasible operating point is found.
feasible for some m., it remains feasible for all m > m because the
We present preliminary results of this expansion policy in $A.6.4
A.3 ALGORITIMS
In this section, provide the pseudo-code for several of our proposed algorithms. We summarize each the algorithms here for clarity.
Top level procedure that first finds target operating char- acteristics using a pre-trained classifier &, post-processing set D pest. and user-specified tol- erances 8' for LF/F fairness constraints (Algorithm 3). Then, it constructs classifier to achieve those operating characteristics with the option of imposing additional desiderata (e.g., minimizing expected number of interventions; see (arrrthhmm[[[ad[33
ROCF-Piper pillineee (Algorithm 1
Regi orgionnSearch (Algorithm 2 Empirical instantiation of the population level optimal fair classification problem (cf. equation 7 searches over each group's empirical ROC-hull support to select target operating characteristics. Handles LF constraints via small outer search over admissible centroids (cf. $A.5.I).
Regi onSearch-FG (Algorithm 3): Wraps feasibility guard around Reg onSearch that guarantees feasibility by loosening the tolerance levels ă when the initial search is infeasible.
Construct Cunstruut Classifier (Algorithm 4) Constructs a randomized post-processor with target operating characteristics, subject to additional desiderata.
MinIntervent (Algorithm 5): Specifie instantiation of Algorithm Given target operating characteristics, this algorithm produces mixed-GWTR (cf. Definition 3.2) with added randomization, to achieve the target characteristics while minimizing the expected intervention rate (cf. Definition A.3). Implements the LABELFLIPPING) randomization procedure discussed in the text.
A.3.1 INTERVENTIONS
Using the output of Algorithm we seek to construct classifiers that achieve target operating char- acteristics. Since there are many classifiers that achieve any operating characteristic, the prac- titioner can impose additional desiderata such as minimizing the expected number interventions (see Definition A.3 below). We provide one particular construction in this work, though we leave the full question of optimally designing these particular classifiers as future work, since this requires answering broader questions
sociotechnical level.
Concretely, we provide a modular meto-algorithm that accepts any constructed classifier (Algorithm For the additional desideratum of minimizing the expected number of interventions, we provide
17

---

Published as a conference paper at ICLR 2026
Algorithm (End-to-end ROCF pipeline)
Require:
Training set Drrain: postprocessing set D post, test set Dresti groups A: tolerances {6x}: constraint indices KL, with Kr. LI LLF = [K]; centroid intervals (ek) margins
{Ex > =0}.
1: Pre-train predictor. Fit probabilistic predictor s: X' x A + [0, on Derain.
2: Postprocess ROC curve. On Doost: compute probabilistic predictor scores s(z,, a;) and trieve labels For each A:: form the empirical ROC curve and keep the upper convex (i) - (1)
hull supports Ha; build lifted points o!5) (TPR FPR .1). Form plug-in coefficients Ta: Uk.a: Fk
3: Search region (Algorithm Provide {Ma), (Fl"), }. iaa, ūk tk (6x), KL, KLF, 1Qx), {Ex}, ] to Algorithm 3 obtain target operating points {Pa).
4: Construct classifier (Algorithm 4). Using ( and construct a classifier f that attains Po. for each group (optionally with additional desiderata).
5: Evaluate. On Drest. evaluate I to report loss and fairness metrics max Gkaa
GR. (f) for & [K].
6: Return {.at, f, and test metrics.
Algorithm RegionSearch
Require: Groups A; hull supports {Ha);: plug-in Ta. úg.a, Tx.oi tolerances {ō&}: index sets KL, KLF; centroid intervals {Ox (Qkkeekri margins {Ex 0}.
best to0, Topt < None, {da,} + None, {Pa} t None.
2: Construct Pa (TPR (1)
o FPR o 1)T from hull supports H.. = [(TPRR FPR Dies.
()
(1)
(
3: for q= (gk) > IIkEKi 2t do
e.g., coarse grid
4: Inner LP: minçAo,, 1 MER, EaEA (aa pa)
Σ Aa. =1, 20 jESa
20
EjESs E
s.t.
Va E A
pa Σ
Xas Nag. -053
jES.
6z < (ūt Pa)) 91 bc
Va A,E KL
2
(Ukaar Pa) (9h + )
(ūr.as (lsassa) 50
Va E A
Uk 5y (Tk,a, Po) (ikaa Pa) 50
(TR.a Pa) Ex.
E A
5: Let 3(4) be the optimal value and (Na.j), ; (Pa) the optimal variables.
6:
if (b()) < best then best <- e (g)), Topt & T. Aa.s +- Aa.j Pa +- Pa-
7: end if
8: end for
9: Return Return the target operating points faa)
18

---

Published as a conference paper at ICLR 2026
Algorithm htw.s/aaaaccceeeessssiittattaaa (a-uniform expansion policy)
Require: Groups A; hull supports (H.g): plug-in {fa), (ūr,a), {ūr,a) tolerances {6x}; index
sets Kt, KLr; centroid intervals { [Qx ke margins {Er > 0}; bisection tolerance Ta 0. Ensure: Minimal feasible expansion and operating points {Pa)a
Step 0: Instantiate search interval.
1: for each a E A do
2: Ja arg minyes, (a pl))); set poase + a..)
3: end for
(uk,a bbss
4: Compute baseline metrics: base = (ū Plasey > for E KL,
kka
base
(k,,a Plase)
for k KLF
with (Tk,a, Phase) 2
base min base 5: Baseline disparities: A max Fř.a
D max
buse
min
base k.a
6: Minimal per- mer-metric expansions: as min Ae/5e, min
a max ar KEKLF
7: Set bracket: at f 1, Ohi f max 1, max of
EEK2
Step 1: Exit early at nominal tolerances.
8: Run RegionnSeareeeeeeee with ((1) = 5;
9: if feasible then
10: return ā and the returned (pa AEEA
end if
Step 2: Bisection-search
12: while (hni - 0h > To do
a (0% + m/2; set 5(a) = (adx).
14:
Run Regi onSearch with 5(a). if feasible then
16:
+ a cache current solution {Pu Jasd-
else
18:
<- a. end
20:
end while
21: return +- Obi and the cached solution (Pa JaE at Ohi
19

---

Published as a conference paper at ICLR 2026
randomized classifier applied to mixed-GWTK. Labe1Flipping flips the mixed-GWTL labels with outcome-dependenn probabilities. We begin by defining interventions.
Definition A.3 (Interventions). Fix a baseline prot-poocsssor f()) X + {0.
as per equation 5 For any candidate post-processor f, the population intervention rate is
[nt(f: ( = Pr (f(X, A) # f()((,A)) with group-wise intervention rates Int, (J; f(
Pr (S(X, A) + (XX
(X, A) A=a). On dataset D, the expected empirical intervention rute is
(f: f ; D) = D
Σ
Pr Pr(s(r,a) f ( (x,,)),
(z,e.))DD
where the probability taken over any randomization introduced by f and/or f()), The expected number of interventions is [D] Int.
Similarly, dataset D, the empirical intervention rale removes the expectation over the random- ization procedures induced by the post-processors, and is given by
[nt f D) = D
Σ
( (f(2,a))(((zzc)))) (z)
(2,0.))
so that the empirical number of interventions is (D) Int.
The intervention rate simply the misclassification emror when the true labels are provided by the baseline post-processor f()), However, find it helpful to define this quantity separately
Definition A,4 (Minimal intervention). Consider a class FN of post-processors per equation We define the following minimal intervention post-processine objective:
min (J; (()); ; Prost) s.t. Pa( Pa: Va E A,
(18)
JEFN
where Pa (f) are the empirical operating characteristic rates of post- post-processors f E FN on the post- processing set D Ppost (see $A.2.1 1, and Pa (TPR,, FPR,, 1)" are target operating characteristics
(c.g.. the output of Algorithm 3)
A.3.2 FORMULATING THE MININTERVENTION PROBLEM
Given a fixed post-processing set, the expected number of interventions (equation A.3 can be computed in closed form for any mixed-GWTR. In particular, for base post-processor [(),, let st Pr (f(0)=1 A=a) denote the baseline selection rate. Then, the expected empirical in- tervention rates for post-processor on (0) under our randomization procedures are given as follows.
13 Inspired by the label flipping procedure of Hardt et al. (016)) let (P..o,Pa.1) be chosen to match the target rates via equation [3 The expected empirical intervention rate in group a is then
LFF = Int LF (()
( [ (0)) A A=a] = 8 Pa..)) + (1 8 Pa
(19)
On finite split D(a)
post. this can be estimated by
FI.F = Int, [1;; Dpoas) = (0) - Pa.1) + (n. n ( /na-
LF
Taking the base post-processor f())) to be of the form given by equation 11 we can substitute the closed-form expressions for the parameters of the randomization procedure,
Io clarify, we are computing an expectation over the randomization procedure induced by post-processors and/or f(0) a fixed dataset
"We do not claim that interventions are the best desiderata to consider when developing classifiers for real- world deployment. We provide general procedure for constructing classifiers achieve any target operating characteristic realizable by post-processing (see Algorithm 4. and leave the question designing additional ethically and legally sound objectives to practitioners (sec, c.g., (eidari et al. (2019); Regooli ct al. (202))). 15 Developed for the of perfect fairness for equality of opportunity and equalized odds.
20

---

Published as a conference paper at ICLR 2026
FPR, FNR, (0)
(1 -(1-FNR,
-1- (0)
(1-FPR
2.0
2,0
Pa,1 (0)
(et
(1
FNR.
FPR (0) 0.0
FPR.
(1 (1- FNR (0) 0,8
Po.o(0) =
(20)
det(O)
into the closed-form intervention expressions (equation 19 0:
This yields one-dimensional objectives
T = s (1 (o)) + (1 s Po.o(0).
(21)
This suggests enumerating adjacent hull pairs Edges = {(h, h+1} for each group E .A, and minimizing the expected empirical intervention rate T over [0. for each edge, either with a coarse grid or golden-section search (see e.g. Section 7.2 of Chong et al. (2023). We then select the edge and / with the smallest empirical intervention, thereby yielding the minimal-interventionn instantiation of the chosen randomization mechanism while matching the target operating character- istics.
Since not all operating characteristics are attainable by applying a randomization rule to a base post-processor of the form in equation [T] we check for feasibility by ensuring that the solved ran- domization parameters lie in the appropriate set (i.e, (Pa.0, Pa,1) E [0, 1J2 for LabelF lipping). We skip values of they are infeasible.
Snapping to the convex hull boundary. In practice, for stability and computational efficiency, we check whether the target operating characteristic for group lies near or on its group-wise ROC convex hull before conducting the search over adjacent hull pairs.
If the target operating characteristic lies exactly on the boundary of the convex hull, we the intervention rate to zero and skip the edge search procedure for this group. We check closeness of the target point within adaptive tolerance values tols:ttoolo-nna and tolmm=/nn.. -//,., for tunable & where 0a,0 and n are the number of negative and positive labels in group respectively, cf. [A.2.I] the target point within these tolerance levels to the convex hull, we snap to the nearest edge and, again, skip the edge search procedure.
Altogether, this procedure is detailed in Algorithm 5 and provides the final module of the post- processing procedure outlined in our ROCF-pipeling (Algorithm)
Algorithm Construct Classifier (Mininterveation)
Require: probabilistic predictor 8; groups A: postprocessing set 'Doost target rates (Pa from Algorithm 3 a construction subroutine Construct E (LabelFlippingg any admissible).
1: for each a E A do
2: Extract group subset D ((a))
post {(1,, (,))) E DDpost A, a).
3: Call subroutine: (Ea) + Construct (s(;aa) D(a)
post Pa
4: Define sa(.) and ((()() from parameters Sa (e.g., mixing thresholds; label-flip rates).
5: end for
6: Assemble f(x, a) == fx()), f (10 a) = f(() (x)) and compute Pa(l) on Ppost-
7: Report [ni ( ; D post)) and (Int, [ ;
Dpost) }
8: Return f, realized rates (Pa). and intervention statistics.
On the global optimality for minimum interventions. The construction of LLPPLNIIPPING chooses intervention parameters that are optimal conditional on the empirical ROC curve: for a given target operating point, the intervention objective in equation computtes the minimal mixing or flipping probabilities needed to achieve that point. In this sense, this mechanism minimizes the population-level expected number of interventions for their particular functional form.
21

---

Published as a conference paper at ICLR 2026
Algorithm MinnIteervnntion subroutine (Labe1Flipping modality)
Require: probabilistic predictor s; post-processing data post: target operating characteristics
((TPR,, Me:: rate tolerance ç: ID line-search routine G; mode (LF).
Ensure: parameter recipe and bechanism-speciffee parameters {SaJaeA
1: for group a E A do
2: Compute empirical hull. Extract the subpopulation { a, yk) E D ) and use s(ri,a)
to form the empirical ROC and upper convex hull (cf. A.2. and order it:
Food (tr....... (t.. along with (FNR, a FPR ((N)
h=1
here, S..+ is the plug-in estimate for Sa.t = Pr(f A=a) where ( =
1 (s(xz, a) 2 tn 3: best +00.
4: Snap to convex hull boundary. If (TPRa. FPR,) ) lies on boundary of Hard with snap toler- ance (ef. )A.3.2). compute the interpolant godge E [0, 1] and set:
modd==L: use Pa,0=0, (0,=0,P,,111. 1=,1=1 (no flips); objective = 0.
Update Co + (th,as t1+1,a godge, mechanism params), best + 0, and continue to the next group.
5:
for each adjacent pair (h, h+11) in Herd do,
6:
Search over & on this edge via 1D line search G (e.g., grid search, golden-section
search):
Read off
(0) FPR (1 O)FPR (h)
OFPR FNR 2,0 (1 0)ENR (h) + OFNR,
(h+1)
(0)
(b+1)
and the baseline selection rate 8a,+ 111--(1)))) -)38 + 08th+t1).
Compute mechanism parameters.
If mode=LF: compute Po., via equation 20 (Pa.0(0) Pa.1 (0)) E [o, 1]2. Skip if infeasible.
feasibility requires
3. Compute expected number of interventions.
mode=LF: evaluate Σ (cf. equation 21
ZLI best, Ca (th,as t,+1,a mechanism params at 0) and best +- 7LF
7:
end for
8:
Assemble outputs. Return the parameter recipe
C. thti,th (pa,0: Pa,1)
LF
which specifies base post-processor f(()() by equation
1] and the final fa(-) via equation 12
(LF).
9: return (5a)
10: end for
22

---

Published as a conference paper at ICLR 2026
More generally, this mechanism is not necessarily "globally optimal" among all post-processing rules for minimizing the intervention rate (cf. Definition A.33). Establishing such optimality is chal- lenging because the minimal achievable intervention rate depends the geometry of the empirical ROC curve and the baseline post-processor.
In light of this, and, most importantly, practically effective instantiations of the broader design space of all post- processing rules (see, e.g., 4.3 and $5
view these intervention methods interpretable, analytically tractable,
A.3.3 MULTIPLE PROTECTED ATTRIBUTES
In RegionSearch (see Algorithm 2 the inner LP optimizes group-wise operating characteris- ties over the empirical ROC-hull supports, yielding ([A)) linear constraints and O(EneA (Sal) variables. where S is the number of support points in the empirical convex hull of group a. As discussed in Remark A.2 and as observed in our experiments (see runtimes in $4A.6.2,, the set of sup- port points is modestly sized. Given the optimal operating characteristics, our classifier construction decouples across groups, so the randomization hyperparameters of Algorithm can be found in parallel.
A.3.4 MULTIPLE CLASSES
In the multi-class setting, the natural analog of operating characteristics (cf. equation [ is confusion-rate matrix, which records a classifier's joint misclassification probabilities for each pair of true and predicted classes (see equation (2)..
In this section, we extend our method to this setting by introducing a direct intervention mechanism on the confusion-rate matrix, preserving the intuition and theoretical guarantees of the binary class case.
Setup in the multi-class setting. Let X X' be features, A E a discrete protected tribute, and Y E [C] == {1,... [1....,C C} the multiclass label. We are given pre-trained probabilis- tie predictor s X A AC-1, s(x, a) (s1 (ar, a),..., (cc,,,,,(((,,)))) a)) and a post-processing set D Dpost = ((r,, 0i, b=) which is drawn i. f.i.d.from the population.
(possibly randomized) post-processo f
+ [C] induces, for each group a, the confusion-
rate matri 16
Ma(y, 2) := Pr (8 = 2, Y = A=a))
y, M
(22)
Row sums equal the class priors Ta,y = Pr(Y = y A a), E. Ma = Ta,y Let Ua Ey Ma é) = Pr(Y
A = a) denote the predicted- marginals. The misclassification
loss is linear in Mq: Pr( Y a) Ense Ma (M
Post-processing confusion rate region. As in the binary classification setting, restrict to post- processors that only depend on and postt
FN = (x; Dpast) = ()( obtained from s(,aa) and Dpost (possibly randomized)).
(23)
Define the realizable (or post-pracessing) confusion-rate region
R.(s) = (Ma(f) f Fr}.
(24)
Randomizing the post-processors by taking mixture the confusion rate matrices makes R, (s) convex.
Multi-class group fairness for common finaar-ractional and linear constraints.
We provide details for extending our ROC feasibility region approach to the multi-class classification setting for common Emear-fraction and lincar group fairness constraints, and defer extending our method in full generality for future work.
Similar to the works of Baumann et al. (0022); Alghamdi et al. (202)): Xian & Zhao (2024), we present here the definitions of common group fairness metrics for the multi-class setting. Similar
16 the binary classification setting, since the rate-matrix is row-stochasttic, this reduces to the familiar group-wise operating characteristics.
23

---

Published as a conference paper at ICLR 2026
to the binary setting, work in the approximate group-fäiress setting, where seek equalize group performance metrics across protected attributes and/or predicted/true class labels.
Multi-class demographic parity (DP). For each predicted class è, multi-class DP requires Ua,e Pr(Y è A a)=E, My ē) to approximately equal across groups. Introducing centroids d8 E [0, 1] with Ee qa
DP = 1 and imposing the linear bands, this constraint is written as
áDp Ma(v.
4o
ápp
for all a, é.
(25)
Multi-class equalized odds (EO). For each true class multi-class EO equalizes the conditional distribution of Y given Y across groups:
M.(. To.y
Pr(Y è Y y. A a)
EO 4ayy
for all y, E [C].
Since Ta is fixed row-sum, clearing the denominator yields linear bands:
6Eo Ta,y I Ma(y.e)
EO Gely Ka.y I 6nO
Na.y.
Σ
EO 4élp = 1, 4ely E [0,
BO
(26)
Multi-clas sufficiency (predictive parity & false-omission rate parity). For each predicted class è, multi-class sufficiency equalizes the conditional distribution of Y given Y = ê across groups:
Ma(y. é)
Pr(Y y Y é, A a)
Suff Pyle
for all è [C],
with Auf E C-1 For a fixed Suff clearing the denominator yields linear bands:
Saatt Uaf S M)( 2
Suff 4ylé
ua, I
6autt 2
taa
Σ
Suff gih
1, Tyja E [0.
1y9
(27)
Population level optimization in confusion-rate space.
Let r E CxC encode an arbitrary loss criterion, so that (T a. Ma) is the group-wise risk (e.g., for 0-1 misclassification loss, Fa has the diagonal and off the diagonal). The population problem is then
Population-level Optimal Fair Classification via Processo Confusion Rates
min (MalacA
Σ (Ta,,
aed
(28)
Ma Ra(s),
Me 20
M,I= ne.
with DP/EO/Suff. constraints equation 25 equation 27
For fixed (a Jeerey. we obtain an inner linear program in the variables ( [Ma)oE.A and centroids for the Emear-fractions and linear group fairness constraints (cf. equation 25 equation 27). By the
following theorem, searching {ff Jes(C) over II A C-1 recovers the optimum of equation 28
Theorem A.5 (Centroid reduction in the multiclass setting). Define the value function such that (()) is the optimal objective value of the inner linear program in equation 28 obtained by fixing the centroid paramelers q == Jeelor Then, the optimal value of equation 28 is equal to
Suff
min ②
7EQ
where Q := C-1 X.. C-1 Moreover, an optimizer (M)) of the original objective in
Ctimes
equation 28 can be obtained by selecting any minimizer q" E arg mingee. ((ÿ) and then solving the corresponding linear program fixed q
24

---

Published as a conference paper at ICLR 2026
The proof mirrors the binary class setting case, where pairwise disparities are equivalent to the existence a common centroid; fractr-faational bands become linear once the (sufficiency- bbsed)) centroid is fixed; and taking union over centroids recovers the original feasible set.
Sample complexity, Our finite-sample guarantees for the binary-class setting can be directly trans- lated to the multi-class case. Recall, in the binary setting, Theorem 4.2 controls the excess risk and fairness slack terms Remin = min..j Pa.j over group-label counts j E 1). In the multi- class setting, these group-label pairs simply become group-class pairs (a. y) with y [C], so that Mmmin :- millayy Ra,y appears in the bounds. The same Hoeffding- and union-bound argument yields ( (rmin rate, which only incurs mild polynomial dependence on C' due to the C(C-1) confusion-rate entries. Thus, the guarantees remain conditional on the fixed score function 8, re- quire neither calibration nor Bayes-optimality, and preserve the same 1/vīi convergence rate in the binary case.
Empirical level optimization in confusion-rate space.
Similar to the binary class setting, we use post-processing set to generate a collection of confusion- rate matrices that approximates the frontier of the realizable confusion-rate region (cf.equation 24
We then prune to support points and allow mixtures between these points, thereby ensuring that the final optimization has considerably fewer variables without losing any expressivity in the resulting family of randomized confusion-rate matrices.
Building the empirical convex hull of confusion- matrices. Define the group-wis empirical confusion-rate matrix of a post-pracessor f as
Ma Ma(u,C) := na
Σ =Y; y. =))
é a:=a
where n2 = #(i: = aa is the number of post-processing samples in group
We seek to construct a finite support of empirical confusion-rate matrices (Ma) ()) jiss with index sets {SA)aEA whose convex hull
(s = conv (M :j e S.}
approximates the realizable confusion-ratte region R. (s).
This is achieved by instantiating several simple, deterministic rule families G E G that map the learned score vectors s(x, a) A C-1 label in [C] (e.g., one versus rest threshold classifiers (Chow 2003 Geifman & EI- Yaniv 2017)) or margin-bases classifiers (Bartlett & Wegkamp 2008))-
For each family G, we then collect empirical confusion-rate matrices Se = (M) 9 E 9) and keep the extreme points (X) their convex hull. Finally, we form the union over families and extract the global extreme points
S. = ext U cxt(s
GEG
The set S. defines the empirical support of attainable confusion-rate matrices for group o, and randomization over S₂ recovers the entire empirical region R2 (s).
Empirical level inner L.P. For fixed finaar-frctional centroids { Jejjy the inner optimization
Suff
reduces to an LP in convex weights and linear centroids.
Analogous the binary class setting, we use empirical plug-ins for proportion based quantities (c.g., Ra.y = 1/naa Σx a;=a (Y; = y)) and empirical group-wise confusion-rate matrices { (Mk Jees. obtained from the post-processing dataset.
I' scores are tied, then ties can be broken with deterministic rule (e.g.. lexicographic ordering), resulting well-defined confusion matrix.
In the binary-clat class setting, suffices to consider group-wisg thresholding rules (ef.equation since the realizable operating characteristic region (cf. equation [ is completely determined by these deterministic rules. In the multiclass setting, however, there is no analogously simple one-parameter family that recovers all extreme confusion-rale points; multiple families are needed adequately explore the frontier of R., (s(s) (cf.equation] 24
25

---

Published as a conference paper at ICLR 2026
We also impose additional positivity guards with negligibly small Ea 0 to ensure the centroid- based linearization valid for the sufficiency based constraints.
(Empirical) Inner Optimization for Fixed Linear Fractional Centroids in the Multi-class Set- ting
min ( (a (gelp)
{Tra
Σ
Ta Σ
Na. Man
Aa.
aEA
jES
s.t.
Σ JESn
Naj = 1, Aa. 2 0,
ya,
DP bands:
dpp
Aa.5 Mc)(,,
96 S
dop va, 2, 2
EO bands: 2
FRQ Fn 1
Σ Xa M.
S8Q ने angg Va, y, C, Aglé n.y S
2
Suff. bands: 2
6ouff
ΣΣ
Das (y).0))
1
EXa
Xa. DaaMMa MD (v,
Suff
ΣΣ Nay (v's (o) s
gole
Σ
Xas Min (v/, C), Va, C.C.
2
Positivity guards:
ΣΣ
Aa. M (v, 2) 2 Ea, Va,
(29)
An outer search over 7Bull then produces target confusion rates (Ma)aea Similar to the binary class setting, a simple feasibility guard can minimally relax the tolerances when the user-specified fairness levels are empirically infeasible.
Computational complexity. In the multi-class setting, each group-wise confusion-rate matrix lies in an affine space of intrinsic dimension d C(C-1), so the inner problem remains polynomial-size LP in the convex weights and fairness centroids, and the outer search over offuff E IIa A C-11 has the
same structure as in the binary case.
The principal open question is whether the empirical hull, constructed from pruning many determin- istic classifiers over Ppess remains small in practice, as it does in the binary setting (e.g., 20-30 support points per group even for datasets with over one million samples like ACSINCOME; see also $A.5).
A direct analogue of the theory available in the binary class setting (e.g., Grenander-style arguments for the ROC frontier as in Groeneboom (202T) is not yet available for multi-class confusion-race matrices. We view developing a full theoretical and/or empirical characterization of the number of support points of this empirical hull as an interesting direction for future work, but note that does not affect the polynomial-time time solvability of each inner-optimization subproblem for any fixed number of classes.
Constructing classifiers.
Given a baseline post-process with confusion matrix M. for group a and a target Ma we give one particular multi-class construction.
Multi-class fabpl-fiipping Let Rg E CCC be column-stochastic matrix. If the baseline post- processor predicts è E [C], the final prediction is drawn randomly from the 8-th column of R,. The resulting confusion-rate matrix then requires
Ma (())) Ray
R.. RTT ī, R. 2 0.
(30)
26

---

Published as a conference paper at ICLR 2026
The expected intervention rate in group equals Int. = =1 E. Uu,cRa(e,e).
Choosing the baseline post-processor and finding the min-interrvnnton classifier: Unlike the binary class setting, where any feasible point on the convex hull of the ROC curve lies one-dimensional segment between two adjacent threshold rules (i.c., a mixed-GWTR ef. equation 4. the multi-class feasible region is higher-dimensional polytope whose extreme points correspond many deter- with empirical confusion-rate matrices {Ma' yees. Consequently, it is
ministic post-processe non-trivial to identify which mixture of deterministic rules, indexed by Sa, we should take as the baseline post-procst post-processor.
adopt simple and fully empirical strategy. For each group a, iterate all baseline candidates (Ma") Jees,, and, for each baseline j. we solve the small convex feasibility problem associated with the chosen intervention mechanism. That is, for the nubel-flipping mecha- nism, we find parameters Rg such that equation 300ho respectively, while minimizing the expected intervention rate. If no such parameters exist for baseline infeasible under the mechanism and skip it.
Instead,
deem that baseline post-processor
Among all baselines j for which feasible mechanism parameterization exists, we simply return the one attaining the smallest intervention rate. This procedure guarantees that the final randomized classifier is realizable and chosen minimize the expected number of interventions.
A.3.5 ROC-F PROCEDURE FOR A SIMPLIFIED SETTING: DP AND PP
In this section, we provide single self-contained algorithm with the full end-to-end implementation of our procedure for single fractonfaational and linear constraint of predictive parity (PP) and demographic parity (DP), respectively in particular, Algorithm 6 below is a specific instantiation of the end-to-end pipeline outlined in Algorithm |
Note that the construction of classifiers for target operating characteristics rates does not require these specific group fairness constraints (i.e., the "Construct classifier" step in Algorithms [ and 6 see, also, $4.3 A.3.1I nonetheless, we present our classifier construction procedure as a self- contained algorithm inside Algorithm 6 for completeness and increased digestibility our method- ology.
A.4 THEORETICAL DETAILS AND PROOFS
Admissible centroid sets. For each linear fractional (LF) constraint i KTFFF let [L,, Up C
[0, 1] for all E A, denote the range of the LF group performance function (cf. Definition 3.1 Given disparity level os. [0, Un Lu), we define the admissible centroid interval as
Qs = LL + 6x Un
(31)
Denote Za == (K,)(Pa), a E A, which satisfy max a -za za! S ōg.
Then denote
n Za
4x Fa
+
4x 2
max =n
min za + + =: Ix; Ay 2
aEA
so that I, n [L
2, Up
&
Ø, and any centroid ia chosen from the intersection automati-
cally lies in Qk.
For common LF constraints like predictive parity and false omission rate parity, we clearly have [L,, Uv] = 1] and 6% E [0, 1]. Hence, the admissible set of centroids for these metrics is Q2 164/2,1-6x/
Definition A.6 (Operating characteristic feasibility region). Let KG, and KLF index linear and lin- car-fractional group performance functions, respectively, and let q = (qx kEKL) be fixed centroids
for the LF constraints. Define 3(7: s, 5) be the set of {aaJA such that there qe, E KL. such that for all a and E KL. 6r S (ūtea, ge S 2. Also, for all and E KLF,
(ūk Pa) (gk + 11 (ūk Pa) < O. (qk- - (Tk Fa) (ūx, Pa) S 0, (Tk, Pa) > >0.
The (eenrooi-frree) operating characteristic feasibility region is then the union B(s, 5) U (1 8, 8), where Q is the collection of admissible centroids for the LF constraiits (cf. Eq. 31
27

---

Published as a conference paper at ICLR 2026
Algorithm ROC-F pipeline for 6-approximate demographic parity (DP) and predictive parity (PP)
Require: Training set Dirains postprocessing set Posst. test set Dreat; groups A: tolerances óD 2 0:
centroid interval Qrr C [0.
Ensure: Target operating points (aa and (optionally) a post-processed classifier
1: Pre-train predictor: Fit a probabilistic predictor : & x AA + [0, 1] on Derain-
2: Postprocess ROC curve. On poss. compute probabilistic predictor scores s(2i, a;) and retrieve labels
Vs- For cach E A: form the empirical ROC curve and keep the upper convex hull supports Ha
(pd))
5= ((TPR, a FPR, (5) )]==; build lifted points ملمم (TPR, .PR.. (3) _1)
S.
(i)
Using poast. form plug-in coefficients to estimate group rates Pa for Pa == Pr(A=a) and base prevalence rates R.a for R.. := Pr(Y=11 A=o);
mis- clascsaasiiiintoonn rate vector %
Pamas P. R.), PaRa):
DP (linear) coefficients: upr = (Ta: Ra. 0) upr = (0.0, 1); and,
PP (linca--racttonna) coefficients: üpr,a (Ra 0), Urr ( Ra 0).
3: Search region (DP PP)
4: for qPP Qpp do Inner LP (DP+PP):
coarse grid over PP centroid
min
Σ Po)
Duihh 9DP aEd
Σ Aus =
Aas 20 0
bj E S.,
JCSu
s.t.
Ya E
Pa
Σ
Aa.
-(1)
JE8a
(DP as linear constraint via centroid gDP)
S (ūnp,a qpp 1
Va E A
(PP linear-fractional constraint with qrr)dqrr)
(ūpp.a pa))
1009p99 qpp
2 Spp (Tpp,a: 50,
Va E A
@PP 2 (Dpp.a Po)) (ŪPP.a. 50,
Wa EA
(PP denominator positivity guard)
(Epr.a. Pa) 2 EPT 1e-7
Wa E A.
Let (ggp) the optimal value {A {P.) qoe the optimal variables. if (ggp)) best then best +- $(gpp), opt.opt f qPP, (DP.opt f- qDP, da da. Pa Pa.
end if
9: end for
10: Return Return the target operating points (Pa)aeA.
11: Construct classifier.
12: for group a E AA do
13: Compute base prevalence rates of empirical hull. Extract the subpopulation ((zi, a, vi) Doein
and use s(,,, a) to form the convex hull of the (mirrored) empirical ROC:
Hamd (t..a....., as along with (FNR, FPR. ..0 y=1
8a
here, 8o.+ is the plug-in in estimate for (نك = (r(f(0)=1 A=a) where f(0 (z, = (s(2, 2 tg.a).
14:
best <- +00
15:
for each adjacent pair (j,+1) in Fi do,
16:
Search over 0 on this edge via a ID line search G (e.g., grid search, golden-section search):
Read off
FPR (0) = (1 (1- FP ( + OFPR
(1+1)
FNR.. = (1 -1-10 O)FNR ()
(0)
+ OFNR. (++1)
and the baseline selection rate Sa, (0) (1 8)5!)) 05()+1). (Continued on next page.)
28

---

Published as a conference paper at ICLR 2026
17:
2. Compute mechanism parameters.
18:
if mode LE then
label-flipping
Define mechanism mechanism-specific operating characteristics
TPR (1 Pa. (P) (0)
po. (011--TRR..) (0)
TPRg,0))
FPR (1 Pa.1 (P)) (0)
Pa.o I.PR, 2,
20:
Solve for the solution Ps.o (0), Pa.1 (0) E [0, 1] of TPR!, = TPR.. FPR FPR..
21:
The expected intervention rate
LFF Pa. (0) (0) + pa.o(0) Bort (0))
end
23:
Update best solution Assemble outputs.
24:
if I < best then
25:
set 0g 8 and
Co + (fj,ar tyt1, la Pa.Pu,( Pa. (0)),
26:
and best FI. end
27:
28: end for
29: end for
30: return parameter recipes {Sa YacA.
31: Evaluate.
32: Construct from parameter recipes (oo by defining baseline post-processor f(
1 (x) =1 (s),, 2 (,,0) + 0.1 (s(2, 2 (5+1,))
and its positive prediction rate
qu (=) Pr (1 = 1| =
33: The final (fair)
Po,o qa (x)x))= (a.)4)
34:
On Doest, evaluate f and report loss and the induced DP and PP metrics of
max P
max a.e'EA
0.0' E.
35: return (P.): f, and test metrics.
29

---

Published as a conference paper at ICLR 2026
A.4.1 PROOF OF THEOREM
Denote the feasible of the post-processing problem with fairness constraints encoded pairwise disparities (cf. equation and the discussion below it) as 8o(s, 6).
We prove this theorem in two parts: (i) first, we argue that Bu(s, 5) - B(s, 8) (cf. Definition A.6 then, (ii) show that the optimal values are the same.
(i) Equality feasible sets.
Part 1. The first required inclusion is that 8o(s, S 8(s,
Suppose {Pataed E Bu(ss 5). Clearly, for any collection of numbers {EalaEA. E [0, and
8 1
max 0,a'
Ea Zal S
qq E [0, 1]such that 2a -9l 20//////2
(32)
Now consider the disjoint sets of constraints, KL, KLF, in turn:
If & E Kr, take {=aJaEAA = {(TH, Pa) JaEA. Then the pairwise disparity constraints and equation 32 guarantee the existence of qk E Qx s.t. -6x A. This centroid is admissible since it associated with linear constraint. 2
2 S (Uk Pa) - 9k I & for all
If k E KLF, take (aalaed = (Ga, = denominator positivity constraint.
(.)) (B)...aa) JoEA which is well-defined by the
Since max, Go.k min, Ga,k & S 6g for all KLF K. and Zn [0, 1]. the set
n Fa
4v 2 2a + fx
max Za 2 min iq + 4x 2
REA
is nonempty. Moreover, it included in Q 1 6 (admissible set of centroids cf. equation 31.. Pick any qk E Qu in this overlap. The pairwise disparity constraints 1za qul 8x/2 and denominator positivity are then equivalent to
(u Pa) (gk + d ( Pa) <0, 0, (gx= (Tx, Pa) (U Pa) S
for all E A.
Since Qh E Qu for all l E KLF, conclude q e Q.
It follows that {PaJacA E 3(q 5) for some admissible
Part 2. The second required inclusion is that (o 8) 2 3(s,
Suppose (PutaEd E s, for some Q. Consider again the disjoint sets of constraints Kr,, KIFF, in turn.
If KL, then (ūk Pa)) qul S 6 for all E A. Hence, for any a, a', (ū (a) - (ūg,a' ) S (Tk, (akka,Pal Pa) qk + (Ths, Par) - quc S 6z
so that the pairwise disparity constraints hold.
If k KLE. then for each A,
(ū (gx + 44 (ūR pa) S O; (gi- 44 (KUk,asPa) (ūR Po) 5.
By denominator positivity, dividing by Vi.a gives 9s dt < Gk. Gka(pa) S qk +
8x
2 so
by the triangle inequality, (G..a Gk.d (Pa:) ) s on for all a, d'.
Therefore (Pa PaEA E 5).
(ūi) Equality of optimal values. Let J(P denote the linear objective in equation we have Bo(s, 8) 3(s, 8) USED 3(q s, 8). Hence
From (i)
min min J((āa)) ((1)6 (%a (8a.e8().)))
J((xa))
min min J((Aa)
min + 7EQ
7E0 (p.133((..3)
30

---

Published as a conference paper at ICLR 2026
since the inner problem at fixed q is exactly equation 9 with optimal value (g)). Moreover, the above argument also implies that the minimizers can recovered as stated in the theorem. This concludes the proof.
A.4.2 PROOF OF THEOREM
We begin by introducing relevant notation and then proving two helper lemmas that provide uniform convergence rates for the group-wise operating characteristics (cf. Lemma A.7) and deviation bound on the fairnsss constraints using an appropriate Lipschitz constant (cf. Lemma A.8)
Notation. For each group a, denote the population-level ROC curve as (s) and the empirical convex hull built from D post as (s) (cf.
A.2.1 I. For arbitrary lifted operating characteristic rates
[Pa]aed with Pa E [0, 1]2 x {1}, the objective is
J(LāaJoEA) = (7a. Pa),
aEA
with empirical version J(PPa A defined by plugging empirical coefficients Ta constructed from D post Define the group-wise maximum-l1 norm of Ta B,, == max A fall..
Lemma A.7 (Uniform control of groupwise rates). For any confidence level 8 E (0, 1). with prob- ability at least - 8, we have simultaneously for all E and all thresholds t RR that
sup TPR. (t) (t),(t) S Ma,1,
sup FPR. (t) (t) S N..0-
where Na.j Σ, (TPPR FPRo(t;) and its empirical analog Pa = E, (TTPRa (PF)),PRR (t),(,;);1), we have 11 Palla S 1/ + Na In particular, for all a E A, the Hausdorff distance between Ra (s) and (5) in the Loo metric is at most No + Ta.00
for j E (0. Consequently, for every convex combination Pa 2m V 2naid log
8
Proof. Let (t) = Pr Ps(xs a) <t Y = 1,A a) and Fa.1 be its empirical conditional CDF over the Na,1 positives in group a. By the DKW inequality (Dvoretzky et al. 1956 Massart 1990s, Pr ( sup; (t) Fo, (t)
Fa, (t and (t), the same bound holds for sup, (PR.(t) TPR, (t) Setting the RHS
2e 2m Since TPR, (t)
(t).(t)
of the inequality to 8 / and applying union bound yields the result for deviation in the TPR. A similar argument holds bounding the FPR from its empirical version in the = 0 case.
The convexity statement follows from linearity of convex combinations and the triangle inequality:
Pe.- Palli s ( TPR, (t,) (t,) - FPR, (t,)) S Na.1 + Na,00
The Hausdorff claim follows immediately, since we can approximate any Pa E Rs) with the same mixture in the empirical hull and vice versa.
Define the following Lipschitz constants
max
Uuka lloc:
k E KL.
aEA
L
Hugaallllluaall + || I1ll k KIF-
max aEA
ez
Lemma A.8 (Lipschitz control for linear and linear-fractional fairness metrics). For p. pf E 10, {1} that satisfy the denominator guards (Uk,a p) 2 Ey and (Vk.ar p) 2 EN for k KLF.
[k.a(p) Gk,a(p') < L+llp p'l12, VK K= K, KKr.
(33)
where the group perup-performance metrics (cf. Definition Gkal(pa) (uk Pa)) (Vk,a; Pa) for l Krr
3.7 Gk. = (Uk.as for k E Kr, or
31

---

Published as a conference paper at ICLR 2026
Proof. For linear constraints &o E K1, the claim is immediate since
(k,a(() - Gk.a(p') = 1(uk,a - D'll s ||4,,all0llp -/112
with La = maxa |lux,allo. lloc.
For fineao-fractionl constraints & KL.,, write Uk,((p) (uR,a p) and Vk,a(p) (UR,as p)- Now, for any p.pl [0, {1} with (e)( (p') EK.
Uk,a(p) ViLa (p)
Uk,a
Uk.a(p) Ux.ap)VVe.a Un,a(p')
Una(p) - (hkal))UUnalP11) ( + (Vra(() Vi Vala(
By Hölder's incquality, (p),a(p) - Un I aux,allool1e pl1 and [Vka(() Vkk(d)) s
|eeelllslllee p'l12, while [Uk,a (p')l $ || | and [Vk,(('') - || Thus
Gkaa(p) - Gkaa(d)) & Lxlp - [|,,
as desired.
We can present the proof of our main result.
We work on the intersection of two high-probability events that control (i) uniform convergence of the empirical ROC curves, and (ii) concentration of the plug-in fairness coefficients.
Proof of Theorem 4.2
Let E denote the (DKW) event of Lemma A.7 on which
hup/TPR.AA (t) TPR. (t) & No sup (t). FF),((t) f7,00 Va E A,
where Ma.. =
1 log 4m for j E {0, 1}: this event holds with probability 2 1 - 5/2. 8
2na..
Let &g denote the Hoeffding event which all plug-in coefficients for the faimess functionals (group proportions, base rates, and all quantities entering Uk Tk and the objective coefficients Ta) satisfy
| ukaalloc llūka Vkaaloor
Il Na Ta C Ma. Va k
where Ta :
log AmK
The == na,0 + n2,11 the total sample size for group a, and C 0 na.j. m. K, d); by Hoeffding's inequality
2na
constant depending only on {uk,as Uk.as Va (but and a union bound, this event holds with probability 2 11-55 5/2.
By union bound, Pr(Ei E2) 1 5, and henceforth work on the event & E1 Ez. Furthermore, for convenience, combine the sample rates as
Ma. := No.i + C- Na,
j (0,
Now, on the event ε,, there exists /² = (Pt with p E Ra(s) such that
l - Pill S No.1 + na,0:
Va E A,
by the convexity argument Lemma A.7
Moreover, for every E A and & E K., Lemma A.8 guarantees bound on the deviation of the fairness metrics
Gk.a(PP) Gk.a(Pt) < Lx + Na,0).
Since e' satisfies the bands |Gk, (Pt) - qul S 6x/2 for some centroids qa (cf. Theorem 4.1 the z satisfy
(T)) - qul s 8x + L2(N1..1 + na,0)) 5
8x
+ Lu7ts
1/ := max (fa,,1
max(1la,1 + Nl.
2
32

---

Published as a conference paper at ICLR 2026
rounding O to the nearest grid point grid with stepsize ha introduces an additional slack of at most L4h4 in (P), - qul Similarly, using Lemma A.8 the denominator guard contributes at most further constant multiple of to the bands.
Furthermore, using Lemma A.8
Consequently, there exist Cgrid. C. depending on {uk,as Vk,a JaEA, kεK and the margins {EE}KER such that pa feasible for the population-leve problem with (inflated) bands
0% Ò₁: + 2 + 2L + 2C.
Risk generalization. Let @ (o and et = p be the optimizer returned by our empirical for nominal disparity levels {6x) and (di respectivvll In particular, both procedures use the same grid stepsize, same empirical ROC hulls (s), and same empirical plug-in coefficients.
region search procedure (Algorithm)
2
We now decompose the risk as
J(o') J(0') + -(()) J(O") (((") J(0' ( - J(e") = ( J( 10 J(o')
B
E
and control each term as follows.
Terms A and D. On the event Eg, for any e = (potaEd with P E [0,113 x x {1}. we have
(((e) - [(o) = Σ (aa Per Pa) < B, Σ Ilpallal -allos S B, Σ
(7, 1 + na,0);
aEA
acAA
aEA
where B, == max l1Tall2. Applying this with e= and @ = @² yields
|Al S By Σ (No.1 + n/.0).
REA
Term B. Define the value functions T nom (g) and in (g) the optimal values of the inner LP of the region search algorithm for fixed centroids q under, respectively, nominal and inflated bands. Since Φ and ø' minimize these value functions over q' E Q centroids Znom and Tauft, respectively, we have
nom (Tom) iint (Mint) S sup @ nom ( -0---nn innt (7))
qEQ
For any fixed 7. the two LPs differ only in the right-hand sides of the fairness-band straints, with per-coordinate inflation at most 5imil - 62 = 2T + Lahh + Cz By standard parametric LP sensitivity (e.g. [Bonnans & Shapiro 2013). there exist constants Cstas, Cgrid, Ce > 0 (depending only on [70 and (uk,, Uk.a) ) such that
0 < B < Cstat (m. + Na,0) + Cgrid
ha + Ce maxE &
Term C, On the event Ez, we have uniform bound
(k)a(p) ( I Cparam (Na,, No.0) Vp Ra(s),
for some constant Cparam > depending only on {uR,a= Ux,a). Since O² is feasible for the inflated population bands, Ø violates the inflated empirical bands by at most an amount of order La (Ma,1 T),,), in addition to the grid and guard terms Σx h& and max; & already accounted for in Simil, Thus, by standard LP sensitivity argument, there exist constants Ca Cariid C² > such that
grid:
ICI (T J( < Catat aed
Σ + To,00) + C C'rid
Σ KER
hu + + max Ek- kEKLP
Term F.. Using linearity of the population objective,
Σ
PM
B
Σ
P
-
B, Σ
(No,1 + na,o),
aEA
aeAA
aEAA
where the last inequality uses the construction of T from Lemma A.7
33

---

Published as a conference paper at ICLR 2026
Collecting terms, obtain the desired bound the risk
[(0) J(e") s ||| + B + |C| [D] |
- (3By + Cstat + -Ctaa)
Σ
(Ma,1 + 77,0) + (Cgrid + Cgria)
> kER
aEA
+ (C2 + Cr)
max KEKLF
(Na,1 + -7,00)
Σ kEKLE
hy
max Ek. KERLE
REA
Fairness altainment.
On the event ε,, the plug-in fairness metrics satisfy
Gk (p) - Gk.a(p)] S Cparam (Ta,1 + Na,0); vp E (s).
for some constant Cparam > 0 depending only on (uk,a Uk,a The triangle inequality then gives
[Gr,a(Pa) Gk.a (pwi) S (k,,(Pee) Gr. (Pa) + (k,a(Pa) Gk.ar (Pa.))
G (Pa.) Gk. (Pa')
8 Cparam [11,,1 + no,0) + (Na',1 + Me o))
so that the maximum pairwise fairness disparity satisfies
max
(ka) Gk.a'(P'' S 6F Te,
Th == max(1a,1 + 7a,0)
0,0'
This completes the proof.
A.5 PRACTICAL IMPLEMENTATION DETAILS
We provide here additional implementation details for the experiments in $
Datasets.
COMPAS (Larson & Angwin 2016 is recidivism dataset where the goal is to predict re-offense within two years. We take race as the protected attribute, restrict to the two largest groups (AfricanAAmriiaa and Caucasian, [Al-2), and perform preprocessing as in Cho et al. (2020) (e.g., removing traffic offenses and enforcing a screening- window) yielding 278 individuals in the cleaned dataset.
We start from the ProPublica two-year cohort and retain only the [age, c.charge.degree, race, sex, priors.count, is-recid, c-jail.in, c.jail.out].
columns wtw..bb.sceennngarrees...
We remove entries with inconsistent screening/arrest timing by keeping records with with is rerec = "O"). Next, we compute length of stay the day difference between c_jail_oo and c.jail i_jail_in, subsequently dropping the original jail timestamp columns and the screening-arres column. We restrict the analysis the largest racial groups (African-American and Caucasian), binarize the label from is is.recid, and define groups by race.
days b. wwwcreening......mmm. aereesstrrrrst arrest in [-30,30 days and excluding
= -1. We then drop traffic offenses (c sc.charge.degres
When training the attribute-aware classifier, remove the sensitive column from X (here, race) and apply one-hot encoding to all remaining categorical features; the protected extra input feature.
attribute A is later concatenated
Lawschool (Wightman) 1998 Fabris et al. 2022) is law school admissions dataset from the Law School Admission Council (LSAC). Following common practice, we keep the core features LSAT, GPA, Gender, res i dent, race indicator (e.g., White), and the binary admission label. After removing unused columns and dropping rows with missing values, the resulting dataset contains 96,584 individuals.
34

---

Published as a conference paper at ICLR 2026
Table 4: Training hyperparameters used for the probabilistic predictor s.
dataset
epochs
learning rate
batch size
hidden width
# layeess
optimizer
COMPAS
500
5 x 10
2048
32
Adam
Lawschool
200
2 10-4
2048
32
Adam
BiasBios
20
1 10
128
32
Adam
ACSIncome
20
x 10-3
128
32
Adam
We treat |A|=2 race groups as the protected attribute, integer-encode them, and, consistent with our attribute-aware setup, drop the sensitive column from X before concatenating the protected group index as an additional input feature. Numeric features are standardized, and categorical features are me-hoot encoded.
BiasBios (D-Arteaga et al. 2019 Ravfogel al. 2020 is large-scale biographi- cal text dataset containing short professional biographics paired with ground truth anno- tated labels for one of 28 occupation categories (e.g.. "physician", "software engineer", "nurse", "teacher") and an associated binary gender attribute provided in the original meta- data. We extract subset of 25,000 biographies by uniformly sampling from the full corpus of roughly 400, 000 individuals.
We designate gender (fema le vs. ma male) as the protected attribute ([Al=2), and con- struct a binary prediction task by grouping the original profession labels into STEM and non-STEM categories. Specifically, we map {software. reengiieeeeeeeeeeeeeeeeee phys i a an, surgeon, dentist, architect, composer] to the STEM class, and assign all re- maining occupations to the non-STEM class.
To handle the text-based data, encode each biography using a frozen, pretrained Distil- BERT encoder by computing one CL.S-based embedding per biography and subsequently standardize these embeddings before feeding them the downstream pre-training and (post-pree prost-processing) fairness algorithms (Devlin et al. 2019). Ultimately, all experiments operate on a fixed 76$-dimensional feature representation.
ACSIncome (Ding al. 2021 comes from the 2018 Yne-Year American Community Sur- vey and contains data on a total of 1, 664, 500 individuals. The goal is to predict whether individual has income of above below $50k. We consider both binary protected attribute (|A|=2) and a qulti-group setting (|A|=5) by either using gender (Male and Fe- male) grouping by race. We follow the preprocessing steps of of & Zhao (2024) for precise variable definitions and bucketing procedures.
We use Folktables' ACS (2018, 1-Year, person) slice and apply adult filter. adult.filer. The feature set includes AGEP, COW, SCHL, MAR, OCCF, POBP, RELP, WKHP, SEX, RACIP, with category maps supplied for interpretability. For binary classification, the target [ INCP $50,000). We set the protected attribute to either SEX in the binary protected attribute setting (cf. 15.1) or bin by RACE for the multiple protected attribute setting.
Races are binned as follows: White (RAC1P=1), Black or African American (2), American Indian Alaska Native (merge 3,4.5), Asian, Native Hawaii iinn or Other Pacific Islander (merge 6,7), Other (merge 8,9).
We convert to a data frame with dummy variables, map group labels to integer codes, and consisettt with the attribute-awar setup- drop the sensitive columns from X before concatenating the group index as an additional input feature.
Base classifier
The probabilistic predictor is small MLP with three layers and 32 hidden nodes hidden layer, ending in a sigmoid output. We train with Adam (without weight decay) and binary cross-cntropy, using dataset-specific epochs, learning rates, and batch sizes listed Table 4
Baselines. We compare with two post-processing methods that seek to simultaneously control LF fairness constraints (META and MFOpt), and one state-of-the-an post-processing method that controls for linear faimess constraints (LPP). In addition, we record the performance of the un- constrained probabilistic classifier (Baseline and an oracle post-processor returned by the Regi BaggonSSercchPP routine of Algorithm 3 (Oracle).
35

---

Published as a conference paper at ICLR 2026
Baseline refers to the probabilistic predictor with no faimess constraints imposed. It does not use the POST set at all (neither for post- pascepssing/dddiiiioonn calibration nor as additional training data for the TRAIN set) and instead directly evaluates the TEST set.
Oracle denotes the optimal operating point returned by RegionSearch-FG (Algo- rithm using the TEST set - this requires access to the true labels of the test set. That is, these rates maximize accuracy over operating characteristics but do not correspond to valid classifier, since they use the test data 19
META (Celis et al., 2019) learns a deterministic GWTR (see equation 3) that maximizes classification accuracy subject to fairness constraints involving ratios of LF/F group per- formance functions (cf. equation (31]). This meta-algorithm reduces these ratio-based con- straints bounds on group performance functions controlled by a hyperparameter т; we tune r on POST and evaluate the fixed rule on TEST.
MFOpt (Hsu et al. 2022) learns a group-conditional randomized postt-rocessor--t i.e. a label-flippngg rule parameterized by 222 transition matrix per group that maps base pre- dictions to final labels as in Hardt et (2016). This method seeks to minimize the expected number of flipped labels (see also $4.3) subject the fairness constraints on POST. The learned mapping is then fixed and applied to TEST.
LPP-DP/ / E00p/EO (Xian & Zhao 2024) learns a linear post-processor of the base prob- abilistic predictor s that satisfies 5-approximate faimess for common linear metrics (see $3). Though it can handle multiple classes [}]] > 2, specializing
the binary setting re- sults in deterministic GWTR, similar to Celis et al. (2019). LPP-DP /EO refers to either imposing 5-approximate demographie parity, equality of opportunity, or equalized odds, respectively.
Baseline configurations
META (Celis et al. 2019): We implement the group-fair reduction with simultaneous DP, EO (TPR/FPR), and PP. A ratio band of width r is enforced by sweeping the lower endpoint a on a grid with step & = 0.01 and setting the upper endpoint to min(1, (1, a/t). We select the band by first determining whether the resulting fairness constraints are satisfied on the POST set, and then choosing the band with the highest accuracy. Finally, we deploy the resulting deterministic score rule on TEST. We use T (0.1, 0.2..... 1.0} unless stated otherwise.
MFOpt (Hsu et al. 2022): We export the probabilistic predictor 's scores on POST/TEST, run their provided solver on POST to obtain stochastic matrix mapping the transition rates between bins. Since the optimizer sometimes does not return row-statistic matrix mapping, we normalize to ensure valid classifier. We use this normalized mapping on TEST and report the sampled metrics from the randomized transitions.
LPP-DP/ / /EO (Xian & Zhao 2024): algorithm (LPP) to solve the empirical LP on POST with tolerance a=ô under either de- mographic parity (DP), equality of opportunity (EO0p) sulting (deterministic) decision rule is obtained by linearly adjusting per-class risks, and then applied unchanged to TEST to report accuracy and disparities. We use CVXPY with GUROBI (fallback SCS) and do not sweep any hyperparameters beyond the nominal 6.
We use the authors' Linear Post-Processe
equalized odds (BO). The re-
Sources of randomness. The stochasticity of the entire procedure induced by the random TRAIN/POST/ESST split, the stochastic training of s, and any randomness introduced by sampled predictions (e.g., MFOpp of Hsu et al. (2022) and our randomization schema LabelF 1ibeFFlli SabbelFlippnngg
Configurations for ROCF-LF (our method). For the LF-fairness constraint grid Opp of the Region RegionSearch subroutine (Algorithm 2). we sweep across q=1000 equidistantly spaced points within the range of the admissible centroids. For the setting with multiple LF-fairness constraints,
The optimality of this operating point depends on how refined the grid-search over the LF faimess con- straints is however, this approximation is a fundamental feature of the centroid linearization technique, see, e.g., Theorem 4.4 of Celis al.] (209). Our constructed classifiers often achieve these optimal operating characteristics (5 $522
36

---

Published as a conference paper at ICLR 2026
sweep across q=100 equidistant points within the admissible bands Opp and Qror instead. The denominator positivity margins EK are uniformly set to 10 see $A.5.1 for full details.
We set the bisection search tolerance of the wrapper algorithm RegionSearch- (Algorithm to =0.011
When constructing the minimum intervention classifier (Algorithm 5) parameter & to be 0.75. We use a golden- section search by first evaluating a coarse 101-point uniform grid over the mixing parameter 8 and then, for contiguous feasible intervals, running golden- section search with tolerance 10-5 and a cap of 40 iterations.
set the snap tolerance
On computational level, incorporating dimensional) grid search in RegionSea search in the grid size, we find that a modest, refined grid of 10100 equidistant points for both FOR-parity and PP performs well in practice (see AA.5. and AA.6.2).
additional LF constraint amounts extra (low- (Algorithm{) Though this yields polynomial-time
A.5.1 THEORETICAL AND PRACTICAL IMPLEMENTATION OF COMMON LF CONSTRAINTS
Let - Pr==P(Y==(A-A) be the prevalence/base rate. The following conditions ensure equation and denominator positivity (p) (Uk,a, p) 2 Ek O for k KLF; see $4.2 met for predictive parity and false omission rate parity.
Predictive parity (PP). For Grr,a
TPR. F. TPR. (1- IFPR, (0, 1), the centroid band [Gpp,o - -ppl & 6pp/2 is equivalent to the linear inequalities in (FPR,, FNR.):
(q T 2
6pp )1 Ta)
1 1N E (TPP) (FPR, 0g (UPP) FPR.),
aa (o/hi(()) =
(1 (q F SPp na
which is valid when (1 - F 6pp 22) a for all a AEA Denominator positivity requires na (1(1 FNR.) + (1 na FPR, 2 Epp > 0 for all E A.
False omission rate (FOR). For GFOr, [1 [1-Ta)) F E 1). let L = -OOR- OFOR/2 and U 9Fon + 5FOR/2. The centroid band [Gron,a @FOR| I 5FOR 2 is equivalent to the two linear constraints:
T.. PNR
(1- (1-L),, FNR, + L(1-7.)FPR, 2 L(1-
(1 (1-U)),FNRR, UL- S SU(1-Ta)
Denominator positivity requires (1 - xT)(1 FPR.) + T. FNR, 2 EFOR > 0 for all a E A.
Practical implementation of bands for common LF constraints. As derived above, admissible centroids require (i) the band coefficients to be well-defined PP (1 (q = 6pp/2) > and (ii) positivity of the LF denominators
PP: T FNR.) ) + (1 TT) FPRR 2 EPP;
FOR (1 - a (1 FPR. ) + FNR, 2 EFOR-
In practice, we perform outer grid search over Q₁ and impose additional box constraints the inner-LP of equation D
Intervals and grids. We ensure band coefficients are well defined by restricting centroids to the outer grids,
Qpp [8Pp/2, 1-pp/2 6pp/2]. QFOR [ÓFOR/ 1--OOO/2]
If only LF metric is active (PP FOR), sample uniform grid of 1000 points its interval.
If both PP and FOR are active, we sample 100 PP points and 100 FOR points and iterate over the pairs in their Cartesian product (100 100 pairs in total, barring denominator guards).
LP box-constraints. To enforce denominator positivity, we add the box cox-constssints FPR, 2 E, 0 FNR, < 1 in the inner-LP of equation 9 with 1e-7 set to be negligibly small. This is slight relaxation; in practice, with n, E I) and our specified grids Qpp. @FOR. these boxes are sufficient ensure the more formal condition (Vk,a > 0) and work well in practice.
37

---

Published as a conference paper at ICLR 2026
A.6 ADDITIONAL EXPERIMENTAL RESULTS
A.6.1 ADDITIONAL RESULTS FOR EXPERIMENTS IN MAIN BODY
We present here experimental results for the binary protected attribute setting on LAWSCHO01, BIASBIOS, and ACSINCOME and the multiple linear-fractional constraint setting for COMPAS, LAWSCHOOL, and ACSINCOME for completeness; see Tables 5 a
Our method ROCF-IP performs favorably on LAWSCHOOL, BIASBIOS, and ACSINCOME with binary protected attributes for the setting where DP, EOpp. PEq, and PP are controlled for at either level 0.02 (for LAWSCHOOL) or 0.05 (for BIASBIOS and ACSINCOME) (T
For the multiple linear fractional setting, we observe that our method can recover mixed GWTR with no added randomization as the final classifier and perform as well as state-of-the-art post- processing methods (Table
We also report the behavior of the feasibility guards triggered during our calls to the region search algorithm (Algorithm 3). This algorithm called on both the post-processing dataset and on the test set (Table (A) and (B), respectively). since ROCF-LF (or Oracle) finds and uses optimal operating characteristics from the post-processing (test) dataset (cf. $5
For the experiments which had a substantial number of triggers (i.e., the setting of multiple LF fairness constraints for BIASBIOS with binary protected attributes and ACSINCOME with multiple protected attributes), we found that the resulting expansion was quite small (a%*1.48 and a ax.1.00 1.04 at nominal levels 0.05 and 0.10 for BIASBIOS and ACSINCOME, respectively, resulting in an additive constant in the disparity level of about 0.025 and 0.005) and yielded strong empirical results (Tables and
For the experiment for controlling multiple LF constraints on BIASBIOS, the failure of our ORACLE and ROCF-LF methods achieve the nominal disparity levels of 0.05 is not the result of any inher- ent shortcoming of their methodology, but rather serves to illustrate the difficulty of simultaneously attaining nontrivial level of approximate fairness for multiple linear/linearfraccin for this dataset (see also the discussion in $5.2).
constraints
On a computational level, any runs that trigger the feasibility guard also require an additional bisec- tion search on the expansion parameter and thus requires multiple calls to Algorithm 2 but we find that a modest level of tolerance for terminating the search =0,10.01) performs well (see Tables and 7 for further discussion of computational runtimes, see AA662
A.6.2 COMPUTATIONAL RUNTIMES
In this section, report wall-clock rumning times of our method and baselines the experiments in $5) Figures A.6.2 and A.6.2 display the runtimes measuring the average execution time of a single run per seed for the COMPAS, Lawschool, and ACSIncome datasets. All experiments conducted on a computing cluster equipped with Intel Xeon Platinum 8375C CPUs @ 2.90GHz processors. For the COMPAS dataset, each run is allowed of RAM, while Lawschool and BiasBios each use up to 2 CPU cores with 8 GB of RAM, and ACSIncome uses a single core with access of up to 32 GB of RAM.
use up to 10 CPU cores with I GB
When the nominal levels are well specified and the guard does not trigger, runtimes are modest with small error bars (Figure A.6.2 and Figure (.) (D)) We observe that this setting occurs often in practice; see Table 7 By contrast, under the multiple LF constraint setting for BiasBios with binary protected attributes and ACSIncome with multiple protected attributes, the feasibility guard often triggered, solves. This leads to both larger means and larger standard crrors in Figure A)) (C), and (E).
require bisection section that adds multiple RegionSearch (Algorithm()
Although ROCF- LF is slower than classic posi-processing baselines, the longest observed runtime (on ACSINCOME with [A|=5 and x 1.6M individuals) is on the order of minutes (=60 minutes) and remains practical for offline model selection. More importantly, these additional solves de- liver strong empirical results: ROCF-LF attains the nominal disparity levels while achieving nearly optimal securacy-fairnes tradeoffs (cf. 5
38

---

Published as a conference paper at ICLR 2026
Table 5: Performance the test for (A) Lawschool (|A]=2). (B) BiasBios (IA) 2) and (C) ACSIncome (14|=2). The disparities dde, 62opp ôpzg óy are controlled level 0.02 (for Lawschool) or 0.05 (for BiasBios and ACSIncome) whenever they are active. Interv. is the empirical intervention rate on the test set (sec Definition A.3). Cells in green indicate that the fairness constraint is satisfied within two standard deviations of the nominal tolerance level, whereas cells in red indicate violation. Entries in the Oracle rows are shaded in lighter colors denote that they not practically feasible baselines.
(A) Lawschool (|.4] =2)
Method
Acc
EOpp
PEg
PP
FOR
Interv.
Baseline
Oracle
0.78 1. 0.00
0.02 0.00
0.01 1. 0.01
0.01 1 0.00
0.02 1: 0.00
0.06 1. 0.00
N/A
(ours)
0.77
0.02
0.01
MFOOt
0.67 + 0.00
0.05 4 0.01
0.03
0.02
0.05 = 0.01
0.04 : 0.01
0.07 - 0.01
0.16 E 0.01
META
0.75
0.02 0.01
0.04
0.03 0.02
0.11 0.01
0.05 = 0.011
0.00 0.00
LPP-DP
0.79 0.00 0.00
0.02 0.01
0.01 0.00
0.01
0.00
0.12 0.01
0.05 = 0.00
0.00 0.00
LPP-EO
0.79 0.00
0.03 0.01
0.03 0.01
0.01 0.00
0.10 0.01
0.05 0.00
0.00 +
(B) BiasBios ([.|=2) 22)
Method
Acc
EOpp
PEg
PP
FOR
Interv.
Oracle
0.87 1. 0.01
0.05 0.00
0.05 1 0.00
0.00 i 0.00
0.05 1. 0.00
0.10 1: 0.01
N/A
(ours)
0.03
+
MFOO
0.71 + 0.01
0.12 2 0.05
0.05 + 0.04
0.08 : 0.04
0.15 4 0.03
0.07 - 0.02
0.15 1 0.03
0.93 - 0.00
0.11 0.02
0.04 0.03
0.01
+
=
LPP-DP
0:92=00000 0.00
0.05
_ 0.01
0.09 0.02
0.04 =
0.24 + 0.03
0.06 = 0.01
0.00 0.00
LPP-EO
0.93 0.00
0.14
0.01
0.06 0.03
0.02
0.01
0.03
0.02 0.01
+
(C) ACSTncome
A Al
Method
Acc
EOpp
PEg
PP
FOR
Interv.
Baseline
0.79 0.01
0.17 0.02
0.14 0.02
0.08 0.03
0.05 +
0.06 = 0.02
0.00 +
Oracle
0.75 0.00
0.05
0.00
0.08 0.00
0.02
0.000
0.08 + 0.00
0.14 =14==00 0.00
N/A
ROCE-LF (ours)
0.75
0.05
MFOpt
0.74
0.20 0.01
0.09 + 1000
0.15 = 0.00
0.06 = 0.01
0.07 = 0.01
0.06 E 0.01
LPP-DF
0.78 1: 0.01
0.05 2 0.00
0.04 + 0.01
0.02 + 0.01
0.14 + 0.01
0.12 - 0.01
0.00 E 0.00
L.P--EO
0.01
1
39

---

Published as a conference paper at ICLR 2026
Table 6: Performance on the test set for (A) COMPAS ([A|=2), (B) BiasBios ([A]=2), and (C) ACSIncome
([A|=2). The disparities drppy dpp and óFOR are controlled at level 0.10 (for COMPAS and ACSIncome) whenever they are active; for the datasct BiasBios, the disparities dpp 8pp and бγоR are controlled at level 0.05 whenever they are active. Interv. is the empirical intervention rate the test set (see Definition A.3) Cells green indicate that the fairness constraint satisfied within two standard deviations the nominal level, whereas cells in red indicate violation. Entries Oracle rows are shaded in lighter colors denote that they are not practically feasible baselines.
(A) COMPAS ([A|=2) 2)
Method
Acc
DP
EOpp
PEg
PP
FOR
Intery.
Baseline
0.68 + 0.01
0,28
0.05
0.27 + 0.05
0.19 = 0.05
0.07 + 0.04
0.03 = 0.02
0.00 + 0.00
Gracle
0.65 1 0.04
0.15 1 0.04
0.10 1'000
0.12
6.00
0.10
0.01
0.09
I 0.01
NIA
ROCE-LF (ours)
0.65 0.04
0.15 0.04
0.11 + 0.04
0.11
= 0.09
0.11
+ 0.04
0.09
= 0.04
0.01 + 0.02
T.P..EOPP
0.68 0,01"
"6.15 0.04
6.14 4'004
6.08 20.04
"n.22" 4 0.03
6.06
_ 0.08
0.000 0.00
(A) BiasBios (I.A==2)
(A|=2)
Method
Acc
DP
E0pp
PEg
PP
FOR
Intery.
Baseline
0.93 0.00
0.14 0.01
0.06 0.03
0.02 0.01
0.05 + 0.03
0.02
0.00 +
Oracle
0.91 0.00
0.08 0.00
0.04 0.00
0.01
60000
0.07 + 0.01
0.08 = 0.00
N/A
ROCF-LF (ours)
0.91 0.01
0.08
0.04
+
LPP-DP
0.92 + 0.00
0.05 0.01
0.09
+ 0.02
0.04
=
0.24 + 0.03
0.06 = 0.01
0.00 E 0.00
(C) ACSIncome
[A]
Alm2)
Method
Acc
DP
EOpp
PEg
PP
FOR
Inters.
Baseline
0.79 0.01
0.17 0.02
0.14 +
0.08
0.03
0.05 + 0.01
0.06 = 0.02
0.00 + 0.00
Orucle
0.79 0.00
0.16 0.16.11.000
0.100 0.00
0.07
10000
00.07 1 0.01
1 0.00
NIA
ROCE-LF (ours)
0.79 0.00
0.00
0.00
0.07
0.01
+
+
LPP-EOpp
0.79 + 0:01
0.14
0.09 + 1.00
0.05
= 0.00
0.08 E 0.01
0.07 = 0.01
0.000 E 0.00
Table 7: Summary statistics for feasibility guard triggers of RegionSearch- (Algorithm for the nominal disparity levels considered in (5.2 p the proportion of runs and μ the average expansion multiplicative factor a with s.d. and is presented as tuple (p, 1i). "No expansion (N/E)" is used indicate that no expansion was needed for all seeds; that is, when listed for an experiment, (p, μu) = (0,1) across all sceds.
(A) ROCP-IF Lawschool
Active composents
COMPAS
Blasãlios
ACSIncome (IA||2)
ACSIncome (|.4|=5)
Aig. Aprapp: Arey App active Sop50pp- dpp, SPOR active
NR (0.10, + 0.02)
N/R
N/P
N/F
NYE (0.66, 1.04 + 0.05)
NE
(1.00, 1.48 0.07)
NE
(B) Oracle
Active 5 composennss
COMPAS
Lawschool
BlasHtios
ACSIncome (1.4) 22)
ACSIncome (I.4)=
frp,, Sanyp: Eyeu Spp active fopeOop App. APOR
N/B
NYE NF
NYE
N/E
NYE (0.64, 1.05 + 0.08)
(0.08, + 0.02)
1.52 0.08)
N/F
40

---

Published as a conference paper at ICLR 2026
ROCT lours)
MF Opt
META
UPP
[A) COMPAS
(8) Lawschool
(C) BlasBlos
800
800
800
600
800
600
200
Se
donson)
234e2.11
200
273961225
CMMAORR 40
200
37.5kx-33
51462
ROCEAF
MFOpX
META
LPP-DP
LPIEE
ROCFAF
MFOOpt
META
UPP-DP
LPP-ED
ROCF-LF
MFFOp
META
LPP-OP
LPP-EO
(D) ACSincome
(E) ACSincome
CPU sine
400
400
41.332240
12.86137
18
ROCF-UF
MFOpt
META
LPP.OP
UPPED
ROCFAF
LPP OP
LYAED
Figure 1: CPU runtime (mean 1 s.d., seconds) for (A) COMPAS, (B) Lawschool, (C) BiasBios, (D) ACSIn-
come ([)]=2), and (E) ACSIncome (|A|= 5)) As in $5.1 and A.3.3 the disparities dve, Stopp. daag and byp are
controlled at either level 0.05 (COMPAS, BiasBios, and ACS Income) 0.03 (Lawschool) whenever active.
ROCF (ours)
LPP
(A) COMPAS
(B) Lawschool
(C) BiasBios
5000
5000
3000
4000
4000
4000
3000
3000
3000
2000
2000
2000
F9 199305111
1000
2.
1000
513611.1
1000
020A00L
ROCE-U9
LPP LPP-EO0P
ROCF AP
LPP -0PE
ROCE AP
UPP-DP
(D) ACSIncome ([A]=) 2]
(F) ACSincome ([A] 5)
6000
6200
5000
5000
4000
4000
3000
3000
2000
2000
1000
1000
0
ROCF-LF
LPP-E00P
80CF4F
LOP-
Figure 2: CPU runtime (mean + s.d., seconds) for (A) COMPAS, (B) Lawschool, (C) BiasBios, (D) ACSIn- come (l)]=2), and (E) ACSIncome ([A]==5). in $52 our method ROCF-LE controls the disparities 8be/ /uoopp 8y and bror-party at either level 0.10 (for COMPAS and ACSIncome), 0.05 (for BiasBios), or 0.03 (for Lawschool), while LPP-DP /E0pp only controls for demographic parity or equality of opportunity, re- spectively. For full experimental details, please see $22
41

---

Published as a conference paper at ICLR 2026
Table Performance on the test set for ACSIncome (IA) = 5) over various grid sizes. The dispari- ties OEOpp ópp and ÓFOR controlled at level 0.10 whenever they active. Interv. is the empirical intervention rate on the test set (see Definition A.3 Cells in green indicate that the fairness con- straint is satisfied within two standard deviations at level 0. 0.10, whereas cells in red indicate violation. baselines.
Entries the Oracle rows are shaded in lighter colors to denote that they are not practically feasible
Grid size
Method
Acc
DP
EOpp
PEq
PP
FOR
Interv.
Baseline
0.79 + 0.00
0.25 = 0.01
0.24 + 0.02
0.09 0.02
0.23 0.02
0.08 0.01
N/A
Ornele
0.66 0.04
0.41
0.12 0.01
0.07
0.12
ROCF-LF (ours)
0.65 + 0.02
0.42
0.14 0.01
0.44
0.13
0.07 0.02
0.02 = 0.02
Grid size
Method
Acc
DP
EOpp
PFg
FOR
Interv.
Baseline
0.79 a 0.00
0.25 = 0.01
0.24 0.02
a
0.23 0.02
0.08 0.01
N/A
Oracle
0.47
ROCF-LF (ours)
0,58 + 0.03
0.47 0.47=0.0
0.12 0.01
0.55
0.11 0.01
0.10 0.02
0.05 + 0.01
(C): Grid size 50
Method
Ace
DP
EOpp
PEg
FOR
Inters.
Baseline
0.79 + 0.00
0.25 = 0.01
0.24 0.02
0.09 0.02
0.23 0.02
0.08 0.01
N/A
Oraele
0.48
0.00
0.57 0.05
N/A 0.05 0.01
ROCF-LF (owrs)
0,56 + 0.02
0.48 = 0.03
0.11 + 0.01
0.57 0.04
0.01
0.12
(D): Grid size 100
Acc
EOpp
PEq
PP
FOR
Interv.
Baseline
0.79 0.00
0.25 = 0.01
0.24 + 0.02
0.09 = 0.02
0.23+ 0.02
0.08 0.01
N/A
Oracle
0.57 0.04
0.48
0.11 +
0.56 0.08
0.10 0.01
0.01
N/A
ROCF-LF (ours)
0,56 0.02
0.49 0.02
0.11 0.01
0.59:0.00
0,11
0.11 0.03
0.05 = 0.01
A.6.3 SENSITIVITY ANALYSIS
Due to centroid linearization (cf. $4.2), we require outer grid search over admissible centroids for the linear-fractional group fairness constraints. We perform a sensitivity analysis of the effect of the grid's granularity computational runtimes (Figure[A.66 and feasibility guard triggers (Table for the ACSIn experiment with multiple protected attributes and finear-fractooal constraints.
method's accuracy performance & fairness attainment (Table B),
The grid size of either 10, 25, 50, or 100, refers to the number of the equidistantly spaced centroids parity bands that swept in the outer grid
in both the predictive parity and false omission search of Algorithm 2 (c.g.. a grid size of would result in x pairs in total for the grid search). In the related experiment of the main text (cf. $5.2). we use q 100 points.
Discussion. We observe that method's performance is quite poor when have overly sparse grid of 10 points: this requires considerable relaxation the nominal disparity levels and, consequently, does not attain the desired fairness levels even within 2 s.d.s. (see Table A) and first row of Table D
In contrast, having moderately coarse grid works well even with 25 and 50 grid points, method achieves similar accuracy performance and fairness attainment for 100 grid points, while exhibiting considerably shorter computational runtimes.
This demonstrates that, though our method is susceptible to overly granular grids (e.g.. = 10), a moderately spaced grid performs well in practice and is comparable with the denser grids considered
in $5
A.6.4 EXPERIMENTAL RESULTS FOR INCREMENTAL EXPANSION POLICY
We present experimental results on COMPAS using A-incremental expansion policy (cf. $A.2.II. Similar to 5.2 consider the setting of multiple linear fractional constraints, except now
42

---

Published as a conference paper at ICLR 2026
ROC-F CPU Runtimes vs Grid Size
ROCF-LE LF
5000
3675 52 1591.78
4000
Seconds
3000
2000
764.11 2 261.66
738 28 # 45.50
1000
52. 52.48 = 2.75
100
Grid Size
Figure 3: CPU runtime (mean + s.d., seconds) for ACSIncome ([A|=5) across various grid sizes. The grid size refers the number of equidistantly spaced points searched over the outer grid search of Algorithm As $.2 the disparities 6copp 6pp and OFOR
oyoR-parity parity are controlled at level 0.10 for our method ROCF-LF.
Table 9: Summary statistics feasibility guard triggers of Regi onSearch-PG (Algorithm for nominal disparity levels considered in $.2 across various grid sizes; p is the proportion of runs and y is the average expansion factor a with s.d.
Grid size
ROCF-LF
ROCF-LF
10
1.00
1.23 0.01
25
0.88
1.08 + 0.01
50
0.72
1.04 0.01
100
0.64
1.04 0.01
wrap an additive expansion policy around our main region search procedure (Algorithml 2 using increments of Δrop le-2 and App 5e-3 and constraining the active faimess metrics of 500pp Spp, and 6FOR at nominal levels 0.05, 0.05 and 0.10, respectively.
As seen in Table 10 we often need to expand the nominal disparity levels m = 5 times in order the final attained disparities, we also see that the disparity
to find a feasible operating point. of predictive parity disparity is lower than that of equality of opportunity, indicating that our non- uniform expansion policy is working as intended.
We would like to note that ORACLE's failure achieve the nominal equality of opportunity dis- parity is not the result of any inherent shortcoming of its methodology, but rather serves to illus- trate the difficulty of simultaneously attaining nontrivial level of approximate fairesss for multiple linear/linaar- fractional laratttoonaaaa constraints for this dataset (see also the discussion $5.2 and additional experimental results in (A.6).
This preliminary result showcases how practitioners can employ intuitive, non-uniform expansion policies using method, for which have proposed and demonstrated the efficacy of simple additive, incremental procedure.
A.6.5 EXPERIMENTAL RESULTS ON
SET
This section reports the performance of our method along with baselines for various experiments on the processocss set. By design, method ROCF-LF attains either the nominal disparity levels when the feasibility guard (cf. ŞA.2.I) is not activated, or a minimal relaxation of the nominal disparity level when the guard is activated; Tables 11 and 12
43

---

Published as a conference paper at ICLR 2026
Table 10: Performance on test set for COMPAS with A-incremental expansion policy with Årop 0.01, App 0.005 (see $A.2.1) The disparities ÓrOpp. opp and ÓFOR are controlled levels 0.05, 0.05, and 0.10, respectively, whenever they are active. Interv. is the empirical interven- tion rate on the test set (see Definition A.3). Cells in green indicate that the fairness constraint is satisfied within two standard deviations at the nominal level, whereas cells in red indicate violation. baselines.
Entries the Oracle rows are shaded in lighter colors denote that they are not practically feasible
COMPAS
Method
Acc
EOpp
PFg
FOR
Intery.
Baseline
0.68 0.01
0.28 0.05
0.27 0.05
0.20 1: 0.05
0.07 1 0.04
0.03 1 0.02
0.00 1. 0.00
Oracle
0.63 1 0.04
0.18 0.05
0.10 0.02
0.19 0.10
0.07
1 0.01
0.10
1 0.00
N/A
ROCF-LF (ours)
0.62 0.04
0.18 0.06
0.12 + 0.04
0.19 0.11
0.08 + 0.04
0.10
= 0.05
0.03 + 0.02
I.PP.EOpP
0.67 0.01
0.10 0.04
0.09 0.04
0.04 0.03
0.14 1: 0.03
0.08 : 0.03
0.00 1 0.00
Performance the post-processing set for (A) COMPAS ((AI=2). (B) ACSIncome ((Al=2), and (C) ACSIncome ([A]=5). The disparities ôoe, ÓBOpp drzy dir are controlled at level 0.05 whenever they are active. Interv. is the empirical intervention rate on the post pros-pprcsssing set (see Definition [.3) Cells in green indicate that the fairness constraint is satisfied within two standard deviations at level 0.05, whereas cells in red indicate violation. Entries in the Oracle rows are shaded in lighter colors to denote that they are not practically feasible baselines.
Table 11:
COMPAS
Method
Acc
DP
EOpp
PFq
PP
FOR
Intery.
Baseline
0.68 i 0.01
0.27
0.04
0.26 1. 0.06
0.19 1 0.05
0.07 1 0.04
0.03 1: 0.02
0,00 1: 0.00
Oracle
0.62 0.02
0.05
0.01
0.03 0.01
0.05 0.01
0.05 + 0.00
0.15 = 0.02
N/A
ROCF-LF (ours)
0.62 0.02
0.01 0.05
0.03 0.02
0.05 4 0.02
0.05 + 0.02
0.16 - 0.03
0.06 + 0.02
MFOpt
0.63 0.01
0.26
0.04
0.24
+ 0.05
0.21 0:04
+
META
0.51 0.02
0.05 0.17
0.05 0.15
0.04 + 0.18
0.06 + 0.19
0.15 = 0.04
0.00 + 0.00
LPP-DP
0.67 0.00
0.05 0.00
0.04 0.00
0.03 0.00
0.16 0.00
0.00
0.00
LPP-EO
0.67 0.00
0.10 0.00
0.09 0.00
0.03 = 0.00
0.14 + 0.00
0.07 = 0.00
0.00 + 0.00
(B) ACSIncome (|A(=2)
Method
Acc
DP
EOpp
PEg
PP
FOR
Interv.
Baseline
0.79 + 0.01
0.17 = 0.03
0.14 + 0.02
0.08 + 0.03
0.05 + 0.01
0.06 = 0.02
0.00 + 0.00
Oracle
0.75 10000
0.05
0.00
0.05
0.000
0.02
4 0.00
0.08 4 0.00
0.14 0.00
NIA
ROCF-LF (ours)
0.75 0.00
0.05
= 0.00
0.05
+ 0.00
0.02
= 0.00
0.05 + 0.00
0.14 = 0.00
0.02 + 0.00
MFOpt
0..00
0.20 0.00
0.09
0.15 0.00
0.06 0.00
= 0.00
0.06 E 0.00
META
0.79 0.00
0.11 0.02
0.03 0.02
0.03 a 0.01
0.11 + 0.01
0.09 2 0.01
0.00 a 0.00
LPP-DP
0.78 0.00
0.05 0.00
0.00
0.00
E
EO
0.78 1. 0.00
0.10 0.00
0.03 1 0.00
0.03 1 0.00
0.10 1 0.00
0.09 1: 0.00
0.00 1. 0.00
(C) ACSTncome
(A=5)
Method
Acc
EOpp
PEg
PP
FOR
Interv.
Baseline
0.79 + 0.00
0.25
0.01
0.24 + 0.02
0.10 + 0.02
0.23 + 0.02
0.08 = 0.01
0.00 + 0.00
Oracle
0.69 1'0.01
0.05
1 0.00
0.00
1 0.00
0.03
16000
0.05
1 0.00
0.23 1 0.01
NUA
ROCF-LF (ours)
0.69 0.01
0.05
- 0.00
0.05
+ 0.00
0.03
= 0.01
0.05 + 0.00
0.23 = 0.01
0.03 + 0.01
LPP-DP
0.78 0.00
0.05 0.00
0.07
0.00
0.09
0.00
0.35 - 0.00
0.15 = 0.00
0.00 I
LPP-EO
0.78 1: 0.00
0.12 0.00
0.06 + 0.00
0.06 + 0.00
0.33 + 0.00
0.13 = 0.00
0.00 1 0.00
44

---

Published as a conference paper at ICLR 2026
Performance on the post- pooteproeessing set for (A) COMPAS (|A|=2), (B) ACSIncome ((Al=2), and (C) ACSIncome ([4|=5).. The disparities Stupp 6ep and ŌFσ are controlled at level 0. 0.10 whenever they are active. Interv. is the empirical intervention rate on the post procepsros set (see Definition A.3 Cells in green indicate that the fairness constraint is satisfied within two standard deviations at level 0.10, whereas cells in red indicate violation. Entries in the Oracle feasible baselines.
Table 12:
shaded in lighter colors denote that they practically
(A) COMPAS
Method
Acc
DP
EOpp
PFq
PP
FOR
Intery.
Baseline
0.68 0.01
0.27
0.04
0.26
0.06
0.19 + 0.05
0.07 + 0.04
0.03 : 0.02
0.00 + 0.00
Oracle
0.65 0.04
0.15
0.04
0.10
0.00
0.12
0.08
0.10
+ 0.01
0.08
= 0.02
N/A
ROCF-LF (ours)
0.65
0.04
0.15
0.04
0.10 0.01
0.12 1 0.09
0.10
0.01
0.09
0.03
0.01 1 0.02
LPP.EOpp
0.67 0.01
0.15 0.01
0.13 0.03
0.07
0.02
0.12
0.03
0.06
0.03
0.00 1 0.00
(B) ACSIncome
([A|=2)
Method
Acc
EOpp
PFg
PP
FOR
Interv.
Baseline
0.79 0.01
0.17 0.03
0.88
0.03
+
Oracle
0.79 + 0.00
0.16 0.00
0.10 + 0.00
0.00
0.07
0.01
0.07 + 0.01
0.07 = 0.00
N/A
ROCF-LF (ours)
1
LPP PPpp
0.79 1 0.01
0.14 0.01
0.09 1 0.01
0.05 i 0.02
0.08 1 0.01
0.07 0.01
0.00 1 0.00
(C) ACSIncome
(A=5)
Method
Acc
EOpp
PEg
PP
FOR
Interv.
Baseline
0.78 +: 0.01
0.25 0.01
0.24 + 0.03
0.10 +: 0.02
0.23 + 0.03
0.08 = 0.01
0.00 + 0.00
Oracle
0.57 0.02
0.48
0.10 0.01
0.57 0.05
0.10+
0.10
NIA
ROCF-LE (ours)
0,56 1 0.02
0.09
0.10
0.58
0.10
0.10
0.05 + 0.01
LPP-EOpP
0.79 0.00
0.13 0.01
0.11 00001
0.06 0.001
0.31 + 0.02
0.12 0.01
0.00
45


Reviews:
[{"review_id": "wckIfr6Ks6", "reviewer": "Reviewer_YVAP", "summary": "This paper presents ROCF (Fair Classification via Operating Characteristic Feasibility Regions), a post-processing framework for achieving approximate group fairness under multiple constraints such as demographic parity (DP), equalized odds (EO), and predictive parity (PP).\nInstead of retraining models, the method intervenes directly on the operating characteristics (TPR/FPR) of a pre-trained classifier. It identifies feasible fairness-adjusted points using each group’s convex hull and post-processes predictions to reach those points. The approach extends to multiple protected attributes and supports linear-fractional fairness metrics.\nExperiments on COMPAS and ACSIncome show that ROCF achieves approximate fairness across several criteria with minimal accuracy loss and few label interventions, outperforming prior post-processing baselines (Celis et al., 2019; Hsu et al., 2022).", "questions": "Complexity and scalability: How does the computational cost of the grid search scale with the number of fairness constraints and protected groups?\nGeneralization beyond binary tasks: Could the ROC-based formulation extend to multi-class or regression settings, or is it inherently tied to binary classification?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Novel geometric perspective: Optimizing fairness directly in ROC space via convex hulls is elegant and intuitive.\nHandles multiple fairness criteria: Supports several linear and fractional constraints simultaneously, a limitation of most existing post-processing methods.\nPractical deployment path: Works on top of pre-trained models, making it applicable when retraining is infeasible.", "weaknesses": "Limited dataset diversity: Evaluation on only two benchmark datasets limits generalization; larger and more complex domains should be tested.\nScalability concerns: The grid search may be expensive when handling many groups or fairness constraints.\nSensitivity to data size: Since ROCF relies on convex hull estimation, small or noisy samples may affect feasibility, but this is not quantified.\nPost-processing limitations: As with all post-processing methods, bias in the learned representation remains unaddressed.", "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": "F1HpNLhaVY", "reviewer": "Reviewer_v8n8", "summary": "This paper introduces a method for jointly optimizing multiple fairness constraints under approximation thresholds. The method leverages the ROC to satisfy linear fractional fairness constraints, and provides extensive analytical results on the framework.\n\nThe authors empirically evaluate on standard fairness datasets, and demonstrate near-oracle performance over multiple fairness measures, with a principled and flexible delta-approximate fairness.", "questions": "1. Does this method suffer from sparse values in the grid search? i.e. is the only trade-off runtime, or does the result fail on overly-granular grids?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The model is well-motivated and the authors situate their work well in the introduction. The application of the ROC is intuitive to a novice reader at a conceptual level.\n\n2. The method evaluates quite well. The method consistently achieves near-oracle performance over multiple fairness measures. The authors evaluate over standard fairness-related datasets which is fine\n\n3. The method allows an intuitive approximate fairness threshold delta, which allows adaptation to the application. Furthermore, the adaptive feasibility search allows this parameter to be over-constrained while still providing a solution in a principled manner .", "weaknesses": "1. Overall, the paper is challenging for a general AI researcher reader, and likely challenging for a fair AI researcher. I don't have a great recommendation for improving this, as the analytical results are necessarily technical. \n\n2. I have low-confidence in verifying the proofs in the paper, particularly Thm 4.1 in A.4.1. Therefore I defer to other reviewers on correctness and evaluate as if true. \n- I believe the proof requires a Q_k construction, which is deferred to A.5.1. This should be moved up in the proof context\n\n3. The method is sensitive to the cardinality of the region search grid. Finding the appropriate scale on this approximation seems to be challenging. The authors address this in terms of runtime, but does an overly-granular grid produces issues of over-sparsity?", "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": "i8N32hVwNI", "reviewer": "Reviewer_nf54", "summary": "This paper proposes post-processing algorithms for achieving (multiple) group fairness (criteria simultaneously), covering criteria that can be expressed in linear or linear-fractional forms: this covers SP, EO, TPR/FPR parity, and predictive rate parity.  The focus is on binary classification and the attribute-aware setting (sensitive attribute can be used explicitly as input to the classifier/post-processor).\n\nGiven the ROC (i.e., feasible TPR-FPR tradeoffs) of the Bayes optimal score function:\n\n1. With a reformulation trick, the authors show that, if the \"centroid\" of the group statistics of the fair classifier is known, then the fairness criteria can be expressed as linear constraints in terms of the group-conditional TPR and FPR.\n2. If the performance of the classifier is a function of the TPR and FPR (e.g., accuracy), then the optimal fair classifier is fully characterized by its TPR-FPR tradeoff.\n\nWith these two facts,\n\n1. The authors proposed a bi-level optimization procedure where the outer layer sweeps over the possible centroids, and the inner layer solves the fair classification with the linear constraints as a linear program. Finally, it returns the one with the centroids that leads to the best performance.\n2. To return a classifier achieving a specific TPR-FPR tradeoff, two methods are proposed: one is based on randomly interpolating a thresholded classifier (which lies on the boundary of the ROC) and a input-independent randomized classifier (which lies on the diagonal), and another which is based on combining thresholding and label flipping.", "questions": "N/A", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- To the reviewer's knowledge, this is the first paper proposing a post-processing based method for achieving fair classification on linear (SP, EO, TPR/FPR) and linear-fractional (predictive rate equality) fairness constraints simultaneously.\n- Experiment results show good empirical performance.\n- The reviewer finds the reformulation trick for \"linearizing\" the linear-fractional constraints interesting, and could be also be applied to the more general attribute-blind and multi-class setting (for representing the optimal fair classifier).", "weaknesses": "- The fact that a bi-level optimization procedure involving a grid search for finding the optimal \"centroid\" is required is a bit dissatisfying, and suggests that the proposed algorithm may be hard to scale to more general settings.\n- The lack of a sample complexity analysis (probably about the same as fitting a linear model with $O(K)$ parameters), and an error propagation analysis: if the upstream score function is non-Bayes-optimal, how much would it hurt performance and fairness?", "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": "i87hItidrD", "reviewer": "Reviewer_keRQ", "summary": "This paper introduces ROCF, a post-processing framework that works directly in rate space, leveraging each group’s ROC convex hull to find realizable regions that satisfy multiple fairness constraints (including linear-fractional ones such as PPV parity). The authors propose (i) a centroid-based linearization of linear-fractional constraints that yields a linear program for any fixed centroid, and (ii) a feasibility guard that minimally relaxes constraints when the desired fairness region is infeasible. Empirical evaluation on COMPAS and ACSIncome shows that ROCF achieves approximate DP, EO, PP, and FOR with minimal intervention rate and only small accuracy drops. The method unifies a variety of fairness notions within one efficient LP-based framework.", "questions": "Centroid grid sensitivity: How fine must the centroid grid be to approximate the true feasible region? Any quantitative link between grid resolution and sub-optimality?\n\nDenominator constraints: How are $\\epsilon_k$ parameters for denominator stability selected, and do they materially alter fairness feasibility for small groups?\n\nConstraint prioritization: Could the feasibility guard relax only selected constraints (e.g., PP but not EO)? A weighted relaxation could make the framework more flexible.\n\nCalibration drift: How robust is ROCF if the base model’s score calibration shifts between training and deployment?\n\nMulti-attribute scalability: How does ROCF scale when there are many protected attributes or intersecting subgroups?\n\nDataset expansion: Adding a credit-risk or medical dataset would make results more convincing and highlight ROCF’s linear-fractional handling.\n\nAntiDiagonal vs. LabelFlipping: Under what conditions does one yield strictly fewer interventions? An ablation or theorem would clarify.\n\nOracle definition: Clarify what makes the Oracle baseline “infeasible in practice” (e.g., requiring group labels at test time).", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Originality: Nice and elegant reframing of fairness post-processing as optimization directly over operating characteristics; the centroid-based linearization for fractional constraints is novel and mathematically neat.\n\nQuality: Sound algorithmic development and proofs; empirical evidence across fairness notions and with multiple random seeds; good engineering of a “feasibility guard” to guarantee graceful degradation.\n\nClarity: Clearly written and well-modularized. Rate-space figures and Algorithm listings support understanding.\n\nSignificance: Offers a practical, easily implementable method to jointly achieve fairness notions that were previously handled separately. Useful for any group dealing with fairness auditing or deployment.", "weaknesses": "Limited scope and datasets: Evaluation restricted to two small tabular datasets (COMPAS, ACSIncome). \n\nBinary-only setting: The framework and proofs assume binary classification with continuous scores; no discussion of multi-class, where scores live in the probabilistic simplex. The assumption that scores are continuous (“ties broken deterministically”) could fail in applications.\n\nBaselines: Comparisons are mostly to post-processing methods (Hardt et al. 2016, Hsu et al. 2022); in-processing reduction approaches (Agarwal et al. 2018) could be included for a broader view.\n\nFeasibility guard uniformity: The relaxation of fairness constraints is uniform; no discussion of prioritizing one constraint (e.g., EO) over another (e.g., PP). This limits interpretability of fairness–utility trade-offs.\n\nIntervention optimality: The AntiDiagonal and LabelFlipping constructions are heuristically minimal but not formally proven globally optimal; empirical stability to hull noise could be further demonstrated.", "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)