Uniform Deviation Bounds for k-Means Clustering

Authors: Olivier Bachem, Mario Lucic, S. Hamed Hassani, Andreas Krause

Abstract

Uniform deviation bounds limit the difference between a model’s expected loss and its loss on an empirical sample