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

Venue: acmmm_org_ACMMM_2024_Conference
Published: 2024-04-06 08:36:03

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 communication efficient block coordinate gradient descent (FedBCGD) method. The proposed method splits model parameters into several blocks and enables upload a specific parameter block by each client during training, which can significantly reduce communication overhead. Moreover, we also develop an accelerated FedBCGD algorithm (called FedBCGD+) with client drift control and stochastic variance reduction techniques. To the best of our knowledge, this paper is the first parameter block communication work 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 results than their counterparts. Empirical results indicate the superiority of the proposed algorithms compared to state-of-the-art algorithms.

Main paper: 
 introduction: 
 Federated Learning (FL) is an emerging machine learning paradigm, which aims at achieving collaborative model training among multiple parties to preserve data privacy. Federated learning achieves model training by training models locally on client devices and then uploading them to a central server for model aggregation [28] . Compared to centralized learning in a data center [11] , the parallel computing clients of federated learning have private data stored in them and communicate remotely with a central server. The clients are responsible for local training, while the central server in charge of aggregating the models uploaded by each client. Currently, federated learning has been widely applied in different fields such as mobile intelligence devices, medical health, and financial risk control [3, 5, 35] .In mainstream federated learning frameworks, the communication between clients and their server is slow, costly, and unreliable [19] . In recent years, large models such as BERT and ChatGPT [4, 7] have emerged, leading to an exponential increase in the model size and data volume on FL clients. The upload of these large models further escalates the cost of communication in FL. To significantly lower the communication complexity, this paper proposes a novel method for federated learning, called Federated Block Coordinate Gradient Descent (FedBCGD), which is based on block coordinate descent (BCD) methods [38] .In FL, the upload speed of the client model is more than a hundred times slower than the download speed, so this paper mainly resolves the issue of upload communication cost. As shown in Figure 1 , we divide the model parameter 𝒙 into 𝑁 blocks and 𝒙 𝑠 , i.e., 𝒙 = 𝒙 ⊤ (1) , . . . , 𝒙 ⊤ (𝑁 ) , 𝒙 ⊤ 𝑠 ⊤, where 𝒙 𝑠 denotes the shared parameters in each client (usually the parameters of the last layer classifier, and their number is small but important, [26] suggests that the deeper the model, the greater the variance of the parameters. In federated learning, it is often the parameters in the last layer of the classifier that are most important and have a very small number of covariates (0.01% of the overall number in ResNet-18)). Each client is responsible for optimizing one selected block 𝒙 ( 𝑗 ) and 𝒙 𝑠 . After local training for all model parameters, the updated parameter block 𝒙 ( 𝑗 ) and 𝒙 𝑠 are sent to the central server, which takes the average aggregation of parameters for different parameter blocks to get the complete model.The initial idea is to require each client to perform local updates only on the specified parameter block 𝒙 ( 𝑗 ) and 𝒙 𝑠 while freezing Table 1 : Comparison of the communication complexities and communication overheads of different algorithms in the 𝜇-strongly convex setting, where 𝜎 is the variance of stochastic gradients, 𝐺 is heterogeneity due to client data distribution, 𝑆 is the number of participating clients, 𝐾 =𝑆/𝑁 , 𝐾 is the number of clients involved in each parameter block, 𝑁 is the number of parameter blocks, and 𝑇 is the number of local training iterations. The number of floats sent per round by FedAvg is 𝑑, and O describes the worst-case complexity of different algorithms, where 𝛼 = 1 1-𝜆 . In non-convex settings, 𝜏 is the second-order heterogeneity (see [16] ), 𝐺 is the first-order heterogeneity, 𝐹 := 𝑓 𝒙 0 -𝑓 ★ , and 𝑓 ★ is a minimum value of Problem (1) below. + 𝑀 𝑆 + 𝛽 𝜇 log 1 𝜖 O 𝛽𝜎 2 𝑇 𝑆𝜖 2 + √︃ 𝛽 𝑇 𝜎 𝜖 3 2 + 𝛽𝐹 𝜖 𝑀 𝑆 2 3Yes Yes 2𝑑FedLin [29] O𝛽 𝜇 log 1 𝜖 -- No No 2𝑑 S-Local-GD [10] O 𝛽 𝜇 log 1 𝜖 -- No No 2𝑑 CE-LSGD [31] -- O 𝐺𝐹𝜏 𝑀𝜖 3 2 Yes Yes 3𝑑 BVR-L-SGD [30] -- O 𝐹𝜏 𝜖 + 𝐹 𝛽 √ 𝑇 𝜖 + 𝜎 2 𝑀𝑇 𝜖 + 𝜎𝐹 𝛽 𝑀𝑇 𝜖 3 2Yes 3𝑑FedBCGD+ (ours) O 𝑀 𝑆 + √︃ 𝛽 𝜇 log 1 𝜖 O 𝛽𝐹 𝜖 𝑀 𝑆 2 3 1 𝑁 1 3Yes Yes 2𝑑/𝑁 the remaining parameter blocks (called FedBCGD_freezing). After local training, the specified parameter blocks would be uploaded for model aggregation. However, due to a large drift between parameter blocks, such scheme often results in bad convergence in our experiments (see Figure 5 for details). More specifically, only updating certain parameter blocks locally results in a large gap between the updated parameter blocks and other freezing parameter blocks, and it is not possible to establish good connections between parameter blocks during the server-side aggregation process. Therefore, we propose a novel FedBCGD method to address these issues. In the proposed algorithm, we employ stochastic gradient descent to update all parameters instead of parameter freezing during local training, but only transmit two specified parameter blocks (𝒙 ( 𝑗 ) and 𝒙 𝑠 ) during the upload process. In addition, to compensate for some missing parameters in block parameter transmission, we add parameter block momentum on the server side. This algorithm design maintains the advantages of low communication costs and has demonstrated a significantly improved convergence speed in our experiments (see Figure 5 for details). Moreover, adding one shared parameter block in each client can significantly improve accuracy performance. However, due to the impact of data heterogeneity, it still leads to inconsistent update directions between parameter blocks, called parameter block drift, resulting in poor performance of the aggregated model. Thus, we also propose an accelerated version (called FedBCGD+) to address data heterogeneity. The main difference between FedBCGD and BCD is that FedBCGD incorporates shared one small parameter block and updates all model parameters in each client (i.e., no parameter freezing), while BCD only updates one parameter block in each iteration.To address these issues such as communication effectiveness, acceleration, theoretical guarantees and parameter block drift, we design a novel federated block coordinate descent framework FedBCGD and its acceleration variant FedBCGD+ for training large-scale deep models such as Vision Transformer. The main contributions of this work are listed as follows:• Novel Federated Learning Paradigm: We propose the first block coordinate descent algorithm FedBCGD for horizontal FL. FedBCGD demonstrates remarkable communication efficiency in distributed learning scenarios. That is, this paper presents the first block coordinate descent algorithm for horizontal federated learning. Moreover, we also introduce an accelerated version, FedBCGD+, which exhibits an even faster convergence rate while maintaining high communication efficiency.• Convergence Analysis: We provide a thorough analysis of the convergence properties of the proposed FedBCGD algorithm and its accelerated version, FedBCGD+. By investigating the impact of partitioned parameter blocks, the number of clients, and the local training rounds, we provide valuable insights into their convergence behavior. From a practical perspective, FedBCGD+ achieves faster convergence than FedBCGD, and it is proved faster from a theoretical perspective. Moreover, FedBCGD+ has a much lower communication complexity than existing algorithms in strong convexity settings (e.g . In other words, the communication complexities of our algorithms are a factor 1/𝑁 lower than those of existing methods, where 𝑁 is the number of parameter blocks.• Overcoming Data Heterogeneity : The convergence of federated learning algorithms is hindered by two sources of high variance: (i) heterogeneous clients, and (ii) the noise from local stochastic gradients. We propose two sets of control variance variables to reduce client heterogeneity and the noise variance of the local gradients in FedBCGD+. And we demonstrate the validity of the two sets of control variables through theory and experiment. 
related work: 
 In this section, we mainly review existing federated learning and block coordinate descent methods.• Local Training: Local Training (LT) is a communicationacceleration technique for FL [28] . One key challenge in LT is client drift, where the local model of each client gradually approaches the minimum of its own local cost function 𝑓 𝑖 after multiple local GD steps. To address this issue, SCAFFOLD [17] is proposed, which was to incorporate control variates to correct for client drift and ensure linear convergence to the exact solution. Subsequent algorithms such as S-Local-GD [10] and FedLin [29] also aimed to provide similar convergence properties.The analysis of algorithms for non-convex federated learning can be classified into several approaches. SCAFFOLD [17] is the first federated algorithm capable of eliminating client data heterogeneity. However, its convergence speed is still affected by stochastic gradients, achieving only a convergence rate of O (1/𝜖 2 ). MIME [16] is essentially a combination of local SGD and variance reduction techniques as in SVRG [15] , with a derived communication complexity of O (1/𝜖 3/2 ). BVR-L-SGD [30] assumed second-order data heterogeneity and achieved a communication complexity of O (1/𝜖) with full client participation. The two-sided momentum (STEM) algorithm [18] can also attain a communication complexity of O (1/𝜖) with full client participation. Inspired by the Storm algorithm [6] , CE-LSGD [31] can achieve a communication complexity of O (1/𝜖 3/2 ) with partial client participation and O (1/𝜖) when all clients participate.• Block Coordinate Descent Methods: The block coordinate descent method is one of the most successful algorithms in the field of big data optimization. BCD is based on the strategy of updating a single coordinate or a single block of coordinate of a vector of variables at each iteration, which usually significantly reduces the memory requirements as well as the arithmetic complexity of a single iteration. The effectiveness of the BCD method for training deep neural networks (DNNs) has been demonstrated in recent years [40] . However, due to the highly non-convex nature of deep neural networks, its convergence is difficult to maintain. In addition, BCD can be easily implemented in a distributed and parallel manner [27, 34] . Liu et al. [25] proposed a vertical federated learning [24] framework (FedBCD) for distributed features, in which parties share only the internal product of model parameters and raw data for each sample during each communication. Unlike the above works, this paper proposes the first block coordinate descent algorithm for horizontal federated learning. Horizontal federated learning is applied to scenarios where the client's datasets have the same feature space and different sample spaces [39] .• Communication-efficient Federated Learning: Communication efficient Federated Learning algorithms can be divided into two categories, quantization and sparsification compression methods. The classical Federated Learning quantization method is proposed by Reisizadeh [33] , which is a cycle averaging and quantization processing method named FedPAQ, and the quantization compression generally belongs to the unbiased compressions. While sparsification methods include 𝑡𝑜𝑝-𝑘 and 𝑟𝑎𝑛𝑑-𝑘 methods [36] , 𝑡𝑜𝑝-𝑘 method is a biased compression method that uploads the gradient at the first 𝑘 large positions in the gradient to the server, while 𝑟𝑎𝑛𝑑-𝑘 method is an unbiased compression method that uploads the gradient at random 𝑘 positions to the server. FedBCGD is different from all of the above methods and utilizes the idea of block gradient descent to address federated efficient communication, in addition to the above mentioned compression method that allows for secondary compression of our transferred block gradient to achieve more efficient communication, which is demonstrated in the following experiment. 
communication-efficient block coordinate gradient descent federated learning: 
 In this section, we propose a new communication-efficient block coordinate gradient descent federated learning algorithm FedBCGD, and its pseudocode is given in Algorithm 1. We formalize the federated learning problem as the minimization of a sum of stochastic functions:minEQUATIONwhere the function 𝑓 𝑖 denotes the loss function on client 𝑖, 𝑀 is the number of clients, 𝑛 𝑖 is the number of data points in client 𝑖, and 𝜁 𝑖,1 , . . . , 𝜁 𝑖,𝑛 𝑖 denote the local data of the 𝑖-th client. In this paper, we assume that 𝑓 𝑖 is a 𝛽-smooth function.We firstly divide the global model 𝒙 into 𝑁 blocks of parameters and one shared block, each of which can have a different number of parameters,EQUATIONWe divide the sampled 𝑆 = 𝑁 • 𝐾 clients into 𝑁 client blocks with 𝐾 clients in each client block (see Figure 2 ). These 𝑁 parameter blocks are distributed to the selected 𝑁 client blocks, where each parameter block will be optimized by 𝐾 clients. Server:18:for 𝑗 = 1, . . . , 𝑁 Blocks in parallel doBlock 𝑗 computes, 20:𝒙 𝑟 ( 𝑗 ) = 1 𝐾 𝐾 𝑘=1 𝒙 𝑟,𝑇 𝑘,𝑗,( 𝑗 ) ; 𝑣 𝑟 ( 𝑗 ) = 𝜆𝑣 𝑟 -1 ( 𝑗 ) + 𝒙 𝑟 ( 𝑗 ) -𝒙 𝑟 -1 ( 𝑗 ) ; 21: 𝒙 𝑟 ( 𝑗 ) = 𝒙 𝑟 ( 𝑗 ) + 𝑣 𝑟 ( 𝑗 ) , 22:end for where 𝒙 𝑡 +1 𝑘,𝑗 is the 𝑡 +1-th local update whole parameter of client 𝑘,𝑗 , and 𝒙 𝑡 +1 𝑘,𝑗,( 𝑗 ) is the 𝑗-th parameter block of client 𝑘,𝑗 . ∇𝑓 𝑘,𝑗,( 𝑗 ) is the 𝑗-th gradient block in client 𝑘,𝑗 (see Figure 2 ). The local client of FedBCGD is used to update all model parameters 𝒙 and send the selected parameter block 𝒙 ( 𝑗 ) and 𝒙 𝑠 to the server.Below, we will describe the proposed server-side aggregation operation. For the 𝑘-th client of the 𝑗-th parameter block, it sends the parameter block 𝒙 . Before the next iteration starts, the client transfers all model parameters 𝒙 𝑟 to the selected client and tells the client which model parameter block needs to be uploaded.𝑣 𝑟 ( 𝑗 ) is the 𝑗-th block of the momentum term 𝑣 𝑟 , and 𝜆 is the momentum parameter. The momentum term 𝑣 𝑟 ( 𝑗 ) considers the model's continuous updates over time, making the updating process smoother. More specifically, it remembers and utilizes the direction and speed of previous model parameter updates, thereby accelerating the convergence speed of the model.The FedBCGD+ algorithm is an extension of our FedBCGD algorithm based on the principles of variance reduction in SVRG [15] . And its details are presented in the Appendix. Note that the serverside updates in FedBCGD+ are consistent with FedBCGD, while the new proposed client-side update of our FedBCGD+ algorithm is formulated as follows:𝒙 𝑟,𝑡 +1 𝑘,𝑗 = 𝒙 𝑟,𝑡 𝑘,𝑗 -𝜂∇𝑓 𝑘,𝑗 𝒙 That is, each client-side update consists of a stochastic gradient descent (SGD) term, one client drift control variate term and a variance reduction term, which is different from all existing works such as [17] . FedBCGD+ maintains a state for each client (the client control variate 𝒄 𝑖 ) and the server (the server control variate 𝑐). Here, 𝒄 + 𝑘,𝑗 = ∇𝑓 𝑘,𝑗 (𝒙 𝑟 ), and we need to send 𝒙 𝑟,𝑇 𝑘,𝑗,( 𝑗 ) , Δ𝒄 𝑘,𝑗,( 𝑗 ) = 𝒄 + 𝑘,𝑗,( 𝑗 ) -𝒄 𝑘,𝑗,( 𝑗 ) , Δ𝒄 𝑘,𝑗,𝑠 = 𝒄 + 𝑘,𝑗,𝑠 -𝒄 𝑘,𝑗,𝑠 to the server, 𝒄 𝑖 = 𝒄 + 𝑖 . We update 𝒄 on the server-side as follows:EQUATIONEQUATIONEQUATION)The key of our FedBCGD+ algorithm for improving the convergence speed is based on the following observation. The convergence of federated learning algorithms is hindered by two sources of high variance: (i) the global server aggregation step and multiple local In the local update in Eq. ( 4), the first term involves stochastic gradient descent, the second term incorporates client heterogeneity control inspired by SCAFFOLD [17] , and the third term adopts one stochastic variance reduction technique as in SVRG [15] to reduce the variance of stochastic gradients. By integrating these three components, our algorithm effectively addresses the challenges posed by heterogeneous clients and noisy local gradients, leading to a significant improvement in the convergence speed during the federated learning process. Compared with existing algorithms such as SCAFFOLD, and our FedBCGD, FedBCGD+ has a faster convergence rate, as shown in the following theoretical results. 
theoretical guarantees: 
 In this section, we provide rigorous theoretical analysis for all the proposed algorithms, and the detailed proofs are included in the Appendix. The theoretical analysis of our FedBCGD algorithm is not a simple parallelization extension of the traditional BCD algorithm but an innovative theoretical analysis framework. Compared with related work, the two proposed algorithms have some theoretical advantages, including faster convergence rates and lower communication complexities. For the convenience of theoretical analysis, we ignore the shared block in the algorithms.Theorem 1 (FedBCGD). For 𝛽-smooth functions {𝑓 𝑖 }, which satisfy Assumptions 1-5 (see the Appendix for details), the output of FedBCGD has expected error smaller than 𝜖 for some values of 𝜂, 𝑅, where 𝑅 denotes the number of communication rounds, 𝐶𝑜𝑚 is the communication complexity (i.e., the product of the number of communication rounds and the floats sent per round) satisfying:Strongly convex: η = 𝛼𝜂𝑇 4 , η ≤ 18𝛽 , and𝑅 = O 𝜎 2 + 𝐺 2 𝜇𝐾𝑇 𝜖 + 𝜎 + 𝐺 𝛼 𝜇 √ 𝜖 + 𝛽 𝜇 log 1 𝜖 , 𝐶𝑜𝑚 = O 𝜎 2 + 𝐺 2 𝜇𝑆𝑇 𝜖 𝑑 + 𝜎 + 𝐺 𝛼 𝜇𝑁 √ 𝜖 𝑑 + 𝛽 𝜇𝑁 log 1 𝜖 𝑑 , Non-convex: η = 1 4 𝛼𝜂𝑇 , η ≤ 1 16𝛽 , 𝐹 := 𝑓 𝒙 0 -𝑓 ★ , 𝑅 = O 𝛽𝜎 2 𝑇 𝐾𝜖 2 + √︁ 𝛽𝐺 + √︃ 𝛽 𝑇 𝜎 𝜖 3 2 + 𝐹 𝛽 𝜖 , 𝐶𝑜𝑚 = O 𝛽𝜎 2 𝑇 𝑆𝜖 2 𝑑 + √︁ 𝛽𝐺 + √︃ 𝛽 𝑇 𝜎 𝑁 𝜖 3 2 𝑑 + 𝐹 𝛽 𝑁 𝜖 𝑑 .From 𝑑 , which is 𝑁 times significantly lower. As the number of blocks 𝑁 increases, FedBCGD can achieve a significantly lower communication complexity, and we will verify this in the experimental section (see Figure 4 ). The momentum parameter 𝛼 here is equivalent to the server step size, and a larger server step size can accelerate convergence, as pointed out in [17] .Theorem 2 (FedBCGD+). For 𝛽-smooth functions {𝑓 𝑖 }, which satisfy Assumptions 1-5, the output of FedBCGD+ has expected error smaller than 𝜖 for some values of 𝜂, 𝑅, where 𝑅 and 𝐶𝑜𝑚 satisfy:Strongly convex: η = 𝛼𝜂𝑇 4 , η ≤ 1 8𝛽 , and 𝑅 = O 𝑀 𝐾 + 𝛽 𝜇 log 1 𝜖 , 𝐶𝑜𝑚 = O 𝑀 𝑆 + 𝛽 𝜇𝑁 𝑑 log 1 𝜖 , Non-convex: η = 1 4 𝛼𝜂𝑇 , η ≤ 1 16𝛽 , 𝐹 := 𝑓 𝒙 0 -𝑓 ★ , 𝑅 = O 𝛽𝐹 𝜖 𝑀 𝐾 2 3 , 𝐶𝑜𝑚 = O 𝛽𝐹 𝜖 𝑀 𝑆 2 3 1 𝑁 1 3𝑑 . 𝑁 -1/3 𝑑 , which also is the best-known result (see Table 1 ). Without client sampling, the communication complexity of FedBCGD+ is O 𝛽𝐹 𝜖 𝑁 -1/3 𝑑 , which is much better than that of CE-LSGD [31] , O 𝛽𝐹 𝜖 𝑑 . As the number of blocks 𝑁 increases, FedBCGD+ can also achieve a significantly lower communication complexity. 
experiments: 
 In this section, we conduct various experiments for convex and nonconvex problems, and more results are reported in the Appendix.Datasets: We evaluate our algorithms on the CIFAR10 [20] , CI-FAR100 [20] , Tiny ImageNet [21] and EMNIST datasets. We set up a total of 100 clients in the FL experiment with a participation rate of 10%. For the non-IID data setup, we model data heterogeneity by sampling label ratios 𝜌 from a Dirichlet distribution. Models: To test the robustness of our algorithms, we use standard classifiers (including LeNet-5 [22] , VGG-11, VGG-19 [37] , and ResNet-18 [13] ), Vision Transformer (ViT-Base) [8] . We divided the parameters of the model into 5 blocks or more blocks and provide the detailed parameter block division of the model in the Appendix. Methods: We compare FedBCGD and FedBCGD+ with many SOTA FL baselines, including FedAvg [28] , SCAFFOLD [17] , FedAvgM [14] , FedDC [9] , FedAdam [32] , and TOP-k [1], FedPAQ [33] . Hyper-parameter Settings: The initial learning rate is searched in {0.01, 0.03, 0.05, 0.1, 0.2, 0.3}, with a decay of 0.998 and a weight decay of 0.001 for each round. Results on Convolutional Neural Network: From Tables 2 and 3 , and Figure 3 , we have the following observations: (i) Compared to FedAvg and its accelerated algorithms, FedBCGD significantly reduces the communication floats per round, converges faster, and achieves more robust final model performance. In the experiment of LeNet-5 on CIFAR100, FedBCGD (77𝑑) achieve 7.3× speedup to reach 40% accuracy, compared to FedAvg (558𝑑). (ii) FedBCGD+ further improves the convergence speed by client drift control and variance reduction, accelerating FedBCGD training process in experiments. In the experiment of ResNet-18 on CIFAR100, FedBCGD+ (154𝑑) achieves 1.8× speedup to reach 54% accuracy, compared to FedBCGD (277𝑑). However, in terms of the final testing accuracy, it does not outperform FedBCGD. This means that FedBCGD+ has a faster convergence speed, requiring less communication floats at the specified accuracy, while the higher accuracy of our FedBCGD algorithm ultimately means that it has better generalization ability. And the generalization ability of our FedBCGD framework is better than those of other algorithms, e.g., FedAvg. (iii) The final accuracy of FedBCGD is much higher than that of Centralised SGD, which means that our FedBCGD has better generalization performance. That is, FedBCGD and FedBCGD+ can jump from a poor local minimum and converge to sharp local minima. Figure 4 compares the effects of different block numbers under the same settings. When the number of blocks is 1, it degenerates into the FedAvgM algorithm. At the specified testing accuracy 53%, when the number of blocks is 20, our FedBCGD algorithm requires the least communication floats. The FedBCGD algorithm with 20 blocks achieves the highest accuracy with the same communication floats 200𝑑. As the number of blocks increases, the acceleration effect of the FedBCGD algorithm becomes more obvious.From Figure 5 , we can observe that freezing parameters in local training will cause client parameters to drift (purple line), resulting in poor performance. In addition, uploading parameters with shared parameters can improve convergence speed and final performance of the model (red line). Adding momentum compensation to client aggregation does accelerate convergence significantly (blue line).Table 4 : Comparison of each algorithm on CIFAR100 and CIFAR10. Heterogeneity is 𝜌 = 0.1, total communication floats are 1000𝑑, and the number of blocks in ResNet-18 is 𝑁 = 5. 𝜌 = 0.1 CIFAR100 (45%) CIFAR10 (78%) FedAvg [28] 45.8 ± 0.3 (741𝑑) 78.1 ± 0.4 (952𝑑) FedAvgM [14] 48.3 ± 0.6 (769𝑑) 78.6 ± 0.8 (997𝑑) FedAdam [32] 49.9 ± 0.5 (610𝑑) 71.4 ± 1.1 (∞) SCAFFOLD [17] 44.3 ± 0.3 (∞) 76.3 ± 1.4 (∞) FedDC [9] 46.6 ± 0.8 (278𝑑) 79.1 ± 0.8 (948𝑑) FedBCGD (ours) 59.5 ± 0.3 (147d) 86.2 ± 0.9 (212d) FedBCGD+ (ours) 59.9 ± 0.4 (200𝑑) 80.2 ± 1.3 (768𝑑) 90.4 ± 0.1 (24𝑑) 71.2 ± 0.1 (67𝑑) FedAvgM [28] 88.7 ± 0.3 (32𝑑) 76.7 ± 0.4 (10𝑑) FedAdam [32] 87.6 ± 0.2 (∞) 65.5 ± 0.6 (∞) SCAFFOLD [17] 88.2 ± 0.3 (88𝑑) 56.8 ± 1.1 (∞) FedDC [9] 85.8 ± 0. From results in Table 4 , we compare the convergence speed of our algorithms and baseline algorithms under high levels of data heterogeneity. It can be observed that when data heterogeneity is high (e.g., 𝜌 = 0.1), FedAvg converges slowly and struggles to reach the optimal point. In contrast, our algorithms consistently converge and achieve better model generalization. Moreover, under high data heterogeneity, FedBCGD+ slightly outperforms FedBCGD, demonstrating the effectiveness of the variance control strategy in our FedBCGD+ algorithm.In our experiments we get a phenomenon that our algorithm, FedBCGD and FedBCGD+, may generalizes better than Centralized SGD when the client data is not highly heterogeneous. The same phenomenon was also found in the literature [12, 23] . For highly non-convex problems, gradient decent and SGD methods are usually prone to fall into local minima, whereas the distributed methods local SGD are more prone to jump out of the local and sharp minimum and usually have better generalization ability [12] .Results on Communication-efficient FL: In Table 6 , the Fed-BCGD algorithm outperforms the traditional efficient federated learning algorithms TOP-k and FedPAQ in terms of convergence speed and final generalization accuracy. The convergence can be further accelerated when the quantization strategy of QSGD is added to the chunks of FedBCGD. Results on Vision Transformer: To verify the effectiveness of our algorithm on large models, we adopt the most classic ViT-Base model on the Tiny ImageNet and CIFAR100 datasets. For the initialization of the model, we used the pretrained model downloaded from the official website. We divide the ViT-Base model into six parameter blocks. From the experimental results in Table 5 and Figure 6 , we can observe that our FedBCGD algorithm can achieve the best results on the CIFAR100 dataset, and has more than 3× faster convergence speed, compared to FedAvg. The FedBCGD algorithm can achieve the best results on the Tiny ImageNet dataset, and attains more than 11.5× faster convergence speed. This can verify that FedBCGD can achieve excellent convergence speed on both Vision Transformer models and big datasets.Effectiveness of 𝜆: We tested FedBCGD using ResNet-18 on CIFAR100 dataset with momentum parameter 𝜆 taking the values of {0.4, 0.5, 0.6, 0.7, 0.8, 0.9} and 𝜌 = 0.6 . The convergence plots are shown in Figure 7 . We note that setting 𝜆 too small or too large impairs the convergence and generalization ability of FedBCGD. As shown in Figure 7 , when 𝜆 is relatively small, with 𝜆 = 0.4, the FedBCGD algorithm converges quickly, but the final generalization is not good. When we enlarge the value of 𝜆, 𝜆 = 0.8, the convergence is slower but the final generalization is good. Empirically, we find the best performance is achieved when the 𝜆 is set to around 0.8. We conducted the classification tests on the EMNIST (byclass) dataset on classical logistic regression problems:EQUATION)where 𝑎 𝑖 ∈ R 𝑑 and 𝑏 𝑖 ∈ {-1, +1} are the data samples, and 𝑁 is their total number. We set the regularization parameter 𝜆 = 10 -4 𝐿, where 𝐿 is the smoothness constant.From Figure 8 (a,b), we observe that our FedBCGD and Fed-BCGD+ algorithms demonstrate faster convergence speed. Particularly, under the strong convexity, our FedBCGD+ algorithm exhibits even faster convergence compared to our FedBCGD, which aligns with our theoretical analysis.  
conclusion: 
 This paper proposed the first federated block coordinate gradient descent method for horizontal federated learning. Moreover, we presented an accelerated version by using variance reduction and client parameter block drift control. In particular, we analyzed the convergence properties of the proposed algorithms, which show that our algorithms have significantly lower communication complexities than existing methods, and they also attain the best-known convergence rates for both convex and non-convex problems. Various experimental results verified our theoretical results and effectiveness of all the proposed algorithms. In the future, it is worthwhile to pay attention to how to more rationally divide model into blocks and how to choose the optimal parameter block to upload for clients.  
 
 Appendix:  


Decision: The paper proposes a block coordinate gradient descent method to improve communication efficiency in federated learning. Despite some concerns about model scalability and generalization, the reviewers' feedback has been largely addressed in the rebuttal. The final score of the paper reads as 3x borderline accept and 1x weak accept. After careful consideration of the reviewers' assessments and responses, ACs concur with the reviewers and recommend accepting this submission. Congratulations. Please carefully consider the reviewers' feedback and suggestions for revision and incorporate promises made in the rebuttal.

Reviews: review: paper_summary: paper_summary: This paper investigates block gradient descent for federated learning. The proposed FedBCGD method splits the model into multiple blocks and only updates a specific block to reduce the communication cost. Convergence analysis is also provided. Experiments are provided to demonstrate the outperformance.
strength_weakness: strength_weakness: The block-wise model update method is interesting.

Extensive theoretical analysis are provided for convergence analysis.

Diverse experiment evaluations and other comparisons are provided.
limitations: limitations: 1 How to ensure the scalability and generalization of the proposed method? Is there any principle on model partition? 

2 The model options are not convincing. The authors claimed “This paper is the first parameter block
communication work for training large-scale deep models”, while the largest model evaluated is the ViT-Base. At least a larger model should be considered. 

3 The baselines are not sufficient, which are not sota. A few more sota methods should be evaluated, such as MOON and FedDyn for federated optimization, and PruneFL for communication efficiency.

4 Minor: Do the first/last blocks include an input layer/classifier?
paper_summary: paper_summary: This paper presents a novel approach FedBCGD to improving communication efficiency in federated learning (FL) scenarios, particularly for large-scale models. The method reduces communication overhead by using block coordinate gradient descent, which is a novel contribution to the field of FL. Briefly, FedBCGD divides the model parameter into N blocks and a shared parameters block, each client only upload one of the N blocks and the shared block after local training. Differring from the BGD, the FedBCGD doesn’t freeze other parameters when update its own parameter block in a client. The authors also propose an accelerated version of the algorithm, FedBCGD+, which includes client drift control and stochastic variance reduction, indicating a deep exploration of the problem space. The paper also provides theoretical analysis of the proposed algorithms, including convergence properties, which adds to the quality of the research.

The problem of communication overhead in FL is significant, especially with the increasing size of models and data. The paper addresses this issue with potentially impactful solutions. The methods could be beneficial for applications in mobile intelligence, healthcare, and finance, where communication efficiency and data privacy are critical. The paper is structured logically and writes clearly. The proposed method appears to be the first of its kind to apply block coordinate descent to horizontal FL, which is an original contribution. And the accelerated version with variance reduction techniques, is also an innovative extension of the base algorithm.
strength_weakness: strength_weakness: 1. Introduces a novel method for improving communication efficiency in FL.
2. Provides an accelerated version with additional improvements.
3. Offers a comprehensive theoretical analysis.
4. Experimental results demonstrate the effectiveness of the proposed methods.
limitations: limitations: 1. The models in experiment is limited on classification tasks, the paper could benefit from a broader range of tasks to further validate the practical significance of the proposed methods.
2. The potential limitations of the proposed methods are not extensively discussed, which would be important for a balanced view.
3. The paper does not elaborate on how the block division strategy (not only the division number N) might affect different models or datasets, which could be an important consideration.
paper_summary: paper_summary: This paper primarily discusses two federated learning frameworks, FedBCGD and FedBCGD+, which are used to improve communication efficiency. Given that federated learning typically operates under constrained communication resources, the paper is well-motivated. Specifically, the methods proposed involve dividing model parameters into multiple blocks and sharing some of these blocks locally to facilitate model aggregation on the server, thereby completing the federated learning process. Additionally, FedBCGD+ introduces a control variant to reduce local client drift, thus accelerating the convergence of federated learning. The benchmarks show that both FedBCGD and FedBCGD+ outperform the baselines presented in the paper.
strength_weakness: strength_weakness: I believe this is a very comprehensive paper that uses the proposed FedBCGD framework to address the issue of communication efficiency and improves the framework to further address the heterogeneity problem, resulting in FedBCGD+. The paper provides a thorough theoretical analysis of FedBCGD and demonstrates well-presented experimental results. In its theoretical analysis, the paper considers both strongly convex and non-convex scenarios, and in the experimental section, it validates the proposed method using logistic regression and DNNs, thereby proving its superiority over other baseline methods.
limitations: limitations: My primary concern is the statement of novelty:
1. The statement in the paper, "we employ stochastic gradient descent to update all parameters instead of parameter freezing during local training," is a method that has been well-studied and is frequently used in personalized federated learning, such as [1]. It would be advisable to clarify so as not to mislead readers into thinking this is a novelty of this paper.
2. The control variant has been introduced in SCAFFOLD to address data heterogeneity. To me, FedBCGD+ seems more like an integration of control variance variables into FedBCGD.
3. Additionally, the differences between BCD or FedBCD [2] and FedBCGD are not clearly explained in lines 168-171. I recommend including FedBCD in the benchmark in Table 1, as the concepts of FedBCD and FedBCGD are similar concerning parameter block updates.

[1] Pillutla, Krishna, et al. "Federated learning with partial model personalization." International Conference on Machine Learning. PMLR, 2022.
[2] Y. Liu et al., "FedBCD: A Communication-Efficient Collaborative Learning Framework for Distributed Features," in IEEE Transactions on Signal Processing, 2022,

Some minor issues:
1. Lines 208-213: It appears that one sentence is repeated.
2. The abbreviation 'FL' is introduced but the full term is still used in the text.
3. All citations in the reference list in the supplementary material are marked with question marks, suggesting issues with citation formatting.
paper_summary: paper_summary: This paper proposes a novel Federated Block Coordinate Gradient Descent (FedBCGD) method for communication efficiency. Specifically, FedBCGD splits model parameters into several blocks including a shared block and enables uploading a specific parameter block by each client during training. The analysis of convergence and extensive experiments validate the value of the proposed methods.
strength_weakness: strength_weakness: 1. The paper is well written and easy to follow. 
2. The approach is thoughtfully designed with a solid theoretical analysis.
3. Evaluations and comparisons with other methods validate the value of FedBCGD.
limitations: limitations: 1. More comparisons with other Communication-efficient Federated Learning methods [1, 2, 3] should be conducted.
2. More datasets, especially in different modalities, should be used.

[1] Fedspeed: Larger local interval, less communication round, and higher generalization accuracy\
[2] Communication-Efficient Federated Learning with Accelerated Client Gradient\
[3] Communicationefficient adaptive federated learning.