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

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

    Jul 12, 2026Grigory Ivanov, Attila Jung, Márton NaszódiVC Dimension

  2. Optimal VC Dimension of Contrastive Learning with Margin

    Sep 30, 2026Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo +1Contrastive LearningGeometric Representation Learning

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

    Oct 29, 2026Ernesto Araya, Gitta Kutyniok, Weilin Li +2Intrinsic DimensionalityLoss Landscape Geometry