  Motivated by an application of eliciting users' preferences, we investigate
the problem of learning hemimetrics, i.e., pairwise distances among a set of
$n$ items that satisfy triangle inequalities and non-negativity constraints. In
our application, the (asymmetric) distances quantify private costs a user
incurs when substituting one item by another. We aim to learn these distances
(costs) by asking the users whether they are willing to switch from one item to
another for a given incentive offer. Without exploiting structural constraints
of the hemimetric polytope, learning the distances between each pair of items
requires $\Theta(n^2)$ queries. We propose an active learning algorithm that
substantially reduces this sample complexity by exploiting the structural
constraints on the version space of hemimetrics. Our proposed algorithm
achieves provably-optimal sample complexity for various instances of the task.
For example, when the items are embedded into $K$ tight clusters, the sample
complexity of our algorithm reduces to $O(n K)$. Extensive experiments on a
restaurant recommendation data set support the conclusions of our theoretical
analysis.
