Analysis of Network Lasso for Semi-Supervised Regression

Alexander Jung, Natalia Vesselinova
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:380-387, 2019.

Abstract

We apply network Lasso to semi-supervised regression problems involving network-structured 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 non-parametric 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 sufficiently large network flows over the empirical graph. Thus, our analysis reveals a connection between network Lasso and maximum network flow problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-jung19a, title = {Analysis of Network Lasso for Semi-Supervised Regression}, author = {Jung, Alexander and Vesselinova, Natalia}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {380--387}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/jung19a/jung19a.pdf}, url = {https://proceedings.mlr.press/v89/jung19a.html}, abstract = {We apply network Lasso to semi-supervised regression problems involving network-structured 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 non-parametric 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 sufficiently large network flows over the empirical graph. Thus, our analysis reveals a connection between network Lasso and maximum network flow problems.} }
Endnote
%0 Conference Paper %T Analysis of Network Lasso for Semi-Supervised Regression %A Alexander Jung %A Natalia Vesselinova %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-jung19a %I PMLR %P 380--387 %U https://proceedings.mlr.press/v89/jung19a.html %V 89 %X We apply network Lasso to semi-supervised regression problems involving network-structured 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 non-parametric 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 sufficiently large network flows over the empirical graph. Thus, our analysis reveals a connection between network Lasso and maximum network flow problems.
APA
Jung, A. & Vesselinova, N.. (2019). Analysis of Network Lasso for Semi-Supervised Regression. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:380-387 Available from https://proceedings.mlr.press/v89/jung19a.html.

Related Material