Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend

By Wendi Wu, Zongren Li, Yawei Zhao, Chenkai Yu, Peilin Zhao, Ji Liu, Kunlun He. 2019

19 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research, Federated & Distributed Learning, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Federated & Distributed Learning

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “Extending FL to other ML paradigms, including reinforcement learning, semisupervised and unsupervised learning, active learning, and online learning [200, 435] all present interesting and open challenges.”
Asynchronous Decentralized Online Learning (2021, unknown): “When receiving the feedback, learner i begins to calculate the gradient ∇ f τi ( w τi ) .”