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

For a general infinite distance space X, 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 H of half-spaces in X may be and if there are generalization error bounds for learning H. We define a combinatorial dimension of X to be the independence number of the class of balls in X. 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 H over any infinite distance space X.