This paper studies distributed optimization over undirected networks to minimize the average of local objective functions. Inspired by centralized adaptive gradient methods, we propose a novel distributed adaptive gradient tracking algorithm. The proposed algorithm enables each agent to adaptively update its step size using only local gradient information, completely eliminating the need for manual parameter tuning or global information about the objective functions. For smooth and strongly convex local objective functions, we prove that the generated iteration sequence converges linearly to the optimal solution. Numerical experiments on distributed linear regression problems demonstrate that, owing to a superior step-size update mechanism, the proposed algorithm achieves better convergence performance in comparison with existing distributed methods with fixed step sizes and adaptive step sizes.
MU Jiaxin
,
GAO Juan
,
LIU Xinwei
. A distributed adaptive gradient tracking algorithm over multi-agent networks[J]. Operations Research Transactions, 2026
, 30(3)
: 23
-40
.
DOI: 10.15960/j.cnki.issn.1007-6093.2026.03.002
[1] 陈宏崟, 程郁琨, 邓小铁, 等. 拍卖机制设计在区块链中的应用与挑战 [J]. 运筹学学报, 2023, 27(1): 1-29.
[2] 王祥丰, 李文浩. 机器学习驱动的多智能体路径搜寻算法综述 [J]. 运筹学学报, 2023, 27(4): 106-135.
[3] Nedić A, Ozdaglar A. Distributed subgradient methods for multi-agent optimization [J]. IEEE Transactions on Automatic Control, 2009, 54(1): 48-61.
[4] Tsitsiklis J, Bertsekas D, Athans M. Distributed asynchronous deterministic and stochastic gradient optimization algorithms [J]. IEEE Transactions on Automatic Control, 1986, 31(9): 803-812.
[5] Yuan K, Ling Q, Yin W. On the convergence of decentralized gradient descent [J]. SIAM Journal on Optimization, 2016, 26(3): 1835-1854.
[6] Shi W, Ling Q, Wu G, et al. EXTRA: an exact first-order algorithm for decentralized consensus optimization [J]. SIAM Journal on Optimization, 2015, 25(2): 944-966.
[7] Yuan K, Ying B, Zhao X, et al. Exact diffusion for distributed optimization and learning|Part I: algorithm development [J]. IEEE Transactions on Signal Processing, 2018, 67(3): 708-723.
[8] Xu J, Zhu S, Soh Y C, et al. Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes [C]//54th IEEE Conference on Decision and Control, 2015: 2055-2060.
[9] Nedić A, Olshevsky A, Shi W, et al. Geometrically convergent distributed optimization with uncoordinated step-sizes [C]//2017 American Control Conference, 2017: 3950-3955.
[10] Nedić A, Olshevsky A, Shi W. Achieving geometric convergence for distributed optimization over time-varying graphs [J]. SIAM Journal on Optimization, 2017, 27(4): 2597-2633.
[11] Qu G, Li N. Harnessing smoothness to accelerate distributed optimization [J]. IEEE Transactions on Control of Network Systems, 2017, 5(3): 1245-1260.
[12] Tian Y, Sun Y, Scutari G. Achieving linear convergence in distributed asynchronous multiagent optimization [J]. IEEE Transactions on Automatic Control, 2020, 65(12): 5264-5279.
[13] Sun Y, Scutari G, Daneshmand A. Distributed optimization based on gradient tracking revisited: enhancing convergence rate via surrogation [J]. SIAM Journal on Optimization, 2022, 32(2): 354-385.
[14] Wu T, Li Z, Sun Y. The effectiveness of local updates for decentralized learning under data heterogeneity [J]. IEEE Transactions on Signal Processing, 2025, 73: 751-765.
[15] Xin R, Xi C, Khan U A. FROST|Fast row-stochastic optimization with uncoordinated stepsizes [J]. EURASIP Journal on Advances in Signal Processing, 2019, 2019: 1-14.
[16] Malitsky Y, Mishchenko K. Adaptive gradient descent without descent [C]//International Conference on Machine Learning, 2020: 6702-6712.
[17] Latafat P, Themelis A, Stella L, et al. Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient [J]. Mathematical Programming, 2025, 213(1- 2): 433-471.
[18] Malitsky Y, Mishchenko K. Adaptive proximal gradient method for convex optimization [C]//Advances in Neural Information Processing Systems, 2024: 100670-100697.
[19] Zhou D, Ma S, Yang J. AdaBB: adaptive Barzilai-Borwein method for convex optimization [J]. Mathematics of Operations Research, 2026, 51(1): 715-745.
[20] Zargham M, Ribeiro A, Jadbabaie A. A distributed line search for network optimization [C]//2012 American Control Conference, 2012: 472-477.
[21] Gao J, Liu X W, Dai Y H, et al. Achieving geometric convergence for distributed optimization with Barzilai-Borwein step sizes [J]. Science China Information Sciences, 2022, 65(4): 149204.
[22] Chen Z, Wang Y. Distributed optimization and learning with automated stepsizes [C]//IEEE 63rd Conference on Decision and Control, 2024: 3121-3126.
[23] Ghaderyan D, Werner S. AdGT: decentralized gradient tracking with tuning-free per-agent stepsize [PP/OL]. (2026-01-06)[2026-06-26]. https://doi.org/10.48550/arXiv.2504.15196.
[24] Ghaderyan D, Aybat N S, Aguiar A P, et al. A fast row-stochastic decentralized method for distributed optimization over directed graphs [J]. IEEE Transactions on Automatic Control, 2023, 69(1): 275-289.
[25] Xin R, Khan U A. A linear algorithm for optimization over directed graphs with geometric convergence [J]. IEEE Control Systems Letters, 2018, 2(3): 315-320.
