We consider the statistical learning setting of active learning in which the learner chooses which examples to obtain labels for. We identify a useful general purpose structural property of such learning problems, giving rise to a query-efficient iterative procedure achieving approximately optimal loss at an exponentially fast rate, where the rate is measured in units of error per label. The effectiveness of our ideas is demonstrated on the problem of learning to rank from pairwise preference labels, known as minimum feedback arc-set in tournaments when all the quadratically many preferences are given as input. The net result is an efficient selective sampling method for this problem, achieving a (1 + e)competitive result using only O(n poly(logn, e−1)) preference queries from the quadratically many. This result is information theoretical in nature because it shows how to efficiently select information, not how to use it (computationally) for optimization. Nevertheless, our ideas transfer quite seamlessly to a convex relaxation counterpart, giving rise to an iterative algorithm with an exponential convergence rate to a relaxation optimum. SVM and logistic regression are, in particular, notable examples of relaxation for which this result applies. Such relaxations are popular in applications where the set of alternatives we wish to rank is embedded in a real vector space (feature space), and we wish to fit a permutation induced by a linear function to the preference information. Moreover, in the particular case of constant dimensional feature space, we obtain a slight additional improvement in the query complexity as a function of the number of alternatives using the powerful notion of e-relative approximations in bounded VC dimension spaces. We believe that our iterative scheme and analysis method are interesting in their own right and will find use in other problems. ∗Technion nailon@cs.technion.ac.il †Technion ronbeg@cs.technion.ac.il ‡NYU Courant Institute esther@cims.nyu.edu