<html><head><meta http-equiv="content-type" content="text/html; charset=us-ascii"></head><body dir="auto"><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;"><span style="font-family: Helvetica; font-size: 14pt;"><b>Stefan Tiegel</b></span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;"><span style="font-family: Helvetica; font-size: 14pt;"><b>Massachusetts Institute of Technology</b></span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;"> </p><img src="cid:5B35A738-D430-4ED7-B724-FC0C6709A342" alt="TiegelPhoto.jpg" id="id-FAFE8085-F5E3-4DCE-8E95-AD43A9A93EC6" data-origin-cid="FAFE8085-F5E3-4DCE-8E95-AD43A9A93EC6" data-origin-width="865" data-origin-height="990" width="272" height="311" style="-webkit-text-size-adjust: auto; width: 272px; height: 311px;"><span style="-webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255);"></span><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;"><span style="font-size: 11pt;"> </span> </p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;"><span style="font-size: 11pt;"><b><span dir="ltr">Tuesday, October 21, 202</span></b></span><span style="font-size: 11pt;"><b><span dir="ltr">5,</span></b></span><span style="font-size: 11pt;"><b><span dir="ltr"> at 3:30pm</span></b></span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;"><span style="font-size: 11pt; background-color: yellow;"><b>Kent Chemical Laboratory, Room 102</b></span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;"><span style="font-size: 11pt;"> </span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;"><span style="font-size: 11pt;"> </span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;"><span style="font-size: 12pt;"> </span></p><div style="-webkit-text-size-adjust: auto;"><span style="font-family: Aptos, Arial, Helvetica, sans-serif; font-size: 12pt; background-color: rgb(255, 255, 255);"><b><i>Title: </i></b></span><span style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 16px; background-color: rgb(255, 255, 255);">Efficiently Deciding High-Dimensional sub-Gaussian-ness, and its Algorithmic Applications</span></div><div dir="ltr" style="font-size: 16px; -webkit-text-size-adjust: auto; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;"><span style="background-color: rgb(255, 255, 255);"><b><br></b></span></div><div dir="ltr" style="font-size: 12pt; -webkit-text-size-adjust: auto; background-color: rgb(255, 255, 255); margin: 0px;"><span style="font-family: Aptos, Arial, Helvetica, sans-serif;"><b><i>Abstract: </i></b></span><span style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;">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.</span></div><div dir="ltr" class="elementToProof" style="font-size: 12pt; -webkit-text-size-adjust: auto; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;"><br></div><div class="elementToProof" style="font-size: 12pt; -webkit-text-size-adjust: auto; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;">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.</div><div class="elementToProof" style="font-size: 12pt; -webkit-text-size-adjust: auto; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;"> </div><div class="elementToProof" style="font-size: 12pt; -webkit-text-size-adjust: auto; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;">Based on joint work with Ilias Diakonikolas, Samuel Hopkins, and Ankit Pensia.</div><div dir="ltr"></div></body></html>