Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this work, the authors study the problem of learning one hidden layer neural network with ReLU activations with $k$ neurons. Their objective is to output a ReLU network $F'$, such that $\|F-F'\|_2^2\leq \epsilon$, where $F$ is the unknown network. They assume that the underlying distribution is Gaussian, and that they have query access to the network. A query is a function of the form $q(x)=F(x)$, that is given an $x$, the query returns the value of $F(x)$. In this work, the only assumption is that $F(x)$ is bounded with respect to the $\|\cdot\|_2$. Other works have required either the vectors $\vec w$ to be linear independent or the weights to be non-negative. The assumptions are required in general, as linear independence is required for parameter estimation, and there exists Statistical Queries hardness on getting $\|F-F'\|_2^2\leq \epsilon$ using polynomial many queries without the assumption of non-negative weights. By assuming a more powerful model with queries they overcome the hardness. 

Their algorithm restricts $F$ to a random line $L$ and then uses queries to estimate approximations to the gradients and get the critical points (points where a neuron is activated, i.e., changes sign) of $F$ restricted to the line $L$, and then they can estimate the $w_i$, and the $b_i$. One problem of this approach is that fails if some neurons are close to each other. To overcome this, the authors prove that if some neurons are close to each other, then they can be approximate by a linear combination of at most two neurons. The algorithm uses polynomial samples and queries with respect the parameters $d,max\|w\|,max(b),1/\epsilon,k$.
main_review: The authors study an interesting problem for the community of statistical learning and provide a polynomial learning algorithm with mild assumptions. The authors overcome several difficulties of this problem by using queries to the unknown function. I find the idea of searching in a Gaussian line for critical points very interesting which might also be of independent interest.

The main weakness of this work is that the queries that are needed are comparable with the overall sample complexity. I would guess that the queries that are needed for this problem, should be less (i.e., logarithmic) and/or with fewer dependencies on the parameters than the ones required by the samples.

Other:
1. $W$ changes to $R$ in the following sections.
2. Instead of having bounds on the norm of the vectors and the parameters, wouldn't a bound on the $\|F\|_2$ norm suffice?
3. Lemma 3.3 is difficult to parse.
4. Line 203 $b^*+$ should be $b^*$
5. I would suggest changing the structure of Theorem 4.8 to make it easier to parse.
6. Algorithm 4 has broken references.
7, Authors should clarify which of the previous work did parameter estimation vs function estimation.
limitations_and_societal_impact: This work does not seem to have any negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Present the first provably polynomial-time algorithm for learning unknown one-layer neural networks when given black-box access to the unknown network.
main_review: $\textbf{Originality}$

To my knowledge, the algorithm presented is novel, and it is clear how this work both differs from and builds upon previous contributions to this topic.

$\textbf{Quality}$

The theorems are clear and supported with sound proofs.

$\textbf{Clarity}$

The submission is clearly written and easy to follow.

$\textbf{Significance}$

Efficiently learning an unknown one-layer network has been an open question with a lot of active research. I believe that such an algorithm is certainly significant.
limitations_and_societal_impact: $\textbf{Limitations}$

The authors have not discussed the limitations in an explicit section, although there is some discussion within the paper. I think the limitations could have been discussed more explicitly.

$\textbf{Broader Impact}$

There is no discussion about the potential negative societal impacts of this work. Given the nature of this work, I think there is certainly potential for negative impact (e.g. model extraction attacks, as stated by the authors but not discussed). I think a section dedicated to this discussion is necessary given the content of the paper, particularly talking about how to mitigate any potential negative impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper provides a polynomial-time algorithm for learning neural networks (NN) with one hidden layer through queries. The result holds for NN with bounded weights and biases under Gaussian distributions.

The authors define a notion of closeness between neurons that allows strong assumptions on the weights (which were used in prior work and didn't translate to the overparametrized setting) to be dropped. Indeed, if a set of neurons are "close" enough, they can be approximated by two neurons or a linear function. This allows the learning algorithm to efficiently represent the target NN, which could be overparametrized.

At a high level, the algorithm recovers neurons by sampling a Gaussian line, separating it into suitably small intervals and computing the gradient (through queries) at their midpoints to recover the neurons' weight vectors. 
main_review: I believe this is a strong paper. It is interesting in its own right, and, as the authors mention, the question is particularly relevant given the practical threat of model extraction in adversarial machine learning. Moreover, the theoretical results on the structural properites of NN (neuron closeness, learning a NN with biases) and the fact that the algorithm works in an overparametrized regime are of independent interest.

The paper is well-written and has a great structure/organization (especially for the outline of the technical results, which gives the reader a clear idea of the proof without being overwhelmed by technical details). The related work section is detailed and it is clear how the work differs from results in the literature (and how previous approaches would fail in the given problem setting). However, a major flaw is the lack of a discussion/conclusion section, which would need to be added were the paper to be accepted. 

Finally, the paper could greatly benefit from an experimental section that implements the algorithm and evaluates it on synthetic and real-world data.

Minor comments:
- l.27-30: Please add the distributional assumption in the theorem statement
- l.46-48: Please define x_0 and v (\in \R^d)

Suggestions:
- l.19-22: It would be great to have a table of different NN learning algorithms (distributional and structural assumptions, runtime, etc.) to compare recent work with this paper
- l.124-125: N(0,I_d) perhaps add that this is WLOG, as we can centre + normalize the training data
- l.133: it would be a good idea to add some text here introducing the lemmas/facts, where they will be used, and stating that the proofs are in the appendix 
- l.134,138: maybe add "we denote by ... the operator norm, and by ... the Frobenius norm" at the beginning of the preliminary section (they haven't been introduced). Also, define S and Haar-randomness 
- Lemma 3.8: perhaps define B and R before "If signs s_1,..."
- l.297-298 and Algorithm 3: could you please add a few sentences explaining what happens when an interval doesn't lie within a linear piece of F_L, and why if (v_j, b_j) can be dropped if they don't satisfy equation 4 (line 13 of Algorithm 3)?

Typos:
- l.143: "the supplement" -> "the supplementary material"
- l. 169: "satisfies triangle inequality" -> "satisfies the triangle inequality"
- l.203 typo "+" in the definition of b^*? 
- l.289: "several sufficiently small" -> "for several sufficiently small"
- l.306: "we prove correctness" -> "we prove the correctness"
- Algorithm 4: Definition and LS problem references are "??"
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers the problem of learning depth-2 ReLU networks w.r.t. Gaussian inputs, where the learner has query (black-box) access to the target network. The problem of learning depth-2 networks (without queries) has been extensively studied in recent years. All known efficient algorithms require assumptions on both the input distribution and the network’s weights (e.g., that the weights matrix has full rank). Moreover, the known efficient algorithms for depth-2 ReLU networks do not handle bias terms. In this paper the authors give a first efficient algorithm for learning depth-2 ReLU networks with bias w.r.t. the Gaussian distribution using black-box access. There are no assumptions on the weights, except for having a bounded norm. The motivation for the problem is two-fold: (1) the model of PAC learning with membership queries is well-studied and natural; (2) there is an interest in model-extraction attacks in the security and privacy communities. Prior works on model-extraction either gave algorithms without theoretical guarantees, or efficient algorithms under strong assumptions. 

The proposed algorithms follows the following ideas. For a random line L consider the restriction of the target network F. This restriction is a piecewise linear univariate function, such that each critical point corresponds to a neuron in F. This property can be exploited in order to recover the neurons. However, there are some major issues to overcome in order to implement this idea efficiently. For example, since we do not have any assumptions on the weights, then the critical points might be very close to each other. The authors solve this issue by showing that this situation occurs only if there is a cluster of similar neurons, in which case we can replace them with a small sub-network and do not have to recover all the neurons in the cluster.

main_review: The model of learning with queries has gained interest both from the theoretical and from the practical viewpoints. The authors show that for the case of depth-2 ReLU networks, black-box access allows us to achieve learners with improved guarantees. I think that the problem considered in the paper is natural and that the contribution is significant. I have some comments on the presentation, which I discuss below.

The authors mention that obtaining polynomial-time algorithms for learning depth-2 networks without assumptions on the weights (and without queries) is an open problem. I think that mentioning the known hardness results for the problem would help understanding the context. Statistical queries lower bounds for learning depth-2 networks on the Gaussian distribution is given in [Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, and Nikos Zarifis. Algorithms and sq lower bounds for pac learning one-hidden-layer relu networks] and in [Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent]. Also, hardness of improperly learning depth-2 networks (with any algorithm) over another product distribution is given in [Amit Daniely and Gal Vardi. From Local Pseudorandom Generators to Hardness of Learning]. Hence, by these hardness results, obtaining a result similar to Thm 1.1 but without queries is probably impossible. It implies that in the case of depth-2 networks learning with queries seems to be strictly stronger than learning from random samples.

Example 1.2: I suspect that there is an error here. For example, if x_2 = 4/Lambda and 0<x_1<1 then F(x_1,x_2) = x_1+4 + 3x_1+4  - 2(-x_1+4) = 6x_1 \neq 0.

In line 117-119 it says: “we also emphasize that our results are the first theoretical guarantees for learning one hidden-layer networks with bias terms in any learning model, including PAC learning from samples”. Note that JSA15 also allows a bias term (although the assumptions on the activation function there rules out the ReLU function).

Lemma 4.11 argues that F can be approximated by a combination of the neurons returned by GetNeurons. However, by Thm 4.8 it is not sufficient to use these neurons, since there is also a term <w*,\cdot> and a term b*. Am I missing something here?

Section 4.4: First, the distributions D’ and D are not defined (they are only defined in the appendix). Also, by observing the appendix, I see that the distributions D and D’ are such that z has dimension |S|+d+1 and hence it seems that the linear regression of algorithm 4 finds also the required w* and b* that I mentioned in the previous comment. However, even in the appendix, in Thm 4.12 the returned function \tilde{F} uses only the neurons in S and does not use w* and b*.

More comments:
- Lemma 2.6: There exists C s.t. for every \nu …
- Lemma 2.7: t and c are introduced but not used.
- Line 203 (and line 266 in the supplementary): “b* + =“.
- Lemma 4.4: c is defined by not used.
- Algorithm 4: “// Definition ??” and “problem (??)”.

Overall, I think that the contribution is significant enough to merit acceptance. 

**Post rebuttal update**
Thank you for the response. After reading the other reviews and the responses, I maintain my recommendation for acceptance. 
limitations_and_societal_impact: Yes
review_title: null

Meta-review: A solid progress in a well studied line of research
Decision: Accept (Poster)