Multi-Source to Multi-Target Decentralized Federated Domain Adaptation

Su Wang, Seyyedali Hosseinalipour, Christopher G. BrintonIEEE Trans. Cogn. Commun. Netw 2023 · OpenReview

TL;DR

This paper introduces ST-LF, a novel decentralized federated learning approach that tackles the challenge of varying labeled and unlabeled data across devices. By jointly optimizing device classification into sources and targets, and the formation of links between them, ST-LF significantly improves model accuracy and communication efficiency, outperforming existing methods.

What Problem Does This Paper Address?

Federated Learning (FL) typically assumes devices have sufficient labeled data for training. However, in real-world scenarios, devices often have varying amounts of labeled and unlabeled data, leading to models biased towards devices with more labeled data. This heterogeneity in data availability, particularly the quantity and distribution of unlabeled data, is a critical challenge that existing FL methods largely overlook. This paper addresses this gap by proposing a decentralized federated domain adaptation (DA) methodology that effectively leverages both labeled and unlabeled data across devices, even when devices have very little or no labeled data. The goal is to adapt models from "source" devices with high-quality labeled data to "target" devices with limited or unlabeled data, without relying on a central server.

Methods

The core of the proposed methodology is Source-Target Determination and Link Formation (ST-LF). This approach tackles three intertwined problems:

  1. Source/Target Classification: Identifying which devices should act as sources (providing high-quality labeled data) and which should act as targets (receiving adapted models).
  2. Link Formation: Determining how to optimally connect sources to targets for model transfer.
  3. Communication Energy Efficiency: Minimizing the energy consumed during model transmissions.

ST-LF formulates a measurable generalization error bound that accounts for source-target hypothesis deviations and data distribution divergences. This bound is then used to create a mixed-integer signomial program (MISP), a complex optimization problem. To solve this tractably, the authors develop an algorithm based on successive convex approximations. A key innovation is the development of a decentralized algorithm for empirical divergence estimation between device pairs, which avoids transmitting raw data, thus preserving data privacy.

Datasets

The authors evaluate their method on three standard image classification datasets commonly used in domain adaptation:

  • MNIST: A dataset of handwritten digits.
  • USPS: Another dataset of handwritten digits, with different image formatting.
  • MNIST-M: A more challenging dataset created by blending MNIST digits with photographs, introducing significant visual differences.

The experiments involve various configurations:

  • Single Dataset: Devices draw data from a single underlying dataset (e.g., MNIST), but with non-i.i.d. distributions and varying labeled/unlabeled ratios.
  • Mixed Dataset: Devices draw data from a combination of datasets (e.g., MNIST + USPS).
  • Split Dataset: Devices exclusively draw data from different datasets (e.g., some from MNIST, others from USPS).

Key Insights and Ideas

  • Data Heterogeneity Beyond Statistical: The paper highlights that heterogeneity in FL extends beyond just statistical (non-i.i.d.) and resource (bandwidth) dimensions to include the crucial aspect of varying labeled/unlabeled data quantities.
  • Joint Optimization is Key: ST-LF's strength lies in its ability to jointly optimize source/target classification, link formation, and communication energy. Treating these independently leads to suboptimal results.
  • Leveraging Unlabeled Data for DA: The methodology effectively uses unlabeled data to estimate divergences between devices, which is crucial for guiding the domain adaptation process when labeled data is scarce.
  • Decentralized Divergence Estimation: The proposed Algorithm 1 for estimating empirical divergences is a significant contribution, enabling privacy-preserving DA in decentralized settings.
  • Trade-off Between Accuracy and Energy: The optimization framework explicitly balances the need for accurate models with the cost of communication, allowing for flexible resource management.

Key Results

  • Improved Classification Accuracy: ST-LF consistently outperforms state-of-the-art baselines (including FedAvg, FADA, and several heuristic methods) in average target classification accuracy across single, mixed, and split dataset scenarios. For instance, on MNIST, ST-LF achieves over 9% higher accuracy than baselines in single-dataset settings.
  • Significant Communication Energy Savings: The method achieves substantial reductions in network-wide communication resource consumption by forming fewer source-target links. This saving is directly influenced by the communication energy scaling parameter, allowing for tunable efficiency.
  • Effective Source/Target Determination: Experiments demonstrate that ST-LF correctly identifies devices with high-quality labeled data as sources and those with limited data as targets, adapting to various divergence scenarios (uniform, extreme, random).
  • Robustness to Data Scenarios: The method shows strong performance across diverse and challenging dataset configurations, including mixed and split datasets, which combine statistical and dataset heterogeneity.

Limitations and Future Work

  • NP-Hard Optimization: The core optimization problem is a mixed-integer signomial program, which is NP-hard. While the authors propose a tractable solution using successive convex approximations, the computational complexity can still be a factor.
  • Theoretical Bounds: The paper derives theoretical bounds, but the empirical estimates for Corollary 1 show a difference from the LHS by roughly an order of magnitude. The authors attribute this to the introduction of terms bounding empirical Rademacher complexities and the worst-case nature of the bound.
  • Future Work: The paper suggests that the optimization techniques developed for ST-LF have broader applicability to other federated domain adaptation problems. Further research could explore more complex network topologies, dynamic device availability, and different types of ML tasks beyond image classification.

Summary updated

Abstract

Heterogeneity across devices in federated learning (FL) typically refers to statistical (e.g., non-i.i.d. data distributions) and resource (e.g., communication bandwidth) dimensions. In this paper, we focus on another important dimension that has received less attention: varying quantities/distributions of labeled and unlabeled data across devices. In order to leverage all data, we develop a decentralized federated domain adaptation methodology which considers the transfer of ML models from devices with high quality labeled data (called sources) to devices with low quality or unlabeled data (called targets). Our methodology, Source-Target Determination and Link Formation (ST-LF), optimizes both (i) classification of devices into sources and targets and (ii) source-target link formation, in a manner that considers the trade-off between ML model accuracy and communication energy efficiency. To obtain a concrete objective function, we derive a measurable generalization error bound that accounts for estimates of source-target hypothesis deviations and divergences between data distributions. The resulting optimization problem is a mixed-integer signomial program, a class of NP-hard problems, for which we develop an algorithm based on successive convex approximations to solve it tractably. Subsequent numerical evaluations of ST-LF demonstrate that it improves classification accuracy and energy efficiency over state-of-the-art baselines.
BibTeX
@article{wang2023multi,
  author = {Su Wang and Seyyedali Hosseinalipour and Christopher G. Brinton},
  title = {{Multi-Source to Multi-Target Decentralized Federated Domain Adaptation}},
  journal = {IEEE Trans. Cogn. Commun. Netw.},
  year = {2023},
  url = {https://openreview.net/forum?id=0UHqvdJcfY},
}
Figure