Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper considers the problem of recovering a mixture of unknown sparse vectors from noisy and noiseless sign responses. A response is the sign of the inner product between a randomly sampled unknown sparse vector from the mixture and a query vector (designed or random), up to some noise. The main contribution of the paper is to show existence of an algorithm that can recovery the support of the unknown vectors in the presence of noise. In the noiseless case and under mild assumptions on the uniqueness of the support set of the unknown sparse vectors and a bound on the size of the non-zero entries in these unknown vectors, the authors show existence of an algorithm that can estimate the sparse vector up to an arbitrary precision. The precision of the estimation depends inversely on the number of queries.  
main_review: The paper shows that the support of the unknown vectors can be recovered with high probability if there are $O(kl^3 \max(2el,2ek)^{\min(l,k)}\log^2n)$ queries, where $k$ is the sparsity of unknown vectors, $l$ is the number of unknown vectors, and $e$ is the Euler's number. Is this sample complexity optimal in $k$ and $l$? A discussion on this would be useful.

Looking at section 5.2 and Theorem 2, the queries that correspond to the result in Theorem 2 are random gaussian. It would be useful to include this in Theorem 2.

Some parts of the paper are well-written, and some are hard to follow. For example, the authors state that the their "main contribution lies in a new support recovery algorithm" (line 48) however to my understanding the paper primarily focuses on proving existence of an algorithm. Robust-resolvable matrices is used in line 58 without a reference to its definition provided in the paper later. Also, the paper will benefit from a notation section. The norm in problem 1 is unclear.

The paper does not provide a significant comparison to prior and related works. 


limitations_and_societal_impact: The limitations of the paper is mentioned in the concluding section and in the last paragraph of section 1.1.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper considers learning a family of \ell unknown k-sparse n-dimensional vectors from mixture of 1-bit repsonses.  In particular, the authors propose a novel robust support recovery algorithm that works without any additional assumption. For robust support recovery, they try to reduce the problem to a problem of quantitative group testing, and they make use of a notion that generalizes cover-free families, which are previously used in the context of various 1-bit compressed sensing problems in [1,12,13]. Based on the reconstructed support of all unknown vectors in the family, the authors provide noiseless approximate vector recovery guarantees under the assumptions that the support of any unknown vector is not fully contained in the support of any other unknown vector from the family and the magnitude of each entry can be bounded from below and above. 
main_review: While some of the results seem potentially valuable (e.g., a non-trivial extension to [12] for robust support recovery), I feel that the techniques used in this paper are somewhat standard (such as cover-free families), and the derived sample complexity for both support and vector recovery are likely  far from optimal (this is particularly true for the case of vector recovery). The following are some specific comments:

What is the purpose of presenting Theorem 3? The settings of Theorem 3 are the same as those of Theorem 2, but the sample complexity of Theorem 3 seems to be always worse than the sample complexity of Theorem 2. 

The term max(2e\ell, 2ek)^{min(\ell,k)} in the sample complexity is quite bad when both k and \ell are large. To compare with the results in [12], the authors discuss the case that \tau = 0, fixed k and large \ell. When k < 4, the sample complexity in this paper is better than that in [12]. However, I think the case that \tau = 0, fixed \ell and large k is more practically interesting to compare. For this case, only when \ell = 2, the sample complexity in this paper is not worse than the sample complexity in [12]. However, for \ell = 2, the authors of [12] have mentioned that they do not need the restrictive separability assumption either. Therefore, my impression is that for support recovery, although this paper does not need the restrictive separability assumption, it, in general, requires a larger sample complexity compared to [12]. 

For standard 1-bit compressed sensing, support and vector recovery can be two separate problems and the sample complexity of vector recovery (depends linearly on k) is usually smaller than for that of support recovery (e.g., depends at least quadratically on k as in [13]). However, in this paper, the results for vector recovery are based on support recovery and thus the sample complexity for vector recovery cannot be smaller than that for support recovery, which is undesirable considering the results for standard 1-bit compressed sensing with \ell = 1. In addition, for the sample complexities of mixtures of sparse linear regressions provided in [18,20], the dependence on k is usually linear and is much better than that in Theorem 2 of this paper. Therefore, I think the most valuable part of this paper is only Theorem 1. Providing vector recovery guarantees based on support recovery guarantees (see Theorem 2) seems to be a bad strategy. Perhaps beyond the scope of this work, but I hope the authors can provide vector recovery guarantees with much smaller sample complexity requirements. 

A minor issue: Line 103, in the definition of the Hamming ball, d_H is used without definition. 

limitations_and_societal_impact: Yes. As mentioned in the Checklist, the limitations have been addressed and there is no potential negative societal impact of this work.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper studies the problem of learning a family of $l$ unknown $k$-sparse vectors. For any query point, we are given the sign of the inner product between a vector from the family (chosen uniformly at random) and the query point. In this setting they consider two problems. In the first problem, they propose a procedure along with guarantees (see Theorem 1) for estimating the supports of each vector in the family where the query responses can be noisy (the signs can be flipped). For the second problem, they consider estimating each vector in the family albeit in a noiseless setting. For this problem, they propose a two-stage algorithm for approximately recovering the vectors in the family, with performance guarantees (in Theorem 2). The performance guarantee for a single-stage algorithm has also been provided in Theorem 3. 
main_review: The problem considered can be viewed as a generalization of 1-bit CS. One issue that I have is the main motivation for studying this generalization. While it is interesting from a theoretical standpoint, I am not entirely sure whether there are concrete existing practical applications where this setup can be applied currently. Regarding the results, an important point is that the algorithms are not polynomial time; in fact, the running time appears to be exponential in the number of queries which is not satisfactory. The presentation of the results is clear for the first half of the paper, and in general the main ideas underlying the proofs are not difficult to follow. However, there are important aspects in this regard that need polishing. For e.g., none of the algorithms are outlined explicitly anywhere which is strange and inconvenient for the reader. Moreover, the single stage recovery algorithm (for Theorem 3) is never described, nor is a proof sketch provided for this result in the main text. Some additional remarks related to typos/clarifications are detailed below. At present, I am not convinced that the results in this paper are strong enough for acceptance.

1.	Line 104: $d_H$ should be defined. In lines 113-114: it should be $\tau \in [0,1]$? Also in  “..reconstruct the length.. “ its not clear what you mean by length, it should just be magnitude? In fact, even if we fix the scale to say unit norm, we still cannot recover the vector exactly so this could be mentioned for clarity. In Problem 1, the norm needs to be clarified.

2.	Typos in Theorems 2,3 : “..to recovery..” --> “..to recover…”. The algorithms corresponding to all theorems should be outlined explicitly in the main text. There should be a proof sketch for Theorem 3 as well in the main text. Its also not clear to me what the benefit of Theorem 3 is (other than being single-stage) since the sample complexity seems to be strictly worse than the two stage method in Theorem 2?

3.	Line 167: it should be “Proof of Lemma 1” to avoid confusion. In Lemma 2: it should be clarified somewhere for completeness how the reconstruction of $\tilde{z}$ will be done, and also the running time of this step. In general, the running times are not discussed properly anywhere (for the proposed algorithms and corresponding sub-routines) in the main text and it will be helpful to do so.

4.	In line 195: $m(n,l,k,\alpha)$ is introduced, but it is referred to as $m$ from thereon.

5.	The construction of robust resolvable matrices (def. 1) is the key to the algorithm for support recovery, and it is shown that they are related to robust cover free matrices (Def. 2). But how do we construct such matrices? Lemmas 6, 7 are only existential results. In line 250, it says that $H_{\mathcal{B}}$ can be uniquely reconstructed, but how? Also, the notation $[I]$ in definition 2 is unclear.

6.	My comments in Section 5 are mostly notational. In Lemma 8, the vectors are considered to be in $\mathbb{R}^k$ and not $\mathbb{R}^n$ as before. In Lemma 9, it should be: “…it holds that for any given $i \in [l]$,..”. In line 273: are the Gaussian vectors in $\mathbb{R}^{kl}$ or $\mathbb{R}^k$? In fact, once you recover the supports of the vectors, shouldn’t the subsequent queries comprise of vectors with support restricted to the union of individual supports of the vectors? Then I am not sure why $n$ should appear for the second stage analysis since the dimensionality reduction has already been done in the first stage. Finally, in line 276: it’s technically not a set since the values therein are not distinct.

------------------------ Post author response ---------------

I thank the authors for their response to some of my concerns. However, I am not convinced about the motivation for studying this particular problem and the significance of the results in the paper. I also feel that a lot of work is needed towards polishing the presentation of the paper. Therefore, I will stick with my original score of 4.
limitations_and_societal_impact: The limitations could be addressed more clearly in my opinion, especially with regards to the computational complexity of the algorithms.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary:  The paper addresses a generalized problem in 1-bit compressed sensing, e.g. considered in the NeurIPS 2020 paper [12]. The problem is to estimate ALL of l unknown k-sparse vectors from 1-bit noisy measurements based on q query vectors (See (1)) in terms of support recovery (Problem 2) and approximate recovery (Problem 1). 

 The goal of this paper is information-theoretic derivation of sufficient conditions on q, for which there are some algorithm and query vectors such that the support of all sparse vectors can be recovered with high probability (Theorem 1) or such that all sparse vectors can be recovered with negligibly small precision (Theorems 2 and 3). Theorem 1 is proven under some mild assumptions while [12] postulated an assumption (See [Assumption 1, 12]). On the other hand, Theorems 2 and 3 are proven under Assumption 1 in the submitted paper, which is weaker than [Assumption 1, 12].

main_review: Originality

The problem formulation and two-stage approach (1st stage: support recovery and 2nd stage: approximate recovery) are the same as in [12]. Theorems 2 and 3 are based on Theorem 1 and an existing Gaussian query result [16] (Lemma 8). Thus, the main contribution of the submitted paper is Theorem 1. 

The proof strategy of Theorem 1 is totally different from in [12], which provided a construct proof under [Assumption 1, 12] by proposing a support recovery algorithm and evaluating its performance theoretically. The proof strategy in the submitted paper is a random coding argument in information theory.

The outline of the proof is as follows: The information on the supports of l sparse vectors is mapped into a hypergraph (See Sec. 4.2). A sequence of the piercing numbers in Sec. 4 is used to distinguish different hypergraphs from each other. On the basis of these mathematical tools, a robust-resolvable binary matrix X is defined in Definition 1 to prove Theorem 1. The challenge in the proof is to prove the existence of a robust-resolvable binary matrix X.

Instead of proving the existence of a robust-resolvable binary matrix directly, the paper first construct s a robust-cover-free binary matrix X in Definition 2, which indicates the robust-resolvability of X under some conditions (Lemma 5). An information-theoretic construction of a robust-cover-free binary matrix is presented in Lemma 6, which is proven in the supplementary material with the well-known random coding argument with expurgation in coding theory.

Quality

The proof strategy is a combination of existing techniques. The hypergraph representation of a sparse matrix (set of sparse vectors) is not novel in coding theory, e.g. [R1]. The piercing number is a classical notion in mathematics. While robust-resolvability is a new definition to prove Theorem 1, the proof of its existence is based on the classical coding theory argument (construction of a robust-cover-free matrix).

[R1] U. V. Catalyurek and C. Aykanat, "Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication," in IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 7, pp. 673-693, July 1999, doi: 10.1109/71.780863.

Clarity

The proof of Theorem 1 is difficult to follow. The current presentation entangles readers in a maze. They might give up following the proof. 
The main reason is because the proof strategy is not outlined at the beginning of the proof. Furthermore, the significance of definitions in the proof should be clarified in presenting a mathematical definition and its properties, such as piercing number. When the proof of a lemma is not presented just after the lemma, clarify where the proof is presented. 

Significance

The paper only proved the existence of some query vectors and algorithm for support recovery and approximate recovery. Such a theoretical contribution would be preferred in the field of information theory. NeurIPS should require a practical algorithm to achieve Theorem 1, i.e. a constructive proof of Theorem 1.

Comments

--The paper postulates no regularity conditions for l k-sparse vectors. For mathematical rigor, clarify some regularity conditions, such as the existence of some norm.  

--Remark 1 implies that Theorem 1 may be loose. Clarify where the bound is loose. Use of piercing number? Construction of a robust-cover-free matrix?

--The submitted paper improves [12] by relaxing an assumption [Assumption 1, 12]. However, Assumption 1 on the support in the submitted paper may be still strong from a practical point of view. 
limitations_and_societal_impact: The main limitation is that the paper only presents theoretical contributions and no algorithmic contributions. Thus, it provides no negative societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the problem of learning multiple sparse signals from a mixture of 1-bit measurements, also referred to as mixture of linear classifiers. It proposes algorithms for both support recovery (with corrupted measurements) and value recovery (with noiseless measurements), which come with theoretical guarantees.
main_review: This work provides some valuable theoretical insights for learning a mixture of sparse signals. It considers a setting of non-adaptive queries (which is different from most prior work on this topic), and also makes milder assumption on the signals' supports. The overall structure of the paper is clear. I cannot comment much on the technical parts, which are out of my expertise.

However, one big concern is that, all theoretical results in Section 3 require query complexities that are **exponential** in sparsity $k$ and the number of signals $l$. I think further work need to be done for publication, such as (a) proposing better algorithms that have (quasi-)polynomial query complexity, (b) proving an exponential lower bound, or (c) identifying natural and mild assumptions that make the problem more easily solvable. 

A minor comment on writing: it might be better to keep the order of (1) support recovery and (2) signal reconstruction (i.e. support and value recovery) fixed throughout the paper. In the current version, the order is (2) -> (1) in abstract and Section 2 (definition of Problem 1 and 2), while the order becomes (1) -> (2) in Sections 3, 4, 5, which can be confusing for readers.


--------
After rebuttal:
Thanks for the authors' response. I decide to keep my score.
limitations_and_societal_impact: N/A
review_title: null

Meta-review: This paper studies the problem of learning a mixture of sparse vectors. More precisely, we observe responses that are the sign of the inner-product between a randomly chosen sparse vector from the mixture and another vector, which can either be random or specified by the algorithm. Let $\ell$ be the number of vectors in the mixture and assume that each is $k$ sparse. Let $n$ be their dimension. The main result of this paper is an algorithm that succeeds with high probability with $O(k \ell^3 \max(2 e \ell, 2 e k)^{\min(\ell, k)} \log^2 n)$ queries. The main critiques for this paper were that (1) the bound is exponential when both $k$ and $\ell$ are large and (2) no motivation is given for this problem (other than the fact that it is a generalization of $1$-bit compressed sensing). In their response, the authors emphasized a connection to learning hidden sparse hypergraphs where the correct bound is exponential when $k$ and $\ell$ are large. However, even if that is the answer one would expect, that seems to further detract from the utility of studying this problem. 
Decision: Accept (Poster)