Skip to yearly menu bar Skip to main content


Poster

How to tell when a clustering is (approximately) correct using convex relaxations

Marina Meila

Room 210 #56

Keywords: [ Clustering ] [ Combinatorial Optimization ] [ Convex Optimization ]


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.

Live content is unavailable. Log in and register to view live content