# Online Supervised Learning with Distributed Features over Multiagent System

Authors: Xibin An; Bing He; Chen Hu; Bingqi Liu
Journal: Complexity
 (2020)

---

## Abstract

Most current online distributed machine learning algorithms have been studied in a data-parallel architecture among agents in networks. We study online distributed machine learning from a different perspective, where the features about the same samples are observed by multiple agents that wish to collaborate but do not exchange the raw data with each other. We propose a distributed feature online gradient descent algorithm and prove that local solution converges to the global minimizer with a sublinear rateO2T. Our algorithm does not require exchange of the primal data or even the model parameters between agents. Firstly, we design an auxiliary variable, which implies the information of the global features, and estimate at each agent by dynamic consensus method. Then, local parameters are updated by online gradient descent method based on local data stream. Simulations illustrate the performance of the proposed algorithm.


---

## Body

## 1. Introduction

With the development of multiagent system, the observed data are being generated at anywhere, anytime, using different devices and technologies [1–3]. There is a lot of interest in extracting knowledge from this massive amount of data and using it to choose a suitable business strategy [4–6], to generate control command [7–9] or to make a decision [10–13]. Many applications are required to process incoming data in online way, e.g., a bank monitors the transactions of its clients to detect frauds [2], wireless sensor networks makes inference [14], and sensor network tracks the uncooperative target [15]. The study of online learning is becoming an important topic of research itself [16–18].The success of online machine learning often depends on the entire data stream. In some applications, the observed data may be generated on and held by multiple agents [1, 13]. Collecting data to a central site for training incurs extra management and privacy concerns [1]. As a result, some distributed machine learning algorithms have been proposed to train a model by letting each agent perform local model updates and exchange some information between neighbors [19–22]. Most of the existing algorithms fall into the data-parallel computation [1], where each agent has its local data stream with the entire features. However, in network applications, multiple agents are used to monitor an environment, where agents are distributed over space and are used to collect different measurements. For example, the observation is generated by different observed models [8, 9]. It is urgent to develop some applicable algorithm to deal with data streams with distributed features over networks.In batch learning settings, some algorithms have been proposed for distributed features, such as variance-reduced dynamic diffusion (VRD2) [12], feature distributed machine learning (FDML) [1], and the ADMM (alternating direction method of multipliers) sharing [23]. VRD2 and FDML obtain the optimal solution in primal domain, and the local model is trained in a distributed manner based on the local features. The ADMM sharing algorithm formulates distributed feature learning as a distributed primal-dual problem and then obtains the optimal solution by ADMM algorithm. These algorithms in [1, 12, 23] effectively deal with the batch distributed feature learning in a distributed form. However, these algorithms in [1, 12, 23] need to access the entire dataset and cannot be applied in online settings. As the observation is continuously arriving very fast in networks, it is important to study online feature distributed machine learning.In this paper, we consider the situation where the features are split across agents in online settings either due to privacy consideration or because they are already physically collected in a distributed manner by means of a networked architecture. We propose a distributed feature online gradient algorithm. Online supervised learning over networks is formulated as a “cost of sum” form. The procedure of the proposed algorithm requires two-scales: one scale is used to update the parameters by gradient descent and a second faster scale for running the consistency step multiple times to track an auxiliary term. The main contributions of this paper are summarized as follows.(1)
We propose a distributed feature online gradient (DFOG) descent algorithm. By exchanging some information between neighbors, local solution can approximate the global solution. Compared with VRD2 [12], FDML [1], and the sharing ADMM algorithm [23], DFOG is applicable to online supervised learning with distributed features over networks.(2)
We firstly formulate the centralized cost as a “cost of sum” form. By dynamic consensus algorithm, each node can track the sum term, which implies the entire features of the sample at each round time. Then, with the help of online gradient descent algorithm, each node locally updates the parameters based on its data stream.(3)
We prove that the proposed algorithm achieves anO2T regret bound. That is, local solution can approach to the global solution, which is the best decision trained based on the entire dataset. The only transmitted message is some parameters’ information, and the proposed algorithm does not require the data of the total number times and does not exchange the raw data between neighbors.The rest of this paper is organized as follows: the problem formulation is discussed in Section 2. In Section 3, we focus on our online optimization algorithm with distributed features over multiagent system, followed by the theoretical results in Section 4. In Section 5, simulations illustrate the effectiveness of our algorithm. Finally, we conclude the paper in Section 6.Notation and terminology: letx be the feature space and y be the corresponding label. We denote the i,jth element of a matrix A by ai,j. For t∈ℕ+, the set 1,2,…,T is denoted by T. For a convex function f, its gradient at a point ω is denoted as ∇ωfω. We denote N as the number of agents in the network. Let ℝd be the d-dimensional vector space and ω22 is the Euclidean norm of a vector ω∈ℝd.


## 2. Problem Formulation

We consider a multiagent system withN agents. The communication between agents is described by a connected graph G=V,ℰ [24], consisting of a set of nodes V=1,2,…,N, a set of edges ℰ, and an adjacent matrix A [19]. For each agent i∈V, we denote ℰi=j|j,i∈ℰ as a set of neighbors of agent i (including agent i itself).Assumption 1.
The graphG=V,ℰ and the adjacent weighted matrix A satisfy the following [25]:(i)
A is a doubly stochastic matrix with positive diagonal, that is, aii>0, ∑j=1Naj,i=1, and ∑j=1Nai,j=1;(ii)
There exists a scalarζ>0 such that aj,i>ζ if j,i∈ℰ;(iii)
There exists an integerB≥1 such that the graph V,ℰiB+1∪⋯∪ℰj+1B is strongly connected.
In this work, we focus on a binary online supervised learning with distributed features. The features are distributed over a collection ofK agents, as illustrated in Figure 1.
At each timet=1,2,…,T, network receives a labeled sample xt,yt. For all the time T, we consider an empirical risk as follows:(1)Lω=1T∑t=1TfωTxt,yt+rω,where the parameters are denoted as ω∈ℝd×1, d is the dimension of the features, and yt∈−1,+1 is the corresponding scalar label of xt at time t. Moreover, the cost fω is convex and differentiable. In most problem of interest, the cost function is dependent on the inner product ωTx, such as the linear SVM cost f=max0,1−ytwTxt and the logistic regression cost f=log1+exp−ytωTxt. The factor rω represents the regularization term. Since the features of xt are distributed across agents, we set ω and xt to be column vector and formulate ω and xt into N subvectors denoted by ωi and xt,i, respectively, that is,(2)xt=xt,1xt,2⋮xt,N,ω=ω1ω2⋮ωN.
Each subfeaturext,i vector and subvector ωi is located at agent i. Then, cost function (1) can be rewritten as(3)L=1T∑t=1Tf∑i=1NωiTxt,i;yt+∑i=1Nrωi,where the regularization term is assumed to satisfy an additive form as (4)rω=∑i=1Nrωi.
This property holds for many popular regularization choices, such asl2, l1, and KL-divergence. Problem of this type has been studied before in the literature by using distributed optimization methods in [20, 21]. One common way is to formulate problem (3) into a constrained problem, that is,(5)Lω=minω1T∑t=1Tfzt;yt+∑i=1Nrωis.t.zt=∑i=1NωiTxt,i,t=1,2,…,T.
For all the timeT, problem (5) is a classical “cost of sum” form [20]. An effective way is to design the Lagrangian function by introducing the dual variable γ [23], namely,(6)Lγ,z,ω=1T∑t=1Tfzt;yt+1T∑t=1Tγtzt−1T∑t=1Tγt∑i=1NωiTxi,t+∑i=1Nrωi.
Problem (6) can be solved in a number of distributed primal-dual methods, such as alternating direction method of multipliers (ADMM) [4, 22, 26] and primal-dual methods [27–29]. These techniques have good convergence properties but suffer from high computational costs and two-time scale communications.
The other way is studied in primal domain [12]. The algorithm in [12] requires a two-time scale operation: a faster time-scale for the consensus iterations and a slower time-scale for the data sampling and the gradient computing. First, we use a consensus strategy to obtain the sum term ∑i=1NωiTxt,i, namely,(7)z^nk,i=∑j∈ℰiaijNωk,jTxnk,j,where nk denotes the index of the sample selected uniformly at random from 1,2,…,T. After sufficient iterations, it is well-known that z^nk,i⟶1/N∑i=1Nznk,i. Then, the stochastic-gradient step is used to update the parameters ω, where the gradient is evaluated by the gradient vector of the cost evaluated at some random data xnk,ynk.
In online settings, since the dataxt,yt is observed one by one, we cannot access to the total dataset xt,ytt=1T. These algorithms in [1, 12, 23] cannot be applied for data stream with distributed feature over networks. For each time t=1,2,…,T, the multiagent system is endowed with a sequence of cost function Ltt=1T, and the goal is to minimize the sum of the cost function. Specifically, we want to minimize the difference between the total cost multiagent system has incurred and that of the best fixed decision in hindsight, which is called regret, and its definition is given as follows: (8)RegT=∑t=1TLtωt−∑t=1TLtω∗,where ω∗ is the best decision of problem (1), that is, (9)ω∗=argminω∑t=1TLtω.
Moreover, we consider the time-varying cost functionLt as(10)Ltωt=Q∑i=1Nωt,iTxt,i;yt+∑i=1Nrωt,i.
Generally speaking, the costQ∑i=1NωiTxt,i;yt satisfies Assumption 2.Figure 1
Distributing the features across agents.Assumption 2.
The loss functionQ⋅ is convex and differentiable, and the gradient ∇ωQω is uniform boundedness, that is, ∇ωQω≤C for some scalar C>0.
Regret is the standard measure of the performance of online optimization algorithm [19]. An algorithm attains good performance if the regret is sublinear as a function of the total time T.Remark 1.
In the multiagent system, since the entries of the featurext are distributed over N agents, each agent just observes its own data stream. We face the following two challenges in solving problem (8):(1)
Distributed challenge: each agent only receives local data streamxt,i,yt and does not access to the entire features xt,yt. Under the condition that we do not exchange the raw data between neighbors, each agent needs to obtain some information on the entire features.(2)
Online challenge: at any timet1, we only have observation for t≤t1 and do not know Lt for t1≤t≤T. It is difficult to store all the observations due to the high-dimensional and high-velocity data stream. We need to update the parameters based on the current sample and the previous parameters and pursue a solution approximating to the global solution ω∗, which is the best decision based on all the data xt,ytt=1t as a prior in offline settings.


## 3. Distributed Feature Online Gradient Descent Algorithm

In this section, we first analyse a dynamic average consensus method for approximating the sum ofωiTxt,i at agent i and propose an online convex optimization to update the parameters ω. The detailed framework is summarised in Figure 2.Figure 2
The framework of the proposed algorithm.Now, we consider the problem of minimizing (5) by means of an online convex optimization. Let zt=∑i=1Nωt,iTxt,i denote the inner product that is available at time t∈T. The cost function Lt can be described as(11)Ltωt=Qzt;yt+∑i=1Nrωt,i.If each agenti can obtain the auxiliary variable zt at any time t, the parameters ωt,i can be obtained by minimizing the local cost Lt,i, which is defined as(12)Lt,i=Qzt;yt+rωt,i.However, the computation ofzt needs to access to all the subfeatures xt,i and the subvectors ωt,i over N agents. We denote the average of the local inner products as(13)z¯t=1N∑i=1Nωt,iTxt,i.Motivated by works in [30–34], z¯t can be approximated by a diffusion-based algorithm. Since the desired variable zt is proportional to the average value z¯t, zt=Nz¯t, the consensus strategy can be used to approximate zt. Specifically, for the total number of iterations M, each agent would repeat the following steps M times:(14)z^t,im+1=∑j∈Εiaijz^t,im,m=0,1,…M−1,where z^t,i0=Nωt,iTxt,i. After each agent obtains the estimator of zt denoted as z^t,i, problem (12) is converted into a differentiable dynamic problem. For online convex optimization problem, online gradient descent and its variants have been achieving optimal dynamic regret in many applications [35]. Recalling that ωt and xt are partitioned into N blocks, the gradient step can be performed in parallel over N agents. Specifically,(15)ωt,i=ωt−1,i−μt∇zQz^t,i;ytxt,i−μt∇ωrωt,i,where the step-size μt should satisfy μt>0, ∑t=1∞μt=∞, and ∑t=1∞μt2<∞.The full algorithm is summarized in Algorithm1.Algorithm 1: Distributed feature online gradient (DFOG) descent for agent i.
(1)
Initialization: setω0,i=0.(2)
Repeat fori=1,2,…,N:(3)
z^0,i=Nω0,iTxt,i(4)
Form=0,1,2,…,M−1(5)
z^t,im+1=∑j∈ℰiaijz^t,im(6)
End(7)
ωt,i=ωt−1,i−μt∇zQz^t,i;ytxt,i−μt∇ωrωt,i(8)
EndRemark 2.
Compared with FDML [1], VRD2 [12], and the ADMM sharing algorithm [23], DFOG is applicable for data stream with distributed features over multiagent system. At each round time, agents observe the same sample from different features. Each agent can obtain an auxiliary term, which implies the information on the entire features. Then, each agent locally runs a gradient descent step to update its local parameters. The procedure of Algorithm 1 is designed to update the parameters ωt,i locally.


## 4. Algorithm Analysis

### 4.1. Convergency Analysis

In this section, we analyse the convergence of the proposed algorithm. We first show that the distance betweenz^t,i and zt is upper bounded by the difference between PM and 1/N, which is shown in Lemma 1 and proved in [25].Lemma 1.
Let Assumption1 holds, for all agents i,j; we have (16)PMij−1N≤1−ζ4N2M/B−2,where N is total number of agents and M is the number of consensus steps in(14).Then, we show that the regret of online gradient descent (OGD) is upper bounded by the cumulative difference between the loss ofωt and ωt+1, which is present in Lemma 2 and proved in [18].Lemma 2.
Letωt,it=1T denotes the sequence of parameters produced by OGD. Then, for any u, we have(17)RegiT=∑t=1TLt,iωt,i−Lt,iu≤ru−rω1,i+∑t=1TQωt,i−Qωt+1,i.
Because the features are distributed across agents,RegiT mainly illustrates the difference between local parameters ωi and the corresponding parameters ωi∗ in global solution. Based on the above lemma, we derive a regret bound of ωi for DFOG with the regularization term rωi=1/2μωi22.Theorem 1.
Let Assumptions1 and 2 hold, and consider running DFOG on a sequence of convex function, Qωt,i for all t, with the regularization term rωi=1/2μωi22. Let ωt,it=1T be the sequence of vectors produced by DFOG. If u≤U and μ=U/C2T, the regret of ωi satisfies (18)RegiT≤CU2T+C2U2T+U22T,where C2=C/21−ζ/4N2M/B−2zt∗x∗. The proof is presented in Appendix.Remark 3.
This theorem indicates that the convergence rate of DFOG depends on the network topology throughB and the number of consensus steps M. The larger the M is or the smaller the B is, the faster the convergence speed is. The theorem presents that the proposed algorithm converges to the global solution with sublinear rate. When the number of data samples increases, the difference between ωt,i with ωi∗ will become closer.


### 4.2. Complexity Analysis

#### 4.2.1. Time Complexity

There are two primary operations associated with learning for DFOG: (1) estimating the inner productz^t for each sample at time t and (2) updating the parameters at gradient descent step. At any time t, each estimator z^t computation requires OM arithmetic operations. There is one gradient descent step to update the parameters, which requires O1 arithmetic operations. As for each time, each node will require OM arithmetic operations. Hence, single node requires OTM arithmetic operations for DFOG.


#### 4.2.2. Space Complexity

At any timet, DFOG needs to store the parameters z^t and ωt, which are updated and time-varying. Hence, space complexity for DFOG is O1.


#### 4.2.3. Communication Complexity

We denote the average degree of the communication graph ask. At each consensus step, each node requires to exchange z^t (float type, 4 bytes) with its neighbors. Since the network topology is an undirected graph, it requires 8kM bytes at any time t. Hence, DFOG requires communication traffic of DFOG is 8kMT bytes for all the time T.


## 4.1. Convergency Analysis

In this section, we analyse the convergence of the proposed algorithm. We first show that the distance betweenz^t,i and zt is upper bounded by the difference between PM and 1/N, which is shown in Lemma 1 and proved in [25].Lemma 1.
Let Assumption1 holds, for all agents i,j; we have (16)PMij−1N≤1−ζ4N2M/B−2,where N is total number of agents and M is the number of consensus steps in(14).Then, we show that the regret of online gradient descent (OGD) is upper bounded by the cumulative difference between the loss ofωt and ωt+1, which is present in Lemma 2 and proved in [18].Lemma 2.
Letωt,it=1T denotes the sequence of parameters produced by OGD. Then, for any u, we have(17)RegiT=∑t=1TLt,iωt,i−Lt,iu≤ru−rω1,i+∑t=1TQωt,i−Qωt+1,i.
Because the features are distributed across agents,RegiT mainly illustrates the difference between local parameters ωi and the corresponding parameters ωi∗ in global solution. Based on the above lemma, we derive a regret bound of ωi for DFOG with the regularization term rωi=1/2μωi22.Theorem 1.
Let Assumptions1 and 2 hold, and consider running DFOG on a sequence of convex function, Qωt,i for all t, with the regularization term rωi=1/2μωi22. Let ωt,it=1T be the sequence of vectors produced by DFOG. If u≤U and μ=U/C2T, the regret of ωi satisfies (18)RegiT≤CU2T+C2U2T+U22T,where C2=C/21−ζ/4N2M/B−2zt∗x∗. The proof is presented in Appendix.Remark 3.
This theorem indicates that the convergence rate of DFOG depends on the network topology throughB and the number of consensus steps M. The larger the M is or the smaller the B is, the faster the convergence speed is. The theorem presents that the proposed algorithm converges to the global solution with sublinear rate. When the number of data samples increases, the difference between ωt,i with ωi∗ will become closer.


## 4.2. Complexity Analysis

### 4.2.1. Time Complexity

There are two primary operations associated with learning for DFOG: (1) estimating the inner productz^t for each sample at time t and (2) updating the parameters at gradient descent step. At any time t, each estimator z^t computation requires OM arithmetic operations. There is one gradient descent step to update the parameters, which requires O1 arithmetic operations. As for each time, each node will require OM arithmetic operations. Hence, single node requires OTM arithmetic operations for DFOG.


### 4.2.2. Space Complexity

At any timet, DFOG needs to store the parameters z^t and ωt, which are updated and time-varying. Hence, space complexity for DFOG is O1.


### 4.2.3. Communication Complexity

We denote the average degree of the communication graph ask. At each consensus step, each node requires to exchange z^t (float type, 4 bytes) with its neighbors. Since the network topology is an undirected graph, it requires 8kM bytes at any time t. Hence, DFOG requires communication traffic of DFOG is 8kMT bytes for all the time T.


## 4.2.1. Time Complexity

There are two primary operations associated with learning for DFOG: (1) estimating the inner productz^t for each sample at time t and (2) updating the parameters at gradient descent step. At any time t, each estimator z^t computation requires OM arithmetic operations. There is one gradient descent step to update the parameters, which requires O1 arithmetic operations. As for each time, each node will require OM arithmetic operations. Hence, single node requires OTM arithmetic operations for DFOG.


## 4.2.2. Space Complexity

At any timet, DFOG needs to store the parameters z^t and ωt, which are updated and time-varying. Hence, space complexity for DFOG is O1.


## 4.2.3. Communication Complexity

We denote the average degree of the communication graph ask. At each consensus step, each node requires to exchange z^t (float type, 4 bytes) with its neighbors. Since the network topology is an undirected graph, it requires 8kM bytes at any time t. Hence, DFOG requires communication traffic of DFOG is 8kMT bytes for all the time T.


## 5. Simulation

In this section, we test our algorithm by minimizing norm regularized logistic regression on two public datasets, a9a and bank from UCI. Here, a multiagent system with 6 agents is considered, and the network is generated by the random geometric graph model. a9a dataset consists of 32561 training samples, 16281 testing samples, and 123 features. We separate the features into 6 parts, and each node obtains one part with 21, 21, 21, 20, 20, and 20 features as the local data, respectively. On the other hand, the bank dataset contains 4068 training samples, 453 testing samples, and 17 features. Similarly, we divide the features into 6 parts, each agent gets one part with 3, 3, 3, 3, 3, and 2 features as the local data, respectively. The loss function we use is(19)Lω=1T∑t=1Tlog1+exp−yt∑i=1NωiTxt,i+λ∑i=1Nωi2.Generally,λ is a positive constant and λ>0. The simulations are implemented in MATLAB to verify the proposed algorithm. Specifically, we use two optimization libraries, SGDLibrary [36] and DADAM [37], to minimize (19). In our simulation, the parameters are set as summarised in Table 1.Table 1
Parameter settings.
ParameterValueλ0.1N5M30B10We adopt dynamic consensus method to obtainzt in (14) and use online gradient descent algorithm to update the parameter ωi locally in (15). In our simulations, we get the global model trained in a centralized manner if all the features were collected centrally by stochastic-gradient descent (SGD) algorithm. Next, we compare our algorithm against SGD algorithm proposed in [38] and keep track of the loss for different datasets and parameters settings. Figures 3 and 4 present the evolution of the cost during the training procedure for a9a and bank datasets, respectively. In addition, to make a fair comparison, we analyse the convergence curve based on the count of gradient calculated. Table 2 shows the testing error for different datasets and the error of parameters for DFOG and SGD. The results show that DFOG can converge to the centralized solution of SGD, while keeping local feature sets to the corresponding agent. That is, DFOG can deal with the online supervised learning problem caused by distributed features over networks.Figure 3
The evolution of cost for a9a dataset.Figure 4
The evolution of cost for bank dataset.Table 2
Testing error and the relative error of parameters.
DatasetTesting error of SGDTesting error of DFOG∑i=1Nωi−ωi∗/ω∗9a0.75810.75810.0026Bank0.84550.84550.0064We next show how the performance depends on differentM. Note that when M is larger, we need to do more communication on the consistency step (14). Figure 5 shows the evolution of the cost with different M. It can be found that the larger the M we set, the faster the DFOG approaches to the centralized SGD algorithm.Figure 5
The convergence behavior with differentM.


## 6. Conclusions

In this paper, we considered an online supervised learning problem where the features are split across agents in online settings. We proposed an online supervised learning algorithm with distributed features over multiagent system. We first formulated the centralized cost as a “cost of sum” form. By dynamic consensus algorithm, each agent could effectively estimate the sum term, which is calculated based on the entire features at each round time. Then, with the help of online gradient descent algorithm, each agent locally updates the parameters. The algorithm designed does not require the data of the total number times and does not communicate the raw data between neighbors. We proved that local solution converges to the centralize minimizer, which is the best decision trained based on the entire dataset, and the proposed algorithm achieves anO2T regret bound. Simulations with real dataset verify the conclusion.Distributed machining learning algorithms are worth of further studies due to their promising future, including distributed online boosting, distributed decision tree [39], the use of Big data-aided learning [40], and distributed learning over time-varying communication topology in networks.



---

*Source: 8830359-2020-11-16.xml*