Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem
Authors: Adarsh Barik
Jean Honorio
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Fairness
Invexity
Combinatorial Optimization
Primal Dual Witness Method

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.

Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem
Adarsh Barik Department of Computer Science
Jean Honorio
Department of Computer Science Purdue University West Lafayette, Indiana, USA jhonorioqpurdue edu
Purdue University
West Lafayette, Indiana, USA abar abarikqpurdue..om edu
Abstract
In this paper, we study the problem of fair sparse regression biased dataset where bias depends upon hidden binary attribute. The presence of a hidden attribute adds extra layer of complexity to the problem by combining sparse regression and clustering with unknown binary labels. The corresponding opti- mization problem is combinatorial, but propose novel relaxation of it invex optimization problem. To the best of our knowledge, this is the first invex relaxation for combinatorial problem. We show that the inclusion of the debi- asing/fairness constraint in our model has no adverse effect on the performance. Rather, enables the recovery of the hidden attribute. The support of our covered regression parameter vector matches exactly with the true parameter vec- tor. Moreover, 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 provide theoretical guarantees for the combi- natorial 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.
Introduction
In modern times, machine learning algorithms used in wide variety of applications, many of which are decision making processes such as hiring (Holiman et all 2018), predicting human behav- ior (Subrahmanian & Kumant 2017). COMPAS (Conrectional Offender Management Profiling for Alternative Sanctions) risk assessment (Brennan et all 2009),, among others. These decisions have large impacts society (Kleineer al] 208) 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 2019, classification (Agaraal et al,, 2018; Domin el all, 2018; Dwork el all
2012
Leldman
2015: Hardt etall 2016: Huang Vishnoi, 2019 Pedreshi all 2008: Zatar
aall
2019: Zemel et all 2013) and clustering (Backurs ef all 2019: Bera el all 2019 Chen el all
2019
Cherichett all 20L1 Huang all 2019). common thread in the above literature that
performance is only viewed in terms of risks, e.g., misclassification rate, false positive rate, false negative rate, mean squared eπror.
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 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 faimnsss, and modeled them as penalty functions. Calders (2015) proposed the faimess notions of equal means and balanced residuals modeling
them as explicit constraints. Agarwal (2019), Fitzsimons (2019) and Chzhen et all (2020) studied
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Comparison to prior work. Notation: is the number of non-zero entries in the regression parameter vector and d is its dimension. The terms independent of s and are not shown in the order notation.
Table
Paper
Hidden sensitive attribute
Modeling type
Sample complexity
Caldens (2013)
Agarwal
No
Explicit
con-
Not provided
2019) Mizsimons
20119
straint
Berk
(2017)
No
Penalty function
Not provided
Chzhen al (2020)
No
Implicit
Not provided
Our paper
Yes
Implicit
[ log d)
demographic parity. While Agarwal (2019), Eiizsions (2019) modeled it as an explicit constraint, Chzhen et (2002) included implicitly their proposed model.
All above work assume access to the sensitive attribute the training samples and provide a framework which inherently fair. Our work fundamentally differs from these work 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, focus identifying unfairly treated members/samples. This adds an extra layer of complexity to linear regression. We solve the linear regression problem while simultaneously solving clustering problem where identify two clusters - one which is positively biased and the other which is negatively biased. Table 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 M). 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 highly correlated with the sensitive attribute. In such 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.
(a) Biased data without hidden (b) Biased data after identifying hid- tive attribute
(c) Data after debiasing
den sensitive attribute
Figure 1: Data before debiasing and after debiasing. Notice how means for two groups (shown as horizontal lines) become almost equal after debiasing.
While the standard algorithms solving the sparse/LASSO problem in this setting do provide an esti- mate of the regression parameter vector, they do not fit the model accurately they fail consider any fairness criteria in their formulations. It is natural then to think about including the hidden at- tribute 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 novel technique to tackle the combinatorial LASSO problem with a hidden at- tribute and provide theoretical guarantees about the quality of the solution given 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 check to detect and remove such unintended discrimination. While the current belief that there trade-off between fairness and performance (Corbett- Davies
d 2 Wi; Klemnber all 2017: Pleiss et al 2017: Z Zlobarto, 2015: Zhao & Gordon 2019)

---

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:
We formulate a novel combinatorial version of sparse linear regres- sion which takes fairness/bias into the consideration. The addition of clustering comes at no extra cost in terms of the performance.
Defining the problem:
Invex relaxation: Most of the current methods solve convex optimization problems as makes the solution tractable. We propose 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 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, clusters (hidden attributes) and a regression parameter vector which is correct up to the sign of entries with respect the true parameter vector. On a more technical side, 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.
recover the true
Notation and Problem Definition
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 E E be the response variable and X IR be the observed attributes. Let * [-1,1] be the hidden attribute and y E R>0 be the amount of bias due to the hidden attribute. The response y is generated using the following mechanism:
XTw
7/** +
(1)
where e is independent noise term. For example, y could represent the market salary of new candidate, X could represent the candidate's 's skills and z could represent the population group the candidate belongs (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 y E R> is available. In practice, even a rough estimate (5%5% of y also works well (See Appendix M...
mean sub-Gaussian random vector aLl ))) with covariance De Sd, i.e., there exists a 0, such that for all Rd
Let [d] denote the set 11,2, .1,,,...,d) ,d]. We assume X E E to be
the following holds: [[(ep(a T)) exp( Jelk5 ). By simply taking o; and a% 0, vk i, follows that each entry of X sub-Gaussian with parameter p. In particular, we will assume that Vi [d], X, is a sub-Gaussian random variable with parameter o > 0. It follows trivially that VEn max [d] VEno & p. We will further assume that is zero mean independent sub- lub-Gaussian noise with variance ae. We assume that as the number of samples increases, the noise in the model gently decreases. We model this by taking ae = vlogn for some > 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 vari- variables. Notice that
able with strictly log-concave density, and any finite mixture of for the group with x +1, E(y) = 7 and for the group with -1. E[y) -y. This means that after correctly identifying groups, one could perform debiasing by subtracting or adding 7 for 2 +1 and 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 (201).
The parameter vector = Rd is s-sparse, i.e., most entries of w are non-zero. We receive i..dd samples of X E Rd and y IR and collect them in X E Ruxd and R." respectively. Thus, in the finite-sample setting,
X + +z= + cc,
(2)
3

---

where z* E [-1,1]] and e e R" both collect independent realizations of x {-1,1] and e I. Our goal to recover w* and z" using the samples y).
We denote a matrix A E Rex4 restricted to the columns and rows in P = [y] and Q = [g] re- spectively Arq- Similarly, vector RP restricted entries in P is denoted ey. We (A) to denote the i-th eigenvalue (Ist being the smallest) of matrix A. Similarly, eigmax (A) denotes the maximum eigenvalue of matrix A. We use diag(A) denote vector containing the diagonal element of matrix A. By overriding the same notation, we use (iag(() to denote a diagonal matrix with its diagonal being the entries in vector v. We denote the inner product be- tween two matrices A and B by (A, B), i.e., (A, B)
trace of matrix. The notation A 2 B denotes that (race(ATB)) where trace denotes the is positive semidefinite matrix. Similarly, A > B denotes that A - B is positive definite matrix. For vectors, ||m||p denotes the t--vector norm of vector v E IR,, i.e., l|ullz - (_ |ujlp) If p = 0c, then we define vo max; ;-1 |oy|- For matrices, ||llp denotes the induced ép-matrix norm for matrix E TRPxq In particular, |A| denotes the spectral norm of A and ||Al|oo + maX - |Ag] A function f()) is of order [))(()) and denoted by f(x) ((g(z)), if there exists constant C > 0 such that for big enough Zo. f(x) > Cg(x), Vo 2 zn- Similarly, a function ((x is of order O(g(z)) and denoted by [(x) (g)()),, if there exists constant C 0 such that for big enough zo. f(x) & Cg(a),, Vo 2 zi. For brevity in our notations, we treat any quantity independent of d, s and constant. Detailed proofs for lemmas and theorems are available in the supplementary material.
3 Our New Optimization Problem and Invexity
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 combinatorial problem. Without any information about the hidden attribute z* in Equation (,), the following LASSO formulation could be incorrectly and unsuccessfully used to estimate the parameter w*
Definition (Standard LASSO).
minler [Xw -X y) An ///w
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 esti- mating both w* and :":
Definition (Combinatorial Fair LASSO).
min a 1
n. (Xw zz - y (Xw + zy y) + \m.|w|li, such that E (-1,1), Vie [n]. (4)
where An > 0 is the regularization level which depends on n.
In its current form, optimization problem (+) is non-convex mixed integer quadratic program (MIQP). Solving MIQP is NP-hard (See Appendix H). Next, we will provide a continuous but still non-convex relaxation of (E)) For case of notation, we define the following quantities:
zT
((w)
2(x y)
I(w)= + [Xw TX y): Z
+
M(w)
+
Z
zzt
7 [x y)
L
(5)
where I is an identity matrix. We provide the following invex relaxation to the optimization problem (2))
Definition 3 (Invex Fair LASSO).
min,,
(M)w), Z) + An||wola, such that diag (Z) = 1, Z 0,+1x=+1
(6)
Note that optimization problem (K)) is continuous and convex with respect to w and Z separately but
it is not jointly convex (See Appendix IN for details). Specifically, for fixed w. the matrix M(w) becomes constant and problem (K resembles a semidefinite program. For fixed Z, problem (i) resembles a standard LASSO. Unfortunately, problem (K) is not jointly convex thus, it might still remain difficult to solve. Next, we will provide arguments that despite being non-convex, optimization problem (B) belongs to particular class of non-convex functions namely "invex" functions. We define "invexity" of functions, as a generalization of convexity (Hanson. 1981).
and Z. and

---

Definition 4 (Invex function). Let ((t) be function defined on set C. Let be a vector valued function defined in C x C such that n(t,, 12) TV)(2)) well defined Vt,,t C. Then, 6(t) is vi-ivve function if ((11) (212) > 12(1,12) ((((2)) 14, 12 C.
Note that convex functions are r7-invex for n](1, (2) = t t2. HEnsOn (1991I) showed that the objective function and constraints are both 17-invex with respect same n defined in C' x C, then Karush-Kuhn- Tucker (KKT) conditions are sufficient for optimality, while is well-known that KKT conditions are necessary. Ben-IsraeL Mond Mond (1986) showed function is invex if and only if each its stationarity point is a global minimum.
In the next lemma, we show that the relaxed optimization problem ( is indeed 77invex for par- ticular 7/ defined 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), diag(Z) 1. Thus, (I, Z> is a constant equal to n + 1. Using this, we can rewrite the optimization problem as:
min
(M(w), ZD) An |wll1 (I, Z), such that diag(Z) 1, Z 2 Ont1xnt1,
Let C = [ww Z) w Rd, diag Z) = 1, 1.23 2 0n+1xn+1). We take M'w) = M(w) + +I and the (eel Z) + A///w//1- We will show an invex function. Note that by definition of the -ormm, ||l||| s0 w) Thus, it suffices to show that Ya IR., (M'(w), Z) and (a, w) are invex for the same (,,, w. Z, Z).
corresponding optimization problem becomes:
that ((W Z) E C, (M'(w.. Z)+A,||uu) An/|w||1
Lemma 1. For (w, Z) E C, the functions f(w, Z)
(M') Z) and g(w, Z) (a, w> are ni- where abuse the vector/matrix notation
invex for nww,, w. Z 2) for clarity of presentation, and avoid the vectorization of matrices.
M((w)- (Z Z)
Now that we have established that optimization problem (6) invex, we are ready discuss our main results in the next section.
4 Our Theoretical Analysis
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 (E) efficiently. First, we want to correctly and uniquely determine the hidden sensitive attribute for each data point, i.e., x* E 1-1,1)". Second, we want recover regression parameter vector which is close to the true parameter vector w" e Rd in fz-norm. Let and be the solution optimization problem (8). Then, we will prove that w and w" have the same support and ž constructed from Z is exactly equal to z*. We define A a (w w*).
4.1 KKT conditions
We start by writing the KKT conditions for optimization problem (b) Let E R=-1 and A 0n41xn+1 be the dual variables for optimization problem (Ei) For fixed An the Lagrangian
L(w, Z: p, A) can be written as L(w Z; μ. A) = (M(w), Z) + >, >n]|ww] 1 + (diag(H), Z) 1
(A, Z). Using this Lagrangian, the KKT conditions the optimum can be written as:
1. Stationarity conditions:
aM((w) Z)
+ Ann Odx1,
(8)
dw
where is an element the subgradient set of || 1, i.e., g
@1 Cur
and ||g| & 1.
M(w) + diag(u) A 0x41xn+1
(9)
2. Complementary Slackness condition:
(A, Z) 0
(10)
5

---

3. Dual Feasibility condition:
A 2 0n+1xn+1
(11)
4. Primal Feasibility conditions:
w R diag(Z)
=, Z 0x+1xn+1
(12)
Next, we will provide a setting for primal and dual variables which satisfies all the KKT conditions. But before that, will describe a of technical assumptions which will help us in our analysis.
4.2 Assumptions
Let denote the support of u. i.e., S {i wo of E [d]]. Similarly, we define the complement of support S as S [i] : 0, i [d]. Let [S] and [S9] = d 8. For ease of notation, we define H B[X XT) and H = LXTX. 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, will show that this assumption needed uniquely recover in the optimization problem (T)
Assumption (Positive Definiteness of Hessian). Hss Oaxa or equivalently eigmin (Hss) 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 Assumption holds with high probability in the finite-sample setting.
Lemma 2. If Assumption Q holds and O s+logd), then eigmin (Hss) Cuii with probability at least - (
As the second assumption, will need to ensure that the variates outside the support of u 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 (Wainwrigh) 2009), Markov random fields (Ravikumar all 2010), non-parametric regression (Ravikumar
ετττ). diffusion networks (Daneshmand all 2014), among others. We formally present this technical condition in what follows.
Assumption (Mutual Incoherence). [ s H 5 & 1 a for some (0, 1].
Again, we will show that with a sufficient number samples, condition similar to Assumption holds in the finite-sample setting with high probability.
Lemma 3. If Assumption 2 holds and 52( 8 (log xloggg) then H & with
probability least O(2) where 7(Cuin, a, a, Σ) is constant independent of n, d and
In Appendix we experimentally show that Assumption D is casier hold (i.c., E Q(s + log d)) than Assumption A (i.c., E Iss log d)). Eventually, both assumptions hold as the number of samples increases.
4.3 Construction of Primal and Dual Witnesses
In this subsection, we will provide a construction of primal and dual variables which satisfies the KKT conditions for optimization problem (8) To that end, provide our first main result.
Theorem (Primal Dual Witness Construction). If Assumptions W and D hold, An 128pk Alng
n
and O TolC (.pke))))))))) ) then the following selting of primal and dual variables
2 Log d
Primal Variables:
i (ws, Od-sx1)
1 - sss + 7z - TX + 7z" - y) + An Anllllla
where, us = arg min
wy n
(13)
1
TT
Z 7
z
z z*22
Dual Variables:
- diag
A M(ū) diag (M (z)

---

satisfies all the KKT conditions for optimization problem ( with probability at least 1 - O + where To mins a, G. P.P, k) constant independent of d and n and thus, the primal vari- ables are a globally optimal solution for (G). Furthermore, the above solution is also unique.
Proof Sketch. The main idea behind our proofs to verify that the setting of primal and dual variables in Theorem I satisfies all the KKT conditions described in subsection I. We do this by proving multiple lemmas in subsequent subsections. The outline of the proof is follows:
It can be trivially verified that the primal feasibility condition (l2) holds. Similarly, the second stationarity condition (H) holds by construction of A.
In subsection we use Lemmas and D to verify that the stationarity condition holds.
In subsection
K we use Lemma 5 to verify the complementary slackness condition (II))
In subsection
G show that the dual feasibility condition (II is satisfied using results
from Lemmas R M
X and I
Finally, in subsection
! we show that our proposed solution also unique.
4.4 Verifying the Stationarity Condition
(
In this subsection, we will show that the setting of v and Z* satisfies the first stationarity condition (8) by proving the following lemma.
Lemma 4. If Assumptions D and @ hold, An > 128pk Alogd and M (Cmim, a.. then the setting of w and Z from equation (13) satisfies the stationarity condition (8) with probability at least 1 O()), where (Cmin; Or, T, E,p) is constant independent of d, n.
4.5 Verifying the Complementary Slackness (IT))
Next, we will show that the setting of A and in (L3) satisfies the complementary slackness condi- tion (IT). To this end, we will show the following:
Lemma 5. Let A be defined as in equation (I3), then Ç*
is an eigenvector of A correspond-
z
ing to the eigenvalue O. Furthermore, (A, Z = O.
Proof. We will show that AÇ* = Ont1x1- Note that,
(Xw T2*
2 2X w yy n
A M(w) - diag(M di))(M(w))"*)
3 [X 1)
-diag( (Xw y) 2
Multiplying the above matrix with ç* gives us 0n41x1. Now (A, z*) = trace(ATZ*) (Tace(A(*(*T)) 0 AÇ* 0,+1x1.
4.6 Verifying the Dual Feasibility
We have already shown that has 0 as one of its eigenvalues. To verify that it satisfies the dual feasibility condition (LI), show that second minimum eigenvalue of A 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 A. Now, note that:
((eigz(A) 0) > P(eigg (A) O, |||| h(n)) > (Ae > 0|| h(n))P((A||) h(n)) (14)
where h(n) is function of n. We bound (Peeigg (A) 0) in two parts. First, we bound P(eigg(A) 0) given that | & h(() and then we bound the probability of |A] & h(n).
Lemma 6. Given that | & h(n), the second minimum eigenvalue of A as defined in equation x2
H is strictly greater than 0 with probability at least - exp( 86oh(n) + log n).
Proof. As the first step. we invoke Haynesworth's 's inertia additivity formula (Haynsworth, (968) to
A
prove our claim. Let be block matrix the form = BT
C then inertia of matrix R.
7

---

denoted by (R) is defined as the tuple (T(R), ( where x ((R) is the number of positive eigenvalues, v(R) the number of negative eigenvalues and (RR) is the number of zero eigenvalues of matrix R. Haynesworth's inertia additivity formula is given as:
In(R) In(C) + In(A BTC B)
(15)
Note that,
2 [Xw y) " (Xw yy
1 [Xw - y) diag( (Xw y)z*1)
(w) - (*)
Then the following holds true by applying equation (LL))
(n(A) =In(-diag( (Xw y)z + In( ? [Xw y) T2
7 -[x y)
n1
(-diag( 2 (Xw y)z 1 - Xw y)) n
71
Notice that the term 2 (Xw T)* 2 [Xw {- 2 (Xw: -y)=*))-12 (Xw: y)) evaluates to O. Thus, it has 0 positive eigenvalue, 0 negative eigenvalue and 1 zero eigenvalue. We have also shown Lemma & that has least 1 zero eigenvalue. follows that
2xxw x (A) = π diag( 2 (Xw- - -))z*)), v(A) = r<( r(-diag((" (Xw y)z*T)
n
n
(16)
? (Xw - y)2* +
(A) = 8( diaga
n
Next, we will show that diagg( (Xw- T)z* has all of its eigenvalues being positive.
Lemma 7. For given | h(n), all eigenvalues of -diag( (Xw y)z*T) are strictly greater than O with probability at least 1 exp( 8(p"h(m²- + log
7²
Proof. Using equation (.) we can expand the term -diag (Xw - T) as diagg( 1 (X(w w*) 7z" -------- 1) Since eigenvalues of a diagonal matrix are its diagonal elements, we focus on the i-th diagonal element of -diag( ? (XA 72* e)z*T) which is
C ez). Note
that (XT + e;) is a sub-Gaussian random variable with parameter A + oē. Using the tail
inequality for sub-Gaussian random variables, for some > O, we can write:
P(X.A + +e,) exp( 2
We take union bound across all the diagonal elements and replace = - and DA)z & h(n) to complete the proof, i.e.,
72
P(l [m], (X, + o.) > t) & nexpp 8(p2h(n)2 02)
(17)
The result of Lemma f follows directly from Lemma M and equation (L.)
Now, are ready bound | Due to our primal dual construction, |A is simply equal to |Al| We provide a bound on As in the following lemma:
Lemma 8. If Assumpttions and hold, An >
log 128pky/oogd and n Q 72(Cmin.P.k)) then |As & on
2 with probability at least - ( where 72 p. k) is a constant independent of s, d or Cmin
By taking ((())= =
2h vB in we get the following: F(eig,(A) > 0) > 1 as long as Cuain
n = S2( (s(Comm,p.kkka..) above results combined with the property that optimization problem (6) is invex ensure that the setting of primal and dual variables in Theorem II indeed the globally optimal solution to the problem (.). It remains show that this solution is also unique.
x3 Poog
where ra(Cmin> k, a, 7) is a constant independent of s, d and n. The

---

4.7 Uniqueness of the Solution
First, we prove that Z* is a unique solution. Suppose there another solution Z which satisfies all KKT conditions and is optimal. Then. 2 2 02+1x=+1 and (A, Z) = O. Since. A 2 0 0n+1x=+1 and eig)(A) > 0, S* spans all of its null space. This enforces that Z is a multiple of z But primal feasibility dictates that dZag(()
1. It follows that Z Z To show that vi is unique, it suffices to show that üys is unique. After substituting
Za, we observe that the Hessian of optimization problem (8) with respect to w and restricted to rows and columns in S, i.e. Hss is positive definite. This ensures that w is unique solution.
The setting of primal and dual variables in Theorem not only solves the optimization problem but also gives rise to the following results:
Corollary 1. If Assumptions B and Q hold, X, 3 128pk Alg d and n 2 log
(, E.p) then the
following statements are true with probability least 1 (
1. The solution Z correctly recovers hidden attribute for each sample, i.e., Z = 7 C*(
2. The support of recovered regression parameter w matches exactly with the support of w".
3. If minss |
42. ve then for all i [d]] wi and w match up to their sign.
Cmin
Experimental Validation
Synthetic Experiments. We validate theoretical result in Theorem M and Corollary 0 by conducting experiments on synthetic data. We show that for fixed s, we need n = 10 log samples for recovering the exact support of w* and exact hidden attributes Z*, where 8 = ((s, Cmin. az o, p. k) is control parameter which is independent of d. We draw e Raxd and e E R from Gaussian distributions. We randomly generate w* Rdd with 8 = non-zero entries. Regarding the hidden attribute 2* {11,1)" we set 2/2 entries as +1 and the rest as -1. The response y E RR generated according (I). According to Theorem MI the regularizer A,,
chosen to be equal to 128ph vlogd We solve optimization problem (G) by using an alternate opti- mization algorithm that converges to the optimal solution (See Appendix for details). Figure A shows that our method recovers the true support we increase the number of samples. Similarly, Figure shows that as the number of samples increase, our recovered hidden attributes are 100% correct. Curves line up perfectly in Figure AF and Rd when plotting with respect to the control This validates our theoretical results (Details Appendix M).
a parameter B log log d
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 Q
C-00
233
Shader of Sareries
100
Ocarrd
1.2
(a) Recovery of vs n
(b) Recovvery of S vs 3 (c) Recovery of * vs m (d) Recovery of Z vs B
Figure 2: Left two: Exact support recovery of n** across 30 runs. Right two: Exact hidden attribute recovery of * across 30 runs.
6 Concluding Remarks
In this paper, we provide 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 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 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, 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 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 apply fairness algorithms real world data where the validity of technical assumptions cannot be easily verified. As with any algorithm in prior literature (Calders 201:: Agarwal, 2019, Fitzsimons, 2019, Herk, 2012; Chzhen 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 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 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 silver bullet to justify fairness socially significant contexts.
2020.
Acknowledgments and Disclosure of Funding
This material is based upon work supported by the National Science Foundation under Grant No. 2134209-DMS.
References
Agarwal, A., Beygelzimer, A., Dudik, M., Langford, J., and Wallach, H. A reductions approach to fair classification. International Conference Machine Learning, 2018.
Agarwal, A., Dudík, M., and Wu, Z. Fair regression: Quantitative definitions and reduction-
algorithms. International Conference on Machine Learning, 2019.
Backurs, A., Indyk, P., Onak, K., Schieber, B., Vakilian, A., and Wagner, T. Scalable fair clustering. In International Conference on Machine Learning, pp. 405-413. PMLR, 2019.
Ben-Israeh A. and Mond, B. What is invexity? The ANZIAM Journal, 28(1):1-9, 1986.
Bera, S. K., Chakrabarty, D., Flores, N. J., and Negahbani, M. Fair algorithms for clustering. Neural Information Processing Systems, 2019.
Berk, R., Heidari, H., Jabbari, S., Joseph, M., Kearns, M., Morgenstern, J., Neel, S., and Roth, A. A convex framework for fair regression. ACM International Conference Knowledge Discovery and Data Mining, Workshop on Fairness, Accountability, and Transparency in Machine Learning, 2017.
Brennan, T., Dieterich, W., and Ehret, B. Evaluating the predictive validity of the compas risk and needs assessment system. Criminal Justice and Behavior, 36( 36(1):21-40, 2009.
Calders, T., Karim, A., Kamiran, F., Ali, W., and Zhang, X. Controlling attribute effect in linear regression. 2013 IEEE 13th international conference on data mining, pp. 71-80, 2013.
Chen, X., Fain, B., Lyu, L., and Munagala, K. Proportionally fair clustering, In International Conference on Machine Learning, pp. 1032-1041. PMLR, 2019.
Chierichetti, F., Kumar, R., Lattanzi, S., and Vassilvitskii, S. Fair clustering through fairlets. Neural Information Processing Systems, 2017.
10

---

Chzhen, E., Denis, C., Hebiri, M., Oneto, L., and Pontil, M. Fair regression with wasserstein barycenters. Neural Information Processing Systems, 2020.
Corbett-Davies, S., Pierson, E., Feller, A., Goel, S., and Huq, A. Algorithmic decision making and the cost of fairness. Proceedings of the 23rd acm sigkdd international conference on knowledge discovery and data mining, pp. 797-806, 2017.
Daneshmand, H., Gomez-Rodriguts M., Song, L.., and Schoelkopf, B. Estimating Diffusion Net- work Structures: Recovery Conditions, Sample Complexity & Soft-Thresholding Algorithm. In International Conference on Machine Learning, pp- 793-801, 2014.
Donini, M., Oneto, L., Ben-David, S., Shawe-Taylor, J. S., and Pontil, M. Empirical risk minimiza- tion under fairness constraints. pp. 2791-2801, 2018.
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. Fairness through awareness. In Pro- ceedings of the 3rd innovations in theoretical computer science conference, pp. 214-226, 2012.
Feldman, M., Friedler, S. A., Moeller, J., Scheidegger, C., and Venkatasubramaniinn, Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international confer- ence on knowledge discovery and data mining, pp. 259 2015.
Hanson, M. A. On sufficiency of the kuhn-tucker conditions. Journal of Mathematical Analysis and Applications, 80(2):545-550, 1981.
Hardt, M., Price, E., and Srebro, N. Equality of opportunity in supervised learning. In Advances in neural information processing systems, pp. 3315-3323, 2016.
Haynsworth, E. V. Determination of the inertia of a partitioned hermitian matrix. Linear algebra and its applications, 1(1):73-81. 1968.
Hoffmman, M., Kahn, L. B., and Li, D. Discretion in hiring. The Quarterly Journal of Economics, 133(2):765-800 2018.
Horn, R. A. and Johnson, C. R. Matrix analysis. Cambridge university press, 2012.
Hsu, D., Kakade, S., Zhang, T., et al. A tail incquality for quadratic forms of subgaussian random vectors. Electronic Communications in Probability, 17, 2012.
Huang, L. and Vishnoi, N. K. Stable and fair classification. International Conference Machine Learning, 2019.
Huang, I.,, Jiang, S. H.-C., and Vishnoi, N. K. Coresets for clustering with faimeess constraints. Neural Information Processing Systems, 2019.
Kleinberg, J., Mullainathan, S., and Raghavan, M. Inherent trade-offs in the fair determination of risk scores. Innovations Theoretical Computer Science, 2017.
Kleinberg, J., Lakkaraju, H., Leskovec, J., Ludwig, J., and Mullainathan, S. Human decisions and machine predictions. The quarterly journal of economics, 133(1):237-293, 2018.
Knutson, A. and Tao, T. Honeycombs and sums of hermitian matrices. Notices Amer. Math. Soc, 48 (2), 2001.
Pedreshi, D., Ruggieri, S., and Turini, Discrimination-awan data mining. In Proceedings of the 14th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 560-568, 2008.
Pleiss, G., Raghavan, M., Wu, F., Kleinberg, J., and Weinberger, K. Q. On faireess and calibration. Neural Information Processing Systems, 2017.
Ravikumar, P. Liu, H., Lafferty, J., and Wasserman, L. Spam: Sparse Additive Models. In Pro- ceedings of the 20th International Conference on Neural Information Processing Systems, pp- 1201-1208. Curran Associates Inc., 2007.

---

Ravikumar, P., Wainwright, M. J. Lafferty. J. D., et al. High High-dimensional ising model selection using II-regularized logistic regression. The Annals of Statistics, 38(3):287-1319, 2010.
Ravikumar, P., Wainwright, M. J., Raskutti, G., Yu, B., et al. High-dimensional covariance estima- tion by minimizing 11-penalized log-determinant divergence. Electronic Journal of Statistics, 5: 935-980, 2011.
Subrahmanian, V. and Kumar, S. Predicting human behavior: The next frontiers. Science, 355 (6324))449944 489, 2017.
Vershynin, R. How close is the sample covariance matrix to the actual covariance matrix? Journal of Theoretiaa Probability, 25(3):655-683 2012.
Wainwright, Sharp thresholds for high-dimensional and noisy sparsity recovery using 11- constrained quadratic programming (lasso). IEEE transactions on information theory, 55(5): 2183-2202, 2009.
Wainwright, M. J. High-dimenssonal statistics: non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
Zafar, B., Valera, I., Gonez-Rodriguezz M., and Gummadi, K. P. Fairness constraints: A flexible approach for fair classification. Journal of Machine Learning Reseurch, 20(75):1-42, 2019.
Zemel, R., Wu, Y., Swersky, K., Pitassi, T., and Dwork, C. Learning fair representations. In International Conference on Machine Learning, pp. 325-333, 2013.
Zhao, H. and Gordon, G. J. Inherent tradeoff's in learning fair representations. Neural Information Processing Systems, 2019.
Zliobaite, I. On the relation between accuracy and faimesss in binary classification. Interna- tional Conference on Machine Learning, Workshop on Fairness, Accountability, and Transparency in Machine Learning, 2015.
Calders, Toon and Karim, Asim and Kamiran, Faisal and Ali, Wasif and Zhang, Xiangliang Con- trolling attribute effect in linear regression. IEEE 13th international conference on data mining, 2013.
Berk, Richard and Heidari, Hoda and Jabbari, Shahin and Joseph, Matthew and Kearns, Michael and Morgenstern. Jamie and Neel, Seth and Roth, Aaron A convex framework for fair regression. Fairness, Accountability, and Transparency Machine Learning, 2017.
Agarwal, Alekh and Dudik, Miroslav and Wu, Zhiwei Steven Fair regression: Quantitative defini- tions and reduction-bass based algorithms. International Conference Machine Learning. 2019.
Fitzsimons, Jack and AI Ali, AbdulRahman and Osborne, Michael and Roberts, Stephen A general framework for fair regression. Entropy, 2019.
Calders, Toon and Verwer, Sicco Three naive bayes approaches for discrimination-fiet free classification. Data Mining and Knowledge Discovery, 2010.
Billionnet, Alain and Elloumi, Sourour Using mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem. Mathematical Programming, 2007.
Redmond, Michael and Baveja, Alok data-driven software tool for enabling cooperative informa- tion sharing among police departments. European Journal of Operational Research, 2002.
Cortez, Paulo and Silva, Alice Maria Gonçalves Using data mining to predict secondary school student performance. EUROSIS-ETI, 2008
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Assumptions M1 and soci- etal impact and limitations
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See societal impact and limitations
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] See Assump- tions M. D
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] Code and data are not included but instructions to reproduce them has been included
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section E and Appendix M
(c) Did you report error bars (e-g.. with respect to the random seed after running experi- ments multiple times)? [Yes] See Figure 2
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "lCHyaoVOwul", "reviewer": "Reviewer_jdvv", "summary": "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The topic of this paper is of significant interest to the machine learning community. This framework could potentially shed a light upon a novel strategy for several NP-hard combinatorial problems including learning Bayesian networks, inference in structured prediction, and community detection. The technique is presented well and technically sound. My concerns are listed below -\n\n1. The proposed algorithm aims to solve the regression problem while identifying the bias for each subgroup. I am wondering how the authors attain prior knowledge of the number of underlying subgroups? The paper discussed two subgroups in which case the invexity can be utilized in the optimization as a learning guarantee, but I am wondering if more discussion can be expanded on the real cases when there are more than 2 subgroups with different biases. \n\n2. The proposed algorithm assumes that the linear/nonlinear sparse model is universally adopted among both subgroups, which sounds not realistic. It would be more appreciated to think about certain error tolerance of the model discrepancy among subgroups, while preserving the good property of the model such as invexity. E.g., if the generative model parameters of the two subgroups are w_1 and w_2, respectively, how sensitive the model is regarding the clustering results when w_1 differs with w_2?\n\n3. By using a DAG model, one can formulate the problem with one additional plate as a Bernulli r.v. in the probabilistic graphical model if the solution's uniqueness is not the central concern. Some empirical comparisons such as DAG models can be added to the experiments.\n\n4. I am not sure why the paper has no conclusion, but I would suggest the authors consider do conclude the work, which can give more important insights and discussions on the future direction. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The author's work might have a potential positive societal impact, which is aimed to identify the bias in decision-making in human society.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "24"}, "extra_text": {}}, {"review_id": "f7rHEazq-s4", "reviewer": "Reviewer_iiXG", "summary": "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.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very carefully done from the theoretical point of view (formulation and analysis), with valuable contributions to invex relaxations of combinatorial problems.  I believe such relaxations could be used in other applications as well, e.g. perhaps  for 'mixed liner regression' or related problems.  I really enjoyed both the formulation, and the rich toolkit involved the analysis. \n\nHowever, the application to fairness seems quite problematic, and this is the first paper where I would worry that it may indeed lead to an adverse societal impact.  Experiments and practical implications seem to be an after-thought of the new methodology.  \nI am completely on board with the need to ensure fairness in ML methods, but this paper shows that there is also a real danger of over-reach if such approaches are used without appropriate care or considering practical implications. (Please correct me if you feel I misunderstood the setting). \n\nConsider a generic (sparse) linear regression problem y = X w + noise , where the data was simulated and includes no bias (no gamma*z term).  About half of the training data-points would lie above the predicted y_hat,  and about half would lie below the y_hat.   I believe that if you apply the proposed invex formulation,  it will still find some clustering which will roughly align with under and over predicted points,  and after 'de-biasing' shrink the clouds of points to be closer to linear model model predictions.  My intuition is that if you take a perfectly homogeneous Gaussian cloud of points, and apply a clustering method (say spectral clustering),  these points will still be split into two clusters -- perhaps two semi-circles.  So whether or not there are real clusters -- the method will find them, or in other words, the method will find bias even if there's none.  I'm being overly dramatic here -- but it's basically a first step on the pathway to communism -- where everyone is equal and perfectly predictable by the model.  I could easily imagine how a team from a consulting company (say Accenture or IBM) would use the proposed approach and advise the government of say Kazakhstan or Papua-New-Guinea to detect hidden biases.  Another related issue -- in cases with real bias in the data:  some biases are bad (e.g subjectively prioritizing majority groups over minorities) -- but some biases are good -- say kids who went to a math summer camp vs. kids who watched TV.   So if the latent labels are hidden -- then there may be no way to separate good bias from bad bias.  This also goes into murky ethical waters. \n\nTo be clear, if the data was generated according to the model in (1) with large gamma*z terms,  i.e. where gamma is large enough compared to the standard deviation of the noise term,  then the method makes sense, and indeed it should recover both the z_i's and the sparse w.  So what's missing is some statistical significance that shows that the clusters are \"real\".  Also strong claims throughout the paper that the proposed method 'exactly recovers the hidden attribute of each sample' need to be qualified.  There are n observations, and s+n unknowns (non-zero w's and all z's), so in case  gamma is comparable to noise-sigma,  clearly the problem is not exactly identifiable.  This basic intuition is not shared in the paper -- instead it makes assumptions on support, and mutual incoherence, and not relating them to what may make sense (or can in fact be tested) in practice. \n\nOther comments: \n1) The inclusion of debiasing / fairness constraint has no adverse impact on the performance, despite what the rest of the literature concluded.  (last sentence on page 2). As I understand there's no paradox here -- you're just not using the same notion of performance as other papers on fairness.  The usual baseline is || y - Xw||  on biased data (say on training set). Clearly by enforcing constraints this performance (MSE) should get worse.   In your case from what I understand you're using || y - Xw - gamma *z|| as \"performance\" -- which is akin to how well your debiasing would compare to an oracle \"debias\", but not the original MSE with biased data.  \n2) Real data experiments are lacking (none in the main body), and even in the appendix it's unclear exactly what was done and what have you uncovered with z_i's.  \n\nMinor comments: \n1) page 2 \"While ... Lasso ... provides an estimate of the regression parameter vector, they do not fit the model accurately,  as they fail to consider any fairness criteria\"...   I think there's a confusion of accuracy and fairness -- the method may be accurate on biased data,  but unfair,  by making it fair -- it'll be less accurate on the original (biased) data. \n2) \"our method recovers the exact hidden attributes for each sample and thus provides an exact measure of bias between two different groups\".   I'd suggest adding some qualifiers to such strong statements.  \n3)  You should explicitly mention whether X and z are allowed to be correlated in the model description on page 3.  \n4) We will assume that as the number of samples increases the noise in the model gently decreases.   Why does this make sense (beyond a mathematical convenience for proofs)? \n5) You make support assumptions on w -- but in reality w's are never exactly sparse -- more likely near-sparse, say like power law.  Do your proofs still hold? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No -- from what I understand the paper goes into dangerous ethical territory.  Please see main review.  I would advise to think about less mathematically savvy practitioners who may use your method, and devise statistical tests to check if the discovered bias is real or not. ", "review_text": "", "extra_scores": {"needs_ethics_review": "Yes", "ethics_review_area": ["Discrimination / Bias / Fairness Concerns", "Inadequate Data and Algorithm Evaluation", "Inappropriate Potential Applications & Impact  (e.g., human rights concerns)"], "time_spent_reviewing": "4"}, "extra_text": {"ethical_concerns": "Please see the main review.  From my understanding the proposed method will always detect hidden bias (whether or not there is one in the data) -- and there are no suggestions for statistical tests to check if it's real. "}}, {"review_id": "6BIaMVzHII", "reviewer": "Reviewer_muDS", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is generally well written. The use of the invex relaxation method for solving the inverse problem is novel. The authors also prove that the sample complexity of the invex relaxation method is logarithmic in terms of the dimension of the regression parameter vector. They also provide sufficient details of their methods, including the technical proofs, the alternating minimization method, and the experimental details. I believe that the proposed method could be applied to other combinatorial problems and continue to be useful.\n\nHowever, I have a few concerns.\nW1. The proposed invex relaxation method could be of theoretical interest only since it requires solving an SDP problem which could be a daunting task since its computational complexity is very high. \nW2. The number of samples and dimensions of the data set used in the experiments are too small. For example, they only consider n<500 and d<1000 in the experiments.\nW3. The CPU time spent for solving the invex problem is not reported.\nW4. The authors do not compare their method with other convex or nonconvex relaxation methods in their experiments.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "5Y1g9ogHyPJ", "reviewer": "Reviewer_SRWv", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: \n\nThe proposed method differs significantly from previous approaches as it assumes no direct access to the sensitive attribute in the data. Instead, the bias depends on a hidden attribute. For this new setting, it proposes a novel optimization problem which is then relaxed into an invex optimization problem. Previous work is discussed and cited adequately.\n\nQuality: \n\nThe claims of the paper are well supported. First, the paper shows theoretically that the pair of primal-dual witnesses correctly recovers the hidden attributes and with high probability yields a parameter vector with the correct support. Those theoretical claims are then again validated experimentally on synthetic data. Finally, on two real-world data sets it is shown that the method also works in practice and can be used to recover groups with bias.\n\nClarity:\n\nThe paper is clearly written and generally well-organized. By nature, the content of Section 4 is more technical and therefore a bit harder to read. However, the authors do a good job in organizing it in different subsections so that it can be followed easily. On the downside, while the paper contains the presentation of the approach and the proof of the optimality of the obtained solution, the description of how to actually solve the optimization problem is delegated to the supplementary material (Appendix K). The paper could be more self-contained by delegating parts of the proofs in Section 4 to the appendix (while keeping the general structure and outline of Section 4) and filling up the gained space by an abridged version of Appendix K.\n  \nSignificance: \n\nThe problem of fairness is an important topic since there are a wide range of applications where it is important to avoid biased decisions. The paper makes an important contribution to the field by considering the scenario where there is a hidden biased attribute. Additionally, the topic of invexity has recently gained some attention in the community. For these reasons, the paper will likely be of interest to the community. \n\n---\nAfter rebuttal:\n\nI have read through the responses by the authors as well as the feedback of the other reviewers. I now believe that the ethical concern raised by reviewer iiXG as well as the ethics reviewers is justified. However, I believe that these concerns can be sufficiently addressed if the authors add a section discussing the societal and ethical implications in the paper, incorporating the changes proposed by the ethics reviewers. Therefore I will keep my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss the assumptions made and therefore the limitations of the given approach in Section 4. There is no negative societal impact of the proposed work.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this work, the authors consider the problem of learning a fair sparse linear model when the sensitive attribute is binary and unknown. They establish that the solution of an invex optimization problem can recover both the correct support of the regression coefficients and the hidden sensitive labels. This problem and solution is of interest to the ML community as a variant of the generally important question of learning fair models that will be particularly apt in certain applications where the sensitive attribute is unknown.
Decision: Accept (Spotlight)