[Colloquium] CS Theory Seminar, Tuesday, April 9: Kent 107

[Jose J Fragoso]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS



Leonardo Coregliano, PhD
University of Chicago

 [A person in a blue shirt  Description automatically generated]


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.

Bio: Leonardo Nagami Coregliano is an L.E. Dickson Instructor at The University of Chicago. He also
received his Ph.D. in Mathematics and Computer Science at The University of Chicago, advised by
Professor Alexander Razborov. His research focuses on interactions of combinatorics and model
theory, with particular emphasis on asymptotic combinatorics and limit theory.


Host: Alexander Razborov

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240409/6e2fd8a3/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 8832 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20240409/6e2fd8a3/attachment-0001.jpg>