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

arXiv: https://arxiv.org/abs/2012.07491 · HTML: https://mlsanity.com/paper/2012.07491/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Dec 2020.

## Built on by (most cited first, 1 of 1)

- [Tree-Guided L1-Convex Clustering](https://mlsanity.com/paper/2503.24012/) (2025)

## Abstract (arXiv)

Network Lasso (NL for short) is a methodology for estimating models by simultaneously clustering data samples and fitting the models to the samples. It often succeeds in forming clusters thanks to the geometry of the ℓ1-regularizer employed therein, but there might be limitations because of the convexity of the regularizer. This paper focuses on the cluster structure that NL yields and reinforces it by developing a non-convex extension, which we call Network Trimmed Lasso (NTL for short). Specifically, we first study a sufficient condition that guarantees the recovery of the latent cluster structure of NL on the basis of the result of Sun et al. (2021) for Convex Clustering, which is a special case of NL for clustering. Second, we extend NL to NTL to incorporate a cardinality (or, ℓ0-)constraint and rewrite the constrained optimization problem defined with the ℓ0 norm, a discontinuous function, into an equivalent unconstrained continuous optimization problem. We develop ADMM algorithms to solve NTL and provide its convergence results. Numerical illustrations demonstrate that the non-convex extension provides a more clear-cut cluster structure when NL fails to form clusters without incorporating prior knowledge of the associated parameters.