Clustering by Sum of Norms: Stochastic Incremental Algorithm, Convergence and Cluster Recovery. Panahi, A., Dubhashi, D., Johansson, F. D., & Bhattacharyya, C. In Proceedings of the 34th International Conference on Machine Learning, pages 2769–2777, July, 2017. PMLR. ISSN: 2640-3498![Clustering by Sum of Norms: Stochastic Incremental Algorithm, Convergence and Cluster Recovery [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper abstract bibtex Standard clustering methods such as K-means, Gaussian mixture models, and hierarchical clustering are beset by local minima, which are sometimes drastically suboptimal. Moreover the number of clusters K must be known in advance. The recently introduced the sum-of-norms (SON) or Clusterpath convex relaxation of k-means and hierarchical clustering shrinks cluster centroids toward one another and ensure a unique global minimizer. We give a scalable stochastic incremental algorithm based on proximal iterations to solve the SON problem with convergence guarantees. We also show that the algorithm recovers clusters under quite general conditions which have a similar form to the unifying proximity condition introduced in the approximation algorithms community (that covers paradigm cases such as Gaussian mixtures and planted partition models). We give experimental results to confirm that our algorithm scales much better than previous methods while producing clusters of comparable quality.
@inproceedings{panahi_clustering_2017,
title = {Clustering by {Sum} of {Norms}: {Stochastic} {Incremental} {Algorithm}, {Convergence} and {Cluster} {Recovery}},
shorttitle = {Clustering by {Sum} of {Norms}},
url = {https://proceedings.mlr.press/v70/panahi17a.html},
abstract = {Standard clustering methods such as K-means, Gaussian mixture models, and hierarchical clustering are beset by local minima, which are sometimes drastically suboptimal. Moreover the number of clusters K must be known in advance. The recently introduced the sum-of-norms (SON) or Clusterpath convex relaxation of k-means and hierarchical clustering shrinks cluster centroids toward one another and ensure a unique global minimizer. We give a scalable stochastic incremental algorithm based on proximal iterations to solve the SON problem with convergence guarantees. We also show that the algorithm recovers clusters under quite general conditions which have a similar form to the unifying proximity condition introduced in the approximation algorithms community (that covers paradigm cases such as Gaussian mixtures and planted partition models). We give experimental results to confirm that our algorithm scales much better than previous methods while producing clusters of comparable quality.},
language = {en},
urldate = {2021-10-01},
booktitle = {Proceedings of the 34th {International} {Conference} on {Machine} {Learning}},
publisher = {PMLR},
author = {Panahi, Ashkan and Dubhashi, Devdatt and Johansson, Fredrik D. and Bhattacharyya, Chiranjib},
month = jul,
year = {2017},
note = {ISSN: 2640-3498},
pages = {2769--2777},
}
Downloads: 0
{"_id":"yWoJ9fKLnPB5GCeXm","bibbaseid":"panahi-dubhashi-johansson-bhattacharyya-clusteringbysumofnormsstochasticincrementalalgorithmconvergenceandclusterrecovery-2017","author_short":["Panahi, A.","Dubhashi, D.","Johansson, F. D.","Bhattacharyya, C."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"Clustering by Sum of Norms: Stochastic Incremental Algorithm, Convergence and Cluster Recovery","shorttitle":"Clustering by Sum of Norms","url":"https://proceedings.mlr.press/v70/panahi17a.html","abstract":"Standard clustering methods such as K-means, Gaussian mixture models, and hierarchical clustering are beset by local minima, which are sometimes drastically suboptimal. Moreover the number of clusters K must be known in advance. The recently introduced the sum-of-norms (SON) or Clusterpath convex relaxation of k-means and hierarchical clustering shrinks cluster centroids toward one another and ensure a unique global minimizer. We give a scalable stochastic incremental algorithm based on proximal iterations to solve the SON problem with convergence guarantees. We also show that the algorithm recovers clusters under quite general conditions which have a similar form to the unifying proximity condition introduced in the approximation algorithms community (that covers paradigm cases such as Gaussian mixtures and planted partition models). We give experimental results to confirm that our algorithm scales much better than previous methods while producing clusters of comparable quality.","language":"en","urldate":"2021-10-01","booktitle":"Proceedings of the 34th International Conference on Machine Learning","publisher":"PMLR","author":[{"propositions":[],"lastnames":["Panahi"],"firstnames":["Ashkan"],"suffixes":[]},{"propositions":[],"lastnames":["Dubhashi"],"firstnames":["Devdatt"],"suffixes":[]},{"propositions":[],"lastnames":["Johansson"],"firstnames":["Fredrik","D."],"suffixes":[]},{"propositions":[],"lastnames":["Bhattacharyya"],"firstnames":["Chiranjib"],"suffixes":[]}],"month":"July","year":"2017","note":"ISSN: 2640-3498","pages":"2769–2777","bibtex":"@inproceedings{panahi_clustering_2017,\n\ttitle = {Clustering by {Sum} of {Norms}: {Stochastic} {Incremental} {Algorithm}, {Convergence} and {Cluster} {Recovery}},\n\tshorttitle = {Clustering by {Sum} of {Norms}},\n\turl = {https://proceedings.mlr.press/v70/panahi17a.html},\n\tabstract = {Standard clustering methods such as K-means, Gaussian mixture models, and hierarchical clustering are beset by local minima, which are sometimes drastically suboptimal. Moreover the number of clusters K must be known in advance. The recently introduced the sum-of-norms (SON) or Clusterpath convex relaxation of k-means and hierarchical clustering shrinks cluster centroids toward one another and ensure a unique global minimizer. We give a scalable stochastic incremental algorithm based on proximal iterations to solve the SON problem with convergence guarantees. We also show that the algorithm recovers clusters under quite general conditions which have a similar form to the unifying proximity condition introduced in the approximation algorithms community (that covers paradigm cases such as Gaussian mixtures and planted partition models). We give experimental results to confirm that our algorithm scales much better than previous methods while producing clusters of comparable quality.},\n\tlanguage = {en},\n\turldate = {2021-10-01},\n\tbooktitle = {Proceedings of the 34th {International} {Conference} on {Machine} {Learning}},\n\tpublisher = {PMLR},\n\tauthor = {Panahi, Ashkan and Dubhashi, Devdatt and Johansson, Fredrik D. and Bhattacharyya, Chiranjib},\n\tmonth = jul,\n\tyear = {2017},\n\tnote = {ISSN: 2640-3498},\n\tpages = {2769--2777},\n}\n\n","author_short":["Panahi, A.","Dubhashi, D.","Johansson, F. D.","Bhattacharyya, C."],"key":"panahi_clustering_2017","id":"panahi_clustering_2017","bibbaseid":"panahi-dubhashi-johansson-bhattacharyya-clusteringbysumofnormsstochasticincrementalalgorithmconvergenceandclusterrecovery-2017","role":"author","urls":{"Paper":"https://proceedings.mlr.press/v70/panahi17a.html"},"metadata":{"authorlinks":{}}},"bibtype":"inproceedings","biburl":"https://bibbase.org/zotero/mh_lenguyen","dataSources":["iwKepCrWBps7ojhDx"],"keywords":[],"search_terms":["clustering","sum","norms","stochastic","incremental","algorithm","convergence","cluster","recovery","panahi","dubhashi","johansson","bhattacharyya"],"title":"Clustering by Sum of Norms: Stochastic Incremental Algorithm, Convergence and Cluster Recovery","year":2017}