Higher-arity PAC learning, VC dimension and packing lemma

Artem Chernikov, Henry Towsner
10/2/2025
stat.MLcs.DMcs.LG

No confident code implementation found for this paper.

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

A packing lemma for VCN${}_k$-dimension and learning high-dimensional data

88% match2025

Uniform Computability of PAC Learning

78% match2026

Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions

77% match2023

Simplicial covering dimension of extremal concept classes

75% match2025

Towards Efficient Contrastive PAC Learning

74% match2025

Optimal Learners for Realizable Regression: PAC Learning and Online Learning

74% match2023

Cite this paper

@article{chernikov2025higherarity,
  title  = {Higher-arity PAC learning, VC dimension and packing lemma},
  author = {Artem Chernikov and Henry Towsner},
  year   = {2025},
  eprint = {2510.02420},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2510.02420v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2510.02420.svg)](https://codeofpaper.com/paper/2510.02420)

Discussion