Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper tries to debias multi-classification models. The proposed method builds on top of the alternating direction method of the multipliers algorithm. It decomposes debiasing multi-classification into a sequence of parallel jobs on each class, followed with an aggregation step. The paper includes experimental results on both synthetic and real-world datasets and found the resultspromising. 
strengths_and_weaknesses: Strengths: 
1. A new way of debiasing multi-classification models.
2. The paper provides both theoretical guarantees and empirical results.
3. The paper explores both classic machine learning models and deep learning models.


Weakness:
1. While we do see that demographic parity is reduced by R2B(the proposed method), the test accuracy also drops, especially when the number of classes is relatively small. This is captured in Figure 2 and Table 1.
2. As pointed out by the paper itself, error parity increases when the dataset has large bias. 
3. The paper may benefit from having analysis on how the proposed method perform differently when models are different (from different families of machine learning models).
questions: Discussed in "Strengths and Weakness" section.
limitations: The paper does emphasize that "fairness" is a societal concept and can not be reduced to statistical metrics. It also discussed the limitations of the proposed method and gives reasonable explanations and potential solutions.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper proposes a reduction-to-binary method, which enforce demographic parity for multi-class classification with non-binary sensitive attributes. It mainly exploits the alternating direction method of the multipliers (ADMM) to decompose the task of debiasing multi-class datasets into a sequence of parallel debiasing jobs. Experiments are implemented on several datasets to demonstrate its effectiveness.
strengths_and_weaknesses: Strengths：
This paper introduces a pre-processing method for multi-class classification with non-binary sensitive attributes with ADMM and experiments are performed to show the performance. In addition, the algorithm are analyzed from different theoretical perspectives.

Weaknesses:
First, the novelty is relatively limited. It mainly extends RTO [1] with ADMM and apply it as a pre-processing method. For example, [2] also exploits ADMM to optimize score transformation for fair classification.  
  
Second, this method is pre-processing method for debiasing multiclass datasets with categorical sensitive attributes. However, some problems are ignored. On the one hand, since the method builds upon the narrow definition of demographic parity, it may not ensure the true fairness [3]. Though this has been discussed in Sec.5 of the paper, fairness is an important motivation for such debiasing work as illustrated in the introduction part. More criterion should be considered. On the other hand, the proposed R2B method does not consider the influences of noisy labels when performing label debiasing.

Further, the experiments are not enough and training settings are relatively simple. For COCO dataset, linear classifiers with softmax activations and cross entropy loss are trained using pretrained features. The total number of examples is 22,616. Such way of training is difficult to demonstrate the effectivity of the proposed method in large-scale datasets when training from scratch is required. As a pre-processing method, more representative models on large-scale datasets should be re-trained to verify the performance.   

[1] Alabdulmohsin I M, Lucic M. A near-optimal algorithm for debiasing trained machine learning models[J]. Advances in Neural Information Processing Systems, 2021, 34: 8072-8084.

[2] Wei D, Ramamurthy K N, Calmon F P. Optimized score transformation for fair classification[J]. Proceedings of Machine Learning Research, 2020, 108.

[3] Wang Z, Qinami K, Karakozis I C, et al. Towards fairness in visual recognition: Effective strategies for bias mitigation[C]//Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2020: 8919-8928.
questions: Please see the weakness part for the novelty, fairness, and experimental comparison in the above comments.  
limitations: Yes.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors introduced a method to extend the current debiasing methods to the multi-class classification problems. The core idea is to formulate the loss function as an L2 regression loss constraint by traditional DP.  Then the optimization problem is solved by ADMM algorithm efficiently; each iteration is only required to solve a binary classification subproblem. The optimality and bound of bias are analyzed. Finally, experiments on both synthetic and commonly used real datasets are conducted to show the reduction in bias while accuracy is sustained. 

strengths_and_weaknesses: This paper is well organized and smooth to read in general, although I found some unclear places (listed in the next section). The idea of transforming the multi-class problem into multiple binary problems is novel and elegant to me. The empirical evaluations are sufficient.

questions: The first limitation of this paper seems to be the loss function itself. Authors choose L2 regression loss instead of the more commonly used cross-entropy loss. This assumption seems critical for applying ADMM. 

Furthermore, I doubt the correctness of the optimality theorem in the paper. It is true that the whole function is strongly convex as a function of yhat, but we are really optimizing over the model parameters in yhat. Even if we consider yhat as free variables, they are constrained by nonconvex set C = DP <= \epsilon. 

There are a few places that are confusing to me:

L140 “Minimizing the expected 0-1 error is equivalent to minimizing the linear…”: I think it should be maximizing the linear functional rather than minimizing.

L148: “the squared loss is statistically consistent”, I checked (Yang et al. 2020), but I can’t find a relevant claim that squared loss is statistically consistent.

L155: “probability of misclassifying an example x equals y^(x)T y(x)”: this should be correctly classifying the example x?

Finally, the format of the tables is ambiguous: the boldface is applied to some (but not all) best methods. For example, in Table 2, only R2B column is highlighted, but other methods are better in DP or accuracy. Similar issue is found in Table 3. In Table 4 there is no boldface in the whole table. So I think efforts are needed to make it more consistent. 

limitations: Please see the section above.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper considers the fairness of the multi-class classification task. The authors reduce a multi-class debasing problem to a set of parallel binary classification debasing tasks for each class label k, followed by an aggregation step. For the binary debias task, they leverage existing method e.g., RTO, to achieve the debiased goal for each label. They apply their debias technique in the pre-processing step: with the "debiased" labels obtained from their R2B method, they compare with some other pre-processing methods in terms of the DP fairness goal and model accuracy. 
strengths_and_weaknesses: Existing literature about fairness usually focuses on the binary classification task, this paper extends this to the multi-class scenario which is a more realistic setting and provides a pre-processing methodology to do this. With their reduction, the algorithm can scale to large datasets. 

While their motivation is important and realistic, it seems to me, the authors just reduce the multiclass problem to a set of binary cases and do an aggregation without further verifying why such an aggregation method works. The aggregation method seems to matter a lot in their method as indicated in the introduction, the normalization could re-introduce bias. However the authors do not mention how their choice can address this re-introducing issue. Also, for the experimental results, it is hard for readers to distinguish between a DP score 5.1 vs 5.0 (e.g., Table 3). 
questions: 1. As indicated above, is there a way to verify why the normalization method in Alg.1 will not re-introduce bias (or reduce that)?
2. For the comparison of the results, e.g, in Fig.2, the DP is in $10^{-3}$ order, then how much difference can we say between your method with other baselines? Is such a difference significant? 
3. For the comparison with other baselines, e.g., with the HTO, what if you did not set the $\gamma$ as the hard-thresholding but follow Alabudulmohsin 2021 to do the grid search? Will your R2B still outperform it?
4. Others:
    - The y-axis in Fig.3 is not correct. The maximum value should be 0.1 (or *1/10 for other values).
    - It will be great if you can introduce a concept before using it in the paper. For example, in the introduction, the authors mentioned "label debiasing" or "debiased label" without defining it, which makes it hard to follow.
 - The $**2$ in $l_2$ distance in #149 seems in the wrong position. 
 - #155: do you mean correctly classifying or misclassifying? 
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposed a novel reduction-to-binary (R2B) approach that enforces demographic parity for multiclass classification with non-binary sensitive attributes via a reduction to a sequence of binary debiasing tasks. It proved that R2B satisfies optimality and bias guarantees. It also demonstrated empirically that it can lead to improvements over baselines and produced competitive results. The authors validated the method on synthetic and real-world datasets from social science, computer vision, and healthcare.
strengths_and_weaknesses: ### Strengths 

1. The paper studies an interesting yet important topic, namely multiclass classification with non-binary sensitive attributes.

2. The paper proposed a debiasing method for multiclass datasets with categorical sensitive attributes. It further established theoretical guarantees for the proposed algorithm.

3. The evaluation was done on real-world datasets from social science, computer vision, and healthcare domains. The performance is notable compared to competing baselines.

4. The writing is clear and easy to follow. The paper is well structured.

### Weaknesses
1. Where does the improvement come from? As the authors noted, potential bias and class imbalance could cause existing algorithms fail for underrepresented data. Yet, no fine-grained results provided for R2B on where the improvements mainly come from. For example, for classes with fewer observations, does it produce more balanced / fair predictions? If so, why is it the case?

2. The datasets evaluated were relatively small-scale. The number of samples and data diversity seem to be limited for the datasets tested. What would be the case when you scale the dataset size up? Without validation on larger datasets, the performance may not be justifiable.

3. No runtime / training cost analysis. What is the additional cost (both time and memory) when introduing the debias procedure?

4. The overall performance was comparable to other algorithms, but no clear advantage. Some of the numbers seem to lie in the noise region. 
questions: Overall, this is a good paper with solid experiments and analysis, and I can see its potential for the broader field.

Please see the weakness part for detailed questions. I paste here some key questions for summary

1. No fine-grained results provided for R2B on where the improvements mainly come from.

2. The datasets evaluated were relatively small-scale. 

3. No runtime / training cost analysis. 
4. The overall performance was comparable to other algorithms, but no clear advantage. 
limitations: The authors have adequately addressed the limitations in the last section of the main paper.
review_title: null

Meta-review: metareview: This paper considers the problem of debiasing multiclass datasets using a reduction-to-binary (R2B) approach for demographic parity as a pre-processing step. This reduction is solved using a ADMM-style algorithm. It offers theoretical analysis of algorithm under some conditions. Experimental results on three datasets show reasonably good results.

All reviewers appreciated the reduction formulation to solve the less-studied problem of debiasing multi-class datasets. They also raised a number of concerns including the narrow problem setting, aggregation of results from reduction, and empirical results. Authors' have responded to those questions/concerns, but only one reviewer followed up and the rest did not. 

Based on my own quick reading of the paper and from reviewer comments, I think the paper needs improvement on the following aspects.
1. The reduction approach is somewhat specific. There is a natural strategy to extend Agarwal et al. (2018)'s approach to multiclass, using the multiclass-to-binary reductions pioneered by Langford et al. (see https://hunch.net/~jl/projects/reductions/reductions.html) This is out of scope of the current paper, but should be mentioned for literature review reasons. The potential benefit is that it can be a sequential reduction that takes into consideration where the classifier is doing well or poorly.
2. As one of the reviewer mentioned, aggregation of results is critical step in reduction style approaches. There is not much detail / intuitive explanation for this in the paper (Line 165-169 doesn't have enough details).
3. Experiments are mostly focused on tabular datasets and non-parameteric classifiers (e.g., Random Forest and k-NN). There is one setting (COCO dataset) where a linear classifer is trained on pre-trained features. One reviewer asked the following question which gets to the core empirical question: "Where does the improvement come from? As the authors noted, potential bias and class imbalance could cause existing algorithms fail for underrepresented data. Yet, no fine-grained results provided for R2B on where the improvements mainly come from. For example, for classes with fewer observations, does it produce more balanced / fair predictions? If so, why is it the case?" I didn't find the authors' response satisfactory. I encourage the authors' to address this aspect if the paper is accepted.
4. The theory which is mostly straightforward states that classifier trained on debiased data is guaranteed to exhibit small bias in future as long as four conditions are met. Two relevant ones for experiments are: a) level of bias in the training data is small, b) there exists a large number of training examples for each group. The paper should have done some ablation experiments to demonstrate what happens when these conditions are not met and how much the results change as these conditions are relaxed. 

For all the above reasons, I think the paper is borderline. I'm leaning towards accepting. If the paper is accepted, I strongly encourage the authors' to incorporate the above feedback in the final paper.
confidence: Less certain
Decision: Accept