# Balancing Communication and Computation in Distributed Optimization

arXiv: https://arxiv.org/abs/1709.02999 · HTML: https://mlsanity.com/paper/1709.02999/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2017.

## Built on by (most cited first, 23 of 23)

- [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021)
- [Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD](https://mlsanity.com/paper/2105.08023/) (2021)
- [Accelerating Gossip SGD with Periodic Global Averaging](https://mlsanity.com/paper/2105.09080/) (2021)
- [DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/2110.01165/) (2021)
- [Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework](https://mlsanity.com/paper/2503.14353/) (2025)
- [Collaborative and Distributed Bayesian Optimization via Consensus: Showcasing the Power of Collaboration for Optimal Design](https://mlsanity.com/paper/2306.14348/) (2023)
- [On the Local Linear Rate of Consensus on the Stiefel Manifold](https://mlsanity.com/paper/2101.09346/) (2021)
- [Federated Optimization of Smooth Loss Functions](https://mlsanity.com/paper/2201.01954/) (2022)
- [Decentralized Bayesian Learning with Metropolis-Adjusted Hamiltonian Monte Carlo](https://mlsanity.com/paper/2107.07211/) (2021)
- [On the Computation-Communication Trade-Off with A Flexible Gradient Tracking Approach](https://mlsanity.com/paper/2306.07159/) (2023)
- [DIMAT: Decentralized Iterative Merging-And-Training for Deep Learning Models](https://mlsanity.com/paper/2404.08079/) (2024)
- [Distributed Online Non-convex Optimization with Composite Regret](https://mlsanity.com/paper/2209.10105/) (2022)
- [DeCAF: Decentralized Consensus-And-Factorization for Low-Rank Adaptation of Foundation Models](https://mlsanity.com/paper/2505.21382/) (2025)
- [Online Distributed Learning with Quantized Finite-Time Coordination](https://mlsanity.com/paper/2307.06620/) (2023)
- [Adjacent Leader Decentralized Stochastic Gradient Descent](https://mlsanity.com/paper/2405.11389/) (2024)
- [Energy-Aware Decentralized Learning with Intermittent Model Training](https://mlsanity.com/paper/2407.01283/) (2024)
- [Distributed optimization: designed for federated learning](https://mlsanity.com/paper/2508.08606/) (2025)
- [Adaptive Consensus: A network pruning approach for decentralized optimization](https://mlsanity.com/paper/2309.02626/) (2023)
- [Asynchronous Local Computations in Distributed Bayesian Learning](https://mlsanity.com/paper/2311.03496/) (2023)
- [MUSIC: Accelerated Convergence for Distributed Optimization With Inexact and Exact Methods](https://mlsanity.com/paper/2403.02589/) (2024)
- [Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization](https://mlsanity.com/paper/2506.15387/) (2025)
- [Pareto-optimal Trade-offs Between Communication and Computation with Flexible Gradient Tracking](https://mlsanity.com/paper/2509.18129/) (2025)
- [Decentralized Gradient Descent: Bottleneck Regimes and Budget Complexity](https://mlsanity.com/paper/2607.12172/) (2026)

## Abstract (arXiv)

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 DGDt, NEAR-DGDt 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.