A new algorithm and theory for penalized regression-based clustering

Chong Wu, Sunghoon Kwon, Xiaotong Shen, Wei Pan

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

Clustering is unsupervised and exploratory in nature. Yet, it can be performed through penalized regression with grouping pursuit, as demonstrated in Pan et al. (2013). In this paper, we develop a more efficient algorithm for scalable computation and a new theory of clustering consistency for the method. This algorithm, called DC-ADMM, combines difference of convex (DC) programming with the alternating direction method of multipliers (ADMM). This algorithm is shown to be more computationally efficient than the quadratic penalty based algorithm of Pan et al. (2013) because of the former's closed-form updating formulas. Numerically, we compare the DC-ADMM algorithm with the quadratic penalty algorithm to demonstrate its utility and scalability. Theoretically, we establish a finitesample mis-clustering error bound for penalized regression based clustering with the L0 constrained regularization in a general setting. On this ground, we provide conditions for clustering consistency of the penalized clustering method. As an end product, we put R package prclust implementing PRclust with various loss and grouping penalty functions available on GitHub and CRAN.

Original languageEnglish (US)
JournalJournal of Machine Learning Research
Volume17
StatePublished - Oct 1 2016

Bibliographical note

Funding Information:
The authors thank the reviewers for helpful comments. This research is partially supported by NIH grants R01GM113250, R01HL105397 and R01HL116720, and NSF grants DMS{1415500 and DMS{1207771. CW is supported by a University of Minnesota Doctoral Dissertation Fellowship.

Keywords

  • Alternating direction method of multipliers (ADMM)
  • Clustering consistency
  • Difference of convex (DC) programming
  • Truncated L1-penalty (TLP)

Fingerprint Dive into the research topics of 'A new algorithm and theory for penalized regression-based clustering'. Together they form a unique fingerprint.

Cite this