Pareto-optimal Tradeoffs Between Communication and Computation with Flexible Gradient Tracking
Yan Huang, Jinming Xu, Li Chai, Jiming Chen, Karl H. Johansson · 2025
Read Pareto-optimal Tradeoffs Between Communication and Computation with Flexible Gradient Tracking by Yan Huang, Jinming Xu, Li Chai, Jiming Chen, Karl H. Johansson (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-18129.txt.
Introduction
Yan Huang and 4 co-authors tune how often scattered workers compute and talk in shared training. Their 2025 paper deals with distributed stochastic optimization, where data at each node are not alike. More local steps save talk, while more talk keeps nodes in sync, so the best mix shifts by system.
Their method, FlexGT, lets each round set both counts freely, with a tracked snapshot gradient. A joint proof frame gives tight bounds for talk and compute cost. A sped-up variant, with graph facts known in advance, hits the best trade curve. In the non-convex case, its costs match known floors.
Catalog record
| CREATOR | Yan Huang, Jinming Xu, Li Chai, Jiming Chen, Karl H. Johansson |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-18129
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Pareto-optimal Tradeoffs Between Communication and Computation with Flexible Gradient Tracking Thanks: Part of the results were previously presented in the Proceedings of the 62nd IEEE Conference on Decision and Control (CDC) [ 14 ] . Yan Huang, Jinming Xu, Li Chai, Jiming Chen, Karl H. Johansson Abstract This paper addresses distributed optimization problems in non-i.i.d. scenarios, focusing on the interplay between communication and computation efficiency. To this end, we propose FlexGT, a flexible snapshot gradient tracking method with tunable numbers of local updates and neighboring communications in each round. Leveraging a unified convergence analysis framework, we prove that FlexGT achieves a linear or sublinear convergence rate depending on objective-specific properties–from (strongly) convex to nonconvex–and the above-mentioned tunable parameters. FlexGT is provably robust to the heterogeneity across nodes and attains the best-known communication and computation complexity among existing results. Moreover, we introduce an accelerated gossip-based variant, termed Acc-FlexGT, and show that with prior knowledge of the graph, it achieves a Pareto-optimal trade-off between communication and computation. Particularly, Acc-FlexGT achieves the optimal iteration complexity of 𝒪 ~ ( L / ϵ + L σ 2 / ( n ϵ 2 1 − ρ W ) ) \tilde{\mathcal{O}}\left(L/\epsilon+L\sigma^{2}/\left(n\epsilon^{2}\sqrt{1-\sqrt{\rho_{W}}}\right)\right) for the nonconvex case, matching the existing lower bound up to a logarithmic factor, and improves the existing results for the strongly convex case by a factor of 𝒪 ~ ( 1 / ϵ ) \tilde{\mathcal{O}}\left(1/\sqrt{\epsilon}\right) , where ϵ \epsilon is the targeted accuracy, n n the number of nodes, L L the Lipschitz constant, ρ W \rho_{W} the spectrum gap of the graph, and σ \sigma the stochastic gradient variance. Numerical examples are provided to demonstrate the effectiveness of the proposed methods. keywords Distributed optimization, data heterogeneity, complexity analysis, gradient tracking, accelerated communication, Pareto-optimal Funding. This work was supported in parts by National Natural Science Foundation of China (NSFC) under Grants 62373323 and 62088101; The work was also partially funded by Swedish Research Council Distinguished Professor Grant 2017-01078, Knut and Alice Wallenberg Foundation Wallenberg Scholar Grant, and Swedish Strategic Research Foundation SUCCESS Grant FUS21-0026. MSC 90C06, 90C25, 90C26 1 Introduction With rapid growth in both data volume and device scale [ 21 ] , distributed optimization methods have gained increasing attention due to their wide range of applications such as in cooperative control [ 33 ] , distributed sensing [ 1 ] , large-scale machine learning [ 49 ] , distributed training of large language models (LLMs) [ 16 ] , to name a few. In this paper, we consider a distributed stochastic optimization problem jointly solved by n nodes over a network: \underset{x\in\mathbb{R}^{p}}{\min}f\left(x\right)=\frac{1}{n}\sum_{i=1}^{n}{\underset{:=f_{i}\left(x\right)}{\underbrace{\mathbb{E}_{\xi_{i}\sim\mathcal{D}_{i}}\left[f_{i}\left(x;\xi_{i}\right)\right]}}}, (1) where x\in\mathbb{R}^{p} is the global decision variable. The objective function f:\mathbb{R}^{p}\rightarrow\mathbb{R} is the sum of n local objective functions f_{i} , i=1,\dots,n , conditioned on the local data sample \xi_{i} with distribution \mathcal{D}_{i} . 1.1 Literature Review Decentralized stochastic gradient descent (DSGD) [ 39 ] is a simple yet efficient algorithm for solving problem ( 1 ). It performs stochastic gradient descent locally while communicating with neighbors to achieve consensus, which enables data parallelism and avoids communication bottlenecks in centralized architectures [ 32 ] . However, the native DSGD methods often struggle in scenarios with non-independent and identically distributed (non-i.i.d.) local datasets [ 24 , 12 ] . For ( 1 ), such a scenario corresponds to that the distribution \mathcal{D}_{i} is different. This data heterogeneity induces gradient drift in the sense that local gradients computed at each node deviate from the global gradient direction, necessitating decaying stepsizes to ensure exact convergence [ 35 , 24 ] . This requirement limits the applicability of DSGD in many real-world tasks, as non-i.i.d. data distributions are common. Many efforts have been made to address this issue of data heterogeneity in distributed optimization. Gradient tracking (GT) methods have gained popularity for mitigating the effect [ 51 , 11 , 41 , 23 , 46 , 48 ] . Notably, Xu et al. [ 51 ] proposed AugDGM, which introduces an auxiliary variable at each node to track the average of the local gradients, enabling exact convergence with a constant stepsize. This method has been extended to broader settings, including time-varying graphs [ 34 ] and directed graphs [ 38 , 40 ] , with convergence guarantees. Pu et al. [ 37 ] extended GT to the stochastic setting, introducing distributed stochastic gradient tracking (DSGT). They proved that DSGT achieves linear convergence to a neighborhood of the optimal solution, determined by the stochastic gradient noise. This extension enhances the applicability of GT, for instance, to many machine learning tasks. Although GT methods are robust to data heterogeneity, they exhibit a stronger dependence on the graph compared to DSGD [ 13 , 18 ] , leading to increased communication overhead. The consensus alternating direction method of multipliers (C-ADMM) [ 27 ] and its inexact variant [ 6 ] also exhibit robustness to data heterogeneity. However, they require either solving a subproblem exactly at each iteration, which incurs high computation overhead, or assuming a well-structured objective function to enable linear approximations, which limits their applicability. These observations highlight the need for more efficient algorithms, especially in resource-constrained scenarios that involve both communication and computation. To mitigate the high communication burden, many improved GT-based methods have been developed [ 36 , 30 , 43 , 10 , 42 ] . A popular strategy is to skip some communication steps and perform local updates only. For instance, FedAvg [ 32 ] (also known as Local SGD [ 44 ] ) is widely used in federated learning [ 8 , 17 ] , where periodic communication occurs between server and worker nodes, with partial node participation to reduce communication overhead. In decentralized settings, Nguyen et al. [ 36 ] introduced LU-GT, a variant of DSGT that uses multiple local updates, and provided communication complexity results matching those of Local SGD for nonconvex objectives. Subsequently, Liu et al. [ 30 ] proposed the gradient-sum-tracking method K-GT, which reduces communication complexity by achieving lower stochastic gradient variance. However, both [ 36 ] and [ 30 ] overlook the side effect of how the local updates increase computation complexity due to worse inter-node consensus. Another approach is to randomly or periodically communicate over a subset of the graph’s edges to reduce communication [ 39 , 25 , 26 , 52 ] . These methods can be seen as approximate asynchronous update schemes, which often require specific connectivity assumptions [ 39 ] or particular topologies, such as exponential graphs [ 52 ] . In contrast to directly skipping certain communications as in Local SGD [ 44 ] , another strategy involves using accelerated consensus protocols. For instance, Chebyshev acceleration [ 43 , 10 ] and accelerated gossip [ 28 , 31 , 54 ] methods enable the distributed algorithm to behave more like a centralized algorithm. In particular, Song et al. [ 43 ] introduced an optimal gradient tracking (OGT) method with Chebyshev acceleration for deterministic optimization problems with smooth and strongly convex objective functions. Leveraging prior knowledge of the network topology, they demonstrated that a limited number of communication steps per round could enable the distributed algorithm to replicate centralized updates. Building on this, the stochastic