marginparsep has been altered.
topmargin has been altered.
marginparpush has been altered.
The page layout violates the ICML style. Please do not change the page layout,
or include packages like geometry, savetrees, or fullpage, which change it for
you. We’re not able to reliably undo arbitrary changes to the style. Please
remove the offending package(s), or layout-changing commands and try again.

Stochastic Gradient Descent under Markov-Chain Sampling Schemes

Mathieu Even 1

††footnotetext:  1Inria - ENS Paris. Correspondence to: Mathieu Even
<EMAIL_ADDRESS>
Proceedings of the $\mathit{40}^{th}$ International Conference on Machine
Learning, Honolulu, Hawaii, USA. PMLR 202, 2023. Copyright 2023 by the
author(s).

###### Abstract

We study a variation of vanilla stochastic gradient descent where the
optimizer only has access to a “Markovian sampling scheme”. These schemes
encompass applications that range from decentralized optimization with a
random walker (_token algorithms_), to RL and online system identification
problems. We focus on obtaining rates of convergence under the least
restrictive assumptions possible on the underlying Markov chain and on the
functions optimized. We first unveil the theoretical lower bound for methods
that sample stochastic gradients along the path of a Markov chain, making
appear a dependency in the hitting time of the underlying Markov chain. We
then study _Markov chain SGD_ (MC-SGD) under much milder regularity
assumptions than prior works. We finally introduce MC-SAG, an alternative to
MC-SGD with variance reduction, that only depends on the hitting time of the
Markov chain, therefore obtaining a communication-efficient token algorithm.

##  1 Introduction

In this paper, we consider a stochastic optimization problem that takes root
in decentralized optimization, estimation problems, and Reinforcement
Learning. Consider a function $f$ defined as:

$f(\mathbf{x})=\mathbb{E}_{v\sim\pi}\left[f_{v}(\mathbf{x})\right]\,,\quad\mathbf{x}\in\mathbb{R}^{d}\,,$
(1)

where $\pi$ is a probability distribution over a set $\mathcal{V}$, and
$f_{v}$ are smooth functions on $\mathbb{R}^{d}$ for all $v$ in $\mathcal{V}$.
Classicaly, this represents the loss of a model parameterized by $\mathbf{x}$
on data parameterized by $v$. If _i.i.d._ samples $(v_{t})_{t\geqslant 0}$ of
law $\pi$ and their corresponding gradient estimates $(\nabla f_{v_{t}})$ were
accessible, one could directly apply SGD-like algorithms, that have proved to
be efficient in large scale machine learning problems (Bottou et al., 2018).
We however consider in this paper a different setting: we assume the existence
of a Markov chain $(v_{t})$ of state space $\mathcal{V}$ and stationary
distribution $\pi$. The optimizer may then use biased stochastic gradients
along the path of this Markov chain to perform incremental updates. She may
for instance use the _Markov chain SGD_ (MC-SGD) algorithm, defined through
the following recursion:

$\mathbf{x}_{t+1}=\mathbf{x}_{t}-\gamma\nabla f_{v_{t}}(\mathbf{x}_{t})\,.$
(2)

Being “ergodically unbiased”, such iterates should behave closely to those of
vanilla SGD. The analysis is however notoriously difficult, since in (2),
variable $\mathbf{x}_{t}$ and the current state of the Markov chain $v_{t}$
are not independent, so that $\mathbb{E}\left[\nabla
f_{v_{t}}(\mathbf{x}_{t})|\mathbf{x}_{t}\right]$ can be arbitrarily far from
$\nabla f(\mathbf{x}_{t})$. This paper focuses on analyzing algorithms that
incrementally sample stochastic gradients alongside the Markov chain
$(v_{t})$, motivated by the following applications.

###  1.1 Token algorithms

Traditional machine learning optimization algorithms require data
centralization, raising scalability and privavy issues, hence the alternative
of Federated Learning, where users’ data is held on device, and the training
is orchestrated at a server level. Decentralized optimization goes further, by
removing the dependency over a central entity, leading to increased
scalability, privacy and robustness to node failures, broadening the range of
applications to IoT (Internet of Things) networks. In decentralized
optimization, users (or agents) are represented as nodes of a connected graph
$G=(\mathcal{V},\mathcal{E})$ over a finite set of users $\mathcal{V}$ (of
cardinality $n$). The problem considered is then the minimization of

$f(\mathbf{x})=\frac{1}{n}\sum_{v\in\mathcal{V}}f_{v}(\mathbf{x})\,,\quad\mathbf{x}\in\mathbb{R}^{d}\,,$
(3)

where each $f_{v}$ is locally held by user $v\in\mathcal{V}$, using only
communications between neighboring agents in the graph. There are several
known decentralized algorithmic approaches to minimize $f$ under these
constrains. The prominent one consists in alternating between communications
using gossip matrices (Boyd et al., 2006; Dimakis et al., 2010) and local
gradient computations, until a consensus is reached. These gossip approaches
suffer from a high synchronization cost (nodes in the graph are required to
perform simultaneous operations, or to be aware of operations at the other end
of the communication graph) that can be prohibitive if we aim at removing the
dependency on a centralized orchestrator. Further, a high number of
communications are required to reach consensus, whether all nodes in the graph
(as in synchronous gossip) or only two neighboring ones (as in randomized
gossip) communicate at each iteration. To alleviate these communication
burdens, based on the original works of Lopes and Sayed (2007); Johansson et
al. (2007; 2010), we study algorithms based on Markov chain SGD: a variable
$\mathbf{x}$ performs a random walk on graph $G$, and is incrementally updated
at each step of the random walk, using the local function available at its
location. This approach thus boils down to the one presented above with the
function defined in (1), where $\mathcal{V}$ is the (finite) set of agents,
$\pi$ is the uniform distribution over $\mathcal{V}$, and $(v_{t})$ is the
Markov chain consisting of the consecutive states of the random walk performed
on graph $G$. The random walk guarantees that every communications are spent
on updating the global model, as opposed to gossip-based algorithms, where
communications are used to reach a running consensus while locally performing
gradient steps.

These algorithms are referred to as _token algorithms_ : a token (that
represents the model estimate) randomly walks the graph and performs updates
during its walk. There are two directions to design and analyze token
algorithms. Johansson et al. (2007) designed and analyzed its algorithm using,
based on SGD with subdifferentials and a Markov chain sampling (consisting of
the random walk). Following works (Duchi et al., 2011; Sun et al., 2018) tried
to improve convergence guarantees of such stochastic gradient algorithms with
Markov chain sampling, under various scenarii (mirror SGD _e.g._). However,
all these analyses rely on overly strong assumption: bounded gradients and/or
bounded domains are assumed, and the rates obtained are of the form $\tau_{\rm
mix}/T+\sqrt{\tau_{\rm mix}/T}$ for a number $T$ of steps, where $\tau_{\rm
mix}$ is the mixing time of the underlying Markov chain. More recently,
Dorfman and Levy (2022) obtained similar rates under similar assumptions
(bounded losses and gradients), but without requiring any prior knowledge of
$\tau_{\rm mix}$, using adaptive stepsizes.

A more recent approach consists in deriving token algorithms from Lagrangian
duality and from variants of coordinate gradient methods or ADMM algorithms
with Markov chain sampling. Mao et al. (2020) introduce the _Walkman_
algorithm, whose analysis works on any graph, and obtain rates of
$\frac{\tau_{\rm mix}^{2}n}{T}$ to reach approximate-stationary points, while
Hendrikx (2022) introduced a more general framework, but whose analysis only
works on the complete graph (and is thus equivalent to an _i.i.d._ sampling).
Yet, Hendrikx (2022) extend their analysis to arbitrary graph, by performing
gradient updates every $\tau_{\rm mix}$ steps of the random walk, obtaining a
a dependency on $\tau_{\rm mix}n$, making their algorithm state of the art for
these problems. Altenatively, Wang et al. (2022) studies the algorithm
stability of MC-SGD in order to derive generalization upper-bounds for this
algorithm, and Sun et al. (2022) provides and studies adaptive token
algorithms. Recently, and concurrently to this work, Doan (2023) also studies
MC-SGD without smoothness; however, their dependency on the mixing time of the
random walk (in their Theorem 1) scales as $\exp(c\tau_{{\rm mix}})$: this is
prohibitive as soon as the mixing time becomes larger than $\mathcal{O}(1)$.

In summary, current token algorithms and their analyses either rely on strong
noise and regularity assumptions (_e.g._ bounded gradients), or suffer from an
overly strong dependency on Markov chain-related quantities (as in Mao et al.
(2020); Hendrikx (2022)).

The token algorithms we consider are to be put in contrast with _consensus-
based decentralized_ algorithms, or _gossip_ algorithms (with fixed gossip
matrices (Dimakis et al., 2010) or with randomized pairwise communications
(Boyd et al., 2006)). They originally were introduced to compute the global
average of local vectors through peer-to-peer communication. Among the
classical decentralized optimization algorithms, some alternate between gossip
communications and local steps (Nedic and Ozdaglar, 2009; Koloskova et al.,
2019; 2020), others use dual formulations and formulate the consensus
constraint using gossip matrices to obtain decentralized dual or primal-dual
algorithms (Scaman et al., 2017; Hendrikx et al., 2019; Even et al., 2021a;
Kovalev et al., 2021; Alghunaim and Sayed, 2019), and benefit from natural
privacy amplification mechanisms (Cyffers et al., 2022). Other approaches
include non-symetric communication matrices (Assran and Rabbat, 2021) that are
more scalable. We refer the reader to Nedic et al. (2018) for a broader survey
on decentralized optimization. The works we relate to in this line of research
are Koloskova et al. (2020), where a unified analysis of decentralized SGD is
performed (the “gossip equivalent” of our algorithm MC-SGD), and in particular
contains rates for convex-non-smooth functions, and Yu et al. (2019), that
performs an analysis of decentralized SGD with momentum in the smooth-non-
convex case, which is the “gossip equivalent” of our algorithm MC-SAG.

###  1.2 Reinforcement Learning problems and online system identification

In several applications (RL, time-series analysis _e.g._), a statistician may
have access to values $(X_{t})_{t\geqslant 0}$ generated sequentially along
the path of a Markov chain, observations from which she wishes to estimate a
parameter For instance, Kowshik et al. (2021) consider a sequence of
observations $X_{t+1}=A_{\star}X_{t}+\xi_{t}$ for $\xi_{t}$ _i.i.d._ centered
noise, and $A_{\star}$ to estimate, and aim at finding $\hat{A}$ minimizing
the MSE
$\mathbb{E}\left[{{\left\|\sum_{t<T}(\hat{A}-A_{\star})X\right\|}}\right]$
where $X\sim\pi$ is the stationary distribution. Studying this problem under
the lens of stochastic optimization, this boils down to building efficient
strategis for SGD under Markov chain sampling, beyond the case of linear mean-
squared regressions studied in Kowshik et al. (2021). While optimal offline
policies have extensively been studied in this setting (Jedra and Proutiere,
2019; Simchowitz et al., 2018), online algorithms that take the form of SGD-
like algorithms have received little attention, and only focus on the case of
quadratic losses with Markov chain as described above. However, these analyses
only focus on least squares and Markov chains of the form
$X_{t+1}=A_{\star}X_{t}+\eta_{t}$. Under these specific assumptions, Nagaraj
et al. (2020) prove that a dependency on $\tau_{\rm mix}$ for MC-SGD is
inevitable, while using reverse-experince replay, Kowshik et al. (2021) breaks
this and obtain sample-optimal online algorithms. Their algorithm however
require to store a number of iterates that grow linearly with $\tau_{\rm
mix}$.

The convergence guarantees we prove in the sequel for SGD under Markov chain
sampling fit in this online framework, and refine previous analyses by
removing strong regularity assumptions such as bounded iterates or bounded
gradients (Sun et al., 2018), or strong assumptions on the Markovian structure
data and least-squares problems (Nagaraj et al., 2020; Kowshik et al., 2021).

Finally, note that in our setting, the iterates of the algorithms considered
(denoted as $(\mathbf{x}_{k})_{k\geqslant 0}$) and the Markov chain
$(v_{k})_{k\geqslant 0}$ are dependent of each other. More precisely,
$(v_{k})_{k\geqslant 0}$ is a Markov chain whose states do not depend on the
iterate sequence, while $\mathbf{x}_{k}$ is $(v_{\ell})_{\ell\leqslant
k-1}$-measurable. This setting is sometimes referred to as _exogenous Markov
noise_ Rust (1986). Another line of works, pioneered by Benveniste et al.
(1990), considers Markov transitions for $(v_{k})$ where $v_{k+1}|v_{k}$ is
sampled using a Markov transition kernel
$P_{\mathbf{x}_{0},\ldots,\mathbf{x}_{k-1}}$ that is directly linked to the
iterates. This orthogonal line of work of stochastic approximation with
Markovian noise is related to sampling (through the MCMC algorithm), adaptive
filtering, and other related problems that involve exploration Brown and Rutan
(1985); Andrieu et al. (2005); Andrieu and Moulines (2006); Fort et al.
(2016); Blanke and Lelarge (2023). Our work aims at finding precise rates of
convergence as in the convex or non-convex optimization literature Bubeck
(2015); Carmon et al. (2021), under the mildest assumptions on the exogenous
Markov-chain $(v_{k})_{k\geqslant 0}$.

Before unrolling our results, we start by reminding definitions and results
related to Markov chain theory in Section 2, before presenting our
contributions in Section 3

##  2 Markov chains preliminaries

We refer the interested reader to Levin et al. (2006) for a thorough
introduction to Markov chain theory. In this section, we define mixing,
hitting and cover times for a Markov chain on a finite space set $\mathcal{V}$
of cardinality $n$. However, note that these definitions can be extended to
the more general setting where $\mathcal{V}$ is infinite (either countable or
not). We focus on Markov chain on finite state spaces, but note that the
mixing time of a Markov chain can similarly be defined on inifinite state
spaces (countable and continuous state spaces). In this paper, all results
that involve only the mixing time of the Markov chain (the results from
Section 5) easily generalize to infinite state spaces.

######  Definition 1.

Let $P\in\mathbb{R}^{\mathcal{V}\times\mathcal{V}}$ be a stochastic matrix
(_i.e._ $P_{v,w}\geqslant 0$ for all $v,w\in\mathcal{V}$ and
$\sum_{w\in\mathcal{V}}P_{v,w}=1$ for all $v\in\mathcal{V}$). A time-
homogeneous Markov chain on $\mathcal{V}$ of transition matrix $P$ is a
stochastic process $(X_{t})_{t\geqslant 0}$ with values in $\mathcal{V}$ such
that, for any $t\geqslant 0$ and $w,v_{0},\ldots,v_{t-1},v\in\mathcal{V}$,

$\mathbb{P}\left(X_{t+1}\\!\\!=w|X_{t}\\!=\\!v,X_{t-1}\\!=\\!v_{t-1},\ldots,X_{0}\\!=\\!v_{0}\right)=P_{v,w}\,.$

A Markov chain of transition matrix $P$ is irreducible if, for any
$v,w\in\mathcal{V}$, there exists $t\geqslant 0$ such that $(P^{t})_{vw}>0$. A
Markov chain of transition matrix $P$ is aperiodic if there exists $t_{0}>0$
such that for all $t\geqslant t_{0}$ and $v,w\in\mathcal{V}$,
$(P^{t})_{v,w}>0$. Any irreducible and aperiodic Markov chain on $\mathcal{V}$
admits a stationary distribution $\pi$, that verifies $\pi P=\pi$. It finally
holds that, if $P$ is reversible ($\pi_{v}P_{v,w}=\pi_{w}P_{w,v}$ for all
$v,w\in\mathcal{V}$), denoting as $\lambda_{P}=1-\max_{\lambda\in{\rm
Sp}(P)\setminus{{\left\\{1\right\\}}}}|\lambda|>0$ the absolute spectral gap
of $P$, where ${\rm Sp}(P)$ is the spectrum of $P$, for any stochastic vector
$\pi_{0}\in\mathbb{R}^{\mathcal{V}}$: 111we write
${{\left\|z\right\|}}_{\pi}^{2}=\sum_{v\in\mathcal{V}}\pi_{v}z_{v}^{2}$ for
$z\in\mathbb{R}^{\mathcal{V}}$, and ${{\left\|\cdot\right\|}}$ always stands
for the Euclidean norm

${{\left\|\pi_{0}P^{t}-\pi\right\|}}_{\pi}\leqslant(1-\lambda_{P})^{t}{{\left\|\pi_{0}-\pi\right\|}}_{\pi}\,.$

If the chain is not reversible, there is still a linear decay, but in terms of
total variation distance rather than in the norm
${{\left\|\cdot\right\|}}_{\pi}$ (Chapter 4.3 of Levin et al. (2006)). In the
sequel, $(v_{t})_{t\geqslant 0}$ is any irreducible aperiodic Markov chain of
transition matrix $P$ on $\mathcal{V}$ of stationary distribution $\pi$ (not
necessarily the uniform distribution on $\mathcal{V}$).

Furthermore, we define the graph $G=(\mathcal{V},\mathcal{E})$ over the state
space $\mathcal{V}$ through the relation ${\\{v,w\\}}\in\mathcal{E}\iff
P_{v,w}>0$ for $v$ and $w$ two distinct states. Consequently, the Markov chain
$(v_{t})_{t}$ can also be seen as a random walk on graph $G$, with transition
probability $P$. In the random walk decentralized optimization case, this
graph coincides with the communication graph. In the sequel, for $t\geqslant
0$ and $v\in\mathcal{V}$, $\mathbb{E}\left[\cdot|v_{t}=v\right]$ and
$\mathbb{P}\left(\cdot|v_{t}=v\right)$ respectively denote the expectation and
probability conditioned on the event $v_{t}=v$. Similarly for $\pi_{t}$ a
probability distribution on $\mathcal{V}$,
$\mathbb{E}\left[\cdot|v_{t}\sim\pi_{t}\right]$ and
$\mathbb{P}\left(\cdot|v_{t}\sim\pi_{t}\right)$ refers to conditioning on the
law of $v_{t}$.

######  Definition 2 (Mixing, hitting and cover times).

For $w\in\mathcal{V}$, let $\tau_{w}=\inf{{\left\\{t\geqslant
1\,|\,v_{t}=w\right\\}}}$ be the time the chain reaches $w$ (or returns to
$w$, in the case $v_{0}=w$). We define the following quantities.

  1. 1.

_Mixing time._ For $\varepsilon>0$, the mixing time $\tau_{\rm
mix}(\varepsilon)$ of $(v_{t})$ is defined as, where ${\rm d}_{\rm TV}$ is the
total-variation distance:

$\tau_{\rm mix}(\varepsilon)=\inf{{\left\\{t\geqslant
1\,|\,\forall\pi_{0}\,,{\rm d}_{\rm
TV}(P^{t}\pi_{0},\pi)\leqslant\varepsilon\right\\}}}\,,$

and we define the mixing time $\tau_{\rm mix}$ as $\tau_{\rm mix}=\tau_{\rm
mix}(\pi_{\min}/2)$ 222this definition of mixing time is not standard: Levin
et al. (2006) define it as $\tau_{\rm mix}(1/4)$, Mao et al. (2020) define it
as we do; however, as explained in Chapter 4.5 of Levin et al. (2006), these
definitions are equivalent up to a factor $\ln(1/\pi_{\min})$ where
$\pi_{\min}=\min_{v\in\mathcal{V}}\pi_{v}$.

  2. 2.

_Hitting and cover times._ The hitting time $\tau_{\rm hit}$ and cover time
$\tau_{\rm cov}$ of $(v_{t})$ are defined as:

$\displaystyle\tau_{\rm hit}$
$\displaystyle=\max_{(v,w)\in\mathcal{V}^{2}}\mathbb{E}\left[\tau_{w}|v_{0}=v\right]\,,$
$\displaystyle\tau_{\rm cov}$
$\displaystyle=\max_{v\in\mathcal{V}}\mathbb{E}\left[\max_{w\in\mathcal{V}}\tau_{w}|v_{0}=v\right]\,.$

The mixing time is the number of steps of the Markov chain required for the
distribution of the current state to be close to the stationary probability
$\pi$. Starting from any arbitrary $v_{0}$, the hitting time bounds the time
it takes to reach any fixed $w$, while the cover time bounds the number of
steps required to visit all the nodes in the graph.

Note that if the chain is reversible, $\tau_{\rm mix}(\varepsilon)$ is closely
related to $\lambda_{P}$ through $\tau_{\rm
mix}(\varepsilon)\leqslant\lceil\lambda_{P}^{-1}\ln(\pi_{\min}^{-1}\varepsilon^{-1})\rceil$.
Under reversibility assumptions, we defined the _relaxation time_ of the
Markov chain as $\tau_{\rm rel}=1/\lambda_{P}$. More generally without
reversibility, $\tau_{\rm
mix}(\varepsilon)\leqslant\lceil\log_{2}(1/\varepsilon)\rceil\tau_{\rm
mix}(1/4)$. Then, as we prove in Appendix A, $\tau_{\rm hit}$ always satisfies
$\tau_{\rm hit}\leqslant 2\pi_{\min}^{-1}\tau_{\rm mix}$. Finally, using
Matthews (1988)’ method (detailed in Chapter 11.4 of Levin et al. (2006)), we
have $\tau_{\rm cov}\leqslant\ln(n)\tau_{\rm hit}$.

##  3 Contributions

In our paper, we analyze theoretically stochastic gradient methods with Markov
chain sampling (such as MC-SGD in Equation (2)), and aim at deriving
complexity bounds under the mildest assumptions possible. We first derive in
Section 4 complexity lower bounds for such methods, making appear $\tau_{\rm
hit}$ as the Markov chain quantity that slows down such algorithms.

We then study MC-SGD under various regularity assumptions in Section 5: we
remove the bounded gradient assumption of all previous analyses, obtain rates
under a $\mu$-PL assumption, and prove a linear convergence in the
interpolation regime, where noise and function dissimilarities only need to be
bounded at the optimum.

In the data-heterogeneous setting (functions $f_{v}$ that can be arbitrarily
dissimilar) and in the case where $\mathcal{V}$ (the state space of the Markov
chain) is finite, we introduce MC-SAG in Section 6, a variance-reduced
alternative to MC-SGD, that is perfectly suited to decentralized optimization.
Using time adaptive stepsizes, this algorithm has a rate of convergence of
$\tau_{\rm hit}/T$ and thus matches that of our lower bound, up to
acceleration.

We discuss in Section 7 the implications of our results. In particular, we
prove that random-walk based decentralization is more communication efficient
than consensus-based approaches; prior to our analysis, this was only shown
empirically (Mao et al., 2020; Johansson et al., 2010). Further, our results
formally prove that using all gradients along the Markov chain trajectory
leads to faster rates; as in the previous case, this was only empirically
observed before (Sun et al., 2018). These two consequences are derived from
the fact that MC-SAG depends only on $\tau_{\rm hit}$ rather than the
traditionally used quantity $n\tau_{\rm mix}$, that can be arbitrarily bigger
(Table 2).

##  4 Oracle complexity lower bounds under Markov chain sampling

In this section, we provide oracle complexity lower bounds for finding
stationary points of the function $f$ defined in (3), for a class of
algorithms that satisfy a “Markov sampling scheme”. For a given Markov chain
$(v_{t})$ on $\mathcal{V}$, we consider algorithms verifying the following
procedural constraints, for some fixed initialization
$\mathcal{M}_{0}={{\left\\{\mathbf{x}_{0}\right\\}}}$ an then for $t\geqslant
0$,

  1. 1.

A iteration $t$, the algorithm has access to function $f_{v_{t}}$ and may
extend its memory:

$\mathcal{M}_{t+1}={\rm Span}({{\left\\{\mathbf{x}\,,\,\nabla
f_{v_{t}}(\mathbf{x})\,,\quad\mathbf{x}\in\mathcal{M}_{t}\right\\}}})\,.$

  2. 2.

Output: the algorithm specifies an output value
$\mathbf{x}_{t}\in\mathcal{M}_{t}$.

We call algorithms verifying such constraints “black box procedures with
Markov sampling $(v_{t})$”. Such procedures as well as the result below are
inspired by the distributed black-box procedures defined in Scaman et al.
(2017). We use the notation $a(\cdot)=\Omega(b(\cdot))$ for $\exists C>0$ such
that $a(\cdot)\geqslant Cb(\cdot)$ in the theorem below, and classically
consider the limiting situation $d\to\infty$, by assuming we are working in
$\ell_{2}={{\left\\{(\theta_{k})_{k\in\mathbb{N}}\in\mathbb{R}^{\mathbb{N}}:\sum_{k}\theta_{k}^{2}<\infty\right\\}}}$.

######  Theorem 1.

Assume that $\tau_{v}$ (see Definition 2) has finite second moment for any
$v\in\mathcal{V}$. Let $\Delta,B>0$, $L>0$ and $\mu>0$, denote $\kappa=L/\mu$.
Let $\mathbf{x}_{0}$ be fixed.

  1. 1.

_Non-convex lower bound:_ there exist functions $(f_{v})_{v\in\mathcal{V}}$
such that $f=\sum_{v\in\mathcal{V}}\pi_{v}f_{v}$ is $L$-smooth, and
$f(\mathbf{x}_{0})-\min_{\mathbf{x}}f(\mathbf{x})\leqslant\Delta$ and such
that for any $T$ and any Markov black-box algorithm that outputs
$\mathbf{x}_{T}$ after $T$ steps, we have:

${{\left\|\nabla
f(\mathbf{x}_{T})\right\|}}^{2}=\Omega\left(L\Delta\left(\frac{\tau_{\rm
hit}}{T}\right)^{2}\right)\,.$

  2. 2.

_Convex lower bound:_ there exist functions $(f_{v})_{v\in\mathcal{V}}$ such
that $f=\sum_{v\in\mathcal{V}}\pi_{v}f_{v}$ is convex and $L$-smooth and
minimized at some $\mathbf{x}^{\star}$ that verifies
${{\left\|\mathbf{x}^{0}-\mathbf{x}^{\star}\right\|}}^{2}\leqslant B^{2}$, and
such that for any $T$ and any Markov black-box algorithm that outputs
$\mathbf{x}_{T}$ after $T$ steps, we have:

$f(\mathbf{x}_{T})-f(\mathbf{x}^{\star})=\Omega\left(LB^{2}\left(\frac{\tau_{\rm
hit}}{T}\right)^{2}\right)\,.$

  3. 3.

_Strongly convex lower bound:_ there exist functions
$(f_{v})_{v\in\mathcal{V}}$ such that $f=\sum_{v\in\mathcal{V}}\pi_{v}f_{v}$
is $\mu$-strongly convex and $L$-smooth and minimized at some
$\mathbf{x}^{\star}$ that verifies
${{\left\|\mathbf{x}^{0}-\mathbf{x}^{\star}\right\|}}^{2}\leqslant B^{2}$, and
such that for any $T$ and any Markov black-box algorithm that outputs
$\mathbf{x}^{T}$ after $T$ steps, we have:

$f(\mathbf{x}_{T})-f(\mathbf{x}^{\star})=\Omega\left(LB^{2}\exp\left(-\frac{T}{\sqrt{\kappa}\tau_{\rm
hit}}\right)\right)\,.$

A complete proof can be found in Appendix B. The hitting time of the Markov
chain bounds, starting from any point in $\mathcal{V}$, the mean time it takes
to reach any other state in the graph. Making no other assumptions than
smoothness, having rates that depend on this hiting time is thus quite
intuitive.

##  5 Analysis of Markov-Chain SGD

We have shown in last subsection that, in order to reach an
$\varepsilon$-stationary point with Markov sampling, the optimizer is slowed
down by the hitting time of the Markov chain; this lower bound being worst-
case on the functions $(f_{v})$, we here add additional similarity
assumptions, that are still milder than classical ones in this setting Sun et
al. (2018).Studying the iterates generated by (2), we obtain in this section a
dependency on $\tau_{\rm mix}$, provided bounded gradient dissimilarities
(Assumptions 1 and 3).

We here assume that $(v_{t})_{t\geqslant 0}$ is a Markov chain on
$\mathcal{V}$ of invariant probability $\pi$ (not necessarily the uniform
measure on $\mathcal{V}$). Our analysis of Markov chain SGD does not rely on
finite state spaces: $\mathcal{V}$ is not assumed to be finite (it can be any
infinite countable, or continuous space). In this section, the function $f$
studied is defined as

$f(\cdot)=\mathbb{E}_{v\sim\pi}[f_{v}(\cdot)]\,,$

as in (1). Consequently, for the MC-SGD algorithm for decentralized
optimization over a given graph $G$ to minimize the averaged function over all
nodes (as in (3)), $\pi$ needs to be the uniform probability over
$\mathcal{V}$.

We first derive convergence rates under smoothness assumptions with or without
a $\mu$-PL inequality that holds, before improving our results under strong
convexity assumptions, under which we prove a linear convergence rate in the
interpolation regime. We finally add local noise (due to sampling, or additive
gaussian noise to enforce privacy) in the final paragraph of this Section.

###  5.1 Analysis under bounded gradient dissimilarities

######  Assumption 1.

There exists $(\sigma^{2}_{v})_{v\in\mathcal{V}}$ such that for all
$v\in\mathcal{V}$ and all $\mathbf{x}\in\mathbb{R}^{d}$, we have333this
assumption could be replaced by a more relaxed noise assumption of the form
${{\left\|\nabla f_{v}(\mathbf{x})-\nabla f(\mathbf{x})\right\|}}^{2}\leqslant
M{{\left\|\nabla f(\mathbf{x})\right\|}}^{2}+\sigma^{2}_{v}$:

${{\left\|\nabla f_{v}(\mathbf{x})-\nabla
f(\mathbf{x})\right\|}}^{2}\leqslant\sigma^{2}_{v}\,,$

and we denote
$\bar{\sigma}^{2}=\mathbb{E}_{v\sim\pi}\left[\sigma_{v}^{2}\right]$ and
$\sigma_{\max}^{2}=\max_{v\in\mathcal{V}}\sigma_{v}^{2}$.

######  Assumption 2.

Each $f_{v}$ is $L$-smooth, $f$ is lower bounded, its minimum is attained at
some $\mathbf{x}^{\star}\in\mathbb{R}^{d}$.

######  Theorem 2 (MC-SGD).

Assume that Assumptions 1 and 2 hold, and let $\Delta\geqslant
f(\mathbf{x}_{0})-f(\mathbf{x}^{\star})+\sigma_{\max}^{2}/L$.

  1. 1.

For a constant time-horizon dependent step size $\gamma$ (_i.e._ , $\gamma$ is
a functiion of $T$), the iterates generated by Equation (2) satisfy, for
$T\geqslant 2\tau_{{\rm mix}}\ln(\tau_{\rm mix})$: 444$\tilde{\mathcal{O}}$
hides logarithmic factors

$\mathbb{E}{{\left\|\nabla
f(\hat{\mathbf{x}}_{T})\right\|}}^{2}\\!=\\!\tilde{\mathcal{O}}\\!\left(\frac{\Delta
L\tau_{\rm mix}}{T}+\frac{\sqrt{L\Delta\bar{\sigma}^{2}\tau_{\rm
mix}}+\bar{\sigma}^{2}}{\sqrt{T}}\right)\,,$

where $\hat{\mathbf{x}}_{T}$ is drawn uniformly at random amongst
$\mathbf{x}_{0},\ldots,\mathbf{x}_{T-1}$.

  2. 2.

If $f$ additionally verifies a $\mu$-PL inequality (for any
$\mathbf{x}\in\mathbb{R}^{d}$, ${{\left\|\nabla
f(\mathbf{x})\right\|}}^{2})\geqslant
2\mu(f(\mathbf{x})-f(\mathbf{x}^{\star}))$), for a constant time-horizon
dependent step size $\gamma$, the iterates generated by Equation (2) satisfy,
for $T\geqslant 2\tau_{{\rm mix}}\ln(\tau_{\rm mix})$ a numerical constant
$c>0$, and $\kappa=L/\mu$, with
$F_{T}=\mathbb{E}\left[f(\mathbf{x}_{T})-f(\mathbf{x}^{\star})\right]$:

$F_{T}\leqslant e^{-\frac{cT}{\kappa\tau_{\rm
mix}\ln(T)}}\Delta+\tilde{\mathcal{O}}\left(\frac{\tau_{\rm
mix}\bar{\sigma}^{2}}{\mu T}\right)\,,$

Theorem 2 is proved in Appendix C, by enforcing a delay of order $\tau_{\rm
mix}$ and relying on recent analyses of delayed SGD and SGD with biased
gradients. As explained in the introduction, removing the bounded gradient
assumption present in previous works (Johansson et al., 2010; Sun et al.,
2018; Duchi et al., 2011) that study Markov chain SGD (in the mirror setting,
or with subdifferentials), and replacing it by a much milder and classical
assumption of bounded gradient dissimilarities (Karimireddy et al., 2020), we
thus still managed to obtain similar rates. Further, if $f$ verifies a
$\mu$-PL inequality (if for any $\mathbf{x}\in\mathbb{R}^{d}$,
${{\left\|\nabla f(\mathbf{x})\right\|}}^{2})\geqslant
2\mu(f(\mathbf{x})-f(\mathbf{x}^{\star}))$), we have an almost-linear rate of
convergence: this is the first rate under $\mu$-PL or strong convexity
assumptions for MC-SGD-like algorithms, that we even refine further in next
subsection.

###  5.2 Tight rates and linear convergence in the interpolation regime

We now study MC-SGD under the following assumptions, to derive faster rates,
that only depend on the sampling noise at the optimum. The interpolation
regime – often related to overparameterization – refers to the case where
there exists a model $\mathbf{x}^{\star}\in\mathbb{R}^{d}$ minimizing all
$f_{v}$ for $v\in\mathcal{V}$, leading to $\sigma_{\star}^{2}=0$ in Assumption
4, and to a linear convergence rate below.

######  Assumption 3.

Functions $f_{v}$ are $L$-smooth and $\mu$-strongly convex. We denote
$\kappa=L/\mu$.

######  Assumption 4 (Noise at the optimum).

Let $\mathbf{x}^{\star}$ be a minimizer of $f$. We assume that for some
$\sigma_{\star}\geqslant 0$, we have for all $v\in\mathcal{V}$:

${{\left\|\nabla
f_{v}(\mathbf{x}^{\star})\right\|}}^{2}\leqslant\sigma_{\star}^{2}\,.$

######  Theorem 3 (Unified analysis).

Under Assumptions 3 and 4, the sequence generated by (2) satisfies, if $\gamma
L<1$:

$\displaystyle\mathbb{E}\left[{{\left\|\mathbf{x}_{T}-\mathbf{x}^{\star}\right\|}}^{2}\right]\leqslant
2(1-\gamma\mu)^{T}{{\left\|\mathbf{x}_{0}-\mathbf{x}^{\star}\right\|}}^{2}$
$\displaystyle+2\frac{\gamma^{3}TL}{\mu}\sum_{0\leqslant s\leqslant
T}(1-\gamma\mu)^{T-s}\mathbb{E}\left[{{\left\|\sum_{s\leqslant t<T}\nabla
f_{v_{t}}(\mathbf{x}^{\star})\right\|}}^{2}\right]\,.$

In the interpolation regime, $\nabla f_{v}(\mathbf{x}^{\star})=0$ for all
$v\in\mathcal{V}$, so that:

$\mathbb{E}\left[{{\left\|\mathbf{x}_{T}-\mathbf{x}^{\star}\right\|}}^{2}\right]\leqslant
2(1-\gamma\mu)^{T}{{\left\|\mathbf{x}_{0}-\mathbf{x}^{\star}\right\|}}^{2}\,.$

The result in Theorem 3 is in fact true irrespectively of the sequence
$(v_{t})$ chosen: it does not require $(v_{t})$ to specifically be a Markov
chain. This property is used in the next Corollary, that also highlights the
fact that by studying distance to the optimum, a condition number is lost in
the process. This is the case in many previous analyses of other different
algorithms (_e.g._ , Bregman/Mirror-SGD (Dragomir et al., 2021) or SGD with
random-resfhuffling (Mishchenko et al., 2020), which is in fact a particular
instance of MC-SGD, that our analysis recovers), that study distances to the
optimum (with respect to some mirror map, in the case of Mirror SGD), and
therefore obtain an extra $\kappa$ factor in the noise term. Theorem 3 is
proved by generalizing the proof technique of Mishchenko et al. (2020) to
arbitrary orderings and for unbounded time horizons.

######  Remark 1 (Random resfhuffling).

A special case of Theorem 3 is SGD with random reshuffling. By analyzing SGD
with random-reshuffling as SGD with a Markovian ordering (on an extended state
space), Theorem 1,2 also recover rates for SGD with random reshuffling for
which we have $\tau_{\rm mix}=n$. Moreover, since Theorem 3 generalizes
Theorem 1 of Mishchenko et al. (2020), we also recover their rate as a special
case by bounding each term $\mathbb{E}\left[{{\left\|\sum_{s\leqslant
t<T}\nabla f_{v_{t}}(\mathbf{x}^{\star})\right\|}}^{2}\right]$.

We specify Theorem 3 under a Markovian sampling scheme in next corollary: the
noise term at the optimum takes the form $\tau_{\rm mix}/T$.

######  Corollary 1 (MC-SGD, interpolation).

Under Assumptions 3 and 4, for $T\geqslant 1$ and for a well chosen stepsize
$\gamma>0$, the iterates generated by (2) satisfy:

$\displaystyle\mathbb{E}\left[{{\left\|\mathbf{x}_{T}-\mathbf{x}^{\star}\right\|}}^{2}\right]$
$\displaystyle\leqslant
2e^{-\frac{T}{\kappa}}{{\left\|\mathbf{x}_{0}-\mathbf{x}^{\star}\right\|}}^{2}$
$\displaystyle+\tilde{\mathcal{O}}\left(\frac{L\tau_{\rm
mix}\big{(}\frac{1}{4}\big{)}\sigma_{\star}^{2}}{\mu^{3}T}\right)\,.$

This result is stronger than Theorem 2.2, for _(i)_ noise amplitude and
gradient dissimilarities only need to be bounded at the optimum; _(ii)_ the
“optimization term” (the first one) is not slowed down by the mixing time.
This comes at the cost of strong convexity assumptions, stronger than a
$\mu$-PL inequality for $f$. The term $\frac{\tau_{\rm mix}\sigma_{\star}}{T}$
cannot be removed in the general case, as next proposition shows. Hence, since
the two other terms have optimal dependency in terms of Markov-chain and noise
related quantities, our analysis ends up being sharp.

Corollary 3 together with the following proposition are an extension of
Nagaraj et al. (2020), who proved similar results for MC-SGD with constant
stepsize on least square problems on Markovian data of a certain form (for
linear online system identification).

######  Proposition 1.

For any $\mathcal{V}$ (such that $|\mathcal{V}|\geqslant 2$) and $\tau>1$,
there exists a Markov chain on $\mathcal{V}$ of relaxation time $\tau$,
functions $(f_{v})_{v\in\mathcal{V}}$ and $\mathbf{x}_{0}\in\mathbb{R}^{d}$
such that given any stepsize $\gamma$, the iterates of Equation (2) output
$\mathbf{x}_{T}$ for any $T>0$ verifying
${{\left\|\mathbf{x}_{T}-\mathbf{x}_{0}\right\|}}^{2}=\tilde{\Omega}(\tau\sigma_{\star}^{2}/T)$,
and the assumptions of Theorem 3 hold.

###  5.3 MC-SGD with local noise

In the two previous subsections, we analyzed SGD with Markovian sampling
schemes, where the stochasticity only came from the Markov chain
$(v_{k})_{k\geqslant 0}$. We now generalize the analysis and results to SGD
with both Markovian sampling, and local noise, by studying the sequence:

$\mathbf{x}_{t+1}=\mathbf{x}_{t}-\gamma_{t}\mathbf{g}_{t}\,.$ (4)

We now formulate the form stochastic gradients $\mathbf{g}_{t}$ can take.

######  Assumption 5.

For all $v\in\mathcal{V}$, the function $f_{v}$ satisfies
$f_{v}(\mathbf{x})=\mathbb{E}\left[F_{v}(\mathbf{x},\xi_{v})\right]$ for all
$\mathbf{x}\in\mathbb{R}^{d}$, where $\xi_{v}\sim\mathcal{D}_{v}$.
Furthermore, there exists a Markov-chain $(v_{t})_{t\geqslant 0}$ such that
for all $t\geqslant 0$,

$\mathbf{g}_{t}=\nabla_{\mathbf{x}}F_{v_{t}}(\mathbf{x}_{t},\xi_{t})\,,$

where $\xi_{t}\sim\mathcal{D}_{v_{t}}|v_{t}$ is independent from
$v_{0},\ldots,v_{t-1}$ and $\xi_{0},\ldots,\xi_{t-1}$.

A direct consequence of Assumption 3 is that
$\mathbb{E}\left[\mathbf{g}_{t}|\mathbf{x}_{t},v_{t}\right]=\nabla
f_{v_{t}}(\mathbf{x}_{t})$. Two main applications of Assumption 3 are:

  1. 1.

Local sampling. If
$f_{v}(\mathbf{x})=\frac{1}{m}\sum_{i=1}^{m}f_{v,i}(\mathbf{x})$ (agent $v$
has $m$ local samples), agent $m$ may use only a batch $\mathcal{B}\subset[m]$
of its samples, leading to stochastic gradients $\mathbf{g}_{t}$ in (4) of the
form:

$\mathbf{g}_{t}=\frac{1}{|\mathcal{B}_{t}|}\sum_{i\in\mathcal{B}_{t}}\nabla
f_{v_{t},i}(\mathbf{x}_{t})\,,$

for random batches $(\mathcal{B}_{t})_{t\geqslant 0}$.

  2. 2.

Differential privacy. Adding local noise (_e.g._ , additive Gaussian random
noise) enforces differential privacy under suitable assumptions. A private
decentralized token algorithm is then Differentially Private MC-SGD (DP-MC-
SGD), with iterates (4) where $\mathbf{g}_{t}$ satisfies

$\mathbf{g}_{t}=\nabla f_{v_{t}}(\mathbf{x}_{t})+\eta_{t}\,,$ (5)

where $(v_{t})$ is the Markov chain (random walk performed by the token on the
communication graph), and $\eta_{t}\sim\mathcal{N}(0,\sigma_{t}^{2}I_{d})$ is
sampled independently from the past, to enforce differential privacy.

Under Assumption 3, a direct generalization of Theorem 3 and Corollary 1 is
the following.

######  Theorem 4 (MC-SGD with local noise).

Assume that Assumptions 5,4 holds, each $F_{v}(\cdot,\xi)$ is $\mu$-strongly
convex $L$-smooth, and there exists $\sigma_{\rm local}^{2}$ such that:

$\mathbb{E}\left[{{\left\|\mathbf{g}_{t}-\nabla
f_{v_{t}}(\mathbf{x}_{t})\right\|}}^{2}|\mathbf{x}_{t},v_{t}\right]\leqslant\sigma^{2}_{\rm
local}\,.$

Then, for a well chosen $\gamma>0$, the iterates generated by (4) satisfy:

$\displaystyle\mathbb{E}\left[{{\left\|\mathbf{x}_{T}-\mathbf{x}^{\star}\right\|}}^{2}\right]$
$\displaystyle\leqslant
2e^{-\frac{T}{\kappa}}{{\left\|\mathbf{x}_{0}-\mathbf{x}^{\star}\right\|}}^{2}$
$\displaystyle+\tilde{\mathcal{O}}\left(\frac{L}{\mu^{3}T}\big{(}\sigma_{\rm
local}^{2}+\tau_{\rm
mix}\big{(}\frac{1}{4}\big{)}\sigma_{\star}^{2}\big{)}\right)\,.$

Importantly, and as one would have expected, local noise is not impacted by
the mixing time of the underlying random walk. While we did not pursue in this
direction, this observation could easily be made under other regularity
assumptions, and such a result would hold for instance under the assumptions
of Theorem 1 or 2. While Differentially Private MC-SGD sounds appealing for
performing decentralized and differentially private optimization, we here only
provided a utility analysis, the privacy analysis being left for future works.

##  6 Analysis of Markov-Chain SAG

Algorithm 1 Markov Chain SAG (MC-SAG)

1: Input: $\mathbf{x}_{0}\in\mathbb{R}^{d}$, $\mathbf{h}_{v}\in\mathbb{R}^{d}$
for $v\in\mathcal{V}$ and $\bar{\mathbf{h}}_{0}\in\mathbb{R}^{d}$, stepsizes
$\gamma_{t}>0$, $v_{0}\in\mathcal{V}$

2: for $t=0,1,\dots$ do

3: Compute $\nabla f_{v_{t}}(\mathbf{x}_{t})$

4: $\bar{\mathbf{h}}_{t+1}=\bar{\mathbf{h}}_{t}+\frac{1}{n}\big{(}\nabla
f_{v_{t}}(\mathbf{x}_{t})-\mathbf{h}_{v_{t}}\big{)}$

5: $\mathbf{x}_{t+1}=\mathbf{x}_{t}-\gamma_{t}\bar{\mathbf{h}}_{t+1}$

6: $\mathbf{h}_{v_{t}}\longleftarrow\nabla f_{v_{t}}(\mathbf{x}_{t})$

7: Sample $v_{t+1}\sim P_{v_{t},\cdot}$

8: end for

After providing convergence guarantees for the most natural algorithm (MC-SGD)
under a Markov chain sampling on the set $\mathcal{V}$, we prove that one can
achieve a rate of order $1/T$ (rather than the $1/\sqrt{T}$ previously
obtained) in the smooth setting, by applying the variance reduction techniques
present in Schmidt et al. (2017), that first introduced the Stochastic
Averaged Gradient algorithm, together with a time-adaptive stepsize policy
described below. Our faster rate with variance reduction leads of a dependency
on $\tau_{\rm hit}$ instead of $\tau_{\rm mix}$; since we do not make any
other assumption other than smoothness, this is unavoidable in light of our
lower bound (Theorem 1).

#### MC-SAG

The MC-SAG algorithm is described in Algorithm 1. The recursion leading to the
iterate $\mathbf{x}_{t}$ can then be summarized as, for stepsizes
$(\gamma_{t})_{t\geqslant 0}$, under the initialization $\mathbf{h}_{v}=\nabla
f_{v}(\mathbf{x}_{0})$ and $\bar{\mathbf{h}}=\nabla f(\mathbf{x}_{0})$:

$\mathbf{x}_{t+1}=\mathbf{x}_{t}-\frac{\gamma_{t}}{n}\sum_{v\in\mathcal{V}}\nabla
f_{v}(\mathbf{x}_{d_{v}(t)})\,,$ (6)

where for $v\in\mathcal{V}$, we define $d_{v}(t)=\sup{{\left\\{s\leqslant
t\,|\,v_{s}=v\right\\}}}$ as the last previous iterate at which $v$ was the
current state of the Markov chain. By convention, if the set over which the
supremum is taken is empty, we set $d_{v}(t)=0$. We handle both the
initialization described just above for $\mathbf{h}_{v},\bar{\mathbf{h}}$ and
arbitrary initialization in our analysis below.

In the same way that MC-SGD reduces to vanilla SGD if $(v_{t})$ is an _i.i.d._
uniform sampling over $\mathcal{V}$, MC-SAG boils down to the SAG algorithm
(Schmidt et al., 2017) in that case and under the initialization
$\mathbf{h}_{v}=\nabla f_{v}(\mathbf{x}_{0})$ and $\bar{\mathbf{h}}=\nabla
f(\mathbf{x}_{0})$. In a decentralized setting, nodes keep in mind their last
gradient computed (variable $\mathbf{h}_{v}$ at node $v$). At all times,
$\bar{\mathbf{h}}_{t}$ is an average of these $\mathbf{h}_{v}$ over the graph,
and is, in the same way as $\mathbf{x}_{t}$, updated along the random walk.
The MC-SAG algorithm is thus perfectly adapted to decentralized optimization.

#### Time-adaptive stepsize policy

To obtain our convergence guarantees, a time-adaptive stepsize policy
$(\gamma_{t})$ is used, as in Asynchronous SGD (Mishchenko et al., 2022) to
obtain delay-independent guarantees. For $t\geqslant 0$, let the stepsize
$\gamma_{t}$ be defined as:

$\gamma_{t}=\frac{1}{2L\big{(}\tau_{\rm
hit}+\max_{v\in\mathcal{V}}(t-d_{v}(t))\big{)}}\,.$ (7)

Denoting $\tau_{t}=\max_{v\in\mathcal{V}}(t-d_{v}(t))$, this quantity can be
tracked down during the optimization process. Indeed, if agent $v_{t}$
receives $\tau_{t-1}$ together with $(\mathbf{x}_{t},\bar{\mathbf{h}}_{t})$,
she may compute $\tau_{t}$ as:

$\tau_{t}=\max\big{(}\tau_{t-1}+1\,,\,t-d_{v_{t}}(t)\big{)}\,,$

where $t-d_{v_{t}}(t)$ is the number of iterations that took place since the
last time the Markov chain state was $v_{t}$. Hence, if agents keep track of
the number of iterations, the adaptive stepsize policy (7) can be used in
Algorithm 1, as long as agent $v_{t}$ sends $(\tau_{t},t)$ to $v_{t+1}$,
yielding the following result.

We now present the convergence results for MC-SAG. $(v_{t})$ is in this
section assumed to be a Markov chain on $\mathcal{V}$ of finite hitting time
$\tau_{\rm hit}$. Importantly, the next Theorem does not require any
additional assumption on $(v_{t})$ such as reversibility, or even that it has
a stationary probability that is the uniform distribution: the non-symmetric
but easily implementable transition probabilities $P_{v,w}=1/(d_{v}+1)$ for
$w=v$ or $w\sim v$ can be used here, as well as non-reversible random walks
than can have much smaller mixing and hitting times. The function $f$ studied
is here independent of the Markov chain, and is defined as in (3), the
uniformly averaged function over all states $v\in\mathcal{V}$ (or over all
agents in the network).

######  Theorem 5 (MC-SAG).

Assume that Assumption 2 holds and that the Markov chain has a finite hitting
time (for an arbitrary invariant probability).

  1. 1.

Under the initialization:

$\displaystyle\mathbf{h}_{v}$ $\displaystyle=\nabla f_{v}(\mathbf{x}_{0})\,,$
$\displaystyle\bar{\mathbf{h}}$ $\displaystyle=\nabla f(\mathbf{x}_{0})\,,$

using the adaptive stepsize policy defined in Equation (7), the sequence
generated by Algorithm 1 satisfies, for any $T>0$:

$\mathbb{E}\left[\min_{t<T}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]\leqslant
8L\big{(}f(\mathbf{x}_{0})-f(\mathbf{x}^{\star})\big{)}\frac{\tau_{\rm
hit}\ln(n)}{T}\,.$

  2. 2.

Under any arbitrary initialization that satisfies
$\bar{\mathbf{h}}=\frac{1}{n}\sum_{v\in\mathcal{V}}\mathbf{h}_{v}$, using the
adaptive stepsize policy defined in Equation (7), the sequence generated by
Algorithm 1 satisfies, for any $T>0$:

$\mathbb{E}\left[\min_{t<T}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]\leqslant 16L\Delta\frac{\tau_{\rm
hit}\ln(n)}{T}\,,$

where

$\Delta=f(\mathbf{x}_{0})-f(\mathbf{x}^{\star})+\frac{1}{8n}\sum_{v\in\mathcal{V}}{{\left\|\nabla
f_{v}(\mathbf{x}_{0})-\mathbf{h}_{v}\right\|}}^{2}\,.$

Theorem 5 is proved in Appendix 5. Up to the logarithmic factor in $n$, the
rates in Theorem 5 are the non-accelerated versions of the lower-bound in
Theorem 1.

##  7 Discussion of our results

###  7.1 Communication efficiency: comparison of our results with consensus-
based approaches

We summarize the communication efficiencies in Table 1 (in terms of total
number of communications required to reach an $\varepsilon$-stationary point),
of classical gossip-based decentralized gradient methods (non-accelerated,
since no accelerated method is known under our regularity assumptions). We
consider the algorithm of Yu et al. (2019) (decentralized SGD with momemtum,
state of the art decentralized gossip-based algorithm for this problem) with
fixed communication matrix $W$ on the graph $G$ together with the Walkman
algorithm Mao et al. (2020) and our algorithms, for a Markov chain with
transition matrix $P$. For the sake of comparison, we take as gossip matrix
$W=P$.Consequently as shown in Table 1, _our algorithm (MC-SAG) always
outperforms non-accelerated gossip-based decentralized gradient descent
algorithms in terms of number of communications required to reach
$\varepsilon$-stationary points_. Note that we do not claim the “overall
superiority” of our approach over classical decentralized optimization
algorithms (the latter benefit from parallelization while ours do not), but a
superiority in terms of communication efficiency.

Table 1:  Number of communications required (# comm. below) to obtain an
$\varepsilon$-stationary point $\mathbf{x}$ (verifying ${{\left\|\nabla
f(\mathbf{x})\right\|}}^{2}\leqslant\varepsilon$). Logarithmic/constant
factors hidden.

| A | B | Our work |
---|---|---|---|---
# comm. | $\varepsilon^{-1}|\mathcal{E}|\tau_{\rm mix}$ | $\varepsilon^{-1}n\tau_{\rm mix}^{2}$ |  |  $\varepsilon^{-2}\tau_{\rm mix}$ c
---
$\varepsilon^{-1}\tau_{\rm hit}$ d

  * •

A: Yu et al. (2019).

  * •

B: Mao et al. (2020).

  * •

c MC-SGD under Assumption 1.

  * •

d MC-SAG.

Table 2:  Hitting and mixing times of some known graphs, for the simple random walk.  | Cycle |  $d$-dim. torus | Complete graph
---|---|---|---
| $\tau_{\rm hit}$
---
$\mathcal{O}(n^{2})$ | $\mathcal{O}(n^{1+\frac{1}{d}})$ | $\mathcal{O}(n)$
| $n\tau_{\rm mix}$
---
$\mathcal{O}(n^{3})$ | $\mathcal{O}(n^{1+\frac{2}{d}})$ | $\mathcal{O}(n)$

The dependency on the quantity $\tau_{\rm hit}$ we obtain (under no other
assumptions than smoothness) is always better than the dependency on
$n\tau_{\rm mix}$ of previous works (using gossip communications or a random
walker), since $\tau_{\rm hit}\leqslant 2n\tau_{\rm mix}$ always holds. As
illustrated in Table 2 on some known graphs, this inequality is rather loose
when the connectivity decreases (_i.e._ the mixing time increases), so that
the speedup our results lead to is even more effective on ill-connected
graphs; the difference between the two can scale up to a factor $n$. In fact,
we prove in Appendix A that for $d$-regular and symetric graphs, we have:

$\tau_{\rm hit}\leqslant\frac{2|\mathcal{E}|{\rm Diam}(G)}{d}\,,$

where ${\rm Diam}$ is the diameter of $G$. The dependency $n\tau_{\rm
mix}^{2}$ obtained in Mao et al. (2020) (the only work that does not make
bounded gradient assumptions) is prohibitive when graph connectivity decreases
($n^{3}$ on the grid, $n^{5}$ on the cycle). Our analysis does not rely on a
reversibility assumption of the Markov chain, so that non symetric random
walks can be used, therefore accelerating mixing; on the cycle for a non-
symmetric random walk for instance, the hitting time decreases to
$\mathcal{O}(n)$.

###  7.2 Using all gradient along the trajectory of $(v_{t})$ is provably more
efficient

Sun et al. (2018) empirically motivated through empirical evidence the use of
all gradients $\nabla f_{v_{t}}$ sampled along the trajectory of the Markov
chain rather than waiting for the chain to mix before every stochastic
gradient step in order to mimic the behavior of vanilla SGD. However, their
rates (as well as those of Johansson et al. (2010); Duchi et al. (2011) and
ours for MC-SGD) are functions of $S=T/\tau_{\rm mix}$, and of order
$1/S+1/\sqrt{S}$. These are exactly what one would obtain, by waiting for
$\tau_{\rm mix}$ steps of the chain in order to have an approximate uniform
sampling before each update! Consequently, there are no theoretical ground or
evidence for using all the gradients along the trajectory of the Markov chain
with these results, other than by doing so, one does not do worse than waiting
for the chain to mix to mimic vanilla SGD. This is exactly the approach taken
by Hendrikx (2022): a gradient step is performed every $\tau_{\rm mix}$ random
walk steps. This is where MC-SAG and its guarantees that depend on
$T/\tau_{\rm hit}$ come in place. Under our assumptions, the rate of SAG for
finding approximate stationary points when waiting for the chain to mix before
using a stochastic gradient is of order $n/S=n\tau_{\rm mix}/T$ where
$S=T/\tau_{\rm mix}$ is the number of stochastic gradients used. We obtain
$\tau_{\rm hit}/T$ instead: hence, in cases where $\tau_{\rm hit}=o(n\tau_{\rm
mix})$, using all stochastic gradients along the trajectory of the Markov
chain - instead of waiting for mixing before performing a stochastic gradient
step - provably helps. Hence, we here provided a realistic scenario where
using all stochastic gradients proves to accelerate the rate; this was
previously noticed in another setting with RER-SGD (SGD with reverse-
experience replay, Kowshik et al. (2021)).

###  7.3 Running-time complexity and robustness to “stragglers”

The total time it takes to run random walk-based decentralized algorithms
depends on $T_{v\to w}$, the time it takes to compute a gradient at $v$, and
then the communication time to send it to $w$. Using ergodicity of the Markov
chain, the time ${\rm time}^{\rm MC}(T)$ it takes to run MC-SAG or MC-SGD for
$T$ iterations verifies:

$\frac{{\rm time}^{\rm
MC}(T)}{T}\to\sum_{(v,w)\in\mathcal{V}^{2}}\pi_{v}P_{v,w}T_{v\to w}\,,$

where the limit is a weighted sum of the local computation/communication
times, with weights summing to 1. Random-walk based decentralized algorithms
are therefore robust to slow edges or nodes (“stragglers”), a property that
synchronous gossip algorithms do not verify (their time complexity depends on
$\max_{v,w}T_{{v\to w}})$, while studying asynchronous gossip is notoriously
difficult (Even et al., 2021b).

#### Numerical illustration of our theory

We present in Appendix G two experiments on synthetic problems, comparing MC-
SAG and MC-SGD to gossip-based and token baselines. We consider two settings
(a well-connected graph with homogeneous functions, an ill-connected graph
with heterogeneous functions) in an effort to illustrate how these two
difficulties (graph connectivity and data-heterogeneity) are both bypassed by
the MC-SAG algorithm.

#### Conclusion

Without variance reduction and under bounded data-heterogeneity assumptions,
SGD under MC sampling is slowed down by a factor $\tau_{\rm mix}$, due to
increased sampling variance. Using variance-reduction techniques, we obtain
faster rates, that depend on $\tau_{\rm hit}$ rather than $n\tau_{\rm mix}$,
which one would have expected by directly extending known results in the
_i.i.d._ setting to our MC sampling schemes. Leveraging such a dependency
yields a fast token algorithm (MC-SAG), robust to both ill-connectivity of the
graph and data-heterogeneity.

#### Aknowledgments

I deeply thank Hadrien Hendrikx for many interesting discussions on the
subject and for all his help in writing this paper, as well as Anastasiia
Koloskova and Edwige Cyffers for helpful discussions.

## References

  * Alghunaim and Sayed [2019] Sulaiman A. Alghunaim and Ali H. Sayed.  Linear convergence of primal-dual gradient methods and their performance in distributed optimization, 2019.
  * Andrieu and Moulines [2006] Christophe Andrieu and Éric Moulines.  On the ergodicity properties of some adaptive MCMC algorithms.  _The Annals of Applied Probability_ , 16(3), August 2006\.
  * Andrieu et al. [2005] Christophe Andrieu, Éric Moulines, and Pierre Priouret.  Stability of stochastic approximation under verifiable conditions.  _SIAM Journal on Control and Optimization_ , 44(1):283–312, January 2005.
  * Assran and Rabbat [2021] Mahmoud S. Assran and Michael G. Rabbat.  Asynchronous gradient push.  _IEEE Transactions on Automatic Control_ , 66(1):168–183, 2021.
  * Benveniste et al. [1990] Albert Benveniste, Michel Métivier, and Pierre Priouret.  _Adaptive Algorithms and Stochastic Approximations_.  Springer Berlin Heidelberg, 1990.
  * Blanke and Lelarge [2023] Matthieu Blanke and Marc Lelarge.  Flex: an adaptive exploration algorithm for nonlinear systems.  In _International Conference on Machine Learning_ , 2023.
  * Bottou et al. [2018] Léon Bottou, Frank E. Curtis, and Jorge Nocedal.  Optimization methods for large-scale machine learning.  _SIAM Review_ , 60(2):223–311, January 2018\.
  * Boyd et al. [2006] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah.  Randomized gossip algorithms.  _IEEE transactions on information theory_ , 52(6):2508–2530, 2006.
  * Brown and Rutan [1985] S.D. Brown and S.C. Rutan.  Adaptive kalman filtering.  _Journal of Research of the National Bureau of Standards_ , 90(6):403, November 1985.
  * Bubeck [2015] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  _Found. Trends Mach. Learn._ , 8(3–4):231–357, November 2015.
  * Carmon et al. [2021] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford.  Lower bounds for finding stationary points ii: First-order methods.  _Math. Program._ , 185(1–2):315–355, jan 2021\.  ISSN 0025-5610.
  * Cyffers et al. [2022] Edwige Cyffers, Mathieu Even, Aurélien Bellet, and Laurent Massoulié.  Muffliato: Peer-to-peer privacy amplification for decentralized optimization and averaging.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, _Advances in Neural Information Processing Systems_ , 2022.
  * Defazio et al. [2014] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien.  Saga: A fast incremental gradient method with support for non-strongly convex composite objectives.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 27. Curran Associates, Inc., 2014.
  * Dimakis et al. [2010] A. G. Dimakis, S. Kar, J. M. F. Moura, M. G. Rabbat, and A. Scaglione.  Gossip algorithms for distributed signal processing.  _Proceedings of the IEEE_ , 98(11):1847–1864, 2010.
  * Doan [2023] Thinh T. Doan.  Finite-time analysis of markov gradient descent.  _IEEE Transactions on Automatic Control_ , 68(4):2140–2153, 2023.
  * Dorfman and Levy [2022] Ron Dorfman and Kfir Yehuda Levy.  Adapting to mixing time in stochastic optimization with Markovian data.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 5429–5446. PMLR, 17–23 Jul 2022.
  * Dragomir et al. [2021] Radu Alexandru Dragomir, Mathieu Even, and Hadrien Hendrikx.  Fast stochastic bregman gradient methods: Sharp analysis and variance reduction.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 2815–2825. PMLR, 18–24 Jul 2021.
  * Duchi et al. [2011] John C. Duchi, Alekh Agarwal, Mikael Johansson, and Michael I. Jordan.  Ergodic mirror descent.  In _2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pages 701–706, 2011.  doi: 10.1109/Allerton.2011.6120236.
  * Even et al. [2021a] Mathieu Even, Raphaël Berthier, Francis Bach, Nicolas Flammarion, Hadrien Hendrikx, Pierre Gaillard, Laurent Massoulié, and Adrien Taylor.  Continuized accelerations of deterministic and stochastic gradient descents, and of gossip algorithms.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 28054–28066. Curran Associates, Inc., 2021a.
  * Even et al. [2021b] Mathieu Even, Hadrien Hendrikx, and Laurent Massoulié.  Decentralized optimization with heterogeneous delays: a continuous-time approach.  Technical report, arXiv:2106.03585, 2021b.
  * Even et al. [2022] Mathieu Even, Laurent Massoulié, and Kevin Scaman.  On sample optimality in personalized collaborative and federated learning.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, _Advances in Neural Information Processing Systems_ , 2022.
  * Fort et al. [2016] G. Fort, E. Moulines, A. Schreck, and M. Vihola.  Convergence of markovian stochastic approximation with discontinuous dynamics.  _SIAM Journal on Control and Optimization_ , 54(2):866–893, January 2016.
  * Hendrikx [2022] Hadrien Hendrikx.  A principled framework for the design and analysis of token algorithms, 2022.
  * Hendrikx et al. [2019] Hadrien Hendrikx, Francis Bach, and Laurent Massoulié.  An accelerated decentralized stochastic proximal algorithm for finite sums.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Jedra and Proutiere [2019] Yassir Jedra and Alexandre Proutiere.  Sample complexity lower bounds for linear system identification.  In _IEEE Conference on decision and control (CDC) 2019_ , pages 2676–2681, 12 2019.
  * Johansson et al. [2007] Bjorn Johansson, Maben Rabi, and Mikael Johansson.  A simple peer-to-peer algorithm for distributed optimization in sensor networks.  In _2007 46th IEEE Conference on Decision and Control_ , pages 4705–4710, 2007.  doi: 10.1109/CDC.2007.4434888.
  * Johansson et al. [2010] Björn Johansson, Maben Rabi, and Mikael Johansson.  A randomized incremental subgradient method for distributed optimization in networked systems.  _SIAM Journal on Optimization_ , 20(3):1157–1170, 2010.
  * Karimireddy et al. [2020] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh.  SCAFFOLD: Stochastic controlled averaging for federated learning.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 5132–5143. PMLR, 13–18 Jul 2020.
  * Koloskova et al. [2019] Anastasia Koloskova, Sebastian Stich, and Martin Jaggi.  Decentralized stochastic optimization and gossip algorithms with compressed communication.  In _International Conference on Machine Learning_ , volume 97, pages 3478–3487. PMLR, 2019.
  * Koloskova et al. [2020] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich.  A unified theory of decentralized SGD with changing topology and local updates.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 5381–5393. PMLR, 13–18 Jul 2020.
  * Kovalev et al. [2021] Dmitry Kovalev, Elnur Gasanov, Alexander Gasnikov, and Peter Richtarik.  Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time-varying networks.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 22325–22335. Curran Associates, Inc., 2021.
  * Kowshik et al. [2021] Suhas Kowshik, Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli.  Streaming linear system identification with reverse experience replay.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 30140–30152. Curran Associates, Inc., 2021.
  * Levin et al. [2006] David A. Levin, Yuval Peres, and Elizabeth L. Wilmer.  _Markov chains and mixing times_.  American Mathematical Society, 2006.
  * Lopes and Sayed [2007] Cassio G. Lopes and Ali H. Sayed.  Incremental adaptive strategies over distributed networks.  _IEEE Transactions on Signal Processing_ , 55(8):4064–4077, 2007.  doi: 10.1109/TSP.2007.896034.
  * Mania et al. [2017] Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and Michael I. Jordan.  Perturbed iterate analysis for asynchronous stochastic optimization.  _SIAM Journal on Optimization_ , 27(4):2202–2229, January 2017.
  * Mao et al. [2020] Xianghui Mao, Kun Yuan, Yubin Hu, Yuantao Gu, Ali H. Sayed, and Wotao Yin.  Walkman: A communication-efficient random-walk algorithm for decentralized optimization.  _IEEE Transactions on Signal Processing_ , 68:2513–2528, 2020.  doi: 10.1109/TSP.2020.2983167.
  * Matthews [1988] Peter Matthews.  Covering Problems for Markov Chains.  _The Annals of Probability_ , 16(3):1215 – 1228, 1988.
  * Mei et al. [2018] Song Mei, Yu Bai, and Andrea Montanari.  The landscape of empirical risk for nonconvex losses.  _The Annals of Statistics_ , 46(6A):2747–2774, 2018.
  * Mishchenko et al. [2020] Konstantin Mishchenko, Ahmed Khaled, and Peter Richtarik.  Random reshuffling: Simple analysis with vast improvements.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 17309–17320. Curran Associates, Inc., 2020.
  * Mishchenko et al. [2022] Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake Woodworth.  Asynchronous SGD beats minibatch SGD under arbitrary delays.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, _Advances in Neural Information Processing Systems_ , 2022.
  * Nagaraj et al. [2020] Dheeraj Nagaraj, Xian Wu, Guy Bresler, Prateek Jain, and Praneeth Netrapalli.  Least squares regression with markovian data: Fundamental limits and algorithms.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 16666–16676. Curran Associates, Inc., 2020.
  * Nedic and Ozdaglar [2009] Angelia Nedic and Asuman Ozdaglar.  Distributed subgradient methods for multi-agent optimization.  _IEEE Transactions on Automatic Control_ , 54(1):48–61, 2009.  doi: 10.1109/TAC.2008.2009515.
  * Nedic et al. [2018] Angelia Nedic, Alex Olshevsky, and Michael G. Rabbat.  Network topology and communication-computation tradeoffs in decentralized optimization.  _Proceedings of the IEEE_ , 106(5):953–976, May 2018.
  * Nesterov [2014] Yurii Nesterov.  _Introductory Lectures on Convex Optimization: A Basic Course_.  Springer Publishing Company, Incorporated, 1 edition, 2014.  ISBN 1461346916.
  * Rao [2012] Shravas Rao.  Finding hitting times in various graphs, 2012.
  * Rust [1986] John Rust.  Structural estimation of markov decision processes.  In R. F. Engle and D. McFadden, editors, _Handbook of Econometrics_ , volume 4, chapter 51, pages 3081–3143. Elsevier, 1 edition, 1986\.
  * Scaman et al. [2017] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié.  Optimal algorithms for smooth and strongly convex distributed optimization in networks.  In Doina Precup and Yee Whye Teh, editors, _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 3027–3036. PMLR, 06–11 Aug 2017.
  * Schmidt et al. [2017] Mark Schmidt, Nicolas Le Roux, and Francis Bach.  Minimizing finite sums with the stochastic average gradient.  _Math. Program._ , 162(1–2):83–112, mar 2017\.  ISSN 0025-5610.
  * Simchowitz et al. [2018] Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, and Benjamin Recht.  Learning without mixing: Towards a sharp analysis of linear system identification.  In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, _Proceedings of the 31st Conference On Learning Theory_ , volume 75 of _Proceedings of Machine Learning Research_ , pages 439–473. PMLR, 06–09 Jul 2018.
  * Stich and Karimireddy [2021] Sebastian U. Stich and Sai Praneeth Karimireddy.  The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication, 2021.
  * Sun et al. [2018] Tao Sun, Yuejiao Sun, and Wotao Yin.  On markov chain gradient descent.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.
  * Sun et al. [2022] Tao Sun, Dongsheng Li, and Bao Wang.  Adaptive random walk gradient descent for decentralized optimization.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 20790–20809. PMLR, 17–23 Jul 2022.
  * Wang et al. [2022] Puyu Wang, Yunwen Lei, Yiming Ying, and Ding-Xuan Zhou.  Stability and generalization for markov chain stochastic gradient methods.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, _Advances in Neural Information Processing Systems_ , 2022.
  * Yu et al. [2019] Hao Yu, Rong Jin, and Sen Yang.  On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 7184–7193. PMLR, 09–15 Jun 2019.

##  Appendix A Preliminary results

###  A.1 Mixing time and relaxation time, mixing time and hitting time

We first begin by the two following lemmas. The first one is very classical,
and bounds the mixing time in terms of $1/\lambda_{P}$, in the case where the
chain is reversible; we provide a proof for completeness. Note that if the
chain is reversible, _we still have a linear decay_ Levin et al. [2006]. The
second lemma we provide bounds the hitting time of the Markov chain with the
mixing time. This result is somewhat less classical, and is not present in the
classical Markov chain literature surveys.

######  Lemma 1 ($\tau_{\rm mix}$ and $\lambda_{P}$).

For any $\varepsilon>0$, if the chain is reversible:

$\tau_{\rm
mix}(\varepsilon)\leqslant\left\lceil\frac{1}{\lambda_{P}}\ln(\varepsilon^{-1}\pi_{\min}^{-1})\right\rceil\,,$

so that $\tau_{\rm
mix}\leqslant\left\lceil\frac{1}{\lambda_{P}}\ln(\pi_{\min}^{-2}/2)\right\rceil$.

###### Proof.

We have:

$\displaystyle{\rm d}_{\rm TV}(P^{t}\pi_{0},\pi)$
$\displaystyle=\frac{1}{2}\sum_{w\in\mathcal{V}}|(P^{t}\pi_{0})_{w}-\pi_{w}|$
$\displaystyle\leqslant\frac{1}{2\pi_{\min}}\sum_{w\in\mathcal{V}}\pi_{w}|(P^{t}\pi_{0})_{w}-\pi_{w}|$
$\displaystyle\leqslant\frac{1}{2\pi_{\min}}\sqrt{{{\left\|P^{t}\pi_{0}-\pi\right\|}}_{\pi}^{2}}$
$\displaystyle\leqslant\frac{(1-\lambda_{P})^{t}}{2\pi_{\min}}{{\left\|\pi_{0}-\pi\right\|}}_{\pi}$
$\displaystyle\leqslant\frac{(1-\lambda_{P})^{t}}{\pi_{\min}}\,,$

so that $|(P^{t})_{v,w}-\pi_{w}|\leqslant\varepsilon$ for
$t\geqslant\lambda_{P}^{-1}\ln(\pi_{\min}^{-1}\varepsilon^{-1}/2)$. ∎

######  Lemma 2 (Mixing times and hitting times).

$\tau_{\rm hit}\leqslant 2\pi_{\min}^{-1}\tau_{\rm mix}\,,$

so that if $\pi$ is the uniform distribution over $\mathcal{V}$, $\tau_{\rm
hit}\leqslant 2n\tau_{\rm mix}$.

###### Proof.

for any $v,w\in\mathcal{V}$,

$\displaystyle\mathbb{E}\left[\tau_{w}|v_{0}=v\right]$
$\displaystyle=\sum_{k\geqslant 1}\mathbb{P}\left(\tau_{w}\geqslant
k|v_{0}=v\right)$ $\displaystyle\leqslant\sum_{\ell\geqslant
0}\mathbb{P}\left(\tau_{w}>\ell\tau_{\rm mix}|v_{0}=v\right)\,.$

Then, for $\ell\geqslant 0$,

$\displaystyle\mathbb{P}\left(\tau_{w}>(\ell+1)\tau_{\rm
mix}|v_{0}=v\right)=\mathbb{P}\left(\tau_{w}>(\ell+1)\tau_{\rm
mix}|\tau_{w}>\ell\tau_{\rm
mix},v_{0}=v\right)\mathbb{P}\left(\tau_{w}>\ell\tau_{\rm
mix}|v_{0}=v\right)\,,$

and, conditioning on $v_{\ell\tau_{\rm mix}}$,
$\mathbb{P}\left(\tau_{w}>(\ell+1)\tau_{\rm mix}|\tau_{w}>\ell\tau_{\rm
mix},v_{\ell\tau_{\rm mix}}\right)\leqslant\mathbb{P}\left(v_{(\ell+1)\tau{\rm
mix}}\neq w|v_{\ell\tau_{\rm mix}}\right)$. By definition of $\tau_{\rm mix}$,
we have that $\mathbb{P}\left(v_{(\ell+1)\tau{\rm mix}}\neq w|v_{\ell\tau_{\rm
mix}}\right)\leqslant(1-\pi_{w}/2)$, so that:

$\mathbb{P}\left(\tau_{w}>(\ell+1)\tau_{\rm
mix}|v_{0}=v\right)\leqslant(1-\pi_{w}/2)\mathbb{P}\left(\tau_{w}>\ell\tau_{\rm
mix}|v_{0}=v\right)\,,$

and $\mathbb{P}\left(\tau_{w}>\ell\tau_{\rm
mix}|v_{0}=v\right)\leqslant(1-\pi_{w}/2)^{\ell}$ by recursion. Finally,

$\displaystyle\mathbb{E}\left[\tau_{w}|v_{0}=v\right]$
$\displaystyle\leqslant\tau_{\rm mix}\sum_{\ell\geqslant
0}(1-\pi_{w}/2)^{\ell}$ $\displaystyle\leqslant\frac{2\tau_{\rm
mix}}{\pi_{w}}\,,$

concluding the proof by taking the maximum over $w$. ∎

###  A.2 Matthews’ bound for cover times

The following result bounds the cover time of the Markov chain: it is in fact
closely related to its hitting time, and the two differ with a most a factor
$\ln(n)$. This surprising result is proved in a very elegant way in the survey
Levin et al. [2006], using the famous Matthews’ method Matthews [1988].

######  Theorem 6 (Matthews’ bound for cover times).

The hitting and cover times of the Markov chain verify:

$\tau_{\rm cov}\leqslant\left(\sum_{k=1}^{n-1}\frac{1}{k}\right)\tau_{\rm
hit}\,.$

###  A.3 A bound on the hitting time of regular and symetric graphs

Using results from Rao [2012], we relate the hitting time of symmetric regular
graphs (in a sense that we define below) to well-known graph-related
quantities: number of edges $|\mathcal{E}|$, diameter $\delta$ and degree $d$.

######  Lemma 3 (Bounding hitting times of regular graphs).

Let $(v_{t})$ be the simple random walk on a $d$-regular graph $G$ of diameter
$\delta$, that satisfies the following symetry property: for any
${\\{u,v\\}},{\\{v,w\\}}\in\mathcal{E}$, there exists a graph automorphism
that maps $v$ to $w$. Then, we have:

$\tau_{\rm hit}\leqslant\frac{2|\mathcal{E}|\delta}{d}$

###### Proof.

Using Theorem 2.1 of Rao [2012], for ${\\{v,w\\}}\in\mathcal{E}$, we have

$\mathbb{E}\left[\tau_{w}|v_{0}=v\right]=\frac{2|\mathcal{E}|}{d}\,,$

where $|\mathcal{E}|$ is the number of edges in the graph. Let $v$ and $w$ in
$\mathcal{V}$, at distance $\delta^{\prime}\leqslant\delta$. There exists
nodes $v=v(0),v(1)\ldots,v(\delta^{\prime}-1),v(\delta^{\prime})=w$ such that
for all $0\leqslant s<\delta^{\prime}$,
${{\left\\{v(s),v(s+1)\right\\}}}\in\mathcal{E}$, and by using the Markov
property:

$\mathbb{E}\left[\tau_{w}|v_{0}=v\right]\leqslant\sum_{s<\delta^{\prime}}\mathbb{E}\left[\tau_{v(s+1)}v_{0}=v(s)\right]\leqslant\delta\frac{2|\mathcal{E}|}{d}\,.$

∎

###  A.4 Two miscellaneous lemmas

We finally end this “preliminary results” section with the two following
lemmas, that we help us conclude the proof of Theorem 5. The first lemma will
lead to a bound on $\Big{(}\sum_{t<T}\gamma_{t}\Big{)}^{-1}$ where
$\gamma_{t}$ is the adaptive stepsize policy defined in Equation (7), while
the second one is used to conclude the proof of Theorem 5 to show that a
remaining term is non-positive.

######  Lemma 4.

For $t\geqslant 0$ and $v\in\mathcal{V}$, let
$p_{v}(t)=\inf{{\left\\{s>t|v_{s}=v\right\\}}}$ and
$d_{v}(t)=\sup{{\left\\{s<t|v_{s}=v\right\\}}}$ be the next and the last
previous iterates for which $v_{t}=v$ ($d_{v}(t)=0$ by convention, if $v$ has
not yet been visited). Assume that $(v_{t})$ has stationary distribution
$\pi$. For $t\geqslant 0$, let
$A_{t}=\sup_{v\in\mathcal{V}}\big{(}t-d_{v}(t)\big{)}$ and
$B_{t}=\sup_{v\in\mathcal{V}}\big{(}p_{v}(t)-t\big{)}$. We have:

$\mathbb{E}\left[B_{t}|v_{t}=v\right]\leqslant\tau_{\rm cov}\,,\quad\forall
v\in\mathcal{V}\,,$

and for $T\geqslant 1$:

$\sum_{t<T}\mathbb{E}\left[A_{t}\right]\leqslant T\tau_{\rm cov}\,.$

###### Proof.

The first bound on $B_{t}$ is obtained using the Markov property of the chain,
and by definition of $\tau_{\rm cov}$. We have:

$\mathbb{E}\left[A_{t}\right]=\sum_{k=0}^{t-1}\mathbb{P}\left(A_{t}\geqslant
k\right)\,.$

For $t\geqslant 0$ fixed, we denote $d=\inf_{v}d_{v}(t)$, so that $A_{t}=t-d$.
We then have the equality between the following events:

${{\left\\{A_{t}\geqslant k\right\\}}}={{\left\\{t-d\geqslant
k\right\\}}}={{\left\\{d\leqslant t-k\right\\}}}={{\left\\{B_{t-k}\geqslant
k\right\\}}}\,,$

that all coincide with the event “there exists some $v\in\mathcal{V}$ such
that for all $t-k\leqslant s\leqslant t$, $v_{s}\neq v$”. Summing over $t<T$:

$\displaystyle\sum_{t<T}\mathbb{E}\left[A_{t}\right]$
$\displaystyle=\sum_{t<T}\sum_{k<t}\mathbb{P}\left(B_{t-k}\geqslant k\right)$
$\displaystyle=\sum_{\ell<T}\sum_{s<T-\ell}\mathbb{P}\left(B_{\ell}\geqslant
s\right)$ $\displaystyle\leqslant\sum_{\ell<T}\sum_{s\geqslant
0}\mathbb{P}\left(B_{\ell}\geqslant s\right)$
$\displaystyle\leqslant\sum_{\ell<T}\mathbb{E}\left[B_{\ell}\right]$
$\displaystyle\leqslant T\tau_{\rm cov}\,.$

∎

######  Lemma 5.

Let $(a_{t})_{t\geqslant 0},(b_{t})_{t\geqslant 0}$ be two sequences of real-
valued random variables. Let $(\mathcal{F}_{t})_{t\geqslant 0}$ be a
filtration. Assume that $b_{t}$ is positive and $\mathcal{F}_{t}$-measurable
for all $t$, and that $\mathbb{E}\left[a_{t}|\mathcal{F}_{t}\right]\leqslant
0$. Then, denoting $H_{T}=\frac{\sum_{t=0}^{T}a_{t}}{\sum_{t=0}^{T}b_{t}}$,
the sequence $(\mathbb{E}\left[H_{T}\right])_{T\geqslant 0}$ is non-
increasing, so that $\mathbb{E}\left[H_{T}\right]\leqslant 0$ for all $T$.

###### Proof.

For fixed $T\geqslant 1$, we have, using the fact tha $b_{t}$ is
$\mathcal{F}_{T}$ measurable for $t\leqslant T$

$\displaystyle\mathbb{E}\left[H_{T}|\mathcal{F}_{T}\right]$
$\displaystyle=\frac{\mathbb{E}\left[a_{T}|\mathcal{F}_{T}\right]+\sum_{t<T}\mathbb{E}\left[a_{t}|\mathcal{F}_{T}\right]}{\sum_{t\leqslant
T}b_{t}}$
$\displaystyle\leqslant\frac{\sum_{t<T}\mathbb{E}\left[a_{t}|\mathcal{F}_{T}\right]}{\sum_{t\leqslant
T}b_{t}}$
$\displaystyle\leqslant\frac{\sum_{t<T}\mathbb{E}\left[a_{t}|\mathcal{F}_{T}\right]}{\sum_{t<T}b_{t}}\,,$

using $\mathbb{E}\left[a_{T}|\mathcal{F}_{T}\right]\leqslant 0$ and $b_{T}>0$.
Consequently, taking the mean, we obtain
$\mathbb{E}\left[H_{T}\right]\leqslant\mathbb{E}\left[H_{T-1}\right]$. ∎

##  Appendix B Lower bound

We prove the smooth non-convex version of Theorem 1; the convex cases are
proved in a similar way using exactly the same arguments, and the “most
difficult function in the world”, as defined by Nesterov [2014], rather than
the one used by Carmon et al. [2021], albeit the two are closely related.

###### Proof of Theorem 1.

For $\mathbf{x}\in\ell_{2}$ and $k\in\mathbb{N}$, denote by $\mathbf{x}(k)$
its $k^{\rm th}$ coordinate. We split the function defined in Section 3.2 of
Carmon et al. [2021] (inspired by the “most difficult function in the world”
of Nesterov [2014]) between two nodes $v,w\in\mathcal{V}$ maximizing
$\mathbb{E}\left[\tau_{w}|v_{0}=v\right]$, by setting
$\pi_{v}f_{v}(\mathbf{x})=\frac{1}{2}\sum_{k\geqslant
1}2\mathbf{x}(2k)^{2}-2\mathbf{x}(2k-1)\mathbf{x}(2k)+\frac{1}{2}\alpha\mathbf{x}(0)^{2}-b\mathbf{x}(0)+\frac{\alpha}{2}$
and $\pi_{w}f_{w}(\mathbf{x})=\frac{1}{2}\sum_{k\geqslant
0}2\mathbf{x}(2k+1)^{2}-2\mathbf{x}(2k+1)\mathbf{x}(2k)$ for some
$b,\alpha>0$. Then, we define $T_{0}=\tau_{v}$ and for $t\geqslant 0$,

$\displaystyle T_{2k+1}=\inf{{\left\\{t\geqslant
T_{2k}\,|\,v_{t}=w\right\\}}}\quad\text{and}$ $\displaystyle
T_{2k+2}=\inf{{\left\\{t\geqslant T_{2k+1}\,|\,v_{t}=w\right\\}}}\,.$

The second step of the proof is somewhat classical, and consists in observing
that the black-box constraints of the algorithm together with the construction
of the functions $f_{v}$ and $f_{w}$ defined in the proof sketch of Section 4
imply that:

$\left\\{\begin{aligned} &\text{if}\quad
v_{t}=v\quad\text{and}\quad\left\\{\begin{aligned} &\mathcal{M}_{t}\supset{\rm
Span}(\mathbf{e}_{i},i\leqslant
2k-1)\,\quad\text{then}\quad\mathcal{M}_{t+1}\supset{\rm
Span}(\mathbf{e}_{i},i\leqslant 2k)\,,\\\ &\mathcal{M}_{t}\subset{\rm
Span}(\mathbf{e}_{i},i\leqslant
2k)\,\quad\text{then}\quad\mathcal{M}_{t+1}\subset{\rm
Span}(\mathbf{e}_{i},i\leqslant 2k)\,,\end{aligned}\right.\\\ &\text{if}\quad
v_{t}=w\quad\text{and}\quad\left\\{\begin{aligned} &\mathcal{M}_{t}\supset{\rm
Span}(\mathbf{e}_{i},i\leqslant
2k)\,\quad\text{then}\quad\mathcal{M}_{t+1}\supset{\rm
Span}(\mathbf{e}_{i},i\leqslant 2k+1)\,,\\\ &\mathcal{M}_{t}\subset{\rm
Span}(\mathbf{e}_{i},i\leqslant
2k+1)\,\quad\text{then}\quad\mathcal{M}_{t+1}\subset{\rm
Span}(\mathbf{e}_{i},i\leqslant 2k+1)\,,\end{aligned}\right.\\\
&\text{if}\quad
v_{t}\notin{\\{v,w\\}},\quad\text{then}\quad\mathcal{M}_{t}=\mathcal{M}_{t+1}\,.\end{aligned}\right.$

In other words, even dimensions are discovered by node $v$, while odd ones are
discovered by node $w$. The dimension $\mathbb{R}\mathbf{e}_{0}$ is discovered
by node $v$ thanks to the term $-b\mathbf{e}_{0}$. Using Theorem 1 of Carmon
et al. [2021], for a right choice of parameters $\alpha,b>0$, $f$ is
$L$-smooth and satisfies
$f(\mathbf{x}_{0})-\inf_{\mathbf{x}}f(\mathbf{x})\leqslant\Delta$, together
with, any $k$ and any $\mathbf{x}\in\mathcal{M}_{t}\subset{\rm
Span}(\mathbf{e}_{i},i\leqslant 2k)$,

${{\left\|\nabla f(\mathbf{x})\right\|}}^{2}=\frac{L\Delta}{16k^{2}}\,.$

This lower bound proof technique is explained in a detailed and enlightening
fashion in Chapter 3.5 of Bubeck [2015].

Then, the final and more technical step of the proof consists in upper
bounding $\mathbb{E}k(t)$. If $(T_{k+1}-T_{k})_{k\geqslant 0}$ were
independent from $k(t)$, using $\mathbb{E}\left[T_{k+1}-T_{k}\right]=\tau_{\rm
hit}$ for $k$ even, we would directly obtain
$t\geqslant\mathbb{E}\left[T_{k(t)}\right]\geqslant\mathbb{E}\left[k(t)\right]-1)\tau_{\rm
hit}/2$. However, these random variables are not independent: since tail
effects can happen, we need a finite second moment for hitting times, and the
proof is a bit trickier. First, note that:

$\mathbb{E}\left[k(t)\right]=\sum_{0\leqslant k\leqslant
t}\mathbb{P}\left(k(t)\geqslant k\right)=\sum_{0\leqslant k\leqslant
t}\mathbb{P}\left(T_{k}\leqslant t\right)\,.$

Let $(X_{\ell})_{\ell\geqslant 0}$ be _i.i.d._ random variables of same law as
$\tau_{w}$ conditioned on $v_{0}=v$. We have
$\mathbb{E}\left[X_{\ell}\right]=\mathbb{E}\left[\tau_{w}|v_{0}=v\right]=\tau_{\rm
hit}$, and ${\rm var\,}(X_{\ell})<\infty$ (by assumption). Let
$S_{k}=\sum_{\ell=0}^{k-1}X_{\ell}$ ($S_{k}$ has the same law as
$\sum_{\ell=0}^{k-1}T_{2k+1}-T_{2k}$ ), so that, using the Markov property of
$(v_{t})$, $T_{k}$ stochastically dominates $S_{\lfloor k/2\rfloor}$. Hence,
$\mathbb{P}\left(T_{k}\leqslant t\right)\leqslant\mathbb{P}\left(S_{\lfloor
k/2\rfloor}\leqslant t\right)$. Then, using Chebychev inequality, for any
$\ell\geqslant 0$ and for $t$ such that $\ell\tau_{\rm hit}\geqslant t$, we
have:

$\displaystyle\mathbb{P}\left(S_{\ell}\leqslant t\right)$
$\displaystyle=\mathbb{P}\left(S_{\ell}-\ell\tau_{\rm hit}\leqslant
t-\ell\tau_{\rm hit}\right)$
$\displaystyle=\mathbb{P}\left((S_{\ell}-\ell\tau_{\rm
hit})^{2}\leqslant(t-\ell\tau_{\rm hit})^{2}\right)$
$\displaystyle\leqslant\frac{\ell{\rm var\,}(X_{0})}{(t-\ell\tau_{\rm
hit})^{2}}\,.$

We then have:

$\displaystyle\mathbb{E}\left[k(t)\right]$ $\displaystyle\leqslant
2\sum_{0\leqslant\ell\leqslant t/2}\mathbb{P}\left(S_{\ell}\leqslant t\right)$
$\displaystyle=2\sum_{0\leqslant\ell\leqslant 2t/\tau_{\rm
hit}}\mathbb{P}\left(S_{\ell}\leqslant t\right)+2\sum_{2t/\tau_{\rm
hit}\leqslant\ell\leqslant t/2}\mathbb{P}\left(S_{\ell}\leqslant t\right)$
$\displaystyle\leqslant\frac{4t}{\tau_{\rm hit}}+2\sum_{2t/\tau_{\rm
hit}\leqslant\ell\leqslant t/2}\frac{\ell{\rm var\,}(X_{0})}{(t-\ell\tau_{\rm
hit})^{2}}\,.$

We finally show that the second term stays bounded:

$\displaystyle\sum_{2t/\tau_{\rm hit}\leqslant\ell\leqslant
t/2}\frac{\ell}{(t-\ell\tau_{\rm hit})^{2}}$ $\displaystyle=\frac{1}{\tau_{\rm
hit}^{2}}\sum_{0\leqslant\ell\leqslant t/2-2t/\tau_{\rm
hit}}\frac{\ell+2t/\tau_{\rm hit}}{(\ell+t/\tau_{\rm hit})^{2}}$
$\displaystyle=\frac{1}{\tau_{\rm hit}^{2}}\sum_{0\leqslant\ell\leqslant
t/2-2t/\tau_{\rm hit}}\frac{\ell}{(\ell+t/\tau_{\rm
hit})^{2}}+\frac{2}{\tau_{\rm hit}^{2}}\sum_{0\leqslant\ell\leqslant
t/2-2t/\tau_{\rm hit}}\frac{t/\tau_{\rm hit}}{(\ell+t/\tau_{\rm hit})^{2}}\,.$

First, using a comparison with a continuous sum, we have:

$\sum_{0\leqslant\ell\leqslant t}\frac{\ell}{(\ell+t/\tau_{\rm
hit})^{2}}\leqslant\sum_{0\leqslant\ell\leqslant t}\frac{1}{(\ell+t/\tau_{\rm
hit})}\leqslant\ln(\frac{t}{t/\tau_{\rm hit}})=\ln(\tau_{\rm hit})\,,$

since for $a,x>0$, $\int_{0}^{ax}\frac{y{\rm
d}y}{(y+a)^{2}}\leqslant\int_{0}^{ax}\frac{{\rm d}y}{(y+a)}=\ln(x)$. Finally,
using $\sum_{\ell\geqslant
1}\frac{1}{(a+\ell)^{2}}\leqslant\int_{0}^{\infty}\frac{{\rm
d}y}{(y+a)^{2}}=\frac{1}{a}$, we bound the second sum as:

$\sum_{0\leqslant\ell\leqslant t/2-2t/\tau_{\rm hit}}\frac{t/\tau_{\rm
hit}}{(\ell+t/\tau_{\rm hit})^{2}}\leqslant\frac{\tau_{\rm hit}}{t}+1\,.$

Wrapping our arguments together, we end up with:

$\mathbb{E}\left[k(t)\right]\leqslant\frac{4t}{\tau_{\rm hit}}+\frac{2{\rm
var\,}(\tau_{v})}{\tau_{\rm hit}^{2}}(\ln(\tau_{\rm hit})+1+\frac{\tau_{\rm
hit}}{t})\,.$

For $t$ big enough, we end up with $\mathbb{E}\left[k(t)\right]\leqslant
5t/\tau_{\rm hit}$, so that since $\mathbb{E}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\geqslant
L\Delta/(16\mathbb{E}\left[k(t)\right]^{2})$ as explained in the main text, we
have:

${{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}=\Omega\left(\frac{L\Delta\tau_{\rm
hit}^{2}}{t^{2}}\right)\,.$

∎

##  Appendix C Markov chain stochastic gradient descent: proof of Theorem 2

The following proofs in this Appendix section are valid for finite as well as
infinite state spaces $\mathcal{V}$.

We start by proving the following bound on $\mathbb{E}\left[{{\left\|\nabla
f_{v_{t}}(\mathbf{x}_{t})\right\|}}^{2}\right]$. Note that this bound can be
used for any $t\geqslant\tau_{\rm mix}$.

######  Lemma 6.

For $t\geqslant 0$ and if $v_{t}\sim\pi_{t}$ for ${\rm d}_{\rm
TV}(\pi_{t},\pi)\leqslant\pi_{\min}/2$, we have:

$\mathbb{E}\left[{{\left\|\nabla
f_{v_{t}}(\mathbf{x}_{t})\right\|}}^{2}\right]\leqslant
3\bar{\sigma}^{2}+2\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]\,.$

###### Proof of the Lemma.

We have for any $v\in\mathcal{V}$ that
$\mathbb{P}\left(v_{t}=v\right)\leqslant\pi_{v}+\pi_{v}/2=3\pi_{v}/2$, so that

$\displaystyle\mathbb{E}\left[{{\left\|\nabla
f_{v_{t}}(\mathbf{x}_{t})\right\|}}^{2}\right]$ $\displaystyle\leqslant
2\mathbb{E}\left[{{\left\|\nabla f_{v_{t}}(\mathbf{x}_{t})-\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]+2\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]$ $\displaystyle\leqslant
2\sum_{v\in\mathcal{V}}\mathbb{P}\left(v_{t}=v\right)\sigma_{v}^{2}+2\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]$
$\displaystyle=3\bar{\sigma}^{2}+2\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]\,.$

∎

The proof borrows ideas from both the analyses of delayed SGD [Mania et al.,
2017] and SGD with biased gradients [Even et al., 2022], thus refining MC-SGD
initial analysis [Johansson et al., 2010]. While a biased gradient analysis
would not yield convergence to an $\varepsilon$-stationary point for arbitrary
$\varepsilon$ (at every iterations, biases are non-negligible and can be
arbitrary high), by enforcing a delay $\tau$ (of order $\tau_{\rm mix}$) in
the analysis, we manage to take advantage of the ergodicity of the biases.

###  C.1 Smooth non-convex case of Theorem 2

###### Proof of Theorem 2.1.

Denoting $F_{t}=\mathbb{E}f(\mathbf{x}_{t})-f(\mathbf{x}^{\star})$, we have
using smoothness:

$F_{t+1}-F_{t}\leqslant-\gamma\mathbb{E}\left[\langle\nabla
f_{v_{t}}(\mathbf{x}_{t}),\nabla
f(\mathbf{x}_{t})\rangle\right]+\frac{\gamma^{2}L}{2}\mathbb{E}\left[{{\left\|\nabla
f_{v_{t}}(\mathbf{x}_{t})\right\|}}^{2}\right]\,.$

For the first term on the righthandside of the inequality, assuming that
$t\geqslant\tau$ for some $\tau>0$ we explicit later in the proof:

$\displaystyle\mathbb{E}\left[-\gamma\langle\nabla
f_{v_{t}}(\mathbf{x}_{t}),\nabla f(\mathbf{x}_{t})\rangle\right]$
$\displaystyle=\mathbb{E}\left[-\gamma\langle\nabla
f_{v_{t}}(\mathbf{x}_{t-\tau}),\nabla
f(\mathbf{x}_{t-\tau})\rangle\right]+\mathbb{E}\left[-\gamma\langle\nabla
f_{v_{t}}(\mathbf{x}_{t}),\nabla f(\mathbf{x}_{t})-\nabla
f(\mathbf{x}_{t-\tau})\rangle\right]$
$\displaystyle\quad+\mathbb{E}\left[-\gamma\langle\nabla
f_{v_{t}}(\mathbf{x}_{t})-\nabla f_{v_{t}}(\mathbf{x}_{t-\tau}),\nabla
f(\mathbf{x}_{t-\tau})\rangle\right]\,.$

First, we condition the first term on the filtration up to time $t-\tau$:

$\displaystyle\mathbb{E}\left[-\gamma\langle\nabla
f_{v_{t}}(\mathbf{x}_{t-\tau}),\nabla f(\mathbf{x}_{t-\tau})\rangle\right]$
$\displaystyle=\mathbb{E}\left[-\gamma\langle\mathbb{E}_{t-\tau}\nabla
f_{v_{t}}(\mathbf{x}_{t-\tau}),\nabla f(\mathbf{x}_{t-\tau})\rangle\right]$
$\displaystyle\leqslant-\frac{\gamma}{2}\mathbb{E}\left[{{\left\|\mathbb{E}_{t-\tau}\nabla
f_{v_{t-\tau}}(\mathbf{x}_{t})\right\|}}^{2}\right]+\frac{\gamma}{2}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})-\mathbb{E}_{t-\tau}\nabla
f_{v_{t}}(\mathbf{x}_{t-\tau})\right\|}}\right]$
$\displaystyle\quad-\frac{\gamma}{2}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]\,.$

Then, for $\tau\geqslant\tau_{\rm mix}(\pi_{\min}\varepsilon)$, using the
following lemma, we have, for $\varepsilon<1/2$:

$\mathbb{E}\left[-\gamma\langle\mathbb{E}_{t-\tau}\nabla
f_{v_{t}}(\mathbf{x}_{t-\tau}),\nabla
f(\mathbf{x}_{t-\tau})\rangle\right]\leqslant-\frac{\gamma}{4}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]+\gamma\varepsilon^{2}\bar{\sigma}^{2}\,.$

######  Lemma 7.

For $\tau\geqslant\tau_{\rm mix}(\varepsilon\pi_{\min})$ and $t\geqslant\tau$,

$\mathbb{E}\left[{{\left\|\mathbb{E}_{t-\tau}\nabla
f_{v_{t}}(\mathbf{x}_{t-\tau})-\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]\leqslant
2\varepsilon^{2}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]+2\varepsilon^{2}\bar{\sigma}^{2}\,.$

###### Proof of the Lemma.

We have:

$\displaystyle\mathbb{E}\left[{{\left\|\mathbb{E}_{t-\tau}\nabla
f_{v_{t}}(\mathbf{x}_{t-\tau})-\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]$
$\displaystyle=\mathbb{E}\left[{{\left\|\sum_{v\in\mathcal{V}}(\mathbb{P}\left(v_{t}=v|\mathbf{x}_{t-\tau}\right)-\pi_{v})\nabla
f_{v}(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]$
$\displaystyle\leqslant\varepsilon^{2}\sum_{v\in\mathcal{V}}\pi_{v}\mathbb{E}\left[{{\left\|\nabla
f_{v}(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]\,,$

where we used
$|\mathbb{P}\left(v_{t}=v|\mathbf{x}_{t-\tau}\right)-\pi_{v}|\leqslant\varepsilon\pi_{v}$
and convexity of the squared Euclidean norm. For that last term,

$\displaystyle\sum_{v\in\mathcal{V}}\pi_{v}\mathbb{E}\left[{{\left\|\nabla
f_{v}(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]$
$\displaystyle\leqslant\sum_{v\in\mathcal{V}}2\pi_{v}\left(\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]+\sigma_{v}^{2}\right)$
$\displaystyle=2\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]+2\bar{\sigma}^{2}\,,$

concluding the proof of the Lemma. ∎

Using gradient Lipschitzness and writing
$\mathbf{x}_{t}-\mathbf{x}_{t-\tau}=-\gamma\sum_{s=\max(t-\tau,0)}^{t-1}\nabla
f_{v_{s}}(\mathbf{x}_{s})$, we have:

$\displaystyle\mathbb{E}\left[-\gamma\langle\nabla
f_{v_{t}}(\mathbf{x}_{t}),\nabla f(\mathbf{x}_{t})-\nabla
f(\mathbf{x}_{t-\tau})\rangle\right]$
$\displaystyle\leqslant\gamma^{2}L\mathbb{E}\left[{{\left\|\nabla
f_{v_{t}}(\mathbf{x}_{t})\right\|}}{{\left\|\sum_{s=\max(t-\tau,0)}^{t-1}\nabla
f_{v_{s}}(\mathbf{x}_{s})\right\|}}\right]$
$\displaystyle\leqslant\frac{\gamma^{2}L}{2}(\tau\mathbb{E}\left[{{\left\|\nabla
f_{v_{t}}(\mathbf{x}_{t})\right\|}}^{2}\right]+\sum_{s=\max(t-\tau,0)}^{t-1}\mathbb{E}\left[{{\left\|\nabla
f_{v_{s}}(\mathbf{x}_{s})\right\|}}^{2}\right]\big{)}\,.$

Similarly,

$\mathbb{E}\left[-\gamma\langle\nabla f_{v_{t}}(\mathbf{x}_{t})-\nabla
f_{v_{t}}(\mathbf{x}_{t-\tau}),\nabla
f(\mathbf{x}_{t-\tau})\rangle\right]\leqslant\frac{\gamma^{2}L}{2}(\tau\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]+\sum_{s=\max(t-\tau,0)}^{t-1}\mathbb{E}\left[{{\left\|\nabla
f_{v_{s}}(\mathbf{x}_{s})\right\|}}^{2}\right]\big{)}\,.$

Wrapping things up, we obtain, for $t\geqslant\tau$ and
$\tau\geqslant\tau_{\rm mix}$:

$\displaystyle F_{t+1}-F_{t}$
$\displaystyle\leqslant-\frac{\gamma}{4}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]+\gamma\varepsilon^{2}\bar{\sigma}^{2}$
$\displaystyle\quad+\frac{\gamma^{2}L}{2}\big{(}(\tau+1)\mathbb{E}\left[{{\left\|\nabla
f_{v_{t}}(\mathbf{x}_{t})\right\|}}^{2}\right]+\tau\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]+2\sum_{s=\max(t-\tau,0)}^{t-1}\mathbb{E}\left[{{\left\|\nabla
f_{v_{s}}(\mathbf{x}_{s})\right\|}}^{2}\right]\big{)}$
$\displaystyle\leqslant-\frac{\gamma}{4}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]+\gamma\varepsilon^{2}\bar{\sigma}^{2}+(3\tau+1)\frac{\gamma^{2}L}{2}$
$\displaystyle\quad+\frac{\gamma^{2}L}{2}\big{(}(\tau+1)\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]+\tau\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]+2\sum_{s=\max(t-\tau,0)}^{t-1}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{s})\right\|}}^{2}\right]\big{)}\,.$

Summing for $\tau\leqslant t<T$:

$\frac{1}{T}\sum_{\tau\leqslant t<T}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]\leqslant\frac{4F_{\tau}}{\gamma
T}+\frac{1}{T}\sum_{\tau\leqslant t<T}6\gamma
L\tau\big{(}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]+\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]\big{)}+2\big{(}2\varepsilon^{2}+\gamma(3\tau+1)\big{)}\bar{\sigma}^{2}\,,$

leading to, for $\gamma\leqslant\frac{1}{12L\tau}$:

$\displaystyle\frac{1}{T}\sum_{t<T-\tau}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]$
$\displaystyle\leqslant\frac{4F_{\tau}}{\gamma T}+\frac{6\gamma
L\tau}{T}\sum_{T-\tau\leqslant t<T}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]+2\big{(}2\varepsilon^{2}+\gamma(3\tau+1)\big{)}\bar{\sigma}^{2}\,.$
(8)

We now prove that for any $t\geqslant 0$, we have $\sup_{t\leqslant s\leqslant
t+\tau}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{s})\right\|}}^{2}\right]\leqslant
4\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]+8\gamma^{2}L^{2}\tau^{2}\sigma^{2}$.
Let $t\leqslant s<t+\tau$.

$\displaystyle\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{s})\right\|}}^{2}\right]$ $\displaystyle\leqslant
2\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]+2\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{s})-\nabla f(\mathbf{x}_{t})\right\|}}^{2}\right]$
$\displaystyle\leqslant 2\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]+2L^{2}\gamma^{2}\mathbb{E}\left[\sum_{r=t}^{s-1}{{\left\|\nabla
f_{v_{r}}(\mathbf{x}_{r})\right\|}}^{2}\right]$ $\displaystyle\leqslant
2\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]+4L^{2}\gamma^{2}\tau\sum_{r=t}^{s-1}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{r})\right\|}}^{2}\right]+\bar{\sigma}^{2}$
$\displaystyle\leqslant 2\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]+4L^{2}\gamma^{2}\tau^{2}(\sup_{t\leqslant
s\leqslant t+\tau}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{s})\right\|}}^{2}\right]+\bar{\sigma}^{2})\,,$

leading to the desired result for $\gamma\leqslant 1/(8L\tau)$. Plugging this
in (8):

$\displaystyle\frac{1}{T}\sum_{t<T-\tau}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]$
$\displaystyle\leqslant\frac{4F_{\tau}}{\gamma T}+\frac{24\gamma
L\tau}{T}\sum_{T-\tau\leqslant t<T}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]$
$\displaystyle\quad+\frac{\tau}{T}4L^{2}\gamma^{2}\tau^{2}\bar{\sigma}^{2}+2\big{(}2\varepsilon^{2}+\gamma(3\tau+1)\big{)}L\bar{\sigma}^{2}\,.$

Now, for $\gamma=\min(1/(48L\tau),\sqrt{F_{0}/(TL\tau\bar{\sigma}^{2})})$,
$\varepsilon=1/\sqrt{T}$, and so $\tau=\tau_{\rm mix}\ln(T)$, we have:

$\frac{1}{T}\sum_{t<T-\tau}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]\leqslant\frac{196\tau
LF_{\tau}}{T}+7\sqrt{\frac{LF_{0}\bar{\sigma}^{2}}{T}}\,.$ (9)

We now upper bound $F_{\tau}$. For any $t$ and $\gamma<1/(2L)$,

$F_{t+1}-F_{t}\leqslant\frac{\gamma}{2}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})-\nabla
f_{v_{t}}(\mathbf{x}_{t})\right\|}}^{2}\right]\leqslant\gamma\sigma_{\max}^{2}/2\,,$

where the first inequality is a simplified version of the descent lemma with
biased gradient at the beggining of this proof, and the second inequality uses
the initialization properties of $v_{0}$. Thus, we obtain $F_{\tau}\leqslant
F_{0}+\gamma\tau\sigma_{\max}^{2}/2\leqslant F_{0}+\sigma_{\max}^{2}/L$ for
our choice of $\gamma$. We thus conclude by plugging this in (9) applied for
$T+\tau$ instead of $T$, yielding the desired result.

The condition for the upper-bound we proved above to be true, namely
$T\geqslant\tau=\tau_{\rm mix}\ln(T)$, is always satisfied for $T\geqslant
2\tau_{\rm mix}\ln(\tau_{\rm mix})$. Indeed, if $T\leqslant\tau_{\rm
mix}^{2}$, then $\tau_{\rm mix}\ln(T)\leqslant 2\tau_{\rm mix}\ln(\tau_{\rm
mix})\leqslant T$, and otherwise we have $\tau_{\rm
mix}\ln(T)\leqslant\sqrt{T}\ln(T)\leqslant T$. This concludes the proof, and
$\tilde{\mathbf{x}}_{0}$ in the Theorem corresponds to $\mathbf{x}_{\tau}$. ∎

###  C.2 Under a $\mu$-PL inequality

###### Proof of Theorem 2.2.

We start from:

$\displaystyle F_{t+1}-F_{t}$
$\displaystyle\leqslant-\frac{\gamma}{4}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]+\gamma\varepsilon^{2}\bar{\sigma}^{2}+(3\tau+1)\frac{\gamma^{2}L}{2}$
$\displaystyle\quad+\frac{\gamma^{2}L}{2}\big{(}(\tau+1)\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]+\tau\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]+2\sum_{s=\max(t-\tau,0)}^{t-1}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{s})\right\|}}^{2}\right]\big{)}\,.$

If $f$ satisfies a $\mu$-PL inequality, then $-\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]\leqslant-2\mu F_{t-\tau}$, so
that, for some $\alpha\in(0,1)$:

$\displaystyle F_{t+1}-F_{t}$
$\displaystyle\leqslant-\frac{\alpha\gamma\mu}{4}F_{t-\tau}-\frac{(1-\alpha)\gamma}{8}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]+\gamma\varepsilon^{2}\bar{\sigma}^{2}+(3\tau+1)\frac{\gamma^{2}L}{2}\bar{\sigma}^{2}$
$\displaystyle\quad+\frac{\gamma^{2}L}{2}\big{(}(\tau+1)\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]+\tau\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t-\tau})\right\|}}^{2}\right]+2\sum_{s=\max(t-\tau,0)}^{t-1}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{s})\right\|}}^{2}\right]\big{)}\,.$

For $t\geqslant 0$, let $P_{t}=(1-\alpha\gamma\mu/4)^{-t}$. We multiply the
above expression by $P_{t+1}$ and sum for $t<T$, hoping for cancellations. For
$T\geqslant\tau$:

$\displaystyle\sum_{\tau\leqslant
t<T}P_{t+1}\big{(}F_{t}-F_{t+1}-\frac{\alpha\gamma\mu}{4}F_{t-\tau}\big{)}$
$\displaystyle=\sum_{\tau\leqslant
t<T}P_{t+1}\big{(}(1-\frac{\alpha\gamma\mu}{4})F_{t}-F_{t+1}+\frac{\alpha\gamma\mu}{4}(F_{t}-F_{t-\tau})\big{)}$
$\displaystyle=\sum_{\tau\leqslant t<T}P_{t}F_{t}-\sum_{\tau+1\leqslant
t\leqslant T}P_{t}F_{t}$
$\displaystyle\quad+\frac{\alpha\gamma\mu}{4}\sum_{\tau\leqslant
t<T}P_{t+1}F_{t}-\frac{\alpha\gamma\mu}{4}\sum_{\tau\leqslant
t<T}P_{t+1}F_{t-\tau}$ $\displaystyle\leqslant
P_{\tau}F_{\tau}-P_{T}F_{T}+\frac{\alpha\gamma\mu}{4}\sum_{\tau\leqslant
t<T}P_{t+1}F_{t}-\frac{P_{\tau}\alpha\gamma\mu}{4}\sum_{0\leqslant
t<T-\tau}P_{t+1}F_{t}$ $\displaystyle\leqslant
P_{\tau}F_{\tau}-P_{T}F_{T}+\frac{\alpha\gamma\mu}{4}\sum_{T-\tau\leqslant
t<T}P_{t+1}F_{t}$ $\displaystyle\leqslant
P_{\tau}F_{\tau}-P_{T}F_{T}+\frac{\alpha\gamma}{8}\sum_{T-\tau\leqslant
t<T}P_{t+1}\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]\,,$

using the $\mu$-PL inequality. For $t\geqslant 0$, we denote
$R_{t}=\mathbb{E}\left[{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]$. We now handle the “$R_{t}$” terms.

$\displaystyle-\sum_{\tau\leqslant
t<T}\frac{(1-\alpha)\gamma}{8}P_{t+1}R_{t-\tau}$
$\displaystyle+\sum_{\tau\leqslant
t<T}\frac{\gamma^{2}L}{2}\big{(}(\tau+1)P_{t+1}R_{t}+\tau
P_{t+1}R_{t-\tau}+2\sum_{s=t-\tau}^{t-1}P_{t+1}R_{s}\big{)}$
$\displaystyle\leqslant-\sum_{0\leqslant
t<T-\tau}\frac{(1-\alpha)\gamma}{8}P_{t+\tau+1}R_{t}$
$\displaystyle+\frac{\gamma^{2}L}{2}\left((\tau+1)\sum_{\tau\leqslant
t<T}P_{t+1}R_{t}+\tau\sum_{0\leqslant
t<T-\tau}P_{t+1}R_{t}+2\tau\sum_{t<T}R_{t}P_{t+\tau}\right)$
$\displaystyle=-\sum_{0\leqslant
t<T-\tau}P_{t+1}R_{t}\gamma\Big{(}\frac{(1-\alpha)}{8}P_{\tau}-\frac{\gamma
L}{2}(2\tau+1+2\tau P_{\tau-1})\Big{)}$
$\displaystyle+\frac{\gamma^{2}L}{2}\sum_{T-\tau\leqslant
t<T}\big{(}(\tau+1+2\tau P_{\tau-1})\big{)}P_{t+1}R_{t}$
$\displaystyle\leqslant-\sum_{0\leqslant
t<T-\tau}\frac{(1-\alpha)\gamma}{16}P_{t+\tau+1}R_{t}$
$\displaystyle+\quad\frac{(1-\alpha)\gamma}{16\beta}\sum_{T-\tau\leqslant
t<T}P_{t+1}R_{t}\,,$

if $\gamma$ satisfies $\gamma\leqslant\frac{1-\alpha}{8\beta L(5\tau+1)}$ and
$P_{\tau}\leqslant 2$, for some $\beta\geqslant 1$. Since for
$\gamma\mu\leqslant 1$, $P_{\tau}\leqslant e^{\tau\mu\gamma}$,
$P_{\tau}\leqslant 2$ can be ensured with $\gamma\leqslant\frac{1}{2\tau L}$.
All in one, we have:

$\displaystyle 0$ $\displaystyle\leqslant
P_{\tau}F_{\tau}-P_{T}F_{T}+\gamma\Big{(}\frac{\alpha}{8}+\frac{1-\alpha}{16\beta}\Big{)}\sum_{T-\tau\leqslant
t<T}P_{t+1}R_{t}$ $\displaystyle\quad-\sum_{0\leqslant
t<T-\tau}\frac{(1-\alpha)\gamma}{16}P_{t+\tau+1}R_{t}$
$\displaystyle\quad+\Big{(}\gamma\varepsilon^{2}\bar{\sigma}^{2}+(3\tau+1)\frac{\gamma^{2}L}{2}\bar{\sigma}^{2}\Big{)}\sum_{\tau\leqslant
t<T}P_{t+1}\,.$

Using what we proved in the previous proof, we have $R_{t}\leqslant
4R_{t-\tau}+8\gamma^{2}L^{2}\tau^{2}\sigma^{2}$ for $T-\tau\leqslant t<T$, so
that:

$\displaystyle\gamma\Big{(}\frac{\alpha}{8}+\frac{1-\alpha}{16\beta}\Big{)}\sum_{T-\tau\leqslant
t<T}P_{t+1}R_{t}$ $\displaystyle\leqslant
4\gamma\Big{(}\frac{\alpha}{8}+\frac{1-\alpha}{16\beta}\Big{)}\sum_{T-2\tau\leqslant
t<T-\tau}P_{t+\tau+1}R_{t}$
$\displaystyle\quad+8\gamma^{2}L^{2}\tau^{2}\sigma^{2}\gamma\Big{(}\frac{\alpha}{8}+\frac{1-\alpha}{16\beta}\Big{)}\sum_{T-2\tau\leqslant
t<T-\tau}P_{t+\tau+1}\,.$

Consequently, for
$4\gamma\Big{(}\frac{\alpha}{8}+\frac{1-\alpha}{16\beta}\Big{)}\leqslant\frac{1-\alpha}{16}\gamma$,
which can be ensured with $\alpha=1/16$ and $\beta=8$, we have:

$\displaystyle 0$ $\displaystyle\leqslant
P_{\tau}F_{\tau}-P_{T}F_{T}+\frac{1}{8}\gamma^{3}L^{2}\tau^{2}\sigma^{2}\sum_{T-2\tau\leqslant
t<T-\tau}P_{t+\tau+1}$
$\displaystyle\quad+\Big{(}\gamma\varepsilon^{2}+(3\tau+1)\frac{\gamma^{2}L}{2}\Big{)}\bar{\sigma}^{2}\sum_{\tau\leqslant
t<T}P_{t+1}\,,$

so that:

$\displaystyle F_{T}$ $\displaystyle\leqslant
F_{\tau}/P_{T-\tau}+\gamma^{2}\bar{\sigma}^{2}L\Big{(}\frac{\varepsilon^{2}}{L\gamma}+\frac{3\tau+1}{2}+\frac{\gamma
L\tau^{2}}{8}\Big{)}\frac{\sum_{t\leqslant T}P_{t}}{P_{T}}$
$\displaystyle\leqslant
2F_{\tau}/P_{T}+\frac{2\gamma\bar{\sigma}^{2}}{\mu}L\Big{(}\frac{\varepsilon^{2}}{L\gamma}+\frac{3\tau+1}{2}+\frac{\gamma
L\tau^{2}}{8}\Big{)}$ $\displaystyle\leqslant
2F_{\tau}/P_{T}+\frac{2\gamma\bar{\sigma}^{2}}{\mu}L(\frac{\varepsilon^{2}}{L\gamma}+\frac{1}{2}+2\tau)\,.$

Finally, using $F_{\tau}\leqslant F_{0}+\sigma_{\max}^{2}/L$, if
$\gamma\leqslant\frac{1}{64(5\tau+1)}$ where $\tau=\tau_{\rm
mix}(\varepsilon)$:

$F_{T}\leqslant
2(F_{0}+\sigma_{\max}^{2}/L)(1-\frac{\gamma\mu}{8})^{T}+\frac{2\gamma\bar{\sigma}^{2}}{\mu}(\frac{\varepsilon^{2}}{L\gamma}+\frac{1}{2}+2\tau)$

We thus choose $\varepsilon=\sqrt{1/T}$ so that $\tau\leqslant\tau_{\rm
mix}\ln(T)$, and stepsize
$\gamma=\min(\frac{8\ln(T(F_{0}+\bar{\sigma}^{2})/\bar{\sigma}^{2})}{\mu
T},\frac{1}{64(5\tau+1)})$ , leading to the desired result for $c=64\times
6=384$.

The same discussion than in the smooth non-convex proof regarding the
condition $T\geqslant\tau$ applies here. ∎

##  Appendix D Markov chain SGD: results in the interpolation regime

###  D.1 Proof of Theorem 3

We begin by proving the following lemma.

######  Lemma 8.

For any $T\geqslant 1$, we have:

$\mathbb{E}\left[{{\left\|\sum_{t<T}\nabla
f_{v_{t}}(\mathbf{x}^{\star})\right\|}}^{2}\right]\leqslant
T\sigma_{\star}^{2}+\sigma_{\star}^{2}\sum_{t<T}{\rm d}_{\rm
TV}(P_{v_{0},\cdot}^{t},\pi^{\star})+2\sigma_{\star}^{2}\sum_{s<t<T}{\rm
d}_{\rm TV}(t-s)\,,$

where ${\rm d}_{\rm TV}(r)=\sup{{\left\\{{\rm d}_{\rm
TV}((P^{r})_{v,\cdot},\pi^{\star})\,,v\in\mathcal{V}\right\\}}}$ for
$r\in\mathbb{N}$, so that:

$\mathbb{E}\left[{{\left\|\sum_{t<T}\nabla
f_{v_{t}}(\mathbf{x}^{\star})\right\|}}^{2}\right]\leqslant\sigma_{\star}^{2}\big{(}4\tau_{\rm
mix}(1/4)+T(1+8\tau_{\rm mix}(1/4))\big{)}\,.$

###### Proof.

We have:

$\displaystyle\mathbb{E}\left[{{\left\|\sum_{t<T}\nabla
f_{v_{t}}(\mathbf{x}^{\star})\right\|}}^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left(\sum_{t<T}\nabla
f_{v_{t}}(\mathbf{x}^{\star})\right)^{\top}\left(\sum_{t<T}\nabla
f_{v_{t}}(\mathbf{x}^{\star})\right)\right]$
$\displaystyle=\sum_{t<T}\mathbb{E}\left[{{\left\|\nabla
f_{v_{t}}(\mathbf{x}^{\star})\right\|}}^{2}\right]+2\sum_{s<t<T}\mathbb{E}\left[\langle\nabla
f_{v_{s}}(\mathbf{x}^{\star}),\nabla
f_{v_{t}}(\mathbf{x}^{\star})\rangle\right]\,.$

Denote $\mathbf{G}_{\star}=(\nabla
f_{v}(\mathbf{x}^{\star}))_{v\in\mathcal{V}}\in\mathbb{R}^{\mathcal{V}\times
d}$. For the first term above,

$\displaystyle\sum_{t<T}\mathbb{E}\left[{{\left\|\nabla
f_{v_{t}}(\mathbf{x}^{\star})\right\|}}^{2}\right]$
$\displaystyle=\sum_{t<T}\mathbb{E}\left[{{\left\|\mathbf{G}_{\star,v_{s}}\right\|}}^{2}\right]$
$\displaystyle=\sum_{t<T}\left(\sigma_{\star}^{2}+\sum_{v\in\mathcal{V}}\big{(}\mathbb{P}\left(v_{t}=v\right)-\pi_{v}\big{)}{{\left\|\mathbf{G}_{\star,v}\right\|}}^{2}\right)$
$\displaystyle\leqslant T\sigma_{\star}^{2}+\sigma_{\star}^{2}\sum_{t<T}{\rm
d}_{\rm TV}(P_{v_{0},\cdot}^{t},\pi^{\star})\,.$

Finally,

$\displaystyle\sum_{s<t<T}\mathbb{E}\left[\langle\nabla
f_{v_{s}}(\mathbf{x}^{\star}),\nabla
f_{v_{t}}(\mathbf{x}^{\star})\rangle\right]$
$\displaystyle=\sum_{s<t<T}\mathbb{E}\left[\langle\mathbf{G}_{\star,v_{s}},\mathbf{G}_{\star,v_{t}}\rangle\right]$
$\displaystyle=\sum_{s<t<T}\sum_{v,w\in\mathcal{V}}(P^{s})_{v_{0},v}(P^{t-s})_{v,w}\mathbf{G}_{\star,v}^{\top}\mathbf{G}_{\star,w}$
$\displaystyle=\sum_{s<t<T}\sum_{v,w\in\mathcal{V}}(P^{s})_{v_{0},v}\big{(}(P^{t-s})_{v,w}-\frac{1}{n}\big{)}\mathbf{G}_{\star,v}^{\top}\mathbf{G}_{\star,w}$
$\displaystyle\leqslant\sum_{s<t<T}\sum_{v,w\in\mathcal{V}}(P^{s})_{v_{0},v}\big{|}(P^{t-s})_{v,w}-\frac{1}{n}\big{|}\sigma_{\star}^{2}$
$\displaystyle=\sigma_{\star}^{2}\sum_{s<t<T}\sum_{v\in\mathcal{V}}(P^{s})_{v_{0},v}\sum_{w\in\mathcal{V}}\big{|}(P^{t-s})_{v,w}-\frac{1}{n}\big{|}$
$\displaystyle\leqslant\sigma_{\star}^{2}\sum_{s<t<T}{\rm d}_{\rm TV}(t-s)\,,$

where ${\rm d}_{\rm TV}(r)=\sup{{\left\\{{\rm d}_{\rm
TV}((P^{r})_{v,\cdot},\pi^{\star})\,,v\in\mathcal{V}\right\\}}}$ for
$r\in\mathbb{N}$.

We finally bound $\sum_{t<T}{\rm d}_{\rm TV}(t)$. Using Chapter 4.5 of Levin
et al. [2006], we have $\tau_{\rm
mix}(\varepsilon)\leqslant(\log_{2}(\varepsilon^{-1})+1)\tau_{\rm mix}(1/4)$,
so that for any $t\geqslant 0$, $d_{\rm TV}(t)\leqslant 2^{-t/\tau_{\rm
mix}(1/4)+1}$. Hence,

$\sum_{t<T}{\rm d}_{\rm TV}(t)\leqslant\frac{2}{1-2^{-1/\tau_{\rm
mix}(1/4)}}\leqslant 4\tau_{\rm mix}(1/4)\,,$

and

$\sum_{s<t<T}{\rm d}_{\rm TV}(t-s)\leqslant 4T\tau_{\rm mix}(1/4)\,,$

concluding the proof. ∎

######  Lemma 9.

For any $\mathbf{y}_{t}\in\mathbb{R}^{d}$ and $t\geqslant 0$, denoting
$\mathbf{y}_{t+1}=\mathbf{y}_{t}-\gamma\nabla f_{v_{t}}(\mathbf{x}^{\star})$,
we have:

${{\left\|\mathbf{x}_{t+1}-\mathbf{y}_{t+1}\right\|}}^{2}\leqslant(1-\gamma\mu){{\left\|\mathbf{x}_{t}-\mathbf{y}_{t}\right\|}}^{2}+\gamma
L{{\left\|\mathbf{y}_{t}-\mathbf{x}^{\star}\right\|}}^{2}\,.$

###### Proof.

Denote $f_{t}=f_{v_{t}}(\cdot)$. We expand:

$\displaystyle{{\left\|\mathbf{x}_{t+1}-\mathbf{y}_{t+1}\right\|}}^{2}$
$\displaystyle={{\left\|\mathbf{x}_{t}-\mathbf{y}_{t}\right\|}}^{2}-2\gamma\langle\nabla
f_{t}(\mathbf{x}_{t})-\nabla
f_{t}(\mathbf{x}^{\star}),\mathbf{x}_{t}-\mathbf{y}_{t}\rangle+\gamma^{2}{{\left\|\nabla
f_{t}(\mathbf{x}_{t})-\nabla f_{t}(\mathbf{x}^{\star})\right\|}}^{2}\,.$

Using the _three points equality_ as Mishchenko et al. [2020], we have:

$-2\gamma\langle\nabla f_{t}(\mathbf{x}_{t})-\nabla
f_{t}(\mathbf{x}^{\star}),\mathbf{x}_{t}-\mathbf{y}_{t}\rangle=-2\gamma
D_{f_{t}}(\mathbf{y}_{t},\mathbf{x}_{t})-2\gamma
D_{f_{t}}(\mathbf{x}_{t},\mathbf{x}^{\star})+2\gamma
D_{f_{t}}(\mathbf{y}_{t},\mathbf{x}^{\star})\,.$

First, $-2\gamma
D_{f_{t}}(\mathbf{y}_{t},\mathbf{x}_{t})\leqslant-\gamma\mu{{\left\|\mathbf{x}_{t}-\mathbf{y}_{t}\right\|}}^{2}$
using strong convexity. Then, $-2\gamma
D_{f_{t}}(\mathbf{x}_{t},\mathbf{x}^{\star})$ cancels the term
$\gamma^{2}{{\left\|\nabla f_{t}(\mathbf{x}_{t})-\nabla
f_{t}(\mathbf{x}^{\star})\right\|}}^{2}\leqslant
2\gamma^{2}LD_{f_{t}}(\mathbf{x}_{t},\mathbf{x}^{\star})$ for $\gamma\leqslant
1/L$, using smoothness of $f_{t}$. And finally, using smoothness again,
$2\gamma D_{f_{t}}(\mathbf{y}_{t},\mathbf{x}^{\star})\leqslant\gamma
L{{\left\|\mathbf{y}_{t}-\mathbf{x}^{\star}\right\|}}^{2}$, concluding the
proof. ∎

###### Proof of Theorem 3.

Fix some $y_{0}\in\mathbb{R}^{d}$ and let $(\mathbf{y}_{t})$ be defined with
the recursion

$\mathbf{y}_{t+1}=\mathbf{y}_{t}-\gamma\nabla
f_{v_{t}}(\mathbf{x}^{\star},\xi_{t})\,.$

Unrolling the previous Lemma, we have, for a fixed time horizon $T$:

${{\left\|\mathbf{x}_{T}-\mathbf{y}_{T}\right\|}}^{2}\leqslant(1-\gamma\mu)^{T}{{\left\|\mathbf{x}_{0}-\mathbf{y}_{0}\right\|}}^{2}+\gamma
L\sum_{t<T}(1-\gamma\mu)^{T-t}{{\left\|\mathbf{y}_{t}-\mathbf{x}^{\star}\right\|}}^{2}\,.$

This is possible, since the descent lemma is deterministic, in the sense that
no expectations are taken so far. Since we want control over the distance to
the optimum, we wish to have $\mathbf{y}_{T}=\mathbf{x}^{\star}$, leading to:

$\mathbf{y}_{0}=\mathbf{x}^{\star}+\gamma\sum_{t<T}\nabla
f_{v_{t}}(\mathbf{x}^{\star},\xi_{t})\,,\quad\mathbf{y}_{s}=\mathbf{x}^{\star}+\gamma\sum_{s\leqslant
t<T}\nabla f_{v_{t}}(\mathbf{x}^{\star},\xi_{t})\,,\quad s<T\,.$

We thus have:

$\displaystyle\mathbb{E}{{\left\|\mathbf{x}_{T}-\mathbf{x}^{\star}\right\|}}^{2}$
$\displaystyle\leqslant
2(1-\gamma\mu)^{T}\left(\mathbb{E}{{\left\|\mathbf{x}_{0}-\mathbf{x}^{\star}\right\|}}^{2}+\gamma^{2}\mathbb{E}\left[{{\left\|\sum_{s<T}\nabla
f_{v_{s}}(\mathbf{x}^{\star})\right\|}}^{2}\right]\right)$
$\displaystyle\quad+\gamma^{3}L\sum_{t<T}(1-\gamma\mu)^{T-t}\mathbb{E}\left[{{\left\|\sum_{t\leqslant
s<T}\nabla f_{v_{s}}(\mathbf{x}^{\star})\right\|}}^{2}\right]\,.$

Using Lemma 8, we have for any $t\leqslant T$:

$\mathbb{E}\left[{{\left\|\sum_{t\leqslant s<T}\nabla
f_{v_{s}}(\mathbf{x}^{\star})\right\|}}^{2}\right]\leqslant CT\tau_{\rm
mix}\sigma_{\star}^{2}\,,$

for $C=13$. Hence,

$\displaystyle\mathbb{E}{{\left\|\mathbf{x}_{T}-\mathbf{x}^{\star}\right\|}}^{2}$
$\displaystyle\leqslant
2(1-\gamma\mu)^{T}\left(\mathbb{E}{{\left\|\mathbf{x}_{0}-\mathbf{x}^{\star}\right\|}}^{2}+\gamma^{2}TC\tau_{\rm
mix}\sigma_{\star}^{2}\right)$
$\displaystyle\quad+\gamma^{3}L\sum_{t<T}(1-\gamma\mu)^{T-t}(T-t)C\tau_{\rm
mix}\sigma_{\star}^{2}$ $\displaystyle\leqslant
2(1-\gamma\mu)^{T}{{\left\|\mathbf{x}_{0}-\mathbf{x}^{\star}\right\|}}^{2}+\frac{3\gamma
L}{\mu^{2}}C\tau_{\rm mix}\sigma_{\star}^{2}\,,$

using $\sum_{t<T}(1-x)^{t}t\leqslant 1/x^{2}$ and
$(1-z)^{x}x\leqslant\frac{1}{eu}\leqslant 1/(2u)$. Finally, for a stepsize
choice of

$\gamma=\min\left(\frac{1}{L}\,,\,\frac{1}{T\mu}\ln\left(T\frac{{{\left\|\mathbf{x}_{0}-\mathbf{x}^{\star}\right\|}}^{2}}{\frac{3\gamma
L}{\mu^{2}}C\tau_{\rm mix}\sigma_{\star}^{2}}\right)\right)\,,$

we obtain:

$\mathbb{E}\left[{{\left\|\mathbf{x}_{T}-\mathbf{x}^{\star}\right\|}}\right]\leqslant
2e^{-\frac{\mu
T}{L}}{{\left\|\mathbf{x}_{0}-\mathbf{x}^{\star}\right\|}}^{2}+\mathcal{O}\left(\frac{L\tau_{\rm
mix}\sigma_{\star}^{2}}{\mu^{3}T}\right)\,.$

∎

###  D.2 Proof of Proposition 1

###### Proof.

Consider the graph $G$ on the set of nodes
$\mathcal{V}={{\left\\{0,1\right\\}}}$, with probability transitions
$p_{01}=p_{10}=p$ and $p_{00}=p_{11}=1-p$, for some small $p\in(0,1)$. The
relaxation time $\tau_{\rm mix}(1/4)$ of this graph scales as $1/p$.

Consider now $f_{0}(\mathbf{x})=\frac{1}{2}(\mathbf{x}-1)^{2}$ and
$f_{1}(\mathbf{x})=\frac{1}{2}(\mathbf{x}+1)^{2}$ for
$\mathbf{x}\in\mathbb{R}$, so that $\mathbf{x}^{\star}=0$. For $(v_{t})$ a
Markov chain with the given transition probabilities, started at $v_{0}$
following the uniform (stationary) distribution on $\mathcal{V}$, let
$\mathbf{x}_{t}$ be generated with MC-SGD:
$\mathbf{x}_{t+1}=\mathbf{x}_{t}-\gamma\nabla f_{v_{t}}(\mathbf{x}_{t})$ and
$\mathbf{x}_{0}=1$, _i.e._ ,

$\mathbf{x}_{T}=(1-\gamma)^{T}-\gamma\sum_{t<T}(1-\gamma)^{T-t-1}\zeta_{t}\,,$

where $\zeta_{t}\in{{\left\\{-1,1\right\\}}}$ takes value $1$ if $v_{t}=0$ and
value $-1$ if $v_{t}=0$. We have:

$\mathbb{E}\left[(\mathbf{x}_{T}-\mathbf{x}^{\star})^{2}\right]=(1-\gamma)^{2T}+\gamma^{2}\sum_{s<t<T}(1-\gamma)^{2T-t-s-2}\mathbb{E}\left[\zeta_{s}\zeta_{t}\right]\,.$

We compute this second term, and show that it is non-negative for $p\leqslant
1/2$ and of order $\frac{\gamma}{4p}$, so that to reach a given precision
$\varepsilon>0$, is required $\gamma\leqslant 4p\varepsilon$ and thus to make
the first term small, $T$ must verify $T=\Omega(1/(2p\varepsilon))$,
concluding our reasonning.

For $s<t$, we have
$\mathbb{E}\left[\zeta_{s}\zeta_{t}\right]=2\mathbb{P}\left(v_{t-s}=v_{0}|v_{0}\sim\pi^{\star}\right)-1$/
Denoting $z_{k}=\mathbb{P}\left(v_{k}=v_{0}|v_{0}\sim\pi^{\star}\right)$, we
have $z_{k+1}=pz_{k}+(1-p)(1-z_{k})$ and $z_{0}=1$, so that
$z_{k}=\frac{1}{2}(1+(1-2p)^{k})$ for $k\geqslant 0$. This leads to:

$\displaystyle\gamma^{2}\sum_{s<t<T}(1-\gamma)^{2T-t-s-2}\mathbb{E}\left[\zeta_{s}\zeta_{t}\right]$
$\displaystyle=\gamma^{2}\frac{(1-\gamma)(1-2p)}{1-(1-\gamma)(1-2p)}$
$\displaystyle\times\left(\frac{1-(1-\gamma)^{2T}}{1-(1-\gamma)^{2}}-(1-2p)\frac{(1-\gamma)^{T}-(1-2p)^{T}}{2p-\gamma}(1-\gamma)^{T}\right)$

For $\varepsilon\to 0$, in order to have
$\mathbb{E}\left[(\mathbf{x}_{T}-\mathbf{x}^{\star})^{2}\right]\leqslant\varepsilon$,
is required $(1-\gamma)^{T}\leqslant\varepsilon$ so that $\gamma T\to\infty$.
Under $\gamma T\to\infty$, we have

$\gamma^{2}\sum_{s<t<T}(1-\gamma)^{2T-t-s-2}\mathbb{E}\left[\zeta_{s}\zeta_{t}\right]\sim\frac{\gamma}{4p}\,.$

Finally, to reach precision $\varepsilon$, this quantity needs to be upper-
bounded by $\varepsilon(1+o(1))$, so that $\gamma\leqslant
4p\varepsilon^{-1}(1+o(1))$ is necessary. Plugging this in
$(1-\gamma)^{2T}\leqslant\varepsilon$ yields
$T=\tilde{\Omega}(p\varepsilon^{-1})$, the desired result. ∎

##  Appendix E With local noise: proof of Theorem 4

The proof follows the exact same steps as the proof of Theorem 3.

###### Proof.

First, note that, using Lemma 15 in Stich and Karimireddy [2021], we have:

$\mathbb{E}\left[{{\left\|\sum_{t<T}\nabla_{\mathbf{x}}F_{v_{t}}(\mathbf{x}^{\star},\xi_{t})\right\|}}^{2}\right]\leqslant
2\mathbb{E}\left[{{\left\|\sum_{t<T}\nabla
f_{v_{t}}(\mathbf{x}^{\star})\right\|}}^{2}\right]+2T\sigma_{\rm
local}^{2}\,.$

We then have the following lemma, proved exactly as in the previous section.

######  Lemma 10.

For any $\mathbf{y}_{t}\in\mathbb{R}^{d}$ and $t\geqslant 0$, denoting
$\mathbf{y}_{t+1}=\mathbf{y}_{t}-\gamma\nabla_{\mathbf{x}}F_{v_{t}}(\mathbf{x}^{\star},\xi_{t})$,
we have:

${{\left\|\mathbf{x}_{t+1}-\mathbf{y}_{t+1}\right\|}}^{2}\leqslant(1-\gamma\mu){{\left\|\mathbf{x}_{t}-\mathbf{y}_{t}\right\|}}^{2}+\gamma
L{{\left\|\mathbf{y}_{t}-\mathbf{x}^{\star}\right\|}}^{2}\,.$

This leads to:

${{\left\|\mathbf{x}_{T}-\mathbf{y}_{T}\right\|}}^{2}\leqslant(1-\gamma\mu)^{T}{{\left\|\mathbf{x}_{0}-\mathbf{y}_{0}\right\|}}^{2}+\gamma
L\sum_{t<T}(1-\gamma\mu)^{T-t}{{\left\|\mathbf{y}_{t}-\mathbf{x}^{\star}\right\|}}^{2}\,,$

for

$\mathbf{y}_{0}=\mathbf{x}^{\star}+\gamma\sum_{t<T}\nabla_{\mathbf{x}}F_{v_{t}}(\mathbf{x}^{\star},\xi_{t})\,,\quad\mathbf{y}_{s}=\mathbf{x}^{\star}+\gamma\sum_{s\leqslant
t<T}\nabla_{\mathbf{x}}F_{v_{t}}(\mathbf{x}^{\star},\xi_{t})\,,\quad s<T\,.$

We thus have:

$\displaystyle\mathbb{E}{{\left\|\mathbf{x}_{T}-\mathbf{x}^{\star}\right\|}}^{2}$
$\displaystyle\leqslant
2(1-\gamma\mu)^{T}\left(\mathbb{E}{{\left\|\mathbf{x}_{0}-\mathbf{x}^{\star}\right\|}}^{2}+\gamma^{2}\mathbb{E}\left[{{\left\|\sum_{s<T}\nabla_{\mathbf{x}}F_{v_{s}}(\mathbf{x}^{\star},\xi_{s})\right\|}}^{2}\right]\right)$
$\displaystyle\quad+\gamma^{3}L\sum_{t<T}(1-\gamma\mu)^{T-t}\mathbb{E}\left[{{\left\|\sum_{t\leqslant
s<T}\nabla_{\mathbf{x}}F_{v_{s}}(\mathbf{x}^{\star},\xi_{s})\right\|}}^{2}\right]\,.$

To conclude, we use the first inequality of this proof, and Lemma 8, and
proceed as in the proof of Theorem 3 and Corollary 1. ∎

##  Appendix F MC-SAG: proof of Theorem 5

###  F.1 With perfect initialization: Theorem 5.1

We begin classically by proving a descent lemma. This lemma is deterministic,
in the sense that not means $\mathbb{E}$ are present, and it therefore does
not use the Markovian properties of the Markov chain. MC-SAG uses biased
gradients, even in the case where $v_{t}$ are _i.i.d._ , since the algorithm
SAG [Schmidt et al., 2017] is inherently biased (making it unbiased leads to
the SAGA iterations [Defazio et al., 2014]).

Let $\mathbf{G}_{t}=\bar{\mathbf{h}}_{t+1}$ for $t\geqslant 0$, so that
$\mathbf{x}_{t+1}=\mathbf{x}_{t}-\gamma_{t}\mathbf{G}_{t}$. We recall that for
$v\in\mathcal{V}$ and $t\geqslant 0$, $p_{v}(t)$ is the next time (strictly)
the chain hits node $v$, while $d_{v}(t)$ is either the last time the chain
was at the state $v$ (if that happened), or $0$ in $v$ has not yet been
visited.

######  Lemma 11.

Assume that $f$ is $L$-smooth. Then, for any $t\geqslant 0$, we have:

$\displaystyle
f(\mathbf{x}_{t+1})-f(\mathbf{x}_{t})\leqslant-\frac{\gamma_{t}}{2}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}-\frac{\gamma_{t}}{4}{{\left\|\mathbf{G}_{t}\right\|}}^{2}+\frac{\gamma_{t}L^{2}}{2n}\sum_{v\in\mathcal{V}}{{\left\|\sum_{s=d_{v}(t)}^{t-1}\gamma_{s}\mathbf{G}_{s}\right\|}}^{2}\,.$

###### Proof.

For $t\geqslant 0$ and $v\in\mathcal{V}$, let
$p_{v}(t)=\inf{{\left\\{s>t|v_{s}=v\right\\}}}$ and
$d_{v}(t)=\sup{{\left\\{s\leqslant t|v_{s}=v\right\\}}}$ be the next and the
last previous iterates for which $v_{t}=v$ ($d_{v}(t)=0$ by convention, if $v$
has not yet been visited). Denote
$F_{t}=\mathbb{E}\left[f(\mathbf{x}_{t})-f(\mathbf{x}^{\star})\right]$. We
have, using smoothness:

$f(\mathbf{x}_{t+1})\leqslant f(\mathbf{x}_{t})-\gamma_{t}\langle\nabla
f(\mathbf{x}_{t}),\mathbf{G}_{t}\rangle+\frac{\gamma_{t}^{2}L}{2}{{\left\|\mathbf{G}_{t}\right\|}}^{2}\\\
$

Together with $\langle\nabla
f(\mathbf{x}_{t}),\mathbf{G}_{t}\rangle=\frac{1}{2}({{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}+{{\left\|\mathbf{G}_{t}\right\|}}^{2}-{{\left\|\nabla
f(\mathbf{x}_{t})-\mathbf{G}_{t}\right\|}}^{2})$, we obtain:

$\displaystyle f(\mathbf{x}_{t+1})$ $\displaystyle\leqslant
f(\mathbf{x}_{t})-\frac{\gamma_{t}}{2}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}+{{\left\|\mathbf{G}_{t}\right\|}}^{2}-{{\left\|\nabla
f(\mathbf{x}_{t})-\mathbf{G}_{t}\right\|}}^{2}+\frac{\gamma_{t}^{2}L}{2}{{\left\|\mathbf{G}_{t}\right\|}}^{2}$
$\displaystyle\leqslant f(\mathbf{x}_{t})-\frac{\gamma_{t}}{2}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}-\frac{\gamma_{t}}{4}{{\left\|\mathbf{G}_{t}\right\|}}^{2}+\frac{\gamma_{t}}{2}{{\left\|\nabla
f(\mathbf{x}_{t})-\mathbf{G}_{t}\right\|}}^{2}\,,$

as long as $\gamma_{t}\leqslant 1/(2L)$. We thus need to upperbound the bias
${{\left\|\nabla f(\mathbf{x}_{t})-\mathbf{G}_{t}\right\|}}^{2}$. We have:

$\displaystyle{{\left\|\nabla f(\mathbf{x}_{t})-\mathbf{G}_{t}\right\|}}^{2}$
$\displaystyle={{\left\|\frac{1}{n}\sum_{v\in\mathcal{V}}\nabla
f_{v}(\mathbf{x}_{d_{v}(t)})-\nabla f_{v}(\mathbf{x}_{t})\right\|}}^{2}$
$\displaystyle\leqslant\frac{1}{n}\sum_{v\in\mathcal{V}}{{\left\|\nabla
f_{v}(\mathbf{x}_{d_{v}(t)})-\nabla f_{v}(\mathbf{x}_{t})\right\|}}^{2}\,.$

Fix some $v$ in $\mathcal{V}$. We have ${{\left\|\nabla
f_{v}(\mathbf{x}_{t})-\nabla
f_{v}(\mathbf{x}_{d_{v}(t)})\right\|}}^{2}\leqslant
L^{2}{{\left\|\sum_{s=d_{v}(t)}^{t-1}\gamma_{s}\mathbf{G}_{s}\right\|}}^{2}$,
leading to:

$\displaystyle f(\mathbf{x}_{t+1})-f(\mathbf{x}_{t})$
$\displaystyle\leqslant-\frac{\gamma_{t}}{2}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}-\frac{\gamma_{t}}{4}{{\left\|\mathbf{G}_{t}\right\|}}^{2}+\frac{\gamma_{t}L^{2}}{2n}\sum_{v\in\mathcal{V}}{{\left\|\sum_{s=d_{v}(t)}^{t-1}\gamma_{s}\mathbf{G}_{s}\right\|}}^{2}\,.$

∎

We now proceed with the proof of Theorem 5.1.

###### Proof of Theorem 5.1.

We begin with

$\displaystyle f(\mathbf{x}_{t+1})-f(\mathbf{x}_{t})$
$\displaystyle\leqslant-\frac{\gamma_{t}}{2}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}-\frac{\gamma_{t}}{4}{{\left\|\mathbf{G}_{t}\right\|}}^{2}+\frac{\gamma_{t}L^{2}}{2n}\sum_{v\in\mathcal{V}}{{\left\|\sum_{s=d_{v}(t)}^{t-1}\gamma_{s}\mathbf{G}_{s}\right\|}}^{2}\,,$

as a starting point. For $v\in\mathcal{V}$,

$\displaystyle\gamma_{t}{{\left\|\sum_{s=d_{v}(t)}^{t-1}L^{2}\gamma_{s}\mathbf{G}_{s}\right\|}}^{2}$
$\displaystyle\leqslant\sum_{s=d_{v}(t)}^{t-1}(t-d_{v}(t))L^{2}\gamma_{t}\gamma_{s}^{2}{{\left\|\mathbf{G}_{s}\right\|}}^{2}$
$\displaystyle\leqslant\sum_{s=d_{v}(t)}^{t-1}L\gamma_{s}^{2}{{\left\|\mathbf{G}_{s}\right\|}}^{2}\,,$

since $\gamma_{t}\leqslant 1/(L(t-d_{v}(t)))$. Summing for $t<T$, we obtain:

$\displaystyle\sum_{t<T}\frac{\gamma_{t}}{2}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\leqslant
F_{0}-\sum_{t<T}\frac{\gamma_{t}}{2}{{\left\|\mathbf{G}_{t}\right\|}}^{2}+\sum_{t<T}\frac{1}{2n}\sum_{v\in\mathcal{V}}\sum_{s=d_{v}(t)}^{t-1}L\gamma_{s}^{2}{{\left\|\mathbf{G}_{s}\right\|}}^{2}\,.$

Then,

$\displaystyle\sum_{t<T}\sum_{s=d_{v}(t)}^{t-1}L\gamma_{s}^{2}{{\left\|\mathbf{G}_{s}\right\|}}^{2}=\sum_{s<T}{{\left\|\mathbf{G}_{s}\right\|}}^{2}L\gamma_{s}^{2}(p_{v}(s)-s)\,.$

For $\gamma_{s}\leqslant 1/(2L\tau_{\rm hit})$, we have
$\mathbb{E}\left[{{\left\|\mathbf{G}_{s}\right\|}}^{2}\gamma_{s}^{2}(p_{v}(s)-s)\right]\leqslant\frac{1}{2}\mathbb{E}\left[{{\left\|\mathbf{G}_{s}\right\|}}^{2}\gamma_{s}\right]$,
so that:

$\displaystyle\sum_{t<T}\frac{\gamma_{t}}{2}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\leqslant
F_{0}+\sum_{t<T}\left(-\frac{\gamma_{t}}{2}{{\left\|\mathbf{G}_{t}\right\|}}^{2}+K_{t}\right)\,,$

where
$K_{t}=\frac{1}{4n}\sum_{v\in\mathcal{V}}{{\left\|\mathbf{G}_{t}\right\|}}^{2}L\gamma_{t}^{2}(p_{v}(t)-t)$
verifies
$\mathbb{E}\left[K_{t}|\mathcal{F}_{t}\right]\leqslant{{\left\|\mathbf{G}_{t}\right\|}}^{2}\gamma_{t}/4$
since $\gamma_{t}\leqslant 1/(2\tau_{\rm hit})$, where $\mathcal{F}_{t}$ is
the filtration up to time $t$:

$\displaystyle\mathbb{E}\left[K_{t}|\mathcal{F}_{t}\right]$
$\displaystyle=\mathbb{E}\left[\frac{1}{4n}\sum_{v\in\mathcal{V}}{{\left\|\mathbf{G}_{t}\right\|}}^{2}L\gamma_{t}^{2}(p_{v}(t)-t)|\mathcal{F}_{t}\right]$
$\displaystyle=\frac{1}{4n}\sum_{v\in\mathcal{V}}{{\left\|\mathbf{G}_{t}\right\|}}^{2}L\gamma_{t}^{2}\mathbb{E}\left[(p_{v}(t)-t)|\mathcal{F}_{t}\right]\quad\big{(}\mathbf{G}_{t}\,,\,\gamma_{t}\text{
are $\mathcal{F}_{t}$-measurable}\big{)}$
$\displaystyle\leqslant\frac{1}{4n}\sum_{v\in\mathcal{V}}{{\left\|\mathbf{G}_{t}\right\|}}^{2}L\gamma_{t}^{2}\tau_{\rm
hit}\quad\big{(}\text{since
}\mathbb{E}\left[(p_{v}(t)-t)|\mathcal{F}_{t}\right]=\mathbb{E}\left[(p_{v}(t)-t)|v_{t}\right]\leqslant\tau_{\rm
hit}\big{)}$
$\displaystyle\leqslant\frac{1}{8}\gamma_{t}{{\left\|\mathbf{G}_{t}\right\|}}^{2}\quad\big{(}\text{since
}\gamma_{t}\leqslant 1/(2\tau_{\rm hit})\big{)}\,.$

Finally,

$\displaystyle\mathbb{E}\left[\min_{t<T}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]\leqslant\mathbb{E}\left[\frac{2F_{0}}{\sum_{t<T}\gamma_{t}}\right]+\mathbb{E}\left[\frac{\sum_{t<T}\left(-\frac{\gamma_{t}}{2}{{\left\|\mathbf{G}_{t}\right\|}}^{2}+K_{t}\right)}{\sum_{t<T}\gamma_{t}}\right]\,.$

Using Lemma 5 and the above bound on
$\mathbb{E}\left[K_{t}|\mathcal{F}_{t}\right]$, that last term is non-
positive. Using Jensen inequality, we have:

$\displaystyle\mathbb{E}\left[\min_{t<T}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]$
$\displaystyle\leqslant\frac{2F_{0}}{T^{2}}\sum_{t<T}\mathbb{E}\left[\gamma_{t}^{-1}\right]\,.$

Since $\gamma_{t}^{-1}=2L(\tau_{\rm hit}+\sup_{v\in\mathcal{V}}(t-d_{v}(t)))$,
we have $\sum_{t<T}\mathbb{E}\left[\gamma_{t}^{-1}\right]\leqslant
2LT(\tau_{\rm hit}+\tau_{\rm cov})$ using Lemma 4, concluding the proof. ∎

###  F.2 With arbitrary initialization: proof of Theorem 5.2

We no longer assume that $\mathbf{G}_{0}=\nabla f(\mathbf{x}_{0})$ or that
$\mathbf{h}_{v}=\nabla f_{v}(\mathbf{x}_{0})$: $\mathbf{h}_{v}$ are arbitrary
and $\mathbf{G}_{0}=\frac{1}{n}\sum_{v\in\mathcal{V}}\mathbf{h}_{v}$. In that
case, we have the following descent lemma.

######  Lemma 12.

Assume that $f$ is $L$-smooth. Let

$\tilde{\tau}_{\rm cov}=\inf{{\left\\{t\geqslant 1\quad\text{such
that}\quad{{\left\\{v_{0},\ldots,v_{t-1}\right\\}}}=\mathcal{V}\right\\}}}\,.$

Then, for any $t\geqslant 0$, we have:

$\displaystyle f(\mathbf{x}_{t+1})-f(\mathbf{x}_{t})$
$\displaystyle\leqslant-\frac{\gamma_{t}}{2}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}-\frac{\gamma_{t}}{4}{{\left\|\mathbf{G}_{t}\right\|}}^{2}+\frac{\gamma_{t}L^{2}}{n}\sum_{v\in\mathcal{V}}{{\left\|\sum_{s=d_{v}(t)}^{t-1}\gamma_{s}\mathbf{G}_{s}\right\|}}^{2}+\frac{\gamma_{t}\mathds{1}_{t<\tilde{\tau}_{\rm
cov}}}{n}\sum_{v\in\mathcal{V}}{{\left\|\nabla
f_{v}(\mathbf{x}_{0})-\mathbf{h}_{v}\right\|}}^{2}\,.$

###### Proof.

As in Lemma 11, we have

$\displaystyle f(\mathbf{x}_{t+1})\leqslant
f(\mathbf{x}_{t})-\frac{\gamma_{t}}{2}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}-\frac{\gamma_{t}}{4}{{\left\|\mathbf{G}_{t}\right\|}}^{2}+\frac{\gamma_{t}}{2}{{\left\|\nabla
f(\mathbf{x}_{t})-\mathbf{G}_{t}\right\|}}^{2}\,,$

as long as $\gamma_{t}\leqslant 1/(2L)$. We thus again need to upperbound the
bias ${{\left\|\nabla f(\mathbf{x}_{t})-\mathbf{G}_{t}\right\|}}^{2}$. For
$t\geqslant\tilde{\tau}_{\rm cov}$, we have
$\mathbf{G}_{t}=\frac{1}{n}\sum_{v\in\mathcal{V}}\nabla
f_{v}(\mathbf{x}_{d_{v}(t)})$, and so:

$\displaystyle{{\left\|\nabla
f(\mathbf{x}_{t})-\mathbf{G}_{t}\right\|}}^{2}\leqslant\frac{1}{n}\sum_{v\in\mathcal{V}}{{\left\|\nabla
f_{v}(\mathbf{x}_{d_{v}(t)})-\nabla f_{v}(\mathbf{x}_{t})\right\|}}^{2}\,,$

hence the result of Lemma 11 holds for $t\leqslant\tilde{\tau}_{\rm cov}$ (and
so does that of the Lemma we are proving). Then, for
$t\leqslant\tilde{\tau}_{\rm cov}$, $\nabla
f(\mathbf{x}_{t})-\mathbf{G}_{t}=\frac{1}{n}\sum_{v\in\mathcal{V}}\nabla
f_{v}(\mathbf{x}_{t})-\mathbf{h}_{v}^{t}$, where
$\mathbf{h}_{v}^{t}=\mathbf{h}_{v}$ if $v$ hasn’t been visited yet, or
$\mathbf{h}_{v}^{t}=\nabla f_{v}(\mathbf{x}_{d_{v}(t)})$ otherwise. Hence,

$\displaystyle{{\left\|\nabla f(\mathbf{x}_{t})-\mathbf{G}_{t}\right\|}}^{2}$
$\displaystyle\leqslant\frac{1}{n}\sum_{v\in\mathcal{V}}{{\left\|\mathbf{h}_{v}^{t}-\nabla
f_{v}(\mathbf{x}_{t})\right\|}}^{2}$
$\displaystyle\leqslant\frac{2}{n}\sum_{v\in\mathcal{V}}{{\left\|\nabla
f_{v}(\mathbf{x}_{d_{v}(t)})-\nabla
f_{v}(\mathbf{x}_{t})\right\|}}^{2}+\frac{2}{n}\sum_{v\in\mathcal{V}}{{\left\|\nabla
f_{v}(\mathbf{x}_{0})-\mathbf{h}_{v}\right\|}}^{2}$

Since ${{\left\|\nabla f_{v}(\mathbf{x}_{t})-\nabla
f_{v}(\mathbf{x}_{d_{v}(t)})\right\|}}^{2}\leqslant
L^{2}{{\left\|\sum_{s=d_{v}(t)}^{t-1}\gamma_{s}\mathbf{G}_{s}\right\|}}^{2}$,
we have:

$\displaystyle f(\mathbf{x}_{t+1})-f(\mathbf{x}_{t})$
$\displaystyle\leqslant-\frac{\gamma_{t}}{2}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}-\frac{\gamma_{t}}{4}{{\left\|\mathbf{G}_{t}\right\|}}^{2}+\frac{\gamma_{t}L^{2}}{n}\sum_{v\in\mathcal{V}}{{\left\|\sum_{s=d_{v}(t)}^{t-1}\gamma_{s}\mathbf{G}_{s}\right\|}}^{2}+\frac{\gamma_{t}}{n}\sum_{v\in\mathcal{V}}{{\left\|\nabla
f_{v}(\mathbf{x}_{0})-\mathbf{h}_{v}\right\|}}^{2}\,,$

leading to the desired result. ∎

###### Proof of Theorem 5.2.

Starting from

$\displaystyle f(\mathbf{x}_{t+1})-f(\mathbf{x}_{t})$
$\displaystyle\leqslant-\frac{\gamma_{t}}{2}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}-\frac{\gamma_{t}}{4}{{\left\|\mathbf{G}_{t}\right\|}}^{2}+\frac{\gamma_{t}L^{2}}{n}\sum_{v\in\mathcal{V}}{{\left\|\sum_{s=d_{v}(t)}^{t-1}\gamma_{s}\mathbf{G}_{s}\right\|}}^{2}+\frac{\gamma_{t}\mathds{1}_{t<\tilde{\tau}_{\rm
cov}}}{n}\sum_{v\in\mathcal{V}}{{\left\|\nabla
f_{v}(\mathbf{x}_{0})-\mathbf{h}_{v}\right\|}}^{2}\,,$

and mimicking the proof with initialization, we obtain that for
$\gamma_{t}^{-1}=4L(\tau_{\rm hit}+\sup_{v\in\mathcal{V}}(t-d_{v}(t)))$, we
have

$\mathbb{E}\left[\min_{t<T}{{\left\|\nabla
f(\mathbf{x}_{t})\right\|}}^{2}\right]\leqslant\frac{2F_{0}}{T^{2}}\sum_{t<T}\mathbb{E}\left[\gamma_{t}^{-1}\right]+\frac{2\mathbb{E}\left[\tilde{\tau}_{\rm
cov}\right]}{T}\frac{1}{n}\sum_{v\in\mathcal{V}}{{\left\|\nabla
f_{v}(\mathbf{x}_{0})-\mathbf{h}_{v}\right\|}}^{2}\,,$

and we conclude the proof by noticing that $\mathbb{E}\left[\tilde{\tau}_{\rm
cov}\right]\leqslant\tau_{\rm cov}$. ∎

##  Appendix G Numerical illustration of our theory

#### Setting

We place ourselves in the decentralized optimization setting on a graph $G$
with local functions $f_{v}$, and build two toy problems. We compare our
algorithms MC-SGD and MC-SAGA with Walkman [Mao et al., 2020] and
decentralized SGD (D-SGD in Figure 1) [Koloskova et al., 2020, Yu et al.,
2019] with both randomized gossip communications and fixed gossip matrix. We
consider the non-convex loss function
$\ell(\mathbf{x},a,b)=(\sigma(\mathbf{x}^{\top}a)-b)^{2}/2$ where
$\sigma(t)=1/(1+\exp(-t))$ as in Mei et al. [2018]. For $v\in\mathcal{V}$, we
take $f_{v}(x)=\ell(\mathbf{x},a_{v},b_{v})$ for $a_{v}$ and $b_{v}$ random
variables. In Figure 1(a), we take a connected random geometric graph of
$n=50$ nodes in $[0,1]^{2}$ with radius parameter $\rho=0.3$ (nodes are
connected if their distance is less than $\rho$). We consider homogeneous
data: $a_{v},b_{v}$ are taken _i.i.d._ , with $a_{v}\sim\mathcal{N}(0,1)$ and
$b_{v}$ uniform in $[0,1]$. In Figure 1(b), we take the cycle of $n=50$ nodes