Learning Smooth Distance Functions via Queries

2024/12/02 by Akash Kumar, Kumar, Akash, Sanjoy Dasgupta +1
Computer Science · #Machine Learning and Algorithms #Data Management and Algorithms #Algorithms and Data Compression

paper · pdf · doi:10.48550/arxiv.2412.01290

Abstract

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 x_i closer to x_j or x_k?'' 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.

Related

• Smooth Distance Approximation
• Approximate Nearest Neighbor Searching with Non-Euclidean and Weighted Distances
• Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
• Distance-based Learning of Hypertrees
• Metric Spaces with Expensive Distances