Review for NeurIPS paper: Recovery of sparse linear classifiers from mixture of responses

Summary and Contributions: This work initiates the study of the following generalization of 1-bit compressed sensing. There are some unknown k-sparse vectors w_1,...,w_{ell} in R d, and one can query any vector v and get back sgn( v,w_i) for random index i. The goal is to recover the w_i's while minimizing the number of queries. This problem should not be confused with the problem of learning mixtures of halfspaces in the sense of distribution learning, as here the learner gets to pick the design vectors. A similar model in the context of regression has been studied before by Krishnamurthy et al. and Yin et al., as the authors acknowledge.