Phase Transitions in Heavy-Tailed Mean Estimation under $\ell_p$ Norms

Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Mikael Møller Høgsgaard, Kasper Green Larsen, Nikita ZhivotovskiyarXiv 2026 · arXiv

This paper, recently published by a team from UC Berkeley, NTU, Aarhus, and Oxford, explores a fundamental question in statistics: how well can we estimate the average of a group of data points when that data is "heavy-tailed" (prone to extreme outliers) and we care about errors in non-Euclidean geometries?

TL;DR

The authors discover a sharp "phase transition" in the difficulty of mean estimation under $\ell_p$ norms for $p > 2$. They prove that while the sample mean is optimal for standard Euclidean distance, it fails significantly in these other geometries, requiring a specifically tuned "median-of-means" estimator to achieve optimal performance.

What Problem Does This Paper Address?

Mean estimation is the bread and butter of machine learning and statistics. If you have $n$ samples, the most natural way to estimate their average is the sample mean. In a standard Euclidean ($\ell_2$) setting, the sample mean is remarkably robust; even if your data has heavy tails, the sample mean is "optimal in expectation."

However, we often care about different ways of measuring error, specifically $\ell_p$ norms. For example, the $\ell_\infty$ norm measures the maximum error across any single coordinate. The researchers found that once you move beyond the "benign" Euclidean geometry to $\ell_p$ norms where $p > 2$, the sample mean is no longer enough. Even if you only care about the average error (expected risk), you must use robust estimation techniques to handle heavy-tailed distributions. The core challenge was to determine the fundamental limits (minimax risk) of this problem and find an algorithm that reaches them.

Methods

The authors focus on the Coordinate-wise Median-of-Means (MoM) estimator. The process is simple:

  1. Bucketization: Split your $n$ data points into $t$ equal-sized buckets.
  2. Averaging: Calculate the standard sample mean within each bucket.
  3. Median: For each coordinate, take the median of those bucket averages.

The "secret sauce" introduced here is how to choose the number of buckets $t$. The authors show that $t$ must be tuned according to the "geometry of the loss"—specifically, the parameter $p$ and the dimension $d$.

To prove their results, they utilize minimax analysis, comparing their estimator against the theoretical "hardest" possible distributions that satisfy a basic covariance assumption. They use tools like Anderson’s Lemma for the Gaussian regime and construct specific heavy-tailed distributions to prove the limits of the non-Gaussian regime.

Datasets

This is a purely theoretical paper. No empirical datasets were used for training or evaluation. The "results" are mathematical proofs regarding the behavior of estimators on classes of probability distributions.

Key Insights and Ideas

  • The Euclidean Exception: The paper highlights that $\ell_2$ (Euclidean) geometry is a special case. For $p \le 2$, the sample mean is optimal. For $p > 2$, the geometry becomes "stretched," and heavy tails in just a few coordinates can ruin the sample mean.
  • A Sharp Phase Transition: The minimax risk doesn't just grow smoothly. It hits a "wall" based on the relationship between sample size $n$, dimension $d$, and the norm $p$.
  • In the Large-Sample Regime, the error behaves like a Gaussian distribution (the "sub-Gaussian" rate).
  • In the Small-Sample Regime, a "genuinely non-Gaussian obstruction" appears, where the error is dominated by heavy-tailed effects that don't exist in Gaussian data.
  • The Failure of Projections: A popular class of robust estimators works by looking at "projections" (shadows) of the data in all directions. The authors prove a surprising result: these sophisticated projection-based estimators are actually polynomially suboptimal for $\ell_p$ norms compared to the simpler coordinate-wise median-of-means.

Key Results

  • Minimax Rate: The authors characterize the optimal expected error. For $p > 2$, the risk transitions from a rate of $d^{1/p} \sqrt{p/n}$ (Gaussian-like) to a much slower $d^{1/(2\lceil n/2 \rceil)}$ when the sample size is small relative to the norm's requirements.
  • Optimality of MoM: They prove that the coordinate-wise MoM, with $t \approx p$ buckets, optimally tracks this phase transition.
  • High-Probability Limits: For the $\ell_\infty$ norm, they provide a sharp characterization of the error even for very high confidence levels ($1-\delta$), showing a similar transition at $n \approx \log(d/\delta)$.

Limitations and Future Work

  • General Norms: While the paper provides a complete picture for $\ell_p$ norms, the "full high probability minimax picture" for more general, arbitrary norms remains unclear.
  • Covariance Structure: The current work assumes an identity covariance matrix (isotropic data). Extending these sharp phase transitions to data with complex, unknown correlation structures is a logical next step.
  • Computational vs. Statistical Trade-offs: While the MoM estimator is computationally efficient, the paper notes that the high-probability theory for general norms is "substantially more delicate" and may involve more complex algorithmic challenges.

Summary updated

Abstract

We study the problem of estimating the mean of a random vector in $\mathbb R^d$ under $\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 $\ell_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 $\ell_p$ norms even in the constant-probability regime.
BibTeX
@misc{adenali2026phase,
  author = {Ishaq Aden-Ali and Yeshwanth Cherapanamjeri and Mikael Møller Høgsgaard and Kasper Green Larsen and Nikita Zhivotovskiy},
  title = {{Phase Transitions in Heavy-Tailed Mean Estimation under $\textbackslash\{\}ell\_p$ Norms}},
  year = {2026},
  eprint = {2611.20176},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.20176},
}
Figure