# Distributed no-regret edge resource allocation with limited communication

Saad Kriouile, Dimitrios Tsilimantos, and Theodoros Giannakas
Huawei Paris Research Centre, France<EMAIL_ADDRESS>This work was
supported by the CHIST-ERA LeadingEdge project, grant CHIST-ERA-18-SDCDN-004
through ANR grant number ANR-19-CHR3-0007-06. The three authors contributed
equally; the order is random.

###### Abstract

To accommodate low latency and computation-intensive services, such as the
Internet-of-Things (IoT), 5G networks are expected to have cloud and edge
computing capabilities. To this end, we consider a generic network setup where
devices, performing analytics-related tasks, can partially process a task and
offload its remainder to base stations, which can then reroute it to cloud
and/or to edge servers. To account for the potentially unpredictable traffic
demands and edge network dynamics, we formulate the resource allocation as an
online convex optimization problem with service violation constraints and
allow limited communication between neighboring nodes. To address the problem,
we propose an online distributed (across the nodes) primal-dual algorithm and
prove that it achieves sublinear regret and violation; in fact, the achieved
bound is of the same order as the best known centralized alternative. Our
results are further supported using the publicly available Milano dataset.

###### Index Terms:

Online convex optimization, edge computing, resource allocation, distributed
algorithms.

##  I Introduction

###  I-A Motivation

It is envisioned that globally more than 29.3 billion networked devices will
be connected to the Internet of Things (IoT) by 2023 [1], offering automation
and real-time monitoring of machine and human-driven processes. A main
challenge in IoT deployment lies with the massive amount of connected devices;
and in particular with the device heterogeneity (e.g., different computational
capabilities) and the diverse and potentially stringent service (task)
requirements [2]. To host the unprecedented IoT data traffic, the edge
computing paradigm has recently gained a lot of momentum as complementary to
that of the cloud and it has been deemed as a key enabler to what ultimately
will be the so-called “Cloud-to-Things Continuum” [3, 4].

In that framework, a plethora of spatially distributed devices collect data
from sensors and perform low-latency impromptu computation (e.g., machine-
learning inference) using energy-limited resources. The envisaged “Cloud-to-
Things Continuum” allows flexible task offloading _from_ an IoT device, via
base stations, _towards_ more computationally powerful edge servers and, if
needed, to the cloud. Although this architecture is promising, allocating
resources for IoT computations has two distinct fundamental challenges: (a)
the resources are allocated in the presence of highly unpredictable and non-
stationary request patterns (demands) and network conditions; (b) the network
nodes handling those tasks, namely devices, base stations and servers, are
distributed and should act in the absence of a centralized entity with full
observability. Naturally, the following question arises:

“Can we offer an efficient distributed data-driven algorithm for resource
allocation in the IoT context?”

In order to address this question, in this paper we consider a distributed
setting with nodes of different capabilities and employ Online Convex
Optimization (OCO) [5]. The use of OCO is suitable for problems that are
difficult to model due to unpredictable dynamics and provides concrete
theoretical guarantees for such problems even in the worst-case.

###  I-B Related Work

The related literature can be split into two categories. The first corresponds
to studies of _IoT network optimization_ in the edge-cloud setting, using
similar system model and assumptions to ours. An offline version of the
problem is formulated and then decomposed across its different domains (fog
and cloud) in [6], resulting in convex subproblems. In [7], the authors
consider the latency minimization and develop an algorithm based on the online
secretary framework—however, no constraints are used in their formulation.
Closer to our work, [2, 4] formulate the resource allocation as an OCO
problem, and model the service violations as long-term constraints. The
learning rate is adapted to the different IoT tasks in [2]; and further
extending the notion of constraint violation (see [8]), the number of
violations is also considered in [4]. Unlike our work, both approaches are
centralized.

The second one deals with works on _OCO with constraints in generic settings_
, such as [9, 10, 11]. Although generic, these works do not apply to our
problem as they develop centralized algorithms. Delayed feedback on the cost
and constraint functions arrive to a centralized agent in [12]; our approach
adopts a different feedback model based on limited exchange of information
between nodes. Finally, a distributed OCO algorithm in an environment with
time-varying constraints is presented and analyzed in [13], but, unlike our
approach, the nodes/actors use synchronous information and make consensus
steps.

###  I-C Contributions and Structure

In this work, we approach the resource allocation in an edge-cloud scenario in
a distributed way; our main contributions can be summarized as follows.

(C.1) We model the resource allocation as a distributed constrained OCO
problem. The network nodes (devices, base stations, edge servers) are cast as
individual OCO agents that must collectively optimize a given network
performance metric and satisfy service requirement guarantees (modeled as
long-term constraints). To this end, we define a limited communication model
between neighboring agents that allows them to exchange crucial information,
related to their coupling constraints.

(C.2) We propose an online primal-dual algorithm, based on projected gradient
descent, with a sub-linear regret bound $\mathcal{O}(T^{1/2})$ and a sub-
linear constraint violation bound $\mathcal{O}(T^{3/4})$. These bounds are
equivalent to a centralized approach besides a multiplicative factor. We
validate our theoretical results with numerical simulations on a commonly used
dataset, and compare the performance of our algorithm to benchmarks.

The remainder of this paper is organized as follows. We summarize our system
model and assumptions in Section II. Then, we introduce the OCO formulation of
the problem and present our proposed algorithm and its theoretical guarantees
in Section III. We show our numerical results in Section IV and conclude the
paper in Section V.

##  II Problem Setup

In this section we present our network model and main assumptions. In
particular, we start by the edge computing components that are available in
our IoT application; then we present the control (optimization) variables, and
finally we discuss our performance objectives and system constraints.

In what follows, we use bold fonts for vectors and matrices, and $\mathcal{A}$
for a set with $|\mathcal{A}|=A$ elements.

###  II-A Topology and Computational Requests

We consider a layer of IoT sensors, which receive computational requests
(e.g., analytics tasks) that need to be executed, similarly to [2, 4, 14, 6,
15, 7]. Time is slotted and at every timeslot $t$ those requests arrive to a
set of devices $\mathcal{D}$. We denote the vector of requests as
$\mathbf{r}^{t}\in\mathbb{R}_{+}^{D}$. Before $\mathbf{r}^{t}$ is revealed,
the Network Operator (NO) has to reserve resources across its network
infrastructure in order to accommodate them.

We assume that the network consists of the following nodes, as shown in Fig.
1.

  * •

Devices at the edge, denoted by $\mathcal{D}$;

  * •

Base Stations (BSs) at the edge, denoted by $\mathcal{B}$;

  * •

Servers at the edge, denoted by $\mathcal{S}$;

  * •

A cloud server at the core network, denoted by $C$.

Throughout the rest of this work, we will refer to the above entities (except
for the cloud) as “nodes” or “agents”. We denote by $\mathcal{N}$ the set of
all nodes across the network with $N=D+B+S$.

Each device can process locally part of the computation and can also offload
tasks via a wireless channel to the BSs. Then, the BSs can forward an incoming
task either to the edge servers (wirelessly) or to the cloud. Finally, each
edge server can process the received tasks locally, reroute to other edge
servers or forward to the cloud; the latter only executes tasks. For
simplicity, we assume full connectivity between nodes, but our methodology
applies to any connectivity graph.

Figure 1: Topology of our edge computing setting

###  II-B Distributed Control Variables

The NO wishes to optimize a set of performance metrics in a _distributed_
manner. Therefore, we wish to design a system where each agent decides its own
actions. At every $t$, the control variables for every device
$d\in\mathcal{D}$, BS $b\in\mathcal{B}$ and server $s\in\mathcal{S}$ are

$\displaystyle\mathbf{x}_{d}^{t}$
$\displaystyle=[w^{t}_{d0},w^{t}_{d1},\dots,w^{t}_{dB},p^{t}_{d1},\dots,p^{t}_{dB}]\in\mathbb{R}_{+}^{2B+1}$
(1) $\displaystyle\mathbf{x}_{b}^{t}$
$\displaystyle=[y^{t}_{bC},y^{t}_{b1},\dots,y^{t}_{bS},q^{t}_{b1},\dots,q^{t}_{bS}]\in\mathbb{R}_{+}^{2S+1}$
(2) $\displaystyle\mathbf{x}_{s}^{t}$
$\displaystyle=[z^{t}_{sC},z^{t}_{s1},\dots,z^{t}_{sS}]\in\mathbb{R}_{+}^{S+1}.$
(3)

For each device $d$, $w^{t}_{d0}$ is the locally executed tasks and
$w^{t}_{db}$, $p^{t}_{db}$ are the offloaded tasks and the respective
transmission power to each available BS. For each BS $b$, $y_{b,C}^{t}$
denotes the tasks offloaded to the cloud and $y_{bs}^{t},q_{bs}^{t}$ are the
offloaded tasks and the respective transmission power to each available server
$s\in\mathcal{S}$. Finally, for each server $s$, $z^{t}_{sC}$ is the offloaded
tasks to the cloud and $z^{t}_{ss^{\prime}}$ is the offloaded tasks to each
available server $s^{\prime}\in\mathcal{S}$, including $z^{t}_{ss}$ that
denotes the locally processed tasks.

For every $t$, it must hold
$\mathbf{x}_{d}^{t}\in\Omega_{d},\mathbf{x}_{b}^{t}\in\Omega_{b},\mathbf{x}_{s}^{t}\in\Omega_{s}$,
where $\Omega_{d},\Omega_{b},\Omega_{s}$ are time-invariant box constraints of
the form $\\{\mathbf{x}:\mathbf{0}\leq\mathbf{x}\leq\mathbf{\bar{x}}\\}$. Note
that these constraints are local, meaning that an agent needs no external
information in order to satisfy them. To denote the _collective_ control
variable of all nodes, we use the following notation:

$\mathbf{x}^{t}_{\mathcal{D}}=\\{\mathbf{x}^{t}_{d}\\}_{\forall
d\in\mathcal{D}},\leavevmode\nobreak\ \leavevmode\nobreak\
\mathbf{x}^{t}_{\mathcal{B}}=\\{\mathbf{x}^{t}_{b}\\}_{\forall
b\in\mathcal{B}},\leavevmode\nobreak\ \leavevmode\nobreak\
\mathbf{x}^{t}_{\mathcal{S}}=\\{\mathbf{x}^{t}_{s}\\}_{\forall
s\in\mathcal{S}}.$ (4)

Finally, we use
$\mathbf{x}^{t}=\\{\mathbf{x}^{t}_{\mathcal{D}},\mathbf{x}^{t}_{\mathcal{B}},\mathbf{x}^{t}_{\mathcal{S}}\\}\in\Omega\subset\mathbb{R}_{+}^{V}$
to denote all the variables across the network, with
$V=D(2B+1)+B(2S+1)+S(S+1)$.

###  II-C Performance Objectives

Our main target is to choose the resources $\mathbf{x}^{t}$, such that a
cumulative cost for the total delay and transmit power across all nodes is
minimized. The cost function at each node depends on its control variables and
it is considered time-varying in order to capture the unpredictable network
dynamics at every timeslot, e.g. the randomness of the wireless channels or
the network congestion levels. More precisely, we have the following cost
functions per node:

$\displaystyle f_{d}^{t}(\mathbf{x}_{d}^{t})$
$\displaystyle=c^{t}_{d}(w_{d0}^{t})+\sum_{b\in
B}c^{t}_{db}(w_{db}^{t},p_{db}^{t})$ (5) $\displaystyle
f_{b}^{t}(\mathbf{x}_{b}^{t})$ $\displaystyle=\sum_{s\in
S}c^{t}_{bs}(y_{bs}^{t},q_{bs}^{t})+c^{t}_{bC}(y_{bC}^{t})$ (6) $\displaystyle
f^{t}_{s}(\mathbf{x}_{s}^{t})$ $\displaystyle=\sum_{s^{\prime}\in
S}c^{t}_{ss^{\prime}}(z_{ss^{\prime}}^{t})+c^{t}_{sC}(z_{sC}^{t}).$ (7)

The functions $c^{t}_{d}(.),c^{t}_{ss}(.)$ represent local processing delay
cost, $c^{t}_{db}(.),c^{t}_{bs}(.)$ capture both delay and power cost for the
wireless links between nodes, $c^{t}_{bC}(.),c^{t}_{sC}(.)$ are used for the
offloading delay cost to the cloud and $c^{t}_{ss^{\prime}}(.)$ introduces the
delay cost for the wired links between servers. At every timeslot $t$, the
total cost is expressed as

$f^{t}(\mathbf{x}^{t})=\sum_{d\in\mathcal{D}}f^{t}(\mathbf{x}^{t}_{d})+\sum_{b\in\mathcal{B}}f^{t}(\mathbf{x}^{t}_{b})+\sum_{s\in\mathcal{S}}f^{t}(\mathbf{x}^{t}_{s}).$
(8)

Similar to our model, most related works, e.g., [2, 4, 7], assume that local
processing delay and communication delay, often specified via standard queuing
models, are expressed by functions of only local control variables. As we will
see next, this is not the case for the problem constraints, where there exist
constraints that couple agents to preserve the flow of tasks inside the
network.

###  II-D Constraints

We now focus on the constraints imposed by our application. In practice, a
good decision must first ensure that the incoming tasks are either processed
locally or offloaded to other nodes (_flow conservation constraint_).
Moreover, the transmission data rate of a wireless link must be sufficient for
the assigned offloaded tasks (_rate constraint_). We model these rates using
the well known Shannon capacity. All constraint functions are considered time-
varying in order to model the unknown dynamics of incoming tasks and channel
gains. Given that the agents first reserve resources and then the tasks are
revealed, it is possible to have service violations, i.e. the provisioned
resources are not adequate or cannot be realized.

For each device $d\in\mathcal{D}$, the constraint functions are

$\displaystyle g^{t}_{d0}(\mathbf{x}_{d}^{t})$
$\displaystyle=r^{t}_{d}-w^{t}_{d0}-\sum_{b\in\mathcal{B}}w^{t}_{db}$ (9)
$\displaystyle g_{db}^{t}(\mathbf{x}_{d}^{t})$
$\displaystyle=w^{t}_{db}-b_{w}\log_{2}\big{(}1+\alpha_{db}^{t}p_{db}^{t}),\forall\leavevmode\nobreak\
b\in\mathcal{B},$ (10)

where $b_{w}$ is a constant for the transmission bandwidth and
$\alpha_{db}^{t}$ is an unknown variable for the channel gain, including the
effect of interference and noise. In a similar way, for each BS
$b\in\mathcal{B}$ we have

$\displaystyle g^{t}_{b0}(\mathbf{x}_{b}^{t};\mathbf{x}_{\mathcal{D}}^{t})$
$\displaystyle=\sum_{d\in\mathcal{D}}w^{t}_{db}-y^{t}_{bC}-\sum_{s\in\mathcal{S}}y^{t}_{bs}$
(11) $\displaystyle g_{bs}^{t}(\mathbf{x}_{b}^{t})$
$\displaystyle=y^{t}_{bs}-b_{w}\log_{2}\big{(}1+\alpha_{bs}^{t}q_{bs}^{t}),\forall\leavevmode\nobreak\
s\in\mathcal{S},$ (12)

where $\alpha_{bs}^{t}$ is defined as $\alpha_{db}^{t}$ above. Notice that
(11) is a _coupling constraint_ , i.e. to evaluate the function at BS $b$, we
need to know the external variables $\\{w^{t}_{db}\\}_{d\in\mathcal{D}}$ of
devices. Conventionally, we denote this dependency with conditional arguments
to distinguish from locally available variables, as denoted by
$g^{t}_{b0}(\mathbf{x}_{b}^{t};\mathbf{x}_{\mathcal{D}}^{t})$. Finally, for
each server $s\in\mathcal{S}$, we have only the following flow conservation
constraint function

$\displaystyle
g_{s0}^{t}(\mathbf{x}_{s}^{t};\mathbf{x}_{\mathcal{B}}^{t},\mathbf{x}_{\mathcal{S}_{-s}}^{t})\\!=\\!\sum_{b\in\mathcal{B}}y^{t}_{bs}+\\!\\!\\!\sum_{s^{\prime}\in\mathcal{S}_{-s}}\\!\\!\\!z^{t}_{s^{\prime}s}-\\!\\!\sum_{s^{\prime}\in\mathcal{S}}\\!z^{t}_{ss^{\prime}}\\!-\\!z^{t}_{sC}$
(13)

where $\mathcal{S}_{-s}$ is used to denote the set of edge servers
$\mathcal{S}$ excluding $s$. (13) is also a coupling constraint, since server
$s$ needs to know the external variables $\\{y^{t}_{bs}\\}_{b\in\mathcal{B}}$
of BSs and $\\{z^{t}_{s^{\prime}s}\\}_{s^{\prime}\in\mathcal{S}_{-s}}$ of
other servers.

To denote the collective set of constraints per device $d$ and per BS $b$, we
use the notation

$\displaystyle\mathbf{g}_{d}^{t}(\mathbf{x}_{d}^{t})$
$\displaystyle=g^{t}_{d0}(\mathbf{x}_{d}^{t})\cup\\{g^{t}_{db}(\mathbf{x}_{d}^{t})\\}_{\forall
b\in\mathcal{B}}$ (14)
$\displaystyle\mathbf{g}_{b}^{t}(\mathbf{x}_{b}^{t};\mathbf{x}_{\mathcal{D}}^{t})$
$\displaystyle=g^{t}_{b0}(\mathbf{x}_{b}^{t};\mathbf{x}_{\mathcal{D}}^{t})\cup\\{g^{t}_{bs}(\mathbf{x}_{b}^{t})\\}_{\forall
s\in\mathcal{S}}$ (15)

and write
$\mathbf{g}^{t}(\mathbf{x}^{t})=\\{\\{\mathbf{g}^{t}_{d}\\}_{d\in\mathcal{D}},\\{\mathbf{g}^{t}_{b}\\}_{d\in\mathcal{B}},\\{g^{t}_{s0}\\}_{s\in\mathcal{S}}\\}:\mathbb{R}_{+}^{V}\to\mathbb{R}^{M}$
to denote all constraints across the network, where $M=B(D+S)+N$.

###  II-E Exchange of Information

Due to the coupling constraints, a fully distributed solution is no longer
possible. To circumvent this, we allow each node to exchange information with
other nodes, so that it can take into account the coupling constraints in its
local decisions. The exact messages to exchange is part of the algorithm
design, which ideally should achieve a performance close to a centralized
approach with a minimal exchange of information. To limit the communication
overhead, we further consider that each node can send information to other
nodes only once during a timeslot, i.e. at the beginning of a timeslot. As we
will see in the next section, this practical assumption introduces delayed
feedback between nodes, as not all of the required information is available
for a single transmission step within a timeslot.

##  III OCO Formulation and Decentralized Algorithm

The goal of this section is to formulate the resource allocation, described in
the previous section, as an Online Convex Optimization (OCO) problem [5] and
propose an algorithm to solve it. Importantly, we explain how we adapt a
centralized algorithm to transcend towards one which can run in a distributed
fashion; finally, we present the performance guarantees of our solution.

###  III-A OCO Preliminaries

We start with the basics of OCO in a centralized algorithm for two reasons:
(a) it helps to introduce useful concepts and metrics; and (b) we benchmark
our distributed algorithm with respect to a centralized one. To formulate the
resource allocation as an OCO problem, we first need to define the sequence of
events taking place for the central agent during every timeslot $t$.

  1. 1.

The agent implements an action $\mathbf{x}^{t}$.

  2. 2.

The environment reveals all the unknown variables, e.g. computation requests
$\mathbf{r}^{t}$ and channel gains $\alpha_{ij}^{t}$, which in the OCO
framework can be random variables or even controlled by an adversary. Using
these, the functions $f^{t}(\mathbf{.})$ and $\mathbf{g}^{t}(\mathbf{.})$
become known.

  3. 3.

The agent receives or evaluates cost and constraint violations, i.e. the
values $f^{t}(\mathbf{x}^{t})$ and $\mathbf{g}^{t}(\mathbf{x}^{t})$.

  4. 4.

The agent updates its action to $\mathbf{x}^{t+1}$.

Below, we define the benchmark actions and the metrics to evaluate an
algorithm that produces a sequence of actions
$\\{\mathbf{x}^{t}\\}_{t=1,\dots,T}$.

######  Definition 1 (Static Regret).

The fixed optimal action $\mathbf{x}_{*}$ and the static regret are defined as

$\displaystyle\mathbf{x}_{*}=\underset{x\in\Omega}{\mathrm{argmin}}\sum_{t=1}^{T}f^{t}(\mathbf{x}),\emph{s.t.}\leavevmode\nobreak\
\mathbf{g}^{t}(\mathbf{x})\leq 0,\leavevmode\nobreak\ t=1,\dots,T$ (16)
$\displaystyle\emph{Reg}_{S}(T)=\sum_{t=1}^{T}f^{t}(\mathbf{x}^{t})-\sum_{t=1}^{T}f^{t}(\mathbf{x}_{*}).$
(17)

######  Definition 2 (Dynamic Regret).

The per slot optimal action $\\{\mathbf{x}_{*}^{t}\\}_{t=1,\dots,T}$ and the
dynamic regret are defined as

$\displaystyle\mathbf{x}_{*}^{t}=\underset{x\in\Omega}{\mathrm{argmin}}f^{t}(\mathbf{x}),\emph{s.t.}\leavevmode\nobreak\
\mathbf{g}^{t}(\mathbf{x})\leq 0$ (18)
$\displaystyle\emph{Reg}_{D}(T)=\sum_{t=1}^{T}f^{t}(\mathbf{x}^{t})-\sum_{t=1}^{T}f^{t}(\mathbf{x}_{*}^{t}).$
(19)

######  Definition 3 (Fit).

Using the clipped constraint function
$h_{m}^{t}(\mathbf{x}^{t}):=[g_{m}^{t}(\mathbf{x}^{t})]^{+}=\max\\{0,g_{m}^{t}(\mathbf{x}^{t})\\}$,
the fit is defined as

$\emph{Fit}(T)=\sum_{t=1}^{T}\sum_{m=1}^{M}h_{m}^{t}(\mathbf{x}^{t}).$ (20)

The static regret is a standard metric for evaluating OCO-based algorithms;
however, there is also a growing interest recently for the dynamic regret
[16], which is in principle a much harder metric. For the fit we use a clipped
version of the constraint, i.e. we do not allow negative and positive values
of the constraints to average out in the long run. This is a suitable modeling
approach, as it would be unrealistic to assume that overprovisioning in
certain timeslots can compensate for missing resources or channel rate
violations in other timeslots. Finally, similarly to [8], we define the
gradient of $h_{m}(\mathbf{x})$ as

$\displaystyle\nabla
h_{m}(\mathbf{x})=\nabla[g_{m}(\mathbf{x})]^{+}=\begin{cases}\mathbf{0}&\text{if
$g_{m}(\mathbf{x})\leq 0$}\\\ \nabla g_{m}(\mathbf{x})&\text{if
$g_{m}(\mathbf{x})>0$}\end{cases}$

In the remainder, we use $\mathbf{h}^{t}$ for our analysis with subscripts
that have the same meaning as for $\mathbf{g}^{t}$ in (9)-(15).

Overall, the objective of an algorithm is to establish that Reg${}_{S}(T)$,
Reg${}_{D}(T)$ and Fit$(T)$ are all sublinear in the time horizon $T$ [5].

###  III-B Decomposition Across the Agents

A centralized algorithm can use the Lagrange function

$\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})=f^{t}(\mathbf{x}^{t})+\sum_{m=1}^{M}h_{m}^{t}(\mathbf{x})\lambda^{t}_{m}$
(21)

and apply the primal-dual updates [8] as follows

$\displaystyle\boldsymbol{\lambda}^{t}=\frac{\mathbf{h}^{t}({\mathbf{x}}^{t})}{\eta\sigma},\leavevmode\nobreak\
\mathbf{x}^{t+1}=\mathcal{P}_{\Omega}\left({\mathbf{x}}^{t}-\eta{\nabla}_{\mathbf{x}}\mathcal{L}^{t}({\mathbf{x}}^{t},\boldsymbol{\lambda}^{t})\right),$
(22)

where $\lambda^{t}_{m}$ is the Lagrange multiplier for constraint $m$, $\eta$
is the gradient step size, $\sigma$ is a constant and
$\mathcal{P}_{\Omega}(\mathbf{x})$ is the projection of $\mathbf{x}$ onto
$\Omega$. Ideally, we want to perform these updates in a distributed way so
that they are as close as possible to the updates of the centralized
algorithm. For any node $n\in\mathcal{N}$ (device, BS or server), we have

$\displaystyle\boldsymbol{\lambda}^{t}_{n}$
$\displaystyle=\frac{\mathbf{h}_{n}^{t}(\mathbf{x}_{n}^{t};\mathbf{x}_{\mathcal{E}_{n}}^{t})}{\eta\sigma}$
(23) $\displaystyle\mathbf{x}_{n}^{t+1}$
$\displaystyle=\mathcal{P}_{\Omega_{n}}\left(\mathbf{x}_{n}^{t}-\eta\nabla_{\mathbf{x}_{n}}\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})\right),$
(24)

where $\mathcal{E}_{n}$ is the set of nodes with variables required for node
$n$, i.e. $\mathcal{E}_{d}=\emptyset$, $\mathcal{E}_{b}=\mathcal{D}$ (11),
$\mathcal{E}_{s}=\mathcal{B}\cup\mathcal{S}_{-s}$ (13), and
$\boldsymbol{\lambda}^{t}$ uses the same subscripts for constraints as
$\mathbf{g}^{t},\mathbf{h}^{t}$.

We now focus on the gradients in (24) and write

$\nabla_{\mathbf{x}_{n}}\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})=\mathbf{H}^{t}_{nL}+\mathbf{H}^{t}_{nE}$
(25)

where $\mathbf{H}^{t}_{nL}$ denotes the part that depends only on local cost
and constraint functions at node $n$,

$\mathbf{H}^{t}_{nL}=\nabla_{\mathbf{x}_{n}}f_{n}^{t}(\mathbf{x}_{n}^{t})+\boldsymbol{\lambda}_{n}^{t\top}\nabla_{\mathbf{x}_{n}}\mathbf{h}^{t}_{n}(\mathbf{x}_{n}^{t};\mathbf{x}_{\mathcal{E}_{n}}^{t}),$
(26)

and $\mathbf{H}^{t}_{nE}$ describes the part that depends on external
constraints from other nodes. For clarity, we provide the explicit expression
for each type of node:

$\displaystyle\mathbf{H}^{t}_{dE}$
$\displaystyle=\sum_{b\in\mathcal{B}}\lambda^{t}_{b0}\nabla_{\mathbf{x}_{d}}h^{t}_{b0}(\mathbf{x}_{b}^{t};\mathbf{x}_{\mathcal{D}}^{t})$
(27) $\displaystyle\mathbf{H}^{t}_{bE}$
$\displaystyle=\sum_{s\in\mathcal{S}}\lambda_{s0}^{t}\nabla_{\mathbf{x}_{b}}h^{t}_{s0}(\mathbf{x}_{s}^{t};\mathbf{x}_{\mathcal{B}}^{t},\mathbf{x}_{\mathcal{S}_{-s}}^{t})$
(28) $\displaystyle\mathbf{H}^{t}_{sE}$
$\displaystyle=\sum_{s^{\prime}\in\mathcal{S}_{-s}}\\!\\!\lambda^{t}_{s^{\prime}0}\nabla_{\mathbf{x}_{s}}h_{s^{\prime}0}^{t}(\mathbf{x}_{s^{\prime}}^{t};\mathbf{x}_{\mathcal{B}}^{t},\mathbf{x}_{\mathcal{S}_{-s^{\prime}}}^{t}).$
(29)

Notice that in (27)-(29), only one dimension of the gradients can be non-zero,
as each node has only a single variable involved in coupling constraints of
another node, i.e. $w_{db},y_{bs}$ and $z_{ss^{\prime}}$ for devices, BSs and
servers.

######  Remark 1.

According to the definition of $\mathbf{h}^{t}(.)$ and the flow constraints,
the summation terms in (27)-(29) simplify to
$\lambda^{t}_{n0}\mathbf{1}_{h^{t}_{n0}(\mathbf{x}_{n}^{t};\mathbf{x}_{\mathcal{E}_{n}}^{t})>0}$,
where $\mathbf{1}_{(.)}$ is the indicator function.

###  III-C Distributed Algorithm

As one can already notice, a distributed version of the algorithm requires
exchange of information at two different steps. Specifically, a node $n$ needs
to send its variables to nodes that need them in their coupling constraints
and then, receive the gradient-related feedback $\mathbf{H}^{t}_{nE}$. We now
turn our focus on the adopted communication model and examine how this message
exchange can be implemented.

(a) Ideal case

(b) Proposed approach

Figure 2: Exchanged messages during time slot $t$ between device $d$ and BS
$b$.

An ideal scenario is shown in Fig. 2(a), where nodes can send messages at any
moment during a time slot, focusing for simplicity in the link between a
device and a BS. As we can see, the BS $b$ needs to collect
$\mathbf{x}^{t}_{\mathcal{E}_{b}}=\\{w^{t}_{db}\\}_{d\in\mathcal{D}}$ and
perform few processing steps before it can send its feedback to the device,
which can then perform the primal update $\mathbf{x}_{d}^{t+1}$. In practice,
this is not possible in our model as nodes are allowed to send messages only
once at the beginning of a time slot. We address this limitation by allowing
nodes to send their feedback at the next time slot, as shown in Fig. 2(b). As
a result, the device uses the outdated feedback $\mathbf{H}^{t-1}_{dE}$ for
its updates.

Overall, we define the following messages between nodes $n,v$, where
$n\in\mathcal{E}_{v}$, and summarize them in Table I.

  1. 1.

$m^{t}_{1,n\to v}:=\mathbf{x}^{t}_{n}\in\mathbf{x}^{t}_{\mathcal{E}_{v}}$;
required to evaluate the coupling constraint
$h^{t}_{v0}(\mathbf{x}^{t}_{v};\mathbf{x}^{t}_{\mathcal{E}_{v}})$ at node $v$,
which is then used for the dual update of $\lambda^{t}_{v0}$ in (23) and the
local term $\mathbf{H}^{t}_{vL}$.

  2. 2.

$m^{t}_{2,v\to
n}:=\lambda^{t-1}_{v0}\mathbf{1}_{h^{t-1}_{v0}(\mathbf{x}_{v}^{t-1};\mathbf{x}_{\mathcal{E}_{v}}^{t-1})>0}$;
feedback required to evaluate $\mathbf{H}^{t-1}_{nE}$ for the primal update at
node $n$.

TABLE I: Messages $(m^{t}_{1},m^{t}_{2})$ between nodes From$\backslash$To |  Device $d^{\prime}$ |  BS $b^{\prime}$ |  Server $s^{\prime}$
---|---|---|---
Device $d$ | $-$ | $w^{t}_{db^{\prime}}$ | $-$
BS $b$ | $\lambda^{t-1}_{b0}\mathbf{1}_{h^{t-1}_{b0}>0}$ | $-$ | $y^{t}_{bs^{\prime}}$
Server $s$ | $-$ | $\lambda^{t-1}_{s0}\mathbf{1}_{h^{t-1}_{s0}>0}$ |  $z^{t}_{ss^{\prime}}$, $\lambda^{t-1}_{s0}\mathbf{1}_{h^{t-1}_{s0}>0}$

Let us now consider the primal/dual updates of the proposed approach. First,
the dual update (23) remains the same and thus, identical to the centralized
case. Then, for the primal update (24), only the gradient term is modified and
approximated by

$\nabla_{\mathbf{x}_{n}}\hat{\mathcal{L}}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})=\mathbf{H}^{t}_{nL}+\mathbf{H}^{t-1}_{nE}.$
(30)

The steps of our proposed distributed algorithm are presented in Algorithm 1
for any node $n$.

Algorithm 1 Distributed OCO for node $n$

1:Initialize: parameters $\sigma$, $\eta$

2:Set first action $\mathbf{x}^{1}_{n}\in\Omega_{n}$ and define
$\boldsymbol{\lambda}^{0}_{n}=\mathbf{0}$.

3:for $t=1,\dots,T$ do

4: Play action $\boldsymbol{x}^{t}_{n}$

5: Send messages $m^{t}_{1,n\to v}$ to nodes $v:n\in\mathcal{E}_{v}$

6: Receive from environment functions $f^{t}_{n}(.)$ and
$\boldsymbol{g}^{t}_{n}(.)$

7: Receive feedback messages $m^{t}_{2,v\to n}$ from nodes $v$

8: Compute $\boldsymbol{\lambda}_{n}^{t}$ with (23) $\triangleright$ Dual
update

9: Update $\boldsymbol{x}_{n}^{t+1}$ with (24),(30) $\triangleright$ Primal
update

10:end for

###  III-D Performance Guarantees

We make the following standard assumptions, widely used in online learning
literature (e.g., see [8, 11]), and then formally state our main theorem.

######  Assumption 1.

  * •

(i) Set $\Omega_{n}$ is bounded and convex; specifically it holds that
$\left\lVert\mathbf{x}_{n}-\mathbf{y}_{n}\right\rVert\leq R$,
$\forall\mathbf{x}_{n},\mathbf{y}_{n}\in\Omega_{n}$, for
$n\in\mathcal{D,B,S}$.

  * •

(ii) For $t=1,\dots,T$, functions $f^{t}_{n}$ and $g^{t}_{n,i}$ are convex and
Lipschitz with $\left\lVert\nabla_{\mathbf{x}_{n}}f^{t}_{n}\right\rVert\leq
F^{\prime}$ and $\left\lVert\nabla_{\mathbf{x}_{n}}g_{n,i}^{t}\right\rVert\leq
G^{\prime}$, for $n\in\mathcal{D,B,S}$ and
$\mathbf{g}_{n}^{t}=\\{g^{t}_{n,i}\\}_{i=1,\dots,M_{n}}$ (with $M_{n}$ the
number of constraints at node $n$).

Below we write a list of implications that we use for the proof of our
theorem. First, $f^{t}_{n}$ and $g^{t}_{n,i}$ are both bounded, i.e.,
$|f^{t}_{n}|\leq F$, $|g^{t}_{n,i}|\leq G^{\prime\prime}$. Second, since
$\left\lVert\nabla g_{n,i}^{t}\right\rVert\leq G^{\prime}$, then
$\left\lVert\nabla h_{n,i}^{t}\right\rVert\leq G^{\prime}$ (comes from the
definition of gradient of $h$). Third, since $g^{t}_{n,i}$ is bounded,
$h^{t}_{n,i}$ is also bounded by definition; hence $|h^{t}_{n,i}|\leq
G^{\prime\prime}$ and $\left\lVert\mathbf{h}^{t}\right\rVert\leq G$. For
simplicity we write that $|f^{t}_{n}|,\left\lVert\nabla
f^{t}_{n}\right\rVert\leq F$ and $|h_{n,i}^{t}|,\left\lVert\nabla
h_{n,i}^{t}\right\rVert,\left\lVert\mathbf{h}_{n}^{t}\right\rVert\leq G$.
Fourth, since $g_{n,i}^{t}$ is convex, then $h_{n,i}^{t}$ is as well.

A proof of the first and fourth implications can be found in Appendix B.

######  Theorem 1.

Given Assumption 1, and $\sigma>3KG^{2}$, Algorithm 1 guarantees that

$\displaystyle{\text{Reg}_{S}}(T)$
$\displaystyle\leq\frac{R^{2}}{2\eta}+\frac{2REG^{2}}{\eta\sigma}+\frac{7}{2}\eta
NF^{2}T\triangleq U_{sr},$ (31) $\displaystyle{\text{Reg}_{D}}(T)$
$\displaystyle\leq U_{sr}+\frac{R}{\eta}V(\boldsymbol{x}_{*}^{1:T}),$ (32)
$\displaystyle{\text{Fit}}(T)$
$\displaystyle\leq\sqrt{\frac{\eta\sigma}{\beta}MT(U_{sr}+2NFT)},$ (33)

where $E$ is the number of edges in the network topology,
$K=2D(3B+1)+2B(3S+1)+2S(2S-1)$, $\beta=1-\frac{3KG^{2}}{\sigma}$ and
$V(\mathbf{x}_{*}^{1:T})=\sum_{t=1}^{T}\left\lVert\mathbf{x}_{*}^{t}-\mathbf{x}_{*}^{t-1}\right\rVert$.

###### Proof.

The proof can be found in Appendix A. ∎

An immediate implication of Theorem 1 is that, for step size
$\eta=\mathcal{O}(T^{-1/2})$, we have

  * •

$\textnormal{Reg}_{S}(T)=\mathcal{O}(T^{1/2})$

  * •

$\textnormal{Reg}_{D}(T)=\mathcal{O}(\max\\{T^{1/2},T^{1/2}V(\mathbf{x}_{*}^{1:T})\\})$

  * •

$\textnormal{Fit}(T)=\mathcal{O}(T^{3/4})$

We conclude that our distributed algorithm, although using outdated Lagrange
multipliers, achieves sublinear static regret and fit; if additionally,
$V(\mathbf{x}_{*}^{1:T})=o(T^{1/2})$, then dynamic regret is also sublinear.
In fact, we achieve the same order of bounds as the centralized algorithm in
[4] (in the case where the authors ignore the outages), which tackles the same
setting. Note that choosing $\eta=\mathcal{O}(T^{-1/2})$ yields the minimum
regret while preserving a sublinear fit.

##  IV Performance Evaluation

###  IV-A Simulation Setup

Topology and box constraints. We assume a fully connected setting with nodes
$D,B,S=2$. Moreover, the upper bounds of the control variables are as follows:
for every device $d$, $\overline{w}_{d0}=2$, $\overline{w}_{db}=25$, and
$\overline{p}_{db}=25$, for every BS $b$, $\overline{y}_{bC}=30$,
$\overline{y}_{bs}=25$, and $\overline{q}_{bs}=25$ and for every server $s$,
$\overline{z}_{sC}=50$, $\overline{z}_{ss}=15$ and
$\overline{z}_{ss^{\prime}}=10$.

Costs. We model the cost functions using expressions for delay (from
$M/M/1$111To avoid numerical instabilities, e.g., $M/M/1$ delay becoming
infinite, we use standard convex extensions [4].) and power [7]. The local
processing delay of node $n$ for $x$ tasks is $c_{n}(x)=1/(\overline{x}-x)$,
where $\overline{x}$ denotes the capacity of node $n$; this cost is used to
model $c^{t}_{d}(w^{t}_{d0})$ and $c^{t}_{ss}(z^{t}_{ss})$. Then, the cost
related to wireless offloading, i.e., $c^{t}_{db}(w^{t}_{db},p^{t}_{db})$ and
$c^{t}_{bs}(y^{t}_{bs},q^{t}_{bs})$, is modeled as
$c^{t}_{nn^{\prime}}(x,y)=1/(R^{t}_{nn^{\prime}}(y)-x)+\frac{1}{2}y^{2}$,
where
$R^{t}_{nn^{\prime}}(y)=b_{w}\log_{2}\big{(}1+\alpha_{nn^{\prime}}^{t}y)$ is
the channel rate. Finally, the delays for offloading to the cloud, i.e.
$c^{t}_{bC}(y^{t}_{bC})$ and $c^{t}_{sC}(z^{t}_{sC})$, are modeled as
$c_{nC}^{t}(x)=d_{nC}^{t}x$, where $d_{nC}^{t}$ is a time-varying unknown
environment parameter.

Unknown variables. For each time slot $t$ we need: (a) channel gains
$\alpha_{db}^{t},\alpha_{bs}^{t}$, (b) cloud delay costs
$d_{bC}^{t},d_{sC}^{t}$, and (c) traffic requests $\mathbf{r}^{t}$. We model
(a) and (b) as random variables sampled from $\mathcal{U}(8,15)$ and
$\mathcal{U}(3,10)$ respectively. For (c), we mainly use the publicly
available Milano dataset [17]; in particular, we extract the aggregate
Internet traffic arrivals measured in MBs to $D=2$ BSs (devices in our model).
We also provide results using synthetic demands, drawn from
$\mathcal{U}(1,10)$.

Metrics and Baselines. The performance of an online algorithm is evaluated
using the static and dynamic regrets (the respective benchmarks are found
using CVXPY [18]), and the fit. We plot these metrics for proposed Algorithm
1, which we refer to as Cooperative algorithm, and for two more baselines.
First, the _Selfish_ is a distributed algorithm without information exchange
between nodes; i.e. $\mathbf{H}_{nE}^{t}=\mathbf{0}$ in (25). Second, the
_Centralized_ algorithm assumes a controller with access to all necessary
information in order to do the updates optimally. This is essentially the
algorithm described in [8], adapted to our setting with time-varying
constraints $\mathbf{h}^{t}$.

###  IV-B Simulation Results

In all our plots, the $x$-axis represents the horizon length $T$, which we
vary from $0$ to $300$ time slots. For each algorithm we plot the average
value across $4$ independent runs and with shade the corresponding standard
deviation. Notice that all metrics are normalized by the horizon $T$.

Our setup is challenging for a distributed algorithm, as the flow conservation
constraints _couple_ different nodes. To this end, we first investigate the
Fit$(T)$ for the Milano and the synthetic datasets in Figs. 3(a), 3(b). The
fit of the _Centralized_ algorithm quickly converges to zero, suggesting that
it learns to play actions that respect most of the time-varying constraints;
the reason is that it performs the best possible primal and dual updates with
the freshest information. The fit of the proposed _Cooperative_ algorithm
converges almost together with the _Centralized_ for the Milano demands (Fig.
3(a)) and slightly slower for the synthetic ones (Fig. 3(b)). Therefore, the
modified gradients proposed in our algorithm suffice in order to satisfy the
constraints in the long run. The _Selfish_ baseline exemplifies the necessity
of at least some information exchange between the nodes; we can see in both
figures the fit increasing. This behavior is expected, as the Fit$(T)$ of
_Centralized_ and _Collaborative_ is sublinear, whereas the one of _Selfish_
can be shown to be linear as its updates totally ignore the coupling (flow
conservation) constraints.

Having discussed the “feasibility” aspect of the algorithms (i.e., how they
perform in terms of constraints) we now focus on the objective function and in
particular on the regrets in Figs. 3(c), 3(d). We plot these metrics only for
the Milano dataset; but the respective plots for the synthetic one are
similar. A first observation is that the regrets of the _Selfish_ algorithm
are the lowest among all three methods. This should not come as a surprise,
since by construction, the algorithm solves a more relaxed version of the
problem (ignores flow constraints) and therefore can achieve better cost
values. The _Centralized_ algorithm has slightly higher regrets, which is
justified by its effort to also satisfy the fit. Finally, our _Collaborative_
algorithm has regrets that also go to zero and are very close to the ones of
the _Centralized_ solution.

(a) Fit - Milano

(b) Fit - Synthetic

(c) Static regret - Milano

(d) Dynamic Regret - Milano

Figure 3: Performance metrics vs horizon length $T$

Finally, we comment on the jump at $T\approx 110$ in Fig. 3(c), which is not
present in Fig. 3(d). The difference of the two plots lies with the
benchmarks; in Fig. 4, the $y$-axis is in fact the cost gap between them, i.e.
$\frac{1}{T}\sum_{t=1}^{T}\Big{(}f^{t}(x_{*})-f^{t}(x^{t}_{*})\Big{)}$; and in
that plot we obviously see that same jump. This behavior can be explained by
the change of demand in Fig. 4. Essentially, the static benchmark, for
$T>110$, solves an optimization problem by finding a feasible $x_{*}$ for that
extreme demand (at $T\approx 110$), and will be then _more constrained_
compared to the dynamic benchmark, which solves the problem for each $t$
individually.

Figure 4: Milano dataset: (a) Difference of regrets (and benchmarks) vs
horizon $T$; (b) Demands of the devices over time.

##  V Conclusions

We revisit the problem of resource allocation in an IoT network, where devices
can process part of the traffic requests, and/or offload the rest to more
powerful computational entities (cloud, edge servers). The distributed nature
of the setting, as well as the unpredictable environment, motivated us to
model the network nodes (devices, BSs, servers) as distributed OCO actors.
However, the nodes of the network are naturally coupled by flow conservation
constraints at each node, which we model as long-term constraints, and as a
result a fully decentralized algorithm is no longer possible.

In order to address this challenge, we propose a distributed OCO algorithm
with limited communication between nodes, which practically leads to partially
outdated gradient updates. Nevertheless, we show theoretically that our
algorithm achieves sub-linear regret bound $\mathcal{O}(T^{1/2})$ and sub-
linear constraint violation bound $\mathcal{O}(T^{3/4})$, which is the same
order of bounds as a centralized algorithm for this setting. Numerical results
based on real data traces confirm our theoretical findings.

## References

  * [1] U. Cisco, “Cisco annual internet report (2018–2023) white paper,” _Cisco: San Jose, CA, USA_ , vol. 10, 2020.
  * [2] T. Chen, Y. Shen, Q. Ling, and G. B. Giannakis, “Online learning for “thing-adaptive” fog computing in iot,” in _IEEE Asilomar_ , 2017.
  * [3] M. Chiang and T. Zhang, “Fog and iot: An overview of research opportunities,” _IEEE Internet of things journal_ , vol. 3, 2016.
  * [4] A. Chouayakh and A. Destounis, “Towards no regret with no service outages in online resource allocation for edge computing,” in _IEEE ICC_ , 2022.
  * [5] M. Zinkevich, “Online convex programming and generalized infinitesimal gradient ascent,” in _(ICML-03)_ , 2003, pp. 928–936.
  * [6] R. Deng, R. Lu, C. Lai, and T. H. Luan, “Towards power consumption-delay tradeoff by workload allocation in cloud-fog computing,” in _IEEE ICC_ , 2015\.
  * [7] G. Lee, W. Saad, and M. Bennis, “An online secretary framework for fog network formation with minimal latency,” in _IEEE ICC_ , 2017.
  * [8] J. Yuan and A. Lamperski, “Online convex optimization for cumulative constraints,” in _NIPS_ , 2018.
  * [9] M. Mahdavi, R. Jin, and T. Yang, “Trading regret for efficiency: online convex optimization with long term constraints,” _The Journal of Machine Learning Research_ , 2012.
  * [10] M. J. Neely and H. Yu, “Online convex optimization with time-varying constraints,” _arXiv preprint arXiv:1702.04783_ , 2017.
  * [11] N. Liakopoulos _et al._ , “Cautious regret minimization: Online optimization with long-term budget constraints,” in _ICML_ , 2019.
  * [12] X. Cao, J. Zhang, and H. V. Poor, “Constrained online convex optimization with feedback delays,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 11, pp. 5049–5064, 2020.
  * [13] X. Yi, X. Li, L. Xie, and K. H. Johansson, “Distributed online convex optimization with time-varying coupled inequality constraints,” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 731–746, 2020.
  * [14] V. B. C. Souza, W. Ramírez, X. Masip-Bruin, E. Marín-Tordera, G. Ren, and G. Tashakor, “Handling service allocation in combined fog-cloud scenarios,” in _IEEE ICC_ , 2016.
  * [15] A. Yousefpour, G. Ishigaki, and J. P. Jue, “Fog computing: Towards minimizing delay in the internet of things,” in _IEEE EDGE_ , 2017.
  * [16] A. Jadbabaie _et al._ , “Online optimization: Competing with dynamic comparators,” in _Artificial Intelligence and Statistics_. PMLR, 2015, pp. 398–406.
  * [17] T. Italia, “Telecommunications - SMS, Call, Internet - MI,” 2015. [Online]. Available: https://doi.org/10.7910/DVN/EGZHFV
  * [18] S. Diamond and S. Boyd, “Cvxpy: A python-embedded modeling language for convex optimization,” _The Journal of Machine Learning Research_ , vol. 17, no. 1, pp. 2909–2913, 2016.

##  Appendix A Proof of Theorem 1

In this section, we provide the upper bounds of the static regret, the dynamic
regret and the fit as a function of $T$. To that extent, we remind that:

$\displaystyle f^{t}(\mathbf{x}^{t})$ $\displaystyle=\sum_{d\in
D}f_{d}^{t}(\mathbf{x}_{d}^{t})+\sum_{b\in
B}f_{b}^{t}(\mathbf{x}_{b}^{t})+\sum_{s\in S}f_{s}^{t}(\mathbf{x}_{s}^{t})$
$\displaystyle\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})$
$\displaystyle=f^{t}(\mathbf{x}^{t})+[\mathbf{h}^{t}(\mathbf{x}^{t})]^{\top}\boldsymbol{\lambda}^{t},\quad\text{with}\;\;\boldsymbol{\lambda}^{t}=\left((\boldsymbol{\lambda}_{d}^{t})_{d\in
D},(\boldsymbol{\lambda}^{t}_{b})_{b\in
B},(\boldsymbol{\lambda}_{s}^{t})_{s\in S}\right).$

For ease of understanding, we also recall that:

  * •

$\eta$ is the step-size of the decentralized algorithm.

  * •

$|f^{t}_{n}|,\left\lVert\nabla f^{t}_{n}\right\rVert\leq F$; and
$\left\lVert\nabla
g^{t}_{n,i}\right\rVert,\left\lVert\mathbf{g}^{t}_{n}\right\rVert\leq G$ for
$n\in\mathcal{D,B,S}$.

  * •

$R$ is the radius of the space set $\Omega$.

  * •

$\sigma$ is a constant that we will define later.

  * •

$D,B,S$ is the number of devices, BSs and servers respectively.

  * •

$N$ is the number of nodes, i.e. $N=D+B+S$.

  * •

$M$ is the number of the constraint functions, with $M=D(B+1)+B(S+1)+S$.

  * •

$E$ is the total number of edges, i.e. $E=DB+BS+S(S-1)$.

In order to prove the present theorem, let us first introduce the following
Lemma.

######  Lemma 1.

For any node $n$, the next inequality holds:

$\displaystyle(\mathbf{x}_{n}^{t}-\mathbf{x}_{n})^{\top}\nabla_{\mathbf{x}_{n}}\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})$
$\displaystyle\leq\frac{1}{2\eta}\left(\left\lVert\mathbf{x}_{n}-\mathbf{x}_{n}^{t}\right\rVert^{2}-\left\lVert\mathbf{x}_{n}-\mathbf{x}_{n}^{t+1}\right\rVert^{2}\right)$
$\displaystyle\quad+2\eta
F^{2}+2\eta(c_{1,n}+c_{2,n})G^{2}\left\lVert\boldsymbol{\lambda}^{t}\right\rVert^{2}+2\eta
c_{2,n}G^{2}\left(\left\lVert\boldsymbol{\lambda}^{t}\right\rVert^{2}+\left\lVert\boldsymbol{\lambda}^{t-1}\right\rVert^{2}\right)$
$\displaystyle\quad+\frac{3}{2}\eta\left(F^{2}+c_{1,n}G^{2}\left\lVert\boldsymbol{\lambda}^{t-1}\right\rVert^{2}+c_{2,n}G^{2}\left\lVert\boldsymbol{\lambda}^{t-2}\right\rVert^{2}\right)+\frac{\eta}{2}c_{2,n}G^{2}\left\lVert\boldsymbol{\lambda}^{t-1}\right\rVert^{2}$
$\displaystyle\quad+(\mathbf{x}_{n}^{t}-\mathbf{x}_{n})^{\top}\mathbf{H}^{t}_{nE}-(\mathbf{x}_{n}^{t-1}-\mathbf{x}_{n})^{\top}\mathbf{H}^{t-1}_{nE}$
$\displaystyle=\frac{1}{2\eta}\left(\left\lVert\mathbf{x}_{n}-\mathbf{x}_{n}^{t}\right\rVert^{2}-\left\lVert\mathbf{x}_{n}-\mathbf{x}_{n}^{t+1}\right\rVert^{2}\right)+\frac{7}{2}\eta
F^{2}$ $\displaystyle\quad+2(c_{1,n}+2c_{2,n})\eta
G^{2}\left\lVert\boldsymbol{\lambda}^{t}\right\rVert^{2}+\frac{1}{2}(3c_{1,n}+5c_{2,n})\eta
G^{2}\left\lVert\boldsymbol{\lambda}^{t-1}\right\rVert^{2}+\frac{3}{2}c_{2,n}\eta
G^{2}\left\lVert\boldsymbol{\lambda}^{t-2}\right\rVert^{2}$
$\displaystyle\quad+(\mathbf{x}_{n}^{t}-\mathbf{x}_{n})^{\top}\mathbf{H}^{t}_{nE}-(\mathbf{x}_{n}^{t-1}-\mathbf{x}_{n})^{\top}\mathbf{H}^{t-1}_{nE}$
(34)

where $\mathbf{H}^{t}_{nE}$ is defined in (27)-(29), $c_{1,n}$ is the number
of local constraints at node $k$ and $c_{2,n}$ is the number of flow
constraints from other nodes that include an optimization variable of node
$k$. Specifically:

$c_{1,n}=\begin{cases}B+1&\text{for $n=d$}\\\ N+1&\text{for $n=b$}\\\
1&\text{for $n=s$}\end{cases},\quad c_{2,n}=\begin{cases}B&\text{for $n=d$}\\\
N&\text{for $n=b$}\\\ N-1&\text{for $n=s$}\end{cases}.$

###### Proof.

We prove in detail only the expression for the devices, as the respective
expressions for BSs and servers is straight-forward following exactly the same
steps. Thus, we have

$\displaystyle\left\lVert\mathbf{x}_{d}-\mathbf{x}_{d}^{t+1}\right\rVert^{2}$
$\displaystyle\overset{(a)}{\leq}\left\lVert\mathbf{x}_{d}-\Bigg{(}\mathbf{x}_{d}^{t}-\eta\bigg{(}\nabla_{\mathbf{x}_{d}}f_{d}^{t}(\mathbf{x}_{d}^{t})+\nabla_{\mathbf{x}_{d}}^{\top}[\mathbf{h}_{d}^{t}(\mathbf{x}_{d}^{t})]\boldsymbol{\lambda}^{t}_{d}+\sum_{b\in\mathcal{B}}\nabla_{\mathbf{x}_{d}}h^{t-1}_{b0}(\mathbf{x}_{b}^{t-1};\mathbf{x}^{t-1}_{\mathcal{D}})\lambda^{t-1}_{b0}\bigg{)}\Bigg{)}\right\rVert^{2}$
$\displaystyle\overset{(b)}{=}\left\lVert\big{(}\mathbf{x}_{d}-\mathbf{x}_{d}^{t}\big{)}+\eta\Bigg{[}\nabla_{\mathbf{x}_{d}}\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})+\nabla_{\mathbf{x}_{d}}\bigg{[}\sum\limits_{b\in\mathcal{B}}\Big{[}h^{t-1}_{b0}(\mathbf{x}_{b}^{t-1};\mathbf{x}^{t-1}_{\mathcal{D}})\lambda_{b0}^{t-1}-h^{t}_{b0}(\mathbf{x}_{b}^{t};\mathbf{x}^{t}_{\mathcal{D}})\lambda_{b0}^{t}\Big{]}\bigg{]}\Bigg{]}\right\rVert^{2}$
$\displaystyle\overset{(c)}{\leq}\left\lVert\mathbf{x}_{d}-\mathbf{x}_{d}^{t}\right\rVert^{2}+2\eta^{2}\left\lVert\nabla_{\mathbf{x}_{d}}\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})\right\rVert^{2}+2\eta^{2}\left\lVert\nabla_{\mathbf{x}_{d}}\bigg{[}\sum\limits_{b\in\mathcal{B}}\Big{[}h^{t-1}_{b0}(\mathbf{x}_{b}^{t-1};\mathbf{x}^{t-1}_{\mathcal{D}})\lambda_{b0}^{t-1}-h^{t}_{b0}(\mathbf{x}_{b}^{t};\mathbf{x}^{t}_{\mathcal{D}})\lambda_{b0}^{t}\Big{]}\bigg{]}\right\rVert^{2}$
$\displaystyle\quad+2\eta(\mathbf{x}_{d}-\mathbf{x}^{t}_{d})^{\top}\nabla_{\mathbf{x}_{d}}\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})+2\eta(\mathbf{x}_{d}-\mathbf{x}_{d}^{t})^{\top}\nabla_{\mathbf{x}_{d}}\bigg{[}\sum\limits_{b\in\mathcal{B}}\Big{[}h^{t-1}_{b0}(\mathbf{x}_{b}^{t-1};\mathbf{x}^{t-1}_{\mathcal{D}})\lambda_{b0}^{t-1}-h^{t}_{b0}(\mathbf{x}_{b}^{t};\mathbf{x}^{t}_{\mathcal{D}})\lambda_{b0}^{t}\Big{]}\bigg{]},$
(35)

where:

  * •

(a) comes from the update rule of $\mathbf{x}_{d}^{t+1}$ and Assumption 1 on
the projection non-expansiveness.

  * •

(b) uses the expression of
$\nabla_{\mathbf{x}_{d}}\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})$
from (25).

  * •

(c) uses
$\left\lVert\mathbf{x}+\mathbf{y}\right\rVert^{2}=\left\lVert\mathbf{x}\right\rVert^{2}+\left\lVert\mathbf{y}\right\rVert^{2}+2\mathbf{x}^{\top}\mathbf{y}$
and then $\left\lVert\mathbf{x}+\mathbf{y}\right\rVert^{2}\leq
2(\left\lVert\mathbf{x}\right\rVert^{2}+\left\lVert\mathbf{y}\right\rVert^{2})$.

Therefore, we have:

$\displaystyle(\mathbf{x}_{d}^{t}-\mathbf{x}_{d})^{\top}\nabla_{\mathbf{x}_{d}}\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})$
$\displaystyle\leq\frac{1}{2\eta}\bigg{(}\left\lVert\mathbf{x}_{d}-\mathbf{x}_{d}^{t}\right\rVert^{2}-\left\lVert\mathbf{x}_{d}-\mathbf{x}_{d}^{t+1}\right\rVert^{2}\bigg{)}+\eta\left\lVert\nabla_{\mathbf{x}_{d}}\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})\right\rVert^{2}$
$\displaystyle\quad+\eta\left\lVert\nabla_{\mathbf{x}_{d}}\sum\limits_{b\in\mathcal{B}}\big{[}h^{t-1}_{b0}(\mathbf{x}_{b}^{t-1};\mathbf{x}^{t-1}_{\mathcal{D}})\lambda_{b0}^{t-1}-h^{t}_{b0}(\mathbf{x}_{b}^{t};\mathbf{x}^{t}_{\mathcal{D}})\lambda_{b0}^{t}\big{]}\right\rVert^{2}$
$\displaystyle\quad+(\mathbf{x}_{d}-\mathbf{x}_{d}^{t})^{\top}\nabla_{\mathbf{x}_{d}}\bigg{[}\sum\limits_{b\in\mathcal{B}}\big{[}h^{t-1}_{b0}(\mathbf{x}_{b}^{t-1};\mathbf{x}^{t-1}_{\mathcal{D}})\lambda_{b}^{t-1}-h^{t}_{b0}(\mathbf{x}_{b}^{t};\mathbf{x}^{t}_{\mathcal{D}})\lambda_{b0}^{t}\big{]}\bigg{]}.$
(36)

We continue by analyzing each term of (A). Specifically, we have:

$\displaystyle\eta\left\lVert\nabla_{\mathbf{x}_{d}}\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})\right\rVert^{2}$
$\displaystyle=\eta\left\lVert\nabla_{\mathbf{x}_{d}}f_{d}^{t}(\mathbf{x}_{d}^{t})+\nabla_{\mathbf{x}_{d}}^{\top}[\mathbf{h}_{d}^{t}(\mathbf{x}_{d}^{t})]\boldsymbol{\lambda}^{t}_{d}+\sum_{b\in\mathcal{B}}\nabla_{\mathbf{x}_{d}}h^{t}_{b0}(\mathbf{x}_{b}^{t};\mathbf{x}^{t}_{\mathcal{D}})\lambda^{t}_{b0}\right\rVert^{2}$
$\displaystyle\overset{(a)}{\leq}\eta\Bigg{(}F+\left\lVert\nabla_{\mathbf{x}_{d}}^{\top}[\mathbf{h}_{d}^{t}(\mathbf{x}_{d}^{t})]\boldsymbol{\lambda}^{t}_{d}+\sum_{b\in\mathcal{B}}\nabla_{\mathbf{x}_{d}}h^{t}_{b0}(\mathbf{x}_{b}^{t};\mathbf{x}^{t}_{\mathcal{D}})\lambda^{t}_{b0}\right\rVert\Bigg{)}^{2}$
$\displaystyle\overset{(b)}{\leq}2\eta
F^{2}+2\eta\bigg{(}\left\lVert\nabla_{\mathbf{x}_{d}}^{\top}[\mathbf{h}_{d}^{t}(\mathbf{x}_{d}^{t})]\boldsymbol{\lambda}^{t}_{d}\right\rVert+\sum_{b\in\mathcal{B}}\left\lVert\nabla_{\mathbf{x}_{d}}h^{t}_{b0}(\mathbf{x}_{b}^{t};\mathbf{x}^{t}_{\mathcal{D}})\lambda^{t}_{b0}\right\rVert\bigg{)}^{2}$
$\displaystyle\overset{(c)}{\leq}2\eta F^{2}+2\eta
G^{2}\big{(}|\lambda^{t}_{d0}|+\sum\limits_{b\in\mathcal{B}}|\lambda_{db}^{t}|+\sum\limits_{b\in\mathcal{B}}|\lambda_{b0}^{t}|\big{)}^{2}$
$\displaystyle\overset{(d)}{\leq}2\eta
F^{2}+2\eta(2B+1)G^{2}\left\lVert\boldsymbol{\lambda}^{t}\right\rVert^{2}$
(37)

where:

  * •

(a) uses
$\left\lVert\mathbf{x}+\mathbf{y}\right\rVert\leq\left\lVert\mathbf{x}\right\rVert+\left\lVert\mathbf{y}\right\rVert$
and then $\left\lVert\nabla{f^{t}_{d}(\mathbf{x}^{t})}\right\rVert\leq F$.

  * •

(b) uses first $\left\lVert\mathbf{x}+\mathbf{y}\right\rVert^{2}\leq
2(\left\lVert\mathbf{x}\right\rVert^{2}+\left\lVert\mathbf{y}\right\rVert^{2})$
and then
$\left\lVert\mathbf{x}+\mathbf{y}\right\rVert\leq\left\lVert\mathbf{x}\right\rVert+\left\lVert\mathbf{y}\right\rVert$.

  * •

(c) follows from $\left\lVert\nabla{h^{t}_{i}(\mathbf{x}^{t})}\right\rVert\leq
G\;\forall i\in[1,M]$.

  * •

(d) uses $(\sum\limits_{i=1}^{K}a_{i})^{2}\leq
K\sum\limits_{i=1}^{K}a_{i}^{2}$ and the fact that $2B+1\leq
M\Rightarrow|{\lambda}_{d0}^{t}|^{2}+\sum\limits_{b\in\mathcal{B}}|\lambda_{db}^{t}|^{2}+\sum\limits_{b\in\mathcal{B}}|\lambda_{b0}^{t}|^{2}\leq\left\lVert\boldsymbol{\lambda}^{t}\right\rVert^{2}$.

Following the same procedure, i.e. steps (b)-(d), for the second term of (A),
we get:

$\displaystyle\eta\left\lVert\nabla_{\mathbf{x}_{d}}\sum\limits_{b\in\mathcal{B}}\big{[}h^{t-1}_{b0}(\mathbf{x}_{b}^{t-1};\mathbf{x}^{t-1}_{\mathcal{D}})\lambda_{b0}^{t-1}-h^{t}_{b0}(\mathbf{x}_{b}^{t};\mathbf{x}^{t}_{\mathcal{D}})\lambda_{b}^{t}\big{]}\right\rVert^{2}$
$\displaystyle\leq 2\eta
G^{2}\left(\Big{(}\sum\limits_{b\in\mathcal{B}}|\lambda_{b0}^{t-1}|\Big{)}^{2}+\Big{(}\sum\limits_{b\in\mathcal{B}}|\lambda_{b0}^{t}|\Big{)}^{2}\right)$
$\displaystyle\leq 2\eta
BG^{2}\Big{(}\left\lVert\boldsymbol{\lambda}^{t}\right\rVert^{2}+\left\lVert\boldsymbol{\lambda}^{t-1}\right\rVert^{2}\Big{)}$
(38)

For the last term of (A), if we add and subtract the term
$(\mathbf{x}_{d}^{t-1})^{\top}\nabla_{\mathbf{x}_{d}}\bigg{[}\sum\limits_{b\in\mathcal{B}}h^{t-1}_{b0}(\mathbf{x}_{b}^{t-1};\mathbf{x}^{t-1}_{\mathcal{D}})\lambda_{b0}^{t-1}\bigg{]}$
we get:

$\displaystyle(\mathbf{x}_{d}-\mathbf{x}_{d}^{t})^{\top}\nabla_{\mathbf{x}_{d}}\bigg{[}\sum\limits_{b\in\mathcal{B}}\big{[}h^{t-1}_{b0}(\mathbf{x}_{b}^{t-1};\mathbf{x}^{t-1}_{\mathcal{D}})\lambda_{b0}^{t-1}-h^{t}_{b0}(\mathbf{x}_{b}^{t};\mathbf{x}^{t}_{\mathcal{D}})\lambda_{b0}^{t}\big{]}\bigg{]}=(\mathbf{x}_{d}-\mathbf{x}_{d}^{t-1})^{\top}\nabla_{\mathbf{x}_{d}}\bigg{[}\sum\limits_{b\in\mathcal{B}}h^{t-1}_{b0}(\mathbf{x}_{b}^{t-1};\mathbf{x}^{t-1}_{\mathcal{D}})\lambda_{b0}^{t-1}\bigg{]}$
$\displaystyle\quad-(\mathbf{x}_{d}-\mathbf{x}_{d}^{t})^{\top}\nabla_{\mathbf{x}_{d}}\bigg{[}\sum\limits_{b\in\mathcal{B}}h^{t}_{b0}(\mathbf{x}_{b}^{t};\mathbf{x}^{t}_{\mathcal{D}})\lambda_{b0}^{t}\bigg{]}+(\mathbf{x}_{d}^{t-1}-\mathbf{x}_{d}^{t})^{\top}\nabla_{\mathbf{x}_{d}}\bigg{[}\sum\limits_{b\in\mathcal{B}}h^{t-1}_{b0}(\mathbf{x}_{b}^{t-1};\mathbf{x}^{t-1}_{\mathcal{D}})\lambda_{b0}^{t-1}\bigg{]}.$
(39)

For the last term of (A) we have:

$\displaystyle(\mathbf{x}_{d}^{t-1}-\mathbf{x}_{d}^{t})^{\top}\nabla_{\mathbf{x}_{d}}\bigg{[}\sum\limits_{b\in\mathcal{B}}h^{t-1}_{b0}(\mathbf{x}_{b}^{t-1};\mathbf{x}^{t-1}_{\mathcal{D}})\lambda_{b0}^{t-1}\bigg{]}\overset{(a)}{\leq}\frac{1}{2\eta}\left\lVert\mathbf{x}_{d}^{t}-\mathbf{x}_{d}^{t-1}\right\rVert^{2}+\frac{\eta}{2}\left\lVert\nabla_{\mathbf{x}_{d}}\bigg{[}\sum\limits_{b\in\mathcal{B}}h^{t-1}_{b0}(\mathbf{x}_{b}^{t-1};\mathbf{x}^{t-1}_{\mathcal{D}})\lambda_{b0}^{t-1}\bigg{]}\right\rVert^{2}$
$\displaystyle\quad\overset{(b)}{\leq}\frac{\eta}{2}\left\lVert\nabla_{\mathbf{x}_{d}}f_{d}^{t-1}(\mathbf{x}_{d}^{t-1})+\nabla^{\top}_{\mathbf{x}_{d}}[\mathbf{h}^{t-1}_{d}(\mathbf{x}_{d}^{t-1})]\boldsymbol{\lambda}_{d}^{t-1}+\sum\limits_{b\in\mathcal{B}}\nabla_{\mathbf{x}_{d}}[h^{t-2}_{b0}(\mathbf{x}_{b}^{t-2};\mathbf{x}^{t-2}_{\mathcal{D}})]\lambda_{b0}^{t-2}\right\rVert^{2}+\frac{\eta}{2}BG^{2}\left\lVert\boldsymbol{\lambda}^{t-1}\right\rVert^{2}$
$\displaystyle\quad\overset{(c)}{\leq}\frac{3\eta}{2}\left(F^{2}+(B+1)G^{2}\left\lVert\boldsymbol{\lambda}^{t-1}\right\rVert^{2}+BG^{2}\left\lVert\boldsymbol{\lambda}^{t-2}\right\rVert^{2}\right)+\frac{\eta}{2}BG^{2}\left\lVert\boldsymbol{\lambda}^{t-1}\right\rVert^{2},$
(40)

where:

  * •

(a) uses
$\mathbf{x}^{\top}\mathbf{y}\leq\frac{1}{2\eta}\left(\left\lVert\mathbf{x}\right\rVert^{2}+\eta^{2}\left\lVert\mathbf{y}\right\rVert^{2}\right)$

  * •

(b) comes from the update rule of $\mathbf{x}_{d}^{t}$ and Assumption 1.

  * •

(c) uses $\left\lVert\mathbf{x}+\mathbf{y}+\mathbf{z}\right\rVert^{2}\leq
3(\left\lVert\mathbf{x}\right\rVert^{2}+\left\lVert\mathbf{y}\right\rVert^{2}+\left\lVert\mathbf{z}\right\rVert^{2})$

Combining (A)-(A) we directly obtain (1). Following the same steps for BSs and
servers completes the proof of Lemma 1. ∎

The next step to prove the theorem is to combine the results of Lemma 1 for
all nodes. According to Assumption 1,
$\mathcal{L}^{t}(.,\boldsymbol{\lambda})$ is a convex function with
$\mathbf{x}$ and thus, we have

$\displaystyle\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})-\mathcal{L}^{t}(\mathbf{x},\boldsymbol{\lambda}^{t})$
$\displaystyle\leq(\mathbf{x}^{t}-\mathbf{x})^{\top}\nabla_{x}\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})$
$\displaystyle=\sum\limits_{d\in\mathcal{D}}(\mathbf{x}_{d}^{t}-\mathbf{x}_{d})^{\top}\nabla_{\mathbf{x}_{d}}\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})+\sum\limits_{b\in\mathcal{B}}(\mathbf{x}_{b}^{t}-\mathbf{x}_{b})^{\top}\nabla_{\mathbf{x}_{b}}\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})+\sum\limits_{s\in\mathcal{S}}(\mathbf{x}_{s}^{t}-\mathbf{x}_{s})^{\top}\nabla_{\mathbf{x}_{s}}\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t}).$
(41)

Then, from Lemma 1 we get:

$\displaystyle\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})-\mathcal{L}^{t}(\mathbf{x},\boldsymbol{\lambda}^{t})$
$\displaystyle\leq\frac{1}{2\eta}\Big{(}\left\lVert\mathbf{x}-\mathbf{x}^{t}\right\rVert^{2}-\left\lVert\mathbf{x}-\mathbf{x}^{t+1}\right\rVert^{2}\Big{)}+\frac{7}{2}\eta
NF^{2}$ $\displaystyle\quad+\Big{(}(6DB+2D)+(6BS+2B)+(4S^{2}-2S)\Big{)}\eta
G^{2}\left\lVert\boldsymbol{\lambda}^{t}\right\rVert^{2}$
$\displaystyle\quad+\Big{(}(4DB+\frac{3}{2}D)+(4BS+\frac{3}{2}B)+(\frac{5}{2}S^{2}-S)\Big{)}\eta
G^{2}\left\lVert\boldsymbol{\lambda}^{t-1}\right\rVert^{2}$
$\displaystyle\quad+\frac{3}{2}\Big{(}DB+BS+S(S-1)\Big{)}\eta
G^{2}\left\lVert\boldsymbol{\lambda}^{t-2}\right\rVert^{2}+Q^{t}(\mathbf{x})-Q^{t-1}(\mathbf{x})$
(42)

where

$\displaystyle Q^{t}(\mathbf{x})$
$\displaystyle:=\sum\limits_{d\in\mathcal{D}}\Bigg{[}(\mathbf{x}_{d}^{t}-\mathbf{x}_{d})^{\top}\nabla_{\mathbf{x}_{d}}\bigg{[}\sum\limits_{b\in\mathcal{B}}h^{t}_{b0}(\mathbf{x}_{b}^{t};\mathbf{x}^{t}_{\mathcal{D}})\lambda_{b0}^{t}\bigg{]}\Bigg{]}+\sum\limits_{b\in\mathcal{B}}\Bigg{[}(\mathbf{x}_{b}^{t}-\mathbf{x}_{b})^{\top}\nabla_{\mathbf{x}_{b}}\bigg{[}\sum\limits_{s\in\mathcal{S}}h^{t}_{s0}(\mathbf{x}^{t}_{s};\mathbf{x}^{t}_{\mathcal{B}},\mathbf{x}^{t}_{\mathcal{S}_{-s}})\lambda_{s0}^{t}\bigg{]}\Bigg{]}$
$\displaystyle\quad+\sum\limits_{s\in\mathcal{S}}\Bigg{[}(\mathbf{x}_{s}^{t}-\mathbf{x}_{s})^{\top}\nabla_{\mathbf{x}_{s}}\bigg{[}\sum\limits_{s^{\prime}\in\mathcal{S}_{-s}}h_{s^{\prime}0}^{t}(\mathbf{x}_{s^{\prime}}^{t};\mathbf{x}_{\mathcal{B}}^{t},\mathbf{x}^{t}_{\mathcal{S}_{-s^{\prime}}})\lambda_{s^{\prime}0}^{t}\bigg{]}\Bigg{]}$
(43)

To upper-bound the multiplicative terms in front of the multipliers in (A), we
define

$\displaystyle K=2D(3B+1)+2B(3S+1)+2S(2S-1),$ (44)

and get

$\displaystyle\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})-\mathcal{L}^{t}(\mathbf{x},\boldsymbol{\lambda}^{t})$
$\displaystyle\leq\frac{1}{2\eta}\underbrace{\Big{(}\left\lVert\mathbf{x}-\mathbf{x}^{t}\right\rVert^{2}-\left\lVert\mathbf{x}-\mathbf{x}^{t+1}\right\rVert^{2}\Big{)}}_{\text{(a)}}+\underbrace{Q^{t}(\mathbf{x})-Q^{t-1}(\mathbf{x})}_{\text{(b)}}+\frac{7}{2}\eta
NF^{2}$ $\displaystyle\quad+\eta
KG^{2}\underbrace{\Big{(}\left\lVert\boldsymbol{\lambda}^{t}\right\rVert^{2}+\left\lVert\boldsymbol{\lambda}^{t-1}\right\rVert^{2}+\left\lVert\boldsymbol{\lambda}^{t-2}\right\rVert^{2}\Big{)}}_{\text{(c)}}.$
(45)

We then sum from $t=1\to T$ and upper-bound the (a)-(c) terms of (A) using the
following:

  * •

(a)
$\sum\limits_{t=1}^{T}(\left\lVert\mathbf{x}-\mathbf{x}^{t}\right\rVert^{2}-\left\lVert\mathbf{x}-\mathbf{x}^{t+1}\right\rVert^{2})=\left\lVert\mathbf{x}-\mathbf{x}^{1}\right\rVert^{2}-\left\lVert\mathbf{x}-\mathbf{x}^{T+1}\right\rVert^{2}\leq\left\lVert\mathbf{x}^{1}-\mathbf{x}\right\rVert^{2}\leq
R^{2}$;

  * •

(b)
$\sum\limits_{t=1}^{T}(Q^{t}(\mathbf{x})-Q^{t-1}(\mathbf{x}))=Q^{T}(\mathbf{x})-Q^{0}(\mathbf{x})\leq\left\lVert
Q^{T}(\mathbf{x})\right\rVert+\left\lVert
Q^{0}(\mathbf{x})\right\rVert\leq\frac{2REG^{2}}{\eta\sigma}$, where in the
last step we use $\left\lVert
Q^{t}(\mathbf{x})\right\rVert\leq\left(DB+BS+S(S-1)\right)RG\left\lVert\boldsymbol{\lambda}^{t}\right\rVert$
according to (A) and the update rule
$\boldsymbol{\lambda}^{t}=\frac{\mathbf{h}^{t}({\mathbf{x}}^{t})}{\eta\sigma}$;

  * •

(c)
$\sum\limits_{t=1}^{T}(\left\lVert\boldsymbol{\lambda}^{t}\right\rVert^{2}+\left\lVert\boldsymbol{\lambda}^{t-1}\right\rVert^{2}+\left\lVert\boldsymbol{\lambda}^{t-2}\right\rVert^{2})=3\sum\limits_{t=1}^{T}\left\lVert\boldsymbol{\lambda}^{t}\right\rVert^{2}-2\left\lVert\boldsymbol{\lambda}^{T}\right\rVert^{2}-\left\lVert\boldsymbol{\lambda}^{T-1}\right\rVert^{2}$,
assuming $\left\lVert\boldsymbol{\lambda}^{0}\right\rVert=0$ and
$\left\lVert\boldsymbol{\lambda}^{-1}\right\rVert=0$.

Putting everything together we have:

$\sum\limits_{t=1}^{T}\left(\mathcal{L}^{t}(\mathbf{x}^{t},\boldsymbol{\lambda}^{t})-\mathcal{L}^{t}(\mathbf{x},\boldsymbol{\lambda}^{t})\right)\leq\frac{R^{2}}{2\eta}+\frac{2REG^{2}}{\eta\sigma}+\frac{7}{2}\eta
NF^{2}T+3\eta
KG^{2}\sum\limits_{t=1}^{T}\left\lVert\boldsymbol{\lambda}^{t}\right\rVert^{2}\\\
$ (46)

###  A-A Static Regret

If we set $x=x_{*}$ for which $\mathbf{h}^{t}(\mathbf{x}_{*})=0$ and use
$\boldsymbol{\lambda}^{t}=\frac{\mathbf{h}^{t}({\mathbf{x}}^{t})}{\eta\sigma}$,
we get

$\displaystyle\sum\limits_{t=1}^{T}\Big{(}f^{t}(\mathbf{x}^{t})+\frac{\left\lVert\mathbf{h}^{t}(\mathbf{x}^{t})\right\rVert^{2}}{\eta\sigma}-f^{t}(\mathbf{x}_{*})\Big{)}\leq\frac{R^{2}}{2\eta}+\frac{2REG^{2}}{\eta\sigma}+\frac{7}{2}\eta
NF^{2}T+3KG^{2}\sum\limits_{t=1}^{T}\frac{\left\lVert\mathbf{h}^{t}(\mathbf{x}^{t})\right\rVert^{2}}{\eta\sigma^{2}},$
(47)

that yields

$\displaystyle\sum\limits_{t=1}^{T}\Big{(}f^{t}(\mathbf{x}^{t})-f^{t}(\mathbf{x}_{*})\Big{)}+\frac{1}{\eta\sigma}\sum\limits_{t=1}^{T}\left\lVert\mathbf{h}^{t}({\mathbf{x}^{t}})\right\rVert^{2}(1-\frac{3KG^{2}}{\sigma})\leq\frac{R^{2}}{2\eta}+\frac{2REG^{2}}{\eta\sigma}+\frac{7}{2}\eta
NF^{2}T.$ (48)

For $\sigma>3KG^{2}$, the upper bound $U_{sr}$ of the static regret is found
by

$\sum\limits_{t=1}^{T}\Big{(}f^{t}(\mathbf{x}^{t})-f^{t}(\mathbf{x}_{*})\Big{)}\leq\frac{R^{2}}{2\eta}+\frac{2REG^{2}}{\eta\sigma}+\frac{7}{2}\eta
NF^{2}T\triangleq U_{sr}.$ (49)

###  A-B Dynamic Regret

Choosing again $\sigma>3KG^{2}$ and plugging the instantaneous optimal
solution $x=x^{t}_{*}$ in (A), we follow the procedure we used for the static
regret and obtain:

$\sum\limits_{t=1}^{T}\Big{(}f^{t}(\mathbf{x}^{t})-f^{t}(\mathbf{x}^{t}_{*})\Big{)}\leq\frac{1}{2\eta}\sum\limits_{t=1}^{T}(\left\lVert\mathbf{x}_{*}^{t}-\mathbf{x}^{t}\right\rVert^{2}-\left\lVert\mathbf{x}_{*}^{t}-\mathbf{x}^{t+1}\right\rVert^{2})+\frac{2REG^{2}}{\eta\sigma}+\frac{7}{2}\eta
NF^{2}T.$ (50)

The only term that needs different handling is
$\left\lVert\mathbf{x}_{*}^{t}-\mathbf{x}^{t}\right\rVert^{2}-\left\lVert\mathbf{x}_{*}^{t}-\mathbf{x}^{t+1}\right\rVert^{2}$,
for which we can write

$\displaystyle\left\lVert\mathbf{x}_{*}^{t}-\mathbf{x}^{t}\right\rVert^{2}-\left\lVert\mathbf{x}_{*}^{t}-\mathbf{x}^{t+1}\right\rVert^{2}=\underbrace{\left\lVert\mathbf{x}_{*}^{t}-\mathbf{x}^{t}\right\rVert^{2}-\left\lVert\mathbf{x}_{*}^{t-1}-\mathbf{x}^{t}\right\rVert^{2}}_{\text{(a)}}+\underbrace{\left\lVert\mathbf{x}_{*}^{t-1}-\mathbf{x}^{t}\right\rVert^{2}-\left\lVert\mathbf{x}_{*}^{t}-\mathbf{x}^{t+1}\right\rVert^{2}}_{\text{(b)}}.$
(51)

We are interested in the telescopic sums of (a, b). In particular, for (a) we
use
$\mathbf{x}^{2}-\mathbf{y}^{2}=(\mathbf{x}-\mathbf{y})^{\top}(\mathbf{x}+\mathbf{y})$
and get

$\displaystyle\sum\limits_{t=1}^{T}\left(\left\lVert\mathbf{x}_{*}^{t}-\mathbf{x}^{t}\right\rVert^{2}-\left\lVert\mathbf{x}_{*}^{t-1}-\mathbf{x}^{t}\right\rVert^{2}\right)$
$\displaystyle=\sum\limits_{t=1}^{T}(\mathbf{x}_{*}^{t}-\mathbf{x}_{*}^{t-1})^{\top}(\mathbf{x}_{*}^{t}+\mathbf{x}_{*}^{t-1}-2\mathbf{x}^{t})\leq\sum\limits_{t=1}^{T}\left\lVert\mathbf{x}_{*}^{t}+\mathbf{x}_{*}^{t}-2\mathbf{x}^{t}\right\rVert\left\lVert\mathbf{x}_{*}^{t}-\mathbf{x}_{*}^{t-1}\right\rVert$
$\displaystyle\leq
2R\sum\limits_{t=1}^{T}\left\lVert\mathbf{x}_{*}^{t}-\mathbf{x}_{*}^{t-1}\right\rVert=2RV(\mathbf{x}_{*}^{1:T})$
(52)

where $V(\mathbf{x}_{*}^{1:T})$ is the sum of distances of consecutive optimal
solutions. Moreover, for term (b) we have

$\sum\limits_{t=1}^{T}(\left\lVert\mathbf{x}_{*}^{t-1}-\mathbf{x}^{t}\right\rVert^{2}-\left\lVert\mathbf{x}_{*}^{t}-\mathbf{x}^{t+1}\right\rVert^{2})=\left\lVert\mathbf{x}_{*}^{0}-\mathbf{x}^{1}\right\rVert^{2}-\left\lVert\mathbf{x}_{*}^{T}-\mathbf{x}^{T+1}\right\rVert^{2}\leq
R^{2}.$ (53)

Finally, the upper bound $U_{dr}$ of the dynamic regret is

$\sum\limits_{t=1}^{T}\Big{(}f^{t}(\mathbf{x}^{t})-f^{t}(\mathbf{x}^{t}_{*})\Big{)}\leq\frac{R}{\eta}V(\mathbf{x}_{*}^{1:T})+\frac{R^{2}}{2\eta}+\frac{2REG^{2}}{\eta\sigma}+\frac{7}{2}\eta
NF^{2}T\triangleq U_{dr}.$ (54)

By combining (49),(54), the relation to the bound of the static regret is
$U_{dr}=U_{sr}+\frac{R}{\eta}V(\mathbf{x}_{*}^{1:T})$.

###  A-C Fit

In order to bound the fit, we choose $\sigma>3KG^{2}$ in (48) and use
$\sum\limits_{t=1}^{T}\left(f^{t}(\mathbf{x}_{*})-f^{t}(\mathbf{x}^{t})\right)\leq
2NFT$, which gives

$\sum\limits_{t=1}^{T}\left\lVert\mathbf{h}^{t}({\mathbf{x}^{t}})\right\rVert^{2}\leq\frac{1}{\beta}(\frac{\sigma
R^{2}}{2}+2REG^{2}+\frac{7}{2}\eta^{2}\sigma NF^{2}T+2\eta\sigma NFT),$ (55)

where $\beta=1-\frac{3KG^{2}}{\sigma}$. By further using the property
$\Big{(}\sum\limits_{i=1}^{n}a_{i}\Big{)}^{2}\leq
n\sum\limits_{i=1}^{n}a_{i}^{2}$, we obtain

$\displaystyle\Big{(}\sum\limits_{t=1}^{T}\left\lVert\mathbf{h}^{t}(\mathbf{x}^{t})\right\rVert\Big{)}^{2}\leq
T\sum\limits_{t=1}^{T}\left\lVert\mathbf{h}^{t}(\mathbf{x}^{t})\right\rVert^{2}$
$\displaystyle\leq\frac{T}{\beta}(\frac{\sigma
R^{2}}{2}+2REG^{2}+\frac{7}{2}\eta^{2}\sigma NF^{2}T+2\eta\sigma NFT).$ (56)

Taking the square root on both sides of (56)

$\displaystyle\sum\limits_{t=1}^{T}\left\lVert\mathbf{h}^{t}(\mathbf{x}^{t})\right\rVert\leq\Big{(}\frac{T}{\beta}(\frac{\sigma
R^{2}}{2}+2REG^{2}+\frac{7}{2}\eta^{2}\sigma NF^{2}T+2\eta\sigma
NFT)\Big{)}^{1/2}$ (57)

Finally,
$\sum_{m=1}^{M}h_{m}^{t}(\mathbf{x}^{t})\leq\sqrt{M\sum_{m=1}^{M}(h_{m}^{t}(\mathbf{x}^{t}))^{2}}=\sqrt{M}\left\lVert\mathbf{h}^{t}(\mathbf{x}^{t})\right\rVert$
which gives us the upper bound $U_{f}$ on the fit

$\displaystyle\sum\limits_{t=1}^{T}\sum\limits_{m=1}^{M}h_{m}^{t}(\mathbf{x}^{t})\leq\Big{(}\frac{MT}{\beta}(\frac{\sigma
R^{2}}{2}+2REG^{2}+\frac{7}{2}\eta^{2}\sigma NF^{2}T+2\eta\sigma
NFT)\Big{)}^{1/2}.$ (58)

By combining (49),(58), the relation to the bound of the static regret is
$U_{f}=\sqrt{\frac{\eta\sigma}{\beta}MT(U_{sr}+2NFT)}$.

##  Appendix B Proof for implications of Assumption 1

Here we show formally two of the implications of Assumption 1, namely (A) that
$f(\mathbf{x})$ is bounded and (B) that clipped function $h(\mathbf{x})$ is
convex. Below, for simplicity we drop the node $n$ and timestep $t$ sub and
superscripts.

###  B-A Function $f(\mathbf{x})$ is bounded

We want to show that for a finite $f$ for which Assumption 1 holds, there
exists $F$ such that $|f|\leq F$ for all $\mathbf{x}\in\Omega$. From
$\left\lVert\nabla_{\boldsymbol{x}}f\right\rVert\leq F^{\prime}$, it is
implied that for any $\boldsymbol{x},\boldsymbol{y}\in\Omega$, we have

$|f(\boldsymbol{x})-f(\boldsymbol{y})|\leq
F^{\prime}\underbrace{\left\lVert\boldsymbol{x}-\boldsymbol{y}\right\rVert}_{\leq
R}\leq F^{\prime}R.$

Furthermore, using that
$|f(\boldsymbol{x})|-|f(\boldsymbol{y})|\leq|f(\boldsymbol{x})-f(\boldsymbol{y})|\leq
F^{\prime}R$, we get

$|f(\boldsymbol{x})|\leq F^{\prime}R+|f(\boldsymbol{y})|=F,$

where we do not know $|f(\boldsymbol{y})|$, but we know that by definition it
is finite. Since Assumption 1 holds for $g$, the exact same steps can be
followed in order to show that $g$ is bounded.

###  B-B Convexity of $h(\mathbf{x})$

Recall the definitions of $h(\mathbf{x})$ and its gradient

$\displaystyle h(\mathbf{x})=[g(\mathbf{x})]^{+}=\begin{cases}0&\text{if
$g(\mathbf{x})\leq 0$}\\\ g(\mathbf{x})&\text{if
$g(\mathbf{x})>0$}\end{cases}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \nabla
h(\mathbf{x})=\nabla[g(\mathbf{x})]^{+}=\begin{cases}\mathbf{0}&\text{if
$g(\mathbf{x})\leq 0$}\\\ \nabla g(\mathbf{x})&\text{if
$g(\mathbf{x})>0$}\end{cases}$

We want to show that if $g(\mathbf{x})$ is convex, that is,
$g(\mathbf{x})-g(\mathbf{y})\leq(\mathbf{x}-\mathbf{y})^{\top}\nabla
g(\mathbf{x})$, then for any $\mathbf{x},\mathbf{y}\in\Omega$, we have

$h(\mathbf{x})-h(\mathbf{y})\leq(\mathbf{x}-\mathbf{y})^{\top}\nabla
h(\mathbf{x}).$

In what follows, we only use the above definitions of $h$ and its gradient,
and the fact that $g$ is convex. The four possible cases are the following.

(a): If $g(\mathbf{x})>0$ and $g(\mathbf{y})>0$, then
$h(\mathbf{x})-h(\mathbf{y})=g(\mathbf{x})-g(\mathbf{y})\leq(\mathbf{x}-\mathbf{y})^{\top}\nabla
g(\mathbf{x})=(\mathbf{x}-\mathbf{y})^{\top}\nabla h(\mathbf{x}).$

(b): If $g(\mathbf{x})\leq 0$ and $g(\mathbf{y})\leq 0$, then
$h(\mathbf{x})-h(\mathbf{y})=0-0\leq 0=(\mathbf{x}-\mathbf{y})^{\top}\nabla
h(\mathbf{x})$.

(c): If $g(\mathbf{x})>0$ and $g(\mathbf{y})\leq 0$, then
$h(\mathbf{x})-h(\mathbf{y})=h(\mathbf{x})=g(\mathbf{x})\leq
g(\mathbf{x})-g(\mathbf{y})\leq(\mathbf{x}-\mathbf{y})^{\top}\nabla
g(\mathbf{x})=(\mathbf{x}-\mathbf{y})^{\top}\nabla h(\mathbf{x}).$

(d): If $g(\mathbf{x})\leq 0$ and $g(\mathbf{y})>0$, then
$h(\mathbf{x})-h(\mathbf{y})=-h(\mathbf{y})=-g(\mathbf{y})\leq
0=(\mathbf{x}-\mathbf{y})^{\top}\nabla h(\mathbf{x}).$