Abstract
Mixture of linear regressions is a popular learning theoretic model that isused widely to represent heterogeneous data. In the simplest form, this modelassumes that the labels are generated from either of two different linearmodels and mixed together. Recent works of Yin et al. and Krishnamurthy et al.,2019, focus on an experimental design setting of model recovery for thisproblem. It is assumed that the features can be designed and queried with toobtain their label. When queried, an oracle randomly selects one of the twodifferent sparse linear models and generates a label accordingly. How many suchoracle queries are needed to recover both of the models simultaneously? Thisquestion can also be thought of as a generalization of the well-knowncompressed sensing problem (Cand\`es and Tao, 2005, Donoho, 2006). In thiswork, we address this query complexity problem and provide efficient algorithmsthat improves on the previously best known results.