Fair Bilevel Neural Network (FairBiNN): On Balancing fairness and accuracy via Stackelberg Equilibrium

Summary

The authors propose a bi-level optimization approach to simultaneously optimize a performance and a fairness loss. They show that this approach is, in theory, superior to a typical approach that regularizes the performance objective with a fairness objective. Using tabular, graph and vision datasets, they demonstrate the Pareto frontiers obtained by their method, compared to multiple (mostly regularization) baselines.

Strengths

Regularization and adversarial training can be difficult to perform in practice, as the choice of hyper-parameters needs to be performed with care and convergence might not be guaranteed. By leveraging bi-level optimization, the authors provide a novel perspective on the problem (to the best of my knowledge).

Weaknesses

While I found the idea interesting, I found that the paper lacked clarity, and have a few major comments / concerns at this stage. **Major concerns** - I found that there were many assumptions made, basically requiring that all parameters are smooth, change at a limited rate and improve compared to prior steps. While some of these might be reasonable, the paper lacked a discussion of what these assumptions mean, and in which conditions they might not be respected. - I am not convinced by Theorem 9 and its proof, as it relies on two functions but DP is computed on a single function (see below). - I found that the connection between the theory and its implementation is not well detailed and explored. - To me, discussing works that perform constrained or multi-objective optimization of hyper-parameters, or refer to meta-learning for fairness would be relevant. - Practically, I see multiple obstacles to the adoption of the proposed method: more hyper-parameters to select, published models cannot be re-used, only one fairness constraint is considered, ... These are not discussed or acknowledged. **Detailed comments**: - Related works: I believe the works who perform the multi-objective or constrained optimization of model’s hyperparameters (e.g. Perrone et al., 2020, https://arxiv.org/pdf/2006.05109 and many others) should be discussed, and potentially considered as baselines. While I understand they do not provide the same guarantees, they are easier to implement. - Can the authors discuss their approach with e.g. Slack et al., 2019 (https://arxiv.org/abs/1911.04336), in which the 2 objectives are separated into learners and a meta-learner instead? - The related works section describes some related works with one sentence, but does not “group” them into the different avenues they represent, or how they differ from the proposed approach. I would suggest trying to “analyze” the field at a higher level and show what the proposed approach can bring. - Overall I found the methodology section dense and not easy to follow. The assumptions are also not discussed, simply enumerated and it is unclear how realistic they are. - The experimental baselines seem to encompass multiple techniques, but are not well described. It is unclear how each of these compares to the proposed approach. - For the Health dataset, as well as for other datasets (in Appendix), the theoretical results do not seem to hold. This is briefly discussed at the end of the results section, but is a clear limitation of the work. There is also little description of whether the selection of hyper-parameters is more complex for the bi-level case. - Relatedly, this is presented as an advantage but to me is a weakness of the approach that the architecture needs to be completely revised to include fairness layers. This means that published models cannot easily be reused, and that the whole process needs to be re-trained for a different fairness constraint.

Questions

- Line 550: how can ensure that $\hat{\theta}_p$ is closer to the optimum than $\theta_p$? Strict improvement at each step seems like a strong assumption to me. Shouldn’t this be spelled out as an extra assumption? - How does the assumption of “sufficiently small” $\eta$ maps to the practical implementation, as we do not know the Lipschitz constant? - Similarly, how about the assumption in Theorem 9 of an overparameterization? - Line 212, DP: why use $\theta_1$ and $\theta_2$? From Assumption 3.10, it suggests that these represent the parameters for $x_1$ and $x_2$. However, the parameters $\theta$ when computing DP are the same for $a=0$ and $a=1$. I don’t see how we can guarantee that the network’s activations are Lipschitz continuous unless we also make assumptions of the distance between input examples (which can be difficult to estimate). The proof also refers to 2 functions $f_1$ and $f_2$, but we have the same function, only different subsets of inputs $x_{a=0}$ and $x_{a=1}$. Can you clarify please? It is not clear to me how the proof shows that DP is Lipschitz continuous. - The discussion seems more like a brief summary with a rebuttal paragraph, rather than a proper discussion. The work is not put in perspective with the literature. - Figures 4 and 5 in Appendix: the proposed method is not strictly better compared to the baselines in all cases. Is there a pattern of failure cases? **Minor**: - Line 64: is the comment pointing towards distribution shifts in the test data? It is unclear what “depends on the data” means. - “Paractical” line 198 - $\hat{\theta}$ is not defined in Assumption 3.3. - Equation (1): the description uses the ‘p’ and ‘s’ subscripts while the equation uses ‘a’ and ‘f’. Please correct. - Is Assumption 3.10 a repeat of definition 3.1? - Line 276: end with “shows”, I am assuming something is missing. - Line 545, equation 38: shouldn’t it be $\phi$ instead of f? - Table 4 (Appendix): it looks like FairGAT has smaller delta EO and should be highlighted instead. Overall, I’d suggest highlighting all results within the standard deviation of each other, as it is a bit misleading otherwise.

Rating

5

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors describe as “NA” the limitations of their approach. I strongly believe that all methods have limitations and these should be discussed. - For instance, multiple assumptions are made, but not discussed. - It is also unclear how the practical implementation reflects the theoretical results, as it would be reasonable to expect effects of finite sample size, the hyper-parameters selected for each of the fairness / performance layers, … - Are any common activation functions not Lipschitz continuous? What about ELU, or other fairness criteria? What would that mean for the derived results?

Summary

The paper proposes and justifies a bi-level optimization approach to optimizing empirical risk minimization objectives when additional fairness constraints need to be considered. Using assumptions of Lipschitz continuity and local convexity, they prove that a bi-criteria (accuracy + fairness) problem is equivalent to bi-level optimization. Key to their approach is to having separate parameters for fairness and accuracy. Practically, accuracy and fairness layers are made for neural networks. Extensive experiments are done.

Strengths

- The paper provides a nice motivation for considering bi-level optimization over the typical fairness regularization approaches. - Theorem 3.9 is nice to show that the Largrangian approach (under certain conditions) is an upper bound of the bi-level approach. - Experiments seem promising and extensive.

Weaknesses

- Missing experimental details. Compute time of baseline and approaches not presented. Neither is the number of parameters used in each approach. Additionally, some approaches / baselines in the appendix aren't well specified, eg, FairGAT and FairGCN. - The convexity assumption does restrict the theory. - Two separate sets of parameters are required. This limits Theorem 3.9's relevance to the typical fairness regularized cases.

Questions

1. What is the compute time of approach? Does the bi-level optimization approach take longer? How do the number of parameters compare? Basically, I am wondering if due to the separate set of parameters needed in the bi-level optimization, the proposed approaches architecture has a larger number of parameters than the baselines. (and if so, would increasing parameter sizes of other approaches increase fairness) 2. What does the overparameterization condition in Theorem 3.9 mean? I am a bit confused about why its needed in Line 186 / 187.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Adequate.

Summary

A common approach to bias mitigating in machine learning is to add a regularization term to the loss function that penalizes deviation from fairness. This is what the current paper calls the Lagrangian approach. It has long been know that this is not an effective approach to multi-objective optimization. The paper proposes to use bilevel optimization to tackle this challenge.

Strengths

The paper addresses an important problem in machine learning fairness. Rather than devising a novel fairness metric as is often the focus in this field, this paper studies a more fundamental problem: how do we get solutions on the Pareto front? The technique employed, bilevel optimization, has not been previously applied in this context, to the best of my knowledge. (However, I did not get a good understanding of the history of bilevel optimization from this paper.) The method, as presented in Algorithm 1, is alluringly simple.

Weaknesses

The following identified weaknesses could be due to my own misunderstanding: *I could not understand how one would decide on which are accuracy parameters and which are fairness parameters in a neural network architecture. I could not find guidance on this in the paper. *Except for the simplest types of neural networks, I can't see how a general neural network can satisfy Assumption 3.4 *Where does bilevel optimization sit in the larger context of multi-objective optimization techniques? I think this needs to be explicitly spelled out.

Questions

*Line 51: "we introduce a novel method that can be trained on existing datasets without requiring any alterations". Is this an accurate characterization? There certainly is a modification to the training algorithm? *"Leader-follower" terminology: is this standard in bilevel optimization? Can you add some references? *In assumption 3.3, $\hat \theta_s$ appears to be undefined *Could you give some example of common activation functions that are Lipschitz continuous? This would help the reader understand how realistic Lemma 3.5 is for common activation functions. *Line 208: "demographic loss function of given layers..." what do you mean by "of given layers"? *Is there an equivalent of Theorem 3.11 for other fairness metrics considered in your paper? Like equal opportunity? or Equal odds? *Line 219: "in practice, the model $f$ can be implemented as a neural network with separate layers for accuracy and fairness". This is one of my main confusions about the paper. How does one decide which layers are accuracy layers and which ones are fairness layers? Some of your experiments concern NNs with just one hidden layer, so then which are accuracy and fairness layers there? *Line 298: "The theoretical analysis, particularly Theorem 4.6, establishes the properties of the optimal solution under certain assumptions, which are not limited to specific datasets or network architectures." I could not find Theorem 4.6. I also think your theoretical analysis is very limited due to the lipschitz continuity assumption. Most NNs used in practice woudl violate this assumption?

Rating

5

Confidence

3

Soundness

2

Presentation

3

Contribution

2

Limitations

I would appreciate a further discussion on the limitations of the theoretical analysis. In particular, I believe the theory is highly limited in terms of the type of NNs it can be applied to.

Summary

This paper proposes a novel bilevel optimization framework called FairBiNN for addressing bias and fairness issues in machine learning models while maintaining accuracy. The approach formulates the problem as a Stackelberg game between accuracy and fairness objectives, proving that it yields Pareto-optimal solutions under certain assumptions. Theoretical analysis shows the method performs at least as well as Lagrangian approaches. Experiments on tabular, graph, and vision datasets demonstrate competitive or superior performance compared to state-of-the-art fairness methods in balancing accuracy and fairness metrics like demographic parity and equality of opportunity.

Strengths

1. Proposes a novel bilevel optimization framework with theoretical guarantees for fairness-aware machine learning. 2. Provides rigorous theoretical analysis and proofs for the proposed method. 3. Demonstrates strong empirical results across multiple domains (tabular, graph, vision) and datasets as shown in both main text and appendix. 4. Compares against numerous state-of-the-art baselines. 5. Conducts thorough ablation studies to analyze different components. 6. Provides clear implementation details and hyperparameters for reproducibility. 7. Visualizes results effectively through plots and t-SNE visualizations.

Weaknesses

1. The bilevel optimization framework may be more complex to implement and understand compared to traditional methods. 2. The theoretical guarantees rely on several assumptions that may not hold in all practical scenarios.

Questions

1. How sensitive is the method to the choice of hyperparameters, especially $\eta$? 2. How does the computational complexity compare to the baseline methods? 3. Are there any scenarios where the method might not perform as well as traditional approaches?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

1. The paper does not explicitly discuss limitations of the proposed approach. 2. Experiments are limited to a few datasets per domain; more diverse datasets could strengthen generalizability claims. 3. The approach is not tested on very large-scale datasets or models

Acknowledging response

I thank the authors for their careful rebuttal and revisions of the manuscript. While I believe that the manuscript would benefit from addressing some of the limitations which are currently mentioned as "future work", I agree that this is a novel and interesting take on fairness and the paper is sound and includes a broad array of experiments. Therefore, I have increased my score.

Keep Score

I thank the authors' response. I think the current response does not change too much of my original impression. I will thus keep my score.

thank you for the detailed response

Thank you for the detailed response. I'm afraid I still find it quite unnatural and confounding to define certain parameters "accuracy" parameters and certain parameters "fairness" parameters. I do not find Figure 3 in the one-page PDF illuminating. It seems completely arbitrary, rather. I would also advise that the authors clearly state that they are not modifying existing architectures. Both Reviewer UWLB (question 1) and the ethical reviewer had the impression that the proposed methodology appends new layers/parameters to existing networks.