{"ID":2861554,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.02420","arxiv_id":"2510.02420","title":"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.","short_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 ar...","url_abs":"https://arxiv.org/abs/2510.02420","url_pdf":"https://arxiv.org/pdf/2510.02420v2","authors":"[\"Artem Chernikov\",\"Henry Towsner\"]","published":"2025-10-02T15:54:50Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.DM\",\"cs.LG\",\"math.CO\",\"math.LO\",\"math.ST\"]","methods":"[]","has_code":false}