Given samples from a probability distribution, can efficient
algorithms tell whether the distribution has heavy or light tails?
This problem is at the core of algorithmic statistics, where
algorithms for deciding heavy-versus-light tailed-ness are key
subroutines for clustering, learning in the presence of adversarial
outliers, and more. It is easy in one dimension but challenging in
high dimensions, where a distribution can have light tails in some
directions and heavy ones in others -- detecting a single direction
with a heavy tail hiding in an otherwise light-tailed distribution can
seemingly require brute-force search. In this talk, I describe a
family of efficient algorithms for deciding whether a high-dimensional
probability distribution has sub-Gaussian tails, with applications to
a wide range of high-dimensional learning tasks using sub-Gaussian
data.
Based on joint work with Ilias Diakonikolas, Ankit Pensia, and Stefan
Tiegel, appearing in STOC 2025