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.