Research map / Learning theory and algorithms / Sample complexity
Sample Complexity of Learning Mixture of Sparse Linear Regressions
Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, Soumyabrata Pal
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Recover Gaussian-mixture means using the epsilon-grid constraint | Noisy Recovery · Noisy Gaussian, two vectors | sample complexity dependence on sigma/epsilon: \exp(\sigma/\epsilon) -> \exp( (\sigma/\epsilon)^{2/3} ) | Improved |
| Use redundant sum and difference queries for alignment | Noisy Recovery · Noisy Gaussian, two vectors | alignment correctness | Improved |
| Allow dense signals and recover their best k-sparse approximations | Noisy Recovery · Noisy Gaussian, L=O(1) | reconstruction guarantee | Improved |
| Remove the restrictive overlap assumption on signal supports | Noiseless Recovery and Noisy Recovery · Noiseless and noisy sparse regression mixtures | applicability to signal collections | Improved |
Closest papers by meaning
- Support Recovery of Sparse Signals from a Mixture of Linear Measurements (NeurIPS 2021 · similarity 0.89)
- Recovery of Sparse Signals from a Mixture of Linear Samples (ICML 2020 · similarity 0.89)
- On learning sparse vectors from mixture of responses (NeurIPS 2021 · similarity 0.88)
- Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements (ICML 2025 · similarity 0.87)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.86)
- The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
