Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Sample Complexity of Learning Mixture of Sparse Linear Regressions
Authors: Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, Soumyabrata Pal
NeurIPS 2019 | Venue PDF | 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 ο¬rst 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 EMAIL Arya Mazumdar UMass Amherst EMAIL |
| 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. |