Higher-arity PAC learning, VC dimension and packing lemma
This work provides a foundational extension of learning theory to higher-arity domains, which is incremental as it builds on prior concepts like VC dimension and PAC learning.
The paper tackles the problem of extending VC theory and PAC learning to higher-arity settings, showing that their developed VC_n dimension characterizes PAC_n learning in n-fold product spaces with respect to product measures.
The aim of this note is to overview some of our work in Chernikov, Towsner'20 (arXiv:2010.00726) developing higher arity VC theory (VC$_n$ dimension), including a generalization of Haussler packing lemma, and an associated tame (slice-wise) hypergraph regularity lemma; and to demonstrate that it characterizes higher arity PAC learning (PAC$_n$ learning) in $n$-fold product spaces with respect to product measures introduced by Kobayashi, Kuriyama and Takeuchi'15. We also point out how some of the recent results in arXiv:2402.14294, arXiv:2505.15688, arXiv:2509.20404 follow from our work in arXiv:2010.00726.