Abstract:

In this paper, we focus on the decentralized online learning problem where online data streams are separately collected and collaboratively processed by a network of decentralized agents. Comparing to centralized batch learning, such a framework is faithful to the decentralized and online natures of the data streams. We propose an online decentralized alternating direction method of multipliers that efficiently solves the online learning problem over a decentralized network.We prove its O(√T ) regret bound when the instantaneous local cost functions are convex, and its O(log T ) regret bound when the instantaneous local cost functions are strongly convex, where T is the number of iterations. Both regret bounds are in the same orders as those of centralized online learning. Numerical experiments on decentralized online least squares and classification problems demonstrate effectiveness of the proposed algorithm.

Key words: Multi-agent network ·, Decentralized optimization ·, Online learning