[Colloquium] CS Theory Seminar - Tuesday, October 21

[Jose J Fragoso via Colloquium]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS




Stefan Tiegel
Massachusetts Institute of Technology

[TiegelPhoto.jpg]

Tuesday, October 21, 2025, at 3:30pm
Kent Chemical Laboratory, Room 102



Title: Efficiently Deciding High-Dimensional sub-Gaussian-ness, and its Algorithmic Applications

Abstract: Given i.i.d. 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. This problem is easy in one dimension but challenging in high dimensions: A single direction with a heavy tail can hide in an otherwise light-tailed distribution, seemingly requiring brute-force search to find.

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. Our algorithms are based on the sum-of-squares (SoS) semidefinite programming hierarchy. Specifically, we establish existence of short SoS certificates of light-tailedness for sub-Gaussian data via a novel connection to empirical process theory and Talagrand's Majorizing Measures Theorem.

Based on joint work with Ilias Diakonikolas, Samuel Hopkins, and Ankit Pensia.



Bio: My work is set in learning theory and statistical inference, where I try to understand which problems admit efficient algorithms and which not (and why). This comprises both designing new efficient algorithms as well as showing new hardness results. I am currently a PostDoc at MIT hosted by Samuel Hopkins and Guy Bresler. Previously, I was a PhD student at ETH Zurich, advised by David Steurer.


  Host: Aaron Potechin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20251021/3de8b6d3/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: TiegelPhoto.jpg
Type: image/jpeg
Size: 2195298 bytes
Desc: TiegelPhoto.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20251021/3de8b6d3/attachment-0001.jpg>