@inproceedings{zhang2018efficient,
author = {Zhang, Chicheng},
title = {Efficient active learning of sparse halfspaces},
booktitle = {Proceedings of Machine Learning Research},
year = {2018},
month = {July},
abstract = {We study the problem of efficient PAC active learning of homogeneous linear classifiers (halfspaces) in R^d , where the goal is to learn a halfspace with low error, using as few label queries as possible. Given the extra assumption that there is a t-sparse halfspace that performs well on the data (t ≪ d), we would like our active learning algorithm to be attribute efficient, i.e. to have label requirements sublinear in d. In this paper, we provide a computationally efficient algorithm that achieves this goal. Under certain distributional assumptions on the data, our algorithm achieves a label complexity of O(t polylog(d, 1/eps)). In contrast, existing algorithms in this setting are either computationally inefficient, or subject to label requirements polynomial in d or 1/eps.},
url = {http://approjects.co.za/?big=en-us/research/publication/efficient-active-learning-of-sparse-halfspaces/},
volume = {75},
edition = {Conference on Learning Theory},
}