Balancing Communication and Computation in Distributed Optimization

DOI10.1109/TAC.2018.2880407MaRDI QIDQ5228298zbMATH OpenOpenAlexFDO

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

Publication date 12 August 2019

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.02999

Mathematics Subject Classification ID

Distributed systems (68M14) Convex programming (90C25)

Abstract: Methods for distributed optimization have received significant attention in recent years owing to their wide applicability in various domains. 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 work we propose an adaptive cost framework which 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${}^t$, NEAR-DGD${}^t$ and NEAR-DGD${}^{+}$, compare favorably to their base algorithms, both theoretically and empirically. The proposed NEAR-DGD${}^{+}$ 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.

Recommendations

• Distributed optimization over networks
• Communication-efficient algorithms for decentralized and stochastic optimization
• Approximations in Distributed Optimization
• Distributed optimisation problem with communication delay and external disturbance
• Distributed Optimization With Coupling Constraints
• Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis
• scientific article; zbMATH DE number 7307473
• Communication-Aware Local Search for Distributed Constraint Optimization
• Distributed optimization: advances in theories, methods, and applications
• Distributed aggregative optimization with quantized communication

Cited in

(21)

• Convergence results of a nested decentralized gradient method for non-strongly convex problems
• Improving the convergence of distributed gradient descent via inexact average consensus
• EFIX: exact fixed point methods for distributed optimization
• scientific article; zbMATH DE number 6982986 (Why is no real title available?)
• On the convergence of exact distributed generalisation and acceleration algorithm for convex optimisation
• Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation
• Distributed aggregative optimization with quantized communication
• DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization
• scientific article; zbMATH DE number 7307473 (Why is no real title available?)
• COMMUNICATION BALANCING IN THE PARALLEL GÖTTFERT ALGORITHM
• Communication-Aware Local Search for Distributed Constraint Optimization
• Balancing load versus decreasing communication: Parameterizing the tradeoff
• Resilient penalty function method for distributed constrained optimization under Byzantine attack
• Decentralized Bayesian learning with Metropolis-adjusted Hamiltonian Monte Carlo
• Adaptive consensus: a network pruning approach for decentralized optimization
• Balancing communication and computation in gradient tracking algorithms for decentralized optimization
• Designing edge-based and node-based fully distributed algorithms for aggregative games with the adaptive technique
• On the convergence result of the gradient-push algorithm on directed graphs with constant stepsize
• A flexible gradient tracking algorithmic framework for decentralized optimization
• Distributed inexact Newton method with adaptive step sizes
• An improved convergence guarantee for the gradient-push algorithm with a constant stepsize

This page was built for publication: Balancing Communication and Computation in Distributed Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5228298)