Metric-valued regression
This provides a foundational solution for metric-valued regression, addressing a gap in machine learning theory for handling complex, unbounded data structures.
The paper tackles the problem of learning mappings between metric spaces with unbounded loss in the agnostic setting, achieving the first Bayes-consistent algorithm under general conditions like topological separability and boundedness in expectation.
We propose an efficient algorithm for learning mappings between two metric spaces, $\X$ and $\Y$. Our procedure is strongly Bayes-consistent whenever $\X$ and $\Y$ are topologically separable and $\Y$ is "bounded in expectation" (our term; the separability assumption can be somewhat weakened). At this level of generality, ours is the first such learnability result for unbounded loss in the agnostic setting. Our technique is based on metric medoids (a variant of Fréchet means) and presents a significant departure from existing methods, which, as we demonstrate, fail to achieve Bayes-consistency on general instance- and label-space metrics. Our proofs introduce the technique of {\em semi-stable compression}, which may be of independent interest.