本文考虑无向网络上的分布式优化问题,其全局目标函数值是网络上所有局部目标函数的平均值。受集中式自适应梯度方法的启发,本文提出了一种新的分布式自适应梯度跟踪算法,每个智能体能够在无需手动调参、也无需掌握目标函数全局信息的情况下,仅利用本地梯度信息来自适应地更新步长。当局部目标函数满足光滑且强凸的假设时,本文证明了该算法产生的迭代序列能够线性地收敛至最优解。在分布式线性回归问题的数值实验中,凭借更优的步长更新机制,该算法比使用固定步长的分布式梯度算法及现有的分布式自适应算法具有更优的收敛性能。
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.
[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.
北大中文核心期刊