DOI: 10.1145/3838723 ISSN: 0004-5411
High-arity PAC learning via exchangeability
Leonardo Coregliano, Maryanthe MalliarisWe develop a theory of high-arity PAC (probably approximately correct) 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.