# Gradient-Type Methods For Decentralized Optimization Problems With Polyak-
Łojasiewicz Condition Over Time-Varying Networks 111The work was supported by
the strategic academic leadership program ”Priority 2030” (Agreement
075-02-2021-1316 30.09.2021).

Ilya Kuruzova and Mohammad Alkousaa,b and Fedor Stonyakina,c and Alexander
Gasnikova,b,d CONTACT Ilya Kuruzov. Email<EMAIL_ADDRESS>aMoscow
Institute of Physics and Technology, Dolgoprudny, Russia; bNational Research
University Higher School of Economics, Moscow, Russia; cV. Vernadsky Crimean
Federal University, Simferopol, Republic of Crimea; dISP RAS Research Center
for Trusted Artificial Intelligence

###### Abstract

This paper focuses on the decentralized optimization (minimization and saddle
point) problems with objective functions that satisfy Polyak-Łojasiewicz
condition (PL-condition). The first part of the paper is devoted to the
minimization problem of the sum-type cost functions. In order to solve a such
class of problems, we propose a gradient descent type method with a consensus
projection procedure and the inexact gradient of the objectives. Next, in the
second part, we study the saddle-point problem (SPP) with a structure of the
sum, with objectives satisfying the two-sided PL-condition. To solve such SPP,
we propose a generalization of the Multi-step Gradient Descent Ascent method
with a consensus procedure, and inexact gradients of the objective function
with respect to both variables. Finally, we present some of the numerical
experiments, to show the efficiency of the proposed algorithm for the robust
least squares problem.

###### keywords:

Distributed optimization; non-convex optimization; saddle-point problem; PL-
condition

††articletype: ARTICLE TEMPLATE

##  1 Introduction

In this paper, firstly we study a sum-type minimization problem

$\min_{x\in\mathbb{R}^{d}}\left\\{f(x):=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x)\right\\},$
(1)

where the functions $f_{i}$ are generally non-convex and stored separately by
nodes in communication network, which is represented by an non-directed graph
$\mathcal{G}=(E,V)$. The graph $\mathcal{G}$, possibly, can have changing over
time structure. This problem, where the object function depends on distributed
data is typed as a decentralized optimization problem. We assume that $f$ is
satisfied the well-known Polyak-Łojasiewicz condition (for brevity, we write
PL-condition). This condition was originally introduced by Polyak [26], who
proved that it is sufficient to show the global linear convergence rate for
the gradient descent without assuming convexity. PL-condition is very well
studied by many researchers in many different works for many different
settings of optimization problems and has been theoretically verified for
objective functions of optimization problems arising in many practical
problems. For example, it has been proven to be true for objectives of over-
parameterized deep networks [5], learning LQR models [8], phase retrieval
[36], Generative adversarial imitation learning of linear quadratic (see
Example 3.1 in [3]). More discussions of PL-condition and many other simple
problems can be found in [14].

This type of problems arises in different areas: distributed machine learning
[16], resource allocation problem [12] and power system control [29].

The problem (1) can be reformulated as a problem with linear constraints. For
this, let us assign each agent in the network a personal copy of parameter
vector $x_{i}\in\mathbb{R}^{d}$ (column vector) and introduce

$\mathbf{X}:=\left(x_{1}^{\top}\,\ldots\;x_{n}^{\top}\right)^{\top}\in\mathbb{R}^{n\times
d},\quad F(\mathbf{X})=\sum_{i=1}^{n}f_{i}\left(x_{i}\right).$ (2)

Now we equivalently rewrite problem (1) as

$\min_{\mathbf{X}\in\mathbb{R}^{n\times
d}}F(\mathbf{X})=\sum_{i=1}^{n}f_{i}(x_{i}),\quad\text{s.t.}\;\;x_{1}=\dots=x_{n},$
(3)

where it has the same optimal value as problem (1). This reformulation
increases the number of variables, but induces additional constraints at the
same time.

Let us denote the set of consensus constraints
$\mathcal{C}=\\{\mathbf{X}|x_{1}=\dots=x_{n}\\}$. Also, for each
$\mathbf{X}\in\mathbb{R}^{n\times d}$ denote the average of its columns
$\overline{x}=\frac{1}{n}\sum_{i=1}^{n}x_{i}\in\mathbb{R}^{d}$ and introduce
its projection onto constraint set

$\overline{\mathbf{X}}=\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\mathbf{X}=\Pi_{\mathcal{C}}(\mathbf{X})=\left(\overline{x}^{\top}\,\ldots\;\overline{x}^{\top}\right)^{\top}\in\mathbb{R}^{n\times
d}.$

Note that $\mathcal{C}$ is a linear subspace in $\mathbb{R}^{n\times d}$, and
therefore projection operator $\Pi_{\mathcal{C}}$ is linear.

Secondly, we study the saddle-point problem with a structure of the sum

$\min_{x\in\mathbb{R}^{d_{x}}}\max_{y\in\mathbb{R}^{d_{y}}}\left\\{\phi(x,y)=\frac{1}{n}\sum\limits_{i=1}^{n}\phi_{i}(x,y)\right\\},$
(4)

where functions $\phi_{i}(\cdot,\cdot)$ are non-convex (with respect to the
variable $x$ for each $y$) and smooth (i.e. with Lipschitz-continuous
gradient). These functions are written separately in different nodes in the
communication network, which is represented by a non-directed graph
$\mathcal{G}$.

Problems of type (4) arise in many applications, such that Generative
adversarial network [9], adversarial training [17] and fair training [3]. In
our work with problem (4), we assume that $\phi(\cdot,y)$ and $-\phi(x,\cdot)$
satisfy the PL-condition (see Assumption (2.2), below).

Let $y(x):=\arg\max_{y\in\mathbb{R}^{d_{y}}}\phi(x,y)$, and let we set
$f_{i}(x):=\phi_{i}(x,y(x))$, then problem (4) can be rewritten in the form of
the minimization problem (1), i.e.

$\min_{x\in\mathbb{R}^{d_{x}}}\left\\{\max_{y\in\mathbb{R}^{d_{y}}}\left\\{\phi(x,y)=\frac{1}{n}\sum\limits_{i=1}^{n}\phi_{i}(x,y)\right\\}\right\\}=\min_{x\in\mathbb{R}^{d_{x}}}\left\\{f(x):=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x)\right\\}.$
(5)

Let $\mathcal{C}_{x}:=\left\\{\mathbf{X}\in\mathbb{R}^{n\times
d_{x}}|x_{1}=\dots=x_{n}\right\\}$,
$\mathcal{C}_{y}:=\left\\{\mathbf{Y}\in\mathbb{R}^{n\times
d_{y}}|y_{1}=\dots=y_{n}\right\\}$ and
$\Phi(\mathbf{X},\mathbf{Y}):=\sum\limits_{i=1}^{n}\phi_{i}(x_{i},y_{i})$. So,
we can rewrite (4), in the similar way like [30, 32], in the following form

$\min_{\mathbf{X}\in\mathcal{C}_{x}}\max_{\mathbf{Y}\in\mathcal{C}_{y}}\Phi(\mathbf{X},\mathbf{Y}).$
(6)

Similarly to the first proposed minimization problem (1), note that the
problem (4), also can be rewritten in the same form

$\min_{\mathbf{X}\in\mathcal{C}_{x}}F(\mathbf{X})=\sum_{i=1}^{n}f_{i}(x_{i}).$
(7)

So, for solving the problem (5) (which is equivalent to problem (6)), we can
try to use some gradient type algorithms, at each iteration of the used
algorithm, we calculate the inexact gradient of $\phi(x,\cdot)$ for each
$x\in\mathbb{R}^{d_{x}}$ in order to solve the (inner) maximization problem in
(5).

In practice, we mention to Multi-step Gradient Descent Ascent (MGDA) algorithm
and its modifications, which are widely used to solve the problem (4) (see
e.g. [9, 10, 21]), as important algorithms for the considered type of saddle-
point problems. In [23], authors demonstrate the effectiveness of MGDA on a
class of games in which one of the players satisfies the PL-condition and
another player has a general non-convex structure. At the same time, [40]
shows that one step of gradient descent ascent demonstrates good performance
and has theoretical guarantees for convergence in two-sided PL-games.

In the end, we mention that the main difference between distributed problems
from usual optimization problems is to keep every agent’s vectors to their
average. It is approached through communication steps, where the communication
can be performed in different scenarios. In our work, we will consider the
time-varying network with changeable edges set and use the standard consensus
procedure (see Subsec. 2.3) when the agent’s vectors are averaged by
multiplying by a weighted matrix of the graph at the current moment.

###  1.1 Related works

The decentralized algorithm makes two types of steps: local updates and
information exchange. Local steps may use gradient [24, 35, 27, 28, 41, 18] or
sub-gradient [25] computations. In primal-only methods, the agents compute
gradients of their local functions and alternate taking gradient steps and
communication procedures. Under cheap communication costs, it may be
beneficial to replace a single consensus iteration with a series of
information exchange rounds. Such methods as MSDA [34], D-NC [13] and Mudag
[41] employ multi-step gossip procedures. In order to achieve acceptable
complexity bounds, one may distribute accelerated methods directly [28, 41,
18, 13, 6] or use a Catalyst framework [19]. Accelerated methods meet the
lower complexity bounds for decentralized optimization [11, 20, 34].

Consensus restrictions $x_{1}=\ldots=x_{n}$ may be treated as linear
constraints, thus allowing for a dual reformulation of problem (1). Dual-based
methods include dual ascent and its accelerated variants [34, 39, 42, 37].
Primal-dual approaches like ADMM [2, 38] are also implementable in
decentralized scenarios. In [35], the authors developed algorithms for non-
smooth convex objectives and provided lower complexity bounds for this case,
as well.

Changing topology for time-varying networks requires new approaches to
decentralized methods and a more complicated theoretical analysis. The first
method with provable geometric convergence was proposed in [24]. Such primal
algorithms as Push-Pull Gradient Method [27] and DIGing [24] are robust to
network changes and have theoretical guarantees of convergence over time-
varying graphs. Recently, a dual method for time-varying architectures was
introduced in [22].

In [33], it was studied the problem of decentralized optimization with
strongly convex smooth objective functions. The authors investigated
accelerated deterministic algorithms under time-varying network constraints
with a consensus projection procedure. The distributed stochastic optimization
over time-varying graphs with consensus projection procedure was studied in
[31]. The consensus projection procedure made it possible to use more
acceptable parameters of smoothness and strong convexity in the complexity
estimates. The main goal of this paper is to investigate a similar consensus
projection approach for problems with PL-condition. Note that approach [31,
33] is based on the well-known concept of the inexact $(\delta,L,\mu)$-oracle.
But in the PL-case, we will use inexact gradients with additive noise to
describe the consensus projection procedure.

###  1.2 Our contributions

Summing up, the contribution of this paper is as follows.

  * •

We study the sum-type minimization problem when the objective function
satisfies the PL-condition. In order to solve a such class of problems, we
propose a gradient descent type method with consensus projection procedure
(see Algorithm 2) and access to only inexact gradient. We consider two cases
of gradient inexactness: the bounded deterministic inexactness and the sum of
random noise with deterministic bias. We estimated the sufficient
communication steps and iterations number to approach the required quality
with respect to the function and the distance between the agent’s vectors and
their average for both cases.

  * •

We study the decentralized saddle-point problem (with the structure of a sum)
when the objective function satisfies the two-sided PL-condition. For solving
a such generalized class of problems, we proposed a generalization of the MGDA
method (see Algorithm 3) with consensus procedure. We provided an estimation
for the sufficient number of iterations for inner and outer loops to approach
the acceptable quality with respect to the function. Also, we estimate the
communication complexity to a distance between agent’s vectors and their
average for both cases to be small enough. Additionally, we research the
influence of interference on the convergence of the proposed Algorithm 3. We
suppose that the inexactness in the gradient can be separated into
deterministic noise with the bounded norm and zero-mean noise with the finite
second moment.

  * •

We present some numerical experiments, which demonstrate the effectiveness of
the proposed algorithm, for the Robust Least Squares problem.

##  2 Proposed algorithms and the main results

Throughout the paper, $\langle\cdot,\cdot\rangle$ denotes the inner product of
vectors or matrices. Correspondingly, by $\|\cdot\|$, we denote the $2$-norm
for vectors or the Frobenius norm for matrices.

###  2.1 Assumptions for the problems under consideration

At the first, for the minimization problem (1) (or its equivalent (3)), we
assume

######  Assumption 2.1 (Lipschitz smoothness).

For every $i=1,\ldots,n$, the function $f_{i}$ is $L_{i}$-smooth, for some
$L_{i}>0$.

Under this assumption, we find that the function $F(\mathbf{X})$ (2) is
$L_{l}$-smooth on $\mathbb{R}^{n\times d}$, where $L_{l}=\max\limits_{1\leq
i\leq n}L_{i}$, and $L_{g}$-smooth on $\mathcal{C}$, where
$L_{g}=\frac{1}{n}\sum\limits_{i=1}^{n}L_{i}$. The constant $L_{l}$ is called
a local constant and $L_{g}$ is called a global constant.

######  Assumption 2.2 (PL-condition).

The function $f$ meets PL-condition, i.e. it holds the following inequality

$f(x)-f^{*}\leq\frac{1}{2\mu}\|\nabla f(x)\|^{2},\quad\forall
x\in\mathbb{R}^{d},$ (8)

for some $\mu>0$, and $f^{*}$ is the optimal value of the function $f$.

Also under this assumption, we find that $f$ satisfies the quadratic growth
condition (QG-condition)

$\|x-x^{*}\|^{2}\leq\frac{2}{\mu}\left(f(x)-f^{*}\right);\quad\forall
x\in\mathbb{R}^{d},$ (9)

where $x^{*}$ is the nearest point to the optimal solution of the minimization
problem under consideration.

At the second, for the saddle-point problem (4), let we introduce the
following assumption.

######  Assumption 2.3 (Lipschitz smoothness).

For every $i=1,\ldots,n$, the function $\phi_{i}(\cdot,\cdot)$ is
differentiable with respect to its both variables and smooth, i.e. the
following inequalities hold

$\displaystyle\left\|\nabla_{x}\phi_{i}(x_{1},y_{1})-\nabla_{x}\phi_{i}(x_{2},y_{2})\right\|\leq
L_{xx,i}\|x_{1}-x_{2}\|+L_{xy,i}\|y_{1}-y_{2}\|,$
$\displaystyle\left\|\nabla_{y}\phi_{i}(x_{1},y_{1})-\nabla_{y}\phi_{i}(x_{2},y_{2})\right\|\leq
L_{yx,i}\|x_{1}-x_{2}\|+L_{yy,i}\|y_{1}-y_{2}\|,$

for all $x_{1},x_{2}\in\mathbb{R}^{d_{x}},y_{1},y_{2}\in\mathbb{R}^{d_{y}}$
and $L_{xx,i},L_{yy,i},L_{xy,i},L_{yx,i}\in\mathbb{R}_{+}^{*}$.

Note, that if Assumption 2.3 is satisfied, then it will be also satisfied for
the function $\Phi(\cdot,\cdot)$ on $\mathbb{R}^{n\times
d_{x}}\times\mathbb{R}^{n\times d_{y}}$ with constants
$L_{xx,g},L_{yx,g},L_{xy,g},L_{yy,g}$, and on
$\mathcal{C}_{x}\times\mathcal{C}_{y}$, with constants
$L_{xx,l},L_{yx,l},L_{xy,l},L_{yy,l}$, where $L_{ab,l}=\max\limits_{1\leq
i\leq n}L_{ab,i}$, $L_{ab,g}=\frac{1}{n}\sum\limits_{i=1}^{n}L_{ab,i}$, and
$ab\in\\{xx,yy,xy,yx\\}$.

###  2.2 Inexact gradient oracle

We will divide the inexactness of the gradient into random noise and a
deterministic bias. To describe this noise, we will use the following
definition.

######  Definition 2.4 ($(\delta,\sigma^{2})$-biased gradient oracle).

Let $\delta>0,\sigma>0$ and $\xi$ be a random variable with probability
distribution $\mathcal{D}$. $(\delta,\sigma^{2})$-biased gradient oracle is a
map $\mathbf{g}:\mathbb{R}^{d}\times\mathcal{D}\rightarrow\mathbb{R}^{d}$,
such that

$\left\|\mathbb{E}_{\xi}\mathbf{g}(x,\xi)-\nabla
f(x)\right\|\leq\delta,\quad\mathbb{E}_{\xi}\left\|\mathbf{g}(x,\xi)-\mathbb{E}_{\xi}\mathbf{g}(x,\xi)\right\|^{2}\leq\sigma^{2}.$

In other words, we suppose that the inexactness of the gradient contains two
parts: bias and noise. At that, bias has bounded norm and noise has bounded
the second moment.

###  2.3 Consensus procedure

We consider a sequence of non-directed communication graphs
$\left\\{\mathcal{G}^{k}=\left(V,E^{k}\right)\right\\}_{k=0}^{\infty}$ and a
sequence of corresponding mixing matrices
$\left\\{\mathbf{W}^{k}\right\\}_{k=0}^{\infty}$ associated with it. We assume
the following assumption.

######  Assumption 2.5.

Mixing matrix sequence $\\{\mathbf{W}^{k}\\}_{k=0}^{\infty}$ satisfies the
following properties:

  * •

(Decentralized property) If $(i,j)\notin E^{k}$, then
$[\mathbf{W}^{k}]_{ij}=0$.

  * •

(Double stochasticity) $\mathbf{W}^{k}\mathbf{1}_{n}=\mathbf{1}_{n}$, and
$\mathbf{1}_{n}^{\top}\mathbf{W}^{k}=\mathbf{1}_{n}^{\top}$.

  * •

(Contraction property) There exist $\tau\in\mathbb{Z}_{++}$ and
$\lambda\in(0,1)$ such that for every $k\geq\tau-1$, it holds the following
inequality

$\left\|\mathbf{W}^{k}_{\tau}\mathbf{X}-\overline{\mathbf{X}}\right\|\leq(1-\lambda)\left\|\mathbf{X}-\overline{\mathbf{X}}\right\|,$

where $\mathbf{W}^{k}_{\tau}=\mathbf{W}^{k}\dots\mathbf{W}^{k-\tau+1}$.

The contraction property in Assumption (2.5) generalizes several assumptions
in the literature.

  1. 1.

Time-static connected graph: $\mathbf{W}^{k}=\mathbf{W}$. In this classical
case we have $\lambda=1-\sigma_{2}(\mathbf{W})$, where
$\sigma_{2}(\mathbf{W})$ denotes the second largest singular value of
$\mathbf{W}$.

  2. 2.

Sequence of connected graphs: every $\mathcal{G}_{k}$ is connected. In this
scenario $\lambda=1-\sup\limits_{k\geq
0}\sigma_{2}\left(\mathbf{W}^{k}\right)$.

  3. 3.

$\tau$-connected graph sequence (i.e. for every $k\geq 0$ graph
$\mathcal{G}_{\tau}^{k}=\left(V,E\right)$, where $E=E^{k}\cup
E^{k+1}\cup\ldots\cup E^{k+\tau-1}$, is connected [24]). For $\tau$-connected
graph sequences it holds

$1-\lambda=\sup_{k\geq
0}\sigma_{\max}\left(\mathbf{W}_{\tau}^{k}-\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\right).$

A stochastic variant of this contraction property is also studied in [15].

During every communication round, the agents exchange information according to
the rule

$x_{i}^{k+1}=w_{ii}^{k}+\sum_{(i,j)\in E^{k}}w_{ij}^{k}x_{j}^{k}\text{. }$

In matrix form, this update rule writes as
$\mathbf{W}^{k+1}=\mathbf{W}^{k}\mathbf{X}^{k}$. The contraction property in
Assumption (2.5) is needed to ensure geometric convergence of Algorithm 1 to
the average of nodes’ initial vectors, i.e. to $\overline{x}_{0}$. In
particular, the contraction property holds for $\tau$-connected graphs with
Metropolis weights choice for $\mathbf{W}^{k}$, i.e.

$\left[\mathbf{W}^{k}\right]_{ij}=\begin{cases}1/\left(1+\max\left\\{d_{i}^{k},d_{j}^{k}\right\\}\right)&\text{if}\;\;(i,j)\in
E^{k},\\\ 0&\text{if}\;\;(i,j)\notin E^{k},\\\ 1-\sum_{(i,m)\in
E^{k}}\left[\mathbf{W}^{k}\right]_{im}&\text{if}\;\;i=j,\end{cases}$

where $d_{i}^{k}$ denotes the degree of node $i$ in graph $\mathcal{G}^{k}$.

Algorithm 1 Consensus.

0: Initial point $\mathbf{Z}^{0}\in\mathcal{C}$, number of communication
rounds $T$.

1: Take current time moment $t_{0}$ from global variable.

2: for $k=0,\ldots,T-1$ do

3: $\mathbf{Z}^{k+1}:=\mathbf{W}^{t_{0}+k}\,\mathbf{Z}^{k}$.

4: end for

5: Update global variable with current time moment: $t_{0}=t_{0}+T$.

6: return $\mathbf{Z}^{T}$.

###  2.4 The Proposed algorithm for PL-minimization problem

In this subsection, we focus on the minimization problem 3 (which is
equivalent to problem (1)). For this, we propose an algorithm (listed as
Algorithm 2) using the inexact gradient. The proposed algorithm is a gradient
type method, that uses a $(\delta,0)$-biased gradient oracle
$\widetilde{\nabla}F(\mathbf{X})$ without noise. This condition can be
rewritten as
$\left\|\widetilde{\nabla}F(\mathbf{X})-{\nabla}F(\mathbf{X})\right\|\leq\delta$,
where $\nabla F(\mathbf{X})=\left(\nabla f_{1}(x_{1}),\ldots,\nabla
f_{n}(x_{n})\right)^{\top}\in\mathbb{R}^{d\times n}$ denotes the gradient of
$F$ at $\mathbf{X}$. Note, that the considered inexact gradient in Algorithm 2
is a usual additively inexact gradient.

Algorithm 2 Decentralized gradient descent with consensus subroutine.

0: Starting point $\mathbf{X}^{0}\in\mathcal{C}$, step size $\gamma>0$, number
of steps $N$, the sequence of number for communication rounds
$\\{T^{k}\\}_{k=0}^{N-1}$ in consensus.

1: for $k=0,\ldots,N-1$ do

2:
$\mathbf{Z}^{k+1}=\mathbf{X}^{k}-\gamma\widetilde{\nabla}F(\mathbf{X}^{k})$,

3: $\mathbf{X}^{k+1}=\text{Consensus}(\mathbf{Z}^{k+1},T^{k})$.

4: end for

5: return $\mathbf{X}^{N}$.

Indeed, after the $k$-th iteration of Algorithm 2 we have a point
$\mathbf{X}^{k+1}\approx\overline{\mathbf{X}}^{k+1}=\overline{\mathbf{X}}^{k}-\gamma\overline{\widetilde{\nabla}F}(\mathbf{X}^{k})$.
If we assume that at each iteration, $\mathbf{X}^{k}$ is close enough to its
projection on $\mathcal{C}$, i.e.
$\left\|\mathbf{X}^{k}-\overline{\mathbf{X}}^{k}\right\|^{2}\leq\delta^{\prime}$
for some $\delta^{\prime}>0$, then we can estimate the new inexactness and
Lipschitz constant for the gradient of the objective function $F$, where

$\left\|\overline{\widetilde{\nabla}F}({\mathbf{X}}^{k})-\overline{{\nabla}F}(\overline{\mathbf{X}}^{k})\right\|\leq\delta+L_{l}\sqrt{\delta^{\prime}}.$

So, in the fact,
$\overline{\mathbf{X}}^{k+1}=\overline{\mathbf{X}}^{k}-\gamma\overline{\widetilde{\nabla}F}(\mathbf{X}^{k})$
is a variant of gradient method for problem (3) with an additively inexact
gradient. At the same time,
$\overline{x}^{k+1}=\overline{x}^{k}-\gamma\overline{\widetilde{\nabla}f}(x^{k})$
is the usual gradient method for minimizing the function $f$ (i.e. for the
problem (1)) with an additively inexact gradient
$\overline{\widetilde{\nabla}f}(x^{k})=\frac{1}{n}\sum\limits_{i=1}^{n}\widetilde{\nabla}f_{i}(x_{i}^{k})$.
We can estimate its inexactness in the following way

$\left\|\overline{\widetilde{\nabla}f}(x^{k})-\nabla
f(\overline{x}^{k})\right\|^{2}=\frac{1}{n}\left\|\overline{\widetilde{\nabla}F}(\mathbf{X}^{k})-\overline{{\nabla}F}(\overline{\mathbf{X}}^{k})\right\|^{2}=\frac{\left(\delta+L_{l}\sqrt{\delta^{\prime}}\right)^{2}}{n}.$
(10)

Using Assumption 2.2, inequality (10) and taking step size
$\gamma=\frac{1}{L_{g}}$, we can estimate the convergence rate of Algorithm 2
with respect to the function $f$, as follows

$f(\overline{x}^{k})-f^{*}\leq\left(1-\frac{\mu}{L_{g}}\right)^{k}\left(f(\overline{x}^{0})-f^{*}\right)+\frac{\Delta^{2}}{2\mu
n},$ (11)

where $\Delta=\delta+L_{l}\sqrt{\delta^{\prime}}$. Although at each iteration
of Algorithm 2 we have access only to $\mathbf{X}^{k}$.

Now, let us find the sufficient communication step such that the following
expression is true

$\left\|\mathbf{X}^{k}-\overline{\mathbf{X}}^{k}\right\|\leq\sqrt{\delta^{\prime}}\Longrightarrow\left\|\mathbf{X}^{k+1}-\overline{\mathbf{X}}^{k+1}\right\|\leq\sqrt{\delta^{\prime}}.$
(12)

By the contraction property (see Assumption (2.5)) and using that
$\overline{\mathbf{Z}}^{k+1}=\overline{\mathbf{X}}^{k+1}$, we have

$\left\|\mathbf{X}^{k+1}-\overline{\mathbf{X}}^{k+1}\right\|\leq(1-\lambda)^{\left\lfloor\frac{T_{k}}{\tau}\right\rfloor}\left\|\overline{\mathbf{X}}^{k+1}-\mathbf{Z}^{k+1}\right\|.$
(13)

Let us estimate the right hand side of inequality (13).

$\displaystyle\left\|\overline{\mathbf{X}}^{k+1}-\mathbf{Z}^{k+1}\right\|\leq\left\|\overline{\mathbf{X}}^{k}-\mathbf{Z}^{k+1}\right\|\leq\left\|\overline{\mathbf{X}}^{k}-\mathbf{X}^{k}\right\|+\gamma\left\|\widetilde{\nabla}F(\mathbf{X}^{k})\right\|$
(14)
$\displaystyle\leq\sqrt{\delta^{\prime}}+\gamma\left\|\widetilde{\nabla}F(\mathbf{X}^{k})-\nabla
F(\overline{\mathbf{X}}^{k})\right\|+\gamma\left\|\nabla
F(\overline{\mathbf{X}}^{k})-\nabla
F(\overline{\mathbf{X}}^{*})\right\|\;+\gamma\left\|\nabla
F(\overline{\mathbf{X}}^{*})\right\|$
$\displaystyle\leq\sqrt{\delta^{\prime}}+\gamma\Delta+\gamma
L_{g}\left\|\overline{\mathbf{X}}^{k}-\overline{\mathbf{X}}^{*}\right\|+\gamma\left\|\nabla
F(\overline{\mathbf{X}}^{*})\right\|.$

From quadratic growth condition (9), we have

$\left\|\overline{\mathbf{X}}^{k}-\overline{\mathbf{X}}^{*}\right\|^{2}=n\left\|\overline{x}^{k}-\overline{x}^{*}\right\|^{2}\leq\frac{2n}{\mu}\left(f(\overline{x}^{k})-f^{*}\right).$

Further, using the convergence rate (11) we can estimate the value of
$\left\|\overline{\mathbf{X}}^{k}-\overline{\mathbf{X}}^{*}\right\|^{2}$ in
(14), as the following

$\left\|\overline{\mathbf{X}}^{k}-\overline{\mathbf{X}}^{*}\right\|^{2}\leq\frac{2}{\mu}\left(1-\frac{\mu}{L_{g}}\right)^{k+1}\left(F(\overline{\mathbf{X}}^{0})-F^{*}\right)+\frac{\Delta^{2}}{\mu^{2}}.$

Therefore we have
$\left\|\overline{\mathbf{X}}^{k+1}-\mathbf{Z}^{k+1}\right\|\leq\sqrt{D}$,
where $D$ is a constant such that:

$\sqrt{D}=\gamma\left\|\nabla
F(\overline{\mathbf{X}}^{*})\right\|+\sqrt{\delta^{\prime}}+\left(\gamma+\frac{1}{\mu}\right)\Delta+\gamma
L_{g}\sqrt{\frac{2}{\mu}\left(1-\frac{\mu}{L_{g}}\right)\left(F(\overline{\mathbf{X}}^{0})-F^{*}\right)}.$
(15)

where $\gamma=\frac{1}{L_{g}}$.

Thus, for
$T_{k}=\tau\left\lceil\frac{1}{2\lambda}\log\frac{D}{\delta^{\prime}}\right\rceil$,
(12) will be satisfied. So, uniting (11) and the result about communication
steps per iteration, we obtain the following theorem.

######  Theorem 2.6.

Choose some $\varepsilon>0$, define $D>0$ as in (15), and set
$\Delta=\delta+L_{l}\sqrt{\delta^{\prime}},\gamma=\frac{1}{L_{g}}$. Under
Assumptions (2.1) and (2.2), Algorithm 2 requires

$N=\left\lceil\frac{L_{g}}{\mu}\log\left(\frac{f(\overline{x}^{0})-f^{*}}{\varepsilon}\right)\right\rceil$

gradient computation at each node,
$T=\tau\left\lceil\frac{1}{2\lambda}\log\frac{D}{\delta^{\prime}}\right\rceil$
communication steps at each iteration and $N_{tot}=N\cdot T$ communication
steps to yield $\mathbf{X}^{N}$ such that

$f(\overline{x}^{N})-f^{*}\leq\varepsilon+\frac{\Delta^{2}}{2\mu
n},\quad\text{and}\quad\left\|\mathbf{X}^{N}-\overline{\mathbf{X}}^{N}\right\|\leq\sqrt{\delta^{\prime}}.$
(16)

Further, we consider the case when Algorithm 2 uses
$(\delta,\sigma^{2})$-biased gradient oracle $\widetilde{\nabla}F(\mathbf{X})$
for arbitrary values $\delta$ and $\sigma$.

As in the previous, after the $k$-th iteration of Algorithm 2 we have a point
$\mathbf{X}^{k+1}\approx\overline{\mathbf{X}}^{k+1}=\overline{\mathbf{X}}^{k}-\gamma\overline{\widetilde{\nabla}F}(\mathbf{X}^{k})$.
In this case, if we consider $\overline{\widetilde{\nabla}F}(\mathbf{X}^{k})$
as an approximation of the exact gradient $\overline{\nabla
F}(\overline{\mathbf{X}}^{k})$, then will have three inexactness: inexactness
caused by $\overline{\mathbf{X}}^{k}\neq\mathbf{X}^{k}$, bias at point
$\mathbf{X}^{k}$ and zero-mean noise at $\mathbf{X}^{k}$. Note, that
$\mathbf{X}^{k}$ is also a random variable.

Let us estimate the bias in $\overline{\widetilde{\nabla}F}(\mathbf{X}^{k})$
at the given point $\overline{\mathbf{X}}^{k}$, as follows

$\displaystyle\sqrt{n}\left\|\mathbb{E}_{x,\xi}\overline{\widetilde{\nabla}f}(x^{k})-{{\nabla}f}(\overline{x}^{k})\right\|=\left\|\mathbb{E}_{\mathbf{X},\xi}\overline{\widetilde{\nabla}F}(\mathbf{X}^{k})-\overline{{\nabla}F}(\overline{\mathbf{X}}^{k})\right\|$
$\displaystyle\qquad\qquad\qquad\leq\left\|\mathbb{E}_{\mathbf{X},\xi}\overline{\widetilde{\nabla}F}(\mathbf{X}^{k})-\mathbb{E}_{\mathbf{X}}\overline{{\nabla}F}(\mathbf{X}^{k})\right\|+\left\|\mathbb{E}_{\mathbf{X}}\overline{{\nabla}F}(\mathbf{X}^{k})-\overline{{\nabla}F}(\overline{\mathbf{X}}^{k})\right\|$
$\displaystyle\qquad\qquad\qquad\leq\mathbb{E}_{\mathbf{X}}\left\|\mathbb{E}_{\xi}\overline{\widetilde{\nabla}F}(\mathbf{X}^{k})-\overline{{\nabla}F}(\mathbf{X}^{k})\right\|+\mathbb{E}_{\mathbf{X}}\left\|\overline{{\nabla}F}(\mathbf{X}^{k})-\overline{{\nabla}F}(\overline{\mathbf{X}}^{k})\right\|$
$\displaystyle\qquad\qquad\qquad\leq\delta+L_{l}\mathbb{E}_{\mathbf{X}}\left\|\mathbf{X}^{k}-\overline{\mathbf{X}}^{k}\right\|,$

where $\mathbb{E}_{\mathbf{X}}$ and $\mathbb{E}_{\xi}$ mean conditional
mathematical expectations under variable $\mathbf{X}$ and random variable
$\xi$ for the given $\overline{\mathbf{X}}^{k}$. Nevertheless, we can not
guarantee the condition
$\mathbb{E}_{\mathbf{X}}\left\|\mathbf{X}^{k}-\overline{\mathbf{X}}^{k}\right\|^{2}\leq{\delta^{\prime}}$.
On the other hand, we can construct Algorithm 2 in such a way that
$\mathbb{E}\left\|\mathbf{X}^{k}-\overline{\mathbf{X}}^{k}\right\|^{2}\leq{\delta^{\prime}}$
at all iterations. When we assume, that Consensus procedure 1 guarantees
$\mathbb{E}\left\|\mathbf{X}^{k}-\overline{\mathbf{X}}^{k}\right\|^{2}\leq{\delta^{\prime}}$,
we have the following estimation

$\mathbb{E}\left\|\mathbb{E}_{x,\xi}\overline{\widetilde{\nabla}f}(x^{k})-{{\nabla}f}(\overline{x}^{k})\right\|^{2}\leq\frac{2\delta^{2}+2L_{l}^{2}\delta^{\prime}}{n}.$

At the same time, we can estimate the random noise in the similar way (see
Appendix A). So, we can obtain the following statement.

######  Lemma 2.7.

Let us assume that the functions $f_{i}$ meet Assumption 2.1 and for all
$j\leq k$ we have that
$\mathbb{E}\left\|\mathbf{X}^{j}-\overline{\mathbf{X}}^{j}\right\|^{2}\leq\delta^{\prime}$,
where $\\{\mathbf{X}^{j}\\}_{j\leq k}$. Then for the bias and noise in the
inexact gradient $\overline{\widetilde{\nabla}f}(x^{k})$, we have the
following estimations

$\mathbb{E}\left\|\mathbb{E}_{x,\xi}\overline{\widetilde{\nabla}f}(x^{k})-{{\nabla}f}(\overline{x}^{k})\right\|^{2}\leq\frac{2\delta^{2}+2L_{l}^{2}\delta^{\prime}}{n},$

and

$\displaystyle\mathbb{E}\left\|\mathbb{E}_{x,\xi}\overline{\widetilde{\nabla}f}(x^{k})-\overline{\widetilde{\nabla}f}(x^{k})\right\|^{2}\leq\frac{16L_{l}^{2}{\delta^{\prime}}+18\sigma^{2}+16\delta^{2}}{n}.$

Note, the mathematical expectation $\mathbb{E}$ above is not conditional. So,
$\overline{\widetilde{\nabla}f}(x^{k})$ is not a biased gradient oracle in the
sense of Definition 2.4. Nevertheless, we can show that the following gradient
process method

$x_{k}=x_{k-1}-\gamma g(x_{k},\xi),$ (17)

where $g(x_{k},\xi)=\nabla f(x_{k})+n(x_{k},\xi)+b(x^{k})$ is such that
$\mathbb{E}\left\|n(x_{k},\xi)\right\|^{2}\leq\sigma^{2}$ and
$\mathbb{E}\left\|b(x_{k})\right\|^{2}\leq\delta^{2}$. The convergence of such
method is given by the following lemma.

######  Lemma 2.8.

Let $f$ be a function meets PL-condition for a constant $\mu>0$ and be an
$L$-smooth function. The gradient oracle $g(x_{k},\xi)=\nabla
f(x_{k})+n(x_{k},\xi)+b(x^{k})$ is such that
$\mathbb{E}\left\|n(x_{k},\xi)\right\|^{2}\leq\sigma^{2}$ and
$\mathbb{E}\left\|b(x_{k})\right\|^{2}\leq\delta^{2}$. So, when
$\gamma\leq\frac{1}{L}$, we can guarantee that method (17) converges to
$f^{*}$ in the following way:

$\mathbb{E}\left[f(x_{k})-f^{*}\right]\leq\left(1-\gamma\mu\right)^{k}(f(x_{0})-f^{*})+\frac{\delta^{2}}{2\mu}+\frac{L\gamma\sigma^{2}}{2\mu}.$
(18)

In the similar way, like for proof of Theorem 2.6, we can estimate required
consensus steps $T$ for condition
$\mathbb{E}\left\|\mathbf{X}^{k}-\overline{\mathbf{X}}^{k}\right\|^{2}\leq\delta^{\prime}$
(see Appendix C). So, we can state the following theorem.

######  Theorem 2.9.

Let $f$ be a function meets Assumption 2.2, the functions $f_{i}$ meet
Assumption 2.1 and the map $\widetilde{\nabla}F$ be a
$(\delta,\sigma^{2})$-biased gradient oracle. Define value $D$ as

$D=6\gamma^{2}\left\|\nabla
F(\overline{\mathbf{X}}^{*})\right\|^{2}+2\delta^{\prime}+6\left(\gamma^{2}+\frac{1}{\mu^{2}}\right)\Delta^{2}+\frac{12\gamma^{2}L_{g}^{2}}{\mu}\left(1-\frac{\mu}{L_{g}}\right)\left(F(\overline{\mathbf{X}}^{0})-F^{*}\right).$

where
$\Delta^{2}=18\left(L_{l}^{2}{\delta^{\prime}}+\sigma^{2}+\delta^{2}\right)$
and step-size $\gamma=\frac{1}{L_{g}}$. Then Algorithm 2 requires
$N=\left\lceil\frac{L_{g}}{\mu}\log\left(\frac{f(\overline{x}^{0})-f^{*}}{\varepsilon}\right)\right\rceil$
gradient computation at each node,
$T=\tau\left\lceil\frac{1}{2\lambda}\log\frac{D}{\delta^{\prime}}\right\rceil$
communication steps in each iteration and $N_{tot}=N\cdot T$ communication
steps to yield $\mathbf{X}^{N}$ such that

$\mathbb{E}f(\overline{x}^{N})-f^{*}\leq\varepsilon+\frac{\Delta^{2}}{2\mu
n},\quad\text{and}\quad\mathbb{E}\left\|\mathbf{X}^{N}-\overline{\mathbf{X}}^{N}\right\|^{2}\leq{\delta^{\prime}}.$
(19)

######  Remark 1.

By using the step-size $\gamma<\frac{1}{L_{g}}$ small enough, we can improve
accuracy level on function in (19). According to Lemma 2.8, for step-size
$\gamma$, Algorithm 2 can converge with the rate as in the inequality (19),
where

$\Delta^{2}=2\delta^{2}+L_{l}^{2}\delta^{\prime}+L_{g}\gamma\left(16L_{l}^{2}{\delta^{\prime}}+18\sigma^{2}+16\delta^{2}\right).$

But in this case the number of required iterations $N$ increases in
$\frac{L_{g}}{\gamma}$ times. Note, that parameter $D$ does not change.

###  2.5 Algorithm for distributed saddle point problems: PL–PL case

In this subsection, we will consider a generalization of Algorithm 2 (see
Algorithm 3) for the saddle-point problem (4) (or its equivalent (6)).

Additionally, we will research the influence of interference on the
convergence of the proposed Algorithm 3. We suppose, that the inexactness in
the gradient can be separated into deterministic noise with the bounded norm
and zero-mean noise with the finite second moment. Note, that the influence of
such inexactness for Gradient Descent Ascent is well researched both in
convex-concave and in non-convex-non-concave saddle point problems under
various assumptions (see e.g. [40], [4]). Also, the results of [23] can be
generalized for stochastic oracle (see Remark 3.8 in [23]).

At each iteration, the proposed method optimizes by an inner variable
$\mathbf{Y}$ for the fixed outer variable $\mathbf{X}$ by Algorithm 2. After
that, it makes one step of Algorithm 3 by outer variable. So, we obtain the
well-known Multi-step Gradient Descent Ascent method with a consensus
subroutine after each gradient method step.

Algorithm 3 Multi-step Gradient Descent Ascent with consensus (MGDA).

0: Number of inner and outer steps $N_{x},N_{y}$, starting point
$(\mathbf{X}^{0},\mathbf{Y}^{0})$, step sizes $\gamma_{x}$ and $\gamma_{y}$,
the sequences of steps $\\{T^{k}_{x}\\}_{k}$ and $\\{T^{k,j}_{y}\\}_{k,j}$ in
consensus.

1: for $k=0,\dots,N_{x}-1$ do

2: $\hat{\mathbf{Y}}^{0}:=\mathbf{Y}^{k}$.

3: for $j=0,\dots,N_{y}-1$ do

4:
$\mathbf{Z}_{y}^{j+1}:={\mathbf{Y}}^{j}+\gamma_{y}\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X}^{k},\hat{\mathbf{Y}}^{j})$.

5: $\hat{\mathbf{Y}}^{j+1}:=\text{Consensus}(\mathbf{Z}_{y}^{j},T^{k,j}_{y})$.

6: end for

7: ${\mathbf{Y}}^{k+1}:=\hat{\mathbf{Y}}^{N_{y}}$.

8:
${\mathbf{Z}}_{x}^{k+1}:=\mathbf{X}^{k}-\gamma_{x}\widetilde{\nabla}_{\mathbf{X}}\Phi(\mathbf{X}^{k},\mathbf{Y}^{k+1})$.

9: ${\mathbf{X}}^{k+1}:=\text{Consensus}(\mathbf{Z}_{x}^{k},T^{k}_{x})$.

10: end for

11: return $\mathbf{X}^{N_{x}},{\mathbf{Y}}^{N_{x}}$.

We suppose that functions $\phi(\cdot,y)$ and $-\phi(x,\cdot)$ satisfy the PL-
condition (Assumption 2.2). So, for each $x$ and $y$ the following
inequalities hold

$\displaystyle\phi(x,y)-\min_{x\in\mathbb{R}^{d_{x}}}\phi(x,y)\leq\frac{2}{\mu_{x}}\|\nabla_{x}\phi(x,y)\|^{2},$
(20)
$\displaystyle\max_{y\in\mathbb{R}^{d_{y}}}\phi(x,y)-\phi(x,y)\leq\frac{2}{\mu_{y}}\|\nabla_{y}\phi(x,y)\|^{2}.$
(21)

Now, let us introduce functions in $\mathbf{Y}$ for fixed variable
$\mathbf{X}$: $g_{\overline{x}}(y)=\phi(\overline{x},y)$ and
$G_{\overline{\mathbf{X}}}(\mathbf{Y})=\Phi(\overline{\mathbf{X}},\mathbf{Y})$.
For the maximization of $g_{\overline{x}}(y)$ we define
$g^{*}_{x}:=\max_{y\in\mathbb{R}^{d_{y}}}g_{\overline{x}}(y)$.

Note, in the inner iterations, we have the gradient process in the form

$\hat{\mathbf{Y}}^{j}\approx\overline{\hat{\mathbf{Y}}}^{j}=\overline{\hat{\mathbf{Y}}}^{k-1}+\gamma_{y}\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X}^{k},\hat{\mathbf{Y}}^{j}).$

Let $\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})$ be a
$(\delta_{y},0)$-biased gradient oracle for any fixed $\mathbf{X}$. So, we can
decompose the bias component in
$\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X}^{k},\hat{\mathbf{Y}}^{j})$ in
the following way

$\displaystyle\left\|{\widetilde{\nabla}_{\mathbf{Y}}\Phi}(\mathbf{X}^{k},\hat{\mathbf{Y}}^{j})-\nabla_{y}\Phi(\overline{\mathbf{X}}^{k},\overline{\hat{\mathbf{Y}}}^{j})\right\|\leq$
$\displaystyle\left\|{\widetilde{\nabla}_{\mathbf{Y}}\Phi}(\mathbf{X}^{k},\hat{\mathbf{Y}}^{j})-\nabla_{y}\Phi({\mathbf{X}}^{k},{\hat{\mathbf{Y}}}^{j})\right\|$
(22)
$\displaystyle+\left\|\nabla_{y}\Phi({\mathbf{X}}^{k},{\hat{\mathbf{Y}}}^{j})-\nabla_{y}\Phi({\mathbf{X}}^{k},\overline{\hat{\mathbf{Y}}}^{j})\right\|$
$\displaystyle+\left\|\nabla_{y}\Phi({\mathbf{X}}^{k},\overline{\hat{\mathbf{Y}}}^{j})-\nabla_{y}\Phi(\overline{\mathbf{X}}^{k},\overline{\hat{\mathbf{Y}}}^{j})\right\|$

The first term in the right hand side of inequality (22) is not more than
$\delta$. Assuming that
$\left\|\overline{\hat{\mathbf{Y}}^{j}}-\hat{\mathbf{Y}}^{j}\right\|^{2}\leq\delta^{\prime}_{y}$
and
$\left\|\overline{\mathbf{X}}^{k}-\mathbf{X}^{k}\right\|^{2}\leq\delta^{\prime}_{x}$
for any $k,j$, we can estimate the last two terms in (22) as
$L_{yy}\sqrt{\delta^{\prime}_{y}}+L_{yx}\sqrt{\delta^{\prime}_{x}}$. So, we
have the following estimate for bias in the inexact gradient
$\overline{\widetilde{\nabla}_{\mathbf{Y}}\phi}(\mathbf{X}^{k},\hat{\mathbf{Y}}^{j})=\frac{1}{n}\sum\limits_{i=1}^{n}\phi(x_{k,i},\hat{y}^{j}_{i})$:

$\displaystyle\left\|\overline{\widetilde{\nabla}_{\mathbf{Y}}\phi}(\mathbf{X}^{k},\hat{\mathbf{Y}}^{j})-\nabla_{y}\phi(\overline{x}_{k},\overline{\hat{y}}^{j})\right\|$
$\displaystyle\leq\frac{1}{n}\left\|{\widetilde{\nabla}_{Y}\Phi}(\mathbf{X}^{k},\hat{\mathbf{Y}}^{j})-\nabla_{y}\Phi(\overline{\mathbf{X}}^{k},\overline{\hat{\mathbf{Y}}}^{j})\right\|$
$\displaystyle\leq\frac{(\delta+L_{yy,l}\sqrt{\delta^{\prime}_{y}}+L_{yx,l}\sqrt{\delta^{\prime}_{x}})^{2}}{n}.$

Finally, note, that $g_{x}$ is $L_{yy,g}$ smooth function. So, the convergence
by $\mathbf{Y}$ is described by Theorem 2.9. So, we have that for any outer
iteration $k$, after
$N_{y}=\left\lceil\frac{L_{yy,g}}{\mu}\log\frac{g_{x}(\overline{y}^{0})-g_{x}^{*}}{\varepsilon}\right\rceil$
iterations of inner loop for
$T_{y}=\tau\left\lceil\frac{1}{2\lambda}\log\left(\frac{D_{y,x}}{\delta^{\prime}_{y}}\right)\right\rceil$
communication steps, the method obtains a point $\mathbf{Y}^{k}$ such that

$\max_{y\in\mathbb{R}^{d_{y}}}\phi(\overline{x}^{k},\overline{y}^{k})-\phi(\overline{x}^{k},\overline{y}^{k})\leq\varepsilon_{y}+\frac{\Delta_{y}^{2}}{2\mu_{y}n}=\hat{\varepsilon}_{y},\quad\text{and}\quad\left\|\mathbf{Y}^{k}-\overline{\mathbf{Y}}^{N}\right\|\leq\sqrt{\delta^{\prime}_{y}},$

where
$\Delta_{y}^{2}=\delta+L_{yy,l}\sqrt{\delta^{\prime}_{y}}+L_{yx,l}\sqrt{\delta^{\prime}_{x}}$
and $D_{y}$ is defined by the following way

$\displaystyle\sqrt{D_{\mathbf{X},\mathbf{Y}}}$
$\displaystyle=\gamma_{y}{\left\|\nabla
G_{\overline{x}}(\overline{\mathbf{Y}}^{*})\right\|}+\sqrt{\delta^{\prime}_{y}}+\left(\gamma_{y}+\frac{1}{\mu_{y}}\right)\Delta_{y}$
(23)
$\displaystyle\;\;\;\;+\gamma_{y}{L_{yy,g}}\sqrt{\frac{2n}{\mu_{y}}\left(1-\frac{\mu_{y}}{L_{yy,g}}\right)\left(G_{\overline{x}}(\overline{\mathbf{Y}})-G_{\overline{x}}^{*}\right)}.$

Note, in not decentralized case we have that the inexact gradient is close
enough to exact one:
$\overline{\nabla_{\mathbf{X}}\Phi}(\overline{\mathbf{X}}^{k},\mathbf{Y}^{k})\approx\overline{\nabla_{\mathbf{X}}F}(\overline{\mathbf{X}}^{k})=\overline{\nabla_{\mathbf{X}}\Phi}(\overline{\mathbf{X}}^{k},\overline{\mathbf{Y}}^{*})$
(see Lemma A.6 from [23]). This case corresponds to every full-connected
graph. Let us generalize this result for decentralized problem statement.

We proved, that after $N_{y}$ iterations of inner loop, we have such point
$Y=\hat{\mathbf{Y}}^{N_{y}}$ that
$g_{x}^{*}-g_{x}(\overline{y})\leq\varepsilon_{y}$ and
$\left\|\mathbf{Y}-\overline{\mathbf{Y}}\right\|\leq\sqrt{\delta^{\prime}_{y}}$.
Using QG-condition for the function $g_{x}$, we can estimate the distance from
obtained point to the optimal one as
$\left\|\mathbf{Y}-\overline{\mathbf{Y}}^{*}(\mathbf{X})\right\|\leq\sqrt{\frac{\hat{\varepsilon}_{y}}{2\mu_{y}}}+\sqrt{\delta^{\prime}_{y}}$,
where $\overline{y}^{*}(x)=\arg\max_{y\in\mathbb{R}^{d_{y}}}g_{\overline{x}}.$
So, we can estimate the inexactness of the gradient with respect to
$\mathbf{X}$ at the point $\mathbf{Y}=\hat{\mathbf{Y}}^{N_{y}}$ according to
the Assumption 2.3 in the following way

$\displaystyle\left\|\overline{\widetilde{\nabla}_{\mathbf{X}}\Phi}(\mathbf{X},\mathbf{Y})-\overline{\nabla
F}(\overline{\mathbf{X}})\right\|$
$\displaystyle\leq\delta+L_{xx,l}\left\|\mathbf{X}-\overline{\mathbf{X}}\right\|+L_{xy,l}\left\|\mathbf{Y}-\overline{\mathbf{Y}}^{*}(\overline{\mathbf{X}})\right\|$
$\displaystyle\leq\delta+L_{xx,l}\sqrt{\delta^{\prime}_{x}}+L_{xy,l}\left(\sqrt{\frac{\hat{\varepsilon}_{y}}{2\mu_{y}}}+\sqrt{\delta^{\prime}_{y}}\right)$
$\displaystyle\leq\delta+L_{xx,l}\sqrt{\delta^{\prime}_{x}}+L_{xy,l}\left(\sqrt{\frac{{\varepsilon}_{y}}{2\mu_{y}}}+\frac{\Delta_{y}}{2\mu_{y}\sqrt{n}}+\sqrt{\delta^{\prime}_{y}}\right).$

So, through the inner iterations we obtain an inexact gradient with respect to
$x$ such that $\left\|\widetilde{\nabla}f(x)-\nabla
f(\overline{x})\right\|\leq\frac{\Delta_{x}}{\sqrt{n}}$, where

$\Delta_{x}=\delta+L_{xx,l}\sqrt{\delta^{\prime}_{x}}+L_{xy,l}\left(\sqrt{\frac{{\varepsilon}_{y}}{2\mu_{y}}}+\frac{\Delta_{y}}{2\mu_{y}\sqrt{n}}+\sqrt{\delta^{\prime}_{y}}\right).$

At the same time, the function $\max_{y\in\mathbb{R}^{d_{y}}}\phi(x,y)$ meets
PL-condition. Moreover, as known (see Lemma A.3 in [40]), when the objective
function $\phi$ meets Assumptions 2.3 and condition (20), the function
$\max_{y\in\mathbb{R}^{d_{y}}}\phi(x,y)$ meets PL-condition with constant
$\mu_{x}$. Also note, that under Assumptions 2.3 and PL-condition (21) for
inner variable, the function
$F(\mathbf{X})=\Phi(\mathbf{X},\mathbf{Y}^{*}(\mathbf{X}))$ is an
$L_{x}$-Lipschitz continuous function with
$L_{x}=L_{xx,g}+\frac{L_{xy,g}}{\mu_{y}}$ (see Lemma A.2 in [40]). So, from
Theorem 2.6, we obtain that Algorithm 3 requires
$N_{x}=\left\lceil\frac{L_{x}}{\mu_{x}}\log\left(\frac{F(\overline{\mathbf{X}}^{0})-F^{*}}{\varepsilon_{x}}\right)\right\rceil$
outer iterations and
$T_{x}=\tau\left\lceil\frac{1}{2\lambda}\log\left(\frac{D_{\mathbf{X}}}{\delta^{\prime}_{x}}\right)\right\rceil$
where

$\sqrt{D_{\mathbf{X}}}=\gamma_{x}{\left\|\nabla
F(\overline{\mathbf{X}}^{*})\right\|}+\sqrt{\delta^{\prime}_{x}}+\left(\gamma_{x}+\frac{1}{\mu_{x}}\right)\Delta_{x}+\gamma_{x}L_{x}\sqrt{\frac{2}{\mu_{x}}\left(1-\frac{\mu_{x}}{L_{x}}\right)\left(F(\overline{\mathbf{X}}^{0})-F^{*}\right)}.$
(24)

Uniting obtained above results for convergences by $\mathbf{X}$ and
$\mathbf{Y}$, we state the following result.

######  Theorem 2.10.

Let functions $\phi(\cdot,y)$ and $-\phi(x,\cdot)$ meet Assumption 2.2 with
constants $\mu_{x}>0$ and $\mu_{y}>0$, and functions $\phi_{i}$ meet the
Assumption 2.3. The gradient oracle
$(\widetilde{\nabla}_{\mathbf{X}}\Phi(\mathbf{X},\mathbf{Y}),\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y}))$
be $(\delta,0)$-biased gradient oracle. Also, Assumption 2.5 holds. Let us
introduce inexactness values
$\Delta_{y}:=\delta+L_{yy,l}\sqrt{\delta^{\prime}_{y}}+L_{yx,l}\sqrt{\delta^{\prime}_{x}}$
and
$\Delta_{x}=\delta+L_{xx,l}\sqrt{\delta^{\prime}_{x}}+L_{xy,l}\left(\sqrt{\frac{{\varepsilon}_{y}}{2\mu_{y}}}+\frac{\Delta_{y}}{2\mu_{y}\sqrt{n}}+\sqrt{\delta^{\prime}_{y}}\right).$
Also define values $D_{\mathbf{X}}$ according to (24) and
$D_{\mathbf{Y}}=\max_{k}{D_{\mathbf{X}^{k},\mathbf{Y}}}$, where
$D_{\mathbf{X}^{k},\mathbf{Y}}$ defined in (23).

Let Algorithm 3 makes
$T_{x}=\tau\left\lceil\frac{1}{2\lambda}\log\left(\frac{D_{X}}{\delta^{\prime}_{x}}\right)\right\rceil$
communication steps in each outer iteration and
$T_{y}=\tau\left\lceil\frac{1}{2\lambda}\log\left(\frac{D_{Y}}{\delta^{\prime}_{y}}\right)\right\rceil$
communication steps at each inner iteration, with step-sizes
$\gamma_{x}=\frac{1}{L_{x}}$ and $\gamma_{y}=\frac{1}{L_{yy,g}}$. Then
Algorithm 3 requires

$N_{x}=\left\lceil\frac{L_{x}}{\mu_{x}}\log\left(\frac{F(\overline{\mathbf{X}}^{0})-F^{*}}{\varepsilon_{x}}\right)\right\rceil$

outer iterations, where $L_{x}=L_{xx,g}+\frac{L_{xy,g}}{\mu_{y}}$, and

$N_{y}=\left\lceil\frac{L_{yy,g}}{\mu_{y}}\log\left(\frac{G_{\overline{x}}^{*}-G_{\overline{x}}(\overline{\mathbf{X}}^{0})}{\varepsilon_{y}}\right)\right\rceil$

inner iterations for each outer iteration to yield the pair
$\left(\mathbf{X}^{N_{x}},\mathbf{Y}^{N_{y}}\right)$, such that

$f(\overline{x}^{N_{x}})-f^{*}\leq\varepsilon_{x}+\frac{\Delta_{x}^{2}}{2\mu_{x}n},\quad\left\|\mathbf{X}^{N_{x}}-\overline{\mathbf{X}}^{N_{x}}\right\|\leq\sqrt{\delta^{\prime}_{x}},$
(25)

and

$\max_{y\in\mathbb{R}^{d_{y}}}\phi(\overline{x}^{N_{x}},y)-\phi(\overline{x}^{N_{x}},\overline{y}^{N_{y}})\leq\varepsilon_{y}+\frac{\Delta_{y}^{2}}{2\mu_{y}n},\quad\left\|\mathbf{Y}^{N_{y}}-\overline{\mathbf{Y}}^{N_{y}}\right\|\leq\sqrt{\delta^{\prime}_{y}}.$
(26)

######  Remark 2.

In general, Algorithm 3 requires

$N_{x}\cdot
N_{y}=O\left(\left(\frac{L_{xx,g}L_{yy,g}}{\mu_{y}\mu_{x}}+\frac{L_{xy,g}L_{yy,g}}{\mu_{y}^{2}\mu_{x}}\right)\log^{2}\frac{1}{\varepsilon}\right),$

gradient computations with respect to $\mathbf{Y}$ and

$N_{x}=O\left(\left(\frac{L_{xx,g}}{\mu_{x}}+\frac{L_{xy,g}}{\mu_{y}\mu_{x}}\right)\log\frac{1}{\varepsilon}\right),$

gradient computations with respect to $\mathbf{X}$ at each node.

######  Remark 3.

Algorithm 3 requires $T_{tot}=N_{x}T_{x}+N_{y}N_{x}T_{y}$ communication steps
to achieve the required quality. Note, that the communication steps in inner
iterations and outer iterations can have different computational cost. Namely,
the dimensions $d_{x}$ for $\mathbf{X}$ and $d_{y}$ for $\mathbf{Y}$ can
significantly differ.

Now, we consider the case, when
$\widetilde{\nabla}_{\mathbf{X}}\Phi(\mathbf{X},\mathbf{Y})$ and
$\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})$ be
$(\delta,\sigma^{2})$-biased gradient oracle. Let parameters numbers of
communication steps $T_{x}$ and $T_{y}$ such that
$\mathbb{E}\|\mathbf{X}^{j}-\overline{\mathbf{Y}}^{j}\|^{2}\leq{\delta^{\prime}_{x}}$
and
$\mathbb{E}\|\mathbf{Y}^{j}-\overline{\mathbf{Y}}^{j}\|^{2}\leq{\delta^{\prime}_{y}}$
in all iterations. So, we can estimate noise and bias for gradient with
respect to $\mathbf{Y}$ for each inner loop. The proof of the following lemma
is presented in Appendix D.

######  Lemma 2.11.

Let us assume that functions $\phi$ meet Assumption 2.3 and for all $j\leq k$
we have
$\mathbb{E}\left\|\mathbf{X}^{j}-\overline{\mathbf{X}}^{j}\right\|^{2}\leq\delta^{\prime}_{x},$
$\mathbb{E}\left\|\hat{\mathbf{Y}}^{j}-\overline{\hat{\mathbf{Y}}}^{j}\right\|^{2}\leq\delta^{\prime}_{y},$
where $\\{\mathbf{X}^{j}\\}_{j\leq k}$ and $\\{\hat{\mathbf{Y}}^{j}\\}_{j\leq
k}$. Then for the bias and noise in the inexact gradient
$g_{k,j}=\overline{\widetilde{\nabla}_{Y}\phi}(\mathbf{X}^{k},\mathbf{Y}^{k})=\frac{1}{n}\sum\limits_{i=1}^{m}\widetilde{\nabla_{y}}\phi_{i}(x_{k,i},y_{k,i})$
we the following estimations:

$\mathbb{E}\left\|\mathbb{E}_{X,Y,\xi}g_{k,j}-\nabla_{Y}\phi(\overline{x}^{k},\overline{\hat{y}}^{j})\right\|^{2}\leq\frac{3\delta^{2}+3L_{yy}^{2}{\delta^{\prime}_{y}}+3L_{yx}^{2}{\delta^{\prime}_{x}}}{n},$

and

$\displaystyle\mathbb{E}\left\|\mathbb{E}_{X,Y,\xi}g_{k,j}-g_{k,j}\right\|^{2}\leq
16\left(\frac{L_{yy,l}^{2}{\delta^{\prime}_{y}}+L_{yx,l}^{2}\delta^{\prime}_{x}+\delta^{2}}{n}\right)+\frac{18\sigma^{2}}{n}.$

It allows us to use results of Theorem 2.9. Let parameters $N_{y}$ and $T_{y}$
be defined according to this theorem for current value of outer variable
$\mathbf{X}^{k}$ and chosen accuracies $\varepsilon_{y}$ and
$\delta^{\prime}_{y}$. Then after $N_{y}$ inner iterations we obtain such
point $\mathbf{Y}=\hat{\mathbf{Y}}^{N_{y}}$, s.t.

$\max_{y\in\mathbb{R}^{d_{y}}}\phi(\overline{x}^{k},y)-\mathbb{E}\phi(\overline{x}^{k},\overline{\hat{y}}^{N_{y}})\leq\varepsilon_{y}+\frac{\Delta_{y}^{2}}{2\mu_{y}n},\quad\text{and}\quad\mathbb{E}\left\|\hat{\mathbf{Y}}^{N_{y}}-\overline{\hat{\mathbf{Y}}}^{N_{y}}\right\|^{2}\leq{\delta^{\prime}_{y}},$

where
$\Delta_{y}^{2}=19\left(L_{yy,l}^{2}{\delta^{\prime}_{y}}+L_{yx,l}^{2}\delta^{\prime}_{x}+\sigma^{2}+\delta^{2}\right).$

This allows us to estimate inaccuracies in the inexact gradient with respect
to $\mathbf{X}$ on outer iterations. Note, that it contains new inexactness
because of the inexact solution of the inner problem on each iteration. The
following lemma contains results about the gradient bias and noise (see the
proof in Appendix E).

######  Lemma 2.12.

Let we assume that the function $\phi$ meets Assumption 2.3 and for all $j\leq
k$ we have
$\mathbb{E}\left\|\mathbf{X}^{j}-\overline{\mathbf{X}}^{j}\right\|^{2}\leq\delta^{\prime}_{x}$,
$\mathbb{E}\left\|{\mathbf{Y}}^{j}-\overline{{\mathbf{Y}}}^{j}\right\|^{2}\leq\delta^{\prime}_{y}$,
where $\\{\mathbf{X}^{j}\\}_{j}$ and $\\{\mathbf{Y}^{j}\\}_{j}$ is the
sequence generated by Algorithm 3. Also, $\mathbf{Y}^{k}$ be a point such that
$g_{x}(\overline{y})-g_{x}^{*}\leq\varepsilon_{y}+\frac{\Delta_{y}^{2}}{2\mu_{y}n}$.
Then for the bias and noise in the inexact gradient
$h_{k}=\overline{\widetilde{\nabla}_{\mathbf{Y}}\phi}(\mathbf{X}^{k},\mathbf{Y}^{k})=\frac{1}{n}\sum\limits_{i=1}^{n}\widetilde{\nabla_{y}}\phi_{i}(x_{k,i},y_{k,i})$,
we the following estimations

$\mathbb{E}\left\|\mathbb{E}_{\mathbf{X},\mathbf{Y},\xi}h_{k}-\nabla
F(\overline{\mathbf{Y}})\right\|^{2}\leq\frac{3\delta^{2}+3L_{xx}^{2}{\delta^{\prime}_{x}}+6L_{xy}^{2}\left({\frac{2{\varepsilon}_{y}}{\mu_{y}}}+\frac{\Delta_{y}^{2}}{\mu_{y}^{2}{n}}+{\delta^{\prime}_{y}}\right)}{n},$

and

$\displaystyle\mathbb{E}\left\|\mathbb{E}_{\mathbf{X},Y,\xi}h_{k}-h_{k}\right\|^{2}\leq
16\frac{L_{xy,l}^{2}{\delta^{\prime}_{y}}+L_{xx,l}^{2}\delta^{\prime}_{x}+\delta^{2}}{n}+\frac{18\sigma^{2}}{n}.$

Uniting the results of Lemmas 2.11, 2.12 and Theorem 2.9, we obtain the
following result for the convergence of Algorithm 3.

######  Theorem 2.13.

Let the functions $\phi(\cdot,y)$ and $-\phi(x,\cdot)$ meet Assumption 2.2
with constants $\mu_{x}>0$ and $\mu_{y}>0$ and the functions $\phi_{i}$ meet
the Assumption 2.3. The gradient oracle
$\left(\widetilde{\nabla}_{\mathbf{X}}\Phi(\mathbf{X},\mathbf{Y}),\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})\right)$
be a $(\delta,\sigma^{2})$-biased gradient oracle. Also, Assumption 2.5 holds.
Let us introduce the following inexactness values

$\displaystyle\Delta_{y}^{2}$
$\displaystyle:=19\left(L_{yy,l}^{2}{\delta^{\prime}_{y}}+L_{yx,l}^{2}\delta^{\prime}_{x}+\sigma^{2}+\delta^{2}\right),$
$\displaystyle\Delta_{x}^{2}$
$\displaystyle:=22L_{xy,l}^{2}{\delta^{\prime}_{y}}+19L_{xx,l}^{2}\delta^{\prime}_{x}+19\delta^{2}+18\sigma^{2}+6L_{xy}^{2}\left({\frac{2{\varepsilon}_{y}}{\mu_{y}}}+\frac{\Delta_{y}^{2}}{\mu_{y}^{2}{n}}\right).$

and define the values $D_{\mathbf{X}}$ and $D_{\mathbf{Y}}$, such that

$D_{\mathbf{X}}=6\gamma_{x}^{2}\left\|\nabla
F(\overline{\mathbf{X}}^{*})\right\|^{2}+2\delta^{\prime}_{x}+6\left(\gamma_{x}^{2}+\frac{1}{\mu_{x}^{2}}\right)\Delta^{2}+\frac{12\gamma_{x}^{2}L_{x}^{2}}{\mu_{x}}\left(1-\frac{\mu_{x}}{L_{x}}\right)\left(F(\overline{\mathbf{X}}^{0})-F^{*}\right),$

and $D_{\mathbf{Y}}=\max_{k}D_{\mathbf{X}^{k},\mathbf{Y}}$, where

$\displaystyle D_{\mathbf{X}^{k},\mathbf{Y}}$
$\displaystyle=6\gamma^{2}\mathbb{E}\left\|\nabla
G_{\mathbf{X}^{k}}(\overline{\mathbf{Y}}^{*})\right\|^{2}+2\delta_{y}^{\prime}+6\left(\gamma_{y}^{2}+\frac{1}{\mu_{y}^{2}}\right)\Delta_{y}^{2}$
$\displaystyle\;\;\;\;+\frac{12\gamma^{2}L_{yy,g}^{2}}{\mu_{y}}\left(1-\frac{\mu_{y}}{L_{yy,g}}\right)\mathbb{E}\left[G_{\mathbf{X}^{k}}(\overline{\mathbf{Y}}^{0})-G_{\mathbf{X}}^{*}\right],$

Let Algorithm 3, with step-sizes $\gamma_{x}=\frac{1}{L_{x}}$ and
$\gamma_{y}=\frac{1}{L_{yy,g}}$, makes
$T_{x}=\tau\left\lceil\frac{1}{2\lambda}\log\left(\frac{D_{\mathbf{X}}}{\delta^{\prime}_{x}}\right)\right\rceil$
communication steps in each outer iteration and
$T_{y}=\tau\left\lceil\frac{1}{2\lambda}\log\left(\frac{D_{\mathbf{Y}}}{\delta^{\prime}_{y}}\right)\right\rceil$
communication steps in each inner iteration. Then Algorithm 3 requires

$N_{x}=\left\lceil\frac{L_{x}}{\mu_{x}}\log\left(\frac{F(\overline{\mathbf{X}}^{0})-F^{*}}{\varepsilon_{x}}\right)\right\rceil$

outer iterations, where $L_{x}=L_{xx,g}+\frac{L_{xy,g}}{\mu_{y}}$, and

$N_{y}=\left\lceil\frac{L_{yy,g}}{\mu_{y}}\log\left(\frac{G_{\overline{x}}^{*}-G_{\overline{x}}(\overline{\mathbf{X}}^{0})}{\varepsilon_{y}}\right)\right\rceil$

inner iterations for each outer iteration to yield the pair
$(\mathbf{X}^{N_{x}},\mathbf{Y}^{N_{y}})$ such that

$\mathbb{E}\left[f\left(\overline{x}^{N_{x}}\right)-f^{*}\right]\leq\varepsilon_{x}+\frac{\Delta_{x}^{2}}{2\mu_{x}n},\quad\mathbb{E}\left\|\mathbf{X}^{N_{x}}-\overline{\mathbf{X}}^{N_{x}}\right\|\leq\sqrt{\delta^{\prime}_{x}}$
(27)

and

$\mathbb{E}\left[\max_{y\in\mathbb{R}^{d_{y}}}\phi\left(\overline{x}^{N_{x}},y\right)-\phi\left(\overline{x}^{N_{x}},\overline{y}^{N_{y}}\right)\right]\leq\varepsilon_{y}+\frac{\Delta_{y}^{2}}{2\mu_{y}n},\quad\mathbb{E}\left\|\mathbf{Y}^{N_{y}}-\overline{\mathbf{Y}}^{N_{y}}\right\|\leq\sqrt{\delta^{\prime}_{y}}.$
(28)

######  Remark 4.

Note, that the total number of gradient computations and communication steps
to approach the qualities (27) and (28) can be considered comparable with (25)
and (26).

######  Remark 5.

In the case, when $\sigma=0$ (i.e. the noise is almost everywhere is zero),
Theorem 2.13 gets results worse than Theorem 2.10. It is related to different
rounding and inexact estimations in the proof of Theorem 2.13.

##  3 Numerical experiments

To show the practical performance of the proposed Algorithm 3, we performed a
series of numerical experiments for the Robust Least Squares problem.

All experiments were made using Python 3.4, on a computer with Intel(R)
Core(TM) i7-8550U CPU @ 1.80GHz, 1992 Mhz, 4 Core(s), 8 Logical Processor(s),
and 8 GB RAM.

Let us consider the following least squares minimization problem

$\min_{x\in\mathbb{R}^{d_{x}}}\frac{1}{n}\sum\limits_{i=1}^{n}\frac{1}{2}\left\|A_{i}x-y_{i,0}\right\|^{2},$
(29)

for given matrices $A_{i}\in\mathbb{R}^{d_{i}\times d_{x}}$ and vectors
$y_{i,0}\in\mathbb{R}^{d_{i}}$, when $A_{i},y_{i,0}$ are placed in $n$
different nodes. In [7], it was proposed a robust version of this problem in
the following form

$\min_{x\in\mathbb{R}^{d_{x}}}\max_{y\in\mathbb{R}^{d_{y}}:\|B_{i}y\|\leq\delta}\frac{1}{n}\sum\limits_{i=1}^{n}\frac{1}{2}\left\|A_{i}x-y_{i,0}-B_{i}y\right\|^{2},$

where $B_{i}\in\mathbb{R}^{d_{i}\times d_{y}}$, for some $\delta>0$. In our
experiments we consider the Robust Least Squares problem with soft constraint

$\min_{x\in\mathbb{R}^{d_{x}}}\max_{y\in\mathbb{R}^{d_{y}}}\left\\{\phi(x,y)=\frac{1}{n}\sum\limits_{i=1}^{n}\phi_{i}(x,y)\right\\},$
(30)

where

$\phi_{i}(x,y)=\frac{1}{2}\left\|A_{i}x-y_{i,0}-B_{i}y\right\|^{2}-\frac{\alpha}{2}\|B_{i}y\|^{2},$
(31)

for some $\alpha>1$. Note, that the matrices $A_{i},B_{i}$ and the vectors
$y_{i,0}$ for each $i\in\\{1,\ldots,n\\}$, are located in different nodes. So,
in the distributed statement, we can not to solve this problem explicitly. At
the same time, the global solution has compact form.

Note that the conditions of Theorem 2.13 are fulfilled for the considered
saddle point problem (30) with (31). The function $\phi(\cdot,y)$, for each
$y\in\mathbb{R}^{n_{y}}$, satisfies PL-condition with constant $\mu_{x}$, and
$-\phi(x,\cdot)$, for each $x\in\mathbb{R}^{n_{x}}$, satisfies PL-condition
with constant $\mu_{y}$, where $\mu_{x}$ and $\mu_{y}$ are the smallest non-
zero eigenvalues of the matrices $A=\sum\limits_{i=1}^{n}A_{i}^{\top}A_{i}$
and $B=(\lambda-1)\sum\limits_{i=1}^{n}B_{i}^{\top}B_{i}$, respectively. Note,
that problem (30) is convex-concave problem but not strongly-convex-strongly-
concave until $A$ and $B$ are not full-rank matrices.

We run Algorithm 3 with different values of $n$ (the number of components in
(30), which indicates to the number of nodes if the graph). We take the zero
matrices for the initialization of the algorithm. The matrices $A_{i},B_{i}$
and vectors $y_{i,0}$, for each $i\in\\{1,\ldots,n\\}$ in (31) are randomly
generated from the standard normal distribution. We also choose the fixed step
sizes $\gamma_{x}=\gamma_{y}=10^{-3},N_{x}=10^{4},N_{y}=10$ (experimentally we
see more than $10$ iterations, but there is not a remarkable difference) and
$10$ steps in the consensus at each iteration of Algorithm 3.

The results of the conducted experiments are represented in Figures 1, 31.
These results demonstrate the value of the objective function $\phi$ and the
norm of its gradient with respect to both variables at each points
$(x_{k},y_{k})$ generated by algorithm as a function of iteration $k$, and the
running time of the algorithm in seconds as a function of the number of nodes
$n$.

From Fig. 1 and Fig. 2, we can see the efficiency of the proposed Algorithm 3,
which provides a remarkable quality solution with respect to the value of the
objective function and the norm of its gradient at each generated point each
iteration. Also, we can see the effect of the number of nodes $n$, in the work
of algorithm, where the quality of a solution is decrease when we increase
(not strongly) the number of nodes.

Figure 1: Results of Algorithm 3 problem (30) with (31) with $\alpha=2$, and
different values of $n$.

Figure 2: Results of Algorithm 3 problem (30) with (31) with $\alpha=2$, and
different values of $n$.

##  4 Conclusion

In this paper, we studied the decentralized minimization problem with
objective functions that satisfy Polyak-Łojasiewicz condition (PL-condition),
and the decentralized saddle-point problem with a structure of the sum, with
objectives satisfying the two-sided PL-condition. For solving the minimization
problem under consideration, we proposed a gradient descent type method with a
consensus projection procedure and the inexact gradient of the cost function.
In order to solve the considered saddle point problem, we proposed a
generalization of the Multi-step Gradient Descent Ascent method with a
consensus procedure, and inexact gradients of the objective function with
respect to both variables. For the studied classes of the problems, we
estimated the sufficient communication steps and iterations number to approach
the required quality with respect to the function and the distance between the
agent’s vectors and their average Some results of the conducted numerical
experiments are presented, which demonstrate the effectiveness of the proposed
algorithm for the Robust Least Squares problem.

## References

  * [1] A. Ajalloeian and S.U. Stich, _On the convergence of sgd with biased gradients_ , arXiv:2008.00051 (2020).
  * [2] Y. Arjevani, J. Bruna, B. Can, M. Gurbuzbalaban, S. Jegelka, and H. Lin, _Ideal: Inexact decentralized accelerated augmented lagrangian method_ , Advances in Neural Information Processing Systems 33 (2020), pp. 20648–20659.
  * [3] B. Barazandeh, D.A. Tarzanagh, and G. Michailidis, _Solving a Class of Non-Convex Min-Max Games Using Adaptive Momentum Methods_ , in _ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. 2021, pp. 3625–3629.
  * [4] A. Beznosikov, E. Gorbunov, H. Berard, and N. Loizou, _Stochastic gradient descent-ascent: Unified theory and new efficient methods_ , arXiv:2202.07262 (2022).
  * [5] S. Du, J. Lee, H. Li, L. Wang, and X. Zhai, _Gradient descent finds global minima of deep neural networks_ , in _International conference on machine learning_. PMLR, 2019, pp. 1675–1685.
  * [6] D. Dvinskikh and A. Gasnikov, _Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems_ , Journal of Inverse and Ill-posed Problems 29 (2021), pp. 385–405.
  * [7] L. El Ghaoui and H. Lebret, _Robust solutions to least-squares problems with uncertain data_ , SIAM Journal on matrix analysis and applications 18 (1997), pp. 1035–1064.
  * [8] M. Fazel, R. Ge, S. Kakade, and M. Mesbahi, _Global convergence of policy gradient methods for the linear quadratic regulator_ , in _International Conference on Machine Learning_. PMLR, 2018, pp. 1467–1476.
  * [9] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, _Generative adversarial networks_ , Communications of the ACM 63 (2020), pp. 139–144.
  * [10] I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A.C. Courville, _Improved training of wasserstein gans_ , Advances in neural information processing systems 30 (2017).
  * [11] H. Hendrikx, F. Bach, and L. Massoulie, _An optimal algorithm for decentralized finite-sum optimization_ , SIAM Journal on Optimization 31 (2021), pp. 2753–2783.
  * [12] A. Ivanova, P. Dvurechensky, A. Gasnikov, and D. Kamzolov, _Composite optimization for the resource allocation problem_ , Optimization Methods and Software 36 (2021), pp. 720–754.
  * [13] D. Jakovetić, _A unification and generalization of exact distributed first-order methods_ , IEEE Transactions on Signal and Information Processing over Networks 5 (2018), pp. 31–46.
  * [14] H. Karimi, J. Nutini, and M. Schmidt, _Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition_ , in _Joint European conference on machine learning and knowledge discovery in databases_. Springer, 2016, pp. 795–811.
  * [15] A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich, _A unified theory of decentralized sgd with changing topology and local updates_ , in _International Conference on Machine Learning_. PMLR, 2020, pp. 5381–5393.
  * [16] T. Kraska, A. Talwalkar, J.C. Duchi, R. Griffith, M.J. Franklin, and M.I. Jordan, _MLbase: A Distributed Machine-learning System._ , in _Cidr_ , Vol. 1. 2013, pp. 2–1.
  * [17] A. Kurakin, I.J. Goodfellow, and S. Bengio, _Adversarial Machine Learning at Scale_ , in _International Conference on Learning Representations_. 2017\. Available at https://openreview.net/forum?id=BJm4T4Kgx.
  * [18] H. Li, C. Fang, W. Yin, and Z. Lin, _A sharp convergence rate analysis for distributed accelerated gradient methods_ , arXiv:1810.01053 (2018).
  * [19] H. Li and Z. Lin, _Revisiting extra for smooth distributed optimization_ , SIAM Journal on Optimization 30 (2020), pp. 1795–1821.
  * [20] H. Li, Z. Lin, and Y. Fang, _Variance reduced extra and diging and their optimal acceleration for strongly convex decentralized optimization_ , arXiv:2009.04373 (2020).
  * [21] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu, _Towards deep learning models resistant to adversarial attacks_ , arXiv:1706.06083 (2017).
  * [22] M. Maros and J. Jaldén, _Panda: A dual linearly converging method for distributed optimization over time-varying undirected graphs_ , in _2018 IEEE Conference on Decision and Control (CDC)_. IEEE, 2018, pp. 6520–6525.
  * [23] M.Nouiehed, M. Sanjabi, T. Huang, J. Lee, and M. Razaviyayn, _Solving a class of non-convex min-max games using iterative first order methods_ , Advances in Neural Information Processing Systems (2019), p. 14905–14916.
  * [24] A. Nedic, A. Olshevsky, and W. Shi, _Achieving geometric convergence for distributed optimization over time-varying graphs_ , SIAM Journal on Optimization 27 (2017), pp. 2597–2633.
  * [25] A. Nedic and A. Ozdaglar, _Distributed subgradient methods for multi-agent optimization_ , IEEE Transactions on Automatic Control 54 (2009), pp. 48–61.
  * [26] B. Polyak, _Gradient methods for the minimisation of functionals_ , Ussr Computational Mathematics and Mathematical Physics 3 (1963), pp. 864–878.
  * [27] S. Pu, W. Shi, J. Xu, and A. Nedić, _Push–pull gradient methods for distributed optimization in networks_ , IEEE Transactions on Automatic Control 66 (2020), pp. 1–16.
  * [28] G. Qu and N. Li, _Accelerated distributed nesterov gradient descent_ , IEEE Transactions on Automatic Control 65 (2019), pp. 2566–2581.
  * [29] S. Ram, V. Veeravalli, and A. Nedic, _Distributed non-autonomous power control through distributed convex optimization_ , Proceedings - IEEE INFOCOM (2009), pp. 3001 – 3005.
  * [30] A. Rogozin, M. Bochko, P. Dvurechensky, A. Gasnikov, and V. Lukoshkin, _An accelerated method for decentralized distributed stochastic optimization over time-varying graphs_ , arXiv:2103.15598 (2021).
  * [31] A. Rogozin, M. Bochko, P. Dvurechensky, A. Gasnikov, and V. Lukoshkin, _An accelerated method for decentralized distributed stochastic optimization over time-varying graphs_ , in _2021 60th IEEE Conference on Decision and Control (CDC)_. IEEE, 2021, pp. 3367–3373.
  * [32] A. Rogozin, V. Lukoshkin, A. Gasnikov, D. Kovalev, and E. Shulgin, _Towards accelerated rates for distributed optimization over time-varying networks_ , arXiv:2009.11069 (2020).
  * [33] A. Rogozin, V. Lukoshkin, A. Gasnikov, D. Kovalev, and E. Shulgin, _Towards accelerated rates for distributed optimization over time-varying networks_ , in _International Conference on Optimization and Applications_. Springer, 2021, pp. 258–272.
  * [34] K. Scaman, F. Bach, S. Bubeck, Y.T. Lee, and L. Massoulié, _Optimal algorithms for smooth and strongly convex distributed optimization in networks_ , in _international conference on machine learning_. PMLR, 2017, pp. 3027–3036.
  * [35] K. Scaman, F. Bach, S. Bubeck, L. Massoulié, and Y.T. Lee, _Optimal algorithms for non-smooth distributed optimization in networks_ , Advances in Neural Information Processing Systems 31 (2018).
  * [36] J. Sun, Q. Qu, and J. Wright, _A geometric analysis of phase retrieval_ , Foundations of Computational Mathematics 18 (2018), pp. 1131–1198.
  * [37] C.A. Uribe, S. Lee, A. Gasnikov, and A. Nedić, _A dual approach for optimal algorithms in distributed optimization over networks_ , in _2020 Information Theory and Applications Workshop (ITA)_. IEEE, 2020, pp. 1–37.
  * [38] E. Wei and A. Ozdaglar, _Distributed alternating direction method of multipliers_ , in _2012 IEEE 51st IEEE Conference on Decision and Control (CDC)_. IEEE, 2012, pp. 5445–5450.
  * [39] X. Wu and J. Lu, _Fenchel dual gradient methods for distributed convex optimization over time-varying networks_ , IEEE Transactions on Automatic Control 64 (2019), pp. 4629–4636.
  * [40] J. Yang, N. Kiyavash, and N. He, _Global convergence and variance-reduced optimization for a class of nonconvex-nonconcave minimax problems_ , arXiv:2002.09621 (2020).
  * [41] H. Ye, L. Luo, Z. Zhou, and T. Zhang, _Multi-consensus decentralized accelerated gradient descent_ , arXiv:2005.00797 (2020).
  * [42] G. Zhang and R. Heusdens, _Distributed optimization using the primal-dual method of multipliers_ , IEEE Transactions on Signal and Information Processing over Networks 4 (2017), pp. 173–187.

##  Appendix A Proof of Lemma 2.7

###### Proof.

Note, for the bias in
$\overline{\widetilde{\nabla}}f(\overline{\mathbf{X}}^{k})$ we proved in the
main part the following estimation

$\mathbb{E}\left\|\mathbb{E}_{\mathbf{X},\xi}\overline{\widetilde{\nabla}f}(\mathbf{X}^{k})-{{\nabla}f}(\overline{x}^{k})\right\|^{2}\leq\frac{2\delta^{2}+L_{l}^{2}\delta^{\prime}}{{n}}.$
(32)

Also, we assume that the condition
$\mathbb{E}_{\mathbf{X}}\left\|\mathbf{X}^{j}-\overline{\mathbf{X}}^{j}\right\|^{2}\leq\delta^{\prime}$
holds for all $j\leq k$.

Let us estimate noise in
$\overline{\widetilde{\nabla}}f(\overline{\mathbf{X}}^{k})$. For this, we
estimate the second moment of random component in
$\widetilde{\nabla}F(\mathbf{X}^{k})$ for given $\overline{\mathbf{X}}^{k}$.
It is given by the expression

$\mathbb{E}_{\mathbf{X},\xi}\left\|\mathbb{E}_{\mathbf{X},\xi}\widetilde{\nabla}F(\mathbf{X}^{k})-\widetilde{\nabla}F(\mathbf{X}^{k})\right\|.$

Let us estimate inner part in the following way:

$\displaystyle\left\|\mathbb{E}_{\mathbf{X},\xi}\widetilde{\nabla}F(\mathbf{X}^{k})-\widetilde{\nabla}F(\mathbf{X}^{k})\right\|$
$\displaystyle\leq\left\|\mathbb{E}_{\mathbf{X},\xi}\widetilde{\nabla}F(\mathbf{X}^{k})-\mathbb{E}_{\mathbf{X}}\widetilde{\nabla}F(\mathbf{X}^{k})\right\|+\left\|\mathbb{E}_{\mathbf{X}}\widetilde{\nabla}F(\mathbf{X}^{k})-\widetilde{\nabla}F(\mathbf{X}^{k})\right\|$
$\displaystyle\leq\mathbb{E}_{\mathbf{X}}\left\|\mathbb{E}_{\xi}\widetilde{\nabla}F(\mathbf{X}^{k})-\widetilde{\nabla}F(\mathbf{X}^{k})\right\|+\left\|\mathbb{E}_{\mathbf{X}}\widetilde{\nabla}F(\mathbf{X}^{k})-\widetilde{\nabla}F(\mathbf{X}^{k})\right\|.$

The second term in the sum above can be represented in the following way:

$\displaystyle\left\|\mathbb{E}_{\mathbf{X}}\widetilde{\nabla}F(\mathbf{X}^{k})-\widetilde{\nabla}F(\mathbf{X}^{k})\right\|\leq$
$\displaystyle\mathbb{E}_{\mathbf{X}}\left\|\widetilde{\nabla}F(\mathbf{X}^{k})-{\nabla}F(\mathbf{X}^{k})\right\|$
$\displaystyle+\left\|\mathbb{E}_{\mathbf{X}}{\nabla}F(\mathbf{X}^{k})-{\nabla}F(\mathbf{X}^{k})\right\|+\left\|\widetilde{\nabla}F(\mathbf{X}^{k})-{\nabla}F(\mathbf{X}^{k})\right\|.$

From this we have the following estimation for its square expecation:

$\displaystyle\mathbb{E}\left\|\mathbb{E}_{\mathbf{X}}\widetilde{\nabla}F(\mathbf{X}^{k})-\widetilde{\nabla}F(\mathbf{X}^{k})\right\|^{2}\leq
2\mathbb{E}\left\|\mathbb{E}_{\mathbf{X}}{\nabla}F(\mathbf{X}^{k})-{\nabla}F(\mathbf{X}^{k})\right\|^{2}+8\mathbb{E}\left\|\widetilde{\nabla}F(\mathbf{X}^{k})-{\nabla}F(\mathbf{X}^{k})\right\|^{2}.$

The term
$\left\|\mathbb{E}_{\mathbf{X}}{\nabla}F(\mathbf{X}^{k})-{\nabla}F(\mathbf{X}^{k})\right\|$
can be estimated above by the following sum

$\mathbb{E}_{\mathbf{X}}\left\|{\nabla}F(\mathbf{X}^{k})-{\nabla}F(\overline{\mathbf{X}}^{k})\right\|+\left\|{\nabla}F(\overline{\mathbf{X}}^{k})-{\nabla}F(\mathbf{X}^{k})\right\|.$

From this we can estimate the full mathematical expectation as
$\mathbb{E}\left\|\mathbb{E}_{\mathbf{X}}{\nabla}F(\mathbf{X}^{k})-{\nabla}F(\mathbf{X}^{k})\right\|^{2}\leq
4L_{l}^{2}\delta^{\prime}$ until
$\mathbb{E}\left\|\mathbf{X}^{k}-\overline{\mathbf{X}}^{k}\right\|^{2}\leq\delta^{\prime}$.
Let us introduce the noise value
$n(\mathbf{X}^{k})=\widetilde{\nabla}F(\mathbf{X}^{k})-\mathbb{E}_{\xi}\widetilde{\nabla}F(\mathbf{X}^{k})$
and the bias
$b(\mathbf{X}^{k})=\mathbb{E}_{\xi}\widetilde{\nabla}F(\mathbf{X}^{k})-{\nabla}F(\mathbf{X}^{k}).$
Note, that $\mathbb{E}\|n(\mathbf{X}^{k})\|^{2}\leq\sigma^{2}$ and
$\mathbb{E}\left\|b(\mathbf{X}^{k})\right\|^{2}\leq\delta^{2}$. So, the
expectation of another term can be estimated in the following form:

$\mathbb{E}\left\|\widetilde{\nabla}F(\mathbf{X}^{k})-{\nabla}F(\mathbf{X}^{k})\right\|^{2}=\mathbb{E}\left\|b(\mathbf{X}^{k})\right\|^{2}+\mathbb{E}\left\|n(\mathbf{X}^{k})\right\|^{2}\leq\sigma^{2}+\delta^{2}.$

Finally, we have that

$\mathbb{E}\left\|\mathbb{E}_{\mathbf{X}}\widetilde{\nabla}F(\mathbf{X}^{k})-\widetilde{\nabla}F(\mathbf{X}^{k})\right\|^{2}\leq
8L_{l}\sqrt{\delta^{\prime}}+8\sigma+8\delta.$

Uniting inequalities above, we have the following estimation:

$\displaystyle\mathbb{E}\left\|\mathbb{E}_{\mathbf{X},\xi}\widetilde{\nabla}F(\mathbf{X}^{k})-\widetilde{\nabla}F(\mathbf{X}^{k})\right\|^{2}\leq$
$\displaystyle
2\mathbb{E}_{\mathbf{X},\xi}\left(\mathbb{E}_{\mathbf{X}}\left\|\mathbb{E}_{\xi}\widetilde{\nabla}F(\mathbf{X}^{k})-\widetilde{\nabla}F(\mathbf{X}^{k})\right\|\right)^{2}$
$\displaystyle+16L_{l}^{2}{\delta^{\prime}}+16\sigma^{2}+16\delta^{2}$
$\displaystyle\leq$ $\displaystyle
16L_{l}^{2}{\delta^{\prime}}+18\sigma^{2}+16\delta^{2}.$

Finally, for the noise component in
$\overline{\widetilde{\nabla}}f(\overline{X}^{k})$, we have the following
estimation:

$\displaystyle\mathbb{E}\left\|\mathbb{E}_{X,\xi}\overline{\widetilde{\nabla}f}(X^{k})-\overline{\widetilde{\nabla}f}(X^{k})\right\|^{2}=$
$\displaystyle\frac{1}{n}\mathbb{E}\left\|\mathbb{E}_{\mathbf{X},\xi}\overline{\widetilde{\nabla}F}(\mathbf{X}^{k})-\overline{\widetilde{\nabla}F}(\mathbf{X}^{k})\right\|^{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{n}\mathbb{E}\left\|\mathbb{E}_{\mathbf{X},\xi}{\widetilde{\nabla}F}(\mathbf{X}^{k})-{\widetilde{\nabla}F}(\mathbf{X}^{k})\right\|^{2}$
$\displaystyle\leq$
$\displaystyle\frac{16L_{l}^{2}{\delta^{\prime}}+18\sigma^{2}+16\delta^{2}}{n}.$

So, we obtained the estimation for the noise component in
$\overline{\widetilde{\nabla}f}(X^{k})$. ∎

##  Appendix B Proof of Lemma 2.8

###### Proof.

According to proof of Lemma 2 from [1] we can prove the following inequality:

$\mathbb{E}\left[f(x^{t+1})\Big{|}x^{t}\right]\leq
f(x^{t})-\frac{\gamma}{2}\left\|\nabla
f(x^{t})\right\|^{2}+\frac{\gamma}{2}\left\|b(x^{k})\right\|^{2}+\frac{\gamma^{2}L}{2}\mathbb{E}_{\xi}\left\|n(x^{k})\right\|^{2}.$

Using PL-condition for function $f$ and taking full mathematical expectation,
we have the following inequality

$\mathbb{E}\left[f(x^{t+1})-f^{*}\right]\leq(1-\gamma\mu)\mathbb{E}\left[f(x^{t})-f^{*}\right]+\frac{\gamma}{2}\mathbb{E}\left\|b(x^{k})\right\|^{2}+\frac{\gamma^{2}L}{2}\mathbb{E}\|n(x^{k})\|^{2}.$

Using lemma’s conditions we obtain the following inequality:

$\mathbb{E}\left[f(x^{t+1})-f^{*}\right]\leq(1-\gamma\mu)\mathbb{E}\left[f(x^{t})-f^{*}\right]+\frac{\gamma\delta^{2}}{2}+\frac{\gamma^{2}L\sigma^{2}}{2},$

or

$\mathbb{E}\left[f(x^{k})-f^{*}\right]\leq(1-\gamma\mu)^{k}\left(f(x^{0})-f^{*}\right)+\frac{\delta^{2}+\gamma
L\sigma^{2}}{2\mu}.$

∎

##  Appendix C Proof of Theorem 2.9

###### Proof.

Using Assumptions 2.2, Lemma 2.8, taking step size $\gamma=\frac{1}{L_{g}}$,
we can estimate convergence for function $f$:

$\mathbb{E}\left[f(\overline{x}^{k})-f^{*}\right]\leq\left(1-\frac{\mu}{L_{g}}\right)^{k}(f(\overline{x}^{0})-f^{*})+\frac{\Delta^{2}}{2\mu
n},$ (33)

until
$\mathbb{E}\left\|\mathbf{X}^{j}-\overline{\mathbf{X}}^{j}\right\|\leq\delta^{\prime}$
for $j<k$ where
$\Delta^{2}=18\left(L_{l}^{2}{\delta^{\prime}}+\sigma^{2}+\delta^{2}\right)$.

But really on iterations of Algorithm 2 we have access only to
$\mathbf{X}^{k}$. Let us find the sufficient communication step such that the
following expression is true:

$\mathbb{E}\left\|\mathbf{X}^{k}-\overline{\mathbf{X}}^{k}\right\|^{2}\leq{\delta^{\prime}}\Longrightarrow\mathbb{E}\left\|\mathbf{X}^{k+1}-\overline{\mathbf{X}}^{k+1}\right\|^{2}\leq{\delta^{\prime}}.$
(34)

By contraction property, we have

$\left\|\mathbf{X}^{k+1}-\overline{\mathbf{X}}^{k+1}\right\|\leq(1-\lambda)^{\left\lfloor\frac{T_{k}}{\tau}\right\rfloor}\left\|\mathbf{Z}^{k+1}-\overline{\mathbf{X}}^{k+1}\right\|.$
(35)

Here we used, that $\overline{\mathbf{Z}}^{k+1}=\overline{\mathbf{X}}^{k+1}$.
Let us estimate the right part of (35).

$\displaystyle\mathbb{E}\left\|\overline{\mathbf{X}}^{k+1}-\mathbf{Z}^{k+1}\right\|^{2}$
$\displaystyle\leq
2\mathbb{E}\left\|\overline{\mathbf{X}}^{k}-\mathbf{X}^{k}\right\|^{2}+2\gamma^{2}\mathbb{E}\left\|\widetilde{\nabla}F(\mathbf{X}^{k})\right\|^{2}$
$\displaystyle\leq
2\delta^{\prime}+6\gamma^{2}\mathbb{E}\left\|\widetilde{\nabla}F(\mathbf{X}^{k})-\nabla
F(\overline{\mathbf{X}}^{k})\right\|^{2}$
$\displaystyle\quad+6\gamma^{2}\mathbb{E}\left\|\nabla
F(\overline{\mathbf{X}}^{k})-\nabla
F(\overline{\mathbf{X}}^{*})\right\|^{2}+6\gamma^{2}\left\|\nabla
F(\overline{\mathbf{X}}^{*})\right\|^{2}$ $\displaystyle\leq
2\delta^{\prime}+6\gamma^{2}\Delta^{2}+6\gamma^{2}L_{g}^{2}\mathbb{E}\left\|\overline{\mathbf{X}}^{k}-\overline{\mathbf{X}}^{*}\right\|^{2}+6\gamma^{2}\left\|\nabla
F(\overline{\mathbf{X}}^{*})\right\|^{2}.$

From quadratic growth condition (9) we have

$\mathbb{E}\left\|\overline{\mathbf{X}}^{k}-\overline{\mathbf{X}}^{*}\right\|^{2}=n\mathbb{E}\left\|\overline{x}^{k}-\overline{x}^{*}\right\|^{2}\leq\frac{2n}{\mu}\mathbb{E}\left[f(x^{k})-f^{*}\right].$

Further, using the convergence rate (18) we can estimate the third value in
the sum above:

$\mathbb{E}\left\|\overline{\mathbf{X}}^{k}-\overline{\mathbf{X}}^{*}\right\|^{2}\leq\frac{2n}{\mu}\left(1-\frac{\mu}{L_{g}}\right)^{k+1}\left(F(\overline{\mathbf{X}}^{0})-F^{*}\right)+\frac{\Delta^{2}}{\mu^{2}}.$

Note, that $\mathbb{E}\xi\leq\sqrt{\mathbb{E}\xi^{2}}$ for any random value
$\xi$. Finally, we have that:

$\mathbb{E}\left\|\overline{\mathbf{X}}^{k+1}-\mathbf{Z}^{k+1}\right\|^{2}\leq
D,$

for $D$ such that:

$D=6\gamma^{2}\|\nabla
F(\overline{\mathbf{X}}^{*})\|^{2}+2\delta^{\prime}+6\left(\gamma^{2}+\frac{1}{\mu^{2}}\right)\Delta^{2}+\frac{12\gamma^{2}L_{g}^{2}}{\mu}\left(1-\frac{\mu}{L_{g}}\right)\left(F(\overline{\mathbf{X}}^{0})-F^{*}\right).$

So, for
$T_{k}=\tau\left\lceil\frac{1}{2\lambda}\log\left(\frac{D}{\delta^{\prime}}\right)\right\rceil$
the condition (34) is met. ∎

##  Appendix D Proof of Lemma 2.11

Proof For the given $\overline{\mathbf{X}}$ and $\overline{\mathbf{Y}}$, we
can estimate the bias in inexact gradient with respect to $Y$ in the following
form:

$\displaystyle\mathbb{E}\left\|\mathbb{E}_{\mathbf{X},\mathbf{Y},\xi}\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})-\nabla_{Y}\Phi(\overline{\mathbf{X}},\overline{\mathbf{Y}})\right\|^{2}\leq$
$\displaystyle
3\mathbb{E}\|\mathbb{E}_{\mathbf{X},\mathbf{Y},\xi}\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})-\mathbb{E}_{\mathbf{X},\mathbf{Y}}\nabla_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})\|^{2}$
$\displaystyle+3\mathbb{E}\left\|\mathbb{E}_{\mathbf{X},\mathbf{Y}}{\nabla}_{Y}\Phi(\mathbf{X},\mathbf{Y})-\mathbb{E}_{\mathbf{X}}\nabla_{\mathbf{Y}}\Phi(\mathbf{X},\overline{\mathbf{Y}})\right\|^{2}$
$\displaystyle+3\mathbb{E}\left\|\mathbb{E}_{\mathbf{X}}{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\overline{\mathbf{Y}})-\nabla_{\mathbf{Y}}\Phi(\overline{\mathbf{X}},\overline{\mathbf{Y}})\right\|^{2}$
$\displaystyle\leq$ $\displaystyle
3\mathbb{E}\left\|\mathbb{E}_{\xi}\widetilde{\nabla}_{Y}\Phi(\mathbf{X},\mathbf{Y})-\nabla_{Y}\Phi(\mathbf{X},\mathbf{Y})\right\|^{2}$
$\displaystyle+3\mathbb{E}\|{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})-\nabla_{Y}\Phi(\mathbf{X},\overline{\mathbf{Y}})\|^{2}$
$\displaystyle+3\mathbb{E}\left\|{\nabla}_{Y}\Phi(\mathbf{Y},\overline{\mathbf{Y}})-\nabla_{\mathbf{Y}}\Phi(\overline{\mathbf{X}},\overline{\mathbf{Y}})\right\|^{2}$
$\displaystyle\leq$ $\displaystyle
3\delta^{2}+3L_{yy}^{2}{\delta^{\prime}_{y}}+3L_{yx}^{2}{\delta^{\prime}_{x}}.$

In the inequality above we used fact that $\|a+b+c\|^{2}\leq
3\|a\|^{2}+3\|b\|^{2}+3\|c\|^{2}$ for each vectors $a,b$ and $c$. Note, for
the bias in $\overline{\widetilde{\nabla}}f(\overline{X}^{k})$ we proved in
the main part the following estimation

$\mathbb{E}\left\|\mathbb{E}_{X,\xi}\overline{\widetilde{\nabla}f}(X^{k})-{{\nabla}f}(\overline{x}^{k})\right\|^{2}\leq\frac{2\delta^{2}+L_{l}^{2}\delta^{\prime}}{{n}}.$
(36)

Also, we assume that the condition
$\mathbb{E}_{\mathbf{X}}\left\|\mathbf{X}^{j}-\overline{\mathbf{X}}^{j}\right\|^{2}\leq\delta^{\prime}$
holds for all $j\leq k$.

Let us estimate noise in $\overline{\widetilde{\nabla}}f(\overline{X}^{k})$.
For this, we estimate the second moment of random component in
$\widetilde{\nabla}F(\mathbf{X}^{k})$ for given $\overline{\mathbf{X}}^{k}$.
It is given by the expression
$\mathbb{E}_{\mathbf{X},\xi}\|\mathbb{E}_{\mathbf{X},\xi}\widetilde{\nabla}F(\mathbf{X}^{k})-\widetilde{\nabla}F(\mathbf{X}^{k})\|$.
Let us estimate inner part in the following way:

$\displaystyle\left\|\mathbb{E}_{\mathbf{X},\mathbf{Y},\xi}\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})-\widetilde{\nabla}_{Y}\Phi(\mathbf{X},\mathbf{Y})\right\|\leq$
$\displaystyle\left\|\mathbb{E}_{\mathbf{X},\mathbf{Y},\xi}\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})-\mathbb{E}_{\mathbf{X},\mathbf{Y}}\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})\right\|$
$\displaystyle+\left\|\mathbb{E}_{\mathbf{X},\mathbf{Y}}\widetilde{\nabla}_{Y}\Phi(\mathbf{X},\mathbf{Y})-\widetilde{\nabla}_{Y}\Phi(\mathbf{X},\mathbf{Y})\right\|$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{\mathbf{X},\mathbf{Y}}\left\|\mathbb{E}_{\xi}\widetilde{\nabla}_{Y}\Phi(X,Y)-\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})\right\|$
$\displaystyle+\left\|\mathbb{E}_{\mathbf{X},\mathbf{Y}}\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})-\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})\right\|.$

The last term can be estimated in similar way like in Appendix A:

$\displaystyle\mathbb{E}\left\|\mathbb{E}_{\mathbf{X},\mathbf{Y}}\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})-\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})\right\|^{2}\leq$
$\displaystyle
2\mathbb{E}\left\|\mathbb{E}_{\mathbf{X},\mathbf{Y}}{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})-{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})\right\|^{2}$
$\displaystyle+8\sigma^{2}+8\delta^{2}$ $\displaystyle\leq$ $\displaystyle
8L_{yy,l}^{2}{\delta^{\prime}_{y}}+8L_{yx,l}^{2}\delta^{\prime}_{x}+8\sigma^{2}+8\delta^{2},$

Finally, we can estimate required the second moment of noise component:

$\displaystyle\mathbb{E}\left\|\mathbb{E}_{\mathbf{X},\mathbf{Y},\xi}\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})-\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})\right\|^{2}\leq$
$\displaystyle
2\mathbb{E}\left\|\mathbb{E}_{\xi}\widetilde{\nabla}_{Y}\Phi(\mathbf{X},\mathbf{Y})-\widetilde{\nabla}_{\mathbf{Y}}\Phi(\mathbf{X},\mathbf{Y})\right\|^{2}$
$\displaystyle+16L_{yy,l}^{2}{\delta^{\prime}_{y}}+16L_{yx,l}^{2}\delta^{\prime}_{x}+16\sigma^{2}+16\delta^{2}$
$\displaystyle\leq$ $\displaystyle
16L_{yy,l}^{2}{\delta^{\prime}_{y}}+16L_{yx,l}^{2}\delta^{\prime}_{x}+18\sigma^{2}+16\delta^{2}$

Whence we can conclude, that

$\mathbb{E}\left\|\mathbb{E}\overline{\widetilde{\nabla}_{\mathbf{Y}}\phi}(\mathbf{X},\mathbf{Y})-\overline{\widetilde{\nabla}_{\mathbf{Y}}\phi}(\mathbf{X},\mathbf{Y})\right\|\leq\frac{16L_{yy,l}^{2}{\delta^{\prime}_{y}}+16L_{yx,l}^{2}\delta^{\prime}_{x}+18\sigma^{2}+16\delta^{2}}{n}.$
(37)

∎

##  Appendix E  Proof of Lemma 2.12

###### Proof.

In the similar way, like for the gradient with respect to the inner variable
$\mathbf{Y}$, we can estimate the mathematical expectation of bias with
respect to the outer variable $\mathbf{X}$:

$\displaystyle\mathbb{E}\left\|\mathbb{E}_{\mathbf{X},\mathbf{Y},\xi}\widetilde{\nabla}_{\mathbf{X}}\Phi(\mathbf{X},\mathbf{Y})-\nabla
F\left(\overline{\mathbf{X}}\right)\right\|^{2}\leq$ $\displaystyle
3\mathbb{E}\left\|\mathbb{E}_{\mathbf{X},\mathbf{Y},\xi}\widetilde{\nabla}_{\mathbf{X}}\Phi(\mathbf{X},\mathbf{Y})-\mathbb{E}_{\mathbf{X},\mathbf{Y}}\nabla_{\mathbf{X}}\Phi(\mathbf{X},\mathbf{Y})\right\|^{2}$
$\displaystyle+3\mathbb{E}\left\|\mathbb{E}_{\mathbf{X},Y}{\nabla}_{\mathbf{X}}\Phi(\mathbf{X},\mathbf{Y})-\mathbb{E}_{\mathbf{X}}\nabla_{\mathbf{X}}\Phi(\mathbf{X},\overline{\mathbf{Y}}^{*}(\mathbf{X}))\right\|^{2}$
$\displaystyle+3\mathbb{E}\left\|\mathbb{E}_{\mathbf{X}}{\nabla}_{\mathbf{X}}\Phi(\mathbf{X},\overline{\mathbf{Y}}^{*}(\mathbf{X}))-\nabla_{\mathbf{X}}\Phi(\overline{\mathbf{X}},\overline{\mathbf{Y}}^{*}(\mathbf{X}))\right\|^{2}$
$\displaystyle\leq$ $\displaystyle
3\mathbb{E}\left\|\mathbb{E}_{\xi}\widetilde{\nabla}_{\mathbf{X}}\Phi(\mathbf{X},\mathbf{Y})-\nabla_{\mathbf{X}}\Phi(\mathbf{X},\mathbf{Y})\right\|^{2}$
$\displaystyle+3\mathbb{E}\left\|{\nabla}_{\mathbf{X}}\Phi(\mathbf{X},\mathbf{Y})-\nabla_{\mathbf{X}}\Phi(\mathbf{X},\overline{\mathbf{Y}}^{*}(\mathbf{X}))\right\|^{2}$
$\displaystyle+3\mathbb{E}\left\|{\nabla}_{\mathbf{X}}\Phi(\mathbf{X},\overline{\mathbf{Y}}^{*}(\mathbf{X})-\nabla_{\mathbf{X}}\Phi(\overline{\mathbf{X}},\overline{\mathbf{Y}}^{*}(\mathbf{X}))\right\|^{2}$
$\displaystyle\leq$ $\displaystyle
3\delta^{2}+3L_{xx}^{2}{\delta^{\prime}_{x}}+6L_{xy}^{2}\left({\frac{2{\varepsilon}_{y}}{\mu_{y}}}+\frac{\Delta_{y}^{2}}{\mu_{y}^{2}{n}}+{\delta^{\prime}_{y}}\right).$

Note, that the noise component in the inexact gradient
$\overline{\widetilde{\nabla}_{\mathbf{X}}\phi}(\mathbf{X},\mathbf{Y})$ does
not depend on inexactness on solution by inner problem. So, repeating steps
above for inexact gradient with respect to the variable $\mathbf{X}$, we can
obtain the following estimation

$\mathbb{E}\left\|\mathbb{E}\overline{\widetilde{\nabla}_{\mathbf{X}}\phi}(\mathbf{X},\mathbf{Y})-\overline{\widetilde{\nabla}_{\mathbf{X}}\phi}(\mathbf{X},\mathbf{Y})\right\|\leq\frac{16L_{xy,l}^{2}{\delta^{\prime}_{y}}+16L_{xx,l}^{2}\delta^{\prime}_{x}+18\sigma^{2}+16\delta^{2}}{n}.$
(38)

Note, that the variable $Y$ in (38) is a result of the inner loop in Algorithm
3. The estimations (37) and (38) give the bounds on the second norm of noise.
∎