\section{Introduction}
Leveraging distributed computing resources and decentralized data is crucial, if not necessary, for large-scale machine learning applications. 
Communication is usually the major bottleneck for parallelization in both data-center settings and cross-device federated settings \citep{Kairouz.McMahan.ea-arXiv19}.

We study the distributed stochastic optimization $\min_{w \in \reals^d} F(w) :=  \expt_{\xi \sim \mathcal{D}} f(w; \xi) $ where $F$ is convex.
We assume there are $M$ parallel workers and each worker can access $F$ at $w$ via oracle $\nabla f(w; \xi)$ for independent sample $\xi$ drawn from distribution $\mathcal{D}$. 
We assume synchronization (communication) among workers is allowed but limited to $R$ rounds. We denote $T$ as the parallel runtime.

One of the most common and well-studied algorithms for this setting is \emph{Federated Averaging} (\fedavg) \citep{McMahan.Moore.ea-AISTATS17}, also known as Local SGD or Parallel SGD  \citep{Mangasarian-95,Zinkevich.Weimer.ea-NIPS10,Coppola-14,Zhou.Cong-IJCAI18} in the literature.\footnote{In the literature, \fedavg usually runs on a randomly sampled subset of heterogeneous workers for each synchronization round, whereas Local SGD or Parallel SGD usually run on a fixed set of workers. In this paper we do not differentiate the terminology and assumed a fixed set of workers are deployed for simplicity.} 
In \fedavg, each worker runs a local thread of SGD \citep{Robbins.Monro-51}, 
and periodically synchronizes with other workers by collecting the averages and broadcast to all workers.
The analysis of \fedavg \citep{Stich-ICLR19,Stich.Karimireddy-arXiv19,Khaled.Mishchenko.ea-AISTATS20,Woodworth.Patel.ea-ICML20} usually follows the perturbed iterate analysis framework \citep{Mania.Pan.ea-SIOPT17} where the performance of \fedavg is compared with the idealized version with infinite synchronization. The key idea is to control the stability of SGD so that the local  iterates held by parallel workers do not differ much, even with infrequent synchronization.

We study the acceleration of \fedavg and investigate whether it is possible to improve convergence speed and communication efficiency. 
The main challenge for introducing acceleration 
lies in the disaccord of acceleration and stability. 
Stability is essential for analyzing distributed algorithms such as \fedavg, whereas momentum applied for acceleration may amplify the instability of the algorithm. 
Indeed, we show that standard Nesterov accelerated gradient descent algorithm \citep{Nesterov-18} \emph{may not be initial-value stable even for smooth and strongly convex functions}, in the sense that the initial infinitesimal difference may grow exponentially fast (see \cref{instability:sketch}). 
This evidence necessitates a more scrutinized acceleration in distributed settings.

We propose a principled acceleration for \fedavg, namely \emph{\fedacfull} (\fedac), which provably improves convergence rate and communication efficiency. 
Our result extends the results of \citet{Woodworth.Patel.ea-ICML20} on \textsc{Local-Ac-Sa} for quadratic objectives to broader objectives.
To the best of our knowledge, this is the \textbf{first provable acceleration} of \fedavg (and its variants) for general or strongly convex objectives.
\fedac parallelizes a generalized version of Accelerated SGD \citep{Ghadimi.Lan-SIOPT12}, while we carefully 
balance the acceleration-stability tradeoff to accommodate distributed settings.
Under standard assumptions on smoothness, bounded variance, and strong convexity (see \cref{asm1} for details), \fedac converges at rate $\tildeo ( \frac{1}{M T} + \frac{1}{TR^3} )$.\footnote{We hide varaibles other than $T, M, R$ for simplicity. The complete bound can be found in \cref{tab:conv:rate} and the corresponding theorems.}
The bound will be dominated by $\tildeo(\frac{1}{MT})$ for $R$ as low as $\tildeo(M^{\frac{1}{3}})$, which implies the synchronization $R$ required for linear speedup in $M$ is $\tildeo(M^{\frac{1}{3}})$.\footnote{
    ``Synchronization required for linear speedup'' is a simple and common measure of the communication efficiency, which can be derived from the raw convergence rate. It is defined as the minimum number of synchronization $R$, as a function of number of workers $M$ and parallel runtime $T$, required to achieve a linear speed up --- the parallel runtime of $M$ workers is equal to the $\nicefrac{1}{M}$ fraction of a sequential single worker runtime.}
In comparison, the state-of-the-art \fedavg analysis \citet{Khaled.Mishchenko.ea-AISTATS20} showed that \fedavg converges at rate $\tildeo ( \frac{1}{M T} + \frac{1}{TR} )$, which requires $\tildeo(M)$ synchronization for linear speedup.
For general convex objective, \fedac converges at rate $\tildeo(\frac{1}{\sqrt{MT}} + \frac{1}{T^{\frac{1}{3}} R^{\frac{2}{3}}})$, which outperforms both state-of-the-art \fedavg $\tildeo(\frac{1}{\sqrt{MT}} + \frac{1}{T^{\frac{1}{3}} R^{\frac{1}{3}}})$ by \citeauthor{Woodworth.Patel.ea-ICML20} and Minibatch-SGD baseline ${\Theta}(\frac{1}{\sqrt{MT}} + \frac{1}{R})$ \citep{Dekel.Gilad-Bachrach.ea-JMLR12}.\footnote{
    Minibatch-SGD baseline corresponds to running SGD for $R$ steps with batch size $MT/R$, which can be implemented on $M$ parallel workers with $R$ communication and each worker queries $T$ gradients in total.
    }
We summarize communication bounds and convergence rates in \cref{tab:sync:bound,tab:conv:rate} (on the row marked A\ref{asm1}).

\input{table1}

Our results suggest an \textbf{intriguing synergy between acceleration and parallelization}.
In the single-worker sequential setting, the convergence is usually dominated by the term related to stochasticity,
which is in general not possible to be accelerated \citep{Nemirovski.Yudin-83}.
In distributed settings, the communication efficiency is dominated by the overhead caused by infrequent synchronization, which can be accelerated as we show in the convergence rates summary \cref{tab:conv:rate}. 

\input{table2}
We establish \textbf{stronger guarantees for \fedac when objectives are \nth{3}-order-smooth}, or ``close to be quadratic'' intuitively (see \cref{asm2} for details).
For strongly convex objectives, \fedac converges at rate $\tildeo (\frac{1}{MT} + \frac{1}{T^2 R^6})$ (see \cref{fedacii:a2}).
We also prove the convergence rates of \fedavg in this setting for comparison.
We summarize our results in \cref{tab:sync:bound,tab:conv:rate} (on the row marked A\ref{tab:conv:rate}).

We empirically verify the efficiency of \fedac in \cref{sec:experiment}. Numerical results suggest a considerable improvement of \fedac over all three baselines, namely \fedavg, (distributed) Minibatch-SGD, and (distributed) Accelerated Minibatch-SGD \citep{Dekel.Gilad-Bachrach.ea-JMLR12,Cotter.Shamir.ea-NeurIPS11}, especially in the regime of highly infrequent communication and abundant workers.
\input{related_work}
{"config": "arxiv", "file": "2006.08950/introduction.tex"}