  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.
