This lecture provides an excellent summary of the main ideas in the ICML paper:

http://www.icml2006.org/icml_document...

The paper points out some weaknesses and limitations of existing active learning methods, in particular, their inability to cope with arbitrary forms of noise. The proposed algorithm, called "Agnostic Active Learning" (or A-squared), makes no assumptions regarding the type of noise. The authors prove that an exponential reduction in the number of samples is indeed possible when the amount of noise is not too large. In the video, an example is presented of learning a threshold on the real line, which helps to illustrate the main concepts. Following the lecture, John fields a few questions, one of which is concerned with the tractability of A-squared when other hypothesis classes are considered; he concedes that there can be significant computational issues. From the paper: “Checking for disagreement amongst all remaining classifiers can be very computationally intensive.” Nevertheless, A-squared is an innovative idea that should be of interest to any student of active learning and/or learning theory.