Learning half-spaces on general infinite spaces equipped with a distance function

For a general infinite distance space chi, with no assumptions about the distance function, which need not satisfy the metric axioms, it is not clear what the VC-dimension of the class Hof half-spaces in chi may be and if there are generalization error bounds for learning H. We define a combinatorial dimension of chi to be the independence number of the class of balls in chi. We compute it for Euclidean space and for several non-metric distance spaces. Using this dimension, we are able to provide a generalization error bound for learning Hover any infinite distance space chi. (c) 2023 Elsevier Inc. All rights reserved.

Automated summary

This paper investigates the VC-dimension of the class of half-spaces in an infinite distance space chi, where no assumptions about the distance function are made and the metric axioms need not be satisfied. It is not clear what the VC-dimension of Hof half-spaces in chi may be and if there are generalization error bounds for learning H. The authors define a combinatorial dimension of chi as the independence number of the class of balls in chi and compute it for different types of distance spaces. They then use this dimension to provide a generalization error bound for learning H in any infinite distance space chi.