# Walk for Learning:
A Random Walk Approach for Federated Learning from Heterogeneous Data

Ghadir Ayache1, Venkat Dassari2, Salim El Rouayheb1

1Electrical and Computer Engineering Department, Rutgers University  2US Army
Research Lab

###### Abstract

We consider the problem of a Parameter Server (PS) that wishes to learn a
model that fits data distributed on the nodes of a graph. We focus on
Federated Learning (FL) as a canonical application. One of the main challenges
of FL is the communication bottleneck between the nodes and the parameter
server. A popular solution in the literature is to allow each node to do
several local updates on the model in each iteration before sending it back to
the PS. While this mitigates the communication bottleneck, the statistical
heterogeneity of the data owned by the different nodes has proven to delay
convergence and bias the model.

In this work, we study random walk (RW) learning algorithms for tackling the
communication and data heterogeneity problems. The main idea is to leverage
available direct connections among the nodes themselves, which are typically
“cheaper” than the communication to the PS. In a random walk, the model is
thought of as a “baton” that is passed from a node to one of its neighbors
after being updated in each iteration.

The challenge in designing the RW is the data heterogeneity and the
uncertainty about the data distributions. Ideally, we would want to visit more
often nodes that hold more informative data. We cast this problem as a
sleeping multi-armed bandit (MAB) to design near-optimal node sampling
strategy that achieves a variance reduced gradient estimates and approaches
sub-linearly the optimal sampling strategy. Based on this framework, we
present an adaptive random walk learning algorithm. We provide theoretical
guarantees on its convergence. Our numerical results validate our theoretical
findings and show that our algorithm outperforms existing random walk
algorithms.

###### Index Terms:

Decentralized Learning, Distributed Learning, Random Walk, Incremental
Algorithms, Multi-armed Bandit.

##  I Introduction

###  I-A Overview and Motivation

Distributed Machine Learning has proven to be an important framework for
training machine learning models without moving the available data from its
local devices, which ensures privacy and scalability. Federated Learning (FL)
has risen to be one of the main applications [1, 2, 3] that has been
attracting significant research attention and has been deployed in real-world
systems with millions of uses [2]. Other applications include learning in IoT
networks [4], smart cities and healthcare [5, 6]. To see how a typical
learning algorithm works in this setting, consider the FL setting in Fig 1.
There is as Parameter Server (PS) (typically sitting in the cloud) and a
number of nodes (phones, IoT-devices, smart sensors, etc.) each having its own
local data. The PS wishes to learn a global model on all the data without
moving the data away from its original owner. The algorithm would work in a
batch SGD fashion. In each iteration, the PS samples a batch of nodes and
sends the current model to it. Each node in this batch will update the model
based on its local data and sends back its updated model to the PS. The PS
then aggregates all the received models and starts over again.

Figure 1: Distributed Learning on Graph through local computations at the
graph’s nodes and through local communication between the connected nodes.

Locality vs. Heterogenity. One of the main bottlenecks here is the
communication with the parameter server (PS) needed in each iteration to
aggregate the updates sent by the nodes and to coordinate the learning
process. A popular solution is to reduce the communication cost with the PS is
to let each node perform several local model updates on its data before
reporting back to the PS [7]. However, the local computations may induce local
biases to the model and slow the convergence of the learning algorithm. This
is due to the data that is heterogeneous across the different nodes, which
imposes an inconsistency between the local and the global objectives [8, 9].

Random Walks.

Figure 2: Random Walk (RW) on the graph: the updated model $w^{(k)}$ is
transmitted at time $k$. The self-loops at $k=3$ and $k=9$, indicate that the
RW algorithm decided to make a second update at the same node. The model is
reported back to the PS on a regular basis.

We propose Random Walks (RW) as a way to simultaneously achieve two seemingly
opposing goals: extending the benefits of locality and mitigating the
drawbacks of data heterogeneity. The idea being that instead of restricting
local computations to the node itself, they can be extended to its neighboring
nodes. This is achieved by leveraging existing local connections among the
nodes themselves, which are typically cheaper than communication to the PS. We
represent the local connections by a graph structure where each node is
connected to a subset of other neighboring nodes. Thus, each node can exchange
information with its neighbors and, through these local communications,
information can propagate through the whole network. This setting can arise in
mobile and edge networks, IoT applications and ad-hoc networks, to name a few.

In our proposed framework, the learning algorithm will run as a random walk
where in each iteration the model gets updated at one of the nodes and then
passed to one of its neighbors to take over the next update, as shown in
Figure 2. The model is then passed to the PS on a regular basis and/or
depending on the network resources to mitigate the communication cost to the
PS.

Random walk learning algorithms have been well studied in the literature on
optimization [10, 11], wireless networks [12] and signal processing [13]. What
distinguishes this work is that it tackles the problem of designing random
walk learning algorithms in the presence of arbitrary data heterogeneity
across the nodes. Our main contribution is a random walk algorithm that, along
with updating the model, it learns and adapts to the different nodes’
distributions by carefully combining exploration and exploitation. Our main
tool is the theory of Multi-Armed Bandit (MAB).

Random Walk via Multi-Armed Bandit. Typically, the distributions of the local
data at each node are not known a priori. Therefore, we want to devise a
random walk strategy that overcomes data heterogeneity by learning about the
local data distributions along the way. The goal is to minimize the variance
of the global objective gradient estimates computed locally by adjusting the
nodes’ sampling strategy. More specifically, at each iteration $k$, one has to
design the probabilities with which the next node in the RW is chosen among
the neighboring nodes. Note that these probabilities will depend on $k$ to
adapt to the information learned so far, leading to a time-varying RW.
Therefore, the random walk will start with an exploration phase before
gradually transitioning into an exploitation phase, once more robust estimates
about the nodes’ data are obtained.

We design the RW by casting our problem as Mulit-Armed bandit. The multi-armed
bandit (MAB) is a learning framework to decide optimally under uncertainty
[14, 15, 16]. It features $N$ arms with unknown random costs (negative
rewards). At each iteration, one pulls. The problem is to decide on which arm
to pull each time so that the accumulated cost, called regret, after playing
$T$ times is minimized. Our solution is an algorithm that explores the
different arms and, in parallel, it exploits the collected information so far,
where it observes the outcome of playing an arm and uses it to tune its
expected reward estimate to adjust future selections [14, 15]. In our
distributed learning setting, we model the node selection in the RW as arm
pulling in the MAB framework. At each iteration, the random walk picks a node
in graph to activate for the next update, observes the update, and receives
the local gradient as a cost.

Under this analogy, the performance of the learning algorithm is measured by
the regret, which is the difference between the cost of a random walk with
optimal transition matrix when all the distributions are known, and the cost
of the nodes visited by the algorithm.

###  I-B Contribution

In this paragraph, we summarize our contribution as follows:

  * •

In this work, we propose a distributed learning algorithm to learn a model on
the distributed data over the nodes in a graph. Our algorithm selects the
nodes to update the model by an adaptive random walk on the network to address
the statistical heterogeneity of distributed data.

  * •

We model the random walk transition design as a sleeping multi-armed bandit
problem to compete with the optimal transition probabilities that mitigate the
high variance in the local gradients estimates.

  * •

We provide the theoretical guarantee on the rate of convergence of our
proposed algorithm approaching a rate $\mathcal{O}(1/\sqrt{T})$. The rate
depends on the graph spectral property and the minimal gradient variance.

  * •

Finally, we simulate our algorithm on real and synthetic data, for different
graph settings and heterogeneity levels and show that it outperforms existing
baseline random walk designs.

###  I-C Prior Work

Random Walk Learning. Several works have studied random walk learning
algorithms focusing on the convergence under different sets of assumptions.
The works of [17, 11, 18] established theoretical convergence guarantees for
uniform random walks for different convex problem settings and using first-
order methods. Later work [19] employs more advanced stochastic updates based
on gradient tracking technique that uses Hessian information to accelerate
convergence. The work of [20] proposed to speed-up the convergence by using
non-reversible random walks. In [13], the authors studied the convergence of
random walks learning for the alternating direction method of multipliers
(ADMM). In [21], the paper proposes to improve the convergence guarantees by
designing a weighted random walk that accounts for the importance of the local
data to speed up convergence. An asymptotic fundamental bound on the
convergence rate of these algorithms was proven by [22] and it approaches
$O(1/\sqrt{k})$ under convexity and bounded-gradient assumptions. From our MAB
perspective, a common aspect of these algorithms is that they are purely
exploitative. They require a priori information about the local data (e.g.,
gradient-Lipschitz constants, bounds on the gradients) to design a non-
adaptive (time-invariant) random walk.

Random Walk algorithms belong to a more general class of decentralized
learning algorithms where no central entity, such as a PS, is involved to
handle the learning process. Gossip algorithms are another class of
decentralized algorithms that are not based on random walks (see for e.g. [10,
23, 24, 25]). In (synchronous) gossip algorithms, at each round, each node
updates and exchanges its local model with its neighboring nodes. Hence, in
each iteration, all the nodes and all the links in the graph are activated.
The goal of a Gossip algorithm is to ensure that all nodes, and not just the
PS, learn the global model and assume convergence once a consensus is reached.
Hence, it is less efficient in terms of computations and communication costs
[21].

Data Heterogeneity. Recently, there has been lots of work addressing the
problem of data heterogeneity especially in the FL literature. The data across
the nodes is typically not generated in an iid fashion. A local dataset tends
to be more personalized and biased towards its specific owner’s profile.
Therefore, multiple local updates on the global model can drift the global
objective optimization towards its local one. This may slow down the
convergence and can lead to converging to a suboptimal model [26, 9]. Several
measures have been proposed in the literature to quantify statistical
heterogeneity, which refers to this local vs. global objectives’ inconsistency
in the distributed data. The focus has been on quantifying the gap between the
local update direction and the global one [8, 26, 27, 28, 29]. The proposed
solutions vary between controlling the update direction [28] or the learning
objective [26].

Multi-Armed Bandit Sampler.  The multi-armed bandit (MAB) problem aims to
devise optimal sampling strategies by balancing together exploration and
exploitation [14, 15, 30, 16]. Results from MAB have been used in problems
related to standard SGD training in a non-distributed settings [31, 32, 33,
34, 35]. The idea there is to use an MAB sampler to select more often the data
points that can better guide the learning algorithm.

In the classical MAB setting there is no constraint on which node to sample
(visit) at a given time (which arm to pull in the MAB language). However, in
our case, we are restricted by the graph topology, so only neighboring nodes
can be visited. To account for this constraint, we cast our problem as
Sleeping Multi-Armed Bandit in which nodes that are not neighbors of the
current nodes are assumed to be sleeping (not available) at the time of the
sampling. The Sleeping MAB literature has studied various assumptions on
sleeping reliance: independent availabilities, general availabilities, and
adversarial availabilities. The lower bound on the regret is known to be
$\Omega(\sqrt{NT})$ if we consider stochastic independent availabilities. For
a harder sleeping-MAB setting with adversarial availabilities, the lower bound
is $\Omega(N\sqrt{T})$ for $N$ being the total number of nodes and $T$ being
the total number of rounds [36, 30, 37]. In our work, we model the RW design
problem as dependent availabilities Sleeping MAB learning algorithm [37]. For
the proof technicality, we use a harder upper bound on the performance that
assume oblivious adversarial availibilities.

A related line of work is the work on importance sampling which can be thought
of as a pure exploitation scheme with no exploration. The literature has
studied different aspects of importance sampling using prior information on
the local datasets (e.g.,[38, 39, 40, 41]). For instance, in [42], the paper
proposes to sample proportionally to the smoothness bounds of the local
objectives. While the scheme in [38] suggests to select the data points based
on the bounds of the gradients of the local objectives.

###  I-D Organization

The rest of the paper is organized as follows. We present the problem setup in
Section II. In Section III, we present the detailed random walk learning
algorithm. In Section IV, we provide the optimal sampling scheme and its
theoretical motivation. In Section V, we outline the analogy between the RW
design problem and the sleeping MAB problem. In Section VI, we present the MAB
RW learning algorithm and the main theorem on its convergence. Moreover, we
provide the technical definitions and assumptions used into the main theorem
proof in Section VII . Finally, we provide numerical results on the
convergence of our proposed algorithm in Section VIII. The full proofs of the
technical results are deferred to the appendices.

##  II Setup

###  II-A Network Model.

We represent a network of $N$ nodes by an undirected graph
$\mathcal{G}(V,\,E)$ with $V=\\{1,\,...,\,N\\}$ being the set of nodes and $E$
being the set of edges such that $E=\\{(i,j)\in V\times V,\text{ if }i\text{
is connected to }j\\}$. Since the graph is undirected, then $\forall(i,j)\in
E,\text{ we have }(j,i)\in E$. Any two connected nodes $i$ and $j$ are called
neighbor nodes and we denote it by $i\sim j$. Moreover, we assume that all the
nodes have self-loops, thus, $\forall i,\,(i,i)\in E$.

###  II-B Data Model.

We assume that every node $i$ owns a dataset $\mathcal{D}_{i}$ of size $n$
such that
${\mathcal{D}}_{i}=\left\\{\xi_{i,j}:=(x_{i,j},\,y_{i,j})\in\mathbb{R}^{d}\times\mathbb{R}\quad\text{for}\quad
j\in\left[n\right]\right\\}$, which is sampled from an unknown local
distribution $\Pi_{i}$.

###  II-C Learning Objective.

Our goal is to minimize a global objective function $F(w)$ where
$w\in\mathcal{W}\subset\mathbb{R}^{d}$, $\mathcal{W}$ being the feasible set
assumed to be closed and bounded. The objective function $F(.)$ represents the
empirical mean of local losses on the distributed data over the graph of $N$
nodes. Therefore, we are looking to solve the following problem:

$\displaystyle\underset{w\in\mathcal{W}}{\min}\left\\{F(w)\coloneqq\frac{1}{N}\sum_{i=1}^{N}F_{i}\left(w\right)\right\\},$
(1)

where the function $F_{i}$ is the local objective at the node $i$ and it is
defined as

$F_{i}\left(w\right)=\mathbb{E}_{\xi_{i}}\left[F_{i}\left(w;\xi_{i}\right)\right]\text{
for }\,\xi_{i}\sim\Pi_{i}.$ (2)

The optimal model is denoted by $w^{*}$ and defined as follows:

$\displaystyle w^{*}=\underset{w\in\mathcal{W}}{\arg\min\,}F(w).$

###  II-D Data Heterogeneity.

The data distributions across the nodes of the network are assumed to be
arbitrary. Therefore, when a node performs a local update on the global model
it may bias it by its local dataset that may not be a good representative of
the global learning objective. Multiple definitions have been recently
proposed to quantify the degree of local heterogeneity in distributed systems
[26, 29, 9, 27]. These definitions focus on the variance of the local
gradients with respect to the global gradient at a given model $w$. In our
work, we adopt the definition used by [28] as stated below.

######  Definition 1 (Data Heterogeneity).

The local objectives $F_{i}$s are $(\alpha,\sigma)$-locally dissimilar at $w$
if

$\displaystyle\mathbb{E}_{i}\left[\left\|{\nabla}F_{i}\left(w\right)\right\|_{2}^{2}\right]\leq\alpha^{2}+\sigma^{2}\left\|\nabla
F\left(w\right)\right\|_{2}^{2},$

for $\alpha\geq 0$, $\sigma\geq 1$, $\mathbb{E}_{i}$ is the expectation over
the nodes and ${\nabla}F_{i}\left(w\right)$ is the gradient at node $i$. For
$\alpha=0$ and $\sigma=1$, we restore the homogeneous case.

This definition is a generalization of other definitions [26, 29].

###  II-E Model Update.

We focus in our analysis on first-order methods using stochastic gradient
descent111Our work is applicable to any iterative algorithm that uses an
unbiased descent update [43, 44, 45].. Given the limited compute power of the
nodes,

Thus, the model update at round $k$ will be as follows

$\displaystyle
w^{(k+1)}={\bf{\Pi}}_{\mathcal{W}}\left(w^{(k)}-\gamma^{(k)}\frac{1}{p^{(k)}(i^{(k)})}\hat{\nabla}F_{i^{(k)}}\left(w^{(k)}\right)\right),$
(3)

where $\gamma^{(k)}$ is the step size,
$\hat{\nabla}F_{i^{(k)}}\left(w^{(k)}\right)$ is an unbiased estimate of the
local gradient at node $i^{(k)}$ computed on a uniformly sampled data point
from $\mathcal{D}_{i^{(k)}}$, ${p^{(k)}(i^{(k)})}$ is the probability of
picking node $i^{(k)}$ at round $k$, and ${\bf{\Pi}}_{\mathcal{W}}$ is the
projection operator onto the feasible set ${\mathcal{W}}$. For our convergence
analysis, we will need the following technical assumptions.

######  Assumption 1.

For every node $i\in[N]$, the local loss function
$F_{i}(.):\mathcal{W}\rightarrow\mathbb{R}^{d}$ is differentiable and convex
function on the closed bounded domain $\mathcal{W}$.

######  Assumption 2.

The step size $\gamma^{(k)}$ is decreasing and satisfies the following

$\displaystyle{\sum_{k=1}^{\infty}}\gamma^{(k)}=+\infty\,\,\,\,\,\,\,\text{and}\,\,\,\,\,\,\,{\sum_{k=1}^{\infty}}\ln
k.{(\gamma^{(k)})}^{2}<+\infty.$ (4)

######  Assumption 3 (Bounded Gradient).

There exits a constant $D$ such that, $\forall i\in[V]$ and $\forall
w\in\mathcal{W}$, we have $\left\|\nabla F_{i}(w)\right\|^{2}_{2}\leq D.$

The last assumption is actually a result that follows from the functions
$F_{i}$’s being convex on a closed bounded subset
$\mathcal{W}\subset\mathbb{R}$. A complementary proof can be found in [21].

##  III Random Walk Algorithm

Our objective is to design a random walk on the graph $\mathcal{G}$ algorithm
to learn the optimal model $w^{*}$. The algorithm starts uniformly at random
at an initial node in the graph, say $i^{(0)}$, with an initial model
$w^{(0)}$ also sampled uniformly at random from the feasible set
$\mathcal{W}$. Let $i^{(k)}$ be the node visited (active) at the $k^{th}$
round of the algorithm, $k=0,1,\dots,T$. At each round $k$, the active node
$i^{(k)}$ will receive the latest model update $w^{(k)}$ from a neighbor node
$i^{(k-1)}$, that was active at the previous round. Then, the model $w^{(k)}$
is updated via a gradient descent update using data sampled from the local
dataset of node $i^{(k)}$.

The main question we are after is how to design the transition probabilities
defining the random walk, which govern how the RW is sampling the nodes in the
graph. In addition to the explicit objective of learning the model, the random
walk will simultaneously learn information about the heterogeneity of each
node’s data. Therefore, as the random walk progresses, it can adapt with the
information gained on the importance of a given node’s data to speed up the
convergence. For this reason, we allow the transition probabilities of the
random walk to adapt over time (algorithm rounds). We denote by $p^{(k)}(i)$
the probability distribution to select the node $i$ to be active at round $k$.
We denote by $P^{(k)}$ the transition matrix at time $k$. Therefore, we have
$P^{(k)}(i,j)>0$ if $j\sim i$ and $P^{(k)}(i,j)=0$ otherwise. Moreover, we
have $p^{(k)}=p^{(0)}P^{(1)}...P^{(k)}$ and
$p^{(m,k)}=p^{(0)}P^{(m+1)}...P^{(k)}$.

##  IV Node Sampling Strategy

We aim to design a sampling strategy that mitigates the effect of
heterogeneity on the performance of the learning algorithm. Such strategy is
constrained by an environment with two essential properties to consider: 1)
The node sampling is restricted by the topology of the graph where the node to
pick next has to be connected to the current active node; 2) No full
information about the distributed heterogeneous data is available except what
has been learned in the rounds so far and what can be shared among neighbor
nodes.

In our algorithm, each node $i$ is sampled (visited) with probability
$p^{(k)}(i)$ at round $k$. And the gradient is computed on one data point
sampled uniformly among the $n$ local data points at the visited node. A
crucial quantity for our analysis is the second moment of the unbiased
gradient estimate at round $k$ which is is

$\displaystyle\mathbb{E}\left[\left\|\hat{\nabla}F_{i^{(k)}}\left(w^{(k)}\right)\right\|_{2}^{2}\right]$
$\displaystyle=\underset{i\in[N]}{\sum}\frac{1}{p^{(k)}\left(i\right)}\sum_{j=1}^{n}\frac{1}{n^{2}}\left\|\nabla
F_{i}\left(w^{(k)};\xi_{i,j}\right)\right\|_{2}^{2}.$ (5)

This quantity affects the convergence rate of the Random Walk SGD algorithm as
we show in equation (6) (see the Appendix for the details)

$\displaystyle\mathcal{O}\left(\left(\sum_{k=1}^{T}\gamma^{(k)}\right)^{-1}\sum_{k=1}^{T}\mathbb{E}\left[\left\|\hat{\nabla}F_{i^{(k)}}\left(w^{(k)}\right)\right\|_{2}^{2}\right]\right).$
(6)

Thus, the second moment of the gradients’ updates imposes a burden on the
convergence, especially in heterogeneous data settings where the diversity of
the gradients is high. This dependence on the second moment is a common
property of SGD based algorithms and has been well studied in the literature.
Variance reduction techniques via importance sampling have been proposed to
improve the convergence guarantees [42, 38, 39, 46, 41].

Our goal is to design the node sampling strategy to approach the optimal
probability that minimizes the convergence bound [38, 42, 39] given by

$\displaystyle p^{(k)}(i)\propto\sqrt{g^{(k)}_{i}\left(w^{(k)}\right)},\text{
such that }$ $\displaystyle
g^{(k)}_{i}\left(w^{(k)}\right)\coloneqq\sum_{\xi_{i,j}\in\mathcal{D}_{i}}\frac{1}{n^{2}}\left\|\nabla
F_{i}\left(w^{(k)};\xi_{i,j}\right)\right\|_{2}^{2}.$

Note that computing the $g^{(k)}_{i}$’s is very costly since it requires
computing the gradients related to all the data points owned by the node and
its neighbors. Moreover, the $g^{(k)}_{i}$’s need to be re-computed at the new
model $w^{(k)}$ at each iteration. Instead, we propose to estimate in each
iteration the $g^{(k)}_{i}$’s using the already computed gradients for the
update step in (3). Therefore, at each iteration, the random walk has a
double-fold objective: (i) update the model in each iteration and (ii) refine
the estimates of the $g_{i}^{(k)}$’s by adjusting the RW level of exploitation
vs. exploration using tools from the theory of sleeping multi-armed bandit.

##  V Sleeping Bandit for RW Node Sampling

The multi-armed bandit (MAB) problem [47, 16] is a decision framework that
features a set of $N$ arms, where each arm $i\in[N]$ has an unknown cost
$c^{(k)}(i)$ at round $k$. A player selects a sequence of arms
$i^{(0)},\,i^{(1)},...$ up to the final round $T$ (also called called horizon)
of the algorithm. The goal is to design an arm selection strategy to minimize
the accumulated regret $R(T)$ over the total number of rounds $T$:

$\displaystyle\text{R}\left(T\right)=\sum_{k=1}^{T}\left(\mathbb{E}\left[c^{(k)}\left(i^{(k)}\right)\right]-\underset{i\in[N]}{\min}\,\mathbb{E}\left[c^{(k)}\left(i\right)\right]\right).$
(7)

The first term in the regret,
$\mathbb{E}\left[c^{(k)}\left(i^{(k)}\right)\right]$, is the average cost of
the arm selected by the player. The second term,
$\underset{i\in[N]}{\min}\,\mathbb{E}\left[c^{(k)}\left(i\right)\right]$, is
the “best” arm with the minimum cost that could have been selected were the
costs known. The expectation is taken over the selection strategy and the cost
randomness.

Our work is based on establishing an analogy between MAB and RW. This allows
us to use results from the vast literature on MAB to design the RW in order to
speed up the learning process. To that end, we think of each node as an arm,
and visiting a node in the RW as selecting an arm in the MAB problem. What is
not clear in this analogy is what the cost of visiting a node and updating the
model is. Based on the discussion in section IV and the the upper bound in
(6), minimizing the accumulated variance of the gradient serves to tighten the
convergence guarantees. Thus, we propose the cost of visiting a node $i$, at a
given round $k$ in our Random Walk algorithm, to be:

$\displaystyle
c^{(k)}(i)=\sum_{\xi_{i,j}\in\mathcal{D}_{i}}\frac{1}{n^{2}}\left\|\nabla
F_{i}\left(w^{(k)};\xi_{i,j}\right)\right\|_{2}^{2}.$ (8)

MAB |  RW Learning on Graph
---|---
Arm |  Node
Action |  Select the next node in the RW
Cost |  Variance of the local gradient at the selected node as shown in (8)
Regret |  Gap between the accumulated variance and the minimal variance under the optimal transition probabilities in full information setting as shown in (9)
TABLE I: Our proposed Analogy between the sleeping MAB and the Random Walk
design problems.

However, this analogy between “standard” MAB and RW cannot be fully
established here. That is because in MAB any arm can be selected at any time.
Whereas in RW only neighboring nodes can be visited in each iteration. To take
into account the graph topology, we consider a variant of the standard MAB
called sleeping MAB, where in each iteration only a subset or arms is
available (the rest are sleeping)[36, 30, 37]. Moreover, the available nodes
to select from are the ones that are connected to the currently visited node.
In Table I, we summarise this analogy between MAB and RW.

Within this sleeping multi-armed bandit framework, our goal is to minimize the
regret given the available arms and approach the best node sampling strategy
denoted by $\pi:2^{[N]}\rightarrow[N]$, which is a mapping from a set of
available arms $\mathcal{N}^{(k)}$ to a selected arm. The goal is to minimize
the following regret

$\displaystyle\text{R}\left(T\right)=$ (9)
$\displaystyle\sum_{k=1}^{T}\left(\mathbb{E}\left[c^{(k)}\left(i^{(k)}\right)\right]-\min_{\pi}\sum_{k=1}^{T}\mathbb{E}\left[c^{(k)}\left(\pi\left(\mathcal{N}^{(k)}\right)\right)\right]\right),$

where the cost $c^{(k)}$ is defined in (8), the expectation is taken w.r.t.
the availabilities and the randomness of the player’s strategy, and
$\mathcal{N}^{(k)}$ is the set of available nodes at time $k$ which consists
of the neighbors of the currently visited node. Therefore, the regret function
is defined as the gap between the local variance of the local gradient
estimate implied by the our selection strategy and the minimal variance that
requires full information about the local datasets.

In [36, 30, 16], it was shown that one can achieve a sublinear regret
$\mathcal{O}(\sqrt{T})$ for sleeping MAB and it is asymptotically optimal.
This is achieved by applying the EXP3 algorithm. Initially, the algorithm
assigns equal importance to all arms. Then, at every round, the player
receives the subset of non-sleeping arms, selects one among them, and observes
the outcome of the chosen arm. The player then updates its cost estimation and
keeps track of the empirical probability of the appearance of a given arm in
the non-sleeping set. The goal of the player is to balance between exploration
and exploitation and gradually shifts to exploitation as the costs estimates
become more robust after playing enough rounds.

The multi-armed bandit modeling implies an algorithm design on the random walk
that guarantees a sublinear decaying of the regret in (9) such that
$\lim_{T\rightarrow\infty}\frac{\text{Regret}\left(T\right)}{T}=0$, thus, it
approaches asymptotically the optimal transition scheme of the random walk.

##  VI Main Results

Algorithm 1 Sleeping MAB Random Walk SGD

1: Input: Exploration parameter $\lambda^{(k)}$. Learning parameter
$\eta=\sqrt{\frac{\log N}{NT}}$. Horizon T. Graph $\mathcal{G}(E,V)$.

2: Initialization: Initial control weight $q^{(0)}(i)=1$ $\forall i\in[N]$,
Initial model $w^{(0)}$ chosen uniformly at random from $\mathcal{W}$. Starter
node $i^{(0)}$ chosen uniformly at random from $[N]$.

3: for $k=1$ to $T$ do

4: Compute
$P^{(k)}(i^{(k-1)},i)\propto{q^{\left(k-1\right)}\left(i\right)}\quad\forall
i\in\mathcal{N}\left(i^{\left(k-1\right)}\right)$ and $P^{(k)}(i^{(k-1)},i)=0$
otherwise.

5: Choose a neighbor node $i^{(k)}\sim P^{(k)}(i^{(k-1)},\,.)$.

6: Choose $\xi_{i,j}$ uniformly at random from $\mathcal{D}_{i^{(k)}}$ and
compute $\hat{\nabla}F_{i^{(k)}}\left(w^{(k)}\right)$.

7: Compute the cost estimate $c^{(k)}_{i}$.

8: Update the model using the SGD update in (3).

9: Update the control weight $q^{(k)}(i^{(k)})$ using (10).

10: end for

In this section, we summarize our main technical results. First, we present
the details of our Sleeping Multi-Armed Bandit Random Walk SGD algorithm in
Algorithm 1. Second, we prove in Theorem 1 that the proposed algorithm has an
asymptotically optimal convergence rate.

###  VI-A Algorithm

Algorithm 1 leverages the analogy between Sleeping MAB and RW that we
established in the previous section to design the RW learning algorithm. In
the literature of Sleeping MAB [37], there are two versions of the EXP3
algorithm based on the availabilities of the arms: dependent versus
independent availabilities. The case with dependent availabilities fits our RW
model since the graph structure dictates the joint availability of any set of
nodes.

In Algorithm 1, each node $i$ keeps an accumulated control (importance) value
$q^{(k)}(i)$ of the observed cost up to round $k$. The nodes with higher
values will be favored in the selection.

In each round of the algorithm, the active node has to make a decision to
select a neighboring node to carry the next update. In order to do that, the
active node receives the control value from each neighboring node, and does
the selection proportionally to the control values
$q^{\left(k-1\right)}\left(i\right)$.

The selection starts with pure exploration using uniform control values and
keeps refining it with time given the observed average cost. The selected node
will turn active, samples one of its local data point uniformly at random,
performs the update in (3) and computes the cost estimate based on the local
gradient.

Each node $i$ keeps tracks of the empirical estimate
$\bar{P}^{(k)}(i)=\frac{1}{k}\sum_{t=1}^{k}\left(P^{(t)}(i^{(t-1)},i)\right)$.
The exploration is implicitly adjusted by a decreasing exploration parameter
$\lambda^{(k)}=\sqrt{\frac{2^{N+2}}{k}\ln\left(T\right)}+\frac{2^{N+2}}{3k}\ln\left(T\right)$.
At early stage of the training $\lambda^{(k)}$ gives less importance to the
observed cost contribution. Lastly the control value is updated as follows

$\displaystyle
q^{\left(k\right)}\left(i^{(k)}\right)=q^{\left(k-1\right)}\left(i^{(k)}\right)\exp\left(-\eta\frac{c_{i}^{(k)}\left(i^{(k)}\right)}{\bar{P}^{\left(k\right)}\left(i^{(k)}\right)+\lambda^{\left(k\right)}}\right).$
(10)

###  VI-B Convergence Guarantees

######  Theorem 1.

Under assumptions 1, 2 and 3, for a connected graph $\mathcal{G}$,
particularly for $\gamma^{(k)}=\frac{1}{k^{q}}$ for $\frac{1}{2}<q<1$, the
convergence rate of Algorithm 1 is as follows:

$\displaystyle\mathbb{E}\left[F\left(\bar{w}^{(T)}\right)-F\left(w^{*}\right)\right]\leq\frac{\frac{c.D^{2}}{\ln\left(1/\mu_{\mathcal{G}}\right)}+N.E+\frac{1}{2}R+3C^{*}}{T^{1-q}},$

where,

$\displaystyle\bar{w}^{(T)}=\frac{\sum_{k=1}^{T}\gamma^{(k)}w^{(k)}}{\sum_{t=1}^{T}\gamma^{(t)}},$
$\displaystyle\,C^{*}=\min_{p}\sum_{k=1}^{T}\mathbb{E}_{p}\left[c^{(k)}(i)\right],$
$\displaystyle R=\frac{1}{2}\left\|w^{\left(0\right)}-w^{*}\right\|_{2}^{2},$
$\displaystyle\text{ and
}E=\sum_{k=1}^{T}\gamma^{\left(k\right)}\left(\frac{1}{2k}+\frac{1}{\sqrt{k}}\right).$

Moreover, $c$ is a constant function of the convexity constants and the step
size and $\mu_{\mathcal{G}}$ is the spectral norm of the transition matrix
defined in Section VII.

The first order contribution of Theorem 1 is to characterize the convergence
rate approaching $\mathcal{O}(\frac{1}{\sqrt{T}})$ of our proposed bandit
random walk SGD algorithm. This proves its asymptotic optimality given the
lower bound $\mathcal{O}(\frac{1}{\sqrt{T}})$ in [48]. To better understand
its significance, one must compare it with other first-order random walk
algorithms, such as uniform node sampling. For all these algorithms, one can
get a similar bound as in Theorem 1 with the same constants (depending on the
data and graph topology, etc.). The only difference would be in the constant
$C^{*}$ which is the cumulated variance of the gradients corresponding to the
optimal sampling strategy $p^{*}$. Any other node sampling strategy $p$ will
lead to a higher constant $C$ and a looser bound. Of course, here we are
optimizing the upper bound which we are taking as a proxy for the actual
performance. Our numerical results in Section VIII substantiate our
theoretical conclusions and show that our proposed algorithm outperform other
baselines.

##  VII Proof Outline

We outline here the different steps needed to establish the result in Theorem
1. The details can be found in the Appendix. First, we state the results on
the regret rate of the sleeping multi-armed bandit selection scheme used in
Algorithm 1. Furthermore, we show that the multi-armed bandit random walk is
strongly ergodic which is an essential assumption for the convergence of our
algorithm.

######  Lemma 2 (Regret Rate of Sleeping Multi-Armed Bandit Sampler).

Let $C^{*}=\min_{p}\sum_{k=1}^{T}\mathbb{E}\left[c^{(k)}(i)\right]$ is the
minimal cost if the optimal transition scheme is known. Under algorithm 1, The
multi-armed bandit sleeping algorithm approximates the optimal cost
asymptotically as follows

$\displaystyle\lim_{T\rightarrow\infty}\frac{1}{T}\left(\sum_{k=1}^{T}\mathbb{E}\left[c^{(k)}(i^{(k)})\right]-3C^{*}\right)\leq
0,$

The proof follows the multiplicative weight approach for EXP3 algorithms
introduced in [15].

Next, we state the definition on Strongly Ergodic Non-Homogeneous Random Walk
[49]. The sleeping multi-armed bandit algorithm guarantees that this property
applies on the sequence of employed transition, which in the end guarantees
the convergence stated in Theorem 1.

######  Definition 2 (Strongly Ergodic Non-Homogeneous Random Walk [49]).

A non-homogeneous random walk, with uniform starting distribution $p^{(0)}$,
is called strongly ergodic if there exists a vector $p^{*}$ such that for all
$m\geq 0$,

$\lim_{k\rightarrow\infty}\left\|p^{(m,k)}-p^{*}\right\|=0.$

Lastly, we present the result on the rate of convergence of the transition
probability distribution.

######  Proposition 3 (Convergence Non-Homogeneous Strongly Ergodic Random
Walk).

The non-homogeneous random walk in Algorithm 1 is strongly ergodic. Thus, it
exists a stochastic matrix $P$ such that
$\lim_{k\rightarrow\infty}\left\|P^{(k)}-P\right\|=0$. Moreover, it exists a
stochastic matrix $Q$ such that $\left\|P^{k}-Q\right\|\leq c\beta_{2}^{k}$,
where $\beta_{1}=1>\beta_{2}\geq...\geq\beta_{N}$ are the eigenvalues of the
matrix $P$. Moreover, it exists a function $g(k)=\mathcal{O}(\sqrt{k})$ such
that

$\lim_{k\rightarrow\infty}\min{\left\\{1/\mu_{\mathcal{G}}^{k},\>g\left(k\right)\right\\}}\left\|P^{(0,\,k)}-Q\right\|=0,$
where $1<1/\mu_{\mathcal{G}}<\sqrt{1/\beta_{2}}.$

##  VIII Simulations

In this section, we present the numerical performance of our proposed Multi-
Armed Bandit Random Walk (RW) SGD algorithm described in Algorithm 1.

###  VIII-A Baseline Algorithms

We compare the performance of our algorithm to three baselines, namely: (1)
Uniform Random Walk, (2) Static Weighted Random Walk, and (3) Adaptive
Weighted Random Walk.

#### The Uniform Random Walk

This algorithm assigns equal importance to all nodes in the network [17]
imitating uniform sampling in centralized SGD. We implement the Metropolis
Hasting (MH) decision rule to design the transition probabilities, so the
random walk converges to a uniform stationary. The MH rule can be described as
follows:

  1. 1.

At the $k^{th}$ step of the random walk, the active node $i^{(k)}$ selects
uniformly at random one of its neighbors, say $j$, as a candidate to be the
next active node. This selection gets accepted with probability

$\displaystyle
a_{u}\left(i^{(k)},\,j\right)=\min\left(1,\,\frac{\deg\left(i^{(k)}\right)}{\deg\left(j\right)}\right).$

Upon the acceptance, we have $i^{(k+1)}=j$.

  2. 2.

Otherwise, if the candidate node gets rejected, the random walk stays at the
same node, i.e., $i^{(k+1)}=i^{(k)}$.

#### Static Weighted Random Walk

This algorithm assigns a static importance metric to each node that is
proportional to the gradient-Lipschitz constant of the local loss function
[50, 42]. The random walk is designed by the MH again with a stationary
distribution that is proportional to the local gradient-Lipschitz constants.
In order to achieve that stationary, the probability of acceptance looks as
follows:

$\displaystyle
a_{w}\left(i^{(k)},\,j\right)=\min\left(1,\,\frac{L_{j}}{L_{i^{(k)}}}\frac{\deg\left(i^{(k)}\right)}{\deg\left(j\right)}\right).$
(11)

#### Adaptive Weighted Random Walk

In this algorithm, we adapted the importance sampling scheme that is used in
[38, 40] for centralized settings. The importance is computed for each node
$i$ as the average of of gradients computed so far at that node which is at
time $k$,
$\frac{\sum_{t=1:i^{(t)}=i}^{k}\left\|\hat{\nabla}F_{i}\left(w^{(t)}\right)\right\|_{2}^{2}}{n_{i,k}}$,
for $n_{i,k}$ is the total number of rounds when node $i$ has been active up
to $k$. We call it the pure Exploitation scheme.

###  VIII-B Datasets and Comparison

Our simulations are run on both synthetic dataset and on real benchmarks to
confirm our theoretical results. They show that a bandit based random walk in
decentralized learning consistently outperforms existing random walk baselines
that uses static or exploitation based importance estimation.

Synthetic Data. For each node $i$, we sample the dataset $\mathcal{D}_{i}$
from a a normal distribution with
$\mathcal{N}\left([\mu_{i,1},\mu_{i,2}],\sigma\mathbb{I}_{2}\right)$. We
assigned manually a label to each node dataset such that half the nodes has
the label $y_{i}=1$ and the other half has the $y_{i}=-1$. We run our
simulations on an Expander graph which known to be sparse (The Margulis-
Gabber-Galil graph). 222We call the generator function of the Python library
NetworkX v2.8 [51]. .

MNIST dataset and Fashion-MNIST. We run experiments on the MNIST dataset and
the Fashion-MNIST to train a multi-class logistic regression model. We divide
the data among the nodes as follows: for a level $s\%$ of similarity, each
client has $s\%$ of its local dataset drawn i.i.d. from a shared pool of data.
Another non-public pool of the data is sorted with respect to label and
partitioned into non-overlapping chunks. Each node is assigned a different
chunk that consists of its remaining $\left(100-s\right)\%$ data [28].

Table II and Table III report the results for different level of similarity
from fully homogeneous to fully heterogeneous to highlight how different
similarity levels affect the convergence of our algorithm vs. the oblivious
uniform algorithm. Table II is on the MNIST dataset. The gap between both
algorithms becomes wider once the system turns more heterogeneous. Table III
is on the Fashion-MNIST dataset. The gap between both algorithms becomes more
significant as the system turns into more heterogeneous state 333The fact that
the ratio between the number of iterations of the two algorithms is constant
(roughly 2) is an artifact of the data and is not reproducible for other
datasets. See for example Table III which is on the Fashion-MNIST dataset that
shows an increasing ratio with decreasing similarity. .

Figure 3:  Classification model trained on a Synthetic dataset distributed over an Expander graph of $100$ nodes. Figure 4: Classification model trained on the Synthetic dataset. The same dataset is been distributed over a Expander graph of size $100$ nodes and $200$ nodes. Figure 5: Classification model trained on the Synthetic dataset. The local dataset size has been augmented from $20$ to $200$ in a Expander graph of size $100$. Figure 6: Multi-class MNIST dataset of 10 classes distributed over $100$ nodes with $0\%$ similarity on Expander graph.  Similarity | $0\%$ | $10\%$ | $100\%$
---|---|---|---
Uniform RW SGD | $202$ | $87$ | $61$
Bandit RW SGD | $138$ | $44$ | $34$
TABLE II: Number of rounds to reach 0.45 test accuracy for logistic regression on MNIST as we vary the level of similarity. Bandit RW SGD is consistently faster than Uniform RW SGD. Similarity | $0\%$ | 10% | $100\%$
---|---|---|---
Uniform RW SGD | $124$ | 90 | $66$
Bandit RW SGD | $82$ | 69 | $54$
TABLE III: Number of rounds to reach 0.45 test accuracy for logistic regression on FMNIST as we vary the level of similarity. Bandit RW SGD is consistently faster than Uniform RW SGD. Probability of Connectivity | $0.1$ | $0.5$ | $0.8$
---|---|---|---
Uniform RW SGD | $202$ | $128$ | $94$
Bandit RW SGD | $138$ | $103$ | $90$
TABLE IV: Number of rounds to reach 0.45 test accuracy for logistic regression
on MNIST as we vary the graph connectivity parameter. Bandit RW SGD is
consistently faster than Uniform RW SGD. As we decrease the probability of
connectivity, the increase in the number of rounds is less significant for the
bandit algorithm.

To elaborate on how our algorithm performs given the graph structure, we
consider multiple scenarios of simulations where we use an Erdos-Renyi with
different probabilities of connectivity that go from sparser to denser. Table
IV measures the performance given the probability of connectivity in the
graph.

Optimal Sampling. Here is a sketched proof on the optimal sampling. Consider
the optimization problem in hand which can be formulated as follows:

$\displaystyle\min\underset{i\in[N]}{\sum}\frac{g_{i}^{(k)}\left(w^{(k)}\right)}{p^{(k)}\left(i\right)},$
$\displaystyle\text{such
that$\quad$}{p^{(k)}\left(i\right)}\in(0,\,1)\,\forall\,i,\text{ and
}\sum_{i}{p^{(k)}\left(i\right)}=1.$

The optimality conditions of the Lagrangian expression of the problem above
gives the following:

$\displaystyle-\frac{g_{i}^{(k)}\left(w^{(k)}\right)}{(p^{(k)}\left(i\right))^{2}}+\eta=0\text{
and }\sum_{i}{p^{(k)}\left(i\right)}=1,$

where $\eta$ is the Lagrange multiplier. Thus, by a simple algebraic
manipulation, we get
$p^{(k)}\left(i\right)=\frac{\sqrt{g_{i}^{(k)}\left(w^{(k)}\right)}}{\sum_{j}\sqrt{g_{j}^{(k)}\left(w^{(k)}\right)}}.$

######  Definition 3.

The local loss function $F_{i}$ for each node $i\in V$ has an
$L_{i}$-Lipschitz continuous gradient; that is, any $w$,
$w^{\prime}\in\mathcal{W}$, there exists a constant $L_{i}>0$ such that

$\displaystyle\left\|\nabla f_{i}\left(w\right)-\nabla
f_{i}\left(w^{\prime}\right)\right\|_{2}\leq
L_{i}\left\|w-w^{\prime}\right\|_{2}.$

######  Lemma 4.

Under assumptions 1, 2 and 3, the Random Walk SGD algorithm, that uses the
update in equation 3 for transition matrix $P$, has the following rate of
convergence.

$\displaystyle\mathbb{E}\left[F\left(w^{(T)}\right)-F\left(w^{*}\right)\right]$
$\displaystyle\qquad\leq\mathcal{O}\left(\left(\sum_{k=1}^{T}\gamma^{(k)}\right)^{-1}\sum_{k=1}^{T}\mathbb{E}\left[\left\|\hat{\nabla}F_{i^{(k)}}\left(w^{(k)}\right)\right\|_{2}^{2}\right]\right).$

In order to prove Lemma 4 and Theorem 1, we present some technical results
that we use in the proof. The proof techniques are essentially inspired by the
work of [21] and theya are adapted to the assumptions and setting of this
work.

######  Lemma 5 (Convexity and Lipschitzness).

If $F_{i}$ is a convex function on an open subset $\Omega\subseteq\mathbb{R}$,
then for a closed bounded subset $\mathcal{W}\subset\Omega$, there exists a
constant $D_{i}\geq 0$, such that, for any $w_{1},\,w_{2}\in\mathcal{W}$,

$\displaystyle\left|F_{i}\left(w_{1}\right)-F_{i}\left(w_{2}\right)\right|\leq
D_{i}\left\|w_{1}-w_{2}\right\|_{2}.$

We define $D=\underset{i\in V}{\sup}D_{i}$. Therefore,

$\left|F_{i}\left(w_{1}\right)-F_{i}\left(w_{2}\right)\right|\leq
D\left\|w_{1}-w_{2}\right\|_{2}.$

A proof for Lemma 5 can be found in [52].

######  Corollary 1 (Boundedness of the gradient).

If $F_{i}$ is a convex function on $\mathbb{R}$, then for a closed bounded
subset $\mathcal{W}\subset\mathbb{R}$, $\left\|\nabla F_{i}(w)\right\|_{2}\leq
D,\,\,\,\,\,\forall w\in\mathcal{W}.$

###### Proof.

Taking $v=w+\nabla F_{i}(w)$,

$\displaystyle D\left\|\nabla F_{i}(w)\right\|_{2}$
$\displaystyle=D\left\|v-w\right\|_{2}$
$\displaystyle\overset{(a)}{\geq}|F_{i}(v)-F_{i}(w)|$
$\displaystyle\overset{(b)}{\geq}\left\langle\nabla F_{i}\left(w\right),\nabla
F_{i}\left(w\right)\right\rangle$ $\displaystyle=\left\|\nabla
F_{i}(w)\right\|_{2}^{2}.$

(a) follows Lemma 5 and (b) follows from $F_{i}$ being convex. ∎

Now, we present the steps of the the proof:

$\displaystyle\left\|w^{(k+1)}-w^{*}\right\|_{2}^{2}$
$\displaystyle\quad=\left\|{\bf{\bf{\Pi}}_{\mathcal{W}}}\left(w^{(k)}-\gamma^{(k)}\hat{\nabla}{F}_{i^{(k)}}\left(w^{(k)}\right)\right)-{\bf{\bf{\Pi}}_{\mathcal{W}}}F\left(w^{*}\right)\right\|_{2}^{2}$
$\displaystyle\quad\overset{\left(a\right)}{\leq}\left\|w^{(k)}-\gamma^{(k)}\hat{\nabla}{F}_{i^{(k)}}\left(w^{(k)}\right)-w^{*}\right\|_{2}^{2}$
$\displaystyle\quad=\left\|w^{(k)}-w^{*}\right\|_{2}^{2}-2\gamma^{(k)}\left\langle
w^{(k)}-w^{*},\hat{\nabla}{F}_{i^{(k)}}\left(w^{(k)}\right)\right\rangle$
$\displaystyle\quad\,\,\,\,\,+\left(\gamma^{(k)}\right){}^{2}\left\|\hat{\nabla}{F}_{i^{(k)}}\left(w^{(k)}\right)\right\|_{2}^{2}$

$\left(a\right)$ follows from $\mathcal{W}$ being a convex closed set, so one
can apply nonexpansivity theorem in [52].

For the next we use the convexity of $F_{i}$,

$\displaystyle\left\|w^{(k+1)}-w^{*}\right\|_{2}^{2}$
$\displaystyle\leq\left\|w^{(k)}-w^{*}\right\|_{2}^{2}$ (12)
$\displaystyle\quad-2\gamma^{(k)}\left(F_{i^{(k)}}\left(w^{(k)}\right)-F_{i^{(k)}}\left(w^{*}\right)\right)$
$\displaystyle\quad+{(\gamma^{(k)})}\left\|\hat{\nabla}F_{i^{(k)}}\left(w^{(k)}\right)\right\|_{2}^{2}.$

Re-arranging the above equation gives

$\displaystyle\gamma^{(k)}$
$\displaystyle\left(F_{i^{(k)}}\left(w^{(k)}\right)-F_{i^{(k)}}\left(w^{*}\right)\right)$
$\displaystyle\leq\frac{1}{2}\left(\left\|w^{(k)}-w^{*}\right\|_{2}^{2}-\left\|w^{(k+1)}-w^{*}\right\|_{2}^{2}\right)$
$\displaystyle\quad+\frac{{(\gamma^{(k)})}^{2}}{2}\left\|\hat{\nabla}F_{i^{(k)}}\left(w^{(k)}\right)\right\|_{2}^{2}.$
(13)

Summing (13) over $k$ and using Assumption and the boundness of $\mathcal{W}$,

$\displaystyle{\sum}_{k}\gamma^{(k)}\left(F_{i^{(k)}}\left(w^{(k)}\right)-F_{i^{(k)}}\left(w^{*}\right)\right)$
$\displaystyle\quad\leq\frac{1}{2}\left\|w^{(0)}-w^{*}\right\|_{2}^{2}+{\sum}_{k}{(\gamma^{(k)})}^{2}\left\|\nabla
F_{i^{(k)}}\left(w^{(k)}\right)\right\|_{2}^{2}.$ (14)

Next we give some results we need on the Markov chain. We denote by $\mu$ the
stationary distribution, $P$ is the transition matrix and $P^{k}$ is the
$k^{th}$ power of matrix P. We refer to $i^{th}$ row of a matrix $P$ by
$P(i,:)$.

######  Lemma 6 (Convergence of Markov Chain [53]).

Assume the graph $\mathcal{G}$ is connected with self-loop, therefore a random
walk is aperiodic and irreducible, we have

$\displaystyle\underset{i}{\max}\left\|\mu-P^{k}\left(i,:\right)\right\|\leq
C\lambda_{P}^{(k)}$

for $k>K_{p}$, where $K_{P}$ is a constant that depends and $\lambda_{P}$ and
$\lambda_{2}(P)$ and $C$ is a constant that depends on the Jordan canonical
form of $P$.

######  Corollary 2.

Using the previous lemma, we get

$\displaystyle\underset{i}{\max}\left\|\mu-P^{T_{k}}\left(i,:\right)\right\|\leq
C\lambda_{P}^{T_{k}}\leq\frac{1}{2k}$

for
$T^{(k)}=\min\\{k,\max\\{\frac{\ln({2Ck})}{\ln({1/\lambda_{P}})},K_{P}\\}\\}.$

Here, we state the next corollary on the convergence of the random walk.

$\displaystyle\gamma^{(k)}\mathbb{E}\left[F_{j^{(k)}}\left(w^{\left(k-T^{\left(k\right)}\right)}\right)-F_{j^{(k)}}\left(w^{(k)}\right)\right]$
$\displaystyle\quad\overset{(a)}{\leq}D\gamma^{(k)}\mathbb{E}\left\|w^{\left(k-T^{\left(k\right)}\right)}-w^{(k)}\right\|$
$\displaystyle\quad\overset{(b)}{\leq}D\gamma^{(k)}\mathbb{E}\left(\sum_{n=k-T^{\left(k\right)}}^{k-1}\left\|w^{\left(n+1\right)}-w^{\left(n\right)}\right\|\right)$
$\displaystyle\quad\overset{(c)}{\leq}D\gamma^{(k)}\sum_{n=k-T^{\left(k\right)}}^{k-1}\mathbb{E}\left(\left\|w^{\left(n+1\right)}-w^{\left(n\right)}\right\|\right)$
$\displaystyle\quad\overset{(d)}{\leq}D^{2}\gamma^{(k)}\sum_{n=k-T^{\left(k\right)}}^{k-1}\gamma^{\left(n\right)}$
$\displaystyle\quad\overset{(e)}{\leq}\frac{D^{2}}{2}\sum_{n=k-T^{\left(k\right)}}^{k-1}\left({(\gamma^{\left(n\right)})}^{2}+{(\gamma^{\left(k\right)})}^{2}\right)$
$\displaystyle\quad\overset{}{\leq}\frac{D^{2}}{2}T^{\left(k\right)}{(\gamma^{\left(k\right)})}^{2}+\frac{D^{2}}{2}\sum_{n=k-T_{k}}^{k-1}{(\gamma^{\left(n\right)})}^{2}.$

(a) follows from Lemma 5, (b) using triangle inequality, (c) using linearity
of expectation and (d) follows from the Cauchy–Schwarz inequality.

Now taking the summation over $k$:

$\displaystyle\sum_{k}\gamma^{(k)}\mathbb{E}\left[F_{j^{(k)}}\left(w^{(k-T^{(k)})}\right)-F_{j^{(k)}}\left(w^{(k)}\right)\right]$
$\displaystyle\leq\sum_{k}\frac{D^{2}}{2}T_{k}{(\gamma^{(k)})}^{2}+\frac{D^{2}}{2}\sum_{k}\sum_{n=k-T_{k}}^{k-1}{(\gamma^{(n)})}^{2}.$
(15)

By simply using the assumption on the step size summability, the result is as
follows:

$\displaystyle\sum_{k=K}^{\infty}\sum_{n=k-T^{(k)}}^{k-1}\left(\gamma^{\left(n\right)}\right)^{2}$
$\displaystyle\leq\sum_{k=K}^{\infty}T^{\left(k\right)}\left(\gamma^{(k)}\right)^{2}$
$\displaystyle\leq\frac{2}{\ln\left(1/\lambda_{P}\right)}\sum_{k=K}^{\infty}\ln
k.\left(\gamma^{(k)}\right)^{2}$ $\displaystyle<\infty.$ (16)

Now, we compute the following lower bound:

$\displaystyle\mathbb{E}_{j^{(k)}}\left[F_{j^{(k)}}\left(w^{(k-T^{\left(k\right)})}\right)-F_{j^{(k)}}\left(w^{*}\right)|\,X_{0},\,X_{1},\,...,\,X_{k-T^{\left(k\right)}}\right]$
$\displaystyle\overset{}{=}\sum_{i=1}^{N}\left(F_{i}\left(w^{(k-T^{\left(k\right)})}\right)-F_{i}\left(w^{*}\right)\right)P\left(j^{(k)}=i\,|\,X_{0},\,X_{1},\,...,\,X_{k-T^{\left(k\right)}}\right)$
$\displaystyle\overset{(a)}{=}\sum_{i=1}^{N}\left(F_{i}\left(w^{(k-T^{\left(k\right)})}\right)-F_{i}\left(w^{*}\right)\right)P\left(j^{(k)}=i\,|\,X_{k-T^{\left(k\right)}}\right)$
$\displaystyle\overset{}{=}\sum_{i=1}^{N}\left(F_{i}\left(w^{(k-T^{\left(k\right)})}\right)-F_{i}\left(w^{*}\right)\right)P^{T^{(k)}}\left[X_{k-T^{\left(k\right)}}\,|\,j^{(k)}=i\right]$
$\displaystyle\overset{(b)}{\geq}\left(F\left(w^{(k-T^{\left(k\right)})}\right)-F\left(w^{*}\right)\right)-\frac{N}{2k}.$
(17)

(a) using Markov property and (b) using Lemma 1 in [20].

Therefore,

$\displaystyle F\left(w^{(k-T^{\left(k\right)})}\right)-F\left(w^{*}\right)$
$\displaystyle\leq\frac{N}{2k}+\mathbb{E}_{j^{(k)}}\left[F_{j^{(k)}}\left(w^{(k-T^{\left(k\right)})}\right)-F_{j^{(k)}}\left(w^{*}\right)|\,X_{0},\,...,\,X_{k-T^{\left(k\right)}}\right]$

$\displaystyle\gamma^{\left(k\right)}\mathbb{E}\left[F\left(w^{(k-T^{\left(k\right)})}\right)-F\left(w^{*}\right)\right]$
$\displaystyle\leq\frac{N\gamma^{\left(k\right)}}{2k}+\gamma^{(k)}\mathbb{E}\left[F_{j^{(k)}}\left(w^{\left(k-T^{\left(k\right)}\right)}\right)-F_{j^{(k)}}\left(w^{*)}\right)\right]$

$\displaystyle\sum_{k}\gamma^{\left(k\right)}\mathbb{E}\left[F\left(w^{(k-T^{\left(k\right)})}\right)-F\left(w^{*}\right)\right]$
$\displaystyle\leq\sum_{k}\frac{N\gamma^{\left(k\right)}}{2k}$
$\displaystyle+\sum_{k}\gamma^{(k)}\mathbb{E}\left[F_{j^{(k)}}\left(w^{\left(k-T^{\left(k\right)}\right)}\right)-F_{j^{(k)}}\left(w^{*)}\right)\right]$
$\displaystyle\leq\sum_{k}\frac{N\gamma^{\left(k\right)}}{2k}+\frac{1}{2}\left\|w^{(0)}-w^{*}\right\|_{2}^{2}$
$\displaystyle+{\sum}_{k}{(\gamma^{(k)})}^{2}\,\mathbb{E}\left[\left\|\nabla
F_{i^{(k)}}\left(w^{*}\right)\right\|_{2}^{2}\right]$

Next, we get a bound on

$\sum_{k}\gamma^{\left(k\right)}\mathbb{E}\left[F\left(w^{(k)}\right)-F\left(w^{(k-T^{\left(k\right)})}\right)\right].$
$\displaystyle\gamma^{(k)}\mathbb{E}\left[F\left(w^{(k)}\right)-F\left(w^{\left(k-T_{k}\right)}\right)\right]$
$\displaystyle\overset{(a)}{\leq}ND\gamma^{(k)}\mathbb{E}\left\|w^{(k)}-w^{\left(k-T_{k}\right)}\right\|$
$\displaystyle\overset{(b)}{\leq}ND\gamma^{(k)}\mathbb{E}\left(\sum_{n=k-T_{k}}^{k-1}\left\|w^{\left(n+1\right)}-w^{\left(n\right)}\right\|\right)$
$\displaystyle\overset{(c)}{\leq}ND\gamma^{(k)}\sum_{n=k-T_{k}}^{k-1}\mathbb{E}\left(\left\|w^{\left(n+1\right)}-w^{\left(n\right)}\right\|\right)$
$\displaystyle\overset{(d)}{\leq}ND^{2}\gamma^{(k)}\sum_{n=k-T_{k}}^{k-1}\gamma^{\left(n\right)}$
$\displaystyle\overset{(e)}{\leq}\frac{ND^{2}}{2}\sum_{n=k-T_{k}}^{k-1}\left({(\gamma^{\left(n\right)})}^{2}+{(\gamma^{\left(k\right)})}^{2}\right)$
$\displaystyle\overset{}{\leq}\frac{ND^{2}}{2}T_{k}{(\gamma^{\left(k\right)})}^{2}+\frac{ND^{2}}{2}\sum_{n=k-T_{k}}^{k-1}{(\gamma^{\left(n\right)})}^{2}.$
(18)

(a) follows from Lemma 4, (b) using triangle inequality, (c) using linearity
of expectation, (d) follows Corollary 1 and (e) follows from the
Cauchy–Schwarz inequality. The upper bound summability over $k$ follows from
previous discussion in equation (VIII-B).

Combining with the results in (14) and (VIII-B) , we get

$\displaystyle\mathbb{E}\left[F\left(w^{(k)}\right)-F\left(w^{*}\right)\right]$
$\displaystyle\leq\frac{\sum_{k=1}^{T}\frac{N\gamma^{\left(k\right)}}{2k}+\frac{C.D^{2}}{\ln\left(1/\lambda_{P}\right)}+\frac{1}{2}\left\|w^{(0)}-w^{*}\right\|_{2}^{2}}{\sum_{k=1}^{T}\gamma^{(k)}}$
$\displaystyle\quad+\frac{{(\gamma^{(0)})}^{2}\sum_{k=1}^{T}\mathbb{E}\left[\left\|\hat{\nabla}F_{i^{(k)}}\left(w^{(k)}\right)\right\|_{2}^{2}\right]}{\sum_{k=1}^{T}\gamma^{(k)}}.$

By this step we proved Lemma 4. Next we present the essential technical
results to use in the proof of Theorem $1$.

######  Proposition 7.

[Sleeping multi-armed bandit convergence [30]] The sleeping multi-armed bandit
sampling scheme under adversarial availabilities guarantees the following:
$\left\|P^{(k)}-P\right\|\leq\mathcal{O}(\frac{1}{\sqrt{k}})$. Therefore,
using Definition 1, the random walk with transition matrices $P^{(k)}$ is
strongly ergodic.

We state next Lemma of [49] about the convergence of strongly ergodic random
walk.

######  Lemma 8 (Theorem II.7 in [49]).

Given strongly ergodic non-homogenous transition matrices $P^{(k)}$ with a
stochastic matrix $P$ such that
$\lim_{k\rightarrow\infty}g(2k)\left\|P^{(k)}-P\right\|=0$, given $Q$ such
$\left\|P^{k}-Q\right\|\leq c\beta_{2}^{k}$, then
$\lim_{k\rightarrow\infty}\min{\left\\{(1/\mu)^{k},\>g\left(k\right)\right\\}}\left\|P^{(0,\,k)}-Q\right\|=0$,
where $1<1/\mu<\sqrt{1/\beta_{2}}.$

Using the previous lemma, we get

$\displaystyle\underset{i}{\max}\left\|\mu-P^{(0,\,T_{k})}\left(i,:\right)\right\|\leq\mathcal{O}\left(\frac{1}{2k}+\frac{1}{\sqrt{k}}\right)$
(19)

for
$T_{k}=\min\left\\{k,\max\left\\{\frac{\ln({2Ck})}{\ln({1/\lambda})},K_{P}\right\\}\right\\}.$
Therefore,

$\displaystyle\mathbb{E}_{j^{(k)}}\left[F_{j^{(k)}}\left(w^{(k-T^{\left(k\right)})}\right)-F_{j^{(k)}}\left(w^{*}\right)|\,X_{0},\,X_{1},\,...,\,X_{k-T^{\left(k\right)}}\right]$
$\displaystyle\overset{}{=}\sum_{i=1}^{N}\left(F_{i}\left(w^{(k-T^{\left(k\right)})}\right)-F_{i}\left(w^{*}\right)\right)P\left(j^{(k)}=i\,|\,X_{0},\,X_{1},\,...,\,X_{k-T^{\left(k\right)}}\right)$
$\displaystyle{=}\sum_{i=1}^{N}\left(F_{i}\left(w^{(k-T^{\left(k\right)})}\right)-F_{i}\left(w^{*}\right)\right)P\left(j^{(k)}=i\,|\,X_{k-T^{\left(k\right)}}\right)$
$\displaystyle\overset{}{=}\sum_{i=1}^{N}\left(F_{i}\left(w^{(k-T^{\left(k\right)})}\right)-F_{i}\left(w^{*}\right)\right)P^{(0,T^{(k)})}\left[X_{k-T^{\left(k\right)}}\,|\,j^{(k)}=i\right]$
$\displaystyle{\geq}\left(F\left(w^{(k-T^{\left(k\right)})}\right)-F\left(w^{*}\right)\right)-\frac{N}{2k}-\frac{cte.N}{\sqrt{k}}.$
(20)

Finally,

$\displaystyle\sum_{k=1}^{T}\gamma^{(k)}\mathbb{E}\left[F\left(w^{(k)}\right)-F\left(w^{*}\right)\right]$
$\displaystyle\quad\leq\sum_{k=1}^{T}N\gamma^{\left(k\right)}\left(\frac{1}{2k}+\frac{cte}{\sqrt{k}}\right)+\frac{C.D^{2}}{\ln\left(1/\lambda\right)}$
$\displaystyle\quad+\frac{1}{2}\left\|w^{(0)}-w^{*}\right\|_{2}^{2}+\sum_{k=1}^{T}{(\gamma^{(k)})}^{2}\mathbb{E}\left[\left\|\hat{\nabla}F_{i^{(k)}}\left(w^{(k)}\right)\right\|_{2}^{2}\right].$

Using previous results and the the convexity assumption, we get

$\displaystyle\mathbb{E}\left[F\left(w^{(k)}\right)-F\left(w^{*}\right)\right]$
$\displaystyle\leq\frac{\sum_{k=1}^{T}N\gamma^{\left(k\right)}\left(\frac{1}{2k}+\frac{cte}{\sqrt{k}}\right)+\frac{C.D^{2}}{\ln\left(1/\lambda\right)}+\frac{1}{2}\left\|w^{(0)}-w^{*}\right\|_{2}^{2}}{\sum_{k=1}^{T}\gamma^{(k)}}$
$\displaystyle\quad+\frac{{(\gamma^{(0)})}^{2}C^{*}}{\sum_{k=1}^{T}\gamma^{(k)}}.$

Employing the assumptions on the step size, we get an order of convergence
$O(T^{1-q})$ for a step size choice $\gamma^{(k)}=\frac{1}{k^{q}}$ where
$\frac{1}{2}<q<1$.

## References

  * [1] H. B. McMahan, E. Moore, D. Ramage, and B. A. y Arcas, “Federated Learning of Deep Networks using Model Averaging,” _CoRR_ , vol. abs/1602.05629, 2016\.
  * [2] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings _et al._ , “Advances and open problems in federated learning,” _arXiv preprint arXiv:1912.04977_ , 2019.
  * [3] T. Li, A. K. Sahu, A. S. Talwalkar, and V. Smith, “Federated learning: Challenges, methods, and future directions,” _IEEE Signal Processing Magazine_ , vol. 37, pp. 50–60, 2020.
  * [4] Y. Yang, R. G. D’Oliveira, S. El Rouayheb, X. Yang, H. Seferoglu, and Y. Chen, “Secure coded computation for efficient distributed learning in mobile iot,” in _2021 18th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON)_ , 2021, pp. 1–9.
  * [5] T. S. Brisimi, R. Chen, T. Mela, A. Olshevsky, I. C. Paschalidis, and W. Shi, “Federated learning of predictive models from federated electronic health records,” _International journal of medical informatics_ , vol. 112, pp. 59–67, 2018.
  * [6] J. C. Jiang, B. Kantarci, S. Oktug, and T. Soyata, “Federated learning in smart city sensing: Challenges and opportunities,” _Sensors_ , vol. 20, no. 21, p. 6230, 2020.
  * [7] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas, “Communication-Efficient Learning of Deep Networks from Decentralized Data,” in _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, A. Singh and J. Zhu, Eds., vol. 54. PMLR, 20–22 Apr 2017, pp. 1273–1282. [Online]. Available: https://proceedings.mlr.press/v54/mcmahan17a.html
  * [8] Y. Zhao, M. Li, L. Lai, N. Suda, D. Civin, and V. Chandra, “Federated learning with non-iid data,” _arXiv preprint arXiv:1806.00582_ , 2018.
  * [9] J. Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor, “Tackling the objective inconsistency problem in heterogeneous federated optimization,” _arXiv preprint arXiv:2007.07481_ , 2020.
  * [10] A. Nedic and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” _IEEE Transactions on Automatic Control_ , vol. 54, pp. 48–61, 2009.
  * [11] B. Johansson, M. Rabi, and M. Johansson, “A randomized incremental subgradient method for distributed optimization in networked systems,” _SIAM J. Optim._ , vol. 20, pp. 1157–1170, 2009.
  * [12] P. Zhang, J. Wang, and K. Guo, “Compressive sensing and random walk based data collection in wireless sensor networks,” _Computer Communications_ , vol. 129, pp. 43–53, 2018.
  * [13] X. Mao, K. Yuan, Y. Hu, Y. Gu, A. H. Sayed, and W. Yin, “Walkman: A communication-efficient random-walk algorithm for decentralized optimization,” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 2513–2528, 2020.
  * [14] P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the multiarmed bandit problem,” _Machine learning_ , vol. 47, no. 2, pp. 235–256, 2002.
  * [15] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire, “The nonstochastic multiarmed bandit problem,” _SIAM journal on computing_ , vol. 32, no. 1, pp. 48–77, 2002.
  * [16] S. Bubeck and N. Cesa-Bianchi, “Regret analysis of stochastic and nonstochastic multi-armed bandit problems,” _arXiv preprint arXiv:1204.5721_ , 2012.
  * [17] B. Johansson, M. Rabi, and M. Johansson, “A simple peer-to-peer algorithm for distributed optimization in sensor networks,” _2007 46th IEEE Conference on Decision and Control_ , pp. 4705–4710, 2007.
  * [18] S. S. Ram, A. Nedic, and V. V. Veeravalli, “Asynchronous gossip algorithms for stochastic optimization,” _2009 International Conference on Game Theory for Networks_ , pp. 80–81, 2009.
  * [19] H. Wai, W. Shi, A. Nedic, and A. Scaglione, “Curvature-aided incremental aggregated gradient method,” _2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pp. 526–532, 2017.
  * [20] T. Sun, Y. Sun, and W. Yin, “On markov chain gradient descent,” in _NeurIPS_ , 2018.
  * [21] G. Ayache and S. El Rouayheb, “Private weighted random walk stochastic gradient descent,” _IEEE Journal on Selected Areas in Information Theory_ , pp. 1–1, 2021.
  * [22] J. C. Duchi, A. Agarwal, M. Johansson, and M. I. Jordan, “Ergodic mirror descent,” _2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pp. 701–706, 2011.
  * [23] W. Shi, Q. Ling, G. Wu, and W. Yin, “Extra: An exact first-order algorithm for decentralized consensus optimization,” _SIAM J. Optim._ , vol. 25, pp. 944–966, 2015.
  * [24] A. I. Chen, “Fast distributed first-order methods,” 2012.
  * [25] D. Jakovetić, J. Xavier, and J. M. F. Moura, “Fast distributed gradient methods,” _IEEE Transactions on Automatic Control_ , vol. 59, pp. 1131–1146, 2014.
  * [26] A. K. Sahu, T. Li, M. Sanjabi, M. Zaheer, A. S. Talwalkar, and V. Smith, “On the convergence of federated optimization in heterogeneous networks,” _ArXiv_ , vol. abs/1812.06127, 2018.
  * [27] F. Haddadpour and M. Mahdavi, “On the convergence of local descent methods in federated learning,” _arXiv preprint arXiv:1910.14425_ , 2019.
  * [28] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh, “Scaffold: Stochastic controlled averaging for federated learning,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 5132–5143.
  * [29] A. Khaled, K. Mishchenko, and P. Richtárik, “Tighter theory for local sgd on identical and heterogeneous data,” in _AISTATS_ , 2020.
  * [30] R. D. Kleinberg, A. Niculescu-Mizil, and Y. Sharma, “Regret bounds for sleeping experts and bandits,” _Machine Learning_ , vol. 80, pp. 245–272, 2010.
  * [31] H. Namkoong, A. Sinha, S. Yadlowsky, and J. C. Duchi, “Adaptive sampling probabilities for non-smooth optimization,” in _ICML_ , 2017.
  * [32] F. Salehi, L. E. Celis, and P. Thiran, “Stochastic optimization with bandit sampling,” _ArXiv_ , vol. abs/1708.02544, 2017.
  * [33] Z. Borsos, A. Krause, and K. Y. Levy, “Online variance reduction for stochastic optimization,” _ArXiv_ , vol. abs/1802.04715, 2018.
  * [34] L. Zhang, S. Lu, and Z. Zhou, “Adaptive online learning in dynamic environments,” in _NeurIPS_ , 2018.
  * [35] A. E. Hanchi and D. Stephens, “Adaptive importance sampling for finite-sum optimization and sampling with decreasing step-sizes,” _ArXiv_ , vol. abs/2103.12243, 2020.
  * [36] V. Kanade, H. B. McMahan, and B. Bryan, “Sleeping experts and bandits with stochastic action availability and adversarial rewards,” in _AISTATS_ , 2009\.
  * [37] A. Saha, P. Gaillard, and M. Valko, “Improved sleeping bandits with stochastic actions sets and adversarial rewards,” in _ICML_ , 2020.
  * [38] P. Zhao and T. Zhang, “Stochastic optimization with importance sampling,” _ArXiv_ , vol. abs/1401.2753, 2014.
  * [39] G. Alain, A. Lamb, C. Sankar, A. C. Courville, and Y. Bengio, “Variance reduction in sgd by distributed importance sampling,” _ArXiv_ , vol. abs/1511.06481, 2015.
  * [40] S. U. Stich, A. Raj, and M. Jaggi, “Safe adaptive importance sampling,” in _NIPS_ , 2017.
  * [41] G. Papa, P. Bianchi, and S. Clémençon, “Adaptive sampling for incremental optimization using stochastic gradient descent,” in _ALT_ , 2015.
  * [42] D. Needell, R. Ward, and N. Srebro, “Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm,” in _Advances in Neural Information Processing Systems 27_ , Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, Eds. Curran Associates, Inc., 2014, pp. 1017–1025.
  * [43] L. Bottou and O. Bousquet, “The tradeoffs of large scale learning,” in _NIPS_ , 2007.
  * [44] A. Defazio, F. Bach, and S. Lacoste-Julien, “Saga: A fast incremental gradient method with support for non-strongly convex composite objectives,” in _NIPS_ , 2014.
  * [45] L. Xiao and T. Zhang, “A proximal stochastic gradient method with progressive variance reduction,” _SIAM J. Optim._ , vol. 24, pp. 2057–2075, 2014.
  * [46] G. Bouchard, T. Trouillon, J. Perez, and A. Gaidon, “Online learning to sample,” 2015.
  * [47] T. Lattimore and C. Szepesvari, “Bandit algorithms,” 2020.
  * [48] J. C. Duchi, A. Agarwal, and M. J. Wainwright, “Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling,” _IEEE Transactions on Automatic Control_ , vol. 57, pp. 592–606, 2012.
  * [49] C.-C. Huang, “Non-homogeneous markov chains and their applications,” 1977.
  * [50] G. Ayache and S. E. Rouayheb, “Random walk gradient descent for decentralized learning on graphs,” _2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)_ , pp. 926–931, 2019.
  * [51] A. A. Hagberg, D. A. Schult, and P. J. Swart, “Exploring network structure, dynamics, and function using networkx,” in _Proceedings of the 7th Python in Science Conference_ , G. Varoquaux, T. Vaught, and J. Millman, Eds., Pasadena, CA USA, 2008, pp. 11 – 15.
  * [52] J. C. Dattorro, “Convex optimization and euclidean distance geometry,” 2004.
  * [53] D. A. Levin, Y. Peres, and E. L. Wilmer, _Markov chains and mixing times_. American Mathematical Society, 2006.


# Exploring Zero and Few-shot Techniques for Intent Classification

Soham Parikh
ServiceNow Inc
<EMAIL_ADDRESS>
Quaizar Vohra
ServiceNow Inc
<EMAIL_ADDRESS>
Prashil Tumbade
ServiceNow Inc
<EMAIL_ADDRESS>
Mitul Tiwari
ServiceNow Inc
<EMAIL_ADDRESS>

###### Abstract

Conversational NLU providers often need to scale to thousands of intent-
classification models where new customers often face the cold-start problem.
Scaling to so many customers puts a constraint on storage space as well. In
this paper, we explore four different zero and few-shot intent classification
approaches with this low-resource constraint: 1) domain adaptation, 2) data
augmentation, 3) zero-shot intent classification using descriptions large
language models (LLMs), and 4) parameter-efficient fine-tuning of instruction-
finetuned language models. Our results show that all these approaches are
effective to different degrees in low-resource settings. Parameter-efficient
fine-tuning using T-few recipe Liu et al. (2022) on Flan-T5 Chung et al.
(2022) yields the best performance even with just one sample per intent. We
also show that the zero-shot method of prompting LLMs using intent
descriptions is also very competitive.

##  1 Introduction

Intent classification is the primary natural language understandin task for a
virtual agent or a chatbot. Providing intent-utterances for training intent
classification models is a laborious process. In this paper, we address this
problem by exploring zero and few-shot intent identification using Large
Language Models (LLMs) as well as instruction finetuned models. Zero-shot and
few-shot intent prediction completely remove or substantially reduce the work
to provide intent-utterances, respectively. We demonstrate that the following
four approaches work well in practice for zero/few-shot intent classification.

  * •

Domain adaptation: We use a sentence encoder that is pre-trained with our
domain knowledge and show that it performs well in a few-shot setting compared
to off-the-shelf sentence encoders.

  * •

Data Augmentation by supplementing human-curated training data with LLM-
generated data to improve training data.

  * •

Zero-shot intent classification: high capacity LLMs can be prompted creatively
with intent descriptions to do zero-shot classification.

  * •

Parameter-efficient fine-tuning (PEFT): finetuning a small number of
parameters added to instruction finetuned LMs using only a few examples

Here is the outline of the rest of the paper. In Section 2 we describe the
related work. In Section 3 we detail the datasets used. In Section 4 we
describe the four approaches covered in this work for zero/few-shot intent
classification. Finally, we conclude with observations in Sections 5 and 6.

Dataset | Intents | Train Size | Test Size | OOS Samples in Test
---|---|---|---|---
MASSIVE | 60 | 11514 | 2974 | No
OOTB-dataset* | 27 | 1363 | 3099 | No
Benchmark01* | 9 | 270 | 300 | Yes
Benchmark02* | 13 | 390 | 420 | Yes
Benchmark03* | 31 | 930 | 960 | Yes
Table 1: Statistics for intent classification datasets used in this paper.
Datasets marked with an asterisk (*) are private, internal benchmarking
datasets. Train and Test Sizes correspond to the number of utterances in the
respective spits. OOS samples in test set indicates whether there are any out-
of-scope samples in the test set.

##  2 Related Work

Recent papers have used domain adaptation Yu et al. (2021) and contrastive
learning Zhang et al. (2021) successfully for few-shot intent classification.
Yu et al. Yu et al. (2021) use embeddings from a BERT model Devlin et al.
(2019) pretrained on domain data to search for utterances belonging to new
intents in the domain. Zhang et al. (2021) finetune a BERT model on few-shot
data using contrastive learning which learns to discriminate between
semantically similar sentences. Our work on domain adaptation differs from
these mainly due to our setting which involves serving thousands of customers.
For legal reasons, we cannot co-mingle data from these customers to pre-train
a single model. Instead, we pre-train a sentence encoder based on an intent
taxonomy and out-of-the-box intents, which consist of human generated
synthetic data. In this setting, we can only train very lightweight models for
each customer, e.g. a dense layer on top of a pre-trained sentence encoder.

Data Augmentation is another widely used technique to solve the problem of
data scarcity. Recent work on data augmentation has focused on using multiple
methods to improve model performance Chen and Yin (2022). Sahu et al. (2022)
use a prompt-based approach to generate labeled training data for intent
classification using LLMs like GPT-3 Brown et al. (2020). The quality of
generated training data using LLMs is highly dependent on the prompts. In this
work, we show various prompt-based approaches that generate diverse data for
training and boost the performance of intent classifiers.

As the usage of conversational agents grows, it is important for them to
generalize to new intents. Recent work has focused on performing zero-shot
intent detection on unseen intents and domains. Ferreira et al. (2015);
Yazdani and Henderson (2015) use additional knowledge from ontologies or
attributes whereas Liu et al. (2019) make modifications to capsule networks to
generalize to unseen domains. Ma et al. (2019) use embeddings of intent
descriptions to perform zero-shot detection of new intents and services. While
these methods are effective, they all require training on an initial set of
intents. Large Language Models (LLMs) like GPT-3 Brown et al. (2020) and more
recently instruction finetuned models like Chung et al. (2022) have shown good
zero-shot performance on newly seen tasks without any prior training data on
those tasks. In this work, we show that these models are also effective for
zero-shot intent classification using just intent descriptions.

##  3 Datasets

We use public and private intent classification datasets to benchmark
different approaches. For evaluation on public dataset, we use the English
train and test sets from MASSIVE for intent classification. MASSIVE contains
utterances directed at a physical device spanning 60 intents and 18 domains.
For more details on the MASSIVE dataset FitzGerald et al. (2022), we encourage
readers to refer to their paper. We also use private benchmarking datasets
internal to our company. These datasets contain various intents and utterances
in the enterprise setting spanning 3 different domains: IT Service Management
(ITSM), HR and Customer Service Management (CSM). The utterances are inspired
by interactions between humans and chatbots and are typically queries from
goal-oriented conversations where the user needs to resolve an issue.
Additionally, some of these datasets also contain out-of-scope (OOS)
utterances in their test set i.e., utterances that do not belong to any
intent, in order to benchmark irrelevance detection of intent classification
models. Table 1 shows statistics for different datasets used in our
benchmarking.

##  4 Methodology

In this section, we describe the various methods we test for zero and few-shot
learning.

Few-shot K | model | Massive | Benchmark01 | Benchmark02 | Benchmark03
---|---|---|---|---|---
3 | LaBSE | 46 (1.7) | 59 (2.9) | 52 (2.7) | 58 (3.1)
MUSE3 | 53 (2.8) | 64 (3.8) | 62 (2.7) | 64 (1.3)
GTR-3b | 59 (1.4) | 76 (1.4) | 70 (3.3) | 78 (2.2)
ELMSE | 57 (2.3) | 77 (2.4) | 63 (4.6) | 74 (1.7)
5 | LaBSE | 58 (1.7) | 65 (3.3) | 59 (1.7) | 67 (1.8)
MUSE3 | 61 (0.9) | 70 (2.2) | 66 (1.4) | 70 (1.7)
GTR-3b | 66 (1.2) | 78 (1.0) | 73 (1.7) | 84 (1.0)
ELMSE | 63 (1.1) | 80 (1.7) | 67 (2.6) | 79 (1.2)
Table 2: Results for domain adaptation on 3 internal datasets along with
MASSIVE comparing LaBSE, MUSE, ELMSE, and GTR-3B models. The metric reported
here is in-scope accuracy averaged over 5 different selections of few shot
data. Numbers inside parenthesis indicate standard deviation across the 5
selections

###  4.1 Domain Adaptation

Domain and task-specific pre-training of language model Gururangan et al.
(2020) has shown to significantly improve classification accuracy in both low
and high resource settings. Techniques like contrastive learning Gao et al.
(2021) Feng et al. (2022) are effective for improving the quality of sentence
encoders, specifically in low-resource settings. Inspired by these ideas, we
use a sentence encoder trained on our domain-specific data along with public
datasets. Starting with the LaBSE checkpoint Feng et al. (2022) we train it
further by converting intent classification, paraphrasing, etc, as sentence
similarity tasks. We will refer to this model as ELMSE (enterprise language
model based sentence encoder).

For training intent-classification models, we freeze ELMSE weights and use its
sentence embeddings as features for a trainable non-linear dense layer for
classification. We compare ELMSE against other publicly available sentence
encoders, namely LaBSE, Multilingual Universal Sentence Encoder (MUSE) Yang et
al. (2020) and GTR-3B. ELMSE is comparable in size to LaBSE and MUSE while
almost 30 times smaller than GTR-3b. We simulate few-shot setting by randomly
selecting K utterances per intent from full datasets. We use K=3,5,8,10,15,20
as well as the full dataset. We report results on 4 datasets from Table 1.
Since OOTB-dataset was used for pretraining ELMSE, we exclude it from few-shot
evaluation.

Figure 1: Comparison of ELMSE which is domain adapted with sentence encoders
which are not domain adapted

####  4.1.1 Results for Domain Adaptation

Table 2 reports in-scope accuracy and standard deviation averaged of 5 random
seeds for 3-shot and 5-shot classification. The results demonstrate that
domain adaptation is a very effective approach with improvements of greater
than 5 percent in most cases when compared with models of similar size. These
results carry over as we increase the number of few-shot utterances to more
than 5 as shown in Figure 1. The plots also show that the gap between ELMSE
and LaBSE is much larger in a few-shot setting and reduces as K increases.
Moreover, ELMSE is only 2-3% worse than GTR-3b which is 30 times larger model.

Approach | Prompt | Generated Text
---|---|---
| GPT3 Paraphrase Aug.
---
|  Task: Create diverse utterances
---
by paraphrasing the following utterances:
schedule alarm to wake me up after 3 hours
alarm for ten am
wake me up on friday at five in the morning i need to catch the train
alarm me at eight am
please set alarm for today
Create 20 utterances:
| Set an alarm for 10 o’clock.
---
Wake me up on Friday at 5am
so I can make the train.
⋮
Set a timer to wake me up
in three hours
| GPT3 Aug. Using Intent Descr.
---
| A virtual assistant serves multiple intents.
---
Below are the description of the intents:
alarm_set: user wants to set an alarm
iot_cleaning: user wants to do some cleaning
⋮
play_podcasts: user wants to play a podcast or rewind/repeat a particular
episode in a podcast
Generate 20 utterances for alarm_set intent:
| Can you set an alarm for next week?
---
I need to set an alarm for a specific time
I want to set an alarm for a certain day
⋮
I’d like to set an alarm
for a certain hour
Table 3: Example prompts used in generating text for the corresponding approaches  Approach | MASSIVE | Benchmark01 | Benchmark02 | Benchmark03
---|---|---|---|---
ELMSE Baseline | 63 (1.1) | 80 (1.7) | 67 (2.6) | 79 (1.2)
GPT-3 w/ Paraphrase Aug. | 63 (0.5) | 84 (0.4) | 71 (0.3) | 81 (0.5)
GPT-3 w/ Intent Descriptions | 51 (0.5) | 76 (0.4) | 69 (0.5) | 76 (0.2)
Parrot T5 | 58 (0.4) | 81 (0.2) | 73 (0.4) | 81 (0.4)
Seed Set + GPT-3 w/ Intent Descriptions | 63 (0.8) | 84 (0.4) | 71 (0.3) | 78 (0.9)
Seed Set + Parrot T5 | 63 (0.6) | 79 (0.4) | 68 (2.2) | 76 (0.6)
Table 4: Results for Data Augmentation on 3 internal datasets along with
MASSIVE comparing the performance on multiple prompt-based approaches. We
report the average in-scope accuracy and standard deviation averaged over 3
different random seeds

###  4.2 Data Augmentation

We use data augmentation to generate labeled data for training starting with a
seed set of 5 utterances per intent. In this section, we exploer different
ways of prompting GPT-3 and T5 Raffel et al. (2020). For evaluating the
generated utterances, we use them for training the same type of lightweight
classifier as described in 4.1 using ELMSE as the sentence encoder. This
section describes different prompt-based approaches for data generation.

##### GPT-3 + Paraphrase

Following Sahu et al. (2022), we ask GPT-3 to generate 20 paraphrases of
utterances from the same intent taken from the seed set. To encourage diverse
generations, we set high temperature and top_p values.

##### GPT-3 + Intent Descriptions

We describe intents in the prompt and ask GPT-3 to generate 20 utterances for
a particular intent. We find that describing all intents prevents
hallucinations in the generations.

##### Parrot T5 Paraphrasing

We use the Parrot Paraphrase approach based on T5 Damodaran (2021) to generate
20 diverse paraphrased utterances given seed set. Table 3 shows a few
generations from our prompt-based approaches.

####  4.2.1 Experimental Setup and Results

To evaluate the quality of generated utterances, we use them to train intent
classifiers. We evaluate the performance of augmented dataset from each
approach as mentioned in Section 4.2.1 by training ELMSE classifier model for
intent classification task. We evaluate on 4 datasets and compared against
ELMSE few-shot baseline where K is set to 5. We report the in-scope accuracy
and standard deviation averaged over 3 different random seeds. Table 4 shows
the result for all approaches using the data augmentation. Unless mentioned
explicitly, we do not add the seed set to the training mix.

We find that using paraphrases from GPT-3 and Parrot T5 Paraphraser give
better results compared to ELMSE Baseline even without the seed set. GPT-3
Augmentations using Intent Descriptions does not perform well but when
combined with ELMSE Baseline seed set gives better results. Moreover, given a
good quality seed-set, we see that data augmentation using LLMs can boost the
performance of intent classification in few-shot setting.

Dataset | LLM Intents | Model | In-Scope Accuracy | Out-of-scope Recall
---|---|---|---|---
MASSIVE (60 intents) | 5 | Flan-T5-XXL | 68.6 | -
GPT-3 | 69.2 | -
60 | Flan-T5-XXL | 73.3 | -
GPT-3 | 73.9 | -
OOTB-dataset (27 intents) | 5 | Flan-T5-XXL | 83.7 | -
GPT-3 | 83.4 | -
27 | Flan-T5-XXL | 86.3 | -
GPT-3 | 84.9 | -
Benchmark01 (9 intents) | 5 | Flan-T5-XXL | 86.5 | 0.43
GPT-3 | 84.6 | 0.97
9 | Flan-T5-XXL | 86.5 | 0.48
GPT-3 | 89.3 | 0.67
Benchmark02 (13 intents) | 5 | Flan-T5-XXL | 69.7 | 0.65
GPT-3 | 60.6 | 0.87
13 | Flan-T5-XXL | 69 | 0.7
GPT-3 | 61.3 | 0.67
Table 5: Results for zero-shot prediction on 3 internal datasets along with
MASSIVE with GPT-3 and Flan-T5-XXL. In-scope accuracy is the accuracy computed
for test samples that belong to the intents in the dataset. Out-of-scope
recall is the fraction of out-of-scope test samples which were correctly
identified as irrelevant by the model i.e., not belonging to any of the
intents

###  4.3 Prompting Zero-shot Prediction

The given sentence needs to be mapped to exactly one of the intents described
below: alarm_set: user wants to set an alarm iot_cleaning: user wants to do
some cleaning $\vdots$ play_podcasts: user wants to play a podcast or
rewind/repeat a particular episode in a podcast none_of_the_above: if the user
sentence is not about any of the intents above Sentence: wake me up at 7am
Intent: alarm_set

We use intent names and descriptions for prompting language models to perform
zero-shot prediction. The intent descriptions are prefaced with instructions
to predict the correct intent and the test utterance is specified at the end.
The output is expected to be the correct intent label. Figure 4.3 shows an
example prompt from the MASSIVE dataset and the output from LLMs. For
evaluation we check for the presence of intent names in the LM completion text
as opposed to an exact match and report the first intent predicted in the
completion. This is done to account for hallucinations. If no intent names are
present in the completion text, we mark it as an “out-of-scope prediction”. We
create intent descriptions for 4 datasets: 3 internal benchmaring datasets and
the open-source MASSIVE dataset. We benchmark 2 language models using this
type of prompt: GPT-3 (175B parameters) and Flan-T5-XXL (11B parameters), an
instruction fine-tuned model.

##### Filtering Intents for LLMs

Many conversational agents have a lot of intents, sometimes more than 50. As
the number of intents increases, the prompt size increases which incurs higher
latency and cost (in case of token-based pricing models). To restrict the
length of the prompt, we use sentence similarity to retrieve the top-5 intents
and only use those 5 intents in the language model prompt. Using sentence
similarity needs a few training examples which makes this a few-shot approach.
With just 5 examples per intent, we get more than 0.85 recall for Top-5. To
restrict the size of the prompt, we do not pass the training examples to the
LMs.

Figure 2: Plots comparing in-scope accuracy of different Flan-T5 models using
Parameter-effiecient FineTuning (PEFT) with the T-Few recipe. The dotted lines
show the best results on each dataset from previously described methods. The
shaded regions show the standard deviation

##### Setup

For GPT-3, we set the temperature to 0 and max tokens for generation to 20. We
use the default setting generation settings for the Flan-T5-XXL model and do
not restrict the number of tokens to be generated. The results with filtering
are averaged over 3 runs using different random seeds for sampling the 5
samples per intent.

##### Results

Table 5 reports the accuracy for in-scope intents and the recall for out-of-
scope samples where applicable (samples that do not belong to any of the
intents in the dataset). We find that prompting language models with intent
descriptions for zero-shot intent classification performs better than few-shot
learning using a classifier (Tables 2 and 4). Since this only needs intent
descriptions, this approach can generalize to new intents as well. Using the
same prompt, Flan-T5-XXL is competitive with GPT-3 in terms of in-scope
accuracy and is often better when presented a smaller number of intents in the
prompt. While the in-scope accuracy is comparable, GPT-3 clearly outperforms
Flan-T5-XXL in terms of the out-of-scope recall, indicating that it is better
at detecting irrelevant samples. We attribute the strong performance of
Flan-T5-XXL (even though it is 16x smaller) to the multi-task instruction
finetuning on over 1800 datasets.

For the 3 internal datasets, we also find that using more intents in the
prompt works better only up to a certain extent but have excluded the results
for the brevity of this paper. While the intent retrieval method does not give
perfect Top-5 recall, it helps in keeping the prompt short and hence provides
lesser chances for the language models to give a output a wrong label name.
Moreover, filtering can also improve the out-of-scope recall as in the case of
Benchmark02 dataset.

###  4.4 Parameter-Efficient FineTuning (PEFT)

Taking inspiration from the T-Few recipe Liu et al. (2022), we add and
finetune IA3 adapters from scratch in Flan-T5 models in a few-shot setting
which is similar to 4.1. We pick K=1,3,5 utterances per intent. Since the
Flan-T5 models are instruction fine-tuned, we use the same prompt from 4.3 and
provide the intent name as the target string. For MASSIVE and OOTB-dataset, we
restrict the number of intents in the prompt to 15 at training time to prevent
out-of-memory exceptions. At inference time, we provide all intents in the
prompt. We use all 3 loss functions (language modeling, unlikelihood and
length normalized losses) and the same hyperparameters as mentioned in the
T-Few paper. For more details about the T-Few recipe, we encourage readers to
refer to their paper.

Figure 2 compares the results of PEFT against the best results from previously
described methods. Flan-T5-XL (3B parameters) consistently outperforms all
other methods with just 1 training example per intent. With a few more
examples, Flan-T5-Large (770M parameters) also outperforms all other methods
except Flan-T5-XXL on the OOTB dataset. This shows that we can train
significantly smaller models which are easier to deploy and also outperform
LLMs like GPT-3 with just a few parameters using intent descriptions and a
handful of examples.

##  5 Observations

Comparing results across the 4 approaches, we notice that all 4 approaches are
effective in low resource settings. We find that domain adaptation is a cheap
option in terms of size of the models but it still requires 5-10 training
utterances per intent for getting accuracy above 70%. Data Augmentation using
paraphrasing further helps in most cases by 2-4 percentage points. However,
expanding to new domains requires sentence-pairs data for training the
sentence encoder which can involve days of human labeling. Zero shot
classification using intent descriptions with LLMs and instruction finetuned
models performs even better than domain adaptation with data augmentation and
doesn’t require any utterances to be configured per intent. However a good
description for each intent is required. Additionally, these models can be
expensive to operationalize. Inference on Flan-T5-XXL requires using A100
GPUs. GPT-3 is not open-source and based on a pricing model which can be
expensive to scale to thousands of customers. Parameter efficient fine-tuning
(PEFT) of instruction finetuned models like Flan-T5-XL and Flan-T5-Large
offers the best performance across all methods and often by a large margin.
Moreover, these models are only a fraction of the size of GPT-3 and
Flan-T5-XXL and much easier to operationalize at scale with far lesser compute
resources.

##  6 Conclusion

In this paper, we addressed the task of zero/few-shot intent identification
with Large Language Models (LLMs). We presented four approaches, namely domain
adaptation, data augmentation, zero-shot prediction with prompting, and
parameter-efficient fine-tuning. Our experimental results demonstrate that
LLMs and larger instruction fine-tuned language models are very effective in
zero-shot setting with in-context prompting. Smaller instruction finetuned
models with adapters are even better when adapter-finetuned on just 1 or 3
examples per intent. We hope these results are useful for practical deployment
of conversational agents in low-resource settings as well as aiding non-
practitioners in building their intent classification models. In the future,
we plan to extend this work by domain adapting smaller instruction finetuned
models in a multi-task setting and exploring their zero-shot capabiltiies.

## References

  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901. Curran Associates, Inc.
  * Chen and Yin (2022) Derek Chen and Claire Yin. 2022.  Data augmentation for intent classification.  _CoRR_ , abs/2206.05790.
  * Chung et al. (2022) Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Y. Zhao, Yanping Huang, Andrew M. Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoc V. Le, and Jason Wei. 2022.  Scaling instruction-finetuned language models.  _CoRR_ , abs/2210.11416.
  * Damodaran (2021) Prithiviraj Damodaran. 2021.  Parrot: Paraphrase generation for nlu.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Feng et al. (2022) Fangxiaoyu Feng, Yinfei Yang, Daniel Cer, Naveen Arivazhagan, and Wei Wang. 2022\.  Language-agnostic BERT sentence embedding.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 878–891, Dublin, Ireland. Association for Computational Linguistics.
  * Ferreira et al. (2015) Emmanuel Ferreira, Bassam Jabaian, and Fabrice Lefèvre. 2015.  Online adaptative zero-shot learning spoken language understanding using word-embedding.  In _2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 5321–5325.
  * FitzGerald et al. (2022) Jack FitzGerald, Christopher Hench, Charith Peris, Scott Mackie, Kay Rottmann, Ana Sanchez, Aaron Nash, Liam Urbach, Vishesh Kakarala, Richa Singh, Swetha Ranganath, Laurie Crist, Misha Britan, Wouter Leeuwis, Gökhan Tür, and Prem Natarajan. 2022.  MASSIVE: A 1m-example multilingual natural language understanding dataset with 51 typologically-diverse languages.  _CoRR_ , abs/2204.08582.
  * Gao et al. (2021) Tianyu Gao, Xingcheng Yao, and Danqi Chen. 2021.  SimCSE: Simple contrastive learning of sentence embeddings.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 6894–6910, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Gururangan et al. (2020) Suchin Gururangan, Ana Marasović, Swabha Swayamdipta, Kyle Lo, Iz Beltagy, Doug Downey, and Noah A. Smith. 2020.  Don’t stop pretraining: Adapt language models to domains and tasks.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8342–8360, Online. Association for Computational Linguistics.
  * Liu et al. (2019) Han Liu, Xiaotong Zhang, Lu Fan, Xuandi Fu, Qimai Li, Xiao-Ming Wu, and Albert Y.S. Lam. 2019.  Reconstructing capsule networks for zero-shot intent classification.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 4799–4809, Hong Kong, China. Association for Computational Linguistics.
  * Liu et al. (2022) Haokun Liu, Derek Tam, Muqeeth Mohammed, Jay Mohta, Tenghao Huang, Mohit Bansal, and Colin Raffel. 2022.  Few-shot parameter-efficient fine-tuning is better and cheaper than in-context learning.  In _Advances in Neural Information Processing Systems_.
  * Ma et al. (2019) Yue Ma, Zengfeng Zeng, Dawei Zhu, Xuan Li, Yiying Yang, Xiaoyuan Yao, Kaijie Zhou, and Jianping Shen. 2019.  An end-to-end dialogue state tracking system with machine reading comprehension and wide & deep classification.  _CoRR_ , abs/1912.09297.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _J. Mach. Learn. Res._ , 21:140:1–140:67.
  * Sahu et al. (2022) Gaurav Sahu, Pau Rodriguez, Issam Laradji, Parmida Atighehchian, David Vazquez, and Dzmitry Bahdanau. 2022.  Data augmentation for intent classification with off-the-shelf large language models.  In _Proceedings of the 4th Workshop on NLP for Conversational AI_ , pages 47–57, Dublin, Ireland. Association for Computational Linguistics.
  * Yang et al. (2020) Yinfei Yang, Daniel Cer, Amin Ahmad, Mandy Guo, Jax Law, Noah Constant, Gustavo Hernández Ábrego, Steve Yuan, Chris Tar, Yun-Hsuan Sung, Brian Strope, and Ray Kurzweil. 2020.  Multilingual universal sentence encoder for semantic retrieval.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations, ACL 2020, Online, July 5-10, 2020_ , pages 87–94. Association for Computational Linguistics.
  * Yazdani and Henderson (2015) Majid Yazdani and James Henderson. 2015.  A model of zero-shot learning of spoken language understanding.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 244–249, Lisbon, Portugal. Association for Computational Linguistics.
  * Yu et al. (2021) Dian Yu, Luheng He, Yuan Zhang, Xinya Du, Panupong Pasupat, and Qi Li. 2021.  Few-shot intent classification and slot filling with retrieved examples.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 734–749, Online. Association for Computational Linguistics.
  * Zhang et al. (2021) Jianguo Zhang, Trung Bui, Seunghyun Yoon, Xiang Chen, Zhiwei Liu, Congying Xia, Quan Hung Tran, Walter Chang, and Philip Yu. 2021.  Few-shot intent detection via contrastive pre-training and fine-tuning.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 1906–1912, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.