Combating Client Dropout in Federated Learning via Friend Model Substitution

Heqiang Wang, Jie Xu

TL;DR

This paper introduces FL-FDMS, a federated learning (FL) algorithm designed to handle unpredictable client dropout. By identifying "friend" clients with similar data distributions on-the-fly, the server can use an active friend's model update as a high-quality substitute for a dropped-out client, significantly improving convergence speed and model accuracy compared to simply ignoring missing updates.

What Problem Does This Paper Address?

In a perfect world, every device in a Federated Learning network would contribute its local model update in every round. In reality, clients (like smartphones or IoT devices) frequently drop out due to low battery, poor connectivity, or hardware constraints.

Most existing FL research focuses on proactive participation—where the server chooses a subset of clients to save bandwidth. This paper tackles passive dropout, which is uncontrollable and often non-random. If specific types of clients (e.g., those in a certain geographic area with poor signal) drop out more often, the global model becomes biased toward the remaining "active" population. Current solutions either ignore dropped clients (causing bias) or use "stale" updates from previous rounds (which become inaccurate as the global model evolves).

Methods

The authors propose Federated Learning with Friend Model Substitution (FL-FDMS). The core idea is that if client A and client B have similar data, their model updates will be similar. If client A drops out, client B’s current update is a better proxy for A than a stale update from A's past or a generic average of all clients.

Key components include:

  • Similarity Discovery: For active clients, the server calculates a similarity score based on the normalized cosine similarity of their model updates. Over time, the server maintains an average similarity score for every pair of clients.
  • Friend Substitution: When a client drops out, the server identifies its "best friend" (the active client with the highest historical similarity score) and uses that friend's current update as a substitute.
  • Complexity Reduction: Calculating $O(K^2)$ pairwise similarities is computationally expensive. The authors implement a mechanism inspired by Hoeffding Races to maintain a "candidate friend set." As the server becomes confident that two clients are not friends, it stops comparing them, drastically reducing the computational overhead.
  • Convergence Analysis: The authors provide a theoretical proof showing that the convergence of FL with dropout depends on the "substitution error." They prove that FL-FDMS asymptotically approaches the performance of a system where all "friendship" relationships are known perfectly from the start.

Datasets

The researchers evaluated their approach using two standard computer vision benchmarks:

  • MNIST: A dataset of handwritten digits.
  • CIFAR-10: A dataset of 60,000 color images in 10 classes.

Both were tested in "clustered" settings (where groups of clients share similar data distributions) and "general" non-IID (Independent and Identically Distributed) settings to simulate real-world data heterogeneity.

Key Insights and Ideas

  • Dropout as Substitution Error: The authors cleverly frame the dropout problem as a "substitute" problem. Even when we ignore a client, we are effectively substituting their missing update with the average of the active ones. This framing allows them to mathematically bound the error.
  • The "Stale" Update Trap: The paper highlights that using a client's own previous update (a common strategy) fails because as the global model moves toward a minimum, old updates point in the wrong direction. A "friend's" current update is often more relevant than your own "past" update.
  • Privacy-Preserving Similarity: Friendship is discovered solely through model updates already being sent to the server. No additional raw data or metadata is required from the clients, maintaining the privacy benefits of standard FL.

Key Results

  • Robustness to High Dropout: FL-FDMS maintained high accuracy even when the dropout rate ($\alpha$) was as high as 70%.
  • Performance Gap: In CIFAR-10 experiments with a 50% dropout rate, FL-FDMS significantly outperformed the "Dropout" (ignore them) and "Stale" (use last update) baselines, tracking closely with the "Full Participation" ideal.
  • Fluctuation Reduction: Standard FL with dropout often shows "jittery" convergence curves. FL-FDMS smoothed these fluctuations by providing more consistent, representative updates to the server in every round.
  • Efficiency: The complexity reduction mechanism successfully pruned the search space, allowing the server to maintain high performance while only computing a fraction of the possible similarity pairs.

Limitations and Future Work

  • Friendship Dependency: The algorithm's effectiveness relies on the existence of "friends." In a scenario where every single client has a completely unique, outlier data distribution, the substitution error would remain high because no good proxies exist.
  • Dynamic Distributions: The current model assumes data distributions are relatively static. If a client’s data distribution changes significantly over time (concept drift), the historical similarity scores might become misleading.
  • Communication Overhead: While the paper addresses computational complexity on the server, the impact of the substitution mechanism on the overall communication protocol (e.g., if the server needs to request specific updates to fill gaps) could be explored further.

Summary updated

Abstract

Federated learning (FL) is a new distributed machine learning framework known for its benefits on data privacy and communication efficiency. Since full client participation in many cases is infeasible due to constrained resources, partial participation FL algorithms have been investigated that proactively select/sample a subset of clients, aiming to achieve learning performance close to the full participation case. This paper studies a passive partial client participation scenario that is much less well understood, where partial participation is a result of external events, namely client dropout, rather than a decision of the FL algorithm. We cast FL with client dropout as a special case of a larger class of FL problems where clients can submit substitute (possibly inaccurate) local model updates. Based on our convergence analysis, we develop a new algorithm FL-FDMS that discovers friends of clients (i.e., clients whose data distributions are similar) on-the-fly and uses friends' local updates as substitutes for the dropout clients, thereby reducing the substitution error and improving the convergence performance. A complexity reduction mechanism is also incorporated into FL-FDMS, making it both theoretically sound and practically useful. Experiments on MNIST and CIFAR-10 confirmed the superior performance of FL-FDMS in handling client dropout in FL.
BibTeX
@misc{wang2022combating,
  author = {Heqiang Wang and Jie Xu},
  title = {{Combating Client Dropout in Federated Learning via Friend Model Substitution}},
  year = {2022},
  eprint = {2205.13222},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2205.13222},
}
Figure