# Graph-Aided Online Multi-Kernel Learning

Pouya M. Ghari, Yanning Shen P. M. Ghari and Y. Shen are with department of
Electrical Engineering and Computer Science, University of California, Irvine,
CA, USA. E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Multi-kernel learning (MKL) has been widely used in function approximation
tasks. The key problem of MKL is to combine kernels in a prescribed
dictionary. Inclusion of irrelevant kernels in the dictionary can deteriorate
accuracy of MKL, and increase the computational complexity. To improve the
accuracy of function approximation and reduce the computational complexity,
the present paper studies data-driven selection of kernels from the dictionary
that provide satisfactory function approximations. Specifically, based on the
similarities among kernels, the novel framework constructs and refines a graph
to assist choosing a subset of kernels. In addition, random feature
approximation is utilized to enable online implementation for sequentially
obtained data. Theoretical analysis shows that our proposed algorithms enjoy
tighter sub-linear regret bound compared with state-of-art graph-based online
MKL alternatives. Experiments on a number of real datasets also showcase the
advantages of our novel graph-aided framework.

##  1 Introduction

The need for function approximation arises in many machine learning studies
including regression, classification, and reinforcement learning, see e.g.,
(Chung et al., 2019). This paper studies supervised function approximation
where given data samples $\\{({\bm{x}}_{t},y_{t})\\}_{t=1}^{T}$, the goal is
to find the function $f(.)$, such that the difference between
$f({\bm{x}}_{t})$ and $y_{t}$ is minimized. In this context, kernel learning
methods exhibit reliable performance. Specifically, the function approximation
problem becomes tractable under the assumption that $f(.)$ belongs to a
reproducing kernel Hilbert space (Scholkopf and Smola, 2001). In some cases,
it is imperative to perform function approximation task in an online fashion.
For instance, when the volume of data is large and is collected in a
sequential fashion, it is impossible to store or process it in batch.
Furthermore, suffering from the well-known problem of ‘curse of
dimensionality’ (Bengio et al., 2006), kernel learning methods are not
suitable for sequential settings. This has motivated studies on online single
kernel learning (Lu et al., 2016; Bouboulis et al., 2018; Zhang and Liao,
2019) to address the curse of dimensionality. Specifically, approximating
kernels by finite-dimensional feature representations such as random Fourier
feature by Rahimi and Recht (2007) and Nyström method by Williams and Seeger
(2000), function approximation task becomes scalable.

Most of prior studies rely on a pre-selected kernel, however, such selection
requires prior information which may not be available. By contrast, utilizing
multiple kernels in a given dictionary in lieu of a pre-selected kernel
provides more flexible approach to obtain more accurate function
approximations as it can learn combination of kernels (Sonnenburg et al.,
2006). Enabled by the random feature approximation by Rahimi and Recht (2007),
online multi-kernel learning algorithms have been developed by Sahoo et al.
(2019); Shen et al. (2019); Ghari and Shen (2020).

One of the most important issues regarding multi-kernel learning is proper
selection of kernels to construct a dictionary. This affects both
computational complexity and accuracy of the function approximation
significantly. However, selecting an appropriate kernel dictionary requires
prior information and when such information is not available one solution is
to include a large number of kernels in the dictionary. In this case,
employing all kernels available in the dictionary may not be a feasible
choice. Data-driven selection of subset of kernels in a given dictionary can
alleviate the computational complexity. Furthermore, data-driven subset
selection of kernels can enhance the accuracy of function approximation by
pruning irrelevant kernels. Subset selection of kernels has been studied in
Ghari and Shen (2020) using a bipartite graph and the resulting algorithm. The
goal of the present paper is to select a subset of kernels in a given
dictionary at each time instant in order to alleviate the computational
complexity and improve function approximation accuracy. Specifically, based on
similarities between kernels a directed graph is constructed by which at each
time instant a subset of kernels is selected. In this case, function
approximations given by the chosen subset of kernels can be viewed as feedback
collected from a graph which is called feedback graph. The resulting algorithm
is called Similarity Feedback Graph based Multi-Kernel Learning (SFG-MKL). The
present paper proves that the proposed SFG-MKL achieves a sub-linear regret of
${\mathcal{O}}(T^{\frac{3}{4}})$ compared with
${\mathcal{O}}(T^{\frac{5}{6}})$ of OMKL-GF (Ghari and Shen, 2020).
Furthermore, an novel algorithm SFG-MKL-R is proposed which adaptively refines
the structure of the feedback graph based on the observed losses. The present
paper proves that the proposed SFG-MKL-R enjoys the sublinear regret of
${\mathcal{O}}(\sqrt{T})$ whereas it may need more computations in comparison
with the proposed SFG-MKL. Experiments on real datasets showcase the
effectiveness of our proposed SFG-MKL and SFG-MKL-R in comparison with other
online multi-kernel learning baselines.

##  2 Preliminaries

Given samples $({\bm{x}}_{1},{y}_{1}),\cdots,({\bm{x}}_{T},{y}_{T})$, with
${\bm{x}}_{t}\in{\mathbb{R}}^{d}$ and $y_{t}\in{\mathbb{R}}$, the function
approximation problem can be written as the following optimization problem

$\displaystyle\min_{f\in{\mathbb{H}}}\frac{1}{T}\sum_{t=1}^{T}{{\mathcal{C}}(f({\bm{x}}_{t}),y_{t})}+\lambda\Omega(\|f\|_{{\mathbb{H}}}^{2})$
(1)

where ${\mathcal{C}}(.,.)$ denotes the cost function, that is defined
according to the learning task. For example, in regression task
${\mathcal{C}}(.,.)$ can be least square function. In (1), $\lambda$ denotes
the regularization coefficient and $\Omega(.)$ represents a non-decreasing
function, which is used to prevent overfitting and control model complexity.
Let
$\kappa({\bm{x}},{\bm{x}}_{t}):{\mathbb{R}^{d}}\times{\mathbb{R}^{d}}\rightarrow\mathbb{R}$
represent a symmetric positive semidefinite basis function called kernel which
measures the similarity between ${\bm{x}}$ and ${\bm{x}}_{t}$. The representer
theorem states that the optimal solution of (1) can be expressed as follows
given finite data samples (Wahba, 1990)

$\displaystyle\hat{f}({\bm{x}})=\sum_{t=1}^{T}{\alpha_{t}\kappa({\bm{x}},{\bm{x}}_{t})}:=\bm{\alpha}^{\top}\bm{\kappa}({\bm{x}})$
(2)

where $\bm{\alpha}:=[{\alpha}_{1},...,{\alpha}_{T}]^{\top}$ denote the vector
of unknown coefficients to be estimated, and
$\bm{\kappa}({\bm{x}}):=[\kappa({\bm{x}},{\bm{x}}_{1}),\cdots,\kappa({\bm{x}},{\bm{x}}_{T})]^{\top}$.
Furthermore, it can be inferred that the dimension of $\bm{\alpha}$ increases
with the number of data samples $T$. This is known as ‘curse of
dimensionality’ (Wahba, 1990) and arises as a challenge to solve (1) in an
online fashion.

One way to deal with the increasing number of variables to be estimated is to
employ random feature (RF) approximation (Rahimi and Recht, 2007). Moreover,
the kernel $\kappa$ in (2) is shift-invariant which satisfy
$\kappa({\bm{x}}_{t},{\bm{x}}_{t^{\prime}})=\kappa({\bm{x}}_{t}-{\bm{x}}_{t^{\prime}})$.
However, relying on a pre-selected kernel often requires prior information
that may not be available. To cope with this, multi-kernel learning can be
exploited which learns the kernel as a combination of a sufficiently rich
dictionary of kernels $\\{\kappa_{i}\\}_{i=1}^{N}$. The kernel combination is
itself a kernel (Scholkopf, 2001). Let
$\kappa_{i}({\bm{x}}_{t}-{\bm{x}}_{t^{\prime}})$ be the $i$-th kernel in the
dictionary of $N$ kernels which is absolutely integrable. In this case, its
Fourier transform $\pi_{\kappa_{i}}(\bm{\psi})$ exists and can be viewed as
probability density function (PDF) if the kernel is normalized such that
$\kappa_{i}(\bm{0})=1$. Specifically, it can be written that

$\displaystyle\kappa_{i}({\bm{x}}_{t}-{\bm{x}}_{{t}^{\prime}})$
$\displaystyle=\int{\pi_{\kappa_{i}}(\bm{\psi}){e}^{j\bm{\psi}^{\top}({\bm{x}}_{t}-{\bm{x}}_{{t}^{\prime}})}}d\bm{\psi}:=\mathbb{E}_{\pi_{\kappa_{i}}(\bm{\psi})}[{e}^{j\bm{\psi}^{\top}({\bm{x}}_{t}-{\bm{x}}_{{t}^{\prime}})}].$
(3)

Let $\\{\bm{\psi}_{i,j}\\}_{j=1}^{D}$ be a set of vectors which are
independently and identically distributed (i.i.d) samples from
$\pi_{\kappa_{i}}(\bm{\psi})$. Hence,
$\kappa_{i}({\bm{x}}_{t}-{\bm{x}}_{{t}^{\prime}})$ can be approximated by the
ensemble mean
$\hat{\kappa}_{i,c}({\bm{x}}_{t}-{\bm{x}}_{{t}^{\prime}}):=\frac{1}{D}\sum_{i=1}^{D}{{e}^{j\bm{\psi}_{i,j}^{\top}({\bm{x}}_{t}-{\bm{x}}_{{t}^{\prime}})}}$.
Furthermore, the real part of
$\hat{\kappa}_{i,c}({\bm{x}}_{t}-{\bm{x}}_{{t}^{\prime}})$ also constitutes an
unbiased estimator of $\kappa_{i}({\bm{x}}_{t}-{\bm{x}}_{t^{\prime}})$ which
can be written as
$\hat{\kappa}_{i}({\bm{x}}_{t}-{\bm{x}}_{{t}^{\prime}})={\mathbf{z}}_{i}^{\top}({\bm{x}}_{t}){\mathbf{z}}_{i}({\bm{x}}_{{t}^{\prime}})$
(Rahimi and Recht, 2007), where

$\displaystyle{\mathbf{z}}_{i}({\bm{x}}_{t})=\frac{1}{\sqrt{D}}[$
$\displaystyle\sin(\bm{\psi}_{i,1}^{\top}{\bm{x}}_{t}),\cdots,\sin(\bm{\psi}_{i,D}^{\top}{\bm{x}}_{t}),\cos(\bm{\psi}_{i,1}^{\top}{\bm{x}}_{t}),\cdots,\cos(\bm{\psi}_{i,D}^{\top}{\bm{x}}_{t})].$

Replacing $\kappa_{i}({\bm{x}},{\bm{x}}_{t})$ with
$\hat{\kappa}_{i}({\bm{x}}-{\bm{x}}_{t})$, $\hat{f}({\bm{x}})$ in (2) can be
approximated as

$\displaystyle\hat{f}_{\text{RF},i}({\bm{x}})$
$\displaystyle=\sum_{t=1}^{T}{\alpha_{t}\hat{\kappa}_{i}({\bm{x}}-{\bm{x}}_{t})}=\sum_{t=1}^{T}{\alpha_{t}{\mathbf{z}}_{i}^{\top}({\bm{x}}){\mathbf{z}}_{i}({\bm{x}}_{t})}={\bm{\theta}}_{i}^{\top}{\mathbf{z}}_{i}({\bm{x}})$
(4)

where ${\bm{\theta}}_{i}\in{\mathbb{R}}^{2D}$ is a vector whose dimension does
not increase with the number of data samples. Therefore, utilizing RF
approximation can make the function approximation problem amenable for online
implementation. Furthermore, the loss of the $i$-th kernel can be calculated
as

$\displaystyle{\mathcal{L}}({\bm{\theta}}_{i}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})={\mathcal{C}}({\bm{\theta}}_{i}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})+\lambda\Omega(\|{\bm{\theta}}_{i}\|^{2}).$
(5)

Moreover, when multiple kernels are employed, function approximation can be
performed by functions in the form
$f({\bm{x}})=\sum_{i=1}^{N}{\bar{w}_{i}f_{i}({\bm{x}})}$ where
$\sum_{i=1}^{N}{\bar{w}_{i}}=1$ (Scholkopf, 2001). Also,
$f_{i}({\bm{x}})\in{\mathbb{H}}_{i}$ where ${\mathbb{H}}_{i}$ is an RKHS
induced by the kernel $\kappa_{i}$. Replacing $f_{i}({\bm{x}})$ with
$\hat{f}_{\text{RF},i}({\bm{x}})$, the function $f({\bm{x}})$ can be
approximated as

$\displaystyle\hat{f}_{\text{RF}}({\bm{x}})=\sum_{i=1}^{N}{\bar{w}_{i}\hat{f}_{\text{RF},i}({\bm{x}})},\sum_{i=1}^{N}{\bar{w}_{i}}=1.$
(6)

In this context, online convex optimization methods can be utilized to find
and update $\\{\bar{w}_{i}\\}_{i=1}^{N}$, $\\{{\bm{\theta}}_{i}\\}_{i=1}^{N}$
upon receiving new datum ${\bm{x}}_{t}$ at each time instant $t$ (Sahoo et
al., 2019; Shen et al., 2019; Ghari and Shen, 2020). However, using all
kernels in the dictionary may not be computationally efficient especially when
the dictionary of kernels is so large. Furthermore, by pruning the kernels
that do not provide approximations with satisfactory accuracy, the performance
of function approximation can be improved in terms of accuracy. Therefore, in
this paper, we propose a novel algorithm to choose a subset of kernels at each
time instant instead of using all kernels in the dictionary.

##  3 Online Multi-Kernel Learning with Feedback Graph

The present section first introduces a disciplined way to construct feedback
graph based on kernel similarities. Furthermore, a novel online MKL algorithm
is developed to select a subset of kernels based on the constructed feedback
graph, which is proved to obtain sub-linear regret.

###  3.1 Feedback Graph Construction

Selecting a subset of kernels for function approximation can decrease the
computational complexity of the learning task considerably, especially when
the number of kernels in a given dictionary is large. In this case, evaluation
of every kernel based learner may arise as a bottleneck. Therefore, this paper
aims at taking into account the similarities between existing kernels in the
given dictionary to avoid unnecessary computations. To this end, we will
construct a graph which models the similarities between kernels. At each time
instant $t$, a subset of kernels is chosen based on the graph.

The similarity between two shift invariant kernels $\kappa_{i}$ and
$\kappa_{j}$ is measured through the function
$\Delta(\kappa_{i}(\bm{\rho}),\kappa_{j}(\bm{\rho})),\bm{\rho}\in\mathbb{R}^{d}$
which is defined as

$\displaystyle\Delta(\kappa_{i}(\bm{\rho}),\kappa_{j}(\bm{\rho}))=\int|\kappa_{i}(\bm{\rho})-\kappa_{j}(\bm{\rho})|^{2}d\bm{\rho}.$
(7)

As $\Delta(\kappa_{i}(\bm{\rho}),\kappa_{j}(\bm{\rho}))$ decreases, kernels
$\kappa_{i}(\bm{\rho})$ and $\kappa_{j}(\bm{\rho})$ are considered to be more
similar. The following Lemma states that the function
$\Delta(\kappa_{i}(\bm{\rho}),\kappa_{j}(\bm{\rho}))$ exists for each pair of
absolutely integrable kernels.

######  Lemma 1.

Under the assumption that kernels $\\{\kappa_{i}\\}_{i=1}^{N}$ are absolutely
integrable, bounded and normalized such that $\kappa_{i}(\mathbf{0})=1$,
$\forall i:1\leq i\leq N$, the function
$\Delta(\kappa_{i}(\bm{\rho}),\kappa_{j}(\bm{\rho}))$ is bounded and exists
for each pair of kernels $\kappa_{i}(.)$ and $\kappa_{j}(.)$.

###### Proof.

Since kernels $\\{\kappa_{i}(\bm{\rho})\\}_{i=1}^{N}$ are assumed to be
bounded as $0\leq\kappa_{i}(\bm{\rho})\leq 1$, $\forall\bm{\rho},\forall
i:1\leq i\leq N$, it can be concluded that
$|\kappa_{i}(\bm{\rho})-\kappa_{j}(\bm{\rho})|^{2}\leq|\kappa_{i}(\bm{\rho})-\kappa_{j}(\bm{\rho})|$.
Thus, it can be inferred that

$\displaystyle\int|\kappa_{i}(\bm{\rho})-\kappa_{j}(\bm{\rho})|^{2}d\bm{\rho}\leq\int|\kappa_{i}(\bm{\rho})-\kappa_{j}(\bm{\rho})|d\bm{\rho}.$
(8)

Furthermore, based on the Triangular inequality, it can be written that

$\displaystyle\int|\kappa_{i}(\bm{\rho})-\kappa_{j}(\bm{\rho})|d\bm{\rho}\leq\int|\kappa_{i}(\bm{\rho})|d\bm{\rho}+\int|\kappa_{j}(\bm{\rho})|d\bm{\rho}.$
(9)

Based on (8), (9) and the fact that kernels are absolutely integrable, we can
conclude that the function
$\Delta(\kappa_{i}(\bm{\rho}),\kappa_{j}(\bm{\rho}))$ is bounded and exists
for each pair of kernels $\kappa_{i}(.)$ and $\kappa_{j}(.)$. ∎

Furthermore, the following lemma states that the average difference between
function approximations given by each pair of kernels is bounded above in
accordance with the function $\Delta(.,.)$ defined in (7).

######  Lemma 2.

Let $C_{m}:=\max_{i}\sum_{t=1}^{T}{|\alpha_{i,t}|^{2}}$ where
$\\{\alpha_{i,t}\\}_{t=1}^{T}$ are weights for (2) associated with the $i$-th
kernel $\kappa_{i}(.)$. Also, let ${\bm{x}}$ is bounded as $\|{\bm{x}}\|\leq
1$ and kernels are absolutely integrable. Then, the average difference between
function approximations given by $\kappa_{i}(.)$ and $\kappa_{j}(.)$ is
bounded above as

$\displaystyle\frac{1}{{\mathcal{U}}_{d}}\int|\hat{f}_{i}({\bm{x}})-\hat{f}_{j}({\bm{x}})|^{2}d{\bm{x}}\leq\frac{2C_{m}}{{\mathcal{U}}_{d}}\sum_{t=1}^{T}{\left(\Delta(\kappa_{i}({\bm{x}}-{\bm{x}}_{t}),\kappa_{j}({\bm{x}}-{\bm{x}}_{t}))+2{\mathcal{U}}_{d}\right)}$
(10)

where $\hat{f}_{i}({\bm{x}})$ denotes the function approximation given by
$\kappa_{i}(.)$ as in (2) and ${\mathcal{U}}_{d}$ represents $d$-dimensional
Euclidean unit norm ball volume.

###### Proof.

See Appendix A. ∎

It can be seen from Lemma 2 that the function
$\Delta(\kappa_{i}(\bm{\rho}),\kappa_{j}(\bm{\rho}))$ can be used as a
criterion to measure the similarity between kernels $\kappa_{i}(.)$ and
$\kappa_{j}(.)$ without knowing data samples $\\{{\bm{x}}_{t}\\}_{t=1}^{T}$.
This helps reduce computational complexity of the function approximation since
similarity among kernels in the dictionary can be measured offline before
observing data samples.

Let ${\mathcal{G}}:=({\mathcal{V}},{\mathcal{E}})$ be a directed graph with
vertex $v_{i}\in\mathcal{V}$ which represents the $i$-th kernel $\kappa_{i}$.
There is an edge from $v_{i}$ to $v_{j}$ i.e. $(i,j)\in{\mathcal{E}}$ if
$\Delta(\kappa_{i}(\bm{\rho}),\kappa_{j}(\bm{\rho}))\leq\gamma_{i}$ where
$\gamma_{i}$ is a threshold for $v_{i}$. Furthermore, in this case, there is a
self-loop for each $v_{i}\in{\mathcal{V}}$. Since a subset of function
approximations associated with kernels will be chosen using the graph
${\mathcal{G}}$, the chosen subset of function approximations can be viewed as
feedback collected from the graph ${\mathcal{G}}$ and as a result the graph
${\mathcal{G}}$ is called _feedback graph_. Let
${\mathbb{N}}_{i}^{\text{out}}$ denote the out-neighborhood set of $v_{i}$
which means $j\in{\mathbb{N}}_{i}^{\text{out}}$ if $(i,j)\in{\mathcal{E}}$.
Also, let ${\mathbb{N}}_{i}^{\text{in}}$ denote the in-neighborhood set of
$v_{i}$ which means $j\in{\mathbb{N}}_{i}^{\text{in}}$ if
$(j,i)\in{\mathcal{E}}$. Specifically in order to restrict the number of out-
neighbors for each node to $M$, the value of $\gamma_{i}$ is obtained as

$\displaystyle\gamma_{i}=\arg\max_{\gamma}\\{\gamma||{\mathbb{N}}_{i}^{\text{out}}|=M\\}.$
(11)

Note that $M$ is a preselected parameter in the algorithm and increasing the
value of $M$ increases the connectivity of the feedback graph. At each time
instant, one of the nodes are drawn and the function approximation is carried
out using the combination of a subset of kernels which are out-neighbors of
the chosen node. Therefore, increase in $M$ can increase the exploration in
the approximation task while it increases the computational complexity. The
feedback graph construction procedure is summarized in Algorithm 1.

Algorithm 1 Feedback Graph Construction

Input:Kernels $\kappa_{i}$, $i=1,...,N$.

for $i=1,...,N$ do

Obtain $\gamma_{i}$ via (11).

Append $(i,j)$ to ${\mathcal{E}}$ if
$\Delta(\kappa_{i}(\bm{\rho}),\kappa_{j}(\bm{\rho}))\leq\gamma_{i}$.

end for

In this paper, the goal is to find the best kernel in the hindsight to
minimize the cumulative regret. To this end, proposed algorithms need
performing sufficient exploration such that algorithms can evaluate all
kernels to find the best kernel in the hindsight. By choosing a subset of
kernels at each time instant, proposed algorithms perform exploration to find
the best kernel in the hindsight. Specifically, using the feedback graph
${\mathcal{G}}$, the algorithm will perform exploration to find the subset of
kernels which include the best kernel in the hindsight and similar kernels to
the best one based on the value of the function $\Delta(.,.)$. In the
meantime, the proposed algorithms learn the optimal combination for each
subset of kernels to minimize the cumulative loss. In what follows, the
proposed algorithmic framework is presented to choose one of nodes from
${\mathcal{G}}$ such that a subset of kernels is selected.

###  3.2 Kernel Selection

The present section studies how to select a subset of kernels using the
feedback graph ${\mathcal{G}}$ and prior observations of losses associated
with kernels. Assume that each kernel is associated with a set of weights
$\\{w_{i,t}\\}_{i=1}^{N}$ where $w_{i,t}$ is the weight associated with the
$i$-th kernel $\kappa_{i}$. The weight $w_{i,t}$ indicates the accuracy of the
function approximation given by the $\kappa_{i}$ at time $t$ and its value can
be updated when more and more information is being revealed. Furthermore, a
set of weights $\\{u_{i,t}\\}_{i=1}^{N}$ is assigned to ${\mathcal{V}}$ such
that $u_{i,t}$ is the weight associated with $v_{i}\in{\mathcal{V}}$ at time
instant $t$, which indicates the accuracy of function approximation when the
node $v_{i}$ is drawn. In order to choose a subset of kernels at time $t$, one
of the vertices in ${\mathcal{V}}$ is drawn according to the probability mass
function (PMF) $p_{t}$

$\displaystyle
p_{i,t}=(1-\xi)\frac{u_{i,t}}{U_{t}}+\frac{\xi}{|{\mathbb{D}}|}\bm{1}_{\mathrm{i\in{\mathbb{D}}}},i=1,\ldots,N$
(12)

where $\xi$ is the exploration rate and $U_{t}:=\sum_{i=1}^{N}{u_{i,t}}$.
${\mathbb{D}}$ represents the dominating set of ${\mathcal{G}}$, and
$|{\mathbb{D}}|$ denotes the cardinality of ${\mathbb{D}}$. Moreover,
$\bm{1}_{\mathrm{i\in{\mathbb{D}}}}$ denote the indicator function and its
value is $1$ when $i\in{\mathbb{D}}$. Let ${\mathbb{S}}_{t}$ denote the subset
of kernel indices chosen at time $t$, and $I_{t}$ denote the index of the
kernel drawn according to the PMF $p_{t}$ in (12). Therefore,
$i\in{\mathbb{S}}_{t}$ if $i\in{\mathbb{N}}_{I_{t}}^{\text{out}}$, which means
that the loss associated with the $i$-th kernel is calculated if the $i$-th
kernel is an out-neighber of the $I_{t}$-th node. In turn, the RF-based
function approximation can be obtained as

$\displaystyle\hat{f}_{\text{RF}}({\bm{x}}_{t})=\sum_{i\in{\mathbb{N}}_{I_{t}}^{\text{out}}}{\frac{w_{i,t}}{\sum_{j\in{\mathbb{N}}_{I_{t}}^{\text{out}}}{w_{j,t}}}\hat{f}_{\text{RF},i}({\bm{x}}_{t})}.$
(13)

Furthermore, the importance sampling loss estimate $\ell_{i,t}$ at time
instant $t$ is defined as

$\displaystyle\ell_{i,t}=\frac{{\mathcal{L}}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})}{q_{i,t}}\bm{1}_{\mathrm{i\in{\mathbb{S}}_{t}}},i=1,\ldots,N$
(14)

where $q_{i,t}$ is the probability that $i\in{\mathbb{S}}_{t}$ and it can be
computed as

$\displaystyle q_{i,t}=\sum_{j\in{\mathbb{N}}_{i}^{\text{in}}}{p_{j,t}}.$ (15)

In addition, the importance sampling function approximation estimate
$\hat{\ell}_{i,t}$ at time instant $t$ associated with $v_{i}\in{\mathcal{V}}$
is defined as

$\displaystyle\hat{\ell}_{i,t}=\frac{{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})}{p_{i,t}}\bm{1}_{\mathrm{I_{t}=i}}.$
(16)

Using the importance sampling loss estimate in (15), ${\bm{\theta}}_{i,t}$ can
be updated as

$\displaystyle{\bm{\theta}}_{i,t+1}$
$\displaystyle={\bm{\theta}}_{i,t}-\eta\nabla\ell_{i,t}={\bm{\theta}}_{i,t}-\eta\frac{\nabla{\mathcal{L}}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})}{q_{i,t}}\bm{1}_{\mathrm{i\in{\mathbb{S}}_{t}}},$
(17)

where $\eta$ is the learning rate. Moreover, the multiplicative update is
employed to update $w_{i,t}$ and $u_{i,t}$ based on importance sampling loss
estimates in (14) and (16) as follows

$\displaystyle w_{i,t+1}$
$\displaystyle=w_{i,t}\exp(-\eta\ell_{i,t}),i=1,\ldots,N$ (18a) $\displaystyle
u_{i,t+1}$ $\displaystyle=u_{i,t}\exp(-\eta\hat{\ell}_{i,t}),i=1,\ldots,N.$
(18b)

The procedure to choose a subset of kernels at each time instant for function
approximation is summarized in Algorithm 2. This algorithm is called SFG-MKL
which stands for Similarity Feedback Graph based Multi-Kernel Leanring.

Algorithm 2 Similarity Feedback Graph aided Online Multi-Kernel Learning (SFG-
MKL)

Input:Kernels $\kappa_{i}$, $i=1,...,N$, learning rate $\eta$, exploration
rate $\xi$, number of RFs $D$.

Initialize: ${\bm{\theta}}_{i,1}=\mathbf{0}$, ${w}_{i,1}=1$, $i=1,...,N$,
Construct the feedback graph ${\mathcal{G}}$ via Algorithm 1.

for $t=1,...,T$ do

Receive one datum ${\bm{x}}_{t}$.

Draw one of nodes $v_{i}\in{\mathcal{V}}$ according to the PMF
${p}_{t}=({p}_{1,t},...,{p}_{N,t})$ in (12).

Predict $\hat{f}_{\text{RF}}({\bm{x}}_{t})$ via (13).

Calculate loss ${{\mathcal{L}}(\hat{f}_{\text{RF},i}({\bm{x}}_{t}),y_{t})}$
for all $i\in{\mathbb{S}}_{t}$.

Update ${{\bm{\theta}}}_{i,t+1}$ via (17).

Update ${w}_{i,t+1}$ and $u_{i,t+1}$ via (18).

end for

###  3.3 Regret Analysis

This subsection presents the regret analysis of SFG-MKL, where we apply
stochastic regret (Hazan, 2016) to measures the difference between expected
cumulative loss of the SFG-MKL and the best function approximant in the
hindsight. Let $f^{*}(.)$ denote the best function approximant in the
hindsight which can be obtained as

$\displaystyle{f}^{*}(.)$
$\displaystyle\in\arg\min_{{f}_{i}^{*},i\in\\{1,...,N\\}}\sum_{t=1}^{T}{{\mathcal{L}}({f}_{i}^{*}({\bm{x}}_{t}),y_{t})}$
(19a) $\displaystyle{f}_{i}^{*}(.)$
$\displaystyle\in\arg\min_{f\in{\mathbb{H}}_{i}}\sum_{t=1}^{T}{{\mathcal{L}}({f}({\bm{x}}_{t}),y_{t})}$
(19b)

Hence, the stochastic regret associated with the algorithm SFG-MKL is defined
as

$\displaystyle\sum_{t=1}^{T}{\mathbb{E}_{t}[{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})]}-\sum_{t=1}^{T}{{\mathcal{L}}(f^{*}({\bm{x}}_{t}),y_{t})}$
(20)

where $\mathbb{E}_{t}[.]$ denotes the expected value at time instant $t$ given
the loss observations in prior times. Furthermore, the performance of SFG-MKL
is analyzed under the following assumptions:
(as1) The loss function
${\mathcal{L}}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})$
is convex with respect to ${\bm{\theta}}_{i,t}$ at each time instant $t$.
(as2) For ${\bm{\theta}}$ in a bounded set ${\mathbb{T}}$ which satisfies
$\|{\bm{\theta}}\|\leq C_{{\bm{\theta}}}$ the loss and its gradient are
bounded as
${\mathcal{L}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})}\in[0,1]$
and
$\|\nabla\mathcal{L}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})\|\leq
L$, respectively.
(as3) Kernels $\\{{\kappa}_{i}\\}_{i=1}^{N}$ are shift-invariant,
standardized, and bounded. And each datum $\|{\bm{x}}_{t}\|\leq 1$.

The following Theorem presents the upper bound for cumulative stochastic
regret of SFG-MKL.

######  Theorem 3.

Under (as1) and (as2), let $j^{*}=\arg\min_{\forall j:1\leq j\leq
N}{\sum_{t=1}^{T}{{\mathcal{L}}(f_{j}^{*}({\bm{x}}_{t}),y_{t})}}$. Then for
any $i\in{\mathbb{N}}_{j^{*}}^{\text{in}}$, the stochastic regret of SFG-MKL
satisfies

$\displaystyle\sum_{t=1}^{T}{\mathbb{E}_{t}[{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})]}-\sum_{t=1}^{T}{{\mathcal{L}}(f^{*}({\bm{x}}_{t}),y_{t})}$
$\displaystyle\leq$ $\displaystyle\frac{\ln
N|{\mathbb{N}}_{i}^{\text{out}}|}{\eta}+\frac{(1+\epsilon)C^{2}}{2\eta}+\epsilon
LTC$ $\displaystyle+(\xi+\frac{\eta
N}{2}-\frac{\eta\xi}{2})T+\frac{\eta}{2}\sum_{t=1}^{T}{(\frac{1}{\bar{q}_{i,t}}+\frac{L^{2}}{q_{j^{*},t}})}$
(21)

with probability at least
$1-2^{8}(\frac{\sigma_{j^{*}}}{\epsilon})^{2}\exp(-\frac{D\epsilon^{2}}{4d+8})$
under (as1)-(as3) for any $\epsilon>0$. Furthermore,
$\frac{1}{\bar{q}_{i,t}}=\sum_{j\in{\mathbb{N}}_{i}^{\text{out}}}{\frac{w_{j,t}}{q_{j,t}W_{i,t}}}$,
$C$ is a constant and $\sigma_{j^{*}}^{2}$ is the second moment of
$\pi_{\kappa_{j^{*}}}(\bm{\psi})$.

###### Proof.

The proof is deferred to Appendix B. ∎

The regret bound in (21) depends on $\frac{1}{\bar{q}_{i,t}}$ and
$\frac{1}{q_{j^{*},t}}$. Since, there is a self-loop for all
$v_{k}\in{\mathcal{V}}$, it can be written that $q_{k,t}\geq p_{k,t}$. In
addition, based on (12), we can conclude that
$p_{k,t}>\frac{\xi}{|{\mathbb{D}}|}$, $\forall v_{k}\in{\mathcal{V}}$ and as a
result $q_{k,t}>\frac{\xi}{|{\mathbb{D}}|}$, $\forall v_{k}\in{\mathcal{V}}$.
Therefore, in the worst case where there is a
$k\in{\mathbb{N}}_{i}^{\text{out}}$ such that
$q_{k,t}={\mathcal{O}}(\frac{\xi}{|{\mathbb{D}}|})$, considering
$\eta=\epsilon={\mathcal{O}}(\frac{1}{\sqrt{T}})$ and
$\xi={\mathcal{O}}(T^{\frac{1}{4}})$, SFG-MKL can achieve regret bound of
${\mathcal{O}}(T^{\frac{3}{4}})$. Since the regret bound of
${\mathcal{O}}(\sqrt{T})$ is more satisfactory than the regret bound of
${\mathcal{O}}(T^{\frac{3}{4}})$, in what follows the structure of the
feedback graph is refined at each time instant so that the regret of
${\mathcal{O}}(\sqrt{T})$ can be achieved.

##  4 Online Multi-Kernel Learning with Graph Refinement

To begin with, let’s define set ${\mathbb{D}}_{t}^{\prime}$ as

$\displaystyle{\mathbb{D}}_{t}^{\prime}:=\left\\{i\bigg{|}\frac{u_{i,t}}{U_{t}}\geq\frac{1}{1-\xi}(\beta-\frac{\xi}{N})\right\\}$
(22)

where $\beta$ is a pre-selected constant. According to (12), it can be
inferred that $p_{i,t}\geq\beta,\forall i\in{\mathbb{D}}_{t}^{\prime}$. Let
${\mathcal{G}}_{t}^{\prime}=({\mathcal{V}},{\mathcal{E}}_{t}^{\prime})$ be a
graph such that ${\mathbb{D}}_{t}^{\prime}$ is a dominating set of
${\mathcal{G}}_{t}^{\prime}$. Suppose at each time instant $t$,
${\mathcal{G}}_{t}^{\prime}$ is employed as the feedback graph instead of
${\mathcal{G}}$. In this case, it is ensured that there is at least one edge
from ${\mathbb{D}}_{t}^{\prime}$ to each
$v_{i}\in{\mathcal{V}}\setminus{\mathbb{D}}_{t}^{\prime}$, i.e.,
${\mathbb{D}}_{t}^{\prime}$ is a dominating set of
${\mathcal{G}}_{t}^{\prime}$. In this case, we have $q_{i,t}\geq\beta$,
$\forall v_{i}\in{\mathcal{V}}$. To this end, at each time instant $t$,
${\mathcal{G}}_{t}^{\prime}$ can be constructed based on ${\mathcal{G}}$ by
expanding ${\mathcal{E}}$ to ${\mathcal{E}}_{t}^{\prime}$ such that
${\mathbb{D}}_{t}^{\prime}$ would be a dominating set of
${\mathcal{G}}_{t}^{\prime}$. Specifically, at each time instant $t$, the edge
$(d_{i,t},i)$ is appended to ${\mathcal{E}}_{t}^{\prime}$, if there is not any
edge from ${\mathbb{D}}_{t}^{\prime}$ to $v_{i}$, where

$\displaystyle
d_{i,t}=\arg\min_{j\in{\mathbb{D}}_{t}^{\prime}}\Delta(\kappa_{i}(\bm{\rho}),\kappa_{j}(\bm{\rho})).$
(23)

Hence, there is at least one edge from ${\mathbb{D}}_{t}^{\prime}$ to
$v_{i}\in{\mathcal{V}}\setminus{\mathbb{D}}_{t}^{\prime}$, meaning
${\mathbb{D}}_{t}^{\prime}$ is a dominating set for
${\mathcal{G}}_{t}^{\prime}$. Then one of the vertices in ${\mathcal{V}}$ is
drawn according to the probability mass function (PMF) $p_{t}$, with

$\displaystyle
p_{i,t}=(1-\xi)\frac{u_{i,t}}{U_{t}}+\frac{\xi}{|{\mathbb{D}}_{t}^{\prime}|}\bm{1}_{\mathrm{i\in{\mathbb{D}}_{t}^{\prime}}},i=1,\ldots,N.$
(24)

Let ${\mathbb{N}}_{i,t}^{\text{out}}$ and ${\mathbb{N}}_{i,t}^{\text{in}}$
denote sets of out-neighbors and in-neighbors of $v_{i}$ in
${\mathcal{G}}_{t}^{\prime}$, respectively. According to (22) and (24), we
have $q_{i,t}\geq\beta$, $\forall v_{i}\in{\mathcal{V}}$ where
$q_{i,t}=\sum_{j\in{\mathbb{N}}_{i,t}^{\text{in}}}{p_{j,t}}$. The RF-based
function approximation can be written as

$\displaystyle\hat{f}_{\text{RF}}({\bm{x}}_{t})=\sum_{i\in{\mathbb{N}}_{I_{t}}^{\text{out}}}{\frac{w_{i,t}}{\sum_{j\in{\mathbb{N}}_{I_{t}}^{\text{out}}}{w_{j,t}}}\hat{f}_{\text{RF},i}({\bm{x}}_{t})}.$
(25)

According to (25), ${\bm{\theta}}_{i,t}$, $w_{i,t}$ and $u_{i,t}$ can be
updated using (17), (18a) and (18b), respectively. The procedure is summarized
in Algorithm 3, which is called SFG-MKL-R, and its performance is analyzed in
the following Theorem.

Algorithm 3 SFG-MKL with Feedback Graph Refinement (SFG-MKL-R)

Input:Kernels $\kappa_{i}$, $i=1,...,N$, learning rate $\eta>0$, exploration
rate $\xi>0$, the number of RFs $D$ and the constant $\beta>0$.

Initialize: ${\bm{\theta}}_{i,1}=\mathbf{0}$, ${w}_{i,1}=1$, $i=1,...,N$,
Construct the feedback graph ${\mathcal{G}}$ via Algorithm 1.

for $t=1,...,T$ do

Receive one datum ${\bm{x}}_{t}$.

Set ${\mathcal{E}}_{t}^{\prime}={\mathcal{E}}$ and obtain $d_{i,t}$, $\forall
i\in{\mathcal{V}}\setminus{\mathbb{D}}_{t}^{\prime}$ by (23).

For all $i\in{\mathcal{V}}\setminus{\mathbb{D}}_{t}^{\prime}$, append
$(d_{i,t},i)$ to ${\mathcal{E}}_{t}^{\prime}$ if
$(d_{i,t},i)\notin{\mathcal{E}}$.

Draw one of nodes $v_{i}\in{\mathcal{V}}$ according to the PMF
${p}_{t}=({p}_{1,t},...,{p}_{N,t})$ in (24).

Predict $\hat{f}_{\text{RF}}({\bm{x}}_{t})$ via (25).

Calculate loss ${{\mathcal{L}}(\hat{f}_{\text{RF},i}({\bm{x}}_{t}),y_{t})}$
for all $i\in{\mathbb{S}}_{t}$.

Update ${{\bm{\theta}}}_{i,t+1}$ via (17).

Update ${w}_{i,t+1}$ and $u_{i,t+1}$ via (18).

end for

######  Theorem 4.

The stochastic regret of SFG-MKL-R satisfies

$\displaystyle\sum_{t=1}^{T}{\mathbb{E}_{t}[{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})]}-\sum_{t=1}^{T}{{\mathcal{L}}(f^{*}({\bm{x}}_{t}),y_{t})}$
$\displaystyle\leq$ $\displaystyle\frac{2\ln
N}{\eta}+\frac{(1+\epsilon)C^{2}}{2\eta}+\epsilon
LTC+(\xi+\frac{\eta}{2}\frac{L^{2}+N\beta+1}{\beta}-\frac{\eta\xi}{2})T$ (26)

with probability at least
$1-2^{8}(\frac{\sigma_{j^{*}}}{\epsilon})^{2}\exp(-\frac{D\epsilon^{2}}{4d+8})$
under (as1)-(as3) for any $\epsilon>0$ and any $\beta\leq\frac{1}{N}$.

###### Proof.

The proof can be found in Appendix C. ∎

According to Theorem 4, by setting
$\eta=\epsilon=\xi={\mathcal{O}}(\frac{1}{\sqrt{T}})$ and
$\beta={\mathcal{O}}(1)$ such that $\beta\leq\frac{1}{N}$, SFG-MKL-R can
achieve regret bound of ${\mathcal{O}}(\sqrt{T})$ using the feedback graph
${\mathcal{G}}_{t}^{\prime}$. However, note that since some edges may be added
to ${\mathcal{G}}$ to construct ${\mathcal{G}}_{t}^{\prime}$, using
${\mathcal{G}}_{t}^{\prime}$ instead of ${\mathcal{G}}$ may cause increase in
computational complexity of function approximation.

Computational Complexity. Both SFG-MKL and SFG-MKL-R needs to store set of
$d$-dimensional vectors $\\{\bm{\psi}_{i,j}\\}_{j=1}^{D}$ per kernel in
addition to two weighting coefficients $\\{w_{i,t}\\}_{i=1}^{N}$ and
$\\{u_{i,t}\\}_{i=1}^{N}$. Therefore, the memory requirement for both of the
algorithms are ${\mathcal{O}}(dDN)$. Let in order to construct
${\mathcal{G}}$, the number of out-neighbors of each node
$v_{i}\in{\mathcal{V}}$ is restricted to $M<N$. In this case, the per-
iteration complexity of SFG-MKL including calculation of inner products is
${\mathcal{O}}(dDM)$. However, in SFG-MKL-R, due to the graph refinement
procedure it is possible that the number of out-neighbors of one node in
${\mathcal{G}}_{t}^{\prime}$ to be $N$. Therefore, the worst case per-
iteration computational complexity of SFG-MKL-R is ${\mathcal{O}}(dDN)$.
Furthermore, the per-iteration computational complexity of OMKR developed by
Sahoo et al. (2014) is ${\mathcal{O}}(tdN)$ while the per-iteration
computational complexity of RF-based online multi-kernel learning algorithms
developed by Sahoo et al. (2019) and Shen et al. (2019) are
${\mathcal{O}}(dDN)$. In addition, the per-iteration complexity of OMKL-GF
(Ghari and Shen, 2020) is ${\mathcal{O}}(dDM+JN)$ where $M$ is the maximum
number of kernels in the chosen subset and $J$ is a constant related to the
algorithm.

Comparison with OMKL-GF (Ghari and Shen, 2020). OMKL-GF by Ghari and Shen
(2020) also views kernels as experts. OMKL-GF exploits a bipartite graph
without considering the relationships between kernels. In contrast, our novel
SFG-MKL and SFG-MKL-R construct feedback graphs based on similarities between
kernels. This feedback graph structure helps SFG-MKL-R to achieve tighter
regret of ${\mathcal{O}}(\sqrt{T})$ compared with
${\mathcal{O}}(T^{\frac{5}{6}})$ of OMKL-GF.

##  5 Experiments

This section presents experimental results over real datasets downloaded from
UCI Machine Learning Repository (Dua and Graff, 2017). The performance of the
proposed algorithms SFG-MKL and SFG-MKL-R are compared with the following
kernel learning benchmarks:
OMKR: online multi-kernel regression approach proposed by Sahoo et al. (2014).
Raker: RF-based online multi-kernel learning (Shen et al., 2019).
OMKL-GF: online multi-kernel learning with bipartite graph (Ghari and Shen,
2020).

Table 1: MSE $\&$ run time for Airfoil Self-Noise dataset. Algorithms | MSE($\times 10^{-3}$) | Run time (s)
---|---|---
OMKR | $28.32$ | $1003.80$
Raker | $22.85$ | $4.86$
OMKL-GF | $30.41$ | $2.71$
SFG-MKL | $12.83$ | $\mathbf{1.32}$
SFG-MKL-R | $\mathbf{12.81}$ | $1.91$
Table 2: MSE and run time for Concrete Compressive Strength dataset. Algorithms | MSE($\times 10^{-3}$) | Run time (s)
---|---|---
OMKR | $30.51$ | $454.87$
Raker | $26.02$ | $3.32$
OMKL-GF | $40.69$ | $2.08$
SFG-MKL | $21.56$ | $\mathbf{0.92}$
SFG-MKL-R | $\mathbf{21.38}$ | $1.43$
Table 3: MSE and run time for Naval Propulsion Plants dataset. Algorithms | MSE($\times 10^{-3}$) | Run time (s)
---|---|---
OMKR | $7.59$ | $39308.53$
Raker | $6.82$ | $38.52$
OMKL-GF | $10.50$ | $17.92$
SFG-MKL | $\mathbf{4.35}$ | $\mathbf{8.99}$
SFG-MKL-R | $4.36$ | $10.35$
Table 4: MSE and run time over Wine Quality dataset. Algorithms | MSE($\times 10^{-3}$) | Run time (s)
---|---|---
OMKR | $21.95$ | $5342.42$
Raker | $21.04$ | $16.34$
OMKL-GF | $23.95$ | $8.60$
SFG-MKL | $\mathbf{20.19}$ | $\mathbf{4.01}$
SFG-MKL-R | $20.20$ | $4.96$

The accuracy of different approaches are evaluated using mean square error
(MSE). Due to the randomness in the random features extracted for function
approximation, we average the MSE over $R=50$ different sets of random
features. The MSE at time $t$ can be computed as
$\text{MSE}_{t}=\frac{1}{R}\sum_{r=1}^{R}{\frac{1}{t}\sum_{\tau=1}^{t}{(\hat{f}_{\text{RF}}({\bm{x}}_{\tau})-y_{\tau})^{2}}}.$
The number of random features $D=50$. The kernel dictionary contains $41$
radial basis function (RBF) kernels. The bandwidth of the $i$-th kernel is as
$10^{\sigma_{i}}$ where $\sigma_{i}=\frac{i-21}{10}$. Parameters $\xi$ and
$\eta$ are set to $\frac{1}{\sqrt{T}}$ for all algorithms. The performance of
kernel learning algorithms is evaluated through several real datasets:
Airfoil Self-Noise: comprises $1503$ different size airfoils at various wind
tunnel speeds and each data sample ${\bm{x}}_{t}$ includes $5$ features such
as frequency and chord length. The output $y_{t}$ is scaled sound pressure
level in decibels (Brooks et al., 1989).
Concrete Compressive Strength: contains $1030$ samples of $8$ features, such
as the amount of cement or water in a concrete. The goal is to predict
concrete compressive strength (Yeh, 1998).
Naval Propulsion Plants : contains $11934$ samples of $15$ features of a naval
vessel characterized by a gas turbine propulsion plant including the ship
speed and gas turbine shaft torque. The goal is to predict the lever position
(Coraddu et al., 2016).
Wine Quality: contains $4898$ samples of $11$ features for white wine
including the amount of acidity, sugar and alcohol. The goal is to predict the
quality of wine (Cortez et al., 2009).

Parameter $\lambda$ is set to $10^{-3}$ and the greedy set cover algorithm by
Chvatal (1979) is employed to find the dominating set ${\mathbb{D}}$ of the
feedback graph ${\mathcal{G}}$. In addition, to determine the value of
$\gamma_{i}$ for each vertex $v_{i}\in{\mathcal{V}}$, the number of out-
neighbors for each node is set to be $5$. For SFG-MKL-R, at each time, $\beta$
is set to $\beta=(1-\xi)\bar{u}_{[10,t]}+\frac{\xi}{N}$ where
$\bar{u}_{[10,t]}$ denote the tenth greatest value in the sequence
$\\{\frac{u_{i,t}}{U_{t}}\\}_{i=1}^{N}$. In order to speed up SFG-MKL and SFG-
MKL-R, after $300$ time instants, both algorithms choose
$I_{t}=\arg\max_{i}{\frac{u_{i,t}}{U_{t}}}$. For OMKL-GF, the number of
selective nodes is set to be $1$ and the maximum number of kernels chosen at
each time instant is $10$, which obtains the best results as shown by Ghari
and Shen (2020). All experiments were carried out using Intel(R) Core(TM)
i7-10510U CPU @ 1.80 GHz 2.30 GHz processor with a 64-bit Windows operating
system.

Tables 1, 2, 3 and 4 show MSE and run time, respectively for kernel learning
algorithms when the performance of the algorithms tested on Airfoil Self-
Noise, Concrete Compressive Strength, Naval Propulsion Plants and Wine Quality
datasets, respectively. As it can be seen from Tables 1, 2, 3 and 4, both SFG-
MKL and SFG-MKL-R can provide lower MSE in comparison with other algorithms.
Also, results in Tables 1, 2, 3 and 4 illustrate that SFG-MKL runs faster than
other kernel learning approaches significantly. From the results in Tables 1,
2, 3 and 4, it can be inferred that using the feedback graph ${\mathcal{G}}$,
SFG-MKL can effectively prune the irrelevant kernels to improve the accuracy
of the learning task. Also, run times reported in Tables 1, 2, 3 and 4 show
that choosing a subset of kernels instead of employing all kernels in the
given dictionary can reduce the computational complexity of kernel learning
since both SFG-MKL and SFG-MKL-R run faster than Raker. Also, SFG-MKL is
faster than OMKL-GF which shows the effectiveness of SFG-MKL in reduction of
computational complexity. Moreover, Figures 1 and 2 illustrate the MSE of MKL
algorithms over time for Airfoil Self Noise and Naval Propulsion plants
datasets, respectively. It can be observed that our proposed algorithms
converge faster than all other alternatives.

Figure 1: MSE performance on Airfoil Self Noise dataset. Figure 2: MSE
performance on Naval Propulsion Plants dataset.

##  6 Conclusion

This paper presented online multi-kernel learning algorithms for non-linear
function learning. Based on the similarities between kernels, a feedback graph
was constructed in order to choose a subset of kernels. It was proved that
SFG-MKL can achieve sub-linear regret of ${\mathcal{O}}(T^{\frac{3}{4}})$.
Furthermore, refining the feedback graph structure at each time instant, SFG-
MKL-R was proposed, which enjoys sub-linear regret of
${\mathcal{O}}(\sqrt{T})$. Moreover, experiments on real datasets showed that
by choosing a subset of kernels, both SFG-MKL and SFG-MKL-R can obtain lower
MSE in comparison with other online multi-kernel learning algorithms OMKR,
Raker and OMKL-GF. Furthermore, experiments showed that SFG-MKL has
considerably lower run time compared to OMKR, Raker and OMKL-GF.

## References

  * Bengio et al. (2006) Yoshua Bengio, Olivier Delalleau, and Nicolas L. Roux.  The curse of highly variable functions for local kernel machines.  In _Advances in Neural Information Processing Systems_ , pages 107–114, May 2006.
  * Bouboulis et al. (2018) Pantelis Bouboulis, Symeon Chouvardas, and Sergios Theodoridis.  Online distributed learning over networks in rkh spaces using random fourier features.  _IEEE Transactions on Signal Processing_ , 66(7):1920–1932, Apr 2018.
  * Brooks et al. (1989) Thomas F. Brooks, D. Stuart Pope, and Micheal A. Marcolini.  Airfoil self-noise and prediction.  Technical report, Jul 1989.
  * Chung et al. (2019) Wesley Chung, Somjit Nath, Ajin Joseph, and Martha White.  Two-timescale networks for nonlinear value function approximation.  In _International Conference on Learning Representations_ , May 2019\.
  * Chvatal (1979) Vasek Chvatal.  A greedy heuristic for the set-covering problem.  _Mathematics of Operations Research_ , 4(3):233–235, Aug 1979.
  * Coraddu et al. (2016) Andrea Coraddu, Luca Oneto, Aessandro Ghio, Stefano Savio, Davide Anguita, and Massimo Figari.  Machine learning approaches for improving condition-based maintenance of naval propulsion plants.  _Proceedings of the Institution of Mechanical Engineers, Part M: Journal of Engineering for the Maritime Environment_ , 230(1):136–153, 2016.
  * Cortez et al. (2009) Paulo Cortez, António Cerdeira, Fernando Almeida, Telmo Matos, and José Reis.  Modeling wine preferences by data mining from physicochemical properties.  _Decision Support Systems_ , 47(4):547 – 553, 2009.
  * Dua and Graff (2017) Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.
  * Ghari and Shen (2020) Pouya M Ghari and Yanning Shen.  Online multi-kernel learning with graph-structured feedback.  In _Proceedings of the International Conference on Machine Learning_ , volume 119, pages 3474–3483, Jul 2020.
  * Hazan (2016) Elad Hazan.  Introduction to online convex optimization.  _Foundations and Trends in Optimization_ , 2(3-4):157–325, 2016.
  * Lu et al. (2016) Jing Lu, Steven C.H. Hoi, Jialei Wang, Peilin Zhao, and Zhi-Yong Liu.  Large scale online kernel learning.  _Journal of Machine Learning Research_ , 17(47):1–43, 2016.
  * Rahimi and Recht (2007) Ali Rahimi and Benjamin Recht.  Random features for large-scale kernel machines.  In _Proceedings of International Conference on Neural Information Processing Systems_ , pages 1177–1184, Dec 2007.
  * Sahoo et al. (2014) Doyen Sahoo, Steven C.H. Hoi, and Bin Li.  Online multiple kernel regression.  In _Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , page 293–302, 2014.
  * Sahoo et al. (2019) Doyen Sahoo, Steven C. H. Hoi, and Bin Li.  Large scale online multiple kernel regression with application to time-series prediction.  _ACM Transactions on Knowledge Discovery from Data_ , 13(1), Jan 2019.
  * Scholkopf and Smola (2001) Bernhard Scholkopf and Alexander J. Smola.  _Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond_.  MIT Press, Cambridge, MA, USA, 2001.
  * Shen et al. (2019) Yanning Shen, Tianyi Chen, and Georgios B. Giannakis.  Random feature-based online multi-kernel learning in environments with unknown dynamics.  _Journal of Machine Learning Research_ , 20(1):773–808, Jan 2019.
  * Sonnenburg et al. (2006) Sören Sonnenburg, Gunnar Rätsch, Christin Schäfer, and Bernhard Schölkopf.  Large scale multiple kernel learning.  _Journal of Machine Learning Research_ , 7:1531–1565, Dec 2006.
  * Wahba (1990) Grace Wahba.  _Spline Models for Observational Data_.  Society for Industrial and Applied Mathematics, 1990.
  * Williams and Seeger (2000) Christopher K. I. Williams and Matthias Seeger.  Using the nyström method to speed up kernel machines.  In _Proceedings of the International Conference on Neural Information Processing Systems_ , page 661–667, Jan 2000.
  * Yeh (1998) I-Cheng Yeh.  Modeling of strength of high-performance concrete using artificial neural networks.  _Cement and Concrete Research_ , 28(12):1797 – 1808, Dec 1998.
  * Zhang and Liao (2019) Xiao Zhang and Shizhong Liao.  Incremental randomized sketching for online kernel learning.  In _Proceedings of International Conference on Machine Learning_ , pages 7394–7403, Jun 2019.

##  Appendix A Proof of Lemma 2

According to (2), we obtain

$\displaystyle\frac{1}{{\mathcal{U}}_{d}}\int|\hat{f}_{i}({\bm{x}})-\hat{f}_{j}({\bm{x}})|^{2}d{\bm{x}}=\frac{1}{{\mathcal{U}}_{d}}\int|\sum_{t=1}^{T}{\alpha_{i,t}\kappa_{i}({\bm{x}},{\bm{x}}_{t})}-\sum_{t=1}^{T}{\alpha_{j,t}\kappa_{j}({\bm{x}},{\bm{x}}_{t})}|^{2}d{\bm{x}}.$
(27)

Applying Arithmetic Mean-Geometric Mean inequality on the right hand side of
(27), we find

$\displaystyle\frac{1}{{\mathcal{U}}_{d}}\int|\hat{f}_{i}({\bm{x}})-\hat{f}_{j}({\bm{x}})|^{2}d{\bm{x}}$
$\displaystyle\leq$
$\displaystyle\frac{2}{{\mathcal{U}}_{d}}\int\left(|\sum_{t=1}^{T}{\alpha_{i,t}\left(\kappa_{i}({\bm{x}},{\bm{x}}_{t})-\kappa_{j}({\bm{x}},{\bm{x}}_{t})\right)}|^{2}+|\sum_{t=1}^{T}{(\alpha_{j,t}-\alpha_{i,t})\kappa_{j}({\bm{x}},{\bm{x}}_{t})}|^{2}\right)d{\bm{x}}.$
(28)

Using Cauchy-Schwartz inequality, (28) can be further relaxed to

$\displaystyle\frac{1}{{\mathcal{U}}_{d}}\int|\hat{f}_{i}({\bm{x}})-\hat{f}_{j}({\bm{x}})|^{2}d{\bm{x}}$
$\displaystyle\leq$
$\displaystyle\frac{2}{{\mathcal{U}}_{d}}\int(\sum_{t=1}^{T}{|\alpha_{i,t}|^{2}})(\sum_{t=1}^{T}{|\kappa_{i}({\bm{x}},{\bm{x}}_{t})-\kappa_{j}({\bm{x}},{\bm{x}}_{t})|^{2}})d{\bm{x}}$
$\displaystyle+\frac{2}{{\mathcal{U}}_{d}}\int(\sum_{t=1}^{T}{|\alpha_{j,t}-\alpha_{i,t}|^{2}})(\sum_{t=1}^{T}{|\kappa_{j}({\bm{x}},{\bm{x}}_{t})|^{2}})d{\bm{x}}.$
(29)

Considering the fact that $C_{m}:=\max_{i}\sum_{t=1}^{T}{|\alpha_{i,t}|^{2}}$,
from (29) it can be written that

$\displaystyle\frac{1}{{\mathcal{U}}_{d}}\int|\hat{f}_{i}({\bm{x}})-\hat{f}_{j}({\bm{x}})|^{2}d{\bm{x}}$
$\displaystyle\leq$
$\displaystyle\frac{2C_{m}}{{\mathcal{U}}_{d}}\sum_{t=1}^{T}{\int|\kappa_{i}({\bm{x}},{\bm{x}}_{t})-\kappa_{j}({\bm{x}},{\bm{x}}_{t})|^{2}d{\bm{x}}}+\frac{4C_{m}}{{\mathcal{U}}_{d}}\sum_{t=1}^{T}{\int|\kappa_{j}({\bm{x}},{\bm{x}}_{t})|^{2}d{\bm{x}}}.$
(30)

Furthermore, based on (30) and the fact that
$|\kappa_{j}({\bm{x}},{\bm{x}}_{t})|^{2}\leq 1$, we can infer that

$\displaystyle\frac{1}{{\mathcal{U}}_{d}}\int|\hat{f}_{i}({\bm{x}})-\hat{f}_{j}({\bm{x}})|^{2}d{\bm{x}}\leq\frac{2C}{{\mathcal{U}}_{d}}\sum_{t=1}^{T}{\left(\Delta(\kappa_{i}({\bm{x}}-{\bm{x}}_{t}),\kappa_{j}({\bm{x}}-{\bm{x}}_{t}))+2{\mathcal{U}}_{d}\right)}$
(31)

which proves Lemma 2.

##  Appendix B Proof of Theorem 3

In order to prove Theorem 3, we prove the following intermediate Lemma.

######  Lemma 5.

Let $\hat{f}_{\text{RF},i}(.)$ denote the sequence of estimates generated by
SFG-MKL with a preselected kernel ${\kappa}_{i}$ where
${\mathcal{F}}_{i}=\\{\hat{f}_{i}|\hat{f}_{i}({\bm{x}})={\bm{\theta}}^{\top}{\mathbf{z}}_{i}({\bm{x}}),\forall{\bm{\theta}}\in\mathbb{R}^{2D}\\}$.
Then, under assumptions (as1) and (as2) the following bound holds

$\displaystyle\sum_{t=1}^{T}{{\mathcal{L}}(\hat{f}_{\text{RF},i}({\bm{x}}_{t}),y_{t})}-\sum_{t=1}^{T}{{\mathcal{L}}(\hat{f}_{i}^{*}({\bm{x}}_{t}),y_{t})}\leq\frac{\|{\bm{\theta}}_{i}^{*}\|^{2}}{2\eta}+\sum_{t=1}^{T}{\frac{\eta
L^{2}}{2q_{i,t}}}$ (32)

where $L$ is the Lipschitz constant in (as2) and ${\bm{\theta}}_{i}^{*}$ is
the parameter vector associated with the best estimator
$\hat{f}_{i}^{*}({\bm{x}})=({\bm{\theta}}_{i}^{*})^{\top}{\mathbf{z}}_{i}({\bm{x}})$.

###### Proof.

For ${\bm{\theta}}_{i,t+1}$ and any fixed ${\bm{\theta}}$, it can be written
that

$\displaystyle\|{\bm{\theta}}_{i,t+1}-{\bm{\theta}}\|^{2}$
$\displaystyle=\|{\bm{\theta}}_{i,t}-{\eta}{\nabla}\ell_{i,t}-\mathbold{\theta}\|$
$\displaystyle=\|\mathbold{\theta}_{i,t}-\mathbold{\theta}\|^{2}-2{\eta}{\nabla}^{\top}\ell_{i,t}({\bm{\theta}}_{i,t}-{\bm{\theta}})+\|{\eta}{\nabla}\ell_{i,t}\|^{2}.$
(33)

Furthermore, from the convexity of the loss function with respect to
${\bm{\theta}}$ in (as1), we can conclude that

$\displaystyle{\mathcal{L}}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})-{\mathcal{L}}({\bm{\theta}}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})\leq\nabla^{\top}{\mathcal{L}}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})({\bm{\theta}}_{i,t}-{\bm{\theta}}).$
(34)

Therefore, from (34), it can be inferred that

$\displaystyle\left(\frac{{\mathcal{L}}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})}{q_{i,t}}-\frac{{\mathcal{L}}({\bm{\theta}}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})}{q_{i,t}}\right)\bm{1}_{\mathrm{i\in{\mathbb{S}}_{t}}}$
$\displaystyle\leq$
$\displaystyle\frac{\nabla^{\top}{\mathcal{L}}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})}{q_{i,t}}({\bm{\theta}}_{i,t}-{\bm{\theta}})\bm{1}_{\mathrm{i\in{\mathbb{S}}_{t}}}.$
(35)

Based on (14), (35) is equivalent to

$\displaystyle\ell_{i,t}-\frac{{\mathcal{L}}({\bm{\theta}}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})}{q_{i,t}}\bm{1}_{\mathrm{i\in{\mathbb{S}}_{t}}}\leq\nabla^{\top}\ell_{i,t}({\bm{\theta}}_{i,t}-{\bm{\theta}}).$
(36)

Combining (33) with (36), we get

$\displaystyle\ell_{i,t}-\frac{{\mathcal{L}}({\bm{\theta}}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})}{q_{i,t}}\bm{1}_{\mathrm{i\in{\mathbb{S}}_{t}}}\leq\frac{\|\mathbold{\theta}_{i,t}-\mathbold{\theta}\|^{2}-\|{\bm{\theta}}_{i,t+1}-{\bm{\theta}}\|^{2}}{2\eta}+\frac{\eta}{2}\|{\nabla}\ell_{i,t}\|^{2}.$
(37)

Taking the expectation of $\ell_{i,t}$ and $\|{\nabla}\ell_{i,t}\|^{2}$ with
respect to $\bm{1}_{\mathrm{i\in{\mathbb{S}}_{t}}}$, we arrive at

$\displaystyle\mathbb{E}_{t}[\ell_{i,t}]$
$\displaystyle=\sum_{j\in{\mathbb{N}}_{i}^{\text{in}}}{p_{j,t}\frac{{\mathcal{L}}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})}{q_{i,t}}}={\mathcal{L}}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})$
(38a) $\displaystyle\mathbb{E}_{t}[\|{\nabla}\ell_{i,t}\|^{2}]$
$\displaystyle=\sum_{j\in{\mathbb{N}}_{i}^{\text{in}}}{p_{j,t}\frac{\|\nabla{\mathcal{L}}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})\|^{2}}{q_{i,t}^{2}}}=\frac{\|\nabla{\mathcal{L}}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})\|^{2}}{q_{i,t}}.$
(38b)

Therefore, taking the expectation with respect to
$\bm{1}_{\mathrm{i\in{\mathbb{S}}_{t}}}$ from both sides of (37), we obtain

$\displaystyle{\mathcal{L}}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})-{\mathcal{L}}({\bm{\theta}}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})$
$\displaystyle\leq$
$\displaystyle\frac{\|\mathbold{\theta}_{i,t}-\mathbold{\theta}\|^{2}-\|{\bm{\theta}}_{i,t+1}-{\bm{\theta}}\|^{2}}{2\eta}+\frac{\eta\|\nabla{\mathcal{L}}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})\|^{2}}{2q_{i,t}}.$
(39)

Based on (as2), we have
$\|\nabla{\mathcal{L}}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})\|^{2}\leq
L^{2}$. Therefore, summing (39) over time from $t=1$ to $t=T$ it can be
concluded that

$\displaystyle\sum_{t=1}^{T}{{\mathcal{L}}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})}-\sum_{t=1}^{T}{{\mathcal{L}}({\bm{\theta}}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})}$
$\displaystyle\leq$
$\displaystyle\frac{\|\mathbold{\theta}\|^{2}-\|{\bm{\theta}}_{i,T+1}-{\bm{\theta}}\|^{2}}{2\eta}+\sum_{t=1}^{T}{\frac{\eta
L^{2}}{2q_{i,t}}}.$ (40)

Putting ${\bm{\theta}}={\bm{\theta}}_{i}^{*}$ in (40) and taking into account
that $\|{\bm{\theta}}_{i,T+1}-{\bm{\theta}}\|^{2}\geq 0$, we can write

$\displaystyle\sum_{t=1}^{T}{{\mathcal{L}}({\bm{\theta}}_{i,t}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})}-\sum_{t=1}^{T}{{\mathcal{L}}({\bm{\theta}}^{\top}{\mathbf{z}}_{i}({\bm{x}}_{t}),y_{t})}\leq\frac{\|{\bm{\theta}}_{i}^{*}\|^{2}}{2\eta}+\sum_{t=1}^{T}{\frac{\eta
L^{2}}{2q_{i,t}}}$ (41)

which completes the proof of Lemma 5. ∎

Furthermore, in order to prove Theorem 3, the following intermediate Lemma is
also proved.

######  Lemma 6.

The following inequality holds under (as1) and (as2)

$\displaystyle\sum_{t=1}^{T}{\mathbb{E}_{t}[{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})]}-\sum_{t=1}^{T}{{\mathcal{L}}_{i}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})}\leq\frac{\ln
N}{\eta}+\eta(1+\frac{N}{2}-\frac{\eta}{2})T$ (42)

where ${\mathcal{L}}_{i}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})$ denote the
loss of function approximation when $v_{i}$ is drawn.

###### Proof.

For any $t$, we can write

$\displaystyle\frac{U_{t+1}}{U_{t}}=\sum_{i=1}^{N}{\frac{u_{i,t+1}}{U_{t}}}=\sum_{i=1}^{N}{\frac{u_{i,t}}{U_{t}}\exp(-\eta\hat{\ell}_{i,t})}.$
(43)

Based on (12), we have
$\frac{u_{i,t}}{U_{t}}=\frac{p_{i,t}-\frac{\xi}{|{\mathbb{D}}|}\bm{1}_{\mathrm{i\in{\mathbb{D}}}}}{1-\xi}$
and as a result (43) can be rewritten as

$\displaystyle\frac{U_{t+1}}{U_{t}}=\sum_{i=1}^{N}{\frac{p_{i,t}-\frac{\xi}{|{\mathbb{D}}|}\bm{1}_{\mathrm{i\in{\mathbb{D}}}}}{1-\xi}\exp(-\eta\hat{\ell}_{i,t})}.$
(44)

Using the inequality $e^{-x}\leq 1-x+\frac{1}{2}x^{2},\forall x\geq 0$ and
(44), it can be concluded that

$\displaystyle\frac{U_{t+1}}{U_{t}}\leq\sum_{i=1}^{N}{\frac{p_{i,t}-\frac{\xi}{|{\mathbb{D}}|}\bm{1}_{\mathrm{i\in{\mathbb{D}}}}}{1-\xi}\left(1-\eta\hat{\ell}_{i,t}+\frac{1}{2}(\eta\hat{\ell}_{i,t})^{2}\right)}.$
(45)

Taking logarithm from both sides of inequality (45), and use the fact that
$1+x\leq e^{x}$, we arrive at

$\displaystyle\ln\frac{U_{t+1}}{U_{t}}\leq\sum_{i=1}^{N}{\frac{p_{i,t}-\frac{\xi}{|{\mathbb{D}}|}\bm{1}_{\mathrm{i\in{\mathbb{D}}}}}{1-\xi}\left(-\eta\hat{\ell}_{i,t}+\frac{1}{2}(\eta\hat{\ell}_{i,t})^{2}\right)}.$
(46)

Summing (46) over $t$ leads to

$\displaystyle\ln\frac{U_{T+1}}{U_{1}}\leq\sum_{t=1}^{T}{\sum_{i=1}^{N}{\frac{p_{i,t}-\frac{\xi}{|{\mathbb{D}}|}\bm{1}_{\mathrm{i\in{\mathbb{D}}}}}{1-\xi}\left(-\eta\hat{\ell}_{i,t}+\frac{1}{2}(\eta\hat{\ell}_{i,t})^{2}\right)}}.$
(47)

Furthermore, $\ln\frac{U_{T+1}}{U_{1}}$ can be bounded from below as

$\displaystyle\ln\frac{U_{T+1}}{U_{1}}\geq\ln\frac{u_{i,T+1}}{U_{1}}=-\sum_{t=1}^{T}{\eta\hat{\ell}_{i,t}}-\ln
N$ (48)

for any $i$ such that $1\leq i\leq N$. Combining (47) with (48), we obtain

$\displaystyle\sum_{t=1}^{T}{\sum_{i=1}^{N}{\frac{p_{i,t}\eta}{1-\xi}\hat{\ell}_{i,t}}}-\sum_{t=1}^{T}{\eta\hat{\ell}_{i,t}}$
$\displaystyle\leq$ $\displaystyle\ln
N+\sum_{t=1}^{T}{\sum_{i=1}^{N}{\frac{\eta\xi\bm{1}_{\mathrm{i\in{\mathbb{D}}}}}{(1-\xi)|{\mathbb{D}}|}\hat{\ell}_{i,t}}}+\sum_{t=1}^{T}{\sum_{i=1}^{N}{\frac{p_{i,t}-\frac{\xi}{|{\mathbb{D}}|}\bm{1}_{\mathrm{i\in{\mathbb{D}}}}}{1-\xi}\left(\frac{1}{2}(\eta\hat{\ell}_{i,t})^{2}\right)}}.$
(49)

Multiplying both sides by $\frac{1-\xi}{\eta}$ it can be concluded that

$\displaystyle\sum_{t=1}^{T}{\sum_{i=1}^{N}{p_{i,t}\hat{\ell}_{i,t}}}-\sum_{t=1}^{T}{\hat{\ell}_{i,t}}$
$\displaystyle\leq$ $\displaystyle\frac{\ln
N}{\eta}+\sum_{t=1}^{T}{\sum_{i=1}^{N}{\frac{\xi\bm{1}_{\mathrm{i\in{\mathbb{D}}}}}{|{\mathbb{D}}|}\hat{\ell}_{i,t}}}+\sum_{t=1}^{T}{\sum_{i=1}^{N}{\frac{\eta(p_{i,t}-\frac{\xi}{|{\mathbb{D}}|}\bm{1}_{\mathrm{i\in{\mathbb{D}}}})}{2}\hat{\ell}_{i,t}^{2}}}.$
(50)

In addition, taking the expectation of $\hat{\ell}_{i,t}$ and
$\hat{\ell}_{i,t}^{2}$, we get

$\displaystyle\mathbb{E}_{t}[\hat{\ell}_{i,t}]$
$\displaystyle=p_{i,t}\frac{{\mathcal{L}}_{i}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})}{p_{i,t}}={\mathcal{L}}_{i}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})$
(51a) $\displaystyle\mathbb{E}_{t}[\hat{\ell}_{i,t}^{2}]$
$\displaystyle={p_{i,t}\frac{{\mathcal{L}}_{i}^{2}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})}{p_{i,t}^{2}}}=\frac{{\mathcal{L}}_{i}^{2}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})}{p_{i,t}}\leq\frac{1}{p_{i,t}}$
(51b)

Thus, taking the expectation from both sides of (50) leads to

$\displaystyle\sum_{t=1}^{T}{\sum_{i=1}^{N}{p_{i,t}{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})}}-\sum_{t=1}^{T}{{\mathcal{L}}_{i}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})}$
$\displaystyle\leq$ $\displaystyle\frac{\ln
N}{\eta}+\sum_{t=1}^{T}{\sum_{i=1}^{N}{\frac{\xi\bm{1}_{\mathrm{i\in{\mathbb{D}}}}}{|{\mathbb{D}}|}{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})}}+\sum_{t=1}^{T}{\sum_{i=1}^{N}{\frac{\eta(p_{i,t}-\frac{\xi}{|{\mathbb{D}}|}\bm{1}_{\mathrm{i\in{\mathbb{D}}}})}{2p_{i,t}}}}.$
(52)

Taking into account that
${\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})\leq 1$ and based on
(52) we can write

$\displaystyle\sum_{t=1}^{T}{\sum_{i=1}^{N}{p_{i,t}{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})}}-\sum_{t=1}^{T}{{\mathcal{L}}_{i}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})}$
$\displaystyle\leq$ $\displaystyle\frac{\ln N}{\eta}+\xi
T+\sum_{t=1}^{T}{\sum_{i=1}^{N}{\frac{\eta(p_{i,t}-\frac{\xi}{|{\mathbb{D}}|}\bm{1}_{\mathrm{i\in{\mathbb{D}}}})}{2p_{i,t}}}}.$
(53)

Moreover, using (53) and the fact that $p_{i,t}\leq 1$, it can be concluded
that

$\displaystyle\sum_{t=1}^{T}{\sum_{i=1}^{N}{p_{i,t}{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})}}-\sum_{t=1}^{T}{{\mathcal{L}}_{i}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})}$
$\displaystyle\leq$ $\displaystyle\frac{\ln N}{\eta}+(\xi+\frac{\eta
N}{2}-\frac{\eta\xi}{2})T.$ (54)

Furthermore, the expected loss incurred by SFG-MKL given observed losses in
prior time instants can be expressed as

$\displaystyle\mathbb{E}_{t}[{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})]$
$\displaystyle=\sum_{i=1}^{N}{p_{i,t}{\mathcal{L}}(\sum_{j\in{\mathbb{N}}_{i,t}^{\text{out}}}{\frac{w_{j,t}}{\sum_{k\in{\mathbb{N}}_{i,t}^{\text{out}}}{w_{k,t}}}\hat{f}_{\text{RF},j}({\bm{x}}_{t})},y_{t})}$
$\displaystyle=\sum_{i=1}^{N}{p_{i,t}{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})}.$
(55)

Therefore, from (54) and (55), it can be inferred that

$\displaystyle\sum_{t=1}^{T}{\mathbb{E}_{t}[{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})]}-\sum_{t=1}^{T}{{\mathcal{L}}_{i}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})}\leq\frac{\ln
N}{\eta}+(\xi+\frac{\eta N}{2}-\frac{\eta\xi}{2})T$ (56)

which establishes the Lemma 6. ∎

Furthermore, to prove Theorem 3, we prove the following Lemma.

######  Lemma 7.

For any $v_{i}\in{\mathcal{V}}$ and any $j\in{\mathbb{N}}_{i}^{\text{out}}$,
it can be written that

$\displaystyle\sum_{t=1}^{T}{{\mathcal{L}}_{i}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})}-\sum_{t=1}^{T}{{\mathcal{L}}(\hat{f}_{\text{RF,j}}({\bm{x}}_{t}),y_{t})}\leq\frac{\ln|{\mathbb{N}}_{i}^{\text{out}}|}{\eta}+\frac{\eta}{2}\sum_{t=1}^{T}{\frac{1}{\bar{q}_{i,t}}}$
(57)

where
$\frac{1}{\bar{q}_{i,t}}=\sum_{j\in{\mathbb{N}}_{i}^{\text{out}}}{\frac{w_{j,t}}{q_{j,t}W_{i,t}}}$.

###### Proof.

Let $W_{i,t}=\sum_{j\in{\mathbb{N}}_{i}^{\text{out}}}{w_{j,t}}$. For
$v_{i}\in{\mathcal{V}}$ we find

$\displaystyle\frac{W_{i,t+1}}{W_{i,t}}=\sum_{j\in{\mathbb{N}}_{i}^{\text{out}}}{\frac{w_{j,t+1}}{W_{i,t}}}=\sum_{j\in{\mathbb{N}}_{i}^{\text{out}}}{\frac{w_{j,t}}{W_{i,t}}\exp(-\eta\ell_{j,t})}.$
(58)

The following inequality can be obtained using the inequality $e^{-x}\leq
1-x+\frac{1}{2}x^{2},\forall x\geq 0$ as follows

$\displaystyle\frac{W_{i,t+1}}{W_{i,t}}\leq\sum_{j\in{\mathbb{N}}_{i}^{\text{out}}}{\frac{w_{j,t}}{W_{i,t}}\left(1-\eta\ell_{j,t}+\frac{1}{2}(\eta\ell_{j,t})^{2}\right)}.$
(59)

Taking the logarithm from both sides of (59) and using the inequality $1+x\leq
e^{x}$, we get

$\displaystyle\ln\frac{W_{i,t+1}}{W_{i,t}}\leq\sum_{j\in{\mathbb{N}}_{i}^{\text{out}}}{\frac{w_{j,t}}{W_{i,t}}\left(-\eta\ell_{j,t}+\frac{1}{2}(\eta\ell_{j,t})^{2}\right)}.$
(60)

Summing (60) over time, we obtain

$\displaystyle\ln\frac{W_{i,T+1}}{W_{i,1}}\leq\sum_{t=1}^{T}{\sum_{j\in{\mathbb{N}}_{i}^{\text{out}}}{\frac{w_{j,t}}{W_{i,t}}\left(-\eta\ell_{j,t}+\frac{1}{2}(\eta\ell_{j,t})^{2}\right)}}.$
(61)

Moreover, for any $j\in{\mathbb{N}}_{i}^{\text{out}}$,
$\ln\frac{W_{i,T+1}}{W_{i,1}}$ can be bounded from below as

$\displaystyle\ln\frac{W_{i,T+1}}{W_{i,1}}\geq\ln\frac{w_{j,T+1}}{W_{i,1}}=-\sum_{t=1}^{T}{\eta\ell_{j,t}}-\ln|{\mathbb{N}}_{i}^{\text{out}}|$
(62)

Combining (61) with (62), it can concluded that

$\displaystyle\sum_{t=1}^{T}{\sum_{j\in{\mathbb{N}}_{i}^{\text{out}}}{\frac{w_{j,t}}{W_{i,t}}\ell_{j,t}}}-\sum_{t=1}^{T}{\ell_{j,t}}\leq\frac{\ln|{\mathbb{N}}_{i}^{\text{out}}|}{\eta}+\frac{\eta}{2}\sum_{t=1}^{T}{\sum_{j\in{\mathbb{N}}_{i}^{\text{out}}}{\frac{w_{j,t}}{W_{i,t}}\ell_{j,t}^{2}}}.$
(63)

For the expected value of $\ell_{i,t}$ and $\ell_{i,t}^{2}$, we have

$\displaystyle\mathbb{E}_{t}[\ell_{j,t}]$
$\displaystyle=\sum_{k\in{\mathbb{N}}_{i}^{\text{out}}}{p_{k,t}\frac{{\mathcal{L}}({\bm{\theta}}_{j,t}^{\top}{\mathbf{z}}_{j}({\bm{x}}_{t}),y_{t})}{q_{j,t}}}={\mathcal{L}}({\bm{\theta}}_{j,t}^{\top}{\mathbf{z}}_{j}({\bm{x}}_{t}),y_{t})$
(64a) $\displaystyle\mathbb{E}_{t}[\ell_{j,t}^{2}]$
$\displaystyle=\sum_{k\in{\mathbb{N}}_{i}^{\text{out}}}{p_{k,t}\frac{{\mathcal{L}}^{2}({\bm{\theta}}_{j,t}^{\top}{\mathbf{z}}_{j}({\bm{x}}_{t}),y_{t})}{q_{j,t}^{2}}}=\frac{{\mathcal{L}}^{2}({\bm{\theta}}_{j,t}^{\top}{\mathbf{z}}_{j}({\bm{x}}_{t}),y_{t})}{q_{j,t}}\leq\frac{1}{q_{j,t}}$
(64b)

Taking the expectation from (63), we get

$\displaystyle\sum_{t=1}^{T}{\sum_{j\in{\mathbb{N}}_{i}^{\text{out}}}{\frac{w_{j,t}}{W_{i,t}}{\mathcal{L}}({\bm{\theta}}_{j,t}^{\top}{\mathbf{z}}_{j}({\bm{x}}_{t}),y_{t})}}-\sum_{t=1}^{T}{{\mathcal{L}}({\bm{\theta}}_{j,t}^{\top}{\mathbf{z}}_{j}({\bm{x}}_{t}),y_{t})}$
$\displaystyle\leq\frac{\ln|{\mathbb{N}}_{i}^{\text{out}}|}{\eta}+\frac{\eta}{2}\sum_{t=1}^{T}{\sum_{j\in{\mathbb{N}}_{i}^{\text{out}}}{\frac{w_{j,t}}{q_{j,t}W_{i,t}}}}.$
(65)

Let
$\frac{1}{\bar{q}_{i,t}}=\sum_{j\in{\mathbb{N}}_{i}^{\text{out}}}{\frac{w_{j,t}}{q_{j,t}W_{i,t}}}$
which is the weighted sum of $\frac{1}{q_{j,t}}$ such that
$j\in{\mathbb{N}}_{i}^{\text{out}}$. Furthermore, according to (13), the loss
${\mathcal{L}}_{i}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})$ can be written as

$\displaystyle{\mathcal{L}}_{i}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})={\mathcal{L}}(\sum_{j\in{\mathbb{N}}_{i}^{\text{out}}}{\frac{w_{j,t}}{W_{i,t}}\hat{f}_{\text{RF},j}({\bm{x}}_{t})},y_{t}).$
(66)

Based on the Jensen’s inequality
${\mathcal{L}}_{i}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})$ can be bounded
from above as

$\displaystyle{\mathcal{L}}_{i}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})\leq\sum_{j\in{\mathbb{N}}_{i}^{\text{out}}}{\frac{w_{j,t}}{W_{i,t}}{\mathcal{L}}(\hat{f}_{\text{RF},j}({\bm{x}}_{t}),y_{t})}.$
(67)

Using (65) and (67), we can conclude that

$\displaystyle\sum_{t=1}^{T}{{\mathcal{L}}_{i}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})}-\sum_{t=1}^{T}{{\mathcal{L}}({\bm{\theta}}_{j,t}^{\top}{\mathbf{z}}_{j}({\bm{x}}_{t}),y_{t})}\leq\frac{\ln|{\mathbb{N}}_{i}^{\text{out}}|}{\eta}+\frac{\eta}{2}\sum_{t=1}^{T}{\frac{1}{\bar{q}_{i,t}}}$
(68)

which proves the Lemma 7. ∎

Combining Lemma 6 with Lemma 7, for any $v_{j}\in{\mathcal{V}}$ and any
$i\in{\mathbb{N}}_{j}^{\text{in}}$ we obtain

$\displaystyle\sum_{t=1}^{T}{\mathbb{E}_{t}[{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})]}-\sum_{t=1}^{T}{{\mathcal{L}}(\hat{f}_{\text{RF},j}({\bm{x}}_{t}),y_{t})}$
$\displaystyle\leq\frac{\ln
N|{\mathbb{N}}_{i}^{\text{out}}|}{\eta}+(\xi+\frac{\eta
N}{2}-\frac{\eta\xi}{2})T+\frac{\eta}{2}\sum_{t=1}^{T}{\frac{1}{\bar{q}_{i,t}}}.$
(69)

In addition, combining Lemma 5 with (69), for any $v_{j}\in{\mathcal{V}}$ and
any $i\in{\mathbb{N}}_{j}^{\text{in}}$ we can write

$\displaystyle\sum_{t=1}^{T}{\mathbb{E}_{t}[{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})]}-\sum_{t=1}^{T}{{\mathcal{L}}(\hat{f}_{j}^{*}({\bm{x}}_{t}),y_{t})}$
$\displaystyle\leq\frac{\ln
N|{\mathbb{N}}_{i}^{\text{out}}|}{\eta}+\frac{\|{\bm{\theta}}_{j}^{*}\|^{2}}{2\eta}+(\xi+\frac{\eta
N}{2}-\frac{\eta\xi}{2})T+\frac{\eta}{2}\sum_{t=1}^{T}{(\frac{1}{\bar{q}_{i,t}}+\frac{L^{2}}{q_{j,t}})}$
(70)

We use the above inequality as a step-stone to prove Theorem 3.

For a given shift invariant kernel $\kappa_{i}$, the maximum point-wise error
of the random feature kernel approximant is uniformly bounded with probability
at least
$1-2^{8}(\frac{\sigma_{i}}{\epsilon})^{2}\exp(-\frac{D\epsilon^{2}}{4d+8})$,
by Rahimi and Recht (2007)

$\displaystyle\sup_{{\bm{x}}_{j},{\bm{x}}_{k}\in{\mathcal{X}}}{|{\mathbf{z}}_{i}^{\top}({\bm{x}}_{j}){\mathbf{z}}_{i}({\bm{x}}_{k})-\kappa_{i}({\bm{x}}_{j},{\bm{x}}_{k})|}<\epsilon$
(71)

where $\sigma_{i}^{2}$ is the second moment of the Fourier transform of
$\kappa_{i}$. Therefore, under (a3) this implies that
$\sup_{{\bm{x}}_{\tau},{\bm{x}}_{t}\in{\mathcal{X}}}{\mathbf{z}}_{i}^{\top}({\bm{x}}_{\tau}){\mathbf{z}}_{i}({\bm{x}}_{t})\leq
1+\epsilon$ holds with probability at least
$1-2^{8}(\frac{\sigma_{i}}{\epsilon})^{2}\exp(-\frac{D\epsilon^{2}}{4d+8})$.
Let $C:=\max_{n}\sum_{t=1}^{T}{|{\alpha}_{n,t}^{*}|}$. Hence,
$\|{\bm{\theta}}_{j}^{*}\|^{2}$ can be bounded from above as

$\displaystyle\|{\bm{\theta}}_{j}^{*}\|^{2}\leq\|\sum_{t=1}^{T}{\alpha_{j,t}^{*}{\mathbf{z}}_{j}({\bm{x}}_{t})\|^{2}}\leq|\sum_{t=1}^{T}{\sum_{\tau=1}^{T}{\alpha_{j,t}^{*}\alpha_{j,\tau}^{*}{\mathbf{z}}_{j}^{\top}({\bm{x}}_{t}){\mathbf{z}}_{j}({\bm{x}}_{\tau})|}}\leq(1+\epsilon)C^{2}$
(72)

with probability at least
$1-2^{8}(\frac{\sigma_{i}}{\epsilon})^{2}\exp(-\frac{D\epsilon^{2}}{4d+8})$.
Moreover, using the triangle inequality yields

$\displaystyle\left|\sum_{t=1}^{T}{{\mathcal{L}}(\hat{f}_{j}^{*}({\bm{x}}_{t}),y_{t})}-\sum_{t=1}^{T}{{\mathcal{L}}(f_{j}^{*}({\bm{x}}_{t}),y_{t})}\right|$
$\displaystyle\leq$
$\displaystyle\sum_{t=1}^{T}\left|{{\mathcal{L}}(\hat{f}_{j}^{*}({\bm{x}}_{t}),y_{t})}-{{\mathcal{L}}(f_{j}^{*}({\bm{x}}_{t}),y_{t})}\right|.$
(73)

According to Lipschitz continuity of the loss function, it can be concluded
that

$\displaystyle\sum_{t=1}^{T}\left|{{\mathcal{L}}(\hat{f}_{j}^{*}({\bm{x}}_{t}),y_{t})}-{{\mathcal{L}}(f_{j}^{*}({\bm{x}}_{t}),y_{t})}\right|$
$\displaystyle\leq\sum_{t=1}^{T}{L\left|\sum_{\tau=1}^{T}{{\alpha}_{j,\tau}^{*}{\mathbf{z}}_{j}^{\top}({\bm{x}}_{\tau}){\mathbf{z}}_{n}({\bm{x}}_{t})}-\sum_{\tau=1}^{T}{{\alpha}_{j,\tau}^{*}\kappa_{j}({\bm{x}}_{\tau},{\bm{x}}_{t})}\right|}.$
(74)

Using the Cauchy-Schwartz inequality, we can write

$\displaystyle\sum_{t=1}^{T}{L\left|\sum_{\tau=1}^{T}{{\alpha}_{j,\tau}^{*}{\mathbf{z}}_{j}^{\top}({\bm{x}}_{\tau}){\mathbf{z}}_{n}({\bm{x}}_{t})}-\sum_{\tau=1}^{T}{{\alpha}_{j,\tau}^{*}\kappa_{j}({\bm{x}}_{\tau},{\bm{x}}_{t})}\right|}$
$\displaystyle\leq\sum_{t=1}^{T}{L\sum_{\tau=1}^{T}{|{\alpha}_{j,\tau}^{*}|\left|{\mathbf{z}}_{j}^{\top}({\bm{x}}_{\tau}){\mathbf{z}}_{j}({\bm{x}}_{t})-\kappa_{j}({\bm{x}}_{\tau},{\bm{x}}_{t})\right|}}.$
(75)

Using (71) and (75), we can conclude that the inequality

$\displaystyle\sum_{t=1}^{T}{{\mathcal{L}}(\hat{f}_{j}^{*}({\bm{x}}_{t}),y_{t})}-\sum_{t=1}^{T}{{\mathcal{L}}(f_{j}^{*}({\bm{x}}_{t}),y_{t})}\leq\epsilon
LTC$ (76)

holds with probability at least
$1-2^{8}(\frac{\sigma_{i}}{\epsilon})^{2}\exp(-\frac{D\epsilon^{2}}{4d+8})$.
Therefore, combining (70) with (72) and (76), it can be inferred that the
following inequality

$\displaystyle\sum_{t=1}^{T}{\mathbb{E}_{t}[{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})]}-\sum_{t=1}^{T}{{\mathcal{L}}(f_{j}^{*}({\bm{x}}_{t}),y_{t})}$
$\displaystyle\leq\frac{\ln
N|{\mathbb{N}}_{i}^{\text{out}}|}{\eta}+\frac{(1+\epsilon)C^{2}}{2\eta}+\epsilon
LTC+(\xi+\frac{\eta
N}{2}-\frac{\eta\xi}{2})T+\frac{\eta}{2}\sum_{t=1}^{T}{(\frac{1}{\bar{q}_{i,t}}+\frac{L^{2}}{q_{j,t}})}$
(77)

holds for any $v_{j}\in{\mathcal{V}}$ and any
$i\in{\mathbb{N}}_{j}^{\text{in}}$ with probability at least
$1-2^{8}(\frac{\sigma_{i}}{\epsilon})^{2}\exp(-\frac{D\epsilon^{2}}{4d+8})$.
This completes the proof of Theorem 3.

##  Appendix C Proof of Theorem 4

According to Theorem 3, the following inequality

$\displaystyle\sum_{t=1}^{T}{\mathbb{E}_{t}[{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})]}-\sum_{t=1}^{T}{{\mathcal{L}}(f^{*}({\bm{x}}_{t}),y_{t})}$
$\displaystyle\leq\frac{\ln
N|{\mathbb{N}}_{i}^{\text{out}}|}{\eta}+\frac{(1+\epsilon)C^{2}}{2\eta}+\epsilon
LTC+(\xi+\frac{\eta
N}{2}-\frac{\eta\xi}{2})T+\frac{\eta}{2}\sum_{t=1}^{T}{(\frac{1}{\bar{q}_{i,t}}+\frac{L^{2}}{q_{j^{*},t}})}$
(78)

holds with probability at least
$1-2^{8}(\frac{\sigma_{j^{*}}}{\epsilon})^{2}\exp(-\frac{D\epsilon^{2}}{4d+8})$
for any $\epsilon>0$ and any $i\in{\mathbb{N}}_{j^{*}}^{\text{in}}$. When
${\mathcal{G}}_{t}^{\prime}$ is generated by Algorithm 3 as the feedback
graph, ${\mathbb{D}}_{t}^{\prime}$ is a dominating set of
${\mathcal{G}}_{t}^{\prime}$. Furthermore, $k\in{\mathbb{D}}_{t}^{\prime}$ if
$p_{k,t}\geq\beta$. Based on (15), if $i\in{\mathbb{N}}_{k,t}^{\text{in}}$
(i.e. in-neighborhood of $v_{k}$ in ${\mathcal{G}}_{t}^{\prime}$),
$q_{k,t}\geq p_{i,t}$. Also, considering the condition $\beta\leq\frac{1}{N}$,
it is ensured that ${\mathbb{D}}_{t}^{\prime}$ is not an empty set. Moreover,
each node $v_{k}$ in ${\mathcal{G}}_{t}^{\prime}$ is out-neighbor of at least
one node in ${\mathbb{D}}_{t}^{\prime}$. Thus, we can conclude that
$q_{k,t}\geq\beta$, $\forall v_{k}\in{\mathcal{V}}$. Hence, it can be written
that

$\displaystyle\sum_{t=1}^{T}{(\frac{1}{\bar{q}_{i,t}}+\frac{L^{2}}{q_{j^{*},t}})}\geq\sum_{t=1}^{T}{(\sum_{j\in{\mathbb{N}}_{i}^{\text{out}}}{\frac{w_{j,t}}{W_{i,t}\beta}}+\frac{L^{2}}{\beta})}=\frac{(L^{2}+1)T}{\beta}.$
(79)

Furthermore, since $|{\mathbb{N}}_{i}^{\text{out}}|\leq N$, we have
$N|{\mathbb{N}}_{i}^{\text{out}}|\leq N^{2}$. Combining (78) with (79), it can
be inferred that in this case the stochastic regret of SFG-MKL-R satisfies

$\displaystyle\sum_{t=1}^{T}{\mathbb{E}_{t}[{\mathcal{L}}(\hat{f}_{\text{RF}}({\bm{x}}_{t}),y_{t})]}-\sum_{t=1}^{T}{{\mathcal{L}}(f^{*}({\bm{x}}_{t}),y_{t})}$
$\displaystyle\leq\frac{2\ln N}{\eta}+\frac{(1+\epsilon)C^{2}}{2\eta}+\epsilon
LTC+(\xi+\frac{\eta}{2}\frac{L^{2}+N\beta+1}{\beta}-\frac{\eta\xi}{2})T$ (80)

with probability at least
$1-2^{8}(\frac{\sigma_{j^{*}}}{\epsilon})^{2}\exp(-\frac{D\epsilon^{2}}{4d+8})$
under (as1)-(as3) for any $\epsilon>0$ and any
$\beta\leq(1-\xi)\max_{k}\frac{u_{k,t}}{U_{t}}+\frac{\xi}{N}$. This completes
the proof of Theorem 4.