Recovery conditions and sampling strategies for network Lasso

Alexandru Mara, Alexander Jung

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

4 Citations (Scopus)

Abstract

The network Lasso is a recently proposed convex optimization method for machine learning from massive network structured datasets, i.e., big data over networks. It is a variant of the well-known least absolute shrinkage and selection operator (Lasso), which is underlying many methods in learning and signal processing involving sparse models. Highly scalable implementations of the network Lasso can be obtained by state-of-the-art proximal methods, e.g., the alternating direction method of multipliers (ADMM). By generalizing the concept of the compatibility condition put forward by van de Geer and Buhlmann as a powerful tool for the analysis of plain Lasso, we derive a sufficient condition, i.e., the network compatibility condition, on the underlying network topology such that network Lasso accurately learns a clustered underlying graph signal. This network compatibility condition relates the location of sampled nodes with the clustering structure of the network. In particular, the NCC informs the choice of which nodes to sample, or in machine learning terms, which data points provide most information if labeled.

Original languageEnglish
Title of host publicationConference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017
EditorsMichael B. Matthews
PublisherIEEE
Pages405-409
Number of pages5
Volume2017-October
ISBN (Electronic)9781538618233
DOIs
Publication statusPublished - 10 Apr 2018
MoE publication typeA4 Article in a conference publication
EventAsilomar Conference on Signals, Systems & Computers - Pacific Grove, United States
Duration: 29 Oct 20171 Nov 2017
Conference number: 51

Publication series

NameConference record of the Asilomar Conference on Signals, Systems & Computers
PublisherComputer Society Press
ISSN (Electronic)2576-2303

Conference

ConferenceAsilomar Conference on Signals, Systems & Computers
Abbreviated titleASILOMAR
CountryUnited States
CityPacific Grove
Period29/10/201701/11/2017

Keywords

  • big data
  • complex networks
  • compressed sensing
  • convex optimzation
  • semi-supervised learning

Fingerprint Dive into the research topics of 'Recovery conditions and sampling strategies for network Lasso'. Together they form a unique fingerprint.

Cite this