The Utility-Fairness Trade-Offs in Learning Fair Representations

Wayne State University (CSE Graduate Seminar)

Progress In Machine Learning

State-of-Affairs

Today's Agenda

A Fork in the Road

• Design metric to measure sensitive demographic attribute information
• non-parameteric statistical dependence measures, this talk



• Learn metric to measure semantic attribute information
• probably feasible, many prior attempts

Game Theoretic Formulation

• Three player game between:
• Encoder extracts features $\mathbf{z}$
• Target Predictor for desired task from features $\mathbf{z}$
• Adversary extracts sensitive information from features $\mathbf{z}$
$$ \begin{equation} \begin{aligned} \min_{\mathbf{\Theta}_E,\mathbf{\Theta}_T} & \underbrace{\color{cyan}{J_t(\mathbf{\Theta}_E,\mathbf{\Theta}_T)}}_{\color{cyan}{\text{error of target}}} \quad s.t. \text{ } \min_{\mathbf{\Theta}_A} \underbrace{\color{orange}{J_s(\mathbf{\Theta}_E,\mathbf{\Theta}_A)}}_{\color{orange}{\text{error of adversary}}} \geq \alpha \nonumber \end{aligned} \end{equation} $$
• Adversary: learned measure of semantic attribute information

How do we learn model parameters?

• Simultaneous/Alternating Stochastic Gradient Descent
• Update target while keeping encoder and adversary frozen.
• Update adversary while keeping encoder and target frozen.
• Update encoder while keeping target and adversary frozen.

ARL is Suboptimal

Unstable Optimization

Lack of Invariance Guarantees

Overview of our Solutions

• Standard Adversarial Representation Learning
• Linear Adversarial Measure: linear dependency between $Z$ and $S$ [ICCV 2019, CVPRW 2020]
• Non-Linear Adversarial Measure: Beyond linear dependency between $Z$ and $S$, but not all types [ECML 2021]
• Universal Dependence Measure: All types of dependency between $Z$ and $S$ [TMLR 2022]
• End-to-End Universal Dependence Measure: All types of dependency between $Z$ and $S$ [Under Review]

Covariance Operator and Dependence Measure

Linear Dependence: $\displaystyle C_{SZ}\approx\displaystyle \frac{1}{n}{\color{Maroon}\tilde{\bm S}} \tilde{\bm Z}^T$

Universal Dependence: $\displaystyle \Sigma_{SZ}\approx\frac{1}{n}{\color{Maroon}\tilde{\bm K}_S} \tilde{\bm K}_Z$

$\mathcal H_Z\times\mathcal H_S\rightarrow \mathbb R:\ Cov\left(\alpha(Z),\ \beta({\color{Maroon}S})\right)$

$=\big\langle \beta, \Sigma_{SZ}\, \alpha \big\rangle_{\mathcal H_S}, \Sigma_{SZ}:\mathcal H_Z\rightarrow \mathcal H_S$

$Z \perp \!\!\! \perp {\color{Maroon}S} \Leftrightarrow \Sigma_{SZ} =0 \Leftrightarrow \left\|\Sigma_{SZ}\right\| =0$, where $\|\cdot\|$ can be any operator norm

HSIC$(Z,S)=\left\|\Sigma_{SZ}\right\|^2_{\text{HS}}=\displaystyle\sum_{\alpha\in\mathcal U_Z}\sum_{\beta\in \mathcal H_S}Cov^2(\alpha(Z),\beta(S))$

Universal Dependence Measure

$\mathcal A_r:=\Big\{(f_1,\cdots,f_r)\,|\,Cov(f_i(X), f_j(X))+\gamma \langle f_i, f_j\rangle_{\mathcal H_X}=\delta_{i,j} \Big\}$

$\displaystyle\sup_{\bm f\in\mathcal A_r} {\Big\{J(\bm f):=\color{ForestGreen}(1-\lambda)\,\text{Dep}(Z, Y)}{\color{Maroon}-\lambda\,\text{Dep}(Z, S) }\Big\}$

Solution: eigenfunctions corresponding to the $r$ largest eigenvalues of $\big({\color{ForestGreen}(1-\lambda)\, \Sigma_{YX}^*\,\Sigma_{YX}}{\color{Maroon}-\lambda\,\Sigma_{SX}^*\Sigma_{SX} }\big)\bm f = \tau (\Sigma_{XX}+\gamma I)\bm f$

• Sadeghi, Dehdashtian, Boddeti, "On Characterizing the Trade-off in Invariant Representation Learning," TMLR 2022

End-to-End Dependence Universal Measure

• Learning through alternating optimization

• Dehdashtian, Sadeghi, Boddeti, "The Utility-Fairness Trade-offs in Learning Fair Representations," (Under Review)

Estimating Trade-Offs on Real Datasets

Face Image Dataset

• Liu, Luo, Wang and Tang "Deep Learning Face Attributes in the Wild," ICCV 2015

CelebA Faces

Folktables