# A Multi-Token Coordinate Descent Method for Semi-Decentralized Vertical
Federated Learning

Pedro Valdeira***Department of Electrical and Computer Engineering, Carnegie
Mellon University; email<EMAIL_ADDRESS>†††Institute for Systems and
Robotics, Instituto Superior Técnico.
CMU, IST  Yuejie Chi∗
CMU  Cláudia Soares‡‡‡Department of Computer Science, NOVA School of Science
and Technology.
NOVA  João Xavier†
IST

###### Abstract

Communication efficiency is a major challenge in federated learning (FL). In
client-server schemes, the server constitutes a bottleneck, and while
decentralized setups spread communications, they do not necessarily reduce
them due to slower convergence. We propose Multi-Token Coordinate Descent
(MTCD), a communication-efficient algorithm for semi-decentralized vertical
federated learning, exploiting both client-server and client-client
communications when each client holds a small subset of features. Our multi-
token method can be seen as a parallel Markov chain (block) coordinate descent
algorithm and it subsumes the client-server and decentralized setups as
special cases. We obtain a convergence rate of $\mathcal{O}(1/T)$ for
nonconvex objectives when tokens roam over disjoint subsets of clients and for
convex objectives when they roam over possibly overlapping subsets. Numerical
results show that MTCD improves the state-of-the-art communication efficiency
and allows for a tunable amount of parallel communications.

44footnotetext: A preliminary version of this work was presented at the 2022
NeurIPS Workshop on Federated Learning: Recent Advances and New Challenges
(Valdeira et al., 2022).

##  1 Introduction

Federated Learning (FL) is a machine learning paradigm where data is
distributed across a set of clients who collaborate to learn a model without
sharing local data (McMahan et al., 2017). Most FL literature considers data
distributed by samples (horizontal FL), where each client holds all the
features of a subset of the samples, yet recently there has been a growing
interest on feature-distributed setups (vertical FL), where each client holds
a subset of the features for all samples (He et al., 2018, Chen et al., 2020,
Alghunaim et al., 2021, Liu et al., 2022b, Castiglia et al., 2022). Vertical
FL may be of particular interest for applications using, for example, time
series data measured by personal devices to learn a model of some cross-client
phenomenon of interest (e.g. meteorological), where each sample corresponds to
the data collected across the devices at a given timestamp. Another example
involves performing a computer vision task using multiple views of the same
object, where a sample corresponds to the concatenation of views from
different devices.

FL often deals with the client-server setup, where a server is connected to
all clients and the clients do not communicate with each other, forming a
star-shaped topology. However, such schemes have a single point of failure and
suffer from a communication bottleneck on the server (Lian et al., 2017). On
the other hand, there is extensive literature on decentralized optimization,
where there is no server—from earlier work motivated by applications such as
wireless sensor networks and multiagent control (Nedic and Ozdaglar, 2009,
Duchi et al., 2012, Qu and Li, 2018), to recent work motivated by FL
(Koloskova et al., 2020, Li et al., 2020, Zhao et al., 2022). Yet, these
algorithms often converge slowly in sparse and large networks (Nedic et al.,
2018) and, although they spread the communication load across the network,
they tend to have poor communication efficiency. Semi-Decentralized FL (SDFL)
uses both client-server and client-client communications, reducing the
overhead at the server (Lin et al., 2021) while avoiding the shortcomings of
decentralized setups and being able to handle multiple clusters of clients.

When concerned with the communications between clients, the use of a token
method (Bertsekas, 1997, Nedic and Bertsekas, 2001, Ram et al., 2009,
Johansson et al., 2010, Mao et al., 2020, Hendrikx, 2022), where a model-
embedding token follows a random walk over a communication graph (undergoing
local updates), allows for better communication efficiency (Hendrikx, 2022)
than the more common consensus-based methods (Nedic and Ozdaglar, 2009, Duchi
et al., 2012, Qu and Li, 2018, Koloskova et al., 2020). Yet, the convergence
rate of token methods degrades even faster for larger and sparser networks,
due to a lack of parallel communications (Hendrikx, 2022). Based on the idea
that performing multiple random walks in parallel leads to a linear speed-up
in the cover time (Alon et al., 2008), multi-token methods (Ye et al., 2020,
Chen et al., 2022, Hendrikx, 2022) mitigate this problem by running multiple
tokens simultaneously and combining them.

###  1.1 Our contribution

Motivated by the above observations, we propose an SDFL multi-token algorithm
for vertical FL. Our main contributions are as follows.

  * •

We introduce Multi-Token Coordinate Descent (MTCD), which, to the best of our
knowledge, is the first multi-token method leveraging the SDFL scheme to
achieve a flexible degree of dependence on the server, recovering both client-
server and fully decentralized FL as special cases;

  * •

We show that MTCD converges at a rate of $\mathcal{O}(1/T)$ for nonconvex
objectives when tokens roam over disjoint subsets of clients and for convex
objectives when they roam over possibly overlapping subsets of clients;

  * •

Numerical experiments on both synthetic and real data and for a variety of
communication setups show that MTCD improves the state-of-the-art
communication efficiency.

###  1.2 Related works

#### Coordinate descent.

Coordinate Descent (CD) methods (Wright, 2015), where (blocks of) coordinates
are updated sequentially, rather than simultaneously, are natural candidates
for optimization in feature-distributed learning. The block selection is most
often cyclic (Beck and Tetruashvili, 2013) or independent and identically
distributed at random (Nesterov, 2012, Richtárik and Takáč, 2012). In
contrast, Sun et al. (2019) considers block selection following a Markov
chain. Several extensions to CD have been proposed, such as acceleration and
parallelization (Fercoq and Richtárik, 2015) and distributed CD methods (Liu
et al., 2022b, Chen et al., 2022).

#### Vertical FL.

Existing vertical FL works include He et al. (2018), which generalizes Smith
et al. (2018) to the decentralized setting. Both works use primal-dual
optimization techniques, as does DCPA (Alghunaim et al., 2021), a state-of-
the-art decentralized method. In contrast, the following methods work in the
primal domain, allowing them to learn more general models. In (Chen et al.,
2020), a CD-based method is used, but no local updates are performed, while
Liu et al. (2022b) does consider local updates. This latter work and Castiglia
et al. (2022), which introduces the use of compressed embeddings, lowering the
communication cost, are particularly close to our method. Note that the
communication costs in vertical FL methods typically depend on the number of
samples (or batch size, in the case of stochastic methods) (Alghunaim et al.,
2021, Liu et al., 2022b, Castiglia et al., 2022), further highlighting the
importance of communication efficiency. An interesting line of work related to
vertical FL is hybrid FL (Zhang et al., 2021b), which deals with datasets
distributed both by samples and features. For a more detailed survey of
vertical FL methods, see (Wei et al., 2022, Liu et al., 2022a).

#### Semi-Decentralized FL.

Recently, SDFL approaches have been proposed to lower communication costs and
deal with data heterogeneity (Lin et al., 2021, Guo et al., 2021), and to
handle intermittent connections, latency, and stragglers (Bian and Xu, 2022,
Yemini et al., 2022). Additionally, other SDFL works deal with (multi-layered)
hierarchical networks (Zhang et al., 2021a, Hosseinalipour et al., 2022). SDFL
is also referred to as hybrid FL sometimes, but we opt for the term semi-
decentralized FL to avoid confusion with the data partitioning setting
mentioned above.

##  2 Problem setup

We consider a dataset $\bm{X}\in\mathbb{R}^{N\times d}$ with $N$
$d$-dimensional samples distributed by features across a set of clients
$[K]\coloneqq\\{1,\dots,K\\}$. Client $k$ holds its local data
$\bm{X}_{k}\in\mathbb{R}^{N\times d_{k}}$ and we have
$\bm{X}=[\bm{X}_{1},\cdots,\bm{X}_{K}]$. Note that $d_{1}+\dots+d_{K}=d$. We
consider a broad class of machine learning models, know as split neural
networks (Ceballos et al., 2020), illustrated in Figure 1.

In split neural networks, each client has an associated local model
$h_{k}(\cdot\,;\bm{X}_{k})\colon\bm{\Theta}_{k}\mapsto\mathcal{H}_{k}$
parameterized by $\bm{\theta}_{k}\in\bm{\Theta}_{k}$, which extracts a
(typically lower-dimensional) representation of $\bm{X}_{k}$. For simplicity,
we write $h_{k}(\bm{\theta}_{k})\coloneqq h_{k}(\bm{\theta}_{k};\bm{X}_{k})$.
These embeddings, $h_{k}(\bm{\theta}_{k})$, are then combined using an
aggregation mechanism
$H\colon\mathcal{H}_{1}\times\dots\times\mathcal{H}_{K}\mapsto\mathcal{H}$ to
form $H(h_{1}(\bm{\theta}_{1}),\dots,h_{K}(\bm{\theta}_{K}))$, which is used
as input to a fusion model
$\phi\colon\mathcal{H}\times\bm{\Theta}_{0}\mapsto\mathbb{R}$, parameterized
by $\bm{\theta}_{0}$. Although more aggregation mechanisms are possible
(Ceballos et al., 2020), we focus on aggregation by concatenation (the most
general case) and by sum. While $\bm{\theta}_{k}\in\bm{\Theta}_{k}$ is
associated with $\bm{X}_{k}$, acting as a local model for client $k$, our
fusion model $\bm{\theta}_{0}$ can be learned at different locations,
depending on whether we consider the existence of a server. Split neural
networks include, for example, generalized linear models, such as linear
regression, logistic regression, and support vector machines, where
$h_{k}(\bm{\theta}_{k})=\bm{X}_{k}\bm{\theta}_{k}$ for $k\in[K]$ and
$\bm{\Theta}_{0}$ is an empty set.

Let $\bm{\Theta}$ denote a parameter space such that
$\bm{\Theta}=\bm{\Theta}_{0}\times\bm{\Theta}_{1}\times\dots\times\bm{\Theta}_{K}$
and $f\colon\bm{\Theta}\mapsto\mathbb{R}$ denote our objective function, our
goal is to solve the following optimization problem, which encompasses the
training of split neural networks:

$\min_{\bm{\theta}\in\bm{\Theta}}\;\left\\{f(\bm{\theta})\coloneqq\phi\left(H\big{(}h_{1}(\bm{\theta}_{1};\bm{X}_{1}),\dots,h_{K}(\bm{\theta}_{K};\bm{X}_{K})\big{)},\,\bm{\theta}_{0}\right)\right\\},$
(1)

where the labels $\bm{y}$ are included in the loss function, which we assume
to be known by all clients.

Throughout the paper, we consider Problem (1) and assume $f$ is an $L$-smooth
function. The standard definition of $L$-smoothness is given below. We define
and assume $f^{\star}\coloneqq\min_{\bm{\theta}}f(\bm{\theta})>-\infty$.

Figure 1: A split neural network, where $K$ embeddings are obtained from
neural networks, before an aggregation mechanism $H$ is applied and its result
is inputted into a fusion neural network.

######  Assumption 1 (Smoothness).

A differentiable function $f\colon\mathbb{R}^{d}\mapsto\mathbb{R}$ is
$L$-smooth if there exists some $L\in(0,\infty)$:

$\lVert\nabla f(\bm{x})-\nabla f(\bm{y})\rVert\leq
L\lVert\bm{x}-\bm{y}\rVert,\quad\forall\;\bm{x},\bm{y}\in\mathbb{R}^{d}.$ (A1)

##  3 Proposed method

###  3.1 The fully decentralized setting

We start by introducing a simple, special case of our algorithm, which we
refer to as Single-Token Coordinate Descent (STCD). This method, which is also
a subroutine of our general algorithm, is closely related to Sun et al. (2019)
and the application mentioned therein, taken from Mao et al. (2020). Yet, we
work in the primal domain and on a feature-distributed setting.

#### Setup.

In this section, we do not require the existence of a server. We solve Problem
(1) in a fully decentralized manner, communicating through channels described
by a communication graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}\coloneqq[K]$ is the vertex set and $\mathcal{E}$ the edge set. We
denote the set of neighbors of client $k$ by
$\mathcal{N}_{k}\coloneqq\\{i\colon\\{i,k\\}\in\mathcal{E}\\}$ and define
$\bar{\mathcal{N}}_{k}\coloneqq\mathcal{N}_{k}\cup\\{k\\}$. In this section
only, $\bm{\theta}_{0}$ is associated with some client $k$, which is
responsible for updating both the local model it holds, $\bm{\theta}_{k}$, and
the fusion model $\bm{\theta}_{0}$.444We do this for alignment with the
analysis in Sun et al. (2019), where all blocks are selected following a
Markov Chain. However, in practice, we may want to update $\bm{\theta}_{0}$ at
each client instead, in which case the analysis would need to be adjusted.

#### Token.

Since all clients know $\phi$, if a client knows
$\mathcal{Z}\coloneqq\\{H(h_{1}(\bm{\theta}_{1}),\dots,h_{K}(\bm{\theta}_{K})),\bm{\theta}_{0}\\}$,
it can compute $f$. We call $\mathcal{Z}$ our token. The size of the token
depends on the model being considered. For example, if
$\mathcal{H}_{k}\subseteq\mathbb{R}^{NE}$ for all $k$ (i.e., we have an
$E$-dimensional embedding per sample) and we do aggregation by concatenation,
then $\mathcal{Z}$ is of size $KNE+\dim(\bm{\Theta}_{0})$, where $\dim(\cdot)$
denotes the dimensionality of a space. Yet, for aggregation by sum, we drop
the dependency on $K$. In particular, for generalized linear models,
$\mathcal{Z}=\\{\bm{X}\bm{\theta}\\}$ is of size $N$.

#### The token suffices to perform local CD steps.

We have seen that a client holding $\mathcal{Z}$ can compute $f$. Yet, more
importantly, if client $k$ has access to its local data $\bm{X}_{k}$ and local
model $\bm{\theta}_{k}$, then holding $\mathcal{Z}$ enables it to compute the
partial gradient with respect to $\bm{\theta}_{k}$,

$\displaystyle\nabla_{k}f(\bm{\theta})\coloneqq\nabla_{\bm{\theta}_{k}}f(\bm{\theta})$
$\displaystyle=\nabla_{\bm{\theta}_{k}}\phi\left(H(h_{1}(\bm{\theta}_{1}),\dots,h_{K}(\bm{\theta}_{K})),\bm{\theta}_{0}\right)$
$\displaystyle=\frac{d\phi\left(H(h_{1}(\bm{\theta}_{1}),\dots,h_{K}(\bm{\theta}_{K})),\bm{\theta}_{0}\right)}{dH(h_{1}(\bm{\theta}_{1}),\dots,h_{K}(\bm{\theta}_{K}))}\cdot\frac{dH(h_{1}(\bm{\theta}_{1}),\dots,h_{K}(\bm{\theta}_{K}))}{dh_{k}(\bm{\theta}_{k})}\cdot\frac{dh_{k}(\bm{\theta}_{k})}{d\bm{\theta}_{k}},$

where $\mathcal{Z}$ is used in the computation of the first two terms. This
will allow client $k$ to update its local model $\bm{\theta}_{k}$.

Input : initial point $\bm{\theta}^{0,0}$, initial client $k^{0}$, step-size
$\eta$, number of hops $S$, number of local updates $Q$

1
$\mathcal{Z}^{0,0}\leftarrow\\{H(h_{1}(\bm{\theta}^{0,0}_{1};\bm{X}_{1}),\dots,h_{K}(\bm{\theta}^{0,0}_{K};\bm{X}_{K})),\bm{\theta}^{0,0}_{0}\\}$

2 $\bm{\theta}^{S,Q},\mathcal{Z}^{S,Q},k^{S}\leftarrow$
TokenRoaming(_$\bm{\theta}^{0,0},\mathcal{Z}^{0,0},k^{0},\bm{X},S,Q$_)

3 Function  _TokenRoaming(_$\bm{\theta},\mathcal{Z},k,\bm{D}$ ,S,Q_)_:

4
$\bm{\theta}^{0,0},\mathcal{Z}^{0,0},k^{0}\leftarrow\bm{\theta},\mathcal{Z},k$

5 for  _$s=0,\dots,S$_ do

6 for  _$q=0,\dots,Q-1$ _in client_ $k^{s}$_ do

7 Compute $\bm{\theta}_{k^{s}}^{s,q+1}$ via a CD step (2), using
$\mathcal{Z}^{s,q}$, $\bm{\theta}_{k^{s}}^{s,q}$, and $\bm{D}_{k^{s}}$

8 Compute $\mathcal{Z}^{s,q+1}$ from $\mathcal{Z}^{s,q}$,
$\bm{\theta}_{k^{s}}^{s,q}$, $\bm{\theta}_{k^{s}}^{s,q+1}$, and
$\bm{D}_{k^{s}}$

9

10 Client $k^{s}$ sends $\mathcal{Z}^{s,Q}$ to client
$k^{s+1}\sim\mathcal{U}(\bar{\mathcal{N}}_{k^{s}})$

11
$\bm{\theta}^{s+1,0},\mathcal{Z}^{s+1,0}\leftarrow\bm{\theta}^{s,Q},\mathcal{Z}^{s,Q}$

12

13 return $\bm{\theta}^{S,Q},\mathcal{Z}^{S,Q},k^{S}$

14

Algorithm 1 Single-Token Coordinate Descent

We now describe STCD, summarized in Algorithm 1, where $\mathcal{U}$ denotes
the uniform distribution. We index $\bm{\theta}$ and $\mathcal{Z}$ with two
counters: one for the sequence of clients (and thus coordinate block) visited
while roaming and one for the local updates at each client. To simplify the
description of the algorithm, we omit $\bm{\theta}_{0}$ for the rest of
Section 3.1, as if it were part of the local model of the client it is
associated with for updating purposes. Yet, $\bm{\theta}_{k}$ does not leave
$k$ but $\bm{\theta}_{0}$ does, as $\bm{\theta}_{0}$ is part of the token.

  * •

Initialization: The token $\mathcal{Z}^{s,q}$ must always be in accordance
with $\bm{\theta}^{s,q}$. So, as $\mathcal{Z}^{0,0}$ starts at client $k^{0}$,
this client must know
$\\{H(h_{1}(\bm{\theta}^{0,0}_{1}),\dots,h_{K}(\bm{\theta}^{0,0}_{K})),\bm{\theta}^{0,0}_{0}\\}$.
For some models, we can achieve this by initializing the local models
$\bm{\theta}^{0,0}_{k}$ such that the embeddings
$h_{k}(\bm{\theta}^{0,0}_{k})$ are independent of local data $\bm{X}_{k}$.
When this is not possible, the clients can send their initial embeddings to
$k^{0}$ as a prelude.

  * •

Updating the local model and the token: as explained above, the client holding
the token after $s$ hops, $k^{s}$, can compute the partial gradient with
respect to its local model $\bm{\theta}_{k^{s}}$ locally. This allows it to
perform a CD step. Further, to lower communication costs, we do $Q$ local CD
updates at each client. That is, for $q=0,\dots,Q-1$:

$\bm{\theta}_{k^{s}}^{s,q+1}=\bm{\theta}_{k^{s}}^{s,q}-\eta\nabla_{k^{s}}f(\bm{\theta}^{s,q})$
(2)

and $\bm{\theta}_{k}^{s,q+1}=\bm{\theta}_{k}^{s,q}$ for $k\not=k^{s}$. We must
now update $\mathcal{Z}$ accordingly. To compute $\mathcal{Z}^{s,q+1}$, we use
$\mathcal{Z}^{s,q}$, $h_{k^{s}}(\bm{\theta}_{k^{s}}^{s,q+1})$, and
$h_{k^{s}}(\bm{\theta}_{k^{s}}^{s,q})$, which are held by $k^{s}$. For
example, for aggregation by sum, we have

$H(h_{1}(\bm{\theta}^{s,q+1}_{1}),\dots,h_{K}(\bm{\theta}^{s,q+1}_{K}))=H(h_{1}(\bm{\theta}^{s,q}_{1}),\dots,h_{K}(\bm{\theta}^{s,q}_{K}))+h_{k^{s}}(\bm{\theta}^{s,q+1}_{k^{s}})-h_{k^{s}}(\bm{\theta}^{s,q}_{k^{s}}).$

This allows us to perform multiple local CD steps. Further, after these $Q$
steps, the updated token can be sent to client $k^{s+1}$. Thus, by induction,
we keep the token up-to-date throughout our algorithm.

  * •

Communicating the token: the token is communicated to a neighbor of $k^{s}$.
This results in a sequence of clients (and blocks) that follows a Markov
Chain.

In essence, STCD is a technique allowing for Markov Chain Coordinate Descent
(Sun et al., 2019) to be performed in feature-distributed setups. In terms of
the progress made in the parameter space, Algorithm 1 differs from Sun et al.
(2019) only in that we consider local updates with $Q>1$.

#### Convergence guarantees.

If $f$ is an $L$-smooth function (A1) with a nonempty set of minimizers and
$(\bm{\theta}^{i})^{r}_{i=1}$ is a sequence generated by Algorithm 1, Sun et
al. (2019) give convergence guarantees for $Q=1$. In particular, let $r=sQ+q$,
we have under mild assumptions on the Markov chain (for example, if the Markov
chain is time-homogeneous, irreducible, and aperiodic) that
$\lim_{r\to\infty}\mathbb{E}\lVert\nabla f(\bm{\theta}^{r})\rVert=0$ and, let
$\Delta\coloneqq f\left(\bm{\theta}^{0}\right)-f^{\star}$,

$\mathbb{E}\left[\min_{i\in[r]}\lVert\nabla
f(\bm{\theta}^{i})\rVert^{2}\right]\leq\frac{(\Omega_{1}(\tau-1)^{2}+\Omega_{2})\Delta}{r},$
(3)

where $\Omega_{1}$ and $\Omega_{2}$ are constants that depend on the minimum
value of the stationary distribution of the Markov chain $\pi_{\min}$, the
step-size $\eta$, and the smoothness constant $L$. Further, $\tau$ denotes the
$\frac{\pi_{\min}}{2}$-mixing time of the the Markov chain. (We present all
the aforementioned Markov chain-related terms in Appendix A.) While Sun et al.
(2019) only consider $Q=1$ explicitly, their analysis can also cover the $Q>1$
case. To see this, consider a virtual dynamic graph
$\mathcal{G}^{r}=(\mathcal{V},\mathcal{E}^{r})$ where $\mathcal{V}$ is the
original vertex set and, recalling that $\mathcal{E}$ is the original edge
set,

$\mathcal{E}^{r}=\begin{cases}\mathcal{E}\quad&\text{if }r\text{ mod }Q=0,\\\
\\{\\{i,i\\}:i\in\mathcal{V}\\}&\text{otherwise}.\end{cases}$

Running STCD on $\mathcal{G}^{r}$ with a single local update is equivalent to
running STCD on the original graph $\mathcal{G}$ with $Q$ local updates. This
dynamic graph preserves the properties required for the analysis to hold. To
see this, let $\bm{P}$ denote the transition matrix of a random walk on the
original graph $\mathcal{G}$ and let $\bm{P}(r)$ denote the transition matrix
of a random walk on $\mathcal{G}^{r}$. Note that $\bm{P}(r)=\bm{I}$ for all
$r\mod Q\not=0$, where $\bm{I}$ denotes the identity matrix, and
$\bm{P}(r)=\bm{P}$ for all $r\mod Q=0$. Assuming, for simplicity, that $R\geq
Q$, we have that $\bm{P}(r)\bm{P}(r+1)\dots\bm{P}(r+R)=\bm{P}^{\lfloor
R/Q\rfloor}$. We thus recover the results in Sun et al. (2019) up to a factor
of $Q$ in the mixing time. (That is, in (3), we replace $\tau$ by $Q\tau$.)

#### Limitations.

The decentralized token algorithm in this section has an appealing simplicity.
However, while it outperforms state-of-the-art feature-distributed learning
algorithms in a variety of setups, as we will see in Section 4, its
performance deteriorates faster with network connectivity than these
decentralized consensus-based algorithms and its convergence per iteration can
be rather slow. These problems will be mitigated by the more general multi-
token method presented next.

###  3.2 Semi-decentralized setting

In Section 3.1, we introduced a special case of MTCD where a single token
roams over a fully decentralized set of clients. We now present our method in
the semi-decentralized setting, which subsumes the setting in Section 3.1 as a
special case. Multi-token CD alternates between a _roaming_ step and a
_syncing_ step.

  * •

Roaming. We start with multiple, matching tokens at a subset of the clients.
As each token performs a different random walk realization, they undergo
different sequences of CD updates, becoming distinct.

  * •

Syncing. To leverage these parallel computations while keeping our model
estimates coupled, we periodically sync the roaming tokens at the server,
combining the progress of multiple CD sequences.

By alternating between these two steps, we get a communication-efficient
algorithm with a flexible degree of parallelization, depending on the number
of tokens and the frequency at which we sync them. This allows us to smoothly
control the trade off between the communication efficiency of settings with
less parallel computations and the faster iteration convergence of settings
with more parallel computations.

We further generalize STCD by allowing the use of stochastic gradient
estimates. Let $\bm{B}\in\mathbb{R}^{B\times d}$ denote a mini-batch of size
$B$ defined by a random set of indices $\mathcal{B}\subseteq[N]$, we make the
following standard assumptions that our gradient estimate is unbiased and has
a bounded variance. For clarity, we make the dependency on $\bm{X}$ explicit
by writing $\nabla f(\bm{\theta};\bm{X})=\nabla f(\bm{\theta})$.

######  Assumption 2 (Unbiased gradients).

For any mini-batch $\bm{B}$, the stochastic gradient is unbiased:

$\mathbb{E}_{\mathcal{B}}[\nabla f(\bm{\theta};\bm{B})]=\nabla
f(\bm{\theta};\bm{X}),\quad\forall\;\bm{\theta}\in\mathbb{R}^{d}.$ (A2)

######  Assumption 3 (Bounded variance).

For any mini-batch $\bm{B}$, there exists a constant $\sigma\geq 0$ such that:

$\mathbb{E}_{\mathcal{B}}\lVert\nabla f(\bm{\theta};\bm{B})-\nabla
f(\bm{\theta};\bm{X})\rVert^{2}\leq\frac{\sigma^{2}}{B},\quad\forall\;\bm{\theta}\in\mathbb{R}^{d}.$
(A3)

Figure 2: Semi-decentralized setup. Client-server communications are
represented by dashed blue lines and client-client communications by solid
green lines.

#### Setup.

In addition to a communication graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$,
we now also consider the existence of a central server with links to all
clients, as illustrated in Figure 2. The existence of a server brings a change
to the model partitioning: $\bm{\theta}_{0}$ is now updated at the server.
Further, we now have $\Gamma$ tokens roaming simultaneously. Each token
$\mathcal{Z}_{\gamma}$ has an associated model estimate $\bm{\theta}(\gamma)$,
for $\gamma\in[\Gamma]$. Thus, during the roaming step, each client $k$ must
now keep up to $\Gamma$ local model estimates $\bm{\theta}_{k}(\gamma)$ in
memory.555In practice, it suffices to to add a copy of $\bm{\theta}^{t}$ as a
new token visits during a given roaming step (with a maximum of $\Gamma$ model
estimates at a client), resetting the number of copies when syncing. To
simplify the description of the algorithm, we define
$[\Gamma]_{0}\coloneqq[\Gamma]\cup\\{0\\}$, with token $\gamma=0$ staying at
the server throughout the roaming step.

We now describe MTCD, summarized in Algorithm 2, where $k_{\gamma}^{t,s}$
denotes the client holding token $\gamma$ after $t$ synchronizations and $s$
hops and $P_{\gamma}$ denotes a distribution over the clients, for
$\gamma\in[\Gamma]$. We index $\bm{\theta}$ and $\mathcal{Z}$ with three
counters: one for synchronizations at the server and two matching the counters
used in STCD. For simplicity, we write
$\mathcal{Z}^{t}\coloneqq\mathcal{Z}^{t,0,0}_{1}=\dots=\mathcal{Z}^{t,0,0}_{\Gamma}$
and
$\bm{\theta}^{t}\coloneqq\bm{\theta}^{t,0,0}(1)=\dots=\bm{\theta}^{t,0,0}(\Gamma)$.

  * •

Initialization: all model-token pairs
$(\bm{\theta}(\gamma),\mathcal{Z}_{\gamma})$ are initialized to the same
values. As in STCD, $\mathcal{Z}_{\gamma}$ must be in accordance with
$\bm{\theta}(\gamma)$.

  * •

Roaming: The server samples a set of indices $\mathcal{B}^{t}$ and
communicates it to each client $k$, which returns its local embedding
$h_{k}(\bm{\theta}^{t}_{k};\bm{B}^{t})$. This allows the server to compute
token $\mathcal{Z}^{t}$ and send copies of it to start the roaming step at
$k^{t,0}_{\gamma}\sim P_{\gamma}$, where
$P_{\gamma}(k)\coloneqq\mathbb{P}(k^{t,0}_{\gamma}=k)$. Note that $P_{0}$ is a
point mass distribution with support over the server, $k=0$ (a node without
neighbors). As $\mathcal{Z}_{\gamma}$ reaches client $k^{t,s}_{\gamma}$, it is
used to perform a local CD step on model estimate $\bm{\theta}(\gamma)$ with
respect to block $k^{t,s}_{\gamma}$ and is then updated accordingly. Each
$\mathcal{Z}_{\gamma}$ roams for $S$ hops, as in STCD. In parallel,
$\bm{\theta}_{0}(0)$ is updated at the server.

  * •

Syncing: after $S$ hops, each client combines its model estimates, obtaining
$\bm{\theta}^{t+1}_{k}=\sum_{\gamma=1}^{\Gamma}w_{k\gamma}\bm{\theta}^{t,S,Q}_{k}(\gamma)$.
We cover the choice of $\bm{w}_{k}\coloneqq(w_{k1},\dots,w_{k\Gamma})$, which
lies in the $\Gamma$-dimensional probability simplex, later.

Input : initial point $\bm{\theta}^{0}$, step-size $\eta$, number of hops $S$,
number of local updates $Q$,

model estimates combination weights $\\{w_{k\gamma}\\}$, distributions
$\\{P_{\gamma}\\}$

1 for  _$t=0,\dots,T-1$_ do

2 Server samples batch indices $\mathcal{B}^{t}\subseteq[N]$ and sends them to
clients

3 for  _$k\in[K]$ _in parallel__ do

4 Client $k$ sends its local embedding $h_{k}(\bm{\theta}^{t}_{k};\bm{B}^{t})$
to the server

5

6 Server computes token
$\mathcal{Z}^{t}\leftarrow\\{H(h_{1}(\bm{\theta}^{t}_{1};\bm{B}^{t}),\dots,h_{K}(\bm{\theta}^{t}_{K};\bm{B}^{t})),\bm{\theta}^{t}_{0}\\}$

7 for  _$\gamma\in[\Gamma]_{0}$ _in parallel__ do

8 Server sends $\mathcal{Z}^{t}$ to $k^{t,0}_{\gamma}\sim P_{\gamma}$

9
$\bm{\theta}^{t,S,Q}(\gamma),\mathcal{Z}^{t,S,Q}_{\gamma},k^{t,S}_{\gamma}\leftarrow$
TokenRoaming(_$\bm{\theta}^{t},\mathcal{Z}^{t},k^{t,0}_{\gamma},\bm{B}^{t},S,Q$_)

10

11 for  _$k\in[K]_{0}$ _in parallel__ do

12
$\bm{\theta}^{t+1}_{k}=\sum_{\gamma=1}^{\Gamma}w_{k\gamma}\bm{\theta}^{t,S,Q}_{k}(\gamma)$

13

14

Algorithm 2 Multi-Token Coordinate Descent

#### Recovering client-server and decentralized setups.

On the one hand, if no client-server communications are available
($S\to\infty$), our algorithm is reduced to a fully decentralized one,
recovering STCD. On the other hand, if the edge set $\mathcal{E}$ is empty, we
recover the client-server setting. In this case, if we assign a token to each
client ($\Gamma=K$ and each $P_{\gamma}$ has support over a single different
client), we get full participation, as in Liu et al. (2022b). In contrast, if
$\Gamma<K$, we recover a partial participation client-server scheme. To the
best of our knowledge, this is the first partial participation vertical FL
algorithm with multiple local updates.

In general, as we increase the amount of parallel computations (by increasing
$\Gamma$) and client-server communications (by lowering $S$), the
communication efficiency and the number of iterations needed to converge both
decrease. Given this trade-off, we see that our choice of $S$ and $\Gamma$
depends on the application.

Having introduced the general MTCD algorithm, we now go over two particular
instances of it, both for semi-decentralized setups, and present convergence
guarantees for each.

#### Setting with a token per cluster.

We now present some convergence guarantees for MTCD in the case where we have
$C$ disjoint clusters of clients $\mathcal{C}_{1},\dots,\mathcal{C}_{C}$ and
one token roams each cluster, hence $\Gamma=C$. Without loss of generality, we
assume $\gamma$ roams $\mathcal{C}_{\gamma}$, allowing us to use $\gamma$ and
$c$ interchangeably. Thus, $P_{\gamma}$ has support over
$\mathcal{C}_{\gamma}$, and only over $\mathcal{C}_{\gamma}$. We also define a
cluster containing only the server, $\mathcal{C}_{0}\coloneqq\\{0\\}$.

These clusters may correspond to the natural topology of the communication
graph, due to physical limitations or to privacy constraints preventing
communications between clients in different clusters (e.g., households or
companies). Yet, we may also generate artificial partitioning of the original
graph, prior to learning our model, in order to allow for the use of multiple
tokens while avoiding overlapping trajectories, rather than having a single
token roaming over a too large (and thus poorly connected) graph.

Since in this setting the blocks of coordinates being updated in each model
estimate are disjoint, we let $\bm{w}_{k}\in\mathbb{R}^{\Gamma}$ be the one-
hot encoding for the token that visits client $k$, thus combining the model
estimates by simply taking the updated version of each block.

######  Theorem 1.

Let $f$ have a nonempty set of minimizers and let all $f(\cdot;\bm{B})$ be
$L$-smooth (A1) and have an unbiased gradient (A2) with a bounded variance
(A3). If $\left(\bm{\theta}^{t}\right)$ is a sequence generated by Algorithm 2
with $\eta\in\left(0,\frac{\rho}{(L+1)SQ(\rho+Se(1+e))}\right)$ under the
token per cluster setting (that is, $P$, $\mathcal{G}$, and $\bm{w}_{k}$ as
explained above) and $\mathbb{P}(k^{t,0}_{\gamma}=k)>0$ for all $\gamma$ and
$k\in\mathcal{C}_{\gamma}$, then:

$\mathbb{E}\left[\frac{1}{T}\sum_{t=0}^{T-1}\left\lVert\nabla
f\left(\bm{\theta}^{t}\right)\right\rVert^{2}\right]=\mathcal{O}\left(\frac{\Delta}{T}+\frac{\sigma^{2}}{B}\right),$
(4)

where the expectation is over $\\{{k}^{t,s}_{c}\\}$ and
$\\{\mathcal{B}_{t}\\}$. Here, $\Delta\coloneqq
f\left(\bm{\theta}^{0}\right)-f^{\star}$.

Encouragingly, we see that, for full batch (exact gradient), we recover the
$\mathcal{O}(\Delta/T)$ rate of convergence for the (expected) squared norm of
the gradient of centralized CD methods. Further, for mini-batches, by choosing
a sufficiently large batch size $B=\Omega(\sigma^{2}/\epsilon)$ we can
preserve the iteration complexity to reach
$\mathbb{E}\left[\frac{1}{T}\sum_{t=0}^{T-1}\left\lVert\nabla
f\left(\bm{\theta}^{t}\right)\right\rVert^{2}\right]\leq\epsilon$.

#### Setting with overlapping token trajectories.

We now present some convergence guarantees for MTCD in the setting where we
allow for overlapping token trajectories. We propose choosing the convex
combination weights to be
$\bm{w}_{k}=(\frac{1}{\Gamma},\dots,\frac{1}{\Gamma})\in\mathbb{R}^{\Gamma}$
for all $k$, thus combining the model estimates by averaging them. We also
consider, for simplicity, that $P_{\gamma}=P$, and assume that distribution
$P$ has support over all clients.

In this setting, to handle the periodic combination by averaging of the model
estimates, we develop convergence guarantees for convex objectives. The
standard definition of convexity is given below.

######  Assumption 4 (Convexity).

A function $f\colon\mathbb{R}^{d}\mapsto\mathbb{R}$ is convex if for all
$a\in[0,1]$:

$f(a\bm{x}+(1-a)\bm{y})\leq
af(\bm{x})+(1-a)f(\bm{y}),\quad\forall\;\bm{x},\bm{y}\in\mathbb{R}^{d}.$ (A4)

######  Theorem 2.

Let $f$ be convex (A4) and have a nonempty set of minimizers and let all
$f(\cdot;\bm{B})$ be $L$-smooth (A1) and have an unbiased gradient (A2) with a
bounded variance (A3). If $\left(\bm{\theta}^{t}\right)$ is a sequence
generated by Algorithm 2 with for
$\eta\in\left(0,\frac{\rho^{\prime}}{(L+1)SQ(\rho^{\prime}+Se(1+e))}\right)$
under the overlapping tokens setting (that is, $P$, $\mathcal{G}$, and
$\bm{w}_{k}$ as explained above) and $\mathbb{P}(k^{t,0}_{\gamma}=k)>0$ for
all $\gamma\in[\Gamma]$ and $k\in[K]$, then:

$\mathbb{E}\left[\frac{1}{T}\sum_{t=0}^{T-1}\left\lVert\nabla
f\left(\bm{\theta}^{t}\right)\right\rVert^{2}\right]=\mathcal{O}\left(\frac{\Delta}{T}+\frac{\sigma^{2}}{B}\right),$

where the expectation is over $\\{{k}^{t,s}_{\gamma}\\}$ and
$\\{\mathcal{B}_{t}\\}$. Here, $\Delta\coloneqq
f\left(\bm{\theta}^{0}\right)-f^{\star}$.

As in the token per cluster setting, we recover the $\mathcal{O}(\Delta/T)$
rate for the (expected) squared norm of the gradient when the exact gradient
is used, matching the rate of centralized CD methods, and, for a sufficiently
large mini-batch size $B=\Omega(\sigma^{2}/\epsilon)$, we preserve the
iteration complexity to reach
$\mathbb{E}\left[\frac{1}{T}\sum_{t=0}^{T-1}\left\lVert\nabla
f\left(\bm{\theta}^{t}\right)\right\rVert^{2}\right]\leq\epsilon$.

##  4 Experiments

We test our method empirically, comparing it to DCPA (Alghunaim et al., 2021),
a state-of-the-art fully decentralized method, and a standard vertical FL
(S-VFL) method which, since we do not consider compression in our experiments,
coincides with both C-VFL (Castiglia et al., 2022) and FedBCD (Liu et al.,
2022b). Note that, while some trajectories have a small variance, making the
confidence interval hard to see, all experiments are run for 5 seeds.

###  4.1 Convex problems

In this section, we use CVXPY (Diamond and Boyd, 2016) to obtain $f^{\star}$,
to use the (relative) suboptimality gap
$\frac{f(\bm{\theta}^{t})-f^{\star}}{f^{\star}}$ as a metric. We define
iteration as the cumulative number of hops and denote by $C_{C2C}$ and
$C_{C2S}$ the cost of Client-To-Client and Client-To-Server communications,
respectively, whose ratio is important for SDFL. For simplicity, we assume
$C_{C2S}$ is the same for communications from the client to the server and
vice-versa, although this is often not the case. Throughout Section 4, we
consider $C_{C2S}/C_{C2C}=100$ when plotting the suboptimality gap with
respect to the communication cost, multiplying the number of $C_{C2C}$
communications by $0.01$ (each communication unit is the size of the token,
which varies with the setup) before adding them to the number of C2S
communications, to obtain the communication costs. For MTCD, we assume a
uniform distribution over the clients when resuming roaming. In Section 4.1,
we allow for the tokens to overlap.

We perform ridge regression on a dataset generated following the same process
as (Alghunaim et al., 2021), with $N=1000$ samples and $d=2000$ features split
evenly across clients. We have
$f(\bm{\theta})=\left\|\bm{X}\bm{\theta}-\bm{y}\right\rVert_{2}^{2}/2+\alpha\|\bm{\theta}\rVert_{2}^{2}/2$,
with $\alpha=10$. For this problem, we use $\eta=10^{-5}$ and $Q=20$ for MTCD
and $\eta=5\times 10^{-7}$ and $Q=20$ for S-VFL. For DCPA, we use
$\mu_{w}=0.01$, $\mu_{y}=0.0003$, and $\mu_{x}=0.03$.

We perform sparse logistic regression on the Gisette dataset (Guyon et al.,
2004), where $N=6000$ and $d=5000$, again split evenly across clients. Let
$s(z)\coloneqq(1+e^{-z})^{-1}$ and $\beta=1$:

$\textstyle{f(\bm{\theta})=-\sum_{n}\left[y_{n}\log
s(\bm{x}_{n}^{\top}\bm{\theta})+(1-y_{n})\log(1-s(\bm{x}_{n}^{\top}\bm{\theta}))\right]+\beta\|\bm{\theta}\rVert_{1},\quad
y_{n}\in\\{0,1\\},\,n\in[N].}$

where $\bm{x}_{n}$ and $y_{n}$ denote samples and labels, respectively. We use
$\eta=10^{-4}$ and $Q=30$ for MTCD and
$\mu_{w}=0.001,\mu_{y}=0.00003,\mu_{x}=0.003$ for DCPA.666In DCPA, the lack of
a closed form solution for the proximal operator of the convex conjugate of
the logistic regression loss leads to the need to solve a local optimization
problem at each client at every iteration.

Figure 3: The left four plots correspond to an Erdős–Rényi graph with $p=0.4$
and right four plots to a path graph, all with $K=40$. The top row concerns
ridge regression and the bottom row concerns sparse logistic regression. We
consider a communication unit consisting of $N$ scalars. The $S\to\infty$ MTCD
run has $\Gamma=1$.

(a) Complete graph ($\alpha_{\mathcal{G}}=40$)

(b) Erdős–Rényi graph with $p=0.4$ ($\alpha_{\mathcal{G}}=7.7$)

(c) Erdős–Rényi graph with $p=0.2$ ($\alpha_{\mathcal{G}}=1.4$)

(d) Grid graph ($5\times 8$) ($\alpha_{\mathcal{G}}=0.15$)

(e) Cycle graph ($\alpha_{\mathcal{G}}=0.025$)

(f) Path graph ($\alpha_{\mathcal{G}}=0.0061$)

Figure 4:  Ridge regression with $N=4000$ and $d=200$ across six different
network topologies, all with $K=40$ clients. Each communication unit consists
of $N$ scalars. The MTCD run has $\Gamma=1$. Algebraic connectivity,
$\alpha_{\mathcal{G}}$, is the second smallest eigenvalue of the Laplacian
matrix of graph $\mathcal{G}$.

#### Fully decentralized setting.

In Figure 3, we see that, while MTCD with $S\to\infty$ and $\Gamma=1$ (that
is, STCD) does not improve upon DCPA in terms of progress per iteration, it is
significantly more communication efficient. Yet, STCD is particularly
vulnerable to poorly connected networks, as seen when going from an
Erdős–Rényi graph to a path graph. Note that, for sparse logistic regression,
while the proximal term used to handle the regularizer is not covered by our
analysis, it does well empirically. Figure 4 shows additional ridge regression
experiments in the $N\gg d$ regime across six different graph topologies.

Figure 5: Experiment on a $K=80$ path graph. For the top row, the MTCD run
with $S\to\infty$ has $\Gamma=1$ and the one with $S=64$ has $\Gamma=2$. For
the bottom row, all MTCD runs have $\Gamma=2$.

#### SDFL setting.

We now tackle the same ridge regression problem, now focusing on path graphs,
where poor connectivity is a greater challenge. In Figure 5, we see in the top
row that our method improves upon the communication efficiency of the other
methods. When plotting the number of communications needed to attain a
suboptimality gap of $10^{-4}$ for each $C_{C2C}/C_{C2S}$, we see that, for
different values of $C_{C2C}/C_{C2S}$, the communication efficiency of SDFL
methods varies. In the bottom row, we see that, as we increase the syncing
frequency, the convergence per iterations speeds up and the communication
efficiency decreases, as expected. This illustrates the flexibility of our
method, which allows us to choose a regime at which to operate.

###  4.2 Neural network training

We train an MVCNN (Su et al., 2015) model on ModelNet10 (Wu et al., 2015), a
dataset of 3D CAD models. We consider $12$ clients split into two clusters of
six clients, each capturing a different (2D) view of each object, and run MTCD
for both complete and path graphs with $S=6$. We use a fixed $\eta=0.001$ for
S-VFL. When running MTCD on 2 complete graph clusters with 6 clients each, we
also start with $\eta=0.001$ but halve it every 20 epochs. On the path graph
clusters, we start with $\eta=0.0005$ and halve it every 20 epochs. For both
both types of graph, we use $S=6$. We use $Q=10$ and a batch size of 64 for
both MTCD and S-VFL.

We also train a ResNet18 (He et al., 2016) on CIFAR-10 (Krizhevsky et al.,
2009), for $K=4$ and two clusters (2 clients each). For MTCD, we use $S=2$. We
use a fixed $\eta=0.0001$, $Q=10$ and a batch size of 100 for both S-VFL and
MTCD. For MTCD, we use $S=2$.

In Figure 6, we present the results of the ModelNet10 and the CIFAR-10
experiments, both in the token-per-cluster setting. In both, we observe a
similar performace in terms of convergence per iteration, but that MTCD
outperforms the baseline in communication efficiency.

Figure 6: The two plots on the left regard ModelNet10 and the two on the right
regard CIFAR-10. We use
$\\{h_{1}(\bm{\theta}_{1}),\dots,h_{K}(\bm{\theta}_{K}),\bm{\theta}_{0}\\}$ as
a communication unit and, for simplicity, we assume that the embeddings and
the server model have the same size.

##  5 Conclusions

We formalize the multi-token SDFL scheme and propose MTCD, a communication-
efficient SDFL algorithm for vertical FL. We provide convergence guarantees
for our method and show empirically the improved communication efficiency of
our algorithm as well as the power of endowing decentralized methods with
periodical client-server communications. A natural extension to this work is
to consider compression and privacy mechanisms, such as differential privacy.

## Acknowledgements

This work is supported in part by the Fundação para a Ciência e a Tecnologia
through the Carnegie Mellon Portugal Program; by the grants U.S. National
Science Foundation CCF-2007911 and ECCS-2318441; and by the CMU-Portugal
project CMU/TIC/0016/2021.

## References

  * Alghunaim et al. (2021) S. A. Alghunaim, Q. Lyu, M. Yan, and A. H. Sayed.  Dual consensus proximal algorithm for multi-agent sharing problems.  _IEEE Transactions on Signal Processing_ , 69:5568–5579, 2021.
  * Alon et al. (2008) N. Alon, C. Avin, M. Koucky, G. Kozma, Z. Lotker, and M. R. Tuttle.  Many random walks are faster than one.  In _Proceedings of the twentieth annual symposium on parallelism in algorithms and architectures_ , pages 119–128, 2008.
  * Beck and Tetruashvili (2013) A. Beck and L. Tetruashvili.  On the convergence of block coordinate descent type methods.  _SIAM Journal on Optimization_ , 23(4):2037–2060, 2013.
  * Bertsekas (1997) D. P. Bertsekas.  A new class of incremental gradient methods for least squares problems.  _SIAM Journal on Optimization_ , 7(4):913–926, 1997.
  * Bian and Xu (2022) J. Bian and J. Xu.  Mobility improves the convergence of asynchronous federated learning.  _arXiv:2206.04742_ , 2022.
  * Castiglia et al. (2022) T. J. Castiglia, A. Das, S. Wang, and S. Patterson.  Compressed-VFL: Communication-efficient learning with vertically partitioned data.  In _International Conference on Machine Learning_ , pages 2738–2766. PMLR, 2022.
  * Ceballos et al. (2020) I. Ceballos, V. Sharma, E. Mugica, A. Singh, A. Roman, P. Vepakomma, and R. Raskar.  Splitnn-driven vertical partitioning.  _arXiv preprint arXiv:2008.04137_ , 2020.
  * Chen et al. (2022) H. Chen, Y. Ye, M. Xiao, and M. Skoglund.  Asynchronous parallel incremental block-coordinate descent for decentralized machine learning.  _arXiv:2202.03263_ , 2022.
  * Chen et al. (2020) T. Chen, X. Jin, Y. Sun, and W. Yin.  VAFL: a method of vertical asynchronous federated learning.  _arXiv:2007.06081_ , 2020.
  * Davis and Yin (2015) D. Davis and W. Yin.  Convergence rate analysis of several splitting schemes, 2015.
  * Diamond and Boyd (2016) S. Diamond and S. Boyd.  CVXPY: A Python-embedded modeling language for convex optimization.  _Journal of Machine Learning Research_ , 17(83):1–5, 2016.
  * Duchi et al. (2012) J. C. Duchi, A. Agarwal, and M. J. Wainwright.  Dual averaging for distributed optimization: Convergence analysis and network scaling.  _IEEE Transactions on Automatic Control_ , 57(3):592–606, 2012.
  * Fercoq and Richtárik (2015) O. Fercoq and P. Richtárik.  Accelerated, parallel, and proximal coordinate descent.  _SIAM Journal on Optimization_ , 25(4), 2015.
  * Guo et al. (2021) Y. Guo, Y. Sun, R. Hu, and Y. Gong.  Hybrid local SGD for federated learning with heterogeneous communications.  In _International Conference on Learning Representations_ , 2021.
  * Guyon et al. (2004) I. Guyon, S. Gunn, A. Ben-Hur, and G. Dror.  Result analysis of the NIPS 2003 feature selection challenge.  _Advances in neural information processing systems_ , 17, 2004.
  * He et al. (2016) K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016.
  * He et al. (2018) L. He, A. Bian, and M. Jaggi.  COLA: Decentralized linear learning.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Hendrikx (2022) H. Hendrikx.  A principled framework for the design and analysis of token algorithms.  _arXiv:2205.15015_ , 2022.
  * Hosseinalipour et al. (2022) S. Hosseinalipour, S. S. Azam, C. G. Brinton, N. Michelusi, V. Aggarwal, D. J. Love, and H. Dai.  Multi-stage hybrid federated learning over large-scale D2D-enabled fog networks.  _IEEE/ACM Transactions on Networking_ , 30(4):1569–1584, 2022.
  * Johansson et al. (2010) B. Johansson, M. Rabi, and M. Johansson.  A randomized incremental subgradient method for distributed optimization in networked systems.  _SIAM Journal on Optimization_ , 20(3):1157–1170, 2010.
  * Koloskova et al. (2020) A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich.  A unified theory of decentralized SGD with changing topology and local updates.  In _International Conference on Machine Learning_ , pages 5381–5393. PMLR, 2020.
  * Krizhevsky et al. (2009) A. Krizhevsky, G. Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Levin and Peres (2017) D. A. Levin and Y. Peres.  _Markov chains and mixing times_ , volume 107.  American Mathematical Soc., 2017.
  * Li et al. (2020) B. Li, S. Cen, Y. Chen, and Y. Chi.  Communication-efficient distributed optimization in networks with gradient tracking and variance reduction, 2020.
  * Lian et al. (2017) X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu.  Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Lin et al. (2021) F. P.-C. Lin, S. Hosseinalipour, S. S. Azam, C. G. Brinton, and N. Michelusi.  Semi-decentralized federated learning with cooperative D2D local model aggregations.  _IEEE Journal on Selected Areas in Communications_ , 39(12):3851–3869, 2021.
  * Liu et al. (2022a) Y. Liu, Y. Kang, T. Zou, Y. Pu, Y. He, X. Ye, Y. Ouyang, Y.-Q. Zhang, and Q. Yang.  Vertical federated learning.  _arXiv preprint arXiv:2211.12814_ , 2022a.
  * Liu et al. (2022b) Y. Liu, X. Zhang, Y. Kang, L. Li, T. Chen, M. Hong, and Q. Yang.  FedBCD: A communication-efficient collaborative learning framework for distributed features.  _IEEE Transactions on Signal Processing_ , 70:4277–4290, 2022b.
  * Mao et al. (2020) X. Mao, K. Yuan, Y. Hu, Y. Gu, A. H. Sayed, and W. Yin.  Walkman: A communication-efficient random-walk algorithm for decentralized optimization.  _IEEE Transactions on Signal Processing_ , 68:2513–2528, 2020.
  * McMahan et al. (2017) B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics_ , pages 1273–1282. PMLR, 2017.
  * Nedic and Bertsekas (2001) A. Nedic and D. P. Bertsekas.  Incremental subgradient methods for nondifferentiable optimization.  _SIAM Journal on Optimization_ , 12(1):109–138, 2001.
  * Nedic and Ozdaglar (2009) A. Nedic and A. Ozdaglar.  Distributed subgradient methods for multi-agent optimization.  _IEEE Transactions on Automatic Control_ , 54(1):48–61, 2009.
  * Nedic et al. (2018) A. Nedic, A. Olshevsky, and M. G. Rabbat.  Network topology and communication-computation tradeoffs in decentralized optimization.  _Proceedings of the IEEE_ , 106(5):953–976, 2018.
  * Nesterov (2012) Y. Nesterov.  Efficiency of coordinate descent methods on huge-scale optimization problems.  _SIAM Journal on Optimization_ , 22(2):341–362, 2012.
  * Paulin (2015) D. Paulin.  Concentration inequalities for Markov chains by Marton couplings and spectral methods.  2015\.
  * Qu and Li (2018) G. Qu and N. Li.  Harnessing smoothness to accelerate distributed optimization.  _IEEE Transactions on Control of Network Systems_ , 5(3):1245–1260, 2018.
  * Ram et al. (2009) S. S. Ram, A. Nedić, and V. V. Veeravalli.  Incremental stochastic subgradient algorithms for convex optimization.  _SIAM Journal on Optimization_ , 20(2):691–717, 2009.
  * Richtárik and Takáč (2012) P. Richtárik and M. Takáč.  Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function.  _Mathematical Programming_ , 144(1-2):1–38, 2012\.
  * Robbins and Siegmund (1971) H. Robbins and D. Siegmund.  A convergence theorem for non negative almost supermartingales and some applications.  In J. S. Rustagi, editor, _Optimizing Methods in Statistics_ , pages 233–257. Academic Press, 1971.
  * Smith et al. (2018) V. Smith, S. Forte, C. Ma, M. Takac, M. I. Jordan, and M. Jaggi.  Cocoa: A general framework for communication-efficient distributed optimization, 2018.
  * Su et al. (2015) H. Su, S. Maji, E. Kalogerakis, and E. Learned-Miller.  Multi-view convolutional neural networks for 3D shape recognition.  In _Proceedings of the IEEE international conference on computer vision_ , 2015.
  * Sun et al. (2019) T. Sun, Y. Sun, Y. Xu, and W. Yin.  Markov chain block coordinate descent.  _Computational Optimization and Applications_ , 75(1):35–61, 2019.
  * Valdeira et al. (2022) P. Valdeira, Y. Chi, C. Soares, and J. Xavier.  A multi-token coordinate descent method for vertical federated learning.  In _NeurIPS Workshop on Federated Learning: Recent Advances and New Challenges_ , 2022.
  * Wei et al. (2022) K. Wei, J. Li, C. Ma, M. Ding, S. Wei, F. Wu, G. Chen, and T. Ranbaduge.  Vertical federated learning: Challenges, methodologies and experiments.  _arXiv preprint arXiv:2202.04309_ , 2022.
  * Wright (2015) S. J. Wright.  Coordinate descent algorithms.  _Mathematical Programming_ , 151(1):3–34, 2015\.
  * Wu et al. (2015) Z. Wu, S. Song, A. Khosla, F. Yu, L. Zhang, X. Tang, and J. Xiao.  3D shapenets: A deep representation for volumetric shapes.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015.
  * Ye et al. (2020) Y. Ye, H. Chen, Z. Ma, and M. Xiao.  Decentralized consensus optimization based on parallel random walk.  _IEEE Communications Letters_ , 24(2):391–395, 2020.
  * Yemini et al. (2022) M. Yemini, R. Saha, E. Ozfatura, D. Gunduz, and A. J. Goldsmith.  Semi-decentralized federated learning with collaborative relaying.  In _2022 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2022.
  * Zhang et al. (2021a) X. Zhang, Y. Liu, J. Liu, A. Argyriou, and Y. Han.  D2D-assisted federated learning in mobile edge computing networks.  In _2021 IEEE Wireless Communications and Networking Conference (WCNC)_ , 2021a.
  * Zhang et al. (2021b) X. Zhang, W. Yin, M. Hong, and T. Chen.  Hybrid federated learning: Algorithms and implementation, 2021b.
  * Zhao et al. (2022) H. Zhao, B. Li, Z. Li, P. Richtárik, and Y. Chi.  BEER: Fast $O(1/T)$ Rate for Decentralized Nonconvex Optimization with Communication Compression.  _arXiv:2201.13320_ , 2022.

##  Appendix A Preliminaries

If a function is $L$-smooth (A1), then the following quadratic upper bound
holds:

$f(\bm{y})\leq f(\bm{x})+\nabla
f(\bm{x})^{\top}(\bm{y}-\bm{x})+\frac{L}{2}\lVert\bm{x}-\bm{y}\rVert^{2},\quad\forall\;\bm{x},\bm{y}\in\mathbb{R}^{d}.$
(5)

######  Definition 1 (Markov chain).

A sequence of random variables $(Z^{t})_{t\geq 0}$ is a finite-state space
$\mathcal{K}$ Markov chain if, for all $\,i,j\in\mathcal{K}$,

$\mathbb{P}(Z^{t+1}=j\mid
Z^{0},\dots,Z^{t-1},Z^{t}=i)=\mathbb{P}(Z^{t+1}=j\mid
Z^{t}=i)\eqqcolon(\bm{P}(t))_{ij},$

where $\bm{P}(t)\in\mathbb{R}^{|\mathcal{K}|\times|\mathcal{K}|}$ is called
the transition matrix. A Markov chain is said to be:

  * •

time-homogeneous if the transition matrix is constant, that is,
$\bm{P}(t)=\bm{P}$ for all $t$;

  * •

irreducible if, starting from any state, all states can be reached eventually,
that is, there exists a $t$ such that $(\bm{P}^{t})_{ij}>0$ for all
$\,i,j\in\mathcal{K}$;

  * •

aperiodic if $\text{gcd}(\\{t\geq 1\colon(\bm{P}^{t})_{ii}>0\\})=1$ for all
states $i\in\mathcal{K}$, that is, if all states have period 1, where the
period of a state $i$ is defined as the greatest common divisor of the set of
times when it is possible for the Markov chain to return to starting position
$i$;

  * •

reversible if $\pi_{i}\bm{P}_{ij}=\pi_{j}\bm{P}_{ji}$ for all
$i,j\in\mathcal{K}$, where $\bm{\pi}=(\pi_{1},\dots,\pi_{|\mathcal{K}|})$ is
the stationary distribution, which is defined as the distribution satisfying
$\bm{\pi}^{\top}=\bm{\pi}^{\top}\bm{P}$.

A Markov chain is a lazy random walk (henceforth referred to simply as a
random walk) if its states correspond to nodes of a graph and

$\bm{P}_{ij}=\begin{cases}\frac{1}{d(i)+1}\quad&\text{if
}j\in\bar{\mathcal{N}}_{i},\\\ 0&\text{otherwise},\end{cases}$

where $d(i)$ denote the degree of node $i$. A random walk on a static,
connected, and undirected graph specifies a finite-state, time-homogeneous,
irreducible, and aperiodic Markov chain. If a Markov chain is irreducible and
aperiodic, every row of $\bm{P}^{t}$ will converge to a unique stationary
distribution $\bm{\pi}$, as shown in (Levin and Peres, 2017). We define
$\pi_{\min}\coloneqq\min_{i}\pi_{i}$ and denote by $d_{\max}$ and $d_{\min}$
the maximum and minimum degrees of any node $k\in\mathcal{K}$, respectively.

######  Definition 2 (Mixing time).

We say $\tau_{\epsilon}$ is the $\epsilon$-mixing time of a Markov chain if

$\tau_{\epsilon}\coloneqq\min\left\\{t\colon\sup_{i\in\mathcal{K}}\,d_{TV}\left(\left(\bm{P}^{t}\right)_{i:},\bm{\pi}\right)\leq\epsilon\right\\},$

where $d_{TV}$ is the total variation distance. For countable sets, our case,
$d_{TV}(\bm{x},\bm{y})=\lVert\bm{x}-\bm{y}\rVert_{1}/2$.

We use the following result in our analysis.

######  Remark (Grönwall-Bellman lemma).

Let $a,b\geq 0$ be constants, if sequence $(u_{n})_{n=0}^{N}$ satisfies

$u_{n}\leq a+b\sum_{i=0}^{n-1}u_{i},\quad 0\leq n\leq
N,\qquad\text{then}\qquad u_{n}\leq a(1+b)^{n},\quad 0\leq n\leq N.$ (6)

###### Proof.

The $n=0$ base case is trivial. For the induction step, we assume the result
we want to show holds for $0\leq n\leq k-1$ and notice that:

$u_{k}\leq a+b\sum_{i=0}^{k-1}u_{i}\leq
a+b\sum_{i=0}^{k-1}a(1+b)^{i}=a\left(1+b\sum_{i=0}^{k-1}(1+b)^{i}\right)\stackrel{{\scriptstyle(a)}}{{\leq}}a(1+b)^{k},$

where in $(a)$ we use the finite sum of a geometric series, which is equal to
the expression that follows for the case $b>0$ and, to handle $b=0$, we can
use Bernoulli’s inequality. ∎

Consider the set of vectors $\\{\bm{a}_{1},\dots,\bm{a}_{n}\\}$, using the
Cauchy–Schwarz inequality we have that:

$\left\lVert\sum_{i=1}^{n}\bm{a}_{i}\right\rVert^{2}\leq
n\sum_{i=1}^{n}\left\lVert\bm{a}_{i}\right\rVert^{2}.$ (7)

##  Appendix B Token roaming lemmas

Lemmas 1, 2, and 3 concern token roaming. Yet, for clarity, we abstract away
the tokens and communications, studying a setup-agnostic Markov chain
coordinate descent instead, summarized in Algorithm 3. We consider
$\psi\colon\mathbb{R}^{d^{\prime}}\to\mathbb{R}$, a partitioning of
$[d^{\prime}]$ with blocks $k\in\mathcal{K}$, and let
$\bar{\nabla}_{k}\psi\left(\bm{v}\right)\in\mathbb{R}^{d^{\prime}}$ denote a
vector whose block $k$ corresponds to $\nabla_{k}\psi\left(\bm{v}\right)$ and
all other entries are zeros. Note that $k^{i}$ is fixed for $i=0$ and a random
variable for $i\in[S]$. We further define the surrogate offset as
$\bm{\delta}^{i,j}\coloneqq\bar{\nabla}_{k^{i}}\psi\left(\bm{v}^{i,j}\right)-\nabla\psi\left(\bm{v}^{0,0}\right)$.
As mentioned in the paper, token roaming is closely related to (Sun et al.,
2019), yet our analysis differs significantly, since the results in (Sun et
al., 2019) require $S\to\infty$ and our end goal is to study the convergence
of MTCD with respect to syncing steps, for a finite number of hops $S$.

Input : initial point $\bm{v}^{0,0}$, initial block $k^{0}$, step-size $\eta$,
block samples $S$, updates per block $Q$

1 $\bm{v}^{S,Q}\leftarrow$ $\mathcal{M}$(_$\bm{v}^{0,0},k^{0},\eta,S,Q,\psi$_)

2 Function  _$\mathcal{M}$(_$\bm{v},k,\eta,S,Q,\psi$_)_:

3 $\bm{v}^{0,0},k^{0}\leftarrow\bm{v},k$

4 for  _$s=0,\dots,S-1$_ do

5 for  _$q=0,\dots,Q-1$_ do

6
$\bm{v}^{s,q+1}\leftarrow\bm{v}^{s,q}-\eta\bar{\nabla}_{k^{s}}\psi\left(\bm{v}^{s,q}\right)$

7

8 $\bm{v}^{s+1,0}\leftarrow\bm{v}^{s,Q}$

9 $k^{s+1}\sim\bm{P}_{k^{s}:}$

10

11 return $\bm{v}^{S,Q}$

12

Algorithm 3 Markov chain coordinate descent (token roaming)

######  Lemma 1.

If $\left(\bm{v}^{i,j}\right)$ is a sequence generated by Algorithm 3, $\psi$
is $L$-smooth, and $\eta\in\big{(}0,\frac{1}{LSQ}\big{]}$, then:

$\left\lVert\bm{\delta}^{s,q}_{k^{s}}\right\rVert\leq
C_{1}\left\lVert\nabla\psi\left(\bm{v}^{0,0}\right)\right\rVert,\qquad
C_{1}\coloneqq\eta eLSQ.$ (8)

###### Proof.

Let $(\triangle)$ denote the triangle inequality and $\sum_{i,j}$ denote
$\sum_{i=0}^{s}\sum_{j=0}^{\tilde{q}_{s}(i)}$, where $\tilde{q}_{s}(i)$ is
$q-1$ if $i=s$ and $Q-1$ otherwise, we first upper bound
$\left\lVert\bm{\delta}^{s,q}_{k^{s}}\right\rVert$ with the sum of the norm of
the blocks of the gradient used to update $\bm{v}^{0,0}$ to $\bm{v}^{s,q}$:

$\displaystyle\left\lVert\bm{\delta}^{s,q}_{k^{s}}\right\rVert$
$\displaystyle=\left\lVert\nabla_{k^{s}}\psi\left(\bm{v}^{s,q}\right)-\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right)\right\rVert$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:lsmooth}}}{{\leq}}L\left\lVert\bm{v}^{s,q}-\bm{v}^{0,0}\right\rVert$
$\displaystyle=\eta
L\left\lVert\sum_{i,j}\bar{\nabla}_{k^{i}}\psi\left(\bm{v}^{i,j}\right)\right\rVert$
$\displaystyle\stackrel{{\scriptstyle(\triangle)}}{{\leq}}\eta
L\sum_{i,j}\left\lVert\bar{\nabla}_{k^{i}}\psi\left(\bm{v}^{i,j}\right)\right\rVert$
$\displaystyle=\eta
L\sum_{i,j}\left\lVert\nabla_{k^{i}}\psi\left(\bm{v}^{i,j}\right)\right\rVert.$

We now use the definition of $\bm{\delta}^{i,j}$ and the triangle inequality
in order to be able to exploit the fact that
$\lVert\nabla\psi(\bm{v}^{0,0})\rVert$ is fixed, allowing us to resort to the
Grönwall-Bellman lemma:

$\displaystyle\left\lVert\bm{\delta}^{s,q}_{k^{s}}\right\rVert$
$\displaystyle\stackrel{{\scriptstyle(\triangle)}}{{\leq}}\eta
L\sum_{i,j}\left(\left\lVert\nabla_{k^{i}}\psi\left(\bm{v}^{0,0}\right)\right\rVert+\left\lVert\bm{\delta}^{i,j}_{k^{i}}\right\rVert\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\eta
L(Qs+q)\left\lVert\nabla\psi\left(\bm{v}^{0,0}\right)\right\rVert+\eta
L\sum_{i,j}\left\lVert\bm{\delta}^{i,j}_{k^{i}}\right\rVert$
$\displaystyle\leq\eta
LSQ\left\lVert\nabla\psi\left(\bm{v}^{0,0}\right)\right\rVert+\eta
L\sum_{i,j}\left\lVert\bm{\delta}^{i,j}_{k^{i}}\right\rVert$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:gb_lemma}}}{{\leq}}\eta
LSQ\left\lVert\nabla\psi\left(\bm{v}^{0,0}\right)\right\rVert\left(1+\eta
L\right)^{Qs+q}$ $\displaystyle\leq\eta
LSQ\left\lVert\nabla\psi\left(\bm{v}^{0,0}\right)\right\rVert\left(1+\eta
L\right)^{SQ}$ $\displaystyle\leq\eta
eLSQ\left\lVert\nabla\psi\left(\bm{v}^{0,0}\right)\right\rVert,$

where in $(a)$ we use the fact that
$\lVert\nabla_{k^{i}}\psi(\bm{v}^{0,0})\rVert\leq\lVert\nabla\psi(\bm{v}^{0,0})\rVert$
and in the last inequality we use our upper bound on the step-size
$\eta\leq\frac{1}{LSQ}$ and the fact that $(1+\frac{1}{u})^{u}<e$ for all
$u>0$, thus arriving at (8). ∎

######  Lemma 2.

If $\left(\bm{v}^{s,q}\right)$ is a sequence generated by Algorithm 3 and
$\mathbb{P}(k^{S}=k)>0$ for all $k$, then:

$\mathbb{E}\left[\sum^{S}_{s=0}\sum_{q=0}^{Q-1}\left\lVert\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}\right]\geq\rho
Q\left\lVert\nabla\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2},$ (9)

where the expectation is taken over $\\{k^{s}\\}^{S}_{s=1}$ and
$\mathbb{P}(k^{S}=k)\geq\rho>0$ for all $k$. We can obtain different lower
bounds on $\rho$ depending on the assumptions we make:

  * •

If $\bm{P}$ is a lazy random walk on a graph, then
$\rho\geq(1/(d_{\max}+1))^{S}$;

  * •

If the graph is static, connected, and undirected and
$S\geq\frac{3\log(2|\mathcal{E}|/(d_{\min}+1))}{2\lambda}$, where
$\lambda\coloneqq 1-\lambda_{2}\in(0,1)$, with $\lambda_{2}$ denoting the
second largest eigenvalue of $\bm{P}$ in absolute value, then
$\rho\geq\frac{d_{\min}+1}{4|\mathcal{E}|}$.

While $\mathbb{P}(k^{S}=k)>0$ is an assumption needed for Lemma 2, it brings
no loss of generality for the theorems where Lemma 2 is used, where this
property always holds. This will become clear when we prove the theorems.

###### Proof.

Let $\sum_{s,q}$ denote $\sum^{S}_{s=0}\sum_{q=0}^{Q-1}$, we have that

$\mathbb{E}\left[\sum_{s,q}\left\lVert\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}\right]=\sum_{s,q}\sum_{k\in\mathcal{K}}\mathbb{P}(k^{s}=k)\left\lVert\nabla_{k}\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}=\sum_{k\in\mathcal{K}}Q\sum_{s}\mathbb{P}(k^{s}=k)\left\lVert\nabla_{k}\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2},$

and, using the fact that
$\left\lVert\nabla_{k}\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}\geq 0$, we
get:

$\displaystyle\sum_{k\in\mathcal{K}}Q\sum_{s}\mathbb{P}(k^{s}=k)\left\lVert\nabla_{k}\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}\geq\sum_{k\in\mathcal{K}}Q\mathbb{P}(k^{S}=k)\left\lVert\nabla_{k}\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}.$

We now obtain two different lower bounds on $\mathbb{P}(k^{S}=k)$, for
different sets of assumptions:

  * •

If $\bm{P}$ is a lazy random walk on a graph, $\rho\geq(1/d_{\max}+1)^{S}$
follows directly from the assumption that $\mathbb{P}(k^{S}=k)>0$ and the
transition probabilities of the random walk:

$\mathbb{P}(k^{S})=\sum_{k^{1},\dots,k^{S-2}}\left[\prod_{i=0}^{S-2}\mathbb{P}(k^{i+1}\mid
k^{i})\right]\geq
0\implies\mathbb{P}(k^{S}=k)\geq\left(\frac{1}{d_{\max}+1}\right)^{S};$

  * •

To avoid an exponential dependency on $S$ we can further assume that the graph
is static, connected, and undirected,777Similar bounds can be found for more
general graphs, but we focus on this case for simplicity. and that
$S\geq\tau$, where $\tau$ is the $\frac{\pi_{\min}}{2}$-mixing time. It
follows from the definition of mixing time (Definition 2) that
$\lvert\left(\bm{P}^{S}\right)_{ij}-\pi_{j}\rvert\leq\pi_{\min}$ for all $i,j$
and therefore $\left(\bm{P}^{S}\right)_{ij}\geq\frac{\pi_{\min}}{2}$. (If
$\left(\bm{P}^{S}\right)_{ij}<\frac{\pi_{\min}}{2}$, then
$\pi_{\min}-\left(\bm{P}^{S}\right)_{ij}>\frac{\pi_{\min}}{2}$, contradicting
the definition of $\frac{\pi_{\min}}{2}$-mixing time.) We can now easily
verify that, for a random walk,
$\bm{\pi}=\left(\frac{d(k)+1}{2|\mathcal{E}|}\right)_{k\in\mathcal{V}}$, and
thus:

$\left(\bm{P}^{S}\right)_{k^{0}k}\geq\frac{d_{\min}+1}{4|\mathcal{E}|}.$

We now want to upper bound $\tau$ with respect to properties of $\bm{P}$, to
know for what values of $S$ this bound holds. For a reversible, aperiodic, and
irreducible Markov chain, our case, we have (Paulin, 2015, Proposition 3.3):

$\tau\leq\frac{3\log(1/\pi_{\min})}{2\lambda}=\frac{3\log(2|\mathcal{E}|/(d_{\min}+1))}{2\lambda}.$

We now use one of these bounds on $\rho$ and the fact that
$\sum_{k\in\mathcal{K}}\left\lVert\nabla_{k}\psi\left(\bm{v}\right)\right\rVert^{2}=\left\lVert\nabla\psi\left(\bm{v}\right)\right\rVert^{2}$
to arrive at (9). ∎

Note that, in the special case of a random walk on complete graph we have
$\mathbb{P}(k^{s}=k)=1/\lvert\mathcal{K}\rvert$ for all $k$, allowing us to
avoid the inequalities above altogether and get:

$\mathbb{E}\left[\sum^{S}_{s=0}\sum_{q=0}^{Q-1}\left\lVert\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}\right]=\frac{SQ}{\lvert\mathcal{K}\rvert}\left\lVert\nabla\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}.$

######  Lemma 3.

Assume $\psi$ is $L$-smooth and let $\left(\bm{v}^{i,j}\right)$ be a sequence
generated by Algorithm 3 with $\eta\in\big{(}0,\frac{1}{(L+1)SQ}\big{]}$. If

$\Psi\coloneqq\Psi_{1}+\Psi_{2},$

where

$\Psi_{1}\coloneqq\left\langle\nabla\psi\left(\bm{v}^{0,0}\right),\bm{v}^{S,Q}-\bm{v}^{0,0}\right\rangle$

and

$\Psi_{2}\coloneqq\frac{L+1}{2}\left\lVert\bm{v}^{S,Q}-\bm{v}^{0,0}\right\rVert^{2},$

then

$\Psi\leq\eta
SQC_{1}(1+\eta(L+1)SQC_{1})\left\lVert\nabla\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}+\eta(\eta(L+1)SQ-1)\sum^{S-1}_{s=0}\sum_{q=0}^{Q-1}\left\lVert\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}.$
(10)

###### Proof.

Let $\sum_{s,q}$ denote $\sum_{s=0}^{S}\sum_{q=0}^{Q-1}$, we first upper bound
$\Psi_{1}$ and then $\Psi_{2}$.

#### Bounding $\Psi_{1}$.

We first use the Algorithm 3 update relating $\bm{v}^{S,Q}$ with
$\bm{v}^{0,0}$ and the definition of $\bm{\delta}^{s,q}$:

$\displaystyle\Psi_{1}=\left\langle\nabla\psi\left(\bm{v}^{0,0}\right),\bm{v}^{S,Q}-\bm{v}^{0,0}\right\rangle$
$\displaystyle=-\eta\left\langle\nabla\psi\left(\bm{v}^{0,0}\right),\sum_{s,q}\bar{\nabla}_{k^{s}}\psi\left(\bm{v}^{s,q}\right)\right\rangle$
$\displaystyle=-\eta\sum_{s,q}\left\langle\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right),\nabla_{k^{s}}\psi\left(\bm{v}^{s,q}\right)\right\rangle$
$\displaystyle=-\eta\sum_{s,q}\left\langle\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right),\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right)+\bm{\delta}^{s,q}_{k^{s}}\right\rangle$
$\displaystyle=-\eta\sum_{s,q}\left\lVert\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}-\eta\sum_{s,q}\left\langle\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right),\bm{\delta}^{s,q}_{k^{s}}\right\rangle.$

Now, using first the Cauchy–Schwarz inequality and then Lemma 1, we have

$\displaystyle\Psi_{1}$
$\displaystyle\leq-\eta\sum_{s,q}\left\lVert\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}+\eta\sum_{s,q}\left\lVert\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right)\right\rVert\left\lVert\bm{\delta}^{s,q}_{k^{s}}\right\rVert$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:surrogate_offset_ub}}}{{\leq}}-\eta\sum_{s,q}\left\lVert\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}+\eta
C_{1}\sum_{s,q}\left\lVert\nabla\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}$
$\displaystyle=-\eta\sum_{s,q}\left\lVert\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}+\eta
SQC_{1}\left\lVert\nabla\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}.$ (11)

#### Bounding $\Psi_{2}$.

Similarly to bounding $\Psi_{1}$, we first use the update relating
$\bm{v}^{S-1,Q-1}$ with $\bm{v}^{0,0}$ and the definition of
$\bm{\delta}^{i,j}$

$\displaystyle\Psi_{2}=\frac{L+1}{2}\left\lVert\bm{v}^{S,Q}-\bm{v}^{0,0}\right\rVert^{2}$
$\displaystyle=\frac{\eta^{2}(L+1)}{2}\left\lVert\sum_{s,q}\bar{\nabla}_{k^{s}}\psi\left(\bm{v}^{s,q}\right)\right\rVert^{2}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:cs_sqd_sum}}}{{\leq}}\frac{\eta^{2}(L+1)SQ}{2}\sum_{s,q}\left\lVert\bar{\nabla}_{k^{s}}\psi\left(\bm{v}^{s,q}\right)\right\rVert^{2}$
$\displaystyle=\frac{\eta^{2}(L+1)SQ}{2}\sum_{s,q}\left\lVert\nabla_{k^{s}}\psi\left(\bm{v}^{s,q}\right)\right\rVert^{2}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:cs_sqd_sum}}}{{\leq}}\eta^{2}(L+1)SQ\sum_{s,q}\left(\left\lVert\bm{\delta}^{s,q}_{k^{s}}\right\rVert^{2}+\left\lVert\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}\right),$

and then use Lemma 1, to obtain

$\displaystyle\Psi_{2}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:surrogate_offset_ub}}}{{\leq}}\eta^{2}(L+1)SQ\sum_{s,q}\left(C_{1}^{2}\left\lVert\nabla\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}+\left\lVert\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}\right)$
$\displaystyle=\eta^{2}(L+1)S^{2}Q^{2}C_{1}^{2}\left\lVert\nabla\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}+\eta^{2}(L+1)SQ\sum_{s,q}\left\lVert\nabla_{k^{s}}\psi\left(\bm{v}^{0,0}\right)\right\rVert^{2}.$
(12)

Finally, we get (10) by summing (B) and (B). ∎

##  Appendix C Proof of Theorem 1

For the sake of clarity and simplicity, we now consider a setup-agnostic
stochastic disjoint parallel Markov chain coordinate descent, presented in
Algorithm 4, which abstracts away the tokens and communications of MTCD while
remaining mathematically equivalent. Map $\mathcal{M}$ is as defined in
Algorithm 3.

In this setup, only block $\bm{\theta}_{\mathcal{C}_{\gamma}}(\gamma)$ of
$\bm{\theta}(\gamma)$ is updated during the roaming step. Since
$\mathcal{C}_{1},\dots,\mathcal{C}_{\Gamma}$ are disjoint, no coordinate is
updated simultaneously for different model estimates. This allows us to use
the simpler notation
$\bm{\theta}=(\bm{\theta}_{\mathcal{C}_{1}}(1),\dots,\bm{\theta}_{\mathcal{C}_{\Gamma}}(\Gamma))$,
focusing on the blocks of $\bm{\theta}(1),\dots,\bm{\theta}(\Gamma)$ which are
updated during the roaming step and seeing their concatenation as a single
model estimate.

We define $\mathcal{V}^{t}_{c}$ as the sub-block of coordinates in block
$\mathcal{C}_{c}$ with a nonzero probability of being updated during roaming
step $t$,
$\mathcal{V}^{t}_{c}\coloneqq\\{k\in\mathcal{C}_{c}\colon\sum^{S-1}_{s=0}\mathbb{P}(k^{t,s}_{c}=k\mid
k^{t,0}_{c})>0\\}$. Further, we denote by $f^{t}_{c}$ as the marginal function
of $f$ which keeps block $\mathcal{V}^{t}_{c}$ of $\bm{\theta}$ as a variable
and is parameterized by the remaining coordinates of $\bm{\theta}$ after the
last sync,
$f^{t}_{c}(\bm{\theta}^{t,s,q}_{\mathcal{V}^{t}_{c}})=f(\bm{\theta}^{t,s,q}_{\mathcal{V}^{t}_{c}};\bm{\theta}^{t}_{-\mathcal{V}^{t}_{c}})$.
Similarly, $\mathcal{V}^{t}\coloneqq\bigcup_{c}\mathcal{V}^{t}_{c}$ and
$f^{t}(\bm{\theta}^{t,s,q}_{\mathcal{V}^{t}})=f(\bm{\theta}^{t,s,q}_{\mathcal{V}^{t}};\bm{\theta}^{t}_{-\mathcal{V}^{t}})$.

Input : initial point $\bm{\theta}^{0}$, step-size $\eta$, block samples $S$,
updates per block $Q$

1 for  _$t=0,\dots,T-1$_ do

2 for  _$c=0,\dots,C$ _in parallel__ do

3 Samples batch indices $\mathcal{B}^{t}\subseteq[N]$

4 $k^{t,0}_{c}\sim P_{c}$

5
$\bm{\theta}^{t,S,Q}_{\mathcal{C}_{c}}\leftarrow\mathcal{M}(\bm{\theta}^{t}_{\mathcal{C}_{c}},k^{t,0}_{c},\eta,S,Q,f^{t}_{c}(\cdot;\mathcal{B}^{t}))$

6

7
$\bm{\theta}^{t+1}\leftarrow(\bm{\theta}^{t,S,Q}_{\mathcal{C}_{0}},\dots,\bm{\theta}^{t,S,Q}_{\mathcal{C}_{C}})$

8

Algorithm 4 Stochastic disjoint parallel Markov chain coordinate descent

In the proof that follows, we let $\sum_{s}$, $\sum_{q}$, $\sum_{c}$ and
$\sum_{k}$ denote $\sum^{S}_{s=0}$, $\sum_{q=0}^{Q}$, $\sum_{c=0}^{C}$, and
$\sum_{k=0}^{K}$, respectively.

###### Proof.

It follows from $L$-smoothness, in particular from (5), that

$\displaystyle f(\bm{\theta}^{t+1})-f(\bm{\theta}^{t})$
$\displaystyle\leq\langle\nabla
f(\bm{\theta}^{t}),\bm{\theta}^{t+1}-\bm{\theta}^{t}\rangle+\frac{L}{2}\lVert\bm{\theta}^{t+1}-\bm{\theta}^{t}\rVert^{2}$
$\displaystyle=\sum_{c}\left[\left\langle\nabla
f^{t}_{c}\left(\bm{\theta}^{t}_{\mathcal{V}^{t}_{c}}\right),\bm{\theta}^{t+1}_{\mathcal{V}^{t}_{c}}-\bm{\theta}^{t}_{\mathcal{V}^{t}_{c}}\right\rangle+\frac{L}{2}\left\lVert\bm{\theta}^{t+1}_{\mathcal{V}^{t}_{c}}-\bm{\theta}^{t}_{\mathcal{V}^{t}_{c}}\right\rVert^{2}\right].$

Now, let $\bm{g}_{c}^{t}\coloneqq\nabla
f^{t}_{c}\left(\bm{\theta}^{t}_{\mathcal{V}^{t}_{c}};\bm{X}\right)=\nabla
f^{t}_{c}\left(\bm{\theta}^{t}_{\mathcal{V}^{t}_{c}}\right)$ and
$\tilde{\bm{g}}_{c}^{t}\coloneqq\nabla
f^{t}_{c}\left(\bm{\theta}^{t}_{\mathcal{V}^{t}_{c}};\mathcal{B}_{t}\right)$,
we have

$\displaystyle f(\bm{\theta}^{t+1})-f(\bm{\theta}^{t})$
$\displaystyle\leq\sum_{c}\left[\left\langle\tilde{\bm{g}}_{c}^{t},\bm{\theta}^{t+1}_{\mathcal{V}^{t}_{c}}-\bm{\theta}^{t}_{\mathcal{V}^{t}_{c}}\right\rangle+\left\langle\bm{g}_{c}^{t}-\tilde{\bm{g}}_{c}^{t},\bm{\theta}^{t+1}_{\mathcal{V}^{t}_{c}}-\bm{\theta}^{t}_{\mathcal{V}^{t}_{c}}\right\rangle+\frac{L}{2}\left\lVert\bm{\theta}^{t+1}_{\mathcal{V}^{t}_{c}}-\bm{\theta}^{t}_{\mathcal{V}^{t}_{c}}\right\rVert^{2}\right]$
$\displaystyle\leq\sum_{c}\left[\left\langle\tilde{\bm{g}}_{c}^{t},\bm{\theta}^{t+1}_{\mathcal{V}^{t}_{c}}-\bm{\theta}^{t}_{\mathcal{V}^{t}_{c}}\right\rangle+\frac{L+1}{2}\left\lVert\bm{\theta}^{t+1}_{\mathcal{V}^{t}_{c}}-\bm{\theta}^{t}_{\mathcal{V}^{t}_{c}}\right\rVert^{2}+\frac{1}{2}\lVert\bm{g}_{c}^{t}-\tilde{\bm{g}}_{c}^{t}\rVert^{2}\right],$

using the fact that $\langle a,b\rangle\leq\frac{1}{2}\lVert
a\rVert^{2}+\frac{1}{2}\lVert b\rVert^{2}$ on the term
$\left\langle\bm{g}_{c}^{t}-\tilde{\bm{g}}_{c}^{t},\bm{\theta}^{t+1}_{\mathcal{V}^{t}_{c}}-\bm{\theta}^{t}_{\mathcal{V}^{t}_{c}}\right\rangle$.
We now define and assume $\zeta\coloneqq\eta(L+1)SQ<1$ and use Lemma 3 to
bound the first two terms, with $\psi$ as $f^{t}_{c}(\cdot;\mathcal{B}_{t})$:

$f(\bm{\theta}^{t+1})-f(\bm{\theta}^{t})\leq\sum_{c}\left[\eta SQC_{1}(1+\zeta
C_{1})\left\lVert\tilde{\bm{g}}^{t}_{c}\right\rVert^{2}+\eta(\zeta-1)\sum_{s,q}\left\lVert\tilde{\bm{g}}_{ck_{c}^{t,s}}^{t}\right\rVert^{2}+\frac{1}{2}\lVert\bm{g}_{c}^{t}-\tilde{\bm{g}}_{c}^{t}\rVert^{2}\right],$

where $C_{1}=\eta eLSQ$. Let $\sigma^{t,s}$ denote the sigma algebra
$\sigma(\bm{k}^{0,0},\dots,\bm{k}^{0,S-1},\dots,\bm{k}^{t,0},\dots,\bm{k}^{t,s-1})$
and $\mathbb{E}^{\sigma}$ be a shorthand for the conditional expectation
$\mathbb{E}[\cdot\mid\sigma]$. We take the conditional expectation
$\mathbb{E}^{\sigma^{t,1}}$ on both sides of the inequality above and, since
$\zeta\leq 1$, it follows from Lemma 2 that

$\displaystyle\mathbb{E}^{\sigma^{t,1}}\left[f(\bm{\theta}^{t+1})\right]-f(\bm{\theta}^{t})$
$\displaystyle\leq-\underbrace{\eta Q(\rho(1-\zeta)-SC_{1}(1+\zeta
C_{1}))}_{\eqqcolon
C_{2}}\sum_{c}\left\lVert\tilde{\bm{g}}^{t}_{c}\right\rVert^{2}+\frac{1}{2}\sum_{c}\lVert\bm{g}_{c}^{t}-\tilde{\bm{g}}_{c}^{t}\rVert^{2}$
$\displaystyle=-C_{2}\left\lVert\tilde{\bm{g}}^{t}\right\rVert^{2}+\frac{1}{2}\lVert\bm{g}^{t}-\tilde{\bm{g}}^{t}\rVert^{2},$

where $\bm{g}^{t}\coloneqq\nabla
f^{t}\left(\bm{\theta}^{t}_{\mathcal{V}^{t}}\right)=\nabla
f^{t}\left(\bm{\theta}^{t}_{\mathcal{V}^{t}};\bm{X}\right)$ and
$\tilde{\bm{g}}^{t}\coloneqq\nabla
f^{t}\left(\bm{\theta}^{t}_{\mathcal{V}^{t}};\mathcal{B}_{t}\right)$. Now,
taking $\mathbb{E}^{\sigma^{t,0}}$ on both sides, we have

$\displaystyle\mathbb{E}^{\sigma^{t,0}}\left[f(\bm{\theta}^{t+1})\right]-f(\bm{\theta}^{t})$
$\displaystyle\leq\mathbb{E}^{\sigma^{t,0}}\left[\sum_{k}\mathbb{I}\\{k\in\mathcal{V}^{t}\\}\left(-C_{2}\left\lVert\nabla_{k}f\left(\bm{\theta}^{t};\mathcal{B}_{t}\right)\right\rVert^{2}+\frac{1}{2}\left\lVert\nabla_{k}f\left(\bm{\theta}^{t};\bm{X}\right)-\nabla_{k}f\left(\bm{\theta}^{t};\mathcal{B}_{t}\right)\right\rVert^{2}\right)\right]$
$\displaystyle=-C_{2}\sum_{k}\mathbb{P}(k\in\mathcal{V}^{t})\left\lVert\nabla_{k}f\left(\bm{\theta}^{t};\mathcal{B}_{t}\right)\right\rVert^{2}+\frac{1}{2}\sum_{k}\mathbb{P}(k\in\mathcal{V}^{t})\left\lVert\nabla_{k}f\left(\bm{\theta}^{t};\bm{X}\right)-\nabla_{k}f\left(\bm{\theta}^{t};\mathcal{B}_{t}\right)\right\rVert^{2}$
$\displaystyle\leq-pC_{2}\left\lVert\nabla
f\left(\bm{\theta}^{t};\mathcal{B}_{t}\right)\right\rVert^{2}+\frac{1}{2}\left\lVert\nabla
f\left(\bm{\theta}^{t};\bm{X}\right)-\nabla
f\left(\bm{\theta}^{t};\mathcal{B}_{t}\right)\right\rVert^{2},$

where in the last inequality we use the fact that, for $k$ in cluster $c(k)$,
$\mathbb{P}(k\in\mathcal{V}^{t})\geq\mathbb{P}(k^{t,0}_{c(k)}=k)\geq p$ to
bound the first term and $\mathbb{P}(k\in\mathcal{V}^{t})\leq 1$ to bound the
second term. To obtain a simpler, more interpretable constant, we bound
$C_{2}$. Since $\zeta>C_{1}=\eta eLSQ$, and using the fact that
$\zeta\in(0,1)\implies\zeta^{3}<\zeta$, we have

$C_{2}\geq\eta Q\bigl{(}\rho(1-\zeta)-Se\zeta(1+e\zeta^{2})\bigr{)}=\eta
Q\bigl{(}\rho-(\rho+Se)\zeta-Se^{2}\zeta^{3}\bigr{)}\geq\eta
Q\bigl{(}\rho-(\rho+Se(1+e))\zeta\bigr{)}\eqqcolon C_{3}.$

For $\eta\in\left(0,\frac{\rho}{(L+1)SQ(\rho+Se(1+e))}\right)$, which
satisfies the bounds imposed on $\eta$ by the lemmas, $C_{3}>0$. We now take
$\mathbb{E}^{\mathcal{B}_{t}}\coloneqq\mathbb{E}_{\mathcal{B}_{t}}[\cdot\mid\mathcal{B}_{0},\dots,\mathcal{B}_{t-1}]$
and lower bound $C_{2}$ with $C_{3}$:

$\displaystyle\mathbb{E}^{\mathcal{B}_{t}}\mathbb{E}^{\sigma^{t,0}}\left[f(\bm{\theta}^{t+1})\right]-f(\bm{\theta}^{t})$
$\displaystyle\leq-pC_{3}\mathbb{E}^{\mathcal{B}_{t}}\left\lVert\nabla
f\left(\bm{\theta}^{t};\mathcal{B}_{t}\right)\right\rVert^{2}+\frac{1}{2}\mathbb{E}^{\mathcal{B}_{t}}\left\lVert\nabla
f\left(\bm{\theta}^{t};\bm{X}\right)-\nabla
f\left(\bm{\theta}^{t};\mathcal{B}_{t}\right)\right\rVert^{2}$
$\displaystyle\leq-pC_{3}\left\lVert\nabla
f\left(\bm{\theta}^{t};\bm{X}\right)\right\rVert^{2}+\left(\frac{1}{2}-pC_{3}\right)\mathbb{E}^{\mathcal{B}_{t}}\left\lVert\nabla
f\left(\bm{\theta}^{t};\bm{X}\right)-\nabla
f\left(\bm{\theta}^{t};\mathcal{B}_{t}\right)\right\rVert^{2},$

where we used the fact that $\mathbb{E}\lVert
X\rVert^{2}=\lVert\mathbb{E}X\rVert^{2}+\mathbb{E}\lVert
X-\mathbb{E}X\rVert^{2}$ and (A2) on the first term. Now, noting that
$\frac{1}{2}-pC_{3}\geq 0$ always holds, it follows from the bounded variance
assumption (A3) that

$\mathbb{E}^{\mathcal{B}_{t}}\mathbb{E}^{\sigma^{t,0}}\left[f(\bm{\theta}^{t+1})\right]-f(\bm{\theta}^{t})\leq-
pC_{3}\left\lVert\nabla
f(\bm{\theta}^{t})\right\rVert^{2}+\left(\frac{1}{2}-pC_{3}\right)\frac{\sigma^{2}}{B}.$

We now take the expected value with respect to all $\\{{k}^{t,s}_{c}\\}$ and
$\\{\mathcal{B}_{t}\\}$ and rearrange the terms, we get that

$\mathbb{E}\left\lVert\nabla
f\left(\bm{\theta}^{t}\right)\right\rVert^{2}\leq\frac{1}{pC_{3}}\mathbb{E}\left[f\left(\bm{\theta}^{t}\right)-f\left(\bm{\theta}^{t+1}\right)\right]+\left(\frac{1}{2pC_{3}}-1\right)\frac{\sigma^{2}}{B}.$

Finally, we sum over $t\in\\{0,\dots,T-1\\}$, getting a telescoping sum, and
divide by $T$. Dropping the $-\sigma^{2}/B$ term, using the fact that
$f^{\star}\leq f(\bm{\theta})$ for all $\bm{\theta}$, and defining
$C_{4}\coloneqq\frac{1}{pC_{3}}$, we finally arrive at

$\mathbb{E}\left[\frac{1}{T}\sum_{t=0}^{T-1}\left\lVert\nabla
f\left(\bm{\theta}^{t}\right)\right\rVert^{2}\right]\leq\frac{C_{4}\Delta}{T}+\frac{C_{4}\sigma^{2}}{2B}.$

∎

##  Appendix D Proof of Theorem 2

For the sake of clarity and simplicity, we again consider a setup-agnostic
version of our method which abstracts away the tokens and communications of
MTCD while remaining mathematically equivalent. A stochastic parallel Markov
chain coordinate descent where we allow for overlapping blocks of coordinates
to be updated simultaneously is presented in Algorithm 5. Similarly to
Appendix C, map $\mathcal{M}$ is as defined in Algorithm 3 and we define
$\mathcal{V}^{t}_{\gamma}\coloneqq\\{k\in\mathcal{V}\colon\sum^{S-1}_{s=0}\mathbb{P}(k^{t,s}_{\gamma}=k\mid
k^{t,0}_{\gamma})>0\\}$,
$f^{t}_{\gamma}(\bm{\theta}^{t,s,q}_{\mathcal{V}^{t}_{\gamma}})=f(\bm{\theta}^{t,s,q}_{\mathcal{V}^{t}_{\gamma}};\bm{\theta}^{t}_{-\mathcal{V}^{t}_{\gamma}})$,
$\mathcal{V}^{t}\coloneqq\bigcup_{\gamma}\mathcal{V}^{t}_{\gamma}$, and
$f^{t}(\bm{\theta}^{t,s,q}_{\mathcal{V}^{t}})=f(\bm{\theta}^{t,s,q}_{\mathcal{V}^{t}};\bm{\theta}^{t}_{-\mathcal{V}^{t}})$.

Input : initial point $\bm{\theta}^{0}$, step-size $\eta$, block samples $S$,
updates per block $Q$

1 for  _$t=0,\dots,T-1$_ do

2 for  _$\gamma=0,\dots,\Gamma$ _in parallel__ do

3 Samples batch indices $\mathcal{B}^{t}\subseteq[N]$

4 $k^{t,0}_{\gamma}\sim P$

5
$\bm{\theta}^{t,S,Q}_{\mathcal{V}^{t}_{\gamma}}(\gamma)\leftarrow\mathcal{M}(\bm{\theta}^{t}_{\mathcal{V}^{t}_{\gamma}},k^{t,0}_{\gamma},\eta,S,Q,f^{t}_{\gamma}(\cdot;\mathcal{B}^{t}))$

6

7
$\bm{\theta}^{t+1}(1),\dots,\bm{\theta}^{t+1}(\Gamma)=\frac{1}{\Gamma}\sum_{\gamma=1}^{\Gamma}\bm{\theta}^{t,S,Q}(\gamma)$

8

Algorithm 5 Stochastic parallel Markov chain coordinate descent (with
overlapping blocks)

The following proof resembles that of Theorem 1, yet we now use the convexity
assumption to handle the averaging of model estimates. We let $\sum_{s}$,
$\sum_{q}$, and $\sum_{\gamma}$ denote $\sum^{S}_{s=0}$, $\sum_{q=0}^{Q}$, and
$\sum_{\gamma=0}^{\Gamma}$, respectively.

###### Proof.

It follows from the convexity assumption (A4) that:

$f(\bm{\theta}^{t+1})-f(\bm{\theta}^{t})=f\left(\frac{1}{\Gamma}\sum_{\gamma}\bm{\theta}^{t,S,Q}(\gamma)\right)-f\left(\bm{\theta}^{t}\right)\leq\frac{1}{\Gamma}\sum_{\gamma}\left(f\left(\bm{\theta}^{t,S,Q}(\gamma)\right)-f\left(\bm{\theta}^{t}\right)\right).$

Therefore, resorting to $L$-smoothness, in particular (5), we have that,

$\displaystyle f(\bm{\theta}^{t+1})-f(\bm{\theta}^{t})$
$\displaystyle\leq\frac{1}{\Gamma}\sum_{\gamma}\left(\left\langle\nabla
f(\bm{\theta}^{t}),\bm{\theta}^{t,S,Q}(\gamma)-\bm{\theta}^{t}\right\rangle+\frac{L}{2}\lVert\bm{\theta}^{t,S,Q}(\gamma)-\bm{\theta}^{t}\rVert^{2}\right)$
$\displaystyle=\frac{1}{\Gamma}\sum_{\gamma}\left(\left\langle\nabla
f^{t}_{\gamma}(\bm{\theta}^{t}_{\mathcal{V}^{t}_{\gamma}}),\bm{\theta}^{t,S,Q}_{\mathcal{V}^{t}_{\gamma}}(\gamma)-\bm{\theta}^{t}_{\mathcal{V}^{t}_{\gamma}}\right\rangle+\frac{L}{2}\lVert\bm{\theta}^{t,S,Q}_{\mathcal{V}^{t}_{\gamma}}(\gamma)-\bm{\theta}^{t}_{\mathcal{V}^{t}_{\gamma}}\rVert^{2}\right)$

and, defining $\bm{g}_{\gamma}^{t}\coloneqq\nabla
f^{t}_{\gamma}\left(\bm{\theta}^{t}_{\mathcal{V}^{t}_{\gamma}};\bm{X}\right)=\nabla
f^{t}_{\gamma}\left(\bm{\theta}^{t}_{\mathcal{V}^{t}_{\gamma}}\right)$ and
$\tilde{\bm{g}}_{\gamma}^{t}\coloneqq\nabla
f^{t}_{\gamma}\left(\bm{\theta}^{t}_{\mathcal{V}^{t}_{\gamma}};\mathcal{B}_{t}\right)$,
we arrive at

$\displaystyle f(\bm{\theta}^{t+1})-f(\bm{\theta}^{t})$
$\displaystyle\leq\frac{1}{\Gamma}\sum_{\gamma}\left(\left\langle\tilde{\bm{g}}_{\gamma}^{t},\bm{\theta}^{t,S,Q}_{\mathcal{V}^{t}_{\gamma}}(\gamma)-\bm{\theta}^{t}_{\mathcal{V}^{t}_{\gamma}}\right\rangle+\left\langle\bm{g}_{\gamma}^{t}-\tilde{\bm{g}}_{\gamma}^{t},\bm{\theta}^{t,S,Q}_{\mathcal{V}^{t}_{\gamma}}(\gamma)-\bm{\theta}^{t}_{\mathcal{V}^{t}_{\gamma}}\right\rangle+\frac{L}{2}\lVert\bm{\theta}^{t,S,Q}_{\mathcal{V}^{t}_{\gamma}}(\gamma)-\bm{\theta}^{t}_{\mathcal{V}^{t}_{\gamma}}\rVert^{2}\right)$
$\displaystyle\leq\frac{1}{\Gamma}\sum_{\gamma}\left(\left\langle\tilde{\bm{g}}_{\gamma}^{t},\bm{\theta}^{t,S,Q}_{\mathcal{V}^{t}_{\gamma}}(\gamma)-\bm{\theta}^{t}_{\mathcal{V}^{t}_{\gamma}}\right\rangle+\frac{L+1}{2}\lVert\bm{\theta}^{t,S,Q}_{\mathcal{V}^{t}_{\gamma}}(\gamma)-\bm{\theta}^{t}_{\mathcal{V}^{t}_{\gamma}}\rVert^{2}+\frac{1}{2}\lVert\bm{g}_{\gamma}^{t}-\tilde{\bm{g}}_{\gamma}^{t}\rVert^{2}\right),$

where we used $\langle a,b\rangle\leq\frac{1}{2}\lVert
a\rVert^{2}+\frac{1}{2}\lVert b\rVert^{2}$ on the term
$\left\langle\bm{g}_{\gamma}^{t}-\tilde{\bm{g}}_{\gamma}^{t},\bm{\theta}^{t,S,Q}_{\mathcal{V}^{t}_{\gamma}}(\gamma)-\bm{\theta}^{t}_{\mathcal{V}^{t}_{\gamma}}\right\rangle$.
We now define and assume $\zeta\coloneqq\eta(L+1)SQ<1$ and use Lemma 3 to
bound the first two terms, with $\psi$ as
$f^{t}_{\gamma}(\cdot;\mathcal{B}_{t})$:

$\displaystyle f(\bm{\theta}^{t+1})-f(\bm{\theta}^{t})$
$\displaystyle\leq\frac{1}{\Gamma}\sum_{\gamma}\left(\eta SQC_{1}(1+\zeta
C_{1})\left\lVert\tilde{\bm{g}}_{\gamma}^{t}\right\rVert^{2}+\eta(\zeta-1)\sum_{s,q}\left\lVert\tilde{\bm{g}}_{\gamma
k_{\gamma}^{t,s}}^{t}\right\rVert^{2}+\frac{1}{2}\lVert\bm{g}_{\gamma}^{t}-\tilde{\bm{g}}_{\gamma}^{t}\rVert^{2}\right)$
$\displaystyle\leq\eta SQC_{1}(1+\zeta
C_{1})\left\lVert\tilde{\bm{g}}^{t}\right\rVert^{2}+\frac{\eta(\zeta-1)}{\Gamma}\sum_{\gamma,s,q}\left\lVert\tilde{\bm{g}}_{\gamma
k_{\gamma}^{t,s}}^{t}\right\rVert^{2}+\frac{1}{2}\lVert\bm{g}^{t}-\tilde{\bm{g}}^{t}\rVert^{2},$

where $\bm{g}^{t}\coloneqq\nabla
f^{t}\left(\bm{\theta}^{t}_{\mathcal{V}^{t}}\right)=\nabla
f^{t}\left(\bm{\theta}^{t}_{\mathcal{V}^{t}};\bm{X}\right)$ and
$\tilde{\bm{g}}^{t}\coloneqq\nabla
f^{t}\left(\bm{\theta}^{t}_{\mathcal{V}^{t}};\mathcal{B}_{t}\right)$ and the
last inequality follows from the fact that $\lVert\nabla
f^{t}(\bm{\theta}^{t}_{\mathcal{V}^{t}})\rVert^{2}\leq\sum_{\gamma}\lVert\nabla
f^{t}_{\gamma}(\bm{\theta}^{t}_{\mathcal{V}^{t}_{\gamma}})\rVert^{2}$. We take
the conditional expectation $\mathbb{E}^{\sigma^{t,1}}$ on both sides of the
inequality above and, since $\zeta\leq 1$, it follows from Lemma 2 that:

$\displaystyle\mathbb{E}^{\sigma^{t,1}}\left[f(\bm{\theta}^{t+1})\right]-f(\bm{\theta}^{t})$
$\displaystyle\leq\eta SQC_{1}(1+\zeta C_{1})\left\lVert\nabla
f^{t}(\bm{\theta}^{t}_{\mathcal{V}^{t}})\right\rVert^{2}+\eta\rho^{\prime}Q(\zeta-1)\left\lVert\nabla
f^{t}(\bm{\theta}^{t}_{\mathcal{V}^{t}})\right\rVert^{2}+\frac{1}{2}\lVert\bm{g}^{t}-\tilde{\bm{g}}^{t}\rVert^{2}$
$\displaystyle=-\underbrace{\eta Q\left(\rho^{\prime}(1-\zeta)-SC_{1}(1+\zeta
C_{1})\right)}_{C^{\prime}_{2}}\left\lVert\nabla
f^{t}(\bm{\theta}^{t}_{\mathcal{V}^{t}})\right\rVert^{2}+\frac{1}{2}\lVert\bm{g}^{t}-\tilde{\bm{g}}^{t}\rVert^{2}.$

Note that, while in Theorem 1 the graph considered in Lemma 2 was that of each
cluster, we now consider the whole communication graph. The rest of the proof
matches the proof of Theorem 1, the only difference being the fact that $p$ is
replaced by $p^{\prime}$, which is such that
$\mathbb{P}(k\in\mathcal{V}^{t})\geq\mathbb{P}(k^{t,0}_{\gamma}=k)\geq
p^{\prime}$. Thus, for
$\eta\in\left(0,\frac{\rho^{\prime}}{(L+1)SQ(\rho^{\prime}+Se(1+e))}\right)$,
we get the inequality that we set out to prove:

$\mathbb{E}\left[\frac{1}{T}\sum_{t=0}^{T-1}\left\lVert\nabla
f\left(\bm{\theta}^{t}\right)\right\rVert^{2}\right]\leq\frac{C_{4}^{\prime}\Delta}{T}+\frac{C_{4}^{\prime}\sigma^{2}}{2B},$

where $C_{4}^{\prime}\coloneqq\frac{1}{p^{\prime}C^{\prime}_{3}}>0$, with
$C_{3}^{\prime}\coloneqq\eta
Q\bigl{(}\rho^{\prime}-(\rho^{\prime}+Se(1+e))\zeta\bigr{)}$. ∎