# Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 34 references that are in the map.
- First posted on arXiv 17 Jun 2025.

## Builds on (most cited first, 4 of 4)

- [The Heavy-Tail Phenomenon in SGD](https://mlsanity.com/paper/2006.04740/) (2020)
- [Moment-based Uniform Deviation Bounds for k-means and Friends](https://mlsanity.com/paper/1311.1903/) (2013)
- [When are epsilon-nets small?](https://mlsanity.com/paper/1711.10414/) (2017)
- [An Improved Uniform Convergence Bound with Fat-Shattering Dimension](https://mlsanity.com/paper/2307.06644/) (2023)

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

- [Sharper Generalization Bounds for Transformer](https://mlsanity.com/paper/2603.21541/) (2026)
- [Optimal Learning from Label Proportions with General Loss Functions](https://mlsanity.com/paper/2509.15145/) (2025)
- [SNAP: A Self-Consistent Agreement Principle with Application to Robust Computation](https://mlsanity.com/paper/2602.02013/) (2026)
- [Mean Testing under Truncation beyond Gaussian](https://mlsanity.com/paper/2605.01335/) (2026)

## Abstract (arXiv)

The Median of Means (MoM) is a mean estimator that has gained popularity in the context of heavy-tailed data. In this work, we analyze its performance in the task of simultaneously estimating the mean of each function in a class F when the data distribution possesses only the first p moments for p ∈ (1,2]. We prove a new sample complexity bound using a novel symmetrization technique that may be of independent interest. Additionally, we present applications of our result to k-means clustering with unbounded inputs and linear regression with general losses, improving upon existing works.