Timezone: »

 
Poster
The Power of Comparisons for Actively Learning Linear Classifiers
Max Hopkins · Daniel Kane · Shachar Lovett

Mon Dec 07 09:00 PM -- 11:00 PM (PST) @ Poster Session 0 #73
in Poster Session 1 »

In the world of big data, large but costly to label datasets dominate many fields. Active learning, a semi-supervised alternative to the standard PAC-learning model, was introduced to explore whether adaptive labeling could learn concepts with exponentially fewer labeled samples. While previous results show that active learning performs no better than its supervised alternative for important concept classes such as linear separators, we show that by adding weak distributional assumptions and allowing comparison queries, active learning requires exponentially fewer samples. Further, we show that these results hold as well for a stronger model of learning called Reliable and Probably Useful (RPU) learning. In this model, our learner is not allowed to make mistakes, but may instead answer ``I don't know.'' While previous negative results showed this model to have intractably large sample complexity for label queries, we show that comparison queries make RPU-learning at worst logarithmically more expensive in both the passive and active regimes.

Author Information

Max Hopkins (University of California San Diego)
Daniel Kane (UCSD)
Shachar Lovett (University of California San Diego)

More from the Same Authors