Decentralized Sporadic Federated Learning: A Unified Algorithmic Framework with Convergence Guarantees

## Abstract

Abstract Decentralized Federated Learning (DFL) has received significant recent research attention, capturing settings where both model updates and model aggregations – the two key FL processes – are conducted by the clients. In this work, we propose Decentralized Sporadic Federated Learning ( DSpodFL ), a DFL methodology which generalizes the notion of sporadicity in both of these processes, modeling the impact of different forms of heterogeneity that manifest in realistic DFL settings. DSpodFL unifies many of the prominent decentralized optimization methods, e.g., distributed gradient descent (DGD), randomized gossip (RG), and decentralized federated averaging (DFedAvg), under a single modeling framework. We analytically characterize the convergence behavior of DSpodFL , showing, among other insights, that we can match
a geometric convergence rate to a finite optimality gap under more general assumptions than in existing works. Through experiments, we demonstrate that DSpodFL achieves significantly improved training speeds and robustness to variations in system parameters compared to the state-of-the-art.

## 1 Introduction

Figure: (a) FL with a central server
Refer to caption: /html/2402.03448/assets/x1.png

Federated learning (FL) has exploded in popularity as a privacy-preserving method for distributed AI/ML (McMahan et al., ). In conventional FL, clients (e.g., edge clients) are connected to a central server (e.g., at a network access point) via a star topology configuration (Konečnỳ et al., ). In this setup (see Fig. [1(a)](#S1.F1.sf1)), FL iterates between (i) client-side local model updates, via stochastic gradient descent (SGD) on local datasets, and (ii) server-side global aggregations/synchronizations (Bonawitz et al., ).

A central server may not always be present/feasible for model aggregations, though, e.g., in the growing body of direct peer-to-peer networks. To address this, recent research has proposed decentralized federated learning (Koloskova et al., ), to replace the server’s role in FL based on distributed optimization techniques (Nedić et al., ). In DFL (see Figs. [1(b)](#S1.F1.sf2)-[1(d)](#S1.F1.sf4)), clients conduct gradient descent on their local models, similar to FL, but exchange models with their neighboring clients to form consensus-driven aggregations over local networks (Huang et al., ).

FL settings are often dominated by heterogeneity in various dimensions, including differing client processing capabilities, communication capabilities, and local dataset statistics (Li et al., ). This causes (i) computing gradients at every iteration to be costlier (e.g., in terms of energy consumption and delay) at clients with weaker/slower processing units, and (ii) higher transmission delays for clients with low-quality communication links (e.g., lower available bandwidth and blocked wireless channels), among other impacts (Wang et al., ). In centralized FL, these properties have been studied extensively, generating a solid understanding of how global model convergence is impacted by e.g., client local updates conducted, global aggregation participation frequencies, and data heterogeneity/gradient diversity (Mishchenko et al., ; Maranjyan et al., ). In DFL, by contrast, there has not yet been a comprehensive study of how these different forms of heterogeneity jointly impact model training performance. The critical distinctions that must be considered are the roles of heterogeneous graph connectivity and the iterative nature of model aggregations.

Main contributions. We bridge this gap by developing a unified framework for analyzing the impacts of heterogeneity in DFL, which we refer to as sporadicity in client participation. Our framework encapsulates the joint effects of (i) sporadicity in local client updates and (ii) sporadicity in inter-client communications for model exchanges. As illustrated in Fig. [1](#S1.F1), our framework (Fig. [1(e)](#S1.F1.sf5)) unites multiple decentralized optimization algorithms from existing research (Fig. [1(b)](#S1.F1.sf2)-[1(d)](#S1.F1.sf4)) under one umbrella, which have focused only on special cases of our generalized sporadic DFL approach. We conduct a comprehensive theoretical analysis to characterize DFL convergence under sporadicity, and experimentally demonstrate the advantages in resource efficiency obtained by properly accounting for these factors.
The following summarizes our main contributions:

- •
We propose Decentralized Sporadic Federated Learning (DSpodFL), which generalizes the notion of sporadicity in DFL (Sec. [3](#S3)). By accounting for sporadic computation and communication simultaneously, DSpodFL subsumes several well-known DFL methods, e.g., DGD (Nedic & Ozdaglar, ), RG (Koloskova et al., ), and DFedAvg (Sun et al., ) (or Decentralized Local SGD), which assume determinism in local updates, inter-client communications, or both. DSpodFL’s probabilistic approach to client participation in effect adjusts the frequency of both SGD computations and ML model aggregations by allowing clients to conduct these processes intermittently without delaying DFL training.
- •
We analytically characterize the convergence behavior of DSpodFL under mild assumptions on the communication graph, data heterogeneity, and gradient noises (Sec. [4](#S4)). Our analysis reveals several insights, including that DSpodFL obtains a geometric convergence rate to a neighborhood of the globally optimal ML model for a constant SGD step size (Theorem [4.11](#S4.Thmtheorem11)).
We show that the optimality gap is directly proportional to the step size, and reveal how it depends on the connectivity of the communication graph, participation probabilities, and dataset heterogeneity. We also provide results under a diminishing step size (App. [M](#A13)), and for non-convex loss functions satisfying the Polyak-Lojasiewicz condition (App. [Q](#A17)).
- •
Our numerical experiments (Sec. [5](#S5)) demonstrate that DSpodFL obtains significant improvements over DFL baselines in terms of the accuracy-delay tradeoff for several ML tasks in heterogeneous network settings. Further, we find that DSpodFL provides robustness to the degree of data heterogeneity across clients, and the strongest performance as the graph connectivity changes.

## 2 Related Works

Table [1](#S2.T1) summarizes key contributions of our work relative to the most closely related literature in centralized and decentralized FL. To the best of our knowledge, our work is the first to consider sporadic SGDs and aggregations simultaneously in the fully decentralized (i.e., serverless) setting. The last three columns in the table are properties of our analysis. Our analysis provides convergence guarantees for last iterates, as opposed to average iterates over all time, under milder assumptions on data heterogeneity and graph connectivity than existing works, as we will elaborate in Sec. [4](#S4).
We organize the rest of this section around the two dimensions of sporadicity in DFL which DSpodFL integrates.

**Table 1: Summary of six key properties of our work and the degrees to which they have been addressed in recent papers.**
| Paper | Fully | Sporadic | Sporadic | Generalized Data | Loose Graph | Last Iterates |
| --- | --- | --- | --- | --- | --- | --- |
| Decentralized | SGDs | Aggregations | Heterogeneity (^1^11In Assumption [4.1](#S4.Thmtheorem1)-[(c)](#S4.I2.i3), we consider a more general/milder data heterogeneity assumption based on two parameters $\delta$ and $\zeta$. This assumption is obtained through $\beta$-smoothness rather than restricting the gradient norms to a constant upper bound.) | Connectivity (^2^22In Assumption [4.3](#S4.Thmtheorem3), we neither require the underlying network graph to be static, nor $B$-connected. We instead make a milder assumption that every communication link is expected to be activated infinitely many times as the number of iterations approaches infinity.) | Convergence |  |
| (Maranjyan et al., ) |  | ✓ |  |  |  | ✓ |
| (Koloskova et al., ) | ✓ |  | ✓ | ✓ | ✓ |  |
| (Yang et al., ) |  | ✓ | ✓ |  |  |  |
| (Wang & Nedic, ) | ✓ |  |  |  |  | ✓ |
| (Sun et al., ) | ✓ |  |  |  |  | ✓ |
| (Mishchenko et al., ) |  |  |  |  |  |  |
| Ours | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |

Sporadic SGDs. In our paper, sporadicity in local SGDs is modeled through clients using a step size of 0 0 at some iterations. A similar idea of uncoordinated step sizes emerged in the gradient tracking literature (Nedić et al., ; Xin et al., ; Pu et al., ). The recent work (Wang & Nedic, ) is the closest to ours in this regard, focusing on a DGD-like algorithm. Nevertheless, the sporadic nature of clients conducting learning operations introduces key modeling challenges for DSpodFL.

Other works in centralized AI/ML (Stich, ; Lin et al., ; Woodworth et al., ) and FL (McMahan et al., ; Karimireddy et al., ; Mishchenko et al., ) have proposed algorithms with multiple local updates between consecutive model aggregations. However, these works focus on a fixed number of SGDs across clients. In this respect, (Yang et al., ; Maranjyan et al., ) propose methods in which at each round of training, the number of SGD steps can differ for each client. Our focus on the fully decentralized setting introduces the dimension of consensus-based aggregations to our analysis.

A few recent works have also considered decentralized counterparts of fixed local SGD methods (Nguyen et al., ; Liu et al., ; Sun et al., ). Again, our focus is on the sporadic case, to understand the consequences of enabling each client to choose its own number of local updates. This is perhaps the most practical case in a fully decentralized scenario, where it is unclear how to globally coordinate client behavior. Moreover, DSpodFL subsumes decentralized fixed local SGD methods as a special case.

Sporadic aggregations. Sporadicity in communications for distributed consensus formation has been studied in randomized gossip (RG) algorithms.
DSpodFL generalizes some of the well-known results from the RG literature to include sporadicity in SGDs as well.
Works such as Even et al. (); Boyd et al. (); Pu & Nedić () study gossip algorithms with only two clients conducting consensus at each iteration, while (Koloskova et al., ; Kong et al., ; Chen et al., ; Zhu et al., ) allow more general mixing matrices, similar to our work.
In another direction, Srivastava & Nedic (); Lian et al. (); Bornstein et al. (); Even et al. () have studied asynchronous DFL, a similar idea to sporadic aggregations.

Koloskova et al. () unify several existing DGD algorithms, under similar generalized data heterogeneity and graph connectivity assumptions that we consider in our analysis. DSpodFL can be seen as taking this a step further to integrate sporadic SGDs into the analysis as well. Overall, different from all these works, we present a more general framework to analyze the effects of sporadic SGDs and sporadic aggregations simultaneously in DFL.

## 3 Methodology and Algorithm

In this section, we formalize our DSpodFL methodology and the notions of sporadicity. A summary of notation used throughout this paper can be found in Appendix [A](#A1).

### 3.1 DSpodFL : Decentralized FL with Sporadicity

We consider a DFL architecture consisting of $m$ clients indexed by $\mathcal{M}:=\{1,\ldots,m\}$. Training proceeds in a series of iterations $k=1,...,K$. At each time $k$, the clients are connected through a set of communication links modeled as a time-varying graph $\mathcal{G}^{(k)}=(\mathcal{M},\mathcal{E}^{(k)})$, where $\mathcal{E}^{(k)}$ denotes the edge set of the graph. The goal is for the clients to discover the globally optimal model $\mathbf{\theta}^{\star}=\operatorname*{argmin}_{\theta\in\mathbb{R}^{n}}{F{(\mathbf{\theta})}}$, while conducting stochastic gradient descent on their local loss functions $F_{i}{(\mathbf{\theta})}$ and exchanging model parameters with their one-hop neighbors. Here,

$$ $F{(\mathbf{\theta})}=\frac{1}{m}\sum_{i=1}^{m}{F_{i}{\mathbf{(\theta)}}},\quad F_{i}{\mathbf{(\theta)}}=\sum_{(\mathbf{x},y)\in\mathcal{D}_{i}}{\ell_{(\mathbf{x},y)}{(\mathbf{\theta})}},\vspace{-2.5mm}$ (1) $$

in which $\mathcal{D}_{i}$ is the local dataset of client $i\in\mathcal{M}$, $(\mathbf{x},y)$ denotes a data point with features $\mathbf{x}$ and label $y$, and $\ell_{(\mathbf{x},y)}{(\mathbf{\theta})}$ is the loss incurred by ML model $\mathbf{\theta}$ on a data point $(\mathbf{x},y)$.

Goal and motivation. In the DFL setup, each client $i\in\mathcal{M}$ has its own ML model $\mathbf{\theta}_{i}$. Therefore, minimizing the global loss function in Eq. ([1](#S3.E1)) will be achieved under $\mathbf{\theta}_{1}=\mathbf{\theta}_{2}=\cdots=\mathbf{\theta}_{m}=\mathbf{\theta}^{\star}$. This means that the clients need to reach a consensus over their model parameters alongside implementing gradient descent (Nedic, ).
To this end, it is necessary to consider an effective consensus mechanism in the decentralized setup of DFL. Here, it is important to consider the heterogeneity in communications/computations capabilities of clients in the system, so that we capture when clients remain active not only during local SGD but also during the model transmission process for aggregations.

DSpodFL framework. Under DSpodFL, client updates are modeled in the following generalized manner:

$$ $\mathbf{\theta}_{i}^{(k+1)}=\mathbf{\theta}_{i}^{(k)}+\underbrace{\sum_{j=1}^{m}{r_{ij}\left(\mathbf{\theta}_{j}^{(k)}-\mathbf{\theta}_{i}^{(k)}\right)\hat{v}_{ij}^{(k)}}}_{\text{Aggregation}}-\underbrace{\alpha^{(k)}\mathbf{g}_{i}^{(k)}v_{i}^{(k)}}_{\text{SGD}},\vspace{-0.5mm}$ (2) $$

where $\theta_{i}^{(k)}$ is the vector of model parameters of client $i$ at iteration $k$, and $\mathbf{g}_{i}^{(k)}=\nabla{F_{i}{(\theta_{i}^{(k)})}}+\mathbf{\epsilon}_{i}^{(k)}$ is the local stochastic gradient of client $i$ at iteration $k$, with $\mathbf{\epsilon}_{i}^{(k)}$ being the SGD noise. In Eq. ([2](#S3.E2)), $v_{i}^{(k)}$ is a binary indicator variable, capturing the sporadicity in SGD iterations, which is $1$ if the client performs SGD in that iteration and 0 0 otherwise. Similarly, $\hat{v}_{ij}^{(k)}$ is an indicator variable capturing the sporadicity in model aggregations, which indicates whether the link $(i,j)$ is being used for communications at iteration $k$ or not. The mixing weight assigned to the link $(i,j)$ is denoted as $r_{ij}$ and can be defined using the Metropolis-Hastings heuristic (Boyd et al., ) as $r_{ij}=1/{(1+\max{\{\lvert\mathcal{N}_{i}\rvert,\lvert\mathcal{N}_{j}\rvert\}})}$ when $j\in\mathcal{N}_{i}$, and 0 0 if $j\notin\mathcal{N}_{i}$, in which $\mathcal{N}_{i}$ is the set of neighbors of client $i$. $r_{ij}$ can be chosen differently as long as the matrix $\mathbf{R}={[r_{ij}]}_{1\leq i,j\leq m}$ is doubly stochastic.

Matrix form of updates in DSpodFL. We can rewrite the update rule given in Eq. ([2](#S3.E2)) compactly as

$$ $\mathbf{\Theta}^{(k+1)}=\mathbf{P}^{(k)}\mathbf{\Theta}^{(k)}-\alpha^{(k)}\mathbf{V}^{(k)}\mathbf{G}^{(k)},$ (3) $$

where $\mathbf{\Theta}^{(k)}$ and $\mathbf{G}^{(k)}$ are matrices with their rows comprised of $(\mathbf{\theta}_{i}^{(k)})^{T}$ and $(\mathbf{g}_{i}^{(k)})^{T}$, respectively, and $\mathbf{V}^{(k)}$ is a diagonal matrix with $v_{i}^{(k)}$ as its diagonal entries for $1\leq i\leq m$. Here, $\mathbf{G}^{(k)}=\mathbf{\nabla}^{(k)}+\mathbf{E}^{(k)}$, where $\mathbf{\nabla}^{(k)}$ (respectively, $\mathbf{E}^{(k)}$) is the matrix whose $i$ th row is $(\nabla{F_{i}{(\mathbf{\theta}_{i}^{(k)})}})^{T}$ (respectively, $(\mathbf{\epsilon}_{i}^{(k)})^{T}$) for $1\leq i\leq m$. Also, the elements of $\mathbf{P}^{(k)}={[p_{ij}^{(k)}]}_{1\leq i,j\leq m}$ are defined as

$$ $p_{ij}^{(k)}=\begin{cases}r_{ij}\hat{v}_{ij}^{(k)}&i\neq j\\ 1-\sum_{j=1}^{m}{r_{ij}\hat{v}_{ij}^{(k)}}&i=j\end{cases}.$ (4) $$

Note that the random matrix $\mathbf{P}^{(k)}$, by definition, is doubly stochastic and symmetric with non-negative entries, i.e., $\mathbf{P}^{(k)}\mathbf{1}=\mathbf{1}$ and $(\mathbf{P}^{(k)})^{T}=\mathbf{P}^{(k)}$. Finally, in our analysis, we will find it useful to define a row vector $\bar{\theta}^{(k)}$ which is the average of vectors $\theta_{i}^{(k)}$ across clients.
Based on Eq. ([3](#S3.E3)),

$$ $\mathbf{\bar{\theta}}^{(k+1)}=\mathbf{\bar{\theta}}^{(k)}-\alpha^{(k)}\overline{\mathbf{g}v}^{(k)},$ (5) $$

where $(\overline{\mathbf{g}v}^{(k)})^{T}=(1/m)\sum_{i=1}^{k}{\mathbf{g}_{i}^{(k)}v_{i}^{(k)}}$. The full pseudocode of DSpodFL is given in Appendix [B](#A2).

### 3.2 Key Takeaways from DSpodFL

Interpreting sporadicity. The novelty of our framework lies in the integration of two sporadicity terms (i.e, indicator variables $v_{i}^{(k)}$ and $\hat{v}_{ij}^{(k)}$) to model the impacts of resource heterogeneity in DFL. Specifically, a client can achieve computational efficiency by setting $v_{i}^{(k)}=0$ in iterations where computing new SGDs at client $i$ does not significantly benefit the statistical/inference performance of the decentralized system.
Similarly, a pair of clients can achieve communication efficiency
by setting $\hat{v}_{ij}^{(k)}=0$ when using link $(i,j)$ at iteration $k$ for exchanging model parameters among clients $i$ and $j$ does not considerably improve the statistical/inference performance of the system. This incorporation of sporadicity increases the degrees of freedom DSpodFL accounts for, thereby distinguishing it from the literature in Sec. [2](#S2).

Unifying existing work. The difference between our methodology and other DFL algorithms is illustrated in Fig. [1](#S1.F1). There, we observe how the other approaches are subsumed by our DSpodFL framework, as they correspond to different values of the indicator variables $v_{i}^{(k)}$ and $\hat{v}_{ij}^{(k)}$. Moreover, we note that local updates and aggregations in the DGD (Fig. [1(b)](#S1.F1.sf2)) and DFedAvg (Fig. [1(c)](#S1.F1.sf3)) methods are carried out in a deterministic fashion, while sporadicity is introduced to them in RG (Fig. [1(d)](#S1.F1.sf4)) and DSpodFL (Fig. [1(e)](#S1.F1.sf5)).

## 4 Convergence Analysis

In this section, we present the convergence analysis of DSpodFL.
Our main theoretical results are provided in Secs. [4.2](#S4.SS2), [4.3](#S4.SS3) and [4.4](#S4.SS4). Other theoretical results, including some lemmas on which the main results are obtained, are relegated to the appendices.

### 4.1 Definitions and Assumptions

We present several definitions and assumptions to be used in the analysis. More detailed mathematical statements of these assumptions are provided in Appendix [C](#A3).

###### Assumption 4.1 (Loss functions) .

The local loss function $F_{i}$ at each client $i\in\mathcal{M}$ is
(a) $\beta_{i}$-smooth and
(b) $\mu_{i}$-strongly convex.
Also,
(c) the gradient diversity across clients is measured via $\delta_{i}>0$ and $\zeta_{i}\geq 0$ as $\left\|\nabla{F{\left(\mathbf{\theta}\right)}}-\nabla{F_{i}{\left(\mathbf{\theta}\right)}}\right\|\leq\delta_{i}+\zeta_{i}\left\|\mathbf{\theta}-\mathbf{\theta^{\star}}\right\|,$
for all $\mathbf{\theta}\in\mathbb{R}^{n}$, $i\in\mathcal{M}$. We also let $\delta=\max_{i\in\mathcal{M}}{\delta_{i}}$ and $\zeta=\max_{i\in\mathcal{M}}{\zeta_{i}}$.

In Assumption [4.1](#S4.Thmtheorem1)-[(c)](#S4.I2.i3), we do not make the stricter assumption of $\zeta=0$ that is found in some works discussed in Table [1](#S2.T1). The addition of this proximal term makes our bounds tighter and causes our theoretical analysis to be more conclusive (Lin et al., ).

###### Assumption 4.2 (Stochastic gradient noise) .

We make the following standard assumptions on the stochastic gradient noise $\mathbf{\epsilon}_{i}^{(k)}$ for all $i\in\mathcal{M}$ and all $k\geq 0$:

- (a)
The gradient noise of each client is zero mean with a bounded variance $\sigma_{i}^{2}$. We also let $\sigma^{2}=\max_{i\in\mathcal{M}}{\sigma_{i}^{2}}$.
- (b)
The random vectors $\mathbf{\epsilon}_{i}^{(k)}$ and indicator variables $v_{i}^{(k)}$ and $\hat{v}_{ij}^{(k)}$ are all mutually uncorrelated.

###### Assumption 4.3 (Asymptotic graph connectivity) .

Denote the asymptotic graph union of the underlying time-varying network graphs by $\mathcal{G}=\left(\mathcal{M},\lim_{K\rightarrow\infty}\cup_{k=0}^{K}{\mathcal{E}^{(k)}}\right)$. We assume that $\mathcal{G}$ is connected, and that for every edge $e_{ij}$ in $\mathcal{G}$, we have $e_{ij}\in\mathcal{E}^{(k)}$ for infinitely many $k$.

Assumption [4.3](#S4.Thmtheorem3) is milder than similar assumptions made in existing works, e.g., considering a static connected graph (Mishchenko et al., ; Sun et al., ; Wang & Nedic, ) or a $B$-connected graph (Nedic & Ozdaglar, ). See Table [1](#S2.T1) for a further comparison to these works.

###### Definition 4.4 .

We define $\mathbf{\Xi}^{(k)}$ as the collection of all random variables $v_{i}^{(r)}$, $\hat{v}_{ij}^{(r)}$ and $\mathbf{\epsilon}_{i}^{(r)}$ for all $(i,j)\in\mathcal{M}^{2}$ and all iterations $0\leq r\leq k$. With this, the expected consensus rate (Koloskova et al., ) can be characterized via parameter $\tilde{\rho}^{(k)}$ as
$\mathbb{E}_{\mathbf{\Xi}^{(k)}}{[{\|\mathbf{P}^{(k)}\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\mathbf{\bar{\theta}}^{(k)}\|}^{2}]}\leq\tilde{\rho}^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[{\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\mathbf{\bar{\theta}}^{(k)}\|}^{2}]}$, where $\tilde{\rho}^{(k)}$ is the spectral radius of the expected mixing matrix,
which we present and prove in Lemma [D.4](#A4.Thmtheorem4)-[(c)](#A4.I2.i3) in the Appendix.(^3^33$\mathbb{E}_{X}{\left[\cdot\right]}$ denotes the expectation operator with respect to the random variable $X$.)

In order to generalize our theory to non-convex loss functions, in Sec. [4.5](#S4.SS5), we will replace the strong convexity assumption in Assumption [4.1](#S4.Thmtheorem1)-[(b)](#S4.I1.i2) with the milder Polyak-Lojasiewicz (PL) condition (Xin et al., ):

###### Assumption 4.5 (PL inequality) .

The global loss function $F$ meets the PL condition ${\|\nabla{F}(\mathbf{\theta})\|}^{2}\geq 2\mu\left(F(\mathbf{\theta})-F^{\star}\right)$ with some $\mu>0$, where $F^{\star}$ is the optimal value of $F$.

Finally, to facilitate the analysis, we define the expected values of the indicator random variables in DSpodFL:

###### Definition 4.6 (Indicator variables) .

The expected values of indicator random variables $v_{i}^{(k)}$ and $\hat{v}_{ij}^{(k)}$ are defined as

$$ $\vspace{-1mm}\begin{gathered}\mathbb{E}_{v_{i}^{(k)}}{\left[v_{i}^{(k)}\right]}=d_{i}^{(k)},\\ \mathbb{E}_{\hat{v}_{ij}^{(k)}}{\left[\hat{v}_{ij}^{(k)}\right]}=\mathbb{E}_{\hat{v}_{ji}^{(k)}}{\left[\hat{v}_{ji}^{(k)}\right]}=b_{ij}^{(k)}=b_{ji}^{(k)},\end{gathered}\vspace{-1mm}$ $$

in which $d_{i}^{(k)}\in(0,1]$ captures client $i$’s probability of conducting SGD, and $b_{ij}^{(k)}\in(0,1]$ captures the probability of link $(i,j)$ being used for communication, at iteration $k$. In addition, we define $d_{\max}^{(k)}=\max_{i\in\mathcal{M}}{d_{i}^{(k)}}$ and $d_{\min}^{(k)}=\min_{i\in\mathcal{M}}{d_{i}^{(k)}}$. Note that the probability distributions of these indicator variables can be time-varying, allowing for a wide range of profiles for $v_{i}^{(k)}$ and $\hat{v}_{ij}^{(k)}$.

###### Assumption 4.1 (Loss functions) .

###### Assumption 4.2 (Stochastic gradient noise) .

###### Assumption 4.3 (Asymptotic graph connectivity) .

###### Definition 4.4 .

###### Assumption 4.5 (PL inequality) .

###### Definition 4.6 (Indicator variables) .

### 4.2 Average Model Error and Consensus Error

To characterize the convergence behavior of DSpodFL, we first provide an upper bound on the average model error $\mathbb{E}_{\mathbf{\Xi}^{(k)}}[\|\bar{\mathbf{\theta}}^{(k+1)}-\mathbf{\theta}^{\star}\|^{2}]$ (Lemma [4.7](#S4.Thmtheorem7)), and also upper bound the consensus error $\mathbb{E}_{\mathbf{\Xi}^{(k)}}{[{\|\mathbf{\Theta}^{(k+1)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k+1)}\|}^{2}]}$ (Lemma [4.8](#S4.Thmtheorem8)), at each $k$.

###### Lemma 4.7 ( Average model error ) .

(See Appendix [G](#A7) for the proof.)
Let Assumptions [4.1](#S4.Thmtheorem1) and [4.2](#S4.Thmtheorem2) hold. For each iteration $k\geq 0$, we have the following bound on the expected average model error:

$\mathbb{E}_{\mathbf{\Xi}^{(k)}}[\|\bar{\mathbf{\theta}}^{(k+1)}-\mathbf{\theta}^{\star}\|^{2}]\leq\phi_{11}^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[{\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\|}^{2}]}+\phi_{12}^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[{\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\|}^{2}]}+\psi_{1}^{(k)}$,

where $\phi_{11}^{(k)}=1-\mu\alpha^{(k)}(1+\mu\alpha^{(k)}-{(\mu\alpha^{(k)})}^{2})+\frac{2\alpha^{(k)}}{\mu}(1+\mu\alpha^{(k)})(1-d_{\min}^{(k)})\beta^{2}$, $\phi_{12}^{(k)}=(1+\mu\alpha^{(k)})\frac{\alpha^{(k)}d_{\max}^{(k)}\beta^{2}}{m\mu}$, and $\psi_{1}^{(k)}=\frac{2\alpha^{(k)}}{\mu}(1+\mu\alpha^{(k)})(1-d_{\min}^{(k)})\delta^{2}+\frac{{(\alpha^{(k)})}^{2}d_{\max}^{(k)}\sigma^{2}}{m}$.

In Lemma [4.7](#S4.Thmtheorem7), the upper bound on the expected error at iteration $k+1$ is expressed in terms of the scaled expected error $\phi_{11}^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[{\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\|}^{2}]}$, the scaled consensus error $\phi_{12}^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[{\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\|}^{2}]}$ (which will be presented in Lemma [4.8](#S4.Thmtheorem8)), and the scalar $\psi_{1}^{(k)}$, all at iteration $k$. It is important to note that this bound is general and reduces to the bound for DGD when $d_{\min}^{(k)}=1$,
i.e., $v_{i}^{(k)}=1$ for all $i\in\mathcal{M}$ (e.g., see Lemma 5-b of Zehtabi et al. ()). We next bound the consensus error in the following lemma.

###### Lemma 4.8 ( Consensus error ) .

(See Appendix [J](#A10) for the proof.)
Let Assumptions [4.1](#S4.Thmtheorem1)-[4.3](#S4.Thmtheorem3) hold. For each iteration $k\geq 0$, we have the following bound on the expected consensus error:

$\mathbb{E}_{\mathbf{\Xi}^{(k)}}{[{\|\mathbf{\Theta}^{(k+1)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k+1)}\|}^{2}]}\leq\phi_{21}^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[{\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\|}^{2}]}\\
+\phi_{22}^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[{\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\|}^{2}]}+\psi_{2}^{(k)}$,

where $\phi_{21}^{(k)}=3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}md_{\max}^{(k)}{(\alpha^{(k)})}^{2}(\zeta^{2}+2\beta^{2}(1-d_{min}^{(k)}))$, $\phi_{22}^{(k)}=\frac{1+\tilde{\rho}^{(k)}}{2}+3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}d_{\max}^{(k)}{(\alpha^{(k)})}^{2}(\zeta^{2}+2\beta^{2})$, and $\psi_{2}^{(k)}=m{(\alpha^{(k)})}^{2}d_{\max}^{(k)}(3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}\delta^{2}+\sigma^{2})$,
where $\tilde{\rho}^{(k)}$ is defined in Definition [4.4](#S4.Thmtheorem4) and Lemma [D.4](#A4.Thmtheorem4)-[(c)](#A4.I2.i3).

Our consensus error bound in Lemma [4.8](#S4.Thmtheorem8) is also a general result, and reduces to a bound for DGD when (a) $\zeta=0$ and (b) $d_{min}^{(k)}=1$, resulting $d_{i}^{(k)}=1$ for all $i$. This will result in $\phi_{21}^{(k)}=0$ (e.g., see Lemma 5-c in (Zehtabi et al., )).

###### Lemma 4.7 ( Average model error ) .

###### Lemma 4.8 ( Consensus error ) .

### 4.3 Connecting with the Spectral Radius

We observe that the the average model error and consensus error from Lemmas [4.7](#S4.Thmtheorem7) and [4.8](#S4.Thmtheorem8) are coupled. We next characterize their joint evolution over the training process.

###### Definition 4.9 (Error vector) .

Denote the error vector at iteration $k$ with $\nu^{(k)}$, defined as the concatenation of the average model error and the consensus error:

$$ $\nu^{(k)}=\begin{bmatrix}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\bar{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\right]}\\ \mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\mathbf{\bar{\theta}}^{(k)}\right\|}^{2}\right]}\end{bmatrix}.$ (6) $$

Using this definition, it follows that

$$ $\nu^{(k+1)}\leq\mathbf{\Phi}^{(k)}\nu^{(k)}+\mathbf{\Psi}^{(k)},$ (7) $$

with $\mathbf{\Phi}^{(k)}={[\phi_{ij}^{(k)}]}_{1\leq i,j\leq 2}$ and $\mathbf{\Psi}^{(k)}=[\psi_{1}^{(k)}\quad\psi_{2}^{(k)}]^{T}$. Recursively expanding the inequalities in Eq. ([7](#S4.E7)) gives us an explicit relationship between the expected model error and consensus error at each iteration, and their initial values:

$$ $\nu^{(k+1)}\leq\mathbf{\Phi}^{(k:0)}\nu^{(0)}+\sum_{r=1}^{k}{\mathbf{\Phi}^{(k:r)}\mathbf{\Psi}^{(r-1)}}+\mathbf{\Psi}^{(k)},$ (8) $$

where we have defined $\mathbf{\Phi}^{(k:s)}=\mathbf{\Phi}^{(k)}\mathbf{\Phi}^{(k-1)}\cdots\mathbf{\Phi}^{(s)}$ for $k>s$, and $\mathbf{\Phi}^{(k:k)}=\mathbf{\Phi}^{(k)}$. Note that $\nu^{(0)}=[{\|\mathbf{\bar{\theta}}^{(0)}-\mathbf{\theta}^{\star}\|}^{2},{\|\mathbf{\Theta}^{(0)}-\mathbf{1}_{m}\mathbf{\bar{\theta}}^{(0)}\|}^{2}]^{T}$.

Thus, a sufficient condition for convergence of DSpodFL
is that the spectral radius of the matrix $\mathbf{\Phi}^{(k)}$ is less than one, i.e., $\rho(\mathbf{\Phi}^{(k)})<1$. In the following proposition, we show this can be enforced through appropriate choice of step size.

###### Proposition 4.10 .

(See Appendix [K](#A11) for the proof.)
Let Assumptions [4.1](#S4.Thmtheorem1)-[4.3](#S4.Thmtheorem3) hold. If the step size satisfies the following condition for all $k\geq 0$:

$\alpha^{(k)}<\min\Bigg{\{}\frac{1}{\mu},\frac{1}{2\sqrt{3d_{max}^{(k)}}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}},$

${\left(\frac{\mu}{12\left(\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)\right)}\right)}^{1/3}{\left(\frac{1-\tilde{\rho}^{(k)}}{2d_{max}^{(k)}\beta}\right)}^{2/3}\Bigg{\}},$

then we have $\rho{\left(\mathbf{\Phi}^{(k)}\right)}<1$ for all $k\geq 0$, in which $\rho{(\cdot)}$ denotes the spectral radius of a given matrix, and $\mathbf{\Phi}^{(k)}$ is given in Eq. ([7](#S4.E7)). The exact value of $\rho{(\mathbf{\Phi}^{(k)})}$ follows as

$\rho{(\mathbf{\Phi}^{(k)})}=\frac{3+\tilde{\rho}^{(k)}}{4}-A^{(k)}\alpha^{(k)}+B^{(k)}{(\alpha^{(k)})}^{2}+\frac{1}{2}\sqrt{{(\frac{1-\tilde{\rho}^{(k)}}{2}-2(A^{(k)}\alpha^{(k)}+B^{(k)}{(\alpha^{(k)})}^{2}))}^{2}+C^{(k)}{(\alpha^{(k)})}^{3}},$

where $A^{(k)}=\frac{2}{\mu}(\Gamma_{2}^{\star(k)}-1)(1-d_{min}^{(k)})\beta^{2}$,

$B^{(k)}=\frac{3}{2}\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}d_{\max}^{(k)}(\zeta^{2}+2\beta^{2})$ and

$C^{(k)}=24\frac{\beta^{2}}{\mu}\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}{(d_{\max}^{(k)})}^{2}(\zeta^{2}+2\beta^{2}(1-d_{min}^{(k)}))$. The value for the constant $\Gamma_{2}^{\star(k)}>1$ is given in Appendix [K](#A11).

Proposition [4.10](#S4.Thmtheorem10) implies that $\lim_{k\to\infty}{\mathbf{\Phi}^{(k:0)}}=0$ in Eq. ([8](#S4.E8)), which means the consensus and average model errors will converge. The exact convergence rate will depend on the choice of step size $\alpha^{(k)}$. Furthermore, since the first expression on the right-hand side of Eq. ([8](#S4.E8)) asymptotically approaches zero, Proposition [4.10](#S4.Thmtheorem10) implies that the non-negative optimality gap is determined by the sum $\sum_{r=1}^{k}{\mathbf{\Phi}^{(k:r)}\mathbf{\Psi}^{(r-1)}}+\mathbf{\Psi}^{(k)}$. Specifically, through
the values of $\mathbf{\Psi}^{(k)}$, we see that being able to achieve a zero optimality gap depends on the choices of $\alpha^{(k)}$ and $d_{i}^{(k)}$ (See Appendix [M](#A13) for further discussion).

Proposition [4.10](#S4.Thmtheorem10) can be restated considering only the initial step size $\alpha^{(0)}$ under certain conditions. Specifically, this occurs if the step size $\alpha^{(k)}$ is non-increasing (i.e., $\alpha^{(k+1)}\leq\alpha^{(k)}$), the SGD probabilities $d_{i}^{(k)}$ and aggregation probabilities are constant (i.e., $d_{i}^{(k)}=d_{i}$ and $b_{ij}=b_{ij}$, respectively, for all $k\geq 0$). Hence, we can obtain a condition only on $\alpha^{(0)}$ in Proposition [4.10](#S4.Thmtheorem10) by dropping the iteration superscripts $k$, and defining $d_{max}=\max_{i\in\mathcal{M}}{d_{i}}$ and $d_{min}=\min_{i\in\mathcal{M}}{d_{i}}$.

###### Definition 4.9 (Error vector) .

###### Proposition 4.10 .

### 4.4 Main Theorem and Discussions

Using the above results, we characterize the convergence behavior of DSpodFL in the following theorem.

###### Theorem 4.11 ( Convergence result ) .

(See Appendix [L](#A12) for the proof.)
Let Assumptions [4.1](#S4.Thmtheorem1)-[4.3](#S4.Thmtheorem3) hold. If a constant step size $\alpha^{(k)}=\alpha$ with $\alpha>0$ satisfying the conditions outlined in Proposition [4.10](#S4.Thmtheorem10) is employed, and the SGD and aggregation probabilities are set to constant values, i.e., $d_{i}^{(k)}=d_{i}$ and $b_{ij}^{(k)}=b_{ij}$ for all $i\in\mathcal{M}$, $(i,j)\in\mathcal{M}^{2}$ and $k\geq 0$, respectively, then we can rewrite Eq. ([8](#S4.E8)) as

$$ $\nu^{(k+1)}\leq{\rho{\left(\mathbf{\Phi}\right)}}^{k+1}\nu^{(0)}+\frac{1}{1-\rho{\left(\mathbf{\Phi}\right)}}\mathbf{\Psi},\vspace{-1mm}$ (9) $$

in which $\mathbf{\Psi}=\mathbf{\Psi}^{(k)}$ and $\mathbf{\Phi}=\mathbf{\Phi}^{(k)}$ from Eq. ([7](#S4.E7)) for all $k$ given the constant $d_{i}$ and $b_{ij}$.
On letting $k\to\infty$, we obtain

$$ $\displaystyle\limsup_{k\to\infty}{\nu^{(k+1)}}$ (10) $\displaystyle=\frac{\alpha}{1-\rho{\left(\mathbf{\Phi}\right)}}\begin{bmatrix}\frac{2}{\mu}\left(1+\mu\alpha\right)\left(1-d_{min}\right)\delta^{2}+\frac{\alpha d_{max}\sigma^{2}}{m}\\ m\alpha\cdot d_{max}\left(3\frac{1+\tilde{\rho}}{1-\tilde{\rho}}\delta^{2}+\sigma^{2}\right)\end{bmatrix}.$ $$

where $\nu^{(k)}$ is as defined in Eq. ([6](#S4.E6)) of Definition [4.9](#S4.Thmtheorem9) and $\tilde{\rho}$ is the spectral radius of the expected mixing matrix from Definition [4.4](#S4.Thmtheorem4). Note
Proposition [4.10](#S4.Thmtheorem10) ensures $\rho(\mathbf{\Phi})<1$.

Convergence guarantee. The bound in Eq. ([9](#S4.E9)) indicates that by using a constant step size, DSpodFL achieves a geometric convergence rate. Eq. ([10](#S4.E10)) characterizes the asymptotic optimality gap as $k\to\infty$. We observe that this optimality gap is proportional to the step size $\alpha$, and thus choosing a smaller step size will linearly reduce this gap. Moreover, we can see how both the convergence rate $\rho(\mathbf{\Phi})^{k+1}$ and the optimality gap in Eq. ([10](#S4.E10)) depend on the connectivity of the communication graph (through $\tilde{\rho}$), the number of clients $m$, the frequency of computations $d_{i}$, the frequency of communications $b_{ij}$ (through $\tilde{\rho}$), the SGD noise $\sigma^{2}$, and other parameters related to the loss function and the dataset: $\mu$, $\beta$, $\delta$ and $\zeta$. Note that the data heterogeneity parameters $\beta$ and $\zeta$ are encapsulated in $\rho(\mathbf{\Phi})$.

Effects of sporadicity terms. Neither $\rho{(\mathbf{\Phi})}$ (as given by Proposition [4.10](#S4.Thmtheorem10)) nor either of the two terms in the optimality gap vector given in Eq. ([10](#S4.E10)) can be guaranteed to be small just by varying $d_{i}$. The optimal values of $d_{max}$ and $d_{min}$ to get a faster convergence rate and a lower optimality gap depends on other problem-related parameters. On the other hand, the communication probabilities $b_{ij}$ affect the bounds through the spectral radius parameter $\tilde{\rho}$ (the exact relationship is in Appendix [I](#A9)). To elaborate, increasing the frequency of communications $b_{ij}$ helps us achieve tighter bounds by lowering the spectral radius $\tilde{\rho}$. However, as we will illustrate in Sec. [5](#S5), this is not always desirable since choosing $d_{i}$ and $b_{ij}$ solely based on improving the convergence rate will result in poor resource consumption. Thus, the variables $d_{i}$ and $b_{ij}$ control the trade-off between learning performance and the resource efficiency.

We also note that Eqs. ([9](#S4.E9)) and ([10](#S4.E10)) are derived for the consensus error and the average model error themselves, i.e., their last iterates. As summarized in Table [1](#S2.T1), this is an improvement over existing works with sporadic aggregations (Koloskova et al., ; Lian et al., ; Sundhar Ram et al., ) where only the Cesaro sums (i.e., the running averages of the iterates) of these error terms are bounded.

Diminishing step size. We also characterized convergence for the case where a diminishing step size is used. DSpodFL achieves zero optimality gap in this case with a sub-linear convergence rate, i.e., $\mathcal{O}{(\ln{k}/\sqrt{k})}$, matching the rate achieved by existing DGD-based methods. See Appendix [M](#A13) for the detailed result.

###### Theorem 4.11 ( Convergence result ) .

### 4.5 Non-Convex Analysis under the PL Condition

Our discussion so far has revolved around strongly convex loss functions. In the following theorem, we present the convergence behavior of DSpodFL when non-convex losses are used under the PL condition of Assumption [4.5](#S4.Thmtheorem5).

###### Theorem 4.12 ( Non-convex result under the PL condition ) .

(See Appendix [U](#A21) for the proof.)
Let Assumptions [4.1](#S4.Thmtheorem1)-[(a)](#S4.I1.i1), [4.1](#S4.Thmtheorem1)-[(c)](#S4.I2.i3) and [4.2](#S4.Thmtheorem2)-[4.5](#S4.Thmtheorem5) hold. Let a constant step size $\alpha^{(k)}=\alpha$ with $\alpha>0$ satisfying the conditions of Proposition [Q.4](#A17.Thmtheorem4) be employed, and the probabilities of SGDs and aggregations be time-invariant, i.e., $d_{i}^{(k)}=d_{i}$ and $b_{ij}^{(k)}=b_{ij}$, for all $k\geq 0$. Then, the convergence rate is geometric, specifically $\rho(\mathbf{\Phi})^{k+1}$, with an optimality gap

$$ $\displaystyle\limsup_{k\to\infty}{\nu_{nc}^{(k+1)}}$ (11) $\displaystyle=\frac{\alpha^{2}}{1-\rho{\left(\mathbf{\Phi}\right)}}\begin{bmatrix}\frac{\beta}{2}\left[4\left(1-d_{min}\right)\delta^{2}+\frac{d_{max}\sigma^{2}}{m}\right]\\ md_{\max}\left(3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}\delta^{2}+\sigma^{2}\right)\end{bmatrix},$ $$

for $\mathbf{\Phi}$ given in Lemma [Q.2](#A17.Thmtheorem2) and Corollary [Q.3](#A17.Thmtheorem3), and $\nu_{nc}^{(k)}$ defined in Eq. ([32](#A17.E32)). Proposition [Q.4](#A17.Thmtheorem4) ensures $\rho(\mathbf{\Phi})<1$.

We see that the optimality gap in Eq. ([11](#S4.E11)) is proportional to the square of the step size, i.e., $\alpha^{2}$. Thus, by choosing a smaller step size, we can quadratically reduce this gap. More detailed discussions and results related to the non-convex analysis are provided in Appendix [Q](#A17).

###### Theorem 4.12 ( Non-convex result under the PL condition ) .

## 5 Numerical Evaluation

### 5.1 Experimental Setup

Figure: (a) FMNIST, IID.
Refer to caption: /html/2402.03448/assets/ICML2024/images/Legend.png

Figure: (a) Varying number of labels per client.
Refer to caption: /html/2402.03448/assets/ICML2024/images/Legend.png

Models and datasets. To evaluate our methodology, we consider an image classification task using the Fashion-MNIST (FMNIST) (Xiao et al., ) and CIFAR10 (Krizhevsky et al., ) datasets. We consider two models: linear SVM (Support Vector Machine) and the VGG11 model (Simonyan & Zisserman, ). We use FMNIST to train the SVM model, while CIFAR-10 is adopted for training VGG11.

Implementation details. By default, we consider a network of $m=10$ clients, connected to each other in a decentralized manner via a random geometric graph (RGG) with radius $0.4$ (Penrose, ).
We adopt a constant learning rate $\alpha=0.01$, and use a batch size of $16$. The SGD probability for each client is set to a constant value across training iterations and is randomly chosen according to the Beta distribution $\operatorname*{Beta}(\alpha,\beta)$. Choosing $\alpha=\beta<1$ results in an inverted bell-shaped distribution, which corresponds to scenarios where the clients and communications links exhibit significant heterogeneity (i.e., either abundant or poor in resource availability).
For FMNIST, we use $d_{i}\sim\operatorname*{Beta}(0.5,0.5)$, and for CIFAR10, we use $d_{i}\sim\operatorname*{Beta}(0.8,0.8)$. The aggregation probability $b_{ij}$ for each link is also randomly chosen from the same Beta distribution for each dataset. We consider two different data distribution scenarios: (i) the IID case, where each client receives samples from all of the $10$ classes in the dataset, and (ii) the non-IID case, where each client receives samples belonging to just $1$ class for the FMNIST dataset, and $3$ classes for CIFAR10. Unless stated otherwise, our experiments are done under the non-IID setup.

Baselines. We compare DSpodFL with four baselines that are tailored to decentralized settings: (a) Distributed Gradient Descent (DGD), which is the conventional DFL algorithm, where SGDs and local aggregations occur at every iteration (Nedic & Ozdaglar, ); (b) the Randomized Gossip (RG) algorithm (Koloskova et al., ), which we can also denote as Sporadic Aggregations (with constant SGDs); (c) Sporadic SGDs (with constant aggregations); and (d) Decentralized Federated Averaging (DFedAvg) (Sun et al., ), which is also called Decentralized Local SGD in some papers.
Note that all these baselines can be viewed as special cases of DSpodFL as elaborated in Fig. [1](#S1.F1).

### 5.2 Results and Discussion

Our main results are provided in Figs. [2](#S5.F2) & [3](#S5.F3). We measure the test accuracy of each scheme achieved over the average total delay incurred up to iteration $k$. Specifically, $\tau_{total}^{(k)}=\tau_{trans}^{(k)}+\tau_{proc}^{(k)}$, in which $\tau_{trans}^{(k)}=[\sum_{i=1}^{m}{(1/|\mathcal{N}_{i}|)\sum_{j}{\hat{v}_{ij}^{(k)}/b_{ij}}}]/[\sum_{i=1}^{m}{(1/|\mathcal{N}_{i}|)\sum_{j}{1/b_{ij}}}]$ and $\tau_{proc}^{(k)}=[\sum_{i=1}^{m}{v_{i}^{(k)}/d_{i}}]/[\sum_{i=1}^{m}{1/d_{i}}]$ are the per-client transmission delays incurred across links and processing delays incurred across clients in iteration $k$, respectively.
For a fair comparison, we determine the number of local update steps for the DFedAvg algorithm based on these $d_{i}$, i.e., $D=\lceil(1/m)\sum_{i=1}^{m}{1/d_{i}}\rceil$, where $D$ is the aggregation frequency of DFedAvg shown in Fig. [1](#S1.F1).

Accuracy vs. delay comparisons. Fig. [2](#S5.F2) compares the test accuracies of different schemes in terms of overall delay. Since DSpodFL employs both sporadic SGDs and aggregations, it
outperforms all baselines for both data distributions and models/datasets. In the IID setups presented in Figs. [2(a)](#S5.F2.sf1) and [2(c)](#S5.F2.sf3), we see that the performances of the baselines are reasonably similar. Meanwhile, our DSpodFL method is able to significantly outperform those algorithms by an accuracy margin of $10-20\%$ in the initial stages of training. The differences between the algorithms become more significant for non-IID data distributions as shown in Figs. [2(b)](#S5.F2.sf2) and [2(d)](#S5.F2.sf4). Inter-client communications become more crucial in non-IID setups, as each client has access only to a small portion of the distribution of the whole dataset. Depending on the baseline and dataset, DSpodFL is able to achieve $10-40\%$ improvement in accuracy for a particular delay.

Effects of system parameters. In Fig. [3](#S5.F3), we study the accuracy performance reached by a certain training delay as system parameters are varied. In contrast to Fig. [2](#S5.F2) where client and link capabilities were sampled from the Beta distribution, for completeness, Figs. [3(a)](#S5.F3.sf1), [3(b)](#S5.F3.sf2) and [3(c)](#S5.F3.sf3) are carried out using the uniform distribution. In Fig. [3(a)](#S5.F3.sf1), we can see how increasing the number of labels possessed by each client (i.e., moving from non-IID to IID) improves the achieved accuracy of all methods. Further, our DSpodFL is able to outperform all of baselines regardless of the data distribution. In Fig. [3(b)](#S5.F3.sf2), we see that increasing the radius of the underlying random geometric graph (which controls the density of connections between clients) improves the achievable accuracy for all baselines. Again, DSpodFL performs the best for all choices of radii, confirming the benefit of integrating the notion of sporadicity in both communications and computations. Fig. [3(c)](#S5.F3.sf3) depicts the impact of the number of clients in the system. We see that DSpodFL obtains the largest improvement as the size of the network increases, whereas the baselines are more likely to suffer from communication/computation bottlenecks if weak nodes are added.

Finally, in Fig. [3(d)](#S5.F3.sf4), we analyze the effects of parameters $\alpha$ and $\beta$ in the $\operatorname*{Beta}$ distribution, which control the communication and computation heterogeneity across clients, keeping $\alpha=\beta$. Note that increasing these parameters to $1$ brings the distribution closer to uniform. We see that DSpodFL is robust to the underlying data distribution, and the gap between our approach and other baselines become more significant when the levels of heterogeneity in client and link resources are higher, i.e., lower $\alpha=\beta$. These results further demonstrate the effectiveness of DSpodFL.

Additional results. Further experimental results on (i) accuracy vs. latency plots and (ii) the effects of system parameters, with probabilities generated using uniform and Beta distributions, respectively, are reported in Appendix [V](#A22).

## 6 Conclusion

We proposed DSpodFL, an FL framework that generalizes the notion of sporadicity to fully decentralized scenarios. By considering (i) sporadic gradient computations and (ii) sporadic client-to-client communications simultaneously, our approach tackles the challenges in heterogeneous resource settings and subsumes well-known decentralized optimization algorithms. We analyzed the convergence behavior of DSpodFL, and characterized the relationship between the optimality gap and key parameters, including the sporadicity terms. Through experiments, we demonstrated the advantage of DSpodFL compared to various DFL baselines.

## Appendix A Notation

Arguments for functions are denoted with parentheses, e.g., $f{(x)}$ implies $x$ is an argument for function $f$. The iteration index for a parameter is indicated via superscripts, e.g., $h^{(k)}$ is the value of the parameter $h$ at iteration $k$. client indices are given via subscripts, e.g., $h_{i}^{(k)}$ refers to parameter belonging to client $i$. We write a graph $\mathcal{G}$ with a set of nodes (clients) $\mathcal{V}$ and a set of edges (links) $\mathcal{E}$ as $\mathcal{G}=(\mathcal{V},\mathcal{E})$.

We denote vectors with lowercase boldface, e.g., $\mathbf{x}$, and matrices with uppercase boldface, e.g., $\mathbf{X}$. All vectors $\mathbf{x}\in\mathbb{R}^{d\times 1}$ are column vectors, except in certain cases where average vectors $\bar{\mathbf{x}}\in\mathbb{R}^{1\times d}$ and optimal vectors $\mathbf{w}^{\star}\in\mathbb{R}^{1\times d}$ are row vectors. $\langle\mathbf{x},\mathbf{x}^{\prime}\rangle$ and $\langle\mathbf{X},\mathbf{X}^{\prime}\rangle$ denote the inner product of two vectors $\mathbf{x},\mathbf{x}^{\prime}$ of equal dimensions and the Frobenius inner product of two matrices $\mathbf{X},\mathbf{X}^{\prime}$ of equal dimensions, respectively. Moreover, ${\|\mathbf{x}\|}$ and ${\|\mathbf{X}\|}$ denote the $2$-norm of the vector $\mathbf{x}$, and the Frobenius norm of the matrix $\mathbf{X}$, respectively. The spectral norm of the matrix $\mathbf{X}$ is written as $\rho{(\mathbf{X})}$.

## Appendix B Algorithm Pseudocode

Figure: Algorithm 1 Decentralized Sporadic Federated Learning (DSpodFL)

## Appendix C Assumption Statements

In this section, we state the mathematical inequalities that follow from the assumptions we made in Sec. [4.1](#S4.SS1), which are used in our subsequent Lemmas and Propositions.

- •
Assumption [4.1](#S4.Thmtheorem1):
[(a)](#S4.I1.i1): $\beta_{i}$-smoothness: $\left\|\nabla F_{i}{\left(\mathbf{\theta}\right)}-\nabla F_{i}{\left(\mathbf{\theta^{\prime}}\right)}\right\|\leq\beta_{i}\left\|\mathbf{\theta}-\mathbf{\theta^{\prime}}\right\|\leq\beta\left\|\mathbf{\theta}-\mathbf{\theta^{\prime}}\right\|$,
[(b)](#S4.I1.i2): $\mu_{i}$-strong convexity: $\left\langle\nabla{F_{i}{\left(\mathbf{\theta}\right)}}-\nabla{F_{i}{\left(\mathbf{\theta^{\prime}}\right)}},\mathbf{\theta}-\mathbf{\theta^{\prime}}\right\rangle\geq\mu_{i}{\left\|\mathbf{\theta}-\mathbf{\theta^{\prime}}\right\|}^{2}\geq\mu{\left\|\mathbf{\theta}-\mathbf{\theta^{\prime}}\right\|}^{2}$,
[(c)](#S4.I2.i3): $\delta_{i},\zeta_{i}$-gradient diversity: $\left\|\nabla{F{\left(\mathbf{\theta}\right)}}-\nabla{F_{i}{\left(\mathbf{\theta}\right)}}\right\|\leq\delta_{i}+\zeta_{i}\left\|\mathbf{\theta}-\mathbf{\theta^{\star}}\right\|\leq\delta+\zeta\left\|\mathbf{\theta}-\mathbf{\theta^{\star}}\right\|$,
for all $(\mathbf{\theta^{\prime}},\mathbf{\theta})\in\mathbb{R}^{n}\times\mathbb{R}^{n}$ and all $i\in\mathcal{M}$, where $\mu=\min_{i\in\mathcal{M}}{\mu_{i}}$, $\beta=\max_{i\in\mathcal{M}}{\beta_{i}}$, $\delta=\max_{i\in\mathcal{M}}{\delta_{i}}$ and $\zeta=\max_{i\in\mathcal{M}}{\zeta_{i}}$.
Note that these measures are related to each other via the inequalities $\mu\leq\mu_{i}\leq\beta_{i}\leq\beta$, $0\leq\zeta_{i}<\beta_{i}+\beta$ and $0\leq\zeta\leq 2\beta$ (see Appendix [E](#A5)). We will also find the relationship $F(\mathbf{\theta})\leq F(\mathbf{\theta}^{\prime})+\left\langle\nabla{F}(\mathbf{\theta}^{\prime}),\mathbf{\theta}-\mathbf{\theta}^{\prime}\right\rangle+\frac{\beta}{2}{\left\|\mathbf{\theta}^{\prime}-\mathbf{\theta}\right\|}^{2}$ useful in our treatment of smoothness.
- •
Assumption [4.2](#S4.Thmtheorem2):
[(a)](#S4.I3.i1): Zero mean and bounded variance of stochastic gradient noise: $\mathbb{E}_{\epsilon_{i}^{(k)}}{[\mathbf{\epsilon}_{i}^{(k)}]}=0$, $\mathbb{E}{[{\|\mathbf{\epsilon}_{i}^{(k)}\|}_{2}^{2}]}\leq\sigma_{i}^{2}\leq\sigma^{2}$,
where $\sigma^{2}=\max_{i\in\mathcal{M}}{\sigma_{i}^{2}}$, for all $i\in\mathcal{M}$ and all $k\geq 0$.
[(b)](#S4.I3.i2): Random vectors $\mathbf{\epsilon}_{i_{1}}^{(k)}$ and $\mathbf{\epsilon}_{i_{2}}^{(k)}$, indicator variables $v_{j_{1}}^{(k)}$ and $v_{j_{2}}^{(k)}$, and $\hat{v}_{l_{1},q_{1}}^{(k)}$ and $\hat{v}_{l_{2},q_{2}}^{(k)}$ all being mutually uncorrelated, for all $i_{1}\neq i_{2}$, $j_{1}\neq j_{2}$ and $(l_{1},q_{1})\neq(l_{2},q_{2})$:
$\mathbb{E}_{\xi^{(k)}}{\left[\mathbf{\epsilon}_{i_{1}}^{(k)}v_{j_{1}}^{(k)}v_{j_{2}}^{(k)}\hat{v}_{l_{1},q_{1}}^{(k)}\hat{v}_{l_{2},q_{2}}^{(k)}\right]}=\mathbb{E}_{\mathbf{\epsilon}_{i_{1}}^{(k)}}{\left[\mathbf{\epsilon}_{i_{1}}^{(k)}\right]}\mathbb{E}_{v_{j_{1}}^{(k)}}{\left[v_{j_{1}}^{(k)}\right]}\mathbb{E}_{v_{j_{2}}^{(k)}}{\left[v_{j_{2}}^{(k)}\right]}\mathbb{E}_{\hat{v}_{l_{1},q_{1}}^{(k)}}{\left[\hat{v}_{l_{1},q_{1}}^{(k)}\right]}\mathbb{E}_{\hat{v}_{l_{2},q_{2}}^{(k)}}{\left[\hat{v}_{l_{2},q_{2}}^{(k)}\right]}$,
$\mathbb{E}_{\xi^{(k)}}{\left[\langle\mathbf{\epsilon}_{i_{1}}^{(k)},\mathbf{\epsilon}_{i_{2}}^{(k)}\rangle\right]}=\left\langle\mathbb{E}_{\mathbf{\epsilon}_{i_{1}}^{(k)}}{\left[\mathbf{\epsilon}_{i_{1}}^{(k)}\right]},\mathbb{E}_{\mathbf{\epsilon}_{i_{2}}^{(k)}}{\left[\mathbf{\epsilon}_{i_{2}}^{(k)}\right]}\right\rangle$.
- •
Assumption [4.3](#S4.Thmtheorem3): This assumption implies that if $\mathbf{P}^{(k)}={[p_{ij}^{(k)}]}_{1\leq i,j\leq m}$ and $\mathbf{R}={[r_{ij}]}_{1\leq i,j\leq m}$ as defined in Eqs. ([4](#S3.E4)) and ([2](#S3.E2)) are the doubly-stochastic mixing matrices assigned to $\mathcal{G}^{(k)}$ and $\mathcal{G}$, respectively, we have
${\left\|\mathbf{P}^{(k)}\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\leq{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2},\qquad{\left\|\mathbf{R}\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\leq\rho_{r}^{2}\cdot{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}$,
with $0<\rho_{r}<1$, where $\rho_{r}$ denotes the spectral radius of the matrix $\mathbf{R}-\frac{1}{m}\mathbf{1}_{m}\mathbf{1}_{m}^{T}$.
- •
Assumption [4.5](#S4.Thmtheorem5): PL condition: Under this assumption, we further know that $F$ satisfies the quadratic growth condition (QG-condition) ${\|\mathbf{\theta}-\mathbf{\theta}^{\star}\|}^{2}\leq\frac{2}{\mu}(F(\mathbf{\theta})-F^{\star})$, where $\mathbf{\theta}^{\star}$ is the nearest point to the optimal solution of the minimization problem under consideration. This will also be useful in our analysis.

## Appendix D Intermediary Lemmas

###### Lemma D.1 .

(See Appendix [E](#A5) for the proof.)
Let Assumption [4.1](#S4.Thmtheorem1) hold. We have

- (a)
The global loss function $F{(\theta)}$ is $\beta$-smooth and $\mu$-strongly convex, i.e.,
$\begin{gathered}\left\|\nabla{F{\left(\mathbf{\theta}\right)}}-\nabla{F{\left(\mathbf{\theta^{\prime}}\right)}}\right\|\leq\beta\left\|\mathbf{\theta}-\mathbf{\theta^{\prime}}\right\|,\qquad\left\langle\nabla{F{\left(\mathbf{\theta}\right)}}-\nabla{F{\left(\mathbf{\theta^{\prime}}\right)}},\mathbf{\theta}-\mathbf{\theta^{\prime}}\right\rangle\geq\mu{\left\|\mathbf{\theta}-\mathbf{\theta^{\prime}}\right\|}^{2}.\end{gathered}$
- (b)
The gradients of the global and local loss functions, and the gradient of the local loss function at the optimal point are bounded as
$\left\|\nabla{F{\left(\mathbf{\theta}\right)}}\right\|\leq\beta\left\|\mathbf{\theta}-\mathbf{\theta^{\star}}\right\|,\quad{\left\|\nabla{F_{i}{\left(\mathbf{\theta}\right)}}\right\|}^{2}\leq 2\left(\beta_{i}^{2}{\left\|\mathbf{\theta}-\mathbf{\theta}^{\star}\right\|}^{2}+\delta_{i}^{2}\right),\quad\left\|\nabla{F_{i}{\left(\mathbf{\theta^{\star}}\right)}}\right\|\leq\delta_{i}.$

Part-[(a)](#A4.Ex2) of Lemma [D.1](#A4.Thmtheorem1) outlines the smoothness and convexity behaviour of the global loss function based on the measures of local loss functions, and part [(b)](#A4.Ex3) provides upper bounds on the gradients. Note how these show that we are not making the bounded gradients assumption for all $\mathbf{\theta}\in\mathbb{R}^{n}$, but only bounded local gradients at the globally optimal point $\mathbf{\theta}^{\star}$.

Next, we provide upper bounds on the expected Frobenius norms of the following quantities related to SGD noises.

###### Lemma D.2 .

(See Appendix [F](#A6) for the proof.)
Let Assumption [4.2](#S4.Thmtheorem2) hold. For every iteration $k\geq 0$, the average SGD noise and their deviation from this average can be bounded as

$$ $\mathbb{E}_{\mathbf{\xi}^{(k)}}{\left[{\left\|\overline{\mathbf{\epsilon}v}^{(k)}\right\|}^{2}\right]}\leq d_{max}^{(k)}\sigma^{2}/m,\qquad\mathbb{E}_{\mathbf{\xi}^{(k)}}{\left[{\left\|\mathbf{V}^{(k)}\mathbf{E}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\epsilon}v}^{(k)}\right\|}^{2}\right]}\leq md_{max}^{(k)}\sigma^{2},$ $$

in which $\overline{\mathbf{\epsilon}v}^{(k)}=\frac{1}{m}{\sum_{i=1}^{m}{\mathbf{\epsilon}_{i}^{(k)}v_{i}^{(k)}}}$.

Note that by setting $d_{max}^{(k)}=1$ in [D.2](#A4.Thmtheorem2), we get back the well-known estimation bounds for these quantities (e.g., see Lemma 2 in Pu & Nedić ()).

Next, we find an upper bound on the expected deviation of the gradients from their average (similar to the second quantity in Lemma [D.2](#A4.Thmtheorem2)).

###### Lemma D.3 .

(See Appendix [H](#A8) for the proof.)
Let Assumption [4.1](#S4.Thmtheorem1) hold. For each iteration $k\geq 0$, we have the following bound on the expected error of gradients from their average

$$ $\displaystyle\mathbb{E}_{\mathbf{\Xi}^{(k)}}{\left[{\left\|\mathbf{V}^{(k)}\mathbf{\nabla}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\nabla}v}^{(k)}\right\|}^{2}\right]}\leq 3$ $\displaystyle d_{max}^{(k)}\Bigg{[}m\delta^{2}+\left(\zeta^{2}+2\beta^{2}\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}$ $\displaystyle+m\left(\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\right]}\Bigg{]}$ $$

in which $\mathbf{\nabla}^{(k)}$ is a matrix whose rows are comprised of the gradient vectors $\nabla{F_{i}{(\mathbf{\theta}_{i}^{(k)})}}$, and $\overline{\mathbf{\nabla}v}^{(k)}=\frac{1}{m}\sum_{i=1}^{m}{\nabla{F_{i}{(\theta_{i}^{(k)})}}v_{i}^{(k)}}$.

Finally, we analyze the behaviour of the random mixing matrix $\mathbf{P}^{(k)}$ defined in Eqs. ([3](#S3.E3)) and ([4](#S3.E4)).

###### Lemma D.4 .

(See Appendix [I](#A9) for the proof.)
Let Assumption [4.3](#S4.Thmtheorem3) hold. For each iteration $k\geq 0$, we have

- (a)
The expected mixing matrix, denoted as $\mathbf{\bar{R}}^{(k)}$, is irreducible and doubly-stochastic:
$\mathbb{E}_{\mathbf{\hat{V}}^{(k)}}{\left[\mathbf{P}^{(k)}\right]}\triangleq\mathbf{\bar{R}}^{(k)}={\left[\bar{r}_{ij}^{(k)}\right]}_{1\leq i,j\leq m},\qquad\bar{r}_{ij}^{(k)}=\begin{cases}b_{ij}^{(k)}r_{ij}&i\neq j\\
1-\sum_{j=1}^{m}{b_{ij}^{(k)}r_{ij}}&i=j\end{cases}$.
- (b)
$\mathbb{E}_{\mathbf{\hat{V}}^{(k)}}{\left[{\left(\mathbf{P}^{(k)}\right)}^{2}\right]}={\left(\mathbf{\bar{R}}^{(k)}\right)}^{2}+\mathbf{R}_{0}^{(k)}\triangleq\mathbf{\tilde{R}}^{(k)}$,
where $\mathbf{R}_{0}^{(k)}$ is a matrix whose rows and columns sum to zero. Thus, $\mathbf{\tilde{R}}^{(k)}$ will be irreducible and doubly-stochastic.
- (c)
$\mathbb{E}_{\mathbf{\Xi}^{(k)}}{\left[{\left\|\mathbf{P}^{(k)}\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\mathbf{\bar{\theta}}^{(k)}\right\|}^{2}\right]}\leq\tilde{\rho}^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\mathbf{\bar{\theta}}^{(k)}\right\|}^{2}\right]},$
in which $\tilde{\rho}^{(k)}$ is the spectral radius of the matrix $\mathbf{\tilde{R}}^{(k)}-\frac{1}{m}\mathbf{1}_{m}\mathbf{1}_{m}^{T}$.

###### Lemma D.1 .

###### Lemma D.2 .

###### Lemma D.3 .

###### Lemma D.4 .

## Appendix E Proof of Lemma D.1

[(a)](#A4.Ex2) First, we use the smoothness property given in Assumption [4.1](#S4.Thmtheorem1)-[(a)](#S4.I1.i1) to get

$$ $\displaystyle\left\|\nabla{F{\left(\mathbf{\theta}\right)}}-\nabla{F{\left(\mathbf{\theta^{\prime}}\right)}}\right\|$ $\displaystyle=\left\|\frac{1}{m}\sum_{j=1}^{m}{\left(\nabla{F_{j}{\left(\mathbf{\theta}\right)}}-\nabla{F_{j}{\left(\mathbf{\theta^{\prime}}\right)}}\right)}\right\|\leq\frac{1}{m}\sum_{j=1}^{m}{\left\|\nabla{F_{j}{\left(\mathbf{\theta}\right)}}-\nabla{F_{j}{\left(\mathbf{\theta^{\prime}}\right)}}\right\|}\leq\frac{1}{m}\sum_{j=1}^{m}{\beta_{j}\left\|\mathbf{\theta}-\mathbf{\theta^{\prime}}\right\|}$ $\displaystyle=\bar{\beta}\left\|\mathbf{\theta}-\mathbf{\theta^{\prime}}\right\|\leq\beta\left\|\mathbf{\theta}-\mathbf{\theta^{\prime}}\right\|$ $$

Next, using the strong convexity property of Assumption [4.1](#S4.Thmtheorem1)-[(b)](#S4.I1.i2), we have

$$ $\left\langle\nabla{F{\left(\mathbf{\theta}\right)}}-\nabla{F{\left(\mathbf{\theta^{\prime}}\right)}},\mathbf{\theta}-\mathbf{\theta^{\prime}}\right\rangle=\frac{1}{m}\sum_{j=1}^{m}{\left\langle\nabla{F_{j}{\left(\mathbf{\theta}\right)}}-\nabla{F_{j}{\left(\mathbf{\theta^{\prime}}\right)}},\mathbf{\theta}-\mathbf{\theta^{\prime}}\right\rangle}\geq\frac{1}{m}\sum_{j=1}^{m}{\mu_{j}{\left\|\mathbf{\theta}-\mathbf{\theta^{\prime}}\right\|}^{2}}=\bar{\mu}{\left\|\mathbf{\theta}-\mathbf{\theta^{\prime}}\right\|}^{2}\geq\mu{\left\|\mathbf{\theta}-\mathbf{\theta^{\prime}}\right\|}^{2}.$ $$

[(b)](#A4.Ex3) Since $\nabla{F}{(\mathbf{\theta^{\star}})}=0$ by definition, we can use the results of part [(a)](#A4.Ex2) of this lemma to show that

$$ $\left\|\nabla{F}{(\mathbf{\theta})}\right\|\leq\beta\left\|\mathbf{\theta}-\mathbf{\theta}^{\star}\right\|.$ $$

Once again noting that $\nabla{F}{(\mathbf{\theta^{\star}})}=0$, we next use the gradient diversity bound outlined in Assumption [4.1](#S4.Thmtheorem1)-[(c)](#S4.I2.i3) to get

$$ $\left\|\nabla{F}_{i}{(\mathbf{\theta^{\star}})}\right\|\leq\delta_{i}.$ (12) $$

Finally, using Eq. ([12](#A5.E12)) and Assumption [4.1](#S4.Thmtheorem1)-[(a)](#S4.I1.i1), we write

$$ $\displaystyle{\left\|\nabla{F_{i}{\left(\mathbf{\theta}\right)}}\right\|}^{2}$ $\displaystyle\leq 2\left({\left\|\nabla{F_{i}{\left(\mathbf{\theta}\right)}}-\nabla{F_{i}{\left(\mathbf{\theta}^{\star}\right)}}\right\|}^{2}+{\left\|\nabla{F_{i}{\left(\mathbf{\theta}^{\star}\right)}}\right\|}^{2}\right)\leq 2\left(\beta_{i}^{2}{\left\|\mathbf{\theta}-\mathbf{\theta}^{\star}\right\|}^{2}+\delta_{i}^{2}\right),$ $$

finishing the proof.

To explain the statement written after Assumption [4.1](#S4.Thmtheorem1) on how these measures relate to each other, we first have

$$ $\mu\leq\mu_{i}\leq\beta_{i}\leq\beta,$ $$

in which $\mu_{i}\leq\beta_{i}$ is a well-known fact (see (Bottou et al., ) as a reference), and $\mu\leq\mu_{i}$ and $\beta_{i}\leq\beta$ follow from the definitions given in Assumption [4.1](#S4.Thmtheorem1). Moreover, if we upper-bound the gradient diversity term $\left\|\nabla{F{\left(\mathbf{\theta}\right)}}-\nabla{F_{i}{\left(\mathbf{\theta}\right)}}\right\|$ without using Assumption [4.1](#S4.Thmtheorem1)-[(c)](#S4.I2.i3), we will have

$$ $\displaystyle\left\|\nabla{F{\left(\mathbf{\theta}\right)}}-\nabla{F_{i}{\left(\mathbf{\theta}\right)}}\right\|$ $\displaystyle\leq\left\|\nabla{F{\left(\mathbf{\theta}\right)}}-\nabla{F_{i}{\left(\mathbf{\theta^{\star}}\right)}}+\nabla{F_{i}{\left(\mathbf{\theta^{\star}}\right)}}-\nabla{F_{i}{\left(\mathbf{\theta}\right)}}\right\|$ (13) $\displaystyle\leq\left\|\nabla{F{\left(\mathbf{\theta}\right)}}\right\|+\left\|\nabla{F_{i}{\left(\mathbf{\theta^{\star}}\right)}}\right\|+\left\|\nabla{F_{i}{\left(\mathbf{\theta}\right)}}-\nabla{F_{i}{\left(\mathbf{\theta^{\star}}\right)}}\right\|\leq\delta_{i}+\beta_{i}\left\|\mathbf{\theta}-\mathbf{\theta^{\star}}\right\|+\beta\left\|\mathbf{\theta}-\mathbf{\theta^{\star}}\right\|$ $\displaystyle\leq\delta_{i}+(\beta_{i}+\beta)\left\|\mathbf{\theta}-\mathbf{\theta^{\star}}\right\|,$ $$

in which we used Assumption [4.1](#S4.Thmtheorem1)-[(a)](#S4.I1.i1) and the results of Lemma [D.1](#A4.Thmtheorem1)-[(b)](#A4.Ex3). Now comparing Eq. ([13](#A5.E13)) with the assumption made in [4.1](#S4.Thmtheorem1)-[(c)](#S4.I2.i3) for the same expression, we conclude that

$$ $\zeta_{i}\leq\beta_{i}+\beta,\qquad\zeta\leq 2\beta.$ $$

## Appendix F Proof of Lemma D.2

We start by finding an upper bound for the average SGD noise, by expanding the terms using their definitions, and employing the properties given in Assumption [4.2](#S4.Thmtheorem2).

$$ $\displaystyle\mathbb{E}_{\mathbf{\xi}^{(k)}}$ $\displaystyle{\left[{\left\|\overline{\mathbf{\epsilon}v}^{(k)}\right\|}^{2}\right]}=\mathbb{E}_{\mathbf{\xi}^{(k)}}{\left[{\left\|\frac{1}{m}\sum_{i=1}^{m}{\mathbf{\epsilon}_{i}^{(k)}v_{i}^{(k)}}\right\|}^{2}\right]}=\mathbb{E}_{\mathbf{\xi}^{(k)}}{\left[\frac{1}{m^{2}}\sum_{i=1}^{m}{\sum_{j=1}^{m}{\left\langle\mathbf{\epsilon}_{i}^{(k)}v_{i}^{(k)},\mathbf{\epsilon}_{j}^{(k)}v_{j}^{(k)}\right\rangle}}\right]}$ $\displaystyle=\frac{1}{m^{2}}\sum_{i=1}^{m}{\mathbb{E}_{\mathbf{\xi}_{i}^{(k)}}{\left[{\left\|\mathbf{\epsilon}_{i}^{(k)}v_{i}^{(k)}\right\|}^{2}\right]}}+\frac{1}{m^{2}}\sum_{i=1}^{m}\sum_{\begin{subarray}{c}j=1\\ j\neq i\end{subarray}}^{m}\left\langle\mathbb{E}_{\mathbf{\xi}_{i}^{(k)}}{\left[\mathbf{\epsilon}_{i}^{(k)}v_{i}^{(k)}\right]},\mathbb{E}_{\mathbf{\xi}_{j}^{(k)}}{\left[\mathbf{\epsilon}_{j}^{(k)}v_{j}^{(k)}\right]}\right\rangle$ $\displaystyle=\frac{1}{m^{2}}\sum_{i=1}^{m}{\mathbb{E}_{\mathbf{\xi}_{i}^{(k)}}{\left[{\left\|\mathbf{\epsilon}_{i}^{(k)}\right\|}^{2}v_{i}^{(k)}\right]}}+\frac{1}{m^{2}}\sum_{i=1}^{m}\sum_{\begin{subarray}{c}j=1\\ j\neq i\end{subarray}}^{m}\Big{\langle}\mathbb{E}_{\mathbf{\epsilon}_{i}^{(k)}}{\left[\mathbf{\epsilon}_{i}^{(k)}\right]}\mathbb{E}_{v_{i}^{(k)}}{\left[v_{i}^{(k)}\right]},\mathbb{E}_{\mathbf{\epsilon}_{j}^{(k)}}{\left[\mathbf{\epsilon}_{j}^{(k)}\right]}\mathbb{E}_{v_{j}^{(k)}}{\left[v_{j}^{(k)}\right]}\Big{\rangle}$ $\displaystyle=\frac{1}{m^{2}}\sum_{i=1}^{m}{\mathbb{E}_{\mathbf{\epsilon}_{i}^{(k)}}{\left[{\left\|\mathbf{\epsilon}_{i}^{(k)}\right\|}^{2}\right]}\mathbb{E}_{v_{i}^{(k)}}{\left[v_{i}^{(k)}\right]}}=\frac{1}{m^{2}}\sum_{i=1}^{m}{d_{i}^{(k)}\sigma_{i}^{2}}\leq\frac{d_{max}^{(k)}\sigma^{2}}{m}.$ $$

Next, we found an upper bound for deviance of the error matrix from its average, using a similar approach as above. We have

$$ $\displaystyle\mathbb{E}_{\mathbf{\xi}^{(k)}}$ $\displaystyle{\left[{\left\|\mathbf{V}^{(k)}\mathbf{E}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\epsilon}v}^{(k)}\right\|}^{2}\right]}=\mathbb{E}_{\mathbf{\xi}^{(k)}}{\left[{\left\|\mathbf{V}^{(k)}\mathbf{E}^{(k)}\right\|}^{2}-2\left\langle\mathbf{V}^{(k)}\mathbf{E}^{(k)},\mathbf{1}_{m}\overline{\mathbf{\epsilon}v}^{(k)}\right\rangle+{\left\|\mathbf{1}_{m}\overline{\mathbf{\epsilon}v}^{(k)}\right\|}^{2}\right]}$ $\displaystyle=\mathbb{E}_{\mathbf{\xi}^{(k)}}{\left[\sum_{i=1}^{m}{{\left\|\mathbf{\epsilon}_{i}^{(k)}v_{i}^{(k)}\right\|}^{2}}\right]}-2\mathbb{E}_{\mathbf{\xi}^{(k)}}{\left[\sum_{i=1}^{m}{\left\langle\mathbf{\epsilon}_{i}^{(k)}v_{i}^{(k)},\overline{\mathbf{\epsilon}v}^{(k)}\right\rangle}\right]}+\mathbb{E}_{\mathbf{\xi}^{(k)}}{\left[m{\left\|\overline{\mathbf{\epsilon}v}^{(k)}\right\|}^{2}\right]}$ $\displaystyle\begin{aligned} \,\,=\sum_{i=1}^{m}{\mathbb{E}_{\mathbf{\xi}_{i}^{(k)}}{\left[{\left\|\mathbf{\epsilon}_{i}^{(k)}\right\|}^{2}v_{i}^{(k)}\right]}}&-\frac{2}{m}\sum_{i=1}^{m}{\mathbb{E}_{\mathbf{\xi}_{i}^{(k)}}{\left[{\left\|\mathbf{\epsilon}_{i}^{(k)}\right\|}^{2}v_{i}^{(k)}\right]}}-\frac{2}{m}\sum_{i=1}^{m}{\left\langle\mathbb{E}_{\mathbf{\xi}_{i}^{(k)}}{\left[\mathbf{\epsilon}_{i}^{(k)}v_{i}^{(k)}\right]},\sum_{\begin{subarray}{c}j=1\\ j\neq i\end{subarray}}^{m}{\mathbb{E}_{\mathbf{\xi}_{j}^{(k)}}{\left[\mathbf{\epsilon}_{j}^{(k)}v_{j}^{(k)}\right]}}\right\rangle}\\ &+m\mathbb{E}_{\mathbf{\xi}^{(k)}}{\left[{\left\|\overline{\mathbf{\epsilon}v}^{(k)}\right\|}^{2}\right]}\end{aligned}$ $$

$$ $\displaystyle\begin{aligned} =\left(1-\frac{2}{m}+\frac{1}{m}\right)&\sum_{i=1}^{m}{\mathbb{E}_{\mathbf{\epsilon}_{i}^{(k)}}{\left[{\left\|\mathbf{\epsilon}_{i}^{(k)}\right\|}^{2}\right]}\mathbb{E}_{v_{i}^{(k)}}{\left[v_{i}^{(k)}\right]}}-\frac{2}{m}\sum_{i=1}^{m}\sum_{\begin{subarray}{c}j=1\\ j\neq i\end{subarray}}^{m}\Big{\langle}\mathbb{E}_{\mathbf{\epsilon}_{i}^{(k)}}{\left[\mathbf{\epsilon}_{i}^{(k)}\right]}\mathbb{E}_{v_{i}^{(k)}}{\left[v_{i}^{(k)}\right]},\mathbb{E}_{\mathbf{\epsilon}_{j}^{(k)}}{\left[\mathbf{\epsilon}_{j}^{(k)}\right]}\mathbb{E}_{v_{j}^{(k)}}{\left[v_{j}^{(k)}\right]}\Big{\rangle}\end{aligned}$ $\displaystyle=\left(1-\frac{1}{m}\right)\sum_{i=1}^{m}{d_{i}^{(k)}\sigma_{i}^{2}}\leq\left(m-1\right)d_{max}^{(k)}\sigma^{2}\leq md_{max}^{(k)}\sigma^{2}.$ $$

## Appendix G Proof of Lemma 4.7

Using Lemma [D.1](#A4.Thmtheorem1)-[(b)](#A4.Ex3) on $\bar{\mathbf{\theta}}^{(k)}$, the average model parameters at iteration $k$, we get

$$ ${\left\|\nabla{F_{i}{\left(\bar{\mathbf{\theta}}^{(k)}\right)}}\right\|}^{2}\leq 2\left(\beta_{i}^{2}{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}+\delta_{i}^{2}\right).$ (14) $$

Now, if $0<\alpha^{(k)}\leq\frac{2}{\mu+\beta}$, we can write

$$ $\displaystyle{\left\|\bar{\mathbf{\theta}}^{(k+1)}-\mathbf{\theta}^{\star}\right\|}^{2}={\left\|\bar{\mathbf{\theta}}^{(k)}-\alpha^{(k)}\overline{\mathbf{g}v}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}$ $\displaystyle={\left\|\bar{\mathbf{\theta}}^{(k)}-\alpha^{(k)}\overline{\mathbf{\nabla}v}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}-2\left\langle\bar{\mathbf{\theta}}^{(k)}-\alpha^{(k)}\overline{\mathbf{\nabla}v}^{(k)}-\mathbf{\theta}^{\star},\alpha^{(k)}\overline{\mathbf{\epsilon}v}^{(k)}\right\rangle+{\left(\alpha^{(k)}\right)}^{2}{\left\|\overline{\mathbf{\epsilon}v}^{(k)}\right\|}^{2}$ $\displaystyle\begin{aligned} \,\,\leq&\left(1+\mu\alpha^{(k)}\right){\left\|\bar{\mathbf{\theta}}^{(k)}-\alpha^{(k)}\nabla{F{\left(\bar{\mathbf{\theta}}^{(k)}\right)}}-\mathbf{\theta}^{\star}\right\|}^{2}+\left(1+\frac{1}{\mu\alpha^{(k)}}\right)\frac{{\left(\alpha^{(k)}\right)}^{2}}{m}\sum_{i=1}^{m}{{\left\|\nabla{F_{i}{\left(\bar{\mathbf{\theta}}^{(k)}\right)}}-\nabla{F_{i}{\left(\mathbf{\theta}_{i}^{(k)}\right)}}v_{i}^{(k)}\right\|}^{2}}\\ &\qquad\,\,-2\left\langle\bar{\mathbf{\theta}}^{(k)}-\alpha^{(k)}\overline{\mathbf{\nabla}v}^{(k)}-\mathbf{\theta}^{\star},\alpha^{(k)}\overline{\mathbf{\epsilon}v}^{(k)}\right\rangle+{\left(\alpha^{(k)}\right)}^{2}{\left\|\overline{\mathbf{\epsilon}v}^{(k)}\right\|}^{2}\end{aligned}$ $\displaystyle\begin{aligned} \,\,\leq&\left(1+\mu\alpha^{(k)}\right){\left(1-\mu\alpha^{(k)}\right)}^{2}{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}+\frac{\alpha^{(k)}}{m\mu}\left(1+\mu\alpha^{(k)}\right)\sum_{\begin{subarray}{c}i=1\\ v_{i}^{(k)}=1\end{subarray}}^{m}{\beta_{i}^{2}{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}_{i}^{(k)}\right\|}^{2}}\\ &\qquad\,\,+\frac{2\alpha^{(k)}}{m\mu}\left(1+\mu\alpha^{(k)}\right)\sum_{\begin{subarray}{c}i=1\\ v_{i}^{(k)}=0\end{subarray}}^{m}{\left(\beta_{i}^{2}{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}+\delta_{i}^{2}\right)}-2\left\langle\bar{\mathbf{\theta}}^{(k)}-\alpha^{(k)}\overline{\mathbf{\nabla}v}^{(k)}-\mathbf{\theta}^{\star},\alpha^{(k)}\overline{\mathbf{\epsilon}v}^{(k)}\right\rangle\\ &\qquad\,\,+{\left(\alpha^{(k)}\right)}^{2}{\left\|\overline{\mathbf{\epsilon}v}^{(k)}\right\|}^{2}\end{aligned}$ $\displaystyle\begin{aligned} &=\Bigg{[}\left(1+\mu\alpha^{(k)}\right){\left(1-\mu\alpha^{(k)}\right)}^{2}+\frac{2\alpha^{(k)}}{m\mu}\left(1+\mu\alpha^{(k)}\right)\sum_{i=1}^{m}{\beta_{i}^{2}\left(1-v_{i}^{(k)}\right)}\Bigg{]}{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\\ &\qquad\,\,+\frac{\alpha^{(k)}}{m\mu}\left(1+\mu\alpha^{(k)}\right)\sum_{i=1}^{m}{\beta_{i}^{2}{\left\|\mathbf{\theta}_{i}^{(k)}-\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}v_{i}^{(k)}}+\frac{2\alpha^{(k)}}{m\mu}\left(1+\mu\alpha^{(k)}\right)\sum_{i=1}^{m}{\delta_{i}^{2}\left(1-v_{i}^{(k)}\right)}\\ &\qquad\,\,-2\left\langle\bar{\mathbf{\theta}}^{(k)}-\alpha^{(k)}\overline{\mathbf{\nabla}v}^{(k)}-\mathbf{\theta}^{\star},\alpha^{(k)}\overline{\mathbf{\epsilon}v}^{(k)}\right\rangle+{\left(\alpha^{(k)}\right)}^{2}{\left\|\overline{\mathbf{\epsilon}v}^{(k)}\right\|}^{2},\end{aligned}$ $$

in which the relationship in first four lines follow from (i) Eq. ([5](#S3.E5)), (ii) $\mathbf{g}_{i}^{(k)}=\mathbf{\nabla}_{i}^{(k)}+\mathbf{\epsilon}_{i}^{(k)}$ for all $i\in\mathcal{M}$, (iii) Young’s inequality, (iv) Lemma 10 in (Qu & Li, ), Assumption [4.1](#S4.Thmtheorem1)-[(a)](#S4.I1.i1) and Eq. ([14](#A7.E14)). Next, we take the expected value of the above inequality and use Assumption [4.2](#S4.Thmtheorem2) and Lemma [D.2](#A4.Thmtheorem2) to get

$$ $\displaystyle\begin{aligned} \mathbb{E}_{\mathbf{\Xi}^{(k)}}\bigg{[}\Big{\|}\bar{\mathbf{\theta}}^{(k+1)}-\mathbf{\theta}^{\star}\Big{\|}^{2}\bigg{]}\leq\mathbb{E}_{\mathbf{v}^{(k)}}\bigg{[}&\left(1+\mu\alpha^{(k)}\right){\left(1-\mu\alpha^{(k)}\right)}^{2}\\ &+\frac{2\alpha^{(k)}}{m\mu}\left(1+\mu\alpha^{(k)}\right)\sum_{i=1}^{m}{\beta_{i}^{2}\left(1-v_{i}^{(k)}\right)}\bigg{]}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\right]}\end{aligned}$ $$

$$ $\displaystyle\qquad\,\,+\frac{\alpha^{(k)}}{m\mu}\left(1+\mu\alpha^{(k)}\right)\sum_{i=1}^{m}{\beta_{i}^{2}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\theta}_{i}^{(k)}-\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}\mathbb{E}_{v_{i}^{(k)}}{\left[v_{i}^{(k)}\right]}}+\frac{2\alpha^{(k)}}{m\mu}\left(1+\mu\alpha^{(k)}\right)\sum_{i=1}^{m}{\delta_{i}^{2}\mathbb{E}_{v_{i}^{(k)}}{\left[1-v_{i}^{(k)}\right]}}$ $\displaystyle\qquad\,\,-2\mathbb{E}_{\mathbf{\Xi}^{(k-1)}\cup\mathbf{v}^{(k)}}{\left[\left\langle\bar{\mathbf{\theta}}^{(k)}-\alpha^{(k)}\overline{\mathbf{\nabla}v}^{(k)}-\mathbf{\theta}^{\star},\alpha^{(k)}\mathbb{E}_{\mathbf{E}^{(k)}}{\left[\overline{\mathbf{\epsilon}v}^{(k)}\right]}\right\rangle\right]}+{\left(\alpha^{(k)}\right)}^{2}\mathbb{E}_{\mathbf{\xi}^{(k)}}{\left[{\left\|\overline{\mathbf{\epsilon}v}^{(k)}\right\|}^{2}\right]}$ $\displaystyle\leq\Bigg{[}\left(1+\mu\alpha^{(k)}\right){\left(1-\mu\alpha^{(k)}\right)}^{2}+\frac{2\alpha^{(k)}}{m\mu}\left(1+\mu\alpha^{(k)}\right)\sum_{i=1}^{m}{\beta^{2}\left(1-d_{i}^{(k)}\right)}\Bigg{]}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\right]}$ $\displaystyle\qquad\,\,+\frac{\alpha^{(k)}}{m\mu}\left(1+\mu\alpha^{(k)}\right)\sum_{i=1}^{m}{d_{i}^{(k)}\beta_{i}^{2}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\theta}_{i}^{(k)}-\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}}+\frac{2\alpha^{(k)}}{m\mu}\left(1+\mu\alpha^{(k)}\right)\sum_{i=1}^{m}{\delta_{i}^{2}\left(1-d_{i}^{(k)}\right)}$ $\displaystyle\qquad\,\,+\frac{{\left(\alpha^{(k)}\right)}^{2}d_{max}^{(k)}\sigma^{2}}{m}-2\mathbb{E}_{\mathbf{\Xi}^{(k-1)}\cup\mathbf{v}^{(k)}}{\left[\left\langle\bar{\mathbf{\theta}}^{(k)}-\alpha^{(k)}\overline{\mathbf{\nabla}v}^{(k)}-\mathbf{\theta}^{\star},\alpha^{(k)}\mathbb{E}_{\mathbf{E}^{(k)}}{\left[\overline{\mathbf{\epsilon}v}^{(k)}\right]}\right\rangle\right]}+{\left(\alpha^{(k)}\right)}^{2}\mathbb{E}_{\mathbf{\xi}^{(k)}}{\left[{\left\|\overline{\mathbf{\epsilon}v}^{(k)}\right\|}^{2}\right]}$ $\displaystyle\begin{aligned} &=\Bigg{[}1-\mu\alpha^{(k)}\left(1+\mu\alpha^{(k)}-{\left(\mu\alpha^{(k)}\right)}^{2}\right)+\frac{2\alpha^{(k)}}{\mu}\left(1+\mu\alpha^{(k)}\right)\left(1-d_{min}^{(k)}\right)\beta^{2}\Bigg{]}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\right]}\\ &\qquad\,\,+\left(1+\mu\alpha^{(k)}\right)\frac{\alpha^{(k)}d_{max}^{(k)}\beta^{2}}{m\mu}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}+\frac{2\alpha^{(k)}}{\mu}\left(1+\mu\alpha^{(k)}\right)\left(1-d_{min}^{(k)}\right)\delta^{2}\\ &\qquad\,\,+\frac{{\left(\alpha^{(k)}\right)}^{2}d_{max}^{(k)}\sigma^{2}}{m}\end{aligned}$ $$

## Appendix H Proof of Lemma D.3

Noting that

$$ ${\left\|\mathbf{V}^{(k)}\mathbf{\nabla}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\nabla}v}^{(k)}\right\|}^{2}=2{\left\|\mathbf{V}^{(k)}\mathbf{\nabla}^{(k)}-\mathbf{V}^{(k)}\mathbf{\nabla{F}}^{(k)}\right\|}^{2}+2{\left\|\mathbf{V}^{(k)}\mathbf{\nabla{F}}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\nabla}v}^{(k)}\right\|}^{2},$ $$

we first find an upper bound for each of the two terms above separately. For the first term, we have

$$ $\displaystyle\bigg{\|}\mathbf{V}^{(k)}\mathbf{\nabla}^{(k)}-\mathbf{V}^{(k)}\mathbf{\nabla{F}}^{(k)}\bigg{\|}^{2}$ $\displaystyle=\sum_{i=1}^{m}{{\left\|\nabla{F_{i}{\left(\mathbf{\theta}_{i}^{(k)}\right)}}v_{i}^{(k)}-\nabla{F{\left(\mathbf{\theta}_{i}^{(k)}\right)}}v_{i}^{(k)}\right\|}^{2}}=\sum_{i=1}^{m}{{\left\|\nabla{F_{i}{\left(\mathbf{\theta}_{i}^{(k)}\right)}}-\nabla{F{\left(\mathbf{\theta}_{i}^{(k)}\right)}}\right\|}^{2}v_{i}^{(k)}}$ $\displaystyle\leq\sum_{i=1}^{m}{{\left(\delta_{i}+\zeta_{i}{\left\|\mathbf{\theta}_{i}^{(k)}-\mathbf{\theta}^{\star}\right\|}\right)}^{2}v_{i}^{(k)}}\leq\sum_{i=1}^{m}{{\left(\delta_{i}+\zeta_{i}{\left\|\mathbf{\theta}_{i}^{(k)}-\mathbf{\bar{\theta}}^{(k)}\right\|}+\zeta_{i}{\left\|\mathbf{\bar{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}\right)}^{2}v_{i}^{(k)}}$ $\displaystyle\leq 3\sum_{i=1}^{m}{\left(\delta_{i}^{2}+\zeta_{i}^{2}{\left\|\mathbf{\theta}_{i}^{(k)}-\mathbf{\bar{\theta}}^{(k)}\right\|}^{2}+\zeta_{i}^{2}{\left\|\mathbf{\bar{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\right)v_{i}^{(k)}},$ $$

where Assumption [4.1](#S4.Thmtheorem1)-[(c)](#S4.I2.i3) was used in the first inequality. Next, for the second term, we use Assumption [4.1](#S4.Thmtheorem1)-[(a)](#S4.I1.i1) write

$$ $\displaystyle{\left\|\mathbf{V}^{(k)}\mathbf{\nabla{F}}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\nabla}v}^{(k)}\right\|}^{2}=\sum_{i=1}^{m}{{\left\|\nabla{F{\left(\mathbf{\theta}_{i}^{(k)}\right)}}v_{i}^{(k)}-\overline{\mathbf{\nabla}v}^{(k)}\right\|}^{2}}=\sum_{i=1}^{m}{{\left\|\frac{1}{m}\sum_{j=1}^{m}{\left(\nabla{F_{j}{\left(\mathbf{\theta}_{i}^{(k)}\right)}}v_{i}^{(k)}-\nabla{F_{j}{\left(\mathbf{\theta}_{j}^{(k)}\right)}}v_{j}^{(k)}\right)}\right\|}^{2}}$ $\displaystyle\leq\sum_{i=1}^{m}{\frac{1}{m}\sum_{j=1}^{m}{{\left\|\nabla{F_{j}{\left(\mathbf{\theta}_{i}^{(k)}\right)}}v_{i}^{(k)}-\nabla{F_{j}{\left(\mathbf{\theta}_{j}^{(k)}\right)}}v_{j}^{(k)}\right\|}^{2}}}$ $\displaystyle\begin{aligned} \,\,=\frac{1}{m}\sum_{i=1}^{m}\sum_{j=1}^{m}\Big{\|}&\nabla{F_{j}{\left(\mathbf{\theta}_{i}^{(k)}\right)}}v_{i}^{(k)}-\nabla{F_{j}{\left(\bar{\mathbf{\theta}}^{(k)}\right)}}v_{i}^{(k)}+\nabla{F_{j}{\left(\bar{\mathbf{\theta}}^{(k)}\right)}}v_{i}^{(k)}-\nabla{F_{j}{\left(\mathbf{\theta}^{\star}\right)}}v_{i}^{(k)}\\ &+\nabla{F_{j}{\left(\mathbf{\theta}^{\star}\right)}}v_{i}^{(k)}-\nabla{F_{j}{\left(\bar{\mathbf{\theta}}^{(k)}\right)}}v_{j}^{(k)}+\nabla{F_{j}{\left(\bar{\mathbf{\theta}}^{(k)}\right)}}v_{j}^{(k)}-\nabla{F_{j}{\left(\mathbf{\theta}_{j}^{(k)}\right)}}v_{j}^{(k)}\Big{\|}^{2}\end{aligned}$ $$

$$ $\displaystyle\begin{aligned} \,\,=\frac{3}{m}\sum_{i=1}^{m}\sum_{j=1}^{m}\bigg{(}&{\left\|\nabla{F_{j}{\left(\mathbf{\theta}_{i}^{(k)}\right)}}-\nabla{F_{j}{\left(\bar{\mathbf{\theta}}^{(k)}\right)}}\right\|}^{2}v_{i}^{(k)}+{\left\|\nabla{F_{j}{\left(\bar{\mathbf{\theta}}^{(k)}\right)}}-\nabla{F_{j}{\left(\mathbf{\theta}^{\star}\right)}}\right\|}^{2}{\left(v_{i}^{(k)}-v_{j}^{(k)}\right)}^{2}\\ &+{\left\|\nabla{F_{j}{\left(\bar{\mathbf{\theta}}^{(k)}\right)}}-\nabla{F_{j}{\left(\mathbf{\theta}_{j}^{(k)}\right)}}\right\|}^{2}v_{j}^{(k)}\bigg{)}\end{aligned}$ $\displaystyle\leq\frac{3}{m}\sum_{i=1}^{m}\sum_{j=1}^{m}\bigg{(}\beta_{j}^{2}{\left\|\mathbf{\theta}_{i}^{(k)}-\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}v_{i}^{(k)}+\beta_{j}^{2}{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\left(v_{i}^{(k)}+v_{j}^{(k)}-2v_{i}^{(k)}v_{j}^{(k)}\right)+\beta_{j}^{2}{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}_{j}^{(k)}\right\|}^{2}v_{j}^{(k)}\bigg{)}$ $\displaystyle\leq\frac{3}{m}\sum_{j=1}^{m}\beta_{j}^{2}\sum_{i=1}^{m}\bigg{(}{\left\|\mathbf{\theta}_{i}^{(k)}-\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}v_{i}^{(k)}+{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\left(v_{i}^{(k)}+v_{j}^{(k)}-2v_{i}^{(k)}v_{j}^{(k)}\right)+{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}_{j}^{(k)}\right\|}^{2}v_{j}^{(k)}\bigg{)}$ $\displaystyle\begin{aligned} \,\,\leq\frac{3\beta^{2}}{m}\Bigg{[}m\sum_{i=1}^{m}{{\left\|\mathbf{\theta}_{i}^{(k)}-\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}v_{i}^{(k)}}&+m\sum_{j=1}^{m}{{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}_{j}^{(k)}\right\|}^{2}v_{j}^{(k)}}\\ &+{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\left(m\sum_{i=1}^{m}{v_{i}^{(k)}}+m\sum_{j=1}^{m}{v_{j}^{(k)}}-2\sum_{i=1}^{m}{\sum_{j=1}^{m}{v_{i}^{(k)}v_{j}^{(k)}}}\right)\Bigg{]}\end{aligned}$ $\displaystyle\leq 6\beta^{2}\sum_{i=1}^{m}{{\left\|\mathbf{\theta}_{i}^{(k)}-\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}v_{i}^{(k)}}+6\beta^{2}{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\left(\sum_{i=1}^{m}{v_{i}^{(k)}}-\frac{1}{m}{\left(\sum_{i=1}^{m}{v_{i}^{(k)}}\right)}^{2}\right)$ $\displaystyle\leq 6\beta^{2}\sum_{i=1}^{m}{\left[{\left\|\mathbf{\theta}_{i}^{(k)}-\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}+{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\left(1-\frac{1}{m}\sum_{j=1}^{m}{v_{j}^{(k)}}\right)\right]v_{i}^{(k)}}.$ $$

Now, by combining the two components together we get

$$ $\displaystyle{\left\|\mathbf{V}^{(k)}\mathbf{\nabla}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\nabla}v}^{(k)}\right\|}^{2}=2{\left\|\mathbf{V}^{(k)}\mathbf{\nabla}^{(k)}-\mathbf{V}^{(k)}\mathbf{\nabla{F}}^{(k)}\right\|}^{2}+2{\left\|\mathbf{V}^{(k)}\mathbf{\nabla{F}}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\nabla}v}^{(k)}\right\|}^{2}$ $\displaystyle\leq 3\sum_{i=1}^{m}\Bigg{[}\delta_{i}^{2}+\left(\zeta_{i}^{2}+2\beta^{2}\right){\left\|\mathbf{\theta}_{i}^{(k)}-\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}+\left(\zeta_{i}^{2}+2\beta^{2}\left(1-\frac{1}{m}\sum_{j=1}^{m}{v_{j}^{(k)}}\right)\right){\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\Bigg{]}v_{i}^{(k)}.$ $$

Finally, we take the expected value of the above inequality to conclude the proof.

$$ $\displaystyle\mathbb{E}_{\mathbf{\Xi}^{(k)}}{\left[{\left\|\mathbf{V}^{(k)}\mathbf{\nabla}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\nabla}v}^{(k)}\right\|}^{2}\right]}$ $\displaystyle\begin{aligned} \leq 3\sum_{i=1}^{m}\Bigg{[}&\left(\delta_{i}^{2}+\left(\zeta_{i}^{2}+2\beta^{2}\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\theta}_{i}^{(k)}-\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}\right)\mathbb{E}_{v_{i}^{(k)}}{\left[v_{i}^{(k)}\right]}+\Bigg{(}\zeta_{i}^{2}\mathbb{E}_{v_{i}^{(k)}}{\left[v_{i}^{(k)}\right]}\\ &+2\beta^{2}\Bigg{(}\mathbb{E}_{v_{i}^{(k)}}{\left[v_{i}^{(k)}\right]}-\frac{1}{m}\mathbb{E}_{v_{i}^{(k)}}{\left[v_{i}^{(k)}\right]}-\frac{1}{m}\mathbb{E}_{v_{i}^{(k)}}{\left[v_{i}^{(k)}\right]}\sum_{\begin{subarray}{c}j=1\\ j\neq i\end{subarray}}^{m}{\mathbb{E}_{v_{j}^{(k)}}{\left[v_{j}^{(k)}\right]}}\Bigg{)}\Bigg{)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\right]}\Bigg{]}\end{aligned}$ $\displaystyle\begin{aligned} \leq 3\sum_{i=1}^{m}\Bigg{[}&\left(\delta_{i}^{2}+\left(\zeta_{i}^{2}+2\beta^{2}\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\theta}_{i}^{(k)}-\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}\right)d_{i}^{(k)}+\Bigg{(}\zeta_{i}^{2}d_{i}^{(k)}\\ &\begin{aligned} +2\beta^{2}\left(d_{i}^{(k)}-\frac{1}{m}d_{i}^{(k)}-\frac{1}{m}d_{i}^{(k)}\sum_{\begin{subarray}{c}j=1\\ j\neq i\end{subarray}}^{m}{d_{j}^{(k)}}\right)\Bigg{)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\right]}\Bigg{]}\end{aligned}\end{aligned}$ $\displaystyle\begin{aligned} \leq 3\sum_{i=1}^{m}d_{i}^{(k)}\Bigg{[}\delta_{i}^{2}&+\left(\zeta_{i}^{2}+2\beta^{2}\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\theta}_{i}^{(k)}-\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}\\ &+\Bigg{(}\zeta_{i}^{2}+2\beta^{2}\Bigg{(}1-\frac{1}{m}\Bigg{[}1+\sum_{\begin{subarray}{c}j=1\\ j\neq i\end{subarray}}^{m}{d_{j}^{(k)}}\Bigg{]}\Bigg{)}\Bigg{)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\right]}\Bigg{]}\end{aligned}$ $$

$$ $\displaystyle\begin{aligned} \leq 3d_{max}^{(k)}\Bigg{[}m\delta^{2}&+\left(\zeta^{2}+2\beta^{2}\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}\\ &\begin{aligned} \,+m\left(\zeta^{2}+2\beta^{2}\left(1-\frac{1}{m}\left[1+(m-1)d_{min}^{(k)}\right]\right)\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\right]}\Bigg{]}\end{aligned}\end{aligned}$ $\displaystyle\begin{aligned} =3d_{max}^{(k)}\Bigg{[}m\delta^{2}&+\left(\zeta^{2}+2\beta^{2}\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}\\ &+m\left(\zeta^{2}+2\beta^{2}\left(1-\frac{1}{m}\right)\left(1-d_{min}^{(k)}\right)\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\right]}\Bigg{]}\end{aligned}$ $\displaystyle\leq 3d_{max}^{(k)}\Bigg{[}m\delta^{2}+\left(\zeta^{2}+2\beta^{2}\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}+m\left(\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\right]}\Bigg{]}.$ $$

## Appendix I Proof of Lemma D.4

[(a)](#A4.I2.i1) We take the expected value of the matrix $\mathbf{P}^{(k)}$ by looking at its individual elements. We have

$$ $\displaystyle\mathbb{E}_{\mathbf{\hat{V}}^{(k)}}{\left[\mathbf{P}^{(k)}\right]}$ $\displaystyle={\left[\mathbb{E}_{\hat{v}_{ij}^{(k)}}{\left[p_{ij}^{(k)}\right]}\right]}_{1\leq i,j\leq m}=\begin{cases}{\left[r_{ij}\mathbb{E}_{\hat{v}_{ij}^{(k)}}{\left[\hat{v}_{ij}^{(k)}\right]}\right]}_{1\leq i,j\leq m}&i\neq j\\ {\left[1-\sum_{j=1}^{m}{r_{ij}\mathbb{E}_{\hat{v}_{ij}^{(k)}}{\left[\hat{v}_{ij}^{(k)}\right]}}\right]}_{1\leq i\leq m}&i=j\end{cases}$ $\displaystyle=\begin{cases}{\left[b_{ij}^{(k)}r_{ij}\right]}_{1\leq i,j\leq m}&i\neq j\\ {\left[1-\sum_{j=1}^{m}{b_{ij}^{(k)}r_{ij}}\right]}_{1\leq i\leq m}&i=j\end{cases}=\mathbf{\bar{R}}^{(k)}$ $$

[(b)](#A4.I2.i2) Similar to the proof of the previous part, we take the expected value of $(\mathbf{P}^{(k)})^{T}\mathbf{P}^{(k)}={\left(\mathbf{P}^{(k)}\right)}^{2}$ by looking at its individual elements. We can write

$$ $\displaystyle\text{if }i\neq j:$ $\displaystyle\mathbb{E}_{\mathbf{\hat{V}}^{(k)}}{\left[\sum_{l=1}^{m}{p_{il}^{(k)}p_{lj}^{(k)}}\right]}=\mathbb{E}_{\mathbf{\hat{V}}^{(k)}}{\left[\sum_{\begin{subarray}{c}l=1\\ l\neq i,j\end{subarray}}^{m}{r_{il}r_{lj}\hat{v}_{il}^{(k)}\hat{v}_{lj}^{(k)}}+\left(1-\sum_{q=1}^{m}{r_{iq}\hat{v}_{iq}^{(k)}}\right)r_{ij}\hat{v}_{ij}^{(k)}+\left(1-\sum_{q=1}^{m}{r_{jq}\hat{v}_{jq}^{(k)}}\right)r_{ij}\hat{v}_{ij}^{(k)}\right]}$ $\displaystyle=\mathbb{E}_{\mathbf{\hat{V}}^{(k)}}{\left[\sum_{l=1}^{m}{r_{il}r_{lj}\hat{v}_{il}^{(k)}\hat{v}_{lj}^{(k)}}+\left(2-\sum_{q=1}^{m}{\left(r_{iq}\hat{v}_{iq}^{(k)}+r_{jq}\hat{v}_{jq}^{(k)}\right)}\right)r_{ij}\hat{v}_{ij}^{(k)}\right]}$ $\displaystyle=\mathbb{E}_{\mathbf{\hat{V}}^{(k)}}\Bigg{[}\sum_{l=1}^{m}{r_{il}r_{lj}\hat{v}_{il}^{(k)}\hat{v}_{lj}^{(k)}}+\left(2-\sum_{\begin{subarray}{c}q=1\\ q\neq i,j\end{subarray}}^{m}{\left(r_{iq}\hat{v}_{iq}^{(k)}+r_{jq}\hat{v}_{jq}^{(k)}\right)}\right)r_{ij}\hat{v}_{ij}^{(k)}-\left(r_{ij}\hat{v}_{ij}^{(k)}+r_{ji}\hat{v}_{ji}^{(k)}\right)r_{ij}\hat{v}_{ij}^{(k)}\Bigg{]}$ $\displaystyle\begin{aligned} \,\,=\sum_{l=1}^{m}{r_{il}r_{lj}\mathbb{E}_{\hat{v}_{il}^{(k)}}{\left[\hat{v}_{il}^{(k)}\right]}\mathbb{E}_{\hat{v}_{lj}^{(k)}}{\left[\hat{v}_{lj}^{(k)}\right]}}&+\left(2-\sum_{\begin{subarray}{c}q=1\\ q\neq i,j\end{subarray}}^{m}{\left(r_{iq}\mathbb{E}_{\hat{v}_{iq}^{(k)}}{\left[\hat{v}_{iq}^{(k)}\right]}+r_{jq}\mathbb{E}_{\hat{v}_{jq}^{(k)}}{\left[\hat{v}_{jq}^{(k)}\right]}\right)}\right)r_{ij}\mathbb{E}_{\hat{v}_{ij}^{(k)}}{\left[\hat{v}_{ij}^{(k)}\right]}\\ &-2r_{ij}^{2}\mathbb{E}_{\hat{v}_{ij}^{(k)}}{\left[\hat{v}_{ij}^{(k)}\right]}\end{aligned}$ $\displaystyle=\sum_{l=1}^{m}{b_{il}^{(k)}r_{il}b_{lj}^{(k)}r_{lj}}+\left(2-\sum_{\begin{subarray}{c}q=1\\ q\neq i,j\end{subarray}}^{m}{\left(b_{iq}^{(k)}r_{iq}+b_{jq}^{(k)}r_{jq}\right)}\right)b_{ij}^{(k)}r_{ij}-2b_{ij}^{(k)}r_{ij}^{2}$ $$

On the other hand,

$$ $\displaystyle\text{if }i=j:$ $\displaystyle\mathbb{E}_{\mathbf{\hat{V}}^{(k)}}{\left[\sum_{l=1}^{m}{p_{il}^{(k)}p_{lj}^{(k)}}\right]}=\mathbb{E}_{\mathbf{\hat{V}}^{(k)}}{\left[\sum_{\begin{subarray}{c}l=1\\ l\neq i\end{subarray}}^{m}{r_{il}r_{li}\hat{v}_{il}^{(k)}\hat{v}_{li}^{(k)}}+{\left(1-\sum_{q=1}^{m}{r_{iq}\hat{v}_{iq}^{(k)}}\right)}^{2}\right]}$ $\displaystyle=\mathbb{E}_{\mathbf{\hat{V}}^{(k)}}{\left[\sum_{l=1}^{m}{r_{il}^{2}\hat{v}_{il}^{(k)}}+1-2\sum_{q=1}^{m}{r_{iq}\hat{v}_{iq}^{(k)}}+\sum_{q=1}^{m}{\sum_{t=1}^{m}{r_{iq}r_{it}\hat{v}_{iq}^{(k)}\hat{v}_{it}^{(k)}}}\right]}$ $\displaystyle=\mathbb{E}_{\mathbf{\hat{V}}^{(k)}}{\left[\sum_{l=1}^{m}{r_{il}^{2}\hat{v}_{il}^{(k)}}+1-2\sum_{q=1}^{m}{r_{iq}\hat{v}_{iq}^{(k)}}+\sum_{q=1}^{m}{\sum_{\begin{subarray}{c}t=1\\ t\neq q\end{subarray}}^{m}{r_{iq}r_{it}\hat{v}_{iq}^{(k)}\hat{v}_{it}^{(k)}}}+\sum_{q=1}^{m}{r_{iq}^{2}\hat{v}_{iq}^{(k)}}\right]}$ $\displaystyle\begin{aligned} =2\sum_{l=1}^{m}{r_{il}^{2}\mathbb{E}_{\hat{v}_{il}^{(k)}}{\left[\hat{v}_{il}^{(k)}\right]}}+1&-2\sum_{q=1}^{m}{r_{iq}\mathbb{E}_{\hat{v}_{iq}^{(k)}}{\left[\hat{v}_{iq}^{(k)}\right]}}+\sum_{q=1}^{m}{\sum_{\begin{subarray}{c}t=1\\ t\neq q\end{subarray}}^{m}{r_{iq}r_{it}\mathbb{E}_{\hat{v}_{iq}^{(k)}}{\left[\hat{v}_{iq}^{(k)}\right]}\mathbb{E}_{\hat{v}_{it}^{(k)}}{\left[\hat{v}_{it}^{(k)}\right]}}}\end{aligned}$ $\displaystyle=2\sum_{l=1}^{m}{b_{il}^{(k)}r_{il}^{2}}+1-2\sum_{q=1}^{m}{b_{iq}^{(k)}r_{iq}}+\sum_{q=1}^{m}{\sum_{\begin{subarray}{c}t=1\\ t\neq q\end{subarray}}^{m}{b_{iq}^{(k)}r_{iq}b_{it}^{(k)}r_{it}}}$ $$

Finally, comparing the above expression with the elements of ${\left(\bar{\mathbf{R}}^{(k)}\right)}^{2}$, we get

$$ $\displaystyle\mathbb{E}_{\mathbf{\hat{V}}^{(k)}}{\left[{\left(\mathbf{P}^{(k)}\right)}^{2}\right]}$ $\displaystyle={\left[\mathbb{E}_{\mathbf{\hat{V}}^{(k)}}{\left[\sum_{l=1}^{m}{p_{il}^{(k)}p_{lj}^{(k)}}\right]}\right]}_{1\leq i,j\leq m}={\left(\mathbf{\bar{R}}^{(k)}\right)}^{2}+\begin{cases}{\left[-2b_{ij}^{(k)}\left(1-b_{ij}^{(k)}\right)r_{ij}^{2}\right]}_{1\leq i,j\leq m}&i\neq j\\ {\left[\sum_{l=1}^{m}{2b_{il}^{(k)}\left(1-b_{il}^{(k)}\right)r_{il}^{2}}\right]}_{1\leq i\leq m}&i=j\end{cases}$ $\displaystyle={\left(\mathbf{\bar{R}}^{(k)}\right)}^{2}+\mathbf{R}_{0}^{(k)}\triangleq\mathbf{\tilde{R}}^{(k)},$ $$

in which $\mathbf{R}_{0}^{(k)}$ is a matrix whose rows and columns sum to zero.

[(c)](#A4.I2.i3) In order to prove this inequality, we expand the left-hand side frobenius norm by its columns and use the results of part [(b)](#A4.I2.i2) of this lemma. We have

$$ $\displaystyle\mathbb{E}_{\mathbf{\Xi}^{(k)}}$ $\displaystyle{\left[{\left\|\mathbf{P}^{(k)}\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\mathbf{\bar{\theta}}^{(k)}\right\|}^{2}\right]}=\mathbb{E}_{\mathbf{\Xi}^{(k)}}{\left[\sum_{j=1}^{m}{{\left\|\mathbf{P}^{(k)}\mathbf{\theta}_{j}^{(k)}-\bar{\theta}_{j}^{(k)}\mathbf{1}_{m}\right\|}^{2}}\right]}=\mathbb{E}_{\mathbf{\Xi}^{(k)}}{\left[\sum_{j=1}^{m}{{\left\|\mathbf{P}^{(k)}\mathbf{\theta}_{j}^{(k)}-\bar{\theta}_{j}^{(k)}\mathbf{P}^{(k)}\mathbf{1}_{m}\right\|}^{2}}\right]}$ $\displaystyle=\mathbb{E}_{\mathbf{\Xi}^{(k)}}{\left[\sum_{j=1}^{m}{{\left\|\mathbf{P}^{(k)}\left(\mathbf{\theta}_{j}^{(k)}-\bar{\theta}_{j}^{(k)}\mathbf{1}_{m}\right)\right\|}^{2}}\right]}=\mathbb{E}_{\mathbf{\Xi}^{(k)}}{\left[\sum_{j=1}^{m}{{\left(\mathbf{\theta}_{j}^{(k)}-\bar{\theta}_{j}^{(k)}\mathbf{1}_{m}\right)}^{T}{\left(\mathbf{P}^{(k)}\right)}^{T}\mathbf{P}^{(k)}\left(\mathbf{\theta}_{j}^{(k)}-\bar{\theta}_{j}^{(k)}\mathbf{1}_{m}\right)}\right]}$ $\displaystyle=\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[\sum_{j=1}^{m}{{\left(\mathbf{\theta}_{j}^{(k)}-\bar{\theta}_{j}^{(k)}\mathbf{1}_{m}\right)}^{T}\mathbb{E}_{\mathbf{\hat{V}}^{(k)}}{\left[\mathbf{P}^{(k)}\mathbf{P}^{(k)}\right]}\left(\mathbf{\theta}_{j}^{(k)}-\bar{\theta}_{j}^{(k)}\mathbf{1}_{m}\right)}\right]}$ $\displaystyle=\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[\sum_{j=1}^{m}{{\left(\mathbf{\theta}_{j}^{(k)}-\bar{\theta}_{j}^{(k)}\mathbf{1}_{m}\right)}^{T}\mathbf{\tilde{R}}^{(k)}\left(\mathbf{\theta}_{j}^{(k)}-\bar{\theta}_{j}^{(k)}\mathbf{1}_{m}\right)}\right]}\leq\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[\sum_{j=1}^{m}{\tilde{\rho}^{(k)}{\left\|\theta_{j}^{(k)}-\bar{\theta}_{j}^{(k)}\mathbf{1}_{m}\right\|}^{2}}\right]}$ $\displaystyle\leq\tilde{\rho}^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\mathbf{\bar{\theta}}^{(k)}\right\|}^{2}\right]}.$ $$

## Appendix J Proof of Lemma 4.8

Using Eqs. ([3](#S3.E3)) and ([5](#S3.E5)), we first expand the left-hand side norm, and then use Young’s inequality to get

$$ $\displaystyle\Big{\|}\mathbf{\Theta}^{(k+1)}$ $\displaystyle-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k+1)}\Big{\|}^{2}={\left\|\mathbf{P}^{(k)}\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}-\alpha^{(k)}\left(\mathbf{V}^{(k)}\mathbf{G}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{g}v}^{(k)}\right)\right\|}^{2}$ $\displaystyle\begin{aligned} \,\,\leq\Big{\|}\mathbf{P}^{(k)}\mathbf{\Theta}^{(k)}&-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}-\alpha^{(k)}\left(\mathbf{V}^{(k)}\mathbf{\nabla}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\nabla}v}^{(k)}\right)\Big{\|}^{2}\\ &-2\alpha^{(k)}\,\Big{\langle}\mathbf{P}^{(k)}\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}-\alpha^{(k)}\left(\mathbf{V}^{(k)}\mathbf{\nabla}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\nabla}v}^{(k)}\right),\mathbf{V}^{(k)}\mathbf{E}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\epsilon}v}^{(k)}\Big{\rangle}\\ &+{\left(\alpha^{(k)}\right)}^{2}{\left\|\mathbf{V}^{(k)}\mathbf{E}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\epsilon}v}^{(k)}\right\|}^{2}\end{aligned}$ $$

$$ $\displaystyle\,\,\leq\left(1+\frac{1-\tilde{\rho}^{(k)}}{2\tilde{\rho}^{(k)}}\right)$ $\displaystyle{\left\|\mathbf{P}^{(k)}\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}+\left(1+\frac{2\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}\right){\left(\alpha^{(k)}\right)}^{2}{\left\|\mathbf{V}^{(k)}\mathbf{\nabla}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\nabla}v}^{(k)}\right\|}^{2}$ $\displaystyle-2\alpha^{(k)}\,\bigg{\langle}\mathbf{P}^{(k)}\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}-\alpha^{(k)}\left(\mathbf{V}^{(k)}\mathbf{\nabla}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\nabla}v}^{(k)}\right),\left(\mathbf{I}_{m}-\frac{1}{m}\mathbf{1}_{m}\mathbf{1}_{m}^{T}\right)\mathbf{V}^{(k)}\mathbf{E}^{(k)}\bigg{\rangle}$ $\displaystyle+{\left(\alpha^{(k)}\right)}^{2}{\left\|\mathbf{V}^{(k)}\mathbf{E}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\epsilon}v}^{(k)}\right\|}^{2}.$ $$

Next, we take the expected value of the above inequality and use Lemmas [D.2](#A4.Thmtheorem2), [D.3](#A4.Thmtheorem3) and [D.4](#A4.Thmtheorem4)-[(c)](#A4.I2.i3) to get

$$ $\displaystyle\mathbb{E}_{\mathbf{\Xi}^{(k)}}$ $\displaystyle{\left[{\left\|\mathbf{\Theta}^{(k+1)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k+1)}\right\|}^{2}\right]}\leq\frac{1+\tilde{\rho}^{(k)}}{2\tilde{\rho}^{(k)}}\tilde{\rho}^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}$ $\displaystyle\quad\,\,\begin{aligned} +3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}d_{max}^{(k)}{\left(\alpha^{(k)}\right)}^{2}\bigg{(}m\delta^{2}&+\left(\zeta^{2}+2\beta^{2}\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}\\ &+m\left(\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\right]}\bigg{)}\end{aligned}$ $\displaystyle\quad\,\,\begin{aligned} -2\alpha^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k)}\setminus\mathbf{E}^{(k)}}\Bigg{[}\bigg{\langle}\mathbf{P}^{(k)}\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}&-\alpha^{(k)}\left(\mathbf{V}^{(k)}\mathbf{\nabla}^{(k)}-\mathbf{1}_{m}\overline{\mathbf{\nabla}v}^{(k)}\right),\\ &\left(\mathbf{I}_{m}-\frac{1}{m}\mathbf{1}_{m}\mathbf{1}_{m}^{T}\right)\mathbf{V}^{(k)}\mathbb{E}_{\mathbf{E}^{(k)}}{\left[\mathbf{E}^{(k)}\right]}\bigg{\rangle}\Bigg{]}+m{\left(\alpha^{(k)}\right)}^{2}d_{max}^{(k)}\sigma^{2}\end{aligned}$ $\displaystyle\begin{aligned} \leq\Bigg{[}\frac{1+\tilde{\rho}^{(k)}}{2}&+3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}d_{max}^{(k)}{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\right)\Bigg{]}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}\\ &+3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}md_{max}^{(k)}{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\right]}\\ &+m{\left(\alpha^{(k)}\right)}^{2}d_{max}^{(k)}\left(3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}\delta^{2}+\sigma^{2}\right)\end{aligned}$ $$

## Appendix K Proof of Proposition 4.10

Step 1: Setting up the proof.
We want to find the conditions under which we will have $\rho{\left(\mathbf{\Phi}^{(k)}\right)}<1$. As we have $\mathbf{\Phi}^{(k)}={\left[\phi_{ij}\right]}_{1\leq i,j\leq 2}$ and $\rho{\left(\mathbf{\Phi}^{(k)}\right)}=\max{\left\{\left\lvert\lambda_{1}^{(k)}\right\rvert,\left\lvert\lambda_{2}^{(k)}\right\rvert\right\}}$ where $\lambda_{i}^{(k)}$ are the eigenvalues of the matrix $\mathbf{\Phi}^{(k)}$ for $i=1,2$, we need to show that $\max{\left\{\left\lvert\lambda_{1}^{(k)}\right\rvert,\left\lvert\lambda_{2}^{(k)}\right\rvert\right\}}<1$. Therefore, we first write the eigenvalue equation of the matrix as

$$ $\begin{gathered}\left(\lambda-\phi_{11}^{(k)}\right)\left(\lambda-\phi_{22}^{(k)}\right)-\phi_{12}^{(k)}\phi_{21}^{(k)}=0\quad\Rightarrow\quad\lambda^{2}-\left(\phi_{11}^{(k)}+\phi_{22}^{(k)}\right)\lambda+\phi_{11}^{(k)}\phi_{22}^{(k)}-\phi_{12}^{(k)}\phi_{21}^{(k)}=0.\end{gathered}$ $$

Since this is a quadratic equation in the form of $a\lambda^{2}+b\lambda+c=0$, we know that if $b<0$, and $a,c>0$ and the determinant is positive, we will have $\max{\left\{\left|\lambda_{1}^{(k)}\right|,\left|\lambda_{2}^{(k)}\right|\right\}}=\frac{-b+\sqrt{b^{2}-4ac}}{2a}$. Therefore, we solve for $\frac{-b+\sqrt{b^{2}-4ac}}{2a}<1$ as follows

$$ $\sqrt{b^{2}-4ac}<b+2a\quad\Rightarrow\quad 4a\left(b+c\right)+4a^{2}>0\quad\Rightarrow\quad a+b+c>0.$ $$

Now, rewriting the above inequality in terms of the actual coefficients, we get

$$ $1-\phi_{11}^{(k)}-\phi_{22}^{(k)}+\phi_{11}^{(k)}\phi_{22}^{(k)}-\phi_{12}^{(k)}\phi_{21}^{(k)}>0\quad\Rightarrow\quad\left(1-\phi_{11}^{(k)}\right)\left(1-\phi_{22}^{(k)}\right)>\phi_{12}^{(k)}\phi_{21}^{(k)}.$ (15) $$

Furthermore, note that $a=1>0$, $b=-\left(\phi_{11}^{(k)}+\phi_{22}^{(k)}\right)<0$ and $b^{2}-4ac={\left(\phi_{11}^{(k)}-\phi_{22}^{(k)}\right)}^{2}+4\phi_{12}^{(k)}\phi_{21}^{(k)}>0$ hold by definition, so we only need to check for

$$ $c=\phi_{11}^{(k)}\phi_{22}^{(k)}-\phi_{12}^{(k)}\phi_{21}^{(k)}>0.$ (16) $$

Eqs. ([15](#A11.E15)) and ([16](#A11.E16)) lay out the necessary conditions in order to get $\rho{\left(\mathbf{\Phi}^{(k)}\right)}<1$.

Step 2: Simplifying the conditions.
Starting off with the more important of the two, we first solve for Eq. ([15](#A11.E15)). In order to simplify this inequality, we choose to have (i) $0<\phi_{11}^{(k)}\leq 1$ and (ii) $0<\phi_{22}^{(k)}\leq 1$ for the main diagonal entries. For $\phi_{11}^{(k)}$ as defined in Lemma [4.7](#S4.Thmtheorem7), we have

$$ $\phi_{11}^{(k)}\leq 1\qquad\Rightarrow\qquad\frac{1+\mu\alpha^{(k)}-{\left(\mu\alpha^{(k)}\right)}^{2}}{1+\mu\alpha^{(k)}}\geq\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right).$ (17) $$

To better characterize the condition on $\alpha^{(k)}$ based on the above inequality, we put the following constraint on $\alpha^{(k)}$ to get

$$ $\text{Constraint 1: }\alpha^{(k)}\leq\frac{\Gamma_{1}^{(k)}}{\mu}\quad\Rightarrow\quad\mu\alpha^{(k)}\geq\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\left(1+\Gamma_{1}^{(k)}\right)+{\left(\Gamma_{1}^{(k)}\right)}^{2}-1,$ $$

where $\Gamma_{1}^{(k)}>0$ is a scalar. The above condition requires the step size $\alpha^{(k)}$ to be lower-bounded, which is something we want to avoid. Thus, if the right-hand side of the inequality is non-positive, this condition only requires us to choose a non-negative value for the step size, which is sensible. So, we have

$$ $\begin{gathered}\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\left(1+\Gamma_{1}^{(k)}\right)+{\left(\Gamma_{1}^{(k)}\right)}^{2}-1\leq 0\\ \Rightarrow\qquad{\left(\Gamma_{1}^{(k)}\right)}^{2}+\left(\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)\Gamma_{1}^{(k)}+\left(\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)-1\right)\leq 0\\ \Rightarrow\qquad\left\lvert\Gamma_{1}^{(k)}-\frac{\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right\rvert\leq\left\lvert\frac{\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)-1\right\rvert\\ \Rightarrow\qquad\begin{cases}d_{min}^{(k)}<1-\frac{\mu^{2}}{\beta^{2}}:&1\leq\Gamma_{1}^{(k)}\leq\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)-1\\ d_{min}^{(k)}>1-\frac{\mu^{2}}{\beta^{2}}:&\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)-1\leq\Gamma_{1}^{(k)}\leq 1\end{cases}\\ \Rightarrow\qquad\min{\left\{1,\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)-1\right\}}\leq\Gamma_{1}^{(k)}\leq\max{\left\{1,\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)-1\right\}}.\end{gathered}$ $$

We observe that we found a lower and upper bound for the choice of $\Gamma_{1}^{(k)}$. Note that this lower bound is not on the step size, as we only have $\alpha^{(k)}\leq\frac{\Gamma_{1}^{(K)}}{\mu}$.

Next, in order to simplify $\phi_{11}^{(k)}$ as defined in Lemma [4.7](#S4.Thmtheorem7), we can use Eq. ([17](#A11.E17)) to write

$$ $\text{Constraint 2: }\frac{1+\mu\alpha^{(k)}-{\left(\mu\alpha^{(k)}\right)}^{2}}{1+\mu\alpha^{(k)}}\geq\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\Gamma_{2}^{(k)},$ $$

in which $\Gamma_{2}^{(k)}\geq 1$ ensures that the constraint is satisfied, since we solved for Eq. ([17](#A11.E17)) and found the conditions on $\alpha^{(k)}$ and $\Gamma_{1}^{(k)}$ to do so. Hence, for the bounds defined in Lemma [4.7](#S4.Thmtheorem7), we get

$$ $\begin{gathered}\phi_{11}^{(k)}\leq 1-\frac{2}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\left(1-d_{min}^{(k)}\right)\beta^{2}\alpha^{(k)},\qquad\phi_{12}^{(k)}\leq\frac{\left(1+\Gamma_{1}^{(k)}\right)d_{max}^{(k)}\beta^{2}}{m\mu}\alpha^{(k)},\\ \psi_{1}^{(k)}\leq\frac{2\alpha^{(k)}}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(1-d_{min}^{(k)}\right)\delta^{2}+\frac{{\left(\alpha^{(k)}\right)}^{2}d_{max}^{(k)}\sigma^{2}}{m},\end{gathered}$ $$

and there are no changes to the upper bounds of $\phi_{21}^{(k)}$, $\phi_{22}^{(k)}$ and $\psi_{2}^{(k)}$, which were defined in Lemma [4.8](#S4.Thmtheorem8). Note that matrix $\mathbf{\Phi}^{(k)}$ and vector $\mathbf{\Psi}^{(k)}$ in Eq. ([7](#S4.E7)) were used as upper bounds, therefore we can always replace their values with new upper bounds for them. Consequently, with this new value for $\phi_{11}^{(k)}$, we continue as

$$ $\phi_{11}^{(k)}>0\quad\Rightarrow\quad\alpha^{(k)}<\frac{\mu}{2\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\left(1-d_{min}^{(k)}\right)\beta^{2}}.$ $$

Finally, we check the next conditions on $\phi_{22}^{(k)}$ defined in Lemma [4.8](#S4.Thmtheorem8), i.e., $0<\phi_{22}^{(k)}\leq 1$. Note that for $\phi_{11}^{(k)}$, $\phi_{12}^{(k)}$ and $\phi_{21}^{(k)}$ the lower bound is 0 0, but for $\phi_{22}^{(k)}$ it is $\frac{1+\tilde{\rho}^{(k)}}{2}$. Therefore, the lower-bound condition of $\phi_{22}^{(k)}>0$ is already met. For the upper-bound condition $\phi_{22}^{(k)}\leq 1$, noting that we have $\frac{3+\tilde{\rho}^{(k)}}{4}<1$, we can write $\phi_{22}^{(k)}\leq\frac{3+\tilde{\rho}^{(k)}}{4}$ to enforce this constraint. We have

$$ $\frac{1+\tilde{\rho}^{(k)}}{2}\leq\phi_{22}^{(k)}\leq\frac{3+\tilde{\rho}^{(k)}}{4}\quad\Rightarrow\quad 0\leq\alpha^{(k)}\leq\frac{1}{2\sqrt{3d_{max}^{(k)}}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}}$ $$

Step 3: Determining the constraints.
Now that we have made sure that (i) $0<\phi_{11}^{(k)}\leq 1$ and (ii) $0<\phi_{22}^{(k)}\leq 1$ in the previous step, we can continue to solve Eq. ([15](#A11.E15)). For the left-hand side of the inequality, we have

$$ $\displaystyle\left(1-\phi_{11}^{(k)}\right)\left(1-\phi_{22}^{(k)}\right)$ $\displaystyle=\left[\frac{2}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\left(1-d_{min}^{(k)}\right)\beta^{2}\alpha^{(k)}\right]\left(1-\phi_{22}^{(k)}\right)$ $\displaystyle\geq\left[\frac{2}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\left(1-d_{min}^{(k)}\right)\beta^{2}\alpha^{(k)}\right]\frac{1-\tilde{\rho}^{(k)}}{4}.$ $$

Now, putting this back to Eq. ([15](#A11.E15)), we get

$$ $\begin{gathered}\left[\frac{2}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\left(1-d_{min}^{(k)}\right)\beta^{2}\alpha^{(k)}\right]\frac{1-\tilde{\rho}^{(k)}}{4}>\phi_{12}^{(k)}\phi_{21}^{(k)}\\ \begin{aligned} \Rightarrow\qquad&\left[\frac{\left(1+\Gamma_{1}^{(k)}\right)d_{max}^{(k)}\beta^{2}}{m\mu}\alpha^{(k)}\right]\left[3md_{max}^{(k)}\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}\left(\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)\right){\left(\alpha^{(k)}\right)}^{2}\right]\\ &<\left[\frac{2}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\left(1-d_{min}^{(k)}\right)\beta^{2}\alpha^{(k)}\right]\frac{1-\tilde{\rho}^{(k)}}{4}\end{aligned}\\ \Rightarrow\qquad\alpha^{(k)}<\frac{\sqrt{\Gamma_{2}^{(k)}-1}\sqrt{1-d_{min}^{(k)}}\left(1-\tilde{\rho}^{(k)}\right)}{\sqrt{6}d_{max}^{(k)}\sqrt{1+\tilde{\rho}^{(k)}}\sqrt{\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)}}.\end{gathered}$ $$

Finally, we solve for Eq. ([16](#A11.E16)). Noting that by solving Eq. ([15](#A11.E15)) we made sure that $1-\phi_{11}^{(k)}-\phi_{22}^{(k)}+\phi_{11}^{(k)}\phi_{22}^{(k)}-\phi_{12}^{(k)}\phi_{21}^{(k)}>0$, we can write

$$ $\begin{gathered}c>0\quad\Rightarrow\quad\phi_{11}^{(k)}\phi_{22}^{(k)}-\phi_{12}^{(k)}\phi_{21}^{(k)}>0\quad\Rightarrow\quad\phi_{11}^{(k)}+\phi_{22}^{(k)}-1>0\\ \Rightarrow\quad 1-\frac{2}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\left(1-d_{min}^{(k)}\right)\beta^{2}\alpha^{(k)}+\frac{1+\tilde{\rho}^{(k)}}{2}-1>0\\ \Rightarrow\qquad\alpha^{(k)}<\frac{\mu\left(1+\tilde{\rho}^{(k)}\right)}{4\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\left(1-d_{min}^{(k)}\right)\beta^{2}}.\end{gathered}$ $$

Step 4: Putting all the constraints together.
Reviewing all the constraints on $\alpha^{(k)}$ from the beginning of this appendix, we can collect all of the constraints together and simplify them as

$$ $\displaystyle\begin{aligned} \alpha^{(k)}<\min\Bigg{\{}&\frac{\Gamma_{1}^{(k)}}{\mu},\frac{1}{2\sqrt{3d_{max}^{(k)}}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}},\frac{\mu}{2\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\left(1-d_{min}^{(k)}\right)\beta^{2}},\\ &\frac{\mu\left(1+\tilde{\rho}^{(k)}\right)}{4\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\left(1-d_{min}^{(k)}\right)\beta^{2}},\frac{\sqrt{\Gamma_{2}^{(k)}-1}\sqrt{1-d_{min}^{(k)}}\left(1-\tilde{\rho}^{(k)}\right)}{\sqrt{6}d_{max}^{(k)}\sqrt{1+\tilde{\rho}^{(k)}}\sqrt{\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)}}\Bigg{\}}\end{aligned}$ $\displaystyle\begin{aligned} =\min\Bigg{\{}&\frac{\Gamma_{1}^{(k)}}{\mu},\frac{1}{2\sqrt{3d_{max}^{(k)}}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}},\frac{\mu\left(1+\tilde{\rho}^{(k)}\right)}{4\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\left(1-d_{min}^{(k)}\right)\beta^{2}},\\ &\frac{\sqrt{\Gamma_{2}^{(k)}-1}\sqrt{1-d_{min}^{(k)}}\left(1-\tilde{\rho}^{(k)}\right)}{\sqrt{6}d_{max}^{(k)}\sqrt{1+\tilde{\rho}^{(k)}}\sqrt{\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)}}\Bigg{\}},\end{aligned}$ $$

while satisfying

$$ $\Gamma_{1}^{(k)}>0,\qquad\min{\left\{1,\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)-1\right\}}\leq\Gamma_{1}^{(k)}\leq\max{\left\{1,\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)-1\right\}},\qquad\Gamma_{2}^{(k)}>1.$ (18) $$

Note that one of the terms in the above minimization function was trivially removed since $\frac{1+\tilde{\rho}^{(k)}}{2}<1$. In order to simply the condition on $\alpha^{(k)}$ further, we take the minimum of these terms with respect to each variable separately to get

$$ $\displaystyle\alpha^{(k)}<\min\Bigg{\{}\min_{\Gamma_{1}^{(k)}}\Bigg{\{}\frac{\Gamma_{1}^{(k)}}{\mu},$ $\displaystyle\min_{\Gamma_{2}^{(k)}}\Bigg{\{}\frac{\mu\left(1+\tilde{\rho}^{(k)}\right)}{4\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\left(1-d_{min}^{(k)}\right)\beta^{2}},$ (19) $\displaystyle\frac{\sqrt{\Gamma_{2}^{(k)}-1}\sqrt{1-d_{min}^{(k)}}\left(1-\tilde{\rho}^{(k)}\right)}{\sqrt{6}d_{max}^{(k)}\sqrt{1+\tilde{\rho}^{(k)}}\sqrt{\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)}}\Bigg{\}}\Bigg{\}},\frac{1}{2\sqrt{3d_{max}^{(k)}}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}}\Bigg{\}}.$ $$

Solving for the inner minimization in Eq. ([19](#A11.E19)) first using $\Gamma_{2}^{(k)}$ by defining $c_{1}^{(k)}=\frac{\sqrt{1-d_{min}^{(k)}}\left(1-\tilde{\rho}^{(k)}\right)}{\sqrt{6}d_{max}^{(k)}\sqrt{1+\tilde{\rho}^{(k)}}\sqrt{\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)}}$ and $c_{2}^{(k)}=\frac{4\left(1+\Gamma_{1}^{(k)}\right)\left(1-d_{min}^{(k)}\right)\beta^{2}}{\mu\left(1+\tilde{\rho}^{(k)}\right)}$, we have

$$ $\begin{cases}c_{1}^{(k)}\sqrt{\Gamma_{2}^{(k)}-1}\leq\frac{1}{c_{2}^{(k)}(\Gamma_{2}^{(k)}-1)};&1<\Gamma_{2}^{(k)}\leq{\Gamma_{2}^{\star}}^{(k)}\\ \frac{1}{c_{2}^{(k)}(\Gamma_{2}^{(k)}-1)}\leq c_{1}^{(k)}\sqrt{\Gamma_{2}^{(k)}-1};&\Gamma_{2}^{(k)}\geq{\Gamma_{2}^{\star}}^{(k)}\end{cases},$ (20) $$

in which $\Gamma_{2}^{(k)}>1$ is due to Eq. ([18](#A11.E18)). We can see that in Eq. ([20](#A11.E20)), one of the expressions is increasing with respect to $\Gamma_{2}^{(k)}$, and the other one is decreasing. Thus, we find the optimal value for it $\Gamma_{2}^{\star(k)}$ as

$$ $\begin{gathered}\sqrt{{\Gamma_{2}^{\star}}^{(k)}-1}^{3}=\frac{1}{c_{1}^{(k)}c_{2}^{(k)}}\qquad\Rightarrow\qquad{\Gamma_{2}^{\star}}^{(k)}=\frac{1}{{\left(c_{1}^{(k)}c_{2}^{(k)}\right)}^{2/3}}+1\\ \begin{aligned} \Rightarrow{\Gamma_{2}^{\star}}^{(k)}&={\left(\frac{\sqrt{6}d_{max}^{(k)}\sqrt{1+\tilde{\rho}^{(k)}}\sqrt{\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)}}{\sqrt{1-d_{min}^{(k)}}\left(1-\tilde{\rho}^{(k)}\right)}\frac{\mu\left(1+\tilde{\rho}^{(k)}\right)}{4\left(1+\Gamma_{1}^{(k)}\right)\left(1-d_{min}^{(k)}\right)\beta^{2}}\right)}^{2/3}+1\\ &=\frac{(1+\tilde{\rho}^{(k)})\sqrt[3]{3}\sqrt[3]{\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)}}{2\left(1-d_{min}^{(k)}\right)}{\left(\frac{d_{max}^{(k)}\mu}{(1-\tilde{\rho}^{(k)})\left(1+\Gamma_{1}^{(k)}\right)\beta^{2}}\right)}^{2/3}+1\end{aligned}\end{gathered}$ $$

In order to simplify the above value for $\Gamma_{2}^{\star(k)}$, we bound it as

$$ ${\left(\frac{\sqrt{3}\mu\zeta d_{min}^{(k)}}{2\left(1+\Gamma_{1}^{(k)}\right)\beta}\right)}^{2/3}+1<{\Gamma_{2}^{\star}}^{(k)}<{\left(\frac{3\sqrt{2}d_{max}^{(k)}}{{\left(1-d_{max}^{(k)}\right)}^{3/2}\left(1-\tilde{\rho}^{(k)}\right)\left(1+\Gamma_{1}^{(k)}\right)}\right)}^{2/3}+1.$ $$

Note that if $d_{min}^{(k)}\to 0$ and $d_{max}^{(k)}\to 1$, then we would have $1<{\Gamma_{2}^{\star}}^{(k)}<\infty$. Choosing $\Gamma_{2}^{(k)}=\Gamma_{2}^{(k)\star}$, we get

$$ $\displaystyle\min_{\Gamma_{2}^{(k)}}$ $\displaystyle\left\{\frac{\mu\left(1+\tilde{\rho}^{(k)}\right)}{4\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\left(1-d_{min}^{(k)}\right)\beta^{2}},\frac{\sqrt{\Gamma_{2}^{(k)}-1}\sqrt{1-d_{min}^{(k)}}\left(1-\tilde{\rho}^{(k)}\right)}{\sqrt{6}d_{max}^{(k)}\sqrt{1+\tilde{\rho}^{(k)}}\sqrt{\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)}}\right\}$ $\displaystyle\geq\frac{\mu\left(1+\tilde{\rho}^{(k)}\right){\left(c_{1}^{(k)}c_{2}^{(k)}\right)}^{2/3}}{4\left(1+\Gamma_{1}^{(k)}\right)\left(1-d_{min}^{(k)}\right)\beta^{2}}={\left(\frac{{(c_{1}^{(k)})}^{2}}{c_{2}^{(k)}}\right)}^{1/3}={\left(\frac{\mu}{6(1+\Gamma_{1}^{(k)})\left(\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)\right)}\right)}^{1/3}{\left(\frac{1-\tilde{\rho}^{(k)}}{2d_{max}^{(k)}\beta}\right)}^{2/3}$ $$

Moving on to the second minimization in Eq. ([19](#A11.E19)) using $\Gamma_{1}^{(k)}$, we note that finding the optimal value $\Gamma_{1}^{\star(k)}$ would be analytically cumbersome due to the conditions that need to be satisfied for it; First, $\Gamma_{1}^{(k)}>0$, and second, $\min{\left\{1,\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)-1\right\}}\leq\Gamma_{1}^{(k)}\leq\max{\left\{1,\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)-1\right\}}$. Thus, in order to get a more intuitive upper bound for $\alpha^{(k)}$, we settle for a possible suboptimal value for it. If we choose $\Gamma_{1}^{(k)}=1$ which is the only point satisfying the conditions in Eq. ([18](#A11.E18)) and it also does not rely on the value of $d_{min}^{(k)}$, we get

$$ $\alpha^{(k)}<\min\Bigg{\{}\frac{1}{\mu},{\left(\frac{\mu}{12\left(\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)\right)}\right)}^{1/3}{\left(\frac{1-\tilde{\rho}^{(k)}}{2d_{max}^{(k)}\beta}\right)}^{2/3},\frac{1}{2\sqrt{3d_{max}^{(k)}}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}}\Bigg{\}}.$ $$

Step 5: Obtaining $\rho(\mathbf{\Phi}^{(k)})$.
We established $\rho(\mathbf{\Phi}^{(k)})<1$ in the previous steps. The last step is to determine what $\rho(\mathbf{\Phi}^{(k)})$ is. We have

$$ $\displaystyle\rho{\left(\Phi^{(k)}\right)}$ $\displaystyle=\frac{-b+\sqrt{b^{2}-4ac}}{2a}=\frac{\phi_{11}^{(k)}+\phi_{22}^{(k)}+\sqrt{{\left(\phi_{11}^{(k)}+\phi_{22}^{(k)}\right)}^{2}-4\left(\phi_{11}^{(k)}\phi_{22}^{(k)}-\phi_{12}^{(k)}\phi_{21}^{(k)}\right)}}{2}$ $\displaystyle=\frac{\phi_{11}^{(k)}+\phi_{22}^{(k)}+\sqrt{{\left(\phi_{11}^{(k)}-\phi_{22}^{(k)}\right)}^{2}+4\phi_{12}^{(k)}\phi_{21}^{(k)}}}{2}$ $\displaystyle\begin{aligned} &\begin{aligned} \,\,=\frac{1}{2}\bigg{[}1-\frac{2}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)&\left(1-d_{min}^{(k)}\right)\beta^{2}\alpha^{(k)}+\frac{1+\tilde{\rho}^{(k)}}{2}+3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}d_{\max}^{(k)}{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\right)\bigg{]}\end{aligned}\\ &\begin{aligned} \qquad\qquad+\frac{1}{2}\Bigg{[}\bigg{(}&1-\frac{2}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\left(1-d_{min}^{(k)}\right)\beta^{2}\alpha^{(k)}\\ &-\frac{1+\tilde{\rho}^{(k)}}{2}-3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}d_{\max}^{(k)}{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\right)\bigg{)}^{2}\end{aligned}\\ &\qquad\qquad+4\frac{\left(1+\Gamma_{1}^{(k)}\right)d_{max}^{(k)}\beta^{2}}{m\mu}\alpha^{(k)}3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}md_{\max}^{(k)}{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)\right)\Bigg{]}^{1/2}\end{aligned}$ $$

$$ $\displaystyle\begin{aligned} \,\,=\frac{3+\tilde{\rho}^{(k)}}{4}&-\frac{1}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\left(1-d_{min}^{(k)}\right)\beta^{2}\alpha^{(k)}+\frac{3}{2}\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}d_{\max}^{(k)}\left(\zeta^{2}+2\beta^{2}\right){\left(\alpha^{(k)}\right)}^{2}\\ &\begin{aligned} \,\,+\frac{1}{2}\Bigg{[}\bigg{(}\frac{1-\tilde{\rho}^{(k)}}{2}&-\frac{2}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\left(1-d_{min}^{(k)}\right)\beta^{2}\alpha^{(k)}\\ &-3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}d_{\max}^{(k)}\left(\zeta^{2}+2\beta^{2}\right){\left(\alpha^{(k)}\right)}^{2}\bigg{)}^{2}\end{aligned}\\ &+12\frac{\left(1+\Gamma_{1}^{(k)}\right)\beta^{2}}{\mu}\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}{\left(d_{\max}^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)\right){\left(\alpha^{(k)}\right)}^{3}\Bigg{]}^{1/2}.\end{aligned}$ $$

## Appendix L Proof of Theorem 4.11

Note that by the properties of spectral radius, we have that $\mathbf{\Phi}\|\cdot\|\leq\rho(\mathbf{\Phi})\|\cdot\|$. Now, using Eq. ([8](#S4.E8)), we can write

$$ $\begin{bmatrix}\mathbb{E}_{\mathbf{\Xi}^{(k)}}{\left[{\left\|\mathbf{\bar{\theta}}^{(k+1)}-\mathbf{\theta}^{\star}\right\|}^{2}\right]}\\ \mathbb{E}_{\mathbf{\Xi}^{(k)}}{\left[{\left\|\mathbf{\Theta}^{(k+1)}-\mathbf{1}_{m}\mathbf{\bar{\theta}}^{(k+1)}\right\|}^{2}\right]}\end{bmatrix}\leq\rho{\left(\mathbf{\Phi}\right)}^{k+1}\begin{bmatrix}{\left\|\mathbf{\bar{\theta}}^{(0)}-\mathbf{\theta}^{\star}\right\|}^{2}\\ {\left\|\mathbf{\Theta}^{(0)}-\mathbf{1}_{m}\mathbf{\bar{\theta}}^{(0)}\right\|}^{2}\end{bmatrix}+\sum_{r=1}^{k}{\rho{\left(\mathbf{\Phi}\right)}^{k-r+1}\mathbf{\Psi}}+\mathbf{\Psi}.$ $$

We emphasize that the time index $k$ in $\mathbf{\Phi}^{(k)}$ and $\mathbf{\Psi}^{(k)}$ was dropped, since we are using a constant step size, constant SGD and aggregation probabilities. This results in the constant matrix $\mathbf{\Phi}^{(k)}=\mathbf{\Phi}$ and the constant vector $\mathbf{\Psi}^{(k)}=\mathbf{\Psi}$. Focusing on the term $\sum_{r=1}^{k}{\rho{\left(\mathbf{\Phi}\right)}^{k-r+1}\mathbf{\Psi}}+\mathbf{\Psi}$, we get

$$ $\sum_{r=1}^{k}{\rho{\left(\mathbf{\Phi}\right)}^{k-r+1}\mathbf{\Psi}}+\mathbf{\Psi}=\sum_{r=1}^{k+1}{\rho{\left(\mathbf{\Phi}\right)}^{k-r+1}\mathbf{\Psi}}=\left(\sum_{u=0}^{k}{\rho{\left(\mathbf{\Phi}\right)}^{u}}\right)\mathbf{\Psi}\leq\left(\sum_{u=0}^{\infty}{\rho{\left(\mathbf{\Phi}\right)}^{u}}\right)\mathbf{\Psi}=\frac{1}{1-\rho{\left(\mathbf{\Phi}\right)}}\mathbf{\Psi}.$ $$

Putting the above inequalities together concludes the proof of Eq. ([9](#S4.E9)). Finally, noting that $\rho{(\mathbf{\Phi})}<1$ following [4.10](#S4.Thmtheorem10), We can let $k\to\infty$ to get Eq. ([10](#S4.E10)).

## Appendix M Diminishing Step Size Policy

In this appendix, we do the convergence analysis of our methodology under a diminishing step size policy, i.e., when $\alpha^{(k+1)}<\alpha^{(k)}$ for all $k\geq 0$. We will show that convergence to the globally optimal point is possible if the frequency of SGDs, i.e., $d_{i}^{(k)}$, is increasing over time. Thus, a few preliminary lemmas are first required, to re-derive the counterpart of Proposition [4.10](#S4.Thmtheorem10) for the increasing $d_{i}^{(k)}$ strategy.

###### Proposition M.1 .

(See Appendix [N](#A14) for the proof.)
Let Assumptions [4.1](#S4.Thmtheorem1)-[4.3](#S4.Thmtheorem3) hold. If the SGD probabilities are chosen as $d_{i}^{(k)}=1-\Gamma_{3}\alpha^{(0)}$ with $0\leq\Gamma_{3}\leq\frac{1}{\alpha^{(0)}}$, and the step size satisfies the following condition for all $k\geq 0$

$$ $\alpha^{(k)}<\min\Bigg{\{}\frac{\Gamma_{1}^{(k)}}{\mu},\frac{1}{2\sqrt{3}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}},{\left(\frac{\mu}{6\left(\zeta^{2}+2\Gamma_{3}\Gamma_{1}^{(k)}\frac{\beta^{2}}{\mu}\right)\left(1+\Gamma_{1}^{(k)}\right)}\right)}^{1/3}{\left(\frac{1-\tilde{\rho}^{(k)}}{2\beta}\right)}^{2/3}\Bigg{\}}.$ $$

then we have $\rho{\left(\mathbf{\Phi}^{(k)}\right)}<1$ for all $k\geq 0$, in which $\rho{(\cdot)}$ denotes the spectral radius of a given matrix, and $\mathbf{\Phi}^{(k)}$ is given in the linear system of inequalities of Eq. ([7](#S4.E7)). $\rho(\mathbf{\Phi}^{(k)})$ is given by

$\rho(\mathbf{\Phi}^{(k)})=1-h{(\alpha^{(k)})}$, where $h{(\alpha^{(k)})}=\frac{1-\tilde{\rho}^{(k)}}{4}+A\alpha^{(k)}-B{(\alpha^{(k)})}^{2}-\frac{1}{2}\sqrt{{(\frac{1-\tilde{\rho}^{(k)}}{2}-2(A\alpha^{(k)}+B{(\alpha^{(k)})}^{2}))}^{2}+C{(\alpha^{(k)})}^{3}}$, and $A=\frac{\Gamma_{3}\Gamma_{1}^{(k)}}{\mu}(1+\Gamma_{1}^{(k)})(\Gamma_{2}^{(k)}-1)\beta^{2}$, $B=\frac{3}{2}\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}(\zeta^{2}+2\beta^{2})$, and $C=12\frac{(1+\Gamma_{1}^{(k)})\beta^{2}}{\mu}\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}(\zeta^{2}+2\Gamma_{3}\Gamma_{1}^{(k)}\frac{\beta^{2}}{\mu})$.

Proposition [M.1](#A13.Thmtheorem1) implies that $\lim_{k\to\infty}{\mathbf{\Phi}^{(k:0)}}=0$ in Eq. ([8](#S4.E8)). However, note that this is only the asymptotic behaviour of $\mathbf{\Phi}^{(k:0)}$, and the exact convergence rate will depend on the choice of the step size $\alpha^{(k)}$. Furthermore, noting that the first expression in Eq. ([8](#S4.E8)) asymptotically approaches zero, Proposition [M.1](#A13.Thmtheorem1) also implies that the optimality gap is determined by the terms $\sum_{r=1}^{k}{\mathbf{\Phi}^{(k:r)}\mathbf{\Psi}^{(r-1)}}+\mathbf{\Psi}^{(k)}$, and it can be made zero if the step size $\alpha^{(k)}$ satisfies certain conditions, which we will discuss in Theorem [M.5](#A13.Thmtheorem5).

Proposition [M.1](#A13.Thmtheorem1) outlines the necessary constraint on the step size $\alpha^{(k)}$ at each iteration $k\geq 0$. We next provide a corollary to Proposition [M.1](#A13.Thmtheorem1), in which we show that under certain conditions, the above-mentioned constraint needs to be satisfied only on the initial value of the step size, i.e, $\alpha^{(0)}$.

###### Corollary M.2 .

(Corollary to Proposition [M.1](#A13.Thmtheorem1))
If the step size $\alpha^{(k)}$ is non-increasing, i.e., $\alpha^{(k+1)}\leq\alpha^{(k)}$, the SGD probabilities are determined as $d_{i}^{(k)}=1-\Gamma_{3}\alpha^{(k)}$ with $0\leq\Gamma_{3}\leq\frac{1}{\alpha^{(0)}}$, for all $k\geq 0$, and we have $\tilde{\rho}^{(k)}\leq\tilde{\rho}=\sup_{k=0,1,...}{\tilde{\rho}^{(k)}}$ for the spectral radius, then the constraints in Proposition [M.1](#A13.Thmtheorem1) simplify to

$$ $\displaystyle\alpha^{(0)}<\min\Bigg{\{}\frac{\Gamma_{1}}{\mu},$ $\displaystyle\frac{1}{2\sqrt{3}}\frac{1-\tilde{\rho}}{\sqrt{1+\tilde{\rho}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}},{\left(\frac{\mu}{6\left(\zeta^{2}+2\Gamma_{3}\Gamma_{1}\frac{\beta^{2}}{\mu}\right)\left(1+\Gamma_{1}\right)}\right)}^{1/3}{\left(\frac{1-\tilde{\rho}}{2\beta}\right)}^{2/3}\Bigg{\}}.$ $$

In the above Corollary, we obtained the constraints on the initial value of the step size, i.e., $\alpha^{(0)}$, that lead to the spectral radius of $\mathbf{\Phi}^{(k)}$ being less than $1$, i.e., $\rho(\mathbf{\Phi}^{(k)})<1$. We need one more ingredient given in the subsequent lemma in order ultimately characterize the short-term behavior and also derive non-asymptotic convergence guarantees on DSpodFL in Theorem [M.5](#A13.Thmtheorem5).

Two final building blocks are necessary for the proof of Theorem [M.5](#A13.Thmtheorem5). We present these in the following lemmas.

###### Lemma M.3 .

(See Lemma 1 in (Zehtabi et al., ) for the proof.)
Let ${\{\zeta_{r}\}}_{r=0}^{\infty}$ be a scalar sequence where $0<\zeta_{r}\leq 1$, $\forall r\geq 0$. For any $p\geq 1$, we have

$$ $\prod_{r=s}^{k}{{\left(1-\zeta_{r}\right)}^{p}}\leq\frac{1}{p\sum_{r=s}^{k}{\zeta_{r}}}.$ $$

Next, we outline another crucial lemma for our analysis.

###### Lemma M.4 .

(See Appendix [O](#A15) for the proof.)
Let a diminishing step size $\alpha^{(k)}=\alpha^{(0)}/\sqrt{1+k/\gamma}$ be used, which satisfies the properties

$$ $\alpha^{(k+1)}<\alpha^{(k)},\qquad\sum_{k=0}^{\infty}{\alpha^{(k)}}=\infty,\qquad\sum_{k=0}^{\infty}{{\left(\alpha^{(k)}\right)}^{2}}<\infty.$ (21) $$

Under the setup of Proposition [M.1](#A13.Thmtheorem1) for the SGD probabilities, i.e., $d_{i}^{(k)}$, if the aggregation probabilities are constant, i.e., $b_{ij}^{(k)}=b_{ij}$ for all $(i,j)\in\mathcal{M}^{2}$, then the following bounds hold

- (a)
$\sum_{q=r}^{k}{\alpha^{(q)}}\geq 2\alpha^{(0)}\left(\sqrt{1+\frac{k}{\gamma}}-\sqrt{1+\frac{r}{\gamma}}\right)$,
- (b)
$h{(\alpha^{(k)})}\geq 2A\alpha^{(k)}$,
- (c)
$\sum_{r=1}^{k}{\frac{{(\alpha^{(r-1)})}^{2}}{\sum_{q=r}^{k}{h{(\alpha^{(q)})}}}}\leq\frac{\alpha^{(0)}}{4A}\left[\frac{1}{\sqrt{1+\frac{k}{\gamma}}-\sqrt{1+\frac{1}{\gamma}}}+\frac{2\left(\gamma+1\right)}{\sqrt{1+\frac{k}{\gamma}}}\left(\ln{\sqrt{1+\frac{k}{\gamma}}}+\ln{\frac{1}{\sqrt{1+\frac{1}{\gamma+k-1}}-1}}\right)+\frac{2\sqrt{1+\frac{k}{\gamma}}}{1+\frac{k-1}{\gamma}}\right]$.

where $h(\alpha^{(k)})$ and the constant $A$ were defined in Proposition [M.1](#A13.Thmtheorem1).

Using Corollary [M.2](#A13.Thmtheorem2) and Lemmas [M.3](#A13.Thmtheorem3) and [M.4](#A13.Thmtheorem4), our main theorem follows.

###### Theorem M.5 .

(See Appendix [P](#A16) for the proof.)
Let Assumptions [4.1](#S4.Thmtheorem1)-[4.3](#S4.Thmtheorem3) hold. If a diminishing step size policy $\alpha^{(k)}=\alpha^{(0)}/\sqrt{1+k/\gamma}$ with $\gamma>0$ satisfying the conditions outlined in Corollary [M.2](#A13.Thmtheorem2) is employed, and the SGD probabilities are all set to same value as $d_{i}^{(k)}=1-\alpha^{(k)}/\alpha^{(0)}$ for all $i\in\mathcal{M}$, while aggregation probabilities are set to constant values, i.e., $b_{ij}^{(k)}=b_{ij}$ for all $(i,j)\in\mathcal{M}^{2}$, then we can rewrite Eq. ([8](#S4.E8)) as

$$ $\nu^{(k+1)}\leq\mathcal{O}{\left(\frac{1}{\sqrt{k}}\right)}\nu^{(0)}+{\left(\alpha^{(0)}\right)}^{2}\left(3\mathcal{O}{\left(\frac{1}{\sqrt{k}}\right)}+\mathcal{O}{\left(\frac{\ln{k}}{\sqrt{k}}\right)}+\mathcal{O}{\left(\frac{1}{k}\right)}\right)\begin{bmatrix}\frac{2}{\mu\alpha^{(0)}}\left(1+\mu\alpha^{(0)}\right)\delta^{2}+\frac{\sigma^{2}}{m}\\ m\left(3\frac{1+\tilde{\rho}}{1-\tilde{\rho}}\delta^{2}+\sigma^{2}\right)\end{bmatrix}.$ (22) $$

Letting $k\to\infty$, we get

$$ $\limsup_{k\to\infty}{\nu^{(k+1)}}=0.$ (23) $$

The bound in Eq. ([22](#A13.E22)) of Theorem [M.5](#A13.Thmtheorem5) indicates that by using a diminishing step size policy of $\alpha^{(k)}=\alpha^{(0)}/\sqrt{1+k/\gamma}$, DSpodFL achieves a sub-linear convergence rate of $\mathcal{O}{(\ln{k}/\sqrt{k})}$, and Eq. ([23](#A13.E23)) shows that asymptotic zero optimality gap as $k\to\infty$ can be achieved.

However, it is worth noting that choosing the SGD probabilities based on the step size, i.e., $d_{i}^{(k)}=1-\alpha^{(k)}/\alpha^{(0)}$ for all $i\in\mathcal{M}$ and $k\geq 0$, is only of theoretical value in this paper. This is because our motivation of introducing the notion of SGD probabilities was to capture computational capabilities of heterogeneous clients in real-world settings, therefore, it is an independent uncontrollable parameter and cannot be chosen based on the step size.

Finally, note that setting $d_{i}^{(k)}=1-\alpha^{(k)}/\alpha^{(0)}$ is equivalent to having all clients in the decentralized system to conduct SGD at each iteration as $k\to\infty$. This result is akin to Wang & Nedic (), in which an increasing similarity between the step sizes of clients is needed for convergence, despite them being initially uncoordinated.

###### Proposition M.1 .

###### Corollary M.2 .

###### Lemma M.3 .

###### Lemma M.4 .

###### Theorem M.5 .

## Appendix N Proof of Proposition M.1

Let the SGD probabilities $d_{i}^{(k)}$ be chosen as the following for all $i\in\mathcal{M}$:

$$ $d_{i}^{(k)}=1-\Gamma_{3}\alpha^{(k)},\qquad 0\leq\Gamma_{3}\leq\frac{1}{\alpha^{(0)}},$ $$

where $\alpha^{(k)}$ is the step size with a diminishing policy, i.e., $\lim_{k\to\infty}{\alpha^{(k)}}=0$. Note that $d_{i}^{(0)}=1-\Gamma_{3}\alpha^{(0)}$ and $\lim_{k\to\infty}{d_{i}^{(k)}}=1$, which means that all clients will basically do SGDs at every iteration for large enough values of $k$. Based on this relationship that we put between the SGD probabilities and the step size, we first rewrite the bounds for matrices $\mathbf{\Phi}^{(k)}$ and $\mathbf{\Psi}^{(k)}$ which were given in Lemmas [4.7](#S4.Thmtheorem7) and [4.8](#S4.Thmtheorem8). We have

$$ $\begin{gathered}\phi_{11}^{(k)}=1-\mu\alpha^{(k)}\left(1+\mu\alpha^{(k)}-{\left(\mu\alpha^{(k)}\right)}^{2}\right)+\frac{2\Gamma_{3}{\left(\alpha^{(k)}\right)}^{2}}{\mu}\left(1+\mu\alpha^{(k)}\right)\beta^{2},\\ \phi_{12}^{(k)}=\left(1+\mu\alpha^{(k)}\right)\left(1-\Gamma_{3}\alpha^{(k)}\right)\frac{\alpha^{(k)}\beta^{2}}{m\mu},\\ \phi_{21}^{(k)}=3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}m\left(1-\Gamma_{3}\alpha^{(k)}\right){\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\Gamma_{3}\alpha^{(k)}\right)\\ \phi_{22}^{(k)}=\frac{1+\tilde{\rho}^{(k)}}{2}+3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}\left(1-\Gamma_{3}\alpha^{(k)}\right){\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\right),\\ \psi_{1}^{(k)}={\left(\alpha^{(k)}\right)}^{2}\left[\frac{2\Gamma_{3}}{\mu}\left(1+\mu\alpha^{(k)}\right)\delta^{2}+\left(1-\Gamma_{3}\alpha^{(k)}\right)\frac{\sigma^{2}}{m}\right],\\ \psi_{2}^{(k)}=m\left(1-\Gamma_{3}\alpha^{(k)}\right){\left(\alpha^{(k)}\right)}^{2}\left(3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}\delta^{2}+\sigma^{2}\right).\end{gathered}$ (24) $$

The important difference with the terms in Eq. ([24](#A14.E24)) and the corresponding ones outlined in Lemmas [4.7](#S4.Thmtheorem7) and [4.8](#S4.Thmtheorem8) is the fact that we get a ${\left(\alpha^{(k)}\right)}^{2}$ factor for $\psi_{1}^{(k)}$ and $\psi_{2}^{(k)}$. This factor will help us show in Theorem [M.5](#A13.Thmtheorem5) that zero optimality gap can be reached, which follows mainly from Eq. ([21](#A13.E21)).

Next, we do an analysis similar to the proof of Proposition [4.10](#S4.Thmtheorem10), which was given in Appendix [K](#A11).

Step 1: Setting up the proof.
We skip repeating the explanations for this step, as they are exactly the same as step 1 in Appendix [K](#A11).

Step 2: Simplifying the conditions.
Recall that we have to ensure (i) $0<\phi_{11}^{(k)}\leq 1$ and (ii) $0<\phi_{22}^{(k)}\leq 1$. For $\phi_{11}^{(k)}$ as defined in Eq. ([24](#A14.E24)), we have

$$ $\qquad\phi_{11}^{(k)}\leq 1\qquad\Rightarrow\qquad\frac{1+\mu\alpha^{(k)}-{\left(\mu\alpha^{(k)}\right)}^{2}}{\left(1+\mu\alpha^{(k)}\right)\alpha^{(k)}}\geq\frac{2\beta^{2}\Gamma_{3}}{\mu^{2}}.$ (25) $$

We then put the following constraint on $\alpha^{(k)}$ to get a tighter lower bound for Eq. ([25](#A14.E25)). We have

$$ $\text{Constraint 1: }\alpha^{(k)}\leq\frac{\Gamma_{1}^{(k)}}{\mu},\qquad\Rightarrow\qquad\mu\alpha^{(k)}>\frac{2\beta^{2}\Gamma_{3}}{\mu^{2}}\Gamma_{1}^{(k)}\left(1+\Gamma_{1}^{(k)}\right)+{\left(\Gamma_{1}^{(k)}\right)}^{2}-1,$ $$

where $\Gamma_{1}^{(k)}>0$ is a scalar. In order to avoid a positive lower-bound on the step size $\alpha^{(k)}$, we find the conditions under which the right-hand side of the above inequality is negative. We have

$$ $\begin{gathered}\frac{2\beta^{2}\Gamma_{3}}{\mu^{2}}\Gamma_{1}^{(k)}\left(1+\Gamma_{1}^{(k)}\right)+{\left(\Gamma_{1}^{(k)}\right)}^{2}-1<0\qquad\Rightarrow\qquad\left(1+\frac{2\beta^{2}\Gamma_{3}}{\mu^{2}}\right){\left(\Gamma_{1}^{(k)}\right)}^{2}+\frac{2\beta^{2}\Gamma_{3}}{\mu^{2}}\Gamma_{1}^{(k)}-1<0,\\ \Rightarrow\quad\left(\left(1+\frac{2\beta^{2}\Gamma_{3}}{\mu^{2}}\right)\Gamma_{1}^{(k)}-1\right)\left(\Gamma_{1}^{(k)}+1\right)<0\quad\Rightarrow\quad-1<\Gamma_{1}^{(k)}<\frac{1}{1+\frac{2\beta^{2}\Gamma_{3}}{\mu^{2}}}.\end{gathered}$ $$

Next, in order to simplify $\phi_{11}^{(k)}$ further, we add another constraint using Eq. ([25](#A14.E25)) to parameterize the lower bound in Eq. ([25](#A14.E25)). We have

$$ $\begin{gathered}\frac{1+\mu\alpha^{(k)}-{\left(\mu\alpha^{(k)}\right)}^{2}}{1+\mu\alpha^{(k)}}\geq\frac{2\beta^{2}\Gamma_{3}}{\mu^{2}}\Gamma_{1}^{(k)},\\ \text{Constraint 2: }\frac{1+\mu\alpha^{(k)}-{\left(\mu\alpha^{(k)}\right)}^{2}}{1+\mu\alpha^{(k)}}>\frac{2\beta^{2}\Gamma_{3}}{\mu^{2}}\Gamma_{1}^{(k)}\Gamma_{2}^{(k)},\qquad\Gamma_{2}^{(k)}>1,\end{gathered}$ $$

in which $\Gamma_{2}^{(k)}>1$ makes sure that the constraint in Eq. ([25](#A14.E25)) is satisfied. Hence, we can update the entries of matrices $\mathbf{\Phi}^{(k)}$ and $\mathbf{\Psi}^{(k)}$ as

$$ $\begin{gathered}\phi_{11}^{(k)}\leq 1-\frac{2\Gamma_{3}\Gamma_{1}^{(k)}}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}\alpha^{(k)},\\ \phi_{12}^{(k)}\leq\frac{\left(1+\Gamma_{1}^{(k)}\right)\beta^{2}}{m\mu}\alpha^{(k)},\qquad\phi_{21}^{(k)}\leq 3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}m{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\Gamma_{3}\Gamma_{1}^{(k)}\frac{\beta^{2}}{\mu}\right)\\ \phi_{22}^{(k)}\leq\frac{1+\tilde{\rho}^{(k)}}{2}+3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\right),\\ \psi_{1}^{(k)}\leq{\left(\alpha^{(k)}\right)}^{2}\left[\frac{2\Gamma_{3}}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\delta^{2}+\frac{\sigma^{2}}{m}\right],\quad\psi_{2}^{(k)}\leq m{\left(\alpha^{(k)}\right)}^{2}\left(3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}\delta^{2}+\sigma^{2}\right).\end{gathered}$ (26) $$

Note that matrix $\mathbf{\Phi}^{(k)}$ and vector $\mathbf{\Psi}^{(k)}$ in Eq. ([7](#S4.E7)) were used as upper bounds, therefore we can always replace their values with new upper bounds for them. Consequently, with this new value for $\phi_{11}^{(k)}$, we continue as

$$ $\phi_{11}^{(k)}>0\qquad\Rightarrow\qquad\alpha^{(k)}<\frac{\mu}{2\Gamma_{3}\Gamma_{1}^{(k)}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}}.$ $$

Finally, we check the next condition $0<\phi_{22}^{(k)}\leq 1$. Noting that we have $\frac{3+\tilde{\rho}^{(k)}}{4}<1$, we can enforce $\phi_{22}^{(k)}\leq 1$ by setting $\phi_{22}^{(k)}\leq\frac{3+\tilde{\rho}^{(k)}}{4}$. We have

$$ $\frac{1+\tilde{\rho}^{(k)}}{2}\leq\phi_{22}^{(k)}\leq\frac{3+\tilde{\rho}^{(k)}}{4}\qquad\Rightarrow\qquad 0\leq\alpha^{(k)}\leq\frac{1}{2\sqrt{3}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}}.$ $$

Step 3: Determining the constraints.
Having made sure that (i) $0<\phi_{11}^{(k)}\leq 1$ and (ii) $0<\phi_{22}^{(k)}\leq 1$ in the previous step, we can continue to solve Eq. ([15](#A11.E15)). For the left-hand side of the inequality, we have

$$ $\displaystyle\left(1-\phi_{11}^{(k)}\right)\left(1-\phi_{22}^{(k)}\right)$ $\displaystyle=\left[\frac{2\Gamma_{3}\Gamma_{1}^{(k)}}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}\alpha^{(k)}\right]\left(1-\phi_{22}^{(k)}\right)$ $\displaystyle\geq\left[\frac{2\Gamma_{3}\Gamma_{1}^{(k)}}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}\alpha^{(k)}\right]\frac{1-\tilde{\rho}^{(k)}}{4}$ $$

Now, putting this back to Eq. ([15](#A11.E15)), we get

$$ $\left[\frac{2\Gamma_{3}\Gamma_{1}^{(k)}}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}\alpha^{(k)}\right]\frac{1-\tilde{\rho}^{(k)}}{4}>\phi_{12}^{(k)}\phi_{21}^{(k)}$ $$

$$ $\begin{gathered}\begin{aligned} \Rightarrow\qquad\left[\frac{\left(1+\Gamma_{1}^{(k)}\right)\beta^{2}}{m\mu}\alpha^{(k)}\right]&\left[3m\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}\left(\zeta^{2}+2\Gamma_{3}\Gamma_{1}^{(k)}\frac{\beta^{2}}{\mu}\right){\left(\alpha^{(k)}\right)}^{2}\right]\\ &<\left[\frac{2\Gamma_{3}\Gamma_{1}^{(k)}}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}\alpha^{(k)}\right]\frac{1-\tilde{\rho}^{(k)}}{4}\end{aligned}\\ \Rightarrow\qquad\alpha^{(k)}<\sqrt{\frac{\Gamma_{3}\Gamma_{1}^{(k)}\left(\Gamma_{2}^{(k)}-1\right){\left(1-\tilde{\rho}^{(k)}\right)}^{2}}{6\left(1+\tilde{\rho}^{(k)}\right)\left(\zeta^{2}+2\Gamma_{3}\Gamma_{1}^{(k)}\frac{\beta^{2}}{\mu}\right)}}.\end{gathered}$ $$

Finally, we solve for Eq. ([16](#A11.E16)), i.e., $c=\phi_{11}^{(k)}\phi_{22}^{(k)}-\phi_{12}^{(k)}\phi_{21}^{(k)}>0$. Noting that by solving Eq. ([15](#A11.E15)) we made sure that $1-\phi_{11}^{(k)}-\phi_{22}^{(k)}+\phi_{11}^{(k)}\phi_{22}^{(k)}-\phi_{12}^{(k)}\phi_{21}^{(k)}>0$, we can write

$$ $\begin{gathered}c>0\quad\Rightarrow\quad\phi_{11}^{(k)}+\phi_{22}^{(k)}-1>0\quad\Rightarrow\quad 1-\frac{2\Gamma_{3}\Gamma_{1}^{(k)}}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}\alpha^{(k)}+\frac{1+\tilde{\rho}^{(k)}}{2}-1>0\\ \Rightarrow\qquad\alpha^{(k)}<\frac{\mu\left(1+\tilde{\rho}^{(k)}\right)}{4\Gamma_{3}\Gamma_{1}^{(k)}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}},\end{gathered}$ $$

in which we have used the value of $\phi_{11}^{(k)}$ itself, but the lower bound of $\phi_{22}^{(k)}$.

Step 4: Putting all the constraints together.
Reviewing
all the constraints on $\alpha^{(k)}$ from the beginning of this appendix, we can collect all of the constraints together and simplify them as

$$ $\displaystyle\begin{aligned} \alpha^{(k)}<\min\Bigg{\{}\frac{\Gamma_{1}^{(k)}}{\mu},&\frac{1}{2\sqrt{3}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}},\frac{\mu}{2\Gamma_{3}\Gamma_{1}^{(k)}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}},\\ &\frac{\mu\left(1+\tilde{\rho}^{(k)}\right)}{4\Gamma_{3}\Gamma_{1}^{(k)}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}},\sqrt{\frac{\Gamma_{3}\Gamma_{1}^{(k)}\left(\Gamma_{2}^{(k)}-1\right){\left(1-\tilde{\rho}^{(k)}\right)}^{2}}{6\left(1+\tilde{\rho}^{(k)}\right)\left(\zeta^{2}+2\Gamma_{3}\Gamma_{1}^{(k)}\frac{\beta^{2}}{\mu}\right)}}\Bigg{\}}\end{aligned}$ (27) $\displaystyle\begin{aligned} =\min\Bigg{\{}\frac{\Gamma_{1}^{(k)}}{\mu},&\frac{1}{2\sqrt{3}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}},\frac{\mu\left(1+\tilde{\rho}^{(k)}\right)}{4\Gamma_{3}\Gamma_{1}^{(k)}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}},\\ &\sqrt{\frac{\Gamma_{3}\Gamma_{1}^{(k)}\left(\Gamma_{2}^{(k)}-1\right){\left(1-\tilde{\rho}^{(k)}\right)}^{2}}{6\left(1+\tilde{\rho}^{(k)}\right)\left(\zeta^{2}+2\Gamma_{3}\Gamma_{1}^{(k)}\frac{\beta^{2}}{\mu}\right)}}\Bigg{\}},\end{aligned}$ $$

while satisfying

$$ $\max{\left\{-1,0\right\}}=0<\Gamma_{1}^{(k)}<\min{\left\{1,\frac{1}{1+\frac{2\beta^{2}\Gamma_{3}}{\mu^{2}}}\right\}}=\frac{1}{1+\frac{2\beta^{2}\Gamma_{3}}{\mu^{2}}},\qquad\Gamma_{2}^{(k)}>1,\qquad 0\leq\Gamma_{3}\leq\frac{1}{\alpha^{(0)}}.$ (28) $$

Note that one of the terms in Eq. ([27](#A14.E27)) was trivially removed since $\frac{1+\tilde{\rho}^{(k)}}{2}<1$. Consequently, we obtain

$$ $\displaystyle\begin{aligned} \alpha^{(k)}<\min_{\Gamma_{1}^{(k)}}\Bigg{\{}\frac{\Gamma_{1}^{(k)}}{\mu},&\frac{1}{2\sqrt{3}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}},\min_{\Gamma_{2}^{(k)},\Gamma_{3}}\Bigg{\{}\frac{\mu\left(1+\tilde{\rho}^{(k)}\right)}{4\Gamma_{3}\Gamma_{1}^{(k)}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}},\\ &\sqrt{\frac{\Gamma_{3}\Gamma_{1}^{(k)}\left(\Gamma_{2}^{(k)}-1\right){\left(1-\tilde{\rho}^{(k)}\right)}^{2}}{6\left(1+\tilde{\rho}^{(k)}\right)\left(\zeta^{2}+2\Gamma_{3}\Gamma_{1}^{(k)}\frac{\beta^{2}}{\mu}\right)}}\Bigg{\}}\Bigg{\}},\end{aligned}$ (29) $$

First, we focus on minimizing the inner expression in Eq. ([29](#A14.E29)) using $\Gamma_{2}^{(k)}$ by defining $c_{1}^{(k)}=\sqrt{\frac{\Gamma_{3}\Gamma_{1}^{(k)}{\left(1-\tilde{\rho}^{(k)}\right)}^{2}}{6\left(1+\tilde{\rho}^{(k)}\right)\left(\zeta^{2}+2\Gamma_{3}\Gamma_{1}^{(k)}\frac{\beta^{2}}{\mu}\right)}}$ and $c_{2}^{(k)}=\frac{4\Gamma_{3}\Gamma_{1}^{(k)}\left(1+\Gamma_{1}^{(k)}\right)\beta^{2}}{\mu\left(1+\tilde{\rho}^{(k)}\right)}$. We can see that one of the above expressions is increasing with respect to $\Gamma_{2}^{(k)}$, and the other one is decreasing. Thus, we have

$$ $\begin{cases}c_{1}^{(k)}\sqrt{\Gamma_{2}^{(k)}-1}\leq\frac{1}{c_{2}^{(k)}\left(\Gamma_{2}^{(k)}-1\right)};&1<\Gamma_{2}^{(k)}\leq{\Gamma_{2}^{\star}}^{(k)}\\ \frac{1}{c_{2}^{(k)}\left(\Gamma_{2}^{(k)}-1\right)}\leq c_{1}^{(k)}\sqrt{\Gamma_{2}^{(k)}-1};&\Gamma_{2}^{(k)}\geq{\Gamma_{2}^{\star}}^{(k)}.\end{cases}$ $$

in which $\Gamma_{2}^{(k)}>1$ is due to Eq. ([28](#A14.E28)). Hence, we find the optimal value for it, i.e., $\Gamma_{2}^{\star(k)}$, as

$$ $\begin{gathered}\sqrt{{\Gamma_{2}^{\star}}^{(k)}-1}^{3}=\frac{1}{c_{1}^{(k)}c_{2}^{(k)}}\qquad\Rightarrow\qquad{\Gamma_{2}^{\star}}^{(k)}=\frac{1}{{\left(c_{1}^{(k)}c_{2}^{(k)}\right)}^{2/3}}+1\\ \begin{aligned} \Rightarrow{\Gamma_{2}^{\star}}^{(k)}&={\left(\sqrt{\frac{6\left(1+\tilde{\rho}^{(k)}\right)\left(\zeta^{2}+2\Gamma_{3}\Gamma_{1}^{(k)}\frac{\beta^{2}}{\mu}\right)}{\Gamma_{3}\Gamma_{1}^{(k)}{\left(1-\tilde{\rho}^{(k)}\right)}^{2}}}\frac{\mu\left(1+\tilde{\rho}^{(k)}\right)}{4\Gamma_{3}\Gamma_{1}^{(k)}\left(1+\Gamma_{1}^{(k)}\right)\beta^{2}}\right)}^{2/3}+1\\ &=\frac{1+\tilde{\rho}^{(k)}}{2\Gamma_{3}\Gamma_{1}^{(k)}\beta}{\left(\frac{3\left(\zeta^{2}+2\Gamma_{3}\Gamma_{1}^{(k)}\frac{\beta^{2}}{\mu}\right)}{\beta}\right)}^{1/3}{\left(\frac{\mu}{\left(1-\tilde{\rho}^{(k)}\right)\left(1+\Gamma_{1}^{(k)}\right)}\right)}^{2/3}+1\end{aligned}\end{gathered}$ $$

We choose $\Gamma_{2}^{(k)}=\Gamma_{2}^{\star(k)}$ (see the explanation given in related step of Appendix [K](#A11)) to get

$$ $\displaystyle\min_{\Gamma_{2}^{(k)}}$ $\displaystyle\left\{\frac{\mu\left(1+\tilde{\rho}^{(k)}\right)}{4\Gamma_{3}\Gamma_{1}^{(k)}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}},\sqrt{\frac{\Gamma_{3}\Gamma_{1}^{(k)}\left(\Gamma_{2}^{(k)}-1\right){\left(1-\tilde{\rho}^{(k)}\right)}^{2}}{6\left(1+\tilde{\rho}^{(k)}\right)\left(\zeta^{2}+2\Gamma_{3}\Gamma_{1}^{(k)}\frac{\beta^{2}}{\mu}\right)}}\right\}$ $\displaystyle\geq\frac{\mu\left(1+\tilde{\rho}^{(k)}\right){\left(c_{1}^{(k)}c_{2}^{(k)}\right)}^{2/3}}{4\Gamma_{3}\Gamma_{1}^{(k)}\left(1+\Gamma_{1}^{(k)}\right)\beta^{2}}={\left(\frac{{(c_{1}^{(k)})}^{2}}{c_{2}^{(k)}}\right)}^{1/3}={\left(\frac{\mu}{6\left(\zeta^{2}+2\Gamma_{3}\Gamma_{1}^{(k)}\frac{\beta^{2}}{\mu}\right)\left(1+\Gamma_{1}^{(k)}\right)}\right)}^{1/3}{\left(\frac{1-\tilde{\rho}^{(k)}}{2\beta}\right)}^{2/3}.$ $$

Note that in the process of minimizing Eq. ([29](#A14.E29)) over $\Gamma_{2}^{(k)}$, two out of the three dependencies on $\Gamma_{3}$, and two out of four dependencies on $\Gamma_{1}^{(k)}$ were removed. Hence, we get

$$ $\alpha^{(k)}<\min\Bigg{\{}\frac{\Gamma_{1}^{(k)}}{\mu},\frac{1}{2\sqrt{3}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}},{\left(\frac{\mu}{6\left(\zeta^{2}+2\Gamma_{3}\Gamma_{1}^{(k)}\frac{\beta^{2}}{\mu}\right)\left(1+\Gamma_{1}^{(k)}\right)}\right)}^{1/3}{\left(\frac{1-\tilde{\rho}^{(k)}}{2\beta}\right)}^{2/3}\Bigg{\}}.$ (30) $$

Finally, we make a remark that we do not minimize over $\Gamma_{3}$ here, as we take it as a given deterministic value based on the choice of $d_{i}^{(k)}=1-\Gamma_{3}\alpha^{(k)}$.

Step 5: Obtaining $\rho(\mathbf{\Phi}^{(k)})$.
We established $\rho(\mathbf{\Phi}^{(k)})<1$ in the previous steps. The last step is to determine what $\rho(\mathbf{\Phi}^{(k)})$ is. We have

$$ $\displaystyle\rho{\left(\Phi^{(k)}\right)}$ $\displaystyle=\frac{-b+\sqrt{b^{2}-4ac}}{2a}=\frac{\phi_{11}^{(k)}+\phi_{22}^{(k)}+\sqrt{{\left(\phi_{11}^{(k)}+\phi_{22}^{(k)}\right)}^{2}-4\left(\phi_{11}^{(k)}\phi_{22}^{(k)}-\phi_{12}^{(k)}\phi_{21}^{(k)}\right)}}{2}$ $\displaystyle=\frac{\phi_{11}^{(k)}+\phi_{22}^{(k)}+\sqrt{{\left(\phi_{11}^{(k)}-\phi_{22}^{(k)}\right)}^{2}+4\phi_{12}^{(k)}\phi_{21}^{(k)}}}{2}$ $\displaystyle\begin{aligned} \,\,=\,\,&\frac{1-\frac{2\Gamma_{3}\Gamma_{1}^{(k)}}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}\alpha^{(k)}+\frac{1+\tilde{\rho}^{(k)}}{2}+3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\right)}{2}\\ &\begin{aligned} &+\frac{1}{2}\Bigg{[}\Bigg{(}1-\frac{2\Gamma_{3}\Gamma_{1}^{(k)}}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}\alpha^{(k)}-\frac{1+\tilde{\rho}^{(k)}}{2}-3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\right)\Bigg{)}^{2}\\ &+4\frac{\left(1+\Gamma_{1}^{(k)}\right)\beta^{2}}{m\mu}\alpha^{(k)}3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}m{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\Gamma_{3}\Gamma_{1}^{(k)}\frac{\beta^{2}}{\mu}\right)\Bigg{]}^{1/2}\end{aligned}\end{aligned}$ $\displaystyle\begin{aligned} \,\,=&\,\,\frac{3+\tilde{\rho}^{(k)}}{4}-\frac{\Gamma_{3}\Gamma_{1}^{(k)}}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}\alpha^{(k)}+\frac{3}{2}\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\right)\\ &\begin{aligned} &+\frac{1}{2}\Bigg{[}\Bigg{(}\frac{1-\tilde{\rho}^{(k)}}{2}-\frac{2\Gamma_{3}\Gamma_{1}^{(k)}}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\left(\Gamma_{2}^{(k)}-1\right)\beta^{2}\alpha^{(k)}-3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\right)\Bigg{)}^{2}\\ &+12\frac{\left(1+\Gamma_{1}^{(k)}\right)\beta^{2}}{\mu}\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}{\left(\alpha^{(k)}\right)}^{3}\left(\zeta^{2}+2\Gamma_{3}\Gamma_{1}^{(k)}\frac{\beta^{2}}{\mu}\right)\Bigg{]}^{1/2}\end{aligned}\end{aligned}$ $\displaystyle=\frac{3+\tilde{\rho}^{(k)}}{4}-A\alpha^{(k)}+B{\left(\alpha^{(k)}\right)}^{2}+\frac{1}{2}\sqrt{{\left(\frac{1-\tilde{\rho}^{(k)}}{2}-2\left(A\alpha^{(k)}+B{\left(\alpha^{(k)}\right)}^{2}\right)\right)}^{2}+C{\left(\alpha^{(k)}\right)}^{3}}$ $$

## Appendix O Proof of Lemma M.4

[(a)](#A13.I1.i1) Since $\alpha^{(k)}=\frac{\alpha^{(0)}}{\sqrt{1+\frac{k}{\gamma}}}$, we have

$$ $\sum_{q=r}^{k}{\alpha^{(q)}}=\sum_{q=r}^{k}{\frac{\alpha^{(0)}}{\sqrt{1+\frac{q}{\gamma}}}}\geq\int_{r}^{k}{\frac{\alpha^{(0)}\,dx}{\sqrt{1+\frac{x}{\gamma}}}}\geq 2\alpha^{(0)}\left(\sqrt{1+\frac{k}{\gamma}}-\sqrt{1+\frac{r}{\gamma}}\right).$ $$

[(b)](#A13.I1.i2)
Based on the equation $\rho(\mathbf{\Phi}^{(k)})=1-h(\alpha^{(k)})$ given in Proposition [M.1](#A13.Thmtheorem1), $h(\alpha^{(k)})$ was given as

$$ $h{(\alpha^{(k)})}=\frac{1-\tilde{\rho}^{(k)}}{4}+A\alpha^{(k)}-B{\left(\alpha^{(k)}\right)}^{2}-\frac{1}{2}\sqrt{{\left(\frac{1-\tilde{\rho}^{(k)}}{2}-2\left(A\alpha^{(k)}+B{\left(\alpha^{(k)}\right)}^{2}\right)\right)}^{2}+C{\left(\alpha^{(k)}\right)}^{3}}.$ $$

Further note that since we established $0\leq\rho{\left(\mathbf{\Phi}^{(k)}\right)}<1$ in Proposition [M.1](#A13.Thmtheorem1), it would mean $0<h{(\alpha^{(k)})}\leq 1$. Using triangle inequality, we have

$$ $\displaystyle h{(\alpha^{(k)})}$ $\displaystyle\geq\frac{1-\tilde{\rho}^{(k)}}{4}+A\alpha^{(k)}-B{\left(\alpha^{(k)}\right)}^{2}-\left(\frac{1-\tilde{\rho}^{(k)}}{4}-\left(A\alpha^{(k)}+B{\left(\alpha^{(k)}\right)}^{2}\right)\right)+\frac{\sqrt{C}}{2}{\left(\alpha^{(k)}\right)}^{3/2}$ $\displaystyle\geq 2A\alpha^{(k)}+\frac{\sqrt{C}}{2}{\left(\alpha^{(k)}\right)}^{3/2}\geq 2A\alpha^{(k)},$ $$

which holds because the step sizes are positive i.e., $\alpha^{(k)}>0$.

[(c)](#A13.I1.i3)

$$ $\displaystyle\sum_{r=1}^{k-1}{\frac{{(\alpha^{(r-1)})}^{2}}{\sum_{q=r}^{k}{h{(\alpha^{(q)})}}}}$ $\displaystyle\leq\sum_{r=1}^{k}{\frac{{(\alpha^{(r-1)})}^{2}}{\sum_{q=r}^{k}{2A\alpha^{(q)}}}}=\frac{1}{2A}\sum_{r=1}^{k}{\frac{{\left(\frac{\alpha^{(0)}}{\sqrt{1+\frac{r-1}{\gamma}}}\right)}^{2}}{\sum_{q=r}^{k}{\alpha^{(q)}}}}\leq\frac{1}{2A}\sum_{r=1}^{k}{\frac{\frac{{(\alpha^{(0)})}^{2}}{1+\frac{r-1}{\gamma}}}{2\alpha^{(0)}\left(\sqrt{1+\frac{k}{\gamma}}-\sqrt{1+\frac{r}{\gamma}}\right)}}$ $\displaystyle=\frac{\alpha^{(0)}}{4A}\sum_{r=1}^{k-1}{\frac{1}{\left(1+\frac{r-1}{\gamma}\right)\left(\sqrt{1+\frac{k}{\gamma}}-\sqrt{1+\frac{r}{\gamma}}\right)}}$ $\displaystyle\leq\frac{\alpha^{(0)}}{4A}\sum_{r=1}^{k-1}{\frac{1+\frac{1}{\gamma}}{\left(1+\frac{r}{\gamma}\right)\left(\sqrt{1+\frac{k}{\gamma}}-\sqrt{1+\frac{r}{\gamma}}\right)}}$ $\displaystyle\leq\frac{\alpha^{(0)}}{4A}\left[\frac{1}{\sqrt{1+\frac{k}{\gamma}}-\sqrt{1+\frac{1}{\gamma}}}+\int_{1}^{k-1}{\frac{\left(1+\frac{1}{\gamma}\right)\,dx}{\left(1+\frac{x}{\gamma}\right)\left(\sqrt{1+\frac{k}{\gamma}}-\sqrt{1+\frac{x}{\gamma}}\right)}}\right].$ $$

Focusing only on the integral and defining $u(x)=\sqrt{1+\frac{x}{\gamma}}$, we have

$$ $\displaystyle\int_{1}^{k-1}$ $\displaystyle{\frac{\left(1+\frac{1}{\gamma}\right)\,dx}{\left(1+\frac{x}{\gamma}\right)\left(\sqrt{1+\frac{k}{\gamma}}-\sqrt{1+\frac{x}{\gamma}}\right)}}=\int_{1}^{k-1}{\frac{2\gamma\left(1+\frac{1}{\gamma}\right)\,d{u(x)}}{u(x)\left(u(k)-u(x)\right)}}$ $\displaystyle=\int_{1}^{k-1}{\frac{2\left(\gamma+1\right)}{u(k)}\left(\frac{1}{u(x)}+\frac{1}{u(k)-u(x)}\right)\,d{u(x)}}=\frac{2\left(\gamma+1\right)}{u(k)}\left(\ln{\frac{u(k-1)}{u(1)}}+\ln{\frac{u(k)-u(1)}{u(k)-u(k-1)}}\right)$ $\displaystyle=\frac{2\left(\gamma+1\right)}{u(k)}\ln{\frac{u(k-1)u(k)}{u(k)-u(k-1)}}=\frac{2\left(\gamma+1\right)}{u(k)}\left(\ln{u(k)}+\ln{\frac{1}{\frac{u(k)}{u(k-1)}-1}}\right)$ $\displaystyle=\frac{2\left(\gamma+1\right)}{\sqrt{1+\frac{k}{\gamma}}}\left(\ln{\sqrt{1+\frac{k}{\gamma}}}+\ln{\frac{1}{\sqrt{1+\frac{1}{\gamma+k-1}}-1}}\right).$ $$

Putting everything back together concludes the proof.

## Appendix P Proof of Theorem M.5

First, using the fact that $\mathbf{\Phi}^{(k)}\|\cdot\|\leq\rho(\mathbf{\Phi^{(k)}})\|\cdot\|$ for each iteration $k\geq 0$, we can rewrite Eq. ([8](#S4.E8)) to get

$$ $\displaystyle\begin{bmatrix}\mathbb{E}_{\mathbf{\Xi}^{(k)}}{\left[{\left\|\mathbf{\bar{\theta}}^{(k+1)}-\mathbf{\theta}^{\star}\right\|}^{2}\right]}\\ \mathbb{E}_{\mathbf{\Xi}^{(k)}}{\left[{\left\|\mathbf{\Theta}^{(k+1)}-\mathbf{1}_{m}\mathbf{\bar{\theta}}^{(k+1)}\right\|}^{2}\right]}\end{bmatrix}\leq$ $\displaystyle\left(\prod_{q=0}^{k}{\rho{\left(\mathbf{\Phi}^{(q)}\right)}}\right)\begin{bmatrix}{\left\|\mathbf{\bar{\theta}}^{(0)}-\mathbf{\theta}^{\star}\right\|}^{2}\\ {\left\|\mathbf{\Theta}^{(0)}-\mathbf{1}_{m}\mathbf{\bar{\theta}}^{(0)}\right\|}^{2}\end{bmatrix}$ (31) $\displaystyle\,\,\,+\sum_{r=1}^{k}{\left(\prod_{q=r}^{k}{\rho{\left(\mathbf{\Phi}^{(q)}\right)}}\right){\left(\alpha^{(r-1)}\right)}^{2}\begin{bmatrix}\frac{2}{\mu\alpha^{(0)}}\left(1+\mu\alpha^{(0)}\right)\delta^{2}+\frac{\sigma^{2}}{m}\\ m\left(3\frac{1+\tilde{\rho}}{1-\tilde{\rho}}\delta^{2}+\sigma^{2}\right)\end{bmatrix}}+\mathbf{\Psi}^{(k)},$ $$

where the $\mathbf{\Psi}^{(k)}$ matrix was written using Eq. ([24](#A14.E24)).

Next, in order to obtain Eq. ([22](#A13.E22)) when $k\to\infty$, we need to simplify each of the three terms in Eq. ([31](#A16.E31)). The easiest one to show is the last term, i.e., $\mathbf{\Psi}^{(k)}$. Based on Eq. ([24](#A14.E24)), both of its entries $\psi_{1}^{(k)}$ and $\psi_{2}^{(k)}$ have a factor ${(\alpha^{(k)})}^{2}$ multiplied by a value that can be upper-bounded by a constant. Thus, we have

$$ $\mathbf{\Psi}^{(k)}\leq\frac{{\left(\alpha^{(0)}\right)}^{2}}{1+\frac{k}{\gamma}}\begin{bmatrix}\frac{2\Gamma_{3}\left(1+\Gamma_{1}\right)}{\mu}\delta^{2}+\frac{\sigma^{2}}{m}\\ m\left(3\frac{1+\tilde{\rho}}{1-\tilde{\rho}}\delta^{2}+\sigma^{2}\right)\end{bmatrix}.$ $$

Regarding the first and the second term, i.e., $\prod_{q=0}^{k}{\rho{\left(\mathbf{\Phi}^{(q)}\right)}}$ and $\sum_{r=1}^{k}{\left(\prod_{q=r}^{k}{\rho{\left(\mathbf{\Phi}^{(q)}\right)}}\right){\left(\alpha^{(r-1)}\right)}^{2}}$, respectively, we have

$$ $\begin{gathered}\prod_{q=0}^{k}{\rho{\left(\mathbf{\Phi}^{(q)}\right)}}=\prod_{q=0}^{k}{\left(1-h{(\alpha^{(q)})}\right)}\leq\frac{1}{\sum_{q=0}^{k}{h{(\alpha^{(q)})}}},\\ \sum_{r=1}^{k}{\left(\prod_{q=r}^{k}{\rho{\left(\mathbf{\Phi}^{(q)}\right)}}\right){\left(\alpha^{(r-1)}\right)}^{2}}=\sum_{r=1}^{k}{\left(\prod_{q=r}^{k}{\left(1-h{(\alpha^{(q)})}\right)}\right){\left(\alpha^{(r-1)}\right)}^{2}}\leq\sum_{r=1}^{k}{\frac{{\left(\alpha^{(r-1)}\right)}^{2}}{\sum_{q=r}^{k}{h{(\alpha^{(q)})}}}},\end{gathered}$ $$

in both of which Lemma [M.3](#A13.Thmtheorem3) was used, since $0\leq h(\alpha^{(k)})<1$.
Next, we employ Lemma [M.4](#A13.Thmtheorem4) on the above expressions. The proof easily follows. Note that $\ln{\frac{1}{\sqrt{1+\frac{1}{\gamma+k-1}}-1}}\leq\mathcal{O}{(\ln{k})}$.

## Appendix Q Convergence Analysis for Non-Convex Models under the PL Condition

In this appendix, we make the convergence analysis of our developed framework when non-convex ML models satisfying the PL condition are employed. Our approach will be quite similar to Sec. [4](#S4), with the key difference that we will use Assumption [4.5](#S4.Thmtheorem5) instead of Assumption [4.1](#S4.Thmtheorem1)-[(b)](#S4.I1.i2).

We will still characterize the expected consensus error as $\mathbb{E}_{\mathbf{\Xi}^{(k)}}{[{\|\mathbf{\Theta}^{(k+1)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k+1)}\|}^{2}]}$, but contrary to what was done in Sec. [4](#S4), the distance of the average model from the optimal solution will be captured via $\mathbb{E}_{\mathbf{\Xi}^{(k)}}[F(\bar{\mathbf{\theta}}^{(k+1)})-F^{\star}]$. As an alternative to Lemma [4.7](#S4.Thmtheorem7), we first provide an upper bound on the expected error in the average model at each iteration for the non-convex case, i.e., $\mathbb{E}_{\mathbf{\Xi}^{(k)}}[F(\bar{\mathbf{\theta}}^{(k+1)})-F^{\star}]$, in Lemma [Q.2](#A17.Thmtheorem2). Then, as an alternative to Lemma [4.8](#S4.Thmtheorem8), we also calculate an upper bound on the consensus error for non-convex models, i.e., $\mathbb{E}_{\mathbf{\Xi}^{(k)}}{[{\|\mathbf{\Theta}^{(k+1)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k+1)}\|}^{2}]}$, in Corollary [Q.3](#A17.Thmtheorem3).

We first need a preliminary Lemma which will be useful in the proof of Lemma [Q.2](#A17.Thmtheorem2).

###### Lemma Q.1 .

(See Appendix [R](#A18) for the proof.)
Let Assumptions [4.1](#S4.Thmtheorem1)-[(a)](#S4.I1.i1), [4.1](#S4.Thmtheorem1)-[(c)](#S4.I2.i3) and [4.5](#S4.Thmtheorem5) hold. The following upper bounds related to the gradient of the global loss function can be obtained in terms of the optimality error $\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}]}$ and the consensus error $\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[{\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\|}^{2}]}$.

- (a)
$\mathbb{E}_{\mathbf{\Xi}^{(k)}}{[{\|\nabla{F}(\bar{\mathbf{\theta}}^{(k)})-\overline{\nabla v}^{(k)}\|}^{2}]}\leq\frac{4\beta^{2}}{\mu}(1-d_{min}^{(k)})\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}]}+\frac{\beta^{2}d_{max}^{(k)}}{m}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[{\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\|}^{2}]}\\
+2(1-d_{min}^{(k)})\delta^{2}$.
- (b)
$-\mathbb{E}_{\mathbf{\Xi}^{(k)}}{[\langle\nabla{F}(\bar{\mathbf{\theta}}^{(k)}),\overline{\nabla v}^{(k)}\rangle]}\leq-\mu(1-\frac{2\beta^{2}}{\mu^{2}}(1-d_{min}^{(k)}))\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}]}+\frac{\beta^{2}d_{max}^{(k)}}{2m}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[{\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\|}^{2}]}\\
+(1-d_{min}^{(k)})\delta^{2}$.
- (c)
$\frac{1}{2}\mathbb{E}_{\mathbf{\Xi}^{(k)}}{[{\|\overline{\nabla v}^{(k)}\|}^{2}]}\leq\frac{2\beta^{2}}{\mu}(3-2d_{min}^{(k)})\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}]}+\frac{\beta^{2}d_{max}^{(k)}}{m}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[{\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\|}^{2}]}+2(1-d_{min}^{(k)})\delta^{2}$.

Now can continue with the key lemma and corollary.

###### Lemma Q.2 ( Average error for non-convex models satisfying the PL condition ) .

(See Appendix [S](#A19) for the proof.)
Let Assumptions [4.1](#S4.Thmtheorem1)-[(a)](#S4.I1.i1), [4.1](#S4.Thmtheorem1)-[(c)](#S4.I2.i3), [4.2](#S4.Thmtheorem2) and [4.5](#S4.Thmtheorem5) hold. For each iteration $k\geq 0$, we have the following bound on the expected average model error

$\mathbb{E}_{\mathbf{\Xi}^{(k)}}[F(\bar{\mathbf{\theta}}^{(k+1)})-F^{\star}]\leq\phi_{11}^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}[F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}]+\phi_{12}^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[{\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\|}^{2}]}+\psi_{1}^{(k)}$,

where $\phi_{11}^{(k)}=1+\frac{2\beta^{3}}{\mu}(3-2d_{min}^{(k)}){(\alpha^{(k)})}^{2}-\mu\alpha^{(k)}(1-\frac{2\beta^{2}}{\mu^{2}}(1-d_{min}^{(k)}))$, $\phi_{12}^{(k)}=\frac{\beta^{2}d_{max}^{(k)}}{2m}\alpha^{(k)}(1+2\beta\alpha^{(k)})$, and
$\psi_{1}^{(k)}=\frac{\beta}{2}{(\alpha^{(k)})}^{2}[4(1-d_{min}^{(k)})\delta^{2}+\frac{d_{max}\sigma^{2}}{m}]$.

Similar to our discussion around Lemma [4.7](#S4.Thmtheorem7), note again how the coefficients simplify when $d_{\min}^{(k)}=1$, which is essentially equivalent to the conventional DFL setup where clients perform SGDs at every iteration, i.e., $v_{i}^{(k)}=1$ for all $i\in\mathcal{M}$.

We next bound the consensus error at each iteration, i.e., $\mathbb{E}_{\mathbf{\Xi}^{(k)}}{[{\|\mathbf{\Theta}^{(k+1)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k+1)}\|}^{2}]}$, which measures the deviation of ML model parameters of clients
from the average non-convex ML model.

###### Corollary Q.3 ( Consensus error for non-convex models satisfying the PL condition ) .

(Corollary to Lemma [4.8](#S4.Thmtheorem8))
Let Assumptions [4.1](#S4.Thmtheorem1)-[(a)](#S4.I1.i1), [4.1](#S4.Thmtheorem1)-[(c)](#S4.I2.i3), [4.2](#S4.Thmtheorem2)-[4.5](#S4.Thmtheorem5) hold. For each iteration $k\geq 0$, we have the following bound on the expected consensus error

$\mathbb{E}_{\mathbf{\Xi}^{(k)}}{[{\|\mathbf{\Theta}^{(k+1)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k+1)}\|}^{2}]}\leq\phi_{21}^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}[F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}]+\phi_{22}^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[{\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\|}^{2}]}+\psi_{2}^{(k)}$,

where $\phi_{21}^{(k)}=\frac{6}{\mu}\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}md_{max}^{(k)}{(\alpha^{(k)})}^{2}(\zeta^{2}+2\beta^{2}(1-d_{min}^{(k)}))$, $\phi_{22}^{(k)}=\frac{1+\tilde{\rho}^{(k)}}{2}+3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}d_{\max}^{(k)}{(\alpha^{(k)})}^{2}(\zeta^{2}+2\beta^{2})$, and $\psi_{2}^{(k)}=m{(\alpha^{(k)})}^{2}d_{\max}^{(k)}(3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}\delta^{2}+\sigma^{2})$.

###### Proof.

Lemma [4.8](#S4.Thmtheorem8) states that $\mathbb{E}_{\mathbf{\Xi}^{(k)}}{[{\|\mathbf{\Theta}^{(k+1)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k+1)}\|}^{2}]}\leq\phi_{21}^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[{\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\|}^{2}]}+\phi_{22}^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{[{\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\|}^{2}]}+\psi_{2}^{(k)}$. Now, using the PL condition (Assumption [4.5](#S4.Thmtheorem5)), we know that ${\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\|}^{2}\leq\frac{2}{\mu}(F(\bar{\mathbf{\theta}}^{(k)})-F^{\star})$. Hence, we get $\phi_{21}^{(k)}\leftarrow\frac{2}{\mu}\phi_{21}^{(k)}$.
∎

Corollary [Q.3](#A17.Thmtheorem3) is almost the same as Lemma [4.8](#S4.Thmtheorem8), with the only difference being in $\phi_{21}^{(k)}$. Note again that $\phi_{21}^{(k)}=0$ in the conventional DFL setup, where (a) $\zeta=0$ and (b) $d_{min}^{(k)}=1$, resulting $d_{i}^{(k)}=1$ for all $i\in\mathcal{M}$.

Let us denote the error vector at iteration $k$ with $\nu_{nc}^{(k)}$, defined as

$$ $\nu_{nc}^{(k)}=\begin{bmatrix}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[F{\left(\mathbf{\bar{\theta}}^{(k)}\right)}-F^{\star}\right]}\\ \mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\mathbf{\bar{\theta}}^{(k)}\right\|}^{2}\right]}\end{bmatrix}.$ (32) $$

With this definition, putting the results of Lemmas [4.7](#S4.Thmtheorem7) and [4.8](#S4.Thmtheorem8) together form the following linear system of inequalities:

Putting the results of Lemma [Q.2](#A17.Thmtheorem2) and Corollary [Q.3](#A17.Thmtheorem3) together form the following linear system of inequalities:

$$ $\nu_{nc}^{(k+1)}\leq\mathbf{\Phi}^{(k)}\nu_{nc}^{(k)}+\mathbf{\Psi}^{(k)},$ (33) $$

with $\mathbf{\Phi}^{(k)}={[\phi_{ij}^{(k)}]}_{1\leq i,j\leq 2}$ and $\mathbf{\Psi}^{(k)}=[\psi_{1}^{(k)}\quad\psi_{2}^{(k)}]^{T}$. Recursively expanding the inequalities in Eq. ([33](#A17.E33)) gives us an explicit relationship between the expected model error and consensus error at each iteration and their
initial values:

$$ $\nu_{nc}^{(k+1)}\leq\mathbf{\Phi}^{(k:0)}\nu_{nc}^{(k)}+\sum_{r=1}^{k}{\mathbf{\Phi}^{(k:r)}\mathbf{\Psi}^{(r-1)}}+\mathbf{\Psi}^{(k)},$ (34) $$

where we have defined $\mathbf{\Phi}^{(k:s)}=\mathbf{\Phi}^{(k)}\mathbf{\Phi}^{(k-1)}\cdots\mathbf{\Phi}^{(s)}$ for $k>s$, and $\mathbf{\Phi}^{(k:k)}=\mathbf{\Phi}^{(k)}$.

In order for us formalize the convergence bound of DSpodFL, we have to show that the spectral radius of matrix $\mathbf{\Phi}^{(k)}$ given in Eq. ([33](#A17.E33)) is less than one, i.e., $\rho(\mathbf{\Phi}^{(k)})<1$. This part was outlined in Proposition [Q.4](#A17.Thmtheorem4) in the main text.

###### Proposition Q.4 .

(See Appendix [T](#A20) for the proof.)
Let Assumptions [4.1](#S4.Thmtheorem1)-[(a)](#S4.I1.i1), [4.1](#S4.Thmtheorem1)-[(c)](#S4.I2.i3), [4.2](#S4.Thmtheorem2)-[4.5](#S4.Thmtheorem5) hold. If the step size satisfies the following condition for all $k\geq 0$

$$ $\displaystyle\alpha^{(k)}<\min\Bigg{\{}\frac{1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)}{10\left(3-2d_{min}^{(k)}\right)}\frac{\mu^{2}}{\beta^{3}},$ $\displaystyle\frac{5\left(1+\tilde{\rho}^{(k)}\right)}{8\mu\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)},$ $\displaystyle\frac{1}{6\sqrt{2d_{max}^{(k)}}}\frac{\mu}{\beta^{2}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\sqrt{\frac{1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)}{1+\frac{2\beta^{2}}{\zeta^{2}}\left(1-d_{min}^{(k)}\right)}}\Bigg{\}},$ $$

then we have $\rho{(\mathbf{\Phi}^{(k)})}<1$ for all $k\geq 0$, in which $\rho{(\cdot)}$ denotes the spectral radius of a given matrix, and $\mathbf{\Phi}^{(k)}$ is the linear system of inequalities of governing the dynamics of optimality and consensus errors. $\rho{(\mathbf{\Phi}^{(k)})}$ follows as

$\rho{(\mathbf{\Phi}^{(k)})}=\frac{3+\tilde{\rho}^{(k)}}{4}-A\alpha^{(k)}+B{(\alpha^{(k)})}^{2}+\frac{1}{2}\sqrt{{(\frac{1-\tilde{\rho}^{(k)}}{2}-2(A\alpha^{(k)}+B{(\alpha^{(k)})}^{2}))}^{2}+C{(\alpha^{(k)})}^{3}},$

where $A=\frac{2\mu}{5}(1-\frac{2\beta^{2}}{\mu^{2}}(1-d_{min}^{(k)}))$, $B=\frac{3}{2}\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}(\zeta^{2}+2\beta^{2})$ and $C=\frac{72\beta^{2}}{5\mu}\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}{(d_{max}^{(k)})}^{2}(\zeta^{2}+2\beta^{2}(1-d_{min}^{(k)}))$.

Proposition [Q.4](#A17.Thmtheorem4) enables us to guarantee convergence of DSpodFL when non-convex models are used. The argument follows along the lines of the things we discussed in Sec. [4.4](#S4.SS4). Proposition [Q.4](#A17.Thmtheorem4) implies that $\lim_{k\to\infty}{\mathbf{\Phi}^{(k:0)}}=0$ in Eq. ([34](#A17.E34)). However, this is only the asymptotic behavior of $\mathbf{\Phi}^{(k:0)}$, and the exact convergence rate will depend on the choice of the step size $\alpha^{(k)}$. Furthermore, since the first expression in Eq. ([34](#A17.E34)) asymptotically approaches zero, Proposition [Q.4](#A17.Thmtheorem4) also implies that the non-negative optimality gap is determined by the terms $\sum_{r=1}^{k}{\mathbf{\Phi}^{(k:r)}\mathbf{\Psi}^{(r-1)}}+\mathbf{\Psi}^{(k)}$, and it can be either zero or a positive value depending on the choice of $\alpha^{(k)}$.

Proposition [Q.4](#A17.Thmtheorem4) outlines the necessary constraint on the step size $\alpha^{(k)}$ at each iteration $k\geq 0$. We next provide a corollary to Proposition [Q.4](#A17.Thmtheorem4), in which we show that under certain conditions, the above-mentioned constraint needs to be satisfied only on the initial value of the step size, i.e, $\alpha^{(0)}$.

###### Corollary Q.5 .

(Corollary to Proposition [Q.4](#A17.Thmtheorem4))
If the step size $\alpha^{(k)}$ is non-increasing and the SGD probabilities $d_{i}^{(k)}$ are constant, i.e., $\alpha^{(k+1)}\leq\alpha^{(k)}$, $d_{i}^{(k)}=d_{i}$, for all $k\geq 0$, and we have $\tilde{\rho}^{(k)}\leq\tilde{\rho}=\sup_{k=0,1,...}{\tilde{\rho}^{(k)}}$ for the spectral radius, then the constraints in Proposition [Q.4](#A17.Thmtheorem4) simplify to

$$ $\displaystyle\alpha^{(0)}<\min\Bigg{\{}\frac{1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}\right)}{10\left(3-2d_{min}\right)}\frac{\mu^{2}}{\beta^{3}},$ $\displaystyle\frac{5}{8\mu\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}\right)\right)},\frac{1}{6\sqrt{2d_{max}}}\frac{\zeta}{\beta^{2}}\frac{1-\tilde{\rho}}{\sqrt{1+\tilde{\rho}}}\sqrt{\frac{\mu^{2}-2\beta^{2}\left(1-d_{min}\right)}{\zeta^{2}+2\beta^{2}\left(1-d_{min}\right)}}\Bigg{\}}.$ $$

###### Lemma Q.1 .

###### Lemma Q.2 ( Average error for non-convex models satisfying the PL condition ) .

###### Corollary Q.3 ( Consensus error for non-convex models satisfying the PL condition ) .

###### Proof.

###### Proposition Q.4 .

###### Corollary Q.5 .

## Appendix R Proof of Lemma Q.1

[(a)](#A17.I1.i1)
For this deviation term, we have

$$ $\displaystyle{\left\|\nabla{F}(\bar{\mathbf{\theta}}^{(k)})-\overline{\nabla v}^{(k)}\right\|}^{2}$ $\displaystyle={\left\|\frac{1}{m}\sum_{i=1}^{m}{\left(\nabla{F}_{i}(\bar{\mathbf{\theta}}^{(k)})-\nabla{F}_{i}(\mathbf{\theta}_{i}^{(k)})v_{i}^{(k)}\right)}\right\|}^{2}\leq\frac{1}{m}\sum_{i=1}^{m}{{\left\|\nabla{F}_{i}(\bar{\mathbf{\theta}}^{(k)})-\nabla{F}_{i}(\mathbf{\theta}_{i}^{(k)})v_{i}^{(k)}\right\|}^{2}}$ $\displaystyle=\frac{1}{m}\sum_{\begin{subarray}{c}i=1\\ v_{i}^{(k)}=1\end{subarray}}^{m}{{\left\|\nabla{F}_{i}(\bar{\mathbf{\theta}}^{(k)})-\nabla{F}_{i}(\mathbf{\theta}_{i}^{(k)})\right\|}^{2}}+\frac{1}{m}\sum_{\begin{subarray}{c}i=1\\ v_{i}^{(k)}=0\end{subarray}}^{m}{{\left\|\nabla{F}_{i}(\bar{\mathbf{\theta}}^{(k)})\right\|}^{2}}$ $\displaystyle\leq\frac{1}{m}\sum_{\begin{subarray}{c}i=1\\ v_{i}^{(k)}=1\end{subarray}}^{m}{\beta_{i}^{2}{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}_{i}^{(k)}\right\|}^{2}}+\frac{2}{m}\sum_{\begin{subarray}{c}i=1\\ v_{i}^{(k)}=0\end{subarray}}^{m}{\left(\beta_{i}^{2}{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}+\delta_{i}^{2}\right)}$ $\displaystyle=\frac{1}{m}\sum_{i=1}^{m}{\beta_{i}^{2}{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}_{i}^{(k)}\right\|}^{2}v_{i}^{(k)}}+\frac{2}{m}\sum_{i=1}^{m}{\left(\frac{2\beta_{i}^{2}}{\mu}\left(F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}\right)+\delta_{i}^{2}\right)\left(1-v_{i}^{(k)}\right)},$ $$

where in the last two lines, (i) Smoothness (Assumption [4.1](#S4.Thmtheorem1)-[(a)](#S4.I1.i1)) and Lemma [D.1](#A4.Thmtheorem1)-[(b)](#A4.Ex3) and (ii) PL condition (Assumption [4.5](#S4.Thmtheorem5)) was used, respectively. Taking the expected value of the above inequality concludes the proof.

[(b)](#A17.I1.i2)
Second, for this inner product term, we have

$$ $\displaystyle-\left\langle\nabla{F}(\bar{\mathbf{\theta}}^{(k)}),\overline{\nabla v}^{(k)}\right\rangle$ $\displaystyle=-\left\langle\nabla{F}(\bar{\mathbf{\theta}}^{(k)}),\overline{\nabla v}^{(k)}-\nabla{F}(\bar{\mathbf{\theta}}^{(k)})+\nabla{F}(\bar{\mathbf{\theta}}^{(k)})\right\rangle$ $\displaystyle=-{\left\|\nabla{F}(\bar{\mathbf{\theta}}^{(k)})\right\|}^{2}+\left\langle\nabla{F}(\bar{\mathbf{\theta}}^{(k)}),\nabla{F}(\bar{\mathbf{\theta}}^{(k)})-\overline{\nabla v}^{(k)}\right\rangle$ $\displaystyle\leq\frac{-1}{2}{\left\|\nabla{F}(\bar{\mathbf{\theta}}^{(k)})\right\|}^{2}+\frac{1}{2}{\left\|\nabla{F}(\bar{\mathbf{\theta}}^{(k)})-\overline{\nabla v}^{(k)}\right\|}^{2}.$ $$

Now, taking the expected value of this inequality and using part [(a)](#A17.I1.i1) of this lemma alongside the PL condition (Assumption [4.5](#S4.Thmtheorem5)), we get

$$ $\displaystyle\begin{aligned} -\mathbb{E}_{\mathbf{\Xi}^{(k)}}{\left[\left\langle\nabla{F}(\bar{\mathbf{\theta}}^{(k)}),\overline{\nabla v}^{(k)}\right\rangle\right]}\leq-\mu&\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}\right]}+\frac{\beta^{2}d_{max}^{(k)}}{2m}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}\\ &+\frac{2\beta^{2}}{\mu}\left(1-d_{min}^{(k)}\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}\right]}+\left(1-d_{min}^{(k)}\right)\delta^{2}\end{aligned}$ $\displaystyle\leq-\mu\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}\right]}+\frac{\beta^{2}d_{max}^{(k)}}{2m}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}+\left(1-d_{min}^{(k)}\right)\delta^{2}.$ $$

[(c)](#A17.I1.i3)
Finally, for the norm term, we have

$$ $\frac{1}{2}{\left\|\overline{\nabla v}^{(k)}\right\|}^{2}=\frac{1}{2}{\left\|\overline{\nabla v}^{(k)}-\nabla{F}(\bar{\mathbf{\theta}}^{(k)})+\nabla{F}(\bar{\mathbf{\theta}}^{(k)})\right\|}^{2}\leq{\left\|\nabla{F}(\bar{\mathbf{\theta}}^{(k)})\right\|}^{2}+{\left\|\nabla{F}(\bar{\mathbf{\theta}}^{(k)})-\overline{\nabla v}^{(k)}\right\|}^{2}.$ $$

Taking the expected value of this inequality and utilizing part [(a)](#A17.I1.i1) of this lemma alongside the PL condition (Assumption [4.5](#S4.Thmtheorem5))

$$ $\displaystyle\begin{aligned} \frac{1}{2}\mathbb{E}_{\mathbf{\Xi}^{(k)}}{\left[{\left\|\overline{\nabla v}^{(k)}\right\|}^{2}\right]}\leq\frac{2\beta^{2}}{\mu}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}\right]}&+\frac{\beta^{2}d_{max}^{(k)}}{m}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}\\ &+\frac{4\beta^{2}}{\mu}\left(1-d_{min}^{(k)}\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}\right]}+2\left(1-d_{min}^{(k)}\right)\delta^{2}\end{aligned}$ $\displaystyle\leq\frac{2\beta^{2}}{\mu}\left(3-2d_{min}^{(k)}\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}\right]}+\frac{\beta^{2}d_{max}^{(k)}}{m}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}+2\left(1-d_{min}^{(k)}\right)\delta^{2}.$ $$

## Appendix S Proof of Lemma Q.2

Using Lemma [D.1](#A4.Thmtheorem1)-[(b)](#A4.Ex3) on $\bar{\mathbf{\theta}}^{(k)}$, the average model parameters at iteration $k$, and then employing Assumption [4.5](#S4.Thmtheorem5), we get

$$ ${\left\|\nabla{F}(\bar{\mathbf{\theta}}^{(k)})\right\|}^{2}\leq\beta^{2}{\left\|\bar{\mathbf{\theta}}^{(k)}-\mathbf{\theta}^{\star}\right\|}^{2}\leq\frac{2\beta^{2}}{\mu}\left(F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}\right).$ (35) $$

Now, we can write

$$ $\displaystyle F(\bar{\mathbf{\theta}}^{(k+1)})-F^{\star}$ $\displaystyle\leq F(\bar{\mathbf{\theta}}^{(k)})+\left\langle\nabla{F}(\bar{\mathbf{\theta}}^{(k)}),\bar{\mathbf{\theta}}^{(k+1)}-\bar{\mathbf{\theta}}^{(k)}\right\rangle+\frac{\beta}{2}{\left\|\bar{\mathbf{\theta}}^{(k)}-\bar{\mathbf{\theta}}^{(k+1)}\right\|}^{2}-F^{\star}$ $\displaystyle=F(\bar{\mathbf{\theta}}^{(k)})+\left\langle\nabla{F}(\bar{\mathbf{\theta}}^{(k)}),-\alpha^{(k)}\overline{gv}^{(k)}\right\rangle+\frac{\beta}{2}{\left\|\alpha^{(k)}\overline{gv}^{(k)}\right\|}^{2}-F^{\star}$ $\displaystyle\begin{aligned} \,\,=F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}-\alpha^{(k)}\left\langle\nabla{F}(\bar{\mathbf{\theta}}^{(k)}),\overline{\nabla v}^{(k)}\right\rangle&-\alpha^{(k)}\left\langle\nabla{F}(\bar{\mathbf{\theta}}^{(k)}),\overline{\epsilon v}^{(k)}\right\rangle+\frac{\beta}{2}{\left(\alpha^{(k)}\right)}^{2}{\left\|\overline{\nabla v}^{(k)}\right\|}^{2}\\ &+\frac{\beta}{2}{\left(\alpha^{(k)}\right)}^{2}{\left\|\overline{\epsilon v}^{(k)}\right\|}^{2}+\beta{\left(\alpha^{(k)}\right)}^{2}\left\langle\overline{\nabla v}^{(k)},\overline{\epsilon v}^{(k)}\right\rangle,\end{aligned}$ $$

in which the relationship in each of the three lines follow from (i) Smoothness (Assumption [4.1](#S4.Thmtheorem1)-[(a)](#S4.I1.i1)), (ii) Eq. ([5](#S3.E5)), (iii) $\mathbf{g}_{i}^{(k)}=\mathbf{\nabla}_{i}^{(k)}+\mathbf{\epsilon}_{i}^{(k)}$ for all $i\in\mathcal{M}$. Next, we take the expected value of the above inequality and use Assumption [4.2](#S4.Thmtheorem2), and Lemmas [D.2](#A4.Thmtheorem2) and [Q.1](#A17.Thmtheorem1) to get

$$ $\displaystyle\begin{aligned} \mathbb{E}_{\mathbf{\Xi}^{(k)}}&{\left[F(\bar{\mathbf{\theta}}^{(k+1)})-F^{\star}\right]}\leq\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}\right]}-\mu\alpha^{(k)}\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}\right]}\\ &+\frac{\beta^{2}d_{max}^{(k)}}{2m}\alpha^{(k)}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}+\alpha^{(k)}\left(1-d_{min}^{(k)}\right)\delta^{2}\\ &+\frac{2\beta^{3}}{\mu}\left(3-2d_{min}^{(k)}\right){\left(\alpha^{(k)}\right)}^{2}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}\right]}+\frac{\beta^{3}d_{max}^{(k)}}{m}{\left(\alpha^{(k)}\right)}^{2}\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}\\ &+2\beta\left(1-d_{min}^{(k)}\right)\delta^{2}{\left(\alpha^{(k)}\right)}^{2}+\frac{\beta}{2}{\left(\alpha^{(k)}\right)}^{2}d_{max}^{(k)}\frac{\sigma^{2}}{m}\end{aligned}$ $\displaystyle\begin{aligned} \leq&\left[1+\frac{2\beta^{3}}{\mu}\left(3-2d_{min}^{(k)}\right){\left(\alpha^{(k)}\right)}^{2}-\mu\alpha^{(k)}\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)\right]\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[F(\bar{\mathbf{\theta}}^{(k)})-F^{\star}\right]}\\ &+\frac{\beta^{2}d_{max}^{(k)}}{2m}\alpha^{(k)}\left(1+2\beta\alpha^{(k)}\right)\mathbb{E}_{\mathbf{\Xi}^{(k-1)}}{\left[{\left\|\mathbf{\Theta}^{(k)}-\mathbf{1}_{m}\bar{\mathbf{\theta}}^{(k)}\right\|}^{2}\right]}+\frac{\beta}{2}{\left(\alpha^{(k)}\right)}^{2}\left[4\left(1-d_{min}^{(k)}\right)\delta^{2}+\frac{d_{max}\sigma^{2}}{m}\right].\end{aligned}$ $$

## Appendix T Proof of Proposition Q.4

We will do an analysis similar to the proof of Propositions [4.10](#S4.Thmtheorem10) and [M.1](#A13.Thmtheorem1), which were given in Appendices [K](#A11) and [N](#A14), respectively.

Step 1: Setting up the proof.
We skip repeating the explanations for this step, as they are exactly the same as step 1 in Appendix [K](#A11).

Step 2: Simplifying the conditions.
Recall that we have to ensure (i) $0<\phi_{11}^{(k)}\leq 1$ and (ii) $0<\phi_{22}^{(k)}\leq 1$. For $\phi_{11}^{(k)}$ as defined in Lemma [Q.2](#A17.Thmtheorem2), we have

$$ $\phi_{11}^{(k)}\leq 1\qquad\Rightarrow\qquad\alpha^{(k)}\leq\frac{\mu^{2}\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)}{2\beta^{3}\left(3-2d_{min}^{(k)}\right)}\qquad\Rightarrow\qquad d_{min}^{(k)}>1-\frac{\mu^{2}}{2\beta^{2}}.$ (36) $$

We can see that we got a requirement for $d_{min}^{(k)}$ here, and it should be lower bounded. Therefore, contrary to when strongly convex models were being used that $d_{i}^{(k)}$ could have had any value for all $i\in\mathcal{M}$ and $k\geq 0$, when using a non-convex model this is no longer the case, and $d_{i}^{(k)}$ have to be larger than a threshold $1-\frac{\mu^{2}}{2\beta^{2}}$. To put this into better context, note that $1-\frac{\mu^{2}}{2\beta^{2}}>\frac{1}{2}$, and thus at the best possible scenario we can allow $d_{i}^{(k)}>\frac{1}{2}$.

We then put the following constraint on $\alpha^{(k)}$ to get a more compact form for $\phi_{11}^{(k)}$, defined in Lemma [Q.2](#A17.Thmtheorem2). We have

$$ $\text{Constraint 1: }\alpha^{(k)}\leq\Gamma_{1}^{(k)}\frac{\mu^{2}\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)}{2\beta^{3}\left(3-2d_{min}^{(k)}\right)},\qquad 0<\Gamma_{1}^{(k)}\leq 1,$ $$

Note that although the above constraint has to be satisfied for $\alpha^{(k)}$, we also obtain an upper bound for the condition for theoretical analysis purposes. We have

$$ $\alpha^{(k)}\leq\Gamma_{1}^{(k)}\frac{\mu^{2}}{2\beta^{3}}\leq\frac{\Gamma_{1}^{(k)}}{2\beta}.$ $$

Hence, we can update $\phi_{11}^{(k)}$ and $\phi_{12}^{(k)}$ as defined in Lemma [Q.2](#A17.Thmtheorem2) as the follows

$$ $\phi_{11}^{(k)}\leq 1-\left(1-\Gamma_{1}^{(k)}\right)\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)\mu\alpha^{(k)},\qquad\phi_{12}^{(k)}\leq\frac{\beta^{2}d_{max}^{(k)}}{2m}\left(1+\Gamma_{1}^{(k)}\right)\alpha^{(k)}.$ (37) $$

Note that other entries of matrices $\mathbf{\Phi}^{(k)}$ and $\mathbf{\Psi}^{(k)}$ remain the same as initially given in Lemma [Q.2](#A17.Thmtheorem2) and Corollary [Q.3](#A17.Thmtheorem3). Moreover, since matrix $\mathbf{\Phi}^{(k)}$ and vector $\mathbf{\Psi}^{(k)}$ in Eq. ([33](#A17.E33)) were used as upper bounds, therefore we can always replace their values with new upper bounds for them. Consequently, with this new value for $\phi_{11}^{(k)}$, we continue as

$$ $\phi_{11}^{(k)}>0\qquad\Rightarrow\qquad\alpha^{(k)}<\frac{1}{\mu\left(1-\Gamma_{1}^{(k)}\right)\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)}.$ $$

Finally, we check the next condition $0<\phi_{22}^{(k)}\leq 1$. Noting that we have $\frac{3+\tilde{\rho}^{(k)}}{4}<1$, we can enforce $\phi_{22}^{(k)}\leq 1$ by setting $\phi_{22}^{(k)}\leq\frac{3+\tilde{\rho}^{(k)}}{4}$. We have

$$ $\frac{1+\tilde{\rho}^{(k)}}{2}\leq\phi_{22}^{(k)}\leq\frac{3+\tilde{\rho}^{(k)}}{4}\qquad\Rightarrow\qquad 0\leq\alpha^{(k)}\leq\frac{1}{2\sqrt{3d_{max}^{(k)}}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}}.$ $$

Step 3: Determining the constraints.
Having made sure that (i) $0<\phi_{11}^{(k)}\leq 1$ and (ii) $0<\phi_{22}^{(k)}\leq 1$ in the previous step, we can continue to solve Eq. ([15](#A11.E15)). For the left-hand side of the inequality, we have

$$ $\displaystyle\left(1-\phi_{11}^{(k)}\right)\left(1-\phi_{22}^{(k)}\right)$ $\displaystyle=\left[\left(1-\Gamma_{1}^{(k)}\right)\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)\mu\alpha^{(k)}\right]\left(1-\phi_{22}^{(k)}\right)$ $\displaystyle\geq\left[\left(1-\Gamma_{1}^{(k)}\right)\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)\mu\alpha^{(k)}\right]\frac{1-\tilde{\rho}^{(k)}}{4}$ $$

Now, putting this back to Eq. ([15](#A11.E15)), we get

$$ $\left[\left(1-\Gamma_{1}^{(k)}\right)\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)\mu\alpha^{(k)}\right]\frac{1-\tilde{\rho}^{(k)}}{4}>\phi_{12}^{(k)}\phi_{21}^{(k)}$ $$

$$ $\begin{gathered}\begin{aligned} \Rightarrow\qquad\left[\frac{\beta^{2}d_{max}^{(k)}}{2m}\left(1+\Gamma_{1}^{(k)}\right)\alpha^{(k)}\right]&\left[\frac{6}{\mu}\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}md_{max}^{(k)}{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)\right)\right]\\ &<\left[\left(1-\Gamma_{1}^{(k)}\right)\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)\mu\alpha^{(k)}\right]\frac{1-\tilde{\rho}^{(k)}}{4}\end{aligned}\\ \Rightarrow\qquad\alpha^{(k)}<\frac{1}{2\sqrt{3}d_{max}^{(k)}}\sqrt{\frac{1-\Gamma_{1}^{(k)}}{1+\Gamma_{1}^{(k)}}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{\mu}{\beta\zeta}\sqrt{\frac{1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)}{1+\frac{2\beta^{2}}{\zeta^{2}}\left(1-d_{min}^{(k)}\right)}}.\end{gathered}$ $$

Finally, we solve for Eq. ([16](#A11.E16)), i.e., $c=\phi_{11}^{(k)}\phi_{22}^{(k)}-\phi_{12}^{(k)}\phi_{21}^{(k)}>0$. Noting that by solving Eq. ([15](#A11.E15)) we made sure that $1-\phi_{11}^{(k)}-\phi_{22}^{(k)}+\phi_{11}^{(k)}\phi_{22}^{(k)}-\phi_{12}^{(k)}\phi_{21}^{(k)}>0$, we can write

$$ $\begin{gathered}c>0\quad\Rightarrow\quad\phi_{11}^{(k)}+\phi_{22}^{(k)}-1>0\quad\Rightarrow\quad 1-\left(1-\Gamma_{1}^{(k)}\right)\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)\mu\alpha^{(k)}+\frac{1+\tilde{\rho}^{(k)}}{2}-1>0\\ \Rightarrow\qquad\alpha^{(k)}<\frac{1+\tilde{\rho}^{(k)}}{2\mu\left(1-\Gamma_{1}^{(k)}\right)\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)},\end{gathered}$ $$

in which we have used the value of $\phi_{11}^{(k)}$ itself, but the lower bound of $\phi_{22}^{(k)}$.

Step 4: Putting all the constraints together.
Reviewing all the constraints on $\alpha^{(k)}$ from the beginning of this appendix, we can collect all of the constraints together and simplify them as

$$ $\displaystyle\begin{aligned} \alpha^{(k)}<\min\Bigg{\{}&\Gamma_{1}^{(k)}\frac{\mu^{2}\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)}{2\beta^{3}\left(3-2d_{min}^{(k)}\right)},\frac{1}{\mu\left(1-\Gamma_{1}^{(k)}\right)\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)},\\ &\frac{1}{2\sqrt{3d_{max}^{(k)}}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}},\frac{1}{2\sqrt{3}d_{max}^{(k)}}\sqrt{\frac{1-\Gamma_{1}^{(k)}}{1+\Gamma_{1}^{(k)}}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{\mu}{\beta\zeta}\sqrt{\frac{1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)}{1+\frac{2\beta^{2}}{\zeta^{2}}\left(1-d_{min}^{(k)}\right)}},\\ &\frac{1+\tilde{\rho}^{(k)}}{2\mu\left(1-\Gamma_{1}^{(k)}\right)\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)}\Bigg{\}}\end{aligned}$ (38) $\displaystyle\begin{aligned} =\min\Bigg{\{}&\Gamma_{1}^{(k)}\frac{\mu^{2}\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)}{2\beta^{3}\left(3-2d_{min}^{(k)}\right)},\frac{1+\tilde{\rho}^{(k)}}{2\mu\left(1-\Gamma_{1}^{(k)}\right)\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)},\\ &\frac{1}{2\sqrt{3d_{max}^{(k)}}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}},\frac{1}{2\sqrt{3}d_{max}^{(k)}}\sqrt{\frac{1-\Gamma_{1}^{(k)}}{1+\Gamma_{1}^{(k)}}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{\mu}{\beta\zeta}\sqrt{\frac{1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)}{1+\frac{2\beta^{2}}{\zeta^{2}}\left(1-d_{min}^{(k)}\right)}}\Bigg{\}}\end{aligned}$ $$

while satisfying

$$ $0<\Gamma_{1}^{(k)}\leq 1.$ (39) $$

Note that one of the terms in Eq. ([38](#A20.E38)) was trivially removed since $\frac{1+\tilde{\rho}^{(k)}}{2}<1$. Furthermore, for the last two terms, we have

$$ $\begin{gathered}(a)\frac{1}{2\sqrt{3d_{max}^{(k)}}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{\zeta^{2}+2\beta^{2}}}>\frac{1}{2\sqrt{3d_{max}^{(k)}}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\sqrt{6}\beta},\\ (b)\frac{1}{2\sqrt{3}d_{max}^{(k)}}\sqrt{\frac{1-\Gamma_{1}^{(k)}}{1+\Gamma_{1}^{(k)}}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{\mu}{\beta\zeta}\sqrt{\frac{1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)}{1+\frac{2\beta^{2}}{\zeta^{2}}\left(1-d_{min}^{(k)}\right)}}<\frac{1}{2\sqrt{3d_{max}^{(k)}}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\frac{1}{\zeta\sqrt{d_{max}^{(k)}}}\sqrt{\frac{1-\Gamma_{1}^{(k)}}{1+\Gamma_{1}^{(k)}}}.\end{gathered}$ $$

We found a lower bound $(a)$, and an upper bound for $(b)$. Since the constraint on $\alpha^{(k)}$ includes the minimum of these two terms, showing that the upper bound for $(b)$ is less than the lower bound for $(a)$, will constitute the fact that the $(b)\leq(a)$. We have

$$ $\frac{1-\Gamma_{1}^{(k)}}{1+\Gamma_{1}^{(k)}}\leq\frac{\zeta^{2}d_{max}^{(k)}}{6\beta^{2}}\qquad\Rightarrow\qquad\Gamma_{1}^{(k)}\geq\frac{1-\frac{\zeta^{2}d_{max}^{(k)}}{6\beta^{2}}}{1+\frac{\zeta^{2}d_{max}^{(k)}}{6\beta^{2}}}=\Gamma_{1}^{\star}.$ $$

Therefore, choosing $\Gamma_{1}^{(k)}=\Gamma_{1}^{\star}$ will give us tightest possible bounds. However, in order to get simpler expressions for the first two terms in Eq. ([38](#A20.E38)) which would give us better intuition, we choose the infimum of $\Gamma_{1}^{(k)}$ for them, i.e., $1/5$, to obtain

$$ $\displaystyle\alpha^{(k)}<\min\Bigg{\{}\frac{\mu^{2}\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)}{10\beta^{3}\left(3-2d_{min}^{(k)}\right)},$ $\displaystyle\frac{5}{4}\frac{1+\tilde{\rho}^{(k)}}{2\mu\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)},$ $\displaystyle\frac{1}{6\sqrt{2d_{max}^{(k)}}}\frac{\mu}{\beta^{2}}\frac{1-\tilde{\rho}^{(k)}}{\sqrt{1+\tilde{\rho}^{(k)}}}\sqrt{\frac{1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)}{1+\frac{2\beta^{2}}{\zeta^{2}}\left(1-d_{min}^{(k)}\right)}}\Bigg{\}}$ $$

Step 5: Obtaining $\rho(\mathbf{\Phi}^{(k)})$.
We established $\rho(\mathbf{\Phi}^{(k)})<1$ in the previous steps. The last step is to determine what $\rho(\mathbf{\Phi}^{(k)})$ is. We have

$$ $\displaystyle\rho{\left(\Phi^{(k)}\right)}$ $\displaystyle=\frac{-b+\sqrt{b^{2}-4ac}}{2a}=\frac{\phi_{11}^{(k)}+\phi_{22}^{(k)}+\sqrt{{\left(\phi_{11}^{(k)}+\phi_{22}^{(k)}\right)}^{2}-4\left(\phi_{11}^{(k)}\phi_{22}^{(k)}-\phi_{12}^{(k)}\phi_{21}^{(k)}\right)}}{2}$ $\displaystyle=\frac{\phi_{11}^{(k)}+\phi_{22}^{(k)}+\sqrt{{\left(\phi_{11}^{(k)}-\phi_{22}^{(k)}\right)}^{2}+4\phi_{12}^{(k)}\phi_{21}^{(k)}}}{2}$ $\displaystyle\begin{aligned} \,\,=\,\,&\frac{1-\left(1-\Gamma_{1}^{(k)}\right)\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)\mu\alpha^{(k)}+\frac{1+\tilde{\rho}^{(k)}}{2}+3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\right)}{2}\\ &\begin{aligned} &+\frac{1}{2}\Bigg{[}\Bigg{(}1-\left(1-\Gamma_{1}^{(k)}\right)\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)\mu\alpha^{(k)}-\frac{1+\tilde{\rho}^{(k)}}{2}-3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\right)\Bigg{)}^{2}\\ &+4\frac{\beta^{2}d_{max}^{(k)}}{2m}\left(1+\Gamma_{1}^{(k)}\right)\alpha^{(k)}\frac{6}{\mu}\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}md_{max}^{(k)}{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)\right)\Bigg{]}^{1/2}\end{aligned}\end{aligned}$ $\displaystyle\begin{aligned} \,\,=\,\,&\frac{3+\tilde{\rho}^{(k)}}{4}-\frac{1}{2}\left(1-\Gamma_{1}^{(k)}\right)\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)\mu\alpha^{(k)}+\frac{3}{2}\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\right)\\ &\begin{aligned} &+\frac{1}{2}\Bigg{[}\Bigg{(}\frac{1-\tilde{\rho}^{(k)}}{2}-\left(1-\Gamma_{1}^{(k)}\right)\left(1-\frac{2\beta^{2}}{\mu^{2}}\left(1-d_{min}^{(k)}\right)\right)\mu\alpha^{(k)}-3\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}{\left(\alpha^{(k)}\right)}^{2}\left(\zeta^{2}+2\beta^{2}\right)\Bigg{)}^{2}\\ &+\frac{12\beta^{2}}{\mu}\left(1+\Gamma_{1}^{(k)}\right)\frac{1+\tilde{\rho}^{(k)}}{1-\tilde{\rho}^{(k)}}{\left(d_{max}^{(k)}\right)}^{2}{\left(\alpha^{(k)}\right)}^{3}\left(\zeta^{2}+2\beta^{2}\left(1-d_{min}^{(k)}\right)\right)\Bigg{]}^{1/2}\end{aligned}\end{aligned}$ $\displaystyle=\frac{3+\tilde{\rho}^{(k)}}{4}-A\alpha^{(k)}+B{\left(\alpha^{(k)}\right)}^{2}+\frac{1}{2}\sqrt{{\left(\frac{1-\tilde{\rho}^{(k)}}{2}-2\left(A\alpha^{(k)}+B{\left(\alpha^{(k)}\right)}^{2}\right)\right)}^{2}+C{\left(\alpha^{(k)}\right)}^{3}}$ $$

## Appendix U Proof of Theorem 4.12

Note that by the properties of spectral radius, we have that $\mathbf{\Phi}\|\cdot\|\leq\rho(\mathbf{\Phi})\|\cdot\|$. Now, using Eq. ([34](#A17.E34)), we can write

$$ $\begin{bmatrix}\mathbb{E}_{\mathbf{\Xi}^{(k)}}{\left[F{\left(\mathbf{\bar{\theta}}^{(k+1)}\right)}-F^{\star}\right]}\\ \mathbb{E}_{\mathbf{\Xi}^{(k)}}{\left[{\left\|\mathbf{\Theta}^{(k+1)}-\mathbf{1}_{m}\mathbf{\bar{\theta}}^{(k+1)}\right\|}^{2}\right]}\end{bmatrix}\leq\rho{\left(\mathbf{\Phi}\right)}^{k+1}\begin{bmatrix}F{\left(\mathbf{\bar{\theta}}^{(0)}\right)}-F^{\star}\\ {\left\|\mathbf{\Theta}^{(0)}-\mathbf{1}_{m}\mathbf{\bar{\theta}}^{(0)}\right\|}^{2}\end{bmatrix}+\sum_{r=1}^{k}{\rho{\left(\mathbf{\Phi}\right)}^{k-r+1}\mathbf{\Psi}}+\mathbf{\Psi}.$ $$

We emphasize that the time index $k$ in $\mathbf{\Phi}^{(k)}$ and $\mathbf{\Psi}^{(k)}$ was dropped, since we are using a constant step size, constant SGD probabilities and aggregations. This results in the constant matrix $\mathbf{\Phi}^{(k)}=\mathbf{\Phi}$ and the constant vector $\mathbf{\Psi}^{(k)}=\mathbf{\Psi}$. Focusing on the term $\sum_{r=1}^{k}{\rho{\left(\mathbf{\Phi}\right)}^{k-r+1}\mathbf{\Psi}}+\mathbf{\Psi}$, we get

$$ $\sum_{r=1}^{k}{\rho{\left(\mathbf{\Phi}\right)}^{k-r+1}\mathbf{\Psi}}+\mathbf{\Psi}=\sum_{r=1}^{k+1}{\rho{\left(\mathbf{\Phi}\right)}^{k-r+1}\mathbf{\Psi}}=\left(\sum_{u=0}^{k}{\rho{\left(\mathbf{\Phi}\right)}^{u}}\right)\mathbf{\Psi}\leq\left(\sum_{u=0}^{\infty}{\rho{\left(\mathbf{\Phi}\right)}^{u}}\right)\mathbf{\Psi}=\frac{1}{1-\rho{\left(\mathbf{\Phi}\right)}}\mathbf{\Psi}.$ $$

Putting the above inequalities together constitutes the fact the rate of convergence is geometric. Finally, noting that $\rho{(\mathbf{\Phi})}<1$ following [Q.4](#A17.Thmtheorem4), We can let $k\to\infty$ to get Eq. ([11](#S4.E11)).

## Appendix V Further Experiments

### V.1 Accuracy vs. Delay with Uniform Distribution

In the experiments we provided in Fig. [2](#S5.F2), the SGD and aggregation probabilities were sampled from a Beta distribution, e.g., $d_{i}^{(k)},b_{ij}^{(k)}\sim\operatorname*{Beta}(\alpha,\beta)$. In this section, we investigate sampling these probabilities from the uniform distribution, denoted as $\mathcal{U}(0,1]$.

We have provided experimental results for only the non-IID cases in Fig. [4](#A22.F4), under exactly the same setup outlined in Sec. [5.1](#S5.SS1). It can be observed that the findings discussed in Sec. [5.2](#S5.SS2) also hold here. In other words, our DSpodFL method outperforms the baselines in terms of accuracy per overall delay.

We will explain the intuitive reason of why DSpodFL is outperforming other baselines in both Figs. [2](#S5.F2) and [4](#A22.F4). Let $\mathcal{G}=(\mathcal{M},\mathcal{E})$ be given a network graph, and assume there exits two paths between nodes $i$ and $j$. Let one of these paths have a communication cost $k$ times more than the other path, where $k\gg 1$. In our DSpodFL method, the path with lower cost will be utilized roughly $k$ times more than the other path, thus resulting in lower communication overhead while still preserving information flow between nodes $i$ and $j$. Meanwhile, other methods, especially DGD and DFedAvg methods, do not take this into account.

Figure: (a) FMNIST, Non-IID.
Refer to caption: /html/2402.03448/assets/ICML2024/images/Legend.png

### V.2 Effects of System Parameters with Beta Distribution

In the experiments we provided in Fig. [3](#S5.F3), specifically Figs. [3(a)](#S5.F3.sf1), [3(b)](#S5.F3.sf2) and [3(c)](#S5.F3.sf3), the SGD and aggregation probabilities were sampled from a uniform distribution, e.g., $d_{i}^{(k)},b_{ij}^{(k)}\sim\mathcal{U}(0,1]$. In this section, we investigate sampling these probabilities from the Beta distribution, denoted as $\operatorname*{Beta}(0.5,0.5)$.

We have provided experimental results for only the non-IID cases in Fig. [5](#A22.F5), under exactly the same setup outlined in [5.1](#S5.SS1). It can be observed that the findings discussed in Sec. [5.2](#S5.SS2) also hold here. In other words, the performance gain of our DSpodFL method compared to the baselines is robust regardless of the variation in system parameters, i.e, (i) data heterogeneity level, (ii) level of graph connectivity level and (iii) number of clients in the system.

Figure: (a) Varying number of labels per client.
Refer to caption: /html/2402.03448/assets/ICML2024/images/Legend.png

### V.3 Effects of System Parameters on CIFAR10

In both Sections [5](#S5) and [V.2](#A22.SS2), we analyzed the effects of system parameters on the FMNIST dataset. Here, we will provide similar experimental results for the CIFAR10 dataset. Note that while an SVM model was trained on the FMNIST dataset, for CIFAR10 we use the VGG11 model. We sample the SGD and aggregation probabilities from the Beta distribution, i.e., $d_{i}^{(k)}\sim\operatorname*{Beta}(0.8,0.8)$ and $b_{ij}^{(k)}\sim\operatorname*{Beta}(0.8,0.8)$, respectively.

The results in Fig. [6](#A22.F6) are carried out in the non-IID regime as well, under the setup descibed in Sec. [5.1](#S5.SS1). Again, the findings discussed in Sec. [5.2](#S5.SS2) and [V.2](#A22.SS2) can be validated here, showing that DSpodFL outperforms the state-of-the-art in various settings. This demonstrates that our results hold regardless of the dataset in question and the ML model being used, adding yet another dimension of robustness to our methodology.

Figure: (a) Varying number of labels per client.
Refer to caption: /html/2402.03448/assets/ICML2024/images/Legend.png

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: I have a few concerns, and I would be very glad if these are addressed:

1. Will taking into account the correlation between inter-client communication improve the guarantee, instead of each client independently making a decision for itself. In general, sporadic communications are often correlated.

2. Referring to Def. 4.6, why are the indicator variables not defined as Bernoulli random variables? It seems like they are modeled as Bernoulli variables, but it is not explicitly mentioned anywhere. 

3. In the aggregation step, the clients need to know which nodes communicate to it? In other words, is a blind aggregation where the identity of the participating clients is anonymized, possible? 

Also, some recent works in communication sporadicity is missing: For example, in this work: https://ieeexplore.ieee.org/document/10705313, communication sporadicity is considered in conjunction with privacy constraints, although in a semi-decentralized setting. Privacy is an important aspect of federated learning, and so the paper will benefit with some discussions on the privacy implications of the current algorithm.
soundness: 3
strengths: The algorithm framework proposed in eq (2) that considers the effect of both kinds of sporadicity as mentioned above is one of the primary contributions of the paper. This is further formulated as a matrix update in eq. (3), and the consensus weights are chosen the mixing matrix is doubly stochastic.

The unifying approach to analyze computation and communication sporadicity is definitely an important step towards analyzing decentralized algorithm. The work has been placed well (and compared with) in the context of existing literature. The convergence analysis is quite comprehensive, and aligns with the standard analysis techniques of works in this line. The analytical contribution of the paper is definitely commendable.
summary: This work proposes a generalized framework for analyzing the challenges of federated learning in a decentralized setting. Such challenges include heterogeneity in the updates of individual clients, and communication constraints for achieving consensus in a decentralized setup (which is more challenging that the typical "star" topology with a central PS). The term "sporadicity" in the title refers to varying frequencies of both -- local updates at clients (limited by computational capacity), and inter-client communication (limited by network capacity). The work proposes a unifying framework for analyzing the effect of this sporadicity on the convergence rate.
weaknesses: I have some important concerns which I list here in the "Weaknesses" section. Other minor concerns or questions are mentioned in the next section. I would appreciate it if the authors could clarify the following concerns:

1. My major concern is that it is not really clear where the gain of DSpodFL is coming from? The work shows improvements in numerical simulations, in which the X-axis in the total latency. Is the primary intuition behind the improved performance of DSpodFL just the fact that frequent communications are not necessary, which other decentralized algorithms do? Is the benefit of DSpodFL over other algorithms quantified/discussed anywhere in the paper?

2. Are the weights $r_{ij}$ need to be known beforehand? For example, in Metropolis-Hastings mixing, the future topology of the graph needs to be known -- an assumption that may not hold true for federated learning when the network is dynamically changing (for mobile clients, for example), and it is not easy to know the union of all edge sets and determine the weight. How are they chosen in the simulations?

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. Paper mentions that (Even et al 2024) did not consider time variations in resource heterogeneity and I would like to ask you to elaborate on this. In my understanding asynchronous communication allows for resource heterogeneity. 

2. What if in proposition 4.10, d_{max}^{k} = 0 for some k? I think it is allowed by the framework and it would mean that you have to divide by zero? 

3. in line 360 you state that lim_{k ->0} \Phi(k:0) = 0 is enough to prove that consensus error and average error converges to zero, however even in this case, it depends on convergence of $\Psi^{(k)}$ that might be non zero or might even diverge. Can you clarify on that? 

4. Why does the matrix R have to be doubly stochastic if you anyways renormalize the matrix P later to be doubly stochastic?

5. I did not understand how exactly result (10) recovers (Koloskova (2020)) (comment in lines 386 and 387), could you provide a more detailed derivation of this result? also, (Koloskova (2020)) allows for local steps in decentralized SGD, meaning that d_{min} = 0 at those steps, could you compare your result with (Koloskova (2020)) for that local decentralized SGD? Same for the non-convex functions. 

6. How does $w_1, w_2, w_3, w_4, w_5$ depend on the key parameters of the problem (parameters from Assumptions 4.2-4.4). Is there a way to simplify the convergence rate, e.g. by using O-notation? 

7. What does “average total delay occurred ip to iteration k" mean? Is it total simulated time? 

8. In experimental comparison, how exactly are the baseline algorithms implemented under the proposed heterogeneity of communication and computation? How does d_i and b_{ij} translate to the speed of the node?
soundness: 2
strengths: The paper proposed framework is general and allows for varying resource availability. The paper compares its framework with the baselines.
summary: The paper considers decentralized optimization with nodes having varying communication time and computation resources that might also change in time. The paper analyzes convergence rate of proposed framework for strongly convex and non-convex functions and evaluates effectiveness of the framework in experiments.
weaknesses: 1. The proposed framework does now allow for the slow gradient computation, as gradients cannot be delayed. This is because the framework does not allow for computation and communication sporadicity being correlated (per assumption 4.3.), and according to (2) each gradient has to be computed at the latest local model $\theta_i$. This means that if some node computed the gradient for a long time, and in the meantime local model is being updated due to the communication on this node occurring, the node has to drop its previous computations and start computing its gradient from scratch on the new model so that it can return the gradient at the latest model.

    There are two possible solutions to this: either allow for communication and computation being correlated (i.e. while node computes, no communication happens), or allow for the gradients to be delayed.

    To me this is a big limitation of the framework.

3. Only asymptotic convergence is proven (i.e. when the number of iterations K goes to infinity), while previous frameworks such as (Even 2024) give convergence bound for any number of iterations K. 


4. Paper has several flows in presentation: e.g. first it states that framework the paper analyzes is (2), but then actual analyzed algorithm is in equations (3)-(4) that is not equivalent to (2) (difference comes from re-normalization of the diagonal element p_{ii}^k).

5. Convergence rate derived for non-convex functions is hard to understand, as it depends on some parameters $w_1, w_2, w_3, w_4, w_5$ that are defined only in appendix. 

6. Paper does not tune the learning rate, but uses the same learning rate for different algorithms - that might give advantage to some algorithms. 

7. Experimental comparison to (Even 2024) is missing. Is there a specific reason why you excluded that baseline from comparison?

---

confidence: 4
contribution: 2
initial_rating: 8
presentation: 3
questions: For the expectation calculations, some of them seems to be conditioned on past realizations, a filtration should be setup to rigorously justify the steps. If this is not the case, please explain. 

How much information is necessary by each of the agents to calculate the learning rates? 

Why should all agents use the same learning rates?
soundness: 3
strengths: The algorithm allows for a very general stochasticity capturing varying communication and computation cost and allows for heterogeneity in agents' capabilities. The algorithm is also written in a very clean fashion. The proofs appear to be mostly right.
summary: This paper studies decentralized federated learning setting, where a central server is lacking and the agents may perform a stochastic number of local iterations. Furthermore, the peer-to-peer communication also happen in a random fashion. The authors propose a method called DSpodFL, which combines consensus and local gradient descent while allowing stochasticity. The main contribution lies in the algorithm setup/flexibility, convergence analysis using indicator random variable to model stochasticity and allowing for milder assumptions for both convex and nonconvex cases.
weaknesses: The proofs in the appendix lacks explanation for the steps.

My main complaint is that while this is a good first step towards allowing different kinds of stochasticity, the proposed algorithm misses the mark in the sense that the value it converges to is not the original optimal solution. There has been a long line of literature in distributed optimization tackling the same setup (without multiple local steps) by including additional error correction terms, (almost) exact convergence can be achieved. A simple counting of the activation frequencies as in the following paper could help reduce the error term in the limit. Because of this, I'm not sure how useful the proposed method would be for any real applications, especially with large amount of heterogeneity in the activations. I'm marginally willing to accept the paper due to its innovative computation framework. 

Ram, S. Sundhar, A. Nedić, and Venugopal V. Veeravalli. "Asynchronous gossip algorithms for stochastic optimization." Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference. IEEE, 2009.

---

confidence: 4
contribution: 2
initial_rating: 8
presentation: 3
questions: 1. The proposed frame can unify existing algorithms including DGD, DFedAvg and RG. If we can obtaining the convergence analysis of these existing analysis **directly** from Theorem 4.11 and 4.12? And if the convergence rates of the existing algorithms obtained from Theorem 4.11 and 4.12 **match** the existing convergence analysis? Please present the detailed steps.

2. Figure 2(b) only show the convergence curves when $\tau\in[0,10000]$, and DSpodFL only achieve the test accuracy of about **0.6** during this period. So can the authors provide convergence curves of these algorithms with a larger $\tau$ such as 20000 or 30000? Similarly, can the authors provide the convergence curves of Figure 2(c) with a larger $\tau$?

3. How do the algorithms including DSpodFL perform in test accuracy with respect to wall-clock time?

I will update the scord according to the response during the discussion period.
soundness: 3
strengths: 1. A unified algorithm framework.

2. Making clients able to take local update and communication according to its available resources.

3. Convergence analysis in both convex and nonconvex scenarios.
summary: The author present DSpodFL, a unified framework of decentralized federated learning. DSpodFL allows each client to take local update and communication intermittently according to its available resources. And DSpodFL framework also involves some existing decentralized federated learning algorithms. The authors provided the convergence analysis of DSpodFL in convex and nonconvex settings.
weaknesses: See questions

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Perhaps $p_{ii}^k = 1 -\sum_{j \in M} r_{ij} \hat v_{ij}^k + r_{ii} \hat v_{ii}^k $ in equation (4)?
soundness: 4
strengths: 1.	The investigated problem is novel, as the authors address the combined effects of sporadic local client computations and inter-client communication, an aspect previously unexplored in DFL.

2.	The presentation of the paper is clear. The authors provide rigorous convergence results for both strongly convex and nonconvex settings, which are well-justified.

3.	The numerical experiments are sufficient and effectively showcase the advantages of the proposed DSpodFL framework.
summary: This paper develops a generalized algorithmic framework, DSpodFL, for decentralized federated learning (DFL), which effectively integrates the heterogeneity and dynamics of local stochastic gradient descents (SGDs) and aggregation processes. The convergence of DSpodFL is analyzed for both strongly convex and nonconvex loss functions. Additionally, numerical experiments on various datasets demonstrate the advantages of the proposed method.
weaknesses: 1.In Section 3.3, why the random matrix $P^k$ is doubly stochastic and symmetric? This is not immediately clear, and providing a proof and an illustrative example would enhance understanding.

2.In Assumption 4.1, the gradient diversity is measured by $ || \nabla F(\theta) - \nabla F_i(\theta) ||$, while in Assumption 4.2, it is measured by $ ||\nabla F_i(\theta) ||$.What is the rationale behind this distinction?

3.In the analysis with a diminishing learning rate, why does exact convergence require an increasing frequency of SGDs over time? Moreover, the dependence of SGD probabilities on the stepsize seems unrealistic. Why does this requirement not apply when using a constant stepsize?

Meta-review: This paper studies the decentralized learning setting, where clients are connected via a network topology and perform gradient updates based on their local data, followed by averaging with their neighboring nodes in the network. A key contribution of this work is the proposal of a general framework, DSpodFL, for analyzing optimization methods with sporadicity in both local gradient computations and aggregation processes.

A major strength of this framework lies in its flexibility, as it employs indicator random variables to model stochasticity and allows for milder assumptions in both convex and non-convex cases. This represents a meaningful advancement in the literature on decentralized optimization, and the paper is likely to be of interest to the ICLR community.

However, a potential weakness, which stems from the generality of the framework, is that it remains unclear in this version of the paper whether the convergence results obtained using the DSpodFL framework can match the prior analyses of earlier work for specific settings. The discussion in the newly added Section P.2 of the appendix remains somewhat vague in this regard, as the big-O notation obscures not only constants but also problem-specific parameters. I hope this can be further clarified in the final version.

Decision: Accept (Spotlight)