  Metric based comparison operations such as finding maximum, nearest and
farthest neighbor are fundamental to studying various clustering techniques
such as $k$-center clustering and agglomerative hierarchical clustering. These
techniques crucially rely on accurate estimation of pairwise distance between
records. However, computing exact features of the records, and their pairwise
distances is often challenging, and sometimes not possible. We circumvent this
challenge by leveraging weak supervision in the form of a comparison oracle
that compares the relative distance between the queried points such as `Is
point u closer to v or w closer to x?'.
  However, it is possible that some queries are easier to answer than others
using a comparison oracle. We capture this by introducing two different noise
models called adversarial and probabilistic noise. In this paper, we study
various problems that include finding maximum, nearest/farthest neighbor search
under these noise models. Building upon the techniques we develop for these
comparison operations, we give robust algorithms for k-center clustering and
agglomerative hierarchical clustering. We prove that our algorithms achieve
good approximation guarantees with a high probability and analyze their query
complexity. We evaluate the effectiveness and efficiency of our techniques
empirically on various real-world datasets.
