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

Title

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

Speaker

Andrea Paudice - Aarhus University (DK)

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 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.

Bio

Andrea Paudice is a tenure-track Assistant Professor in Computer Science at Aarhus University. Previously, he held a joint postdoctoral position at the University of Milan (Statale) and IIT, where he also obtained his PhD in Computer Science advised by Nicolò Cesa-Bianchi and Massimiliano Pontil. Previously, he spent approximately three years as a researcher at Imperial College London. In the past, he held an industrial collaboration with Leonardo. His research interests lie in the theory of machine learning, with a focus on stochastic optimization, generalization bounds, and the analysis of classical algorithms in non-standard settings. His research has been awarded with a prestigious Villum Young Investigator (2026-2031) award and a Novo Nordisk Starting grant (2024-2029).

When

Thursday, May 7th, 11:30

Where

Room 322, UniGe DIBRIS/DIMA, Via Dodecaneso 35