Analysis of Network Lasso for Semi-Supervised Regression
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 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 flow problems.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringregressionSimilar Papers 제목 키워드 기반
The Well Tempered Lasso
We study the complexity of the entire regularization path for least squares regression with 1-norm penalty, known as the Lasso. Every regression parameter in the Lasso changes linearly as a function of the regularization…
regressionSNAP: A semismooth Newton algorithm for pathwise optimization with optimal local convergence rate and oracle properties
We propose a semismooth Newton algorithm for pathwise optimization (SNAP) for the LASSO and Enet in sparse, high-dimensional linear regression. SNAP is derived from a suitable formulation of the KKT conditions based on N…
regressionA PLS-Integrated LASSO Method with Application in Index Tracking
In traditional multivariate data analysis, dimension reduction and regression have been treated as distinct endeavors. Established techniques such as principal component regression (PCR) and partial least squares (PLS) r…
Semi-Analytic Resampling in Lasso
An approximate method for conducting resampling in Lasso, the $\ell_1$ penalized linear regression, in a semi-analytic manner is developed, whereby the average over the resampled datasets is directly computed without rep…
Variable SelectionThe Well-Tempered Lasso
We study the complexity of the entire regularization path for least squares regression with 1-norm penalty, known as the Lasso. Every regression parameter in the Lasso changes linearly as a function of the regulariz…
regression