On learning sparse vectors from mixture of responses
Authors: Nikita Polyanskii
Venue: NeurIPS 2021 Poster (2021)
Keywords: sparse vectors
mixture of binary linear classifiers
1-bit compessed sensing
query complexity
noisy measurements

Abstract:  In this paper, we address two learning problems. Suppose a family of $\ell$ unknown sparse vectors is fixed, where each vector has at most $k$ non-zero elements. In the first problem, we concentrate on robust learning the supports of all vectors from the family using a sequence of noisy responses. Each response to a query vector shows the sign of the inner product between a randomly chosen vector from the family and the query vector. In the second problem, we aim at designing queries such that all sparse vectors from the family can be approximately reconstructed based on the error-free responses.  This learning model was introduced in the work of Gandikota et al., 2020, and these problems can be seen as generalizations of support recovery and approximate recovery problems, well-studied under the framework of  1-bit compressed sensing.  As the main contribution of the paper, we prove the existence of learning algorithms for the first problem which work without any assumptions. Under a mild structural assumption on the unknown vectors, we also show the existence of learning algorithms for the second problem and rigorously analyze their query complexity.

On learning sparse vectors from mixture of responses
Nikita Polyanskii IOTA Foundation
Berlin, Germany
mikitappoyymmsyyogmmsl.ccc
Abstract
In this paper, address two learning problems. Suppose family of l unknown sparse vectors is fixed, where each vector has at most l non-zero elements. In the first problem,
concentrate robust learning the supports of all vectors from the family using sequence of noisy responses. Each response to a query vector shows the sign of the inner product between randomly chosen vector from the family and the query vector. In the second problem, we aim at designing queries such that all sparse vectors from the family can be approximately reconstructed based on the error-free responses. This learning model was introduced in the work of Gandikota et al., 2020, and these problems can be seen as generalizations and approximate recovery problems, well-studied under the framework of 1-bit compressed sensing. As the main contribution of the paper, we prove the existence of learning algorithms for the first problem which work without any assumptions. Under a mild structural assumption on the unknown vectors, we also show the existence of learning algorithms for the second problem and rigorously analyze their query complexity.
support recovery
Introduction
Many digital data acquisition methods can be expressed as recovering an unknown real-valued sparse vector from linear measurements. Compressed sensing is a signal processing methodology proposed in g (5 make the process of vector reconstruction reliable and efficient. Criticism of classical compressed sensing is that it assumes infinite precision of real-valued measurements. One interesting setup for compressed sensing is that the measurement outcomes are quantized, e.g., only signs of measurements are captured. Different aspects of the 1-bit compressed sensing problem have been extensively investigated in recent years [
One important sub-problem that often arises in 1-bit compressed sensing is to learn the support of an unknown sparse vector. A vast body of literature focuses on this task and gives bounds on the minimum number of measurements
16
1 B
sufficient for support recovery I 16 13].
In this paper, we investigate model which can be seen generalization of 1-bit compressed sensing. In this model, family of & unknown sparse k-sparse vectors in R" is fixed, and the response to query vector shows the sign the inner product between the query vector and vector picked uniformly at random from the family. The goal is to reconstruct the vectors (or only the supports of the vectors) using the least number of queries. real-life applications, the measurements are suffered by noise, which causes sign flips. Thereby, we also suggest considering a variation of the model that admits adversarial noise.
Our problem statement is in spirit of many machine learning models, e.g., a mixture of linear regression models 77 19 27
29 6 and a mixture of binary linear classifiers [29]. However, we stress an important difference from the classical machine learning setting: in our model, one constructs data points and oracle provides the label for each of them; the goal is find the minimal number of data points sufficient for learning all the components in a mixture of binary linear
21 17
30
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

classifiers. Recent works on mixture of sparse linear regressions considered a similar setting and
studied query complexity of learning algorithms [3] 23 20].
The most relevant research to our work is provided in 14 where the noiseless version of the proposed model was discussed and some single-stage and two-stage learning strategies were provided. The main technical contribution presented in that paper is an algorithm for finding the support of the sparse vectors. However, its main drawback is that for three or more unknown vectors, it was shown to work only under the support separability assumption: the support of any unknown vector in the family is not covered by the union of the supports of the other unknown vectors (c.f. Table I The authors left the problem of support recovery without any structural assumptions as an open problem. We also highlight that for family of two unknown sparse vectors, the authors of [14] provided a polynomial time algorithm for the approximate reconstruction of both vectors that works under a mild assumption.
Since the first submission of this work, the authors of [15] have developed additional theoretical results for the robust support recovery problem. Specifically, using various tensor decomposition techniques and constructions of union-free families, it was shown how to efficiently learn with high probability the supports of all unknown vectors without any assumptions (c.f. Table D.. For certain structural assumptions on the support of unknown vectors, it was also shown how to improve the query complexity.
1.1 Our contribution and technique
Our main contribution lies in showing the existence of learning algorithm that works without any assumptions and is resilient to noisy measurements. Suppose a family of l unknown k-sparse vectors in T is fixed. For any given subset Q C [n]. we first design queries that enable us to learn the number of vectors whose support intersects Q non-trivially. Based on this knowledge, we show how problem of quantitative group testing. In this problem,
to reduce the support recovery problem one needs to learn a hidden hypergraph defined over the set [xi] with É edges each of size at most k. The response
query Q C [n] shows the piercing number, the number of edges overlapping with Q. Here, we arrive to the concept of (f, k. a) roburro----roolllllll us uniquely reconstruct any hidden sparse hypergraph based on sequence of responses. In the combinatorial coding theory literature, this concept was analyzed only when & = 1, a = 0 [26). We extend this line of research for k 2 1 and a 2 0 and give an achievability bound for robust-resolvable matrices. In particular, we show connection between robust-resolvabee matrices and a notion that generalizes cover-free families which were previously investigated in extremal set theory 28 [2]. We highlight that the use of some specific subclasses of generalized cover-free families such as union-free families and pairwise independent union-free families was already discussed the context of various 1-bit compressed sensing problems [14 1 [6]. However, such link was used before either in very specific setting, e.g., l = 1, or under certain assumptions. We note that all queries of the proposed support recovery algorithm can be carried out in parallel (Theorem
matrices (Definition I that allow
Once the supports of all unknown vectors in the family are reconstructed, it remains to recover the values of these vectors. We consider this task in the noiseless setting and make an assumption: (a) the support of any unknown vector not fully contained in the support of any other unknown vector from the family, and (b) the magnitude of each entry can be bounded from below and above. It is known that Okk/c (og(n/c) simple Gaussian queries are sufficient to learn an unknown k-sparse vector in RR using only signs of linear measurements [8]. Thereby, one natural idea to recover the family of vectors to model Gaussian query for every given unknown vector from the family. A similar technique was also used in [4], however, our solutions work under a milder assumption. In simple tto-stage recovery process, we carry out queries required for the approximate reconstruction at the second stage after getting responses to queries used for the support recovery (Theorem 2 In more sophisticated non-adaptive solution, we re-use the concept of cover-free free families that enable us to emulate individual Gaussian queries for any potential family of l unknown sparse vectors (Theorem B
We emphasize that our contribution is primarily theoretical as the questions raised in our work are purely mathematical. For instance, we leave the problem of designing query scheme that allows for an efficient reconstruction algorithm with running time polynomial in the number of queries as an open problem. However, our research has relevant practical applications since the considered model can be used for modeling complex systems with heterogeneous data. According to [14,, studying

---

different aspects in such a model would help analyze recommendation systems where the privacy of user's data has be preserved.
1.2 Outline
The remainder of the paper organized as follows. We introduce some notations and describe the problem statement in Sec. 2 Our results are summarized in Sec. Sec. describes robust support recovery algorithm and introduces useful concepts required for the algorithm. We present our approximate recovery algorithms Sec. Finally, Sec. conclldes the paper and discusses some open research directions. The proofs many statements are deferred to the supplementary material.
2 Problem statement
For simplicity of presentation, hereafter one-based numbering is used and log stands for the base- two logarithm of n. Let H2(a) denote the binary entropy function, i..., H2(a) = -a -a log a (1 a) log(1 a). The set of integers from to is abbreviated by [n]. A vector is denoted by bold lowercase letters, such as æ; and the i-th entry of the vector æ is referred to as T4. A binary matrix is denoted by uppercase letters, such X, and the entry in the i-th row and the j-th column written as Xi.j-
We say that vector support vector æ, written as supp(æ), denotes the set of coordinates corresponding to non-zero components of æ. We write 1 { to denote the indicator function of event A. For an integer vector æ E T and an integer r, 0 < r < m, define the Hamming ball centered at æ with radius r as (x) {y 2m (x. y) r). where du (æ, y) denotes the Hamming distance between and y. We will use the standard notion (o-morm written as ||-112-
R" is k-sparse if it contains at most k non-zero components. The
Let B ( ................................ ( } be family of l unknown k-sparse vectors in 1n such that g
for all i e [d]. Throughout the paper we assume that the number of vectors not too large and the vectors are indeed sparse. Specifically, let lk o(n)). Suppose that an oracle returns a (noisy) output
E 1} for given query vector x E R". [g]:
sign( (0) ,),) M/-
(1)
where the random variable 3 is sampled uniformly at random from the set B, the value E {-1,1} noise, and the sign function is defined as follows
0, -1, a 0.
1,
sign(a:)
Clearly, for 7i- = 1, the resulting response is exactly the sign of the inner product between ( and G. For the approximate recovery problem, assume the noiseless case, i.e., 1/: for all [q]- For the support recovery problem, we make the only structural assumption regarding the noise level, namely:
L 1m== -13 S rq
for given real value E [0, 1). Our first goal is recover the supports of all unknown vectors.
Problem 1 (r-robust support recovery). Let be real value from the interval [0, 1] and B (a(1) "8."),..""" (3.)),3(f) such that with probability 1 O(1/n), based on a sequence of noisy binary responses yı..... My. provided that (1- is possible to find S1,...,,S S₁ S [m] with
a family of & unknown k-sparse vectors in RR. Design queries (1)), ,..., (..),..., (44)
(S..... S2} (supp( supp(
Our second task to approximately recover the unordered set directions of unknown vectors with given precision in the noiseless setting. Formally, this problem can be stated follows.
3

---

Result
Query complexity
Assumption
the support of any unknown not covered by union the supports of other vectors
14
Theorem 1]
O(1)),1 n)
15
Corollary
O ((k) logellootttt 2+2 log n)
No
Theorem
Okkl max( 7 (2,k) log n)
No
Table 1: Comparison of query complexity for support recovery of unknown k-sparse vectors in IR..
Problem 2 (e-approximate recovery). Fix - O. Let > be a given real value and B {g(0) .e.......))) be family of 8 unknown k-sparse vectors in RR.. Design queries _!.))..... al))) such that with probability 1 -0(1//)) based on the sequence of binary responses yı...., Yg provided that 1 22. it is possible to reconstruct the unknown vectors with precision e, Le., find k-sparse
vectors B
B
E IR" satisfying the inequality
B ( c,
max VE(E]
where a : [8] - [E] is some bijection (permutation).
Our results
In the following three statements, summarize main results concerning the above problems.
First, we show the existence of a robust support recovery algorithm without any assumptions.
Theorem (Robust support recovery algorithm). Let B {1((2) ..... ((())) be a family of unknown
k-sparse vectors in R Let E [0, 32t
where
p' min(e, k)
min(f,A)
(1-
min(E, 2ki-min((.A)
(3)
2kl
2kl
Define
((),, := (2 - 1) log(1 -p') 2- logp'' - H2
Then there exists a r-robust algorithm to learn the support of all vectors in B with probability at least 1 O(1nn) using
(2ke 1) log (1 o(1)
w((66T, E, k)
non-adaptive queries, where is Euler's number. For the noiseless case 0, the query complexity can be estimated as
Okk max(2el, mek)min(E..) log n).
For the noiseless case T = O, we compare our query complexity for the support recovery problem with the results of prior work [14] and parallel paper (15) in Table Similar to f15) and unlike (14), we don't impose any structural assumptions on the unknown vectors, which may make the learning problem much simpler. The main drawbacks of our recovery algorithm are: (i) the running time is exponential in l and (ii) the query complexity is exponential in min E) log (og(maxx( kk, E)). Our solution outperforms the one from (15] for small enough k. say k ollog E). We believe that the dependence on k and & is not optimal in all existing solutions and it is possible to further improve the query complexity. For instance, for the degenerate case k and 7 O. also show the existence queries. In our proof. we think that the employed construction of robust-resol resolvable matrices via robust cover-free codes is far from an optimal one (Lemma 5). As for converse bounds in the noiseless setting, from simple counting arguments, follows that the number of queries in the support recovery problem has to be at least 2 log(E+1) log n). Recall that for 1,
Remark 1.
of an algorithm with O ((A Flog"
log
1² the number of queries required for finding the support of the unknown vector is at least 2 log
logn)
which is implied by 11

---

Let us introduce a mild assumption required for the approximate recovery problem.
Assumption 1. Let B { ..... . be famity of t unknown k-sparse vectors in R". For every i # j. the support of the i-th vector from is not contained in the support of the j-th vector from B, Le., supp(B(() supp(g(i) + 0. Some bounds on the magnitude of non-zero entries in all vectors from B are given, e.g,, that 0 O.
I 18 S exp(O(n)) for all j E [m]] and i [1] such
Recall that the approximate recovery problem is considered in the noiseless setting, i.c., T 0. Now show the existence of query algorithm which can be performed in two (non-adaptive) stages. Theorem Stwoestage approximate recovery algorithm). Let e > 0 be a real value. Let = 7 Then there exists an algorithm to recover all vectors in B with precision with probability least I O(L/n) using
(3(0) ......3)) 3 be family of vectors as in Assumption
o kE (kee max(2el, bek)min(t..))) log" n n log(k/c) log((/)))og(n/e)
kdd
queries that can be asked in two (non-adaptive) stages.
Finally, we present result concerning the existence of non-adaptive learning scheme.
Theorem 3 (Single-stage approximate recovery algorithm). Under the condition of Theorem there exists an algorithm to recover all vectors in with precision e with probability at least (1/n) using
o 2.203
(ke max(2el, min(k)) log log(n/c/) log(k/c)
non-adaptive queries.
4 Robust support recovery
For a set Q S [n] and a family = (3(1) (((), of unknown k-sparse vectors R", we define the piercing number of Q in B as
pir Qi = Σ )
In Sec. 4.1
we first show how to learn this number with overwhelming probability by asking the same query multiple times. Sec. 4.2 we rephrase the support recovery problem the language of quantitative group testing and introduce the concept of robust resolvable matrices. The existence of such matrices discussed Sec, 4.3 and Sec. 4.4 Finally, in Sec. 4.5 we give a proof of Theorem
4.1 Estimating the piercing number
Let Q S [n] and æ = (ai...., xn) be a vector such that the i-th entry is sampled independently from the continuous uniform distribution U(0, 1) if i Q and is 0 otherwise. For integer m (divisible by 168), define
x. (1)
x (m/22 x
and
x (m/2+1)
x (m) x.
For every i E [m]] let y be noisy response defined as in (I. Let round(y) be function that takes real number 7 as input and outputs the closest integer number. Define sample statistic that estimates B)
m
pir(Q, m) == round
Σ yi
Σ
Vi
im//2+]
Lemma (Piercing number estimator). Suppose
m 1/1 = - 11 < m
Then it holds that
Toe
Pr pir(Q, m)) = pir(Q, B)
- exp( (opl-st(mt-
5

---

4.2 Quantitative search model for sparse hy hypergraphs
hypergraph is a pair H E), where V is set of vertices, and E is a multiset of non-empty
subsets of V called hyperedges. A hypergraph H = (V, E) is said to be (E, ---paasseseeeeeee if the number of hyperedges is and the size of each hyperedge is at most Let E {er.... ,,,,),,, EE). For subset
Q S V. define the integer output =QQ, H) as follows
(Q, H) = Σ +()
(4)
==1
We now introduce the hypergraph His (V, EB), where the vertices V [n] and the set of hyperedges Es = [er,..... ee} contains hyperedges with e; = supp(33)) for all E [C]. Note that without any assumptions, the edge set Eg can possibly contain a hyperedge with large multiplicity if some vectors in B share the same support. Clearly, Hg is (f. -sparsee and z(Q HB) = pir(Q, B). In next statement, we derive an obvious extension of Lemma
Let B be a family of unknown sparse vectors and QQ....,Qu. Qm S [n] be a sequence of subsets. Set (=(Q1, Hg),..., z(Qm. HB)). Let be noise parameter such that O S. Te: Then there exist queries a!1), ,..., xl9)
Lemma 2.
1
IK" with q = ( log(ma)) such that with probubility 1 - O(1/n), bused sequence of binary responses ".,.....
..,3, provided that 2 it is possible to reconstruct at least one E 2 such that du (2, 2) S 16rEm.
Let X be a binary matrix of size m x n, and H = (V, E) be hypergraph with V = In]. Set Q: supp(X;), where X; is the i-th row of X. With a slight abuse of notation, we denote by
z xX, H = (Z)...., 2m)
the sequence of integer responses, where 2; (Qi, H) is computed as in Lemma naturally motivates us introduce notion of robust resolvable matrices.
Definition (Robust resolvable matrix). Fix real number cx, 0 < a < 1/2, and integers E, > 1. matrix& X of size m x n said to be (f, kt a t-rrobut-resolvabll for any two distinct (f, k))-parse hypergraphs H1, H2, the corresponding Hamming balls centered at x =(X, H1) and xXX, H2) with radius am are disjoint, i.c.
(1), H2)) 2 2am +
By m(n, E, k. a:) denote the minimal number of rows in an (e, k, a) i--robut-resollvare matrix with n columns. Up to our best knowledge, Definition for > (and a 0, k: 2 2) new in the literature. We proceed our discussion with the simplest case & = 1 which might seem degenerate. However, the corresponding analysis already non-trivial and sheds light on the existence of robust resolvable matrices.
4.3 Existence of (4, 1,1,0)-oobuutt-rsoovabbl matrices
We now review literature (e, 1, 1100)rreollvbbl matrices. The best known explicit constructions come from number theory [4] [2] and are closely related to the concept of BCH codes. They have n columns and m f log r1(1 o(1) rows. For É 2 3. the best currently known resolvable matrices are all inexplicit and constructed by random coding as shown in 26 10).
Lemma 3. For any given integer f, there exists an (e, 1, resolvable matrix of size m n with
28
m
log
22 22
log (()))
Furthermore, logng/ log ((1 + o(1) as oc. Remark 2. The presented existential result is order-optimal. By 110 8). the number of rows in an (e, 1, roout)-abbuutteesslvallllll matrix with n columns has be m 28 logn/ log f(1 + o(1))
4.4 Constructing robust resolvable matrices via robust cover-free matrices
challenging to find sufficient (and necessary) condition for a matrix to (f, k, -obuustt resolvable. In the following statement, make step toward understanding this problem.

---

Lemma 4, Suppose H1 = (V, 31) and H2 = (V, E2) are two different (f, -spare hypergraphs. Then there exists a query Q V of size at most min(f, k) that separates the hypergraphs, i.e. =(Q, H1) * =Q, H2).
Proof. Since two hypergraphs are distinct, there exists at least one hyperedge such that one edge set (E₁ E2) contains it with larger multiplicity than the other one (E2 Ei). We take the largest hyperedge with this property. Without loss of generality, let my and m2 be multiplicities such that is included, respectively, to F with multiplicity mi and Eg with multiplicity m2g l 2 m. > m2 2 O. For vertex v, define the set of hyperedges in a hypergraph H = (V, E) that are incident to this vertex
A(u, {e' E vEd)..
Consider the set of hyperedges Nose A(v, H1). It includes mi copies of and possibly some other hyperedges E' C Ej. We observe that the set of hyperedges Nwee A(v, H2) includes m2 copies of e and precisely the same set of hyperedges E". This happens due to the choice of e. Thus, we obtain
mi + |E =
A
A(v, Hi)
>
n VEE
A(v, H2) = =m + EE".
(5)
JoEe
Toward a contradiction, assume that there is no Q S such that
=Q, H1) = U
A(v, Hi) +
U NEQ
A(v, H2) = =QQ, H2).
FEQ
This means that the above unions for any Q S must have the same size. By the inclusion-exclusion principle
A(t,HH)) = Σ
(-1)191+1
n
A(u, H1)
PEQ
D7Q'SQ
PEQ
Therefore, by induction on the size of Q, one can derive
n
A(u. H1)
n NEQ
A(v, H₂)
tEQ
for all Q C e. This contradicts to when c.
The above arguments show that proper query Q could have size at most f. Assume that =QQ Hi) > =Q, H2). Note that =(Q, H1) < k since Hi contains & edges. Thus, one can remove at least m0 QI - k) vertices from Q to get a subset of vertices Q' such that the output result for H1 is not changed, i.e., 2Q'', H1) z(Q, H1). On the other hand, it is clear that 2(Q', H22 S x(2, H2). This completes the proof.
Lemma suggests way for constructing (E, robust matrices. We now introduce a concept that generalizes the definition of cover-free codes. This family of codes was originally suggested in (24 connection with cryptographic applications.
Definition 2. A binary matrix X of size m is said to be f, rooou-a---oustt-oee---reeeee if for any disjoint subsets of columns U, W C [n] of size [U] = c and [W] = f, there exists at least 2am + 1 rows S [m] such that
X 1
for i [7 EU
X, = for all E [T] W.
If 0, then a (c. f, rohustt-ccee matrix is simply called (c, --cover-eeeee
An (1, f. a:) robuss--oveerr-eeeeeeeeeeo free matrix is also called robust union-free The latter has several applica- tions in 1-bit compressed sensing [6]. Now we state a straightforward corollary of Lemma that enables us to construct robust resolvable matrices.
Lemma 5. Suppose a binary matrix of size m x i (minn(e k), 2kl min(l, k), a) (.),aa)oouuust-eee -ooust---ove
free. Then X is (e, k, a) relllllalll......lle...
7

---

Proof. Let H1 (V, and H2 = E2) be two distinct (E. -sparre hypergraphs. By Lemma 4
there exists query Q S V. [Q] I min(e, k), such that xQ2 H1) * 2Q2, H2). Define W to be {v and W _ [m]. [W] < 2 min(L, k). Combining these arguments with the fact that is (min(e, k), 2kl min(f, k), a)) roobust-oroess yields that X is (c, k, aerok,,.--ouuuuttetee robuss-resollaabblle
E En U }2) Since we associate V with [n], we get Q S [n]. Q < min k.).
Fundamental limits of cover-free matrices have been subject of extensive studies in many papers [2]
28 However, we cannot directly apply known bounds since they correspond to the case = O. Now we present an achievability bound for robust cover-free matrices.
Lemma 6. Let c 2 1 and be integers, be real number from the interval (0.//2). where
p ( (tt)) (c++)'
Define
g(7 e, f) == (2y log Then there exists (c, [, co.ffaa)-robus--oove--reee matrix of size m such that
(1- P) 2n log H2((?)).
m (c+ 1--f-117 11-1) log n (1 + o(1).
g)
Using the above statement, we show an existential result for robust-resolvable matrices. Lemma 7. Let E 2 1 and k 2 be integers, be real number from the interval (0. /2). Let pl and w(r, k) be as in Theorem Then there exists an (f, k. resstttaee-e matrix of size m x n such that
(2ke 1) log
w(a, kkk)
For a = O, we have
m(n, e, o) (kl max(2el, 2ek) min(())))))))) logn).
Proof. The statement is implied by Lemma and Lemma min(E.))
with min(e, 28h
4.5 Proof of Theorem
Let == - ( (00 be family of unknown k-sparse vectors. Let H8 = (V, E&) denote the (E, -s-arse hypergraph induced by i.e., the of edges Eg consists of the supports of vectors from B. Set a 16 By Lemma 7 there exists an (f, kt rooust-ss-ee matrix X of size m x with
.....,
w(a.t,k) (1+) By Definition Hs can be uniquely recovered based on any noisy version & E nd of the vector 2XX, HE) so that di d 2(x, HB)) < amn. Applying Lemma 2 with overwhelming probability one can learn some by asking q O log(um)) queries (11)) ..... ...-, (99)) and obtaining responses .1,---. - Bg provided that (1 Finally, reconstruct the supports of all unknown vectors, we apply Algorithm This algorithm uses function next(.) that takes an (e, -spaase hypergraph and outputs the next [E, k) -sparse hypergraph (here we assume some canonical order on the set of sparse hypergraphs). In other words, the algorithm involves enumerating over family of (E, -sprse hypergraphs. Thereby, g queries are sufficient for solving Problem
[246- 1) log
Algorithm 1: Support recovery algorithm
Data: (e, rou---rbu--rsoollabblll matrix X of size n: noisy response vector & with d'r (xX, X, HB))
/+ exists by Lemma 7 +/
< om
/* found by Lemma 2 +/
Result: supports of the & unknown vectors, S SI...., S C [n]
H + (V, E). where V = [n], E = fei..... (t), e, [k];
while d (X, H) 2) > am do
H + next(H)
/* outputs the next sparse hypergraph */
end
for
i 1 to l do S, x 6
end

---

Approximate recovery
Throughout this section, we assume that there is no noise in measurements, i.e., T O. Theorem enables us to assume that the supports of all sparse vectors are already known. Thus, it remains to approximately reconstruct the values of the vectors.
A query vector æ = (z1....., Fn) E R" is called Gaussian if each entry is sampled independently from Gaussian distribution (0, 1). We shall the following result which says that Gaussian queries allow to efficiently reconstruct any sparse vector.
Lemma (Approximate vector recovery, [88). Let 3 be an unknown vector in IR with || = For any > 0, there exists algorithm that takes responses to Gaussian queries ..... x(() E 12
with O E log 4) as input and outputs 3 R so that ||
Recall the response to a query in our model is taken uniformly at random from set of & possible responses. Therefore, we need to show how to model a response to a Gaussian query for any given vector from the family. Here, we will use our structural assumption regarding the support of vectors (c.f. Assumption D In Sec. 5.1 we show how to emulate individual Gaussian queries in our model. In Sec. 5.2 we present two-stage approximate recovery algorithm.
5.1 Modeling Gaussian query
Define Inf to be very large positive real number whose lower bound will be clear from the context. For query vector (æ1, (21,...,, T.n) R² and integer [e]. write Inf(*) (a:) to denote the vector whose j-th entry
Tjj E Supp(3 or E Ut/ssupp(3"")
Inf (x)) =
Inf, otherwise.
Let O denote an all-zero vector whose length will be clear from the context and g E R" be Gaussian query. Fix an integer i [{] and some positive integer m. Set (1.i) = _.... x (m/2,s)
Inf(*) (g) and (m/2+11,5) = = (m.f) = (nf (0). Let yı,..., 3m be responses to queries (1.3). ;...,,"" x (m.1), i.e., yj = (ag B3) with 3 being sampled uniformly at random from B.
Define sample statistic that estimates the value sign((g. ((g, ()))
2 m
VIA
sign(g, (00mm) m) round
Σ yj
Σ
Vi
+1
j=m/241
Lemma (Gaussian query estimator). Let B be family of sparse vectors that satisfies Assumption Then holds that
Pr si (00 m) sign((g,3(0)))
(pp(-(((-2m)))
5.2 Proof of Theorem 2
Let = (1 ....",..... (00) ((0) be a family of & unknown k-sparse vectors that satisfy Assumption Fix <> 0. First, we invoke Theorem 1 and with probability O(1/n), the supports of all vectors in B can be reconstructed using (kt max(2ef, 2ek) min((.)) log" n) queries. Note that the number of coordinates in the supports of the vectors is at most kl.
..... .(M.....)))........ Bg with R = O log ) being as in Lemma Applying Lemma with probability 1 O(ne è log =)-)) we can learn the value of sign((g (i) 3 (()))) for some [R] and i [f]. by making O log(nkl/c)) queries. By the union bound, all values (sign( (g)()) (000))8()) jjj [R] i [4]} are reconstructed with probability 1 (1/n)) by making O log log(nkl/c) measurements. Finally, Lemma guarantees that all sparse vectors from B can be recovered with the given precision based on the set of values {sign((g (0)gn(())),,0 (()))))))))))))))))
At the second stage, we first generate Gaussian vectors ()),.,,
[R], ė [e]] Since kt O(n). the required claim follows.

---

5.3 Proof of Theorem 3
Let B = (33 ,,.."....,"""""" ....,,3(0) be a family of & unknown k-sparse vectors that satisfy Assumption Fix
6 >> 0. First, we apply Theorem I and with probability 1 O(1 (n),, the supports of all vectors in B can be reconstructed using (R:E max(2el, 2ck) 2ck)min(f,k) log" n) queries. Note that the number of coordinates in the supports of the vectors is at most kL.
It remains to approximately recover the entries of the unknown vectors by asking queries in parallel to the queries used for the support recovery. Let X be an (L, coverr--ee matrix of size m x n with m = (kk max(f, k) miin((k.) exppminn( k)) log 71) which exists by Lemma 6 Let R = O log ) be the number of queries required in Lemma 8 For j E [R], define G to be a real- real-valued matrix obtained from the binary matrix X by replacing I's by Inf's and O's by independent samples from a Gaussian distribution (0, 1). We define Inf (X) to be a real-valued matrix obtained from the binary matrix X by replacing I's by Inf"s.
We ask queries corresponding to rows of matrices (Tnr() GX)( : : [R]} multiple times. Let T denote the number of times a fixed query repeatedly queried. We set T 0 (o)((RR) Recall that all the matrices are obtained from an (e, (e.kee)-oveer-free matrix. This means that for
every j E [R] and [f]. there exist rows in G (X) and Inf' (X) that are Inf (g) and In (0) for some Gaussian query 9. Thus, by Lemma 9 with probability 1 - [[( one can learn sign((g ())) for some E [C] and some independent Gaussian query g j E [R]]. By the union bound, one can learn the set of values (sign((g ,))))) : E [R]. i E [{]} with probability guarantees that all sparse vectors from B can be reconstructed with the given precision based the set of values ((.)) (3))) =j E [R]) E [[]]
1 1- 1-0(1/m) (1))n.. Finally, Lemma 8
Finally, we estimate the number of queries used at the second stage of the approxi- mate recovery algorithm as O O²* log(= k ) max(e, k) m))in((ke) exp(min((, R:)) log lognlog" ") Thus, the total number of queries sufficient for solving Problem _ can be estimated as te (3 max(2el, mek)miin(k.)) log n log( l)g(
Remark 3. We note the following improvement on query complexity the number of queries required in Lemma 8 can be additionally bounded as o(log n) (e.g.. it is applicable when = (2(olg n)- n)-1/2)). In such a case, one can generate (f, kł, re-orousstcooer--fee o and m = Okk max(e, k) mi)kk(k, exp min(f, k)) log n) and construct only two matrices G(X) and [x) in a similar way. By performing the rest of the same procedure, one can decrease the total number of required queries in 12 & log(?)) times.
matrix of size m x n with small positive
6 Conclusion
In this paper, we studied two problems that arise in recovering unknown sparse vectors from mixture of sign responses. For the support recovery problem, we found a completely non-adaptive solution that does not use any assumptions. This problem was posed in [14). In addition, the proposed algorithm is resilient to noisy measurements. When describing our result, we introduced the notion of a robust resolvable matrix and derived an existential result for such matrices. We leave the problem of deriving fundamental limits of this combinatorial object as an open challenging problem that can be of independent interest in computer science, coding theory, and combinatorics. For the approximate recovery problem, we suggested single-stap stage and two-stage reconstruction algorithms working under Assumption TT] Finding an algorithm for robust approximate recovery of a family of unknown sparse vectors without any assumptions remains a major open problem.
Acknowledgments and Disclosure of Funding
The work was conducted in part when Nikita Polyanskii was with the Technical University of Munich and the Skolkovo Institute of Science and Technology. The author indebted to Arya Mazumdar for bringing this problem to his attention. The research was supported by the German Research Foundation (Deutsche forschungsgemminschhff, DFG) under Grant No. WA3907/1-1 and by the Russian Foundation for Basic Research under Grant No. 20-01-00559.
10

---

References
[1] Jayadev Acharya, Amab Bhattacharyya, and Pritish Kamath. Improved bounds for universal one-bit compressive sensing. In 2017 IEEE International Symposium Information Theory (ISIT), pages 2353-2357. IEEE, 2017.
[2] Albert Ai, Alex Lapanowski, Yaniv Plan, and Roman Vershynin. One-bit compressed sensing with non-gaussian measurements. Linear Algebra and its Applications, 441:222-2399 2014.
[3] Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Hongyang Zhang. Learning and 1-bit compressed sensing under asymmetric noise. In Conference on Learning Theory, pages 192. PMLR, 2016.
[4] Raj C Bose and Sarvadaman Chowla. Theorems in the additive theory of numbers. Commentarii Mathematici Helvetici, 37(1):141 147, 1962.
[5] Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEÉE Transactions information theory, 52((): -098 2006.
[6] Arun Tejasvi Chaganty and Percy Liang. Spectral experts for estimating mixtures of linear regressions. In International Conference on Machine Learning, pages 1040-1048, 2013.
[7] Yudong Chen, Xinyang Yi, and Constantine Caramanis. A convex formulation for mixed regression with two components: Minimax optimal rates. In Conference on Learning Theory, pages 560-604, 2014.
[8] Arkady Djackov. On search model of false coins. In Topics in Information Theory (Colloquia Mathematica Societatis Janos Bolyai 16). Budapest, Hungary: Hungarian Acad. Sci, pages 163-170, 1975.
[9] David L Donoho. Compressed sensing. IEEE Transactions on information theory, 52(4):1289; 1306, 2006.
[10] Arkadii D'yachkov and Vladimir Rykov. On a coding model for a multiple-access adder channel. Problemy Peredachi Informatsii, 17(2):26-3,, 1981.
[1]] Arkadii Georgievich D' yachkov and Vladimir Vasil'evich Rykov. Bounds on the length of disjunctive codes. Problemy Peredachi Informatsii, 18(3):7-13, 1982.
[12] Arkady D' y'ycchkov, Pavel Vilenkin, David Torney, and Anthony Macula. Families of finite sets in which no intersection of sets is covered by the union of others. Journal of Combinatorial Theory, Series A, 99(2):195-25 218,,2118222 2002.
[13] Larkin Flodin, Venkata Gandikota, and Arya Mazumdar, Superset technique for approximate recovery in one-bit compressed sensing. In Advances in Neural Information Processing Systems, pages 10387-10396, 2019.
[14] Venkata Gandikota, Arya Mazumdar, and Soumyabrata Pal. Recovery of sparse linear classifiers from mixture of responses. Advances in Neural Information Processing Systems, 2020.
[15] Venkata Gandikota, Arya Mazumdar, and Soumyabrata Pal. Support recovery of sparse signals from a mixture of linear measurements. In Advances in Neural Information Processing Systems, 2021.
[16] Sivakant Gopi, Praneeth Netrapalli, Prateek Jain, and Aditya Nori. One-bit compressed sensing: Provable support and vector recovery. In International Conference on Machine Learning, pages 154-162, 2013.
[17] Mian Huang, Runze Li, and Shaoli Wang. Nonparametrie mixture of regression models. Journal of the American Statistical Association, 108(503):929-94) 2013.
[18] Laurent Jacques, Jason N Laska, Petros T Boufounos, and Richard G Baraniuk. Robust 1 1-bit compressive sensing via binary stable embeddings of sparse vectors. IEEE Transactions on Information Theory, 59(4):2082-2102 2013.

---

[19] Abbas Khalili and Jiahua Chen. Variable selection in finite mixture of regression models. Journal of the american Statistical association, 102(479) 2007.
[20] Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, and Soumyabrata Pal. Sample complexity of learning mixtures of sparse linear regressions. In Advances in Neural Information Processing Systems, pages (0532-10544) 2019.
[21] Yuanzhi and Yingyu Liang. Learning mixtures of linear regressions with nearly optimal complexity. In Conference On Learning Theory, pages 1125-1144. PMLR, 2018.
[22] Bernt Lindström. Determination of two vectors from the sum. Journal of Combinatorial Theory, 6(4):402-407, 1969.
[23] Arya Mazumdar and Soumyabrata Pal. Recovery of sparse signals from mixture of linear samples. In International Conference on Machine Learning, pages 7466-7475, 2020.
[24] Chris Mitchell and Fred C Piper. Key storage in secure networks. Discrete applied mathematics, 21(3):215-22 2288, 1988.
[25] Yaniv Plan and Roman Vershynin. One-bit compressed sensing by linear programming. Com- munications on Pure and Applied Mathematics, 66(8):1275 2013.
[26] Grigory Poltyrev. Improved upper bound on the probability of decoding error for codes of complex structure. Problemy Peredachi Informatsii, 23(4):5-18, 1987.
[27] Weixing Song. Weixin Yao, and Yanru Xing. Robust mixture regression model fitting by laplace distribution. Computational Statistics & Data Analysis, 71:128-137, 2014.
[28] Douglas R Stinson, Ruizhong Wei, and Lie Zhu. Some new bounds for cover-free families. J. Comb. Theory, Ser. A, 90(1):224-234, 2000.
[29] Yuekai Sun, Stratis loannidis, and Andrea Montanari. Learning mixtures of linear classifiers. In International Conference Machine Learning, pages 721-729, 2014.
[30] Taiyao Wang and Ioannis Ch Paschalidis. Convergence of parameter estimates for regularized mixed linear regression models. In 2019 JEEE 58th Conference on Decision and Control (CDC), pages 3664-3669. IEEE, 2019.
[31] Dong Yin, Ramtin Pedarsani, Yudong Chen, and Kannan Ramchandran. Learning mixtures of sparse linear regressions using sparse graph codes. IEEE Transactions on Information Theory, 65(3):1430-14511 1451, 2018.
12


Reviews:
[{"review_id": "lbMer7Kv82C", "reviewer": "Reviewer_QFJA", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nHowever, 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. \n\nA 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.\n\n\n--------\nAfter rebuttal:\nThanks for the authors' response. I decide to keep my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "d5Rec60UzfC", "reviewer": "Reviewer_mc9P", "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. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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:\n\nWhat 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. \n\nThe 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]. \n\nFor 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. \n\nA minor issue: Line 103, in the definition of the Hamming ball, d_H is used without definition. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "a_u1_pwVQ2a", "reviewer": "Reviewer_aD1b", "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.  ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nLooking 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.\n\nSome 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.\n\nThe paper does not provide a significant comparison to prior and related works. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of the paper is mentioned in the concluding section and in the last paragraph of section 1.1.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "EASPXGb2Yt", "reviewer": "Reviewer_dmUb", "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. ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n1.\tLine 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.\n\n2.\tTypos 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?\n\n3.\tLine 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.\n\n4.\tIn line 195: $m(n,l,k,\\alpha)$ is introduced, but it is referred to as $m$ from thereon.\n\n5.\tThe 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.\n\n6.\tMy 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.\n\n------------------------ Post author response ---------------\n\nI 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "around 12 hours"}, "extra_text": {}}, {"review_id": "5f6l59HY0GU", "reviewer": "Reviewer_DGsh", "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). \n\n 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].\n", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality\n\nThe 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. \n\nThe 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.\n\nThe 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.\n\nInstead 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.\n\nQuality\n\nThe 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).\n\n[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.\n\nClarity\n\nThe proof of Theorem 1 is difficult to follow. The current presentation entangles readers in a maze. They might give up following the proof. \nThe 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. \n\nSignificance\n\nThe 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.\n\nComments\n\n--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.  \n\n--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?\n\n--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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

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)