Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: A popular approach in fair machine learning in-processing methods is to replace the original fairness constraints, which are non-convex and non-differentiable, with surrogates that are easier to handle. This paper studies several of these relaxations. On the one hand, it shows some of their limits by proving sufficient conditions under which existing surrogates may lead to optimization problems where the Lagrangian has no stationary points. On the other hand, it proposes three relaxations that are less prone to this undesirable behavior.
main_review: Pros:
 - The paper is relatively easy to follow
 - Studying the limits of surrogates in fair machine learning is an important problem
 - The paper comes with both theoretical and empirical results

Cons:
 - Some comparison to existing work is missing
 - It remains unclear how fair models can be efficiently found using the proposed relaxations
 - The theoretical results are limited to very specific problems

Detailed comments:
1. Surrogate constraints are an appealing way to enforce fairness in machine learning as they are relatively easy to implement and the resulting constrained optimization problems may be solved efficiently. Unfortunately, these surrogates are often not guaranteed to lead to fair solutions. This paper proposes to study a particular case of failure where the lagrangian of the problem may become arbitrarily small, potentially leading to very sub-optimal solutions. Thus, proposing relaxations that can avoid this pitfall is important.

2. A comparison with the work of Cotter et al., Two-player games for efficient non-convex constrained optimization (2019) is missing. It studies the more general problem of non-convex constrained optimization and proposes an approach based on surrogates in a lagrangian formulation that is very reminiscing of the problem considered here. This approach should, at the very least, be considered as a baseline in the experiments 

3. While it is interesting to exhibit sufficient conditions under which surrogates may lead to degeneracies (Theorem 1 and 2), it remains unclear whether the relaxations will behave well when the conditions are not met. Furthermore, the result seems to be limited to linear models (since the representation is fixed) with a particular family of loss functions. This greatly reduces the interest of the results.

4. Three different surrogates are proposed with the common idea that the indicator function should be relaxed. While the relaxations themselves are not new, for example it has long been known that the sigmoid may be used to approximate the indicator function, the paper gives interesting insights on their particular interest for fairness and gives interesting connections to the existing literature.

5. From the paper, it seems that a critical point to achieve fairness using the proposed relaxations is to correctly choose the Lagrangians parameters \lambda. Unfortunately, the paper does not provide any algorithm to find the optimal parameters in an efficient way (a grid-search is used in the experiments). This might not be trivial in practice and thus slightly reduces the overall interest of the paper. 

Summary of the review:

On the one hand, this paper studies the important problem of surrogates in fair machine learning showing the limits of existing formulations and proposing alternative relaxations. On the other hand, the applicability of the theoretical results remains quite limited. Furthermore, a comparison with the work of Cotter et al., that seems quite close in spirit, is missing. Overall, I think that this paper presents valuable ideas but is slightly below the acceptance threshold.
limitations_and_societal_impact: The limitations and potential negative societal impact of this work were correctly addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study several surrogates for fairness constraints. They show that simple surrogates such as linear can lead to degeneracy. They show that when the derivative of the surrogate does not go to zero as the prediction goes to infinite, we should deal with degeneracy. They show that such degeneracy is not only theoretical and happens on real-world datasets as well for linear surrogates. 
main_review: The authors study several surrogates for fairness constraints. They show that simple surrogates such as linear can lead to degeneracy. They show that when the derivative of the surrogate does not go to zero as the prediction goes to infinite, we should deal with degeneracy. They show that such degeneracy is not only theoretical and happens on real-world datasets as well for linear surrogates. 

The writing can be improved, I had a hard time understanding some parts of the paper! Especially some parts of the paper were really dense and it was hard to understand the main point. 

People usually use the loss function as the surrogate for f especially when working with DNN. So, the proposed surrogates (sigmoid and log sigmoid) are not very novel. However, the thorough analysis of them and showing that they will not lead to degeneracy was interesting!

Minimizing the worst-case group loss (either grouping data points with label and sensitive attribute to achieve EOO or only sensitive attribute to achieve DP) is also a very common technique for fairness application (e..g, group-DRO). (note that we can always randomize the performance of the better group if equality is really the goal!). Do they also have the mentioned degeneracy problems?
I didn’t exactly follow why Agrawal et al. method may fail, I think a better description there would help. 

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study fairness relaxations, especially in deep learning settings. They propose several conditions under which prior fairness surrogates may degenerate. Three new surrogates are proposed further to avoid degeneracy and the performance and stability of the new surrogates are proved by real-world experiments.
main_review: Generally, the authors propose several interesting fairness relaxations and prove the effectiveness both theoretically and empirically. However, more analysis on the theories is needed and the experiment results should be further explained. Meanwhile, the writing of the paper should be improved.

**Pros**

1. Theory part: Theorem 1 and 2 are insightful results and they show that under some conditions, ill-defined fairness relaxations will degenerate. Meanwhile, it is interesting to develop the logistic sum from the logistic difference.
2. Experiment part: Different kinds of datasets are included (both tabular and deep tasks). In addition, several meaningful conjectures are proposed, which may shed light on the optimization of fairness in deep models.

**Cons**

1. Theory part: Theorem 1 and 2 propose the critical points. However, it will be more useful if the authors could discuss the tightness of the critical point. In other words, when will the critical points be small enough so that the relaxations would totally fail and when will the critical points be large? 
2. Experiment part: An important baseline [1] is missing for the DP setting. In addition, improvements over ReLU Difference for the EO setting are not significant.
3. Writing part: The writing should be improved. Some notations are used without explanation (such as $\gamma$ at Line 283) and some notations are introduced in different parts of the paper so that it is difficult to look up (such as $p_{s0}$ and $\mu_{jsy}$). I think it would be better if the authors could provide a paragraph to introduce all the notations solely. In addition, explanations of the experiments on tabular datasets are missing. This may be caused by the space limit but some texts could be moved to the appendix (such as Line 317 to 338).
4. Some small typos:
   - Line 249: "A generalization Theorem 3" --> "A generalization of Theorem 3"
   - Line 342: "to induce cause degeneracy as in Theorems 1-2" --> "to cause" or "to induce"
   - Figure 4 subcaption: "CelebA (EOO)" --> "CelebA (EO)"

**References**

[1] Zafar, Muhammad Bilal, et al. "Fairness constraints: Mechanisms for fair classification." Artificial Intelligence and Statistics. PMLR, 2017.
limitations_and_societal_impact: As shown in the main review part, theory, experiment, and writing could be improved.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper discusses several relaxations for the hard-indicator based fairness measures and compares their fairness-accuracy tradeoffs. 

Detailed discussion on the necessary conditions for the failure case of certain relaxations (like linear or hinge) is provided. When the said conditions are satisfied, it is shown that the method converges to degenerate solutions where improving the fairness measure results in very high loss values of the prediction function. 

Three surrogates are proposed, namely, the logistic sum, the logistic difference, and the sigmoid relaxation. They are shown to be more stable than the linear and hinge relaxations especially in non-convex models. 

Experimental results are provided on tabular, vision and NLP datasets.  
main_review: ## Strengths

The paper identifies that degenerate solutions are not caused not by the failure of KKT conditions but instead because of the conditions discovered in the paper (one of the important ones being the asymptotic behaviour). As demonstrated in the paper, despite \lambda being bounded, the Lagrangian could turn out to be unbounded. 

The logistic sum relaxation offers a means to search for only one parameter ($\lambda$)  instead of two ($\lambda$ and $\tau$). Here, $\lambda$ is the constraint multiplier and $\tau$ appears in DDP $\le \tau$. Varying only the value of $\lambda$ for a feasible solution of the objective function ensures that the tolerance is brought under $\epsilon$. 

It is a strength that the claims of the paper on the degeneracy of current fairness relaxations is supported both by empirical and theoretical evidence (Theorem 1, 2). The experiments support the applicability of the proposed relaxation even in the regime of non-convex models such as deep networks. 

Section 5 offers some valuable insights into the behavior of the relaxations, such as -- despite the similar asymptotic behavior of ReLU and the proposed logistic difference, degeneracy is observed only with ReLU indicating the importance of adopting smooth relaxations. 


## Weaknesses 

Degeneracy is primarily caused by the fairness measure $\Delta_g$ approaching $-\infty$. This happens when the parameters of the model $w$ diverge. This is as per Theorem 1 and 2. A simpler alternative to prevent degeneracy would be to incorporate weight clipping / gradient clipping approaches. It is unclear how such regularization techniques compare against the use of the proposed relaxations. 

The assumption for degeneracy $\delta_g \ne 0$ is weak as only a handful of relaxations, such as max(x, 0) or a linear function, qualify for this criterion. The use of softmax and gaussian functions, with $\delta_g = 0$, as a relaxation has been very common in the literature. Eg., eq (2) in  [1] or [2]. Very few methods in the existing literature have adopted max(x, 0) or linear relaxation, thereby reducing the relevance of the paper within the community. 

To prepare the claims on degeneracy of fairness relaxations, the authors use the inequality constraint $\Delta_g \le \epsilon$ rather than $\Delta_g = 0$ adopted by several prior works (section 3.1 of the paper). It is unclear what motivates this modeling choice. Observe that adopting $\Delta_g = 0$ has an immediate benefit -- it would prevent the failure case where $\Delta_g$ is significantly negative yet the DDP measure is not satisfied.  

The paper misses out on discussing generalization ability of the proposed relaxation techniques. It is well studied [3] that a differentiable surrogate to the indicator function leads to over-constrained objective, causing poor generalization performance. It is unclear if any of the proposed relaxations suffer from such an over-constraining phenomena. It is further unclear how the gap between the training and test accuracies differs across different relaxations. 


[1] http://proceedings.mlr.press/v28/zemel13.pdf

[2] https://arxiv.org/pdf/1412.5244.pdf

[3] https://www.fatml.org/media/documents/training_fairness_constrained_classifiers_to_generalize.pdf



## Comments / Questions

Can the highly unstable training, seen on CelebA and FOTW datasets due to the use of linear relaxation, be reduced by lowering the learning rate of the model?

line 43 in the paper argues that the proposed surrogates are robust to outliers. However, there is no experimental or theoretical evidence provided for this in the paper. Please elaborate or edit the line accordingly. 



limitations_and_societal_impact: Authors have discussed the limitations of their work.
review_title: null

Meta-review: The paper studies the effect of different fairness relaxations in the training of "fair" classifiers. The reviewers point out some limitations of the work, but think that the paper has ideas that could be interesting to the NeurIPS community, and therefore recommend acceptance. The authors are strongly encouraged to incorporate the feedback provide, and in particular, work on improving the writing as suggested by the reviewers.

**Additional comments from AC:**

To Reviewer okm9's comment on comparison to Cotter et al., my understanding of their work is that they propose a Lagrangian-based solver, in which the classifier is optimized using surrogate relaxations, whereas the Lagrange multipliers or costs $\lambda$ are updated using the *unrelaxed fairness constraint*. I think this is reminiscent of how you perform grid search, although when there are multiple constraints (e.g. over large number of protected groups), a simple grid search may not be feasible, and methods such as theirs may be needed. I think it's important to at least have a discussion on this in the paper, and to be explicit about the difficulty of applying grid search with non-binary attributes.

To Reviewer C1h7's question on why the method of Agarwal et al. may *fail* with non-negative costs, I don't think the authors provided a response. I can see why the surrogate relaxations would become non-convex with negative costs, but given that training of deep networks would anyway result in a non-convex problem, would the surrogate being non-convex be all that problematic? As the reviewer suggested, I think it's important to elaborate on why their method may *fail* (which I think is a strong claim).

Finally, a couple of minor comments on the writing from a quick glance:
- In the abstract, you mention that "We propose an easy-to-use and robust way of imposing fairness constraints when training": are you referring to Lagrangian formulation, which I think has already been well-studied in the literature and not necessarily a contribution of this paper, or specifically to the use of grid-search to tune $\lambda$, which unfortunately is not scalable to multiple constraints / protected groups. It might be good to be a bit more specific about what the paper claims to be its proposal.
- In the intro, you mention that "We also provide some of the first empirical results on fair relaxations for large-scale image and
text classification." Is this statement entirely accurate? I do remember CelebA being used commonly in prior fairness papers, e.g. https://arxiv.org/pdf/2004.01355.pdf.

I trust that the authors will put in the time and effort to make a thorough pass over the paper to polish up the writing, and to ensure that the statements made are all precise and accurate.

Decision: Accept (Poster)