Thank you for your thoughtful feedback. We have addressed your questions and concerns below. If you have any further questions, we would be glad to discuss them.

Weaknesses

W1

We appreciate the reviewer's feedback on the assumptions in our paper. In response, we have added a dedicated discussion section in global rebuttal.

W2

Thank you for your comment on Theorem 3.9. We believe there may have been a lack of clarity from our part about its purpose and formulation. The theorem compares the performance of the primary objective between our bilevel optimization approach and the Lagrangian approach, not directly addressing the computation of Demographic Parity (DP). It involves two loss functions (See Fig. 3 in attached PDF): one for the main objective, such as accuracy, and another for the fairness constraint, which may be DP but is not limited to it. The theorem concludes that our bilevel approach can achieve better performance on the primary task under certain conditions compared to the Lagrangian method, while still providing Pareto solutions near local minima.

W3

We appreciate your observation about the connection between our theoretical framework and practical implementation. In response, we have added a section comparing bilevel optimization and Lagrangian regularization, presenting empirical results that validate our theoretical claims and show where our approach excels in balancing accuracy and fairness. We’ve also included a section on how our theoretical assumptions apply in real-world scenarios. While our method yields Pareto optimal solutions under certain conditions, we acknowledge that other methods can also produce different Pareto optimal solutions, and we have discussed the scope of our theoretical guarantees in relation to the broader field of fairness-aware machine learning.

W4

We modified the related work section to position our work better in the literature.

W5

We have addressed several key points in our paper. First, we added a section on practical implementation, discussing hyperparameter selection and its role in providing finer control over balancing accuracy and fairness, along with guidelines for choosing these parameters (See a glimpse of it in the attached PDF, Fig. 1 and 2). Second, we clarified that our method can be applied as a downstream task on pre-trained models, allowing for fairness enhancements without full retraining, as demonstrated with ResNet on CelebA. Third, we discussed extending our method to handle other fairness constraints, with theoretical guidance provided in the appendix. Additionally, we included limitations of our work in global rebuttal.

Comments

The Related Work section was thoroughly revised, categorizing classic multi-objective optimization methods into two groups: common regularization-based methods, including adversarial debiasing, fair representation learning, and Lagrangian optimization, and less common approaches, such as gradient-based methods and transfer and meta-learning approaches. Two mentioned papers were added to the latter group and discussed. The advantages of bilevel optimization were summarized at the end of the section.

Questions

Q1

We provide a theoretical analysis of the neighborhood around local minima in the loss landscape. Due to the convexity of the loss in this area, a sufficiently small step size can lead to strict improvements in the loss. For more details, please refer to item 1 in the assumption discussion in the global rebuttal.

Q2

In practical scenarios, the learning rate is a tunable hyperparameter specific to the task, and the Lipschitz constant is not required for implementation.

Q3

Most modern deep learning architectures satisfy this assumption, as it is met when the network has the capability and parameters to fit all the data. For more details, please refer to item 3 in the assumption discussion in the global rebuttal.

Q4

We apologize for the notation error in the DP definition on Line 212, where $\theta_1$ and $\theta_2$ should represent the same set of parameters for both $a=0$ and $a=1$ . This will be corrected in the revised paper. Regarding the proof of Lipschitz continuity for DP, the proof is correctly formulated, focusing on the difference between DP loss calculated with two parameter sets. Here, $f_1$ and $f_2$ refer to the same function evaluated with different parameters, consistent with DP computation practices $20,on manuscript$ . The Lipschitz continuity being proven relates to parameter changes, showing that small parameter adjustments lead to bounded changes in the DP metric. The proof establishes that if the underlying function is Lipschitz continuous with respect to its parameters, then the DP metric is also Lipschitz continuous concerning those parameters.

Q5

Please refer to the global rebuttal. We will include a comprehensive discussion in the revised paper.

Q6

Our method’s performance varies due to differences in data handling and augmentation techniques used by baselines, which can affect the loss landscape. While it is not universally superior, our approach consistently demonstrates competitive performance across diverse scenarios, underscoring the complex nature of fairness-accuracy trade-offs in machine learning.

Minors

Thank you for your meticulous attention to detail. All minor issues have been corrected.

Limitations

We have added Limitations and future works to the global rebuttal and manuscript.

L1

Please refer to "Assumption Discussion" in global rebuttal.

L2

Thank you for your comment! We have added several ablation studies to the paper. Figures 1 and 2 in attached PDF provide a glimpse of two of these studies.

L3

Yes, Softmax is a key activation function that is not Lipschitz continuous, while ELU and ReLU are. We have also included a theoretical proof of Lipschitz continuity for another common fairness criterion, equalized odds.

Thank you for your thoughtful feedback. We have addressed your questions and concerns below. If you have any further questions, we would be glad to discuss them.

Weaknesses

W1

We acknowledge that some important information was missing from our initial presentation. To address these concerns, we have made the following additions and clarifications:

1. Compute time and parameter comparison: We have now included a detailed comparison of compute time with the same number of parameters between our method and the Lagrangian approach in the global rebuttal. This comparison is particularly relevant as the Lagrangian method serves as our natural baseline, given the theoretical focus of our work.

2. Focus on Lagrangian comparison: We want to emphasize that our primary goal was to demonstrate the theoretical results in practice. As such, we focused our direct comparisons on the Lagrangian method, which is most closely related to our approach in terms of problem formulation. We have now made this focus clearer in our experimental setup section.

3. Other baselines: While we included results from other approaches for context, we acknowledge that a direct comparison of computational complexity or parameter count with these methods may not be fair or meaningful. These methods approach the fairness problem in fundamentally different ways, making such comparisons non-trivial. We have added a note in our experimental section to clarify this point.

4. Specification of approaches in the appendix: We have added proper citations and brief descriptions of all methods mentioned in the appendix to provide better context. This includes FairGAT, FairGCN, and others.

We appreciate the reviewer’s feedback, which helped improve the transparency of our experimental setup and the validity of our comparisons, particularly concerning the Lagrangian method.

W2

We'd like to clarify that our theory doesn't assume convexity of the entire neural network optimization problem, but rather convexity near local optima. We have added a new section to the paper discussing how our assumptions translate to real-world scenarios, which addresses this point in detail. In this new section, we explain that while neural network loss landscapes are generally non-convex, recent research [1] suggests they often exhibit locally convex regions around minima, especially in overparameterized networks. Our assumption of convexity near local optima aligns with this understanding. In practice, this assumption translates to the behavior of neural networks as they converge during training. As long as the network converges, it will likely encounter these locally convex regions along its optimization path. Our theory applies particularly well in these parts of the optimization process. As networks approach convergence, our assumption of local convexity becomes increasingly valid, making it applicable to well-designed models trained on suitable datasets. Practitioners can rely on this aspect of our theory if their models show convergence. The clarification and new section in our paper highlight how our theoretical framework aligns with practical neural network optimization. By focusing on local rather than global convexity, we significantly broaden the applicability of our theory to real-world scenarios.

W3

We appreciate the reviewer's insightful observation regarding the separate sets of parameters and their impact on Theorem 3.9's relevance to typical fairness regularized cases. We'd like to clarify that the number of parameters in both our bilevel approach and the regularization method are the same, and both methods optimize parameters within the network (please see Fig. 3 in attached PDF). This allows for a meaningful theoretical comparison between the approaches. In practice, the separation of parameters into accuracy ($θ_a$) and fairness ($θ_f$) sets in our approach allows for more fine-grained control over the optimization process. This can potentially lead to finding better solutions than single-objective regularization methods, as demonstrated in our experimental results.

Questions

Q1

To address concerns about experimental details, we have enhanced our paper in two key ways. First, we added a new section that directly compares our method to the Lagrangian approach, demonstrating that our method outperforms it with the same number of parameters. Second, we included a comprehensive analysis that examines the computational complexity of both bilevel and regularization training processes (summary in global rebuttal), along with empirical timing results. These additions provide a clear picture of our method’s efficiency and performance relative to traditional regularization techniques.

Q2

The overparameterization condition refers to a scenario where the model has more parameters than necessary to fit the training data perfectly. In the context of our theorem, specifically in lines 186-187, this condition is needed for the following reasons:

1. Flexibility: Overparameterization provides the model with additional flexibility to find solutions that satisfy both accuracy and fairness objectives simultaneously.

2. Existence of Multiple Optima: It ensures the existence of multiple parameter configurations that can achieve optimal performance on the primary (accuracy) objective. This is crucial for our bilevel optimization approach, as it allows the model to choose among these configurations to optimize the secondary (fairness) objective.

3. Theoretical Guarantees: The condition allows us to establish theoretical guarantees about the performance of our bilevel approach compared to the Lagrangian method.

References:

1. Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. Advances in neural information processing systems, 32, 2019.

Thank you for your thoughtful feedback. We have addressed your questions and concerns below. If you have any further questions, we would be glad to discuss them.

Weaknesses

W1

In our approach, the separation of accuracy and fairness parameters is a key design choice that allows for the bilevel optimization. Typically, accuracy parameters ($θ_a$) are those in the main network layers directly contributing to task performance, while fairness parameters ($θ_f$) are in additional layers specifically designed to address fairness concerns. To address this lack of clarity, we have added a new figure to the paper that visually illustrates how accuracy and fairness parameters are typically separated in different networks (Attached PDF, Fig. 3). For instance, in a simple feedforward network for binary classification, the structure might be:

Input -> Main Layers ($θ_a$) -> Fairness Layers ($θ_f$) -> Output Layer ($θ_a$)

The architecture of our approach can vary based on the specific task and dataset, and the separation of accuracy and fairness parameters may not always be straightforward. Practitioners may need to experiment with different configurations to find the most effective split for their use case. This flexibility is a strength of our method, allowing adaptation to various network designs. To enhance clarity, we added an ablation study examining the impact of fairness layer positioning within the network architecture (Attached PDF, Fig. 2), offering insights into how design choices affect model performance and fairness. We appreciate the reviewer’s feedback, which improved the clarity and applicability of our work.

W2

We appreciate the reviewer’s insightful observation regarding Assumption 3.4 and its applicability to general neural networks. While this assumption may initially seem restrictive, we have added a section to the paper explaining how it can be met in practice. Specifically, Assumption 3.4 can be satisfied through common techniques such as:

• Bounded Activation Functions: Many popular activation functions, such as sigmoid, tanh, and ReLU (when combined with proper weight initialization), naturally bound the output of each layer.
• Regularization methods
• Normalization techniques

These approaches are widely used in modern neural networks, ensuring that many architectures inherently satisfy or can easily be modified to meet this assumption without significantly altering their structure or performance.

W3

Thank you for your suggestion! We have modified the related work to place our work better in the existing literature.

Questions

Q1

You are correct that our original statement could have been more precise. We have edited it to ".. without requiring any alterations to the data itself (data augmentation, perturbation, etc)."

Unlike some fairness approaches that require data augmentation or perturbation, our method operates on the original datasets without alterations. This allows for direct application to existing datasets without preprocessing, avoiding additional biases or changes to the data distribution. Our approach focuses on modifying the learning process, not the data, which is a key strength of our method.

Q2

We have added relevant papers and refined the related work section accordingly.

Q3

$\hat{\theta}_s$ represents the updated values of the secondary objective's parameters.

Q4

Great insight! We have added a discussion and examples of different activation functions and layers in the appendix. In summary, Linear, Sigmoid, Tanh, ReLU, Leaky ReLU, ELU, and Softplus are Lipschitz continuous, while Softmax, Hard Tanh, and Hard Sigmoid are not.

Q5

The revised statement now reads: "We showed that the demographic parity loss function, when applied to the output of neural network layers, is also Lipschitz continuous (Theorem 3.10)"

Q6

We know:

$

\text{EO Difference} = \max(\text{TPR Difference}, \text{FPR Difference})

$

Lipschitz constants for true positive rates (TPR) and false positive rates (FPR) can be calculated in the same way as in Theorem 3.10. Therefore, Equalized Odds (EO) possesses a Lipschitz constant, indicating that it is a smooth function.

Q7

We covered this. (Response to W1)

Q8

We apologize for the confusion caused by the incorrect theorem number. There is no Theorem 4.6 in our paper; the correct reference should be to Theorem 3.8. This error has been corrected in the text.

We acknowledge your concern about the limitations of the Lipschitz continuity assumption, as many practical neural networks might appear to violate it. To address this, we have added a section discussing how our theoretical assumptions apply to real-world scenarios, highlighting how neural network design and training practices can satisfy or approximate these assumptions. Additionally, we have included an appendix section exploring the Lipschitz properties of various layers, demonstrating that many commonly used types are Lipschitz continuous or can be modified to be so.

Although the Lipschitz continuity assumption may seem restrictive, our analysis shows that it is more applicable to practical neural networks than it initially appears. Many modern architectures, such as CNNs[1], GNNs[2], and GATs[3], either inherently satisfy this property or can be easily adjusted to do so.

Limitations

L1

We have added limitations and future works to global rebuttal and revised manuscript.

References:

1. Dongmian Zou, Radu Balan, and Maneesh Singh. On lipschitz bounds of general convolutional neural networks. IEEE Transactions on Information Theory, 66(3):1738–1759, 2019.
2. Simona Ioana Juvina, Ana Antonia Neacs, u, Jérôme Rony, Jean-Christophe Pesquet, Corneliu Burileanu, and Ismail Ben Ayed. Training graph neural networks subject to a tight lipschitz constraint. Transactions on Machine Learning Research.
3. Reference [2] in global rebuttal.

Thank you for your thoughtful feedback. We have addressed your questions and concerns below. If you have any further questions, we would be glad to discuss them.

Weaknesses

W1

While our approach may initially appear more complex than traditional methods, we believe its benefits significantly outweigh this drawback. Our experiments demonstrate that the proposed method offers greater training stability compared to common adversarial training techniques in fairness research. The optimization can be implemented through a customized training loop with separate optimizers for accuracy and fairness, which is straightforward in modern deep learning frameworks.

The bilevel framework enhances interpretability by clearly separating accuracy and fairness objectives. This separation allows for more fine-grained control over parameters compared to fairness regularization methods, enabling precise tuning of the trade-off between objectives. This level of control is particularly valuable in sensitive applications where balancing fairness and accuracy is crucial.

W2

We appreciate your insightful comment regarding the assumptions underlying our theoretical guarantees. We have addressed assumptions' discussion in global rebuttal.

Questions

Q1

We have included ablation study in attached PDF (Fig. 1) showing the impact of varying the parameter $\eta$ on the FairBiNN model. The results revealed a trade-off: increasing $\eta$ enhanced fairness but decreased accuracy, with diminishing returns at higher values. This underscores the importance of tuning $\eta$ to achieve an optimal balance between accuracy and fairness, tailored to the specific needs of each application.

Q2

In our paper, we focused our theoretical analysis and direct comparison on the Lagrangian regularization method, as it serves as a natural baseline for our bilevel optimization approach. We'd like to emphasize that the computational complexity of our approach is equivalent to that of the Lagrangian method. Both methods use the same number of parameters and require similar computational resources per iteration. This equivalence in complexity allows for a fair and direct comparison between the two approaches. We have included a detailed theoretical analysis of the computational aspects for both our method and Lagrangian regularization in global rebuttal. Additionally, we report practical execution times for both approaches in our experimental results. These comparisons provide a clear picture of how our method compares to Lagrangian regularization in terms of computational efficiency.

Direct complexity comparisons with other baseline methods are challenging due to their varying approaches to ensuring fairness. By focusing on Lagrangian regularization, we provide a clear comparison of our method’s computational efficiency relative to a similar approach. This comparison highlights the practical benefits of our bilevel optimization framework while maintaining comparable computational efficiency.

Q3

While our approach has shown strong performance across various scenarios, there are indeed cases where it might face challenges or not perform as well as traditional approaches. One notable scenario is multiclass classification, particularly when using softmax activation in the output layer. The softmax function is not Lipschitz continuous, which is one of the key assumptions in our theoretical framework. This lack of Lipschitz continuity could potentially lead to instability in the optimization process or reduced performance compared to traditional approaches in multiclass settings. Also, in non-stationary environments, Our current framework assumes a static dataset. In scenarios where data distributions change over time, the method might require adaptations to maintain its performance.

Limitations

L1

We have added the limitations and future work section in global rebuttal.

L2 and L3

We appreciate the reviewer's observation regarding the number of datasets used in our experiments. We acknowledge that testing on a wider variety of datasets could indeed strengthen generalizability claims. However, our dataset selection was deliberate and constrained by several factors in the field of fairness research.

We chose widely used benchmark datasets that are well-established in fairness tasks, such as UCI Adult and Heritage Health for tabular data, Pokec and NBA for graph data, and CelebA for vision. These datasets allow for direct comparison with existing methods. It's important to note that the number of high-quality benchmark datasets specifically designed for fairness tasks is somewhat limited in the field, posing a challenge for all researchers in this area.

As our primary contribution is a theoretical framework, our main goal was to demonstrate that our theoretical results hold in practice. The selected datasets, covering a range of domains and data types, serve this purpose well. While we agree that more datasets could potentially strengthen generalizability claims, we believe that the diversity of domains we covered provides strong evidence for the broad applicability of our method.

We are actively seeking to apply our method to additional datasets as they become available as part of our ongoing research. We believe our current results, spanning multiple domains and dataset types, provide a solid foundation for the practical utility of our theoretical framework. However, we welcome and encourage further testing and application of our method on diverse datasets by the research community to further validate its generalizability.

Flag For Ethics:

All datasets used in this study are publicly available, and no human subjects were involved in the research.