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

  • 2025-06-18 07:49:11
  • Mikael Møller Høgsgaard, Andrea Paudice
  • 0

Abstract

The Median of Means (MoM) is a mean estimator that has gained popularity inthe context of heavy-tailed data. In this work, we analyze its performance inthe task of simultaneously estimating the mean of each function in a class$\mathcal{F}$ when the data distribution possesses only the first $p$ momentsfor $p \in (1,2]$. We prove a new sample complexity bound using a novelsymmetrization technique that may be of independent interest. Additionally, wepresent applications of our result to $k$-means clustering with unboundedinputs and linear regression with general losses, improving upon existingworks.

 

Quick Read (beta)

loading the full paper ...