Higher-arity PAC learning, VC dimension and packing lemma

Abstract

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.

v.2. Corrected our presentation of PAC_n learning in the sense of Takeuchi et al. in section 4; and slightly improved the PAC_n learning function in Theorem 6.5 to additionally ensure its properness