Network Lasso: Clustering and Optimization in Large Graphs.

Area of Science:

• Optimization
• Machine Learning
• Data Mining

Background:

• Convex optimization is crucial for data analysis but general solvers lack scalability.
• Existing scalable solvers are often problem-specific, necessitating broader solutions.

Purpose of the Study:

• To introduce a novel, scalable algorithm for convex optimization problems on graphs.
• To address the need for versatile and efficient optimization methods in machine learning and data mining.

Main Methods:

• Developed the network lasso, a graph-based generalization of the group lasso.
• Utilized the Alternating Direction Method of Multipliers (ADMM) for distributed and scalable computation.
• Explored a non-convex extension of the network lasso framework.

Main Results:

• The network lasso algorithm demonstrates guaranteed global convergence on large graphs.
• The framework successfully models diverse problems including classification, regression, and time series analysis.
• Empirical results show the network lasso is both fast and accurate compared to baseline methods.

Conclusions:

• The network lasso provides a unified, scalable framework for optimization on graphs.
• This method offers a significant advancement for tackling complex problems in machine learning and data analysis.
• The approach is effective for large-scale applications in binary classification, housing price prediction, and event detection.