Adaptive Sampling for Ranking and Clustering

In this talk I will discuss two learning problems: “Learning to Rank from Pairwise Preferences” and “Clustering from Pairwise Similarity Information”. For both problems, traditional (passive) learning bounds are suboptimal. In addition, general purpose active learning algorithms based on the disagreement coefficient are also suboptimal. I will present a method for obtaining near optimal query complexity bounds for the two. The method, called “Smooth Relative Regret Approximation” is an iterative algorithm relying on the ability, given a current hypothesis H, to build an empirical process approximating the difference between the loss of any hypothesis H’ and H, to within an error gracefully degrading as a function of the disagreement distance between H and H’. Based on joint work with Ron Begleiter and Esther Ezra.