# Online Algorithms for Hierarchical Inference in Deep Learning applications
at the Edge

Vishnu Narayanan Moothedath<EMAIL_ADDRESS>0000-0002-2739-5060 KTH Royal
Institute of TechnologyMalvinas Väg 10StockholmSweden10044 ,  Jaya Prakash
Champati<EMAIL_ADDRESS>0000-0002-5127-8497 IMDEA Networks
InstituteAvda. del Mar Mediterraneo, 22MadridSpain28918 and  James Gross
<EMAIL_ADDRESS>0000-0001-6682-6559 KTH Royal Institute of TechnologyMalvinas
Väg 10StockholmSweden10044

###### Abstract.

We consider a resource-constrained Edge Device (ED) embedded with a small-size
ML model (S-ML) for a generic classification application, and an Edge Server
(ES) that hosts a large-size ML model (L-ML). Since the inference accuracy of
S-ML is lower than that of the L-ML, offloading all the data samples to the ES
results in high inference accuracy, but it defeats the purpose of embedding
S-ML on the ED and deprives the benefits of reduced latency, bandwidth
savings, and energy efficiency of doing local inference. To get the best out
of both worlds, i.e., the benefits of doing inference on the ED and the
benefits of doing inference on ES, we explore the idea of Hierarchical
Inference (HI), wherein S-ML inference is only accepted when it is correct,
otherwise the data sample is offloaded for L-ML inference. However, the ideal
implementation of HI is infeasible as the correctness of the S-ML inference is
not known to the ED. We thus propose an online meta-learning framework to
predict the correctness of the S-ML inference. The resulting online learning
problem turns out to be a Prediction with Expert Advice (PEA) problem with
continuous expert space. We consider the full feedback scenario, where the ED
receives feedback on the correctness of the S-ML once it accepts the
inference, and the no-local feedback scenario, where the ED does not receive
the ground truth for the classification, and propose the HIL-F and HIL-N
algorithms and prove a regret bound that is sublinear with the number of data
samples. We evaluate and benchmark the performance of the proposed algorithms
for image classification applications using four datasets, namely, Imagenette
and Imagewoof (Howard and Gugger, 2020), MNIST (LeCun and Cortes, 2010), and
CIFAR-10 (Krizhevsky et al., 2009).

hierarchical inference, edge computing, regret bound, continuous experts,
expert advice prediction

††copyright: none††ccs: Theory of computation Online learning algorithms††ccs:
Mathematics of computing Probabilistic inference problems††ccs: Theory of
computation Scheduling algorithms

##  1\. Introduction

Emerging applications in smart homes, smart cities, intelligent manufacturing,
autonomous internet of vehicles, etc., are increasingly using Deep Learning
(DL) inference. Collecting data from the Edge Devices (EDs) and performing
remote inference in the cloud results in bandwidth, energy, and latency costs
as well as reliability (due to wireless transmissions) and privacy concerns.
Therefore, performing local inference using embedded DL models, which we refer
to as S-ML (Small-ML) models, on EDs has received significant research
interest in the recent past (Wang et al., 2020; Sanchez-Iborra and Skarmeta,
2020; Deng et al., 2020). These S-ML models range from DL models that are
optimized for moderately powerful EDs such as mobile phones to tinyML DL
models that even fit on microcontroller units. However, S-ML inference
accuracy reduces with the model size and can be potentially much smaller than
the inference accuracy of large-size state-of-the-art DL models, which we
refer to as L-ML (Large-ML) models, that can be deployed on Edge Servers
(ESs). For example, for an image classification application, an S-ML can be a
quantized MobileNet (Howard et al., 2017) with a width multiplier of $0.25$,
that has a memory size of $0.5$ MB and an inference accuracy of $39.5\%$ for
classifying ImageNet dataset (Deng et al., 2009), whereas CoCa (Wortsman et
al., 2022), an L-ML, has an accuracy of $91\%$ and a memory size in the order
of GBs.

One may choose to achieve the accuracy of L-ML model while utilizing the
computational capabilities of EDs using the well-known DNN partitioning
techniques, e.g., see (Kang et al., 2017; Li et al., 2020; Hu and Li, 2022).
Note that such partitioning techniques require processing time and energy
profiling of the layers on EDs as well as on ESs to decide the optimal
partition points. Early Exit is yet another technique that introduces side
branches in between the layers of DL models to trade-off accuracy with latency
(Teerapittayanon et al., 2016). In this work, we explore the novel idea of
Hierarchical Inference (HI) that complements the above techniques for
performing DL inference at the edge. Consider that an ED is embedded with an
S-ML and an L-ML111Both S-ML and L-ML are trained ML models deployed for
providing inference and HI does not modify these models. is deployed on an ES
(to which the ED enlists to get help for doing inference). In HI, we propose
that an ED first observes the S-ML inference on each data sample and offloads
it to L-ML only if S-ML inference is incorrect.

Clearly, the ambition of HI is to maximize the use of S-ML in order to reap
the benefits of reduced latency, bandwidth savings, and energy efficiency
while not losing inference accuracy by offloading strategically to L-ML, thus
achieving the best benefits out of the two worlds: EDs and ESs. However, the
central challenge is that the incorrect inferences are inherently unknown at
the ED and thus a decision under uncertainty needs to be taken. In this work,
we focus on the pervasive classification applications and address the above
sequential decision problem by proposing a novel HI meta-learning framework,
shown in Fig. 2, that facilitates the ED to decide if a current S-ML inference
for a given sample should be accepted or the sample to be offloaded. In our
framework, for each sample, the HI learning algorithm observes $p$, the
maximum probability value in the probability distribution over classes output
by the S-ML. It then decides to offload, receiving a fixed cost
$0\leq\beta<1$, or not to offload, receiving a cost $0$ if the inference is
correct, and a cost $1$, otherwise. We will show later that this cost
structure facilitates HI by maximizing the offloading of samples with
incorrect inference and not offloading the samples with correct inference. To
simplify the analysis, we assume that S-ML accepts the inference of L-ML as
the ground truth implying that the top-1 accuracy of L-ML is $100$%. The
justification for this assumption is that the ED cannot know the ground truth
when L-ML provides incorrect inference and thus by accepting the L-ML
inference the ED tries to achieve the top-1 accuracy of L-ML.

Figure 1. Schematic of the HI meta-learning framework

Figure 2. Classification of Imagenette by a small-size quantized MobileNet
using width multiplier $0.25$ (Howard et al., 2017).

Intuitively, if the maximum probability $p$ is high, then accepting S-ML
inference will likely result in cost $0$ and thus, it is beneficial to do so.
However, if $p$ is low, the cost will likely be equal to $1$, and thus
offloading with cost $\beta$ is beneficial. This can be seen from Fig. 2,
where we present the number of misclassified and correctly classified images
of the dataset Imagenette (Howard and Gugger, 2020) by the classifier
MobileNet (Howard et al., 2017). Observe that, for $p\geq 0.45$
(approximately) there are more images correctly classified. Thus offloading
for images with $p<0.45$ might look like a reasonable policy, where the images
that statistically tend to be correctly classified are processed locally and
those that are not are offloaded. In this work, we design learning algorithms
that learn the best threshold $\theta\in[0,1)$ with performance guarantees
after assigning quantifiable cost functions. Using these algorithms in each
step, we decide to offload if $p<\theta$ and not offload, otherwise.

The above problem falls in the domain of Prediction with Expert Advice (PEA)
(Cesa-Bianchi and Lugosi, 2006). However, we have continuous expert space (or
action space) for $\theta$ and therefore, as explained later in Section 4, the
standard Exponentially Weighted average Forecaster (EWF) does not have a
regret bound for our problem. Another challenge is that, in the case of
accepting S-ML inference, the local cost is not observable as the ED will not
know if the interence is correct or not; we call this no-local feedback
scenario. To tackle this challenge, we first design an algorithm for the
important scenario where local feedback is available – for example, a human
user providing this feedback. We refer to this as full feedback scenario. We
then extend the algorithm to the no-local feedback scenario.

A novel aspect of our algorithms is that they use the structural properties of
the HI learning problem at hand to find a set non-uniform intervals obtained
by doing dynamic and non-uniform discretizations, and use these intervals as
experts, there by transforming the problem from a continuous to a discrete
domain without introducing any error due to this discretization. To the best
of our knowledge, our work is the first attempt to extend the concept of
continuous experts to the no-local feedback scenario and find regret bounds
for the same. We summarize our main contributions below.

  * •

We propose a novel meta-learning framework for HI that decides whether a data
sample that arrived should be offloaded or not based on S-ML output. For the
full feedback scenario, we prove that $O\left(\sqrt{n\log n}\right)$ is the
lower bound for the regret that can be achieved by any randomized algorithm
for a general loss function, where $n$ is the number of data samples.

  * •

We propose the HI Learning with Full feedback (HIL-F) algorithm that uses
exponential weighting and dynamic non-uniform discretization. We prove that
HIL-F has $\sqrt{n\ln(1/\lambda_{\text{min}})/2}$ regret bound, where
$\lambda_{\text{min}}$ is the minimum difference between any two distinct $p$
values among the $n$ samples.

  * •

We propose HI Learning with the no-local feedback (HIL-N) algorithm, which on
top of HIL-F, uses an unbiased estimate of the loss function. We prove a
regret bound $O\left(n^{{2}/{3}}\ln^{{1}/{3}}(1/\lambda_{\text{min}})\right)$.
We discuss the ways to approximate $\lambda_{\text{min}}$ and find the optimal
values of the parameters used.

  * •

We show that the computational complexity of our algorithms in round $t$ is
$O\left(\min(t,\frac{1}{\lambda_{\mathrm{min}}})\right)$.

  * •

Finally, we evaluate the performance of the proposed algorithms for image
classification application using four datasets, namely, Imagenette and
Imagewoof (Howard and Gugger, 2020), MNIST (LeCun and Cortes, 2010), and
CIFAR-10 (Krizhevsky et al., 2009; Krizhevsky, 2009). For Imagenette and
Imagewoof we use MobileNet, for MNIST we implement a linear classifier for
S-ML, and for CIFAR-10, we use a readily available CNN. We compare with four
baseline algorithms – the optimal fixed-$\theta$ policy, one that offloads all
samples, one that does not offload any, and a hypothetical genie algorithm
that knows the ground truth.

This paper is organized as follows: In Section 2 we go through the related
research and explain the novelty in the contributions. In Section 3, we
describe the system model followed by some background information and
preliminary results in Section 4. Sections 5 and 6 details HIL-F and HIL-N,
derive their regret bounds, and Section 7 discuss their computational
complexity. Finally, we show the numerical results in Section 8 and conclude
in Section 9.

##  2\. Related Work

### Inference Offloading:

Since the initial proposal of edge computing in (Satyanarayanan et al., 2009),
significant attention was given to the computational offloading problem,
wherein the ED needs to decide which jobs to offload and how to offload them
to an ES. The majority of works in this field studied offloading generic
computation jobs, e.g., see (Cuervo et al., 2010; Guo et al., 2019; Sundar et
al., 2020). In contrast, due to the growing interest in edge intelligence
systems, recent works studied offloading data samples for ML inference both
from a theoretical (Ogden and Guo, 2020; Fresa and Champati, 2021; Nikoloska
and Zlatanov, 2021) and practical (Wang et al., 2018, 2019b) perspectives. In
(Ogden and Guo, 2020), offloading between a mobile device and a cloud is
considered. The authors account for the time-varying communication times by
using model selection at the cloud and by allowing the duplication of
processing the job a the mobile device. In (Fresa and Champati, 2021), the
authors considered a scalable-size ML model on the ED and studied the
offloading decision to maximize the total inference accuracy subject to a time
constraint. All the above works focus on dividing the load of the inference
and do not consider HI and online learning. Our work is in part motivated by
(Nikoloska and Zlatanov, 2021), where the authors assumed that the energy
consumption for local inference is less than the transmission energy of a
sample and studied offloading decision based on a confidence metric computed
from the probability distribution over the classes. However, in contrast to
our work, the authors do not consider the meta-learning framework and compute
a threshold for the confidence metric based on the energy constraint at the
ED.

### On-Device Inference

Several research works focused on designing S-ML models to be embedded on EDs
that range from mobile phones to microcontroller units. While optimization
techniques such as parameter pruning and sharing (Han et al., 2015), weights
quantization (Rastegari et al., 2016), and low-rank factorization (Denton et
al., 2014) were used to design the S-ML models, techniques such as EarlyExit
were used to reduce the latency of inference. For example, (Wang et al.,
2019a) studied the use of DNNs with early exits (Teerapittayanon et al., 2016)
on the edge device, while (Taylor et al., 2018) studied the best DNN selection
on the edge device for a given data sample to improve inference accuracy and
reduce latency. These works do not consider inference offloading and in turn
HI.

### DNN Partitioning:

Noting that mobile devices such as smartphones are embedded with increasingly
powerful processors and the data that needs to be transmitted between
intermediate layers of a DNN is much smaller than the input data in several
applications, the authors in(Kang et al., 2017) studied partitioning DNN
between a mobile device and cloud to reduce the mobile energy consumption and
latency. Following this idea, significant research work has been done that
includes DNN partitioning for more general DNN structures under different
network settings (Hu et al., 2019; Li et al., 2020) and using heterogeneous
EDs (Hu and Li, 2022), among others. In contrast to DNN partitioning, under
HI, ED, and ES may import S-ML and L-ML algorithms from the pool of trained ML
algorithms available on open-source libraries such as Keras, TFLite, and
PyTorch. Furthermore, HI doesn’t even require that S-ML and L-ML be DL models
but rather they can even be signal processing algorithms. On the one hand,
there is significant research by the tinyML community for building small-size
DNNs that can be embedded on microcontrollers and also in designing efficient
embedded hardware accelerators (Sanchez-Iborra and Skarmeta, 2020). On the
other hand, abundant state-of-the-art DNNs are available at edge servers that
provide high inference accuracy. Our work is timely as HI will equip ML at the
edge to reap the benefits of the above two research thrusts. To the best of
our knowledge, we are the first to propose an online meta-learning framework
for HI.

### Online Learning:

The problem of minimizing the regret, when the decision is chosen from a
finite expert space falls under the well-known Prediction with Expert Advice
(PEA) or Multi-Armed Bandit (MAB) problems (Bubeck and Cesa-Bianchi, 2012;
Cesa-Bianchi and Lugosi, 2006). We will explain more about these problems in
Section 4. We will see that we cannot directly use these problems due to the
uncountable nature of the expert space in our problems which we will elaborate
in 3. We will also explain why some of the existing literature on continuous
extensions of PEA and MAB are not suited or sub-optimal for our specific
problem.

##  3\. System Model and Problem Statement

We consider the system shown in Fig. 2, with an ED enlisting the service of an
ES for data classification applications. For the EDs, we focus on resource-
constrained devices such as IoT sensors or microcontroller units. The ED is
embedded with an S-ML which provides lower inference accuracy, i.e., the top-1
accuracy, whereas the ES runs an L-ML with higher accuracy. For example, for
an image classification application, an S-ML can be a quantized MobileNet
(Howard et al., 2017) with a width multiplier of $0.25$; its memory size is
$0.5$ MB and has an inference accuracy of $39.5\%$ for classifying ImageNet
dataset (Deng et al., 2009), whereas CoCa (Wortsman et al., 2022), an L-ML,
has accuracy $91\%$ and has memory size in the order of GBs. Note that the
only assumption that we make on the algorithms is that the L-ML is
significantly more accurate and costlier than the S-ML. Thus, we do not
specify what exactly the S-ML or the L-ML algorithms needs to be, but can be
any classification algorithm including regression algorithms, SVMs, random
forests, and DNNs. Given an arbitrary sequence of $n$ data samples that arrive
over time at the ED, the question we study is: For each sample, should the ED
offload for inference from L-ML or accept the inference from S-ML? We approach
this as an online sequential decision problem. We assume that each sample
first goes through local inference and the decision is made according to the
inference results and parameters. Note that this is an essential assumption to
facilitate HI, otherwise, the ED cannot infer anything about the sample. Also,
as argued earlier in Section 1, we assume that all the offloaded images will
be correctly classified by the L-ML. This assumption is not necessary for the
proposed algorithms, but since the ED cannot possibly know if the inference
provided by the ES is correct or wrong, we use the assumption to simplify the
formulation.

Let $t$ denote the index of a data sample (e.g., an image), or simply sample,
that arrives $t$-th in the sequence. Let $p_{t}$ denote the maximum
probability in the probability distribution over the classes output by S-ML
for the sample $t$. 222Note that, in a classification application, a
classifier typically outputs a probability distribution over the classes. Our
framework allows other metrics, besides $p_{t}$, that are computed based on
the probability distribution over classes. Note that the class corresponding
to $p_{t}$ is declared as the true class for computing the top-1 accuracy.
Intuitively speaking, $p_{t}$ is the confidence level of S-ML for classifying
sample $t$ and it is a natural candidate to use for HI. Let binary random
variable $Y_{t}$ denote the cost representing the ground truth that is equal
to $0$ if the class corresponding to $p_{t}$ is the correct class and is equal
to $1$, otherwise. Clearly, given an S-ML model, $Y_{t}$ depends on ${p}_{t}$
and the sample. Let $\beta\in[0,1)$ denote the cost incurred for offloading
the image for inference at the ES. This cost, for example, may include the
costs for the transmission energy and the idle energy spent by the transceiver
till the reception of the inference. Note that, if $\beta\geq 1$, then
accepting the inference of S-ML, which incurs a cost at most $1$, for all
samples will minimize the total cost.

If the ED offloads sample $t$, it incurs cost $\beta$, and if it accepts the
S-ML inference, it incurs a cost $Y_{t}$. In the latter case, the ED may not
know $Y_{t}$, in general, and we refer to it by no-local feedback scenario. If
$Y_{t}$ is revealed once the ED accepts S-ML, we refer to by full feedback
scenario. In either scenario, if the ED offloads and receives the inference
from the ES, it can use that inference to infer $Y_{t}$. As explained in
Section 1, in round $t$, we use the following decision rule $\mathfrak{D}_{t}$
based on the choice of threshold $\theta_{t}\in[0,1]$:

(1) $\displaystyle\mathfrak{D}_{t}$ $\displaystyle=\begin{cases}\text{Do not
offload}&\text{ if }{p}_{t}\geq\theta_{t},\\\ \text{Offload}&\text{ if
}{p}_{t}<\theta_{t}.\end{cases}$ Therefore, given $p_{t}$, choosing threshold
$\theta_{t}$ results in a cost/loss $l(\theta_{t},Y_{t})$ at step $t$, given
by (2) $\displaystyle l(\theta_{t},Y_{t})$
$\displaystyle=\begin{cases}Y_{t}&{p}_{t}\geq\theta_{t},\\\
\beta&{p}_{t}<\theta_{t}.\end{cases}$

Note that, we omit the variable $p_{t}$ from the loss function
$l(\theta_{t},Y_{t})$ for notational simplicity.  We focus on designing online
algorithms that learn the best threshold, which balances the conflicting
objectives of reducing the number of images offloaded and increasing the
inference accuracy, thereby improving the responsiveness and energy efficiency
of the system.

We use boldface notations to denote vectors. Let
$\bm{Y}_{t}=\\{Y_{\tau}\\},\bm{\theta}_{t}=\\{\theta_{\tau}\\}$, and
$\mathbf{p}_{t}=\\{{p}_{\tau}\\},\,\tau=1,2,\dots,t\leq n$. Further, let
$\bm{Y}\coloneqq\bm{Y}_{n}$, $\bm{\theta}\coloneqq\bm{\theta}_{n}$ and
$\mathbf{p}\coloneqq\mathbf{p}_{n}$ for convenience. Finally, we define
$\lambda_{\text{min}}$ as the minimum difference between any two distinct
probability values in the sequence $\bm{p}_{n}$. Define the cumulative cost
$L(\bm{\theta},\bm{Y})$ as
$L(\bm{\theta},\bm{Y})=\sum_{t=1}^{n}l(\theta_{t},Y_{t})$. Also let
$\bm{\theta^{*}}=\\{\theta^{*},\theta^{*},\dots\\}$, a vector of size $n$ with
all values $\theta^{*}$, denote an optimal fixed-$\theta$ policy and
$L(\bm{\theta}^{*},\bm{Y})$ denote the corresponding cost. Then,

$\displaystyle L(\bm{\theta}^{*},\bm{Y})$
$\displaystyle=\sum_{t=1}^{n}l(\theta^{*},Y_{t})],$ where $\theta^{*}$ need
not necessarily be unique and is given by $\displaystyle\theta^{*}$
$\displaystyle=\operatorname*{arg\,min}_{\theta\in[0,1]}\sum_{t=1}^{n}l(\theta,Y_{t}).$

Given a sequence $\bm{Y}$, we now define the regret under an arbitrary
algorithm $\pi$ as

(3) $\displaystyle R_{n}$
$\displaystyle={\mathbb{E}}_{\pi}\left[L(\bm{\theta},\bm{Y})\right]-L(\bm{\theta}^{*},\bm{Y}),$

where the expectation ${\mathbb{E}}_{\pi}[\cdot]$ is with respect to the
distribution induced by $\pi$.

In this work, we are interested finding algorithms for both the full feedback
and no-local feedback scenarios that have a sublinear upper bound (i.e., a
bound that goes to 0 as n goes to $\infty$) on ${\mathbb{E}}_{\bm{Y}}[R_{n}]$
– the expected regret over the distribution of all possible sequences
$\bm{Y}$. We call this bound an expected regret bound and note that if we can
find a regret bound that is applicable for any given sequence $\bm{Y}$, the
same bound is also applicable for the expected regret (or even the maximum
regret) over all possible sequences of $\bm{Y}$. For this reason, and for the
sake of simplicity, we will only carry out the analysis for a given ${\bm{Y}}$
in the upcoming analysis sections. However, later in the numerical section, we
will show the results with expected average regret
${\mathbb{E}}_{\bm{Y}}[\frac{1}{n}R_{n}]=\frac{1}{n}{\mathbb{E}}_{\bm{Y}}[R_{n}]$
and expected average cost
$\frac{1}{n}{\mathbb{E}}_{\bm{Y},\pi}[{L}(\bm{\theta},\bm{Y})]$. We take the
average over the number of samples $n$ to remove the dependency on the size of
different datasets and normalize the maximum to $1$, for easy comparison.

Before going to the next section, we summarize the abbreviations and notations
used in this paper in TABLE 1 below.

ED | edge device | HI | hierarchical inference | HIL-F | HIL algorithm: full feedback
---|---|---|---|---|---
ES | edge server | HIL | hierarchical inference learning | HIL-N | HIL algorithm: no-local feedback
S-ML | small-size ML | PEA | prediction with expert advice | EWF | exponentially weighted forecaster
L-ML | large-size ML | ${p}_{[i]}$ |  $i^{\mathrm{th}}$ smallest district value in the set of available probabilities $\\{{p}_{1},{p}_{1},\dots\\}$
Table 1. Table of abbreviations.

##  4\. Background and Preliminary Analysis

Learning Problems: The HI learning problem falls into the category of PEA
(Cesa-Bianchi and Lugosi, 2006) problems. In the standard PEA problem, $N$
experts (or actions) are available for a predictor – known formally as a
forecaster. When the forecaster chooses an expert, it receives a cost/reward
corresponding to that expert. If the cost is only revealed for the chosen
expert, then this setting is the MAB. In contrast to the standard PEA, we have
an uncountable expert space where the expert $\theta_{t}$ belongs to the
continuous space $[0,1]$. Continuous action space is well studied in MAB
settings, e.g., see (Auer et al., 2007; Bubeck et al., 2011; Singh, 2021),
where the main technique used is to discretize the action space and bound the
regret by assuming that the unknown loss function has smoothness properties
such as uniformly locally Lipschitz. However, the problem at hand does not
assume any smoothness properties for the loss function.

As discussed briefly in Section 1, one well-known forecaster for standard PEA
is the exponential weighted average forecaster (EWF). For each expert, EWF
assigns a weight that is based on the cost incurred for choosing this expert.
For each prediction, EWF selects an expert with a probability computed based
on these weights. It is known that for $n$ predictions, EWF achieves a regret
$\sqrt{n\ln N/2}$. However, the continuous nature of the expert space renders
EWF not directly applicable for solving the problem at hand and we need an
extension of EWF. Such an extension was considered in (Bubeck, 2011), and a
regret bound for convex losses is obtained for continuous experts, conditioned
on a hyperparameter $\gamma>0$. Later, a particular $\gamma$ is proposed to
get the optimum regret bound of $1+\sqrt{n\ln n/2}$. We, on the other hand, do
not require any hyperparameter and more importantly do not assume any
convexity for the loss function. In addition, (Bubeck, 2011) does not describe
how to compute the integral required for computing the weights. Furthermore,
the solution in (Bubeck, 2011) is only applicable to HIL-F with full feedback,
but not to HIL-N in which case ours is the first work to the best of our
knowledge.

One may discretize $[0,1]$ with a uniform interval length $\Delta$ and use the
standard EWF, where a straightforward substitution of the number of experts
$N=1/\Delta$ results in regret bound $\sqrt{n\ln({1}/{\Delta})/2}$. However,
to not sacrifice the accuracy due to this discretization, one has to take
$\Delta$ small enough such that no two probability realization ${p}_{t}$ falls
within an interval. This is to make sure that the cumulative loss function is
constant within each interval, which will be more clear after Lemma 4.1. Thus,
if $\lambda_{\mathrm{min}}$ is the minimum separation between any two distinct
probabilities $p_{t},1\leq t\leq n$, the best attainable regret bound of a
standard EWF using uniform discretization is
$\sqrt{n\ln({1}/{\lambda_{\mathrm{min}}})/2}$ with
$N=1/\lambda_{\mathrm{min}}$. We will soon see that these regret bounds are
similar to what we get using our proposed algorithms, but the added complexity
with a large number of experts from the first round onwards makes it
suboptimal.

In this paper, we start with the continuous experts and then use the structure
of the problem to formulate it in a discrete domain. We propose a non-uniform
discretization that retains the accuracy of a continuous expert while reducing
the complexity to the theoretical minimum with at most $n+1$ experts after
$n^{\text{th}}$ round. Note that, due to the non-uniform discretization, the
proposed HIL does not involve $\Delta$, but instead involves
$\lambda_{\text{min}}$, where ${1}/{\lambda_{\mathrm{min}}}$ acts similar to
$N$ in the regret bound. In Section 5, we provide simple methods to
approximate $\lambda_{\text{min}}$.

Preliminary Analysis: In order to choose a good threshold $\theta_{t}$ in
round $t$, we take a hint from the discrete PEA (Cesa-Bianchi and Lugosi,
2006) where a weight for an expert is computed using the exponential of the
scaled cumulative losses incurred for potentially choosing that expert. We
extend this idea and define continuous weight function $w_{t}(\theta)$ as
follows:

$\displaystyle w_{t+1}(\theta)=$ $\displaystyle
e^{-\eta\sum_{\tau=1}^{t}l({\theta},{Y}_{\tau})}$ (4) $\displaystyle=$
$\displaystyle e^{-\eta\sum_{\tau=1}^{t-1}l({\theta},{Y}_{\tau})}e^{-\eta
l(\bm{\theta},{Y}_{t})}=w_{t}(\theta)e^{-\eta l(\theta,{Y}_{t})}.$ (5)
$\displaystyle W_{t+1}=$
$\displaystyle\int_{0}^{1}w_{t+1}(\theta)\,\mathrm{d}\theta.$

Here, $\eta>0$ is the learning rate. At each round $t$, the normalized weights
give the probability distribution for choosing the next threshold
$\theta_{t+1}$, and thus they can be used to learn the system. However, it
comes with two challenges – (i) finding a (set of) thresholds that follow this
distribution, and (ii) computing the integral. Although these challenges can
be solved using direct numerical methods, they incur a large amount of
computational cost. For instance, the inverse transformation method can
generate a random sample of the threshold with this distribution. Instead, we
use the facts from (1) and (2) that our final decision (to offload or not)
depends solely on the relative position of $\theta_{t}$ and $p_{t}$, but not
directly on $\theta_{t}$. Thus, using the distribution given by the normalized
weights, we define $q_{t}$ as the probability of not offloading, i.e., the
probability that $\theta_{t}$ is less than $p_{t}$, where

(6) $q_{t}=\frac{\int_{0}^{{p}_{t}}w_{t}(x)\,\mathrm{d}x}{W_{t}}.$

Thus, the decision $\mathfrak{D}_{t}$ from (1) boils down to do not offload
and offload with probabilities $q_{t}$ and $(1-q_{t})$, respectively.

With the first challenge mitigated, we look for efficient methods to compute
the integral in (6). Note that the cumulative loss function
$L(\bm{\theta}_{t},\bm{Y}_{t})=\sum_{\tau=1}^{t}l({\theta}_{\tau},{Y}_{\tau})$
can take potentially $3^{t}$ different values (because of 0, 1, or $\beta$
cost in each step), without any necessary pattern, and hence direct analytical
integration is not possible. To address this issue, we leverage the result of
the following lemma (Lemma 4.1) and convert the integral into summation by
discretizing the domain $[0,1]$ of the integral into a finite set of non-
uniform intervals.

The non-uniform discretization suggested by this lemma is incremental and a
new interval is (potentially) added in each round. Let’s look at the structure
of the weight function after $n$ rounds. Let ${p}_{0}=0$ and ${p}_{N}=1$,
where $N$ is the number of intervals formed formed in $[0,1]$ by the sequence
of probabilities $\bm{{p}}_{n}$. Here, we have $N\leq n+1$ because of the
repeated probabilities that do not result in the addition of a new interval.
We denote these intervals by ${B}_{i}=(p_{[i-1]},p_{[i]}],1\leq i\leq N$,
where $p_{[i]}$ denotes the $i$-th smallest distinct probability in
$\bm{{p}}_{n}$. Let $m_{i},1\leq i\leq N$ be the number of times $p_{[i]}$ is
repeated in $\bm{{p}}_{n}$. For instance, $N=n+1$ and $p_{[i]}=p_{i}$ iff
$m_{i}=1\forall i$. Finally, let $Y_{[i]},i=1,2,\dots n$ be the $i$-th element
in the ordered set of local inference costs ordered according to the
increasing values of the corresponding probability $p_{i}$. Note that, $i$ in
$Y_{[i]}$ goes up to $n$ while $i$ in $p_{[i]}$ goes only up to $N$ because
any two local inference costs $Y_{j}$ and $Y_{k}$ associated with repeated
probability values $p_{j}=p_{k}$ are two different but i.i.d random variables.

###### Lemma 4.1.

The function $L(\bm{\theta},\bm{Y})$ is a piece-wise constant function with a
constant value in each interval $B_{i}$. Furthermore, if there are no
repetitions in the sequence $\bm{p}_{n}$, then

$L(\bm{\theta^{*}},\bm{Y})=\underset{1\leq i\leq
n+1}{\min}\left\\{(i-1)\beta+\sum_{k=i}^{n}Y_{{[j]}}\right\\}.$

###### Proof.

By definition, $p_{t}$ falls on the boundary of $B_{i},\,\forall t$, for some
$i$. Hence, $B_{i}$ is a subset of either $(0,{p}_{t}]$ or $({p}_{t},1]$.

(7) $\Rightarrow
l(\theta_{t},Y_{t})=\begin{cases}Y_{t},&\forall\theta:\theta_{t}\in
B_{i}\subset(0,{p}_{t}],\text{ and}\\\ \beta,&\forall\theta:\theta_{t}\in
B_{i}\subset({p}_{t},1].\end{cases}$

Thus, $\forall\,i\leq N,\;l(\theta,Y_{t})\coloneqq
l(B_{i},Y_{t}),\forall\theta\in B_{i}.$ That is, the cost for all $\theta$
within an interval $B_{i}$ takes a constant value of $l(B_{i},Y_{t})$, and
this value depends on whether $p_{[i]}$ (the upper boundary of $B_{i}$) is
greater than ${p}_{t}$ or not. To prove the second part, note that
$L(\theta,\bm{Y})=\sum_{t=1}^{n}l(B_{i},Y_{t}):\theta\in B_{i}.$

$\displaystyle\Rightarrow L(\bm{\theta^{*}},\bm{Y})$
$\displaystyle=\min_{\theta\in[0,1]}L(\theta,\bm{Y})=\min_{1\leq i\leq
N}\sum_{t=1}^{n}l(B_{i},Y_{t}).$ $\displaystyle\sum_{t=1}^{n}l(B_{i},Y_{t})$
$\displaystyle=\sum_{t=1}^{n}[\beta\,\mathbbm{1}({p}_{t}<p_{[i]})+Y_{t}\,\mathbbm{1}({p}_{t}\geq
p_{[i]})]$ (8)
$\displaystyle=\beta\sum_{j=1}^{i-1}m_{j}+\smashoperator[r]{\sum_{k=1+\sum_{j=1}^{i-1}m_{j}}^{n}}Y_{[k]}$
$\displaystyle\Rightarrow L(\bm{\theta^{*}},\bm{Y})$
$\displaystyle=\min_{1\leq i\leq
N}\Big{\\{}\beta\sum_{j=1}^{i-1}m_{j}+\smashoperator[r]{\sum_{k=1+\sum_{j=1}^{i-1}m_{j}}^{n}}Y_{[k]}\Big{\\}}$

When there are no repetitions, we can substitute $m_{j}=1,\forall j$ in the
above expression to complete the proof. ∎

From Lemma 4.1, we infer that for any $t$ the weight function is constant
within the intervals defined by $\bm{p}_{t}$, and we can compute the integral
in (6) by adding multiple rectangular areas formed by the length of each
interval $B_{i}$ and the corresponding constant weight within it. Thus, by
converting the integral of $w_{t}(\theta)$ in a continuous domain to a
summation of areas of rectangles with non-uniform bases, we not only reduce
the complexity but also do that without sacrificing the accuracy of the
results. We will discuss more on the computational complexity in Section 7.
Note that the property of the piece-wise nature – given by the first part of
Lemma 4.1 – is not only valid for the particular loss function
$l({\theta_{t}},{Y_{t}})$, but also for any other loss function with a single
decision boundary (as in (2)) and discrete costs on either side of this
boundary. This becomes important when we use a modified loss function for
finding the optimum decision boundary $\theta^{*}$ later in Section 6.

Consider the scenario where $\bm{p}_{n}$ is known a priori. We can then use
the standard EWF with $N$ intervals with the cost corresponding to interval
$B_{i}$ as defined in (7). The following Corollary states the regret bound for
this algorithm.

###### Corollary 4.2.

If the sequence $\bm{p}_{n}$ is known a priori, an EWF that uses the intervals
$B_{i}$ as experts achieves $\sqrt{n\ln N/2}$ regret bound. Consequently,
given that $N=O(n)$, the regret bound of EWF is $O(\sqrt{n\ln n})$.

Note that, for the standard PEA with $N$ experts, $\sqrt{n\ln N/2}$ is the
lower bound for the regret for any randomized algorithm (Cesa-Bianchi et al.,
1997). Thus, Corollary 4.2 implies that for the problem at hand, under a
general loss function, no randomized algorithm has regret bound lower than
$O(\sqrt{n\ln n})$. Clearly, the lower bound $O(\sqrt{n\ln n})$ is much higher
than the lower bound of PEA, where the number of experts is independent of
$n$. This establishes the hardness of our problem. Adding to the difficulty,
$O(\sqrt{n\ln n})$ can only be achieved if $\bm{p}_{n}$ is known a priori,
which is not the case in practice.

With all preliminaries covered, we now present the HIL algorithms and their
regret bounds for full feedback and no-local feedback scenarios in Sections 5
and 6, respectively.

##  5\. Full Feedback

In this section, we consider the full-feedback scenario, where the algorithm
receives the ground truth $Y_{t}$ for all the samples, including those that
are not offloaded by accepting the S-ML inference. For this scenario, we
present the HIL-F algorithm in Algorithm 1. Some algorithmic rules for the
parameter updates are given later in Section 7. As explained in the previous
section, given $p_{t}$, we compute $q_{t}$, the probability to not offload.
Once the decision is made using $q_{t}$, the costs are received and the
weights are updated using (4) and (5). For simplicity, we denote the expected
cost received by HIL-F in round $t$ by $\bar{l}(\theta_{t},Y_{t})$ and is
given by

$\bar{l}(\theta_{t},Y_{t})={\mathbb{E}}_{Q_{t}}[{l}(\theta_{t},Y_{t})]=Y_{t}q_{t}+\beta(1-q_{t}),$

where the expectation is with respect to the probability distribution dictated
by $q_{t}$. Also, let
$\bar{L}(\bm{\theta},\bm{Y})=\sum_{t=1}^{n}\bar{l}(\theta_{t},Y_{t})$ denote
the total expected cost after $n$ rounds. In the theorem below, we provide a
regret bound for HIL-F.

###### Theorem 5.1.

For $\eta>0$, HIL-F achieves the following regret bound:

$R_{n}=\bar{L}(\bm{\theta},\bm{Y})-L(\bm{\theta^{*}},\bm{Y})\leq\frac{1}{\eta}\ln\frac{1}{\lambda_{\mathrm{min}}}+\frac{n\eta}{8}.$

###### Proof.

Recall from Lemma 4.1 that $p_{[i]},B_{i}=(p_{[i-1]},p_{[i]}]$, and
$l(B_{i},Y_{t})$ are the $i-$th smallest probability, intervals formed by
them, and the constant loss function within that interval at round $t$,
respectively. Also, $\lambda_{i}=p_{[i]}-p_{[i-1]}$ and $N\leq n+1$ correspond
to the length of the intervals $i$ and the total number of intervals,
respectively. Finally, $\lambda_{\mathrm{min}}=\min_{1\leq i\leq
N}\lambda_{i}$. Substituting $t=0$ in (5), we have $W_{1}=1$. Thus, taking
logarithm of $\frac{W_{n+1}}{W_{1}}$ gives,

$\displaystyle\ln\frac{W_{n+1}}{W_{1}}$
$\displaystyle=\ln\int_{0}^{1}e^{-\eta\sum_{t=1}^{n}l(x,Y_{t})}\,\mathrm{d}x$
$\displaystyle=\ln\sum_{i=1}^{N}\lambda_{i}e^{-\eta\sum_{t=1}^{n}l(B_{i},Y_{t})}$
$\displaystyle\geq\ln\max_{1\leq i\leq
N}\left(\lambda_{\mathrm{min}}e^{-\eta\sum_{t=1}^{n}l(B_{i},Y_{t})}\right)$
$\displaystyle=-\eta\min_{1\leq i\leq
N}\sum_{t=1}^{n}l(B_{i},Y_{t})-\ln\frac{1}{\lambda_{\mathrm{min}}}$ (9)
$\displaystyle=-\eta\min_{\theta\in[0,1]}\sum_{t=1}^{n}l(\theta,Y_{t})-\ln\frac{1}{\lambda_{\mathrm{min}}}.$
Now, we bound the ratio $\frac{W_{t+1}}{W_{t}}$.
$\displaystyle\ln\left(\frac{W_{t+1}}{W_{t}}\right)$
$\displaystyle=\ln\left(\frac{\int_{0}^{1}w_{t+1}(x)\,\mathrm{d}x}{W_{t}}\right)$
$\displaystyle=\ln\left(\int_{0}^{1}\frac{w_{t}(x)}{W_{t}}e^{-\eta
l(x,Y_{t})}\,\mathrm{d}x\right).$

1: Initialize: Set $w_{1}(\theta)=1,\forall\theta\in[0,1]$ and $N=1$.

2: for every sample in round $t=1,2,\ldots$ do

3: S-ML outputs ${p}_{t}$.

4: Compute $q_{t}$ using (5) and (6), and generate Bernoulli random variable
$Q_{t}$ with ${\mathbb{P}}(Q_{t}=1)=q_{t}$.

5: if $Q_{t}=1$ then

6: Accept the S-ML inference and receive cost $Y_{t}$.

7: else

8: Offload the sample and receive cost $\beta$.

9: end if

10: Find the loss function using (2).

11: if $p_{t}$ is not a repetition then

12: Update the intervals by splitting the interval containing $p_{t}$, at
$p_{t}$. Increment $N$ by $1$.

13: end if

14: Update the weights for all intervals using (4), based on the interval
positions with respect to $p_{t}$.

15: end for

Algorithm 1 The HIL-F algorithm for full feedback.

By using Hoeffding’s lemma333For a bounded random variable
$X\in[a,b],\ln({\mathbb{E}}[e^{sX}])\leq
s{\mathbb{E}}[X]+\frac{s^{2}(b-a)^{2}}{8}$. in the above equation, we get

$\displaystyle\ln\left(\frac{W_{t+1}}{W_{t}}\right)$
$\displaystyle\leq-\eta\int_{0}^{1}\frac{w_{t}(x)}{W_{t}}l(x,Y_{t})\,\mathrm{d}x+\frac{\eta^{2}}{8}$
$\displaystyle=-\eta\int_{0}^{{p}_{t}}\frac{w_{t}(x)}{W_{t}}l(x,Y_{t})\,\mathrm{d}x-\eta\int_{{p}_{t}}^{1}\frac{w_{t}(x)}{W_{t}}l(x,Y_{t})\,\mathrm{d}x+\frac{\eta^{2}}{8}$
$\displaystyle=-\eta\left(Y_{t}\int_{0}^{{p}_{t}}\frac{w_{t}(x)}{W_{t}}\,\mathrm{d}x+\beta\int_{{p}_{t}}^{1}\frac{w_{t}(x)}{W_{t}}\,\mathrm{d}x\right)+\frac{\eta^{2}}{8}.$
In the above step, we used (2). Now using (6) to replace the integrals, we get
$\displaystyle\ln\left(\frac{W_{t+1}}{W_{t}}\right)$
$\displaystyle\leq-\eta\left(Y_{t}q_{t}+\beta(1-q_{t})\right)+\frac{\eta^{2}}{8}$
(10) $\displaystyle=-\eta\bar{l}(\theta_{t},Y_{t})+\frac{\eta^{2}}{8}.$
Extending this expression telescopically, we get
$\displaystyle\ln\left(\frac{W_{n+1}}{W_{1}}\right)$
$\displaystyle=\ln\left(\prod_{t=1}^{n}\frac{W_{t+1}}{W_{t}}\right)=\sum_{t=1}^{n}\ln\frac{W_{t+1}}{W_{t}}$
(11)
$\displaystyle\leq\sum_{t=1}^{n}\left[-\eta\bar{l}(\theta_{t},Y_{t})+\frac{\eta^{2}}{8}\right]=-\eta\sum_{t=1}^{n}\bar{l}(\theta_{t},Y_{t})+\frac{n\eta^{2}}{8}.$

Using (9) and (11), we obtain

$\displaystyle-\eta\min_{\theta\in[0,1]}\sum_{t=1}^{n}l(\theta,Y_{t})-\ln\frac{1}{\lambda_{\mathrm{min}}}$
$\displaystyle\leq-\eta\sum_{t=1}^{n}\bar{l}(\theta_{t},Y_{t})+\frac{n\eta^{2}}{8}$
$\displaystyle\Rightarrow\bar{L}(\bm{\theta},\bm{Y})$ $\displaystyle\leq
L(\bm{\theta^{*}},\bm{Y})+\frac{1}{\eta}\ln\frac{1}{\lambda_{\mathrm{min}}}+\frac{n\eta}{8}$
$\displaystyle\Rightarrow R_{n}$
$\displaystyle\leq\frac{1}{\eta}\ln\frac{1}{\lambda_{\mathrm{min}}}+\frac{n\eta}{8}.$

In the last two steps above, we rearranged the terms and divided them with
$\eta$. ∎

Here, $\eta$ is the learning rate of the algorithm. To find $\eta^{*}$, the
$\eta$ that minimizes the above regret bound, we differentiate the regret
$R_{n}$ above to obtain

(12) $\displaystyle\eta^{*}=\sqrt{\frac{8\ln(1/\lambda_{\min})}{n}}.$

What remains is to find an approximation for $\lambda_{\min}$, which is
possible through various methods. For instance, one can use the precision of
the probability outputs, i.e., if the probability outputs are truncated to 6
decimal places, then we know that $\lambda_{\min}\geq 10^{-6}$. Further, some
datasets and/or S-ML models come with specific $\lambda_{\min}$. For example,
the probability output by MobileNet on the Imagenette dataset is 8-bit and
hence the probabilities are integer multiples of $1/256$. Even in cases where
all these methods fail, we see that a decent approximation for
$\lambda_{\min}$ is $\hat{\lambda}_{\min}={1}/{(n+1)}$.

##  6\. no-local feedback

Under no-local feedback, the cost is unknown once the inference of the S-ML is
accepted. For this scenario, we use the randomization idea used for label
efficient prediction problem (Cesa-Bianchi et al., 2005), which is a variant
of the PEA, where the costs in each round are not revealed, unless they are
inquired for, and there can only be at most $m$ inquires that can be made. For
this variant, EWF is modified as follows: in each round, a Bernoulli random
variable $Z$ is generated with probability $\epsilon$. If $Z=1$, then feedback
is requested and the costs are revealed. However, for our problem, the
algorithm for the label-efficient prediction problem is not applicable due to
the aspect of continuous expert space. Further, we do not have the notion of
inquiring about the costs at the ED. Instead, when $Z=1$, the sample has to be
offloaded to the ES with cost $\beta$ irrespective of the original decision
made using $q_{t}$. These samples provide the ED with the inference using
which the ED computes the cost $Y_{t}$.

To address the above aspects we follow the design principles of HIL-F and use
non-uniform discretization of the continuous domain and propose the HI
algorithm for no-local feedback (HIL-N), which is presented in Algorithm 2.
Even though HIL-N and HIL-F have a similar structure, the design of HIL-N is
significantly more involved and has the following key differences with HIL-F.
Firstly, in line $5$ of Algorithm 2, a Bernoulli random variable $Z_{t}$ is
generated with probability $\epsilon$. If $Z_{t}=1$, then the sample is
offloaded even if $Q_{t}=1$, and thus $Y_{t}$ is realized in this case. This
step is used to control the frequency of additional offloads carried out to
learn the ground truth $Y_{t}$. Secondly, instead of the loss function, the
weights are updated using a pseudo loss function $\tilde{l}(\theta_{t},Y_{t})$
defined as follows:

(13) $\displaystyle\tilde{l}(\theta_{t},Y_{t})$
$\displaystyle=\begin{cases}0&{p}_{t}\geq\theta_{t},Z_{t}=0;\quad\;[\text{{Do
Not Offload}}]\\\
\frac{Y_{t}}{\epsilon}&{p}_{t}\geq\theta_{t},Z_{t}=1;\qquad\;\;\,[\text{{Offload}}]\\\
\beta&{p}_{t}<\theta_{t}.\qquad\qquad\qquad[\text{{Offload}}]\end{cases}$

We also update the equations (4), (5) and (6) as follows:

(14) $\displaystyle w_{t+1}(\theta)$
$\displaystyle=w_{t}(\theta)e^{-\eta\tilde{l}_{t}(\theta,Y_{t})},$ (15)
$\displaystyle W_{t+1}$
$\displaystyle=\int_{0}^{1}w_{t+1}(\theta)\,\mathrm{d}\theta,\text{ and }$
(16) $\displaystyle q_{t}$
$\displaystyle=\frac{\int_{0}^{{p}_{t}}w_{t}(x)\,\mathrm{d}x}{W_{t}}.$

We emphasize that the pseudo loss function $\tilde{l}(\theta_{t},Y_{t})$ is
used only as part of the HIL-N algorithm, and is not the actual cost incurred
by the ED. The actual cost remains unchanged and it depends only on the
offloading decision and the correctness of the inference if not offloaded.
However, this actual incurred cost or the corresponding loss function
$l(\theta_{t},Y_{t})$ is unknown for the no-local feedback scenario, whenever
the sample is not offloaded and the local inference is accepted. This is
precisely the reason to introduce the pseudo loss function
$\tilde{l}(\theta_{t},Y_{t})$ which is known in each $t$, and can be used in
the HIL-N algorithm to update the weights. Recall from Section 5 that in
HIL-F, the cost incurred and the cost used to update the weights are the same,
and the incurred cost is $\beta$ if and only if $p_{t}<\theta_{t}$. However in
HIL-N, we use the pseudo cost to update the weights, and thus the actual cost
incurred can be equal to $\beta$ even if $p_{t}\geq\theta_{t}$. However, we
designed the pseudo-loss function such that

(17)
${\mathbb{E}}_{Z}\left[\tilde{l}(\theta_{t},Y_{t})\right]=l(\theta_{t},Y_{t}).$

Therefore, the pseudo loss function is an unbiased estimate of the actual loss
function, a fact that we will facilitate our analysis. Further, with the
addition of a random variable $Q$, the regret for HIL-N can be rewritten as

(18) $\displaystyle
R_{n}={\mathbb{E}}_{{\bm{Q}}Z}[L(\bm{\theta},\bm{Y})]-L(\bm{\theta^{*}},\bm{Y}),$

where ${\mathbb{E}}_{{\bm{Q}}Z}[\cdot]$ is expectation with respect to random
variables $\\{Q_{1},Q_{2},\ldots,Q_{n}\\}$ and Bernoulli random variable $Z$.

###### Theorem 6.1.

For $\eta,\epsilon>0$, HIL-N achieves the regret bound

$R_{n}\leq
n\beta\epsilon+\frac{n\eta}{2\epsilon}+\frac{1}{\eta}\ln(1/\lambda_{\text{min}}).$

###### Proof.

Step 1: Since the costs incurred and the loss function used for updating the
weights are different under HIL-N, we first find a bound for the difference
between the expected total cost received and the expected total cost obtained
using $\tilde{l}(\theta_{t},Y_{t})$. From Algorithm 2, we infer that sample
$t$ is offloaded if $Q_{t}=0$ or $Q_{t}=1$ and $Z_{t}=1$, and it is not
offloaded only when $Q_{t}=0$ and $Z_{t}=0$. Therefore, we have

(19) $\displaystyle{\mathbb{E}}_{Q_{t}Z}\left[l(\theta_{t},Y_{t})\right]$
$\displaystyle=\beta[1-q_{t}+q_{t}\epsilon]+q_{t}(1-\epsilon)Y_{t}.$ From
(13), we have $\displaystyle\tilde{l}(\theta_{t},Y_{t})$
$\displaystyle=\frac{Y_{t}}{\epsilon}\,\mathbbm{1}(\theta_{t}\leq
p_{t})\,\mathbbm{1}(Z_{t}=1)+\beta\,\mathbbm{1}(\theta_{t}>p_{t})$ (20)
$\displaystyle\Rightarrow{\mathbb{E}}_{Q_{t}Z}\left[\tilde{l}(\theta_{t},Y_{t})\right]$
$\displaystyle=Y_{t}q_{t}+\beta(1-q_{t}).$ From (19) and (20), we obtain
$\displaystyle{\mathbb{E}}_{Q_{t}Z}\left[l(\theta_{t},Y_{t})\right]-{\mathbb{E}}_{Q_{t}Z}\left[\tilde{l}(\theta_{t},Y_{t})\right]$
$\displaystyle=\beta\epsilon q_{t}-Y_{t}\epsilon q_{t}.$
$\displaystyle\Rightarrow{\mathbb{E}}_{{\bm{Q}}Z}\left[L(\bm{\theta},\bm{Y})\right]-\sum_{t=1}^{n}{\mathbb{E}}_{{\bm{Q}}Z}\left[\tilde{l}(\theta_{t},Y_{t})\right]$
$\displaystyle=\beta\epsilon\sum_{t=1}^{n}q_{t}-\epsilon\sum_{t=1}^{n}Y_{t}q_{t}$
$\displaystyle\leq n\beta\epsilon-\epsilon\sum_{t=1}^{n}Y_{t}q_{t}$ (21)
$\displaystyle\Rightarrow-\sum_{t=1}^{n}{\mathbb{E}}_{{\bm{Q}}Z}\left[\tilde{l}(\theta_{t},Y_{t})\right]$
$\displaystyle\leq-{\mathbb{E}}_{{\bm{Q}}Z}\left[L(\bm{\theta},\bm{Y})\right]+n\beta\epsilon.$

In the last step above, we have used $q_{t}\leq 1$, for all $t$.

Step 2: Using the same analysis to derive (9), we obtain

$\displaystyle\ln\left(\frac{W_{n+1}}{W_{1}}\right)$
$\displaystyle\geq-\eta\min_{\theta\in[0,1]}\sum_{t=1}^{n}\tilde{l}(\theta,Y_{t})-\ln\frac{1}{\lambda_{\mathrm{min}}}$
Note that, here we have $\tilde{l}(\theta,Y_{t})$ instead of
$l(\theta,Y_{t})$. Now using the fact that the expectation over the minimum is
upper bounded by the minimum over expectation, we get
$\displaystyle\Rightarrow{\mathbb{E}}_{Z}\left[\ln\left(\frac{W_{n+1}}{W_{1}}\right)\right]$
$\displaystyle\geq-\eta\min_{\theta\in[0,1]}\sum_{t=1}^{n}{\mathbb{E}}_{Z}\left[\tilde{l}(\theta,Y_{t})\right]-\ln\frac{1}{\lambda_{\mathrm{min}}}$
(22)
$\displaystyle\Rightarrow{\mathbb{E}}_{Z}\left[\ln\left(\frac{W_{n+1}}{W_{1}}\right)\right]$
$\displaystyle\geq-\eta
L(\bm{\theta^{*}},\bm{Y})-\ln(1/\lambda_{\mathrm{min}}).$

Step 3: In the following we find a bound for $\ln(\frac{W_{t+1}}{W_{t}})$.

$\displaystyle\ln\left(\frac{W_{t+1}}{W_{t}}\right)$
$\displaystyle=\ln\left(\frac{\int_{0}^{1}w_{t+1}(x)\,\mathrm{d}x}{W_{t}}\right)$
(using (14))
$\displaystyle=\ln\left(\int_{0}^{1}\frac{w_{t}(x)}{W_{t}}e^{-\eta\tilde{l}(x,Y_{t})}\,\mathrm{d}x\right)$
$\displaystyle\leq\ln\left(\int_{0}^{1}\frac{w_{t}(x)}{W_{t}}\left(1-\eta\tilde{l}(x,Y_{t})+\frac{\eta^{2}}{2}\tilde{l}(x,Y_{t}\right)^{2})\,\mathrm{d}x\right).$
In the above step, we used the fact that $e^{-x}\leq 1-x+x^{2}/2$. Rearranging
the terms, we get $\displaystyle\ln\left(\frac{W_{t+1}}{W_{t}}\right)$
$\displaystyle=\ln\left(1+\int_{0}^{1}\frac{w_{t}(x)}{W_{t}}\left(-\eta\tilde{l}(x,Y_{t})+\frac{\eta^{2}}{2}\tilde{l}(x,Y_{t})^{2}\right)\,\mathrm{d}x\right)$
$\displaystyle\leq\int_{0}^{1}\frac{w_{t}(x)}{W_{t}}\left(-\eta\tilde{l}(x,Y_{t})+\frac{\eta^{2}}{2}\tilde{l}(x,Y_{t})^{2}\right)\,\mathrm{d}x.$
The above step follows from the fact that $\ln(1+x)\leq x,\,\forall x>-1$.
(23) $\displaystyle\Rightarrow\ln\left(\frac{W_{t+1}}{W_{t}}\right)$
$\displaystyle\leq\int_{0}^{1}\frac{w_{t}(x)}{W_{t}}\left(-\eta\tilde{l}(x,Y_{t})+\frac{\eta^{2}}{2\epsilon}\tilde{l}(x,Y_{t})\right)\,\mathrm{d}x.$

In the last step, we have used the fact that
$\tilde{l}(x,Y_{t})\in[0,1/\epsilon]$. Note that the integral above can be
rearranged as follows:

$\displaystyle\int_{0}^{1}\frac{w_{t}(x)}{W_{t}}\tilde{l}(x,Y_{t})\,\mathrm{d}x$
$\displaystyle=\int_{0}^{p_{t}}\frac{w_{t}(x)}{W_{t}}\tilde{l}(x,Y_{t})\,\mathrm{d}x+\int_{p_{t}}^{1}\frac{w_{t}(x)}{W_{t}}\tilde{l}(x,Y_{t})\,\mathrm{d}x$
$\displaystyle=\frac{Y_{t}}{\epsilon}\mathbbm{1}(Z_{t}=1)q_{t}+\beta(1-q_{t}).$
Therefore, we have
$\displaystyle{\mathbb{E}}_{Z}\left[\int_{0}^{1}\frac{w_{t}(x)}{W_{t}}\tilde{l}(x,Y_{t})\,\mathrm{d}x\right]$
$\displaystyle=Y_{t}q_{t}+\beta(1-q_{t})$ (24)
$\displaystyle={\mathbb{E}}_{Q_{t}Z}\left[\tilde{l}(\theta_{t},Y_{t})\right],$
where we have used (20). Taking expectation with respect $Z$ on both sides in
(23) and then substituting (24),
$\displaystyle{\mathbb{E}}_{Z}\left[\ln\left(\frac{W_{t+1}}{W_{t}}\right)\right]$
$\displaystyle\leq-\eta{\mathbb{E}}_{Q_{t}Z}\left[\tilde{l}(\theta_{t},Y_{t})\right]+\frac{\eta^{2}}{2\epsilon}{\mathbb{E}}_{Q_{t}Z}\left[\tilde{l}(\theta_{t},Y_{t})\right]$
(25)
$\displaystyle\leq-\eta{\mathbb{E}}_{Q_{t}Z}\left[\tilde{l}(\theta_{t},Y_{t})\right]+\frac{\eta^{2}}{2\epsilon}.$
Above, we used the fact that
${\mathbb{E}}_{{\bm{Q}}Z}[\tilde{l}(\theta_{t},Y_{t})]\leq 1$. Taking
summation of (25) over $t$, we obtain
$\displaystyle{\mathbb{E}}_{Z}\left[\ln\prod_{t=1}^{n}\left(\frac{W_{t+1}}{W_{t}}\right)\right]$
$\displaystyle\leq-\eta\sum_{t=1}^{n}{\mathbb{E}}_{Q_{t}Z}\left[\tilde{l}(\theta_{t},Y_{t})\right]+\frac{n\eta^{2}}{2\epsilon}$
(26)
$\displaystyle\Rightarrow{\mathbb{E}}_{Z}\left[\ln\left(\frac{W_{n+1}}{W_{1}}\right)\right]$
$\displaystyle\leq-\eta\left({\mathbb{E}}_{{\bm{Q}}Z}\left[L(\bm{\theta},\bm{Y})\right]-n\beta\epsilon\right)+\frac{n\eta^{2}}{2\epsilon}.$

In the last step above, we have used (21). Combining (26) and (6) and
rearranging the terms, we obtain

$\displaystyle{\mathbb{E}}_{{\bm{Q}}Z}\left[L(\bm{\theta},\bm{Y})\right]-L(\bm{\theta^{*}},\bm{Y})\leq
n\beta\epsilon+\frac{n\eta}{2\epsilon}+\frac{1}{\eta}\ln(1/\lambda_{\text{min}}),$

which is the regret $R_{n}$ for HIL-N given by (18). ∎

1: Initialize: Set $w_{1}(\theta)=1,\forall\theta\in[0,1]$ and $N=1$.

2: for $t=1,2,\ldots$ do

3: S-ML outputs ${p}_{t}$.

14: Compute $q_{t}$ using weights from (14) and (15) and generate Bernoulli
random variables

$Q_{t}$ and $Z_{t}$ with ${\mathbb{P}}(Q_{t}=1)=q_{t}$ and
${\mathbb{P}}(Z_{t}=1)=\epsilon$.

5: if $Q_{t}=1$ and $Z_{t}=0$ then

6: Accept the S-ML inference and receive cost $Y_{t}$ (unknown).

7: else

8: Offload the sample and receive cost $\beta$.

9: end if

10: Find the pseudo loss function using (13).

11: if $p_{t}$ is not a repetition then

12: Update the intervals by splitting the interval containing $p_{t}$ at
$p_{t}$. Increment $N$ by $1$.

13: end if

14: Update the weights for all intervals using (14), based on the interval
positions with respect to $p_{t}$.

15: end for

Algorithm 2 The HIL-N algorithm

The bound in Theorem 6.1 neatly captures the effect of $\epsilon$ on the
regret. Note that the term $n\beta\epsilon$ is a direct consequence of
offloading sample $t$, when $Z_{t}=1$. We denote the bound by

(27) $\displaystyle
g(\epsilon,\eta)=n\beta\epsilon+\frac{n\eta}{2\epsilon}+\frac{1}{\eta}\ln(1/\lambda_{\text{min}}).$

We now minimize this bound and find the parameters that provide a bound that
is sublinear in $n$.

###### Lemma 6.2.

The function $g(\epsilon,\eta)$ defined in (27) has a global minimum at
$(\epsilon^{*},\eta^{*})$, where
$\eta^{*}=\left(\frac{2\ln^{2}({1}/{\lambda_{\text{min}}})}{\beta
n^{2}}\right)^{{1}/{3}}$ and $\epsilon^{*}=\sqrt{\frac{\eta}{2\beta}}.$ At
this minimum, we have,

$g(\epsilon^{*},\eta^{*})=3n^{{2}/{3}}\left(\frac{\beta\ln({1}/{\lambda_{\text{min}}})}{2}\right)^{{1}/{3}}.$

###### Proof.

We can easily see the strict convexity of $g(\epsilon,\eta)$ in each dimension
$\epsilon$ and $\eta$ independently, which tells us that any inflection point
of the function will be either a saddle point or a minima but not a maxima. We
equate the first-order partial derivatives to zero to get a set of points
given by the equations

(28) $\displaystyle\frac{\partial g}{\partial\epsilon}=0\Rightarrow\epsilon$
$\displaystyle=\sqrt{\frac{\eta}{2\beta}},$ (29) $\displaystyle\frac{\partial
g}{\partial\eta}=0\Rightarrow\eta$
$\displaystyle=\sqrt{\frac{2\epsilon\ln({1}/{\lambda_{\text{min}}})}{n}}.$

However, it still remains to check if this point is unique and if this point
is indeed a minimum, but not a saddle point. Seeing the uniqueness is
straightforward by noting that these two expressions correspond to two non-
decreasing, invertible curves in the $\epsilon\text{\textendash}\eta$ plane,
and thus they have a unique intersection. We find this intersection denoted
using $(\epsilon^{*},\eta^{*})$ by substituting (28) in (29). We obtain

$\displaystyle\eta^{*}=\sqrt{\frac{2\epsilon^{*}\ln({1}/{\lambda_{\text{min}}})}{n}}=\sqrt{\frac{2\sqrt{{\eta^{*}}/{2\beta}}\ln({1}/{\lambda_{\text{min}}})}{n}}.$

We get $\eta^{*}$ and $\epsilon^{*}$ by simplifying the above equation and
then substituting it back in (28). Finally, to prove that
$(\epsilon^{*},\eta^{*})$ is indeed a minimum, we verified that the
determinant of the Hessian at $(\epsilon^{*},\eta^{*})$ is positive, the steps
of which are not presented due to space constraints. Since
$(\epsilon^{*},\eta^{*})$ is a unique minimum, it should be the global
minimum. The proof is complete by substituting $(\epsilon^{*},\eta^{*})$ in
(27). ∎

Now, with the above Lemma in hand, we provide a sublinear regret bound for
HIL-N in the following corollary.

###### Corollary 6.3.

With $\eta=\left(\frac{2\ln^{2}({1}/{\lambda_{\text{min}}})}{\beta
n^{2}}\right)^{{1}/{3}}$ and
$\epsilon=\min\\{1,\sqrt{\frac{\eta}{2\beta}}\\}$, HIL-N achieves a regret
bound sublinear in $n$:

$R_{n}\leq
3n^{{2}/{3}}\left(\frac{\beta\ln({1}/{\lambda_{\text{min}}})}{2}\right)^{{1}/{3}}$

###### Proof.

Note that, if $\sqrt{\frac{\eta}{2\beta}}\leq 1$, then
$\epsilon=\sqrt{\frac{\eta}{2\beta}}$ and the results directly follows from
Lemma 6.2. If $\sqrt{\frac{\eta}{2\beta}}>1$, then we have $\epsilon=1$.
Substituting $\eta$ value in $\sqrt{\frac{\eta}{2\beta}}>1$, we obtain

(30)
$\displaystyle\beta<\sqrt{\frac{\sqrt{2}\ln({1}/{\lambda_{\text{min}}})}{n}}.$

Since $\epsilon=1$, we will have $Z_{t}=1$ for all $t$, i.e., HIL-N will
always offload. Therefore, in this case, the total cost incurred by HIL-N is
equal to $n\beta$. Now, using (30), we obtain

$\displaystyle
n\beta<\sqrt{{\sqrt{2}\ln({1}/{\lambda_{\text{min}}})}\big{/}{n}}=\sqrt{\sqrt{2}n\ln({1}/{\lambda_{\text{min}}})}.$

Thus, when (30) holds and we have $\epsilon=1$, the total cost itself is
$O(n^{\frac{1}{2}})$ and therefore regret cannot be greater than
$O(n^{\frac{1}{2}})$. The result follows by noting that $O(n^{\frac{2}{3}})$
is the larger bound. ∎

Remarks:  It is worth noting the following:

  1. (1)

The proof steps in Theorem 5.1 closely follow some analysis of the standard
EWF for PEA with the added complexity to account for the continuous experts
and non-uniform discretization. The analysis for HIL-N is novel. In
particular, the design of the unbiased estimator, steps 1 and 3 in the proof
of Theorem 6.1, and the proof of Lemma 6.2 have new analysis.

  2. (2)

The computational complexity of HIL-N is of the same order as that of HIL-F
due to the similar interval generation steps.

  3. (3)

We can remove the dependency of $\eta$ on $\lambda_{\mathrm{min}}$ and $n$ by
using a sequence of dynamic learning rates: $\eta_{t}=\frac{1}{\sqrt{t+1}}$.
Sublinear regret bounds can be obtained for such a modification but we omit
the analysis due to space constraints.

##  7\. Algorithm Implementation and Computational complexity

Recall from Lemma 4.1 that cumulative loss is a piece-wise constant function.
We use this fact to compute the continuous domain integral in (6) efficiently
by splitting the function into multiple rectangular areas of nonuniform base
and then summing them up, where we do not make any discretization error but
compute the exact value of the integral. In each round $t$, we increase the
number of intervals by at most $1$ as we split the interval containing
${p}_{t}$ at ${p}_{t}$. After receiving ${p}_{t}$, we thus have $N\leq t+1$
intervals with boundaries given by ${p}_{[0]}=0$, ${p}_{[i]},1\leq i\leq t$,
and ${p}_{[N]}=1$. The weight $w_{i,t},i\leq t+1$ of the interval $i$ in round
$t$ is then updated based on, 1) the weights in round $t-1$, and 2) the
position of the interval with respect to ${p}_{t}$. Note that in lines $12$ of
HIL-F and HIL-N, we state that the interval containing $p_{t}$ should be split
and in line $14$ we state that the weights should be computed, but without
giving more details. Below, we present four algorithmic rules that can be used
to compute the probability $q_{t}$, interval boundaries $\\{p_{[i]}\\}$ and
weights $\\{w_{i,t}\\}$, which needs to be computed in order. Let $j$ be the
interval strictly below ${p}_{t}$ and $dup$ be a boolean variable denoting
duplicate ${p}_{t}$.

$\displaystyle(i)$ $\displaystyle\;\;\;j$
$\displaystyle\leftarrow\max\\{i:p_{[i]}<{p}_{t}\\}.$ $\displaystyle(ii)$
$\displaystyle\;\;\;dup$ $\displaystyle\leftarrow FALSE\text{, if
}{p}_{\tau}\neq{p}_{t}\,\forall\tau<t,\ TRUE\text{ otherwise}.$
$\displaystyle(iii)$ $\displaystyle\;\;\;q_{t}$
$\displaystyle\leftarrow\frac{\sum_{i=1}^{j}w_{i,t}(p_{[i]}-p_{[i-1]})+w_{j+1,t}({p}_{t}-p_{[i]})}{\sum_{i=1}^{N}w_{i,t}(p_{[i]}-p_{[i-1]})}$
$\displaystyle(iv)$ $\displaystyle\;\;\;N$
$\displaystyle\leftarrow\begin{cases}N&(dup=TRUE),\\\
N+1&(dup=FALSE).\end{cases}$ $\displaystyle(v)$ $\displaystyle\;\;\;{p}_{[i]}$
$\displaystyle\leftarrow\begin{cases}{p}_{[i]}&i\leq j\text{ or }(dup=TRUE)\\\
{p}_{t}&i=j+1\text{ and }(dup=FALSE)\\\ {p}_{[i-1]}&j+1<i\leq N\text{ and
}(dup=FALSE)\\\ \end{cases}$ $\displaystyle(vi)$ $\displaystyle\;\;\;w_{i,t}$
$\displaystyle\leftarrow\begin{cases}w_{i,t-1}e^{-\eta\beta}&{p}_{[i]}>{p}_{t},\;(dup=TRUE)\\\
w_{i-1,t-1}e^{-\eta\beta}&{p}_{[i]}>{p}_{t},\;(dup=FALSE)\\\ w_{i,t-1}e^{-\eta
Y_{t}}&{p}_{[i]}\leq{p}_{t},\text{HIL-F}\\\ w_{i,t-1}e^{-\eta
Y_{t}/\epsilon}&{p}_{[i]}\leq{p}_{t},Z_{t}=1,\text{HIL-N}\\\
w_{i,t-1}&{p}_{[i]}\leq{p}_{t},Z_{t}=0,\text{HIL-N}.\end{cases}$

In every round of computation, we need a certain constant number of additions,
multiplications, and comparisons per interval, irrespective of the number of
samples already processed. Thus, the computational complexity in each round is
in the order of the number of intervals present in that interval. Now consider
a set of $n$ input images. In our proposed algorithms, the number of intervals
in round $t$ is upper bounded by $t+1$. Thus, the worst-case computational
complexity of HIL-F in round $t$ is $O(t)$. Further, when
$\lambda_{\mathrm{min}}$ is the minimum difference between any two
probabilities, the maximum number of intervals is clearly upper bounded by
${1}/{\lambda_{\mathrm{min}}}$, which reduces the complexity to
$O\left(\min\\{t,{1}/{\lambda_{\mathrm{min}}}\\}\right)$.

###### Proposition 0.

The computational complexity of HIL-F and HIL-N in round $t$ is
$O\left(\min\\{t,1/\lambda_{\mathrm{min}}\\}\right)$.

Note that there can be many intervals with lengths larger than
$\lambda_{\mathrm{min}}$, and thus the number of intervals can typically be
less than ${1}/{\lambda_{\mathrm{min}}}$, which reduces the complexity in
practice. As discussed earlier, one might approximate $\lambda_{\mathrm{min}}$
to $1/n$ in some datasets, which gives us a complexity of
$O\left(\min\\{t,n\\}\right)$ in terms of the number of images. Also note that
the above complexities are that of round $t$, and to get the total complexity
of the algorithm, one has to sum it overall $t$.

Finally, we note that there can be datasets where
$\lambda_{\mathrm{min}}<{1}/{n}$ and for such cases the complexity from
Proposition 7.1 will be $O(t)$. For instance, this is the case for the MNIST
dataset but is not applicable for the Imagenette dataset with
$\lambda_{\mathrm{min}}=\frac{1}{256}$. In this regard, we propose a practical
modification to the algorithms by limiting the interval size to a minimum of
$\Delta_{\mathrm{min}}>\lambda_{\mathrm{min}}$, where $\Delta_{\mathrm{min}}$
is a parameter chosen based on the complexity and cost tradeoffs. One then
considers any different probabilities that lie within $\Delta_{\mathrm{min}}$
of each other as duplicates while generating new intervals in line $12$ of
HIL-F and HIL-N, which further reduces the complexity to
$O\left(\min\\{t,{1}/{\Delta_{\mathrm{min}}}\\}\right)$. We observed by
choosing different values of $\lambda_{\mathrm{min}}$ (including
$\frac{1}{n}$) that over a range of values, there is a notable reduction in
algorithm runtime, with negligible difference in the expected average costs.

##  8\. Numerical Results

In this section, we evaluate the performance of the proposed algorithms HIL-F
and HIL-N by comparing them against each other as well as further benchmarks.
Our evaluation scenario consists of two different classifiers and four
different datasets. Firstly, we use 8-bit quantized MobileNet (Howard et al.,
2017; GitHub Repository, Keras.io, 2022), with width parameter $0.25$, to
classify the Imagenette and Imagewoof datasets (Howard and Gugger, 2020). We
use $0.25$ for the width parameter as it reduces the number of filters in each
layer drastically, and the resulting MobileNet has a size of $0.5$ MB,
suitable to fit on an IoT sensor. Imagenette and Imagewoof are derived from
Imagenet (Deng et al., 2009) and each contains a mixture of 10 different image
classes with approximately 400 images per class. Out of the two, Imagewoof is
a tougher dataset for classification as it contains $10$ different breeds of
dogs. Next, we use the test set of MNIST dataset (LeCun and Cortes, 2010),
which contains 10000 images of handwritten digits from $0$ through $9$. For
this dataset, we train a linear classifier (without regularizer), as the S-ML
model. We convert the labels into vectors of size $10$. For label $l$, i.e.,
digit $l$, we use all zero vectors except in $l$-th location, where the value
is $1$. After training the classifier, we scale the output to obtain a
probability distribution over the $10$ labels. The top-1 accuracy we obtain is
$86$%. Finally for CIFAR-10 (Krizhevsky et al., 2009; Krizhevsky, 2009), we
use a readily available trained CNN (GitHub Repository, 2021) with accuracy
$84\%$ as the S-ML model. Note that for all the simulations we invoke the
assumption that the L-ML models have accuracy $1$.

As explained in Section 3, we choose the expected average regret
$\frac{1}{n}{\mathbb{E}}_{\bm{Y}}[R_{n}]$ and expected average cost
$\frac{1}{n}{\mathbb{E}}_{\bm{Y},\pi}[{L}(\bm{\theta},\bm{Y})]$ as the metrics
to compare the performance. Recall that these metrics are upper bounded by
$1$, which is the maximum cost in a single round. For simplicity, we refer to
them by average regret and average cost, respectively. For the simulations, we
take $100$ randomizations of the input sequence $Y$ and for each of these
randomizations we repeat the simulations $100$ times. The randomization is for
the statistical convergence across the sequences of $\bm{Y}$
$(i.e.,{\mathbb{E}}_{\bm{Y}}[.]$), and the repetitions are for the convergence
over the randomized decisions based on $q_{t}$ made in line 4 of the
algorithms (i.e., ${\mathbb{E}}_{\pi}[.]$). We also checked with higher
numbers of randomizations and repetitions and verified that $100\times 100$
iterations are sufficient for statistical convergence. We use $\eta$ and
$\epsilon$ from (12) and Lemma 6.2, unless mentioned otherwise.

We use the following four baseline algorithms (i.e., policies) to compare the
performance of HIL-F and HIL-N.

  1. (1)

Genie – a non-causal policy, where only those images that are misclassified by
S-ML are offloaded.

  2. (2)

$\bm{\theta^{*}}$ – an optimal fixed-$\theta$ policy. We compute this cost by
running a brute-force grid search over all $\theta$.

  3. (3)

Full offload – all images are offloaded to the ES.

  4. (4)

No offload – all images are processed locally.

Before we go to the figures, we show the number of images offloaded and the
number of images misclassified by different policies for the Imagenette
dataset with a total of 3925 images in TABLE 2. These results are basically
the data point with $\beta=0.5$ from Fig. 3(a) (explained later). We can
immediately infer from the table that HIL-F achieves an offloading rate and
misclassification rate very close to that of the optimum fixed-$\theta$
policy. Further, HIL-F offloads approximately the same number of images as the
optimum fixed-$\theta$ policy and achieves a top-1 accuracy of $92.3$%.
Contrast this with a much lower accuracy output of $43.2$% by the chosen
MobileNet as the S-ML. This also asserts that our framework with the cost
structure $\beta$ and $Y$ indeed facilitates HI by reducing the number of
offloaded images that are correctly classified by S-ML. Note that HIL-N also
achieves high accuracy $95.2$%, but it achieves this at the cost of offloading
more images, $18$% more than $\theta^{*}$. This is because HIL-N can only get
feedback from L-ML and chooses to offload more images to learn the best
threshold. Note that a $\beta$ of $0.5$ corresponds to minimizing the sum of
the total number of errors and offloads. One can the optimum in this case
visually from Fig. 2 in Section 1, where all images below the threshold and
all misclassified images above the threshold add 1 to the total costs.

Images | Genie | Full offload | No offload | $\theta^{*}$ | HIL-F | HIL-N
---|---|---|---|---|---|---
offloaded | 2230 | 3925 | 0 | 2588 | 2626 | 3056
Misclassified | 0 | 0 | 2230 | 303 | 304 | 191
Table 2. Number of images offloaded and misclassified for different policies
on Imagenette with $\beta=0.5$ and optimal $\eta,\epsilon$.

In Fig. 3, we compare the two proposed algorithms HIL-F and HIL-N with the
baselines for all four datasets by plotting the average cost vs. $\beta$.
Here, Fig. 3(a) through Fig. 3(d) correspond to Imagenette, Imagewoof, MNIST,
and CIFAR-10 datasets, respectively. Observe that HIL-F performs very close to
${\theta^{*}}$, having at most $6$% higher total cost than $\theta^{*}$ among
all four figures irrespective of the absolute value of the cost or the dataset
considered. In Fig. 3(a) we have also added an inset where we have enlarged a
portion of the figure to highlight the distinction between the proposed
policies and ${\theta^{*}}$. The vertical difference between these two
corresponds to the corresponding regret. We can see that HIL-F achieves a cost
very close to that of ${\theta^{*}}$, having at most $4.5$% higher total cost
than $\theta^{*}$ throughout the range of $\beta$. For instance for the
Imagenette dataset with $\beta=0.5$, this increase is less than $1.4$%. HIL-N
on the other hand is more sensitive to the properties of the considered
dataset. It performs much better than the Full offload policy and also follows
a similar trend as that of the HIL-F. However, for larger values of $\beta$
the comparative performance of HIL-N with the No offload policy deteriorates.
This is because even when offloading is not optimum, HIL-N is offloading with
a fixed probability $\epsilon>0$, to learn the ground truth $Y$. Furthermore,
we can see by comparing the four figures that, lower the accuracy of S-ML –
for instance in Fig. 3(b) – larger will be the range of $\beta$ for which
HIL-N performs better than both No offload and Full offload policies.

(a) Imagenette dataset.

(b) Imagewoof dataset

(c) MNIST dataset

(d) CIFAR-10 dataset

Figure 3. Average cost incurred by various offloading policies vs. $\beta$ for
different datasets. The bound optimizing $\eta$ and $\epsilon$ are used
assuming a prior knowledge of $\lambda_{\text{min}}$. Note that the curves
corresponding to $\theta^{*}$ and HIL are very close to each other.

In Fig. 4 we show the dependency of the algorithm on the learning rate
parameter $\eta$ plotting the average regret obtained by the proposed
algorithms vs. the number of images for $\beta=0.7$ and different values of
$\eta$. We show the plots for theoretical bound-optimizing $\eta$, and for
HIL-F we also show the plots with a few other $\eta$ for comparison. First,
note that the HIL-N learns slower compared to HIL-F which is an intuitive
behavior because HIL-N cannot learn from those images that are not offloaded.
Also, note that the difference in regret incurred by using
$\hat{\lambda}_{\min}=1/(n+1)$ as an approximation of $\lambda_{\min}$ is
minimal – in the order $10^{-3}$. Recall that the optimum $\eta$ that we
proposed is an optimum for the regret bound, but not necessarily for the
regret itself. Hence, it is worth noting that, while using a larger $\eta$ is
slightly beneficial in this particular dataset, this turns out to be
deleterious for the regret bound, which is valid for any given dataset.
Further, too large an $\eta$ will give too large weights to the thresholds
that achieved lower costs in the past, making the algorithm resemble a
deterministic algorithm that cannot guarantee performance (Cesa-Bianchi and
Lugosi, 2006).

Figure 4. Average regret vs. Number of images for $\beta=0.7$ using HIL-F and
HIL-N on the imagenette database with various $\eta$.

##  9\. Conclusion

We considered an ED embedded with S-ML and an ES having L-ML and explored the
idea of HI, where the ED can benefit from only offloading samples for which
S-ML outputs incorrect inference. Since an ideal implementation of HI is
infeasible, we proposed a novel meta-learning framework where the ED decides
to offload or not to offload after observing the maximum probability $p$ in
the probability mass function output by S-ML. For the full feedback scenario,
we proposed HIL-F, which assigns exponential weights to decision thresholds
$\theta\in[0,1]$ based on past costs and probabilistically chooses a
threshold, based on $p$, to offload or not. For the no-local feedback
scenario, we proposed HIL-N, which uses an unbiased estimator of the cost and
generates an additional Bernoulli random variable $Z$ and always offloads if
$Z=1$. A novel and unique aspect of the proposed algorithms is that we use
non-uniform discretization, i.e., create new intervals in each round based on
$p$ and use these intervals as experts. We proved that HIL-F and HIL-N have
sublinear regret bounds $\sqrt{{n\ln(1/\lambda_{\text{min}})}/{2}}$ and
$O\left(n^{{2}/{3}}\ln^{{1}/{3}}(1/\lambda_{\text{min}})\right)$,
respectively, and have runtime complexity
$O\left(\min\\{t,{1}/{\lambda_{\mathrm{min}}}\\}\right)$ in round $t$. Here,
it is worth noting that the term $1/\lambda_{\text{min}}$ acts similarly to
the number of experts in PEA as far as regret bounds are concerned and we have
explained simple methods to approximate it. For verifying the results, we
generated values of ${p}$ for four datasets, namely, Imagenette, Imagewoof,
MNIST, and CIFAR-10, and compared the performance of HIL-F and HIL-N with four
different baseline policies, including the fixed-$\theta$ policy. The cost
achieved by the proposed algorithms is always lower compared to the Full
offload and the No offload policies and is close to the cost achieved by the
optimum fixed-$\theta$ policy for a wide range of $\beta$. More importantly,
the algorithms achieve much higher accuracy compared to S-ML while offloading
a marginally higher number of images compared to the optimum fixed-$\theta$
policy.

## References

  * (1)
  * Auer et al. (2007) Peter Auer, Ronald Ortner, and Csaba Szepesvári. 2007\.  Improved Rates for the Stochastic Continuum-Armed Bandit Problem. In _Learning Theory_ , Nader H. Bshouty and Claudio Gentile (Eds.). Springer Berlin Heidelberg, 454–468.
  * Bubeck (2011) Sébastien Bubeck. 2011\.  Introduction to online optimization.  (2011).
  * Bubeck and Cesa-Bianchi (2012) Sébastien Bubeck and Nicolò Cesa-Bianchi. 2012.  Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems.  _Foundations and Trends® in Machine Learning_ 5, 1 (2012), 1–122.  https://doi.org/10.1561/2200000024
  * Bubeck et al. (2011) Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. 2011.  X-Armed Bandits.  _J. Mach. Learn. Res._ 12, null (jul 2011), 1655–1695.
  * Cesa-Bianchi et al. (1997) Nicolò Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth. 1997.  How to Use Expert Advice.  _J. ACM_ 44, 3 (may 1997), 427–485.  https://doi.org/10.1145/258128.258179
  * Cesa-Bianchi and Lugosi (2006) Nicolò Cesa-Bianchi and Gábor Lugosi. 2006.  _Prediction, learning, and games._ Cambridge University Press. I–XII, 1–394 pages.
  * Cesa-Bianchi et al. (2005) N. Cesa-Bianchi, G. Lugosi, and G. Stoltz. 2005.  Minimizing regret with label efficient prediction.  _IEEE Transactions on Information Theory_ 51, 6 (2005), 2152–2162.  https://doi.org/10.1109/TIT.2005.847729
  * Cuervo et al. (2010) Eduardo Cuervo, Aruna Balasubramanian, Dae ki Cho, Alec Wolman, Stefan Saroiu, Ranveer Chandra, and Paramvir Bahl. 2010.  MAUI: making smartphones last longer with code offload.. In _MobiSys_. ACM, 49–62.
  * Deng et al. (2009) Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. 2009\.  Imagenet: A large-scale hierarchical image database. In _Proc. IEEE CVPR_. 248–255.
  * Deng et al. (2020) Lei Deng, Guoqi Li, Song Han, Luping Shi, and Yuan Xie. 2020.  Model Compression and Hardware Acceleration for Neural Networks: A Comprehensive Survey.  _Proc. IEEE_ 108, 4 (2020), 485–532.  https://doi.org/10.1109/JPROC.2020.2976475
  * Denton et al. (2014) Emily Denton, Wojciech Zaremba, Joan Bruna, Yann LeCun, and Rob Fergus. 2014.  Exploiting Linear Structure within Convolutional Networks for Efficient Evaluation. In _Proc. NeurIPS_. 1269–1277.
  * Fresa and Champati (2021) Andrea Fresa and Jaya Prakash Champati. 2021.  Offloading Algorithms for Maximizing Inference Accuracy on Edge Device Under a Time Constraint.  _CoRR_ abs/2112.11413 (2021).  https://arxiv.org/abs/2112.11413
  * GitHub Repository (2021) GitHub Repository. 2021\.  Retrieving the predictions in the CIFAR-10 dataset.  Retrieved January 26, 2023 from https://github.com/TracyRenee61/CIFAR_10/blob/main/CIFAR10_PyTprch_83_accuracy.ipynb
  * GitHub Repository, Keras.io (2022) GitHub Repository, Keras.io. 2022\.  Retrieved January 26, 2023 from https://keras.io/api/applications/mobilenet/
  * Guo et al. (2019) Songtao Guo, Jiadi Liu, Yuanyuan Yang, Bin Xiao, and Zhetao Li. 2019.  Energy-Efficient Dynamic Computation Offloading and Cooperative Task Scheduling in Mobile Cloud Computing.  _IEEE Transactions on Mobile Computing_ 18, 2 (2019), 319–333.  https://doi.org/10.1109/TMC.2018.2831230
  * Han et al. (2015) Song Han, Jeff Pool, John Tran, and William J. Dally. 2015\.  Learning Both Weights and Connections for Efficient Neural Networks. In _Proc. NeurIPS_. 1135–1143.
  * Howard et al. (2017) Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. 2017\.  MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications.  _CoRR_ abs/1704.04861 (2017).  arXiv:1704.04861
  * Howard and Gugger (2020) Jeremy Howard and Sylvain Gugger. 2020.  Fastai: A Layered API for Deep Learning.  _Information_ 11, 2 (2020).  https://github.com/fastai/imagenette
  * Hu et al. (2019) Chuang Hu, Wei Bao, Dan Wang, and Fengming Liu. 2019\.  Dynamic Adaptive DNN Surgery for Inference Acceleration on the Edge. In _IEEE INFOCOM 2019 - IEEE Conference on Computer Communications_. 1423–1431.  https://doi.org/10.1109/INFOCOM.2019.8737614
  * Hu and Li (2022) Chenghao Hu and Baochun Li. 2022.  Distributed Inference with Deep Learning Models across Heterogeneous Edge Devices. In _Proc. IEEE INFOCOM_. 330–339.  https://doi.org/10.1109/INFOCOM48880.2022.9796896
  * Kang et al. (2017) Yiping Kang, Johann Hauswald, Cao Gao, Austin Rovinski, Trevor Mudge, Jason Mars, and Lingjia Tang. 2017.  Neurosurgeon: Collaborative Intelligence Between the Cloud and Mobile Edge. In _in Proc. ASPLOS_. Association for Computing Machinery, 615–629.  https://doi.org/10.1145/3037697.3037698
  * Krizhevsky (2009) Alex Krizhevsky. 2009\.  The CIFAR-10 dataset.  Retrieved January 26, 2023 from https://www.cs.toronto.edu/~kriz/cifar.html
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, et al. 2009\.  Learning multiple layers of features from tiny images.  (2009).
  * LeCun and Cortes (2010) Yann LeCun and Corinna Cortes. 2010.  MNIST handwritten digit database.  http://yann.lecun.com/exdb/mnist/.  (2010).  http://yann.lecun.com/exdb/mnist/
  * Li et al. (2020) En Li, Liekang Zeng, Zhi Zhou, and Xu Chen. 2020\.  Edge AI: On-Demand Accelerating Deep Neural Network Inference via Edge Computing.  _IEEE Transactions on Wireless Communications_ 19, 1 (2020), 447–457.  https://doi.org/10.1109/TWC.2019.2946140
  * Nikoloska and Zlatanov (2021) Ivana Nikoloska and Nikola Zlatanov. 2021.  Data Selection Scheme for Energy Efficient Supervised Learning at IoT Nodes.  _IEEE Communications Letters_ 25, 3 (2021), 859–863.  https://doi.org/10.1109/LCOMM.2020.3034992
  * Ogden and Guo (2020) Samuel S. Ogden and Tian Guo. 2020.  MDINFERENCE: Balancing Inference Accuracy and Latency for Mobile Applications. In _Proc. IEEE IC2E_. 28–39.  https://doi.org/10.1109/IC2E48712.2020.00010
  * Rastegari et al. (2016) Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi. 2016.  XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks. In _Computer Vision – ECCV 2016_ , Bastian Leibe, Jiri Matas, Nicu Sebe, and Max Welling (Eds.). Springer International Publishing, Cham, 525–542.
  * Sanchez-Iborra and Skarmeta (2020) Ramon Sanchez-Iborra and Antonio F. Skarmeta. 2020.  TinyML-Enabled Frugal Smart Objects: Challenges and Opportunities.  _IEEE Circuits and Systems Magazine_ 20, 3 (2020), 4–18.  https://doi.org/10.1109/MCAS.2020.3005467
  * Satyanarayanan et al. (2009) Mahadev Satyanarayanan, Paramvir Bahl, Ramon Caceres, and Nigel Davies. 2009.  The Case for VM-Based Cloudlets in Mobile Computing.  _IEEE Pervasive Computing_ 8, 4 (2009), 14–23.  https://doi.org/10.1109/MPRV.2009.82
  * Singh (2021) Shashank Singh. 2021\.  Continuum-Armed Bandits: A Function Space Perspective. In _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ _(Proceedings of Machine Learning Research, Vol. 130)_ , Arindam Banerjee and Kenji Fukumizu (Eds.). PMLR, 2620–2628.
  * Sundar et al. (2020) Sowndarya Sundar, Jaya Prakash Varma Champati, and Ben Liang. 2020\.  Multi-user Task Offloading to Heterogeneous Processors with Communication Delay and Budget Constraints.  _IEEE Transactions on Cloud Computing_ (2020), 1–1.  https://doi.org/10.1109/TCC.2020.3019952
  * Taylor et al. (2018) Ben Taylor, Vicent Sanz Marco, Willy Wolff, Yehia Elkhatib, and Zheng Wang. 2018.  Adaptive Deep Learning Model Selection on Embedded Systems.  _SIGPLAN Not._ 53, 6 (jun 2018), 31–43.  https://doi.org/10.1145/3299710.3211336
  * Teerapittayanon et al. (2016) Surat Teerapittayanon, Bradley McDanel, and H.T. Kung. 2016\.  BranchyNet: Fast inference via early exiting from deep neural networks. In _Proc. ICPR_. 2464–2469.
  * Wang et al. (2018) Junjue Wang, Ziqiang Feng, Zhuo Chen, Shilpa George, Mihir Bala, Padmanabhan Pillai, Shao-Wen Yang, and Mahadev Satyanarayanan. 2018.  Bandwidth-Efficient Live Video Analytics for Drones Via Edge Computing. In _2018 IEEE/ACM Symposium on Edge Computing (SEC)_. 159–173.  https://doi.org/10.1109/SEC.2018.00019
  * Wang et al. (2019b) Junjue Wang, Ziqiang Feng, Zhuo Chen, Shilpa Anna George, Mihir Bala, Padmanabhan Pillai, Shao-Wen Yang, and Mahadev Satyanarayanan. 2019b.  Edge-Based Live Video Analytics for Drones.  _IEEE Internet Computing_ 23, 4 (2019), 27–34.  https://doi.org/10.1109/MIC.2019.2909713
  * Wang et al. (2020) Xiaofei Wang, Yiwen Han, Victor C. M. Leung, Dusit Niyato, Xueqiang Yan, and Xu Chen. 2020\.  Convergence of Edge Computing and Deep Learning: A Comprehensive Survey.  _IEEE Communications Surveys and Tutorials_ 22, 2 (2020), 869–904.  https://doi.org/10.1109/COMST.2020.2970550
  * Wang et al. (2019a) Zizhao Wang, Wei Bao, Dong Yuan, Liming Ge, Nguyen H. Tran, and Albert Y. Zomaya. 2019a.  SEE: Scheduling Early Exit for Mobile DNN Inference during Service Outage. In _in Proc. MSWIM_. 279–288.  https://doi.org/10.1145/3345768.3355917
  * Wortsman et al. (2022) Mitchell Wortsman, Gabriel Ilharco, Samir Ya Gadre, Rebecca Roelofs, Raphael Gontijo-Lopes, Ari S Morcos, Hongseok Namkoong, Ali Farhadi, Yair Carmon, Simon Kornblith, and Ludwig Schmidt. 2022.  Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time. In _Proceedings of the 39th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 162)_. PMLR, 23965–23998.