Distributed accelerated Nash equilibrium learning for two-subnetwork zero-sum game with bilinear coupling

Xianlin Zeng; Lihua Dou; Jinqiang Cui

Kybernetika (2023)

  • Volume: 59, Issue: 3, page 418-436
  • ISSN: 0023-5954

Abstract

top
This paper proposes a distributed accelerated first-order continuous-time algorithm for O ( 1 / t 2 ) convergence to Nash equilibria in a class of two-subnetwork zero-sum games with bilinear couplings. First-order methods, which only use subgradients of functions, are frequently used in distributed/parallel algorithms for solving large-scale and big-data problems due to their simple structures. However, in the worst cases, first-order methods for two-subnetwork zero-sum games often have an asymptotic or O ( 1 / t ) convergence. In contrast to existing time-invariant first-order methods, this paper designs a distributed accelerated algorithm by combining saddle-point dynamics and time-varying derivative feedback techniques. If the parameters of the proposed algorithm are suitable, the algorithm owns O ( 1 / t 2 ) convergence in terms of the duality gap function without any uniform or strong convexity requirement. Numerical simulations show the efficacy of the algorithm.

How to cite

top

Zeng, Xianlin, Dou, Lihua, and Cui, Jinqiang. "Distributed accelerated Nash equilibrium learning for two-subnetwork zero-sum game with bilinear coupling." Kybernetika 59.3 (2023): 418-436. <http://eudml.org/doc/299580>.

@article{Zeng2023,
abstract = {This paper proposes a distributed accelerated first-order continuous-time algorithm for $O(\{1\}/\{t^2\})$ convergence to Nash equilibria in a class of two-subnetwork zero-sum games with bilinear couplings. First-order methods, which only use subgradients of functions, are frequently used in distributed/parallel algorithms for solving large-scale and big-data problems due to their simple structures. However, in the worst cases, first-order methods for two-subnetwork zero-sum games often have an asymptotic or $O(1/t)$ convergence. In contrast to existing time-invariant first-order methods, this paper designs a distributed accelerated algorithm by combining saddle-point dynamics and time-varying derivative feedback techniques. If the parameters of the proposed algorithm are suitable, the algorithm owns $O(1/t^2)$ convergence in terms of the duality gap function without any uniform or strong convexity requirement. Numerical simulations show the efficacy of the algorithm.},
author = {Zeng, Xianlin, Dou, Lihua, Cui, Jinqiang},
journal = {Kybernetika},
keywords = {two-subnetwork zero-sum game; distributed accelerated algorithm; Nash equilibrium learning; nonsmooth function; continuous-time algorithm},
language = {eng},
number = {3},
pages = {418-436},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Distributed accelerated Nash equilibrium learning for two-subnetwork zero-sum game with bilinear coupling},
url = {http://eudml.org/doc/299580},
volume = {59},
year = {2023},
}

TY - JOUR
AU - Zeng, Xianlin
AU - Dou, Lihua
AU - Cui, Jinqiang
TI - Distributed accelerated Nash equilibrium learning for two-subnetwork zero-sum game with bilinear coupling
JO - Kybernetika
PY - 2023
PB - Institute of Information Theory and Automation AS CR
VL - 59
IS - 3
SP - 418
EP - 436
AB - This paper proposes a distributed accelerated first-order continuous-time algorithm for $O({1}/{t^2})$ convergence to Nash equilibria in a class of two-subnetwork zero-sum games with bilinear couplings. First-order methods, which only use subgradients of functions, are frequently used in distributed/parallel algorithms for solving large-scale and big-data problems due to their simple structures. However, in the worst cases, first-order methods for two-subnetwork zero-sum games often have an asymptotic or $O(1/t)$ convergence. In contrast to existing time-invariant first-order methods, this paper designs a distributed accelerated algorithm by combining saddle-point dynamics and time-varying derivative feedback techniques. If the parameters of the proposed algorithm are suitable, the algorithm owns $O(1/t^2)$ convergence in terms of the duality gap function without any uniform or strong convexity requirement. Numerical simulations show the efficacy of the algorithm.
LA - eng
KW - two-subnetwork zero-sum game; distributed accelerated algorithm; Nash equilibrium learning; nonsmooth function; continuous-time algorithm
UR - http://eudml.org/doc/299580
ER -

References

top
  1. Alkousa, M. S., Gasnikov, A. V., Dvinskikh, D. M., Kovalev, D. A., Stonyakin, F. S., , Comput. Math. and Math. Phys. 60 (2020), 1787-1787. MR4184700DOI
  2. Attouch, H., Chbani, Z., Riahi, H., , ESAIM: COCV 25 (2019), 2. MR3943364DOI
  3. Aubin, J. P., Cellina, A., Differential Inclusions., Springer-Verlag, Berlin 1984. MR0755330
  4. Beck, A., Teboulle, M., , SIAM J. Imaging Sci. 21 (2009), 1, 183-202. MR2486527DOI
  5. Bertsekas, D. P., Convex Optimization Algorithms., Athena Scientific, Belmont 2015. MR3558548
  6. Chambolle, A., Pock, T., , J. Math. Imaging Vis. 40 (2011), 1, 120-145. MR2782122DOI
  7. Chen, Y., Lan, G., Ouyang, Y., , SIAM J. Control Optim. 24 (2014), 4, 1779-1814. MR3272627DOI
  8. Chen, S., Liang, S., , Kybernetika 56 (2020), 3, 559-577. MR4131743DOI
  9. Chen, Z., Liang, S., , Kybernetika 58 (2022), 1, 123-144. MR4405950DOI
  10. Chen, G., Ming, Y., Hong, Y., Yi, P., , Automatica 123 (2021), 109313. MR4164533DOI
  11. Chen, J., Sun, J., Wang, G., , Engineering 8 (2022), 1-5. DOI
  12. Cherukuri, A., Gharesifard, B., Cortés, J., , SIAM J. Control Optim. 55 (2017), 1, 486-511. MR3612173DOI
  13. Deng, Z., , Automatica 132 (2021), 109794. MR4283791DOI
  14. Deng, Z., , Automatica 135 (2022), 109980. MR4335720DOI
  15. Gharesifard, B., Cortés, J., , Automatica 49 (2013), 6, 1683-1692. MR3049216DOI
  16. Goebel, R., , Syst. Control. Lett. 108 (2017), 16-22. MR3709078DOI
  17. He, X., Hu, R., Fang, Y. P., , SIAM J. Control Optim. 59 (2021), 5, 3278-3301. MR4315476DOI
  18. Huang, S., Lei, J., Hong, Y., , IEEE Trans. Automat. Control , 2022. MR4557578DOI
  19. Huang, S., Lei, J., Hong, Y., Shanbhag, U. V., No-regret distributed learning in two-network zero-sum games., In: 60th IEEE Conference on Decision and Control (CDC), 2021, pp. 924-929. 
  20. Ibaraki, T., Katoh, N., Resource Allocation Problems: Algorithmic Approaches., MIT Press, Cambridge 1988. MR0937050
  21. Khan, S., Tufail, M., Khan, M. T., Khan, Z. A., Iqbal, J., Wasim, A., A novel framework for multiple ground target detection, recognition and inspection in precision agriculture applications using a UAV., Unmanned Syst. 10 (2022), 1, 45-56. 
  22. Kia, S. S., Cortés, J., Martínez, S., , Automatica 55 (2015), 254-264. MR3336675DOI
  23. Li, P., Hu, J., Qiu, L., Zhao, Y., Ghosh, B. K., , IEEE Trans. Control. Netw. Syst9 (2022), 1, 356-366. MR4450544DOI
  24. Lou, Y., Hong, Y., Xie, L., Shi, G., Johansson, K. H., , IEEE Trans. Automat. Control 61 (2016), 10, 2920-2935. MR3554031DOI
  25. Mo, L., Yu, Y., Ren, G., Yuan, X., , J. Syst. Sci. Complex 35 (2022), 105-122. MR4376657DOI
  26. Nesterov, Y., A method of solving a convex programming problem with convergence rate O ( 1 / k 2 ) ., Soviet Math. Doklady 27 (1983), 372-376. MR0701288
  27. Nesterov, Y., , Math Program. 103 (2005), 1, 127-152. MR2166537DOI
  28. Paoli, L. A., , Math. Models Methods Appl. Sci. 10 (2000), 6, 815-831. MR1771507DOI
  29. Peng, Z., Luo, R., Hu, J., Shi, K., Ghosh, B. K., 10.1109/TCSI.2022.3177407, IEEE Trans. Circuits Syst. I Regular Papers 69 (2022), 9, 3689-3700. DOI10.1109/TCSI.2022.3177407
  30. Shi, B., Du, S. S., Jordan, M. I., Su, W. J., , Math. Program. 195 (2022), 79-148. MR4499055DOI
  31. Su, W., Boyd, S., Candes, E. J., A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights., Adv. Neural Inf. Process. Syst. 3 (2015), 1, 2510-2518. MR3555044
  32. Vassilis, A., Jean-Francois, A., Charles, D., , SIAM J. Control. Optim. 29 (2018), 1, 551-574. MR3766971DOI
  33. Wang, Q., Chen, J., Xin, B., Zeng, X., , IEEE Trans. Syst. Man Cybern. Syst. 51 (2021), 7, 4588-4598. DOI
  34. Wang, M., Li, L., Dai, Q., Shi, F., , J. Syst. Sci. Complex 34 (2022), 2231-2249. DOI
  35. Wang, Y., Lin, P., Qin, H., , Kybernetika 53 (2017), 4, 595-611. MR3730254DOI
  36. Wang, D., Wang, Z., Wu, Z., Wang, W., Distributed convex optimization for nonlinear multi-agent systems disturbed by a second-order stationary process over a digraph., Sci. China Inf. Sci. 65 (2022), 132201. MR4381757
  37. Wibisono, A., Wilson, A. C., Jordan, M. I., , Proc. Natl. Acad. Sci. 113 (2016), 47, 7351-7358. MR3582442DOI
  38. Wu, C., Fang, H., Yang, Q., Zeng, X., Wei, Y., Chen, J., , IEEE Trans. Cybernet. 53 (2023), 2, 1195-1207. DOI
  39. Wu, Y., Liang, Q., Zhao, Y., Hu, J., Xiang, L., 10.1007/s11432-020-3191-x, Sci. China Inf. Sci. 66 (2023), 139204. DOI10.1007/s11432-020-3191-x
  40. Wu, Y., Liang, Q., Zhao, Y., Hu, J., Xiang, L., 10.1007/s11432-021-3485-0, Sci. China Inf. Sci. 66 (2023), 189202. DOI10.1007/s11432-021-3485-0
  41. Xie, S., Wang, L., Nazari, M. H., Yin, G., Li, G., 10.1007/s11432-022-3582-5, Sci. China Inf. Sci. 65 (2022), 222205. MR4510580DOI10.1007/s11432-022-3582-5
  42. Xu, Y., , SIAM J. Optim. 27 (2018), 3, 1459-1484. MR3679324DOI
  43. Xu, Y., Zhang, S., , Comput. Optim. Appl. 70 (2018), 91-128. MR3780462DOI
  44. Yang, R., Liu, L., Feng, G., , Unmanned Syst. 2022. DOI
  45. Yang, S., Wang, J., Liu, Q., , IEEE Trans. Automat. Control 64 (2019), 4, 358-1372. MR3936416DOI
  46. Ye, M., Hu, G., Xu, S., , Automatica 114 (2020), 108815. MR4053524DOI
  47. Ye, M., Yin, J., Yin, L., , IEEE Trans. Automat. Control. MR4504365DOI
  48. Zeng, X., Chen, J., Liang, S., Hong, Y., , Automatica 103 (2019), 20-26. MR3908257DOI
  49. Zeng, X., Dou, L., Chen, J., Accelerated first-order continuous-time algorithm for solving convex-concave bilinear saddle point problem., In: 21st IFAC World Congress, Berlin 2020. 
  50. Zeng, X., Lei, J., Chen, J., , IEEE Trans. Automat. Control. DOI
  51. Zhou, H., Zeng, X., Hong, Y., , IEEE Trans. Automat. Control 64 (2019), 11, 4661-4667. MR4030790DOI

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.