SPACE: Single-round Participant Amalgamation for Contribution Evaluation in Federated Learning

Yi-Chung Chen, Hsi-Wen Chen, Shun-Guei Wang, Ming-Syan Chen

In the world of Federated Learning (FL), not all participants are created equal. Some clients provide high-quality, diverse data that accelerates model convergence, while others might contribute "noisy" or even malicious updates. To maintain fairness and robustness, we need to evaluate exactly how much each client contributes.

The gold standard for this evaluation is the Shapley Value, a concept derived from cooperative game theory. However, calculating it is a computational nightmare, often requiring exponential retraining or hundreds of communication rounds. In their NeurIPS 2023 paper, researchers from National Taiwan University introduce SPACE (Single-round Participant Amalgamation for Contribution Evaluation), a framework that slashes this overhead to a single communication round.

TL;DR

SPACE is an efficient framework that evaluates client contributions in Federated Learning using just one communication round. By combining federated knowledge distillation with class-based prototypes, it eliminates the need for expensive model retraining and large-scale validation set iterations.

What Problem Does This Paper Address?

Evaluating client contribution is essential for incentive mechanisms (paying people for their data), client selection (picking the best participants), and robustness (filtering out bad actors).

The primary challenge is the computational cost. Traditional Shapley Value methods require evaluating the model's performance across nearly every possible combination of clients. Even modern approximations suffer from two major bottlenecks:

  1. Multi-Round Training: They usually require the global model to reach or near convergence, involving many expensive communication rounds.
  2. Dataset-Dependent Evaluation: The time it takes to evaluate a model usually scales with the size of the validation set. As datasets grow, the evaluation phase becomes a massive bottleneck.

Methods

SPACE introduces two novel components to bypass these hurdles:

Overview of the SPACE framework featuring Federated Knowledge Amalgamation and Prototype-based Model Evaluation.
  • Federated Knowledge Amalgamation (FKA): Instead of waiting for a model to converge through standard FL, SPACE treats client models as "teachers" and the server model as a "student." It uses feature projector modules to align the embedding spaces of all clients and distills their collective knowledge into the server model in a single round.
  • Prototype-based Model Evaluation (PME): To break the dependency on validation set size, SPACE uses "prototypes"—the mean embedding vectors for each class. Instead of testing the model on thousands of individual samples, the server compares the similarity between client prototypes and server prototypes. This turns a heavy evaluation task into a simple, fast similarity calculation.
  • Logistic Utility Function: The authors observed that standard accuracy-based utility functions often violate "individual rationality" (where a client might seem to contribute less than if they worked alone). They wrap the utility in a logistic function to better model user satisfaction and ensure that high-performing coalitions are properly weighted.

Datasets

The authors evaluated SPACE across several standard benchmarks, simulating both Non-IID (heterogeneous data) and Mislabeled (noisy/malicious data) scenarios:

  • MNIST: A classic digit recognition dataset (10 clients).
  • CIFAR10: A more complex image dataset (5 clients).
  • Tiny-ImageNet: Used to test scalability, featuring 50 categories and 10 clients.

Key Insights and Ideas

  • The "One-Round" Efficiency: The most striking insight is that you don't need a fully trained global model to understand which clients have the most valuable data. Distilling feature representations in one round is sufficient to rank contributions accurately.
  • Prototypes as Privacy-Preserving Proxies: Prototypes allow the server to understand the data distribution of a client without ever seeing the raw data or even individual gradients, adding a layer of efficiency and privacy.
  • Rationality in Incentives: By using a logistic utility function, the authors acknowledge that in real-world applications, the "value" of a model isn't linear. A jump from 50% to 90% accuracy is worth much more to a user than a jump from 90% to 91%, and the contribution evaluation should reflect that.

Key Results

SPACE demonstrates significant improvements over existing contribution evaluation methods, both theoretically and empirically.

Comparison of communication and computation costs between SPACE and baseline methods.
  • Massive Speedup: On the MNIST dataset, SPACE completed its evaluation in 160 seconds, compared to 97,137 seconds for the "Real Shapley" method—a speedup of roughly 600x.
  • Communication Efficiency: As shown in the cost analysis, SPACE drastically reduces communication overhead. In practice, it reduced communication costs from over 11,000 MB (for traditional methods) to just 1.76 MB on MNIST.
  • High Correlation: Despite the speed, SPACE maintained a high Pearson Correlation Coefficient (PCC), meaning its estimated contributions were very close to the "true" Shapley values.
  • Application Success: The researchers showed that using SPACE for "Client Reweighting" (giving more weight to good clients) improved final model accuracy by up to 3.52% in noisy data scenarios.

Limitations and Future Work

  • Validation Set Requirement: SPACE still requires the server to hold a "proper and reliable" labeled validation set. In some highly private or specialized FL settings, the server might not have any labeled data at all.
  • GPU Memory: Amalgamating many client models simultaneously can be memory-intensive. While the authors propose a "hierarchical" approach to mitigate this, it remains a factor for massive-scale FL.
  • Future Directions: The authors suggest exploring ways to decrease the dependence on the validation set further, perhaps by using unlabeled data or self-supervised techniques for the amalgamation phase.

Check out the code: https://github.com/culiver/SPACE

Summary updated

Abstract

The evaluation of participant contribution in federated learning (FL) has recently gained significant attention due to its applicability in various domains, such as incentive mechanisms, robustness enhancement, and client selection. Previous approaches have predominantly relied on the widely adopted Shapley value for participant evaluation. However, the computation of the Shapley value is expensive, despite using techniques like gradient-based model reconstruction and truncating unnecessary evaluations. Therefore, we present an efficient approach called Single-round Participants Amalgamation for Contribution Evaluation (SPACE). SPACE incorporates two novel components, namely Federated Knowledge Amalgamation and Prototype-based Model Evaluation to reduce the evaluation effort by eliminating the dependence on the size of the validation set and enabling participant evaluation within a single communication round. Experimental results demonstrate that SPACE outperforms state-of-the-art methods in terms of both running time and Pearson’s Correlation Coefficient (PCC). Furthermore, extensive experiments conducted on applications, client reweighting, and client selection highlight the effectiveness of SPACE. The code is available at https://github.com/culiver/SPACE.
BibTeX
@inproceedings{chen2023space,
  author = {Yi-Chung Chen and Hsi-Wen Chen and Shun-Guei Wang and Ming-Syan Chen},
  title = {{SPACE: Single-round Participant Amalgamation for Contribution Evaluation in Federated Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=tmxjuIFSEc},
}
Figure