Computer Science
Computer Science-2021.gz:143152
Computer Science
bdbe2ca01049b85bb7c6656aef27d2d2f50743d2
To Talk or to Work: Flexible Communication Compression for Energy Efficient Federated Learning over Heterogeneous Mobile Edge Devices

Recent advances in machine learning, wireless communication, and mobile hardware technologies promisingly enable federated learning (FL) over massive mobile edge devices, which opens new horizons for numerous intelligent mobile applications. Despite the potential benefits, FL imposes huge communication and computation burdens on participating devices due to periodical global synchronization and continuous local training, raising great challenges to battery constrained mobile devices. In this work, we target at improving the energy efficiency of FL over mobile edge networks to accommodate heterogeneous participating devices without sacrificing the learning performance. To this end, we develop a convergence-guaranteed FL algorithm enabling flexible communication compression. Guided by the derived convergence bound, we design a compression control scheme to balance the energy consumption of local computing (i.e.,"working") and wireless communication (i.e.,"talking") from the long-term learning perspective. In particular, the compression parameters are elaborately chosen for FL participants adapting to their computing and communication environments. Extensive simulations are conducted using various datasets to validate our theoretical analysis, and the results also demonstrate the efficacy of the proposed scheme in energy saving.


I. INTRODUCTION
The growing prevalence of mobile smart devices and the rapid advancement of social networking applications result in the phenomenal growth of the data generated at the edge network. To draw useful information from such geographically distributed data, federated learning (FL) has emerged as a promising paradigm that allows participating users to collaboratively learn a shared model, while keeping all the private training data on their edge devices. In particular, all the participants are allowed to run stochastic gradient descent (SGD) locally and send the intermediate gradients to the server periodically for global synchronization. The recent advances in mobile edge computing further facilitate the implementation of FL in mobile networks, since modern smart mobile devices are now armed with high-performance central processing units (CPUs) and graphics processing units (GPUs) to handle intensive computations of intelligent applications. With the technical advantages and implemental feasibilities, FL has seen recent successes in several applications, including next word prediction in Google's Gboard [1], vocal classifier for "Hey Siri" [2], mobile augmented reality [3], etc.
However, to practically deploy FL in wireless networks still faces several critical challenges. On the one hand, both transmitting the gradient updates and performing the local optimizations are resource-hungry, leading to considerable energy consumption at mobile edge devices during the training process. Despite improving computing capacity, mobile edge devices are generally subject to the limited battery lifetime, which hinders their applications in training complex models and supporting continuous learning. On the other hand, the mismatch between the heavy communication loads and the constrained wireless bandwidth hampers the efficient exchange of locally computed updates. The current trend of going deeper in the depth of neural networks has resulted in high-dimensional models with millions of parameters, which inevitably involves significant wireless traffic in global model synchronization. Things can only worsen when considering the heterogeneity of communication environments across different devices, where the learning efficiency may severely depend on a few stragglers with poor channel conditions. Several pioneering works have been done to manage system resources for efficient FL in wireless networks [4]- [8]. However, these studies overlooked reducing resource consumption intrinsically from the learning algorithm's perspective, hindering a substantial performance boost in resource utilization and training efficiency. A promising solution suggested in recent works in distributed learning is to incorporate stateof-the-art communication compression strategies into FL algorithms, which can considerably reduce the communication cost with little impacts on learning outcomes [9]- [14]. Yet the existing compressed distributed learning algorithms and the corresponding convergence analysis typically require identical compressor across all the participants, which ignores the heterogeneity in participants' communication capacity and thereby exhibits less flexibility. More importantly, this line of works mainly focuses on alleviating communication burdens in FL. However, the ever-increasing deployment of 5G networks that provides data rates as high as 1Gbps has shown a great potential to eliminate the communication bottleneck in FL, let alone the forthcoming 6G revolution [15]. For example, to transmit a Resnet-50, a commonly used deep network for image classification, with approximately 100MB parameters via 1Gbps wireless links typically consumes 0.16J, which is comparable to the energy consumption of performing a singlestep local training on one GPU (e.g., 0.2J for NVIDIA Tesla V100 [16], [17]). In light of this fact, it is worthwhile to investigate the impacts of both "working" (i.e., local computing) and "talking" (i.e., wireless transmission) and strike a balance between them via flexible compression control.
In designing a compression control scheme, we would like to communicate as few times and bits as possible to reduce the communication cost. At the same time, we attempt to incur as little distortion to the gradient information as possible towards fast convergence. However, these two goals are fundamentally in conflicts since deeper compression will naturally lead to more distortion on the gradients and more potential communication rounds to converge. When taking energy consumption of edge devices as the measure, this can be further interpreted as follows: Compressing the gradients severely and performing single-step local updates all the time could minimize the energy consumption per communication round. This may require extra communications to attain the targeted model accuracy, or even make the model fail to converge, and thereby impair the overall energy efficiency.
To tackle the challenges above, in this work, we study to improve the energy efficiency of FL over heterogeneous mobile edge devices. Considering the heterogeneous environments across participating wireless edge devices, we propose a flexibly compressed learning algorithm integrating local computation, gradient sparsification, error compensation, and batch size increment. Based on the convergence rate of the algorithm, we develop a compression control scheme that adapts the compression parameters to minimize all the devices' energy consumption on computing and communication.
Our salient contributions are summarized as follows: • We propose a convergence-guaranteed FL algorithm enabling flexible communication compression, which allows participants to compress the gradients to different levels before uploading. The convergence rate is analyzed theoretically and some insightful results are highlighted. • From the long-term learning perspective, we formulate a compression control problem using the derived convergence bound, where the goal is to achieve energy efficient federated training on edge GPUs over wireless networks. • Capturing the heterogeneity of participating edge devices in their computing and communication environments, we develop a control algorithm integrating Benders decomposition and inner convex approximation to determine the compression parameters for each participant. • We evaluate the performance of the proposed control scheme via extensive simulations, which verify the efficacy of our algorithms with various data sources, learning architectures, and system configurations.
The remainder of the paper is organized as follows. Section II reviews related work. Section III elaborates on the flexibly compressed FL procedures and provides the convergence analysis. Section IV presents an energy-efficient compression control algorithm. Section V gives the performance evaluation, and Section VI finally concludes the paper.
II. RELATED WORK FL over wireless networks has recently gained tremendous attention, whose system design is entangled with training acceleration, network optimization, and on-device resource allocation. Recognizing the limited computing and communication resources at edge computing systems, Wang et al. in [4] dynamically controlled the frequency of global synchronization to minimize the learning loss in real-time adapting to the resource budget. By exploring the unique properties of wireless multiple-access channels, Yang et al. in [5] developed a fast model aggregation approach with joint device selection and beamforming design, which considers only one communication round, and thus cannot guarantee the longterm training performance. To accelerate the training process, Chen et al. in [6] scheduled the participants of high significance for model uploading per communication round while allocating the uplink wireless resources properly. Capturing the trade-off between training time and participants' energy consumption, authors in [7] and [8] formulated optimization problems to jointly allocate the computing and communication resources by considering the heterogeneity of environments. While properly managing the system resources to enable FL in mobile edge networks, these studies overlook reducing resource consumption intrinsically in the essence of learning algorithm itself, thus hindering the substantial boost in training efficiency and resource utilization.
Some recent efforts on distributed learning algorithm design have been devoted to mitigating the communication bottleneck, which can be categorized into two directions: communication round reduction and communication traffic reduction. Specifically, McMahan et al. in [18] proposed the FedAvg algorithm (also known as local SGD) to reduce the frequency of global synchronization, which allows every participant to perform multiple local SGD iterations in a communication round, other than communicating after every local iteration. Authors in [19] and [20] used dynamically increasing batch sizes in distributed SGD to reduce the required number of communication rounds. In [21], a momentum SGD method was adopted to accelerate the convergence where the involved communications during training can be reduced accordingly. To reduce the traffic per communication round, one could let each participant communicate the compressed gradients rather than raw gradients for every global synchronization. For example, sparsified SGD studied in [10], [11] followed the idea that only a small subset of gradients with large magnitude are required to upload. Quantized SGD studied in [12], [14] allowed each participant to quantize the gradients into low-precision values before sending. Despite reduced communication complexity, the huge computing cost remains hinder FL on resource-constrained edge devices. Besides, most of the current gradient sparsification methods require identical sparsity levels across all the participants, ignoring the heterogeneity of participants and thereby exhibiting less flexibility. This work fills this gap by redesigning the compressed-federated learning algorithm with flexible and well-controlled compression parameters (e.g., global synchronization frequency and gradient sparsity). Simultaneously, heterogeneous computing and communication environments of participants are jointly considered to make the compression strategy suitable for mobile edge networks in practice.

III. FEDERATED LEARNING WITH COMPRESSION A. Federated Learning Algorithm Design
We consider an edge computing powered wireless network in which one base station and a set of mobile participants, denoted by M = {1, 2, ..., m, ..., M }, collaboratively train a deep neural network model via FL. We follow the common settings of synchronous FL as in [18] and assume that each participant maintains a locally collected dataset. The goal of collaborative training is to learn a global model that achieves uniformly good performance over all the participants, which can be formally described as minimizing a finite-sum nonconvex objective F : R d → R of the form Here, f m (w) is the loss function defined by the participant m's local dataset D m and the parameter vector w. Specifically, where |D m | is the size of D m and (x i m , y i m ) is the i-th sample in D m . Note here that we usually have D m = D j and ∇f m (w m ) = ∇f j (w j ) for any m = j since data are usually heterogeneously-distributed across participants in typical FL applications.
Aiming at reducing the communication cost during FL, we propose the Flexible Top k Local Stochastic Gradient Descent with Dynamic Batch sizes (FT-LSGD-DB) algorithm by integrating two state-of-the-art communication compression strategies, namely, local computations and gradient sparsification. The former allows each participant to perform more local computations on the edge device between every two global synchronizations, thereby reducing the total number of communication rounds. The latter lets participants explicitly sparsify the updated gradient tensors before uploading by retaining only a fraction of components, thereby reducing the size of communication payload in each round. Here, we use "Top k " compressor, a commonly used gradient sparsification approach, to take the sparsified top-k gradients. Specifically, for a vector x ∈ R d , Top k (x) ∈ R d , and the i th (i = 1, 2, ..., d) element of Top k (x) is defined by: On Edge Devices: 3: for m ∈ M in parallel do if t + 1 is an integer multiple of H then 8:

16:
At Central Server: 17: if t + 1 is an integer multiple of H then where x i denotes the i th element of x and thr is the k-th largest absolute value of the elements in x. In practice, k can be two to three orders of magnitude smaller than d while only sacrificing the model accuracy to a mild extent. In this case, the communication overhead involved in gradient transmission can be dramatically saved [11], [22]. Unlike previous studies requiring identical sparsity level across all the participants, FT-LSGD-DB injects more flexibility into training procedures by allowing the participating devices to perform gradient sparsification with different values of "k". This indeed helps to accommodate stragglers with poor channel conditions and thus mitigates the impacts of stale updates. Besides, FT-LSGD-DB novelly incorporates error compensation and batch size increment into FL procedures, which are two effective methods adopted and verified by practitioners recently. Specifically, error compensation is used to accelerate the global convergence by accumulating the error that arises from only uploading sparse approximations of the gradient updates, which ensures all gradient information does get eventually aggregated [10]. Using dynamically increasing batch sizes during training can maintain the known convergence rate with fewer communication rounds [20]. The pseudocode of our FT-LSGD-DB algorithm is given in Algorithm 1, and the details are described in the following.
Let {1, 2, ..., t, ...T } denote a set of iteration indices and assume that each participant performs H steps of local updates between every two global synchronizations. In each iteration t, evey participant m ∈ M performs: 1) Batch size increment: Exponentially increases its own SGD batch size with a factor ρ. 2) Local update: Update local parameter w m using the stochastic gradient ∇f m (w; m is a minibatch of size b sampled uniformly from D m at the t-th iteration. If aggregation is performed at iteration t (i.e., t is an integer multiple of H), every participant m ∈ M performs: 3) Error compensation: Add the local error e (t) m from the previous iteration into the gradient g to be equal to the global parameter w (t+1) . The training process above is repeated until achieving satisfactory accuracy. The following section further shows the convergence rate achieved by Algorithm 1 and derives the corresponding communication complexity.

B. Convergence Analysis and Discussion
We consider the following two standard assumptions on the local loss functions f m :

) Assumption 2 (Bounded variances and second momentum):
For every w (t) m ∈ R d and t ∈ Z + , there exists constants σ > 0 and G ≥ σ such that: Let δ m = d/k m ≥ 1 be the gradient sparsity chosen by the m-th participant. Under the assumptions above, the following theorem hold when Algorithm 1 is run with the sparsity series {δ m } ∀m .
Theorem 1: Suppose a constant learning rate 2L , we have the convergence rate for Algorithm 1: where δ = 1 M M m=1 δ 2 m is the root mean square of the sparsity series {δ m } ∀m and z T is a random variable which samples a previous parameter w (t) m with probability 1/M T . Proof: Please refer to Appendix for the proof. In Theorem 1, we settle for a weaker notion of convergence and use the average expected squared gradient norm to characterize the convergence rate due to the non-convex settings as [11] does. Based on this, we further give the following corollary on communication complexity of our FT-LSGD-DB algorithm.
Corollary 1: The maximum number of global communication rounds required for achieving an ε-global model convergence, i.e., satisfying E[||z T || 2 ] ≤ ε, is given by According to the convergence criterion, we suppose that Rearranging the terms, we get the maximum number of iterations as follows: In Algorithm 1, communications are only needed to aggregate individual gradient-update and happen only once every H iterations. Hence, the total number of necessary communication rounds is given by K = T /H, i.e., The results in (7) and (8) indicate that the gradient sparsity magnitudes of all the participants jointly take impacts on global convergence and communication complexity. Given a target model accuracy (i.e., ε), a higher δ results in a larger bound of communication rounds. Besides, aggressively enlarging H (i.e., "working" more) can also impair the learning efficiency as more communications may be involved.

IV. ENERGY-EFFICIENT FEDERATED LEARNING ON GPUS:
PROBLEM FORMULATION AND CONTROL ALGORITHM The theoretical results above reveal that both gradient sparsity levels {δ m } ∀m and global update frequency H play critical roles in convergence rate and communication efficiency from the learning perspective. Considering a realistic edge computing environment, we highlight that {δ m } ∀m and H also have great impacts on the energy consumption of participating edge devices, because they affect the payload required for transmitting and the workload required for processing, respectively. In this section, we aim to tune these two types of compression parameters accommodating heterogeneous FL participants for optimizing overall energy efficiency.
The positions of the non-zero entries can be identified by enumerating all possible sparsity patterns, which require S m,pos = log 2 d k m bits (14) to represent. Accordingly, we define S m as S m = s 1 (S m,val + S m,pos ) + s 0 bits, where s 0 and s 1 are coefficients indicating extra communication overhead involved in wireless transmitting [23]. Note that a federated training task usually lasts for a time duration in tens of minutes due to the huge volume of data required for transferring as well as the high computational complexity in running SGD. Thus, the channel conditions of participants may suffer from great fluctuations during a training period. For this reason, it is expected to consider the energy consumption of a training task from a long-term learning perspective. Here, we employ the average transmission rate of every participant m ∈ M, which is evaluated by where the expectation is taken over channel fading h m between participant m and the base station; N 0 indicates the power of additive white Gaussian noise; W m and P m denote the bandwidth and the transmitting power of participant m, respectively [24]. Afterward, the energy consumed to transmit the sparsified gradients by participant m is calculated as 2) Computational model: On-device learning, especially for training deep network models, is a compute-intensive task that has proved challenging to achieve adequate performance when running merely on CPUs of commodity mobile devices. Fueled by the recent advances in mobile hardware technology, GPU has become a ubiquitous hardware accelerator integrated virtually in every smart device to offer significantly more compute power. A typical GPU chip includes a multi-core GPU module and an associated GPU memory module where the voltage and frequency of GPU cores and GPU memory can be controlled separately. We model the energy consumed to execute a single iteration of GPU-accelerated mini-batch SGD at the m-th edge device as the product of the runtime power and the execution time, i.e., where P cmp m and T cmp m are two functions of the core voltage and the core/memory frequency [25], which are given by ( Here, P 0 m and T 0 m represent the static power consumption and static time consumption; v core m , f core m , f mem m denote the GPU core voltage, GPU core frequency, and GPU memory frequency, respectively; α, β, a and b are constant coefficients indicating the sensitivity to memory frequency scaling and the core voltage/frequency scaling, which depend on the hardware and the application characteristics. In this work, the value of α, β, a, and b are derived from platform-based experiments by measuring the average runtime energy consumption. Specifically, we measure the energy consumed to execute single-step SGD and estimate the parameters that appeared in the energy model in (18). For simplicity, we shall assume that E cmp m,ite keeps unchanged during training in spite of the incremental batch sizes used in Algorithm 1. This is reasonable due to the fact that GPUs are capable of parallel execution. When the training batch size remains under a threshold, GPUs can process the whole-batch samples simultaneously, leading to a near-constant execution time [16], [26]. In this case, the total energy 1 consumed between every two global synchronizations including H local iterations can be computed as 3) Problem Formulation: Given the communication model and the computational model above, we compute the total energy consumption of all the participating edge devices between every two global synchronizations as where α and β are constants used to approximate the big-O notion in (8). With the goal of overall energy consumption minimization, we jointly determine the gradient sparsity δ m for each participant m ∈ M and the global update frequency H by solving the following optimization problem: Here, constraints (24b) and (24c) restrict the feasible range of δ m and H with H ⊂ Z + , respectively. The formulated problem in (24) exhibits a certain trade-off between compression and convergence in the considered communicationcompressed FL setting. To minimize the energy consumption in single global iteration, one will severely compress the gradient tensor and decide to perform a single-step local update all the time, which would greatly impact the convergence rate and increase the number of global synchronizations. As a result, total energy consumption may increase considerably. In practice, the participants with excellent communication environments are expected to adopt slight gradient compression schemes for accelerating the convergence, while the others with poor channel conditions should be allowed to sparsify the gradients more severely to save the energy. In light of this, global update frequency and gradient sparsity should be carefully determined by considering the heterogeneity of participants for achieving energy-efficient FL.

B. Compression Control Algorithm
We develop a compression parameter control algorithm by approximately solving the formulated optimization problem in (24) that falls into the category of mixed-integer nonlinear programming. It is non-trivial to solve since the integer variable H is highly coupled with the continuous variables {δ m } ∀m . In the following, we first transform the permutation operator in (15) into a tractable form. Then we propose an efficient algorithm integrating generalized Benders decomposition and inner convex approximation to find a satisfactory solution of the considered compression control problem.
Corollary 2: Let δ m = d/k m be the chosen gradient sparsity and κ = FPP+1. The total number of bits required to be transmitted by participant m per global round, i.e., S m , can be approximated to Proof: Here, (a) is by Stirling formula that gives precise estimate for factorials, i.e., log 2 n! ≈ n log 2 n−n log 2 e, and (b) is due to δ m = d/k m ≫ 1. Substituting S m,pos into (15) yields (25). We can easily verify that S m (δ m ) is strongly convex w.r.t. δ m , when δ m ≥ e 3/2 by calculating its second order derivative: Extensive empirical evidence reveals that δ m ≥ e 3/2 always holds in practice so that gradient sparsification can considerably reduce the communication overhead. In the following, we assume that δ lb is set to be no less than e 3/2 and view S m (δ m ) as a strongly convex function without extra conditions. Using Corollary 2, we substitute Γ(·) by an approximated energy cost function and rewrite the problem in (24) as: To solve (27), we propose an algorithm integrating generalized Benders decomposition and inner convex approximation. Specifically, generalized Benders decomposition performs as the outer-loop algorithm to decompose the problem above into two sub-problems: a primal problem w.r.t. the continuous variables {δ m } ∀m and a master problem w.r.t. the integer variable H [27]. As the inner-loop algorithm, inner convex approximation is used to solve the primal problem by successively optimizing the approximants of the nonconvex objective. We solve the primal problem and the master problem in an alternative and iterative manner, as detailed in Algorithm 2. In each outer-loop iteration, solving the primary problem with given H yields an upper bound for the optimal value of (27) while solving the master problem provides its lower bound. Particularly, we formulate the primal problem in the i-th iteration with fixed H (i) as follows:

Algorithm 2 Compression Control Algorithm
Initialization: H (1) ∈ H; I out ; ǫ = 10 −5 ; ι = 10 −5 ; ξ = 10 −5 ; LBD = −∞; U BD = ∞; i = 1; Compute δ * m (δ ν m ), ∀m via (35) 6: Set ν = ν + 1 8: until ||δ ν − δ ν−1 || 2 2 ≤ ι Note that the primal problem above is always feasible for all H (i) since the continuous variables {δ m } ∀m are independent of H (i) in the constraint. Thus, we do not need to check the feasibility of the current H (i) as conventional Benders decomposition methods do [28]. Let {λ m1 } ∀m and {λ m2 } ∀m denote two sets of Lagrange multiplier corresponding to the constraints in (24b). We solve the primal problem to get the solutions of {δ m } ∀m , {λ m1 } ∀m and {λ m2 } ∀m , which are denoted by {δ We also update U BD with the objective value of (28a). Afterwards, a feasibility cut can be generated and added to the master problem as a new constraint. In particular, the master problem in the i-th iteration is given as follows: The master problem in (29) is a small-scale mixed-integer programming problem and can be solved using classical opti-mization algorithms, e.g., Branch-and-Bound. After solving it, we update LBD with the value of η. Now we focus on solving the non-convex primal problem (28), which is specified by the inner-loop procedures in Algorithm 2. Here, we use the inner convex approximation method to find the stationary points iteratively. The main idea is to successively optimize certain approximations of the non-convex objective function in (28a) while maintaining feasibility at each iteration. This requires us to derive a strongly convex approximant of (28a) around each feasible iteration. With a slight abuse of notation, we denote the objective function in (28a) by Γ(δ) with δ = (δ 1 , ..., δ M ) and rewrite it as the product of two functions, i.e., where Note that both Γ 1 (δ) and Γ 2 (δ) are positive and strongly convex since non-negative combinations of convex functions preserve convexity. Capturing such the "product of convexity" property of (30), we built an approximation for Γ(δ) as: where δ ν (δ ν 1 , δ ν 2 , ..., δ ν M ) denote the current intermediate δ obtained in the ν-th inner iteration [29]. Obviously, the approximated objective function in (33) is strongly convex and the corresponding approximations of the primal problem in (28) can be solved optimally, which is in the form of: Corollary 3 (Closed form of δ * m (δ ν ), ∀m): Let δ * m (δ ν ) be the optimal solution of δ m given the current δ ν . Then, each δ * m (δ ν ) has the following expression: where δ m (δ ν ) is given by Here, W (·) denotes the Lambert function.
Proof: This is derived by using the Karush-Kuhn-Tucker conditions. We omit the proof due to space limitation.
Thanks to the closed-formula for δ * m (δ ν ), Algorithm 2 can solve the inner-loop primal problem into optimality without resorting to any iterative solver that can provide approximate solutions only. We adopt the branch-and-bound algorithm to solve the master problem in (29) with computational complexity O(2 |H| ). When solving the primal problem takes I in inner-loop iterations in total, the overall complexity of Algorithm 2 is O(I out max{O(2 |H| ), I in }) in the worst case where I out denotes the number of iterations required by the outer loops.

V. PERFORMANCE EVALUATION
We evaluate the performance of the proposed compression control scheme, denoted by "FlexibleSpars", via extensive simulations. Particularly, we compare with the following three schemes: 1) SynSgdSpars allows participants to sparsify their gradients flexibly, and follows the typical setting of synchronous distributed gradient descent to perform global aggregation after every local update. 2) GreedySpars greedily makes the compression control decisions by minimizing the energy cost in the current round, which is oblivious to the impact of the trade-off relationship between the number of global rounds and the cost in a single round on the total energy consumption. 3) UnifiedSpar forces every participant to compress the gradients with a unified sparsity, regardless of the heterogeneous communication condition. Compression parameters are determined by solving a simplified version of the problem in (27). Fig. 1(a) demonstrates the average energy consumption with the varying number of participating devices. We see that the average energy consumption decreases with the growing scale of the FL system under all the schemes, while all the curves tend to be flat. This is due to the fact that increasing the number of participants can help to speed up the convergence of the training process and thereby save the resources at each edge device. Yet such speed-ups will be slight when the participating devices are enough to well capture the whole dataset's information and characteristics m D m for training. Among the four schemes, "SynSgdSpars" is shown to consume the most energy since it increases the communication complexity significantly. As expected, our proposed scheme "Flexi-bleSpar" outperforms the others as it injects more foresight than "GreedySpar" and more flexibility than UnifiedSpar into the compression decision-making, to better fit the heterogeneous communication conditions across participants. Fig. 1(b) further gives an insight into the impact of the heterogeneity level of participants' communication capacity on the system energy efficiency. Here, we set the number of participants 12 and divide them into four groups, corresponding to four capacity levels. Assume that participants belonging to the same group use the same wireless bandwidth for gradient exchanges. Let L be the level of heterogeneity that controls the variations in bandwidth among different groups. Fixing the average bandwidth W = 1GHz, we set the bandwidth adopted by the four groups as W − 0.03L (GHz), W − 0.01L (GHz), W + 0.01L (GHz), and W + 0.03L (GHz), respectively. We set the value of L to vary in {0, 1, ..., 14}, where larger L indicates higher level of heterogeneity. Fig. 1(b) elucidates that the high level of communication heterogeneity has a negative impact on FL and indeed impairs the system energy efficiency.
Notice that we omit the examination of "SynSgdSpars" in this setting since it performs so poorly that it is incomparable to the other schemes. Thanks to the flexible compression, our proposed scheme, as we would expect, exhibits more resilience than the others to cope with the scenario with high heterogeneity across participants in terms of wireless channel conditions.
We define ζ com = 1 M m Pms1 Rm (J/bit) and ζ cmp = 1 M m E cmp m,ite (J/iteration) representing the average energy intensity in terms of transmitting and computing, respectively. Keeping the above group setting of 12 participants with L = 10, we further examine the impacts of ζ com and ζ cmp on the optimal values of gradient sparsity {δ} ∀m and synchronization frequency H obtained from our control algorithm. The results are shown in Fig. 1(c)-1(d). Note that H can be viewed as the level of temporal sparsity in the sense that performing multiple local iterations between every two synchronizations implicitly sparsifies the communications in the temporal domain. In Fig. 1(c), "Sparsity-G1/2/3/4" denotes the decision of gradient sparsity for the participants in the group 1/2/3/4, respectively. "LocIteration" denotes the decision of their temporal sparsity H. When ζ com is small, participants are allowed to sparsify the gradients at a relatively low degree without adding to the total energy cost significantly. In this case, the number of global rounds is dominantly affected by the second term in (8), and a large temporal sparsity H is needed to reduce the number of necessary global rounds. As ζ com grows, all the participants tend to increase the gradient sparsity to fit the worsening communication conditions. We observe that the participants in Group 1 suffering the worst channel conditions generally prefer higher gradient sparsity than the participants in the other groups. When ζ com is large enough, the impact of communication on the total energy consumption becomes more profound than that of computing, forcing the participants to compress the gradients severely with the large {δ m } ∀m to alleviate the communication burden. Accordingly, the first term in (8) begins to take effects, resulting in the decreasing degree of temporal sparsity H. The analysis above can also be verified by Fig. 1(d), where we vary ζ cmp while keeping ζ com unchanged. We find that the curves in Fig. 1(d) are somewhat symmetrical to the curves in Fig. 1(c). The reason lies in that increasing ζ cmp can be viewed as decreasing ζ com in our system, both of which imply the process of computing cost becoming the bottleneck. Fig. 1(c)-1(d) reveal that there is a trade-off between gradient sparsity and temporal sparsity, which indeed corresponds to less "talking" and less "working". As expected, our flexible compression scheme allows participants to balance these two types of sparsity smoothly against one another for saving energy during training. Fig. 2 further presents the training results on several commonly used deep models and datasets. Specifically, Fig. 2(a)-2(b) show the convergence rate in terms of epochs and consumed energy respectively for ResNet20 [30] trained on CIFAR-10, while Fig. 2(c)-2(d) show the same things for LeNet5-Caffe [22] trained on MNIST. Here, we take ordinary distributed SGD as the baseline in which each participant transmits full gradients to the server after every local update. From Fig. 2(a) and Fig. 2(c), we observe that "FlexibleSpar" exhibits very similar behavior with "UnifiedSpar" in terms of convergence rate and final accuracy, both of which slightly underperform "SynSgdSpar". This also implies that temporal sparsity has a more profound impact on convergence rate than gradient sparsity in our setting. Due to delayed synchronization and imprecise gradient information, both "UnifiedSpar" and "FlexibleSpar" are shown to slow down the convergence at initial, which is consistent with our convergence analysis. In spite of this, "FlexibleSpar" is validated to be capable of saving energy for on-device training. As reported in Fig. 2(b) and Fig. 2(d), "FlexibleSpar" consumes ×1.5 − ×100 less energy than the other schemes to reach a given target accuracy.

VI. CONCLUSION
In this work, we have presented a holistic communication compression solution to reduce the energy consumption of FL over heterogeneous participating edge devices without sacrificing the model accuracy. We have developed a FL algorithm enabling flexible communication compression and provided the convergence analysis from a theoretical perspective. Considering the heterogeneous computing and communication conditions across edge devices, we have further designed an energy-efficiency oriented compression control scheme guided by the derived convergence bound. Extensive simulations have been conducted to verify the theoretical analysis and evaluate the algorithm's performance. The results have shown that our flexibly compressed FL scheme exhibits great potentials in accommodating heterogeneous mobile edge devices and improving the energy efficiency of FL over those edge devices.