stat.MLNov 9, 2026

VC-Dimension and Generalization in Geometric Machine Learning with Applications to Active Learning

Authors: Gokul Bhusal, Delanna Do, Ekaterina Merkurjev, Kevin Miller, Stephan Wojtowytsch

Abstract

We compute the VC-dimension of metric ball classifiers in the model spaces of Riemannian geometry (Euclidean, spherical, hyperbolic) and present upper and lower bounds on the VC-dimension of metric balls in several other situations, including general normed vector spaces (potentially infinite VC-dimension), vector spaces with ℓp\ell^p-norms (VC-dimension grows at least linearly in the dimension, faster than Euclidean for p=1p=1), flat tori, and general Riemannian manifolds (arbitrarily large VC-dimension after a conformal change). In several situations where the VC-dimension is large or even infinite, we prove generalization bounds under additional assumptions on the data distribution using covering arguments. Both in the VC-dimension and covering setting, we consider data on low-dimensional subsets of high-dimensional Euclidean spaces. As an application, we consider coverage-based algorithms in active learning.

Figures & tables

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Jul 12, 2026

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

Following Alon, Hanneke, Holzman, and Moran (FOCS 2021), we define a partial concept class (PCC) as a family of partial functions f:V→{0,1,∗}f: V\to\{0,1,\ast\}; equivalently, its concepts partition the ground set into black (f−1(1)f^{-1}(1)), grey (f−1(∗)f^{-1}(\ast)), and white parts (f−1(0)f^{-1}(0)). Its VC dimension is defined by shattering sets on which the value ∗\ast is not taken. We study two geometric PCCs in real Banach spaces, both with a margin δ>0δ>0: expanded half-spaces, where the grey part is a strip of width at least δδ adjacent to a half-space, and expanded balls, where the grey part is an annulus of width δδ around a unit radius ball. Our main results are dimension-free upper bounds on the VC dimension of the PCC of expanded balls in Lp\parenthμL_p\parenthμ, 1≤p<∞1\le p<\infty, including the non-Euclidean and algorithmically particularly relevant case ℓ1d\ell^d_1. These bounds depend on the margin and on the radii, but not on the ambient dimension or the underlying measure space. These are extensions of the work of Bourneuf, Charbit, and Thomassé (FOCS 2025) who studied the PCC of expanded balls in Euclidean space, that is, ℓ2d\ell_2^d. We also prove lower bounds on the VC dimension that match the upper bounds in terms of the margin parameter δδ. Finally, we derive a Dense Neighborhood Lemma in LpL_p-spaces, again extending the known Euclidean results. Our method relies on the linearization of the distance through a map into a space of non-trivial Rademacher type, and then the use of a balanced signed-sum estimate, or a no-dimensional Radon theorem. The arguments rely on ideas from functional analysis that are clearly explained for the non-expert in that field.
Sep 30, 2026

Optimal VC Dimension of Contrastive Learning with Margin

Contrastive learning is a successful paradigm for learning dd-dimensional geometric representations from a collection of anchor--positive--negative'' triplets $(i,j^{+},k^{-})$, indicating that item ii is closer to jj than to kk.'' Despite its success, understanding why contrastive learning leads to representations of high generalization quality---beyond the often pessimistic predictions from PAC-learning---remains a central question. Recently, \citet*{alon2024optimal} proved that, for PAC-learning dd-dimensional Euclidean representations of nn-point datasets, Θ(min⁡(nd,n2))Θ(\min(nd, n^2)) triplets are necessary and sufficient, while they posed as an open question whether their VC dimension bounds for the more realistic setting of contrastive learning with a margin can be improved. For a margin parameter α>0α>0, a triplet (i,j+,k−)α(i,j^{+},k^{-})_α is satisfied by the embedding φ:[n]→Rdφ:[n]\rightarrow \mathbb{R}^{d}, if ∥φ(i)−φ(k)∥2>(1+α)⋅∥φ(i)−φ(j)∥2\|φ(i)-φ(k)\|_2>(1+α)\cdot\|φ(i)-φ(j)\|_2. In this work, we resolve their question by proving that the VC dimension of contrastive learning under any margin α∈(0,1)α\in(0,1) is in fact O(n/α2)O(n/α^2), improving on the previous bound of O(nlog⁡(n)/α2)O(n\log(n)/α^2). We also establish that the bounds are optimal up to constant factors, by providing a matching lower bound of Ω(nα2)Ω(\frac{n}{α^2}) (the previously known lower bound was Ω(nα)Ω(\frac{n}α)), for α≥max⁡(n−1/2,d−1/2)α\geq \max(n^{-1/2},d^{-1/2}).
Oct 29, 2026

Formalizing the Intrinsic Dimension of Objective Landscapes by a Generalized Notion of Co-dimension

In this work, we formalize the concept of intrinsic dimension of objective landscapes introduced in Li et al. (2018), which measures the structural complexity of learning problems by training along randomly generated subspaces. We define the intrinsic dimension of a set Θ⊂RpΘ\subset\mathbb{R}^p as the minimal dimension dint(Θ)d_{\mathrm{int}}(Θ) such that a random plane of dimension dint(Θ)d_{\mathrm{int}}(Θ) in Rp\mathbb{R}^p intersects ΘΘ with probability one. We show that it is a generalized notion of co-dimension that depends on the global geometry of ΘΘ. We study mathematical properties of the intrinsic dimension and develop techniques to estimate the intrinsic dimension of sets ΘΘ that arise in learning problems. More specifically, we derive upper and/or lower bounds where ΘΘ is the set of optimal parameters in student-teacher settings with shallow and deep ReLU networks, including finite and infinite sample cases, and with and without regularization. We discuss how our theory leads to novel types of generalization bounds, thereby showing that the intrinsic dimension is a measure of learning complexity. Our results connect techniques from seemingly different areas of machine learning research such as classification of symmetries of ReLU networks and stochastic geometry.