Decentralized Semi-supervised Learning over Multitask Graphs

In network semi-supervised learning problems, only a subset of the network nodes is able to access the data labeling. This paper formulates a decentralized optimization problem where agents have individual decision rules to estimate, subject to the condition that neighboring agents (classifiers) are more likely to have similar labels. To promote such relationships, we propose to add to the aggregate sum of individual costs a graph regularization term that allows to penalize the differences between the labels at neighboring agents. Streaming data is assumed, and therefore, the stochastic (sub-)gradient method is used to solve the regularized problem. We provide conditions that guarantee the stability and convergence of the proposed algorithm. Simulation results show that collaboration among neighboring agents leads to better classification results by decreasing the probability of error and by improving the convergence rate.