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. A few extensions of the PAC learning framework were made to address the case when the sample are not independent but have “reasonable” correlation. However, in these attempts, correlation is seen as an obstacle to overcome in the learning task.

In this first talk of a series of three, I will present an overview of the new framework of high-arity learning, in which structured-correlation is used to increase the learning power. I will also talk about a connection of learning theory to hypergraph regularity lemmas via Haussler packing property.

No background in learning theory or regularity lemmas is required for this talk.

This talk is based on joint works with Maryanthe Malliaris and Caroline Terry.