PaperlayerView exact revision on arXiv

Source-linked AI summary

FedCor: Correlation-Based Active Client Selection Strategy for Heterogeneous Federated Learning

Minxue Tang, Xuefei Ning, Yitu Wang, Jingwei Sun, Yu Wang, Hai Li, Yiran Chen

arXiv:2103.13822v3cs.LGcs.DC

TL;DR

Client-wise data heterogeneity challenges federated learning, while active selection methods that ignore client loss correlations achieve only marginal improvement. FedCor models client loss changes with a Gaussian Process and selects clients using correlations; it reports improved convergence rates on FMNIST and CIFAR-10.

  • Problem

    Client-wise data heterogeneity challenges FL, while active selection methods that treat client losses independently neglect loss correlations and achieve only marginal improvement.

    Source: §1 · p. 1

  • Method

    FedCor models client loss changes with a Gaussian Process and uses the modeled correlations for active client selection, alongside a communication-efficient GP training method.

    Source: §1 · p. 2

  • Results

    FedCor improves convergence rates by 34% ∼99% on FMNIST and 26% ∼51% on CIFAR-10.

    Source: §1 · p. 2

  • Takeaways & Limitations

    FedCor is reported to accelerate and stabilize training under highly heterogeneous settings.

    Source: §6 · p. 8

    The GP loss-change premise is supported by a preliminary sampled-selection experiment, and the correlation rationale assumes dataset similarities remain invariant during FL.

    Source: §4.2 · p. 3, §4.5 · p. 5

Abstract

from arXiv · show

Client-wise data heterogeneity is one of the major issues that hinder effective training in federated learning (FL). Since the data distribution on each client may vary dramatically, the client selection strategy can significantly influence the convergence rate of the FL process. Active client selection strategies are popularly proposed in recent studies. However, they neglect the loss correlations between the clients and achieve only marginal improvement compared to the uniform selection strategy. In this work, we propose FedCor -- an FL framework built on a correlation-based client selection strategy, to boost the convergence rate of FL. Specifically, we first model the loss correlations between the clients with a Gaussian Process (GP). Based on the GP model, we derive a client selection strategy with a significant reduction of expected global loss in each round. Besides, we develop an efficient GP training method with a low communication overhead in the FL scenario by utilizing the covariance stationarity. Our experimental results show that compared to the state-of-the-art method, FedCorr can improve the convergence rates by $34\%\sim 99\%$ and $26\%\sim 51\%$ on FMNIST and CIFAR-10, respectively.

1. Introduction

Client-wise data heterogeneity challenges FL, and active selection strategies that ignore client correlations achieve only marginal improvement. FedCor models client loss changes with a Gaussian Process and uses correlations to select clients, with reported convergence gains on FMNIST and CIFAR-10.

1. Introduction

  • Prior active selection methods favor clients with larger losses but neglect client correlations, yielding only marginal improvement.The paper frames correlation-based selection as a way to address accuracy degradation associated with data heterogeneity.Source: §1 · p. 1
  • Clients contribute unequally, and their effects are interdependent because local updates are aggregated.A large balanced dataset may reduce losses for many clients, while a small biased dataset may increase other clients’ losses.Source: §1 · p. 1
  • In a toy experiment, independent selection of the two highest-local-loss clients fails to reduce global loss, whereas correlation-aware selection achieves an almost lowest global loss.The comparison is among the “Ind Result,” “Cor Result,” and “Opt Result” selections.Source: §1 · pp. 1–2
  • FedCor models client loss changes with a Gaussian Process and derives an interpretable selection strategy intended to reduce expected global loss each round.The strategy is based on client loss correlations.Source: §1 · p. 2
  • FedCor trains its Gaussian Process using covariance stationarity to reduce communication cost, and experiments indicate that the trained model captures client correlations well.Source: §1 · p. 2
  • Experimental results show that FedCor stabilizes training convergence and significantly improves convergence rates by 34% ∼99% on FMNIST and 26% ∼51% on CIFAR-10, respectively.Source: §1 · p. 2

2. Related Work

Related work addresses statistical heterogeneity through changes to local training losses or aggregation, while active selection strategies choose clients rather than sampling uniformly. The cited active selection methods do not account for correlations between clients.

2. Related Work

  • Prior heterogeneous-FL methods modify local losses or aggregation, including regularization-based approaches [10] [18] [20] [26] and aggregation methods aimed at reducing variance [24] [32].The section focuses on statistical heterogeneity, including non-IID and imbalanced data distributions.Source: §2 · p. 2
  • Active client selection chooses clients strategically each round rather than uniformly, with prior methods favoring clients with large local loss [6] or selecting the largest-loss clients from a sampled subset [4].The sampled subset has size d > C, from which C clients are selected.Source: §2 · p. 2
  • The cited active selection methods do not consider correlations between clients when selecting them.Source: §2 · p. 2

3. Preliminary

The preliminary section defines FL’s goal as finding a global model that performs well across clients and expresses the global loss through client losses. It then describes partial participation and local updating followed by server aggregation.

3. Preliminary

  • FL seeks a global model with strong performance across all N clients, and its global loss is a weighted sum of local losses.Each client’s weight is proportional to its local dataset size.Source: §3 · p. 2
  • A client’s local loss is the average objective loss over its local dataset, evaluated at the model.Source: §3 · p. 2
  • In each communication round, the server selects C clients to train locally, then averages their trained models to produce the next global model.The local updates can be expressed as cumulative gradients from the current global model.Source: §3 · p. 2

4. Methodology

FedCor formulates client selection as maximizing expected global loss decrease, models client loss changes with a Gaussian Process, and selects clients using predicted correlations. Its GP training method reuses covariance and historical information to reduce communication overhead.

4.1. Problem Formulation

  • FedCor seeks client selections that maximize global loss decrease each round, while avoiding costly repeated trials of candidate selections.The paper reformulates the objective probabilistically so predictions of selected clients’ loss changes can inform the global-loss estimate.Source: §4.1 · p. 3

4.2. Modeling Loss Changes with GP

  • PCA histograms of sampled loss changes support modeling their one-round prior distribution with a Gaussian Process.The paper reports that a Gaussian density approximates the plotted principal-component samples well.Source: §4.2 · p. 3

4.3. Client Selection Strategy

  • FedCor iteratively predicts client loss changes, selects a client minimizing posterior expected overall loss, and updates the GP posterior without measuring global loss changes.Unlike traditional Bayesian Optimization [3], its selection uses predictions rather than measured global-loss changes, which would add communication overhead in FL.Source: §4.3 · p. 4

4.4. Insights into Our Selection Strategy

  • The selection criterion favors clients correlated with others while penalizing correlation with already selected clients, reducing redundancy and supporting more diverse data.The paper links this redundancy penalty to reduced variance and more stable training.Source: §4.4 · pp. 4–5

4.5. Training GP in FL

  • Covariance similarity stays above 0.97 for FMNIST and 0.95 for CIFAR-10, supporting less frequent GP updates.The reported similarities are measured between covariance matrices separated by Δt=10 for FMNIST and Δt=50 for CIFAR-10.Source: §4.5 · p. 5
  • FedCor trains low-rank client embeddings with a linear kernel, reuses historical samples, and updates the embeddings only every Δt rounds to reduce GP-training communication.The method reports communication reduction with large Δt and S=1 while guaranteeing performance.Source: §4.5 · p. 5

5. Experiments

Across FMNIST and CIFAR-10 heterogeneity settings, FedCor converges faster and more stably than the baselines. Experiments also examine GP update frequency, annealing, and learned client embeddings.

5.1. Experiment Settings

  • Experiments cover FMNIST and CIFAR-10 across balanced 2SPC and 1SPC partitions and an unbalanced Dirichlet partition, with FedAvg results averaged over five seeds.The experiments also use a uniform-selection warm-up before normal GP-based client selection.Source: §5.1 · pp. 6–7

5.2. Convergence under Heterogeneous Settings

  • FedCor reaches specified accuracy 34% ∼99% and 26% ∼51% faster than Pow-d on FMNIST and CIFAR-10, respectively, while achieving the highest test accuracy and fastest convergence.Its learning curves are also smoother and less noisy than those of other methods.Source: §5.2 · p. 7

5.3. Results with Larger GP Training Interval

  • Larger GP training intervals degrade performance only slightly; even without post-warm-up updates, FedCor remains faster than random selection.Figure 5 compares test accuracy across intervals and datasets under 2SPC, 1SPC, and Dir.Source: §5.3 · p. 7, Figure 5 · p. 7

5.4. Influence of Annealing Coefficient

  • With smaller β, client selections appear more uniform while learning curves remain nearly invariant, and FedCor still consistently improves on uniform sampling.The authors conclude that selecting a good group matters more than selecting good individuals alone.Source: §5.4 · p. 8, Figure 6 · p. 8

5.5. Visualization of Client Embedding

  • Under 1SPC, clients with the same label cluster in the learned embedding, which the authors interpret as evidence that FedCor captures client correlations.Embedding vectors are normalized so their distances reveal correlation.Source: §5.5 · p. 8, Figure 7 · p. 8

6. Conclusion and Future Work

FedCor models client correlations with a Gaussian Process to guide client selection and trains that model with low communication overhead. Experiments on FMNIST and CIFAR-10 show faster, more stable training; extending the approach beyond cross-silo FL remains future work.

6. Conclusion and Future Work

  • FedCor combines GP-modeled client correlations, interpretable client selection, and a GP training method designed for low communication overhead.The paper reports faster and more stable training on FMNIST and CIFAR-10, and identifies extension to other tasks and cross-device FL as future directions.Source: §6 · p. 8

A. Theoretical Analysis

The analysis assumes that a uniformly sampled client selection produces a Gaussian global model update. Under a first-order approximation, the resulting client loss changes follow a Gaussian Process.

A. Theoretical Analysis

  • Under Assumption 1, uniform client selection makes the global model update Gaussian in each communication round.The assumption is motivated by the analogy between federated updates and stochastic-gradient updates.Source: §A.1 · p. 11
  • Given that assumption, client loss changes follow a Gaussian Process under a first-order approximation.The corollary states that the loss changes for any client subset have a multivariate Gaussian distribution.Source: §A.1 · p. 11
  • Uniform sampling is required for the prior assumption, but final client selection need not be uniform because predictions use the GP posterior conditioned on selected clients.The posterior during iterative selection reflects both previously selected clients and uniform sampling from the remaining clients.Source: §A.1 · p. 11

A.2. Proof of Lemma 1

FedCor's selection analysis rests on an approximate probabilistic reformulation of expected global loss decrease. It develops a simpler proxy for iterative client selection and gives that proxy a convergence guarantee.

A.2. Proof of Lemma 1

  • FedCor's optimization of expected global loss decrease is approximately reformulated as minimizing the weighted expected loss changes conditioned on selected clients' loss changes.The proof uses an assumption that other selections are unlikely to produce the same loss changes on the selected clients.Source: §A.2 · pp. 11–12

A.3. Proof of Lemma 2

  • For two-client selection, the first client maximizes a weighted correlation score, while the second uses a posterior-correlation criterion conditioned on the first.The score includes the Pearson correlation coefficient between clients.Source: §A.3 · p. 12

B.1. Definitions

  • The analysis defines FedCor's one-round advantage over uniform sampling and notes that iterative dependencies make quantifying it difficult.It therefore seeks a lower-bound-maximizing proxy with similar behavior and a convergence guarantee.Source: §B.1 · p. 13

B.2. Approximation of FedCor

  • FedCor's iterative selection favors clients with lower correlations to previously selected clients, motivating a proxy that maximizes summed individual gains.The proxy's selected clients are used to approximate FedCor's selection and share similar convergence characteristics.Source: §B.2 · p. 13
  • The proxy algorithm is stated to converge to the global-loss optimum without a gap, despite using biased selection.Source: §B.2 · p. 13

B.3. Convergence Analysis of the Proxy Algorithm

The analysis establishes an O(1/T) convergence rate for FedCor’s proxy algorithm under stated assumptions and a diminishing learning-rate schedule. It bounds the optimality gap and relates its vanishing to convergence of the iterates to the global optimum.

B.3. Convergence Analysis of the Proxy Algorithm

  • The proxy selection strategy maximizes the inner product of the projected global gradient and the sum of selected clients’ projected gradients.This property is established for each communication round under Assumptions 1 and 2.Source: §B.3 · p. 14
  • If Δ_t converges to zero, the iterates converge to the global optimum; under a nondegenerate Gaussian assumption, a vanishing full gradient implies this optimum.The consistency corollary states Δ_t→0 ⇒ w_t→w*, while the proof connects a vanishing projected gradient to a vanishing full gradient under the nondegeneracy condition.Source: §B.3 · p. 14
  • Under Assumptions 1, 3, and 6 and E||w_t−w_{t+1}||²≤q², the covariance change satisfies ||Σ_{t+1}−Σ_t||₁≤(bN²/C)[η_t²(G+Mq_t)²−η_{t+1}²G²].Here b is the largest eigenvalue of BBᵀ.Source: §B.3 · p. 15
  • Under Assumptions 1–7 and η_t=β/(t+γ) with β>1/m, Theorem 1 bounds Δ_t by ν/(γ+t), giving O(1/t) decay.The theorem also requires γ>0 and an initial learning-rate constraint; the supplied passage truncates the constraint’s full expression.Source: §B.3 · p. 15
  • With a diminishing learning rate, the proof uses induction to bound the loss gap Δt by ν/(γ+t), yielding convergence to zero.The induction follows from the recurrence for Δt and the stated bound on ν.Source: §B.3 · p. 17
  • The proxy algorithm converges to the global optimum at rate O(1/T).The analysis first establishes that the loss gap Δt converges to zero at rate O(1/T).Source: §B.3 · p. 17

C. Experiment Details

The experiments use FMNIST and CIFAR-10 with specified client partitions, model configurations, and FedCor settings. The Dirichlet partitioning procedure controls label proportions and client dataset sizes.

C. Experiment Details

  • Experiments ran on one NVIDIA 2080-Ti GPU and two Intel Xeon E5-2630 v4 CPUs, with reported per-seed runtimes of about 3 hours for FMNIST and 10 hours for CIFAR-10.Source: C. Experiment Details · p. 17

C.1. Model Parameters

  • FMNIST uses an MLP and CIFAR-10 a three-convolution-layer CNN; FedCor uses 15-dimensional client embeddings and dataset-specific discount factors.FMNIST uses 100 clients with participation fractions of 10 for 1SPC and 5 for 2SPC and Dir; CIFAR-10 uses the same client count and participation fractions.Source: §C.1 · pp. 17–18
  • The random-selection baseline samples uniformly without replacement, unlike Cho et al. [4], whose implementation samples with replacement.The paper notes that its implementation performs better than theirs.Source: §C.1 · p. 18

C.2. Dirichlet Distribution for Data Partition

  • For the Dir setting, each client's label proportions are sampled independently from a Dirichlet distribution, and client dataset sizes are chosen by quadratic programming to avoid over-concentration.The quadratic program constrains the aggregate label counts to match the specified counts and minimizes the squared dataset-size vector.Source: §C.2 · p. 18

D.1. Ablation Study: Annealing Coefficient

The ablation reports that convergence and final accuracy change only slightly across a broad range of annealing coefficients. It also distinguishes client selection frequencies from the combinations favored by sequential selection.

D.1. Ablation Study: Annealing Coefficient

  • Across tested FMNIST and CIFAR-10 settings, changing the annealing coefficient only slightly affects convergence rate and final accuracy.The paper concludes that FedCor is not sensitive to the tested annealing coefficients or GP training intervals.Source: §D.1 · p. 18
  • With smaller β, client selection frequencies become more uniform, but sequential dependencies still favor some client combinations over others.The reported advantage over uniform selection is attributed to choosing good combinations, not only good individual clients.Source: §D.1 · p. 18

D.2. Normality Verification

The appendix tests whether loss changes from uniformly sampled client selections are well modeled by Gaussian distributions. Across the experiments, the principal components fit Gaussian distributions well.

  • The verification samples 1,000 uniform client selections, applies PCA to their loss changes, and compares each principal component’s histogram with a Gaussian distribution.Source: §D.2 · p. 18
  • PCA is used instead of a multivariate normality test because the covariance matrix is nearly singular, making that test unstable.Source: §D.2 · p. 19
  • Gaussian distributions fit the principal-component distributions well across all experiments, supporting Lemma 1.The comparison uses each component’s histogram and a Gaussian density with that component’s mean and variance.Source: §D.2 · p. 19

D.3. Covariance Stationarity Verification

The appendix checks whether the client-loss covariance remains approximately stationary during training. In most cases, adjacent covariance matrices have similarity above 0.9.

  • The tested assumption is that the covariance matrix remains approximately unchanged between training rounds separated by Δt.Source: §D.3 · p. 19
  • Every 10 FMNIST rounds or 50 CIFAR-10 rounds, the authors sample 1,000 client selections, compute loss-change covariance, and compare adjacent matrices using cosine similarity.The similarity score ranges from 0 to 1, with larger values indicating greater similarity.Source: §D.3 · p. 19
  • Similarity between adjacent covariance matrices exceeds 0.9 in most cases, supporting the covariance-stationarity assumption.Source: §D.3 · p. 19
Loading 2103.13822v3…