Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend
Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend
复制标题
DOI：
10.1145/3559765
复制
发表时间：
2019-01
影响因子：
5
通讯作者：
Wendi Wu;Zongren Li;Yawei Zhao;Chenkai Yu;P. Zhao;Ji Liu;K. He
中科院分区：
文献类型：
--
作者：
Wendi Wu;Zongren Li;Yawei Zhao;Chenkai Yu;P. Zhao;Ji Liu;K. He
去中心化在线学习（去中心化网络中的在线学习）已经吸引了越来越多的关注，因为人们认为去中心化在线学习可以帮助数据提供者更好地合作解决他们的在线问题，而无需将他们的私人数据共享给第三方或其他提供者。通常，通过让数据提供者在邻居之间交换它们的模型来实现协作，例如，推荐模型然而，去中心化在线学习算法的最佳遗憾边界是n（n <$T），其中n是节点（或用户）的数量，T是迭代次数。这显然是无关紧要的，因为这个界限可以在网络中没有任何通信的情况下实现。这提醒我们要问一个根本性的问题：人们真的能通过交换信息从分散的在线学习中获益吗？在这篇文章中，我们研究了何时以及为什么沟通可以帮助分散式在线学习减少遗憾。具体来说，每个损失函数由两个分量表征：对抗分量和随机分量。在这个特征下，我们证明了分散的在线梯度具有遗憾界\（{\mathcal {O}（\sqrt {n^2TG^2 + n T \sigma ^2}）} \），其中G度量私有数据中对抗分量的大小（或等效的局部损失函数），σ度量私有数据中的随机性。这种遗憾表明，人们可以通过交换私人信息从私人数据的随机性中获益。本文的另一个重要贡献是考虑了动态后悔，一种更实用的后悔来跟踪用户的兴趣动态。实证研究也进行了验证我们的分析。
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 𝒪(n√T), where n is the number of nodes (or users) and T is the number of iterations. This is clearly insignificant, since this bound can be achieved without any communication in the networks. This reminds us to ask a fundamental question: Can people really get benefit from the decentralized online learning by exchanging information? 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 \( {\mathcal {O}(\sqrt {n^2TG^2 + n T \sigma ^2})} \) , where G measures the magnitude of the adversarial component in the private data (or equivalently the local loss function) and σ 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—a more practical regret to track users’ interest dynamics. Empirical studies are also conducted to validate our analysis.