Fairness-Aware Meta-Learning via Nash Bargaining

Thank you for the reviewer’s constructive feedback and acknowledgment of our contribution. We appreciate the opportunity to clarify our approach and address your concerns.

W1: Transitioning to Stage 2 and selection of $T_{bar}$.

Thank you for your question! In practice, we determine $T_{bar}$ by monitoring the bargaining success rate. We observed from real-data experiments that the model's performance would stabilize when this rate stabilizes. This may serve as a sign of switching to Stage 2 because no significant improvements could be brought by bargaining. In our real-data experiments, we set $T_{bar}$ to 15 epochs, as this allowed all evaluated settings to reach a stable bargaining success rate. We also want to clarify that $\beta_0$ is also used in Stage 1 when bargaining fails, which would preserve the fairness objectives meanwhile providing a fresh start for subsequent bargaining. We've updated the manuscript to improve clarity and consistency.

W2: Figure 1.b clarification.

The two colors are overlapping. We've updated the figure in our manuscript.

Q2.1: Theoretical novelty.

Thank you for your question! The removal of linear independence in Thm 3.2 is not the only novelty. Compared to previous work [37], our additional theoretical contribution is as follows:

• For Pareto improvement of $\tilde{w}$, Thm 3.6 gives a tighter upper bound for the learning rate than [37]. We require $\eta^{(t)} \le \frac{2}{C K \alpha_j^{(t)}}$ for all $j \in [K]$, compared to $min_{j \in [K]} \frac{1}{C K \alpha_j^{(t)}}$ in [Theorem 5.4, 37]. Our bound is better with multiplicative constant 2. See Line 710-712 for details.
• For meta-learning, Thm 3.7 is a novel result of the NBS on the monotonicity of validation loss, which has not been presented before as [37] did not focus on meta-learning. In fact, we generalized [Lemma 1, 43] from a fixed protocol to any protocol $\beta$ with the finite norm. Setting the bargained $\alpha$ to $\beta$ gives a new desirable property of the NBS in mete-learning, which establishes its validity as a meta-learning protocol.
• Compared to the setup in [37], we also provided a careful characterization of the feasible set $A$ and extended the discussion from a single disagreement point $D=0$ to general $D$ in Appendix A.4 (Line 611-643). This may provide directions for future gradient aggregation work (Line 350-353). We updated our manuscript with the aforementioned comparison.

Q2.2: Experimental results matching previous works.

Our experimental results on real data majorly agree with the previous results. We've carefully characterized the pros and cons of previous methods and the effect of bargaining on different previous methods, along with their comparisons in Sections 2 and 4.2. We've updated our manuscript to include this point accordingly.

Thanks for the response and clarifications. I would recommend that the new contributions be better highlighted to make them clear, and that the other changes be included as well.

We deeply appreciate the reviewer’s thoughtful feedback and recognition of our contributions. Thank you for giving us the opportunity to clarify our approach based on your insightful comments.

W1: Discussion on the scale of experiments.

Thank you for your comment! We've updated Section 4.2 to include the potential limitations of the scale of experiments (in particular, on the effect of model size, training size, and number of groups, as suggested). Though we do not extensively explore very large-scale problems due to the scope of this paper, we encourage future studies in this direction.

W2: Emphasis on synthetic experiments.

Thank you for pointing it out! We agree and have changed the phrasing to ``experiments on synthetic data" in Line 275 and all other places (Line 108, 574, etc) to avoid overstating the observed properties from simulations. We've also added a clarification on real-world data as suggested.

W3 / Q1: Constraining optimization to set $A$.

Thank you for your question! Appendix A.2 gives the comparison with conflict resolution methods, which attempt to give more aligned updates but do not gaurentee to be within $A$. To strictly constrain a proposed update to a non-empty $A$, there are two potential ways as follows:

1. Choose one update from $A$. This is essentially a bargaining process (where players choose feasible points from $A$). First, a random choice from $A$ would lose the axiomatic property of Pareto Optimality and may result in performance degradation. Second, for axiomatic choices (i.e. solutions characterized by their axioms), we prefer the Nash solution among other prominent ones (including the Kalai-Smorodinsky solution and the Egalitarian solution). Specifically, the Nash objective aligns with our objective to maximize the joint in-effect update. It stands out for its general applicability, robustness [34], and as the unique solution satisfying desirable axioms.

2. Transform the update from previous weighting protocols (LtR, FORML, Meta-gDRO) to $A$. As far as we understand, there is no simple way to project or rescale the proposed update into $A$.

We've updated our manuscript to include this discussion accordingly.

Q2.1: Feasibility of $A$.

Thank you for your question! The following table indicates the number of non-empty $A$ in the first 15 epochs on the US Crime dataset as a showcase.

Here, "hypergradients aligned" means the proposed update of the mini-batch lies in $A$ ($\nabla L_{\beta}^\top g_i > 0$ for all $i$). The percentage in parenthesis is the portion out of the total number of 1275 mini-batches. We observed that approximately 80% times the $A$ is nonempty, which gives room for improvement with bargaining. We've updated our manuscript accordingly.

Q2.2: Scalability with larger number of groups.

Although the likelihood of getting unresolvable conflict may get higher due to the fact that more players are getting involved, we think that the feasibility of $A$ depends more on the group structure rather than the number of groups. For example, the interdependencies and shared factors between groups may cause dependency in hypergradients to enable the feasibility of $A$. When goals of groups rely on common resources or have shared objectives at a higher level, it is still likely to have nonempty $A$.

Theoretically, all presented results should still hold as the number of group increases, thanks to the novel techniques employed in Theorem 3.2 for making this possible. For exmaple, if the number of subgroups exceeds the dimension of the hypergradient, it’s impossible to have linear independence and the previous result [Theorem 5.4, 37] cannot apply.

We've updated our manuscript to include this discussion.

W4: Typos.

Thanks for pointing them out! We've fixed the typos and improved the phrasing on Line 144-145 as suggested.

Thank you for your insightful feedback and constructive comments. We are grateful for the chance to discuss these questions.

W1: Technical explanations on the game theoretical model.

Thank you for your comment! The concepts you mentioned lacking emphasis on Page 4 have their detailed definition subsequently on Page 5 (Line 151-160). Additional discussion on how incentives play roles is in Section 3.3. We also supplemented further explanations on the problem setup in Appendix A.4, the technical preliminaries in Appendix A.3, and the game theory context in Appendix A.2. Please let us know if you have further questions.

W2: How payoffs are determined?

Thank you for your question! Equation 4 gives the definition of payoffs (i.e. utilities). Given a proposed update, the payoff of one group is determined by the dot product between the proposed update and the hypergradient of this group. Though the way to compute payoff is pre-determined, the values of payoffs change during the algorithm and serve as a criterion to compute the bargained update.

Q1: Magnitude of payoff.

Thank you for your question! The value of utility tells us how much of the proposed update is applied in the direction of hypergradient of a certain group. Informally, if it is positive and the magnitude is large, it means the "in-effect" update for such group is large and this group is likely to be improved much by the proposed update (vice versa). We refer to Line 151-160 for detailed explanations.

We sincerely thank the reviewer for their thoughtful comments and valuable feedback. We appreciate the opportunity to address these points and clarify our approach.

W1: Computational cost.

We appreciate this insightful question. We agree the bargaining phase introduces additional complexity to the training process, primarily due to solving the optimization problem in each step. Our analysis shows that the entire training process takes approximately 1.2-1.4 times as long as training with bargaining does, with the bargaining steps (first 15 epochs) themselves taking 2-10 times as much regular training takes per epoch. We view this as a worthwhile trade-off given the enhanced performance and fairness achieved. We've updated our manuscript accordingly.

W2: Switching phases and selection of $T_{bar}$.

Thank you for your question! We refer to our observations from synthetic experiments (Figure 3) to justify the reason to remain a fixed weighting protocol after bargaining: After using bargaining to reach the Pareto Front, switching objective does not diverge the model from the Pareto Front in simulations. This implies that achieving downstream fairness goals may not be at the cost of compromising overall model performance if the model has been converged to the Pareto Front.

In practice, we determine $T_{bar}$ by monitoring the bargaining success rate. We observed from real-data experiments that model's performance would stabilize when this rate stabilizes. This may serve as a sign of swtiching to Stage 2 because no significant improvements could be brought by bargaining. In our real-data experiments, we set $T_{bar}$ to 15 epochs, as this allowed all evaluated settings to reach a stable bargaining success rate. We've added clarifications in our manuscript.

Q1: Sensitivity to the initial weighting protocol $\beta_0$.

We agree and appreciate your acute observation! First, we want to clarify that $\beta_0$ is also used in Stage 1 when bargaining fails, which would preserve the fairness objectives meanwhile providing a fresh start for subsequent bargaining. Second, for the exhibited sensitivity, our analysis to Figure 4 demonstrates that the improvement from bargaining correlates with the initial hypergradient alignment rate (the portion of aligned batches). When this initial rate is low, the bargaining process yields significant improvements (for example, FORML). Conversely, when the initial alignment rate is high, the gains from bargaining are more modest. This relationship may provide insight into the varying effectiveness of our approach across different scenarios.