[Theory] UC Theory seminar: a reminder

[Alexander Razborov]

Leonardo Coregliano, PhD
University of Chicago
 
 
 
 
Tuesday, April 9, 2024 at 3:30pm
Room – Kent 107
 
 
 
Title: High-arity PAC learning via exchangeability

Abstract: Classic PAC learning theory studies when we can make an accurate guess of a set based on finitely
many i.i.d.\ samples from it. The Fundamental Theorem of Statistical Learning characterizes when
such an accurate guess can be made in terms of the Vapnik--Chervonenkis dimension. The natural
generalization of PAC learning functions has also been characterized in terms of the Natarajan
dimension (when the co-domain is finite) and in terms of the Daniely--Shalev-Shwartz dimension (for
arbitrary co-domains).

In this talk, we will explore a different generalization, called high-arity PAC learning, that is
motivated by PAC learning of graphs, hypergraphs and relational structures and relies on
exchangeability theory. We will cover the basic definitions, the statement of the high-arity
Fundamental Theorem, some proof ideas and mention the furthest reaches of the theory covering "PAC
learning for (quasi)random graphs".

No prior knowledge of learning theory or exchangeability theory will be required.

This talk is based on joint work with Maryanthe Malliaris.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20240408/64d7859e/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 8832 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20240408/64d7859e/attachment-0001.jpg>