Research map / Learning theory and algorithms / Matrix and tensor methods
Recovery of sparse linear classifiers from mixture of responses
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| Use support-separability and union-free-family queries for support recovery | Sparse mixture of ℓ classifiers · Sparse mixture, support-separable | query complexity for support recovery: O(\ell^6 k^3 \log^2 n) | Helped |
| Recover supports first, then use modified Gaussian queries | Sparse mixture of ℓ classifiers · Sparse mixture, support-separable | query complexity for ε-recovery: O\Big(\ell^6 k^3 \log^2 n + (\ell^3 k/\epsilon)\log (nk/\epsilon) \log(k/\epsilon) \Big) | Helped |
| Make the full recovery procedure completely non-adaptive | Sparse mixture of ℓ classifiers · Sparse mixture, support-separable | query complexity for ε-recovery: O\Big((\ell^{\ell+3} k^{\ell+2}/\epsilon )\log n \log (n/\epsilon) \log(k/\epsilon) \Big) | Mixed |
| Use finite-precision, sub-Gaussian-query recovery for two classifiers without support separability | Two sparse classifiers · Two sparse classifiers, no support-separability condition | query complexity for ε-recovery: O(k^3 \log^2 n + (k^2/\epsilon^4 \delta^2) \log^2 (n/k \delta^2)) | Helped |
| Use two-stage recovery when the two classifiers have different supports | Two sparse classifiers · Two sparse classifiers with different supports | query complexity for ε-recovery: O(k^3 \log^2 n + (k/\epsilon) \log (nk/\epsilon) \log(k/\epsilon)) | Helped |
| Drop the sparsity constraint and treat both supports as all coordinates | Two classifiers · Two unrestricted classifiers | query complexity for ε-recovery: O( (n^2 /\epsilon^4 \delta^2)\log(1/\delta)) | Helped |
Closest papers by meaning
- Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements (ICML 2025 · similarity 0.89)
- On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.85)
- A Unified Framework for Learning with Nonlinear Model Classes from Arbitrary Linear Samples (ICML 2024 · similarity 0.85)
- Beyond Worst-Case Dimensionality Reduction for Sparse Vectors (ICLR 2025 · similarity 0.84)
- Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization (ICML 2024 · similarity 0.84)
- 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.