  Similarity functions measure how comparable pairs of elements are, and play a
key role in a wide variety of applications, e.g., notions of Individual
Fairness abiding by the seminal paradigm of Dwork et al., as well as Clustering
problems. However, access to an accurate similarity function should not always
be considered guaranteed, and this point was even raised by Dwork et al. For
instance, it is reasonable to assume that when the elements to be compared are
produced by different distributions, or in other words belong to different
``demographic'' groups, knowledge of their true similarity might be very
difficult to obtain. In this work, we present an efficient sampling framework
that learns these across-groups similarity functions, using only a limited
amount of experts' feedback. We show analytical results with rigorous
theoretical bounds, and empirically validate our algorithms via a large suite
of experiments.
