Distributed dynamic stochastic approximation algorithm over time-varying networks

Abstract

In this paper, a distributed stochastic approximation algorithm is proposed to track the dynamic root of a sum of time-varying regression functions over a network. Each agent updates its estimate by using the local observation, the dynamic information of the global root, and information received from its neighbors. Compared with similar works in optimization area, we allow the observation to be noise-corrupted, and the noise condition is much weaker. Furthermore, instead of the upper bound of the estimate error, we present the asymptotic convergence result of the algorithm. The consensus and convergence of the estimates are established. Finally, the algorithm is applied to a distributed target tracking problem and the numerical example is presented to demonstrate the performance of the algorithm.

Keywords

Distributed algorithm / Dynamic stochastic approximation algorithm / Time-varying network

References

[1] JadbabaieA., LinJ., MorseA. S.. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans. Autom. Control, 2003, 48(6):988-1001

[2] RenWei, BeardR. W.. Consensus seeking in multiagent systems under dynamically changing interaction topologies. IEEE Trans. Autom. Control, 2005, 50(5):655-661

[3] Olfati-SaberR., FaxA. J., MurrayR. M.. Consensus and cooperation in networked multi-agent systems. Proc. IEEE, 2007, 95(1):215-233

[4] FengW., ChenH. -F.. Output consensus of networked hammerstein and wiener systems. SIAM J. Control Optim., 2019, 57(2):1230-1254

[5] YiP., HongY., LiuF.. Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and application to economic dispatch of power systems. Automatica, 2016, 74: 259-269

[6] A. Nedić, A. Olshevsky, W. Shi, in 2018 IEEE Conf. Decis. Control (CDC). Improved convergence rates for distributed resource allocation (IEEE, 2018), pp. 172–177. https://doi.org/10.1109/cdc.2018.8619322.

[7] Y. Kuriki, T. Namerikawa, in 2014 Amer. Control Conf.Consensus-based cooperative formation control with collision avoidance for a multi-uav system (IEEE, 2014), pp. 2077–2082. https://doi.org/10.1109/acc.2014.6858777.

[8] AeronS., SaligramaV., CastanonD. A.. Efficient sensor management policies for distributed target tracking in multihop sensor networks. IEEE Trans. Sig. Process., 2008, 56(6):2562-2574

[9] NedicA., OzdaglarA.. Distributed subgradient methods for multi-agent optimization. IEEE Trans. Autom. Control, 2009, 54(1):48

[10] NedicA., OzdaglarA., ParriloP. A.. Constrained consensus and optimization in multi-agent networks. IEEE Trans. Autom. Control, 2010, 55(4):922-938

[11] A. Simonetto, G. Leus, Distributed asynchronous time-varying constrained optimization (IEEE, 2014). https://doi.org/10.1109/acssc.2014.7094854.

[12] JakubiecF. Y., D-mapA. R.. Distributed maximum a posteriori probability estimation of dynamic systems. IEEE Trans. Sig. Process., 2012, 61(2):450-466

[13] YiX., LiX., XieL., JohanssonK. H.. Distributed online convex optimization with time-varying coupled inequality constraints. IEEE Trans. Sig. Process., 2020, 68: 731-746

[14] ShahrampourS., JadbabaieA.. Distributed online optimization in dynamic environments using mirror descent. IEEE Trans. Autom. Control, 2017, 63(3):714-725

[15] BajovicD., XavierJ., SinopoliB., MouraJ. M. F., et al.. Distributed detection via gaussian running consensus: Large deviations asymptotic analysis. IEEE Trans. Sig. Process., 2011, 59(9):4381-4396

[16] M. Ye, H. Guoqiang, in 2015 54th IEEE Conference on Decision and Control (CDC). Distributed optimization for systems with time-varying quadratic objective functions (IEEE, 2015), pp. 3285–3290. https://doi.org/10.1109/cdc.2015.7402713.

[17] SimonettoA., KoppelA., MokhtariA., LeusG., RibeiroA.. Decentralized prediction-correction methods for networked time-varying convex optimization. IEEE Trans. Autom. Control, 2017, 62(11):5724-5738

[18] FazlyabM., PaternainS., PreciadoV. M., RibeiroA.. Prediction-correction interior-point method for time-varying convex optimization. IEEE Trans. Autom. Control, 2017, 63(7):1973-1986

[19] ChenH. -F., DuncanT. E., Pasik-DuncanB.. A kiefer-wolfowitz algorithm with randomized differences. IEEE Trans. Autom. Control, 1999, 44(3):442-453

[20] KushnerH. J., YinG.. Asymptotic properties of distributed and communicating stochastic approximation algorithms. SIAM J. Control Optim., 1987, 25(5):1266-1290

[21] BianchiP., FortG., HachemW.. Performance of a distributed stochastic approximation algorithm. IEEE Trans. Inform. Theory, 2013, 59(11):7405-7418

[22] LeiJ., ChenH. -F.. Distributed stochastic approximation algorithm with expanding truncations. IEEE Trans. Autom. Control, 2020, 65(2):664-679

[23] V. Dupač, A dynamic stochastic approximation method. Ann. Math. Stat., 1695–1702 (1965).

[24] ChenH. -F., UosakiK.. Convergence analysis of dynamic stochastic approximation. Syst. Control Lett., 1998, 35(5):309-315

[25] D. Acemoglu, A. Nedic, A. Ozdaglar, in 2008 47th IEEE Conference on Decision and Control. Convergence of rule-of-thumb learning rules in social networks (IEEE, 2008), pp. 1714–1720. https://doi.org/10.1109/cdc.2008.4739167.

[26] S. Shahrampour, S. Rakhlin, A. Jadbabaie, in Advances in Neural Information Processing Systems. Online learning of dynamic parameters in social networks, (2013). https://doi.org/10.4018/978-1-4666-1815-2.ch006.

[27] F. Kewei, H. -F. Chen, W. Zhao, in 2018 37th Chinese Control Conference (CCC). Distributed stochastic approximation algorithm for time-varying regression function over network (IEEE, 2018), pp. 1925–1930. https://doi.org/10.23919/chicc.2018.8483554.

[28] H. -F. Chen, Stochastic Approximation and Its Applications, vol. 64 (Springer Science & Business Media, 2002). https://doi.org/10.1007/b101987.

[29] X. Yuan, C. Han, Z. Duan, M. Lei, in 2005 7th International Conference on Information Fusion, 2. Comparison and choice of models in tracking target with coordinated turn motion (IEEE, 2005), p. 6. https://doi.org/10.1109/icif.2005.1592032.

[30] JacksonM. O.. Social and Economic Networks, 2010 US Princeton university press