Decentralized Finite-Sum Optimization over Time-Varying Networks

## Abstract

Abstract We consider decentralized time-varying stochastic optimization problems where each of the functions held by the nodes has a finite sum structure. Such problems can be efficiently solved using variance reduction techniques. Our aim is to explore the lower complexity bounds (for communication and number of stochastic oracle calls) and find optimal algorithms. The paper studies strongly convex and nonconvex scenarios. To the best of our knowledge, variance reduced schemes and lower bounds for time-varying graphs have not been studied in the literature. For nonconvex objectives, we obtain lower bounds and develop an optimal method GT-PAGE. For strongly convex objectives, we propose the first decentralized time-varying variance-reduction method ADOM+VR and establish lower bound in this scenario, highlighting the open question of matching the algorithms complexity and lower bounds even in static network case.

## 1 Introduction

We consider a sum-type problem

$$ $\min_{x\in\mathbb{R}^{d}}~{}F(x):=\sum_{i=1}^{m}F_{i}(x),$ (1) $$

where $F_{i}(x)=\frac{1}{n}\sum_{j=1}^{n}f_{ij}(x)$. We assume that for each $i=1,\ldots,m$ the set of functions $\left\{f_{ij}\right\}_{j=1}^{n}$ is stored at node $i$. Decentralized optimization has applications in power system control Ram et al., (); Gan et al., (), distributed statistical inference Forero et al., (); Nedić et al., (), vehicle coordination and control Ren and Beard, (), distributed sensing Rabbat and Nowak, (); Bazerque and Giannakis, (). In most scenarios, the data is generated in a distributed way. In applications such as federated learning Konečný et al., (); McMahan et al., (), centralized data processing is not allowed by privacy constraints.

In this paper, we focus on time-varying networks. That is, between consequent data exchanges, the topology of communication graph may change Zadeh, (); Nedić, (). The set of nodes remains the same, while the set of edges changes. The instability of links practically happens due to malfunctions in communication, such as a loss of wireless connection between sensors or drones.

Our Contribution. We propose lower bounds in the strongly convex and nonconvex case, an optimal algorithm in the nonconvex case, and an algorithm in the strongly convex case with an open question about its optimality.

1. We propose a method for decentralized finite-sum optimization over time-varying graphs ADOM+VR (Algorithm 1). The method is based on the combination of ADOM+ algorithm for non-stochastic decentralized optimization over time-varying networks and loopless Katyusha approach for finite-sum problems .

2. For nonconvex decentralized optimization over time-varying graphs, we propose an optimal algorithm GT-PAGE (Algorithm 2). The main idea is to implement the PAGE gradient estimator Li et al., () for finite-sum problem into the gradient tracking Nedic et al., ().

3. We give lower complexity bounds for decentralized finite-sum optimization over time-varying networks for strongly-convex (Theorem 4.3) and nonconvex (Theorem 4.5) objectives with taking into account the sensivity of smoothness constants from Assumptions 2.1, 2.2 and 2.3

**Table 1: Computational (the number of stochastic oracle calls per node) and communication complexities of decentralized methods for finite-sum strongly convex optimization over time-varying graphs. $O(\cdot)$ notation and $\log(1/\varepsilon)$ factor are omitted. Comment " static" means that the method only works over time-static networks. Comment " dual" means that the method is dual-based. For notation, see Section 2.**
| Algorithm | Comp. | Comm. |
| --- | --- | --- |
| ADOM | $n\sqrt{\frac{L}{\mu}}$ | $\chi\sqrt{\frac{L}{\mu}}$ (dual) |
| ADOM+ | $n\sqrt{\frac{L}{\mu}}$ | $\chi\sqrt{\frac{L}{\mu}}$ |
| Acc-GT<br>Li and Lin, () | $n\sqrt{\frac{L}{\mu}}$ | $\chi\sqrt{\frac{L}{\mu}}$ |
| ADFS<br>Hendrikx et al., () | $n+\sqrt{n\max_{i}\frac{L_{i}}{\mu_{i}}}$ | $\sqrt{\chi}\sqrt{\max_{i}\frac{L_{i}}{\mu_{i}}}$ (static + dual) |
| Acc-VR-EXTRA<br>Li et al., () | $n+\sqrt{n\frac{L}{\mu}}$ | $\sqrt{\chi\frac{L}{\mu}}$ (static) |
| ADOM+VR<br>Alg. 1, this paper | $n+\sqrt{n\frac{L}{\mu}}$ | $\chi\sqrt{\frac{L}{\mu}}$ |
| Lower bound<br>Th. 4.3, this paper | $n+\sqrt{n\max_{i}\frac{L_{i}}{\mu_{i}}}$ | $\chi\sqrt{\max_{i}\frac{L_{i}}{\mu_{i}}}$ |

Related Work. Decentralized optimization over static and time-varying networks has been actively developing in recent years. In Scaman et al., (), dual-based methods and lower bounds for (non-stochastic) strongly convex optimization over static graphs were proposed. Optimal primal methods were obtained in . For time-varying networks, non-accelerated primal Nedic et al., () and dual Maros and Jaldén, () methods were proposed. After that, accelerated algorithms were given in for dual oracle and in ; Li and Lin, () for primal oracle. These methods match the lower complexity bounds for time-varying graphs developed in .

Our paper is devoted to variance reduced schemes. Classical variance reduction methods such as SAGA Defazio et al., () and SVRG Johnson and Zhang, () allow to enhance the rates for stochastic optimization problems with finite-sum structure. Accelerated variance reduced schemes require adding a negative momentum, also referred to as Katyusha momentum Allen-Zhu, (). Considering nonconvex problems, recent development starts with Reddi et al., () and Allen-Zhu and Hazan, (), where algorithms based on SVRG were proposed. More recently, other modifications of SVRG scheme with the same gradient complexity $\mathcal{O}\left(n+n^{2/3}/{\epsilon^{2}}\right)$ were proposed in Li and Li, (), Ge et al., () and Horváth and Richtárik, (). Moreover, optimal algorithms was presented, such as Spider Fang et al., (), SNVRG Zhou et al., (), methods based on SARAH Nguyen et al., () (e.g. SpiderBoost Wang et al., (), ProxSARAH Pham et al., (), Geom-SARAH Horváth et al., ()) and PAGE Li et al., (), which have $\mathcal{O}\left(n+\sqrt{n}/{\epsilon^{2}}\right)$ gradient estimation complexity.

**Table 2: Computational (the number of stochastic oracle calls per node) and communication complexities of decentralized methods for finite-sum nonconvex optimization over time-varying graphs. $O(\cdot)$ notation is omitted. Comment " static" means that the method only works over time-static networks. Here $L_{s}=\max_{i,j}L_{ij}$ from 2.1, $L$ from 2.2 and $\hat{L}$ from 2.3. For notation, see Section 2.**
| Algorithm | Comp. | Comm. |
| --- | --- | --- |
| GT-SAGA | $\big{(}1+\frac{n^{2/3}}{m^{1/3}}+\sqrt{n}\big{)}\frac{L_{s}\Delta}{\varepsilon<br>^{2}}$ | $\sqrt{\chi}\big{(}1+\frac{n^{2/3}}{m^{1/3}}+\sqrt{n}\big{)}\frac{L_{s}\Delta}{<br>\varepsilon^{2}}$   (static) |
| GT-SARAH<br>Xin et al., () | $(m+\sqrt{nm}+n^{1/3}m^{2/3})\frac{L_{s}\Delta}{\varepsilon^{2}}$ | $\sqrt{\chi}\frac{L_{s}\Delta}{\varepsilon^{2}}$    (static) |
| DESTRESS | $n+\frac{\sqrt{n}L_{s}\Delta}{\varepsilon^{2}}$ | $\sqrt{\chi}\big{(}\sqrt{mn}+\frac{L_{s}\Delta}{\varepsilon^{2}}\big{)}$   (static) |
| DEAREST<br>Luo and Ye, () | $n+\frac{\sqrt{n}\hat{L}\Delta}{\varepsilon^{2}}$ | $\sqrt{\chi}\frac{\hat{L}\Delta}{\varepsilon^{2}}$   (static) |
| GT-PAGE<br>Alg. 2, this paper | $n+\frac{\sqrt{n}\hat{L}\Delta}{\varepsilon^{2}}$ | $\chi\frac{L\Delta}{\varepsilon^{2}}$ |
| Lower bound<br>Th. 4.5, this paper | $n+\frac{\sqrt{n}\hat{L}\Delta}{\varepsilon^{2}}$ | $\chi\frac{L\Delta}{\varepsilon^{2}}$ |

In strongly-convex decentralized optimization over static graphs, optimal variance reduced methods ADFS Hendrikx et al., () and Acc-VR-EXTRA were proposed. The corresponding lower bounds were given in Hendrikx et al., (). For variational inequalities, variance reduction is also applicable Alacaoglu and Malitsky, (). Moreover, optimal methods for decentralized finite-sum variational inequalities were proposed in Kovalev et al., () both for static and time-varying networks. See an overview of methods for strongly-convex objectives in Table 1.

In the nonconvex case, the result of first application of variance reduction and gradient tracking to decentralized optimization for static graphs was the method D-GET Sun et al., (). Later, algorithms GT-SAGA , GT-HSGD  and GT-SARAH Xin et al., () were proposed, which improve the complexity of communication rounds and local computations comparing to D-GET. A relatively new result was achieved by the method DESTRESS , which is optimal in terms of local computations, but ineffective in terms of number of communications in case of static graphs. This method was improved into DEAREST Luo and Ye, (), which is optimal. Nevertheless, the application of variance reduction has not been studied for the case of nonconvex decentralized optimization over time-varying graphs. In Table 2 we present an overview of methods for which it is possible to explicitly write out complexities in terms of constants of smoothness and $\chi$. For an overview of other algorithms, see Table 1 in Xin et al., () and Table 1 in .

###### Remark 1.1 .

It is necessary to clarify that optimality of DESTRESS and DEAREST is not clear in terms of dependence on smoothness constants. Indeed, mentioned constants $L_{s},\hat{L}$ and $L$ are sensitive to $n$. In Section C.5 we show that ratios $\sqrt{n}L=\hat{L}$ and $nL=L_{s}$ can be achieved.

Paper Organization. We organize the paper as follows. In Section 2, we introduce notation and assumptions on the objectives and communication network. In Section 3, we describe our methods and give complexity results. Section 3.2 describes ADOM+VR for strongly convex objectives and Section 3.3 covers GT-PAGE for nonconvex objectives. Lower bounds are provided in Section 4. Finally, in Section 5 we give concluding remarks.

###### Remark 1.1 .

## 2 Notation and Assumptions

Throughout this paper, we adopt the following notations: We denote by $||\cdot||=||\cdot||_{2}$ the norm in $L_{2}$ space. The Kronecker product of two matrices is denoted as $A\otimes B$. We use $\mathcal{D}(X)$ to denote some distribution over a finite set $X$. The sets of batch indices are denoted by $S$, expressed as $S=(\xi^{1},\ldots,\xi^{b})$, where $\xi^{j}$ is a tuple of $m$ elements, each corresponding to a node, specifically $\xi^{j}=(\xi^{j}_{1},\ldots,\xi^{j}_{m})$, with $\xi_{i}^{j}$ being the index of the local function on $i$-th node in $j$-th element of the batch. Also for each $i=1,\ldots,m$ define $S_{i}=(\xi_{i}^{1},\ldots,\xi_{i}^{b})$. Each node maintains its own copy of a variable corresponding to a specific variable in the algorithm. The variables in the algorithm are aggregations of the corresponding node variables:

$$ $x=(x_{1},x_{2},\ldots,x_{m})\in\mathbb{R}^{d\times m}.$ $$

With a slight abuse of notation we will denote $F(x)=\sum_{i=1}^{m}F_{i}(x_{i})$ and $\nabla F(x)=\left(\nabla F_{1}(x_{1}),\ldots,\nabla F_{m}(x_{m})\right).$
Linear operations and scalar products are performed component-wise in a decentralized way. Let us introduce an auxiliary subspace $\mathcal{L}=\{x\in\mathbb{R}^{d\times m}|x_{1}=\ldots=x_{m}\}$, respectively $\mathcal{L}^{\perp}=\{x\in\mathbb{R}^{d\times m}|x_{1}+\ldots+x_{m}=0\}$. We also let $x^{*}=\operatorname*{arg\,min}_{x\in\mathbb{R}^{d}}F(x)$ or $x^{*}=\operatorname*{arg\,min}_{x\in\mathbb{R}^{d\times m}}F(x)$, depending on the context.

Let us pass to assumptions on objective functions. Firstly, we assume that objectives are smooth, which is a standard assumption for optimization. We introduce different concepts of smoothness: Assumptions 2.1, 2.2 and 2.4 are used in Algorithm 1; Assumptions 2.2 and 2.3 are for Algorithm 2.

###### Assumption 2.1 .

For each $i=1,\ldots,m$ and $j=1,\ldots,n$ function $f_{ij}$ is convex and $L_{ij}$-smooth, i.e.

$$ $\displaystyle\|\nabla f_{ij}(y)-\nabla f_{ij}(x)\|\leq L_{ij}\|y-x\|.$ $$

For each $i=1,\ldots,m$ let us define

$$ $\overline{L}_{i}=\frac{1}{n}\sum_{j=1}^{n}L_{ij},\text{ }\overline{L}=\max_{i} \left\{\overline{L}_{i}\right\}.$ $$

###### Assumption 2.2 .

For each $i=1,\ldots,m$ function $F_{i}$ is $L$-smooth, i.e.

$$ $\displaystyle\|\nabla F_{i}(y)-\nabla F_{i}(x)\|\leq L\|y-x\|.$ $$

Note that in the context of Assumption 2.1 and Assumption 2.2, the following holds for the smallest possible $L_{ij}$ and $L$:

$$ $\displaystyle L\leq\overline{L}\leq nL.$ $$

In the next assumption, we introduce average smoothness constants. That is used in analysis of Algorithm 2.

###### Assumption 2.3 .

For each $i=1,\ldots,m$ function $F_{i}$ is $\hat{L}$-average smooth, i.e.

$$ $\displaystyle\frac{1}{n}\sum\limits_{j=1}^{n}\|\nabla f_{ij}(y)-\nabla f_{ij}( x)\|^{2}\leq\hat{L}^{2}\|y-x\|^{2}.$ $$

Finally, we introduce an assumption on strong convexity

###### Assumption 2.4 .

For each $i=1,\ldots,m$ function $F_{i}$ is $\mu$-strongly convex, i.e.

$$ $\displaystyle F_{i}(y)\geq F_{i}(x)+\langle\nabla F_{i}(x),y-x\rangle+\frac{ \mu}{2}\|y-x\|^{2}_{2}.$ $$

Decentralized communication is represented by a sequence of graphs $\left\{\mathcal{G}^{k}=(\mathcal{V},\mathcal{E}^{k})\right\}_{k=0}^{\infty}$. With each graph, we associate a gossip matrix $\mathbf{W}(k)$.

###### Assumption 2.5 .

For each $k=0,1,2,\ldots$ it holds

- 1.
$[\mathbf{W}(k)]_{i,j}\neq 0$ if and only if $(i,j)\in\mathcal{E}^{k}$ or $i=j$,
- 2.
$\ker\mathbf{W}(k)\supset\left\{(x_{1},\ldots,x_{m})\in\mathbb{R}^{n}:x_{1}=
\ldots=x_{m}\right\}$,
- 3.
$\mathrm{range}\mathbf{W}(k)\subset\left\{(x_{1},\ldots,x_{m})\in\mathbb{R}^{n}
:\sum_{i=1}^{m}x_{i}=0\right\}$,
- 4.
There exists $\chi\geq 1$, such that
$\displaystyle\|\mathbf{W}(k)x-x\|^{2}\leq(1-\chi^{-1})\|x\|^{2}$
(2)
$\displaystyle\text{ for all }x\in\left\{(x_{1},\ldots,x_{m})\in\mathbb{R}^{d
\times m}:\sum_{i=1}^{m}x_{i}=0\right\}.$

In particular, matrices $\mathbf{W}(k)$ can be chosen as $\mathbf{W}(k)=\mathbf{L}(\mathcal{G}^{k})/\lambda_{\max}(\mathbf{L}(\mathcal{G
}^{k}))$, where $\mathbf{L}(\mathcal{G}^{k})$ denotes a graph Laplacian matrix. Moreover, if the network is constant ($\mathcal{G}^{k}\equiv\mathcal{G}$), we have $\chi=\lambda_{\max}(\mathbf{L}(\mathcal{G}))/\lambda_{\min}^{+}(\mathbf{L}(
\mathcal{G}))$, i.e. $\chi$ equals the graph condition number.

###### Assumption 2.1 .

###### Assumption 2.2 .

###### Assumption 2.3 .

###### Assumption 2.4 .

###### Assumption 2.5 .

## 3 Algorithms

We propose optimal methods for decentralized finite-sum optimization: Algorithm 1 for strongly convex case and Algorithm 2 for nonconvex case. Both algorithms use a variance reduction technique. The main idea of variance reduced methods is a special gradient estimator. The estimator is computed w.r.t. a snapshot of the full gradient. If the objective is a sum of $q$ functions, one recomputes the full gradient (over all samples) once in $O(q)$ iterations Johnson and Zhang, (); Allen-Zhu, (). In a loopless approach the full gradient is computed with a probability of order $O(1/q)$ at each iteration. In this paper, we use the latter technique.

We measure the complexity in two ways: number of communications and number of stochastic oracle calls. The computational complexity of the algorithm iterations can be controlled using mini-batching of the gradient. That is, we take $b$ gradient estimations and average them. If the batch size is large, the number of algorithm iterations decreases, but the number of oracle calls per iteration is increased by $b$ times. In Katyusha Allen-Zhu, () it is shown that an optimal batch size is $b\sim\sqrt{n}$. In the analysis of Algorithms 1 and 2, we obtain optimal batch sizes, as well.

### 3.1 Multi-Stage Consensus

There is a universal way to divide oracle and communication complexities of a decentralized optimization method. Instead of performing one synchronized communication, let us perform several iterations in a row. Following , we introduce

$$ $\displaystyle\mathbf{W}(k;T)=\mathbf{I}_{m}-\Pi_{q=kT}^{(k+1)T-1}(\mathbf{I}_{ m}-\mathbf{W}(q))$ $$

It can be shown that if we take $T=\lceil\chi\rceil$, then condition number of $\mathbf{W}(k;T)$ reduces to $O(1)$. To see that, note that for all $x\in\mathcal{L}^{\bot}$ it holds

$$ $\displaystyle\|\mathbf{W}(k;T)x-x\|^{2}$ $\displaystyle\leq(1-\chi^{-1})^{T}\|x\|^{2}$ $\displaystyle\leq\exp(-T\chi^{-1})\leq e^{-1}.$ $$

In other words, by using multi-stage consensus we reduce $\chi$ to $O(1)$ by paying a $\lceil\chi\rceil$ times more communications per iteration.

###### Remark 3.1 .

For static networks, Chebyshev acceleration replaces multi-stage consensus Scaman et al., (). Term $\chi$ in complexity is reduced to $O(1)$ at the cost of performing $\lceil\sqrt{\chi}\rceil$ communications per iteration. (Static) gossip matrix $\mathbf{W}$ is replaced by a Chebyshev polynomial $P(\mathbf{W})$.

###### Remark 3.1 .

### 3.2 Strongly Convex Case

For the strongly convex case, we take ADOM+  as a base decentralized method. We also use a gradient estimator averaged over a mini-batch and a negative Katyusha momentum Allen-Zhu, (); .

Let’s briefly discuss the idea of ADOM+. The given optimization problem can be written in decentralized form as follows:

$$ $\min_{x\in\mathcal{L}}F(x).$ $$

This can be further reformulated as follows, which is the basis for the ADOM+ method:

$$ $\min_{x\in\mathbb{R}^{d\times m}}\max_{y\in\mathbb{R}^{d\times m}}\max_{z\in \mathcal{L}^{\perp}}F(x)-\frac{\nu}{2}\|x\|^{2}-\langle y,x\rangle-\frac{1}{2 \nu}\|y+z\|^{2}.$ $$

It is not difficult to show that in case $\nu<\mu$, this saddle point problem is strongly convex, which means that it has a single solution $(x^{*},y^{*},z^{*})$ satisfying the optimality conditions:

$$ $\displaystyle 0$ $\displaystyle=\nabla F(x^{*})-\nu x^{*}-y^{*},$ (3) $\displaystyle 0$ $\displaystyle=\nu^{-1}(y^{*}+z^{*})+x^{*},$ (4) $\displaystyle 0$ $\displaystyle\ni y^{*}+z^{*}.$ (5) $$

The idea is described in more detail in .

Let us discuss the gradient estimator for strongly convex setup. Consider a minimization problem $\min_{x\in\mathbb{R}^{d}}g(x)=\frac{1}{q}\sum_{i=1}^{q}g_{i}(x)$. At step $k$, instead of the gradient $\nabla g(x^{k})$ one uses an estimator

$$ $\displaystyle\nabla^{k}=\frac{1}{b}\sum_{i\in S}[\nabla g_{i}(x^{k})-\nabla g_ {i}(w^{k})]+\nabla g(w^{k}),$ (6) $$

where $S$ is a random batch of indices of size $b$, $x^{k}$ is the current iterate and $w^{k}$ is a reference point at which the full gradient is computed. Gradient estimator (6) is used in such methods as SVRG Johnson and Zhang, () and Katyusha Allen-Zhu, ().

Figure: Algorithm 1 ADOM+VR

###### Theorem 3.2 .

Let Assumptions 2.1, 2.2, 2.4, 2.5 and $b\geq\overline{L}/L$ hold. Then Algorithm 1 requires $N$ iterations to yield $x^{N}$ such that $\|x^{N}-x^{*}\|^{2}\leq\varepsilon$, where

$$ $N=\mathcal{O}\left(\left(\frac{n}{b}+\left(\frac{\sqrt{n}}{b}+\frac{n\overline {L}}{b^{2}L}+\chi\right)\sqrt{\frac{L}{\mu}}\right)\log\frac{1}{\epsilon} \right).$ $$

###### Corollary 3.3 .

In the setting of Theorem 3.2, with $b\sim\max\left\{\sqrt{n\overline{L}/L},n\sqrt{\mu/L}\right\}$ and the number of communications per iteration $\sim\chi$, the algorithm requires

$$ $\mathcal{O}\left(n+\sqrt{\frac{n\overline{L}}{\mu}}\right)\log\frac{1}{\epsilon}$ $$

oracle calls per node and

$$ $\mathcal{O}\left(\chi\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon}\right)$ $$

communication iterations to reach $\|x^{N}-x^{*}\|^{2}\leq\epsilon$.

###### Proof.

The proof may be found in Appendix A.
∎

###### Theorem 3.2 .

###### Corollary 3.3 .

###### Proof.

### 3.3 Nonconvex Case

For the nonconvex setup, we propose a method based on a combination of gradient tracking and PAGE gradient estimator Li et al., (). The main idea of this approach consists of two parts.

Gradient Tracking. Gradient tracking scheme can be written as in Nedic et al., ():

$$ $\displaystyle x^{k+1}$ $\displaystyle=\mathbf{W}^{k}x^{k}-\eta y^{k}$ $\displaystyle y^{k+1}$ $\displaystyle=\mathbf{W}^{k}y^{k}+\nabla F(x^{k+1})-\nabla F(x^{k})$ $$

Such an algorithm leads to $y_{i}^{k}$ being an approximation of the average gradient from all devices in the network at each iteration.

PAGE. The key meaning of PAGE is as follows. Calculating the full gradient can be expensive, but finite-sum construction allows to count the batched gradient, which is clearly lower in computational cost. Moreover, PAGE update does not have any loops (as, for example, in SVRG Johnson and Zhang, ()) and can be computed recursively as follows:

$$ $\displaystyle\nabla^{k+1}=\frac{1}{b}\sum_{i\in S}\left[\nabla g_{i}(x^{k+1})- \nabla g_{i}(x^{k})\right]+\nabla^{k},$ (7) $$

where $S$ denotes a random set of indices of size $b$. Note that unlike estimator (6) for strongly convex case, PAGE estimator (7) stores the gradient from previous iteration, not only the gradient snapshot.

Figure: Algorithm 2 GT-PAGE

###### Theorem 3.4 .

Let Assumptions 2.2, 2.3 and 2.5 hold. Then, Algorithm 2 requires $N$ iterations to yield $\hat{x}^{N}$, which is randomly taken from $\{\bar{x}^{k}\}_{k=0}^{N-1}$ such that $\mathbb{E}\left[\|\nabla F(\hat{x}^{N})\|^{2}\right]\leq\epsilon^{2}$, where

$$ $\displaystyle N=\mathcal{O}\left(\frac{\chi^{3}L\Delta\left(1+\sqrt{\frac{(1-p )\hat{L}^{2}}{bpL^{2}}}\right)}{\epsilon^{2}}\right),$ $$

where $\Delta=F(x_{0})-F^{*}$.

###### Corollary 3.5 .

In the setting of Theorem 3.4, let $b=\frac{\sqrt{n}\hat{L}}{L},~{}p=\frac{b}{n+b}$ and number of communications per iteration $\chi$. Then Algorithm 2 requires

$$ $\displaystyle\mathcal{O}\left(n+\frac{\sqrt{n}\hat{L}\Delta}{\varepsilon^{2}}\right)$ $$

oracle calls per node and

$$ $\displaystyle\mathcal{O}\left(\frac{\chi L\Delta}{\varepsilon^{2}}\right)$ $$

communications to reach accuracy $\varepsilon$, i.e. $\mathbb{E}\left[\|\nabla F(\hat{x}^{N})\|^{2}\right]\leq\epsilon^{2}$.

Proofs of Theorem 3.4 and Corollary 3.5 can be found in Section C.3 and Section C.4 respectively.

###### Remark 3.6 .

It should be clarified that in the case of time-static graphs the multi-step communication procedure called Chebyshev acceleration allows us to go from $\chi$ to $\sqrt{\chi}$ in the estimation on the number of communications.

###### Theorem 3.4 .

###### Corollary 3.5 .

###### Remark 3.6 .

## 4 Lower Bounds

In this section, we present lower bounds for the strongly convex case in terms of Hendrikx et al., () and for the nonconvex case. It is important to note that the setup for the strongly convex case in which lower bounds for stochastic problems are considered is different from the class of problems analyzed in this article, which will be discussed in more detail later.

The high-level concept underlying lower bounds in decentralized optimization involves creating a decentralized counterexample problem, where information exchange between two vertex clusters is slow. More specifically, the vertices in the counterexample are divided into three types: the first type can potentially “transfer” the gradient from even positions to the next, introducing a new dimension, the second type can do so from odd positions, the third type does nothing. We take a “bad” function for the corresponding optimization problem and divide it by the corresponding node types in such a way that different clusters contain components of the "bad" function that can approach the solution only after “communicating” with nodes from another cluster.

It is also worth noting that the lower bounds in non-stochastic setting have a different interpretation than in stochastic one. Namely, in classical decentralized optimization, the lower bounds on the number of computational iterations are given in terms of the number of iterations when the network performs local computations without exchanging information. However, in stochastic setting, the lower bounds is interpreted as the maximum number of stochastic oracle calls per node, which forces almost the entire “bad” function to be put into a single node. This is exactly the problem that underlies the current divergence of upper and lower bounds in the strongly convex case.

Strongly Convex Case. Lower bounds for a static network for non-stochastic problems were first presented in Scaman et al., (). It has been shown that to reach an $\epsilon$-solution of the problem, the system requires $\Omega\left(\sqrt{\chi L/\mu}\log(1/\epsilon)\right)$ communication iterations and $\Omega\left(\sqrt{{L}/{\mu}}\log(1/\epsilon)\right)$ computational iterations. In , lower bounds for a time-varying setting were presented, the differs occur in communication complexity, in particular one needs to perform $\Omega\left(\chi\sqrt{L/\mu}\log(1/\epsilon)\right)$ communication iterations to reach $\varepsilon$-solution. Regarding stochastic setup, in Hendrikx et al., (), lower bounds of $\Omega(\sqrt{\chi\kappa_{b}}\log(1/\varepsilon))$ communication iterations and $\Omega(n+\sqrt{n\kappa_{s}}\log(1/\varepsilon))$ oracle calls per node were presented, where $\kappa_{b}=\max_{i}\{L_{i}/\mu_{i}\}$ is the maximum of the condition numbers of functions at nodes, and $\kappa_{s}=\max_{i}\{\bar{L}_{i}/\mu_{i}\}$ is stochastic condition number among local function at nodes. Also, an optimal dual-based method was proposed.

Nonconvex Case. At first, lower bounds for finite-sum nonconvex problem were presented in Fang et al., (). It has been shown that for reaching $\epsilon$-accuracy $(\mathbb{E}\left[\|\nabla F(x)\|^{2}\right]\leq\epsilon^{2})$ $\Omega\big{(}\sqrt{n}\hat{L}/\epsilon^{2}\big{)}$ gradient estimates is required. Moreover, this lower bound was extended in Li et al., () to $\Omega\big{(}n+\sqrt{n}\hat{L}/\epsilon^{2}\big{)}$.

Considering a decentralized optimization problem without variance reduction, there are both estimates of lower bounds for static (e.g. Yuan et al., ()) and time-varying (e.g. Huang and Yuan, ()) graphs, which are equal to $\Omega\big{(}\sqrt{\chi}{L}\Delta/\epsilon^{2}\big{)}$ and
$\Omega\big{(}\chi{L}\Delta/\epsilon^{2}\big{)}$ communications respectively.

The combination of decentralized nonconvex optimization with variance reduction has been studied only in the case of static graphs, e.g., in Luo and Ye, (), where authors show that lower bounds are $\Omega\big{(}\sqrt{\chi}\hat{L}\Delta/\epsilon^{2}\big{)}$ and $\Omega\big{(}n+\sqrt{n}\hat{L}\Delta/\epsilon^{2}\big{)}$ in their assumptions for the number of communication rounds and local computations per node respectively.

### 4.1 First-order Decentralized Algorithms

Following and Hendrikx et al., (), let us formalize the concept of a decentralized optimization algorithm. The procedure will consist of two types of iterations: communicational iterations, in which nodes cannot access the oracle, but only exchange information with neighbors, and computational iterations, in which nodes do not communicate with each other, but only perform local computations in their memory. Let time be discrete, each iteration $k$ is either communicational or computational. For any vertex $i$, denote by $\mathcal{H}_{i}(k)$ the local memory at $k$th iteration. Then the following inclusions hold:

1. For all $i=1,\ldots,m$, if nodes perform a local computation at step $k$, local information is updated as

$$ $\displaystyle\mathcal{H}_{i}(k+1)\subseteq\text{span}\bigg{(}\bigcup_{j=1}^{n} \{x,\nabla f_{ij}(x),\nabla f_{ij}^{*}(x)x\in\mathcal{H}_{i}(k)\}\bigg{)}.$ $$

2. For all $i=1,\ldots,m$, if nodes perform a communicational iteration at time step $k$, local information is updated as

$$ $\mathcal{H}_{i}(k+1)\subseteq\text{span}\left(\bigcup_{j\in\mathcal{N}^{k}_{i} }\mathcal{H}_{j}(k)\cup\mathcal{H}_{i}(k)\right),$ $$

where $\mathcal{N}^{k}_{i}$ is neighbours of node $i$ at $k$th step.

### 4.2 Strongly Convex Case

In the strongly convex case, we formulate the lower bounds under slightly different assumptions. We let each function $F_{i}$ have its own smoothness and strong convexity parameters.

###### Assumption 4.1 .

For each $i=1,\ldots,m$ function $F_{i}$ is $\mu_{i}$-strongly convex and $L_{i}$-smooth.

###### Assumption 4.2 .

For all $i=1,\ldots,m$, we have $\kappa_{b}\geq L_{i}/\mu_{i}$ and $\kappa_{s}\geq\frac{1}{n}\sum_{j=1}^{n}L_{ij}/\mu_{i}$.

In this case, we allow functions on nodes to have different constants of strong convexity, preserving the constraints on condition numbers. This plays a role in lower bounds, because in the counterexample problem the strong convexity constants on the nodes can differ by a factor of $m$.

###### Theorem 4.3 .

For any $\chi>24$, for any $\kappa_{b}>0$, there exists a constant $\kappa_{s}>0$, a time-varying network $\{\mathcal{G}^{k}\}_{k=1}^{\infty}$ on $m$ nodes, the corresponding sequence of gossip matrices $\{\mathbf{W}(k)\}_{k=1}^{\infty}$ satisfying Assumption 2.5, and functions $\{f_{ij}\}$, such that the problem (1) satisfies Assumptions 2.1, 4.1, 4.2 and for any first-order decentralized algorithm holds

$$ $\frac{1}{nm}\sum_{i=1}^{m}\sum_{j=1}^{n}\frac{\|x_{ij}-x^{*}\|^{2}}{\|x^{0}_{ ij}-x^{*}\|^{2}}\geq\max\left\{T_{1},T_{2}\right\},$ $$

where

$$ $\displaystyle T_{1}$ $\displaystyle=\left(1-\frac{2}{\sqrt{\frac{2}{3}\kappa_{b}+\frac{1}{3}}+1} \right)^{2+16N_{c}/(\chi-24)},$ $\displaystyle T_{2}$ $\displaystyle=\left(1-\frac{2n}{\sqrt{n}\sqrt{\frac{2}{3}\kappa_{s}+n/3}+n} \right)^{4N_{s}/n},$ $$

$N_{c}$ is the number of communication iterations, $N_{s}$ is the maximum number of stochastic oracle calls on any node, and $x_{ij}\in\mathcal{H}_{i}(k)$, $k$ is the number of the last time step.

###### Proof.

The proof may be found in Appendix B.
∎

###### Corollary 4.4 .

For any $\chi>0$ and any $\kappa_{b}>0$, there exists a decentralized problem satisfying Assumptions 2.1, 2.5, 4.1, and 4.2, such that for any first-order decentralized algorithm for each node to reach an $\epsilon$-solution of problem (1), a minimum of $N_{c}$ communication iterations and $N_{s}$ stochastic oracle calls on some node are required, where

$$ $\displaystyle N_{s}$ $\displaystyle=\Omega\left(\left(n+\sqrt{n\kappa_{s}}\right)\log\left(\frac{1}{ \varepsilon}\right)\right),$ $\displaystyle N_{c}$ $\displaystyle=\Omega\left(\chi\sqrt{\kappa_{b}}\log\left(\frac{1}{\varepsilon} \right)\right).$ $$

As we can see, the obtained lower bound has different setting than the class of problems on which the work of Algorithm 1 is analysed, the same problem is present in Li et al., () and Kovalev et al., (). This difficulty appears to arise in a decentralised setup, so the question of how to make the lower bound correct, how to interpret it and what would be the optimal primal algorithm in the case of static and time-varying network remains open. The lower bounds are presented in Table 1.

###### Assumption 4.1 .

###### Assumption 4.2 .

###### Theorem 4.3 .

###### Proof.

###### Corollary 4.4 .

### 4.3 Nonconvex Case

In the nonconvex case, we use the same assumptions that for Algorithm 2.

###### Theorem 4.5 .

For any $L>0$, $m\geq 3$, there exists a set $\{F_{i}\}_{i=1}^{n}$ which satisfy 2.2 and 2.3, and a sequence of matrices $\{\mathbf{W}(k)\}_{k=0}^{\infty}$ which satisfy 2.5, such that for any output $\hat{x}^{N}$ of any first-order decentralized algorithm after $N$ communications and $K$ local computations we get:

$$ $\displaystyle\mathbb{E}\left[\|\nabla F(\hat{x}^{N})\|^{2}\right]$ $\displaystyle=\Omega\left(\frac{\chi L\Delta}{N}\right),$ $\displaystyle\mathbb{E}\left[\|\nabla F(\hat{x}^{N})\|^{2}\right]$ $\displaystyle=\Omega\left(\frac{\sqrt{n}\Delta\hat{L}}{K}\right).$ $$

###### Proof.

See Section C.5.
∎

###### Corollary 4.6 .

In the setting of Theorem 4.5, the number of communication rounds $N_{c}$ and local oracle calls $N_{s}$ required to reach $\epsilon$-accuracy ($\mathbb{E}\left[\|\nabla F(\hat{x}^{N})\|^{2}\right]\leq\epsilon^{2}$) is lower bounded as

$$ $\displaystyle N_{s}$ $\displaystyle=\Omega\left(n+\frac{\sqrt{n}\Delta\hat{L}}{\epsilon^{2}}\right),$ $\displaystyle N_{c}$ $\displaystyle=\Omega\left(\frac{\chi L\Delta}{\epsilon^{2}}\right),$ $$

respectively.

###### Remark 4.7 .

The lower bound for communication rounds $N_{s}$ is obtained the following way. From Theorem 4.5 we get $N_{s}=\Omega(\sqrt{n}\Delta\hat{L}/\varepsilon^{2})$. Additionally, in Li et al., () it was shown that $N_{s}=\Omega(n)$ even for non-distributed optimization. Consequently, we have

$$ $\displaystyle N_{s}=\Omega\left(\max\left(n,\frac{\sqrt{n}\Delta\hat{L}}{ \varepsilon^{2}}\right)\right)=\Omega\left(n+\frac{\sqrt{n}\Delta\hat{L}}{ \varepsilon^{2}}\right).$ $$

The main idea of the proof starts from the example of "bad" nonconvex function (see Arjevani et al., ()). Next, we extend the lower bound for decentralized nonconvex optimization over static graphs (see Yuan et al., ()) by considering time-varying graphs and finite-sum constructions. The lower bounds for nonconvex case are also presented in Table 2.

###### Remark 4.8 .

Since one of the main ideas of the proof of Theorem 4.5 is the selection of a special sequence of time-varying graphs, that is why we get an estimate on the number of communications $\sim\chi$. But, as has been shown in some papers (e.g., Yuan et al., ()), a lower bound on the number of communications for decentralized optimization on static graphs is $\sim\sqrt{\chi}$. Applying the same topology to our proof and taking into account Remark 3.6, we can conclude that GT-PAGE is optimal for the case of static graphs as well.

###### Theorem 4.5 .

###### Proof.

###### Corollary 4.6 .

###### Remark 4.7 .

###### Remark 4.8 .

## 5 Conclusion

This paper establishes lower bounds for stochastic decentralized optimization in both nonconvex and strongly convex scenarios. For the nonconvex case, we derived a lower bound of $\Omega\left(n+\sqrt{n}\hat{L}\Delta/\varepsilon^{2}\right)$ for stochastic oracle calls at a certain node, and $\Omega\left(\chi L\Delta/\varepsilon^{2}\right)$ for communication rounds, while also proposing the optimal GT-PAGE algorithm. In the strongly convex case, the lower bound of $\Omega\left(\left(n+\sqrt{n\kappa_{s}}\right)\log(1/\varepsilon)\right)$ for stochastic oracle calls and $\Omega\left(\chi\sqrt{\kappa_{b}}\log(1/\varepsilon)\right)$ for communication iterations was introduced. The paper also proposes the ADOM+VR algorithm, which optimal in terms of communication iterations. Despite it, the questions of whether existing decentralised VR algorithms are optimal and whether there is a similar lower bound for a narrower class of problems were highlighted. These questions remain open in both time-varying and static scenarios, presenting a way for future research.

## Appendix A Proof of Theorem 3.2

By $\mathrm{D}_{F}(x,y)$ we denote Bregman distance $\mathrm{D}_{F}(x,y)\coloneqq F(x)-F(y)-\langle\nabla F(y),x-y\rangle$.

By $\mathrm{G}_{F}(x,y)$ we denote $\mathrm{G}_{F}(x,y)\coloneqq\mathrm{D}_{F}(x,y)-\frac{\nu}{2}\|x-y\|^{2}$.

###### Lemma A.1 .

$$ $\displaystyle\mathbb{E}_{S^{k}}\left[\|\nabla^{k}-\nabla F(x_{g}^{k})\|^{2}\right]$ $\displaystyle\leq\frac{2\overline{L}}{b}\left(\mathrm{G}_{F}(\omega^{k},x^{*}) -\mathrm{G}_{F}(x_{g}^{k},x^{*})\right)$ (8) $\displaystyle-\frac{2\overline{L}}{b}\langle\nabla F(x_{g}^{k})-\nabla F(x^{*} )-\nu x_{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle.$ $$

###### Proof.

Firstly note, that if $g^{k}=\nabla f_{i}(x^{k}_{g})-\nabla f_{i}(\omega^{k})+\nabla f_{i}(\omega^{k})$, then

$$ $\displaystyle\mathbb{E}_{i}\left[\left\|g^{k}-\nabla f(x^{k}_{g})\right\|^{2}\right]$ $\displaystyle=\mathbb{E}_{i}\left[\left\|\nabla f_{i}(x^{k}_{g})-\nabla f_{i}( w^{k})-\mathbb{E}_{i}\left[\nabla f_{i}(x^{k}_{g})-\nabla f_{i}(w^{k})\right] \right\|^{2}\right]$ (9) $\displaystyle\leq\mathbb{E}_{i}\left[\left\|\nabla f_{i}(x^{k})-\nabla f_{i}(w ^{k})\right\|^{2}\right]$ $\displaystyle\leq 2\overline{L}\left(f(w^{k})-f(x^{k})-\left\langle\nabla f(x^ {k}),w^{k}-x^{k}\right\rangle\right).$ $$

Let us describe the main term

$$ $\displaystyle\mathbb{E}_{S^{k}_{i}}\left[\left\|\left(\nabla^{k}\right)_{i}- \nabla F_{i}(x^{k}_{g,i})\right\|^{2}\right]$ $\displaystyle=\mathbb{E}_{S^{k}_{i}}\left[\left\|\frac{1}{b}\sum_{j\in S^{k}_{ i}}\frac{1}{np_{ij}}\big{[}\nabla f_{ij}(x^{k}_{g,i})-\nabla f_{ij}(\omega^{k} _{i})\big{]}+\nabla F_{i}(\omega^{k}_{i})-\nabla F_{i}(x^{k}_{g,i})\right\|^{2 }\right]$ $\displaystyle\overset{(1)}{=}\frac{1}{b}\mathbb{E}_{j}\left[\left\|\frac{1}{np _{ij}}\big{[}\nabla f_{ij}(x^{k}_{g,i})-\nabla f_{ij}(\omega^{k}_{i})\big{]}+ \nabla F_{i}(\omega^{k}_{i})-\nabla F_{i}(x^{k}_{g,i})\right\|^{2}\right]$ $\displaystyle=\frac{1}{b}\mathbb{E}_{j}\left[\left\|\frac{1}{np_{ij}}\big{[} \left(\nabla f_{ij}(x^{k}_{g,i})-\nabla f_{ij}(x^{*})\right)-\left(\nabla f_{ ij}(\omega^{k}_{i})-\nabla f_{ij}(x^{*})\right)\big{]}+\nabla F_{i}(\omega^{k} _{i})-\nabla F_{i}(x^{k}_{g,i})\right\|^{2}\right]$ $\displaystyle\overset{(2)}{\leq}\frac{1}{b}\mathbb{E}_{j}\left[\left\|\frac{1} {np_{ij}}\big{[}\left(\nabla f_{ij}(x^{k}_{g,i})-\nabla f_{ij}(x^{*})-\nu x^{k }_{g,i}+\nu x^{*}\right)-\left(\nabla f_{ij}(\omega^{k}_{i})-\nabla f_{ij}(x^{ *})-\nu\omega_{i}+\nu x^{*}\right)\big{]}\right\|^{2}\right]$ $\displaystyle\overset{(3)}{\leq}\sum_{j=1}^{n}\frac{p_{ij}}{b}\frac{2L_{ij}}{n ^{2}p_{ij}^{2}}\mathrm{G}_{f_{ij}}(x_{g,i}^{k},x^{*})\overset{(4)}{=}\frac{2 \overline{L}_{i}}{b}\left(\mathrm{G}_{F_{i}}(\omega^{k}_{i},x^{*})-\mathrm{G}_ {F_{i}}(x_{g,i}^{k},x^{*})-\langle\nabla\mathrm{G}_{F_{i}}(x_{g,i}^{k},x^{*}), \omega^{k}_{i}-x_{g,i}^{k}\rangle\right),$ $$

where

- (1)
is due to independency of $(\xi^{1}_{i},\xi^{2}_{i},\ldots,\xi^{b}_{i})$,
- (2)
follows from the inequality $\mathbb{E}\left[\|\xi\|^{2}\right]\leq\mathbb{E}\left[\|\xi+c\|^{2}\right]$ if $\mathbb{E}\left[\xi\right]=0$ and $c$ is constant,
- (3)
follows from (9) inequality,
- (4)
follows from $p_{ij}=L_{ij}/(n\overline{L}_{i})$ definition.

The required inequality is the simple consequence of the previous statement.
∎

Further we will assume that the basis of the expectation is clear from the context.

###### Lemma A.2 .

Let $\tau_{2}$ be defined as follows:

$$ $\tau_{2}=\min\left\{\frac{1}{2},\max\left\{1,\frac{\sqrt{n}}{b}\right\}\sqrt{ \frac{\mu}{L}}\right\}.$ (10) $$

Let $\tau_{1}$ be defined as follows:

$$ $\tau_{1}=(1-\tau_{0})(1/\tau_{2}+1/2)^{-1}.$ (11) $$

Let $\tau_{0}$ be defined as follows:

$$ $\tau_{0}=\frac{\overline{L}}{2Lb}.$ (12) $$

Let $\eta$ be defined as follows:

$$ $\eta=\left(L\left(\tau_{2}+\frac{2\tau_{1}}{1-\tau_{1}}\right)\right)^{-1}.$ (13) $$

Let $\alpha$ be defined as follows:

$$ $\alpha=\mu/2.$ (14) $$

Let $\nu$ be defined as follows:

$$ $\nu=\mu/2.$ (15) $$

Let $\Psi_{x}^{k}$ be defined as follows:

$$ $\Psi_{x}^{k}=\left(\frac{1}{\eta}+\alpha\right)\|x^{k}-x^{*}\|^{2}+\frac{2}{ \tau_{2}}\left(\mathrm{D}_{f}(x_{f}^{k},x^{*})-\frac{\nu}{2}\|x_{f}^{k}-x^{*} \|^{2}\right)$ (16) $$

Then the following inequality holds:

$$ $\begin{split}\Psi_{x}^{k+1}&\leq\left(1-\frac{1}{20}\min\left\{\sqrt{\frac{\mu }{L}},b\sqrt{\frac{\mu}{nL}}\right\}\right)\Psi_{x}^{k}+2\mathbb{E}\left[ \langle y^{k+1}-y^{*},x^{k+1}-x^{*}\rangle\right]\\ &+\frac{\overline{L}}{Lb}\left(\frac{1}{\tau_{1}}-1\right)\left(\mathrm{G}_{F} (\omega^{k},x^{*})-\mathrm{G}_{F}(x_{g}^{k},x^{*})\right)-\mathrm{G}_{F}(x_{g} ^{k},x^{*})-\frac{1}{2}\mathrm{G}_{F}(x_{f}^{k},x^{*})\\ &+\frac{\overline{L}}{Lb}\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x_{g}^ {k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle.\end{split}$ (17) $$

###### Proof.

$$ $\displaystyle\frac{1}{\eta}\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle=\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}+\frac{2}{\eta}\langle x^{k+1}- x^{k},x^{k+1}-x^{*}\rangle-\frac{1}{\eta}\|x^{k+1}-x^{k}\|^{2}.$ $$

Using Line 7 of Algorithm 1 we get

$$ $\displaystyle\frac{1}{\eta}\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle=\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}+2\alpha\langle x_{g}^{k}-x^{k+ 1},x^{k+1}-x^{*}\rangle$ $\displaystyle-2\langle\nabla^{k}-\nu x_{g}^{k}-y^{k+1},x^{k+1}-x^{*}\rangle- \frac{1}{\eta}\|x^{k+1}-x^{k}\|^{2}$ $\displaystyle=\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}+2\alpha\langle x_{g}^{k}-x^{*} -x^{k+1}+x^{*},x^{k+1}-x^{*}\rangle$ $\displaystyle-2\langle\nabla^{k}-\nu\hat{x}_{g}^{k}-y^{k+1},x^{k+1}-x^{*} \rangle-\frac{1}{\eta}\|x^{k+1}-x^{k}\|^{2}$ $\displaystyle\leq\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\|x^{k+1}-x^{*}\|^{2} +\alpha\|x_{g}^{k}-x^{*}\|^{2}-2\langle\nabla^{k}-\nu x_{g}^{k}-y^{k+1},x^{k+1 }-x^{*}\rangle$ $\displaystyle-\frac{1}{\eta}\|x^{k+1}-x^{k}\|^{2}.$ $$

Using optimality condition (3) we get

$$ $\displaystyle\frac{1}{\eta}\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle\leq\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\|x^{k+1}-x^{*}\|^{2} +\alpha\|x_{g}^{k}-x^{*}\|^{2}-\frac{1}{\eta}\|x^{k+1}-x^{k}\|^{2}$ $\displaystyle-2\langle\nabla F(x_{g}^{k})-\nabla F(x^{*}),x^{k+1}-x^{*}\rangle +2\nu\langle x_{g}^{k}-x^{*},x^{k+1}-x^{*}\rangle+2\langle y^{k+1}-y^{*},x^{k+ 1}-x^{*}\rangle$ $\displaystyle-2\langle\nabla^{k}-\nabla F(x_{g}^{k}),x^{k+1}-x^{*}\rangle.$ $$

Using Line 8 of Algorithm 1 we get

$$ $\displaystyle\frac{1}{\eta}\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle\leq\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\|x^{k+1}-x^{*}\|^{2} +\alpha\|x_{g}^{k}-x^{*}\|^{2}-\frac{1}{\eta\tau_{2}^{2}}\|x_{f}^{k+1}-x_{g}^{ k}\|^{2}$ $\displaystyle-2\langle\nabla F(x_{g}^{k})-\nabla F(x^{*}),x^{k}-x^{*}\rangle+2 \nu\langle x_{g}^{k}-x^{*},x^{k}-x^{*}\rangle+2\langle y^{k+1}-y^{*},x^{k+1}-x ^{*}\rangle$ $\displaystyle-\frac{2}{\tau_{2}}\langle\nabla F(x_{g}^{k})-\nabla F(x^{*}),x_{ f}^{k+1}-x_{g}^{k}\rangle+\frac{2\nu}{\tau_{2}}\langle x_{g}^{k}-x^{*},x_{f}^{ k+1}-x_{g}^{k}\rangle$ $\displaystyle-2\langle\nabla^{k}-\nabla F(x_{g}^{k})-\nu(\hat{x}_{g}^{k}-x_{g} ^{k}),x^{k+1}-x^{*}\rangle$ $\displaystyle=\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\|x^{k+1}-x^{*}\|^{2}+ \alpha\|x_{g}^{k}-x^{*}\|^{2}-\frac{1}{\eta\tau_{2}^{2}}\|x_{f}^{k+1}-x_{g}^{k }\|^{2}$ $\displaystyle-2\langle\nabla F(x_{g}^{k})-\nabla F(x^{*}),x^{k}-x^{*}\rangle+2 \nu\langle x_{g}^{k}-x^{*},x^{k}-x^{*}\rangle+2\langle y^{k+1}-y^{*},x^{k+1}-x ^{*}\rangle$ $\displaystyle-\frac{2}{\tau_{2}}\langle\nabla F(x_{g}^{k})-\nabla F(x^{*}),x_{ f}^{k+1}-x_{g}^{k}\rangle+\frac{\nu}{\tau_{2}}\left(\|x_{f}^{k+1}-x^{*}\|^{2}- \|x_{g}^{k}-x^{*}\|^{2}-\|x_{f}^{k+1}-x_{g}^{k}\|^{2}\right)$ $\displaystyle-2\langle\nabla^{k}-\nabla F(x_{g}^{k}),x^{k+1}-x^{*}\rangle.$ $$

Using the $L$-smoothness property of $\mathrm{D}_{F}(x,x^{*})$ with respect to $x$, which is derived from the $L$-smoothness of $F(x)$, we obtain

$$ $\displaystyle\frac{1}{\eta}\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle\leq\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\|x^{k+1}-x^{*}\|^{2} +\alpha\|x_{g}^{k}-x^{*}\|^{2}-\frac{1}{\eta\tau_{2}^{2}}\|x_{f}^{k+1}-x_{g}^{ k}\|^{2}$ $\displaystyle-2\langle\nabla F(x_{g}^{k})-\nabla F(x^{*}),x^{k}-x^{*}\rangle+2 \nu\langle x_{g}^{k}-x^{*},x^{k}-x^{*}\rangle+2\langle y^{k+1}-y^{*},x^{k+1}-x ^{*}\rangle$ $\displaystyle-\frac{2}{\tau_{2}}\langle\nabla F(x_{g}^{k})-\nabla F(x^{*}),x_{ f}^{k+1}-x_{g}^{k}\rangle+\frac{\nu}{\tau_{2}}\left(\|x_{f}^{k+1}-x^{*}\|^{2}- \|x_{g}^{k}-x^{*}\|^{2}-\|x_{f}^{k+1}-x_{g}^{k}\|^{2}\right)$ $\displaystyle-2\langle\nabla^{k}-\nabla F(x_{g}^{k}),x^{k+1}-x^{*}\rangle$ $\displaystyle\leq\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\|x^{k+1}-x^{*}\|^{2} +\alpha\|x_{g}^{k}-x^{*}\|^{2}-\frac{1}{\eta\tau_{2}^{2}}\|x_{f}^{k+1}-x_{g}^{ k}\|^{2}$ $\displaystyle-2\langle\nabla F(x_{g}^{k})-\nabla F(x^{*}),x^{k}-x^{*}\rangle+2 \nu\langle x_{g}^{k}-x^{*},x^{k}-x^{*}\rangle+2\langle y^{k+1}-y^{*},x^{k+1}-x ^{*}\rangle$ $\displaystyle-\frac{2}{\tau_{2}}\left(\mathrm{D}_{f}(x_{f}^{k+1},x^{*})- \mathrm{D}_{f}(x_{g}^{k},x^{*})-\frac{L}{2}\|x_{f}^{k+1}-x_{g}^{k}\|^{2}\right)$ $\displaystyle+\frac{\nu}{\tau_{2}}\left(\|x_{f}^{k+1}-x^{*}\|^{2}-\|x_{g}^{k}- x^{*}\|^{2}-\|x_{f}^{k+1}-x_{g}^{k}\|^{2}\right)-2\langle\nabla^{k}-\nabla F(x _{g}^{k}),x^{k+1}-x^{*}\rangle$ $\displaystyle=\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\|x^{k+1}-x^{*}\|^{2}+ \alpha\|x_{g}^{k}-x^{*}\|^{2}+\left(\frac{L-\nu}{\tau_{2}}-\frac{1}{\eta\tau_{ 2}^{2}}\right)\|x_{f}^{k+1}-x_{g}^{k}\|^{2}$ $\displaystyle-2\langle\nabla F(x_{g}^{k})-\nabla F(x^{*}),x^{k}-x^{*}\rangle+2 \nu\langle x_{g}^{k}-x^{*},x^{k}-x^{*}\rangle+2\langle y^{k+1}-y^{*},x^{k+1}-x ^{*}\rangle$ $\displaystyle-\frac{2}{\tau_{2}}\left(\mathrm{D}_{f}(x_{f}^{k+1},x^{*})- \mathrm{D}_{f}(x_{g}^{k},x^{*})\right)+\frac{\nu}{\tau_{2}}\left(\|x_{f}^{k+1} -x^{*}\|^{2}-\|x_{g}^{k}-x^{*}\|^{2}\right)$ $\displaystyle-2\langle\nabla^{k}-\nabla F(x_{g}^{k}),x^{k+1}-x^{*}\rangle$ $$

Using Line 4 of Algorithm 1 we get

$$ $\displaystyle\frac{1}{\eta}\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle\leq\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\|x^{k+1}-x^{*}\|^{2} +\alpha\|x_{g}^{k}-x^{*}\|^{2}+\left(\frac{L-\nu}{\tau_{2}}-\frac{1}{\eta\tau_ {2}^{2}}\right)\|x_{f}^{k+1}-x_{g}^{k}\|^{2}$ $\displaystyle-2\langle\nabla F(x_{g}^{k})-\nabla F(x^{*}),x_{g}^{k}-x^{*} \rangle+2\nu\|x_{g}^{k}-x^{*}\|^{2}+\frac{2(1-\tau_{1}-\tau_{0})}{\tau_{1}} \langle\nabla F(x_{g}^{k})-\nabla F(x^{*}),x_{f}^{k}-x_{g}^{k}\rangle$ $\displaystyle+\frac{2\tau_{0}}{\tau_{1}}\langle\nabla F(x_{g}^{k})-\nabla F(x^ {*}),\omega^{k}-x_{g}^{k}\rangle+\frac{2\nu(1-\tau_{1}-\tau_{0})}{\tau_{1}} \langle x_{g}^{k}-x_{f}^{k},x_{g}^{k}-x^{*}\rangle+\frac{2\nu\tau_{0}}{\tau_{1 }}\langle x_{g}^{k}-\omega^{k},x_{g}^{k}-x^{*}\rangle$ $\displaystyle+2\langle y^{k+1}-y^{*},x^{k+1}-x^{*}\rangle-\frac{2}{\tau_{2}} \left(\mathrm{D}_{f}(x_{f}^{k+1},x^{*})-\mathrm{D}_{f}(x_{g}^{k},x^{*})\right) +\frac{\nu}{\tau_{2}}\left(\|x_{f}^{k+1}-x^{*}\|^{2}-\|x_{g}^{k}-x^{*}\|^{2}\right)$ $\displaystyle-2\langle\nabla^{k}-\nabla F(x_{g}^{k}),x^{k+1}-x^{*}\rangle$ $\displaystyle=\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\|x^{k+1}-x^{*}\|^{2}+ \alpha\|x_{g}^{k}-x^{*}\|^{2}+\left(\frac{L-\nu}{\tau_{2}}-\frac{1}{\eta\tau_{ 2}^{2}}\right)\|x_{f}^{k+1}-x_{g}^{k}\|^{2}$ $\displaystyle-2\langle\nabla F(x_{g}^{k})-\nabla F(x^{*}),x_{g}^{k}-x^{*} \rangle+2\nu\|x_{g}^{k}-x^{*}\|^{2}+\frac{2(1-\tau_{1}-\tau_{0})}{\tau_{1}} \langle\nabla F(x_{g}^{k})-\nabla F(x^{*}),x_{f}^{k}-x_{g}^{k}\rangle$ $\displaystyle+\frac{2\tau_{0}}{\tau_{1}}\langle\nabla F(x_{g}^{k})-\nabla F(x^ {*}),\omega^{k}-x_{g}^{k}\rangle+\frac{\nu(1-\tau_{1}-\tau_{0})}{\tau_{1}} \left(\|x_{g}^{k}-x_{f}^{k}\|^{2}+\|x_{g}^{k}-x^{*}\|^{2}-\|x_{f}^{k}-x^{*}\|^ {2}\right)$ $\displaystyle+\frac{2\nu\tau_{0}}{\tau_{1}}\langle x_{g}^{k}-\omega^{k},x_{g}^ {k}-x^{*}\rangle+2\langle y^{k+1}-y^{*},x^{k+1}-x^{*}\rangle-\frac{2}{\tau_{2} }\left(\mathrm{D}_{f}(x_{f}^{k+1},x^{*})-\mathrm{D}_{f}(x_{g}^{k},x^{*})\right)$ $\displaystyle+\frac{\nu}{\tau_{2}}\left(\|x_{f}^{k+1}-x^{*}\|^{2}-\|x_{g}^{k}- x^{*}\|^{2}\right)-2\langle\nabla^{k}-\nabla F(x_{g}^{k}),x^{k+1}-x^{*}\rangle.$ $$

By applying $\mu$-strong convexity of $\mathrm{D}_{F}(x,x^{*})$ in $x$, following from $\mu$-strong convexity of $F(x)$, we obtain

$$ $\displaystyle\frac{1}{\eta}\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle\leq\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\|x^{k+1}-x^{*}\|^{2} +\alpha\|x_{g}^{k}-x^{*}\|^{2}+\left(\frac{L-\nu}{\tau_{2}}-\frac{1}{\eta\tau_ {2}^{2}}\right)\|x_{f}^{k+1}-x_{g}^{k}\|^{2}$ $\displaystyle-2\mathrm{D}_{F}(x_{g}^{k},x^{*})-\mu\|x_{g}^{k}-x^{*}\|^{2}+2\nu \|x_{g}^{k}-x^{*}\|^{2}$ $\displaystyle+\frac{2(1-\tau_{1}-\tau_{0})}{\tau_{1}}\left(\mathrm{D}_{F}(x_{f }^{k},x^{*})-\mathrm{D}_{F}(x_{g}^{k},x^{*})-\frac{\mu}{2}\|x_{f}^{k}-x_{g}^{k }\|^{2}\right)+\frac{2\tau_{0}}{\tau_{1}}\langle\nabla F(x_{g}^{k})-\nabla F(x ^{*}),\omega^{k}-x_{g}^{k}\rangle$ $\displaystyle+\frac{\nu(1-\tau_{1}-\tau_{0})}{\tau_{1}}\left(\|x_{g}^{k}-x_{f} ^{k}\|^{2}+\|x_{g}^{k}-x^{*}\|^{2}-\|x_{f}^{k}-x^{*}\|^{2}\right)+\frac{2\nu \tau_{0}}{\tau_{1}}\langle x_{g}^{k}-\omega^{k},x_{g}^{k}-x^{*}\rangle$ $\displaystyle+2\langle y^{k+1}-y^{*},x^{k+1}-x^{*}\rangle-\frac{2}{\tau_{2}} \left(\mathrm{D}_{f}(x_{f}^{k+1},x^{*})-\mathrm{D}_{f}(x_{g}^{k},x^{*})\right)$ $\displaystyle+\frac{\nu}{\tau_{2}}\left(\|x_{f}^{k+1}-x^{*}\|^{2}-\|x_{g}^{k}- x^{*}\|^{2}\right)-2\langle\nabla^{k}-\nabla F(x_{g}^{k}),x^{k+1}-x^{*}\rangle.$ $\displaystyle=\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\|x^{k+1}-x^{*}\|^{2}+ \frac{2(1-\tau_{1}-\tau_{0})}{\tau_{1}}\left(\mathrm{D}_{F}(x_{f}^{k},x^{*})- \frac{\nu}{2}\|x_{f}^{k}-x^{*}\|^{2}\right)$ $\displaystyle-\frac{2}{\tau_{2}}\left(\mathrm{D}_{f}(x_{f}^{k+1},x^{*})-\frac{ \nu}{2}\|x_{f}^{k+1}-x^{*}\|^{2}\right)+2\langle y^{k+1}-y^{*},x^{k+1}-x^{*}\rangle$ $\displaystyle+2\left(\frac{1}{\tau_{2}}-\frac{1-\tau_{0}}{\tau_{1}}\right) \mathrm{D}_{F}(x_{g}^{k},x^{*})+\left(\alpha-\mu+\nu+\frac{(1-\tau_{0})\nu}{ \tau_{1}}-\frac{\nu}{\tau_{2}}\right)\|x_{g}^{k}-x^{*}\|^{2}$ $\displaystyle+\left(\frac{L-\nu}{\tau_{2}}-\frac{1}{\eta\tau_{2}^{2}}\right)\| x_{f}^{k+1}-x_{g}^{k}\|^{2}+\frac{(1-\tau_{1}-\tau_{0})(\nu-\mu)}{\tau_{1}}\|x _{f}^{k}-x_{g}^{k}\|^{2}$ $\displaystyle+\frac{2\tau_{0}}{\tau_{1}}\langle\nabla F(x_{g}^{k})-\nabla F(x^ {*}),\omega^{k}-x_{g}^{k}\rangle+\frac{2\nu\tau_{0}}{\tau_{1}}\langle x_{g}^{k }-\omega^{k},x_{g}^{k}-x^{*}\rangle$ $\displaystyle-2\langle\nabla^{k}-\nabla F(x_{g}^{k}),x^{k+1}-x^{*}\rangle.$ $$

Utilizing $\eta$ as defined in (13), $\tau_{1}$ as defined in (11), and considering that $\nu<\mu$, we derive

$$ $\displaystyle\frac{1}{\eta}\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle\leq\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\|x^{k+1}-x^{*}\|^{2} +\frac{2(1-\tau_{2}/2)}{\tau_{2}}\mathrm{G}_{F}(x_{f}^{k},x^{*})$ $\displaystyle-\frac{2}{\tau_{2}}\mathrm{G}_{F}(x_{f}^{k+1},x^{*})+2\langle y^{ k+1}-y^{*},x^{k+1}-x^{*}\rangle$ $\displaystyle-\mathrm{D}_{F}(x_{g}^{k},x^{*})+\left(\alpha-\mu+\frac{3\nu}{2} \right)\|x_{g}^{k}-x^{*}\|^{2}-\frac{2L\tau_{1}}{\tau_{2}^{2}(1-\tau_{1})}\|x_ {f}^{k+1}-x_{g}^{k}\|^{2}$ $\displaystyle+\frac{2\tau_{0}}{\tau_{1}}\langle\left(\nabla F(x_{g}^{k})-\nu x _{g}^{k}\right)-\left(\nabla F(x^{*})-\nu x^{*}\right),\omega^{k}-x_{g}^{k}\rangle$ $\displaystyle-2\langle\nabla^{k}-\nabla F(x_{g}^{k}),x^{k+1}-x^{*}\rangle.$ $$

Using $\alpha$ defined by (14) and $\nu$ defined by (15) we get

$$ $\displaystyle\frac{1}{\eta}\|x^{k+1}-x^{*}\|^{2}$ $\displaystyle\leq\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\|x^{k+1}-x^{*}\|^{2} +\frac{2(1-\tau_{2}/2)}{\tau_{2}}\mathrm{G}_{F}(x_{f}^{k},x^{*})$ $\displaystyle-\frac{2}{\tau_{2}}\mathrm{G}_{F}(x_{f}^{k+1},x^{*})+2\langle y^{ k+1}-y^{*},x^{k+1}-x^{*}\rangle$ $\displaystyle-\left(\mathrm{D}_{F}(x_{g}^{k},x^{*})-\frac{\nu}{2}\|x_{g}^{k}-x ^{*}\|^{2}\right)-\frac{2L\tau_{1}}{\tau_{2}^{2}(1-\tau_{1})}\|x_{f}^{k+1}-x_{ g}^{k}\|^{2}$ $\displaystyle+\frac{2\tau_{0}}{\tau_{1}}\langle\left(\nabla F(x_{g}^{k})-\nu x _{g}^{k}\right)-\left(\nabla F(x^{*})-\nu x^{*}\right),\omega^{k}-x_{g}^{k}\rangle$ $\displaystyle-2\langle\nabla^{k}-\nabla F(x_{g}^{k}),x^{k+1}-x^{*}\rangle.$ $$

Taking the expectation over $i$ at the $k$th step, using that $x^{k}-x^{*}$ is independent of $i$ and that $\mathbb{E}\left[\nabla^{k}-\nabla F(x_{g}^{k})\right]=0$ we get

$$ $\displaystyle\frac{1}{\eta}\mathbb{E}\left[\|x^{k+1}-x^{*}\|^{2}\right]$ $\displaystyle\leq\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\mathbb{E}\left[\|x^{ k+1}-x^{*}\|^{2}\right]+\frac{2(1-\tau_{2}/2)}{\tau_{2}}\mathrm{G}_{F}(x_{f}^{ k},x^{*})$ $\displaystyle-\frac{2}{\tau_{2}}\mathbb{E}\left[\mathrm{G}_{F}(x_{f}^{k+1},x^{ *})\right]+2\mathbb{E}\left[\langle y^{k+1}-y^{*},x^{k+1}-x^{*}\rangle\right]$ $\displaystyle-\mathrm{G}_{F}(x_{g}^{k},x^{*})-\frac{2L\tau_{1}}{\tau_{2}^{2}(1 -\tau_{1})}\mathbb{E}\left[\|x_{f}^{k+1}-x_{g}^{k}\|^{2}\right]$ $\displaystyle+\frac{2\tau_{0}}{\tau_{1}}\langle\left(\nabla F(x_{g}^{k})-\nu x _{g}^{k}\right)-\left(\nabla F(x^{*})-\nu x^{*}\right),\omega^{k}-x_{g}^{k}\rangle$ $\displaystyle-2\mathbb{E}\left[\langle\nabla^{k}-\nabla F(x_{g}^{k}),x^{k+1}-x ^{k}\rangle\right].$ $$

Using Line 8 of Algorithm 1 and the Cauchy–Schwarz inequality for $\langle\nabla^{k}-\nabla F(x_{g}^{k}),x_{f}^{k+1}-x_{g}^{k}\rangle$ we get

$$ $\displaystyle\frac{1}{\eta}\mathbb{E}\left[\|x^{k+1}-x^{*}\|^{2}\right]$ $\displaystyle\leq\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\mathbb{E}\left[\|x^{ k+1}-x^{*}\|^{2}\right]+\frac{2(1-\tau_{2}/2)}{\tau_{2}}\mathrm{G}_{F}(x_{f}^{ k},x^{*})$ $\displaystyle-\frac{2}{\tau_{2}}\mathbb{E}\left[\mathrm{G}_{F}(x_{f}^{k+1},x^{ *})\right]+2\mathbb{E}\left[\langle y^{k+1}-y^{*},x^{k+1}-x^{*}\rangle\right]$ $\displaystyle-\mathrm{G}_{F}(x_{g}^{k},x^{*})+\frac{1-\tau_{1}}{2L\tau_{1}} \mathbb{E}\left[\|\nabla^{k}-\nabla F(x_{g}^{k})\|^{2}\right]$ $\displaystyle+\frac{2\tau_{0}}{\tau_{1}}\langle\left(\nabla F(x_{g}^{k})-\nu x _{g}^{k}\right)-\left(\nabla F(x^{*})-\nu x^{*}\right),\omega^{k}-x_{g}^{k}\rangle.$ $$

Using lemma A.1 and $\tau_{0}$ definition (12) we get

$$ $\displaystyle\frac{1}{\eta}\mathbb{E}\left[\|x^{k+1}-x^{*}\|^{2}\right]$ $\displaystyle\leq\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\mathbb{E}\left[\|x^{ k+1}-x^{*}\|^{2}\right]+\frac{2(1-\tau_{2}/2)}{\tau_{2}}\mathrm{G}_{F}(x_{f}^{ k},x^{*})$ $\displaystyle-\frac{2}{\tau_{2}}\mathbb{E}\left[\mathrm{G}_{F}(x_{f}^{k+1},x^{ *})\right]+2\mathbb{E}\left[\langle y^{k+1}-y^{*},x^{k+1}-x^{*}\rangle\right]- \mathrm{G}_{F}(x_{g}^{k},x^{*})$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\frac{1}{\tau_{1}}-1\right)\left( \mathrm{G}_{F}(\omega^{k},x^{*})-\mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F (x_{g}^{k})-\nabla F(x^{*})-\nu x_{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k} \rangle\right)$ $\displaystyle+\frac{2\tau_{0}}{\tau_{1}}\langle\left(\nabla F(x_{g}^{k})-\nu x _{g}^{k}\right)-\left(\nabla F(x^{*})-\nu x^{*}\right),\omega^{k}-x_{g}^{k}\rangle$ $\displaystyle=\frac{1}{\eta}\|x^{k}-x^{*}\|^{2}-\alpha\mathbb{E}\left[\|x^{k+1 }-x^{*}\|^{2}\right]+\frac{2(1-\tau_{2}/2)}{\tau_{2}}\mathrm{G}_{F}(x_{f}^{k}, x^{*})-\frac{2}{\tau_{2}}\mathbb{E}\left[\mathrm{G}_{F}(x_{f}^{k+1},x^{*})\right]$ $\displaystyle+2\mathbb{E}\left[\langle y^{k+1}-y^{*},x^{k+1}-x^{*}\rangle \right]+\frac{\overline{L}}{Lb}\left(\frac{1}{\tau_{1}}-1\right)\left(\mathrm{ G}_{F}(\omega^{k},x^{*})-\mathrm{G}_{F}(x_{g}^{k},x^{*})\right)-\mathrm{G}_{F} (x_{g}^{k},x^{*})$ $\displaystyle+\frac{\overline{L}}{Lb}\langle\nabla F(x_{g}^{k})-\nabla F(x^{*} )-\nu x_{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle.$ $$

After rearranging and using $\Psi_{x}^{k}$ definition (16) we get

$$ $\displaystyle\mathbb{E}\left[\Psi_{x}^{k+1}\right]$ $\displaystyle\leq\max\left\{1-\tau_{2}/4,1/(1+\eta\alpha)\right\}\Psi_{x}^{k}+ 2\mathbb{E}\left[\langle y^{k+1}-y^{*},x^{k+1}-x^{*}\rangle\right]$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\frac{1}{\tau_{1}}-1\right)\left( \mathrm{G}_{F}(\omega^{k},x^{*})-\mathrm{G}_{F}(x_{g}^{k},x^{*})\right)- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\frac{1}{2}\mathrm{G}_{F}(x_{f}^{k},x^{*})$ $\displaystyle+\frac{\overline{L}}{Lb}\langle\nabla F(x_{g}^{k})-\nabla F(x^{*} )-\nu x_{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle$ $\displaystyle\leq\left(1-\frac{1}{20}\min\left\{\sqrt{\frac{\mu}{L}},b\sqrt{ \frac{\mu}{nL}}\right\}\right)\Psi_{x}^{k}+2\mathbb{E}\left[\langle y^{k+1}-y^ {*},x^{k+1}-x^{*}\rangle\right]$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\frac{1}{\tau_{1}}-1\right)\left( \mathrm{G}_{F}(\omega^{k},x^{*})-\mathrm{G}_{F}(x_{g}^{k},x^{*})\right)- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\frac{1}{2}\mathrm{G}_{F}(x_{f}^{k},x^{*})$ $\displaystyle+\frac{\overline{L}}{Lb}\langle\nabla F(x_{g}^{k})-\nabla F(x^{*} )-\nu x_{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle.$ $$

The last inequality follows from $\eta$, $\alpha$, $\tau_{0}$, $\tau_{1}$, $\tau_{2}$ definitions (13), (14), (12), (11) and (10). Estimating the second term:

$$ $\displaystyle\frac{1}{1+\eta\alpha}$ $\displaystyle\leq 1-\frac{\eta\alpha}{2}\leq 1-\frac{\mu}{4}\left(L\left(\tau_ {2}+\frac{2\tau_{1}}{1-\tau_{1}}\right)\right)^{-1}\leq 1-\frac{\mu}{4}\left(L \left(\tau_{2}+\frac{2\tau_{2}}{1-\tau_{2}}\right)\right)^{-1}$ $\displaystyle\leq 1-\frac{\mu}{4}\left(L\left(\tau_{2}+4\tau_{2}\right)\right) ^{-1}=1-\frac{\mu}{20L\tau_{2}}\leq 1-\frac{1}{20\max\left\{1,\frac{\sqrt{n}}{ b}\right\}}\sqrt{\frac{\mu}{L}}\leq 1-\frac{1}{20}\min\left\{\sqrt{\frac{\mu}{ L}},b\sqrt{\frac{\mu}{nL}}\right\}.$ $$

Estimating the first term:

$$ $\displaystyle 1-\tau_{2}/4\leq 1-\min\left\{\frac{1}{8},\frac{1}{4}\sqrt{\frac {\mu}{L}}\right\}.$ $$

∎

###### Lemma A.3 .

The following inequality holds:

$$ $\begin{split}-\|y^{k+1}-y^{*}\|^{2}&\leq\frac{(1-\sigma_{1})}{\sigma_{1}}\|y_{ f}^{k}-y^{*}\|^{2}-\frac{1}{\sigma_{2}}\|y_{f}^{k+1}-y^{*}\|^{2}\\ &-\left(\frac{1}{\sigma_{1}}-\frac{1}{\sigma_{2}}\right)\|y_{g}^{k}-y^{*}\|^{2 }+\left(\sigma_{2}-\sigma_{1}\right)\|y^{k+1}-y^{k}\|^{2}.\end{split}$ (18) $$

###### Proof.

Lines 10 and 12 of Algorithm 1 imply

$$ $\displaystyle y_{f}^{k+1}$ $\displaystyle=y_{g}^{k}+\sigma_{2}(y^{k+1}-y^{k})$ $\displaystyle=y_{g}^{k}+\sigma_{2}y^{k+1}-\frac{\sigma_{2}}{\sigma_{1}}\left(y _{g}^{k}-(1-\sigma_{1})y_{f}^{k}\right)$ $\displaystyle=\left(1-\frac{\sigma_{2}}{\sigma_{1}}\right)y_{g}^{k}+\sigma_{2} y^{k+1}+\left(\frac{\sigma_{2}}{\sigma_{1}}-\sigma_{2}\right)y_{f}^{k}.$ $$

After subtracting $y^{*}$ and rearranging we get

$$ $\displaystyle(y_{f}^{k+1}-y^{*})+\left(\frac{\sigma_{2}}{\sigma_{1}}-1\right)( y_{g}^{k}-y^{*})=\sigma_{2}(y^{k+1}-y^{*})+\left(\frac{\sigma_{2}}{\sigma_{1}} -\sigma_{2}\right)(y_{f}^{k}-y^{*}).$ $$

Multiplying both sides by $\frac{\sigma_{1}}{\sigma_{2}}$ gives

$$ $\displaystyle\frac{\sigma_{1}}{\sigma_{2}}(y_{f}^{k+1}-y^{*})+\left(1-\frac{ \sigma_{1}}{\sigma_{2}}\right)(y_{g}^{k}-y^{*})=\sigma_{1}(y^{k+1}-y^{*})+ \left(1-\sigma_{1}\right)(y_{f}^{k}-y^{*}).$ $$

Squaring both sides gives

$$ $\displaystyle\frac{\sigma_{1}}{\sigma_{2}}\|y_{f}^{k+1}-y^{*}\|^{2}+\left(1- \frac{\sigma_{1}}{\sigma_{2}}\right)\|y_{g}^{k}-y^{*}\|^{2}-\frac{\sigma_{1}}{ \sigma_{2}}\left(1-\frac{\sigma_{1}}{\sigma_{2}}\right)\|y_{f}^{k+1}-y_{g}^{k} \|^{2}\leq\sigma_{1}\|y^{k+1}-y^{*}\|^{2}+(1-\sigma_{1})\|y_{f}^{k}-y^{*}\|^{2}.$ $$

Rearranging gives

$$ $\displaystyle-\|y^{k+1}-y^{*}\|^{2}\leq-\left(\frac{1}{\sigma_{1}}-\frac{1}{ \sigma_{2}}\right)\|y_{g}^{k}-y^{*}\|^{2}+\frac{(1-\sigma_{1})}{\sigma_{1}}\|y _{f}^{k}-y^{*}\|^{2}-\frac{1}{\sigma_{2}}\|y_{f}^{k+1}-y^{*}\|^{2}+\frac{1}{ \sigma_{2}}\left(1-\frac{\sigma_{1}}{\sigma_{2}}\right)\|y_{f}^{k+1}-y_{g}^{k} \|^{2}.$ $$

Using Line 12 of Algorithm 1 we get

$$ $\displaystyle-\|y^{k+1}-y^{*}\|^{2}\leq-\left(\frac{1}{\sigma_{1}}-\frac{1}{ \sigma_{2}}\right)\|y_{g}^{k}-y^{*}\|^{2}+\frac{(1-\sigma_{1})}{\sigma_{1}}\|y _{f}^{k}-y^{*}\|^{2}-\frac{1}{\sigma_{2}}\|y_{f}^{k+1}-y^{*}\|^{2}+\left( \sigma_{2}-\sigma_{1}\right)\|y^{k+1}-y^{k}\|^{2}.$ $$

∎

###### Lemma A.4 .

Let $\beta$ be defined as follows:

$$ $\beta=1/(2L).$ (19) $$

Let $\sigma_{1}$ be defined as follows:

$$ $\sigma_{1}=(1/\sigma_{2}+1/2)^{-1}.$ (20) $$

Then the following inequality holds:

$$ $\begin{split}&\left(\frac{1}{\theta}+\frac{\beta}{2}\right)\mathbb{E}\left[\|y ^{k+1}-y^{*}\|^{2}\right]+\frac{\beta}{2\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+ 1}-y^{*}\|^{2}\right]\\ &\leq\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+\frac{\beta(1-\sigma_{2}/2)}{2\sigma_ {2}}\|y_{f}^{k}-y^{*}\|^{2}-2\mathbb{E}\left[\langle x^{k+1}-x^{*},y^{k+1}-y^{ *}\rangle\right]+\mathrm{G}_{F}(x_{g}^{k},x^{*})\\ &-2\nu^{-1}\mathbb{E}\left[\langle y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*}),y^{k+1}-y ^{*}\rangle\right]-\frac{\beta}{4}\|y_{g}^{k}-y^{*}\|^{2}+\left(\frac{\beta \sigma_{2}^{2}}{4}-\frac{1}{\theta}\right)\mathbb{E}\left[\|y^{k+1}-y^{k}\|^{2 }\right]\\ &+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})-\mathrm{G}_{F} (x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x_{g}^{k}+\nu x ^{*},\omega^{k}-x_{g}^{k}\rangle\right).\end{split}$ (21) $$

###### Proof.

$$ $\displaystyle\frac{1}{\theta}\|y^{k+1}-y^{*}\|^{2}$ $\displaystyle=\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+\frac{2}{\theta}\langle x^{k +1}-x^{k},x^{k+1}-x^{*}\rangle-\frac{1}{\theta}\|y^{k+1}-y^{k}\|^{2}.$ $$

Using Line 11 of Algorithm 1 we get

$$ $\displaystyle\frac{1}{\theta}\|y^{k+1}-y^{*}\|^{2}$ $\displaystyle=\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+2\beta\langle\nabla^{k}-\nu x _{g}^{k}-y^{k+1},y^{k+1}-y^{*}\rangle$ $\displaystyle-2\langle\nu^{-1}(y_{g}^{k}+z_{g}^{k})+x^{k+1},y^{k+1}-y^{*} \rangle-\frac{1}{\theta}\|y^{k+1}-y^{k}\|^{2}.$ $$

Using optimality condition (3) we get

$$ $\displaystyle\frac{1}{\theta}\|y^{k+1}-y^{*}\|^{2}$ $\displaystyle=\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+2\beta\langle\nabla^{k}-\nu x _{g}^{k}-(\nabla F(x^{*})-\nu x^{*})+y^{*}-y^{k+1},y^{k+1}-y^{*}\rangle$ $\displaystyle-2\langle\nu^{-1}(y_{g}^{k}+z_{g}^{k})+x^{k+1},y^{k+1}-y^{*} \rangle-\frac{1}{\theta}\|y^{k+1}-y^{k}\|^{2}$ $\displaystyle=\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+2\beta\langle\nabla^{k}-\nu x _{g}^{k}-(\nabla F(x^{*})-\nu x^{*}),y^{k+1}-y^{*}\rangle-2\beta\|y^{k+1}-y^{* }\|^{2}$ $\displaystyle-2\langle\nu^{-1}(y_{g}^{k}+z_{g}^{k})+x^{k+1},y^{k+1}-y^{*} \rangle-\frac{1}{\theta}\|y^{k+1}-y^{k}\|^{2}$ $\displaystyle\leq\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+\beta\|\nabla^{k}-\nu x_{ g}^{k}-(\nabla F(x^{*})-\nu x^{*})\|^{2}-\beta\|y^{k+1}-y^{*}\|^{2}$ $\displaystyle-2\langle\nu^{-1}(y_{g}^{k}+z_{g}^{k})+x^{k+1},y^{k+1}-y^{*} \rangle-\frac{1}{\theta}\|y^{k+1}-y^{k}\|^{2}.$ $$

Taking expectation over $i$ and using the property $\mathbb{E}\left[\|\xi\|^{2}\right]=\mathbb{E}\left[\|\xi-\mathbb{E}\left[\xi
\right]\|^{2}\right]+\|\mathbb{E}\left[\xi\right]\|^{2}$ we get

$$ $\displaystyle\frac{1}{\theta}\mathbb{E}\left[\|y^{k+1}-y^{*}\|^{2}\right]$ $\displaystyle\leq\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+\beta\|\nabla F(x_{g}^{k} )-\nu x_{g}^{k}-(\nabla F(x^{*})-\nu x^{*})\|^{2}-\beta\|y^{k+1}-y^{*}\|^{2}$ $\displaystyle-2\langle\nu^{-1}(y_{g}^{k}+z_{g}^{k})+x^{k+1},y^{k+1}-y^{*} \rangle-\frac{1}{\theta}\|y^{k+1}-y^{k}\|^{2}+\beta\mathbb{E}\left[\|\nabla^{k }-\nabla F(x_{g}^{k})\|^{2}\right].$ $$

Function $F(x)-\frac{\nu}{2}\|x\|^{2}$ is convex and $L$-smooth, together with (A.1) it implies

$$ $\displaystyle\frac{1}{\theta}\|y^{k+1}-y^{*}\|^{2}$ $\displaystyle\leq\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+2\beta L\left(\mathrm{D}_ {F}(x_{g}^{k},x^{*})-\frac{\nu}{2}\|x_{g}^{k}-x^{*}\|^{2}\right)-\beta\mathbb{ E}\left[\|y^{k+1}-y^{*}\|^{2}\right]$ $\displaystyle-2\mathbb{E}\left[\langle\nu^{-1}(y_{g}^{k}+z_{g}^{k})+x^{k+1},y^ {k+1}-y^{*}\rangle\right]-\frac{1}{\theta}\mathbb{E}\left[\|y^{k+1}-y^{k}\|^{2 }\right]$ $\displaystyle+\frac{2\overline{L}\beta}{b}\left(\mathrm{G}_{F}(\omega^{k},x^{* })-\mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})- \nu x_{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right).$ $$

Using $\beta$ definition (19) we get

$$ $\displaystyle\frac{1}{\theta}\mathbb{E}\left[\|y^{k+1}-y^{*}\|^{2}\right]$ $\displaystyle\leq\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+\mathrm{G}_{F}(x_{g}^{k}, x^{*})-\beta\mathbb{E}\left[\|y^{k+1}-y^{*}\|^{2}\right]$ $\displaystyle-2\mathbb{E}\left[\langle\nu^{-1}(y_{g}^{k}+z_{g}^{k})+x^{k+1},y^ {k+1}-y^{*}\rangle\right]-\frac{1}{\theta}\mathbb{E}\left[\|y^{k+1}-y^{k}\|^{2 }\right]$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x _{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right).$ $$

Using optimality condition (4) we get

$$ $\displaystyle\frac{1}{\theta}\mathbb{E}\left[\|y^{k+1}-y^{*}\|^{2}\right]$ $\displaystyle\leq\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}-\beta\mathbb{E}\left[\|y^ {k+1}-y^{*}\|^{2}\right]-2\nu^{-1}\mathbb{E}\left[\langle y_{g}^{k}+z_{g}^{k}- (y^{*}+z^{*}),y^{k+1}-y^{*}\rangle\right]$ $\displaystyle-2\mathbb{E}\left[\langle x^{k+1}-x^{*},y^{k+1}-y^{*}\rangle \right]-\frac{1}{\theta}\mathbb{E}\left[\|y^{k+1}-y^{k}\|^{2}\right]+\mathrm{G }_{F}(x_{g}^{k},x^{*})$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x _{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right).$ $$

Using (18) together with $\sigma_{1}$ definition (20) we get

$$ $\displaystyle\frac{1}{\theta}\mathbb{E}\left[\|y^{k+1}-y^{*}\|^{2}\right]$ $\displaystyle\leq\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}-\frac{\beta}{2}\mathbb{E} \left[\|y^{k+1}-y^{*}\|^{2}\right]+\frac{\beta(1-\sigma_{2}/2)}{2\sigma_{2}}\| y_{f}^{k}-y^{*}\|^{2}$ $\displaystyle-\frac{\beta}{2\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1}-y^{*}\|^{ 2}\right]-\frac{\beta}{4}\|y_{g}^{k}-y^{*}\|^{2}+\frac{\beta\left(\sigma_{2}- \sigma_{1}\right)}{2}\mathbb{E}\left[\|y^{k+1}-y^{k}\|^{2}\right]+\mathrm{G}_{ F}(x_{g}^{k},x^{*})$ $\displaystyle-2\nu^{-1}\mathbb{E}\left[\langle y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{* }),y^{k+1}-y^{*}\rangle\right]-2\mathbb{E}\left[\langle x^{k+1}-x^{*},y^{k+1}- y^{*}\rangle\right]-\frac{1}{\theta}\mathbb{E}\left[\|y^{k+1}-y^{k}\|^{2}\right]$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x _{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right).$ $\displaystyle\leq\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}-\frac{\beta}{2}\mathbb{E} \left[\|y^{k+1}-y^{*}\|^{2}\right]+\frac{\beta(1-\sigma_{2}/2)}{2\sigma_{2}}\| y_{f}^{k}-y^{*}\|^{2}$ $\displaystyle-\frac{\beta}{2\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1}-y^{*}\|^{ 2}\right]-\frac{\beta}{4}\|y_{g}^{k}-y^{*}\|^{2}+\left(\frac{\beta\sigma_{2}^{ 2}}{4}-\frac{1}{\theta}\right)\mathbb{E}\left[\|y^{k+1}-y^{k}\|^{2}\right]+ \mathrm{G}_{F}(x_{g}^{k},x^{*})$ $\displaystyle-2\nu^{-1}\mathbb{E}\left[\langle y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{* }),y^{k+1}-y^{*}\rangle\right]-2\mathbb{E}\left[\langle x^{k+1}-x^{*},y^{k+1}- y^{*}\rangle\right]$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x _{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right).$ $$

Rearranging gives

$$ $\displaystyle\left(\frac{1}{\theta}+\frac{\beta}{2}\right)\mathbb{E}\left[\|y^ {k+1}-y^{*}\|^{2}\right]+\frac{\beta}{2\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1 }-y^{*}\|^{2}\right]$ $\displaystyle\leq\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+\frac{\beta(1-\sigma_{2}/ 2)}{2\sigma_{2}}\|y_{f}^{k}-y^{*}\|^{2}-2\mathbb{E}\left[\langle x^{k+1}-x^{*} ,y^{k+1}-y^{*}\rangle\right]+\mathrm{G}_{F}(x_{g}^{k},x^{*})$ $\displaystyle-2\nu^{-1}\mathbb{E}\left[\langle y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{* }),y^{k+1}-y^{*}\rangle\right]-\frac{\beta}{4}\|y_{g}^{k}-y^{*}\|^{2}+\left( \frac{\beta\sigma_{2}^{2}}{4}-\frac{1}{\theta}\right)\mathbb{E}\left[\|y^{k+1} -y^{k}\|^{2}\right]$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x _{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right).$ $$

∎

###### Lemma A.5 .

The following inequality holds:

$$ $\|m^{k}\|^{2}_{\mathbf{P}}\leq 8\chi^{2}\gamma^{2}\nu^{-2}\|y_{g}^{k}+z_{g}^{k }\|^{2}_{\mathbf{P}}+4\chi(1-(4\chi)^{-1})\|m^{k}\|^{2}_{\mathbf{P}}-4\chi\|m^ {k+1}\|^{2}_{\mathbf{P}}.$ (22) $$

###### Proof.

Using Line 15 of Algorithm 1 we get

$$ $\displaystyle\|m^{k+1}\|^{2}_{\mathbf{P}}$ $\displaystyle=\|\gamma\nu^{-1}(y_{g}^{k}+z_{g}^{k})+m^{k}-(\mathbf{W}(k) \otimes\mathbf{I}_{d})\left[\gamma\nu^{-1}(y_{g}^{k}+z_{g}^{k})+m^{k}\right]\| ^{2}_{\mathbf{P}}$ $\displaystyle=\|\mathbf{P}\left[\gamma\nu^{-1}(y_{g}^{k}+z_{g}^{k})+m^{k} \right]-(\mathbf{W}(k)\otimes\mathbf{I}_{d})\mathbf{P}\left[\gamma\nu^{-1}(y_{ g}^{k}+z_{g}^{k})+m^{k}\right]\|^{2}.$ $$

Using property (2) we obtain

$$ $\displaystyle\|m^{k+1}\|^{2}_{\mathbf{P}}$ $\displaystyle\leq(1-\chi^{-1})\|m^{k}+\gamma\nu^{-1}(y_{g}^{k}+z_{g}^{k})\|^{2 }_{\mathbf{P}}.$ $$

Using inequality $\|a+b\|^{2}\leq(1+c)\|a\|^{2}+(1+c^{-1})\|b\|^{2}$ with $c=\frac{1}{2(\chi-1)}$ we get

$$ $\displaystyle\|m^{k+1}\|^{2}_{\mathbf{P}}$ $\displaystyle\leq(1-\chi^{-1})\left[\left(1+\frac{1}{2(\chi-1)}\right)\|m^{k} \|^{2}_{\mathbf{P}}+\left(1+2(\chi-1)\right)\gamma^{2}\nu^{-2}\|y_{g}^{k}+z_{g }^{k}\|^{2}_{\mathbf{P}}\right]$ $\displaystyle\leq(1-(2\chi)^{-1})\|m^{k}\|^{2}_{\mathbf{P}}+2\chi\gamma^{2}\nu ^{-2}\|y_{g}^{k}+z_{g}^{k}\|^{2}_{\mathbf{P}}.$ $$

Rearranging gives

$$ $\displaystyle\|m^{k}\|^{2}_{\mathbf{P}}$ $\displaystyle\leq 8\chi^{2}\gamma^{2}\nu^{-2}\|y_{g}^{k}+z_{g}^{k}\|^{2}_{ \mathbf{P}}+4\chi(1-(4\chi)^{-1})\|m^{k}\|^{2}_{\mathbf{P}}-4\chi\|m^{k+1}\|^{ 2}_{\mathbf{P}}.$ $$

∎

###### Lemma A.6 .

Let $\hat{z}^{k}$ be defined as follows:

$$ $\hat{z}^{k}=z^{k}-\mathbf{P}m^{k}.$ (23) $$

Then the following inequality holds:

$$ $\begin{split}&\frac{1}{\gamma}\|\hat{z}^{k+1}-z^{*}\|^{2}+\frac{4}{3\gamma}\|m ^{k+1}\|^{2}_{\mathbf{P}}\leq\left(\frac{1}{\gamma}-\delta\right)\|\hat{z}^{k} -z^{*}\|^{2}+\left(1-(4\chi)^{-1}+\frac{3\gamma\delta}{2}\right)\frac{4}{3 \gamma}\|m^{k}\|^{2}_{\mathbf{P}}\\ &-2\nu^{-1}\langle y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*}),z^{k}-z^{*}\rangle+\gamma \nu^{-2}\left(1+6\chi\right)\|y_{g}^{k}+z_{g}^{k}\|^{2}_{\mathbf{P}}\\ &+2\delta\|z_{g}^{k}-z^{*}\|^{2}+\left(2\gamma\delta^{2}-\delta\right)\|z_{g}^ {k}-z^{k}\|^{2}.\end{split}$ (24) $$

###### Proof.

$$ $\displaystyle\frac{1}{\gamma}\|\hat{z}^{k+1}-z^{*}\|^{2}$ $\displaystyle=\frac{1}{\gamma}\|\hat{z}^{k}-z^{*}\|^{2}+\frac{2}{\gamma} \langle\hat{z}^{k+1}-\hat{z}^{k},\hat{z}^{k}-z^{*}\rangle+\frac{1}{\gamma}\| \hat{z}^{k+1}-\hat{z}^{k}\|^{2}.$ $$

The combination of Lines 14 and 15 in Algorithm 1, coupled with the definition of $\hat{z}^{k}$ in (23), imply

$$ $\hat{z}^{k+1}-\hat{z}^{k}=\gamma\delta(z_{g}^{k}-z^{k})-\gamma\nu^{-1}\mathbf{ P}(y_{g}^{k}+z_{g}^{k}).$ $$

Hence,

$$ $\displaystyle\frac{1}{\gamma}\|\hat{z}^{k+1}-z^{*}\|^{2}$ $\displaystyle=\frac{1}{\gamma}\|\hat{z}^{k}-z^{*}\|^{2}+2\delta\langle z_{g}^{ k}-z^{k},\hat{z}^{k}-z^{*}\rangle-2\nu^{-1}\langle\mathbf{P}(y_{g}^{k}+z_{g}^{ k}),\hat{z}^{k}-z^{*}\rangle+\frac{1}{\gamma}\|\hat{z}^{k+1}-\hat{z}^{k}\|^{2}$ $\displaystyle=\frac{1}{\gamma}\|\hat{z}^{k}-z^{*}\|^{2}+\delta\|z_{g}^{k}- \mathbf{P}m^{k}-z^{*}\|^{2}-\delta\|\hat{z}^{k}-z^{*}\|^{2}-\delta\|z_{g}^{k}- z^{k}\|^{2}$ $\displaystyle-2\nu^{-1}\langle\mathbf{P}(y_{g}^{k}+z_{g}^{k}),\hat{z}^{k}-z^{* }\rangle+\gamma\|\delta(z_{g}^{k}-z^{k})-\nu^{-1}\mathbf{P}(y_{g}^{k}+z_{g}^{k })\|^{2}$ $\displaystyle\leq\left(\frac{1}{\gamma}-\delta\right)\|\hat{z}^{k}-z^{*}\|^{2} +2\delta\|z_{g}^{k}-z^{*}\|^{2}+2\delta\|m^{k}\|^{2}_{\mathbf{P}}-\delta\|z_{g }^{k}-z^{k}\|^{2}$ $\displaystyle-2\nu^{-1}\langle\mathbf{P}(y_{g}^{k}+z_{g}^{k}),\hat{z}^{k}-z^{* }\rangle+2\gamma\delta^{2}\|z_{g}^{k}-z^{k}\|^{2}+\gamma\|\nu^{-1}\mathbf{P}(y _{g}^{k}+z_{g}^{k})\|^{2}$ $\displaystyle\leq\left(\frac{1}{\gamma}-\delta\right)\|\hat{z}^{k}-z^{*}\|^{2} +2\delta\|z_{g}^{k}-z^{*}\|^{2}+\left(2\gamma\delta^{2}-\delta\right)\|z_{g}^{ k}-z^{k}\|^{2}$ $\displaystyle-2\nu^{-1}\langle\mathbf{P}(y_{g}^{k}+z_{g}^{k}),z^{k}-z^{*} \rangle+\gamma\|\nu^{-1}\mathbf{P}(y_{g}^{k}+z_{g}^{k})\|^{2}+2\delta\|m^{k}\| ^{2}_{\mathbf{P}}+2\nu^{-1}\langle\mathbf{P}(y_{g}^{k}+z_{g}^{k}),m^{k}\rangle.$ $$

Using the fact that $z^{k}\in\mathcal{L}^{\perp}$ for all $k=0,1,2\ldots$ and optimality condition (5) we get

$$ $\displaystyle\frac{1}{\gamma}\|\hat{z}^{k+1}-z^{*}\|^{2}$ $\displaystyle\leq\left(\frac{1}{\gamma}-\delta\right)\|\hat{z}^{k}-z^{*}\|^{2} +2\delta\|z_{g}^{k}-z^{*}\|^{2}+\left(2\gamma\delta^{2}-\delta\right)\|z_{g}^{ k}-z^{k}\|^{2}$ $\displaystyle-2\nu^{-1}\langle y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*}),z^{k}-z^{*} \rangle+\gamma\nu^{-2}\|y_{g}^{k}+z_{g}^{k}\|^{2}_{\mathbf{P}}$ $\displaystyle+2\delta\|m^{k}\|^{2}_{\mathbf{P}}+2\nu^{-1}\langle\mathbf{P}(y_{ g}^{k}+z_{g}^{k}),m^{k}\rangle.$ $$

Using Young’s inequality we get

$$ $\displaystyle\frac{1}{\gamma}\|\hat{z}^{k+1}-z^{*}\|^{2}$ $\displaystyle\leq\left(\frac{1}{\gamma}-\delta\right)\|\hat{z}^{k}-z^{*}\|^{2} +2\delta\|z_{g}^{k}-z^{*}\|^{2}+\left(2\gamma\delta^{2}-\delta\right)\|z_{g}^{ k}-z^{k}\|^{2}$ $\displaystyle-2\nu^{-1}\langle y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*}),z^{k}-z^{*} \rangle+\gamma\nu^{-2}\|y_{g}^{k}+z_{g}^{k}\|^{2}_{\mathbf{P}}$ $\displaystyle+2\delta\|m^{k}\|^{2}_{\mathbf{P}}+3\gamma\chi\nu^{-2}\|y_{g}^{k} +z_{g}^{k}\|^{2}_{\mathbf{P}}+\frac{1}{3\gamma\chi}\|m^{k}\|^{2}_{\mathbf{P}}.$ $$

Using (22) we get

$$ $\displaystyle\frac{1}{\gamma}\|\hat{z}^{k+1}-z^{*}\|^{2}$ $\displaystyle\leq\left(\frac{1}{\gamma}-\delta\right)\|\hat{z}^{k}-z^{*}\|^{2} +2\delta\|z_{g}^{k}-z^{*}\|^{2}+\left(2\gamma\delta^{2}-\delta\right)\|z_{g}^{ k}-z^{k}\|^{2}$ $\displaystyle-2\nu^{-1}\langle y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*}),z^{k}-z^{*} \rangle+\gamma\nu^{-2}\|y_{g}^{k}+z_{g}^{k}\|^{2}_{\mathbf{P}}$ $\displaystyle+2\delta\|m^{k}\|^{2}_{\mathbf{P}}+6\gamma\nu^{-2}\chi\|y_{g}^{k} +z_{g}^{k}\|^{2}_{\mathbf{P}}+\frac{4(1-(4\chi)^{-1})}{3\gamma}\|m^{k}\|^{2}_{ \mathbf{P}}-\frac{4}{3\gamma}\|m^{k+1}\|^{2}_{\mathbf{P}}$ $\displaystyle=\left(\frac{1}{\gamma}-\delta\right)\|\hat{z}^{k}-z^{*}\|^{2}+2 \delta\|z_{g}^{k}-z^{*}\|^{2}+\left(2\gamma\delta^{2}-\delta\right)\|z_{g}^{k} -z^{k}\|^{2}$ $\displaystyle-2\nu^{-1}\langle y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*}),z^{k}-z^{*} \rangle+\gamma\nu^{-2}\left(1+6\chi\right)\|y_{g}^{k}+z_{g}^{k}\|^{2}_{\mathbf {P}}$ $\displaystyle+\left(1-(4\chi)^{-1}+\frac{3\gamma\delta}{2}\right)\frac{4}{3 \gamma}\|m^{k}\|^{2}_{\mathbf{P}}-\frac{4}{3\gamma}\|m^{k+1}\|^{2}_{\mathbf{P}}.$ $$

∎

###### Lemma A.7 .

The following inequality holds:

$$ $\begin{split}&2\langle y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*}),y^{k}+z^{k}-(y^{*}+z^ {*})\rangle\\ &\geq 2\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+\frac{(1-\sigma_{2}/2)}{ \sigma_{2}}\left(\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}-\|y_{f}^{k}+z_{f}^{ k}-(y^{*}+z^{*})\|^{2}\right).\end{split}$ (25) $$

###### Proof.

$$ $\displaystyle 2\langle y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*}),y^{k}+z^{k}-(y^{*}+z^ {*})\rangle$ $\displaystyle=2\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+2\langle y_{g}^{k}+z_ {g}^{k}-(y^{*}+z^{*}),y^{k}+z^{k}-(y_{g}^{k}+z_{g}^{k})\rangle.$ $$

Using Lines 10 and 13 of Algorithm 1 we get

$$ $\displaystyle 2\langle y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*}),y^{k}+z^{k}-(y^{*}+z^ {*})\rangle$ $\displaystyle=2\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+\frac{2(1-\sigma_{1}) }{\sigma_{1}}\langle y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*}),y_{g}^{k}+z_{g}^{k}-(y_ {f}^{k}+z_{f}^{k})\rangle$ $\displaystyle=2\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}$ $\displaystyle+\frac{(1-\sigma_{1})}{\sigma_{1}}\left(\|y_{g}^{k}+z_{g}^{k}-(y^ {*}+z^{*})\|^{2}+\|y_{g}^{k}+z_{g}^{k}-(y_{f}^{k}+z_{f}^{k})\|^{2}-\|y_{f}^{k} +z_{f}^{k}-(y^{*}+z^{*})\|^{2}\right)$ $\displaystyle\geq 2\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+\frac{(1-\sigma_{ 1})}{\sigma_{1}}\left(\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}-\|y_{f}^{k}+z_ {f}^{k}-(y^{*}+z^{*})\|^{2}\right).$ $$

Using $\sigma_{1}$ definition (20) we get

$$ $\displaystyle 2\langle y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*}),y^{k}+z^{k}-(y^{*}+z^ {*})\rangle$ $\displaystyle\geq 2\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+\frac{(1-\sigma_{ 2}/2)}{\sigma_{2}}\left(\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}-\|y_{f}^{k}+ z_{f}^{k}-(y^{*}+z^{*})\|^{2}\right).$ $$

∎

###### Lemma A.8 .

Let $\zeta$ be defined by

$$ $\zeta=1/2.$ (26) $$

Then the following inequality holds:

$$ $\begin{split}&-2\langle y^{k+1}-y^{k},y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\rangle \\ &\leq\frac{1}{\sigma_{2}}\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}-\frac{1}{ \sigma_{2}}\|y_{f}^{k+1}+z_{f}^{k+1}-(y^{*}+z^{*})\|^{2}\\ &+2\sigma_{2}\|y^{k+1}-y^{k}\|^{2}-\frac{1}{2\sigma_{2}\chi}\|y_{g}^{k}+z_{g}^ {k}\|^{2}_{\mathbf{P}}.\end{split}$ (27) $$

###### Proof.

$$ $\displaystyle\|y_{f}^{k+1}+z_{f}^{k+1}-(y^{*}+z^{*})\|^{2}$ $\displaystyle=\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+2\langle y_{f}^{k+1}+z _{f}^{k+1}-(y_{g}^{k}+z_{g}^{k}),y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\rangle$ $\displaystyle+\|y_{f}^{k+1}+z_{f}^{k+1}-(y_{g}^{k}+z_{g}^{k})\|^{2}$ $\displaystyle\leq\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+2\langle y_{f}^{k+1 }+z_{f}^{k+1}-(y_{g}^{k}+z_{g}^{k}),y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\rangle$ $\displaystyle+2\|y_{f}^{k+1}-y_{g}^{k}\|^{2}+2\|z_{f}^{k+1}-z_{g}^{k}\|^{2}.$ $$

Using Line 12 of Algorithm 1 we get

$$ $\displaystyle\|y_{f}^{k+1}+z_{f}^{k+1}-(y^{*}+z^{*})\|^{2}$ $\displaystyle\leq\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+2\sigma_{2}\langle y ^{k+1}-y^{k},y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\rangle+2\sigma_{2}^{2}\|y^{k+1} -y^{k}\|^{2}$ $\displaystyle+2\langle z_{f}^{k+1}-z_{g}^{k},y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*}) \rangle+2\|z_{f}^{k+1}-z_{g}^{k}\|^{2}.$ $$

Using Line 16 of Algorithm 1 and optimality condition (5) we get

$$ $\displaystyle\|y_{f}^{k+1}+z_{f}^{k+1}-(y^{*}+z^{*})\|^{2}$ $\displaystyle\leq\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+2\sigma_{2}\langle y ^{k+1}-y^{k},y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\rangle+2\sigma_{2}^{2}\|y^{k+1} -y^{k}\|^{2}$ $\displaystyle-2\zeta\langle(\mathbf{W}(k)\otimes\mathbf{I}_{d})(y_{g}^{k}+z_{g }^{k}),y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\rangle+2\zeta^{2}\|(\mathbf{W}(k) \otimes\mathbf{I}_{d})(y_{g}^{k}+z_{g}^{k})\|^{2}$ $\displaystyle=\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+2\sigma_{2}\langle y^{ k+1}-y^{k},y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\rangle+2\sigma_{2}^{2}\|y^{k+1}-y ^{k}\|^{2}$ $\displaystyle-2\zeta\langle(\mathbf{W}(k)\otimes\mathbf{I}_{d})(y_{g}^{k}+z_{g }^{k}),y_{g}^{k}+z_{g}^{k}\rangle+2\zeta^{2}\|(\mathbf{W}(k)\otimes\mathbf{I}_ {d})(y_{g}^{k}+z_{g}^{k})\|^{2}.$ $$

Using $\zeta$ definition (26) we get

$$ $\displaystyle\|y_{f}^{k+1}+z_{f}^{k+1}-(y^{*}+z^{*})\|^{2}$ $\displaystyle\leq\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+2\sigma_{2}\langle y ^{k+1}-y^{k},y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\rangle+2\sigma_{2}^{2}\|y^{k+1} -y^{k}\|^{2}$ $\displaystyle-\langle(\mathbf{W}(k)\otimes\mathbf{I}_{d})(y_{g}^{k}+z_{g}^{k}) ,y_{g}^{k}+z_{g}^{k}\rangle+\frac{1}{2}\|(\mathbf{W}(k)\otimes\mathbf{I}_{d})( y_{g}^{k}+z_{g}^{k})\|^{2}$ $\displaystyle=\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+2\sigma_{2}\langle y^{ k+1}-y^{k},y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\rangle+2\sigma_{2}^{2}\|y^{k+1}-y ^{k}\|^{2}$ $\displaystyle-\frac{1}{2}\|(\mathbf{W}(k)\otimes\mathbf{I}_{d})(y_{g}^{k}+z_{g }^{k})\|^{2}-\frac{1}{2}\|y_{g}^{k}+z_{g}^{k}\|^{2}+\frac{1}{2}\|(\mathbf{W}(k )\otimes\mathbf{I}_{d})(y_{g}^{k}+z_{g}^{k})-(y_{g}^{k}+z_{g}^{k})\|^{2}$ $\displaystyle+\frac{1}{2}\|(\mathbf{W}(k)\otimes\mathbf{I}_{d})(y_{g}^{k}+z_{g }^{k})\|^{2}$ $\displaystyle\leq\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+2\sigma_{2}\langle y ^{k+1}-y^{k},y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\rangle+2\sigma_{2}^{2}\|y^{k+1} -y^{k}\|^{2}$ $\displaystyle-\frac{1}{2}\|y_{g}^{k}+z_{g}^{k}\|^{2}_{\mathbf{P}}+\frac{1}{2} \|(\mathbf{W}(k)\otimes\mathbf{I}_{d})(y_{g}^{k}+z_{g}^{k})-(y_{g}^{k}+z_{g}^{ k})\|^{2}_{\mathbf{P}}.$ $\displaystyle=\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+2\sigma_{2}\langle y^{ k+1}-y^{k},y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\rangle+2\sigma_{2}^{2}\|y^{k+1}-y ^{k}\|^{2}$ $\displaystyle-\frac{1}{2}\|y_{g}^{k}+z_{g}^{k}\|^{2}_{\mathbf{P}}+\frac{1}{2} \|(\mathbf{W}(k)\otimes\mathbf{I}_{d})\mathbf{P}(y_{g}^{k}+z_{g}^{k})-\mathbf{ P}(y_{g}^{k}+z_{g}^{k})\|^{2}.$ $$

Using condition (2) we get

$$ $\displaystyle\|y_{f}^{k+1}+z_{f}^{k+1}-(y^{*}+z^{*})\|^{2}$ $\displaystyle\leq\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+2\sigma_{2}\langle y ^{k+1}-y^{k},y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\rangle+2\sigma_{2}^{2}\|y^{k+1} -y^{k}\|^{2}$ $\displaystyle-(2\chi)^{-1}\|y_{g}^{k}+z_{g}^{k}\|^{2}_{\mathbf{P}}.$ $$

Rearranging gives

$$ $\displaystyle-2\langle y^{k+1}-y^{k},y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\rangle$ $\displaystyle\leq\frac{1}{\sigma_{2}}\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2} -\frac{1}{\sigma_{2}}\|y_{f}^{k+1}+z_{f}^{k+1}-(y^{*}+z^{*})\|^{2}$ $\displaystyle+2\sigma_{2}\|y^{k+1}-y^{k}\|^{2}-\frac{1}{2\sigma_{2}\chi}\|y_{g }^{k}+z_{g}^{k}\|^{2}_{\mathbf{P}}.$ $$

∎

###### Lemma A.9 .

Let $\delta$ be defined as follows:

$$ $\delta=\frac{1}{17L}.$ (28) $$

Let $\gamma$ be defined as follows:

$$ $\gamma=\frac{\nu}{14\sigma_{2}\chi^{2}}.$ (29) $$

Let $\theta$ be defined as follows:

$$ $\theta=\frac{\nu}{4\sigma_{2}}.$ (30) $$

Let $\sigma_{2}$ be defined as follows:

$$ $\sigma_{2}=\frac{\sqrt{\mu}}{16\chi\sqrt{L}}.$ (31) $$

Let $\Psi_{yz}^{k}$ be the following Lyapunov function

$$ $\begin{split}\Psi_{yz}^{k}&=\left(\frac{1}{\theta}+\frac{\beta}{2}\right)\|y^{ k}-y^{*}\|^{2}+\frac{\beta}{2\sigma_{2}}\|y_{f}^{k}-y^{*}\|^{2}+\frac{1}{ \gamma}\|\hat{z}^{k}-z^{*}\|^{2}\\ &+\frac{4}{3\gamma}\|m^{k}\|^{2}_{\mathbf{P}}+\frac{\nu^{-1}}{\sigma_{2}}\|y_{ f}^{k}+z_{f}^{k}-(y^{*}+z^{*})\|^{2}.\end{split}$ (32) $$

Then the following inequality holds:

$$ $\begin{split}\mathbb{E}\left[\Psi_{yz}^{k+1}\right]&\left(1-\frac{\sqrt{\mu}}{ 32\chi\sqrt{L}}\right)\Psi_{yz}^{k}-2\mathbb{E}\left[\langle x^{k+1}-x^{*},y^{ k+1}-y^{*}\rangle\right]+\mathrm{G}_{F}(x_{g}^{k},x^{*})\\ &+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})-\mathrm{G}_{F} (x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x_{g}^{k}+\nu x ^{*},\omega^{k}-x_{g}^{k}\rangle\right).\end{split}$ (33) $$

###### Proof.

Combining (LABEL:scary:eq:y) and (LABEL:scary:eq:z) gives

$$ $\displaystyle\left(\frac{1}{\theta}+\frac{\beta}{2}\right)\mathbb{E}\left[\|y^ {k+1}-y^{*}\|^{2}\right]+\frac{\beta}{2\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1 }-y^{*}\|^{2}\right]+\frac{1}{\gamma}\|\hat{z}^{k+1}-z^{*}\|^{2}+\frac{4}{3 \gamma}\|m^{k+1}\|^{2}_{\mathbf{P}}$ $\displaystyle\leq\left(\frac{1}{\gamma}-\delta\right)\|\hat{z}^{k}-z^{*}\|^{2} +\left(1-(4\chi)^{-1}+\frac{3\gamma\delta}{2}\right)\frac{4}{3\gamma}\|m^{k}\| ^{2}_{\mathbf{P}}+\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+\frac{\beta(1-\sigma_{2} /2)}{2\sigma_{2}}\|y_{f}^{k}-y^{*}\|^{2}$ $\displaystyle-2\nu^{-1}\langle y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*}),y^{k}+z^{k}-( y^{*}+z^{*})\rangle-2\nu^{-1}\mathbb{E}\left[\langle y_{g}^{k}+z_{g}^{k}-(y^{* }+z^{*}),y^{k+1}-y^{k}\rangle\right]$ $\displaystyle+\gamma\nu^{-2}\left(1+6\chi\right)\|y_{g}^{k}+z_{g}^{k}\|^{2}_{ \mathbf{P}}+\left(\frac{\beta\sigma_{2}^{2}}{4}-\frac{1}{\theta}\right)\mathbb {E}\left[\|y^{k+1}-y^{k}\|^{2}\right]+2\delta\|z_{g}^{k}-z^{*}\|^{2}-\frac{ \beta}{4}\|y_{g}^{k}-y^{*}\|^{2}$ $\displaystyle-2\mathbb{E}\left[\langle x^{k+1}-x^{*},y^{k+1}-y^{*}\rangle \right]+\left(2\gamma\delta^{2}-\delta\right)\|z_{g}^{k}-z^{k}\|^{2}+\mathrm{G }_{F}(x_{g}^{k},x^{*})$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x _{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right).$ $$

Using (LABEL:scary:eq:3) and (LABEL:scary:eq:4) we get

$$ $\displaystyle\left(\frac{1}{\theta}+\frac{\beta}{2}\right)\mathbb{E}\left[\|y^ {k+1}-y^{*}\|^{2}\right]+\frac{\beta}{2\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1 }-y^{*}\|^{2}\right]+\frac{1}{\gamma}\|\hat{z}^{k+1}-z^{*}\|^{2}+\frac{4}{3 \gamma}\|m^{k+1}\|^{2}_{\mathbf{P}}$ $\displaystyle\leq\left(\frac{1}{\gamma}-\delta\right)\|\hat{z}^{k}-z^{*}\|^{2} +\left(1-(4\chi)^{-1}+\frac{3\gamma\delta}{2}\right)\frac{4}{3\gamma}\|m^{k}\| ^{2}_{\mathbf{P}}+\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+\frac{\beta(1-\sigma_{2} /2)}{2\sigma_{2}}\|y_{f}^{k}-y^{*}\|^{2}$ $\displaystyle-2\nu^{-1}\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+\frac{\nu^{-1 }(1-\sigma_{2}/2)}{\sigma_{2}}\left(\|y_{f}^{k}+z_{f}^{k}-(y^{*}+z^{*})\|^{2}- \|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}\right)$ $\displaystyle+\frac{\nu^{-1}}{\sigma_{2}}\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\| ^{2}-\frac{\nu^{-1}}{\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1}+z_{f}^{k+1}-(y^{ *}+z^{*})\|^{2}\right]+2\nu^{-1}\sigma_{2}\mathbb{E}\left[\|y^{k+1}-y^{k}\|^{2 }\right]$ $\displaystyle-\frac{\nu^{-1}}{2\sigma_{2}\chi}\|y_{g}^{k}+z_{g}^{k}\|^{2}_{ \mathbf{P}}+\gamma\nu^{-2}\left(1+6\chi\right)\|y_{g}^{k}+z_{g}^{k}\|^{2}_{ \mathbf{P}}+\left(\frac{\beta\sigma_{2}^{2}}{4}-\frac{1}{\theta}\right)\mathbb {E}\left[\|y^{k+1}-y^{k}\|^{2}\right]+2\delta\|z_{g}^{k}-z^{*}\|^{2}$ $\displaystyle-\frac{\beta}{4}\|y_{g}^{k}-y^{*}\|^{2}-2\mathbb{E}\left[\langle x ^{k+1}-x^{*},y^{k+1}-y^{*}\rangle\right]+\left(2\gamma\delta^{2}-\delta\right) \|z_{g}^{k}-z^{k}\|^{2}+\mathrm{G}_{F}(x_{g}^{k},x^{*})$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x _{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right)$ $\displaystyle=\left(\frac{1}{\gamma}-\delta\right)\|\hat{z}^{k}-z^{*}\|^{2}+ \left(1-(4\chi)^{-1}+\frac{3\gamma\delta}{2}\right)\frac{4}{3\gamma}\|m^{k}\|^ {2}_{\mathbf{P}}+\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+\frac{\beta(1-\sigma_{2}/ 2)}{2\sigma_{2}}\|y_{f}^{k}-y^{*}\|^{2}$ $\displaystyle+\frac{\nu^{-1}(1-\sigma_{2}/2)}{\sigma_{2}}\|y_{f}^{k}+z_{f}^{k} -(y^{*}+z^{*})\|^{2}-\frac{\nu^{-1}}{\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1}+ z_{f}^{k+1}-(y^{*}+z^{*})\|^{2}\right]$ $\displaystyle+2\delta\|z_{g}^{k}-z^{*}\|^{2}-\frac{\beta}{4}\|y_{g}^{k}-y^{*} \|^{2}+\nu^{-1}\left(\frac{1}{\sigma_{2}}-\frac{(1-\sigma_{2}/2)}{\sigma_{2}}- 2\right)\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}$ $\displaystyle+\left(\gamma\nu^{-2}\left(1+6\chi\right)-\frac{\nu^{-1}}{2\sigma _{2}\chi}\right)\|y_{g}^{k}+z_{g}^{k}\|^{2}_{\mathbf{P}}+\left(\frac{\beta \sigma_{2}^{2}}{4}+2\nu^{-1}\sigma_{2}-\frac{1}{\theta}\right)\mathbb{E}\left[ \|y^{k+1}-y^{k}\|^{2}\right]$ $\displaystyle+\left(2\gamma\delta^{2}-\delta\right)\|z_{g}^{k}-z^{k}\|^{2}-2 \mathbb{E}\left[\langle x^{k+1}-x^{*},y^{k+1}-y^{*}\rangle\right]+\mathrm{G}_{ F}(x_{g}^{k},x^{*})$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x _{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right)$ $\displaystyle=\left(\frac{1}{\gamma}-\delta\right)\|\hat{z}^{k}-z^{*}\|^{2}+ \left(1-(4\chi)^{-1}+\frac{3\gamma\delta}{2}\right)\frac{4}{3\gamma}\|m^{k}\|^ {2}_{\mathbf{P}}+\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+\frac{\beta(1-\sigma_{2}/ 2)}{2\sigma_{2}}\|y_{f}^{k}-y^{*}\|^{2}$ $\displaystyle+\frac{\nu^{-1}(1-\sigma_{2}/2)}{\sigma_{2}}\|y_{f}^{k}+z_{f}^{k} -(y^{*}+z^{*})\|^{2}-\frac{\nu^{-1}}{\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1}+ z_{f}^{k+1}-(y^{*}+z^{*})\|^{2}\right]$ $\displaystyle+2\delta\|z_{g}^{k}-z^{*}\|^{2}-\frac{\beta}{4}\|y_{g}^{k}-y^{*} \|^{2}-\frac{3\nu^{-1}}{2}\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+\left(2 \gamma\delta^{2}-\delta\right)\|z_{g}^{k}-z^{k}\|^{2}$ $\displaystyle+\left(\gamma\nu^{-2}\left(1+6\chi\right)-\frac{\nu^{-1}}{2\sigma _{2}\chi}\right)\|y_{g}^{k}+z_{g}^{k}\|^{2}_{\mathbf{P}}+\left(\frac{\beta \sigma_{2}^{2}}{4}+2\nu^{-1}\sigma_{2}-\frac{1}{\theta}\right)\mathbb{E}\left[ \|y^{k+1}-y^{k}\|^{2}\right]$ $\displaystyle+2\mathbb{E}\left[\langle x^{k+1}-x^{*},y^{k+1}-y^{*}\rangle \right]+\mathrm{G}_{F}(x_{g}^{k},x^{*})$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x _{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right).$ $$

Using $\beta$ definition (19) and $\nu$ definition (15) we get

$$ $\displaystyle\left(\frac{1}{\theta}+\frac{\beta}{2}\right)\mathbb{E}\left[\|y^ {k+1}-y^{*}\|^{2}\right]+\frac{\beta}{2\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1 }-y^{*}\|^{2}\right]+\frac{1}{\gamma}\|\hat{z}^{k+1}-z^{*}\|^{2}+\frac{4}{3 \gamma}\|m^{k+1}\|^{2}_{\mathbf{P}}$ $\displaystyle\leq\left(\frac{1}{\gamma}-\delta\right)\|\hat{z}^{k}-z^{*}\|^{2} +\left(1-(4\chi)^{-1}+\frac{3\gamma\delta}{2}\right)\frac{4}{3\gamma}\|m^{k}\| ^{2}_{\mathbf{P}}+\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+\frac{\beta(1-\sigma_{2} /2)}{2\sigma_{2}}\|y_{f}^{k}-y^{*}\|^{2}$ $\displaystyle+\frac{\nu^{-1}(1-\sigma_{2}/2)}{\sigma_{2}}\|y_{f}^{k}+z_{f}^{k} -(y^{*}+z^{*})\|^{2}-\frac{\nu^{-1}}{\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1}+ z_{f}^{k+1}-(y^{*}+z^{*})\|^{2}\right]$ $\displaystyle+2\delta\|z_{g}^{k}-z^{*}\|^{2}-\frac{1}{8L}\|y_{g}^{k}-y^{*}\|^{ 2}-\frac{3}{\mu}\|y_{g}^{k}+z_{g}^{k}-(y^{*}+z^{*})\|^{2}+\left(2\gamma\delta^ {2}-\delta\right)\|z_{g}^{k}-z^{k}\|^{2}$ $\displaystyle+\left(\gamma\nu^{-2}\left(1+6\chi\right)-\frac{\nu^{-1}}{2\sigma _{2}\chi}\right)\|y_{g}^{k}+z_{g}^{k}\|^{2}_{\mathbf{P}}+\left(\frac{\beta \sigma_{2}^{2}}{4}+2\nu^{-1}\sigma_{2}-\frac{1}{\theta}\right)\mathbb{E}\left[ \|y^{k+1}-y^{k}\|^{2}\right]$ $\displaystyle-2\mathbb{E}\left[\langle x^{k+1}-x^{*},y^{k+1}-y^{*}\rangle \right]+\mathrm{G}_{F}(x_{g}^{k},x^{*})$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x _{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right).$ $$

Using $\delta$ definition (28) we get

$$ $\displaystyle\left(\frac{1}{\theta}+\frac{\beta}{2}\right)\mathbb{E}\left[\|y^ {k+1}-y^{*}\|^{2}\right]+\frac{\beta}{2\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1 }-y^{*}\|^{2}\right]+\frac{1}{\gamma}\|\hat{z}^{k+1}-z^{*}\|^{2}+\frac{4}{3 \gamma}\|m^{k+1}\|^{2}_{\mathbf{P}}$ $\displaystyle\leq\left(\frac{1}{\gamma}-\delta\right)\|\hat{z}^{k}-z^{*}\|^{2} +\left(1-(4\chi)^{-1}+\frac{3\gamma\delta}{2}\right)\frac{4}{3\gamma}\|m^{k}\| ^{2}_{\mathbf{P}}+\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+\frac{\beta(1-\sigma_{2} /2)}{2\sigma_{2}}\|y_{f}^{k}-y^{*}\|^{2}$ $\displaystyle+\frac{\nu^{-1}(1-\sigma_{2}/2)}{\sigma_{2}}\|y_{f}^{k}+z_{f}^{k} -(y^{*}+z^{*})\|^{2}-\frac{\nu^{-1}}{\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1}+ z_{f}^{k+1}-(y^{*}+z^{*})\|^{2}\right]$ $\displaystyle+\left(\gamma\nu^{-2}\left(1+6\chi\right)-\frac{\nu^{-1}}{2\sigma _{2}\chi}\right)\|y_{g}^{k}+z_{g}^{k}\|^{2}_{\mathbf{P}}+\left(\frac{\beta \sigma_{2}^{2}}{4}+2\nu^{-1}\sigma_{2}-\frac{1}{\theta}\right)\mathbb{E}\left[ \|y^{k+1}-y^{k}\|^{2}\right]$ $\displaystyle+\left(2\gamma\delta^{2}-\delta\right)\|z_{g}^{k}-z^{k}\|^{2}-2 \mathbb{E}\left[\langle x^{k+1}-x^{*},y^{k+1}-y^{*}\rangle\right]+\mathrm{G}_{ F}(x_{g}^{k},x^{*})$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x _{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right).$ $$

Using $\gamma$ definition (29) we get

$$ $\displaystyle\left(\frac{1}{\theta}+\frac{\beta}{2}\right)\mathbb{E}\left[\|y^ {k+1}-y^{*}\|^{2}\right]+\frac{\beta}{2\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1 }-y^{*}\|^{2}\right]+\frac{1}{\gamma}\|\hat{z}^{k+1}-z^{*}\|^{2}+\frac{4}{3 \gamma}\|m^{k+1}\|^{2}_{\mathbf{P}}$ $\displaystyle\leq\left(\frac{1}{\gamma}-\delta\right)\|\hat{z}^{k}-z^{*}\|^{2} +\left(1-(4\chi)^{-1}+\frac{3\gamma\delta}{2}\right)\frac{4}{3\gamma}\|m^{k}\| ^{2}_{\mathbf{P}}+\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+\frac{\beta(1-\sigma_{2} /2)}{2\sigma_{2}}\|y_{f}^{k}-y^{*}\|^{2}$ $\displaystyle+\frac{\nu^{-1}(1-\sigma_{2}/2)}{\sigma_{2}}\|y_{f}^{k}+z_{f}^{k} -(y^{*}+z^{*})\|^{2}-\frac{\nu^{-1}}{\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1}+ z_{f}^{k+1}-(y^{*}+z^{*})\|^{2}\right]$ $\displaystyle+\left(\frac{\beta\sigma_{2}^{2}}{4}+2\nu^{-1}\sigma_{2}-\frac{1} {\theta}\right)\mathbb{E}\left[\|y^{k+1}-y^{k}\|^{2}\right]+\left(2\gamma \delta^{2}-\delta\right)\|z_{g}^{k}-z^{k}\|^{2}$ $\displaystyle-2\mathbb{E}\left[\langle x^{k+1}-x^{*},y^{k+1}-y^{*}\rangle \right]+\mathrm{G}_{F}(x_{g}^{k},x^{*})$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x _{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right).$ $$

Using $\theta$ definition together with (15), (19) and (31) gives

$$ $\displaystyle\left(\frac{1}{\theta}+\frac{\beta}{2}\right)\mathbb{E}\left[\|y^ {k+1}-y^{*}\|^{2}\right]+\frac{\beta}{2\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1 }-y^{*}\|^{2}\right]+\frac{1}{\gamma}\|\hat{z}^{k+1}-z^{*}\|^{2}+\frac{4}{3 \gamma}\|m^{k+1}\|^{2}_{\mathbf{P}}$ $\displaystyle\leq\left(\frac{1}{\gamma}-\delta\right)\|\hat{z}^{k}-z^{*}\|^{2} +\left(1-(4\chi)^{-1}+\frac{3\gamma\delta}{2}\right)\frac{4}{3\gamma}\|m^{k}\| ^{2}_{\mathbf{P}}+\frac{1}{\theta}\|y^{k}-y^{*}\|^{2}+\frac{\beta(1-\sigma_{2} /2)}{2\sigma_{2}}\|y_{f}^{k}-y^{*}\|^{2}$ $\displaystyle+\frac{\nu^{-1}(1-\sigma_{2}/2)}{\sigma_{2}}\|y_{f}^{k}+z_{f}^{k} -(y^{*}+z^{*})\|^{2}-\frac{\nu^{-1}}{\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1}+ z_{f}^{k+1}-(y^{*}+z^{*})\|^{2}\right]$ $\displaystyle+\left(2\gamma\delta^{2}-\delta\right)\|z_{g}^{k}-z^{k}\|^{2}-2 \mathbb{E}\left[\langle x^{k+1}-x^{*},y^{k+1}-y^{*}\rangle\right]+\mathrm{G}_{ F}(x_{g}^{k},x^{*})$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x _{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right).$ $$

Using $\gamma$ definition (29) and $\delta$ definition (28) we get

$$ $\displaystyle\left(\frac{1}{\theta}+\frac{\beta}{2}\right)\mathbb{E}\left[\|y^ {k+1}-y^{*}\|^{2}\right]+\frac{\beta}{2\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1 }-y^{*}\|^{2}\right]+\frac{1}{\gamma}\|\hat{z}^{k+1}-z^{*}\|^{2}+\frac{4}{3 \gamma}\|m^{k+1}\|^{2}_{\mathbf{P}}$ $\displaystyle\leq\left(\frac{1}{\gamma}-\delta\right)\|\hat{z}^{k}-z^{*}\|^{2} +\left(1-(8\chi)^{-1}\right)\frac{4}{3\gamma}\|m^{k}\|^{2}_{\mathbf{P}}+\frac{ 1}{\theta}\|y^{k}-y^{*}\|^{2}+\frac{\beta(1-\sigma_{2}/2)}{2\sigma_{2}}\|y_{f} ^{k}-y^{*}\|^{2}$ $\displaystyle+\frac{\nu^{-1}(1-\sigma_{2}/2)}{\sigma_{2}}\|y_{f}^{k}+z_{f}^{k} -(y^{*}+z^{*})\|^{2}-\frac{\nu^{-1}}{\sigma_{2}}\mathbb{E}\left[\|y_{f}^{k+1}+ z_{f}^{k+1}-(y^{*}+z^{*})\|^{2}\right]$ $\displaystyle-2\mathbb{E}\left[\langle x^{k+1}-x^{*},y^{k+1}-y^{*}\rangle \right]+\mathrm{G}_{F}(x_{g}^{k},x^{*})$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x _{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right).$ $$

After rearranging and using $\Psi_{yz}^{k}$ definition (32) we get

$$ $\displaystyle\mathbb{E}\left[\Psi_{yz}^{k+1}\right]$ $\displaystyle\leq\max\left\{(1+\theta\beta/2)^{-1},(1-\gamma\delta),(1-\sigma_ {2}/2),(1-(8\chi)^{-1})\right\}\Psi_{yz}^{k}$ $\displaystyle-2\mathbb{E}\left[\langle x^{k+1}-x^{*},y^{k+1}-y^{*}\rangle \right]+\mathrm{G}_{F}(x_{g}^{k},x^{*})$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x _{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right)$ $\displaystyle\leq\left(1-\frac{\sqrt{\mu}}{32\chi\sqrt{L}}\right)\Psi_{yz}^{k}$ $\displaystyle-2\mathbb{E}\left[\langle x^{k+1}-x^{*},y^{k+1}-y^{*}\rangle \right]+\mathrm{G}_{F}(x_{g}^{k},x^{*})$ $\displaystyle+\frac{\overline{L}}{Lb}\left(\mathrm{G}_{F}(\omega^{k},x^{*})- \mathrm{G}_{F}(x_{g}^{k},x^{*})-\langle\nabla F(x_{g}^{k})-\nabla F(x^{*})-\nu x _{g}^{k}+\nu x^{*},\omega^{k}-x_{g}^{k}\rangle\right).$ $$

∎

###### Lemma A.10 .

Let $\lambda$ be defined as follows:

$$ $\lambda=\frac{n}{b}\left(\frac{1}{2}+\frac{\overline{L}}{Lb\tau_{1}}\right).$ (34) $$

Let $p_{1}$ be defined as follows:

$$ $p_{1}=\frac{1}{2\lambda}.$ (35) $$

Let $p_{2}$ be defined as follows:

$$ $p_{2}=\frac{\overline{L}}{\lambda Lb\tau_{1}}.$ (36) $$

Then the following inequality holds:

$$ $\begin{split}\mathbb{E}\left[\Psi_{x}^{k}+\Psi_{yz}^{k}+\lambda\mathrm{G}_{F}( \omega^{k+1},x^{*})\right]\leq\left(1-\frac{1}{32}\min\left\{\frac{b}{n},b \sqrt{\frac{\mu}{nL}},\frac{b^{2}L}{n\overline{L}}\sqrt{\frac{\mu}{L}},\frac{ \sqrt{\mu}}{\chi\sqrt{L}}\right\}\right)(\Psi_{x}^{0}+\Psi_{yz}^{0}+\lambda \mathrm{G}_{F}(\omega^{k},x^{*})).\end{split}$ (37) $$

###### Proof.

Combining (17) and (33) gives

$$ $\begin{split}\mathbb{E}\left[\Psi_{x}^{k+1}+\Psi_{yz}^{k+1}\right]&\leq\left(1 -\frac{1}{20}\min\left\{\sqrt{\frac{\mu}{L}},b\sqrt{\frac{\mu}{nL}}\right\} \right)\Psi_{x}^{k}+\left(1-\frac{\sqrt{\mu}}{32\chi\sqrt{L}}\right)\Psi_{yz}^ {k}\\ &-\frac{\overline{L}}{Lb\tau_{1}}\mathrm{G}_{F}(x_{g}^{k},x^{*})+\frac{ \overline{L}}{Lb\tau_{1}}\mathrm{G}_{F}(\omega^{k},x^{*})-\frac{1}{2}\mathrm{G }_{F}(x_{f}^{k},x^{*})\\ &\leq\left(1-\frac{1}{32}\min\left\{b\sqrt{\frac{\mu}{nL}},\frac{\sqrt{\mu}}{ \chi\sqrt{L}}\right\}\right)(\Psi_{x}^{k}+\Psi_{yz}^{k})\\ &-\frac{\overline{L}}{Lb\tau_{1}}\mathrm{G}_{F}(x_{g}^{k},x^{*})+\frac{ \overline{L}}{Lb\tau_{1}}\mathrm{G}_{F}(\omega^{k},x^{*})-\frac{1}{2}\mathrm{G }_{F}(x_{f}^{k},x^{*}).\end{split}$ (38) $$

Using (9) we get the following inequality:

$$ $\mathbb{E}\left[\mathrm{G}_{F}(\omega^{k+1},x^{*})\right]\leq p_{1}\mathrm{G}_ {F}(x_{f}^{k},x^{*})+p_{2}\mathrm{G}_{F}(x_{g}^{k},x^{*})+(1-p_{1}-p_{2}) \mathrm{G}_{F}(\omega^{k},x^{*}).$ (39) $$

Multiplying (39) on $\lambda$ and combining with (38) we get

$$ $\displaystyle\mathbb{E}\left[\Psi_{x}^{k+1}+\Psi_{yz}^{k+1}+\lambda\mathrm{G}_ {F}(\omega^{k+1},x^{*})\right]$ $\displaystyle\leq\left(1-\frac{1}{32}\min\left\{b\sqrt{\frac{\mu}{nL}},\frac{ \sqrt{\mu}}{\chi\sqrt{L}}\right\}\right)(\Psi_{x}^{k}+\Psi_{yz}^{k})+\lambda(1 -p_{1})\mathrm{G}_{F}(\omega^{k},x^{*}).$ $$

Estimating $p_{1}$, using $\tau_{1}$ and $\tau_{0}$ definitions (11), (12)

$$ $\displaystyle p_{1}$ $\displaystyle=\frac{b}{n}\left(2\left(\frac{1}{2}+\frac{\overline{L}}{Lb\tau_{ 1}}\right)\right)^{-1}=\frac{b}{n}\left(1+\frac{2\overline{L}}{Lb\tau_{1}} \right)^{-1}\geq\frac{b}{2n}\min\left\{1,\left(\frac{2\overline{L}}{Lb\tau_{1} }\right)^{-1}\right\}=\min\left\{\frac{b}{2n},\frac{b^{2}L\tau_{1}}{4n \overline{L}}\right\}$ $\displaystyle\geq\min\left\{\frac{b}{2n},\frac{b^{2}L\tau_{2}}{10n\overline{L} }\right\}=\min\left\{\frac{b}{2n},\frac{b^{2}L}{10n\overline{L}}\min\left\{ \frac{1}{2},\max\left\{1,\frac{\sqrt{n}}{b}\right\}\sqrt{\frac{\mu}{L}}\right \}\right\}\geq\min\left\{\frac{b}{2n},\frac{b^{2}L}{20n\overline{L}},\frac{b^{ 2}L}{10n\overline{L}}\max\left\{1,\frac{\sqrt{n}}{b}\right\}\sqrt{\frac{\mu}{L }}\right\}$ $\displaystyle\geq\min\left\{\frac{b}{20n},\frac{b^{2}L}{10n\overline{L}}\sqrt{ \frac{\mu}{L}}\right\}.$ $$

Therefore we conclude

$$ $\displaystyle\mathbb{E}\left[\Psi_{x}^{k+1}+\Psi_{yz}^{k+1}+\lambda\mathrm{G}_ {F}(\omega^{k+1},x^{*})\right]$ $\displaystyle\leq\left(1-\frac{1}{32}\min\left\{\frac{b}{n},b\sqrt{\frac{\mu}{ nL}},\frac{b^{2}L}{n\overline{L}}\sqrt{\frac{\mu}{L}},\frac{\sqrt{\mu}}{\chi \sqrt{L}}\right\}\right)(\Psi_{x}^{k}+\Psi_{yz}^{k}+\lambda\mathrm{G}_{F}( \omega^{k},x^{*})).$ $$

This implies

$$ $\displaystyle\mathbb{E}\left[\Psi_{x}^{k}+\Psi_{yz}^{k}+\lambda\mathrm{G}_{F}( \omega^{k},x^{*})\right]$ $\displaystyle\leq\left(1-\frac{1}{32}\min\left\{\frac{b}{n},b\sqrt{\frac{\mu}{ nL}},\frac{b^{2}L}{n\overline{L}}\sqrt{\frac{\mu}{L}},\frac{\sqrt{\mu}}{\chi \sqrt{L}}\right\}\right)^{k}(\Psi_{x}^{0}+\Psi_{yz}^{0}+\lambda\mathrm{G}_{F}( x^{0},x^{*})).$ $$

Using $\Psi_{x}^{k}$ definition (16) we get

$$ $\displaystyle\mathbb{E}\left[\|x^{k}-x^{*}\|^{2}\right]$ $\displaystyle\leq\eta\mathbb{E}\left[\Psi_{x}^{k}\right]\leq\eta\mathbb{E} \left[\Psi_{x}^{k}+\Psi_{yz}^{k}+\lambda\mathrm{G}_{F}(\omega^{k},x^{*})\right]$ $\displaystyle\leq\left(1-\frac{1}{32}\min\left\{\frac{b}{n},b\sqrt{\frac{\mu}{ nL}},\frac{b^{2}L}{n\overline{L}}\sqrt{\frac{\mu}{L}},\frac{\sqrt{\mu}}{\chi \sqrt{L}}\right\}\right)^{k}\eta(\Psi_{x}^{0}+\Psi_{yz}^{0}+\lambda\mathrm{G}_ {F}(\omega^{0},x^{*})).$ $$

Choosing $C=\eta(\Psi_{x}^{0}+\Psi_{yz}^{0}+\lambda\mathrm{G}_{F}(\omega^{k},x^{*}))$ and using the number of iterations

$$ $k=32\max\left\{\frac{n}{b},\frac{\sqrt{n}}{b}\sqrt{\frac{L}{\mu}},\frac{n \overline{L}}{b^{2}L}\sqrt{\frac{L}{\mu}},\chi\sqrt{\frac{L}{\mu}}\right\}\log \frac{C}{\varepsilon}=\mathcal{O}\left(\max\left\{\frac{n}{b},\frac{\sqrt{n}}{ b}\sqrt{\frac{L}{\mu}},\frac{n\overline{L}}{b^{2}L}\sqrt{\frac{L}{\mu}},\chi \sqrt{\frac{L}{\mu}}\right\}\log\frac{1}{\varepsilon}\right)$ $$

we get

$$ $\|x^{k}-x^{*}\|^{2}\leq\epsilon.$ $$

Therefore the number of iterations of Algorithm (1) is bounded by

$$ $k=\mathcal{O}\left(\left(\frac{n}{b}+\frac{\sqrt{n}}{b}\sqrt{\frac{L}{\mu}}+ \frac{n\overline{L}}{b^{2}L}\sqrt{\frac{L}{\mu}}+\chi\sqrt{\frac{L}{\mu}} \right)\log\frac{1}{\epsilon}\right),$ $$

which concludes the proof.
∎

Let’s prove the Corollary 3.3.

###### Proof.

The choice of the number of communication iterations $\sim\chi$ per algorithm iteration and a specific choice of $b=\max\{\sqrt{n\overline{L}/L},n\sqrt{\mu/L}\}$ provides the following upper bound on the number of algorithm iterations:

$$ $N=\mathcal{O}\left(\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon}\right).$ $$

From this, it immediately follows that the upper bound on the number of communications is as follows:

$$ $\mathcal{O}\left(\chi\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon}\right).$ $$

Now, let’s estimate the number of oracle calls at each node. It is not difficult to show the following upper bound:

$$ $Nb=\mathcal{O}\left(\left(n+\sqrt{n}\sqrt{\frac{L}{\mu}}+b\sqrt{\frac{L}{\mu}} +\frac{n\overline{L}}{bL}\sqrt{\frac{L}{\mu}}\right)\log\frac{1}{\epsilon} \right)=\mathcal{O}\left(\left(n+\sqrt{n}\sqrt{\frac{\overline{L}}{\mu}}\right )\log\frac{1}{\epsilon}\right),$ $$

which completes the proof.

∎

###### Lemma A.1 .

###### Proof.

###### Lemma A.2 .

###### Proof.

###### Lemma A.3 .

###### Proof.

###### Lemma A.4 .

###### Proof.

###### Lemma A.5 .

###### Proof.

###### Lemma A.6 .

###### Proof.

###### Lemma A.7 .

###### Proof.

###### Lemma A.8 .

###### Proof.

###### Lemma A.9 .

###### Proof.

###### Lemma A.10 .

###### Proof.

###### Proof.

## Appendix B Proof of Theorem 4.3

As our graph counterexample, we will use the graph from Metelev et al., () because it allows us to obtain a lower bound not only in the setting of “changing graphs” but also in the setting of “slowly changing graphs”, which will be a good addition.

Let’s define $T_{a,b}$ as a graph consisting of two “stars” with sizes $a+1$ and $b+1$, whose centers are connected to an isolated vertex. In total, the graph will have $a+b+3$ vertices.

Let’s say the left part of the graph $\mathcal{P}_{1}$ is the set of $a+1$ vertices of the first star, and the right part $\mathcal{P}_{2}$ is correspondingly the set of $b+1$ vertices of the second star. The middle vertex $v_{m}$ is the vertex connected to the centers $v_{l}$ and $v_{r}$ of the left and right stars, respectively.

If $v\in\mathcal{P}_{1}$, we define the “hop to the right” operation as follows: remove the edge $(v_{l},v_{m})$ and add the edge $(v,v_{r})$. As a result, $v_{m}$ ceases to be the middle vertex, being replaced by the vertex $v$. The operation “hop to the left” is defined in the same way.

Now, let’s describe the sequence of graphs that will make up the changing network. The first graph will be of the form $T_{0,m-3}$, followed by a series of “hops to the left”, which increase the left part $\mathcal{P}_{1}$ of the graph and decrease the right. This will continue until the graph $T_{m-3,0}$ appears. After this, a series of “hops to the right” occur until the network returns to its original form. Then, the cycle repeats.

###### Lemma B.1 .

For this sequence of graphs, there exists a corresponding sequence of positive weights $(A_{k})_{k=0}^{\infty}$ and a sequence of Laplacian matrices $(W(k))_{k=0}^{\infty}$ for these weighted graphs, such that it satisfies 2.5 with

$$ $\chi\leq 8m.$ (40) $$

###### Proof.

This is a direct consequence of Lemma 8 from Metelev et al., ().
∎

Note that vertices $v_{l}$ and $v_{r}$ in the process of changing the network are always on the left and right parts, respectively. Denote by $\{g_{i}\}_{i=1}^{m}$:$y\in$ $\ell_{2}\rightarrow\mathbb{R}$ the set of auxiliary functions corresponding to the vertices:

$$ $g_{i}(y)=\begin{cases}\frac{\mu}{2}\|y\|^{2}+\frac{(L-\mu)}{4}\left[(y_{1}-1)^ {2}+\sum_{k=1}^{\infty}(y_{2k}-y_{2k+1})^{2}\right],&i=v_{l},\\ \frac{\mu}{2}\|y\|^{2}+\frac{(L-\mu)}{4}\sum_{k=1}^{\infty}(y_{2k-1}-y_{2k})^{ 2},&i=v_{r},\\ \frac{\mu}{2(m-2)}\|y\|^{2},&i\not\in\{v_{l},v_{r}\}.\end{cases}$ (41) $$

Let’s describe the local functions on the nodes: let $x\in\ell_{2}^{n}$, then define $f_{ij}(x)=g_{i}(x_{j})$, where $x_{j}\in\ell_{2}$. Accordingly, it turns out that $f_{ij}:x\in\ell_{2}^{n}\rightarrow\mathbb{R}$, but its gradient affects only the $j$th subspace of $\ell_{2}^{n}$, in which $x_{k}=0$ for $k\neq j$. Hence, $F_{i}(x)=\frac{1}{n}\sum_{j=1}^{n}g_{i}(x_{j})$.

Such a structure allows achieving that the “transfer” of the gradient to the next dimension in each subspace occurs once every $\Omega(m)=\Omega(\chi)$ communication iterations.

The solution to this optimization problem will be the vector $(x^{*},\ldots,x^{*})\in\ell_{2}^{n}$, $x^{*}=(1,q,q^{2},\ldots)\in\ell_{2}$, $q=\frac{\sqrt{\frac{2}{3}L/\mu+\frac{1}{3}}-1}{\sqrt{\frac{2}{3}L/\mu+1}+\frac
{1}{3}}$ .

Let $(e_{1},e_{2},\ldots,e_{n})$ be sets of vectors that form a basis in the space $\ell_{2}^{n}$. Let $x_{ij}$ denote the coordinates along a set of vectors $e_{j}$ on the variable on the $i$th node.

Following the ideas of Hendrikx et al., (), consider the expression

$$ $\displaystyle A\overset{\Delta}{=}\sum_{i=1}^{m}\sum_{j=1}^{n}\|x_{ij}-x^{*}\| ^{2}.$ $$

Let’s define the quantities $k_{j}=\min\{k\in\mathbb{N}_{0}|\forall l\geq k,\forall i\in\{1,\ldots,m\}
\rightarrow x_{ijl}=0\}$. Using this definition and the convexity of $q^{2x}$ we get

$$ $A\geq\frac{m}{1-q^{2}}\sum_{i=1}^{n}q^{2k_{j}}\geq\frac{nm}{1-q^{2}}q^{\frac{2 }{n}\sum_{j=1}^{n}k_{j}}.$ (42) $$

Let $T_{c}$ and $T_{s}$ be the number of communication rounds and the number of oracle calls at node $v_{l}$, respectively. Between the network state $T_{0,m-3}$ and the next such state there are $2m-6$ communication iterations, during which two “transfers” of the gradient from an odd position to an even one cannot occur. Therefore we get

$$ $k_{j}\leq 1+\frac{T_{c}}{m-3}.$ (43) $$

Note that each $j$ corresponds to at least $\lceil k_{j}/2\rceil$ oracle calls to the function $f_{ij}$ for $i=v_{l}$, hence we get

$$ $\sum_{j=1}^{n}k_{j}\leq 2T_{s}.$ (44) $$

Using (42), (43) and (44) we get

$$ $A\geq\frac{nm}{1-q^{2}}\max\left\{\left(1-\frac{2}{\sqrt{\frac{2}{3}L/\mu+ \frac{1}{3}}+1}\right)^{2+2t_{c}/(m-3)},\left(1-\frac{2}{\sqrt{\frac{2}{3}L/ \mu+\frac{1}{3}}+1}\right)^{4t_{s}/n}\right\}.$ (45) $$

Based on the form of the function we can conclude that $\kappa_{s}=\frac{nL}{\mu}=n\kappa_{b}$, then using $x^{0}=0$, $\|x^{0}_{ij}-x^{*}_{ij}\|^{2}=(1-q^{2})^{-1}$ and (40) we get

$$ $\displaystyle\frac{1}{nm}\sum_{i=1}^{m}\sum_{j=1}^{n}\frac{\|x_{ij}-x^{*}\|^{2 }}{\|x^{0}_{ij}-x^{*}\|^{2}}\geq\max\left\{\left(1-\frac{2}{\sqrt{\frac{2}{3} \kappa_{b}+\frac{1}{3}}+1}\right)^{2+16t_{c}/(\chi-24)},\left(1-\frac{2n}{ \sqrt{n}\sqrt{\frac{2}{3}\kappa_{s}+n/3}+n}\right)^{4t_{s}/n}\right\},$ $$

which concludes the proof.

###### Lemma B.1 .

###### Proof.

## Appendix C Proofs for Algorithm 2

Before we start, let us denote

$$ $\displaystyle\mathbf{M}(k)=(\mathbf{I}_{m}-\mathbf{W}(k))\otimes\mathbf{I}_{d}$ (46) $$

and

$$ $\displaystyle\rho=\frac{1}{\chi}$ (47) $$

for the convenient analysis. Moreover, we need to introduce some definitions as

$$ $\displaystyle\bar{x}^{k}$ $\displaystyle=\frac{1}{m}({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})x^{k},$ $\displaystyle\bar{v}^{k}$ $\displaystyle=\frac{1}{m}({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})v^{k},$ $\displaystyle S^{k}$ $\displaystyle=(S_{1}^{k},\ldots,S_{m}^{k}),$ $\displaystyle\nabla_{S^{k}}F(x^{k})$ $\displaystyle=\big{(}\nabla_{S_{1}^{k}}F_{1}(x_{1}^{k}),\ldots,\nabla_{S_{m}^{ k}}F_{m}(x_{m}^{k})\big{)}\in\mathbb{R}^{md},$ $\displaystyle\nabla_{S_{i}^{k}}F_{i}(x_{i}^{k})$ $\displaystyle=\frac{1}{b}\sum\limits_{j\in S^{k}_{i}}\nabla f_{ij}(x_{i}^{k})$ $$

Also we need to formulate some useful propositions:

###### Proposition C.1 .

If $\bar{v}^{0}=\frac{1}{m}({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})y^{0}$, then for any $k\geq 1$, according to Algorithm 2, we get

$$ $\bar{v}^{k}=\frac{1}{m}({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})y^{k},$ (48) $$

and

$$ $\bar{x}^{k+1}=\bar{x}^{k}-\frac{\eta}{m}({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_ {d})y^{k}.$ (49) $$

###### Proof.

We prove it using the induction. For $k=0$ it is trivial because of start point. Now suppose that at the $k$-th iteration, the relation (48) is true:

$$ $\bar{v}^{k}=\frac{1}{m}({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})y^{k}.$ $$

Hence, at the $(k+1)$-th iteration, we have

$$ $\displaystyle\bar{v}^{k+1}$ $\displaystyle=\frac{1}{m}({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})v^{k+1}$ $\displaystyle=\frac{1}{m}({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})v^{k}+\frac {1}{m}({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})(\mathbf{M}(k)-\mathbf{I}_{md} )v^{k}+\frac{1}{m}({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})\left(y^{k+1}-y^{k }\right)$ $\displaystyle=\frac{1}{m}({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})v^{k}+\frac {1}{m}({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})\left(y^{k+1}-y^{k}\right)$ $\displaystyle=\frac{1}{m}({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})y^{k+1},$ $$

where the third line follows from 2.5:

$$ $\displaystyle({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})(\mathbf{M}(k)-\mathbf{ I}_{md})=-({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})(\mathbf{W}(k)\otimes \mathbf{I}_{d})=-({\bm{1}}^{\top}_{m}\mathbf{W}(k)\otimes\mathbf{I}_{d})=0.$ $$

Thus, we complete the proof of (48).
For (49),

$$ $\displaystyle\bar{x}^{k+1}$ $\displaystyle=\bar{x}^{k}+\frac{1}{m}({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d} )(\mathbf{M}(k)-\mathbf{I}_{md})x^{k}-\frac{\eta}{m}({\bm{1}}^{\top}_{m} \otimes\mathbf{I}_{d})v^{k}$ $\displaystyle=\bar{x}^{k}-\eta\bar{v}^{k}=\bar{x}^{k}-\frac{\eta}{m}({\bm{1}}^ {\top}_{m}\otimes\mathbf{I}_{d})y^{k}.$ $$

∎

###### Proposition C.2 .

If $\mathbf{W}(k)$ satisfy 2.5 and $\mathbf{M}(k)$ is taken from (46), then $\forall x\in\mathbb{R}^{md}$, we have

$$ $\displaystyle\|\mathbf{M}(k)x-\frac{1}{m}({\bm{1}}_{m}\otimes\mathbf{I}_{d})({ \bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})x\|^{2}\leq(1-\rho)\|x-\frac{1}{m}({ \bm{1}}_{m}\otimes\mathbf{I}_{d})({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})x\| ^{2},$ (50) $$

###### Proof.

Note that

$$ $\displaystyle\mathbf{M}(k)({\bm{1}}_{m}\otimes\mathbf{I}_{d})=((\mathbf{I}_{m} -\mathbf{W}(k))\otimes\mathbf{I}_{d})({\bm{1}}_{m}\otimes\mathbf{I}_{d})=(( \mathbf{I}_{m}-\mathbf{W}(k)){\bm{1}}_{m}\otimes\mathbf{I}_{d})={\bm{1}}_{m} \otimes\mathbf{I}_{d}.$ $$

Therefore,

$$ $\displaystyle\|\mathbf{M}(k)x-\frac{1}{m}({\bm{1}}_{m}\otimes\mathbf{I}_{d})({ \bm{1}}^{\top}_{m}\otimes\mathbf{I}_{d})x\|^{2}=\|\mathbf{M}(k)\left(x-\frac{1 }{m}({\bm{1}}_{m}\otimes\mathbf{I}_{d})({\bm{1}}^{\top}_{m}\otimes\mathbf{I}_{ d})x\right)\|^{2}.$ $$

Decomposing $x-\frac{1}{m}({\bm{1}}_{m}\otimes\mathbf{I}_{d})({\bm{1}}^{\top}_{m}\otimes
\mathbf{I}_{d})x$ by eigenvectors of $\mathbf{M}(k)$ and using that

$$ $\displaystyle{\bm{1}}_{md}^{\top}\left(\mathbf{I}_{md}-\frac{1}{m}({\bm{1}}_{m }{\bm{1}}_{m}^{\top}\otimes\mathbf{I}_{d})\right)=0,$ $$

we claim the final result.

###### Remark C.3 .

The proposition above is equivalent to

$$ $\displaystyle\|\mathbf{M}(k)x^{k}-({\bm{1}}_{m}\otimes\mathbf{I}_{d})\bar{x}^{ k}\|^{2}\leq(1-\rho)\|x^{k}-({\bm{1}}_{m}\otimes\mathbf{I}_{d})\bar{x}^{k}\|^{ 2}.$ $$

∎

###### Proposition C.1 .

###### Proof.

###### Proposition C.2 .

###### Proof.

###### Remark C.3 .

### C.1 Descent lemma

###### Lemma C.4 .

(Descent lemma)
Let 2.2 and 2.5 hold. Then, after $k$ iterations of Algorithm 2, we get

$$ $\displaystyle\mathbb{E}F(\bar{x}^{k+1})$ $\displaystyle\leq\mathbb{E}F(\bar{x}^{k})-\frac{\eta}{2}\mathbb{E}\|\nabla F( \bar{x}^{k})\|^{2}+\frac{\eta}{m}\mathbb{E}\|\nabla F(x^{k})-y^{k}\|^{2}+\frac {\eta L^{2}}{m}\mathbb{E}\|x^{k}-({\bm{1}}_{m}\otimes\mathbf{I}_{d})\bar{x}^{k }\|^{2}$ $\displaystyle-\left(\frac{\eta}{2}-\frac{\eta^{2}L}{2}\right)\mathbb{E}\|\bar{ v}^{k}\|^{2}.$ (51) $$

###### Proof.

Starting with $L$-smoothness:

$$ $\displaystyle F(\bar{x}^{k+1})$ $\displaystyle\leq F(\bar{x}^{k})-\eta\left<\bar{v}^{k},\nabla F(\bar{x}^{k}) \right>+\frac{\eta^{2}L}{2}\|\bar{v}^{k}\|^{2}$ $\displaystyle=F(\bar{x}^{k})-\frac{\eta}{2}\|\nabla F(\bar{x}^{k})\|^{2}-\frac {\eta}{2}\|\bar{v}^{k}\|^{2}+\frac{\eta}{2}\|\nabla F(\bar{x}^{k})-\bar{v}^{k} \|^{2}+\frac{\eta^{2}L}{2}\|\bar{v}^{k}\|^{2}$ $\displaystyle=F(\bar{x}^{k})-\frac{\eta}{2}\|\nabla F(\bar{x}^{k})\|^{2}+\frac {\eta}{2}\|\nabla F(\bar{x}^{k})-\bar{v}^{k}\|^{2}-\left(\frac{\eta}{2}-\frac{ \eta^{2}L}{2}\right)\|\bar{v}^{k}\|^{2}$ $\displaystyle\leq F(\bar{x}^{k})-\frac{\eta}{2}\|\nabla F(\bar{x}^{k})\|^{2}+ \frac{\eta}{2}\|\nabla F(\bar{x}^{k})-\frac{1}{m}({\bm{1}}^{\top}_{m}\otimes \mathbf{I}_{d})y^{k}\|^{2}-\left(\frac{\eta}{2}-\frac{\eta^{2}L}{2}\right)\| \bar{v}^{k}\|^{2}$ $\displaystyle\leq F(\bar{x}^{k})-\frac{\eta}{2}\|\nabla F(\bar{x}^{k})\|^{2}+ \frac{\eta}{2m}\|({\bm{1}}_{m}\otimes\mathbf{I}_{d})\nabla F(\bar{x}^{k})- \nabla F(x^{k})+\nabla F(x^{k})-y^{k}\|^{2}$ $\displaystyle-\left(\frac{\eta}{2}-\frac{\eta^{2}L}{2}\right)\|\bar{v}^{k}\|^{2}$ $\displaystyle\leq F(\bar{x}^{k})-\frac{\eta}{2}\|\nabla F(\bar{x}^{k})\|^{2}+ \frac{\eta}{m}\|\nabla F(x^{k})-y^{k}\|^{2}+\frac{\eta L^{2}}{m}\|x^{k}-({\bm{ 1}}_{m}\otimes\mathbf{I}_{d})\bar{x}^{k}\|^{2}$ $\displaystyle-\left(\frac{\eta}{2}-\frac{\eta^{2}L}{2}\right)\|\bar{v}^{k}\|^{ 2},$ (52) $$

where in the last inequality we use $(a+b)^{2}\leq 2a^{2}+2b^{2}$. Taking the expectation, we claim the final result.
∎

###### Lemma C.4 .

###### Proof.

### C.2 Auxiliary lemmas

###### Lemma C.5 .

Let 2.3 holds. Hence, after $k$ iterations the following is fulfilled:

$$ $\displaystyle\mathbb{E}\|\nabla F(x^{k+1})-y^{k+1}\|^{2}\leq(1-p)\mathbb{E}\| \nabla F(x^{k})-y^{k}\|^{2}+\frac{(1-p)\hat{L}^{2}}{b}\mathbb{E}\|x^{k+1}-x^{k }\|^{2}.$ $$

###### Proof.

$$ $\displaystyle\mathbb{E}$ $\displaystyle\|\nabla F(x^{k+1})-y^{k+1}\|^{2}=p\mathbb{E}\|\nabla F(x^{k+1})- \nabla F(x^{k+1})\|^{2}$ $\displaystyle+(1-p)\mathbb{E}\|\nabla F(x^{k+1})-y^{k}-\nabla_{S^{k}}F(x^{k+1} )+\nabla_{S^{k}}F(x^{k})\|^{2}$ $\displaystyle=(1-p)\mathbb{E}\|\nabla F(x^{k+1})-\nabla F(x^{k})+\nabla F(x^{k })-y^{k}-\nabla_{S^{k}}F(x^{k+1})+\nabla_{S^{k}}F(x^{k})\|^{2}$ $\displaystyle=(1-p)\mathbb{E}\|\nabla F(x^{k+1})-\nabla F(x^{k})-\nabla_{S^{k} }F(x^{k+1})+\nabla_{S^{k}}F(x^{k})\|^{2}$ $\displaystyle+(1-p)\mathbb{E}\|\nabla F(x^{k})-y^{k}\|^{2},$ (53) $$

Rewriting $\nabla_{S^{k}}F(x)$ as claimed before, using that $\mathbb{E}\|X-\mathbb{E}X\|^{2}\leq\mathbb{E}\|X\|^{2}$, clarifying that indices in one batch are chosen independently and using the $\hat{L}$-average smoothness, one can obtain

$$ $\displaystyle\mathbb{E}\|\nabla F(x^{k+1})-y^{k+1}\|^{2}\leq(1-p)\mathbb{E}\| \nabla F(x^{k})-y^{k}\|^{2}+\frac{(1-p)\hat{L}^{2}}{b}\mathbb{E}\|x^{k+1}-x^{k }\|^{2},$ (54) $$

what ends the proof.
∎

###### Remark C.6 .

The proof is similar to the proof of Lemma 3 in Li et al., (), but we write it for each node in the same time.

Now we need to bound some extra terms for our Lyapunov’s function. We use the next notation

$$ $\displaystyle\Omega_{1}^{k}$ $\displaystyle=\mathbb{E}\|x^{k}-({\bm{1}}_{m}\otimes\mathbf{I}_{d})\bar{x}^{k} \|^{2},$ $\displaystyle\Omega_{2}^{k}$ $\displaystyle=\mathbb{E}\|v^{k}-({\bm{1}}_{m}\otimes\mathbf{I}_{d})\bar{v}^{k} \|^{2}.$ $$

###### Lemma C.7 .

Let 2.5 holds. Therefore, for the Algorithm 2, we have

$$ $\displaystyle\Omega_{1}^{k+1}$ $\displaystyle\leq\left(1-\frac{\rho}{2}\right)\Omega_{1}^{k}+\frac{3\eta^{2}}{ \rho}\Omega_{2}^{k},$ $\displaystyle\Omega_{2}^{k+1}$ $\displaystyle\leq\left(1-\frac{\rho}{2}\right)\Omega_{2}^{k}+\frac{3}{\rho} \mathbb{E}\|y^{k+1}-y^{k}\|^{2}.$ $$

###### Proof.

Substituting the iteration of Algorithm 2 into $\Omega_{1}^{k+1}$, we get

$$ $\displaystyle\|x^{k+1}-({\bm{1}}_{m}\otimes\mathbf{I}_{d})\bar{x}^{k+1}\|^{2}$ $\displaystyle=\|\mathbf{M}(k)x^{k}-\eta v^{k}-({\bm{1}}_{m}\otimes\mathbf{I}_{ d})\bar{x}^{k}+({\bm{1}}_{m}\otimes\mathbf{I}_{d})\eta\bar{v}^{k}\|^{2}$ $\displaystyle\leq(1+\beta)(1-\rho)\|x^{k}-({\bm{1}}_{m}\otimes\mathbf{I}_{d}) \bar{x}^{k}\|^{2}+\left(1+\frac{1}{\beta}\right)\eta^{2}\|v^{k}-({\bm{1}}_{m} \otimes\mathbf{I}_{d})\bar{v}^{k}\|^{2}$ $\displaystyle\leq\left(1-\frac{\rho}{2}\right)\|x^{k}-({\bm{1}}_{m}\otimes \mathbf{I}_{d})\bar{x}^{k}\|^{2}+\left(1+\frac{2}{\rho}\right)\eta^{2}\|v^{k}- ({\bm{1}}_{m}\otimes\mathbf{I}_{d})\bar{v}^{k}\|^{2}$ $\displaystyle\leq\left(1-\frac{\rho}{2}\right)\|x^{k}-({\bm{1}}_{m}\otimes \mathbf{I}_{d})\bar{x}^{k}\|^{2}+\frac{3\eta^{2}}{\rho}\|v^{k}-({\bm{1}}_{m} \otimes\mathbf{I}_{d})\bar{v}^{k}\|^{2},$ (55) $$

where we choose $\beta=\frac{\rho}{2}$. For $\Omega_{2}^{k+1}$ respectively

$$ $\displaystyle\|v^{k+1}-({\bm{1}}_{m}\otimes\mathbf{I}_{d})\bar{v}^{k+1}\|^{2}$ $\displaystyle=\|v^{k+1}-({\bm{1}}_{m}\otimes\mathbf{I}_{d})\bar{v}^{k}+({\bm{1 }}_{m}\otimes\mathbf{I}_{d})\bar{v}^{k}-({\bm{1}}_{m}\otimes\mathbf{I}_{d}) \bar{v}^{k+1}\|^{2}$ $\displaystyle=\|v^{k+1}-({\bm{1}}_{m}\otimes\mathbf{I}_{d})\bar{v}^{k}\|^{2}-m \|\bar{v}^{k+1}-\bar{v}^{k}\|^{2}$ $\displaystyle\leq\|v^{k+1}-({\bm{1}}_{m}\otimes\mathbf{I}_{d})\bar{v}^{k}\|^{2}.$ $$

Thus by the update rule of Algorithm 2, one can obtain

$$ $\displaystyle\|v^{k+1}-({\bm{1}}_{m}\otimes\mathbf{I}_{d})\bar{v}^{k+1}\|^{2}$ $\displaystyle\leq\|v^{k+1}-({\bm{1}}_{m}\otimes\mathbf{I}_{d})\bar{v}^{k}\|^{2}$ $\displaystyle=\|\mathbf{M}(k)v^{k}+y^{k+1}-y^{k}-({\bm{1}}_{m}\otimes\mathbf{I }_{d})\bar{v}^{k}\|^{2}$ $\displaystyle\leq\left(1-\frac{\rho}{2}\right)\|v^{k}-({\bm{1}}_{m}\otimes \mathbf{I}_{d})\bar{v}^{k}\|^{2}+\left(1+\frac{2}{\rho}\right)\|y^{k+1}-y^{k} \|^{2}$ $\displaystyle\leq\left(1-\frac{\rho}{2}\right)\|v^{k}-({\bm{1}}_{m}\otimes \mathbf{I}_{d})\bar{v}^{k}\|^{2}+\frac{3}{\rho}\|y^{k+1}-y^{k}\|^{2}.$ (56) $$

Taking the expectation in both bounds, we claim the final result.
∎

As a consequence of Lemma C.5 and Lemma C.7, we need to bound some redundant expressions.

###### Lemma C.8 .

Let Assumptions 2.2, 2.3 and 2.5 hold. Then, after $k$ iterations of Algorithm 2, we get

$$ $\displaystyle\mathbb{E}\|y^{k+1}-y^{k}\|^{2}$ $\displaystyle\leq(1+p)\hat{L}^{2}\mathbb{E}\|x^{k+1}-x^{k}\|^{2}+2p\mathbb{E} \|\nabla F(x^{k})-y^{k}\|^{2},$ $\displaystyle\mathbb{E}\|x^{k+1}-x^{k}\|^{2}$ $\displaystyle\leq 2\widetilde{C}\mathbb{E}\|x^{k}-({\bm{1}}_{m}\otimes\mathbf{ I}_{d})\bar{x}^{k}\|^{2}+2\eta^{2}\mathbb{E}\|v^{k}-({\bm{1}}_{m}\otimes \mathbf{I}_{d})\bar{v}^{k}\|^{2}+2\eta^{2}m\mathbb{E}\|\bar{v}^{k}\|^{2},$ $$

where $\widetilde{C}=\max_{k}\|\mathbf{M}(k)-\mathbf{I}_{md}\|^{2}=\max_{k}\sigma_{
\max}(\mathbf{M}(k)-\mathbf{I}_{md})^{2}\leq 4$.

###### Proof.

Start with substituting $y^{k+1}$:

$$ $\displaystyle\mathbb{E}\|y^{k+1}-y^{k}\|^{2}$ $\displaystyle=p\mathbb{E}\|\nabla F(x^{k+1})-y^{k}\|^{2}+(1-p)\mathbb{E}\| \nabla_{S^{k}}F(x^{k+1})-\nabla_{S^{k}}F(x^{k})\|^{2}$ $\displaystyle=p\mathbb{E}\|\nabla F(x^{k+1})-\nabla F(x^{k})+\nabla F(x^{k})-y ^{k}\|^{2}$ $\displaystyle+(1-p)\mathbb{E}\|\nabla_{S^{k}}F(x^{k+1})-\nabla_{S^{k}}F(x^{k}) \|^{2}$ $\displaystyle\leq p(1+\beta)L^{2}\mathbb{E}\|x^{k+1}-x^{k}\|^{2}+p\left(1+ \frac{1}{\beta}\right)\mathbb{E}\|\nabla F(x^{k})-y^{k}\|^{2}$ $\displaystyle+(1-p)\mathbb{E}\|\nabla_{S^{k}}F(x^{k+1})-\nabla_{S^{k}}F(x^{k}) \|^{2}.$ (57) $$

Let us bound the last term in (C.2). We have

$$ $\displaystyle\mathbb{E}\|\nabla_{S^{k}}F(x^{k+1})-\nabla_{S^{k}}F(x^{k})\|^{2}$ $\displaystyle=\mathbb{E}\sum\limits_{i=1}^{m}\|\nabla_{S_{i}^{k}}F_{i}(x_{i}^{ k+1})-\nabla_{S_{i}^{k}}F_{i}(x_{i}^{k})\|^{2}$ $\displaystyle=\mathbb{E}\sum\limits_{i=1}^{m}\|\frac{1}{b}\sum\limits_{\ell\in \{S_{i}^{k}\}}\nabla f_{i\ell}(x_{i}^{k+1})-\nabla f_{i\ell}(x_{i}^{k})\|^{2}$ $\displaystyle=\mathbb{E}\sum\limits_{i=1}^{m}\frac{1}{b^{2}}\|\sum\limits_{ \ell\in\{S_{i}^{k}\}}\nabla f_{i\ell}(x_{i}^{k+1})-\nabla f_{i\ell}(x_{i}^{k}) \|^{2}$ $\displaystyle\leq\mathbb{E}\sum\limits_{i=1}^{m}\frac{1}{b}\sum\limits_{\ell \in\{S_{i}^{k}\}}\|\nabla f_{i\ell}(x_{i}^{k+1})-\nabla f_{i\ell}(x_{i}^{k})\| ^{2}$ $\displaystyle\leq\mathbb{E}\sum\limits_{i=1}^{m}\frac{\hat{L}^{2}}{b}\sum \limits_{\ell\in\{S_{i}^{k}\}}\|x_{i}^{k+1}-x_{i}^{k}\|^{2}$ $\displaystyle=\mathbb{E}\sum\limits_{i=1}^{m}\hat{L}^{2}\|x_{i}^{k+1}-x_{i}^{k }\|^{2}$ $\displaystyle=\hat{L}^{2}\mathbb{E}\|x^{k+1}-x^{k}\|^{2}.$ (58) $$

Hence, substituting (C.2) into (C.2), choosing $\beta$ as $1$ and using $L\leq\hat{L}$ (because of Jensen’s inequality), one can obtain

$$ $\displaystyle\mathbb{E}\|y^{k+1}-y^{k}\|^{2}\leq(1+p)\hat{L}^{2}\mathbb{E}\|x^ {k+1}-x^{k}\|^{2}+2p\mathbb{E}\|\nabla F(x^{k})-y^{k}\|^{2}.$ (59) $$

The second expression can be bounded in the following way:

$$ $\displaystyle\|x^{k+1}-x^{k}\|^{2}$ $\displaystyle=\|(\mathbf{M}(k)-\mathbf{I}_{md})x^{k}-\eta v^{k}\|^{2}$ $\displaystyle=\|(\mathbf{M}(k)-\mathbf{I}_{md})(x^{k}-({\bm{1}}_{m}\otimes \mathbf{I}_{d})\bar{x}^{k})-\eta v^{k}\|^{2}$ $\displaystyle\leq 2\widetilde{C}\|x^{k}-({\bm{1}}_{m}\otimes\mathbf{I}_{d}) \bar{x}^{k}\|^{2}+2\eta^{2}\|v^{k}\|^{2}$ $\displaystyle=2\widetilde{C}\|x^{k}-({\bm{1}}_{m}\otimes\mathbf{I}_{d})\bar{x} ^{k}\|^{2}+2\eta^{2}\|v^{k}-({\bm{1}}_{m}\otimes\mathbf{I}_{d})\bar{v}^{k}\|^{ 2}+2\eta^{2}m\|\bar{v}^{k}\|^{2}.$ (60) $$

Taking the expectation, we claim the final result.
∎

Now we denote some expressions from Lemma C.5 and Lemma C.8 as follows

$$ $\displaystyle\Delta^{k}$ $\displaystyle=\mathbb{E}\|\nabla F(x^{k})-y^{k}\|^{2},$ $\displaystyle\Delta_{x}^{k}$ $\displaystyle=\mathbb{E}\|x^{k+1}-x^{k}\|^{2}.$ $$

Consequently, substituting the bound of a first expression from Lemma C.8 in Lemma C.7, we get

$$ $\displaystyle\Omega_{1}^{k+1}$ $\displaystyle\leq\left(1-\frac{\rho}{2}\right)\Omega_{1}^{k}+\frac{3\eta^{2}}{ \rho}\Omega_{2}^{k},$ $\displaystyle\Omega_{2}^{k+1}$ $\displaystyle\leq\left(1-\frac{\rho}{2}\right)\Omega_{2}^{k}+\frac{3}{\rho}(2p \Delta^{k}+(1+p)\hat{L}^{2}\Delta_{x}^{k}).$ (61) $$

Moreover, we can write

$$ $\displaystyle\Delta^{k+1}$ $\displaystyle\leq(1-p)\Delta^{k}+\frac{(1-p)\hat{L}^{2}}{b}\Delta_{x}^{k},$ $\displaystyle\Delta_{x}^{k}$ $\displaystyle\leq 2\widetilde{C}\Omega_{1}^{k}+2\eta^{2}\Omega_{2}^{k}+2\eta^{ 2}m\mathbb{E}\|\bar{v}^{k}\|^{2}.$ $$

###### Lemma C.5 .

###### Proof.

###### Remark C.6 .

###### Lemma C.7 .

###### Proof.

###### Lemma C.8 .

###### Proof.

### C.3 Proof of Theorem 3.4

###### Proof.

Rewriting the descent lemma in new notation, we have

$$ $\displaystyle\mathbb{E}F(\bar{x}^{k+1})\leq\mathbb{E}F(\bar{x}^{k})-\frac{\eta }{2}\mathbb{E}\|\nabla F(\bar{x}^{k})\|^{2}+\frac{\eta}{m}\Delta^{k}+\frac{ \eta L^{2}}{m}\Omega_{1}^{k}-\left(\frac{\eta}{2}-\frac{\eta^{2}L}{2}\right) \mathbb{E}\|\bar{v}^{k}\|^{2}.$ $$

Also we can construct a Lyapunov’s function in the following way:

$$ $\displaystyle\Phi_{k}=\mathbb{E}F(\bar{x}^{k})-F^{*}+C_{0}\Delta^{k}+s_{1} \Omega_{1}^{k}+s_{2}\Omega_{2}^{k}.$ (62) $$

Then, adding some terms to the left-hand side of descent lemma mentioned above, one can obtain

$$ $\displaystyle\Phi_{k+1}$ $\displaystyle=\mathbb{E}F(\bar{x}^{k+1})-F^{*}+C_{0}\Delta^{k+1}+s_{1}\Omega_{ 1}^{k+1}+s_{2}\Omega_{2}^{k+1}$ $\displaystyle\leq\mathbb{E}F(\bar{x}^{k})-F^{*}-\frac{\eta}{2}\mathbb{E}\| \nabla F(\bar{x}^{k})\|^{2}+\frac{\eta}{m}\Delta^{k}+\frac{\eta L^{2}}{m} \Omega_{1}^{k}-\left(\frac{\eta}{2}-\frac{\eta^{2}L}{2}\right)\mathbb{E}\|\bar {v}^{k}\|^{2}$ $\displaystyle+C_{0}\left((1-p)\Delta^{k}+\frac{(1-p)\hat{L}^{2}}{b}\Delta_{x}^ {k}\right)+s_{1}\left(\left(1-\frac{\rho}{2}\right)\Omega_{1}^{k}+\frac{3\eta^ {2}}{\rho}\Omega_{2}^{k}\right)$ $\displaystyle+s_{2}\left(\left(1-\frac{\rho}{2}\right)\Omega_{2}^{k}+\frac{3}{ \rho}(2p\Delta^{k}+(1+p)\hat{L}^{2}\Delta_{x}^{k})\right).$ $$

Grouping the terms, we get

$$ $\displaystyle\Phi_{k+1}$ $\displaystyle\leq\mathbb{E}F(\bar{x}^{k})-F^{*}-\frac{\eta}{2}\mathbb{E}\| \nabla F(\bar{x}^{k})\|^{2}+\Delta^{k}\left((1-p)C_{0}+\frac{\eta}{m}+\frac{6 ps_{2}}{\rho}\right)$ $\displaystyle+\Omega_{1}^{k}\left(\frac{\eta L^{2}}{m}+\left(1-\frac{\rho}{2} \right)s_{1}\right)+\Omega_{2}^{k}\left(\frac{3\eta^{2}s_{1}}{\rho}+\left(1- \frac{\rho}{2}\right)s_{2}\right)$ $\displaystyle+\Delta_{x}^{k}\left(\frac{(1-p)\hat{L}^{2}C_{0}}{b}+\frac{3(1+p) \hat{L}^{2}s_{2}}{\rho}\right)-\left(\frac{\eta}{2}-\frac{\eta^{2}L}{2}\right) \mathbb{E}\|\bar{v}^{k}\|^{2}.$ (63) $$

Hence, denoting

$$ $\displaystyle A$ $\displaystyle=(1-p)C_{0}+\frac{\eta}{m}+\frac{6ps_{2}}{\rho},$ $\displaystyle B$ $\displaystyle=\frac{(1-p)\hat{L}^{2}C_{0}}{b}+\frac{3(1+p)\hat{L}^{2}s_{2}}{ \rho},$ $\displaystyle C$ $\displaystyle=\frac{\eta L^{2}}{m}+\left(1-\frac{\rho}{2}\right)s_{1},$ $\displaystyle D$ $\displaystyle=\frac{3\eta^{2}s_{1}}{\rho}+\left(1-\frac{\rho}{2}\right)s_{2},$ $$

and substituting these constants into (C.3), we get

$$ $\displaystyle\Phi_{k+1}\leq\mathbb{E}F(\bar{x}^{k})-F^{*}-\frac{\eta}{2} \mathbb{E}\|\nabla F(\bar{x}^{k})\|^{2}+A\Delta^{k}+C\Omega_{1}^{k}+D\Omega_{2 }^{k}+B\Delta_{x}^{k}-\left(\frac{\eta}{2}-\frac{\eta^{2}L}{2}\right)\mathbb{E }\|\bar{v}^{k}\|^{2}.$ (64) $$

Using the definition of $\Delta_{x}^{k}$ and Lemma C.8 in (64), we finally have

$$ $\displaystyle\Phi_{k+1}$ $\displaystyle\leq\mathbb{E}F(\bar{x}^{k})-F^{*}-\frac{\eta}{2}\mathbb{E}\| \nabla F(\bar{x}^{k})\|^{2}+A\Delta^{k}+(C+2\widetilde{C}B)\Omega_{1}^{k}+(D+2 \eta^{2}B)\Omega_{2}^{k}$ $\displaystyle-\left(\frac{\eta}{2}-\frac{\eta^{2}L}{2}-2\eta^{2}nB\right) \mathbb{E}\|\bar{v}^{k}\|^{2}$ $\displaystyle=\mathbb{E}F(\bar{x}^{k})-F^{*}+s_{1}\Omega_{1}^{k}+s_{2}\Omega_{ 2}^{k}+A\Delta^{k}-\frac{\eta}{2}\mathbb{E}\|\nabla F(\bar{x}^{k})\|^{2}$ $\displaystyle+(C+2\widetilde{C}B-s_{1})\Omega_{1}^{k}+(D+2\eta^{2}B-s_{2}) \Omega_{2}^{k}-\left(\frac{\eta}{2}-\frac{\eta^{2}L}{2}-2\eta^{2}mB\right) \mathbb{E}\|\bar{v}^{k}\|^{2}.$ (65) $$

Looking at the form of the descent lemma, we want to require the following:

- 1.
$C_{0}=A$.
- 2.
$\frac{\eta}{2}-\frac{\eta^{2}L}{2}-2\eta^{2}mB\geq 0$.
- 3.
$C+2\widetilde{C}B-s_{1}\leq 0$.
- 4.
$D+2\eta^{2}B-s_{2}\leq 0$.

Before we start to solve this system relative to $\eta$, we assume the following form of constants $s_{1}$ and $s_{2}$:

$$ $\displaystyle s_{1}$ $\displaystyle=\frac{c_{1}(\rho,p,b)\hat{L}^{2}}{mL},$ $\displaystyle s_{2}$ $\displaystyle=\frac{c_{2}(\rho,p,b)L}{m\hat{L}^{2}}.$ (66) $$

First part
From the first requirement we get

$$ $\displaystyle C_{0}=\frac{\eta}{mp}+\frac{6s_{2}}{\rho}.$ (67) $$

Second part
From the second requirement:

$$ $\displaystyle\frac{\eta}{2}-\frac{\eta^{2}L}{2}-2\eta^{2}m\left(\frac{(1-p) \hat{L}^{2}C_{0}}{b}+\frac{3(1+p)\hat{L}^{2}s_{2}}{\rho}\right)\geq 0.$ (68) $$

After substituting $C_{0}$ into (68), we have

$$ $\displaystyle\frac{\eta}{2}-\frac{\eta^{2}L}{2}-\frac{2\eta^{3}(1-p)\hat{L}^{2 }}{bp}-\frac{12\eta^{2}m(1-p)\hat{L}^{2}s_{2}}{b\rho}-\frac{6\eta^{2}m(1+p) \hat{L}^{2}s_{2}}{\rho}\geq 0.$ $$

Using (C.3), one can obtain

$$ $\displaystyle\frac{\eta}{2}-\frac{\eta^{2}L}{2}-\frac{2\eta^{3}(1-p)\hat{L}^{2 }}{bp}-\frac{12\eta^{2}(1-p)Lc_{2}(\rho,p,b)}{b\rho}-\frac{6\eta^{2}(1+p)Lc_{2 }(\rho,p,b)}{\rho}\geq 0.$ $$

Dividing both sides by $\eta$:

$$ $\displaystyle\frac{1}{2}-\frac{\eta L}{2}-\frac{2\eta^{2}(1-p)\hat{L}^{2}}{bp} -\frac{12\eta(1-p)Lc_{2}(\rho,p,b)}{b\rho}-\frac{6\eta(1+p)Lc_{2}(\rho,p,b)}{ \rho}\geq 0.$ $$

Multiplying the left side by $2$ and entering a variable $r=\eta L$,

$$ $\displaystyle 1-r-\frac{4(1-p)r^{2}\hat{L}^{2}}{bpL^{2}}-\frac{24(1-p)c_{2}( \rho,p,b)r}{b\rho}-\frac{12(1+p)c_{2}(\rho,p,b)r}{\rho}\geq 0.$ (69) $$

Consequently, we could consider the next inequality

$$ $\displaystyle 1-r-\frac{4(1-p)r^{2}\hat{L}^{2}}{bpL^{2}}-\frac{36c_{2}(\rho,p, b)r}{\rho}\geq 0.$ (70) $$

Since $\frac{24(1-p)}{b}+12(1+p)\leq 36$, if $r_{0}=\eta_{0}L$ satisfies (70), then $r_{0}$ satisfies (69) too. Hence, we could solve (70) to find a bound on $r$. Therefore,

$$ $\displaystyle r$ $\displaystyle\leq\frac{-\left(1+\frac{36c_{2}(\rho,p,b)}{\rho}\right)+\sqrt{ \left(1+\frac{36c_{2}(\rho,p,b)}{\rho}\right)^{2}+\frac{16(1-p)\hat{L^{2}}}{ bpL^{2}}}}{\frac{8(1-p)\hat{L}^{2}}{bpL^{2}}}$ $\displaystyle=\frac{2}{\left(1+\frac{36c_{2}(\rho,p,b)}{\rho}\right)+\sqrt{ \left(1+\frac{36c_{2}(\rho,p,b)}{\rho}\right)^{2}+\frac{16(1-p)\hat{L^{2}}}{ bpL^{2}}}}.$ $$

Then,

$$ $\displaystyle\eta\leq\frac{2}{L\left(\left(1+\frac{36c_{2}(\rho,p,b)}{\rho} \right)+\sqrt{\left(1+\frac{36c_{2}(\rho,p,b)}{\rho}\right)^{2}+\frac{16(1-p) \hat{L^{2}}}{bpL^{2}}}\right)}.$ $$

Using $(a+b)^{2}\leq 2a^{2}+2b^{2}$, we claim that

$$ $\displaystyle\eta\leq\frac{2}{L\left(\left(1+\frac{36c_{2}(\rho,p,b)}{\rho} \right)+\sqrt{2+\frac{2592c_{2}^{2}(\rho,p,b)}{\rho^{2}}+\frac{16(1-p)\hat{L^{ 2}}}{bpL^{2}}}\right)}.$ (71) $$

Third part
From the third requirement one can obtain

$$ $\displaystyle\frac{\eta L^{2}}{m}+\left(1-\frac{\rho}{2}\right)s_{1}+2 \widetilde{C}\left(\frac{(1-p)\hat{L}^{2}C_{0}}{b}+\frac{3(1+p)\hat{L}^{2}s_{2 }}{\rho}\right)-s_{1}\leq 0.$ (72) $$

Substituting $C_{0}$ in (72):

$$ $\displaystyle\frac{\eta L^{2}}{m}-\frac{\rho}{2}s_{1}+\frac{2\widetilde{C}(1-p )\hat{L}^{2}}{b}\left(\frac{\eta}{mp}+\frac{6s_{2}}{\rho}\right)+\frac{6 \widetilde{C}(1+p)\hat{L}^{2}s_{2}}{\rho}\leq 0.$ $$

Hence, we get

$$ $\displaystyle\frac{\eta L^{2}}{m}-\frac{\rho}{2}s_{1}+\frac{2\widetilde{C}(1-p )\hat{L}^{2}\eta}{bmp}+\frac{12s_{2}\widetilde{C}(1-p)\hat{L}^{2}}{b\rho}+ \frac{6\widetilde{C}(1+p)\hat{L}^{2}s_{2}}{\rho}\leq 0.$ $$

Combining two last terms:

$$ $\displaystyle\frac{\eta L^{2}}{m}-\frac{\rho}{2}s_{1}+\frac{2\widetilde{C}(1-p )\hat{L}^{2}\eta}{bmp}+\frac{\widetilde{C}\hat{L}^{2}s_{2}}{\rho}\left(\frac{1 2(1-p)}{b}+6(1+p)\right)\leq 0.$ $$

Grouping terms with $\eta$:

$$ $\displaystyle\eta\left(\frac{L^{2}}{m}+\frac{2\widetilde{C}(1-p)\hat{L}^{2}}{ bmp}\right)-\frac{\rho}{2}s_{1}+\frac{\widetilde{C}\hat{L}^{2}s_{2}}{\rho} \left(\frac{12(1-p)}{b}+6(1+p)\right)\leq 0.$ $$

Using the (C.3), one can obtain

$$ $\displaystyle\eta\left(\frac{L^{2}}{m}+\frac{2\widetilde{C}(1-p)\hat{L}^{2}}{ bmp}\right)+\frac{\widetilde{C}Lc_{2}(\rho,p,b)}{\rho m}\left(\frac{12(1-p)}{b }+6(1+p)\right)\leq\frac{c_{1}(\rho,p,b)\hat{L}^{2}\rho}{2mL}.$ $$

Consequently,

$$ $\displaystyle\frac{2\eta L^{2}}{\rho m}\left(1+\frac{2\widetilde{C}(1-p)\hat{L }^{2}}{bpL^{2}}\right)+\frac{2\widetilde{C}Lc_{2}(\rho,p,b)}{\rho^{2}m}\left( \frac{12(1-p)}{b}+6(1+p)\right)\leq\frac{c_{1}(\rho,p,b)\hat{L}^{2}}{mL}.$ $$

Multiplying both sides by $\frac{m}{L}$:

$$ $\displaystyle\frac{2\eta L}{\rho}\left(1+\frac{2\widetilde{C}(1-p)\hat{L}^{2}} {bpL^{2}}\right)+\frac{2\widetilde{C}c_{2}(\rho,p,b)}{\rho^{2}}\left(\frac{12( 1-p)}{b}+6(1+p)\right)\leq\frac{c_{1}(\rho,p,b)\hat{L}^{2}}{L^{2}}.$ (73) $$

Then, we can consider next inequality

$$ $\displaystyle\frac{2\eta L}{\rho}\left(1+\frac{2\widetilde{C}(1-p)\hat{L}^{2}} {bpL^{2}}\right)+\frac{36\widetilde{C}c_{2}(\rho,p,b)}{\rho^{2}}\leq c_{1}( \rho,p,b),$ (74) $$

where we use $\frac{12(1-p)}{b}+6(1+p)\leq 18-6p\leq 18$. Hence, if we choose $\eta$ equal to some $\eta_{0}$ at which (74) holds, then (73) holds too. Therefore, we can bound $\eta$:

$$ $\displaystyle\eta\leq\frac{\frac{\rho c_{1}(\rho,p,b)\hat{L}^{2}}{L^{2}}-\frac {36\widetilde{C}c_{2}(\rho,p,b)}{\rho}}{2L\left(1+\frac{2\widetilde{C}(1-p) \hat{L}^{2}}{bpL^{2}}\right)}.$ $$

Using $\hat{L}\geq L$:

$$ $\displaystyle\eta\leq\frac{\rho c_{1}(\rho,p,b)-\frac{36\widetilde{C}c_{2}( \rho,p,b)}{\rho}}{2L\left(1+\frac{2\widetilde{C}(1-p)\hat{L}^{2}}{bpL^{2}} \right)}.$ (75) $$

Fourth part
From the fourth requirement, we get:

$$ $\displaystyle\frac{3\eta^{2}s_{1}}{\rho}+\left(1-\frac{\rho}{2}\right)s_{2}+2 \eta^{2}\left(\frac{(1-p)\hat{L}^{2}C_{0}}{b}+\frac{3(1+p)\hat{L}^{2}s_{2}}{ \rho}\right)-s_{2}\leq 0.$ (76) $$

Substituting the (67), we have

$$ $\displaystyle\frac{3\eta^{2}s_{1}}{\rho}-\frac{\rho}{2}s_{2}+\frac{2(1-p)\eta^ {3}\hat{L}^{2}}{bmp}+\frac{12(1-p)\eta^{2}\hat{L}^{2}s_{2}}{b\rho}+\frac{6\eta ^{2}(1+p)\hat{L}^{2}s_{2}}{\rho}\leq 0.$ $$

Then, after combining last two terms, we get

$$ $\displaystyle\frac{3\eta^{2}s_{1}}{\rho}-\frac{\rho}{2}s_{2}+\frac{2(1-p)\eta^ {3}\hat{L}^{2}}{bmp}+\frac{\eta^{2}\hat{L}^{2}s_{2}}{\rho}\left(\frac{12(1-p)} {b}+6(1+p)\right)\leq 0.$ $$

Using the (C.3), one can obtain

$$ $\displaystyle\frac{3\eta^{2}c_{1}(\rho,p,b)\hat{L}^{2}}{m\rho L}-\frac{\rho c_ {2}(\rho,p,b)L}{2m\hat{L}^{2}}+\frac{2(1-p)\eta^{3}\hat{L}^{2}}{bmp}+\frac{ \eta^{2}Lc_{2}(\rho,p,b)}{\rho m}\left(\frac{12(1-p)}{b}+6(1+p)\right)\leq 0.$ $$

Consequently,

$$ $\displaystyle\frac{\eta L}{\rho}\left(\frac{3\eta c_{1}(\rho,p,b)\hat{L}^{2}}{ mL^{2}}+\frac{2\rho(1-p)\eta^{2}\hat{L}^{2}}{bmpL}+\frac{\eta c_{2}(\rho,p,b)} {m}\left(\frac{12(1-p)}{b}+6(1+p)\right)\right)-\frac{\rho c_{2}(\rho,p,b)L}{2 m\hat{L}^{2}}\leq 0.$ (77) $$

If we choose $\eta\leq\frac{\rho}{L}$, then we could consider next inequality

$$ $\displaystyle\frac{3\eta c_{1}(\rho,p,b)\hat{L}^{2}}{mL^{2}}+\frac{2\rho(1-p) \eta^{2}\hat{L}^{2}}{bmpL}+\frac{\eta c_{2}(\rho,p,b)}{m}\left(\frac{12(1-p)}{ b}+6(1+p)\right)-\frac{\rho c_{2}(\rho,p,b)L}{2m\hat{L}^{2}}\leq 0.$ (78) $$

If (78) holds for some $\eta_{0}$, where $\eta_{0}L\leq\rho$, then (77) holds respectively. Hence, we could solve (78) relative to $\eta$. For convenience, multiply both sides of the equation by $m$:

$$ $\displaystyle\frac{3\eta c_{1}(\rho,p,b)\hat{L}^{2}}{L^{2}}+\frac{2\rho(1-p) \eta^{2}\hat{L}^{2}}{bpL}+{\eta c_{2}(\rho,p,b)}\left(\frac{12(1-p)}{b}+6(1+p) \right)-\frac{\rho c_{2}(\rho,p,b)L}{2\hat{L}^{2}}\leq 0.$ $$

Moreover, we could use $\frac{12(1-p)}{b}+6(1+p)\leq 18$ and $\rho\leq 1$. Therefore, using $L\leq\hat{L}$, we can consider

$$ $\displaystyle\frac{\hat{L}^{2}}{L^{2}}({3\eta c_{1}(\rho,p,b)}+18\eta c_{2}( \rho,p,b))+\frac{2(1-p)\eta^{2}\hat{L}^{2}}{bpL}-\frac{\rho c_{2}(\rho,p,b)L}{ 2\hat{L}^{2}}\leq 0.$ (79) $$

Then, if $\eta_{0}$ satisfies (79), consequently it satisfies (78) and (77). So, we could solve (79):

$$ $\displaystyle\frac{2(1-p)\eta^{2}\hat{L}^{2}}{bpL}+\frac{\eta\hat{L^{2}}}{L^{2 }}\left(3c_{1}(\rho,p,b)+{18c_{2}(\rho,p,b)}\right)-\frac{\rho c_{2}(\rho,p,b) L}{2\hat{L}^{2}}\leq 0.$ $$

Solving the inequality, we get

$$ $\displaystyle\eta$ $\displaystyle\leq\frac{-\left(3c_{1}(\rho,p,b)+{18c_{2}(\rho,p,b)}\right)+ \sqrt{\left(3c_{1}(\rho,p,b)+{18c_{2}(\rho,p,b)}\right)^{2}+\frac{8(1-p)}{bp} \frac{\rho c_{2}(\rho,p,b)}{2}}}{\frac{4(1-p)\hat{L}^{2}}{bpL}}$ $\displaystyle=\frac{4{\rho c_{2}(\rho,p,b)}}{{4L}\left(\left(3c_{1}(\rho,p,b)+ {18c_{2}(\rho,p,b)}\right)+\sqrt{\left(3c_{1}(\rho,p,b)+{18c_{2}(\rho,p,b)} \right)^{2}+\frac{8(1-p)}{bp}\frac{\rho c_{2}(\rho,p,b)}{2}\frac{L^{4}}{\hat{L }^{4}}}\right)}$ $\displaystyle=\frac{{\rho c_{2}(\rho,p,b)}}{{L}\left(\left(3c_{1}(\rho,p,b)+{1 8c_{2}(\rho,p,b)}\right)+\sqrt{\left(3c_{1}(\rho,p,b)+{18c_{2}(\rho,p,b)} \right)^{2}+\frac{8(1-p)}{bp}\frac{\rho c_{2}(\rho,p,b)}{2}\frac{L^{4}}{\hat{L }^{4}}}\right)}.$ $$

Using that $(a+b)^{2}\leq 2a^{2}+2b^{2}$ and $\frac{L^{4}}{\hat{L}^{4}}\leq\frac{\hat{L^{2}}}{L^{2}}$, we can give a bit rough estimate of $\eta$:

$$ $\displaystyle\eta\leq\frac{\rho c_{2}(\rho,p,b)}{L\left(3c_{1}(\rho,p,b)+18c_{ 2}(\rho,p,b)+\sqrt{18c_{1}^{2}(\rho,p,b)+648c_{2}^{2}(\rho,p,b)+\frac{4(1-p) \rho c_{2}(\rho,p,b)}{bp}\frac{\hat{L^{2}}}{L^{2}}}\right)}.$ (80) $$

Selection of $c_{1}(\rho,p,b)$ and $c_{2}(\rho,p,b)$
Let us take these parameters in the following way

$$ $\displaystyle c_{1}(\rho,p,b)$ $\displaystyle=2\widetilde{C}(1+\rho)\left(\sqrt{\frac{(1-p)\hat{L}^{2}}{bpL^{2 }}}+\frac{1}{\widetilde{C}}\right),$ $\displaystyle c_{2}(\rho,p,b)$ $\displaystyle=\frac{\rho^{2}}{18\widetilde{C}}.$ $$

From (71), we get

$$ $\displaystyle\eta\leq\frac{2}{L\left(\left(1+\frac{2\rho}{\widetilde{C}}\right )+\sqrt{2+\frac{8\rho^{2}}{\widetilde{C}^{2}}+\frac{16(1-p)\hat{L}^{2}}{bpL^{2 }}}\right)}.$ $$

Consequently, we could roughen the estimate by $\rho\leq 1$:

$$ $\displaystyle\eta\leq\frac{2}{L\left(\left(1+\frac{2}{\widetilde{C}}\right)+ \sqrt{2+\frac{8}{\widetilde{C}^{2}}+\frac{16(1-p)\hat{L}^{2}}{bpL^{2}}}\right)}.$ (81) $$

From (75), one can obtain

$$ $\displaystyle\eta\leq\frac{2\widetilde{C}(\rho+\rho^{2})\left(\sqrt{\frac{(1-p )\hat{L}^{2}}{bpL^{2}}}+\frac{1}{\widetilde{C}}\right)-2\rho}{2L\left(1+\frac{ 2\widetilde{C}(1-p)\hat{L}^{2}}{bpL^{2}}\right)}.$ $$

Hence, final bound is

$$ $\displaystyle\eta\leq\frac{2\rho^{2}+2\widetilde{C}(\rho^{2}+\rho)\sqrt{\frac{ (1-p)\hat{L}^{2}}{bpL^{2}}}}{L\left(1+\frac{2\widetilde{C}(1-p)\hat{L}^{2}}{ bpL^{2}}\right)}.$ (82) $$

From (80), we have

$$ $\displaystyle\eta\leq\frac{\rho^{3}}{18\widetilde{C}L\left(6\widetilde{C}(1+ \rho)\left(\sqrt{\frac{(1-p)\hat{L}^{2}}{bpL^{2}}}+\frac{1}{\widetilde{C}} \right)+\frac{\rho^{2}}{\widetilde{C}}+\sqrt{72\widetilde{C}^{2}(1+\rho)^{2} \left(\sqrt{\frac{(1-p)\hat{L}^{2}}{bpL^{2}}}+\frac{1}{\widetilde{C}}\right)^{ 2}+\frac{2\rho^{4}}{\widetilde{C}^{2}}+\frac{2(1-p)\rho^{3}\hat{L}^{2}}{9 \widetilde{C}bp}L^{2}}\right)}.$ $$

Using that $(a+b)^{2}\leq 2a^{2}+2b^{2}$ and $\rho\leq 1$, we claim

$$ $\displaystyle\eta\leq\frac{\rho^{3}}{18\widetilde{C}L\left(12+\frac{1}{ \widetilde{C}}+12\widetilde{C}\sqrt{\frac{(1-p)\hat{L}^{2}}{bpL^{2}}}+\sqrt{28 8+\frac{2}{\widetilde{C}^{2}}+\frac{288\widetilde{C}^{2}(1-p)\hat{L}^{2}}{bpL^ {2}}+\frac{2(1-p)\hat{L}^{2}}{9\widetilde{C}bpL^{2}}}\right)}.$ (83) $$

From $\eta\leq\frac{\rho}{L}$ and bounds (81), (82) and (83) the next result follows:

$$ $\displaystyle\Phi_{k+1}\leq\Phi_{k}-\frac{\eta}{2}\mathbb{E}\|\nabla F(\bar{x} ^{k})\|^{2}.$ $$

Summarizing over $t$, we claim

$$ $\displaystyle\frac{1}{N}\sum\limits_{k=0}^{N-1}\mathbb{E}\|\nabla F(\bar{x}^{k })\|^{2}\leq\frac{2(\Phi_{0}-\Phi_{k})}{\eta N},$ $$

where $\Phi_{0}=F(x^{0})-F^{*}=\Delta$ because of initialization. Hence, for reaching $\frac{1}{N}\sum\limits_{k=0}^{N-1}\mathbb{E}\|\nabla F(\bar{x}^{k})\|^{2}\leq
\epsilon^{2}$, we need

$$ $\displaystyle N=\mathcal{O}\left(\frac{L\Delta\left(1+\sqrt{\frac{(1-p)\hat{L} ^{2}}{bpL^{2}}}\right)}{\rho^{3}\epsilon^{2}}\right)$ $$

iterations. Choosing $\hat{x}^{N}$ uniformly from $\{\bar{x}^{k}\}_{k=0}^{N-1}$, we claim the final result.
∎

###### Proof.

### C.4 Proof of Corollary 3.5

###### Proof.

First, we need to clarify that multi-stage consensus technique allows to avoid $\chi^{3}$ factor in Theorem 3.4, but apply $\chi$ to a number of communications. Hence, choosing $b=\frac{\sqrt{n}\hat{L}}{L},p=\frac{b}{n+b}$, we get

$$ $\displaystyle N_{comm}=\mathcal{O}\left(\frac{\chi L\Delta\left(1+\sqrt{\frac{ n\hat{L^{2}}}{b^{2}L^{2}}}\right)}{\epsilon^{2}}\right)=\mathcal{O}\left(\frac {\chi L\Delta}{\epsilon^{2}}\right).$ $$

Moreover, number of local computations (in average) is equal to

$$ $\displaystyle n+N_{comm}(pn+(1-p)b)=n+C\frac{\chi L\Delta}{\epsilon^{2}}\left( \frac{2n\sqrt{n}\frac{\hat{L}}{L}}{n+\sqrt{n}\frac{\hat{L}}{L}}\right)\leq n+C \chi\frac{\sqrt{n}\hat{L}\Delta}{\epsilon^{2}}=\mathcal{O}\left(n+\frac{\sqrt{ n}\hat{L}\Delta}{\epsilon^{2}}\right),$ $$

where $C$ is a constant from $\mathcal{O}(\cdot)$. This finishes the proof.
∎

###### Proof.

### C.5 Lower bounds for nonconvex setting

The main idea of lower bound construction is to provide an example of a bad function for which we can estimate the minimum required number of iterations or oracle calls to solve the problem. Hence, we need to consider some class of problems, oracles, and algorithms among which we shall dwell.
Before we start, let us propose some additional facts for a clear proof.
Consider the next function:

$$ $\displaystyle l(x)=-\Psi(1)\Phi(\left[x\right]_{1})+\sum\limits_{j=2}^{d}\left (\Psi(-\left[x\right]_{j-1})\Phi(-\left[x\right]_{j})-\Psi(\left[x\right]_{j-1 })\Phi(\left[x\right]_{j})\right),$ (84) $$

where

$$ $\displaystyle\Psi(z)$ $\displaystyle=\begin{cases}0\qquad z\leq\frac{1}{2};\\ \exp\left(1-\frac{1}{(2z-1)^{2}}\right)\qquad z>\frac{1}{2},\end{cases}$ $\displaystyle\Phi(z)$ $\displaystyle=\sqrt{e}\int\limits_{-\infty}^{z}e^{-\frac{t^{2}}{2}}\,dt.$ (85) $$

It has already been shown in Arjevani et al., () (see Lemma 2) that $l(x)$ satisfies the following properties:

- 1.
$\forall x\in\mathbb{R}^{d}\ l(x)-\inf_{x}l(x)\leq\Delta_{0}d\$ with $\Delta_{0}=12$.
- 2.
$l(x)$ is $L_{0}$-smooth with $L_{0}=152$.
- 3.
$\forall x\in\mathbb{R}^{d}\ \|\nabla l(x)\|_{\infty}\leq G_{0}$ with $G_{0}=23$.
- 4.
$\forall x\in\mathbb{R}^{d}:\left[x\right]_{d}=0\ \|\nabla l(x)\|_{\infty}\geq 1$.

Moreover, let us introduce the next definition

$$ $\displaystyle\text{prog}(x)=\begin{cases}0\qquad x=0;\\ \max_{1\leq j\leq d}\{j:\left[x\right]_{j}\neq 0\}\qquad\text{otherwise}.\end{cases}$ (86) $$

Hence, the function $f$ is called zero-chain, if

$$ $\displaystyle\text{prog}(\nabla f(x))\leq\text{prog}(x)+1.$ $$

This means that if we start at point $x=0$, after a gradient estimation we earn at most one non-zero coordinate of $x$. What is more, $l(x)$ is zero-chain function.
Let us formulate an auxiliary lemma which helps to estimate the lower bound.

###### Lemma C.9 .

Consider the function $l(x)$ which is defined above. Suppose that

$$ $\displaystyle\hat{l}_{1}(x)$ $\displaystyle=-\Psi(1)\Phi(\left[x\right]_{1})+\sum\limits_{j\text{ odd; }j \geq 2}\left(\Psi(-\left[x\right]_{j-1})\Phi(-\left[x\right]_{j})-\Psi(\left[x \right]_{j-1})\Phi(\left[x\right]_{j})\right),$ $\displaystyle\hat{l}_{2}(x)$ $\displaystyle=\sum\limits_{j\text{ even}}\left(\Psi(-\left[x\right]_{j-1})\Phi (-\left[x\right]_{j})-\Psi(\left[x\right]_{j-1})\Phi(\left[x\right]_{j})\right).$ $$

Hence, if we divide $\hat{l}_{i}(x)$ into $n$ parts in the following way:

$$ $\displaystyle\hat{l}_{i}(x)=\frac{1}{n}\sum\limits_{k=1}^{n}\hat{l}_{ik}(x),$ $$

where

$$ $\displaystyle\hat{l}_{1k}(x)$ $\displaystyle=\begin{cases}-n\Psi(1)\Phi(\left[x\right]_{1})+\sum\limits_{j \geq 2,\ j\equiv 1\text{ mod 2n}}n\left(\Psi(-\left[x\right]_{j-1})\Phi(-\left [x\right]_{j})-\Psi(\left[x\right]_{j-1})\Phi(\left[x\right]_{j})\right)\qquad k =1;\\ \sum\limits_{j\equiv 2k-1\text{ mod 2n}}n\left(\Psi(-\left[x\right]_{j-1})\Phi (-\left[x\right]_{j})-\Psi(\left[x\right]_{j-1})\Phi(\left[x\right]_{j})\right )\qquad k>1;\end{cases}$ $\displaystyle\hat{l}_{2k}(x)$ $\displaystyle=\sum\limits_{j\equiv 2k\text{ mod 2n}}n\left(\Psi(-\left[x\right ]_{j-1})\Phi(-\left[x\right]_{j})-\Psi(\left[x\right]_{j-1})\Phi(\left[x\right ]_{j})\right),$ $$

then

$$ $\displaystyle\frac{1}{n}\sum\limits_{k=1}^{n}\|\nabla\hat{l}_{ik}(y)-\nabla \hat{l}_{ik}(x)\|^{2}\leq nL_{0}^{2}\|y-x\|^{2}$ $$

for $i=1,2$ and for all $x,y\in\mathbb{R}^{d}$.

###### Proof.

Let us consider the structure of $\nabla\hat{l}_{ik}(x)$. This part of $\hat{l}_{i}(x)$ depends only on some coordinates of $x$. Hence, given the definition of each slice, we can identify which coordinates of $\hat{l}_{ik}(x)$ can be non-zero. For example, $\nabla\hat{l}_{11}(x)$ can be non-zero only in components $1,2n,2n+1,4n,4n+1,\ldots$ because this function depends only on these coordinates.
Moreover, since $n\geq 2$ (when $n=1$, the fact above is obvious), if we consider $\hat{l}_{ik}(x)$ and $\hat{l}_{ij}(x)$, then there is no intersection of sets of potentially non-zero coordinates of gradients of these functions due to the construction. Using that full gradient is

$$ $\displaystyle\nabla\hat{l}_{i}(x)=\frac{1}{n}\sum\limits_{k=1}^{n}\nabla\hat{l }_{ik}(x),$ $$

one can obtain

$$ $\displaystyle\frac{1}{n}\sum\limits_{k=1}^{n}\|\nabla\hat{l}_{ik}(y)-\nabla \hat{l}_{ik}(x)\|^{2}=n\|\nabla\hat{l}_{i}(y)-\nabla\hat{l}_{i}(x)\|^{2}\leq nL _{0}^{2}\|y-x\|^{2}.$ $$

∎

###### Remark C.10 .

Lemma C.9 asserts that in essence the function under consideration and its pieces satisfy the assumptions from Theorem 4.5. The main effect consists of the scaling factor $\frac{1}{\sqrt{n}}$.

Proof of Theorem 4.5

###### Proof.

We need to introduce functions $F_{i}$, structure of a time-varying graphs and mixing matrices respectively to construct the lower bound. Then, we can consider next functions

$$ $\displaystyle l_{1}(x)$ $\displaystyle=\frac{m}{\left\lceil\frac{m}{3}\right\rceil}\left(-\Psi(1)\Phi( \left[x\right]_{1})+\sum\limits_{j\text{ odd}}\left(\Psi(-\left[x\right]_{j-1} )\Phi(-\left[x\right]_{j})-\Psi(\left[x\right]_{j-1})\Phi(\left[x\right]_{j}) \right)\right),$ $\displaystyle l_{2}(x)$ $\displaystyle=\frac{m}{\left\lceil\frac{m}{3}\right\rceil}\left(\sum\limits_{j \text{ even}}\left(\Psi(-\left[x\right]_{j-1})\Phi(-\left[x\right]_{j})-\Psi( \left[x\right]_{j-1})\Phi(\left[x\right]_{j})\right)\right).$ $$

As a sequence of graphs, we take star graphs, for each of which the center changes with time according some rules, which we explain later. We derive the mixing matrix from the Laplacian matrix of the graph at the moment $t$ in the next way:

$$ $\displaystyle\mathbf{W}(t)=\mathbf{I}-\frac{1}{\lambda_{max}(L(t))}L(t).$ $$

This matrix is obviously a mixing matrix by reason of symmetry and doubly stochasticity. Moreover, $\rho(t)=1-\mu_{2}(\mathbf{W}(t))$, where $\mu_{2}(\mathbf{W}(t))$ is the second largest eigenvalue of $\mathbf{W}(t)$. Consequently, using the spectrum of $L(t)$, one can obtain that $\rho(t)=\rho=\frac{1}{m}$.
Let us specify the functions $F_{i}$ at each node:

$$ $\displaystyle F_{i}(x)=\begin{cases}\frac{LC^{2}}{3L_{0}}l_{1}\left(\frac{x}{C }\right)\qquad&1\leq i\leq{\left\lceil\frac{m}{3}\right\rceil}\Leftrightarrow i \in S_{1},\\ \frac{LC^{2}}{3L_{0}}l_{2}\left(\frac{x}{C}\right)\qquad&{\left\lceil\frac{m}{ 3}\right\rceil}+1\leq i\leq 2{\left\lceil\frac{m}{3}\right\rceil} \Leftrightarrow i\in S_{2},\\ 0\qquad&\text{otherwise}\Leftrightarrow i\in S_{3},\end{cases}$ $$

where we clarify $C$ later.
Also we need to separate each function into $n$ blocks. It is enough to divide $F_{i}(x)$ according to Lemma C.9 with corresponding multiplicative constants.
Therefore, since $l_{1}(x)$ and $l_{2}(x)$ are $3L_{0}$-smooth, $F_{i}(x)$ is $L$-smooth for every $C>0$.
We also can bound $F(0)-\inf_{x}F(x)$ using

$$ $\displaystyle F(0)-\inf_{x}F(x)\leq\frac{1}{m}\sum\limits_{i=1}^{m}(F_{i}(x)- \inf_{x}F_{i}(x))\leq\frac{LC^{2}\Delta_{0}d}{3L_{0}}.$ $$

Hence, we need

$$ $\displaystyle\frac{LC^{2}\Delta_{0}d}{3L_{0}}\leq\Delta.$ $$

Now we are ready to divide our proof into three parts.
Number of communications
We want the transfer of information between sets $S_{1}$ and $S_{2}$ to not occur for as long as possible. This requires that the center of the star graph is not a vertex from $S_{1}$ or $S_{2}$, or it is not a vertex of $S_{3}$ that already has information from other sets of vertices. Therefore, let us specify the changes of the graphs with time according to the following principle: first we go through all the vertices of the set $S_{3}$, and after that we choose the vertex that allows the exchange of information between $S_{1}$ and $S_{2}$.
Then, mentioning that $\frac{1}{m}\sum\limits_{i=1}^{m}F_{i}(x)=\frac{LC^{2}}{3L_{0}}l\left(\frac{x}{
C}\right)$ and

$$ $\displaystyle\text{prog}(\nabla F_{i}(x))\begin{cases}=\text{prog}(x)+1\qquad( \text{prog}(x)\text{ is even and }i\in S_{1})\text{ or }(\text{prog}(x)\text{ is odd and }i\in S_{2});\\ \leq\text{prog}(x)\qquad\text{otherwise},\end{cases}$ $$

we claim that for increasing the $\text{prog}(x)$ at $1$ we need at least $m-2{\left\lceil\frac{m}{3}\right\rceil}+1$ iterations (without considering local computations). Therefore, after $N$ iterations

$$ $\displaystyle\text{prog}(N)=\max_{1\leq i\leq m,\ 0\leq t\leq N}\text{prog}(x_ {i}^{t})\leq\left\lfloor\frac{N}{m-2{\left\lceil\frac{m}{3}\right\rceil}+1} \right\rfloor+1.$ $$

Also it is easy to make sure that if $m\geq 3$, then $m-2{\left\lceil\frac{m}{3}\right\rceil}+1\geq\frac{m}{4}$. Then

$$ $\displaystyle\text{prog}(N)\leq\left\lfloor\frac{4N}{m}\right\rfloor+1.$ $$

Number of local computations
Here we use the same idea as in first part. Let us consider the next oracle computation: we take one of pieces on each node uniformly, i.e. $\mathbb{P}\{\text{block with index $k$ is chosen}\}=\frac{1}{n}$ for every $k=1,\ldots,n$. Hence, at the current moment, we need a specific piece of function, because according to structure of $l(x)$, each gradient estimation can "defreeze" at most one component and only a computation on a certain block makes it possible. Let us define the number of required gradient calculations as $n_{avg}$. Therefore,

$$ $\displaystyle\mathbb{E}\{n_{avg}\}=\sum\limits_{i=1}^{\infty}\frac{i}{n}\left( \frac{n-1}{n}\right)^{i-1}=n,$ $$

where $\frac{1}{n}\left(\frac{n-1}{n}\right)^{i-1}$ is a is the probability that at $i$-th moment we take the correct piece. Thus, after $K$ local computations on each node we can change at most $\left\lfloor\frac{K}{n}\right\rfloor+1$ coordinates.
Final result
Hence, if considered algorithm makes $N$ communications and $K$ local computations on each node, then

$$ $\displaystyle\text{prog}(N,K)=\max_{1\leq i\leq m,\ 0\leq t\leq N}\text{prog}( x_{i}^{t})\leq\min\left(\left\lfloor\frac{4N}{m}\right\rfloor+1,\left\lfloor \frac{K}{n}\right\rfloor+1\right)$ $$

Consequently, for every $N\geq\frac{m}{4}$ and $K\geq n$ consider

$$ $\displaystyle d=2+\min\left(\left\lfloor\frac{4N}{m}\right\rfloor,\left\lfloor \frac{K}{n}\right\rfloor\right).$ $$

It is easy to verify thar

$$ $\displaystyle d<\min\left(\frac{16N}{m},\frac{4K}{n}\right).$ $$

Moreover, we choose $C$ as

$$ $\displaystyle C=\left(\frac{3L_{0}\Delta}{L\Delta_{0}\min\left(\frac{16N}{m}, \frac{4K}{n}\right)}\right)^{\frac{1}{2}}.$ $$

Hence, clarifying that $\text{prog}(N,K)<d$, we have

$$ $\displaystyle\mathbb{E}\|\nabla F(\hat{x}_{N})\|^{2}$ $\displaystyle\geq\min_{\left[x\right]_{d}=0}\|\nabla F(\hat{x}_{N})\|^{2}= \frac{L^{2}C^{2}}{9L_{0}^{2}}\min_{\left[x\right]_{d}=0}\|\nabla l(\hat{x}_{N} )\|^{2}\geq\frac{L^{2}C^{2}}{9L_{0}^{2}}=\max\left(\frac{L\Delta m}{48NL_{0} \Delta_{0}},\frac{L\Delta n}{12KL_{0}\Delta_{0}}\right)$ $\displaystyle\geq\frac{L\Delta m}{96NL_{0}\Delta_{0}}+\frac{L\Delta n}{24KL_{0 }\Delta_{0}}=\Omega\left(\frac{L\Delta m}{N}+\frac{L\Delta n}{K}\right),$ $$

where the second inequality holds from fourth property of $l(x)$.
Consequently, applying Lemma C.9 to $\{F_{i}\}_{i=1}^{m}$ and noting that $\chi=\Theta\left(m\right)$, we finish the proof.
∎

###### Lemma C.9 .

###### Proof.

###### Remark C.10 .

###### Proof.

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 8
presentation: 3
questions: - Can the authors clarify whether there is no need to represent error bars across independent experiments to mitigate the impact of stochasticity in the numerical examples?
soundness: 3
strengths: - The paper studies an important problem.
- The paper is well-written.
- Notation, assumptions, and results are presented clearly.
- The established lower bounds on the complexities and presenting optimal algorithms achieving these bounds are solid contributions.
- Numerical examples further strengthen the paper's claims.
summary: This paper studies decentralized finite-sum optimization problem over time-varying graphs. Theorem 4.3 and Theorem 4.5 establish lower bounds on computational and communication complexities, resp., for strongly convex and non-convex optimization. Furthermore, the paper presented two algorithms ADOM+VR and GT-PAGE, resp., for strongly convex and non-convex optimization while comparing its performance with the state-of-the-art methods both analytically (see Tables 1 & 2) and numerically. Notably, GT-PAGE is optimal by achieving the lower complexity bounds while ADOM+VR is optimal in terms of communication iterations. Some open problems have also been highlighted. The numerical examples for the LibSVM dataset show the superior performance of the algorithm in terms of communication and computational complexities. Interestingly, the optimal algorithm GT-PAGE achieve presents better yet not strongly superior performance in comparison to the state-of-the-art methods.
weaknesses: - The paper is fairly technical. To smoothen the paper's technical content and to improve the paper's accessibility, more qualitative discussions can be included.
- The introduction directly jumps to the optimization problem formulation. More motivating examples for the problem formulation would improve the paper.
- In the introduction, Tables 1 and 2 present the complexities in terms of parameters n, L, \mu, and some others. However, it is not clear what these parameters, e.g., L and \mu, refer to.
- Numerical examples do not provide error bars.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: - Why the two proposed algorithms require different function smoothness assumptions (c.f. Assumption 2.1, 2.2 and 2.3)?
- The LibSVM dataset used for the experiments in this work seems not adequate; the reviewer would like to know if the algorithm could be applied to more complex datasets such as cifar-10/100 to further validate the effect of the algorithm.
- How is the time-varying topology being implemented in the experiments?
- Why the reference Metelev et al. (2024) is not discussed in the main text? In fact, the time-varying topological sequences used in this work for obtaining lower bound adopt their strategy.
soundness: 3
strengths: - This work provides rich theoretical analytical results for different objective function assumptions. By comparing with the proposed lower bound, it is shown that the proposed algorithm is optimal in their scenario;
- The lower bound in this paper takes into account the smoothness coefficient of each node, which is more refined.
summary: This manuscript addresses a decentralized stochastic optimization problem with a finite sample set at each node over time-varying networks. The authors propose two algorithms tailored for strongly convex and non-convex objective functions, respectively, and provide a lower bound analysis to discuss the optimality of the proposed algorithms.
weaknesses: While this work presents a set of results for distributed stochastic optimization problems, I found the paper difficult to follow, with unclear motivation and insufficient discussion on the necessity of this study. My specific concerns are as follows:

- On the significance of this work: The paper addresses time-varying topologies in distributed networks, but it is unclear why these topologies pose unique challenges for distributed algorithms. In my view, as long as Assumption 2.5 holds (i.e., the topology is connected at each iteration) and multi-round communication acceleration is employed, a time-varying topology does not seem substantially more challenging than that of fixed topology. Thus, this work appears to be tackling a corner case, especially considering that similar problems have been widely studied, e.g., Kovalev et al., 2021a, Luo and Ye, 2022, Huang and Yuan, 2022, Li and Lin, 2021. The authors need to further clarify the novelty and contribution of this work against these exisitng works.
- On the Assumptions on Smoothness: The assumptions regarding smoothness are somewhat confusing. The authors consider three types of smoothness but do not compare their differences or clarify which assumptions are strongest. Additionally, Assumption 2.1 requires that each sample’s objective function is smooth. It would be helpful to discuss whether this holds in typical machine learning tasks and if it is verifiable in practice.
- Regrading the proof of Theorem 3.2, compared to (Kovalev et al., 2021a), it seems to differ in only one constrained VR gradient estimation error (c.f. Lemma B.1), while the other proofs are almost identical to Kovalev et al., 2021a, differing only in some parameter choices. This makes the technical contribution of this paper vague.
- On Readability and Clarity: The paper’s readability could be significantly improved. In the algorithm design section, the authors rely heavily on prior literature to explain their algorithmic approach, offering limited unique insights. This reliance diminishes the perceived novelty of the work. Additionally, the paper contains many symbols that are either used before being defined or left undefined altogether (e.g., $\lambda^{+}_{\text{min}}$), making it challenging to follow.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. The organization clarity (please see weakness-1). In order to better elaborate the contributions in this work, it is suggested that the authors re-write all bullet points in the contribution paragraph. For the ADOM+VR algorithm, please state the type of optimization problem/network setting and why it is optimal (is it applied to a different optimization problem or the convergence speed is faster than others); For the GT-PAGE algorithm, please also state the type of optimization problem and why it is optimal. It is not strong enough to only mention the elements of different algorithms in the contribution.

2. The achievability of Assumption 2.5 (please see weakness-2).

3. In experiments, are those plots presenting training set performance or testing set performance? It is expected both training and testing performance are shown. Moreover, it would be good to show classification accuracy on test set.
soundness: 3
strengths: The topic of the work is well aligned with ICLR community and it is significant to extend the lower bound analysis for decentralized optimization problems. The work also contains great amount of theoretical work.
summary: This paper studies stochastic decentralized optimization problems of strongly-convex and non-convex settings over static and time-varying networks. For the strongly-convex setting, the ADOM+VR algorithm is proposed and the convergence property is established; For the non-convex setting, the GT-PAGE algorithm is proposed and the convergence property is established. The authors also study the lower bounds of both strongly-convex and non-convex decentralized optimization problems theoretically. The efficacy of the proposed algorithms is validated in simulations.
weaknesses: 1. The organization of the manuscript is not clear and different pieces (section 3.2, 3.3, 4.1) are isolated from each other. Since they are presented in this manuscript, it is assumed they have some internal relationship. For example, is the optimal non-convex algorithm, GT-PAGE, also optimal in the strongly-convex setting? Why is the strongly-convex algorithm based on ADOM+ algorithm while the non-convex algorithm is based on PAGE algorithm?

2. It is concerned that the Assumption 2.5 is too strong, i.e., assuming the existence of $\chi \geq 1$ (also why $\geq 1$ rather than $ > 1$?).  This work studies time-varying networks and the matrices $W(k)$ change at every time step $k$. How is it guaranteed that such $\chi$ exists? Are there any other requirements for the network connectivity or matrix construction to guarantee the existence of $\chi$?

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: - It is said in Corollary 3.3 that the number of communications per iteration is of order $\chi$, but in Algorithm 1 there is only one communication per iteration (matrix $W(k)$ is used). I understand that we should use Algorithm 1 with the multi-consensus matrix $W(k, \kappa)$ instead, is that true? This should be clarified.
soundness: 3
strengths: - the overall approach is clear and natural
- (almost) matching upper and lower bounds 
- results for both strongly convex and non-convex settings
summary: This paper studies decentralized finite-sum optimization over time-varying networks for smooth objectives. 

In the strongly-convex setting, the ADOM+VR algorithm consists in mixing the ADOM+ (accelerated decentralized optimization for time-varying graphs) and Katyusha (Accelerated variance-reduced single-machine) algorithms. Similarly, the lower bound mixes the ones from ADOM+ and ADFS. 

In the non-convex setting, gradient tracking (a standard way to obtain "exact" decentralized algorithms) is combined with the PAGE VR algorithm. Similarly, the lower bound mixes that of Yuan et al (2022) and ADOM+. 

In both cases, combining existing optimal approaches yields (almost) matching upper and lower complexity bounds. Toy experiments are given to illustrate the practical performances.
weaknesses: - Contributions are incremental: mostly combining accelerated variance-reduced estimators with accelerated decentralized algorithms over time-varying graphs (or gradient tracking for the non-convex setting) 
- The setting (finite-sum decentralized optimization over time-varying graphs) is rather niche
- The algorithms are quite rigid, with long communication stages (through $W(k)$) and long computation stages (through mini-batching), which is effective but not very elegant, and unlikely to extend well to, e.g., asynchronous settings. Approaches like DADAO (Nabli and Oyallon, 2023) are likely to lead to better solutions, as well as maybe close the gap between lower and upper bounds in the strongly-convex setting.
- The non-convex algorithm has a pretty bad dependence on the graph constants ($\chi^3$), and is only saved by multi-consensus steps (which again, would likely break in asynchronous settings for instance).

Meta-review: While the authors see some possible merit in this work, after the rebuttal and discussion most of the reviewers still view the paper as being below the acceptance threshold (two weakly and one strongly).  There most common recurring concern was the limited technical novelty, and there were also some suggestions on other issues such as paper organization and providing more metrics in experiments.  There could be some routes to strengthening the paper, e.g., handling other settings such as relaxing synchronicity, but the consensus is not to accept in the current form.

Decision: Reject