Fair and Optimal Prediction via Post-Processing
Waterloo Arti cial Intelligence InstituteNov. 24th, 2023

fi

Han Zhaohanzhao@illinois.edu
Amazon Visiting Academic
Assistant Professor
Department of Computer Science
University of Illinois Urbana-Champaign

Potential Bias of Data in High-stakes Domains

2

Algorithmic Fairness: Statistical Parity
Statistical Parity (aka Demographic Parity)

̂
Y⊥A
-

In words: The prediction given by an algorithm shouldn’t take thesensitive/protected attribute into account-Dates back at least to Calders et al. 2009: “Building classi ers withindependency constraints”

fi3Fairness Through Blindness
Statistical Parity
Ignorance is bliss?! — Thomas Gray<latexit sha1_base64="Ol1UIw6EF1ZVY5USauXsLpmDs9o=">AAAEbXicfZNbaxNBFMenTdQab6nik1IGQ7EFCYkU60ulUgvxrcamDWRDmZ09mwyZy3Zm0lyWffPT+Kpfxk/hV3A2jSSZoAcWDuf3P+e/cwsTzoyt1X5tbBaKd+7e27pfevDw0eMn5e2nF0YNNYUWVVzpdkgMcCahZZnl0E40EBFyuAwHJzm/vAFtmJLndpJAV5CeZDGjxLrSVXnnZK/9BgeUSAo8/Zjt44AJZwwGO7J/Va7UqrVZ4PWkPk8qaB5nV9uFwyBSdChAWsqJMZ16LbHdlGjLKIesFAwNJIQOSA86LpVEgOmms4VkeNdVIhwr7T5p8ay63JESYcxEhE4piO0bn+XFfzHbF5lfy11MhmexwpzYKsXNakc+d73cGdr4fTdlMhlakPR2FfGQY6twvuU4Yhqo5ROXEKqZ2whM+0QTat3BlHaxb5GQqcpKKxaCDEArJdxOzU7K/YCEEVVCEBmlAZNRlgZ5bximnzOPjoD1+vavIE5HvmA8XsCxDyeTBZz4cDpdwOma7+g/niaRc0oJT7+uY6sBlhTnvqLRWKINn4LW7kKlwQ3RkBjGlfQEkXtbSwM++QMiiOE6H0Dzm+wuojzyLa6dJkuPliSe4nScLI7l1HdoNhewmWXuqdX9h7WeXLyt1t9VD74cVI4/zB/dFnqBXqE9VEeH6Bg10BlqIYq+oe/oB/pZ+F18XnxZ3LmVbm7Me56hlSi+/gNL6Iwc</latexit>

C(X, A ) =) C(X)0=<latexit sha1_base64="DtnBsMFJKt0GW8M0Mud6iLS7M5Q=">AAAETnicfZPNbhMxEMfdboEQvlo4clkRVeIUJQWpXCJVLZXCrQ1NWymJKq93NrHij63tbbKx9gm4wntx5UW4IfCmQUkcwUgrjeb3nxl71hOljGrTaPzY2g52Hjx8VHlcffL02fMXu3svL7XMFIEukUyq6whrYFRA11DD4DpVgHnE4Coan5T86g6UplJcmDyFAcdDQRNKsHGh89bNbq1Rb8wt3HSaC6eGFnZ2sxcc9mNJMg7CEIa17jUbqRlYrAwlDIpqP9OQYjLGQ+g5V2AOemDnJy3CfReJw0Qq9wkTzqOrGRZzrXMeOSXHZqR9Vgb/xcyIF36s7KKLcG5rzImNlEyvZ5R1N8O9zCQfBpaKNDMgyP0tkoyFRoblTMOYKiCG5c7BRFE3iJCMsMLEuMlX90O/RYpnsqiuteB4DEpK7iaFBQHmDiBgQiTnWMS2T0Vc2H6ZG0X2U+HRCdDhyPwVJHbiC6bTJZz6MM+XMPfhbLaEs42+k//01KlYUIKZ/byJjQJYUVz4inZ7hbZ9Ckq5B2X7d1hBqimTwhPEbnlWCnz0C8SQwG1ZgJQv2T1E0fJb3DpNYVsrEk9xOk2Xv+XU79DpLGGnKNyqNf3F2nQuD+rNd/WD8/e1o+PF0lXQa/QGvUVNdIiOUBudoS4iCNAX9BV9C74HP4Nfwe976fbWIucVWrOdyh/3CoRU</latexit>

Defendant

1prior arrests
B prior sentences C
B
C
B
C
age
B
C
B drug history C
B
C
B
C
race
B
C
Bage at first arrestC
B
C
Beducation historyC
B
C@ vocation history A
gender<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>

4Fairness Through Blindness<latexit sha1_base64="Ol1UIw6EF1ZVY5USauXsLpmDs9o=">AAAEbXicfZNbaxNBFMenTdQab6nik1IGQ7EFCYkU60ulUgvxrcamDWRDmZ09mwyZy3Zm0lyWffPT+Kpfxk/hV3A2jSSZoAcWDuf3P+e/cwsTzoyt1X5tbBaKd+7e27pfevDw0eMn5e2nF0YNNYUWVVzpdkgMcCahZZnl0E40EBFyuAwHJzm/vAFtmJLndpJAV5CeZDGjxLrSVXnnZK/9BgeUSAo8/Zjt44AJZwwGO7J/Va7UqrVZ4PWkPk8qaB5nV9uFwyBSdChAWsqJMZ16LbHdlGjLKIesFAwNJIQOSA86LpVEgOmms4VkeNdVIhwr7T5p8ay63JESYcxEhE4piO0bn+XFfzHbF5lfy11MhmexwpzYKsXNakc+d73cGdr4fTdlMhlakPR2FfGQY6twvuU4Yhqo5ROXEKqZ2whM+0QTat3BlHaxb5GQqcpKKxaCDEArJdxOzU7K/YCEEVVCEBmlAZNRlgZ5bximnzOPjoD1+vavIE5HvmA8XsCxDyeTBZz4cDpdwOma7+g/niaRc0oJT7+uY6sBlhTnvqLRWKINn4LW7kKlwQ3RkBjGlfQEkXtbSwM++QMiiOE6H0Dzm+wuojzyLa6dJkuPliSe4nScLI7l1HdoNhewmWXuqdX9h7WeXLyt1t9VD74cVI4/zB/dFnqBXqE9VEeH6Bg10BlqIYq+oe/oB/pZ+F18XnxZ3LmVbm7Me56hlSi+/gNL6Iwc</latexit>

C(X, A ) =) C(X)0=<latexit sha1_base64="DtnBsMFJKt0GW8M0Mud6iLS7M5Q=">AAAETnicfZPNbhMxEMfdboEQvlo4clkRVeIUJQWpXCJVLZXCrQ1NWymJKq93NrHij63tbbKx9gm4wntx5UW4IfCmQUkcwUgrjeb3nxl71hOljGrTaPzY2g52Hjx8VHlcffL02fMXu3svL7XMFIEukUyq6whrYFRA11DD4DpVgHnE4Coan5T86g6UplJcmDyFAcdDQRNKsHGh89bNbq1Rb8wt3HSaC6eGFnZ2sxcc9mNJMg7CEIa17jUbqRlYrAwlDIpqP9OQYjLGQ+g5V2AOemDnJy3CfReJw0Qq9wkTzqOrGRZzrXMeOSXHZqR9Vgb/xcyIF36s7KKLcG5rzImNlEyvZ5R1N8O9zCQfBpaKNDMgyP0tkoyFRoblTMOYKiCG5c7BRFE3iJCMsMLEuMlX90O/RYpnsqiuteB4DEpK7iaFBQHmDiBgQiTnWMS2T0Vc2H6ZG0X2U+HRCdDhyPwVJHbiC6bTJZz6MM+XMPfhbLaEs42+k//01KlYUIKZ/byJjQJYUVz4inZ7hbZ9Ckq5B2X7d1hBqimTwhPEbnlWCnz0C8SQwG1ZgJQv2T1E0fJb3DpNYVsrEk9xOk2Xv+XU79DpLGGnKNyqNf3F2nQuD+rNd/WD8/e1o+PF0lXQa/QGvUVNdIiOUBudoS4iCNAX9BV9C74HP4Nfwe976fbWIucVWrOdyh/3CoRU</latexit>

Defendant

1prior arrests
B prior sentences C
B
C
B
C
age
B
C
B drug history C
B
C
B
C
race
B
C
Bage at first arrestC
B
C
Beducation historyC
B
C@ vocation history A
gender<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>

Does this mechanism work?
-No, due to “redundant encoding”
Other attributes in the inputs could be used to reconstruct thedeleted sensitive attributes due to the potential correlations
among them
• Ethnicity vs hair color/last name• Race vs zipcode5

Algorithmic Fairness: Statistical Parity
Example in loan application
0

1

age
B
C
education
B
C
B
C
race
B
C
B
C
genderBC
B annual income C
BC
B repaying history C
BC@defaulting historyAcredit score

Ŷ = f (X)Approve/
Decline?

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

ApplicantsfTarget variable(X, A, Y ) ⇠ D
Input vector

Sensitive attribute

Statisticalparity:Statistical parity:Ŷ any? Afair algorithm cannot take information
related to sensitive attribute during decision making
6

Algorithmic Fairness: Statistical Parity
Pre-processing Methods: Feature Learning
Male or Female ?

Fair
Representations[Zemel et al. ICML13][Edwards et al. ICLR 15][Madras et al. ICML 18][Zhao et al. ICLR 20]-

Needs full access to (X, A, Y )In practice: minimax optimization can be unstable and hard forneural networks

7

Algorithmic Fairness: Statistical Parity
Adversarial Training
Male or Female ?

Fair Representations[Zemel et al. ICML13][Edwards et al. ICLR 15][Madras et al. ICML 18]
8

Algorithmic Fairness: Statistical Parity
In-processing Methods: Constrained Optimizationmin[ℓ( fθ(x), y)]subject to| Pr( fθ(x) = 1 ∣ A = 0) − Pr( fθ(x) = 1 ∣ A = 1) | ≤ ϵθerror minimization

-

ff

-

Needs full access to (X, A, Y )Need to design dedicated optimization solvers for each di erent
model fθ( ⋅ )We may not be able to train the model from scratch due to limited
computational resources, e.g., LLMs
𝔼-

constraint of approximate statistical parity

9

Algorithmic Fairness: Statistical Parity
Post-processing Methods:
0

1

age
B
C
education
B
C
B
C
race
B
C
B
C
genderBC
B annual income C
BC
B repaying history C
BC@defaulting historyAcredit score

Ŷ = f (X)Approve/
Decline?

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

Applicants

Ỹ =

-

The given classi er f( ⋅ ) can be treated as a black-box
No need to re-train the model from scratch
10
fi

-

No need to have full access to (X, A, Y )𝒜-( f(X), A)

Fairness-Accuracy Tradeo
Before we talk about the algorithm:- Is there any price we have to pay for fairness? If yes, what’s theprice (in terms of accuracy)?
- Is it possible to derive an algorithm that achieves the optimalaccuracy under the constraint of fairness (statistical parity)?

f11

Fairness-Accuracy Tradeo
Statistical parity: enforcing statistical independence, will this lead toloss of accuracy?
Consider some extremal cases:-

What if Y ? A in the underlying distribution?
<latexit sha1_base64="a+ymAN5XIX/7ZVg3U/7lwVIyHWw=">AAAEVXicfZPfaxNBEMe3Taw1/mirj74choJPIZHS+mChooX4VmPTRnKh7O3NJUv2V3f3mlyO+yd81f9L/GME99JIkg06cDDM5zsze7M7kWLU2Gbz19Z2pfpg5+Huo9rjJ0+f7e0fPL8yMtUEukQyqXsRNsCogK6llkFPacA8YnAdjT+U/PoOtKFSXNpMwYDjoaAJJdi6UO9rqECr4P3Nfr3ZaM4t2HRaC6eOFnZxc1A5CWNJUg7CEoaN6beayg5yrC0lDIpamBpQmIzxEPrOFZiDGeTzAxfBoYvEQSK1+4QN5tHVjBxzYzIeOSXHdmR8Vgb/xeyIF36s7GKKYG5rzImtlMysZ5R1N8P91CZvBzkVKrUgyP1fJCkLrAzK0QYx1UAsy5yDiaZuEAEZYY2JdRdQOwz8FgrPZFFba8HxGLSU3E0KCwLMHUDAhEjOsYjzkIq4yMMyN4ryT4VHJ0CHI/tXkOQTXzCdLuHUh1m2hJkPZ7MlnG30nfynp1FiQQlm+ZdNbDXAiuLSV7TbK7TtU9DaPag8vMMalKFMCk8Qux1aKfDRLxBDArdlAVK+ZPcQxanf4tZpivx0ReIpzqdqeS3nfodOZwk7ReFWreUv1qZz9abROm4cfT6qn71bLN0ueoleodeohU7QGWqjC9RFBDH0DX1HPyo/K7+r1erOvXR7a5HzAq1Zde8P2UiFKw==</latexit>

What if Y = A in the underlying distribution?
<latexit sha1_base64="XKHZP+np6XEYQHhrQrVhpGsgtb0=">AAAEUnicfZPNbhMxEMedJkAJBVo4crGIKnGKElRRDkQqgkrhVkLTFiVR5fXOJlb8sbW9TTarfQau8F5ceBVOeNOgbBzBSCuN5vefGXvWE8ScGdtq/arsVGv37j/YfVh/tPf4ydP9g2cXRiWaQp8qrvRVQAxwJqFvmeVwFWsgIuBwGUw/FPzyFrRhSp7bNIaRIGPJIkaJdaH+V9zB76/3G61ma2l422mvnAZa2dn1QfV4GCqaCJCWcmLMoN2K7Sgj2jLKIa8PEwMxoVMyhoFzJRFgRtnytDk+dJEQR0q7T1q8jJYzMiKMSUXglILYifFZEfwXsxOR+7Gii8nx0jaYE1uluNnMKOpuhweJjd6OMibjxIKkd7eIEo6twsVcccg0UMtT5xCqmRsEphOiCbVu+vVD7LeIyULl9Y0WgkxBKyXcpIikwN0BJMyoEoLIMBsyGebZsMgNguxT7tEZsPHE/hVE2cwXzOdrOPdhmq5h6sPFYg0XW31n/+lpYrmilPDsyza2GqCkOPcV3W6Jdn0KWrsHlQ1viYbYMK6kJwjdApUKfPQLhBDBTVGAFi/ZPUTZ8VvcOE2edUoST3E6j9e/5dTv0OutYS/P3aq1/cXadi5eN9tvmkefjxon71ZLt4teoJfoFWqjY3SCuugM9RFFDH1D39GP6s/q71qlVr2T7lRWOc/RhtX2/gCoNINX</latexit>

There should be a term that quanti es the dependency of these two
random variables!
The tradeo result should be inherent:-

Does not depend on the speci c algorithm used to achieve
statistical parity-

Does not depend on the computational resources available to thealgorithm-

Does not depend on the sample size for training the predictor
f

fi

fi

ff

12

Fairness-Accuracy Tradeo
Statistical parity: Ŷ ? A
Theorem [ZG, NeurIPS 19]: For any fair algorithm Yb = h(X) (in the sense ofstatistical parity), the following inequality holds:"A=0 (h) + "A=1 (h)BR

0/1 error on Group 1

0/1 error on Group 0

Key Message: when the base rates di er, any fair algorithm has
to make a large error on at least one of the groupsℏ(Improper) Analogy: a kind of uncertainty principle for fairness Δp ⋅ Δx ≥2
Di erence of base rates:

Pr(Y = 1 | A = 1)|
ff= 1 | A = 0)fff

BR := | Pr(Y13

Fairness-Accuracy Tradeo
Theorem [ZG, NeurIPS 19]: For any fair algorithm Yb = h(X) (in the sense ofstatistical parity), the following inequality holds:"A=0 (h) + "A=1 (h)BRDi erence of base rates:
BR := | Pr(Y

= 1 | A = 0)

Pr(Y = 1 | A = 1)|- If A = Y , thenBR = 1, meaning max{"A=0 (h), "A=1 (h)}- If A ? Y , thenBR = 0, meaning no tension with utility

0.5

BR is a fundamental quantity to characterize

the coupling between target and sensitive attribute

f

ff

14

Fairness-Accuracy Tradeo
But, why the speci c form of this lower bound? Why not the joint error?
-

A simple corollary regarding the joint error could be obtained:
ε(h) = Pr(A = 0) ⋅ εA=0(h) + Pr(A = 1) ⋅ εA=1(h)≥ min{Pr(A = 0), Pr(A = 1)} ⋅ (εA=0(h) + εA=1(h))≥ H01(A) ⋅ ΔBR

where H01(A) := 1 − max Pr(A = a) is called zero-one entropy of A-a

Any lower bound for the joint error has to depend on the marginal
distribution of the sensitive attribute A, which could bias towards the
majority group✓ Instead, the lower bound in Theorem 1 treats both errors equally✓ In cases where the ratio between two groups is extremely

imbalanced, the lower bound for the joint error could be 0, i.e., noprice to pay in terms of the joint errorffiPeter D Grünwald, A Philip Dawid, et al. Game theory, maximum entropy, minimum discrepancy and robust bayesian15
decision theory. Annals of statistics’ 04

1

h(x,0)

h(x,1)P( )εA=0(h ∘ g0)
Ŷ
0
Ŷ
1

Y
1

{

0

Y
0

εA=1(h ∘ g1)

P( )

𝒳

𝒴

a: input distributions over group A = aŶa : predicted label distributions over group A = a
Y
a : ground-truth label distributions over group A = a

16
fi

𝒟
𝒟

𝒟
𝒟

𝒟
𝒟

𝒟

𝒟

We provide a proof sketch for an attribute-aware classi er:{𝒟

Proof Sketch

An Optimal Fair Classi er via Post-Processing
Is it possible to construct a classi er that veri es the lower bound?
Why should we care about this question?
-

Can con rm the tightness of the inequality-

Can design optimal classi ers on the fairness-accuracy frontier[Why?] However, this problem cannot be easier than learning
the Bayes classi er without fairness constraint

fi

fi

fi

fi

fi

fi

17

An Optimal Fair Classi er via Post-Processing
This problem cannot be easier than learning the Bayes classi er-

Assume we have oracle access to the problem of learning optimal
fair classi er-

Use this oracle access to learn the Bayes optimal classi er

Problem A:
0
Let µ be a distribution over X ⇥ Y . We want to learn h0 (·) ,0
the Bayes optimal classi er over µ<latexit sha1_base64="atjolN4BLFG2M2iez3G73HAq2QI=">AAAEUXicfZPNbhMxEMfdJEBJ+WjhyGXVqIJTlKCq5VKpAiqFWwlNWykbVV7vbGLFH1vb22Rj7StwhffixKNww5umSuIIRlppNL//zNiznihlVJtW6/dWpVp79PjJ9tP6zrPnL17u7r261DJTBHpEMqmuI6yBUQE9Qw2D61QB5hGDq2j8qeRXd6A0leLC5CkMOB4KmlCCTRkKefb2ZrfRarbmFmw67YXTQAs7v9mrHoexJBkHYQjDWvfbrdQMLFaGEgZFPcw0pJiM8RD6zhWYgx7Y+WGL4MBF4iCRyn3CBPPoaobFXOucR07JsRlpn5XBfzEz4oUfK7voIpjbGnNiIyXT6xll3c1wPzPJh4GlIs0MCHJ/iyRjgZFBOdYgpgqIYblzMFHUDSIgI6wwMW749YPAb5HimSzqay04HoOSkrtJYUGAuQMImBDJORaxDamICxuWuVFkvxQenQAdjsyDILETXzCdLuHUh3m+hLkPZ7MlnG30nfynp07FghLM7LdNbBTAiuLCV3Q6K7TjU1DKPSgb3mEFqaZMCk8Qu/1ZKfDZLxBDArdlAVK+ZPcQxYnf4tZpCnuyIvEUZ9N0+VvO/A7d7hJ2i8KtWttfrE3n8n2zfdQ8/HrYOP24WLpt9Abto3eojY7RKeqgc9RDBI3Qd/QD/az+qv6poVrlXlrZWuS8RmtW2/kLtBKDoQ==</latexit><latexit sha1_base64="IaK8IgZ62vVKq8sFgPBDkLSpvRg=">AAAEVnicfZPNbhMxEMfdJqUlfKVw5LIiqiiXKqkqyqVSBVQKtxKatigbVV7vbGLFH1vb22Rj7VNwhfeCl0F406AkjmCklUbz+8+Md+yJUka1aTZ/bWxWqlsPtnce1h49fvL0WX33+aWWmSLQJZJJdR1hDYwK6BpqGFynCjCPGFxFow8lv7oDpakUFyZPoc/xQNCEEmxc6Ovw9X5IYmne3NQbzYPmzIJ1pzV3Gmhu5ze7leMwliTjIAxhWOteq5mavsXKUMKgqIWZhhSTER5Az7kCc9B9OztxEey5SBwkUrlPmGAWXc6wmGud88gpOTZD7bMy+C9mhrzwY2UXXQQzW2FObKRkejWjrLse7mUmede3VKSZAUHu/yLJWGBkUM42iKkCYljuHEwUdYMIyBArTIy7gdpe4LdI8VQWtZUWHI9AScndpLAgwNwBBIyJ5ByL2IZUxIUNy9wosp8Kj46BDobmryCxY18wmSzgxId5voC5D6fTBZyu9R3/p6dOxZwSzOyXdWwUwJLiwle020u07VNQyj0oG95hBammTApPELslWirw0S8QQwK3ZQFSvmT3EMWJ3+LWaQp7siTxFGeTdHEtZ36HTmcBO0XhVq3lL9a6c3l40Hp7cPT5qHH6fr50O+gleoX2UQsdo1PURueoiwji6Bv6jn5UflZ+V7eq2/fSzY15zgu0YtX6H2S9hVQ=</latexit><latexit sha1_base64="NFTJ8vqgqO02t9Akq4iLY1dYywk=">AAAEa3icfZPNbhMxEMfdJkAJXym9QQ8rokicoqSqKJdKFVAp3Epo2qBsFHm9s4kVf2xtb5PNai88DVd4Gx6Cd8CbBpI4gpFWGs3v7/l77XEQM6pNs/lzZ7dUvnf/wd7DyqPHT54+q+4/v9IyUQS6RDKpegHWwKiArqGGQS9WgHnA4DqYvC/49S0oTaW4NGkMA45HgkaUYGNLw+qhz7EZE8yyXu4bykH/LXzJh9Vas9FchLedtJZJDS3jYrhfOvFDSRIOwhCGte63mrEZZFgZShjkFT/REGMywSPo21RgazjIFr+Re3VbCb1IKvsJ4y2q6ysyzLVOeWCVxR61y4riv5gZ89ytFS469xaxwazYSMn05oqi73a5n5jo7SCjIk4MCHL3F1HCPCO94sC9kCoghqU2wURRexAeGWOFibHXUql7rkWM5zKvbFhwPAElJbcnhQUBZjcgYEok51iEmU9FmGeLawuC7GPu0CnQ0dj8EUTZ1BXMZis4c2GarmDqwvl8BedbvtP/eOpYLGkxaZ+3sVEAa4pLV9Fur9G2S0EpO1CZf4sVxJoyKRxBaF/WWoMPboMQIrgpGpBiku0gilPX4sZq8ux0TeIozmfx6lrOXYdOZwU7efHUWu7D2k6ujhqtN43jT8e1s3fLR7eHXqJX6DVqoRN0htroAnURQV/RN/Qd/Sj9Kh+UX5QP76S7O8s1B2gjyvXfWBGN6Q==</latexit><latexit sha1_base64="atjolN4BLFG2M2iez3G73HAq2QI=">AAAEUXicfZPNbhMxEMfdJEBJ+WjhyGXVqIJTlKCq5VKpAiqFWwlNWykbVV7vbGLFH1vb22Rj7StwhffixKNww5umSuIIRlppNL//zNiznihlVJtW6/dWpVp79PjJ9tP6zrPnL17u7r261DJTBHpEMqmuI6yBUQE9Qw2D61QB5hGDq2j8qeRXd6A0leLC5CkMOB4KmlCCTRkKefb2ZrfRarbmFmw67YXTQAs7v9mrHoexJBkHYQjDWvfbrdQMLFaGEgZFPcw0pJiM8RD6zhWYgx7Y+WGL4MBF4iCRyn3CBPPoaobFXOucR07JsRlpn5XBfzEz4oUfK7voIpjbGnNiIyXT6xll3c1wPzPJh4GlIs0MCHJ/iyRjgZFBOdYgpgqIYblzMFHUDSIgI6wwMW749YPAb5HimSzqay04HoOSkrtJYUGAuQMImBDJORaxDamICxuWuVFkvxQenQAdjsyDILETXzCdLuHUh3m+hLkPZ7MlnG30nfynp07FghLM7LdNbBTAiuLCV3Q6K7TjU1DKPSgb3mEFqaZMCk8Qu/1ZKfDZLxBDArdlAVK+ZPcQxYnf4tZpCnuyIvEUZ9N0+VvO/A7d7hJ2i8KtWttfrE3n8n2zfdQ8/HrYOP24WLpt9Abto3eojY7RKeqgc9RDBI3Qd/QD/az+qv6poVrlXlrZWuS8RmtW2/kLtBKDoQ==</latexit>

Problem B:
Let µ be a distribution over X ⇥ A ⇥ Y . We want to learn h(·, ·),the optimal fair classi er over µ<latexit sha1_base64="mMAgzLVAKS2Dpm/NnqPGnR4uAeY=">AAAEXnicfZPfa9swEMfVJuu6bF3S7WWwF7NQ6GCEpJR1L4XSrpC9dVnTFuIQZPmciOiHK8lNHOO/ZK/bH7W3/SmT04wkCtuB8HGf793Jki6IGdWm2fy1tV0qP9l5uvus8vzF3stqbf/VjZaJItAlkkl1F2ANjAroGmoY3MUKMA8Y3Abji4LfPoDSVIprk8bQ53goaEQJNjY0qFVHhz4JpfngzT/vB7V6s9Gcm7fptBZOHS3sarBfOvFDSRIOwhCGte61mrHpZ1gZShjkFT/REGMyxkPoWVdgDrqfzXeeewc2EnqRVHYJ482jqxkZ5lqnPLBKjs1Iu6wI/ouZEc/dWNFF597c1pgVGymZXs8o6m6Ge4mJPvUzKuLEgCCPfxElzDPSK87YC6kCYlhqHUwUtQfhkRFWmBh7E5UDz20R45nMK2stOB6DkpLbk8KCALMbEDAhknMswsynIswzv8gNguxL7tAJ0OHI/BVE2cQVTKdLOHVhmi5h6sLZbAlnG30n/+mpY7GgBLPs2yY2CmBFce0q2u0V2nYpKGUfVOY/YAWxpkwKRxDaYVop8NktEEIE90UBUrxk+xDFqdvi3mry7HRF4igup/HyWi7dDp3OEnby3I5ayx2sTefmqNH62Dj+elw/O18M3S56i96hQ9RCJ+gMtdEV6iKCEvQd/UA/S7/LO+W9cvVRur21yHmN1qz85g+De4bt</latexit><latexit sha1_base64="2ZmPSEzVigR/jnr0/LhJlJaPN4Y=">AAAEfHicfVPbbtNAEN02AUq4pfDIi0WohIQaJVXV8lKpXCqFtxKaNiiOovV6nKyyF3d33cSx/BV8Da/wFfwMYp0GkmwEI1kanXN2zq5nJogZ1abR+Lm1XSrfuXtv537lwcNHj59Ud59eapkoAh0imVTdAGtgVEDHUMOgGyvAPGBwFYzfF/zVDShNpbgwaQx9joeCRpRgY6FBdd/n2IwIZlk39w3loP8Cb13gSz6o1hr1xjy8zaS5SGpoEeeD3dKxH0qScBCGMKx1r9mITT/DylDCIK/4iYYYkzEeQs+mAlvDfjZ/V+7tWST0IqnsJ4w3R1dPZJhrnfLAKos7apcrwH9xZsRzFytcdO7NY42zYiMl0+snirqbcC8x0Zt+RkWcGBDk9hVRwjwjvaIDXkgVEMNSm2CiqP0RHhlhhYmxfarsea5FjGcyr6xZcDwGJSW3fwoLAsxeQMCESM6xCDOfijDP5m0Lguxj7rAToMOR+SOIsokrmE6X5NQl03RJpi45my3J2Ybv5D+eOhYLtpi0z5u0UQArigtX0WqtsC2XBaXsQGX+DVYQa8qkcAShXbWVAh/cAiFEcF0UIMUk20EUJ67FtdXk2cmKxFGcTeNlW85ch3Z7SbbzYtWa7mJtJpcH9eZR/fDTYe303WLpdtBz9AK9Qk10jE5RC52jDiLoK/qGvqMfpV/ll+XX5f1b6fbW4swztBblo98SRZWA</latexit><latexit sha1_base64="v8oGXHpEj5wbHp/jCLsw9CQXL9E=">AAAEUHicfZPNbtNAEMe3TYASvlo4crGIKnGKElS1XCpVQKVwK2nTVoqjar0eJ6vsh7u7buKs/Ahc4b248SbcYJ0GxdkIRrI8mt9/ZtbjnShlVJt2++fWdq3+4OGjnceNJ0+fPX+xu/fyUstMEegTyaS6jrAGRgX0DTUMrlMFmEcMrqLJx5Jf3YHSVIoLk6cw5HgkaEIJNi50HvLsZrfZbrUXFmw6naXTREs7u9mrHYWxJBkHYQjDWg867dQMLVaGEgZFI8w0pJhM8AgGzhWYgx7axVmLYN9F4iCRyj3CBItoNcNirnXOI6fk2Iy1z8rgv5gZ88KPlV10ESxsjTmxkZLp9Yyy7mZ4kJnk/dBSkWYGBLn/iiRjgZFBOdUgpgqIYblzMFHUDSIgY6wwMW72jf3Ab5HiuSwaay04noCSkrtJYUGAuQMImBLJORaxDamICxuWuVFkPxcenQIdjc1fQWKnvmA2W8GZD/N8BXMfzucrON/oO/1PT52KJSWY2fNNbBRARXHhK7rdCu36FJRyF8qGd1hBqimTwhPEbn0qBT75BWJI4LYsQMqb7C6iOPZb3DpNYY8rEk9xOktXv+XU79DrrWCvKNyqdfzF2nQu37U6h62DLwfNkw/LpdtBr9Eb9BZ10BE6QV10hvqIoBH6ir6h77UftV+13/Wte+n28o1eoTWrN/4AFbyEbw==</latexit><latexit sha1_base64="v8oGXHpEj5wbHp/jCLsw9CQXL9E=">AAAEUHicfZPNbtNAEMe3TYASvlo4crGIKnGKElS1XCpVQKVwK2nTVoqjar0eJ6vsh7u7buKs/Ahc4b248SbcYJ0GxdkIRrI8mt9/ZtbjnShlVJt2++fWdq3+4OGjnceNJ0+fPX+xu/fyUstMEegTyaS6jrAGRgX0DTUMrlMFmEcMrqLJx5Jf3YHSVIoLk6cw5HgkaEIJNi50HvLsZrfZbrUXFmw6naXTREs7u9mrHYWxJBkHYQjDWg867dQMLVaGEgZFI8w0pJhM8AgGzhWYgx7axVmLYN9F4iCRyj3CBItoNcNirnXOI6fk2Iy1z8rgv5gZ88KPlV10ESxsjTmxkZLp9Yyy7mZ4kJnk/dBSkWYGBLn/iiRjgZFBOdUgpgqIYblzMFHUDSIgY6wwMW72jf3Ab5HiuSwaay04noCSkrtJYUGAuQMImBLJORaxDamICxuWuVFkPxcenQIdjc1fQWKnvmA2W8GZD/N8BXMfzucrON/oO/1PT52KJSWY2fNNbBRARXHhK7rdCu36FJRyF8qGd1hBqimTwhPEbn0qBT75BWJI4LYsQMqb7C6iOPZb3DpNYY8rEk9xOktXv+XU79DrrWCvKNyqdfzF2nQu37U6h62DLwfNkw/LpdtBr9Eb9BZ10BE6QV10hvqIoBH6ir6h77UftV+13/Wte+n28o1eoTWrN/4AFbyEbw==</latexit>

To show that Problem A ≪ Problem B, suppose we have an algorithm
to solve Problem B, we could use that algorithm to solve Problem A as
well.

fi

fi

fi

fi

fi

fi

18

An Optimal Fair Classi er via Post-Processing
Problem A:
0
Let µ be a distribution over X ⇥ Y . We want to learn h0 (·) ,0µthe Bayes optimal classi er over<latexit sha1_base64="atjolN4BLFG2M2iez3G73HAq2QI=">AAAEUXicfZPNbhMxEMfdJEBJ+WjhyGXVqIJTlKCq5VKpAiqFWwlNWykbVV7vbGLFH1vb22Rj7StwhffixKNww5umSuIIRlppNL//zNiznihlVJtW6/dWpVp79PjJ9tP6zrPnL17u7r261DJTBHpEMqmuI6yBUQE9Qw2D61QB5hGDq2j8qeRXd6A0leLC5CkMOB4KmlCCTRkKefb2ZrfRarbmFmw67YXTQAs7v9mrHoexJBkHYQjDWvfbrdQMLFaGEgZFPcw0pJiM8RD6zhWYgx7Y+WGL4MBF4iCRyn3CBPPoaobFXOucR07JsRlpn5XBfzEz4oUfK7voIpjbGnNiIyXT6xll3c1wPzPJh4GlIs0MCHJ/iyRjgZFBOdYgpgqIYblzMFHUDSIgI6wwMW749YPAb5HimSzqay04HoOSkrtJYUGAuQMImBDJORaxDamICxuWuVFkvxQenQAdjsyDILETXzCdLuHUh3m+hLkPZ7MlnG30nfynp07FghLM7LdNbBTAiuLCV3Q6K7TjU1DKPSgb3mEFqaZMCk8Qu/1ZKfDZLxBDArdlAVK+ZPcQxYnf4tZpCnuyIvEUZ9N0+VvO/A7d7hJ2i8KtWttfrE3n8n2zfdQ8/HrYOP24WLpt9Abto3eojY7RKeqgc9RDBI3Qd/QD/az+qv6poVrlXlrZWuS8RmtW2/kLtBKDoQ==</latexit><latexit sha1_base64="IaK8IgZ62vVKq8sFgPBDkLSpvRg=">AAAEVnicfZPNbhMxEMfdJqUlfKVw5LIiqiiXKqkqyqVSBVQKtxKatigbVV7vbGLFH1vb22Rj7VNwhfeCl0F406AkjmCklUbz+8+Md+yJUka1aTZ/bWxWqlsPtnce1h49fvL0WX33+aWWmSLQJZJJdR1hDYwK6BpqGFynCjCPGFxFow8lv7oDpakUFyZPoc/xQNCEEmxc6Ovw9X5IYmne3NQbzYPmzIJ1pzV3Gmhu5ze7leMwliTjIAxhWOteq5mavsXKUMKgqIWZhhSTER5Az7kCc9B9OztxEey5SBwkUrlPmGAWXc6wmGud88gpOTZD7bMy+C9mhrzwY2UXXQQzW2FObKRkejWjrLse7mUmede3VKSZAUHu/yLJWGBkUM42iKkCYljuHEwUdYMIyBArTIy7gdpe4LdI8VQWtZUWHI9AScndpLAgwNwBBIyJ5ByL2IZUxIUNy9wosp8Kj46BDobmryCxY18wmSzgxId5voC5D6fTBZyu9R3/p6dOxZwSzOyXdWwUwJLiwle020u07VNQyj0oG95hBammTApPELslWirw0S8QQwK3ZQFSvmT3EMWJ3+LWaQp7siTxFGeTdHEtZ36HTmcBO0XhVq3lL9a6c3l40Hp7cPT5qHH6fr50O+gleoX2UQsdo1PURueoiwji6Bv6jn5UflZ+V7eq2/fSzY15zgu0YtX6H2S9hVQ=</latexit><latexit sha1_base64="NFTJ8vqgqO02t9Akq4iLY1dYywk=">AAAEa3icfZPNbhMxEMfdJkAJXym9QQ8rokicoqSqKJdKFVAp3Epo2qBsFHm9s4kVf2xtb5PNai88DVd4Gx6Cd8CbBpI4gpFWGs3v7/l77XEQM6pNs/lzZ7dUvnf/wd7DyqPHT54+q+4/v9IyUQS6RDKpegHWwKiArqGGQS9WgHnA4DqYvC/49S0oTaW4NGkMA45HgkaUYGNLw+qhz7EZE8yyXu4bykH/LXzJh9Vas9FchLedtJZJDS3jYrhfOvFDSRIOwhCGte63mrEZZFgZShjkFT/REGMywSPo21RgazjIFr+Re3VbCb1IKvsJ4y2q6ysyzLVOeWCVxR61y4riv5gZ89ytFS469xaxwazYSMn05oqi73a5n5jo7SCjIk4MCHL3F1HCPCO94sC9kCoghqU2wURRexAeGWOFibHXUql7rkWM5zKvbFhwPAElJbcnhQUBZjcgYEok51iEmU9FmGeLawuC7GPu0CnQ0dj8EUTZ1BXMZis4c2GarmDqwvl8BedbvtP/eOpYLGkxaZ+3sVEAa4pLV9Fur9G2S0EpO1CZf4sVxJoyKRxBaF/WWoMPboMQIrgpGpBiku0gilPX4sZq8ux0TeIozmfx6lrOXYdOZwU7efHUWu7D2k6ujhqtN43jT8e1s3fLR7eHXqJX6DVqoRN0htroAnURQV/RN/Qd/Sj9Kh+UX5QP76S7O8s1B2gjyvXfWBGN6Q==</latexit><latexit sha1_base64="atjolN4BLFG2M2iez3G73HAq2QI=">AAAEUXicfZPNbhMxEMfdJEBJ+WjhyGXVqIJTlKCq5VKpAiqFWwlNWykbVV7vbGLFH1vb22Rj7StwhffixKNww5umSuIIRlppNL//zNiznihlVJtW6/dWpVp79PjJ9tP6zrPnL17u7r261DJTBHpEMqmuI6yBUQE9Qw2D61QB5hGDq2j8qeRXd6A0leLC5CkMOB4KmlCCTRkKefb2ZrfRarbmFmw67YXTQAs7v9mrHoexJBkHYQjDWvfbrdQMLFaGEgZFPcw0pJiM8RD6zhWYgx7Y+WGL4MBF4iCRyn3CBPPoaobFXOucR07JsRlpn5XBfzEz4oUfK7voIpjbGnNiIyXT6xll3c1wPzPJh4GlIs0MCHJ/iyRjgZFBOdYgpgqIYblzMFHUDSIgI6wwMW749YPAb5HimSzqay04HoOSkrtJYUGAuQMImBDJORaxDamICxuWuVFkvxQenQAdjsyDILETXzCdLuHUh3m+hLkPZ7MlnG30nfynp07FghLM7LdNbBTAiuLCV3Q6K7TjU1DKPSgb3mEFqaZMCk8Qu/1ZKfDZLxBDArdlAVK+ZPcQxYnf4tZpCnuyIvEUZ9N0+VvO/A7d7hJ2i8KtWttfrE3n8n2zfdQ8/HrYOP24WLpt9Abto3eojY7RKeqgc9RDBI3Qd/QD/az+qv6poVrlXlrZWuS8RmtW2/kLtBKDoQ==</latexit>

Problem B:
Let µ be a distribution over X ⇥ A ⇥ Y . We want to learn h(·, ·),the optimal fair classi er over µ such that the lower bound holds<latexit sha1_base64="mMAgzLVAKS2Dpm/NnqPGnR4uAeY=">AAAEXnicfZPfa9swEMfVJuu6bF3S7WWwF7NQ6GCEpJR1L4XSrpC9dVnTFuIQZPmciOiHK8lNHOO/ZK/bH7W3/SmT04wkCtuB8HGf793Jki6IGdWm2fy1tV0qP9l5uvus8vzF3stqbf/VjZaJItAlkkl1F2ANjAroGmoY3MUKMA8Y3Abji4LfPoDSVIprk8bQ53goaEQJNjY0qFVHhz4JpfngzT/vB7V6s9Gcm7fptBZOHS3sarBfOvFDSRIOwhCGte61mrHpZ1gZShjkFT/REGMyxkPoWVdgDrqfzXeeewc2EnqRVHYJ482jqxkZ5lqnPLBKjs1Iu6wI/ouZEc/dWNFF597c1pgVGymZXs8o6m6Ge4mJPvUzKuLEgCCPfxElzDPSK87YC6kCYlhqHUwUtQfhkRFWmBh7E5UDz20R45nMK2stOB6DkpLbk8KCALMbEDAhknMswsynIswzv8gNguxL7tAJ0OHI/BVE2cQVTKdLOHVhmi5h6sLZbAlnG30n/+mpY7GgBLPs2yY2CmBFce0q2u0V2nYpKGUfVOY/YAWxpkwKRxDaYVop8NktEEIE90UBUrxk+xDFqdvi3mry7HRF4igup/HyWi7dDp3OEnby3I5ayx2sTefmqNH62Dj+elw/O18M3S56i96hQ9RCJ+gMtdEV6iKCEvQd/UA/S7/LO+W9cvVRur21yHmN1qz85g+De4bt</latexit><latexit sha1_base64="2ZmPSEzVigR/jnr0/LhJlJaPN4Y=">AAAEfHicfVPbbtNAEN02AUq4pfDIi0WohIQaJVXV8lKpXCqFtxKaNiiOovV6nKyyF3d33cSx/BV8Da/wFfwMYp0GkmwEI1kanXN2zq5nJogZ1abR+Lm1XSrfuXtv537lwcNHj59Ud59eapkoAh0imVTdAGtgVEDHUMOgGyvAPGBwFYzfF/zVDShNpbgwaQx9joeCRpRgY6FBdd/n2IwIZlk39w3loP8Cb13gSz6o1hr1xjy8zaS5SGpoEeeD3dKxH0qScBCGMKx1r9mITT/DylDCIK/4iYYYkzEeQs+mAlvDfjZ/V+7tWST0IqnsJ4w3R1dPZJhrnfLAKos7apcrwH9xZsRzFytcdO7NY42zYiMl0+snirqbcC8x0Zt+RkWcGBDk9hVRwjwjvaIDXkgVEMNSm2CiqP0RHhlhhYmxfarsea5FjGcyr6xZcDwGJSW3fwoLAsxeQMCESM6xCDOfijDP5m0Lguxj7rAToMOR+SOIsokrmE6X5NQl03RJpi45my3J2Ybv5D+eOhYLtpi0z5u0UQArigtX0WqtsC2XBaXsQGX+DVYQa8qkcAShXbWVAh/cAiFEcF0UIMUk20EUJ67FtdXk2cmKxFGcTeNlW85ch3Z7SbbzYtWa7mJtJpcH9eZR/fDTYe303WLpdtBz9AK9Qk10jE5RC52jDiLoK/qGvqMfpV/ll+XX5f1b6fbW4swztBblo98SRZWA</latexit><latexit sha1_base64="v8oGXHpEj5wbHp/jCLsw9CQXL9E=">AAAEUHicfZPNbtNAEMe3TYASvlo4crGIKnGKElS1XCpVQKVwK2nTVoqjar0eJ6vsh7u7buKs/Ahc4b248SbcYJ0GxdkIRrI8mt9/ZtbjnShlVJt2++fWdq3+4OGjnceNJ0+fPX+xu/fyUstMEegTyaS6jrAGRgX0DTUMrlMFmEcMrqLJx5Jf3YHSVIoLk6cw5HgkaEIJNi50HvLsZrfZbrUXFmw6naXTREs7u9mrHYWxJBkHYQjDWg867dQMLVaGEgZFI8w0pJhM8AgGzhWYgx7axVmLYN9F4iCRyj3CBItoNcNirnXOI6fk2Iy1z8rgv5gZ88KPlV10ESxsjTmxkZLp9Yyy7mZ4kJnk/dBSkWYGBLn/iiRjgZFBOdUgpgqIYblzMFHUDSIgY6wwMW72jf3Ab5HiuSwaay04noCSkrtJYUGAuQMImBLJORaxDamICxuWuVFkPxcenQIdjc1fQWKnvmA2W8GZD/N8BXMfzucrON/oO/1PT52KJSWY2fNNbBRARXHhK7rdCu36FJRyF8qGd1hBqimTwhPEbn0qBT75BWJI4LYsQMqb7C6iOPZb3DpNYY8rEk9xOktXv+XU79DrrWCvKNyqdfzF2nQu37U6h62DLwfNkw/LpdtBr9Eb9BZ10BE6QV10hvqIoBH6ir6h77UftV+13/Wte+n28o1eoTWrN/4AFbyEbw==</latexit><latexit sha1_base64="v8oGXHpEj5wbHp/jCLsw9CQXL9E=">AAAEUHicfZPNbtNAEMe3TYASvlo4crGIKnGKElS1XCpVQKVwK2nTVoqjar0eJ6vsh7u7buKs/Ahc4b248SbcYJ0GxdkIRrI8mt9/ZtbjnShlVJt2++fWdq3+4OGjnceNJ0+fPX+xu/fyUstMEegTyaS6jrAGRgX0DTUMrlMFmEcMrqLJx5Jf3YHSVIoLk6cw5HgkaEIJNi50HvLsZrfZbrUXFmw6naXTREs7u9mrHYWxJBkHYQjDWg867dQMLVaGEgZFI8w0pJhM8AgGzhWYgx7axVmLYN9F4iCRyj3CBItoNcNirnXOI6fk2Iy1z8rgv5gZ88KPlV10ESxsjTmxkZLp9Yyy7mZ4kJnk/dBSkWYGBLn/iiRjgZFBOdUgpgqIYblzMFHUDSIgY6wwMW72jf3Ab5HiuSwaay04noCSkrtJYUGAuQMImBLJORaxDamICxuWuVFkPxcenQIdjc1fQWKnvmA2W8GZD/N8BXMfzucrON/oO/1PT52KJSWY2fNNbBRARXHhK7rdCu36FJRyF8qGd1hBqimTwhPEbn0qBT75BWJI4LYsQMqb7C6iOPZb3DpNYY8rEk9xOktXv+XU79DrrWCvKNyqdfzF2nQu37U6h62DLwfNkw/LpdtBr9Eb9BZ10BE6QV10hvqIoBH6ir6h77UftV+13/Wte+n28o1eoTWrN/4AFbyEbw==</latexit>

Reduction:
Problem A<latexit sha1_base64="atjolN4BLFG2M2iez3G73HAq2QI=">AAAEUXicfZPNbhMxEMfdJEBJ+WjhyGXVqIJTlKCq5VKpAiqFWwlNWykbVV7vbGLFH1vb22Rj7StwhffixKNww5umSuIIRlppNL//zNiznihlVJtW6/dWpVp79PjJ9tP6zrPnL17u7r261DJTBHpEMqmuI6yBUQE9Qw2D61QB5hGDq2j8qeRXd6A0leLC5CkMOB4KmlCCTRkKefb2ZrfRarbmFmw67YXTQAs7v9mrHoexJBkHYQjDWvfbrdQMLFaGEgZFPcw0pJiM8RD6zhWYgx7Y+WGL4MBF4iCRyn3CBPPoaobFXOucR07JsRlpn5XBfzEz4oUfK7voIpjbGnNiIyXT6xll3c1wPzPJh4GlIs0MCHJ/iyRjgZFBOdYgpgqIYblzMFHUDSIgI6wwMW749YPAb5HimSzqay04HoOSkrtJYUGAuQMImBDJORaxDamICxuWuVFkvxQenQAdjsyDILETXzCdLuHUh3m+hLkPZ7MlnG30nfynp07FghLM7LdNbBTAiuLCV3Q6K7TjU1DKPSgb3mEFqaZMCk8Qu/1ZKfDZLxBDArdlAVK+ZPcQxYnf4tZpCnuyIvEUZ9N0+VvO/A7d7hJ2i8KtWttfrE3n8n2zfdQ8/HrYOP24WLpt9Abto3eojY7RKeqgc9RDBI3Qd/QD/az+qv6poVrlXlrZWuS8RmtW2/kLtBKDoQ==</latexit>µProblem B

0<latexit sha1_base64="e2UZZ+HEOwxdwaUkaCfGGFVYbRs=">AAAEb3icfZNLbxMxEMfdJkAJj6Zw4ICELKIKuFQJqiiXSOVRKdxKaNpK2SjyemcTK35sbW/zWO2VT8MVvgsfg2+ANw0kcQQj7Wo8v//MrL2eMOHM2Hr959Z2qXzr9p2du5V79x883K3uPTo3KtUUOlRxpS9DYoAzCR3LLIfLRAMRIYeLcPSh4BfXoA1T8sxOE+gJMpAsZpRYF+pXcSDSfvYON3E9d6+/q8Zi9aJfrdUP6nPDm05j4dTQwk77e6WjIFI0FSAt5cSYbqOe2F5GtGWUQ14JUgMJoSMygK5zJRFgetl8Kzned5EIx0q7R1o8j65mZEQYMxWhUwpih8ZnRfBfzA5F7seKLibHc1tjTmyV4mY9o6i7Ge6mNn7by5hMUguS3uwiTjm2CheHjiOmgVo+dQ6hmrmDwHRINKHW/ZrKPvZbJGSm8spaC0FGoJUS7qSIpMDdB0gYUyUEkVEWMBnlWVDkhmH2KffoGNhgaP8I4mzsCyaTJZz4cDpdwqkPZ7MlnG30Hf+np0nkglLCsy+b2GqAFcWZr2i1VmjLp6C1u1BZcE00JIZxJT1B5KZrpcBHv0AEMVwVBWhxk91FlE2/xZXT5FlzReIpTibJ8rec+B3a7SVs57kbtYY/WJvO+euDxpuDw8+HteP3i6HbQU/Rc/QSNdAROkYtdIo6iKKv6Bv6jn6UfpWflJ+V8Y10e2uR8xitWfnVb44ri+w=</latexit>µA=0 = µA=1 = µ0h(·, 0) = h(·, 1) = h0 (·)<latexit sha1_base64="FwyIWtsMnYlYLNxg/lWWnunrknk=">AAAEdHicfZPNbhMxEMfdJkAJXykc4WARRbQSinZRRblEqoBK4VZC01ZKosrrnSRWvPbW9jbZrPYJeBqu8CS8CGe8SSCJIxhppfH8/jOz/pgg5kwbz/u5s1sq37l7b+9+5cHDR4+fVPefXmiZKAodKrlUVwHRwJmAjmGGw1WsgEQBh8tg/KHgl7egNJPi3KQx9CMyFGzAKDE2dF2tjw56NJTmNfYOcRP/Xfnz1avF8vC6WvMa3tzwtuMvnRpa2tn1fum4F0qaRCAM5UTrru/Fpp8RZRjlkFd6iYaY0DEZQte6gkSg+9l8Pzmu20iIB1LZTxg8j65nZCTSOo0Cq4yIGWmXFcF/MTOKcjdWdNE5ntsGs2IjJdebGUXd7XA3MYN3/YyJODEg6GIXg4RjI3Fx8jhkCqjhqXUIVcweBKYjogg19n4qdey2iMlM5pWNFhEZg5IysidFBAVuf0DAhMooIiLMekyEedYrcoMg+5Q7dAJsODJ/BINs4gqm0xWcujBNVzB14Wy2grOtvpP/9NSxWFJKePZlGxsFsKY4dxWt1hptuRSUsg8q690SBbFmXApHENoRWyvw0S0QwgBuigK0eMn2IYqm2+LGavKsuSZxFKfTeHUtp26HdnsF23luR813B2vbuXjT8N82jj4f1U7eL4duDz1HL9EB8tExOkEtdIY6iKKv6Bv6jn6UfpVflGvl+kK6u7PMeYY2rNz4DSfQjQ8=</latexit>h(·, ·) satis es statistical parity<latexit sha1_base64="mMAgzLVAKS2Dpm/NnqPGnR4uAeY=">AAAEXnicfZPfa9swEMfVJuu6bF3S7WWwF7NQ6GCEpJR1L4XSrpC9dVnTFuIQZPmciOiHK8lNHOO/ZK/bH7W3/SmT04wkCtuB8HGf793Jki6IGdWm2fy1tV0qP9l5uvus8vzF3stqbf/VjZaJItAlkkl1F2ANjAroGmoY3MUKMA8Y3Abji4LfPoDSVIprk8bQ53goaEQJNjY0qFVHhz4JpfngzT/vB7V6s9Gcm7fptBZOHS3sarBfOvFDSRIOwhCGte61mrHpZ1gZShjkFT/REGMyxkPoWVdgDrqfzXeeewc2EnqRVHYJ482jqxkZ5lqnPLBKjs1Iu6wI/ouZEc/dWNFF597c1pgVGymZXs8o6m6Ge4mJPvUzKuLEgCCPfxElzDPSK87YC6kCYlhqHUwUtQfhkRFWmBh7E5UDz20R45nMK2stOB6DkpLbk8KCALMbEDAhknMswsynIswzv8gNguxL7tAJ0OHI/BVE2cQVTKdLOHVhmi5h6sLZbAlnG30n/+mpY7GgBLPs2yY2CmBFce0q2u0V2nYpKGUfVOY/YAWxpkwKRxDaYVop8NktEEIE90UBUrxk+xDFqdvi3mry7HRF4igup/HyWi7dDp3OEnby3I5ayx2sTefmqNH62Dj+elw/O18M3S56i96hQ9RCJ+gMtdEV6iKCEvQd/UA/S7/LO+W9cvVRur21yHmN1qz85g+De4bt</latexit>

fi

fi

fi

fi

[Zhao et al., JMLR’ 22b]

19

An Optimal Fair Classi er via Post-Processing
Bad news: We know that learning the Bayes optimal classi er iscomputationally hard in general, even for simple function classes
like linear predictors
Instead, what we can aim for is:Given oracle access to Bayes classi ers, could we construct analgorithm to learn the optimal fair classi er?

20
fi

fi

fi

fi

[Zhao et al., JMLR’ 22b]

An Optimal Fair Classi er via Post-Processing
A constructive algorithm for the optimal fair classi er:-

It is a randomized classi er-

The classi er needs to have explicit access to the sensitive attribute

21
fi

fi

fi

fi

[Zhao et al., JMLR’ 22b]

An Optimal Fair Classi er via Post-Processing
Theorem (noiseless): For any distribution μ over (X, A, Y ) such that
YA=0 = h*(X) and YA=1 = h*(X), the classi er h* constructed by the
0
1
Fair

algorithm satis es statistical parity and is optimal, i.e.,⇤⇤"A=0 (hFair ) + "A=1 (hFair ) =<latexit sha1_base64="ySBmz0W9bg6VXiKERkr98cUCaZA=">AAAEqXicfZPbbhMxEIbdNkAJpxQuubGoKhUqRUlVUW4ildKicNeWntRsiLzeSWLVa29tpzlYfjdegxfgFh4Bb5oqiQOMFGk03z/zb2xPnHGmTaXyY2l5pfDg4aPVx8UnT589f1Fae3muZU9ROKOSS3UZEw2cCTgzzHC4zBSQNOZwEV9/yvnFLSjNpDg1wwyaKekI1maUGF9qla4iUEqqlv2Ia7jiNrstGxkYGPuZMOXct3dv8Rae1VT/qqnh6AC4Ifdk/8S5Vmm9Uq6MAy8m1UmyjiZx1Fpb2Y0SSXspCEM50bpRrWSmaYkyjHJwxainISP0mnSg4VNBUtBNOz4Ehzd8JcFtqfxPGDyuznZYkmo9TGOvTInp6pDlxX8x001dWMtdtMPjmGNebKTker4jn7tYbvRM+0PTMpH1DAh69y/aPY6NxPl14YQpoIYPfUKoYv4gMO0SRajxl1rcwKFFRkbSFecsUnINSsrUnxQRFLj/AAF9KtOUiMRGTCTORnlvHNsvLqB9YJ2uuRe0bT8UDAZTOAjhcDiFwxCORlM4WvDt/8dTZ2JCKeH26yI2CmBGcRoq6vUZWg/p+LV7wS1RkGnGpQgEid/LmQEH4YAE2nCTD6D5S/YPUdRCixuvcbY2IwkUh4Nsei2HocPJyRTerVo1XKzF5Hy7XH1f3jneWd/bnyzdKnqN3qBNVEW7aA/V0RE6QxR9Rz/RL/S7sFU4LlwWru6ky0uTnldoLgr0D5Fio/o=</latexit>

BR

Note:
-

This theorem assumes 0 Bayes errors, so
fairness constraint-

It shows that learning fair classi er is not much harder than learning
the group-wise Bayes classi ers

BR is purely due to the

22
fi

fi

fi

fi

[Zhao et al., JMLR’ 22b]fi

<latexit sha1_base64="N9S7BhcM4MNL2HEsAWtbshDcVSs=">AAAEYXicfZPfb9owEMfdwraW/aLssS/RUKU9IZiqdg+rVG2txN46VtpKBCHHuRQLx05tpyRY+Vf2uv1Le94/MgeYAKPtpEin+3zvzjn7goRRpdvtXzu7leqTp8/29mvPX7x89bp+0LhRIpUE+kQwIe8CrIBRDn1NNYO7RAKOAwa3weRzyW8fQSoq+LXOExjG+J7TiBKsbWhUb/gXwDQeGV9Dps2nXlGM6s12qz03b9vpLJ0mWtrV6KBy6oeCpDFwTRhWatBpJ3posNSUMChqfqogwWSC72FgXY5jUEMzP3zhHdlI6EVC2o9rbx5dzzA4ViqPA6uMsR4rl5XBfzE9jgs3VnZRhTe3DWbFWgimNjPKutvhQaqjD0NDeZJq4GTxF1HKPC28csxeSCUQzXLrYCKpHYRHxlhiou1l1I48t0WCZ6KobbSI8QSkELGdFOYEmD0AhykRcYx5aHzKw8L4ZW4QmC+FQ6dA78f6ryAyU1eQZSuYuTDPVzB34Wy2grOtvtP/9FQJX1KCmfm2jbUEWFNcu4pud412XQpS2gdl/EcsIVGUCe4IQrtPawUu3AIhRPBQFiDlS7YPkZ+5LR6spjBnaxJHcZklq2u5dDv0eiu4WLWOu1jbzs37Vuekdfz1uHn+cbl0e+gQvUXvUAedonPURVeojwjK0Hf0A/2s/K7uV+vVxkK6u7PMeYM2rHr4B8RpiT4=</latexit>An Optimal Fair Classi er via Post-Processing
Extension to multi-groups under noiseless multi-class classi cation:- Let m ≥ 2 be the number of classes and n ≥ 2 be the number of groups- Let Δm be the standard m − 1 dimensional probability simplex-

Let pi ∈ Δm be the marginal label distribution of Y from group i ∈ [n]m
Let OPT ({pi}i=1) be the optimal value of the above barycenter problem

under the Total Variation (TV) distance, then,nnεA=a(h) ≥ OPT ({pi}i=1)
∑
a=1

23
fi

fi

[Zhao et al., JMLR’ 22b]

An Optimal Fair Classi er via Post-Processingm
Let OPT ({pi}i=1) be the optimal value of the above barycenter problem

under the Total Variation (TV) distance, then,nnεA=a(h) ≥ OPT ({pi}i=1)
∑
a=1
-

-

-

We no longer have analytical lower bound but the optimal value can becomputed e ciently via a linear program
When n = 2, the OPT has a closed form via ΔBR, which is essentially the TV
distance between p0 and p1
An extended version of the post-processing algorithm still works, by properly(0, 0, 1)choosing the randomization con guration
p4

p1
q⇤

p3

fi

(1, 0, 0)fi

ffi[Zhao et al., JMLR’ 22b]

p5

p2
24

(0, 1, 0)

An Optimal Fair Classi er via Post-Processing
What about multi-groups but noisy multi-class classi cation?
- Let m ≥ 2 be the number of classes and n ≥ 2 be the number of groups- Let Δm be the standard m − 1 dimensional probability simplex

Let fi ∈ Δ|m | be the Bayes score function of group i ∈ [n], i.e., fi(x) ∈ Δm with-fi(x)( j) = Pr(Y = j ∣ X = x, A = i)Price of fairness:(Wasserstein-Barycenter):
n

min
q

subjectto

1
W1 (fi♯μiX, q)2∑
i=1

q ∈ ΔmNote: fi♯μiX is the push-forward distribution over Δm given by the mapping fi acting
on the marginal distribution of X, i.e., μiX. W1( ⋅ , ⋅ ) is the 1-Wasserstein distanceunder the ℓ1 metric

25
fi

fi

𝒳

[Xian et al., ICML’ 23]

An Optimal Fair Classi er via Post-Processing
Price of fairness: (Wasserstein-Barycenter):minqsubjectton1
W1 (fi♯μiX, q)2∑
i=1

q ∈ Δm

A two-step procedure:
1. Find the barycenter under the W1 metric

2. Find the (randomized) transportation map to the barycenter as the postprocessing map
q(e3)
q(e1)
e3
e1

q(e2)
r

fi

e2
26
[Xian et al., ICML’ 23] Note: our algorithm also allows a relaxation of the exact fairness as wellExperiments-

FairProjection (Calmon et al. NeurIPS’22) is another post-processing method forfairness under the same setting-

FairProjection-KL works by minimizing the KL distance-

FairProjection-CE works by minimizing the reverse-KL distance-Top-left points should be preferred (Pareto-optimal)[Xian et al., ICML’ 23]27

Summary
Inherent tradeo s by enforcing statistical parity under di erent
settings:[Chzhen et al. NeurIPS’ 20]:

[Zhao et al. JMLR’ 22]:

[Xian et al. ICML’ 23]:

The prices of fairness are characterized by the barycenter problems
under di erent metrics
ff

-

fi

Randomization is a powerful tool to enable the construction of the
optimal fair predictor

ffi

-

ff

Attribute-aware post-processing is su cient to achieve the optimal fair
prediction, under both regression and classi cation settings

ff

-

28

Thanks

Q&A

Ruicheng Xian
Code: https://github.com/rxian/fair-classi cation

fi

ff

fi

ff

Papers:
1. Inherent Tradeo s in Learning Fair Representations, JMLR’ 22b
2. Fundamental Limits and Tradeo s in Invariant Representation Learning, JMLR’ 22a
3. Fair and Optimal Classi cation via Post-Processing, ICML’ 2329