# Decentralized Langevin Dynamics

Vyacheslav Kungurtsev111Kungurtsev<EMAIL_ADDRESS>is with
the Department of Computer Science, Faculty of Electrical Engineering, Czech
Technical University in Prague, 13 Karlovo Namesti, 12135 Prague, Czech
Republic. His work was supported by the OP VVV project CZ.02.1.01/0.0/0.0/16
019/0000765 “Research Center for Informatics”

###### Abstract

Langevin MCMC gradient optimization is a class of increasingly popular methods
for estimating a posterior distribution. This paper addresses the algorithm as
applied in a decentralized setting, wherein data is distributed across a
network of agents which act to cooperatively solve the problem using peer-to-
peer gossip communication. We show, theoretically, results in 1) the time-
complexity to $\epsilon$-consensus for the continuous time stochastic
differential equation, 2) convergence rate in $L^{2}$ norm to consensus for
the discrete implementation as defined by the Euler-Maruyama discretization
and 3) convergence rate in the Wasserstein metric to the optimal stationary
distribution for the discretized dynamics.

##  1 Introduction

Consider the problem of sampling a posterior distribution $\pi$ on
$\mathbb{R}^{d}$ with density

$\pi:x\to e^{-U(x)}/\int_{\mathbb{R}^{d}}e^{-U(y)}dy$

with respect to the Lebesgue measure, with a continuously differentiable
potential $U:\mathbb{R}^{d}\to\mathbb{R}$. Now, consider a decentralized
computing environment. Specifically, we define the potential
$U(x)=\sum_{i=1}^{m}u_{i}(x)$, where we have a set of agents all of whom store
local copies of estimates of $x_{(i)},\,i\in\\{1,...,m\\}$ and only have
access to their respective $u_{i}(x)$. This can be an inherent property of the
problem, with the data defined on separate and distinct processes whose
conglomerate minimization is encouraged. Alternatively, the set up is
methodological, where the use of a distributed computing platform is
undertaken in order accelerate the convergence towards the stationary
distribution.

The communication network of the agent is modeled as a fixed undirected graph
$\mathcal{G}\triangleq(\mathcal{V},\mathcal{E})$ with vertices
$\mathcal{V}\triangleq\\{1,..,I\\}$ and
$\mathcal{E}\triangleq\\{(i,j)|i,j\in\mathcal{V}\\}$ representing the agents
and communication links, respectively. We assume that the graph $\mathcal{G}$
is strongly connected. We note by $\mathcal{N}_{i}$ the neighbors of $i$,
i.e., $\mathcal{N}_{i}=\\{j:(i,j)\in\mathcal{E}\\}$.

We define the graph Laplacian matrix $\mathbf{L}=\mathbf{I}-\mathbf{W}$, where
$\mathbf{W}=\mathbf{A}\otimes\mathbf{I}$ with $\mathbf{A}$ satisfying
$\mathbf{A}_{ij}\neq 0$ if $(i,j)\in\mathcal{E}$ and $\mathbf{A}_{ij}=0$
otherwise.

We assume that $\mathbf{W}$ is double stochastic (and symmetric, since the
graph is undirected). The eigenvalues of $\mathbf{L}$ are real and can be
sorted in a nonincreasing order
$1=\lambda_{1}(\mathbf{L})>\lambda_{2}(\mathbf{L})\geq...\geq\lambda_{n}(\mathbf{L})\geq
0$.

Defining,

$\beta\triangleq\lambda_{2}(\mathbf{L})$

we shall make the following assumption,

###### Assumption 1.1

It holds that,

$\beta<1$

We shall define $\bar{\beta}$ to be the smallest eigenvalue of $\mathbf{L}$
that is nonzero.

Each agent $i$ has access to and controls an estimate of the primal stochastic
variables $X^{(i)}(t)$.

We make the following assumption about the potential function.

###### Assumption 1.2

The potential $U(x)$ has a Lipschitz continuous gradient with constant $L$,
i.e., $\|\nabla U(x)-\nabla U(y)\|\leq L\|x-y\|$ and $U(\cdot)$ is strongly
convex with constant $m$, i.e., $U(x)-U(y)-\nabla
U(y)(x-y)\geq\frac{m}{2}\|x-y\|^{2}$. Furthermore, the component functions
have bounded dissimilarity in gradients, i.e., $\|\nabla u_{i}(x)-\nabla
u_{j}(y)\|\leq G\|x-y\|$.

We consider convergence in terms of the Wasserstein distance $W_{2}$. For two
measures $\mu$ and $\nu$ on $(\mathbb{R}^{d},\mathcal{B}(\mathbb{R}^{d}))$ and
for any real number $q\geq 1$, we define,

$W_{q}(\mu,\nu)=\left(\inf_{\rho\in\rho(\mu,\nu)}\int_{\mathbb{R}^{d}\times\mathbb{R}^{d}}\|x-y\|^{q}_{2}d\rho(x,y)\right)^{1/q}$

where $\rho(\mu,\nu)$ is the set of joint distributions with $\mu$ and $\nu$
as marginals.

Consider the standard Langevin equation with Brownian motion $B_{t}$,

$dX_{t}=-\nabla U(X_{t})dt+\sqrt{2\sigma}dB_{t}$

Convergence of this stochastic differential equation (SDE) and its
discretization to the stationary distribution of the potential has been
studied in a number of works, with increased interest in recent years due to
the superiority of Langevin gradient based approaches over sampling for log-
concave potentials with high dimensional datasets. Consider now that there are
now $m$ different estimates $X^{(i)}$ for which we implement the following
SDE,

$dX^{(i)}_{t}=-\sum_{j\in\mathcal{N}_{i}\cup\\{i\\}}\mathbf{L}_{ij}X^{(j)}(t)dt-\alpha(t)\nabla
u_{i}(X^{(i)}(t))dt+\sqrt{2\sigma\alpha(t)}dB^{(i)}_{t}$ (1)

and its Euler-Maruyana discretization with step-size $h$,

$X^{(i)}_{k+1}=(1-h)X^{(i)}_{k}+h\sum_{j\in\mathcal{N}_{i}}\mathbf{W}_{ij}X^{(j)}_{k}-\alpha_{k+1}h\nabla
u_{i}(X^{(i)}_{k})dt+\sqrt{2\sigma\alpha_{k+1}h}Z^{(i)}_{k+1}$ (2)

We assume a standard diminishing step-size,

$\alpha(t)=\frac{1}{1+t}$ (3)

If we consider the random vectors $X_{t}$ and $X_{k}$, respectively, as the
stack,

$X_{t}=\begin{pmatrix}(X^{(1)}_{t})^{T}&(X^{(2)}_{t})^{T}&...&(X^{(m)}_{t})^{T}\end{pmatrix}^{T}\text{
and
}X_{k}=\begin{pmatrix}(X^{(1)}_{k})^{T}&(X^{(2)}_{k})^{T}&...&(X^{(m)}_{k})^{T}\end{pmatrix}^{T}$

and define $U_{v}(X)=\sum_{i=1}^{m}u_{i}(X^{(i)})$, then we can write the
update of the full stack of vectors as,

$dX_{t}=-\mathbf{L}X(t)dt-\alpha(t)\nabla
U_{v}(X(t))dt+\sqrt{2\sigma\alpha(t)}dB_{t}$ (4)
$X_{k+1}=\left((1-h)\mathbf{I}-h\mathbf{W}\right)X_{k}-\alpha_{k+1}h\nabla
U_{v}(X_{k})+\sqrt{2\sigma\alpha_{k+1}h}Z_{k+1}$ (5)

Consider the averaging operator $\frac{1}{m}\mathbf{1}\mathbf{1}^{T}\otimes
I_{d}$. It is clear from the double stochasticity of $\mathbf{W}$ that
$(\frac{1}{m}\mathbf{1}\mathbf{1}^{T}\otimes
I_{d})\mathbf{W}=(\frac{1}{m}\mathbf{1}\mathbf{1}^{T}\otimes I_{d})$ and so
$(\frac{1}{m}\mathbf{1}\mathbf{1}^{T}\otimes I_{d})\mathbf{L}=0$.

Thus the average vectors
$\bar{X}_{t}=(\frac{1}{m}\mathbf{1}\mathbf{1}^{T}\otimes I_{d})X_{t}$ and
$\bar{X}_{k}=(\frac{1}{m}\mathbf{1}\mathbf{1}^{T}\otimes I_{d})X_{k}$ satisfy
the updates,

$\begin{array}[]{l}d\bar{X}_{t}=-\frac{\alpha(t)}{m}\sum_{i=1}^{m}\nabla
u_{i}(X^{(i)}(t))dt+\sqrt{2\sigma\alpha(t)}dB_{t}\\\ \qquad=-\alpha(t)\nabla
U(\bar{X}(t))dt-\alpha(t)\left(\frac{1}{m}\sum_{i=1}^{m}\nabla
u_{i}(X^{(i)}(t))-\nabla
U(\bar{X}(t))\right)dt+\sqrt{2\sigma\alpha(t)}d\bar{B}_{t}\end{array}$ (6)
$\begin{array}[]{l}\bar{X}_{k+1}=\bar{X}_{k}-\frac{\alpha_{k+1}h}{m}\sum_{i=1}^{m}\nabla
u_{i}(X^{(i)}_{k})+\alpha_{k+1}\sqrt{2\sigma\alpha_{k+1}h}Z_{k+1}\\\
\qquad=\bar{X}_{k}-\alpha_{k+1}h\nabla
U(\bar{X}_{k})-\alpha_{k+1}h\left(\frac{1}{m}\sum_{i=1}^{m}\nabla
u_{i}(X^{(i)}_{k})-\nabla
U(\bar{X}_{k})\right)+\sqrt{2\sigma\alpha_{k+1}h}\bar{Z}_{k+1}\end{array}$ (7)

where we treat these terms in parentheses as bias error terms. Note that since
a standard stochastic gradient approximation has zero mean and bounded
variance, just like the added normal noise, an extension to the stochastic
gradient Langevin case would be trivial and it is not included for ease of
readability.

###  1.1 Previous Work

Langevin gradient methods have enjoyed a surge in popularity roughly since the
publication of the popular article [10]. Other important papers concerning
convergence and applications include [5] and [2].

The paper [1] considers stochastic gradient Langevin dynamics for distributed
learning, without the network architecture considered in this work. The
closest paper to this work is [7] which considers a stochastic gradient
annealing algorithm for global optimization, see also the similar [9]. The
setting and algorithms are similar, however the focus and ultimate nature of
the results is distinct in considering asymptotic convergence as well as
iteration convergence in expectation to a global minimizer, as opposed to
convergence to a desired stationary distribution for posterior sampling as
considered here, with convergence defined in appropriate distance of
probability measures.

##  2 Consensus

To begin with, we consider a precisely defined appropriate notion of consensus
in this setting, and show that the SDE converges to consensus. We characterize
the time-complexity to consensus at an arbitrary desired $\epsilon$.

###### Theorem 2.1

Assume $\sigma<\bar{\beta}$.

Let $\check{X}(t)=X(t)-1_{m}\otimes\bar{X}(t)$.

Define $f(\check{X}_{t})=\|\check{X}_{t}\|^{2}$.

It holds that $\mathbb{E}[f(\check{X}_{t})]$ converges to zero exponentially,
i.e., we have that for any $\epsilon$ the time $T_{\epsilon}$ at which
$\mathbb{E}[f(\check{X}_{t})]\leq\epsilon$ satisfies,

$\mathbb{E}[T_{\epsilon}]\leq\frac{2}{\bar{\beta}-\sigma}\left[-\log\epsilon+\left(\mathbb{E}[f(\check{X}_{0})]+\sigma\log\left(\frac{2L}{\bar{\beta}}\right)\right)e^{(\alpha(0)L-\bar{\beta})(\frac{2L}{\bar{\beta}}-1)}+\frac{2L}{\bar{\beta}}-1\right]$

Proof. We have that,

$d\check{X}_{t}=-\mathbf{L}\check{X}_{t}dt-\alpha(t)\left(\nabla
U_{v}(X(t))-\mathbf{1}\otimes\frac{1}{m}\sum_{i=1}^{m}\nabla
u_{i}(X^{(i)}(t))\right)dt+\sqrt{2\sigma\alpha(t)}\left(dB_{t}-\mathbf{1}\otimes
d\bar{B}_{t}\right)$

We can write $d\check{B}_{t}=\left(dB_{t}-\mathbf{1}\otimes
d\bar{B}_{t}\right)$ as itself a Wiener process since it is a scaled sum of
Wiener processes.

Now it holds that,

$\begin{array}[]{l}\alpha(t)\left\|\nabla
U_{v}(X(t))-\mathbf{1}\otimes\frac{1}{m}\sum_{i=1}^{m}\nabla
u_{i}(X^{(i)}(t))\right\|\\\ \qquad\leq\alpha(t)\left\|\nabla
U_{v}(X(t))-\mathbf{1}\otimes\nabla U(\bar{X}(t))+\mathbf{1}\otimes\nabla
U(\bar{X}(t))-\mathbf{1}\otimes\frac{1}{m}\sum_{i=1}^{m}\nabla
u_{i}(X^{(i)}(t))\right\|\\\ \qquad\qquad\qquad\leq
2\alpha(t)L\|\check{X}(t)\|\end{array}$

By Itô’s Lemma,

$df(\check{X}_{t})=-2\check{X}_{t}^{T}\mathbf{L}\check{X}_{t}dt-2\alpha(t)\left(\nabla
U_{v}(X(t))-\mathbf{1}\otimes\frac{1}{m}\sum_{i=1}^{m}\nabla
u_{i}(X^{(i)}(t))\right)^{T}\check{X}_{t}dt+\sigma\alpha(t)dt+\sqrt{2\sigma\alpha(t)}\check{X}_{t}^{T}d\check{B}_{t}.$

Note that $\check{X}_{t}$ is in the nullspace of $\mathbf{L}$ if and only if
$\check{X}_{t}=0$. Thus,
$\check{X}_{t}^{T}\mathbf{L}\check{X}_{t}\geq\bar{\beta}\|\check{X}_{t}\|^{2}$.
And so we have,

$\begin{array}[]{l}\mathbb{E}_{t}(f(\check{X}_{t}))=f(\check{X}_{0})-\mathbb{E}\left[\int_{s=0}^{t}\left\\{2\check{X}_{t}^{T}\mathbf{L}\check{X}_{t}+2\alpha(s)\left(\nabla
U_{v}(X(t))-\mathbf{1}\otimes\frac{1}{m}\sum_{i=1}^{m}\nabla
u_{i}(X^{(i)}(t))\right)^{T}\check{X}_{s}-\frac{1}{2}\sigma\alpha(s)\right\\}ds\right]\\\
\qquad\leq
f(\check{X}_{0})-2\mathbb{E}\left[\int_{s=0}^{t}\left\\{\bar{\beta}f(\check{X}_{s})-\alpha(s)L\|\check{X}_{s}\|^{2}-\frac{1}{2}\alpha(s)\sigma\right\\}ds\right]\\\
\qquad\leq
f(\check{X}_{0})-2\mathbb{E}\left[\int_{s=0}^{t}\left\\{(\bar{\beta}-\alpha(s)L)f(\check{X}_{s})-\frac{1}{2}\alpha(s)\sigma\right\\}ds\right]\end{array}$

Let $\hat{T}$ be such that $\alpha(\hat{T})\leq\frac{\bar{\beta}}{2L}$, i.e.,
$\hat{T}=\frac{2L}{\bar{\beta}}-1$. Then,

$\mathbb{E}_{t}(f(\check{X}_{t}))\leq\mathbb{E}[f(\check{X}_{0})]+2\mathbb{E}\left[\int_{s=0}^{\hat{T}}\left\\{(\alpha(0)L-\frac{1}{2}\bar{\beta})f(\check{X}_{s})+\frac{1}{2}\alpha(s)\sigma\right\\}ds\right]-2\mathbb{E}\left[\int_{s=\hat{T}}^{t}\left\\{\frac{1}{2}\bar{\beta}f(\check{X}_{s})-\frac{1}{2}\alpha(s)\sigma\right\\}ds\right]$

Recall the standard Grownwall’s inequality,

$u(t)\leq v+\int_{a}^{t}\beta(s)u(s)ds\Longrightarrow u(t)\leq
v\exp\left(\int_{a}^{t}\beta(s)ds\right)$

We get that,

$\mathbb{E}_{t}(f(\check{X}(\hat{T})))\leq\left(\mathbb{E}[f(\check{X}_{0})]+\frac{\sigma}{2}\int_{s=0}^{\hat{t}}\alpha(s)ds\right)e^{(\alpha(0)L-\bar{\beta})\hat{T}}\leq\left(\mathbb{E}[f(\check{X}_{0})]+\sigma\log\left(\frac{2L}{\bar{\beta}}\right)\right)e^{(\alpha(0)L-\bar{\beta})(\frac{2L}{\bar{\beta}}-1)}$

Now define $T_{\epsilon}$ as a stopping time at which it holds that
$\mathbb{E}[f(\check{X}_{s})]\leq\epsilon$. Consider,

$\mathbb{E}(f(\check{X}_{T_{\epsilon}}))\leq\mathbb{E}[f(\check{X}_{\hat{T}})]-\mathbb{E}\left[\int_{s=\hat{T}}^{T_{\epsilon}}\left\\{\bar{\beta}f(\check{X}_{s})-\alpha(s)\sigma\right\\}ds\right]$

Applying Grownwall’s inequality again,

$\begin{array}[]{l}\mathbb{E}(f(\check{X}_{T_{\epsilon}}))\leq\left(\mathbb{E}[f(\check{X}_{\hat{T}})]+\sigma\int_{s=\hat{T}}^{\mathbb{E}[T_{\epsilon}]}\alpha(s)ds\right)e^{-\bar{\beta}(\mathbb{E}[T_{\epsilon}]-\hat{T})}\\\
\qquad\qquad\leq\left(\mathbb{E}[f(\check{X}_{\hat{T}})]+\sigma\log(1+\mathbb{E}[T_{\epsilon}])-\sigma\log(1+\hat{T})\right)e^{-\bar{\beta}(\mathbb{E}[T_{\epsilon}]-\hat{T})}\\\
\qquad\qquad\leq\left(\mathbb{E}[f(\check{X}_{\hat{T}})]+\sigma\mathbb{E}[T_{\epsilon}]\right)e^{-\bar{\beta}(\mathbb{E}[T_{\epsilon}]-\hat{T})}\end{array}$

which implies,

$\log(\epsilon)\leq\log\left(\mathbb{E}[f(\check{X}_{\hat{T}})]+\sigma\mathbb{E}[T_{\epsilon}]\right)-\bar{\beta}(\mathbb{E}[T_{\epsilon}]-\hat{T})\leq\mathbb{E}[f(\check{X}_{\hat{T}})]+\left(\sigma-\bar{\beta}\right)\mathbb{E}[T_{\epsilon}]+\frac{2L}{\bar{\beta}}-1$

and thus,

$\mathbb{E}[T_{\epsilon}]\leq\frac{1}{\bar{\beta}-\sigma}\left[-\log\epsilon+\left(\mathbb{E}[f(\check{X}_{0})]+\sigma\log\left(\frac{2L}{\bar{\beta}}\right)\right)e^{(\alpha(0)L-\bar{\beta})(\frac{2L}{\bar{\beta}}-1)}+\frac{2L}{\bar{\beta}}-1\right]$

Now consider the discrete result, i.e., a notion of convergence rate to
consensus for the stochastic process defined by the Euler-Maruyama
discretization $X_{k}$.

We will need to use a classic convergence Lemma

###### Lemma 2.1

[6, Lemma 2.5] Let $u_{k}\geq 0$ and,

$u_{k+1}\leq\left(1-\frac{c}{k^{s}}\right)u_{k}+\frac{d}{k^{t}}$

with $0<s<1$ and $s<t$ and $c,d>0$. Then,

$u_{k}\leq\frac{d}{c}\frac{1}{k^{t-s}}+o\left(\frac{1}{k^{t-s}}\right)$

###### Theorem 2.2

The distribution associated with the consensus error
$\check{X}_{k}:=X_{k}-1\otimes\bar{X}_{k}$ converges in $W_{2}(\cdot,\cdot)$
distance, for any $\gamma>0$, to the Dirac delta at zero at a rate of

$O\left(\frac{1}{(1+k)^{1/2-\gamma}}\right)$

Proof. We have that

$\begin{array}[]{l}\check{X}_{k+1}:=X_{k+1}-1\otimes\bar{X}_{k+1}\\\
\qquad=\left((1-h)\mathbf{I}-h\mathbf{W}\right)X_{k}-\mathbf{1}\otimes\bar{X}_{k}-\alpha_{k+1}h\nabla
U_{v}(X_{k})+\sqrt{2\sigma\alpha_{k+1}h}Z_{k+1}\\\
\qquad\qquad\qquad\qquad+\frac{\alpha_{k+1}h}{m}\sum_{i=1}^{m}\mathbf{1}\otimes\nabla
u_{i}(X^{(i)}_{k})-\sqrt{2\sigma\alpha_{k+1}h}1\otimes\bar{Z}_{k+1}\\\
\qquad=\check{X}_{k}-h\mathbf{L}X_{k}-\alpha_{k+1}h\left(\nabla
U_{v}(X_{k})-\frac{1}{m}\sum_{i=1}^{m}\mathbf{1}\otimes\nabla
u_{i}(X^{(i)}_{k})\right)+\sqrt{2\sigma\alpha_{k+1}h}\check{Z}_{k+1}\\\
\qquad=(1-h)\mathbf{L}\check{X}_{k}-\alpha_{k+1}h\left(\nabla
U_{v}(X_{k})-\frac{1}{m}\sum_{i=1}^{m}\mathbf{1}\otimes\nabla
u_{i}(X^{(i)}_{k})\right)+\sqrt{2\sigma\alpha_{k+1}h}\check{Z}_{k+1}\end{array}$

Let $\nu_{k}$ be the distribution associated with the stochastic process
$\check{X}_{k}$. Define the distribution for consensus of $\check{X}$ to be
$\pi$, the delta function at zero, i.e., $\pi=\delta_{0}(x)$. Define the
distribution $\pi_{k}$ to be the normal distribution with standard deviation
$2\sigma h/\sqrt{1+k}$.

Construct now a stochastic variable $Y_{0}\sim\pi_{0}$ such that the
Wasserstein distance to the initial distribution is minimized, i.e.,
$W_{2}(\nu_{0},\pi_{0})=\|Y_{0}-\check{X}_{0}\|$ and
$Y_{k+1}=\sqrt{2\sigma\alpha_{k+1}h}\check{Z}_{k+1}$. Note that this is a
process that for each $k$ has $\pi_{k}$ as its associated distribution. Since
the support is $\mathbb{R}^{d}$, each $Y_{k}$ is in the support of $\pi_{k}$.
Since zero, the only vector in the support of $\pi$, is also in the support of
$\pi_{k}$, it holds that
$W_{2}(\pi,\pi_{k})=\sqrt{\int_{\mathbb{R}^{d}}\|x\|^{2}d\pi_{k}}=2\sigma
h/\sqrt{k+1}$ and we can finally write,

$W_{2}(\nu_{k},\pi)\leq
W_{2}(\nu_{k},\pi_{k})+W_{2}(\pi_{k},\pi)\leq\mathbb{E}[\|\check{X}_{k}-Y_{k}\|_{L^{2}}]+2\sigma
h/\sqrt{k+1}$ (8)

Consider now $\check{X}_{k+1}-Y_{k+1}$,

$\begin{array}[]{l}\check{X}_{k+1}-Y_{k+1}=(1-h)\mathbf{L}\check{X}_{k}-\alpha_{k+1}h\left(\nabla
U_{v}(X_{k})-\frac{1}{m}\sum_{i=1}^{m}\mathbf{1}\otimes\nabla
u_{i}(X^{(i)}_{k})\right)\end{array}$

and thus, using Assumption 1.2 we can see that,

$\|\check{X}_{k+1}-Y_{k+1}\|=(1-h-2\alpha_{k+1}hmG)\|\check{X}_{k}-Y_{k}\|+\|Y_{k}\|$

and so,

$\mathbb{E}\|\check{X}_{k+1}-Y_{k+1}\|=(1-h-2\alpha_{k+1}hmG)\mathbb{E}\|\check{X}_{k}-Y_{k}\|+\mathbb{E}\|Y_{k}\|$

Finally we can apply Lemma 2.1 to conclude that for any $\gamma>0$, for
sufficiently large $k\geq K$,

$\mathbb{E}\|\check{X}_{k+1}-Y_{k+1}\|=\left(1-\frac{2h}{(k+1)^{\gamma}}\right)\mathbb{E}\|\check{X}_{k}-Y_{k}\|+\frac{2\sigma
h}{\sqrt{k+1}}=O\left(\frac{1}{k^{1/2-\gamma}}\right)$

Plugging this into (8) yields the final result.

##  3 Convergence

Finally we show that the average process $\bar{X}_{k}$ converges to a
minimizer of $U(\cdot)$.

Let $S(t)=\int_{0}^{t}\alpha(s)ds$ and let $T:\mathbb{R}\to\mathbb{R}$ be the
inverse of $S$ such that $S(T(t))=t$ (which exists since $T$ is increasing.
Letting $Y(t)=\bar{X}(T(t))$, we have
$\frac{d}{dt}Y(t)=\frac{d\bar{X}(T(t))}{dt}\frac{dT(t)}{dt}$ and
$\frac{dS(T(t))}{dt}\frac{dT(t)}{dt}=1$ so
$\frac{dT(t)}{dt}=\frac{1}{\alpha(T(t))}$ (see [8]). Now the process $Y_{t}$
satisfies,

$dY_{t}=-h\nabla U(\bar{X}(T(t)))dt-h\left(\frac{1}{m}\sum_{i=1}^{m}\nabla
u_{i}(X^{(i)}(T(t)))-\nabla
U(\bar{X}(T(t)))\right)dt+\frac{\sqrt{2\sigma\alpha(T(t))h}}{\alpha(T(t))}d\bar{B}(T(t))$

and by the scale invariance of a Wiener process
($\beta^{-1}W_{\beta^{2}t}=W_{t}$ for all $\beta>0$) this is equivalent to,

$dY_{t}=-h\nabla U(Y_{t})dt-h\left(\frac{1}{m}\sum_{i=1}^{m}\nabla
u_{i}(X^{(i)}(T(t)))-\nabla U(\bar{X}(T(t)))\right)dt+\sqrt{2\sigma
h}d\bar{B}_{t}$

with discretization,

$Y_{k+1}=Y_{k}-h\nabla U(Y_{k})-h\left(\frac{1}{m}\sum_{i=1}^{m}\nabla
u_{i}(Y^{(i)}_{k})-\nabla U(\bar{Y}_{k})\right)+\sqrt{2\sigma h}\bar{Z}_{k+1}$

We observe that with $\alpha_{k}=\frac{1}{1+k}$, it holds that
$S_{k}=\log(1+k)$ and so $T(t_{k})=e^{t_{k}}-1$. Thus
$\alpha_{k}=\frac{1}{e^{k}}\leq\frac{1}{1+k}$.

Let us redefine $\nu_{k}$ to be the distribution associated with the
stochastic process $Y_{k}$ and $\pi$ the stationary process associated with
$U(x)$. Consider that in general now we have iteration dependant stepsize
$h_{k}$.

To derive our diminishing step-size convergence result, we recall a useful
Lemma.

###### Lemma 3.1

[6, Lemma 2.4] Let $u_{k}\geq 0$ and,

$u_{k+1}\leq\left(1-\frac{c}{k}\right)u_{k}+\frac{d}{k^{p+1}}$

with $d>0$, $p>0$ and $c>0$ and $c>p$. Then,

$u_{k}\leq d(c-p)^{-1}k^{-p}+o(k^{-p})$

We are now ready to prove the main convergence result.

###### Theorem 3.1

If $h_{k}$ is constant, i.e., $h_{k}=h$ and
$h<\min\left\\{\frac{1}{L},m\right\\}$ then,

$\lim_{K\to\infty}W_{2}(\nu_{K},\pi)\leq\frac{\chi L(hd)^{1/2}}{m}$

with $\chi=7\sqrt{2}/6$. If $h_{k}=\frac{1}{k}$ then for
$k\geq\frac{L+m}{2}-1$,

$W_{2}(\nu_{k},\pi)=O\left(k^{-1/2}\right)$

Proof. We apply [3, Proposition 2] to $\nu_{k}$ with the deterministic bias
bound $\|\zeta_{k}\|\leq L\alpha_{k}$ to get,

$W_{2}(\nu_{k+1},\pi)\leq\rho_{k+1}W_{2}(\nu_{k},\pi)+\chi
L(h^{3}_{k+1}d)^{1/2}+Lh_{k+1}\alpha_{k+1}$ (9)

where $\rho_{k}=\max(1-mh_{k+1},Lh_{k+1}-1)$.

If $h_{k}=h$ such that $\rho_{k}<1$ (i.e.,
$h<\min\left\\{\frac{1}{L},m\right\\}$) then we have,

$W_{2}(\nu_{K},\pi)\leq\rho^{K}W(\nu_{0},\pi)+\sum_{k=0}^{K}\rho^{K-k}\chi
L(h^{3}d)^{1/2}+\sum_{k=0}^{K}\frac{Lh\rho^{K-k}}{1+k}$

and we use [4, Lemma 7a] to conclude that the last term approaches zero.

Now assume that $h_{k}=\frac{1}{k}$, and let $\hat{K}$ be the first iteration
from which $1-\frac{m}{k+1}\geq\frac{L}{k+1}-1$, or $\frac{L+m}{k+1}\leq 2$,
i.e., $\hat{K}=\frac{L+m}{2}-1$. We have for $k\geq\hat{K}$,

$\begin{array}[]{l}W_{2}(\nu_{k+1},\pi)\leq\left(1-\frac{m}{k+1}\right)W_{2}(\nu_{k},\pi)+\frac{\chi
Ld^{1/2}}{(k+1)^{3/2}}+\frac{L}{(k+1)^{2}}\\\
\qquad\qquad\qquad\leq\left(1-\frac{m}{2k}\right)W_{2}(\nu_{k},\pi)+\frac{\chi
Ld^{1/2}+L}{k^{3/2}}\end{array}$

Applying Lemma 3.1 we obtain that,

$W_{2}(\nu_{k},\pi)\leq\frac{\chi
Ld^{1/2}+L}{\left(\frac{m}{2}-\frac{1}{2}\right)k^{1/2}}+o(k^{-1/2})$

##  4 Conclusion

In this paper we derived convergence rate results in appropriate notions of
probability measure distance for the stochastic gradient Langevin dynamics
method in a decentralized setting. These results confirm that the performance
of this powerful method for obtaining the stationary distribution associated
with log-concave potentials extends to a distributed network communication
setting. Given the promising theoretical results we are aiming to perform an
extensive set of numerical experiments.

## References

  * [1] Sungjin Ahn, Babak Shahbaba, and Max Welling.  Distributed stochastic gradient mcmc.  In International conference on machine learning, pages 1044–1052, 2014.
  * [2] Changyou Chen, David Carlson, Zhe Gan, Chunyuan Li, and Lawrence Carin.  Bridging the gap between stochastic gradient mcmc and stochastic optimization.  In Artificial Intelligence and Statistics, pages 1051–1060, 2016\.
  * [3] Arnak S Dalalyan and Avetik Karagulyan.  User-friendly guarantees for the langevin monte carlo with inaccurate gradient.  Stochastic Processes and their Applications, 2019.
  * [4] Paolo Di Lorenzo and Gesualdo Scutari.  Next: In-network nonconvex optimization.  IEEE Transactions on Signal and Information Processing over Networks, 2(2):120–136, 2016.
  * [5] Yi-An Ma, Tianqi Chen, and Emily Fox.  A complete recipe for stochastic gradient mcmc.  In Advances in Neural Information Processing Systems, pages 2917–2925, 2015.
  * [6] Boris T Polyak.  Introduction to optimization.  Number 04; QA402. 5, P6. 1987.
  * [7] Brian Swenson, Soummya Kar, H Vincent Poor, and Jose’MF Moura.  Annealing for distributed global optimization.  arXiv preprint arXiv:1903.07258, 2019.
  * [8] Brian Swenson, Ryan Murray, H Vincent Poor, and Soummya Kar.  Distributed gradient descent: Nonconvergence to saddle points and the stable-manifold theorem.  arXiv preprint arXiv:1908.02747, 2019.
  * [9] Stefan Vlaski and Ali H Sayed.  Distributed learning in non-convex environments–part i: Agreement at a linear rate.  arXiv preprint arXiv:1907.01848, 2019.
  * [10] Max Welling and Yee W Teh.  Bayesian learning via stochastic gradient langevin dynamics.  In Proceedings of the 28th international conference on machine learning (ICML-11), pages 681–688, 2011.
  * [11] Jinshan Zeng and Wotao Yin.  On nonconvex decentralized gradient descent.  IEEE Transactions on signal processing, 66(11):2834–2848, 2018\.