Reviews: Noise-Tolerant Interactive Learning Using Pairwise Comparisons

The labelling oracle will provide a noisy answer (with either adversarial noise or Tsybakov) In addition to the labeling oracle, there is a comparison oracle. The leaner then can ask which of two instances is more likely to be positive. This oracle's answers is also noisy. The authors provide results which show that if the learner uses comparison queries, then it can reduce the label-query complexity. The problem that the authors study seem to be a valid and interesting one.