PaperlayerView exact revision on arXiv

Source-linked AI summary

FedGroup: Efficient Clustered Federated Learning via Decomposed Data-Driven Measure

Moming Duan, Duo Liu, Xinyuan Ji, Renping Liu, Liang Liang, Xianzhang Chen, Yujuan Tan

arXiv:2010.06870v6cs.LGcs.DC

TL;DR

Statistical heterogeneity in federated learning makes the joint optimization objective difficult and can slow convergence. FedGroup clusters clients using a decomposed data-driven measure and supports newcomer cold starts; across evaluated datasets, it outperforms several frameworks, including a reported FEMNIST accuracy gain over FedSEM.

  • Problem

    Non-IID and imbalanced client data make federated joint optimization difficult, increase local-to-global divergence, and slow convergence.

    Source: §I · p. 1, C. Group Cold Start · p. 5

  • Method

    FedGroup clusters client parameter-update directions using EDC, a decomposed data-driven measure, and uses an auxiliary server for newcomer cold starts.

    Source: §I · pp. 1–2

  • Results

    Across four open datasets, FedGroup and FedGrouProx outperform several frameworks; FedGroup improves top-1 test accuracy by +26.9% on FEMNIST compared to FedSEM.

    Source: §I · p. 2, §V · p. 9

  • Takeaways & Limitations

    Adding FedProx can make federated training more stable, but the experiments found no significant classification-accuracy improvement from the proximal term.

    Source: §V · p. 9

Abstract

from arXiv · show

Federated Learning (FL) enables the multiple participating devices to collaboratively contribute to a global neural network model while keeping the training data locally. Unlike the centralized training setting, the non-IID and imbalanced (statistical heterogeneity) training data of FL is distributed in the federated network, which will increase the divergences between the local models and global model, further degrading performance. In this paper, we propose a novel clustered federated learning (CFL) framework FedGroup, in which we 1) group the training of clients based on the similarities between the clients' optimization directions for high training performance; 2) construct a new data-driven distance measure to improve the efficiency of the client clustering procedure. 3) implement a newcomer device cold start mechanism based on the auxiliary global model for framework scalability and practicality. FedGroup can achieve improvements by dividing joint optimization into groups of sub-optimization and can be combined with FL optimizer FedProx. The convergence and complexity are analyzed to demonstrate the efficiency of our proposed framework. We also evaluate FedGroup and FedGrouProx (combined with FedProx) on several open datasets and made comparisons with related CFL frameworks. The results show that FedGroup can significantly improve absolute test accuracy by +14.1% on FEMNIST compared to FedAvg. +3.4% on Sentiment140 compared to FedProx, +6.9% on MNIST compared to FeSEM.

I. INTRODUCTION

Statistical heterogeneity complicates federated training, while prior clustered approaches leave efficiency and newcomer-device challenges. FedGroup groups client training using a data-driven distance measure and adds a cold-start strategy; the paper reports accuracy gains over existing frameworks.

I. INTRODUCTION

  • Because the server cannot access client data for balancing or outlier detection, statistical heterogeneity remains challenging; prior CFL frameworks can be inefficient or omit newcomers.The paper describes CFL as clustering clients around optimization directions rather than using a single consensus model.Source: §I · p. 1
  • FedGroup and FedGrouProx cluster clients using a decomposed data-driven measure of similarities between their parameter updates.FedGrouProx combines FedGroup with the FedProx optimizer.Source: §I · pp. 1–2
  • +6.9% on MNIST, +26.9% on FEMNIST, and +5.3% on Sentiment140 versus FedSEM are reported test-accuracy improvements for FedGroup.The paper also reports superior performance to FedProx and FeSEM.Source: §I · pp. 1–2
  • EDC is designed to improve client clustering and avoid distance-concentration effects when clustering high-dimensional, low-sample-size parameters or directions.The paper describes EDC as a decomposed data-driven measure of cosine dissimilarity.Source: §I · pp. 1–2
  • An auxiliary server supports cold starts for groups and newcomer devices, a strategy presented as improving scalability and practicality.The framework also reports experimentally demonstrating the strategy's efficiency.Source: §I · pp. 1–2

A. Federated Learning

  • Larger local epoch counts can speed convergence and reduce communication, but excessive epochs increase local-to-global discrepancies and can make training volatile and suboptimal.The passage identifies local epochs as a FedAvg hyperparameter.Source: A. Federated Learning · p. 2

B. Clustered Federated Learning

Clustered federated learning replaces a single consensus objective with specialized group models to address statistical heterogeneity. Existing CFL approaches face efficiency, communication, initialization, and newcomer-device challenges.

B. Clustered Federated Learning

  • CFL divides the global optimization goal into sub-objectives and trains specialized group models, aiming for higher accuracy under statistical heterogeneity.The passage contrasts this pluralistic group architecture with a consensus global model trained on incongruent data.Source: B. Clustered Federated Learning · p. 3
  • Existing CFL methods trade off efficiency, communication, or robustness: recursive splitting can be costly, IFCA broadcasts every group model, and FL+HC repeatedly computes cluster distances.IFCA is also described as initialization-sensitive, while ℓ2-based FeSEM may suffer distance concentration in high dimensions.Source: B. Clustered Federated Learning · p. 3
  • Prior CFL frameworks assume every client participates in clustering and do not account for newcomer devices, limiting their fit to large-scale systems.The paper characterizes that assumption as impractical for large-scale federated learning.Source: B. Clustered Federated Learning · p. 3

A. Motivation

A FedAvg experiment on MNIST examines how client data heterogeneity relates to model discrepancy, accuracy, and convergence. Its reported measurements show substantial changes in discrepancy variance and maximum accuracy across heterogeneity settings.

A. Motivation

  • The motivation experiment uses convex multinomial logistic regression on MNIST, with client data limited to different numbers of classes.It uses 1,000 clients, selects 20 clients per round, trains for 300 rounds, and evaluates on local test data.Source: A. Motivation · p. 3
  • Higher data heterogeneity is associated with greater model discrepancy, lower accuracy, slower convergence, and more fluctuation in accuracy curves.The figure’s class-per-client settings represent decreasing heterogeneity as the number of classes increases from left to right.Source: A. Motivation · p. 3
  • As heterogeneity increases, discrepancy variance decreases 92.5% (from 0.11 to 0.0082), while max accuracy increases +4.3% (from 87.9% to 92.2%).The comparison is reported for FedAvg training on MNIST settings with different numbers of classes per client.Source: A. Motivation · p. 3, Table I · p. 3

B. Framework Overview

FedGroup statically groups clients using similarities between their local optimization solutions and uses EDC to cluster high-dimensional direction vectors. Groups train separate models, with an auxiliary server supporting cold starts and optional inter-group aggregation.

B. Framework Overview

  • FedGroup uses static client groups and EDC, a decomposed cosine-based distance designed for efficient clustering of high-dimensional direction vectors.The grouping is based on similarities between clients’ local optimization solutions; EDC is intended to avoid concentration effects from directly clustering high-dimensional parameters or directions.Source: B. Framework Overview · pp. 3–4
  • The overview assumes groups share a cloud server and clients are connected mobile devices, while noting that the schematic does not prescribe physical deployment.It also allows groups to be deployed on the cloud server or a mobile edge computing server.Source: B. Framework Overview · p. 4
  • An auxiliary server maintains the global model and supports assigning newcomers to groups through a cold-start algorithm.The overview also allows empty groups and clients that have not yet been assigned.Source: B. Framework Overview · p. 4
  • Each group trains on its clients using FedAvg, then group models undergo inter-group aggregation and are averaged to refresh the global model.FedGrouProx replaces the within-group FedAvg update with FedProx; FedGroup is the special case with µ = 0.Source: B. Framework Overview · pp. 4–5
  • The server does not broadcast optimization gradients to clients or groups; it retains them for newcomer cold starts.Clients and groups maintain their latest model and update.Source: B. Framework Overview · p. 4

C. Group Cold Start

FedGroup addresses client grouping by clustering local optimization directions, using EDC to make high-dimensional clustering more efficient. Its group cold start uses a subset of clients and can complete the clustering calculations with one communication round.

C. Group Cold Start

  • EDC addresses the limits of pairwise cosine similarity and MADC for efficient Euclidean clustering by providing a decomposed distance measure.MADC and the pairwise similarity matrix have the same computational complexity and are proximity measures, not distances for efficient Euclidean clustering.Source: C. Group Cold Start · p. 5
  • Truncated SVD decomposes client updates into m directions, so EDC calculates similarities between updates and those directions.This gives a low-dimensional embedding for clustering high-dimensional update directions.Source: C. Group Cold Start · p. 5
  • FedGroup clusters client update directions into m groups with K-Means++ after a low-dimensional embedding, requiring one communication round for the similarity and clustering calculations.The approach is unsupervised and can divide the global objective into m sub-objectives without requiring incongruent optimization goals.Source: C. Group Cold Start · p. 6
  • Group cold start pre-trains a random subset of αm clients, making the procedure practical when not all clients can remain active until training completes.The paper notes that network jitter can cause client dropout.Source: C. Group Cold Start · p. 6

D. Client Cold Start

FedGroup assigns newcomers to groups by comparing their optimization direction with the groups’ directions. It uses a pre-training gradient from the global initial model, avoiding the need to broadcast every group model for clustering.

D. Client Cold Start

  • The client cold start strategy assigns newcomers to groups most closely related to their optimization direction.The strategy addresses devices joining a dynamic federated network after group cold start.Source: D. Client Cold Start · p. 6
  • A newcomer’s pre-training gradient, computed from the global initial model, is used to assign it to the group with the minimum normalized cosine dissimilarity.This assignment avoids broadcasting all group models for clustering.Source: D. Client Cold Start · p. 6
  • FedGroup requires additional communication for pre-training parameters, but pre-training does not occupy a whole round and clients can continue training for E−1 epochs.The framework also considers newcomer devices when clustering clients.Source: D. Client Cold Start · p. 6

IV. EVALUATION

The evaluation reports results for FedGroup and FedGrouProx on four open datasets. It examines the grouping and newcomer-assignment strategies and studies the relationship between EDC and MADC.

IV. EVALUATION

  • The evaluation examines FedGroup and FedGrouProx on four open datasets and studies their performance improvements.The passage does not provide specific dataset-level results or values.Source: §IV · pp. 6–7
  • The experiments assess the clustering algorithm, including group cold start, and the newcomer assignment algorithm, or client cold start.Source: §IV · p. 7
  • The evaluation also studies the relationship between EDC and MADC.Source: §IV · p. 7
  • The implementation fixes random seeds for client selection and initialization, and code and data are publicly available.Source: §IV · p. 7

A. Experimental Setup

The experiments cover image classification, a synthetic federated dataset, and sentiment analysis, using specified client, local-training, and optimization settings. Performance is measured with test accuracy, with group models evaluated on their assigned clients.

A. Experimental Setup

  • FedGroup and FedGrouProx are evaluated on MNIST, FEMNIST, a synthetic dataset, and Sentiment140, with 20 local epochs, 20 selected clients per round, and batch size 10.The settings also use pre-training scale α = 20, disable inter-group aggregation, and follow recommended learning-rate and FedProx hyperparameter settings.Source: A. Experimental Setup · p. 7
  • MNIST uses 1,000 clients with two digit classes each, and the experiments train MCLR and MLP models.The MNIST MLP has one hidden layer with 128 units; FEMNIST uses 62 classes and an MLP with 512 hidden units.Source: A. Experimental Setup · p. 7
  • Sentiment140 is a sentiment-analysis task with 772 clients, each representing a different Twitter account, and uses an LSTM classifier.Source: A. Experimental Setup · p. 7
  • The comparison frameworks include FedAvg, FedProx, IFCA, and FeSEM.They are described respectively as vanilla FL, a heterogeneous-network optimizer, a framework estimating cluster identities, and an ℓ2 distance-based CFL framework.Source: A. Experimental Setup · p. 7
  • Performance is measured using top-1 accuracy, weighted across groups in proportion to each group’s test-data size.Group models are evaluated on the test sets of clients in their group; FedAvg and FedProx use test sets for all clients.Source: A. Experimental Setup · p. 7
  • For group models, test clients are historically assigned members; the maximum test accuracy during training is treated as the final score under early stopping.The number of groups is held constant across CFL frameworks for each dataset.Source: A. Experimental Setup · p. 7

B. Effects of Proposed Framework

FedGroup and FedGrouProx outperform several comparison frameworks, while ablations show that clustering and cold-start strategies both matter. The results also examine proximal-term stability, inter-group aggregation, and the efficiency of EDC.

B. Effects of Proposed Framework

  • RAC reduced accuracy by 7.86% on average and scored below FedAvg, while RCC moderately degraded accuracy except on Synthetic but still surpassed FeSEM.The authors conclude that combining the clustering algorithm with client cold start is effective.Source: B. Effects of Proposed Framework · p. 7
  • +26.9% absolute test accuracy on FEMNIST for FG-EDC over FeSEM; FG, FGP, and IFCA also significantly outperform other frameworks.TABLE III compares the frameworks on MNIST, FEMNIST, Synthetic, and Sent140.Source: B. Effects of Proposed Framework · p. 7, Table III · p. 8
  • FedGrouProx training was more stable than FedGroup, but the results do not establish a significant accuracy benefit from the proximal term.Fig. 3 reports accuracy, mean training loss, and discrepancy on MNIST and FEMNIST.Source: B. Effects of Proposed Framework · p. 8, Figure 3 · p. 8
  • FedGroup maintained low initial discrepancy relative to IFCA and FeSEM, attributed to its group cold-start strategy, and converged faster than FedAvg.The paper notes that faster convergence can reduce communication consumption.Source: B. Effects of Proposed Framework · pp. 8–9
  • Inter-group aggregation slightly improved convergence on MNIST-MCLR and Sent140-LSTM, but other experimental sets did not improve as expected.The authors suggest groups may be highly specialized with few shared representations.Source: B. Effects of Proposed Framework · p. 9
  • EDC mapped approximately linearly from MADC and is described as its low-dimensional linear approximation; calculating EDC requires pre-training only αm clients.The authors describe this calculation as more computationally efficient and implementable than pairwise proximity.Source: Figure 5 · p. 8, B. Effects of Proposed Framework · p. 9

V. CONCLUSION

The conclusion presents FedGroup as a clustered federated-learning framework using efficient clustering and cold-start strategies, evaluated on four open datasets. It reports higher accuracy than several baselines and summarizes findings on FedGrouProx and EDC.

V. CONCLUSION

  • FedGroup significantly improved FEMNIST top-1 test accuracy by +26.9% compared with FedSEM.The conclusion reports superiority to FedAvg, FedProx, and FeSEM across four open datasets.Source: §V · p. 9
  • FedGroup uses efficient clustering and cold-start strategies, and the paper presents FedGrouProx as a variant incorporating the proximal term.The conclusion describes the frameworks as decomposed data-driven measure-based clustered federated learning.Source: §V · p. 9
  • FedGrouProx's proximal term made federated training more stable but did not significantly improve classification accuracy.Source: §V · p. 9
  • The conclusion describes EDC as an appropriate linear approximation of MADC and reports higher FedGroup accuracy than FedAvg, FedProx, and two random strategies across six models, except Sent140 for RCC.Source: §V · p. 9

Related papers

Loading 2010.06870v6…