{'fraction_non_alphanumeric': 0.0285471888471063, 'fraction_numerical': 0.0071310648445382, 'mean_word_length': 4.698066370525216, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Accelerating DNN Training in Wireless Federated Edge Learning System

Training task in classical machine learning models, such as deep neural networks (DNN), is generally implemented at the remote computationally-adequate cloud center for centralized learning, which is typically time-consuming and resource-hungry. It also incurs serious privacy issue and long communication latency since massive data are transmitted to the centralized node. To overcome these shortcomings, we consider a newly-emerged framework, namely federated edge learning (FEEL), to aggregate the local learning updates at the edge server instead of users' raw data. Aiming at accelerating the training process while guaranteeing the learning accuracy, we first define a novel performance evaluation criterion, called learning efficiency and formulate a training acceleration optimization problem in the CPU scenario, where each user device is equipped with CPU. The closed-form expressions for joint batchsize selection and communication resource allocation are developed and some insightful results are also highlighted. Further, we extend our learning framework into the GPU scenario and propose a novel training function to characterize the learning property of general GPU modules. The optimal solution in this case is manifested to have the similar structure as that of the CPU scenario, recommending that our proposed algorithm is applicable in more general systems. Finally, extensive experiments validate our theoretical analysis and demonstrate that our proposal can reduce the training time and improve the learning accuracy simultaneously.

the most cutting-edge technique in both academia and industry communities and is envisioned as a revolutionary innovation enabling a smart earth in the future [1]. The implementation of AI in wireless networks is one of the most fundamental research directions, leading the trends of communication and computation convergence [2]- [4]. The key idea of implementing AI in wireless networks is leveraging the rich data collected by massive distributed user devices to learn approximate AI models for network planning and optimization. Various conceptual and engineering AI breakthroughs have been applied for wireless network design, such as channel estimation [5], signal detection [6], and resource allocation [7], [8].
In despite of the substantial progress in AI techniques, current learning algorithms demand enormous computation and memory resources for data processing. However, the training data in wireless networks is unevenly distributed over a large amount of resource-constrained user devices, whereas each device only owns a small fraction of data [9]. These two hostile conditions make it hard to implement AI algorithms in user devices. Conventional solution generally offloads the local training data to a remote cloud center for centralized learning. Nevertheless, this method suffers from two key disadvantages. On the one hand, the latency for data transmission is typically very large because of the limited communication resource. On the other hand, the privacy information involved in the training data may be leaked since the cloud center can be inevitably attacked by some malicious third parties. Hence, classical cloud-based learning framework is no longer suitable for the scenarios where data privacy is of paramount importance, such as intelligent healthcare system and smart bank system [10] .
To address the first issue, an innovative architecture called mobile edge computing (MEC) has been developed by implementing cloud computation capability at the network edge and migrating learning tasks from the cloud center to the edge server [11]. By this means, the communication latency can be significantly reduced [12], the mobile energy consumption can be extensively saved [13], and the core network congestion can be notably relieved [14]. To overcome the second deficiency, a novel distributed learning framework, namely federated learning (FL) has been recently proposed in [15]. The key idea of this framework is to globally aggregate local learning updates (gradients or parameters) trained on user devices in a centralized node while keeping the privacy-sensitive raw data remained at local devices. Toward this end, the benefit of the shared models trained from the affluent data can be reaped and the computation resources of both user devices and cloud servers can be collectively exploited [16]. Motivated by this, effective collaboration between MEC and FL, referred to as federated edge learning (FEEL) has the great potential to facilitate AI implementation in wireless networks [17].
This paper makes use of the FEEL framework to accelerate the training task of general deep neural networks (DNN). We are inspired by the pioneering studies on applying FL to learn AI models [18]- [27]. In [18], a practical FederatedAveraging algorithm for distributed DNN training has been developed, while both independently and identically distributed (IID) and non-IID datasets are used to test its learning performance. Two approaches called structured updates and sketched updates have been proposed to reduce communication cost between the center node and the user devices [19]. Based on this, substantial studies have devoted great effort to further reducing the communication overhead by developing effective compression methods [20]- [23]. Moreover, via creating a shared subset of data gathered from user devices, an efficient collaborative learning strategy for non-IID data distributed system has been devised to improve the learning accuracy [24]. In addition, the authors in [25] have investigated the multi-task FL system and proposed a system-aware optimization framework to balance the communication cost, stragglers, and fault tolerance. Particularly, a block-chained FL architecture has been introduced in [26], where the optimal block generation rate has been derived to minimize the end-to-end latency. Last but not least, a prominent broadband analog aggregation scheme based on the overthe-air computation technology has been proposed in [27], and two communication-and-learning tradeoffs have been presented to achieve a low-latency FEEL system.
The precedent works on FL mainly focus on accelerating the training task from the communication perspective, i.e., reducing the communication overhead between centralized node and user devices. However, the optimization for the training task itself is also crucial and has not been investigated yet. To facilitate the intelligent system implementation, we consider the joint communication and computation resource allocation in this paper. The major hyperparameter, i.e., the training batchsize is also optimized to improve the training efficiency. This work is most closely related to the pioneering work of [28], which has developed a control algorithm to achieve the tradeoff between local update and global parameter aggregation under fixed resource budget. In contrast, we go one further step toward the training batchsize optimization from the learning perspective. Our main result is that the batchsize of each device should dynamically adapt to the wireless channel condition in order to achieve lower training latency and higher learning accuracy. The main contributions of this work are summarized as follows.
• To quantitatively analyze the training process, we first define a significant global loss decay function with respect to the training batchsize. Based on this, a novel criterion, namely learning efficiency is also developed as the ratio between the global loss decay and the end-to-end latency, which can well evaluate the system learning performance.
• We theoretically analyze the detailed expression of the learning efficiency in the CPU scenario and formulate a training acceleration problem under both communication and learning resource budgets. The closed-form expressions for joint batchsize selection and communication resource allocation are also derived. Specifically, the optimal batchsize is proved to scale linearly with the local training speed and increase with both the training priority ratio and the uplink data rate in the power of −1/2.
• We extend the training acceleration problem to the GPU scenario and develop a new training function to characterize the relation between the training latency and the batchsize of general GPU modules. The corresponding solution in this scenario is manifested to have the similar structure as that in the CPU scenario, revealing that our proposed algorithm can be applied in more general systems.
• The proposed algorithms in both CPU and GPU scenarios are implemented in software.
Several classical DNN models are used to test the system performance based on a real image dataset. The experimental results demonstrate that our proposed scheme can attain a better learning performance than some benchmark schemes.
The rest of this paper is organized as follows. In Section II, we introduce the FEEL system and establish the DNN model and the channel model. In Section III, we quantitatively analyze the training process and formulate the training acceleration optimization problem in the CPU scenario. The closed-form solution for the CPU scenario is developed in Section IV. In Section V, we extend the training acceleration problem to the GPU scenario and discuss the solution in this case. Section VI presents the experimental results and the whole paper is concluded in Section VII.

A. Federated Edge Learning System Model
As depicted in Fig. 1 and constitutes its local dataset D k = {(x 1 , y 1 ), . . . , (x N k , y N k )}, where x i is the training sample and y i represents the corresponding ground-true label.
To accomplish the training task, two schemes have been widely employed: 1) centralized learning, i.e., each device directly uploads the raw data to the base station (BS) for global training, and the updated model is then multicast back to each device; 2) individual learning, i.e., each device trains an independent model via local dataset without any collaboration. The former faces with severe privacy issue since the edge server is inevitably attacked by some malicious third parties. In contrast, the latter is capable of avoiding privacy disclosure but suffers from isolated data island. Thus, the learning accuracy and reliability cannot be guaranteed. To deal with the above two issues, we adopt the FEEL scheme to accelerate the training task and improve the learning accuracy simultaneously. In this scheme, the edge server only aggregates the local gradients without centrally collecting the raw data. 1 For convenience, we define the following five steps as a training period, which is periodically performed before achieving a satisfactory learning accuracy. The detailed procedures can be summarized as follows.
• Step 1 (Local Gradient Calculation): In each training period, say the n-th period, each device first selects the training data from the local dataset, performs the forward-backward propagation algorithm, and then derives the local gradient vector g w k [n], where w is the parameter set of the DNN model.
• Step 4 (Global Gradient Downloading): After finishing the gradient aggregation, the edge server delivers the global gradient g w [n] to the BS, which broadcasts it to all user devices.
where η[n] is the step-size in the n-th training period.

B. DNN Model
In this work, we take a generalized fully-connected DNN model for analysis. To comprehensively characterize the network structure, we denote L as the number of layers, where the i-th layer is equipped with n i neurons. Then in the (i + 1)-th layer, the number of weights between each pair of connected neurons and the number of biases added to each neuron are n i n i+1 and n i+1 , respectively. Therefore, the total number of parameters (weights and biases) is given by We assume that the DNN model is deployed in each user device and the edge server. Moreover, the local loss function of each device that measures the training error is defined as where ℓ(w, x i , y i ) is the sample-wise loss function that quantifies the prediction error between the learning output (via input x i and parameter w) and the ground-true label y i . Accordingly, the global loss function at the edge server can be expressed as The target of the training task is to optimize the parameters towards minimizing the global loss function L(w) via the SGD algorithm. Further, the gradient vector of each device can be expressed as where ∇ implies the gradient operator. Note that each parameter has a counterpart gradient, therefore the total number of gradients of each device exactly equals p in (3).

C. Communication Model
Without loss of generality, we adopt the typical TDMA method for data transmission in this paper. Let P U k denote the transmit power of device k for gradient uploading and h U k denote the uplink channel power gain. Accordingly, denote P D k as the transmit power of the BS for transmitting the global gradient to device k and h D k as the downlink channel power gain. It should be emphasized that the durations of both uplink and downlink time-slots are relatively short (e.g., the frame duration of LTE protocol is 10 ms), during which the channel power gains keep fixed. However, the time duration for one training period is usually in the time-scale of second because of the high computational complexity in running SGD algorithm as well as the limited computation resource of user devices. In view of this, each training period will experience multiple time-slots. Since this work focuses on accelerating the training task from the long-term learning perspective, the channel dynamics would not affect the learning performance too much. Toward this end, we employ the average uplink and downlink data rates instead of the instantaneous ones, which can be respectively evaluated as where E h represents the expectation over channel fading, W denotes the system bandwidth, and N 0 implies the variance of additive white Gaussian noise (AWGN).
Thus far, we have elaborated the detailed procedures of the FEEL scheme and established both the learning and communication models. In the next, we will analyze the training task and formulate the training acceleration optimization problem. In our work, the edge server is always equipped with powerful GPU whereas the training module of user devices can be either CPU or GPU. Therefore, we will respectively investigate the CPU and GPU scenarios in the sequel.

III. FEDERATED LEARNING IN CPU SCENARIO: PROBLEM FORMULATION
In this section, we will first investigate the CPU scenario where each device is only equipped with CPU for DNN training. The training acceleration problem is formulated to maximize the system learning efficiency. Some insightful results about network planning are also discussed.

A. Training Loss Decay Analysis
To accelerate the training process and achieve a satisfactory learning accuracy, we take the mini-batch SGD algorithm in this paper. As is known to us, the major difficulty performing this algorithm is the selection of the hyperparameter, i.e., the training batchsize, which greatly affects the learning accuracy and is valuable to be optimized.
To quantitatively assess the training performance, we first define an auxiliary function, namely global loss decay, as which represents the difference of the global loss function across the n-th training period. For brevity, we rewrite ∆L[n] as ∆L since our following analysis is based on one training period.
Now we analyze the training performance of the introduced FEEL system. Recall that in one training period, each device first selects a subset of data, namely one batch for local gradient calculation. Denote B k as the number of data involved in the batch of device k. Then the edge server aggregates the gradient information from all devices and calculates the global gradient.
Therefore, the FEEL system is capable of processing B = K k=1 B k data in one training period, which is referred to as global batchsize. Note that the target of the training task is toward minimizing the global loss function. Then according to [29], the relation between the global loss decay function and the global batchsize can be approximately evaluated as where ξ is a coefficient determined by the specific structure of the DNN model. We shall remark that the global loss decay does not increase linearly with the global batchsize. It is because that the learning rate should adapt to the batchsize to ensure the convergence of the mini-batch SGD algorithm and guarantee the learning accuracy as well [30].

B. End-to-End Latency Analysis
As mentioned earlier, we aim at accelerating the training task by collaboratively leveraging the data information and computation resources among all devices. Therefore, the end-to-end latency of the training period is also an essential term to be optimized. In the following, we will mathematically calculate the latency of each step in one training period.
• Local Gradient Calculation Latency: In the CPU scenario, each device is equipped with CPU for DNN training. We measure the computation capacity of each device by its CPU frequency, denoted by f C k (in CPU cycle/s). Moreover, let C L denote the number of CPU cycles performing the forward-backward propagation algorithm with one data. Due to the fact that CPU operates in serial mode, the local gradient calculation latency is given by • Local Gradient Upload Latency: The local gradient vector of each device should be quantized and compressed before transmission. 2 Denote the average quantitative bit number for each gradient as d. Let r denote the compression ratio, which is defined as the ratio between the compressed gradient data size and the overall raw gradient data size. Then the total data size for each local gradient vector is s = r × d × p. Recall that we adopt the TDMA channel access for data transmission. Let T U f denote the length of each uplink radio frame (usually 10 ms in LTE standards) and τ U k denote the time-slot duration allocated to device k. Therefore, the local gradient upload latency can be expressed as • Global Gradient Download Latency: When the edge server finishes gradient aggregation, it broadcasts the global gradient vector to each device. To consist with the uploading procedure, we use d bits to quantize each global gradient term and leverage the same gradient compression technique. Similarly, let T D f denote the length of each downlink radio frame and denote τ D k as the time-slot duration allocated to device k for global gradient downloading. Thus, the global gradient download latency can be expressed as • Local Model Update Latency: After receiving the global gradient, each device starts to update its local model via the gradient-descent method, as presented in (2). Denote M C as the number of CPU cycles that are required for local model update. Then, the local model update latency is given by It should be noted that the edge server has powerful GPU modules so that the gradient aggregation latency can be reasonably neglected. Moreover, the gradient aggregation at the edge server cannot start until receiving the local gradient vectors of all devices. Therefore, in one training period, the end-to-end latency of each device can be expressed as Accordingly, the end-to-end latency of the FEEL system in one training period is given by

C. Problem Formulation
In this paper, we aim at accelerating the training task while guaranteeing the learning accuracy.
To better reflect the training performance, we first define a novel evaluation criterion from the learning perspective, as presented below.

Definition 1:
The training performance of the FEEL system can be evaluated by the learning efficiency, which is defined as Remark 1: The learning efficiency can be interpreted as the average global loss decay rate in the duration of one training period. Therefore, improving the learning efficiency is equivalent to accelerating the training process. In view of this, the learning efficiency is an appropriate metric to evaluate the system training performance.
Based on the above analysis, the objective of training acceleration can be transformed into the learning efficiency maximization. Therefore, the optimization problem can be mathematically formulated as where (18b) and (18c) represent the uplink and downlink communication resource limitations, respectively, (18d) gives the overall number of data that can be processed in one training period, and (18e) bounds the minimum and maximum batchsizes of each device, where B max is determined by the memory size and the CPU configuration of each device.
It can be observed that the objective function in problem P 1 is complicated and non-convex, making it hard to be solved in general. In the next section, we will decompose it into two subproblems and devise efficient algorithms to solve them individually.

IV. FEDERATED LEARNING IN CPU SCENARIO: OPTIMAL SOLUTION
In this section, we first analyze the mathematical characteristics of problem P 1 and then equivalently decompose it into two subproblems. The closed-form solutions for both subproblems are derived individually and some insightful results are also discussed.

A. Problem Decomposition
The main challenge in solving problem P 1 is that the denominator of the objective function is non-smooth. For ease of decomposition, (18a) can be rewritten as It can be seen that the local gradient upload latency t U k is determined only by the uplink communication resource τ U k , while the global gradient download latency t D k is determined only by the downlink communication resource τ D k and is independent of other variables. Meanwhile, τ U k and τ D k are generally independent of each other according to (18b) and (18c). Toward this end, one training period can be divided into two subperiods. The first subperiod aims to perform local gradient calculation and uploading, which can be formulated as The second subperiod is to download global gradient and update local DNN model, and thus can be formulated as It needs to be emphasized that the value of B in subproblem P 3 should match that in subproblem P 2 . Therefore, the global batchsize can be regarded as a global variable which will be optimized at last. In view of this, we will analyze the two subproblems in the sequel.

B. Solution to Subproblem P 2
We can find that subproblem P 2 is generally a min-max optimization problem and is hard to be solved directly. To make it better tractable, we first define E U as the maximum reciprocal of each uplink learning efficiency among user devices, i.e., . Then, by parametric algorithm [31], subproblem P 2 can be transformed into (18b), (18d), (18e), and (18f).
It can be easily verified that constraint (22b) is non-convex, resulting in a non-convex optimization problem. Recall that the values of B in subproblems P 2 and P 3 are identical. Therefore, we first keep B fixed and then determine the joint optimal batchsize selection and uplink communication resource allocation policy. When B is fixed, the problem P 4 becomes a convex one, as presented in the following lemma.
Lemma 1: Given the value of B, problem P 4 can be converted into a classical convex optimization problem.
Proof: The proof is straightforward since when the value of B is fixed, the objective function (22a) is convex and all constraints get affine. The detailed derivation is omitted for brevity.
Lemma 1 is essential for solving problem P 4 by applying the fractional optimization method.
Moreover, classical convex optimization algorithms can be also utilized. To better characterize the structure of the solution and gain more insightful results, we first define some significant auxiliary indicators for each device, as • Local training speed is defined as the speed of performing local forward-backward propagation algorithm at each device, i.e., V k = f C k C L . • Training priority ratio is defined as the ratio between the local computation capacity and the overall devices' computation capacity, i.e., Based on the above definitions, the optimal solution to problem P 4 with fixed B can be described as follows.
Theorem 1: The joint optimal batchsize selection and uplink communication resource alloca-tion policy is given by where µ * and E U * are the optimal values satisfying the active time-sharing constraint K k=1 τ U * k = T Now we start to determine the optimal values of the above two parameters, i.e., E U * and µ * .
Classical method is to perform the two-dimensional search algorithm. To facilitate the search process and reduce the computational complexity, we will calculate some useful bounds for these two parameters in the following. On the one hand, by investigating a special case where each device trains with the same batchsize as well as being allocated with identical time-slot resource, we can obtain the upper bound of E U * . On the other hand, we relax the constraint (18e) and further apply the Karush-Kuhn-Tucker (KKT) conditions to achieve the lower bound of E U * .
With mathematical analysis, the range of E U * could be expressed in the following corollary, which is proved in Appendix B.
Corollary 1: The value of E U * shall satisfy Based on Corollary 1, we further investigate another two extreme cases to determine the range of µ * . The first one corresponds to the scenario where the optimal batchsize for all devices are B * k = 1, ∀k. The second one corresponds to the scenario of B * k = B max , ∀k. Then the range of µ * can be expressed as the function of E U * , which is presented in the following corollary and is also proved in Appendix B.

Corollary 2:
When there exists at least one device whose optimal batchsize is in the interval (1, B max ), the value of µ * should satisfy Remark 4: From Corollary 2, we can observe that the values of µ * and E U * are tightly coupled.
Note that even though this result is derived under the assumption that there is at least one device's batchsize is between 1 and B max , it is still applicable since the extreme cases of B k = 1, ∀k and B k = B max , ∀k rarely occur in practice. On the other hand, these two extreme cases correspond to the cases of B = K and B = KB max , whose solutions can be directly obtained via the KKT conditions.
Based on the above analysis, we now develop an effective two-dimensional search algorithm to solve subproblem P 2 , as described in Table I  τ U * k,h based on Theorem 1, involving the one-dimensional search for µ * ℓ and µ * h , respectively. 10: 12: end if 13: Update τ U * k,ℓ and τ U * k,h . 14: end if 15: end while

C. Solution to Subproblem P 3 and Global Discussion
In this part, we will first solve subproblem P 3 and then discuss the global solution to the original problem P 1 . Similar to the subproblem P 2 , we denote as the maximum reciprocal of each downlink learning efficiency among all devices. Then, the subproblem P 3 can be reformulated as (18c) and (18f).
Given the value of B, the mathematical characteristic of problem P 5 is similar to that of problem P 4 . Therefore, it can be solved using the KKT conditions. The closed-form solution to P 5 is presented in the following theorem. Note that the proof is similar to that of Theorem 1, which is omitted here due to page limits.

Theorem 2:
The optimal downlink communication resource allocation policy is given by where E D * is the optimal value associated with the time-sharing constraint K k=1 τ D * k = T D f . Remark 5: (Consistent Resource Allocation) Theorem 2 indicates that the optimal downlink resource decreases with the downlink data rate. The reason is similar to that in Theorem 1. Note that by this means, the local model updating of each device can be accomplished simultaneously.
Combined it with the results in Theorem 1, we can conclude that the overall end-to-end latency of each device should be identical, leading to a synchronous training system.
As yet, we have presented the closed-form expressions of joint optimal batchsize selection and uplink/downlink time-slot resource allocation as the function of the global batchsize B. As a result, problem P 1 can be degraded into an univariate optimization problem and thus can be solved by classical gradient descent algorithm effectively.

V. EXTENSION TO GPU SCENARIO
In this section, we consider the scenario where each device is equipped with GPU for DNN training. We will first propose a novel GPU training function and then extend the training acceleration problem in this case. Particularly, the optimal solution is proved to have a similar structure as that in the CPU scenario.

A. GPU Training Function
Unlike the serial mode of general CPUs, GPUs perform computation in the parallel mode.
In this situation, the local gradient calculation latency is no longer proportional to the training batchsize. Specifically, when the training batchsize is small, GPU can directly process all data simultaneously, leading to a constant training latency. In contrary, it grows once the training batchsize exceeds the maximum volume of data that the GPU can process at a time. With this consideration, we propose the following function to capture the relation between the local  gradient calculation latency and the training batchsize, as presented in the following assumption and shown in Fig. 2(a).

Assumption 1:
In the GPU scenario, the relation between the local gradient calculation latency and the training batchsize of each device is given by where t ℓ k , c k , and B th k are three coefficients determined by the specific DNN structure (e.g., the number of layers and the number of neurons) and the concrete GPU configuration (e.g., the video memory size and the number of cores).

Remark 6:
As discussed earlier, when the training batchsize is below a threshold B th k , the local gradient calculation latency keeps fixed because of GPU's parallel execution capability.
In this case, the data samples are inadequate such that the computation resource is not fully exploited. Therefore, we name it as the data bound region. On the other hand, the local gradient calculation latency grows linearly when the training batchsize exceeds the threshold. It is because in this case, the computation resource (e.g., the video memory) cannot support processing all data samples simultaneously. We shall note that the local gradient calculation latency does not increase in a ladder form. The reason is rather intuitive that the operations of data reading and transferring between memory modules and processing modules need additional time, leading to a comprehensive linear trend. Consequently, we name this region as the compute bound region.
To validate the results in Assumption 1, we implement three classic DNN models, i.e., DenseNet, GoogleNet, and PNASNet on a Linux server equipped with three NVIDIA GeForce GTX 1080 Ti GPUs. The experimental results are depicted in Fig. 2(b). It can be observed that the local gradient calculation latency of each model first keeps invariant and then increases almost linearly with the training batchsize. This result shows that the curves obtained via experiments fit the theoretical model in (28) very well, which demonstrates the applicability of the proposed GPU training function.

B. Problem Formulation and Analysis
Similar to the CPU scenario, the learning efficiency in the GPU scenario can be also defined as the ratio between the global loss decay and the end-to-end latency of each training period.
Note that the data size of both local gradient g w k and global gradient g w in the GPU scenario are identical to those in the CPU scenario. Thus, the local gradient upload latency and global gradient download latency can be still expressed as (12) and (13) Based on the above analysis, the end-to-end latency of each training period in the GPU scenario is given by Consequently, the training acceleration problem can be formulated as The above problem is not easy to solve since the local gradient calculation latency t L,GPU k is non-differential. Traditional method for solving problem P 6 is the sub-gradient algorithm which performs iterative optimization of the three-variable set, {τ U k , τ D k , B k }, via the sub-gradient functions and will result in high computational complexity. To address this issue, we analyze the mathematical characteristic of the learning efficiency in (31a) and derive a necessary condition of the solution to problem P 6 , as summarized in the following lemma.

Lemma 2:
In the GPU scenario, the optimal batchsize B * k for each device shall locate in the compute bound region, i.e., B th k ≤ B * k ≤ B max . Proof: Please refer to Appendix C.
The result in Lemma 2 coincides with the empirical result in practical systems that the computation resource of all devices should be fully exploited to achieve the largest learning efficiency. Accordingly, the data bound region can be neglected and P 6 can be reformulated as With comprehensive comparison, we can observe that the structures of problems P 1 and P 7 are identical except the expressions of local gradient calculation latency. Fortunately, the two kinds of latency are affine with the batchsize, making both problems essentially the same structure.
Therefore, the GPU scenario can be degraded into the CPU scenario and the algorithms to solve problem P 1 are still applicable with a minor modification on the delay expressions. The detailed derivations and results are omitted due to page limits.

A. Experiment Settings
In this section, we conduct experiments to validate our theoretical analysis and evaluate the performance of the proposed algorithms. The system setup is summarized as follows unless To test the system performance, we choose three commonly-used DNN models: DenseNet121, ResNet18, and MobileNetV2 for image classification. The well-known dataset CIFAR-10 is used for model training, which consists of 50000 training images and 10000 validation images of 32 × 32 pixels in 10 classes. Standard data augmentation and preprocessing methods are employed to improve the test accuracy, and effective deep gradient compression methods are also used to reduce the communication overhead [23]. Moreover, to simulate the distributed mobile data, we study two typical ways of partitioning CIFAR-10 data over devices [27]: 1) IID case, where all data samples are first shuffled and then partitioned into K equal parts, and each device is assigned with one particular part; 2) non-IID case, where all data samples are first sorted by digit label and then divided into 2K shards of size 25000/K, and each device is thereafter assigned with two shards. Note that the latter is a pathological non-IID partition way since most devices only obtain two kinds of digits.

B. CPU Scenario: Generalization with Different DNN Models
An important test of the proposed scheme is whether it is applicable for training different DNN models, i.e., the generalization ability. Toward this end, we implement the above three DNN models in an FEEL system with K = 12 user devices. Specifically, the CPU frequencies of all devices are configured as: 4 devices with 0.7 GHz, 4 devices with 1.4 GHz, and 4 devices with 2.1 GHz.
We test both the loss convergence speed and learning accuracy improvement of each DNN model with different learning rates. To be more realistic, we implement the non-IID case and the results are presented in Fig. 3. It can be observed that our proposed scheme is capable of attaining a satisfactory learning accuracy with a fast loss convergence speed for all three models. Moreover, the ultimate learning accuracy can be well guaranteed with different learning rates. This result demonstrates the strong generalization ability of the proposed algorithm, which promotes its wide implementation in practical systems.

C. CPU Scenario: Performance Comparison among Different Schemes
In this part, we test the performance improvement of our proposed scheme as compared with three benchmark schemes in the scenarios of K = 6 and K = 12 devices, respectively. Without loss of generality, we take a pre-trained DenseNet121 with 86% initial learning accuracy for the following test. Both the IID and non-IID cases are implemented. The detailed procedures of each scheme can be summarized as follows.
• Individual Learning: Each device trains its DNN model until the local loss function converges. Then the edge server aggregates all local models, averages the parameters, and transmits the results to each device. • Gradient-Based FL: Each device trains its DNN model by running one-step SGD algorithm.
Then the gradients of each device are transmitted to the edge server for aggregation. After that, the global gradients are transmitted back to each device. This process is periodically performed before the global loss function converges [32].
It is clearly that the main difference between our proposed scheme and the gradient-based FL scheme is that we take into account the joint batchsize selection and communication resource allocation.
We use two metrics to evaluate the training performance of each scheme, i.e., the test accuracy and the training speedup, which is defined as the ratio between the training speed of each scheme and that of the individual learning scheme.    We further test the training performance of each scheme in the scenario of K = 12 devices. The results are presented in Table II(b). It can be observed that our proposed scheme can still achieve the fastest training speed as well as attain a satisfactory learning accuracy improvement among all schemes, which demonstrates the superiority and scalability of our proposal. Moreover, as the number of devices increases, both the learning accuracy improvement and the training speed improvement of the proposed scheme become more evident as compared with the individual learning scheme. It is because with more devices, more computation resources can be exploited to fully train the DNN model in our scheme, resulting in a higher learning accuracy. In particular, the accuracy gap between IID case and non-IID case in the individual learning scheme is larger than those in other schemes. As we can imagine, the individual learning scheme cannot properly grasp the characteristic of the non-IID data because it performs local training without any collaboration. Conversely, other three schemes dynamically share the local learning updates so that their accuracy gaps between IID case and non-IID case are much smaller. This result also suggests the superiority of the proposed scheme to deal with the non-IID data in distributed FL systems.

D. GPU Scenario: Performance Comparison among Different Schemes
An important test is whether the proposed joint batchsize selection and communication resource allocation policy can accelerate the training task while guaranteeing the learning accuracy in the GPU scenario. Therefore, we turn to compare the training performance of the proposed  scheme with three baseline schemes in the scenario of K = 6 devices. Similarly, the DenseNet121 is tested and both IID and non-IID cases are experimented. The three baseline schemes are summarized as follows.
• Online learning scheme, where the training batchsize of each device is B k = 1, ∀k.
• Full batchsize scheme, where the training batchsize of each device is B k = B max = 128, ∀k.
• Random batchsize scheme, where each device randomly selects a training batchsize between 1 and 128 in each training period. Therefore, the learning accuracy in the non-IID case will not deteriorate as compared with that in the IID case. This also suggests the applicability of the proposed scheme in the hyperparameter adjustment for practical systems with non-IID data.

VII. CONCLUSION
This paper aims at accelerating the DNN training task in the framework of FEEL, which not only protects users' privacy but also improves the system learning efficiency. The key idea is to jointly optimize the local training batchsize and wireless resource allocation to achieve a fast training performance while maintaining the learning accuracy. In the common CPU scenario, According to Lemma 1, problem P 4 is a classical convex optimization problem for a given value of B. Therefore, it can be solved by the Lagrange multiplier method. The partial Lagrange function can be defined as where λ k , ∀k, µ, and γ are the Lagrange multipliers associated with constraints (22b), (18b), and (18d), respectively. Denote B * k , τ U * k as the optimal solution to P 4 . Note that the uplink communication resource τ U k is non-negative while the batchsize of each device is bounded in the interval [1, B max ]. Therefore, applying the KKT conditions gives the following necessary and sufficient conditions, as With simple mathematical calculation, we can derive the optimal batchsize selection policy as Moreover, the minimum E U is achieved when "≤" in (38) is set to "=". Combining (38) and (42), we can obtain the optimal time-slot allocation in Theorem 1.

A. Proof of Corollary 1
To prove Corollary 1, we first analyze the following two cases.

1) Case A (Equivalent resource allocation)
In this case, the time-slot resource allocated to each device is identical and each device selects the same training batchsize for local gradient calculation, i.e., τ U k = T U f K and B k = B K , ∀k. As a result, the corresponding objective value in (22a) can be derived as Since the goal of problem P 4 is to minimize E U , the optimal E U * is no greater than E U h , which can be regarded as an upper bound of E U * .

2) Case B (Infinite memory resource)
In this case, the memory of each device is sufficient so that the batchsize limitation (18e) can be relaxed. Further, the convexity of problem P 4 can be preserved, making the KKT conditions still effective. With the similar derivations in Appendix A, we can obtain the objective value as Due to the fact that the objective value will not increase after constraint relaxation, E U * is no less than E U ℓ . Thus, E U ℓ can be viewed as a lower bound of E U * . Combining (43) and (44), we can express the range of E U * in Corollary 1, which ends the proof.

B. Proof of Corollary 2
According to Theorem 1, we can observe that the optimal batchsize has a threshold-based structure. Similar to the proof of Corollary 1, we also consider two cases.

1) Case A (Online learning)
In this case, we assume that the optimal batchsize of each device is B * k = 1, ∀k. According to (23), this case happens when ∆LE U * −

2) Case B (Full batch learning)
Similar to case A, this case demands that the optimal batchsize of each device satisfies B * k = B max , ∀k. Therefore, this case occurs when Based on the above analysis, when there exists at least one device whose batchsize is between 1 and B max , the value of µ * will satisfy µ ℓ ≤ µ * ≤ µ h , which completes the proof.
APPENDIX C PROOF OF LEMMA 2 The proof of Lemma 2 is straightforward by the reduction to absurdity. It can be observed that the global loss decay ∆L is an increasing function with each training batchsize B k , ∀k.
However, the local gradient calculation latency t L,GPU k keeps unchanged when 1 ≤ B k ≤ B th k . Therefore, in the data bound region, the global loss decay (numerator of (31a)) increases with B k while the end-to-end latency (denominator of (31a)) remains unchanged, resulting in an increasing learning efficiency. Since the objective of problem P 6 is to maximize the learning efficiency, the optimal batchsize will not locate in the data bound region. This ends the proof.