Phase Transitions in Heavy-Tailed Mean Estimation under ℓp Norms
Authors: Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Mikael Møller Høgsgaard, Kasper Green Larsen, Nikita Zhivotovskiy
Organizations: Work done at EECS Department, UC Berkeley. · College of Computing and Data Science, Nanyang Technological University · Department of Statistics, University of Oxford · Computer Science Department, Aarhus University · Department of Statistics, UC Berkeley
We study the problem of estimating the mean of a random vector in Rd under ℓp norms, assuming only the existence of a covariance matrix. In the Euclidean norm, the sample mean is already optimal in expectation, and robust estimators are usually needed only to obtain high-probability tails. Our results show that this picture changes for ℓp norms with p>2: robustification is already necessary even for the expected risk. We prove that the minimax risk exhibits a sharp phase transition, controlled by the interaction between the sample size n, the dimension d, and the norm parameter p. In the large-sample regime, the classical Gaussian rate remains achievable. In the complementary regime, heavy-tailed distributions create a genuinely non-Gaussian obstruction. Furthermore we show that the simple estimator: coordinate-wise median of means whose number of buckets chosen according to the geometry of the loss, optimally tracks this phase transition in its expected risk minimax. We also show that natural projection-based median-of-means estimators for general norms, despite achieving the optimal confidence trade-off relative to the sample-mean benchmark of Lugosi and Mendelson (Probab. Theory Relat. Fields, 2019), can be polynomially suboptimal for ℓp norms even in the constant-probability regime.