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

Sep 1, 2026

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

We revisit median-of-means estimation from a deterministic optimization viewpoint and develop a family of block-Lp estimators for robust learning with heavy-tailed and adversarially corrupted data. In a block contamination model with at least a fraction 1 minus epsilon of good blocks, we first show that every convex block M-estimator has worst-case robustness constant at least 1 divided by 1 minus 2 epsilon. This matches the classical median-of-means bound and proves that the trimmed-block oracle constant 1 divided by 1 minus epsilon cannot be attained within the convex class. We then introduce a nonconvex block-Lp family for p between 0 and 1 and derive finite-sample deterministic robustness bounds for all global minimizers. As p decreases from 1 toward 0, these bounds continuously approach the trimmed-block oracle constant. For sufficiently small p, the global minimizers coincide with those of the oracle under a mild separation condition. We also show that the block-Lp objectives have a benign landscape, with all local minima remaining close to the truth and no bad basins. Combining these results with block-level concentration yields sub-Gaussian deviation bounds under finite 2 plus delta moments and high-dimensional extensions to robust mean estimation and sparse regression.
Mar 11, 2026

Heavy-Tailed Principal Component Analysis

Principal Component Analysis (PCA) is a cornerstone of dimensionality reduction, yet its classical formulation relies critically on second-order moments and is therefore fragile in the presence of heavy-tailed data and impulsive noise. While numerous robust PCA variants have been proposed, most either assume finite variance, rely on sparsity-driven decompositions, or address robustness through surrogate loss functions without a unified treatment of infinite-variance models. In this paper, we study PCA for high-dimensional data generated according to a superstatistical dependent model of the form X=A1/2G\mathbf{X} = A^{1/2}\mathbf{G}, where AA is a positive random scalar and G\mathbf{G} is a Gaussian vector. This framework captures a wide class of heavy-tailed distributions, including multivariate tt and sub-Gaussian αα-stable laws. We formulate PCA under a logarithmic loss, which remains well defined even when moments do not exist. Our main theoretical result shows that, under this loss, the principal components of the heavy-tailed observations coincide with those obtained by applying standard PCA to the covariance matrix of the underlying Gaussian generator. Building on this insight, we propose robust estimators for this covariance matrix directly from heavy-tailed data and compare them with the empirical covariance and Tyler's scatter estimator. Extensive experiments, including background denoising tasks, demonstrate that the proposed approach reliably recovers principal directions and significantly outperforms classical PCA in the presence of heavy-tailed and impulsive noise, while remaining competitive under Gaussian noise.
Sep 3, 2026

Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails

Restricted eigenvalue (RE) bounds govern stable recovery by norm-regularized estimators. For isotropic sub-Gaussian measurements, the benchmark sample size is 1+w(A)21+w(A)^2, where w(A)w(A) is the Gaussian width of the normalized descent cone. The COLT 2015 open-problem note (Banerjee et al., 2015) asked whether the same law follows for heavy-tailed designs from a uniform small-ball condition alone. We give an explicit and systematic negative answer to the general question as formulated there: the proposed law fails in its full dimension-free, arbitrary-set form, and the missing obstruction is simultaneous threshold occupancy. A constant-width polyhedral descent cone with fixed small-ball constants has zero empirical RE on every sample path up to half the ambient dimension. More generally, every finite range space admits exact threshold encoding in an arbitrarily narrow spherical cap and a lift to a full polyhedral descent-cone section. For every fixed threshold VC dimension dd, as β↓0β\downarrow0, the sharp worst-case sample complexity is Θ(β−1[dlog⁡(1/β)+log⁡(1/δ)])Θ(β^{-1}[d\log(1/β)+\log(1/δ)]). The separation persists under exact isotropy and all finite moments: on the same constant-width cone, Gaussian measurements succeed with O(1+log⁡(1/δ))O(1+\log(1/δ)) samples, whereas an isotropic heavy-tailed design fails pathwise for n≲p/log⁡pn\lesssim\sqrt{p/\log p}. Gaussian smoothing yields an everywhere-positive C∞C^\infty density while retaining arbitrarily poor RE. Under isotropy, a distribution-free fallback governed by affine dimension times squared enclosing radius is sharp on this family.