# Distributed Online Learning with Multiple Kernels

Jeongmin Chae, and Songnam Hong J. Chae is with the Department of Electrical
Engineering, University of Southern California, CA, 90089, USA (e-mail:
chaej@usc.edu)S. Hong is with the Department of Electronic Engineering,
Hanyang University, Seoul, 04763, Korea (e-mail<EMAIL_ADDRESS>
###### Abstract

We consider the problem of learning a nonlinear function over a network of
learners in a fully decentralized fashion. Online learning is additionally
assumed, where every learner receives continuous streaming data locally. This
learning model is called a fully distributed online learning (or a fully
decentralized online federated learning). For this model, we propose a novel
learning framework with multiple kernels, which is named DOMKL. The proposed
DOMKL is devised by harnessing the principles of an online alternating
direction method of multipliers and a distributed Hedge algorithm. We
theoretically prove that DOMKL over $T$ time slots can achieve an optimal
sublinear regret ${\cal O}(\sqrt{T})$, implying that every learner in the
network can learn a common function which has a diminishing gap from the best
function in hindsight. Our analysis also reveals that DOMKL yields the same
asymptotic performance of the state-of-the-art centralized approach while
keeping local data at edge learners. Via numerical tests with real datasets,
we demonstrate the effectiveness of the proposed DOMKL on various online
regression and time-series prediction tasks.

###### Index Terms:

Distributed online learning, decentralized federated learning, multiple kernel
learning, online learning.

##  I Introduction

In Internet-of-Things (IoT) systems, a massive number of machine-type (or
mobile) devices can be used to monitor and analyze various cyber-physical
systems such as smart city, connected cars, smart factory, intelligent energy
management, and so on [1, 2]. Machine learning plays a key role in
accomplishing such sophisticated tasks. In particular, this paper focuses on a
nonlinear function learning as it is of great interest in various machine
learning tasks such as classification, regression, clustering, and
dimensionality reduction [3, 4, 5]. Function learning tasks, in many existing
works, are conducted in a centralized fashion with the assumption that all
data (possibly measured in distributed edge devices) are gathered in a central
server. However, this assumption may not be acceptable due to the growing
concerns of data privacy. Several cases of data leakage and misuse have
demonstrated that centralizing local data comes at high risk for an end-user
privacy. A privacy-preserving distributed learning is witnessing an
unprecedented interest, in which local data is kept at distributed edge
devices without centralizing the data. According to the structures of a
communication network, this can be categorized into a centralized federated
learning [6, 7, 8, 9] and a fully distributed learning (a.k.a., a fully
decentralized federated learning) [10, 11, 12, 13]. In the former, a central
server is used to coordinate all the participating learners during the
learning process. Whereas, in the latter, edge learners can coordinate
themselves to learn a function, which is the main network structure to be
considered in this paper. Furthermore, in many real-world applications,
function learning tasks are expected to be performed in an online fashion.
Specifically, online learning is required when data arrive in a sequential way
[14] and when a large number of data makes it impossible to carry out data
analytic in batch form [15]. Therefore, it is necessary to investigate a
distributed online function learning for continuous streaming data, which is
the main subject of this paper.

Learning a function involves an optimization over a function space. This
challenging problem can be efficiently solved by restricting the function
space to a reproducing kernel Hilbert space (RKHS) which has attractive
properties from both the computational and statistical points of view [16].
Such function learning approach is called a kernel-based learning. Obviously
the accuracy of a kernel-based learning fully relies on a preselected basis
kernel. In many real-world applications, however, it is very challenging to
find an adequate single kernel. Multiple kernel learning (MKL), using a
preselected set of $P$ kernels (called a kernel dictionary), is more powerful
as it can enable a data-driven kernel selection from the kernel dictionary
[17, 18]. Specifically, a linear (or nonlinear) combination of multiple kernel
functions is optimized as a consequence of a function learning process.

A kernel-based learning has been extended into a fully decentralized network
[10, 11, 12] due to its necessity in various applications such as social
networks, big data processing, and environmental monitoring. In [10], a
consensus-based distributed MKL has been proposed for regression tasks, where
alternating direction method of multipliers (ADMM) [19] is used as the
underlying distributed optimization technique. A diffusion-based distributed
learning with a single kernel has been developed in [11], where the
cooperation of distributed nodes is performed via the diffusion rationale. In
addition, such diffusion-based approach has been incorporated into MKL
framework [12], being able to outperform the previous works [10, 11] in
distributed estimation tasks. However, none of the above kernel-based
approaches cannot operate in distribute online learning frameworks.

In a centralized network, online kernel-based learning has been proposed,
which seeks a sequence of kernel functions from a sequential data in an online
fashion [15, 20]. As shown in [3, 21], it suffers from a high computational
complexity as the dimension of optimization variables grow with time (i.e.,
the number of incoming data). This scalability problem has been addressed in
[22, 23] via a random feature (RF) approximation [24]. The RF-based online
kernel-based learning is named online MKL (OMKL) [23], where the optimization
size can be determined irrespective of the number of incoming data. Also, as
in MKL, OMKL can enjoy the advantage of using multiple kernels. Very recently,
active learning strategy for OMKL has been proposed in [23], yielding an
elegant accuracy performance and labeling cost tradeoff. Nevertheless, both
OMKL and AMKL are not applicable to distributed online learning tasks because
the underlying optimization method based on OGD can only operate with a
centralized data. As far as we know, there exists one related work for
distributed kernel-based online learning, which is dubbed RFF-DOKL [25]. This
method is devised based on single kernel-based learning with RF approximation
and a diffusion strategy to satisfy the consensus constraint. As expected, it
cannot yield an attractive performance mainly due to the inherent limitation
of using a predetermined single kernel. Thus, it is still an open problem to
construct an efficient multiple kernel-based algorithm for distributed online
learning tasks, which is the primary motivation of this paper.

In this work, we consider a fully distributed online learning framework. In
detail, we treat individual computational units (e.g., mobile devices) as
learners. They aim at learning a sequence of nonlinear functions independently
from their local streaming data and estimation information provided by their
neighbors via a communication network. Especially, our communication network
is assumed to be represented as an undirected graph, i.e., neighboring
learners can communicate with each other. Inspired by the success of MKL [18,
12, 22, 23], we propose a novel distributed online multiple kernel-based
learning (named DOMKL) for the above learning setting. Our key contributions
are summarized as follows.

  * •

In the proposed DOMKL, every learned function follows the particular structure
induced by a RF-based MKL as in the centralized OMKL. Thus. it can maintain
the advantages of OMKL such as scalability and an attractive accuracy. In
contrast, an underlying technique to optimize the parameters of such function
is completely different from that in OMKL. Thus, DOMKL can be considered as a
nontrivial extension of OMKL into a fully decentralized network.

  * •

To be specific, each learned function is fully determined by the parameters of
$P$ kernel functions and the weights for their proper combination. We optimize
them by presenting a novel two-step approach based on online ADMM and a Hedge
algorithm. Since our optimization only requires to exchange some estimates
(obtained by a complex nonlinear mapping of local data) with neighboring
learners, the privacy of local data is certainly preserved.

  * •

We theoretically prove that DOMKL over $T$ time slots can achieve an optimal
sublinear regret ${\cal O}(\sqrt{T})$ in terms of both learning accuracy and
constraint violation (i.e., discrepancy). This implies that as time grows,
every learner in a network can learn a common function having a diminishing
gap from the best function in hindsight. To the best of authors’ knowledge,
this is the first work of its kind that proposes a multiple kernel-based
algorithm with a theoretical performance guarantee under a distributed online
learning setting. Specifically, our analysis reveals that DOMKL yields the
same asymptotic performance with the centralized OMKL [22, 23] while keeping
local data at edge learners.

  * •

Via numerical tests with real datasets, we demonstrate the effectiveness of
the proposed DOMKL on various online regression and time-series prediction
tasks. It is shown that DOMKL significantly outperforms the state-of-the-art
RFF-DOKL, by enjoying the advantage of using multiple kernels. Furthermore,
DOMKL can still approach the performance of the centralized OMKL, even in non-
asymptotic cases. These results suggest practicality.

The remaining part of this paper is organized as follows. In Section II, we
provide some notations and definitions which will be used throughout the paper
and review a multiple kernel-based online learning. The proposed DOMKL is
described in Section III. We theoretically prove the asymptotic optimality of
DOMKL in Section IV. Beyond the asymptotic analysis, in Section V, we
demonstrate the effectiveness of our algorithm via experiments with real
datasets. Some concluding remarks are provided in Section VI.

Notations: Bold lowercase letters denote the column vectors. For any vector
${\bf x}$, ${\bf x}^{{\sf T}}$ denotes the transpose of ${\bf x}$ and $\|{\bf
x}\|$ denote the $\ell_{2}$-norm of ${\bf x}$. Also,
$\langle\cdot,\cdot\rangle$ represents the inner product in Euclidean space.
$\mbox{\bb E}[\cdot]$ represents the expectation over an associated
probability distribution. For any set ${\cal N}$, $|{\cal N}|$ denotes the
cardinality of ${\cal N}$ (i.e., the number of elements in ${\cal N}$). To
simplify the notations, we let
$[K]\stackrel{{\scriptstyle\Delta}}{{=}}\\{1,...,K\\}$ for any positive
integer $K$. Also, $k$, $t$, and $p$ will be used to indicate the indices of a
node, time, and kernel, respectively.

##  II Preliminaries

In this section, we describe the basic framework of an online function
learning and provide some definitions that will be used throughout the paper.
The main objective of an online learning is to seek a sequence of functions
$\\{\hat{f}:t\in[T]\\}$ such that the cumulative regret is minimized [26]:

${\rm regret}(T)=\sum_{t=1}^{T}{\cal L}\big{(}\hat{f}_{t}({\bf
x}_{t}),y_{t}\big{)}-\sum_{t=1}^{T}{\cal L}\big{(}f^{\star}({\bf
x}_{t}),y_{t}\big{)},$ (1)

where ${\cal L}(\cdot,\cdot)$ and $f^{\star}(\cdot)$ represent a cost (or
loss) function and the best function in hindsight, respectively. Due to the
nature of a streaming data, $\hat{f}_{t}(\cdot)$ is estimated only using the
received data $\\{({\bf x}_{\tau},y_{\tau}):\tau\in[t-1]\\}$. Then, it will be
used to generate an estimate $\hat{y}_{t}=\hat{f}_{t}({\bf x}_{t})$ of a newly
incoming data ${\bf x}_{t}$. This challenging problem has been efficiently
solved by incorporating a kernel-based learning into the above online learning
framework [15, 22, 23]. Particularly, the computational complexity of a
function learning becomes tractable by restricting a function space as a well-
structured reproducing Hilbert kernel space (RKHS) ${\cal H}_{p}$, defined as
${\cal H}_{p}\stackrel{{\scriptstyle\Delta}}{{=}}\left\\{f:f({\bf
x})=\sum_{t}\alpha_{t}\kappa_{p}({\bf x},{\bf x}_{t})\right\\}$, where
$\kappa_{p}({\bf x},{\bf x}_{t})$ denotes a symmetric positive semidefinite
basis function (called a kernel $\kappa_{p}$) [27]. One representative example
is a Gaussian kernel, which is fully defined by a single parameter (called
bandwidth) $\sigma_{p}^{2}$:

$\kappa_{p}({\bf x},{\bf x}_{t})=\exp\left(-\frac{\|{\bf x}-{\bf
x}_{t}\|^{2}}{2\sigma_{p}^{2}}\right).$ (2)

Especially when a number of incoming data is finite, the representer theorem
in [21] shows that an optimal solution to minimize the cumulative regret can
be represented as

$\hat{f}_{t}({\bf x})=\sum_{\tau=1}^{t-1}\alpha_{\tau}\kappa_{p}({\bf x},{\bf
x}_{\tau})\in{\cal H}_{p},$ (3)

for some coefficients $\alpha_{\tau}$’s. The major drawback of the above
function learning is the curse of dimensionality as the number of parameters
$\alpha_{\tau}$’s (to be optimized) grows with the number of incoming data.
This problem has been addressed via random feature (RF) approximation [24]
such that $\hat{f}_{t}({\bf x})$ can be well-approximated as

$\hat{f}_{t}({\bf x})=\hat{\hbox{\boldmath$\theta$}}_{[t,p]}^{{\sf T}}{\bf
z}_{p}({\bf x})\in{\cal H}_{p},$ (4)

with a parameter $\hat{\hbox{\boldmath$\theta$}}_{[t,p]}\in\mbox{\bb
R}^{2M\times 1}$, where the so-called randomized feature map ${\bf
z}_{p}(\cdot)$ is defined as

$\displaystyle{\bf z}_{p}({\bf x})=$
$\displaystyle\frac{1}{\sqrt{M}}\left[\sin{{\bf v}_{1}^{{\sf T}}{\bf
x}},...,\sin{{\bf v}_{M}^{{\sf T}}({\bf x}),\cos{{\bf v}_{1}^{{\sf T}}{\bf
x}},...,\cos{{\bf v}_{M}^{{\sf T}}{\bf x}}}\right]^{{\sf T}},$ (5)

where $\\{{\bf v}_{i}:i\in[M]\\}$ denotes an independent and identically
distributed samples from the Fourier transform of a given kernel function
$\kappa_{p}(\cdot,\cdot)$ (denoted by $\pi_{\kappa_{p}}({\bf v})$), i.e.,
${\bf v}_{i}\sim\pi_{\kappa_{p}}({\bf v})$. For a Gaussian kernel in (2),
$\pi_{\kappa_{p}}({\bf v})$ is a multivariate Gaussian distribution with the
mean vector $\hbox{\boldmath$\mu$}={\bf 0}$ and covariance matrix
${\bf\Sigma}=\sigma_{p}^{-2}{\bf I}$. It is remarkable that via RF
approximation, a function optimization has been converted into a much simper
vector (or parameter) optimization. Also, the parameter $M$ is a constant not
growing with a time index $t$ (e.g., $M=50$), which makes it suitable for an
online learning with continuous streaming data (i.e., $t$ could be extremely
large). Note that the accuracy of the kernel-based learning fully relies on a
preselected kernel $\kappa_{p}$, which can be chosen manually either by a
task-specific priori knowledge or by some intensive cross-validation process.
In many real-world applications, however, finding an adequate single kernel is
very demanding. Online multiple kernel learning (OMKL), using a predetermined
set of $P$ kernels (called a kernel dictionary), is more powerful as it can
enable a data-driven kernel selection from a given kernel dictionary [22, 23].
Specifically OMKL learns a sequence of functions, each of which has the form
of

$\hat{f}_{t}({\bf
x})=\sum_{p=1}^{P}\hat{q}_{[t,p]}\hat{\hbox{\boldmath$\theta$}}_{[t,p]}^{{\sf
T}}{\bf z}_{p}({\bf x})\in\bar{{\cal H}},$ (6)

where $\hat{f}_{[t,p]}({\bf x})=\hat{\hbox{\boldmath$\theta$}}_{[t,p]}^{{\sf
T}}{\bf z}_{p}({\bf x})\in{\cal H}_{p}$ (i.e., RKHS induced by the kernel
$\kappa_{p}$) and $\hat{q}_{[t,p]}\in[0,1]$ denotes the combination weight of
the kernel function $\hat{f}_{[t,p]}({\bf x})$. Then, we have

$\displaystyle\hat{f}_{t}\in\bar{{\cal H}}$ $\displaystyle={\cal
H}_{1}+\cdots+{\cal H}_{P}$
$\displaystyle\stackrel{{\scriptstyle\Delta}}{{=}}\big{\\{}\hat{f}_{[t,1]}+\cdots+\hat{f}_{[t,P]}:\hat{f}_{[t,p]}\in{\cal
H}_{p}\big{\\}},$

and $\bar{{\cal H}}$ is an RKHS from [27, Proposition 12.27].

Motivated by the success of multiple kernel-based learnings [10, 12, 22, 23],
our learned function in Section III will be assumed as a parameterized
function in (6). We emphasize that the parameters to be optimized in the
proposed algorithms are equivalent to those in OMKL [23] (e.g.,
$\\{\hat{\hbox{\boldmath$\theta$}}_{[t,p]},\hat{q}_{[t,p]}:p\in[P]\\}$),
whereas the optimization technique (or learning algorithm) in Section III is
completely different from that in OMKL.

##  III Methods

In this section, we study the problem of an online learning over a fully
decentralized network consisting of a set of $K$ learners (or nodes), indexed
by $k\in{\cal V}=\\{1,2,...,K\\}$. They learn a sequence of nonlinear
functions independently from their local streaming data and pass estimated
information to their neighbors in a communication network. This network is
completely defined by an undirected connected graph ${\cal G}=({\cal V},{\cal
E})$. For the case of a disconnected graph, the proposed algorithms can be
applied to each connected component separately. The ${\cal E}$ represents the
set of unordered pairs of the learners (called edges), defined as ${\cal
E}=\\{\\{k,\ell\\}:\mbox{the nodes }k\mbox{ and }\ell\mbox{ are
connected}\\}$. This shows the connectivity of the $K$ learners (i.e., a
network structure). For any node $k\in{\cal V}$, the index subset of its
neighbors is defined as ${\cal N}_{k}=\\{\ell:\\{k,\ell\\}\in{\cal
E}\\}\subseteq{\cal V}$. Since an undirected graph is assumed, it is obvious
that $\ell\in{\cal N}_{k}$ and $k\in{\cal N}_{\ell}$ if $\\{k,\ell\\}\in{\cal
E}$. Given a communication network ${\cal G}=({\cal V},{\cal E})$, it is
assumed that at every time $t$, each learner $k\in{\cal V}$ can transmit the
latest estimated information
$\\{\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]},\hat{q}_{[k,t,p]}:p\in[P]\\}$ to
its neighbors $\ell\in{\cal N}_{k}$. Definitely this communication protocol
can preserve privacy of local data as it should not be recovered from the
shared parameters and the relationship in (6) (i.e., the non-linearity of our
function model).

Given a communication network ${\cal G}=({\cal V},{\cal E})$, our goal is to
optimize the parameters of $P$ kernel functions and the combination weights in
a distributed way. In Section III-A, we first introduce a distributed online
learning with a predetermined single kernel (named DOKL). Appropriately
combining this method with a distributed Hedge algorithm, in Section III-B, we
propose a novel distributed online learning with multiple kernels (named
DOMKL).

###  III-A The Proposed DOKL

We first introduce a distributed kernel learning and extend it into our online
learning framework. Without loss of generality, a single kernel ${\cal
H}_{p}$, defined by a kernel $\kappa_{p}$, is assumed. As shown in (5), due to
the use of RF approximation, the characteristic of the kernel $\kappa_{p}$ is
only reflected by a randomized feature map ${\bf z}_{p}(\cdot)$. Using the
same seed value to generate the ${\bf z}_{p}(\cdot)$, all distributed learners
can have the identical map ${\bf z}_{p}(\cdot)$. Recall that $M$ and $K$
indicate the size of random features (see (5)) and the size of the set ${\cal
V}$ (i.e., $|{\cal V}|=K)$, respectively. In a distributed kernel learning,
every learner $k\in{\cal V}$ has its own local dataset $\\{({\bf
x}_{k,1},y_{k,1}),...,({\bf x}_{k,T},y_{k,T})\\}$ and learns a function
$\hat{f}_{k}({\bf x})$ collaboratively with its neighbors subject to a
consensus constraint. Also, based on a kernel-based learning, each function
$\hat{f}_{k}$(x) is fully determined by a parameter
$\hat{\hbox{\boldmath$\theta$}}_{[k,p]}\in\mbox{\bb R}^{2M\times 1}$, i.e.,

$\hat{f}_{k}({\bf
x})\stackrel{{\scriptstyle\Delta}}{{=}}\hat{\hbox{\boldmath$\theta$}}_{[k,p]}^{{\sf
T}}{\bf z}_{p}({\bf x}),\;\forall k\in{\cal V}.$ (7)

The parameters $\\{\hat{\hbox{\boldmath$\theta$}}_{[k,p]}:k\in{\cal V}\\}$ in
(7) can be optimized by taking the solution of

$\displaystyle\operatornamewithlimits{argmin}_{\\{\hbox{\boldmath$\theta$}_{k}:k\in{\cal
V}\\}}\;\;\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal
L}(\hbox{\boldmath$\theta$}_{k}^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t})$
$\displaystyle\mbox{ subject to
}\;\;\hbox{\boldmath$\theta$}_{k}=\hbox{\boldmath$\theta$}_{\ell},\forall
k\in{\cal V},\ell\in{\cal N}_{k}.$ (8)

The above constraint is known as consensus constraint in the context of a
distributed optimization. In [19], it was shown that the above problem can be
solved in a distributed way via alternating direction method of multipliers
(ADMM). Leveraging this, we convert the optimization problem (8) into the
standard from of ADMM:

$\displaystyle\operatornamewithlimits{argmin}_{\\{\hbox{\boldmath$\theta$}_{k}:k\in{\cal
V}\\}}\;\;\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal
L}(\hbox{\boldmath$\theta$}_{k}^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t})$
$\displaystyle\mbox{ subject to
}\;\;\hbox{\boldmath$\theta$}_{k}=\hbox{\boldmath$\gamma$}_{\\{k,\ell\\}},\;\;\forall
k\in{\cal V},\ell\in{\cal N}_{k},$ (9)

where
$\hbox{\boldmath$\gamma$}_{\\{\ell,k\\}}=\hbox{\boldmath$\gamma$}_{\\{\ell,k\\}}$
denotes an auxiliary vector assigned to every edge $\\{k,\ell\\}\in{\cal E}$.
It is easily verified that the constraints in (9) and (8) are equivalent.

We are now ready to propose a kernel-based distributed online learning (named
DOKL). The proposed DOKL aims at solving the optimization problem (9) in an
online fashion, under the assumption that data arrives sequentially. From our
theoretical analysis in Section IV, it is proved that the optimal sublinear
regrets from the optimal performance of (9) can be achieved, if the following
optimization problem is solved exactly at every time $t$:

$\displaystyle\\{\hat{\hbox{\boldmath$\theta$}}_{[t+1,k,p]}:k\in{\cal V}\\}=$
$\displaystyle\;\;\operatornamewithlimits{argmin}_{\\{\hbox{\boldmath$\theta$}_{k}:k\in{\cal
V}\\}}\;\;\sum_{k=1}^{K}{\cal L}(\hbox{\boldmath$\theta$}_{k}^{{\sf T}}{\bf
z}_{p}({\bf
x}_{k,t}),y_{k,t})+\frac{\eta_{l}}{2}\sum_{k=1}^{K}\|\hbox{\boldmath$\theta$}_{k}-\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}\|^{2}$
$\displaystyle\;\;\mbox{subject to
}\;\;\hbox{\boldmath$\theta$}_{k}=\hbox{\boldmath$\gamma$}_{\\{k,\ell\\}},\;\in\forall
k\in{\cal V},\ell\in{\cal N}_{k},$ (10)

where $\eta_{l}>0$ denotes a learning rate. Moreover, Lemma 1 shows that the
above problem can be solved exactly in a distributed way, by harnessing the
principle of online ADMM [28]. Therefore, the proposed DOKL based on Lemma 1
can solve the optimization problem (9) in a distributed way while ensuring an
asymptotic optimality.

###### Lemma 1

The optimization problem in (10) can be solved in a distributed way, wherein
each learner $k$ only exchanges the $\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}$
and $\hat{\hbox{\boldmath$\theta$}}_{[\ell,t,p]}$ with its neighbors
$\ell\in{\cal N}_{k}$. Given parameters $\eta_{l}>0$ and $\rho>0$, the
corresponding updates at the learner $k$ are given as

$\displaystyle\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}=\operatornamewithlimits{argmin}_{\hbox{\boldmath$\theta$}_{k}}{\cal
L}(\hbox{\boldmath$\theta$}_{k}^{{\sf T}}{\bf z}_{p}({\bf
x}_{k,t}),y_{k,t})+\hat{\hbox{\boldmath$\lambda$}}_{[k,t,p]}^{{\sf
T}}\hbox{\boldmath$\theta$}_{k}$
$\displaystyle+\frac{\rho}{2}\sum_{\ell\in{\cal
N}_{k}}\left\|\hbox{\boldmath$\theta$}_{k}-\frac{\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}+\hat{\hbox{\boldmath$\theta$}}_{[\ell,t,p]}}{2}\right\|^{2}+\frac{\eta_{l}}{2}\|\hbox{\boldmath$\theta$}_{k}-\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}\|^{2},$
(11)
$\displaystyle\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]}=\hat{\hbox{\boldmath$\lambda$}}_{[k,t,p]}+\frac{\rho}{2}\sum_{\ell\in{\cal
N}_{k}}(\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hat{\hbox{\boldmath$\theta$}}_{[\ell,t+1,p]}).$
(12)

###### Proof:

The proof is provided in Appendix A. ∎

Note that a regularization parameter $\rho$ can control the tradeoff between
the loss and discrepancy (i.e., constraint violation). The rationale to choose
the hyper-parameters $\eta_{l}$ and $\rho$ of DOKL will be provided in Section
IV via theoretical analysis. From Lemma 1, at time $t$, every learner
$k\in{\cal V}$ performs the following procedures in parallel:

  * •

The learner $k$ stores the latest estimates
$\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}$ and
$\hat{\hbox{\boldmath$\lambda$}}_{[k,t,p]}$ at the previous time.

  * •

Using them, it locally updates the parameter
$\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}$ by solving the optimization
problem (11). See Remark 1 for the case of quadratic loss function.

  * •

Then, it transmits the $\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}$ to and
receives $\\{\hat{\hbox{\boldmath$\theta$}}_{[\ell,t+1,p]}:\ell\in{\cal
N}_{k}\\}$ from the neighbors.

  * •

Leveraging updated estimates, the learner $k$ updates the discrepancy
$\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]}$ locally.

The above procedures are summarized in Algorithm 1.

###### Remark 1

Suppose that the quadratic loss function is used:

$\displaystyle{\cal L}(\hbox{\boldmath$\theta$}^{{\sf T}}{\bf z}({\bf
x}_{t}),y_{t})=(\hbox{\boldmath$\theta$}^{{\sf T}}{\bf z}({\bf
x}_{t})-y_{t})^{2}.$ (13)

In this case, the closed-form solution of (11) is obtained as

$\displaystyle\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}$
$\displaystyle=\Big{(}2{\bf z}({\bf x}_{k,t}){\bf z}({\bf x}_{k,t})^{{\sf
T}}+(\eta_{l}+\rho|{\cal N}_{k}|){\bf I}\Big{)}^{-1}$
$\displaystyle\times\left(2y_{k,t}{\bf z}({\bf
x}_{k,t})+\eta_{l}\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}+\rho\hat{\hbox{\boldmath$\gamma$}}_{[k,t,p]}-\hat{\hbox{\boldmath$\lambda$}}_{[k,t,p]}\right),$

where $\hat{\hbox{\boldmath$\gamma$}}_{[k,t,p]}=\sum_{\ell\in{\cal
N}_{k}}(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}+\hat{\hbox{\boldmath$\theta$}}_{[\ell,t,p]})/2$.
This closed-form expression will be used for our experiments in Section V.

Algorithm 1 DOKL (at the learner $k\in{\cal V}$)

1:Input: Network ${\cal G}=({\cal V},{\cal E})$, a preselected kernel
$\kappa_{p}$, and hyper-parameters $(\rho,\eta_{l},M)$.

2:Output: A sequence of functions $\hat{f}_{k,t}({\bf x}),\;t\in[T+1]$.

3:Initialization: $\hat{\hbox{\boldmath$\theta$}}_{[k,1,p]}={\bf 0}$ and
$\hat{\hbox{\boldmath$\lambda$}}_{[k,1,p]}={\bf 0}$. Each learner constructs
the identical random feature map ${\bf z}_{p}(\cdot)$ with the same seed.

4:Iteration: $t=1,...,T$

  * •

Receive a streaming data $({\bf x}_{k,t},y_{k,t})$.

  * •

Construct ${\bf z}_{p}({\bf x}_{k,t})$ via (5) using the kernel $\kappa_{p}$.

  * •

Update $\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}$ from (11).

  * •

Transmit $\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}$ to and receive
$\hat{\hbox{\boldmath$\theta$}}_{[\ell,t+1,p]}$ from the neighbors
$\ell\in{\cal N}_{k}$.

  * •

Update $\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]}$ via (12).

###  III-B The Proposed DOMKL

The proposed DOKL in Section III-A has an inevitable limitation of using a
predetermined single kernel. This problem can be even worse in an online
learning framework as the single kernel should be determined without observing
a sequential data. Thus, it is required to extend DOKL into a multiple kernel
setting. Motivated by this, we propose a distributed online multiple kernel-
based online learning (DOMKL). Hereinafter, it is assumed that there are $P$
kernels in a kernel dictionary. Under RF approximation, each kernel $p$ is
specified by a kernel-dependent mapping ${\bf z}_{p}({\bf x})$ in (52), for
$p\in[P]$. It is remarkable that we will not formulate an optimization for
DOMKL (i.e., online ADMM formulation for the parameters of a multiple kernel-
based function in (14)), since the resulting optimization seems to be quite
complex. Instead, we resort to a simpler two-step approach, wherein the
parameters of $P$ local functions and their combination weights are optimized
separately. It will be proved in Section IV that our approach can guarantee an
order-optimal performance. Then, the proposed DOMKL is performed with the
following two steps.

i) Local step: In this step, each learner $k$ optimizes the parameters of $P$
kernel functions (denoted by
$\\{\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}:p\in[P]\\}$) independently from
each other. Given a kernel $\kappa_{p}$, such optimization has been already
solved in Section III-A, namely, $\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}$
is obtained via (11). From this, every kernel $k$ can simply obtain the
updated parameters of the $P$ kernel functions.

ii) Global step: In this step, each learner $k$ seeks the best function
approximation $\hat{f}_{[k,t+1]}({\bf x})$ by combining its kernel functions
$\\{\hat{f}_{[k,t+1,p]}({\bf x}),p\in[P]\\}$ with proper weights
$\\{\hat{q}_{[k,t+1,p]},p\in[P]\\}$:

$\hat{f}_{[k,t+1]}({\bf
x})=\sum_{p=1}^{P}\hat{q}_{[k,t+1,p]}\hat{f}_{[k,t+1,p]}({\bf x}),$ (14)

where $\sum_{p=1}^{P}\hat{q}_{[k,t+1,p]}=1$ with
$\hat{q}_{[k,t+1,p]}\in[0,1]$. Thus, we need to optimize the combination
weights so that they can capture the reliabilities of the $P$ kernels. Based
on the principle of exponential strategy (or Hedge algorithm) [26], each
learner $k$ determines the weights $\\{\hat{q}_{[k,t+1,p]}:p\in[P]\\}$ on the
basis of its own and neighbors’ past losses. Towards this, we first define the
accumulated losses of the learner $k$: for $p\in[P]$,

$\hat{w}_{[k,t+1,p]}=\exp\left(-\frac{1}{\eta_{g}}\sum_{\tau=1}^{t}{\cal
L}(\hat{f}_{[k,\tau,p]}({\bf x}_{k,\tau}),y_{k,\tau})\right),$ (15)

with some learning rate $\eta_{g}>0$. Combining with
$\\{\hat{w}_{[\ell,t+1,p]}:\ell\in{\cal N}_{k}\\}$ (provided by the
neighbors), the weights are computed as

$\hat{q}_{[k,t+1,p]}=\frac{\hat{w}_{[k,t+1,p]}\times\prod_{\ell\in{\cal
N}_{k}}\hat{w}_{[\ell,t+1,p]}}{\sum_{p=1}^{P}\hat{w}_{[k,t+1,p]}\times\prod_{\ell\in{\cal
N}_{k}}\hat{w}_{[\ell,t+1,p]}}.$ (16)

The learned function in (14) with the above optimized parameters will be used
to estimate the label $\hat{y}_{k,t+1}$ of a newly incoming data ${\bf
x}_{k,t+1}$, i.e.,

$\hat{y}_{k,t+1}=\hat{f}_{[k,t+1]}({\bf x}_{k,t+1}).$ (17)

The procedures of DOMKL are summarized in Algorithm 2.

###### Remark 2

We will verify that the proposed weight-update in (16) is performed in a
network-wise, thus enabling to satisfy the consensus constraint. From the
update rule in (16), we can have:

$\displaystyle\hat{w}_{[k,t+1,p]}\times\prod_{\ell\in{\cal
N}_{k}}\hat{w}_{[\ell,t+1,p]}=\exp\left(-\frac{1}{\eta_{g}}L_{[k,t+1,p]}\right),$

where the accumulated losses $L_{[k,t+1,p]}$ can be expressed as

$\displaystyle L_{[k,t+1,p]}$ $\displaystyle=\sum_{\tau=1}^{t}{\cal
L}(\hat{f}_{[k,\tau,p]}({\bf x}_{k,\tau}),y_{k,\tau})$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;+\sum_{\ell\in{\cal
N}_{k}}\sum_{\tau=1}^{t}{\cal L}(\hat{f}_{[\ell,\tau,p]}({\bf
x}_{\ell,\tau}),y_{\ell,\tau}).$ (18)

The second term in (18) captures the reliability of the kernel $p$ on the
basis of the local data of neighboring learners.

###### Remark 3

When a network graph ${\cal G}$ forms an acyclic graph, the combination
weights can be further elaborated by exploiting the principle of message-
passing [29]. Specifically, for acyclic networks, the weights can be updated
using the local data of all connected learners. Before stating the update
rule, some useful definitions are first provided. We say that two learners are
connected with a length $\zeta$ if there exists an undirected path of length
$\zeta$ between these nodes. Also, let ${\cal N}_{k}^{(\zeta)}$ be the index
set containing the length-$\zeta$ connected learners of the learner $k$, i.e.,
${\cal N}_{k}^{(\zeta)}=\\{\ell\in{\cal V}:\mbox{there exists a length-$\zeta$
path between the learners $k$ and $\ell$}\\}$, where ${\cal N}_{k}^{(1)}={\cal
N}_{k}$. Harnessing the principle of message-passing, the message transmitted
from the learner $k$ to its neighbors $\ell\in{\cal N}_{k}$ is determined as

$m_{k\rightarrow\ell,t+1}=\hat{w}_{[k,t+1,p]}\times\prod_{i\in{\cal
N}_{k}:i\neq\ell}m_{i\rightarrow k,t}$ (19)

with initial values $m_{i\rightarrow k,1}=1$ for all $\\{i,k\\}\in{\cal E}$.
Accordingly, the weights in the learner $k$ are updated using the incoming
messages $\\{m_{\ell\rightarrow k,t}:\ell\in{\cal N}_{k}\\}$ such as

$\hat{q}_{[j,t+1,p]}=\frac{\hat{w}_{[j,t+1,p]}\times\prod_{\ell\in{\cal
N}_{k}}m_{\ell\rightarrow
k,t}}{\sum_{p=1}^{P}\hat{w}_{[k,t+1,p]}\times\prod_{\ell\in{\cal
N}_{k}}m_{\ell\rightarrow k,t}},$ (20)

for some parameter $\eta_{g}>0$. This update rule can guarantee that the
information of local losses can be propagated over the entire network as a
time (or iteration) $t$ grows, which is manifested as follows:

$\hat{w}_{[k,t+1,p]}\times\prod_{\ell\in{\cal N}_{k}}m_{\ell\rightarrow
k,t}=\exp\left(-\frac{1}{\eta_{g}}L_{[k,t+1,p]}\right),$ (21)

where the accumulated losses are computed as

$\displaystyle L_{[k,t+1,p]}$ $\displaystyle=\sum_{\tau=1}^{t}{\cal
L}(\hat{f}_{[k,\tau,p]}({\bf x}_{k,\tau}),y_{k,\tau})$
$\displaystyle\;\;\;+\sum_{\zeta=1}^{t-1}\sum_{\ell\in{\cal
N}_{k}^{(\zeta)}}\sum_{\tau=1}^{t-\zeta}{\cal L}(\hat{f}_{[\ell,\tau,p]}({\bf
x}_{\ell,\tau}),y_{\ell,\tau}).$ (22)

This message-passing update can be used even for cyclic graphs, provided that
the girth of a network graph ${\cal G}$ is larger than the number of incoming
data $T$. Otherwise, some local losses can be reflected because of the
duplication.

###### Remark 4

Definitely, our approach in Section III-B can be naturally applied to another
single kernel-based algorithm (named RFF-DOKL) proposed in [25]. Then, the
difference is in the underlying distributed optimization methods.
Specifically, online ADMM is used in the proposed DOKL while RFF-DOKL is based
on online gradient descent (OGD and a diffusion strategy. Although such
extension would be straightforward with respect to algorithm, it requires an
more effort to prove the asymptotic optimality of the resulting method. The
proof is quite demanding and left for an interesting future work.

Algorithm 2 DOMKL (at the learner $k\in{\cal V}$)

1:Input: Network ${\cal G}=({\cal V},{\cal E})$, a preselected set of $P$
kernels $\kappa_{p}$, $p\in[P]$ and hyper-parameters
$(\rho,\eta_{l},\eta_{g},M)$.

2:Output: A sequence of functions $\hat{f}_{[k,t]}({\bf x})$, $t\in[T+1]$.

3:Initialization: $\hat{\hbox{\boldmath$\theta$}}_{[k,1,p]}={\bf 0}$,
$\hat{\hbox{\boldmath$\lambda$}}_{[k,1,p]}={\bf 0}$ and
$\hat{w}_{[k,1,p]}=1,\forall p\in[P]$. Each learner constructs the identical
random feature map ${\bf z}_{p}(\cdot)$, $\forall p\in[P]$ with the same seed.

4:Iteration: $t=1,...,T$

  * •

Receive a streaming data $({\bf x}_{k,t},y_{k,t})$.

  * •

Construct ${\bf z}_{p}({\bf x}_{k,t})$ via (5) for $\kappa_{p},\forall
p\in[P]$.

  * •

Update $\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}$ via (11) for $\forall
p\in[P]$.

  * •

Update $\hat{w}_{[k,t+1,p]}$ via (15) for $\forall p\in[P]$.

  * •

Transmit
$\\{\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]},\hat{w}_{[k,t+1,p]}\\}$ to and
receive
$\\{\hat{\hbox{\boldmath$\theta$}}_{[\ell,t+1,p]},\hat{w}_{[\ell,t+1,p]}\\}$
from the neighbors $\forall\ell\in{\cal N}_{k}$, for $\forall p\in[P]$.

  * •

Update $\hat{q}_{[k,t+1,p]}$ via (16).

  * •

Update $\hat{\hbox{\boldmath$\lambda$}}_{[j,t+1,p]}$ via (12).

  * •

Update $\hat{f}_{[k,t+1]}({\bf
x})=\sum_{p=1}^{P}\hat{q}_{[k,t+1,p]}\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}^{{\sf
T}}{\bf z}_{p}({\bf x})$.

##  IV Regret Analysis

In this section, we analyze the performances of the proposed DOKL and DOMKL in
terms of learning accuracy and constraint violation (i.e., discrepancy). These
cumulative regrets are commonly used for the analysis of online distributed
optimizations [28]. Let $\hat{f}_{[k,t]}$ denote the estimated function of the
learner $k$. Also, let $f_{k}^{\star}$ denote the optimal function in terms of
the incoming data at the learner $k$, namely,

$f_{k}^{\star}=\operatornamewithlimits{argmin}_{f\in\bar{{\cal
H}}}\sum_{t=1}^{T}{\cal L}(f({\bf x}_{k,t}),y_{k,t}),$ (23)

subject to the consensus constraint $f_{k}^{\star}=f_{\ell}^{\star}$ for
$\forall k\in{\cal V},\ell\in{\cal N}_{k}$. For the assumption of a connected
graph ${\cal G}=({\cal V},{\cal E})$, the consensus constraint implies that
$f_{k}^{\star}=f^{\star}$ for all $k\in{\cal V}$. As in [28], the cumulative
regrets for learning accuracy and consensus violation (or discrepancy) at the
node $k$ are respectively defined as

$\displaystyle{\rm regret}_{\rm a}^{k}(T)$ $\displaystyle=\sum_{t=1}^{T}{\cal
L}(\hat{f}_{[k,t]}({\bf x}_{k,t}),y_{k,t})-{\cal L}\left(f_{k}^{\star}({\bf
x}_{k,t}),y_{k,t}\right)$ $\displaystyle{\rm regret}_{\rm d}^{k}(T)$
$\displaystyle=\sum_{t=1}^{T}\left[\sum_{\ell\in{\cal
N}_{k}}\hat{f}_{[k,t]}({\bf x}_{k,t})-\hat{f}_{[\ell,t]}({\bf
x}_{k,t})\right]^{2}.$

From now on, we will prove that the proposed DOKL and DOMKL can achieve the
optimal sublinear regrets ${\cal O}(\sqrt{T})$ for both learning accuracy and
discrepancy. Namely, as $T\rightarrow\infty$, DOKL and DOMKL can achieve
negligible gaps from the associated optimal performances. We remark that in
general, the optimal performance of DOMKL is likely to be much better than
that of DOKL, because of the advantage of using multiple kernels. Before
stating our main results, some useful notations and definitions will be
provided. Recall that in the proposed methods in Section III, each kernel
function $\hat{f}_{[k,t,p]}$ is represented as

$\hat{f}_{[k,t,p]}({\bf x})=\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}^{{\sf
T}}{\bf z}_{p}({\bf x}).$ (24)

For ease of exposition, given the data $({\bf x}_{k,t},y_{k,t})$, the loss
function with respect to $\theta$ is defined as

${\cal L}_{[k,t,p]}(\hbox{\boldmath$\theta$})={\cal
L}(\hbox{\boldmath$\theta$}^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t}).$
(25)

Hereinafter, the above two notations will be used interchangeably. Let
$\hbox{\boldmath$\theta$}_{[k,p]}^{\star}$ be the parameter of an optimal
kernel function in the kernel $\kappa_{p}$, i.e.,

$\hbox{\boldmath$\theta$}_{[k,p]}^{\star}=\operatornamewithlimits{argmin}_{\hbox{\boldmath$\theta$}}\sum_{t=1}^{T}{\cal
L}_{[k,t,p]}(\hbox{\boldmath$\theta$}),\forall k\in{\cal V}.$ (26)

subject to the consensus constraint in (10). As noticed before, when ${\cal
G}=({\cal V},{\cal E})$ is a connected graph, we have that
$\hbox{\boldmath$\theta$}_{p}^{\star}=\hbox{\boldmath$\theta$}^{\star}_{[k,p]}$
for all $k\in{\cal V}$. For our analysis, the following conditions are
assumed:

  * •

(a1) For any fixed ${\bf z}_{p}({\bf x}_{k,t})$ and $y_{k,t}$, the loss
function ${\cal L}_{[k,t,p]}(\hbox{\boldmath$\theta$})$ is convex with respect
to $\theta$, differentiable, and bounded as ${\cal
L}_{[k,t,p]}(\hbox{\boldmath$\theta$})\in[0,L_{u}]$. Also, its gradient is
bounded, i.e., $\|\nabla{\cal L}_{[k,t,p]}(\hbox{\boldmath$\theta$})\|^{2}\leq
G$.

  * •

(a2) For any kernel $\kappa_{p}$, $\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}$
belongs to a bounded set $\Theta_{p}\subseteq\mbox{\bb R}^{2D\times 1}$, i.e.,
$\|\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}\|^{2}\leq C$.

  * •

(a3) For any time $t$, ${\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]})-{\cal
L}_{[k,t,p]}(\hbox{\boldmath$\theta$}_{[k,p]}^{\star})\geq-B$ for some
positive constant $B$.

  * •

(a4) For any fixed $k\in{\cal V}$ and $p\in[P]$, there exists a sequence of
$\epsilon_{t}$’s such that
$|\hat{q}_{[k,t,p]}-\hat{q}_{[\ell,t,p]}|\leq\epsilon_{t}$ for all
$\ell\in{\cal N}_{k}$ and $\sum_{t=1}^{T}\epsilon_{t}^{2}\leq{\cal
O}(\sqrt{T})$.

The assumptions (a1) and (a2) are generally required for the analysis of
online learning setting [22, 23, 30, 28]. Also, the assumption (a3) is
required to prove the sublinear regret of constraint violation (i.e.,
discrepancy), which is true if convex functions are bounded from below or
Lipschitz continuous [28]. The assumption (a4) is required for the proof of
Theorem 2, which implies that the degree of heterogeneity of distributed local
data is bounded and thus results in a bounded loss (e.g., ${\cal O}(\sqrt{T})$
of the proposed DOMKL. In fact, the upper-bound $\epsilon_{t}$ is determined
on the basis of network structure (i.e., the connectivity of nodes in the
network). For example, when the network is a complete graph, we can easily
obtain the $\epsilon_{t}=0$ for all $t\in[T]$. Obviously, as the connectivity
of a network becomes sparse, $\epsilon_{t}$ tends to increase. Via numerical
tests, we have confirmed that the assumption (a4) might not be tight, i.e., it
can be easily satisfied in practical network structures.

We first state the main results of this section in Theorems 1 and 2 below, and
the proofs will be provided in Sections IV-A and IV-B.

###### Theorem 1

Under the assumptions (a1) \- (a3), DOKL in Algorithm 1 with the parameters
$\rho=\eta_{l}={\cal O}(\sqrt{T})$ and any preselected kernel $\kappa_{p}$ can
achieve the sublinear regrets as

$\displaystyle{\rm regret}_{\rm a}^{k}(T)$
$\displaystyle\;=\sum_{t=1}^{T}{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]})-\sum_{t=1}^{T}{\cal
L}_{[k,t,p]}(\hbox{\boldmath$\theta$}_{[k,p]}^{\star})\leq{\cal O}(\sqrt{T}),$
$\displaystyle{\rm regret}_{\rm d}^{k}(T)$
$\displaystyle\;=\sum_{t=1}^{T}\left[\sum_{\ell\in{\cal
N}_{k}}\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}^{{\sf T}}{\bf z}_{p}({\bf
x}_{j,t})-\hat{\hbox{\boldmath$\theta$}}_{[\ell,t,p]}^{{\sf T}}{\bf
z}_{p}({\bf x}_{j,t})\right]^{2}\leq{\cal O}(\sqrt{T}).$

for any learner $k\in{\cal V}$.

###### Proof:

The proof is provided in Section IV-A. ∎

###### Theorem 2

Under the assumptions (a1) \- (a4), DOMKL in Algorithm 2 with the parameters
$\rho=\eta_{l}=\eta_{g}={\cal O}(\sqrt{T})$ and kernels
$\\{\kappa_{p}:p\in[P]\\}$ can achieve the sublinear regrets as

$\displaystyle{\rm regret}_{\rm a}^{k}(T)$ $\displaystyle=\sum_{t=1}^{T}{\cal
L}\left(\sum_{p=1}^{P}\hat{q}_{[k,t,p]}\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}{\bf
z}_{p}({\bf x}_{k,t}),y_{k,t}\right)$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;-\min_{1\leq
p\leq P}\sum_{t=1}^{T}{\cal
L}_{[k,t,p]}(\hbox{\boldmath$\theta$}_{[k,p]}^{\star})\leq{\cal O}(\sqrt{T}),$
$\displaystyle{\rm regret}_{\rm d}^{k}(T)$
$\displaystyle=\sum_{t=1}^{T}\left[\sum_{\ell\in{\cal
N}_{k}}\left(\sum_{p=1}^{P}\hat{q}_{[k,t,p]}\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}^{{\sf
T}}{\bf z}_{p}({\bf x}_{k,t})\right.\right.$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left.\left.-\sum_{p=1}^{P}\hat{q}_{[\ell,t,p]}\hat{\hbox{\boldmath$\theta$}}_{[\ell,t,p]}^{{\sf
T}}{\bf z}_{p}({\bf x}_{j,t})\right)\right]^{2}\leq{\cal O}(\sqrt{T}),$

for any learner $k\in{\cal V}$.

###### Proof:

The proof is provided in Section IV-B. ∎

Theorem 1 and Theorem 2 reveal that DOKL and DOMKL can achieve the optimal
sublinear regret bounds when compared with the respective best functions in
hindsight. However, it is noticeable that the best functions as to DOMKL and
DOKL are from $\bar{{\cal H}}={\cal H}_{1}+\cdots+{\cal H}_{P}$ and ${\cal
H}_{p}\subseteq\bar{{\cal H}}$ for a preselected $p\in[P]$, respectively. In
this regards, with a sufficiently large number of kernels, DOMKL can have a
potential gain over DOKL.

###  IV-A Proof of Theorem 1

Let $\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}$ and
$\hat{\hbox{\boldmath$\lambda$}}_{[k,t,p]}$ be the output of the proposed DOKL
(in Algorithm 1). We first derive the useful lemma:

###### Lemma 2

For any learner $k\in{\cal V}$, letting
$\hat{\hbox{\boldmath$\gamma$}}_{[k,t,p]}=\sum_{\ell\in{\cal
N}_{k}}(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}+\hat{\hbox{\boldmath$\theta$}}_{[\ell,t,p]})/2$,
we obtain the upper-bound::

$\displaystyle{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]})-{\cal
L}_{[k,t,p]}(\hbox{\boldmath$\theta$}_{[k,p]}^{\star})$
$\displaystyle\leq\frac{1}{2\rho}(\|\hat{\hbox{\boldmath$\lambda$}}_{[k,t,p]}\|^{2}-\|\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]}\|^{2})-\frac{\rho}{2}\|\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hat{\hbox{\boldmath$\gamma$}}_{[k,t,p]}\|^{2}$
$\displaystyle+\frac{\eta_{l}}{2}(\|\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2}-\|\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2})$
$\displaystyle-\frac{\eta_{l}}{2}(\|\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]})-\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}\|^{2})$
$\displaystyle+\frac{\rho}{2}(\|\hat{\hbox{\boldmath$\gamma$}}_{[k,t,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2}-\|\hat{\hbox{\boldmath$\gamma$}}_{[k,t+1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2}).$
(27)

###### Proof:

The proof is provided in Appendix B. ∎

We are now ready to prove Theorem 1.

(a) The proof of learning accuracy: From the convexity of the loss function,
we obtain the following inequality:

$\displaystyle{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]})-{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]})$
$\displaystyle\leq\left\langle\nabla{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}),\;\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}-\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}\right\rangle$
$\displaystyle=\left\langle\frac{1}{\sqrt{\eta_{l}}}\nabla{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}),\;\sqrt{\eta_{l}}(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}-\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]})\right\rangle$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{1}{2\eta_{l}}\|\nabla{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]})\|^{2}+\frac{\eta_{l}}{2}\|\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}-\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}\|^{2},$
(28)

where (a) is due to the Fenchel-Young inequality [31]. From (27) and (28), we
can get:

$\displaystyle{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]})-{\cal
L}_{[k,t,p]}(\hbox{\boldmath$\theta$}_{[k,p]}^{\star})$
$\displaystyle\leq\frac{1}{2\rho}(\|\hat{\hbox{\boldmath$\lambda$}}_{[k,t,p]}\|^{2}-\|\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]}\|^{2})+\frac{1}{2\eta_{l}}\|\nabla{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]})\|^{2}$
$\displaystyle+\frac{\rho}{2}(\|\hat{\hbox{\boldmath$\gamma$}}_{[k,t,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2}-\|\hat{\hbox{\boldmath$\gamma$}}_{[k,t+1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2})$
$\displaystyle+\frac{\eta_{l}}{2}(\|\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2}-\|\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2}).$

From the above inequality and the telescoping sum, we have:

$\displaystyle\sum_{t=1}^{T}{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]})-{\cal
L}_{[k,t,p]}(\hbox{\boldmath$\theta$}_{[k,p]}^{\star})$
$\displaystyle\leq\frac{1}{2\rho}(\|\hat{\hbox{\boldmath$\lambda$}}_{[k,1,p]}\|^{2}-\|\hat{\hbox{\boldmath$\lambda$}}_{[k,T+1,p]}\|^{2})$
$\displaystyle+\frac{\rho}{2}(\|\hat{\hbox{\boldmath$\gamma$}}_{[k,1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2}-\|\hat{\hbox{\boldmath$\gamma$}}_{[k,T+1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2})$
$\displaystyle+\frac{1}{2\eta_{l}}\sum_{t=1}^{T}\|\nabla{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]})\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{\rho}{2}\|\hat{\hbox{\boldmath$\gamma$}}_{[k,1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2}+\frac{1}{2\eta_{l}}\sum_{t=1}^{T}\|\nabla{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]})\|^{2},$ (29)

where (a) is due to the fact $\hat{\hbox{\boldmath$\lambda$}}_{[k,1,p]}={\bf
0}$, $\|\hat{\hbox{\boldmath$\lambda$}}_{[k,T+1,p]}\|^{2}\geq 0$, and
$\|\hat{\hbox{\boldmath$\gamma$}}_{[k,T+1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2}\geq
0$. Finally, from the assumptions (a1) and (a2), we can get:

$\displaystyle\sum_{t=1}^{T}{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]})-{\cal
L}_{[k,t,p]}(\hbox{\boldmath$\theta$}_{[k,p]}^{\star})\leq\frac{\rho
C}{2}+\frac{TG}{2\eta_{l}}.$ (30)

Setting $\rho=\eta_{l}={\cal O}(\sqrt{T})$, we can verify that DOKL (in
Algorithm 1) achieves the sublinear regret, which completes the proof of the
part (a).

(b) The proof of consensus violation: We first obtain the following upper-
bound:

$\displaystyle\left[\sum_{\ell\in{\cal
N}_{k}}\left(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}^{{\sf T}}{\bf
z}_{p}({\bf x}_{k,t})-\hat{\hbox{\boldmath$\theta$}}_{[\ell,t,p]}^{{\sf
T}}{\bf z}_{p}({\bf x}_{k,t})\right)\right]^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\left\|\sum_{\ell\in{\cal
N}_{k}}\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}-\hat{\hbox{\boldmath$\theta$}}_{[\ell,t,p]}\right\|^{2}\Big{\|}{\bf
z}_{p}({\bf x}_{k,t})\Big{\|}^{2}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\left\|\sum_{\ell\in{\cal
N}_{k}}\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}-\hat{\hbox{\boldmath$\theta$}}_{[\ell,t,p]}\right\|^{2},$
(31)

where (a) follows the Cauchy-Schwartz inequality and (b) is due to the fact
that $\|{\bf z}_{p}({\bf x}_{k,t})\|_{2}^{2}\leq 1$ from (5). Also, the
following inequality is obtained:

$\displaystyle\left\|\sum_{\ell\in{\cal
N}_{k}}\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}-\hat{\hbox{\boldmath$\theta$}}_{[\ell,t,p]}\right\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{4}{\rho^{2}}\left\|\hat{\hbox{\boldmath$\lambda$}}_{[k,t,p]}-\hat{\hbox{\boldmath$\lambda$}}_{[k,t-1,p]}\right\|^{2}=4\left\|\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}-\hat{\hbox{\boldmath$\gamma$}}_{[k,t,p]}\right\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}4\left\|\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hat{\hbox{\boldmath$\gamma$}}_{[k,t,p]}\right\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\frac{8B}{\rho}+\frac{4}{\rho^{2}}(\|\hat{\hbox{\boldmath$\lambda$}}_{[k,t,p]}\|^{2}-\|\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]}\|^{2})$
$\displaystyle+4(\|-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}+\hat{\hbox{\boldmath$\gamma$}}_{[k,t,p]}\|^{2}-\|-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}+\hat{\hbox{\boldmath$\gamma$}}_{[k,t+1,p]}\|^{2})$
$\displaystyle+\frac{2\eta_{l}}{\rho}(\|\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2}-\|\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2}),$
(32)

where (a) is due to the fact that
$\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hat{\hbox{\boldmath$\gamma$}}_{[k,t+1,p]}=\frac{1}{\rho}(\hat{\hbox{\boldmath$\lambda$}}_{[k,t,p]}-\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]})$,
(b) follows the [28, Lemma 3], and (c) is from the rearrangement of (27) in
Lemma 2 and using the assumption (a3). From (31) and (32), and using the
telescoping sum, we can get:

$\displaystyle{\rm Regret}_{\rm
d}^{k}(T)=\sum_{t=1}^{T}\left[\sum_{\ell\in{\cal N}_{k}}\hat{f}_{[k,t,p]}({\bf
x}_{k,t})-\hat{f}_{[\ell,t,p]}({\bf x}_{k,t})\right]^{2}$
$\displaystyle\leq\sum_{t=1}^{T}\left\|\sum_{\ell\in{\cal
N}_{k}}\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hat{\hbox{\boldmath$\theta$}}_{[\ell,t+1,p]}\right\|^{2}$
$\displaystyle\leq\frac{8BT}{\rho}+4\|\hat{\hbox{\boldmath$\gamma$}}_{[k,1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2}+\frac{2\eta_{l}}{\rho}\|\hat{\hbox{\boldmath$\theta$}}_{[k,1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2}$
$\displaystyle\leq\frac{8BT}{\rho}+4C+\frac{4\eta_{l}}{\rho}C.$ (33)

Setting $\rho=\eta_{l}={\cal O}(\sqrt{T})$, the sublinear regret is achieved,
which completes the proof.

###  IV-B Proof of Theorem 2

We prove the sublinear regrets of DOMKL in Algorithm 2.

(a) The proof of learning accuracy: We first give the key lemma:

###### Lemma 3

Setting $\eta_{g}={\cal O}(\sqrt{T})$ and using the weights in (16), the
following sublinear regret is achieved:

$\displaystyle\sum_{t=1}^{T}{\cal
L}\left(\sum_{p=1}^{P}\hat{q}_{[k,t,p]}\hat{f}_{[k,t,p]}({\bf
x}_{k,t}),y_{k,t}\right)$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;-\min_{1\leq p\leq
P}\sum_{t=1}^{T}{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]})\leq{\cal
O}(\sqrt{T}),$ (34)

for any learner $k\in{\cal V}$.

###### Proof:

The proof is provided in Appendix C. ∎

From Theorem 1, we know that for any kernel $p\in[P]$,

$\displaystyle\sum_{t=1}^{T}{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]})-{\cal
L}_{[k,t,p]}(\hbox{\boldmath$\theta$}_{[k,p]}^{\star})\leq{\cal O}(\sqrt{T}).$
(35)

By integrating (35) and (34), the proof is completed.

(b) The proof of consensus violation: We first obtain the following upper-
bound on the discrepancy at time $t$:

$\displaystyle\left[\sum_{\ell\in{\cal
N}_{k}}\left(\sum_{p=1}^{P}\hat{q}_{[k,t,p]}\hat{f}_{[k,t,p]}({\bf
x}_{k,t})-\sum_{p=1}^{P}\hat{q}_{[\ell,t,p]}\hat{f}_{[\ell,t,p]}({\bf
x}_{k,t})\right)\right]^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}2\sum_{p=1}^{P}\hat{q}_{[k,t,p]}^{2}\left[\sum_{\ell\in{\cal
N}_{k}}\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}^{{\sf T}}{\bf z}_{p}({\bf
x}_{j,t})-\hat{\hbox{\boldmath$\theta$}}_{[\ell,t,p]}^{{\sf T}}{\bf
z}_{p}({\bf x}_{j,t})\right]^{2}$ $\displaystyle+2D_{t}$ $\displaystyle\leq
2\sum_{p=1}^{P}\hat{q}_{[k,t,p]}^{2}\left\|\sum_{\ell\in{\cal
N}_{k}}\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}-\hat{\hbox{\boldmath$\theta$}}_{[\ell,t,p]}\right\|^{2}+2D_{t},$
(36)

where (a) is due to the fact that $(A+B)^{2}\leq 2(A^{2}+B^{2})$ and

$\displaystyle D_{t}=\left[\sum_{\ell\in{\cal
N}_{k}}\sum_{p=1}^{P}\Big{(}\hat{q}_{[k,t,p]}-\hat{q}_{[\ell,t,p]}\Big{)}\hat{\hbox{\boldmath$\theta$}}_{[\ell,t,p]}{\bf
z}_{p}({\bf x}_{k,t})\right]^{2}.$ (37)

From (36), we obtain the following upper-bound:

$\displaystyle{\rm Regret}_{d}^{k}(T)$ $\displaystyle\;\;\leq
2\sum_{p=1}^{P}\hat{q}_{[k,t,p]}^{2}\sum_{t=1}^{T}\left\|\sum_{\ell\in{\cal
N}_{k}}\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}-\hat{\hbox{\boldmath$\theta$}}_{[\ell,t,p]}\right\|^{2}+2\sum_{t=1}^{T}D_{t}$
$\displaystyle\;\;\stackrel{{\scriptstyle(a)}}{{\leq}}2\sum_{p=1}^{P}\hat{q}_{[k,t,p]}^{2}\left(\frac{8BT}{\rho}+4C+\frac{4\eta_{l}}{\rho}C\right)+2\sum_{t=1}^{T}D^{t}$
$\displaystyle\;\;\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{16BT}{\rho}+8C+\frac{8\eta_{l}}{\rho}C+2\sum_{t=1}^{T}D_{t},$
(38)

where (a) is from (33) and (b) is due to the fact that
$\sum_{p=1}^{P}\hat{q}_{[k,t,p]}^{2}\leq 1$. Also, we have that

$\displaystyle\sum_{t=1}^{T}D_{t}$
$\displaystyle\leq\sum_{t=1}^{T}\epsilon_{t}^{2}\sum_{p=1}^{P}\sum_{\ell\in{\cal
N}_{k}}\left\|\hat{\hbox{\boldmath$\theta$}}_{[\ell,t,p]}\right\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}|{\cal
N}_{k}|CP\sum_{t=1}^{T}\epsilon_{t}^{2}\stackrel{{\scriptstyle(b)}}{{\leq}}{\cal
O}(\sqrt{T}),$ (39)

where (a) is from the assumption (a2) and (b) is from the assumption (a4).
From (38) and (39), and setting $\rho=\eta_{l}={\cal O}(\sqrt{T})$, the
sublinear regret of discrepancy is achieved, which completes the proof.

##  V Experiments

In this section, we verify the effectiveness of the proposed DOMKL via
experiments on various online regression and time-series prediction tasks with
real datasets. In particular, the superiority of DOMKL will be demonstrated by
showing stable performances on various online learning tasks and network
structures (e.g., network connectivity and size), and the great advantage of
using multiple kernels. A least-square loss function, which has been widely
used in the above learning tasks [22, 23, 25], is assumed:

${\cal L}(\hbox{\boldmath$\theta$}^{{\sf T}}{\bf z}_{p}({\bf
x}_{t}),y_{t})=(y_{t}-\hbox{\boldmath$\theta$}^{{\sf T}}{\bf z}_{p}({\bf
x}_{t}))^{2}.$ (40)

For the sake of comparison, we construct a centralized approach based on OMKL
in [22, 23], which is named COMKL. In this method, at time $t$, every learner
$k\in{\cal V}$ transmits its local data $({\bf x}_{k,t},y_{k,t})$ (or the
associated local gradient $\nabla{\cal
L}(\hat{\hbox{\boldmath$\theta$}}_{[t,p]}^{{\sf T}}{\bf z}_{p}({\bf
x}_{k,t}),y_{k,t})$) to a central server. Using them, the central server
learns a common function $\hat{f}_{t+1}({\bf
x})=\sum_{p=1}^{P}\hat{q}_{[t+1,p]}\hat{f}_{[t+1,p]}({\bf x})$ via [23,
Algorithm 1] with a modified local step. This modification is required as the
central server observes the $K$ labeled data at every time, whereas in OMKL
[22, 23], one labeled data arrives. Then, the central server broadcasts the
estimated function $\hat{f}_{t+1}(\cdot)$ to all $K$ nodes. This method can be
regarded as a centralized federated learning based on multiple kernels.
Obviously, COMKL reduces to OMKL when $K=1$. Specifically, in the modified
local step, the parameter of each kernel function $\hat{f}_{[t+1,p]}$
(parameterized by $\hat{\hbox{\boldmath$\theta$}}_{[t+1,p]}$) is updated via
mini-batch OGD with the batch size $K$:

$\hat{\hbox{\boldmath$\theta$}}_{[t+1,p]}=\hat{\hbox{\boldmath$\theta$}}_{[t,p]}-\frac{\eta_{l}}{K}\sum_{k=1}^{K}\nabla{\cal
L}(\hat{\hbox{\boldmath$\theta$}}_{[t,p]}^{{\sf T}}{\bf z}_{p}({\bf
x}_{k,t}),y_{k,t}).$ (41)

We remark that the learning accuracy of COMKL can be regarded as the
performance limit (or the lower bound) of all possible multiple kernel-based
distributed online learning algorithms (including our DOMKL). Definitely the
other kernel-based learning algorithms (e.g., online multiple kernel
regression [20], online multiple kernel learning with a budget [15], and so
on) can be incorporated into the above centralized framework. However, they
are excluded for comparisons since their performances are much worse than
COMKL, as expected from the numerical results in [23] and references therein.
Also, we consider the state-of-the-art kernel-based distributed online
learning algorithm (named RFF-DOKL) [25]. As far as we know, RFF-DOKL is the
only kernel-based algorithm suitable for our distributed online learning
framework with continuous streaming data. As explained in Section I, the other
kernel-based distributed learning algorithms were not customized in online
learning, thus being lack of scalability with respect to the number of
incoming data. In summary, the following online learning algorithms will be
used for our experiments:

  * •

COMKL: The centralized online multiple kernel-based learning algorithm, which
is the variant of OMKL [22, 23] with the modified local step in (41). Note
that the underlying optimization techniques are based on OGD and a Hedge
algorithm.

  * •

RFF-DOKL: The distributed online single kernel-based learning algorithm, which
is developed based on OGD and a diffusion strategy [25]. (Gaussian kernel with
$\sigma^{2}$).

  * •

DOKL : The proposed distributed online single kernel-based learning algorithm,
which is based on online ADMM and a distributed Hedge algorithm. (Gaussian
kernel with $\sigma^{2}$).

  * •

DOMKL: The proposed distributed online multiple kernel-based learning
algorithm, where the kernel dictionary consists of the $17$ Gaussian kernels
(i.e., $P=17$) with the parameters (called bandwidths)

$\sigma_{p}^{2}=10^{\frac{p-9}{2}},~{}p=1,\dots,17.$ (42)

For RFF-DOKL and DOKL, the bandwidth of a Gaussian kernel (i.e, $\sigma^{2}$)
will be specified when they are used.

TABLE I: Performance comparisons of MSE ($\times 10^{-2}$) and CV ($\times 10^{-2}$) as a function of the parameters $\eta_{g}$ and $\rho$. ($K=10$ and $\alpha_{c}=0.25$).  $\eta_{g}$ | $\rho$ | Conductivity | Weather
---|---|---|---
MSE | CV | MSE | CV
10 | 10 | 5.23 | 3.11 | 0.41 | 0.25
10 | 100 | 4.78 | 1.10 | 0.49 | 0.19
10 | 1000 | 4.98 | 0.46 | 0.86 | 0.21
100 | 10 | 5.68 | 2.77 | 0.55 | 0.28
100 | 100 | 4.93 | 0.95 | 0.66 | 0.23
100 | 1000 | 5.27 | 0.46 | 1.16 | 0.25

We investigate the performances of the above algorithms in terms of learner-
wise and network-wise aspects. They are measured by learning accuracy and
consensus violation, respectively. Recall that
$\hat{y}_{k,t}=\hat{f}_{[k,t]}({\bf x}_{k,t})$ and $y_{k,t}$ stand for an
estimated label and a true label at time $t$ in the learner $k$, where
$\hat{f}_{[k,t]}$ is generated at time $t-1$ via Algorithm 1 (resp. Algorithm
2) for the proposed DOKL (resp. DOMKL). Through the experiments, it is assumed
that communication graphs in our experiments are connected. This assumption
does not violate the generality as the proposed algorithms can be
straightforwardly applied to each connected component in parallel if a
communication graph is not connected.

i) Learning accuracy: We evaluate the accuracy of a learned function with
respect to the associated local data, which is measured by the mean-square-
error (MSE) as

$\mbox{MSE}(t)=\frac{1}{tK}\sum_{\tau=1}^{t}\sum_{k=1}^{K}(\hat{f}_{[k,\tau]}({\bf
x}_{k,\tau})-y_{k,\tau})^{2},$

with the initial value $\mbox{MSE}(1)=1$. It is well matched to our loss
function in (40). However, this metric alone is not sufficient as it could not
reflect a network-wise performance (i.e., the closeness of learned functions).
We address this problem by introducing the following second metric.

ii) Consensus violation: Since a communication graph is assumed to be
connected, every learner in the network aims at learning a common function. By
taking this into account, the network-wise consensus is measured as

$\displaystyle\mbox{CV}(t)=$
$\displaystyle\frac{1}{tK(K-1)}\sum_{\tau=1}^{t}\sum_{k=1}^{K}\sum_{\ell=1:\ell\neq
k}^{K}(\hat{f}_{[k,\tau]}({\bf x}_{k,\tau})-\hat{f}_{[\ell,\tau]}({\bf
x}_{k,\tau}))^{2},$

with the initial value $\mbox{CV}(1)=1$.

To capture the impact of network structures, in our experiments, we consider a
random communication graph consisting of $K$ nodes (or learners). This graph
is constructed by starting with a set of $K$ isolated nodes and adding
successive edges between them randomly according to a connection probability
$\alpha_{c}\in(0,1]$. Consequently, every learner in the network can have
$\alpha_{c}K$ neighboring learners in average. Due to the randomness of the
learning algorithms (e.g., COMKL, RFF-DOKL, DOKL, and DOMKL) and a
communication graph, the averaged MSE and CV performances over $500$ trials
are evaluated. On constructing a random communication graph, it might be
possible that the resulting graph is not connected. This sample is removed
(i.e., not counted in $500$ trials). In the proposed DOKL and DOMKL (i.e.,
Algorithm 1 and Algorithm 2), the following hyper-parameters are used:

$\rho=100,\;\eta_{l}=10,\;\eta_{g}=10,\;\text{and}~{}M=50.$ (43)

In fact, $\eta_{l}$ has little impact on the performances, whereas $\rho$ and
$\eta_{g}$ can control the tradeoff between learning accuracy and consensus
violation, as provided in Table I. For instance, if $\rho$ is large, the
network tends to build a strong consensus at the expense of accuracy-
performance losses at learners. Unfortunately, the optimal choices of $\rho$
and $\eta_{g}$ rely on the both target MSE and CV performances, and datasets.
In real-world online learning tasks, it might not be tractable to optimize
these parameters because of the sequential nature of incoming data. Such
optimization is an interesting open problem even in the simpler centralized
setting [23], which is beyond the scope of this paper. In all datasets, we
used the hyper-parameters in (43), which is determined on the basis of the
results in Table I. The datasets to be used for the experiments are given in
Section V-A, and the experimental results and some discussions are provided in
Section V-B.

TABLE II: Summary of Real Datasets for Experiments Regression task
---
Datasets | # of features | # of data | feature type
Weather | 21 | 7750 | real
Conductivity | 81 | 11000 | real
Wave energy | 48 | 9500 | real
Twitter | 77 | 98704 | real & integer
Time series prediction task
Datasets | # of features | # of data | feature type
Air quality | 13 | 7322 | real
Traffic | 5,10 | 6500 | real
Temperature | 5,10 | 5500 | real

###  V-A Descriptions of online learning tasks and datasets

We describe online regression and time-series prediction tasks and real-world
datasets for the experiments.

####  V-A1 Online regression tasks

For these tasks, we consider the following real datasets from UCI Machine
Learning Repository, which are also summarized in Table II:

  * •

Weather [32] : The dataset contains 7750 samples obtained from LDAPS model
operated by the Korea Meteorological Administration during 2015-2017, where
the features show the geographical variables of Seoul. The goal is to predict
the minimum temperature of next day.

  * •

Conductivity [33] : The dataset contains 11000 samples of extracted from
superconductors, where each feature in ${\bf x}_{t}\in\mbox{\bb R}^{81}$
represents critical information to construct superconductor such as density
and mass of atoms. The purpose is to predict the critical temperature which
creates superconductor.

  * •

Wave energy [34] : This dataset contains 9500 samples consisted of positions
and absorbed power obtained from wave energy converters (WECs) in four real
wave scenarios from the southern coast of Australia. The objective is to
predict the total power energy of the farm.

  * •

Twitter [35]: This dataset contains 98704 samples consisted of buzz events
from Twitter, where each attributes are used to predict the popularity of a
topic. Higher value indicates more popularity.

To build a distributed learning framework, the above data samples are
distributed to the $K$ nodes in the following way. The entire data samples are
partitioned into the $K$ parts of the equal size $T=\left\lfloor\mbox{the
total number of data}/K\right\rfloor$, where some remaining data samples can
be excluded. The resulting partition is denoted as $\\{{\cal D}_{1},...,{\cal
D}_{K}\\}$, where $|{\cal D}_{k}|=T,\forall K\in[K]$ and ${\cal
D}_{k}\cap{\cal D}_{\ell}=\phi$ for any $k,\ell\in{\cal V}$ with $k\neq\ell$.
Then, ${\cal D}_{k}=\\{({\bf x}_{k,t},y_{k,t}):t=1,...,T\\}$ is used as the
local dataset of the learner $k$ for $k\in{\cal V}$. At time $t$, each learner
$k$ receives the data $({\bf x}_{k,t},y_{k,t})$ from ${\cal D}_{k}$. Note that
although there are lots of possible partitions of the equal size $T$, they do
not affect the performances of the algorithms considered in the experiments.
In contrast, it is not true for time-series prediction tasks in the next
subsection.

(a) Conductivity data (b) Weather data (c) Wave energy data (d) Air quality
data

(e) Traffic data (f) Temperature data

Figure 1: Comparisons of MSE and CV performances of various methods in online
regression ((a) \- (c)) and time-series prediction ((d) \- (f)) tasks. Here, a
communication graph with $K=10$ learners is randomly constructed with a
connection probability $\alpha_{c}=0.25$.

####  V-A2 Time-series prediction tasks

For time-series prediction tasks, we consider the popular Autoregressive (AR)
model [36]. The AR($s$) model predicts the future value $y_{t}$ with the
assumption of the linear dependency on its past $s$ values, which is formally
defined as

$y_{t}=c+\sum_{i=1}^{s}\gamma_{i}y_{t-i}+n_{t},$ (44)

where $c$ is a constant, $\gamma_{i}$ denotes the weight associated with
$y_{t-i}$, and $n_{t}$ denotes a Gaussian noise. Based on this, the RF-based
kernelized AR($s$) model, which can explore a nonlinear dependency, has been
introduced in [23], where it is formulated as

$\displaystyle y_{t}$ $\displaystyle=c+f(y_{t-1},y_{t-2},\dots,y_{t-s})+n_{t}$
$\displaystyle=c+f({\bf x}_{t})+\epsilon_{t},$ (45)

where ${\bf x}_{t}\triangleq\left[y_{t-1},y_{t-2},\dots,y_{t-p}\right]^{{\sf
T}}$ and $f({\bf x}_{t})\in\bar{{\cal H}}$ (i.e., RKHS). In our experiments,
the parameter $s$ is fixed as 5. Then, the above model can be directly plugged
into the proposed and benchmark algorithms to solve time-series prediction
tasks. These algorithms are tested with the following univariate time-series
datasets from UCI Machine Learning Repository, which are also summarized in
Table II:

  * •

Air quality [37] : This dataset includes 7322 time-series air quality data,
where the features contain hourly response from an array of 5 metal oxide
chemical sensors embedded in an Air Quality multi-sensor device deployed on
the field in a city of Italy. The goal is to predict the concentration of
polluting chemicals in the air.

  * •

Traffic [38]: This dataset contains 6500 time-series traffic data obtained
from Minneapolis Department of Transportation in US. Data is collected from
hourly interstate 94 Westbound traffic volume for MN DoT ATR station 301.

  * •

Temperature [38]: This dataset includes 5500 time-series temperature data
obtained from Minneapolis Department of Transportation in US. Data is
collected from hourly interstate 94 Westbound temperature for MN DoT ATR
station 301, roughly midway between Minneapolis and St Paul, MN.

Unlike online regression tasks, the partition $\\{{\cal D}_{1},...,{\cal
D}_{K}\\}$ should keep the characteristic of a time-series data. This can be
satisfied by building the partition in the following way. Letting $\\{({\bf
x}_{t},y_{t}):t\in[KT]\\}$ be the time-series data in a dataset, it is
partitioned as ${\cal D}_{k}=\\{({\bf x}_{k,t}={\bf
x}_{K(t-1)+k},y_{k,t}=y_{K(t-1)+k}),t\in[T]\\}$ for $k\in{\cal V}$, where
$T=\left\lfloor\mbox{the total number of data}/K\right\rfloor$. Then, at time
$t$, each learner $k$ receives the data $({\bf x}_{k,t},y_{k,t})$ from ${\cal
D}_{k}$.

###  V-B Performance Evaluations

We demonstrate the advantage of using multiple kernels with the comparison
between DOMKL and the single kernel-based methods (e.g., DOKL and RFF-DOKL).
The proposed DOMKL is first compared with DOKL with the best kernel, in which
the best kernel was identified via an exhaustive search from the 17 Gaussian
kernels in (42), assuming that all incoming data is given in advance. As an
example, it turns out that the Gaussian kernel with $\sigma^{2}=10^{-2}$ is
the best kernel for the Wave energy data. We also confirmed that in this
dataset, DOMKL yields the same MSE and CV performances of DOKL with
$\sigma^{2}=10^{-2}$. The same results are also attained for the other
datasets in Section V-A. These experiments reveal that as in OMKL [23], the
proposed DOMKL can quickly find the best kernel in hindsight as the part of a
learning process. In other words, our extension approach from DOKL to DOMKL is
quite reasonable. We emphasize that in practice, it might be a chance to
select an unsuitable single kernel, thus leading to a severe performance loss.
This can be demonstrated via Fig. 1, where in both DOKL and RFF-DOKL, the
parameter of a Gaussian kernel is determined as either a higher bandwidth
$\sigma^{2}=10^{-3}$ or a lower bandwidth $\sigma^{2}=10^{3}$. In Fig. 1, the
averaged performances of the above two cases are evaluated, namely, during the
experiments, 250 trials with $\sigma^{2}=10^{-3}$ and the other 250 trials
with $\sigma^{2}=10^{3}$ are performed. Hence, the performance gaps from DOMKL
can be regarded as the performance loss in average caused by choosing an
unsuitable single kernel. From Fig. 1, we observe that the proposed DOMKL
shows the best MSE and CV performances in all datasets, by enjoying the great
advantage of using multiple kernels. Especially in the conductivity, weather,
and traffic data, the performance gains obtained from using multiple kernels
are tremendous. This suggests the practicality of the proposed DOMKL.

In comparison between DOKL and RFF-DOKL, we can identify the difference of
online ADMM and OGD-based diffusion strategy in the context of a distributed
optimization. From the MSE performances in Fig. 1, we observe that no
algorithm is overwhelmingly better, i.e., DOKL can outperform RFF-DOKL and
vice versa according to datasets. In contrast, DOKL shows better CV
performances than RFF-DOKL in all datasets, implying that online ADMM seems to
be more adequate for the network-wise consensus. Also, DOKL can be further
elaborated by adjusting the hyper-parameters $\rho$ and $\eta_{g}$, whereas
RFF-DOKL cannot. Nevertheless, it would be an interesting future work to
extend RFF-DOKL in a multiple kernel setting (see Remark 4), since RFF-DOKL
shows attractive performances in some datasets.

Finally, we investigate the robustness of the proposed DOMKL in terms of the
network scalability. From Fig. 2, we observe that DOMKL yields the almost same
MSE and CV performances regardless of the network size. Herein, a random
communication graph is considered with a connection probability
$\alpha_{c}=0.5$. These results reveal that DOMKL performs uniformly well for
various network sizes, thus being suitable for online learning tasks arising
from massive IoT systems. We point out that the CV performances in Fig. 2
become better as the network size $K$ grows. This is because by construction,
the number of neighboring learners can increase in average (e.g.,
$\alpha_{c}K$) as $K$ grows. Namely, as the network size increases, the
updated information at each learner is propagated over a network more quickly,
thus leading to a better consensus. Consider another type of a random
communication graph with a fixed $\alpha_{c}K$ regardless of $K$ (e.g.,
$\alpha_{c}=\frac{c}{k}$ for some constant $c$). Differently from the previous
case, the number of neighboring learners in average is fixed regardless of the
network size $K$. As expected, one can observe the opposite trends of CV
performances, compared with them in Fig. 1. More importantly, in the both
cases, we verified that CV values themselves are sufficiently small and also,
the gaps between the best and worst CV values are almost negligible. Fig. 1
shows that DOMKL provides the comparable MSE performances with COMKL, in which
the latter can be regarded as the lower bound. Namely, we can say that DOMKL
almost achieves the optimal distributed online learning algorithm based on
multiple kernels. Due to its attractive performance and the robustness on
various network structures, thus, the proposed DOMKL would be a promising
candidate for fully decentralized online learning tasks.

Figure 2: The MSE and CV performances of DOMKL and COMKL as a function of
network size $K$ on online regression task with Twitter dataset, where a
random communication graph is constructed with the connection probability
$0.5$.

##  VI Conclusion

In this paper, we proposed a novel distributed online learning framework with
multiple kernels (dubbed DOMKL). This method was devised by appropriately
combining online alternating direction method of multipliers (online ADMM) and
a distributed Hedge algorithm. The key advantages of the proposed DOMKL are
the scalability in terms of the number of incoming data and privacy-
preserving. As a theoretical contribution, we proved that the proposed DOMKL
achieves the optimal sublinear regret, implying that it can yield the same
asymptotic performance with the centralized OMKL, without centralizing the
local data. Via experiments with real datasets, we demonstrated the
effectiveness of the proposed DOMKL on various online regression and time-
series prediction tasks. The advantages of scalability, privacy-preserving,
and attractive performance suggest the practicability of DOMKL in real-world
distributed online learning tasks. An interesting future work is to extend the
proposed DOMKL into a more general communication network such as wireless and
directed communication networks. Regarding wireless communication networks,
the amount of exchanged information should be taken into account because of
the limited capacity of a wireless channel. Active learning would be useful as
it can only activate learners with an informative incoming data. This
definitely reduces the communication overhead as well as the labeling cost.
Another promising solution is to develop a quantized optimization technique
suitable for our learning framework. As a result, exchanging quantized
messages can reduce the communication overhead significantly.

##  Appendix A Proof of Lemma 1

For ease of exposition, we will drop the subscript $p$ as the proof holds for
any kernel $\kappa_{p}$. Accordingly, $\hat{\hbox{\boldmath$\theta$}}_{[t,p]}$
(resp., $\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}$) is replaced by
$\hat{\hbox{\boldmath$\theta$}}_{t}$ (resp.,
$\hat{\hbox{\boldmath$\theta$}}_{[k,t]}$). This proof is based on online ADMM
proposed in [28]. To formulate the standard form of online ADMM, we let

$\hbox{\boldmath$\theta$}_{[1:K]}\stackrel{{\scriptstyle\Delta}}{{=}}[\hbox{\boldmath$\theta$}_{1}^{{\sf
T}},\hbox{\boldmath$\theta$}_{2}^{{\sf
T}},\cdots,\hbox{\boldmath$\theta$}_{K}^{{\sf T}}]^{{\sf T}}\in\mbox{\bb
R}^{2MK\times 1},$

with $\hbox{\boldmath$\theta$}_{k}\in\mbox{\bb R}^{2M\times 1},\;\forall
k\in[K]$. Also, we introduce an auxiliary vector
$\hbox{\boldmath$\gamma$}_{\\{k,\ell\\}}\in\mbox{\bb R}^{2M\times 1}$ denotes
an auxiliary vector associated with an edge $\\{k,\ell\\}\in{\cal E}$. Then,
the optimization problem in (10) can be rewritten as

$\displaystyle\hat{\hbox{\boldmath$\theta$}}_{t+1}$
$\displaystyle=\operatornamewithlimits{argmin}_{\hbox{\boldmath$\theta$}_{[1:K]}}\sum_{k=1}^{K}{\cal
L}(\hbox{\boldmath$\theta$}_{k}^{{\sf T}}{\bf z}_{p}({\bf
x}_{k,t}),y_{k,t})+\frac{\eta_{l}}{2}\|\hbox{\boldmath$\theta$}_{[1:K]}-\hat{\hbox{\boldmath$\theta$}}_{t}\|^{2}$
$\displaystyle\mbox{ subject to }{\bf A}\hbox{\boldmath$\theta$}_{[1:K]}+{\bf
B}\hbox{\boldmath$\gamma$}={\bf 0},$ (46)

where ${\bf A}\in\mbox{\bb R}^{4M|{\cal E}|\times 2MK}$, ${\bf B}\in\mbox{\bb
R}^{4M|{\cal E}|\times 2M|{\cal E}|}$, and
$\hbox{\boldmath$\gamma$}=[\hbox{\boldmath$\gamma$}_{\\{k,\ell\\}}:\\{k,\ell\\}\in{\cal
E}]\in\mbox{\bb R}^{2M|{\cal E}|\times 1}$ are specified below. We will
explain how to determine the ${\bf A}$, ${\bf B}$, and $\gamma$ from a given
network ${\cal G}=({\cal V},{\cal E})$. Consider the simple graph ${\cal
G}(\\{1,2,3\\},\\{\\{1,2\\},\\{1,3\\}\\})$. Given the set ${\cal
E}=\\{\\{1,2\\},\\{1,3\\}\\}$, the auxiliary vector $\gamma$ is defined as

$\hbox{\boldmath$\gamma$}=[\hbox{\boldmath$\gamma$}_{\\{1,2\\}}^{{\sf
T}},\hbox{\boldmath$\gamma$}_{\\{1,3\\}}^{{\sf T}}]^{{\sf T}}.$

From the connectivity of the nodes, the matrices of ${\bf A}$ and ${\bf B}$
are determined as

$\displaystyle{\bf A}$ $\displaystyle=\left[\begin{matrix}{\bf I}_{2M}&{\bf
0}_{2M}&{\bf 0}_{2M}\\\ {\bf I}_{2M}&{\bf 0}_{2M}&{\bf 0}_{2M}\\\ {\bf
0}_{2M}&{\bf I}_{2M}&{\bf 0}_{2M}\\\ {\bf 0}_{2M}&{\bf 0}_{2M}&{\bf
I}_{2M}\end{matrix}\right]\mbox{ and }{\bf B}=-\left[\begin{matrix}{\bf
I}_{2M}&{\bf 0}_{2M}\\\ {\bf 0}_{2M}&{\bf I}_{2M}\\\ {\bf I}_{2M}&{\bf
0}_{2M}\\\ {\bf 0}_{2M}&{\bf I}_{2M}\end{matrix}\right],$ (47)

where ${\bf I}_{2M}$ and ${\bf 0}_{2M}$ represent the $2M\times 2M$ identify
and all-zero matrices, respectively. Then, it is clearly verified that the
consensus constraint in (46) is equivalent to that in (9) because

${\bf A}\hbox{\boldmath$\theta$}_{[1:3]}+{\bf
B}\hbox{\boldmath$\gamma$}=\left[\begin{matrix}\hbox{\boldmath$\theta$}_{1}-\hbox{\boldmath$\gamma$}_{\\{1,2\\}}\\\
\hbox{\boldmath$\theta$}_{1}-\hbox{\boldmath$\gamma$}_{\\{1,3\\}}\\\
\hbox{\boldmath$\theta$}_{2}-\hbox{\boldmath$\gamma$}_{\\{1,2\\}}\\\
\hbox{\boldmath$\theta$}_{3}-\hbox{\boldmath$\gamma$}_{\\{1,3\\}}\end{matrix}\right]={\bf
0}.$ (48)

As shown in (47), ${\bf A}$ and ${\bf B}$ are represented by simple block
matrices consisting of $2M\times 2M$ identify and zero matrices. For ease of
exposition, we let $(i,j)$ denote the indices of block-row of ${\bf A}$ with
$\\{i,j\\}=\\{j,i\\}\in{\cal E}$. In (47), we have the four block-rows whose
are indexed by $(1,2)$, $(1,3)$, $(2,1)$, and $(3,1)$ in that order. Also, the
block-columns of ${\bf A}$ are indexed by numbers as usual. The matrix ${\bf
A}$ is constructed by determining the locations of ${\bf I}_{2M}$ (i.e., non-
zero matrices), for which $((i,j),k)$-th element (e.g., a block matrix) is
equal to ${\bf I}_{2M}$ only if $k=i$. The matrix ${\bf B}$ can be easily
constructed using the circular shift of the first block-row ${\bf E}$, where

${\bf E}\stackrel{{\scriptstyle\Delta}}{{=}}-\left[\begin{matrix}{\bf
I}_{2M}&{\bf 0}_{2M}&\cdots&{\bf 0}_{2M}\end{matrix}\right]\in\mbox{\bb
R}^{2M\times|{\cal E}|}.$ (49)

In detail, the $i$-th block-row is obtained by the $i-1$ times circular shift
of ${\bf E}$ to the right.

The augmented Lagrangian of (46) is obtained as

$\displaystyle
L_{\rho}^{t}(\hbox{\boldmath$\theta$}_{[1:K]},\hbox{\boldmath$\gamma$},\hbox{\boldmath$\lambda$})$
$\displaystyle\;\;\;\;\;\;\;=\sum_{k=1}^{K}{\cal
L}(\hbox{\boldmath$\theta$}_{k}^{{\sf T}}{\bf z}_{p}({\bf
x}_{k,t}),y_{k,t})+\hbox{\boldmath$\lambda$}^{{\sf T}}({\bf
A}\hbox{\boldmath$\theta$}_{[1:K]}+{\bf B}\hbox{\boldmath$\gamma$})$
$\displaystyle\;\;\;\;\;\;\;+\frac{\eta_{l}}{2}\|\hbox{\boldmath$\theta$}_{[1:K]}-\hat{\hbox{\boldmath$\theta$}}_{t}\|^{2}+\frac{\rho}{2}\|{\bf
A}\hbox{\boldmath$\theta$}_{[1:K]}+{\bf B}\hbox{\boldmath$\gamma$}\|^{2}.$
(50)

Online ADMM, then, consists of the three steps [28]:

$\displaystyle\hat{\hbox{\boldmath$\theta$}}_{t+1}$
$\displaystyle=\operatornamewithlimits{argmin}_{\hbox{\boldmath$\theta$}_{[1:K]}}\sum_{k=1}^{K}{\cal
L}(\hbox{\boldmath$\theta$}_{k}^{{\sf T}}{\bf z}({\bf
x}_{k,t}),y_{k,t})+\hat{\hbox{\boldmath$\lambda$}}_{t}^{{\sf T}}({\bf
A}\hbox{\boldmath$\theta$}_{[1:K]}+{\bf B}\hat{\hbox{\boldmath$\gamma$}}_{t})$
$\displaystyle+\frac{\rho}{2}\|{\bf A}\hbox{\boldmath$\theta$}_{[1:K]}+{\bf
B}\hat{\hbox{\boldmath$\gamma$}}_{t}\|^{2}+\frac{\eta_{l}}{2}\|\hbox{\boldmath$\theta$}_{[1:K]}-\hat{\hbox{\boldmath$\theta$}}_{t}\|^{2},$
(51) $\displaystyle\hat{\hbox{\boldmath$\gamma$}}_{t+1}$
$\displaystyle=\operatornamewithlimits{argmin}_{\hbox{\boldmath$\gamma$}}\hat{\hbox{\boldmath$\lambda$}}_{t}^{{\sf
T}}({\bf A}\hat{\hbox{\boldmath$\theta$}}_{t+1}+{\bf
B}\hbox{\boldmath$\gamma$})+\frac{\rho}{2}\|{\bf
A}\hat{\hbox{\boldmath$\theta$}}_{t+1}+{\bf B}\hbox{\boldmath$\gamma$}\|^{2},$
(52) $\displaystyle\hat{\hbox{\boldmath$\lambda$}}_{t+1}$
$\displaystyle=\hat{\hbox{\boldmath$\lambda$}}_{t}+\rho({\bf
A}\hat{\hbox{\boldmath$\theta$}}_{t+1}+{\bf
B}\hat{\hbox{\boldmath$\gamma$}}_{t+1}).$ (53)

As shown in (48), we have that

${\bf A}\hbox{\boldmath$\theta$}_{[1:K]}+{\bf
B}\hat{\hbox{\boldmath$\gamma$}}_{t}=\left[\begin{matrix}{\bf c}_{1}\\\ {\bf
c}_{2}\\\ \vdots\\\ {\bf c}_{K}\end{matrix}\right]\mbox{ with }{\bf
c}_{k}=\left[\begin{matrix}\hbox{\boldmath$\theta$}_{k}-\hat{\hbox{\boldmath$\gamma$}}_{\\{k,k_{1}\\},t}\\\
\vdots\\\
\hbox{\boldmath$\theta$}_{k}-\hat{\hbox{\boldmath$\gamma$}}_{\\{k,k_{|{\cal
N}_{k}|}\\},t}\\\ \end{matrix}\right],$ (54)

where $\\{k_{\ell}$, $\ell\in{\cal N}_{k}\\}$ denote the indices of the
neighbors of the learner $k$. Also,
$\hat{\hbox{\boldmath$\lambda$}}_{(k,\ell),t}$ denotes the components of
$\hat{\hbox{\boldmath$\lambda$}}_{t}$ corresponding to the element
$\hbox{\boldmath$\theta$}_{k}-\hat{\hbox{\boldmath$\gamma$}}_{\\{k,\ell\\},t}$
in the ${\bf A}\hbox{\boldmath$\theta$}_{[1:K]}+{\bf
B}\hat{\hbox{\boldmath$\gamma$}}_{t}$. Similarly,
$\hat{\hbox{\boldmath$\lambda$}}_{(\ell,k),t}$ corresponds to
$\hbox{\boldmath$\theta$}_{\ell}-\hat{\hbox{\boldmath$\gamma$}}_{\\{k,\ell\\},t}$.
Note $(k,\ell)$ denotes the ordered pair while $\\{k,\ell\\}$ denotes the
unorderd pair. From (54) and using the above notations, the optimization
problem in (51) can be decomposed into $K$ sub-optimization problems, in which
the sub-optimization problem with respect to $\hbox{\boldmath$\theta$}_{k}$ is
formulated as

$\displaystyle\hat{\hbox{\boldmath$\theta$}}_{[k,t+1]}=\operatornamewithlimits{argmin}_{\hbox{\boldmath$\theta$}_{k}}{\cal
L}(\hbox{\boldmath$\theta$}_{k}^{{\sf T}}{\bf z}({\bf
x}_{k,t}),y_{k,t})+\hat{\hbox{\boldmath$\lambda$}}_{[k,t]}^{{\sf
T}}\hbox{\boldmath$\theta$}_{k}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;+\frac{\rho}{2}\sum_{\ell\in{\cal
N}_{k}}\|\hbox{\boldmath$\theta$}_{k}-\hat{\hbox{\boldmath$\gamma$}}_{\\{k,\ell\\},t}\|^{2}+\frac{\eta_{l}}{2}\|\hbox{\boldmath$\theta$}_{k}-\hat{\hbox{\boldmath$\theta$}}_{[k,t]}\|^{2},$
(55)

where $\hat{\hbox{\boldmath$\lambda$}}_{[k,t]}=\sum_{\ell\in{\cal
N}_{k}}\hat{\hbox{\boldmath$\lambda$}}_{(k,\ell),t}$. Likewise, the
optimization problem in (52) can be decomposed such as

$\displaystyle\hat{\hbox{\boldmath$\gamma$}}_{\\{k,\ell\\},t+1}$
$\displaystyle=\operatornamewithlimits{argmin}_{\hbox{\boldmath$\gamma$}_{\\{k,\ell\\}}}\hat{\hbox{\boldmath$\lambda$}}_{[k,t]}^{{\sf
T}}(\hat{\hbox{\boldmath$\theta$}}_{[k,t+1]}-\hbox{\boldmath$\gamma$}_{\\{k,\ell\\}})+\hat{\hbox{\boldmath$\lambda$}}_{[\ell,t]}^{{\sf
T}}(\hat{\hbox{\boldmath$\theta$}}_{[\ell,t+1]}-\hbox{\boldmath$\gamma$}_{\\{k,\ell\\}})$
$\displaystyle\;\;\;\;\;+\frac{\rho}{2}(\|\hat{\hbox{\boldmath$\theta$}}_{[k,t+1]}-\hbox{\boldmath$\gamma$}_{\\{k,\ell\\}}\|^{2}+\|\hat{\hbox{\boldmath$\theta$}}_{[\ell,t+1]}-\hbox{\boldmath$\gamma$}_{\\{k,\ell\\}}\|^{2}),$
(56)

for any $\\{k,\ell\\}\in{\cal E}$. The optimal solution of (56) can be easily
obtained as

$\displaystyle\hat{\hbox{\boldmath$\gamma$}}_{\\{k,\ell\\},t+1}=\frac{1}{2}(\hat{\hbox{\boldmath$\theta$}}_{[k,t+1]}+\hat{\hbox{\boldmath$\theta$}}_{[\ell,t+1]})+\frac{1}{2\rho}(\hat{\hbox{\boldmath$\lambda$}}_{(k,\ell),t}+\hat{\hbox{\boldmath$\lambda$}}_{(\ell,k),t}).$
(57)

Also, we obtain that

$\displaystyle\hat{\hbox{\boldmath$\lambda$}}_{(\ell,k),t+1}=\hat{\hbox{\boldmath$\lambda$}}_{(\ell,k),t}+\rho(\hat{\hbox{\boldmath$\theta$}}_{[\ell,t+1]}-\hat{\hbox{\boldmath$\gamma$}}_{\\{k,\ell\\},t+1})$
(58)
$\displaystyle\;\;\;\;\;\;\;\;=\frac{\rho}{2}(\hat{\hbox{\boldmath$\theta$}}_{[\ell,t+1]}-\hat{\hbox{\boldmath$\theta$}}_{[k,t+1]})+\frac{1}{2}(\hat{\hbox{\boldmath$\lambda$}}_{(\ell,k),t}-\hat{\hbox{\boldmath$\lambda$}}_{(k,\ell),t}).$
(59)

From (59), the following equality holds:

$\hat{\hbox{\boldmath$\lambda$}}_{(\ell,k),t}+\hat{\hbox{\boldmath$\lambda$}}_{(k,\ell),t}={\bf
0}.$ (60)

Also, from (57) and (60), we have:

$\displaystyle\hat{\hbox{\boldmath$\gamma$}}_{\\{k,\ell\\},t+1}$
$\displaystyle=\frac{1}{2}(\hat{\hbox{\boldmath$\theta$}}_{[k,t+1]}+\hat{\hbox{\boldmath$\theta$}}_{[\ell,t+1]}).$
(61)

By combining (61) and (55), we obtain the (11). From (58) and (61), we have:

$\hat{\hbox{\boldmath$\lambda$}}_{(k,\ell),t+1}=\hat{\hbox{\boldmath$\lambda$}}_{(k,\ell),t}+\frac{\rho}{2}(\hat{\hbox{\boldmath$\theta$}}_{[k,t+1]}-\hat{\hbox{\boldmath$\theta$}}_{[\ell,t+1]}).$
(62)

Thus, we can get:

$\displaystyle\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1]}$
$\displaystyle=\sum_{\ell\in{\cal
N}_{k}}\hat{\hbox{\boldmath$\lambda$}}_{(k,\ell),t+1}$
$\displaystyle=\hat{\hbox{\boldmath$\lambda$}}_{[k,t]}+\frac{\rho}{2}\sum_{\ell\in{\cal
N}_{k}}(\hat{\hbox{\boldmath$\theta$}}_{[k,t+1]}-\hat{\hbox{\boldmath$\theta$}}_{[\ell,t+1]}).$

This completes the proof.

##  Appendix B Proof of Lemma 2

From (11) and (12), the gradient of the loss function can be represented as

$\displaystyle\nabla{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]})$
$\displaystyle=-\Big{(}\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]}+\frac{\rho}{2}\sum_{\ell\in{\cal
N}_{k}}(\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}+\hat{\hbox{\boldmath$\theta$}}_{[\ell,t+1,p]})$
$\displaystyle\;\;\;\;-\frac{\rho}{2}\sum_{\ell\in{\cal
N}_{k}}(\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}+\hat{\hbox{\boldmath$\theta$}}_{[\ell,t,p]})+\eta_{l}(\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]})\Big{)}$
$\displaystyle=-\left(\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]}+\rho(\hat{\hbox{\boldmath$\gamma$}}_{[k,t+1,p]}-\hat{\hbox{\boldmath$\gamma$}}_{[k,t,p]})\right)$
$\displaystyle\;\;\;\;-\eta_{l}\left(\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}\right),$
(63)

where the last equality follows the definition of
$\hat{\hbox{\boldmath$\gamma$}}_{k,t}$. From the convexity of the loss
function, we obtain:

$\displaystyle{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]})-{\cal
L}_{[k,t,p]}(\hbox{\boldmath$\theta$}_{[k,p]}^{\star})$
$\displaystyle\leq\langle\nabla{\cal
L}_{[k,t,p]}(\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}),\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\rangle$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}-\langle\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]},\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\rangle$
$\displaystyle\;\;\;\;\;+\rho\langle-\hat{\hbox{\boldmath$\gamma$}}_{[k,t+1,p]}+\hat{\hbox{\boldmath$\gamma$}}_{[k,t,p]},\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\rangle$
$\displaystyle\;\;\;\;\;-\eta_{l}\langle\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]},\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\rangle,$
(64)

where (a) is from (63). Using the fact that

$\displaystyle\langle{\bf v}_{1}-{\bf v}_{2},{\bf v}_{3}+{\bf v}_{4}\rangle$
$\displaystyle=\frac{1}{2}(\|{\bf v}_{4}-{\bf v}_{2}\|^{2}-\|{\bf v}_{4}-{\bf
v}_{1}\|^{2}+\|{\bf v}_{3}+{\bf v}_{1}\|^{2}-\|{\bf v}_{3}+{\bf
v}_{2}\|^{2}),$

we obtain the following inequality:

$\displaystyle\langle-\hat{\hbox{\boldmath$\gamma$}}_{[k,t+1,p]}+\hat{\hbox{\boldmath$\gamma$}}_{[k,t,p]},\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\rangle$
$\displaystyle=\frac{1}{2}(\|-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}+\hat{\hbox{\boldmath$\gamma$}}_{[k,t,p]}\|^{2}-\|-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}+\hat{\hbox{\boldmath$\gamma$}}_{[k,t+1,p]}\|^{2}$
$\displaystyle+\|\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hat{\hbox{\boldmath$\gamma$}}_{[k,t+1,p]}\|^{2}-\|\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hat{\hbox{\boldmath$\gamma$}}_{[k,t,p]}\|^{2}).$
(65)

The following inequality is also satisfied:

$\displaystyle-\langle\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]},\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\rangle+\frac{\rho}{2}\|\hat{\hbox{\boldmath$\theta$}}_{j,t+1}-\hat{\hbox{\boldmath$\gamma$}}_{[k,t+1,p]}\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}-\langle\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]},\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\rangle$
$\displaystyle\;\;\;\;\;-\langle\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]},\hbox{\boldmath$\theta$}_{[k,p]}^{\star}-\hat{\hbox{\boldmath$\gamma$}}_{[k,t+1,p]}\rangle+\frac{\rho}{2}\|\hat{\hbox{\boldmath$\theta$}}_{j,t+1}-\hat{\hbox{\boldmath$\gamma$}}_{[k,t+1,p]}\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}-\frac{1}{\rho}\langle\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]},\hat{\hbox{\boldmath$\lambda$}}_{[k,t,p]}-\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]}\rangle$
$\displaystyle\;\;\;\;\;+\frac{1}{2\rho}\|\hat{\hbox{\boldmath$\lambda$}}_{[k,t,p]}-\hbox{\boldmath$\lambda$}_{[k,t+1,p]}\|^{2}$
$\displaystyle=\frac{1}{2\rho}(\|\hat{\hbox{\boldmath$\lambda$}}_{[k,t,p]}\|^{2}-\|\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]}\|^{2}),$
(66)

where (a) follows the fact that

$\langle\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]},\hbox{\boldmath$\theta$}_{[k,p]}^{\star}-\hat{\hbox{\boldmath$\gamma$}}_{[k,t+1,p]}\rangle\leq
0,$ (67)

which is shown in the proof of [28, Lemma 2] and (b) is due to the fact that

$\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hat{\hbox{\boldmath$\gamma$}}_{[k,t+1,p]}=\frac{1}{\rho}(\hat{\hbox{\boldmath$\lambda$}}_{[k,t,p]}-\hat{\hbox{\boldmath$\lambda$}}_{[k,t+1,p]}).$

Finally, we have:

$\displaystyle-\langle\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]},\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\rangle$
$\displaystyle=\frac{1}{2}\|\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2}-\frac{1}{2}\|\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hbox{\boldmath$\theta$}_{[k,p]}^{\star}\|^{2}$
$\displaystyle-\frac{1}{2}\|\hat{\hbox{\boldmath$\theta$}}_{[k,t+1,p]}-\hat{\hbox{\boldmath$\theta$}}_{[k,t,p]}\|^{2}.$
(68)

By integrating (64), (65), (66), and (68), we complete the proof.

##  Appendix C Proof of Lemma 3

We focus on any fixed $k\in{\cal V}$. Letting ${\cal
J}\stackrel{{\scriptstyle\Delta}}{{=}}\\{k\\}\cup\\{{\cal N}_{k}\\}$, we
define

$\zeta\stackrel{{\scriptstyle\Delta}}{{=}}\sum_{t=1}^{T}\log\left[\sum_{p=1}^{P}\hat{q}_{[k,t,p]}\exp\left(-\frac{1}{\eta_{g}}\sum_{j\in{\cal
J}}{\cal L}(\hat{f}_{[j,t,p]}({\bf x}_{j,t}),y_{j,t})\right)\right].$

The proof will be complete by deriving the upper and lower bounds of $\zeta$.
We first obtain the upper-bound:

$\displaystyle\zeta$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{t=1}^{T}\mbox{\bb
E}\left[\exp\left(-\frac{1}{\eta_{g}}\sum_{j\in{\cal J}}{\cal
L}(\hat{f}_{[j,t,I]}({\bf x}_{j,t}),y_{j,t})\right)\right]$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{j\in{\cal
J}}\left(\sum_{t=1}^{T}-\frac{1}{\eta_{g}}\mbox{\bb E}\left[{\cal
L}(\hat{f}_{[j,t,I]}({\bf x}_{j,t}),y_{j,t})\right]\right)+\frac{|{\cal
N}_{k}|TL_{u}^{2}}{8\eta_{g}^{2}},$ (69)

where (a) is due to the fact that $I$ denotes a random variable with the
probability mass function $(\hat{q}_{[k,t,1]},...,\hat{q}_{[k,t,P]})$ and (b)
follows the Hoeffding inequality with the bounded random variable ${\cal
L}(\hat{f}_{[j,t,I]}({\bf x}_{j,t}),y_{j,t})$ [27]. Letting
$\hat{W}_{[t,p]}\stackrel{{\scriptstyle\Delta}}{{=}}\hat{w}_{[k,t,p]}\cdot\prod_{\ell\in{\cal
N}_{k}}\hat{w}_{[\ell,t.p]}$, we derive the lower-bound on $\zeta$:

$\displaystyle\zeta$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{t=1}^{T}\log\left(\frac{\sum_{p=1}^{P}\hat{W}_{[t+1,p]}}{\sum_{p=1}^{P}\hat{W}_{[t,p]}}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\log\left(\sum_{p=1}^{P}\hat{W}_{[T+1,p]}\right)-\log\left(\sum_{p=1}^{P}\hat{W}_{[1,p]}\right)$
$\displaystyle=\log\left(\sum_{p=1}^{P}\hat{W}_{[T+1,p]}\right)-\log{P}$
$\displaystyle\geq-\frac{1}{\eta_{g}}\sum_{j\in{\cal J}}\left(\min_{1\leq
p\leq P}\sum_{t=1}^{T}{\cal L}(\hat{f}_{[j,t,p]}({\bf
x}_{j,t}),y_{j,t})\right)-\log{P},$ (70)

where (a) follows the definition of $\hat{q}_{[k,t,p]}$ and $\hat{W}_{[t,p]}$
and (b) is from the telescoping sum. From (69) and (70), we have:

$\displaystyle-\frac{1}{\eta_{g}}\sum_{j\in{\cal J}}\left(\min_{1\leq p\leq
P}\sum_{t=1}^{T}{\cal L}(\hat{f}_{[j,t,p]}({\bf
x}_{j,t}),y_{j,t})\right)-\log{P}$ $\displaystyle\leq\sum_{j\in{\cal
J}}\left(\sum_{t=1}^{T}-\frac{1}{\eta_{g}}\mbox{\bb E}\left[{\cal
L}(\hat{f}_{[j,t,I]}({\bf x}_{j,t}),y_{j,t})\right]\right)+\frac{|{\cal
N}_{k}|TL_{u}^{2}}{8\eta_{g}^{2}}.$

Rearranging the above inequality, we can get:

$\displaystyle\sum_{t=1}^{T}\mbox{\bb E}\left[{\cal L}(\hat{f}_{[k,t,I]}({\bf
x}_{k,t}),y_{k,t})\right]-\min_{1\leq p\leq P}\sum_{t=1}^{T}{\cal
L}(\hat{f}_{[k,t,p]}({\bf x}_{k,t}),y_{k,t})$
$\displaystyle\leq\sum_{\ell\in{\cal N}_{k}}\left[\min_{1\leq p\leq
P}\sum_{t=1}^{T}{\cal L}(\hat{f}_{[\ell,t,p]}({\bf
x}_{\ell,t}),y_{\ell,t})\right.$ $\displaystyle\left.-\sum_{t=1}^{T}\mbox{\bb
E}\left[{\cal L}\left(\hat{f}_{[\ell,t,I]}({\bf
x}_{\ell,t}),y_{\ell,t}\right)\right]\right]+\frac{|{\cal
N}_{k}|TL_{u}^{2}}{8\eta_{g}}+\eta_{g}\log{P}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{|{\cal
N}_{k}|TL_{u}^{2}}{8\eta_{g}}+\eta_{g}\log{P},$

where (a) follows the fact that for any $\ell\in{\cal V}$,

$\min_{1\leq p\leq P}\sum_{t=1}^{T}{\cal L}(\hat{f}_{[\ell,t,p]}({\bf
x}_{\ell,t}),y_{\ell,t})\leq\sum_{t=1}^{T}\mbox{\bb E}\left[{\cal
L}(\hat{f}_{[\ell,t,I]}({\bf x}_{\ell,t}),y_{\ell,t})\right].$

Finally, setting $\eta_{g}={\cal O}(\sqrt{T})$, the sublinear regret is
achieved, which completes the proof.

## Acknowledgment

This work was supported by the National Research Foundation of Korea(NRF)
grant funded by the Korea government(MSIT) (NRF-2020R1A2C1099836).

## References

  * [1] A.Zanella, N.Bui, A.Castellani and L.Vangelista and M.Zorzi, “Internet of things for smart cities,”, IEEE Internet of Things journal, vol. 1, no. 1, pp. 22–32, 2014.
  * [2] G. Bedi, G.K.Venayagamoorthy, R.Singh, R.R.Brooks, and K.-C.Wang, “Review of Internet of Things (IoT) in electric power and energy systems,” IEEE Internet of Things journal, vol. 5, no. 2, pp. 847–870, 2018.
  * [3] J.Shawe-Taylor, N.Cristianiniet al., “Kernel methods for pattern analysis”, Cambridge university press, 2004
  * [4] Y.-Y.Lin,T.-L.Liu, and C.-S.Fuh, “Multiple kernel learning for dimensionality reduction”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 6, pp. 1147–1160, 2010.
  * [5] X. Chen, Y. Gao, and R. Wang, “Online selective kernel-based temporal difference learning”, IEEE transactions on neural networks and learning systems, vol. 24, no. 12, pp. 1944–1956, 2013.
  * [6] A. Hard, K.Rao, R.Mathews, S.Ramaswamy, F.Beaufays, S.Augenstein, H. Eichner, C. Kiddon, and D.Ramage, “Federated learning for mobile keyboard prediction,” arXiv preprint arXiv :1811.03604, 2018
  * [7] F.Sattler, S. Wiedemann, K-R.M uller and W.Samek, “Robust and communication-efficient federated learning from non-iid data,” IEEE transactions on neural networks and learning systems, 2019.
  * [8] T.Li, A.K.Sahu, A.Talwalkar, and V.Smith, “Federated learning: Challenges, methods, and future directions,” IEEE Signal Processing Magazine, vol. 37, no. 3, pp. 50–60, 2020.
  * [9] M. E. Gursoy, A. Inan, M. E. Nergiz, and Y. Saygin, “Privacy-preserving learning analytics: challenges and techniques,” IEEE Transactions on Learning technologies, vol. 10, no. 1, pp. 68–81, 2016.
  * [10] B.-S. Shin, H. Paul, M. Yukawa, and A. Dekorsy, “Distributed nonlinear regression using in-network processing with multiple gaussian kernels,” in 2017 IEEE 18th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC). IEEE, 2017, pp. 1–5.
  * [11] W. Gao, J. Chen, C. Richard, and J. Huang, “Diffusion adaptation over networks with kernel least-mean-square,” in 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP). IEEE, 2015, pp. 217–220.
  * [12] B.-S. Shin, M. Yukawa, R.L.G. Cavalcante, and A. Dekorsy, “Distributed adaptive learning with multiple kernels in diffusion networks,” IEEE Transactions on Signal Processing, vol. 66, no. 21, pp. 5505–5519,2018.
  * [13] A. Lalitha, S. Shekhar, T. Javidi, and F. Koushanfar, “Fully decentralized federated learning,” in Third workshop on Bayesian Deep Learning (NeurIPS), 2018.
  * [14] C.Richard, J.C.M.Bermudez, and P.Honeine, “Online prediction of time series data with kernels,” IEEE Transactions on Signal Processing,vol. 57, no. 3, pp. 1058–1067, 2008.
  * [15] J.Kivinen, A.J.Smola, and R.C.Williamson, “Online learning with kernels,” IEEE transactions on signal processing, vol.52, no.8, pp.2165–2176, 2004.
  * [16] B.Scholkopf and A.J.Smola, “Learning with kernels: support vector machines, regularization, optimization, and beyond,” MIT press, 2001.
  * [17] S.Sonnenburg, G.Ratsch, C.Scafer, and B.Sholkopf, “Large scale multiple kernel learning,” The Journal of Machine Learning Research, vol. 7, pp. 1531–1565, 2006.
  * [18] M. Gonen and E.Alpaydın, “Multiple kernel learning algorithms,” Journal of machine learning research, vol.12, Jul, pp. 2211–2268,2011.
  * [19] S. Boyd, N. Parikh, and E. Chu, Distributed optimization and statistical learning via the alternating direction method of multipliers, Now Publishers Inc, 2011.
  * [20] D.Sahoo, S.C.Hoi, and B.Li, “Online multiple kernel regression,” in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 2014, pp. 293–302
  * [21] G. Wahba, “Spline models for observational data,” Siam, 1990, vol.59.
  * [22] Y. Shen, T. Chen, and G. B. Giannakis, “Random feature-based online multi-kernel learning in environments with unknown dynamics,” The Journal of Machine Learning Research, vol.20, no.1, pp. 773–808, 2019.
  * [23] S. Hong and J.Chae, “Active Learning with Multiple Kernels,” arXiv preprint arXiv:2005.03188, 2020.
  * [24] A. Rahimi and B.Recht, “Random features for large-scale kernel machines,” in Advances in neural information processing systems, 2008, pp. 1177–1184.
  * [25] P. Bouboulis, S. Chouvardas, and S. Theodoridis, “Online distributed learning over networks in RKH spaces using random fourier features,” IEEE Transactions on Signal Processing, vol. 66, no. 7, pp. 1920–1932,2017.
  * [26] S. Bubeck, “Introduction to online optimization,” Lecture Notes, vol. 2, 2011.
  * [27] M. J. Wainwright, High-dimensional statistics: A non-asymptotic view-point. Cambridge University Press, 2019, vol. 48.
  * [28] H. Wang and A. Banerjee, “Online alternating direction method (longer version),” arXiv preprint arXiv:1306.3721, 2013.
  * [29] M. Mezard and A.Montanari, Information, physics, and computation. Oxford University Press, 2009
  * [30] E. Hazanet al., “Introduction to online convex optimization,” Foundations and Trends in Optimization, vol. 2, no. 3-4, pp. 157–325, 2016.
  * [31] R.T.Rockafellar, Convex analysis, Princeton university press, 1970, no.28.
  * [32] J.D.Cho, C.Yoo and D.Cha, “Comparative assessment of various machine learning-based bias correction methods for numerical weather prediction model forecasts of extreme air temperatures in urban areas,” Earth and Space Science, 2020
  * [33] K.Hamidieh, “A data-driven statistical model for predicting the critical temperature of a superconductor,” Computational Materials Science, pp.346-354.
  * [34] M. M.Neshat, B.Alexander and Y.Xia, “A detailed comparison of meta-heuristic methods for optimising wave energy converter placements,” In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1318-1325.
  * [35] E.G.Francois, Kawala, Ahlame Douzal Chouakria and E. Dimert, “Predictions dactivite dans les reseaux sociaux en ligne,” 4i’eme Conference sur les Modeles et l’ Analyse des Reseaux: Approches Mathematiques et Informatiques, 2013.
  * [36] T. C. Mills, “Time series techniques for economists,” Cambridge University Press, 1991.
  * [37] M. L. S. De Vito, E. Massera and G. D. Francia, “On field calibration of an electronic nose for benzene estimation in an urban pollution monitoring scenario,” Sensors and Actuators B: Chemical, p. 750–757.
  * [38] https://archive.ics.uci.edu/ml/datasets/metro+interstate+traffic+volume.