# Multiple Kernel-Based Online Federated Learning

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

Online federated learning (OFL) becomes an emerging learning framework, in
which edge nodes perform online learning with continuous streaming local data
and a server constructs a global model from the aggregated local models.
Online multiple kernel learning (OMKL), using a preselected set of $P$
kernels, can be a good candidate for OFL framework as it has provided an
outstanding performance with a low-complexity and scalability. Yet, an naive
extension of OMKL into OFL framework suffers from a heavy communication
overhead that grows linearly with $P$. In this paper, we propose a novel
multiple kernel-based OFL (MK-OFL) as a non-trivial extension of OMKL, which
yields the same performance of the naive extension with $1/P$ communication
overhead reduction. We theoretically prove that MK-OFL achieves the optimal
sublinear regret bound when compared with the best function in hindsight.
Finally, we provide the numerical tests of our approach on real-world
datasets, which suggests practicality.

##  I Introduction

Federated learning is an emerging distributed learning framework, in which
distributed nodes (e.g., mobile phones, wearable devices, etc.) train a model
collaboratively under the coordination of a central server without
centralizing the training data [6, 9]. To be specific, federated learning
optimizes a global model by repeating the two operations: i) local model
optimizations at edge nodes; ii) global model update (e.g., model averaging)
at the server [24]. This approach has received tremendous attention due to the
myriad of applications: activities of mobile phone users, predicting a low
blood sugar, heart attack risk from wearable devices, or detecting burglaries
within smart homes [1, 14, 16].

In many real-world applications, machine learning tasks are expected to be
operated in an online fashion. For example, online learning is required when
data is generated as a function of time (i.e., time-series predictions) [17,
20] and when the large number of data makes it impossible to carry out data
analytic in batch form [11]. This challenging problem has been successfully
addressed via online multiple kernel learning (OMKL) [19, 21, 8]. OMKL learns
a sequence of functions (or models) which predicts the label of a newly
incoming data. In particular, it seeks the optimal combination of a pool of
$P$ single kernel functions in an online fashion. With the use of multiple
kernels, OMKL can provide a superior accuracy and enjoy a great flexibility
compared with single-kernel online learning [21, 8]. In spite of these merits,
OMKL is restricted to a centralized online learning and an extension to a
federated learning is still open problem.

In this paper, we consider an online federated learning (OFL) problem. The
objective of OFL is to learn a sequence of global models using continuous
streaming data across a large number of distributed nodes. At every time,
specifically, OFL optimizes a global model by repeating two operations: i)
edge nodes updates local models using their own incoming data; ii) the server
constructs an improved global model by averaging the them. The construction of
a single kernel-based OFL (named SK-OFL) is rather straightforward, where the
parameter of a kernel function (defined by a $2D$-dimensional vector) is
simply exchanged between every node and the server. As in the centralized
counterpart [21, 8], the use of multiple kernels (i.e., a preselected set of
$P$ kernels) is necessary to enhance a learning accuracy. However, a naive
extension of SK-OFL into a multiple kernel setting suffers from a heavy
communication overhead that increases linearly with $P$. This is because the
parameters of all $P$ kernels should be exchanged. In this paper, we propose a
novel multiple-kernel OFL (named MK-OFL) which can achieve the same
performance of the naive extension and outperforms SK-OFL considerably with
the same communication overhead with SK-OFL. To this end, our major
contributions are summarized as follows.

  * •

In the proposed MK-OFL, every node selects one kernel index out of $P$ kernels
randomly according to its own probability mass function (PMF). Then, it sends
one local model corresponding to the selected index, thus having the same
communication overhead with SK-OFL. With high probability, this randomized
algorithm chooses the best kernel only after a certain convergence time, thus
being able to yield an attractive performance.

  * •

Leveraging the martingale argument, we theoretically prove that MK-OFL
achieves the optimal sublinear regret bound ${\cal O}(\sqrt{T})$ when compared
wit the best kernel function in hindsight. This implies that MK-OFL achieves
the same accuracy of the centralized OMKL asymptotically by preserving an
edge-node privacy.

  * •

Via numerical tests on real-world datasets, we demonstrate the effectiveness
of the proposed MK-OFL in various online learning tasks such as online
regressions and time-series predictions. Remarkably, it is shown that MK-OFL
significantly outperforms SK-OFL and almost achieves the performance of the
best kernel function in hindsight.

##  II Preliminaries

We briefly review the kernel-based online learning framework (named OMKL) in
[8], and describe the problem setting of an online federated learning (OFL).
To simplify the notation, we let $[N]=\\{1,2,...,N\\}$ for some positive
integer $N$. Also, $t$, $k$, $p$ represent the indices of time, node, and
kernel, respectively.

###  II-A Overview of a kernel-based online learning

The main objective of an online learning is to learn a sequence of functions
$\\{\hat{f}_{t}:t\in[T]\\}$ such that the cumulative regret is minimized:

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

where ${\cal L}(\cdot,\cdot)$ and $f^{\star}(\cdot)$ denote a cost function
and the best function in hindsight, respectively. Specifically, at every time
$t-1$, $\hat{f}_{t}(\cdot)$ is estimated from the received data $\\{({\bf
x}_{\tau},y_{\tau}):\tau\in[t-1]\\}$. The above challenging problem has been
efficiently solved via a kernel-based online learning [21, 8]. In this
approach, a function space for an optimization is restricted to a reproducing
Hilbert kernel space (RKHS) ${\cal H}_{p}$, defined as ${\cal
H}_{p}\stackrel{{\scriptstyle\Delta}}{{=}}\left\\{f:f({\bf
x})=\sum_{t}\alpha_{t}\kappa_{p}({\bf x},{\bf x}_{t})\right\\}$, where
$\kappa_{p}({\bf x},{\bf x}_{t}):{\cal X}\times{\cal X}\rightarrow{\cal Y}$ is
a symmetric positive semidefinite basis function (called kernel) [23].
Moreover, the representer theorem [22] and random-feature approximation [15]
shows that each kernel function in an optimal solution of (1) can be well-
approximated with a model parameter $\hat{{\bf w}}_{t}^{p}$, i.e.,

$\hat{f}_{t}({\bf x})=\left(\hat{{\bf w}}_{t}^{p}\right)^{{\sf T}}{\bf
z}_{p}({\bf x}),$ (2)

where ${\bf z}_{p}({\bf x})$ denotes a non-linear function defined by a kernel
$\kappa_{p}$, i.e.,

$\displaystyle{\bf z}_{p}({\bf x})=$ (3)
$\displaystyle\frac{1}{\sqrt{D}}[\sin{\bf v}_{1}^{{\sf T}}{\bf
x},\dots,\sin{\bf v}_{D}^{{\sf T}}{\bf x},\cos{\bf v}_{1}^{{\sf T}}{\bf
x},\dots,\cos{\bf v}_{D}^{{\sf T}}{\bf x}]^{{\sf T}},$

and where $\\{{\bf v}_{i}:i\in[D]\\}$ denotes an independent and identically
distributed (i.i.d.) samples from the Fourier transform of a given kernel
function $\kappa_{p}(\cdot,\cdot)$. Note that the hyper-parameter $D$ can be
chosen independently from the size of data $T$. The accuracy of the above
kernel-based online learning fully relies on a preselected kernel
$\kappa_{p}$, which is chosen manually either by a task-specific priori
knowledge or by some intensive cross-validation process. Online multiple
kernel learning (OMKL), using a predetermined set of $P$ kernels (called a
kernel dictionary), is more powerful [21, 8]. Namely, OMKL seeks a sequence of
best kernel functions, each of which has the following form:

$\displaystyle\hat{f}_{t}({\bf
x})=\sum_{p=1}^{P}\hat{q}_{t}^{p}\left(\hat{{\bf w}}_{t}^{p}\right)^{{\sf
T}}{\bf z}_{p}({\bf x})\in\bar{{\cal H}},$ (4)

where $\bar{{\cal H}}\stackrel{{\scriptstyle\Delta}}{{=}}{\cal H}_{1}+{\cal
H}_{2}+\cdots+{\cal H}_{P}$ is again RKHS [23] and $\hat{q}_{t}^{p}\in[0,1]$
denotes the combination weight (or reliability) of the associated kernel
function $\hat{f}_{t}^{p}({\bf x})=\left(\hat{{\bf w}}_{t}^{p}\right)^{{\sf
T}}{\bf z}_{p}({\bf x})$. We remark that the optimization of OMKL can be
solved using the powerful tool boxes from online convex optimization and
online learning techniques developed over vector spaces.

Figure 1: Description of the proposed online federated learning with multiple
kernels at time $t$, in which $\hat{{\bf w}}_{k,t+1}$ and $\hat{{\bf
w}}_{t+1}$ denote the local model of the node $k$ and the global model,
respectively. The estimated label $\hat{y}_{k,t}$ at each node $k$ is
determined as $\hat{y}_{k,t}=\hat{{\bf w}}_{t}^{{\sf T}}{\bf
z}_{\hat{p}_{t}}({\bf x}_{k,t})$.

###  II-B Problem Formulation

We define the problem setting of an online federated learning (OFL). The
objective of OFL is to learn a sequence of functions (i.e., global models)
from sequentially incoming data across a large number of distributed nodes. In
detail, at each time $t$, the server distributes the current global model
$\hat{{\bf w}}_{t}\in\mbox{\bb R}^{r}$ (the parameter of a learned function)
to the distributed $K$ nodes, where $r$ denotes a communication overhead.
Every nodes $k$ updates the local model independently from the current global
model and incoming data $({\bf x}_{k,t},y_{k,t})$, where ${\bf
x}_{k,t}\in{\cal X}\subseteq\mbox{\bb R}^{d}$ and $y_{k,t}\in{\cal
Y}\subseteq\mbox{\bb R}$ represent the feature and the label, respectively.
Hereinafter, the corresponding local model are denoted as $\hat{{\bf
w}}_{k,t+1}$ for $k\in[K]$. Then, the $K$ nodes send it back to the server,
from which the server constructs an improved global model as

$\hat{{\bf w}}_{t+1}=h\left(\hat{{\bf w}}_{1,t+1},...,\hat{{\bf
w}}_{K,t+1}\right),$ (5)

for some function $h:\mbox{\bb R}^{r}\times\cdots\times\mbox{\bb
R}^{r}\rightarrow\mbox{\bb R}^{r}$. In this paper, it is assumed that $h$ is
the popular averaging function (FedAvg) [12], i.e., $\hat{{\bf
w}}_{t+1}=\frac{1}{K}\sum_{k=1}^{K}\hat{{\bf w}}_{k,t+1}$. These two-step
procedures will be repeated.

##  III Methods

We first present a single kernel-based OFL (SK-OFL) and then extend it into a
multiple kernel setting. The resulting method is named MK-OFL. To meet the
communication overhead, in both methods, the messages exchanged between a
server and edge nodes are constructed as $r$-dimensional real-valued vectors
(see Fig. 1). The detailed algorithms of SK-OFL and MK-OFL are described in
Section III-A and Section III-B, respectively.

###  III-A The Proposed SK-OFL

The objective of SK-OFL is to seek a sequence of functions $\hat{f}_{1}({\bf
x}),...,\hat{f}_{T}({\bf x})$ under the OFL framework in Section II-B.
Following the structure of a kernel-based online learning [8], each function
is fully defined with a single parameter $\hat{{\bf w}}_{t}\in\mbox{\bb
R}^{2D}$, i.e.,

$\hat{f}_{t}({\bf x})=\hat{{\bf w}}_{t}^{{\sf T}}{\bf z}_{p}({\bf x}),$ (6)

where ${\bf z}_{p}({\bf x})$ is defined in (3) and a preselected kernel
$\kappa_{p}$ is assumed. In SK-OFL, $\hat{{\bf w}}_{t}$ is considered as a
global model and by setting $D=\lfloor r/2\rfloor$, the communication overhead
is met. At every time $t$, SK-OFL performs a distributed model training
iteratively with the two steps: i) local model update at the edge nodes; ii)
global model update at the server. Focusing on time $t$, we provide the
specific procedures of these steps below.

(i) Local model update: Given the current global model $\hat{{\bf w}}_{t}$ and
an incoming data $({\bf x}_{k,t},y_{k,t})$, each node $k$ updates its local
model $\hat{{\bf w}}_{k,t+1}$ via online gradient descent (OGD) [7]:

$\hat{{\bf w}}_{k,t+1}=\hat{{\bf w}}_{t}-\eta_{\ell}\nabla{\cal
L}\left(\hat{{\bf w}}_{t}^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t}\right),$
(7)

with step size $\eta_{l}>0$, where $\nabla{\cal L}\left(\hat{{\bf
w}}_{t}^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t}\right)$ stands for the
gradient at the point $\hat{{\bf w}}_{t}$. Then, it sends the updated local
model $\hat{{\bf w}}_{k,t+1}$ to the server.

(ii) Global model update: Given the received local models $\\{\hat{{\bf
w}}_{k,t+1}:k\in[K]\\}$, the server updates the global model by averaging
them:

$\hat{{\bf w}}_{t+1}=\frac{1}{K}\sum_{k=1}^{K}\hat{{\bf w}}_{k,t+1}.$ (8)

Then, it distributes the updated global model $\hat{{\bf w}}_{t+1}\in\mbox{\bb
R}^{r}$ to the $K$ nodes.

###### Remark 1

The proposed SK-OFL can be immediately extended into a multiple kernel
setting, in which every node transmits the $P$ local models and the
corresponding weights as in (4) to the server, and vice versa. This naive
extension suffers from an expensive communication overhead as it linearly
increases with the size of a kernel dictionary $P$ (i.e., equals to $P\times
r$). In the following section, we will present a novel MK-OFL as a non-trivial
extension of SK-OFL into a multiple kernel setting. It is noticeable that MK-
OFL can achieve the performance of the naive extension and significantly
improve the performance of SK-OFL while having the communication overhead $r$
irrespective of $P$.

###  III-B The Proposed MK-OFL

In the proposed MK-OFL, the central server broadcasts the global information
$(\hat{p}_{t+1},\hat{{\bf w}}_{t})\in[P]\times\mbox{\bb R}^{2D}$ at time $t$
over $t=1,...,T$, where the initial values are assigned as $\hat{{\bf
w}}_{1}={\bf 0}$ and $\hat{p}_{2}=1$. Regarding the communication overhead,
compared with SK-OFL a kernel index is additionally transmitted. Taking this
into account, $(\hat{p}_{t+1},\hat{{\bf w}}_{t})$ is considered as a global
model and by setting $D=\lfloor r/2\rfloor-1$, the communication overhead is
satisfied. Then, a common learned (or estimated) function at the current time
$t$ is fully determined by the parameters $\hat{p}_{t}$ (obtained at time
$t-1$) and $\hat{{\bf w}}_{t}$, i.e.,

$\hat{f}_{t}({\bf x})=\hat{{\bf w}}_{t}^{{\sf T}}{\bf z}_{\hat{p}_{t}}({\bf
x}).$ (9)

The key idea of MK-OFL is following: it is allowed to choose a different
kernel at every time, while as $t$ grows, a selected kernel can converge to
the best kernel in hindsight. Furthermore, we verified that the convergence
speed is quite fast. In contrast, SK-OFL should choose one kernel before
receiving data and thus, the predetermined kernel is unlikely to be the best
one. For these reasons, MK-OFL can significantly outperform SK-OFL without
sacrificing the communication overhead and by enjoying the use of multiple
kernels. Focusing on time $t$, we provide the detailed algorithm of MK-OFL
below (see Fig. 1).

(i) Local model update: At time $t$, each node $k$ has its own local
information as $\\{\tilde{{\bf w}}_{k,t}^{p}:p\in[P]\\}$ and receives the
global model $(\hat{p}_{t+1},\hat{{\bf w}}_{t})$ from the server. Using the
$\hat{p}_{t}$ (observed at time $t-1$) and $\hat{{\bf w}}_{t}$, it first
updates the parameters of the $P$ local kernel functions:

$\hat{{\bf w}}_{k,t}^{p}=\begin{cases}\tilde{{\bf w}}_{k,t}^{p},\mbox{ if
}p=\hat{p}_{t}\\\ \hat{{\bf w}}_{t},\mbox{ if }p\neq\hat{p}_{t},\end{cases}$
(10)

for $\forall p\in[P]$. Then, every node $k$ updates the local information via
OGD:

$\tilde{{\bf w}}_{k,t+1}^{p}=\hat{{\bf w}}_{k,t}^{p}-\eta_{\ell}\nabla{\cal
L}\left((\hat{{\bf w}}_{k,t}^{p})^{{\sf T}}{\bf z}_{p}({\bf
x}_{k,t}),y_{k,t}\right),$ (11)

for $\forall p\in[P]$, where $\eta_{\ell}>0$ is the step size. Given the
received parameter $\hat{p}_{t+1}$, set

$\hat{{\bf w}}_{k,t+1}=\tilde{{\bf w}}_{k,t+1}^{\hat{p}_{t+1}},$ (12)

which will be transmitted to the server as the updated local model.

We next explain how each node $k$ selects the candidate of the best kernel at
time $t+2$ (denoted by $\hat{p}_{k,t+2}$). The weights for combining the $P$
kernel functions are determined on the basis of the past local losses, i.e.,

$\hat{{\bf q}}_{k,t+2}(p)=\frac{\hat{{\bf
m}}_{k,t+2}(p)}{\sum_{p=1}^{P}\hat{{\bf m}}_{k,t+2}(p)},\;\;\forall p\in[P],$
(13)

where the initial values $\hat{{\bf m}}_{k,2}(p)=1,\forall p\in[P]$ and for a
learning rate $\eta_{g}>0$,

$\displaystyle\hat{{\bf m}}_{k,t+2}(p)=\hat{{\bf m}}_{k,t+1}(p)$
$\displaystyle\;\;\;\;\;\times\exp\left(-\eta_{g}K{\cal L}\left((\hat{{\bf
w}}_{k,t}^{p})^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t}\right)\right).$
(14)

In the context of online learning, the above weight update is known as
exponential strategy (or Hedge algorithm) [2]. From (13), the following
probability mass function (PMF) is defined

$\hat{{\bf q}}_{k,t+2}=(\hat{{\bf q}}_{k,t+2}(1),...,\hat{{\bf
q}}_{k,t+2}(P)).$ (15)

Then, it selects one kernel index $\hat{p}_{k,t+2}\in[P]$ according to the PMF
$\hat{{\bf q}}_{k,t+2}$ and transmits the updated local model
$(\hat{p}_{k,t+2},\hat{{\bf w}}_{k,t+1}=\tilde{{\bf
w}}_{k,t+1}^{\hat{p}_{t}})$ to the server.

(ii) Global model update: The server receives the updated local models
$\\{(\hat{p}_{k,t+2},\hat{{\bf w}}_{k,t+1}):k\in[K]\\}$ from the $K$ nodes.
First, the global parameter is updated by averaging the local parameters such
as

$\hat{{\bf w}}_{t+1}=\frac{1}{K}\sum_{k=1}^{K}\hat{{\bf w}}_{k,t+1}.$ (16)

Also, each kernel $k$ chooses one kernel index $\hat{p}_{t+2}$ from
$\\{\hat{p}_{k,t+2}:k\in[K]\\}$ randomly according to the PMF
$\hat{\hbox{\boldmath$\alpha$}}_{t+2}=(\hat{\alpha}_{1,t+2},...,\hat{\alpha}_{K,t+2})$,
where

$\displaystyle\alpha_{k,t+2}$
$\displaystyle=\frac{|\\{k\in[K]:\hat{p}_{k,t+1}=p\\}|^{K-1}}{\sum_{p=1}^{P}{|\\{k\in[K]:\hat{p}_{k,t+1}=p\\}|^{K}}}.$
(17)

Naturally, this PMF construction aims at assigning a higher probability to a
more frequent index from $\\{\hat{p}_{k,t+2}:k\in[K]\\}$. The resulting index
$\hat{p}_{t+2}$ represents the kernel index to be globally updated at the next
time slot $t+2$. The server distributes the updated global model
$(\hat{p}_{t+2},\hat{{\bf w}}_{t+1})$ to the $K$ nodes.

##  IV Regret Analysis

We analyze the cumulative regret of the proposed MK-OFL. As usually considered
for the analysis of online convex optimizations and online learning frameworks
[2, 7, 21, 8], the following conditions are also assumed.

Assumption 1. For any fixed ${\bf z}_{p}({\bf x}_{t})$ and $y_{t}$, the loss
function ${\cal L}({\bf w}^{{\sf T}}{\bf z}_{p}({\bf x}_{t}),y_{t})$ is convex
with respect to ${\bf w}$, and is bounded as ${\cal L}({\bf w}^{{\sf T}}{\bf
z}_{p}({\bf x}_{t}),y_{t})\in[0,1]$.

Assumption 2. For any kernel $\kappa_{p}$, ${\bf w}_{k,t}^{p}$ belongs to a
bounded set ${\cal B}$, i.e., $\|{\bf w}_{k,t}^{p}\|\leq C$ for any $t\in[T]$.

Assumption 3. The loss function is $L$-Lipschitz continuous, i.e.,
$\|\nabla{\cal L}({\bf w}^{{\sf T}}{\bf z}_{p}({\bf x}_{t}),y_{t})\|\leq L$.

Let $f_{p}^{\star}({\bf x})=({\bf w}_{p}^{\star})^{{\sf T}}{\bf z}_{p}({\bf
x})$ denote the best function in the kernel $\kappa_{p}$ with respect to the
distributed data $\\{({\bf x}_{k,t},y_{k,t}):k\in[K],t\in[T]\\}$:

${\bf w}_{p}^{\star}\stackrel{{\scriptstyle\Delta}}{{=}}{\hbox{arg}}\min_{{\bf
w}\in{\cal B}}\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal L}\left({\bf w}^{{\sf T}}{\bf
z}_{p}({\bf x}_{k,t}),y_{k,t}\right).$ (18)

Before stating our main results, we will give some intuitions behind the
proposed MK-OFL. It is a randomized algorithm due to the randomness of the
best kernel selection at every time $t$ (denoted by $\hat{p}_{t}$ in our
algorithm). By integrating randomness at the distributed edges and the server,
it can be understood that $\hat{p}_{t}$ is chosen from $[P]$ randomly
according to the following PMF:

$\hat{{\bf q}}_{t}=\sum_{k=1}^{K}\alpha_{k,t}\hat{{\bf q}}_{k,t},$ (19)

where $\alpha_{k,t}$, defined in (17), can capture the reliabilities of the
$K$ nodes at the current time $t$. To evaluate the accuracy of $\hat{{\bf
q}}_{t}$, we introduce the corresponding network-wise (or centralized) PMF
$\bar{{\bf q}}_{t}$, which is determined on the basis of the entire losses of
the $K$ nodes:

$\bar{{\bf q}}_{t}(p)=\frac{\bar{{\bf m}}_{t}(p)}{\sum_{p=1}^{P}\bar{{\bf
m}}_{t}(p)},\;\;\forall p\in[P],$ (20)

with the initial values $\bar{{\bf m}}_{1}(p)=1,\forall p\in[P]$, where

$\bar{{\bf m}}_{t}(p)=\bar{{\bf m}}_{t-1}(p)\times L_{t-1}^{p},$ (21)

and for some parameter $\eta_{g}>0$

$L_{t-1}^{p}=\prod_{k=1}^{K}\exp\left(-\eta_{g}{\cal L}\left((\hat{{\bf
w}}_{k,t-1}^{p})^{{\sf T}}{\bf z}_{p}({\bf
x}_{k,t-1}),y_{k,t-1}\right)\right).$

In general, the data available locally fail to estimate the overall
distribution $\bar{{\bf q}}_{t}$. Obviously MK-OFL can approach the
performance of the centralized OMKL [8] (i.e., the performance limit),
provided that our PMF $\hat{{\bf q}}_{t}$, which is constructed in a
decentralized way, is sufficiently close to $\bar{{\bf q}}_{t}$. In fact, an
exact gap between them relies on the characteristics (e.g., heterogeneity) of
real datasets. Nevertheless, in our theoretical analysis, it is proved that
regardless of datasets, the above gap only leads to a bounded performance
loss, which is less than ${\cal O}(\sqrt{T})$. Namely, the loss is small
enough to guarantee the optimal sublinear regret ${\cal O}(\sqrt{T})$ of the
proposed MK-OFL. Beyond the asymptotic analysis, our experiments in Fig. 2
demonstrate that the impact of the above gap is negligible.

###  IV-A Main results

Note that in the proposed MK-OFL, the server broadcasts the current estimate
$\hat{wv}_{t}$ at time $t$ to the $K$ nodes and each node $k$ estimates the
label of a newly incoming data ${\bf x}_{k,t}$ as $\hat{y}_{k,t}=\hat{{\bf
w}}_{t}^{{\sf T}}{\bf z}_{\hat{p}_{t}}({\bf x}_{k,t})$. Also, ${\bf
w}_{p}^{\star}$ denotes the optimal parameter defined in (18). Under the
Assumption 1 - Assumption 3, we state the main result of this section:

###### Theorem 1

The proposed MK-OFL with $\eta_{\ell}=\eta_{g}={\cal O}(1/\sqrt{T})$
guarantees the sublinear regret ${\cal O}(\sqrt{T})$ with high probability:

$\displaystyle{\cal R}_{T}$ $\displaystyle=\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal
L}\left(\hat{{\bf w}}_{t}^{{\sf T}}{\bf z}_{\hat{p}_{t}}({\bf
x}_{k,t}),y_{k,t}\right)$ $\displaystyle-\min_{1\leq p\leq
P}\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal L}\Big{(}({\bf w}_{p}^{\star})^{{\sf
T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t}\Big{)}\leq{\cal O}(\sqrt{T}).$

From the fact that SK-OFL is a deterministic algorithm with a preselected
kernel $\kappa_{p}$, we can immediately get:

###### Corollary 1

For a predetermined kernel $\kappa_{p}$, SK-OFL with
$\eta_{\ell}=\eta_{g}={\cal O}(1/\sqrt{T})$ guarantees the sublinear regret as

$\displaystyle{\cal R}_{T}$ $\displaystyle=\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal
L}\left(\hat{{\bf w}}_{t}^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t}\right)$
$\displaystyle\;\;\;\;\;\;-\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal L}\Big{(}({\bf
w}_{p}^{\star})^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t}\Big{)}\leq{\cal
O}(\sqrt{T}).$

Theorem 1 and Corollary 1 reveal that MK-OFL and SK-OFL can achieve the
optimal sublinear regret bounds when compared with the respective best
functions in hindsight. However, it is noticeable that the best functions as
to MK-OFL and SK-OFL are from $\bar{{\cal H}}={\cal H}_{1}+\cdots+{\cal
H}_{P}$ and ${\cal H}_{p}\subset\bar{{\cal H}}$ for a preselected $p\in[P]$,
respectively. Consequently, the former tends to be much better than the
latter. For this reason, MK-OFL can considerably outperform SK-OFL, which will
be demonstrated in Section V via online learning tasks with real-world
datasets.

###  IV-B Proof of Theorem 1

To capture the randomness of kernel selections in MK-OFL, we introduce a
random variable $I_{t}$ which indicates a selected kernel index at time $t$ in
the server. As in the description of MK-OFL, the realization of $I_{t}$ is
denoted as $\hat{p}_{t}$. The parameters of $P$ kernel functions and the local
PMFs are also random variables, which are determined as a function of random
variables $I_{1},...,I_{t-1}$. Without loss of generality, their realizations
at time $t$ are denoted as $\\{\hat{q}_{k,t}(p):p\in[P],k\in[K]\\}$ and
$\\{\hat{{\bf w}}_{k,t}^{p}:p\in[P],k\in[K]\\}$, respectively. Also, the
realizations of the PMFs are denoted as $\hat{{\bf q}}_{t}(p)$ and $\bar{{\bf
q}}_{t}(p)$. With these notations, we first provide key lemmas for this proof.
Lemma 1 are immediately obtained following the proof of OGD convergence [7]
with the Assumption 2 and Assumption 3. The proofs of Lemma 2 and Lemma 3 are
provided in the appendices.

###### Lemma 1

For any $p\in[P]$ and step size $\eta_{l}>0$, the following upper bound is
hold:

$\displaystyle\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal L}\left(\left(\hat{{\bf
w}}_{k,t}^{p}\right)^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t}\right)$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;-\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal
L}\Big{(}({\bf w}_{p}^{\star})^{{\sf T}}{\bf z}_{p}({\bf
x}_{k,t}),y_{k,t}\Big{)}$
$\displaystyle\leq\frac{KC^{2}}{2\eta_{l}}+\frac{3\eta_{l}KL^{2}T}{2}.$

Proof: The proof is provided in Appendix A.

###### Lemma 2

For any fixed parameter $\eta_{g}>0$, we have:

$\displaystyle\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal
L}\left(\sum_{p=1}^{P}\hat{q}_{t}(p)\left(\hat{{\bf w}}_{k,t}^{p}\right)^{{\sf
T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t}\right)$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;-\min_{1\leq p\leq
P}\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal L}\left(\left(\hat{{\bf
w}}_{k,t}^{p}\right)^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{j,t}\right)$
$\displaystyle\leq\frac{1}{\eta_{g}}\log{P}+\frac{9\eta_{g}KT}{8}.$

Proof: The proof is provided in Appendix B.

It is remarkable that Lemma 1 and Lemma 2 hold for any realization of our
randomized algorithm. Setting $\eta_{l}={\cal O}(1\sqrt{T})$, the upper bound
of Lemma 1 is bounded by ${\cal O}(\sqrt{T})$. Also, setting $\eta_{g}={\cal
O}(1/\sqrt{T})$, the upper bound of Lemma 2 is bounded by ${\cal
O}(\sqrt{T})$. We next show that our randomized algorithm, choosing one kernel
at every time instead of using the combination of all $P$ kernels, only leads
to a bounded loss ${\cal O}(\sqrt{T})$.

###### Lemma 3

For some $\delta>0$, the following bound holds with at least probability
$1-\delta$:

$\displaystyle\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal L}\Big{(}W_{t}^{{\sf T}}{\bf
z}_{I_{t}}({\bf x}_{k,t}),y_{k,t}\Big{)}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;-\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal
L}\left(\sum_{p=1}^{P}\hat{q}_{t}(p)\left(\hat{{\bf w}}_{k,t}^{p}\right)^{{\sf
T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t}\right)$ $\displaystyle\leq
K\sqrt{\frac{\log(\delta^{-1})}{2}T}.$

Proof: The proof is provided in Appendix C.

Finally, from Lemma 1, Lemma 2 and Lemma 3 with the parameters
$\eta_{l}=\eta_{g}={\cal O}(1/\sqrt{T})$, the proof is completed.

##  V Experimental Results

We evaluate the accuracy performances of the proposed MK-OFL for various
online learning tasks such as online regressions and time-series predictions.
The OFL system with $K=20$ distributed nodes and communication overhead
$r=100$ is considered, and a regularized least-square loss function is
assumed, i.e.,

${\cal L}({\bf w}^{{\sf T}}{\bf z}_{p}({\bf x}),y)=\left[{\bf w}^{{\sf T}}{\bf
z}_{p}({\bf x})-y\right]^{2}+\lambda\|{\bf w}\|^{2}.$ (22)

Taking the randomness of our algorithm into account, the averaged performances
over 50 trials are evaluated. The learning accuracy at time $t$ is measured by
the mean-square-error (MSE) as

${\rm
MSE}(t)=\frac{1}{tK}\sum_{\tau=1}^{t}\sum_{k=1}^{K}(\hat{y}_{k,\tau}-y_{k,\tau})^{2},$
(23)

where $\hat{y}_{k,\tau}$ and $y_{k,\tau}$ denote a predicted label and a true
label, respectively. In these experiments, the following hyper-parameters for
both SK-OFL and MK-OFL are used:

$\eta_{l}=1/\sqrt{t},\;\eta_{g}=\log{P}/\sqrt{t},\mbox{ and }\lambda=0.01.$
(24)

These choices are based on anytime strategy [2], which is widely used in the
context of online learning when $T$ is unknown (e.g., continuous streaming
data). We remark that this anytime strategy also achieves the same asymptotic
performance in Theorem 1, which can be proved by incorporating the proof-
technique of anytime strategy in [2] into our proof in Section III. In non-
asymptotic cases, whereas, the performance MK-OFL can be further enhanced by
carefully optimizing the hyper-parameters $\eta_{l}$ and $\eta_{g}$. As
noticed in [8], such hyper-parameter optimization is still an open problem
even in the centralized setting. Instead, in our experiments, one pair of the
parameters in (24) are used for all test datasets. We build the kernel
dictionary with $11$ Gaussian kernels (i.e., $P=11$), each of which is defined
with the basis kernels

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

with the parameters (or bandwidths) $\sigma_{p}^{2}=10^{p-6}$, $p=1,2,...,11$.
Finally, the real-world datasets for our experiments in online regressions and
time-series predictions are described in Section V-A and V-B, respectively.

Figure 2: Convergence speed of a randomized MK-OFL by measuring the fraction
of the best kernel index out of 50 trials.

(a) Twitter data (b) Twitter data (Large) (c) Tom’s hardware data (d)
Conductivity data

(e) Wave data (f) Naval propulsion plant data

Figure 3: Comparisons of MSE performances of MK-OFL and SK-OFL in online
regressions tasks.

(a) Air quality data (b) Traffic data (c) Temperature data

Figure 4: Comparisons of MSE performances of MK-OFL and SK-OFL in time-series
prediction tasks.

First of all, we demonstrate our analytical result in Theorem 1 with the real-
world datasets. The corresponding numerical results are illustrated in Fig. 2,
where the fraction of selecting the best kernel $p^{\star}\in[P]$ out of 50
trials is evaluated. It is clearly shown that after a certain time (called a
convergence time), our randomized algorithm selects the best kernel out of
$P=11$ kernels with probability 1. Furthermore, the convergence time is
extremely fast. Because of this, MK-OFL can yield superior performance with a
not-so-large number of incoming data (e.g., $T\leq 1000$) as well as an
asymptotic case.

We next verify the effectiveness of the proposed MK-OFL in various online
learning tasks. Fig. 3 shows the MSE results in online regression tasks with
real-world datasets in Section V-A. We observe that MK-OFL almost achieves the
accuracy of the best kernel function in all the test datasets. Since the best
kernels are generally different according to datasets, it is not likely to
determine the best kernel at the beginning of an online learning process
(i.e., with no knowledge of dataset). As a consequence, when an suitable
kernel is preselected, SK-OFL can deteriorate the accuracy (see Fig. 3).
Especially in Fig. 3 (d) and (f), MKL-OFL and SK-OFL (with an unsuitable
kernel) have a non-trivial performance gap. This situation can be happened in
numerous real-world applications. Similarly, the MSE performances of MK-OFL in
time-series prediction tasks are provided in Fig. 4. These results also
manifest the advantage of using multiple kernels, achieving the performance of
the best kernel function and outperforming SK-OFL considerably. From the
experimental results in Fig. 3 and Fig. 4, one can expect that MK-OFL yields
an outstanding performance for any real-world application with a sufficiently
large number of kernels. This is a natural consequence as the probability of
the adequate kernel belongs to a set of $P$ kernels becomes higher as $P$
grows. In contrast, using multiple similar kernels might degrade the
performance since it can decrease the convergence time especially when there
exist several kernels similar to the best one. In this regard, one interesting
future work is to construct $P$ kernels so that they are distinct enough. With
a sufficiently large $P$, this construct can guarantee a fast convergence time
as well as increase the probability containing the adequate kernel in the
kernel dictionary. This is left of an interesting future work.

###  V-A Online Regression Tasks

For the experiments of online regression tasks, the following real datasets
from UCI Machine Learning Repository are considered:

  * •

Twitter [5]: Data contains buzz events from Twitter, where each attributes are
used to predict the popularity of a topic. Higher value indicates more
popularity. The larger dataset (termed Twitter(L)) is also considered.

  * •

Tom’s hardware [5]: Data consists of samples acquired from a forum, where each
features represents such as the number of times a content is displayed to
visitors. The task is to predict the average number of display about on a
certain topic.

  * •

Conductivity [10]: This dataset contains samples of extracted from
superconductors, where each feature represents critical information to
construct superconductor such as density and mass of atoms. The goal is to
predict the critical temperature to create superconductor.

  * •

Wave [13]: This data contains the samples consisting of positions and absorbed
power obtained from wave energy converters (WECs) in four real wave scenarios
from the southern coast of Australia. The goal is to predict total power
energy of the farm.

  * •

Naval propulsion plants [3]: This dataset has been obtained from Gas Turbine
plant. Dataset contains samples with 16 features such as ship speed and fuel
flow. The goal is to determine turbine decay state coefficient.

###  V-B Time-series Prediction Tasks

We consider time-series prediction tasks which estimate the future values in
online fashion. As considered in the centralized counterpart [8], the famous
time-series prediction method called Autogressive (AR) model is considered. An
${\rm AR}(s)$ model predicts the future value ${\bf y}_{t}$ assuming the
linear dependency on its $s$ values, i.e.,

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

where $\gamma_{i}$ denotes the weight for $y_{t-i}$ and $n_{t}$ denotes a
Gaussian noise at time $t$. Based on this, the RF-based kernelized ${\rm
AR}(s)$ model, which can explore a nonlinear dependency, is introduced in [8],
given as

$\displaystyle y_{t}=f_{t}({\bf x}_{t})+n_{t},$ (27)

where ${\bf x}_{t}=[y_{t-1},...,y_{t-s}]^{{\sf T}}$. The proposed MKL-OFL aims
at learning $f_{t}(\cdot)$ with a parameterized model $\hat{f}_{t}({\bf
x})=\hat{{\bf w}}_{t}{\bf z}_{\hat{p}_{t}}({\bf x})$. The proposed algorithm
is tested with the following univariate time-series datasets from UCI Machine
Learning Repository:

  * •

Air quality [18]: Data includes samples, of which features include hourly
response from an array of chemical sensors embedded in a city of Italy. The
goal is to predict the concentration of polluting chemicals in the air.

  * •

Traffic [4]: This dataset contains the time-series traffic data obtained from
Minneapolis Department of Transportation in US. Data is collected from hourly
interstate 94 Westbound traffic volume for MN DoT ATR station 301, roughly
midway between Minneapolis and St Paul, MN.

  * •

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

##  VI Conclusion

We have proposed a novel online federated learning (OFL) framework with
multiple kernels. The proposed method is dubbed multiple kernel-based OFL (MK-
OFL). In the proposed MK-OFL, one kernel index is random selected from a
predetermined set of $P$ kernels at every time according to a carefully
designed probability distribution. Also, the chosen index quickly converges to
the best kernel in hindsight. Thus, our algorithm indeed exploits the
advantage of using multiple kernels while having the same communication
overhead with a single kernel-based OFL (SK-OFL). The asymptotic optimality of
MK-OFL is proved using a martingale argument. Beyond the asymptotic analysis,
we demonstrated the effectiveness of our algorithm in various online learning
tasks with real-world datasets, which suggests practicality. One interesting
future work is to extend MK-OFL into a wireless OFL framework, in which a
distributed optimization at edge nodes and an optimal estimation at a server
will be incorporated. Another interesting future work is to construct the so-
called collaborative OFL by integrating collaborating learning with OFL so as
to enable edge nodes to engage in OFL without directly connecting a server.

##  Appendix A Proof of Lemma 1

Given the parameters $\hat{p}_{t}\in[P]$ and $\hat{{\bf w}}_{t}$, the OGD
update for any fixed $p\in[P]$ is given as

$\tilde{{\bf w}}_{k,t+1}^{p}=\hat{{\bf w}}_{k,t}^{p}-\eta_{\ell}\nabla{\cal
L}((\hat{{\bf w}}_{k,t}^{p})^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t}),$
(28)

where

$\hat{{\bf w}}_{k,t}^{p}=\begin{cases}\tilde{{\bf w}}_{k,t}^{p}&\mbox{ if
}\hat{p}_{t}\neq p\\\ \hat{{\bf w}}_{t}=\frac{1}{K}\sum_{k=1}^{K}\tilde{{\bf
w}}_{k,t}^{p}&\mbox{ if }\hat{p}_{t}=p.\end{cases}$ (29)

Our analysis is based on the regret analysis of OGD but carefully considering
the above cases. From (28) and following the analysis of OGD, we have that for
any $k\in{\cal V}$:

$\displaystyle\|\tilde{{\bf w}}_{k,t+1}^{p}-{\bf w}_{p}^{\star}\|^{2}$
$\displaystyle=\|\hat{{\bf w}}_{k,t}^{p}-\eta_{\ell}\nabla{\cal L}((\hat{{\bf
w}}_{k,t}^{p})^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t})-{\bf
w}_{p}^{\star}\|^{2}$ $\displaystyle=\|\hat{{\bf w}}_{k,t}^{p}-{\bf
w}_{p}^{\star}\|^{2}+\eta_{\ell}^{2}\|\nabla{\cal L}((\hat{{\bf
w}}_{k,t}^{p})^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t})\|^{2}$
$\displaystyle-2\eta_{\ell}\nabla{\cal L}((\hat{{\bf w}}_{k,t}^{p})^{{\sf
T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t})^{{\sf T}}(\hat{{\bf w}}_{k,t}^{p}-{\bf
w}_{p}^{\star}).$ (30)

Foe ease of exposition, throughout the proof, we let

$\nabla_{k,t}^{p}\stackrel{{\scriptstyle\Delta}}{{=}}\nabla{\cal L}((\hat{{\bf
w}}_{k,t}^{p})^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t}).$ (31)

According to the two cases in (29), we can get:

i) For $\hat{{\bf w}}_{k,t}^{p}=\tilde{{\bf w}}_{k,t}^{p}$ (i.e.,
$p\neq\hat{p}_{t}$), we have:

$\displaystyle\|\tilde{{\bf w}}_{k,t+1}^{p}-{\bf
w}_{p}^{\star}\|^{2}=\|\tilde{{\bf w}}_{k,t}^{p}-{\bf w}_{p}^{\star}\|^{2}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;+\eta_{\ell}^{2}\|\nabla_{k,t}^{p}\|^{2}-2\eta_{\ell}(\nabla_{k,t}^{p})^{{\sf
T}}(\hat{{\bf w}}_{k,t}^{p}-{\bf w}_{p}^{\star}).$ (32)

ii) For $\hat{{\bf w}}_{k,t}^{p}=\frac{1}{K}\sum_{k=1}^{K}\tilde{{\bf
w}}_{k,t}^{p}$ (i.e., $p=\hat{p}_{t}$), we have:

$\displaystyle\sum_{k\in[K]}\|\tilde{{\bf w}}_{k,t+1}^{p}-{\bf
w}_{p}^{\star}\|^{2}\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{k\in[K]}\|\tilde{{\bf
w}}_{k,t}^{p}-{\bf w}_{p}^{\star}\|^{2}$
$\displaystyle+\eta_{\ell}^{2}\sum_{k\in[K]}\|\nabla_{k,t}^{p}\|^{2}-2\eta_{\ell}\sum_{k\in[K]}(\nabla_{k,t}^{p})^{{\sf
T}}(\hat{{\bf w}}_{k,t}^{p}-{\bf w}_{p}^{\star}),$ (33)

where (a) is due to the following fact:

$\displaystyle\sum_{k\in[K]}\|\hat{{\bf w}}_{k,t}^{p}-{\bf
w}_{p}^{\star}\|^{2}=\frac{1}{K^{2}}\sum_{k\in[K]}\left\|\sum_{\ell\in[K]}\tilde{{\bf
w}}_{\ell,t}^{p}-{\bf w}_{p}^{\star}\right\|^{2}$
$\displaystyle\leq\frac{1}{K}\sum_{k\in[K]}\|\tilde{{\bf w}}_{k,t}^{p}-{\bf
w}_{p}^{\star}\|^{2}\leq\sum_{k\in[K]}\|\tilde{{\bf w}}_{k,t}^{p}-{\bf
w}_{p}^{\star}\|^{2}.$

Leveraging the convexity of a loss function, we obtain that for any $k\in{\cal
V}$:

$\displaystyle{\cal L}((\hat{{\bf w}}_{k,t}^{p})^{{\sf T}}{\bf z}_{p}({\bf
x}_{k,t}),y_{t})-{\cal L}(({\bf w}_{p}^{\star})^{{\sf T}}{\bf z}_{p}({\bf
x}_{k,t}),y_{t})$ $\displaystyle\leq(\nabla_{k,t}^{p})^{{\sf T}}(\hat{{\bf
w}}_{k,t}^{p}-{\bf w}_{p}^{\star}).$ (34)

Plugging (34) into (32) and (33) separately, and combining these two cases, we
can get

$\displaystyle\sum_{k=1}^{K}{\cal L}((\hat{{\bf w}}_{k,t}^{p})^{{\sf T}}{\bf
z}_{p}({\bf x}_{k,t}),y_{t})-{\cal L}(({\bf w}_{p}^{\star})^{{\sf T}}{\bf
z}_{p}({\bf x}_{k,t}),y_{t})$
$\displaystyle\leq\sum_{k=1}^{K}\frac{\|\tilde{{\bf w}}_{k,t}^{p}-{\bf
w}_{p}^{\star}\|^{2}-\|\tilde{{\bf w}}_{k,t+1}^{p}-{\bf
w}_{p}^{\star}\|^{2}}{2\eta_{\ell}}$
$\displaystyle+\frac{\eta_{\ell}}{2}\sum_{k=1}^{K}\|\nabla_{k,t}^{p}\|^{2}.$
(35)

Summing (35) over $t=1,...,T$, we obtain that for any fixed $p\in[P]$,

$\displaystyle\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal L}((\tilde{{\bf
w}}_{k,t}^{p})^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{t})-{\cal L}(({\bf
w}_{p}^{\star})^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{t})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{t=1}^{T}\sum_{k=1}^{K}\frac{\|\tilde{{\bf
w}}_{k,1}^{p}-{\bf
w}_{p}^{\star}\|^{2}}{2\eta_{\ell}}+\frac{\eta_{\ell}}{2}\sum_{t=1}^{T}\sum_{k=1}^{K}\|\nabla_{k,t}^{p}\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{KC^{2}}{2\eta_{\ell}}+\frac{\eta_{\ell}KL^{2}T}{2},$
(36)

where (a) is due to the telescoping sum and (b) is from the Assumption 2 and
Assumption 3. This completes the proof of Lemma 1.

##  Appendix B Proof of Lemma 2

Recall that

$L_{t}^{p}=\exp\left(-\eta_{g}\sum_{k=1}^{K}{\cal L}((\hat{{\bf
w}}_{k,t}^{p})^{{\sf T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t})\right).$ (37)

Also, to simplify the expressions, we let

$\hat{f}_{k,t}^{p}({\bf x})\stackrel{{\scriptstyle\Delta}}{{=}}(\hat{{\bf
w}}_{k,t}^{p})^{{\sf T}}{\bf z}_{p}({\bf x}).$ (38)

Then, the proof will be completed by comparing the upper and lower bounds of
$\zeta$, which is defined below:

$\displaystyle\zeta=\sum_{t=1}^{T}\log\left(\sum_{p=1}^{P}\hat{{\bf
q}}_{t}(p)\exp\left(-\eta_{g}\sum_{k=1}^{K}{\cal L}(\hat{f}_{k,t}^{p}({\bf
x}_{k,t}),y_{k,t})\right)\right).$

We first derive the upper bound on $\zeta$ such as

$\displaystyle\zeta$ $\displaystyle=\sum_{t=1}^{T}\log\left(\mbox{\bb
E}_{I_{t}}\left[\exp\left(-\eta_{g}\sum_{k=1}^{K}{\cal
L}(\hat{f}_{k,t}^{I_{t}}({\bf x}_{k,t}),y_{k,t})\right)\right]\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}-\eta_{g}\sum_{t=1}^{T}\sum_{k=1}^{K}\mbox{\bb
E}_{I_{t}}\left[{\cal L}(\hat{f}_{k,t}^{I_{t}}({\bf
x}_{k,t}),y_{k,t})\right]+\frac{\eta_{g}^{2}KT}{8}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}-\eta_{g}\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal
L}\left(\mbox{\bb E}_{I_{t}}\left[\hat{f}_{k,t}^{I_{t}}({\bf
x}_{k,t})\right],y_{k,t}\right)+\frac{\eta_{g}^{2}KT}{8},$

where (a) follows the Hoeffding’s inequality with the bounded random variable
${\cal L}(\hat{f}_{k,t}^{I_{t}}({\bf x}_{k,t}),y_{k,t})\in[0,1]$ and (b) is
from Assumption 1 (i.e., the convexity of a loss function). We next derive the
lower bound on $\zeta$ as follows:

$\displaystyle\zeta=\sum_{t=1}^{T}\log\left(\sum_{p=1}^{P}\hat{{\bf
q}}_{t}(p)\exp\left(-\eta_{g}\sum_{k=1}^{K}{\cal L}(\hat{f}_{k,t}^{p}({\bf
x}_{k,t}),y_{k,t})\right)\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{t=1}^{T}\log\left(\sum_{p=1}^{P}\bar{{\bf
q}}_{t}(p)\exp\left(-\eta_{g}\sum_{k=1}^{K}{\cal L}(\hat{f}_{k,t}^{p}({\bf
x}_{k,t}),y_{k,t})\right)\right)$
$\displaystyle\;\;\;\;\;+\sum_{t=1}^{T}\log\left(\frac{\sum_{p=1}^{P}\hat{{\bf
q}}_{t}(p)L_{t}^{p}}{\sum_{p=1}^{P}\bar{{\bf q}}_{t}(p)L_{t}^{p}}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\sum_{t=1}^{T}\log\left(\frac{\sum_{p=1}^{P}\bar{{\bf
m}}_{t+1}(p)}{\sum_{p=1}^{P}\bar{{\bf
m}}_{t}(p)}\right)+\sum_{t=1}^{T}\log\left(\frac{\sum_{p=1}^{P}\hat{{\bf
q}}_{t}(p)L_{t}^{p}}{\sum_{p=1}^{P}\bar{{\bf q}}_{t}(p)L_{t}^{p}}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\log\left(\sum_{p=1}^{P}\bar{{\bf
m}}_{T+1}(p)\right)-\log\left(\sum_{p=1}^{P}\bar{{\bf m}}_{1}(p)\right)$
$\displaystyle\;\;\;\;\;+\sum_{t=1}^{T}\log\left(\frac{\sum_{p=1}^{P}\hat{{\bf
q}}_{t}(p)L_{t}^{p}}{\sum_{p=1}^{P}\bar{{\bf q}}_{t}(p)L_{t}^{p}}\right)$
$\displaystyle\geq\log\left(\max_{1\leq p\leq P}\bar{{\bf
m}}_{T+1}\right)-\log{P}$
$\displaystyle\;\;\;\;\;+\sum_{t=1}^{T}\log\left(\frac{\sum_{p=1}^{P}\hat{{\bf
q}}_{t}(p)L_{t}^{p}}{\sum_{p=1}^{P}\bar{{\bf q}}_{t}(p)L_{t}^{p}}\right)$
$\displaystyle=-\eta_{g}\min_{1\leq p\leq P}\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal
L}(\hat{f}_{k,t}^{p}({\bf x}_{k,t}),y_{k,t})-\log{P}$
$\displaystyle\;\;\;\;\;+\sum_{t=1}^{T}\log\left(\frac{\sum_{p=1}^{P}\hat{{\bf
q}}_{t}(p)L_{t}^{p}}{\sum_{p=1}^{P}\bar{{\bf q}}_{t}(p)L_{t}^{p}}\right),$

where (a) follows the definition of $L_{t}^{p}$ in the main document, (b) is
from the definitions of $\bar{{\bf q}}_{t}(p)$ and $\bar{w}_{t}(p)$, and (c)
is due to the telescoping sum. From the upper and lower bounds, we can get

$\displaystyle-\eta_{g}\min_{1\leq p\leq P}\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal
L}(\hat{f}_{k,t}^{p}({\bf x}_{k,t}),y_{k,t})-\log{P}$
$\displaystyle+\sum_{t=1}^{T}\log\left(\frac{\sum_{p=1}^{P}\hat{{\bf
q}}_{t}(p)L_{t}^{p}}{\sum_{p=1}^{P}\bar{{\bf q}}_{t}(p)L_{t}^{p}}\right)$
$\displaystyle\leq-\eta_{g}\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal L}\left(\mbox{\bb
E}_{I_{t}}[\hat{f}_{k,t}^{I_{t}}({\bf
x}_{k,t})],y_{k,t}\right)+\frac{\eta_{g}^{2}KT}{8}.$

By rearranging them, we have:

$\displaystyle\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal
L}\left(\sum_{p=1}^{P}\hat{q}_{t}(p)\left(\hat{{\bf w}}_{k,t}^{p}\right)^{{\sf
T}}{\bf z}_{p}({\bf x}_{k,t}),y_{k,t}\right)$ $\displaystyle-\min_{1\leq p\leq
P}\sum_{t=1}^{T}\sum_{k=1}^{K}{\cal L}\left((\hat{{\bf w}}_{k,t}^{p})^{{\sf
T}}{\bf z}_{p}({\bf x}_{k,t}),y_{j,t}\right)$
$\displaystyle\leq\frac{1}{\eta_{g}}\log{P}+\frac{\eta_{g}KT}{8}+\sum_{t=1}^{T}\log\left(\frac{\sum_{p=1}^{P}\hat{{\bf
q}}_{t}(p)L_{t}^{p}}{\sum_{p=1}^{P}\bar{{\bf q}}_{t}(p)L_{t}^{p}}\right).$

Also, we have the following inequality:

$\displaystyle\sum_{t=1}^{T}\log\left(\frac{\sum_{p=1}^{P}\hat{{\bf
q}}_{t}(p)L_{t}^{p}}{\sum_{p=1}^{P}\bar{{\bf q}}_{t}(p)L_{t}^{p}}\right)$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{t=1}^{T}\log\left(\frac{\sum_{p=1}^{P}\hat{{\bf
q}}_{t}(p)}{\sum_{p=1}^{P}\bar{{\bf q}}_{t}(p)}\right)+\eta_{g}KT$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\stackrel{{\scriptstyle(b)}}{{=}}\eta_{g}KT,$

where (a) is due to the fact that $\exp(-K\eta_{g})\leq L_{t}^{p}\leq 1$ from
Assumption 1 and (b) is from that $\sum_{p=1}^{P}\hat{{\bf
q}}_{t}(p)=\sum_{p=1}^{P}\bar{{\bf q}}_{t}(p)=1$. From (3) and (4), the proof
is completed.

##  Appendix C Proof Lemma 3

For the proof, we define a random variable $X_{k,t}$ as

$\displaystyle X_{k,t}$ $\displaystyle={\cal L}(W_{t}^{{\sf T}}{\bf
z}_{I_{t}}({\bf x}_{k,t}),y_{k,t})$ $\displaystyle-\sum_{p=1}^{P}\hat{{\bf
q}}_{t}(p){\cal L}((\hat{{\bf w}}_{k,t}^{p})^{{\sf T}}{\bf z}_{p}({\bf
x}_{k,t}),y_{k,t}).$

Here, one can think that the fixed values $\hat{{\bf w}}_{k,t}^{p}$ and
$\hat{{\bf q}}_{t}(p)$ are obtained as a consequence of random variables
$I_{1},...,I_{t-1}$. Specifically, let ${\cal
F}_{t}=\sigma(I_{1},I_{2},...,I_{t})$ be the smallest sigma algebra such that
$I_{1},I_{2},...,I_{t}$ is measurable. Then, $\\{{\cal F}_{t}:t=1,...,T\\}$ is
filtration and $X_{k,t}$ is ${\cal F}_{t}$-measurable. Note that condition on
${\cal F}_{t-1}$, $\hat{{\bf q}}_{t}(p)$ and $\hat{{\bf w}}_{k,t}^{p}$ are
fixed and $I_{t}$ is only random variable. Leveraging this fact, we have:

$\mbox{\bb E}[X_{j,t}|{\cal F}_{t-1}]=0,$

because

$\displaystyle\mbox{\bb E}\left[{\cal L}\left(W_{t}^{{\sf T}}{\bf
z}_{I_{t}}({\bf x}_{k,t}),y_{k,t}\right)\Big{|}{\cal F}_{t-1}\right]$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=\sum_{p=1}^{P}\hat{{\bf
q}}_{t}(p){\cal L}\left((\hat{{\bf w}}_{k,t}^{p})^{{\sf T}}{\bf z}_{p}({\bf
x}_{k,t}),y_{k,t}\right).$

Thus, $\\{X_{k,t}:t\in[T]\\}$ is a martingale difference sequence and
$X_{k,t}\in[B_{t},B_{t}+c_{t}]$ is bounded, where $B_{t}=-U_{t}$ is a random
variable and ${\cal F}_{t-1}$ measurable, and $c_{t}=1$. From Azuma-
Hoeffding’s inequality, the following bound holds for some $\delta>0$ with at
least probability $1-\delta$:

$\displaystyle\sum_{t=1}^{T}X_{k,t}\leq\sqrt{\frac{\log{\delta^{-}1}}{2}T}.$
(39)

Since this is true for any $k\in{\cal V}$, we have:

$\sum_{t=1}^{T}\sum_{k=1}^{K}X_{k,t}\leq
K\sqrt{\frac{\log{\delta^{-}1}}{2}T}.$ (40)

This completes the proof.

## References

  * [1] Anguita, D., Ghio, A., Oneto, L., Parra, X., and Reyes-Ortiz, J. L. A public domain dataset for human activity recognition using smartphones. InEsann, volume 3,pp.3, 2013.
  * [2] Bubeck, S. Introduction to online optimization. Lecture Notes, 2, 2011.
  * [3] Coraddu, Oneto, L., Ghio, A., Savio, S., Anguita, D., and Figari, M., Machine learning approaches for improving condition based maintenance of naval propulsion plants. Journal of Engineering for the Maritime Environment, 2014.
  * [4] Dua, D. and Graff, C. UCI machine learning repository,2017. URL http://archive.ics.uci.edu/ml.
  * [5] Francois Kawala, Ahlame Douzal-Chouakria, E. G.and Dimert, E. Predictions activitee dans les reseauxsociaux en ligne. 4ieme Conference sur les Mod eleset lAnalyse des Reeseaux: Approches Mathematiqueset Informatiques, 2013
  * [6] Hard, A., Rao, K., Mathews, R., Ramaswamy, S., Beaufays, F., Augenstein, S., Eichner, H., Kiddon, C., andRamage, D. Federated learning for mobile keyboard prediction. arXiv preprint arXiv:1811.03604, 2018.
  * [7] Hazan, E. et al. Introduction to online convex optimization. Foundations and Trends®in Optimization, 2(3-4):157–325, 2016.
  * [8] Hong, S. and Chae, J. Active learning with multiple kernels. accepted to IEEE Transactions on neural networks and learning systems. [Online] arXiv preprint arXiv:2005.03188, 2020.
  * [9] Kairouz, P., McMahan, H. B., Avent, B., Bellet, A.,Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles,Z., Cormode, G., Cummings, R., et al. Advances and open problems in federated learning. arXiv preprintarXiv:1912.04977, 2019.
  * [10] K.Hamidieh. A data-driven statistical model for predicting the critical temperature of a superconductor. Computational Materials Science, pp. 346–354.
  * [11] Kivinen, J., Smola, A. J., and Williamson, R. C. Online learning with kernels. IEEE transactions on signal processing, 52(8):2165–2176, 2004.
  * [12] Konecny, J., McMahan, H. B., Yu, F. X., Richitarik,P., Suresh, A. T., and Bacon, D. Federated learning :Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492, 2016.
  * [13] M. M.Neshat, B. and Y.Xia. A detailed comparison of meta-heuristic methods for optimising wave energy converter placements. In Proceedings of the Genetic and Evolutionary Computation Conference, pp.1318–1325.
  * [14] Pantelopoulos, A. and Bourbakis, N. G. A survey on wearable sensor-based systems for health monitoring and prognosis. IEEE Transactions on Systems, Man,and Cybernetics, Part C (Applications and Reviews),40(1):1–12, 2009.
  * [15] Rahimi, A. and Recht, B. Random features for large-scale kernel machines. Advances in neural information processing systems, 20:1177–1184, 2007.
  * [16] Rashidi, P. and Cook, D. J. Keeping the resident in the loop: Adapting the smart home to the user. IEEE Transactions on systems, man, and cybernetics-part A:systems and humans, 39(5):949–959, 2009.
  * [17] Richard, C., Bermudez, J. C. M., and Honeine, P. Online prediction of time series data with kernels. IEEE Transactions on Signal Processing, 57(3):1058–1067,2008.
  * [18] Saverio De Vito, Ettore Massera, M.P.L.M. and Francia, G. D. On field calibration of an electronic nose forbenzene estimation in an urban pollution monitoring scenario. Sensors and Actuators B: Chemical, 129(2):750–757, 2008.
  * [19] Shawe-Taylor, J., Cristianini,N., et al. Kernel methods for pattern analysis. Cambridge university press,2004.
  * [20] Shen, S., Jiang, H., and Zhang, T. Stock market forecasting using machine learning algorithms. Department of Electrical Engineering, Stanford University,Stanford, CA, pp. 1–5, 2012.
  * [21] Shen, Y., Chen, T., and Giannakis, G. B. Random feature-based online multi-kernel learning in environments with unknown dynamics. The Journal of Ma-chine Learning Research, 20(1):773–808, 2019.
  * [22] Wahba, G. Spline models for observational data, volume 59. Siam, 1990.
  * [23] Wainwright, M.J. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019
  * [24] Yang, Q., Liu, Y., Chen, T., and Tong, Y. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology(TIST), 10(2):1–19, 2019.


Preliminariessection: preliminaries See kemenysnell1983 or norris1998markov
for basic facts about Markov chains. Throughout this paper, except where
otherwise noted, Markov chains are assumed to have a finite state space
indexed by positive integers $1,\dots,n$ for some $n$; when we consider Markov
chains with countably infinite state spaces, we will assume that for each
state $i$ there are only finitely many states $j$ such that the transition
probability $P_{ij}$ from state $i$ to state $j$ is positive. We can represent
a Markov chain by a weighted directed graph $G=(V,E)$ whose vertices $v_{i}\in
V$ are the allowed states and the weight of the directed edge
$(v_{i},v_{j})\in E$ is $P_{ij}$. For brevity, we will use the words state and
vertex to refer to both the state in the Markov chain and the corresponding
vertex in $G$, passing back and forth between the abstract Markov chain and
its concrete embodiment as a random walk on $G$. We say that state $i$ is an
absorbing state if $P_{ii}=1$ (equivalently if $G$ has a loop at $v_{i}$ with
weight 1). Notice that for every vertex $v\in G$, the sum of the weights of
all edges $(v,w)$ is 1.

Let $H=P-I$, where $I$ is the $n$-by-$n$ identity matrix. Let $H_{i}$,
$P_{i}$, and $I_{i}$ denote the $i$th rows of the matrices $H$, $P$, and $I$
respectively. Observe that $I_{i}=e_{i}$ (the $i$th unit vector) and that $-H$
is the Laplacian of the graph. The Markov chain admits at least one stationary
measure $\ppi$ for which the vector $v=[\ppi(1),\dots,\ppi(n)]$ satisfies
$vP=v$ (this follows from the assumption that the Markov chain is finite; see,
e.g., norris1998markov), so 1 is an eigenvalue of $P$ and 0 is an eigenvalue
of $H$. All eigenvalues of $P$ have magnitude at most 1. When the Markov chain
is irreducible (that is, when every state can be reached from every other
state in some finite number of steps), 1 is a simple eigenvalue of $P$ and 0
is a simple eigenvalue of $H$, so that $H$ has rank $n-1$, and the rows of
$H$, taken with integer coefficients, generate an $n-1$-dimensional sublattice
of the space of vectors with entries summing to zero; in this case, there is a
unique stationary measure $\ppi$ satisfying $\ppi(1)+\cdots+\ppi(n)=1$.

We now informally introduce the hunger game on the weighted directed graph $G$
by comparing it to the chip-firing model and the rotor-router model before
offering a more technical definition.

The “goodness” of a deterministic analogue of a random process can be assessed
by the notion of discrepancy. If some numerical characteristic of the
deterministic process converges to a corresponding numerical characteristic of
the random process as simulation time goes to infinity, one can try to
determine the rate of convergence.

The simplest deterministic analogues of Markov chains were invented by Engel
engel1975probabilistic,engel1976does, under the name the stochastic abacus
(though the term chip-firing is more common nowadays). Suppose that all the
transition probabilities $P_{ij}$ are rational, and that we have positive
integers $d_{1},\dots,d_{n}$ such that $d_{i}P_{ij}$ is an integer for all
$i,j$. Assume that the Markov chain is irreducible. Define a chip-
configuration as an $n$-tuple
$\mathbf{c}=(\mathbf{c}_{1},\dots,\mathbf{c}_{n})$; say that a chip-
configuration is stable if $\mathbf{c}_{i}<d_{i}$ whenever $i$ is a non-
absorbing state. If $\mathbf{c}_{i}\geq d_{i}$, then we obtain another chip-
configuration by firing at $i$, replacing $\mathbf{c}$ by
$\mathbf{c^{\prime}}=\mathbf{c}+d_{i}H_{i}$; if we represent the Markov chain
by drawing a graph with vertices $v_{1},\dots,v_{n}$ and we represent the
chip-configuration $\mathbf{c}$ by putting $\mathbf{c}_{j}$ chips at $v_{j}$
for all $j$, then firing means sending $d_{i}P_{ij}$ chips from $i$ to $j$ for
each $j\neq i$. Chip-firing can be used to find the stationary probability
measure of an irreducible Markov chain as follows. Put sufficiently many chips
on the state-graph so that stabilization is impossible no matter how many
firings are performed, and start performing firings however one wishes; when
we encounter a chip-configuration we have seen before (as must happen
eventually), the vector that records the number of times each state has fired
will be a stationary vector.

Suppose we have the Markov chain given by the Markov matrix 12 & 12 0
12 0 12
0 12 12 , representing a doubly-reflecting random walk. Its corresponding
graph is shown in fig:ex2G .

[scale=0.6,font=,baseline,thick] in 1,…,3 [color=black,fill=green!30,thick]
(4*,0) circle (16pt); at (4*,0) $v_{\x}$; in 2,3 [-¿,¿=latex] plot
[smooth,tension=1] coordinates (4*-0.866*0.7,0.4*0.7) (4*-2,0.7)
(4*-4+0.866*0.7,0.4*0.7); in 1,2 [-¿,¿=latex] plot [smooth,tension=1]
coordinates (4*+0.866*0.7,-0.4*0.7) (4*+2,-0.7) (4*+4-0.866*0.7,-0.4*0.7); at
(6,1) 0.5; at (10,1) 0.5; at (6,-1) 0.5; at (10,-1) 0.5; [-¿,¿=latex] plot
[smooth,tension=5] coordinates (4-0.866*0.7,0.5*0.7) (4-1.5,0)
(4-0.866*0.7,-0.5*0.7); at (2,0) 0.5; [-¿,¿=latex] plot [smooth,tension=5]
coordinates (12+0.866*0.7,-0.5*0.7) (12+1.5,0) (12+0.866*0.7,0.5*0.7); at
(14,0) 0.5;

Figure : A graph $G$ corresponding to a doubly-reflecting random walk.

If we place 1 chip at state 1, 2 chips at state 2, and 1 chip at state 3, then
state 2 is unstable, so we may fire at 2, turning the chip-configuration
(1,2,1) into the chip-configuration (2,0,2). Then firing at 1 and at 3 brings
us back to (1,2,1). The vector that records the number of times each state
fired is (1,1,1), which is indeed a stationary vector for this Markov chain.
The rotor-router model [holroyd2010rotor] is a different scheme for imitating
Markov chains deterministically. Assume as above that the Markov chain has
rational transition probabilities, with $d_{i}$ as above. Represent the Markov
chain using a directed graph with $d_{i}P_{ij}$ parallel edges from $v_{i}$ to
$v_{j}$, so that $v_{i}$ has outdegree $d_{i}$. Each vertex distributes
arriving chips along its outgoing edges in a cyclic manner, not sending a chip
along any edge for a second time until it has sent a chip along every edge at
least once, and thereafter always sending the next chip along the edge along
which it has sent a chip least recently. Inasmuch as the vertex with the chip
gets to decide where the chip goes next, we call this “supply-side” management
of the chip’s movement. Assume that the Markov chain is irreducible. It can be
shown that once the chip enters an infinite loop (as must happen eventually),
the fraction of the time that the chip spends at vertex $v_{i}$ is
proportional to the steady-state $\ppi(i)$. We use the same Markov chain as
example: 3 chip. Suppose we start with the chip at $v_{1}$ and begin the game
by sending the chip to $v_{2}$, then $v_{3}$, then $v_{3}$ again. Since at
this point the chip has already traveled along the edge sending $v_{3}$ to
$v_{3}$, it now travels along the edge from $v_{3}$ to $v_{2}$. As the chip
has already gone from $v_{2}$ to $v_{3}$, the rotor-router protocol dictates
that it must now travel along the other edge from $v_{2}$ and go to $v_{1}$.
Similarly, as it has already gone from $v_{1}$ to $v_{2}$, now it must travel
from $v_{1}$ to $v_{1}$. Thereafter the process cycles forever. Since within
each cycle the chip spends 2 steps at each vertex, (2,2,2) is a stationary
vector. The hunger game introduced in this article can be seen as a “demand-
side” management system: each vertex has a “hunger” for chips, determined by
its expectation of receiving chips from neighboring vertices that have been
previously visited. When a vertex $v$ receives a chip, the neighboring
vertices’ hunger increases in accordance to the transition probabilities from
$v$ to those vertices, and $v$ sends its chip to the vertex with highest
hunger (regardless of whether that chip is a neighbor of $v$). Now we give a
more formal definition of the hunger game. It is simplest to start with the
situation in which the chain runs forever without restarts (in contrast to
chains that will be restarted when they enter an absorbing state). We also
start with the case in which the state space is finite, with $|V|=n$,
deferring discussion of infinite-state spaces until later. The hunger vector
$\mathbf{h}\in\R^{n}$ represents the hunger at each vertex in $V$; we will
sometimes call it the hunger state to emphasize its interpretation as a state
of the hunger game system. At each step, whichever vertex has the highest
hunger receives the chip; if vertex $v_{i}$ receives the chip, then the hunger
vector $\mathbf{h}$ is updated by adding $H_{i}=P_{i}-I_{i}$ to it,
corresponding to the increase in vertices’ hunger from the presence of this
chip at $v_{i}$ but also the satiation of $v_{i}$ after receiving a chip. If
multiple states are tied for the highest hunger, we break the tie by choosing
the lowest-indexed such vertex. Since each row of $H$ has entries summing to
0, total hunger never changes. Each relocation of the chip is referred to as
firing the chip; specifically, when the chip is relocated at $i$, we say the
chip fires to $i$. Unlike rotor-router or chip-firing, under the hunger game
rules a chip does not necessarily have to be fired to a vertex adjacent to its
current location; see example: 3 hunger . In fact, the determination of the
chip’s next location depends only on the hunger state $\mathbf{h}$ and not the
current location of the chip. The step can be described purely in terms of the
matrix $H$ and the vector $\mathbf{h}$ without any reference to chips, via the
rule “Replace $\mathbf{h}$ by $\mathbf{h}^{\prime}=\mathbf{h}+H_{i}$ where $i$
maximizes $\mathbf{h}_{i}$, choosing the smallest such $i$ in the event of a
tie.” We use the same Markov chain as example: 3 chip. Starting with
$\mathbf{h}=0$, as shown in subfig:ex2init , regardless of the initial
location of the chip, we fire the chip to $v_{1}$ under the tie-breaking rule,
yielding $\mathbf{h}=\left[-\frac{1}{2},\frac{1}{2},0\right]$ as shown in
subfig:ex2fire1 . After this, we fire to $v_{2}$, as shown in subfig:ex2fire2
, and then fire to $v_{3}$, as shown in subfig:ex2fire3 . Notice that we have
returned back to the initial hunger state $\mathbf{h}=\mathbf{0}$, so this
process repeats, visiting states 1, 2, 3, then back to 1, and so on. Notice
that we fire the chip from 3 to 1 even though $P_{31}=0$.

[scale=0.6,font=,baseline,thick] /in 1/white,2/white,3/white
[color=black,fill=,thick] (4*,0) circle (16pt); /in 1/0,2/0,3/0 at (4*,0) ; in
2,3 [-¿,¿=latex] plot [smooth,tension=1] coordinates (4*-0.866*0.7,0.4*0.7)
(4*-2,0.7) (4*-4+0.866*0.7,0.4*0.7); in 1,2 [-¿,¿=latex] plot
[smooth,tension=1] coordinates (4*+0.866*0.7,-0.4*0.7) (4*+2,-0.7)
(4*+4-0.866*0.7,-0.4*0.7); at (6,1) 0.5; at (10,1) 0.5; at (6,-1) 0.5; at
(10,-1) 0.5; [-¿,¿=latex] plot [smooth,tension=5] coordinates
(4-0.866*0.7,0.5*0.7) (4-1.5,0) (4-0.866*0.7,-0.5*0.7); at (2,0) 0.5;
[-¿,¿=latex] plot [smooth,tension=5] coordinates (12+0.866*0.7,-0.5*0.7)
(12+1.5,0) (12+0.866*0.7,0.5*0.7); at (14,0) 0.5;
[scale=0.6,font=,baseline,thick] /in 1/blue!30,2/yellow!30,3/white
[color=black,fill=,thick] (4*,0) circle (16pt); /in 1/-0.5,2/0.5,3/0 at (4*,0)
; in 2,3 [-¿,¿=latex] plot [smooth,tension=1] coordinates
(4*-0.866*0.7,0.4*0.7) (4*-2,0.7) (4*-4+0.866*0.7,0.4*0.7); in 1,2
[-¿,¿=latex] plot [smooth,tension=1] coordinates (4*+0.866*0.7,-0.4*0.7)
(4*+2,-0.7) (4*+4-0.866*0.7,-0.4*0.7); at (6,1) 0.5; at (10,1) 0.5; at (6,-1)
0.5; at (10,-1) 0.5; [-¿,¿=latex] plot [smooth,tension=5] coordinates
(4-0.866*0.7,0.5*0.7) (4-1.5,0) (4-0.866*0.7,-0.5*0.7); at (2,0) 0.5;
[-¿,¿=latex] plot [smooth,tension=5] coordinates (12+0.866*0.7,-0.5*0.7)
(12+1.5,0) (12+0.866*0.7,0.5*0.7); at (14,0) 0.5;
[scale=0.6,font=,baseline,thick] /in 1/yellow!30,2/blue!30,3/yellow!30
[color=black,fill=,thick] (4*,0) circle (16pt); /in 1/0,2/-0.5,3/0.5 at (4*,0)
; in 2,3 [-¿,¿=latex] plot [smooth,tension=1] coordinates
(4*-0.866*0.7,0.4*0.7) (4*-2,0.7) (4*-4+0.866*0.7,0.4*0.7); in 1,2
[-¿,¿=latex] plot [smooth,tension=1] coordinates (4*+0.866*0.7,-0.4*0.7)
(4*+2,-0.7) (4*+4-0.866*0.7,-0.4*0.7); at (6,1) 0.5; at (10,1) 0.5; at (6,-1)
0.5; at (10,-1) 0.5; [-¿,¿=latex] plot [smooth,tension=5] coordinates
(4-0.866*0.7,0.5*0.7) (4-1.5,0) (4-0.866*0.7,-0.5*0.7); at (2,0) 0.5;
[-¿,¿=latex] plot [smooth,tension=5] coordinates (12+0.866*0.7,-0.5*0.7)
(12+1.5,0) (12+0.866*0.7,0.5*0.7); at (14,0) 0.5;
[scale=0.6,font=,baseline,thick] /in 1/white,2/yellow!30,3/blue!30
[color=black,fill=,thick] (4*,0) circle (16pt); /in 1/0,2/0,3/0 at (4*,0) ; in
2,3 [-¿,¿=latex] plot [smooth,tension=1] coordinates (4*-0.866*0.7,0.4*0.7)
(4*-2,0.7) (4*-4+0.866*0.7,0.4*0.7); in 1,2 [-¿,¿=latex] plot
[smooth,tension=1] coordinates (4*+0.866*0.7,-0.4*0.7) (4*+2,-0.7)
(4*+4-0.866*0.7,-0.4*0.7); at (6,1) 0.5; at (10,1) 0.5; at (6,-1) 0.5; at
(10,-1) 0.5; [-¿,¿=latex] plot [smooth,tension=5] coordinates
(4-0.866*0.7,0.5*0.7) (4-1.5,0) (4-0.866*0.7,-0.5*0.7); at (2,0) 0.5;
[-¿,¿=latex] plot [smooth,tension=5] coordinates (12+0.866*0.7,-0.5*0.7)
(12+1.5,0) (12+0.866*0.7,0.5*0.7); at (14,0) 0.5;

Figure : The initial hunger state $\mathbf{h}=\mathbf{0}$. Figure :
$\mathbf{h}$ after firing to $v_{1}$, shown in blue. States with updated
hungers are shown in yellow. Figure : $\mathbf{h}$ after firing to $v_{2}$,
shown in blue. States with updated hungers are shown in yellow. Figure :
$\mathbf{h}$ after firing to $v_{3}$, shown in blue. States with updated
hungers are shown in yellow. Figure : The hunger game on a doubly-reflecting
random walk.

If one ignores the chip and focuses on the entries of the hunger vector, the
hunger game can be viewed as a greedy variant of chip-firing. Specifically, if
all entries of $\mathbf{h}$ and $P$ are rational, we can without loss of
generality assume they are all non-negative integers (since the firing rule is
invariant under affine transformation of the hunger vector) and create a chip-
configuration of the customary kind in which the number of chips at $i$ is
$\mathbf{h}_{i}$. Then the firing rule, translated to the new context, tells
us to fire the vertex $i$ that has the most chips, with ties resolved as
before. When the state space is (countably) infinite, our hunger vectors are
infinite sequences. We restrict ourselves to sequences that are bounded and
take on only finitely many distinct values; this ensures that there exists at
least one $i$ for which $\mathbf{h}_{i}$ equals $\sup_{i}\mathbf{h}_{i}$, from
which it follows that a smallest such $i$ exists. As each vertex has only
finitely many outgoing edges, this assumption ensures that after any finite
number of steps in the hunger game there are only finitely many distinct
values of hunger, so a vertex of highest hunger can be found and the lowest-
indexed one can be chosen, ad infinitum. For Markov chains with absorbing
states we vary the procedure slightly. We start with a graph devoid of chips,
add a chip at an initial vertex, and then follow the rule for moving the chip
described above, with the extra stipulation that when the chip reaches an
absorbing vertex, it gets removed from the graph. In more detail, we define
chip addition operators $E_{i}$ as follows: Given an initial hunger vector
$\mathbf{h}$, we place a chip at $v_{i}$ (increasing the hunger of the
neighbors of $v_{i}$) and add $P_{i}$ to $\mathbf{h}$, and we then repeatedly
move the chip to the currently hungriest vertex (the lowest-indexed one, in
the event of a tie), simultaneously incrementing the hunger vector by the row
of $H$ corresponding to the chip’s new location, until we arrive at an
absorbing vertex $v_{k}$, at which point we subtract $P_{k}=I_{k}$ from the
current hunger vector and remove the chip from $v_{k}$. We define
$E_{i}(\mathbf{h})$ to be the final hunger vector, and call $E_{i}$ the chip
addition operator at $i$. It is possible for $E_{i}(\mathbf{h})$ to be
undefined, in the event that the process never arrives at an absorbing state,
but we will show in lemma: finite terminate that for finite absorbing chains
the process must terminate so that $E_{i}$ is well-defined; moreover, each
chip addition operator preserves total hunger, since the sum of the entries
increases by 1 when $P_{i}$ is added, stays the same each time a row of $H$ is
added, and decreases by 1 when $P_{k}$ is subtracted. As in the previous
situation, the process can be described purely in terms of vector and matrix
operations without reference to $G$ or a chip. Given a vector
$\mathbf{h}\in\R^{n}$, add row $P_{i}$ to $\mathbf{h}$. Thereafter, if $j$ is
the unique value such that $h_{j^{\prime}}<h_{j}$ for all $j^{\prime}<j$ and
$h_{j}\geq h_{j^{\prime}}$ for all ${j^{\prime}}>j$, add $H_{j}$ to
$\mathbf{h}$, unless $j$ is an absorbing state (call it $k$), in which case
subtract $P_{k}$ from the hunger vector and stop, calling the result
$E_{i}(\mathbf{h})$. Suppose we have the Markov chain represented by the graph
in fig:ex1G . It has absorbing states $v_{1}$ and $v_{5}$.

[scale=0.6,font=,baseline,thick] in 1,…,5 [color=black,fill=green!30,thick]
(4*,0) circle (16pt); at (4*,0) $v_{\x}$; [-¿,¿=latex] plot [smooth,tension=5]
coordinates (8+0.5*0.7,0.866*0.7) (8+0,1.5) (8-0.5*0.7,0.866*0.7); at (8,1.8)
0.6; in 3,…,4 [-¿,¿=latex] plot [smooth,tension=1] coordinates
(4*-0.866*0.7,0.4*0.7) (4*-2,0.7) (4*-4+0.866*0.7,0.4*0.7); in 2,…,3
[-¿,¿=latex] plot [smooth,tension=1] coordinates (4*+0.866*0.7,-0.4*0.7)
(4*+2,-0.7) (4*+4-0.866*0.7,-0.4*0.7); [-¿,¿=latex] (8-0.7,0) – (4+0.7,0);
[-¿,¿=latex] (16+0.7,0) – (20-0.7,0); at (6,0.3) 0.2; at (10,1) 0.6; at (14,1)
0.2; at (10,-1) 0.2; at (14,-1) 0.4; at (18,-0.3) 0.8; [-¿,¿=latex] plot
[smooth,tension=5] coordinates (4-0.866*0.7,0.5*0.7) (4-1.5,0)
(4-0.866*0.7,-0.5*0.7); at (2.2,0) 1; [-¿,¿=latex] plot [smooth,tension=5]
coordinates (20+0.866*0.7,-0.5*0.7) (20+1.5,0) (20+0.866*0.7,0.5*0.7); at
(21.8,0) 1;

Figure : A graph $G$ corresponding to an absorbing Markov chain.

Let us compute $E_{3}(\mathbf{0})$. Starting with $\mathbf{h}=\mathbf{0}$, for
our first step we add a chip to $v_{3}$ to yield $\mathbf{h}=[0,0.6,0,0.4,0]$,
as shown in subfig:ex1insert . After this, we follow additional steps of the
hunger game process, firing the chip successively to $v_{2}$, $v_{4}$, and
$v_{5}$, as shown in subfig:ex1fire3 . Having reached an absorbing state, the
final step is to remove the chip from $v_{5}$, resulting in
$E_{3}(\mathbf{0})=[0.2,0.2,0.4,-0.6,-0.2]$, as shown in subfig:ex1remove .

[scale=0.6,font=,baseline,thick] /in 1/white,2/white,3/white,4/white,5/white
[color=black,fill=,thick] (4*,0) circle (16pt); /in 1/0,2/0,3/0,4/0,5/0 at
(4*,0) ; [-¿,¿=latex] plot [smooth,tension=5] coordinates
(8+0.5*0.7,0.866*0.7) (8+0,1.5) (8-0.5*0.7,0.866*0.7); at (8,1.8) 0.6; in
3,…,4 [-¿,¿=latex] plot [smooth,tension=1] coordinates (4*-0.866*0.7,0.4*0.7)
(4*-2,0.7) (4*-4+0.866*0.7,0.4*0.7); in 2,…,3 [-¿,¿=latex] plot
[smooth,tension=1] coordinates (4*+0.866*0.7,-0.4*0.7) (4*+2,-0.7)
(4*+4-0.866*0.7,-0.4*0.7); [-¿,¿=latex] (8-0.7,0) – (4+0.7,0); [-¿,¿=latex]
(16+0.7,0) – (20-0.7,0); at (6,0.3) 0.2; at (10,1) 0.6; at (14,1) 0.2; at
(10,-1) 0.2; at (14,-1) 0.4; at (18,-0.3) 0.8; [-¿,¿=latex] plot
[smooth,tension=5] coordinates (4-0.866*0.7,0.5*0.7) (4-1.5,0)
(4-0.866*0.7,-0.5*0.7); at (2.2,0) 1; [-¿,¿=latex] plot [smooth,tension=5]
coordinates (20+0.866*0.7,-0.5*0.7) (20+1.5,0) (20+0.866*0.7,0.5*0.7); at
(21.8,0) 1; [scale=0.6,font=,baseline,thick] /in
1/white,2/yellow!30,3/blue!30,4/yellow!30,5/white [color=black,fill=,thick]
(4*,0) circle (16pt); /in 1/0,2/0.6,3/0,4/0.4,5/0 at (4*,0) ; [-¿,¿=latex]
plot [smooth,tension=5] coordinates (8+0.5*0.7,0.866*0.7) (8+0,1.5)
(8-0.5*0.7,0.866*0.7); at (8,1.8) 0.6; in 3,…,4 [-¿,¿=latex] plot
[smooth,tension=1] coordinates (4*-0.866*0.7,0.4*0.7) (4*-2,0.7)
(4*-4+0.866*0.7,0.4*0.7); in 2,…,3 [-¿,¿=latex] plot [smooth,tension=1]
coordinates (4*+0.866*0.7,-0.4*0.7) (4*+2,-0.7) (4*+4-0.866*0.7,-0.4*0.7);
[-¿,¿=latex] (8-0.7,0) – (4+0.7,0); [-¿,¿=latex] (16+0.7,0) – (20-0.7,0); at
(6,0.3) 0.2; at (10,1) 0.6; at (14,1) 0.2; at (10,-1) 0.2; at (14,-1) 0.4; at
(18,-0.3) 0.8; [-¿,¿=latex] plot [smooth,tension=5] coordinates
(4-0.866*0.7,0.5*0.7) (4-1.5,0) (4-0.866*0.7,-0.5*0.7); at (2.2,0) 1;
[-¿,¿=latex] plot [smooth,tension=5] coordinates (20+0.866*0.7,-0.5*0.7)
(20+1.5,0) (20+0.866*0.7,0.5*0.7); at (21.8,0) 1;
[scale=0.6,font=,baseline,thick] /in
1/yellow!30,2/blue!30,3/yellow!30,4/white,5/white [color=black,fill=,thick]
(4*,0) circle (16pt); /in 1/0.2,2/0.2,3/0.2,4/0.4,5/0 at (4*,0) ; [-¿,¿=latex]
plot [smooth,tension=5] coordinates (8+0.5*0.7,0.866*0.7) (8+0,1.5)
(8-0.5*0.7,0.866*0.7); at (8,1.8) 0.6; in 3,…,4 [-¿,¿=latex] plot
[smooth,tension=1] coordinates (4*-0.866*0.7,0.4*0.7) (4*-2,0.7)
(4*-4+0.866*0.7,0.4*0.7); in 2,…,3 [-¿,¿=latex] plot [smooth,tension=1]
coordinates (4*+0.866*0.7,-0.4*0.7) (4*+2,-0.7) (4*+4-0.866*0.7,-0.4*0.7);
[-¿,¿=latex] (8-0.7,0) – (4+0.7,0); [-¿,¿=latex] (16+0.7,0) – (20-0.7,0); at
(6,0.3) 0.2; at (10,1) 0.6; at (14,1) 0.2; at (10,-1) 0.2; at (14,-1) 0.4; at
(18,-0.3) 0.8; [-¿,¿=latex] plot [smooth,tension=5] coordinates
(4-0.866*0.7,0.5*0.7) (4-1.5,0) (4-0.866*0.7,-0.5*0.7); at (2.2,0) 1;
[-¿,¿=latex] plot [smooth,tension=5] coordinates (20+0.866*0.7,-0.5*0.7)
(20+1.5,0) (20+0.866*0.7,0.5*0.7); at (21.8,0) 1;
[scale=0.6,font=,baseline,thick] /in
1/white,2/white,3/yellow!30,4/blue!30,5/yellow!30 [color=black,fill=,thick]
(4*,0) circle (16pt); /in 1/0.2,2/0.2,3/0.4,4/-0.6,5/0.8 at (4*,0) ;
[-¿,¿=latex] plot [smooth,tension=5] coordinates (8+0.5*0.7,0.866*0.7)
(8+0,1.5) (8-0.5*0.7,0.866*0.7); at (8,1.8) 0.6; in 3,…,4 [-¿,¿=latex] plot
[smooth,tension=1] coordinates (4*-0.866*0.7,0.4*0.7) (4*-2,0.7)
(4*-4+0.866*0.7,0.4*0.7); in 2,…,3 [-¿,¿=latex] plot [smooth,tension=1]
coordinates (4*+0.866*0.7,-0.4*0.7) (4*+2,-0.7) (4*+4-0.866*0.7,-0.4*0.7);
[-¿,¿=latex] (8-0.7,0) – (4+0.7,0); [-¿,¿=latex] (16+0.7,0) – (20-0.7,0); at
(6,0.3) 0.2; at (10,1) 0.6; at (14,1) 0.2; at (10,-1) 0.2; at (14,-1) 0.4; at
(18,-0.3) 0.8; [-¿,¿=latex] plot [smooth,tension=5] coordinates
(4-0.866*0.7,0.5*0.7) (4-1.5,0) (4-0.866*0.7,-0.5*0.7); at (2.2,0) 1;
[-¿,¿=latex] plot [smooth,tension=5] coordinates (20+0.866*0.7,-0.5*0.7)
(20+1.5,0) (20+0.866*0.7,0.5*0.7); at (21.8,0) 1;
[scale=0.6,font=,baseline,thick] /in 1/white,2/white,3/white,4/white,5/blue!30
[color=black,fill=,thick] (4*,0) circle (16pt); /in
1/0.2,2/0.2,3/0.4,4/-0.6,5/0.8 at (4*,0) ; [-¿,¿=latex] plot
[smooth,tension=5] coordinates (8+0.5*0.7,0.866*0.7) (8+0,1.5)
(8-0.5*0.7,0.866*0.7); at (8,1.8) 0.6; in 3,…,4 [-¿,¿=latex] plot
[smooth,tension=1] coordinates (4*-0.866*0.7,0.4*0.7) (4*-2,0.7)
(4*-4+0.866*0.7,0.4*0.7); in 2,…,3 [-¿,¿=latex] plot [smooth,tension=1]
coordinates (4*+0.866*0.7,-0.4*0.7) (4*+2,-0.7) (4*+4-0.866*0.7,-0.4*0.7);
[-¿,¿=latex] (8-0.7,0) – (4+0.7,0); [-¿,¿=latex] (16+0.7,0) – (20-0.7,0); at
(6,0.3) 0.2; at (10,1) 0.6; at (14,1) 0.2; at (10,-1) 0.2; at (14,-1) 0.4; at
(18,-0.3) 0.8; [-¿,¿=latex] plot [smooth,tension=5] coordinates
(4-0.866*0.7,0.5*0.7) (4-1.5,0) (4-0.866*0.7,-0.5*0.7); at (2.2,0) 1;
[-¿,¿=latex] plot [smooth,tension=5] coordinates (20+0.866*0.7,-0.5*0.7)
(20+1.5,0) (20+0.866*0.7,0.5*0.7); at (21.8,0) 1;
[scale=0.6,font=,baseline,thick] /in
1/white,2/white,3/white,4/white,5/yellow!30 [color=black,fill=,thick] (4*,0)
circle (16pt); /in 1/0.2,2/0.2,3/0.4,4/-0.6,5/-0.2 at (4*,0) ; [-¿,¿=latex]
plot [smooth,tension=5] coordinates (8+0.5*0.7,0.866*0.7) (8+0,1.5)
(8-0.5*0.7,0.866*0.7); at (8,1.8) 0.6; in 3,…,4 [-¿,¿=latex] plot
[smooth,tension=1] coordinates (4*-0.866*0.7,0.4*0.7) (4*-2,0.7)
(4*-4+0.866*0.7,0.4*0.7); in 2,…,3 [-¿,¿=latex] plot [smooth,tension=1]
coordinates (4*+0.866*0.7,-0.4*0.7) (4*+2,-0.7) (4*+4-0.866*0.7,-0.4*0.7);
[-¿,¿=latex] (8-0.7,0) – (4+0.7,0); [-¿,¿=latex] (16+0.7,0) – (20-0.7,0); at
(6,0.3) 0.2; at (10,1) 0.6; at (14,1) 0.2; at (10,-1) 0.2; at (14,-1) 0.4; at
(18,-0.3) 0.8; [-¿,¿=latex] plot [smooth,tension=5] coordinates
(4-0.866*0.7,0.5*0.7) (4-1.5,0) (4-0.866*0.7,-0.5*0.7); at (2.2,0) 1;
[-¿,¿=latex] plot [smooth,tension=5] coordinates (20+0.866*0.7,-0.5*0.7)
(20+1.5,0) (20+0.866*0.7,0.5*0.7); at (21.8,0) 1;

Figure : The effect of inserting a chip at $v_{3}$, shown in blue. States with
updated hungers are shown in yellow. Figure : $\mathbf{h}$ as the chip fires
successively to $v_{2}$, $v_{4}$, and $v_{5}$, shown in blue. Updated hungers
are shown in yellow. Figure : $\mathbf{h}$ after removing chip from $v_{5}$,
shown in yellow. Figure : The hunger game on $G$ from fig:ex1G after inserting
a chip at $v_{3}$.

Notice that the total hunger is 0 at the start, increases to 1 when the chip
is added at $v_{3}$, stays 1 as the chip moves through $G$, and decreases to 0
when the chip is removed at the end. Since increasing the hunger at every
vertex by the same amount has no effect on the dynamics of the hunger game,
when our Markov chain is finite we will often assume that total hunger is 0.