Convex Relaxations of Bregman Divergence Clustering

Hao Cheng, Xinhua Zhang, Dale Schuurmans
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:362-371, 2013.

Abstract

Although many convex relaxations of clustering have been proposed in the past decade, current formulations remain restricted to spherical Gaus- sian or discriminative models and are susceptible to imbalanced clusters. To address these short- comings, we propose a new class of convex re- laxations that can be flexibly applied to more general forms of Bregman divergence clustering. By basing these new formulations on normalized equivalence relations we retain additional control on relaxation quality, which allows improvement in clustering quality. We furthermore develop optimization methods that improve scalability by exploiting recent implicit matrix norm methods. In practice, we find that the new formulations are able to efficiently produce tighter clusterings that improve the accuracy of state of the art methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-cheng13a, title = {Convex Relaxations of Bregman Divergence Clustering}, author = {Cheng, Hao and Zhang, Xinhua and Schuurmans, Dale}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {362--371}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/cheng13a/cheng13a.pdf}, url = {https://proceedings.mlr.press/r11/cheng13a.html}, abstract = {Although many convex relaxations of clustering have been proposed in the past decade, current formulations remain restricted to spherical Gaus- sian or discriminative models and are susceptible to imbalanced clusters. To address these short- comings, we propose a new class of convex re- laxations that can be flexibly applied to more general forms of Bregman divergence clustering. By basing these new formulations on normalized equivalence relations we retain additional control on relaxation quality, which allows improvement in clustering quality. We furthermore develop optimization methods that improve scalability by exploiting recent implicit matrix norm methods. In practice, we find that the new formulations are able to efficiently produce tighter clusterings that improve the accuracy of state of the art methods.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Convex Relaxations of Bregman Divergence Clustering %A Hao Cheng %A Xinhua Zhang %A Dale Schuurmans %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-cheng13a %I PMLR %P 362--371 %U https://proceedings.mlr.press/r11/cheng13a.html %V R11 %X Although many convex relaxations of clustering have been proposed in the past decade, current formulations remain restricted to spherical Gaus- sian or discriminative models and are susceptible to imbalanced clusters. To address these short- comings, we propose a new class of convex re- laxations that can be flexibly applied to more general forms of Bregman divergence clustering. By basing these new formulations on normalized equivalence relations we retain additional control on relaxation quality, which allows improvement in clustering quality. We furthermore develop optimization methods that improve scalability by exploiting recent implicit matrix norm methods. In practice, we find that the new formulations are able to efficiently produce tighter clusterings that improve the accuracy of state of the art methods. %Z Reissued by PMLR on 04 October 2026.
APA
Cheng, H., Zhang, X. & Schuurmans, D.. (2013). Convex Relaxations of Bregman Divergence Clustering. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:362-371 Available from https://proceedings.mlr.press/r11/cheng13a.html. Reissued by PMLR on 04 October 2026.

Related Material