When is Network Lasso Accurate: The Vector Case
This work addresses the challenge of learning from massive network-structured datasets with sparse labels, which is incremental as it builds on existing nLasso methods by analyzing their accuracy conditions.
The paper tackles the problem of determining when the network Lasso algorithm accurately learns vector-valued graph signals from limited labeled data, providing sufficient conditions on network structure and label information for accurate learning.
A recently proposed learning algorithm for massive network-structured data sets (big data over networks) is the network Lasso (nLasso), which extends the well- known Lasso estimator from sparse models to network-structured datasets. Efficient implementations of the nLasso have been presented using modern convex optimization methods. In this paper, we provide sufficient conditions on the network structure and available label information such that nLasso accurately learns a vector-valued graph signal (representing label information) from the information provided by the labels of a few data points.