High-arity PAC learning via exchangeability
This work addresses foundational challenges in machine learning for handling complex relational data, representing a novel theoretical extension rather than an incremental improvement.
The paper tackles the problem of statistical learning with structured correlations by developing a theory of high-arity PAC learning, where hypotheses are relational structures and sampling is based on induced substructures, resulting in an exchangeable distribution; the main result establishes a high-arity version of the fundamental theorem of statistical learning.
We develop a theory of high-arity PAC learning, which is statistical learning in the presence of "structured correlation". In this theory, hypotheses are either graphs, hypergraphs or, more generally, structures in finite relational languages, and i.i.d. sampling is replaced by sampling an induced substructure, producing an exchangeable distribution. Our main theorems establish a high-arity (agnostic) version of the fundamental theorem of statistical learning.