Balancing Communication and Computation in Distributed Optimization

By Albert S. Berahas, Raghu Bollapragada, Nitish Shirish Keskar, Ermin Wei. 2017

120 citations recorded by the source corpus.

Methods for distributed optimization have received significant attention in recent years owing to their wide applicability in various domains including machine learning, robotics, and sensor networks. A distributed optimization method typically consists of two key components: communication and computation. More specifically, at every iteration (or every several iterations) of a distributed algorithm, each node in the network requires some form of information exchange with its neighboring nodes (communication) and the computation step related to a (sub)-gradient (computation). The standard way of judging an algorithm via only the number of iterations overlooks the complexity associated with each iteration. Moreover, various applications deploying distributed methods may prefer a different composition of communication and computation. Motivated by this discrepancy, in this paper, we propose an adaptive cost framework that adjusts the cost measure depending on the features of various applications. We present a flexible algorithmic framework, where communication and computation steps are explicitly decomposed to enable algorithm customization for various applications. We apply this framework to the well-known distributed gradient descent (DGD) method, and show that the resulting customized algorithms, which we call DGD<inline-formula><tex-math notation="LaTeX">$^t$</tex-math></inline-formula>, NEAR-DGD<inline-formula><tex-math notation="LaTeX">$^t$</tex-math></inline-formula>, and NEAR-DGD<inline-formula><tex-math notation="LaTeX">$^+$</tex-math></inline-formula>, compare favorably to their base algorithms, both theoretically and empirically. The proposed NEAR-DGD<inline-formula><tex-math notation="LaTeX">$^+$</tex-math></inline-formula> algorithm is an exact first-order method where the communication and computation steps are nested, and when the number of communication steps is adaptively increased, the method converges to the optimal solution. We test the performance and illustrate the flexibility of the methods, as well as practical variants, on quadratic functions and classification problems that arise in machine learning, in terms of iterations, gradient evaluations, communications, and the proposed cost framework.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

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 Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization (2019, background): “We consider the total training time as the cost objective which consists of communication and computation time [Berahas et al., 2018, Reisizadeh et al., 2019c].”
Compressed Distributed Gradient Descent: Communication-Efficient Consensus over Networks (2018, methodology): “Consider the following Lyapunov function, which is also used in [16], [21]:”
Distributed Gradient Methods for Convex Machine Learning Problems in Networks: Distributed Optimization (2020, methodology): “Subsequently, many distributed methods have been developed, such as those with a faster convergence [19], [20] and with emphasis on the communication and computation tradeoffs [21], [22].”
Nested Distributed Gradient Methods with Adaptive Quantized Communication (2019, methodology): “By setting the parameters t(k) appropriately, one can recover all the methods proposed in [11].”