From Large to Small Datasets: Size Generalization for Clustering Algorithm Selection
Speaker
Ellen Vitercik
Stanford University
Host
Costis Daskalakis
CSAIL MIT
Abstract: In clustering algorithm selection, we are given a massive dataset and must efficiently select which clustering algorithm to use. We study this problem in a semi-supervised setting, with an unknown ground-truth clustering that we can only access through expensive oracle queries. Ideally, the clustering algorithm's output will be structurally close to the ground truth. We approach this problem by introducing a notion of size generalization for clustering algorithm accuracy. We identify conditions under which we can (1) subsample the massive clustering instance, (2) evaluate a set of candidate algorithms on the smaller instance, and (3) guarantee that the algorithm with the best accuracy on the small instance will have the best accuracy on the original big instance. We verify these findings both theoretically and empirically.
This is joint work with Vaggos Chatziafratis and Ishani Karmarkar.
This is joint work with Vaggos Chatziafratis and Ishani Karmarkar.