Analysis of Network Lasso for SemiSupervised Regression
[edit]
Proceedings of Machine Learning Research, PMLR 89:380387, 2019.
Abstract
We apply network Lasso to semisupervised regression problems involving networkstructured data. This approach lends quite naturally to highly scalable learning algorithms in the form of message passing over an empirical graph which represents the network structure of the data. By using a simple nonparametric regression model, which is motivated by a clustering hypothesis, we provide an analysis of the estimation error incurred by network Lasso. This analysis reveals conditions on the network structure and the available training data which guarantee network Lasso to be accurate. Remarkably, the accuracy of network Lasso is related to the existence of suciently large network flows over the empirical graph. Thus, our analysis reveals a connection between network Lasso and maximum network flow problems.
Related Material


