Inherent Tradeoffs in Learning Fair Representations††,‡Han Zhao , Geoffrey J. Gordon†‡Carnegie Mellon University, Microsoft Research Montreal
han.zhao@cs.cmu.edu, geoff.gordon@microsoft.com
Overview

Preliminary

Recidivism Prediction:<latexit sha1_base64="DtnBsMFJKt0GW8M0Mud6iLS7M5Q=">AAAETnicfZPNbhMxEMfdboEQvlo4clkRVeIUJQWpXCJVLZXCrQ1NWymJKq93NrHij63tbbKx9gm4wntx5UW4IfCmQUkcwUgrjeb3nxl71hOljGrTaPzY2g52Hjx8VHlcffL02fMXu3svL7XMFIEukUyq6whrYFRA11DD4DpVgHnE4Coan5T86g6UplJcmDyFAcdDQRNKsHGh89bNbq1Rb8wt3HSaC6eGFnZ2sxcc9mNJMg7CEIa17jUbqRlYrAwlDIpqP9OQYjLGQ+g5V2AOemDnJy3CfReJw0Qq9wkTzqOrGRZzrXMeOSXHZqR9Vgb/xcyIF36s7KKLcG5rzImNlEyvZ5R1N8O9zCQfBpaKNDMgyP0tkoyFRoblTMOYKiCG5c7BRFE3iJCMsMLEuMlX90O/RYpnsqiuteB4DEpK7iaFBQHmDiBgQiTnWMS2T0Vc2H6ZG0X2U+HRCdDhyPwVJHbiC6bTJZz6MM+XMPfhbLaEs42+k//01KlYUIKZ/byJjQJYUVz4inZ7hbZ9Ckq5B2X7d1hBqimTwhPEbnlWCnz0C8SQwG1ZgJQv2T1E0fJb3DpNYVsrEk9xOk2Xv+XU79DpLGGnKNyqNf3F2nQuD+rNd/WD8/e1o+PF0lXQa/QGvUVNdIiOUBudoS4iCNAX9BV9C74HP4Nfwe976fbWIucVWrOdyh/3CoRU</latexit>

Defendant

1ccc∆DP(Y) := |D0(Y= 1) − D1(Y= 1)|.

prior arrests
B prior sentences CB
CB
Cage
B
C
B drug history CB
CB
Crace
B
CBage at first arrestCB
C
Beducation historyCB
C@ vocation history AgenderPredictor• Da(·) = PrD (· | A = a), ∀a ∈ {0, 1}.
• ∆DP(Y ) = ∆BR , by definition.
ccc• ErrD (Y) = ED [Y 6= Y].

Recidivism?: {0, 1}• Joint distribution D over input X ∈ Rd, label Y ∈ {0, 1} andsensitive attribute A ∈ {0, 1}.
c• A (randomized) classifier Y= h(g(X)) ∈ {0, 1}.
• Feature mapping g : X → Z.
• A classifier is said to be fair, or satisfy statistical parity if:
ccc
PrD (Y = 1 | A = 0) = PrD (Y = 1 | A = 1) ⇔ Y ⊥ A.
• Base rate: Pr(Y = 1 | A = a), a ∈ {0, 1}.
∆BR := | Pr(Y = 1 | A = 0) − Pr(Y = 1 | A = 1)|.
Learning Fair Representations:

Defendant<latexit sha1_base64="/Nqzz8mjoLYeKQvmI2jBWmr3N8A=">AAAFNnicfZPNbhMxEMc3bYASvlI4crGoKnGqklKpXCpVQKVwQCqlX1I2irze2cSK197a3iabZd+LV+HCDfXKIzCbBrJxKD6N5/efGdszDhLBjW21vtfW1uv37j/YeNh49PjJ02fNzefnRqWawRlTQunLgBoQXMKZ5VbAZaKBxoGAi2D0vuQX16ANV/LUZgn0YjqQPOKMWnT1mzd+AAMu8ySmVvNJ0fAtTGyeaK40oVqDsaYgvr/kNyAtSAZVQgdQ2YU6HZAhHl/prOLWlMFyDKGWRFwbOy9WoRCmt6f8R6JrdScagAxBF6Tho/H3Xv3mVmunNVtk1WjPjS1vvo77m+v7fqhYGuNdmaDGdNutxPZyqi1nAvChUgMJZSO8RBdNSWMwvXzWkYJsoyckEb5VpKQlM281IqexMVkcoBIPODQuK513MTuMC9dXVsFuzNYSQ7FVSpjliDLvqrub2uhtL+cyScv23t4iSgWxipSzQ0KugVmRoUGZ5vgQhA0pNtXihDW2iVsioVNVNJZKxHQEWqkYX4riBAk8gIQxU3FMsVs+l2GR+2VsEOQfC4eOgQ+G9o8gyseuYDJZwIkLs2wBMxdOpws4Xak7/k9Nk8g5ZVTkX1ax1QAVxamr6HQqtONS0BoHKvevqYbEcKGkIwjxB1QSfHAThBDBVZmAlZOMgygP3BJXqCnyg4rEURxNkkVbjtwKJycLeFKUX63tfqxV43x3p/1mZ/fz3tbhu/mn2/Beeq+8117b2/cOvY537J15rPapZmpfa0X9W/1H/Wf95la6VpvHvPCWVv3XbyzL3oI=</latexit>

Fair Representations<latexit sha1_base64="DtnBsMFJKt0GW8M0Mud6iLS7M5Q=">AAAETnicfZPNbhMxEMfdboEQvlo4clkRVeIUJQWpXCJVLZXCrQ1NWymJKq93NrHij63tbbKx9gm4wntx5UW4IfCmQUkcwUgrjeb3nxl71hOljGrTaPzY2g52Hjx8VHlcffL02fMXu3svL7XMFIEukUyq6whrYFRA11DD4DpVgHnE4Coan5T86g6UplJcmDyFAcdDQRNKsHGh89bNbq1Rb8wt3HSaC6eGFnZ2sxcc9mNJMg7CEIa17jUbqRlYrAwlDIpqP9OQYjLGQ+g5V2AOemDnJy3CfReJw0Qq9wkTzqOrGRZzrXMeOSXHZqR9Vgb/xcyIF36s7KKLcG5rzImNlEyvZ5R1N8O9zCQfBpaKNDMgyP0tkoyFRoblTMOYKiCG5c7BRFE3iJCMsMLEuMlX90O/RYpnsqiuteB4DEpK7iaFBQHmDiBgQiTnWMS2T0Vc2H6ZG0X2U+HRCdDhyPwVJHbiC6bTJZz6MM+XMPfhbLaEs42+k//01KlYUIKZ/byJjQJYUVz4inZ7hbZ9Ckq5B2X7d1hBqimTwhPEbnlWCnz0C8SQwG1ZgJQv2T1E0fJb3DpNYVsrEk9xOk2Xv+XU79DpLGGnKNyqNf3F2nQuD+rNd/WD8/e1o+PF0lXQa/QGvUVNdIiOUBudoS4iCNAX9BV9C74HP4Nfwe976fbWIucVWrOdyh/3CoRU</latexit>prior arrests
B prior sentences CBCBCage
BC
B drug history CBCBCraceBC
Bage at first arrestC
BCBeducation historyCBC@ vocation history A
genderInput Vectors=1• Total variation lower bound:cAccuracy Parity: ErrD0(Y ) = ErrD1(Y ).

<latexit sha1_base64="/Nqzz8mjoLYeKQvmI2jBWmr3N8A=">AAAFNnicfZPNbhMxEMc3bYASvlI4crGoKnGqklKpXCpVQKVwQCqlX1I2irze2cSK197a3iabZd+LV+HCDfXKIzCbBrJxKD6N5/efGdszDhLBjW21vtfW1uv37j/YeNh49PjJ02fNzefnRqWawRlTQunLgBoQXMKZ5VbAZaKBxoGAi2D0vuQX16ANV/LUZgn0YjqQPOKMWnT1mzd+AAMu8ySmVvNJ0fAtTGyeaK40oVqDsaYgvr/kNyAtSAZVQgdQ2YU6HZAhHl/prOLWlMFyDKGWRFwbOy9WoRCmt6f8R6JrdScagAxBF6Tho/H3Xv3mVmunNVtk1WjPjS1vvo77m+v7fqhYGuNdmaDGdNutxPZyqi1nAvChUgMJZSO8RBdNSWMwvXzWkYJsoyckEb5VpKQlM281IqexMVkcoBIPODQuK513MTuMC9dXVsFuzNYSQ7FVSpjliDLvqrub2uhtL+cyScv23t4iSgWxipSzQ0KugVmRoUGZ5vgQhA0pNtXihDW2iVsioVNVNJZKxHQEWqkYX4riBAk8gIQxU3FMsVs+l2GR+2VsEOQfC4eOgQ+G9o8gyseuYDJZwIkLs2wBMxdOpws4Xak7/k9Nk8g5ZVTkX1ax1QAVxamr6HQqtONS0BoHKvevqYbEcKGkIwjxB1QSfHAThBDBVZmAlZOMgygP3BJXqCnyg4rEURxNkkVbjtwKJycLeFKUX63tfqxV43x3p/1mZ/fz3tbhu/mn2/Beeq+8117b2/cOvY537J15rPapZmpfa0X9W/1H/Wf95la6VpvHvPCWVv3XbyzL3oI=</latexit>

0

Induced distribution by feature mapping g:
Given a feature mapping g : X → Z, define g]D := D ◦ g −1 to be theinduced distribution (pushforward) of D under g, i.e., for any event
E 0 ⊆ Z, g]D(E 0) := D(g −1(E 0)) = D({x ∈ X | g(x) ∈ E 0}).
Theorem: Assume dJS(g]D0, g]D1) ≤ dJS(D0(Y ), D1(Y )) andH(g]D0, g]D1) ≤ H(D0(Y ), D1(Y )), then the following hold:

Demographic Parity Gap (DP Gap):

0=Tradeoff in Fair Representation LearningYbf -divergence: Let P and Q be two probability distributions over thesame space and assume P is absolutely continuous w.r.t. Q (P  Q).
Then for any convex function f : (0, ∞) → R that is strictly convex at
1 and f (1) = 0, the f -divergence of Q from P is defined as dP
Df (P || Q) := EQf  .
dQ
1
The function f is called the generator function of Df (· || ·).
Df (P || Q) f (t)Name• Jensen-Shannon lower bound:
ErrD0(h ◦ g)+ErrD1(h ◦ g) ≥2dJS(D0(Y ), D1(Y )) − dJS(g]D0, g]D1) /2.

• Hellinger lower bound:Symm. Tri.

Kullback-Leibler DKL(P || Q) t log t
7Reverse-KL
DKL(Q || P) − log t
7t+1
Jensen-Shannon DJS(P, Q) t log t√− (t + 1) log( 2 ) 3
3Squared Hellinger H 2(P, Q) (1 − t)2/2
Total VariationdTV(P, Q) |t − 1|/2
3

ErrD0(h ◦ g)+ErrD1(h ◦ g) ≥dTV(D0(Y ), D1(Y )) − dTV(g]D0, g]D1).

77773

Tradeoff between Utility and Fairness

ErrD0(h ◦ g)+ErrD1(h ◦ g) ≥2H(D0(Y ), D1(Y )) − H(g]D0, g]D1) /2.

Fair Representations Lead to Accuracy Parity:
Theorem: For any hypothesis H 3 h : X → Y, the following inequality holds:|ErrD0(h) − ErrD1(h)| ≤ nD0 + nD1 + dTV(D0(X), D1(X))∗∗∗∗+ min {ED0[|h0 − h1 |], ED1[|h0 − h1 |]} .
• nDa, a ∈ {0, 1}: the noise over distribution Da.
• h∗a, a ∈ {0, 1}: the optimal predictor over distribution Da.

<latexit sha1_base64="M8EJx8/jtCbhbNeo9EzqdBy821c=">AAAEWHicfZNLbxMxEMfdJtA2vNpy5LIiqsQpSnioXCpVQKVwK6Fpi7JR5fXOZq34sbW9TTbWfgyu8Lng0+BNg5I4gpFWGs3vPzPesSfKGNWm3f61tV2rP3i4s7vXePT4ydNn+weHl1rmikCfSCbVdYQ1MCqgb6hhcJ0pwDxicBWNP1b86g6UplJcmCKDIccjQRNKsHGhQTihMaTY2G/lzX6z3WrPLdh0OguniRZ2fnNQOw5jSXIOwhCGtR502pkZWqwMJQzKRphryDAZ4xEMnCswBz208zOXwZGLxEEilfuECebR1QyLudYFj5ySY5Nqn1XBfzGT8tKPVV10GcxtjTmxkZLp9Yyq7mZ4kJvk/dBSkeUGBLn/iyRngZFBNd0gpgqIYYVzMFHUDSIgKVaYGHcHjaPAb5HhmSwbay04HoOSkrtJYUGAuQMImBDJORaxDamISxtWuVFkP5cenQAdpeavILETXzCdLuHUh0WxhIUPZ7MlnG30nfynp87EghLM7NdNbBTAiuLCV3S7K7TrU1DKPSgb3mEFmaZMCk8QuzVaKfDJLxBDArdVAVK9ZPcQxYnf4tZpSnuyIvEUZ9NseS1nfodebwl7ZbVqHX+xNp3L163Om9a7L2+bpx8WS7eLXqCX6BXqoGN0irroHPURQRJ9Rz/Qz9rvOqrv1Pfupdtbi5znaM3qh38AKMOGFA==</latexit>bA<latexit sha1_base64="1Q1tPLqFfaHvUv1+9aFbw0GX5LA=">AAAEWHicfZNLbxoxEMedQJuEvpL02MuqKFJPCPpQeomUPiLRW0pDEolFkdc7y1r4sbG9gcXaj9Fr+7naT1MvoQKM2pFWGs3vPzPesSfKGNWm3f61tV2rP3i4s7vXePT4ydNn+weHl1rmikCfSCbVdYQ1MCqgb6hhcJ0pwDxicBWNP1X86g6UplJcmCKDIccjQRNKsHGhQTihMaTY2A/lzX6z3WrPLdh0OguniRZ2fnNQOw5jSXIOwhCGtR502pkZWqwMJQzKRphryDAZ4xEMnCswBz208zOXwZGLxEEilfuECebR1QyLudYFj5ySY5Nqn1XBfzGT8tKPVV10GcxtjTmxkZLp9Yyq7mZ4kJvk/dBSkeUGBLn/iyRngZFBNd0gpgqIYYVzMFHUDSIgKVaYGHcHjaPAb5HhmSwbay04HoOSkrtJYUGAuQMImBDJORaxDamISxtWuVFkv5QenQAdpeavILETXzCdLuHUh0WxhIUPZ7MlnG30nfynp87EghLM7LdNbBTAiuLCV3S7K7TrU1DKPSgb3mEFmaZMCk8QuzVaKfDZLxBDArdVAVK9ZPcQxYnf4tZpSnuyIvEUZ9NseS1nfodebwl7ZbVqHX+xNp3L163Om9a7r2+bpx8XS7eLXqCX6BXqoGN0irroHPURQRJ9Rz/Qz9rvOqrv1Pfupdtbi5znaM3qh38AyqyF/A==</latexit>

Adversary• Representations compete with the adversary to confuse the latter.
Question:
What is the fundamental tradeoff between fairness and utility?
How fair representations affect utility and fairness of thepredictor?

cc

Theorem: Let Y = h(g(X)) be the predictor. If Y satisfies statisticalparity, then ErrD0(h ◦ g) + ErrD1(h ◦ g) ≥ ∆BR (D0, D1).
• If A = Y a.s., then ∆BR (D0, D1) = 1 andErrD0(h ◦ g) + ErrD1(h ◦ g) ≥ 1.
• If A ⊥ Y , then ∆BR (D0, D1) = 0 and
ErrD0(h ◦ g) + ErrD1(h ◦ g) ≥ 0, i.e., no constraint on utility.
• The lower bound is tight, in the sense that there exists problem
instances where the equality holds.

Experiments
Incomeprediction
on
the
Adult
dataset,sensitive
attribute:
gender.
Experiments
Joint Error

Err0 + Err1

Approx. DP

0.4

0.3

<latexit sha1_base64="rttdt/hydocidDOjWiU1JdKwAdI=">AAAEa3icfZPNbhoxEMedQNuUfpHm1uawKkLqCUFaifSAFLWJRG8pDUkkQMjrnQULf2xsb2BZ7aVP02v7Nn2IvkO9QAUYtSOtNJrf3/P32h4/YlSbev3X3n6h+ODho4PHpSdPnz1/UT58ea1lrAh0iWRS3fpYA6MCuoYaBreRAsx9Bjf+5FPOb+5BaSrFlUkiGHA8EjSkBBtbGpaP++fADB6mfY7NWPH0YyfLvJZXrzU+NIflSr1WX4S3mzRWSQWt4nJ4WGj2A0liDsIQhrXuNeqRGaRYGUoYZKV+rCHCZIJH0LOpwBz0IF38RuZVbSXwQqnsJ4y3qG6uSDHXOuG+Veab1S7Li/9iZswzt5a76MxbxBazYiMl09sr8r675V5swtNBSkUUGxBk+RdhzDwjvfzAvYAqIIYlNsFEUXsQHhljhYmx11Kqeq5FhOcyK21ZcDwBJSW3J4UFAWY3IGBKJOdYBGmfiiBb3p/vp58zh06BjsbmryBMp65gNlvDmQuTZA0TF87nazjf8Z3+x1NHYkUJZunXXWwUwIbiylW02xu07VJQyj6otH+PFUSaMikcQWAna6PBudsggBDu8gYkf8n2IYqWa3FnNVna2pA4iotZtL6WC9eh01lDO3J21BruYO0m1ye1xrvayZf3lbPT1dAdoNfoDXqLGqiJzlAbXaIuIugb+o5+oJ+F38Wj4qvi8VK6v7dac4S2olj9A3A2i9k=</latexit>

BR = 0.197

0.2

Implication: When the base rates differ between different demographic groups, then any fair algorithm has to make an error of atleast ∆BR (D0, D1)/2 on one of the groups.

Our Answer: When the base rates differ, any fair classifier has tomake a large error on at least one of the demographic group.

0.1

000.1

1.0

5.050.0<latexit sha1_base64="bCKyyr4lcoQ1HaFYFGCAFAYTz6Y=">AAAEVHicfZTNbtNAEMe3TYASoLRw5GIRVeIUJQWpvVSqBJXCrYSmqRRH1Xo9TlbZD3d33cRZ+SG4wnsh8S4cWKdBcTaCkSyN5vefmfV4x1HKqDbt9q+d3Vr90eMne08bz56/2H95cPjqWstMEegTyaS6ibAGRgX0DTUMblIFmEcMBtH0Y8kH96A0leLK5CmMOB4LmlCCjQsNQuakMb49aLZb7aUF205n5TTRyi5vD2snYSxJxkEYwrDWw047NSOLlaGEQdEIMw0pJlM8hqFzBeagR3Z53iI4cpE4SKRyjzDBMlrNsJhrnfPIKTk2E+2zMvgvZia88GNlF10ES9tgTmykZHozo6y7HR5mJjkdWSrSzIAgD2+RZCwwMignG8RUATEsdw4mirpBBGSCFSbGzb9xFPgtUryQRWOjBcdTUFJyNyksCDB3AAEzIjnHIrYhFXFhwzI3iuznwqMzoOOJ+StI7MwXzOdrOPdhnq9h7sPFYg0XW31n/+mpU7GiBDP7dRsbBVBRXPmKbrdCuz4FpdyFsuE9VpBqyqTwBLFboUqBT36BGBK4KwuQ8ia7iyjO/BZ3TlPYs4rEU1zM0/VnufA79Hpr2CsKt2odf7G2nevjVud96/jLh+b56Wrp9tAb9Ba9Qx10gs5RF12iPiJoir6h7+hH7Wftd939JR6kuzurnNdow+r7fwBuBIUI</latexit>

21

NeurIPS-2019

han.zhao@cs.cmu.edu

Conclusion: When the label distributions are different,
Dec.
12,
2019
aligning both domains while minimizing the source error leads to an