Uniform Deviation Bounds for Unbounded Loss Functions like k-Means

Olivier Bachem, Mario Lucic, S. Hamed Hassani +1

Uniform deviation bounds limit the difference between a model's expected loss and its loss on an empirical sample uniformly for all models in a learning problem. As such, they are…