{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T15:49:09Z","timestamp":1778255349992,"version":"3.51.4"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,11,9]],"date-time":"2022-11-09T00:00:00Z","timestamp":1667952000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Ministry of Industry and Information Technology of the People\u2019s Republic of China","award":["2020-0103-3-1"],"award-info":[{"award-number":["2020-0103-3-1"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["91948303-1, 61803375, 12002380, 62106278, 62101575, and 61906210"],"award-info":[{"award-number":["91948303-1, 61803375, 12002380, 62106278, 62101575, and 61906210"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National University of Defense Technology Foundation","award":["ZK20-52"],"award-info":[{"award-number":["ZK20-52"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2023,2,28]]},"abstract":"<jats:p>\n            Decentralized online learning (online learning in decentralized networks) has been attracting more and more attention, since it is believed that decentralized online learning can help data providers cooperatively better solve their online problems without sharing their private data to a third party or other providers. Typically, the cooperation is achieved by letting the data providers exchange their models between neighbors, e.g., recommendation model. However, the best regret bound for a decentralized online learning algorithm is \ud835\udcaa(\n            <jats:italic>n<\/jats:italic>\n            \u221a\n            <jats:italic>T<\/jats:italic>\n            ), where\n            <jats:italic>n<\/jats:italic>\n            is the number of nodes (or users) and\n            <jats:italic>T<\/jats:italic>\n            is the number of iterations. This is clearly insignificant, since this bound can be achieved\n            <jats:italic>without<\/jats:italic>\n            any communication in the networks. This reminds us to ask a fundamental question:\n            <jats:italic>Can people really get benefit from the decentralized online learning by exchanging information?<\/jats:italic>\n            In this article, we studied when and why the communication can help the decentralized online learning to reduce the regret. Specifically, each loss function is characterized by two components: the adversarial component and the stochastic component. Under this characterization, we show that decentralized online gradient enjoys a regret bound\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( {\\mathcal {O}(\\sqrt {n^2TG^2 + n T \\sigma ^2})} \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , where\n            <jats:italic>G<\/jats:italic>\n            measures the magnitude of the adversarial component in the private data (or equivalently the local loss function) and \u03c3 measures the randomness within the private data. This regret suggests that people can get benefits from the randomness in the private data by exchanging private information. Another important contribution of this article is to consider the dynamic regret\u2014a more practical regret to track users\u2019 interest dynamics. Empirical studies are also conducted to validate our analysis.\n          <\/jats:p>","DOI":"10.1145\/3559765","type":"journal-article","created":{"date-parts":[[2022,9,2]],"date-time":"2022-09-02T11:21:55Z","timestamp":1662117715000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Decentralized Online Learning: Take Benefits from Others\u2019 Data without Sharing Your Own to Track Global Trend"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1355-8228","authenticated-orcid":false,"given":"Wendi","family":"Wu","sequence":"first","affiliation":[{"name":"Institute for Quantum Information &amp; State Key Laboratory of High Performance Computing, College of Computer Science and Technology, National University of Defense Technology, Changsha, Hunan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9258-1022","authenticated-orcid":false,"given":"Zongren","family":"Li","sequence":"additional","affiliation":[{"name":"Medical Big Data Research Center, Chinese PLA General Hospital, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8352-0092","authenticated-orcid":false,"given":"Yawei","family":"Zhao","sequence":"additional","affiliation":[{"name":"Medical Big Data Research Center, Chinese PLA General Hospital, China and School of Cyberspace Security, Dongguan University of Technology, Dongguan, Guangdong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6540-2583","authenticated-orcid":false,"given":"Chen","family":"Yu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Rochester, Rochester, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8543-3953","authenticated-orcid":false,"given":"Peilin","family":"Zhao","sequence":"additional","affiliation":[{"name":"Tencent AI Lab, Shenzhen, Guangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0240-8881","authenticated-orcid":false,"given":"Ji","family":"Liu","sequence":"additional","affiliation":[{"name":"Kwai Seattle AI Lab, Seattle, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3335-5700","authenticated-orcid":false,"given":"Kunlun","family":"He","sequence":"additional","affiliation":[{"name":"Medical Big Data Research Center, Chinese PLA General Hospital, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,11,9]]},"reference":[{"issue":"23","key":"e_1_3_2_2_2","first-page":"1","article-title":"A closer look at adaptive regret","volume":"17","author":"Adamskiy Dmitry","year":"2016","unstructured":"Dmitry Adamskiy, Wouter M. Koolen, Alexey Chernov, and Vladimir Vovk. 2016. A closer look at adaptive regret. J. Mach. Learn. Res. 17, 23 (2016), 1\u201321.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCNS.2015.2505149"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2018.2797423"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","unstructured":"Andr\u00e1s A. Bencz\u00far Levente Kocsis and R\u00f3bert P\u00e1lovics. 2018. Online machine learning in big data streams (unpublished).","DOI":"10.1007\/978-3-319-63962-8_326-1"},{"key":"e_1_3_2_6_2","first-page":"Paper 471","volume-title":"Proceedings of the Conference and Workshop on Neural Information Processing Systems (NIPS\u201912)","author":"Cesa-Bianchi Nicol\u00f2","year":"2012","unstructured":"Nicol\u00f2 Cesa-Bianchi, Pierre Gaillard, Gabor Lugosi, and Gilles Stoltz. 2012. Mirror descent meets fixed share (and feels no regret). In Proceedings of the Conference and Workshop on Neural Information Processing Systems (NIPS\u201912). Paper 471."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2016.02.023"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/11503415_14"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2209627"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/3045390.3045700"},{"key":"e_1_3_2_11_2","volume-title":"Proceedings of International Conference on International Conference on Machine Learning (ICML\u201913)","author":"Hall Eric C.","year":"2013","unstructured":"Eric C. Hall and Rebecca Willett. 2013. Dynamical models and tracking regret in online convex programming. In Proceedings of International Conference on International Conference on Machine Learning (ICML\u201913)."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2015.2404790"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1561\/2400000013"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007424614876"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2013.6760092"},{"key":"e_1_3_2_16_2","first-page":"398","volume-title":"Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS\u201915)","author":"Jadbabaie Ali","year":"2015","unstructured":"Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. 2015. Online optimization : Competing with dynamic comparators. In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS\u201915). 398\u2013406."},{"key":"e_1_3_2_17_2","first-page":"20185","volume-title":"Advances in Neural Information Processing Systems","author":"Jiang Jiyan","year":"2021","unstructured":"Jiyan Jiang, Wenpeng Zhang, Jinjie Gu, and Wenwu Zhu. 2021. Asynchronous decentralized online learning. In Advances in Neural Information Processing Systems. 20185\u201320196."},{"key":"e_1_3_2_18_2","first-page":"943","volume-title":"Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS\u201917)","volume":"54","author":"Jun Kwang-Sung","year":"2017","unstructured":"Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. 2017. Improved strongly adaptive online learning using coin betting. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS\u201917), Aarti Singh and Jerry Zhu (Eds.), Vol. 54. 943\u2013951."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.5555\/3120260.3120301"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-009-0206-2"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/060659624"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2018.2830299"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCNS.2016.2573639"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2016.7798923"},{"key":"e_1_3_2_25_2","first-page":"1732","volume-title":"Proceedings of the 21st International Conference on Artificial Intelligence and Statistics","volume":"84","author":"Mohri Mehryar","year":"2018","unstructured":"Mehryar Mohri and Scott Yang. 2018. Competing with automata-based expert sequences. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, Amos Storkey and Fernando Perez-Cruz (Eds.), Vol. 84. 1732\u20131740."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2016.7799379"},{"key":"e_1_3_2_27_2","unstructured":"Jaouad Mourtada and Odalric-Ambrym Maillard. 2017. Efficient tracking of a growing number of experts. Proceedings of the 28th International Conference on Algorithmic Learning Theory Vol. 76 Proceedings of Machine Learning Research 517\u2013539."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2015.7172037"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/3327144.3327198"},{"key":"e_1_3_2_30_2","first-page":"18501","volume-title":"Advances in Neural Information Processing Systems","author":"Sentenac Flore","year":"2021","unstructured":"Flore Sentenac, Etienne Boursier, and Vianney Perchet. 2021. Decentralized learning in online queuing systems. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, and J. Wortman Vaughan (Eds.), Vol. 34. Curran Associates, Inc., 18501\u201318512."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2017.2743462"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1561\/2200000018"},{"key":"e_1_3_2_33_2","unstructured":"Hanlin Tang Shaoduo Gan Ce Zhang Tong Zhang and Ji Liu. 2018. Communication compression for decentralized training. arxiv:cs.LG\/1803.06443v3. Retrieved from https:\/\/arxiv.org\/abs\/1803.06443v3."},{"key":"e_1_3_2_34_2","first-page":"3972","volume-title":"Proceedings of Advances in Neural Information Processing Systems","author":"Wei Chen-Yu","year":"2016","unstructured":"Chen-Yu Wei, Yi-Te Hong, and Chi-Jen Lu. 2016. Tracking the best expert in non-stationary stochastic environments. In Proceedings of Advances in Neural Information Processing Systems, D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (Eds.). 3972\u20133980."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSIPN.2017.2695121"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/s40305-015-0104-0"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3417607"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.191"},{"key":"e_1_3_2_39_2","volume-title":"Proceedings of the 34th International Conference on Machine Learning (ICML\u201916)","author":"Yang Tianbao","year":"2016","unstructured":"Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. 2016. Tracking slowly moving clairvoyant - optimal dynamic regret of online learning with true and noisy gradient. In Proceedings of the 34th International Conference on Machine Learning (ICML\u201916)."},{"key":"e_1_3_2_40_2","doi-asserted-by":"crossref","unstructured":"Kun Yuan Qing Ling and Wotao Yin. 2016. On the convergence of decentralized gradient descent. SIAM Journal on Optimization 26 3 (2016) 1835\u20131854.","DOI":"10.1137\/130943170"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2018.2818081"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-017-5676-y"},{"key":"e_1_3_2_43_2","first-page":"1323","volume-title":"Advances in Neural Information Processing Systems 31","author":"Zhang Lijun","year":"2018","unstructured":"Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. 2018. Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems 31, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.). 1323\u20131333."},{"key":"e_1_3_2_44_2","first-page":"5882","volume-title":"Proceedings of the 35th International Conference on Machine Learning (ICML\u201918)","author":"Zhang Lijun","year":"2018","unstructured":"Lijun Zhang, Tianbao Yang, rong jin, and Zhi-Hua Zhou. 2018. Dynamic regret of strongly adaptive methods. In Proceedings of the 35th International Conference on Machine Learning (ICML\u201918). 5882\u20135891."},{"key":"e_1_3_2_45_2","volume-title":"Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS\u201917)","author":"Zhang Lijun","year":"2017","unstructured":"Lijun Zhang, Tianbao Yang, Jinfeng Yi, Rong Jin, and Zhi-Hua Zhou. 2017. Improved dynamic regret for non-degenerate functions. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS\u201917)."},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.5555\/3305890.3306100"},{"key":"e_1_3_2_47_2","unstructured":"Yawei Zhao Shuang Qiu Kuan Li Lailong Luo Jianping Yin and Ji Liu. 2021. Proximal online gradient is optimum for dynamic regret: A general lower bound. IEEE Transactions on Neural Networks and Learning Systems 1\u201310."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375788"},{"key":"e_1_3_2_49_2","first-page":"928","volume-title":"Proceedings of International Conference on Machine Learning (ICML\u201903)","author":"Zinkevich Martin","year":"2003","unstructured":"Martin Zinkevich. 2003. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of International Conference on Machine Learning (ICML\u201903). 928\u2013935."}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3559765","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3559765","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:07:57Z","timestamp":1750183677000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3559765"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,9]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2,28]]}},"alternative-id":["10.1145\/3559765"],"URL":"https:\/\/doi.org\/10.1145\/3559765","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"value":"2157-6904","type":"print"},{"value":"2157-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,9]]},"assertion":[{"value":"2020-10-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}