Distributed Asynchronous Discrete-Time Feedback Optimization
Gabriel Behrendt, Matthew Longmire, Zachary I. Bell,
Matthew Hale, Member, IEEE

Gabriel Behrendt and Matthew Hale were supported by
AFRL under grant FA8651-23-F-A006,
AFOSR under grant FA9550-19-1-0169,
and ONR under grant N00014-21-1-2495.
Matthew Longmire was supported by AFRL under contract FA8651-22-F-1052 under task orders FA8651-19-D-0037 and FAA8651-22-F-1045.

Gabriel Behrendt, Matthew Longmire, and Matthew Hale are
with the Department of Mechanical and Aerospace Engineering
at the University of Florida, Gainesville, FL, USA.
Emails:  Zachary I. Bell is with AFRL/RW at Eglin AFB. Email:

In this article, we present an algorithm that drives the outputs of a network of agents to
jointly track the solutions of time-varying optimization problems in a way that is robust
to asynchrony in the agents' operations. We consider three operations that can be asynchronous:
(1) computations of control inputs, (2) measurements of network outputs, and (3) communications
of agents' inputs and outputs. We first show that our algorithm
converges to the solution of a time-invariant feedback optimization problem in linear time.
Next, we show that our algorithm drives outputs to track the solution of time-varying feedback optimization
problems within a bounded error dependent upon the movement of the minimizers and degree of
asynchrony in a way that we make precise. These convergence results are extended to quantify
agents' asymptotic behavior as the length of their time horizon approaches infinity. Then, to
ensure satisfactory network performance, we specify the timing of agents' operations relative
to changes in the objective function that ensure a desired error bound.
Numerical experiments confirm these developments and show the success
of our distributed feedback optimization algorithm under asynchrony.

Multi-agent systems, Asynchronous optimization algorithms, Time-varying optimization.

§ INTRODUCTION

Time-varying optimization problems arise in machine learning, robotics, power systems, and others [1, 2, 3]. These problems can model time-varying demands in power distribution systems [4] and robot navigation in cluttered dynamic environments [5], among other engineering
Time-varying optimization problems have been studied in both continuous-time [6, 7, 8] and discrete-time [9, 10, 11, 12], and methods for tracking their solutions include correction-only methods [13, 9] and prediction-correction methods [14, 15].
For a survey of time-varying optimization  see [16, 17].

Time-varying optimization problems have been combined with control by embedding optimization algorithms
into feedback loops. This setup often uses the measured
output of a dynamical system as the input to an optimization
algorithm. Then the optimization algorithm computes new control inputs for the system that
drive its outputs to track the time-varying solution of a time-varying optimization problem.
The actual measured outputs of a system can be subject to disturbances, e.g., measurement
noise, and the use of measured outputs in this setup can provide robustness to such disturbances
without needing to explicitly estimate or model those disturbances [18].
In discrete time, measuring an output leads to a new optimization problem whose solution
is the optimal input at the next timestep.
In some cases, the calculation of optimal inputs
cannot be run to completion

due to practical constraints,
e.g., a low-power computer may not have enough time to exactly
reach a solution before a new input is needed by the system.
In such cases, sub-optimal inputs to the control
system are used.
These types of
feedback optimization methods have been used

in various settings such as
optimal power flow and human-in-the-loop control, among others [19, 13, 20, 21, 22].

In this paper, we develop and analyze a distributed algorithm for multi-agent feedback optimization.
In centralized feedback optimization,
all output measurements are fed into a single optimization algorithm, which computes
all inputs for the system. However, some modern control applications
consist of interacting decision-makers, such as buildings on the smart power grid,
and we therefore develop a
multi-agent feedback optimization framework.

In this framework, different agents measure different system outputs and compute different system inputs, and
they communicate to collaborate.
Many multi-agent systems face asynchrony in agents' communications, computations, and sensor measurements. For example, asynchronous communications can arise from
adversarial jamming,
asynchronous computations can stem from heterogeneous hardware, and
asynchrony in sensor measurements can be due to intermittent feedback [23].

Therefore, the goal of this article is to design a decentralized feedback optimization algorithm
that enables a network of agents
to drive system outputs to track the
time-varying solutions of time-varying optimization problems,
even when agents’
communications, computations, and sensor measurements are subject to asynchrony.
In particular, we use a block-based gradient optimization algorithm.
Asynchronous block-based algorithms were first established in seminal work in [24, 25, 26], and
recent developments have extended these results to constrained problems [27], problems that satisfy the Polyak-Łojasiewicz condition [28], and others [29, 30]. These successes motivate their use here as well.
To the best of our knowledge, our work is the first to consider decentralized
feedback optimization with asynchrony
in computations, communications, and sensing.

To summarize, this paper makes the following contributions:

Distributed Time-varying optimization

7 correction-only. ct

* <cit.> correction-only. dt

* <cit.> correction-only. dt

* <cit.> correction-only. dt

* <cit.> correction-only. dt

* <cit.> pc. ct. averaging based consensus. assumes connected graph. no asynchrony

* We provide the first block-based asynchronous algorithm for distributed feedback optimization problems (Algorithm <ref>).

* We show that this algorithm converges toward the global minimizer for time-invariant and time-varying feedback optimization problems, and we derive a convergence rate (Theorems <ref> & <ref>).

* We show that our algorithm
asymptotically tracks the global minimizer
to within an explicit error bound (Theorem <ref>).

* We provide timing specifications for computations, communications, and sensor measurements to achieve desired network tracking performance (Theorem <ref>, Corollary <ref>).

* We empirically demonstrate the ability of our algorithm to track the solutions of feedback optimization problems by applying it to networks of
agents in two simulations (Section <ref>).

Feedback optimization and time-varying optimization have been studied in the centralized setting
[31, 19], as well as
in the distributed setting [20, 32, 33].
The most closely related works to the current article are [34, 35, 20, 32, 33]. Results in
[34] studied decentralized feedback optimization problems where agents' communications are subject to asynchrony, and
[35] considers time-varying optimization problems with asynchrony in agents' computations and communications, while
[20] develops a primal-dual method utilizing feedback for the optimal power flow problem.
Efforts in
[32] developed a distributed saddle-flow algorithm to achieve consensus over a connected graph considering a feedback optimization problem, and finally
we mention that
[33] proposes a distributed feedback algorithm for the optimal power flow problem, and they consider asynchrony in agents' computations.
This article differs from all of these works in that we

address asynchrony
in agents' computations, communications, and sensor measurements simultaneously.
This article extends our previous work [36] on convex time-varying optimization problems,
and the current paper differs from [36] because it considers the feedback optimization setting.

The rest of this article is organized as follows.
Section <ref> gives a problem statement, and
Section <ref> presents our asynchronous feedback optimization algorithm.
Convergence rates are derived in Section <ref>,
Section <ref> presents simulations,
and Section <ref> concludes.

Notation Let $\N=\{1,2,3,\dots \}$ denote the natural numbers and let ${\N_{0} = \N \cup \{ 0 \}}$ denote the non-negative integers.
For $N \in \N$, define $[N] = \{1, \ldots, N\}$.
We use $\norm{\cdot}$ for the Euclidean norm. For $a \in \R^n$ and $b \in \R^m$ we denote the stacking of these vectors as $(a,b) \in \R^{n+m}$.
The diameter of a compact set $\X \subset \R^n$ is denoted $\diam ( \X ) \coloneqq  \sup_{x, y \in \mathcal{X}} \|x - y\|$.
We use $\Pi_{Z}$ for the Euclidean projection of a point
onto a closed, convex set $Z$, i.e., $\Pi_Z[v] = \argmin_{z \in Z} \|v - z\|$.
We define $\nabla_x \coloneqq \frac{\partial}{\partial x}$
and $\nabla_y \coloneqq \frac{\partial}{\partial y}$. We denote $I_n$ as the $n \times n$ identity matrix
and $\otimes$ is the Kronecker product. We also use $\mathbb{1}_n$ as the $n$-dimensional ones vector.

Early works related to this field designed continuous-time feedback controllers such that the control law regulates the system to an optimal steady state operating point which is the solution to an optimization problem.

* Time-varying optimization problems arise in many domains

* Optimization problems are so large that they need to be solved over a network of agents

* Batch solvers cannot solve the large scale optimization problems fast enough so we need algorithms that can be implemented online to track the solution of these time-varying problems.

* More sensors than ever before = more output data than ever before.

* Online Convex Optimization

* <cit.>

* Parametric Optimization

* Predictor-Corrector Methods <cit.>

* Simplicial methods <cit.>

* Time-Varying Optimization

* Correction-only

* Continuous-Time <cit.>

* Discrete-Time <cit.>

* Prediction-correction

* Continuous-Time <cit.>

* Discrete-Time <cit.>

* Feedback Optimization

Why feedback optimization?

* Measuring all the disturbances over an entire network and estimating the disturbance model may be computationally infeasible

* They require limited knowledge of the input-output map and no knowledge of disturbances

Feedback optimization methods utilize output measurements from a dynamical system to drive its states and outputs to the solution of an optimization problem.
Early works related to this field designed continuous-time feedback controllers such that the control law regulates the system to an optimal steady state operating point which is the solution to an optimization problem.

* <cit.> considers a time-invariant optimization problem with no exogenous disturbances. Nonlinear dynamics

* <cit.> considers an optimization problem with a time-invariant objective and time-varying constraints due to exogenous disturbances. Requires knowledge of the disturbance model. Distributed control affine dynamics.

13 considers time-varying objective function and utilizes output measurements rather than use knowledge of disturbance model. LTI dynamics

Feedback optimization algorithms have been proposed in the centralized case to track the solution of time-varying optimization problems.

31 A Feedback-Based Regularized Primal-Dual Gradient Method for Time-Varying Nonconvex Optimization

Feedback optimization algorithms have been proposed in the distributed case

20 tracks the time-varying solution of the approximate optimal power flow problem over a network of agents using primal-dual method with feedback. Discrete-time.

32 Saddle flow for distributed feedback-based optimization. Static linear map. Continuous-time

Feedback Optimization has been implemented asynchronously

* <cit.>

* <cit.>

* <cit.>

Let $\N=\{1,2,3,\dots \}$ denote the natural numbers and let ${\N_{0} = \N \cup \{ 0 \}}$ denote the non-negative integers.
For $N \in \N$, define $[N] = \{1, \ldots, N\}$.
The notation $\norm{\cdot}$ denotes the Euclidean norm. For vectors $a \in \R^n$ and $b \in \R^m$ we denote the stacking of these vectors using the notation $(a,b) \in \R^{n+m}$. Given a compact set $\X \subset \R^n$ we denote its diameter by $\diam ( \X ) \coloneqq  \sup\limits_{x, y \in \mathcal{X}} \|x - y\|$.
We use the notation $\Pi_{Z}$ to denote the Euclidean projection of a point
onto a closed, convex set $Z$, i.e., $\Pi_Z[v] = \argmin_{z \in Z} \|v - z\|$.
We also define the operators $\nabla_x \coloneqq \frac{\partial}{\partial x}$
and $\nabla_y \coloneqq \frac{\partial}{\partial y}$.

If ${f:\R^n \rightarrow \R}$ is continuously differentiable and has the property ${\Vert \nabla f(x) - \nabla f(y) \Vert \leq K \Vert x-y \Vert}$ for every ${x,y \in \R^n}$, then

$f\left(x+y\right) \leq f\left(x\right)+y^{T}\nabla f\left(x\right)+\frac{K}{2}\left\Vert y\right\Vert^{2}$.

§ PROBLEM FORMULATION

This section states the problem
that is the focus of this paper.

§.§ Problem Statement

Suppose the output of a dynamical system is given as

${y = h(x)}$,

where $h:\R^n \rightarrow \R^m$ is a map from some controllable inputs ${x \in \X \subseteq \R^n}$ to outputs $y \in \Y \subseteq \R^m$ for sets $\X$ and $\Y$.
In this article, we consider systems where $h$ is a linear map of the form

$y(k) = Cx(k)$,

where $C \in \R^{m \times n}$.
Our goal is to regulate the outputs of such a system
to the solution of a time-varying optimization problem.
We consider a network of agents doing so,
and this setup models settings in which
computations of new inputs and/or measurements
of outputs are done in a parallelized fashion.
That is, while the relationship $y(k) = Cx(k)$ may hold,
measurements of each entry of $y$ may happen onboard different embedded
sensors, and their embedded processors may compute new
values for different entries of $x$.
This can be seen, e.g., in
the real-time control of power distribution systems, which
measures active and reactive powers from a network
to regulate voltages and power
flows [20].
It can be difficult to synchronize agents' operations, and thus all agents are permitted to operate asynchronously as they compute
new inputs, measure outputs, and communicate
to work together.

Formally, we consider problems of the following form.

Given $f : \R^{n} \times \N_{0} \rightarrow \R$, $g : \R^{m} \times \N_{0} \rightarrow \R$, using $N \in \N$ agents that asynchronously
compute, communicate, and measure outputs, drive $x$ and $y$ to
track the solution of

\begin{align}
\underset{x\in \X}{\textnormal{minimize}} & \ \J{x}{y}{\ell} \coloneqq \f{x}{\ell} + \g{y}{\ell} \\
\textnormal{subject to} & \ y=Cx,
\end{align}

where $t_{\ell} \in \T \coloneqq \{t_0, \ldots, t_T\}$
and $T \in \N$.

Problem <ref> can model the scenario of sampling from a continuous-time objective function that
was considered in [14, 10], though we model problems simply as occurring in discrete time.

Problem <ref> is an aggregated form of the problem
that will be solved by $N$ agents. However
no single agent will always know the most recent values
of all entries of $y$ as it is written in Problem <ref>, and the same is true for $x$.
Instead, different agents will
measure different entries of $y$, and different agents will compute
new values for
different entries of $x$
(discussed in Section <ref>). Under asynchronous communications, agents will send and receive different
entries of $x$ and $y$ at different times, causing agents to have disagreeing local
copies of $x$ and $y$ onboard.
These disagreements are disturbances in $x$ and $y$, in the sense that each
agent's local copy of $x$ and $y$ can be viewed as a perturbed version of the actual values of $x$ and $y$.
When $x$ and $y$ are used in local computations, their attendant perturbations enter these computations as well.
Feedback optimization has been shown to be robust to various forms of perturbations, and
in Section <ref>, we show that it is robust to the perturbations that result
from asynchrony as well. $\blacklozenge$

§.§ Assumptions on Problem <ref>

We make the following assumptions about Problem <ref>.

For all $\ind{\ell}  \in \T$, the functions $\f{\cdot}{\ell}$ and $\g{\cdot}{\ell}$ are twice continuously differentiable and $p$-strongly convex. $\lozenge$

Assumption <ref> guarantees the existence and continuity of both the gradient and Hessian of $\J{\cdot}{\cdot}{\ell}$. Additionally, it implies that $\J{\cdot}{\cdot}{\ell}$ is $p$-strongly convex for all $\ind{\ell} \in \T$.

The constraint set $\X$ can be decomposed via

${\X = \X_{1} \times \X_{2} \times \dots \times \X_{N}}$,

where $\X_{i} \subseteq \R^{n_i}$, $n_i \in \N$, is non-empty, compact, and polyhedral for all $i \in [N]$. $\lozenge$

Assumption <ref> permits constraints such as box constraints, which
are common in multi-agent problems.
Because $y = Cx$ we also have $y \in \Y$, where $\Y = \{y = Cx : x \in \X\}$,
and under Assumption <ref> the set $\Y$
is non-empty, compact, and convex.

We decompose $x\in\X$ via $x = \begin{bmatrix} x^T_1 \hdots x^T_N  \end{bmatrix}^T$, where for all ${i \in [N]}$ we have $x_{i} \in \X_{i} \subseteq \R^{n_i}$ and $n= \sum^N_{i=1} n_i$. We decompose $y \in \Y$ via $y = \begin{bmatrix} y^T_1 \hdots y^T_N  \end{bmatrix}^T$, where $y_{i} \in \R^{m_i}$ and $m= \sum^N_{i=1} m_i$. For notational simplicity,
we consider the case where every agent measures at least one output,
i.e., at least one entry of $y$, though all of our developments directly apply to problems in which this is not the case.

Under this decomposition of $y$, agent $i$ measures the block of outputs $y_i$
and performs computations to determine subsequent values of $x_i$.
We note that, for all $i \in [N]$,
Assumption <ref> allows agent $i$ to project values of $x_i$ onto $\X_i$, and,
when done by all agents, this projection ensures that $x\in\X$.

It will be helpful in the forthcoming analysis to partition the matrix $C$ as

$C = \begin{bmatrix}
C_1 & C_2 & \dots & C_N
\end{bmatrix}$,

where we have defined the matrix $\Ci \in \R^{m \times n_i}$ for all $i \in [N]$.
Here, $C_1$ is the first $n_1$ columns of $C$, then $C_2$
is the next $n_2$ columns, etc.
We also denote the rows of $C$ via

$C = \begin{bmatrix}
C^T_{1*} & C^T_{2*} & \dots & C^T_{N*}
\end{bmatrix}^T$,

where $C_{1*}$ is the first $m_1$ rows, then $C_{2*}$
is the next $m_2$ rows, etc.

Assumptions <ref> and <ref> ensure the existence and uniqueness of
the minimizer of $J(\cdot, \cdot; t_{\ell})$.
For $t_{\ell} \in \T$ we denote this minimizer as

\begin{equation} \label{eq:solution}
\x{*}{}{\ind{\ell}} \coloneqq \underset{x \in \X}{\argmin} \ \f{x}{\ell} + \g{Cx}{\ell}, \quad
\y{*}{}{\ind{\ell}} = C \x{*}{}{\ind{\ell}}.
\end{equation}

Assumptions <ref> and <ref> also give the following lemma.

Let Assumptions <ref> and <ref> hold. Then
for every $\varpi > 0$ and for each $\ind{\ell} \in \T$, there exist $\upsilon, \lambda > 0$ such that for all $x \in \X$ and $y \in \Y$ with (i) $\J{x}{y}{\ell} \leq \varpi$ and (ii) $\big\Vert x - \Pi_\X \big[ \x{}{}{} - \gamma_\ell \nabla_x \J{\x{}{}{}}{\y{}{}{}}{\ell} \big] \big\Vert \leq \upsilon$, we have the upper bounds

$\norm{x - \x{*}{}{\ind{\ell}}} \leq \lambda \big\Vert x - \Pi_\X \big[ \x{}{}{} - \nabla_x \J{\x{}{}{}}{\y{}{}{}}{\ell} \big] \big\Vert$

\begin{equation}
\norm{x - \x{*}{}{\ind{\ell}}} \leq \lambda \max\{ 1,\gamma^{-1}_\ell \} \big\Vert x - \Pi_\X \big[ \x{}{}{} -  \gamma_\ell \nabla_x \J{\x{}{}{}}{\y{}{}{}}{\ell} \big] \big\Vert \label{eq:15}
\end{equation}

for all $\gamma_\ell > 0$. $\blacksquare$

Lemma <ref> (in its original form without outputs) holds for a number of problem classes as discussed in <cit.>.

In this article, $\J{\cdot}{\cdot}{\ind{\ell}}$ satisfies the error bound condition for each $\ind{\ell} \in \T$ because it is strongly convex (by Assumption <ref>) and defined over a polyhedral set (by Assumption <ref>),
which is established in [38].
The convergence proofs of this article
therefore use Lemma <ref> and
draw in part on the work in [37], which derives a linear convergence rate for asynchronous projected gradient iterations for a class of time-invariant problems (that are not feedback optimization)

that satisfy Lemma <ref>.

For the time evolution of Problem <ref>, we assume the following.

For all $x \in \X$, $y \in \Y$, and $\ind{\ell} \in \T$, there exist $L_t,\Delta , \sigma_{\ell} > 0$ such that
(i)   ${\big\Vert \x{*}{}{\ind{\ell+1}} - \x{*}{}{\ind{\ell}} \big\Vert \leq \sigma_{\ell+1}}$,
(ii) $\big\vert \J{x}{y}{\ell + 1} - \J{x}{y}{\ell} \big\vert \leq L_t \big\vert \ind{\ell + 1} - \ind{\ell} \big\vert$, and
(iii) ${\big\vert \ind{\ell+1} - \ind{\ell} \big\vert \leq \Delta}$.

The first condition in Assumption <ref>
ensures that successive minimizers
are not arbitrarily far apart.
Without such an assumption it may be impossible for an algorithm to track
time-varying solutions, and therefore we enforce this condition here
to ensure that Problem <ref> is solvable.
The second condition
establishes a Lipschitz continuous-like condition in time.
The last condition in Assumption <ref> simply states that the time between changes in the objective function is bounded.

§ ASYNCHRONOUS UPDATE LAW

In this section we develop the proposed asynchronous algorithm we use to
drive agents' outputs to
track the solution of Problem <ref> over time.
In this section, we use the term “operations" to collectively refer to agents' computations, communications, and output measurements.

§.§ Timescale Separation

The objective in Problem <ref> is indexed by the discrete time index $\ind{\ell}$, and

we index agents' operations over a different discrete time index, namely $k$, because
the timing of agents' operations can differ from the timing of changes
in their objective functions. In fact, [43]
notes that for correction-only algorithms, namely, algorithms that do not predict future objective functions,
some timescale separation is required between the changes in objective functions and the agents'
That is, between the change from $\ind{\ell}$ to $\ind{\ell +1}$ there must be some non-zero number
of ticks of $k$. We consider a correction-only algorithm since it may be difficult to predict
discrete jumps in agents' objective function, and
we therefore assume the following.

In Problem <ref>, for each $\ind{\ell} \in \T$, there are $\kappa_{\ell} \geq 1$ ticks of $k$ when minimizing $\J{\cdot}{\cdot}{\ell}$.

This assumption is one of technical feasibility rather than conveience;
without Assumption <ref>, agents may not be able to track solutions
at all, and this assumption at least makes it possible to track a solution
with bounded error. Such tracking is not guaranteed, and we still must
devise an algorithm and characterize its performance.

We use $\eta_\ell \in \N$ to denote the total number of ticks of $k$ that have elapsed from $t_0$ to the moment  before $\ind{\ell}$ increments to $\ind{\ell + 1}$, i.e.,

\begin{equation} \label{eq:etadef}
\eta_\ell = \sum^{\ell}_{i=0} \kappa_i.
\end{equation}

§.§ Formal Algorithm Statement

We consider a block-based gradient projection algorithm with asynchronous computations, communications, and output measurements to make $x$ and $y$ approximately
track $\big\{\big(x^*(t_{\ell}), y^*(t_{\ell})\big)\big\}_{t_{\ell} \in \T}$.
Each agent updates only a subset of the entries of
the input vector, $x$, and
each agent measures only a subset of the entries of the output vector, $y$.

Over time, each agent locally computes new values for its entries of $x$ and then
communicates these new values and values of $y$ that it has measured
to other agents.

Asynchrony implies that agents receive different information at different times, and thus we expect them to have differing values for network inputs and outputs onboard.
At any time $k$, agent $i$ has a local copy of the network input and output vectors, denoted as $\x{i}{}{k}$ and $\y{i}{}{k}$, respectively.
Due to asynchrony, we allow $\x{i}{}{k} \neq \x{j}{}{k}$ and $\y{i}{}{k} \neq \y{j}{}{k}$ for $j \neq i$. Within the vector $\x{i}{}{k}$, agent $i$ computes new values only for its own sub-vector of inputs, which is $\x{i}{i}{k} \in \R^{n_i}$.
Similarly, within the vector $\y{i}{}{k}$, agent $i$ measures only a sub-vector of outputs, denoted $\y{i}{i}{k} \in \R^{m_i}$.
At any time $k$, agent $i$ has onboard (possibly old) values for agent $j$'s sub-vector of the inputs and outputs, denoted by $\x{i}{j}{k} \in \R^{n_j}$ and $\y{i}{j}{k} \in \R^{m_j}$, respectively.
These values onboard agent $i$ only change when agent $i$ receives
a  communication from agent $j$. In particular, agent $i$ does
not perform any computations on $\x{i}{j}{k}$ and does
not measure $\y{i}{j}{k}$ at any point in time; only agent $j$
does these operations.

At time $k$, if agent $i$ computes an update to $\x{i}{i}{k}$,
then it performs these computations with its onboard
input vector $\x{i}{}{k}$ and onboard output vector $\y{i}{}{k}$
because these are all that it has access to.
As noted in the preceding paragraph, the entries of $\x{i}{j}{k}$ and $\y{i}{j}{k}$ for $j \! \neq \! i$ are obtained by communications from agent $j$, which may be subject to delays. Therefore, agent $i$ may (and often will) compute updates to $\x{i}{i}{k}$ using outdated information from other agents.

To formalize an algorithm statement,
let $\K^i$ be the set of times at which agent $i$ computes an update to $\x{i}{i}{}$. Similarly, let $\M^i$ be the set of times at which agent $i$ takes measurements of $\y{i}{i}{}$.
Let $\C^j_i$ be the set of times at which agent $i$ receives transmission of $\x{i}{j}{}$ and $\y{i}{j}{}$ from agent $j$; due to communication delays, these transmissions can be received at some time after they are sent, and they can be received at different times by different agents.
We emphasize that the sets $\K^i, \ \M^i$, and $\C^j_i$ are only defined to simplify discussion; agents do not know (and do not need to know) $\K^i, \ \M^i$, and $\C^j_i$.

We define $\tau^i_j(k)$ to be the time at which agent $j$ originally computed the value of $\x{i}{j}{k}$ that agent $i$ has onboard at time $k$.
We define $\mu^i_j(k)$ to be the time at which agent $j$ originally measured the value of $\y{i}{j}{k}$ that agent $i$ has onboard at time $k$.
Using this notation, at any time $k$, agent $i$ stores onboard

\begin{align}
\x{i}{}{k} &= \left( \x{1}{1}{\tau^i_1(k)}^T,\dots,\x{i}{i}{k}^T,\dots, \x{N}{N}{\tau^i_N(k)}^T \right)^T  \label{eq:3} \\
\y{i}{}{k} &= \left( \y{1}{1}{\mu^i_1(k)}^T,\dots,\y{i}{i}{k}^T,\dots, \y{N}{N}{\mu^i_N(k)}^T \right)^T. \label{eq:4}
\end{align}

In Section <ref>, we will also analyze the “true” state of the network,

\begin{align}
\x{}{}{k} &= \left( \x{1}{1}{k}^T,\x{2}{2}{k}^T,\dots,\x{N}{N}{k}^T \right)^T \label{eq:85} \\
\y{}{}{k} &= \left( \y{}{1}{k}^T,\y{}{2}{k}^T,\dots,\y{}{N}{k}^T \right)^T, \label{eq:86}
\end{align}

where $\y{}{i}{k} = C_{i*} \x{}{}{k}$. Here $x(k)$ and $y(k)$ contain all of the
most recent values of inputs and outputs; no agent knows these vectors and they
are used only for analysis.

As noted in Remark <ref>, asynchrony causes disturbances in agent $i$'s local copy of $x$ and $y$.
In particular, the disturbances in $x^i(k)$ and $y^i(k)$ are $x^i(k) - x(k)$ and $y^i(k) - y(k)$, respectively.
These disturbances are not known to agent $i$, though
we show in Section <ref> that feedback optimization is robust
to them, despite not having an explicit model for them, and this robustness
is in line with the existing feedback optimization literature [18, 19].

We assume that computation, communication, and measurement delays are bounded, which is called partial asynchrony.

[Partial Asynchrony]
Let $\K^i$ be the set of times at which agent $i$ computes an update to $\x{i}{i}{}$,
and let $\M^i$ be the set of times at which agent $i$ takes measurements of $\y{i}{i}{}$.
Let $\tau^i_j(k)$ be the time at which agent $j$ originally computed the value of $\x{i}{j}{k}$ that agent $i$ has onboard at time $k$,
and let $\mu^i_j(k)$ to be the time at which agent $j$ originally measured the value of $\y{i}{j}{k}$ that agent $i$ has onboard at time $k$.
Then there exists $B \in \N$ such that:

* For every $i \in [N]$ and for every $k\geq0$, at least one of the elements
of the set $\left\{ k,k+1,\dots,k+B-1\right\} $ belongs to $\K^{i}$

* For every $i \in [N]$ and for every $k\geq0$, at least one of the elements
of the set $\left\{ k,k+1,\dots,k+B-1\right\} $ belongs to $\M^{i}$

* It holds that

$\max\left\{ 0,k-B+1\right\} \leq\tau_{j}^{i}\left(k\right)\leq k$

for all $i \in [N]$, $j \in [N]$, and $k\geq0$.

* It holds that

$\max\left\{ 0,k-B+1\right\} \leq\mu_{j}^{i}\left(k\right)\leq k$

for all ${i \in [N]}$, $j \in [N]$, and $k\geq0$. $\lozenge$

Assumptions <ref>.1 and <ref>.2 ensure each agent updates their assigned decision variables and measures their assigned outputs at least once every $B$ time steps. Assumptions <ref>.3 and <ref>.4 ensure that agents communicate those updates and measurements at least once every $B$ time steps.
We will use this assumption to prove that for each $\ind{\ell} \in \T$ our algorithm will
provably make progress toward $\big( \x{*}{}{\ind{\ell}}, \y{*}{}{\ind{\ell}} \big)$ across each
interval of $B$ time steps.
For simplicity, for each $\ind{\ell} \in \T$
we consider $\kappa_\ell = r_\ell B$ for some $r_\ell \in \N_0$.
Furthermore, we adopt the convention that $\kappa_{-1}=0$ and $\eta_{-1}=0$.

Before we propose our distributed algorithm let us calculate the gradient of the objective in the centralized case. The gradient of $\J{x}{y}{\ell}$ with respect to $x$ can be calculated as

\begin{align}
\nabla_{x} \J{x}{y}{\ell} &= \nabla_{x} \left( \f{x}{\ell} + \g{y}{\ell} \right) \\
& = \nabla_{x} \f{x}{\ind{\ell}} + C^{T} \nabla_{y} \g{y}{\ell}, \label{eq:centralGrad}
\end{align}

where the second term in Equation (<ref>) is due to the chain rule.

We seek to develop a distributed
feedback optimization
algorithm that is robust to asynchrony.
It has been shown that gradient-based methods are robust
to asynchrony for static optimization problems [24, 25, 26], and we
therefore we propose the update law

\begin{align}
\x{i}{i}{k+1}= & \begin{cases}
\zeta_i\big(x^i(k), y^i(k)\big) & k\in \K^{i}\\
x_{i}^{i}(k) & k\notin \K^{i}
\end{cases}\label{eq:update}\\
\x{i}{j}{k+1}= & \begin{cases}
\x{j}{j}{\tau_{j}^{i}(k)} & k\in \C_{i}^{j}\\
\x{i}{j}{k} & k\notin \C_{i}^{j},
\end{cases}
\end{align}

\begin{multline} \label{eq:zetai}
\zeta_i\big(x^i(k), y^i(k)\big) \\ = \Pi_{\X_{i}}\Big[\x{i}{i}{k} - \gamma_{\ell}\Big(\nabla_{x_{i}} \f{\x{i}{}{k}}{\ell} + \Ci^{T}\nabla_{y} \g{\y{i}{}{k}}{\ell} \Big)\Big]
\end{multline}

and $\gamma_{\ell} > 0$ is the step size used to minimize $J(\cdot, \cdot; t_{\ell})$.

In addition to agents' computations, we consider the output law

\begin{align}
\y{i}{i}{k+1}= & \begin{cases}
\y{}{i}{k} & k\in \M^{i}\\
\y{i}{i}{k} & k\notin \M^{i}
\end{cases}\\
\y{i}{j}{k+1}= & \begin{cases}
\y{j}{j}{\mu_{j}^{i}(k)} & k\in \C_{i}^{j}\\
\y{i}{j}{k} & k\notin \C_{i}^{j},
\end{cases}
\end{align}

where we define $y_i(k) = C_{i*}x(k)$.

This update law only requires agents to perform computations with
their local copies of the network inputs and outputs.

Algorithm <ref> provides pseudocode for agents' update law, and
the remainder of this paper focuses on analyzing the execution of Algorithm <ref>.

Asynchronous Feedback Optimization Algorithm

$\x{i}{j}{0}$ and $\y{i}{j}{0}$ for all $i,j \in [N]$
$\ind{\ell} \in \T$

$k \in C^{j}_i$
$\x{i}{j}{k+1} = \x{j}{j}{\tau^i_j(k)}$

$\y{i}{j}{k+1} = \y{j}{j}{\mu^i_j(k)}$

$\x{i}{j}{k+1} = \x{i}{j}{k}$

$\y{i}{j}{k+1} = \y{i}{j}{k}$

k $\in \K^{i}$
$\x{i}{i}{k+1} = \zeta_i\big(x^i(k), y^i(k)\big)$

$\x{i}{i}{k+1} = \x{i}{i}{k}$

k $\in \M^{i}$
$\y{i}{i}{k+1} = \y{}{i}{k}$

$\y{i}{i}{k+1} = \y{i}{i}{k}$

§ CONVERGENCE OF ASYNCHRONOUS FEEDBACK OPTIMIZATION ALGORITHM

In this section we prove the approximate convergence of Algorithm <ref>.
First, we establish the following properties of the objective function.
For all $\ind{\ell} \in \T$, from Assumptions <ref>-<ref> both $\nabla_x^2 \f{\cdot}{\ell}$ and $\nabla_y^2 \g{\cdot}{\ell}$ are continuous and
both $\X$ and $\Y$ are compact.
Therefore $\nabla_x \f{\cdot}{\ell}$ and $\nabla_y \g{\cdot}{\ell}$ are Lipschitz on $\X$ and $\Y$, respectively. For each $\ind{\ell} \in \T$, we use $\Lx$ and $\Ly$ to denote upper bounds on $\norm{\nabla_x^2 \f{\cdot}{\ell}}$ and $\norm{\nabla_y^2 \g{\cdot}{\ell}}$ over $\X$ and $\Y$, respectively. These $\Lx$ and $\Ly$ are the Lipschitz constants of $\nabla_x \f{\cdot}{\ell}$ and $\nabla_y \g{\cdot}{\ell}$ over $\X$ and $\Y$, respectively. Thus, for each ${\ind{\ell} \in \T}$, and for all $x_1,x_2 \in \X$ and $y_1,y_2 \in \Y$, we have

\begin{align}
\big\Vert \nabla_x \f{x_1}{\ell} - \nabla_x \f{x_2}{\ell} \big\Vert &\leq \Lx \big\Vert x_1 - x_2 \big\Vert\\
\big\Vert \nabla_y \g{y_1}{\ell} - \nabla_y \g{y_2}{\ell} \big\Vert &\leq \Ly \big\Vert y_1 - y_2 \big\Vert.
\end{align}

By an analogous argument, for all $x \in \X$, $y \in \Y$, and $\ind{\ell} \in \T$, there exist $M_{x,\ell}>0$ and $M_{y,\ell}>0$ such that

\begin{equation} \label{eq:gradbound}
\Vert \nabla_x \f{x}{\ell} \Vert \leq M_{x,\ell} \qquad \textnormal{ and } \qquad
\Vert \nabla_y \g{y}{\ell} \Vert \leq M_{y,\ell}.
\end{equation}

Since $\nabla \J{\cdot}{\cdot}{\ell}$ is continuous over the compact set
$\X \times \Y$, it is bounded on $\X \times \Y$. Thus,
the function $\J{\cdot}{\cdot}{\ell}$ is Lipschitz for each $\ind{\ell} \in \T$,
and there exists a Lipschitz constant ${\Lj > 0}$ such that

$\big\vert\J{x_1}{y_1}{\ell} - \J{x_2}{y_2}{\ell} \big\vert \leq \Lj \norm{ \big(x_1,y_1 \big) - \big(x_2,y_2 \big)}$

for all $x_1, x_2 \in \X$ and $y_1, y_2 \in \Y$.
By a similar argument, continuity of $\nabla_x^2 \J{\cdot}{\cdot}{\ell}$
over $\X \times \Y$ implies that $\nabla_x \J{\cdot}{\cdot}{\ell}$
is Lipchitz, and
for each $\ind{\ell} \in \T$
there exists a Lipschitz constant $\Lt > 0$ such that

$\norm{\nabla_x \J{x_1}{y_1}{\ell} - \nabla_x \J{x_2}{y_2}{\ell}}\leq \Lt \norm{ \big(x_1,y_1 \big) - \big(x_2,y_2 \big)}$

for all $x_1,x_2 \in \X$ and $y_1,y_2 \in \Y$.

To keep track of computations, we define

\begin{align}
\s{i}{k}{\ell} & \coloneqq \begin{cases}
\x{i}{i}{k+1} - \x{i}{i}{k} & k\in \K^{i}\\
0 & k \notin \K^{i}, \label{eq:81}
\end{cases}
\end{align}

and to track output measurements we define $\q{i}{k}$ as

\begin{align}
\q{i}{k} & \coloneqq  \begin{cases}
\y{i}{i}{k+1} - \y{i}{i}{k} & k\in \M^{i}\\
0 & k \notin \M^{i},
\end{cases}
\end{align}

where we note $\y{i}{i}{k+1} - \y{i}{i}{k}=\y{}{i}{k} - \y{}{i}{\mu_i^i(k)}$
for $k \in \M^{i}$.

We concatenate terms in $\s{}{k}{\ell} \coloneqq \big( \s{1}{k}{\ell}^T, \dots, \s{N}{k}{\ell}^T \big)^T \in \R^n$, and  $\q{}{k} \coloneqq \big( \q{1}{k}^T, \dots, \q{N}{k}^T \big)^T \in \R^m$.
We also define the following terms for all $\ind{\ell} \in \T$ and for all $k$ such that $\eta_{\ell -1} \leq k \leq \eta_\ell$:

\begin{align}
\at{k}{\ell} &\coloneqq \J{\x{}{}{k}}{\y{}{}{k}}{\ell} - \J{\x{*}{}{\ind{\ell}}}{\y{*}{}{\ind{\ell}}}{\ell} \\
\bt{k}{\ell} &\coloneqq \sum_{\tau=k-B }^{k-1} \norm{\s{}{\tau}{1}}^2, \qquad \dt{k}{\ell} \coloneqq \sum_{\tau=k-B }^{k-1} \norm{\q{}{\tau}{}}^2. \label{eq:104}
\end{align}

The next theorem establishes a convergence rate for
the first, static objective function that agents minimize.
After that, we will
extend our analysis to a sequence of time-varying objectives
in Theorem <ref>.

Let Assumptions <ref>, <ref>, and <ref> hold.

Then, for fixed $t_0$,
a stepsize $\gamma_0 \in (0,\gamma_{\max,0})$,
iterates $\x{}{}{k}$ and $\y{}{}{k}$ as defined in (<ref>) and (<ref>), and any $r_0 \in \mathbb{N}$, the sequence $\{ \x{}{}{k}, \y{}{}{k} \}_{k \in \N_0}$ generated by $N$ agents executing Algorithm <ref> satisfies

\begin{align}
\at{r_0 B}{0} \leq a_0 \pt{r_0 - 1}{0} \label{eq:t1_alpha} \\
\bt{r_0 B}  &\leq b_0 \pt{r_0 - 1}{0} \label{eq:t1_beta} \\
\dt{r_0 B} &\leq d_0 \pt{r_0-1}{0}, \label{eq:t1_delta}
\end{align}

where $D_0$ and $E_0$ are from $\eqref{eq:bigone_dande}$, $F_0$ is from (<ref>), $G_0$ is from (<ref>),
$\gamma_{\max, 0}$ is from (<ref>), $c_0$, $\rho_0$, $b_0$, and $d_0$ are from (<ref>),

${a_0 \!=\! \max \!\Bigg\{\! L_{J,0} \big( 1 \!+\! \norm{C} \big) \diam(\X),
\!\frac{8 E_0 \Big( \frac{G_0}{F_0} + \frac{E_0}{D_0} \Big) F_0}{D_0} B \diam\left(\X\right)^{2} \!\!\Bigg\}}$

and $b_0 = \frac{D_0}{8 E_0 \Big( \frac{G_0}{F_0} + \frac{E_0}{D_0} \Big) F_0} a_0$.

Proof: See Appendix B. $\blacksquare$

\begin{align}
D_\ell &=  \frac{  2 - \gamma_\ell \big(\big( 1+ B \big) \Lx + \big( 1 + B N  \big) \norm{C}^2 \Ly \big) }{2}, \qquad\qquad  E_\ell =   N B \frac{ \Lx + \Ly N \norm{C}^2}{2} \label{eq:bigone_dande} \\
F_\ell &= \frac{1}{2}
\bigg((1 + \lambda^2) \Big[ 36 B^3 \Vert C \Vert^6 L_\ell^2 L_{y,\ell}^2 N^2 m
+ 72 B^3 \Vert C \Vert^4 L_\ell^2 L_{x,\ell} L_{y,\ell} N^2 m
+ 36 B L_\ell^2 L_{x,\ell}^2 N^2
+ 36 B^3 \Vert C \Vert^2 L_\ell^2 L_{x,\ell}^2 N^2 m \\
&+ 36 B \Vert C \Vert^4 L_\ell^2 L_{y,\ell}^2 N^2
+ 18 \Vert C \Vert^2 L_{x,\ell} L_{y,\ell} N
+ 72 B \Vert C \Vert^2 L_\ell^2 L_{x,\ell} L_{y,\ell} N^2
+ 9 \Vert C \Vert^4 L_{y,\ell}^2 N\Big]
+ 3 B^2 \Vert C \Vert^6 L_\ell^2 L_{y,\ell}^2 N^2 m \\
&+ \Vert C \Vert^4
\big[72 B^3  L_\ell^2 L_{y,\ell} N^2 m
+ 6 B^2 L_\ell^2 L_{x,\ell} L_{y,\ell} N^2 m
+ 6 B^2 L_\ell^2 L_{y,\ell} N^2 m
+ 3 L_\ell^2 L_{y,\ell}^2 N^2
+ 3 B^2 L_{y,\ell}^2 N m\big] \\
&+ \Vert C \Vert^2 \Big[ 96 B^3  L_\ell^2 N^2 m
+ 72 B^3  L_\ell^2 L_{x,\ell} N^2 m
+ 72 B  L_\ell^2 L_{y,\ell} N^2
+ 60 B^3  L_\ell^2 N^2  \lambda^2 m
+ 18  L_{y,\ell} N
+ 8 B^2  L_\ell^2 N^2 m  \\
&+ 6 B^2  L_\ell^2 L_{x,\ell} N^2 m
+ 6  L_\ell^2 L_{x,\ell} L_{y,\ell} N^2
+ 6  L_\ell^2 L_{y,\ell} N^2
+ 3 B^2  L_\ell^2 L_{x,\ell}^2 N^2 m \Big]
+ 3 L_\ell^2 L_{x,\ell}^2 N^2
+ 96 B L_\ell^2 N^2
+ 6 L_\ell^2 L_{x,\ell} N^2  \\
&+ 8 L_\ell^2 N^2
+ 60 B L_\ell^2 N^2  \lambda^2
+ 72 B L_\ell^2 L_{x,\ell} N^2
+ 12 L_{x,\ell}^2 N
+ 9 L_{x,\ell}^2 N  \lambda^2
+ 18 L_{x,\ell} N
+ 15 N  \lambda^2
+ 24 N
+ 2 \bigg) \label{eq:bigone_f} \\
G_\ell &= \frac{N}{2}
\bigg( (1 + \lambda^2) \Big[
72 B^3 \Vert C \Vert^4 L_\ell^2 L_{x,\ell} L_{y,\ell} N m
+ 72 B \Vert C \Vert^2 L_\ell^2 L_{x,\ell} L_{y,\ell} N
+ 36 B^3 \Vert C \Vert^6 L_\ell^2 L_{y,\ell}^2 N m
+ 36 B^3 \Vert C \Vert^2 L_\ell^2 L_{x,\ell}^2 N m \\
&+ 36 B \Vert C \Vert^4 L_\ell^2 L_{y,\ell}^2 N
+ 36 B L_\ell^2 L_{x,\ell}^2 N
\Big]
+ 3 B^2 \Vert C \Vert^6 L_\ell^2 L_{y,\ell}^2 N m
+ \Vert C \Vert^4 \Big[
72 B^3  L_\ell^2 L_{y,\ell} N m
+ 6 B^2  L_\ell^2 L_{x,\ell} L_{y,\ell} N m \\
+ 6 B^2  L_\ell^2 L_{y,\ell} N m
+ 3 B^2  L_{y,\ell}^2 m
+ 3  L_\ell^2 L_{y,\ell}^2 N \Big]
+ \Vert C \Vert^2 \Big[
96 B^3  L_\ell^2 N m
+ 72 B^3  L_\ell^2 L_{x,\ell} N m
+ 72 B  L_\ell^2 L_{y,\ell} N
+ 60 B^3  L_\ell^2 N  \lambda^2 m \\
&+ 8 B^2  L_\ell^2 N m
+ 6 B^2  L_\ell^2 L_{x,\ell} N m
+ 6  L_\ell^2 L_{x,\ell} L_{y,\ell} N
+ 6  L_\ell^2 L_{y,\ell} N
+ 3 B^2  L_\ell^2 L_{x,\ell}^2 N m
+ B  L_{y,\ell} N  \Big]
+ 96 B L_\ell^2 N
+ 72 B L_\ell^2 L_{x,\ell} N \\
&+ 60 B L_\ell^2 N  \lambda^2
+ 8 L_\ell^2 N
+ 6 L_\ell^2 L_{x,\ell} N
+ 3 L_{x,\ell}^2
+ 3 L_\ell^2 L_{x,\ell}^2 N
+ B L_{x,\ell}
\bigg) \label{eq:bigone_g} \\
a_\ell &= a_{\ell-1} \pt{r_{\ell-1} -1}{\ell-1} \!\!+ 2 \Delta L_t \!+\! L_{J,\ell} \sigma_{\ell} \big( 1 \!+\! \big\Vert C \big\Vert \big) \big(  M_{x,\ell} \!+\!  M_{y,\ell} \Vert C \Vert \big)  B \diam\left( \X \right) + \frac{8 E_\ell\left(\frac{G_\ell}{F_\ell} \!+\! \frac{E_\ell}{D_\ell}\right) F_\ell B^2 \diam \left(\X\right)^{2} \big( L_{x,\ell} \!+\! L_{y,\ell} \Vert C \Vert^2  \big)}{2 D_\ell} \label{eq:bigone_a} \\
\gamma_{\max,\ell} &= \min \bigg\{\frac{2}{\big( 3N+1 \big) B \Lx + \big( 3N^2+1 \big) B \norm{C}^2 \Ly}, \frac{2}{\big( 1+ B \big) \Lx + \big( 1 +B N \big) \norm{C}^2 \Ly},
\frac{D_{\ell}}{E_{\ell}},
\bigg(\frac{G_{\ell}}{F_{\ell}} + \frac{E_{\ell}}{D_{\ell}} \bigg)^{-1},
\frac{1}{2c_\ell}, \\
&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\frac{D_{\ell}}{8 F_{\ell} \Big( \frac{G_{\ell}}{F_{\ell}} + \frac{E_{\ell}}{D_{\ell}} \Big) c_\ell},
\frac{ \frac{a_\ell}{b_\ell} + 2E_\ell + D_{\ell} c_\ell - \sqrt{\big( \frac{a_\ell}{b_\ell} + 2E_\ell + D_{\ell} c_\ell \big)^2 - 4 D_{\ell} E_{\ell} c_\ell}}{2 E_{\ell} c_\ell},
\frac{1}{2} \bigg\}, \label{eq:bigone_gmax} \\
c_\ell &= \frac{D_\ell}{2 F_\ell + 2 D_\ell} \in \left(0,\frac{1}{2} \right), \qquad \pt{}{\ell} = 1 - \gamma_\ell c_\ell \in (0,1), \qquad b_\ell = B \diam \left(\X\right)^{2}, \qquad d_\ell = B^2 m \norm{C}^2  b_{\ell}, \label{eq:bigone_candrhoandbandd}
\end{align}

Theorem <ref> generalizes standard linear convergence results using asynchronous projected gradient descent on functions that satisfy the error bound condition in [37] to time-invariant feedback optimization problems that satisfy the same error bound condition.

Theorem <ref> establishes
that linear convergence is attained for static feedback optimization problems,
though the constants and overall convergence rate are different from
those in the static case.
That is, linear convergence carries over from conventional optimization
to static feedback optimization.
To the best of our knowledge this is the first convergence result for time-invariant feedback optimization problems where agents' computations,
communications, and state measurements
are subject to asynchrony.

Motivated by Theorem <ref>, we next
present a convergence result
Algorithm <ref> for time-varying feedback optimization problems.

Let Assumptions <ref>-<ref> hold.
Fix $T \in \N$ and fix ${\T = \left\{ \ind{0},\dots, \ind{T} \right\}}$.
Suppose that $\frac{2}{B(L_{x,\ell} + L_{y,\ell}\|C\|^2)} \leq 1$.
Then, for all $\ind{\ell} \in \T$, a stepsize $\gamma_\ell \in (0,\gamma_{\max,\ell})$,
iterates $\x{}{}{k}$ and $\y{}{}{k}$ as defined in (<ref>) and (<ref>), the sequence $\{ \x{}{}{k}, \y{}{}{k} \}_{k \in \N_0}$ generated by $N$ agents executing Algorithm <ref> satisfies

\begin{multline}
\at{\eta_{\ell-1} + r_\ell B}{\ell} \leq {a_{\ell} \pt{r_{\ell} - 1}{\ell}},
\bt{\eta_{\ell-1} + r_\ell B}{}     \leq b_{\ell} \pt{r_{\ell} - 1}{\ell}, \\
\dt{\eta_{\ell-1} + r_\ell B}{}     \leq d_{\ell} \pt{r_{\ell}-1}{\ell},
\end{multline}

where $\eta_{\ell}$ is from (<ref>), $D_{\ell}$ and $E_{\ell}$ are from $\eqref{eq:bigone_dande}$, $F_{\ell}$ is from (<ref>), $G_{\ell}$ is from (<ref>), $a_{\ell}$ is from (<ref>),
$\gamma_{\max, \ell}$ is from (<ref>),
and $c_{\ell}$, $\rho_{\ell}$, $b_{\ell}$, and $d_{\ell}$ are from (<ref>).

Proof: See Appendix C. $\blacksquare$

Theorem <ref> shows
that the iterates of Algorithm <ref> track solutions
to time-varying feedback optimization problems to within
an error ball.
We bound errors at time $\eta_{\ell-1} + r_{\ell}B$ because
this is the last tick of agents' iteration counter $k$
before $t_{\ell}$ increments to $t_{\ell+1}$.
Thus, for each $t_{\ell} \in \T$,
Theorem <ref> bounds errors
after agents have made all of the progress that
they are going to make towards $\big(x^*(t_{\ell}), y^*(t_{\ell})\big)$.

Although the results in Theorems <ref> and <ref>
bear some superficial resemblance, the meanings of
these results
differ substantially.
Specifically, Theorem <ref> bounds $\alpha$ using $a_{\ell}$,
which is defined in (<ref>), where it
can be seen that $a_{\ell}$ depends on $a_{\ell-1}$.
Through this recursive dependence, we see that $a_{\ell}$ depends on $a_{\ell-1}, a_{\ell-2}, \ldots, a_0$.
Similarly, the value of $a_{\ell}$ depends
on $\rho_{\ell-1}, \ldots, \rho_0$, which encode convergence
rates attained for past objective functions,
and also depends on $r_{\ell-1}, \ldots, r_0$, which account
for the numbers of agents' computations, communications, and sensor
measurements executed for past objectives. The remaining terms
in the definition of $a_{\ell}$ in (<ref>) account
for how $J(\cdot, \cdot; t_{\ell})$ has changed over time.
Thus, Theorem <ref> presents a bound that must quantify
the effects of the entire time history of
Algorithm <ref> so far, including all
operations completed by all agents, and the timing
and magnitude of changes in agents' objective function.
Conversely, Theorem <ref> is about a single static
objective and hence has no dependence on the past.

Theorem <ref> addresses an open problem identified
in the literature, namely the problem in
Remark 3 in [34], because,
in the setting of feedback optimization,
we account for agents exhibiting different computational capabilities by allowing asynchronous computations, communications,
and output measurements.
That is, agents with different abilities to compute, communicate, and sense may execute these operations at different rates and different
times, and Theorem <ref> analyzes their convergence.

The bounds in Theorem <ref> show that if $r_{\ell} = 1$ for all $\ell$,
then agents may not make any progress towards a solution in the sense
that $\alpha$, $\beta$, and $\delta$ may not get smaller.
This occurs
because agents' objective is time-varying. Specifically, due to delays
in agents' communications, as agents minimize one cost, say $J(\cdot, \cdot; t_{\ell})$,
agent $i$ may send $x^i_i(k)$ and $y^i_i(k)$ to other agents. Before that
message is received by other agents, the cost may change to $J(\cdot, \cdot; t_{\ell+1})$.
Then, if agent $i$'s message is received by other agents after this change in cost,
those agents receive iterates that do not help it minimize $J(\cdot, \cdot; t_{\ell+1})$.
It can take up to $B$ timesteps for all outdated iterates to be received,
and the value $r_{\ell} = 1$ means that agents only minimize $J(\cdot, \cdot; t_{\ell})$
for $B$ timesteps total. It is therefore possible to communicate only
older iterates during that time, and thus
the value $r_{\ell} = 1$ means that progress towards a minimizer is not guaranteed.

Theorem <ref> analyzes convergence for
agents operating over a fixed time horizon. One may also
ask what performance to expect if Algorithm <ref>
were run indefinitely over an unbounded time horizon.
To answer this,
we next present an asymptotic tracking error result for infinite horizon time-varying feedback optimization problems,
and, in light of Remark <ref>, we consider $r_{\ell} \geq 2$ for this result.

Let Assumptions <ref>-<ref> hold. Let

\begin{multline}
V_\ell \coloneqq 2 \Delta L_t + L_{J,\ell} \sigma_\ell \big( 1+ \Vert C \Vert \big) + \big( M_{x,\ell} + M_{y,\ell} \Vert C \Vert \big) B \diam \big( \X \big) \\
+ \frac{8 E_\ell\left(\frac{G_\ell}{F_\ell} + \frac{E_\ell}{D_\ell}\right) F_\ell B^2 \diam \left(\X\right)^{2}}{2 D_\ell} \big( L_{x,\ell} + L_{y,\ell} \Vert C \Vert^2  \big),
\end{multline}

\begin{equation}
V_\infty \coloneqq \max \bigg\{ a_0, \underset{\ell \geq 0}{\sup} \ V_\ell \bigg\}, \qquad
\rho_\infty \coloneqq \underset{\ell \geq 0}{\sup} \ \rho_\ell \in (0,1).
\end{equation}

Then, the sequence $\{ \x{}{}{k}, \y{}{}{k} \}_{k \in \N_0}$ generated by $N$ agents executing Algorithm <ref> with ${r_\ell \geq 2}$ for all $\ind{\ell} \geq 0$ satisfies

\begin{align} \label{eq:t3bound}
\underset{\ell \rightarrow \infty}{\limsup} \ \at{\eta_\ell}{\ell} \leq V_\infty \frac{\pt{}{\infty}}{1-\pt{}{\infty}},
\end{align}

where $\eta_{\ell}$ is from (<ref>).

Proof: For any $\eta_\ell$ where $\ell \geq 0$, Theorem <ref> gives us
the upper bound

$\at{\eta_\ell}{\ell} \leq a_0 \prod^\ell_{\theta=0} \pt{r_\theta - 1}{\theta} + \sum^\ell_{\tau=1} V_\tau \prod^\ell_{\psi=\tau} \pt{r_\psi - 1}{\psi}$.

Then, using $V_\tau \leq V_\infty$, $\pt{}{\tau} \leq \pt{}{\infty}$ for all $\tau \geq 0$,

and the fact that $r_\ell \geq 2$ for all $\ind{\ell} \in \N$ results in

${\at{\eta_\ell}{\ell} \leq V_\infty \bigg( \prod^\ell_{\theta=0} \pt{}{\infty} + \sum^\ell_{\tau=1} \pt{\tau}{\infty} \bigg)}$.

For $\ell \rightarrow \infty$, using $\sum^\infty_{k=1} \nu^k = \frac{\nu}{1-\nu}$ for $\vert \nu \vert < 1$ gives the result. $\blacksquare$

Theorem <ref> shows that agents' long-run performance
can be bounded using certain worst-case constants,
namely $V_{\infty}$ and $\rho_{\infty}$.
In particular,
suppose for some fixed $t_{\ell}$ that agents
make little to no progress towards
the minimizer of $J(\cdot, \cdot; t_{\ell})$.
This can be captured mathematically through
larger values of $V_{\infty}$ and $\rho_{\infty}$.
Then Theorem <ref> reveals that
this lack of progress for a single objective
may negatively impact long-term performance
by making $V_{\infty}$ and $\rho_{\infty}$ larger.
Conversely, consistently high performance (in the sense
of agents making significant progress towards
the minimizer of $J(\cdot, \cdot; t_{\ell})$ for each $t_{\ell}$)
produces long-term high performance in a predictable, quantifiable
way by ensuring that both $V_{\infty}$ and $\rho_{\infty}$ are smaller.

Bounds similar to (<ref>) appear  in [9, 34] for certain centralized and decentralized discrete-time correction-only time-varying
optimization methods. Thus,
Theorem <ref> shows that we can obtain similar asymptotic
tracking performance when considering a more general problem formulation that allows asynchrony in agents' computations, communications,
and sensor measurements.  $\blacklozenge$

In some cases, networks are able to complete their operations with predictable timing. For example, agents may complete their operations at certain frequencies dependent upon onboard computation and communication hardware. In these situations, it can be of interest to design or select certain
specifications, e.g., computational hardware or a network topology, such that the network yields some desired performance.
For such cases, we next
provide bounds on the number of operations agents must execute
to attain a certain cost.

Let Assumptions <ref>-<ref> hold and let $\phi > 0$.
Fix $T \in \N$ and fix $\T = \{t_0, \ldots, t_T\}$.
Suppose $N$ agents are executing Algorithm <ref> with $r_\ell \equiv r$ for all $\ind{\ell} \in \T$ and $r \in \N$ with $r \geq 2$. Let

$V_{\max} = \max \big\{ a_0, \underset{\ind{\ell} \in \T}{\max} V_\ell \big\}$
$\rho_{\max} \coloneqq \underset{\ind{\ell} \in \T}{\max} \ \rho_\ell \in (0,1)$.

\begin{align}
r \geq 1 +
\frac{ \ln \Big( \frac{V_{\max} \rho_{\max}^{(T+2)(r-1)} + \phi }{V_{\max} +\phi} \Big)}{\ln (\rho_{\max})},
\end{align}

then $\at{\eta_\ell}{\ell} \leq \phi$ for all $\ind{\ell} \in \T$, where $\eta_{\ell}$ is from (<ref>).

Proof: For any $\eta_\ell$ where $\ell \geq 0$, Theorem <ref> gives us
the bound

$\at{\eta_\ell}{\ell} \leq a_0 \prod^\ell_{\theta=0} \pt{r_\theta - 1}{\theta} + \sum^\ell_{\tau=1} V_\tau \prod^\ell_{\psi=\tau} \pt{r_\psi - 1}{\psi}$.

Setting $r_{\tau}=r$ for all $\tau \geq 0$, and using the facts $V_\tau \leq V_{\max}$ and $\pt{}{\tau} \leq \pt{}{\max}$ for all $\tau \geq 0$ we can derive the upper bound

$\at{\eta_\ell}{\ell} \leq V_{\max} \pt{r-1}{\max} \sum^\ell_{\tau=0} \pt{\tau(r-1)}{\max}$.

To upper bound $\at{\eta_\ell}{\ell}$ by $\phi$ it is sufficient to have

$V_{\max} \pt{r-1}{\max} \sum^\ell_{\tau=0} \pt{\tau(r-1)}{\max} \leq \phi$.

From the fact that $\sum^{n-1}_{m=0} aq^{mc}=a\frac{q^{cn}-1}{q^c - 1}$ when $q < 1$,
boundedness by $\phi$ holds if and only if

$V_{\max} \pt{r-1}{\max} \frac{\pt{(\ell+1)(r-1)}{\max}-1}{\pt{r-1}{\max} - 1} \leq \phi$.

Setting $\ell = T$ maximizes the left-hand side. Solving for $r$
completes the proof.

Theorem <ref> quantifies agents' performance based on how many operations they complete,
and Theorem <ref> essentially inverts this analysis to determine how many operations
agents must execute to attain a desired level of performance. Theorem <ref>
is for the finite-horizon case, and next we extend it to the asymptotic case.

Let Assumptions <ref>-<ref> hold and let $\phi > 0$. Suppose $N$ agents execute Algorithm <ref> with $r_\ell \equiv r$
for all $\ind{\ell} \geq 0$ and $r \in \N$ with $r \geq 2$.
Consider the constants $V_{\infty}$ and $\rho_{\infty}$ from Theorem <ref>.

$r \geq 1 + \frac{ \ln \Big( \frac{\phi}{V_\infty + \phi} \Big)}{\ln (\rho_{\infty})}$,

then $\at{\eta_\ell}{\ell} \leq \phi$ for all $\ind{\ell} \geq 0$.

Proof: In Theorem <ref>, use $\lim_{T \to \infty} q_{\infty}^{\left(T+2\right)c} = 0$. $\blacksquare$

Both Theorem <ref> Corollary <ref> relate
agents' desired performance bound (in $\phi$),
the time-varying nature of the problem (through $V_{\ell}$), and
agents' rate of convergence (through $\rho_{\ell}$) to quantify how
the rate at which they complete their operations
(codified in $r$) affects long-term performance. We next explore
related questions numerically.

We proved that our algorithm can achieve a linear convergence rate for all $\ind{\ell} \in \T$ while considering asynchronous updates, measurements, and communications. Furthermore, this result extends previously derived results in feedback optimization to asynchronous settings. Specifically, this result addresses Remark 3 in [34] in that we account for agents exhibiting different computational capabilities by allowing asynchronous operations.

§ NUMERICAL RESULTS

In this section we consider two examples using Algorithm <ref>.
The first is a time-varying quadratic program utilizing feedback, and
the second is a network of aircraft modeled with F-16XL dynamics.

§.§ Time-Varying Quadratic Program with Feedback

We consider $N=10$ agents executing Algorithm <ref> as the objective changes. The problem takes the form

\begin{align}
\underset{x\in \X}{\textnormal{minimize}} & \ \frac{1}{2} x^T Q(\ind\ell) x + q(\ind\ell)^T x + \frac{1}{2} y^T P(\ind\ell) y  + p(\ind\ell)^T y\\
\textnormal{subject to} & \ y=Cx,
\end{align}

where ${Q(\ind\ell) \succ 0 \in \R^{20 \times 20}}$, ${P(\ind\ell) \succ 0 \in \R^{10 \times 10}}$, ${q(\ind\ell) \in \R^{20}}$, ${p(\ind\ell) \in \R^{10}}$, and  ${C \in \R^{10 \times 20}}$ are randomly generated. We use the
set $\X = [-10,10]^{20}$.
The objective function changes every $1,000$ iterations of $k$.
Each agent is assigned to update two entries of $x$,
measure one entry of $y$, and communicate with other agents.
At each $k$, agent $i$ computes an update with probability $p_{i,u}(k) = 0.01$, measures its output with probability $p_{i,m}(k) = 0.01$, and communicates with probability $p_{i,c}(k) = 0.01$.
The stepsize $\gamma_\ell = 0.001$ was used for all $\ind{\ell} \in \T$, and we set $B = 5$.
In Figures <ref> and <ref>, Algorithm <ref>
operates on the “Iterations $(k)$”
timescale (bottom axes), while the objective function
changes on the “Time Index $(\ind{\ell})$” timescale (top axes).

In Figure <ref>,
the increases in error are due to the changes in the objective function.
Moreover, we observe that the values of $\at{k}{\ell},\bt{k}{}$, and $\dt{k}{}$ trend toward zero between changes in the objective function
for all $\ind{\ell} \in \T$, which agrees
with the result of Theorem <ref>.

We demonstrate the effects of the maximum delay length $B$ in Figure <ref>. As the value of $B$ decreases, the agents are able to track the minimizers more closely at each time index $\ind{\ell}$. Intuitively,
as $B$ shrinks, we expect Algorithm <ref> to approach a synchronous
feedback optimization algorithm, from which
we expect better tracking performance,
which we indeed see in Figure <ref>.

Plot of $\at{k}{\ell}$, $\bt{k}{}$, and $\dt{k}{}$ as a function of $k$
and $\ind{\ell} \in \T$ for ${N=10}$ agents executing Algorithm <ref>
with $B=5$.
We see that $\alpha$, $\beta$, and $\delta$ abruptly increase when agents'
objective function changes, then gradually decrease between these changes
as agents complete more computations, communications,
and sensor readings, which agrees with Theorem <ref>.

A plot of $\at{k}{\ell}$ as a function of $k$
and $\ind{\ell} \in \T$ for ${N=10}$ agents executing Algorithm <ref>
differing values of $B$. As $B$ shrinks, Algorithm <ref>
more closely approximates a synchronous algorithm, and convergence
to a minimizer occurs faster, which
agrees with Theorem <ref>.

§.§ Aircraft Altitude Tracking

In this section, Algorithm <ref> is implemented on a network of $N=8$ F16-XL aircraft to: (1) track a time-varying desired altitude denoted by $\Phi(\ind{\ell}) \in \R$,
(2) maintain a specified altitude separation $\omega_i \in \R$ for all ${i \in [N]}$, and (3) track a time-varying desired acceleration denoted by $\Psi_i (\ind{\ell}) \in \R$ for all $i \in [N]$.
This goal is representative of tracking a target with an a priori unknown trajectory while maintaining safe levels of acceleration for the aircraft and avoiding inter-agent collisions.
The state vector of agent $i$ is denoted ${x_i = \big[ v_i, \vartheta_i, \varphi_i, \dot{\varphi}_i, \xi_i \big]^T \in \R^5}$
for all $i \in [N]$, where $\xi_i \in \R$ is the
altitude, $v_i \in \R$ is the velocity, $\vartheta_i \in \R$ is
the angle of attack, $\varphi_i \in \R$ is the pitch,
and $\dot{\varphi}_i \in \R$ is the pitch rate.
Furthermore, we consider $y_i = \big[ \dot{v}_i, \xi_i \big]^T$ as
the outputs for all $i \in [N]$, where $\dot{v}_i \in \R$ is the acceleration of the aircraft.

By linearizing the aircraft longitudinal dynamics [44]
about the operating point ${\bar{x} = \big[ 500 \textnormal{ ft/s}, 0\degree, 0\degree, 0\degree/s, 15,000 \textnormal{ ft} \big]^T \in \R^5}$ we formulated the  input-output relationship $ y_i = C_i x_i$, where

\begin{align}   C_i &= \begin{bmatrix}
-0.0133 &-7.3259 &-3.17 &-1.1965 &0.0001 \\
0& 0& 0& 0& 1
\end{bmatrix}.
\end{align}

We denote the actual altitude separation
between aircraft as ${\tilde{\xi}=[\xi_1 - \xi_2, \dots, \xi_i - \xi_{i+1}, \dots, \xi_7 - \xi_8]^T \in \R^7}$ and the desired separation vector $\omega = [\omega_1,\dots,\omega_7]^T \in \R^7$.
We stack the aircraft states and outputs into the vectors $x=(x_1^T,\dots,x_8^T)^T \in \R^{40}$ and $y=(y_1^T,\dots,y_8^T)^T \in \R^{16}$, respectively, to compactly write the network-wide output model as $y = C x$. Here, $C\in \R^{16 \times 40}$ is a block diagonal matrix with $C_i$ on its diagonal for all $i \in [N]$. Lastly, we stack the desired outputs in a vector $\Theta (\ind{\ell}) = [\Phi(\ind{\ell}), \Psi_1(\ind{\ell}),\dots, \Phi(\ind{\ell}), \Psi_8(\ind{\ell}) ] \in \R^{16}$.
Agents attempt to satisfy the three goals of this section by tracking the solution of
the following problem:

\begin{align} \label{prob:planes}
\!\!\!\!\!\!\! \underset{x\in \X}{\textnormal{minimize}} \ \! \J{x}{y}{\ell} & \!\! \coloneqq \!\!\! \ \frac{1}{2} x^T Q x + \! \frac{1}{2} (y - \Theta(\ind{\ell}))^T \! P (y - \Theta(\ind{\ell}))\\
& \qquad\qquad\qquad\qquad + \frac{1}{2} (\tilde{\xi} - \omega)^T R (\tilde{\xi} - \omega) \\
\textnormal{subject to} & \quad \ y = Cx,
\end{align}

where $Q= 100 \cdot I_{40}\in\R^{40 \times 40}$, $P=  I_8 \otimes \big[ 10^3 \ 0; 0 \ 5\times 10^4 \big]  \in\R^{16 \times 16}$, and $R=10^6 \cdot I_{7} \in\R^{7\times7}$.
We designed the desired altitude as ${\Phi(\ind{\ell}) = 15000 + 1500 \sin \big( \frac{\ind{\ell}\cdot t_s \cdot \pi}{24} \big) \textnormal{ft}}$,  where $t_s = 5s$ is the sampling time for the desired altitude, and desired separation as $\omega_i = 1500 \textnormal{ft}$ for all $i \in [N]$.

The desired accelerations for each agent are updated according to $\Psi_i(\ind{\ell}) = \frac{0.1}{t_s} \big( \Phi(\ind{\ell}) - \frac{1}{N} \sum_{j=1}^N \xi_j^i (\eta_\ell)  \big)$.
In this example, desired outputs are updated every 500 iterations of $k$ and they are updated $20$ times.
We define $x_{\max} = [556.2664 \text{ ft/s}, 1.5\degree, 25 \degree, 60 \degree / s,40,000 \text{ ft}]$ and $x_{\min} = [443.7336 \text{ ft/s}, -13 \degree, -25 \degree, -60 \degree / s, 1000 \text{ ft}]$ so that we have $\X_i = \{ x \in \R^5 \mid x_{\min,j} \leq x_j \leq x_{\max,j},  j=1,\dots,5 \}$ for all $i \in [8]$. This yields $\X = \X_1 \times \dots \times \X_8$.
Agent $i$ computes an update to $x^i_i(k)$ with probability $p_{i,u}(k)=0.5$, measures $y^i_i(k)$ with probability $p_{i,m}(k) =0.5$, and communicates its desired state and measured altitude with probability $p_{i,c}(k) = 0.5$.
The maximum delay is $B=50$.

Figure <ref> shows the optimal altitudes of each agent along with the actual agent altitudes as agents track the solution of (<ref>). Note that the optimal altitudes are not equal to the desired altitude $\Psi(\ind{\ell})$ because we include the altitude separation term $\omega$ in the objective function. Even under a high degree of asynchrony (i.e., large $B$)
we observe that the agents are able to track the optimal altitudes closely.
Figure <ref> shows the agents' actual accelerations alongside the optimal accelerations. As with altitudes, agents are able to track the optimal accelerations,
even under asynchrony.
We show the errors between the optimal and actual altitudes and accelerations in Figure <ref>.

Plot of the optimal agent altitudes (red) and the actual agent altitudes (blue) produced by agents executing Algorithm <ref>. As agents complete more operations their actual altitudes approach the optimal altitudes for all $\ind{\ell} \in \T$.

Plot of the optimal agent accelerations (red) and the actual agent accelerations (blue) produced by agents executing Algorithm <ref>. Similar to Figure <ref> agents' accelerations track the optimal accelerations
better as agents complete more operations, which is intuitive.

Plot of the error between the optimal outputs and actual outputs. Specifically, at $k=3999$, the altitude error is equal to $850.7 ft$ and the acceleration error is $2.30 ft/s^2$. These values
are the errors that result both from the time-varying nature of the agents'
problem and the asynchrony in their operations.

§ CONCLUSION

We presented a decentralized asynchronous algorithm for tracking the solution of
feedback optimization problems, and we derived tracking error bounds for a
class of problems.
This work extended the feedback optimization concept to distributed problems
with asynchrony, and it showed the viability of feedback optimization
as a means to provide robustness to disturbances that result from asynchrony.
Future work will explore
analogous results for problems with more complex
observation maps and problems in which agents asynchronously
sample an objective function.

§.§ Technical Lemmas

This section provides lemmas used
in Appendices <ref> and <ref>.

If ${f:\R^n \rightarrow \R}$ is continuously differentiable and has the property ${\Vert \nabla f(x) - \nabla f(y) \Vert \leq K \Vert x-y \Vert}$ for every ${x,y \in \R^n}$, then

$f\left(x+y\right) \leq f\left(x\right)+y^{T}\nabla f\left(x\right)+\frac{K}{2}\left\Vert y\right\Vert^{2}$. $\blacksquare$

For all $\ind{\ell} \in \T$, all $i \in [N]$, and all $k \geq 0$ we have the bound

$\s{i}{k}{\ell}^T \nabla_{\x{}{i}{}} \J{\x{i}{}{k}}{\y{i}{}{k}}{\ell} \leq  -\frac{1}{\gamma_\ell} \norm{\s{i}{k}{\ell}}^2$.

Proof: For $v \in \X \subset \R^n$, $x \in \R^n \backslash \X$, and $z=\Pi_\X \left[x\right]$, a property of orthogonal
projections [45] is $0 \geq (z-x)^T(z-v)$.
Define ${z \coloneqq \Pi_{\X_i}\big[ \x{i}{i}{k} - \gamma_\ell \nabla_{\x{}{i}{}} \J{\x{i}{}{k}}{\y{i}{}{k}}{\ell}\big]}$. Then
we find that

$0 \geq \big(z - \big( \x{i}{i}{k} - \gamma_\ell \nabla_{\x{}{i}{}} \J{\x{i}{}{k}}{\y{i}{}{k}}{\ell} \big) \big)^T\big(z-\x{i}{i}{k} \big)$.

Expanding the inner product and combining like terms then gives us

$0 \geq \norm{z-\x{i}{i}{k}}^2
+ \big( z - \x{i}{i}{k} \big)^T \gamma_\ell \nabla_{\x{}{i}{}} \J{\x{i}{}{k}}{\y{i}{}{k}}{\ell}$.

Using $\s{i}{k}{\ell} = z - \x{i}{i}{k}$
and rearranging completes the proof. $\blacksquare$

For all $\ind{\ell} \in \T$, all $i \in [N]$, and all $k \geq 0$, we have
$\norm{ \x{i}{}{k} - \x{}{}{k} } \leq \sum^{k-1}_{\tau = k - B} \norm{\s{}{\tau}{\ell}}$. $\blacksquare$

For all $\ind{\ell} \in \T$, all $i \in [N]$, and all $k \geq 0$, we have

$\norm{\y{i}{}{k} - \y{}{}{k}} \leq N \norm{C} \sum^{k-1}_{\tau = k-B} \norm{\s{}{\tau}{\ell}}$.

Proof: We define $\s{}{\tau}{0}=0$ for $\tau<0$. For any ${i\in [N]}$,

the triangle inequality gives

$\norm{\y{}{}{k} - \y{i}{}{k}}  \leq \sum^N_{j=1} \Vert \y{}{j}{k} - \y{j}{j}{\mu^i_j(k)} \Vert$.

Using ${\y{}{j}{k} = C_{j*} \x{}{}{k}}$ and $\y{j}{j}{\mu^i_j(k)}=C_{j*} \x{}{}{\mu^i_j(k)}$, where  ${C_{j*} \in \R^{m_j \times n}}$, we then
find the upper bound

${\norm{\y{}{}{k} - \y{i}{}{k}} \leq \sum^N_{j=1} \big\Vert C_{j*} \x{}{}{k} - C_{j*} \x{}{}{\mu^i_j(k)} \big\Vert}$.

From $\norm{AB} \leq \norm{A} \norm{B}$ and the fact that $\norm{C_{j*}} \leq \norm{C}$ for all $j$, we have

$\norm{\y{}{}{k} - \y{i}{}{k}} \leq \norm{C} \sum^N_{j=1} \Vert \sum^{k-1}_{\tau = \mu^i_j(k)} \s{}{\tau}{\ell} \Vert$.

By partial asynchrony $k-B \leq \mu^i_j(k)$, and using this and the triangle inequality gives

$\norm{\y{}{}{k} - \y{i}{}{k}}  \leq \norm{C} \sum^N_{j=1} \sum^{k-1}_{\tau = k-B} \norm{\s{}{\tau}{\ell}}$. $\blacksquare$

For all $\ind{\ell} \in \T$ and $k \in \{\eta_{\ell-1}, \ldots, \eta_{\ell}-B\}$, we have

\begin{multline}
\J{\x{}{}{k+B}}{\y{}{}{k+B}}{\ell} - \J{\x{}{}{k}}{\y{}{}{k}}{\ell} \leq  \\
- \left( \frac{  2 - \gamma_{\ell} \big((1 + B) \Lx + (1 + B N) \norm{C}^2 \Ly \big) }{2 \gamma_{\ell}} \right)
\!\sum^{k+B-1}_{\tau = k} \! \big\Vert \s{}{\tau}{\ell} \big\Vert^2
\\ +  N B \frac{\Lx+\Ly N \norm{C}^2}{2} \sum^{k-1}_{\tau = k - B} \big\Vert \s{}{\tau}{\ell} \big\Vert^2.
\end{multline}

Proof: We first bound $\f{\x{}{}{k+1}}{\ell} - \f{\x{}{}{k}}{\ell}$.
By definition, $\f{\x{}{}{k+1}}{\ell} = \f{\x{}{}{k} + \s{}{k}{\ell}}{\ell}$.
Then, by Lemma <ref>,

${\f{\x{}{}{k\!+\!1}}{\ell} \!\leq\! \f{\x{}{}{k}}{\ell}
\!+\! \s{}{k}{\ell}^T \nabla_{\x{}{}{}} \f{\x{}{}{k}}{\ell}
\!+\! \frac{\Lx}{2} \norm{\s{}{k}{\ell}}^2}$.

Expressing the inner product as a sum,

adding $\nabla_{\x{}{i}{}} \f{\x{i}{}{k}}{\ell} - \nabla_{\x{}{i}{}} \f{\x{i}{}{k}}{\ell}$ inside
the sum, and rearranging, we find

\begin{multline}
\f{\x{}{}{k+1}}{\ell}  \leq \f{\x{}{}{k}}{\ell}
+ \sum^N_{i=1}\s{i}{k}{\ell}^T  \nabla_{\x{}{i}{}} \f{\x{i}{}{k}}{\ell} \\
+ \sum^N_{i=1}\s{i}{k}{\ell}^T \big(\nabla_{\x{}{i}{}} \f{\x{}{}{k}}{\ell} - \nabla_{\x{}{i}{}} \f{\x{i}{}{k}}{\ell}\big)
+ \frac{\Lx}{2} \norm{\s{}{k}{\ell}}^2.
\end{multline}

In the second sum, we apply the Cauchy-Schwarz inequality,
the Lipschitz property of $\nabla_{\x{}{}{}} \f{\cdot}{\ell}$, and
the result of Lemma <ref> to find

\begin{multline}
\f{\x{}{}{k+1}}{\ell}  \leq \f{\x{}{}{k}}{\ell}
+ \sum^N_{i=1}\s{i}{k}{\ell}^T  \nabla_{\x{}{i}{}} \f{\x{i}{}{k}}{\ell} \\
+ \Lx \sum^N_{i=1} \big\Vert \s{i}{k}{\ell} \big\Vert \sum^{k-1}_{\tau = k - B} \big\Vert \s{}{\tau}{\ell} \big\Vert
+ \frac{\Lx}{2} \norm{\s{}{k}{\ell}}^2.
\end{multline}

Using ${\big\Vert \s{i}{k}{\ell} \big\Vert \cdot \big\Vert \s{}{\tau}{\ell} \big\Vert  \leq  \frac{1}{2} \big( \big\Vert \s{i}{k}{\ell} \big\Vert^2 + \big\Vert \s{}{\tau}{\ell} \big\Vert^2} \big)$

\begin{multline} \label{eq:fDescent}
\f{\x{}{}{k+1}}{\ell}  \leq \f{\x{}{}{k}}{\ell} + \sum^N_{i=1}\s{i}{k}{\ell}^T  \nabla_{\x{}{i}{}} \f{\x{i}{}{k}}{\ell} \\
\!\!\!\!+ \frac{\Lx}{2} \Bigg( B \norm{\s{}{k}{\ell}}^2
+ N \sum^{k-1}_{\tau = k - B} \big\Vert \s{}{\tau}{\ell} \big\Vert^2 \Bigg)
+ \frac{\Lx}{2} \norm{\s{}{k}{\ell}}^2.
\end{multline}

Next, we can bound $\g{\y{}{}{k+1}}{\ell} - \g{\y{}{}{k}}{\ell}$
using the same steps with Lemma <ref> in place of Lemma <ref>.
This leads to

\begin{multline} \label{eq:gDescent}
\g{\y{}{}{k+1}}{\ell} \leq  \g{\y{}{}{k}}{\ell}
+ \sum^N_{i=1} \s{i}{k}{\ell} ^T \Ci^T \nabla_{\y{}{}{}} \g{\y{i}{}{k}}{\ell} \\
+ \frac{\Ly N \norm{C}^2}{2} \Bigg( \! B \|s(k)\|^2
+ N \!\!\!\! \sum^{k-1}_{\tau = k - B} \!\!\! \Vert s(\tau) \Vert^2 \! \Bigg)
+ \frac{\Ly \norm{C}^2}{2} \norm{s(k)}^2.
\end{multline}

Adding (<ref>) and (<ref>)
and applying Lemma <ref> gives

\begin{multline}
\J{\x{}{}{k+1}}{\y{}{}{k+1}}{\ell} - \J{\x{}{}{k}}{\y{}{}{k}}{\ell} \leq \\
\Bigg( {-\frac{1}{\gamma_{\ell}}} + \frac{\Lx + \Ly \norm{C}^2}{2}  + B\frac{ \Lx + \Ly N \norm{C}^2}{2} \Bigg)  \norm{\s{}{k}{\ell}}^2 \\
+  N \frac{\Lx+\Ly N \norm{C}^2}{2} \sum^{k-1}_{\tau = k - B} \big\Vert \s{}{\tau}{\ell} \big\Vert^2.
\end{multline}

We apply this to $k, k+1, \dots, k+B - 1$ and sum to conclude.

Define $\chi(\gamma_{\ell}) = 2\gamma_\ell \big( 1+\gamma_\ell \big) \Lt^2 B N$.
For each $\ind{\ell} \in \T$ and all $k \in \{\eta_{\ell-1}, \ldots, \eta_{\ell}-B\}$ we have

\begin{multline}
\big\Vert \x{}{}{k+1} - \x{}{}{k} \big\Vert^2
\leq
\frac{ 1 + \chi(\gamma_{\ell})}{1-\gamma_\ell}  \sum_{\tau=k}^{k+B-1} \Vert \s{}{\tau}{\ell} \Vert^2 \\
+ \frac{\chi(\gamma_{\ell})}{1-\gamma_\ell}
\left(\sum_{\tau=k}^{k+B-1} \Vert \q{}{\tau} \Vert^2 + \!\!\sum_{\tau=k-B}^{k-1} \Big(\Vert \s{}{\tau}{\ell} \Vert^2
+ \Vert \q{}{\tau} \Vert^2\Big) \right).
%& + \frac{2\gamma_\ell \big( 1+\gamma_\ell \big) \Lt^2 B N}{1-\gamma_\ell}  \sum_{\tau=k-B}^{k-1} \Vert \s{}{\tau}{\ell} \Vert^2 \\
%+ \frac{2\gamma_\ell \big( 1+\gamma_\ell \big) \Lt^2 B N}{1-\gamma_\ell}  \sum_{\tau=k-B}^{k-1} \Vert \q{}{\tau} \Vert^2.
\end{multline}

Proof: Fix some $k\in\left\{ \eta_{\ell-1},\dots,\eta_{\ell}\right\}$.
For each $i\in[N]$ let $k^{i}$ be the smallest
element of $\K^{i}$ that exceeds $k$. Then, for each $i \in [N]$,

\begin{align}
\!\!\!\!\!\!\!\!\!\!\x{i}{i}{k^i} \!&=\! \x{i}{i}{k} \label{eq:1} \\
%\y{}{i}{k^i} &= \y{}{i}{k} \\
\!\!\!\!\!\!\!\!\!\!\s{i}{k^i}{\ell} \!&=\! \Pi_{\X_i} \!\Big[ \x{i}{i}{k^i} \!-\! \gamma_\ell \nabla_{\x{}{i}{}} \J{\x{i}{}{k^i}}{\y{i}{}{k^i}}{\ell}  \Big] \!-\! \x{i}{i}{k^i}. \label{eq:2}
\end{align}

Using the triangle inequality and
the non-expansive property of the projection operator we have

\begin{align}
&\big\Vert \Pi_{\X_i} \big[ \x{i}{i}{k} - \gamma_\ell \nabla_{\x{}{i}{}} \J{\x{}{}{k}}{\y{}{}{k}}{\ell} \big] - \x{i}{i}{k} \big\Vert
\leq \\
& \gamma_\ell \big\Vert \nabla_{\x{}{i}{}} \J{\x{}{}{k}}{\y{}{}{k}}{\ell} - \nabla_{\x{}{i}{}} \J{\x{i}{}{k^i}}{\y{i}{}{k^i}}{\ell}  \big\Vert \\
&+  \big\Vert \Pi_{\X_i} \big[ \x{i}{i}{k} - \gamma_\ell \nabla_{\x{}{i}{}} \J{\x{i}{}{k^i}}{\y{i}{}{k^i}}{\ell} \big] - \x{i}{i}{k} \big\Vert.
\end{align}

Subtracting the $\gamma_\ell$ term from both sides and using (<ref>) and (<ref>) gives

\begin{align}
&\big\Vert \s{i}{k^i}{\ell} \big\Vert \geq \big\Vert \Pi_{\X_i} \big[ \x{i}{i}{k} - \gamma_\ell \nabla_{\x{}{i}{}} \J{\x{}{}{k}}{\y{}{}{k}}{\ell} - \x{i}{i}{k} \big] \big\Vert \\
& - \gamma_\ell \big\Vert \nabla_{\x{}{i}{}} \J{\x{}{}{k}}{\y{}{}{k}}{\ell} - \nabla_{\x{}{i}{}} \J{\x{i}{}{k^i}}{\y{i}{}{k^i}}{\ell}  \big\Vert.
\end{align}

Using the Lipschitz property of $\nabla_x \J{\cdot}{\cdot}{\ell}$

and using $(a-\gamma b)^2 \geq (1-\gamma)a^2 - \gamma (1+\gamma)b^2$ on the right-hand side then gives us

\begin{multline} \label{eq:6}
\big\Vert \s{i}{k^i}{\ell} \big\Vert^2 \geq - \gamma_\ell \big( 1+\gamma_\ell \big) \Lt^2 \big\Vert \big( \x{}{}{k}, \y{}{}{k}\big) - \big( \x{i}{}{k^i},\y{i}{}{k^i} \big) \big\Vert^2
\\ \big(1-\gamma_\ell \big)\big\Vert \Pi_{\X_i} \big[ \x{i}{i}{k}
- \gamma_\ell \nabla_{\x{}{i}{}} \J{\x{}{}{k}}{\y{}{}{k}}{\ell}  \big] - \x{i}{i}{k} \big\Vert^2.
\end{multline}

By definition, $k\leq k^i \leq k+B-1$. By partial asynchronism, we also have $k-B \leq \tau^i_j(k^i) \leq k+B-1$ and $k-B \leq \mu^i_j(k^i) \leq k+B-1$.
Then, for all $j$,

\begin{align}
\Bigg\Vert \begin{bmatrix}
\x{j}{j}{k} \\ \y{}{j}{k}
\end{bmatrix} - \begin{bmatrix}
\x{j}{j}{\tau^i_j(k^i)} \\ \y{j}{j}{\mu^i_j(k^i)}
\end{bmatrix} \Bigg\Vert^2 \leq \Bigg( \sum_{\tau=k-B}^{k+B-1} \Bigg\Vert \begin{bmatrix}
\s{j}{\tau}{\ell} \\
\q{j}{\tau}
\end{bmatrix} \Bigg\Vert   \Bigg)^2.
\end{align}

Using the inequality $(a_1+\dots+a_{2B})^2 \leq 2B (a_1^2 + \dots + a_{2B}^2)$,
summing over all $j \in [N]$, and using (<ref>) and (<ref>)
then gives

\begin{align} \label{eq:5}
\Bigg\Vert \begin{bmatrix}
\x{}{}{k} \\ \y{}{}{k}
\end{bmatrix} - \begin{bmatrix}
\x{i}{}{k^i} \\ \y{i}{}{k^i}
\end{bmatrix} \Bigg\Vert^2 \leq 2B \sum_{\tau=k-B}^{k+B-1} \Bigg\Vert \begin{bmatrix}
\s{}{\tau}{\ell} \\
\q{}{\tau}
\end{bmatrix} \Bigg\Vert^2.
\end{align}

Applying (<ref>) to (<ref>) gives

\begin{multline} \label{eq:7}
\big\Vert \s{i}{k^i}{\ell} \big\Vert^2 \geq - 2\gamma_\ell \big( 1+\gamma_\ell \big) \Lt^2 B \sum_{\tau=k-B}^{k+B-1} \Bigg\Vert \begin{bmatrix}
\s{}{\tau}{\ell} \\
\q{}{\tau}
\end{bmatrix} \Bigg\Vert^2 + \\
\!\!\!\!\big(1\!-\!\gamma_\ell \big)\big\Vert \Pi_{\X_i} \big[ \x{i}{i}{k}
- \gamma_\ell \nabla_{\x{}{i}{}} \!\J{\x{}{}{k}}{\y{}{}{k}}{\ell}  \big] \!-\! \x{i}{i}{k} \big\Vert^2.
\end{multline}

Next, we sum the left-hand side over $i \in [N]$ to find

\begin{equation} \label{eq:RHSbound}
\sum^N_{i=1} \big\Vert \s{i}{k^i}{\ell} \big\Vert^2 \leq \sum^N_{i=1} \sum^{k+B-1}_{\tau=k} \big\Vert \s{i}{\tau}{\ell} \big\Vert^2 = \sum^{k+B-1}_{\tau=k} \big\Vert \s{}{\tau}{\ell} \big\Vert^2.
\end{equation}

Summing over $i \in [N]$ in (<ref>) and applying (<ref>) gives

\begin{multline}
\sum^{k+B-1}_{\tau=k} \big\Vert \s{}{\tau}{\ell} \big\Vert^2 \geq \big(1-\gamma_\ell \big)\big\Vert \x{}{}{k+1} - \x{}{}{k} \big\Vert^2 \\
{-2}\gamma_\ell \big( 1+\gamma_\ell \big) \Lt^2 B N \sum_{\tau=k-B}^{k+B-1} \Bigg\Vert \begin{bmatrix}
\s{}{\tau}{\ell} \\
\q{}{\tau}
\end{bmatrix} \Bigg\Vert^2.
\end{multline}

The result follows by

taking ${\gamma_\ell \in (0,1)}$, and dividing by $1-\gamma_\ell$. $\blacksquare$

Define $K_{\ell} = \Lx + \Ly\|C\|^2$.
For all $\ind{\ell} \in \T $, ${x \in \R^n}$, $y \in \R^m$, $\bar{x}\in\X$ with $\bar{y} = C \bar{x}\in\Y$,
${\x{1}{}{},\dots,\x{N}{}{} \in \R^n}$, and $\y{1}{}{},\dots,\y{N}{}{} \in \R^m$, we have

\begin{multline}
\J{a}{b}{\ell}-\J{\bar{x}}{\bar{y}}{\ell} \leq \\
\bigg( N  \bigg( \frac{3}{2} \Big( K_{\ell} + \frac{1}{\gamma_\ell} \Big)^2 + \frac{5}{2} \bigg)\gamma^2_\ell \Lt^2 + \frac{3}{2} \Lx^2 \bigg) \sum^N_{j=1} \norm{x - \x{j}{}{}}^2 \\ + \bigg( N \bigg( \frac{3}{2} \Big( K_{\ell} + \frac{1}{\gamma_\ell} \Big)^2 + \frac{5}{2} \bigg)\gamma^2_\ell \Lt^2 + \frac{3}{2} \Ly^2 \norm{C}^2 \bigg) \sum^N_{j=1} \norm{ y - \y{j}{}{}}^2    \\
+ N \bigg( \frac{3}{2} \Big( K_{\ell} + \frac{1}{\gamma_\ell} \Big)^2 + \frac{5}{2} \bigg) \norm{\bar{a} - x}^2
+ N \bigg( \frac{3}{2} \Big( K_{\ell} \Big)^2  +\frac{5}{2} \bigg) \norm{\bar{x} - x}^2,
\end{multline}

where $\bar{a}\coloneqq \Pi_{\X}\big[x - \gamma_\ell \nabla_x \J{x}{y}{\ell} \big]$ and $a$ is a vector with components $a_i \coloneqq \Pi_{\X_i} \big[ \x{}{i}{} - \gamma_\ell \nabla_{\x{}{i}{}} \J{\x{i}{}{}}{\y{i}{}{}}{\ell} \big]$
for all $i \in [N]$, along with $\bar{b} = C\bar{a}$ and $b=Ca$.

Proof: For each $i \in [N]$, since we define $a_i$ to be the orthogonal projection of $\x{}{i}{} - \gamma_\ell \nabla_{\x{}{i}{}} \J{\x{i}{}{}}{\y{i}{}{}}{\ell}$ onto $\X_i$ and $\bar{x}_i \in \X_i$, we have

$0 \leq \big\langle a_i - \bar{x}_i, \x{}{i}{} - \gamma_\ell \nabla_{\x{}{i}{}} \J{\x{i}{}{}}{\y{i}{}{}}{\ell} - a_i \big\rangle$,

or, equivalently,

\begin{equation} \label{eq:8}
\!\!\!\!0 \!\leq\! \big\langle a_i \!-\! \bar{x}_i,  -\nabla_{\x{}{i}{}} \f{\x{i}{}{}}{\ell} \!-\! \Ci^T \nabla_y \g{\y{i}{}{}}{\ell}
\!+\! \frac{1}{\gamma_\ell} ( \x{}{i}{} - a_i ) \big\rangle.
\end{equation}

The definition of $\J{\cdot}{\cdot}{\ell}$ gives

$\J{a}{b}{\ell}-\J{\bar{x}}{\bar{y}}{\ell} = \f{a}{\ell} - \f{\bar{x}}{\ell} + \g{b}{\ell} - \g{\bar{y}}{\ell}$.

By the Mean Value Theorem there exists a point $(\phi,\nu)$ between $(a,b)$ and $(\bar{x},\bar{y})$ such that

\begin{equation}
\J{a}{b}{\ell}-\J{\bar{x}}{\bar{y}}{\ell} = \big\langle a-\bar{x}, \nabla_x \f{\phi}{\ell} \big\rangle
+ \big\langle b-\bar{y}, \nabla_y \g{\nu}{\ell} \big\rangle.
\end{equation}

Using $\bar{y}=C\bar{x}$ and $b=Ca$ and simplifying we have

\begin{equation}
\!\!\J{a}{b}{\ell} - \J{\bar{x}}{\bar{y}}{\ell} \!=\!\! \sum^N_{i=1} \! \big\langle a_i-\bar{x}_i, \!\nabla_{x_i} \f{\phi}{\ell} + \Ci^T\!\nabla_y \g{\nu}{\ell}\!\big\rangle .
\end{equation}

Using (<ref>) we add $-\Big( \nabla_{\x{}{i}{}} \f{\x{i}{}{}}{\ell} + \Ci^T \nabla_y \g{\y{i}{}{}}{\ell} \Big) + \frac{1}{\gamma_\ell} ( \x{}{i}{} - a_i )$ inside the second argument of the inner product. Then

\begin{multline}
\J{a}{b}{\ell}-\J{\bar{x}}{\bar{y}}{\ell} \leq \sum^N_{i=1} \Vert a_i-\bar{x}_i \Vert \cdot \Big\Vert \nabla_{\x{}{i}{}} \f{\phi}{\ell} \\
+ \Ci^T\nabla_y \g{\nu}{\ell}
-\nabla_{\x{}{i}{}} \f{\x{i}{}{}}{\ell} - \Ci^T \nabla_y \g{\y{i}{}{}}{\ell}
+ \frac{1}{\gamma_\ell} ( \x{}{i}{} - a_i ) \Big\Vert.
\end{multline}

Using the triangle inequality, $\norm{\Ci} \leq \norm{C}$,

the Lipschitz property of $\nabla_x \f{\cdot}{\ell}$ and $\nabla_y \g{\cdot}{\ell}$, and

$\big\Vert \nabla_{\x{}{i}{}} \f{\phi}{\ell} -\nabla_{\x{}{i}{}} \f{\x{i}{}{}}{\ell} \big\Vert \leq \big\Vert \nabla_{x} \f{\phi}{\ell} -\nabla_{x} \f{\x{i}{}{}}{\ell} \big\Vert$ for all $i \in [N]$, we find

\begin{multline}
\J{a}{b}{\ell}-\J{\bar{x}}{\bar{y}}{\ell} \leq \sum^N_{i=1} \Vert a_i-\bar{x}_i \Vert \cdot \Big( \Lx \Vert \phi - \x{i}{}{} \Vert \\
+ \Ly \norm{C} \Vert \nu - \y{i}{}{} \Vert + \frac{1}{\gamma_\ell} \big\Vert \x{}{i}{} - a_i \big\Vert  \Big).
\end{multline}

We have both ${\Vert a_i-\bar{x}_i \Vert \leq \Vert a-\bar{x} \Vert}$ and ${\big\Vert \x{}{i}{} - a_i \big\Vert \leq \big\Vert x - a \big\Vert}$
for all $i \in [N]$,
which give us

\begin{multline}
\J{a}{b}{\ell}-\J{\bar{x}}{\bar{y}}{\ell} \leq \sum^N_{i=1} \Vert a -\bar{x} \Vert \cdot \Big( \Lx \Vert \phi - \x{i}{}{} \Vert \\
+ \Ly \norm{C} \Vert \nu - \y{i}{}{} \Vert + \frac{1}{\gamma_\ell} \big\Vert x - a \big\Vert  \Big). \label{eq:11}
\end{multline}

We continue by bounding terms on the right-hand side of (<ref>) separately. Since $\phi$
lies between
the points $a$ and $\bar{x}$, we have
${\Vert \phi - x \Vert \leq \Vert a - x \Vert + \norm{\bar{x} - x}}$ for all $x \in \R^n$.

\begin{align}
\Vert \phi - \x{i}{}{} \Vert & = \Vert \phi - x + x - \x{i}{}{} \Vert \leq \Vert \phi - x \Vert + \norm{x - \x{i}{}{}} \\
&\leq \Vert a - x \Vert + \norm{\bar{x} - x} + \norm{x - \x{i}{}{}}. \label{eq:9}
\end{align}

Similar reasoning gives

\begin{align}
\Vert \nu - \x{i}{}{} \Vert %& = \Vert \nu - y + y - \y{i}{}{} \Vert \leq \Vert \nu - y \Vert + \norm{y - \y{i}{}{}} \\
&\leq \Vert b - y \Vert + \Vert \bar{y} - y \Vert + \norm{y - \y{i}{}{}}. \label{eq:10}
\end{align}

Applying (<ref>) and (<ref>) to (<ref>),
substituting in $b=Ca$, $y=Cx$, and $\bar{y}=C\bar{x}$, and
combining like terms, we find

\begin{multline}
\J{a}{b}{\ell}-\J{\bar{x}}{\bar{y}}{\ell} \leq \sum^N_{i=1} \Vert a -\bar{x} \Vert \cdot \\
\Big( \big( \Lx + \Ly \norm{C}^2 + \frac{1}{\gamma_\ell} \big)  \Vert a - x \Vert
+ \big( \Lx + \Ly \norm{C}^2 \big) \norm{\bar{x} - x} \\
+ \Lx\norm{x - \x{i}{}{}}
+ \Ly \norm{C}\norm{y - \y{i}{}{}}
\Big).
\end{multline}

By adding zero and using the triangle inequality we reach

\begin{multline}
\J{a}{b}{\ell}-\J{\bar{x}}{\bar{y}}{\ell} \leq  \sum^N_{i=1} \Big( \norm{a - \bar{a}} + \norm{\bar{a} - x} + \norm{x -\bar{x}} \Big) \\
\cdot \bigg(( \Lx + \Ly \norm{C}^2) \norm{\bar{x} - x} + \Lx\norm{x - \x{i}{}{}} + \Ly \norm{C}\norm{y - \y{i}{}{}}  + \\
\Big( \Lx + \Ly \norm{C}^2 + \frac{1}{\gamma_\ell} \Big) ( \norm{a - \bar{a}} + \norm{\bar{a} - x})\bigg).
\end{multline}

Expanding, using $ab\leq\frac{1}{2}\left(a^{2}+b^{2}\right)$, and simplifying,
we get

\begin{multline}
\J{a}{b}{\ell}-\J{\bar{x}}{\bar{y}}{\ell} \leq \\
N \bigg( \frac{3}{2} \Big( \Lx + \Ly \norm{C}^2 + \frac{1}{\gamma_\ell} \Big)^2 + \frac{5}{2} \bigg)
\Big( \norm{a - \bar{a}}^2 + \norm{\bar{a} - x}^2  \Big) \\
+ N \bigg( \frac{3}{2} \Big( \Lx + \Ly \norm{C}^2 \Big)^2
+ \frac{5}{2} \bigg) \norm{\bar{x} - x}^2 \\
+  \frac{3}{2} \Lx^2 \sum^N_{i=1} \norm{x - \x{i}{}{}}^2
+ \frac{3}{2} \Ly^2 \norm{C}^2  \sum^N_{i=1} \norm{y - \y{i}{}{}}^2. \label{eq:13}
\end{multline}

We bound $\norm{a - \bar{a}}^2$ by plugging
in the definitions of $a$ and $\bar{a}$ and
using the non-expansive property of the projection operator to find

\norm{a - \bar{a}}^2 %&= \sum^N_{j=1} \ \norm{a_j - \bar{a}_j}^2 \\
%& = \sum^N_{j=1} \ \norm{ \Pi_{\X_j} \big[ \x{}{j}{} - \gamma_\ell \nabla_{\x{}{j}{}} \J{\x{j}{}{}}{\y{j}{}{}}{\ell} \big] \\
%&- \Pi_{\X_j}\big[\x{}{j}{} - \gamma_\ell \nabla_{\x{}{j}{}} \J{x}{y}{\ell} \big]}^2 \\
\leq \sum^N_{j=1} \ \gamma^2_\ell \norm{ \nabla_{\x{}{j}{}} \J{x}{y}{\ell} - \nabla_{\x{}{j}{}} \J{\x{j}{}{}}{\y{j}{}{}}{\ell}}^2.

Using the fact that for all $j \in [N]$ we have

$\big\Vert \nabla_{\x{}{j}{}} \J{x}{y}{\ell} - \nabla_{\x{}{j}{}} \J{\x{j}{}{}}{\y{j}{}{}}{\ell} \big\Vert \leq \big\Vert \nabla_{x} \J{x}{y}{\ell} - \nabla_{x} \J{\x{j}{x}{}}{\y{j}{}{}}{\ell} \big\Vert$

and the Lipschitz property of $\nabla_{x} \J{\cdot}{\cdot}{\ell}$, we then reach the upper bound

\norm{a - \bar{a}}^2 \leq \gamma^2_\ell \Lt^2  \sum^N_{j=1} \ \norm{ \big(x,y\big) - \big(\x{j}{}{},\y{j}{}{}\big)}^2.

The result follows by applying this to (<ref>),
using $\norm{ \big(x,y\big) - \big(\x{j}{}{},\y{j}{}{}\big)}^2 = \norm{ x - \x{j}{}{}}^2 + \norm{ y - \y{j}{}{}}^2$, and combining like terms. $\blacksquare$

For all $\ind{\ell} \in \T$ and for all $k \geq 0$, we have

${\dt{k}{\ell} \leq B^2 m \norm{C}^2  \bt{k}{\ell}}$.

Suppose agent $i$ measures its output at time $k$ and
suppose that its most recent prior measurement was taken at time $\mu^i_i(k)$.
Then $\y{i}{i}{k} =  \y{}{i}{\mu^i_i(k)}$. We know that ${\y{}{i}{k}= C_{i*} x(k)}$,

and thus

$\y{}{i}{k} - \y{}{i}{\mu^i_i(k)} = C_{i*} \x{}{}{k} - C_{i*} \x{}{}{\mu^i_i(k)}$.

Taking the norm squared of both sides and using $\norm{C_{i*}}^2 \leq \norm{C}^2$
leads to the bound

$\norm{\y{}{i}{k} - \y{}{i}{\mu^i_i(k)}}^2 %&\leq \norm{C}^2 \sum_{j=1}^N \ \norm{\x{}{j}{k} - \x{}{j}{\mu^i_i(k)}}^2 \\
\leq \norm{C}^2 \sum_{j=1}^N \ \Big\Vert \sum^{k-1}_{\tau = \mu^i_i(k)} \s{j}{\tau}{\ell} \Big\Vert^2$.

Using the triangle inequality and $ \Big( \sum^N_{i=1} z_i \Big)^2 \leq N \sum^N_{i=1} z_i^2$  next gives us the bound

$\norm{\y{}{i}{k} - \y{}{i}{\mu^i_i(k)}}^2 \leq \norm{C}^2 \sum_{j=1}^N \ \big( k-\mu^i_i(k) \big) \sum^{k-1}_{\tau = \mu^i_i(k)} \norm{\s{j}{\tau}{\ell}}^2$.

By partial asynchrony $k-\mu^i_i(k) \leq B$ and $k-B \leq \mu^i_i(k)$, and thus

$\norm{\y{}{i}{k} - \y{}{i}{\mu^i_i(k)}}^2 \leq \norm{C}^2 B \sum_{j=1}^N \  \sum^{k-1}_{\tau = k-B} \norm{\s{}{\tau}{\ell}}^2$,

where we have used $\sum^N_{j=1}\norm{\s{j}{\tau}{\ell}}^2 = \norm{\s{}{\tau}{\ell}}^2$.

By definition of $\bt{k}{\ell}$ and $\q{j}{k}$ we can rewrite this as

$\norm{\q{j}{k}}^2 \leq \norm{C}^2 B \bt{k}{\ell}$.

Taking the sum over the $m$ outputs on both sides we arrive at

$\sum^{m}_{j=1} \ \norm{\q{j}{\tau}}^2 = \|q(\tau)\|^2 \leq m \norm{C}^2 B \bt{\tau}{\ell}$.

The result follows by taking the sum from $\tau = k-B$ to $\tau = k-1$ on both sides. $\blacksquare$

Take $\gamma_{\ell} \in (0, 1)$ for all $\ell\geq 0$.
For all $ \ind{\ell} \in\T$ and $k \in \{\eta_{\ell-1}, \ldots, \eta_\ell - B\}$ we have

\begin{multline}
\J{\x{}{}{k+B}}{\y{}{}{k+B}}{\ell} - \J{\x{*}{}{\ind{\ell}}}{\y{*}{}{\ind{\ell}}}{\ell} \leq \\
\big( A_1+A_3+A_6 \big( A_2+A_4 \big) + 1 \big) \sum^{k+B-1}_{\tau = k} \  \norm{\s{}{\tau}{\ell}}^2 \\
+ \big( A_1+A_4+A_5+A_6 \big( A_2+A_4 \big) \big) \sum^{k-1}_{\tau = k-B} \  \norm{\s{}{\tau}{\ell}}^2,
\end{multline}

where we define the constants $A_1 = N^2M_{\ell}\gamma^2_\ell \Lt^2 + \frac{3}{2} N \Lx^2$
and $A_2 = N^2M_{\ell}\gamma^2_\ell \Lt^2 + \frac{3}{2} N \Ly^2 \norm{C}^2$,
in addition to

\begin{align}
A_3 &= NM_{\ell} + N \bigg( \frac{3}{2} K_{\ell}^2 +\frac{5}{2} \bigg) \frac{\lambda^2}{\gamma_{\ell}^2}  \cdot \frac{ 1 + 2\gamma_\ell \big( 1+\gamma_\ell \big) \Lt^2 B N}{1-\gamma_\ell} \\
A_4 &=  N M_{\ell} + N \bigg( \frac{3}{2} K_{\ell}^2  +\frac{5}{2} \bigg) \frac{\lambda^2}{\gamma_{\ell}^2} \cdot \frac{2\gamma_\ell \big( 1+\gamma_\ell \big) \Lt^2 B N}{1-\gamma_\ell} \\
A_5 &= N B \frac{\Lx + \Ly N \norm{C}^2}{2} \\
K_{\ell} &= \Lx + \Ly\|C\|^2, \, M_{\ell} = \frac{3}{2}\left(K_{\ell} + \frac{1}{\gamma_{\ell}}\right)^2 + \frac{5}{2}.
\end{align}

Fix any $k \geq 0$. For each $i$, let $k^i$ denote the smallest element of $K^i$ exceeding $k$. Then we can write the equation

$\x{i}{i}{k^i+1} = \Pi_{\X_i} \big[ \x{i}{i}{k} - \gamma_\ell \nabla_{\x{}{i}{}} \J{\x{i}{}{k^i}}{\y{i}{}{k^i}}{\ell}  \big]$.

Next we
apply Lemma <ref> with $x=\x{}{}{k}$, $x^i=\x{i}{}{k^i}$ for ${i \in [N]}$, $y=\y{}{}{k}$, $y^i=\y{i}{}{k^i}$ for ${i \in [N]}$, ${\bar{x}=\x{*}{}{\ind{\ell}}}$, ${\bar{y}=\y{*}{}{\ind{\ell}}=C\x{*}{}{\ind{\ell}}}$,
$a \in \R^n$ with $a_i = \x{i}{i}{k^i+1}$ for $i \in [N]$, $b = Ca$
$\bar{a}(k)=\Pi_{\X} \big[ \x{}{}{k} - \gamma_\ell \nabla_{x} \J{\x{}{}{k}}{\y{}{}{k}}{\ell}  \big]$.

\begin{multline}
\J{a}{b}{\ell}-\J{\x{*}{}{\ind{\ell}}}{\y{*}{}{\ind{\ell}}}{\ell} \leq \\
\bigg( N M_{\ell}\gamma^2_\ell \Lt^2 + \frac{3}{2} \Lx^2 \bigg) \sum^N_{i=1} \  \norm{x(k) - \x{i}{}{k^i}}^2 \\
+ \bigg(NM_{\ell}\gamma^2_\ell \Lt^2 + \frac{3}{2} \Ly^2 \norm{C}^2 \bigg) \sum^N_{i=1} \norm{ y(k) - \y{i}{}{k^i}}^2 \\
+ N \bigg( \frac{3}{2} M_{\ell} + \frac{5}{2} \bigg) \norm{\bar{a}(k) - x(k)}^2
+ N \bigg( \frac{3}{2} K_{\ell}^2 + \frac{5}{2} \bigg) \norm{\x{*}{}{\ind{\ell}} - x(k)}^2.
\end{multline}

Applying Lemma <ref>, using $0 < \gamma_\ell < 1$, and simplifying gives

\begin{multline} \label{eq:new41}
\J{a}{b}{\ell}-\J{\x{*}{}{\ind{\ell}}}{\y{*}{}{\ind{\ell}}}{\ell} \leq \\
\bigg( NM_{\ell}\gamma^2_\ell \Lt^2 + \frac{3}{2} \Lx^2 \bigg) \sum^N_{i=1} \  \norm{x(k) - \x{i}{}{k^i}}^2 \\
+ \bigg(NM_{\ell}\gamma^2_\ell \Lt^2 + \frac{3}{2} \Ly^2 \norm{C}^2 \bigg) \sum^N_{i=1} \ \norm{ y(k) - \y{i}{}{k^i}}^2 \\
+ \Bigg( N M_{\ell}
+ N \bigg( \frac{3}{2} K_{\ell}^2 + \frac{5}{2} \bigg)
\frac{\lambda^2}{\gamma_{\ell}^2} \Bigg) \norm{\bar{a}(k) - x(k)}^2 .
\end{multline}

We note that $\|x(k) - x^i(k^i)\|^2 = \sum_{j=1}^{N} \|x_j(k) - x^i_j(k^i)\|^2$ and similar for $y$.
Assumption <ref> gives us both $k-B \leq \tau^i_j (k^i) \leq k + B - 1$ and $k-B \leq \mu^i_j (k^i) \leq k + B - 1$ for all $i,j \in [N]$.
Using these facts and the definitions in (<ref>) and (<ref>),
we rewrite (<ref>) as

\begin{multline} \label{eq:17}
\J{a}{b}{\ell}-\J{\x{*}{}{\ind{\ell}}}{\y{*}{}{\ind{\ell}}}{\ell} \leq
A_1 \sum^{k+B-1}_{\tau = k-B} \  \norm{\s{}{\tau}{\ell}}^2 \\
+ A_2 \sum^{k+B-1}_{\tau =k-B} \ \norm{ \q{}{\tau}}^2
+ NM_{\ell}\Bigg(1 + \frac{\lambda^2}{\gamma_{\ell}^2} \Bigg) \norm{\bar{a}(k) - x(k)}^2.
\end{multline}

Adding the last inequality to (<ref>) yields

\begin{multline}
\J{\x{}{}{k+B}}{\y{}{}{k+B}}{\ell} - \J{\x{*}{}{\ind{\ell}}}{\y{*}{}{\ind{\ell}}}{\ell} \leq \\
\bigg( N^2M_{\ell}\gamma^2_\ell \Lt^2 + \frac{3}{2} N \Lx^2 \bigg) \sum^{k+B-1}_{\tau = k-B} \  \norm{\s{}{\tau}{\ell}}^2 + \sum^N_{i=1} \big\Vert \s{i}{k^i}{\ell} \big\Vert^2 \\
+ \bigg( N^2 M_{\ell}\gamma^2_\ell \Lt^2 + \frac{3}{2} N \Ly^2 \norm{C}^2 \bigg) \sum^{k+B-1}_{\tau =k-B} \ \norm{ \q{}{\tau}}^2    \\
+ \Bigg( N M_{\ell} + N M_{\ell}
\Big( \lambda \max \big\{1, \gamma_\ell^{-1} \big\} \Big)^2 \Bigg) \norm{\bar{a}(k) - x(k)}^2 \\
+ N B \frac{\Lx + \Ly N \norm{C}^2}{2} \sum^{k-1}_{\tau = k - B} \norm{\s{}{\tau}{\ell}}^2. \label{eq:97}
\end{multline}

Since $k \leq k^i \leq k+B-1$ and $\sum^N_{i=1} \big\Vert \s{i}{\tau}{\ell} \big\Vert^2 = \big\Vert \s{}{\tau}{\ell} \big\Vert^2$ we have

\begin{equation}
\sum^N_{i=1} \big\Vert \s{i}{k^i}{\ell} \big\Vert^2 \leq \sum^N_{i=1}  \sum^{k+B-1}_{\tau=k} \big\Vert \s{i}{\tau}{\ell} \big\Vert^2 \leq \sum^{k+B-1}_{\tau=k} \big\Vert \s{}{\tau}{\ell} \big\Vert^2. \label{eq:87}
\end{equation}

Applying Lemma <ref> and (<ref>) to (<ref>) yields

\begin{multline}
\J{\x{}{}{k+B}}{\y{}{}{k+B}}{\ell} - \J{\x{*}{}{\ind{\ell}}}{\y{*}{}{\ind{\ell}}}{\ell} \leq \\
\bigg( N^2  M_{\ell}\gamma^2_\ell \Lt^2 + \frac{3}{2} N \Lx^2 \bigg) \sum^{k+B-1}_{\tau = k-B} \  \norm{\s{}{\tau}{\ell}}^2 \\
+ \bigg( N^2 M_{\ell}\gamma^2_\ell \Lt^2 + \frac{3}{2} N \Ly^2 \norm{C}^2 \bigg) \sum^{k+B-1}_{\tau =k-B} \ \norm{ \q{}{\tau}}^2    \\
+ N M_{\ell}\Bigg(1 + \frac{\lambda^2}{\gamma_{\ell}^2} \Bigg)
\frac{ 1 + 2\gamma_\ell \big( 1+\gamma_\ell \big) \Lt^2 B N}{1-\gamma_\ell}  \sum_{\tau=k}^{k+B-1} \Vert \s{}{\tau}{\ell} \Vert^2 \\
+ \epsilon_{\ell} \left( \sum_{\tau=k}^{k+B-1} \Vert \q{}{\tau} \Vert^2
+ \sum_{\tau=k-B}^{k-1} \Vert \s{}{\tau}{\ell} \Vert^2
+ \sum_{\tau=k-B}^{k-1} \Vert \q{}{\tau} \Vert^2\right) \\
+ N B \frac{\Lx + \Ly N \norm{C}^2}{2} \sum^{k-1}_{\tau = k - B} \norm{\s{}{\tau}{\ell}}^2 + \sum^{k+B-1}_{\tau=k} \big\Vert \s{}{\tau}{\ell} \big\Vert^2,
\end{multline}

where $\epsilon_{\ell} = N M_{\ell}\Big(1 + \frac{\lambda^2}{\gamma_{\ell}^2} \Big)
\frac{2\gamma_\ell \big( 1+\gamma_\ell \big) \Lt^2 B N}{1-\gamma_\ell} $.
We conclude by applying Lemma <ref> and combining like terms.

For all $\ind{\ell} \in \T$ and for all $k \in \{\eta_{\ell-1}, \ldots, \eta_{\ell} - B\}$, we have

$\at{k+B}{\ell} \leq \gamma_\ell^{-2}Q_\ell \bt{k+B}{\ell}
+ \gamma_\ell^{-1} R_\ell \bt{k}{\ell}$,

where we define

$Q_\ell = Z_1+ Z_3 + A_6 \big( Z_2 + Z_4 \big) + 1$ and
$R_\ell = Z_1 + Z_4 + A_5+ A_6 \big(Z_2 + Z_4 \big)$,

where $A_5$ and $A_6$ are from Lemma <ref>

\begin{multline}
Z_1  \coloneqq \frac{N}{2} \Big(3 \big\Vert C \big\Vert^4 L_\ell^2 \Ly^2 N +6 \big\Vert C \big\Vert^2 L_\ell^2 \Lx \Ly N
+3 L_\ell^2 \Lx^2 N \\ +6 \big\Vert C \big\Vert^2 L_\ell^2 \Ly N  +6 L_\ell^2 \Lx N +8 L_\ell^2 N +3 \Lx^2\Big)
\end{multline}

\begin{multline}
Z_2 \coloneqq \frac{N}{2}\Big(3 \big\Vert C \big\Vert^4 L_\ell^2 \Ly^2 N +6 \big\Vert C \big\Vert^2 L_\ell^2 \Lx \Ly N +3 \big\Vert C \big\Vert^2 \Ly^2\\
+ 6 \big\Vert C \big\Vert^2 L_\ell^2 \Ly N +3 L_\ell^2 \Lx^2 N +6 L_\ell^2 \Lx N +8 L_\ell^2 N  \Big)
\end{multline}

\begin{multline}
Z_3 \coloneqq \frac{N}{2} \Big[
(1+\lambda^2) \Big( 36  B \big\Vert C \big \Vert^4 L_\ell^2 \Ly^2 N
+ 9 \big\Vert C \big \Vert^4 \Ly^2 \\
+ 72  B \big\Vert C \big \Vert^2 L_\ell^2 \Lx \Ly N
+ 18 \big\Vert C \big \Vert^2 \Lx \Ly
+ 36  B L_\ell^2 \Lx^2 N \\
+ 9 \Lx^2 \Big)
+ 72  B \big\Vert C \big \Vert^2 L_\ell^2 \Ly N
+ 72  B L_\ell^2 \Lx N
+ 60  B L_\ell^2 N  \lambda^2 \\
+ 96  B L_\ell^2 N +18  \Ly \big\Vert C \big \Vert^2
+18 \Lx
+15 \lambda^2+24\Big]
\end{multline}

\begin{align}
&Z_4 \coloneqq N^2 L_\ell^2 B \Big(
\big( 1 + \lambda^2 \big) \big( 18  \big\Vert C \big\Vert^4 \Ly^2
+ 36  \big\Vert C \big\Vert^2 \Lx \Ly  \\
+ 18  \Lx^2 \big)
+36  \big\Vert C \big\Vert^2 \Ly
+36  \Lx
+30  \lambda^2
\Big).
\end{align}

Proof: From Lemma <ref>, for any $k \in \{\eta_{\ell-1}, \ldots, \eta_\ell - B\}$ we have

\begin{multline}
\at{k+B}{\ell} \leq \big( A_1+A_3+A_6 \big( A_2+A_4 \big) + 1 \big) \bt{k+B}{\ell} \\
+ \big( A_1+A_4+A_5+A_6 \big( A_2+A_4 \big) \big) \bt{k}{\ell} , \label{eq:91}
\end{multline}

where $A_1, \dots , A_6 > 0$ are from Lemma <ref>.

Using $ \gamma_\ell < 1$ gives

\begin{multline}
A_1 \leq \frac{N}{2} \Big(3 \big\Vert C \big\Vert^4 L_\ell^2 \Ly^2 N +6 \big\Vert C \big\Vert^2 L_\ell^2 \Lx \Ly N +3 \Lx^2\\
+6 \big\Vert C \big\Vert^2 L_\ell^2 \Ly N +3 L_\ell^2 \Lx^2 N +6 L_\ell^2 \Lx N +8 L_\ell^2 N \Big) . \label{eq:92}
\end{multline}

Similarly, using $\gamma_\ell < 1$ lets us upper bound $A_2$ as

\begin{multline}
A_2 \leq \frac{N}{2}\Big(3 \big\Vert C \big\Vert^4 L_\ell^2 \Ly^2 N +6 \big\Vert C \big\Vert^2 L_\ell^2 \Lx \Ly N +3 \big\Vert C \big\Vert^2 \Ly^2\\
6 \big\Vert C \big\Vert^2 L_\ell^2 \Ly N +3 L_\ell^2 \Lx^2 N +6 L_\ell^2 \Lx N +8 L_\ell^2 N  \Big). \label{eq:93}
\end{multline}

Taking $\gamma_\ell < \frac{1}{2}$ we have $\frac{1}{1-\gamma_\ell} < 1+2 \gamma_\ell$.
Using this inequality and the fact that $\max \big\{1, \gamma_\ell^{-1} \big\} = \frac{1}{\gamma_\ell}$ yields

\begin{multline}
A_3 \leq \frac{1}{2 \gamma_\ell^2}\bigg(N \Big(
\big(1+\lambda^2 \big) \big( 36  B \big\Vert C \big \Vert^4 L_\ell^2 \Ly^2 N
+ 9 \big\Vert C \big \Vert^4 \Ly^2 \\
+ 72  B \big\Vert C \big \Vert^2 L_\ell^2 \Lx \Ly N
+ 18 \big\Vert C \big \Vert^2 \Lx \Ly
+ 36  B L_\ell^2 \Lx^2 N \\
+ 9 \Lx^2 \big)
+ 72  B \big\Vert C \big \Vert^2 L_\ell^2 \Ly N
+ 72  B L_\ell^2 \Lx N  + 60  B L_\ell^2 N  \lambda^2 \\
+ 96  B L_\ell^2 N +18  \Ly \big\Vert C \big \Vert^2
+18 \Lx
+15 \lambda^2
+24\Big)\bigg). \label{eq:94}
\end{multline}

Lastly, we bound $A_4$.

Using $\gamma_\ell < \frac{1}{2}$ we again have $\frac{1}{1-\gamma_\ell} < 1+2 \gamma_\ell$. Applying this inequality and the fact that $\max \big\{1, \gamma_\ell^{-1} \big\} = \frac{1}{\gamma_\ell}$ yields

\begin{align}
A_4 &\leq \frac{1}{\gamma_\ell}\bigg(N^2 L_\ell^2 B \Big(
\big( 1 + \lambda^2 \big) \big( 18  \big\Vert C \big\Vert^4 \Ly^2
+ 36  \big\Vert C \big\Vert^2 \Lx \Ly  \\
+ 18  \Lx^2 \big)
+36  \big\Vert C \big\Vert^2 \Ly
+36  \Lx
+30  \lambda^2
\Big)\bigg). \label{eq:95}
\end{align}

From (<ref>)-(<ref>) we have

$A_1 \leq Z_1$,
$A_2 \leq Z_2$,
$A_3 \leq Z_3 \gamma_\ell^{-2}$, and
$A_4 \leq Z_4 \gamma_\ell^{-1}$.

Using these in (<ref>) with $\gamma_\ell < 1$ gives the result. $\blacksquare$

For $\ind{0}$, we have $\at{0}{0} \leq a_0$ and ${\at{B}{0} \leq a_0}$,

$a_0 \geq L_{J,0} \big( 1 + \norm{C} \big) \diam(\X)$.

Next, we would like to bound $\at{B}{0}$. By definition we have

\begin{align}
\at{B}{0} &= \J{\x{}{}{B}}{\y{}{}{B}}{0} - \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{0}.
\end{align}

This is equivalent to

\begin{align}
&\at{B}{0} = \J{\x{}{}{0} + \sum^{B - 1}_{\tau =0} \s{}{\tau}{0}}{\y{}{}{0} + \sum^{B - 1}_{\tau=0} C \s{}{\tau}{0}}{0} \\
&- \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{0} \\
& = \f{\x{}{}{\eta_0} + \sum^{B - 1}_{\tau =0} \s{}{\tau}{0}}{0} + \g{\y{}{}{\eta_0} + \sum^{B - 1}_{\tau=0} C \s{}{\tau}{0}}{0} \\
&- \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{0}.
\end{align}

From Lemma <ref> we have

\begin{align}
&\at{B}{0} \leq
\f{\x{}{}{0}}{0} \\
&+ \Bigg( \sum^{B - 1}_{\tau =0} \s{}{\tau}{0} \Bigg)^T \nabla_x \f{\x{}{}{0}}{0} + \frac{L_{x,0}}{2} \Bigg\Vert \sum^{B - 1}_{\tau =0} \s{}{\tau}{0} \Bigg\Vert^2 \\
&+\g{\y{}{}{\eta_0}}{0} + \Bigg( \sum^{B - 1}_{\tau =0} C \s{}{\tau}{0} \Bigg)^T \nabla_y \g{\y{}{}{0}}{0} \\
&+ \frac{L_{y,0}}{2} \Bigg\Vert \sum^{B - 1}_{\tau =0} C \s{}{\tau}{0} \Bigg\Vert^2
- \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{0}.
\end{align}

Using the fact $ \big\Vert \sum^N_{i=1} z \big\Vert^2 \leq N \sum^N_{i=1} \Vert z \Vert^2$ we have

\begin{align}
& \at{B}{0} \leq
\f{\x{}{}{0}}{0} \\
&+ \Bigg( \sum^{B - 1}_{\tau =0} \s{}{\tau}{0} \Bigg)^T \nabla_x \f{\x{}{}{0}}{0} + \frac{L_{x,0} B}{2}  \sum^{B - 1}_{\tau =0} \big\Vert \s{}{\tau}{0} \big\Vert^2 \\
&+\g{\y{}{}{0}}{0} + \Bigg( \sum^{B - 1}_{\tau =0} C \s{}{\tau}{0} \Bigg)^T \nabla_y \g{\y{}{}{0}}{0} \\
&+ \frac{L_{y,0} B}{2} \sum^{B - 1}_{\tau =0} \big\Vert C \s{}{\tau}{0} \big\Vert^2
- \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{0}.
\end{align}

Applying the Cauchy-Schwarz inequality and the norm properties $\norm{AB}^2 \leq \norm{A}^2 \norm{B}^2$ and $\norm{AB} \leq \norm{A} \norm{B}$ yields

\begin{align}
&\at{B}{0} \leq
\f{\x{}{}{0}}{0} \\
&+ \Bigg\Vert \sum^{B - 1}_{\tau =0} \s{}{\tau}{0} \Bigg\Vert \big\Vert \nabla_x \f{\x{}{}{0}}{0} \big\Vert \\
&+ \frac{L_{x,0} B}{2}  \sum^{B - 1}_{\tau =0} \big\Vert \s{}{\tau}{0} \big\Vert^2 \\
+ \Vert C \Vert \Bigg\Vert \sum^{B - 1}_{\tau =0} \s{}{\tau}{0} \Bigg\Vert \big\Vert \nabla_y \g{\y{}{}{0}}{0} \big\Vert \\
&+ \frac{L_{y,0} B \Vert C \Vert^2}{2} \sum^{B - 1}_{\tau =0} \big\Vert \s{}{\tau}{0} \big\Vert^2
- \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{0}.
\end{align}

Applying the triangle inequality gives us

\begin{align}
&\at{B}{0} \leq
\f{\x{}{}{0}}{0} \\
&+ \sum^{B - 1}_{\tau =0} \big\Vert \s{}{\tau}{0} \big\Vert \big\Vert \nabla_x \f{\x{}{}{0}}{0} \big\Vert \\
&+ \frac{L_{x,0} B}{2}  \sum^{B - 1}_{\tau =0} \big\Vert \s{}{\tau}{0} \big\Vert^2 \\
+ \Vert C \Vert \sum^{B - 1}_{\tau =0} \big\Vert \s{}{\tau}{0} \big\Vert \big\Vert \nabla_y \g{\y{}{}{0}}{0} \big\Vert \\
&+ \frac{L_{y,0} B \Vert C \Vert^2}{2} \sum^{B - 1}_{\tau =0} \big\Vert \s{}{\tau}{0} \big\Vert^2
- \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{0}.
\end{align}

Since $ \bt{B}{0} = \sum^{B - 1}_{\tau =0} \big\Vert \s{}{\tau}{0} \big\Vert^2$, applying the result of Lemma <ref>, i.e., $ \sum^{B - 1}_{\tau =0} \big\Vert \s{}{\tau}{0} \big\Vert^2 \leq B \diam \left(\X\right)^{2}$,
we obtain

\begin{align}
&\at{B}{0} \leq
\f{\x{}{}{0}}{0} \\
&+ \sum^{B - 1}_{\tau =0} \big\Vert \s{}{\tau}{0} \big\Vert \big\Vert \nabla_x \f{\x{}{}{0}}{0} \big\Vert
+ \frac{L_{x,0} B^2 \diam \left(\X\right)^{2}}{2}  \\
+ \Vert C \Vert \sum^{B - 1}_{\tau =0} \big\Vert \s{}{\tau}{0} \big\Vert \big\Vert \nabla_y \g{\y{}{}{0}}{0} \big\Vert \\
+ \frac{L_{y,0} B^2 \Vert C \Vert^2 \diam \left(\X\right)^{2}}{2}
- \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{0}.
\end{align}

Due to the boundedness of $\nabla_x \f{\cdot}{0}$ and $\nabla_y \g{\cdot}{0}$ we have

\begin{align}
&\at{B}{0} \leq
\f{\x{}{}{0}}{0} +  M_{x,0} \sum^{B - 1}_{\tau =0} \big\Vert \s{}{\tau}{0} \big\Vert \\
+ \frac{L_{x,0} B^2 \diam \left(\X\right)^{2}}{2}
+\g{\y{}{}{0}}{0} \\
+ M_{y,0} \Vert C \Vert \sum^{B - 1}_{\tau =0} \big\Vert \s{}{\tau}{0} \big\Vert
+ \frac{L_{y,0} B^2 \Vert C \Vert^2 \diam \left(\X\right)^{2}}{2} \\
- \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{0}.
\end{align}

Due to the fact $\Vert \s{}{\cdot}{1} \Vert \leq \diam\left( \X \right)$ we find

\begin{align}
&\at{B}{0} \leq
\f{\x{}{}{0}}{0} +  M_{x,0} B \diam\left( \X \right) \\
+ \frac{L_{x,0} B^2 \diam \left(\X\right)^{2}}{2}
+ M_{y,0} \Vert C \Vert B \diam\left( \X \right) \\
+ \frac{L_{y,0} B^2 \Vert C \Vert^2 \diam \left(\X\right)^{2}}{2}
- \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{0}.
\end{align}

Simplifying we get

\begin{align}
&\at{B}{0} \leq
\at{0}{0} + \big(  M_{x,0} +  M_{y,0} \Vert C \Vert \big)  B \diam\left( \X \right) \\
+ \big( L_{x,0} + L_{y,0} \Vert C \Vert^2  \big) \frac{ B^2 \diam \left(\X\right)^{2}}{2}.
\end{align}

Applying the bound in Equation (<ref>) we get

\begin{align}
\at{B}{0} &\leq L_{J,0} \big( 1 + \norm{C} \big) \diam(\X) \\
&+ \big(  M_{x,0} +  M_{y,0} \Vert C \Vert \big)  B \diam\left( \X \right) \\
+ \big( L_{x,0} + L_{y,0} \Vert C \Vert^2  \big) \frac{ B^2 \diam \left(\X\right)^{2}}{2}.
\end{align}

By definition of $\at{0}{0}$ we have

\begin{align}
\at{0}{0} &= \J{\x{}{}{0}}{\y{}{}{0}}{0} - \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{0}.   \label{eq:29}
\end{align}

Using this and the Lipschitz continuity of $\J{\cdot}{\cdot}{\ell}$

we have

$\at{0}{0} \leq L_{J,0} \Big( \big\Vert \x{}{}{0} - \x{*}{}{\ind{0}} \big\Vert + \big\Vert \y{}{}{0} - \y{*}{}{\ind{0}} \big\Vert \Big)$.

Then using $y=Cx$ next gives

$\at{0}{0} %&\leq L_{J,0} \Big( \big\Vert \x{}{}{0} - \x{*}{}{\ind{0}} \big\Vert + \norm{C} \big\Vert \x{}{}{0} - \x{*}{}{\ind{0}} \big\Vert \Big) \\
%\leq L_{J,0} \big( 1 + \norm{C} \big) \big\Vert \x{}{}{0} - \x{*}{}{\ind{0}} \big\Vert
\leq L_{J,0} \big( 1 + \norm{C} \big) \diam(\X)$,

which follows from $\big\Vert \x{}{}{0} - \x{*}{}{\ind{0}} \big\Vert \leq \diam(\X)$.

The same argument can be made to bound $\at{B}{0}$ by replacing $\at{0}{}$ with $\at{B}{}$ in (<ref>). Thus,

$\at{B}{0} \leq L_{J,0} \big( 1 + \norm{C} \big) \diam(\X)$.

Selecting any $a_0 \geq L_{J,0} \big( 1 + \norm{C} \big) \diam(\X)$ gives
the result. $\blacksquare$

For all $\ind{\ell} \in \T$, we have

$\bt{\eta_{\ell-1}}{\ell}\leq b_\ell$
and $\bt{\eta_{\ell-1}+B}{\ell} \leq b_\ell$,

$b_\ell \geq B \diam\left(\X\right)^{2}$.

Proof: By definition of $\bt{\eta_{\ell-1}}{\ell}$
in (<ref>)

and $\s{}{\tau}{\ell}$ in (<ref>) we have

$\bt{\eta_{\ell-1}}{\ell}  = \sum_{\tau=\eta_{\ell-1}-B}^{\eta_{\ell-1}-1} \sum_{i=1}^{N} \|x^i_i(\tau+1) - x^i_i(\tau)\|^2$.

We can bound this as

\leq  \sum_{\tau=\eta_{\ell-1}-B}^{\eta_{\ell-1}-1} \sup_{v, w \in X} \|v - w\|^2}$.

Using $\sup_{v \in X, w \in X} \|v - w\| \leq \diam\left(\X \right)$ we then find
the bound

$\bt{\eta_{\ell-1}}{\ell} \leq B \diam\left(\X \right)^2$.

An analogous argument shows that $\bt{\eta_{\ell-1} + B}{\ell} \leq B \diam\left(\X\right)^2$.

§.§ Proof of Theorem <ref>

For convenience we define $\s{}{\tau}{0}=0$ for $\tau<0$.
From Lemma <ref> and Lemma <ref> for any $k$ such that $0 \leq k \leq \eta_0 - B$,

\begin{align}
\at{k+B}{0} &\leq \at{k}{0} - \gamma_0^{-1}D_0 \bt{k+B}{0} + E_0 \bt{k}{0} \label{eq:20} \\
\at{k+B}{0} &\leq \gamma_0^{-2}F_0 \bt{k+B}{0} + \gamma_0^{-1} G_0 \bt{k}{0}. \label{eq:19}
\end{align}

Rearranging (<ref>) gives

$\bt{k+B}{0} \geq \frac{\at{k+B}{0}  - \gamma_0^{-1} G_0 \bt{k}{0}}{\gamma_0^{-2}F_0}$.

Substituting this into (<ref>) and rearranging yields

\begin{align}
&\bigg( 1 + \frac{\gamma_0 D_0}{F_0} \bigg) \at{k+B}{0} \leq \at{k}{0} + \bigg(  \frac{D_0 G_0}{F_0}
+ E_0 \bigg) \bt{k}{0}. \label{eq:22}
\end{align}

Fix $k \in \{B, \ldots, \eta_0 - B\}$ and substitute $k-B$ for $k$ in (<ref>) to find

\begin{align}
\bt{k}{0} &\leq \gamma_0 \frac{ \at{k-B}{0} -\at{k}{0} + E_0 \bt{k-B}{0}}{D_0}. \label{eq:21}
\end{align}

Applying (<ref>) to the right-hand side of (<ref>) and rearranging, we get

\begin{align}
&\at{k+B}{0} \leq \bigg( 1 + \frac{\gamma_0 D_0}{F_0} \bigg)^{-1}  \Bigg( \bigg(1 - \gamma_0 \bigg( \frac{G_0}{F_0} + \frac{E_0}{D_0} \bigg)\bigg) \\
& \cdot \at{k}{0}
+ \gamma_0 \bigg( \frac{G_0}{F_0}
+ \frac{E_0}{D_0} \bigg) \Big( \at{k-B}{0} + E_0 \bt{k-B}{0} \Big) \Bigg). \label{eq:25}
\end{align}

For any integer $d \geq 2$, we iterate (<ref>) to find

\begin{multline}
\at{k+dB}{0} \leq \at{k}{0} - \big( \gamma^{-1}_0 D_0 - E_0 \big) \sum^{d-1}_{j=1} \bt{k+jB}{0} \\
-\gamma^{-1}_0 D_0 \bt{k+dB}{0} + E_0 \bt{k}{0}.
\end{multline}

Using $\gamma_0 < D_0 / E_0$ and the fact that $\bt{\tau}{0} \geq 0$ for all $\tau > 0$ gives ${\at{k+dB}{0} \leq \at{k}{0} - \big( \gamma^{-1}_0 D_0 - E_0 \big) \bt{k+B}{0} + E_0 \bt{k}{0}}$.
Using the nonnegativity of $\at{k+dB}{0}$ we can then write $0 \leq \at{k}{0} - \big( \gamma^{-1}_0 D_0 - E_0 \big) \bt{k+B}{0} + E_0 \bt{k}{0}$, and thus

\begin{align}
\bt{k+B}{0} &\leq \frac{\gamma_0}{ D_0 - \gamma_0 E_0} \big( \at{k}{0} + E_0 \bt{k}{0} \big). \label{eq:26}
\end{align}

Next, we will use (<ref>) and (<ref>) to show linear convergence of Algorithm <ref> for $\ind{0}$.
Select $a_0 \geq L_{J,0} \big( 1 + \norm{C} \big) \diam(\X)$ and ${b_0 \geq B \diam\left(\X\right)^{2}}$ according to Lemma <ref> and Lemma <ref>. Then

$\at{0}{0} \leq a_0$,
$\at{B}{0} \leq a_0$,
$\bt{0}{0} \leq b_0$,
$\bt{B}{0} \leq b_0$.

Then (<ref>) and (<ref>) hold for $r_0=0,1$. Next, we will use induction to show that (<ref>) and (<ref>) hold for all $r_0 \in \N_0$. For
the inductive hypothesis suppose (<ref>) and (<ref>) hold for all $r_0$ up to $d \geq 1$.
We obtain from $\gamma_0 < 1 \big/ \big( \frac{G_0}{F_0} + \frac{E_0}{D_0} \big)$ and (<ref>) that

\begin{multline} \label{eq:t1_alpha_bound_start}
\at{dB+B}{0} \leq \frac{1}{1 + \gamma_0 \frac{D_0}{F_0}}  \Bigg( \bigg(1 - \gamma_0 \bigg( \frac{G_0}{F_0} + \frac{E_0}{D_0} \bigg)\bigg) \at{dB}{0} \\
+ \gamma_0 \bigg( \frac{G_0}{F_0}
+ \frac{E_0}{D_0} \bigg) \Big( \at{dB-B}{0} + E_0 \bt{dB-B}{0} \Big) \Bigg).
\end{multline}

For $\gamma_0 \leq \frac{1}{2 c_0}$ we have $\pt{-1}{0} \leq 1 + 2c_0\gamma_0$.
Using this and the inductive hypothesis,
we find

\begin{multline}
\at{dB+B}{0} \leq \frac{1}{1 + \gamma_0 \frac{D_0}{F_0}}  \Bigg( 1 + 2 \gamma^2_0 c_0 \bigg( \frac{G_0}{F_0} + \frac{E_0}{D_0} \bigg) \\
+ \gamma_0 \bigg( \frac{G_0}{F_0} + \frac{E_0}{D_0} \bigg) \big( 1 + 2c_0 \gamma_0 \big) E_0 \frac{b_0}{a_0} \Bigg) a_0 \pt{d-1}{0}.
\end{multline}

Then, using $\frac{b_0}{a_0} = \frac{D_0}{8 E_0 \big( \frac{G_0}{F_0} + \frac{E_0}{D_0} \big) F_0}$,

Next, we select $a_0$ and $b_0$ such that (<ref>) and (<ref>) are satisfied
and such that $\frac{b_0}{a_0} = \frac{D_0}{8 E_0 \big( \frac{G_0}{F_0} + \frac{E_0}{D_0} \big) F_0}$. Then

$\gamma_0 \leq \frac{1}{2 c_0}$, and $\gamma_0 \leq \frac{D_0}{8 F_0 \Big( \frac{G_0}{F_0} + \frac{E_0}{D_0} \Big) c_0}$ and simplifying gives

\begin{equation}
\at{dB+B}{0}  \leq \bigg( \frac{2 F_0 + \gamma_0 D_0}{2 F_0 + 2 \gamma_0 D_0} \bigg) a_0 \pt{d-1}{0}.
\end{equation}

Using $1 - \gamma_0 \frac{ D_0}{2F_0 + 2 \gamma_0 D_0} = \frac{2F_0 + \gamma_0 D_0}{2F_0 + 2 \gamma_0 D_0}$ and $\gamma_0 < 1$,
we reach

\begin{equation} \label{eq:t1_alpha_bound_end}
\at{dB+B}{0} \leq a_0 \pt{d}{0},
\end{equation}

and this completes the induction on (<ref>).

To complete the this inductive argument we make a similar argument for (<ref>). From (<ref>)

and the inductive hypothesis we have

the bound $\bt{dB+B}{0} \leq \frac{\gamma_0 \big( \frac{a_0}{b_0} + E_0 \big)}{ D_0 - \gamma_0 E_0} b_0 \pt{d-1}{0}$.
Here $\gamma_0 < \gamma_{\max, 0}$ ensures

${\gamma_0 \big(\frac{a_0}{b_0} + E_0\big) \leq (D_0 - \gamma_0 E_0)(1 - \gamma_0 c_0)}$,

and we obtain

$\bt{dB+B}{0} \leq \big( 1 - \gamma_0 c_0 \big) b_0 \pt{d-1}{0}$.

The definition of $\pt{}{0}$ gives

$\bt{dB+B}{0} \leq b_0 \pt{d}{0}$.

Thus, (<ref>) and (<ref>) hold for all ${r_0 \in \N_0}$.
From Lemma <ref> we have

$\dt{dB+B}{1} \leq d_{0} \pt{d}{0}$,

where ${d_{0} = B^2 m \norm{C}^2  b_{0}}$.

§.§ Proof of Theorem <ref>

We first show that for $\gamma_1 \in \big( 0,\gamma_{\max,1} \big)$ and $r_1 \in \N_0$ there holds

\begin{align}
\at{\eta_{0} + r_1 B}{1} & \leq a_1 \pt{r_1-1}{1} \label{eq:59}\\
\bt{\eta_{0} + r_1 B}{1} & \leq b_1 \pt{r_1-1}{1} \label{eq:60}\\
\dt{\eta_{0} + r_1 B}{1} & \leq d_1 \pt{r_1-1}{1}. \label{eq:99}
\end{align}

Following the same steps to reach (<ref>) we find

\begin{multline}
\at{k+B}{1} \leq \bigg( 1 + \frac{\gamma_1 D_1}{F_1} \bigg)^{-1}  \Bigg( \bigg(1 - \gamma_1 \bigg( \frac{G_1}{F_1} + \frac{E_1}{D_1} \bigg)\bigg)\at{k}{1}  \\
+ \gamma_1 \bigg( \frac{G_1}{F_1}
+ \frac{E_1}{D_1} \bigg) \Big( \at{k-B}{1} + E_1 \bt{k-B}{1} \Big) \Bigg), \label{eq:56}
\end{multline}

and following the same steps to reach (<ref>), we find

\begin{align}
\bt{k+B}{1} &\leq \frac{\gamma_1}{ D_1 - \gamma_1 E_1} \big( \at{k}{1} + E_1 \bt{k}{1} \big). \label{eq:57}
\end{align}

We will use (<ref>) and (<ref>) to prove the convergence of Algorithm <ref> for $t_1$, i.e., show that (<ref>), (<ref>), and (<ref>) hold for any $r_1 \in \N_0$. First, we show
that (<ref>) and (<ref>) hold for $r_1 = 0,1$. Specifically, we select $a_{1} > 0$ and $b_{1} > 0$ such that

\begin{align}
\begin{array}{cc}
\at{\eta_0}{1} \leq a_1 & \at{\eta_0 + B}{1} \leq a_1  \label{eq:78}
\end{array} \\
\begin{array}{cc}
\bt{\eta_0}{1} \leq b_1  & \bt{\eta_0 + B}{1} \leq b_1 . \label{eq:79}
\end{array}
\end{align}

By definition of $\at{\eta_0}{1}$ we may write

\begin{multline}
\at{\eta_0}{1} =
\J{\x{}{}{\eta_0}}{\y{}{}{\eta_0}}{1}
- \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{0} \\
+ \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{0}
+\J{\x{}{}{\eta_0}}{\y{}{}{\eta_0}}{0} \\
- \J{\x{}{}{\eta_0}}{\y{}{}{\eta_0}}{0}
- \J{\x{*}{}{\ind{1}}}{\y{*}{}{\ind{1}}}{1}. \label{eq:30}
\end{multline}

Using the triangle inequality, Assumption <ref>,
and Theorem <ref> gives

\begin{multline}
\at{\eta_0}{1} \leq
\Delta L_t + a_{0} \pt{r_{0} -1}{0} \\
+ \big\vert \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{0}
- \J{\x{*}{}{\ind{1}}}{\y{*}{}{\ind{1}}}{1} \big\vert.
\end{multline}

Adding $\J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{1} - \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{1}$, using the triangle inequality,
and again using Assumption <ref> yields

\begin{multline}
\at{\eta_0}{1} \leq
2 \Delta L_t + a_{0} \pt{r_{0} -1}{0} \\
+ \big\vert \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{1}
- \J{\x{*}{}{\ind{1}}}{\y{*}{}{\ind{1}}}{1} \big\vert. \label{eq:49}
\end{multline}

Using the Lipschitz continuity of $\J{\cdot}{\cdot}{1}$, the triangle inequality, and $y = Cx$,
we find

\begin{multline}
\big\vert \J{\x{*}{}{\ind{0}}}{\y{*}{}{\ind{0}}}{1}
- \J{\x{*}{}{\ind{1}}}{\y{*}{}{\ind{1}}}{1} \big\vert \\
\leq L_{J,1} (1 + \|C\|)\Big( \big\Vert \x{*}{}{\ind{0}} - \x{*}{}{\ind{1}} \big\Vert \Big)
\leq L_{J,1} \sigma_1 \big( 1 + \big\Vert C \big\Vert \big), \label{eq:48}
\end{multline}

where the last inequality uses Assumption <ref>.

Using (<ref>) in (<ref>) yields

\begin{align}
\at{\eta_0}{1} &\leq
a_{0} \pt{r_{0} -1}{0} + 2 \Delta L_t
+ L_{J,1} \sigma_1 \big( 1 + \big\Vert C \big\Vert \big). \label{eq:80}
\end{align}

Next, we bound $\at{\eta_0 + B}{1}$. By definition we have

\begin{multline}
\at{\eta_0 + B}{1}
%&= \J{\x{}{}{\eta_0} + \sum^{\eta_0 + B - 1}_{\tau = \eta_0} \s{}{\tau}{1}}{\y{}{}{\eta_0} + \sum^{\eta_0 + B - 1}_{\tau=\eta_0} C \s{}{\tau}{1}}{1} \\
%&- \J{\x{*}{}{\ind{1}}}{\y{*}{}{\ind{1}}}{1} \\
= f\bigg(x(\eta_0) + \sum^{\eta_0 + B - 1}_{\tau = \eta_0} \s{}{\tau}{1}; t_1\bigg) \\
%\f{\x{}{}{\eta_0} + \sum^{\eta_0 + B - 1}_{\tau = \eta_0} \s{}{\tau}{1}}{1} \\
+ g\bigg(y(\eta_0) + \sum^{\eta_0 + B - 1}_{\tau=\eta_0} C \s{}{\tau}{1}; t_1\bigg)
%+ \g{\y{}{}{\eta_0} + \sum^{\eta_0 + B - 1}_{\tau=\eta_0} C \s{}{\tau}{1}}{1}
- \J{\x{*}{}{\ind{1}}}{\y{*}{}{\ind{1}}}{1}.
\end{multline}

Applying Lemma <ref>, the bound $ \big\Vert \sum^N_{i=1} z \big\Vert^2 \leq N \sum^N_{i=1} \Vert z \Vert^2$,
the Cauchy-Schwarz inequality, and the triangle inequality, we find

\begin{multline}
\at{\eta_0 + B}{1} \leq
\f{\x{}{}{\eta_0}}{1} \\
+ \sum^{\eta_0 + B - 1}_{\tau = \eta_0} \big\Vert \s{}{\tau}{1} \big\Vert \big\Vert \nabla_x \f{\x{}{}{\eta_0}}{1} \big\Vert
+ \frac{L_{x,1} B}{2}  \sum^{\eta_0 + B - 1}_{\tau = \eta_0} \big\Vert \s{}{\tau}{1} \big\Vert^2 \\
+ \Vert C \Vert \sum^{\eta_0 + B - 1}_{\tau = \eta_0} \big\Vert \s{}{\tau}{1} \big\Vert \big\Vert \nabla_y \g{\y{}{}{\eta_0}}{1} \big\Vert \\
+ \frac{L_{y,1} B \Vert C \Vert^2}{2} \sum^{\eta_0 + B - 1}_{\tau = \eta_0} \big\Vert \s{}{\tau}{1} \big\Vert^2
- \J{\x{*}{}{\ind{1}}}{\y{*}{}{\ind{1}}}{1}.
\end{multline}

Since $ \bt{\eta_0 + B}{1} = \sum^{\eta_0 + B - 1}_{\tau = \eta_0} \big\Vert \s{}{\tau}{1} \big\Vert^2$,
we apply Lemma <ref> to it, then use the boundedness
of $\nabla_x \f{\cdot}{1}$ and $\nabla_y \g{\cdot}{1}$ from (<ref>) and
the fact that $\Vert \s{}{\cdot}{1} \Vert \leq \diam\left( \X \right)$ to find

\begin{multline}
\at{\eta_0 + B}{1} \leq
\at{\eta_0}{1} + \big(  M_{x,1} +  M_{y,1} \Vert C \Vert \big)  B \diam\left( \X \right) \\
+ \big( L_{x,1} + L_{y,1} \Vert C \Vert^2  \big) \frac{ B^2 \diam \left(\X\right)^{2}}{2}.
\end{multline}

Applying the bound in (<ref>) we get

\begin{multline}
\at{\eta_0 + B}{1} \leq a_{0} \pt{r_{0} -1}{0} + 2 \Delta L_t
+ L_{J,1} \sigma_1 \big( 1 + \big\Vert C \big\Vert \big) \\
+ \big(  M_{x,1} +  M_{y,1} \Vert C \Vert \big)  B \diam\left( \X \right) \\
+ \big( L_{x,1} + L_{y,1} \Vert C \Vert^2  \big) \frac{ B^2 \diam \left(\X\right)^{2}}{2}. \label{eq:84}
\end{multline}

Next, we modify the right-hand side of (<ref>) to design $\frac{b_1}{a_1}$.  We observe that $8E_1\left(\frac{G_1}{F_1} + \frac{E_1}{D_1}\right)F_1 \geq 1$. Indeed,
we have the bound

$8E_1\left(\frac{G_1}{F_1} + \frac{E_1}{D_1}\right)F_1 = 8E_1G_1 + 8\frac{E_1^2F_1}{D_1} \geq 1$,

which follows by inspection of $8E_1G_1$. We note for all $\gamma_1 \in \left( 0 ,  \frac{2}{\big( 1+ B \big) L_{x,1} + \big( 1 +B N  \big) \norm{C}^2 L_{y,1}} \right)$, we have $D_1 \leq 1$. Then
we have

$\frac{D_1}{8E_1\left(\frac{G_1}{F_1} + \frac{E_1}{D_1}\right)F_1} \leq 1$ as well.

We can multiply $\frac{8E_1\left(\frac{G_1}{F_1} + \frac{E_1}{D_1}\right)F_1}{D_1} \geq 1$ with the last term in (<ref>)
to yield a new upper bound to replace (<ref>).

Therefore if we select

\begin{align} \label{eq:a1_choice}
a_1 &= a_{0} \pt{r_{0} -1}{0} + 2 \Delta L_t
+ L_{J,1} \sigma_1 \big( 1 + \big\Vert C \big\Vert \big) \\
+ \big(  M_{x,1} +  M_{y,1} \Vert C \Vert \big)  B \diam\left( \X \right) \\
+ \frac{8 E_1\left(\frac{G_1}{F_1} + \frac{E_1}{D_1}\right)F_1 B^2 \diam \left(\X\right)^{2}}{2 D_1} \big( L_{x,1} + L_{y,1} \Vert C \Vert^2  \big),
\end{align}

then we satisfy (<ref>).
Furthermore, selecting $b_1 = B \diam \left( \X \right)^2$ satisfies (<ref>) due to Lemma <ref>.
From these selections of $a_1$ and $b_1$ we have $\frac{b_1}{a_1} \leq \frac{D_1}{8 E_1 \big( \frac{G_1}{F_1} + \frac{E_1}{D_1} \big) F_1}$.

These choices of $a_1, b_1$ satisfy (<ref>) and (<ref>) for $r_1 = 0,1$. Next, we prove that (<ref>) and (<ref>) hold for all $r_1 \in \N_0$ by induction. For
the inductive hypothesis suppose that (<ref>) and (<ref>) hold for all $r_1$ up to $d\geq 1$.

Using the same steps used from (<ref>) to (<ref>), we have

$\at{\eta_0 +dB+B}{1} \leq a_1 \pt{d}{1}$,

and this completes induction on (<ref>).

To complete the inductive argument for $\beta$ we make a similar argument
in order to reach (<ref>). From (<ref>) we have

\begin{equation} \label{eq:t2_beta1}
\bt{\eta_0 \!+\! dB \!+\! B}{1} \leq \frac{\gamma_1}{ D_1 \!-\! \gamma_1 E_1} \big( \at{\eta_0 + dB}{1} \!+\! E_1 \bt{\eta_0 \!+\! dB}{1} \big).
\end{equation}

Next, we have

${\bt{\eta_0 +dB+B}{1} \leq \frac{\gamma_1 \big( \frac{a_1}{b_1} + E_1 \big)}{ D_1 - \gamma_1 E_1} b_1 \pt{d-1}{1}}$

by the inductive hypothesis.
We then design ${\gamma_1 < \frac{ \frac{a_1}{b_1} + 2E_1 + D_1 c_1 - \sqrt{\big( \frac{a_1}{b_1} + 2E_1 + D_1 c_1\big)^2 - 4 D_1 E_1 c_1}}{2 E_1 c_1}}$ to ensure that $\gamma_1 \Big( \frac{a_1}{b_1} + E_1 \Big) \leq \big(  D_1 - \gamma_1 E_1 \big) \big( 1 - \gamma_1 c_1 \big)$ so that we obtain

$\bt{\eta_0 + dB+B}{1} \leq \big( 1 - \gamma_1 c_1 \big) b_1 \pt{d-1}{1}$.

\begin{align} \label{eq:100}
\bt{\eta_0 +dB+B}{1} &\leq b_1 \pt{d}{1}.
\end{align}

Thus, (<ref>) holds for all $r_1 \in \N_0$.
Then by Lemma <ref> we have

$\dt{\eta_0 + dB+B}{1} \leq B^2 m \norm{C}^2  b_{1} \pt{d}{1}$.

This proves (<ref>).

The preceding establishes the base case for the next inductive argument
in which we show that if

$\at{\eta_{\ell-1} + r_\ell B}{\ell}  \leq a_\ell \pt{r_\ell-1}{\ell}$,
$\bt{\eta_{\ell-1} + r_\ell B}{\ell}  \leq b_\ell \pt{r_\ell-1}{\ell}$, and
$\dt{\eta_{\ell-1} + r_\ell B}{\ell}  \leq b_\ell \pt{r_\ell-1}{\ell}$

hold for a fixed $\ind{\ell}$, then
$\dt{\eta_{\ell} + r_{\ell+1} B}{\ell + 1} \leq d_{\ell+1} \pt{r_{\ell+1}-1}{\ell + 1}$

\begin{align}
\at{\eta_{\ell} + r_{\ell+1} B}{\ell + 1} & \leq a_{\ell+1} \pt{r_{\ell+1}-1}{\ell + 1} \label{eq:74}\\
\bt{\eta_{\ell} + r_{\ell+1} B}{\ell + 1} & \leq b_{\ell+1} \pt{r_{\ell+1}-1}{\ell + 1} \label{eq:75}
\end{align}

also hold. This will complete our proof of Theorem <ref>.

From Lemma <ref> and Lemma <ref> for any $k \in \{\eta_{\ell}, \ldots, \eta_{\ell+1} - B\}$,

\begin{align}
\at{k+B }{\ell+1} &\leq \at{k}{\ell+1} - \gamma_{\ell+1} ^{-1}D_{\ell+1} \bt{k+B }{{\ell+1}} + E_{\ell+1} \bt{k}{{\ell+1}} \label{eq:62} \\
\at{k+B }{\ell+1} &\leq \gamma_{\ell+1}^{-2}F_{\ell+1} \bt{k+B}{\ell+1} + \gamma_{\ell+1}^{-1} G_{\ell+1} \bt{k}{\ell+1}, \label{eq:63}
\end{align}

by taking $\gamma_{\ell+1} < \frac{2}{\big( 1+ B \big) L_{x,\ell+1} + \big( 1 +B N  \big) \norm{C}^2 L_{y,\ell+1}}$.
Rearranging (<ref>) to lower-bound $\bt{k+B}{\ell+1}$ we obtain

\begin{align}
\bt{k+B}{\ell+1} &\geq \frac{\at{k+B}{\ell+1}  - \gamma_{\ell+1}^{-1} G_{\ell+1} \bt{k}{\ell+1}}{\gamma_{\ell+1}^{-2} F_{\ell+1}}.
\end{align}

Applying this to (<ref>) and simplifying gives

\begin{multline}
\bigg( 1 + \frac{\gamma_{\ell+1} D_{\ell+1}}{F_{\ell+1}} \bigg) \at{k+B}{\ell+1} \leq \at{k}{\ell+1} \\
+ \bigg( \frac{D_{\ell+1} G_{\ell+1}}{F_{\ell+1}}
+ E_{\ell+1} \bigg) \bt{k}{\ell+1}. \label{eq:64}
\end{multline}

Fix $k \in \{\eta_{\ell} + B, \ldots, \eta_{\ell+1} - B\}$ and replace $k-B$ by $k$ in (<ref>).

$\bt{k}{\ell+1} \leq \frac{\gamma_{\ell+1}}{D_{\ell+1}} \big( \at{k-B}{\ell+1} -\at{k}{\ell+1} + E_{\ell+1} \bt{k-B}{\ell+1} \big)$.

Applying this to (<ref>) gives

\begin{align}
&\at{k+B}{\ell+1} \leq \bigg( 1 + \frac{\gamma_{\ell+1} D_{\ell+1}}{F_{\ell+1}} \bigg)^{-1}  \Bigg( \bigg(1 -\gamma_{\ell+1} \\
&\cdot\bigg( \frac{G_{\ell+1}}{F_{\ell+1}} + \frac{E_{\ell+1}}{D_{\ell+1}} \bigg)\bigg) \at{k}{\ell+1}
+ \gamma_{\ell+1} \bigg( \frac{G_{\ell+1}}{F_{\ell+1}}
+ \frac{E_{\ell+1}}{D_{\ell+1}} \bigg) \\
& \cdot \Big( \at{k-B}{\ell+1} + E_{\ell+1} \bt{k-B}{\ell+1} \Big) \Bigg). \label{eq:66}
\end{align}

For any $d \geq 2$, we iterate (<ref>) to find

\begin{multline}
\at{k+dB}{\ell+1} \leq \at{k}{\ell+1} - \gamma^{-1}_{\ell+1} D_{\ell+1} \bt{k+dB}{\ell+1} \\ + E_{\ell+1} \bt{k}{\ell+1}
- \big( \gamma^{-1}_{\ell+1} D_{\ell+1} - E_{\ell+1} \big) \sum^{d-1}_{j=1} \bt{k+jB}{\ell+1}.
\end{multline}

Since $\gamma_{\ell+1} < D_{\ell+1} / E_{\ell+1}$ and $\bt{\tau}{\ell+1} \geq 0$ for all $\tau > 0$,
we obtain

\begin{multline}
\at{k+dB}{\ell+1} \leq \at{k}{\ell+1} \\ - \big( \gamma^{-1}_{\ell+1} D_{\ell+1} - E_{\ell+1} \big) \bt{k+B}{\ell+1} + E_{\ell+1} \bt{k}{\ell+1}.
\end{multline}

Using $\at{k+dB}{\ell+1} \geq 0$,

we rearrange to find

\begin{equation}
\bt{k+B}{\ell+1} \leq \frac{\gamma_{\ell+1}}{ D_{\ell+1} - \gamma_{\ell+1} E_{\ell+1}} \big( \at{k}{\ell+1} + E_{\ell+1} \bt{k}{\ell+1} \big). \label{eq:67}
\end{equation}

We will use (<ref>) and (<ref>) to show that (<ref>)
and (<ref>) hold for any $r_{\ell+1} \in \N_0$.
First, we show that (<ref>) and (<ref>) hold for $r_{\ell+1} = 0,1$.
Specifically, we select $a_{\ell+1} > 0$ and $b_{\ell+1} > 0$ such that

\begin{equation}
\at{\eta_{\ell}}{\ell+1} \leq a_{\ell+1}, \qquad \at{\eta_{\ell} + B}{\ell+1} \leq a_{\ell+1} \label{eq:73}
\end{equation}

\begin{equation}
\bt{\eta_{\ell}}{\ell+1} \leq b_{\ell+1}, \qquad \bt{\eta_{\ell} + B}{\ell+1} \leq b_{\ell+1}. \label{eq:68}
\end{equation}

Using the definition of $\at{\eta_{\ell}}{\ell+1}$ we
repeat the steps used from (<ref>) to (<ref>) to find

if we select $a_{\ell+1}$ such that

\begin{multline}
a_{\ell+1} = a_{\ell} \pt{r_\ell -1}{\ell} + 2 \Delta L_t
+ L_{J,{\ell+1}} \sigma_{\ell+1} \big( 1 + \big\Vert C \big\Vert \big) \\
+ \big(  M_{x,{\ell+1}} +  M_{y,{\ell+1}} \Vert C \Vert \big)  B \diam\left( \X \right) \\
+ \frac{8E_{\ell+1}\left(\frac{G_{\ell+1}}{F_{\ell+1}} + \frac{E_{\ell+1} }{ D_{\ell+1}}\right)F_{\ell+1} B^2 \diam \left(\X\right)^{2}}{2 D_{\ell+1}} \\
\cdot \big( L_{x,\ell+1} + L_{y,\ell+1} \Vert C \Vert^2  \big),
\end{multline}

then (<ref>) holds.
Selecting $b_{\ell+1} = B \diam \left( \X \right)^2$ satisfies (<ref>) due to Lemma <ref>.
From these selections of $a_{\ell+1}$ and $b_{\ell+1}$ we have the bound

%\leq \frac{B \diam \left( \X \right)^2}{\frac{8E_{\ell+1}\left(\frac{G_{\ell+1}}{F_{\ell+1}} + \frac{E_{\ell+1}}{D_{\ell+1}}\right)F_{\ell+1}}{D_{\ell+1}} \big( L_{x,\ell+1} + L_{y,\ell+1} \Vert C \Vert^2  \big)} \\
%& \cdot \frac{1}{\frac{ B^2 \diam \left(\X\right)^{2}}{2}} \\
%&\leq \frac{D_{\ell+1}}{8 E_{\ell+1} \big( \frac{G_{\ell+1}}{F_{\ell+1}} + \frac{E_{\ell+1}}{D_{\ell+1}} \big) F_{\ell+1}} \\
%& \cdot \frac{2}{B(L_{x,\ell+1} + L_{y,\ell+1}\|C\|^2)} \\
\leq \frac{D_{\ell+1}}{8 E_{\ell+1} \big( \frac{G_{\ell+1}}{F_{\ell+1}} + \frac{E_{\ell+1}}{D_{\ell+1}} \big) F_{\ell+1}}$.

These selections of $a_{\ell+1}, b_{\ell+1}$ satisfy (<ref>) and (<ref>) for $r_{\ell+1} = 0,1$.

Next, we prove that (<ref>) and (<ref>) hold for all $r_{\ell+1} \in \N_0$ by induction. For the inductive hypothesis suppose
that (<ref>) and (<ref>) hold for all $r_{\ell+1}$ up to some $d\geq 1$.
Using the same steps used from (<ref>) to (<ref>)
we obtain

$\at{\eta_\ell + dB+B}{\ell+1} \leq a_{\ell+1} \pt{d}{\ell+1}$,

and this completes the induction on (<ref>).

To complete the inductive argument for $\beta$ we make a similar argument to
reach (<ref>).
Following the same steps used to go from (<ref>) to (<ref>),
we find

$\bt{\eta_\ell + dB+B}{\ell+1} \leq b_{\ell+1} \pt{d}{\ell+1}$.

Therefore, (<ref>) holds for $\ell+1$.
We also have

$\dt{\eta_\ell + dB+B}{\ell} \leq d_{\ell+1} \pt{d}{\ell+1}$,

from Lemma <ref>,
where $d_{\ell+1} \coloneqq B^2 m \norm{C}^2  b_{\ell+1}$.

[1]
J. Yang, K. Yu, Y. Gong, and T. Huang, “Linear spatial pyramid matching using sparse coding for image classification,” in 2009 IEEE Conference on computer vision and pattern recognition, 2009, pp. 1794–1801.

[2]
A. Koppel, A. Simonetto, A. Mokhtari, G. Leus, and A. Ribeiro, “Target tracking with dynamic convex optimization,” in 2015 IEEE Global Conference on Signal and Information Processing (GlobalSIP), 2015, pp. 1210–1214.

[3]
Y. Tang, “Time-varying optimization and its application to power system operation,” Ph.D. dissertation, California Institute of Technology, 2019.

[4]
Y. Tang, K. Dvijotham, and S. Low, “Real-time optimal power flow,” IEEE Transactions on Smart Grid, vol. 8, no. 6, pp. 2963–2973, 2017.

[5]
O. Arslan and D. E. Koditschek, “Exact robot navigation using power diagrams,” in 2016 IEEE International Conference on Robotics and Automation (ICRA), 2016, pp. 1–8.

[6]
Y. Zhao and W. Lu, “Training neural networks with time-varying optimization,” in Proceedings of 1993 International Conference on Neural Networks (IJCNN-93-Nagoya, Japan), vol. 2, 1993, pp. 1693–1696 vol.2.

[7]
C. Sun, M. Ye, and G. Hu, “Distributed time-varying quadratic optimization for multiple agents under undirected graphs,” IEEE Transactions on Automatic Control, vol. 62, no. 7, pp. 3687–3694, 2017.

[8]
M. Fazlyab, S. Paternain, V. M. Preciado, and A. Ribeiro, “Prediction-correction interior-point method for time-varying convex optimization,” IEEE Transactions on Automatic Control, vol. 63, no. 7, pp. 1973–1986, 2018.

[9]
A. Y. Popkov, “Gradient methods for nonstationary unconstrained optimization problems,” Automation and Remote Control, vol. 66, no. 6, pp. 883–891, 2005.

[10]
Y. Tang, E. Dall'Anese, A. Bernstein, and S. Low, “Running primal-dual gradient method for time-varying nonconvex problems,” SIAM Journal on Control and Optimization, vol. 60, no. 4, pp. 1970–1990, 2022.

[11]
A. Simonetto and E. Dall’Anese, “Prediction-correction algorithms for time-varying constrained optimization,” IEEE Transactions on Signal Processing, vol. 65, no. 20, pp. 5481–5494, 2017.

[12]
N. Bastianello, A. Simonetto, and R. Carli, “Prediction-correction splittings for time-varying optimization with intermittent observations,” IEEE Control Systems Letters, vol. 4, no. 2, pp. 373–378, 2019.

[13]
M. Colombino, E. Dall’Anese, and A. Bernstein, “Online optimization as a feedback controller: Stability and tracking,” IEEE Transactions on Control of Network Systems, vol. 7, no. 1, pp. 422–432, 2020.

[14]
A. Simonetto, A. Mokhtari, A. Koppel, G. Leus, and A. Ribeiro, “A class of prediction-correction methods for time-varying convex optimization,” IEEE Transactions on Signal Processing, vol. 64, no. 17, pp. 4576–4591, 2016.

[15]
M. Baumann, C. Lageman, and U. Helmke, “Newton-type algorithms for time-varying pose estimation,” in Proceedings of the 2004 Intelligent Sensors, Sensor Networks and Information Processing Conference, 2004., 2004, pp. 155–160.

[16]
A. Simonetto, E. Dall'Anese, S. Paternain, G. Leus, and G. B. Giannakis, “Time-varying convex optimization: Time-structured algorithms and applications,” Proceedings of the IEEE, vol. 108, no. 11, pp. 2032–2048, 2020.

[17]
A. Hauswirth, S. Bolognani, G. Hug, and F. Dörfler, “Optimization algorithms as robust feedback controllers,” arXiv preprint arXiv:2103.11329, 2021.

[18]
M. Colombino, J. W. Simpson-Porco, and A. Bernstein, “Towards robustness guarantees for feedback-based optimization,” in 2019 IEEE 58th Conference on Decision and Control (CDC), 2019, pp. 6207–6214.

[19]
A. Bernstein, E. Dall'Anese, and A. Simonetto, “Online primal-dual methods with measurement feedback for time-varying convex optimization,” IEEE Transactions on Signal Processing, vol. 67, no. 8, pp. 1978–1991, 2019.

[20]
E. Dall’Anese and A. Simonetto, “Optimal power flow pursuit,” IEEE Transactions on Smart Grid, vol. 9, no. 2, pp. 942–952, 2016.

[21]
L. Lindemann, A. Robey, L. Jiang, S. Tu, and N. Matni, “Learning robust output control barrier functions from safe expert demonstrations,” arXiv preprint arXiv:2111.09971, 2021.

[22]
A. M. Ospina, N. Bastianello, and E. Dall’Anese, “Feedback-based optimization with sub-weibull gradient errors and intermittent updates,” IEEE Control Systems Letters, vol. 6, pp. 2521–2526, 2022.

[23]
B. Sinopoli, L. Schenato, M. Franceschetti, K. Poolla, M. I. Jordan, and S. S. Sastry, “Kalman filtering with intermittent observations,” IEEE transactions on Automatic Control, vol. 49, no. 9, pp. 1453–1464, 2004.

[24]
J. Tsitsiklis, D. Bertsekas, and M. Athans, “Distributed asynchronous deterministic and stochastic gradient optimization algorithms,” IEEE transactions on automatic control, vol. 31, no. 9, pp. 803–812, 1986.

[25]
D. P. Bertsekas and J. N. Tsitsiklis, “Convergence rate and termination of asynchronous iterative algorithms,” in Proceedings of the 3rd International Conference on Supercomputing, 1989, pp. 461–470.

[26]
——, Parallel and Distributed Computation: Numerical Methods.1em plus 0.5em minus 0.4emUSA: Prentice-Hall, Inc., 1989.

[27]
K. R. Hendrickson and M. T. Hale, “Totally asynchronous primal-dual convex optimization in blocks,” IEEE Transactions on Control of Network Systems, vol. 10, no. 1, pp. 454–466, 2022.

[28]
K. Yazdani and M. Hale, “Asynchronous parallel nonconvex optimization under the polyak-łojasiewicz condition,” IEEE Control Systems Letters, vol. 6, pp. 524–529, 2021.

[29]
M. Assran, A. Aytekin, H. R. Feyzmahdavian, M. Johansson, and M. G. Rabbat, “Advances in asynchronous parallel and distributed optimization,” Proceedings of the IEEE, vol. 108, no. 11, pp. 2013–2031, 2020.

[30]
M. Ubl and M. Hale, “Totally asynchronous large-scale quadratic programming: Regularization, convergence rates, and parameter selection,” IEEE Transactions on Control of Network Systems, vol. 8, no. 3, pp. 1465–1476, 2021.

[31]
Y. Tang, E. Dall'Anese, A. Bernstein, and S. H. Low, “A feedback-based regularized primal-dual gradient method for time-varying nonconvex optimization,” in 2018 IEEE Conference on Decision and Control (CDC), 2018, pp. 3244–3250.

[32]
C.-Y. Chang, M. Colombino, J. Corté, and E. Dall’Anese, “Saddle-flow dynamics for distributed feedback-based optimization,” IEEE Control Systems Letters, vol. 3, no. 4, pp. 948–953, 2019.

[33]
S. Bolognani, R. Carli, G. Cavraro, and S. Zampieri, “Distributed reactive power feedback control for voltage regulation and loss minimization,” IEEE Transactions on Automatic Control, vol. 60, no. 4, pp. 966–981, 2014.

[34]
A. Bernstein and E. Dall'Anese, “Asynchronous and distributed tracking of time-varying fixed points,” in 2018 IEEE Conference on Decision and Control (CDC), 2018, pp. 3236–3243.

[35]
N. Bastianello, D. Deplano, M. Franceschelli, and K. H. Johansson, “Online distributed learning over random networks,” arXiv preprint arXiv:2309.00520, 2023.

[36]
G. Behrendt and M. Hale, “A totally asynchronous algorithm for tracking solutions to time-varying convex optimization problems,” in Proceedings of the 22nd IFAC World Congress, 2023, In press; preprint at: <https://arxiv.org/abs/2110.06705>.

[37]
P. Tseng, “On the rate of convergence of a partially asynchronous gradient projection algorithm,” SIAM Journal on Optimization, vol. 1, no. 4, pp. 603–619, 1991.

[38]
J.-S. Pang, “A posteriori error bounds for the linearly-constrained variational inequality problem,” Mathematics of Operations Research, vol. 12, pp. 474–484, August 1987.

[39]
S. M. Robinson, Some continuity properties of polyhedral multifunctions.1em plus 0.5em minus 0.4emSpringer, 1981.

[40]
Z.-Q. Luo and P. Tseng, “On the linear convergence of descent methods for convex essentially smooth minimization,” SIAM Journal on Control and Optimization, vol. 30, no. 2, pp. 408–425, 1992.

[41]
D. Drusvyatskiy and A. S. Lewis, “Error bounds, quadratic growth, and linear convergence of proximal methods,” Mathematics of Operations Research, vol. 43, no. 3, pp. 919–948, 2018.

[42]
H. Zhang, “The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth,” Optimization Letters, vol. 11, pp. 817–833, 2017.

[43]
A. Simonetto, A. Koppel, A. Mokhtari, G. Leus, and A. Ribeiro, “Decentralized prediction-correction methods for networked time-varying convex optimization,” IEEE Transactions on Automatic Control, vol. 62, no. 11, pp. 5724–5738, 2017.

[44]
R. S. Russell, “Non-linear f-16 simulation using simulink and matlab,” University of Minnesota, 2003.

[45]
W. Cheney and A. A. Goldstein, “Proximity maps for convex sets,” Proceedings of the American Mathematical Society, vol. 10, no. 3, pp. 448–450, 1959.