# Recovery of sparse linear classifiers from mixture of responses

arXiv: https://arxiv.org/abs/2010.12087 · HTML: https://mlsanity.com/paper/2010.12087/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2020.

## Built on by (most cited first, 6 of 6)

- [Support Recovery of Sparse Signals from a Mixture of Linear Measurements](https://mlsanity.com/paper/2106.05951/) (2021)
- [SQ Lower Bounds for Learning Mixtures of Linear Classifiers](https://mlsanity.com/paper/2310.11876/) (2023)
- [Support Recovery in Mixture Models with Sparse Parameters](https://mlsanity.com/paper/2202.11940/) (2022)
- [Learning and Generalization with Mixture Data](https://mlsanity.com/paper/2504.20651/) (2025)
- [Personalized Prediction By Learning Halfspace Reference Classes Under Well-Behaved Distribution](https://mlsanity.com/paper/2509.15592/) (2025)
- [Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Fewer Measurements](https://mlsanity.com/paper/2609.32176/) (2026)

## Abstract (arXiv)

In the problem of learning a mixture of linear classifiers, the aim is to learn a collection of hyperplanes from a sequence of binary responses. Each response is a result of querying with a vector and indicates the side of a randomly chosen hyperplane from the collection the query vector belongs to. This model provides a rich representation of heterogeneous data with categorical labels and has only been studied in some special settings. We look at a hitherto unstudied problem of query complexity upper bound of recovering all the hyperplanes, especially for the case when the hyperplanes are sparse. This setting is a natural generalization of the extreme quantization problem known as 1-bit compressed sensing. Suppose we have a set of ℓ unknown k-sparse vectors. We can query the set with another vector boldsymbola, to obtain the sign of the inner product of boldsymbola and a randomly chosen vector from the ℓ-set. How many queries are sufficient to identify all the ℓ unknown vectors? This question is significantly more challenging than both the basic 1-bit compressed sensing problem (i.e., ℓ=1 case) and the analogous regression problem (where the value instead of the sign is provided). We provide rigorous query complexity results (with efficient algorithms) for this problem.