Timezone: »

 
Poster
Active Learning Polynomial Threshold Functions
Omri Ben-Eliezer · Max Hopkins · Chutong Yang · Hantao Yu

Wed Nov 30 02:00 PM -- 04:00 PM (PST) @ Hall J #728
We initiate the study of active learning polynomial threshold functions (PTFs). While traditional lower bounds imply that even univariate quadratics cannot be non-trivially actively learned, we show that allowing the learner basic access to the derivatives of the underlying classifier circumvents this issue and leads to a computationally efficient algorithm for active learning degree-$d$ univariate PTFs in $\tilde{O}(d^3\log(1/\varepsilon\delta))$ queries. We extend this result to the batch active setting, providing a smooth transition between query complexity and rounds of adaptivity, and also provide near-optimal algorithms for active learning PTFs in several average case settings. Finally, we prove that access to derivatives is insufficient for active learning multivariate PTFs, even those of just two variables.

Author Information

Omri Ben-Eliezer (Massachusetts Institute of Technology)
Max Hopkins (University of California San Diego)
Chutong Yang (Stanford University)
Hantao Yu (Columbia University)

Computer Science Ph.D student at Columbia University. Studying complexity, algorithms and learning theory.

More from the Same Authors