Federated learning (FL) is an emerging distributed learning paradigm that enables multiple edge devices to train a common global model without sharing individual data [1]. This privacyfriendly data analytics technique over massive devices is envisioned as a promising solution to realize pervasive intelligence [2]. However, in many real-world application areas, mobile devices are often equipped with different local resources, which raises the emerging challenges for locally on-demand training [3]. Given different local resources status (e.g., computing capability and communication channel state) and personalized efficiency constraints (e.g., latency and energy), it is crucial to customize training strategies for heterogeneous edge devices.
We perform an in-depth analysis on the time delay and the energy consumption for performing the local model updates at edge devices. Specifically, we evaluate and record the cost of local training on three different NVIDIA Jetson family platforms (i.e., Nano, NX AGX, and Xavier AGX) under different channel states (i.e., good, medium, and poor). On the one hand, we observe that the learning efficiency differs significantly with diverse learning scenarios. As shown in Fig. 1, the singleepoch training on Nano with poor communication condition consumes about 4.0 times training latency than that of Xavier AGX with good communication condition, while its energy consumption is about 0.7 times less than the latter one's. On the other hand, we observe that the bottlenecks of latency and energy are induced by parameter transmission and local model training, respectively.
The above observations provide insights for a proper design of the on-demand FL system. To handle the resource heterogeneity, it is suggested to alleviate the energy and the latency cost of the local device. More importantly, the computation and communication costs should be jointly reduced to achieve efficient local training. In the literature, most existing studies either employ resource allocation and device scheduling to mitigate the system cost [4]- [10], or design gradient compression to accelerate the parameter transmission procedure [11]- [17]. The former method inherits the ideas of traditional design for mobile edge systems and takes no account of the optimization for neural networks, while the latter overlooks the computation cost of local model training.
In this paper, we propose "anycost" FL, named AnycostFL, to break the latency and energy bottlenecks for on-demand distributed training over heterogeneous edge devices. Our goal is to develop a cost-adjustable FL framework that enables edge devices to perform local updates under diverse learning scenarios. To this end, we first design the model shrinking and gradient compression to enable adaptive local updates with different computation and communication costs. Meanwhile, an enhanced parameter aggregation scheme is proposed to fuse the knowledge of the local updates. Following that, we investigate the on-demand learning of AnycostFL by regulating the local model structure, gradient compression policy and computing frequency under personalized latency and energy constraints. However, customizing training strategy for different learning scenarios is a non-trivial task, since how the global accuracy is affected by the local model structure and compression rate is still unknown. To address this issue, we theoretically reveal the convergence insights of our framework, which are further leveraged to guide optimization analysis. Finally, the optimal training strategy is derived for each device according to its locally available resource.
Our main contributions are summarized as follows.
• We propose a novel FL framework, named AnycostFL, that enables the local updates with elastic computation cost and communication overhead. • We theoretically present the optimal aggregation scheme and convergence analysis for AnycostFL. • We investigate the on-demand training problem of Any-costFL, and the optimal training strategy is devised to adapt the locally available resource.
• Extensive experiments indicate that the proposed Any-costFL outperforms the state-of-the-art efficient FL methods in terms of resource utilization and learning accuracy. The remainder of this paper is organized as follows. Section II describes related studies. In Section III, we detail the main operations of AnycostFL to fulfill the single-round training. The problem formulation, theoretical analysis and the corresponding solution are provided in Section IV. The experiment evaluations are presented in Section V, and we finally conclude the paper in Section VI and discuss the future directions.
Resource Management Methods. Resource management methods aim to reduce the FL system cost by arranging the local and system resources. Resource allocation methods employ frequency scheduling [18], transmission power control [19], and bandwidth allocation [20] to balance the cost of local training. Recent device selection methods directly exclude those weak devices with poor computation or communication capabilities to accelerate the convergence time [21]- [23]. Besides, topology-aware management is another very effective method to mitigate the network throughput [18], [24], [25]. However, these methods inherit the ideas of the efficient design for traditional mobile systems and overlook the optimization of neural networks.
Neuron-aware Techniques. Neuron-aware techniques focus on revealing the black box of neural networks to improve the training efficiency of the FL system. Early gradient compression utilizes sparsification [11], [26], and quantization [14], [27], [28] to reduce the transmission cost of FL system. In addition, feature maps fusion and knowledge distillation can be carried out to improve the information aggregation [29], [30].
Besides, FedMask proposes to train a personalized mask for each device to improve the test accuracy on the local dataset [31]. Recently, model structure pruning enables multiple devices with different model architectures to train a shared global model [32], [33]. Such methods can reduce the cost of local training, but how to customize optimal training strategies (e.g., gradient compression and model pruning policy) for different learning scenarios is still unknown.
In this section, we first outline the overall design of Any-costFL. Next, we detail the key techniques of our framework, including elastic model shrinking (EMS), flexible gradient compression (FGC), and all-in-one aggregation (AIO).
We consider a generic application scenario of FL with a set of I edge devices
where |D i | is the size of D i . Given the specified learning task, the original training workload of single sample W and the data size of uncompressed gradient S can be empirically measured.
As shown in Fig. 2(a), to reduce the computational complexity of the local model training and the communication cost of gradient update transmission, we propose AnycostFL with two device-side techniques, i.e., model shrinking and gradient compression. At the t-th global iteration of AnycostFL, the device i is enabled to adjust its training workload and gradient size as W t,i = α t,i W and S t,i = β t,i S, respectively. Here, α t,i ∈ (0, 1] and β t,i ∈ (0, 1] are defined as the model shrinking factor and the gradient compression rate, respectively. The training procedure of AnycostFL is summarized as follows.
1) Elastic local training: At the t-th global round, the device i downloads the latest global model w t from the parameter server. With the pre-calculated model shrinking factor α t,i , the specialized sub-model w α t,i = shrink(w t , α t,i ) can be efficiently derived, where function shrink(•, •) indicates the operations for model shrinking. Then, the local training is conducted with sub-model w α t,i and local data D i , and the updated local sub-model w α t+1,i is obtained. Furthermore, the local gradient update can be acquired as u t,i = w α t,i -w α t+1,i . 2) Flexible gradient upload: To further reduce the uplink traffic, the local device i is motivated to compress the gradient update u t,i before the parameter transmission. With the given compression rate β t,i , the compressed gradient update ũt,i = cmprs(u t,i , β t,i ) is uploaded to the server, where cmprs(•, •) is the function for gradient compression. 3) Parameter aggregation: The server collects the compressed local updates {ũ t,i } ∀i with different shrinking factors {α t,i } ∀i and compression rates {β t,i } ∀i . After that, the global update is calculated by ũt = aioagg({ũ t,i } ∀i ), where aioagg(•) is the server-side all-in-one aggregation. Then, the updated global model is computed as w t+1 = w t -ũt .
After the T -round training of the above three-step iterations, the final global model w T is obtained. Before introducing how to customize the values of {α t,i } ∀i and {β t,i } ∀i in Section IV, we illustrate the details of model shrinking, gradient compression and update aggregation in the rest of this section.
We aim to derive the sub-model w α t,i with training complexity of α t,i W from global model w t by reducing the width of the global model. The shrinking operations work as follows.
1) Server-side channel sorting: To avoid incurring extra memory cost for the edge devices, the server first sorts the channels of the latest global model before the model distribution. Given one layer of the weight of the global model, the server sorts the output channels in the current layer in descending order according to their values of L2 norm, and meanwhile, the input channels of the next layer should be sorted accordingly in the same order to maintain the permutation invariance of the whole model [34].
2) Layer-wise uniform shrinking: Next, the server broadcasts the weight of each layer of the global model in a channelby-channel manner. Instead of downloading the full global model, each device only receives those important parameters from the global model to assemble the local sub-model. Here, we utilize the fixed shrinking ratio for each layer in the same sub-model. Empirically, given model shrinking factor α t,i , we can reduce the size of the hidden layer by √ α t,i to acquire the sub-model. For example, as shown in Fig. 2(c), when shrinking a global model with hidden sizes of {16, 32, 64} under α t,i = 1 4 , we approximately reduce the size of each hidden layer by half as {8, 16, 32} to form the sub-model.
At the beginning of the t-th global round, all device initialize their local sub-models {w α t,i } ∀i by choosing the most important channels from the global model w t . In this way, the training complexity is significantly reduced while maintaining the performance of local sub-models. After that, the local training of device k is conducted with sub-model w α t,i , which produces the local gradient u t,i with data size of α t,i S.
Given the local update u t,i with the desired compression rate β t,i , we aim to obtain the compressed update ũt,i with data size of α t,i β t,i S. Let ρ t,i and L t,i denote the sparsity rate and the number of quantization levels, respectively. The gradient compression scheme works as follows.
1) Kernel-wise sparsification: Without loss of generality, we take the convolution neural network (CNN) as an example to illustrate the sparsification procedure. We aim to acquire the sparse update ût,i from u t,i . Let u t,i [k] denote the k-th kernel of u t,i , and u t,i = {u t,i [k]} ∀k . We measure the importance of each kernel and obtain N = { u t,i [k] 2 } ∀k , where • 2 denotes the L2 norm operation. Next, by selecting the ρ t,i Kth largest value in N as the threshold Π, the kernel-wise sparsification is expressed as
Meanwhile, the binary mask of ût,i is denoted as m t,i .
2) Probabilistic quantization: Motivated by the studies in [35], [36], we aim to obtain the quantized update ũt,i with the given sparse ût,i and the quantization level L t,i . Let u ∈ ût,i be a scalar value. To begin with, we first calculate the magnitude range of the non-zero elements of ût,i , denoted as [u min , u max ], where u min = min{|u|} ∀u =0 , and
l=1 denote the set of quantization points, where Q l is computed by
ut,1 ut,2 ut,3 ut Fig. 3. An illustration of the all-in-one aggregation.
For any u ∈ ût,i and u = 0, we can always find a quantization interval
, and its corresponding quantized value ũ is further computed by
where sgn(•) calculates the sign of the given scalar. Furthermore, the set of the quantization indices of all ũ ∈ ũt,i is denoted as
3) Lossless encoding: Due to the distribution characteristics of L t,i that smaller indices may occur more frequently, we apply entropy coding to reduce the data size [14], [37]. Besides, the sparse binary matrix m t,i can be compressed by Golomb encoding [11], [38].
After determining the compression scheme, we can vary the combinations of {ρ t,i , L t,i } and record the corresponding compression rates. Based on the results, we can build a piecewise linear function to predict the compression strategy {ρ t,i , L t,i } with the given β t,i . Notably, this function can be efficiently fitted by the server with a rather small amount of public training data (e.g., 16 samples) in an offline manner.
After all the devices upload their encoded updates, the server receives, decodes and then reconstructs the compressed local updates {ũ t,i } ∀i . Our goal is to obtain the global update ũt by aggregating {ũ t,i } ∀i . However, the aggregation of local updates in our framework cannot be supported by conventional FedAvg [1], since the local updates are produced by different model structures with different levels of precision (i.e., different quantization levels and sparsity).
To tackle the above challenge, we propose an all-in-one aggregation scheme that fuses the local updates in an elementwise manner. Let the set {1, 2, • • • , J} index elements of the global update ũt , and ũ[j] t denote the j-th element of ũt . To accomplish the aggregation for ũ[j] t , we first determine the subset of devices I j ⊆ I whose local model structure also contains the j-th element. Then, we have
t,i = 0,
where p t,i is the aggregation coefficient for the j-th device at the t-th global round. The optimal values of {p t,i } ∀i will be further analyzed in Section IV. Fig. 3 gives an example to illustrate the aggregation details. Specifically, different elements in the global update are updated by different subsets of devices, and more important elements will "absorb" knowledge from more devices. When the j-th element is zeroed out by all the devices in I j , we have ũ[j] t = 0.
In this section, we focus on the optimization of our framework by customizing the training strategies for diverse devices. We first formulate the on-demand training problem of Any-costFL. Then, we derive the upper bound of the convergence rate and reveal the key insights to improve the performance of AnycostFL. Based on the analysis, the optimization problem is transformed into a tractable form, and the closed-form solution is derived.
In this subsection, we formulate the computation and communication models for our framework. After that, we build up an on-demand learning problem that minimizes the global training loss with given delay and energy constraints.
1) Computation model: For the device i at the t-th global round, given the model shrinking factor α t,i and computing frequency f t,i , the time consumption of local model training can be measured by
where τ denotes the number of local epochs. Meanwhile, the corresponding energy consumption can be given by
where i is the hardware energy coefficient of the device i.
2) Communication model: We consider the frequency division multiple access (FDMA) scheme for the transmission of the local gradient update. For the device i at the t-th global round, the achievable transmitting rate can be estimated by
where P com t,i is the transmitting power; b i is the achievable bandwidth; |h t,i | denotes the path loss of wireless channel; N 0 is the power spectral density of the additive white Gaussian noise. For the device i at t-th global round, given the update ũt,i generated by the local model with a shrinking factor of α t,i and compression rate of β t,i , the required time T com t,i and energy consumption E com t,i of uplink transmission can be respectively measured by
, and
With the above computation and communication models, we next focus on the optimization problem of AnycostFL.
To optimize AnycostFL, we study an on-demand training problem. Specifically, the shared maximal latency for each round T max is determined by the server. The local energy consumption budget for each round E max t,i is customized by the device itself. Given multiple devices with diverse local resources (e.g., computation, communication and data), our goal is to customize the training strategy for each device to minimize the global training loss with personalized constraints (e.g., latency and energy). To sum up, at the t-th global round, we aim to optimize the following problem.
(P1) minF w t ; {α t,i } ∀i , {β t,i } ∀i (10) subject to:
) variables: {α t,i , β t,i , f t,i } ∀i , where F w t ; {α t,i } ∀i , {β t,i } ∀i denotes the global loss of the t-th round with given the global model weight w t under the training strategies of {α t,i } ∀i and {β t,i } ∀i . In the rest of this section, we analyze the relationship between training loss and training strategies. After that, Problem (P1) is further solved based on the theoretical insights.
Being in line with the studies in [5], [39], we make the following assumptions for the local loss function
Assumption 3. F i is twice-continuously differentiable. Based on Assumptions 1 and 2, we have νI ∇ 2 F i (w) λI. Assumption 4. The ratios between the norms of ∇F i (w) and ∇F (w) are bounded: ∇F i (w) 2 ≤ ε ∇F (w) 2 , where ε ≥ 0 is a positive constant. Assumption 5. For the moderate shrinking factor α ≥ α min , the first-shrinking-then-training can be approximated as firsttraining-then-shrinking: ∇F i (w α ) = [∇F i (w)] α . Here, we use [∇F i (w)] α to denote the shrinking operation for ∇F i (w).
Next, we give the following two definitions. Definition 1 (Local gradient divergence). The local gradient divergence δ t,i is defined as the difference between u t,i and ũt,i , which is given by δ t,i = u t,i -ũt,i . Definition 2 (Global gradient divergence). The global gradient divergence Δ t is defined as the difference between u t and ũt , which is measured by
Definition 1, u t,i and ũt,i may have different dimensions. We pad the missing elements in ũt,i with zeros before the arithmetic operation. Next, we are interested in how the training strategies {α t,i , β t,i } ∀i affect {δ t,i } ∀i and Δ t . We derive the following two lemmas. Lemma 1. For the local training with the model shrinking factor α t,i and compression rate β t,i . The square of the local gradient divergence is bounded by E δ t,i 2 ≤ 1α t,i (2α t,i ) β t,i 2 E u t,i 2 . (11) Proof. See Appendix A. Lemma 2. For the local update {ũ t,i , ∀i} with the corresponding training strategies {α t,i , β t,i } ∀i and aggregation coefficients {p t,i } ∀i , the square of the global gradient divergence is bounded by
(12) Proof. See Appendix B.
Intuitively, the local update u t,i generated with larger {α t,i , β t,i } may carry more accurate information, and thus a larger p t,i should be assigned during the aggregation. Based on Lemma 2, we deduce the following theorem. Theorem 1 (Optimal aggregation scheme). Given the local updates {ũ t,i } ∀i with corresponding training strategies {α t,i , β t,i } ∀i , the optimal aggregation coefficients are
Proof. Based on Lemma 2, we study the following optimization problem to minimize the global gradient divergence.
(P2) min
subject to: pt,i ≥0, ∀i, (14a)
It can be verified that Problem (P2) is a convex optimization problem. We further solve the problem by the Karush-Kuhn-Tucker (KKT) conditions. Let { } ∀i and θ be the Lagrange multipliers for Constraints (14a) and (14b), respectively. Then, we obtain
Being in line with the study in [40], we can obtain
By putting Eqn. ( 16) into Eqn. (14b), we obtain
Putting Eqn. (17) into Eqn. ( 16) completes the proof.
With the optimal aggregation scheme, we investigate the upper bound of the convergence rate of AnycostFL. Definition 3 (Local and global learning gains). The local and global learning gains are defined as g t,i = α 4 t,i β t,i and g t = i g t,i /I, respectively. Specifically, the local and global learning gains (i.e., g t,i ∈ [0, 1] and g t ∈ [0, 1]) measure the amount of effective information carried in the local and global updates, respectively. Theorem 2 (Convergence rate of AnycostFL). Let g min = min{g t } ∀t be the minimal global learning gain over the Tround training. The upper bound of the convergence rate of AnycostFL satisfies (18) where
Recall that parameters ν, λ and are defined in Assumptions 1 to 4 before. Proof. See Appendix C.
Based on Definition 3 and Theorem 2, we derive the following proposition. Proposition 1. The key to minimizing the training loss of AnycostFL is to maximize the learning gain g t for each global round. If g t = 1 ∀t, AnycostFL degrades to conventional FL without model shrinking and gradient compression.
Based on Theorem 2 and Proposition 1, Problem (P1) can be transformed into the following problem.
subject to: Constrains (10a) to (10e), variables:
Based on Constraints (10a) and (10b) for the training latency and energy, we obtain the following lemma. Lemma 3. The equality will always hold for Constraints (10a) and (10b) when confirming the optimal training strategy {α * t,i , β * t,i , f * t,i } ∀i , and thus T * t,i = T max and E t,i = E * t,i ∀i. Proof. The lemma can be proved by showing the contradiction. Suppose that there exists i 0 such that T * t,i0 < T max . We can find a new solution {α t,i0 , β * t,i0 , f t,i0 } for device i 0 and α
, such that T t,i0 = T max and E t,t0 = E max t,i . Since the global learning gain increases with the increase of α t,i0 , we have g t > g * t . Likewise, the contradiction also appears when E * t,i0 < E max t,i0 , and thus we complete the proof.
Based on Lemma 3, we employ two intermediate variables (i.e., φ t,i and ϕ t,i ) for each device to reparameterize Problem (P3). Specifically, φ t,i ∈ [0, 1] and ϕ t,i ∈ [0, 1] are the splitting factors for latency and energy, respectively, such that
By combining Eqns ( 6) and ( 20), the local learning gain of the device i at the t-th round can be rewritten as
where
Note that Problem (P3) can be transformed into I subproblems because the decision-making procedure of each device is independent. Based on Eqn. ( 21), the i-th subproblem can be expressed as a single-variable optimization problem with respect to φ t,i as follows.
(P4) m a x φt,i g t,i φ t,i (22) subject to: φ min t,i ≤ φ t,i ≤φ max t,i , where the lower and upper limits of φ t,i can be acquired by
Based on the first-order optimality condition ∂g t,i /φ t,i = 0, we obtain the stationary points as
where ψ t,i = 4(P com t,i T max )
2 -4E max t,i P com t,i T max + 9(E max t,i ) 2 . Let S t,i = {φ min t,i , φ max t,i , φ s1 t,i , φ s2 t,i } denote the union of the stationary points and the boundary points for Problem (P4). Then, S t,i = {φ t,i |φ t,i ∈ [φ min t,i , φ max t,i ], φ t,i ∈ S t,i } is the set of the feasible solutions of S t,i . The optimal solution for Problem (P4) can be acquired by φ * t,i = arg max φt,i∈S t,i g t,i (φ t,i ).
Furthermore, we obtain the optimal solution for device i at the t-th global round by putting φ * t,i into the following equations.
(26) Notably, the decision-making process of each device does not involve the auxiliary information of the resource status from other devices. At the beginning of each global round, each device can determine its training strategy locally.
We consider the FL application with image classification on Fashion-MNIST and CIFAR-10 datasets [41], [42]. For Fashion-MNIST, we use a small convolutional neural network (CNN) with data size of model update as 53.22Mb [1]. For the CIFAR-10 dataset, we employ VGG-9 with data size of model update as 111.7Mb [43]. For IID and non-IID data settings, we follow the dataset partition strategy in [34]. For the learning hyper-parameters, the learning rate, batch size and local epoch are set as {0.01, 32, 1} for Fashion-MNIST and {0.08, 64, 1} for CIFAR-10 dataset. The maximal latency is set as T max = 10 seconds TABLE I PERFORMANCE COMPARISON BETWEEN ANYCOSTFL AND OTHER METHODS ON FASHION-MNIST AND CIFAR-10 DATASETS. IID non-IID Dataset Method #Round Energy (KJ) Latency (min) Comp. (TFLOPs) Comm. (GB) Best Acc. (%) #Round Energy (KJ) Latency (min) Comp. (TFLOPs) Comm. (GB) Best Acc. (%) FMNIST {90%, 89%} * STC 305 (1.7×) 10.94 (1.4×) 25.42 (1.7×) 152.71 0.71 90.28±0.18 283 (1.3×) 10.17 (1.1×) 23.56 (1.3×) 141.53 0.66 89.47±0.16 QSGD 283 (1.6×) 11.40 (1.4×) 23.56 (1.6×) 141.53 0.80 90.39±0.04 279 (1.3×) 11.27 (1.2×) 23.28 (1.3×) 139.86 0.79 89.49±0.07 UVeQFed 247 (1.4×) 11.36 (1.4×) 20.58 (1.4×) 123.67 0.72 90.44±0.10 266 (1.2×) 12.21 (1.3×) 22.14 (1.2×) 133.01 0.77 89.64±0.16 HeteroFL 233 (1.3×) 12.03 (1.5×) 21.78 (1.5×) 92.21 0.57 90.43±0.13 242 (1.1×) 12.51 (1.3×) 22.62 (1.3×) 95.77 0.59 89.42±0.10 FedHQ 288 (1.6×) 13.89 (1.7×) 24.03 (1.6×) 144.36 0.86 90.21±0.07 313 (1.5×) 14.96 (1.6×) 26.06 (1.5×) 156.55 0.93 89.27±0.19 AnycostFL 179 (1.0×) 8.07 (1.0×) 14.94 (1.0×) 67.49 0.35 91.20±0.09 214 (1.0×) 9.63 (1.0×) 17.83 (1.0×) 80.51 0.42 90.32±0.14 CIFAR-10 {82%, 80%} * STC 341 (1.2×) 35.39 (1.3×) 56.83 (1.2×) 4160.56 1.78 85.38±0.29 412 (1.1×) 42.39 (1.3×) 68.67 (1.1×) 5026.84 2.15 83.09±0.53 QSGD 337 (1.2×) 39.82 (1.5×) 56.17 (1.1×) 4111.76 2.14 84.83±0.54 430 (1.2×) 50.29 (1.5×) 71.61 (1.2×) 5242.39 2.73 81.94±0.13 UVeQFed 296 (1.0×) 40.77 (1.5×) 49.28 (1.0×) 3607.45 2.12 85.09±0.16 377 (1.0×) 51.59 (1.5×) 62.89 (1.0×) 4603.87 2.71 82.30±0.28 HeteroFL 332 (1.1×) 50.07 (1.9×) 69.14 (1.4×) 3222.26 1.65 83.75±0.55 413 (1.1×) 62.88 (1.9×) 85.78 (1.4×) 3990.49 2.05 80.68±0.45 FedHQ 340 (1.2×) 48.95 (1.9×) 56.67 (1.2×) 4148.36 2.32 84.02±0.22 435 (1.2×) 61.99 (1.9×) 72.44 (1.2×) 5303.40 2.96 81.00±0.41 AnycostFL 294 (1.0×) 26.43 (1.0×) 48.94 (1.0×) 2459.92 1.56 87.72±0.23 372 (1.0×) 33.51 (1.0×) 62.06 (1.0×) 3118.60 1.98 84.91±0.51 * {x, y}: x and y denote the target global model accuracy under IID and non-IID data settings, respectively.
and the energy budget is set as E max t,i ∼ U [3,9] joules for the CIFAR-10 dataset, and the corresponding hyper-parameters for the FMNIST dataset are halved by default. Additionally, we set α min = 1/4 and β max = 1/15.
2) Setup for mobile system: We investigate a mobile system with I = 60 devices located within a circle cell with a radius of 550 meters, and a base station is situated at the center. To simulate the mobility, the position of each device is refreshed randomly at the beginning of each round [44]. For the computation, the energy coefficient is set as i ∼ U [5 × 10 -27 , 1 × 1 -26 ]. For communication, the bandwidth is set as 1MHz equally for each device, and the path loss exponent is 3.76. The transmission power is set as 0.1W, and N 0 is set as -114dBm/MHz.
We compare the proposed AnycostFL with the following efficient FL algorithms with three different random seeds.
• STC. The sparse ternary compression (STC) is adapted to reduce the cost of uplink parameter transmission [11]. • QSGD. The TopK sparsification and probabilistic quantization are combined to compress the local gradient [36]. • UVeQFed. The TopK sparsification and universal vector quantization are used to compress the local gradient [14]. • HeteroFL. Each device trains the local sub-model in different widths to match its computation capacity [32]. • FedHQ. Each device uses different quantization levels to compress the gradient according to its channel state [40]. I provides the best accuracy and required system cost for achieving the specified test accuracy. Particularly, when compared with HeterFL and FedHQ, AnycostFL can reduce up to 1.9 times the energy consumption to reach the test accuracy of 82% on CIFAR-10 dataset under the IID setting. When compared with STC, AnycostFL can reduce up to 1.7 times the time consumption to reach the test accuracy of 90% on FMNIST dataset under the IID setting. Moreover, our framework can significantly improve the best accuracy of the global model by 2.33% and 1.82% on CIFAR-10 dataset under the IID and the non-IID settings, respectively.
Fig. 5(a) verifies the advantages of the main techniques of AnycostFL. We gradually remove the elastic model shrinking (w/o EMS), the flexible gradient compression (w/o FGC) and the all-in-one aggregation (w/o AIO), and record the required system cost to achieve 80% test accuracy with CIFAR-10 dataset under the IID setting. We observe that the proposed EMS and FGC can significantly save the energy consumption and training time, respectively. Besides, AIO contributes to saving both energy and time. We next evaluate the impact of resource heterogeneity on the training efficiency in Fig. 5(b-c). We set the average energy coefficient i as 7.5 × 10 -27 and the average distance between the base station and edge devices as 400 meters, and then change their variances to simulate the computation and communication heterogeneity, respectively. The larger variance indicates a higher level of system heterogeneity. As we expect, the proposed AnycostFL shows more resilience than other baselines to tackle the high level of system heterogeneity.
We also evaluate the performance of sub-models in different widths in Fig. 5(d). Specifically, We compare AnycostFL with HeteroFL (i.e., local training with different widths) and STC (i.e., the best-performing compression-only method). The submodels are derived from the well-trained global model without further re-training. Surprisingly, the sub-models of the global model trained by AnycostFL can still maintain satisfactory test accuracy, which provides dynamic inference for diverse edge devices after the training time.
In this paper, we proposed AnycostFL, a joint computation and communication efficient framework for FL, that enables edge devices with diverse resources to train a shared global model. We aimed to minimize the global training loss under given personalized latency and energy constraints. By leveraging the theoretical insight of AnycostFL, we decomposed the optimization problem into multiple sub-problems. Following that, the optimal training strategy is derived for each device according to its locally available resource. Experiments demonstrate the advantage of our framework in improving the system efficiency and model performance compared to the state-of-the-art methods.
Rong Yu and Yuan Wu are the corresponding authors. This work was supported in part by National Key R&D Program of China under Grant 2020YFB1807802, in part by National Natural Science Foundation of China under Grants 61971148, 62102099, U22A2054 and 62001125, in part by Science and Technology Development Fund of Macau SAR under Grant 0162/2019/A3, in part by FDCT-MOST Joint Project under Grant 0066/2019/AMJ, in part by the Guangdong Basic and Applied Basic Research Foundation (2022A1515011287), and in part by US National Science Foundation under grant CNS-2107057. APPENDIX A PROOF OF LEMMA 1
Proof. For the given local gradient ũt,i with shrinking factor α t,i and gradient compression rate β t,i , we aim to capture the divergence between ũt,i and u t,i . Suppose that the absolute value of the element in u t,i follows uniform distribution |u| ∼ U (0, u max ), and u max = max{|u|} ∀u∈ut,i .
For clear notation, we sort the element-wise absolute value of u t,i in ascending order. Then, we obtain u
Based on Assumption 5, the update generated from local training with w α t,i is equal to shrink(u t,i , α t,i ). The operation of model shrinking on u t,i with α t,i can be viewed as removing (1α t,i )J elements with the least value from u t,i . Then, we obtain shrink(u t,i , α t,i ) = [0, . . . , 0, u
We next focus on the gradient compression. The operation of gradient sparsification on u t,i with sparsity of ρ t,i can be viewed as removing ρ t,i J elements with the least value from u t,i . Then, the quantization is conducted on the nonzero elements of ût,i , and we obtain cmprs(u t,i , β t
) Likewise to Eqn. (28), we have (A) = ρ 3 t,i E u t,i 2 . Based on Eqn. (4) and the statistical feature of u t,i , we obtain (B) = (1ρ t,i ) 3 E u t,i 2 /(2L 2 t,i ). Given plain update u t,i in 32-bit floating point and the desired compression rate β t,i , we can set ρ t,i = 1β t,i and L t,i = 2 32 √ βt,i for the analysis. In this way, the operations of sparsification and quantization contribute equally to the gradient compression. Furthermore, we have E ut,icmprs(ut,i, βt,i) 2 ≤ (1βt,i) 2 E ut,i 2 . (30) Next, we focus on the local divergence δ t,i with respect to α t,i and β t,i . According to the Definition 1, we have E δt,i 2 = E ut,icmprs([ut,i] α , βt,i) 2 = E ut,i -[ut,i] α 2 + E [ut,i] αcmprs([ut,i] α , βt,i) 2 + 2 < ut,i -[ut,i] α , [ut,i] αcmprs([ut,i] α , βt,i) > (C)
. (31) It can be verified that the two vectors in term (C) are orthogonal, and we obtain (C) = 0. According to Eqns ( 28) and ( 30), we further obtain
≤ (1αt,i)
3 E ut,i 2 + (1βt,i) 2 αt,i(α 2 t,i -3αt,i + 3)E ut,i 2 (b) ≤ 1αt,i(2αt,i) βt,i 2 E ut,i 2 . (32) Likewise to Eqn. (28), inequality (a) stems from the fact that E [u t,i ] α 2 = α t,i (α 2 t,i -3α t,i +3)E u t,i 2 . Besides, inequality (b) holds for all α t,i ∈ [α min , 1] and β t,i ∈ [0, β max ]. Thus, we complete the proof. APPENDIX B PROOF OF LEMMA 2 Proof. Based on Definition 2 and Lemma 1, we have E Δt 2 = E I i=1 pt,iut,i -I i=1 pt,i ũt,i 2 ≤ E I i=1 pt,i 1αt,i(2αt,i) βt,i ut,i 2 . (33) We use η to denote the learning rate, and u t,i = η∇F i (w t ). Based on Assumption 4, we obtain E Δt 2 ≤ εη 2 I i=1 pt,i 1αt,i(2αt,i) βt,i 2 E ∇F (wt) 2 . (34) According to Cauchy-Schwarz inequality, we obtain E Δt 2 ≤ Iεη 2 I i=1 p 2 t,i 1αt,i(2αt,i) βt,i 2 E ∇F (wt) 2 .
(
Thus, we complete the proof.
Proof. Inspired by the studies in [5], [39], we deduce the convergence analysis of AnycostFL. According to Taylor expansion and Assumption 3, we have
F (wt+1) ≤ F (wt) + (wt+1 -wt) ∇F (wt) + λ 2 wt+1 -wt 2 = F (wt) -ũ t ∇F (wt) + λ 2 ũt 2 . (36) By using learning rate η = 1 λ , we obtain E F (wt+1) ≤ E F (wt)λ (ut -Δt) ut + λ 2 ut -Δt 2 = E F (wt) -1 2λ ∇F (wt) 2 + λ 2 Δt 2 . (37) We now pay attention to the upper bound of Δ t 2 . Based on Jensen's inequality and Eqn. (34), we obtain E Δt 2 ≤ εη 2 I i=1 pt,i 1αt,i(2αt,i) βt,i 2 (D) E ∇F (wt) 2 . (38) By putting Eqn. (13) into (A), we have E D ≤ E I I i=1 1 (1-αt,i(2-αt,i) √ βt,i) 2 (c) ≤E I I i=1 1 1-α 4 t,i βt,i , (39) where (c) always holds for α t,i ∈ [0, 1] and β t,i ∈ [0, 1]. According to Definition 3, we have g t,i = α 4 t,i β t,i and g t = i g t,i /I. Since 1/ i 1 1-gt,i is a concave function with respect to g t,i , based on Jensen's inequality, we obtain E A ≤ I i 1 1-E(α 4 t,i βt,i) = 1g t . (40) Since the training strategies of each device and the norm of the gradient of global data ∇F (w t ) are independent, by putting Eqn. (40) back to Eqn. (38), we obtain E Δ t 2 ≤ E εη 2 1g t ∇F (w t ) 2 . (41) Next, by putting Eqn. (41) back to Eqn. (37), we have E F (wt+1) ≤ E F (wt) -1 + ε gt -1 2λ ∇F (wt) 2 . (42) Subtracting F (w * ) in both sides of Eqn. (42) yields E F (wt+1 -F (w * ) ≤ E F (wt) -1 + ε(gt -1) 2λ ∇F (wt) 2 -F (w * ) .
(
Based on Assumptions 2 and 3, we have [5], [45] ∇F (w t ) 2 ≥ 2ν F (w t ) -F (w * ) . (
Plugging Eqn. (44) into Eqn. ( 43), we have E F (w t+1 ) -F (w * ) ≤ Z t E F (w t ) -F (w * ) , (45) where Z t = 1 -ν λ (1ε(1g t )). Let g min = min{g t } ∀t be the minimal global learning gain over T global rounds. By recursively applying the above inequality from iteration round 0 to T , we can obtain E F (w T ) -F (w * ) ≤ Z T -1 E F (w 0 ) -F (w * ) , (46) where Z = 1 -ν λ 1ε(1g min ) . Thus, we complete the proof.
Authorized licensed use limited to: University of Houston. Downloaded on August 28,2024 at 17:39:18 UTC from IEEE Xplore. Restrictions apply.