Fair Federated Learning via Bounded Group Loss

Shengyuan Hu, Zhiwei Steven Wu, Virginia Smith

Federated Learning (FL) has revolutionized how we train models on decentralized data, but it brings a unique set of headaches when it comes to fairness. In a new paper, researchers from CMU introduce PFFL (Provably Fair Federated Learning), a framework that provides the first formal convergence and fairness guarantees for group fairness in federated settings.

TL;DR

This paper introduces a framework for provably fair federated learning by leveraging Bounded Group Loss (BGL). Unlike prior methods that lack formal guarantees, their proposed algorithm (PFFL) provides a scalable way to satisfy global fairness constraints while maintaining high model utility across heterogeneous data silos.

What Problem Does This Paper Address?

In standard machine learning, group fairness aims to ensure a model doesn't discriminate based on protected attributes like race or gender. In Federated Learning, this is significantly harder because data is distributed across different "silos" (like phones or hospitals) that often have very different data distributions (heterogeneity).

The authors point out a critical gap: naively enforcing fairness locally at each client doesn't guarantee fairness for the global population. As shown in Figure 1, local fairness constraints can actually lead to higher error and worse global fairness because they ignore how groups are distributed across the entire network. Furthermore, most existing "fair FL" methods are empirical and lack the theoretical "teeth"—formal proofs that the model will actually be fair or even converge—needed for high-stakes deployments.

Figure 1: Left: Due to data heterogeneity in FL, data distribu- tions conditioned on each protected attribute (shown in different colors) may differ across clients. Fair FL aims to learn a model that provides fair prediction on the entire data distribution. Right: Empirical results (ACS dataset) verify that training with local fairness constraints alone induces higher error and worse fairness than using a global fairness constraint.

Methods

The core of their approach is moving away from "loss parity" (trying to make losses exactly equal across groups) toward Bounded Group Loss (BGL).

Key Innovations:

  1. Bounded Group Loss (BGL): Instead of forcing all groups to have the same error rate (which can be mathematically difficult and hurt overall accuracy), BGL ensures that the loss for every group stays below a specific threshold. This maintains the convexity of the optimization problem, making it much easier to solve reliably.
  2. Conditional BGL (CBGL): They extend BGL to handle conditional cases, providing a flexible relaxation of "Equalized Odds"—a common fairness metric that is notoriously hard to satisfy in FL.
  3. PFFL Algorithm: They formulate the problem as a saddle-point optimization (a min-max problem). The algorithm alternates between:
  4. Server-side: Updating "fairness weights" ($\lambda$) using exponentiated gradient descent based on which groups are currently seeing the highest violations.
  5. Client-side: Performing local training rounds (similar to FedAvg) to minimize a regularized objective that includes these fairness weights.

Datasets

The authors evaluated PFFL on three diverse benchmarks:

  • ProPublica COMPAS: A dataset for recidivism prediction (protected attribute: gender).
  • ACS Employment: US Census data used to predict employment status (protected attribute: race). This dataset is naturally partitioned into 50 states, mimicking real-world FL silos.
  • CelebA: A large-scale face attributes dataset (protected attribute: gender), used to test the method on non-convex neural networks.

Key Insights and Ideas

  • Convexity is King: By using BGL instead of parity constraints, the authors keep the objective function convex (assuming the underlying loss is convex). This allows them to provide the first "no-regret" style convergence analysis for fair FL.
  • Global > Local: The paper proves that global fairness constraints are essential. Because one client might only see a small, non-representative slice of a protected group, local enforcement is often counterproductive.
  • Flexibility in Trade-offs: BGL allows practitioners to tune the "fairness level" ($\zeta$) for each group. This is more practical than parity, which often forces a "race to the bottom" where accuracy is sacrificed on easy-to-predict groups just to match the performance of harder ones.

Key Results

The empirical results across all datasets show that PFFL consistently outperforms vanilla FedAvg and other fair FL baselines.

  • Better Trade-offs: PFFL achieves a better Pareto frontier between accuracy and fairness. In some cases, it actually improved both fairness and accuracy compared to baselines.
  • Provable Guarantees: The authors provide a theorem (Theorem 3) that bounds both the expected risk and the fairness violation on unseen test data, accounting for the number of clients and samples per group.
  • Generalization: They show that as the number of clients ($K$) increases, the model generalizes better in terms of utility, but requires more samples per group to maintain strict fairness guarantees.

Limitations and Future Work

  • Communication Overhead: PFFL requires clients to send group-specific loss information back to the server, which adds a small amount of extra data to each communication round.
  • Privacy Risks: Sharing group-level statistics might leak information about the composition of a client's local dataset. The authors suggest that integrating differential privacy (DP) is a vital next step.
  • Hyperparameter Tuning: Finding the optimal balance between the regularization strength ($B$) and the loss bounds ($\zeta$) currently requires a grid search, which can be computationally expensive in FL.

Summary updated

Abstract

Fair prediction across protected groups is an important constraint for many federated learning applications. However, prior work studying group fair federated learning lacks formal convergence or fairness guarantees. In this work we propose a general framework for provably fair federated learning. In particular, we explore and extend the notion of Bounded Group Loss as a theoretically-grounded approach for group fairness. Using this setup, we propose a scalable federated optimization method that optimizes the empirical risk under a number of group fairness constraints. We provide convergence guarantees for the method as well as fairness guarantees for the resulting solution. Empirically, we evaluate our method across common benchmarks from fair ML and federated learning, showing that it can provide both fairer and more accurate predictions than baseline approaches.
BibTeX
@inproceedings{hu2023fair,
  author = {Shengyuan Hu and Zhiwei Steven Wu and Virginia Smith},
  title = {{Fair Federated Learning via Bounded Group Loss}},
  booktitle = {SaTML},
  year = {2023},
  url = {https://openreview.net/forum?id=KkI8sjKqtnV},
}
Figure