Online Linearized Confidence‐Weighted Learning on a Budget

Abstract

Online learning aims to solve a sequence of consecutive prediction tasks by leveraging the knowledge gained from previous tasks. Linearized confidence‐weighted (LCW) learning is the first online learning algorithm introducing the concept of weight confidence into the prediction model through distributions over weights. It provides the flexibility for weights to update their values at different scales. The kernel trick in machine learning can be applied to LCW for a better prediction performance. However, the kernel‐based LCW algorithm is subject to the curse of kernelization which makes it vulnerable to the unlimited growth of the prediction model in runtime and memory consumption. In this study, we present the budgeted LCW (BLCW) algorithm which puts a limit on the growth by a predefined budget with optimization. Consequently, BLCW performs the LCW update and then reduces the information loss by projection. Based on the resource perspective that reinterprets LCW in terms of resources and utilization degrees, we demonstrated that BLCW approximates the kernel‐based LCW algorithm. We evaluate four budget maintenance strategies and suggest that the mean removal is the most stable. By various numerical experiments on real datasets, we demonstrate that BLCW performs competitively and effectively when compared to leading budgeted online algorithms.

Introduction

Online learning is a branch of machine learning and has been studied extensively in recent years.^[1–10] It aims to solve a sequence of consecutive prediction tasks by leveraging the knowledge gained from previous tasks. The goal is to make accurate predictions about the sequence. This is different from traditional offline machine learning methods that aim to learn a prediction model from the entire training set. Online learning plays an important role in practical applications involving continuous streaming of data, such as ad click-through rate prediction,^[11] online collaborative filtering,^[12] online malicious URL detection,^[13] and online portfolio selection.^[14]

In this article, we focus on the problem of online classification for online learning. Many online algorithms have been proposed to deal with successive binary classification tasks. A typical online algorithm employs a binary discriminant based on a linear hypothesis to make the prediction and updates the model for future tasks. For example, the well-known Perceptron algorithm performs a mistake-driven update to the hypothesis.^[15–17] The online gradient descent (OGD) algorithm updates the hypothesis according to the direction of the current gradient.^[18] Crammer et al.^[19] presented the passive-aggressive (PA) algorithm, which enables a loss-driven update by utilizing the notion of margin, and two variants of PA that further take the presence of noise into consideration. On top of the PA algorithm, confidence-weighted (CW) and linearized confidence-weighted (LCW) algorithms include the notion of weight confidence through probability distributions.^[20–22] Soft confidence-weighted (SCW) learning introduces the concept of a loss function to the CW algorithm such that the update will be less aggressive as compared to reacting to noising examples.^[23,24] When it comes to handling successive multiclass classification tasks, most research works targeted primarily extending online algorithms for binary problems to multiclass problems. This results in a bunch of multiclass-oriented online algorithms that employ a multiclass discriminant based on multiple linear hypotheses: MIRA,^[25] multiclass PA,^[19,26] multiclass CW,^[27] and so on. However, the prediction performance may be limited by the linearity, and thus superior feature extraction is required for complex problems to achieve satisfying performance.

The kernel trick in machine learning provides a way to bypass the linearity.^[28] It kernelizes a learning algorithm by substituting all inner products in the algorithm with kernel functions, e.g., the Gaussian kernel.^[29] Since many online algorithms can be kernelized, they are able to employ a discriminant based on a nonlinear hypothesis (or multiple nonlinear hypotheses) composed of kernel functions to reach a satisfying prediction performance. However, a kernel-based online algorithm has the storage requirement of support vectors (SVs) and corresponding combination coefficients for constructing a hypothesis. This causes the kernelization of an online algorithm suffers from the unlimited growth in runtime and memory consumption as more and more tasks are done. This phenomenon is known as the curse of kernelization and may lead to a broken-down situation for a kernel-based online algorithm. Some works stop the growth by setting a limit on the maximum number of SVs. For example, the budget Perceptron algorithm controls the number of SVs by removing the support element (SE) whose removal gives the maximum margin.^[30] The Forgetron algorithm shrinks the hypothesis and then discards the oldest SE.^[31] The randomized budget Perceptron (RBP) algorithm selects randomly an SE for removal.^[32] The Projectron and Projectron++ algorithms bound the growth by projecting the kernel function of the current instance onto the subspace, which is spanned by the kernel functions centered on SVs.^[33] In contrast, both Fourier OGD (FOGD) and Nyström OGD (NOGD) algorithms transform a nonlinear hypothesis into a linear hypothesis by a kernel-induced feature approximation and then apply the OGD algorithm.^[34,35] Some kernel-based online algorithms are further extended to solve multiclass problems, such as multiclass Projectron++,^[33] MFOGD, and MNOGD.^[34,35]

Among state-of-the-art online algorithms, both CW and LCW algorithms introduce the weight confidence by using Gaussian distributions. They determine the update by a constrained optimization problem; the only difference between them is the optimization constraint that ensures a sufficiently large margin. As compared with the Perceptron and PA algorithms, the weight confidence allows each weight to be updated at a different scale and thus have a better prediction performance.^[22] The CW algorithm serves as the basis to design SCW-I and SCW-II algorithms.^[23] Both CW and LCW algorithms are extended to multiclass-oriented algorithms for solving multiclass problems.^[24,27] Moreover, they can be kernelized to employ a nonlinear hypothesis for a better prediction performance, but they are still subject to the curse of kernelization that makes them hard to operate in practical applications where limited computing power is available. However, to the best of our knowledge, there exists no research work aiming at breaking the curse for the CW or LCW algorithm. It is worth studying how to overcome this issue for the CW or LCW algorithm; as a consequence, a nonlinear hypothesis can be employed safely in practical applications. In addition, this study may give a clue about how to break the curse for CW- or LCW-based algorithm, such as SCW-I and SCW-II.

In this article, we try to break the curse of kernelization for the kernel-based LCW algorithm, which is the LCW algorithm kernelized by the kernel trick. We propose to control the growth by putting a limit on the maximum number of SVs by the budget, which is a predefined value. Since controlling the growth gives rise to some sacrifice in the prediction performance, the challenge is how to maintain the performance by means of reducing the information loss in the hypothesis. To deal with the challenge, we proposed the budgeted LCW (BLCW) algorithm that controls the growth by the budget and utilizes projections to reduce the information loss. Specifically, the following contributions are made in this article. 1) The resource perspective is introduced to the kernel-based LCW algorithm. From the resource perspective, we treat each receiving instance as a possible resource and the kernel-based LCW algorithm as the resource manager that exploits available resources for building the hypothesis for prediction. It gives an alternative and equivalent interpretation of the kernel-based LCW algorithm. 2) Based on the resource perspective, we propose the BLCW algorithm that approximates the kernel-based LCW algorithm by exploiting a limited number of available resources. The BLCW algorithm reduces the information loss in the hypothesis by projections, which keep the information of the discarded resource. 3) We study four kinds of removal strategies for maintaining the budget and suggest the mean removal strategy as the default for the proposed BLCW algorithm due to its good and stable performance. 4) We verify the proposed BLCW algorithm and the removal strategies by conducting various numerical experiments on real datasets.

For streaming applications that receive data in terms of a sequence of examples, we often assume that their targets are generated according to a specific function or distribution. The assumption may not hold true all the time, and the problem of concept drift can result in the dynamic problem that the targeted function or distribution is changed overtime.^[36,37] Many methods are proposed to solve this problem. For example, leveraging bagging,^[38] adaptive random forests,^[39] and Kappa updated ensemble^[40] are ensemble learning-based methods. In addition to ensemble learning techniques, EAL-MAB^[41] and MD-OAL^[42] further extend to the realm of active learning under a limited labeling budget. In addition, the PA algorithm with the unlearning framework has been studied for the adaption of concept drift overtime.^[43] Since the LCW algorithm is based on the PA algorithm, it can be applied to address this issue. The objective of this study is to develop a budgeted online algorithm that is capable of implementing the LCW algorithm while operating under the constraint of limited computational power. The budget used in this study corresponds to the maximum number of instances that can be used to represent the prediction model, while we always query the labels of the encountered instances.

The rest of the article is organized as follows. Section 2 reviews the CW and LCW algorithms, and the kernelization of LCW. In Section 3, the resource perspective is introduced to the kernel-based LCW algorithm, followed by the proposed BLCW algorithm and four removal strategies for budget maintenance. Numerical experiments are conducted in Section 4. We give the conclusions in Section 5, followed by discussions of limitations and possible future directions.

Problem Setting and Background

In this section, we review the CW and LCW algorithms and discuss their difference. Then, we introduce the kernelization of LCW. We consider the problem of online binary classification. It is performed in a sequence of consecutive rounds. Figure 1 depicts the typical flow of online learning in a round. On round t, the learner first receives an instance $x_t\in \mathcal{X}$, where $\mathcal{X}$ is a predefined instance domain. Based on some prediction rule, the learner predicts the class label ${\widehat{y}}_t\in \{-\mathrm{1,}+1\}$ and later receives the correct class label $y_t\in \{-\mathrm{1,}+1\}$. Then, the learner updates the prediction rule for future rounds by using the current example $(x_t,y_t)$. The goal of online learning is to have as many correct predictions as possible for the given sequence.

[IMAGE OMITTED. SEE PDF]

Let us first delve into the prediction part of online learning. On round t, an online algorithm employs a binary discriminant based on a linear hypothesis composed of an inner product,^[21]1$f_t\left(x\right)=\mathit{\varphi }{\left(x\right)}^{\top }{\mathbf{w}}_t$which is characterized by the weight vector ${\mathbf{w}}_t\in {ℝ}^d$. $\mathit{\varphi }:\mathcal{X}\to {ℝ}^d$ acts as feature extraction which maps instances into the desired feature space. $\text{sign}\left(\mathit{\varphi }{\left(x_t\right)}^{\top }{\mathbf{w}}_t\right)\in \{-1,+1\}$ predicts the class label of the instance $x_t$, and $\mathit{\varphi }{\left(x\right)}^{\top }{\mathbf{w}}_t=0$ defines a linear decision boundary for instances in the feature space. The magnitude $\left|\mathit{\varphi }{\left(x_t\right)}^{\top }{\mathbf{w}}_t\right|$ is interpreted as the confidence in this prediction.

Based on the aforementioned setting for the linear hypothesis, both CW and LCW algorithms further introduce a Gaussian distribution over the weight vector,^[21]2${\mathbf{w}}_t\sim \mathcal{N}({\mathit{\mu }}_t,{\mathbf{\Sigma }}_t)$with the mean vector ${\mathit{\mu }}_t\in {ℝ}^d$ and the covariance matrix ${\mathbf{\Sigma }}_t\in {\mathbf{S}}_{++}^d$. We denote by ${\mathbf{S}}_{++}^d$ the set of symmetric positive definite $d\times d$ matrices.^[44] Entries of ${\mathit{\mu }}_t$ represent the knowledge of features, and diagonal entries of ${\mathbf{\Sigma }}_t$ stand for the confidence in the weights. The larger a diagonal entry, the less confident in the corresponding weight, and vice versa. Off-diagonal entries record the knowledge of interactions among features. The Gaussian distribution captures the idea of confidence in weights, and hence both CW and LCW algorithms get the adjective term, “confidence-weighted”.

With the adoption of the Gaussian distribution, both CW and LCW algorithms predict the class label of the instance $x_t$ by using the mean value of $\mathit{\varphi }{\left(x_t\right)}^{\top }{\mathbf{w}}_t$,3${\widehat{y}}_t=\text{sign}\left(\mathbb{E}\right[{\mathit{\varphi }}_t^{\top }{\mathbf{w}}_t\left]\right)=\text{sign}\left({\mathit{\varphi }}_t^{\top }{\mathit{\mu }}_t\right)$where ${\mathit{\varphi }}_t^{\top }{\mathbf{w}}_t\sim \mathcal{N}({\mathit{\varphi }}_t^{\top }{\mathit{\mu }}_t,{\mathit{\varphi }}_t^{\top }{\mathbf{\Sigma }}_t{\mathit{\varphi }}_t)$. For simplicity of notation, we denote by ${\mathit{\varphi }}_a$ the feature vector of $x_a$, $\mathit{\varphi }(x_a)$, from now on. The variance of ${\mathit{\varphi }}_t^{\top }{\mathbf{w}}_t$, ${\mathit{\varphi }}_t^{\top }{\mathbf{\Sigma }}_t{\mathit{\varphi }}_t$, can be used to describe the confidence in this prediction: the smaller the variance, the more confidence we have in this prediction, and vice versa. Once the correct class label $y_t$ is received, the prediction performance is evaluated by computing the corresponding prediction mistake4$\mathbb{I}({\widehat{y}}_t\ne y_t)=\{\begin{array}{cc}1& \text{if }{\widehat{y}}_t\ne y_t\\ 0& \text{if }{\widehat{y}}_t=y_t\end{array}$

Before going to the next round, both CW and LCW algorithms determine the update of the linear hypothesis for future rounds by solving a constrained optimization problem. The new hypothesis is5$f_{t+1}\left(x\right)=\mathit{\varphi }{\left(x\right)}^{\top }{\mathbf{w}}_{t+1},{\mathbf{w}}_{t+1}\sim \mathcal{N}({\mathit{\mu }}_{t+1},{\mathbf{\Sigma }}_{t+1})$where $({\mathit{\mu }}_{t+1},{\mathbf{\Sigma }}_{t+1})$ is the solution of the optimization problem. This constitutes the learning part of online learning. However, the optimization problem for both algorithms is related but different.

CW Algorithm

We review the update on round t for the CW algorithm. Because the hypothesis $f_t$ in the CW algorithm is parameterized by a weight vector ${\mathbf{w}}_t$ following a Gaussian distribution $\mathcal{N}({\mathit{\mu }}_t,{\mathbf{\Sigma }}_t)$, it is equivalent to that $f_t$ is determined by $\mathcal{N}({\mathit{\mu }}_t,{\mathbf{\Sigma }}_t)$. It is natural that the updated hypothesis $f_{t+1}$ is required to be parameterized by a new weight vector ${\mathbf{w}}_{t+1}$ following a new Gaussian distribution $\mathcal{N}({\mathit{\mu }}_{t+1},{\mathbf{\Sigma }}_{t+1})$ (cf. Equation (5)), or equivalently, that $f_{t+1}$ is determined by $\mathcal{N}({\mathit{\mu }}_{t+1},{\mathbf{\Sigma }}_{t+1})$.

Thus, the update of the CW algorithm is determined by the solution of the following constrained optimization problem involving two Gaussian distributions,6$\begin{array}{lll}\underset{\mathit{\mu },\mathbf{\Sigma }}{\text{minimize}}& & D_{\text{KL}}\left(\mathcal{N}\right(\mathit{\mu },\mathbf{\Sigma })\parallel \mathcal{N}({\mathit{\mu }}_t,{\mathbf{\Sigma }}_t\left)\right)\\ \text{subject} \text{to}& & \mathbb{P}\left[y_t\right({\mathit{\varphi }}_t^{\top }\mathbf{w})\ge 0]\ge \eta ,\end{array}$where $D_{\text{KL}}(\cdot \parallel \cdot )$ is the Kullback–Leibler (KL) divergence between two distributions, and $\mathbb{P}[\cdot ]$ measures the probability that depends on $\mathbf{w}\sim \mathcal{N}(\mathit{\mu },\mathbf{\Sigma })$ with $\mathit{\mu }\in {ℝ}^d$ and $\Sigma \in {\mathbf{S}}_{++}^d$. $\eta \in (\mathrm{0.5,1}]$ is a predefined probability threshold. Since the KL divergence can be interpreted as a measure of the difference between two distributions, this optimization problem aims to find the new Gaussian distribution that has minimum change in the distribution while ensuring enough probability of a correct prediction on the current example $(x_t,y_t)$.

Equation (6) can be rewritten as the following equivalent problem7$\begin{array}{ll}\underset{\mathit{\mu },\mathbf{\Sigma }}{\text{minimize}}& \frac{1}{2}\log \left(\frac{\det {\mathbf{\Sigma }}_t}{\det \mathbf{\Sigma }}\right)+\frac{1}{2}\text{tr}\left({\mathbf{\Sigma }}_t^{-1}\mathbf{\Sigma }\right)+\frac{1}{2}{({\mathit{\mu }}_t-\mathit{\mu })}^{\top }{\mathbf{\Sigma }}_t^{-1}({\mathit{\mu }}_t-\mathit{\mu })\\ \text{subject to}& y_t\left({\mathit{\varphi }}_t^{\top }\mathit{\mu }\right)\ge \psi \sqrt{{\mathit{\varphi }}_t^{\top }\mathbf{\Sigma }{\mathit{\varphi }}_t}\end{array}$where $\psi ={\Psi }^{-1}(\eta )$ and $\Psi (z)=\frac{1}{\sqrt{2\pi }}{\int }_{-\infty }^z{e}^{-u^2/2}du$ is the cumulative distribution function of a standard normal distribution. We can observe from the constraint of Equation (7) that a correct prediction is not good enough for the CW algorithm; it demands a sufficiently large margin that is basically determined by the standard deviation of ${\mathit{\varphi }}_t^{\mathrm{T}}{\mathbf{w}}_t$. In other words, the more confident in the prediction, the less strict in the constraint, and vice versa. Although the objective function of Equation (7) is convex in $(\mathit{\mu },\mathbf{\Sigma })$, Equation (7) is not a convex optimization problem because the standard deviation term of the constraint, $\sqrt{{\mathit{\varphi }}_t^{\top }\mathbf{\Sigma }{\mathit{\varphi }}_t}$, is concave in $\mathbf{\Sigma }$.^[44] To conquer this difficult situation, Crammer et al.^[21] have proposed two alternatives to transform Equation (7) into a convex problem. One of them is to perform a change of variables from $\mathbf{\Sigma }$ to another symmetric positive definite matrix $\mathbf{\Gamma }$ such that ${\mathbf{\Gamma }}^2=\mathbf{\Sigma }$ and solve the corresponding convex optimization problem.^[22] This gives the update rule of the CW algorithm. The other alternative is to linearize the constraint by ignoring the square root of the standard deviation term and solve the corresponding convex optimization problem.^[20] This leads to the update rule of the LCW algorithm, which will be discussed in more detail in the next section.

LCW Algorithm

The LCW algorithm is the core algorithm we use to propose the budgeted algorithm. On round t, it modifies the constraint of Equation (7) to a linearized form by omitting the square root and obtains a new constrained optimization problem as follows8$\begin{array}{ll}\underset{\mathit{\mu },\mathbf{\Sigma }}{\text{minimize}}& \frac{1}{2}\log \left(\frac{\det {\mathbf{\Sigma }}_t}{\det \mathbf{\Sigma }}\right)+\frac{1}{2}\text{tr}\left({\mathbf{\Sigma }}_t^{-1}\mathbf{\Sigma }\right)+\frac{1}{2}{({\mathit{\mu }}_t-\mathit{\mu })}^{\top }{\mathbf{\Sigma }}_t^{-1}({\mathit{\mu }}_t-\mathit{\mu })\\ \text{subject} \text{to}& y_t\left({\mathit{\varphi }}_t^{\top }\mathit{\mu }\right)\ge \psi \left({\mathit{\varphi }}_t^{\top }\mathbf{\Sigma }{\mathit{\varphi }}_t\right)\end{array}$which aims to find the new Gaussian distribution that has minimum change in the distribution while preserving the property of a sufficiently large margin by using the variance of ${\mathit{\varphi }}_t^{\top }{\mathbf{w}}_t$, ${\mathit{\varphi }}_t^{\top }\mathbf{\Sigma }{\mathit{\varphi }}_t$, instead of the standard deviation. The constraint of Equation (8) can be rewritten as the following probability constraint similar to that of Equation (6),9$\mathbb{P}\left[y_t\right({\mathit{\varphi }}_t^{\top }\mathbf{w})\ge 0]\ge \Psi \left({\Psi }^{-1}\right(\eta \left)\sqrt{{\mathit{\varphi }}_t^{\top }\mathbf{\Sigma }{\mathit{\varphi }}_t}\right)$which is equivalent to introduce a standard deviation term to the confidence parameter η of the CW algorithm. Compared with η, the new confidence parameter ${\eta }^{\prime }=\Psi \left({\Psi }^{-1}\right(\eta \left)\sqrt{{\mathit{\varphi }}_t^{\top }\mathbf{\Sigma }{\mathit{\varphi }}_t}\right)$ associated with the LCW algorithm will be amplified or shrunk according to that the standard deviation is larger or smaller than 1. Finally, a closed-form solution exists for Equation (8) and determines the update rule for the LCW algorithm:10a${\mathit{\mu }}_{t+1}={\mathit{\mu }}_t+{\tau }_t{y}_t{\mathbf{\Sigma }}_t{\mathit{\varphi }}_t$10b${\mathbf{\Sigma }}_{t+1}={\mathbf{\Sigma }}_t-{\lambda }_t{\mathbf{\Sigma }}_t{\mathit{\varphi }}_t{\mathit{\varphi }}_t^{\top }{\mathbf{\Sigma }}_t$where $m^t=y_t\left({\mathit{\varphi }}_t^{\top }{\mathit{\mu }}_t\right)$, $v^t={\mathit{\varphi }}_t^{\top }{\mathbf{\Sigma }}_t{\mathit{\varphi }}_t$,11a${\tau }_t=\max \left\{\mathrm{0,}\frac{-(1+2\psi m^t)+\sqrt{{(1+2\psi m^t)}^2-8\psi (m^t-\psi v^t)}}{4\psi v^t}\right\}$11b${\lambda }_t=\frac{2{\tau }_t\psi }{1+2{\tau }_t\psi v^t}$

Note that ${\tau }_t=0$ if and only if $({\mathit{\mu }}_t,{\mathbf{\Sigma }}_t)$ satisfies the constraint of Equation (8). Even though the real situation is more complicated, to have a better understanding of this update rule, we assume that ${\mathbf{\Sigma }}_t$ is diagonal at this round. Equation (10a) suggests that for the weight with less confidence, a more aggressive update of its mean value is required, and Equation (10b) implies that for the weight with more confidence, the update of its variance is less aggressive. In addition, both prediction and learning parts of the LCW algorithm require to extract the feature vectors of instances, ${\mathit{\varphi }}_t$'s, the feature space has to be restricted to a finite-dimensional space.

Kernelization of LCW

The kernel trick is to replace an inner product on a feature space with the kernel function k which implicitly realizes the inner product:12$k(x,x^{\prime })=\mathit{\varphi }{\left(x\right)}^{\top }\mathit{\varphi }\left(x^{\prime }\right)$

By the kernel trick, we can kernelize the LCW algorithm to employ a kernel-based hypothesis and thus provide another way to make predictions. To see this, we first give the following lemma that provides new expressions for the mean vector and covariance matrix.

Lemma 1. Let the LCW algorithm initialize with ${\mathit{\mu }}_1=\mathbf{0}$ and ${\mathbf{\Sigma }}_1=\mathbf{I}$. The mean vector ${\mathit{\mu }}_t$ computed by the LCW algorithm can be expressed as a linear combination of feature vectors of instances, and the corresponding covariance matrix ${\mathbf{\Sigma }}_t$ can be expressed as a linear combination of outer products of feature vectors of instances,13$\begin{array}{l}{\mathit{\mu }}_t=\sum _{i\in {\mathcal{I}}_t}{u}_i^{\left(t\right)}{\mathit{\varphi }}_i\\ {\mathbf{\Sigma }}_t=\mathbf{I}+\sum _{i\in {\mathcal{I}}_t}\sum _{j\in {\mathcal{I}}_t}{\omega }_{ij}^{\left(t\right)}{\mathit{\varphi }}_i{\mathit{\varphi }}_j^{\top }\end{array}$where ${\mathcal{I}}_t=\{i\in \mathbb{N}|i<t\wedge {\tau }_i\ne 0\}$. In addition, the coefficients, $u_i^{(t)}$'s and $w_{ij}^{(t)}$'s, depend only on inner products of feature vectors of instances.

The lemma can be proved by induction similar to the proof of Theorem 2 from ref. [22]. Let $m_t\left(x\right)=\mathit{\varphi }{\left(x\right)}^{\top }{\mathit{\mu }}_t$ and $c_t(x,x^{\prime })=\mathit{\varphi }{\left(x\right)}^{\top }{\mathbf{\Sigma }}_t\mathit{\varphi }\left(x^{\prime }\right)$ be the mean and covariance functions on round t, respectively. Lemma 1 suggests that we can reexpress the linear hypothesis on round t as a kernel-based hypothesis characterized by14a$m_t(x)=\sum _{i\in {\mathcal{I}}_t}{u}_i^{(t)}k(x,x_i)$14b$c_t(x,x^{\prime })=k(x,x^{\prime })+\sum _{i\in {\mathcal{I}}_t}\sum _{j\in {\mathcal{I}}_t}{\omega }_{ij}^{(t)}k(x,x_i)k(x_j,x^{\prime })$where $x_i,i\in {\mathcal{I}}_t$, is the support element (SE) and ${\mathcal{I}}_t$ is the index set of corresponding SEs. $u_i^{(t)}$ is the combination coefficient associated with the SE $x_i$ for constructing the mean function $m_t(x)$, and ${\omega }_{ij}^{(t)}$ is the combination coefficient associated with the SE pair $(x_i,x_j)$ for constructing the covariance function $c_t(x,x^{\prime })$. In this article, instead of a support vector, an instance $x_i\in \mathcal{X}$ that is used to form a hypothesis for prediction is called an SE because we assume that the instance space X may contain any unstructured elements, including nonvector elements. Together Lemma 1 and Equation (10a,b) give the update formulas of the kernel-based hypothesis as follows15a$m_{t+1}(x)=m_t(x)+\sum _{i\in {\mathcal{I}}_{t+1}}\Delta u_i^{(t)}k(x,x_i)$15b$c_{t+1}(x,x^{\prime })=c_t(x,x^{\prime })+\sum _{i\in {\mathcal{I}}_{t+1}}\sum _{j\in {\mathcal{I}}_{t+1}}\Delta {\omega }_{ij}^{(t)}k(x,x_i)k(x_j,x^{\prime })$with16$\begin{array}{r}{\mathcal{I}}_{t+1}=\{\begin{array}{cc}{\mathcal{I}}_t& \text{if }{\tau }_t=0\\ {\mathcal{I}}_t\cup \left\{t\right\}& \text{if }{\tau }_t\ne 0\end{array}\\ \Delta u_i^{\left(t\right)}=\{\begin{array}{cc}{\tau }_t{y}_t\sum _{p\in {\mathcal{I}}_t}{\omega }_{ip}^{\left(t\right)}k(x_p,x_t)& \text{if }i<t\\ {\tau }_t{y}_t& \text{if }i=t\end{array}\\ \Delta {\omega }_{ij}^{\left(t\right)}=\{\begin{array}{ll}-{\lambda }_t\left(\sum _{p\in {\mathcal{I}}_t}{\omega }_{ip}^{\left(t\right)}k(x_p,x_t)\right)& \\ \times \left(\sum _{q\in {\mathcal{I}}_t}{\omega }_{qj}^{\left(t\right)}k(x_q,x_t)\right)& \text{if }i,j<t\\ -{\lambda }_t\sum _{p\in {\mathcal{I}}_t}{\omega }_{ip}^{\left(t\right)}k(x_p,x_t)& \text{if }j=t\text{ \& }i<t\\ -{\lambda }_t\sum _{q\in {\mathcal{I}}_t}{\omega }_{qj}^{\left(t\right)}k(x_q,x_t)& \text{if }i=t\text{ \& }j<t\\ -{\lambda }_t& \text{if }i=j=t\end{array}\end{array}$where ${\tau }_t$ and ${\lambda }_t$ are computed by Equation (11a,b) with $m^t=y_t{m}_t(x_t)$ and $v^t=c_t(x_t,x_t)$. Note that ${\tau }_t=0$ if and only if $m_t\ge \psi v_t$. We summarize the kernel-based LCW algorithm in Algorithm 1.

Algorithm 1 Kernel-Based LCW Algorithm.

1: Input: kernel k, confidence parameter $\eta \in (\mathrm{0.5,1}]$

2: Initialize: ${\mathcal{I}}_1=\varnothing$, $m_1(x)=0$, $c_1(x,x^{\prime })=k(x,x^{\prime })$, $\psi ={\Psi }^{-1}(\eta )$

3: for $t=\mathrm{1,2,}\dots$do

4:  Receive an instance $x_t\in \mathcal{X}$

5:  Predict the class label ${\widehat{y}}_t=\text{sign}(m_t(x_t))$

6:  Receive the correct class label $y_t\in \{+\mathrm{1,}-1\}$

7:  if $y_t{m}_t(x_t)\ge \psi c_t(x_t,x_t)$ then

8:   ${\mathcal{I}}_{t+1}={\mathcal{I}}_t$

9:   $m_{t+1}(x)=m_t(x)$

10:   $c_{t+1}(x,x^{\prime })=c_t(x,x^{\prime })$

11:  else

12:   ${\mathcal{I}}_{t+1}={\mathcal{I}}_t\cup \{t\}$

13:   Update $m_{t+1}(x)$ and $c_{t+1}(x,x^{\prime })$ by Equation (15a,b)

14:  end if

15: end for

Kernel-Based LCW on a Budget

Since the kernel-based LCW algorithm employs a kernel-based hypothesis for prediction, all SEs and combination coefficients are required to be stored for constructing the mean and covariance functions. On round t, the runtime and memory consumption depend on the size of the support index set ${\mathcal{I}}_t$. Whenever the hypothesis fails to satisfy the optimization constraint (cf. line 7 in Algorithm 1), the size of the support index set increases. Hence, the computational burden may grow unlimitedly eventually. It is known as the curse of kernelization^[45] which asks for a resource-efficient approach to make the kernel-based LCW algorithm realizable in practice, especially in a resource-scarce environment. To break the curse, we present a budgeted algorithm, which puts a limit on the maximum number of SEs for constructing the kernel-based hypothesis. The concept of the budgeted algorithm follows the spirit of the LCW algorithm, and thus we call it the budgeted LCW (BLCW) algorithm. Figure 2 demonstrates the concept of the proposed BLCW algorithm. In the rest of this section, we first introduce the resource perspective on the kernel-based LCW algorithm. Based on this perspective, we propose the BLCW algorithm and then study four SE removal strategies for maintaining the budget.

[IMAGE OMITTED. SEE PDF]

Resource Perspective

Let us first delve into the hypothesis used by the kernel-based LCW algorithm. The kernelization of LCW as in Section 2.3 implies that Equation (14a,b) is the mean and covariance functions of $f_t\left(x\right)=\mathit{\varphi }{\left(x\right)}^{\top }{\mathbf{w}}_t$ with ${\mathbf{w}}_t\sim \mathcal{N}({\mathit{\mu }}_t,{\mathbf{\Sigma }}_t)$ because of17$\begin{array}{l}{m}_t(x)=\mathbb{E}[f_t(x)]\hfill \\ c_t(x,x^{\prime })=\mathbb{E}[(f_t(x)-m_t(x))(f_t(x^{\prime })-m_t(x^{\prime }))]\hfill \end{array}$where $\mathbb{E}[\cdot ]$ computes the expectation. In addition, $f_t(x)$ can be shown to be a Gaussian process.^[46] Thus, the hypothesis used by the kernel-based LCW algorithm on round t is actually a Gaussian process characterized by the kernel-based mean and covariance functions, Equation (14a,b),18a$f_t\left(x\right)=\mathit{\varphi }{\left(x\right)}^{\top }{\mathbf{w}}_t\sim \mathcal{G}\mathcal{P}\left(m_t\right(x),c_t(x,x^{\prime }\left)\right)$18b$m_t\left(x\right)=\mathit{\varphi }{\left(x\right)}^{\top }{\mathit{\mu }}_t=\left(14\mathrm{a}\right)$18c$c_t(x,x^{\prime })=\mathit{\varphi }{\left(x\right)}^{\top }{\mathbf{\Sigma }}_t\mathit{\varphi }\left(x^{\prime }\right)=\left(14\mathrm{b}\right)$

Similarly, the updated hypothesis is also a Gaussian process characterized by another kernel-based mean and covariance functions, Equation (15a,b),19$\begin{array}{l}{f}_{t+1}\left(x\right)=\mathit{\varphi }{\left(x\right)}^{\top }{\mathbf{w}}_{t+1}\sim \mathcal{G}\mathcal{P}\left(m_{t+1}\right(x),c_{t+1}(x,x^{\prime }\left)\right)\\ m_{t+1}\left(x\right)=\mathit{\varphi }{\left(x\right)}^{\top }{\mathit{\mu }}_{t+1}=\left(15\mathrm{a}\right)\\ c_{t+1}(x,x^{\prime })=\mathit{\varphi }{\left(x\right)}^{\top }{\mathbf{\Sigma }}_{t+1}\mathit{\varphi }\left(x^{\prime }\right)=\left(15\mathrm{b}\right)\end{array}$

As a consequence of the constrained optimization problem (Equation (8)), the update adjusts the combination coefficients associated with SEs and SE pairs. This motivates us to investigate whether somehow we can directly control the combination coefficients of available SEs and SE pairs and obtain a new update rule for the kernel-based LCW algorithm.

Wu et al.^[47] introduced the resource perspective which gives us a clue about how to control the combination coefficients directly. With the resource perspective, we treat each instance $x_t$ as a possible resource that can be used as an SE for constructing a kernel-based hypothesis. On round t, we consider SEs as available resources which are utilized to construct the hypothesis for prediction; we consider the combination coefficients associated with SEs and SE pairs as utilization degrees of the SEs and SE pairs. When it comes to the update part, we first have to decide which instances are the available resources that are responsible for prediction for the next round and determine the corresponding utilization degrees. Instances which are not considered available resources for the updated hypothesis are discarded from the storage and cannot be used in future rounds anymore. It leaves us with the question of how to obtain a new update rule by applying the resource perspective while keeping the spirit of the LCW algorithm, which seeks minimum change in successive distributions while ensuring a sufficiently large margin.

Bearing the resource perspective in mind, we start from the kernel-based hypothesis. Assume the hypothesis on round t is a Gaussian process ${\tilde{f}}_t(x)$ characterized by some kernel-based mean function ${\tilde{m}}_t(x)$ and some kernel-based covariance function ${\tilde{c}}_t(x,x^{\prime })$20a${\tilde{f}}_t(x)\sim \mathcal{G}\mathcal{P}({\tilde{m}}_t(x),{\tilde{c}}_t(x,x^{\prime }))$20b${\tilde{m}}_t(x)=\sum _{i\in {\tilde{\mathcal{I}}}_t}{\tilde{u}}_i^{(t)}k(x,x_i)$20c${\tilde{c}}_t(x,x^{\prime })=k(x,x^{\prime })+\sum _{i\in {\tilde{\mathcal{I}}}_t}\sum _{j\in {\tilde{\mathcal{I}}}_t}{\tilde{\omega }}_{ij}^{(t)}k(x,x_i)k(x_j,x^{\prime })$where ${\tilde{m}}_t(x)$ is some linear combination of kernels centered on a set of some SEs, and ${\tilde{c}}_t(x,x^{\prime })$ is some linear combination of outer products of kernels centered on the same set of SEs. ${\tilde{\mathcal{I}}}_t$ is the index set of corresponding SEs. We further assume that ${\tilde{\omega }}_{ij}^{(t)}={\tilde{\omega }}_{ji}^{(t)}$ for any $i,j\in {\tilde{\mathcal{I}}}_t$. Note that the $\sim$ symbol is used to emphasize that Equation (20a–c) and (18a–c) may be different in SEs and the combination coefficients, even with the same sequence of rounds.

After receiving the instance $x_t$, we predict the class label by using the mean function ${\tilde{m}}_t(x)$,21${\widehat{y}}_t=\text{sign}({\tilde{m}}_t(x_t))$

Once the correct class label $y_t$ is received, we update the Gaussian process for the next round based on the current example $(x_t,y_t)$. The spirit of the LCW algorithm suggests to check whether the current Gaussian process ${\tilde{f}}_t(x)$ has a sufficiently large margin for the current example $(x_t,y_t)$ or satisfies the following inequality22$y_t{\tilde{m}}_t(x_t)\ge \psi {\tilde{c}}_t(x_t,x_t)$

If Equation (22) is satisfied, we keep the same Gaussian process for the next round,23a${\tilde{f}}_{t+1}(x)\sim \mathcal{G}\mathcal{P}({\tilde{m}}_{t+1}(x),{\tilde{c}}_{t+1}(x,x^{\prime }))$23b${\tilde{m}}_{t+1}(x)={\tilde{m}}_t(x)$23c${\tilde{c}}_{t+1}(x,x^{\prime })={\tilde{c}}_t(x,x^{\prime })$

Otherwise, without putting any constraint on the number of resources, the resource perspective suggests selecting all available instances including the current instance $x_t$ as available resources for constructing the new Gaussian process. We seek a new Gaussian process $\tilde{f}(x)$ characterized by some kernel-based mean function $\tilde{m}(x)$ and some kernel-based covariance function $\tilde{c}(x,x^{\prime })$,24a$\tilde{f}(x)\sim \mathcal{G}\mathcal{P}(\tilde{m}(x),\tilde{c}(x,x^{\prime }))$24b$\tilde{m}(x)=\sum _{i\in {\tilde{\mathcal{I}}}_{t+1}}{\tilde{a}}_{i}k(x,x_i)$24c$\tilde{c}(x,x^{\prime })=k(x,x^{\prime })+\sum _{i\in {\tilde{\mathcal{I}}}_{t+1}}\sum _{j\in {\tilde{\mathcal{I}}}_{t+1}}{\tilde{b}}_{ij}k(x,x_i)k(x_j,x^{\prime })$where $\tilde{m}(x)$ is some linear combination of kernels centered on the new set of SEs, and $\tilde{c}(x,x^{\prime })$ is some linear combination of outer products of kernels centered on the same new set of SEs. ${\tilde{\mathcal{I}}}_{t+1}={\tilde{\mathcal{I}}}_t\cup \{t\}$ corresponds to the new index set. We further assume that ${\tilde{b}}_{ij}={\tilde{b}}_{ji}$ for any $i,j\in {\tilde{\mathcal{I}}}_{t+1}$. That leaves us to do is the determination of the utilization degrees, ${\tilde{a}}_i$'s and ${\tilde{b}}_{ij}$'s.

Note that the assumption of Equation (20b,c) allows us to have the following decomposition for them,25a${\tilde{m}}_t\left(x\right)=\mathit{\varphi }{\left(x\right)}^{\top }{\tilde{\mathit{\mu }}}_t,{\tilde{\mathit{\mu }}}_t=\sum _{i\in {\tilde{\mathcal{I}}}_t}{\tilde{u}}_i^{\left(t\right)}{\mathit{\varphi }}_i$25b${\tilde{c}}_t(x,x^{\prime })=\mathit{\varphi }{\left(x\right)}^{\top }{\tilde{\mathbf{\Sigma }}}_t\mathit{\varphi }\left(x^{\prime }\right),{\tilde{\mathbf{\Sigma }}}_t=\mathbf{I}+\sum _{i\in {\tilde{\mathcal{I}}}_t}\sum _{j\in {\tilde{\mathcal{I}}}_t}{\tilde{\omega }}_{ij}^{\left(t\right)}{\mathit{\varphi }}_i{\mathit{\varphi }}_j^{\top }$which imply Equation (20a) can be treated as a linear hypothesis ${\tilde{f}}_t\left(x\right)=\mathit{\varphi }{\left(x\right)}^{\top }{\tilde{\mathbf{w}}}_t$ with ${\tilde{\mathbf{w}}}_t\sim \mathcal{N}({\tilde{\mathit{\mu }}}_t,{\tilde{\mathbf{\Sigma }}}_t)$. It is equivalent to that ${\tilde{f}}_t(x)$ is determined by $\mathcal{N}({\tilde{\mathit{\mu }}}_t,{\tilde{\mathbf{\Sigma }}}_t)$. Similarly, Equation (24b,c) can be decomposed as26a$\tilde{m}\left(x\right)=\mathit{\varphi }{\left(x\right)}^{\top }\tilde{\mathit{\mu }},\tilde{\mathit{\mu }}=\sum _{i\in {\tilde{\mathcal{I}}}_{t+1}}{\tilde{a}}_i{\mathit{\varphi }}_i$26b$\tilde{c}(x,x^{\prime })=\mathit{\varphi }{\left(x\right)}^{\top }\tilde{\mathbf{\Sigma }}\mathit{\varphi }\left(x^{\prime }\right),\tilde{\mathbf{\Sigma }}=\mathbf{I}+\sum _{i\in {\tilde{\mathcal{I}}}_{t+1}}\sum _{j\in {\tilde{\mathcal{I}}}_{t+1}}{\tilde{b}}_{ij}{\mathit{\varphi }}_i{\mathit{\varphi }}_j^{\top }$which imply that Equation (24a) is a linear hypothesis $\tilde{f}\left(x\right)=\mathit{\varphi }{\left(x\right)}^{\top }\tilde{\mathbf{w}}$ with $\tilde{\mathbf{w}}\sim \mathcal{N}(\tilde{\mathit{\mu }},\tilde{\mathbf{\Sigma }})$. It is equivalent to that $\tilde{f}(x)$ is determined by $\mathcal{N}(\tilde{\mathit{\mu }},\tilde{\mathbf{\Sigma }})$. Following the spirit of the LCW algorithm, we seek the utilization degrees for the next round that solve the following constrained optimization problem27$\begin{array}{ll}\underset{{\tilde{a}}_i,{\tilde{b}}_{ij},\forall i,j}{\text{minimize}}& D_{\text{KL}}\left(\mathcal{N}\right(\tilde{\mathit{\mu }},\tilde{\mathbf{\Sigma }})\parallel \mathcal{N}({\tilde{\mathit{\mu }}}_t,{\tilde{\Sigma }}_t\left)\right)\\ \text{subject to}& y_t\tilde{m}\left(x_t\right)\ge \psi \tilde{c}(x_t,x_t)\end{array}$where the objective function measures the difference between two Gaussian processes, $\tilde{f}(x)$ and ${\tilde{f}}_t(x)$, and the constraint ensures that the updated Gaussian process has a sufficiently large margin on the current example $(x_t,y_t)$. Note that $\psi ={\Psi }^{-1}(\eta )$ with the confidence parameter $\eta \in (\mathrm{0.5,1}])$. It is worth to emphasize that Equation (27) shares the same spirit with Equation (8), but they are different optimization problems since we seek the utilization degrees of available resources in Equation (27), not the mean vector and covariance matrix in Equation (8). Finally, substituting the solution of Equation (27) back into Equation (24a–c) leads to the new Gaussian process ${\tilde{f}}_{t+1}(x)\sim GP({\tilde{m}}_{t+1}(x),{\tilde{c}}_{t+1}(x,x^{\prime }))$ for the next round.

It turns out that combining the resource perspective and the spirit of the LCW algorithm gives an update rule the same as that of the kernel-based LCW algorithm. Moreover, the prediction results will be the same for the entire sequence of rounds with a proper initialization for the approach from the resource perspective. A formal statement of the results is given in the following proposition.

Proposition 2. Suppose all kernel matrices of encountered instances are strictly positive definite. Let the resource perspective combining the spirit of the LCW algorithm use the following setting.

1. Initialize the Gaussian process as follows28$\begin{array}{l}{\tilde{f}}_1(x)\sim \mathcal{G}\mathcal{P}({\tilde{m}}_1(x),{\tilde{c}}_1(x,x^{\prime }))\hfill \\ {\tilde{m}}_1(x)=0\hfill \\ {\tilde{c}}_1(x,x^{\prime })=k(x,x^{\prime })\hfill \end{array}$

2. Predict the class using the mean function on round t,29${\widehat{y}}_t=\text{sign}({\tilde{m}}_t(x_t))$

3. Update the Gaussian process for round $t+1$ by solving Equation (27) when the margin inequality (Equation (22)) is violated, otherwise keep the same by Equation (23a–c).

This setting follows the same prediction path made by the kernel-based LCW algorithm, that is, for $t=\mathrm{1,2,}\dots$:30a${\tilde{f}}_t(x)\sim \mathcal{G}\mathcal{P}({\tilde{m}}_t(x),{\tilde{c}}_t(x,x^{\prime }))$30b${\tilde{m}}_t(x)=m_t(x)$30c${\tilde{c}}_t(x,x^{\prime })=c_t(x,x^{\prime })$where $f_t(x)\sim \mathcal{G}\mathcal{P}(m_t(x),c_t(x,x^{\prime }))$ is the Gaussian process employed by the kernel-based LCW algorithm on round t. By the equality signs of Equation (30b,c), we mean ${\tilde{\mathcal{I}}}_t={\mathcal{I}}_t$, ${\tilde{u}}_i^{(t)}=u_i^{(t)},\forall i\in {\tilde{\mathcal{I}}}_t$, and ${\tilde{\omega }}_{ij}^{(t)}={\omega }_{ij}^{(t)},\forall i,j\in {\tilde{\mathcal{I}}}_t$.

The proof is given in Appendix. Instead of mean vectors and covariance matrices of Gaussian distributions, the resource perspective considers the viewpoint of the utilization degrees of available resources for Gaussian Processes. Proposition 2 assures that the resource perspective and the kernel-based LCW algorithm use the same sequence of Gaussian processes for prediction. Hence, an alternative and equivalent interpretation for the kernel-based LCW algorithm is given by the resource perspective. It allows us to propose an approximate algorithm for the kernel-based LCW algorithm under the constraint of a limited number of available resources.

BLCW Algorithm

The kernel-based LCW algorithm is subject to the curse of kernelization, because the size of the Gaussian process for prediction, in terms of the size of the support index set, increases whenever the margin inequality (cf. line 7 in Algorithm 1) is violated. The violations are even more frequent in the presence of noise. It may cause unbounded growth of the Gaussian process in runtime and memory consumption and thus make the kernel-based LCW algorithm broken in practical applications where only finite computational resources are affordable. If we can control the size of the Gaussian process, we will be able to break the curse. Hence, we propose the BLCW algorithm that puts a limit on the maximum number of SEs by a predefined budget B. In a practical application, we can set the budget B by considering the available computational power. We can envision that we have to make some sacrifices in the proposed BLCW algorithm. Fortunately, Proposition 2 suggests that the proposed BLCW algorithm can be an approximate algorithm of the kernel-based LCW algorithm according to the reinterpretation from the resource perspective.

To be more clear about how the proposed BLCW algorithm can approximate the kernel-based LCW algorithm, we first assume the hypothesis on round t is a Gaussian process $f_t(x)$ characterized by some kernel-based mean function $m_t(x)$ and some kernel-based covariance function $c_t(x,x^{\prime })$,31a$f_t(x)\sim \mathcal{G}\mathcal{P}(m_t(x),c_t(x,x^{\prime }))$31b$m_t(x)=\sum _{i\in {\mathcal{I}}_t}{u}_i^{(t)}k(x,x_i)$31c$c_t(x,x^{\prime })=k(x,x^{\prime })+\sum _{i\in {\mathcal{I}}_t}\sum _{j\in {\mathcal{I}}_t}{\omega }_{ij}^{(t)}k(x,x_i)k(x_j,x^{\prime })$where $m_t(x)$ is some linear combination of kernels centered on a set of some SEs, and $c_t(x,x^{\prime })$ is some linear combination of outer products of kernels centered on the same set of SEs. ${\mathcal{I}}_t$ is the corresponding index set. Note that ${\omega }_{ij}^{(t)}={\omega }_{ji}^{(t)}$ for any $i,j\in {\mathcal{I}}_t$. If $f_t(x)$ satisfies the margin constraint enforced by the kernel-based LCW algorithm, i.e., $y_t{m}_t(x_t)\ge \psi c_t(x_t,x_t)$, or the number of current SEs is smaller than the budget B, i.e., $|{\mathcal{I}}_t|<B$, the proposed BLCW algorithm updates the hypothesis the same as the kernel-based LCW algorithm,32a$f_{t+1}(x)\sim \mathcal{G}\mathcal{P}(m_{t+1}(x),c_{t+1}(x,x^{\prime }))$32b$m_{t+1}(x)=(15\mathrm{a})$32c$c_{t+1}(x)=(15\mathrm{b})$

We call this kind of update the LCW update. Otherwise, we need to handle the situation where $f_t(x)$ violates the margin constraint, i.e., $y_t{m}_t(x_t)<\psi c_t(x_t,x_t)$, and in the meantime the number of current SEs reaches the budget, i.e., $|{\mathcal{I}}_t|=B$. The resource perspective suggests the BLCW algorithm removing one of the current SEs and setting the current instance $x_t$ and the remaining SEs as available resources for constructing the new Gaussian process for prediction on the next round. Let $x_r$ be the removed SE and $r\in {\mathcal{I}}_t$ be the corresponding index. Therefore, the BLCW algorithm seeks a new Gaussian process $f(x)$ characterized by some kernel-based mean function $m(x)$ and some kernel-based covariance function $c(x,x^{\prime })$,33a$f(x)\sim \mathcal{\text{GP}}(m(x),c(x,x^{\prime }))$33b$m(x)=\sum _{i\in {\mathcal{I}}_{t+1}}{a}_{i}k(x,x_i)$33c$c(x,x^{\prime })=k(x,x^{\prime })+\sum _{i\in {\mathcal{I}}_{t+1}}\sum _{j\in {\mathcal{I}}_{t+1}}{b}_{ij}k(x,x_i)k(x_j,x^{\prime })$where $m(x)$ is some linear combination of kernels centered on the new set of SEs, and $c(x,x^{\prime })$ is some linear combination of outer products of kernels centered on the same new set of SEs. ${\mathcal{I}}_{t+1}=({\mathcal{I}}_t\backslash \{r\})\cup \{t\}$ corresponds to the new index set of the B available resources. Again, we assume that $b_{ij}=b_{ji}$ for any $i,j\in {\mathcal{I}}_{t+1}$.

Note that the assumptions of Equation (31b,c) and (33b,c) allow us to have the following decomposition34a$m_t\left(x\right)=\mathit{\varphi }{\left(x\right)}^{\top }{\mathit{\mu }}_t$34b$c_t(x,x^{\prime })=\mathit{\varphi }{\left(x\right)}^{\top }{\mathbf{\Sigma }}_t\mathit{\varphi }\left(x^{\prime }\right)$34c$m\left(x\right)=\mathit{\varphi }{\left(x\right)}^{\top }\mathit{\mu }$34d$c(x,x^{\prime })=\mathit{\varphi }{\left(x\right)}^{\top }\mathbf{\Sigma }\mathit{\varphi }\left(x^{\prime }\right)$where ${\mathit{\mu }}_t$, ${\mathbf{\Sigma }}_t$, $\mathit{\mu }$, and $\mathbf{\Sigma }$ can be derived accordingly, but we omit their detailed expressions for simplicity. Equation (34a–d) implies that Equation (31a) and (33a) can be treated as linear hypotheses with Gaussian distributions as follows35$\begin{array}{l}{f}_t(x)=\mathit{\varphi }{(x)}^{\mathrm{T}}{\mathbf{w}}_t,{\mathbf{w}}_t\sim \mathcal{N}({\mathit{\mu }}_t,{\mathbf{\Sigma }}_t)\hfill \\ f(x)=\mathit{\varphi }{(x)}^{\mathrm{T}}\mathbf{w},\mathbf{w}\sim \mathcal{N}(\mathit{\mu },\mathbf{\Sigma })\hfill \end{array}$

Motivated by the resource perspective, we propose that the BLCW algorithm determines the utilization degrees of the B available resources, $a_i$'s and $b_{ij}$'s, by solving the following constrained optimization problem36$\begin{array}{ll}\underset{a_i,b_{ij},\forall i,j}{\text{minimize}}& D_{\text{KL}}\left(\mathcal{N}\right(\mathit{\mu },\mathbf{\Sigma })\parallel \mathcal{N}({\mathit{\mu }}_t,{\mathbf{\Sigma }}_t\left)\right)\\ \text{subject to}& y_{t}m\left(x_t\right)\ge \psi c(x_t,x_t)\end{array}$where the objective function measures the difference between two Gaussian processes, $f(x)$ and $f_t(x)$, and the constraint ensures that the updated Gaussian process has a sufficiently large margin for the current example $(x_t,y_t)$. We call this type of update the BLCW update. The BLCW update is stated formally by the following proposition.

Proposition 3. Suppose the kernel matrix of the B new SEs is strictly positive definite and the feature vector of the removed SE can be spanned by those of the B new SEs. If on round t the Gaussian process $f_t(x)$ violates the margin constraint, i.e., $y_t{m}_t(x_t)<\psi c_t(x_t,x_t)$ and the budget is reached, i.e., $|I_t|=B$, the BLCW algorithm updates as follows37a$f_{t+1}(x)\sim \mathcal{\text{GP}}(m_{t+1}(x),c_{t+1}(x,x^{\prime }))$37b$m_{t+1}(x)=m_t(x)-u_r^{(t)}k(x,x_r)+\sum _{i\in {\mathcal{I}}_{t+1}}{\alpha }_{i}k(x,x_i)$37c$\begin{array}{c}{c}_{t+1}(x,x^{\prime })\\ =\left\{\begin{array}{l}{c}_t(x,x^{\prime })-w_{rr}^{\left(t\right)}k(x,x_r)k(x_r,x^{\prime })-\sum _{i\in {\mathcal{I}}_t\backslash \left\{r\right\}}{w}_{ir}^{\left(t\right)}k(x,x_i)k(x_r,x^{\prime })\\ -\sum _{j\in {\mathcal{I}}_t\backslash \left\{r\right\}}{w}_{rj}^{\left(t\right)}k(x,x_r)k(x_j,x^{\prime })+\sum _{i\in {\mathcal{I}}_{t+1}}\sum _{j\in {\mathcal{I}}_{t+1}}{\beta }_{ij}k(x,x_i)k(x_j,x^{\prime })\end{array}\right\},\end{array}$37d$\mathit{\alpha }={\tau }_t{y}_t({\mathbf{e}}_B+\mathbf{h})+{\mathbf{K}}_r^{-1}{\mathbf{k}}_r(u_r^{(t)}+{\tau }_t{y}_t\rho )$37e$\begin{array}{c}\mathit{\beta }=-{\lambda }_t({\mathbf{e}}_B+\mathbf{h}){({\mathbf{e}}_B+\mathbf{h})}^{\top }+{\mathbf{K}}_r^{-1}{\mathbf{k}}_r[{\mathit{\omega }}_r^{\top }-{\lambda }_t\rho {({\mathbf{e}}_B+\mathbf{h})}^{\top }]\\ +[{\mathit{\omega }}_r-{\lambda }_t\rho ({\mathbf{e}}_B+\mathbf{h}\left)\right]{\mathbf{k}}_r^{\top }{\mathbf{K}}_r^{-1}+{\mathbf{K}}_r^{-1}{\mathbf{k}}_r({\omega }_{rr}^{\left(t\right)}-{\lambda }_t{\rho }^2){\mathbf{k}}_r^{\top }{\mathbf{K}}_r^{-1}\end{array}$37f$\mathbf{h}={\mathbf{\Omega }}_r{\mathbf{k}}_t+{\mathit{\omega }}_r{k}_{rt}$37g$\rho =w_{rr}^{\left(t\right)}{k}_{rt}+{\mathit{\omega }}_r^{\top }{\mathbf{k}}_t$37h${\lambda }_t=\frac{2{\tau }_t\psi }{1+2{\tau }_t\psi v}$37i${\tau }_t=\frac{-(1+2\psi m)+\sqrt{{(1+2\psi m)}^2-8\psi (m-\psi v)}}{4\psi v}$where $r\in {\mathcal{I}}_t$, ${\mathcal{I}}_{t+1}=({\mathcal{I}}_t\backslash \{r\})\cup \{t\}$, $\mathit{\alpha }=[{\alpha }_i],i\in {\mathcal{I}}_{t+1}$, $\mathit{\beta }=[{\beta }_{ij}],i,j\in {\mathcal{I}}_{t+1}$, $k_{ab}=k(x_a,x_b),a,b\in \mathbb{N}$, ${\mathbf{K}}_r=[k_{ij}],i,j\in {\mathcal{I}}_{t+1}$, ${\mathbf{k}}_a=[k_{ia}],i\in {\mathcal{I}}_{t+1}$ for $a=r\text{ or }t$, $m=y_t{m}_t(x_t)$, $v=c_t(x_t,x_t)$, ${\mathbf{e}}_B={[0,...,0,1]}^{\top }\in {ℝ}^B$,38$\begin{array}{r}{\mathit{\omega }}_r={[{\omega }_{i_1,r}^{\left(t\right)},\dots ,{\omega }_{i_{B-1},r}^{\left(t\right)},0]}^{\top }\in {\mathbb{R}}^B\\ {\mathbf{\Omega }}_r=\left[\begin{array}{cccc}{\omega }_{i_1,i_1}^{\left(t\right)}& \dots & {\omega }_{i_1,i_{B-1}}^{\left(t\right)}& 0\\ ⋮& \ddots & ⋮& ⋮\\ {\omega }_{i_{B-1},i_1}^{\left(t\right)}& \dots & {\omega }_{i_{B-1},i_{B-1}}^{\left(t\right)}& 0\\ 0& \dots & 0& 0\end{array}\right]\in {\mathbf{S}}^B\end{array}$and ${\mathcal{I}}_t\backslash \{r\}=\{i_1,\dots ,i_{B-1}\}$ with $i_1<\dots <i_{B-1}$.

We give the proof in Appendix. At first glance, the BLCW update seems rather complicated. However, it turns out to have a simple interpretation. For ease of understanding, we explain the update by using the equivalent linear hypothesis of Equation (37a–c) with the highly organized form as follows,39a$f_{t+1}\left(x\right)=\mathit{\varphi }{\left(x\right)}^{\top }{\mathbf{w}}_{t+1},{\mathbf{w}}_{t+1}\sim \mathcal{N}({\mathit{\mu }}_{t+1},{\mathbf{\Sigma }}_{t+1})$39b$m_{t+1}\left(x\right)=\mathit{\varphi }{\left(x\right)}^{\top }{\mathit{\mu }}_{t+1}$39c$c_{t+1}(x,x^{\prime })=\mathit{\varphi }{\left(x\right)}^{\top }{\mathbf{\Sigma }}_{t+1}\mathit{\varphi }\left(x^{\prime }\right)$with40a${\mathit{\mu }}_{t+1}=\{{\mathit{\mu }}_t+{\mathbf{\Phi }}_r[{\tau }_t{y}_t({\mathbf{e}}_B+\mathbf{h})]+{\mathit{\varphi }}_r{\tau }_t{y}_t\rho \}$40b$+\{-{\mathit{\varphi }}_r(u_r^{(t)}+{\tau }_t{y}_t\rho )+{\mathcal{P}}_t[{\mathit{\varphi }}_r(u_r^{(t)}+{\tau }_t{y}_t\rho )\left]\right\}$40c${\mathbf{\Sigma }}_{t+1}=\left\{\begin{array}{l}{\mathbf{\Sigma }}_t+{\mathbf{\Phi }}_r[-{\lambda }_t({\mathbf{e}}_B+\mathbf{h}\left){({\mathbf{e}}_B+\mathbf{h})}^{\top }\right]{\mathbf{\Phi }}_r^{\top }\\ +{\mathit{\varphi }}_r(-{\lambda }_t{\rho }^2){\mathit{\varphi }}_r^{\top }+{\mathbf{\Phi }}_r[-{\lambda }_t\rho ({\mathbf{e}}_B+\mathbf{h}\left)\right]{\mathit{\varphi }}_r^{\top }\\ +{\mathit{\varphi }}_r[-{\lambda }_t\rho {({\mathbf{e}}_B+\mathbf{h})}^{\top }]{\mathbf{\Phi }}_r^{\top }\end{array}\right\}$40d$+\left\{{\mathcal{P}}_{t,\mathrm{F}}\right[{\mathit{\varphi }}_r({\omega }_{rr}^{\left(t\right)}-{\lambda }_t{\rho }^2){\mathit{\varphi }}_r^{\top }]-{\mathit{\varphi }}_r({\omega }_{rr}^{\left(t\right)}-{\lambda }_t{\rho }^2\left){\mathit{\varphi }}_r^{\top }\right\}$40e$+\left\{{\mathcal{P}}_{t,\mathrm{F}}\right[{\mathbf{\Phi }}_r({\mathit{\omega }}_r-{\lambda }_t\rho ({\mathbf{e}}_B+\mathbf{h}\left)\right){\mathit{\varphi }}_r^{\top }]-{\mathbf{\Phi }}_r[{\mathit{\omega }}_r-{\lambda }_t\rho ({\mathbf{e}}_B+\mathbf{h})\left]{\mathit{\varphi }}_r^{\top }\right\}$40f$+\left\{{\mathcal{P}}_{t,\mathrm{F}}\right[{\mathit{\varphi }}_r({\mathit{\omega }}_r^{\top }-{\lambda }_t\rho {({\mathbf{e}}_B+\mathbf{h})}^{\top }){\mathbf{\Phi }}_r^{\top }]-{\mathit{\varphi }}_r[{\mathit{\omega }}_r^{\top }-{\lambda }_t\rho {({\mathbf{e}}_B+\mathbf{h})}^{\top }\left]{\mathbf{\Phi }}_r^{\top }\right\}$where ${\mathbf{\Phi }}_r=[{\mathit{\varphi }}_{i_1},\dots ,{\mathit{\varphi }}_{i_{B-1}},{\mathit{\varphi }}_t]$, ${\mathcal{P}}_t[\cdot ]$ is the orthogonal projection in the Euclidean norm sense, and ${\mathcal{P}}_{t,\mathrm{F}}[\cdot ]$ is the orthogonal projection in the Frobenius norm sense. ${\mathcal{P}}_t\left[\mathit{\varphi }\right(x\left)\right]={\mathbf{\Phi }}_r{\mathbf{K}}_r^{-1}{\mathbf{\Phi }}_r^{\top }\mathit{\varphi }\left(x\right)$ projects the feature vector $\mathit{\varphi }(x)$ onto the subspace spanned by feature vectors of the B new SEs, $\text{span}(\{{\mathit{\varphi }}_i|i\in {\mathcal{I}}_{t+1}\})$; ${\mathcal{P}}_{t,\mathrm{F}}\left[{\mathit{\varphi }}_p{\mathit{\varphi }}_q^{\top }\right]$ projects the outer product ${\mathit{\varphi }}_p{\mathit{\varphi }}_q^{\top }$ onto the subspace spanned by outer products of feature vectors of the B new SEs, $\text{span}\left(\right\{{\mathit{\varphi }}_i{\mathit{\varphi }}_j^{\top }|i,j\in {\mathcal{I}}_{t+1}\})$, as follows41${\mathcal{P}}_{t,\mathrm{F}}\left[{\mathit{\varphi }}_p{\mathit{\varphi }}_q^{\top }\right]=\{\begin{array}{ll}{\mathbf{\Phi }}_r{\mathbf{K}}_r^{-1}{\mathbf{k}}_r{\mathbf{k}}_r^{\top }{\mathbf{K}}_r^{-1}{\mathbf{\Phi }}_r^{\top }& \text{if }p=q=r\\ {\mathit{\varphi }}_p{\mathbf{k}}_r^{\top }{\mathbf{K}}_r^{-1}{\mathbf{\Phi }}_r^{\top }& \text{if }p\in {\mathcal{I}}_{t+1},q=r\\ {\mathbf{\Phi }}_r{\mathbf{K}}_r^{-1}{\mathbf{k}}_r{\mathit{\varphi }}_q^{\top }& \text{if }p=r,q\in {\mathcal{I}}_{t+1}\\ {\mathit{\varphi }}_p{\mathit{\varphi }}_q^{\top }& \text{if }p,q\in {\mathcal{I}}_{t+1}\end{array}$where r is the index corresponding to the removed SE.

Note that we split ${\mathit{\mu }}_{t+1}$ and ${\mathbf{\Sigma }}_{t+1}$ of the BLCW update into two parts, Equation (40a,b), and four parts, Equation (40c–f), respectively; each part is enclosed by a pair of curly brackets. Comparing carefully Equation (40a–f) to the update of the kernel-based LCW algorithm, Equation (15a,b), we observe that together the first parts of ${\mathit{\mu }}_{t+1}$ and ${\mathbf{\Sigma }}_{t+1}$, i.e., Equation (40a,c), can be interpreted as an LCW update, and the remaining parts, Equation (40b) and (40d–f), correspond to projections related to the removed SE $x_r$. According to the derivation in this section, we first select the removed SE $x_r$ and then determine the utilization degrees of B available resources. However, the organized form (Equation (40a–f)) suggests that there is an alternative way for the interpretation of the BLCW update: it first updates the same as the LCW update and then performs the removal of the unaffordable resource $x_r$ by projections, which preserve the information of $x_r$.

In Proposition 3, we include an assumption for the removed SE $x_r$. The assumption allows ${\mathit{\varphi }}_r$ to be represented by the B new SEs. Thus, the projection parts, Equation (40b) and (40b–f), vanish if this assumption holds true, and then the BLCW update is equivalent to the LCW update. In practice, this assumption may not hold true and results in the sacrifice showing up as projection errors. Finally, Algorithm 2 summarizes the proposed BLCW algorithm.

Remark. Although we develop and explain the BLCW update by using a finite-dimensional feature space mapped by the feature extraction $\mathit{\varphi }:\mathcal{X}\to {ℝ}^d$, the proposed BLCW algorithm is presented in a pure kernel-based style. This means the proposed BLCW algorithm and the associated interpretations are applicable to any valid kernel function that realizes an inner product, for example, the Gaussian kernel. $k(\mathbf{x},{\mathbf{x}}^{\prime })=\exp (-\gamma \parallel \mathbf{x}-{\mathbf{x}}^{\prime }{\parallel }_2^2),\gamma >0$, which corresponds to an infinite-dimensional feature space.

Algorithm 2 BLCW Algorithm.

1: Input: budget B, kernel k, confidence parameter $\eta \in (\mathrm{0.5,1}]$

2: Initialize: ${\mathcal{I}}_1=\varnothing$, $m_1(x)=0$, $c_1(x,x^{\prime })=k(x,x^{\prime })$, $\psi ={\Psi }^{-1}(\eta )$

3: for $t=\mathrm{1,2,}\dots$ do

4:  Receive an instance $x_t\in \mathcal{X}$

5:  Predict the class label ${\widehat{y}}_t=\text{sign}(m_t(x_t))$

6:  Receive the correct class label $y_t\in \{+\mathrm{1,}-1\}$

7:  if $y_t{m}_t(x_t)\ge \psi c_t(x_t,x_t)$ then ▹ LCW update

8:   ${\mathcal{I}}_{t+1}={\mathcal{I}}_t$

9:   $m_{t+1}(x)=m_t(x)$

10:   $c_{t+1}(x,x^{\prime })=c_t(x,x^{\prime })$

11:  else if $|{\mathcal{I}}_t|<B$ then ▹ LCW update

12:   ${\mathcal{I}}_{t+1}={\mathcal{I}}_t\cup \{t\}$

13:   Update $m_{t+1}(x)$ and $c_{t+1}(x,x^{\prime })$ by Equation (15a,b)

14:  else ▹ BLCW update

15:   Determine the removal index $r=r_t\in {\mathcal{I}}_t$

16:   ${\mathcal{I}}_{t+1}=({\mathcal{I}}_t\backslash \{r\})\cup \{t\}$

17:  Update $m_{t+1}(x)$ and $c_{t+1}(x,x^{\prime })$ by Equation (37b,c)

18: end if

19: end for

Budget Maintenance

In Section 3.2, we propose the BLCW algorithm that is an approximate algorithm for the kernel-based LCW algorithm. The BLCW algorithm puts a limit on the maximum number of SEs by the budget B and performs the LCW update as long as the size of the Gaussian process for prediction is less than the budget, i.e., $|{\mathcal{I}}_t|<B$. Once the budget is reached, the BLCW algorithm performs the BLCW update whenever the Gaussian process has no sufficiently large margin in the current example. Let $r_t$ be the index corresponding to the removed SE on round t. The BLCW algorithm selects the removed SE from the set of current SEs, i.e., $r_t\in {\mathcal{I}}_t$, without any other specific removal strategy. Different removal strategies may lead to totally different prediction paths for the same sequence of prediction tasks. Thus, the determination of the removal index $r_t$ is important. In this section, we study four kinds of removal strategies for maintaining the budget.

To facilitate the study, we consider the situation where the BLCW algorithm needs to perform a BLCW update on round t. The interpretation of the BLCW update in Section 3.2 suggests that we can separate out an intermediate Gaussian process $f_t^{\prime }(x)$ that is obtained by performing the LCW update without the subsequent projections,42a$f_t^{\prime }(x)\sim \mathcal{\text{GP}}(m_t^{\prime }(x),c_t^{\prime }(x,x^{\prime }))$42b$m_t^{\prime }\left(x\right)=\sum _{i\in {\mathcal{I}}_t^{\prime }}{u}_i^{\prime }k(x,x_i)$42c$c_t^{\prime }(x,x^{\prime })=k(x,x^{\prime })+\sum _{i\in {\mathcal{I}}_t^{\prime }}\sum _{j\in {\mathcal{I}}_t^{\prime }}{\omega }_{ij}^{\prime }k(x,x_i)k(x_j,x^{\prime })$

BLCW with Oldest Removal (BLCW-O)^[48]

Because the BLCW algorithm deals with a sequence of consecutive rounds, adjacent examples may be more related than those far apart. This means that the SE with the smaller index may be less helpful in making predictions for future rounds. Thus, it suggests removing the oldest SE,43$r_t=\min {\mathcal{I}}_t$

We compute the computational burden of a BLCW update. The calculation of the matrix inverse ${\mathbf{K}}_{r_t}^{-1}$ dominates the time complexity of BLCW-O. It takes $\mathcal{O}(B^3)$ time by computing directly ${\mathbf{K}}_{r_t}^{-1}$ from ${\mathbf{K}}_{r_t}$. However, we can speed up the computation of the matrix inverse by using a recursive approach that exploits the incremental and decremental natures of the kernel matrix. It takes $\mathcal{O}(B^2)$ time to compute ${\mathbf{K}}_{r_t}^{-1}$ from the last matrix inverse ${\mathbf{K}}_{r_{t-1}}^{-1}$ by two recursive steps: the first one corresponds to shrink ${\mathbf{K}}_{r_{t-1}}^{-1}$ to a smaller matrix inverse of size $(B-1)\times (B-1)$, and the second one is to enlarge back to ${\mathbf{K}}_{r_t}^{-1}$. Both recursive steps take $\mathcal{O}(B^2)$ time. Note that although the recursive approach reduces the computation of ${\mathbf{K}}_{r_t}^{-1}$ to $\mathcal{O}(B^2)$ time, it takes at most $\mathcal{O}(B^2)$ time to compute the rest parts. Hence, the time complexity of BLCW-O is $\mathcal{O}(B^2)$ in total. Moreover, the space complexity of BLCW-O is $\mathcal{O}(B^2)$ since it needs to store ${\mathbf{K}}_{r_t}^{-1}$, ${\mathbf{\Omega }}_r$, $\mathit{\beta }$, etc., which dominate the main memory usage.

BLCW with Mean Removal (BLCW-M)

There may exist information loss whenever a BLCW update is performed; the loss comes from the SE removal through the projections. In other words, minimizing the loss between two Gaussian processes, $f_{t+1}(x)$ and $f_t^{\prime }(x)$, may lead to a better prediction performance. Because a prediction is made by using the mean function of a Gaussian process, combination coefficients associated with SEs in the mean function affect the prediction result. The removal of the SE with the smallest magnitude of the combination coefficient in the mean function of $f_t^{\prime }(x)$ is suggested,44$r_t=\underset{i\in {\mathcal{I}}_t}{\arg \min }|u_i^{\prime }|$where the SE removal is selected from ${\mathcal{I}}_t$ instead of ${\mathcal{I}}_t^{\prime }$.

Compared with BLCW-O, BLCW-M needs additional computation for $|u_i^{\prime }|,i\in {\mathcal{I}}_t$. it is dominated by the computation of ${\tau }_t{y}_t({\mathbf{e}}_B+\mathbf{h})$ and ${\tau }_t{y}_t\rho$, which takes $\mathcal{O}(B^2)$ time. After determining the removed SE, the time and space complexities of the BLCW update for BLCW-M are the same as those of BLCW-O, i.e., $\mathcal{O}(B^2)$ time and $\mathcal{O}(B^2)$ space. Hence, both time and complexities of BLCW-O are $\mathcal{O}(B^2)$.

BLCW with Divergence Removal (BLCW-D)

Let us consider another way to minimize information loss. A Gaussian process is characterized by mean and covariance functions, so the information loss should involve both functions. One way to measure the loss is to compute the divergence between two Gaussian processes. The removal of the SE with the smallest KL divergence based on the current example $(x_t,y_t)$ is suggested,45$r_t=\underset{r\in {\mathcal{I}}_t}{\arg \min }{D}_{\text{KL}}(\mathcal{N}(m_{t+1}(x_t),c_{t+1}(x_t,x_t))\parallel \mathcal{N}(m_t^{\prime }(x_t),c_t^{\prime }(x_t,x_t)))$where $D_{\text{KL}}(\mathcal{N}(a,b)\parallel \mathcal{N}(a^{\prime },b^{\prime }))=\frac{1}{2}\log \left(\frac{b^{\prime }}{b}\right)+\frac{b+{(a^{\prime }-a)}^2}{2b^{\prime }}-\frac{1}{2}$.

For each $r\in {\mathcal{I}}_t$, we need to compute the corresponding Gaussian process $f_{t+1}(x)$ for calculating its divergence with the intermediate Gaussian process $f_{t^{\prime }}(x)$. Each $f_{t+1}(x)$ takes the same time and complexities of BLCW-O, i.e., $\mathcal{O}(B^2)$ time and $\mathcal{O}(B^2)$ space. Because $f_{t^{\prime }}(x)$ is a by-product of the computation of any $f_{t+1}(x)$, the total time complexity of BLCW-D is still dominated by the inspection of all $f_{t+1}(x)$'s. Hence, the time complexity of BLCW-D is $\mathcal{O}(B^3)$ in total. In addition, the space complexity of BLCW-D is still $\mathcal{O}(B^2)$ because the computation of $f_{t+1}(x)$'s is performed in sequential order, not in parallel.

BLCW with Accuracy Removal (BLCW-A)

Because the goal of online learning is to make as many correct predictions as possible for the sequence of rounds, we need the updated Gaussian process $f_{t+1}(x)$ to predict well for future rounds. One way to measure the prediction power of $f_{t+1}(x)$ is to compute its accuracy based on available examples. This suggests removing the SE with the maximum accuracy based on available examples, or the minimum number of prediction mistakes,46$r_t=\underset{r\in {\mathcal{I}}_t}{\arg \min }\sum _{p\in {\mathcal{I}}_t^{\prime }}\mathbb{I}({\widehat{z}}_p\ne y_p)$where ${\widehat{z}}_p=\text{sign}(m_{t+1}(x_p))$ and $\left\{\right(x_i,y_i\left)\right|i\in {\mathcal{I}}_t^{\prime }\}$ is the set of available examples.

For each $r\in {\mathcal{I}}_t$, we need to compute the corresponding Gaussian process $f_{t+1}(x)$ for measuring its prediction power. Similarly, the total time complexity of BLCW-A is dominated by the inspection of all $f_{t+1}(x)$'s; thus, BLCW-A requires $\mathcal{O}(B^3)$ time. Of course, the space complexity of BLCW-A is still $\mathcal{O}(B^2)$ because the computation of $f_{t+1}(x)$'s is performed in a sequential order, not in parallel.

Experiments

We conducted various numerical experiments on real datasets to show the effectiveness of the proposed BLCW algorithm. The experimental results were organized into three phases. In phase 1, we showed that BLCW approximates LCW, which was used in this section as the abbreviation of the kernel-based LCW algorithm. In phase 2, we compared four kinds of removal strategies that are described in Section 3.3. In phase 3, the competitiveness of BLCW to state-of-the-art budgeted online algorithms was demonstrated.

We have used 10 typical and real datasets, which were collected from practical applications and could be downloaded from the LIBSVM website. Table 1 summarizes the detailed information about these datasets. For each dataset, we generated 20 distinct sequences of T examples that were permuted at random; T was equal to the size of the dataset, except for the cod-rna and mnist datasets. Because the computing power of our computer equipment was limited, we set T to one-tenth of the dataset size and sample at random for the cod-rna dataset. For the mnist dataset, it contained handwritten digit images from zero to nine (10 categories in total), so we used it to generate a one-versus-rest problem: we retained all images of digit one and sample images from the rest at random such that $T=20\hspace{0.17em}000$ (6742 1's and 13 258 R's). The prediction performance was measured by the cumulative mistake rate averaged over 20 sequences. All compared algorithms were kernel-based algorithms with the Gaussian kernel $k(\mathbf{x},{\mathbf{x}}^{\prime })=\exp (-\gamma \parallel \mathbf{x}-{\mathbf{x}}^{\prime }{\parallel }_2^2)$ where the hyperparameter γ was chosen from ${\{2}^{-5}{\mathrm{,2}}^{-4},\dots {\mathrm{,2}}^5\}$. Similar to the approach used in ref. [33]. γ was determined to have the best prediction performance with the Perceptron algorithm and applied to all algorithms. We set the confidence parameter η of CW, LCW, and BLCW algorithms to 0.55. All experiments were conducted with MATLAB R2017a.

Table 1 Detailed information of datasets ($\mathcal{X}\subseteq {ℝ}^n$).

Dataseta)	$\#$ Examples (T)	Size	$\#$ Features (n)	${\log }_2\gamma$
Liver disorders	$145$	$145$	$5$	$-1$
Heart	$270$	$270$	$13$	$-3$
Australian	$690$	$690$	$14$	$-3$
Diabetes	$768$	$768$	$8$	$0$
German	$1000$	$1000$	$24$	$-4$
svmguide3	$1243$	$1243$	$21$	$1$
svmguide1	$3089$	$3089$	$4$	$-5$
a4a	$4781$	$4781$	$123$	$-3$
cod-rna	$6000$	$59535$	$8$	$-5$
mnist (1 vs. R)	$20000$	$60000$	$780$	$-5$

Approximation of LCW

We verified that BLCW approximated LCW by using the oldest removal strategy; however, the observations held true for the other three strategies. The performance of the cumulative mistake rate is plotted as a function of the number of encountered examples for LCW and BLCW-O in Figure 3. The average number of total SEs used by LCW after all T examples were received was given. Small values of budgets were set for BLCW-O such that BLCW-O could perform BLCW updates more frequently. For completeness, BLCW-O with the budget set as the average number of SEs of LCW was provided.

[IMAGE OMITTED. SEE PDF]

Compared with the curves of BLCW-O, we could observe that the curve of LCW was almost always the lowest. This implied that the prediction performance of BLCW-O was worse than that LCW. Among several budgets being performed, BLCW-O with a larger budget tended to have a lower curve that was much closer to the curve of LCW; this meant that BLCW-O with a larger budget achieved a better prediction performance. Eventually, with a large enough budget, BLCW-O and LCW could not be distinguished. We also included the performance of the cumulative mistake rate versus the budget for BLCW-O and LCW in Figure 4. The result shows that the mistake rate of BLCW-O got closer to that of LCW as the budget increased. We concluded that BLCW approximated LCW.

[IMAGE OMITTED. SEE PDF]

Removal Strategies

Because different removal strategies might have very different prediction results, we studied the four strategies proposed in Section 3.3 and attempted to suggest some strategy as the default for BLCW. The performance of the cumulative mistake rate was plotted as a function of the budget B for LCW and BLCW in Figure 4. Since LCW was a non-budgeted online algorithm, we depicted it as a horizontal line. Note that although with different paces, curves of all four strategies tend to approach that of LCW when the budget increases. This observation validated our claim that BLCW approximated LCW. Curves of BLCW-O and BLCW-D were overlapping such that it was impossible to distinguish both. The reason was that we set the oldest SE as the removal default in our BLCW-D program and the KL divergence adopted by BLCW-D was almost zero for any candidate SE. Hence, it could not tell the difference between all candidate SEs. We might improve BLCW-D by using the KL divergence based on available examples $\{(x_i,y_i)|i\in {\mathcal{I}}_t^{\prime }\}$ instead of the current example $(x_t,y_t)$. However, the corresponding time complexity would grow greatly such that it was not worth giving it a try. Among the four strategies, BLCW-M almost always achieves the lowest mistake rate and thus shows a relatively stable prediction performance. It was because BLCW-M dealt with the combination coefficients of the mean function, which affected the prediction result directly. Hence, we recommended the mean removal strategy as the default for BLCW. In contrast, curves of BLCW-A did not show any obvious performance benefits. It was because the in-sample error of a small sample was easier to have a bias.

Competitiveness

Since the mean removal strategy showed the most stable prediction performance as shown in Section 4.2, we compared it, as the representative of BLCW, with the state-of-the-art budgeted online algorithms. RBP: the RBP algorithm with random removal strategy;^[32] Forgetron: the self-tuned Forgetron algorithm by shrinking and oldest removal strategy;^[31] Projectron: the Projectron algorithm using the projection strategy;^[33] Projectron++: the aggressive version of the Projectron algorithm that includes the notion of margin;^[33] FOGD: the FOGD algorithm using random Fourier features;^[34] and NOGD: the NOGD algorithm using Nyström-based features.^[34]

These algorithms were proposed for solving the problem of online binary classification. RBP randomly removed an SE from the set of current SEs when the budget constraint was reached and included the current instance as the SE by the Perceptron update.^[32] Since the removal of RBP was randomized, the performance of RBP was run and averaged over 10 times for each sequence. Forgetron shrank the intermediate hypothesis that was through the Perceptron update and then removed the oldest SE.^[31] Both Projectron and Projectron++ bound the number of SEs of the kernel-based Perceptron by projection.^[33] Projectron projected the kernel function centered on the current instance to the subspace spanned by kernel functions centered on SEs whenever the magnitude of projection error was less than a sparseness parameter η while Projectron++ introduced the notion of margin on top of Projectron. The number of SEs of Projectron (or Projection++) was bounded, but could not be known in advance. To have a fair comparison, we ran Projectron with different values of η; for each value of η, the corresponding number of SEs averaged over 20 sequences was set as the budget to run all budgeted online algorithms, except for Projectron++, which was run with η. FOGD approximated the shift-invariant kernel by the use of random Fourier features and updated the approximated linear hypothesis by the OGD algorithm.^[34] NOGD approximated the kernel matrix through the Nyström method and updated the approximated linear hypothesis by the OGD algorithm.^[34] Following the parameter setting in ref. [34], the number of Fourier components for FOGD was set to $4B$ and the rank approximation parameter for NOGD was set as $0.2B$. The step size η for both algorithms was selected from $\{\mathrm{2,0.2,}\dots \mathrm{,0.0002}\}$ randomly. Both algorithms were run and averaged 10 times for each sequence.

There were many other well-known classification methods that might be used for comparison. For example, logistic regression,^[29] SVMs,^[49] and Gaussian process classification^[46] are machine-learning-based classification methods. AlexNet,^[50] GoogLeNet,^[51] and ResNet^[52] are deep-learning-based classification methods. These types of methods aimed to learn a fixed classification model for new testing data by using the training data that needed to be collected before learning and thus fell in the realm of offline learning. Here, we only considered those methods that were designed for online learning. Specifically, we included Perceptron, PA, CW, and LCW for comparison. All four algorithms were run with the kernel trick and they belong to non-budgeted online methods.

The performance of the cumulative mistake rate is plotted as a function of the budget B for budgeted and non-budgeted online algorithms in Figure 5. Although we did not intend to stress this through the experiments here, LCW outperformed the other non-budgeted methods in most of the datasets. More importantly, Figure 5 shows that the curve of BLCW-M usually achieved the lowest among those of the other budgeted algorithms. This meant that BLCW-M outperformed the other budgeted algorithms and thus supported the claim that our proposed BLCW algorithm was competitive with state-of-the-art budgeted online algorithms.

[IMAGE OMITTED. SEE PDF]

We concluded this section with a brief comparison of the time and space complexities per round for budgeted and non-budgeted online algorithms, as summarized in Table 2. Since Perceptron, PA, CW, and LCW were non-budgeted algorithms, their time and space complexities grew up with the number of SEs, $|{\mathcal{I}}_t|$. Both complexities were linear in $|{\mathcal{I}}_t|$ for Perceptron and PA while quadratic for CW and LCW as they involved with the covariance function. In addition, both complexities of all budgeted algorithms studied in this section, including the proposed BLCW algorithm, were constant once the budget value was set. While we did not see the benefits from the complexity comparison at this point, BLCW-M outperformed the other state-of-the-art budgeted algorithms in terms of the prediction performance on the datasets collected from practical applications. Further reduction in complexities would make the proposed BLCW algorithm more accessible.

Table 2 Computational complexity per round for budgeted and non-budgeted online algorithms.

Algorithm	Time complexity	Space complexity
Perceptron	$\mathcal{O}(|{\mathcal{I}}_t|)$	$\mathcal{O}(|{\mathcal{I}}_t|)$
PA	$\mathcal{O}(|{\mathcal{I}}_t|)$	$\mathcal{O}(|{\mathcal{I}}_t|)$
CW	$\mathcal{O}(|{\mathcal{I}}_t{|}^2)$	$\mathcal{O}(|{\mathcal{I}}_t{|}^2)$
LCW	$\mathcal{O}(|{\mathcal{I}}_t{|}^2)$	$\mathcal{O}(|{\mathcal{I}}_t{|}^2)$
RBP	$\mathcal{O}(B)$	$\mathcal{O}(B)$
Forgetron	$\mathcal{O}(B^2)$	$\mathcal{O}(B^2)$
Projectron	$\mathcal{O}(B^2)$	$\mathcal{O}(B^2)$
Projectron++	$\mathcal{O}(B^2)$	$\mathcal{O}(B^2)$
FOGD	$\mathcal{O}(B)$	$\mathcal{O}(B)$
NOGD	$\mathcal{O}(B^2)$	$\mathcal{O}(B^2)$
BLCW-O	$\mathcal{O}(B^2)$	$\mathcal{O}(B^2)$
BLCW-M	$\mathcal{O}(B^2)$	$\mathcal{O}(B^2)$
BLCW-D	$\mathcal{O}(B^3)$	$\mathcal{O}(B^2)$
BLCW-A	$\mathcal{O}(B^3)$	$\mathcal{O}(B^2)$

Conclusions

In this paper, we bring the resource perspective into the kernel-based LCW algorithm. The kernel-based LCW algorithm is reinterpreted as an online algorithm that employs a Gaussian process for prediction. The Gaussian process is characterized by mean and covariance functions that consist of kernels of available resources (i.e., SEs) and their utilization degrees. From the resource perspective, we propose the BLCW algorithm to approximate the kernel-based LCW algorithm. Given a limited number of available resources, the proposed BLCW algorithm optimizes their utilization degrees through a constrained optimization problem. We further study four removal strategies for budget maintenance and suggest the mean removal as the default. Through extensive experiments, we have verified that BLCW algorithm is indeed an approximation of the kernel-based LCW algorithm and shown its competitiveness to state-of-the-art budgeted online algorithms.

Ideally, the kernel-based LCW algorithm may serve as an optimal point with an infinite budget ($B=\infty$), which corresponds to the situation where unlimited computation resources are supplied. In practice, the computation resources are never enough, and we often cannot do anything in this situation. Therefore, we propose the BLCW algorithm as an alternative solution. However, the figure of the budget cannot fully reveal the actual problem size, which depends on the data type we have to deal with. To build a useful and advanced intelligence system, we need to investigate the impact of the budget on various datasets and problem types in future works. As compared with other budgeted algorithms, evaluations of the computational complexity and efficiency may be refined to address this issue. Eventually, we may come up with a set of application guidelines for suggesting the optimal budget sizes for different scenarios. We will also study how to reduce the computational complexity of the BLCW algorithm furthermore and explore adaptive budget maintenance strategies that adjust based on the data characteristics and dynamics of the environment. Moreover, we hope to extend the current analysis to tackle multiclass classification and regression problems.

Appendix

Appendix

A1.

Matrix Derivative Identity

Proofs of Propositions 2 and 3 involve several matrix derivative identities, one of which requires additional derivations and is provided as the following lemma.

Lemma 4. Suppose $\mathbf{A}\in {ℝ}^{p\times m}$, $\mathbf{B}\in {ℝ}^{n\times p}$, and $\mathbf{C}\in {ℝ}^{p\times p}$ are matrices that are independent of $\mathbf{X}\in {ℝ}^{m\times n}$. Then, the matrix derivative of $g(\mathbf{X})=\det (\mathbf{A}\mathbf{X}\mathbf{B}+\mathbf{C})$ isA1$\frac{\partial g\left(\mathbf{X}\right)}{\partial \mathbf{X}}=\det (\mathbf{A}\mathbf{X}\mathbf{B}+\mathbf{C}){\mathbf{A}}^{\top }{(\mathbf{A}\mathbf{X}\mathbf{B}+\mathbf{C})}^{-\top }{\mathbf{B}}^{\top }$

Proof. Denote by $m_{ij}$ the $(i,j)$th entry of a matrix $\mathbf{M}$ and let $\mathbf{U}=\mathbf{A}\mathbf{X}\mathbf{B}+\mathbf{C}$. We prove the result by using the chain rule,^[53]A2$\frac{\partial \text{det}\left(\mathbf{U}\right)}{\partial x_{ij}}=\text{tr}\left[{\left(\frac{\partial \text{det}\left(\mathbf{U}\right)}{\partial \mathbf{U}}\right)}^{\top }\frac{\partial \mathbf{U}}{\partial x_{ij}}\right]$

The partial derivative of the $(k,l)$th entry of $\mathbf{U}$ with respect to the $(i,j)$th entry of $\mathbf{X}$ isA3$\frac{\partial u_{kl}}{\partial x_{ij}}=\frac{\partial }{\partial x_{ij}}(\sum _{q=1}^m\sum _{r=1}^n{a}_{kq}{x}_{qr}{b}_{rl}+c_{kl})=a_{ki}{b}_{jl}$

By Equation (A3), the partial derivative of $\mathbf{U}$ with respect to the $(i,j)$th entry of $\mathbf{X}$ isA4$\frac{\partial \mathbf{U}}{\partial x_{ij}}=\left[\begin{array}{ccc}{a}_{1i}{b}_{j1}& \dots & a_{1i}{B}_{jp}\\ ⋮& \ddots & ⋮\\ a_{pi}{b}_{j1}& \dots & a_{pi}{B}_{jp}\end{array}\right]={\mathbf{a}}_i{\mathbf{b}}_j^{\top }$where ${\mathbf{a}}_i$ is the ith column of $\mathbf{A}$ and ${\mathbf{b}}_j^{\mathrm{T}}$ is the jth row of $\mathbf{B}$. By Equation (49) from ref. [53] and Equation (A4), the chain rule givesA5$\begin{array}{l}\frac{\partial g\left(\mathbf{U}\right)}{\partial x_{ij}}=\text{tr}\left[{\left(\right(\det \mathbf{U}\left){\mathbf{U}}^{-\top }\right)}^{\top }{\mathbf{a}}_i{\mathbf{b}}_j^{\top }\right]\\ =\left(\det \mathbf{U}\right)\text{tr}\left[{\mathbf{b}}_j^{\top }{\mathbf{U}}^{-1}{\mathbf{a}}_i\right]\\ =\left(\det \mathbf{U}\right){\mathbf{a}}_i^{\top }{\mathbf{U}}^{-\top }{\mathbf{b}}_j,\end{array}$where the second equality uses the fact that $\text{tr}(\mathbf{Y}\mathbf{Z})=\text{tr}(\mathbf{Z}\mathbf{Y})$ holds for any two matrices, $\mathbf{Y}$ and $\mathbf{Z}$, with proper dimensions, and the third equality holds because a scalar value is equal to its transpose. Hence, we haveA6$\begin{array}{r}\frac{\partial g\left(\mathbf{X}\right)}{\partial \mathbf{X}}=\left(\det \mathbf{U}\right)\left[\begin{array}{c}{\mathbf{a}}_1^{\top }\\ ⋮\\ {\mathbf{a}}_m^{\top }\end{array}\right]{\mathbf{U}}^{-\top }\left[{\mathbf{b}}_1,\dots ,{\mathbf{b}}_n\right]\\ =\left(\det \mathbf{U}\right){\mathbf{A}}^{\top }{\mathbf{U}}^{-\top }{\mathbf{B}}^{\top }\end{array}$which completes the proof.

A2.

Proof of Proposition 2

We prove the result by induction. The initialization implies Equation (30a–c) for the first round (i.e., $t=1$) is valid. Suppose Equation (30a–c) holds for round t and proceed to prove the case for round $t+1$. We only need to take care of the situation where the Gaussian process violates the margin inequality (Equation (22)),A7$y_t{\tilde{m}}_t(x_t)<\psi {\tilde{c}}_t(x_t,x_t)$

Note that ${\tilde{\mathcal{I}}}_t={\mathcal{I}}_t$ and ${\tilde{\mathcal{I}}}_{t+1}={\mathcal{I}}_{t+1}={\tilde{\mathcal{I}}}_t\cup \{t\}$. Let $\widetilde{{\mathcal{I}}_t}=\{i_1,\dots ,i_N\}$ with $N=|\widetilde{{\mathcal{I}}_t}|$ and $i_1<\dots <i_N$, and $\mathbf{\Phi }=[{\mathit{\varphi }}_{i_1},\dots ,{\mathit{\varphi }}_{i_N},{\mathit{\varphi }}_t]$. Denote by ${\mathbf{S}}^{N+1}$ the set of $(N+1)\times (N+1)$ symmetric matrices. We rearrange Equation (25a,b) and (26a,b) into the following matrix representationA8a${\tilde{\mathit{\mu }}}_t=\mathbf{\Phi }\tilde{\mathbf{u}}$A8b${\tilde{\mathbf{\Sigma }}}_t=\mathbf{I}+\mathbf{\Phi }\tilde{\mathbf{\Omega }}{\mathbf{\Phi }}^{\top }$A8c$\tilde{\mathit{\mu }}=\mathbf{\Phi }\tilde{\mathbf{a}}$A8d$\tilde{\mathbf{\Sigma }}=\mathbf{I}+\mathbf{\Phi }\tilde{\mathbf{B}}{\mathbf{\Phi }}^{\top }$where$\begin{array}{r}\tilde{\mathbf{u}}={[u_{i_1}^{\left(t\right)},\dots ,u_{i_N}^{\left(t\right)},0]}^{\top }\in {\mathbb{R}}^{N+1}\\ \tilde{\mathbf{\Omega }}=\left[\begin{array}{cccc}{\omega }_{i_1,i_1}^{\left(t\right)}& \dots & {\omega }_{i_1,i_N}^{\left(t\right)}& 0\\ ⋮& \ddots & ⋮& ⋮\\ {\omega }_{i_N,i_1}^{\left(t\right)}& \dots & {\omega }_{i_N,i_N}^{\left(t\right)}& 0\\ 0& \dots & 0& 0\end{array}\right]\in {\mathbf{S}}^{N+1}\\ \tilde{\mathbf{a}}={[{\tilde{a}}_{i_1},\dots ,{\tilde{a}}_{i_N},{\tilde{a}}_t]}^{\top }\in {\mathbb{R}}^{N+1}\\ \tilde{\mathbf{B}}=\left[\begin{array}{cccc}{\tilde{b}}_{i_1,i_1}& \dots & {\tilde{b}}_{i_1,i_N}& {\tilde{b}}_{i_1,t}\\ ⋮& \ddots & ⋮& ⋮\\ {\tilde{b}}_{i_N,i_1}& \dots & {\tilde{b}}_{i_N,i_N}& {\tilde{b}}_{i_N,t}\\ {\tilde{b}}_{t,i_1}& \dots & {\tilde{b}}_{t,i_N}& {\tilde{b}}_{t,t}\end{array}\right]\in {\mathbf{S}}^{N+1}\end{array}$

By substituting Equation (A8a–d) into Equation (27), we obtain the following constrained optimization problemA9$\begin{array}{ll}\underset{\tilde{\mathbf{a}},\tilde{\mathbf{B}}}{\text{minimize}}& \frac{1}{2}\log \left(\frac{\det {\tilde{\mathbf{\Sigma }}}_t}{\det (\mathbf{I}+\mathbf{\Phi }\tilde{\mathbf{B}}{\mathbf{\Phi }}^{\top })}\right)+\frac{1}{2}\text{tr}\left({\tilde{\mathbf{\Sigma }}}_t^{-1}\right(\mathbf{I}+\mathbf{\Phi }\tilde{\mathbf{B}}{\mathbf{\Phi }}^{\top }\left)\right)\\ & +\frac{1}{2}{(\mathbf{\Phi }\tilde{\mathbf{u}}-\mathbf{\Phi }\tilde{\mathbf{a}})}^{\top }{\tilde{\mathbf{\Sigma }}}_t^{-1}(\mathbf{\Phi }\tilde{\mathbf{u}}-\mathbf{\Phi }\tilde{\mathbf{a}})\\ \text{subject to}& \psi {\mathit{\varphi }}_t^{\top }(\mathbf{I}+\mathbf{\Phi }\tilde{\mathbf{B}}{\mathbf{\Phi }}^{\top }){\mathit{\varphi }}_t-y_t{\mathit{\varphi }}_t^{\top }\mathbf{\Phi }\tilde{\mathbf{a}}\le 0\end{array}$

Because both the objective and constraint functions of Equation (A9) are convex in $(\tilde{\mathbf{a}},\tilde{\mathbf{B}})$, Equation (A9) is a convex optimization problem. We can turn to find a solution satisfying the Karush–Kuhn–Tucker (KKT) conditions.^[44] First, we define the Lagrangian of Equation (A9) to beA10$\begin{array}{r}L(\tilde{\mathbf{a}},\tilde{\mathbf{B}},\tau )=-\frac{1}{2}\log \det \left(\mathbf{I}+\mathbf{\Phi }\tilde{\mathbf{B}}{\mathbf{\Phi }}^{\top }\right)+\frac{1}{2}\mathrm{tr}\hspace{0.17em}\left({\tilde{\mathbf{\Sigma }}}_t^{-1}\mathbf{\Phi }\tilde{\mathbf{B}}{\mathbf{\Phi }}^{\top }\right)\\ +\frac{1}{2}{\left(\mathbf{\Phi }\tilde{\mathbf{u}}-\mathbf{\Phi }\tilde{\mathbf{a}}\right)}^{\top }{\tilde{\mathbf{\Sigma }}}_t^{-1}\left(\mathbf{\Phi }\tilde{\mathbf{u}}-\mathbf{\Phi }\tilde{\mathbf{a}}\right)\\ +\tau \left[\psi {\mathit{\varphi }}_t^{\top }\left(\mathbf{\Phi }\tilde{\mathbf{B}}{\mathbf{\Phi }}^{\top }\right){\mathit{\varphi }}_t-y_t{\mathit{\varphi }}_t^{\top }\mathbf{\Phi }\tilde{\mathbf{a}}\right]\\ +\mathrm{const}\end{array}$where τ is the Lagrange multiplier associated with the inequality constraint and $\text{const}$ consists of the remaining terms that do not depend on $(\tilde{\mathbf{a}},\tilde{\mathbf{B}})$.

Setting partial derivatives of L with respect to $\tilde{\mathbf{a}}$ to zero givesA11$\frac{\partial L}{\partial \tilde{\mathbf{a}}}={\mathbf{\Phi }}^{\top }\left[{\tilde{\mathbf{\Sigma }}}_t^{-1}\right(\mathbf{\Phi }\tilde{\mathbf{a}}-\mathbf{\Phi }\tilde{\mathbf{u}})-\tau y_t{\mathit{\varphi }}_t]=0$from which we obtain a solution as follows:A12${\tilde{\mathbf{\Sigma }}}_t^{-1}(\mathbf{\Phi }\tilde{\mathbf{a}}-\mathbf{\Phi }\tilde{\mathbf{u}})-\tau y_t{\mathit{\varphi }}_t=\mathbf{0}$orA13$\mathbf{\Phi }\tilde{\mathbf{a}}=\mathbf{\Phi }\tilde{\mathbf{u}}+\tau y_t{\tilde{\mathbf{\Sigma }}}_t{\mathit{\varphi }}_t$

Multiplying both sides of the aforementioned equation by ${\mathbf{\Phi }}^{\top }$ from the left and substituting with Equation (A8b) lead toA14$\mathbf{K}\tilde{\mathbf{a}}=\mathbf{K}\tilde{\mathbf{u}}+\tau y_t(\mathbf{k}+\mathbf{K}\tilde{\mathbf{\Omega }}\mathbf{k})$where $\mathbf{K}={\mathbf{\Phi }}^{\top }\mathbf{\Phi }$ and $\mathbf{k}={\mathbf{\Phi }}^{\top }{\mathit{\varphi }}_t$. Note that although this matrix multiplication is not reversible, later we can still find a solution satisfying Equation (A11). Let ${\mathbf{e}}_{N+1}={[0,...,0,1]}^{\top }\in {ℝ}^{N+1}$. Note that ${\mathbf{K}}^{-1}\mathbf{k}={\mathbf{e}}_{N+1}$ because $\mathbf{k}$ is the last column of $\mathbf{K}$. Multiplying both sides of Equation (A14) by ${\mathbf{K}}^{-1}$ from the left givesA15$\tilde{\mathbf{a}}=\tilde{\mathbf{u}}+\tau y_t({\mathbf{e}}_{N+1}+\tilde{\mathbf{\Omega }}\mathbf{k})$which indeed satisfies Equation (A11). This can be verified by directly substituting Equation (A15) and (A8b) back into Equation (A11).

Next, we deal with the partial derivatives for $\tilde{\mathbf{B}}$. Omitting the symmetry of $\tilde{\mathbf{B}}$ for now, we calculate the partial derivatives of L with respect to $\tilde{\mathbf{B}}$ and set them to zero,A16$\begin{array}{r}\frac{\partial L}{\partial \tilde{\mathbf{B}}}=-\frac{1}{2}{\mathbf{\Phi }}^{\top }{\left(\mathbf{I}+\mathbf{\Phi }\tilde{\mathbf{B}}{\mathbf{\Phi }}^{\top }\right)}^{-\top }\mathbf{\Phi }+\frac{1}{2}{\mathbf{\Phi }}^{\top }{\tilde{\mathbf{\Sigma }}}_t^{-\top }\mathbf{\Phi }+\tau \psi {\mathbf{\Phi }}^{\top }{\mathit{\varphi }}_t{\mathit{\varphi }}_t^{\top }\mathbf{\Phi }\\ ={\mathbf{\Phi }}^{\top }\left[-\frac{1}{2}{\left(\mathbf{I}+\mathbf{\Phi }\tilde{\mathbf{B}}{\mathbf{\Phi }}^{\top }\right)}^{-1}+\frac{1}{2}{\tilde{\mathbf{\Sigma }}}_t^{-1}+\tau \psi {\mathit{\varphi }}_t{\mathit{\varphi }}_t^{\top }\right]\mathbf{\Phi }\\ =0\end{array}$where the first equality uses Equation (70) and (101) from ref. [53] and Lemma 4. Equation (A16) gives a solution as followsA17${(\mathbf{I}+\mathbf{\Phi }\tilde{\mathbf{B}}{\mathbf{\Phi }}^{\top })}^{-1}={\tilde{\mathbf{\Sigma }}}_t^{-1}+2\tau \psi {\mathit{\varphi }}_t{\mathit{\varphi }}_t^{\top }$

We calculate the inverse of both sides of the previous equation by applying the Sherman–Morrison formula and obtainA18$\mathbf{I}+\mathbf{\Phi }\tilde{\mathbf{B}}{\mathbf{\Phi }}^{\top }={({\tilde{\mathbf{\Sigma }}}_t^{-1}+2\tau \psi {\mathit{\varphi }}_t{\mathit{\varphi }}_t^{\top })}^{-1}={\tilde{\mathbf{\Sigma }}}_t-\lambda {\tilde{\mathbf{\Sigma }}}_t{\mathit{\varphi }}_t{\mathit{\varphi }}_t^{\top }{\tilde{\mathbf{\Sigma }}}_t$withA19$\lambda =\frac{2\tau \psi }{1+2\tau \psi {\mathit{\varphi }}_t^{\top }{\tilde{\mathbf{\Sigma }}}_t{\mathit{\varphi }}_t}=\frac{2\tau \psi }{1+2\tau \psi \tilde{v}}$where $\tilde{v}={\mathit{\varphi }}_t^{\top }{\tilde{\mathbf{\Sigma }}}_t{\mathit{\varphi }}_t={\tilde{c}}_t(x_t,x_t)$. Multiplying both sides of Equation (A18) by ${\mathbf{\Phi }}^{\top }$ from the left and $\mathbf{\Phi }$ from the right and substituting with Equation (A8b) lead toA20$\mathbf{K}\tilde{\mathbf{B}}\mathbf{K}=\mathbf{K}\tilde{\mathbf{\Omega }}\mathbf{K}-\lambda (\mathbf{k}+\mathbf{K}\tilde{\mathbf{\Omega }}\mathbf{k}){(\mathbf{k}+\mathbf{K}\tilde{\mathbf{\Omega }}\mathbf{k})}^{\top }$

Similarly, these two matrix multiplications are not reversible; however, we can find a solution satisfying Equation (A16) later. Multiplying both sides of the previous equation by ${\mathbf{K}}^{-1}$ from the left and right givesA21$\tilde{\mathbf{B}}=\tilde{\mathbf{\Omega }}-\lambda ({\mathbf{e}}_{N+1}+\tilde{\mathbf{\Omega }}\mathbf{k}){({\mathbf{e}}_{N+1}+\tilde{\mathbf{\Omega }}\mathbf{k})}^{\top }$which can be shown to satisfy Equation (A16) by using Equation (A18). Moreover, we can observe that Equation (A21) makes sure of the symmetry of $\tilde{\mathbf{B}}$.

The KKT conditions for the convex optimization problem (Equation (A9)) imply that the constraint in Equation (A9) holds with equality,A22$\psi (k_{tt}+{\mathbf{k}}^{\top }\tilde{\mathbf{B}}\mathbf{k})-y_t{\mathbf{k}}^{\top }\tilde{\mathbf{a}}=0$where $k_{tt}=k(x_t,x_t)$. Substituting Equation (A15), (A19), and (A21) into the previous equation givesA23$\psi \tilde{v}-\left(\frac{2\tau \psi }{1+2\tau \psi \tilde{v}}\right)\psi {\tilde{v}}^2=\tilde{m}+\tau \tilde{v}$where $\tilde{m}=y_t{\mathbf{k}}^{\top }\tilde{\mathbf{u}}=y_t{\tilde{m}}_t\left(x_t\right)$ and we have used the fact that $\tilde{v}=k_{tt}+{\mathbf{k}}^{\top }\tilde{\mathbf{\Omega }}\mathbf{k}$. Following a derivation similar to the subsequent derivation for Equation (17) from ref. [21], we obtainA24$\begin{array}{r}\tau =\frac{-(1+2\psi \tilde{m})+\sqrt{{(1+2\psi \tilde{m})}^2-8\psi (\tilde{m}-\psi \tilde{v})}}{4\psi \tilde{v}}\\ >0.\end{array}$

We have shown that there exists a solution satisfying the KKT conditions for Equation (A9), i.e., Equation (A15), (A21), and (A24). Moreover, substituting Equation (A8a–d), (A15), (A19), (A21), and (A24) into Equation (24b–c) and comparing the result with Equation (15a,b), we can observe that 1) ${\tilde{\mathcal{I}}}_{t+1}={\mathcal{I}}_{t+1}$ and 2) ${\tilde{m}}_{t+1}(x)$ and $m_{t+1}(x)$ have the same combination coefficients of SEs, and 3) ${\tilde{c}}_{t+1}(x,x^{\prime })$ and $c_{t+1}(x,x^{\prime })$ have the same combination coefficients of SE pairs. These observations imply that Equation (30a–c) holds for round $t+1$ and thus completes the proof.

A3.

Proof of Proposition 3

First, we write down the detailed expressions of ${\mathit{\mu }}_t$, ${\mathbf{\Sigma }}_t$, $\mathit{\mu }$, and $\mathbf{\Sigma }$ associated with the decomposition (Equation (34a–d)),A25a${\mathit{\mu }}_t=\sum _{i\in {\mathcal{I}}_t}{u}_i^{(t)}{\mathit{\varphi }}_i$A25b${\mathbf{\Sigma }}_t=\mathbf{I}+\sum _{i\in {\mathcal{I}}_t}\sum _{j\in {\mathcal{I}}_t}{\omega }_{ij}^{\left(t\right)}{\mathit{\varphi }}_i{\mathit{\varphi }}_j^{\top }$A25c$\mathit{\mu }={\mathit{\mu }}_t-u_r^{(t)}{\mathit{\varphi }}_r+\sum _{i\in {\mathcal{I}}_{t+1}}{\delta }_i{\mathit{\varphi }}_i$A25d$\mathbf{\Sigma }=\mathbf{I}+\sum _{i\in {\mathcal{I}}_t\left\{r\right\}}\sum _{j\in {\mathcal{I}}_t\left\{r\right\}}{w}_{ij}^{\left(t\right)}{\mathit{\varphi }}_i{\mathit{\varphi }}_j^{\mathrm{T}}+\sum _{i\in {\mathcal{I}}_{t+1}}\sum _{j\in {\mathcal{I}}_{t+1}}{z}_{ij}{\mathit{\varphi }}_i{\mathit{\varphi }}_j^{\top }$

By a change of variables with Equation (A25a–d), we turn to find the increments in utilization degrees of the B available resources. ${\delta }_i$ and $z_{ij}$ are the increments associated with $k(x,x_i)$ and $k(x,x_i)k(x_j,x^{\prime })$, respectively.

Note that ${\mathcal{I}}_t\backslash \{r\}=\{i_1,\dots ,i_{B-1}\}$ with $i_1<\dots <i_{B-1}$ and let ${\mathbf{\Phi }}_r=[{\mathit{\varphi }}_{i_1},\dots ,{\mathit{\varphi }}_{i_{B-1}},{\mathit{\varphi }}_t]$. Denote by ${\mathbf{S}}^B$ the set of $B\times B$ symmetric matrices. For convenience, we rearrange Equation (A25b–d) into the following matrix representationA26a${\mathbf{\Sigma }}_t=\mathbf{I}+{\mathbf{\Phi }}_r{\mathbf{\Omega }}_r{\mathbf{\Phi }}_r^{\top }+{\mathbf{\Phi }}_r{\mathit{\omega }}_r{\mathit{\varphi }}_r^{\top }+{\mathit{\varphi }}_r{\mathit{\omega }}_r^{\top }{\mathbf{\Phi }}_r^{\top }+w_{rr}^{\left(t\right)}{\mathit{\varphi }}_r{\mathit{\varphi }}_r^{\top }$A26b$\mathit{\mu }={\mathit{\mu }}_t-u_r^{(t)}{\mathit{\varphi }}_r+{\mathbf{\Phi }}_r\mathit{\delta },$A26c$\mathbf{\Sigma }=\mathbf{I}+{\mathbf{\Phi }}_r{\mathbf{\Omega }}_r{\mathbf{\Phi }}_r^{\top }+{\mathbf{\Phi }}_r\mathbf{Z}{\mathbf{\Phi }}_r^{\top }$where$\begin{array}{rr}\mathit{\delta }& ={[{\delta }_{i_1},\dots ,{\delta }_{i_{B-1}},{\delta }_t]}^{\top }\in {\mathbb{R}}^B,\\ \mathbf{Z}& =\left[\begin{array}{cccc}{z}_{i_1,i_1}& \dots & z_{i_1,i_{B-1}}& z_{i_1,t}\\ ⋮& \ddots & ⋮& ⋮\\ z_{i_{B-1},i_1}& \dots & z_{i_{B-1},i_{B-1}}& z_{i_{B-1},t}\\ z_{t,i_1}& \dots & z_{t,i_{B-1}}& z_{t,t}\end{array}\right]\in {\mathbf{S}}^B.\end{array}$

Note that for ${\mathbf{\Sigma }}_t$ we write out those terms that depend on the removed SE $x_r$. By substituting Equation (A26b,c) into Equation (36), we get the following constrained optimization problemA27$\begin{array}{ll}\underset{\mathit{\delta },\mathbf{Z}}{\text{minimize}}& \frac{1}{2}\log \left(\frac{\det {\mathbf{\Sigma }}_t}{\det (\mathbf{I}+{\mathbf{\Phi }}_r{\mathbf{\Omega }}_r{\mathbf{\Phi }}_r^{\top }+{\mathbf{\Phi }}_r\mathbf{Z}{\mathbf{\Phi }}_r^{\top })}\right)\\ & +\frac{1}{2}\text{tr}\left({\mathbf{\Sigma }}_t^{-1}\right(\mathbf{I}+{\mathbf{\Phi }}_r{\mathbf{\Omega }}_r{\mathbf{\Phi }}_r^{\top }+{\mathbf{\Phi }}_r\mathbf{Z}{\mathbf{\Phi }}_r^{\top }\left)\right)\\ & +\frac{1}{2}{(u_r^{\left(t\right)}{\mathit{\varphi }}_r-{\mathbf{\Phi }}_r\mathit{\delta })}^{\top }{\mathbf{\Sigma }}_t^{-1}(u_r^{\left(t\right)}{\mathit{\varphi }}_r-{\mathbf{\Phi }}_r\mathit{\delta })\\ \text{subject to}& \psi {\mathit{\varphi }}_t^{\top }(\mathbf{I}+{\mathbf{\Phi }}_r{\mathbf{\Omega }}_r{\mathbf{\Phi }}_r^{\top }+{\mathbf{\Phi }}_r\mathbf{Z}{\mathbf{\Phi }}_r^{\top }){\mathit{\varphi }}_t\\ & -y_t{\mathit{\varphi }}_t^{\top }({\mathit{\mu }}_t-u_r^{\left(t\right)}{\mathit{\varphi }}_r+{\mathbf{\Phi }}_r\mathit{\delta })\le 0\end{array}$

Because both the objective and constraint functions of Equation (A27) are convex, Equation (A27) is also a convex optimization problem. Hence, we find a solution satisfying the KKT conditions.^[44] The Lagrangian of Equation (A27) is defined asA28$\begin{array}{r}L(\mathit{\delta },\mathbf{Z},\tau )=-\frac{1}{2}\log \det \left(\mathbf{I}+{\mathbf{\Phi }}_r{\mathbf{\Omega }}_r{\mathbf{\Phi }}_r^{\top }+{\mathbf{\Phi }}_r\mathbf{Z}{\mathbf{\Phi }}_r^{\top }\right)\\ +\frac{1}{2}\mathrm{tr}\hspace{0.17em}\left({\mathbf{\Sigma }}_t^{-1}{\mathbf{\Phi }}_r\mathbf{Z}{\mathbf{\Phi }}_r^{\top }\right)\\ +\frac{1}{2}{\left(u_r^{\left(t\right)}{\mathit{\varphi }}_r-{\mathbf{\Phi }}_r\mathit{\delta }\right)}^{\top }{\mathbf{\Sigma }}_t^{-1}\left(u_r^{\left(t\right)}{\mathit{\varphi }}_r-{\mathbf{\Phi }}_r\mathit{\delta }\right)\\ +\tau \left[\psi {\mathit{\varphi }}_t^{\top }\left({\mathbf{\Phi }}_r\mathbf{Z}{\mathbf{\Phi }}_r^{\top }\right){\mathit{\varphi }}_t-y_t{\mathit{\varphi }}_t^{\top }\left({\mathbf{\Phi }}_r\mathit{\delta }\right)\right]\\ +\mathrm{const}\hspace{0.17em}\end{array}$where τ is the Lagrange multiplier associated with the inequality constraint and $\text{const}$ consists of the remaining terms that do not depend on $(\mathit{\delta },\mathbf{Z})$.

Setting partial derivatives of L with respect to $\mathit{\delta }$ to zero givesA29$\frac{\partial L}{\partial \mathit{\delta }}={\mathbf{\Phi }}_r^{\top }\left[{\mathbf{\Sigma }}_t^{-1}\right({\mathbf{\Phi }}_r\mathit{\delta }-u_r^{\left(t\right)}{\mathit{\varphi }}_r)-\tau y_t{\mathit{\varphi }}_t]=0$which provides a solution as followsA30${\mathbf{\Sigma }}_t^{-1}({\mathbf{\Phi }}_r\mathit{\delta }-u_r^{(t)}{\mathit{\varphi }}_r)-\tau y_t{\mathit{\varphi }}_t=\mathbf{0}$orA31${\mathbf{\Phi }}_r\mathit{\delta }=u_r^{(t)}{\mathit{\varphi }}_r+\tau y_t{\mathbf{\Sigma }}_t{\mathit{\varphi }}_t$

Multiplying both sides of the above equation by ${\mathbf{\Phi }}_r^{\top }$ from the left and substituting with Equation (A26a) lead toA32${\mathbf{K}}_r\mathit{\delta }=u_r^{\left(t\right)}{\mathbf{k}}_r+\tau y_t({\mathbf{k}}_t+{\mathbf{K}}_r{\mathbf{\Omega }}_r{\mathbf{k}}_t+{\mathbf{K}}_r{\mathit{\omega }}_r{k}_{rt}+{\mathbf{k}}_r{\mathit{\omega }}_r^{\top }{\mathbf{k}}_t+{\omega }_{rr}^{\left(t\right)}{\mathbf{k}}_r{k}_{rt})$where we recall ${\mathbf{K}}_r={\mathbf{\Phi }}_r^{\top }{\mathbf{\Phi }}_r$, ${\mathbf{k}}_t={\mathbf{\Phi }}_r^{\top }{\mathit{\varphi }}_t$, ${\mathbf{k}}_r={\mathbf{\Phi }}_r^{\top }{\mathit{\varphi }}_r$, and $k_{rt}=k(x_r,x_t)$. This matrix multiplication is not reversible, but we can still find a solution satisfying Equation (A29) later. Note that ${\mathbf{K}}_r^{-1}{\mathbf{k}}_t={\mathbf{e}}_B$. Multiplying both sides of Equation (A32) by ${\mathbf{K}}_r^{-1}$ from the left givesA33$\mathit{\delta }=\tau y_t({\mathbf{e}}_B+{\mathbf{\Omega }}_r{\mathbf{k}}_t+{\mathit{\omega }}_r{k}_{rt})+{\mathbf{K}}_r^{-1}{\mathbf{k}}_r(u_r^{\left(t\right)}+\tau y_t({\mathit{\omega }}_r^{\top }{\mathbf{k}}_t+{\omega }_{rr}^{\left(t\right)}{k}_{rt}\left)\right)$which turns out to be a solution of Equation (A29). This can be verified by substituting Equation (A33) back into Equation (A31) and taking the assumption for the feature vector of $x_r$, ${\mathbf{\Phi }}_r{\mathbf{K}}_r^{-1}{\mathbf{k}}_r={\mathit{\varphi }}_r$.

Now, we turn to handle the partial derivatives for $\mathbf{Z}$. Again, omitting the symmetry of $\mathbf{Z}$ for now, we compute the partial derivatives of L with respect to $\mathbf{Z}$ and set them to zero:A34$\begin{array}{r}\frac{\partial L}{\partial \mathbf{Z}}=-\frac{1}{2}{\mathbf{\Phi }}_r^{\top }{\left(\mathbf{I}+{\mathbf{\Phi }}_r{\mathbf{\Omega }}_r{\mathbf{\Phi }}_r^{\top }+{\mathbf{\Phi }}_r\mathbf{Z}{\mathbf{\Phi }}_r^{\top }\right)}^{-\top }{\mathbf{\Phi }}_r\\ +\frac{1}{2}{\mathbf{\Phi }}_r^{\top }{\mathbf{\Sigma }}_t^{-\top }{\mathbf{\Phi }}_r+\tau \psi {\mathbf{\Phi }}_r^{\top }{\mathit{\varphi }}_t{\mathit{\varphi }}_t^{\top }{\mathbf{\Phi }}_r\\ ={\mathbf{\Phi }}_r^{\top }\left[-\frac{1}{2}{\left(\mathbf{I}+{\mathbf{\Phi }}_r{\mathbf{\Omega }}_r{\mathbf{\Phi }}_r^{\top }+{\mathbf{\Phi }}_r\mathbf{Z}{\mathbf{\Phi }}_r^{\top }\right)}^{-\top }+\frac{1}{2}{\mathbf{\Sigma }}_t^{-\top }+\tau \psi {\mathit{\varphi }}_t{\mathit{\varphi }}_t^{\top }\right]{\mathbf{\Phi }}_r\\ =0\end{array}$where the first equality uses Equation (70) and (101) from ref. [53] and Lemma 4. Equation (A34) provides a solution as followsA35${(\mathbf{I}+{\mathbf{\Phi }}_r{\mathbf{\Omega }}_r{\mathbf{\Phi }}_r^{\top }+{\mathbf{\Phi }}_r\mathbf{Z}{\mathbf{\Phi }}_r^{\top })}^{-1}={\mathbf{\Sigma }}_t^{-1}+2\tau \psi {\mathit{\varphi }}_t{\mathit{\varphi }}_t^{\top }$

We compute the inverse of both sides of the previous equation by using the Sherman–Morrison formula and getA36$\mathbf{I}+{\mathbf{\Phi }}_r{\mathbf{\Omega }}_r{\mathbf{\Phi }}_r^{\top }+{\mathbf{\Phi }}_r\mathbf{Z}{\mathbf{\Phi }}_r^{\top }={({\mathbf{\Sigma }}_t^{-1}+2\tau \psi {\mathit{\varphi }}_t{\mathit{\varphi }}_t^{\top })}^{-1}={\mathbf{\Sigma }}_t-\lambda {\mathbf{\Sigma }}_t{\mathit{\varphi }}_t{\mathit{\varphi }}_t^{\top }{\mathbf{\Sigma }}_t$withA37$\lambda =\frac{2\tau \psi }{1+2\tau \psi {\mathit{\varphi }}_t^{\top }{\mathbf{\Sigma }}_t{\mathit{\varphi }}_t}=\frac{2\tau \psi }{1+2\tau \psi v}$where $v={\mathit{\varphi }}_t^{\top }{\mathbf{\Sigma }}_t{\mathit{\varphi }}_t=c_t(x_t,x_t)$. Multiplying both sides of Equation (A36) by ${\mathbf{\Phi }}_r^{\top }$ from the left and by ${\mathbf{\Phi }}_r$ from the right and substituting Equation (A26a) lead toA38${\mathbf{K}}_r\mathbf{Z}{\mathbf{K}}_r=[{\mathbf{K}}_r{\mathit{\omega }}_r{\mathbf{k}}_r^{\top }+{\mathbf{k}}_r{\mathit{\omega }}_r^{\top }{\mathbf{K}}_r+w_{rr}^{\left(t\right)}{\mathbf{k}}_r{\mathbf{k}}_r^{\top }]-\lambda {\mathbf{h}}_1{\mathbf{h}}_1^{\top }$withA39${\mathbf{h}}_1={\mathbf{k}}_t+{\mathbf{K}}_r{\mathbf{\Omega }}_r{\mathbf{k}}_t+{\mathbf{K}}_r{\mathit{\omega }}_r{k}_{rt}+{\mathbf{k}}_r{\mathit{\omega }}_r^{\top }{\mathbf{k}}_t+w_{rr}^{\left(t\right)}{\mathbf{k}}_r{k}_{rt}$

Similarly, these two matrix multiplications are not reversible, but we can still find a solution satisfying Equation (A34) later. Multiplying both sides of Equation (A38) by ${\mathbf{K}}_r^{-1}$ from the left and right givesA40$\mathbf{Z}=[{\mathit{\omega }}_r{\mathbf{k}}_r^{\mathrm{T}}{\mathbf{K}}_r^{-1}+{\mathbf{K}}_r^{-1}{\mathbf{k}}_r{\mathit{\omega }}_r^{\mathrm{T}}+w_{rr}^{(t)}{\mathbf{K}}_r^{-1}{\mathbf{k}}_r{\mathbf{k}}_r^{\mathrm{T}}{\mathbf{K}}_r^{-1}]-\lambda {\mathbf{h}}_2{\mathbf{h}}_2^{\mathrm{T}}$withA41${\mathbf{h}}_2={\mathbf{e}}_B+{\mathbf{\Omega }}_r{\mathbf{k}}_t+{\mathit{\omega }}_r{k}_{rt}+{\mathbf{K}}_r^{-1}{\mathbf{k}}_r({\mathit{\omega }}_r^{\mathrm{T}}{\mathbf{k}}_t+w_{rr}^{(t)}{k}_{rt})$

Note that Equation (A40) is a solution of Equation (A34). We can verify it by substituting Equation (A40) and (A41) back into Equation (A36) and adopting the assumption for the feature vector of $x_r$, ${\mathbf{\Phi }}_r{\mathbf{K}}_r^{-1}{\mathbf{k}}_r={\mathit{\varphi }}_r$. Moreover, Equation (A40) is symmetric.

The KKT conditions for the convex optimization problem (Equation (A27)) imply that the constraint in Equation (A27) holds with equality,A42$\psi (k_{tt}+{\mathbf{k}}_t^{\top }{\mathbf{\Omega }}_r{\mathbf{k}}_t+{\mathbf{k}}_t^{\top }\mathbf{Z}{\mathbf{k}}_t)=y_t\left(m_t\right(x_t)-u_r^{\left(t\right)}{k}_{rt}+{\mathbf{k}}_t^{\top }\mathit{\delta })$

By substituting Equation (A33), (A37), (A40), and (A41) into the previous equation and rearranging with some efforts, we getA43$\psi v-\left(\frac{2\tau \psi }{1+2\tau \psi v}\right)\psi v^2=m+\tau v$where $m=y_t{m}_t(x_t)$ and we have used the fact that $v=k_{tt}+{\mathbf{k}}_t^{\top }{\mathbf{\Omega }}_r{\mathbf{k}}_t+2{\mathbf{k}}_t^{\top }{\mathit{\omega }}_r{k}_{rt}+w_{rr}^{\left(t\right)}{k}_{rt}^2=c_t(x_t,x_t)$. Again, by following a derivation similar to the subsequent derivation for Equation (17) from ref. [21], we getA44$\begin{array}{r}\tau =\frac{-(1+2\psi m)+\sqrt{{(1+2\psi m)}^2-8\psi (m-\psi v)}}{4\psi v}\\ >0\end{array}$

Note that Equation (A33), (A40), and (A44) are a solution satisfying the KKT conditions for Equation (A27). Therefore, Equation (A33), (A37), (A40), (A41), and (A44) give the BLCW update rule. ▪

Acknowledgements

This work received funding from various sources, including the National Science and Technology Council (grants: 110-2811-M-A49-550-MY2, 112-2811-M-A49-557-, 112-2634-F-A49-003-, 113-2118-M-A49-007-MY2, 113-2923-M-A49-004-MY3), the Higher Education Sprout Project of the National Yang Ming Chiao Tung University from the Ministry of Education, Taiwan, and the Biomedical Artificial Intelligence Academy of the Kaohsiung Medical University, Taiwan. We also thank Wan-Yi Tai for her valuable assistance and acknowledge the National Center for High-performance Computing for providing computing resources.

Conflict of Interest

The authors declare no conflict of interest.

Author Contributions

Jacky Chung-Hao Wu: Conceptualization (lead); Data curation (equal); Formal analysis (lead); Funding acquisition (supporting); Investigation (lead); Methodology (lead); Software (equal); Validation (lead); Visualization (lead); Writing—original draft (lead); Writing – review & editing (lead). Yu-Shiou Lin: Conceptualization (equal); Data curation (equal); Formal analysis (equal); Investigation (equal); Methodology (equal); Software (equal); Validation (equal); Visualization (equal); Writing—original draft (equal); Writing—review & editing (equal). Henry Horng-Shing Lu: Conceptualization (supporting); Formal analysis (supporting); Funding acquisition (lead); Investigation (supporting); Methodology (supporting); Resources (lead); Supervision (lead); Writing—review & editing (supporting). Hsueh-Ming Hang: Project administration (supporting); Resources (supporting); Supervision (supporting); Writing—review & editing (supporting).

Data Availability Statement

The data that support the findings of this study are available from the corresponding author upon reasonable request.

References

Y. Freund, R. E. Schapire, Mach. Learn. 1999, 37, 277.

C. Gentile, Mach. Learn. 2003, 53, 265.

J. Kivinen, A. J. Smola, R. C. Williamson, IEEE Trans. Signal Process. 2004, 52, 2165.

N. Cesa‐Bianchi, G. Lugosi, Prediction, Learning, and Games, Cambridge University Press, Cambridge 2006.

S. Shalev‐Shwartz, Found. Trends Mach. Learn. 2012, 4, 107.

S. C. H. Hoi, J. Wang, P. Zhao, J. Mach. Learn. Res. 2014, 15, 495.

S. C. H. Hoi, D. Sahoo, J. Lu, P. Zhao, Neurocomputing 2021, 459, 249.

E. Hazan, Introduction to Online Convex Optimization, arXiv:1909.05207 2019.

K. Jun, F. Orabona, in Proc. COLT’19, Phoenix, AZ 2019, pp. 1802–1823.

E. Hazan, E. Minasyan, in Proc. COLT’20, Virtual Event, Graz, Austria 2020, pp. 1877–1893.

H. B. McMahan, G. Holt, D. Sculley, M. Young, D. Ebner, J. Grady, L. Nie, T. Phillips, E. Davydov, D. Golovin, S. Chikkerur, D. Liu, M. Wattenberg, A. M. Hrafnkelsson, T. Boulos, J. Kubica, in Proc. KDD’13, Chicago, IL 2013, pp. 1222–1230.

J. Lu, S. C. H. Hoi, J. Wang, in Proc. ACML’13, Canberra, ACT, Australia 2013, pp. 325–340.

J. Ma, L. K. Saul, S. Savage, G. M. Voelker, in Proc. ICML’09, Montreal, Quebec, Canada 2009, pp. 681–688.

B. Li, P. Zhao, S. C. H. Hoi, V. Gopalkrishnan, Mach. Learn. 2012, 87, 221.

F. Rosenblatt, Psychol. Rev. 1958, 65, 386.

A. B. J. Novikoff, in Proc. Symp. on the Mathematical Theory of Automata, New York, NY 1962, Vol. 12, pp. 615–622.

C. Gentile, J. Mach. Learn. Res. 2001, 2, 213.

M. Zinkevich, in Proc. ICML’03, Washington, DC 2003, pp. 928–936.

K. Crammer, O. Dekel, J. Keshet, S. Shalev‐Shwartz, Y. Singer, J. Mach. Learn. Res. 2006, 7, 551.

M. Dredze, K. Crammer, F. Pereira, in Proc. ICML’08, Helsinki, Finland 2008, pp. 264–271.

K. Crammer, M. Dredze, F. Pereira, J. Mach. Learn. Res. 2012, 13, 1891.

K. Crammer, M. Dredze, F. Pereira, in Proc. NIPS’08, Vancouver, British Columbia, Canada 2008, pp. 345–352.

J. Wang, P. Zhao, S. C. H. Hoi, in Proc. ICML’12, Edinburgh, Scotland, UK 2012.

J. Wang, P. Zhao, S. C. H. Hoi, ACM Trans. Intell. Syst. Technol. 2016, 8, 15:1.

K. Crammer, Y. Singer, J. Mach. Learn. Res. 2003, 3, 951.

S. Matsushima, N. Shimizu, K. Yoshida, T. Ninomiya, H. Nakagawa, in Proc. SDM’10, Columbus, OH 2010, pp. 303–314.

K. Crammer, M. Dredze, A. Kulesza, in Proc. EMNLP’09, Singapore 2009, pp. 496–504.

B. Schölkopf, A. J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, Cambridge, MA 2001.

C. M. Bishop, Pattern Recognition and Machine Learning, Springer‐Verlag, Berlin 2006.

K. Crammer, J. Kandola, Y. Singer, in Proc. NIPS’03, Vancouver and Whistler, British Columbia, Canada 2003, pp. 225–232.

O. Dekel, S. Shalev‐Shwartz, Y. Singer, J. Comput. 2008, 37, 1342.

G. Cavallanti, N. Cesa‐Bianchi, C. Gentile, Mach. Learn. 2007, 69, 143.

F. Orabona, J. Keshet, B. Caputo, J. Mach. Learn. Res. 2009, 10, 2643.

J. Lu, S. C. H. Hoi, J. Wang, P. Zhao, Z.‐Y. Liu, J. Mach. Learn. Res. 2016, 17, 1.

J. Wang, S. C. H. Hoi, P. Zhao, J. Zhuang, Z. Liu, in Proc. IJCAI’13, Beijing, China 2013, pp. 1750–1756.

J. Gama, I. Zliobaite, A. Bifet, M. Pechenizkiy, A. Bouchachia, ACM Comput. Surv. 2014, 46, 44:1.

A. Bifet, G. Holmes, R. Kirkby, B. Pfahringer, J. Mach. Learn. Res. 2010, 11, 1601.

A. Bifet, G. Holmes, B. Pfahringer, in Proc. ECML PKDD’10, Barcelona, Spain 2010, pp. 135–150.

H. M. Gomes, A. Bifet, J. Read, J. P. Barddal, F. Enembreck, B. Pfahringer, G. Holmes, T. Abdessalem, Mach. Learn. 2017, 106, 1469.

A. Cano, B. Krawczyk, Mach. Learn. 2020, 109, 175.

B. Krawczyk, A. Cano, in Proc. IJCAI’19, Macao, China 2019, pp. 2763–2771.

L. Korycki, A. Cano, B. Krawczyk, in Proc. IEEE BigData’19, Los Angeles, CA 2019, pp. 2334–2343.

S. You, H. Lin, in Proc. PAKDD’16, Auckland, New Zealand 2016, pp. 115–126.

S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY 2004.

Z. Wang, K. Crammer, S. Vucetic, J. Mach. Learn. Res. 2012, 13, 3103.

C. E. Rasmussen, C. K. I. Williams, Gaussian Processes for Machine Learning, MIT Press, Cambridge, MA 2006.

C.‐H. Wu, H. H.‐S. Lu, H.‐M. Hang, IEEE Access 2020, 8, 227420.

Y.‐S. Lin, C.‐H. Wu, H. H.‐S. Lu, in Proc. ICCBDC’19, Oxford, UK 2019, pp. 6–10.

C.‐W. Hsu, C.‐J. Lin IEEE Trans. Neural Netw. 2002, 13, 415.

A. Krizhevsky, I. Sutskever, G. E. Hinton, in Proc. NIPS’12, Lake Tahoe, Nevada 2012, pp. 1106–1114.

C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. E. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, A. Rabinovich, in Proc. CVPR’15, Boston, MA 2015, pp. 1–9.

K. He, X. Zhang, S. Ren, J. Sun, in Proc. CVPR’16, Las Vegas, NV 2016, pp. 770–778.

K. B. Petersen, M. S. Pedersen, The Matrix Cookbook, Version 20121115, November 2012, http://www2.compute.dtu.dk/pubdb/pubs/3274‐full.html.