A Unified Theory of Decentralized SGD with Changing Topology and Local Updates

Introduction

Training machine learning models in a non-centralized fashion can offer many advantages over traditional centralized approaches in core aspects such as data ownership, privacy, fault tolerance and scalability. In efforts to depart from the traditional parameter server paradigm (Dean et al., 2012), federated learning (Konečnỳ et al., 2016; McMahan et al., 2016, 2017; Kairouz et al., 2019) has emerged, but also fully decentralized approaches have been suggested recently—though yet still at a smaller scale than federated learning (Lian et al., 2017; Assran et al., 2019; Koloskova et al., 2020). However, the community has identified a host of challenges that come along with decentralized training: notably, high communication cost (Tang et al., 2018a; Wang et al., 2019; Koloskova et al., 2019), a need for time-varying topologies (Nedić & Olshevsky, 2014; Assran et al., 2019) and data-heterogeneity (Li et al., 2018; Karimireddy et al., 2019; Li et al., 2020a, b). It is imperative to have a good theoretical understanding of decentralized stochastic gradient descent (SGD) to predict the training performance of SGD in these scenarios and to assist the design of optimal decentralized training schemes for machine learning tasks.

In contrast to the centralized setting, where the convergence of SGD is well understood (Bach & Moulines, 2011; Rakhlin et al., 2012; Dekel et al., 2012), the analyses of SGD in non-centralized settings are often application specific and have been historically developed separately in different communities, besides some recent efforts towards a unified theory. Notably, Wang & Joshi (2018) propose a framework for decentralized optimization with non-heterogeneous data and Li et al. (2019) study decentralized SGD for non-convex heterogeneous settings. We here propose a significantly extended framework that covers these previously proposed ones as special cases.

We provide tight convergence rates for a large family of decentralized SGD variants. Proving convergence rates in a unified framework is much more powerful than studying individual special cases on their own: We are not only able to recover many existing analyses and results, we can also often show improved rates under more general setting. Remarkably, for instance for local SGD (Zinkevich et al., 2010; Stich, 2019b; Patel & Dieuleveut, 2019) we show improved rates for the convex and strongly-convex case and recover the best known rates for the non-convex case under weaker assumptions than assumed in prior work (highlighted in Table 1).

We present a unified framework for gossip based decentralized SGD methods that captures local updates and time-varying, randomly sampled, mixing distributions. Our framework covers a rich class of methods that previously needed individual convergence analyses.

Our theoretical results rely on weak assumptions that measure the strength of the noise and the dissimilarity of the functions between workers and a novel assumption on the expected mixing rate of the gossip algorithm. This provides us with great flexibility on how to select the topology of the network and the mixing weights.

We demonstrate the effectiveness and tightness of our results by exemplary showing that our framework gives the best convergence rates for local SGD for both, heterogeneous and iid. data settings, improving over all previous analyses on convex functions.

We provide a lower bound that confirms that our convergence rates are tight on strongly convex functions.

We empirically verify the tightness of our theoretical results on strongly convex functions and explain the impact of noise and data diversity on the convergence.

Related Work

The study of decentralized optimization algorithms can be tracked back at least to (Tsitsiklis, 1984). For the problem of computing aggregates (finding consensus) among clients, various gossip-based protocols have been proposed. For instance the push-sum algorithm (Kempe et al., 2003), based on the intuition of mixing in Markov chains and allowing for asymmetric communication, or the symmetric randomized gossip protocol for averaging over arbirary graphs (Xiao & Boyd, 2004; Boyd et al., 2006) that we follow closely in this work. For general optimization problems, the most common algorithms are either combinations of standard gradient based methods with gossip-type averaging step (Nedić & Ozdaglar, 2009; Johansson et al., 2010), or specifically designed methods relying on problem structure, such as alternating direction method of multipliers (ADMM) (Wei & Ozdaglar, 2012; Iutzeler et al., 2013), dual averaging (Duchi et al., 2012; Nedić et al., 2015; Rabbat, 2015), primal-dual methods (Alghunaim & Sayed, 2019), or block-coordinate methods for generalized linear models (He et al., 2018). There is a rich literature in the control community that discusses various special cases—motivated by particular applications—such as for instance asynchronity (Boyd et al., 2006) or time-varying graphs (Nedić & Olshevsky, 2014, 2016), see also (Nedić et al., 2018) for an overview.

For the deterministic (non-stochastic) descentralized optimization a recent line of work developed optimal algorithms based on acceleration (Jakovetić et al., 2014; Scaman et al., 2017, 2018; Uribe et al., 2018; Fallah et al., 2019). In the machine learning context, decentralized implementations of stochastic gradient descent have gained a lot of attention recently (Lian et al., 2017; Tang et al., 2018b; Assran et al., 2019; Koloskova et al., 2020), especially for the particular (but not fully decentralized) case of a star-shaped network topology, the federated learning setting (Konečnỳ et al., 2016; McMahan et al., 2016, 2017; Kairouz et al., 2019). Rates for the stochastic optimization are derived in (Shamir & Srebro, 2014; Rabbat, 2015), under the assumption that the distributions on all nodes are equal. However, this is a very strong assumption for practical problems.

It has been noted quite early that decentralized gradient based methods in heterogenous data setting suffer from a ‘client-drift’, i.e. the diversity in the functions on each node leads to a drift on each client towards the minima of $f_{i}$—potentially far away from the global minima of $f$. This phenomena has been discussed (and sometimes been adressed by modifing the SGD updates) for example in (Shi et al., 2015; Lee et al., 2015; Nedić et al., 2016) and been rediscovered frequently in the context of stochastic optimization (Zhao et al., 2018; Karimireddy et al., 2019). It is important to note that in analyses based on the bounded gradient assumption—which was traditionally assumend for analyzing SGD (Lacoste-Julien et al., 2012; Rakhlin et al., 2012)—the diversity in the data distribution on each worker sometimes can be hidden in this generous upper bound and the analyses cannot distinguish between iid. and non-iid. data cases, such as e.g. in (Koloskova et al., 2019; Nadiradze et al., 2019; Li et al., 2020b). In this work, we use much weaker assumptions and we show how the convergence rate depends on the similarity between the functions (by providing matching lower and upper bounds). Our results show that in overparametrized settings no drift effects occur and linear convergence can be achieved similar as to the centralized setting (Schmidt & Roux, 2013; Needell et al., 2016; Ma et al., 2018).

For reducing communication cost, various techniques have been proposed. In this work we do not consider gradient compression techniques (Alistarh et al., 2017; Stich et al., 2018; Tang et al., 2018a, 2019; Stich & Karimireddy, 2019)—but such orthogonal techniques could be added on top of our scheme—and instead only focus on local updates steps which are often efficient in practice but challenging to handle in the theoretical analysis (McMahan et al., 2017; Stich, 2019b; Yu et al., 2019; Lin et al., 2020).

Setup

We study the distributed stochastic optimization problem

where $\mathcal{D}_{i}$ denotes the distribution of $\xi_{i}$ over parameter space $\Omega_{i}$ on node $i$. Standard empirical risk minimization is an important special case of this problem, when each $\mathcal{D}_{i}$ presents a finite number $m_{i}$ of elements $\{\xi_{i}^{1},\dots,\xi_{i}^{m_{i}}\}$. Then $f_{i}$ can be rewritten as $f_{i}(\mathbf{x})=\frac{1}{m_{i}}\sum_{j=1}^{m_{i}}F_{i}(\mathbf{x},\xi_{i}^{j})$. In the special case of $m_{i}=1$, for each $i\in[n]$, we further recover the deterministic distributed optimization problem.

For all our theoretical results we assume that $f$ is smooth.

Sometimes it will be enough to just assume smoothness of $f_{i}$ instead.

Clearly, Assumption 1b is more general than Assumption 1a. Moreover, for convex $F(\mathbf{y},\xi)$ Assumption 1a implies Assumption 1b (Nesterov, 2004).

Assumption 1b is quite common in the literature (e.g. Lian et al., 2017; Wang & Joshi, 2018) but sometimes also the stronger Assumption 1a is assumed (Nguyen et al., 2018). We here use this version in the convex case only, to allow for a more general assumption on the noise instead (see Section 3.2 below).

For some of the derived results we need in addition convexity. Specifically, $\mu$-convexity for a parameter $\mu\geq 0$.

2 Assumptions on the noise

We now formulate our conditions on the noise. For the convergence analysis of SGD on smooth convex functions it is typically enough to assume a bound on the noise at the optimum only (Needell et al., 2016; Bottou et al., 2018; Gower et al., 2019; Stich, 2019a). Similarly, to express the diversity of the functions $f_{i}$ in the convex case it is sufficient to measure it only at the optimal point $\mathbf{x}^{\star}$ (such a point always exists for strongly convex functions).

Let $\mathbf{x}^{\star}=\operatorname*{arg\,min}f(\mathbf{x})$ and define

and similarly as above, $\bar{\sigma}^{2}:=\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}^{2}$. We assume that $\bar{\sigma}^{2}$ and $\bar{\zeta}^{2}$ are bounded.

Here, $\bar{\sigma}^{2}$ measures the noise level, and $\bar{\zeta}^{2}$ the diversity of the functions $f_{i}$. If all functions are identical, $f_{i}=f_{j}$, for all $i,j$, then $\bar{\zeta}^{2}=0$. Many prior work in the context of stochastic decentralized optimization often assumed bounded diversity and bounded noise everywhere (such as e.g. Lian et al., 2017; Tang et al., 2018b), whereas we here only need to assume this bound locally at $\mathbf{x}^{\star}$.

For the non-convex case—where a unique $\mathbf{x}^{\star}$ does not necessarily exist—we generalize Assumption 3a to:

We see that Assumption 3a is weaker than Assumption 3b as it only needs ho hold for $\mathbf{x}_{i}=\mathbf{x}^{\star}$. Further, it is important to note that we do not assume a uniform bound on the variance (as many prior work, such as Li et al., 2019; Tang et al., 2018b; Lian et al., 2017; Assran et al., 2019) but instead allow the bound on the noise and the diversity to grow with the gradient norm (similar assumptions are common in the convex setting (Bottou et al., 2018)).

Discussion. We now show that the Assumption 3b is weaker than assuming a uniform upper bound on the noise. The uniform variance bound is given as

similarly for the similarity of functions between nodes

A second common assumption is to assume that the (stochastic) gradients are uniformly bounded (e.g. Koloskova et al., 2019; Li et al., 2020b), that is

for a constant $G$. Under the bounded gradient assumption, Assumption 3b is clearly satisfied, as all terms on the left hand side of (8) and (9) can be upper bounded by $2G^{2}$.

3 Notation

We use the notation $\mathbf{x}_{i}^{(t)}$ to denote the iterates on node $i$ at time step $t$. We further define the average

We use both vector and matrix notation whenever it is more convenient, and define

and likewise define $\bar{X}^{(t)}:=\left[\bar{\mathbf{x}}^{(t)},\dots,\bar{\mathbf{x}}^{(t)}\right]\equiv X^{(t)}\frac{1}{n}\mathbf{1}\mathbf{1}^{\top}$.

Decentralized (Gossip) SGD

We now present the generalized decentralized SGD framework. Similar to existing works (Lian et al., 2017; Wang & Joshi, 2018; Li et al., 2019) our proposed method allows only decentralized communications. That is, the exchange of information (through gossip averaging) can only occur between connected nodes (neighbors). The algorithm (outlined in Algorithm 1) consists of two phases: (i) stochastic gradient updates, performed locally on each worker (lines 4–5), followed by a (ii) consensus operation, where nodes average their values with their neighbors (line 6).

The gossip averaging protocol can be compactly written in matrix notation, with $\mathcal{N}_{i}^{(t)}:=\{j\colon w_{ij}^{(t)}>0\}$ denoting the neighbors of node $i$ at iteration $t$:

where the mixing matrix $W^{(t)}\in^{n\times n}$ encodes the network structure at time $t$ and the averaging weights (nodes $i$ and $j$ are connected if $w^{(t)}_{ij}>0$).

Our scheme shows great flexibility as the mixing matrices can change over iterations and moreover can be selected from (changing) distributions.

A symmetric ($W\!=\!W^{\top}$) doubly stochastic ($W\mathbf{1}\!=\!\mathbf{1}$, $\mathbf{1}^{\top}W\!=\!\mathbf{1}^{\top}\!$) matrix $W\!\in\!^{n\times n}$.

In each iteration in Algorithm 1 a new mixing matrix $W^{(t)}$ is sampled from a possibly time-varying distribution $\mathcal{W}^{(t)}$, $t\in\{0,\dots,T\}$ (we will show below that also degenerate mixing matrices, for instance $W^{(t)}=\mathbf{I}_{n}$ which implies no communication in round $t$, are possible choices). We will discuss several important instances below, but first we now state our assumption on the quality of the mixing matrices. This assumption is novel in the literature to the best of our knowledge and a natural generalization of earlier versions.

2 New assumption on mixing matrices

We recall that for randomized gossip averaging with a randomly sampled mixing matrix $W\sim\mathcal{W}$ it holds

In our analysis it will be enough to assume that a property similar to (12) holds for the composition of mixing matrixes, and does not necessarily hold for every single step.

It is crucial to observe that this assumption does not require every realization $W$ to satisfy a decrease property as for the standard analysis, it is enough if it holds over the concatenation of $\tau$ mixing steps. This assumption differs from the connectivity assumptions sometimes used in the control community. For example Nedić & Olshevsky (2014) require strong connectivity of the graph after every $\tau$ steps, whereas we here do not require this (for example, even sampling one single random edge leads to a positive decrease in expectation, whereas to ensure connectivity one would need to perform $\Omega(n)$ pairwise communications). This means that our bounds are typically much tighter that bounds derived on the strong connectivity assumption. However, as we require $W$ to be symmetric, our setting is less general than the one considered in (Nedić et al., 2017; Xi & Khan, 2017; Saadatniaki et al., 2018; Assran & Rabbat, 2018; Scutari & Sun, 2019; Assran et al., 2019).

Examples Covered in the Framework

Our framework is very general and covers many special cases previously introduced in the literature.

The simplest instances of Algorithm 1 arise when the mixing matrix $W$ is kept constant over the iterations. By choosing the fully connected matrix $W=\frac{1}{n}\mathbf{1}\mathbf{1}^{\top}$ we recover $\bullet$ centralized mini-batch SGD (Dekel et al., 2012) and by choosing an arbitrary connected $W$, we recover $\bullet$ decentralized SGD (Lian et al., 2017).

One noteably instance of this type is $\bullet$ loopless local decentralized SGD where the mixing matrix is (a fixed) $W$ with probability $\frac{1}{\tau}$, and $\mathbf{I}_{n}$ with probability $1-\frac{1}{\tau}$, for a parameter $\tau\geq 1$. This algorithm mimicks the behavior of the local SGD (see subsection below), commonly analyzed for $W=\frac{1}{n}\mathbf{1}\mathbf{1}^{\top}$ only, but the loopless variant is much easier to analyze (with $p$ decreased by a factor of $\tau$, but no need to consider local steps explicitly in the analysis.).

𝑡𝜏\mathcal{W}^{(t)}\equiv\mathcal{W}^{(t+\tau)}) Our analysis covers the empirical (finite-sample) versions of the aforementioned algorithms, for instance $\bullet$ alternating decentralized SGD that sweeps through $\tau$ fixed mixing matrices. A special algorithm of this type is $\bullet$ local SGD (Coppola, 2015; Zhou & Cong, 2018; Stich, 2019b) where averaging on the complete graph is performed every $\tau$ iterations and only local steps are performed otherwise (mixing matrix $\mathbf{I}_{n}$ for $\tau-1$ steps).

Our analysis covers also natural extensions such as $\bullet$ decentralized local SGD where mixing is performed with an arbitrary matrix $W$, and $\bullet$ random decentralized local SGD where the mixing matrix is sampled from a distribution. More generally, our framework also allows to combine local steps with all of the examples described in the previous section.

3 Non-Periodic Sampling

It is not necessary to have a periodic structure, it is sufficient that the composition of every $\tau$ consecutive mixing matrixes satisfies Assumption 4. For instance as in $\bullet$ distriributed SGD over time-varying graphs (Nedić & Olshevsky, 2014).

4 Other Frameworks

In contrast to many prior works, we here allow the topology and the averaging weights to change between iterations. Our framework covers $\bullet$ Cooperative SGD (Wang & Joshi, 2018) which considers only the IID data case ($f_{i}=f_{j}$) with local updates and a fixed mixing matrix $W$, and the recently proposed $\bullet$ periodic decentralized SGD (Li et al., 2019) that allows for multiple local update and multiple mixing steps (for fixed $W$) in a periodic manner. None of these work considered sampling of the mixing matrix and do only provide rates for non-convex functions.

Convergence Result

In this section we present the convergence results for decentralized SGD variants that fit the template of Algorithm 1.

iterations, for positive weights $w_{t}$ and $F_{0}:=f(\mathbf{x}_{0})-f^{\star}$ and $R_{0}=\left\lVert\mathbf{x}_{0}-\mathbf{x}^{\star}\right\rVert$ denote the initial errors.

2 Lower Bound

We now show that the terms depending on $\bar{\zeta}$ are necessary for the strongly convex setting and cannot be removed by an improved analysis.

iterations to converge to accuracy $\epsilon$.

3 Discussion

Exemplary, we focus in our discussion on the strongly convex case only. For strongly convex functions we prove that the expected function value suboptimality decreases as

where $T$ denotes the iteration counter. We now argue that this rate is optimal up to acceleration.

Stochastic Terms. If $\bar{\sigma}^{2}>0$ the convergence rate is asymptotically dominated by the first term, which cannot be further improved for stochastic methods (Nemirovsky & Yudin, 1983). We observe that the dominating first term indicates a linear speedup in the number of workers $n$, and no dependence on the number of local steps $\tau$, the mixing parameter $p$ or the dissimilarity parameter $\bar{\zeta}^{2}$. This means that decentralized SGD methods are ideal for the optimization in the high-noise regime even when network connectivity is low and number of local steps is large (see also (Chaturapruek et al., 2015) and recent work (Pu et al., 2019)). In our rates the variance $\bar{\sigma}^{2}$ parameter also appears in the second term, but affects the convergence only mildly (for $T=\Omega(\tau n/p)$ this second term gets dominated by the first one).

Optimization Terms. Even when $\bar{\sigma}^{2}=0$, the convergence of decentralized SGD only sublinear when $\bar{\zeta}^{2}>0$:Except for the special case when $p=1$ (fully connected graph, such as for mini-batch SGD). In this case the rate does not depend on $\bar{\zeta}^{2}$. We detail this (known result) in the appendix.

The dependence on the dissimilarity $\bar{\zeta}^{2}$ cannot be removed in general as we show in Theorem 3. These results show that decentralized SGD methods without additional modifications (see also Shi et al., 2015; Karimireddy et al., 2019) cannot converge linearly.

We can further observe see that the rates only depend on the ratio $p/\tau$, but not on $p$ or $\tau$ individually. This also means that the rates for local variants of decentralized SGD are the same as for their loopless variants (when the mixing is performed with probability $\frac{1}{\tau}$ only). The error term depending on $R_{0}^{2}$ vanishes exponentially fast, as expected for SGD methods (Bach & Moulines, 2011). The linear dependence on $\frac{L}{\mu p}$ (the therm in the exponent) is expected here, as we use non-accelerated first order schemes and standard gossip. This term could potentially be improved to \smash{\bigl{(}\frac{L}{\mu p}\bigr{)}^{1/2}} with acceleration techniques, such as in (Scaman et al., 2017). The linear dependence on $\tau$ cannot further be improved in general. This follows from the lower bound for the communication complexity of distributed convex optimization (Arjevani & Shamir, 2015), as the number of communication rounds is at most $\frac{T}{\tau}$ (no communication happens during the local steps). However, when $\bar{\zeta}^{2}=0$ (as for instance the case for identical functions $f_{i}$ on each worker), this lower bound becomes vacuous and improvement of the dependence on $\tau$ might be possible (which we cannot not exploit here).

In overparametrized problems, there exists always $\mathbf{x}^{\star}$ s.t. $\left\lVert\nabla f_{i}(\mathbf{x}^{\star})\right\rVert^{2}=0$, that is $\bar{\sigma}^{2}=0$ and $\bar{\zeta}^{2}=0$. We prove here that decentralized SGD converges linearly in this case, similarly to mini-batch SGD (Bach & Moulines, 2011; Schmidt & Roux, 2013; Needell et al., 2016; Ma et al., 2018; Gower et al., 2019; Loizou et al., 2020).

Special Cases: Highlights

Our rates apply to all the examples discussed in Section 5 and of course we could design even more variants and combinations of these schemes. This gives great flexibility in designing new schemes and algorithms for future applications. We leave the exploration of the trade-offs in these approaches for future work, and highlight here only a few special cases that could be of particular interest.

Local SGD is a simplified version of the federated averaging algorithm (McMahan et al., 2016, 2017) and has recently attracted the attention of the theoretical community in the seek of the best convergence rates (Stich, 2019b; Wang & Joshi, 2018; Yu et al., 2019; Basu et al., 2019; Patel & Dieuleveut, 2019; Stich & Karimireddy, 2019; Li et al., 2019; Khaled et al., 2020). Our work extends this chain and improves previous best results for convex settings and recovers the results of Li et al. (2019) in the non-convex case as we highlight in Table 1. We point out that all these rates are still dominated by large-batch SGD and do not match the lower bounds established in (Woodworth et al., 2018) for the iid. case $\bar{\zeta}^{2}=0$. See also recent parallel work in (Woodworth et al., 2020). Whilst these previous analysis were often specifically tailored and only applicable to the mixing structure in local SGD, our analysis is much more general and tighter at the same time.

In their recently updated parallel version, Karimireddy et al. (2019) improve upon these rates by removing $\sigma$ from the second term. However, they do analyze a different version of local SGD (with different stepsizes for inner and outer loops) than we consider here. This change does not fit in our framework and it is not clear if similar trick is possible the decentralized setting.

2 Comparison to Recent Frameworks

We mentioned major differences to other frameworks in Section 5.4 above already. Our results for the non-convex case recover the best results from (Wang & Joshi, 2018) for the iid. case These results can be recovered by optimizing the stepsize in (Wang & Joshi, 2018, Theorem 1) directly, instead of resorting to the worse rate stated in (Wang & Joshi, 2018, Corollary 1). ($\hat{\zeta}^{2}=0$) and the non-iid. case from (Li et al., 2019) for their specific settings. We point out that our results also cover the convex setting and deterministic setting.

3 Best Rates for Decentralized SGD

We improve best known rates of Decentralized SGD (Olshevsky et al., 2019; Koloskova et al., 2019) for strongly convex objectives and recover the best rates in the non-convex case (Lian et al., 2017).

Experiments

Complementing prior work that established the effectiveness of decentralized training methods (Lian et al., 2017; Assran et al., 2019) we here focus on verifying whether the numerical performance of decentralized stochastic optimization algorithms coincides with the rates predicted by theory, focusing on the strongly convex case for now.

We consider a distributed least squares objective with $f_{i}(\mathbf{x}):=\frac{1}{2}\left\lVert\mathbf{A}_{i}\mathbf{x}-\mathbf{b}_{i}\right\rVert_{2}^{2}$, for fixed Hessian $\mathbf{A}_{i}^{2}=\frac{i^{2}}{n}\cdot\mathbf{I}_{d}$ and sample each $\mathbf{b}_{i}\sim\mathcal{N}(0,\nicefrac{{\bar{\zeta}^{2}}}{{i^{2}}}\mathbf{I}_{d})$ for a parameter $\bar{\zeta}^{2}$, which controls the similarity of the functions (and coincides with the parameter in Assumption 3a). We control the stochastic noise $\bar{\sigma}^{2}$ by adding Gaussian noise to every stochastic gradient. We depict the effect of these parameters in Figure 2.

We consider three common network topologies, ring, 2-$d$ torus and fully-connected graph and use the Metropolis-Hasting mixing matrix $W$, i.e. $w_{ij}=w_{ji}=\frac{1}{deg(i)+1}=\frac{1}{deg(j)+1}$ for $\{i,j\}\in E$. For all algorithms we tune the stepsize to reach a desired target accuracy $\epsilon$ with the fewest number of iterations.

Discussion of Results.

In Figure 1 we depict the results. We observe that in the high noise regime (bottom row) the graph topology and the functions similarity $\bar{\zeta}^{2}$ do not impact the number of iterations needed to reach the target accuracy (the $\frac{\bar{\sigma}^{2}}{T}$ term is dominating in this regime. We also see linear rates when $\bar{\sigma}^{2}=\bar{\zeta}^{2}=0$ as predicted. When increasing $\bar{\zeta}^{2}$ (in the case of $\bar{\sigma}^{2}=0$) we see that on the ring and torus topology the linear rate changes to a sublinear rate: even thought the curves look like straight lines, they stop converging when reaching the target accuracy (the stepsize must be further decreased to achieve higher accuracy). By comparing two top right plots, we see that for fixed topology the number of iterations increases approximately by a factor of $\sqrt{10}$ when increasing $\bar{\zeta}^{2}$ by a factor of 10, as one would expect from the term $\frac{\bar{\zeta}^{2}}{p^{2}T^{2}}$ in the convergence rate (see also Figure 3 in the appendix). The difference in number of iterations on the torus vs. ring scales approximately linear in the ratio of their mixing parameters $p$, (that is, $\Theta(n)$ as mentioned in Section 4.2).

Extensions

We presented a unifying framework for the analysis of decentralized SGD methods and provide the best known convergence guarantees. Our results show that when the noise is high, decentralized SGD methods can achieve linear speedup in the number of workers $n$ and the convergence rate does only weakly depend on the graph topology, the number of local steps or the data heterogeneity. This shows that such methods are perfectly suited to solve stochastic optimization problems in a decentralized way. However, our results also reveal that when the noise is small (for e.g. when using large mini-batches), the effect of those parameters become more pronounced and especially function diversity can hamper the convergence of decentralized SGD methods.

Our framework can be further extended by considering gradient compression techniques (Koloskova et al., 2019) or overlapping communication steps (Assran et al., 2019; Wang et al., 2020) to additionally speedup the distributed training.

Acknowledgements

We would like to thank Edouard Oyallon for indicating an inaccuracy in the proof in the first version of this manuscript. We acknowledge funding from SNSF grant 200021_175796, as well as a Google Focused Research Award. Nicolas Loizou acknowledges support by the IVADO Postdoctoral Funding Program.

References

Appendix A Proof of Theorem 2

We can rewrite Algorithm 1 using the following matrix notation, extending the definition used in the main text:

A.2 Proof Sketch—Combining Consensus Progress (Gossip) and Optimization Progress (SGD)

We will then bound the consensus distance $\Xi_{t}$ as detailed in Section C; Lemmas 9 and 12 by a recursion of the form

where $m=\lfloor{t/\tau}\rfloor-1$; for convex cases $A=8\bar{\sigma}^{2}+\frac{18\tau}{p}\bar{\zeta}^{2}$ , $D=72L\frac{\tau}{p}$ (Lemma 9) and for non-convex case $A=2\hat{\sigma}^{2}+2\left(\frac{6\tau}{p}+M\right)\hat{\zeta}^{2}$, $D=2P\left(\frac{6\tau}{p}+M\right)$ (Lemma 12).

Note that (16) holds only for $t\geq(m+1)\tau$. To be able to simplify (16) we additionally consider $m\tau\leq t<(m+1)\tau$ and prove (Lemmas 10, 13) that with the same parameters as above, it holds

Next, we simplify this recursive equation (16) using Lemma 14 and some positive weights $\{w_{t}\}_{t\geq 0}$ (see Lemma 14 for the definition of the weights $w_{t}$) to

Then we combine (15) and (18). Firstly rearranging (15), multiplying by $w_{t}$ and dividing by $\eta_{t}$, we get

Now summing up and dividing by $W_{T}=\sum_{t=0}^{T}w_{t}$,

Finally, to solve this main recursion (19) and obtain the final convergence rates of Theorem 2, we will use the following Lemmas, which will be presented in Section D:

Lemma 15 for strongly convex case when $a>0$.

Lemmas 16 and 17 for both weakly convex and non-convex cases as their common feature is that $a=0$.

A.3 How the Proof of Theorem 2 Follows

In this section we summarize how the proof of Theorem 2 follows from the results that we establish in Sections C and D below. Note that for convex cases we require both $f_{i}$ and $F_{i}$ to be convex as in Lemma 9.

A.4 Improved rate when τ=1𝜏1\tau=1 (recovering mini-batch SGD convergence results)

In the special case when $\tau=1$ the proof can be simplified and the rate can be improved: there will be an additional $(1-p)$ factor appearing in the middle term, e.g in strongly convex case the improved rate reads as

The main difference to the general result stated in Theorem 2 (for $\tau\geq 1$) is that the second term is multiplied with $(1-p)$, allowing to recover the rate of mini-batch SGD in the case of fully-connected graph when $p=1$. This improvement also holds for the weakly-convex and non-convex case.

In order to do so, one has to observe that the consensus distance Lemmas 9 and 12 can be improved when $\tau=1$. In the first lines of both these proofs we multiply with $(1-p)$ not only the first term $\left\lVert X^{(t)}-\bar{X}^{(t)}\right\rVert_{2}^{2}$ but also the second term with the gradient as during the 1-step averaging both $\mathbf{x}^{(t)}$ and $\eta_{t}\partial F_{i}(X^{(t)},\xi_{i}^{(t)})$ are averaged with mixing matrix $W^{(t)}$ (line 4 of Algorithm 2). We omit the full derivations for this special case, as they can easily be obtained by following the current proofs.

Appendix B Technical Preliminaries

One step of gossip averaging with the mixing matrix $W$ (def. 1) preserves the average of the iterates, i.e.

If for functions $F_{i}(\mathbf{x},\xi)$ Assumption 1a holds, then it also holds that

Moreover, if in addition $F_{i}$ are convex functions, then

where $g(\mathbf{x})$ is either $F_{i}$ or $f_{i}$.

B.2 Useful Inequalities

B.3 τ𝜏\tau-slow Sequences

The sequence $\{a_{t}\}_{t\geq 0}$ of positive values is $\tau$-slow decreasing for parameter $\tau>0$ if

The sequence $\{a_{t}\}_{t\geq 0}$ is $\tau$-slow increasing if $\{a_{t}^{-1}\}_{t\geq 0}$ is $\tau$-slow decreasing.

The sequence $\{\eta_{t}^{2}\}_{t\geq 0}$ with $\eta_{t}=\frac{a}{b+t}$, $b\geq\frac{32}{p}$ is $\frac{4}{p}$-slow decreasing.

The sequence of constant stepsizes $\{\eta_{t}^{2}\}_{t\geq 0}$ with $\eta_{t}=\eta$ is $\tau$-slow decreasing for any $\tau$.

The sequence $\{w_{t}\}_{t\geq 0}$ with $w_{t}=(1-\frac{p}{64\tau c})^{-t}$, $c\geq 1$ is $\frac{16\tau}{p}$-slow increasing.

The sequence $\{w_{t}\}_{t\geq 0}$ with $w_{t}=(b+t)^{2}$, $b\geq\frac{128}{p}$ is $\frac{16}{p}$-slow increasing.

The sequence of constant weights $\{w_{t}\}_{t\geq 0}$ with $w_{t}=1$ is $\tau$-slow increasing for any $\tau$.

Appendix C Descent Lemmas and Consensus Recursions

In this section, according to our proof sketch we derive descent (15) and consensus recursions (18) for both convex and also non-convex cases.

Under Assumptions 1a, 2, 3a and 4, the averages $\bar{\mathbf{x}}^{(t)}:=\frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_{i}^{(t)}$ of the iterates of Algorithm 1 with the stepsize $\eta_{t}\leq\frac{1}{12L}$ satisfy

where $\bar{\sigma}^{2}=\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}^{2}$.

Because all mixing matrixes preserve the average (Proposition 1), we have

Where at the last step (25) was applied to $\left\lVert\bar{\mathbf{x}}^{(t)}-\mathbf{x}^{\star}\right\rVert^{2}\leq 2\left\lVert\bar{\mathbf{x}}^{(t)}-\mathbf{x}_{i}^{(t)}\right\rVert^{2}+2\left\lVert{\mathbf{x}}_{i}^{(t)}-\mathbf{x}^{\star}\right\rVert^{2}$. Putting everything together and using that $\eta_{t}\leq\frac{1}{12L}$ we are getting statement of the lemma.∎

Under Assumptions 1a, 2, 3a and 4, if in addition functions $F_{i}$ are convex and if stepsizes $\eta_{t}\leq\frac{p}{96\sqrt{6}\tau L}$, then

Using matrix notation (14), for $t\geq\tau$

where we used that $\left\lVert A-\bar{A}\right\rVert_{F}^{2}=\sum_{i=1}^{n}\left\lVert\mathbf{a}_{i}-\bar{\mathbf{a}}\right\rVert_{2}^{2}\leq\sum_{i=1}^{n}\left\lVert\mathbf{a}_{i}\right\rVert_{2}^{2}=\left\lVert A\right\rVert_{F}^{2}$. Unrolling $X^{(t)}$ up to $X^{(m\tau)}$ using lines 3–4 of the Algorithm 2,

Now, similarly, we split terms that depend on $X^{(t-2)}$ with $\beta_{2}=\frac{1}{C-2}$. Note that $(1+\beta_{1})(1+\beta_{2}^{-1})=C$ and $(1+\beta_{1})(1+\beta_{2})=\frac{C}{C-2}$:

Splitting the same way the rest of the terms and using that $\frac{C}{C+j-(t-1)}\leq 2$ for $C\geq 2\tau$,

Taking $C=2\tau(1+\frac{2}{p})$ and using (13) to bound the first term we get that

Estimating separately the last two terms, and using the notation $\pm a=a-a=0~{}\forall a$,

where the last term is bounded by $n\bar{\sigma}^{2}$ by definition (7). Putting back estimates for $T_{1}$ and $T_{2}$ and using that $\eta_{t}\leq\frac{p}{96\sqrt{6}\tau L}$ we arrive to the statement of the lemma. ∎

This recursion in Lemma 9 holds only when $t\geq(m+1)\tau$. For these steps we are guaranteed to get $(1-p)$ decrease by Assumption 4. To simplify this recursion we would need similar relation also for smaller $t$ that is $m\tau\leq t<(m+1)\tau$, that we derive in Lemma 10.

Under Assumptions 1a, 2, 3a and 4, if in addition functions $F_{i}$ are convex and if stepsizes $\eta_{t}\leq\frac{p}{96\sqrt{6}\tau L}$, then

The proof follows exactly the same lines as in Lemma 9, with the change that we don’t use (13) to decrease the consensus distance by $(1-p)$, but instead we use the Definition 1 that each $W^{(i)}$ is doubly stochastic

C.2 Non-convex Case

Here we derive descent recursive equation (15) and recursion for consensus distance (16) for the non-convex case.

Under Assumptions 1b, 3b and 4, the averages $\bar{\mathbf{x}}^{(t)}:=\frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_{i}^{(t)}$ of the iterates of Algorithm 1 with the constant stepsize $\eta<\frac{1}{4L(M+1)}$ satisfy

Because all mixing matrixes preserve the average (Proposition 1) and function $f$ is $L$-smooth, we have

To estimate the second term, we add and subtract $\nabla f(\bar{\mathbf{x}}^{(t)})$

For the last term, using the notation $~{}\pm a=a-a=0~{}~{}\forall a$,

Combining this together and using $L$-smoothness to estimate $\left\lVert\nabla f_{i}(\bar{\mathbf{x}}^{(t)})-\nabla f_{i}(\mathbf{x}_{i}^{(t)})\right\rVert_{2}^{2}$ and $\left\lVert\nabla f(\bar{\mathbf{x}}^{(t)})-\nabla f(\mathbf{x}_{i}^{(t)})\right\rVert_{2}^{2}$,

Applying $\eta<\frac{1}{4L(M+1)}$ we get statement of the lemma. ∎

Under Assumptions 1b, 3b and 4, if the stepsize $\eta_{t}\leq\frac{p}{8L\sqrt{2\tau(6\tau+pM)}}$, then

where we used that $\left\lVert A-\bar{A}\right\rVert_{F}^{2}=\sum_{i=1}^{n}\left\lVert\mathbf{a}_{i}-\bar{\mathbf{a}}\right\rVert\leq\sum_{i=1}^{n}\left\lVert\mathbf{a}_{i}\right\rVert_{F}^{2}=\left\lVert A\right\rVert_{F}^{2}$. Unrolling $X^{(t)}$ up to $X^{(m\tau)}$ using lines 3-4 of the Algorithm 2 and splitting stochastic terms similar way as for the convex cases in Lemma 9,

Putting back estimate for $T$ and using that $\eta_{t}\leq\frac{p}{8L\sqrt{2\tau(6\tau+pM)}}$ we arrive to the statement of this lemma. ∎

Similarly to the convex cases, we additionally need a recursion for values $t$ that are in between $m\tau\leq t<(m+1)\tau$

Under Assumptions 1b, 3b and 4, if the stepsize $\eta_{t}\leq\frac{p}{8L\sqrt{2\tau(6\tau+pM)}}$, and $t$ such that $m\tau\leq t<(m+1)\tau$ then

As in the convex case, we need to change the proof of Lemma 12 just slightly, by applying Def. 1 instead of (13) as follows

C.3 Simplifying Consensus Recursion

In Lemmas 9, 12 we obtained the consensus recursive equation (16) for both convex and non-convex cases. In this section we simplify it to be able to easily combine it later with (15).

If non-negative sequences $\{\Xi_{t}\}_{t\geq 0}$, $\{e_{t}\}_{t\geq 0}$ and $\{\eta_{t}\}_{t\geq 0}$ satisfy (16) and (17) for some constants $0<p\leq 1,\tau\geq 1,A,D\geq 0$, moreover if the stepsizes $\{\eta_{t}^{2}\}_{t\geq 0}$ is $\frac{8\tau}{p}$-slow decreasing sequence (Definition 2), and if $\{w_{t}\}_{t\geq 0}$ is $\frac{16\tau}{p}$-slow increasing non-negative sequence of weights, then it holds that

for some constant $B>0$ with the constraint that stepsizes $\eta_{t}\leq\frac{1}{16}\sqrt{\frac{pb}{DB\tau}}$.

Recursively substituting every $\Xi_{j}$ for $j\geq(m+1)\tau$ in the second term of (16) we get

We substitute the rest of $\Xi_{j}$ for $m\tau\leq j<(m+1)\tau$ with (17). Lets start with substituting $\Xi_{(m+1)\tau-1}$

Since $0<p\leq 1$, it holds that $\frac{p}{64\tau}\left(1+\frac{p}{2}\right)\leq\left(1-\frac{p}{2}\right)\frac{p}{16\tau}$ and therefore

Applying the same way (17) to the rest of $\Xi_{j}$ and using that $\frac{p}{64\tau}\leq\frac{p}{16\tau}$ we get that

Using that $\left(1+\frac{p}{16\tau}\right)^{2\tau}\leq\exp\left(\frac{p}{8}\right)\leq 1+\frac{p}{4}$ for $p\leq 1$ and also that $(1+\frac{p}{16\tau})^{t-1-j}\leq\left(1+\frac{p}{16\tau}\right)^{2\tau}\leq 1+\frac{p}{4}\leq 2$

Unrolling $\Xi_{m\tau}$ recursively up to we get,

For the first term estimating $\left(1-\frac{p}{4}\right)^{1/\tau}\leq\exp(-\frac{p}{4\tau})\leq 1-\frac{p}{8\tau}$ and that $\left(1-\frac{p}{8\tau}\right)^{\tau\lfloor(t-j)/\tau\rfloor}\leq\left(1-\frac{p}{8\tau}\right)^{t-j}\left(1-\frac{p}{8\tau}\right)^{-\tau}$. For the last term, $\left(1-\frac{p}{8\tau}\right)^{-\tau}\leq\left(\frac{1}{1-\frac{p}{8\tau}}\right)^{\tau}\leq(1+\frac{p}{4\tau})^{\tau}$ because $\frac{p}{8\tau}\leq\frac{1}{2}$ and finally $\left(1+\frac{p}{4\tau}\right)^{\tau}\leq\exp(\frac{p}{4})<2$,

Now using that $\eta_{t}^{2}$ is $\frac{8\tau}{p}$-slow decreasing, i.e. $\eta_{j}^{2}\leq\eta_{t}^{2}\left(1+\frac{p}{16\tau}\right)^{t-j}$ and using that $(1-\frac{p}{8\tau})(1+\frac{p}{16\tau})\leq(1-\frac{p}{16\tau})$

Now averaging $\Xi_{t}$ with weights $w_{t}$ and using that $w_{t}$ is $\frac{16\tau}{p}$-slow increasing sequence, i.e. $w_{t}\leq w_{j}\left(1+\frac{p}{32\tau}\right)^{t-j}$, and also using that $\eta_{t}\leq\frac{1}{16}\sqrt{\frac{pb}{DB\tau}}$

Appendix D Solving the Main Recursion (19)

If non-negative sequences $\{r_{t}\}_{t\geq 0},\{e_{t}\}_{t\geq 0}$ satisfy (19) for some constants $a,b,p~{}>~{}0,c,A,B,\tau~{}\geq~{}0$, then there exists a constant stepsize $\eta_{t}=\eta<\frac{1}{d}$ such that for weights $w_{t}=(1-a\eta)^{-(t+1)}$ and $W_{T}:=\sum_{t=0}^{T}w_{t}$ it holds:

Starting from (19) and using that $\eta_{t}=\eta$ and that $\frac{w_{t}(1-a\eta)}{\eta}=\frac{w_{t-1}}{\eta}$ we obtain a telescoping sum,

Using that $W_{T}\leq\frac{w_{T}}{a\eta}$ and $W_{T}\geq w_{T}=(1-a\gamma)^{-(T+1)}$ we can simplify

Now lemma follows by tuning $\eta$ the same way as in (Stich, 2019a).

If $\frac{1}{d}\geq\frac{\ln(\max\{2,a^{2}r_{0}T^{2}/c\})}{aT}$ then we choose $\eta=\frac{\ln(\max\{2,a^{2}r_{0}T^{2}/c\})}{aT}$ and get that

Otherwise $\frac{1}{d}\leq\frac{\ln(\max\{2,a^{2}r_{0}T^{2}/c\})}{aT}$ we pick $\eta=\frac{1}{d}$ and get that

D.2 a=0𝑎0a=0 (weakly convex and non-convex cases)

Now we assume that in Assumption 2 $\mu=0$, which means that $a=0$ in (19).

If non-negative sequences $\{r_{t}\}_{t\geq 0},\{e_{t}\}_{t\geq 0}$ satisfy (19) with $a=0,b~{}>~{}0,c,A,B~{}\geq~{}0$, then there exists a constant stepsize $\eta_{t}=\eta<\frac{1}{d}$ such that for weights $\{w_{t}=1\}_{t\geq 0}$ it holds that:

With $a=0$, constant stepsizes $\eta_{t}=\eta$ and weights $\{w_{t}=1\}_{t\geq 0}$ (19) is equivalent to

To conclude the proof we tune the stepsize using Lemma 17. ∎

For any parameters $r_{0}\geq 0,b\geq 0,e\geq 0,d\geq 0$ there exists constant stepsize $\eta\leq\frac{1}{d}$ such that

Choosing $\eta=\min\left\{\left(\frac{r_{0}}{b(T+1)}\right)^{\frac{1}{2}},\left(\frac{r_{0}}{e(T+1)}\right)^{\frac{1}{3}},\frac{1}{d}\right\}\leq\frac{1}{d}$ we have three cases

$\eta=\frac{1}{d}$ and is smaller than both $\left(\frac{r_{0}}{b(T+1)}\right)^{\frac{1}{2}}$ and $\left(\frac{r_{0}}{e(T+1)}\right)^{\frac{1}{3}}$, then

$\eta=\left(\frac{r_{0}}{b(T+1)}\right)^{\frac{1}{2}}<\left(\frac{r_{0}}{e(T+1)}\right)^{\frac{1}{3}}$, then

The last case, $\eta=\left(\frac{r_{0}}{e(T+1)}\right)^{\frac{1}{3}}<\left(\frac{r_{0}}{b(T+1)}\right)^{\frac{1}{2}}$

Appendix E Lower Bound

We assume that the starting point $\mathbf{x}^{(0)}$ is an eigenvector of $W$, corresponding to the second largest eigenvalue, i.e. $W\mathbf{x}^{(0)}=\lambda_{2}\mathbf{x}^{(0)}$ and we set $y_{i}$ such that $\mathbf{y}=\mathbf{1}+\mathbf{x}^{(0)}$. With this choice of $\mathbf{y}$, $\bar{\zeta}^{2}=\left\lVert\mathbf{x}^{(0)}\right\rVert_{2}^{2}$. It will be also useful to note that the average $\bar{\mathbf{x}}^{(0)}=\mathbf{0}$ since it is orthogonal to $\mathbf{1}$, the eigenvector of $W$ corresponding to the largest eigenvalue. We use the notation $\bar{\mathbf{z}}:=\frac{1}{n}\mathbf{1}\mathbf{1}^{\top}\mathbf{z}$.

We start the proof by decomposing the error $\frac{1}{n}\left\lVert\mathbf{x}^{(t)}-\bar{\mathbf{y}}\right\rVert^{2}_{2}$ on consensus and optimization terms

Using that for our chosen functions $\nabla f(\mathbf{x})=\mathbf{x}-\mathbf{y}$, we can estimate the optimization term as

In order to guarantee error less than $\epsilon$, it is necessary to have simultaneously both optimization and consensus terms less than $\epsilon$, therefore it is required that

Note that $\lambda_{2}=\sqrt{1-p}$, where $p$ is from Assumption 4. Using that $\sqrt{1-p}\geq 1-p$ for $p\in$,

And therefore using that $\sqrt{1-p}\leq 1$ and for $\epsilon\leq\frac{\bar{\zeta}^{2}(1-p)}{16}$,

With this upper bound on $\eta$, the inequality (32) gives a lower bound on $t$:

here we used that $\log(1-\eta)\geq-\eta$ for $\eta\leq\frac{4}{5}$. ∎

In Theorem 2 we proved an upper bound and in Theorem 3 we proved a lower bound, that indicates that in the noiseless ($\bar{\sigma}^{2}=0$) strongly convex case the convergence is not linear when $\bar{\zeta}^{2}>0$. In this section we verify numerically that this rate indeed reflects tightly the convergence behavior of decentralized SGD.

We consider the same setting as in Section 8 before, with $\bar{\sigma}^{2}=0$, $\bar{\zeta}^{2}=10$, $n=25$, and $d=10$.

For both ring and 2-$d$ torus (grid), we vary the target accuracy ($\epsilon$) and tune the stepsize to find the smallest number of iterations required ($T_{\epsilon}$) to achieve this target accuracy. In Figure 3 we depict the results, where x-axis is $\frac{1}{\sqrt{\epsilon}}$ and y-axis is $T_{\epsilon}$. Based on the Theorem 2 for strongly convex case, ideally each of them should be a line, as we observe in the plots. Moreover, the ratio of the slopes of these lines is $30.2/2.3=13.13$ which matches the ratio of the spectral gap of these graphs ($p_{\rm grid}/p_{\rm ring}=0.276/0.021=13.142$), as it is shown in Theorems 2 and 3.