Communication-efficient algorithms for decentralized and stochastic optimization

By Guanghui Lan, Soomin Lee, Yi Zhou. 2017

239 citations recorded by the source corpus.

We present a new class of decentralized first-order methods for nonsmooth and stochastic optimization problems defined over multiagent networks. Considering that communication is a major bottleneck in decentralized optimization, our main goal in this paper is to develop algorithmic frameworks which can significantly reduce the number of inter-node communications. Our major contribution is to present a new class of decentralized primal–dual type algorithms, namely the decentralized communication sliding (DCS) methods, which can skip the inter-node communications while agents solve the primal subproblems iteratively through linearizations of their local objective functions. By employing DCS, agents can find an ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon $$\end{document}-solution both in terms of functional optimality gap and feasibility residual in O(1/ϵ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal {O}}}(1/\epsilon )$$\end{document} (resp., O(1/ϵ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal {O}}}(1/\sqrt{\epsilon })$$\end{document}) communication rounds for general convex functions (resp., strongly convex functions), while maintaining the O(1/ϵ2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal {O}}}(1/\epsilon ^2)$$\end{document} (resp., O(1/ϵ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{O}(1/\epsilon )$$\end{document}) bound on the total number of intra-node subgradient evaluations. We also present a stochastic counterpart for these algorithms, denoted by SDCS, for solving stochastic optimization problems whose objective function cannot be evaluated exactly. In comparison with existing results for decentralized nonsmooth and stochastic optimization, we can reduce the total number of inter-node communication rounds by orders of magnitude while still maintaining the optimal complexity bounds on intra-node stochastic subgradient evaluations. The bounds on the (stochastic) subgradient evaluations are actually comparable to those required for centralized nonsmooth and stochastic optimization under certain conditions on the target accuracy.

Subfields: Artificial Intelligence, Computer Networks and Communications, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Optimization & Training

Citations in the corpus

Communication Efficient Decentralized Training with Multiple Local Updates (2019, background): “2 [14] Guanghui Lan, Soomin Lee, and Yi Zhou.”
GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, background): “On the other hand, (Lan et al., 2017) proposed a decentralized algorithm that enforces each worker to transmit the updated primal and dual variables at each iteration.”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, methodology): “Lan et al. (2018) applied gradient sliding techniques allowing to skip some of the communication rounds.”
Distributed Learning over Unreliable Networks (2018, background): “g (Seide & Agarwal, 2016), decentralized communication (Lian et al., 2017a; Sirb & Ye, 2016; Lan et al., 2017; Tang et al., 2018a; Stich et al., 2018), and asynchronous communication (Lian et al.”
D2: Decentralized Training over Decentralized Data (2018, methodology): “In Lan et al. [2017], a decentralized primal-dual type method was proposed with a computational complexity of O ( n/e2 ) for general convex objectives. Lian et al. [2017a] proved that D-PSGD can admits linear speedup w.”
Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent (2017, background): “…and Nedic, 2011, Sundhar Ram et al., 2010] or implicitly indicate that decentralized algorithms were much worse than centralized algorithms in terms of computational complexity and total communication complexity [Aybat et al., 2015, Lan et al., 2017, Ram et al., 2010, Zhang and Kwok, 2014].”
Scheduling Policies for Federated Learning in Wireless Networks (2019, background): “In many real-world systems, communicating data between machines is several orders of magnitude slower than reading data from main memory and performing local computing [27].”
Communication Compression for Decentralized Training (2018, methodology): “In Lan et al. [2017], a new decentralized primal-dual type method is proposed with a computational complexity of O( √ n/T ) for general convex objectives.”
Collaborative Deep Learning in Fixed Topology Networks (2017, background): “A new class of decentralized primal-dual methods [18] was also proposed recently in order to improve inter-node communication efficiency for distributed convex optimization problems.”
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks (2018, methodology): “Our decentralized algorithm is closely related to the recent primal-dual algorithm of [14] which enjoys fast communication rates in a decentralized and stochastic setting.”
LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learning (2018, background): “While a sublinear convergence rate can be achieved by algorithms in (Lan et al., 2017), the proposed gradient selection rule is nonadaptive and requires double-loop iterations.”
Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks (2019, background): “In this experiment, the number of inner iterations of D-CS is set to 1. works where there the performance depends on the interplay between the bias, variance and network effects.”
Lower Bounds and Optimal Algorithms for Personalized Federated Learning (2020, methodology): “In this work, we focus on the mixing FL objective from [19], which is well-known from the area of distributed optimization [26, 16] and distributed transfer learning [30, 50].”
Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning (2019, unknown): “On the other hand, [48] proposed a decentralized algorithm that enforces each worker to transmit the updated primal and dual variables at every iteration.”
Optimal Convergence Rates for Convex Distributed Optimization in Networks (2019, unknown): “This algo-rithm is closely related to the primal-dual algorithm proposed by Lan et al. (2017), which we modify by the use of accelerated gossip using Chebyshev polynomials as done by Scaman et al. (2017).”
A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent (2019, background): “[21] presented a new class of distributed first-order methods for nonsmooth and stochastic optimization which was shown to exhibit an O( 1 k ) (respectively, O( 1 √ k )) convergence rate for minimizing the sum of strongly convex functions (respectively, convex functions).”