Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers support recovery of multiple sparse vectors with the same sparsity level from a mixture of linear measurements in the tensor setting with CP decomposition. Specifically, several algorithms for various types of support matrix, including p-identifiable, flip-independent and r-Kruskal rank support matrices, are proposed to solve the problem, together with computational cost analysis in terms of mixture of sparse linear classifiers (MLC) and mixture of sparse linear regressions (MLR). 
main_review: The work that uses the tensor framework to recover multiple sparse signals with the same sparsity level from a mixture of linear measurements is interesting. In particular, support recovery is embedded into the MLC and MLR models. However, the motivations and contributions of the proposed algorithms, especially the use of low CP-rank assumption, are not fully clear, which could be highlighted. The title could be more specific about the tensor setting. Although theoretical success guarantees of the proposed algorithms are provided, numerical justifications are completely missing. The paper seems incomplete to some point. 
limitations_and_societal_impact: The assumptions about the feasibility of the proposed algorithms should be justified in practice. Numerical implementation details and performance comparisons with the state of the arts should be provided to make this work more attractive.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers the support recovery of sparse vectors from linear mixtures. They extend the results from prior works by relaxing some assumptions and provide support recovery using a low-rank tensor decomposition.
main_review: The paper is well-organized and written well. Related works is properly discussed and the authors explained well how their work differs from prior works. The paper studies the support recovery of sparse vectors from linear mixtures. As also pointed out by the authors, prior works have studied the approximate recovery of the sparse signals in a similar problem. This work mainly extends [29], relaxes some assumptions, and focuses on support recovery. Hence, the paper is incremental and lack originality. Sufficient discussion and remarks are provided on the derived theorems.

In addition, although the paper includes theoretical results on the problem discussed, it ends with no conclusion section and lacks numerical results supporting their theorem. In the absence of conclusion and no numerical experiments to verify their theorem, the papers does not meet the standards for NeurIPS publication.

Below are my further comments:

- Although mentioned in the related works section, please explain which techniques used in this paper differ from those in [27, 29, 44]. This can help the authors to show the originality of the work in their method and techniques.

- It is known that compressed sensing has many real-world application in radar, MRI, etc. What are the applications of the sparse linear mixture model? An experiment section with baseline comparison is needed to show the performance of the proposed algorithms.

- Include numerical analysis. For example, phase transition curve on support recovery as the number of measurements and sparsity level changes.

limitations_and_societal_impact: - No negative impact is discussed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers a support-recovery problem for a mixture of sparse linear classifier and regressions with $l \ge 2$ number of components in the active-learning setting, i.e., where we can design input-vectors (or queries, as few as possible). For sparse linear classifiers, unlike in previous work [19] where supports of any two unknown vectors are disjoint, the authors consider a few milder assumptions on the support (Definition 1 and 2). For sparse linear regressions, they do not impose target vectors to be on some scaled integer lattice [27, 44] (but instead we need minimum magnitude $\delta > 0$ for any non-zero entry, and some high SNR condition). 

In order to recover all supports, three assumptions are considered for the support-matrix: (1) p-identifiable, if some size $p$ subset of support locations uniquely decides an unknown vector, then the authors can devise some combinatorial approach extending [19], (2) flip-independent, which essentially is required for some 3rd-order (support) tensor uniquely decomposable, (3) more general case where we deal with higher-order (support) tensor decomposition which cannot be done in polynomial-time in general but for full-rank 3rd order tensors. 

The heart of the proposed algorithms for all three cases is to compute $|occ(C,a) := \{v \in \mathcal{V} | \ supp(v)|_C = a \}|$ for all possible combination of $C$ and $a$ of a fixed length $s \ge 1$ (Lemma 2). It seems quite non-trivial to compute all these $\Omega(n^s)$ quantities using only $O(log n)$-queries. Equipped with this powerful lemma, subsequent procedures seem to be nice combinatorial arguments adjusted to different assumptions. Overall algorithms and proofs are quite non-trivial. 
main_review: The paper is well-written: problem statement is clear, comparison to previous work is well described, background knowledge is kindly introduced whenever necessary, and the main results are easy to catch. Here, I have to admit that I am not very familiar with union-free family or cover-free family literature, hence I cannot fully appreciate Lemma 2 which seems to be the core of all proposed algorithms. I instead raise some concerns from different aspects:

- Why do you consider only to recover the supports (in [29], it was possible to recover all regression vectors although with some assumptions). Are there any fundamental challenges?

- Related to the previous one, for MLR, I wonder if a naive idea can work: lets say we just use Gaussian input design $x \sim \mathcal{N}(0,I)$. Then for each coordinate $i \in [n]$, just estimate $\mathbb{E} [y^2 x_i^2]$ where $y$ is a response for the query $x$. This expectation gives (constant + $\frac{1}{l} \sum_{j=1}^l |v_{j}^i|^2$), and all coordinates $i \in [n]$ can be estimated with $O(poly(k,l) log n)$ samples. What would be the drawback of this approach, and what is the merit of your algorithm?

- Again for MLR, an interesting aspect of [29] was that the query complexity was linear in sparsity $k$. With passive Gaussian design, a statistical-query lower bound $\Omega(k^2)$ is known (even for $l = 2$) (e.g., Brennan & Bresler 2020), and getting a $O(k^2)$ upper-bound is relatively easy for $l = 2$ case. So if much higher order in $k$ is allowed, why shouldn't we just work with passive Gaussian input design?

- Flip-independent - this assumption seems very tricky. How natural is this assumption (e.g., would there be more easy-to-understand assumption that can be implied by this?) 




On Complexity Results

- For MLR, a recent result by (Diakonikolas & Kane 2021) gives a quasi-polynomial time complexity result. Could you compare your result to them?

- Is there any fundamental limits (e.g., exponential lower bound) for the general case (Kruskal-rank, without full-rank 3rd-order tensor)?



Some other comments

- It would have been much helpful if more space has been allocated to explain (in high-level) how to compute $|occ(C,a)|$. Has this or some similar idea been appeared before somewhere? If so, reference to such literature would be nice.

- Line 263: "we have better results" - Are the results for Algorithm 1 and 2 comparable? In other words, is flip-independence a special case of p-identifiability?

- Line 595: "Moreover, SNR = ..." - what does this mean?



References 

- M. Brennan and G. Bresler, Reducibility and statistical-computational gaps from secret leakage, 2020.

- I. Diakonikolas and D.M. Kane, Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models, 2020.









==============================================

Post-Rebuttal: Thanks to the authors for a thoughtful response. It seems more clear to me now what the motivation is - more unified approach for mixture of linear models (MLC, MLR).

At this point, I still wonder how significant the results are for MLR, but for MLC it seems interesting. If there were more known results for solving MLC with passive input design, it would have been easier to appreciate this work further.

Currently, the focus of the paper is mostly on discussing conditions. But I am not sure whether they are interesting conditions on their own - maybe why other reviewers felt that some experiments seem necessary. Nevertheless, I think there are some good ideas and results in Lemma 2 + several other places in supplementary materials. I increased my score accordingly. 
limitations_and_societal_impact: Overall narrative of the paper is "we just solved a problem under this and that assumptions", but it would be nicer to see what can be said of learning mixture models which have been extensively studied, e.g., what main results can imply for them, why active-learning setting should be of interest, and so on. Also, I would like to hear what can be possible next steps.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work studies support recovery of a collection of multiple, unknown sparse vectors using a small number of noisy linear or 1-bit observations where the observations are constructed from random mixtures of the unknown sparse vectors. In other words, for each measurement, one of the multiple, unknown sparse vectors is chosen uniformly at random to generate the response and we aim to learn the support of all of these unknown vectors from the mixed measurements using the least amount of measurements as possible. In particular, the work considers sample complexity of recovery in both models and provides efficient algorithms to perform the recovery. Previous work in the area considered either approximate recovery under restrictive assumptions or support recovery only for the case where there are \ell = 2 unknown sparse vectors (of course, the \ell = 1 case has been studied extensively). This work considers support recovery for \ell >= 2 unknown sparse vectors.
main_review: I believe that the problem studied in this work is nicely formulated and introduced that is of relevance to the NeurIPs community. I also believe the work to be theoretically precise, but at some times the writing seems to be a bit terse, obviously due in some part to tight page limits. I think the authors could do a bit of a better job with the organization and presentation of the assumptions, algorithms, and main results. For example, while I recognize that the authors want to give some intuition to the assumptions in Section 2.2, it's somehow odd to read high level overviews of the algorithms there when the algorithms aren't formally described until much later in the paper. My main concern is about the significance of the research: while the work generalizes the assumptions made in previous works studying the problem like [19] or [29], it's not clear to me that this line of work has found many applications nor is it clear that the generalizations presented here will help it find new applications. Perhaps the authors could discuss a bit about how their conceptual tools or novel proof techniques could aide future research in related problems.

Some typos:
-- I found equation (1) confusing. What does it mean to minimize over \ell, when \ell is the total number of unknown v vectors? Perhaps minimizing over j \in [\ell] would be more clear.
-- Line 88: "Here we provide results for support recovery... that DO not have..."
-- Line 122: "Such that the indices of v corresponding ... ARE flipped"
-- Line 130: should it be \mathcal{A}_{i1,..., iw} = \Prod_{j=1}^w z_{ij + 1} or are vectors in R^n also indexed from 0 to n-1?
limitations_and_societal_impact: yes.
review_title: null

Meta-review: This paper proposes new algorithms for support recovery for mixtures of sparse linear regressions/classifiers. Recovery guarantees are obtained, which improve/generalize several previous results. However, the reviewers feel that the contributions are somewhat incremental given the existing work in [19,27,29,44]. The authors could also have done a better job motivating the problem setting and assumptions. It is currently clear if this results are of significance interest to the NeurIPS community, especially as the paper has focused on theory without numerical experiments for their new algorithms.
Decision: Accept (Poster)