# Learning Smooth Distance Functions via Queries

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 48 references that are in the map.
- First posted on arXiv 2 Dec 2024.

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

- [Scalable and Efficient Comparison-based Search without Features](https://mlsanity.com/paper/1905.05049/) (2019)
- [Dimension Free Generalization Bounds for Non Linear Metric Learning](https://mlsanity.com/paper/2102.03802/) (2021)
- [Linear Distance Metric Learning with Noisy Labels](https://mlsanity.com/paper/2306.03173/) (2023)

## Abstract (arXiv)

In this work, we investigate the problem of learning distance functions within the query-based learning framework, where a learner is able to pose triplet queries of the form: ``Is xi closer to xj or xk?'' We establish formal guarantees on the query complexity required to learn smooth, but otherwise general, distance functions under two notions of approximation: ω-additive approximation and (1 + ω)-multiplicative approximation. For the additive approximation, we propose a global method whose query complexity is quadratic in the size of a finite cover of the sample space. For the (stronger) multiplicative approximation, we introduce a method that combines global and local approaches, utilizing multiple Mahalanobis distance functions to capture local geometry. This method has a query complexity that scales quadratically with both the size of the cover and the ambient space dimension of the sample space.