# Metric-valued regression

arXiv: https://arxiv.org/abs/2202.03045 · HTML: https://mlsanity.com/paper/2202.03045/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 34 references that are in the map.
- First posted on arXiv 7 Feb 2022.

## Builds on (most cited first, 11 of 11)

- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Universal Bayes consistency in metric spaces](https://mlsanity.com/paper/1906.09855/) (2019)
- [Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound](https://mlsanity.com/paper/2011.04586/) (2020)
- [Learning Whenever Learning is Possible: Universal Learning under General Stochastic Processes](https://mlsanity.com/paper/1706.01418/) (2017)
- [Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces](https://mlsanity.com/paper/2010.00636/) (2020)
- [Ultra Fast Medoid Identification via Correlated Sequential Halving](https://mlsanity.com/paper/1906.04356/) (2019)
- [Universal Online Learning with Bounded Loss: Reduction to Binary Classification](https://mlsanity.com/paper/2112.14638/) (2021)
- [Universal Online Learning with Unbounded Losses: Memory Is All You Need](https://mlsanity.com/paper/2201.08903/) (2022)
- [A Sub-Quadratic Exact Medoid Algorithm](https://mlsanity.com/paper/1605.06950/) (2016)
- [Functions with average smoothness: structure, algorithms, and learning](https://mlsanity.com/paper/2007.06283/) (2020)
- [A Bayes consistent 1-NN classifier](https://mlsanity.com/paper/1407.0208/) (2014)

## Built on by (most cited first, 3 of 3)

- [Uncertainty quantification in metric spaces](https://mlsanity.com/paper/2405.05110/) (2024)
- [Conditional Mean and Variance Estimation via textitk-NN Algorithm with Automated Variance Selection](https://mlsanity.com/paper/2402.01635/) (2024)
- [Conformal and kNN Predictive Uncertainty Quantification Algorithms in Metric Spaces](https://mlsanity.com/paper/2507.15741/) (2025)

## Abstract (arXiv)

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.