Privacy-preserving dual stochastic push-sum algorithm for distributed constrained optimization. (English) Zbl 1517.90152
Summary: This paper investigates a private distributed optimization problem over a multi-agent network, where the goal is to cooperatively minimize the sum of all locally convex cost functions subject to coupled equality constraints over time-varying unbalanced directed networks while considering privacy concerns. To solve this problem, we integrate push-sum protocols with dual subgradient methods to design a private distributed dual stochastic push-sum algorithm. Under the assumption of convexity, we first establish the convergence of the algorithm in terms of dual variables, primal variables and constraint violations. Then we show that the algorithm has a sub-linear growth with order of \(O(\ln t/\sqrt{t})\). The result reveals that there is a tradeoff between the privacy level and the accuracy of the algorithm. Finally, the efficiency of the algorithm is verified numerically over two applications to the economic dispatch problems and electric vehicles charging control problems.
References:
| [1] | Aybat, N.S., Fallah, A., G��rbüzbalaban, M., A. Ozdaglar.: Robust accelerated gradient methods for smooth strongly convex functions. SIAM J. Optim. 30(1), 717-751 (2020) · Zbl 1461.62145 |
| [2] | Aybat, NS; Hamedani, EY, A distributed ADMM-like method for resource sharing over time-varying networks, SIAM J. Optim., 29, 4, 3036-3068 (2019) · Zbl 1427.90214 · doi:10.1137/17M1151973 |
| [3] | Beck, A.; Nedić, A.; Ozdaglar, A.; Teboulle, M., An \(O (1/k)\) gradient method for network resource allocation problems, IEEE Trans. Control of Netw. Syst., 1, 1, 64-73 (2014) · Zbl 1370.90290 · doi:10.1109/TCNS.2014.2309751 |
| [4] | Bekkerman, R.; Bilenko, M.; Langford, J., Scaling up machine learning: parallel and distributed approaches (2011), Cambridge: Cambridge University Press, Cambridge · doi:10.1017/CBO9781139042918 |
| [5] | Blondin, MJ; Hale, M., A decentralized multi-objective optimization algorithm, J. Optim. Theory Appl., 189, 2, 458-485 (2021) · Zbl 1471.90125 · doi:10.1007/s10957-021-01840-z |
| [6] | Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1058.90049 · doi:10.1017/CBO9780511804441 |
| [7] | Chang, TH; Nedić, A.; Scaglione, A., Distributed constrained optimization by consensus-based primal-dual perturbation method, IEEE Trans. Autom. Control., 59, 6, 1524-1538 (2014) · Zbl 1360.68775 · doi:10.1109/TAC.2014.2308612 |
| [8] | Dong, T.; Bu, X.; Hu, W., Distributed differentially private average consensus for multi-agent networks by additive functional Laplace noise, J. Franklin Inst., 357, 6, 3565-3584 (2020) · Zbl 1437.93119 · doi:10.1016/j.jfranklin.2019.12.027 |
| [9] | Du, B.; Zhou, J.; Sun, D., Improving the convergence of distributed gradient descent via inexact average consensus, J. Optim. Theory Appl., 185, 2, 504-521 (2020) · Zbl 1443.90270 · doi:10.1007/s10957-020-01648-3 |
| [10] | Duchi, JC; Agarwal, A.; Wainwright, MJ, Dual averaging for distributed optimization: convergence analysis and network scaling, IEEE Trans. Autom. Control., 57, 3, 592-606 (2012) · Zbl 1369.90156 · doi:10.1109/TAC.2011.2161027 |
| [11] | Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Theory of Cryptography Conference, pp. 265-284. Springer, Berlin, Heidelberg (2006) · Zbl 1112.94027 |
| [12] | Falsone, A.; Margellos, K.; Garatti, S.; Prandini, M., Dual decomposition for multi-agent distributed optimization with coupling constraints, Automatica, 84, 149-158 (2017) · Zbl 1376.93005 · doi:10.1016/j.automatica.2017.07.003 |
| [13] | Gu, C.; Li, J.; Wu, Z., An adaptive online learning algorithm for distributed convex optimization with coupled constraints over unbalanced directed graphs, J. Franklin Inst., 356, 13, 7548-7570 (2019) · Zbl 1418.93117 · doi:10.1016/j.jfranklin.2019.06.026 |
| [14] | Huang, Z., Mitra, S., Vaidya, N.: Differentially private distributed optimization. In: 2015 16th International Conference on Distributed Computing and Networking, pp. 1-10 (2015) |
| [15] | Jain, P., Kothari, P., Thakurta, A.: Differentially private online learning. In: Conference on Learning Theory. JMLR Workshop and Conference Proceedings, pp. 24-1 (2012) |
| [16] | Li, J.; Wu, Z.; Wu, C.; Long, Q.; Wang, X., An inexact dual fast gradient-projection method for separable convex optimization with linear coupled constraints, J. Optim. Theory Appl., 168, 1, 153-171 (2016) · Zbl 1332.90199 · doi:10.1007/s10957-015-0757-1 |
| [17] | Li, C.; Zhou, P.; Xiong, L.; Wang, Q.; Wang, T., Differentially private distributed online learning, IEEE Trans. Knowl. Data En., 30, 8, 1440-1453 (2018) · doi:10.1109/TKDE.2018.2794384 |
| [18] | Li, H.; Zhang, H.; Wang, Z.; Zhu, Y.; Han, Q., Distributed consensus-based multi-agent convex optimization via gradient tracking technique, J. Franklin Inst., 356, 6, 3733-3761 (2019) · Zbl 1411.93012 · doi:10.1016/j.jfranklin.2019.01.050 |
| [19] | Li, X.; Yi, X.; Xie, L., Distributed online optimization for multi-agent networks with coupled inequality constraints, IEEE Trans. Autom. Control., 66, 8, 3575-3591 (2020) · Zbl 1471.93019 · doi:10.1109/TAC.2020.3021011 |
| [20] | Lou, Y.; Yu, L.; Wang, S.; Yi, P., Privacy preservation in distributed subgradient optimization algorithms, IEEE Trans. Cybern., 48, 7, 2154-2165 (2017) · doi:10.1109/TCYB.2017.2728644 |
| [21] | Lü, Q.; Liao, X.; Xiang, T.; Li, H.; Huang, T., Privacy masking stochastic subgradient-push algorithm for distributed online optimization, IEEE Trans. Cybern., 51, 6, 3224-3237 (2020) · doi:10.1109/TCYB.2020.2973221 |
| [22] | Mao, S.; Tang, Y.; Dong, Z.; Meng, K.; Dong, ZY; Qian, F., A privacy preserving distributed optimization algorithm for economic dispatch over time-varying directed networks, IEEE Trans. Ind. Inform., 17, 3, 1689-1701 (2020) · doi:10.1109/TII.2020.2996198 |
| [23] | McSherry, F.D.: Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In: 2009 35th ACM SIGMOD International Conference on Management of Data, pp. 19-30 (2009) |
| [24] | Nedić, A.; Olshevsky, A., Distributed optimization over time-varying directed graphs, IEEE Trans. Autom. Control., 60, 3, 601-615 (2015) · Zbl 1360.90262 · doi:10.1109/TAC.2014.2364096 |
| [25] | Nedić, A.; Olshevsky, A., Stochastic gradient-push for strongly convex functions on time-varying directed graphs, IEEE Trans. Autom. Control, 12, 61, 3936-3947 (2016) · Zbl 1359.90142 · doi:10.1109/TAC.2016.2529285 |
| [26] | Nedić, A.; Ozdaglar, A., Distributed sub-gradient methods for multi-agent optimization, IEEE Trans. Autom. Control., 54, 1, 48-61 (2009) · Zbl 1367.90086 · doi:10.1109/TAC.2008.2009515 |
| [27] | Nozari, E.; Tallapragada, P.; Cortés, J., Differentially private distributed convex optimization via functional perturbation, IEEE Trans. Control Netw. Syst., 5, 1, 395-408 (2016) · Zbl 1507.90131 · doi:10.1109/TCNS.2016.2614100 |
| [28] | Ram, SS; Nedić, A.; Veeravalli, VV, Distributed stochastic subgradient projection algorithms for convex optimization, J. Optim. Theory Appl., 147, 3, 516-545 (2010) · Zbl 1254.90171 · doi:10.1007/s10957-010-9737-7 |
| [29] | Shi, Z.; Zhou, C., An improved distributed gradient-push algorithm for bandwidth resource allocation over wireless local area network, J. Optim. Theory Appl., 183, 3, 1153-1176 (2019) · Zbl 1432.90083 · doi:10.1007/s10957-019-01588-7 |
| [30] | Simonetto, A.; Jamali-Rad, H., Primal recovery from consensus-based dual decomposition for distributed convex optimization, J. Optim. Theory Appl., 168, 1, 172-197 (2016) · Zbl 1332.90203 · doi:10.1007/s10957-015-0758-0 |
| [31] | Wang, Y., Hale, M., Egerstedt, M., Dullerud, G.: Differentially private objective functions in distributed cloud-based optimization. In: 2016 55th IEEE Conference on Decision and Control, pp. 3688-3694. IEEE (2016) |
| [32] | Wang, S.; Li, C., Distributed stochastic algorithm for global optimization in networked system, J. Optim. Theory Appl., 179, 3, 1001-1007 (2018) · Zbl 1414.90293 · doi:10.1007/s10957-018-1355-9 |
| [33] | Wang, A.; Liu, W.; Li, T.; Huang, T., Privacy-preserving weighted average consensus and optimal attacking strategy for multi-agent networks, J. Franklin Inst., 358, 6, 3033-3050 (2021) · Zbl 1464.93073 · doi:10.1016/j.jfranklin.2021.01.039 |
| [34] | Xia, X.; Elaiw, AM, Optimal dynamic economic dispatch of generation: a review, Electr. Power Syst. Res., 80, 8, 975-986 (2010) · doi:10.1016/j.epsr.2009.12.012 |
| [35] | Yuan, D., Xu, S., Zhao, H.: Distributed primal-dual subgradient method for multiagent optimization via consensus algorithms. IEEE Trans. Syst. Man. Cybern. B. Cybern. 41(6), 1715-1724 (2011) |
| [36] | Zhang, T.; Zhu, Q., Dynamic differential privacy for ADMM-based distributed classification learning, IEEE Trans. Inf. Forensics Security, 12, 1, 172-187 (2016) · doi:10.1109/TIFS.2016.2607691 |
| [37] | Zhang, B.; Gu, C.; Li, J., Distributed convex optimization with coupling constraints over time-varying directed graphs, J. Ind. Manag. Optim., 17, 4, 2119-2138 (2021) · Zbl 1476.90342 · doi:10.3934/jimo.2020061 |
| [38] | Zhu, J.; Xu, C.; Guan, J.; Wu, DO, Differentially private distributed online algorithms over time-varying directed networks, IEEE Trans. Signal Process, 4, 1, 4-17 (2018) |
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.
