2015 NetworkLassoClusteringandOptimi

• (Hallac et al., 2015) ⇒ David Hallac, Jure Leskovec, and Stephen Boyd. (2015). “Network Lasso: Clustering and Optimization in Large Graphs.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783313

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Network+Lasso%3A+Clustering+and+Optimization+in+Large+Graphs
• http://dl.acm.org/citation.cfm?id=2783258.2783313&preflayout=flat#citedby

Quotes

Author Keywords

• Admm; convex optimization; data mining; network lasso

Abstract

Convex optimization is an essential tool for modern data analysis, as it provides a framework to formulate and solve many problems in machine learning and data mining. However, general convex optimization solvers do not scale well, and scalable solvers are often specialized to only work on a narrow class of problems. Therefore, there is a need for simple, scalable algorithms that can solve many common optimization problems. In this paper, we introduce the network lasso, a generalization of the group lasso to a network setting that allows for simultaneous clustering and optimization on graphs. We develop an algorithm based on the Alternating Direction Method of Multipliers (ADMM) to solve this problem in a distributed and scalable manner, which allows for guaranteed global convergence even on large graphs. We also examine a non-convex extension of this approach. We then demonstrate that many types of problems can be expressed in our framework. We focus on three in particular --- binary classification, predicting housing prices, and event detection in time series data --- comparing the network lasso to baseline approaches and showing that it is both a fast and accurate method of solving large optimization problems.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 NetworkLassoClusteringandOptimi	Jure Leskovec Stephen Boyd David Hallac			Network Lasso: Clustering and Optimization in Large Graphs				10.1145/2783258.2783313		2015