[Seminar] Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means.

Speaker

Prof. Andrea Paudice, Aarhus University, Aarhus, Denmark

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.

Biography

Andrea Paudice is a tenure-track Assistant Professor in Computer Science at Aarhus University, where he is also a Villum Young Investigator. Previously, he held a joint postdoctoral position at the University of Milan and the Italian Institute of Technology, where he also obtained his PhD in Computer Science. Before that, he spent approximately three years as a Research Fellow at Imperial College London. His research interests lie in the theory of machine learning, with a focus on stochastic optimization, generalization theories, and the analysis of classical algorithms in non-standard settings.