Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem

Abstract:
In this paper, we study the problem of fair sparse regression on a biased dataset where bias depends upon a hidden binary attribute. The presence of a hidden attribute adds an extra layer of complexity to the problem by combining sparse regression and clustering with unknown binary labels. The corresponding optimization problem is combinatorial, but we propose a novel relaxation of it as an invex optimization problem. To the best of our knowledge, this is the first invex relaxation for a combinatorial problem. We show that the inclusion of the debiasing/fairness constraint in our model has no adverse effect on the performance. Rather, it enables the recovery of the hidden attribute. The support of our recovered regression parameter vector matches exactly with the true parameter vector. Moreover, we simultaneously solve the clustering problem by recovering the exact value of the hidden attribute for each sample. Our method uses carefully constructed primal dual witnesses to provide theoretical guarantees for the combinatorial problem. To that end, we show that the sample complexity of our method is logarithmic in terms of the dimension of the regression parameter vector.

heading: 1 Introduction
text: In modern times, machine learning algorithms are used in a wide variety of applications, many of which are decision making processes such as hiring (Hoffman et al., 2018), predicting human behavior (Subrahmanian & Kumar, 2017), COMPAS (Correctional Offender Management Profiling for Alternative Sanctions) risk assessment (Brennan et al., 2009), among others. These decisions have large impacts on society (Kleinberg et al., 2018). Consequently, researchers have shown interest in developing methods that can mitigate unfair decisions and avoid bias amplification. Several fair algorithms have been proposed for machine learning problems such as regression (Agarwal, 2019; Berk, 2017; Calders, 2013), classification (Agarwal et al., 2018; Donini et al., 2018; Dwork et al., 2012; Feldman et al., 2015; Hardt et al., 2016; Huang & Vishnoi, 2019; Pedreshi et al., 2008; Zafar et al., 2019; Zemel et al., 2013) and clustering (Backurs et al., 2019; Bera et al., 2019; Chen et al., 2019; Chierichetti et al., 2017; Huang et al., 2019). A common thread in the above literature is that performance is only viewed in terms of risks, e.g., misclassification rate, false positive rate, false negative rate, mean squared error.
In the literature, fairness is discussed in the context of discrimination based on membership to a particular group (e.g. race, religion, gender) which is considered a sensitive attribute. Fairness is generally modeled explicitly by adding a fairness constraint or implicitly by incorporating it in the model itself. There have been several notions of fairness studied in linear regression. Berk (2017) proposed notions of individual fairness and group fairness, and modeled them as penalty functions. Calders (2013) proposed the fairness notions of equal means and balanced residuals by modeling them as explicit constraints. Agarwal (2019), Fitzsimons (2019) and Chzhen et al. (2020) studied
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
demographic parity. While Agarwal (2019), Fitzsimons (2019) modeled it as an explicit constraint, Chzhen et al. (2020) included it implicitly in their proposed model.
All the above work assume access to the sensitive attribute in the training samples and provide a framework which are inherently fair. Our work fundamentally differs from these work as we do not assume access to the sensitive attribute. Without knowing the sensitive attribute, it becomes difficult to ascertain bias, even for linear regression. In this work, we focus on identifying unfairly treated members/samples. This adds an extra layer of complexity to linear regression. We solve the linear regression problem while simultaneously solving a clustering problem where we identify two clusters – one which is positively biased and the other which is negatively biased. Table 1 shows a consolidated comparison of our work with the existing literature.
Once one identifies bias (positive or negative) for each sample, one could perform debiasing which would lead to the fairness notion of equal means (Calders, 2013) among the two groups (See Figure 1). It should be noted that identifying groups with positive or negative bias may not be same as identifying the sensitive attribute. The reason is that there may be multiple attributes that are highly correlated with the sensitive attribute. In such a situation, these correlated attributes can facilitate indirect discrimination even if the sensitive attribute is identified and removed. This is called the red-lining effect (Calders, 2010). Our model avoids this by directly identifying biased groups.
While the standard algorithms solving the sparse/LASSO problem in this setting do provide an estimate of the regression parameter vector, they do not fit the model accurately as they fail to consider any fairness criteria in their formulations. It is natural then to think about including the hidden attribute in LASSO itself. However, this breaks the convexity of the loss function which makes the problem intractable by the standard LASSO algorithms. The resulting problem is a combinatorial version of sparse linear regression with added clustering according to the hidden attribute. In this work, we propose a novel technique to tackle the combinatorial LASSO problem with a hidden attribute and provide theoretical guarantees about the quality of the solution given a sufficient number of samples. Our method provably detects unfairness in the system. It should be noted that observing unfairness does not always imply that the designer of the system intended for such inequalities to arise. In such cases, our method acts as a check to detect and remove such unintended discrimination. While the current belief is that there is a trade-off between fairness and performance (Corbett-Davies et al., 2017; Kleinberg et al., 2017; Pleiss et al., 2017; Zliobaite, 2015; Zhao & Gordon, 2019), our
theoretical and experimental results show evidence on the contrary. Our theoretical results allow for a new understanding of fairness, as an “enabler” instead of as a “constraint”.
Contribution. Broadly, we can categorize our contribution in the following points:
• Defining the problem: We formulate a novel combinatorial version of sparse linear regression which takes fairness/bias into the consideration. The addition of clustering comes at no extra cost in terms of the performance. • Invex relaxation: Most of the current methods solve convex optimization problems as it makes the solution tractable. We propose a novel relaxation of the combinatorial problem and formally show that it is invex. To the best of our knowledge, this is the first invex relaxation for a combinatorial problem. • Theoretical Guarantees: Our method can detect bias in the system. In particular, our method recovers the exact hidden attributes for each sample and thus provides an exact measure of bias between two different groups. Our method solves linear regression and clustering simultaneously with theoretical guarantees. To that end, we recover the true clusters (hidden attributes) and a regression parameter vector which is correct up to the sign of entries with respect to the true parameter vector. On a more technical side, we provide a primal-dual witness construction for our invex problem and provide theoretical guarantees for recovery. The sample complexity of our method varies logarithmically with respect to dimension of the regression parameter vector.

heading: 2 Notation and Problem Definition
text: In this section, we collect all the notations used throughout the paper. We also formally introduce our novel problem. We consider a problem where we have a binary hidden attribute, and where fairness depends upon the hidden attribute. Let y P R be the response variable and X P Rd be the observed attributes. Let z˚ P t´1, 1u be the hidden attribute and γ P Rą0 be the amount of bias due to the hidden attribute. The response y is generated using the following mechanism:
y “ X⊺w˚ ` γz˚ ` e (1)
where e is an independent noise term. For example, y could represent the market salary of a new candidate, X could represent the candidate’s skills and z could represent the population group the candidate belongs to (e.g., majority or minority). While the group of the candidate is not public knowledge, a bias associated with the candidate’s group may be present in the underlying data. For our problem, we will assume that an estimate of the bias γ P Rą0 is available. In practice, even a rough estimate (˘25%) of γ also works well (See Appendix J). Let rds denote the set t1, 2, ¨ ¨ ¨ , du. We assume X P Rd to be a zero mean sub-Gaussian random vector (Hsu et al., 2012) with covariance Σ P Sd`, i.e., there exists a ρ ą 0, such that for all α P Rd the following holds: Epexppα⊺Xqq ď expp }α} 2 2ρ 2
2 q. By simply taking αi “ r and αk “ 0,@k ‰ i, it follows that each entry of X is sub-Gaussian with parameter ρ. In particular, we will assume that @i P rds , Xi?
Σii is a sub-Gaussian random variable with parameter σ ą 0. It follows trivially that
maxiPrds ? Σiiσ ď ρ. We will further assume that e is zero mean independent sub-Gaussian noise with variance σe. We assume that as the number of samples increases, the noise in the model gently decreases. We model this by taking σe “ k?logn for some k ą 0. Our setting works with a variety of random variables as the class of sub-Gaussian random variable includes for instance Gaussian variables, any bounded random variable (e.g., Bernoulli, multinomial, uniform), any random variable with strictly log-concave density, and any finite mixture of sub-Gaussian variables. Notice that for the group with z “ `1, Epyq “ γ and for the group with z “ ´1, Epyq “ ´γ. This means that after correctly identifying groups, one could perform debiasing by subtracting or adding γ for z “ `1 and ´1 respectively. After debiasing, the expected value of both groups would match (and be equal to 0). This complies with the notion of equal mean fairness proposed by Calders (2013).
The parameter vector w˚ P Rd is s-sparse, i.e., at most s entries of w˚ are non-zero. We receive n i.i.d. samples of X P Rd and y P R and collect them in X P Rnˆd and y P Rn respectively. Thus, in the finite-sample setting,
y “ Xw˚ ` γz˚ ` e , (2)
where z˚ P t´1, 1un and e P Rn both collect n independent realizations of z˚ P t´1, 1u and e P R. Our goal is to recover w˚ and z˚ using the samples pX,yq. We denote a matrix A P Rpˆq restricted to the columns and rows in P Ď rps and Q Ď rqs respectively as APQ. Similarly, a vector v P Rp restricted to entries in P is denoted as vP . We use eigipAq to denote the i-th eigenvalue (1st being the smallest) of matrix A. Similarly, eigmaxpAq denotes the maximum eigenvalue of matrix A. We use diagpAq to denote a vector containing the diagonal element of matrix A. By overriding the same notation, we use diagpvq to denote a diagonal matrix with its diagonal being the entries in vector v. We denote the inner product between two matrices A and B by xA,By, i.e., xA,By “ tracepA⊺Bq, where trace denotes the trace of a matrix. The notation A ľ B denotes that A ´ B is a positive semidefinite matrix. Similarly, A ą B denotes that A ´ B is a positive definite matrix. For vectors, }v}p denotes the ℓp-vector norm of vector v P Rd, i.e., }v}p “ p řd i“1 |vi|pq 1 p . If p “ 8, then we define }v}8 “ maxdi“1 |vi|. For matrices, }A}p denotes the induced ℓp-matrix norm for matrix A P Rpˆq . In particular, }A}2 denotes the spectral norm of A and }A}8 fi maxiPrps řq j“1 |Aij |. A function fpxq is of order Ωpgpxqq and denoted by fpxq “ Ωpgpxqq, if there exists a constant C ą 0 such that for big enough x0, fpxq ě Cgpxq,@x ě x0. Similarly, a function fpxq is of order Opgpxqq and denoted by fpxq “ Opgpxqq, if there exists a constant C ą 0 such that for big enough x0, fpxq ď Cgpxq,@x ě x0. For brevity in our notations, we treat any quantity independent of d, s and n as constant. Detailed proofs for lemmas and theorems are available in the supplementary material.

heading: 3 Our New Optimization Problem and Invexity
text: In this section, we introduce our novel combinatorial problem and propose an invex relaxation. To the best of our knowledge, this is the first invex relaxation for a combinatorial problem. Without any information about the hidden attribute z˚ in Equation (2), the following LASSO formulation could be incorrectly and unsuccessfully used to estimate the parameter w˚. Definition 1 (Standard LASSO).
minw 1 n pXw ´ yq ⊺pXw ´ yq ` λn}w}1 (3)
However, without including z˚, standard LASSO does not provide accurate estimation of w˚ in Equation (2). We provide the following novel formulation of LASSO which fits our goals of estimating both w˚ and z˚: Definition 2 (Combinatorial Fair LASSO). minw,z 1 n pXw ` γz ´ yq
⊺pXw ` γz ´ yq ` λn}w}1, such that zi P t´1, 1u, @i P rns, (4) where λn ą 0 is the regularization level which depends on n.
In its current form, optimization problem (4) is a non-convex mixed integer quadratic program (MIQP). Solving MIQP is NP-hard (See Appendix B). Next, we will provide a continuous but still non-convex relaxation of (4). For ease of notation, we define the following quantities:
lpwq fi 1 n pXw ´ yq⊺pXw ´ yq, Z fi
„ 1 z⊺
z zz⊺
ȷ , Mpwq fi „
lpwq γn pXw ´ yq ⊺
γ n pXw ´ yq
γ2 n Inˆn
ȷ
,
(5) where I is an n ˆ n identity matrix. We provide the following invex relaxation to the optimization problem (4). Definition 3 (Invex Fair LASSO).
minw,Z xMpwq,Zy ` λn}w}1, such that diagpZq “ 1, Z ľ 0n`1ˆn`1 . (6)
Note that optimization problem (6) is continuous and convex with respect to w and Z separately but it is not jointly convex (See Appendix N for details). Specifically, for a fixed w, the matrix Mpwq becomes a constant and problem (6) resembles a semidefinite program. For a fixed Z, problem (6) resembles a standard LASSO. Unfortunately, problem (6) is not jointly convex on w and Z, and thus, it might still remain difficult to solve. Next, we will provide arguments that despite being non-convex, optimization problem (6) belongs to a particular class of non-convex functions namely “invex” functions. We define “invexity” of functions, as a generalization of convexity (Hanson, 1981).
Definition 4 (Invex function). Let ϕptq be a function defined on a set C. Let η be a vector valued function defined in C ˆ C such that ηpt1, t2q⊺∇ϕpt2q, is well defined @t1, t2 P C. Then, ϕptq is a η-invex function if ϕpt1q ´ ϕpt2q ě ηpt1, t2q⊺∇ϕpt2q, @t1, t2 P C.
Note that convex functions are η-invex for ηpt1, t2q “ t1 ´ t2. Hanson (1981) showed that if the objective function and constraints are both η-invex with respect to same η defined in C ˆ C, then Karush-Kuhn-Tucker (KKT) conditions are sufficient for optimality, while it is well-known that KKT conditions are necessary. Ben-Israel & Mond (1986) showed a function is invex if and only if each of its stationarity point is a global minimum.
In the next lemma, we show that the relaxed optimization problem (6) is indeed η-invex for a particular η defined in C ˆ C and a well defined set C. Before that, we will reformulate it into an equivalent optimization problem. Note that in the optimization problem (6), diagpZq “ 1. Thus, xI,Zy is a constant equal to n ` 1. Using this, we can rewrite the optimization problem as:
minw,Z xMpwq,Zy ` λn}w}1 ` xI,Zy, such that diagpZq “ 1, Z ľ 0n`1ˆn`1 , (7)
Let C “ tpw,Zq | w P Rd, diagpZq “ 1,Z ľ 0n`1ˆn`1u. We take M1pwq “ Mpwq ` I and the corresponding optimization problem becomes: minpw,ZqPCxM1pwq,Zy ` λn}w}1. We will show that @pw,Zq P C, xM1pwq,Zy`λn}w}1 is an invex function. Note that by definition of the ℓ1-norm, }w}1 “ sup}a}8“1xa,wy. Thus, it suffices to show that @a P R
d, xM1pwq,Zy and xa,wy are invex for the same ηpw, w̄,Z, Z̄q. Lemma 1. For pw,Zq P C, the functions fpw,Zq “ xM1pwq,Zy and gpw,Zq “ xa,wy are ηinvex for ηpw, w̄,Z, Z̄q fi „
w ´ w̄ M1pw̄q´1M1pwqpZ ´ Z̄q
ȷ
, where we abuse the vector/matrix notation
for clarity of presentation, and avoid the vectorization of matrices.
Now that we have established that optimization problem (6) is invex, we are ready to discuss our main results in the next section.

heading: 4 Our Theoretical Analysis
text: In this section, we show that our Invex Fair Lasso formulation correctly recovers the hidden attributes and the regression parameter vector. More formally, we want to achieve the two goals by solving optimization problem (6) efficiently. First, we want to correctly and uniquely determine the hidden sensitive attribute for each data point, i.e., z˚ P t´1, 1un. Second, we want to recover regression parameter vector which is close to the true parameter vector w˚ P Rd in ℓ2-norm. Let w̃ and Z̃ be the solution to optimization problem (6). Then, we will prove that w̃ and w˚ have the same support and z̃ constructed from Z̃ is exactly equal to z˚. We define ∆ fi pw̃ ´ w˚q.

heading: 4.1 KKT conditions
text: We start by writing the KKT conditions for optimization problem (6). Let µ P Rn`1 and Λ ľ 0n`1ˆn`1 be the dual variables for optimization problem (6). For a fixed λn, the Lagrangian Lpw,Z;µ,Λq can be written as Lpw,Z;µ,Λq “ xMpwq,Zy ` λn}w}1 ` xdiagpµq,Zy ´ 1⊺µ ´ xΛ,Zy. Using this Lagrangian, the KKT conditions at the optimum can be written as:
1. Stationarity conditions:
BxMpwq,Zy Bw ` λng “ 0dˆ1, (8)
where g is an element of the subgradient set of }w}1, i.e., g P B}w}1Bw and }g}8 ď 1.
Mpwq ` diagpµq ´ Λ “ 0n`1ˆn`1 (9)
2. Complementary Slackness condition:
xΛ,Zy “ 0 (10)
3. Dual Feasibility condition: Λ ľ 0n`1ˆn`1 (11)
4. Primal Feasibility conditions:
w P Rd, diagpZq “ 1, Z ľ 0n`1ˆn`1 (12)
Next, we will provide a setting for primal and dual variables which satisfies all the KKT conditions. But before that, we will describe a set of technical assumptions which will help us in our analysis.

heading: 4.2 Assumptions
text: Let S denote the support of w˚, i.e., S “ ti |w˚i ‰ 0, i P rdsu. Similarly, we define the complement of support S as Sc “ ti |w˚i “ 0, i P rdsu. Let |S| “ s and |Sc| “ d ´ s. For ease of notation, we define H fi EpXX⊺q and Ĥ fi 1nX
⊺X. As the first assumption, we need the minimum eigenvalue of the population covariance matrix of X restricted to rows and columns in S to be greater than zero. Later, we will show that this assumption is needed to uniquely recover w in the optimization problem (6). Assumption 1 (Positive Definiteness of Hessian). HSS ą 0sˆs or equivalently eigminpHSSq “ Cmin ą 0.
In practice, we only deal with finite samples and not populations. In the next lemma, we will show that with a sufficient number of samples, a condition similar to Assumption 1 holds with high probability in the finite-sample setting.
Lemma 2. If Assumption 1 holds and n “ Ωp s`log d C2min q, then eigminpĤSSq ě Cmin2 with probability at least 1 ´ Op 1d q.
As the second assumption, we will need to ensure that the variates outside the support of w˚ do not exert lot of influence on the variates in the support of w˚. This sort of technical condition, known as the mutual incoherence condition, has been previously used in many problems related to regularized regression such as compressed sensing (Wainwright, 2009), Markov random fields (Ravikumar et al., 2010), non-parametric regression (Ravikumar et al., 2007), diffusion networks (Daneshmand et al., 2014), among others. We formally present this technical condition in what follows. Assumption 2 (Mutual Incoherence). }HScSH´1SS}8 ď 1 ´ α for some α P p0, 1s.
Again, we will show that with a sufficient number of samples, a condition similar to Assumption 2 holds in the finite-sample setting with high probability.
Lemma 3. If Assumption 2 holds and n “ Ωp s 3plog s`log dq τpCmin,α,σ,Σq q, then }ĤScSĤ ´1 SS}8 ď 1 ´ α 2 with probability at least 1 ´ Op 1d q where τpCmin, α, σ,Σq is a constant independent of n, d and s.
In Appendix L, we experimentally show that Assumption 1 is easier to hold (i.e., n P Ωps ` log dq) than Assumption 2 (i.e., n P Ωps3 log dq). Eventually, both assumptions hold as the number of samples increases.

heading: 4.3 Construction of Primal and Dual Witnesses
text: In this subsection, we will provide a construction of primal and dual variables which satisfies the KKT conditions for optimization problem (6). To that end, we provide our first main result. Theorem 1 (Primal Dual Witness Construction). If Assumptions 1 and 2 hold, λn ě 128ρkα ? log d n and n “ Ωp s 3 log d
τ0pCmin,α,σ,Σ,ρ,k,γq q, then the following setting of primal and dual variables
Primal Variables: w̃ “ pw̃S ,0d´sˆ1q
where, w̃S “ argmin wS
1 n pX.SwS ` γz˚ ´ yq⊺pX.SwS ` γz˚ ´ yq ` λn}wS}1
Z “ Z˚ fi „ 1 z˚⊺
z˚ z˚z˚⊺
ȷ
Dual Variables: µ “ ´diagpMpw̃qZ˚q, Λ “ Mpw̃q ´ diagpMpw̃qZ˚q
(13)
satisfies all the KKT conditions for optimization problem (6) with probability at least 1 ´ Op 1n q, where τ0pCmin, α, σ,Σ, ρ, k, γq is a constant independent of s, d and n and thus, the primal variables are a globally optimal solution for (6). Furthermore, the above solution is also unique.
Proof Sketch. The main idea behind our proofs is to verify that the setting of primal and dual variables in Theorem 1 satisfies all the KKT conditions described in subsection 4.1. We do this by proving multiple lemmas in subsequent subsections. The outline of the proof is as follows:
• It can be trivially verified that the primal feasibility condition (12) holds. Similarly, the second stationarity condition (9) holds by construction of Λ. • In subsection 4.4, we use Lemmas 4 and 11 to verify that the stationarity condition (8) holds. • In subsection 4.5, we use Lemma 5 to verify the complementary slackness condition (10). • In subsection 4.6, we show that the dual feasibility condition (11) is satisfied using results
from Lemmas 6, 7, 8 and 12. • Finally, in subsection 4.7, we show that our proposed solution is also unique.
4.4 Verifying the Stationarity Condition (8)
In this subsection, we will show that the setting of w̃ and Z˚ satisfies the first stationarity condition (8) by proving the following lemma. Lemma 4. If Assumptions 1 and 2 hold, λn ě 128ρkα ? log d n and n “ Ωp s3 log d τ1pCmin,α,σ,Σ,ρq q, then the setting of w and Z from equation (13) satisfies the stationarity condition (8) with probability at least 1 ´ Op 1d q, where τ1pCmin, α, σ,Σ, ρq is a constant independent of d, s or n.
4.5 Verifying the Complementary Slackness (10)
Next, we will show that the setting of Λ and Z in (13) satisfies the complementary slackness condition (10). To this end, we will show the following:
Lemma 5. Let Λ be defined as in equation (13), then ζ˚ fi „
1 z˚
ȷ
is an eigenvector of Λ correspond-
ing to the eigenvalue 0. Furthermore, xΛ,Z˚y “ 0.
Proof. We will show that Λζ˚ “ 0n`1ˆ1. Note that,
Λ “ Mpwq ´ diagpMpwqZ˚q “ „ ´ γn pXw ´ yq T z˚ γn pXw ´ yq T
γ n pXw ´ yq ´diagp γ n pXw ´ yqz ˚T q
ȷ
Multiplying the above matrix with ζ˚ gives us 0n`1ˆ1. Now xΛ,Z˚y “ tracepΛ⊺Z˚q “ tracepΛζ˚ζ˚⊺q “ 0 as Λζ˚ “ 0n`1ˆ1.
4.6 Verifying the Dual Feasibility (11)
We have already shown that Λ has 0 as one of its eigenvalues. To verify that it satisfies the dual feasibility condition (11), we show that second minimum eigenvalue of Λ is greater than zero with high probability. At this point, it might not be clear why strict positivity is necessary, but this will be argued later in subsection 4.7. Now, note that:
Ppeig2pΛq ą 0q ě Ppeig2pΛq ą 0, }∆}2 ď hpnqq ě Ppeig2pΛq ą 0|}∆}2 ď hpnqqPp}∆}2 ď hpnqq (14)
where hpnq is a function of n. We bound Ppeig2pΛq ą 0q in two parts. First, we bound Ppeig2pΛq ą 0q given that }∆}2 ď hpnq and then we bound the probability of }∆}2 ď hpnq. Lemma 6. Given that }∆}2 ď hpnq, the second minimum eigenvalue of Λ as defined in equation (13) is strictly greater than 0 with probability at least 1 ´ expp´ γ 2
8pρ2hpnq2`σ2eq ` log nq.
Proof. As the first step, we invoke Haynesworth’s inertia additivity formula (Haynsworth, 1968) to prove our claim. Let R be a block matrix of the form R “ „
A B B⊺ C
ȷ
, then inertia of matrix R,
denoted by InpRq, is defined as the tuple pπpRq, νpRq, δpRqq where πpRq is the number of positive eigenvalues, νpRq is the number of negative eigenvalues and δpRq is the number of zero eigenvalues of matrix R. Haynesworth’s inertia additivity formula is given as:
InpRq “ InpCq ` InpA ´ B⊺C´1Bq (15) Note that,
Λ “ Mpwq ´ diagpMpwqZ˚q “ „ ´ γn pXw ´ yq ⊺z˚ γn pXw ´ yq ⊺ γ n pXw ´ yq ´diagp γ n pXw ´ yqz ˚⊺q ȷ
Then the following holds true by applying equation (15):
InpΛq “Inp´diagp γ n pXw ´ yqz˚⊺qq ` Inp´ γ n pXw ´ yq⊺z˚ ´ γ n pXw ´ yq⊺
p´diagp γ n pXw ´ yqz˚⊺q´1 γ n pXw ´ yqq
Notice that the term ´ γn pXw ´ yq ⊺z˚ ´ γn pXw ´ yq ⊺p´diagp γn pXw ´ yqz ˚⊺q´1 γn pXw ´ yqq evaluates to 0. Thus, it has 0 positive eigenvalue, 0 negative eigenvalue and 1 zero eigenvalue. We have also shown in Lemma 5 that Λ has at least 1 zero eigenvalue. It follows that
πpΛq “ πp´diagp γ n pXw ´ yqz˚⊺qq, νpΛq “ νp´diagp γ n pXw ´ yqz˚⊺qq δpΛq “ δp´diagp γ
n pXw ´ yqz˚⊺qq ` 1
(16)
Next, we will show that ´diagp γn pXw ´ yqz ˚⊺q has all of its eigenvalues being positive. Lemma 7. For a given }∆}2 ď hpnq, all eigenvalues of ´diagp γn pXw´yqz ˚⊺q are strictly greater than 0 with probability at least 1 ´ expp´ γ 2
8pρ2hpnq2`σ2eq ` log nq.
Proof. Using equation (1), we can expand the term ´diagp γn pXw ´ yqz ˚⊺q as ´diagp γn pXpw ´ w˚q ´ γz˚ ´ eqz˚⊺q. Since eigenvalues of a diagonal matrix are its diagonal elements, we focus on the i-th diagonal element of ´diagp γn pX∆ ´ γz ˚ ´ eqz˚⊺q which is γ 2 n ´ γ nz ˚ i pX ⊺ i¨∆ ` eiq. Note that pX⊺i¨∆ ` eiq is a sub-Gaussian random variable with parameter ρ2}∆}22 ` σ2e . Using the tail inequality for sub-Gaussian random variables, for some t ą 0, we can write:
PppXi¨∆ ` eiq ě tq ď expp´ t2
2pρ2}∆}22 ` σ2eq q
We take union bound across all the diagonal elements and replace t “ γ2 and }∆}2 ď hpnq to complete the proof, i.e.,
PpDi P rns , pXi¨∆ ` eiq ě tq ď n expp´ γ2
8pρ2hpnq2 ` σ2eq q . (17)
The result of Lemma 6 follows directly from Lemma 7 and equation (16).
Now, we are ready to bound }∆}2. Due to our primal dual construction, }∆}2 is simply equal to }∆S}2. We provide a bound on ∆S in the following lemma: Lemma 8. If Assumptions 1 and 2 hold, λn ě 128ρk ? log d αn and n “ Ωp s3 log d
τ2pCmin,ρ,kq q, then }∆S}2 ď 2λn ? s
Cmin with probability at least 1 ´ Op 1d q where τ2pCmin, ρ, kq is a constant independent of s, d or
n. By taking hpnq “ 2λn ? s
Cmin in (14), we get the following: Ppeig2pΛq ą 0q ě 1 ´ Op 1n q, as long as
n “ Ωp s 3 log d
τ3pCmin,ρ,k,α,γq q, where τ3pCmin, ρ, k, α, γq is a constant independent of s, d and n. The above results combined with the property that optimization problem (6) is invex ensure that the setting of primal and dual variables in Theorem 1 is indeed the globally optimal solution to the problem (6). It remains to show that this solution is also unique.

heading: 4.7 Uniqueness of the Solution
text: First, we prove that Z˚ is a unique solution. Suppose there is another solution Z̄ which satisfies all KKT conditions and is optimal. Then, Z̄ ľ 0n`1ˆn`1 and xΛ, Z̄y “ 0. Since, Λ ľ 0n`1ˆn`1 and eig2pΛq ą 0, ζ˚ spans all of its null space. This enforces that Z̄ is a multiple of Z˚. But primal feasibility dictates that diagpZ̄q “ 1. It follows that Z̄ “ Z˚. To show that w̃ is unique, it suffices to show that w̃S is unique. After substituting Z “ Z˚, we observe that the Hessian of optimization problem (6) with respect to w and restricted to rows and columns in S, i.e., ĤSS is positive definite. This ensures that w̃ is a unique solution.
The setting of primal and dual variables in Theorem 1 not only solves the optimization problem (6) but also gives rise to the following results: Corollary 1. If Assumptions 1 and 2 hold, λn ě 128ρkα ? log d n and n “ Ωp s3 log d τ1pCmin,α,σ,Σ,ρq q, then the following statements are true with probability at least 1 ´ Op 1n q:
1. The solution Z correctly recovers hidden attribute for each sample, i.e., Z “ Z˚ “ ζ˚ζ˚⊺. 2. The support of recovered regression parameter w̃ matches exactly with the support of w˚. 3. If miniPS |w˚i | ě 4λn ? s Cmin then for all i P rds, w̃i and w˚i match up to their sign.

heading: 5 Experimental Validation
text: Synthetic Experiments. We validate our theoretical result in Theorem 1 and Corollary 1 by conducting experiments on synthetic data. We show that for a fixed s, we need n “ 10β log d samples for recovering the exact support of w˚ and exact hidden attributes Z˚, where β ” βps, Cmin, α, σ,Σ, ρ, γ, kq is a control parameter which is independent of d. We draw X P Rnˆd and e P Rn from Gaussian distributions. We randomly generate w˚ P Rd with s “ 10 non-zero entries. Regarding the hidden attribute z˚ P t´1, 1un, we set n2 entries as `1 and the rest as ´1. The response y P Rn is generated according to (1). According to Theorem 1, the regularizer λn is chosen to be equal to 128ρkα ? log d n . We solve optimization problem (6) by using an alternate optimization algorithm that converges to the optimal solution (See Appendix K for details). Figure 2a shows that our method recovers the true support as we increase the number of samples. Similarly, Figure 2c shows that as the number of samples increase, our recovered hidden attributes are 100% correct. Curves line up perfectly in Figure 2b and 2d when plotting with respect to the control parameter β “ log nlog d . This validates our theoretical results (Details in Appendix M).
Real World Experiments. We show applicability of our method by identify groups with bias in the Communities and Crime data set (Redmond, 2002) and the Student Performance data set (Cortez, 2008). In both cases, our method is able to recover groups with bias (Details in Appendix O).

heading: 6 Concluding Remarks
text: In this paper, we provide a novel formulation of invex fair LASSO which incorporates fairness constraints into the standard LASSO problem without compromising on the performance. We show that invexity of our optimization problem allows for a tractable solution. We provide provable
theoretical guarantees for our solution and further validate them by computational experiments. The sample complexity of our method is polynomial in terms of sparsity and logarithmic in terms of the dimension of the true parameter. Our method helps to identify and subsequently remove bias in the sparse regression model. In the future, it will be interesting to study invex relaxations of other models of fairness. Since set of invex functions subsumes convex functions, invexity will enable us to tackle a larger set of problems.
Societal Impact And Limitations
Fairness in machine learning is an active field of research. As it has the potential to affect the basic well being of our society, it should always be used with caution. This is especially important when one moves away from the theoretical setting and tries to apply fairness algorithms to real world data where the validity of technical assumptions cannot be easily verified. As with any algorithm in prior literature (Calders, 2013; Agarwal, 2019; Fitzsimons, 2019; Berk, 2017; Chzhen et al., 2020), one has to be extra cautious when interpreting the results of our method as well. In particular, we emphasize that our method does not characterize the nature of the recovered bias – good or bad. Our proposed hidden attribute could be seen as a proxy for algorithmic bias, but one that exists outside the features of the data itself. To interpret the meaning of such an attribute, we advise consulting with a domain expert, and to regress the discovered hidden attribute against some existing predictors provided by the expert. We also caution practitioners that such a notion of hidden bias would naturally not extend to every task, and should not be used as a silver bullet to justify fairness in socially significant contexts.
Acknowledgments and Disclosure of Funding
This material is based upon work supported by the National Science Foundation under Grant No. 2134209-DMS.

Review summaries:
The paper considers the task of sparse regression on a biased dataset where the bias depends on a hidden binary attribute. A new optimization problem is formulated which is then relaxed into an invex optimization problem. The authors then prove that their invex fair lasso formulation correctly recovers the hidden attributes and finds a regression parameter vector with the same support as the true parameter vector. This is done by constructing a pair of primal and dual variables that have the desired properties and fulfill the KKT conditions. In the experimental section, the theoretical results are validated on synthetic data. Moreover, the method is evaluated on two real world datasets where the hidden attributes are recovered in both cases.

The paper considers sparse regression with a hidden binary attribute modeling unknown bias (as in lack of fairness).  This is in contrast to most other work on fairness where the protected attribute is known, and used to impose fairness constraints.  The paper presents an invex relaxation (bi-convex generalization of convexity without local minima), proves its correctness, and makes claims that it can exactly identify hidden bias, and does so at no cost to prediction accuracy.  

This paper studies the inverse problem of fair sparse regression. The corresponding optimization problem contains a continuous variable and discrete variable, and it is combinatorial. The authors consider a novel invex relaxation of it. They prove that there exists a unique solution to the invex problem，and the true variables of the model can be recovered exactly. 

A problem of fair sparse linear regression is addressed in this paper, where bias depends upon a hidden binary random variable. This hidden r.v. can be thought of as a clustering assignment combining sparse regression. An optimization problem is formulated by the authors as a mixed-integer linear programming originally, then, a continuous relaxation is used to reformulate it into an invex optimization problem. The theoretical results mainly focus on the solution's uniqueness of the invex problem by verifying Karush-Kuhn-Tucker conditions and primal-dual certificates. In the experiments, the proposed method shows the ability to correctly recover the support of the regression parameter vector, and the correct clusters.