# High-arity Sample Compression

arXiv: https://arxiv.org/abs/2605.12465 · HTML: https://mlsanity.com/paper/2605.12465/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 28 references that are in the map.
- First posted on arXiv 12 May 2026.

## Builds on (most cited first, 4 of 4)

- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [On statistical learning via the lens of compression](https://mlsanity.com/paper/1610.03592/) (2016)
- [Graph-based Discriminators: Sample Complexity and Expressiveness](https://mlsanity.com/paper/1906.00264/) (2019)
- [Uniform Laws of Large Numbers in Product Spaces](https://mlsanity.com/paper/2603.24493/) (2026)

## Abstract (arXiv)

Recently, a series of works have started studying variations of concepts from learning theory for product spaces, which can be collected under the name high-arity learning theory. In this work, we consider a high-arity variant of sample compression schemes and we prove that the existence of a high-arity sample compression scheme of non-trivial quality implies high-arity PAC learnability.