# Fast learning rates with heavy-tailed losses

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Sep 2016.

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

- [Posterior concentration and fast convergence rates for generalized Bayesian learning](https://mlsanity.com/paper/2111.10243/) (2021)
- [Subsampled Ensemble Can Improve Generalization Tail Exponentially](https://mlsanity.com/paper/2405.14741/) (2024)

## Abstract (arXiv)

We study fast learning rates when the losses are not necessarily bounded and may have a distribution with heavy tails. To enable such analyses, we introduce two new conditions: (i) the envelope function supf ∈ F|ℓ circ f|, where ℓ is the loss function and F is the hypothesis class, exists and is Lr-integrable, and (ii) ℓ satisfies the multi-scale Bernstein's condition on F. Under these assumptions, we prove that learning rate faster than O(n-1/2) can be obtained and, depending on r and the multi-scale Bernstein's powers, can be arbitrarily close to O(n-1). We then verify these assumptions and derive fast learning rates for the problem of vector quantization by k-means clustering with heavy-tailed distributions. The analyses enable us to obtain novel learning rates that extend and complement existing results in the literature from both theoretical and practical viewpoints.