Pursuit of the Cluster Structure of Network Lasso: Recovery Condition and Non-convex Extension

Network Lasso (NL for short) is a methodology for estimating models by simultaneously fitting and clustering data samples. It often succeeds in forming clusters thanks to the geometry of the $\ell_1$-regularizer employed therein, but there might be limitations because of the convexity of the regularizer. This paper focuses on the cluster structure of NL and develops a non-convex extension, which we call Network Trimmed Lasso (NTL for short). Specifically, we first studies a sufficient condition which guarantees the recovery of latent cluster structure of NL on the basis of the result of Sun et al. for Convex Clustering, which is a special case of NL. Second, we extend NL to NTL to incorporate a cardinality constraint, reformulate the non-convex constrained optimization problem into an equivalent continuous unconstrained optimization problem, and develop ADMM algorithms. Numerical illustrations demonstrate that the non-convex extension provides more clear-cut cluster structure when NL fails to form clusters without incorporating prior knowledge on the associated parameters.