1
$\begingroup$

I am a PhD student working on the theory of active learning.

Over the years, accepted papers in COLT and ALT for active learning are focused on approaches that almost all of them define new information complexity measures of the hypothesis class, which is a bit intriguing to me is the invention of many information complexities (combinatorial objects such as VC dimension was the first one invented) in active learning such as: Inference dimension (Shay Moran, Active Learning with comparison queries), Extended-Teaching dimension for pool-based active learning,Alexander capacity function, Star number and disagreement coefficient (Steve Hanneke),... etc Without connecting between them. I assume the goal of using such complexity measures is to find tight bounds for sample complexity (i.e, extended-teaching dimension gives that).

Are the type of queries that give this kind of intuition for coming up with information complexity measures? Given that all those information complexity measures are "very combinatorial" and hard to compute, is coming up with new measures help solving the problem?

Another question, since I started learning about statistical queries (Rev Leyzin recent work), it seems like the approach is different than the one used in classic work. Do theses approach guarantee fast convergence compared to other active learning approaches?

Improve this question
$\endgroup$
1
  • $\begingroup$ people study natural learning problems, and then find the complexity measure that characterizes it. For example, VC dimension is exactly what captures PAC learnability; there's no getting around that. I therefore wouldn't say the dimensions/complexities are invented but rather "discovered". $\endgroup$
    – mathworker21
    Nov 9 at 14:51

0

Reset to default

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.