# Uniform Deviation Bounds for Unbounded Loss Functions like k-Means

arXiv: https://arxiv.org/abs/1702.08249 · HTML: https://mlsanity.com/paper/1702.08249/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2017.

## Built on by (most cited first, 2 of 2)

- [Expert with Clustering: Hierarchical Online Preference Learning Framework](https://mlsanity.com/paper/2401.15062/) (2024)
- [The Nah Bandit: Modeling User Non-compliance in Recommendation Systems](https://mlsanity.com/paper/2408.07897/) (2024)

## Abstract (arXiv)

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 a critical component to empirical risk minimization. In this paper, we provide a novel framework to obtain uniform deviation bounds for loss functions which are *unbounded*. In our main application, this allows us to obtain bounds for k-Means clustering under weak assumptions on the underlying distribution. If the fourth moment is bounded, we prove a rate of Oleft(m-frac12right) compared to the previously known Oleft(m-frac14right) rate. Furthermore, we show that the rate also depends on the kurtosis - the normalized fourth moment which measures the "tailedness" of a distribution. We further provide improved rates under progressively stronger assumptions, namely, bounded higher moments, subgaussianity and bounded support.