Differentially Private and Fair Deep Learning:A Lagrangian Dual Approach
Cuong Tran1 , Ferdinando Fioretto1 , Pascal Van Hentenryck2
1

Syracuse University, 2 Georgia Institute of Technology
cutran@syr.edu, ffiorett@syr.edu, pvh@isye.gatech.edu

Abstract
A critical concern in data-driven decision making is to build
models whose outcomes do not discriminate against some demographic groups, including gender, ethnicity, or age. To ensure non-discrimination in learning tasks, knowledge of thesensitive attributes is essential, while, in practice, these attributes may not be available due to legal and ethical requirements. To address this challenge, this paper studies a modelthat protects the privacy of the individuals’ sensitive information while also allowing it to learn non-discriminatory predictors. The method relies on the notion of differential privacy
and the use of Lagrangian duality to design neural networks
that can accommodate fairness constraints while guaranteeing the privacy of sensitive attributes. The paper analyses thetension between accuracy, privacy, and fairness and the experimental evaluation illustrates the benefits of the proposedmodel on several prediction tasks.

Introduction
A number of socio-technical decisions, such as criminal assessment, landing, and hiring, are increasingly being aided
by machine learning systems. A critical concern is thatthe learned models are prone to report outcomes that are
discriminatory against some demographic group, including
gender, ethnicity, or age. These concerns have spurred the recent development of fairness definitions and algorithms for
decision-making, focusing attention on the tradeoff between
the model accuracy and fairness.
To ensure non-discrimination in learning tasks, knowledge of the sensitive attributes is essential. At the sametime, legal and ethical requirements often prevent the useof this sensitive data. For example, U.S. law prevents using racial identifiers in the development of models for consumer lending or credit scoring. Other requirements may
be even more stringent, and prevent the collection of protected user attributes, such as for the case of racial attributes
in the E.U. General Data Protection Regulation (GDPR), or
require protection of the consumer data privacy. In this scenario, an important tension arise between (1) the demand
for models to be non-discriminatory, (2) the requirement forsuch model to use the protected attribute during training, and(3) the restriction on the data or protected attributes that can
Copyright c 2021, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

be used. There is thus a need to provide learning models thatcan both guarantee non discriminatory decisions and protect
the privacy of the individuals’ sensitive attributes.
To this end, this paper introduces a differential privacy
framework to train deep learning models that satisfy several
group fairness notions, including equalized odds, accuracy
parity, and demographic parity (Zafar et al. 2017a; Hardt
et al. 2016; Agarwal et al. 2018), while providing privacy ofthe protected attributes. The key elements of the framework
can be summarized as follows:
1. The fairness requirement is captured by casting the learning task as a constrained optimization problem. A Lagrangian dual approach is then applied to the learningtask, dualizing the fairness constraints using augmented
Lagrangian terms (Hestenes 1969).
2. The privacy requirement is enforced by using a clipping approach on the primal and dual steps and adding
noise calibrated by the sensitivities of the constraint terms
and their gradients. The primal step only applies clippingon constraint gradients involving sensitive attributes, andthus, does not have a major effect on the model accuracy.
3. The framework addresses the bias-variance trade-off ofclipping by providing bounds on the expected errors ofconstraint gradients and constraint violations. The clipping bounds can then be calibrated by minimizing theseupper bounds.
The rest of the paper presents the proposed Private and Fair
Lagrangian Dual (PF-LD) framework, its theoretical results,
and its empirical evaluation on several prediction tasks. The
empirical results show that, on selected benchmarks, PF-LD
achieves an excellent trade-off among accuracy, privacy, andfairness. It may represent a promising step towards a practical tool for privacy-preserving and fair decision making.
An extended version of this work, that includes proofs ofall theorems, can be found in (Tran, Fioretto, and Van Hentenryck 2020).

Related Work
The topics of privacy and fairness have been study mostly
in isolation. A few exceptions are represented by the workof Dwork et al. (2012), which is one of the earliest contribution linking fairness and differential privacy, showing that

individual fairness is a generalization of differential privacy.
More recently, Cummings et al. (2019) study the tradeoff
between differential privacy and equal opportunity, a notionof fairness that restricts a classifier to produce equal true
positive rates across different groups. The work shows that
there is no classifier that achieves (, 0)-differential privacy,satisfies equal opportunity, and has accuracy better than aconstant classifier. Ekstrand, Joshaghani, and Mehrpouyan(2018) raise questions about the tradeoff between privacy
and fairness and, Jagielski et al. (2019) and Mozannar,
Ohannessian, and Srebro (2020) propose two simple, yeteffective algorithms that satisfy (, δ)-differential privacy
and equalized odds. Xu, Yuan, and Wu (2019) proposes a
privacy-preserving and fair logistic regression model making use of the functional mechanism (Chaudhuri, Monteleoni, and Sarwate 2011). Finally, a recent line of work has
also observed that private models may have a negative impact towards fairness (Pujol et al. 2020; Bagdasaryan, Poursaeed, and Shmatikov 2019). In contrast to the work discussed above, this paper, presents a Lagrangian dual method
to enforce several fairness constraints directly into the training cycle of a deep neural network and proposes a differentially private and fair version of the learning algorithm.

Problem Settings and Goals
The paper considers datasets D consisting of n individual
data points (Xi , Ai , Yi ), with i ∈ [n] drawn i.i.d. from an
unknown distribution. Therein, Xi ∈ X is a non-sensitive
feature vector, Ai ∈ A, with A = [m] (for some finite m) is
a protected attribute1 , and Yi ∈ Y = {0, 1} is a binary label.
The goal is to learn a classifier Mθ : X → Y, where θ isa vector of real-valued parameters, that ensures a specified
non-discriminatory notion with respect to A while guaranteeing the privacy of the sensitive attribute A. The model
quality is measured in terms of a nonnegative, and assumed
differentiable, loss function L : Y × Y → R+ , and the problem is that of minimizing the empirical risk minimization(ERM) function:n

1X
min J(Mθ , D) =L(Mθ (Xi ), Yi ).
θ
n i=1

(L)

The paper focuses on learning general classifiers, such asneural networks, that satisfy group fairness (as defined next)
and protect the disclosure of the sensitive attributes using thenotion of differential privacy. Importantly, the paper assumes
that the attribute A is not part of the model input during inference. This is crucial in the application of interest to thiswork as the protected attributes cannot be disclosed.

Preliminaries: Fairness
The paper consider a classifier M satisfying some groupfairness notion under a distribution over (X, A, Y ) for theprotected attribute A and focuses on three fairness notions:
1
While this notation simplifies exposition, the method proposed
is not limited to the case where there is a single protected attribute.

• Demographic Parity: M’s predictions are statistically independent of the protected attribute A. That is,Pr[M(X) = ŷ | A = a] = Pr[M(X) = ŷ] ∀a ∈ A, ŷ ∈ Y,
which, since ŷ ∈ {0, 1}, can be expressed as
E[M(X) | A = a] = E[M(X)], ∀a ∈ A.
• Equalized odds: M’s predictions are conditionally independent of the protected attribute A given the label Y .
That is, for all a ∈ A, ŷ ∈ Y, and y ∈ Y:
Pr[M(X) = ŷ | A = a, Y = y] = Pr[M(X) = ŷ | Y = y].
or, equivalently, for all a ∈ A, y ∈ Y,
E[M(X) | A = a, Y = y] = E[M(X) | Y = y].
• Accuracy parity: M’s miss-classification rate is conditionally independent of the protected attribute:
Pr[M(X) 6= Y | A = a] = Pr[M(X) 6= Y ], ∀a ∈ A,or equivalently,
E[L(M(X), Y ) | A = a] = E[L(M(X), Y )], ∀a ∈ A,
where L is the loss function to minimize in problem (L).
As noted by Agarwal et al. (2018) and Fioretto et al.
(2020), several fairness notions, including those above, canbe viewed as equality constraints between the properties ofeach group with respect to the population. These constraints
can be expressed as:Ez∼DPi [h(z)] − Ez∼DGi [h(z)] = 0(1)where, for i in some index set I, DPi is a subset of thedataset D, indicating the population term, DGi is a subset ofDPi , indicating the group term, and is obtained by accessing
the protected attributes A, the function h characterizes themodel output under some fairness definition.
Since the joint data distribution over (X, A, Y ) is unknown, the above uses its empirical mean ÊD , which canbe estimated from the training data D.
Example 1 (Demographic parity). Demographic parity canbe expressed as a set of |A| constraints, with h(z) = Mθ (z)and, for each i ∈ A, the subsets indicating population terms
are defined as:
DPi = {(X, Y ) | (X, A, Y ) ∈ D},
and the subsets indicating the group terms as:
DGi = {(X, Y ) | (X, A, Y ) ∈ D ∧ A = i}.

Preliminaries: Differential Privacy
Differential privacy (DP) (Dwork et al. 2006) is a strong
privacy notion used to quantify and bound the privacy lossof an individual participation to a computation. While traditional DP protects the participation of an individual to adataset used in a computation, similarly to (Jagielski et al.
2019; Mozannar, Ohannessian, and Srebro 2020), this work
focuses on the instance where the protection is restricted tothe sensitive attributes only. A dataset D ∈ D = (X ×A×Y)

of size n can be described as a pair (DP , DS ) where DP ∈(X × Y)n describes the public attributes and DS ∈ An describes the sensitive attributes. The privacy goal is to guarantee that the output of the learning model does not differ
much when a single individual sensitive attribute is changed.
The action of changing a single attribute from a dataset
DS , resulting in a new dataset DS0 , defines the notion ofdataset adjacency. Two dataset DS and DS0 ∈ An are said
adjacent, denoted DS ∼ DS0 , if they differ in at most a single
entry (e.g., in one individual’s group membership).
Definition 1 (Differential Privacy). A randomized mechanism M : D → R with domain D and range R is (, δ)differentially private w.r.t. attribute A, if, for any dataset
DP ∈ (X × Y)n , any two adjacent inputs DS , DS0 ∈ An ,and any subset of output responses R ⊆ R:
Pr[M(DP , DS ) ∈ R] ≤ e Pr[M(DP , DS0 ) ∈ R] + δ.
When δ = 0 the algorithm is said to satisfy -differential privacy. Parameter  > 0 describes the privacy loss of the algorithm, with values close to 0 denoting strong privacy, whileparameter δ ∈ [0, 1] captures the probability of failure of thealgorithm to satisfy -differential privacy. The global sensitivity ∆f of a real-valued function f : D → Rk is definedas the maximum amount by which f changes in two adjacent inputs D and D0 : ∆f = maxD∼D0 kf (D) − f (D0 )k.
In particular, the Gaussian mechanism, defined by

Algorithm 1: Fair-Lagrangian Dual (F-LD)
input : D = (Xi , Ai , Yi )ni=1 : Training data;α, s = (s1 , s2 , . . .) : step sizes.
λmax : Max multipliers value.
1 λ1,i ← 0 ∀i ∈ I
2 for epoch k = 1, 2, . . . T do
3foreach Mini-batch B ⊆ D do
4
θ ← θ − α∇θ J(Mθ , BP )+λ>k |µ(BP ) - µ(BG )|56

λk+1 ← λk + sk |µ(DP ) − µ(DG )|λk+1,i ← min(λmax , λk+1,i ) ∀i ∈ I

In Lagrangian relaxation, the problem constraints are relaxed into the objective function using Lagrangian multipliers λi ≥ 0 associated to each of the |I| constraints and expressing the penalty induced by violating them. When all theconstraints are relaxed, the Lagrangian function becomesLλ (θ) = J(Mθ , DP ) + λ> |µ(DP ) − µ(DG )| ,where λ = (λ1 , . . . , λ|I| ) and the function | · |, used here to
denote the element-wise operator (i.e, |µ(DPi ) − µ(DGi )|for i ∈ I), captures a quantification of the constraint violations, often used in constraint programming (Fontaine, Laurent, and Van Hentenryck 2014).
Using a Lagrangian function, the optimization becomes?

M(D) = f (D) + N (0, ∆2f σ 2 ),θ (λ) = argmin Lλ (θ),

(5)

θ

2

where N (0, ∆f σ ) is the Gaussian distribution with 0mean and standard deviation ∆f σ 2 , satisfies (, δ)-DP forδ > 54 exp(−(σ)2 /2) and  < 1 (Dwork, Roth et al. 2014).

Constrained Learning with Lagrange Duality
When interpreted as constraints of the form (1), fairness
properties can be explicitly imposed to problem (L), resulting in a constrained ERM problem. Solving this new problem, however, becomes challenging due to the presence ofconstraints. To address this challenge, this work uses concepts borrowed from Lagrangian duality.
Consider a set of |I| constraints of the form (1), and expressed succinctly as:µ(DP ) − µ(DG ) = 0>(2)where µ(DP ) and µ(DG ) are vectors containing elementsµ(DPi ) = Êz∼DPi [h(z)] and µ(DGi ) = Êz∼DGi [h(z)], respectively, for each i ∈ I.
Notice that the constraints in µ(DP ) access public data
only, while the constraints in µ(DG ) access also the sensitive data. Notice also that the paper does not restrict the setting to the case where only demographic attributes are sensitive and, in particular, it does not assume that DS = DG .
The resulting learning task is defined by the following optimization problemµ(DP ) − µ(DG ) = 0> .

that produces an approximation Mθ? (λ) of Mθ? . The Lagrangian dual finds the best Lagrangian multipliers, i.e.,?

λ= argmaxλ≥0 J(Mθ? (λ) , DP )(6)

to obtain Mθ? (λ? ) , i.e., the strongest Lagrangian relaxation of
M. Learning this relaxation relies on an iterative schemethat interleaves the learning of a number of Lagrangian relaxations (for various multipliers) with a subgradient method
to learn the best multipliers. The resulting method, called
Fair-Lagrangian Dual (F-LD) is sketched in Algorithm 1.
Given the input dataset D, the optimizer step size α > 0,
and the vector of step sizes s, the Lagrangian multipliers are
initialized in line 1. The training is performed for a fixed
number of T epochs. At each epoch k, the primal update
step (lines 3 and 4) optimizes the model parameters θ using stochastic gradient descent over different mini-batches
B ⊆ D. The optimization step uses the current Lagrangian
multipliers λk . Therein, BP and BG indicate the population and group terms over a minibatch. After each epoch,the dual update step (line 5), updates the value of the Lagrangian multipliers following to a dual ascent rule (Boydet al. 2011; Fioretto, Mak, and Van Hentenryck 2020). The
multipliers values are thus restricted to a predefined upperbound λmax (line 6).

A Private and Fair LD Modeln

1X
L(Mθ (Xi ), Yi )argmin J(Mθ , DP ) =n i=1
θsubject to

(4)

(3a)
(3b)

To ensure fairness, the primal (line 4) and dual (line 5) updates of Algorithm 1 involve terms to compute the violations associated to constraints (3b). These terms rely on theattributes A, and therefore, the resulting model leaks the sensitive information. To contrast this issue, this section introduces an extension to F-LD, called Private and Fair Lagrangian Dual (PF-LD) method, that guarantees both fairness and privacy. The idea is to render the computations of
the primal and dual update steps differentially private withrespect to the sensitive attributes.
Private Primal Update At each epoch k, the primal update (line 4 of Algorithm 1) computes the gradients over theloss function Lλk (θ), which is composed of two terms (seeEquation (4)). The first term, J(Mθ , DP ), uses exclusively
public information, while the second term, λ> |µ(DP ) −µ(DG )| requires both the public and sensitive group information. The computation of these gradients can be madedifferentially private by the introduction of carefully calibrated Gaussian noise. The general concept, relies on performing a differentially private Stochastic Gradient Descent(DP-SGD) step (Abadi et al. 2016). In a nutshell, DP-SDG
computes the gradients for each data sample in a randommini-batch, clips their L2-norm, computes the average, andadds noise to ensure privacy.
The result below bounds the global sensitivity ∆p of thesensitive term in the primal update, which is needed to calibrate the noise necessary to guarantee privacy.
Theorem 1. Let k∇θ h(z)k ≤ Cp , for all z ∈ BGi , i ∈ I, andsome Cp > 0. The global sensitivity ∆p of the gradients ofthe constraints violation ∇θ λ> |µ(BP ) − µ(BG )| is∆p ≤2Cp λmax.
mini∈I |BGi | − 1(7)

The above uses a clipping term, Cp , to control the maximal change of the gradients. Crucially, this is non-limiting,as it can be enforced by clipping the gradient contribution k∇θ h(z)k to Cp , similarly to what is done in DPSGD (Abadi et al. 2016). Using Theorem 1, the privacypreserving primal update step for a mini-batch B ⊆ D canbe executed by clipping exclusively the gradients of thefunctions h(z) associated with the group terms in BG . It is
not necessary to perform gradient clipping for the functions
h(z) associated with the population terms in BP . While thismay induce propagating population and group terms gradients of different magnitudes, the authors observed often
improved performance in the adopted setting. Thus, PF-LD
substitutes line 4 of Algorithm 1 with the followingθ ← θ−α ∇θ [J(Mθ , BP )] +(8)¯ Cp µ(BG ) + N (0, σ 2 ∆2 I) ,λ> ∇θ µ(BP ) − ∇ppθ
¯ Cp is applied towith I ∈ {0, 1}|I|×|I| , σp > 0, and ∇θ¯ Cp (x) =each element µ(BGi ) of vector µ(BG ), where ∇θk∇xk∇x/max(1,Cp ) denotes the gradients of a given scalar loss
x clipped in a Cp -ball, for Cp > 0.
Private Dual Update Similar to the primal step, the dual
update requires access to the sensitive group information(see line 5 of Algorithm 1). It updates the multipliers basedon amount of constraint violation |µ(DP ) − µ(DG )| computed over the entire dataset D. Privacy can be attained byinjecting Gaussian noise to the computation of the multipliers, but computing the global sensitivity ∆d of the constraint
violations is non-trivial since the range of the violations is
unbounded. Once again, the paper recurs to the adoption ofa clipping term, Cd , that controls the maximal contributionof the constraint violation to the associated multiplier value.
Theorem 2. Let |h(z)| ≤ Cd , for all samples z ∈ DGi , i ∈ I,
and some Cd > 0. The global sensitivity ∆d of the constraint
violation |µ(DP ) − µ(DG )| is
√
2Cd
∆d ≤
.
(9)
mini∈I |DGi | − 1
The privacy-preserving dual update step, used in lieu ofline 5 of Algorithm 1, is given by the following

λk+1 ← λk + sk |µ(DP ) − µ̄Cd (DG )|+N (0, σd2 ∆2d I)(10)with I ∈ {0, 1}|I|×|I| , σd > 0, and where, for every i ∈ I,#"h(z)µ̄Cd (DGi ) = Êz∼DGi.
max(1, |h(z)|Cd )Note that while Theorem 1 bounds the individual gradientnorms of each functions h(z) for samples z ∈ BGi andi ∈ I, Theorem 2 bounds their maximum absolute values.
The choice of terms Cp and Cd plays a special role in limiting the impact of an individual change in the protected
attributes. It controls, indirectly, the privacy loss, as it impacts the global sensitivities ∆p and ∆d . However, theseterms also affect the model accuracy and fairness. In particular, larger Cp values will propagate more precise gradientsensuring better accuracy and model fairness. On the other
hand, larger clipping values will also introduce more noise,and thus degrade the information propagated. The converse
is true for smaller clipping values. A theoretical and experimental analysis of the impact of these terms to the model
accuracy and fairness is provided in the next sections.

Privacy Analysis
The privacy analysis of PF-LD relies on the moment accountant for Sampled Gaussian (SG) mechanism (Mironov, Talwar, and Zhang 2019), whose privacy is analyzed using thedefinition of Rényi Differential Privacy (RDP) (?). In synthesis, a function f satisfies (α, )-RDP, if the Rényi divergence Dα of order α between any adjacent inputs of f isupper bounded by . Additionally, the SG mechanism withsampling ratio q (that is, uses a fraction q of the n data
points) and standard deviation σ satisfies (α, )-RDP with: ≤ Dα N (0, σ 2 ) k (1 − q)N (0, σ 2 ) + qN (1, σ 2 )
2

2



(11a)

2 

 ≤ Dα (1 − q)N (0, σ ) + qN (1, σ ) k N (0, σ ) . (11b)The following results consider a PF-LD algorithm thattrains a model over T epochs using a dataset D containing n
training samples, uses mini-batches B at each iteration, andstandard deviation parameters σp and σd , associated to theprimal and dual steps, respectively. Note that, Equations (8)and (10), correspond to instances of the SG mechanism.

Lemma 1. The PF-LD primal step satisfies (α, p )-RDP,
where p satisfies Equations (11) with q = |B|/n and σ =σp ∆p are, respectively, the SG sampling ratio q and standard deviation parameters.
Lemma 2. The PF-LD dual step satisfies (α, d )-RDP,
where d satisfies Equations (11) with q = 1 and σ = σd ∆dare, respectively, the SG sampling ratio and standard deviation parameters.
PF-LD uses a predefined amount of noise (specified byparameters σp and σd ) at each iteration, so that each iteration has roughly the same privacy loss, and uses the momentaccountant (Abadi et al. 2016) to track detailed informationof the cumulative privacy loss.
T n

Theorem 3. PF-LD satisfies (α, |B|p + T d )-RDP.
The results above follow directly from Equations (11) and
RDP composability results (Mironov 2017), since the primal and dual steps of PF-LD uses Gaussian noise withparameter σp and σd , respectively. The final privacy loss
in the (, δ)-differential privacy model is obtained by observing that a mechanism satisfying (α, )-RDP also satis1/δ
fies ( + log
α−1 , δ)-differential privacy, for any 0 < δ < 1(Mironov 2017).

Bias-Variance Analysis
A key aspect of PF-LD is the choice of values Cd and Cp
used to bound the functions h(z), and their gradients, respectively, for every sample z ∈ DGi and i ∈ I. The choiceof these clipping terms affects the global sensitivity of thefunctions of interest, which, in turn, impacts the amount ofnoise used by the differentially private mechanisms. As aresult, the clipping terms are associated to a bias-variance
trade-off: Small values can discard significant amounts ofconstraints information, thus introduce bias; large values
retain more information but force the differential privacy
mechanism to introduce larger noise, inducing more variance. It is important to recall that, at every iteration, PF-LD
induces some privacy loss, thus, for a fixed privacy budget,the use of small values cannot be compensated by longer
runs. This section formulates a bias-variance analysis thatis helpful to select clipping values for gradient norms under
the SG mechanism.
Let G = ∇θ λ>|µ(BP ) − µ(BG )| be the gradient computed over a minibatch B during the primal update of F-LD
¯ Cp µ(BG )|+(Algorithm 1 line 4) and G̃ = λ>|∇θ µ(BP )−∇θ
2 2
N (0, σp ∆p I) be its privacy-preserving counterpart, as computed by PF-LD (Equation (8)).
Theorem 4. The expected error between the real and noisy
gradients, G and G̃, incurred during the primal step can be
upper bounded as:hi 2pS σ λmax C
p
G̃ p
+
(12)
E G − G̃ ≤mini∈I |BGi | − 1Xλi Êz∼BGi max 0, k∇θ h(z)k − Cp ,i∈Iwhere SG̃ is the shape (i.e., the number of entries) of G̃.

The proof relies on isolating and bounding the variance andbias terms of the expected error).
Note that the bound above is a convex function of Cp . Its
unique minimizer satisfies:
p
h 
X
i
2 SG̃ σp λmax=
λi Êz∼BGi 1 k∇θ h(z)k ≥ Cp .
mini∈I |BGi | − 1i∈IWhile beyond the scope of this work, the above illustrates
that a procedure to find the optimal Cp privately can be constructed effectively.
Next, the paper shows how to bound the expected error incurred in using the noisy constraint violations during
the dual step. Let Vi = |µ(DPi ) − µ(DGi )| be the value
corresponding to the i-th constraint violation (i ∈ I), andṼi = |µ(DPi ) − µ̄Cd (DGi )| + N (0, σd2 ∆2d ) be its privacypreserving version (see Equation (10)).
Theorem 5. The expected absolute error between the realand noisy constraint violations Vi and Ṽi , for i ∈ I, isbounded by the following√hi
2Cd σdE |Vi − Ṽi | ≤(13)mini∈I |DGi | − 1+ Êz∼DGi [max(0, |h(z)| − Cd )] .
The proof uses similar arguments as those in the proof of
Theorem 4 (see (Tran, Fioretto, and Van Hentenryck 2020)
for details).

Experimental Analysis
Datasets, Models, and Metrics This section studies the
behavior of the proposed algorithm on several datasets, including Income, Bank, and Compas (?) datasets. Since thetrends are similar, the following discussion focuses on the
Bank datasets, whose task is to detect client subscriptions to
the term deposit, and the protected attributes define two age
groups.
The experiments consider a baseline classifier (CLF), implemented as a neural network with two hidden layers, thatmaximize accuracy only, without considerations for fairness
or privacy, and compare the proposed PF-LD model against
the following state-of-the-art algorithms: Z, it implements afair logistic regression models that achieves group fairness.
These models were presented in (Zafar et al. 2017b) for demographic parity and in (?) for accuracy parity and equalized odds. A, it implements the fair logistic regression model
based on reduction approaches, introduced in (?). Note thatthe models above preserves group fairness but do not guarantee privacy. They are used to highlight the effectiveness ofthe proposed approach based on the Lagrangian dual to ensure fairness. Finally, M, proposed in (Mozannar, Ohannessian, and Srebro 2020), the model most related to the proposed work, ensures both fairness and -differential privacy
with respect to the sensitive attributes. The algorithm uses
the fair model A on perturbed noisy data generated according to a randomized response mechanism (Kairouz, Oh, andViswanath 2014). While these models where studied in thecontext of equalized odds, this work extends them to satisfy

0.815
0.810

0.1
CLF

Z

A

M

PF-LD

0.85
0.80

PF-LD
M

0.81
0.80
0.79

0.75
0.65
0.60

CLF

Z

A

M

PF-LD

Figure 1: Accuracy and fairness comparison.

Accuracy

0.70

0.815
0.810
0.805
0.800

PF-LD
M

0.4 0.5 0.6 0.7 0.8 0.9 1.0

Accuracy parity viol.

0.820

0.03

PF-LD
M

0.02
0.01
0.00

Demographic parity viol.

0.2

PF-LD
M

Equalized odds viol.

0.3

0.0

Accuracy

0.825

Equalized odds

Accuracy

Demographic parity

Accuracy

Fairness Violation

Accuracy parity

PF-LD
M

0.3
0.2
0.1
0.4

PF-LD
M

0.3
0.2
0.1

0.4 0.5 0.6 0.7 0.8 0.9 1.0

Figure 2: Privacy, fairness, and accuracy tradeoff.
all fairness definitions considered in this work. Compared tothe proposed model M has the disadvantage of introducing
large amounts of noise to the sensitive attribute, especiallywhen the domain of these attributes is large and/or when A
is high-dimensional. 2
The experiments analyze the accuracy, fairness violations,and privacy losses (when applicable) of the models above.
The fairness violations are measured as the maximal difference in fairness constraint violations between any two protected groups. The privacy losses are set to  = 1.0 andδ = 10−5 , unless otherwise specified. PF-LD uses clipping
bound values Cp = 10.0 and Cd = 5.0 and each experimentand configuration is repeated 10 times and presents averageand standard deviation results.
Accuracy and Fairness This section analyzes the impact
on accuracy and fairness of the privacy-preserving models introduced above. The results are summarized in Figure
1. Note that the plots have different scales. First, observethat the prediction accuracy of the proposed model is inline with that of the baseline non-private, non-fair classifier.
This is true for all the group fairness constraints adopted.
Next, observe that the fairness violations reported by PFLD are competitive with those reported by the fair, nonprivate models A and Z. Finally, notice that PF-LD reports
considerably lower fairness violations when compared to M,
the only other private and fair model analyzed, and the results are consistent across all fairness metrics and benchmarks. This is remarkable as the privacy budget adopted isvery modest when compared to what typically adopted in
the privacy-preserving machine learning literature (Xie et al.
2018; Jagielski et al. 2019).
Privacy, Fairness, and Accuracy Tradeoff This section illustrates the tradeoff between privacy, fairness, and accuracy
attained by PF-LD and compares them with algorithm M.
2

The authors note there is an additional work which addresses
learning a fair and private classifier (Jagielski et al. 2019). Whilean important contribution, it has been shown to induce significant
privacy losses (see Figure 1 of (Jagielski et al. 2019)). Model M wasshown to outperform these algorithms presented in (Jagielski et al.
2019) in terms of classification error bounds. Therefore, this paper
adopts M, as the state-of-the-art.

The results are summarized in Figure 2, that depicts the average and standard deviation of 100 model runs. The statisticaldifference between the performance PF-LD and M was verified using a paired t-test, which reported a p-value < 0.001
in each setting.
Firstly, observe that the fairness violation score decreases
as the privacy budget  increases (note that the scale differs across the plots). Large privacy losses allow PF-LD toeither run more iterations, given fixed noise values used ateach iteration, or reduce the level of noise applied to a given
number of iterations. These cases imply propagating more(former case) or more accurate (latter case) noisy constraint
violations that results in better capturing the fairness constraints violations during the primal and dual update steps.
This aspect is not obvious for M.
Next, notice that the model accuracy slightly decreases
as  increases. While this may seem surprising, our analysis shows that the fairness constraints, having their violations being propagated more exactly when  increases, havea negative impact on the model accuracy.
Finally, notice that, in most cases, PF-LD is more accurate and produce models that have smaller fairness violations, and, importantly, it produces models that are more robust than those produced by M. This is noticeable by comparing the standard deviations on accuracy and fairness violations of the two models. These observations demonstrates
the practical benefits of the proposed model.
PF-LD: Analysis of the Clipping Values This sections
analyses the factors affecting the privacy, accuracy, and fairness tradeoff outlined above. The analysis focuses on the primal clipping bound Cp as trends for the dual bound Cd aresimilar. Figure 3 illustrates the effects of Cp on the model
accuracy and fairness, at varying of the privacy parameter .
Observe that, for different fairness definitions, the best accuracy/fairness tradeoff is obtained when Cp ∈ [10, 20] (green
and yellow curves). The use of small clipping values (bluecurve) slows the drop in fairness violations at the increasingof the privacy budget . This is because small Cp values limit
the impact of the constraints violations to the model. On theother extreme, for high Cp values (e.g., brown curve), not0.750Accuracy

0.82
0.81
0.80

0.50 0.75 1.00 1.25 1.50 1.75 2.00

Epochs0.8

Epochs

0.2

0.3
0.2
0.1
0.0

0.1
0.0
0.3

Cp = 100.0

0.8
0.8
0

20

40

60

80

100

0.3
0.2
0.1
0.0

0

20

40

60

majorityminority

0.5
0.0

EpochsCp = 100.0

EpochsCp = 10.0

1.0%||G|| > Cp

0.3

Cp = 10.0

0.8

majorityminority

0.5
0.0

EpochsCp = 10.0

Cp = 1.0

1.0%||G|| > Cp

Fairness Violation

Accuracy

0.8

0.3
0.2
0.1
0.0

EpochsCp = 100.0

1.0%||G|| > Cp

0.775

0.03
0.02
0.01
0.00

Cp = 1.0

0.8

Fairness Violation

Accuracy

0.800

Cp = 1.0

Cp = 1000

Fairness Violation

0.825

Cp = 100

Accuracy

0.805

Cp = 50

Accuracy

0.810

Cp = 20Equalized odds viol.

Accuracy

0.815

Cp = 10

Demographic parity viol. Accuracy parity viol.

Cp = 180

100majorityminority

0.5
0.0

0

20

40

60

80

100

EpochsEpochsEpochs0.39 0.75 1.07 1.31 1.52 1.7 0.39 0.75 1.07 1.31 1.52 1.7 0.39 0.75 1.07 1.31 1.52 1.7

0.2
0.1
0.50 0.75 1.00 1.25 1.50 1.75 2.00

Figure 3: Effects of Cp on fairness and accuracy.
only it is observed a degradation in fairness violations, butalso in the model accuracy. This is because large Cp values imply larger amount of noise to be added to the gradient of the constraint violations, resulting in less accurate
information to be back-propagated at each step. Additionally, the noisy constraints gradients can negatively impact
the classifier loss function. Thus, the resulting models tend
to have worse accuracy/fairness tradeoff than those trainedwith intermediate Cp values. These observations support thetheoretical analysis which showed that the expected error
between the true and private gradients of the fairness constraints is upper bounded by a convex function of the primal
and the dual clipping bounds.
To further shed lights on the impacts of Cp to the model
fairness and accuracy, Figure 4 illustrates the model accuracy (left column) the fairness violations (middle column)
and the percentage of times the norm of the gradients associated to the constraint violations of a protected group exceeds
the clipping value Cp : kG̃k > Cp % (right column). The lastcolumn indicates the frequency of propagating the correct or
the clipped information. The figure uses demographic parity,
but the results are consistent across the other fairness metrics
studied. Observe that, the percentage of individual constraint
gradients exceeding Cp is very high when Cp is small. Thus,
a significant amount of information is lost due to clipping.
Conversely, at large Cp regimes most individual gradients(for both protected groups) are smaller than Cp . This choice
reduces bias, but it introduces large variances due to noise
necessary to preserve privacy. Therefore, both cases resultin models that have large fairness violations. Conversely, atintermediate Cp regimes, the produced models have lower
constraint violations while retaining high accuracy.
Performance Finally, this section analyses the performanceof the proposed Lagrangian dual framework. Table 1 reports
the average training time and standard deviations (in parenthesis) required to execute one epoch at the varying of thenumber of hidden layers and mini-batch size |B| for a model
enforcing no privacy nor fairness (N), one enforcing privacy
only (P), one enforcing fairness only (F-LD), and the pro-

Figure 4: Individual gradient norms associated to a protectedgroup and their relation to the clipping values Cp .
Hidden layers

|B|

N

F-LD

P

PF-LD

2
2
2

16
64
256

0.53 (0.01)
0.19 (0.01)
0.11 (0.01)

0.60 (0.01)
0.25 (0.01)
0.16 (0.01)

0.9 (0.04)
3.2 (0.09)
5.7 (0.05)

1.0 (0.02)
3.3 (0.08)
5.7 (0.10)

10
10
10

16
64
256

1.20 (0.02)
0.41 (0.02)
0.17 (0.01)

1.30 (0.01)
0.47 (0.01)
0.20 (0.01)

2.0 (0.08)
6.9 (0.09)
11.8 (0.15)

2.1 (0.07)
7.0 (0.12)
11.8 (0.23)

Table 1: Training time (sec) comparison.
posed one enforcing both privacy and fairness (PF-LD). The
tests use a common laptop (MacBook Air 2013, 1.7GHz,
8GB RAM) on the Bank dataset and are consistent for all
the fairness notions adopted.
Note that imposing the fairness constraints comes at almost no-overhead on top of the non-fair counterpart models.
It has been observed that clipping (used to preserve privacy)
is computationally expensive. However, this drawback has
been recently mitigated by the work of Subramani, Vadivelu,
and Kamath (2020), which uses JAX to speed up these operations and can achieve up to an order magnitude speedups.

Conclusions
This paper was motivated by the discrepancy between concerns in building models whose outcomes do not discriminate against some demographic groups and the requirementsthat the sensitive attributes, which are essential to build thesemodels, may not be available due to legal and ethical requirements. It proposed a framework to train deep learningmodels that satisfy several notions of group fairness, including equalized odds, accuracy parity, and demographic parity, while ensuring that the model satisfies differential privacy for the protected attributes. The framework relies on
the use of Lagrangian duality to accommodate the fairness
constraints and the paper showed how to inject carefully calibrated noise to the primal and dual steps of the Lagrangian
dual process to guarantee privacy of the sensitive attributes.
The paper further analyses the tension between accuracy,
privacy, and fairness and an extensive experimental evaluation illustrates the benefits of the proposed framework
showing that it may be come a practical tool for privacypreserving and fair decision making.

Ethic Statement
This paper studies a framework to train deep neural networks
resulting in models that protect the privacy of the individuals’ sensitive information while also allowing it learn nondiscriminatory predictors. The outcome of this research has
the potential to operate ethically, privately, and effectively in
key decision processes arising in many classification problems, as illustrated in the experimental section. The adoption of the proposed methodology would benefit both theindividual data owners, whose privacy protection is guaranteed, and the data curators that can use privacy-preserving
and fair solutions which are also operationally effective. The
main challenge or limitation of the proposed framework liesin the inherent tradeoff between the privacy of its users, thelevel of fairness retained, and the model accuracy.

References
Abadi, M.; Chu, A.; Goodfellow, I.; McMahan, H. B.;
Mironov, I.; Talwar, K.; and Zhang, L. 2016. Deep Learningwith Differential Privacy. In Proceedings of the 2016 ACM
SIGSAC Conference on Computer and Communications Security.
Agarwal, A.; Beygelzimer, A.; Dudik, M.; Langford, J.; andWallach, H. 2018. A Reductions Approach to Fair Classification. In Proceedings of the International Conference on
Machine Learning (ICML).
Bagdasaryan, E.; Poursaeed, O.; and Shmatikov, V. 2019.
Differential privacy has disparate impact on model accuracy.
In Proceedings of Advances in Neural Information Processing Systems (NIPS).

Fioretto, F.; Van Hentenryck, P.; Mak, T.; Tran, C.; Baldo, F.;
and Lombardi, M. 2020. Lagrangian Duality for Constrained
Deep Learning. In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in
Databases (ECML-PKDD).
Fontaine, D.; Laurent, M.; and Van Hentenryck, P. 2014.
Constraint-Based Lagrangian Relaxation. In Principles andPractice of Constraint Programming, 324–339.
Hardt, M.; Price, E.; Price, E.; and Srebro, N. 2016. Equalityof Opportunity in Supervised Learning. In Proceedings ofAdvances in Neural Information Processing Systems (NIPS).
Hestenes, M. R. 1969. Multiplier and gradient methods. Journal of optimization theory and applications 4(5): 303–320.
Jagielski, M.; Kearns, M.; Mao, J.; Oprea, A.; Roth, A.; Malvajerdi, S. S.; and Ullman, J. 2019. Differentially Private Fair
Learning. In Proceedings of the 36th International Conference on Machine Learning (ICML).
Kairouz, P.; Oh, S.; and Viswanath, P. 2014. Extremal Mechanisms for Local Differential Privacy. In Proceedings of Advances in Neural Information Processing Systems (NIPS).
Mironov, I. 2017. Rényi differential privacy. In 2017 IEEE
30th Computer Security Foundations Symposium (CSF),
263–275. IEEE.
Mironov, I.; Talwar, K.; and Zhang, L. 2019. R\’enyi Differential Privacy of the Sampled Gaussian Mechanism. ArXiv
abs/1908.10530.
Mozannar, H.; Ohannessian, M. I.; and Srebro, N. 2020. Fair
Learning with Private Demographic Data. In Proceedings ofthe International Conference on Machine Learning (ICML).

Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J.; et al.
2011. Distributed optimization and statistical learning via thealternating direction method of multipliers. Foundations andTrends R in Machine learning 3(1): 1–122.

Pujol, D.; McKenna, R.; Kuppam, S.; Hay, M.; Machanavajjhala, A.; and Miklau, G. 2020. Fair decision making using
privacy-protected data. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency (FAT),
189–199.

Chaudhuri, K.; Monteleoni, C.; and Sarwate, A. D. 2011. Differentially Private Empirical Risk Minimization. Journal of
Machine Learning Research .

Subramani, P.; Vadivelu, N.; and Kamath, G. 2020. Enabling
Fast Differentially Private SGD via Just-in-Time Compilation
and Vectorization. ArXiv abs/2010.09063.

Cummings, R.; Gupta, V.; Kimpara, D.; and Morgenstern, J.
2019. On the compatibility of privacy and fairness. In Proceedings of the Adjunct Publication of the 27th Conference
on User Modeling, Adaptation and Personalization (UMAP).

Tran, C.; Fioretto, F.; and Van Hentenryck, P. 2020. Differentially Private and Fair Deep Learning: A Lagrangian DualApproach. ArXiv abs/2009.12562.

Dwork, C.; Hardt, M.; Pitassi, T.; Reingold, O.; and Zemel,
R. 2012. Fairness through awareness. In Proceedings of the
3rd innovations in theoretical computer science conference.
Dwork, C.; McSherry, F.; Nissim, K.; and Smith, A. 2006.
Calibrating noise to sensitivity in private data analysis. In
Proceedings of Theory of Cryptography Conference, 265–284. Springer.
Dwork, C.; Roth, A.; et al. 2014. The algorithmic foundationsof differential privacy. Foundations and Trends R in Theoretical Computer Science 9(3–4): 211–407.
Ekstrand, M. D.; Joshaghani, R.; and Mehrpouyan, H. 2018.
Privacy for all: Ensuring fair and equitable privacy protections. In Proceedings of Conference on Fairness, Accountability and Transparency, 35–47.
Fioretto, F.; Mak, T.; and Van Hentenryck, P. 2020. Predicting AC Optimal Power Flows: Combining Deep Learning andLagrangian Dual Methods. Proceedings of the AAAI Conference on Artificial Intelligence 34(01): 630–637.

Xie, L.; Lin, K.; Wang, S.; Wang, F.; and Zhou, J. 2018.
Differentially private generative adversarial network. arXiv
preprint arXiv:1802.06739 .
Xu, D.; Yuan, S.; and Wu, X. 2019. Achieving Differential
Privacy and Fairness in Logistic Regression. In Proceedings of the 26th International Conference on World Wide Web(WWW).
Zafar, M. B.; Valera, I.; Gomez Rodriguez, M.; and Gummadi, K. P. 2017a. Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In Proceedings of the 26th International Conference on World Wide Web (WWW).
Zafar, M. B.; Valera, I.; Rodriguez, M. G.; and Gummadi,
K. P. 2017b. Fairness Constraints: Mechanisms for Fair Classification. In Proceedings of Artificial Intelligence and Statistics (AISTAT).