[Theory] UC Theory seminar: a reminder

[Alexander Razborov via Theory]

Stefan Tiegel
Massachusetts Institute of Technology
 

  
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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20251020/f2bf9a17/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cid:FAFE8085-F5E3-4DCE-8E95-AD43A9A93EC6.jpeg
Type: image/jpeg
Size: 479014 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20251020/f2bf9a17/attachment-0001.jpeg>