wikillm

Paper · 2021-08-22 · cs.LG, cs.DC

Flexible Clustered Federated Learning for Client-Level Data Distribution Shift

FlexCFL groups federated clients once, before training: pre-trained update directions are reduced by truncated SVD and clustered with k-means++ on cosine features (EDC). Newcomers join the group with the closest direction, and clients whose label counts drift are reassigned. Author-reported gains over FeSEM: +8.4 on MNIST, +40.9 on FEMNIST (mean of three models), +11.3 on FashionMNIST.

Clustered federated learningFederated learningFederated aggregationk-means clusteringfederated-learningclusteringdistribution-shift

arXivPDFCodeMarkdown16 min read

AI-compiled by claude-haiku-5-5 on 2026-11-13, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.

In plain words

Federated learning trains one model across many devices, such as phones or sensors, without collecting their data. When the devices hold very different data, one shared model fits none of them well. Clustered federated learning sorts the devices into groups whose data behave alike, and each group trains its own model.

FlexCFL does this sorting once, before training starts. A small sample of devices does a little local training, and the direction each device's update points in is used to group the devices. A new device joins the group whose direction it matches. If a device's data changes enough, it is sorted again. The groups train in parallel and can optionally borrow a little from one another.

The aim is to keep the benefit of separate models for separate kinds of data without re-sorting every device in every round, which costs extra communication and computation.

TL;DR

FlexCFL is a clustered federated learning framework that groups clients once, before training, instead of re-clustering them each round. Clustering uses a decomposed cosine-similarity measure (EDC) on pre-training updates, followed by k-means++ §3.3. Newcomers and clients whose label counts shift are reassigned by update direction §3.4. Author-reported gains over FeSEM, and accuracy close to IFCA with lower communication overhead §5.2. The official code has no LICENSE file and differs from the paper in several places (see Paper vs code).

Problem

With statistically heterogeneous (non-IID, imbalanced) client data, a single consensus model degrades, and the local models diverge from the global one §1 §2.1. Clustered FL trains several group models, but earlier methods are costly: recursive bi-partitioning needs several rounds, some methods broadcast all group models every round, and clustering by pairwise proximity is recomputed at runtime §2.2 §3.1. Existing CFL frameworks also assume every client takes part in clustering and do not handle newcomers §2.2. Client-level distribution shift, where a client's data changes over time, had received little study §1 §3.1.

The motivating experiment is a convex multinomial logistic regression with FedAvg on MNIST §3.1. As the number of classes per client rises from 1 to 10 (IID), the variance of the discrepancy falls from 0.11 to 0.0082 and the maximum accuracy rises from 87.9% to 92.2% tab. 1.

Table 1. FedAvg on MNIST with different numbers of classes per client tab. 1.

# ClassesDiscrepancy meanDiscrepancy varianceAccuracy maxAccuracy medianRounds to 85%
10.7670.1187.9%79.3%39
30.7670.07390.9%87.0%14
50.6850.02191.3%90.0%10
10 (IID)0.6270.008292.2%91.5%4

Method

Objectives

The FL objective is a weighted sum of client losses, f(w) = Σ_k p_k F_k(w), with p_k ≥ 0 summing to 1 eq. 1. Each F_k is the expected loss over client k's data distribution eq. 2 §2.1.

Discrepancy motivation

Discrepancy at round t is the mean norm difference between the selected clients' weights and the global weights eq. 3 §3.1. The paper's argument is that high heterogeneity makes models diverge, and that splitting the joint objective into group objectives can reduce this §3.1.

Group cold start (one-time clustering) alg. 3 eq. 4-7

  1. Sample α·m clients, with α = 20 and m groups, and have each pre-train from the initial model w0 §3.3 alg. 3.
  2. Stack their updates ΔW, one row per client alg. 3.
  3. Compute the top-m directions of ΔW^T with truncated SVD §3.3 alg. 3.
  4. Score each client update against each direction with cosine similarity eq. 4 eq. 5.
  5. Cluster the rows into m groups with k-means++ on the EDC features eq. 7 §3.3.
  6. Set each group's optimisation direction to the average of its members' updates alg. 3.

EDC is defined as an Euclidean distance between the cosine vectors of two clients against the m directions, scaled by 1/m eq. 7. The paper also gives MADC, a mean absolute difference of pairwise cosines. It is a proximity measure rather than a Euclidean distance, so the paper clusters it hierarchically with complete linkage eq. 6 §3.3. The paper argues that the expectation of the cosine similarity stays constant as the dimension grows, and that the SVD step keeps the cost to O(m²d²) rather than O(n²d²) for n clients §3.3.

Pseudocode
# Group cold start  [alg. 3] [eq. 7]
# Input:  clients, m (groups), alpha (pre-training scale), w0
# Output: m group directions, one per group

def group_cold_start(clients, m, alpha, w0):
    # Pre-train a random sample of alpha*m clients from w0  [alg. 3]
    sample = random_sample(clients, alpha * m)
    updates = [pretrain_update(c, w0) for c in sample]
    # One row per pre-trained client, one column per parameter  [alg. 3]
    delta_w = stack(updates)                          # (alpha*m, d)
    # Top-m directions of delta_w^T via truncated SVD  [§3.3] [eq. 7]
    directions = truncated_svd(delta_w.T, m)          # (d, m)
    # EDC features: cosine of each update with each direction  [eq. 7]
    features = cosine_matrix(delta_w, directions.T)   # (alpha*m, m)
    # Cluster the features into m groups with k-means++  [§3.3]
    labels = kmeans_plus_plus(features, m)
    # Group direction is the mean of its members' updates  [alg. 3]
    group_directions = []
    for j in range(m):
        members = [i for i in range(len(sample)) if labels[i] == j]
        group_directions.append(mean_of(updates, members))
    return group_directions

Newcomers eq. 8 §3.4

A client without a group is pre-trained from the initial model w0 and joins the group whose direction is closest, measured by the normalised cosine dissimilarity eq. 8 §3.4. The server stores the group directions and w0 so that the client can be moved later §3.4.

Pseudocode
# Newcomer assignment  [eq. 8] [§3.4]
# Dissimilarity is (1 - cos) / 2 between the newcomer's pre-training
# update and each group direction.

def assign_newcomer(client, groups, w0):
    # Pre-train from the initial model, not from any group  [§3.4]
    update = pretrain_update(client, w0)
    dissimilarities = [
        (1 - cosine(update, g.direction)) / 2 for g in groups
    ]
    return groups[argmin(dissimilarities)]

Training round alg. 2 §3.2

Each round, the server runs the following steps alg. 2:

  1. For each client, test for distribution shift and, if the test fires, redo its cold start locally alg. 2 lines 4-6 eq. 9.
  2. Sample K clients at random alg. 2 line 7.
  3. Each group runs FedAvg on the selected members of that group, weighting clients by training-set size alg. 2 lines 8-11 alg. 1. A group with no selected member keeps its model alg. 2 line 153.
  4. Inter-group aggregation with rate η_g, which is skipped when η_g = 0 alg. 2 line 13 eq. 20.

With η_g = 0 the framework is pluralistic. With η_g > 0 the paper calls it semi-pluralistic §3.2. The paper's inter-group rule is additive eq. 20.

Pseudocode
# FlexCFL training round  [alg. 2] [eq. 20]
# Input:  groups (model, direction), clients, K, eta_g, w0
# Output: updated group models

def flexcfl_round(groups, clients, K, eta_g, w0):
    # Migrate clients whose data shifted, before selection  [alg. 2]
    for c in clients:
        if distribution_shift(c):
            c.group = assign_newcomer(c, groups, w0)
    # Sample K clients for this round  [alg. 2 line 7]
    selected = random_sample(clients, K)
    # Each group runs FedAvg on its selected members  [alg. 2 lines 8-11]
    for g in groups:
        members = [c for c in selected if c.group is g]
        if members:
            g.model = fedavg(members, g.model)
        # An empty group keeps its model  [alg. 2 line 153]
    # Inter-group aggregation, skipped when eta_g = 0  [alg. 2 line 13]
    for g in groups:
        others = [h.model for h in groups if h is not g]
        # norm is over all parameters of the model  [eq. 20]
        g.model = g.model + eta_g * sum(w / norm(w) for w in others)
    return groups

Distribution shift and migration eq. 9 §3.4

Before each round the paper checks whether each client's training distribution has changed, using a Wasserstein distance alg. 2 line 4. The reference distribution is not specified in the paper. If the distance exceeds τ_i = (0.2 / |C|) · n_i, where |C| is the number of labels and n_i is the client's training-set size, the client is cold-started again eq. 9 §3.4. The paper states that a change of 20% of the training data counts as a shift §3.4.

Pseudocode
# Distribution-shift test, run before each round  [eq. 9] [§3.4]
# The Wasserstein distance is implemented as in the code (see Pitfalls).

def distribution_shift(client):
    # Current training label counts, one entry per class
    counts = label_counts(client.train_labels)        # (C,)
    # Threshold tau = 0.2 * n / C  [eq. 9]
    tau = 0.2 * client.n / num_classes
    # Wasserstein distance between counts and reference counts  [§3.4]
    distance = wasserstein(counts, client.reference_counts)
    return distance > tau

Convergence §4 eq. 10-22

The analysis assumes that each client's local loss F_{k,g} is convex, M-Lipschitz and L-smooth §4. The group loss is the weighted sum of its clients' losses §4, definition 1. Without inter-group aggregation, the loss gap between the group model and a virtual centrally trained group model is bounded by (δM/L)((ηL+1)^E − 1), where δ is the intra-group gradient divergence eq. 13 eq. 19. Inter-group aggregation adds η_g(|G|−1) to this bound eq. 22. The bound degrades to the no-aggregation case when η_g = 0 or |G| = 1 §4.

Hyperparameters

NameValueWhereNotes
Clients per round K20§5.1 §3.1Code default is 20 trainer_utils.py
Local epochs E10 (evaluation); 20 (motivation)§5.1; §3.1Code default 10 trainer_utils.py
Local batch size B10§5.1; §3.1Code default 10 trainer_utils.py
Rounds T300§3.1; fig. 6 captionCode default 300 trainer_utils.py
Pre-training scale α20§5.1; alg. 3Pre-trains α·m clients
Number of groups m3 (MNIST); 5 (FEMNIST, FashionMNIST)fig. 3; fig. 4 captionsSynthetic: not stated. Code uses 5 trainer_utils.py
Learning rate η (motivation)0.03§3.1Code uses 0.03 for MNIST trainer_utils.py
Learning rate η (evaluation)not stated§5.1Paper says "consistent with" FedProx's recommendation. Code: FEMNIST 0.003, Synthetic 0.01, FashionMNIST 0.005 trainer_utils.py, trainer_utils.py, trainer_utils.py
Inter-group rate η_g0.1 (Table 3, FlexCFL-η_g); 5.0 (Table 4)tab. 3; tab. 4Default 0 in code trainer_utils.py
Shift threshold factor0.2eq. 9 §3.4Fraction of training data that counts as a shift
Swap probability0.05§5.3 tab. 4 captionFor swap-all and swap-part
Incremental release25% of data every 50 rounds§5.3 tab. 4 captionRelease steps at rounds 0, 50, 100, 150 groupbase.py
Final scoreMaximum test accuracy over training§5.1Early-stopping style selection; see Pitfalls
Proximal μnot used by FlexCFLalg. 2 inputListed in the input but FedAvg is used
L2 regularisationnot stated—Code applies 0.001 on dense kernels mlp.py
Random seednot stated§5.1 says seeds are fixedCode default 2077 trainer_utils.py

Datasets and models §5.1 tab. 2. The MNIST CNN is listed in the table but not described in the text. Its parameter count, 50,186, matches the code's model (see Paper vs code).

Table 2. Federated datasets and models tab. 2.

DatasetDevicesSamplesModeld_w
MNIST1,00069,035MCLR7,850
MNIST1,00069,035MLP (128 hidden)101,770
MNIST1,00069,035CNN50,186
FEMNIST20018,345MCLR7,850
FEMNIST20018,345MLP (512 hidden)407,050
FEMNIST20018,345CNN325,578
Synthetic(1,1)10075,349MCLR610
FashionMNIST50072,505CNN3,274,634

Results

Author-reported. Setup: top-1 accuracy, weighted by test-set size, with the maximum over training taken as the final score §5.1. Baselines are FedAvg, FedProx, IFCA, FeSEM and FedGroup §5.1. The paper reports no error bars, repeated runs or variance across seeds.

Table 3. Accuracy without distribution shift. RCC and RAC are ablations. The paper's bold best-cell marks are not reproduced tab. 3.

MethodMNIST MCLRMNIST MLPMNIST CNNFEMNIST MCLRFEMNIST MLPFEMNIST CNNSynthetic MCLRFashionMNIST CNN
FedAvg89.492.797.374.979.695.266.989.2
FedProx90.994.594.676.779.496.380.789.1
IFCA94.295.897.885.887.998.191.390.9
FeSEM84.689.892.043.757.957.377.081.3
RCC93.496.298.388.893.998.786.091.2
RAC88.291.695.367.069.486.1—85.0
FlexCFL95.8 (↑11.2)97.0 (↑7.2)99.0 (↑7.0)90.1 (↑46.4)92.9 (↑35.0)98.7 (↑41.4)85.6 (↑8.6)92.6 (↑11.3)
FlexCFL-η_g95.296.698.886.088.998.580.392.4

The ↑ values are gains over FeSEM, as the paper defines them tab. 3 caption. The text's headline gains over FeSEM are +8.4 on MNIST and +40.9 on FEMNIST, which are means over the model variants (by our arithmetic the three MNIST cells average 8.47), and +11.3 on FashionMNIST, a single cell §5.2 §1. The +3.5 on FashionMNIST over FedProx is a single cell (92.6 vs 89.1) tab. 3.

Table 4. Accuracy under client-level distribution shift. Each cell gives swap-all / swap-part / incremental. FedGroup is FlexCFL without migration. The paper's bold best-per-setting marks are not reproduced tab. 4.

MethodMNIST MCLRMNIST MLPMNIST CNNFEMNIST MCLRFEMNIST MLPFEMNIST CNNSynthetic MCLRFashionMNIST CNN
FedAvg89.9 / 89.2 / 89.992.0 / 92.7 / 92.397.3 / 97.5 / 95.477.1 / 77.3 / 69.980.3 / 82.1 / 74.295.7 / 95.9 / 74.163.4 / 71.1 / 78.289.4 / 89.3 / 83.6
IFCA64.5 / 85.0 / 90.263.4 / 83.7 / 92.066.5 / 86.6 / 92.676.3 / 56.7 / 77.378.7 / 63.4 / 78.786.1 / 84.0 / 82.889.3 / 96.8 / 91.673.8 / 82.2 / 85.6
FeSEM84.7 / 83.6 / 84.589.6 / 89.3 / 84.092.2 / 89.6 / 80.041.5 / 40.6 / 37.758.9 / 57.1 / 48.823.1 / 59.8 / 19.857.4 / 77.3 / 69.482.2 / 81.8 / 78.2
FedGroup87.1 / 86.3 / 95.191.7 / 89.9 / 95.696.5 / 95.7 / 97.358.1 / 64.6 / 85.866.1 / 67.8 / 87.587.6 / 90.9 / 88.284.4 / 93.5 / 89.886.0 / 86.4 / 88.8
FlexCFL95.1 / 91.7 / 95.193.8 / 93.3 / 95.697.0 / 97.0 / 97.484.7 / 68.5 / 84.886.6 / 73.4 / 87.593.7 / 94.7 / 88.685.0 / 91.7 / 89.890.8 / 87.5 / 88.7
FlexCFL-η_g89.1 / 90.2 / 89.193.4 / 93.5 / 92.497.8 / 97.9 / 95.483.1 / 90.2 / 89.189.9 / 81.5 / 85.797.2 / 96.6 / 86.158.0 / 76.5 / 80.291.8 / 89.3 / 87.6

The paper's distribution-shift claims are averages over model variants. For example, +2.2 on MNIST under swap-all, against FedAvg, is the mean of the three MNIST rows §5.3 tab. 4. By our arithmetic, those three rows give (95.1−89.9) + (93.8−92.0) + (97.0−97.3) over 3, which is about 2.2. The per-model differences are not reported individually.

Paper vs code

Code: github.com/morningD/FlexCFL at commit 968b5fa8528eb8d9fc177023ed6693f623ee1db9, cloned with git clone --depth 1. The paper links this repository §5, so it is the official code. It contains no LICENSE file, so no code may be copied verbatim. Everything below is a paraphrase.

  • Inter-group rule differs. The paper's update is additive: w̃_j = w_j + η_g · Σ_{l≠j} w_l / ‖w_l‖ alg. 2 line 13 eq. 20. The code divides the sum by the total weight, so each group's new model is a weighted average of itself and the others groupbase.py. The sum is over the models w_l / ‖w_l‖, but the denominator is 1 + η_g · Σ_{l≠j} 1/‖w_l‖. The output scale and the bound in eq. 22 therefore do not match the code.

  • Pre-training is not one epoch. The paper's group cold start calls ClientUpdate from Algorithm 1, which runs E local epochs alg. 3 alg. 1. The text says pre-training takes less than a round §3.4. The code calls pretrain(..., iterations=50), which runs 50 mini-batch SGD steps of batch 10, not epochs fedgroup.py, fedgroup.py, client.py, actor.py. For clients with fewer than 500 samples, 50 steps cover more than one epoch. The paper does not state the length.

  • Group test uses stale client models. The paper evaluates each group model on its clients' test sets §5.1. With the default eval_locally = False trainer_utils.py, Group.test calls each client's test(), which uses the client's own latest_params group.py, client.py. The group sets those parameters only when the client trains in that round group.py, and local training does not update them actor.py. The evaluated model is therefore the group model as it was at each client's last selection, not the current group model. A client never selected keeps the initial parameters. With eval_locally = True the paper's description holds group.py, actor.py. The shipped entry points never set it main.py, test.ipynb. Which setting produced the reported numbers is not stated.

  • Shift test uses counts, not labels. The paper specifies a Wasserstein distance only in outline §3.4 alg. 2 line 4. The code calls scipy.stats.wasserstein_distance(curr_count, train_label_count) on the two count vectors client.py. This compares the two sets of counts as values, so the distance does not depend on which class each count belongs to.

  • Shift threshold uses the initial size. The code sets emd_threshold = (1/C) · train_size · 0.2 once, in the constructor client.py. The paper's n_i is not specified as initial or current eq. 9.

  • Migration needs the flag and the threshold. Swaps set distribution_shift = True groupbase.py, groupbase.py. A client is migrated only if the count test also exceeds the threshold, and the flag stays set otherwise fedgroup.py. A swapped client below the threshold is checked again in later rounds.

  • Newcomers are assigned when selected. The paper assigns a newcomer when it joins §3.4. The code cold-starts a client when it is first selected for training and has no group fedgroup.py.

  • K-means details. The paper uses k-means++ on the EDC measure with a 1/m factor eq. 7 §3.3. The code uses scikit-learn KMeans with random_state=seed and max_iter=20 on the cosine features, without the 1/m factor fedgroup.py. Scaling all features by a constant does not change k-means assignments, so the 1/m factor has no effect on the result. n_init is not set, so the scikit-learn default applies. The paper states neither max_iter nor n_init.

  • Group and direction are averaged differently. alg. 3 averages updates into w_0^{(g_j)} and then subtracts w_0. The code averages full client models into the group model and averages updates into the direction fedgroup.py, fedgroup.py.

  • Regularisation and optimiser are not in the paper. The code applies an L2 kernel regularizer of 0.001 to the Dense layers of the MNIST MLP and MCLR, the FEMNIST MLP and the FEMNIST CNN mlp.py, mlp.py, cnn.py, mclr.py. The MNIST CNN and FashionMNIST CNN have no regularizer cnn.py, cnn.py. The optimiser is plain SGD without momentum mlp.py.

  • MNIST CNN matches its count. The paper's text does not describe the MNIST CNN §5.1. The code's model has convolutions of 32 and 64 filters, 3×3, same padding, 2×2 max-pooling, dropout 0.5 and a 10-way dense layer cnn.py. Its parameter count, 320 + 18,496 + 31,370 = 50,186, matches tab. 2.

  • Learning rates and epochs differ. The paper gives η = 0.03 and E = 20 for the motivation experiment §3.1 and says only that the evaluation learning rates follow FedProx §5.1. The code sets learning rates per dataset trainer_utils.py, trainer_utils.py, trainer_utils.py, trainer_utils.py and defaults to 0.003 trainer_utils.py. The README also gives 0.003 README.md. The repository contains no motivation script.

  • Auxiliary model comment is wrong. The round loop says empty groups are not aggregated into the auxiliary model groupbase.py. It includes every group returned by the server, and a trainable group with no selected client returns its unchanged parameters server.py, group.py.

  • Proximal term is disabled. The algorithm input lists μ alg. 2, and the FedProx line is commented out in the code fedgroup.py.

  • Coverage. The repository's shipped configurations cover FEMNIST-MLP only test.ipynb, test.ipynb, main.py. As far as this card read, the other rows of Tables 3 and 4 are not reproducible from the repository as shipped.

Pitfalls

  • Unstated cold-start length. The pre-training length is not in the paper. The code uses 50 mini-batch steps fedgroup.py. Results depend on this choice, so match it exactly when reimplementing.
  • Memory of the update matrix. The cold start stores αm update vectors of size d_w. For FashionMNIST's CNN (d_w = 3,274,634 tab. 2), with α·m = 100 rows, this is about 3.3×10⁸ values: roughly 1.3 GB at float32 or 2.6 GB at float64. This is our arithmetic. The paper does not state memory use.
  • Per-round checks. Every warm client gets a Wasserstein check each round fedgroup.py. Each migration costs one more pre-training run for that client fedgroup.py.
  • Inter-group rate meaning. The η_g values in tab. 3 (0.1) and tab. 4 (5.0) are reported under the paper's additive rule. Under the code's normalised rule, the same values give a different mixing strength (see Paper vs code).
  • Final score is test-selected. The final score is the maximum test accuracy over training §5.1. This is optimistic, because the choice uses the test data. The paper says it did not tune the model on test results and so ignores test-data leakage §3.1.
  • Test sets move with swapped data. Under swap-all, the client's test data are swapped with its train data groupbase.py. A client's test accuracy then reflects the data, not the device.
  • Headline numbers are averages. Several headline percentages are means over model variants, not single cells: +8.4 and +40.9 over FeSEM tab. 3; and +2.2 on MNIST under swap-all over FedAvg tab. 4. The +10.6 on FEMNIST over FedAvg in the abstract is likewise a mean of three rows; by our arithmetic it is about 10.7. The text does not say so.
  • Convexity gap. The analysis assumes convex, Lipschitz, smooth losses §4. The experiments use non-convex MLPs and CNNs §5.1. The bounds do not cover those models formally.
  • Proof typo. In the proof of Lemma 2, the induction writes g(e) where h(e) is meant §4, eq. 17.
  • Introduction typo. The introduction says "FedSEM" where the baseline is FeSEM §1.
  • Simulated shift. The three shift types are simulated and do not change the global data union §5.3. They do not model real drift.
  • No variance. There are no error bars or repeated seeds. Differences of a point or two in tab. 3 or tab. 4 are not established.

Lineage

  • Builds on: FedAvg for local training and aggregation §2.1; clustered FL methods CFL, IFCA, FeSEM and FL+HC §2.2.
  • Preliminary version: FedGroup, accepted at ISPA 2021 according to the author note; this paper extends it with the inter-group rule, migration and the convergence analysis §5.1.
  • Compared against: FedAvg, FedProx, IFCA, FeSEM and FedGroup §5.1.
  • Superseded by: not stated.

Source and license

Adapted from “Flexible Clustered Federated Learning for Client-Level Data Distribution Shift” by Moming Duan, Duo Liu, Xinyuan Ji, Yu Wu, Liang Liang, Xianzhang Chen, Yujuan Tan (arXiv:2108.09749), used under CC BY 4.0. Changes: condensed and restructured for implementation, with tables, equations and algorithms taken from the paper and its code, each cited to its source. Not affiliated with or endorsed by the authors. Code citations refer to https://github.com/morningD/FlexCFL at commit 968b5fa8528e (none (no LICENSE file in repository)). Any quoted code is shown under that license.