Certification of Distributional Individual Fairness
Authors: Matthew Robert Wicker
Vihari Piratla
Adrian Weller
Venue: NeurIPS 2023 poster (2023)
Keywords: Fairness
Individual Fairness
Deep Learning
Certification
Trustworthy ML
TL;DR: In this work, we provide novel certification for distributional individual fairness which is an important, practical notion of fairness.

Abstract: Providing formal guarantees of algorithmic fairness is of paramount importance to socially responsible deployment of machine learning algorithms. In this work, we study formal guarantees, i.e., certificates, for individual fairness (IF) of neural networks. We start by introducing a novel convex approximation of IF constraints that exponentially decreases the computational cost of providing formal guarantees of local individual fairness. We highlight that prior methods are constrained by their focus on global IF certification and can therefore only scale to models with a few dozen hidden neurons, thus limiting their practical impact. We propose to certify \textit{distributional} individual fairness which ensures that for a given empirical distribution and all distributions within a $\gamma$-Wasserstein ball, the neural network has guaranteed individually fair predictions. Leveraging developments in quasi-convex optimization, we provide novel and efficient certified bounds on distributional individual fairness and show that our method allows us to certify and regularize neural networks that are several orders of magnitude larger than those considered by prior works. Moreover, we study real-world distribution shifts and find our bounds to be a scalable, practical, and sound source of IF guarantees.

Certification of Distributional Individual Fairness
Matthew Wicker The Alan Turing Institute mwi mwickertuurng ac. uk
Vihari Piratia University of Cambridge vp4210cam ac uk
Adrian Weller University of Cambridge The Alan Turing Institute
Abstract
Providing formal guarantees of algorithmic fairness is of paramount importance to socially responsible deployment machine learning algorithms. In this work, we study formal guarantees, i.e., certificates, for individual fairness (IF) of neural networks. We start by introducing a novel convex approximation of IF constraints that exponentially decreases the computational cost of providing formal guarantees of local individual fairness. We highlight that prior methods are constrained by their focus on global IF certification and can therefore only scale models with a few dozen hidden neurons, thus limiting their practical impact. We propose to certify distributional individual fairness which ensures that for a given empirical distribution and all distributions within a y 77-Wasserstein ball, the neural network has guaranteed individually fair predictions. Leveraging developments in quasi-convex optimization, we provide novel and efficient certified bounds distributional individual fairness and show that our method allows us certify and regularize neural networks that are several orders of magnitude larger than those considered by prior works. Moreover, we study real-world distribution shifts and find our bounds to be a scalable, practical, and sound source of IF guarantees.
Introduction
There is growing concern about the potential of machine learning models perpetuate and amplify diserimination (Barocas & Selbst 2016). Machine learning algorithms have been put forward to automate decision making in variety of sainness-sensitive domains, such healthcare (Davenport
& Kalakota 2019). employment (Ding et al., [02I), and criminal justice (Dressel & Farid 2018
Zilka et al. 2022). It has been demonstrated that such models produce biased outcomes that unfairly
disadvantage certain individuals or groups Seyyed-Kalantar et al., 202 Yurochkin & Sun 2020
To combat this, there has been surge of interest in algorithmic fairness metrics (Mehrabi al. 2021
Fairness metrics provide practitioners with a means to quantify the extent of bias within model and
facilitate development heuristics for debiasing models (Madras et al. 2018 Yurochkin al. 2019).
However, relying solely on heuristic debiasing methods may not be satisfactory for justifying the deployment of machine learning models as they do not provide guarantees of fairness. To address this concern there has been a recent focus on certification approaches, which provide formal guarantees that a model adheres Shoukry 2022). Providing certified guarantees of fairness is of utmost importance stakeholders, and regulators formal assurances that the predictions a model align with a rigorous standards of fairness. These guarantees serve as powerful tool to promote trust, accountability, and ethical deployment of machine learning models.
specified fairness criterion (John et al.) 2020 Benussi et al., 2022, Khedr & offers users,
In this work, we study the problem of certifying individual fairness (IF) in neural networks (NNs). Individual fairesss enforees the intuitive property that given neural network issues similar predictions for all pairs of similar individuals (Dwork et al. 2012). Individuals are considered similar if they differ only with respect to protected attributes (e.g.. race, gender, or age) or features correlated with the protected attributes. This similarity is captured by fair distance metric which can be learned by
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

querying human experts or extracted from observed data (Mkhherjee et al. 2020). Given a NN and a fairness metric, recent works have established procedures for certifying that a NN conforms a given IF definition, which is crucial step in developing and deploying fair models (Benussi et al. 2022 Khedr Shoukry 2022). While current approaches to IF guarantees for NNs are effective for simple problems, they face scalability issues when dealing with NNs containing more than a few dozen neurons. This limitation is due to their emphasis on global individual fairness, which guarantees the IF property for every input within the NN's domain (Benussi et al., 2022 Khedr & Shoukry 2022). Although global IF certification is the gold standard, it places constraints on extreme outliers, such as ensuring loan decisions are fair to three-year-old billionaire applying for small business loan. Subsequently, as the dimension of the input space grows, solving an optimization problem that covers the entire domain becomes either impossible for current solvers to deal with or computationally prohibitive. On the other hand, distributional individual fairness (DIF), first proposed in Yurochkin al. (2019), enforces that a model's predictions are individually fair w.r.t a family of distributions that are within a ? Wasserstein ball of the empirical distribution over observed individuals. The focus on distributions removes the constraints unrealistic individuals while enforcing fairness on the relevant part of the input domain. As such, providing certification of DIF can provide strong guarantees of fairness that scale even relatively large neural network models. However, prior works in DIF focus only on heuristic debiasing techniques (Yurochkin et al. 2019).
In this work, we provide the first formal certificates of DIF. As it cannot be computed exactly, present a framework for bounding distributional individual fairness. We start by presenting a novel convex relaxation of local IF constraints, i.e., IF with respect to a single prediction. Our approach to local IF certification offers an exponential computational speed-up compared with prior approaches. Building this efficient bound, we are able propose optimization problem whose solution, attainable due to the problem's s quasi-convexig certified bounds can be easily incorporated as learning objectíve, enabling efficient individual fairness training. In a series of experiments, we establish that our method is able to certify that IF holds for meaningful, real-world distribution shifts. Further, our proposed regularization is able to certifiably fair neural networks that are two orders of magnitude larger than those considered in previous works in a fraction of the time. We highlight the following key contributions of this work:
produces sound certificates of DIF. Further, our
We prove a convex relaxation of local individual fairness, enabling exponentially more efficient local IF certification compared with prior mixed integer linear programming approaches.
We formulate a novel optimization approach to certificates of local and distribution individual fairness and leverage quasi-convex optimization to provide the first formal upper and lower bounds, i.e., certificates, on distributional individual fairness.
We empirically demonstrate the tightness of our distributional individual fairness guarantees compared with real-world distributional shifts, and demonstrate the considerable scalability benefits of our proposed method.
2 Related Work
Individual fairness, originally investigated by Dwork et al. (002)) establishes a powerful and intuitive notion of fairness. Subsequent works have focused on defining the individual fairness metrics
(Mukherjee et al. [2200] Yurochkin & Sun 2020), expanding the definition to new domains (Gupta &
Kamble 10 Xu et al. Doherty et al. 2002), and importantly, guaranteeing that a model conforms
to individual fairness (John et al. 2020; Ruoss et al. 2020: [enussi et al., 2022 Khedr & Shoukry
2022 Peychev et al.
2022). In (John et al. 2020) the authors consider relaxation of individual
Tairness and present methods to verify that it holds for linear classifiers. In YYom & Fredrikson] 2020
Peychev et al. 2022) the authors extend randomized smoothing to present statistical guarantees on individual fairness for neural networks. These guarantees are much weaker than the sound guarantees
presented in Benussi et al. (202);; Khedr & Shoukry (002)) which are based on mixed integer linear programming (MILP). Both of these methods focus solely on the global notion of individual fairnsss which proves to only scale to neural networks with a few dozen hidden neurons. Our work relaxes the need to certify a property globally allowing us to scale to neural networks that are orders of magnitude larger than what can be considered by prior works. Further, prior works have sought to debias models according an individual fairness criterion (Yurochkin et al., 2019| Benussi et al.] 2022 Khedr & Shoukry 2022). In Yurochkin et al. (2019) the authors present a method for debiased training relying on PGD which is insufficient for training a NN with strong fairness guarantees (Benussi et al. 2022

---

In (Benussi et al. 2022 Khedr& & Shoukry 2022) the authors use linear programming formulations of tairness during training which leads to strong IF guarantees but at a large computational cost and greatly limited scalability.
Distributional individual faimess was originally proposed by Yurochkin et al. (2019) and the impor- lance of distributional robustness of notions of fairness has been underscored in several recent woks
et al., 2019 Taskesen et al. 2020 Mukherjee et al. 2022). To the best of our knowledge, this work is the first that provides formal certificates that guarantee a model satisfies distributional individual fairness. We provide further discussion of works related to distributional robustness in Appendix
(Sagawa al. 2019; Sharifi-Malvajeer
3 Background
We consider a supervised learning scenario in which we have a set of feature-label pairs drawn from an unknown joint distribution {(x(1) y ~ (xx, y) with
R= and y RR We consider feed forward neural network (NN) as function f R - R&, parametrised by vector 0 E I.P
We define a local version of the individual fairness definition that is studied in (John et al.)
2020
Benussi et al., 2022) to evaluate algorithmic bias:
Definition 1. Local ô-e-Individual Fairness Given ô > 0 and 2 O. we say that 8e is locally individually fair (IF) with respect to fair distance dfair and imput x' iff:
Ya" s.1. diaaraa' , x²") I - (0' - (
For given value of 8 we use the notation I(f".I, 5) to denote the function that returns the largest value of e such that the local IF property holds. Further, I(J .x. 6) = O holds if a network is perfectly locally individually fair. Throughout the paper, will refer to the value the IF violation this the amount by which the perfect fairness property is violated.
Several methods have been investigated for crafting fair distance metries (Mukherjee al., 2020).
Methods in this work can flexibly handle majority of the currently proposed metrics. We discuss the particulars in Appendix D While certifying local IF sufficient for proving that a given prediction is fair w.r.t. a specific individual, it does not suffice as proof that the model will be fair for unseen individuals at deployment time. To this end. prior works have investigated a global individual fairness definition. Global e-8 individual fairness holds if and only if V'z E R" I(f" x. 5) c. However, global individual fairness is a strict constraint and training neural networks to satisfy global individual fairness comes at potentially prohibitive computational cost. For example, training a neural network with only 32 hidden units can take up to hours on multi-GPU machine (Benussi et 2022
Distributional Individual Fairness
In this section, we describe distributional individual fairness (DIF) notion that can ensure that neural networks are individually fair at deployment time while not incurring the considerable overhead of global training and certification methods. DIF ensures that individuals in the support of pD and distributions close to pa are treated fairly. To measure the distributions close to pe we consider the p- Wasserstein distance between distributions, Wp(P", .). Further, denote the ball of all distributions within 7 /- Wasserstein distance of po as By (P)). To abbreviate notation, we drop the p from the Wasserstein distance, noting that any integer p 2 1 can chosen.
Definition 2. Distributional ----e-Individual Fairness Given individual fairness parameters ō 0 and e 2 0, and distributional parameter 7y >> O, we say that 1e is distributionally individually fair (DIF) with respect to fair distance djair if and only if the following condition holds:
(Ea-Pr (I(", ((,,,,;;,)) s2, Se
sup (ro),
Intuitively, distributional individual fairness ensures that for all distributions Wasserstein ball around Po we maintain individual fairness on average. In Figure [ we visualize the difference between local, distributional, and global IF in toy two dimensional settings. Prior work that focuses on DIF only provides a heuristic method based the PGD attack to train debiased NNs and therefore
3

---

Coverage with Local IF Cuarantees
Coverage with Distrib. IF Guarantees
Coverage with Global IF Guarantees
certificate individuals
Carificate for ikaly insieduals consirintt natler ind vidiid
St constrait outler ind vilues
2-
2
-1-
-1
Empifical Distribution
Area covered certificate
Figure 1:
Using the halfmoons dataset we illustrate the benefits of DIF. Left: local IF does not do enough to provide guarantees individuals are likely to see. Right: Global IF provides strict constraint on anomalous points, leading to scalability issues. Center: Distributional IF covers likely individuals without over-constraining the problem leading scalable and reliable faimess guarantees.
provide formal guarantees (Yurochkin et al. 2019). Below state two key computational problems in the study of guarantees for distributional individual fairness:
Problem Certification of Distributional Individual Fairness: Given neural network, f and parameters 5 and 7, compute value such that c provably upper-bounds the left hand side of Equation An optimal certificate is the smallest such such that Equation ① holds.
The problem of certifying distributional individual fairness is critical to ensuring that the definition can used in practice as allows for regulators and auditors to have similar assurances to global individual fairness, but only on what is deemed to be the relevant portion of the input space as controlled by 7-
Problem 2. Distributionally Individually Fair Training: Given randomly initialized neural network, f and parameters å and 7 and a dataset drawn from pa, learn a neural network that approximately minimizes both the standard loss, L, and the DIF violation:
arg min Eo [C(f" 22, 22.)) + sup 8
(IF
Problem 2 is tantamount certified debiased training of neural network w.r.t the DIF definition. Certified debiasing places focus on formal guarantees that is not present in prior distributional individual fairness work.
5
Methodology
To address Problems and we start by providing a novel and efficient computation for certificates of local individual fairness. We then build on this efficient guarantee compute formal bounds and proposed regularizers for certified DIF training.
5.1 Certifying Local Individual Fairness
A key step in certification of distributional individual fairness is proving that given neural network satisfies local individual fairness i.e., Definition I While there are many methods for efficiently certifying local robustness properties, individual faimness must be certified w.r.t. ball of inputs whose shape and size is determined by duir- Existing works crafting individual fairness metrics Mahalanobis metrics express the fair distance between individuals, i.e., drar (zr, x²)
((x 5-1 y) where S is positive semi-den cemindefinite matrix mm order certify this more expressive class of specifications prior works use linear bounding techniques part of larger MILP formulation (Benussi al. 2022). this work, we show that one can in fact use exponentially more efficient bound propagation techniques developed for robustness certification to certify local individual fairness. In order do so, we provide the following bound that over-approximates the daai metric ball with an orthotope:

---

Theorem 5.1. Given a positive semi-definite matrix S E Rmxm feature vector x' E R and similarity theshold ö, all vectors x" E IR" satisfying ds(z', x²) S 8 are contained within the axis-aligned orthoe:
x' avd x' + +8vd
where d = diag(S), the vector containing the elements along the diagonal of S.
Theorem 5.1 holds as well for weighted Ep faimess metrics by setting the diagonal entries of S to the weights for metric provides an over approximation of the lo metric, which is also a valid over-approximation for any oc. The key consequence of Theorem 5.1 is that it directly enables efficient certification of local 6-e individual faireess. By over-approximatue an axis- axis-aligned orthotope, certification (Gowal et al.) 2018). Such methods allow us to take the given input interval and compute output bounds 1y" such that Væ E [x' - 8vd, x' + 5vd,, f (x) E 1y","") Subsequently, is clear to see that ly" - y²1 S e then we have certified that Va' E [r ōvd, x + σ
the fair distance with able to leverage the efficient methods developed for robustness
(x) - fd (x') I c which proves that local individual faimness holds according to Definition Computing such output bounds requires the computational complexity of two forward Mirman et al. (2118: Gowal et al. (2018). MILP approaches, on the other hand, requires complexity cubic in the largest number of neurons in a layer plus requires exponentially (in the number of problem variables) many MILP iterations Benussi et al. (022). We denote the function that takes the interval
corresponding to an individual x and value 8 and returns ly" -y² with the notation I(f 6). Given that bound propagation methods are sound, this value over-approximates the function in Definition] [ We emphasize that this approach to local faimess certification only takes two forward passes through the neural network, and can therefore be used as real-time decision support. We provide exact details of the computations of this upper bound in Appendix D By exploring the orthotope using methods developed for adversarial attacks, e.g., PGD (Madry et al. 2017), we can find an input x² that approximately maximizes | (x') (xx)), ) Subsequently, this value is valid lower-bound on the local IF violation around æ. As such, we will denote the value produced by PGD as I( f o)..
5.2 Certifying Distributional Individual Fairness
In this section we leverage the efficient upper bound on I(f", xx, 0) to prove bounds distributional individual fairness. We first highlight that computing the Wasserstein distance between two known distributions is non-trivial, and that in general we do not have access to the joint distribution po Thus, computing the Wasserstein ball around the data generating distribution is infeasible. To overcome this, as is traditionally done in the distributional robustness literature, we make the practical choice of certifying distributional individual fairness w.r.t. the empirical distribution 0o which is the probability mass function with uniform density over set of observed individuals (Sinha et al. 2017). While this introduces approximation in the inite-sample regime, we can bound the absolute difference between our estimate and the true value by using Chernoff's inequality, discussion in Appendix D Given the empirical distribution of individuals as well as parameters 7 and we pose optimization objective whose solution is the tightest value of satisfying Definition
max (L..))) T1
1 IIS
s.t.,
(())
P
(3)
Unfortunately, computing the optimal values of (09) even when is a non-convex optimization problem which is known to be NP-hard (Katz et al. 2017). We restate this optimization problem in terms of our bounds on I x, 8) to get formal lower (e) and upper (E) bounds on e* such that g
< < E.
5.3 Bounding Distributional Individual Fairness
Lower-bound on DIF Observe that any selection of (o(0) y satisfying the constraints represents feasible solution to the optimization problem and therefore a lower-bound on the maximization problem of interest. Thus, the lower-bound can be stated as:
max g)...
I(fo, (0) +000000 st.. 6(0)
R
Σ
||
ST
(4)
5

---

We can optimize this lower bound to be tight by observing that for any given i, the function I(f ,ا(()) + o is differentiable w.r.t. σl and is therefore amenable to first-order optimization. In particular, denote o6" to be randomly selected, feasible assignment of %0 then gradient ascent to find locally optimal assignment of ()()
(6) + ao
(1 I(f x(00 ((0)
where a is learning rate parameter. Subsequently, one could use a projection step in order to ensure that the constraint in Equation e is never violated. We note that this is a strict lower-bound unless the
Equation is solved exactly and I( [,] + +600) 0) I(f" x(1) + (()) ,8) for all i. Finally, we denote the computed solution to Equation as (f" X, 5) where y is the distributional parameter of the DIF specification and is the tensor containing the n individual feature vectors.
Upper-bound on DIF An upper- bound bound on the maximization in Equation i.c., غ 2 e*, constitutes certificate that the model provably satisfies distributional individual fairness for all greater than ē. Given that the optimization posed by Equation (3) is highly non-convex, searching for an optimal solution cannot be guaranteed converge globally without knowledge of global Lipschitz constants, which are difficult to compute efficiently for large NNs (Fazlyab et al. (019). Instead, we transform the optimization problem from one over the input space to the space of over-approximate local IF violations:
1 Σ 1=1
I(S d +0))) s.t. w E 1 Σ
E max
S
(5)
(L...
The key change the formulation is that we are no longer considering input transformations parameterized by z60), but instead consider averaapproi of all possible g(*) that within radiuu around the point (1) Moreover, it is clear that picking any assignment of the spt)
values will not constitute an upper- bound on the DIF violation. However, the global maximizing 3 formally
assignment of ((tt) values guaranteed to appr-appr the value of Equation stated in Theorem
Theorem 5.2. Given optimal assignment of {10(0) in Equation 5 the corresponding ī yi=1
sound upper-bound on the DIF violation of the model and therefore, is a certificate that no r- Wasserstien distribution shift can cause the individual fairness fainees of the model to exceed E.
The proof Theorem 5.2 is contained Appendix E.3 Given that the function I( x 5 + gp(i) continuous and monotonically increasing function, we have that the maximization problem in Equation (5) is quasi-convex. After proving this function also Hölder continuous, one can guarantee convergence in finite time to the optimal solution with bounded error using recent advancements in quasi-convex optimization (Hu et al. 2020 Agrawal & Boyd, 2020 Hu et al., 2022). As the global optimal solution is guaranteed to be upper- optimization to compute a certificate for the DIF property. In the Appendix we prove the Hölder continuity of I and conduct numerical convergence experiments to validate this theory. Given that the result of this optimization a certified upper bound on the DIF value, we denote its result with (f Xx 5) where 7 is the distributional parameter of the DIF formulation. While č is valid upper- bound on the DIF violation for the given dataset, in the low-data regime one may have nog-negli error due to poor approximation of the data distribution. The finite sample approximation error can be bounded by an application of Hoeffding's 's inequality as we state in Lemma !
the methods for quasi-convex
Lemma 1. Given an upper-bound ? (a global maximizing assignment to Equation (D)) we can bound the error induced by using finite sumple from above by That is, the estimate is within of the true expectution of with probability
as long as n is al least (-1/27") log(A/2)
5.4 Training Distributionally Individually Fair NNs
well-known that guarantees for certification agnostic neural networks can be vacuous (Gowal et al. 2018 Wicker et al. 2021). To combat this, strong empirical results have been obtained for neural networks trained with certified regularizers (Benussi al., 2022. Khedr & Shoukry 2022). In
this work, we have proposed three novel, differentiable bounds certified individual fairness. We

---

start by proposing a loss on certified local individual faimess similar to what is proposed in Benussi al. (2022) but substituted with our significantly more efficient interval bound procedure:
CymB = [(f ,xY) + aIo(f" (X,,
where a is weighting that trades off the fair loss with the standard loss. When y O, we recover
exactly a local constraint individual fairness for each 2!(() E X. By increasing the y from zero move from a local individual fairness constraint to a DIF constraint:
LE-IIF L("" X,Y) + aI,
where U-DIF stands for upper-boune on DIF. This loss comes at the cost of increased computational time, but is considerably stronger regularizer. In fact, given that the upper bound on certified DIF might be vacuous, and therefore difficult to optimize, at the start of training, we also propose training loss that optimizes the lower bound on DIF as may be empirically easier optimize and serves as middle ground between F-IBP and U-DIF:
DI = L(F X, +
6 Experiments
In this section we empirically validate our proposed method on variety of datasets. We first describe the datasets and metrics used. We then cover wide range of experimental ablations and validate bounds on world distribution shifts. We conclude the section with a study of how IF training impacts other notions of fairness !
Datasets We benchmark against the Adult, Credit, and German datasets from the UCI dataset repository (Dua & Graff 2017). The German or Satlog dataset predicts credit risk of individuals. The Credit dataset predicts an individual will default on their credit. The Adult dataset predicts an individuals income is greater than 50 thousand dollars. We additionally consider three datasets from the Folktables datasets, Income, Employ and Coverage, which are made up of millions of data points curated from the 2015 to 2021 US census data (Ding et al. (021). The Income dataset predicts if an individual makes more than 50 thousand US dollars, the Employ dataset predicts if an individual is employed, and the Coverage dataset predicts if an individual has health insurance. For each dataset gender is considered the protected attribute.
Metrics We consider four key metrics. For performance, we measure accuracy which is computed over the entire test-set. Next we consider the local fairness certificates (LFC), which taken as 1/n Σm= Io( 8). Next we consider the empirical distributional fairness certificate (E-DFC) which is the maximum of the LFC taken over a set of observed distribution shifts. That is, we observe a set of individuals drawn from a distribution shift, (k(k) pk. where pk represents a shift of geographic context (e.g., po being individuals from California and PI being individuals from North
Carolina) or shift in time. E-LFC is then defined ma 1/n Di Io(f", xx(" 8). Finally, we consider the adversarial distributional fairness certification (A-DFC) which our computed value of I, (fo xx, 8). Unless stated otherwise, we use 8 = 0.05, 7 = 0.1, and with respect to 1000 test-set individuals. Complete experimental details given in Appendix
6.1 Comparing Training Methods
In Table I we compare different individual fairness training methods on three datasets from Ding
et al. (202)). ). For each dataset, train two layer neural network with 256 hidden neurons per layer. We compare with fairness through unawareness (FTU) which simply removes the sensitive feature and sensitive subspace robustness (SenSR) (Yurochkin et al. 2019). We observe consistent decrease in accuracy as we increase the strictness of our constraint. Whi While FTU has the best performance, we unable to compute strong IF guarantees. This result is expected given that it is well-known that guaranteeing the performance of certification-agnosiic networks is empirically challenging (Gowal et al. 2018). Similarly, observe that SenSR has positive effect the DIF guarantee while paying a 2-5% accuracy cost. When only enforcing local guarantees with F-IBP, we observe a 3-5%
'Code to reproduce experiments can be found at: AnstribttioomlIIndviiiaaaaaalall
7

---

Income
Employ
Coverage
Acc
LFC
E-DEC
A-DFC
Acc
LFC
E-DFC
A-DEC
Acc
LFC
EADEC
A-DFC
FTU
0.820
0.999 0.999
1.000
0.809
0.891
0.906
0.999
0.721
1.000
1.000
1.000
SenSR
0.782
0.8855
0.931
0.995
0.743
00.247
0.300
0.639
0.709 0.538
0.865
0.899
F-IBP
0.771
0.076
0.092
0.130
0.743
0.040
0.090
0.178
0.699
0.162 0.253
0.288
L-DIF
0.763
0.035
0.051
0.095
0.738
0.025
0.051
0.091
0.698
0.101 0.122
0.136
U-DIF
0.725
0.002
0.002
0.042
0.724
0.000
0.006
0.067
0.681
0.000 0.042
0.071
Table 1:
Performance of each training method across three folktables datasets. For each dataset we give the accuracy (Acc, t), local IF violation (LFC, }) empirical DIF violation (E-DFC, J), and the adversarial DIF violation (A-DFC, 4). We observe consistent drop in accuracy across datasets as we enforce more strict DIF constraints. However, we notice orders magnitude decrease in the individual fairness violation across all three metrics as methods impose stricter constraints.
Computational Time (Training with in
DIF Witth
Bounde 0.2)
Ten hours
Time (Seconte)
Cin hour
DIF Vistalion
88
0.
0..11
10
000200
Fire migules
1-200
12:41
Upper
10"
102
One minute
00/07
0.0
512 1024
2048
4095
128
1024
2048
0.01
0.05
0.1
0.15
0.2
Neural Net. Width
NN Width (Depth 2)
Vaaluo
L-DRO
Adult
German
Upper Bound
Lower Bound
Figure 2: Empirical algorithm analysis for our upper and lower bounds on DIF. Left: Computational time comparison between MILP training (times reported in (Benussi et al. 2022)) and L-DIF demonstrates our methods considerable advantage in scalability. Center: As the NNs get larger our DIF certificates get looser, as expected with bound propagation methods (Gowal et al. 2018). Right: As we increase 7 we also increase the gap between our upper and lower bounds due the over-approximate nature of our upper- bounds.
decrease in accuracy, but achieve an order of magnitude decrease in the local and distributional fairness violations. Using both L-DIF and U-DIF results in the strongest IF and DIF guarantees, albeit at a larger accuracy cost. Each regularization method proposed provides different cairness-accuras trade-off which should be carefully chosen to suit the needs of a given application.
6.2 Empirical Bound Analysis
In this section, we provide an overview of our algorithm's 's performance as we vary architecture size and the distributional parameter 7. In the left-most plot of Figure 2 we use stars to plot the computational times reported to train a single hidden layer neural network from (Benussi et al.) 2022). We squares to denote the amount of time used by our most computationally demanding method (L-DIF). Our method scales up to 4096 neurons without crossing the one hour threshold. We report an extended version of this experiment in Appendix B Moreover, the results from this paper were run on a laptop while the timings from Benussi et al. 2022) use a multi-GPU machine.
In the center plot of Figure 2 we show how the value of our upper bound on the DIF violation grows as we increase the size of the neural network. As the neural network grows in size, we observe a steady increase in our upper-bounds. This is not necessarily because the learned classifier is less individually fair. The steady increase in the bound value can be attributed to the approximation incurred by using bound propagation methods. It is well-known that as the neural networks grow larger, certification methods become more approximate /Ger et al. 2018 Wicker et al. 2021).
In the right-most plot of Figure 2 we show how our upper and lower bounds respond to increasing the distributional parameter 7. As 7 grows, we expect that our bounds become loose due to the over-approximation inherent in our bounds. Here we consider two-layer 16 neuron per-layer NN. Indeed we observe in the right-most plot of Figure g that the gap between our upper and lower bounds grow to almost an order of magnitude when increase 7 from 0.01 to 0.2.
8

---

Wass. Distancce Geog,
SerCh Model
F:BP Model
Wodel
1:2r Model
0.10-
20
6.F-
0.5
0.22
stslatton
0.4
Dat Vilation
6.3
0.2-
0,20
0:31
6.65-
0.21
Fikk
Covenge Eneray
Fil
Coeernge Erriee
Fdlk
Coverage Eritky
Fel
Coeenge Entlay
(b)
(c)
(d)
(e)
Income
Coverage
Employ
Upper Bound
Lower Bound
Figure 3: Evaluating our bounds versus real-world distribution shifts. Column (a): An empirical
distribution of Wasserstein distances between the distribution of individuals from different pairs of states, we certify w.r.t the upper quartile of these distributions. Columns (b) (c): We plot the local fairncess certificates (LFC) for each of the shifted dataset using a boxplot. We then plot our lower bound on the worst-case DIF violation as blue triangle and our upper bound on the worst-case DIF violation as a red triangle.
6.3
Certification for
Distribution Shifts
In this section we compare our adversarial bounds on DIF against real-world distribution shifts. In Figure we study our ability bound shift geographical context. We use the folktables dataset (Ding et al. 202T) and assume we can only train our model using data from California. We would then like to ensure that our model is individually fair when applied to other states. We start by computing the Wasserstein distance between the data observed for different states. The distribution of these values plotted Figure 3 (a). By estimating the pairwise Wasserstein distance between estimate what y. In practice, one would use domain knowledge to estimate y. Each dataset has a different worst-case y value, i.c., 0.15 for Employ versus 0.4 for Coverage. In Figure (b) then compute upper bounds (red triangle) and lower bounds (blue triangle) for each observed value of yy We also plot the observed local individual fairness certificates centered at each of the shifted datasets, i.e., the local fairesss of our model when applied to North Carolina etc., and plot this as box plot. We observe that our tower-bound tightly tracks the worst-case observed individual fairness. Our upper-bound is over-approximate but reasonably tight, especially for NNs trained with DIF guarantees. The validation of our upper and lower bounds against real world DIF violations highlights the value of bounds scalable, practical, and sound source of guarantees for individual fairness such that model stakeholders can justify deployment.
the states data
7 Conclusion
In conclusion, proposed method addresses the crucial need for scalable, formal guarantees of individual fairness. Our novel convex approximation of IF constraints enables efficient real-time audits of individual fairness by significantly reducing the computational cost local IF certification. We introduced the first certified bounds on DIF and demonstrated their applicability to significantly larger neural networks than previous works. Our empirical investigation of real-world distribution shifts further validated the scalability, practicality, and reliability of the proposed bounds. Our bounds on DIF violations offer robust source of guarantees for individual faireess, enabling model stakeholders to justify the deployment of fair machine learning algorithms.
Limitations This work improves the scalability of prior IF guarantees by more than two orders of magnitude. However, the models we consider are smaller than models that may be deployed in practice we hope to further improve scalability in future work.
Broader Impact This work focuses on fairness quantification and bias reduction which one critical aspect of developing socially responsible and trustworthy machine learning (ML). We highlight that this work focuses on individual fairness which is only one aspect of fairness in machine learning and on its own does not constitute a complete, thorough fairness evaluation. Experimental analysis of the impact of DIF on group fairness is in Appendix B.4 The intention of this work is improve the state of algorithmic fairness in ML, and we do not foresee negative societal impacts.

---

References
Agrawal, A. and Boyd, S. Diseiplined quasiconvex programming. Optimization Letters, 14:1643- 1657, 2020.
Alger, N.
Smallest axis-aligned bounding box of hyper-ellipsoid. Mathematics Stack Exchange, 2020. URI. httpas//mah..stacllcchagggg wwt.c/mmm/////ee cttteee//mmm/m3/8/5555 httpps/s//mmatttttaeeeeaaeeeee//
(version: 2020-11-29),
Barocas, S. and Selbst, A. D. Big data's disparate impact. Calif. L. Rev., 104:671, 2016.
Benussi, E., Patane, A., Wicker, M., Laurenti, L.. and Kwiatkowska, M. Individual faireess guarantees for neural networks. arXiv preprint arXiv:2205.05763 2022.
Carbone, G., Wicker, M., Laurenti, L.,, Patane, A., Bortolussi, L., and Sanguinetti, G. Robustness of bayesian neural networks to gradient-based attacks. Advances in Neural Information Processing Systems, 33:15602-15613. 2020.
Davenport, T. and Kalakota, R. The potential for artificial intelligence in healthcare. Future healthcare journal, 6(2):94, 2019.
Ding, F., Hardt, M., Miller, J., and Schmidt, L.. Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 34:6478-6493 2021.
Doherty, A., Wicker, M., Laurenti, L., and Patane, A. Individual fairness in bayesian neural networks. Advances in Approximate Bayesian Inference, 2023.
Dressel, J. and Farid, H. The accuracy, fairness, and limits predicting recidivism. Science advances, 4(1):eaa05580, 2018.
Dua, D. and Graff, C. UCI machine learning repository, 2017. URL. htt.::t://arccieeeieee. uci edu/ml
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pp. 214-226, 2012.
Emrich, T., Jossé, G., Kriegel, H.-P., Mauder, M., Niedermayer, J., Renz, M., Schubert, M., and Züfle, Optimal distance bounds for the mahalanobis distance. International Conference on Similarity Search and Applications, pp. 175-188 181. Springer, 2013.
Fazelpour, S. and Lipton, Z. C. Algorithmic fairness from non-ideal perspective. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pp. 57-63, 2020.
Fazlyab, M., Robey, A., Hassani, H., Morari, M., and Pappas, G. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Gehr, T., Mirman, M., Drachsler-Cohen. D., Tsankov, P., Chaudhuri, S., and Vechev, M. Ai2: Safety and robustness certification of neural networks with abstract interpretation. In 2018 IEEE symposium on security and privacy (SP), pp. 3-18. IEEE, 2018.
Gowal, S., Dvijotham, K., Stanforth, R., Bunel, R., Qin, C., Uesato, J., Arandjelovic, R., Mann, T., and Kohli, P. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint 1rXiv:
2018.
Gupta, S. and Kamble, V. Individual fairness in hindsight. The Journal of Machine Learning Research, 22(1):636-64400, 2021.
Hu, Y., Li, J., and Yu, C. K. W. Convergence rates of subgradient methods for quasi-convex optimization problems. Computational Optimization and Applications, 77:183-212, 2020.
Hu, Y., Li, G., Yu, C. K. W., and Yip, T. L. Quasi-convex feasibility problems: Subgradient methods and convergence rates. European Journal of Operational Research, 298(1):45-58, 2022.
John, P. G., Vijaykeerthy, D., and Saha, D. Verifying individual fairness in machine learning models.
In Conference on Uncertainty in Artificial Intelligence, pp. 749-758. PMLR, 2020.
10

---

Katz, G., Barrett, C.. Dill, D. L.. Julian, K., and Kochenderfer, M. J. Reluplex: An efficient smt solver for verifying deep neural networks. In Computer Aided Verification: 29th International Conference. CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part I 30, pp. 97-117. Springer, 2017.
Khedr, H. and Shoukry, Y. Certifair: A framework for certified global fairness of neural networks. arXiv preprint arXiv:2205.0999: 2022.
Madras, D., Creager, E., Pitassi, T., and Zemel, R. Learning adversarially fair and transferable representations. In International Conference on Machine Learning, pp. 3384.3393. PMLR, 2018.
Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706. 06083, 2017.
Mehrabi, N., Morstatter, F., Saxena, N., Lerman, K., and Galstyan, A. A survey on bias and fairness in machine learning. ACM Computing Surveys (CSUR), 54(6):1-35, 2021.
Mirman, M., Gehr, T., and Vechev, M. Differentiable abstract interpretation for provably robust neural networks. In International Conference on Machine Learning, pp. 3578-357866 PMLR, 2018.
Mukherjee, D., Yurochkin, M., Banerjee, M., and Sun, Y. Two simple ways to learn individual fairness metrics from data. In International Conference on Machine Learning, pp. 7097-7107. PMLR, 2020.
Mukherjee, D., Petersen, F., Yurochkin, M., and Sun, Domain adaptation meets individual fairness. and they get along. arXiv preprint arXiv: 00504, 2022.
Peychev, M., Ruoss, A., Balunović, M., Baader, M., and Vechev, M. Latent space smoothing for individually fair representations. In Computer Vision-ECCV 2022: 17th European Conference, Tel Aviy, Israel, October 23-27, 2022, Proceedings, Pari XIII, pp. 535-554. Springer, 2022.
Ruoss, A., Balunovic, M., Fischer, M., and Vechev, M. Learning certified individually fair representa- tions. Advances in Neural Information Processing Systems, 75776687779, 2020.
Sagawa, S., Koh, P. W., Hashimoto, T. B., and Liang, P. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. arXiv preprint ArXiv: 2019.
Scyyed-Kalantart L., Zhang, H., McDermott, M. B., Chen, I. Y., and Ghassemi, M. Underdiagnosis bias of artificial intelligence algorithms applied to chest radiographs in under-served patient populations. Nature medicine, 27(12):176-2182) 2021.
Sharifi-Malhe Maaaii--aalvjjerdi.. S., Kearns, M., and Roth, A. Average individual fairness: Algorithms, generaliza- tion and experiments. Advances in neural information processing systems, 32, 2019.
Sinha, A., Namkoong, H., Volpi, R., and Duchi, J. Certifying some distributional robustness with principled adversarial training. arXiv preprint arXiv: 10571, 2017.
Taskesen, B., Nguyen, V. A., Kuhn, D., and Blanchet, J. A distributionally robust approach to fair classification. arXiv preprint urXiv:2007.009300 2020.
Wicker, M., Laurenti, L., Patane, A., Chen, Z., Zhang, Z.,, and Kwiatkowska, M. Bayesian inference with certifiable adversarial robustness. In International Conference on Artificial Intelligence and Statistics, pp. 2431 12399. PMLR, 2021.
Xu, P., Zhou, Y., An, B., Ai, W., and Huang, F. Gfairhint: neural networks via fairness hint. In Workshop Trustworthy and Socially Responsible Machine Learning, NeurIPS 2022.
Improving individual fairness for graph
Yeom, S. and Fredrikson, M. Individual fairness revisited: Transferring techniques from adversarial robustness. arXiv preprint arXiv:2002.07738 2020.
Yurochkin, M. and Sun, Sensei: Sensitive set invariance for enforcing individual fairness. arXiv preprint arXiv:2006. 14168, 2020.

---

Yurochkin, M., Bower, A., and Sun, Y. Training individually fair ml models with sensitive subspace robustness, arXiv preprint arXiv: 1907.0002, 2019.
Zilka, M., Butcher, B., and Weller, A. A survey and datasheet repository of publicly available us criminal justice datasets, Advances in Neural Information Processing Systems, 01128008-28222. 2022.
12


Reviews:
[{"review_id": "8aG6uQjMMk", "reviewer": "Reviewer_FRnw", "summary": "This paper studies the problem of individual fairness in supervised learning. The focus is on studying how to certify distributional individual fairness (IF) (individual fairness over a set of distributions close to the observed empirical data distribution) in neural networks. Prior work has focused largely on certifying global IF, which is more expensive and thus can only be applied to smaller neural networks than the proposed certification/debiasing technique. The contributions of the paper are in showing how to certify distributional IF in neural networks and then using these bounds in the training process as regularizers to debias NNs. \n\nThe main methodology for certifying IF is presented in Section 5. The first step is to certify local IF by over-approximating the similarity ball to find a conservative estimate of the IF violation. They can then use this bound to certify distributional IF around the empirical data distribution and apply finite sample guarantees to give an estimate of the true distributional IF. \n\nThe authors then show how to use the bounds on distributional fairness as regularizers in the training procedure as a way to debias neural networks. They then provide experimental evaluation on a few benchmark datasets that demonstrates that their proposed training method indeed improves distributional individual fairness, at relatively modest degradations in accuracy. ", "questions": "What is the purpose of Table 2? It is a little difficult to interpret the punchline - it just seems to indicate that DIF training does not have a consistent effect on group fairness measures, either positively or negatively. ", "limitations": "-", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The main advantage is a relatively lightweight way to certify and train NNs for IF, in a way that requires little additional computation, compared to previous methods which are not able to scale to large NNs. \n\nThe experimental evaluation seems to confirm that DIF training as proposed by the regularization method does in fact improve significantly improve IF at modest degradation in classification accuracy. ", "weaknesses": "Section 5 is a little dense and it would be helpful for the reader if there was a little more discussion of the optimization procedure, particularly in Section 5.3. Theorem statements here might also be helpful for the reader to understand what the final guarantees are. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments on the presentation of our paper. Below we comment on the points and questions raised by the reviewer by providing specific actions that will be taken to address these presentation points.\n\n### On Clarity of Section 5\nWe thank the reviewer for this valuable comment. First, we comment that the requested theorem statement already exists in the paper as Theorem E.2 in the Appendix. We agree that moving Theorem E.2 to the main text of the paper and writing it to emphasize the final guarantee will improve the paper, thus, we propose to change the text of Theorem E.2 to the following and to present it in the main text as follows: \n\nTheorem 5.3: A solution to Equation (5), $\\bar{\\epsilon}$, is a sound upper-bound on the Distributional Individual Fairness violation, and therefore, is a certificate that no $\\gamma$-Wasserstien distribution shift can cause the individual fairness of the model $f^{\\theta}$ to exceed $\\bar{\\epsilon}$.\n\nIn addition, we will provide a clear statement of Lemma 5.3 (see our comment to Reviewer Lpfq) which adds clarity to the exact guarantees offered by our framework. \n\n\n### On the purpose of Table 2\n\nThe intended purpose of Table 2 is two fold. Firstly, to demonstrate empirically that optimizing a model for distributional individual fairness (DIF) does not inherently worsen nor improve other popular notions of fairness. Secondly, by showing that it has no strong correlation with other notions of fairness we hoped to convey that while DIF is a flexible and powerful notion of fairness, other aspects of fairness should be analyzed to get a wholistic picture of model bias.\n\nTo improve the presentation of the paper, we will highlight this point in our Broader Impacts section and move the table and discussion to the Appendix where we can further elaborate on the discussion of this point."}, {"review_id": "cToo13gC4R", "reviewer": "Reviewer_Lpfq", "summary": "This paper studies formal guarantees for notions of individual fairness (IF) for predictors given by neural network models. After relaxing common definitions for IF metrics by means of $\\ell_\\infty$ balls (or orthotopes), they adapt methodology based on adversarial robustness to provide upper and lower bounds to the IF achieved by models on an empirical sample - and those within a $\\gamma-$Wasserstein ball about it.", "questions": "1. Numerous times in the paper the authors say their bounds are ”efficient” because they leverage efficient methods (e.g. those based on bound propagation). While that may be true, it would be nice for the readers if they provided a brief explanation as to why these methods are efficient instead of placing everything in the appendix. \n2. It seems to me that the central novelty of this paper is to upper bound a mahalanobis metric (for $d_{fair}$) with an orthotope, which is quite simple. The remaining of the paper seems to me a direct application of results and methods in adversarial robustness. While I do appreciate the observation of being able to use those tools in the context of fairness - which also constitutes novelty - I would appreciate if the authors could be very clear about what are the main technical contributions of this work.\n3. Personally, I am not sure providing a section on the impact of these methods on group fairness is necessary. I’d much rather prefer a discussion on the efficiency of the bounds.\n4. Figure 1 is quite confusing. What makes the blue-star individuals likely? As presented, those blue-star points do not look likely. If I understand the figure correctly, the authors should present a more balanced empirical sample together with a larger sample representing the (unobserved) population. \n5. I also have problems with the fact that the authors state their goals and present their definitions in terms of expectation (e.g. as in Def 2), but simply restrict themselves to studying empirical samples. I think the presentation is misleading, because nowhere the authors really provide guarantees for the definition in Def 2 (that is, risk bounds). This is also an important limitation where the study the Wasserstein distance between distributions, as they simply regard their distribution as a one supported on Dirac functions (on the observed samples). \n6. Immediately after Eq (4), the authors write that “we can optimize this bound to be tight”. I don’t think this is correct: while they can indeed optimize the bound, there’s no guarantee that the bound will be tight, as the original problem is non-concave.\n7. In Section 5.4 and after presenting $\\mathcal L_{F-DIF}$, the authors mention when $\\gamma=0$, one recovers a local constraint on individual fairness on $x\\in X$. I don’t think this is completely accurate, because again, Def. 2 is defined in expectation of $x\\sim p(x)$, not simply over the empirical sample.", "limitations": "The authors mention that they do not foresee negative societal impacts. Maximizing upper and lower bounds is great but in doing so we don’t really know what is happening to the true fairness violation. It may be that the true fairness violation is in fact increasing which is propagating unfairness. While I understand that solving for this value is not feasible and thus appreciate the results presented, I would also like the paper to acknowledge that there are potential negative effects.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper studies an important problem of individual fairness\n- The first half of the paper, Section 3 and 4, which cover Background, the DIF definition, and problem explanation are very clear and easy to understand.", "weaknesses": "- The key observation and novelty in the approach is not clearly noted (See below)\n- Several of the nice advantages of their method (e.g efficiency) are not explained (see below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments on the presentation of our paper and appreciate the detail of their review. Below, we address each point raised by the reviewer. We clear up any minor misconceptions and provide a clear action to improve the presentation of the final version of the paper. We note that we have addressed the authors point on key contributions and observations in the global response. We are more than happy to respond on any further concerns. \n\n### On point 1:\nOn line 180-191 we state that our approach to local IF certification has computational complexity of two forward passes through the network, where one forward pass maintains the upper bound, the other maintains the lower bound. On the other hand, MILP approaches take exponentially many forward passes to converge. We will elaborate on these in the revised paper. We will also add a further comment on this in the main text that also points to Figure 2 as empirical validation of this statement.\n\n### On point 2:\nWe agree with the reviewer that one central novelty of the work is to upper bound the Mahalanobis metric with an orthotope. However, we would like to underscore that the application of this result is not to any traditional notion adversarial robustness, but to distributional individual fairness. The distributional component of fairness has not been certified in any prior work. Moreover, distributional certificates for any notion (fairness or robustness) have not been provided without assuming explicit knowledge of a Lipschitz constant. To this end, our optimization approach for this problem is novel and Theorem E.2 (to be moved to the main text as Theorem 5.3) showing that the upper bound formulation can be efficiently solved is another key non-trivial result of this paper which may find impactful application outside the current work. We appreciate that this novelty could have been further underscored and in the final version we will ensure that these points are emphasized.\n\n### On point 3:\nWe agree with the reviewers that Table 2 and Section 6.4 may be moved to the Appendix to make room for further analysis. Specific details are provided in our global response.\n\n### On point 4:\nIn Figure 1, the blue points have feature values that are generally within the observed range of individuals, albeit slightly outside what we have already seen. On the other hand, the purple stars fall wholly outside the range of feature values that were seen during training. The exact location of the blue stars is taken for illustration purposes. The blue points are not meant to illustrate the unobserved population (which implies unobserved points from the same distribution) but represent points that may be drawn from a population with a slightly different distribution. The purple individuals on the other hand illustrate individuals drawn from a drastically different distribution with different support. \n\n### On point 5:\nOn line 196 of the paper, we state that the error introduced in the finite sample regime can be bounded by means of concentration inequalities (i.e., risk bounds as the reviewer alludes to). In the final version of the work, we will elaborate on this point and provide a clear lemma statement in the main text in order to fully clarify the guarantees we give. The lemma statement will be: \n\nLemma 5.3 Given an upper-bound $\\bar{\\epsilon}$ computed according to Equation (5) the error introduced by using a finite sample can be bounded from above by $\\tau$. That is, the estimate $\\bar{\\epsilon}$ is within $\\tau$ of the true expectation of $\\bar{\\epsilon}$ with probability $1- \\lambda$, as long as $n$ is at least $\\dfrac{-1}{2\\tau^2} log(\\lambda/2) $. \n\nThe proof of this Lemma is a straight-forward application of Chernoff or Hoeffding's inequality. This lemma allows us to quantify the error induced by using finite samples to approximate the expectation in Definition 2, and works for both our upper and lower bounds.  \n\n### On point 6:\nWe thank the reviewer for this note, and they are correct with this point. The phrasing of this should state \"we can optimize any feasible selection of $\\phi_{i}$ values to be a tighter lower-bound by observing ... the function is differentiable.\" We stress that any feasible selection of $\\phi_{i}$ yields a valid lower bound to the DIF violation and that by observing our upper bounds we can quantify how \"tight\" the lower bound is w.r.t. the true value. \n\n### On Local IF constraint when $\\gamma = 0$\nWe believe this is a minor misconception on behalf of the reviewer. We highlight the specific phrasing used: \"we recover the local IF constraint on each $x^{(i)} \\in X$.\" This claim is that when $\\gamma = 0$, $x^{(i)}$ will not be perturbed and therefore the upper-bound fairness violation is taken at $x^{(i)}$ which is identical to the local IF constraint (note this is Definition 1 not Definition 2).\n\n### On the negative societal impacts comment\nGiven that we compute upper and lower bounds on the DIF violation, we are guaranteed that the true DIF value falls between these bounds. Therefore, we do know what is happening to the true fairness violation (w.r.t DIF) up to the tightness of our bounds. See Figures 2 and 3 of the main text for illustration of our upper and lower bounds. \n\nIn addition, where \"true fairness violation\" means bias not captured by the notion of DIF, we specifically address this in Section 6.4 where we state \"it is currently the case that no one fairness metric alone captures a complete picture of model bias\" and further make the point that DIF has no correlation with group fairness notions (see Table 2), thus a complete analysis of model bias should take these definitions into account. In the final version of the draft we will include this sentiment in our Broader Impact statement. "}, {"review_id": "W8HBtqkWK8", "reviewer": "Reviewer_xyNq", "summary": "This paper considers the problem of certifying individual fairness (IF), which is of great importance to reliable machine learning algorithms. To this end, the authors propose a novel convex relation of IF constraints that greatly reduces the computational cost. In addition, the authors propose to certify distributional individual fairness, ensuring that the neural network has guaranteed individually fair predictions for a given empirical distribution and all distributions within a $\\gamma$-Wasserstein ball.", "questions": "## Miscellaneous\n1.\tLine 106: feed forward $\\to$ feedforward\n2.\tLine 168: $d$ is indeed a vector; however, the denotation $\\sqrt{d}$ should be defined more specifically.\n", "limitations": "none", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper is technically sound.\n2. The extensive experiments validate the effectiveness of the proposed methods.", "weaknesses": "The paper studies individual fairness and distributional fairness. To my opinion, the two topics seem to be independent. However, it is possible that I misunderstand this paper. It would be better if the authors can present more relations between these topics.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments including their clarifying points about our notation and praise regarding our experimental section. We will ensure that the notational points are adjusted in the final version of the paper\n\n### On the separation between distributional robustness and fairness\nIn general, distributionally robust fairness and individual fairness are separate concepts. This point is made on line 97 (last paragraph of the related works). However, in this work we study the intersection of these two: distributional individual fairness. We will attempt to further emphasize this in the Introduction."}]

Author rebuttal:

Meta-review: The paper proposes a method for certifying individual fairness of neural networks under distribution shifts. Particularly, it seeks to certify that the output of the neural network remains almost the same (for each individual data point) when the input distribution changes within a certain Wasserstein ball. The reviewers found the results interesting for the community. There were several initial concerns about the presentation of the results. However, after a few communication rounds between the authors and the reviewers, the concerns have been resolved. Therefore, I believe the paper can be published after minor changes. Please consider the reviewers' comments in your revision.
Decision: Accept (poster)