Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work studies learning fair classification under the assumption that an arbitrary eta-fraction of training samples are perturbed on the protected attributes. The authors propose an optimization framework for eta-Hamming model which has the provable guarantees on accuracy and fairness. The experiments with linear models on synthetic and real-world datasets are used to evaluate the proposed approach. 
main_review: Originality: The problem setting of this paper is a bit different from existing ones, that is the eta-fraction of perturbations are arbitrary. The main thought of the techniques seems  inspired by Richard 1950 that has been properly cited.

Quality: I am not knowledgeable enough to check the correctness of every theory result, so I can only basically understand what each theoretical result is used for.  By reading the whole paper, I have the following major concerns:
1. The authors claim their results extend to the case of perturbing both labels and features. This leads me to think about the connection between the proposed setting and eta-fraction over training sample labels. Is the latter one an alternative assumption for learning fair classifier?
2. I know targeting the worst-case adversary makes a strict guarantee on theory. However, for a real case the perturbation type is not known. From this view, should expectation formulation is a better choice for the generalization consideration?
3. I found that eta is a small value in experiments to ensure the optimal fair classifier. For works that are dealing with noisy feature/label, eta might be bigger than used in this work. Back to the setting, when and why is a small proportional perturbations for adversary reasonable?

Clarity: The submission is clearly written and well organized. 

Significance: The theoretical results are interesting, while the experimental results seem only comparable. Generally, as the problem setting is not identical with the existing ones,  some modified methods are applied as baselines. But it is fine with me. 

limitations_and_societal_impact: The authors have discussed the limitation of their work, but the further explanation about the above concerns are also needed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents an optimization framework to learn fair and accurate classifiers in the setting where an adversary can perturb the protected attributes. The contribution is mainly theoretical and focuses on Theorem 4.3, which gives guarantees on fairness and accuracy from a solution to their ErrorTolerant program, along with additional impossibility results (4.4, 4.5) which provide tightness and optimality guarantees for the proposed approach. There are also results from a small set of experiments on one simulated and one real dataset showing that the proposed approach generally outperforms baseline methods under the perturbation model.

**Update**: I have read the author response, and it addresses my concerns. Looking at the other reviews and the responses as well, I will keep my initial rating.
main_review: Overall: In general, while the paper is somewhat dense and covers a lot of ground, I found it to be a solid contribution to a problem of great relevance to the community -- versions of this particular problem has the potential to arise in many applied contexts. The paper is generally well-written and the theoretical contributions are made clear enough. I think that the paper could use some reorganization, but absent an issue with the proofs (which I was only able to briefly review) I think there is a good case for acceptance. Detailed comments are below.

Major Comments:

* In general, I found the paper difficult to read at times due to the confusing order of presentation. Many terms are used far in advance of their definitions, and the authors refer to definitions (such as 4.7) many pages before they are introduced. I would suggest to introduce all definitions earlier in the paper, in particular, and to introduce the model itself earlier as well. This will make it much easier to assess the contribution and understand what some ambiguous terms (such as "error") mean when used in context.

* The prior work section is also particularly difficult to read, since the authors mostly focus on immediately defending their territory relative to prior works. Please clearly describe the contributions of these prior works *separate* from your discussion of how the current work is different from them. 

Minor Comments:

* The authors' claims about the fragility of imputation methods on L32 seem to me to assume a very specific imputatoin strategy (namely, one based on deep learning). This is certainly not the case for all imputation strategies, such as mean/mode/constant imputation which are sometimes used in practice. Please clarify your claim, or perhaps soften it.

* I am not sure whether SR is ever actually defined in the paper.

* It isn't clear from my reading how the authors actually find the solution to Program ErrTolerant in practice; it would be useful to comment more on how to solve this problem and give more details regarding complexity of this solution, particularly in the sections with experimental results on actual datasets.

Typos etc.

There are several minor typos in the paper; I only list a few here.

* L39: the distribution of --> the distributions of
* L70 -- could "performance" simply be error?
* L80-82 incomplete sentence
* L103: as measured \Omega --> as measured by \Omega
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors study fair classification in the presence of an adversary who is capable of choosing an arbitrary-fraction of the training samples and arbitrarily perturbing the corresponding protected attributes. Theoretically, the authors propose an optimization framework to learn fair classifiers with provable guarantees on accuracy and fairness in the adversarial settings. Empirically, the authors evaluate the classifiers produced by our framework for statistical rate on real-world and synthetic datasets against different adversaries. 

main_review: 
Overall, I think the paper is well written and the theoretical results are solid and impressive. The proposed problem setup is also important and practical. Assumption 1 also sounds reasonable to me. 

However, there exists some problems in the empirical evaluations. First of all, I think the author should provide more justifications in the synthetic experiments. For example, I think the experiment results would be more convincing if the sizes of the protected group are varied by the authors. Besides, more different values of fairness constraint $\tau$ would be more convincing. 

Moreover, if the authors could add one more dataset in the empirical evaluation, such as the Adult dataset, which has more data instances than COMPAS, the results would be more convincing.

limitations_and_societal_impact: The authors have described the limitations of the work and discuss the potential negative societal impacts.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: They consider the problem offFair classification in the adversarially perturbed setting — that is, the adversary gets to choose eta fraction of the sample arbitrarily and change their protected attributes arbitrarily. 

They show an optimization problem that ensures fairness and accuracy guarantees under a mild assumption and show a mild assumption is necessary for those guarantees. 

Finally, they have some experiments in which they consider two well thought out adversaries.
main_review: To my knowledge, this is the first paper that considers fair machine learning with a full adversary that can arbitrarily corrupt the protected attributes of the data unlike previous work that focused on stochastic corrpution. 

The solution that the paper proposes is pretty intuitive and hence, it's very easy to follow. For instance, the overall paper is very clear in its description of the problem and its explanation of the solution/proof techniques (e.g. at the end of section 4). 

However, the paper only shows an optimization problem that has nice guarantees (Thm 4.3) but doesn't actually show how to solve the optimization problem. More specifically, there isn't a discussion on how to actually solve ErrTolerant regardless of whether it's just a heuristics to solve the problem or an actual algorithm with guarantees. At a glance, the constraints seem convex so one can replace the objective term with a surrogate loss and use any convex optimization approach? In the experiment, it seems that the authors have "solved" ErrTolerant, so some discussion on how to solve and how they were solved in the experiment would be helpful.

Finally, the experiments do show to some extent that the proposed method in the paper is better or observe similar performance as other methods. However, I do have some questions:

-For the synthetic dataset set, why are other methods besides CHKV not tried out? Is it because it's hard to tune the parameters of the other algorithms to have a meaningful comparison?

-I think the easiest way to compare fair-accuracy tradeoffs is by drawing out the pareto curve, so is it possible to just try out much larger sets of parameters for all these algorithms to see a bigger pareto curve instead of the current one that seems to concentrate on a small region? 

Questions/Comments on the impossibility results (Thm 4.4, 4.5, and D.1)
-Are the proofs of the impossibility results specific to SR or can one easily generalize the proofs to other fairness metrics? 

-Maybe, because it's hard to parse the sentence in line 265 (when eta/gamma is small ... ), it's not clear to me how Thm 4.5 shows that the constants in Thm 4.3 are tight. It would be helpful to have a couple more sentences showing how they are tight.

-Lastly, how dependent are the proofs of Theorem 4.5 and D.1 on tau=1 which requires the fairness metric is exact for any group? 





Minor questions/comments:

-Delta = O(blah, blah, blah). Is this supposed to be max with constants hidden? 

-definition 4.7 (stability definition) is has not quantified the high probability. 

-For adversaries in the Empirical results section A_TN and A_FN, how was f^* obtained? 

Typos:
line 265. It's hard to understand what this sentence is saying because I think it's a run-on sentence?
line 270: learnable ⇒ learn
limitations_and_societal_impact: Yes, the authors have addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: This paper provides novel theoretical results regarding fair classification in the presence of adversarial perturbations of the training examples, as well as supporting experiments on real world datasets. The reviewers found the problem formulation to be well motivated by application, and they deemed the theoretical results to be sound, novel, and interesting. Therefore, I recommend acceptance of the paper.

Throughout the discussion there are a number of concerns that should be addressed in the next version of the paper, and I strongly encourage the authors to do so. To name a few: (1) definitions and terminology should be defined early and clearly, (2) the additional experiments discussed in the responses should be added to the paper, and (3) the implementation strategy of solving the proposed programs in practice should be described clearly for the paper to be self-contained.
Decision: Accept (Poster)