Review for NeurIPS paper: Efficient active learning of sparse halfspaces with arbitrary bounded noise

Summary and Contributions: This paper studies the problem of learning sparse halfspaces given access to a noisy point-label pair oracle. In particular, given underlying true halfspace h *, the goal is to recover an \epsilon accurate sparse representation h' of h * using minimum number of noisy-oracle queries. The paper makes the following standard assumptions (i) the underlying distribution over the points is log-concave isotropic (ii) The label noise model is Massart noise. Under these assumptions, the paper gives an efficient algorithm which \epsilon learns halfspaces using O(s/(1 - 2\eta) 4 \poly-log(d,\epsilon)) samples, making it the first linear in s-sample complexity algorithm in this setting. This is also known to be almost information theoretically optimal with the upper and lower bounds differing only by a factor of O(1/(1 - 2\eta) 2).