PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Distribution Similarity Identification in Clustered Federated Learning via Principal Angles Between Client Data Subspaces

Saeed Vahidian, Mahdi Morafah, Weijia Wang, Vyacheslav Kungurtsev, Chen Chen, Mubarak Shah, Bill Lin

arXiv:2209.10526v1cs.LGcs.AIcs.DCmath.OC

TL;DR

Prior clustered federated learning methods identify client distribution similarities indirectly during training, which can take many rounds before clusters stabilize. PACFL uses one-shot truncated SVD signatures and principal angles to form clusters directly; the paper presents it as a framework spanning broad data heterogeneity, from shared to client-specific models.

  • Problem

    Prior clustered federated learning methods infer client distribution similarities indirectly during training, which can require many rounds before clusters stabilize.

    Source: §1 · p. 1

  • Method

    PACFL has clients send small sets of principal vectors from one-shot truncated SVD, which the server compares using principal angles between client data subspaces.

    Source: §1 · p. 2

  • Results

    PACFL is presented as addressing a broad range of client data heterogeneity beyond simpler forms such as label skew.

    Source: §4 · p. 7

  • Takeaways & Limitations

    PACFL spans shared training in one cluster for IID clients through separate client clusters for extremely Non-IID data.

    Source: §1 · p. 2

    The analysis assumes each client’s M samples are arranged as columns of an N-feature data matrix.

    Source: Overview of PACFL · p. 4

Abstract

from arXiv · show

Clustered federated learning (FL) has been shown to produce promising results by grouping clients into clusters. This is especially effective in scenarios where separate groups of clients have significant differences in the distributions of their local data. Existing clustered FL algorithms are essentially trying to group together clients with similar distributions so that clients in the same cluster can leverage each other's data to better perform federated learning. However, prior clustered FL algorithms attempt to learn these distribution similarities indirectly during training, which can be quite time consuming as many rounds of federated learning may be required until the formation of clusters is stabilized. In this paper, we propose a new approach to federated learning that directly aims to efficiently identify distribution similarities among clients by analyzing the principal angles between the client data subspaces. Each client applies a truncated singular value decomposition (SVD) step on its local data in a single-shot manner to derive a small set of principal vectors, which provides a signature that succinctly captures the main characteristics of the underlying distribution. This small set of principal vectors is provided to the server so that the server can directly identify distribution similarities among the clients to form clusters. This is achieved by comparing the similarities of the principal angles between the client data subspaces spanned by those principal vectors. The approach provides a simple, yet effective clustered FL framework that addresses a broad range of data heterogeneity issues beyond simpler forms of Non-IIDness like label skews. Our clustered FL approach also enables convergence guarantees for non-convex objectives. Our code is available at https://github.com/MMorafah/PACFL.

1 Introduction

Clustered FL can help groups of clients with different data distributions learn shared models, but prior methods discover clusters indirectly during training and may require many rounds. PACFL instead uses client data subspaces to identify distribution similarities directly, enabling one-shot clustering, a personalization–globalization trade-off, and matching for newcomer clients.

1 Introduction

  • Clustered FL is useful when client groups have substantially different local distributions, including differences arising from distinct tasks or mixtures beyond label skew.Clients in a cluster can leverage one another’s data; a single global model may not suit heterogeneous clients.Source: §1 · p. 1
  • Prior clustered FL methods learn distribution similarities indirectly during training, and noisy initial cluster models can mean many rounds are needed before clusters stabilize.Some approaches also require a prespecified cluster count or downloading all cluster models in each iteration.Source: §1 · p. 1
  • PACFL derives a small set of principal vectors from each client’s local data with one-shot truncated SVD, then sends those signatures to the server for clustering.The paper says clients send only 2–5 vectors out of approximately 500 and that local data is not sent.Source: §1 · p. 2
  • The server compares principal angles between client data subspaces to identify distribution similarities, addressing heterogeneity beyond label skews.The paper states that greater differences in data heterogeneity correspond to more orthogonal subspaces.Source: §1 · p. 2
  • PACFL spans one cluster for IID clients through one cluster per client for extremely Non-IID data, trading off globalization and personalization.The paper describes the latter endpoint as clients being best trained on their own local data.Source: §1 · p. 2
  • New clients can submit principal vectors to be matched to an existing cluster model or directed to form a new cluster when their distribution is not sufficiently similar.The matched client can further personalize the selected model with local training.Source: §1 · p. 2
  • The paper provides a convergence analysis of PACFL in supplementary material.Source: §1 · p. 2

2 Clustered Federated Learning

PACFL compares client data subspaces to identify distribution similarity and form clusters before training. Clients represent their data with truncated-SVD principal vectors, which the server uses to build a proximity matrix and cluster clients.

Preliminaries

  • Principal angles measure the separation between subspaces; the smallest principal angle is Θ1, and principal angle distance is a metric for subspace distance.For subspaces spanned by orthonormal vectors, the principal angles form an ordered sequence from 0 to π/2.Source: Preliminaries · p. 2

How Principal Angles Can Capture the Similarity Between Data/Features

  • The CIFAR-10 and SVHN subspaces have a smaller principal angle than the CIFAR-10 and USPS subspaces, and the four-dataset proximity matrix is reported to capture their similarities and differences accurately.Table 1 entries give the smallest angle and the sum of principal angles for each dataset pair.Source: Figure 1 · p. 2, How Principal Angles Can Capture the… · p. 3
  • Truncated SVD gives each dataset a small set of principal vectors, and the server compares subspaces using either the smallest angle or the sum of corresponding principal-vector angles.Smaller proximity-matrix entries indicate more similar datasets; Eq. 3 is described as the more rigorous measure when p > 1.Source: How Principal Angles Can Capture the… · p. 3

Overview of PACFL

  • Before training, clients send their principal vectors; the server forms a proximity matrix and can use hierarchical clustering when the number of clusters is unknown.Training then uses cluster membership and model parameters for within-cluster model averaging.Source: Overview of PACFL · p. 4
  • PACFL accommodates partial participation and arriving or departing clients, and can determine new clients’ cluster IDs without changing existing clients’ IDs.The method can form a fitting number of clusters without specifying that number in advance, unlike IFCA, which requires it a priori.Source: Overview of PACFL · p. 4
  • PACFL’s convergence analysis provides guarantees for non-convex objectives, while its computational complexity adds one-shot hierarchical clustering to FedAvg.The paper gives the clustering complexity as O(N^2), where N is the number of clients.Source: Overview of PACFL · p. 4

3 Experiments

Experiments evaluate PACFL on image-classification benchmarks under heterogeneous client partitions, including a four-dataset MIX-4 task. They examine cluster selection, the personalization–globalization trade-off, newcomer clients, and communication costs.

3 Experiments

  • Experiments use FMNIST, SVHN, CIFAR-10, and CIFAR-100, with LeNet-5 for the first three and ResNet-9 for CIFAR-100.Unless otherwise stated, experiments use 100 clients, sample 10% per round, and run 200 rounds with 10 local epochs and batch size 10.Source: §3 · pp. 4–5, Table 2 · p. 5

Globalization and Personalization Trade-off

  • Changing β sweeps PACFL from one global cluster to client-specific clusters, with intermediate settings trading globalization against personalization.Larger β reduces the cluster count; sufficiently small β yields one cluster per client, while sufficiently large β yields one cluster overall.Source: Globalization and Personalization… · pp. 5–6

Mixture of 4 Datasets

  • On MIX-4, PACFL finds four clusters and outperforms all SOTA methods, while IFCA with two clusters performs nearly as poorly as global baselines.MIX-4 assigns each client data from only one of USPS, CIFAR-10, SVHN, or FMNIST.Source: Mixture of 4 Datasets · p. 6, Table 3 · p. 6

How Many Clusters Are Needed?

Generalization to Newcomers

  • For unseen clients, PACFL matches a client to a cluster model that the client fine-tunes; it outperforms other baselines by a large margin.The reported experiment joins 20 clients after federation and gives them five personalization epochs.Source: Generalization to Newcomers · p. 7, Table 4 · p. 7

Communication Cost

  • PACFL requires only 30 communication rounds to converge on CIFAR-10, SVHN, and FMNIST, and beats IFCA and other SOTA methods under an 80-round budget.The comparison concerns Non-IID label skew (20%); Table 5 reports rounds needed to reach target accuracy.Source: Communication Cost · p. 7, Table 5 · p. 7

4 Conclusion

PACFL identifies client distribution similarities by analyzing principal angles between data subspaces spanned by clients’ principal vectors. It is designed to handle data heterogeneity beyond label skews.

  • PACFL directly identifies distribution similarities by comparing principal angles between client data subspaces spanned by principal vectors.Source: §4 · p. 7
  • The framework is intended to address data heterogeneity beyond simpler forms of Non-IIDness such as label skews.Source: §4 · p. 7
  • The approach is presented as a simple, effective framework for clustered federated learning.Source: §4 · p. 7

Supplementary Document

The supplementary document gathers preliminaries, convergence theory, consistency analysis, related work, additional experiments, and implementation details.

1 Preliminaries

The preliminaries define truncated SVD and hierarchical clustering, including the clustering threshold used in this paper.

  • Truncated SVD approximates a real matrix using p leading singular-vector pairs and their associated singular values.Source: §1 · p. 8
  • Agglomerative hierarchical clustering repeatedly merges the closest clusters using a linkage criterion until one cluster or C clusters remain.Source: §1 · p. 8
  • The paper calls β the clustering threshold, while linkage criteria determine inter-cluster distance.Source: §1 · p. 8

2 Convergence Analysis

The convergence analysis treats each PACFL cluster as a Local SGD process and examines how incorrectly assigned clients affect its guarantees. Under the stated gradient-bound condition, misidentification increases a constant without changing the convergence rate or biasing the solution.

2 Convergence Analysis

  • The analysis models each cluster as Local SGD with randomly selected clients taking local SGD steps before averaging.Source: §2 · p. 8
  • Misidentified clients are treated as having no guaranteed gradient similarity; their effect depends on a bound on their gradients.Source: §2 · pp. 8–9
  • Using data rather than loss values for cluster identification permits convergence analysis for non-convex objectives.Source: §2 · p. 9
  • For quadratic-growth objectives, the analysis states that the convergence rate matches the standard Local SGD rate.Source: §2 · p. 9
  • With bounded gradients for misidentified clients, convergence has no added bias or rate slowdown, only an increased constant.Source: §2 · p. 9

Proof of Theorems

  • The proof adapts prior Local SGD results, with incorrectly identified clients adding an error term proportional to their squared gradient bound.Source: Proof of Theorems · pp. 9–10

3 Consistency with other Distribution Similarity Metrics

PACFL is evaluated as a measure of distribution similarity using synthetic Gaussian pairs and comparisons with established distance measures.

3 Consistency with other Distribution Similarity Metrics

  • PACFL uses principal angles between data subspaces spanned by the first p significant left singular vectors to capture distribution similarity or dissimilarity.The comparison uses pairs of 100 samples from 20-dimensional multivariate Gaussians.Source: §3 · p. 10
  • The comparisons include Bhattacharyya distance, maximum mean discrepancy, and Kullback–Leibler distance.Source: §3 · p. 10
  • When the Gaussian covariance is fixed and the mean changes, the paper expects the second pair’s distributions to be farther apart than the first pair’s.The passage also describes an analogous comparison between the third and fourth columns.Source: §3 · p. 10

4 Background and Related Work

The background contrasts global, personalized, and clustered FL as responses to client data heterogeneity. It describes clustered FL as a way to group clients with similar local distributions, while noting communication and cluster-count challenges.

Global Federated Learning with Non-IID Data

  • Under Non-IID data, FedAvg can face weight divergence and unguaranteed convergence; FedProx, SCAFFOLD, and FedNova modify local updates to address aspects of heterogeneity.These global-model methods do not directly address local-level performance, and the global aggregate may differ from a highly personalized target.Source: Global Federated Learning with Non-IID… · pp. 10–11

Federated Learning from a Client’s Perspective

  • Personalized FL can fine-tune a global model locally, but that initialization may be poor when client distributions differ substantially.The section also situates multi-task learning as learning relationships among related tasks in a centralized manner.Source: Federated Learning from a Client’s… · p. 11

Clustered Federated Learning

  • Clustered FL groups clients with similar local distributions, but cluster formation may take many rounds; IFCA requires a preset cluster count and client model downloads.A fixed count may fit poorly when heterogeneity calls for more or fewer clusters.Source: Clustered Federated Learning · p. 11

5 Experimental Results

The experiments report PACFL accuracy and communication results under label-skew and Dirichlet partitions, and examine its clustering-threshold trade-off. Additional results include convergence curves and an illustrative CelebA clustering case study.

5 Experimental Results

  • The experimental section adds supplementary results to those presented in the main paper.Source: §5 · p. 11

Non-IID Label Skew

  • PACFL outperforms the compared state-of-the-art algorithms by a noticeable margin on 30% Non-IID label skew.Table 7 reports average accuracy over clients across datasets; each baseline is run three times for 200 rounds.Source: Table 7 · p. 11, Non-IID Label Skew · p. 11

Non-IID Dirichlet Label Skew

Communication Cost

  • PACFL is more communication-efficient than the baselines except LG; on CIFAR-100, it reduces cost by 1.6–3.2×, while IFCA uses 3,495.19 Mb to reach 50% accuracy.The text attributes IFCA’s cost to sending all server cluster models to participating clients each round.Source: Table 9 · p. 12, Communication Cost · p. 12, Table 10 · p. 12
  • For 30% Non-IID label skew, PACFL converges quickly and outperforms strong competitors in test accuracy except on SVHN.Figure 5 plots test accuracy against communication rounds under a budget of 80 rounds for personalized baselines.Source: Communication Cost · p. 12, Figure 5 · p. 13

Globalization vs Personalization Trade-off

6 Implementation

The implementation uses shared codebases and common client partitions for comparisons, with additional setup details for the MIX-4 experiment and selected hyperparameter choices.

6 Implementation

  • PACFL and baselines were implemented in PyTorch using public codebases, with global benchmarks using the Qinbin et al. codebase.The experiments ran on RCI clusters.Source: §6 · pp. 13–14

Hyper-parameters & Architectures

  • Comparisons use the same 100 clients and Non-IID partitions; LG-FedAvg is randomly initialized and evaluated by final, rather than maximum, local accuracy.IFCA uses two clusters in most experiments, while PACFL uses p = 3 for Tables 2, 7, and 3 and p = 5 for Table 8.Source: §6 · p. 14, Hyper-parameters & Architectures · p. 14

Implementation Details for MIX-4

  • For MIX-4, 100 clients receive 500 samples each, and FMNIST and USPS images are padded and replicated to match the 32 × 32, three-channel inputs.Experiments use LeNet-5, 50 communication rounds, and five local epochs; each baseline is run three times.Source: Implementation Details for MIX-4 · p. 14

Hyper-parameters & Architectures

  • CFL’s learning rate was lowered to address divergence, and its implementation omitted parameter γ.The authors also report using SGD with batch size 10 and the original papers’ settings for method-specific hyperparameters.Source: Hyper-parameters & Architectures · p. 14

Related papers

Loading 2209.10526v1…