Abstract:
Sub-Gaussian distributions play a central role in statistics, probability, and computer science. A distribution is termed sub-Gaussian if all of its univariate projections have tails that decay faster than a Gaussian. In algorithmic statistics, a central task is the following: given samples from a distribution, decide whether the underlying distribution is sub-Gaussian or heavy-tailed. In high dimensions, this is a challenging problem because sub-Gaussianity requires all univariate projections to be light-tailed, which seemingly necessitates a brute-force search over directions to verify. In this talk, I will describe a structural property of sub-Gaussian distributions that leads to computationally efficient algorithms for a wide range of statistical problems, e.g., clustering, robust estimation, and more. Based on joint work with Ilias Diakonikolas, Sam Hopkins, and Stefan Tiegel.
Short Bio: Ankit Pensia is an assistant professor in the Department of Statistics and Data Science at Carnegie Mellon University. Previously, he was a research fellow at the Simons Institute for the Theory of Computing and a Herman Goldstine Postdoctoral Fellow at IBM Research. He obtained his PhD in Computer Science from the University of Wisconsin-Madison. His current research interests include algorithmic robust statistics, high-dimensional probability, distribution testing, and algorithmic stability.