FedBCD:Communication-Efficient Accelerated Block Coordinate Gradient Descent for Federated Learning

Junkang Liu; Fanhua Shang; Yuanyuan Liu; Hongying Liu; Yuangang Li; YunXiang Gong

cs.LGMar 5, 2026

FedBCD:Communication-Efficient Accelerated Block Coordinate Gradient Descent for Federated Learning

Authors: Junkang Liu, Fanhua Shang, Yuanyuan Liu, Hongying Liu, Yuangang Li, YunXiang Gong

Organizations: School of Artificial Intelligence, Xi’an, Xidian University, China · College of Intelligence and Computing, Tianjin, Tianjin University, China · Medical College, Tianjin University; Peng Cheng Laboratory, Tianjin, China · University of Southern California, Los Angeles, US

Abstract

Although Federated Learning has been widely studied in recent years, there are still high overhead expenses in each communication round for large-scale models such as Vision Transformer. To lower the communication complexity, we propose a novel Federated Block Coordinate Gradient Descent (FedBCGD) method for communication efficiency. The proposed method splits model parameters into several blocks, including a shared block and enables uploading a specific parameter block by each client, which can significantly reduce communication overhead. Moreover, we also develop an accelerated FedBCGD algorithm (called FedBCGD+) with client drift control and stochastic variance reduction. To the best of our knowledge, this paper is the first work on parameter block communication for training large-scale deep models. We also provide the convergence analysis for the proposed algorithms. Our theoretical results show that the communication complexities of our algorithms are a factor $1/N$ lower than those of existing methods, where $N$ is the number of parameter blocks, and they enjoy much faster convergence than their counterparts. Empirical results indicate the superiority of the proposed algorithms compared to state-of-the-art algorithms. The code is available at https://github.com/junkangLiu0/FedBCGD.

Figures & tables

Figure 1. The diagram of the proposed FedBCGD framework, where $S\geq N$ , $S$ and $N$ are the numbers of clients and parameter blocks, respectively.

Algorithm	Strongly convex Communication complexity	Non-convex Communication complexity	Client sample	Stochastic Gradient	Floats sent per round
FedAvg ( McMahan et al., 2017 )	$\mathcal{O}\Big(\frac{\sigma^{2}+G^{2}}{\mu ST\epsilon}+\frac{\sigma+G}{\mu\sqrt{\epsilon}}+\frac{\beta}{\mu}\log\frac{1}{\epsilon}\Big)$	$\mathcal{O}\Big(\frac{\beta\sigma^{2}}{TS\epsilon^{2}}+\frac{\sqrt{\beta}G+\sqrt{\frac{\beta}{T}}\sigma}{\epsilon^{\frac{3}{2}}}+\frac{F\beta}{\epsilon}\Big)$	Yes	Yes	$d$
FedBCGD (ours)	$\mathcal{O}\Big(\frac{\sigma^{2}+G^{2}}{\mu ST\epsilon}+\frac{\sigma+G}{\alpha\mu N\sqrt{\epsilon}}+\frac{\beta}{\mu N}\log\frac{1}{\epsilon}\Big)$	$\mathcal{O}\Big(\frac{\beta\sigma^{2}}{TS\epsilon^{2}}+\frac{\sqrt{\beta}G+\sqrt{\frac{\beta}{T}}\sigma}{N\epsilon^{\frac{3}{2}}}+\frac{F\beta}{N\epsilon}\Big)$	Yes	Yes	$d/N$
SCAFFOLD ( Karimireddy et al., 2020b )	$\mathcal{O}\Big(\frac{\sigma^{2}}{\mu ST\epsilon}\!+\!\frac{\sigma}{\mu\sqrt{\epsilon}}\!+\!\Big(\frac{M}{S}\!+\!\frac{\beta}{\mu}\Big)\log\frac{1}{\epsilon}\Big)$	$\mathcal{O}\Big(\frac{\beta\sigma^{2}}{TS\epsilon^{2}}+\frac{\sqrt{\frac{\beta}{T}}\sigma}{\epsilon^{\frac{3}{2}}}+\frac{\beta F}{\epsilon}\Big(\frac{M}{S}\Big)^{\frac{2}{3}}\Big)$	Yes	Yes	$2d$
FedLin ( Mitra et al., 2021 )	$\mathcal{O}\Big({\frac{\beta}{\mu}}\log\frac{1}{\epsilon}\Big)$	——	No	No	$2d$
S-Local-GD ( Gorbunov et al., 2021 )	$\mathcal{O}\Big({\frac{\beta}{\mu}}\log\frac{1}{\epsilon}\Big)$	——	No	No	$2d$
CE-LSGD ( Patel et al., 2022 )	——	$\mathcal{O}\Big(\frac{GF\tau}{M\epsilon^{\frac{3}{2}}}\Big)$	Yes	Yes	$3d$

Table 1. Comparison of the communication complexities and communication overheads of different algorithms in the

\mu

-strongly convex setting, where

\sigma

is the variance of stochastic gradients,

G

is heterogeneity due to client data distribution,

S

is the number of participating clients,

K\!=\!S/N

K

is the number of clients involved in each parameter block,

N

is the number of parameter blocks, and

T

is the number of local training iterations. The number of floats sent per round by FedAvg is

d

, and

\mathcal{O}

describes the worst-case complexity of different algorithms, where

\alpha=\frac{1}{1-\lambda}

. In non-convex settings,

\tau

is the second-order heterogeneity (see ( Karimireddy et al., 2020a ) ),

G

is the first-order heterogeneity,

F:=f\left(\boldsymbol{x}^{0}\right)-f^{\star}

, and

f^{\star}

is a minimum value of Problem (1) below.

Figure 2. The client parameter block allocation in FedBCGD. For the sake of convenience, we suppose $S=N\cdot K$ clients are sampled and divided into $N$ client blocks, i.e., $K$ clients for each client block. The clients in the $i$ -th client block are responsible for optimizing the upload parameter block $i$ .

CIFAR100	LeNet-5 (40%)	VGG-11 (48%)	ResNet-18 (54%)	VGG-19 (45%)
Centralised SGD	$53.7\pm 0.2$	$56.3\pm 0.3$	$62.2\pm 0.1$	$58.9\pm 0.1$
FedAvg ( McMahan et al., 2017 )	$41.2\pm 0.2\;(558d)$	$48.7\pm 0.4\;(720d)$	$54.2\pm 0.2\;(927d)$	$47.6\pm 0.1\;(735d)$
FedAvgM ( Hsu et al., 2019 )	$48.2\pm 0.5\;(277d)$	$51.7\pm 0.6\;(299d)$	$61.8\pm 0.8\;(398d)$	$56.0\pm 0.3\;(403d)$
FedAdam ( Reddi et al., 2020 )	$46.2\pm 0.8\;(391d)$	$50.9\pm 0.5\;(597d)$	$53.9\pm 0.4\;(\infty)$	$58.7\pm 0.2\;(367d)$
SCAFFOLD ( Karimireddy et al., 2020b )	$50.3\pm 0.2\;(214d)$	$47.9\pm 0.2\;(\infty)$	$52.3\pm 0.2\;(\infty)$	$58.3\pm 0.5\;(556d)$
FedDC ( Gao et al., 2022 )	$53.2\pm 0.3\;(302d)$	$48.2\pm 0.2\;(956d)$	$46.6\pm 0.1\;(\infty)$	$56.8\pm 0.4\;(321d)$

Table 2. Comparison of the average testing accuracy (%) on CIFAR100, where the heterogeneity parameter is

\rho=0.6

, total communication floats are

1000d

, and the number of blacks is

N=5

. The number in brackets indicates the number of communication floats to reach the target accuracy. Note that centralised SGD refers to using SGD to train models on a single machine.

CIFAR10	LeNet-5 (78%)	VGG-11 (83%)	ResNet-18 (88%)	VGG-19 (84%)
Centralised SGD	$83.1\pm 0.2$	$87.4\pm 0.3$	$90.1\pm 0.1$	$88.6\pm 0.1$
FedAvg ( McMahan et al., 2017 )	$79.6\pm 0.3\;(498d)$	$83.3\pm 0.7\;(630d)$	$89.0\pm 0.5\;(698d)$	$84.9\pm 0.7\;(499d)$
FedAvgM ( Hsu et al., 2019 )	$81.1\pm 0.6\;(360d)$	$83.7\pm 0.4\;(830d)$	$89.1\pm 0.7\;(882d)$	$87.4\pm 0.5\;(252d)$
FedAdam ( Reddi et al., 2020 )	$78.3\pm 1.2\;(860d)$	$85.4\pm 1.1\;(478d)$	$81.1\pm 1.3\;(\infty)$	$87.5\pm 0.9\;(298d)$
SCAFFOLD ( Karimireddy et al., 2020b )	$82.8\pm 0.7\;(540d)$	$86.9\pm 0.6\;(278)$	$89.0\pm 0.4\;(747d)$	$85.5\pm 0.5\;(358d)$
FedDC ( Gao et al., 2022 )	$83.0\pm 0.2\;(280d)$	$83.1\pm 0.6\;(866)$	$88.0\pm 0.6\;(1985d)$	$78.0\pm 0.9\;(\infty)$

Table 3. Comparison of the average testing accuracy (%) over the last 10% rounds of each algorithm on CIFAR10, where the heterogeneity parameter is

\rho=0.6

, total communication floats are

1000d

, the number of blacks is set to

N=5

Panel of Figure 3 — Figure 3. The convergence comparison of our FedBCGD and FedBCGD+, and other baselines on the CIFAR10 and CIFAR100 datasets with different neural network architectures, where, in 100 clients, partial (10%) clients are used, $\rho\!=\!0.6$ .

Figure 4. The acceleration comparison of FedBCGD with different numbers of blocks.

Panel of Figure 5 — Figure 5. Accuracy comparison of FedBCGD with LeNet-5 on CIFAR10 (a) and CIFAR100 (b), where heterogeneity is $\rho\!=\!0.6$ . FedBCGD_freezing_nonshare is updated by using the local freezing parameter algorithm without the shared block. FedBCGD_freezing_share is FedBCGD_freezing algorithm with shared parameters. FedBCGD_nonshare trains all parameters locally and only transmits parameter blocks without shared parameters. FedBCGD_share has shared parameters. FedBCGD_share_momentum (i.e., FedBCGD) has momentum acceleration.

$\rho=0.1$	CIFAR100 (45%)	CIFAR10 (78%)
FedAvg ( McMahan et al., 2017 )	$45.8\pm 0.3\;(741d)$	$78.1\pm 0.4\;(952d)$
FedAvgM ( Hsu et al., 2019 )	$48.3\pm 0.6\;(769d)$	$78.6\pm 0.8\;(997d)$
FedAdam ( Reddi et al., 2020 )	$49.9\pm 0.5\;(610d)$	$71.4\pm 1.1\;(\infty)$
SCAFFOLD ( Karimireddy et al., 2020b )	$44.3\pm 0.3\;(\infty)$	$76.3\pm 1.4\;(\infty)$
FedDC ( Gao et al., 2022 )	$46.6\pm 0.8\;(278d)$	$79.1\pm 0.8\;(948d)$
FedBCGD (ours)	$59.5\pm 0.3\;(\mathbf{147d})$	$\mathbf{86.2\pm 0.9}\;(\mathbf{212d})$

Table 4. Comparison of each algorithm on CIFAR100 and CIFAR10. Heterogeneity is

\rho\!=\!0.1

, total communication floats are

1000d

, and the number of blocks in ResNet-18 is

N=5

$\rho=0.6$	CIFAR100 (88%)	Tiny Imagenet (70%)
Centralised SGD	$81.5\pm 0.3$	$76.7\pm 0.2$
FedAvg ( McMahan et al., 2017 )	$90.4\pm 0.1\;(24d)$	$71.2\pm 0.1\;(67d)$
FedAvgM ( McMahan et al., 2017 )	$88.7\pm 0.3\;(32d)$	$76.7\pm 0.4\;(10d)$
FedAdam ( Reddi et al., 2020 )	$87.6\pm 0.2\;(\infty)$	$65.5\pm 0.6\;(\infty)$
SCAFFOLD ( Karimireddy et al., 2020b )	$88.2\pm 0.3\;(88d)$	$56.8\pm 1.1\;(\infty)$
FedDC ( Gao et al., 2022 )	$85.8\pm 0.4\;(25d)$	$55.0\pm 1.2\;(\infty)$

Table 5. The test accuracy comparison of each algorithm with ViT-Base on CIFAR100 and Tiny ImageNet. Heterogeneity is

\rho\!=\!0.6

, total communication floats are

100d

N=6

$\rho=0.6$	CIFAR100 (40%)	CIFAR10 (70%)
FedAvg ( McMahan et al., 2017 )	$35.4\pm 0.1\;(\infty)$	$73.2\pm 0.1\;(133d)$
TOP-k ( Aji and Heafield, 2017 )	$42.2\pm 0.5\;(112d)$	$74.5\pm 0.4\;(92d)$
FedPAQ ( Reisizadeh et al., 2020 )	$43.3\pm 0.2\;(110d)$	$75.2\pm 0.4\;(121d)$
FedBCGD (ours)	$48.7\pm 0.2\;(91d)$	$\mathbf{77.2\pm 0.2}\;(65d)$
FedBCGD+ (ours)	$49.6\pm 0.3\;(89d)$	$80.6\pm 0.2\;(57d)$
QSGD ( Alistarh et al., 2017 ) +FedBCGD (ours)	$52.2\pm 0.4\;(61d)$	$82.6\pm 0.1\;(32d)$

Table 6. The test accuracy comparison of each algorithm with LeNet-5 on CIFAR100 and CIFAR10. Here, the heterogeneity is

\rho\!=\!0.6

, total communication floats are

200d

N=5

Panel of Figure 6 — Figure 6. The test accuracy varies with the communication floats with ViT-Base on the CIFAR100 and Tiny ImageNet datasets, where $E\!=\!1$ and $\rho\!=\!0.6$ , $N=6$ .

Panel of Figure 7 — Figure 7. Test accuracy (a) and training loss (b) with ResNet-18 on CIFAR100, where $E\!=\!5$ and $\rho\!=\!0.6$ , $N=5$ .

Panel of Figure 8 — Figure 8. Logistic regression with $E\!=\!1$ and $\rho\!=\!0.1$ , $N=5$ .

Panel of Figure 9 — Figure 9. (a) Logistic regression with $E\!=\!1$ and $\rho\!=\!0.1$ . (b) The problem with non-convex loss, where $E\!=\!1$ and $\rho\!=\!0.1$ . The number of blocks is set to $N=5$ .

Parameter Block	Network Layers	Number of parameters
Block 1	conv3-64	4800
Block 2	conv3-64	102400
Block 3	FC-1600	614400
Block 4	FC-384	73728
Block 5	FC-192 (share)	1920

Table 7. The parameters block division of the LeNet-5 network.

Parameter Block	Network Layers	Number of parameters
Block 1	conv3-64	1728
Block 1	conv3-128	73728
Block 2	conv3-256	294912
Block 2	conv3-256	589824
Block 3	conv3-512	1179648
Block 3	conv3-512	2359296

Table 8. The parameter block division of the VGG-11 network.

Parameter Block	Network Layers	Number of parameters
Block 1	conv3-64	1728
Block 1	conv3-64	36864
Block 1	conv3-64	36864
Block 1	conv3-64	36864
Block 1	conv3-64	36864
Block 2	conv3-128	73728

Table 9. The parameters block division of the ResNet-18 network.

Parameter Block	Network Layers	Number of parameters
Block 1	conv3-64	1728
Block 1	conv3-64	36864
Block 1	conv3-128	73728
Block 1	conv3-128	147456
Block 1	conv3-256	294912
Block 1	conv3-256	589824

Table 10. The parameters block division of the VGG-19 network.

Parameter Block	Network Layers	Number of parameters
Block 1	ViT-Block 1	14299520
Block 2	ViT-Block 2	14299520
Block 3	ViT-Block 3	14299520
Block 4	ViT-Block 4	14299520
Block 5	ViT-Block 5	14299520
Block share	FC-100	153600

Table 11. The parameters block division of the VGG-19 network.

Federated Learning

Federated learning trains shared models across data holders without requiring them to pool their raw data.

See all 943 papers

Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm
Jun 21, 2026Shengchao Zhao, Yongchao LiuStochastic Optimization Nonconvex Stochastic Optimization
School of Mathematics, China University of Mining and Technology, Xuzhou, China · School of Mathematical Sciences, Dalian University of Technology, Dalian, China
Fed-FBD: Federated Functional Block Diversification for Isolation, Privacy, and Surgical Unlearning
Jun 10, 2026Weijie Chen, Alan B. McMillanFederated Unlearning Byzantine-Robust Federated Learning
Department of Radiology, University of Wisconsin–Madison
FedLore: Communication and Memory Efficient Federated Learning via Shared Gradient Low-Rank Projection
Oct 1, 2026Junkang LiuFederated Learning Aggregation Memory-Efficient Fine-Tuning
Tianjin University

Jun 21, 2026J/K move · Enter open · S save

Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm

Shengchao Zhao, Yongchao Liu

School of Mathematics, China University of Mining and Technology, Xuzhou, China · School of Mathematical Sciences, Dalian University of Technology, Dalian, China

Stochastic Optimization Nonconvex Stochastic Optimization Heavy-Tailed Noise Variance Reduction Heavy-Tailed Stochastic Optimization Federated Learning

Open paper AskPDF arXiv

Federated learning (FL) is an emerging distributed machine learning paradigm that enables local devices to jointly train a global model while keeping data decentralized and private. We propose a variance-reduction based algorithm, VRA-FedSGD, for FL in the presence of heavy-tailed gradient noise and communication noise, where these noises are prevalent in large-scale machine learning over wireless networks and Internet of Things deployments. VRA-FedSGD employs a momentum variance reduction technique together with a nonlinear mapping to mitigate heavy-tailed gradient noise, and uses a variance-reduced aggregation mechanism to suppress heavy-tailed communication noise. In the mean sense, VRA-FedSGD achieves a convergence rate of {\small

\mathcal{O}\left(K^{-(p-1)/(2p-1)}\right)

} for nonconvex objective functions, where

p

is the tail index of heavy-tailed noise. In the almost sure sense, VRA-FedSGD achieves a convergence rate of

\tilde{\mathcal{O}}\left(K^{-(1-1/(p-ε))}\right)

for strongly convex objective functions, where

ε

is an arbitrarily small constant. Simulated experiments on a logistic regression problem with real-world data verify the effectiveness of VRA-FedSGD.

Abstract

Federated Learning

Explore similar work

Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm

Fed-FBD: Federated Functional Block Diversification for Isolation, Privacy, and Surgical Unlearning

FedLore: Communication and Memory Efficient Federated Learning via Shared Gradient Low-Rank Projection