×

Distributed stochastic optimization algorithm with non-consistent constraints in time-varying unbalanced networks. (English) Zbl 07909866

Summary: This study focuses on a class of distributed optimization problems with non-consistent local set constraints in time-varying unbalanced networks. Considering that each agent only has access to local gradient information with random errors, this paper proposes a distributed stochastic gradient projection algorithm. Under some conditions of random errors and a uniformly joint strongly connected topology, it is shown that the local decision states of all agents converge to a common optimal solution with a probability of one, achieving a sublinear convergence rate of \(\mathcal{O}(\ln k/\sqrt{k})\). Notably, under the condition that at least one local function exhibits strong convexity, the algorithm achieves a faster sublinear convergence rate of \(\mathcal{O}(1/k)\). These theoretical results are validated through numerical simulations. Furthermore, this paper applies the proposed algorithm to solve for the unknown parameters in distributed linear regression problems with incomplete data. Numerical results indicate that the algorithm not only aligns with the convergence properties reported in existing literature but also demonstrates significant superiority in convergence speed. This important discovery not only lays a solid theoretical foundation for the further application and extension of the algorithm but also reveals its immense potential in solving practical problems.

MSC:

90C25 Convex programming
90C15 Stochastic programming
93A14 Decentralized systems
93E15 Stochastic stability in control theory
Full Text: DOI

References:

[1] Jaleel, H.; Shamma, J. S., Distributed optimization for robot networks: From real-time convex optimization to game-theoretic self-organization, Proc. IEEE, 108, 11, 1953-1967, 2020
[2] Park, J.; Samarakoon, S.; Elgabli, A., Communication-efficient and distributed learning over wireless networks: Principles and applications, Proc. IEEE, 109, 5, 796-819, 2021
[3] Wen, G.; Yu, X.; Liu, Z., Recent progress on the study of distributed economic dispatch in smart grid: an overview, Front. Inf. Technol. Electron. Eng., 22, 1, 25-39, 2021
[4] Lin, P.; Qi, H., Distributed gradient-based sampling algorithm for least-squares in switching multi-agent networks, Sci. China Inf. Sci., 63, 9, Article 199203 pp., 2020
[5] Nedić, A.; Ozdaglar, A., Distributed subgradient methods for multi-agent optimization, IEEE Trans. Autom. Control, 54, 1, 48-61, 2009 · Zbl 1367.90086
[6] Nedić, A.; Ozdaglar, A.; Parrilo, P. A., Constrained consensus and optimization in multi-agent networks, IEEE Trans. Autom. Control, 55, 4, 922-938, 2010 · Zbl 1368.90143
[7] Mai, V. S.; Abed, E. H., Distributed optimization over directed graphs with row stochasticity and constraint regularity, Automatica, 102, 94-104, 2019 · Zbl 1415.93294
[8] Li, H.; Lü, Q.; Chen, G.; Huang, T.; Dong, Z., Distributed constrained optimization over unbalanced directed networks using asynchronous broadcast-based algorithm, IEEE Trans. Autom. Control, 66, 3, 1102-1115, 2020 · Zbl 1536.93329
[9] Liu, H.; Zheng, W. X.; Yu, W., Distributed discrete-time algorithms for convex optimization with general local constraints on weight-unbalanced digraph, IEEE Trans. Control Netw. Syst., 8, 1, 51-64, 2020 · Zbl 07588074
[10] Xin, R.; Khan, U. A., A linear algorithm for optimization over directed graphs with geometric convergence, IEEE Control Syst. Lett., 2, 3, 315-320, 2018
[11] Pu, S.; Shi, W.; Xu, J.; Nedić, A., Push-pull gradient methods for distributed optimization in networks, IEEE Trans. Autom. Control, 66, 1, 1-16, 2021 · Zbl 1536.93337
[12] Nedić, A.; Olshevsky, A., Distributed optimization over time-varying directed graphs, IEEE Trans. Autom. Control, 60, 3, 601-615, 2014 · Zbl 1360.90262
[13] Saadatniaki, F.; Xin, R.; Khan, U. A., Decentralized optimization over time-varying directed graphs with row and column-stochastic matrices, IEEE Trans. Autom. Control, 65, 11, 4769-4780, 2020 · Zbl 1536.93026
[14] Liang, S.; Yin, G., Dual averaging push for distributed convex optimization over time-varying directed graph, IEEE Trans. Autom. Control, 65, 4, 1785-1791, 2019 · Zbl 07256302
[15] Yu, W.; Liu, H.; Zheng, W. X.; Zhu, Y., Distributed discretetime convex optimization with nonidentical local constraints over time-varying unbalanced directed graphs, Automatica, 134, Article 109899 pp., 2021 · Zbl 1478.93258
[16] Heymans, M. W.; Twisk, J. W., Handling missing data in clinical research, J. Clin. Epidemiol., 151, 185-188, 2022
[17] Gholami, M. R.; Jansson, M.; Ström, E. G.; Sayed, A. H., Diffusion estimation over cooperative multi-agent networks with missing data, IEEE Trans. Signal Inf. Process. Netw., 2, 3, 276-289, 2016
[18] Pu, S.; Olshevsky, A.; Paschalidis, I. C., Asymptotic network independence in distributed stochastic optimization for machine learning: Examining distributed and centralized stochastic gradient descent, IEEE Signal Process. Mag., 37, 3, 114-122, 2020
[19] Nedić, A.; Olshevsky, A., Stochastic gradient-push for strongly convex functions on time-varying directed graphs, IEEE Trans. Autom. Control, 61, 12, 3936-3947, 2016 · Zbl 1359.90142
[20] Chen, Y.; Hashemi, A.; Vikalo, H., Communication-efficient variance-reduced decentralized stochastic optimization over time-varying directed graphs, IEEE Trans. Autom. Control, 67, 12, 6583-6594, 2021 · Zbl 1541.93378
[21] Lei, J.; Yi, P.; Chen, J.; Hong, Y., Distributed variable samplesize stochastic optimization with fixed step-sizes, IEEE Trans. Autom. Control, 67, 10, 5630-5637, 2022 · Zbl 1541.93384
[22] Nguyen, D. T.A.; Nguyen, D. T.; Nedić, A., Distributed stochastic optimization with gradient tracking over time-varying directed networks, (2023 57th Asilomar Conference on Signals, Systems, and Computers, vol. 10477004, 2023, IEEE), 1605-1609
[23] Ram, S. Sundhar.; Nedić, A.; Veeravalli, V. V., Distributed stochastic subgradient projection algorithms for convex optimization, J. Optim. Theory Appl., 147, 516-545, 2010 · Zbl 1254.90171
[24] Wang, Y.; Lin, P.; Hong, Y., Distributed regression estimation with incomplete data in multi-agent networks, Sci. China Inf. Sci., 61, 1-14, 2018
[25] Zhu, J.; Xie, P.; Zhang, M.; Zheng, R.; Xing, L.; Wu, Q., Distributed stochastic subgradient projection algorithms based on weight-balancing over time-varying directed graphs, Complexity, 19, 4, 5413-5422, 2019
[26] Wang, Z.; Zhang, J.; Chang, T. H., Distributed stochastic consensus optimization with momentum for nonconvex nonsmooth problems, IEEE Trans. Signal Process., 69, 4486-4501, 2021 · Zbl 07591640
[27] Jiang, X.; Zeng, X.; Sun, J.; Chen, J., Distributed stochastic gradient tracking algorithm with variance reduction for non-convex optimization, IEEE Trans. Neural Netw. Learn. Syst., 34, 9, 5310-5321, 2022
[28] Chen, Y.; Hashemi, A.; Vikalo, H., Accelerated Distributed Stochastic Non-Convex Optimization over Time-Varying Directed Networks ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing, 1-5, 2023, IEEE
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.