Multi-Model Federated Learning with Provable Guarantees

Neelkamal Bhuyan, Sharayu Moharir, Gauri JoshiValuetools 2022 · DOI

TL;DR

This paper introduces two novel algorithms, MFA-Rand and MFA-RR, for training multiple independent models simultaneously in a federated learning setting. Crucially, these algorithms come with provable convergence guarantees, addressing a key limitation of prior work, and demonstrate that multi-model federated learning can be more efficient than training models sequentially.

What Problem Does This Paper Address?

Federated Learning (FL) allows edge devices to collaboratively train a global model without sharing their raw data. While much research has focused on training a single model, a more complex scenario arises when the goal is to train multiple distinct models concurrently using the same pool of clients. This "multi-model FL" presents a challenge: how to efficiently assign clients to train different models in each round to achieve good performance for all models without significant accuracy degradation. Prior work explored this, but lacked theoretical guarantees on convergence. This paper aims to fill that gap by proposing algorithms with provable convergence and demonstrating their effectiveness.

Methods

The authors propose two variants of the popular FedAvg algorithm adapted for multi-model FL:

  • MFA-Rand (Multi-FedAvg-Random): In each round, clients are randomly partitioned into M groups (where M is the number of models), and these groups are randomly assigned to the M models.
  • MFA-RR (Multi-FedAvg-Round Robin): This approach divides training into "frames" of M rounds. Within each frame, clients are randomly partitioned into M groups, and these groups are assigned to the M models in a round-robin fashion. This ensures each client-model pair is trained exactly once per frame.

The core of their contribution lies in providing theoretical convergence guarantees for both MFA-Rand and MFA-RR under standard assumptions (e.g., strongly convex and smooth loss functions, bounded stochastic gradients). They also introduce a performance metric to quantify the "gain" of multi-model FL over sequential training.

Datasets

The paper uses synthetic datasets for experiments:

  • Synthetic(1,1)-A and Synthetic(1,1)-B: Used for multi-class logistic regression.
  • CelebA: Used for binary classification of facial attributes.

These datasets are standard in FL research and are used to evaluate the proposed algorithms in various settings.

Key Insights and Ideas

  • Provable Guarantees for Multi-Model FL: The most significant contribution is providing the first provable convergence guarantees for multi-model FL algorithms, moving beyond empirical observations.
  • MFA-RR's Efficiency: The round-robin assignment in MFA-RR leads to a faster convergence rate (O(1/T)) compared to MFA-Rand (O(1/√T)) under certain conditions, especially when local SGD transitions to full gradient descent.
  • Efficiency of Simultaneous Training: The paper demonstrates, both theoretically and empirically, that training multiple models simultaneously can be more efficient (yield a higher "gain") than training them one by one sequentially, especially as the number of models increases.
  • Impact of Client Sampling: The analysis highlights how factors like the number of models (M) and the number of local SGD iterations (E) influence convergence.

Key Results

  • Convergence Rates: MFA-Rand achieves an error decay of O(1/√T), while MFA-RR achieves O(1/T) under specific conditions.
  • Performance Gain: Experiments show that the "gain" (efficiency improvement) of multi-model FL increases with the number of models (M). For instance, in strongly convex settings, the gain increases sub-linearly with M.
  • Reliability: While MFA-Rand and MFA-RR show similar average performance, MFA-RR exhibits significantly lower variance, making it a more reliable choice.
  • Real-world Applicability: Experiments on datasets like CelebA (which involves CNNs and thus non-convex optimization) and mixed model scenarios (logistic regression + CNN) demonstrate the practical benefits of multi-model FL.

Limitations and Future Work

  • Full Device Participation Assumption: The theoretical analysis, particularly for MFA-Rand's gain, primarily assumes full device participation. While experiments explore partial participation, theoretical guarantees for this scenario are left for future work.
  • Unbiased Client Selection: The paper mentions that further work could include theoretical analysis for unbiased client selection algorithms in multi-model FL.
  • Data Heterogeneity: While the paper assumes heterogeneous data across clients, the theoretical analysis might benefit from deeper exploration of its impact on multi-model FL.
  • Specific Convergence Rates: The paper notes that while analytical bounds show an order-wise difference between MFA-Rand and MFA-RR, the observed empirical difference is not always as pronounced, potentially due to simplifications in the analysis (e.g., assuming full gradient descent for MFA-RR).

Summary updated

BibTeX
@inproceedings{bhuyan2022multi,
  author = {Neelkamal Bhuyan and Sharayu Moharir and Gauri Joshi},
  title = {{Multi-Model Federated Learning with Provable Guarantees}},
  booktitle = {Valuetools},
  year = {2022},
  doi = {10.1007/978-3-031-31234-2\_13},
}
Figure