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

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.