High-arity Sample Compression
2026-05-12 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study a new area called high-arity learning theory, which looks at learning problems involving combinations or products of multiple variables. They focus on a concept called sample compression schemes, adapted for these high-arity settings. Their main finding is that if a good high-arity sample compression scheme exists, then it guarantees the problem can be learned efficiently using a method called PAC learning. This connects two important ideas in learning theory for more complex input spaces.
high-arity learning theorysample compression schemesPAC learnabilityproduct spaceslearning theorysample complexitycompression schemestatistical learningmachine learning theory
Authors
Leonardo N. Coregliano, William Opich
Abstract
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.