# Handling Delayed Feedback in Distributed Online Optimization : A Projection-
Free Approach ††thanks: The authors express their gratitude for the support
provided by the Multidisciplinary Institute in Artificial Intelligence,
University Grenoble-Alpes, France (ANR-19-P3IA-0003)

Tuan-Anh Nguyen
LIG, Inria
University Grenoble-Alpes
Saint-Martin-d’Hères, France
<EMAIL_ADDRESS>&Nguyen Kim Thang
LIG, Inria, CNRS, Grenoble INP
University Grenoble-Alpes
Saint-Martin-d’Hères, France
<EMAIL_ADDRESS>
&Denis Trystram
LIG, Inria, CNRS, Grenoble INP
University Grenoble-Alpes
Saint-Martin-d’Hères, France
<EMAIL_ADDRESS>

###### Abstract

Learning at the edges has become increasingly important as large quantities of
data are continually generated locally. Among others, this paradigm requires
algorithms that are _simple_ (so that they can be executed by local devices),
_robust_ (again uncertainty as data are continually generated), and _reliable_
in a distributed manner under network issues, especially delays. In this
study, we investigate the problem of online convex optimization (OCO) under
adversarial delayed feedback. We propose two projection-free algorithms for
centralized and distributed settings in which they are carefully designed to
achieve a regret bound of $\mathcal{O}(\sqrt{B})$ where $B$ is the sum of
delay, which is optimal for the OCO problem in the delay setting while still
being projection-free. We provide an extensive theoretical study and
experimentally validate the performance of our algorithms by comparing them
with existing ones on real-world problems.

_K_ eywords Online Learning $\cdot$ Distributed Learning $\cdot$ Delayed
Feedback $\cdot$ Frank-Wolfe Algorithm

##  1 Introduction

Many machine learning (ML) applications owe their success to factors such as
efficient optimization methods, effective system design, robust computation,
and the availability of enormous amounts of data. In a typical situation, ML
models are trained in an offline and centralized manner. However, in real-life
scenarios, significant portions of data are continuously generated locally at
the user level. Learning at the edge naturally emerges as a new paradigm to
address such issues. In this new paradigm, the development of suitable
learning techniques has become a crucial research objective. Responding to the
requirements (of this new paradigm), online learning has been intensively
studied in recent years. Its efficient use of computational resources,
adaptability to changing environments, scalability, and robustness against
uncertainty show promise as an effective approach for edge devices.

However, online learning/online convex optimization (OCO) problems typically
assume that the feedback is immediately received after a decision is made,
which is too restrictive in many real-world scenarios. For example, a common
problem in online advertising is the delay that occurs between clicking on an
ad and taking subsequent action, such as buying or selling a product. In
distributed systems, the previous assumption is clearly a real issue. Wireless
sensor/mobile networks that exchange information sequentially may experience
delays in feedback due to several problems: connectivity reliability, varying
processing/computation times, heterogeneous data and infrastructures, and
unaware-random events. This can lead to difficulties in maintaining
coordination and efficient data exchange, eventually affecting network
performance and responsiveness. Given these scenarios, the straightforward
application of traditional OCO algorithms often results in inefficient
resource utilization because one must wait for feedback before starting
another round. To address this need, this paper focuses on developing
algorithms that can adapt to adversarial delayed feedback in both centralized
and distributed settings.

#### Model.

We first describe the delay model in a centralized setting. Given a convex set
$\mathcal{K}\subseteq\mathbb{R}^{d}$, at every time step $t$, the decision
maker/agent chooses a decision $\bm{x}_{t}\in\mathcal{K}$ and suffers from a
loss function $f_{t}:\mathcal{K}\rightarrow\mathbb{R}$. We denote by
$d_{t}\geq 1$ an arbitrary delay value of time $t$. In contrast to the
classical OCO problem, the feedback of iteration $t$ is revealed at time
$t+d_{t}-1$. The agent does not know $d_{t}$ in advance and is only aware of
the feedback of iteration $t$ at time $t+d_{t}-1$. Consequently, at time $t$,
the agent receives feedback from the previous iterations
$s\in\mathcal{F}_{t}$, where $\mathcal{F}_{t}=\left\\{s:s+d_{s}-1=t\right\\}$.
In other words, $\mathcal{F}_{t}$ is the set of moments before time $t$ such
that the corresponding feedbacks are released at time $t$. Moreover, the
corresponding feedbacks are not necessarily released in the order of their
iterations. The goal is to minimize regret, which is defined as:

$\displaystyle\mathcal{R}_{T}:=\sum_{t=1}^{T}f_{t}(\bm{x}_{t})-\min_{\bm{x}\in\mathcal{K}}\sum_{t=1}^{T}f_{t}(\bm{x})$

In a distributed setting, we have additionally a set of agents connected over
a network, represented by a graph $\mathcal{G}=(V,E)$ where $n=|V|$ is the
number of agents. Each agent $i\in V$ can communicate with (and only with) its
immediate neighbors, that is, adjacent agents in $\mathcal{G}$. At each time
$t\geq 1$, agent $i$ takes a decision $\bm{x}^{i}_{t}\in\mathcal{K}$ and
suffers a partial loss function $f^{i}_{t}:\mathcal{K}\rightarrow\mathbb{R}$,
which is revealed adversarially and locally to the agent at time
$(t+d^{i}_{t}-1)$ — again, that is unknown to the agent. Similarly, denote
$\mathcal{F}^{i}_{t}=\\{s:s+d^{i}_{s}-1=t\\}$ as the set of feedbacks revealed
to agent $i$ at time $t$ where $d^{i}_{s}$ is the delay of iteration $s$ to
agent $i$. Although the limitation in communication and information, the agent
$i$ is interested in the global loss $F_{t}(.)$ where
$F_{t}(.)=\frac{1}{n}\sum_{i=1}^{n}f^{i}_{t}(.)$. In particular, at time $t$,
the loss of agent $i$ for chosen $\bm{x}^{i}_{t}$ is $F_{t}(\bm{x}^{i}_{t})$.
Note that each agent $i$ does not know $F_{t}$ but has only knowledge of
$f^{i}_{t}$ — its observed cost function. The objective here is to minimize
regret for all agents:

$\mathcal{R}_{T}:=\max_{i}\biggl{(}\sum_{t=1}^{T}F_{t}(\bm{x}^{i}_{t})-\min_{\bm{x}\in\mathcal{K}}\sum_{t=1}^{T}F_{t}(\bm{x})\biggr{)}$

Figure 1: Illustration of delayed feedback in distributed system. Given a time
$t$, each agent holds a distinct pool of available gradient feedback from
$s<t$ that is ready for computation at the current time. The pool can also be
empty if no feedback is provided.

###  1.1 Our contribution

The challenge in designing robust and efficient algorithms for these problems
is to address the following issues simultaneously:

  * •

Uncertainty (online setting, agents observe their loss functions only after
selecting their decisions).

  * •

Asynchronous (distributed setting with different delayed feedback between
agents)

  * •

Partial information (distributed setting, agents know only its local loss
functions while attempting to minimize the cumulative loss).

  * •

Low computation/communication resources of agents (so it is desirable that
each agent performs a small number of gradient computations and
communications).

We introduce performance-guaranteed algorithms in solving the centralized and
distributed constraint online convex optimization problem with adversarial
delayed feedback. Our algorithms achieve an _optimal_ regret bound for
centralized and distributed settings. Specifically, we obtain the regret bound
of $O(\sqrt{B})$ where $B$ is the total delay in the centralized setting and
$B$ is the average total delay over all agents in the distributed setting.
Note that, if $d$ is a maximum delay of each feedback then our regret bound
becomes $\mathcal{O}(\sqrt{dT})$. This result recovers the regret bound of
$O(\sqrt{T})$ in the classic setting without delay (i.e., $d=1$).
Additionally, the algorithms can be made projection-free by selecting
appropriate oracles, allowing them to be implemented in different contexts
based on the computational capacity of local devices. Finally, we illustrate
the practical potential of our algorithms and provide a thorough analysis of
their performance which is predictably explained by our theoretical results.
The experiments demonstrate that our proposed algorithms outperform existing
solutions in both synthetic and real-world datasets.

Table 1: Comparisons to previous algorithms DGD [4] and DOFW [5] on centralized online convex optimization with delays bounded by $d$. Our algorithms are in bold. Algorithm | Centralized | Distributed | Adversarial Delay | Projection-free | Regret
---|---|---|---|---|---
DGD | Yes | - | Yes | - | $\mathcal{O}(\sqrt{dT})$
DOFW | Yes | - | Yes | Yes | $\mathcal{O}(T^{3/4}+dT^{1/4})$
DeLMFW | Yes | - | Yes | Yes | $\mathcal{O}(\sqrt{dT})$
De2MFW | - | Yes | Yes | Yes | $\mathcal{O}(\sqrt{dT})$

###  1.2 Related Work

#### Online Optimization with delayed feedback

Over the years, studies on online optimization with delayed feedback have
undergone a swift evolution. [7] shed light on the field by focusing on the
convergence properties of online stochastic gradient descent with delays. They
provide a regret bound of $\mathcal{O}(\sqrt{dT})$ with $d$ the delay value if
$d^{2}\leq T$. Later on, [4] proposes a centralized (single-agent) gradient
descent algorithm under adversarial delays. The theoretical analysis of [4]
entails a regret bound of $\mathcal{O}(\sqrt{B})$, where $B$ is the total
delay. This bound becomes $\mathcal{O}(\sqrt{dT})$ if $d$ is the upper bound
of delays. [8] provided a black-box style method to learn under delayed
feedback. They showed that for any non-delayed online algorithms, the
additional regret in the presence of delayed feedback depends on its
prediction drifts. [9] developed an online saddle point algorithm for convex
optimization with feedback delays. They achieved a sublinear regret
$\mathcal{O}(\sqrt{dT})$ where $d$ is a fixed constant delay value. Recently,
[5] proposed a first Frank-Wolfe-type online algorithm with delayed feedback.
They modified the Online Frank-Wolfe (OFW) for the unknown delays setting and
provided a regret bound of $\mathcal{O}(T^{3/4}+dT^{1/4})$. This is the
current state of the art for projection-free (Frank-Wolfe-type) algorithms
with delays. Our bound of $O(\sqrt{dT})$ improves over the aforementioned
results.

#### Distributed Online Optimization.

[10] introduced decentralized online projected subgradient descent and showed
vanishing regret for convex and strongly convex functions. In contrast,[11]
extended distributed dual averaging technique to the online setting, using a
general regularized projection for both unconstrained and constrained
optimization. A distributed variant of online conditional gradient [1] was
designed and analyzed in [12] that requires linear minimizers and uses exact
gradients. Computing exact gradients may be prohibitively expensive for
moderately sized data and intractable when a closed form does not exist. [3]
proposes a decentralized online algorithm for convex function using stochastic
gradient estimate and multiple optimization oracles. This work achieves the
optimal regret bound of $O(T^{1/2})$ and requires multiple gradient evaluation
and communication rounds. Later on, [13] provide a decentralized algorithm
that uses stochastic gradient estimate and reduces communication by using only
one gradient evaluation. [survey-distributed] provides a comprehensible survey
on recent developpement of distributed OCO. More recent work on distributed
online optimization with feedback delays is proposed in [6]. The authors
consider a distributed projected gradient descent algorithm where each agent
has a fixed known amount of delay $d_{i}$. They provide a regret bound of
$\mathcal{O}(\sqrt{dT})$ where $d=\max_{i}d_{i}$ but the delays $d_{i}$ must
be fixed (non-adversarial).

Despite the growing number of studies on decentralized online learning in
recent years, there is a lack of research that accounts for the
_adversarial/online_ delayed feedback. In this paper, we first present a
centralized online algorithm and then extend it to a distributed online
variant that takes an adversarial delay setting into consideration.

##  2 Projection-Free Algorithms under Delayed Feedback

In this section, we will present our method for addressing delayed feedback in
the OCO problem. In Section 2.1, we state some assumptions and results that
form the basis of our approach. We then describe our first algorithm DeLMFW
for centralized setting in Section 2.2 and extend it to distributed setting in
Section 2.3.

###  2.1 Preliminaries

Throughout the paper, we use boldface letter e.g $\bm{x}$ to represent
vectors. We denote by $\bm{x}_{t}$ the final decision of round $t$ and
$\bm{x}_{t,k}$ to be the sub-iterate at round $k$ of $t$. In distributed
setting, we add a superscript $i$ to make distinction between agents. If not
specified otherwise, we use Euclidean norm $\left\lVert.\right\rVert$ and
suppose that the constraint set $\mathcal{K}\subset\mathbb{R}^{m}$ is convex.
We state the following standard assumptions in OCO.

######  Assumption 1.

The constraint set $\mathcal{K}$ is a bounded convex set with diameter $D$ i.e
$D:=\sup_{\bm{x},\bm{y}\in\mathcal{K}}\left\lVert\bm{x}-\bm{y}\right\rVert$

######  Assumption 2 (Lipschitz).

For all $\bm{x}\in\mathcal{K}$, there exists a constant $G$ such that,
$\forall t\in[T]$, $\left\lVert\nabla f_{t}(\bm{x})\right\rVert\leq G$

######  Assumption 3 (Smoothness).

For all $\bm{x},\bm{y}\in\mathcal{K}$, there exists a constant $\beta$ such
that, $\forall t\in[T]$ :

$\displaystyle f_{t}(\bm{y})\leq f_{t}(\bm{x})+\left\langle\nabla
f_{t}(\bm{x}),\bm{y}-\bm{x}\right\rangle+\frac{\beta}{2}\left\lVert\bm{y}-\bm{x}\right\rVert^{2}$

or equivalently $\left\lVert\nabla f_{t}(\bm{x})-\nabla
f_{t}(\bm{y})\right\rVert\leq\beta\left\lVert\bm{x}-\bm{y}\right\rVert$.

#### Online Linear Optimization Oracles

In the context of the Frank-Wolfe (FW) algorithm, we utilize multiple
optimization oracles to approximate the gradient of the upcoming loss function
by solving an online linear problem. This approach was first introduced in
[2]. Specifically, the online linear problem involves selecting a decision
$\bm{v}_{t}\in\mathcal{K}$ at every time $t\in[T]$. The adversary then reveals
a vector $\bm{g}_{t}$ and loss function
$\left\langle\bm{g}_{t},\cdot\right\rangle$ to the oracle. The objective is to
minimize the oracle’s regret. A possible candidate for an online linear oracle
is the Follow the Perturbed Leader algorithm (FTPL) [14]. Given a sequence of
historical loss functions
$\left\langle\bm{g}_{\ell},\cdot\right\rangle,s\in[1,t]$ and a random vector
$\bm{n}$ drawn uniformly from a probability distribution $\mathcal{D}$, FTPL
makes the following update.

$\displaystyle\hat{\bm{v}}_{t+1}=\operatorname*{arg\,min}_{\bm{v}\in\mathcal{K}}\left\\{\zeta\sum_{\ell=1}^{t}\left\langle\bm{g}_{\ell},\bm{v}\right\rangle+\left\langle\bm{n},\bm{v}\right\rangle\right\\}$
(1)

######  Lemma 1 (Theorem 5.8 [1]).

Given a sequence of linear loss function $f_{1},\ldots,f_{T}$. Suppose that
Assumptions 1, 2 and 3 hold true. Let $\mathcal{D}$ be a the uniform
distribution over hypercube $\left[0,1\right]^{m}$. The regret of FTPL is

$\displaystyle\mathcal{R}_{T,\mathcal{O}}\leq\zeta
DG^{2}T+\frac{1}{\zeta}\sqrt{m}D$

where $\zeta$ is learning rate of algorithm.

#### Delay Mechanism

We consider the following delay mechanism. At round $t$, the agent receives a
set of delayed gradient $\nabla f_{s}(\bm{x}_{s})$ from previous rounds $s\leq
t$ such that $s+d_{s}-1=t$, where $d_{s}$ is the delay value of iteration $s$.
We denote by $\mathcal{F}_{t}=\left\\{s:s+d_{s}-1=t\right\\}$ the set of
indices released at round $t$. Following this setting, the feedback of round
$t$ is released at time $t+d_{t}-1$, and the case $d_{t}=1$ is considered as
no delay. We suppose that the delay value is unknown to the agent and make no
assumption about the set $\mathcal{F}_{t}$. Consequently it is possible for
the set to be empty at any particular round. We extend the aforementioned
mechanism to the distributed setting by assuming that each agent has a unique
delay value at each round $t\in[T]$. The delay value of agent $i$ at round $t$
is denoted by $d^{i}_{t}$, and the set of delayed feedbacks of agent $i$ at
round $t$ is denoted by
$\mathcal{F}^{i}_{t}=\left\\{s:s+d^{i}_{s}-1=t\right\\}$, which is distinct
between agents.

###  2.2 Centralized Algorithm

We describe the procedure of LABEL:algo:delmfw in details. At each round $t$,
the agent performs two blocks of operations: prediction and update. During the
prediction block, the agent performs $K$ iterations of FW updates by querying
solutions from the oracles $\mathcal{O}_{k}$, $k\in[K]$ and updates the sub-
iterate vector $\bm{x}_{t,k+1}$ using a convex combination of the previous one
and the oracle’s output. The agent then plays the final decision
$\bm{x}_{t}=\bm{x}_{t,K+1}$ and incurs a loss $f_{t}(\bm{x}_{t})$ which may
not be revealed at $t$ due to delay. From the mechanism described in Section
2.1, there exists a set of gradient feedbacks from the previous rounds
revealed at $t$ whose indices are in $\mathcal{F}_{t}$. The update block
involves observing the delayed gradients evaluated at $K$ sub-iterates of
rounds $s\in\mathcal{F}_{t}$, computing surrogate gradients
$\left\\{\bm{g}_{t,k},k\in[K]\right\\}$ by summing the delayed gradients and
feeding them back to the oracles $\left\\{\mathcal{O}_{k},k\in K\right\\}$.

In our algorithm, the agent employs a suite of online linear optimization
oracles, denoted $\mathcal{O}_{1},\ldots,\mathcal{O}_{K}$. These oracles
utilize feedbacks accumulated from previous rounds to estimate the gradient of
the upcoming loss function. However, in the delay setting, these estimations
may be perturbed owing to a lack of information. For example, if there is no
feedback from rounds $t$ to $t^{\prime}$, that is, $\mathcal{F}_{s}=\emptyset$
for $s\in[t,t^{\prime}]$, the oracles will resort to the information available
in round $t-1$ to estimate the gradient of all rounds from $t+1$ to
$t^{\prime}+1$. As a result, the oracle’s output remains unchanged for these
rounds, and decisions $\left\\{\bm{x}_{s}:s\in[t+1,t^{\prime}+1]\right\\}$ are
not improved. Our analysis for LABEL:algo:delmfw and 2 will be focused on
assessing the impact of delayed feedback on the oracle’s output.

######  Lemma 2.

Let $\hat{\bm{v}}_{t}$ be the FTPL prediction defined in Equation 1 and

$\displaystyle\bm{v}_{t}=\operatorname*{arg\,min}_{\bm{v}\in\mathcal{K}}\left\\{\zeta\sum_{\ell=1}^{t-1}\left\langle\sum_{s\in\mathcal{F}_{\ell}}\bm{g}_{s},\bm{v}\right\rangle+\left\langle\bm{n},\bm{v}\right\rangle\right\\}$

the prediction of FTPL with delayed feedback. For all $t\in[T]$, we have:

$\displaystyle\left\lVert\bm{v}_{t}-\hat{\bm{v}}_{t}\right\rVert\leq\zeta
DG\sum_{s<t}\mathbb{I}_{\left\\{s+d_{s}>t\right\\}}$

Input: Constraint set $\mathcal{K}$, number of iterations $T$, sub-iteration
$K$, online oracles $\left\\{\mathcal{O}_{k}\right\\}_{k=1}^{K}$, step sizes
$\eta_{k}\in(0,1]$

1: for $t=1$ to $T$ do

2: Initialize arbitrarily $\bm{x}_{t,1}\in\mathcal{K}$

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

4: Query $\bm{v}_{t,k}$ from oracle $\mathcal{O}_{k}$.

5: $\bm{x}_{t,k+1}\leftarrow(1-\eta_{k})\bm{x}_{t,k}+\eta_{k}\bm{v}_{t,k}$.

6: end for

7: $\bm{x}_{t}\leftarrow\bm{x}_{t,K+1}$, play $\bm{x}_{t}$ and incurs loss
$f_{t}(\bm{x}_{t})$

8: Receive $\mathcal{F}_{t}=\left\\{s\in[T]:s+d_{s}-1=t\right\\}$

9: if $\mathcal{F}_{t}=\emptyset$ then

10: do nothing

11: else

12: for $k=1$ to $K$ do

13: $\bm{g}_{t,k}\leftarrow\sum_{s\in\mathcal{F}_{t}}\nabla
f_{s}(\bm{x}_{s,k})$

14: Feedback $\langle\bm{g}_{t,k},\cdot\rangle$ to oracles $\mathcal{O}_{k}$.

15: end for

16: end if

17: end for

Algorithm 1 DeLMFW

algorithm]algo:delmfw

######  Theorem 1.

Given a constraint set $\mathcal{K}$. Let $A=\max\left\\{3,\frac{G}{\beta
D}\right\\}$, $\eta_{k}=\min\left\\{1,\frac{A}{k}\right\\}$, and $K=\sqrt{T}$.
Suppose that Assumptions 1, 2 and 3 hold true. If we choose FTPL as the
underlying oracle and set $\zeta=\frac{1}{G\sqrt{B}}$, the regret of
LABEL:algo:delmfw is

$\displaystyle\sum_{t=1}^{T}$
$\displaystyle\left[f_{t}(\bm{x}_{t})-f_{t}(\bm{x}^{*})\right]\leq 2\beta
AD^{2}\sqrt{T}+3(A+1)\left(DG\sqrt{B}+\mathcal{R}_{T,\mathcal{O}}\right)$ (2)

where $B=\sum_{t=1}^{T}d_{t}$, the sum of all delay values and
$\mathcal{R}_{T,\mathcal{O}}$ is the regret of FTPL with respect to the
current choice of $\zeta$.

#### Discussion

The regret bound of Theorem 1 differs from that of the non-delayed MFW [2] by
the additive term $DG\sqrt{B}$ which represents the total cost of sending
delayed feedback to the oracles over $T$ rounds (Lemma 2). If we assume that
there exists a maximum value $d$ such that $d_{t}\leq d$ for all $t\in[T]$.
Our regret bound becomes $\mathcal{O}(\sqrt{dT})$ which coincides with the
setting in [5], a delayed-feedback FW algorithm that achieves
$\mathcal{O}(T^{3/4}+dT^{1/4})$. Another line of work is from [8], a framework
that addresses delayed feedback for any base algorithm. By considering MFW as
the base algorithm, their theoretical analysis suggests that the algorithm
also achieves $\mathcal{O}(\sqrt{dT})$ regret bound. However, their delay
value is not completely unknown to the agent because it is time-stamped by
maintaining multiple copies of the base algorithm. We empirically show in
Section 3 that this algorithm is highly susceptible to high delay values.
Instead of using FTPL, our algorithm has the flexibility to select any online
algorithm as an oracle, for example, Online Gradient Descent [1].

###  2.3 Distributed Algorithm

In this section, we extend LABEL:algo:delmfw to a distributed setting in which
multiple agents collaboratively optimize a global model. Our setting considers
a fully distributed framework, characterized by the absence of a server to
coordinate the learning process. Let $\mathbf{W}\in\mathbb{R}_{+}^{n\times n}$
be the adjacency matrix of communication graph $\mathcal{G}=(V,E)$. The
entries $w_{ij}$ are defined as

$\displaystyle
w_{ij}=\begin{cases}\dfrac{1}{1+\max\\{\tau_{i},\tau_{j}\\}}&\text{if
$(i,j)\in E$}\\\ 0&\text{if $(i,j)\not\in E$,$i\neq j$}\\\ 1-\sum_{j\in
N(i)}w_{ij}&\text{if $i=j$}\end{cases}$

where $\tau_{i}=\\#\\{j\in V:(i,j)\in E\\}$ is the degree of vertex $i$. The
matrix $\mathbf{W}$ is doubly stochastic (i.e
$\mathbf{W}\bm{1}=\mathbf{W}^{T}\bm{1}=\bm{1}$) and therefore possesses
several useful properties associated with doubly stochastic matrices. We call
$\lambda(\mathbf{W})$ the second-largest eigenvalue of $\mathbf{W}$ and define
$k_{0}$ as the smallest integer that verifies
$\lambda(\mathbf{W})\leq\left(\frac{k_{0}}{k_{0}+1}\right)^{2}$. Furthermore,
we set $\rho=1-\lambda(\mathbf{W})$ to be the spectral gap of matrix
$\mathbf{W}$.

At a high level, each agent maintains $K$ copies of the oracles
$\mathcal{O}^{i}_{1},\cdots,\mathcal{O}^{i}_{K}$ while performing prediction
and update at every round $t$. The prediction block consists of performing $K$
FW-steps while incorporating the neighbors’ information. Specifically, the
agent computes at its local level during the $K$ steps a local average
decision $\bm{y}^{i}_{t,k}$ representing a weighted aggregation of its
neighbor’s current sub-iterates. The update vector is convex combination of
the local average decision and the oracle’s output. The final decision of
agent $\bm{x}^{i}_{t}$ is disclosed at the end of $K$ steps. Lemma 3 shows
that $\bm{y}^{i}_{t,k}$ is a local estimation of the global average
$\overline{\bm{x}}_{t,k}=\frac{1}{n}\sum_{i=1}^{n}\bm{x}^{i}_{t,k}$ as $K$
increases.

Following the $K$ FW-steps, the update block employs $K$ gradient updates
utilizing the delayed feedback from previous rounds. The agent observes the
delayed gradients evaluated on theirs corresponding subiterates and computes
the local average gradient $\bm{d}^{i}_{t,k}$ through a weighted aggregation
of the neighbors’ current surrogates (18). The agent updates the surrogate
gradient via a gradient-tracking step (19) to ensure that it approaches the
global gradient as $K$ increases. It is worth noting that feedback provided to
the oracle contains information about delays experienced by all neighboring
agents. Consequently, the oracle $\mathcal{O}^{i}_{k}$ observes delayed
feedback from $\cup_{j\in\mathcal{N}(i)}\mathcal{F}^{j}_{t}$ instead of
$\mathcal{F}^{i}_{t}$. This result highlights the dependency on the
connectivity of the communication graph when considering the effect of delayed
feedback to the oracle’s output, as demonstrated in Lemma 4.

######  Lemma 3.

Define $C_{d}=k_{0}\sqrt{n}D$, for all $t\in[T]$, $k\in[K]$, we have

$\displaystyle\max_{i\in[1,n]}\left\lVert\bm{y}^{i}_{t,k}-\overline{\bm{x}}_{t,k}\right\rVert\leq\frac{C_{d}}{k}$
(3)

######  Lemma 4.

For all $t\in[T]$, $k\in[K]$ and $i\in[n]$. Let $\bm{v}^{i}_{t,k}$ be the
output of the oracle $\mathcal{O}^{i}_{k}$ with delayed feedback and
$\hat{\bm{v}}^{i}_{t,k}$ its homologous in non-delay case. Suppose that
Assumptions 1 and 2 hold true. Choosing FTPL as the oracle, we have:

$\displaystyle\left\lVert\bm{v}^{i}_{t,k}-\hat{\bm{v}}^{i}_{t,k}\right\rVert\leq
2\zeta\sqrt{n}DG\left(\frac{\lambda\left(\mathbf{W}\right)}{\rho}+1\right)\frac{1}{n}\sum_{i=1}^{n}\sum_{s\leq
t}\mathbb{I}_{\left\\{s+d^{i}_{s}>t\right\\}}$ (4)

where $\zeta$ is the learning rate, $\lambda(\mathbf{W})$ is the second-
largest eigenvalue of $\mathbf{W}$ and $\rho=1-\lambda(\mathbf{W})$ is the
spectral gap of matrix $\mathbf{W}$.

######  Theorem 2.

Given a constraint set $\mathcal{K}$. Let $A=\max\left\\{3,\frac{3G}{2\beta
D},\frac{2\beta C_{d}+C_{g}}{\beta D}\right\\}$,
$\eta_{k}=\min\left\\{1,\frac{A}{k}\right\\}$, and $K=\sqrt{T}$. Suppose that
Assumptions 1, 2 and 3 hold true. If we choose FTPL as the underlying oracle
and set $\zeta=\frac{1}{G\sqrt{B}}$, the regret of Algorithm 2 is

$\displaystyle\sum_{t=1}^{T}\left[F_{t}(\bm{x}^{i}_{t})-F_{t}(\bm{x}^{*})\right]\leq\left(GC_{d}+2\beta
AD^{2}\right)\sqrt{T}+3(A+1)\left(2\sqrt{n}DG\left(\frac{\lambda\left(\mathbf{W}\right)}{\rho}+1\right)\sqrt{B}+\mathcal{R}_{T,\mathcal{O}}\right)$

where $B=\frac{1}{n}\sum_{i=1}^{n}B_{i}$ such that $B_{i}$ is the sum of all
delay values of agent $i$. $C_{d}=k_{0}\sqrt{n}D$ and
$C_{g}=\sqrt{n}\max\left\\{\lambda_{2}(\mathbf{W})\left(G+\frac{\beta
D}{\rho}\right),k_{0}\beta\left(4C_{d}+AD\right)\right\\}$ and
$\mathcal{R}_{T,\mathcal{O}}$ is the regret of FTPL with respect to the
current choice of $\zeta$.

Input: Constraint set $\mathcal{K}$, number of iterations $T$, sub-iterations
$K$, online linear optimization oracles
$\left\\{\mathcal{O}^{i}_{k}:k\in[K]\right\\}$ for each agent $i\in[n]$, step
sizes $\eta_{k}\in(0,1]$

1: for $t=1$ to $T$ do

2: for every agent $i=1$ to $n$ do

3: Initialize arbitrarily $\bm{x}^{i}_{t,1}\in\mathcal{K}$

4: for $k=1$ to $K$ do

5: Query $\bm{v}^{i}_{t,k}$ from oracle $\mathcal{O}^{i}_{k}$

6: Exchange $\bm{x}^{i}_{t,k}$ with neighbours $\mathcal{N}(i)$

7: $\bm{y}^{i}_{t,k}\leftarrow\sum_{j}w_{ij}\bm{x}^{j}_{t,k}$

8:
$\bm{x}^{t}_{i,k+1}\leftarrow(1-\eta_{k})\bm{y}^{i}_{t,k}+\eta_{k}\bm{v}^{i}_{t,k}$

9: end for

10: $\bm{x}^{t}_{t}\leftarrow\bm{x}^{t}_{t,K+1}$, play $\bm{x}^{i}_{t}$ and
incurs loss $f^{i}_{t}(\bm{x}^{i}_{t})$

11: Receive $\mathcal{F}^{i}_{t}=\left\\{s\in[T]:s+d^{i}_{s}-1=t\right\\}$

12: if $\mathcal{F}^{i}_{t}=\emptyset$ then

13: do nothing

14: else

15: $\bm{g}^{i}_{t,1}\leftarrow\sum_{s\in\mathcal{F}^{i}_{t}}\nabla
f^{i}_{s}(\bm{x}^{i}_{s,1})$

16: for $k=1$ to $K$ do

17: Exchange $\bm{g}^{i}_{t,k}$ with neighbours $\mathcal{N}(i)$

18:
$\bm{d}^{i}_{t,k}\leftarrow\sum_{j\in\mathcal{N}(i)}w_{ij}\bm{g}^{j}_{t,k}$

19: $\bm{g}^{i}_{t,k+1}\leftarrow\sum_{s\in\mathcal{F}^{i}_{t}}\left(\nabla
f^{i}_{s}(\bm{x}^{i}_{s,k+1})-\nabla f^{i}_{s}(\bm{x}^{i}_{s,k})\right)$ \+
$\bm{d}^{i}_{t,k}$

20: Feedback $\langle\bm{d}^{i}_{t,k},\cdot\rangle$ to oracles
$\mathcal{O}_{i,k}$

21: end for

22: end if

23: end for

24: end for

Algorithm 2 De2MFW

##  3 Numerical Experiments

We evaluated the performance of our algorithms on the online multiclass
logistic regression problem using two datasets: MNIST and FashionMNIST. MNIST
is a well-known hand digit dataset containing $60000$ grayscale images of size
$(28\times 28)$, divided into 10 classes, and FashionMNIST includes images of
fashion products with the same configuration. We conducted the experiment
using Julia 1.7 on MacOS 13.3 with 16GB of memory. The code is available at
https://github.com/tuananhngh/DelayMFW.

#### Centralized Setting

Given an iteration $t$, the agent receives a subset $\mathcal{B}_{t}$ of the
form
$\bm{b}_{t}=\left\\{\bm{a}_{t},y_{t}\right\\}\in\mathbb{R}^{m}\times\left\\{1,\dots,C\right\\}$,
consisting of the features vector $\bm{a}_{t}$ and the corresponding label
$y_{t}$. We define the loss function $f_{t}$ as

$\displaystyle
f_{t}(\bm{x})=-\sum_{\bm{b}_{t}\in\mathcal{B}_{t}}\sum_{c=1}^{C}\left\\{y^{i}_{t}=c\right\\}\log\frac{\exp{\left\langle\bm{x}_{c},\bm{a}^{i}_{t}\right\rangle}}{\sum_{\ell=1}^{C}\exp{\left\langle\bm{x}_{\ell},\bm{a}^{i}_{t}\right\rangle}}$
(5)

where $\bm{x}$ must satisfy the constraint $\bm{x}\in\mathcal{K}$ such that
$\mathcal{K}=\left\\{\bm{x}\in\mathbb{R}^{m\times
C},\left\lVert\bm{x}\right\rVert_{1}\leq r\right\\}$. Using the MNIST dataset,
we note $m=784$, $C=10$, $r=8$, $|\mathcal{B}_{t}|=60$ and a total of $T=1000$
rounds. To evaluate the performance of the algorithm under different delay
regimes, we generated a random sequence of delays $d_{t}$ such that $d_{t}\leq
d$ for $d\in\left\\{21,41,61,81,101\right\\}$. We compared the performance of
DeLMFW against DOFW [5], a projection-free algorithm with adversarial delay,
and BOLD-MFW [8], an online learning framework designed to handle delayed
feedback.

Figure 2: Cumulative Loss Comparison for Different Delays Regimes. Left :
Without delay. Middle : Maximal delay 21. Right : Maximal delay 101

Figure 2 displays the performance of the three algorithms under various delay
regimes. In the absence of delay, that is, $d=1$ (left figure), DeLMFW and
BOLD-MFW have the same performance since both algorithms reduce to MFW [2]
with a regret of $\mathcal{O}(\sqrt{T})$. Meanwhile, DOFW is the classical OFW
[15] that guarantees a regret of $\mathcal{O}(T^{3/4})$. The analysis in
Theorem 1 suggests that DeLMFW achieves a regret of $\mathcal{O}(\sqrt{dT})$
when the delay is upper-bounded by $d$. In the case where $d\leq T^{1/2}$
(middle figure, $d=21$), the dominant term in DOFW is $T^{3/4}$ whereas DeLMFW
takes advantage by incurring a regret of order $\sqrt{dT}\leq T^{3/4}$. For
$d\geq T^{1/2}$ (right figure, $d=101$), DOFW’s regret is dominated by the
term $dT^{1/4}$, which is outperformed by DeLMFW, particularly for high values
of $d$. This result confirms our theoretical analysis in Section 2.2.

Figure 3: Total loss of BOLD-MFW, DOFW and DeLMFW when varying delay value.

Figure 3 illustrates the total loss of DeLMFW and the other two algorithms
when increasing $d$ to show the sensitivity of each algorithm in the presence
of delays. As BOLD is a general framework that can be applied to any base
algorithm, it is noticeable that it is susceptible to high levels of delays.
This phenomenon has also been observed in [5] when utilizing BOLD with OFW,
highlighting the need for a customized design algorithms in the context of
delayed feedback.

#### Distributed Setting

In the second experiment, we examined the distributed online multiclass
logistic regression problem on the FashionMNIST dataset, using a network of 30
agents. The algorithm was run on four different topologies, including Erdos-
Renyi, Complete, Grid, and Cycle. At each iteration $t\in[T]$, each agent $i$
received a subset $\mathcal{B}^{i}_{t}$ of the form
$\left\\{\bm{a}^{i}_{t},y^{i}_{t}\right\\}\in\mathbb{R}^{d}\times\left\\{1,\dots,C\right\\}$,
which consisted of the feature vector $\bm{a}^{i}_{t}$ and its corresponding
label $y^{i}_{t}$. The goal was to collaboratively optimize the global loss
function $F_{t}(\bm{x})=\frac{1}{n}\sum_{i=1}^{n}f^{i}_{t}(\bm{x})$, where the
local loss $f^{i}_{t}$ was defined in Equation 5.

For this experiment, we set $m=784$, $C=10$, $r=32$, $|\mathcal{B}^{i}_{t}|=2$
and $T=1000$ rounds. We are interested in examining the effect of delays on
network performance, and thus randomly select $f<n$ agents to have delayed
feedback with a maximum value of 501. We compared the total loss on each
topology under these conditions, and present the result in Figure 4. We
observe that the presence of delayed agents has a significant impact on the
network performance of Cycle graph as the number of delayed agents increases,
while the Complete graph is less affected. This result is consistent with the
analysis in Section 2.3 because the delay term in the regret bound depends on
the connectivity of the communication graph.

Figure 4: Total Loss with varying numbers of agents experiencing delayed
feedback in the network. $(f=0)$ for no delayed-agents.

In Table 2, we report the change in total loss when increasing the number of
delayed agents. We observe that the average percentage change is smaller for
Grid than for Erdos-Renyi when compared with the network of non-delayed agents
($f=0$). This result indicate that the generated Erdos-Renyi graph is more
sensitive to the presence of delayed agents.

Table 2: Total Loss of the algorithm running on 4 different topology. We randomly select $f<n$ agents to have delay with maximal value to be 501. In parenthesis, the percentage of total loss compared that of no delayed agents in the network (i.e $f=0$). f Topology | Erdős-Rényi | Grid | Complete | Cycle
---|---|---|---|---
0 | 809.37 | 855.62 | 799.49 | 925.72
2 | 820.15 (+1.3%) | 852.15 (-0.4%) | 798.79 (-0.08%) | 932.34 (+0.7%)
5 | 834.74 (+3.0%) | 868.52 (+1.4%) | 802.59 (+0.3%) | 971.24 (+4.7%)
10 | 838.74 (+3.5%) | 878.04 (+2.5%) | 792.45 (-0.8%) | 983.89 (+6.0%)
20 | 850.49 (+4.9%) | 902.30 (+5.3%) | 812.21 (+1.5%) | 1119.24 (+18.9%)

##  4 Concluding Remarks

In this paper, we propose two algorithms for solving the online convex
optimization problem with adversarial delayed feedback in both centralized and
decentralized settings. These algorithms achieve optimal
$\mathcal{O}(\sqrt{dT})$ regret bounds, where $d$ is the upper bound of the
delays. The experimental results show that our algorithms outperform existing
solutions in both centralized and decentralized settings, which are
predictable by our theoretical analysis. Although the algorithms achieve good
performance guarantees for the online convex optimization problem with
adversarial delays, they currently rely on exact gradients, which may not be
feasible for many real-world applications. Therefore, future research could
explore the use of stochastic gradients with variance reduction techniques.
Additionally, in decentralized settings, communication delays can be
practically challenging, and further improvements are needed in this area.
Nevertheless, our work demonstrates the potential of using Frank-Wolfe-type
algorithms for solving constraint convex optimization problems under
adversarial delays, which is beneficial for learning on edge devices.

## References

  * [1] Elad Hazan.  Introduction to online convex optimization.  Foundations and Trends® in Optimization, 2(3-4):157–325, 2016.
  * [2] Lin Chen, Christopher Harshaw, Hamed Hassani, and Amin Karbasi.  Projection-free online optimization with stochastic gradient: From convexity to submodularity.  In Proceedings of the 35th International Conference on Machine Learning, pages 814–823, 2018.
  * [3] Nguyen Kim Thang, Abhinav Srivastav, Denis Trystram, and Paul Youssef.  A stochastic conditional gradient algorithm for decentralized online convex optimization.  Journal of Parallel and Distributed Computing, 169:334–351, 2022\.
  * [4] Kent Quanrud and Daniel Khashabi.  Online learning with adversarial delays.  In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
  * [5] Yuanyu Wan, Wei-Wei Tu, and Lijun Zhang.  Online frank-wolfe with arbitrary delays.  In Advances in Neural Information Processing Systems, volume 35, pages 19703–19715. Curran Associates, Inc., 2022.
  * [6] Xuanyu Cao and Tamer Başar.  Decentralized online convex optimization with feedback delays.  IEEE Transactions on Automatic Control, 67(6):2889–2904, 2022.
  * [7] Martin Zinkevich, John Langford, and Alex Smola.  Slow learners are fast.  In Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009.
  * [8] Pooria Joulani, Andras Gyorgy, and Csaba Szepesvari.  Online learning under delayed feedback.  In Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 1453–1461, Atlanta, Georgia, USA, 17–19 Jun 2013. PMLR.
  * [9] Xuanyu Cao, Junshan Zhang, and H. Vincent Poor.  Constrained online convex optimization with feedback delays.  IEEE Transactions on Automatic Control, 66(11):5049–5064, 2021\.
  * [10] F. Yan, S. Sundaram, S. V. N. Vishwanathan, and Y. Qi.  Distributed autonomous online learning: Regrets and intrinsic privacy-preserving properties.  IEEE Transactions on Knowledge and Data Engineering, 25(11):2483–2493, 2013.
  * [11] S. Hosseini, A. Chapman, and M. Mesbahi.  Online distributed optimization via dual averaging.  In 52nd IEEE Conference on Decision and Control, pages 1484–1489, 2013.
  * [12] W. Zhang, P. Zhao, W. Zhu, S.C.V. Hoi, and T. Zhang.  Projection-free distributed online learning in networks.  In Proceedings of the 34th International Conference on Machine Learning, pages 4054–4062, 2017.
  * [13] Tuan-Anh Nguyen, Nguyen Kim Thang, and Denis Trystram.  One gradient frank-wolfe for decentralized online convex and submodular optimization.  In Proceedings of The 14th Asian Conference on Machine Learning, volume 189 of Proceedings of Machine Learning Research, pages 802–815. PMLR, 12–14 Dec 2023.
  * [14] Adam Kalai and Santosh Vempala.  Efficient algorithms for online decision problems.  Journal of Computer and System Sciences, 71(3):291–307, 2005.  Learning Theory 2003.
  * [15] Elad Hazan and Satyen Kale.  Projection-free online learning.  In Proceedings of the 29th International Conference on Machine Learning, ICML 2012, Proceedings of the 29th International Conference on Machine Learning, ICML 2012, pages 521–528, 2012.  29th International Conference on Machine Learning, ICML 2012 ; Conference date: 26-06-2012 Through 01-07-2012.
  * [16] Anastasia Koloskova, Sebastian Stich, and Martin Jaggi.  Decentralized stochastic optimization and gossip algorithms with compressed communication.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3478–3487. PMLR, 09–15 Jun 2019.

Supplementary Material

Handling Delayed Feedback in Distributed Online Optimization : A Projection-
Free Approach

We start by recalling notations that will be used throughout the proof of
Theorems 1 and LABEL:thmm:decen. All notation, are described in the
centralized setting. For decentralized setting, if not specify otherwise, we
add a superscript $i$ to indicate the dependant of the variable to agent $i$.
Following the notation in the main section, we note
$\mathcal{F}_{t}=\left\\{s\in[T],s+d_{s}-1=t\right\\}$ as the set of feedback
arrives at time $t$ (denoted $\mathcal{F}^{i}_{t}$ in decentralized setting).
The sum of total delay is denoted by $B:=\sum_{t=1}^{T}d_{t}$ and we call $d$
the upper bound on all delay value when it is clear from the context. For
simplicity of notation, we denote by $\nabla f_{t,k}=\nabla
f_{t}(\bm{x}_{t,k})$, $\zeta$ the learning rate of the oracle and
$\pi_{\mathcal{K}}(\bm{x})$ the projection of $\bm{x}$ into the constraint set
$\mathcal{K}$. If $t$ is the time the agent plays the decision $\bm{x}_{t}$,
the feedback is revealed at time $\sigma(t):=t+d_{t}-1$.

##  Appendix A Analysis of Algorithm LABEL:algo:delmfw

###  A.1 Auxiliary Lemmas

######  Lemma 2.

Let $\hat{\bm{v}}_{t}$ be the FTPL prediction defined in Equation 1 and

$\displaystyle\bm{v}_{t}=\operatorname*{arg\,min}_{\bm{v}\in\mathcal{K}}\left\\{\zeta\sum_{\ell=1}^{t-1}\left\langle\sum_{s\in\mathcal{F}_{\ell}}\bm{g}_{s},\bm{v}\right\rangle+\left\langle\bm{n},\bm{v}\right\rangle\right\\}$

the prediction of FTPL with delayed feedback. For all $t\in[T]$, we have:

$\displaystyle\left\lVert\bm{v}_{t}-\hat{\bm{v}}_{t}\right\rVert\leq\zeta
DG\sum_{s<t}\mathbb{I}_{\left\\{s+d_{s}>t\right\\}}$

###### Proof.

Recall that $f_{t}$ is a linear function defined as
$f_{t}=\left\langle\bm{g}_{t},\cdot\right\rangle$. For the ease of analysis,
we call $\hat{\bm{u}}_{t}=\zeta\sum_{\ell=1}^{t-1}\bm{g}_{\ell}$ and
$\bm{u}_{t}=\zeta\sum_{\ell=1}^{t-1}\sum_{s\in\mathcal{F}_{\ell}}\bm{g}_{s}$.
We define
$h_{t}(\bm{n})=\operatorname*{arg\,min}_{\bm{v}\in\mathcal{K}}\left\\{\left\langle\bm{n},\bm{v}\right\rangle\right\\}$.
By definition of $\hat{\bm{v}}_{t}$ and $\bm{v}_{t}$, we have

$\displaystyle\hat{\bm{v}}_{t}=\mathbb{E}\left[h_{t}(\bm{n}+\hat{\bm{u}}_{t})\right]=\int_{\bm{n}}h_{t}(\bm{n}+\hat{\bm{u}}_{t})p(\bm{n})\mathrm{d}\bm{n}=\int_{\bm{n}}h_{t}(\bm{n})p(\bm{n}-\hat{\bm{u}}_{t})\mathrm{d}\bm{n}$
(6)

and

$\displaystyle\bm{v}_{t}=\mathbb{E}\left[h_{t}(\bm{n}+\bm{u})\right]=\int_{\bm{n}}h_{t}(\bm{n})p(\bm{n}-\bm{u})\mathrm{d}\bm{n}$
(7)

From linearity of expectation and Cauchy-Schwarz inequality,

$\displaystyle\left\lVert\bm{v}_{t}-\hat{\bm{v}}_{t}\right\rVert$
$\displaystyle\leq\int_{\bm{n}}\left\lVert h_{t}(\bm{n})\right\rVert\lvert
p(\bm{n}-\bm{u})-p(\bm{n}-\hat{\bm{u}}_{t})\rvert\mathrm{d}\bm{n}$
$\displaystyle=\int_{\bm{n}}\left\lVert
h_{t}(\bm{n})-h_{t}(\bm{0})\right\rVert\lvert
p(\bm{n}-\bm{u})-p(\bm{n}-\hat{\bm{u}}_{t})\rvert\mathrm{d}\bm{n}$
$\displaystyle\leq D\int_{\bm{n}}\lvert
p(\bm{n}-\bm{u})-p(\bm{n}-\hat{\bm{u}}_{t})\rvert\mathrm{d}\bm{n}$
$\displaystyle\leq DL\left\lVert\bm{u}-\hat{\bm{u}}_{t}\right\rVert$
$\displaystyle\leq\zeta DLG\sum_{s<t}\mathbb{I}_{\left\\{s+d_{s}>t\right\\}}$
(8)

The first inequality follows from the fact that $h_{t}(\bm{n})$ and
$h_{t}(\bm{0})$ are in $\mathcal{K}$. The second inequality is due to the
stability of the distribution of $\bm{n}$, where $L$ is the Lipschitz constant
of the probability distribution function $p$. Since each function is
$G$-Lipschitz, the distance between $\bm{u}$ and $\hat{\bm{u}}_{t}$ is bounded
by $G$ multiplied by the number of functions whose feedback is not received at
time $t$, which leads to the last inequality. ∎

######  Lemma 5 ([3]).

For every $t\in[T]$ and $k\in[K]$. Define
$h_{t,k}=f_{t}(\bm{x}_{t,k+1})-f_{t}(\bm{x}^{*})$ let $A=\max(3,\frac{G}{\beta
D})$ and $\eta_{k}=\min(1,\frac{A}{k})$, it holds that

$\displaystyle h_{t,k}=f_{t}(\bm{x}_{t,k+1})-f_{t}(\bm{x}^{*})\leq\frac{2\beta
AD^{2}}{k}+\sum_{k^{\prime}=1}^{k}\eta_{k^{\prime}}\left(\prod_{\ell=k^{\prime}+1}^{k}(1-\eta_{\ell})\right)\left\langle\nabla
f_{t,k^{\prime}},\bm{v}_{t,k^{\prime}}-\bm{x}^{*}\right\rangle$ (9)

###### Proof.

We state the proof of [3] for clarity. The proof is based on an induction on
$k$. For $k=1$, $\eta_{1}=1$, we have
$h_{t,1}=f_{t}(\bm{x}_{t,2})-f_{t}(\bm{x}^{*})\leq GD$ since $f_{t}$ is
$G$-Lipschitz and the constraint set $\mathcal{K}$ is bounded by $D$
(Assumptions 1 and 2). More over, we have $2\beta AD^{2}+\left\langle\nabla
f_{t,1},\bm{x}_{t,1}-\bm{x}^{*}\right\rangle\geq 2\beta
AD^{2}-\left\langle\nabla f_{t,1},\bm{x}_{t,1}-\bm{x}^{*}\right\rangle\geq
2\beta AD^{2}-GD\geq GD$ by assuming $A\geq\frac{G}{\beta D}$. We have then
$h_{t,1}\leq 2\beta AD^{2}+\left\langle\nabla
f_{t,1},\bm{x}_{t,1}-\bm{x}^{*}\right\rangle$ Assume that the inequality holds
for $k-1$, we now prove for $k$. By definition of $h_{t,k}$, we have

$\displaystyle h_{t,k}\leq(1-\eta_{k})h_{t,k-1}+\eta_{k}\left\langle\nabla
f_{t,k},\bm{v}_{t,k}-\bm{x}^{*}\right\rangle+\eta_{k}^{2}\frac{\beta
D^{2}}{2}$ $\displaystyle\leq\left(1-\eta_{k}\right)\left[\frac{2\beta
AD^{2}}{k-1}+\sum_{k^{\prime}=1}^{k-1}\eta_{k^{\prime}}\left(\prod_{\ell=k^{\prime}+1}^{k-1}(1-\eta_{\ell})\right)\left\langle\nabla
f_{t,k^{\prime}},\bm{v}_{t,k^{\prime}}-\bm{x}^{*}\right\rangle\right]$
$\displaystyle\quad+\eta_{k}\left\langle\nabla
f_{t,k},\bm{v}_{t,k}-\bm{x}^{*}\right\rangle+\eta_{k}^{2}\frac{\beta
D^{2}}{2}$ $\displaystyle\leq\left(1-\eta_{k}\right)\left[\frac{2\beta
AD^{2}}{k-1}+\sum_{k^{\prime}=1}^{k-1}\eta_{k^{\prime}}\left[\prod_{\ell=k^{\prime}+1}^{k-1}(1-\eta_{\ell})\right]\left\langle\nabla
f_{t,k^{\prime}},\bm{v}_{t,k^{\prime}}-\bm{x}^{*}\right\rangle\right]$
$\displaystyle\quad+\eta_{k}\prod_{\ell=k+1}^{k}\left(1-\eta_{\ell}\right)\left\langle\nabla
f_{t,k},\bm{v}_{t,k}-\bm{x}^{*}\right\rangle+\eta_{k}^{2}\frac{\beta
D^{2}}{2}$ $\displaystyle\leq\left(1-\eta_{k}\right)\frac{2\beta
AD^{2}}{k-1}+\sum_{k^{\prime}=1}^{k-1}\eta_{k^{\prime}}\left[\prod_{\ell=k^{\prime}+1}^{k}(1-\eta_{\ell})\right]\left\langle\nabla
f_{t,k^{\prime}},\bm{v}_{t,k^{\prime}}-\bm{x}^{*}\right\rangle$
$\displaystyle\quad+\eta_{k}\prod_{\ell=k+1}^{k}\left(1-\eta_{\ell}\right)\left\langle\nabla
f_{t,k},\bm{v}_{t,k}-\bm{x}^{*}\right\rangle+\eta_{k}^{2}\frac{\beta
D^{2}}{2}$ $\displaystyle\leq\left(1-\eta_{k}\right)\frac{2\beta
AD^{2}}{k-1}+\sum_{k^{\prime}=1}^{k}\eta_{k^{\prime}}\left[\prod_{\ell=k^{\prime}+1}^{k}\left(1-\eta_{\ell}\right)\right]\left\langle\nabla
f_{t,k^{\prime}},\bm{v}_{t,k^{\prime}}-\bm{x}^{*}\right\rangle+\eta_{k}^{2}\frac{\beta
D^{2}}{2}$ $\displaystyle\leq\frac{2\beta AD^{2}}{k-1}-\frac{2\beta
A^{2}D^{2}}{k\left(k-1\right)}+\frac{\beta
A^{2}D^{2}}{2k^{2}}+\sum_{k^{\prime}=1}^{k}\eta_{k^{\prime}}\left[\prod_{\ell=k^{\prime}+1}^{k}\left(1-\eta_{\ell}\right)\right]\left\langle\nabla
f_{t,k^{\prime}},\bm{v}_{t,k^{\prime}}-\bm{x}^{*}\right\rangle$
$\displaystyle\leq\frac{2\beta AD^{2}}{k-1}-\frac{2\beta
A^{2}D^{2}}{k(k-1)}+\frac{\beta
A^{2}D^{2}}{2k(k-1)}+\sum_{k^{\prime}=1}^{k}\eta_{k^{\prime}}\left[\prod_{\ell=k^{\prime}+1}^{k}\left(1-\eta_{\ell}\right)\right]\left\langle\nabla
f_{t,k^{\prime}},\bm{v}_{t,k^{\prime}}-\bm{x}^{*}\right\rangle$
$\displaystyle\leq\frac{2\beta AD^{2}}{k-1}-\frac{2\beta
A^{2}D^{2}-\frac{\beta}{2}A^{2}D^{2}}{k(k-1)}+\sum_{k^{\prime}=1}^{k}\eta_{k^{\prime}}\left[\prod_{\ell=k^{\prime}+1}^{k}\left(1-\eta_{\ell}\right)\right]\left\langle\nabla
f_{t,k^{\prime}},\bm{v}_{t,k^{\prime}}-\bm{x}^{*}\right\rangle$
$\displaystyle\leq\frac{2\beta AD^{2}}{k-1}-\frac{\beta
A^{2}D^{2}}{k(k-1)}+\sum_{k^{\prime}=1}^{k}\eta_{k^{\prime}}\left[\prod_{\ell=k^{\prime}+1}^{k}\left(1-\eta_{\ell}\right)\right]\left\langle\nabla
f_{t,k^{\prime}},\bm{v}_{t,k^{\prime}}-\bm{x}^{*}\right\rangle$
$\displaystyle\leq\frac{2\beta
AD^{2}}{k}+\sum_{k^{\prime}=1}^{k}\eta_{k^{\prime}}\left[\prod_{\ell=k^{\prime}+1}^{k}\left(1-\eta_{\ell}\right)\right]\left\langle\nabla
f_{t,k^{\prime}},\bm{v}_{t,k^{\prime}}-\bm{x}^{*}\right\rangle$

where the last inequality follows from the fact that $\beta A^{2}\geq 2\beta
A$ for $A\geq 3$ and $\frac{1}{k-1}-\frac{1}{k(k-1)}\leq\frac{1}{k}$. ∎

###  A.2 Proof of Theorem 1

######  Theorem 1.

Given a constraint set $\mathcal{K}$. Let $A=\max\left\\{3,\frac{G}{\beta
D}\right\\}$, $\eta_{k}=\min\left\\{1,\frac{A}{k}\right\\}$, and $K=\sqrt{T}$.
Suppose that Assumptions 1, 2 and 3 hold true. If we choose FTPL as the
underlying oracle and set $\zeta=\frac{1}{G\sqrt{B}}$, the regret of
LABEL:algo:delmfw is

$\displaystyle\sum_{t=1}^{T}$
$\displaystyle\left[f_{t}(\bm{x}_{t})-f_{t}(\bm{x}^{*})\right]\leq 2\beta
AD^{2}\sqrt{T}+3(A+1)\left(DG\sqrt{B}+\mathcal{R}_{T,\mathcal{O}}\right)$ (10)

where $B=\sum_{t=1}^{T}d_{t}$, the sum of all delay values and
$\mathcal{R}_{T,\mathcal{O}}$ is the regret of FTPL with respect to the
current choice of $\zeta$

###### Proof.

Let $\bm{x}_{t,1},\ldots,\bm{x}_{t,K+1}$ be the sequence of sub-iterate for a
fixed time step $t$. Using Frank-Wolfe updates and smoothness of $f_{t}$, we
have

$\displaystyle f_{t}(\bm{x}_{t,k+1})$ $\displaystyle-
f_{t}(\bm{x}^{*})=f_{t}(\bm{x}_{t,k}+\eta_{k}(\bm{v}_{t,k}-\bm{x}_{t,k}))-f_{t}(\bm{x}^{*})$
$\displaystyle\leq
f_{t}(\bm{x}_{t,k})-f_{t}(\bm{x}^{*})+\eta_{k}\left\langle\nabla
f_{t,k},\bm{v}_{t,k}-\bm{x}_{t,k}\right\rangle+\eta_{k}^{2}\frac{\beta}{2}\left\lVert\bm{v}_{t,k}-\bm{x}_{t,k}\right\rVert^{2}$
$\displaystyle\leq
f_{t}(\bm{x}_{t,k})-f_{t}(\bm{x}^{*})+\eta_{k}\left\langle\nabla
f_{t,k},\bm{v}_{t,k}-\bm{x}_{t,k}\right\rangle+\eta_{k}^{2}\frac{\beta
D^{2}}{2}\quad\text{($\mathcal{K}$ is bounded)}$ $\displaystyle\leq
f_{t}(\bm{x}_{t,k})-f_{t}(\bm{x}^{*})+\eta_{k}\left[\left\langle\nabla
f_{t,k},\bm{v}_{t,k}-\bm{x}^{*}\right\rangle+\left\langle\nabla
f_{t,k},\bm{x}^{*}-\bm{x}_{t,k}\right\rangle\right]+\eta_{k}^{2}\frac{\beta
D^{2}}{2}$ $\displaystyle\leq
f_{t}(\bm{x}_{t,k})-f_{t}(\bm{x}^{*})+\eta_{k}\left[\left\langle\nabla
f_{t,k},\bm{v}_{t,k}-\bm{x}^{*}\right\rangle+f_{t}(\bm{x}^{*})-f_{t}(\bm{x}_{t,k})\right]+\eta_{k}^{2}\frac{\beta
D^{2}}{2}\quad\text{(by convexity of $f_{t}$)}$
$\displaystyle\leq(1-\eta_{k})\left[f_{t}(\bm{x}_{t,k})-f_{t}(\bm{x}^{*})\right]+\eta_{k}\left\langle\nabla
f_{t,k},\bm{v}_{t,k}-\bm{x}^{*}\right\rangle+\eta_{k}^{2}\frac{\beta
D^{2}}{2}$

Let $h_{t,k}=f_{t}(\bm{x}_{t,k+1})-f_{t}(\bm{x}^{*})$, section A.2 becomes

$\displaystyle h_{t,k}\leq(1-\eta_{k})h_{t,k-1}+\eta_{k}\left\langle\nabla
f_{t,k},\bm{v}_{t,k}-\bm{x}^{*}\right\rangle+\eta_{k}^{2}\frac{\beta
D^{2}}{2}$ (12)

A direct application of Lemma 5 for $k=K$ yields

$\displaystyle f_{t}(\bm{x}_{t,K+1})-f_{t}(\bm{x}^{*})\leq\frac{2\beta
AD^{2}}{K}+\sum_{k^{\prime}=1}^{K}\eta_{k^{\prime}}\left[\prod_{\ell=k+1}^{K}(1-\eta_{\ell})\right]\left\langle\nabla
f_{t,k},\bm{v}_{t,k}-\bm{x}^{*}\right\rangle$ (13)

Following the notation from LABEL:algo:delmfw and Lemma 2. For a fixed time
$t$ and any sub-iterate $k$, $\bm{v}_{t,k}$ and $\hat{\bm{v}}_{t,k}$ are
respectively the predictions of the oracle $\mathcal{O}_{k}$ under delayed and
non-delayed feedback, the scalar product of eq. 13 over $T$-round is written
as

$\displaystyle\sum_{t=1}^{T}\left\langle\nabla
f_{t,k},\bm{v}_{t,k}-\bm{x}^{*}\right\rangle$
$\displaystyle=\sum_{t=1}^{T}\left\langle\nabla
f_{t,k},\bm{v}_{t,k}-\hat{\bm{v}}_{t,k}\right\rangle+\sum_{t=1}^{T}\left\langle\nabla
f_{t,k},\hat{\bm{v}}_{t,k}-\bm{x}^{*}\right\rangle$
$\displaystyle\leq\sum_{t=1}^{T}\left\langle\nabla
f_{t,k},\bm{v}_{t,k}-\hat{\bm{v}}_{t,k}\right\rangle+\sum_{t=1}^{T}\left\langle\nabla
f_{t,k},\hat{\bm{v}}_{t,k}-\bm{x}^{*}\right\rangle$ (14)

In the first term on the right hand side of Section A.2, using the Cauchy-
Schwartz inequality and Lemma 2, we have

$\displaystyle\sum_{t=1}^{T}\left\langle\nabla
f_{t,k},\bm{v}_{t,k}-\hat{\bm{v}}_{t,k}\right\rangle\leq\sum_{t=1}^{T}\left\lVert\nabla
f_{t,k}\right\rVert\left\lVert\bm{v}_{t,k}-\hat{\bm{v}}_{t,k}\right\rVert\leq\zeta
DG^{2}\sum_{t=1}^{T}\sum_{s<t}\mathbb{I}_{s+d_{s}>t}\leq\zeta DG^{2}B$ (15)

Recall that the objective function of the oracle $\mathcal{O}_{k}$ in non-
delay setting is $\left\langle\nabla f_{t,k},\cdot\right\rangle$ and
$\hat{\bm{v}}_{t,k}$ is its prediction at time $t$, the second term of Section
A.2 is bounded by the regret of $\mathcal{O}_{k}$ in non-delay setting,
$\mathcal{R}_{T,\mathcal{O}}$. Specifically, we have

$\displaystyle\sum_{t=1}^{T}\left\langle\nabla
f_{t,k},\hat{\bm{v}}_{t,k}\right\rangle\leq\min_{\bm{x}\in\mathcal{K}}\sum_{t=1}^{T}\left\langle\nabla
f_{t,k},\bm{x}\right\rangle+\mathcal{R}_{T,\mathcal{O}}\leq\sum_{t=1}^{T}\left\langle\nabla
f_{t,k},\bm{x}^{*}\right\rangle+\mathcal{R}_{T,\mathcal{O}}$ (16)

Recall that $\bm{x}_{t}=\bm{x}_{t,K+1}$, combining Sections A.2, 15 and 16 and
summing Equation 13 over $T$-rounds yields

$\displaystyle\sum_{t=1}^{T}\left[f_{t}(\bm{x}_{t})-f_{t}(\bm{x}^{*})\right]\leq\frac{2\beta
AD^{2}}{K}T+\sum_{k^{\prime}=1}^{K}\eta_{k^{\prime}}\left[\prod_{\ell=k+1}^{K}(1-\eta_{\ell})\right]\left[\zeta
DG^{2}B+\mathcal{R}_{T,\mathcal{O}}\right]$ (17)

Let $\eta_{k}=\frac{A}{k}$, we have

$\displaystyle\prod_{k^{\prime}=k+1}^{K}(1-\eta_{k^{\prime}})\leq
e^{-\sum_{k^{\prime}=k+1}^{K}\eta_{k^{\prime}}}\leq
e^{-\sum_{k^{\prime}=\ell}^{K}\frac{A}{k^{\prime}}}\leq
e^{-A\int_{k+2}^{K}ds/s}\leq\left(\frac{k+2}{K}\right)^{A}$ (18)

We have then,

$\displaystyle\sum_{k=1}^{K}\eta_{k}\left[\prod_{k^{\prime}=k+1}^{K}(1-\eta_{k^{\prime}})\right]$
$\displaystyle\leq\min\left\\{1,\frac{A}{K}\right\\}+\min\left\\{1,\frac{A}{K-1}\right\\}+\min\left\\{1,\frac{A}{K-2}\right\\}+\sum_{k=1}^{K-3}\frac{A}{k}\left[\frac{k+2}{K}\right]^{A}$
$\displaystyle\leq
3\min\left\\{1,\frac{A}{K-2}\right\\}+\frac{A}{K}\sum_{k=1}^{K-3}\frac{k+2}{k}\left[\frac{k+2}{K}\right]^{A-1}$
$\displaystyle\leq
3+\frac{3A}{K}\sum_{k=1}^{K-3}\left[\frac{k+2}{K}\right]^{A-1}$
$\displaystyle\leq 3(A+1)$ (19)

From Section A.2, we deduce that

$\displaystyle\sum_{t=1}^{T}\left[f_{t}(\bm{x}_{t})-f_{t}(\bm{x}^{*})\right]$
$\displaystyle\leq\frac{2\beta
AD^{2}}{K}T+\sum_{k^{\prime}=1}^{K}\eta_{k^{\prime}}\left(\prod_{\ell=k+1}^{K}(1-\eta_{\ell})\right)\left(\zeta
DG^{2}B+\mathcal{R}_{T,\mathcal{O}}\right)$ $\displaystyle\leq\frac{2\beta
AD^{2}}{K}T+3(A+1)\left(\zeta DG^{2}B+\mathcal{R}_{T,\mathcal{O}}\right)$

The theorem follows by letting $\zeta=\frac{1}{G\sqrt{B}}$, $K=\sqrt{T}$ and
choosing the oracle as FTPL with regret $\mathcal{R}_{T,\mathcal{O}}$. ∎

##  Appendix B Analysis of Algorithm 2

###  B.1 Additional Notations (only for the analysis)

In the analysis, for any vector $\bm{x}^{i}\in\mathbb{R}^{d},\forall i\in[n]$,
we note $\bm{x}^{cat}\in\mathbb{R}^{dn}$ a column vector defined as
$\bm{x}^{cat}:=\left[\bm{x}^{1\top},\ldots,\bm{x}^{n\top}\right]^{\top}$. Let
$\overline{\bm{x}}$ be the average of $\bm{x}^{i}$ over $i\in[n]$, the vector
$\overline{\bm{x}}^{cat}$ is a $dn$-vector where we stack $n$-times
$\overline{\bm{x}}$ i.e
$\overline{\bm{x}}^{cat}:=\left[\overline{\bm{x}}^{\top},\ldots,\overline{\bm{x}}^{\top}\right]$.
For simplicity of notation, we note $\nabla
f^{i}_{t}(\bm{x}^{i}_{t,k}):=\nabla f^{i}_{t,k}$ and $\nabla
F_{t,k}:=\frac{1}{n}\sum_{i=1}^{n}\nabla f^{i}_{t,k}$. In order to incorporate
the delay of agents at each time-step $t$, we define $\nabla f^{cat}_{t,k}$ as
described above using the sum of agent’s delay feedback, we note then

$\displaystyle\quad\nabla
f^{cat}_{t,k}=\left[\sum_{s\in\mathcal{F}^{1}_{t}}\nabla
f^{1\top}_{s,k},\dots,\sum_{s\in\mathcal{F}^{n}_{t}}\nabla
f^{n\top}_{s,k}\right]^{\top}$ (21)

and its homologous in the non-delay setting by
$\nabla\hat{f}^{cat}_{t,k}=\left[\nabla f^{1\top}_{t,k},\dots,\nabla
f^{n\top}_{t,k}\right]^{\top}$

The variables $\bm{d}^{cat}_{t,k},\hat{\bm{d}}^{cat}_{t,k}$ and
$\bm{g}^{cat}_{t,k},\hat{\bm{g}}^{cat}_{t,k}$ are defined similarly as
described. Lastly, we define the slack variable $\bm{\delta}^{i}_{t,k}:=\nabla
f^{i}_{t,k}-\nabla f^{i}_{t,k-1}$, then the definition of
$\overline{\bm{\delta}}_{t,k},\bm{\delta}^{cat}_{t,k}$ and
$\overline{\bm{\delta}}^{cat}_{t,k}$ followed.

###  B.2 Auxiliary lemmas

######  Claim 1.

In the analysis, we make use of the following bounds

$\displaystyle\left\lVert\overline{\bm{x}}_{t,k}-\bm{x}^{i}_{t,k}\right\rVert\leq\frac{2C_{d}}{k}$
$\displaystyle\left\lVert\bm{x}^{i}_{t,k+1}-\bm{x}^{i}_{t,k}\right\rVert\leq\frac{4C_{d}+AD}{k}$

_Proof of claim._ For the first bound, recall the definition of FW-update in
Algorithm 2 and using Lemma 3, we have

$\displaystyle\left\lVert\overline{\bm{x}}_{t,k}-\bm{x}^{i}_{t,k}\right\rVert=\left\lVert\left(1-\eta_{k-1}\right)\left(\overline{\bm{x}}_{t,k-1}-\bm{y}^{i}_{t,k-1}\right)+\eta_{k-1}\left(\overline{\bm{v}}_{t,k-1}-\bm{v}^{i}_{t,k-1}\right)\right\rVert$
$\displaystyle\leq\frac{C_{d}}{k-1}-\frac{AC_{d}}{(k-1)^{2}}+\frac{AD}{k-1}\leq\frac{C_{d}}{k-1}-\left[\frac{AC_{d}}{(k-1)^{2}}-\frac{AD}{k-1}\right]\leq\frac{C_{d}}{k-1}-\left[\frac{AC_{d}-AD}{(k-1)^{2}}\right]\leq\frac{C_{d}}{k-1}\leq\frac{2C_{d}}{k}$

Applying the first bound on the second one yiels

$\displaystyle\left\lVert\bm{x}^{i}_{t,k+1}-\bm{x}^{i}_{t,k}\right\rVert\leq\left\lVert\bm{x}^{i}_{t,k+1}-\overline{\bm{x}}_{t,k+1}\right\rVert+\left\lVert\overline{\bm{x}}_{t,k+1}-\overline{\bm{x}}_{t,k}\right\rVert+\left\lVert\overline{\bm{x}}_{t,k}-\bm{x}^{i}_{t,k}\right\rVert\leq\frac{2C_{d}}{k+1}+\frac{AD}{k}+\frac{2C_{d}}{k}\leq\frac{4C_{d}+AD}{k}$

∎

######  Lemma 3.

Define $C_{d}=k_{0}\sqrt{n}D$, for all $t\in[T]$, $k\in[K]$, we have

$\displaystyle\max_{i\in[1,n]}\left\lVert\bm{y}^{i}_{t,k}-\overline{\bm{x}}_{t,k}\right\rVert\leq\frac{C_{d}}{k}$
(22)

###### Proof.

We prove the lemma by induction, we first note that

$\displaystyle\left\lVert\bm{y}^{cat}_{t,k}-\overline{\bm{x}}^{cat}_{t,k}\right\rVert$
$\displaystyle=\left\lVert\left(\mathbf{W}\otimes
I_{d}\right)\bm{x}^{cat}_{t,k}-\left(\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{T}\right)\bm{x}^{cat}_{t,k}\right\rVert$
$\displaystyle=\left\lVert\left[\left(\mathbf{W}-\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{T}\right)\otimes
I_{d}\right]\bm{x}^{cat}_{t,k}\right\rVert$
$\displaystyle=\left\lVert\left[\left(\mathbf{W}-\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{T}\right)\otimes
I_{d}\right]\left(\bm{x}^{cat}_{t,k}-\overline{\bm{x}}^{cat}_{t,k}\right)\right\rVert$
$\displaystyle\leq\lambda(\mathbf{W})\left\lVert\bm{x}^{cat}_{t,k}-\overline{\bm{x}}^{cat}_{t,k}\right\rVert$
(23)

Let $C_{d}=k_{0}\sqrt{n}D$, the base case is verified for $k\in[1,k_{0}]$
since
$\left\lVert\bm{x}^{cat}_{t,k}-\overline{\bm{x}}^{cat}_{t,k}\right\rVert\leq\sqrt{n}D\leq\frac{C_{d}}{k}$.
Suppose that the hypothesis is verified for $k-1\geq k_{0}$, we have

$\displaystyle\left\lVert\bm{y}^{cat}_{t,k}-\overline{\bm{x}}^{cat}_{t,k}\right\rVert$
$\displaystyle\leq\lambda(\mathbf{W})\left\lVert\bm{x}^{cat}_{t,k}-\overline{\bm{x}}^{cat}_{t,k}\right\rVert$
$\displaystyle=\lambda(\mathbf{W})\left\lVert\left(1-\eta_{k-1}\right)\left(\bm{y}^{cat}_{t,k-1}-\overline{\bm{x}}^{cat}_{t,k-1}\right)+\eta_{k-1}\left(\bm{v}^{cat}_{t,k-1}-\overline{\bm{v}}^{cat}_{t,k-1}\right)\right\rVert$
$\displaystyle\leq\lambda(\mathbf{W})\left\lVert\bm{y}^{cat}_{t,k-1}-\overline{\bm{x}}^{cat}_{t,k-1}\right\rVert+\lambda(\mathbf{W})\frac{\sqrt{n}D}{k-1}$
$\displaystyle\leq\lambda(\mathbf{W})\left(\frac{C_{d}+\sqrt{n}D}{k-1}\right)$
$\displaystyle\leq\lambda(\mathbf{W})C_{d}\frac{k_{0}+1}{k_{0}(k-1)}$
$\displaystyle\leq\frac{C_{d}}{k}$ (24)

where we use the induction hypothesis in the third inequality and the last
inequality follows the fact that
$\lambda(\mathbf{W})\frac{k_{0}+1}{k_{0}(k-1)}\leq\frac{k-1}{k}\cdot\frac{1}{k-1}\leq\frac{1}{k}$.
We conclude the proof by noting that

$\displaystyle\max_{i\in[1,n]}\left\lVert\bm{y}^{i}_{t,k}-\overline{\bm{x}}_{t,k}\right\rVert\leq\sqrt{\sum_{i=1}^{n}\left\lVert\bm{y}^{i}_{t,k}-\overline{\bm{x}}_{t,k}\right\rVert^{2}}=\left\lVert\bm{y}^{cat}_{t,k}-\overline{\bm{x}}^{cat}_{t,k}\right\rVert\leq\frac{C_{d}}{k}$

∎

######  Lemma 6.

Define $C_{g}=\sqrt{n}\max\left\\{\lambda(\mathbf{W})\left(G+\frac{\beta
D}{1-\lambda(\mathbf{W})}\right),k_{0}\beta\left(4C_{d}+AD\right)\right\\}$
and recall the definition of $\nabla F_{t,k}:=\frac{1}{n}\sum_{i=1}^{n}\nabla
f^{i}_{t,k}$. For all $t\in[T]$, $k\in[K]$, we have

$\displaystyle\max_{i\in[1,n]}\left\lVert\bm{d}^{i}_{t,k}-\nabla
F_{t,k}\right\rVert\leq\frac{C_{g}}{k}$ (25)

###### Proof.

We prove the lemma by induction. Following the idea from [xie19b], we have

$\displaystyle\left\lVert\hat{\bm{d}}^{cat}_{t,k}-\nabla
F^{cat}_{t,k}\right\rVert$ $\displaystyle=\left\lVert\left(\mathbf{W}\otimes
I_{d}\right)\hat{\bm{g}}^{cat}_{t,k}-\left(\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{T}\right)\hat{\bm{g}}^{cat}_{t,k}\right\rVert$
$\displaystyle=\left\lVert\left[\left(\mathbf{W}-\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{T}\right)\otimes
I_{d}\right]\hat{\bm{g}}^{cat}_{t,k}\right\rVert$
$\displaystyle=\left\lVert\left[\left(\mathbf{W}-\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{T}\right)\otimes
I_{d}\right]\left(\hat{\bm{g}}^{cat}_{t,k}-\nabla
F^{cat}_{t,k}\right)\right\rVert$
$\displaystyle\leq\lambda(\mathbf{W})\left\lVert\hat{\bm{g}}^{cat}_{t,k}-\nabla
F^{cat}_{t,k}\right\rVert$ (26)

where the third equality and the last inequality are verified since
$\mathbf{W}\cdot\nabla
F^{cat}_{t,k}=\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{T}\cdot\nabla
F^{cat}_{t,k}=\nabla F^{cat}_{t,k}$ and
$\left\lVert\mathbf{W}-\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{T}\right\rVert\leq\lambda(\mathbf{W})$
[16, Lemma 16]. Using the gradient tracking step and Section B.2, we have

$\displaystyle\left\lVert\hat{\bm{d}}^{cat}_{t,k}-\nabla
F^{cat}_{t,k}\right\rVert$
$\displaystyle\leq\lambda(\mathbf{W})\left\lVert\hat{\bm{g}}^{cat}_{t,k}-\nabla
F^{cat}_{t,k}\right\rVert$
$\displaystyle=\lambda(\mathbf{W})\left\lVert\bm{\delta}^{cat}_{t,k}+\hat{\bm{d}}^{cat}_{t,k-1}-\nabla
F^{cat}_{t,k}+\nabla F^{cat}_{t,k-1}-\nabla F^{cat}_{t,k-1}\right\rVert$
$\displaystyle\leq\lambda(\mathbf{W})\left(\left\lVert\hat{\bm{d}}^{cat}_{t,k-1}-\nabla
F^{cat}_{t,k-1}\right\rVert+\left\lVert\bm{\delta}^{cat}_{t,k}-\overline{\bm{\delta}}^{cat}_{t,k}\right\rVert\right)$
$\displaystyle\leq\lambda(\mathbf{W})\left(\left\lVert\hat{\bm{d}}^{cat}_{t,k-1}-\nabla
F^{cat}_{t,k-1}\right\rVert+\left\lVert\bm{\delta}^{cat}_{t,k}\right\rVert\right)$
(27)

where the last inequality holds since

$\displaystyle\left\lVert\bm{\delta}^{cat}_{t,k}-\overline{\bm{\delta}}^{cat}_{t,k}\right\rVert^{2}=\sum_{i=1}^{n}\left\lVert\bm{\delta}^{i}_{t,k}-\overline{\bm{\delta}}_{t,k}\right\rVert^{2}=\sum_{i=1}^{n}\left\lVert\bm{\delta}^{i}_{t,k}\right\rVert^{2}-n\left\lVert\overline{\bm{\delta}}_{t,k}\right\rVert^{2}\leq\sum_{i=1}^{n}\left\lVert\bm{\delta}^{i}_{t,k}\right\rVert^{2}=\left\lVert\bm{\delta}^{cat}_{t,k}\right\rVert^{2}$
(28)

Moreover, using the smoothness of $f_{t}$ and 1, we have

$\displaystyle\left\lVert\bm{\delta}^{cat}_{t,k}\right\rVert^{2}=\sum_{i=1}^{n}\left\lVert\bm{\delta}^{i}_{t,k}\right\rVert^{2}$
$\displaystyle\leq\sum_{i=1}^{n}\left\lVert\nabla f^{i}_{t,k}-\nabla
f^{i}_{t,k-1}\right\rVert^{2}\leq\sum_{i=1}^{n}\beta^{2}\left\lVert\bm{x}^{i}_{t,k}-\bm{x}^{i}_{t,k-1}\right\rVert^{2}$
$\displaystyle\leq n\beta^{2}\left(\frac{4C_{d}+AD}{k-1}\right)^{2}$ (29)

Thus, we have
$\left\lVert\bm{\delta}^{cat}_{t,k}\right\rVert\leq\sqrt{n}\beta\frac{4C_{d}+AD}{k-1}$.
For the base case $k=1$, we have

$\displaystyle\left\lVert\hat{\bm{d}}^{cat}_{t,1}-\nabla
F^{cat}_{t,1}\right\rVert^{2}=\left\lVert\left[\left(\mathbf{W}-\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{T}\right)\otimes
I_{d}\right]\hat{\bm{g}}^{cat}_{t,1}\right\rVert^{2}\leq\lambda^{2}(\mathbf{W})\left\lVert\hat{\bm{g}}^{cat}_{t,1}\right\rVert^{2}\leq\lambda^{2}(\mathbf{W})\sum_{i=1}^{n}\left\lVert\nabla
f^{i}_{t,1}\right\rVert^{2}\leq n\lambda^{2}(\mathbf{W})G^{2}$ (30)

We have then $\left\lVert\hat{\bm{d}}^{cat}_{t,1}-\nabla
F^{cat}_{t,1}\right\rVert\leq\sqrt{n}\lambda(\mathbf{W})G$. For
$k\in(1,k_{0}]$, by Section B.2

$\displaystyle\left\lVert\hat{\bm{d}}^{cat}_{t,k}-\nabla
F^{cat}_{t,k}\right\rVert$
$\displaystyle\leq\lambda(\mathbf{W})\left(\left\lVert\hat{\bm{d}}^{cat}_{t,k-1}-\nabla
F^{cat}_{t,k-1}\right\rVert+\left\lVert\bm{\delta}^{cat}_{t,k}\right\rVert\right)$
$\displaystyle\leq\lambda(\mathbf{W})\left(\left\lVert\hat{\bm{d}}^{cat}_{t,k-1}-\nabla
F^{cat}_{t,k-1}\right\rVert+\sqrt{n\beta^{2}D^{2}}\right)$
$\displaystyle\leq\lambda^{k-1}(\mathbf{W})\left\lVert\hat{\bm{d}}^{cat}_{t,1}-\nabla
F^{cat}_{t,1}\right\rVert+\sum_{\tau=1}^{k}\lambda^{\tau}(\mathbf{W})\sqrt{n}\beta
D$
$\displaystyle\leq\lambda^{k}(\mathbf{W})\sqrt{n}G+\frac{\lambda(\mathbf{W})}{1-\lambda(\mathbf{W})}\sqrt{n}\beta
D$ $\displaystyle\leq\lambda(\mathbf{W})\sqrt{n}\left(G+\frac{\beta
D}{1-\lambda(\mathbf{W})}\right)$

where in the second inequality, we use smoothness of $f_{t}$ and bound the
distance $\left\lVert\bm{x}^{i}_{t,k}-\bm{x}^{i}_{t,k-1}\right\rVert$ by the
diameters $D$. The third inequality resulted from applying the previous one
recursively for $k\in\left\\{1,\ldots,k-1\right\\}$. Using Taylor’s expansion
of $\lambda(\mathbf{W})$ and the bound in Equation 30, we obtain the fourth
inequality. Let
$C_{g}=\sqrt{n}\max\left\\{\lambda(\mathbf{W})\left(G+\frac{\beta
D}{1-\lambda(\mathbf{W})}\right),k_{0}\beta\left(4C_{d}+AD\right)\right\\}$.
We claim that $\left\lVert\hat{\bm{d}}^{cat}_{t,k-1}-\nabla
F^{cat}_{t,k-1}\right\rVert\leq\frac{C_{g}}{k-1}$ for all $k-1\geq k_{0}$. We
prove the claim for round $k$. Using Section B.2, we have

$\displaystyle\left\lVert\hat{\bm{d}}^{cat}_{t,k}-\nabla
F^{cat}_{t,k}\right\rVert$
$\displaystyle\leq\lambda(\mathbf{W})\left(\left\lVert\hat{\bm{d}}^{cat}_{t,k-1}-\nabla
F^{cat}_{t,k-1}\right\rVert+\left\lVert\bm{\delta}^{cat}_{t,k}\right\rVert\right)$
$\displaystyle\leq\lambda(\mathbf{W})\left(\frac{C_{g}}{k-1}+\sqrt{n}\beta\frac{4C_{d}+AD}{k-1}\right)$
$\displaystyle\leq\lambda(\mathbf{W})\left(\frac{C_{g}+\sqrt{n}\beta\left(4C_{d}+AD\right)}{k-1}\right)$
$\displaystyle\leq\lambda(\mathbf{W})\left(C_{g}\frac{k_{0}+1}{k_{0}(k-1)}\right)$
$\displaystyle\leq\frac{C_{g}}{k}$ (31)

where the second inequality followed by the induction hypothesis and Section
B.2. The fourth inequality is a consequence of the definition of $C_{g}$ and
the final inequality resulted from the fact that
$\lambda(\mathbf{W})\frac{k_{0}+1}{k_{0}(k-1)}\leq\frac{1}{k}$ as $k>k_{0}$.
We conclude the proof by noting that

$\displaystyle\max_{i\in[1,n]}\left\lVert\hat{\bm{d}}^{i}_{t,k}-\nabla
F_{t,k}\right\rVert\leq\sqrt{\sum_{i=1}^{n}\left\lVert\hat{\bm{d}}^{i}_{t,k}-\nabla
F_{t,k}\right\rVert^{2}}=\left\lVert\hat{\bm{d}}^{cat}_{t,k}-\nabla
F^{cat}_{t,k}\right\rVert\leq\frac{C_{g}}{k}$

∎

######  Lemma 4.

For all $t\in[T]$, $k\in[K]$ and $i\in[n]$. Let $\bm{v}^{i}_{t,k}$ be the
output of the oracle $\mathcal{O}^{i}_{k}$ with delayed feedback and
$\hat{\bm{v}}^{i}_{t,k}$ its homologous in non-delay case. Suppose that
Assumptions 1 and 2 hold true. Choosing FTPL as the oracle, we have:

$\displaystyle\left\lVert\bm{v}^{i}_{t,k}-\hat{\bm{v}}^{i}_{t,k}\right\rVert\leq
2\zeta\sqrt{n}DG\left[\frac{\lambda\left(\mathbf{W}\right)}{\rho}+1\right]\frac{1}{n}\sum_{i=1}^{n}\sum_{s\leq
t}\mathbb{I}_{\left\\{s+d^{i}_{s}>t\right\\}}$ (32)

where $\zeta$ is the learning rate, $\lambda(\mathbf{W})$ is the second-
largest eigenvalue of $\mathbf{W}$ and $\rho=1-\lambda(\mathbf{W})$ is the
spectral gap of matrix $\mathbf{W}$.

###### Proof.

We call $\bm{u}^{i}_{t}=\zeta\sum_{\ell=1}^{t}\bm{d}^{i}_{\ell}$ the
accumulated delayed feedback of the oracle of agent $i$ and
$\hat{\bm{u}}^{i}_{t}=\zeta\sum_{\ell=1}^{t}\hat{\bm{d}}^{i}_{\ell}$ its
homologous in non-delay setting. Using the same computation in the proof of
Lemma 2, we have

$\displaystyle\left\lVert\bm{v}^{i}_{t,k}-\bm{\hat{v}}^{i}_{t,k}\right\rVert\leq
D\left\lVert\bm{u}^{i}_{t,k}-\bm{\hat{u}}^{i}_{t,k}\right\rVert\leq
D\left\lVert\bm{u}^{cat}_{t,k}-\hat{\bm{u}}^{cat}_{t,k}\right\rVert\leq\zeta
D\left\lVert\sum_{\ell=1}^{t}\left[\bm{d}^{cat}_{\ell,k}-\hat{\bm{d}}^{cat}_{\ell,k}\right]\right\rVert$
(33)

For $t\in[T]$, the concatenation of the gradient local average is expanded as
follow

$\displaystyle\bm{d}^{cat}_{t,k}=\left(\mathbf{W}\otimes
I_{d}\right)\left(\nabla f^{cat}_{t,k}-\nabla
f^{cat}_{t,k-1}+\bm{d}^{cat}_{t,k-1}\right)$ $\displaystyle=$
$\displaystyle\left(\mathbf{W}\otimes I_{d}\right)\left(\nabla
f^{cat}_{t,k}-\nabla f^{cat}_{t,k-1}\right)+\left(\mathbf{W}\otimes
I_{d}\right)^{2}\left(\nabla f^{cat}_{t,k-1}-\nabla
f^{cat}_{t,k-2}+\bm{d}^{cat}_{t,k-2}\right)$ $\displaystyle=$
$\displaystyle\sum_{\tau=1}^{k-1}\left[\left(\mathbf{W}\otimes
I_{d}\right)^{k-\tau}\left(\nabla f^{cat}_{t,\tau+1}-\nabla
f^{cat}_{t,\tau}\right)\right]+\left(\mathbf{W}\otimes I_{d}\right)^{k}\nabla
f^{cat}_{t,1}$ (34) $\displaystyle=$
$\displaystyle\sum_{\tau=1}^{k-1}\left[\left(\mathbf{W}\otimes
I_{d}\right)^{k-\tau}\left(\nabla f^{cat}_{t,\tau+1}-\nabla
f^{cat}_{t,\tau}\right)\right]+\left(\mathbf{W}\otimes I_{d}\right)^{k}\nabla
f^{cat}_{t,1}-\sum_{\tau=1}^{k-1}\left[\nabla F^{cat}_{t,\tau+1}-\nabla
F^{cat}_{t,\tau}\right]-\nabla F^{cat}_{t,1}+\nabla F^{cat}_{t,k}$
$\displaystyle=$
$\displaystyle\sum_{\tau=1}^{k-1}\left[\left[\left(\mathbf{W}^{k-\tau}-\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{T}\right)\otimes
I_{d}\right]\left(\nabla f^{cat}_{t,\tau+1}-\nabla
f^{cat}_{t,\tau}\right)\right]+\left[\left(\mathbf{W}^{k}-\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{T}\right)\otimes
I_{d}\right]\nabla
f^{cat}_{t,1}+\left(\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{T}\otimes
I_{d}\right)\nabla f^{cat}_{t,k}$

Recall the definition of $\nabla
f^{cat}_{t,k}=\left[\sum_{s\in\mathcal{F}^{1}_{t}}\nabla
f^{1\top}_{s,k},\dots,\sum_{s\in\mathcal{F}^{n}_{t}}\nabla
f^{n\top}_{s,k}\right]^{\top}$ and $\nabla\hat{f}^{cat}_{t,k}=\left[\nabla
f^{1\top}_{t,k},\dots,\nabla f^{n\top}_{t,k}\right]^{\top}$. We have

$\displaystyle\sum_{\ell=1}^{t}\left[\nabla
f^{cat}_{\ell,k}-\nabla\hat{f}^{cat}_{\ell,k}\right]=\sum_{s<t}\left[\nabla
f^{1\top}_{s,k}\mathbb{I}_{\left\\{s+d^{1}_{s}>t\right\\}},\ldots,\nabla
f^{n\top}_{s,k}\mathbb{I}_{\left\\{s+d^{n}_{s}>t\right\\}},\right]^{\top}$
(35)

Using Section B.2, we bound the RHS of Equation 33 as follow

$\displaystyle\left\lVert\sum_{\ell=1}^{t}\left[\bm{d}^{cat}_{\ell,k}-\hat{\bm{d}}^{cat}_{\ell,k}\right]\right\rVert\leq\sum_{\tau=1}^{k-1}\left\lVert\left(\mathbf{W}^{k-\tau}-\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{T}\right)\otimes
I_{d}\right\rVert\left\lVert\sum_{\ell=1}^{t}\left[\nabla
f^{cat}_{\ell,\tau+1}-\hat{f}^{cat}_{\ell,\tau+1}+\hat{f}^{cat}_{\ell,\tau}-\nabla
f^{cat}_{t,\tau}\right]\right\rVert$
$\displaystyle\quad+\left\lVert\left(\mathbf{W}^{k}-\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{T}\right)\otimes
I_{d}\right\rVert\left\lVert\sum_{\ell=1}^{t}\left[\nabla
f^{cat}_{\ell,1}-\hat{f}^{cat}_{\ell,1}\right]\right\rVert+\left(\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{T}\otimes
I_{d}\right)\left\lVert\sum_{\ell=1}^{t}\left[\nabla
f^{cat}_{\ell,k}-\hat{f}^{cat}_{\ell,k}\right]\right\rVert$ $\displaystyle\leq
2\sum_{\tau=1}^{k}\lambda^{k-\tau}(\mathbf{W})\left\lVert\sum_{s\leq
t}\left[\nabla
f^{1\top}_{s,\tau}\mathbb{I}_{\left\\{s+d^{1}_{s}>t\right\\}},\ldots,\nabla
f^{n\top}_{s,\tau}\mathbb{I}_{\left\\{s+d^{n}_{s}>t\right\\}}\right]^{\top}\right\rVert$
$\displaystyle\quad+\lambda^{k}(\mathbf{W})\left\lVert\sum_{s\leq
t}\left[\nabla
f^{1\top}_{s,k}\mathbb{I}_{\left\\{s+d^{1}_{s}>t\right\\}},\ldots,\nabla
f^{n\top}_{s,k}\mathbb{I}_{\left\\{s+d^{n}_{s}>t\right\\}}\right]^{\top}\right\rVert+\left\lVert\sum_{s\leq
t}\left[\nabla
f^{1\top}_{s,1}\mathbb{I}_{\left\\{s+d^{1}_{s}>t\right\\}},\ldots,\nabla
f^{n\top}_{s,1}\mathbb{I}_{\left\\{s+d^{n}_{s}>t\right\\}}\right]^{\top}\right\rVert$
$\displaystyle\leq 2\sum_{\tau=1}^{k}\lambda^{k-\tau}(\mathbf{W})\sum_{s\leq
t}\left\lVert\left[\nabla
f^{1\top}_{s,\tau}\mathbb{I}_{\left\\{s+d^{1}_{s}>t\right\\}},\ldots,\nabla
f^{n\top}_{s,\tau}\mathbb{I}_{\left\\{s+d^{n}_{s}>t\right\\}}\right]^{\top}\right\rVert$
$\displaystyle\quad+\lambda^{k}(\mathbf{W})\sum_{s\leq
t}\left\lVert\left[\nabla
f^{1\top}_{s,k}\mathbb{I}_{\left\\{s+d^{1}_{s}>t\right\\}},\ldots,\nabla
f^{n\top}_{s,k}\mathbb{I}_{\left\\{s+d^{n}_{s}>t\right\\}}\right]^{\top}\right\rVert+\sum_{s\leq
t}\left\lVert\left[\nabla
f^{1\top}_{s,1}\mathbb{I}_{\left\\{s+d^{1}_{s}>t\right\\}},\ldots,\nabla
f^{n\top}_{s,1}\mathbb{I}_{\left\\{s+d^{n}_{s}>t\right\\}}\right]^{\top}\right\rVert$
$\displaystyle\leq 2\sum_{\tau=1}^{k}\lambda^{k-\tau}(\mathbf{W})\sum_{s\leq
t}\sqrt{\sum_{i=1}^{n}\left\lVert\nabla
f^{i}_{s,\tau}\mathbb{I}_{\left\\{s+d^{i}_{s}>t\right\\}}\right\rVert^{2}}+\lambda^{k}(\mathbf{W})\sum_{s\leq
t}\sqrt{\sum_{i=1}^{n}\left\lVert\nabla
f^{i}_{s,k}\mathbb{I}_{\left\\{s+d^{i}_{s}>t\right\\}}\right\rVert^{2}}+\sum_{s\leq
t}\sqrt{\sum_{i=1}^{n}\left\lVert\nabla
f^{i}_{s,1}\mathbb{I}_{\left\\{s+d^{i}_{s}>t\right\\}}\right\rVert^{2}}$
$\displaystyle\leq 2G\sum_{\tau=1}^{k}\lambda^{k-\tau}(\mathbf{W})\sum_{s\leq
t}\sqrt{\sum_{i=1}^{n}\mathbb{I}_{\left\\{s+d^{i}_{s}>t\right\\}}}+G\left[\lambda^{k}(\mathbf{W})+1\right]\sum_{s\leq
t}\sqrt{\sum_{i=1}^{n}\mathbb{I}_{\left\\{s+d^{i}_{s}>t\right\\}}}$
$\displaystyle\leq
2G\left[\frac{\lambda(\mathbf{W})}{1-\lambda(\mathbf{W})}+1\right]\sum_{s\leq
t}\sqrt{\sum_{i=1}^{n}\mathbb{I}_{\left\\{s+d^{i}_{s}>t\right\\}}}$
$\displaystyle\leq
2\sqrt{n}G\left[\frac{\lambda(\mathbf{W})}{1-\lambda(\mathbf{W})}+1\right]\sum_{s\leq
t}\frac{1}{n}\sum_{i=1}^{n}\sum_{i=1}^{n}\mathbb{I}_{\left\\{s+d^{i}_{s}>t\right\\}}$

where the fifth inequality resulted from Lipschitzness of $f_{t}$ and the
value of indicator function. ∎

###  B.3 Proofs of Theorem 2

######  Theorem 2.

Given a constraint set $\mathcal{K}$. Let $A=\max\left\\{3,\frac{3G}{2\beta
D},\frac{2\beta C_{d}+C_{g}}{\beta D}\right\\}$,
$\eta_{k}=\min\left\\{1,\frac{A}{k}\right\\}$, and $K=\sqrt{T}$. Suppose that
Assumptions 1, 2 and 3 hold true. If we choose FTPL as the underlying oracle
and set $\zeta=\frac{1}{G\sqrt{B}}$, the regret of Algorithm 2 is

$\displaystyle\sum_{t=1}^{T}$
$\displaystyle\left[F_{t}(\bm{x}^{i}_{t})-F_{t}(\bm{x}^{*})\right]\leq\left(GC_{d}+2\beta
AD^{2}\right)\sqrt{T}+3(A+1)\left[2\sqrt{n}DG\left(\frac{\lambda(\mathbf{W})}{\rho}+1\right)\sqrt{B}+\mathcal{R}_{T,\mathcal{O}}\right]$

where $B=\frac{1}{n}\sum_{i=1}^{n}B_{i}$ such that $B_{i}$ is the sum of delay
values of agent $i$. $C_{d}=k_{0}\sqrt{n}D$ and
$C_{g}=\sqrt{n}\max\left\\{\lambda(\mathbf{W})\left(G+\frac{\beta
D}{\rho}\right),k_{0}\beta\left(4C_{d}+AD\right)\right\\}$ are defined in
Lemmas 3 and 6 and $\mathcal{R}_{T,\mathcal{O}}$ is the regret of FTPL with
the current choice of $\zeta$

###### Proof.

By smoothness of $F_{t}$, we have

$\displaystyle
F_{t}(\overline{\bm{x}}_{t,k+1})-F_{t}(\bm{x}^{*})=F_{t}\left(\overline{\bm{x}}_{t,k}+\eta_{k}\left(\frac{1}{n}\sum_{i=1}^{n}\bm{v}^{i}_{t,k}-\overline{\bm{x}}_{t,k}\right)\right)-F_{t}(\bm{x}^{*})$
$\displaystyle\leq$ $\displaystyle
F_{t}(\overline{\bm{x}}_{t,k})-F_{t}(\bm{x}^{*})+\eta_{k}\left\langle\nabla
F_{t}(\overline{\bm{x}}_{t,k}),\frac{1}{n}\sum_{i=1}^{n}\bm{v}^{i}_{t,k}-\overline{\bm{x}}_{t,k}\right\rangle+\eta_{k}^{2}\frac{\beta}{2}\left\lVert\frac{1}{n}\sum_{i=1}^{n}\bm{v}^{i}_{t,k}-\overline{\bm{x}}_{t,k}\right\rVert^{2}$
$\displaystyle\leq$ $\displaystyle
F_{t}(\overline{\bm{x}}_{t,k})-F_{t}(\bm{x}^{*})+\frac{\eta_{k}}{n}\left\langle\nabla
F_{t}(\overline{\bm{x}}_{t,k}),\bm{v}^{i}_{t,k}-\overline{\bm{x}}_{t,k}\right\rangle+\eta_{k}^{2}\frac{\beta
D^{2}}{2}$ (37) $\displaystyle\leq$ $\displaystyle
F_{t}(\overline{\bm{x}}_{t,k})-F_{t}(\bm{x}^{*})+\frac{\eta_{k}}{n}\sum_{i=1}^{n}\left[\left\langle\nabla
F_{t}(\overline{\bm{x}}_{t,k}),\bm{v}^{i}_{t,k}-\bm{x}^{*}\right\rangle+\left\langle\nabla
F_{t}(\overline{\bm{x}}_{t,k}),\bm{x}^{*}-\overline{\bm{x}}_{t,k}\right\rangle\right]+\eta_{k}^{2}\frac{\beta
D^{2}}{2}$ $\displaystyle\leq$
$\displaystyle\left(1-\eta_{k}\right)\left[F_{t}(\overline{\bm{x}}_{t,k})-F_{t}(\bm{x}^{*})\right]+\frac{\eta_{k}}{n}\sum_{i=1}^{n}\left[\left\langle\nabla
F_{t}(\overline{\bm{x}}_{t,k}),\bm{v}^{i}_{t,k}-\bm{x}^{*}\right\rangle\right]+\eta_{k}^{2}\frac{\beta
D^{2}}{2}$ $\displaystyle\leq$
$\displaystyle\left(1-\eta_{k}\right)\left[F_{t}(\overline{\bm{x}}_{t,k})-F_{t}(\bm{x}^{*})\right]+\frac{\eta_{k}}{n}\sum_{i=1}^{n}\left[\left\langle\nabla
F_{t}(\overline{\bm{x}}_{t,k}),\bm{v}^{i}_{t,k}-\bm{\hat{v}}^{i}_{t,k}\right\rangle+\left\langle\nabla
F_{t}(\overline{\bm{x}}_{t,k}),\bm{\hat{v}}^{i}_{t,k}-\bm{x}^{*}\right\rangle\right]+\eta_{k}^{2}\frac{\beta
D^{2}}{2}$ $\displaystyle\leq$
$\displaystyle\left(1-\eta_{k}\right)\left[F_{t}(\overline{\bm{x}}_{t,k})-F_{t}(\bm{x}^{*})\right]+\frac{\eta_{k}}{n}\sum_{i=1}^{n}\left[\left\langle\nabla
F_{t}(\overline{\bm{x}}_{t,k}),\bm{v}^{i}_{t,k}-\bm{\hat{v}}^{i}_{t,k}\right\rangle+\left\langle\bm{\hat{d}}^{i}_{t,k},\bm{\hat{v}}^{i}_{t,k}-\bm{x}^{*}\right\rangle\right]+\eta_{k}\frac{2\beta
C_{d}+C_{g}}{k}D+\eta_{k}^{2}\frac{\beta D^{2}}{2}$

where we used convexity of $F_{t}$ in the fourth inequality and the last
inequality follows by observing that

$\displaystyle\left\langle\nabla
F_{t}(\overline{\bm{x}}_{t,k}),\bm{\hat{v}}^{i}_{t,k}-\bm{x}^{*}\right\rangle=\left\langle\nabla
F_{t}(\overline{\bm{x}}_{t,k})-\nabla
F_{t,k},\bm{\hat{v}}^{i}_{t,k}-\bm{x}^{*}\right\rangle+\left\langle\nabla
F_{t,k},\bm{\hat{v}}^{i}_{t,k}-\bm{x}^{*}\right\rangle$
$\displaystyle=\left\langle\nabla F_{t}(\overline{\bm{x}}_{t,k})-\nabla
F_{t,k},\bm{\hat{v}}^{i}_{t,k}-\bm{x}^{*}\right\rangle+\left\langle\nabla
F_{t,k}-\bm{\hat{d}}^{i}_{t,k},\bm{\hat{v}}^{i}_{t,k}-\bm{x}^{*}\right\rangle+\left\langle\bm{\hat{d}}^{i}_{t,k},\bm{\hat{v}}^{i}_{t,k}-\bm{x}^{*}\right\rangle$
$\displaystyle\leq\left(\beta\left\lVert\overline{\bm{\bm{x}}}_{t,k}-\bm{\bm{x}}^{i}_{t,k}\right\rVert+\left\lVert\nabla
F_{t,k}-\bm{\hat{d}}^{i}_{t,k}\right\rVert\right)D+\left\langle\bm{\hat{d}}^{i}_{t,k},\bm{\hat{v}}^{i}_{t,k}-\bm{x}^{*}\right\rangle$
$\displaystyle\leq\frac{2\beta
C_{d}+C_{g}}{k}D+\left\langle\bm{\hat{d}}^{i}_{t,k},\bm{\hat{v}}^{i}_{t,k}-\bm{x}^{*}\right\rangle$

Let $A=\max\left\\{3,\frac{3G}{2\beta D},\frac{2\beta C_{d}+Cg}{\beta
D}\right\\}$ and $\eta_{k}=\frac{A}{k}$, From Lemma 5 we have

$\displaystyle
F_{t}(\overline{\bm{x}}_{t,K+1})-F_{t}(\bm{x}^{*})\leq\frac{2\beta
AD^{2}}{K}+\frac{1}{n}\sum_{i=1}^{n}\sum_{k=1}^{K}\eta_{k}\left[\prod_{\ell=k+1}^{K}\left(1-\eta_{\ell}\right)\right]\left[\left\langle\bm{\hat{d}}^{i}_{t,k},\bm{\hat{v}}^{i}_{t,k}-\bm{x}^{*}\right\rangle+\left\langle\nabla
F_{t}(\overline{\bm{\bm{x}}}_{t,k}),\bm{v}^{i}_{t,k}-\bm{\hat{v}}^{i}_{t,k}\right\rangle\right]$
(38)

Summing Equation 38 over $T$-rounds yields,

$\displaystyle\sum_{t=1}^{T}$
$\displaystyle\left[F_{t}(\overline{\bm{x}}_{t})-F_{t}(\bm{x}^{*})\right]\leq\frac{2\beta
AD^{2}T}{K}+\frac{1}{n}\sum_{i=1}^{n}\sum_{k=1}^{K}\eta_{k}\prod_{\ell=k+1}^{K}\left(1-\eta_{\ell}\right)\sum_{t=1}^{T}\left[\left\langle\bm{\hat{d}}^{i}_{t,k},\bm{\hat{v}}^{i}_{t,k}-\bm{x}^{*}\right\rangle+\left\langle\nabla
F_{t}(\overline{\bm{\bm{x}}}_{t,k}),\bm{v}^{i}_{t,k}-\bm{\hat{v}}^{i}_{t,k}\right\rangle\right]$
$\displaystyle\leq\frac{2\beta
AD^{2}T}{K}+\frac{1}{n}\sum_{i=1}^{n}\sum_{k=1}^{K}\eta_{k}\prod_{\ell=k+1}^{K}\left(1-\eta_{\ell}\right)\left[\mathcal{R}_{T,\mathcal{O}}+2\zeta\sqrt{n}DG^{2}\left(\frac{\lambda(\mathbf{W})}{1-\lambda(\mathbf{W})}+1\right)\frac{1}{n}\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{s\leq
t}\mathbb{I}_{\left\\{s+d^{i}_{s}>t\right\\}}\right]$
$\displaystyle\leq\frac{2\beta
AD^{2}T}{K}+3(A+1)\left[\mathcal{R}_{T,\mathcal{O}}+2\zeta\sqrt{n}DG^{2}\left(\frac{\lambda(\mathbf{W})}{1-\lambda(\mathbf{W})}+1\right)\frac{1}{n}\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{s\leq
t}\mathbb{I}_{\left\\{s+d^{i}_{s}>t\right\\}}\right]$ (39)

From Section B.3, we deduce that, for all $i\in[n]$,

$\displaystyle\sum_{t=1}^{T}$
$\displaystyle\left[F_{t}(\bm{x}^{i}_{t})-F_{t}(\bm{x}^{*})\right]\leq\sum_{t=1}^{T}\left[F_{t}(\bm{x}^{i}_{t})-F_{t}(\overline{\bm{x}}_{t})\right]+\sum_{t=1}^{T}\left[F_{t}(\overline{\bm{x}}_{t})-F_{t}(\bm{x}^{*})\right]$
$\displaystyle\leq\sum_{t=1}^{T}G\left\lVert\bm{x}^{i}_{t}-\overline{\bm{x}}_{t}\right\rVert+\sum_{t=1}^{T}\left[F_{t}(\overline{\bm{x}}_{t})-F_{t}(\bm{x}^{*})\right]$
$\displaystyle\leq\frac{GC_{d}T}{K}+\sum_{t=1}^{T}\left[F_{t}(\overline{\bm{x}}_{t})-F_{t}(\bm{x}^{*})\right]$
$\displaystyle\leq\frac{GC_{d}+2\beta
AD^{2}}{K}T+3(A+1)\left[\mathcal{R}_{T,\mathcal{O}}+2\zeta\sqrt{n}DG^{2}\left(\frac{\lambda(\mathbf{W})}{1-\lambda(\mathbf{W})}+1\right)\frac{1}{n}\sum_{i=1}^{n}\sum_{t=1}^{T}\sum_{s<t}\mathbb{I}_{\left\\{s+d^{i}_{s}>t\right\\}}\right]$
$\displaystyle\leq\frac{GC_{d}+2\beta
AD^{2}}{K}T+3(A+1)\left[\mathcal{R}_{T,\mathcal{O}}+2\zeta\sqrt{n}DG^{2}\left(\frac{\lambda(\mathbf{W})}{1-\lambda(\mathbf{W})}+1\right)\frac{1}{n}\sum_{i=1}^{n}B_{i}\right]$

The theorem follows by letting $\zeta=\frac{1}{G\sqrt{B}}$, $K=\sqrt{T}$ and
$B=\frac{1}{n}\sum_{i=1}^{n}B_{i}$. This concludes the proof. ∎