Communication trade-offs for synchronized distributed SGD with large step size

Introduction

where $(\eta_{t})_{t\geq 0}$ is a deterministic sequence of positive scalars, referred to as the learning rate and $\boldsymbol{g}_{t}(\boldsymbol{v}_{t-1})$ is an oracle on the gradient of the function $F$ at $\boldsymbol{v}_{t-1}$. We focus on objective functions that are both smooth and strongly convex (Bach and Moulines, 2011). While these assumptions might be restrictive in practice, they enable to provide a tight analysis of the error of SGD. In such a setting, two types of proofs have been used traditionally. On one hand, Lyapunov-type proofs rely on controlling the expected squared distance to the optimal point (Zhao and Zhang, 2015). Such analysis suggests using small decaying steps, inversely proportional to the number of iterations ($t^{-1}$). On the other hand, studying the recursion as a stochastic process (Polyak and Juditsky, 1992) enables to better capture the reduction of the noise through averaging. It results in optimal convergence rates for larger steps, typically scaling as $t^{-\alpha}$, $\alpha\in(1/2,1)$ (Bach and Moulines, 2011).

Over the past decade, the amount of available data has steadily increased: to adapt SGD to such situations, it has become necessary to distribute the workload between several machines, also referred to as workers (Delalleau and Bengio, 2007; Zinkevich et al., 2010; Recht et al., 2011). For SGD, two extreme approaches have received attention: 1) workers run SGD independently and at the end aggregate their results, called one-shot averaging (OSA) (Zinkevich et al., 2010; Godichon and Saadane, 2017) or parameter mixing, and 2) mini-batch averaging (MBA) (Dekel et al., 2012a; Takáč et al., 2013; Li et al., 2014c; Goyal et al., 2017; Jain et al., 2016), where workers communicate after every iteration: all gradients are thus computed at the same support point (iterate) and the algorithm is equivalent to using mini-batches of size $P$, with $P$ the number of workers. While OSA requires only a single communication step, it typically does not perform very well in practice (Zhang et al., 2016). At the other extreme, MBA performs better in practice, but the number of communications equals the number of steps, which is a major burden, as communication is highly time consuming (Zhang et al., 2016). To optimize this computation-communication-convergence trade-off, we consider the Local-SGD framework: $P$ workers run SGD iterations in parallel and communicate periodically. This framework encompasses one-shot averaging and mini-batch averaging as special cases (see Figure 1).

We make the following contributions: 1) We provide the first non-asymptotic analysis for local-SGD with large step sizes (typically scaling as $t^{-\alpha}$, for $\alpha\in(1/2;1)$), in both on-line and finite horizon settings. Our assumptions encompass the ubiquitous least-squares regression and logistic regression. 2) Our comparison of the two extreme cases, OSA and MBA, underlines the communication trade-offs. While both of these algorithms are asymptotically equivalent for a fixed number of machines, mini-batch theoretically outperforms one-shot averaging when we consider the precise bias-variance split. In the regime where both the number of machines and gradients grow simultaneously we show that mini-batch SGD outperforms one-shot averaging. 3) Under three different sets of assumptions, we quantify the frequency of communication necessary for Local SGD to be optimal (i.e., as good as mini-batch). Precisely, we show that the communication frequency can be reduced by as much as O\Big{(}\frac{\sqrt{T}}{P^{3/2}}\Big{)}, with $T$ gradients and $P$ workers. Moreover, our bounds suggest an adaptive communication frequency for logistic regression, which depending on the expected distance to the optimal point (a phenomenon observed by Zhang et al. (2016)). 4) We support our analysis by experiments illustrating the behavior of the algorithms.

The paper is organized as follows: in Section 2, we introduce the general setting, notations and algorithms, then in Section 2.2, we describe the related literature. Next, in Section 2.3, we describe assumptions made on the objective function. In Section 3, we provide our main results, their interpretation, consequence and comparison with other results. Results in the on-line setting and experiments are presented in the Section 4 and Appendix A.

Algorithms and setting

We consider $P$ machines, each of them running SGD. Periodically, workers aggregate (i.e., average) their models and restart from the resulting model. We denote by $C$ the number of communication steps. We define a phase as the time between two communication rounds. At phase $t\in[C]$, for any worker $p\in[P]$, we perform $N^{t}$ local steps of SGD. Iterations are thus naturally indexed by $(t,k)\in[C]\times[N^{t}]$. We consider the lexicographic order $\preccurlyeq$ on such pairs, which matches the order in which iterations are processed. Note that we assume the number of local steps is the same over all machines $p$. While this assumption can be relaxed in practice, is facilitates our proof technique and notation. At any $k\in[N^{t}]$, we denote by $\boldsymbol{w}_{p,k}^{t}$ the model proposed by worker $p$, at phase $t$, after $k$ local iterations. All machines initially start from the same point $\boldsymbol{w}_{0}$, that is for any $p\in[P]$, $\boldsymbol{w}_{p,0}^{1}=\boldsymbol{w}_{0}$. The update rule is thus the following, for any $p\in[P],t\in[C],k\in[N^{t}]$:

Aggregation steps consist in averaging the final local iterates of a phase: for any $t\in[C]$, $\hat{\boldsymbol{w}}^{t}=\frac{1}{P}\sum_{p=1}^{P}\boldsymbol{w}_{p,N^{t}}^{t}.$ At phase $t+1$, every worker $p\in[P]$ restarts from the averaged model: $\boldsymbol{w}_{p,0}^{t+1}:=\hat{\boldsymbol{w}}^{t}$. Eventually, we are interested in controlling the excess risk of the Polyak-Ruppert averaged iterate:

with $\overline{\boldsymbol{w}}^{t}=\frac{1}{PN^{t}}\sum_{k=1}^{N^{t}}\sum_{p=1}^{P}\boldsymbol{w}_{p,k}^{t}$. We use the notation $\overline{\boldsymbol{w}}$ to underline the fact that iterates are averaged over one phase and $\overline{\overline{\boldsymbol{w}}}$ when averaging is made over all iterations. All averaged iterates can be computed on-line.

The algorithm, called local-SGD, is thus parameterized by the number of machines $P$, communication steps $C$, local iterations $(N^{t})_{t\in[C]}$, the starting point $\boldsymbol{w}_{0}$, the learning rate $(\eta^{t}_{k})_{(t,k)\in[C]\times[N^{t}]}$, and the first order oracle on the gradient. Pseudo-code of the algorithm is given in Table 2.

Link with classical algorithms. Special cases of Local-SGD correspond to one-shot averaging or mini-batch averaging, as summarized in Table 2. More precisely, for a total number of gradients $T$, with $P$ workers, $C=T/P$ communication rounds, and $(N^{t})_{t\in[C]}=(1,.\dots,1)$, we realize an instance of P-mini-batch averaging (P-MBA). On the other hand, with $P$ workers, $C=1$ communication, and $(N^{1})=T/P$, we realize an instance of one shot-averaging. Our goal is to get general convergence bounds for Local-SGD that recover classical bounds for both these settings when we choose the correct parameters. While comparing to Serial-SGD (which is also a particular case of the algorithm), would also be interesting, we focus here on the comparison between Local-SGD, one-shot averaging and mini-batch averaging. Indeed, the step size is generally increased for mini-batch with respect to Serial SGD, and the running efficiency of algorithms is harder to compare: we only focus on different algorithms that use the same number of machines.

2 Related Work

For quadratic functions, larger steps can be used, as pointed by Bach and Moulines (2013). Indeed, even with non-decaying step size, the averaged process converges to the optimal point. Several studies focus on understanding properties of SGD for quadratic functions: a detailed non-asymptotic analysis is provided by Défossez and Bach (2015), acceleration under the additive noise oracle (see Assumption 4 below) is studied by Dieuleveut et al. (2016) (without this assumption by Jain et al. (2017)), and Jain et al. (2016) analyze the effects of mini-batch and tail averaging.

Mini-batch averaging. Mini-batch averaging has been studied by Dekel et al. (2012a); Takáč et al. (2013). These papers show an improvement in the variance of the process, and make comparisons to SGD. It has been found that increasing the mini-batch size often leads to increasing generalization errors, which limits their distributivity (Li et al., 2014d). Jain et al. (2016) have provided upper bounds on learning-rate and mini-batch size for optimal performance. Recently, large mini-batches have been leveraged successfully in deep learning as in (Shirish Keskar et al., 2016; You et al., 2017; Goyal et al., 2017) by properly tuning learning rates, etc.

Local-SGD. Zhang et al. (2016) empirically show that local SGD performs well. They also provide a theoretical guarantee on the variance of the process, however, they assume the variance of the estimated gradients to be uniformly upper bounded (Assumption 4 below). Such an assumption is restrictive in practice, for example it is not satisfied for least squares regression. In a simultaneous work, Stich (2018) has provided an analysis for local-SGD. The limitation with their analysis is that they also assume bounded gradients and use a small step size scaling as $\frac{c}{\mu t}$. More importantly, their analysis doesn’t extend to the extreme case of one-shot averaging like ours. Lin et al. (2018) have experimentally shown that Local-SGD is better than the synchronous mini-batch techniques, in terms of overcoming the large communication bottleneck. Recently, Yu et al. (2018) have given convergence rates for the non-convex synchronous and a stale synchronous settings.

We have summarized the major limitations of some of these analyses in Table S3, given in Appendix H. Our motivation is to get away with some of these restrictive assumptions, and provide tight upper bounds for the above three averaging schemes. In the following section, we present the set of assumptions under which our analysis is conducted.

3 Assumptions

The function $F$ is strongly-convex with convexity constant $\mu>0$.

If Q 1 is satisfied, then Assumptions 1, 2 are satisfied, and $L$ and $\mu$ are respectively the largest and smallest eigenvalues of $\Sigma$. At any iteration $(t,k)\in[C]\times[N^{t}]$, any machine can query an unbiased estimator of the gradient $g_{p,k}^{t}(\boldsymbol{w})$ at a point $\boldsymbol{w}$. Formally, we make the following assumption:

A filtration is an increasing (i.e., for all $(t,k)\preccurlyeq(t^{\prime},k^{\prime})$, $\mathcal{H}_{k}^{t}\subset\mathcal{H}_{k^{\prime}}^{t^{\prime}}$), sequence of $\sigma$-algebras. 3 expresses that we have access to an i.i.d. sequence $(g^{t}_{p,k})_{(t,k)\in[C]\times[N^{t}]}$ of unbiased estimators of $F^{\prime}$. Remark that with such notations, for any $t\in[C],k\in[N^{t}],p\in[P]$, $\boldsymbol{w}_{p,k}^{t}$ is $\mathcal{H}_{k}^{t}$-measurable. In Proposition 3.3, we make the additional, stronger assumption that the variance of gradient estimates is uniformly upper bounded, a standard assumption in the SGD literature, see e.g. Zhang et al. (2016):

Assumption 4 is for example true if the sequence of random vectors $(g^{t}_{p,k+1}(\boldsymbol{w}_{p,k}^{t})-F^{\prime}(\boldsymbol{w}_{p,k}^{t}))_{t\in[C],k\in[N^{t}],p\in[P]}$ is i.i.d.. This setting is referred to as the semi-stochastic setting in Dieuleveut et al. (2016).

We also consider the following conditions on the regularity of the gradients, for $p\geq 2$:

Almost sure $L$-co-coercivity (Zhu and Marcotte, 1996) is for example satisfied if for any $(p,k)\in[P]\times[N^{t}]$, there exist a random function $f^{t}_{p,k}$ such that $g^{t}_{p,k}=(f^{t}_{p,k})^{\prime}$ and which is a.s. convex and $L$-smooth. Finally, we assume the fourth order moment of the random gradients at $\boldsymbol{w}^{\star}$ to be well defined:

It must be noted that 6 is a much weaker assumption than 4, for e.g., least-square regression satisfies former but not latter. Most of these assumptions are classical in machine learning. SGD for least squares regression satisfies Q 1, 3, 5 and 6. On the other hand, SGD for logistic regression satisfies 1, 2, 3 and 4. Our main result Theorem 3.6 (lower bounding the frequency of communications) applies to both these sets of assumptions. In Section B.3 we further detail how these assumptions apply in machine learning.

Though both of these approaches are often considered to be nearly equivalent (Bach, 2014; Dieuleveut and Bach, 2016), fundamental differences exist in their convergence properties. The on-line case is harder to analyze, but ultimately provides a better convergence rate. However as the behavior is easier to interpret in the finite horizon case, we postpone results for on-line setting to Section 4.

Moreover, we always assume that for any $t\in[C],k\in[N^{t}]$, the learning rate satisfies $2\eta_{k}^{t}L\leq 1$. In the following section, we present our main results.

Main Results

Sketch of the proof. We follow the approach by Polyak and Juditsky, which relies on the following decomposition: for any $p\in[P],t\in[C],k\in[N^{t}]$, Equation (2) is trivially equivalent to:

We have used a first order Taylor expansion around the optimal value $\boldsymbol{w}^{\star}$ of the gradient. Thus, using the definition of $\overline{\overline{\boldsymbol{w}}}^{C}$:

We first compare the results for Mini-batch averaging and One-shot averaging for finite horizon (FH) setting, and then provide these results for local-SGD.

First we assume the step size $\eta_{k}^{t}$ to be a constant $\eta$ at every iteration for any $(t,k)\in[C]\times[N^{t}]$. Our first contribution is to provide non-asymptotic convergence rates for mini-batch SGD and one shot averaging, that allow a simple comparison. For the benefit of presentation, we define following quantities:

We have the following result for mini-batch averaging:

Under Assumptions 1, 2, 3, 5, 6, we have the following bound for mini-batch SGD: for any $t\in[C]$,

The notation $\precsim$ denotes inequality up to an absolute constant. Recall that for mini-batch, the total number of gradients processed is $T=PC$.

On the other hand, we also have the following result for one-shot averaging:

Under Assumptions 1, 2, 3, 5, 6, we have the following bound for one shot averaging: $p\in[P],t=1,k\in[N]$,

Note that for one-shot averaging, the total number of gradients used is $T=PN$.

Interpretation, fixed $P$. Using mini-batch naturally reduces the variance of the process $(\boldsymbol{w}_{p,k}^{t})_{p\in[P],t\in[C],k\in[N^{t}]}$. Equations 4 and 6 show that the speed at which the initial condition is forgotten remains the same, but that the variance of the local process is reduced by a factor $P$.

Equations 5 and 7 show that the convergence depends on an initial condition term and a variance term. For a fixed number of machines $P$, and a step size scaling as $\eta=X^{-\alpha}$, $0.5<\alpha<1$, $X\in\{N,C\}$, the speed at which the initial condition is forgotten is asymptotically dictated by $Q_{bias}/(\eta X)^{2}$ where $X\in\{N,C\}$, for both algorithms (if we use the same number of gradients for both algorithms, naturally, $N=C$.) As for the variance term, it scales as $\sigma^{2}T^{-1}$ as $T\to\infty$ , as the remaining terms $Q_{var}(X)$ asymptotically vanish for $\eta=X^{-\alpha}$. It reduces with the total number $T$ of gradients used in the process. Interestingly, this term is the same for the two extreme cases (MBA and OSA): it does not depend on the number of communication rounds. This phenomenon is often described as “the noise is the noise and SGD doesn’t care” (for asynchronous SGD, (Duchi et al., 2015)). Though we recover this asymptotic equivalence here, our belief is that this asymptotic point of view is typically misleading as the asymptotic regime is not always reached, and the residual terms do then matter.

Indeed, the lower order terms do have a dependence on the number of communication rounds: when the number of communications increases, the overall effect of the noise is reduced. More precisely, since $Q_{var}(N)=Q_{var}(C)$ the remaining terms are respectively $P$ or $P^{2}$ times smaller for mini-batch. This provides a theoretical explanation of why mini-batch SGD outperforms one shot averaging in practice. It also highlights the weakness of an asymptotic analysis: the dominant term might be equivalent, without reflecting the actual behavior of the algorithm. Disregarding communication aspects, mini-batch SGD is in that sense optimal.

Note that for quadratic functions, $Q_{2,var}=0$ as $M=0$. The conditions on the step size can thus be relaxed, and the asymptotic rates described above would be valid for any step size satisfying $\eta\leq\mu$ (Jain et al., 2016).

Extension to the on-line setting, eventually leading to a better convergence rate, is given in Proposition 4.1 in Section 4.

Interpretation, $P,T\to\infty$. When both the total number of gradients used $T$ and the number of machines $P$ are allowed to grow simultaneously, the asymptotic regime is not necessarily the same for MBA and OSA, as remaining terms are not always negligible. For example, if fixing $\eta=X^{-2/3}$, $X\in\{N,C\}$ (we chose $\alpha=2/3$ to balance $Q_{1,var}$ and $Q_{2,var}$), the variance term would be controlled by $\sigma^{2}T^{-1}(1+\frac{P}{\mu C^{1/3}})$. Thus, unless $P\leq\mu{C^{1/3}}$, MBA could outperform OSA by a factor as large as $P$.

Novelty and proofs. Both Propositions 3.1 and 3.2 are proved in the Appendix F. Importantly, Equations 4 and 6 respectively imply Equations 5 and 7 under the stated conditions: this is the reason why we only focus on proving equations similar to Equations 4 and 6 for Local-SGD.

Proposition 3.1 is similar to the analysis of Serial-SGD for large step size, but with a reduction in the variance proportional to the number of machines. Such a result is derived from the analysis by Dieuleveut et al. (2017), combining the approach of Bach and Moulines (2013) with the correct upper bound for smooth strongly convex SGD (Needell et al., 2014), and controlling similarly higher order moments. While this result is expected, we have not found it under such a simple form in the literature. Proposition 3.2 follows a similar approach, we combine the proof for mini-batch with a control of the iterates of each of the machines. This is closely related to Godichon and Saadane (2017), but we preserve a non-asymptotic approach.

Remark: link with convergence in function values. We mainly focus on proving convergence results on the Mahalanobis distance $\|F^{\prime\prime}(\boldsymbol{w}^{\star})(\overline{\overline{\boldsymbol{w}}}^{C}-\boldsymbol{w}^{\star})\|^{2}$, which is the natural quantity in such a setting (Bach and Moulines, 2011, 2013; Godichon and Saadane, 2017). These results could be translated into function value convergence $F(\overline{\overline{\boldsymbol{w}}}^{C})-F(\boldsymbol{w}^{\star})$, using the inequality $F(\overline{\overline{\boldsymbol{w}}}^{C})-F(\boldsymbol{w}^{\star})\leq L\mu^{-2}\|F^{\prime\prime}(\boldsymbol{w}^{\star})(\overline{\overline{\boldsymbol{w}}}^{C}-\boldsymbol{w}^{\star})\|^{2}$ but the dependence on $\mu$ would be pessimistic and sub-optimal. However, a similar approach has been used by Bach (2014), under a slightly different set of assumptions (including self-concordance, e.g., for logistic regression), recovering optimal rates. Extension to such a set of assumptions, which relies on tracking other quantities, is an important direction.

While the “classical proof”, which provides rates for function values directly (with smoothness, or with uniformly bounded gradients) has a better dependence on $\mu$, one cannot easily obtain a noise reduction when averaging between machines. Similarly, there is no proof showing that one-shot averaging is asymptotically optimal that relies only on function values. In other words, these proofs do not adequately capture the noise reduction due to averaging. Moreover, such proof techniques relying on function values typically involve a small step size $1/(\mu t)$ (because the noise reduction is captured inefficiently). Such step size performs poorly in practice (initial condition is forgotten slowly), and $\mu$ is unknown.

In conclusion, though they do not directly result in optimal dependence on $\mu$ for function values, we believe our approach allows to correctly capture the effect of the noise, and is thus suitable for capturing the effect of local SGD.

Conclusion: for a fixed or limited number of machines, asymptotically, the convergence rate is similar for OSA and MBA. However, non-asymptotically, or when the number of machines also increases, the dominant terms can be as much as $P^{2}$ times smaller for MBA. In the following we provide conditions for Local-SGD to perform as well as MBA (while requiring much fewer communication rounds).

2 Convergence of Local-SGD, FH setting

For local-SGD we first consider the case of a quadratic function, under the assumption that the noise has a uniformly upper bounded variance. While this set of assumptions is not realistic, it allows an intuitive presentation of the results. Similar results for settings encompassing LSR and LR follow. We provide a bound on the moment of an iterate after the communication step $\hat{\boldsymbol{w}}^{t}$ (i.e., the restart point of the next phase), and on the second order moment of any iterate.

For $t\in[C]$, we denote $\boldsymbol{N}_{1}^{t}:=\sum_{t^{\prime}=1}^{t}N^{t^{\prime}}$.

Under Assumptions Q 1, 3, 4, we have the following bound for Local-SGD: for any $p\in[P],t\in[C],k\in[N^{t}]$,

To prove such a result, we use the classical technique, and introduce a ghost sequence $\breve{\boldsymbol{w}}_{k}^{t}:=\frac{1}{P}\sum_{p=1}^{P}\boldsymbol{w}_{p,k}^{t}$, and recursively control $\left\|\breve{\boldsymbol{w}}_{k}^{t}-\boldsymbol{w}^{\star}\right\|^{2}$. We conclude by remarking that $\breve{\boldsymbol{w}}_{N^{t}}^{t}=\hat{\boldsymbol{w}}^{t}$. This proof is given in Section C.2.

Interpretation. The variance bound for the iterates after communication, $\hat{w}^{t}$ exactly behaves as in mini-batch case: the initialization term decays linearly with the number of local steps, and the variance is reduced proportionally to the number of workers $P$. On the other hand, the bound on the iterates $\boldsymbol{w}_{p,k}^{t}$ shows that the variance of this process is composed of a “long term” reduced variance, that accumulates through phases, and is increasingly converging to $\frac{\sigma^{2}_{\infty}\eta}{P\mu}$ and of an extra variance $\eta\sigma^{2}_{\infty}\frac{1-(1-\eta\mu)^{k}}{\mu}$, that increases within the phase, and is upper bounded by $\sigma^{2}_{\infty}\eta^{2}k$.

In the case of constant step size, the iterates of serial SGD converge to a limit distribution $\pi_{\eta}$ that depends on the step size (Dieuleveut et al., 2017). Here, the iterates after communication (or the mini-batch iterates) converge to a distribution with reduced variance $\pi_{\eta/P}$, thus local iterates periodically restart from a distribution with reduced variance, then slowly “diverge” to the distribution with large variance. If the number of local iterations is small enough, the iterates keep a reduced variance. More precisely, we have the following result.

If for all $t\in[C]$, $N^{t}\leq\frac{1}{\mu\eta P}$, then the second order moment of $\boldsymbol{w}_{p,k}^{t}$ admits the same upper bound as the mini-batch iterate $\hat{\boldsymbol{w}}_{MB}^{\boldsymbol{N}_{1}^{t-1}+k}$ (Equation (4)) up to a constant factor of 2. As a consequence, Equation (5) is still valid, and Local-SGD performs optimally.

Interpretation. This result shows that if the algorithm communicates often enough, the convergence of the Polyak Ruppert iterate $\overline{\overline{\boldsymbol{w}}}^{C}$ is as good as in the mini-batch case, thus it is “optimal”. Moreover, the minimal number of communication rounds is easy to define: the maximal number of local steps $N^{t}$ decays as the number of workers and the step size increases. This bound implies that more communication steps are necessary when more machines are used. Note that $(\eta P)^{-1}$ is a large number, as a typical value for $\eta$ is inversely proportional to (a power of) the number of local steps for e.g., $(\sum_{t^{\prime}=1}^{t}N^{t^{\prime}})^{-\alpha}$, $\alpha\in(1/2;1)$.

With constant number of local steps $N^{t}=N$, and learning rate $\eta=\frac{c}{\sqrt{NC}}$ in order to obtain an optimal $O(\frac{\sigma^{2}}{T})$ parallel convergence rate, local-SGD communicates $O(\frac{\sqrt{NC}}{P\mu})$ times less as compared to mini-batch averaging.

We believe that this is the first result (with Stich (2018)) that shows a communication reduction proportional to a power of the number of local steps of a local solver (i.e., $O({\sqrt{NC}})$), compared to mini-batch averaging.

In the following, we alternatively relax the bounded variance assumption 4 and the quadratic assumption Q 1, and show similar results for local SGD. This allows us to successively cover the cases of least squares regression (LSR) and logistic regression (LR).

Under either of the following sets of assumptions, the convergence of the Polyak Ruppert iterate $\overline{\overline{\boldsymbol{w}}}^{C}$ is as good as in the mini-batch case, up to a constant:

Assume Q 1, 3, 5, 6, and for any $t\in[C]$, $N^{t}\leq\frac{1}{\mu\eta P}$ and $\mu\eta^{2}\boldsymbol{N}_{1}^{t}=O(1)$.

These results are derived from Proposition S9 and Proposition S13 which generalize Proposition 3.3. Those results are proved in Appendix C and D and constitute the main technical challenge of the paper.

Interpretation. We note that in both of these situations, the optimal rates can be achieved if the communications happen often enough, and beyond such a number of communication rounds, there is no substantial improvement in the convergence. This result corresponds to the effect observed in practice (Zhang et al., 2016). The first set of assumption is valid for LSR, the second for LR. In the first case, the maximal number of local steps before communication is upper bounded by the same ratio as in Corollary 3.4, but the “constant” that appears is $\exp(\mu\eta^{2}\boldsymbol{N}_{1}^{t})$, so we need this quantity to be small (which is typically always satisfied in practice) in order to be optimal w.r.t. mini-batch averaging. A similar result as Example 3.5 can be provided reducing the communication by a factor of $O(\frac{\sqrt{NC}}{P\mu})$.

Main results: On-line Setting

In the on-line setting we consider the particular case of a decaying sequence $\eta^{t}_{k}=(\sum_{t^{\prime}=1}^{t-1}N^{t^{\prime}}+k)^{-\alpha}$, for some $\alpha\in(\frac{1}{2},1)$. The analysis is slightly more involved as Equation 3 results in more terms than in the finite horizon setting (sums do not directly telescope). While the decaying step-size case enables to improve some terms with respect to the finite horizon case (e.g. the speed at which one forgets the initial condition), the trade-offs concerning communication remain unchanged. We define the following constants to make the presentation clear, for $\alpha\in(1/2;1)$:

Now we present a result similar to Proposition 3.1 for mini-batch averaging and one shot averaging:

Under the Assumptions 1, 2, 3, 5, 6 using $\eta^{t}_{k}=(\sum_{t^{\prime}=1}^{t-1}N^{t^{\prime}}+k)^{-\alpha}$ we have for respectively mini-batch averaging and one-shot averaging:

with respectively $\kappa=1$ and $X=N$ for one-shot averaging, and $\kappa=P$ and $X=C$ for mini-batch averaging.

This proposition is directly derived from Lemma S15 in Appendix G. This proposition is similar to Propositions 3.1 and 3.2, but the overall convergence rate is better as using decaying step size eventually performs better. For example, the bias term mainly decays as $1/X^{2}$ instead of $1/(\eta X)^{2}$. This underlines why in practice decaying step size is often preferable. Asymptotically, the variance term is now dominant, and as before, MBA and OSA have similar performance as $\sigma^{2}T^{-1}$.

For a fixed number of machine $P$, the bias is asymptotically vanishing, and if we ignore the linearly decaying terms and the dependence on $\mu$, the resulting dominating term in $R_{1,2,var}$ is controlled by $X^{-\min\{(1-\alpha),\alpha,2\alpha-1\}}$, which would result in an optimal choice of $\alpha=2/3$.

In the non asymptotic regime, where the total number of iterations and $P$ grow simultaneously, the variance of OSA scales as $T^{-1}$ as long as $PX^{-\min\{(1-\alpha),\alpha,2\alpha-1\}}=O(1)$. In other words, for $\alpha=2/3$, we need $P\leq X^{1/3}$: the number of machines as to be smaller than the number of iterations to the power $1/3$, in other words, for 1000 iterations, one could only use 10 machines to reach the asymptotic regime where OSA performs similarly to MBA.

Conclusion

Stochastic approximation and distributed optimization are both very densely studied research areas. However, in practice most distributed applications stick to bulk synchronous mini-batch SGD. While the algorithm has desirable convergence properties, it suffers from a huge communication bottleneck. In this paper we have analyzed a natural generalization of mini-batch averaging, Local SGD. Our analysis is non-asymptotic, which helps us to better understand the exact communication trade-offs. We give feasible lower bounds on communication frequency which significantly reduce the need for communication, while providing similar non-asymptotic convergence as mini-batch averaging. Our results apply to common loss functions, and use large step sizes. Further, our analysis unifies and extends all the scattered results for one-shot averaging, mini-batch averaging and local SGD, providing an intuitive understanding of their behavior.

Some important future directions are obtaining lower bounds, studying observable quantities to predict an adaptive communication frequency and relaxing some of the technical assumptions required by the analysis. The on-line case, experiments, proofs, additional materials and a review of distributed optimization follow in the appendix.

Acknowledgments

We thank Martin Jaggi, Sebastian Stichs, and Sai Praneeth Reddy for helpful discussions.

References

Appendix A Experimental results

We perform experiments for three different data-sets\hrefhttps://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/https://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/, two for least-squares regression and one for logistic regression Table S1. For all the curves we use $\log(y)$ v/s $\log(x)$ plots unless explicitly mentioned. Moreover, to elucidate the theory we use the same learning rates for all the algorithms in an experiment. The number of workers is set to $P=32$ every where, and plots are labeled w.r.t. the number of local steps $N$ which we don’t change along the different phases. We do the following experiments:

Performance of local SGD with different number of local steps spanning OSA to MBA (Figure S1). We globally find MBA to perform the best. Besides, as we increase the number of local steps $N$ the performance gets closer to OSA. This observation aligns with our theoretical guarantees. We use the averaged iterate (i.e., $\overline{\overline{\boldsymbol{w}}}$, the average over all the iterates till that point) for reporting the performance. The current iterate (i.e., $\breve{\boldsymbol{w}}^{t}_{k}$, the ghost iterate for the current iteration) is omitted as the graphs are too noisy to be interpreted, and a variance of the loss is used instead.

Performance of local SGD with different number of local steps when started at the optimal point (Figure S2). We expect that if we start at $\boldsymbol{w}^{\star}$ then the bias term goes to zero and the difference between the algorithms becomes sharper. This is because our results predict that for constant learning rate, the initial conditions are forgotten at the same rate. We see that mini-batch outperforms OSA no the first iterations, but not asymptotically.

Variance of the estimators, for loss (Figure S3) and iterate values (Figure S4). We expect that a larger mini-batch size predicts a lower variance for these cases, and we observe the same through our experiments. In fact, the mean squared error of the parameters at the optimal is observed to be following a periodic curve. The value on an individual worker rises until it communicates, but always remains lower than a single SGD process run for the same number of iterations. This, verifies our theory and results for iterate convergence. Moreover, the variance at the loss function follows a similar pattern which elucidates the fact the intuitions developed in the paper also hold for functional convergence.

Appendix B Some Additional Material

Pseudo codes of both algorithms are given in Figure S7.

B.2 Summary of Results

In the table below, we specify for which algorithm our results apply (mini batch, one shot, or local SGD), under which assumptions they are proved and if they apply to the on-line setting(OL) or just the finite horizon(FH) case.

B.3 Example: Learning from i.i.d. observations

Stochastic Approximation: We use independent observations at each iteration. The total number of iterations is thus at most the number of observations we access. SGD then corresponds to following the gradient of the loss $f_{k}$ on a single independent observation $(X_{k},Y_{k})$. As the gradients we use are then unbiased gradients of the generalization error, this means that SGD directly minimizes this (unknown) function.

In practice, this means that in the first situation, we want to optimize the precision of the algorithm for a limited number of oracle calls, while in the second situation one would rather optimize the number of outer iterations of the algorithm (i.e. its running time). In both these assumptions, Assumption 3 is satisfied for the filtration generated by all the observations before time $(t,k)$ (respectively all the indices sampled before time $(t,k)$).

Then, Assumption 5 and 6 are satisfied, if $X$ is bounded and $Y$ has finite variance.

SGD for least squares regression typically satisfies Q 1, 3, 5 and 6. On the other hand, SGD for logistic regression satisfies 1, 2, 3 and 4.

Appendix C Convergence guaranties for the second order moment.

In this section, we prove several Lemmas that allow to control the second order moment for the iterate. We first recall a few useful inequalities that will be used in the following. See for example Nesterov (2004).

We first recall the proof of the convergence for inner iterates. This proof corresponds to what happens on one machine, and can be found in the literature Bach and Moulines (2011); Dieuleveut et al. (2017) for example.

For any $p\in[P],t\in[C],k\in[N^{t}]$, under Assumptions 1, 2, 3, 5, 6, we have

Using the second equation recursively results in:

More precisely, for precise reference in the following proofs, we referenced this inequality with the following specific cases:

Under Assumptions 1, 2, 3, 5, 6, for mini-batch SGD with batch-size $P$ and step-size $\eta$ we have,

Such a result on reduced variance for mini-batch SGD ($\frac{\sigma^{2}}{P}$) can be found in many previous works like Dekel et al. (2012b). Since mini-batch SGD is trivial to parallelize, this result also holds for the averaged iterate for outer iteration $t$ while using mini-batch averaging. Similarly, for decaying step sizes,

Similarly, in the case of one-shot averaging,

Under Assumptions 1, 2, 3, 5, 6 and a constant step-size $\eta$ using one-shot averaging, for any $K\in[N^{1}]$ and $i\in[P]$ we have,

C.2 Proof of Proposition 3.3

In this Section we prove Proposition 3.3. In order to provide a bound on the mean squared distance to the optimum of the outer iterates, we introduce a ghost sequence Mania et al. (2015), i.e., a sequence of iterates which is not actually computed. For any $t\in[C],k\in[N^{t}]$, we define

Under Assumptions Q 1, 3 and 4, for any $t\in[C],K\in[N^{t}]$, we have:

Remarking that for any $t\in[C]$, $\breve{\boldsymbol{w}}^{t}_{N^{t}}=\hat{\boldsymbol{w}}^{t}$ this implies the first inequality of Proposition 3.3. Note that this Lemma is valid for both decaying steps and and a constant learning rate. Especially, for a constant step size $\eta$, and $K=N^{t}$:

Under Assumptions Q 1, 3 and 4, for any $T\in[C]$, we have:

By induction, Lemma S5 implies that for any $T\in[C]$

To prove the second inequality of Proposition 3.3, we combine Lemma S5 and Equation (S5), using the fact that $\boldsymbol{w}_{p,0}^{t}=\hat{\boldsymbol{w}}^{t-1}$.

This results means that for a quadratic function with gradients having uniformly bounded variance, the outer iteration decay is the same as for mini-batch iterations (but for mini-batch, it is true under the weaker set of Assumptions 1, 2, 3, 5, 6).

By definition of $\breve{\boldsymbol{w}}_{k}^{t}$, we have for any $t\in[C],k\in[N^{t}]$, using the linearity of $F^{\prime}$ (Assumption Q 1):

Under the independence of the noises (Assumption 3), then the uniform upper bound on the variance (Assumption 4), we have the following upper bound :

Under Assumption Q 1, $F^{\prime}$ is co-coercive, thus using Equation (S2), we have the following upper bound:

And using strong convexity (esp. Equation (S3)), and the fact that $\eta_{k+1}^{t}L\leq\frac{1}{2}$:

By recursion, we then have, for any $K\in[N^{t}]$:

C.3 Proof of Proposition S9

Under Assumptions Q 1,3,5,6, we have the following bound for one shot averaging: $p\in[P],t\in[C],k\in[N^{t}]$,

with, for $t\in[C]$, $\kappa_{1}^{t}=\left(4+\mu\sum_{k=1}^{N^{t}}(\eta_{k}^{t})^{2}\right)$, and $\kappa_{2}^{t}:=\exp\left(\mu\sum_{t^{\prime}=0}^{t}\sum_{k=1}^{N^{t}}(\eta_{k}^{t})^{2}\right)$.

When considering a constant step size $\eta$, we have the following corollary.

Under Assumptions Q 1,3,5,6, we have the following bound for one shot averaging: $p\in[P],t\in[C],k\in[N^{t}]$, constant learning rate $\eta$,

Where we have $\tau^{t}_{1}=4+\mu\boldsymbol{N}^{t}\eta^{2}$ and $\tau^{t}_{2}=\exp\left(\mu\boldsymbol{N}_{1}^{t}\eta^{2}\right)$. Under the latter requirement (for optimality) that for any $t$, $\boldsymbol{N}^{t}\mu P\eta\leq 1$, we have $\mu\boldsymbol{N}_{1}^{t}\eta^{2}\leq C\eta P^{-1}$, thus this is generally a small constant. This result is a consequence of Lemma S11.

As before, the first bound shows that the variance of the iterates after communication is reduced by a factor of $P$ w.r.t. the serial case, thus almost as good as mini-batch averaging. However, the constants involved are worse than in the additive noise setting (Proposition 3.3). Consequently, and similarly to Proposition 3.3, the bound for the current iterates is composed of two terms for the variance: a “reduced variance” coming from the communication step, and a “inner loop” variance, that does not benefit from the number of machines.

Finally, we provide a convergence result in the most general case, removing the quadratic assumption. For the sake of concision, we skip the bound for the averaged iterate after a communication round, and directly give the result for the inner process.

C.3.2 Proof

This result is a consequence of Lemma S11, which implies Equation S15. Indeed, using it recursively, and using $(1+x)\leq\exp(x)$, we get:

Under Assumptions Q 1, 3, 5, 6, for any $t\in[C],K\in[N^{t}]$, we have:

The proof is a bit technical, so we summarize here the 2 main steps:

We prove an inequality (namely Equation S20) that is comparable to Equation S12, but with an extra term.

We use the control on the inner process (Section C.1) to control the extra term.

We consider again the ghost process defined at Equation (S6). Equations (S10) and (S11) are still valid. We now use the following decompositionIn the following, $\square,\diamond,\clubsuit$, etc. are used as symbolic notations to ease presentation.:

Using the independence of the noises (Assumption 3) we have,

Using Assumption 5 (co-coercivity for $(g_{i,k}^{t})$-s and $F$) we obtain,

This leads to, combining Equations (S10) and (S19), and the upper bound on the variance of the noise at the optimum (Assumption 6)

Using $L\eta^{t}_{k+1}\leq\frac{1}{2}$, and strong-convexity (Assumption 1)

This inequality should be compared to Equation (S12). It is interesting to remark that the last term is not an artifact of the proof: this is easy to check for least-squares regression.

Using recursively the above inequality and using the definition of $\breve{\boldsymbol{w}}^{t}$, and taking expectation on the historical randomness we have, for any $N\in[N^{t}-1]$

Especially, for $N=N^{t}-1$, $\breve{\boldsymbol{w}}_{N^{t}}^{t}=\hat{\boldsymbol{w}}^{t}$, and moreover $\breve{\boldsymbol{w}}_{0}^{t}=\hat{\boldsymbol{w}}^{t-1}$:

To upper bound the last term in the above equation, we use Equation S4,

Note that since the mean squared distance doesn’t depend on the machine, we can assume to be working on machine $1$. This leads to, using an Abel transform:

We now use Equation S5. It leads to the following,

Combining Equations S21, S22 and S23, we get, denoting $C_{N^{t}}=\eta_{N^{t}}^{t}+\sum_{k=0}^{N^{t}-1}\mu(\eta_{k+1}^{t})^{2}$:

This concludes the proof of the Lemma, using $L\eta^{t}_{k}\leq 1/2$:

This result can be used recursively. It implies that if $\mu\sum_{t=1}^{C}\sum_{k=1}^{N^{t}}(\eta_{k}^{t})^{2}\leq K$, then the upper bound on the outer iterates is as good as the one for mini-batch, up to a constant.

C.4 Proof of Proposition S13

In this Section we prove the first upper bound of Corollary S14.

Finally, we provide a convergence result in the most general case, removing the quadratic assumption.

with $C_{P,M,K,t}=1+MP\sum_{k=1}^{K}\eta_{k}^{t}\left\|\breve{\boldsymbol{w}}_{k-1}^{t}-\boldsymbol{w}^{\star}\right\|$.

if $(\sup_{t^{\prime}=1\dots t}C_{P,M,K,t})$ is uniformly bounded, we perform as well as minibatch SGD for the outer iterations (up to a constant).

For a constant step size $\eta$, the proposition has the following corollary:

In the following, we alternatively relax the bounded variance assumption 4 and the quadratic assumption Q 1, and show similar results for local SGD. This allows us to successively cover the cases of least squares regression (LSR) and logistic regression (LR).

C.4.2 Proof

Proposition S13 follows from Lemma S15. We have for any $t\in[C],K\in[N^{t}]$,

with $C_{P,M,K,t}=1+MP\sum_{k=1}^{K}\eta_{k}^{t}\left\|\breve{\boldsymbol{w}}_{k-1}^{t}-\boldsymbol{w}^{\star}\right\|$.

For any $t\in[C],K\in[N^{t}]$, under Assumptions 1, 2, 3, 4 we have:

C.4.3 Proof of Lemma S15

We rely on the following decomposition. Almost surely, we have:

The first two lines correspond to the quadratic case (Equation S10), that has been analyzed in Lemma S11. The third term accounts for the difference between the mean gradient and the gradient at the mean point. We use Assumption 2 to control this term.

We then use the following Lemma, which control how the inner iterates $\boldsymbol{w}_{p,k}^{t}$ deviate from their average $\breve{\boldsymbol{w}}_{k}^{t}$:

For any $t\in[C],k\in[N^{t}]$, under Assumptions 1, 2, 3, 4 we have a.s.:

The proof of this Lemma is postponed to Section C.4.4.

Using Cauchy-Schwarz inequality and the bound on the third order derivative of $F$, we have:

and, using a second order expansion of the gradient at $\breve{\boldsymbol{w}}_{k}^{t}$ together with Assumption 2 we have:

Using the proof of Equation S12, and combining Equations S24, S26 and S25 and Lemma S16, we have, for any $t\in[C],k\in[N^{t}]$:

Thus by induction, for any $t\in[C],K\in[N^{t}]$:

In the following section, we proved the auxiliary Lemma that was used in the proof.

C.4.4 Proof of Lemma S16

We now study $\frac{1}{P}\sum_{p=1}^{P}\left\|\boldsymbol{w}_{p,k}^{t}-\breve{\boldsymbol{w}}_{k}^{t}\right\|^{2}$ as $k$ increases. Note that initially ($k=0$), this quantity is 0. For any $k\in[N^{t}],p\in[P]$:

Thus, expanding and using cocoercivity Assumption:

Note that everything is tight until the last line for $P=1$ ( then for all $k$, $\delta^{t}_{k}=0$). Under Assumption 4, we thus have:

Appendix D Convergence guaranties for the fourth order moment.

In this section, we prove several Lemmas that allow to control the fourth order moment of the iterate. While controlling the second order moment is sufficient for quadratic functions as no “residual” term appears in Equation 3 (the “residual” corresponds to the rest of a linear expansion of the gradient, which is thus exact for a quadratic function), in the general case, we also need to control the 4th order moment.

We first give guarantees for the inner iterates (within a phase) in Section D.1, then in the local SGD framework in Section D.2.

Here, we can use the following Lemma from Dieuleveut et al. (2017), that gives a recursion for the 4th order moment.

Under the Assumptions 1, 2, 3, 5 for th $4^{th}$-order moment, assuming $\eta\leq\frac{1}{18L}$ we have,

In the mini-batch setting, we have of course the same result with a variance reduction:

Under the Assumptions 1, 2, 3, 5 for th $4^{th}$-order moment for mini-batch averaging we have, assuming $\eta\leq\frac{1}{18L}$ we have,

Analogous to Lemma S1 we have the following result for fourth order moments,

Under the Assumptions 1, 2, 3, 5 for th $4^{th}$-order moment, assuming $\eta\leq\frac{1}{18L}$ we have,

Similarly for mini-batch analogous to Lemma S2,

Under the Assumptions 1, 2, 3, 5 for th $4^{th}$-order moment for mini-batch averaging and decreasing step size we have, assuming $\eta\leq\frac{1}{18L}$ we have,

The proof is included for completeness and because the same proof technique is used afterwards in Section D.2.

For $i\ \in[P]$, $k\ \in[N_{t}]$ and $t\in[C]$ we define the notation $\phi_{i,k}^{t}=\left\|\boldsymbol{w}_{i,k}^{t}-\boldsymbol{w}^{\star}\right\|$. We have that,

Above we have used Cauchy Schwartz inequality several times for the second inequality and equation (S28) for the third one.

Above we used $\eta L\leq 1$ in the last line. Finally, using strong convexity, we have:

D.2 Proof of Lemma S6

In this section, we prove the following Lemma, which is necessary to conclude the proof for the second set of Assumptions in Theorem 3.6. Indeed, we need to control the moment of order 4 to be able to control the residual term that arises from linear expansion of the gradient around $\boldsymbol{w}^{\star}$.

There exist absolute constants $C_{4},D_{4},E_{4}$, such that if $\eta_{k}^{t}L\leq\frac{1}{C_{4}}$:

This proof combines element from the classical bound for the fourth order moment, and from the proof of Lemma S15, which addresses the similar setting but only for the second order moment. We start from the definition of $\breve{\boldsymbol{w}}_{k+1}^{t}$:

Thus, squaring this equation we get, denoting $\breve{\phi}_{k}^{t}=\left\|\breve{\boldsymbol{w}}_{k}^{t}-\boldsymbol{w}^{\star}\right\|$:

formally, we have used $(a+b+c+d)^{2}\leq a^{2}+2ab+2ac+2ad+3b^{2}+3c^{2}+3d^{2}$.

That is, conditioning on the past, and using Assumption 5 (cocoercivity and the fact that $g_{k}^{t}$ is a.s. $L$-Lipshitz):

Rearranging terms and using the uniform upper bound on the 4-th moment of the noise 6, we have:

The first 2 lines of Equation S31 correspond to the expansion in S5 (the constants are slightly different because we use a uniform bound on the gradient instead of co-coercivity). The last two lines correspond to the residual term, for which we will use Lemma S16.

As a result, there exist absolute constants (“numbers”) $C_{4},D_{4},E_{4}$, such that if $\eta_{k}^{t}L\leq\frac{1}{C_{4}}$:

Appendix E Main error decomposition

In this section, we prove the following decomposition for the on-line setting.

Under the differentiability of 2 we haveNote that after the final iteration of the phase the learning rate (which the algorithm uses nowhere) corresponds to the first learning rate for the next phase. This anomaly in notation is a direct result of us considering the ghost process, which runs continuously till the end.,

where $\xi_{i,k}^{t}=F^{\prime}(\boldsymbol{w}_{i,k-1}^{t})-\boldsymbol{g}_{i,k}^{t}(\boldsymbol{w}_{i,k-1}^{t})$ and $\delta_{i,k}^{t}=F^{\prime\prime}(\boldsymbol{w}^{\star})(\boldsymbol{w}_{i,k-1}^{t}-\boldsymbol{w}^{\star})-F^{\prime}(\boldsymbol{w}_{i,k-1}^{t})$.

Below, we have $\boldsymbol{g}_{i,k}^{t}(\boldsymbol{w}_{i,k-1}^{t})$ as the stochastic gradient at step $k$ on machine $i$ for communication phase $t$. After adding and subtracting few quantities and rearranging we have,

where $\xi_{i,k}^{t}$ and $\delta_{i,k}^{t}$ are respectively terms related to stochastic noise and quadratic residual. Obtaining the horizontal average over all the machines and recalling the definition of the ghost process $\breve{\boldsymbol{w}}_{k}^{t}$ as defined above we have,

Obtaining the vertical average over all the machines first within a communication phase and then among different phases we have,

Now recalling the definitions for the overall iterate $\overline{\overline{\boldsymbol{w}}}^{C}=\frac{1}{\sum_{t=1}^{C}N^{t}}\sum_{t=1}^{C}\sum_{k=1}^{N^{t}}\breve{\boldsymbol{w}}_{k}^{t}$, $\hat{\boldsymbol{w}}^{t}=\breve{\boldsymbol{w}}_{N^{t}}^{t}$, the initial point $\hat{\boldsymbol{w}}^{0}=\boldsymbol{w}^{0}$, and the total number of gradients $T=P\sum_{t=1}^{C}N^{t}$ as we have defined above. After making these changes and on rearranging we obtain,

Thus we have obtained the required result as,

E.2 Bounding the noise term

The stochastic noise term which appears above can be bounded using the following lemma,

Using Assumptions 3, 5, 6 respectively we prove the result

Appendix F Proofs for OSA, MBA and Local-SGD in the finite horizon setting

Polyak and Judisky were mainly interested in the asymptotic analysis, and the set of assumptions considered was different.

In Bach and Moulines (2011), the authors prove comparable bounds in the case of bounded gradients. However, their analysis in the smooth and strongly convex setting is not optimal. Precisely, they use a sub-optimal upper bound when controlling the second order moments, that significantly worsens the subsequent proof. This point was underlined in Needell et al. (2014); Dieuleveut et al. (2017). The result they provide under our set of assumptions is eventually 1) not optimal, 2) uselessly complex, and 3) only for serial-SGD.

The result is an application of Jensen’s inequality with the convex function $f(.)=\left\lVert.\right\rVert^{2}$.

F.2 Proof of Proposition 3.1 (Mini-batch case)

Under the Assumptions 1, 2, 3, 5, 6 we have,

In order to upper bound the expectation we need to separately upper bound all the terms that appear in the result for Lemma S1. But before that we can actually simplify the result with constant step size and using $N^{t}=1\ \forall t\in[C]$ as follows,

Now we bound each of the terms in the above decomposition one by one. For the first term,

For the third term using Lemma S1 and Lemma S3 we get,

Now using the upper bound from 2 followed by Lemma S2 we get,

For the fourth term, note that we are sampling i.i.d observations and thus the stochastic noise across all machines and iterations is independent and equal to zero in expectation (see 3). This implies the first equation below while the second inequality is obtained using Lemma S3,

Now using Lemma S1, we have proved the lemma.

It can be seen in the above lemma that there are two kinds of terms: one that depend on the history or initialization and second the ones that depend on the variance bound. This implies that it would be possible to restate Lemma S5 as follows,

Under the assumptions 1, 2, 3, 5, 6 we have,

Ignoring constants the above constants can be upper bounded as follows,

F.3 Proof Proposition 3.2 (One-shot averaging case)

To prove the proposition we need to prove a bound on second moment of the inner iterations followed by a bound on the final average outer iteration. For inner iterations we follow the result from Moulines and Bach (2011) as the process on a single worker is completely independent of any other worker. We have the following lemma,

Under the Assumptions 1, 2, 3, 5, 6 for constant step size for one shot averaging we have,

We follow the same line of proof as before. We can use the decomposition from Lemma S1 with constant step size and $C=1$, which results in the following simpler decomposition,

For the second term using Lemma S3 and rearranging we have,

For the third term using Lemma S1 and Lemma S3 we obtain,

Now first using the upper bound of 2, followed by Lemma S1 and some rearranging we can obtain the following,

For the fourth term, using the fact that on different machines noise of the gradient is i.i.d. over different iterations and zero in expectation (3) we obtain,

Finally using Lemma S3, concludes the proof.

Similar to the mini-batch case, there are two kinds of terms one that depend on the history or initialization and second that depend on the variance bound of the functions. This implies that it would be possible to restate Lemma S8 as follows,

Under the Assumptions 3, 2, 1, 5, 6 we have,

On upper-bounding the above two terms while ignoring the constants,

Appendix G Proofs for OSA, MBA and Local-SGD in the online setting

Recall that the step size at iteration $(t,k),\in[C]\times[N^{t}]$ is defined as $\eta_{k}^{t}=\frac{c_{\eta}}{\left(\sum_{t^{\prime}=1}^{t-1}N^{t}+k\right)^{\alpha}}$ where $\alpha\in(0,1)$. Though our results can be extended for the entire range of learning rates, we prove results only for $\alpha\in(\frac{1}{2},1)$.

We first state a few technical results which are helpful in the following proofs.

The proof simply follows from applying the inequality $1+x\leq\exp\left(x\right)$, followed by an integral bound over the series as $\sum_{m=1}^{t}\frac{1}{m^{\alpha}}\geq\frac{1}{2}\int_{0}^{t}\frac{1}{m^{\alpha}}dm=\frac{t^{1-\alpha}}{1-\alpha}$. Note that it is possible to consider $\alpha=1$ but the integral bound changes. For brevity we don’t include it here.

First we decompose the term, then use $1+x\leq\exp(x)$, followed by a series of integral bounds like Lemma S1,

For the gamma function $\Gamma(s)=\int_{0}^{\infty}y^{s-1}\exp(-y)dy$ we have, $\sum_{t=1}^{C}\exp\left(-at^{b}\right)\leq\frac{1}{ba^{1/b}}\Gamma(\frac{1}{b})$.

First we use an integral bound as $\sum_{t=1}^{C}\exp\left(-at^{b}\right)\leq\int_{0}^{\infty}\exp\left(-az^{b}\right)dz$, followed by the integral substitution $u=az^{b}$ after which the proof follows from the definition of the gamma function.

For the gamma function $\Gamma(s)=\int_{0}^{\infty}y^{s-1}\exp(-y)dy$ we have, $\sum_{t=1}^{C}\frac{\exp\left(-at^{b}\right)}{t^{c}}\leq\frac{1}{ba^{(1-c)/b}}\Gamma(\frac{1-c}{b})$.

First we use an integral bound as $\sum_{t=1}^{C}\frac{\exp\left(-at^{b}\right)}{t^{c}}\leq\int_{0}^{\infty}\frac{\exp\left(-az^{b}\right)}{z^{c}}dz$, followed by the integral substitution $u=az^{b}$ after which the proof follows from the definition of the gamma function.

For $a\in(0,1)$, $\sum_{t=1}^{C}\frac{1}{t^{1-a}}\leq\frac{C^{a}}{a}$.

It is a simple application of the integral bound on a decreasing function, $\sum_{t=1}^{C}\frac{1}{t^{1-a}}\leq\int_{0}^{C}x^{a-1}dx=\frac{C^{a}}{a}$.

G.2 Proof of Proposition 4.1 (Mini-batch Averaging Case)

We have the following lemma for mini-batch averaging for the decreasing step-size case,

Under the Assumptions 1, 2, 3, 5, 6 we have for mini-batch averaging,

Using again the decomposition in Lemma S1, we can obtain the following simpler version for mini-batch averaging,

Note again that we assume $\alpha\in(\frac{1}{2},1)$, just for the sake of brevity. For the first term,

For the second term using Lemma S2, followed by Lemma S1 and Lemma S3 we obtain,

For the third term using Lemma S11 and $(t+1)^{\alpha}-t^{\alpha}\leq\alpha t^{\alpha-1}$,

Now using Lemma S2, Lemma S1, Lemma S3 and $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ we get,

Now using Lemma S7 (with $b=1-\alpha$, $c=1-\alpha$ and $a=\frac{\mu c_{\eta}}{4(1-\alpha)}$), followed by using Lemma S7 again (with $a=\frac{\mu c_{\eta}}{4(1-\alpha)}\left(1-\frac{1}{2^{1-\alpha}}\right)$, $b=1-\alpha$ and $c=1-\alpha$) and Lemma S9 (with $a=\frac{\alpha}{2}$) we get,

Finally using Lemma S1 and re-organizing with constants defined as above,

For the fourth term first proceeding as in Lemma S5 with Lemma S1 and Lemma S3 we can obtain,

Now using Lemma S3, followed by Lemma S1 and Lemma S3 we getNote that we ignore t=1 in second inequality for second term as we have already incorporated it in the first term,

Now using Lemma S5 (with $b=1-\alpha$ and $a=\frac{\mu c_{\eta}}{2(1-\alpha)}$), followed by Lemma S5 again (with $a=\frac{\mu c_{\eta}}{2(1-\alpha)}\left(1-\frac{1}{2^{1-\alpha}}\right)$ and $b=1-\alpha$), followed by Lemma S9 (with $a=1-\alpha$) and Lemma S1 we get,

Bounding again with the constants defined above,

For the fifth term, proceeding as in Lemma S5,

Now using Lemma S2, Lemma S1 and Lemma S3 like before,

Further using Lemma S5 (with $b=1-\alpha$ and $a=\frac{\mu c_{\eta}}{2(1-\alpha)}$), followed by Lemma S5 again (with $a=\frac{\mu c_{\eta}}{2(1-\alpha)}\left(1-\frac{1}{2^{1-\alpha}}\right)$ and $b=1-\alpha$), followed by Lemma S9 (with $a=1-\alpha$) and the constants as used above we get,

Finally using Lemma S1 we have proved the lemma.

The following lemma separates the terms above into bias and variance terms, following which we can easily prove Proposition 4.1,

Under the Assumptions 1, 2, 3, 5, 6 we have for mini-batch averaging,

Where for constants defined as above the terms are,

To get Proposition 4.1, we upper bound every term up to constants depending only on $\alpha$. Specifically, we use $\beta_{1}\precsim{(\mu c_{\eta})^{-\frac{1}{1-\alpha}}}$, $\beta_{2}\precsim{(\mu c_{\eta})^{-\frac{\alpha}{1-\alpha}}}$, and $\beta_{3}\precsim\frac{c_{\eta}}{\mu}$.

G.3 Proof of Proposition 4.1 (One-shot Averaging case)

The analysis for the one-shot case is very similar to the mini-batch case, just like the constant step-size case. In fact at many place the communications $C$ of MBA get replaced by $N^{1}$ and the form of the bound remains the same. This intuitive conversion strengthens our analysis, which smoothly extends to both the extreme cases.

Under the Assumptions 1, 2, 3, 5, 6 for decreasing step size, for one shot averaging we have,

And the constants are $\beta_{1}=1+\left(\frac{(1-\alpha)^{\alpha}}{\mu c_{\eta}}\right)^{\frac{1}{1-\alpha}}\Gamma\left(\frac{1}{1-\alpha}\right)$ and $\beta_{2}=\left(2^{\alpha}\frac{(1-\alpha)^{2\alpha-1}}{(\mu c_{\eta})^{\alpha}}\right)^{\frac{1}{1-\alpha}}\Gamma\left(\frac{\alpha}{1-\alpha}\right)$.

We follow an analysis similar to Godichon and Saadane (2017). We can simplify the decomposition from Lemma S1 for one outer phase as follows,

For the second term note that the inner iterate bound is independent for different machines using Lemma S4 for say machine $1$, followed by Lemma S1 and Lemma S3 we get,

For the third term using $(k+1)^{\alpha}-k^{\alpha}\leq\alpha k^{\alpha-1}$, Lemma S11, and noting that the individual bounds on inner iterates for different machines are the same, thus using machine $1$ for brevity we can obtain,

Now using Lemma S4, Lemma S1, Lemma S3 and $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ we get,

Now using Lemma S7 again with $b=1-\alpha$ and $a=\frac{\mu c_{\eta}}{2(1-\alpha)}$ with $\beta_{2}$ defined as above and Lemma S9 we get,

Now for the fourth term proceeding as in Lemma S8 with Lemma S1 and Lemma S3 we can obtain ,

Now first using the upper bound of 2, followed by Lemma S3, Lemma S1, Lemma S3 and Lemma S5 we can obtain the following,

For the fifth term, using the fact that for different machines noise is independent, zero in expectation (3) we obtain,

Now using Lemma S4, followed by Lemma S1, Lemma S3 and Lemma S5 with definition of $\beta$ as before, and we have,

Thus using Lemma S1 we have proved the lemma.

We can get the following lemma combining the bias and variance terms separately,

Under the Assumptions 1, 2, 3, 5, 6 for decreasing step size, for one shot averaging we have,

Where for constants defined as above the terms are,

Appendix H Brief overview of distributed optimization

The above three schemes (OSA, MBA, Local-SGD) are the most studied synchronous parallel schemes. However, communication latencies often make it difficult to use these algorithms for large-scale problems. Thus many alternative parallelization schemes which minimize communication or perform better have been studied. The major problem with some of these variants is that they are often difficult to tune, are not as stable and don’t scale well to non-convex optimization problems. Result-wise, most of the machine learning packages use centralized mini-batch synchronous SGD.

Asynchronous SGD: These techniques are characterized by avoiding a centralized synchronization, using delayed updates, maintaining parameter server estimates and being fault tolerant. Some of the notable references in a chronological order are Langford et al. (2009); Niu et al. (2011); Agarwal and Duchi (2011); Paine et al. (2013); Li et al. (2014b); Zhang et al. (2014); Keuper and Pfreundt (2015); De and Goldstein (2015); Feyzmahdavian et al. (2015); Lian et al. (2015); Mania et al. (2015); Zhao and Li (2015); Duchi et al. (2015); Chen et al. (2016a); Lian et al. (2017a); Pedregosa et al. (2017); Lian et al. (2017b); Leblond et al. (2018); Alistarh et al. (2018).

Federated optimization: This setting is characterized by a huge number of mobile user devices, which run their local model in a decentralized manner with often unbalanced data, but aim to train jointly. Many research questions still remain open but the direction is very relevant for distributed AI. Some references are Konecný et al. (2015, 2016); McMahan et al. (2016).

Compressed Communication: A common strategy to combat the communication overhead is to introduce lossless or lossy compression of exchanged information, often the gradients. Some of the work in this direction can be found in Zhang et al. (2017); Wen et al. (2017); Wangni et al. (2017); Sa et al. (2015); Na et al. (2017); Gupta et al. (2015); Alistarh et al. (2016); Khirirat et al. (2018).

Non-SGD methods: Many other optimization algorithms (coordinate descent, quasi newton, etc.) have also been studied in the parallel setting, owing to their better distributivity or convergence for some applications compared to the SGD algorithm. Some of them are Boyd et al. (2011) (ADMM), Shamir et al. (2014) (DANE), Zhang and Xiao (2015) (DiSCO), Reddi et al. (2016) (AIDE), Ma et al. (2017); Smith et al. (2016); Ma et al. (2015) (COCOA) and some of the references therein. Recently Scaman et al. (2017) gave provably optimal algorithms for the strongly convex and smooth functions for both synchronous and asynchronous cases. More broadly speaking, variance reduction methods are often the methods of choice in better understood, convex optimization problems [add reference]. Yet, their usage in the deep learning community has been relatively scarce, and often they are more difficult to parallelize [add reference]. Some of the works for instance are Reddi et al. (2015); Zhao and Li (2016); De and Goldstein (2015); Lee et al. (2015). Among second order methods, quasi newton methods like distributed L-BFGS Najafabadi et al. (2017); Şimşekli et al. (2018) are also widely popular among the machine learning community.

Communication Lower Bounds: On a broader level our work is related to communication lower bounds which arise from information and learning-theoretic considerations. Unfortunately, these bounds are difficult to match for convex optimization as they are provided in Arjevani and Shamir (2015). Similar bounds have also been provided for the generally easier statistical estimation setting in Duchi et al. (2014); Braverman et al. (2015); Zhang et al. (2013).

Feature Distribution: As clearly evident training data is not the only element of our optimization scheme which can be parallelized. Often in many problems in natural language processing and linear estimation, the features number in hundreds of thousands, and it might be of some interest to distribute the features alongside or beside training data. Some relevant references are Lee et al. (2014); Ma and Takáč (2015); Smith et al. (2016); Chen et al. (2016b); Fang and Klabjan (2018).

There has also been work in parallelizing stochastic optimization algorithms for specific problems (like PCA) in the past, for e.g., Mcdonald et al. (2009); McDonald et al. (2010); Meng et al. (2012); Zhuang et al. (2013); Li et al. (2014a); Chin et al. (2015); Oh et al. (2015).

We also provide a brief overview of some other techniques in distributed optimization in Appendix H.