NeurIPS 2018poster14 citations
How to tell when a clustering is (approximately) correct using convex relaxations
Abstract
We introduce the Sublevel Set (SS) method, a generic method to obtain sufficient guarantees of near-optimality and uniqueness (up to small perturbations) for a clustering. This method can be instantiated for a variety of clustering loss functions for which convex relaxations exist. Obtaining the guarantees in practice amounts to solving a convex optimization. We demonstrate the applicability of this method by obtaining distribution free guarantees for K-means clustering on realistic data sets.
BibTeX
@inproceedings{NEURIPS2018_882735cb,
author = {Meila, Marina},
booktitle = {Advances in Neural Information Processing Systems},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {How to tell when a clustering is (approximately) correct using convex relaxations},
url = {https://proceedings.neurips.cc/paper_files/paper/2018/file/882735cbdfd9f810814d17892ae50023-Paper.pdf},
volume = {31},
year = {2018}
}