<html><head><meta http-equiv="content-type" content="text/html; charset=us-ascii"></head><body dir="auto"><div id="mail-editor-reference-message-container" style="-webkit-text-size-adjust: auto;"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><div id="mail-editor-reference-message-container"><p class="MsoNormal" style="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="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="margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;"> </p><img src="cid:05FE65A4-A377-4E65-B1B8-C4A29E5CE9A3" id="FAFE8085-F5E3-4DCE-8E95-AD43A9A93EC6" aria-label="Mail.messageViewer.inlineAttachment.TiegelPhoto.jpg" class="x-apple-edge-to-edge" style="width: calc(100% + 0px); margin-left: 0px; padding: 1px 0px;" alt="cid:FAFE8085-F5E3-4DCE-8E95-AD43A9A93EC6"><p class="MsoNormal" style="margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;"><span style="font-size: 11pt;"> </span> </p><p class="MsoNormal" style="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="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="margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;"><span style="font-size: 11pt;"> </span></p><p class="MsoNormal" style="margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;"><span style="font-size: 11pt;"> </span></p><p class="MsoNormal" style="margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;"><span style="font-size: 12pt;"> </span></p><div><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-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 16px;"><span style="background-color: rgb(255, 255, 255);"><b><br></b></span></div><div dir="ltr" style="background-color: rgb(255, 255, 255); margin: 0px; font-size: 12pt;"><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-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt;"><br></div><div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt;">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-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt;"> </div><div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt;">Based on joint work with Ilias Diakonikolas, Samuel Hopkins, and Ankit Pensia.</div><div dir="ltr" style="font-family: Aptos, Arial, Helvetica, sans-serif; font-size: 12pt;"></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div><div dir="ltr"></div></body></html>