Mathematics · Research talk

The VC dimension of partial concept classes via Radon's theorem

Márton Naszódi


Abstract

Following Alon, Ben-David, Cesa-Bianchi, and Haussler, we define a partial concept class (PCC) as a family of partial functions \(V\to\{0,1,\ast\}\); its Vapnik–Chervonenkis (VC) dimension is defined through shattering in which the undefined value \(\ast\) is forbidden on the shattered set. We study two geometric PCCs in a (possibly infinite-dimensional) real Banach space \(X\), each carrying a margin \(\delta>0\): the expanded half-spaces, and the expanded balls of unit radius with centers in a fixed ball. We prove bounds on their VC dimension that are dimension-free: they depend on the margin \(\delta\) (and, for balls, on the radii), but not on \({\rm dim}\,X\).

Our main contribution concerns the PCC of expanded balls in \(\ell_p\) and \(L_p(\mu)\) with \(1\le p<\infty\), which extends the work of Bourneuf, Charbit, and Thomassé who studied the PCC of expanded balls in Euclidean space, that is, \(\ell_2^d\). As an application we derive a Dense Neighborhood Lemma in these spaces.

Joint work with Grigory Ivanov and Attila Jung.