summaries: This paper considers fair representation as a bi-level optimization problem where the data representation is first learned then the fair predictors are optimized based on this fixed representation. A theoretical analysis on the the error gap of the implicit algorithm is conducted, and some positive results have been shown in the paper. The paper presents an interesting and topical problem and is easy to follow.    This paper proposes a methodology for fair representation learning. The core novelty of the proposal is the satisfaction of a sufficient rule. Experimental results claim good performance with respect to other approaches in terms of an accuracy-fairness tradeoff, in which a sufficient gap is measured. This paper considers the fair representation learning problem. In particular, the fairness notion utilized is (close to) the sufficient rule, and this paper proposes a bi-level implicit path alignment algorithm to (approximately) achieve it.  The contribution of the paper includes (1) an empirical algorithm for DNN to (approximately) achieve the sufficient rule, (2) theoretical analysis w.r.t. effectiveness of the algorithm as well as its application scope (classification and regression). The paper considers the learning of fair representations (and classifiers). In particular, the paper considers the (group) sufficiency rule for fairness and optimization path alignment to achieve the fairness requirement. The paper considers a representation fair if the optimization path (gradient steps) of subgroups are equivalent / invariant, with respect to optimal subgroup classifiers. To this end, the paper introduces a bi-level optimization problem for a representation function, which is solved by approximating gradients with the implicit function theorem. The approximation error of the gradients and the convergence of representation function (appendix) are analysed. Their algorithm is then experimentally tested under various datasets and compared to various baseline approaches.
abstractText: We considered a fair representation learning perspective, where optimal predictors, on top of the data representation, are ensured to be invariant with respect to different subgroups. Specifically, we formulated the problem as a bi-level optimization, where the representation is learned in the outer-level, and invariant optimal group predictors are updated in the inner-level. To avoid the high computational and memory cost of differentiating in the inner-level optimization, we proposed the implicit path alignment algorithm, which only relies on the solution of inner optimization and the implicit differentiation rather than the exact optimization path. Moreover, the proposed bi-level objective is demonstrated to fulfill the sufficiency rule, which is desirable in various practical scenarios but was not commonly studied in fair representation learning. We further analyzed the error gap of the implicit approach and empirically validated the proposed method in both classification and regression settings. Experimental results show the consistently better trade-off in prediction performance and fairness measurement.
references.authors: Alekh Agarwal Miroslav Dudı́k Zhiwei Steven Wu
references.title: Fair regression: Quantitative definitions and reduction-based algorithms
references.venue: In International Conference on Machine Learning,
references.authors: Martin Arjovsky Léon Bottou Ishaan Gulrajani David Lopez-Paz
references.title: Invariant risk minimization
references.venue: arXiv preprint arXiv:1907.02893,
references.authors: Solon Barocas Moritz Hardt Arvind Narayanan
references.title: Fairness and Machine Learning
references.venue: fairmlbook.org,
references.authors: Yoshua Bengio
references.title: Gradient-based optimization of hyperparameters
references.venue: Neural computation,
references.authors: Peter Bühlmann
references.title: Invariance, causality and robustness
references.venue: Statistical Science,
references.authors: Kai-Wei Chang Vinod Prabhakaran Vicente Ordonez
references.title: Bias and fairness in natural language processing
references.venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLPIJCNLP): Tutorial
references.authors: Yining Chen Elan Rosenfeld Mark Sellke Tengyu Ma Andrej Risteski
references.title: Iterative feature matching: Toward provable domain generalization with logarithmic environments
references.venue: arXiv preprint arXiv:2106.09913,
references.authors: Alexandra Chouldechova
references.title: Fair prediction with disparate impact: A study of bias in recidivism prediction instruments
references.venue: Big data,
references.authors: Ching-Yao Chuang Youssef Mroueh
references.title: Fair mixup: Fairness via interpolation
references.venue: arXiv preprint arXiv:2103.06503,
references.authors: Evgenii Chzhen Christophe Denis Mohamed Hebiri Luca Oneto Massimiliano Pontil
references.title: Fair regression with wasserstein barycenters
references.venue: arXiv preprint arXiv:2006.07286,
references.authors: P. Concus G. Golub Gérard Meurant
references.title: Block preconditioning for the conjugate gradient method
references.venue: Siam Journal on Scientific and Statistical Computing,
references.authors: Elliot Creager Jörn-Henrik Jacobsen Richard Zemel
references.title: Environment inference for invariant learning
references.venue: In International Conference on Machine Learning,
references.authors: Jacob Devlin Ming-Wei Chang Kenton Lee Kristina Toutanova. Bert
references.title: Pre-training of deep bidirectional transformers for language understanding
references.venue: arXiv preprint arXiv:1810.04805,
references.authors: Kawin Ethayarajh
references.title: Is your classifier actually biased? measuring fairness under uncertainty with bernstein bounds
references.venue: In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 2914–2919,
references.authors: Richard Ribón Fletcher Audace Nakeshimana Olusubomi Olubeko
references.title: Addressing fairness, bias, and appropriate use of artificial intelligence and machine learning in global health
references.venue: Frontiers in Artificial Intelligence,
references.authors: Chuan Guo Geoff Pleiss Yu Sun Kilian Q Weinberger
references.title: On calibration of modern neural networks
references.venue: In International Conference on Machine Learning,
references.authors: Umang Gupta Aaron Ferber Bistra Dilkina Greg Ver Steeg
references.title: Controllable guarantees for fair outcomes via contrastive information estimation
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Moritz Hardt Eric Price Nati Srebro
references.title: Equality of opportunity in supervised learning
references.venue: Advances in neural information processing systems,
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Deep residual learning for image recognition
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Ray Jiang Aldo Pacchiano Tom Stepleton Heinrich Jiang Silvia Chiappa
references.title: Wasserstein fair classification
references.venue: In Uncertainty in Artificial Intelligence,
references.authors: Thomas Kehrenberg Myles Bartlett Oliver Thomas Novi Quadrianto
references.title: Null-sampling for interpretable and fair representations
references.venue: In European Conference on Computer Vision,
references.authors: Byungju Kim Hyunwoo Kim Kyungsu Kim Sungjin Kim Junmo Kim
references.title: Learning not to learn: Training deep neural networks with biased data
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Junpei Komiyama Akiko Takeda Junya Honda Hajime Shimao
references.title: Nonconvex optimization for regression with fairness constraints
references.venue: Proceedings of the 35th International Conference on Machine Learning,
references.authors: Volodymyr Kuleshov Nathan Fenner Stefano Ermon
references.title: Accurate uncertainties for deep learning using calibrated regression
references.venue: In International Conference on Machine Learning,
references.authors: Lydia T. Liu Max Simchowitz Moritz Hardt
references.title: The implicit fairness criterion of unconstrained learning
references.venue: Proceedings of the 36th International Conference on Machine Learning,
references.authors: Ziwei Liu Ping Luo Xiaogang Wang Xiaoou Tang
references.title: Deep learning face attributes in the wild
references.venue: In Proceedings of International Conference on Computer Vision (ICCV),
references.authors: Francesco Locatello Gabriele Abbati Tom Rainforth Stefan Bauer Bernhard Schölkopf Olivier Bachem
references.title: On the fairness of disentangled representations
references.authors: David Madras Elliot Creager Toniann Pitassi Richard Zemel
references.title: Learning adversarially fair and transferable representations
references.venue: In International Conference on Machine Learning,
references.authors: Ninareh Mehrabi Fred Morstatter Nripsuta Saxena Kristina Lerman Aram Galstyan
references.title: A survey on bias and fairness in machine learning
references.venue: ACM Computing Surveys (CSUR),
references.authors: Ziad Obermeyer Brian Powers Christine Vogeli Sendhil Mullainathan
references.title: Dissecting racial bias in an algorithm used to manage the health of populations
references.venue: Science, 366(6464):447–453,
references.authors: Fabian Pedregosa
references.title: Hyperparameter optimization with approximate gradient
references.venue: In International conference on machine learning,
references.authors: Geoff Pleiss Manish Raghavan Felix Wu Jon Kleinberg Kilian Q Weinberger
references.title: On fairness and calibration
references.venue: arXiv preprint arXiv:1709.02012,
references.authors: Manish Raghavan Solon Barocas Jon Kleinberg Karen Levy
references.title: Mitigating bias in algorithmic hiring: Evaluating claims and practices
references.venue: In Proceedings of the 2020 conference on fairness, accountability, and transparency,
references.authors: Aravind Rajeswaran Chelsea Finn Sham Kakade Sergey Levine
references.title: Meta-learning with implicit gradients
references.venue: In Advances in neural information processing systems,
references.authors: Elan Rosenfeld Pradeep Ravikumar Andrej Risteski
references.title: The risks of invariant risk minimization
references.venue: arXiv preprint arXiv:2010.05761,
references.authors: Michael W Sjoding Robert P Dickson Theodore J Iwashyna Steven E Gay Thomas S Valley
references.title: Racial bias in pulse oximetry measurement
references.venue: New England Journal of Medicine,
references.authors: Jiaming Song Pratyusha Kalluri Aditya Grover Shengjia Zhao Stefano Ermon
references.title: Learning controllable fair representations
references.venue: In The 22nd International Conference on Artificial Intelligence and Statistics,
references.authors: Rich Zemel Yu Wu Kevin Swersky Toni Pitassi Cynthia Dwork
references.title: Learning fair representations
references.venue: In International conference on machine learning,
references.authors: Brian Hu Zhang Blake Lemoine Margaret Mitchell
references.title: Mitigating unwanted biases with adversarial learning
references.venue: In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society,
references.authors: Wenbin Zhang Eirini Ntoutsi
references.title: Faht: an adaptive fairness-aware decision tree classifier
references.venue: arXiv preprint arXiv:1907.07237,
references.authors: Han Zhao Amanda Coston Tameem Adel Geoffrey J Gordon
references.title: Conditional learning of fair representations
references.venue: arXiv preprint arXiv:1910.07162,
references.authors: Based on Kuleshov
references.title: 2018), we first compute the predicted cumulative distribution (Ŷ0) of at point t: D0(Ŷ0 ≤ t) = α, then we compute the corresponding ground truth cumulative distribution
sections.heading: 1 INTRODUCTION
sections.text: Machine learning has been widely adopted in the real world decision-making practice such as job candidate screening (Raghavan et al., 2020) and credit application. However, it has been observed that learning algorithms treated some groups of population unfavorably, for example, denying credit on the grounds of gender, age or ethnicity (Hardt et al., 2016). To this end, algorithmic fairness that is to mitigate the prediction bias for different subgroups has recently received tremendous attentions.
  With the rapid advancement of representation learning (LeCun et al., 2015), learning a fair embedding (Zemel et al., 2013) has been recently highlighted. Specifically, the learned fair representation can easily transfer the unbiased prior knowledge to the downstream tasks, with various successful applications in computer vision (Kim et al., 2019; Kehrenberg et al., 2020), language understanding (Chang et al., 2019; Ethayarajh, 2020) and artificial intelligence for health (Fletcher et al., 2021). Typically, the fair representation learning is achieved by adding various statistical fair metrics during the training process.
  Based on this, most existing fair representation approaches in classification or regression principally aim to meet the independence or separation rule, e.g., (Madras et al., 2018; Song et al., 2019; Chzhen et al., 2020). However, in various realworld scenarios, the sufficiency rule is preferable. For example, health systems rely on commercial algorithms to identify and help patients with complex health needs. The algorithm outputs a healthcare need score, where a higher score indicates the patient is sicker and requires more healthcare. Obermeyer et al. (2019) revealed that a widely
  used algorithm, typical of this industry-wide approach and affecting millions of patients, exhibits significant racial bias. At a given predicted healthcare need score Ŷ = t, Black patients are considerably sicker than White patients (Eblack[Y |Ŷ = t] > Ewhite[Y |Ŷ = t]). Obermeyer et al. (2019) also pointed out that remedying the disparity would increase the percentage of Black patients receiv-
  ing additional healthcare from 17.7 to 46.5%. Moreover, it has been theoretically justified (Barocas et al., 2019) that the Sufficiency rule is generally not compatible with Independence and Separation. Thus learning the fair representation w.r.t. the sufficiency rule is promising in both the algorithmic design and real-world applications.
  In this paper, we address the sufficiency rule by considering the following intuition: given a fixed representation function, if the optimal predictor that learned on the embedding space are invariant from different sub-groups, then the corresponding representation function is fair. Fig. 1 provides an illustrative example. when the representation function λ : X → Z is unfair and we adopt gradient descent to learn the predictor h : Z → R. The optimal predictors of different subgroups (blue, red) are not invariant, resulting in biased predictions. We will later demonstrate such an intuition ensures the learned representation satisfying the sufficiency rule (Liu et al., 2019; Chouldechova, 2017).
  The aforementioned intuition can be naturally formulated as a bi-level optimization problem, where we aim to adjust the representation λ (in the outer-level) to satisfy the invariant optimal predictor h (in the inner-level). Thus, when we adopt the gradient-based approach in solving the bi-level objective, a straightforward solution is to learn the representation λ to fulfill the identical explicit gradient-descent directions in learning predictor h? of different groups, shown in Fig. 2(a). Intuitively, if the inner gradient descent step of each sub-group is identical, their final predictors (as the approximation of h?) will be invariant. However, the corresponding algorithmic realization is challenging in deep learning: 1) It requires storing the whole gradient steps, which induces a high memory burden. 2) the embedding function λ is optimized via backpropagation from the whole gradient optimization path, which induces a high computational complexity.
  To this end, we propose an implicit path alignment, shown in Fig. 2(b). Notably, we only consider the final (t-th) update of the predictor h(t), then we update representation function λ by approximating its gradient at point h(t) through the implicit function (Bengio, 2000). By using the gradient approximation, it is no more required to store the whole gradient step and conduct the backpropagation through the entire path. Overall, the highlights in this paper are as follows:
  Fair-representation learning to satisfy the sufficiency rule Instead of enforcing the independence or separation rule, the considered fair-representation criteria is proved to satisfy the sufficiency rule in both classification and regression. We also find such a criteria is intrinsically consistent with the recent Invariant Risk Minimization (IRM) (Arjovsky et al., 2019; Bühlmann, 2020), which aims to eliminate suspicious correlations while keeping robust correlations that are invariant across different environments. Intuitively, reducing the correlation w.r.t. the protected attributes enables the fair representation.
  Principled and efficient algorithm We proposed a novel implicit path alignment algorithm to learn the fair representation, which addressed the prohibitive memory and computational cost in the original bi-level objective. Besides, we analyzed the approximation error gap of the proposed implicit algorithm, which induces a trade-off between the correct gradient estimation and fairness measures.
  Improved fairness in classification and regression We evaluated the implicit algorithm in both classification and regression with tabular, computer vision and NLP datasets. Compared to the baselines, the implicit algorithm effectively improved the fairness with a smaller sufficiency gap.
sections.heading: 2 PRELIMINARIES
sections.text: We suppose the input X ∈ X , the ground truth label Y ∈ Y , and the algorithmic output Ŷ ∈ Y . Throughout the paper, we only consider binary sensitive attribute (i.e, two sub-groups) with distributions D0 and D1. Then based on (Liu et al., 2019), the sufficiency rule is defined as:
  ED0 [Y |Ŷ = t] = ED1 [Y |Ŷ = t], ∀t ∈ Y (1) To measure the fairness w.r.t. the sufficiency rule, we propose the sufficiency gap as the metric. Since we aim to evaluate the fairness in both binary classification (Y ∈ {−1, 1}) and regression (Y ∈ R), the metric is separately defined on these two scenarios. Sufficiency gap in binary classification Based on the sufficiency rule, the sufficiency gap in binary classification is naturally defined as:
  ∆SufC = ∑
  y∈{−1,1}
  |D0(Y = y|Ŷ = y)−D1(Y = y|Ŷ = y)| (2)
  ∆SufC encourages the two subgroups with identical Positive predicted value (PPV) and Negative predicted value (NPV). On the practical side, considering the healthcare evaluation system outputs either High Risk or Low Risk, Obermeyer et al. (2019) essentially revealed Dblack(Y = High Risk|Ŷ = Low Risk) > Dwhite(Y = High Risk|Ŷ = Low Risk): the severity of Black patients is actually underestimated. Thus if ∆SufC is small, the racial discrimination can be remedied.
  Sufficiency gap in regression Based on the sufficiency rule and (Kuleshov et al., 2018), the sufficiency gap in regression is defined as:
  ∆SufR = ∫ t∈Y |D0(Y ≤ t|Ŷ ≤ t)−D1(Y ≤ t|Ŷ ≤ t)|dt (3)
  ∆SufR ∈ [0, 1] is an approximation of |D0(Y = y|Ŷ = y)−D1(Y = y|Ŷ = y)|, ∀y ∈ R, since the latter is difficult to estimate. From the practical aspect, assuming the health system outputs a realvalue healthcare score Ŷ = t (higher indicates sicker), Obermeyer et al. (2019); Sjoding et al. (2020) observed Dblack(Y > t|Ŷ ≤ t) > Dwhite(Y > t|Ŷ ≤ t): for the patients whose predicted healthcare score is less than t, the actual proportion of sicker (Y > t) in Black patients is considerably higher than White patients. Therefore a small ∆SufR suggests an improved disparity.
sections.heading: 3 PROBLEM SETUP
sections.text: We denote the representation function λ that maps the input X into the latent variable Z, the prediction function h such that h : Z → R for regression and h : Z → {−1, 1} for binary classification. We then denote the prediction loss as `, the prediction loss on subgroup D0,D1 is expressed as:
  L0(h, λ) = E(x,y)∼D0`(h ◦ λ(x), y), L1(h, λ) = E(x,y)∼D1`(h ◦ λ(x), y)
  According to the intuition, we aim to solve the following bi-level objective: min λ L0(h?0, λ) + L1(h?1, λ) (Outer level)
  s.t. h?0 = h ? 1, h ? 0 ∈ argmin h L0(h, λ), h?1 ∈ argmin h L1(h, λ). (Inner level)
  Specifically, in the outer level, we aim to find a representation λ for minimizing the prediction error, given the optimal predictor (h?0, h ? 1) on the embedding space Z . As for the inner level, given a fixed representation λ, h?0, h ? 1 are the optimal predictor for each sub-group. The constraints h ? 0 = h ? 1 additionally encourage the invariant optimal predictors from D0, D1.
  Relation to the explicit path alignment In deep learning we adopt the gradient-based approach to minimize the loss, therefore h? in the inner level is approximated as h(t+1), the t-th update in the gradient descent: h?0 ≈ h(0)− ∑ t∇hL0(h(t), λ), h?1 ≈ h(0)− ∑ t∇hL1(h(t), λ), where h(0) is the common initialization. Thus the invariant optimal predictor is equivalent to:∑ t ∇hL0(h(t), λ) = ∑ t ∇hL1(h(t), λ).
  The aforementioned equation suggests learning a representation λ that ensures the identical optimization path w.r.t. h for each sub-group, which recovers the explicit path alignment.
  Relation to the Sufficiency rule We further demonstrate the relation between the bi-level objective and Sufficiency rule. Proposition 1. If we specify the prediction loss ` as logistic regression loss in the classification log(1 + exp(−yh(z))) with Y = {−1, 1} and the square loss in the regression (h(z) − y)2 with Y ⊂ R. Then minimizing the inner-level loss is equivalent to:
  ED0 [Y |Z = z] = ED1 [Y |Z = z], ED0 [Y |Ŷ = h?(z)] = ED1 [Y |Ŷ = h?(z)],
  where h? = h?0 = h ? 1 and z = λ(x).
  Proposition 1 reveals that the objective of inner-level loss is to encourage the sufficiency rule.
sections.heading: 4 PRACTICAL ALGORITHMS
sections.text: In this section, we propose an implicit alignment in deep learning, where λ and h are implemented by the neural network. We also reformulate as the original objective through Lagrangian relaxation:
  min λ L0(h?0, λ) + L1(h?1, λ) +
  κ 2 ‖h?0 − h?1‖22 (Outer level)
  s.t. h?0 ∈ argmin h L0(h, λ), h?1 ∈ argmin h L1(h, λ), (Inner level)
  where κ > 0 is the coefficient to control the fairness. Then we will drive the approximated gradient w.r.t. λ, which contains the following key elements.
  Solving the inner optimization Given a fixed representation λ, we find h 0, h 1 such that:
  ‖h?0 − h 0‖ ≤ , ‖h?1 − h 1‖ ≤ ,
  where is the optimization tolerance. Besides, h?1 and h 1 are essentially the function of λ, i.e., h 1 depends on the predefined representation function λ.
  Computing the gradient of λ Given the approximate solution h 0, h 1, we can compute the gradient w.r.t. λ (referred as ˜grad(λ)) 1 in the outer-level:
  ˜grad(λ) =∇λL0(h 0, λ) + (∇λh 0) T (∇h0L0(h 0, λ) + κ(h 0 − h 1))
  +∇λL1(h 1, λ) + (∇λh 1) T (∇h1L1(h 1, λ)− κ(h 0 − h 1)) .
  Where ∇h0L0(h 0, λ) is the partial derivative in the loss w.r.t. the first term (about h0), evaluated at h 0. Also ∇λL0(h 0, λ) is the partial derivative w.r.t. the second term (about λ).
  Implicit function for approximating the gradient In order to compute ˜grad(λ) in autograd, we need to estimate ∇λh 0 and ∇λh 1. We herein adopt the implicit function (Bengio, 2000) to approximate ∇λh 0, which has been adopted in the hyperparameter optimization (Pedregosa, 2016) and meta-learning (Rajeswaran et al., 2019).
  Concretely, if the prediction loss is smooth and there exist stationary points to achieve optimal, we have: ∇h0L0(h?0(λ), λ) = 0,∇h1L0(h?1(λ), λ) = 0. Then differentiating w.r.t. λ will induce: d (∇h0L0(h?0(λ), λ)) /dλ = ∇2h0L0(h ? 0, λ)∇λh?0+∇λ∇h0L0(h?0, λ) = 0.2 Thus we have∇λh?0 =
  − ( ∇2h0L0(h ∗ 0, λ) )−1 (∇λ∇h0L0(h∗0, λ)), where the Hessian matrix∇2h0L0(h ∗ 0, λ) is assumed to be invertible.
  Through the implicit function, we can approximate∇λh 0 as: ∇λh 0 ≈ − ( ∇2h0L0(h 0, λ) )−1 (∇λ∇h0L0(h 0, λ))
  As for∇λh 1, we have the similar result: ∇λh 1 ≈ − ( ∇2h1L1(h 1, λ) )−1 (∇λ∇h1L1(h 1, λ)).
  1We denote the ground truth gradient as grad(λ) if we adopt optimal predictor h?0, h?1 in the computation. 2d(·)/dλ denotes the total derivative.
  Algorithm 1 Implicit Path Alignment Algorithm Ensure: Representation function λ, predictor h0, h1, datasets from two sub-groups D0. D1.
  1: for mini-batch of samples from (D0,D1) do 2: Solving the inner-level optimization with tolerance . Obtaining h 0, h 1. 3: Solving Eq. (4) with tolerance δ. Obtaining pδ0 and p δ 1. 4: Computing ˜grad δ (λ) (gradient of representation λ) 5: Updating λ through autograd: λ← λ− ˜gradδ(λ) 6: end for 7: return λ, h 0, h 1
  Efficient and numerical stable gradient estimation Plugging in the approximations, the gradient w.r.t λ is approximated as:
  ˜grad(λ) ≈ ∇λL0(h 0, λ)− (∇λ∇h0L0(h 0, λ)) T (∇2h0L0(h 0, λ))−1 (∇h0L0(h 0, λ) + κ(h 0 − h 1))︸ ︷︷ ︸
  p0 +∇λL1(h 1, λ)− (∇λ∇h1L1(h 1, λ)) T (∇2h1L1(h 1, λ))−1 (∇h1L1(h 1, λ)− κ(h 0 − h 1))︸ ︷︷ ︸
  p1
  However, the current form is still computationally expensive due to the computation of inverse Hessian matrix. To this end, we denote p0 and p1 as the inverse-Hessian vector product. Then computing p0 and p1 is equivalent to solve the following quadratic programming (QP):
  argminp̂0 1 2 p̂T0 ( ∇2h0L0(h 0, λ) ) p̂0 − p̂ T 0 (∇h0L0(h 0, λ) + κ(h 0 − h 1)) argminp̂1 1 2 p̂T1 ( ∇2h1L1(h 1, λ) ) p̂1 − p̂ T 1 (∇h1L1(h 1, λ)− κ(h 0 − h 1)) (4)
  Since it is a typical QP problem and we adopt conjugate gradient method (Concus et al., 1985; Rajeswaran et al., 2019), which can be updated efficiently through autograd via computing the Hessian-vector product. We additionally suppose the optimization error in the QP as δ, i.e.: ‖p0 − pδ0‖ ≤ δ, ‖p1 − pδ1‖ ≤ δ, then the gradient w.r.t representation λ can be finally expressed as:
  ˜grad δ (λ) = ∇λL0(h 0, λ)− (∇λ∇h0L0(h 0, λ)) T pδ0 +∇λL1(h 1, λ)− (∇λ∇h1L1(h 1, λ)) T pδ1
  The ˜grad δ (λ) can be also efficiently estimated through Hessian vector product via autograd without explicitly computing the Hessian matrix.
  Proposed algorithm Based on the key elements, the proposed algorithm is shown in Algo. 1.
sections.heading: 4.1 THE COST OF IMPLICIT ALGORITHM: APPROXIMATION-FAIR TRADE-OFF
sections.text: Theorem 1 (Approximation Error Gap). Suppose that (1) Smooth Predictive Loss. The first-order derivatives and second-order derivatives of L are Lipschitz continuous; (2) Non-singular Hessian matrix. We assume ∇h0,h0L0(h0, λ),∇h1,h1L1(h1, λ), the Hessian matrix of the inner optimization problem, are invertible. (3) Bounded representation and predictor function. We assume the λ and h are bounded, i.e., ‖λ‖, ‖h‖ are upper bounded by the predefined positive constants. Then the approximation error between the ground truth and algorithmic estimated gradient w.r.t. the representation is be upper bounded by:
  ‖grad(λ)− ˜gradδ(λ)‖ = O(κ + + δ).
  The proof is delegated in Appendix B. We also discuss the assumptions to guarantee the convergence of Algorithm 1, shown in Appendix C.
  Theorem 1 reveals that the gradient approximation error depends on the two-level optimization tolerance , δ and the coefficient of fair constraints κ. Specifically, the error gap reveals the inherent trade-off in accurate gradient estimation and fair-representation learning. If we fix the optimization tolerance and δ, a smaller κ indicates a better approximation of the gradient, which yields weak fair constraints. Thus the implicit alignment introduces a trade-off in the prediction performance (i.e., correct approximation of the gradient) and fairness measurement.
sections.heading: 5 RELATED WORK
sections.text: Fair Machine Learning Below we only list the most related work in the fairness and refer to the survey paper (Mehrabi et al., 2021) for details in the algorithmic fairness. In the classification, various methods in learning fair representations have been proposed. Specifically, a common strategy is to introduce the statistical constraints as the regularization during the training, e.g., demographic parity (DP) (Zhang et al., 2018; Madras et al., 2018; Song et al., 2019; Jiang et al., 2020; Kehrenberg et al., 2020) or equalized odds (EO) (Song et al., 2019; Gupta et al., 2021) as the proxy of the separation and independence rule. Another direction is to disentangle the data for factorizing meaningful representations such as (Locatello et al., 2019). Intuitively, the disentangled embedding is independent of the sensitive attribution, thus reflecting a fair representation w.r.t. the independence rule, which can be potentially problematic when the label distributions of subgroups vary dramatically (Zhao et al., 2019).
  Fairness has also been extended to the fields beyond classification. For instance, in the regression problem (Komiyama et al., 2018; Agarwal et al., 2019), the bounded group loss has been proposed as the fair measure: if prediction loss in each subgroup is smaller than , the regression is -level fair. In fact, the fair criteria in our paper is not equivalent to -fair. Given a fixed λ, the -level fair does not guarantee the optimal and invariant predictor for each subgroup and vice versa.
  The sufficiency rule has also been discussed in the previous work. Notably, Chouldechova (2017); Liu et al. (2019) proposed the sufficiency gap in classification for measuring fairness w.r.t. the sufficiency rule. Liu et al. (2019) also discussed the inequivalence between the sufficiency gap and probabilistic calibration (Guo et al., 2017) (referred as calibration gap). According to Pleiss et al. (2017), the calibration rule is a stronger condition than sufficiency rule while it simultaneously hurts the prediction performance. Throughout this paper, we only consider the sufficiency rule. The triple trade-off between the calibration rule, sufficiency rule, and prediction performance will be left as future work.
  Invariant Risk Minimization The analyzed fair-representation criteria shares a quite similar spirit to the IRM (Arjovsky et al., 2019; Bühlmann, 2020; Creager et al., 2021), where an algorithm IRM v1 is proposed to enable the out-of-distribution (OOD) generalization. The key difference between our work and (Arjovsky et al., 2019) lies in the algorithmic aspect: it has been theoretically justified that the originally proposed IRM v1 does not necessarily capture the invariance (Rosenfeld et al., 2020). By contrast, we directly solve the bi-level objective in the context of deep-learning and propose an efficient practical algorithm with better empirical performance than IRM v1. Besides, based on Chen et al. (2021), the proposed algorithm does not provably guarantee the OOD generalization property due to the limited subgroups (N = 2) considered within the paper.
  6 EXPERIMENTS
  6.1 EXPERIMENTAL SETUP
  In the paper, we adopt the sufficiency gap as fair metrics, where Ŷ is denoted as:
  Ŷ = { h 0 ◦ λ(X), X ∈ D0 h 1 ◦ λ(X), X ∈ D1
  Then in the binary classification, we can estimate ∆SufC =∑ y∈{−1,+1} |D0(Y = y|Ŷ = y) − D1(Y = y|Ŷ = y)| from the data. As for regression, the sufficiency gap ∆SufR =∫ t |D0(Y ≤ t|Ŷ ≤ t) − D1(Y ≤ t|Ŷ ≤ t)| (shown in Fig. 3, the orange region) is difficult to estimate due to the integration. To address this, we sample multiple values {t1, . . . , tm} and compute its average difference as the approximation of the integration. ∆SufR ≈ 1 m ∑m i=1 |D0(Y ≤ ti|Ŷ ≤ ti)−D1(Y ≤ ti|Ŷ ≤ ti)|
  Method Accuracy (↑) ∆SufC (↓) ERM (I) 0.768 ± 0.004 0.173 ± 0.008
  Adv debias (II) 0.760 ± 0.008 0.291 ± 0.006 Mixup (III) 0.758 ± 0.003 0.343 ± 0.022
  IRM v1 (IV) 0.753 ± 0.004 0.057 ± 0.015 One step (V) 0.755 ± 0.007 0.048 ± 0.008
  Implicit 0.760 ± 0.007 0.051 ± 0.012
  Table 1: Toxic comments dataset. Accuracy and ∆SufC in different approaches. 0.05 0.08 0.11 0.14 0.17 Suf_C (Sufficiency Gap)
  0.75
  0.76
  0.77
  Ac cu
  ra cy
  Implicit One_step IRM_v1 ERM
  Figure 4: Toxic. Accuracy-Fair Trade-off
  Concretely, for a given ti in each group, we compute the percentile (Ŷ0) at point t: D0(Ŷ0 ≤ ti), then we compute the corresponding ground truth cumulative distribution (Y ) at the same point ti: D(Y ≤ ti|Ŷ ≤ ti). Through the aforementioned approximation, we can compute |D0(Y ≤ ti|Ŷ ≤ ti)−D1(Y ≤ ti|Ŷ ≤ ti)|.
  Baselines We consider the baselines that add fairness constraints during the training process. Specifically, we compare our method with (I) empirical risk minimization (ERM) that trains the model without considering fairness; (II) adversarial debiasing (Zhang et al., 2018); (III) fair mix-up (Chuang & Mroueh, 2021), a recent data-augmentation and effective approach in the fair representation learning. In fact, the baselines (II) and (III) are DP-based fair approaches, which is designed to demonstrate the general non-compatibility in addressing the sufficiency based fairness.
  Besides, we include two additional baselines that have the similar objective but different algorithmic realizations. (IV) the original IRM regularization (referred as IRM v1) (Arjovsky et al., 2019), which adds a gradient penalty to encourage the invariance. (V) One-step explicit alignment. In the inner-level optimization, we suppose to conduct the one-step gradient descent for each sub-group. Then in the outer-level optimization, we add a gradient-incoherence constraint to encourage the identical (one-step) optimization path: minλ ‖∇h0L0(h0, λ) − ∇h1L1(h1, λ)‖22. All the results are reported by averaging five repetitions and additional experimental details are delegated in the Appendix.
sections.heading: 6.2 EMPIRICAL RESULTS
sections.heading: 6.2.1 TOXIC COMMENTS
sections.text: The toxic comments dataset (Jigsaw, 2018) is a binary classification task in NLP to predict whether comment is toxic or not. The original label is actually not binary since the comments is decided by multiple annotators, where the labelling discrepancy generally occurs. To this end, we conduct a simple strategy to decide comment is toxic if at least one annotator marks it. In this dataset, a portion of comments have been labeled with identity attributes, including gender and race. It has also been revealed that the race identity (e.g., black) is correlated with the toxicity label, which can lead to the predictive discrimination. Thus we adopted the race as the protected group by selecting two subgroups of Black and Asian. For the sake of computational simplicity, we first applied the pretrained BERT (Devlin et al., 2018) to extract the word embedding with 748 dimensional vector. Then we adopt representation function λ as two fully-connected layers with hidden dimension 200 with Relu activation and classifier h as a linear predictor. We report the test-set sub-group average accuracy and sufficiency gap (∆SufC) in Tab. 1 and Fig. 4.
  The results reveal several interesting facts. (1) The Demographic Parity (DP) based fair constraints are generally non-compatible with the sufficiency rule. Specifically, baseline (II,III) even increase ∆SufC with higher value than ERM. (2) For the baselines that track the sufficiency rule (IV,V), the sufficiency gap ∆SufC is improved with a similar accuracy, shown in Tab.1. We also change the regularization coefficient in (IV,V) and κ in the implicit approach. We observe that the implicit approach demonstrates a consistent better Accuracy-Fair trade-off, shown in Fig. 4.
  Method Accuracy (↑) ∆SufC (↓) ERM (I) 0.780 ± 0.015 0.210 ± 0.022
  Adv debias (II) 0.785 ± 0.022 0.165 ± 0.028 Mixup (III) 0.792 ± 0.011 0.160 ± 0.010
  IRM v1 (IV) 0.795 ± 0.012 0.086 ± 0.015 One step (V) 0.797 ± 0.006 0.086 ± 0.012
  Implicit 0.794 ± 0.027 0.074 ± 0.020
  Table 2: CelebA dataset. Accuracy and predictive parity in different approaches. 0.05 0.10 0.15 0.20 Suf_C (Sufficiency Gap)
  0.76
  0.77
  0.78
  0.79
  Ac cu
  ra cy
  Implicit One_step IRM_v1 ERM
  Figure 5: CelebA. Accuracy-Fair Trade-off
sections.heading: 6.2.2 CELEBA DATASET
sections.text: The CelebA dataset (Liu et al., 2015) contains around 200K images of celebrity faces, where each image is associated with 40 human-annotated binary attributes including gender, hair color, young, etc. In this paper, we designate gender as the sensitive attribute, and attractive as the binary classification task. We randomly select around 82K and 18K images as the training and validation set. Then we adopt representation function λ as pre-trained ResNet-18 (He et al., 2016) and classifier h as two-fully connected layers. We report the test-set sub-group average accuracy and sufficiency gap (∆SufC) in Tab. 2 and Fig. 5.
  The results in the CelebA show similar behaviors with the Toxic comments. Specifically, the DP based fair approaches (II, III) did not effectively improve ∆SufC , shown in Tab. 2. In contrast, the sufficiency can be significantly improved in baselines (IV, V) and implicit approach without largely losing the accuracy. Specifically, Fig. 5 visualizes the accuracy-fair trade-off curve, where the later three approaches show quite similar behaviors.
sections.heading: 6.2.3 LAW DATASET
sections.text: The Law Dataset is a regression task to predict a students GPA (real value, ranging from [0, 4]), where the data is utilized from the School Admissions Councils National Longitudinal Bar Passage Study (Wightman, 1998) with 20K examples. In the regression task, we adopt the square loss and race as the protected attribute (white versus non-white). We adopt λ as the one fully connected layer with hidden dimension 100 and Relu activation and predictor h as a linear predictor. We report the test-set subgroup average MSE (Mean Square Error) and sufficiency gap (∆SufR) in Tab. 1 and Fig. 4.
  Compared to the classification task, the results show similar behaviors in the regression. Specifically, the DP based fair approaches (II, III) still increase ∆SufR in the regression. In contrast, the gap is significantly improved in our proposed approach and baseline (IV,V). Specifically, Fig. 7 visualizes the sufficiency-gap of different approaches, where the implicit approach significantly mitigate the sufficiency gap. Besides, Fig. 6 shows the MSE-sufficiency gap curve, which still reveals the implicit approach benefits a better trade-off between the performance and fairness.
  Method MSE (↓) ∆SufR (↓) ERM (I) 0.190 ± 0.005 0.160 ± 0.007
  Adv debias (II) 0.223 ± 0.008 0.188 ± 0.012 Mixup (III) 0.216 ± 0.012 0.172 ± 0.007
  IRM v1 (IV) 0.208 ± 0.006 0.096 ± 0.006 One step (V) 0.204 ± 0.007 0.125 ± 0.010
  Implicit 0.198 ± 0.005 0.091 ± 0.011
  Table 3: Law dataset. MSE and sufficiency gap in different approaches. 0.04 0.06 0.08 0.10 0.12 0.14 0.16 Suf_R (Sufficiency Gap)
  0.19
  0.20
  0.21
  0.22
  0.23
  0.24
  M SE
  Implicit One_step IRM_v1 ERM
  Figure 6: Law. MSE-Fair Trade-off
  Method MSE (↓) ∆SufR (↓) ERM (I) 1.939 ± 0.021 0.246 ± 0.019
  Adv debias (II) 1.982 ± 0.016 0.252 ± 0.020 Mixup (III) 1.979 ± 0.025 0.246 ± 0.023
  IRM v1 (IV) 1.927 ± 0.031 0.077 ± 0.009 One step (V) 1.904 ± 0.027 0.090 ± 0.019
  Implicit 1.906 ± 0.019 0.051 ± 0.005
  Table 4: NLSY dataset. MSE and sufficiency gap in different approaches. 0.05 0.10 0.15 0.20 0.25 Suf_R (Sufficiency Gap)
  1.8
  1.9
  2.0
  2.1
  2.2
  2.3
  2.4
  M SE
  Implicit One_step IRM_v1 ERM
  Figure 8: NLSY. MSE-Fair Trade-off
sections.heading: 6.2.4 NLSY DATASET
sections.text: The National Longitudinal Survey of Youth (NLSY, 2021) dataset is a regression task with around 7K dataset, which involves the survey results of the U.S. Bureau of Labor Statistics. It is intended to gather information on the labor market activities and other life events of several groups for predicting the income y of each person. We treat the gender as the sensitive attribute. We also normalize the output y by diving the 10, 000, then the final output y ranges around [0, 8]. The prediction loss is also the square loss. We adopt representation λ as the two fully connected layers with hidden dimension 200 and Relu activation and predictor h as a linear predictor. We report the test-set sub-group average MSE (Mean Square Error) and Sufficiency Gap (∆SufR) in Tab. 4 and Fig. 8.
  Tab. 4 provides similar trends with other datasets. Baselines (IV,V) and implicit approach effective control the sufficiency gap, while the DP based approach generally fails to improve the gap. Fig. 8 reveals a slightly better approximation-fair trade off for the implicit approach. Finally, Fig. 11 (in Appendix) visualizes the sufficiency gap of different algorithms. The gap is actually significantly improved while the calibration gap still exists, which is consistent with (Liu et al., 2019). Therefore it can be quite interesting and promising to analyze the triple trade-off between the sufficiency gap, calibration gap and prediction performance in the regression.
sections.heading: 7 CONCLUSION
sections.text: We considered the fair representation learning from a novel perspective through encouraging the invariant optimal predictors on the top of data representation. Then we formulated this problem as a bi-level optimization and proposed an implicit alignment algorithm. We further demonstrated the bilevel objective is to fulfil the sufficiency rule. Besides, we also analyzed the error gap of the implicit algorithm. The empirical results in both classification and regression settings suggest the improved fairness measurement. Finally, we think the future work can include developing computationally efficient explicit algorithms for avoiding the biased gradient computation.
sections.heading: ETHICS STATEMENT
sections.text: This paper proposed a novel fair representation algorithm, which aims to address the potential prediction discrimination towards several subgroups. The proposed approach may also introduce the potential negative impact: we merely address the fairness with respect to the sufficiency rule in the paper, which is not always the preferable criteria in several specific scenarios.
sections.heading: REPRODUCIBILITY STATEMENT
sections.text: We provided a demo source code in the supplementary material for a better understanding the proposed algorithm. Besides, the detailed experimental descriptions and theoretical proofs are also provided in the appendix.
sections.heading: A PROPOSITION 1
sections.text: We consider the regression and classification separately.
  Regression According to the definition, given a fixed and deterministic representation λ, we have L0(h, λ) = ED0(h(z)− y)2
  It is noted as a typical regression problem with square error. We set the derivative as zero: ∇hL0(h, λ) = 0, we have h?0(z) = ED0 [Y |Z = z]. As for D1, we apply the same strategy with h?1(z) = ED1 [Y |Z = z]. Based on the invariant optimal predictor, we have ED0 [Y |Z = z] = ED1 [Y |Z = z] with z = λ(x).
  Classification According to the definition, we have: L0(h, λ) = ED0 log(1 + exp(−yh(z))) Since the optimal predictor on the logistic loss is the log-conditional density ratio: h?0(z) = log ( D0(Y=1|Z=z) D0(Y=−1|Z=z) ) . Observe that in the binary classification with Y = {−1, 1}, we have D0(Y = 1|Z = z) = 12 (1 + ED0 [Y |Z = z]) and D0(Y = −1|Z = z) = 1 2 (1 − ED0 [Y |Z = z]), then we have:
  h?0(z) = log ( 1 + ED0 [Y |Z = z] 1− ED0 [Y |Z = z] ) As for D1, we adopt the same strategy and we have log ( 1+ED0 [Y |Z=z] 1−ED0 [Y |Z=z] ) = log ( 1+ED1 [Y |Z=z] 1−ED1 [Y |Z=z] ) , then we have ED0 [Y |Z = z] = ED1 [Y |Z = z]. As for the predictive parity, since we have ED0 [Y |Z = z] = ED1 [Y |Z = z] and h? = h?1 = h?2, then we have ED0 [Y |h?(z)] = ED1 [Y |h?(z)].
sections.heading: B APPROXIMATION ERROR
sections.text: Theorem 2 (Approximation Error Gap). Suppose that (1) Smooth Predictive Loss. The first-order derivatives and second-order derivatives of L are Lipschitz continuous; (2) Non-singular Hessian matrix. We assume∇h0,h0L0(h0, λ),∇h1,h1L1(h1, λ), the Hessian matrix of the inner optimization problem, are invertible. (3) Bounded representation and predictor function. We assume the λ and h are bounded, i.e., ‖λ‖, ‖h‖ are upper bounded by the predefined positive constants. Then the approximation error between the ground truth and algorithmic estimated gradient w.r.t. the representation is be upper bounded by:
  ‖grad(λ)− ˜gradδ(λ)‖ = O(κ + + δ).
  Proof. We denote grad(λ) as the ground truth gradient w.r.t. λ in outer-level loss (given the optimal predictor h?0, h ? 1). Then we aim to bound
  ‖grad(λ)− ˜gradδ(λ)‖ We first introduce the following terms for facilitating the proof:
  A 0 = ∇h0∇λL0(h 0, λ), A 1 = ∇λ∇h1L1(h 1, λ), A?0 = ∇λ∇h0L0(h?0, λ), A?1 = ∇λ∇h1L1(h?1, λ), B 0 = ∇λL0(h 0, λ), B 1 = ∇λL1(h 1, λ), B?0 = ∇λL0(h?0, λ), B?1 = ∇λL1(h?1, λ),
  p?0 = ( ∇2h0L0(h ? 0, λ) )−1 (∇h0L0(h?0, λ) + κ(h?0 − h?1)) ,
  p?1 = ( ∇2h1L1(h ? 1, λ) )−1 (∇h1L1(h?1, λ)− κ(h?0 − h?1)) .
  Then the approximation error gap can be expressed as: ‖grad(λ)− ˜gradδ(λ)‖ = ‖ (B?0 −A?0p?0 +B?1 −A?1p?1)− ( B 0 −A 0pδ0 +B 1 −A 1pδ1 ) ‖
  ≤ 1∑ i=0 ‖B?i −B i ‖+ 1∑ i=0 ‖A?ip?i −Aδipδi ‖
  Due to the symmetric of D0 and D1, we only focus on the term on i = 0, the the upper bound in i = 1 can be derived analogously.
  As for bounding ‖B?0 −B 0‖, since we assume first order derivative of the loss is Lipschitz functions (with constant L1), then we have :
  ‖B?0 −B 0‖ ≤ L1‖h?0 − h 0‖ ≤ L1
  Then the second term can be upper bounded by three terms:
  ‖A?0p?0 −Aδ0pδ0‖ ≤ ‖A?0p?0 −A?0p0‖︸ ︷︷ ︸ (1) + ‖A?0p0 −A 0p0‖︸ ︷︷ ︸ (2) + ‖A 0p0 −A 0pδ0‖︸ ︷︷ ︸ (3)
  Before estimating the upper bound, we first demonstrate ‖A 0‖ and ‖A?0‖ are also bounded. Since we assume λ and h are bounded (assuming the bounded constant as η and φ), the second order derivative are Lipschitz (with constant L2). Then we consider another fixed point (λ′, h?0(λ
  ′)) with bounded second order derivative: A0 = ∇2h0,λL0(h ? 0(λ ′), λ′) and ‖A0‖ ≤ A. We have:
  ‖A?0 −A0‖2 ≤ L2‖[h?0(λ), λ]− [h?0(λ′), λ′]‖2 ≤ L2 √ η2 + φ2
  Thus we have ‖A?0‖ ≤ A + L2 √ η2 + φ2 = A?sup. As for the second derivative at point h 0, it can be upper bounded analogously with a similar constant A sup.
  The upper bound of term (1) We have:
  ‖A?0p?0 −A?0p0‖ ≤ ‖A?0‖‖p?0 − p0‖
  We have proved ‖A?0‖ is upper bounded by A?sup. We additionally introduce the following auxiliary terms:
  P ?0 = ( ∇2h0L0(h ? 0, λ) )−1 , P 0 = ( ∇2h1L1(h ? 1, λ) )−1 . b?0 = ∇h0L0(h?0, λ) + κ(h?0 − h?1), b 0 = ∇h0L0(h 0, λ) + κ(h 0 − h 1)
  Then we have:
  ‖p?0 − p0‖ = ‖P ?0 b?0 − P 0b 0‖ ≤ ‖P ?0 b?0 − P ?0 b 0‖+ ‖P ?0 b 0 − P 0b 0‖ ≤ ‖P ?0 ‖‖b?0 − b 0‖+ ‖b 0‖‖P ?0 − P 0‖
  As for the ‖P ?0 ‖, since we assume the Hessian matrix is invertible thus its norm is upper bounded by some constant (denoted as A−1). As for ‖b?0 − b 0‖, we have:
  ‖b?0 − b 0‖ ≤ ‖∇h0L0(h?0, λ)−∇h0L0(h 0, λ)‖+ 2κ ≤ L1 + 2κ
  Thus we have ‖P ?0 ‖‖b?0 − b 0‖ ≤ A−1( L1 + 2κ ). As for ‖b 0‖, we can easily verify that it is indeed bounded by some constant b. For the first term, we can adopt the same strategy in proving bounded ‖A?0‖. As for the second term in b 0, it is upper bounded by 2κφ, due to the bounded predictor.
  We now demonstrate ‖P ?0 − P 0‖. Denoting ∆ = (P ?0 )−1 − (P 0 )−1, then according to the second order Lipschitz assumption, we have: ‖∆‖ ≤ L2. Plugging in the result, we have:
  ‖P ?0 − P 0‖ = ‖(P ?0 )∆(P 0 )‖ ≤ ‖P ?0 ‖‖∆‖‖P 0‖ ≤ (A−1)2L2
  We still adopt the assumption that the bounded Hessian-inverse matrix by A−1.
  Plugging in all the results, we have:
  (1) ≤ A1( L1 + 2κ ) + b(A1)2L2 := O(κ + )
  The upper bound of term (2) We have:
  ‖A?0p0 −A 0p0‖ ≤ ‖p0‖2‖A?0 −A 0‖
  Since we assume the loss is second-order Lipschitz, thus we have
  ‖A?0 −A 0‖ = ‖∇λ∇h0L0(h?0, λ)−∇λ∇h0L0(h 0, λ)‖ ≤ L2‖h?0 − h 0‖ ≤ L2 We can also demonstrate ‖p0‖ is bounded. According to the definition we have:
  ‖p0‖ ≤ ‖ ( ∇2h0L0(h 0, λ) )−1 ‖‖ (∇h0L0(h 0, λ) + κ(h 0 − h 1)) ‖ (i)
  ≤ A−1(L1‖h?0 − h 0‖2 + 2κφ) (ii)
  ≤ A−1( L1 + 2κφ)
  For (i), we assume: 1) the Hessian matrix is invertible thus its norm is surely upper bounded by some constant (denoted as A−1), 2) the first-order derivative is Lipschitz (bounded by L1), 3) the predictor h is bounded. For (ii), we adopt the definition of h 0.
  Therefore, the upper bound for Term (2) is formulated as:
  (2) ≤ L2A−1( L1 + 2κφ) := O(κ )
  The upper bound of term (3) We have:
  ‖A 0p0 −A 0pδ0‖ ≤ ‖A 0‖‖p0 − pδ0‖ ≤ δA sup = O(δ)
  Through the upper bound in (1)-(3), we finally have the error between the estimated and ground-truth gradient:
  ‖grad(λ)− ˜gradδ(λ)‖ = O(κ + + δ)
sections.heading: C THE CONVERGENCE BEHAVIOR
sections.text: For the sake of completeness, we provide the convergence analysis of the proposed algorithm. Proposition 2. We execute the implicit alignment algorithm (Algo. 1), obtaining a sequence of λ1, . . . , λk, . . . . Supposing the fair constraint κ is fixed. The optimization tolerances are summable:∑ k 2 k ≤ +∞ and ∑ k δ 2 k ≤ +∞, then λk is proved to be converged with
  lim k→∞
  λk = λ ?.
  If the stationary point λ? is also within the bounded norm, then we have:
  grad(λ?) = 0.
  Proof. We denote the entire outer-level loss w.r.t. λ as L(λ), by the assumption the β-smooth loss L. Then at iteration k + 1 and k, we have:
  L(λk+1) ≤ L(λk)− grad(λk)T (λk − λk+1) + β
  2 ‖λk+1 − λk‖2 = L(λk)− ( grad(λk)− ˜grad δ (λk) + ˜grad δ (λk) )T (λk − λk+1) + β
  2 ‖λk+1 − λk‖2 = L(λk)− ( grad(λk)− ˜grad δ (λk) )T (λk − λk+1)− ˜grad δ (λk)(λk − λk+1) + β
  2 ‖λk+1 − λk‖2
  Since we assume the representation is within the bounded norm, the projection onto the convex set are non-expansive operators (Boyd et al., 2004). Then for any point p, q, we have ‖proj(p) − proj(q)‖2 ≤ (p− q)T (proj(p)− proj(q)). Then we set λk and λk+1 = λk − 1β ˜grad δ (λk), we have:
  ‖λk − λk+1‖2 ≤ 1
  β ( ˜grad
  δ (λk)) T (λk − λk+1)
  Plugging into the results, we have: L(λk+1) ≤ L(λk)− ( grad(λk)− ˜grad δ (λk) )T (λk − λk+1)− β
  2 ‖λk+1 − λk‖2
  ≤ L(λk) + ‖grad(λk)− ˜grad δ (λk)‖‖λk − λk+1‖ −
  β 2 ‖λk+1 − λk‖2
  Rearranging the inequality, we have: β
  2 ‖λk+1 − λk‖2 − ‖grad(λk)− ˜grad
  δ (λk)‖‖λk − λk+1‖+ (L(λk+1)− L(λk)) ≤ 0
  Then we have:
  ‖λk+1 − λk‖ ≤ 1
  β
  ( ‖grad(λk)− ˜grad δ (λk)‖+ √ ‖grad(λk)− ˜grad δ (λk)‖2 − 2β (L(λk+1)− L(λk)) ) By denoting Bk = ‖grad(λk)− ˜grad δ (λk)‖ and Ck = L(λk+1)− L(λk). Then we have:
  ‖λk+1 − λk‖2 ≤ 1
  β2
  ( B2k +B 2 k − 2βCk + 2Bk √ B2k − 2βCk ) ≤ 1 β2 ( B2k +B 2 k − 2βCk +B2k +B2k − 2βCk
  ) = 4
  β2 [‖grad(λk)− ˜grad
  δ (λk)‖22 − 2β (L(λk+1)− L(λk))]
  Taking sum over k, we have: +∞∑ k=1 ‖λk+1 − λk‖2 ≤ 4 β2 +∞∑ k=1 ‖grad(λk)− ˜grad δ (λk)‖22 − 8 β ( lim k→∞ L(λk+1)− L(λ1))
  ≤ 4 β2 ∑ k [(C + κ)2 2k + δ 2 k]− 8 β ( lim k→∞ L(λk+1)− L(λ1) ) < +∞
  Since 1) the first term on the right side is finite, because the optimization tolerance is summable; 2) the second term is also finite, because the loss is assumed to be bounded. Then the upper bound is finite. In order to satisfy this condition, on the left side we should have:
  lim k→∞
  λk+1 − λk = 0
  By adopting the definition λk+1 = Proj(λk − ˜grad δ (λk)) and limk→∞ ˜grad δ (λk) = grad(λk) (Based on theorem 1, the limit of the optimization tolerance is zero), then we have: λ? = proj(λ? − grad(λ?))
  Where λ? = limk→+∞ λk+1 = limk→+∞ λk. Since the projection is on the bounded norm Lnorm and λ? is within the bounded norm space, thus if λ? − grad(λ?) is within the bounded norm space, we have: grad(λ?) = 0 Else if λ? − grad(λ?) is outside the bounded norm space, then according to the definition, the projection of λ?−grad(λ?) is surely on the boundary of the Lnorm space, with ‖proj(λ?−grad(λ?))‖ = Lnorm. However, we have assumed the λ? is within the bounded norm space with ‖λ?‖ < Lnorm, which leads to the contradiction. Based on these discussions, we finally have:
  grad(λ?) = 0
sections.heading: D ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS
sections.heading: D.1 ADDITIONAL DETAILS
sections.text: Toxic Comments We split the training, validation and testing set as 70%, 10% and 20%. We adopt Adam optimizer with learning rate 10−3 and eps 10−3. The batch-size is set as 500 for each subgroup and we use sampling with replacement to run the explicit algorithm with maximum epoch 100. The fair coefficient is generally set as κ = 0.1 ∼ 0.001. As for the inner-optimization step, the iteration number is 20 and the iteration in running conjugate gradient approach is 10.
  CelebA The training/validation/test set are around 82K, 18K and 18K. We also adopt the Adam optimizer with learning rate on λ : 10−5 ∼ 10−4 and h : 10−3. The batch-size is set as 64 for each subgroup and we iterate the whole dataset as one epoch. The maximum running epoch is set as 20 and the iteration in running conjugate gradient approach is 10.
  Law We split the training, validation and testing set as 70%, 10% and 20%. Then we adopt Adam optimizer with learning rate 10−3 and eps 10−3. The batch-size is set as 500 for each subgroup and we use sampling with replacement to run the implicit algorithm, with the maximum epoch 100. We adopt the MSE loss in the regression. The fair coefficient is generally set as κ = 0.1 ∼ 10−4. As for the inner-optimization, the iteration number is 20 and the iteration in running conjugate gradient is 10. In computing the sufficiency gap in the regression, we sample 33 points to compute the gap.
  NLSY We split the training, validation and testing set as 70%, 10% and 20%. Then we adopt Adam optimizer with learning rate 10−3 and eps 10−3. The batch-size is set as 500 for each subgroup and we use sampling with replacement to run the implicit algorithm, with maximum epoch 100. We adopt the MSE loss in the regression. The fair coefficient is generally set as κ = 0.1 ∼ 10−4. As for the inner-optimization, the iteration number is 20 and the iteration in running conjugate gradient is 10. In computing the sufficiency gap, we sample 33 points to compute the sufficiency gap.
sections.heading: D.2 ADDITIONAL EMPIRICAL RESULTS
sections.text: Computational complexity To show the efficiency of the implicit approach, we empirically compare the computational complexity of the T -step explicit alignment and implicit approach (for different iterations of conjugate gradient solver.) The experimental results verified the efficiency of the implicit approach, where a significant large inner-optimization step does not considerably increase the computational time.
  Gradient evolution We also visualize the gradient norm of the representation λ in the Toxic dataset, shown in Fig. 10. The results verify the convergence behavior and the gradient norm finally tends to zero.
sections.heading: D.3 DISCUSSION WITH NON-DEEP LEARNING BASELINES
sections.text: In order to show the effectiveness of the proposed approach, we additionally compare the FAHT (Zhang & Ntoutsi, 2019), a decision tree based fair classification approach. We evaluated the empirical performance on Toxic comments dataset.
  the norm of ˜grad δ (λ) at each training epoch, which suggests a convergence behavior and the gradient finally tends to zero.
  The implicit approach demonstrates the considerable better results, which may come from two aspects: (1) the Toxic task is a high-dimensional classification problem (x ∈ R748), where the deep learning based approach is more effective in handling the high-dim dataset. (2) The FAHT aims to realize the statistical parity (the independence rule), which is not compatible with the sufficiency. According to the analysis of (Barocas et al., 2019), when the sensitive attribute (A) and label (Y) are not independent (This has been justified by computing their Pearson Correlation coefficient), the sufficiency and independence cannot both hold.
sections.heading: D.4 SUFFICIENCY GAP IN REGRESSION
sections.text: We visualize the sufficiency gap of NLSY dataset.
sections.heading: E COMPLEMENTARY TECHNICAL DETAILS
sections.text: We present complementary details that are related to the paper.
sections.heading: E.1 CONJUGATE GRADIENT METHOD
sections.text: We present the Conjugate Gradient (CG) algorithm in Algo. 2 through autograd. In the conventional CG algorithm with objective 12x
  TAX−bX , we need to estimateAX and compute its residual and update X . Since in our problem setting, the A = ∇2h0L0(h 0, λ), then computing AX can be realized through Hessian-vector product through autograd, denoted as function F in the paper. i.e.,∇2h0L0(h 0, λ)X = F (x).
  Below we provided a simple PyTorch code for realizing the Hessian Vector product.
  1 import torch 2 def hessain_vector_product(loss,model,vector): 3 # loss: the defined loss 4 # model: the model in computing the Hessian 5 # vector: the required vector in computing Hessian-vector product
  Algorithm 2 Conjugate Gradient Method Ensure: Function F that computes Hessian-vector product through autograd, initial value X0,
  bias vector B. 1: Computing Residual: r0 = B − F (X0) 2: Set p0 = r0 3: for inner iterations k do 4: Computing αk ← r T k rk
  pTk F (pk)
  5: Xk+1 ← Xk + αkpk 6: rk+1 ← rk − αkF (pk) 7: If rk+1 is sufficiency small, then stop. 8: βk ← rTk+1rk+1
  rTk rk
  9: pk+1 ← rk+1 + βkpk 10: end for 11: return Xk+1
  6 partial_grad = torch.autograd.grad(loss, model_parameters(), create_graph=True) 7 flat_grad = torch.cat([g.contiguous().view(-1) for g in partial_grad ]) 8 h = torch.sum(flat_grad * vector_to_optimize) 9 hvp = torch.autograd.grad(h, model.parameters())
  10 return hvp
  Listing 1: Simple demo in computing Hessian vector product
sections.heading: E.2 CALIBRATION GAP IN THE REGRESSION
sections.text: Based on Kuleshov et al. (2018), we first compute the predicted cumulative distribution (Ŷ0) of at point t: D0(Ŷ0 ≤ t) = α, then we compute the corresponding ground truth cumulative distribution (Y0) at point t. By changing t, we obtain several points on function D0(Y ≤ t|Ŷ0 ≤ t) = β. Then the regression is probabilistic calibrated when α ≡ β. From this perspective, the zero calibration gap can guarantee a zero sufficiency gap. But the inverse is not necessarily true, as our experimental results suggest, a small sufficiency gap can lead to either small or large calibration gap. Thus it can be quite promising to explore their inherent relations and trade-off in the fair regression.