Learning Smooth Distance Functions via Queries
This provides theoretical foundations for query-based distance learning, which could benefit applications like metric learning and similarity search, though it appears incremental in extending existing query frameworks.
The paper tackles the problem of learning smooth distance functions using triplet queries, establishing formal guarantees on query complexity for both additive and multiplicative approximations. For additive approximation, they propose a global method with quadratic query complexity in cover size, while for multiplicative approximation, they introduce a hybrid method with quadratic complexity in both cover size and ambient dimension.
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.