<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div dir="ltr"></div><div dir="ltr">Correction: the talk will be on *Tuesday*, March 9. </div><div dir="ltr"><br><blockquote type="cite">On Apr 2, 2024, at 10:25 AM, Alexander Razborov <razborov@uchicago.edu> wrote:<br><br></blockquote></div><blockquote type="cite"><div dir="ltr"><meta http-equiv="content-type" content="text/html; charset=utf-8">*Note a different room*.<div dir="ltr"></div><div><br></div><div><div style="-webkit-text-size-adjust: auto;"><p class="MsoNormal" style="margin: 0in; font-size: 12pt; font-family: Aptos, sans-serif; caret-color: rgb(33, 33, 33);"><b><span style="font-family: Helvetica; color: rgb(33, 33, 33);">Leonardo Coregliano, PhD</span></b><span style="font-size: 10pt; font-family: Calibri, sans-serif; color: rgb(33, 33, 33);"><o:p></o:p></span></p><p class="MsoNormal" style="margin: 0in; font-size: 12pt; font-family: Aptos, sans-serif; caret-color: rgb(33, 33, 33);"><b><span style="color: rgb(33, 33, 33);">University of Chicago</span></b><span style="font-size: 10pt; font-family: Calibri, sans-serif; color: rgb(33, 33, 33);"><o:p></o:p></span></p><p class="MsoNormal" style="margin: 0in; font-size: 12pt; font-family: Aptos, sans-serif; caret-color: rgb(33, 33, 33);"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(33, 33, 33);"> </span><span style="font-size: 10pt; font-family: Calibri, sans-serif; color: rgb(33, 33, 33);"><o:p></o:p></span></p><p class="MsoNormal" style="margin: 0in; font-size: 12pt; font-family: Aptos, sans-serif; caret-color: rgb(33, 33, 33);"><span style="font-size: 10pt; font-family: Calibri, sans-serif; color: rgb(33, 33, 33);"> <div><image001.jpg></div><o:p></o:p></span></p><p class="MsoNormal" style="margin: 0in; font-size: 12pt; font-family: Aptos, sans-serif; caret-color: rgb(33, 33, 33);"><b><span style="font-size: 11pt; font-family: Helvetica;"> </span></b><span style="font-size: 10pt; font-family: Calibri, sans-serif; color: rgb(33, 33, 33);"><o:p></o:p></span></p><p class="MsoNormal" style="margin: 0in; font-size: 12pt; font-family: Aptos, sans-serif; caret-color: rgb(33, 33, 33);"><span style="font-size: 10pt; font-family: Calibri, sans-serif; color: rgb(33, 33, 33);"> <o:p></o:p></span></p><p class="MsoNormal" style="margin: 0in; font-size: 12pt; font-family: Aptos, sans-serif; caret-color: rgb(33, 33, 33);"><b><span style="font-size: 11pt; font-family: Calibri, sans-serif; background: yellow;"><span dir="ltr">Monday, April 9, 2024 at 3:30pm</span></span></b><span style="font-size: 10pt; font-family: Calibri, sans-serif; color: rgb(33, 33, 33);"><o:p></o:p></span></p><p class="MsoNormal" style="margin: 0in; font-size: 12pt; font-family: Aptos, sans-serif; caret-color: rgb(33, 33, 33);"><b><span style="font-size: 11pt; font-family: Calibri, sans-serif; background: yellow;">Room – Kent 107</span></b><span style="font-size: 10pt; font-family: Calibri, sans-serif; color: rgb(33, 33, 33);"><o:p></o:p></span></p><p class="MsoNormal" style="margin: 0in; font-size: 12pt; font-family: Aptos, sans-serif; caret-color: rgb(33, 33, 33);"><span style="font-size: 11pt; font-family: Calibri, sans-serif;"> </span><span style="font-size: 10pt; font-family: Calibri, sans-serif; color: rgb(33, 33, 33);"><o:p></o:p></span></p><p class="MsoNormal" style="margin: 0in; font-size: 12pt; font-family: Aptos, sans-serif;"><o:p> </o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 12pt; font-family: Aptos, sans-serif;"><o:p> </o:p></p></div><div style="-webkit-text-size-adjust: auto;"><p class="MsoNormal" style="margin: 0in; font-size: 12pt; font-family: Aptos, sans-serif;"><b><i>Title:</i></b> <span style="font-family: Calibri, sans-serif;">High-arity PAC learning via exchangeability<br></span><br><b><i>Abstract:</i></b> <span style="font-family: Calibri, sans-serif;">Classic PAC learning theory studies when we can make an accurate guess of a set based on finitely<br>many i.i.d.\ samples from it. The Fundamental Theorem of Statistical Learning characterizes when<br>such an accurate guess can be made in terms of the Vapnik--Chervonenkis dimension. The natural<br>generalization of PAC learning functions has also been characterized in terms of the Natarajan<br>dimension (when the co-domain is finite) and in terms of the Daniely--Shalev-Shwartz dimension (for<br>arbitrary co-domains).<br><br>In this talk, we will explore a different generalization, called high-arity PAC learning, that is<br>motivated by PAC learning of graphs, hypergraphs and relational structures and relies on<br>exchangeability theory. We will cover the basic definitions, the statement of the high-arity<br>Fundamental Theorem, some proof ideas and mention the furthest reaches of the theory covering "PAC<br>learning for (quasi)random graphs".<br><br>No prior knowledge of learning theory or exchangeability theory will be required.<br><br>This talk is based on joint work with Maryanthe Malliaris.</span></p></div></div></div></blockquote></body></html>