I have been looking for theoretical papers studying this question of the hardness of PAC active learning algorithms. I found a few papers studying the problem from a fixed perspective (particular hypothesis class thresholds and halfspaces) but not agnostic with respect to the hypothesis class and the realizable distribution. Can you suggest some papers or seminar talk that studies the problem from a general perspective?

  • $\begingroup$ I'd take a chance and tag @Lev Reyzin, hopefully getting a response $\endgroup$
    – rivana
    Nov 8 at 12:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.