statistical-computational tradeoffs

Recovery Guarantees for Kernel-based Clustering under Non-parametric Mixture Models

Despite the ubiquity of kernel-based clustering, surprisingly few statistical guarantees exist beyond settings that consider strong structural assumptions on the data generation process. In this work, we take a step towards bridging this gap by …

On the optimality of kernels for high-dimensional clustering

This paper studies the optimality of kernel methods in high-dimensional data clustering. Recent works have studied the large sample performance of kernel clustering in the high-dimensional regime, where Euclidean distance becomes less informative. …