Toward Multiple Federated Learning Services Resource Sharing in Mobile Edge Networks

In this subsection, we summarize our recent federated learning algorithm design according to [20] as in the detail of Algorithm 1. Accordingly, in the typical setting of federated learning for a general supervised learning problem, given a sample data $\{x_{i},y_{i}\}\in\cal{D}$ with input $x_{i}\in\mathbb{R}^{d}$, the learning task is required to train the model parameter $w\in\mathbb{R}^{d}$ to predict the correct label $y_{i}$ by minimizing the loss function $f_{i}(w)$. The training data at UEs can be the usage information or sensing data from the integrated sensors. Different from the conventional centralized learning, the dataset of the federated learning scheme is distributed over a set of $N$ UEs where each participating UE $n$ collects training data samples and stores a local dataset $\mathcal{D}_{n}$ such that

The local loss function of the learning problem using the local dataset of UE $n$ is defined as

where $\langle x,x^{\prime}\rangle$ denotes the inner product of vectors $x$ and $x^{\prime}$ and $\left\lVert\cdot\right\rVert$ is Euclidean norm. These strong convexity, smoothness assumptions are also used in [25], and satisfied in popular ML problems such as $l_{2}$-regularized linear regression model with $f_{i}(w)=\frac{1}{2}(\langle{x_{i}},{w}\rangle-y_{i})^{2}+\frac{\beta}{2}\left\lVert w\right\rVert^{2},y_{i}\in\mathbb{R}$, and $l_{2}$-regularized logistic regression with $f_{i}(w)=\log\bigl{(}1+\exp(-y_{i}\langle{x_{i}},{w}\rangle)\bigr{)}+\frac{\beta}{2}\left\lVert w\right\rVert^{2},y_{i}\in\{-1,1\}$. Accordingly, we denote $\rho\mathrel{\mathop{:}}=\frac{L}{\beta}$ as the condition number of $F_{n}(\cdot)$’s Hessian matrix.

Then, the global loss function of the global learning problem is as follows

Accordingly, the global learning model can be obtained by solving the global problem (2) using an iterative update process at the server and UEs in the federated learning scheme. These updates perform alternatively within a number of global rounds (i.e., $K_{g}$) that consists of four following steps at one global round as

• •

  S1. Local Training: Every UE needs to train a local model by using the local training data $\mathcal{D}_{n}$.

• •

  S2. Upload local model: UEs transmit the local learning model and global gradient updates to the server.

• •

  S3. Update global model: The global model is constructed based on the weight parameters of local models at the server.

• •

  S4. Broadcast global model: The updated global model and gradient are broadcast to all UEs.

Local Training at UEs: According to [20], instead of solving the local objective in the equation (1), the surrogate problem is solved to attain the local model $w_{n}^{t}$ for each global round $t$ as follows

where $D_{F_{n}}$ denotes the Bregman divergence [21] of $F_{n}(\cdot)$

$\hat{F}(w|w^{t-1})$ denotes the first-order approximation of the global function $F(\cdot)$ at $w^{t-1}$

and $\eta>0$ is the weight that balances between two objectives which is also our controlled learning parameter. The Bregman divergence is the generalized distance between the local model solution $w$ and the latest global model parameter $w^{t-1}$ (e.g., square Euclidean distance) that is widely applied in machine learning applications, statistics, and information geometry [21]. Thus, the local model at UEs can be constructed by minimizing the surrogate objective with the approximated loss function minimization such that its parameters is close to the latest global model parameter $w^{t-1}$. Then the equivalent local learning problem is derived as follows

Since it is usually difficult to obtain the optimal solution in the learning problem (4), UEs is required find a (possibly weak) solution $w_{n}^{t}$ instead. As an analogy from the definition for the relative accuracy in [26, 14] for the approximation, the local weight parameters at all UEs satisfy

where the relative local accuracy $\theta\in(0,1)$ is common to all UEs. This parameter also defines the quality of the approximation solutions when solving the local learning problem (3), in which $\theta=0$ the optimal solution is obtained, while $\theta=1$ we have no progress (i.e., $w_{n}^{t}=w^{t-1}$). Since the objectives $J_{n}^{t}(w)$ and $F_{n}(\cdot)$ have the same Hessian matrix, $J_{n}^{t}(w)$ is also $\beta$-strongly convex and $L$-smooth. Accordingly, the gradient descent (GD) method is reasonable to solve (4) and requires $K_{l}$ number of local iterations to achieve the accuracy $\theta$-approximation of the solution.

where $h_{k}$ is a learning rate. Note that each UE holds a small portion of samples, i.e, $D_{n}<<D$, $\forall n$. In case of large $D_{n}$, mini-batch SGD can be used to alleviate the computation burden on UEs, but the convergence rate will be different. We assume that the generated convergent sequence $(w^{k}_{n})_{k\geq 0}$ for the local model satisfying a linear convergence rate [27] as follows

where $w^{*}_{n}$ is the optimal solution of the local problem (4), and $c$ and $\gamma\in(0,1)$ are constants depending on $\rho$.

Global model updates at the server: Considering a synchronous federated learning scheme, the global model parameter is then updated by aggregating the local model parameter $w_{n}^{t}$ from all UEs as follows

This updated global model is then broadcast along with $\nabla F(w^{t})$ to all UEs (line 5) to all UEs. The convergence of the global problem (2) is achieved by satisfying

where $\epsilon>0$ is an arbitrarily small constant, $w^{*}$ is the optimal solution of the problem (2). The algorithm enhances data privacy by exchanging learning information only rather than the local training data. The convergence analysis for FEDL is developed in [20].

We show the detail proofs of Lemma 1, Theorem 1, and Corollary 1 in the work [20].

Learning Time Model: According to the convergence analysis of the federated learning algorithm, we obtain the convergence rate and the global rounds depend on the hyper-learning rate $\eta$ and the relative accuracy of the local learning problem $\theta$ as in Corollary 1. Therefore, the total learning time can be defined in the general form as follows

where $c$ is the one round of communication time, $\mathcal{T}(\theta)$ is the required time to obtain the relative accuracy $\theta$ of the local learning algorithm, and $K_{g}(\Theta)$ is the required number of global rounds in the equation (12) and the $\Theta$ is defined in the equation (12). In a common setting of many federated learning frameworks [6, 18], the number of local iterations is often fixed for each UE, thus, the remaining control parameter is the hyper-learning rate $\eta$ that affects to the number of global rounds. Accordingly, we substitute the constants and get the simplified form as follows

where

In this paper, we consider a multi-service federated learning scheme with one Federated Learning Orchestrator (FLO) at the MEC server and a set $\mathcal{N}$ of $N$ UEs as shown in Fig. 1. Each participating UE $n$ stores a local data set $\mathcal{D}_{s,n}$ with size $D_{s,n}$ for each federated learning service $s$. Then, we can define the total data size of a service $s$ by $D_{s}=\sum_{n=1}^{N}D_{s,n}$. The CPU resource of each UE is consumed to perform the local learning problem in (4) for each service $s$ by using the local data. Therefore, it is crucial to share the CPU resource of each UE amongst the local learning problems of multiple services efficiently. After the local training, all UEs upload their updated local model parameters to the MEC server by using the wireless medium. Hence, it is also important to efficiently share the communication resource (i.e., bandwidth) among the UEs. At the MEC server, FLO is deployed to manage computation (i.e., CPU) and communication resources sharing among learning services and UEs. In addition to resource allocation, FLO also controls the hyper-learning rate of learning services.

Since the learning services jointly occupy the shared CPU resource in each UE, and the shared uplink bandwidth resource to upload the weight parameters of local models. Thus, FLO takes a role to manage these shared resources and controls the hyper-learning rate of learning services. To minimize the running time cost and the energy consumption of UEs, we propose the multi-service Federated Learning optimization problem for FLO, MS-FEDL, as follows

where $f_{n}^{tot}$ is the total CPU frequency of UE $n$. The main decision variables include the allocated CPU frequency (i.e., ${f}:=\{f_{s,n}\}$) for each service $s$ at UE $n$, the allocated fraction (i.e., ${w}:=\{w_{n}\}$ ) of total uplink bandwidth for each UE $n$, and the relative accuracy (i.e., ${\theta}:=\{\theta_{s}\}$) of the local learning problem at UEs. According to the constraints in (26), (27), all of the learning services and UEs are required to be allocated at least the minimum amount of CPU frequency and bandwidth to train and upload the learning parameters of local model. Besides, the auxiliary variables $T^{cmp}_{s}$ is the computational time of one local iteration, and $T^{com}_{s}$ is the uplink transmission time which depends on $f$ and $w$ in the constraint (29), (30), respectively. The constraint (24) indicates the shared CPU resource among learning services and the constraint (25) defines the shared uplink bandwidth for each UE. Lastly, the constraint (25) provides the feasible ranges of the learning parameters in the FEDL algorithm for each learning service.

Even though the MS-FEDL problem is non-convex, we later show the specific form of this problem is bi-convex [30]. The convexity proofs of subproblems are shown in the appendices. For solving this type of problem, we adopt the popular technique, Block Coordinate Descent (BCD) algorithm [30]. The block coordinate descent method cyclically solves the optimization problem for each block of variables while fixing the remaining blocks at their last updated values by following the Gauss-Seidel update scheme. In the MS-FEDL problem, there are two blocks of variables such as block of $\theta$ and block of $f,w$. The detail of the centralized algorithm is shown in Algorithm 2.

Given the fixed values $\hat{f},\hat{w}$ for the resource allocation variable block $f,w$ and the corresponding computation, communication time $\hat{T^{cmp}_{s}},\hat{T^{com}_{s}}$, the total cost for each learning service $s$ (i.e., $\hat{\cal{C}}_{s}\mathrel{\mathop{:}}=E_{s}^{gl}(\hat{f}_{s},\hat{w})+\kappa_{s}T_{s}^{gl}(\hat{T^{cmp}_{s}},\hat{T^{com}_{s}})$), we have the learning parameter decision problem as follows

SUB1-c ​: Learning Parameter Decision Problem

where ${\eta}:=\{\eta_{s}\}$. In $K_{g}(\Theta_{s})$, $\Theta_{s}$ are the functions of the hyper-learning rate $\eta_{s}$ and it is defined in the equation (15). However, the hyper-learning rate decision subproblem SUB1-c can be decentralized for each learning service $s$ without any coupling among services in the constraints. Thus, each service $s$ can make the decision independently by solving the following decentralized subproblem.

SUB1-d ​: Decentralized Learning Parameter Decision

Accordingly, we provide the proof for Lemma 2 in the appendix section. In addition, Fig. 2 illustrates the convexity of the SUB1-d subproblem for three learning services. The optimal solutions are obtained by using Lemma 2 and marked as the circles which are also the lowest values of the objective curves. As an observation, both high and low values of the hyper-learning rate $\eta$ cause a higher number of global rounds $K_{g}$ and higher total cost for each learning service.

According to Lemma 2, the optimal hyper-learning rate solutions do not depend on the total cost for each learning service $\hat{\cal{C}}_{s}$. Thus, the optimal solution of this problem is independent to the other decisions. Then, given the optimal learning parameter $\eta^{*}$ and the corresponding $\Theta^{*}_{s}$, the problem can be decomposed into two independent sub-problems for CPU frequency allocation and bandwidth allocation as follows

SUB2-c ​: CPU Allocation Problem

where ${T^{cmp}}:=\{T^{cmp}_{s}\}$.
This problem decides a number of CPU frequency for each learning service at UEs.

SUB3-c ​: Bandwidth Allocation Problem

where ${T^{com}}:=\{T^{com}_{s}\}$.

Using block coordinate descent, FLO solves alternatively three convex subproblems of the hyper-learning rate decision, CPU allocation, bandwidth allocation. Discussion as mentioned above, the optimal hyper-learning rate decision can be obtained independently, then only one iteration is required in block coordinate descent style algorithm. These convex problems that can be easily solved by using a off-the-shelf convex solver (i.e., IpOpt solver [31]). After solving these problems, the resource allocation solutions and the decision of the hyper-learning rate are sent to the UEs to start the learning process. The whole operation process is illustrated in Fig. 3.

In addition to the centralized algorithm, we develop a decentralized algorithm, which leverages the parallelism structure for subproblems update of Jacobi-Proximal ADMM[23] into the multi-convex ADMM framework[24], namely JP-miADMM. Since the original form of multi-convex ADMM using the conventional Gauss-Seidel scheme does not allow solving the CPU allocation subproblem independently, the integrated Jacobi-Proximal ADMM form provides the parallelism structure for this subproblem. The JP-miADMM algorithm consists of two procedures, such as primal update which can be independently solved by each service $s$ and dual update takes the role of a coordinator from the solutions of learning services. Note that in the following primal subproblems of JP-miADMM, the objectives comprise the addictive norm-2 terms which are the augmented term that originally is introduced in ADMM and proximal term in Jacobi-Proximal ADMM. These two updates are performed iteratively until the convergence condition is obtained. In this algorithm, we introduce the dual variables $v,y$, and the auxiliary variable $z$ that are used in the next subproblems. The detail of the decentralized algorithm is shown in Algorithm 3 by alternatively updating the primal variables, primal residual and dual variables until the convergence conditions in line 14 are obtained. Specifically, the first condition is the condition of CPU allocation based on the Frobenius norm of allocation matrix $f$ while the second one is based on the vector norm of bandwidth allocation solution $w$.

Since the optimal hyper-learning rate decision (i.e., $\eta^{*}$) is obtained independently according to the closed-form in Lemma 2 for each learning service, the JP-miADMM algorithm consists of an iterative process on the shared CPU and bandwidth allocation as follows

In this work, we assume that three learning services are deployed at the edge networks. Moreover, 50 heterogeneous UEs are positioned within the coverage area of the base station to participate in the federated learning system. Similar to our prior works [20, 10], we consider that the channel gain between the base station and the UE follows the exponential distribution with the mean $g_{0}(d_{0}/d)^{4}$ where $g_{0}=-40\,dB$, the reference distance $d_{0}=1\,m$ between BS and UEs. Here, the actual distance $d$ between the UEs and the base station is uniformly generated between $[2,50]\,m$. Furthermore, the uplink system bandwidth $B=20\,MHz$ is shared amongst UEs, the Noise power spectral is $10^{-10}\,W$, and the transmit power of UEs and BS are $10\,W$ and $40\,W$, respectively. In this work, we assume that the size of the uploaded local model and downloaded global model is the same and it is set to $v_{s}\in\{100,200,300\}\,KB$ for each service.

For the local training model at UEs, we first set the training data size of UEs in each learning service following a uniform distribution in $10-20\,MB$. The maximum computation capacity (i.e., CPU frequency) at each UE is uniformly distributed between $[1,2]\,GHz$. The required CPU cycles $c_{s}$ to train one bit of data at the UE for each learning service is $\{50,70,90\}\,cycles$. Furthermore, the minimum required CPU frequency for each service is $f^{min}_{s}=0.1\,GHz$. We consider that the effective capacitance coefficient is the same for all UEs as $\beta_{n}=2\cdot 10^{-28}$ and the trade-off parameter $\kappa_{s}$ is set to $0.2$. For the federated learning parameters, we set $L=1,\,\beta=0.5,\gamma=1,$ and $c=1$. Then, the relative accuracy of the local problem at UEs for each service is $\theta\in\{0.07,0.06,0.05\}$. This setting reflects the CPU frequency requirement and model size as above and defines the required number of local iterations for each learning service correspondingly. Finally, for the algorithm setting, we set the convergence thresholds in the algorithms as $\epsilon_{1}$ and $\epsilon_{2}$ are $10^{-4}$ and $10^{-5}$, respectively. Then, the values of the parameters $\rho_{1}$, $\rho_{2}$, and $\nu$ are $1000$, $10$, and $1500$ respectively.