2025/09/11 by Huang, Yan, Xu, Jinming, Chai, Li +2
#90C06 #90C25 #90C26 #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2509.18129
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 O ( L/ε+Lσ2/( nε2 √(1-√(ρW)) ) ) 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 O ( 1/√ε ), where ε is the targeted accuracy, n the number of nodes, L the Lipschitz constant, ρW the spectrum gap of the graph, and σ the stochastic gradient variance. Numerical examples are provided to demonstrate the effectiveness of the proposed methods.