math.STNov 15, 2026

Phase Transitions in Heavy-Tailed Mean Estimation under ℓp\ell_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 · 

Abstract

We study the problem of estimating the mean of a random vector in Rd\mathbb R^d under ℓp\ell_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\ell_p norms with p>2p>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 nn, the dimension dd, and the norm parameter pp. 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\ell_p norms even in the constant-probability regime.

Explore similar work

CardsList
  1. Median-of-Means as an Extremal Convex Estimator and a Nonconvex Route to the Trimmed Oracle

    Sep 1, 2026Angshul MajumdarNonconvex OptimizationRobust Mean Estimation

  2. Heavy-Tailed Principal Component Analysis

    Mar 11, 2026Mario Sayde, Christopher Khater, Jihad Fahs +1Principal Component AnalysisRobust Estimation

  3. Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails

    Sep 3, 2026Shi Fu, Huibo Xu, Qixin Zhang +1Sparse RecoveryHeavy-Tailed Noise