{'fraction_non_alphanumeric': 0.039412989742891064, 'fraction_numerical': 0.014577940403666868, 'mean_word_length': 4.479948805460751, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Multi-Job Intelligent Scheduling with Cross-Device Federated Learning

Recent years have witnessed a large amount of decentralized data in various (edge) devices of end-users, while the decentralized data aggregation remains complicated for machine learning jobs because of regulations and laws. As a practical approach to handling decentralized data, Federated Learning (FL) enables collaborative global machine learning model training without sharing sensitive raw data. The servers schedule devices to jobs within the training process of FL. In contrast, device scheduling with multiple jobs in FL remains a critical and open problem. In this paper, we propose a novel multi-job FL framework, which enables the training process of multiple jobs in parallel. The multi-job FL framework is composed of a system model and a scheduling method. The system model enables a parallel training process of multiple jobs, with a cost model based on the data fairness and the training time of diverse devices during the parallel training process. We propose a novel intelligent scheduling approach based on multiple scheduling methods, including an original reinforcement learning-based scheduling method and an original Bayesian optimization-based scheduling method, which corresponds to a small cost while scheduling devices to multiple jobs. We conduct extensive experimentation with diverse jobs and datasets. The experimental results reveal that our proposed approaches significantly outperform baseline approaches in terms of training time (up to 12.73 times faster) and accuracy (up to 46.4% higher).


INTRODUCTION
In recent years, we have witnessed a large amount of decentralized data over various Internet of Things (IoT) devices, mobile devices, etc. [1], which can be exploited to train machine learning models of high accuracy for diverse artificial intelligence applications. Since the data contain sensitive information of end-users, a few stringent legal restrictions [2], [3], [4], [5] have been put in place to protect data security and privacy. In this case, it is difficult or even impossible to aggregate the decentralized data into a single server or a data center to train machine learning models. To enable collaborative training with decentralized data, Federated Learning (FL) [6], which does not transfer raw data, have emerged as a practical approach.
FL was first introduced to collaboratively train a global model with non-Independent and Identically Distributed (non-IID) data distributed across mobile devices [6]. During the training process of FL, the raw data remains decentralized without being transferred to a single server or a single data center [7], [8]. FL only allows the intermediate data to be transferred from the distributed devices, which can be the weights or the gradients of a model. FL generally utilizes a parameter server architecture [9], [10], [11], where a server (or a group of servers) coordinates the training process with numerous devices. To collaboratively train a global model, the server selects (schedules) several devices to perform local model updates based on their local data, and then it aggregates the local models to obtain a new global model. This process is repeated multiple times to generate a global other eligible devices should also participate in the training process to increase the fairness of data to improve the accuracy of the final global models. The fairness of data refers to the fair participation of the data in the training process of FL, which can be indicated by the standard deviation of the times to be scheduled to a job [23], [24].
While the scheduling problem of devices is typical NPhard [25], [26], some solutions have already been proposed for the training process of FL [16], [27], [28], [29] or distributed systems [30], which generally only focus on a single job with FL. In addition, these methods either cannot address the heterogeneity of devices [27], or do not consider the data fairness during the training process [16], [28], [29], which may lead to low accuracy.
In this paper, we propose a Multi-Job Federated Learning (MJ-FL) framework to enable the efficient training of multiple jobs with heterogeneous edge devices. The MJ-FL framework consists of a system model and a novel intelligent scheduling approach. The system model enables the parallel training process of multiple jobs. With the consideration of both the efficiency of the training process, i.e., the time to execute an iteration, and the data fairness of each job for the accuracy of final models, we propose a cost model based on the training time and the data fairness within the system model. We propose an intelligent scheduling approach based on multiple scheduling methods, including two original scheduling methods, i.e., reinforcement learning-based and Bayesian optimization-based, to schedule the devices for each job. To the best of our knowledge, we are among the first to study FL with multiple jobs. This paper is an extension of a conference version [31], with an extra meta-scheduling approach, additional theoretical proof, and extensive experimental results. We summarize our contributions as follows: • We propose MJ-FL, a multi-job FL framework composed of a parallel training process for multiple jobs and a cost model for scheduling methods. We propose combining the capability and data fairness in the cost model to improve the efficiency of the training process and the accuracy of the global model. • We propose two scheduling methods, i.e., Reinforcement Learning (RL)-based and Bayesian Optimization (BO)-based methods, to schedule the devices to diverse jobs (more details including the method to estimate the loss in Section 3.3 are added compared with [31]). Each method has advantages in a specific situation. The BO-based method performs better for simple jobs, while the RL-based method is more suitable for complex jobs. In addition, we provide theoretical convergence analysis in Section 5. • We propose a novel intelligent scheduling approach based on multiple scheduling methods (extra contribution compared with [31]). The novel intelligent scheduling approach is a meta-scheduling approach that coordinates multiple scheduling methods to achieve excellent performance with an adapted dynamic cost model. • We carry out extensive experimentation to validate the proposed approach. We exploit multiple jobs, composed of Resnet18, CNN, AlexNet, VGG, and LeNet, to demonstrate the advantages of our proposed approach using both IID and non-IID datasets (with extra extensive experimental results for the meta-scheduling approach).
The rest of the paper is organized as follows. We present the related work in Section 2. Then, we explain the system model and formulate the problem with a cost model in Section 3. We present the scheduling methods in Section 4. We provide theoretical convergence analysis in Section 5. The experimental results with diverse models and datasets are given in Section 6. Finally, Section 7 concludes the paper.

RELATED WORK
In order to protect the security and privacy of decentralized raw data, FL emerges as a promising approach, which enables training a global model with decentralized data [1], [6], [8], [15]. Based on the data distribution, FL can be classified into three types, i.e., horizontal, vertical, and hybrid [1], [8]. The horizontal FL addresses the decentralized data of the same features, while the identifications are different. The vertical FL handles the decentralized data of the same identifications with different features. The hybrid FL deals with the data of different identifications and different features. In addition, FL includes two variants: cross-device FL and cross-silo FL [7]. The cross-device FL trains global machine learning models with a huge number of mobile or IoT devices, while the cross-silo FL handles the collaborative training process with the decentralized data from multiple organizations or geo-distributed datacenters. In this paper, we focus on the horizontal and cross-device FL.
Current FL approaches [32], [33], [34], [35], [36], [37] generally deal with a single job, i.e., with a single global model. While some FL approaches have been proposed to handle multiple tasks [13], [38], the tasks share some common parts of a global model and deal with the same types of data. In addition, the devices are randomly selected (scheduled) in these approaches.
A few scheduling approaches [16], [16], [27], [28], [28], [29], [29], [30], [39] exist for single-job scheduling while the device scheduling with multi-job FL is rarely addressed. The scheduling methods in the above works are mainly based on some heuristics. For instance, the greedy method [40] and the random scheduling method [27] are proposed for FL, while genetic algorithms [30] are exploited for distributed systems. However, these methods do not consider the fairness of data, which may lead to low accuracy for multi-job FL. The black-box optimization-based methods, e.g., RL [39], BO [41], and deep neural network [42], have been proposed to improve the efficiency, i.e., the reduction of execution time, in distributed systems. They do not consider data fairness either, which may lead to low accuracy for multijob FL. Although ensemble learning or ensemble method consisting of multiple models [43], has been exploited for scheduling parallel tasks [44], proper cost models and ensemble mechanism should be well designed.
Different from all existing works, we propose a system model for the multi-job FL with the consideration of both efficiency and accuracy. In addition, we propose a novel intelligent scheduling approach based on multiple scheduling methods. To improve the efficiency of the training process, The sampled dataset for Job m at local iteration h Round r on Device k we propose two original scheduling methods, i.e., RL and BO, for multi-job FL, which are suitable for diverse models and for both IID and non-IID datasets.

SYSTEM MODEL AND PROBLEM FORMULATION
In this section, we first explain the motivation for multijob FL. Then, we propose our multi-job FL framework , consisting of a multi-job FL process and a cost model. Afterward, we formally define the problem to address in this paper. Please see the meanings of the major notations in Table 1.

Motivation for Multi-Job Federated Learning
Let us assume a scenario where multiple FL jobs are processed simultaneously, e.g., image classification, speech recognition, and text generation. These jobs can be trained in parallel to exploit the available devices efficiently. However, while each device can only update the model of one job at a given time slot, it is critical to schedule devices to different jobs during the training process. As the devices are generally heterogeneous, some may possess high computation or communication capability while others may not. In addition, the data fairness of multiple devices may also impact the convergence speed of the training process. For instance, if only specific powerful devices are scheduled for a job, the model can only learn from the data stored on these devices, while the knowledge from the data stored on other devices may be missed. In order to accelerate the training process of multiple jobs with high accuracy, it is critical to consider how to schedule devices while considering both the computing and communication capability and the data fairness.
A straightforward approach is to train each job separately using the mechanism explained in [27], while exploiting the existing scheduling of single-job FL, e.g., FedAvg [27]. In this way, simple parallelism is considered while the devices are not fully utilized and the system is of low efficiency. In addition, a direct adaptation of existing scheduling methods to multi-job FL cannot address the efficiency and the accuracy at the same time. Thus, it is critical to propose a reasonable and effective approach for the multi-job FL.

Multi-job Federated Learning Framework
In this paper, we focus on an FL environment composed of a server module and multiple devices. The server module (Server) may consist of a single parameter server or a group of parameter servers [45]. In this section, we present a multijob FL framework, which is composed of a process for the multi-job execution and a cost model to estimate the cost of the execution.

Multi-job FL Process
Within the multi-job FL process, we assume that K devices, denoted by the set K, collaboratively train machine learning models for M jobs, denoted by the set M. Each Device k is assumed to have M local datasets corresponding to the M jobs without loss of generality, and the dataset of the m-th job on Device k is expressed as The global learning problem of multi-job FL can be expressed by the following formulation: where L m is the loss value of Job m, is the loss value of Job m at Device k, W :≡ {w 1 , w 2 , ..., w M } is the set of weight vectors for all jobs, and f m (w m ; x m k,d , y m k,d ) captures the error of the model parameter w m on the data pair {x m k,d , y m k,d }. In order to solve the problem defined in Formula 1, the Server needs to continuously schedule devices for different jobs to iteratively update the global models until the training processes of the corresponding job converge or achieve the target performance requirement (in terms of accuracy or loss value). We design a multi-job FL process as shown in Figure  1. The Server first initializes a global model for each job. The initialization can be implemented randomly or from the pre-training process with public data. To know the current status of devices, the Server sends requests to available devices in Step 1 . Then, in Step 2 , the Server schedules devices for the current job based on the scheduling plan generated by the scheduling method (see details in Section 4). The scheduling plan is a set of devices selected to execute the local training process of the current job. Note that the scheduling process generates a scheduling plan for each job during the training process of multiple jobs, i.e., with an online strategy, while the scheduling processes for multiple jobs are carried out in parallel. The Server distributes the latest global model for the current job to the scheduled devices in Step 3 , and then the model is updated in each device based on the local data in Step 4 . Afterward, each device sends the updated model to the Server after its local training in Step 5 . Finally, the Server aggregates the models of scheduled devices to generate a new global model in Step 6 . The combination of Steps 1 -6 is denoted by a round, which is repeated for each job until the corresponding global model reaches the expected performance (accuracy, loss value, or convergence). Please note that multiple jobs are executed in parallel asynchronously, while a device can only be scheduled to one job at a given time. In addition, we assume that each job is of equal importance.
As an FL environment may contain GPUs or other highperformance chips, it is beneficial to train multiple jobs simultaneously to reduce training time while achieving target accuracy. Within each round, Step 6 exploits FedAvg [27] to aggregate multiple models within each job, which can ensure the optimal convergence [46], [47].Within our framework, the sensitive raw data is kept within each device, while only the models are allowed to be transferred. Other methods, e.g., homomorphic encryption [48] and differential privacy [49], can be exploited to protect the privacy of sensitive data.

Cost Model
In order to measure the performance of each round, we exploit a cost model defined in Formula 2, which is composed of time cost and data fairness cost. The data fairness has a significant impact on convergence speed.
where α and β are the weights of time cost and fairness cost respectively, T r m (·) represents the execution time of the training process in Round r with the set of scheduled devices V r m , and F r m (·) is the corresponding data fairness cost. We choose the linear combination because of its convenience and excellent performance. In practice, we empirically set α and β based on the information from previous execution and adjust them using small epochs. We increase α for fast convergence and increase β mainly for high accuracy.
As defined in Formula 3, the execution time of a round depends on the slowest device in the set of scheduled devices. T where t k m is the execution time of Round r in Device k for Job m. t k m is composed of the communication time and the computation time, which is complicated to estimate and differs for different devices. In this study, we assume that the execution time of each device follows the shift exponential distribution as defined in Formula 4 [50], [51]: where the parameters a k > 0 and µ k > 0 are the maximum and fluctuation of the computation and communication capability, which is combined into one quantity, of Device k, respectively. Moreover, we assume that the calculation time of model aggregation has little impact on the training process because of the strong computation capability of the Server and the low complexity of the model.
The data fairness of Round r corresponding to Job m is indicated by the deviation of the frequency of each device to be scheduled to Job m defined in Formula 5.
where s r k,m is the frequency of Device k to be scheduled to Job m, and K and |K| are the set of all devices and the size, respectively. s r k,m is calculated by counting the total number of the appearance of Device k to be scheduled to Job m in the set of scheduling plans for Job m, i.e., {V 1 m , ..., V r m }. In particular, S r m = {s r 1,m , ..., s r |K|,m } represents the frequency vector of Job m at Round r. At the beginning, i.e., Round 0, each s 0 k,m ∈ S 0 m is 0. s r k,m represents the frequency of Device k scheduled to Job m at Round r. Then, we can calculate s r+1 k,m using the following formula: Please note that the "data fairness" is reflected by the deviation of the frequency of each device scheduled to a job [52], which is different from the "fairness" (the bias of the machine learning models concerning certain features) in machine learning [53]. Formula 5 is inspired by [52], and we are among the first to extend this idea from distributed or network systems to FL. When the devices are non-uniformly sampled with low data fairness, the convergence is slowed down [46], [47]. In addition, data fairness is important due to the underlying data heterogeneity across the devices. Data fairness can help arbitrarily select devices without harming the learning performance.

Problem Formulation
The problem we address is how to reduce the training time when given a loss value for each job. While the execution of each job is carried out in parallel, the problem can be formulated as follows: where l m is the given loss value of Job m, R m represents the minimum number of rounds to achieve the given loss in the real execution, and L m (R m ) is the loss value of the trained model at Round R m , defined in Formula 1.
We assume Stochastic Gradient Descent (SGD) is utilized to train models, which converges at a rate of O(r) with r representing the number of rounds [54]. Inspired by [46], we exploit Formula 8 to roughly estimate the loss value of the global model for Job m at Round r.
where γ 0 m , γ 1 m and γ 2 m represent non-negative coefficients of the convergence curve of Job m. γ 0 m , γ 1 m and γ 2 m can be calculated based on previous execution. In addition, we assume that the real number of rounds corresponding to the same loss value has 30% error compared with r (from the observation of multiple executions). Given a loss value of a model, we exploit this loss estimation method to calculate the maximum rounds for each job. Given a loss value of a model, we utilize this loss estimation method to calculate the number of rounds as R c m and take (1 + 0.3) * R c m as R m defined in Table 1. Please note that this estimation is different from the loss value during the real execution; i.e., R m can be different from R m .
As it requires the global information of the whole training process, which is hard to predict, to solve the problem, we transform the problem to the following one, which can be solved with limited local information of each round. In addition, in order to achieve the given loss value of Job m within a short time (the first constraint in Formula 7), we need to consider the data fairness within the total cost in Formula 9, within which the data fairness can help reduce R m to minimize the total training time.
where Cost r m (V r m ) can be calculated based on Formula 2 with a set of scheduled devices V r m to be generated using a scheduling method for Job m. Since the scheduling results of one job may potentially influence the scheduling of other jobs, we consider the cost of other jobs when scheduling devices to the current job in this problem. As the search space is O(2 |K| ), this scheduling problem is a combinatorial optimization problem [55] and NP-hard [25].

DEVICE SCHEDULING FOR MULTI-JOB FL
In this section, we propose two original scheduling methods, i.e., BO-based and RL-based, and a novel intelligent scheduling approach, i.e., meta-greedy, to address the problem defined in Formula 9. The scheduling plan generated by a scheduling method is defined in Formula 10: where V r m is a scheduling plan, K\V r o represents the set of available devices to schedule, T otalCost(V r m ) is defined in Formula 9, and K and V r o are the set of all devices and the set of occupied devices in Round r, respectively.
The BO-based and RL-based methods are designed for different model complexities, and we choose the better one based on known profiling information with small tests (a few epochs) to avoid possible limitations. RLDS favors complex jobs, as it can learn the influence among diverse devices. The influence refers to the concurrent, complementary, and latent impacts of the data in multiple devices for diverse jobs. However, BODS favors simple jobs, while it relies on simple statistical knowledge. The complexity of jobs is determined by the number of parameters of models and the size of the training dataset. We consider the probability to release the devices in V o in BODS and RLDS, and possible concurrent occupation of other devices for other jobs, which is not explained in the paper to simplify the explanation. During the execution, we assume that a fraction of the devices is sampled for each job and some devices can be unavailable for the execution. In order to optimize the scheduling process for diverse types of models, we further propose a meta-greedy scheduling approach, which takes advantage of multiple scheduling methods and chooses the most appropriate scheduling plan from the results of the scheduling methods.

Bayesian Optimization-Based Scheduling
As the Gaussian Process (GP) [56] can well represent linear and non-linear functions, BO-based methods [57] can exploit a GP to find a near-optimal solution for the problem defined in Formula 10. In this section, we propose a Bayesian Optimization-based Device Scheduling method (BODS).
We adjust a GP to fit the cost function T otalCost(·). The GP is composed of a mean function µ defined in Formula 11 and a covariance function K defined in Formula 12 with a M atern kernel [58].
The BODS is explained in Algorithm 1. First, we generate a random set of observation points and calculate the cost according to the Formula 2 (Line 1). Each observation point is a pair of scheduling plan and cost for the estimation of mean function and the covariance function. Then, in each round, we randomly sample a set of scheduling plans (Line 3), within which we use updated µ and K based on Π L+r−1 (Line 4) to select the one with the largest reward. Afterward, we perform the FL training for Job m with the generated scheduling plan (Line 5). In the meanwhile, we calculate the cost corresponding to the actual execution (Line 6) according to Formula 9 and update the observation point set (Line 7).
Let (V r l , C l ) denote an observation point l for Job m in Round r, where V r l = {V r l,1 , ..., V r l,M } and C l is the cost value of T otalCost(V r l,m ) while the scheduling plans of other jobs are updated with the ones in use in Round r. At a given time, we have a set of observations We denote the minimum cost value within the L − 1 observations by C + L−1 . Then, we exploit Expected Improvement(EI) [59] to select a new scheduling plan V * r m in Round r what improves C + L−1 the most, which is the utility function. Please note that this is not an exhaustive search since we randomly select several observation points (a subset of the whole search space) at the beginning and add new observation points using the EI method. The utility function is defined in Formula 13.
where we receive a reward C + turns out to be less than C + L−1 , and no reward otherwise. Then, we use the following formula, which is also denoted an acquisition function, to calculate the expected reward of a given scheduling plan V.
where Φ is the Cumulative Distribution Function (CDF) of the standard Gaussian distribution. Finally, we can choose the scheduling plan with the largest reward as the next observation point, i.e., V * r L,m .

Reinforcement Learning-Based Scheduling
In order to learn more information about the near-optimal scheduling patterns for complex jobs, we further propose a Reinforcement Learning-based Device Scheduling (RLDS) method as shown in Figure 2. In addition, the method is inspired by [39], [60]. The scheduler of RLDS consists of a policy network and a policy converter. During the process of device scheduling, RLDS collects the status information of jobs as the input of the policy network. Afterwards, the policy network generates a list of probabilities on all devices as the output. Finally, the policy converter converts the list into a scheduling plan.

Policy Network
The policy network is implemented using a Long Short-Term Memory (LSTM) network followed by a fully connected layer, which can learn the device sharing relationship among diverse jobs. We take the computation and communication capability of available devices to be used in Formula 4, and the data fairness of each job defined in Formula 5 as the input. The network calculates the probability of each available device to be scheduled for a job.

Policy Converter
The Policy Converter generates a scheduling plan based on the probability of each available device which is calculated by the policy network with the -greedy strategy [61].

Training
In the training process of RLDS, we define the reward as R m = −1 * T otalCost(V r m ). Inspired by [62], [63], we exploit Formula 15 to update the policy network: Update θ according to Formula 15 where θ and θ represent the updated parameters and the current parameters of the policy network, respectively, η represents the learning rate, N is the number of scheduling plans to update the model in Round r (N > 1 in the pretraining process and N = 1 during the execution of multiple jobs), P represents the probability calculated based on the RL model, S m k = 1 represents that Device k is scheduled to Job m, and b m is the baseline value for reducing the variance of the gradient.
We pre-train the policy network using Algorithm 2. First, we randomly initialize the policy network (Line 1). We use the latest policy network and the -Greedy method to generate N scheduling plans (Line 5). The parameters are updated based on the Formula 15 (Line 7), and the baseline value b m is also updated with the consideration of the historical value (Line 8). Afterward, we choose the best scheduling plan that corresponds to the minimum total cost, i.e., the maximum reward (Line 9). Finally, we update the frequency matrix S m and the set of occupied devices V o , while assuming that the best scheduling plan is used for the multi-job FL (Line 10).
After the pre-training, we exploit RLDS during the training process of multiple jobs within the MJ-FL framework as shown in Algorithm 3. First, we load the pre-trained policy network and initialize the parameters ∆θ, b m (Line 1). When generating a scheduling plan for Job m, the latest policy network is utilized (Line 3). We perform the FL training for Job m with the generated scheduling plan and update the frequency matrix S m and the set of occupied devices V o (Line 4). Afterward, we calculate the reward corresponding to the real execution (Line 5). The parameters are updated based on the Formula 15 (Line 6), while the

Meta-Greedy Scheduling
Multiple jobs of diverse structures and layers exist within the multi-job federated learning environment. Some scheduling methods, e.g., BODS, favor simple jobs, while some other scheduling methods, e.g., RLDS, prefer complex jobs. In addition, heuristic scheduling methods, e.g., Greedy and Genetic, can be exploited to schedule devices, as well. In this case, we take advantage of the existing scheduling methods, and further propose a meta-greedy scheduling approach as shown in Figure 3. In Round r, the Meta-Greedy executes six scheduling methods in parallel, appends the solution generated by each method to the candidate scheduling solutions set Θ r m , and selects a scheduling plan from the set of candidate device scheduling solutions according to Formula 16 as the solution for the r-th round under the current job. The meta-greedy scheduling approach chooses the most appropriate one from the scheduling plans generated by multiple methods, which can be closer to the optimal solution compared with that of a single method.
The Meta-Greedy algorithm is shown in Algorithm 4. First, for each round (Line 2), we exploit diverse scheduling methods, e.g., BODS, RLDS, Random [27], FedCS [28], Genetic [30], and Greedy [40], to generate scheduling plan candidates (Line 3). As each scheduling method may have superior performance in a specific environment (Random corresponds to high final accuracy; Genetic corresponds to high accuracy at the beginning of the training process for the jobs of moderate complexity; Greedy corresponds to high accuracy at the beginning of the training process of simple jobs; FedCS corresponds to high accuracy at the middle of the the training process; see details in Section 6), we take these 6 methods in Meta-Greedy. Then, we choose a scheduling plan that corresponds to the smallest total cost according to Formula 16 (Line 4). Finally, we utilize the selected scheduling plan for the training process (Line 5).  We propose a dynamic cost model for the selection in Line 4. While Formula 2 can also be exploited for the selection, the influence of the data fairness becomes smaller in the later round of FL as the frequency of the participation has little change with a small increase of one. We reconstruct the cost model using Formula 16 to replace Formula 2. ReCost where β r dynamically changes according to r and is defined in Formula 17.
β r = β * Ω(r), r ≥ 1 (17) where Ω(r) is a function based on Round r. Ω(r) should enhance the impact of data fairness when r becomes significant. We take Ω(r) = √ r in our algorithm because of its excellent performance (see details in Section 6).

CONVERGENCE ANALYSIS
In this section, we present the theoretical convergence proof for our multi-job FL with arbitrary scheduling methods. We first introduce the assumptions and then present the convergence theorem and corollary.  Assumption 4. Bounded local gradient: For each device k ∈ N , the expected squared of stochastic gradient is bounded: Assumption 1 has been made in [46], [64], while Assumptions 2, 3, 4, have been exploited in [65]. When Assumptions 1 -4 hold, we get the following theorem.
Theorem 5.1. Suppose that Assumptions 1 to 4 hold, and consider that F m k is a non-convex function. When the learning rate satisfies 0 < η m ≤ 1 L , then for all R ≥ 1 we have: where F m * is the local optimal value, R refers to the number of rounds for Job m during the execution, H represents the number of local iterations, and Q is the upper bound ratio between the learning rate at local iteration 0 and h , i.e., η m r,0 ≤ Qη m r,h .
Proof. The proof can be found in Appendix.
Then, we can get the following corollary:  The convergence accuracy and the time required to achieve the target accuracy for different methods in Group A. The numbers in parentheses represent the target accuracy, and "/" represents that the target accuracy is not achieved.

Convergence Accuracy Time (min) Random Genetic FedCS Greedy BODS RLDS Meta-Greedy Random Genetic FedCS Greedy BODS RLDS Meta-Greedy
We can find that, the training process of multi-job FL converges to a stationary point of f (w * ) with a convergence rate of O( 1 √ RH ) for each job.

EXPERIMENTS
In this section, we present the experimental results to show the efficiency of our proposed scheduling methods within MJ-FL. We compared the performance of Meta-Greedy, RLDS, and BODS with six baseline methods, i.e., Random [27], FedCS [28], Genetic [30], Greedy [40], Deep Neural Network (DNN), and Simulated Annealing (SA) [66].
CNN-A-IID comprises of two 3 × 3 convolution layers, one with 32 channels and the other with 64 channels. Each layer is followed by one batch normalization layer and 2 × 2 max pooling. Then, there are one flatten layer and three fully-connected layers (1568, 784, and 26 units) after the two convolution layers. In addition, we make a simple modification of CNN-A-IID to CNN-A-non-IID since the convergence behavior of CNN on non-IID in Group A is not satisfiable. CNN-A-non-IID consists of three 3 × 3 convolution layers (32, 64, 64 channels, each of them exploits ReLU activations, and each of the first two convolution layers is followed by 2 × 2 max pooling), followed by one flatten layer and two fully-connected layers (64, 26 units). CNN-B consists of two 2 × 2 convolution layers (64, 32 channels, each of them exploits ReLU activations) followed by a flatten layer and a fully-connected layer, and each convolution layer is followed by a dropout layer with 0.05. In addition, the other parameters are shown in Tables 2 and  3. DNN comprises of a flatten layer and 40 hidden layers before an Alpha Dropout layer and a fully-connected layer. The hidden layers consist of 20 units of a fully-connected layer and a batch normalization layer.
For the non-IID setting of each dataset, the training set is classified by category, and the samples of each category 50   are divided into 20 parts. Each device randomly selects two categories and then selects one part from each category to produce its local training set. For the IID setting, each device randomly samples a specified number of images from each training set. In addition, we use 12 Tesla V100 GPUs to simulate an FL environment composed of a parameter server and 100 devices. We exploit the execution time, including the training time and communication time, measured in real edge devices as the parameters in Formula 4 to simulate the real execution. We use Formula 4 to simulate the capabilities of devices in terms of training time with the uniform sampling strategy, while the accuracy is the results from the actual training processes. In the experimentation, we use corresponding target accuracy (for ease of comparison) in the place of target loss value.
Afterward, we present the ablation experiments to show the impact of execution time and the data fairness in the cost model and the influence of Ω(r).

Comparison with Single-Job FL
In order to demonstrate the effectiveness of our proposed framework, i.e., MJ-FL, over the SJ-FL, we execute each group of jobs sequentially with FedAvg, which is denoted the Random method when adapted to multi-job FL. As shown in Tables 4, 5, and 6, MJ-FL outperforms SJ-FL (up to 1.68 times faster) with Random and the same accuracy. RLDS with MJ-FL outperforms Random with SJ-FL up to 15.38 times faster, and the advantage of BODS can be up to 8.83 times faster. Furthermore, Meta-Greedy can achieve much better performance, i.e., 19 times faster.

Comparison within MJ-FL
In this section, we present the experimental results with the IID setup and the non-IID setup.
Evaluation with the IID setting: As shown in Figures  4 and 5  than other methods. In addition, the convergence speed of RLDS has significant advantages in terms of both complex and simple jobs compared to BODS, while Meta-Greedy outperforms all others in terms of convergence speed. Besides, Meta-Greedy can achieve higher accuracy within less time compared to other methods for both complex jobs (ResNet in Figure 5(a)) and simple jobs (AlexNet in Figure  5(c)). Tables  Evaluation with the non-IID setting: When the decentralized data is of non-IID, the data fairness defined in Formula 5 has a significant impact on the accuracy. As shown in Figures 6 and 7, the convergence speed of our proposed methods, i.e., RLDS, BODS and Meta-Greedy, is significantly faster than other methods. RLDS shows a significant advantage for complex jobs (VGG in Figure 6(a)), while BODS shows advantage for relatively simple jobs in Groups A and B (please see details in Figures 6 and 7). This is reasonable as we have much more parameters to adjust for complex jobs with RLDS, e.g., the learning rate, the decay rate, the structure of the LSTM etc, which can fit into a complex jobs. However, it may be complicated to fine-tune the parameters for a simple job with RLDS. In contrary, the execution of simple jobs can be directly well addressed by the Bayesian optimization. Meta-Greedy can lead to a good performance for both simple and complex jobs. As shown in Tables 4 and 5  46.4% for Meta-Greedy), as well. Given a target accuracy, our proposed methods can achieve the accuracy within a shorter time, compared with baseline methods, in terms of the time for a single job, i.e., the training time of each job (up to 5.04 times shorter for BODS, 5.11 times shorter for RLDS and 7.53 times shorter for Meta-Greedy), and the time for the whole training process, i.e., the total time calculated based on Formula 7 (up to 4.15 times for BODS, 4.67 times for RLDS and 7.16 times for Meta-Greedy), for Groups A and B. In addition, among our proposed methods, Meta-Greedy always has the shortest time to achieve the target accuracy. We have similar observations with IID, while the advantage of Meta-Greedy is much more significant (up to 19.0 times shorter in terms of the time for a single job) than that of non-IID as shown in Tables 4 and 5. Besides, we can find that our proposed method (i.e., Meta-Greedy) leads to a better performance in the case of non-IID data due to dynamically enhancing the impact of data fairness to decrease the imbalance of devices. Figures 5 and 7, the convergence speed corresponding to RLDS, BODS and Meta-Greedy is much higher than baseline methods with different target accuracy. The advantage of RLDS and BODS is up to 8.77 times faster for Target 1 (0.845), 13.96 times faster for Target 2 (0.856), and 27.04 times faster for Target 3 (0.865), compared with the baselines. In addition, Meta-Greedy outperforms the other six methods (four baselines and two scheduling methods, i.e., RLDS and BODS) up to 4.42 times faster for Target 1 (0.845), 6.65 times faster for Target 2 (0.856), and 5.61 times faster for Target 3 (0.865). Furthermore, According to Figure 8, SA [66] corresponds to much worse performance (up to 91.4% slower and 3.5% lower accuracy) compare with our methods. We carry out experiments to compare out methods with DNNs [42], the performance of which is significantly worse (up to 90.5% slower and 26.3% lower accuracy) than our methods. In addition, we test other combinations of the two costs, which correspond to worse performance (up to 37.1% slower and 3.5% lower accuracy for the sum of squared costs, and 64.4% slower and 3.3% lower accuracy for multiplication) compared to the linear one (Formula 2).

Comparison in other cases: As shown in
As RLDS can learn more information through a complex neural network, RLDS outperforms BODS for complex jobs (0.008 and 0.029 in terms of accuracy with VGG19 and ResNet18, and 46.7% and 34.8% faster for the target accuracy of 0.7 with VGG19 and 0.5 with ResNet18; see details in Appendix). Due to the emphasis on the combination of data fairness and device capabilities, i.e.,computation and communication capabilities, BODS can lead to high convergence accuracy and fast convergence speed for simple jobs (0.018 in terms of accuracy and 38% faster for the target accuracy of 0.97 with CNN; see details in Appendix). Meta-Greedy reconstructs the cost model based on six scheduling schemes and dynamically adjusts the parameters so that the impact of data fairness increases with the number of rounds, which leads to high convergence accuracy and fast convergence speed in both complex and simple jobs. BODS, RLDS and Meta-Greedy significantly outperform the baseline methods, while there are also differences among the four methods. The Greedy method prefers devices with high capacity, which leads to a significant decline in terms of the final convergence accuracy. The Genetic method can exploit randomness to achieve data fairness while generating scheduling plans, and the convergence performance is better than the Greedy method. The FedCS method optimizes the scheduling plan by randomly selecting devices, which improves the fairness of the device to a certain extent, and convergences faster than the Random method. We carry out  an experiment with Group A with both IID and non-IID distribution, and find that Meta-Greedy with 6 methods significantly outperforms that with 2 methods in terms of accuracy (up to 0.091) and training speed (up to 65%) (see details in Appendix). In addition, after analyzing the log of the training process (see details in Appendix), we find Greedy and Genetic are extensively exploited, RLDS is selected at the beginning of the training process, BODS is chosen at the end of the training process, FedCS participates with less frequency, and Random is seldomly utilized. As Meta-Greedy can intelligently select a proper scheduling plan based on available methods, it results in a more efficient training process.

Ablation Study
In this section, we first present the ablation study to show the impact of the execution time and the data fairness. Then, we analyze the influence of Ω(r). Impact of data fairness: As shown in Figures 10 and  9, we conduct ablation experiments and find an evident decline in convergence accuracy when the cost model is only composed of execution time cost. From Figures 10 and 9, we can see that the accuracy of the cost model composed of execution time (i.e., BODS (Time) and RLDS (Time)) is worse than that of both data fairness and execution time (i.e., BODS and RLDS) in most cases (up to 35.83% lower for RLDS (Time)). The abnormal case, when the convergence accuracy of BODS (Time) is slightly higher (about 1%) than the convergence accuracy of BODS (please see details in Figure 10 (d)) should be caused by randomness. Besides, from the Figures 10 and 9, we can find that the impact of execution time on complex jobs (VGG in Figure 10 and Resnet in Figure 9) is significantly greater than that on simple jobs (LeNet in Figure 10 and AlexNet in Figure 9). Figures 10 and 9, the data fairness improves both the convergence speed (up to 9.35 times faster) and the accuracy (up to 15.3%). From Figures 11 and 12, we can find that the convergence speed significantly decreases (up to 25.46 times slower for RLDS (Variance) compared with RLDS) when given a target accuracy with the cost model composed of only data fairness. In most cases, considering data fairness reduces the convergence speed and essentially does not affect the convergence accuracy. There are few cases that the job fails to achieve the convergence accuracy. In addition, from the results shown in Figures 10 and 9, we find that the convergence accuracy in complex jobs (VGG in Figure 11 and ResNet in Figure  12) are more likely to decline when the cost model is only composed of data fairness, compared with that with simple jobs. Besides, the performance corresponding to the cost model with only data fairness is close to that of the 'Random' method in most setups.

Influence of Ω(r): As shown in Figures of Appendix, Meta-Greedy with Ω(r) =
√ r outperforms other methods, i.e., Ω(r) = r and Ω(r) = log r, in terms of both convergence accuracy and convergence speed. Although the convergence accuracy of Meta-Greedy with Ω(r) = r is slightly higher than that with Ω(r) = √ r in a few experiments, the convergence accuracy of Meta-Greedy with Ω(r) = √ r in complex jobs is significantly lower than that with Ω(r) = r. In addition, Meta-Greedy with Ω(r) = √ r takes less time to reach the target accuracy in previous rounds compared with Meta-Greedy with Ω(r) = r. This indicates that when round r is linearly related to Ω(r), the data fairness in later rounds influences the cost model too much and may lead to a lower convergence accuracy. Therefore, we avoid using Ω(r) = r due to the dramatic changes of the magnitude in the linear relationship. Meta-Greedy with Ω(r) = √ r takes less time to reach the target accuracy in previous rounds compared with Meta-Greedy with Ω(r) = log r. In the meanwhile, the convergence accuracy of Meta-Greedy with Ω(r) = log r is lower than that of Meta-Greedy with Ω(r) = √ r, which implies that the relatively gentle variation of Ω(r) with round r leads to lower convergence accuracy and slower convergence speed. By contrast, Meta-Greedy with Ω(r) = √ r performs best among them in terms of both convergence accuracy and convergence speed. Thus, we adopt Meta-Greedy with Ω(r) = √ r, which dynamically changes the influence of data fairness to obtain relatively optimal solution in both complex and simple jobs.

CONCLUSION
In this work, we proposed a new Multi-Job Federated Learning framework, i.e., MJ-FL. The framework is composed of a system model and three device scheduling methods. The system model is composed of a process for the parallel execution of multiple jobs and a cost model based on the capability of devices and data fairness. We proposed three device scheduling methods, i.e., RLDS for complex jobs and BODS for simple jobs, while Meta-Greedy for both complex and simple jobs, to efficiently schedule proper devices for each job based on the cost model. We carried out extensive experimentation with six real-life models and four datasets with IID and non-IID distribution. The experimental results show that MJ-FL outperforms the single-job FL, and that our proposed scheduling methods, i.e., BODS and RLDS, significantly outperform baseline methods (up to 44.6% in terms of accuracy, 12.6 times faster for a single job and 5.81 times faster for the total time). In addition, Meta-Greedy, the intelligent scheduling approach based on multiple scheduling methods (including the two proposed methods, i.e., RODS and BODS) significantly outperforms other methods (up to 46.4% in terms of accuracy, 12.73 times faster for a single job and 8.16 times faster for the total time).

Proof of Theorem 1
For simplicity, we take ∇f m k (w m,k r,h ) instead of ∇f m k (w m,k r,h ; ζ m,r k,h ) in the proof. By the smoothness of F m , we have where the fourth equality results from the basic identity Then, combine A and B together We take 0 < η m r,h ≤ 1 L . As C in (22) is positive, we have For D we have,

Experimentation with Real Mobile Devices
We carried out an experimentation with 20 real devices (mobile devices) and a parameter server on the Baidu AI Cloud [74]. The devices are summarized in Table 8. We carry out the experimentation with a synthetic CNN model of 4 layers, a VGG model of 6 layers, and a ResNet model of 13 layers. The time to achieve target accuracy is shown in Table 7. From the table, we can find that Meta-Greedy corresponds to the shortest time (up to 42.4% shorter than others) to achieve the target accuracy of simple models, i.e. CNN and VGG, while BODS outperforms baseline methods (up to The time to achieve target accuracy for divers models and methods. The "()" after the model represents the target accuracy. "/" represents that the training cannot achieve the target accuracy with the corresponding scheduling method while the "()" represents the highest accuracy during the training process.  Impact of Ω(r) As shown in Figures 13 and 14, Meta-Greedy with Ω(r) = √ r outperforms other methods, i.e., Ω(r) = r and Ω(r) = log r, in terms of both convergence accuracy and convergence speed.

RLDS & BODS with Simple and Complex Jobs
As shown in Figure 15, RLDS favors complex jobs (VGG and ResNet) while BOSD corresponds to better performance for a simple job (CNN). We exploit VGG19 (21,240,010) [67] and ResNet18 (595,466) [69] to train models with non-IID Cifar10 [71] dataset. We exploit CNN with 491,920 parameters to train a model with the emnist-digital dataset [72].
As RLDS can learn more information through a complex neural network, RLDS outperforms BODS for complex jobs (0.008 and 0.029 in terms of accuracy with VGG19 and ResNet18, and 46.7% and 34.8% faster for the target accuracy of 0.7 with VGG19 and 0.5 with ResNet18). Due to the emphasis on the combination of data fairness and device capabilities, i.e.,computation and communication capabilities, BODS can lead to high convergence accuracy and fast convergence speed for simple jobs (0.018 in terms of accuracy and 38% faster for the target accuracy of 0.97 with CNN; see details in Appendix).

Frequency of Each Method in Meta-Greedy
As shown in Figure 17, Meta-Greedy with 2 methods (BODS and RLDS) significantly outperforms that with 6 methods (BODS, RLDS, Genetic, Greedy, Random, and FedCS). We find that Greedy and Genetic are extensively exploited, RLDS is selected at the beginning of the training process, BODS is chosen at the end of the training process, FedCS participates with less frequency, and Random is seldomly utilized. This result shows that when there are Greedy, Genetic, FedCS, and RLDS, Meta-Greedy can combine them to generate better scheduling plans for a simple job (LeNet with IID). When the job becomes complex, Meta-Greedy combines Greedy, Genetic, FedCS, RLDS, and BODS to generate proper scheduling plans (LeNet with non-IID, CNN with both IID and non-IID). However, when the job becomes even more complex, Meta-Greedy exploits more frequently RLDS and BODS. RLDS is utilized at the beginning of the training process because of its superior performance while BODS is exploited at the end. As BODS may introduce some randomness to the scheduling process, it may correspond to better data fairness and higher accuracy at the end. Please note that does not contradict with the claim "BODS favors simple jobs and RLDS favors complex jobs" as the combination of Greedy and Genetic can well address the simple jobs and the training process is quite different from that of a single scheduling method. As Meta-Greedy can intelligently select a proper scheduling plan based on method, it corresponds to efficiency training process.  (2) and MetaGreedy (6). MetaGreedy (2) represents Meta-Greedy with 2 methods and MetaGreedy (6) represents Meta-Greedy with 6 methods.