VC-Dimension and Generalization in Geometric Machine Learning with Applications to Active Learning
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 -norms (VC-dimension grows at least linearly in the dimension, faster than Euclidean for ), 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
| Half-spaces in | |
|---|---|
| VC-dimension = | VC-dimension = |
| • Open homogeneous half-spaces • Closed homogeneous half-spaces • Closed strictly exterior half-spaces • Closed strictly interior half-spaces • Closed interior half-spaces | • All open half-spaces • All closed half-spaces • All homogeneous half-spaces • Closed exterior half-spaces |
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Optimal VC Dimension of Contrastive Learning with Margin
anchor--positive--negative'' triplets $(i,j^{+},k^{-})$, indicating that item is closer to than to .'' 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 -dimensional Euclidean representations of -point datasets, 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 , a triplet is satisfied by the embedding , if . In this work, we resolve their question by proving that the VC dimension of contrastive learning under any margin is in fact , improving on the previous bound of . We also establish that the bounds are optimal up to constant factors, by providing a matching lower bound of (the previously known lower bound was ), for .