Comparison-Based Learning with Rank Nets
  We consider the problem of search through comparisons, where a user is
presented with two candidate objects and reveals which is closer to her
intended target. We study adaptive strategies for finding the target, that
require knowledge of rank relationships but not actual distances between
objects. We propose a new strategy based on rank nets, and show that for target
distributions with a bounded doubling constant, it finds the target in a number
of comparisons close to the entropy of the target distribution and, hence, of
the optimum. We extend these results to the case of noisy oracles, and compare
this strategy to prior art over multiple datasets.
