Sample Complexity of Learning Mixture of Sparse Linear Regressions
Authors: Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, Soumyabrata Pal
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we consider the case where the signal vectors are sparse; this generalizes the popular compressed sensing paradigm. We improve upon the state-of-the-art results as follows: In the noisy case, we resolve an open question of Yin et al. (IEEE Transactions on Information Theory, 2019) by showing how to handle collections of more than two vectors and present the first robust reconstruction algorithm, i.e., if the signals are not perfectly sparse, we still learn a good sparse approximation of the signals. In the noiseless case, as well as in the noisy case, we show how to circumvent the need for a restrictive assumption required in the previous work. Our techniques are quite different from those in the previous work: for the noiseless case, we rely on a property of sparse polynomials and for the noisy case, we provide new connections to learning Gaussian mixtures and use ideas from the theory of error correcting codes. |
| Researcher Affiliation | Collaboration | Akshay Krishnamurthy Microsoft Research, NYC akshay@cs.umass.edu Arya Mazumdar UMass Amherst arya@cs.umass.edu |
| Pseudocode | Yes | Algorithm 1 Noiseless Recovery The algorithm for extracting recovering vectors via queries to oracle in noiseless setting. ... Algorithm 2 Noisy Recovery for L = 2 The algorithm for recovering best k-sparse approximation of vectors via queries to oracle in noisy setting. ... Algorithm 3 Noisy Recovery for any constant L The algorithm for recovering best k-sparse approximation of vectors via queries to oracle in noisy setting. |
| Open Source Code | No | No mention or link to open-source code for the described methodology was found. |
| Open Datasets | No | The paper is theoretical, defining a problem setup with an 'oracle' and abstract vectors, rather than using concrete datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments requiring dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments that would require a list of specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments that would involve hyperparameter tuning or specific training configurations. |