Network Lasso: Clustering and Optimization in Large Graphs (KDD'15)

Network Lasso: Clustering and Optimization in Large Graphs

David Hallac, Jure Leskovec, Stephen Boyd (Stanford University)

　概要

凸最適化はデータ分析において非常に重要な役割を担っているが汎用の凸最適化ソルバは大規模な問題に対してスケールせず,　一部の問題に対してスケールするソルバが扱える問題は狭い範囲のものでしかなかった.この論文ではネットワーク上での最適化やクラスタリングを行う問題に対して, group lassoを一般化したnetwork lassoというものを提案する. Alternating Direction Method of Multipliers (ADMM)に基づくアルゴリズムを開発し大規模なネットワークでも計算が収束するようにした. 二値分類・家賃予測・時系列データのイベント予測などの凸でない問題も含む問題において既存手法と比較することによってnetworks lassoに基づく手法が高速で高精度であることをしめした.

アブスト訳すだけになってしまった・・・