Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization

• DOI: 10.48550/arxiv.2002.11364
• Publication Date: 2020-01-01
• Authors: Zhize Li; Dmitry Kovalev; Xun Qian; Peter Richtárik
• Keywords: FOS: Computer and information sciences; Computer Science - Machine Learning; Databases and Information Systems; Computer Science - Distributed, Parallel, and Cluster Computing; Optimization and Control (math.OC); FOS: Mathematics; Distributed, Parallel, and Cluster Computing (cs.DC); Mathematics - Optimization and Control; 01 natural sciences; 0105 earth and related environmental sciences; Machine Learning (cs.LG)

Due to the high communication cost in distributed and federated learning problems, methods relying on compression of communicated messages are becoming increasingly popular. While other contexts best performing gradient-type invariably rely some form acceleration/momentum reduce number iterations, there no which combine benefits both gradient acceleration. In this paper, we remedy situation propose first accelerated compressed descent (ACGD) methods. single machine regime, prove that ACGD enjoys rate $O\Big((1+\omega)\sqrt{\frac{L}{\mu}}\log \frac{1}{\epsilon}\Big)$ for $\mu$-strongly convex problems $O\Big((1+\omega)\sqrt{\frac{L}{\epsilon}}\Big)$ respectively, where $\omega$ is parameter. Our results improve upon existing non-accelerated rates $O\Big((1+\omega)\frac{L}{\mu}\log $O\Big((1+\omega)\frac{L}{\epsilon}\Big)$, recover optimal as a special case when ($\omega=0$) applied. We further variant (called ADIANA) convergence $\widetilde{O}\Big(\omega+\sqrt{\frac{L}{\mu}}+\sqrt{\big(\frac{\omega}{n}+\sqrt{\frac{\omega}{n}}\big)\frac{\omega L}{\mu}}\Big)$, $n$ devices/workers $\widetilde{O}$ hides logarithmic factor $\log \frac{1}{\epsilon}$. This improves previous result $\widetilde{O}\Big(\omega + \frac{L}{\mu}+\frac{\omega L}{n\mu} \Big)$ achieved by DIANA method Mishchenko et al. (2019). Finally, conduct several experiments real-world datasets corroborate our theoretical confirm practical superiority