skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Algorithms for Metric Learning via Contrastive Embeddings
We study the problem of supervised learning a metric space under discriminative constraints. Given a universe X and sets S, D subset binom{X}{2} of similar and dissimilar pairs, we seek to find a mapping f:X -> Y, into some target metric space M=(Y,rho), such that similar objects are mapped to points at distance at most u, and dissimilar objects are mapped to points at distance at least l. More generally, the goal is to find a mapping of maximum accuracy (that is, fraction of correctly classified pairs). We propose approximation algorithms for various versions of this problem, for the cases of Euclidean and tree metric spaces. For both of these target spaces, we obtain fully polynomial-time approximation schemes (FPTAS) for the case of perfect information. In the presence of imperfect information we present approximation algorithms that run in quasi-polynomial time (QPTAS). We also present an exact algorithm for learning line metric spaces with perfect information in polynomial time. Our algorithms use a combination of tools from metric embeddings and graph partitioning, that could be of independent interest.  more » « less
Award ID(s):
1815145
PAR ID:
10166832
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Leibniz international proceedings in informatics
Volume:
129
ISSN:
1868-8969
Page Range / eLocation ID:
45:1--45:14
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Mulzer, Wolfgang; Phillips, Jeff M (Ed.)
    Metric spaces (X, d) are ubiquitous objects in mathematics and computer science that allow for capturing pairwise distance relationships d(x, y) between points x, y ∈ X. Because of this, it is natural to ask what useful generalizations there are of metric spaces for capturing "k-wise distance relationships" d(x_1, …, x_k) among points x_1, …, x_k ∈ X for k > 2. To that end, Gähler (Math. Nachr., 1963) (and perhaps others even earlier) defined k-metric spaces, which generalize metric spaces, and most notably generalize the triangle inequality d(x₁, x₂) ≤ d(x₁, y) + d(y, x₂) to the "simplex inequality" d(x_1, …, x_k) ≤ ∑_{i=1}^k d(x_1, …, x_{i-1}, y, x_{i+1}, …, x_k). (The definition holds for any fixed k ≥ 2, and a 2-metric space is just a (standard) metric space.) In this work, we introduce strong k-metric spaces, k-metric spaces that satisfy a topological condition stronger than the simplex inequality, which makes them "behave nicely." We also introduce coboundary k-metrics, which generalize 𝓁_p metrics (and in fact all finite metric spaces induced by norms) and minimum bounding chain k-metrics, which generalize shortest path metrics (and capture all strong k-metrics). Using these definitions, we prove analogs of a number of fundamental results about embedding finite metric spaces including Fréchet embedding (isometric embedding into 𝓁_∞) and isometric embedding of all tree metrics into 𝓁₁. We also study relationships between families of (strong) k-metrics, and show that natural quantities, like simplex volume, are strong k-metrics. 
    more » « less
  2. ; ; ; (, Proceedings of the AAAI Conference on Artificial Intelligence)
    Motivated by applications to classification problems on metric data, we study Weighted Metric Clustering problem: given a metric d over n points and a k x k symmetric matrix A with non-negative entries, the goal is to find a k-partition of these points into clusters C1,...,Ck, while minimizing the sum of A[i,j] * d(u,v) over all pairs of clusters Ci and Cj and all pairs of points u from Ci and v from Cj. Specific choices of A lead to Weighted Metric Clustering capturing well-studied graph partitioning problems in metric spaces, such as Min-Uncut, Min-k-Sum, Min-k-Cut, and more.Our main result is that Weighted Metric Clustering admits a polynomial-time approximation scheme (PTAS). Our algorithm handles all the above problems using the Sherali-Adams linear programming relaxation. This subsumes several prior works, unifies many of the techniques for various metric clustering objectives, and yields a PTAS for several new problems, including metric clustering on manifolds and a new family of hierarchical clustering objectives. Our experiments on the hierarchical clustering objective show that it better captures the ground-truth structural information compared to the popular Dasgupta's objective. 
    more » « less
  3. ; ; (, Proc. 40th Sympos. Computational Geometry (SoCG))
    Mulzer, Wolfgang; Phillips, Jeff M (Ed.)
    Let X be a set of points in ℝ² and 𝒪 be a set of geometric objects in ℝ², where |X| + |𝒪| = n. We study the problem of computing a minimum subset 𝒪^* ⊆ 𝒪 that encloses all points in X. Here a point x ∈ X is enclosed by 𝒪^* if it lies in a bounded connected component of ℝ²∖(⋃_{O ∈ 𝒪^*} O). We propose two algorithmic frameworks to design polynomial-time approximation algorithms for the problem. The first framework is based on sparsification and min-cut, which results in O(1)-approximation algorithms for unit disks, unit squares, etc. The second framework is based on LP rounding, which results in an O(α(n)log n)-approximation algorithm for segments, where α(n) is the inverse Ackermann function, and an O(log n)-approximation algorithm for disks. 
    more » « less
  4. ; (, Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms)
    null (Ed.)
    The 2-Wasserstein distance (or RMS distance) is a useful measure of similarity between probability distributions with exciting applications in machine learning. For discrete distributions, the problem of computing this distance can be expressed in terms of finding a minimum-cost perfect matching on a complete bipartite graph given by two multisets of points A, B ⊂ ℝ2, with |A| = |B| = n, where the ground distance between any two points is the squared Euclidean distance between them. Although there is a near-linear time relative ∊-approximation algorithm for the case where the ground distance is Euclidean (Sharathkumar and Agarwal, JACM 2020), all existing relative ∊-approximation algorithms for the RMS distance take Ω(n3/2) time. This is primarily because, unlike Euclidean distance, squared Euclidean distance is not a metric. In this paper, for the RMS distance, we present a new ∊-approximation algorithm that runs in O(n^5/4 poly{log n, 1/∊}) time. Our algorithm is inspired by a recent approach for finding a minimum-cost perfect matching in bipartite planar graphs (Asathulla et al, TALG 2020). Their algorithm depends heavily on the existence of sublinear sized vertex separators as well as shortest path data structures that require planarity. Surprisingly, we are able to design a similar algorithm for a complete geometric graph that is far from planar and does not have any vertex separators. Central components of our algorithm include a quadtree-based distance that approximates the squared Euclidean distance and a data structure that supports both Hungarian search and augmentation in sublinear time. 
    more » « less
  5. ; (, Analysis and Applications)
    In this paper, we present a sharper version of the results in the paper Dimension independent bounds for general shallow networks; Neural Networks, \textbf{123} (2020), 142-152. Let $$\mathbb{X}$$ and $$\mathbb{Y}$$ be compact metric spaces. We consider approximation of functions of the form $$ x\mapsto\int_{\mathbb{Y}} G( x, y)d\tau( y)$$, $$ x\in\mathbb{X}$$, by $$G$$-networks of the form $$ x\mapsto \sum_{k=1}^n a_kG( x, y_k)$$, $$ y_1,\cdots, y_n\in\mathbb{Y}$$, $$a_1,\cdots, a_n\in\mathbb{R}$$. Defining the dimensions of $$\mathbb{X}$$ and $$\mathbb{Y}$$ in terms of covering numbers, we obtain dimension independent bounds on the degree of approximation in terms of $$n$$, where also the constants involved are all dependent at most polynomially on the dimensions. Applications include approximation by power rectified linear unit networks, zonal function networks, certain radial basis function networks as well as the important problem of function extension to higher dimensional spaces. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email