Decentralized Online Learning Algorithms Based On Alternating Direction Method Of Multipliers

With the development of network technologies, social networking, Internet bank-ing, Internet of things, as well as many other applications rise rapidly and generate huge amounts of data every day. Among these data, a small fraction is static and not real-time, while the majority is streaming data that need real-time processing. For the learning of huge streaming data, traditional decentralized batch learning methods have shown their deficiency, which motivates the research on processing streaming data with decentralized real-time online learning algorithms in this thesis.This thesis considers the online learning problem in which data is collected by a decentralized network. A synchronous decentralized online learning algorithm, termed as oDM, and an asynchronous decentralized online learning algorithm, termed as aoD-M, are proposed. Both algorithms are based on the alternating direction method of multipliers (ADMM).Firstly, observing that decentralized online learning requires each node to update its local iterate based on new local data while all the nodes to converge to a consen-sual iterate, a mathematical model is developed and solved by the synchronous and asynchronous algorithms, oDM and aoDM. Secondly, For both synchronous and asyn-chronous case, regret bounds of decentralized online learning is defined to characterize the difference of objective function value between online learning and batch learning. Theoretical analysis proves that oDM has a O(√T) regret bound and a O(√T/T) convergence rate when the instantaneous local cost functions are convex and the sub-gradients are bounded; further, it has a O(log T) regret bound and a O(log T/T) con-vergence rate when the instantaneous local cost functions are strongly convex and the subgradients are bounded. aoDM has a O(1) regret bound and a O(1/T) convergence rate when the domain of primal variables is tight and functions have Lipschitz continu-ity. Finally, numerical experiments demonstrate the effectiveness of oDM and aoDM.