A Fairness Analysis on Private Aggregation of Teacher Ensembles

The Private Aggregation of Teacher Ensembles (PATE) is an important private machine learning framework. It combines multiple learning models used as teachers for a student model that learns to predict an output chosen by noisy voting among the teachers. The resulting model satisfies differential privacy and has been shown effective in learning high-quality private models in semisupervised settings or when one wishes to protect the data labels. This paper asks whether this privacy-preserving framework introduces or exacerbates bias and unfairness and shows that PATE can introduce accuracy disparity among individuals and groups of individuals. The paper analyzes which algorithmic and data properties are responsible for the disproportionate impacts, why these aspects are affecting different groups disproportionately, and proposes guidelines to mitigate these effects. The proposed approach is evaluated on several datasets and settings.


Introduction
The availability of large datasets and inexpensive computational resources has rendered the use of machine learning (ML) systems instrumental for many critical decisions involving individuals, including criminal assessment, landing, and hiring, all of which have a profound social impact. A key concern for the adoption of these system regards how they handle bias and discrimination and how much information they leak about the individuals whose data is used as input.
Differential Privacy (DP) [5] is an algorithmic property that bounds the risks of disclosing sensitive information of individuals participating in a computation. It has become the paradigm of choice in privacy-preserving machine learning systems and its deployments are growing at a fast rate. However, it was recently observed that DP systems may induce biased and unfair outcomes for different groups of individuals [1,19,28].
The resulting outcomes can have significant societal and economic impacts on the involved individuals: classification errors may penalize some groups over others in important determinations including criminal assessment, landing, and hiring [1] or can result in disparities regarding the allocation of critical funds and benefits [19]. While these surprising observations are becoming increasingly common, their causes are largely understudied and not fully understood.
This paper makes a step toward this important quest, and studies the disparate impacts arising when training a model using Private Aggregation of Teacher Ensembles (PATE) [17] an important and popular privacy-preserving machine learning framework. It combines multiple agnostic learning models used as teachers for a student model that learns to predict an output chosen by noisy voting among the teachers. The resulting model satisfies differential privacy and has been shown effective in learning high quality private models in semisupervised settings or when one wishes to protect the data labels.
The paper analyzes which properties of the algorithm and the data are responsible for the disproportionate impacts, why these aspects are affecting different individuals or groups of individuals disproportionately, and proposes a solution that may aid mitigating these effects.
In summary, the paper makes the following contributions: 1. It uses a fairness notion that relies on the concept of excessive risk, and measures the direct impact of privacy to the model accuracy for individuals or groups. 2. It analyzes this fairness notion in PATE, a state-of-the-art privacy-preserving ML framework. 3. It isolates key components of the model parameters and the data properties which are responsible for the observed disparate impacts. 4. It studies when and why these components affect different individuals or groups disproportionately. 5. Finally, based on these findings, it proposes a method that may aid mitigating these unfairness effects while retaining high accuracy.
To the best of the authors knowledge, this work represents a first effort toward understanding the reasons of the disparate impacts in privacy-preserving ensemble models.

Related Work
The study of the disparate impacts caused by privacy-preserving algorithms has recently seen several important developments. Ekstrand et al. [7] raise questions about the tradeoffs involved between privacy and fairness. Cummings et al. [4] study the tradeoffs arising between differential privacy and equal opportunity, a fairness notion requiring a classifier to produce equal true positive rates across different groups. They show that there exists no classifier that simultaneously achieves ( , 0)-DP, satisfies equal opportunity, and has accuracy better than a constant classifier. This development has risen the question of whether one can practically build fair models while retaining sensitive information private. To this end, Jagielski et al. [10] presents two algorithms that satisfy ( , δ)-differential privacy and equalized odds. Mozannar et al. [15] develops methods to adapt a nondiscriminatory learner to work with privatized protected attributes and Tran et al. [24] proposes a differentially private learning approach to enforce several group fairness notions using a Lagrangian dual method.
Pujol et al. [19] were seemingly the first to show, empirically, that resource allocation decisions made using DP datasets may disproportionately affect some groups of individuals over others. These studies were complemented theoretically by Tran et al. [25]. Similar observations were also made in the context of model learning. Bagdasaryan et al. [1] empirically observed that the accuracy of a DP model trained using DP-Stochastic Gradient Descent (DP-SGD) decreases disproportionately across groups causing larger negative impacts to the underrepresented groups. Farrand et al. [8], Uniyal et al. [26] reaches similar conclusions and show that this disparate impact is not limited to highly imbalanced data.
This paper builds on this body of work and their important empirical observations. It provides an analysis for the reasons of unfairness in the context of semi-supervised private learning ensembles, a commonly adopted scheme in privacy-preserving ML systems as well as introduces mitigating guidelines.
voting confidence privacy parameter f 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " i s 8 z / j 6 9 A A D p y l Z D l V N v + v N a u f o = " > A A A B + n i c b V B N T w I x F H z F L 8 Q v 1 K O X R m L i i e w a E j m S e P G I U c A E V t I t X W h o u 5 u 2 a 0 J W f o J X v X s z X v 0 z X v 0 l F t i D g p O 8 Z D L z X u Z l w k R w Y z 3 v C x X W 1 j c 2 t 4 r b p Z 3 d v f 2 D 8 u F R 2 8 S p p q x F Y x H r + 5 A Y J r h i L c u t Y P e J Z k S G g n X C 8 d X M 7 z w y b X i s 7 u w k Y Y E k Q 8 U j T o l 1 0 m 3 0 4 P f L F a / q z Y F X i Z + T C u R o 9 s v f v U F M U 8 m U p Y I Y 0 / W 9 x A Y Z 0 Z Z T w a a l X m p Y Q u i Y D F n X U U U k M 0 E 2 f 3 W K z 5 w y w F G s 3 S i L 5 + r v i 4 x I Y y Y y d J u S 2 J F Z 9 m b i v 1 4 o l 5 J t V A 8 y r p L U M k U X w V E q s I 3 x r A c 8 4 J p R K y a O E K q 5 + x 3 T E d G E W t d W y Z X i L 1 e w S t o X V b 9 W r d 3 U K o 1 6 X k 8 R T u A U z s G H S 2 j A N T S h B R S G 8 A w v 8 I q e 0 B t 6 R x + L 1 Q L K b 4 7 h D 9 D n D y 4 b l D A = < / l a t e x i t > f 2 < l a t e x i t s h a 1 _ b a s e 6 4 = " y 6 0 S M K n k P h g O i C N e 4 D F F + D 5 U t 9 g = " > A A A B + 3 i c b V D L S g N B E O y N r x h f U Y 9 e B o P g K e y G g D k G v H i M Y B 6 Q r G F 2 0 p s M m Z l d Z m a F E P I L X v X u T b z 6 M V 7 9 E n e T P W h i Q U N R 1 U 0 1 F c S C G + u 6 X 0 5 h a 3 t n d 6 + 4 X z o 4 P D o + K Z + e d U y U a I Z t F o l I 9 w J q U H C F b c u t w F 6 s k c p A Y D e Y 3 m Z + 9 w m 1 4 Z F 6 s L M Y f U n H i o e c U Z t J 4 W O t N C x X 3 K q 7 B N k k X k 4 q k K M 1 L H 8 P R h F L J C r L B D W m 7 7 m x 9 e d U W 8 4 E L k q D x G B M 2 Z S O s Z 9 S R S U a f 7 7 8 d U G u U m V E w k i n o y x Z q r 8 v 5 l Q a M 5 N B u i m p n Z h 1 L x P / 9 Q K 5 l m z D h j / n K k 4 s K r Y K D h N B b E S y I s i I a 2 R W z F J C m e b p 7 4 R N q K b M p n V l p X j r F W y S T q 3 q 1 a v 1 + 3 q l 2 c j r K c I F X M I 1 e H A D T b i D F r S B w Q S e 4 Q V e n Y X z 5 r w 7 H 6 v V g p P f n M M f O J 8 / Z W W U R Q = = < / l a t e x i t > f k < l a t e x i t s h a 1 _ b a s e 6 4 = " y K o 6 g a 4 B 4 y I < l a t e x i t s h a 1 _ b a s e 6 4 = " 7 + r G R O / 0 z 8 J z w i P X Z u X O s t T 8 J 0 o = " > A A A C C n i c b V D L S s N A F J 3 4 r P W V 6 t J N s A i u S i I F u y y 4 c V n B P q A N Y T K d t E N n J m H m R i k h f + A v u N W 9 O 3 H r T 7 j 1 S 5 y 0 W W j r g Q u H c + 7 l X E 6 Y c K b B d b + s j c 2 t 7 Z 3 d y l 5 1 / + D w 6 N i u n f R 0 n C p C u y T m s R q E W F P O J O 0 C A 0 4 H i a J Y h J z 2 w 9 l N 4 f c f q N I s l v c w T 6 g v 8 E S y i B E M R g r s 2 i j E K o v y I B v B l A L O q 4 F d d x v u A s 4 6 8 U p S R y U 6 g f 0 9 G s c k F V Q C 4 V j r o e c m 4 G d Y A S O c 5 t V R q m m C y Q x P 6 N B Q i Q X V f r Z 4 P X c u j D J 2 o l i Z k e A s 1 N 8 X G R Z a z 0 V o N g W G q V 7 1 C v F f L x Q r y R C 1 / I z J J A U q y T I 4 S r k D s V P 0 4 o y Z o g T 4 3 B B M F D O / O 2 S K F S Z g 2 i t K 8 V Y r W C e 9 q 4 b X b D T v m v V 2 q 6 y n g s 7 Q O b p E H r p G b X S L O q i L C H p E z + g F v V p P 1 p v 1 b n 0 s V z e s 8 u Y U / Y H 1 + Q M N k p q 6 < / l a t e x i t > v(·) < l a t e x i t s h a 1 _ b a s e 6 4 = " o Q p n k + n a L D a m k D H W K R R 2 K s x z B K m l d V Z x q p X p X L d V r i 3 g K 5 I y c k z J x y D W p k 1 v S I E 3 C y C N 5 J i / k 1 X g y 3 o x 3 4 2 P e u m Y s Z k 7 I H x i f P 9 7 j n n M = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " g P F h G 5 L 5 M x u 5 V y w p U v e Q d O Y D z n k = " > A A A B / X i c b V D L S g M x F L 2 p r 1 p f V Z d u g k V w V W a k Y J c F N y 4 r 2 A e 0 Q 8 m k m T Y 2 y Q x J R i h D 8 R f c 6 t 6 d u P V b 3 P o l p u 0 s t P X A h c M 5 9 3 I u J 0 w E N 9 b z v l B h Y 3 N r e 6 e 4 W 9 r b P z g 8  x U x m 6 T U n s 2 K x 6 c / F f L 5 Q r y T a q B x l X S W q Z o s v g K B X Y x n h e B R 5 y z a g V U 0 c I 1 d z 9 j u m Y a E K t K 6 z k S v F X K 1 g n 7 a u q X 6 v W 7 m q V R j 2 v p w h n c A 6 X 4 M M 1 N O A W m t A C C g / w D C / w i p 7 Q G 3 p H H 8 v V A s p v T u E P 0 O c P 8 2 u V x g = = < / l a t e x i t > x < l a t e x i t s h a 1 _ b a s e 6 4 = " b G x i + U F x / o e v b W H K Q H N s I E 6 L M I c = " > A A A B / X i c b V D L S g M x F L 2 p r 1 p f V Z d u g k V w V W a k Y J c F N y 4 r 2 A f Y o W T S T B u b Z I Y k I 5 a h + A t u d e 9 O 3 P o t b v 0 S 0 3 Y W 2 n r g w u G c e z m X E y a C G + t 5 X 6 i w t r 6 x u V X c L u 3 s 7 u 0 f l A + P 2 i Z O N W U t G o t Y d 0 N i m O C K t S y 3 g n U T z Y g M B e u E 4 6 u Z 3 3 l g 2 v B Y 3 d p J w g J J h o p H n B L r p H Y v l N n j t F + u e F V v D r x K / J x U I E e z X / 7 u D W K a S q Y s F c S Y O 9 9 L b J A R b T k V b F r q p Y Y l h I 7 J k N 0 5 q o h k J s j m 3 0 7 x m V M G O I q 1 G 2 X x X P 1 9 k R F p z E S G b l M S O z L L 3 k z 8 1 w v l U r K N 6 k H G V Z J a p u g i O E o F t j G e V Y E H X D N q x c Q R Q j V 3 v 2 M 6 I p p Q 6 w o r u V L 8 5 Q p W S f u i 6 t e q t Z t a p V H P 6 y n C C Z z C O f h w C Q 2 4 h i a 0 g M I 9 P M M L v K I n 9 I b e 0 c d i t Y D y m 2 P 4 A / T 5 A z w N l f Q = < / l a t e x i t >D < l a t e x i t s h a 1 _ b a s e 6 4 = " H a R a c + s X n Q f D h H P / E 8 I J n x E V w B o = " > A A A B / n i c b V C 7 S g N B F L 0 b X z G + o p Y 2 g 0 G w C r s S M G V A C 8 s I 5 g H J E m Y n s 8 m Q e S w z s 0 J Y A v 6 C r f Z 2 Y u u v 2 P o l T p I t N P H A h c M 5 9 3 I u J 0 o 4 M 9 b 3 v 7 z C x u b W 9 k 5 x t 7 S 3 f 3 B 4 V D 4 + a R u V a k J b R H G l u x E 2 l D N J W 5 Z Z T r u J p l h E n H a i y c 3 c 7 z x S b Z i S D 3 a a 0 F D g k W Q x I 9 g 6 q d O P s M 5 u Z 4 N y x a / 6 C 6 B 1 E u S k A j m a g / J 3 f 6 h I K q i 0 h G N j e o G f 2 D D D 2 j L C 6 a z U T w 1 N M J n g E e 0 5 K r G g J s w W 7 8 Teacher models Private voting < l a t e x i t s h a 1 _ b a s e 6 4 = "

Problem Settings and Goals
This paper considers a private dataset D consisting of n individuals' data points (x i , y i ), with i ∈ [n], drawn i.i.d. from an unknown distribution Π. Therein, x i ∈ X is a feature vector that may contain a protected group attribute a i ∈ A ⊂ X, and y i ∈ Y = [C] is a C-class label. For example, consider a classifier that needs to predict criminal defendant's recidivism. The training example features x i may describe the individual's demographics, education, occupation, and crime committed, the protected attribute a i , if available, may describe the individual's gender or ethnicity, and y i represents whether or not the individual has high risk to reoffend.
This paper studies the fairness implications arising when training privacy-preserving semi-supervised transfer learning models. The setting is depicted in Figure 1. We are given an ensemble of teacher , with each f i : X → Y trained on a non-overlapping portion D i of D. This ensemble is used to transfer knowledge to a student modelf θ : X → Y, where θ denotes a vector of real-valued parameters associated with modelf .
The student modelf is trained using a public datasetD = {x i } m i=1 with samples drawn i.i.d. from the same distribution Π considered above but whose labels are unrevealed. The paper focuses on learning classifierf θ using knowledge transfer from the teacher model ensemble T while guaranteeing the privacy of each individual's data (x i , y i ) ∈ D. The sought model is learned by minimizing the regularized empirical risk function where : Y × Y → R + is a loss function and measures the performance of the model, v : Y k → Y is a voting scheme used to decide the prediction label from the ensemble T , with T (x) used as a shorthand for { f i (x)} k i=1 , and λ > 0 is a regularization parameter. The paper focuses on learning classifiers that protect the disclosure of the individual's data using the notion of differnetial privacy and it analyzes the fairness impact (as defined below) of privacy on different groups and individuals.

Privacy
Privacy is achieved by using a differentially private versionṽ of the voting function v, defined as which perturbs the reported counts # j (T (x)) = |{i : i ∈ [k], f i (x) = j}| associated to label j ∈ Y, via additive Gaussian noise of zero mean and standard deviation σ. The overall approach, called PATE, guarantees ( , δ)-differential privacy, with privacy loss scaling with the magnitude of the standard deviation σ and the size of the public datasetD [17]. A detailed discussion reviewing the privacy analysis of PATE is reported in Appendix A. Throughout the paper, the privacy-preserving parameters of the modelf are denoted withθ.

Fairness
The fairness analysis focuses on the notion of excessive risk [27,29]. It defines the difference between the private and non private risk functions: where the expectation is defined over the randomness of the private mechanism, S is a subset of D, andθ denotes the private student's model parameters while θ= argmin θ L(θ;D, T ). The above definition captures both individual R({x}, T ) excessive risk for a sample x and group R(D ←a , T ) excessive risk for a group a, whereD ←a denotes the subset ofD containing exclusively samples whose group attribute is a ∈ A. This paper uses shorthands R(x) and R(D ←a ) to denote R(x, T ) and R(D ←a , T ).
Finally, this paper assumes that the private mechanisms are non-trivial, i.e., they minimize the population-level excessive risk R(D) and the fairness goal is to minimize excessive risk difference among all individuals and/or groups.

PATE Fairness Analysis: Roadmap
The next sections focus on two orthogonal aspects of PATE: the algorithm's parameters and the public student data distribution characteristics and analyze their fairness impact.
Within the algorithm's parameters, in addition to the privacy variable σ, the paper reveals two surprising aspects which have a direct impact on fairness: The size k of the teacher ensemble and the regularization parameter λ associated with the student risk function. Regarding the public student data's characteristics, the paper shows that the magnitude of the sample input norms x and the distance of a sample to the decision boundary (denoted s(x)) play decisive roles to exacerbate the excessive risk induced by the student model. These aspects are illustrated schematically with green dotted lines in Figure 1.
Several aspects of the analysis in this paper rely on the following definition. Definition 2 (Flipping probability). Given a data sample (x, y) ∈ D, for an ensemble model T and voting scheme v, the flipping probability of T is defined as: It connects the voting confidence of the teacher ensemble with the perturbation induced by the privacy-preserving voting scheme, and will be instrumental in the fairness analysis introduced below.
The following sections use several standard datasets including UCI Adults, Credit card, Bank, and Parkinsons [2,12,14] to support the theoretical claims. The results use feed-forward networks with two hidden layers and nonlinear ReLU activations for both the ensemble and student models. All reported metrics are average of 100 repetitions, used to compute the empirical expectations. When not otherwise stated, the experiments refer to the Credit card dataset.
The main paper reports a glimpse of the empirical results, which appears in an extended form in the Appendix (C). Additional description of the dataset and proofs of all theorems are reported in the Appendix.

Algorithm's Parameters
This section focuses on analyzing the algorithm's parameters that affect the disparate impact of the student model outputs. In more details, it shows that, in addition to the privacy parameter σ, the regularization term λ of the empirical risk function L(θ,D, T ) (see Equation (1)) and the size k of the teacher ensemble T largely control the difference between model learned with noisy and clean labels. The fairness analysis reported in this section assumes that the student model loss (·) is convex and decomposable: Definition 3 (Decomposable function). A function (·) is decomposable if there exists a parametric function h θ : X → R, a constant real number c, and a function z : R → R, such that, for x ∈ X, and y ∈ Y: Note that a number of loss functions commonly adopted in machine learning, including the logistic loss and the least square loss function, are decomposable [9,18]. Additionally, while it is common to impose restrictions on the nature of the loss function to render the analysis tractable, our findings are empirically validated on non-linear models, as shown next.
The following theorem sheds light on the unfairness induced by PATE and the dependency with its parameters. It provides an upper bound on the expected difference between the non-private and private student model parameters. As the paper will show in Theorem 3, this quantity is closely related with the excessive risk. Therein, θ andθ represent the parameters of student modelf which are learned as a result of training, respectively, with a clean or noisy voting scheme. Theorem 1. Consider a student modelf θ trained with a convex and decomposable loss function (·). Then, the expected difference between the private and non-private model parameters is upper bounded as follows: where c is a real constant and g x = max θ ∇ θ h θ (x) represents the maximum gradient norm distortion introduced by a sample x. Both c and h are defined as in Equation (5).
The proof relies on λ-strong convexity of the loss function L(·) (see Appendix B). Theorem 1 relates the difference in the expected private and non-private student parameters with three key factors: (1) the regularization term λ, (2) the flipping probability p ↔ x , and (3) the the maximum gradient norm distortion g x induced by a sample x. The former two factors are mechanisms-dependent components and the subject of study of this section. As it will be shown next, they are controlled by the size k of the teacher ensemble and the noise parameter σ. The discussion about data dependent components, including those related with the gradient norms, is delegated to Section 7.
Throughout the paper, the quantity θ −θ is referred to as model sensitivity to privacy, or simply model sensitivity, as it captures the effect of the private teacher voting on the student learned model.

The impact of the regularization term λ
The first immediate observation of Theorem 1 is that variations of the regularization term λ can reduce or magnify the difference between the private and non-private student model parameters. Since the model sensitivity E θ −θ relates directly to the excessive risk (see Theorem 3), the regularization term affects the disparate impact of the privacy-preserving student model. (left), as well as the excessive risk R(D ←a ) difference between groups a = 0 and a = 1 (middle). Note, however, that while larger λ values may reduce the model unfairness, they can hurt the resulting model accuracy, as shown in the right plot. The latter is an intuitive and recognized effect of large regularizers factors.

The impact of the teachers ensemble size k
The second aspect considered in this section is the relation between the ensemble size k and the resulting private model fairness. The following result relates the size of the ensemble with its voting confidence. Theorem 2. For a sample x ∈D assume that the teacher models outputsŷ i = f i (x) (i ∈ [k]) are all in agreement. That is,ŷ i =ŷ j for all i, j ∈ [k]. Then, the flipping probability p ↔ x is given by: where Φ(·) is the CDF of the standard normal distribution and σ is the standard deviation in the Gaussian mechanism.
The proof is based on the properties of independent Gaussian random variables.
The analysis above sheds light on the outcome of the teachers voting scheme and its relation with the ensemble size k (as well as the privacy parameter σ). It indicates that larger k values correspond to smaller flipping probability p ↔ x . Combined with Theorem 1, the result suggests that the difference between the private and non-private model parameters is inversely proportional to k.
While for simplicity of analysis Theorem 2 requires the decision of all teachers to agree on a given sample x, our empirical analysis supports this result for the more general scenario where different teachers have different agreements on a sample. Figure 3 (left) illustrates the relation between the number k of teachers and the flipping probability p ↔ x of the ensemble. The plot shows a clear trend indicating that larger ensembles result in smaller flipping probabilities.
Next, analogously to what is reported in Figure 2, Figure 4 shows that increasing k reduces the difference in the expected private and non-private model parameters (left), reduces the group excessive risk difference (middle), and increases the modelf accuracy (right). However, similarly as for the regularization term λ, there is also a downside of using very large ensembles: large values k can reduce the accuracy of the (private and non-private) models. While studying these tradeoffs goes beyond the scope of this work, we believe this behavior is related with the bias-variance tradeoff imposed on the growing ensemble: The larger the ensemble the less data each teacher is given to train their models, thus affecting their voting accuracy. We believe this is an interesting and important direction for future work.
This section concludes with a useful corollary of Theorem 1. Corollary 1 (Theorem 1). Letf θ be a logistic regression classifier. Its expected model sensitivity is upper bounded as: The result above highlights several interesting points. First, in logistic regression, samples with large input norms can have a non negligible impact on fairness. This place emphasis on an nontrivial aspect of the student data properties which may affect fairness and is subject of study of the next section. Next, notice the similarities between Equation (8) and Equation (22); In the former, gradient norms x multiply the associated flipping probabilities p ↔ x in place of the gradient norms g x . Thus the result above indicates the presence of a relation between gradient norms and input norms, which is further highlighted in Figure 3 (right). The plot illustrates the strong correlation between input norms and their associated gradient norms.

Student's Data Properties
Having examined the algorithmic properties of PATE affecting fairness, this section turns on analyzing a set of properties concerning the student data which regulate the disproportionate impacts of the algorithm. The subsequent set of results shows that the norms of the student's data samples and their distance to the decision boundary are two key factor tied to the exacerbation of excessive risk in PATE.
The following is a corollary of Theorem 1 and bounds the second order statistics of the model sensitivity to privacy. Corollary 2 (Theorem 1). Given the same settings and assumption of Theorem 1, it follows: Note that, similarly to as shown by Corollary 1, whenf θ is a logistic regression model, the gradient norm g x in Equation (9) can be substituted with the input norm x .
The result above is useful to derive an upper bound on the excessive risk, as illustrated in the following theorem. Theorem 3. Let (·) be a β x -smooth loss function. The excessive risk R(x) of a sample x is upper bounded as: where, U 1 = E θ −θ and U 2 = E θ −θ 2 capture the first and second order statistics of the model sensitivity.
The proof of the above theorem relies on Theorem 1 and Corollary 2, which provide bounds for the first and second order statistics of the model sensitivity, and on the properties of smooth functions.
Theorem 3 provides an upper bound on the (individual) excessive risk. It shows the presence of three central factors controlling this excessive risk: (1) the gradient norm ∇ θ (f θ (x), y) for a sample x, (2) the smoothness parameter β x associated with a sample x, and (3) the model sensitivity (captured by terms U 1 and U 2 ). As the paper shows next, these seemingly unrelated factors are controlled indirectly by two key data aspects: the samples input norms and their distance to the decision boundary. The rest of the section focuses on logistic regression models, however, as our experimental results illustrate, the observations extend to complex nonlinear models as well.

The impact of the data input norms
First notice that the norm x of a sample x strongly influences the quantities U 1 and U 2 , as already observed by Corollary 1. This aspect is further illustrated in Figure 5 (left), which shows a strong correlation between the input norms and the expected model sensitivity. Thus, samples with higher input norms may have a nontrivial impact to the model sensitivity and, in turn, to the private model disparate impacts.
Next, the following proposition sheds light on the relation between the norm of a sample x and its associated gradient norm ∇ θ (f θ (x), y) .

Proposition 1. Letf θ be a logistic regression binary classifier with cross entropy loss function
. For a given sample (x, y) ∈D, the gradient ∇ θ (f θ (x), y) is given by: Recall that gradient norms have a proportional effect on the upper bound of the excessive risk (Equation (10)). Notice further how applying the norm on both side of Equation (11) illustrates the relation between the gradients and inputs norms. Thus, the relation above sheds further light on the weight that samples with large norms may have in controlling their associated excessive risk. This aspect can be appreciated in Figure 5 (right), which shows a strong correlation between these two quantities.
The result above can be generalized to multi-class classifiers, as shown in Appendix C.5.
Finally, the discussion notes that the smoothness parameter β x captures the local flatness of the loss function at a point x. A derivation of β x for logistic regression classifier is provided below.

Proposition 2.
Consider again a binary logistic regression as in Proposition 1. The smoothness parameter β x for a sample x is given by [22]: The above clearly illustrates the relationship between input norms x and the smoothness parameters β x .
To summarize, propositions 1 and 2 illustrate that individuals x with large (small) input norms tends to have large (small) gradient norm and smoothness parameters, thus controlling the model sensitivity and, in turn, the excessive risk R(x). An extended analysis of the above claim is provided in Appendix C.

The impact of the distance to decision boundary
As mentioned in the previous section, the flipping probability p ↔ x associated with a sample x ∈D directly controls the model sensitivity E[ θ −θ ]. Beside the discussed factors, this section further studies which characteristics of sample x can causes it to have a high flipping probability. Intuitively, samples close to the decision boundary are associated to small ensemble voting confidence and vice-versa. To illustrate this intuition the paper borrows the concept of closeness to the decision boundary from Tran et al. [23].
Definition 4 (Closeness to decision boundary). Let f θ be a C-classes classifier trained using dataD with its true labels. The closeness to the decision boundary s(x) is defined as: where f θ,c denotes the softmax probability for class c.
The above, (together with Theorem 5 of [23]) illustrate that large (small) s(x) values are associated to close (distant) projections of point x to the model decision boundary. The concept of closeness to the decision boundary gives a way to indirectly quantify the flipping probability of a sample. Empirically, the correlation between the distance to decision boundary of sample x and its flipping probability p ↔ x is illustrated in Figure 6 (left). The plots are once again generated using a neural network with nonlinear objective and the relation holds for all datasets analyzed. Notice the strong positive correlation between these two quantities. The plot indicates that the samples that are close to the decision boundary will have a higher probability of "flipping" their label, thus resulting in worse excessive risks. Finally, the proportional effect of the flipping probability on the excessive risks is illustrated in Figure 6 (right). Once again, the plot clearly illustrates that large flipping probabilities p ↔ x imply large excessive risks.

Mitigation solution
The previous sections highlighted the presence of several algorithmic and data-related factors which affect the disparate impact of the student model. A common role of these factors was their effects on the model sensitivity E θ −θ which, in turn, is related with the excessive risk of different groups, whose difference we would like to minimize.
Motivated by these observations, this section proposes a mitigating strategy that aims at reducing the sensitivity of the private model parameters. To do so, the paper exploits the idea of soft labels (as defined below). When using the traditional voting process (denoted hard labels in this section), in low voting confidence regimes small perturbations (aka additive noise) may significantly affect the result of the voting scheme. Consider, for example, the case of a binary classifier where for a sample x, k /2 + 1 teachers vote for label 0 and k /2 − 1 for label 1, for some even ensemble size k. When perturbations are induced to these counts to guarantee privacy, the process can report the incorrect label (ŷ = 1) with high probability. As a results, the private student model parameters obtained from private training with hard labels can be sensitive to the noisy voting, and may deviate significantly from the non-private one. This issue can be partially addressed by the introduction of soft labels: and their privacy-preserving counterparts: To exploit soft labels, the training step of the student model is altered to use the following loss function: which can be considered as a weighted version of the original loss function (f θ (x), c) on class label c, whose weight is its confidenceα c . Note that (f θ (x),α) = (f θ (x)) when all teachers in the ensemble chose the same label. The privacy analysis for this model is similar that of classical PATE and is reported in Appendix A.
The effectiveness of this scheme is demonstrated in Figure 7. The experiment settings are reported in details in the Appendix and reflect those described at the end of Section 5. The left subplot shows the relation between the model sensitivity E θ −θ at varying levels of the privacy loss (dictated by the noise level σ). Notice how the student models trained using soft labels reduce their sensitivity to privacy when compared to the counterparts that use hard labels.
The middle and right plots of Figure 7 illustrate the effects of the proposed mitigating solution in terms of utility/fairness tradeoff on the private student model. The top subplots illustrate the group excessive risks R(D ←0 ) and R(D ←1 ) associated with minority (0) and majority (1) groups while the bottom subplot illustrate the accuracy of the model at increasing values of the privacy loss . Notice how soft labels can reduce the disparate impacts in private training (top), which consistently reduces the difference in excessive risks between two groups, suggesting an improvement in fairness. Finally, notice that while fairness is improved there is seemingly no cost in accuracy. On the contrary, using soft labels produces comparable or better models to the counterparts produced with the hard labels.
Additional experiments, including illustrating the behavior of the mitigating solution at varying of the number k of teachers are reported in the appendix and the general message is consistent with what described above. Finally, an important benefit about the proposed solution is that it does not require the protected group information (a ∈ A) to be part of the training data. Thus, it is applicable in challenging situations when it is not feasible to collect or use protected features (e.g., under the General Data Protection Regulation (GDPR) [11]).
These results are significant. They suggest that this mitigating solution can be an effective strategy for improving the disparate impact of private model ensembles without sacrificing accuracy.

Discussion
We note that the proposed mitigating solution relates to concepts explored in robust machine learning. In particular, Papernot et al. [16] noted that training a classifiers with soft labels can increase its robustness against adversarial samples. This connection is not coincidental. Indeed, the model sensitivity is affected by the voting outcomes of the teacher ensemble (Theorems 1 and 3). Similarly to robust ML models being insensitive to input perturbations, strongly agreeing ensemble will be less sensitive to noise and vice-versa.
Finally, we notice that the use of more advanced voting schemes, such as the interactive GNMAX [17], may produce different fairness results. While this is an interesting avenue for extending our analysis, sophisticated voting schemes may introduce sampling bias (e.g., interactive GNMAX may exclude samples with low ensemble voting agreement). Such bias may trigger some nontrivial unfairness issues on its own.

Conclusions
This work was motivated by the recent observations regarding the effects of differential privacy to the disparate impacts of machine learning models. The paper introduced a notion of fairness that relies on the concept of excessive risk and analyzed this notion in the Private Aggregation of Teacher Ensembles (PATE) [17], an important privacy-preserving machine learning framework used in semisupervised settings or when one wishes to protect the data labels. This paper isolated key components related with the algorithms parameters and the public training data characteristics which are responsible for exacerbating the disparate impacts, it studied the factors affecting these components, and introduced a mitigation solution.
Given the increasing presence of privacy-preserving data-driven algorithms in consequential decisions, we believe that this work may represents an important and broadly applicable step toward understanding the sources of disparate impacts observed in differentially private learning systems.

A Privacy Analysis
This section provides the privacy analysis for the proposed mitigation solution. In PATE with the noisy-max scheme presented in Equation (2) of the main paper (also called GNMAX), the privacy budget is used for releasing the voting labelsṽ(T (x i )) (a.k.a. hard labels) for each of the m public data samples x i ∈D according to: The proposed mitigation solutions, instead, releases privately the voting counts (# c (T (x i )) + N(0, σ 2 )) C c=1 and use these noisy counts to construct the soft-labels, see Equation (5). Using an analogous analysis as that provided in [17], adding or removing one individual sample x from any disjoint partition D i of D can change the voting count vector by at most two. This value of the query sensitivity is obtained by GNMAX [17]. Therefore the privacy cost for releasing hard labels or soft-labels is equivalent.
Next, this section provides the privacy computation given by Gaussian mechanism which adds Gaussian noise with standard deviation σ to the voting counts.
The privacy analysis of PATE with hard or soft-labels is based on the concept of Renyi differential privacy (RDP) [13]. In either implementations, the process uses the Gaussian mechanism to add independent Gaussian noise to the voting counts. The following Proposition 3 (from [17]) derives the privacy guarantee for GNMAX. Proposition 3. The GNMAX aggregator with private Gaussian noise N(0, σ 2 ) satisfies (γ, γ /σ 2 )-RDP for all γ ≥ 1.

B Missing Proofs
This section contains the missing proofs associated with the theorems presented in the main paper. The theorems are restated for completeness. Theorem 1. Consider a student modelf θ trained with a convex and decomposable loss function (·). Then, the expected difference between the private and non-private model parameters is upper bounded as follows: where c is a real constant and g x = max θ ∇ θ h θ (x) represents the maximum gradient norm distortion introduced by a sample x. Both c and h are defined as in Equation (5).
Proof of Theorem 1 requires the following Lemma 1 from [21] on the property of strongly convex functions. Lemma 1 (Shalev-Shwartz [21]). Let L(θ) be a differentiable function. Then L(θ) is λ-strongly convex iff for all vectors θ, θ : where the first inequality is due to definition of g x i = max θ ∇ θ h θ (x i ) and the second inequality is due to the general triangle inequality . Since |ρ i | is a Bernoulli random variable, in which Thus, it follows that: which concludes the proof.
Theorem 2. For a sample x ∈D assume that the teacher models outputs f i (x) are in agreement for all i ∈ [k]. Then, the flipping probability p ↔ x is given by: where Φ(·) is the CDF of the standard normal distribution, and σ is the standard deviation in the Gaussian mechanism.
Proof. By assumption, for any given sample x, all teachers agree in their predictions, so w.l.o.g., assume k teachers output label 0, while none of them outputs label 1. Next, let ψ, ψ ∼ N(0, σ 2 ) be two independent Gaussian random variables which are added to true voting counts, k and 0, respectively. The associated flipping probability is: since ψ, ψ are two independent Gaussian random variable with zero mean and standard deviation of σ. Therefore, ψ − ψ ∼ N(0, 2σ 2 ). Thus: Hence, the flipping probability will be: ). Corollary 1 (Theorem 1). Letf θ be a logistic regression classifier. Its expected model sensitivity is upper bounded as: Proof. The loss function (f θ (x), y) of a logistic regression classifier with binary cross entropy loss can be rewritten as follows: Hence, (·) is decomposable by Definition 3 with h θ (x) = −θ T x, c = 1 and z(h) = − log( exp(h) 1+exp(h) ). Applying Theorem 1 with g x = max θ ∇ θ h θ (x) = max θ ∇ θ − θ T x = x , and c = 1, gives the intended result. Bank dataset, where the task is to predict if a user subscribes a term deposit or not and the group labels are defined by age: people whose age is less than vs greater than 60 years old [2]. 3. Parkinsons dataset, where the task is to predict if a patient has total UPDRS score that exceeds the median value, and the group labels are defined by gender: female vs male [12]. 4. Credit Card dataset, where the task is to predict if a customer defaults a loan or not. The group labels are defined by gender: female vs male [3].
Each dataset has been standardized to render its features having zero mean and unit standard deviation. Each dataset was partitioned into three disjoint subsets: private set, public train, and test set, as follows. 75% of the dataset was used as private data and the rest for public data. For the public data, 200 samples were randomly selected to train the student model and the rest of the data was used as a test set to evaluate that model.

Models' Setting
To illustrate the tightness of the upper bound provided in Corollary 1, the paper uses a logistic regression model executed over 1000 runs to estimate the expected model sensitivity E θ −θ . For all other experiments, the paper uses a neural network with two hidden layers and nonlinear ReLU activations for both the ensemble and student models. All reported metrics are an average of 100 repetitions, used to compute the empirical expectations. The batch size for stochastic gradient descent was fixed to 32 and the learning rate to η = 1e − 4.

C.2 The impact of regularization parameter
This section provides further empirical supports regarding impact of the regularization parameter λ to the accuracy and fairness trade-off. As shown in Theorem 1, increasing λ reduces the model sensitivity E θ −θ , which in turns decreases the group excessive risk R(D ←a ) (for any group a ∈ A) by Theorem 3. On the other hand, large regularization can negatively impact the model accuracy. Figure 8 illustrates this discussion. It shows how model sensitivity (left), excessive risk difference between two groups (middle), and utility (right) vary according to λ.

C.3 The impact of teachers ensemble size k
This section illustrates the effects of varying the teacher ensemble sizes k with respect to two factors:  Recall that Theorem 2 shows that larger k values correspond to smaller flipping probability p ↔ x . This dependency is reported in Figure 9. Notice how increasing the number of teachers k reduces the flipping probability p ↔ x on all samples x. Next, concerning the fairness analysis, we provide additional empirical support on the effects of k to the model sensitivity, the difference between the group excessive risk, and the utility of the PATE models. These metrics are summarized in Figure 10. A similar trend with what observed for the regularization parameter λ can be observed here, when varying the ensemble size k. Additionally, when the values k grow large they produce models with small model sensitivity as well as low accuracy, but the unfairness, measured by the excessive risk difference between two groups, reduces. This observation can be explained by looking at Figure 9 and by Theorem 1: Large k values imply smaller flipping probability, which, in turn, reduce the model sensitivity. Notice also that Theorem 3 shows that small model sensitivities can reduce the level of unfairness.

C.4 The impact of the data input norm
This sections provides further experimental results regarding the relation between the input norms with (1) the private model sensitivity and (2) the model excessive risk.
Regarding the first relation, Corollary 1 shows that the larger the input norm x the larger the model sensitivity. To illustrate this claim, for each dataset, the experiments vary the range of the input norm x and report the associated values of the expected model sensitivity. 11 clearly illustrates a strong, non-decreasing, relation between input norms and the model sensitivity.
On the other hand, large input norms can affect the excessive risk because they directly control the gradient norms, by the analysis performed in Subsection C.5. By Theorem 3, the individuals generating large gradient norms can suffer from large excessive risk. Similarly, the individuals associated with large input data norms-which are often observed at the tail of data distribution-are more impacted in terms of accuracy drop, when compared to individuals with smaller input norms. These claims are illustrated in Figure 12, which shows the Spearman correlation between input norms and the associated individual excessive risk of the model. On all datasets, observe the positive relation between the data input norm and the excessive risk.

C.5 Connection between input norm and gradient norm
Propositions 1 and 2 showed the presence of a strong relation between the individual input norms x and their associated gradient norms at the optimal model parameter θ, ∇ θ (f θ (x), y) , for logistic regression classifiers. This subsection extends the analysis to non-linear models. In particular, it will show a similar connection between the gradient norms and the input norms for a neural network with a single hidden layer. We start by considering the following settings: Settings Consider a neural network modelf θ (x) is a d dimensional input vector, τ(·) is an activation function, the parameters θ1 ∈ R H×C , θ2 ∈ R d×H , and the cross entropy loss (f θ (x), y) = − C c=1 y c logf θ,c (x). Let O = τ( θ T 2 x) ∈ R H be the vector (O 1 , . . . , O H ) of H hidden nodes of the network. Denote the variables h j = d i=1 θ 2, j,i x i as the j-th hidden unit before the activation function. Next, denote θ 1, j,k ∈ R as the weight parameter that connects the j-th hidden unit h j with the c-th output unitf c and θ 2,i, j ∈ R as the weight parameter that connects the i-th input unit x i with the j-th hidden unit h j .
Given the settings above, we now show the dependency between gradient norms and input norms. First notice that we can decompose the gradients norm of this neural network into two layers as follows: ∇ θ (f θ (x), y) 2 = ∇ θ1 (f θ (x), y) 2 + ∇ θ2 (f θ (x), y) 2 .
Notice that: Applying, Equation (14) from Sadowski [20], it follows that: which highlights the dependency of the gradient norm ∇ θ2 (f θ (x), y) and the input norm x . Figure  13 provides empirical evidence supporting this dependency. It shows a strong positive correlation between input norms and the gradient norms at individual levels on all datasets analyzed.

C.6 Upper bound of the expected model sensitivity
The following provides empirical results for Corollary 1 on four benchmark datasets. As indicated in this corollary, the expected model sensitivity is bounded by 1 mλ x∈D p ↔ x x . Figure 14 illustrates the tightness of this bound by plotting the RHS and the LHS values of Equation (8)

C.7 Effectiveness of mitigation solution
This subsection provides extended empirical results regarding the effectiveness of the proposed mitigation solution, presented in Section 8.
It reports a comparison between training PATE with hard and soft labels when k = 20 ( Figure 15) and when k = 150 ( Figure 16). The analysis compares the models learned with hard and soft labels in terms of utility and fairness. In each figure, the top subplots show the group excessive risks R(D ←0 ) and R(D ←1 ) associated with minority (0) and majority (1) groups while the bottom subplot illustrate the accuracy of the model, at increasing of the privacy loss . The figures clearly show how the models trained using soft labels achieve improved fairness (it reduces the excessive risk differences between the groups) without sacrificing accuracy.
Finally, recall that the mitigation solution does not require the availability of group labels during training. This challenging settings are of importance under the scenario when it is not feasible to collect or use protected features (e.g., under GDPR).