betaFeedback

WorksMathematics

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

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.

Introduction

Mean estimation, or location estimation, is one of the foundational subroutines in machine learning and statistics. A modern line of work focuses on statistical estimators that are robust to heavy-tailed distributions. Starting with the systematic study pioneered by Catoni [6], this line of work seeks to obtain non-asymptotic sub-Gaussian rates for estimating the means of random variables, usually using estimators such as the median of means, which appeared independently in [NY83, JVV86, AMS99], Catoni’s estimator [6], or trimmed-mean estimators [16]. As we recall later, more involved versions of these estimators also work well in high-dimensional regimes, where the primary focus has traditionally been on the Euclidean norm.

However, the Euclidean norm is arguably the most benign norm to work with. Indeed, given nn independent vectors X1,…,XnX_1,\ldots,X_n in Rd\mathbb{R}^d with common mean μ\mu and identity covariance IdI_d, the sample mean is essentially optimal, up to universal constant factors for all nn and dd:

E∥1n∑i=1nXi−μ∥2≤dn,(1)\mathbb{E}\left\|\frac{1}{n}\sum_{i=1}^{n}X_i-\mu\right\|_2\le\sqrt{\frac{d}{n}}, \tag*{(1)}

which follows from Cauchy–Schwarz and does not require the existence of any moments above the second moment, while the lower bound follows from Anderson’s lemma [3] as discussed below. Assuming only the existence of the covariance, and no higher moments, the main focus has therefore been on obtaining sub-Gaussian estimators, namely estimators with optimal sub-Gaussian type tails, where the sample mean is clearly the wrong object [Min15, LM19b, CG17, LM21].

When going beyond the Euclidean norm, while still keeping only the bounded covariance assumption, even the in expectation story of (1) becomes more delicate especially in the high-dimensional regime where the dimension dd is larger than the sample size nn. In non-Hilbertian geometries, the vanilla sample mean is no longer necessarily a good estimator.6 Our key contribution is to show that the Euclidean picture is special even for the simple mean estimation problem in Rd\mathbb{R}^d. For ℓp\ell_p norms with p>2p>2, robustification can be necessary even for in expectation bounds of the form (1). This phenomenon does not appear in the regime 1≤p≤21\le p\le2, where the sample mean remains optimal up to universal constants, but it becomes crucial once the geometry of the loss is sufficiently far from ℓ2\ell_2.

Theorem 1.1 (Phase transition for location estimation in ℓp\ell_p, informal). Under only the covariance assumption Cov⁡P(X)=Id\operatorname{Cov}_P(X)=I_d, the optimal expected error for estimating the mean in ℓp\ell_p satisfies

inf⁡μ^sup⁡μ∈RdP:EP[X]=μCov⁡P(X)=IdE∥μ^−μ∥p≍{d12⌈n/2⌉,pˉ>2⌈n/2⌉,d1pˉpˉn,pˉ≤2⌈n/2⌉,\inf_{\widehat{\mu}}\sup_{\substack{\mu\in\mathbb{R}^d\\P:\mathbb{E}_P[X]=\mu\\\operatorname{Cov}_P(X)=I_d}}\mathbb{E}\|\widehat{\mu}-\mu\|_p\asymp \begin{cases} d^{\frac{1}{2\lceil n/2\rceil}}, & \bar p>2\lceil n/2\rceil,\\ d^{\frac{1}{\bar p}}\sqrt{\frac{\bar p}{n}}, & \bar p\le2\lceil n/2\rceil, \end{cases}

where μ^\widehat{\mu} ranges over all estimators based on the nn samples and

pˉ=min⁡{p,max⁡{log⁡d,1}}.\bar p=\min\{p,\max\{\log d,1\}\}.

Thus, the minimax risk undergoes a sharp phase transition. In the large sample regime, the rate has the familiar Gaussian form, corresponding to the Gaussian width of the dual ball inducing the norm, as we discuss below:

d1/pˉpˉn.d^{1/\bar p}\sqrt{\frac{\bar p}{n}}.

In contrast, in the small sample or large pp regime, the effective exponent is capped by the number of samples, and the optimal rate becomes

d12⌈n/2⌉.d^{\frac{1}{2\lceil n/2\rceil}}.

We show that a estimator achieving this rate is a simple coordinate-wise median of means estimator, with the choice of number of buckets depending on the geometry of the loss. Recall that median of means first splits the sample into nearly equal buckets, computes the average inside each bucket, and then takes a median of these bucket averages. In the coordinate-wise version used here, if Xˉ(1),…,Xˉ(t)\bar{X}^{(1)}, \ldots, \bar{X}^{(t)} denote the nonempty bucket averages, the estimator is defined by

μ^j=Median⁡({Xˉj(1),…,Xˉj(t)}),j=1,…,d.\widehat{\mu}_j = \operatorname{Median}\left(\left\{\bar{X}^{(1)}_j,\ldots,\bar{X}^{(t)}_j\right\}\right), \qquad j=1,\ldots,d.

The number of buckets is dictated by the geometry of the loss, namely by the effective exponent pˉ\bar{p}. More precisely, the estimator uses

t(pˉ)=2⌊pˉ2⌋−1t(\bar{p}) = 2\left\lfloor\frac{\bar{p}}{2}\right\rfloor- 1

buckets, with the median taken over the nonempty buckets. When 1≤p<21 \le p < 2, we have t(pˉ)=1t(\bar{p}) = 1, so the estimator is just the ordinary sample mean. The same happens at p=2p = 2, recovering exactly the Euclidean behavior in (1). When p>2p > 2 and pˉ>2\bar{p} > 2, the estimator becomes a genuine coordinate-wise median of means estimator, with the number of buckets increasing with pˉ\bar{p}. Finally, in the extreme regime where t(pˉ)>nt(\bar{p}) > n, every nonempty bucket contains a single observation, and the procedure reduces to the coordinate-wise median of the sample points. The technical difficulty is to show that these regimes match sharply and together give the precise minimax rate above.

Phase transition and the existing general norm results. Our in expectation analysis complements the existing high probability theory of robust mean estimation with respect to general norms. Sub-Gaussian mean estimators for general norms were studied, in different forms, in [14 Min25, 10]. The original benchmark in [14] is distribution dependent and is centered around robustly reproducing the performance of the empirical mean, together with the correct one dimensional sub-Gaussian deviation term. Informally, in our ℓp\ell_p setup this benchmark contains a term of the form

E∥1n∑i=1n(Xi−μ)∥p,\mathbb{E}\left\|\frac{1}{n}\sum_{i=1}^{n}(X_i-\mu)\right\|_p,

or its symmetrized analogue. This is the natural target if the goal is to obtain optimal high probability tails around the performance of the sample mean. However, for the problem considered in this paper, this benchmark can be too large: as follows from our results, for p>2p > 2, the sample mean itself is already suboptimal even in expectation.7

A related but different point is emphasized in [10]. If one takes Gaussian mean estimation as the benchmark, then the relevant complexity is the Gaussian width of the dual ball inducing the norm. In the case of the ℓp\ell_p norm and identity covariance, this gives

E∥G∥pn≍d1/pˉpˉn,\frac{\mathbb{E}\|G\|_p}{\sqrt{n}} \asymp d^{1/\bar{p}}\sqrt{\frac{\bar{p}}{n}},

where G∼N(0,Id)G \sim N(0,I_d) and pˉ=min⁡{p,max⁡{log⁡d,1}}\bar{p} = \min\{p,\max\{\log d,1\}\}. Thus, the second branch of our theorem,

d1/pˉpˉn,d^{1/\bar{p}}\sqrt{\frac{\bar{p}}{n}},

coincides exactly with the Gaussian width benchmark. In this regime, our estimator achieves the same rate that the sample mean would have for Gaussian data; this may be called the sub-Gaussian regime. The genuinely new phenomenon provided by our analysis is the first branch,

d21/pˉ.d^{2^{1/\bar{p}}}.

This term does not appear in the Gaussian mean estimation setup. It reflects a finite sample heavy-tailed regime under only a covariance assumption. Morally, the Gaussian width rate is correct once the number of samples is large enough relative to the effective exponent pˉ\bar{p}. When this condition fails, the minimax risk enters a different phase.

Phase transition and the Gaussian location estimation problem. The Gaussian width branch of Theorem 1.1 is also closely connected to the classical minimax theory of Gaussian location estimation. In the Gaussian location model, Anderson’s lemma implies an exact minimax identity for every bowl-shaped loss; see the original inequality of Anderson [3] and the modern presentation in [PW25, Section 28.6]. In particular, for X1,…,Xn∼N(μ,Id)X_1,\ldots,X_n \sim N(\mu,I_d), Anderson’s lemma implies

inf⁡μ^sup⁡μ∈RdE∥μ^−μ∥p=E∥G∥pn≍d1/pˉpˉn,G∼N(0,Id),pˉ=min⁡{p,max⁡{log⁡d,1}}.\inf_{\widehat{\mu}}\sup_{\mu\in\mathbb{R}^d}\mathbb{E}\|\widehat{\mu}-\mu\|_p = \frac{\mathbb{E}\|G\|_p}{\sqrt{n}} \asymp d^{1/\bar{p}}\sqrt{\frac{\bar{p}}{n}}, \qquad G\sim N(0,I_d),\qquad\bar{p}=\min\{p,\max\{\log d,1\}\}.

Thus, as discussed above, the second branch of our theorem is exactly the classical Gaussian location obstruction. Our result shows that this Gaussian answer is not the whole story under only a covariance assumption. For the much larger class of all distributions with covariance IdI_d, the Gaussian benchmark remains sharp only when

pˉ≤2⌊n2⌋.\bar{p}\le2\left\lfloor\frac{n}{2}\right\rfloor.

When this condition fails, heavy-tailed distributions create an additional obstruction, and the minimax risk becomes d21/pˉd^{2^{1/\bar{p}}}. In this sense, Theorem 1.1 may be viewed as a heavy-tailed, covariance-only analogue of the classical Gaussian location minimax identity.

High probability implications and limitations of projection-based estimators. As of now, the full high probability minimax picture for ℓp\ell_p norms remains unclear. In particular, the aforementioned general norm results do not directly provide the matching high probability behavior for ℓp\ell_p norms under only the covariance assumption. Our theorem in expectation already shows that the sample mean can be suboptimal. On the negative side, we further show that natural projection-based median of means estimators, of the type used in the general norm theory [14 Min25, 10 OR25], can also fail to achieve the correct ℓp\ell_p behavior.

Informally, a projection-based median of means estimator works as follows. It searches for a point whose projection in every dual direction agrees with the median of the projected bucket means:

References

  1. [1][AM26] Pedro Abdalla and Shahar Mendelson. Covariance estimation with direction dependence accuracy. Probability Theory and Related Fields, 194(1–2):371–409, 2026. 6arxiv.org/abs/2402.08288
  2. [3][And55] T. W. Anderson. The integral of a symmetric unimodal function over a symmetric convex set and some probability inequalities. Proceedings of the American Mathematical Society, 6(2):170–176, 1955. 2, 4, 10, 17DOI
  3. [4]Pedro Abdalla and Nikita Zhivotovskiy. Covariance estimation: Optimal dimension-free guarantees for adversarial corruption and heavy tails. Journal of the European Mathematical Society, 28(4):1809–1847, 2026. 2
  4. [5]Daniel Bartl and Shahar Mendelson. Uniform mean estimation via generic chaining. Advances in Mathematics, 493, 2026. 6
  5. [6]Olivier Catoni. Challenging the empirical mean and empirical variance: a deviation study. In Annales de l’IHP Probabilités et statistiques, volume 48, pages 1148–1185, 2012. 1arxiv.org/abs/1009.2048
  6. [7]Yeshwanth Cherapanamjeri, Nicolas Flammarion, and Peter L. Bartlett. Fast mean estimation with sub-Gaussian rates. In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 786–806. PMLR, 2019. 6arxiv.org/abs/1902.01998
  7. [9]Ilias Diakonikolas, Daniel M. Kane, and Ankit Pensia. Outlier robust mean estimation with subgaussian rates via stability. In Advances in Neural Information Processing Systems, volume 33, pages 1830–1840, 2020. 6arxiv.org/abs/2007.15618
  8. [10]Jules Depersin and Guillaume Lecué. Optimal robust mean and location estimation via convex programs with respect to any pseudo-norms. Probability Theory and Related Fields, 183(3):1005–1056, 2022. 3, 4
  9. [11]Samuel B. Hopkins, Jerry Li, and Fred Zhang. Robust and heavy-tailed mean estimation made simple, via regret minimization. In Advances in Neural Information Processing Systems, volume 33, pages 11902–11912, 2020. 6
  10. [12]Samuel B. Hopkins. Mean estimation with sub-Gaussian rates in polynomial time. The Annals of Statistics, 48(2):1193–1213, 2020. 6arxiv.org/abs/1809.07425
  11. [14]Gábor Lugosi and Shahar Mendelson. Near-optimal mean estimators with respect to general norms. Probability Theory and Related Fields, 175(3–4):957–973, 2019. 3, 4arxiv.org/abs/1806.06233
  12. [16]Gábor Lugosi and Shahar Mendelson. Robust multivariate mean estimation: The optimality of trimmed mean. The Annals of Statistics, 49(1):393–410, 2021. 1, 2arxiv.org/abs/1907.11391
  13. [17]Kasper Green Larsen, Rasmus Pagh, and Jakub Tetek. Countsketches, feature hashing and the median of three. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18–24 July 2021, Virtual Event, Proceedings of Machine Learning Research, pages 6011–6020. PMLR, 2021. 8arxiv.org/abs/2102.02193

Paper details

vlnc:W_9kscfc7x
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents