Nearly optimal classification for semimetrics
This work addresses the challenge of classification in semimetric spaces for machine learning researchers, providing a novel theoretical framework and algorithms that improve upon metric-based approaches.
The paper tackles the problem of classification in semimetric spaces, where distances lack the triangle inequality, by introducing the density dimension as a key factor for learning feasibility, and presents nearly optimal sample compression algorithms that achieve generalization guarantees with fast rates.
We initiate the rigorous study of classification in semimetric spaces, which are point sets with a distance function that is non-negative and symmetric, but need not satisfy the triangle inequality. For metric spaces, the doubling dimension essentially characterizes both the runtime and sample complexity of classification algorithms --- yet we show that this is not the case for semimetrics. Instead, we define the {\em density dimension} and discover that it plays a central role in the statistical and algorithmic feasibility of learning in semimetric spaces. We present nearly optimal sample compression algorithms and use these to obtain generalization guarantees, including fast rates. The latter hold for general sample compression schemes and may be of independent interest.