Metric-valued regression
  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\'echet 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.
