Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means
Abstract
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 $\mathcal{F}$ when the data distribution possesses only the first $p$ moments for $p \in (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.
Cite
Text
Høgsgaard and Paudice. "Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means." Proceedings of the 42nd International Conference on Machine Learning, 2025.Markdown
[Høgsgaard and Paudice. "Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means." Proceedings of the 42nd International Conference on Machine Learning, 2025.](https://mlanthology.org/icml/2025/hgsgaard2025icml-uniform/)BibTeX
@inproceedings{hgsgaard2025icml-uniform,
title = {{Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means}},
author = {Høgsgaard, Mikael Møller and Paudice, Andrea},
booktitle = {Proceedings of the 42nd International Conference on Machine Learning},
year = {2025},
pages = {23357-23381},
volume = {267},
url = {https://mlanthology.org/icml/2025/hgsgaard2025icml-uniform/}
}