Gossiped and Quantized Online Multi-Kernel Learning

Many of the latest efforts in machine learning are focused on bringing learning as close to data collection as possible. This is of practical interest in a diverse array of applications, sensor networks in particular. In sensor networks, nodes are often communication-constrained, operate distributively, and can send only a few bits to their neighbors.

There are several papers in the literature that consider the problem of designing distributed learning methods for Online Multi-Kernel Learning (OMKL). In particular, [1] contains the design and regret analysis of quantized and distributed OMKL for a fully connected (complete) graph. Although the fully connected case is important, it is not applicable in many sensor networks. This letter designs a new algorithm that expands the theoretical guarantees of the distributed and quantized OMKL in [1] to an arbitrary general non-fully connected graph. Unlike [1], our method uses a novel hidden state quantization scheme in conjunction with a gossip algorithm. One major advantage, compared with [1], is that our algorithm does not need to communicate the loss function. Another example of a distributed OMKL that works for a non-fully connected graph is presented in [2]. It requires communicating an unlimited number of bits between neighbors, and its assumptions are stricter than those of [1]. To manage the required communication throughput, which is often a performance bottleneck [3, 4], this letter provides the properties of [2] under looser assumptions and while communicating only a limited number of bits between neighboring nodes.

In [5], a distributed stochastic gradient descent scheme with quantized communication is discussed. The proposed algorithm uses an extra shared “hidden” state and can be used for the single-kernel case, but not multi-kernel settings. In addition to extending [1] to general non-fully connected networks, our work can be considered as the extension of [5] to multi-kernel cases.

There are a variety of learning tasks that OMKL is suited for, such as multi-kernel classification, regression, and clustering [6, 7, 8]. For a more in-depth review of the literature, see [1].

Let us consider a network with $J$ nodes and model it as an undirected connected graph, where two nodes are connected if and only if they can communicate. Our set of nodes $V$, and the set of edges $E$, define a communication graph $G=(V,E)$. At each instant of time $t$, Node $j$ receives the data string $\bm{x}^{j}_{t}\in\mathbb{R}^{d}$ and the desired response $y^{j}_{t}\in\mathbb{R}$. Our task is to find an approximating function $f(\bm{x}^{j}_{t})$ for $y^{j}_{t}$. As in [1], $f$ belongs to a Reproducing Kernel Hilbert Space (RKHS) $\mathcal{H}=\left\{f\mid f(\bm{x})=\sum_{t=1}^{\infty}\sum_{j=1}^{J}\alpha^{j}_{t}\kappa(\bm{x},\bm{x}^{j}_{t})\right\}$, where $\kappa(\bm{x},\bm{x}^{j}_{t}):\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$ is a kernel function that measures the similarity between $x$ and $\bm{x}^{j}_{t}$. Let us consider the following optimization problem

where $\mathcal{C}$ is a cost function and $\lambda>0$ is a regularization parameter that controls an increasing function $\Omega$. An optimal solution for this problem exists in the form $\hat{f}(\bm{x})=\sum_{t=1}^{T}\sum_{j=1}^{J}\alpha_{t}^{j}\kappa(\bm{x},\bm{x}_{t}^{j})$, where $\alpha_{t}^{j}$ are real numbers [9].

In multi-kernel learning, a weighted combination of several kernels is selected to improve the performance, compared to single-kernel learning. A convex combination of the kernels $\left\{\kappa_{p}\right\}_{p=1}^{P}$, where $\kappa_{p}\in\mathcal{H}_{p}$ is an RKHS, is also an RKHS, denoted by $\bar{\mathcal{H}}=\mathcal{H}_{1}\oplus\cdots\oplus\mathcal{H}_{P}$ [9]. Here, $\oplus$ indicates the direct sum of Hilbert spaces. Using $\bar{\mathcal{H}}$ instead of $\mathcal{H}$, we turn problem (1) into:

To evade the curse of dimensionality, a Random Feature (RF) approximation is used [1, 10]. For normalized shift-invariant kernels, i.e., $\kappa(\bm{x},\bm{x}^{\prime})=\kappa(\bm{x}-\bm{x}^{\prime})$, their Fourier transforms $\pi_{\kappa}(v)$ exist, and due to normalization, $\pi_{\kappa}(0)=1$. Also, viewing $\pi_{\kappa}$ as a pdf, $\kappa(\bm{x}-\bm{x}^{\prime})=\int\pi_{\kappa}(v)e^{jv^{\top}(\bm{x}-\bm{x}^{\prime})}\,dv=\mathbb{E}_{v}[e^{jv^{\top}(\bm{x}-\bm{x}^{\prime})}]$. Gaussian, Laplacian, and Cauchy kernels are three examples of normalized shift-invariant kernels that we can use [11]. However, any family of shift invariant kernels can be used for the RF approximation we describe next. Drawing $D$ i.i.d. samples $\{\bm{v_{i}}\}_{i=1}^{D}$ from $\pi_{\kappa}(v)$, we define

which has the property that $\kappa(\bm{x},\bm{x^{\prime}})=\mathbb{E}_{v}[z_{V}(\bm{x^{\prime}})^{\top}z_{V}(\bm{x})]$. So, given a fixed $\{\bm{v_{i}}\}_{i=1}^{D}$, we can approximate $\kappa(\bm{x},\bm{x^{\prime}})\approx z_{V}(\bm{x^{\prime}})^{\top}z_{V}(\bm{x})$. This is called the RF approximation, and it is an unbiased and consistent estimation of $\kappa(\bm{x},\bm{x^{\prime}})$ [10]. Thus, a weight vector $\bm{\theta}\in\mathbb{R}^{2D}$ can be constructed such that

Then, the loss function is defined as

and the following equations are obtained for Kernel $p$ and Node $j$:

where $\eta\in(0,1)$ is a learning rate. The weights are normalized as $\bar{w}_{p,t}^{j}=w_{p,t}^{j}/\sum_{p=1}^{P}w_{p,t}^{j}$ to have

The above equations represent how local online multi-kernel learning models can be built [1, 10]. In contrast to previous research, each node $j$ in our scenario can only communicate with its neighboring nodes in the set $\mathcal{S}_{j}\subseteq V$. Thus, the local model $\bm{\theta}^{j}_{p,t}$ of each node may be different from node to node. Therefore, our algorithm must ensure that all nodes converge to the same model. For this purpose, the local models are propagated using a gossip algorithm. The nodes calculate the weighted average of the information provided by their neighbors at each communication round and use it to update their local information. The weight Node $j$ assigns to the information coming from Node $i$ is defined as $w_{ij}^{\prime}$. Notice that the sum of weights $\sum_{i\in\mathcal{S}_{j}}w_{ij}^{\prime}=1$ for all $j$ since the weights of a weighted average must add up to one. We impose $w_{ij}^{\prime}=w_{ji}^{\prime}$ such that we can associate the weights to the edges of the undirected communication graph $G$. Thus, the weights define the gossip matrix $\bm{W}^{\prime}$, which is $J\times J$ and doubly stochastic  [12, 13, 14]. The spectral gap of $\bm{W}^{\prime}$ is denoted by $\rho=1-\lambda_{2}(\bm{W}^{\prime})\in(0,1]$, where $\lambda_{2}(\bm{W}^{\prime})$ represents the second eigenvalue of $\bm{W}^{\prime}$ in descending order.

Such a gossip algorithm works very well when the nodes communicate their states perfectly with their neighbors. However, practically, only a few bits can be communicated, i.e., information needs to be quantized before being shared with the neighbors. We use a random quantizer $Q:\mathbb{R}^{n}\to\mathbb{R}^{n}$, to represent an arbitrary vector $\bm{x}\in\mathbb{R}^{n}$ with $Q(\bm{x})$ in an efficient way. Our results work for any random quantizer that satisfies

for some $\delta>0$, which we will call the compression parameter. Here, $\mathbb{E}_{Q}$ denotes the expected value with respect to the internal randomness of $Q(\cdot)$. In simulations, we use the randomized quantizer of [15]. Each element of a non-zero vector $\bm{v}\in\mathbb{R}^{n}$, i.e., $v_{i}$, is quantized by

where $M=2^{b}-1$ is the number of quantization levels and defining $l=\lfloor M\tfrac{v_{i}}{\lVert v\rVert}\rfloor$,

is represented by $b$ bits. Following [15, Lemma 3.1], Eq. (10) holds for $\delta=1-\min\left(\tfrac{2D}{M^{2}},\tfrac{\sqrt{2D}}{M}\right)>0$.

We present Algorithm 1 for gossiped and quantized OMKL. For ease of notation, we will denote $\mathcal{L}({\bm{\theta}^{j}_{p,t}}^{\top}z_{V_{p}}(\bm{x}_{t}^{j}),y_{t})$ as $\mathcal{L}(\bm{\theta}^{j}_{p,t})$ from now on. In Algorithm 1, at each time instance, nodes collect their local data and transform them according to the RF approximation. Then, the kernel losses are computed and used to update the kernel weights. For the gossip step, we define a hidden state $\bm{h}_{p,t}^{j}\in\mathbb{R}^{2D}$ for each node $j$ that is known for all neighbors in $\mathcal{S}_{j}$ because it is updated by the same quantized values known to all neighbors. The new local state, $\bm{\theta}_{p,t}^{j}$, will be a sum of $\bm{\theta}_{p,t-1}^{\prime j}$, which is an auxiliary variable where we store the local learning, plus a gossip step of size $\gamma$ with the information from the hidden states. Subsequently, each node $j$ prepares the update to the hidden state by quantizing the difference between its local state $\bm{\theta}_{p,t}^{j}$ and the common hidden state $\bm{h}_{p,t}^{j}$. This quantized difference is sent to the neighbors and is used by them to collectively update the hidden state. Finally, each node performs local learning with a step size $\eta$, and stores it in the auxiliary variable $\bm{\theta}_{p,t}^{\prime j}$.

The role of a hidden state and quantized update is to have an accurate representation of the neighbor’s states without the need for broadcasting the full state at each time instance.

In what follows, we provide regret analysis to study the performance of our algorithm. First, we make the following assumptions similar to what is done in the literature.

To prove Thm. 1, we first need to present Lemma 1, which bounds the difference between a single kernel loss and the optimal loss, and Lemma 2, which bounds the error added by the kernel weights.

The proof of Lemma 2 follows the same steps as in [1, Lemma 3].

From the convexity of $\mathcal{L}(\cdot)$,

and Thm. 1 follows immediately using Lemma 1 and Lemma 2.

To validate Thm. 1, we have tested Algorithm 1 with real datasets for binary classification, with different topologies, and using different values of quantization level. We have used the well-known Kernel Logistic Regression (KLR) loss function [9], i.e., the loss function (5) is defined as

where we have used $\Omega(\lVert\bm{\theta}\rVert^{2})=\lVert\bm{\theta}\rVert^{2}$. We have conducted our experiments with three datasets: Banana, Credit-Card, and MNIST. The synthetic data from the Banana dataset [17] ($n=5300,d=2$) are two non-linearly separable clusters. The Credit-Card dataset [18] ($n=30000,d=2$) contains data from credit card users, such as their credit history and whether they have defaulted or not. It is obtained from the UCI machine learning repository [19]. The MNIST dataset [20] ($n=70000,d=784$) is a labeled set of handwritten digits from 0 to 9. We divide them into two classes, those that are number 8 and those that are not.

Our experimental setup has $J=20$ nodes, dimension $D=20$ for our RF approximation, regularization parameter $\lambda=0.001$, and three Gaussian kernels with $\sigma\in\{1,3,5\}$, where a Gaussian kernel with parameter $\sigma$ is defined as $\kappa(\bm{x},\bm{x^{\prime}})=\exp{[-\lVert\bm{x}-\bm{x^{\prime}}\rVert^{2}/(2\sigma^{2})]}$. Simulations have been performed 100 times with different sets of Random Features and the corresponding mean of the loss function is plotted. We report the loss instead of the classification accuracy because the difference in the latter is minimal. We have used the quantizer described in (12) with 7 levels of quantization, that is, 3 bits per element in any transmitted array. Our learning rates are $\eta=0.01$ and $\gamma=0.9\eta=0.009$.

Fig. 1 compares the performance of our algorithm versus two benchmarks. Since Algorithm 1 can be viewed as an extension of [1] to non-complete graphs, the first benchmark for comparison is the OMKL algorithm from [1]. There is a small difference between the performance of OMKL and that of our gossiped OMKL although OMKL requires many more inter-node communications. This is despite the fact that OMKL is run over a complete topology, but the gossiped OMKL is executed over the worst-case scenario, i.e., a path topology that includes much smaller number of connections and as a result requires much less communication.

Gossiped OMKL can also be considered as an extension of [5] to multi-kernel learning, which justifies using the single-kernel SGD from [5] as our second benchmark. Gossiped OMKL using three kernels clearly outperforms the single-kernel approach, named Koloskova in Fig. 1.

Although not shown in the figure, we have observed that, for values of $\eta$ and $\gamma$ chosen in Fig. 1, or smaller values, the choice of topology does not affect the performance of our algorithm. To observe the effect of topology on algorithm performance, larger step sizes ($\eta=0.1$ and $\gamma=0.09$) are chosen in Fig. 2. The figure shows simulations using the Credit-Card dataset and without quantization on three different topologies: the complete graph, the ring, and the path. We can observe that more densely connected communication graphs lead to better performance. We have also tested the algorithm for $M\geq 7$ levels of quantization, that satisfies the condition $\delta>0$ in (12), and all of them perform as well as the non-quantized version, with the loss function differences in the order of $10^{-6}$.

The results show that our gossiped OMKL algorithm can successfully extend the OMKL algorithm [1] to non-complete graphs and the distributed learning algorithm in [5] to multi-kernel learning.