Certifying Some Distributional Fairness with Subpopulation Decomposition
Authors: Mintong Kang
Linyi Li
Maurice Weber
Yang Liu
Ce Zhang
Bo Li
Venue: NeurIPS 2022 Accept (2022)
Keywords: Certifying Fairness
fairness constrained distribution
distribution shifts

Abstract: Extensive efforts have been made to understand and improve the fairness of machine learning models based on observational metrics, especially in high-stakes domains such as medical insurance, education, and hiring decisions. However, there is a lack of certified fairness considering the end-to-end performance of an ML model. In this paper, we first formulate the certified fairness of an ML model trained on a given data distribution as an optimization problem based on the model performance loss bound on a fairness constrained distribution, which is within bounded distributional distance with the training distribution. We then propose a general fairness certification framework and instantiate it for both sensitive shifting and general shifting scenarios. In particular, we propose to solve the optimization problem by decomposing the original data distribution into analytical subpopulations and proving the convexity of the subproblems to solve them. We evaluate our certified fairness on six real-world datasets and show that our certification is tight in the sensitive shifting scenario and provides non-trivial certification under general shifting. Our framework is flexible to integrate additional non-skewness constraints and we show that it provides even tighter certification under different real-world scenarios. We also compare our certified fairness bound with adapted existing distributional robustness bounds on Gaussian data and demonstrate that our method is significantly tighter.

Certifying Some Distributional Fairness with Subpopulation Decomposition
Mintong Kang
Linyi Li UIUC
Maurice Weber ETH Zurich
UIUC
mintong20illimois.. edu
linyi20illinois edu
maurice weber@inf ethz
Yang Liu UC Santa Cruz
Ce Zhang ETH Zurich
Bo Li UIUC
yangliuQucsc.
ce ne.zhan@@inff .ttz. ch
1bo@illinois edu
Abstract
Extensive efforts have been made understand and improve the fairness of ma- chine learning models based on different fairness measurement metrics, especially in high-stakes domains such as medical insurance, education, and hiring decisions. fairness However, there is a lack of fairess on the end-to-end performance of an ML model. In this paper, we first formulate the certified fairness of an ML model trained on a given data distribution as an optimization problem based on the model performance loss bound on a fairness constrained distribution, which is within bounded distributional distance with the training distribution. We then propose a general fairness certification framework and instantiate it for both sensitive shifting and general shifting scenarios. In particular, we propose to solve the optimization problem by decomposing the original data distribution into analytical subpopula- tions and proving the convexity of the sub-problems to solve them. We evaluate our certified fairness on six real-world datasets and show that our certification tight in the sensitive shifting scenario and provides non-trivial certification under general shifting. Our framework flexible to integrate additional non-skewness constraints and we show that it provides even tighter certification under different real-world scenarios. We also compare our certified fairness bound with adapted existing distributional robustness bounds on Gaussian data and demonstrate that our method is significantly tighter.
Introduction
As machine learning (ML) has become ubiquitous A4 18
13 fairness ML have attracted
automated hiring systems biased lot of attention from different perspectives. For instance, Different approaches have been proposed
towards males due to gender imbalanced training data 3
improve ML fairness, such as regularized training
2
30), disentanglement
duality 44), low-rank matrix factorization [34] and distribution alignment
4 20 53
In addition to existing approaches that evaluate faimess, is important and challenging provide certification for ML fairness. Recent studies have explored the certified fair representation of ML 39 4 33). However, there lacks certified fairness the predictions of end-to-end ML model trained on an arbitrary data distribution. In addition, current fairness literature mainly focuses on training ML model a potentially (am)balanced distribution and evaluate its performance in target domain measured by existing statistical fairness definitions [17 20 Since in practice these selected target domains encode certain forms of unfairness of their own (e-g., sampling bias), the evaluation would be more informative if we can evaluate and certify faireess of an ML model
"The first two authors contributed equally.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

on an objective distribution. Taking these factors into account, in this work, we aim to provide the first definition of certified fairness given an ML model and training distribution by bounding its end-to-end performance on an benjettive,aireen
constrained distribution. In particular, we define certified fairness as the worst-case upper bound of the MI. prediction loss on a fairness constrained test distribution 2, which is within bounded distance to the training distribution P. For example, for an ML model of crime rate prediction, we can define the model performance as the expected loss within a specific age group. Suppose the model is deployed in a fair environment that does not deviate too much from the training, our fairness certificate can guarantee that the loss of crime rate prediction for particular age group is upper bounded, which is an indicator of model's faimess.
We mainly focus on the base rate condition as the faimess constraint for Q. We prove that our certified fairness based on a base rate constrained distribution will imply other faimess metrics, such as demographie parity (DP) and equalized odds (EO). Moreover, our framework flexible integrate other fairness constraints into Q. We consider two scenarios: (1) sensitive shifting where only the joint distribution of sensitive attribute and label can be changed when optimizing Q; and (2) general shifting where everything including the conditioned distribution of non-sensitive attributes can be changed. We then propose an effective cenetiieeaarreee fairness certification framework to compute the certificate.
In our fairness certification framework, we first formulate the problem as constrained optimization, where the fairees constrained distribution is encoded by base rate constraints. Our key technique is to decompose both training and the faimess constrained test distributions to several subpopulations based on sensitive attributes and target labels, which can be used encode the base rate constraints. With such a decomposition, in sensitive shifting, we can decompose the distance constraint to subpopulation ratio constraints and prove the transformed low-dimensional optimization problem convex and thus efficiently solvable. In general shifting case, we propose to solve it based on divide and conquer: we first partition the feasible space into different subpopulations, then optimize the density (ratio) of each subpopulation, apply relaxation on each subpopulation finally prove the convexity of the sub-problems with respect to other low-dimensional variables. Our framework is applicable for any black-box ML models and any distributional shifts bounded by the Hellinger distance. which is a type of --divergence studied in the literature
sub-problem, and
25 15
To demonstrate the effectiveness and tightness of our framework, we evaluate our fairness bounds on six real- world fairness related datasets [3 2 19 We show that our certificate is tight under different scenarios. In addition, we verify that our framework is flexible to integrate additional constraints on Q and evaluate the certified fairness with additional non-skewness constraints, with which our fairness certificate is tighter. Finally, as the first work on certifying fairess of an end-to-end ML model, we adapt existing distributional robustness bound [ for comparison to provide more intuition. Note that directly integrating the fairness constraint to the existing distributional robustness bound is challenging, which is one of the main contributions for our framework. We show that with the fairness constraints and our effective solution, our bound is strictly tighter.
Technical Contributions, In this work, we take the first attempt towards formulating and computing the certified fairness on an end-to-end MI. model, which is trained on a given distribution. We make contributions on both theoretical and empirical fronts.
1. We formulate the certified fairness of an end-to-end ML model trained given distribution P as the worst-case upper bound of its prediction loss on a fairesss constrained distribution Q which is within bounded distributional distance with P.
2. We propose an effective fairness certification framework that simulates the problem as constrained optimization and solve it by decomposing the training and fairness constrained test distributions into subpopulations and proving the convexity of each sub-problem to solve it.
3. We evaluate our certified faimess on six real-world datasets to show its tightness and scalability. We also show that with additional distribution constraints on Q, our certification would be tighter.
4. We show that our bound is strictly tighter than adapted distributional robustness bound on Gaussian dataset due to the added fairness constraints and our effective optimization approach.
Related Work Fairness in ML can be generally categorized into individual faimess and group fairesss. Individual faimess guarantees that similar inputs should lead to similar outputs for a model and it is analyzed with optimization approaches 49 33 and different types of relaxations [21]] Group fairness indicates to measure the independence between the sensitive features and model prediction, the separation which means that the sensitive features are statistically independent of model prediction given the target label, and the sufficiency which means that the sensitive features are
2

---

statistically independent of the target label given the model prediction 27 Different approaches are proposed to analyze group fairness via static analysis [6], interactive computation AT. and probabilistic approaches [1 10, [. In addition, there is a line of work trying to certify the fair representation 39
9 the authors have provided bounds for how group fairness transfers subject to bounded distribution shift. Our certified fairness differs from existing work from three perspectives: I) we provide fairness certification considering the end-to-end model performance instead of the representation level, 2) we define and certify fairness based on a fairness constrained distribution which implies other fairness notions, and 3) our certified fairness can be computed for any black-bos. box models trained on an arbitrary given data distribution.
2 Certified Fairness Based on Fairness Constrained Distribution
In this section, we first introduce preliminaries, and then propose the definition of certified fairness based on a bounded fairness constrained distribution, which to the best of our knowledge is the first formal fairness certification end-to-end model prediction. We also show that our proposed certified fairness relates to established fairess definitions in the literature.
Notations. We consider the general classification setting: we denote by X' and 3 [C] the feature space and labels, [C] := 21, ..... ,C). ho: X' - A represents mapping function parameterized with 0 E O and e: A x y - R_ is non-negative loss function such as cross-entropy loss. Within feature space X. we identify a sensitive or protected attribute X₂ that takes a finite number of values: X, [S]. i.e. for any X E X, X, E [S].
Definition 1 (Base Rate). Given distribution P. supported over X' x V. the base rate for sensitive attribute value E [S] with respect to label E [C] is b2,, = Pr(x,r)-[Y = y X, s].
Given the definition of base rate, we define a fair base rute distribution (in short as fair distribution). Definition (Fair Base Rate Distribution). A distribution P supported over x y is fair base rate distribution if and only if for any label [C), the base rate bb is equal across all 8 E [S], i.e., Vi E [S], Vj E [5],6,,, = 6l.y
Remark. In the literature, the concepts of fairness are usually directly defined at the model predic- tion level, where the criterion is whether the model prediction is fair against individual attribute changes 39 36 50) or fair at population level [54]. In this work, to certify the fairness of model prediction, we define fairness constrained distribution on which we will certify the model predic- tion (e.g., bound the prediction error), rather than relying on the empirical fairness evaluation. In particular, we first define the fairness constrained distribution through the lens of base rate parity, i.e. the probability of being any class should be independent of sensitive attribute values, and then define the certified fairness of a given model based on its performance on the fairness constrained distribution as we will show next.
The choice of focusing on fair base rate may look restrictive but its definition aligns very well with the celebrated fairness definition Demographic Parity [5I] which promotes that Pr[ho(X) (X) = 1|X, i] = Pr (x( fair base rate will relate directly to Pr[ha
1|X, = jl. In this case, the prediction performance of he on Q with
1|X, t]. Secondly, under certain popular data generation process, the base rate sufficiently encodes the differences in distributions and a fair base rate will imply a homogeneous (therefore equal or "fair") distribution over X, Y: consider when Pr(X = y, X, i) is the same across different group X,. Then Pr(X, YIX, i) is simply linear combination of basis distributions Pr(X|Y= = y, X, = i). and the difference between different groups' joint distribution of X, Y is fully characterized by the difference in base rate Pr(Y = y X)). This assumption will greatly enable trackable analysis and is not an uncommon modeling choice in
the recent discussion of fairness when distribution shifts [22 37
2.1 Certified Fairness
Now we are ready to define the fairness certification based on the optimized fairness constrained distribution. We define the certification under two data generation scenarios: general shift- ing and sensitive shifting. In particular, consider the data generative model Pr(X.. X., Y) Pr(Y)) Pr(X.IY) Pr(X.lY, X.). where X,, and X, represent the non-sensitive and sensitive features, respectively. If all three random variables on the RHS are allowed to change, we call general shifting; if both Pr(Y) and Pr(X,]Y) are allowed to change to ensure the fair base rate (Def.)
3

---

while Pr X,) is the same across different groups, we call it sensitive shifting. In Section 3 we will introduce our certification framework for both scenarios.
Problem 1 (Certified Fairnsss with General Shifting). Given a training distribution P supported on X' x V, a model ho).)) trained on P. and distribution distance bound >> 0, we call E IR a faimess certificate with general shifting, if upper bounds
max elxx) (X),Y) S.A. dist 2) P. Q
2 is a fair distribution,
where dist( is predetermined distribution distance metric.
In the above definition, we define the fairness certificate the upper bound of the model's loss among all fair base rate distributions Q within a bounded distance from P. Besides the bounded distance constraint dP Q) S p. there is other constraint between P and Q so this satisfies "general shifting". This bounded distance constraint, parameterized by a tunable parameter p. ensures that the test distribution should not be too far away from the training. In practice, the model he may represent a DNN whose complex analytical forms would pose challenges for solving Problem [ As a result, as we will show in Equation ② we can query some statistics of hg trained on P constraints to characterize ha, and thus compute the upper bound certificate.
The feasible region of optimization problem might be empty if the distance bound is too small, and thus we cannot provide fairness certification this scenario, indicating that there no nearby fair distribution and thus the fairness of the model trained on the highly "unfaired" distribution is generally low. In other words, if the training distribution P is unfair (typical case) and there is no feasible fairness constrained distribution Q within a small distance to P, faimesss cannot be certified.
This definition follows the intuition of typical real-world scenarios: The real-world training dataset is usually biased due to the limitation in data curation and collection processes, which causes the model be unfair. Thus, when the trained models are evaluated on the real-world fairness constrained test distribution or ideal fair distribution, we hope that the model does not encode the training bias which would lead to low test performance. That is to say, the model performance on fairness constrained distribution is indeed a witness of the model's 's intrinsic fairness.
We can further constrain that the subpopulation of P and Q parameterized by X, and Y does not change, which results in the following "sensitive shifting" faimess certification.
Problem 2 (Certified Fairness with Sensitive Shifting). Under the same setting as Problem we call & a fairness certificate against sensitive shifting, if upper bounds
max (xx.rr=l(((h(()),,
s.t. dist 2) S. Pr,, Q.yy Vs (5), (C], Q a fair distribution,
where Paa and 2x.y are the subpopulations of P and Q on the support {(X,Y) Y): : X E x,X, = Y.YY= = y) respectively, and dist(.,.) is predetermined distribution distance metric.
The definition adds an additional constraint between and Q that each subpopulation, partitioned by the sensitive attribute X, and label Y, does not change. This constraint corresponds to the scenario where the distribution shifting between training and test distributions only happens on the proportions of different sensitive attributes and labels, and within each subpopulation the shifting is negligible.
In addition, to model the real-world test distribution, we may further request that the test distribution
Q is not too skewed regarding the sensitive attribute X, by adding constraint (T). We will show that this constraint can also be integrated into our fairness certification framework flexibly in Section
Wi E [S] Vj E [S], (x.Y)<e [X, = (x.Pr_ [X, = S As-
Connections to Other Fairness Measurements. Though not explicitly stated, goal of certifying
the performance on fair distribution Q relates to certifying established faimess definitions in the literature. Consider the following example: Suppose Problem i feasible and returns a classifier hg that achieves certified fairness per group and per label class / := Pr(x.y>~ehho(X + Y|Y y. X, = i| < e on Q. We will then have the following proposition:
Proposition 1. he achieves e-Demographic Parity (DP) (5I) and e-Equalized Odds (EO) 18
eDDP: [P)) _|X, d] - (x) 1|X, j] S e, Vi,j.
4

---

c-EO: [Pro[ha(X) = = =, (X) 1|Y = v. 5]1 Vy,yi
Remark. The detailed proof is omitted to appendix Ca (1) When e = 0, Proposition can guarantee perfect DP and EO simultaneously. We achieve so because we evaluate with fair distribution Q, where "fair distribution" stands for "equalized base rate" and according to [23 Theorem 1.1, page 5] both DP and EO are achievable for this fair distribution. This observation in fact motivated us to identify the fair distribution Q for the evaluation since it is this fair distribution that allows the fairness measures to hold at the same time. Therefore, another way to interpret our framework is: given a model, we provide a framework that certifies worst-case "unfairness" bound in the context where perfect fairness is achievable. Such a worse-case bound serves as the gap to a perfectly fair model and could be a good indicator of the model's 's faimess level. (2) In practice, c is not necessarily zero. Therefore, Proposition] [ only provides e-BO, instead of absolute DP and EO. The approximate fairness guarantee renders our results more general. Meanwhile, there is higher flexiblity in simultaneously satisfying approximate fairness metrics (for example when DP = O, but EO = 6, which is plausible for proper range of epsilon, regardless of the distribution Q being fair or not). But again, similar to (1), e-DP and e-EO can be achieved at the same time easily since the test distribution satisfies base rate parity.
upper lower bound of DP and EO, namely c-DP and
The bounds in Proposition 1 are tight. Consider the distribution Q with binary classes and binary sensitive attributes (i.e., Y. X, E 1)). When the distribution Q and classifier hg satisfy the conditions that Pho + Y = 0, X, 0] c, (rogho(XX) * Y|Y 0, X, = 1] = 0 and
Pro[Y = 0| = 1, = 1] = 0, the bounds in Proposition are tight. From Pro [Y = 0 =
1, Pror 1] = 0, we can observe that e-DP is equivalent e-EO. From Pro[ha + Y|Y
0, = 0 = =e, e,Prolha(X)
+ Y = 0, X, 1] O and Tralba(X) +YY O, =
= Prolha(X) (X)
0, X. = i] for i E {0. 13. we know that e-BO holds with tightness since
| (X) = =1|Y = O. = 0] - Pro (X) = 1| = O, 1]] = c. To this point, we show
that both bounds in Proposition are tight.
3 Fairness Certification Framework
We will introduce our fairness certification framework which efficiently computes the fairness certificate defined in Section 2. We first introduce our framework for sensitive shifting (Problem 2
which is less complex and shows our core methodology, then general shifting case (Problem DD
Our framework focuses on using the Hellinger distance to bound the distributional distance in Problems and 2 The Hellinger distance [P, Q) is defined in Def. 3 (in Appendix B. The Hellinger distance has some nice properties, e.g., (P, 2) E [0, 1]. and H 2) = O if and only if p Q and the maximum value of is attained when P and Q have disjoint support. The Hellinger distance is a type of f-divergences which are widely studied in ML distributional robustness literature 47 [4] and in the context of distributionally robust optimization | 25 15). Also, using Hellinger distance enables our certification framework to generalize to total variation distance (or statistic distance) 8(P, o directly with the connection, H (P, Q) I 8(P, Q) I /2H (P, Q) (145, Equation 1). We leave the extension of our framework other distance metries future work.
3.1 Core Idea: Subpopulation Decomposition
The core idea in our framework is (finite) subpopulation decomposition. Consider a generic optimiza- tion problem for computing the loss upper bound on a constrained test distribution 2, given training distribution P and trained model (-).,, we first characterize model feg(-) based on some statistics, e.g., mean and variance for loss of the model: ha(+) satisfies e, (P, he) < U/. 1 < j - L. Then we characterize the properties (e.g.. fair base rate) of the test distribution Q: 9 < Mj. 1 S S M.
As result, we can upper bound the loss of he h-)-) on Q as the following optimization:
max T (X(hox))) V)] s.t. H(P, 2 S P. e, ho) S S, Vj E [7.) (2) S uy Vj E [M] Q.0
Now we decompose the space Z = X y to N partitions: 2 W 2i, where Z is the support of both P and Q. Then, we denote P conditioned on Z, by P. and similarly Q conditioned on Z, by
Q, As a result, we can write P = EiENN P.P; and Q = EiEINT q, Since P is known, p, 's are known. In contrast, both Q, and q 's are optimizable. Our key observation is that N
H(P, 2) Sp + - p² (1 - H (P., 2.) 50
(3)
28(P, Q) = SEP (P()) - 2(A) where F is o algebra of subsets of the sample space f2
5

---

which leads to the following theorem. Theorem 1. The following constrained optimization upper bounds Equation
max 2;,0
Σ 2
(4a)
s.t. 1 1-p -- Σ VP - p.) SO,
(4b)
N
2(P, WEIN E =1 2 20 IE P: ViE (M],
(4c)
<)P(PNN (Pi)EENN ho) S vj E [L], d'((ssheNN; (aree( S uf [M], (4d)
if (P, ho) vi implies ((PP))EE tui ha) 0/j for any j [T] and gj (2) Vj
implies of(( (e))en))))))))))) S u for any j E [M].
In Problem the challenge is to deal with the fair base rate constraint. Our core technique in Thm. is subpopulation decomposition. At a high level, thanks to the disjoint support among different This equation gives
equivalence relationship between distribution-level (namely, P and ②) distance constraint and subpopulation-level (namely, P; 's and Q s) distance constraint. As result, as decision variables as in Equation (4b) and then imposing the unity constraint (Equation (4c) get Thm. We provide detailed proof in Appendix C.2 Although the optimization problem
subpopulations, we get Equation
rewrite the original problem 2 using sub-population
(Equation (4) may look more complicated then the original Equation ( this optimization sim-
upper bound each subpopulation loss Exx,y>~o (X), Y)] individually, and hence makes the whole optimization tractable.
plifies the challenging fair base rate constraint, allows
3.2 Certified Fairness with Sensitive Shifting
For the sensitive shifting case, we instantiate Thm. and obtain the following fairness certificate.
Theorem 2. Given distance bound p > O, the following constrained optimization, which is convex. when feasible, provides a tight fairness certificate for Problem
5
c
max Ra-"y
Eerg
s.t. Σ
k
==
Σ
rg
1,
k. Vs E ry 2 0 Vy E [C].
1=1 1=1
y=1
8
Va.khir S 0,,
where Eay == (oxx))w..,,(((ha Y'] and Pay == Pr(x.yepl|x, = = s, = y] are constants.
Proof sketch. We decompose distribution P and Q to Pa. 2. 's and Qe.y according to their sensitive attribute and label values. In sensitive shifting, Pr(X, [Y, X,) is fixed, i.e., Pa.y Qu.y- which means E(x,y)~Q... [X), = Ex.y and Ps. = H(P.. s.y. Qx.g) = We plug these properties into Thm. Then, denoting {s.y to PI(X,r)~ X, = s, y]. we can represent the fairness
constraint in Def. 2 as 400.30 = [S. s=1 (5,30 [Eg (30.3) for any E [S] and yo E [C]. Next, we parameterize (s.y with K. Such parameterization simplifies the fairness constraint and allow us to prove the convexity of the resulting optimization. Since all the constraints are encoded equivalently. the problem formulation provides tight certification. Detailed proof Appendix
As Thm. suggests, we can exploit the expectation information Ez,y ExX,)~ [6 (X), Y)] and density information Pa,y Pr(x,))~p(XX XX = s, Y = y) of each P's subpopulation to provide a tight fairness certificate in sensitive shifting. The convex optimization problem with (S + C) variables can be efficiently solved by off- the-hhh--hlf packages.
3.3 Certified Fairness with General Shifting
For the general shifting case, we leverage Thm. and the parameterization trick Js.9 = kery used in Thm. 2 to reduce Problem to the following constrained optimization.

---

Lemma 3.1. Given distance bound > O, the following constrained optimization, when feasible, provides tight fairness certificate for Problem !
max Ras P.PE.N
k Bx ((hb))))))(((()))))))))))))))))) (((bo(X).
(6a)
==
C Σ y=1
s.t.
Σ
1,
rgy = hg 20 0 A E (S),
To 20 0 by E [C],
(6h)
Vaaghiaty - -p2.)) 21 1
(6c)
y=1
H(P.. 2a.v) S PaN Vs |5), E (0).
(6d)
where Pa.y == Px,, = = y) is fixed constant. The Рaa and Qny are the subpopulations of P and @ on the support {(X, Y): X E X, = S, = y) respectively.
Proof sketch. We show that Equation 6bb) ensures a parameterization of (s.y Pr(x,Y)ee| =
s, Y = y] that satisfies fairness constraints on Q. Then, leveraging Thm. I we prove that the constrained optimization provides fairness certificate. Since all the constraints are either kept or equivalently encoded, this resulting certification is tight. Detailed proof Appendix C.4
Q
Now the main obstacle is to solve the non-convex optimization in Problem 6 Here, as the first
step, we upper bound the loss of h.).) within each shifted subpopulation Q. i.c., upper bound Then, we apply
Ex (X),, Y)] in Equation (6a by Thm. 4 in Appendix B.2
variable transformations to make some decision variables convex. For the remaining decision variables, we observe that they are non-convex but bounded. Hence, we propose the technique of grid-based sub- problem construction. Concretely, we divide the feasible region regarding non-convex variables into small grids and consider the optimization problem in each region individually, For each sub-problem, we relax the objective by pushing the values of non-convex variables to the boundary of the current grid and then solve the convex optimization sub-problems. Concretely, the following theorem states our computable certificate for Problem
[ with detailed proof in Appendix
Theorem 3. If for any s E [S] and y [Y], H(P Qo.y) S % and ((ho(X), s M. given a distance bound > O. for any region granularity T E N4, the following expression provides a faimess certificate for Problem 7
==
max
C
(11*
i, -1
i
12
Jy
G
where
(7)
T
T
T
T
C
(
[Ke, s=1, (1re 701
max Zs,9
loty (EEN + Cou)+ + kery (Ea.y + Co.z)
+ 2k.T VV 1z,0(1 Tz Vvo BeTuTee(Cazpl - -Coo)
(8a)
8 1
s.t.
Σ
ΣE EesI, ΣT
(8b)
Σ
Poiykssgge 21 (1- (1- S Jay S1 Ae ( (C),
(8c)
y=1
where (+)+ = 0), (c)- = minf;00:: Fx, =
V..y =
V.. V ((x,r)-P,, ((hgg(X),, Ps.y Pr(X.Y)~lXX, = =,Y = y). C..y = M ES,y M-
and 12.y =1 1 (1 + (M- - 2//.)//V/.))) Equation 77 only takes C 's value when it is feasible, and each C queried by Equation 7 is convex optimization.
Implications. Thm. B provides a faimess certificate for Problem I Junder two assumptions: (1) The loss function is bounded (by M). This assumption holds for several typical losses such as 0-1 loss and JSD loss. (2) The distribution shift between training and test distribution within each subpopulation is bounded by Ts.y where Ty.yy determined by the model's statistics on P. practice, this additional distance bound assumption generally holds, since Je,y > p for common choices of p.
7

---

In Thm. we exploit three types of statistics of h-)-) on P to compute the faimess certificates: the expectation E,,y ((x,Y) (((g Y)), the variance V.,y = (x.)))>PP.. [e(hg (X), Y)],
and the density Px.g Pr(x,y)~ [X, s, Y y/. all of which are the subpopulation level and high-confidence estimation of them based on finite samples are tractable (Section 3.4)
Using Thm. El after determining the region granularity T, we can provide faimess certificate for Problem 1 by solving TS convex optimization problems, each of which has SC' decision variables. Note that the computation cost independent of hig and therefore we can numerically compute the certificate for large DNN models used in practice. Specifically, when S = 2 (binary sensitive attribute) or C = 2 (binary classification) which is common in the fairness evaluation setting, can construct the region for only one dimension k1 or 71, and use 1 1--k k1 or 1 - rı for the other dimension. Thus, for the typical setting S 2, C 2, we only need to solve T convex optimization problems.
Note that for Problem 2 our certificate in Thm. 2 tight, whereas for Problem | our certificate in Thm.
B is not. This is because in Problem [ extra distribution shift exists within each subpopulation, i.e. X X,) changes from P to Q, and to bound such shift, we need to leverage Thm. 2.2 in 47 which has no tightness guarantee. Future work providing tighter bounds than - can be seamlessly incorporated into our framework to tighten our fairness certificate for Problem
3.4 Dealing with Finite Sampling Error
In Section 2 and Section 3.3 we present Thm. 2 and Thm. 3 that provide computable fairness
certificates for sensitive shifting and general shifting scenarios respectively. In these theorems, we need to know the quantities related to the training distribution and trained P and model h-):
Es.y
(X),o(X), Y),, VaN = (X,Y)~Pa.
V (X.))-P.
(X))o(X), Y) Pa.v (X.Y) (X.P)
Pr [X, =x, = vl. (9)
3.3 further requires Cs.y and Ts.y which are functions of Es,g and V. However, a practical challenge is that common training distributions do not have an analytical expression that allows us to precisely compute these quantities. Indeed, we only have access finite number of individually drawn samples, i.c., the training dataset, from P. Thus, we will provide high-confidence bounds for Es.y. V.yy. and Ps.y in Lemma (stated in Appendix D.I.
Section
For Thm. we can replace Es.y in the objective by the upper bounds of E.,y and replace the concrete quantities of Ps.y by interval constraints and the unit constraint >> M,, Ps.y = 1, which again yields a convex optimization that can be effectively solved. For Thm. 3 we compute the confidence intervals of Cs.y and p.,y. then plug either the lower bounds or the upper bounds the objective (a) based on the coefficient, and finally replace the concrete quantities of Px.y by interval constraints and the unit constraint Σ, Ey Ps.y = 1. The resulting optimization proved to be convex and provides an upper bound for any possible values of E..y. Ve.g. and Ps.y within the confidence intervals. We defer the statement of Thm. - and Thm. B considerig finite sampling error to Appendix D.2] To this point, we have presented our framework for computing high- confideeecee fairness certificates given access to model ha (-) and a finite number of samples drawn from P.
Experiments
In this section, we evaluate the certified fairness under both sensitive shifting and general shifting scenarios on six real-world datasets. We observe that under the sensitive shifting, our certified fairness bound is right (Section 4.Tpp p; while the bound is less tight under general shifting (Section 4.2) which depends on the tightness of generalization bounds within each subpopulation (details in Section 5.3)
In addition, we show that our certification framework can flexibly integrate more constraints on Q. leading to tighter fairness certification (Section 4.3). Finally, we compare our certified fairness bound with existing distributional robustness bound 43 (section 4.4). since both consider a shifted distribution while our bound is optimized with an additional faimess constraint which is challenging to be directly integrated to the existing distributional robustness optimization. We show that with the fairness constraint and our optimization approach, our bound is much tighter.
Dataset & Model. We validate our certified fairness on six real-world datasets: Adult B. Com- pas (2) Health [19], Lawschool 48] Crime 3 and German 3 Details on the datasets and data
processing steps are provided in Appendix F.
Following the standard setup of fairness evaluation in 31 42 we consider the scenario that the sensitive attributes and labels take
the literature [39 38
binary values. The ReLU network composed of 2 hidden layers of size 20 is used for all datasets.
8

---

ADULT
COMPAS
HEALTH
LAW SCHOOL
0.6
0.4
0.4
Erro
0.4
0.2
0.2
0.2
0.00
0.0
0.2
0.4
0.6
0.0
1.0
1.00
1.0
BCE Loss
0.6
0.5
0.75
0.5
0.4
0.50
0.2
0.0
0.0
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
Hellinger Distance
Hellinger Distance
Hellinger Distance
Hellinger Distance
- Certified Fainess
X
EpL((h(), Y]
Eg(e(h(X) Y)]
Figure I: Certified faimess with sensitive shifting. Grey points are results on generated distributions (Q) and the black line is our fairness certificate based on Thm. We observe that our fairesss certificate is usually tight.
Fairness Certification. We perform vanilla model training and then leverage our fairness cer- tification framework to calculate the faimesss certificate. Concretely, input the trained model information on P and the framework would output the fairness certification for both sensitive shifting and general shifting scenarios following Thm. 2 and Thm. respectively.
Code, model, and all experimental data are publicly available at https://githht: com/ Se--secure/Crttfieed--eeee -aiiedd-Faarees
4.1 Certified Fairness with Sensitive Shifting
Generating Fair Distributions. To evaluate how well our certificates capture the fairness risk in practice, we compare our certification bound with the empirical loss evaluated on randomly generated 30, 000 fairness constrained distributions Q shifted from P. The detailed steps for generating fairness constrained distributions subpopulation divided by the sensitive attribute and label does not change (Section 2.1). we tune only the portion of each subpopulation gs.y satisfying the base rate fairness constraint, and then sample from each subpopulation of P individually according to the proportion 9s.y. In this way, our protocols can generate distributions with different combinations of subpopulation portions. the classifier is biased toward one subpopulation (i.e.. it achieves high accuracy in the group but low accuracy in others), the worst-case accuracy on generated distribution is low since the portion of the biased subpopulation in the generated distribution can be low; in contrast, fair classifier which performs uniformly well for each group can achieve high worst-case accuracy (high certified fairness). Therefore, we believe that protocols can demonstrate real-world training distribution bias as well as reflect the model's unfairness and certification tightness real-workd scenarios.
are provided in Appendix E.2 Under sensitive shifting, since each
Results. We report the classification error (Error) and BCE loss as the evaluation metric. Figure | illustrates the certified fairness on Adult, Compas, Health, and Lawschool under sensitive shifting. More results on two relatively small datasets (Crime, German) are shown in Appendix E.5 From the results, we see that our certified fairness is tight in practice.
4.2 Certified Fairness with General Shifting
In the general shifting scenario, we similarly randomly generate 30, 000 fair distributions Q shifted from P. Different from sensitive shifting, the distribution conditioned on sensitive attribute X, and label Y can also change in this scenario. Therefore, we construct another distribution Q' disjoint with P on non-sensitive attributes and mix P and Q' in each subpopulation individually guided by mixing parameters satisfying fair base rate constraint. Detailed generation steps are given in Appendix E.2 Since the fairness certification for general shifting requires bounded loss, we select classification error (Error) and Jensen- Shannon Jensen-Shannon loss (JSD Loss) as the evaluation metric. Figure 2 illustrates the certified fairness with classification error metric under general shifting. Results of JSD loss and more results on two relatively small datasets (Crime, German) are in Appendix E.5
4.3 Certified Fairness with Additional Non-Skewness Constraints
In Section 2.1
we discussed that to represent different real-world scenarios we can add more constraints such as Equation T to prevent the skewness of Q, which can flexibly incorporated into our certificate framework. Concretely, for sensitive shifting, we only need to add one more

---

ADULT
COMPAS
HEALTH
LAW SCHOOL
1.0
1.0
1.0
1.0
Error
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
Hellinger Distance
Hellinger Distance
Hellinger Distance
Hellinger Distance
Certified Fainess
X
(p((( Y)
(ol((h()). Y)]
Figure 2: Certified fairness with general shifting. Grey points are results on generated distributions (Q) and the We observe that our faimess certificate is non-trivial.
black line is our fairness certificate based on Thm.
B
Claveffeattonn Error
0.40
Classiiiaatin Error
0.6
1.0
WRM Bound
0.35
0.4
JSD Log
0.8
Certified Fxirness
0.6
0.30
0.25
4. =1
0.2
A.
A
0.2
0.4
0.20
4==0
0.0
0.05
0.10 0.15 0.20 0.25 0.30 Hellinger Distance
0.10
0.15
0.20
0.25
0.30
0.0
0.2
0.4
0.6
0.8
Hellinger Distance
Distriburion Shift cc-norm llöll;
(a) Sentitive Shifting
(b) General Shifting
(c) Comparison with WRM
Figure 3: Certified fairness with additional non-skewness constraints on Adult dataset is shown in (a) (b).
A. controls the skewness of Q ( (r(xxy)~o = 0] Pr [X, = 1] S A.). More analysis in
Section 4.3 In (c), we compare our certified fairness bound with the distributional robustness bound 4
More
analysis in Section 4.4
box constrain 0.5 4,/2 k. S 0.5 + A../2 where A, is parameter controlling the skewness of Q. which still guarantees convexity. For general shifting, we only need to modify the region partition stepa. where we split [0.5 / 0.5 + A. x 22 instead of (0, 1]. The certification results with additional constraints are in Figures ((a) and bbb which suggests that if the added constraints are strict (i.e., smaller A.). the bound is tighter. More constraints w.r.t. labels can also be handled by our framework and the corresponding results as well as results on more datasets are Appendix E.6
4.4 Comparison with Distributional Robustness Bound
To the best of our knowledge, there is no existing work providing feriiiedaairrnss on the end-to-ent model performance. Thus, we try to compare our bound with the distributional robustness bound since both consider certain distribution shifts. However, it challenging to directly integrate the fairness constraints into existing bounds. Therefore, we compare with the state-of-the-arr distributional robustness certification WRM the fairness constraint. For fair comparison, we construct a synthetic dataset following 43 on which there is a one-to-one correspondence between the Hellinger and Wasserstein distance used by WRM. We randomly select one dimension as the sensitive attribute. Since WRM has additional assumptions on smoothness of models and losses, we use JSD loss and a small ELU network with 2 hidden layers of size 4 and 2 following their setting. More implementation details are in Appendix DE Results in Figure ( suggest that 1) our certified fairness bound is much tighter than WRM given the additional fairness distribution constraint and our optimization framework: 2) with additional fairness constraint, our certificate problem could be infeasible under very small distribution distances since the fairness constrained distribution Q does not exist the skewed original distribution P: 3) with the fairness constraint, we provide non-trivial fairness certification bound even when the distribution shift is large.
4 which solves the similar optimization problem as ours except for
5 Conclusion
In this paper, we provide the first fairness certification on end-to-end model performance, based on fairness constrained distribution which has bounded distribution distance from the training distribution. We show that our fairness certification has strong connections with existing fairness notions such as group parity, and we provide an effective framework to calculate the certification under different scenarios. We provide both theoretical and empirical analysis of our fairness certification.
Acknowledgements.. MK, LL, and BL are partially supported by the NSF grant No. 1910100,,, NSF CNS No.2046726, C3 AI, and the Alfred P. Sloan Foundation. YL is partially supported by the NSF grants IIS-2143895 and I04-000000.
'Note that such modification is only viable when sentive attributes take binary values, which is the typical scenario in the literature of faimeess evaluation 39
R8
31
[p
10

---

References
[1] Aws Albarghouthi, Loris D' Antoni, Samuel Drews, and Aditya Nori. Fairsquare: proba- bilistic verification of program fairesss. Proceedings of the ACM on Programming Languages, 1(00PSLA):1-3) 2017.
[2] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. In Ethics of Data and Analytics, pages 254-264. Auerbach Publications, 2016.
[3] Arthur Asuncion and David Newman. Uci machine learning repository, 2007.
[4] Mislav Balunović, Anian Ruoss, and Martin Vechev. Fair normalizing flows. arXiv preprint arXiv:2106.05937. 2021.
[5] Solon Barocas and Andrew D Selbst. Big data's disparate impact. Calif. L. Rev., 104:671, 2016.
[6] Osbert Bastani, Xin Zhang, and Armando Solar-Lezama. Probabilistic verification of fair- ness properties via concentration. Proceedings of the ACM on Programming Languages, 3(00PSLA):1-27) 2019
[7] Aharon Ben-Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2):341-357, 2013.
[8] Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. Fairness in criminal justice risk assessments: The state of the art. Sociological Methods Research, 50(1):3 44, 2021.
[9] Yatong Chen, Reilly Raab, Jialu Wang, and Yang Liu. Faimess transferability subject to bounded distribution shift, Advances in Neural Information Processing Systems, 2022.
[10] YooJung Choi, Meihua Dang, and Guy Van den Broeck. Group fairness by probabilistic modeling with latent fair decisions. arXiv preprint 1rX1v:2009.00031, 2020.
[11] Alexandra Chouldechova. Fair prediction with disparate impact: study of bias in recidivism prediction instruments. Big data, 5(2):153-163, 2017.
[12] Elliot Creager, David Madras, Jörn-Henrik Jacobsen, Marissa Weis, Kevin Swersky, Toniann Pitassi, and Richard Zemel. Flexibly fair representation learning by disentanglement. In International conference on machine learning, pages 1436-1445. PMLR, 2019.
[13] Amit Datta, Michael Carl Tschantz, and Anupam Datta. Automated experiments on ad privacy settings. Proceedings on privacy enhancing technologies, 2015(1);92-112, 2015.
[14] John Duchi and Hongseok Namkoong. Variance based regularization with convex objectives. The Journal of Machine Learning Research, 20(1):2450-2504 2019.
[15] John Duchi, Peter W Glynn, and Hongseok Namkoong. Statistics of robust optimization: A generalized empirical likelihood approach. Mathematics of Operationss Research, 2021.
[16] Harrison Edwards and Amos Storkey. Censoring representations with adversary. arXiv preprint
2015.
[17] Jeffrey A Gliner. Reviewing qualitative research: Proposed criteria for fairness and rigor. The Occupational Therapy Journal of Research, 14(2):78-99) 1994.
[18] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances neural information processing systems, 29, 2016.
[19] Kaggle Inc. Heritage health prize kaggle. https::/ htmps::/wwww... http://wwwwkggl..cmoooo c/hhp 2022.
[20] Xisen Jin, Francesco Barbieri, Brendan Kennedy, Aida Mostafazadeh Davani, Leonardo Neves, and Xiang Ren. On transferability of bias mitigation effects language model fine-tuning. arXiv preprint arXiv:2010.12866 2020.

---

[21] Philips George John, Deepak Vijaykeerthy, and Diptikalyan Saha. Verifying individual fairness in machine learning models. In Conference on Uncertainty in Artificial Intelligence, pages 749-758. PMIR, 2020.
[22] Thomas Kehrenberg, Myles Bartlett, Oliver Thomas, and Novi Quadrianto. Null-sampling for interpretable and fair representations. In European Conference on Computer Vision, pages 565-580. Springer, 2020.
[23] Jon Kleinberg. Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. arXiv preprint arXiv: 1609. 05807, 2016.
[24] Himabindu Lakkaraju. Jon Kleinberg, Jure Leskovec, Jens Ludwig, and Sendhil Mullainathan. The selective labels problem: Evaluating algorithmic predictions the presence of unobserv- ables. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 275-284,20 2017.
[25] Henry Lam. Robust sensitivity analysis for stochastic systems. Mathematics of Operations Research, (1(4):1248-12) 1275, 2016.
[26] Jiachun Liao, Chong Huang, Peter Kairouz, and Lalitha Sankar. Learning generative adversarial representations (gap) under fairness and censoring constraints. arXiv preprint 100.04,1,, 1, 2019.
[27] Lydia T Liu, Max Simchowitz, and Moritz Hardt. The implicit fairness criterion of unconstrained learning. In International Conference on Machine Learning, pages 4051 4051-4060. PMLR, 2019.
[28] Francesco Locatello, Gabriele Abbati, Thomas Rainforth, Stefan Bauer, Bernhard Schölkopf, and Olivier Bachem. On the fairness of disentangled representations. Advances in Neural Information Processing Systems, 32, 2019.
[29] Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard Zemel. The variational 2015.
fair autoencoder. arXiv preprint 151
[30] David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. International Conference on Machine Learning, pages 3384 3393. PMLR, 2018
[31] Subha Maity, Debarghya Mukherjee, Mikhail Yurochkin, and Yuekai Sun. Does enforcing fairness mitigate biases caused by subpopulation shift? In M. Ranzato, A. Beygelzimer, Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances Neural Information Processing Systems, volume 34, pages 25773-25784. Curran Associates, Inc., 2021.
[32] Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.3744 2009.
[33] Daniel McNamara, Cheng Soon Ong. and Robert C. Williamson. Costs and benefits of fair representation learning. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Sociery, AIES '19, page 263-270. New York, NY, USA, 2019. Association for Computing Machinery.
[34] Luca Oneto, Michele Donini, Massimiliano Pontil, and Andreas Maurer. Learning fair and trans- ferable representations with theoretical guarantees. In 2020 IEEE 7th International Conference on Data Science and Advanced Analytics (DSAA), pages 30-39, 2020.
[35] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[36] Momchil Peychev, Anian Ruoss, Mislav Balunović, Maximilian Baader, and Martin Vechev. Latent space smoothing for individually fair representations. arXiv preprint arXiv: 13650. 2021.
12

---

[37] Reilly Raab and Yang Liu. Unintended selection: Persistent qualification rate disparities and interventions. Advances Neural Information Processing Systems, 34, 2021.
[38] Yuji Roh, Kangwook Lee, Steven Whang, and Changho Suh. Sample selection for fair and robust training. Advances in Neural Information Processing Systems, 34, 2021.
[39] Anian Ruoss, Mislav Balunovic, Mare Fischer, and Martin Vechev. Learning certified individu- ally fair representations. Advances in Neural Information Processing Systems, 33:7584-7596. 2020.
[40] Mhd Hasan Sarhan, Nassir Navab, Abouzar Eslami, and Shadi Albarqouni. Fairness by learning orthogonal disentangled representations. In European Conference on Computer Vision, pages 746-761. Springer, 2020.
[41] Shahar Segal, Yossi Adi, Benny Pinkas, Carsten Baum, Chaya Ganesh, and Joseph Keshet. Fairness in the eyes of the data: Certifying machine- models. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pages 226-935,222 2021.
[42] Shubhanshu Shekhar, Greg Fields, Mohammad Ghavamzadeh, and Tara Javidi. Adaptive sampling for minimax fair classification. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 24535-24544, Curran Associates, Inc., 2021.
[43] Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Certifying some dis- tributional robustness with principled adversarial training. arXiv preprint arXiv:/710. 10571, 2017.
[44] Jiaming Song, Pratyusha Kalluri, Aditya Grover, Shengjia Zhao, and Stefano Ermon. Learning controllable fair representations. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2164 2173. PMLR, 2019.
[45] Ton Steerneman. On the total variation and hellinger distance between signed measures; an application to product measures. Proceedings of the American Mathematical Society, 88(4):684 688, 1983.
[46] Caterina Urban, Maria Christakis, Valentin Wüstholz, and Fuyuan Zhang, Perfectly parallel fairness certification of neural networks. Proceedings of the ACM on Programming Languages, 4(00PSLA):1-30, 2020.
[47] Maurice Weber, Linyi Li, Boxin Wang, Zhikuan Zhao, Bo Li, and Ce Zhang. Certifying out-of-domain generalization for blackbox functions. In International Conference on Machine Learning. PMLR, 2022.
[48] Linda F Wightman. Lsac national longitudinal bar passage study. Isac research report series. Law School Admission Council, 1998.
[49] Robin Winter, Floriane Montanari, Frank Noé, and Djork-Aré Clevert. Learning continuous and data-driven molecular descriptors by translating equivalent chemical representations. Chemical science, 1696):669211700 2019.
[50] Samuel Yeom and Matt Fredrikson. Individual faimess revisited: Transferring techniques from adversarial robustness. arXiv preprint arXiv:2002.07738, 2020.
[51] Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork, Learning fair representa- tions. In International conference on machine learning, pages 325 333. PMLR, 2013.
[52] Xueru Zhang, Ruibo Tu, Yang Liu, Mingyan Liu, Hedvig Kjellstrom, Kun Zhang, and Cheng Zhang. How do fair decisions fare in long-term qualification? Advances Neural Information Processing Systems, 33:18457-18469 2020.
[53] Han Zhao, Amanda Coston, Tameem Adel, and Geoffrey J Gordon. Conditional learning of fair representations. arXiv preprint arXhv:1910.07112, 2019.
[54] Han Zhao and Geoff Gordon. Inherent tradeoffs in learning fair representations. Advances in neural information processing systems, 32, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes) We clearly specify the assumptions and application scopes, if exists, of all our results.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We discuss broader impacts in Appendix A
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] We include complete proof's for all results in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material
URL)? [Yes]
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] We include them in Appendix
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes] Indeed, we rigorously compute the confidence intervals due to the finite sampling (see Section 3.4) and guarantee that all fairness certificates reported in the paper holds with probability 2 90%.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We provide them in Appendix E.3
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material or URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [No] We only use public data.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] only use public data.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "rgez5fUgDMu", "reviewer": "Reviewer_iRnk", "summary": "In this paper, the authors propose the certified fairness problem under two kinds of distribution shifts, i.e., the sensitive shifting and the general shifting. They provide the fairness certification framework to deal with the problems. Theoretically, they achieve the upper bound for the two settings and the bound is tight for the sensitive shift setting. Finally, they conduct experiments on six real-world datasets to prove the effectiveness of the method.", "questions": "See details in the Strengths and Weaknesses section, especially the points in the Quality, and Significance parts.", "limitations": "More limitations are demonstrated in the Strengths and Weaknesses section.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality**\n\n\\+ The authors propose a new problem setting, i.e., the certified fairness problem, and develop non-trivial methods to deal with it.\n\n**Quality**\n\n\\+ The method provided in this paper is technically sound with detailed proof. The experiments are comprehensive.\n\n\\- The relationship between traditional fairness notions (e.g., DP and EO) and the proposed setting should be further discussed. It is well-known that common fairness notions can not be satisfied at the same time in non-trivial settings [1]. As a result, it is not clear why Proposition 1 could guarantee DP and EO simultaneously. More discussions of the tightness of the bounds in Proposition 1 are encouraged.\n\n**Clarity**\n\n\\+ The paper is generally well-written. Several small typos exist. For example\n - Line 40: \"other other\" --> \"other\"\n - Line 361: \"dimensio\" --> \"dimension\"\n\n**Significance**\n\n\\- My major concern is about the problem setting proposed in this paper. Fairness problems generally require that several specific statistics match among different subpopulations (e.g., DP and EO) or individuals, which is not the case proposed in this paper. As a result, I am not clear whether the proposed problem setting is practical and sound in real-world scenarios. It would be better if the authors provide real-world examples to demonstrate the soundness of the proposed problem setting.\n\n[1] Kleinberg, Jon, Sendhil Mullainathan, and Manish Raghavan. \"Inherent trade-offs in the fair determination of risk scores.\" arXiv preprint arXiv:1609.05807 (2016).", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OWMjtuH0ND", "reviewer": "Reviewer_qSEq", "summary": "The authors propose fairness certification on end-to-end model performance based on a fairness constrained distribution. ", "questions": "- How do you train a classifier on a distribution?\n- How do you get $ \\rho $ the distance between two distributions in practical datasets?\n- How do you differentiate between a fair and a non-fair distribution?", "limitations": "In my opinion, there is no negative societal impact of the paper.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n- The paper seems solid. \n\nWeakness: \n- The paper is too dense with notations. An illustrative example (perhaps, earlier in the paper) would improve readability.\n- Experimental results such as figures are narrowly explained.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6Ukdxh2Radz", "reviewer": "Reviewer_f4hd", "summary": "The paper proposes certified fairness as the worst case prediction loss on a distribution Q such that d(P,Q) \\leq \\rho, where P is the training distribution. The proposed definition is analyzed in two different cases (i) general shifting (ii) sensitive shifting\n", "questions": "Please explain key steps of the proof and add crucial details of experiments to the main paper.", "limitations": "yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nS1 The problem of studying fairness under distribution shift is an important topic.\n\nS2 Paper presents interesting ideas to bound loss for shifted distribution.\n\n\nW1 Theorem 1 is the main result, and it lacks any justification in the main paper. Theorem 2 uses thm 1 and its proof is not that interesting.\n\nW2 Please add more insights for the proof in the main paper and appendix. \n\nW3 Experiments: The process used to generate distribution shift is synthetic and highly specific. Please explain a high level summary of the steps taken and how it impacts the results.\n\nWhat is the solved used for the optimization problem? How much is the runtime?\n\nComparison with baselines: Please add a detailed comparison of the proposed approach with baselines and discuss advantages. Fig 3c is the only comparison it does not explain the reasons for difference in quality of different techniques.\n\nTypos:\nline 359: following following\nline 361: one dimensio \n\nOverall, the paper presents many interesting theoretical ideas but the empirical evidence is weak and presentation can be improved. ", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept