Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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. 
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.

However, I have a few concerns.
W1. 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. 
W2. 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.
W3. The CPU time spent for solving the invex problem is not reported.
W4. The authors do not compare their method with other convex or nonconvex relaxation methods in their experiments.



limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

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 -

1. 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. 

2. 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?

3. 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.

4. 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. 
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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: Originality: 

The 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.

Quality: 

The 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.

Clarity:

The 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.
  
Significance: 

The 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. 

---
After rebuttal:

I 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.

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.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.  
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. 

However, 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.  
I 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). 

Consider 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. 

To 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. 

Other comments: 
1) 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.  
2) 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.  

Minor comments: 
1) 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. 
2) "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.  
3)  You should explicitly mention whether X and z are allowed to be correlated in the model description on page 3.  
4) 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)? 
5) 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? 

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_title: null

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)