Data-Driven Clustering via Parameterized Lloyd's Families
Algorithms for clustering points in metric spaces is a long-studied area of research. Clustering has seen a multitude of work both theoretically, in understanding the approximation guarantees possible for many objective functions such as k-median and k-means clustering, and experimentally, in finding the fastest algorithms and seeding procedures for Lloyd's algorithm. The performance of a given clustering algorithm depends on the specific application at hand, and this may not be known up front. For example, a "typical instance" may vary depending on the application, and different clustering heuristics perform differently depending on the instance. In this paper, we define an infinite family of algorithms generalizing Lloyd's algorithm, with one parameter controlling the initialization procedure, and another parameter controlling the local search procedure. This family of algorithms includes the celebrated k-means++ algorithm, as well as the classic farthest-first traversal algorithm. We design efficient learning algorithms which receive samples from an application-specific distribution over clustering instances and learn a nearoptimal clustering algorithm from the class. We show the best parameters vary significantly across datasets such as MNIST, CIFAR, and mixtures of Gaussians. Our learned algorithms never perform worse than k-means++, and on some datasets we see significant improvements.
The paper proposes a generalization of the KMeans++ Algorithm by introducing non-negative parameters alpha and beta. alpha parameterizes the initialization phase, i.e. the distribution from which the initial center seeds are sampled. beta parameterizes the objective according to which the data is clustered.  The motivation is that different instances of clustering problems may cluster well according to different clustering objectives. The optimal parameter configuration of alpha and beta defines an optimal choice, from the proposed family of clustering algorithms.  The paper offers several theoretical contributions. It provides guarantees for the number of samples necessary such that the empirically best parameter set yields clustering costs is within epsilon bounds of the optimal parameters.  It provides an algorithm for the enumeration of all possible sets of initial centers for any alpha-interval. This allows to provide runtime guarantees for tuning the parameter alpha.  The proposed algorithm is evaluated on MNIST, Cifar10, CNAE-9 and a mixture of Gaussians dataset, where the datasets are split into training and test sets. Results show that the optimal parameters transfer from one training to test set.  The theoretical contribution of this paper seems solid. Proofs are provided for all theorems.  The fact that a cost close to the empirically optimal value can be achieved for parameter beta = 2 for all datasets (see supplementary material), equaling to the k-means objective, is a bit disappointing. However, this finding might be different for different datasets.  In general, the paper is difficult to read. This might be due to the fact that many details do not find place in the main paper, such that, without reading the proofs in detail, it becomes hard to understand the exact conditions under which the provided guarantees hold. For example  on page 4, line 182, the paper need to be more precise! The assumption made is that ALL data points from one cluster have to be closer to ALL data points of the same cluster than to any point of a different cluster (which is a very strong assumption in practice).