#  Stability and Generalization of the Decentralized Stochastic Gradient
Descent††thanks: This work is sponsored in part by National Key R&D Program of
China (2018YFB0204300), and the National Science Foundation of China (No.
61932001 and 61906200).

Tao Sun1, Dongsheng Li1, and Bao Wang2
1College of Computer, National University of Defense Technology, Changsha,
Hunan, China.
2Scientific Computing & Imaging Institute, University of Utah, USA.
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding
author.

###### Abstract

The stability and generalization of stochastic gradient-based methods provide
valuable insights into understanding the algorithmic performance of machine
learning models. As the main workhorse for deep learning, stochastic gradient
descent has received a considerable amount of studies. Nevertheless, the
community paid little attention to its decentralized variants. In this paper,
we provide a novel formulation of the decentralized stochastic gradient
descent. Leveraging this formulation together with (non)convex optimization
theory, we establish the first stability and generalization guarantees for the
decentralized stochastic gradient descent. Our theoretical results are built
on top of a few common and mild assumptions and reveal that the
decentralization deteriorates the stability of SGD for the first time. We
verify our theoretical findings by using a variety of decentralized settings
and benchmark machine learning models.

## Introduction

The great success of deep learning (LeCun, Bengio, and Hinton 2015) gives
impetus to the development of stochastic gradient descent (SGD) (Robbins and
Monro 1951) and its variants (Nemirovski et al. 2009; Duchi, Hazan, and Singer
2011; Rakhlin, Shamir, and Sridharan 2012; Kingma and Ba 2014; Wang et al.
2020). Although the convergence results of SGD are abundant, the effects
caused by the training data is absent. To this end, the generalization error
(Hardt, Recht, and Singer 2016; Lin, Camoriano, and Rosasco 2016; Bousquet and
Elisseeff 2002; Bottou and Bousquet 2008) is developed as an alternative
method to analyze SGD. The generalization bound reveals the performance of
stochastic algorithms and characterizes how the training data and stochastic
algorithm jointly affect the target machine learning model. To mathematically
describe generalization, Hardt, Recht, and Singer (2016); Bousquet and
Elisseeff (2002); Elisseeff, Evgeniou, and Pontil (2005) introduce the
algorithmic stability for SGD, which mainly depends on the landscape of the
underlying loss function, to study the generalization bound of SGD. The
stability theory of SGD has been further developed (Charles and Papailiopoulos
2018; Kuzborskij and Lampert 2018; Lei and Ying 2020).

SGD has already been widely used in parallel and distributed settings (Agarwal
and Duchi 2011; Dekel et al. 2012; Recht et al. 2011), e.g., the decentralized
SGD (D-SGD) (Ram, Nedić, and Veeravalli 2010b; Lan, Lee, and Zhou 2020;
Srivastava and Nedic 2011; Lian et al. 2017). D-SGD is implemented without a
centralized parameter server, and all nodes are connected through an
undirected graph. Compared to the centralized SGD, the decentralized one
requires much less communication with the busiest node (Lian et al. 2017),
accelerating the whole computational system.

From the theoretical viewpoint, although there exist plenty of convergence
analysis of D-SGD (Sirb and Ye 2016; Lan, Lee, and Zhou 2020; Lian et al.
2017, 2018), the stability and generalization analysis of D-SGD remains rare.

### Contributions

In this paper, we establish the first theoretical result on the stability and
generalization of the D-SGD. We elaborate on our contributions below.

  1. 1.

Stability of D-SGD: We provide the uniform stability of D-SGD in the general
convex, strongly convex, and nonconvex cases. Our theory shows that besides
the learning rate, data size, and iteration number, the stability and
generalization of D-SGD are also dependent on the connected graph structure.
To the best of our knowledge, our result is the first theoretical stability
guarantee for D-SGD. In the general convex setting, we also present the
stability of D-SGD in terms of the ergodic average instead of the last
iteration for the excess generalization analysis.

  2. 2.

Computational errors for D-SGD with convexity and projection: We consider more
general schemes of D-SGD, that is, D-SGD with projection. In the previous work
(Ram, Nedić, and Veeravalli 2010b), to get the convergence rate, the authors
need to make additional assumptions on the graph ([Assumptions 2 and 3, (Ram,
Nedić, and Veeravalli 2010b)]). In this paper, we remove these assumptions,
and we present the computational errors of D-SGD with projections in the
strongly convex setting.

  3. 3.

Generalization bounds for D-SGD with convexity: We derive (excess)
generalization bounds for convex D-SGD. The excess generalization is
controlled by the computational error and the generalization bound, which can
be directly obtained from the stability.

  4. 4.

Numerical results: We numerically verify our theoretical results by using
various benchmark machine learning models, ranging from strongly convex and
convex to nonconvex settings, in different decentralized settings.

## Prior Art

In this section, we briefly review two kinds of related works: decentralized
optimization and stability and generalization analysis of SGD.

Decentralized and distributed optimization Decentralized algorithms arise in
calculating the mean of data distributed over multiple sensors (Boyd et al.
2005; Olfati-Saber, Fax, and Murray 2007). The decentralized (sub)gradient
descent (DGD) algorithms are propose and studied by (Nedic and Ozdaglar 2009;
Yuan, Ling, and Yin 2016). Recently, DGD has been generalized to the
stochastic settings. With a local Poisson clock assumption on each agent, Ram,
Nedić, and Veeravalli (2010a) proposes an asynchronous gossip algorithm. The
decentralized algorithm with a random communication graph is proposed in
(Srivastava and Nedic 2011; Ram, Nedić, and Veeravalli 2010b). Sirb and Ye
(2016); Lan, Lee, and Zhou (2020); Lian et al. (2017) consider the randomness
caused by the stochastic gradients and proposed the decentralized SGD (D-SGD).
The complexity analysis of D-SGD has been done in (Sirb and Ye 2016). In (Lan,
Lee, and Zhou 2020), the authors propose another kind of D-SGD that leverages
dual information, and provide the related computational complexity. In the
paper (Lian et al. 2017), the authors show the advantage of D-SGD compared to
the centralized SGD. In a recent paper (Lian et al. 2018), the authors
developed asynchronous D-SGD with theoretical convergence guarantees. The
biased decentralized SGD is proposed and studied by (Sun et al. 2019). In
(Richards and others 2020), the authors studied the stability for a non-fully
decentralized training method, in which each node needs to communicate extra
gradient information. Paper (Richards and others 2020) is closed to ours, but
we consider the DSGD, which is different from the algorithm investigated by
(Richards and others 2020) and more general. Further more, we studied the
nonconvex settings.

Stability and Generalization of SGD In (Shalev-Shwartz et al. 2010), on-
average stability is proposed and further studied by Kuzborskij and Lampert
(2018). The uniform stability of empirical risk minimization (ERM) under
strongly convex objectives is considered by Bousquet and Elisseeff (2002).
Extended results are proved with the pointwise-hypothesis assumption, which
shows that a class of learning algorithms is convergent with global optimum
(Charles and Papailiopoulos 2018). In order to prove uniform stability of SGD,
Hardt, Recht, and Singer (2016) reformulate SGD as a contractive iteration. In
(Lei and Ying 2020), a new stability notion is proposed to remove the bounded
gradient assumptions. In (Bottou and Bousquet 2008), the authors establish a
framework for the generalization performance of SGD. Hardt, Recht, and Singer
(2016) connects the uniform stability with generalization error. The
generalization errors with strong convexity are established in (Hardt, Recht,
and Singer 2016; Lin, Camoriano, and Rosasco 2016). The stability and
generalization are also studied for the Langevin dynamics (Li, Luo, and Qiao
2019; Mou et al. 2018).

## Setup

This part contains preliminaries and mathematical descriptions of our problem.
Analyzing the stability of D-SGD is more complicated than that of SGD due to
the challenge arises from the mixing matrix in D-SGD. We cannot directly adapt
the analysis for SGD to D-SGD. To this end, we reformulate D-SGD as an
operator iteration with an error term, which is followed by bounding the error
in each iteration.

### Stability and Generalization

The population risk minimization is an important model in machine learning and
statistics, whose mathematical formulation reads as

$\displaystyle\min_{{\bf x}\in\mathbb{R}^{d}}R({\bf
x}):=\mathbb{E}_{\xi\sim\mathcal{D}}f({\bf x};\xi),$

where $f({\bf x};\xi)$ denotes the loss of the model associated with data
$\xi$ and $\mathcal{D}$ is the data distribution. Due to the fact that
$\mathcal{D}$ is usually unknown or very complicated, we consider the
following surrogate ERM

$\displaystyle\min_{{\bf x}\in\mathbb{R}^{d}}R_{S}({\bf
x}):=\frac{1}{N}\sum_{i=1}^{N}f({\bf x};\xi_{i}),$

where $S:=\\{\xi_{1},\xi_{2},\ldots,\xi_{N}\\}$ and
$~{}\xi_{i}\sim\mathcal{D}$ is a given data.

For a specific stochastic algorithm $\mathcal{A}$ act on $S$ with output
$\mathcal{A}(S)$, the generalization error of $\mathcal{A}$ is defined as
$\epsilon_{\textrm{gen}}:=\mathbb{E}_{S,\mathcal{A}}[R(\mathcal{A}(S))-R_{S}(\mathcal{A}(S))].$
Here, the expectation is taken over the algorithm and the data. The
generalization bound reflects the joint effects caused by the data $S$ and the
algorithm $\mathcal{A}$. We are also interested in the excess generalization
error, which is defined as $\epsilon_{\textrm{ex-
gen}}:=\mathbb{E}_{S,\mathcal{A}}[R(\mathcal{A}(S))-R({\bf x}^{*})]$, where
${\bf x}^{*}$ is the minimizer of $R$. Let $\overline{{\bf x}}$ be the
minimizer of $R_{S}$. Due to the unbiased expectation of the data $S$, we have
$\mathbb{E}_{S}[R_{S}({\bf x}^{*})]=\mathbb{E}[R({\bf x}^{*})]$. Thus, Bottou
and Bousquet (2008) point out $\epsilon_{\textrm{ex-gen}}$ can be decomposed
as follows

$\displaystyle\mathbb{E}_{S,\mathcal{A}}[R(\mathcal{A}(S))-R({\bf
x}^{*})]=\underbrace{\mathbb{E}_{S,\mathcal{A}}[R(\mathcal{A}(S))-R_{S}(\mathcal{A}(S))]}_{\textrm{generalization
error}}$
$\displaystyle+\underbrace{\mathbb{E}_{S,\mathcal{A}}[R_{S}(\mathcal{A}(S))-R_{S}(\overline{{\bf
x}})]}_{\textrm{optimization
error}}+\underbrace{\mathbb{E}_{S,\mathcal{A}}[R_{S}(\overline{{\bf
x}})-R_{S}({\bf x}^{*})]}_{\textrm{test error}}.$

Notice that $R_{S}(\overline{{\bf x}})\leq R_{S}({\bf x}^{*})$, therefore

$\epsilon_{\textrm{ex-
gen}}\leq\epsilon_{\textrm{gen}}+\mathbb{E}_{S,\mathcal{A}}[R_{S}(\mathcal{A}(S))-R_{S}(\overline{{\bf
x}})].$

The uniform stability is used to bound the generalization error of a given
algorithm $\mathcal{A}$ (Hardt, Recht, and Singer 2016; Elisseeff, Evgeniou,
and Pontil 2005).

###### Definition 1

We say that the randomized algorithm $\mathcal{A}$ is $\epsilon$-_uniformly
stable_ if for any two data sets $S,S^{\prime}$ with $n$ samples that differ
in one example, we have

$\sup_{\xi}\mathbb{E}_{\mathcal{A}}\left[f(\mathcal{A}(S);\xi)-f(\mathcal{A}(S^{\prime});\xi)\right]\leq\epsilon.$

It has been proved that the uniform stability directly implies the
generalization bound.

######  Lemma 1 ((Hardt, Recht, and Singer 2016))

Let $\mathcal{A}$ be $\epsilon$-_uniformly stable_ , it follows
$|\mathbb{E}_{S,\mathcal{A}}[R(\mathcal{A}(S))-R_{S}(\mathcal{A}(S))]|\leq\epsilon.$

Thus, to get the generalization bound of a random algorithm, we just need to
compute the uniform stability bound $\epsilon$.

### Problem Formulation

Notation: We use the following notations throughout the paper. We denote the
$\ell_{2}$ norm of ${\bf x}\in\mathbb{R}^{d}$ as $\|{\bf x}\|$. For a matrix
${\bf A}$, ${\bf A}^{\top}$ denotes its transpose, we denote the spectral norm
of ${\bf A}$ as $\|{\bf A}\|_{\textrm{op}}$. Given another matrix ${\bf B}$,
${\bf A}\succ{\bf B}$ means that ${\bf A}-{\bf B}$ is positive define; and
${\bf A}\succeq{\bf B}$ means ${\bf A}-{\bf B}$ is positive semidefinite. The
identity matrix is defined as $\mathbb{I}$. We use $\mathbb{E}[\cdot]$ to
denote the expectation of $\cdot$ with respect to the underlying probability
space. For two positive constants $a$ and $b$, we denote $a=\mathcal{O}(b)$ if
there exists $C>0$ such that $a\leq Cb$, and $\widetilde{\mathcal{O}}(b)$
hides a logarithmic factor of $b$.

Let $\mathcal{D}_{i}=\\{\xi_{l(i)}\\}_{1\leq l\leq n}$ ($1\leq i\leq m$)
denote the data stored in the $i$th client, which follow the same distribution
of $\mathcal{D}$ 111For simplicity, we assume all clients have the same amount
of samples.. In this paper, we consider solving the objective function (1) by
the DGD, where

$\displaystyle f({\bf x}):=\frac{1}{mn}\sum_{i=1}^{m}\sum_{l=1}^{n}f({\bf
x};\xi_{l(i)}).$ (1)

Note that (1) is a decentralized approximation to the following population
risk function

$\displaystyle F({\bf x}):=\mathbb{E}_{\xi\sim\mathcal{D}}f({\bf x};\xi).$ (2)

To distinguish from the objective functions in the last subsection, we use $f$
rather than $R_{S}$ here. The decentralized optimization is usually associated
with a mixing matrix, which is designed by the users according to a given
graph structure. In particular, we consider the connected graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ with vertex set
$\mathcal{V}=\\{1,...,M\\}$ and edge set
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ with edge
$(i,l)\in\mathcal{E}$ represents the communication link between nodes $i$ and
$l$. Before proceeding, let us recall the definition of the mixing matrix.

######  Definition 2 (Mixing matrix)

For any given graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, the mixing matrix
${\bf W}=[w_{ij}]\in\mathbb{R}^{M\times M}$ is defined on the edge set
$\mathcal{V}$ that satisfies: (1) If $i\neq j$ and $(i,j)\notin{\cal E}$, then
$w_{ij}=0$; otherwise, $w_{ij}>0$; (2) ${\bf W}={\bf W}^{\top}$; (3)
$\mathrm{null}\\{\mathbb{I}-{\bf W}\\}=\mathrm{span}\\{\bf 1\\}$; (4)
$\mathbb{I}\succeq{\bf W}\succ-\mathbb{I}.$

Note that ${\bf W}$ is a doubly stochastic matrix (Marshall, Olkin, and Arnold
1979), and the mixing matrix is non-unique for a given graph. Several common
examples for ${\bf W}$ include the Laplacian matrix and the maximum-degree
matrix (Boyd, Diaconis, and Xiao 2004). A crucial constant that characterizes
the mixing matrix is

$\lambda:=\max\\{|\lambda_{2}|,|\lambda_{m}({\bf W})|\\},$

where $\lambda_{i}$ denotes the $i$th largest eigenvalue of ${\bf
W}\in\mathbb{R}^{m\times m}$. The definition of the mixing matrix implies that
$0\leq\lambda<1$.

######  Lemma 2 (Corollary 1.14., (Montenegro and Tetali 2006))

Let ${\bf P}\in\mathbb{R}^{m\times m}$ be the matrix whose elements are all
$1/m$. Given any $k\in\mathbb{Z}^{+}$, the mixing matrix ${\bf
W}\in\mathbb{R}^{m\times m}$ satisfies

$\|{\bf W}^{k}-{\bf P}\|_{\emph{op}}\leq\lambda^{k}.$

Note the fact that the stationary distribution of an irreducible aperiodic
finite Markov chain is uniform if and only if its transition matrix is doubly
stochastic. Thus, ${\bf W}$ corresponds to some Markov chain’s transition
matrix, and the parameter $0\leq\lambda<1$ characterizes the speed of
convergence to the stationary state.

We consider a general decentralized stochastic gradient descent with
projection, which carries out in the following manner: in the $t$-th
iteration, 1) client $i$ applies an approximate copy ${\bf
x}^{t}(i)\in\mathbb{R}^{d}$ to calculate a unbiased gradient estimate $\nabla
f({\bf x}^{t}(i);\xi_{j_{t}(i)})$, where $j_{t}(i)\in\mathbb{Z}^{+}$ is the
local random index; 2) client $i$ replaces its local parameters with the
weighted average of its neighbors, i.e.,

$\displaystyle\tilde{{\bf x}}^{t}(i)=\sum_{l\in\mathcal{N}(i)}w_{i,l}{\bf
x}^{t}(l);$ (3)

3) client $i$ updates its parameters as

$\displaystyle{\bf x}^{t+1}(i)$
$\displaystyle=\textbf{Proj}_{V}\Big{(}\tilde{{\bf x}}^{t}(i)-\alpha_{t}\nabla
f({\bf x}^{t}(i);\xi_{j_{t}(i)})\Big{)}$ (4)

with learning rate $\alpha_{t}>0$, and ${\bf Proj}_{V}(\cdot)$ stands for
projecting the quantity $\cdot$ into the space $V$. We stress that, in
practice, we do not need to compute the average ${\bf
x}^{t}=\frac{1}{m}\sum_{i=1}^{m}{\bf x}^{t}(i)$ in each iteration, and we take
the average only in the last iteration.

Algorithm 1 Decentralized Stochastic Gradient Descent (D-SGD)

0: $(\alpha_{t}>0)_{t\geq 0}$, initialization ${\bf x}^{0}$for node
$i=1,2,\ldots,m$ for $t=1,2,\ldots$ updates local parameter as (3) and (4)
${\bf x}^{t}=\frac{1}{m}\sum_{i=1}^{m}{\bf x}^{t}(i)$ end forend for

In the following, we draw necessary assumptions, which are all common and
widely used in the nonconvex analysis community.

###### Assumption 1

The loss function $f({\bf x};\xi)$ is nonnegative and differentiable with
respect to ${\bf x}$, and $\nabla f({\bf x};\xi)$ is bounded by the constant
$B$ over $V$, i.e., $\max_{{\bf x}\in V,\xi\sim\mathcal{D}}\|\nabla f({\bf
x};\xi)\|\leq B$.

Assumption 1 implies that $|f({\bf x};\xi)-f({\bf y};\xi)|\leq B\|{\bf x}-{\bf
y}\|,$ for all ${\bf x},{\bf y}\in V$ and any $\xi\sim\mathcal{D}$.

###### Assumption 2

The gradient of $f({\bf x};\xi)$ with respect to ${\bf x}$ is $L$-Lipschitz,
i.e., $\|\nabla f({\bf x};\xi)-\nabla f({\bf y};\xi)\|\leq L\|{\bf x}-{\bf
y}\|,$ for all ${\bf x},{\bf y}\in V$ and any $\xi\sim\mathcal{D}$.

###### Assumption 3

The set $V$ forms a closed ball in $\mathbb{R}^{d}$.

Compared with the scheme presented in (Lian et al. 2017), our algorithm
accommodates a projection after each update in each client. When $\nabla
f({\bf x};\xi)$ is non-strongly convex, $V$ can be set as the full space and
Algorithm 1 reduces to the scheme given in (Lian et al. 2017), whose
convergence has been well studied. Such a projection is more general and is
necessary for the strongly convex analysis; we explain this necessary claim as
follows: if $f$ is $\nu$-strongly convex, then $\|\nabla f({\bf
x})\|^{2}\geq\nu\|{\bf x}-{\bf x}^{*}\|^{2}$ with ${\bf x}^{*}$ being the
minimizer of $f({\bf x})$ (Karimi, Nutini, and Schmidt 2016). Thus, when ${\bf
x}$ is far from ${\bf x}^{*}$, the gradient is unbounded, which breaks
Assumption 1. However, with the projection procedure, D-SGD (Algorithm 1)
actually minimizes function (1) over the set $V$. The strong convexity gives
us $f({\bf x})-f({\bf x}^{*})\geq\frac{\nu}{2}\|{\bf x}-{\bf x}^{*}\|^{2}$,
which indicates ${\bf x}^{*}\in\textbf{B}(\textbf{0},\sqrt{{2(f({\bf
x}^{0})-\min f)}/{\nu}})$. Thus, when the radius of $V$ is large enough, the
projection does not change the output of D-SGD.

## Stability of D-SGD

In this section, we prove the stability theory for D-SGD in strongly convex,
convex, and nonconvex settings.

### General Convexity

This part contains the stability result of D-SGD when $f(\cdot;\xi)$ is
generally convex.

###### Theorem 1

Let $f(\cdot;\xi)$ be convex and Assumptions 1, 2, 3 hold. If the step size
$\alpha_{t}\leq{2}/{L}$, then D-SGD satisfies the uniform stability with

$\epsilon_{\emph{stab}}\leq\frac{2B^{2}\sum_{t=1}^{T-1}\alpha_{t}}{mn}+4B^{2}\sum_{t=1}^{T-1}\Big{[}(1+\alpha_{t}B)\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j}\Big{]}.$

Compared to the results of minimizing (1) by using centralized SGD with step
sizes $(\alpha_{t})_{t\geq 1}$ [Theorem 3.8, (Hardt, Recht, and Singer 2016)],
which yields the uniformly stable bound as
${2B^{2}\sum_{t=1}^{T-1}\alpha_{t}}/{(mn)}$. Theorem 1 shows that D-SGD
suffers from an additional term
$4B^{2}\sum_{t=1}^{T-1}(1+\alpha_{t}B)\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j}$,
which does not vanish when $\lambda>0$.

If we set $\alpha_{t}={1}/{(t+1)}$, with Lemma 3, it is easy to check that
$\epsilon_{\textrm{stab}}=\mathcal{O}(\frac{\ln T}{mn}+C_{\lambda}\ln T)$;
However, if we use a constant learning rate, (i.e., $\alpha_{t}\equiv\alpha$),
when $0<\lambda<1$, we have
$4B^{2}\sum_{t=1}^{T-1}(1+\alpha_{t}B)\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j}=\mathcal{O}(\frac{\alpha
T}{1-\lambda})$ and $\epsilon_{\textrm{stab}}=\mathcal{O}(\frac{\alpha
T}{1-\lambda}+\frac{\alpha T}{mn})$. The result indicates that although
decentralization reduces the busiest node’s communication, it hurts the
stability.

Theorem 1 provides the uniform stability for the last-iterate of D-SGD.
However, the computational error of D-SGD in general convexity case uses the
following average

$\textrm{ave}({\bf x}^{T}):=\frac{\sum_{t=1}^{T-1}\alpha_{t}{\bf
x}^{t}}{\sum_{t=1}^{T-1}\alpha_{t}}.$ (5)

Such a mismatch leads to the difficulty in characterizing the excess
generalization bound. It is thus necessary describe to the uniform stability
in terms of $\textrm{ave}({\bf x}^{T})$. To this end, we consider that D-SGD
outputs $\textrm{ave}({\bf x}^{t})$ instead of ${\bf x}^{t}$ in the $t$-th
iteration. The uniform stability, in this case, is defined as
$\epsilon_{\textrm{ave-stab}}$, and we have the following result.

###### Proposition 1

Let $f(\cdot;\xi)$ be convex and Assumptions 1, 2, 3 hold. If the step size
$\alpha_{t}\equiv\alpha\leq{2}/{L}$, the uniform stability
$\epsilon_{\emph{ave-stab}}$, in terms of $\textrm{ave}({\bf x}^{t})$,
satisfies

$\epsilon_{\emph{ave-stab}}\leq\frac{2B^{2}\alpha(t-1)}{mn}+\frac{4\alpha
B^{2}(1+\alpha B)(t-1)}{1-\lambda}1_{\lambda\neq 1}.$

Furthermore, if the step size is chosen as $\alpha_{t}={1}/{(t+1)}$, we have

$\epsilon_{\emph{ave-stab}}\leq\frac{B^{2}\ln
T}{mn}+\frac{4B^{2}(1+B)}{\ln(T+1)}1_{\lambda\neq 1}.$

Unlike the uniform stability for ${\bf x}^{T}$, the average turns out to be a
very complicated one. We thus just present two classical kinds of step size.

(a) Random (b) Star (c) Cycle (d) k-NNG (e) Bipartite

(f) Complete

Figure 1:  Structures of the connected graph used in our numerical tests.

### Strong Convexity

In the convex setting, for a fixed iteration number $T$, as the data size $mn$
increases and $\lambda$ decreases, $\epsilon_{\textrm{stab}}$ gets smaller for
both diminishing and constant learning rates. However, similar to SGD, D-SGD
also fails to have $\epsilon_{\textrm{stab}}$ under control when $T$
increases. This drawback does not exist in the strongly convex setting.

Strongly convex loss functions appear in the $\ell_{2}$ regularized machine
learning models. As mentioned in Section 2, to guarantee the bounded gradient,
the set $V$ should be restricted to a closed ball. We formulate the uniform
stability results in this case in Theorem 2.

###### Theorem 2

Let $f(\cdot;\xi)$ be $\nu$-strongly convex and Assumptions 1, 2, 3 hold. If
the step size $\alpha_{t}\equiv\alpha\leq{1}/{L}$, then D-SGD satisfies the
uniform stability with

$\epsilon_{\emph{stab}}\leq\frac{2B^{2}}{mn\nu}+\frac{4(1+\alpha
B)B^{2}}{\nu}\frac{1_{\lambda\neq 0}}{1-\lambda}.$

Furthermore, if the step size $\alpha_{t}=\frac{1}{\nu(t+1)}$, it holds that

$\epsilon_{\emph{stab}}\leq\frac{2B^{2}}{mn\nu}+4(1+\frac{B}{\nu})\frac{B^{2}}{\nu}\frac{1_{\lambda\neq
0}}{1-\lambda}.$

The uniformly stability bound for SGD with strong convexity is
${2B^{2}}/{(mn\nu)}$ (Hardt, Recht, and Singer 2016), which is smaller than
the one of D-SGD. From Theorem 2, we see that the uniform stability bound of
D-SGD is independent on the iterative number $T$. Moreover, D-SGD enjoys a
smaller uniformly stable bound when the data size $mn$ is larger and $\lambda$
is smaller.

### Nonconvexity

We now present the stability result for nonconvex loss functions.

###### Theorem 3

Suppose Assumptions 1, 2, 3 hold and $\sup_{{\bf x}\in V,\xi}f({\bf
x};\xi)\leq 1$. For any $T$, if the step size $\alpha_{t}\leq{c}/{(t+1)}$ and
$c$ is small enough, then D-SGD satisfies the uniform stability with

$\displaystyle\epsilon_{\emph{stab}}$
$\displaystyle\leq\frac{c^{\frac{1}{1+cL}}T^{\frac{cL}{1+cL}}}{mn}$
$\displaystyle+c^{\frac{1}{1+cL}}\Big{[}\frac{2B^{2}cL}{mn}+4(1+cB)B^{2}LC_{\lambda}\Big{]}T^{\frac{cL}{1+cL}}.$

Without the convexity assumption, the uniform stable bound of D-SGD
deteriorated. Theorem 3 shows that
$\epsilon_{\textrm{stab}}=\mathcal{O}((1+C_{\lambda}){T^{\frac{cL}{1+cL}}}/{(mn)})$,
which is much larger than the bounds in the convex case
$\left(\mathcal{O}({\ln T}/{(mn)}+C_{\lambda}\ln T)\right)$.

(a) Linear regression  (b) Regularized logistic regression  (c) ResNet-20
classification on Cifar-10

Figure 2: Comparison of the absolute loss difference under different graphs.
(a), (b) and (c) correspond to the general convex, strongly convex, and
nonconvex cases, respectively. In the strongly convex case, the curves become
stable after enough iterations for all graphs. In the general convex case, the
absolute loss difference oscillates and inferior to the strongly convex case.
D-SGD performs worst in the nonconvex tests in terms of stability.

## Excess Generalization for Convex Problems

In the nonconvex case, the optimization error of the function value is
unclear. Thus, the excess generalization error is absent. We are also
interested in the excess generalization associated with the computational
optimization error. The existing computational errors of Algorithm 1 require
extra assumptions on the graph for projections. However, these assumptions may
fail to hold in many applications. Thus, we first present the optimization
error of D-SGD when $f({\bf x};\xi)$ is convex without extra assumptions.

### Optimization Error of Convex D-SGD

This part consists of optimization errors of D-SGD for convex and strongly
convex settings. Assume ${\bf x}^{*}$ is the minimizer of $f({\bf x})$ over
the set $V$, i.e., $f({\bf x}^{*})=\min_{{\bf x}\in V}f({\bf x})$.

###### Lemma 3

Let $f(\cdot;\xi)$ be convex and Assumptions 1, 2 hold, and let $({\bf
x}^{t})_{1\leq t\leq T}$ be the sequence generated by D-SGD. Then

$\displaystyle\mathbb{E}(f(\emph{ave}({\bf x}^{T}))-f({\bf
x}^{*}))\leq\frac{\|{\bf x}^{1}-{\bf
x}^{*}\|^{2}}{\sum_{t=1}^{T-1}\alpha_{t}}+\frac{2B^{2}\sum_{t=1}^{T-1}\alpha_{t}^{2}}{m\sum_{t=1}^{T-1}\alpha_{t}}$
$\displaystyle+8LrBM(T)+2\lambda^{2}B^{2}M(T)^{2},$

where $M(T):=\max_{1\leq t\leq
T-1}\\{\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j}\\}$ and $r$ is the radius of
$V$.

It is worth mentioning that the optimization error is established on the
average point $\textrm{ave}({\bf x}^{T})$ for technical reasons.

In the following, we provide the results for the strongly convex setting.

###### Lemma 4

Let $f(\cdot;\xi)$ be $\nu$-strongly convex and Assumptions 1, 2, 3 hold, and
let $V$ be a closed ball with radius $r>0$, and let $({\bf x}^{t})_{1\leq
t\leq T}$ be the sequence generated by D-SGD. When $\alpha_{t}\equiv\alpha>0$,
then

$\displaystyle\mathbb{E}\|{\bf x}^{T}-{\bf
x}^{*}\|^{2}\leq(1-2\alpha\nu)^{T-1}\|{\bf x}^{1}-{\bf x}^{*}\|^{2}$
$\displaystyle+(\frac{4\alpha
LrB}{(1-\lambda)\nu}+\frac{\lambda^{2}B^{2}\alpha}{m(1-\lambda)^{2}\nu})1_{\lambda\neq
0},$

where $1_{\lambda\neq 0}=1$ when $\lambda\neq 0$, and $1_{\lambda\neq 0}=0$
when $\lambda=0$. When $\alpha_{t}={1}/{(2\nu(t+1))}$, it then follows

$\mathbb{E}\|{\bf x}^{T}-{\bf x}^{*}\|^{2}\leq\frac{\|{\bf x}^{1}-{\bf
x}^{*}\|^{2}}{T-1}+\frac{D_{\lambda}\ln T}{T-1},$

where
$D_{\lambda}:=\frac{B^{2}}{2\nu^{2}}+\frac{\lambda^{2}B^{2}C_{\lambda}^{2}}{2\nu^{2}m}+\frac{2LrBC_{\lambda}}{\nu^{2}}$
and

$C_{\lambda}:=\left\\{\begin{array}[]{c}\ln\frac{1}{\lambda}\frac{\lambda^{\ln\frac{1}{\lambda}}}{\lambda}+\frac{\ln^{2}\frac{1}{\lambda}}{16\lambda}\lambda^{\frac{\ln\frac{1}{\lambda}}{8}}+\frac{2}{\lambda\ln\frac{1}{\lambda}}~{}~{}\lambda\neq
0,\\\ 0,~{}~{}\lambda=0.\\\ \end{array}\right.$

The result shows that D-SGD with projection converges sublinearly in the
strongly convex case. To reach an $\epsilon>0$ error, we shall set the
iteration number as $\widetilde{\mathcal{O}}({1}/{\epsilon})$. Our result
coincides with the existing convergence results of SGD with strong convexity
(Rakhlin, Shamir, and Sridharan 2012). What is different is that D-SGD is
affected by the parameter $\lambda$, which is determined by the structure of
the connected graph222For the strongly convex case, we avoid showing the
result under general step size due to the complicated form..

### General Convexity

Notice that the computational error of D-SGD, in this case, is described by
$\textrm{ave}({\bf x}^{T})$. Thus, we need to estimate the generalization
bound about $\textrm{ave}({\bf x}^{T})$.

###### Theorem 4

Let $f(\cdot;\xi)$ be convex and Assumptions 1, 2, 3 hold. If the step size
$\alpha_{t}\equiv\alpha\leq{2}/{L}$, then the average output (5) obeys the
following generalization bound

$\displaystyle\epsilon_{\emph{ex-
gen}}\leq\frac{2B^{2}\alpha(t-1)}{mn}+\frac{4\alpha B^{2}(1+\alpha
B)(t-1)}{1-\lambda}1_{\lambda\neq 1}$
$\displaystyle+\frac{4r^{2}}{(T-1)\alpha}+\frac{2B^{2}\alpha}{m}+\frac{8LrB\alpha}{1-\lambda}1_{\lambda\neq
1}+\frac{2\lambda^{2}B^{2}\alpha^{2}}{(1-\lambda)^{2}}.$

Furthermore, if the step size is chosen as $\alpha_{t}={1}/{(t+1)}$, we have

$\displaystyle\epsilon_{\emph{ex-gen}}\leq\frac{B^{2}\ln
T}{mn}+\frac{4B^{2}(1+B)}{\ln(T+1)}1_{\lambda\neq
1}+2\lambda^{2}B^{2}C_{\lambda}^{2}$
$\displaystyle+\frac{4r^{2}}{\ln(T+1)}+\frac{4B^{2}}{m\ln(T+1)}+8LrBC_{\lambda}1_{\lambda\neq
1}.$

(a) Random  (b) Star  (c) Cycle (d) k-NNG (e) Bipartite (f) Complete

Figure 3: Absolute loss difference versus epochs for linear regression task on
Body Fat dataset. With current learning rates, D-SGD diverges for the Cycle
graph. With enough iterations, the smaller learning rate can achieves a
smaller difference for all graph.

(a) Random  (b) Star  (c) Cycle (d) k-NNG (e) Bipartite (f) Complete

Figure 4:  Absolute loss difference versus epochs for the $\ell_{2}$
regularized logistic regression task on ijcnn1. The strongly convex tests are
similar to general convex ones but more smooth. With strong convexity, D-SGD
converges over the Cycle graph. In particular, when a smaller learning rate is
used.

(a) Random  (b) Star  (c) Cycle (d) k-NNG (e) Bipartite (f) Complete

Figure 5:  Absolute loss difference versus epochs for training nonconvex
machine learning model, i.e., ResNet20. Unlike the convex cases, the absolute
loss difference oscillates chaotically, which implies worse stability.

### Strong Convexity

Now, we present the excess generalization of D-SGD under strong convexity.

###### Theorem 5

Let $f(\cdot;\xi)$ be $\nu$-strongly convex and Assumptions 1, 2, 3 hold. If
the step size $\alpha_{t}\equiv\alpha\leq{1}/{L}$, the excess generalization
bound is

$\displaystyle\epsilon_{\emph{ex-
gen}}\leq\frac{2B^{2}}{mn\nu}+\frac{4(1+\alpha
B)B^{2}}{\nu}\frac{1_{\lambda\neq 0}}{1-\lambda}$
$\displaystyle+B\sqrt{(1-2\alpha\nu)^{T-1}4r^{2}+(\frac{4\alpha
LrB}{(1-\lambda)\nu}+\frac{\lambda^{2}B^{2}\alpha}{m(1-\lambda)^{2}\nu})1_{\lambda\neq
0}}.$

Furthermore, if the step size $\alpha_{t}={1}/{(\nu(t+1))}$, the excess
generalization bound is

$\displaystyle\epsilon_{\emph{ex-gen}}$
$\displaystyle\leq\frac{2B^{2}}{mn\nu}+\frac{4(\nu+B)B^{2}}{\nu^{2}}\frac{1_{\lambda\neq
0}}{1-\lambda}+B\sqrt{\frac{4r^{2}}{T-1}+\frac{D_{\lambda}\ln T}{T-1}}.$

## Numerical Results

We numerically verify our theoretical findings in this section, with a focus
on testing three kinds of models, namely, strongly convex, convex, and
nonconvex. For all the above three scenarios, we set the number of nodes $m$
to 10 and conduct two kinds of experiments: the first kind of experiments is
to verify the stability and generalization results. Given a fixed graph, we
use two sets of samples that are of the same amount, and the entries are
differing by a small portion. We compare the training loss and training
accuracy of D-SGD on these two datasets; the second kind is to demonstrate the
effects due to the structure of the connected graph. We run our experiments on
different types of connected graphs with the same dataset. In particular, we
test six different connected graphs, as shown in Figure 1.

### Convex case

We consider the following optimization problem

$\min_{{\bf x}\in\mathbb{R}^{14}}\Phi({\bf
x}):=\frac{1}{504}\sum_{i=1}^{252}\|\xi_{i}^{\top}{\bf x}-{\bf y}_{i}\|^{2},$

which arises from a simple regression problem. Here, we use the Body Fat
dataset (Johnson 1996) which contains 252 samples. We run D-SGD on two subsets
of the Body Fat dataset, and both of size 200. Let ${\bf x}^{k}$ and
$\widehat{{\bf x}}^{k}$ be the outputs of the D-SGD on the two different
subsets. We define the absolute loss difference as $|\Phi({\bf
x}^{k})-\Phi(\widehat{{\bf x}}^{k})|.$ For the above six graphs, we record the
absolute difference in the value of function $\Phi$ for a set of learning
rate, namely, $\\{0.001,0.004,0.016,0.064\\}$ in Figure 3. In the second test,
we use the learning rate $0.001$ and compare the absolute loss difference with
different graphs in Figure 2 (a). Our results show that the smaller learning
rate usually yields a smaller loss difference, and the complete graph can
achieve the smallest bound. These observations are consistent with our
theoretical results for the convex D-SGD.

### Strongly convex case

To verify our theory on the strongly convex case, we consider the regularized
logistic regression model as follows

$\min_{{\bf
x}\in\mathbb{R}^{22}}\left\\{\frac{1}{9000}\sum_{i=1}^{9000}\left(\log(1+\textrm{exp}(-b_{i}{\bf
a}^{\top}_{i}{\bf x}))+\frac{\lambda}{2}\|{\bf x}\|^{2}\right)\right\\}.$

We use the benchmark ijcnn1 dataset(Rennie and Rifkin 2001) and set
$\lambda=10^{-4}$. Two 8000-sample sub-datasets with 1000 different samples
are used as the test set. We conduct experiments on the two datasets with the
same set of learning rates that are used in the last subsection. The absolute
loss difference under different learning rates is plotted in Figure 4, and the
performance under different graphs is reported in Figure 2 (b). The results of
D-SGD in the strongly convex case is similar to the convex case. Also, note
that the absolute loss difference increases as the learning rates grow.

### Nonconvex case

We test ResNet-20 (He et al. 2016) for CIFAR10 classification (Krizhevsky
2009). We adopt two different 40000-sample subsets. The loss values are built
on the test set. The absolute loss difference with the learning rate set
$\\{0.0001,0.0004,0.0016,0.0064\\}$ versus the epochs is presented in Figure
5, and the absolute loss difference with different graphs are shown in Figure
5 (c). 100 epochs are used in the nonconvex test. The results show that the
nonconvex D-SGD is much more unstable than the convex ones, which matches our
theoretical findings.

## Conclusion

In this paper, we develop the stability and generalization error for the
(projected) decentralized stochastic gradient descent (D-SGD) in strongly
convex, convex, and nonconvex settings. In contrast to the previous works on
the analysis of the projected decentralized gradient descent, our theories are
built on much more relaxed assumptions. Our theoretical results show that the
stability and generalization of D-SGD depend on the learning rate and the
structure of the connected graph. Furthermore, we prove that decentralization
deteriorates the stability of D-SGD. Our theoretical results are empirically
supported by experiments on training different machine learning models in
different decentralization settings. There are numerous avenues for future
work: 1) deriving the improved stability and generalization bounds of D-SGD in
the general convex and nonconvex cases, 2) proving the high probability
bounds, 3) studying the stability and generalization bound of the moment
variance of D-SGD.

## References

  * Agarwal and Duchi (2011) Agarwal, A., and Duchi, J. C.  2011\.  Distributed delayed stochastic optimization.  In Advances in Neural Information Processing Systems, 873–881.
  * Bottou and Bousquet (2008) Bottou, L., and Bousquet, O.  2008\.  The tradeoffs of large scale learning.  In Advances in neural information processing systems, 161–168.
  * Bousquet and Elisseeff (2002) Bousquet, O., and Elisseeff, A.  2002\.  Stability and generalization.  Journal of machine learning research 2(Mar):499–526.
  * Boyd et al. (2005) Boyd, S.; Ghosh, A.; Prabhakar, B.; and Shah, D.  2005\.  Gossip algorithms: Design, analysis and applications.  In Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies., volume 3, 1653–1664.  IEEE.
  * Boyd, Diaconis, and Xiao (2004) Boyd, S.; Diaconis, P.; and Xiao, L.  2004\.  Fastest mixing markov chain on a graph.  SIAM review 46(4):667–689.
  * Charles and Papailiopoulos (2018) Charles, Z., and Papailiopoulos, D.  2018\.  Stability and generalization of learning algorithms that converge to global optima.  In International Conference on Machine Learning, 745–754.
  * Dekel et al. (2012) Dekel, O.; Gilad-Bachrach, R.; Shamir, O.; and Xiao, L.  2012\.  Optimal distributed online prediction using mini-batches.  The Journal of Machine Learning Research 13:165–202.
  * Duchi, Hazan, and Singer (2011) Duchi, J.; Hazan, E.; and Singer, Y.  2011\.  Adaptive subgradient methods for online learning and stochastic optimization.  Journal of machine learning research 12(7).
  * Elisseeff, Evgeniou, and Pontil (2005) Elisseeff, A.; Evgeniou, T.; and Pontil, M.  2005\.  Stability of randomized learning algorithms.  Journal of Machine Learning Research 6(Jan):55–79.
  * Hardt, Recht, and Singer (2016) Hardt, M.; Recht, B.; and Singer, Y.  2016\.  Train faster, generalize better: Stability of stochastic gradient descent.  ICML 2016.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J.  2016\.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, 770–778.
  * Johnson (1996) Johnson, R. W.  1996\.  Fitting percentage of body fat to simple body measurements.  Journal of Statistics Education 4(1).
  * Karimi, Nutini, and Schmidt (2016) Karimi, H.; Nutini, J.; and Schmidt, M.  2016\.  Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 795–811.  Springer.
  * Kingma and Ba (2014) Kingma, D. P., and Ba, J.  2014\.  Adam: A method for stochastic optimization.  ICLR.
  * Kuzborskij and Lampert (2018) Kuzborskij, I., and Lampert, C.  2018\.  Data-dependent stability of stochastic gradient descent.  In International Conference on Machine Learning, 2815–2824.
  * Lan, Lee, and Zhou (2020) Lan, G.; Lee, S.; and Zhou, Y.  2020\.  Communication-efficient algorithms for decentralized and stochastic optimization.  Mathematical Programming 180(1):237–284.
  * LeCun, Bengio, and Hinton (2015) LeCun, Y.; Bengio, Y.; and Hinton, G.  2015\.  Deep learning.  nature 521(7553):436–444.
  * Lei and Ying (2020) Lei, Y., and Ying, Y.  2020\.  Fine-grained analysis of stability and generalization for sgd.  In Proceedings of the 37th International Conference on Machine Learning, 2020.
  * Li, Luo, and Qiao (2019) Li, J.; Luo, X.; and Qiao, M.  2019\.  On generalization error bounds of noisy gradient methods for non-convex learning.  Proceedings of Machine Learning Research 1:37.
  * Lian et al. (2017) Lian, X.; Zhang, C.; Zhang, H.; Hsieh, C.-J.; Zhang, W.; and Liu, J.  2017\.  Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent.  In Advances in Neural Information Processing Systems, 5330–5340.
  * Lian et al. (2018) Lian, X.; Zhang, W.; Zhang, C.; and Liu, J.  2018\.  Asynchronous decentralized parallel stochastic gradient descent.  In International Conference on Machine Learning, 3043–3052.
  * Lin, Camoriano, and Rosasco (2016) Lin, J.; Camoriano, R.; and Rosasco, L.  2016\.  Generalization properties and implicit regularization for multiple passes sgm.  In International Conference on Machine Learning, 2340–2348.
  * Marshall, Olkin, and Arnold (1979) Marshall, A. W.; Olkin, I.; and Arnold, B. C.  1979\.  Inequalities: theory of majorization and its applications, volume 143.  Springer.
  * Montenegro and Tetali (2006) Montenegro, R. R., and Tetali, P.  2006\.  Mathematical aspects of mixing times in Markov chains.  Now Publishers Inc.
  * Mou et al. (2018) Mou, W.; Wang, L.; Zhai, X.; and Zheng, K.  2018\.  Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints.  In Conference on Learning Theory, 605–638.
  * Nedic and Ozdaglar (2009) Nedic, A., and Ozdaglar, A.  2009\.  Distributed subgradient methods for multi-agent optimization.  IEEE Transactions on Automatic Control 54(1):48–61.
  * Nemirovski et al. (2009) Nemirovski, A.; Juditsky, A.; Lan, G.; and Shapiro, A.  2009\.  Robust stochastic approximation approach to stochastic programming.  SIAM Journal on optimization 19(4):1574–1609.
  * Olfati-Saber, Fax, and Murray (2007) Olfati-Saber, R.; Fax, J. A.; and Murray, R. M.  2007\.  Consensus and cooperation in networked multi-agent systems.  Proceedings of the IEEE 95(1):215–233.
  * Rakhlin, Shamir, and Sridharan (2012) Rakhlin, A.; Shamir, O.; and Sridharan, K.  2012\.  Making gradient descent optimal for strongly convex stochastic optimization.  In Proceedings of the 29th International Coference on International Conference on Machine Learning, 1571–1578.
  * Ram, Nedić, and Veeravalli (2010a) Ram, S. S.; Nedić, A.; and Veeravalli, V. V.  2010a.  Asynchronous gossip algorithm for stochastic optimization: Constant stepsize analysis.  In Recent Advances in Optimization and its Applications in Engineering. Springer.  51–60.
  * Ram, Nedić, and Veeravalli (2010b) Ram, S. S.; Nedić, A.; and Veeravalli, V. V.  2010b.  Distributed stochastic subgradient projection algorithms for convex optimization.  Journal of optimization theory and applications 147(3):516–545.
  * Recht et al. (2011) Recht, B.; Re, C.; Wright, S.; and Niu, F.  2011\.  Hogwild: A lock-free approach to parallelizing stochastic gradient descent.  In Advances in neural information processing systems, 693–701.
  * Rennie and Rifkin (2001) Rennie, J. D., and Rifkin, R.  2001\.  Improving multiclass text classification with the support vector machine.
  * Richards and others (2020) Richards, D., et al.  2020\.  Graph-dependent implicit regularisation for distributed stochastic subgradient descent.  Journal of Machine Learning Research 21(2020).
  * Robbins and Monro (1951) Robbins, H., and Monro, S.  1951\.  A stochastic approximation method.  The annals of mathematical statistics 400–407.
  * Shalev-Shwartz et al. (2010) Shalev-Shwartz, S.; Shamir, O.; Srebro, N.; and Sridharan, K.  2010\.  Learnability, stability and uniform convergence.  The Journal of Machine Learning Research 11:2635–2670.
  * Sirb and Ye (2016) Sirb, B., and Ye, X.  2016\.  Consensus optimization with delayed and stochastic gradients on decentralized networks.  In 2016 IEEE International Conference on Big Data (Big Data), 76–85.  IEEE.
  * Srivastava and Nedic (2011) Srivastava, K., and Nedic, A.  2011\.  Distributed asynchronous constrained stochastic optimization.  IEEE Journal of Selected Topics in Signal Processing 5(4):772–790.
  * Sun et al. (2019) Sun, T.; Chen, T.; Sun, Y.; Liao, Q.; and Li, D.  2019\.  Decentralized markov chain gradient descent.  arXiv preprint arXiv:1909.10238.
  * Wang et al. (2020) Wang, B.; Nguyen, T. M.; Sun, T.; Bertozzi, A. L.; Baraniuk, R. G.; and Osher, S. J.  2020\.  Scheduled restart momentum for accelerated stochastic gradient descent.  arXiv preprint arXiv:2002.10583.
  * Yuan, Ling, and Yin (2016) Yuan, K.; Ling, Q.; and Yin, W.  2016\.  On the convergence of decentralized gradient descent.  SIAM Journal on Optimization 26(3):1835–1854.
  * Krizhevsky (2009) Krizhevsky, A.  2009\.  Learning Multiple Layers of Features from Tiny Images.  Technical Report.

Supplementary materials for

Stability and Generalization Bounds of Decentralized Stochastic Gradient
Descent

##  Appendix A More results of the test

We present the absolute accuracy difference in the decentralized neutral
networks training.

(a) Random  (b) Star  (c) Cycle (d) k-NNG (e) Bipartite (f) Complete

Figure 6: Absolute accuracy difference versus epochs for nonconvex model. The
absolute accuracy difference performs similarly to the absolute loss
difference.

##  Appendix B Technical Lemmas

###### Lemma 5

For any $0<\lambda<1$ and $t\in\mathbb{Z}^{+}$, it holds

$\sum_{j=0}^{t-1}\frac{\lambda^{t-1-j}}{j+1}\leq\frac{C_{\lambda}}{t}$

with
$C_{\lambda}:=\ln\frac{1}{\lambda}\frac{\lambda^{\ln\frac{1}{\lambda}}}{\lambda}+\frac{\ln^{2}\frac{1}{\lambda}}{16\lambda}\lambda^{\frac{\ln\frac{1}{\lambda}}{8}}+\frac{2}{\lambda\ln\frac{1}{\lambda}}$.

###### Lemma 6

[Lemmas 2.5 and 3.7, (Hardt, Recht, and Singer 2016)] Fix an arbitrary
sequence of updates $G_{1},\dots,G_{T}$ and another sequence
$G_{1}^{\prime},\dots,G_{T}^{\prime}.$ Let ${\bf x}^{0}={\bf y}^{0}$ be a
starting point in $V$ and define $\delta_{t}=\|{\bf x}^{t}-{\bf y}^{t}\|$
where ${\bf x}^{t},{\bf y}^{t}$ are defined recursively through

$\displaystyle{\bf x}^{t+1}=G_{t}({\bf x}^{t}),\,\,~{}~{}\,~{}~{}{\bf
y}^{t+1}=G_{t}^{\prime}({\bf y}^{t}).$

Then, we have the recurrence relation $\delta_{0}=0$,

$\displaystyle\delta_{t+1}$
$\displaystyle\leq\begin{cases}\eta\delta_{t}&\text{$G_{t}=G_{t}^{\prime}$ is
$\eta$-expansive}\\\ \min(\eta,1)\delta_{t}+2\sigma_{t}&\text{$G_{t}$ and
$G_{t}^{\prime}$ are $\sigma$-bounded,}\,\text{$G_{t}$ is $\eta$
expansive.}\end{cases}$

For a nonnegative step size $\alpha\geq 0$ and a function $f\colon
V\to\mathbb{R},$ we define $G_{f,\alpha}$ as

$G_{f,\alpha}({\bf x})=\textbf{\emph{Proj}}_{V}({\bf x}-\alpha\nabla f({\bf
x})),$

where $V$ is a closed convex set. Assume that $f$ is $L$-smooth. Then, the
following properties hold.

  * •

$G_{f,\alpha}$ is $(1+\alpha L)$-expansive.

  * •

If $f$ is convex. Then, for any $\alpha\leq 2/L,$ the gradient update
$G_{f,\alpha}$ is $1$-expansive.

  * •

If $f$ is $\nu$-strongly convex. Then, for $\alpha\leq\frac{1}{L}$,
$G_{f,\alpha}$ is $\left(1-\alpha\nu\right)$-expansive.

###### Lemma 7

Let Assumption 1 hold. Assume two sample sets $S$ and $S^{\prime}$ just
differs at one sample in the first $n$ sample. And let ${\bf x}^{T}$ and ${\bf
y}^{T}$ be the corresponding outputs of D-SGD applied to these two sets after
$T$ steps. Then, for every $\xi\sim\mathcal{D}$ and every
$t_{0}\in\\{0,1,\dots,n\\},$ under both the random update rule and the random
permutation rule, we have

$\mathbb{E}\left|f({\bf x}^{T};\xi)-f({\bf
y}^{T};\xi)\right|\leq\frac{t_{0}}{n}\sup_{{\bf x}\in V,\xi}f({\bf
x};\xi)+B\mathbb{E}\left[\delta_{T}\mid\delta_{t_{0}}=0\right].$

###### Lemma 8

Given the stepsize $(\alpha_{t})_{t\geq 0}>0$ and assume $({\bf
x}^{t}(i))_{t\geq 0}$ are generated by D-SGD for all $i\in\\{1,2\ldots,m\\}$.
If Assumption 3 holds, we have the following bound

$\displaystyle\left[\sum_{i=1}^{m}\|{\bf x}^{t}(i)-{\bf
x}^{t}\|^{2}\right]^{\frac{1}{2}}\leq
2\sqrt{m}B\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j}.$ (6)

###### Lemma 9

Denote the matrix ${\bf X}^{t}:=\begin{bmatrix}{\bf x}^{t}(1),{\bf
x}^{t}(2),\ldots,{\bf x}^{t}(m)\end{bmatrix}^{\top}\in\mathbb{R}^{m\times d}$.
Assume the conditions of Lemma 8 hold, we then get

$\displaystyle\|({\bf W}-{\bf P}){\bf
X}^{t}\|\leq\sqrt{m}B\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-j}.$ (7)

##  Appendix C Proofs of Technical Lemmas

### Proof of Lemma 5

For any $x\in[j,j+1]$, $j+1\geq x$ and $\lambda^{t-1-j}\leq\lambda^{t-1-x}$,
we then get

$\displaystyle\sum_{j=0}^{t-1}\frac{\lambda^{t-1-j}}{j+1}=\lambda^{t-1}+\sum_{j=1}^{t-1}\frac{\lambda^{t-1-j}}{j+1}\leq\lambda^{t-1}+\sum_{j=1}^{t-1}\int_{j}^{j+1}\frac{\lambda^{t-1-x}}{x}dx$
(8)
$\displaystyle=\lambda^{t-1}+\lambda^{t-1}\int_{1}^{t}\frac{\lambda^{-x}}{x}dx.$

We turn to the bound

$\begin{aligned}
&\int_{1}^{t}\frac{\lambda^{-x}}{x}dx=\int_{1}^{\frac{t}{2}}\frac{\lambda^{-x}}{x}dx+\int_{\frac{t}{2}}^{t}\frac{\lambda^{-x}}{x}dx\\\
&\leq\lambda^{-\frac{t}{2}}\int_{1}^{\frac{t}{2}}\frac{1}{x}dx+\frac{2}{t}\int_{\frac{t}{2}}^{t}\lambda^{-x}dx\leq\lambda^{-\frac{t}{2}}\ln
t+\frac{2\lambda^{-t}}{t\ln\frac{1}{\lambda}}\end{aligned}.$

With (8), we are then led to

$\displaystyle\sum_{j=0}^{t-1}\frac{\lambda^{t-1-j}}{j+1}\leq\lambda^{t-1}+\lambda^{\frac{t}{2}-1}t+\frac{2}{t\lambda\ln\frac{1}{\lambda}},$

where we used the fact $\ln t\leq t$. Now, we provide the bounds for
$\sup_{t\geq
1}\\{t\lambda^{t-1}+\lambda^{\frac{t}{2}-1}t^{2}\\}\leq\sup_{t\geq
1}\\{t\lambda^{t-1}\\}+\sup_{t\geq 1}\\{\lambda^{\frac{t}{2}-1}t^{2}\\}$. Note
that $\ln(t\lambda^{t-1})=\ln t+(t-1)\ln\lambda$, whose derivative is
$\frac{1}{t}+\ln\lambda$. It is easy to check that $t=\ln\frac{1}{\lambda}$
achieves the maximum, which indicates

$\sup_{t\geq
1}\\{t\lambda^{t-1}\\}\leq\ln\frac{1}{\lambda}\frac{\lambda^{\ln\frac{1}{\lambda}}}{\lambda}.$

Similarly, we get

$\sup_{t\geq
1}\\{\lambda^{\frac{t}{2}-1}t^{2}\\}\leq\frac{\ln^{2}\frac{1}{\lambda}}{16\lambda}\lambda^{\frac{\ln\frac{1}{\lambda}}{8}}.$

### Proof of Lemma 7

Proof of Lemma 7 is almost identical to the proof of Lemma 3.11 in (Hardt,
Recht, and Singer 2016).

### Proof of Lemma 8

We denote that

${\bf\zeta}^{t}:=\alpha_{t}\begin{bmatrix}\nabla f({\bf
x}^{t}(1);\xi_{j_{t}(1)}),\nabla f({\bf
x}^{t}(2);\xi_{j_{t}(2)}),\ldots,\nabla f({\bf
x}^{t}(m);\xi_{j_{t}(m)})\end{bmatrix}^{\top}\in\mathbb{R}^{m\times d}.$

With Assumption 1, $\|{\bf\zeta}^{t}\|\leq\alpha_{t}\sqrt{m}B$. Then the
global scheme can be presented as

$\displaystyle{\bf X}^{t+1}=\textbf{Proj}_{V^{m}}\Big{[}{\bf W}{\bf
X}^{t}-{\bf\zeta}^{t}\Big{]},$ (9)

where $V^{m}:=\underbrace{V\oplus V\ldots\oplus V}_{m}$. Noticing the fact

${\bf W}{\bf P}={\bf P}{\bf W}={\bf P}.$ (10)

With Lemma 2, we have

$\|{\bf W}-{\bf P}\|_{\textrm{op}}\leq\lambda.$

Multiplication of both sides of (9) with ${\bf P}$ together with (10) then
tells us

$\displaystyle(\mathbb{I}-{\bf P}){\bf X}^{t+1}=(\mathbb{I}-{\bf
P})\textbf{Proj}_{V^{m}}\Big{[}{\bf W}{\bf X}^{t}-{\bf\zeta}^{t}\Big{]}$ (11)
$\displaystyle=\textbf{Proj}_{V^{m}}\Big{[}{\bf W}{\bf
X}^{t}-{\bf\zeta}^{t}\Big{]}-{\bf P}\cdot\textbf{Proj}_{V^{m}}\Big{[}{\bf
W}{\bf X}^{t}\Big{]}+{\bf P}\cdot\textbf{Proj}_{V^{m}}\Big{[}{\bf W}{\bf
X}^{t}\Big{]}-{\bf P}\cdot\textbf{Proj}_{V^{m}}\Big{[}{\bf W}{\bf
X}^{t}-{\bf\zeta}^{t}\Big{]}.$

It is easy to check that ${\bf W}{\bf X}^{t}\in V^{m}$ and ${\bf P}{\bf W}{\bf
X}^{t}\in V^{m}$. Thus, it follows ${\bf
P}\cdot\textbf{Proj}_{V^{m}}\Big{[}{\bf W}{\bf X}^{t}\Big{]}={\bf P}{\bf
W}{\bf X}^{t}=\textbf{Proj}_{V^{m}}\Big{[}{\bf P}{\bf W}{\bf X}^{t}\Big{]}$.
From (11), letting $\mathbb{I}\in\mathbb{R}^{m}$ be the identical matrix,

$\displaystyle\|(\mathbb{I}-{\bf P}){\bf
X}^{t+1}\|\leq\left\|\textbf{Proj}_{V^{m}}\Big{[}{\bf W}{\bf
X}^{t}-{\bf\zeta}^{t}\Big{]}-\textbf{Proj}_{V^{m}}\Big{[}{\bf P}{\bf W}{\bf
X}^{t}\Big{]}\right\|+\|{\bf\zeta}^{t}\|$ (12) $\displaystyle\qquad\leq\|{\bf
W}{\bf X}^{t}-{\bf\zeta}^{t}-{\bf P}{\bf W}{\bf
X}^{t}\|+\sqrt{m}B\alpha_{t}\leq\|{\bf W}{\bf X}^{t}-{\bf P}{\bf W}{\bf
X}^{t}\|+2\sqrt{m}B\alpha_{t}$ $\displaystyle\qquad\overset{a)}{\leq}\|({\bf
W}-{\bf P})(\mathbb{I}-{\bf P}){\bf
X}^{t}\|+2\sqrt{m}B\alpha_{t}\overset{b)}{\leq}\lambda\|(\mathbb{I}-{\bf
P}){\bf X}^{t}\|+2\sqrt{m}B\alpha_{t}.$

where $a)$ uses the fact $({\bf W}-{\bf P})(\mathbb{I}-{\bf P})={\bf W}-2{\bf
P}+{\bf W}{\bf P}={\bf W}-{\bf P}={\bf W}-{\bf P}W$, and $b)$ depends on Lemma
2. Then, we derive

$\displaystyle\|{\bf X}^{t}-{\bf P}{\bf X}^{t}\|\leq
2\sqrt{m}B\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j}.$ (13)

where we used initialization ${\bf X}^{0}=\textbf{0}$.

### Proof of Lemma 9

Direct computations give

$\displaystyle({\bf W}-{\bf P}){\bf X}^{t+1}$ $\displaystyle=({\bf W}-{\bf
P}){\bf W}{\bf X}^{t}-({\bf W}-{\bf P}){\bf\zeta}^{t}$ $\displaystyle=({\bf
W}-{\bf P})({\bf W}-{\bf P}){\bf X}^{t}-({\bf W}-{\bf P}){\bf\zeta}^{t},$

where we used $(W-{\bf P})W=(W-{\bf P})(W-{\bf P})$. Thus, we obtain

$\displaystyle\|(W-{\bf P}){\bf X}^{t+1}\|\leq\lambda\|(W-{\bf P}){\bf
X}^{t}\|+\sqrt{m}\lambda B\alpha_{t},$

##  Appendix D Proof of Theorem 1

Without loss of generalization , assume two sample sets $S$ and $S^{\prime}$
just differs at one sample in the first $m$ sample. And let ${\bf x}^{t}$ and
${\bf y}^{t}$ be the corresponding outputs of D-SGD applied to these two sets.
Denoting that

$\delta_{t}:=\|{\bf x}^{t}-{\bf y}^{t}\|.$

At iteration $t$, with probability $1-\frac{1}{n}$,

$\displaystyle{\bf x}^{t+1}-{\bf y}^{t+1}$
$\displaystyle=\frac{\sum_{i=1}^{m}\left[\textbf{Proj}_{V}[\sum_{l\in\mathcal{N}(i)}w_{i,l}{\bf
x}^{t}(l)-\alpha_{t}\nabla f({\bf
x}^{t}(i);\xi_{j_{t}(i)})]-\textbf{Proj}_{V}[\sum_{l\in\mathcal{N}(i)}w_{i,l}{\bf
y}^{t}(l)-\alpha_{t}\nabla f({\bf y}^{t}(i);\xi_{j_{t}(i)})]\right]}{m}$ (14)
$\displaystyle=\underbrace{\frac{\sum_{i=1}^{m}\left[\textbf{Proj}_{V}[{\bf
x}^{t}-\alpha_{t}\nabla f({\bf x}^{t};\xi_{j_{t}(i)})]-\textbf{Proj}_{V}[{\bf
y}^{t}-\alpha_{t}\nabla f({\bf
y}^{t};\xi_{j_{t}(i)})]\right]}{m}}_{\S}+\wp_{t}.$

With gradient smooth assumption,

$\displaystyle\|\wp_{t}\|$
$\displaystyle\leq\frac{\sum_{i=1}^{m}(\sum_{l\in\mathcal{N}(i)}w_{i,l}\|{\bf
x}^{t}(l)-{\bf x}^{t}\|+\alpha_{t}B\|{\bf x}^{t}(i)-{\bf
x}^{t}\|)}{m}+\frac{\sum_{i=1}^{m}(\sum_{l\in\mathcal{N}(i)}w_{i,l}\|{\bf
y}^{t}(l)-{\bf y}^{t}\|+\alpha_{t}B\|{\bf y}^{t}(i)-{\bf y}^{t}\|)}{m}$ (15)
$\displaystyle\leq\frac{\sum_{i=1}^{m}(\sum_{l=1}^{m}w_{i,l}\|{\bf
x}^{t}(l)-{\bf x}^{t}\|+\alpha_{t}B\|{\bf x}^{t}(i)-{\bf
x}^{t}\|)}{m}+\frac{\sum_{i=1}^{m}(\sum_{l=1}^{m}w_{i,l}\|{\bf y}^{t}(l)-{\bf
y}^{t}\|+\alpha_{t}B\|{\bf y}^{t}(i)-{\bf y}^{t}\|)}{m}$
$\displaystyle\leq\frac{\sum_{l=1}^{m}\|{\bf x}^{t}(l)-{\bf
x}^{t}\|+\alpha_{t}B\sum_{i=1}^{m}\|{\bf x}^{t}(i)-{\bf
x}^{t}\|}{m}+\frac{\sum_{l=1}^{m}\|{\bf y}^{t}(l)-{\bf
y}^{t}\|+\alpha_{t}B\sum_{i=1}^{m}\|{\bf y}^{t}(i)-{\bf y}^{t}\|}{m}$
$\displaystyle\leq\frac{(1+\alpha_{t}B)\sqrt{m}[\sum_{i=1}^{m}\|{\bf
x}^{t}(i)-{\bf
x}^{t}\|^{2}]^{\frac{1}{2}}}{m}+\frac{(1+\alpha_{t}B)\sqrt{m}[\sum_{i=1}^{m}\|{\bf
y}^{t}(i)-{\bf y}^{t}\|^{2}]^{\frac{1}{2}}}{m}$ $\displaystyle\leq
4(1+\alpha_{t}B)B\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j}.$

Due to the convexity, $\textbf{Proj}_{V}[\cdot-\alpha_{t}\nabla
f(\cdot;\xi_{j_{t}(i)})]$ is 1-expansive when $\alpha_{t}\leq\frac{2}{L}$.
Thus, we have

$\|\S\|\leq\|{\bf x}^{t}-{\bf y}^{t}\|=\delta_{t}.$

With probability $\frac{1}{n}$,

$\displaystyle{\bf x}^{t+1}-{\bf y}^{t+1}$
$\displaystyle=\frac{\sum_{i=2}^{m}\left[\textbf{Proj}_{V}[\sum_{l\in\mathcal{N}(i)}w_{i,l}{\bf
x}^{t}(l)-\alpha_{t}\nabla f({\bf
x}^{t};\xi_{j_{t}(i)})]-\textbf{Proj}_{V}[\sum_{l\in\mathcal{N}(i)}w_{i,l}{\bf
y}^{t}(l)-\alpha_{t}\nabla f({\bf y}^{t};\xi_{j_{t}(i)})]\right]}{m}$ (16)
$\displaystyle+\frac{\left[\textbf{Proj}_{V}[\sum_{l\in\mathcal{N}(1)}w_{1,l}{\bf
x}^{t}(l)-\alpha_{t}\nabla f({\bf
x}^{t};\xi^{\prime}_{j_{t}(1)})]-\textbf{Proj}_{V}[\sum_{l\in\mathcal{N}(1)}w_{1,l}{\bf
y}^{t}(l)-\alpha_{t}\nabla f({\bf y}^{t};\xi_{j_{t}(1)})]\right]}{m}+\Im_{t}$
$\displaystyle=\underbrace{\frac{\sum_{i=2}^{m}\left[\textbf{Proj}_{V}[{\bf
x}^{t}-\alpha_{t}\nabla f({\bf x}^{t};\xi_{j_{t}(i)})]-\textbf{Proj}_{V}[{\bf
y}^{t}-\alpha_{t}\nabla f({\bf y}^{t};\xi_{j_{t}(i)})]\right]}{m}}_{\sharp}$
$\displaystyle+\frac{\left[\textbf{Proj}_{V}[{\bf x}^{t}-\alpha_{t}\nabla
f({\bf x}^{t};\xi^{\prime}_{j_{t}(1)})]-\textbf{Proj}_{V}[{\bf
y}^{t}-\alpha_{t}\nabla f({\bf y}^{t};\xi_{j_{t}(1)})]\right]}{m}+\Im_{t}.$

It is easy to check that $\|\Im_{t}\|\leq
4(1+\alpha_{t}B)B\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j}$. With Lemma 6, we
have

$\|\sharp\|\leq\frac{m-1}{m}\delta_{t},~{}\,~{}\,~{}\left\|\frac{\left[\textbf{Proj}_{V}[{\bf
x}^{t}-\alpha_{t}\nabla f({\bf
x}^{t};\xi_{j^{\prime}_{t}(1)})]-\textbf{Proj}_{V}[{\bf
y}^{t}-\alpha_{t}\nabla f({\bf
y}^{t};\xi_{j_{t}(1)})]\right]}{m}\right\|\leq\frac{\delta_{t}+2B\alpha_{t}}{m}.$

Thus, we derive

$\mathbb{E}\delta_{t+1}\leq\mathbb{E}\delta_{t}+\frac{2B\alpha_{t}}{mn}+4(1+\alpha_{t}B)B\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j}.$

That also means

$\mathbb{E}\delta_{T}\leq\frac{2B\sum_{t=0}^{T-1}\alpha_{t}}{mn}+4B\sum_{t=0}^{T-1}(1+\alpha_{t}B)\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j}.$

Noticing the fact

$\mathbb{E}|f({\bf x}^{T};\xi)-f({\bf y}^{T};\xi)|\leq B\mathbb{E}\|{\bf
x}^{T}-{\bf y}^{T}\|=B\mathbb{E}\delta_{T},$ (17)

we then proved the result.

##  Appendix E Proof of Proposition 1

Let ${\bf x}^{t}$ and ${\bf y}^{t}$ be the output of D-SGD with only one
different sample after $t$ iterations. We have

$\displaystyle\|\textrm{ave}({\bf x}^{T})-\textrm{ave}({\bf
y}^{T})\|=\left\|\frac{\sum_{t=1}^{T-1}\alpha_{t}({\bf x}^{t}-{\bf
y}^{t})}{\sum_{t=1}^{T-1}\alpha_{t}}\right\|\leq\frac{\sum_{t=1}^{T-1}\alpha_{t}\|{\bf
x}^{t}-{\bf y}^{t}\|}{\sum_{t=1}^{T-1}\alpha_{t}}.$

As the same proofs in Theorem 1, we can derive

$\|{\bf x}^{t}-{\bf
y}^{t}\|\leq\frac{2B\sum_{k=1}^{t-1}\alpha_{k}}{mn}+4B\sum_{k=1}^{t-1}(1+\alpha_{k}B)\sum_{j=0}^{k-1}\alpha_{j}\lambda^{k-1-j}.$

1) when $\alpha_{t}\equiv\alpha$, we have

$\|{\bf x}^{t}-{\bf y}^{t}\|\leq\frac{2B\alpha(t-1)}{mn}+\frac{4\alpha
B(1+\alpha B)(t-1)}{1-\lambda}1_{\lambda\neq 1}.$

Thus, we get

$\displaystyle\|\textrm{ave}({\bf x}^{T})-\textrm{ave}({\bf
y}^{T})\|\leq\frac{B\alpha(t-1)}{mn}+\frac{2\alpha B(1+\alpha
B)(t-1)}{1-\lambda}1_{\lambda\neq 1}.$

2) when $\alpha_{t}=\frac{1}{t+1}$, we have

$\|{\bf x}^{t}-{\bf y}^{t}\|\leq\frac{2B\ln t}{mn}+\frac{4\alpha
B(1+B)C_{\lambda}}{t}1_{\lambda\neq 1}.$

Thus, we get

$\displaystyle\|\textrm{ave}({\bf x}^{T})-\textrm{ave}({\bf
y}^{T})\|\leq\frac{B\ln T}{mn}+\frac{4\alpha B(1+B)}{\ln(T+1)}1_{\lambda\neq
1}.$

The Lipschitz continuity of the loss function then proves the result.

##  Appendix F Proof of Theorem 2

Without loss of generalization , we assume $\lambda\neq 0$. Due to the strong
convexity with $\nu$, $\textbf{Proj}_{V}[\cdot-\alpha_{t}\nabla
f(\cdot;\xi_{j_{t}(i)})]$ is $(1-\alpha_{t}\nu)$-contractive when
$\alpha_{t}\leq\frac{1}{L}$. Thus, in (14), it holds

$\|\S\|\leq(1-\alpha_{t}\nu)\|{\bf x}^{t}-\overline{{\bf
x}}^{t}\|=(1-\alpha_{t}\nu)\delta_{t};$

and in (16),

$\|\sharp\|\leq\frac{m-1}{m}(1-\alpha_{t}\nu)\delta_{t},$
$\left\|\frac{\left[\textbf{Proj}_{V}[{\bf x}^{t}-\alpha_{t}\nabla f({\bf
x}^{t};\xi_{j^{\prime}_{t}(1)})]-\textbf{Proj}_{V}[{\bf
y}^{t}-\alpha_{t}\nabla f({\bf
y}^{t};\xi_{j_{t}(1)})]\right]}{m}\right\|\leq\frac{(1-\alpha_{t}\nu)\delta_{t}+2B\alpha_{t}}{m}.$

Therefore, we can get

$\displaystyle\mathbb{E}\delta_{t+1}\leq(1-\alpha_{t}\nu)\mathbb{E}\delta_{t}+\frac{2B\alpha_{t}}{mn}+4(1+\alpha_{t}B)B\sum_{j=0}^{t-1}\lambda^{t-1-j}\alpha_{j}.$
(18)

a) When $0<\lambda<1$,
$\sum_{j=0}^{t-1}\lambda^{t-1-j}\leq\frac{1}{1-\lambda}$ and
$\alpha_{t}\equiv\alpha$. Then we are led to

$\displaystyle\mathbb{E}\delta_{t+1}\leq(1-\alpha\nu)\mathbb{E}\delta_{t}+\frac{2B\alpha}{mn}+4(1+\alpha
B)B\alpha\frac{1}{1-\lambda}.$

The recursion of inequality gives us

$\displaystyle\mathbb{E}\delta_{T}\leq\sum_{t=0}^{T-1}(1-\alpha\nu)^{t}\left[\frac{2B\alpha}{mn}+4(1+\alpha
B)B\alpha\frac{1}{1-\lambda}\right]=\frac{2B}{mn\nu}+\frac{4(1+\alpha
B)B}{\nu}\frac{1}{1-\lambda}.$

Once using (17), we then get the result.

b) In (18), by replacing $\alpha$ with $\alpha_{t}=\frac{1}{\nu(t+1)}$,

$\displaystyle\mathbb{E}\delta_{t+1}\leq(1-\frac{1}{t+1})\mathbb{E}\delta_{t}+\Big{[}\frac{2B}{\nu
mn}+4(1+\frac{B}{\nu})\frac{B}{\nu}\frac{1_{\lambda\neq
0}}{1-\lambda}\Big{]}\frac{1}{t+1}.$ (19)

Thus, we get

$\displaystyle\mathbb{E}\delta_{t}\leq\frac{2B}{\nu
mn}+4(1+\frac{B}{\nu})\frac{B}{\nu}\frac{1_{\lambda\neq 0}}{1-\lambda}.$ (20)

##  Appendix G Proof of Theorem 3

Assume $t_{0}\in\\{1,2,\ldots,n\\}$ to be determined, with Lemma 7,

$\mathbb{E}\left|f({\bf x}^{T};\xi)-f({\bf
y}^{T};\xi)\right|\leq\frac{t_{0}}{n}+L\mathbb{E}\left[\delta_{T}\mid\delta_{t_{0}}=0\right],$

where we used $\sup_{{\bf x}\in V,\xi}f({\bf x};\xi)\leq 1$. In the following,
we consider the case $\delta_{t_{0}}=0$. With Lemma 6, in (14),

$\|\S\|\leq(1+\alpha_{t}L)\|{\bf x}^{t}-{\bf
y}^{t}\|=(1+\alpha_{t}L)\delta_{t};$

and in (16),

$\|\sharp\|\leq\frac{m-1}{m}(1+\alpha_{t}L)\delta_{t},$
$~{}\left\|\frac{\left[\textbf{Proj}_{V}[{\bf x}^{t}-\alpha_{t}\nabla f({\bf
x}^{t};\xi_{j^{\prime}_{t}(1)})]-\textbf{Proj}_{V}[{\bf
y}^{t}-\alpha_{t}\nabla f({\bf
y}^{t};\xi_{j_{t}(1)})]\right]}{m}\right\|\leq\frac{\delta_{t}+2B\alpha_{t}}{m}.$

Therefore, when $t>t_{0}$, we can get

$\displaystyle\mathbb{E}(\delta_{t+1}\mid\delta_{t_{0}}=0)$
$\displaystyle\leq(1-\frac{1}{n})(1+\alpha_{t}L)\mathbb{E}(\delta_{t}\mid\delta_{t_{0}}=0)+\frac{1}{n}\Big{[}\frac{m-1}{m}(1+\alpha_{t}L)+\frac{1}{m}\Big{]}\delta_{t}$
$\displaystyle+\frac{2B\alpha_{t}}{mn}+4(1+\alpha_{t}B)B\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j}$
$\displaystyle=\Big{[}1+(1-\frac{1}{mn})\alpha_{t}L\Big{]}\mathbb{E}(\delta_{t}\mid\delta_{t_{0}}=0)+\frac{2B\alpha_{t}}{mn}+4(1+\alpha_{t}B)B\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j}.$

With $\alpha\leq\frac{c}{t}$ and Lemma 5, we are then led to

$\displaystyle\mathbb{E}(\delta_{t+1}\mid\delta_{t_{0}}=0)$
$\displaystyle\leq\Big{[}1+cL(1-\frac{1}{mn})/t\Big{]}\mathbb{E}(\delta_{t}\mid\delta_{t_{0}}=0)+(\frac{2Bc}{mn}+4(1+cB)BC_{\lambda})/t$
$\displaystyle\leq\exp(cL(1-\frac{1}{mn})/t)\mathbb{E}(\delta_{t}\mid\delta_{t_{0}}=0)+(\frac{2Bc}{mn}+4(1+cB)BC_{\lambda})/t.$

That then yields

$\displaystyle\mathbb{E}(\delta_{T}\mid\delta_{t_{0}}=0)$
$\displaystyle\leq\sum_{t=t_{0}+1}^{T}\Big{[}\exp(\sum_{i=t+1}^{T}cL(1-\frac{1}{mn})/i)\Big{]}(\frac{2Bc}{mn}+4(1+cB)BC_{\lambda})/t$
$\displaystyle\leq\sum_{t=t_{0}+1}^{T}\Big{[}\exp(cL(1-\frac{1}{mn})\ln\frac{T}{t})\Big{]}(\frac{2Bc}{mn}+4(1+cB)BC_{\lambda})/t$
$\displaystyle=(\frac{2Bc}{mn}+4(1+cB)BC_{\lambda})T^{cL(1-\frac{1}{mn})}\sum_{t=t_{0}+1}^{T}\frac{1}{t^{cL(1-\frac{1}{mn})+1}}$
$\displaystyle\leq(\frac{2Bc}{mn}+4(1+cB)BC_{\lambda})T^{cL(1-\frac{1}{mn})}\frac{cL(1-\frac{1}{mn})}{t_{0}^{cL(1-\frac{1}{mn})}}$
$\displaystyle\leq(\frac{2Bc}{mn}+4(1+cB)BC_{\lambda})cL\frac{T^{cL}}{t_{0}^{cL}}$

From Lemma 7, we get

$\mathbb{E}\left|f({\bf x}^{T};\xi)-f({\bf
y}^{T};\xi)\right|\leq\frac{t_{0}}{mn}+BcL(\frac{2Bc}{mn}+4(1+cB)BC_{\lambda})\frac{T^{cL}}{t_{0}^{cL}}.$

Setting $t_{0}=c^{\frac{1}{1+cL}}T^{\frac{cL}{1+cL}}$, when $c$ is small
enough, $t_{0}\leq n$. We then have

$\mathbb{E}\left|f({\bf x}^{T};\xi)-f({\bf
y}^{T};\xi)\right|\leq\frac{c^{\frac{1}{1+cL}}T^{\frac{cL}{1+cL}}}{mn}+BLc^{\frac{1}{1+cL}}(\frac{2Bc}{mn}+4(1+cB)BC_{\lambda})T^{\frac{cL}{1+cL}}.$

##  Appendix H Proof of Lemma 3

Without loss of generalization , we assume $\lambda\neq 0$. With the
projection ${\bf x}^{*}=\textbf{Proj}_{V}({\bf x}^{*})$, it then follows

$\displaystyle\mathbb{E}\|{\bf x}^{t+1}-{\bf x}^{*}\|^{2}$
$\displaystyle\leq\mathbb{E}\left\|\sum_{i=1}^{m}\textbf{Proj}_{V}[\sum_{l\in\mathcal{N}(i)}w_{i,l}{\bf
x}^{t}(l)-\alpha_{t}\nabla f({\bf
x}^{t}(i);\xi_{j_{t}(i)})]/m-\textbf{Proj}_{V}({\bf x}^{*})\right\|^{2}$ (21)
$\displaystyle=\mathbb{E}\left\|\Big{[}\sum_{i=1}^{m}\textbf{Proj}_{V}[\sum_{l\in\mathcal{N}(i)}w_{i,l}{\bf
x}^{t}(l)-\alpha_{t}\nabla f({\bf
x}^{t}(i);\xi_{j_{t}(i)})]-\textbf{Proj}_{V}({\bf
x}^{*})\Big{]}/m\right\|^{2}$ $\displaystyle\leq\frac{1}{m}\mathbb{E}\|{\bf
W}{\bf X}^{t}-{\bf\zeta}^{t}-{\bf X}^{*}\|^{2}=\frac{1}{m}\mathbb{E}\|{\bf
P}{\bf X}^{t}-{\bf X}^{*}-\alpha_{t}{\bf\zeta}^{t}+({\bf W}-{\bf P}){\bf
X}^{t}\|^{2}$ $\displaystyle=\mathbb{E}\|{\bf x}^{t}-{\bf
x}^{*}\|^{2}+\underbrace{\frac{2}{m}\mathbb{E}\langle({\bf W}-{\bf P}){\bf
X}^{t}-{\bf\zeta}^{t},{\bf P}{\bf X}^{t}-{\bf
X}^{*}\rangle}_{\textrm{I}}+\underbrace{\frac{1}{m}\mathbb{E}\|\alpha_{t}{\bf\zeta}^{t}-({\bf
W}-{\bf P}){\bf X}^{t}\|^{2}}_{\textrm{II}},$

where ${\bf X}^{*}:=\begin{bmatrix}{\bf x}^{*},{\bf x}^{*},\ldots,{\bf
x}^{*}\end{bmatrix}^{\top}\in\mathbb{R}^{m\times d}$. Now, we bound I and II:
we first observe

$\displaystyle\langle({\bf W}-{\bf P}){\bf X}^{t},{\bf P}{\bf X}^{t}-{\bf
X}^{*}\rangle=\langle{\bf P}({\bf W}-{\bf P}){\bf X}^{t},{\bf
X}^{t}\rangle-\langle{\bf X}^{t},({\bf W}-{\bf P}){\bf X}^{*}\rangle=0.$

The convexity and Lemma 8 tell us

$\displaystyle\frac{2}{m}\mathbb{E}\langle({\bf W}-{\bf P}){\bf
X}^{t}-{\bf\zeta}^{t},{\bf P}{\bf X}^{t}-{\bf
X}^{*}\rangle\leq\frac{2}{m}\mathbb{E}\langle-{\bf\zeta}^{t},{\bf P}{\bf
X}^{t}-{\bf X}^{*}\rangle+\frac{2}{m}\mathbb{E}\langle({\bf W}-{\bf P}){\bf
X}^{t},{\bf P}{\bf X}^{t}-{\bf X}^{*}\rangle$
$\displaystyle\leq\sum_{i=1}^{m}\frac{2\alpha_{t}}{m}\mathbb{E}\langle-\nabla
f({\bf x}(i)),{\bf x}^{t}-{\bf x}^{*}\rangle$
$\displaystyle\leq\sum_{i=1}^{m}\frac{2\alpha_{t}}{m}\mathbb{E}\langle-\nabla
f({\bf x}^{t}),{\bf x}^{t}-{\bf
x}^{*}\rangle+\sum_{i=1}^{m}\frac{2\alpha_{t}}{m}\mathbb{E}\langle\nabla
f({\bf x}^{t})-\nabla f({\bf x}(i)),{\bf x}^{t}-{\bf x}^{*}\rangle$
$\displaystyle\leq-2\alpha_{t}\mathbb{E}(f({\bf x}^{t})-f({\bf
x}^{*}))+\frac{4\alpha_{t}Lr}{\sqrt{m}}\mathbb{E}(\sum_{i=1}^{m}\|{\bf
x}^{t}-{\bf x}(i)\|^{2})^{\frac{1}{2}}$
$\displaystyle\leq-2\alpha_{t}\mathbb{E}(f({\bf x}^{t})-f({\bf
x}^{*}))+8\alpha_{t}LrB\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j}.$

And with Lemma 9, we have

$\displaystyle\frac{1}{m}\mathbb{E}\|\alpha_{t}{\bf\zeta}^{t}-({\bf W}-{\bf
P}){\bf X}^{t}\|^{2}\leq
2\alpha_{t}^{2}B^{2}+\frac{2\lambda^{2}(B\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j})^{2}}{m}.$
(22)

Thus, we then get

$\displaystyle\frac{\sum_{t=0}^{T-1}\alpha_{t}\mathbb{E}(f({\bf x}^{t})-f({\bf
x}^{*}))}{\sum_{t=0}^{T-1}}\leq\frac{\|{\bf x}^{0}-{\bf
x}^{*}\|^{2}}{\sum_{t=0}^{T-1}\alpha_{t}}+\frac{8LrB\sum_{t=0}^{T-1}\alpha_{t}\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j}}{\sum_{t=0}^{T-1}\alpha_{t}}$
$\displaystyle+\frac{2\lambda^{2}B^{2}\sum_{t=0}^{T-1}\alpha_{t}(\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j})^{2}}{m\sum_{t=0}^{T-1}\alpha_{t}}+\frac{2B^{2}\sum_{t=0}^{T-1}\alpha_{t}^{2}}{m\sum_{t=0}^{T-1}\alpha_{t}}.$

The convexity then completes the proof.

##  Appendix I Proof of Lemma 4

We start from (21) and bound I and II: the strong convexity and Lemma 8 yields

$\displaystyle\frac{2}{m}\mathbb{E}\langle({\bf W}-{\bf P}){\bf
X}^{t}-{\bf\zeta}^{t},{\bf P}{\bf X}^{t}-{\bf
X}^{*}\rangle\leq\sum_{i=1}^{m}\frac{2\alpha_{t}}{m}\mathbb{E}\langle-\nabla
f({\bf x}(i)),{\bf x}^{t}-{\bf x}^{*}\rangle$
$\displaystyle\leq\sum_{i=1}^{m}\frac{2\alpha_{t}}{m}\mathbb{E}\langle-\nabla
f({\bf x}^{t}),{\bf x}^{t}-{\bf
x}^{*}\rangle+\sum_{i=1}^{m}\frac{2\alpha_{t}}{m}\mathbb{E}\langle\nabla
f({\bf x}^{t})-\nabla f({\bf x}(i)),{\bf x}^{t}-{\bf x}^{*}\rangle$
$\displaystyle\leq-2\alpha_{t}\nu\mathbb{E}\|{\bf x}^{t}-{\bf
x}^{*}\|^{2}+\frac{4\alpha_{t}Lr}{\sqrt{m}}\mathbb{E}(\sum_{i=1}^{m}\|{\bf
x}^{t}-{\bf x}(i)\|^{2})^{\frac{1}{2}}$
$\displaystyle\leq-2\alpha_{t}\nu\mathbb{E}\|{\bf x}^{t}-{\bf
x}^{*}\|^{2}+8\alpha_{t}LrB\sum_{j=0}^{t-1}\alpha_{j}\lambda^{t-1-j}.$

Note that (22) still holds in the strong convexity case.

a) Applying the bounds of I and II to (21), letting $\alpha_{t}\equiv\alpha$,

$\displaystyle\mathbb{E}\|{\bf x}^{t+1}-{\bf
x}^{*}\|^{2}\leq(1-2\alpha\nu)\mathbb{E}\|{\bf x}^{t}-{\bf
x}^{*}\|^{2}+\frac{8\alpha^{2}LrB}{1-\lambda}+\frac{2\lambda^{2}B^{2}\alpha^{2}}{m(1-\lambda)^{2}}.$

Thus, we derive

$\displaystyle\mathbb{E}\|{\bf x}^{T}-{\bf
x}^{*}\|^{2}\leq(1-2\alpha\nu)^{T}\mathbb{E}\|{\bf x}^{0}-{\bf
x}^{*}\|^{2}+\frac{\frac{8\alpha^{2}LrB}{1-\lambda}+\frac{2\lambda^{2}B^{2}\alpha^{2}}{m(1-\lambda)^{2}}}{2\alpha\nu}.$

b) Applying the bounds of I and II to (21), letting
$\alpha_{t}=\frac{1}{2\nu(t+1)}$, we get

$\displaystyle\mathbb{E}\|{\bf x}^{t+1}-{\bf
x}^{*}\|^{2}\leq(1-\frac{1}{t+1})\mathbb{E}\|{\bf x}^{t}-{\bf
x}^{*}\|^{2}+\frac{4D_{\lambda}}{(t+1)^{2}}.$

Thus, we derive

$\displaystyle\mathbb{E}\|{\bf x}^{T}-{\bf
x}^{*}\|^{2}\leq\frac{\mathbb{E}\|{\bf x}^{0}-{\bf
x}^{*}\|^{2}}{T}+\frac{D_{\lambda}}{T}\sum_{t=2}^{T}\frac{1}{t}\leq\frac{\mathbb{E}\|{\bf
x}^{0}-{\bf x}^{*}\|^{2}}{T}+\frac{D_{\lambda}\ln T}{T}.$

##  Appendix J Proofs of Theorem 4 and 5

Using the fact $\epsilon_{\textrm{ex-
gen}}\leq\epsilon_{\textrm{gen}}+\mathbb{E}_{S,\mathcal{A}}[R_{S}(\mathcal{A}(S))-R_{S}(\overline{{\bf
x}})]$ and noticing that
$\mathbb{E}_{S,\mathcal{A}}[R_{S}(\mathcal{A}(S))-R_{S}(\overline{{\bf x}})$
is computational error, we then get the result by proved results given above.


# A perspective on the use of health digital twins in computational pathology

Manuel Cossioa∗
aDept. of Mathematics and Computer Science, Universitat de Barcelona,
Barcelona, Spain.
∗Corresponding author: Manuel, Cossio<EMAIL_ADDRESS>
###### Abstract

A digital health twin can be defined as a virtual model of a physical person,
in this specific case, a patient. This virtual model is constituted by
multidimensional data that can host from clinical, molecular and therapeutic
parameters to sensor data and living conditions. Given that in computational
pathology, it is very important to have the information from image donors to
create computational models, the integration of digital twins in this field
could be crucial. However, since these virtual entities collect sensitive data
from physical people, privacy safeguards must also be considered and
implemented. With these data safeguards in place, health digital twins could
integrate digital clinical trials and be necessary participants in the
generation of real-world evidence, which could positively change both fields.

Keywords: health digital twin; computational pathology; digital clinical
trial; real world evidence; sensors; digital health.

##  1 Introduction

Thanks to advances in storage capabilities and the digitization of routine
practices, healthcare is changing its operating paradigm (Palabindala et al.,
2016; Xiao et al., 2018). Day after day, considerable amounts of data relating
to the medical care of patients in hospitals and clinics are being stored. In
fact, there are systems as large as regions and countries that operate mainly
using electronic health records (EHR) (C. Cossio and Gilardino, 2022). These
EHRs can store anything from text entries in defined variables to unstructured
text with medical images. Therefore, it is essential to be able to have some
entity that centralizes all the data per patient(Tayefi et al., 2021). This
entity could bear some resemblance to the actual patient and be updated as new
studies are performed. In fact, the humanization of the data also allows the
addition of other types of information such as housing conditions and access
to basic services. In this brief article, some particular aspects of these
centralized and humanized entities will be discussed.

##  2 What is a health digital twin?

A health digital twin (HDT) could be defined as a virtual space model of a
patient. This virtual model defines its shape and contour using multimodal
clinical data, population data, socio-economic data, behavioral data and real-
time data that may come from wearable sensors (Figure 2). The HDT can be
highly multidimensional if constructed using all available variables. On the
other hand, its dimensions can be reduced by selecting the variables to
construct it. The latter is often the case when HDTs are built for a
particular purpose (Venkatesh et al., 2022).

Figure 1:  Representation of the generation process of a health digital twin
(HDT). Processing includes data mining and application of artificial
intelligence algorithms for automatization.

##  3 Evolution of digital twins for healthcare applications

According to Coorey et al. (2022), the term HDT comes from an adaptation of a
similar term used in industrial engineering to refer to virtual models of
physical systems that can be tested virtually. These virtual tests were used
to refine the settings before manufacturing the devices and thus save time and
resources in fine-tuning (Thuemmler and Bai, 2017). In fact, prototypes could
also be manufactured in small numbers and sensors could be added. These
sensors could record variables during the ride and improve the digital twin.
The improved digital twin could be the target of virtual tests that were more
reliable of the physical phenomena to which it was subjected (Coorey et al.,
2022; Thuemmler and Bai, 2017). The digital twin concept was, after what was
explained in the previous paragraph, derived to healthcare. Within this field,
we have numerous applications where data were integrated to build these
virtual entities. In this way, we have some research works with HDT in
cardiology (Coorey et al., 2022; Mazumder et al., 2019; Gillette et al., 2021;
Herrgårdh et al., 2022), public health (Kamel Boulos and Zhang, 2021),
oncology (Zhang et al., 2020; Kaul et al., 2022; Meraghni et al., 2021),
immunology (Laubenbacher et al., 2022), neurology (Voigt et al., 2021),
infectology (Laubenbacher et al., 2021) and nutrition (Gkouskou et al., 2020).

##  4 HDTs environment

Among the components that make up and should make up the environment of an HDT
we mention some of them.

###  4.1 Artificial intelligence

We can include within this category, all those computational components that
collaborate in the emulation of human reasoning (Figure 1). These components
are the ones that will provide the system with different degrees of autonomy,
reactivity and self-initiation. Coorey et al. (2022) includes in this category
entities such as:

  * •

Computational power

  * •

Big data processing

  * •

Machine learning

  * •

Pattern recognition

We could go deeper in this listing and add possible interesting partners:

  * •

Computer vision

  * •

Multiagents systems

###  4.2 Internet of things (IoT)

IoT refers to the physical and virtual means by which data can be exchanged
(Coorey et al., 2022). Data may flow from inputs to servers, which may be
housed in different physical locations (Figure 1).

###  4.3 Data exchange

Between the HDT and the physical person (physical twin) there must be a
constant exchange of information. This information can be acquired from the
clinical and molecular study of the physical person and from the measurement
of its behavior (sensoring)(Coorey et al., 2022). The closer the gap between
these two entities, the more reliable the virtual model (HDT) will be.

###  4.4 Data privacy and protection

In this brief paper, we add this fourth component, which we believe is very
important to include. There should be between the HDT and the physical person,
a mechanism to protect privacy and safeguard anonymity. The HDT contains a lot
of sensitive information. Only the parties necessary to carry out a diagnosis
or emulation of a therapy should have access to it, with the prior consent of
the individual. To prevent unauthorized third parties from gaining access to
the HDT, the HDT information could be stored in a decentralized form with some
form of encryption. Above all, the identity link between the physical person
and the virtual model (Figure 1) would have to have several levels of
protection. Some ideas in this regard will be developed in future sections
(Section 9).

##  5 Data: where it can come from?

Thanks to the incorporation of new diagnostic techniques and the increasing
digitization of medical records, the data (Figure 2) that can make up an HDT
are extensive:

  * •

Clinical: They are obtained by the physician when performing the physical
examination and asking about signs and symptoms. They can be in the form of
free notes or in categories (Panahiazar et al., 2015).

  * •

Celular and molecular: they involve the prescription of laboratory tests.
These tests can range from routine blood chemistry (such as hematocrit) or
specific techniques such as gene, exome or genome sequencing. Sequencing can
be on panels for diagnostic genes for specific pathologies or the patient’s
entire exome or genome (Panahiazar et al., 2015).

  * •

Pathology: they involve digitizing the tissue slides at multiple levels of
magnification. The slides can correspond to classical pathology with
conventional stains (e.g. hematoxylin and eosin) or to molecular pathology
such as IHC which detects specific cellular markers (Feng et al., 2020).

  * •

Diagnostic imaging: they involve imaging of internal organs and tissues. They
may be with high-energy radiation, such as XR or CT, or by means of a high-
intensity magnetic field, such as MRI. The first two should be used as little
as possible and in justified cases, since radiation is harmful to patients in
high doses(Pesapane et al., 2022).

  * •

Drug pumps: involved in the dispensing of medicines to patients. These data
involve amount of medication administered, frequency and treatment plan.
Automatic pumps can dispense insulin, chemotherapy agents, antibodies for
immunotherapy and enzymes for enzyme replacement therapy (Swapna and Soman,
2021).

  * •

Sensor: they involve real-time measurement of the patient’s vital signs such
as heart rate, blood oxygenation, movement and degree of physical activity.
They can also monitor sleep quality and some of them, of greater complexity
and prior implantation, can monitor serum glucose levels (Mauldin et al.,
2018).

  * •

Apps: they involve the collection of patient data through interaction with an
interface. These data can be level of drowsiness, type of food eaten, amount
of food or state of pain. Some apps can also perform small tests, such as
visual acuity tests, to collect data on sensory impairment (Brady et al.,
2015).

  * •

Social-economical: involve the collection of social and community data from
the patient’s environment. These data may include income level, access to
essential services, disability, level of education achieved, interaction with
the community where he/she lives, access to care services in sickness or old
age. Some databases, such as the Secure Anonymised Information Linkage (SAIL)
include such data, for example in its Index Multiple Deprivation (IMD)
(Schnier et al., 2020).

Figure 2:  Different sources of data that can conform a health digital twin
(HDT). IHC, immunohistochemistry; XR, X rays; CT, computed tomography; MRI,
magnetic resonance imaging;

##  6 HDTs with computational pathology

As we saw in Section 5, part of the data that make up an HDT can be digital
pathology images. Now, how can the use of HDT impact the development of
computational pathology?

###  6.1 Clinical and molecular profiling

General clinical information on the patient’s condition plus the blood and
molecular marker profile is crucial to give context to what is found on the
digital pathology images (Figure 3). For example, in a study by Qu et al.
(2021) they were able to develop a deep learning model to predict point
mutations (such as RB1 and CDH1) in whole slide images (WSIs) of breast
cancer. The molecular profile data for each patient was obtained from EHR. The
algorithm could be developed thanks to the availability of these data for each
patient in the study.

###  6.2 Diagnostic imaging

Information provided by medical imaging studies, which may be contained in
HDTs, can contribute positively to computational pathology. In a study by
Boehm et al. (2022), the authors combined information from contrast-enhanced
computed tomography (CE-CT) with that from WSI to address the diagnosis of
high-grade serous ovarian cancer. The work included the construction of a
multimodal model that segmented omental and adnexal disease on CE-CT and
combined these features with tissue type and cell morphology from WSI
analysis.

###  6.3 Treatment plans

Since HDTs can also store information on the type and degree of development of
treatment plans, this information may also be important for the advancement of
computational pathology. For example, in a study by Lipkova et al. (2022) they
were able to predict the type of cardiac allograft rejection in transplanted
patients with various anti-rejection therapy regimens. The study used WSI from
several cohorts of patients who had their therapeutic regimens recorded by
automatic pumps in the EHRs.

###  6.4 Health apps

In previous sections, we saw how mobile applications can help in the early
screening of patients. Many of these apps can simply help with a signs and
symptoms questionnaire. Some can perform cognitive or vision tests. Others,
for example, can be key in accelerating early diagnosis of skin cancer by
automatically analyzing mole photos by deep learning (Wibowo et al., 2020).
With the score the patient obtains, he or she can then go to the hospital for
a biopsy. The information from the app can be combined with that from the
biopsy and then recorded in a WSI image and a trained algorithm can be used to
detect tumor lesions(Höhn et al., 2021).

###  6.5 Tasks in computational pathology

There are many applications in computational pathology, especially given the
large number of therapeutic areas that use pathology as part of the diagnostic
and therapeutic process. Within computational pathology, four main tasks can
be distinguished (Figure 3). The first is classification, where the input is
an image and the output is a label (e.g., positive or negative). The second is
detection, where the input is an image and the output is a bounding box with
the detected region. This task allows not only to detect the region, but also
to report its position. The third is segmentation, where the input is also an
image and the output is a mask (a label for each pixel). The last one is the
generation, where the input is an image and the output is another image
similar to the input one but with a different style. This task is very useful
in computational pathology to generate artificial stains on WSIs (Huo et al.,
2021).

Figure 3:  Representation of health digital twins as label generators for
computational pathology. EHR, electronic health record; ML, machine learning;
WSI, whole slide image.

##  7 Digital clinical trials

HDTs could have a considerable impact on clinical trials (CT). Given the
increasing digitization of medical services and the performance of global CT
for the same molecule, having HDTs for each patient would have a positive
impact on data processing. Firstly, it would reduce operator bias since all
the data could be processed in one place. Secondly, part of the processing
could be done automatically using machine learning algorithms, which would
speed up the obtaining of results. Third, the anonymity of the patients would
be ensured since only the HDT would be available. Finally, if non-clinical
(social) data are incorporated, the analysis could be broadened to determine
if there is a component of the patients’ environment that could be influencing
the therapeutic response (Steinhubl et al., 2019; Vamathevan et al., 2019).

##  8 Real world evidence (RWE)

Generation of RWE through the analysis of real world data (RWD) is crucial to
enhance the therapeutic effect once the molecules have passed the CT stage.
Since the CTs are subjected to the contingency that the patients are very
typical and do not fully represent the real world population, having data from
real patients would be optimal. Since the HDTs contain multidimensional
information (laboratory, medical images, sensors, see Figure 2) of very
diverse patients, the analysis of these models could be key to obtain insights
from real patients. In addition, since the HDTs may contain social and
economic information, not only exclusively medical aspects but also
multidisciplinary aspects that could be influencing the patient’s recovery
could be analyzed(Khosla et al., 2018). For example, if from the analysis of
the HDTs parameters we observe that the variable access to emotional support
and home care influences recovery after cancer treatment, this could be a
factor to incorporate into the medical treatment plan (Lazar and Davenport,
2018; C. Cossio and Gilardino, 2022).

##  9 Security and data protection

As mentioned before, HDTs contain a lot of sensitive information and are
associated with the identity of individuals. The more extensive they are,
i.e., the more features they contain, the higher the risk associated with
their violation. Therefore, analyzing the possible ways to protect the
information in the first place and the link with the individual in the second
place is crucial to move towards secure practices.

###  9.1 Identifying risks

As a first step, it is possible to identify parts of the programming of the
models and pipelines that may have risk areas. A group in China worked on the
development of a model that could identify parts of vulnerable code in HDTs
built for lung cancer diagnosis. The model was trained with a ground truth
that contained extensive pairs of vulnerable and non-vulnerable code from
related applications (Zhang et al., 2020).

###  9.2 Decentralization and anonymization

Helping to identify parts of the code that could be targeted is a good
strategy. However, this is not enough to ensure that patients’ identities are
not compromised. The blockchain can be used to create a secure network to host
and analyze DHTs. One could start with protecting the assembly of the DHT
models by means of smart-contracts. These contracts could also regulate the
users who would be authorized to upload data to the DHTs and those who would
be authorized to read their information. To provide a greater degree of
anonymity, large files (such as WSI, MRI or CT images) can be hosted on the
DHTs through the use of interplanetary file system (IPFS) mapped with a
content identifier (CID). In this way, part of the smart-contract would
contain the identifiers separated from the IDs of physical persons and this
would ensure that the data would be protected by one more barrier (Kumar et
al., 2021; M. Cossio, 2022; Raj, 2021).

##  10 Future perspectives

In the previous paragraphs some important aspects concerning HDTs have been
discussed very briefly. It has been shown the immensity of devices that can
generate relevant data and the number of dimensions that can be accommodated
by such an entity. It was also briefly mentioned the possible applications
where the impact could be the greatest, such as clinical trials and RWE
generation. However, we also looked at one aspect that needs to be addressed
as quickly as possible, which is the protection of patient data. The data
belong to the patients and therefore any application that is to be made using
their data must have informed consent. In addition to consent, protection
measures must be maximized and some strategies such as block chain or IPFS
have been mentioned to generate a secure network that does not violate
anonymization. It is this last part that has a promising future, because if
holistic protection measures can be implemented, HDTs can be shared and
studied worldwide. This is key to broaden the study populations of many
pathologies, especially in the field of rare diseases. This field, as is well
known, is characterized by too few patients to be able to design effective
therapeutic strategies. In summary, HDTs will surely be able to provide many
options for inclusive and representative studies that positively impact all
human beings.

## References

  *   * Boehm et al. (2022) Boehm, K. M., Aherne, E. A., Ellenson, L., Nikolovski, I., Alghamdi, M., Vázquez-García, I., … others  (2022).  Multimodal data integration using machine learning improves risk stratification of high-grade serous ovarian cancer.  _Nature cancer_ , _3_(6), 723–733.
  * Brady et al. (2015) Brady, C. J., Eghrari, A. O., and Labrique, A. B.  (2015).  Smartphone-based visual acuity measurement for screening and clinical assessment.  _Jama_ , _314_(24), 2682–2683.
  * Coorey et al. (2022) Coorey, G., Figtree, G. A., Fletcher, D. F., Snelson, V. J., Vernon, S. T., Winlaw, D., … others  (2022).  The health digital twin to tackle cardiovascular disease—a review of an emerging interdisciplinary field.  _NPJ digital medicine_ , _5_(1), 1–12.
  * C. Cossio and Gilardino (2022) Cossio, C., and Gilardino, R.  (2022).  Rwd6 the use of machine learning in electronic health records disease analysis: An updated perspective.  _Value in Health_ , _25_(7), S576–S577.
  * M. Cossio (2022) Cossio, M.  (2022).  Ethereum, ipfs and neural compression to decentralize and protect patient data in computational pathology.  _Cambrigde Open Engage_.
  * Feng et al. (2020) Feng, R., Liu, X., Chen, J., Chen, D. Z., Gao, H., and Wu, J.  (2020).  A deep learning approach for colonoscopy pathology wsi analysis: accurate segmentation and classification.  _IEEE Journal of Biomedical and Health Informatics_ , _25_(10), 3700–3708.
  * Gillette et al. (2021) Gillette, K., Gsell, M. A., Prassl, A. J., Karabelas, E., Reiter, U., Reiter, G., … others  (2021).  A framework for the generation of digital twins of cardiac electrophysiology from clinical 12-leads ecgs.  _Medical Image Analysis_ , _71_ , 102080.
  * Gkouskou et al. (2020) Gkouskou, K., Vlastos, I., Karkalousos, P., Chaniotis, D., Sanoudou, D., and Eliopoulos, A. G.  (2020).  The “virtual digital twins” concept in precision nutrition.  _Advances in Nutrition_ , _11_(6), 1405–1413.
  * Herrgårdh et al. (2022) Herrgårdh, T., Simonsson, C., Tunedal, K., and Cedersund, G.  (2022).  Digital twins for prediction of atherosclerosis progression and stroke.  _Atherosclerosis_ , _355_ , 101.
  * Höhn et al. (2021) Höhn, J., Krieghoff-Henning, E., Jutzi, T. B., von Kalle, C., Utikal, J. S., Meier, F., … others  (2021).  Combining cnn-based histologic whole slide image analysis and patient data to improve skin cancer classification.  _European Journal of Cancer_ , _149_ , 94–101.
  * Huo et al. (2021) Huo, Y., Deng, R., Liu, Q., Fogo, A. B., and Yang, H.  (2021).  Ai applications in renal pathology.  _Kidney international_ , _99_(6), 1309–1320.
  * Kamel Boulos and Zhang (2021) Kamel Boulos, M. N., and Zhang, P.  (2021).  Digital twins: from personalised medicine to precision public health.  _Journal of Personalized Medicine_ , _11_(8), 745.
  * Kaul et al. (2022) Kaul, R., Ossai, C., Forkan, A. R. M., Jayaraman, P. P., Zelcer, J., Vaughan, S., and Wickramasinghe, N.  (2022).  The role of ai for developing digital twins in healthcare: The case of cancer care.  _Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery_ , e1480.
  * Khosla et al. (2018) Khosla, S., White, R., Medina, J., Ouwens, M., Emmas, C., Koder, T., … Leonard, S.  (2018).  Real world evidence (rwe)–a disruptive innovation or the quiet evolution of medical evidence generation?  _F1000Research_ , _7_.
  * Kumar et al. (2021) Kumar, R., Wang, W., Kumar, J., Yang, T., Khan, A., Ali, W., and Ali, I.  (2021).  An integration of blockchain and ai for secure data sharing and detection of ct images for the hospitals.  _Computerized Medical Imaging and Graphics_ , _87_ , 101812.
  * Laubenbacher et al. (2022) Laubenbacher, R., Niarakis, A., Helikar, T., An, G., Shapiro, B., Malik-Sheriff, R., … Glazier, J.  (2022).  Building digital twins of the human immune system: toward a roadmap.  _npj Digital Medicine_ , _5_(1), 1–5.
  * Laubenbacher et al. (2021) Laubenbacher, R., Sluka, J. P., and Glazier, J. A.  (2021).  Using digital twins in viral infection.  _Science_ , _371_(6534), 1105–1106.
  * Lazar and Davenport (2018) Lazar, M., and Davenport, L.  (2018).  Barriers to health care access for low income families: a review of literature.  _Journal of community health nursing_ , _35_(1), 28–37.
  * Lipkova et al. (2022) Lipkova, J., Chen, T. Y., Lu, M. Y., Chen, R. J., Shady, M., Williams, M., … others  (2022).  Deep learning-enabled assessment of cardiac allograft rejection from endomyocardial biopsies.  _Nature medicine_ , _28_(3), 575–582.
  * Mauldin et al. (2018) Mauldin, T. R., Canby, M. E., Metsis, V., Ngu, A. H., and Rivera, C. C.  (2018).  Smartfall: A smartwatch-based fall detection system using deep learning.  _Sensors_ , _18_(10), 3363.
  * Mazumder et al. (2019) Mazumder, O., Roy, D., Bhattacharya, S., Sinha, A., and Pal, A.  (2019).  Synthetic ppg generation from haemodynamic model with baroreflex autoregulation: a digital twin of cardiovascular system.  In _2019 41st annual international conference of the ieee engineering in medicine and biology society (embc)_ (pp. 5024–5029).
  * Meraghni et al. (2021) Meraghni, S., Benaggoune, K., Masry, Z. A., Terrissa, L. S., Devalland, C., and Zerhouni, N.  (2021).  Towards digital twins driven breast cancer detection.  In _Intelligent computing_ (pp. 87–99).  Springer.
  * Palabindala et al. (2016) Palabindala, V., Pamarthy, A., and Jonnalagadda, N. R.  (2016).  Adoption of electronic health records and barriers.  _Journal of community hospital internal medicine perspectives_ , _6_(5), 32643.
  * Panahiazar et al. (2015) Panahiazar, M., Taslimitehrani, V., Pereira, N., and Pathak, J.  (2015).  Using ehrs and machine learning for heart failure survival analysis.  _Studies in health technology and informatics_ , _216_ , 40.
  * Pesapane et al. (2022) Pesapane, F., Rotili, A., Penco, S., Nicosia, L., and Cassano, E.  (2022).  Digital twins in radiology.  _Journal of Clinical Medicine_ , _11_(21), 6553.
  * Qu et al. (2021) Qu, H., Zhou, M., Yan, Z., Wang, H., Rustgi, V. K., Zhang, S., … Metaxas, D. N.  (2021).  Genetic mutation and biological pathway prediction based on whole slide images in breast carcinoma using deep learning.  _NPJ precision oncology_ , _5_(1), 1–11.
  * Raj (2021) Raj, P.  (2021).  Empowering digital twins with blockchain.  In _Advances in computers_ (Vol. 121, pp. 267–283).  Elsevier.
  * Schnier et al. (2020) Schnier, C., Wilkinson, T., Akbari, A., Orton, C., Sleegers, K., Gallacher, J., … Sudlow, C. L.  (2020).  The secure anonymised information linkage databank dementia e-cohort (sail-dec).  _International journal of population data science_ , _5_(1).
  * Steinhubl et al. (2019) Steinhubl, S. R., Wolff-Hughes, D. L., Nilsen, W., Iturriaga, E., and Califf, R. M.  (2019).  _Digital clinical trials: creating a vision for the future_ (Vol. 2) (No. 1).  Nature Publishing Group.
  * Swapna and Soman (2021) Swapna, G., and Soman, K.  (2021).  Diabetes detection and sensor-based continuous glucose monitoring–a deep learning approach.  In _Efficient data handling for massive internet of medical things_ (pp. 245–268).  Springer.
  * Tayefi et al. (2021) Tayefi, M., Ngo, P., Chomutare, T., Dalianis, H., Salvi, E., Budrionis, A., and Godtliebsen, F.  (2021).  Challenges and opportunities beyond structured data in analysis of electronic health records.  _Wiley Interdisciplinary Reviews: Computational Statistics_ , _13_(6), e1549.
  * Thuemmler and Bai (2017) Thuemmler, C., and Bai, C.  (2017).  Health 4.0: application of industry 4.0 design principles in future asthma management.  In _Health 4.0: How virtualization and big data are revolutionizing healthcare_ (pp. 23–37).  Springer.
  * Vamathevan et al. (2019) Vamathevan, J., Clark, D., Czodrowski, P., Dunham, I., Ferran, E., Lee, G., … others  (2019).  Applications of machine learning in drug discovery and development.  _Nature reviews Drug discovery_ , _18_(6), 463–477.
  * Venkatesh et al. (2022) Venkatesh, K. P., Raza, M. M., and Kvedar, J. C.  (2022).  _Health digital twins as tools for precision medicine: Considerations for computation, implementation, and regulation_ (Vol. 5) (No. 1).  Nature Publishing Group.
  * Voigt et al. (2021) Voigt, I., Inojosa, H., Dillenseger, A., Haase, R., Akgün, K., and Ziemssen, T.  (2021).  Digital twins for multiple sclerosis.  _Frontiers in immunology_ , _12_ , 669811.
  * Wibowo et al. (2020) Wibowo, A., Hartanto, C. A., and Wirawan, P. W.  (2020).  Android skin cancer detection and classification based on mobilenet v2 model.  _International Journal of Advances in Intelligent Informatics_ , _6_(2), 135–148.
  * Xiao et al. (2018) Xiao, C., Choi, E., and Sun, J.  (2018).  Opportunities and challenges in developing deep learning models using electronic health records data: a systematic review.  _Journal of the American Medical Informatics Association_ , _25_(10), 1419–1428.
  * Zhang et al. (2020) Zhang, J., Li, L., Lin, G., Fang, D., Tai, Y., and Huang, J.  (2020).  Cyber resilience in healthcare digital twin on lung cancer.  _IEEE Access_ , _8_ , 201900–201913.