Generalization Bounds for Federated Learning: Fast Rates, Unparticipating Clients and Unbounded Losses

Xiaolin Hu, Shaojie Li, Yong LiuICLR 2023 · OpenReview

Introduction

In real-world Federated Learning (FL) deployments, the ecosystem is often messy. While thousands or millions of devices might exist in a network, only a small fraction—the participating clients—usually contribute to training a global model at any given time due to constraints like poor network connections or low battery. Most existing research focuses on how well the model performs on the data it saw during training. However, the ultimate goal is often to deploy that model to all devices, including the "unparticipating" ones.

This paper provides a rigorous theoretical framework to answer a critical question: Does a model trained on a subset of clients actually work for the ones who stayed home? The authors derive state-of-the-art "fast" generalization bounds for both participating and unparticipating clients, and extend these results to realistic scenarios involving unbounded, heavy-tailed loss functions.

The Challenges: Participation Gap and Unbounded Losses

When evaluating FL models, two major theoretical hurdles arise:

  1. The Participation Gap: The error for unparticipating clients is composed of two parts: the error from training on finite data (participating error) and the error caused by the fact that the training clients are just a sample of the whole population (participation gap).
  2. Unbounded Losses: Most theoretical guarantees for machine learning assume that the "loss" (the error) is bounded, meaning it cannot be infinitely large. This assumption fails in many practical regression tasks where noise can be "heavy-tailed" (i.e., extreme outliers are possible).

Methodology: A Two-Level Distribution Framework

To tackle these challenges, the authors employ a two-level distribution framework that captures both the relatedness and heterogeneity of client data.

Two-level distribution framework illustrating the sources of participating error and the participation gap.

As illustrated above, the framework consists of:

  • Meta-distribution ($P$): A high-level distribution from which individual client distributions are sampled. This models client relatedness.
  • Client Distribution ($D_i$): The specific data distribution for a single client, from which local data samples ($S_i$) are drawn. This models data heterogeneity.

To analyze generalization within this framework, the authors utilize several sophisticated statistical tools:

  • Bernstein Conditions: Used to achieve "fast" learning rates. While standard rates usually improve at a speed of $\mathcal{O}(1/\sqrt{N})$, fast rates improve at $\mathcal{O}(1/N)$, significantly tightening the performance guarantees.
  • Small-Ball Method: This is the key to handling unbounded losses. When losses are heavy-tailed, standard concentration inequalities break down. The small-ball method allows the authors to relate empirical risk to population risk even when the error can be very large.
  • Rademacher Complexity: Used to measure the "richness" or capacity of the hypothesis space (the set of possible models).

Key Insights and Theoretical Results

The paper establishes several state-of-the-art bounds that confirm unparticipating clients do benefit from the global model, provided the number of participating clients ($m$) is sufficiently large.

  • Fast Rates in Probability: For bounded losses, the generalization error for unparticipating clients is bounded by $\mathcal{O}(\frac{1}{mn} + \frac{1}{m})$, where $m$ is the number of clients and $n$ is the number of samples per client. This is significantly faster than previous $\mathcal{O}(\frac{1}{\sqrt{mn}})$ results. Furthermore, unlike previous works that only showed fast rates "in expectation" (on average), this paper proves them "in probability," offering a much stronger guarantee for specific runs of the algorithm.
  • Unbounded Convergence: Even with sub-exponential or sub-Weibull losses (which allow for extreme outliers), the authors successfully derive convergence bounds of $\mathcal{O}(\frac{1}{\sqrt{mn}} + \frac{1}{\sqrt{m}})$. While heavy tails slow down the convergence compared to the bounded case, it still follows a predictable power law.
  • Empirical Alignment: The theoretical findings were validated using the EMNIST dataset (for CNNs) and synthetic data (for federated linear regression). On EMNIST, researchers observed that as $m$ increased, the convergence rate of the "participating error" was actually slower than the "unparticipating error," perfectly matching their theoretical predictions.

Limitations and Future Work

While this paper provides a massive leap in FL theory, a few areas remain open for exploration:

  • Non-Convexity: Much of the "fast rate" theory relies on the Bernstein condition, which is easier to satisfy in convex settings. Extending these high-probability bounds to complex, non-convex deep learning landscapes remains a challenge.
  • Extreme Heterogeneity: If every client is completely different (extreme heterogeneity), the generalization error for unparticipating clients will naturally be large. The model's success inherently relies on the existence of a meaningful meta-distribution.
  • Algorithm Specifics: The current analysis focuses on Empirical Risk Minimization (ERM). Future work could investigate how specific federated optimizers, like FedAvg or FedProx, affect these bounds through their local update steps.

Summary updated

Abstract

In {federated learning}, the underlying data distributions may be different across clients. This paper provides a theoretical analysis of generalization error of {federated learning}, which captures both heterogeneity and relatedness of the distributions. In particular, we assume that the heterogeneous distributions are sampled from a meta-distribution. In this two-level distribution framework, we characterize the generalization error not only for clients participating in the training but also for unparticipating clients. We first show that the generalization error for unparticipating clients can be bounded by participating generalization error and participating gap caused by clients' sampling. We further establish fast learning bounds of order $\mathcal{O}(\frac{1}{mn} + \frac{1}{m})$ for unparticipating clients, where $m$ is the number of clients and $n$ is the sample size at each client. To our knowledge, the obtained fast bounds are state-of-the-art in the two-level distribution framework. Moreover, previous theoretical results mostly require the loss function to be bounded. We derive convergence bounds of order $\mathcal{O}(\frac{1}{\sqrt{mn}} + \frac{1}{\sqrt{m}})$ under unbounded assumptions, including sub-exponential and sub-Weibull losses.
BibTeX
@inproceedings{hu2023generalization,
  author = {Xiaolin Hu and Shaojie Li and Yong Liu},
  title = {{Generalization Bounds for Federated Learning: Fast Rates, Unparticipating Clients and Unbounded Losses}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=-EHqoysUYLx},
}
Figure