## Active Learning Polynomial Threshold Functions

### Omri Ben-Eliezer · Max Hopkins · Chutong Yang · Hantao Yu

##### Hall J #728

Keywords: [ Active Learning ] [ Statistical Learning Theory ] [ Polynomial Threshold Functions ] [ Enriched Queries ]

[ Abstract ]
[ [ [
Wed 30 Nov 2 p.m. PST — 4 p.m. PST

Abstract: 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.

Chat is not available.