Sample Compression Schemes for Balls in Graphs
Jérémie Chalopin, Victor D. Chepoi, Fionn Mc Inerney, Sébastien Ratel, Yann Vaxès · SIAM Journal on Discrete Mathematics · 2023
Abstract. One of the open problems in machine learning is whether any set-family of VC-dimension [Formula: see text] admits a sample compression scheme of size [Formula: see text]. In this paper, we study this problem for balls in graphs. For a ball [Formula: see text] of a graph [Formula: see text], a realizable sample for [Formula: see text] is a signed subset [Formula: see text] of [Formula: see text] such that [Formula: see text] contains [Formula: see text] and is disjoint from [Formula: see text]. A proper sample compression scheme of size [Formula: see text] consists of a compressor and a reconstructor. The compressor maps any realizable sample [Formula: see text] to a subsample [Formula: see text] of size at most [Formula: see text]. The reconstructor maps each such subsample [Formula: see text] to a ball [Formula: see text] of [Formula: see text] such that [Formula: see text] includes [Formula: see text] and is disjoint from [Formula: see text]. For balls of arbitrary radius [Formula: see text], we design proper labeled sample compression schemes of size 2 for trees, of size 3 for cycles, of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. For balls of a given radius, we design proper labeled sample compression schemes of size 2 for trees and of size 4 for interval graphs. We also design approximate sample compression schemes of size 2 for balls of [Formula: see text]-hyperbolic graphs.