Efficiently Learning One Hidden Layer ReLU Networks From Queries
Authors: Sitan Chen
Adam Klivans
Raghu Meka
Venue: NeurIPS 2021 Poster (2021)
Keywords: PAC learning
polynomial-time algorithms
neural networks
query learning
model extraction

Abstract: While the problem of PAC learning neural networks from samples has received considerable attention in recent years, in certain settings like model extraction attacks, it is reasonable to imagine having more than just the ability to observe random labeled examples. Motivated by this, we consider the following problem: given \emph{black-box query access} to a neural network $F$, recover $F$ up to some error. Formally, we show that if $F$ is an arbitrary one hidden layer neural network with ReLU activations, there is an algorithm with query complexity and runtime polynomial in all parameters which outputs a network $F’$ achieving low square loss relative to $F$ with respect to the Gaussian measure. While a number of works in the security literature have proposed and empirically demonstrated the effectiveness of certain algorithms for this problem, ours is to the best of our knowledge the first provable guarantee in this vein.

Efficiently Learning One Hidden Layer Neural Networks From Queries
Sitan Chen" sitanc@mit edu MIT
Adam R. Klivans klivans@cs <livans@cs.utexas utexas. ateexa.edu UT Austin
Raghu Meka* raghum@cs. ucla. iala... edu UCLA
Abstract
Model extraction attacks have renewed interest in the classic problem of learning neural networks from queries. This work gives the first polynomial-time algo- rithm for learning one hidden layer neural networks provided black-box access the network. Formally, we show that if F is arbitrary one hidden layer neural network with ReLU activations, there is an algorithm with query complexity and running time that is polynomial in all parameters that outputs network F" achiev- ing low square loss relative to with respect to the Gaussian measure. While a number of works in the security literature have proposed and empirically demon- strated the effectiveness of certain algorithms for this problem, ours the first with fully polynomial-time guarantees of efficiency for worst-case networks (in particular our algorithm succeeds in the overparameterized setting).
Introduction
The problem learning neural networks given random labeled examples continues to be a funda- mental algorithmic challenge in machine learning theory. There has been resurgence of interest in developing algorithms for learning one hidden layer neural networks, namely functions of the form F(x) = Σi= s (w;, . - bx) where w, E Rd. E {=1). 6, E R are the unknown parameters. Here consider the ubiquitous setting where is the ReLU activation, the input distribution on is Gaussian, and the goal is to output ReLU network F' with E[(F(z) - F' S
Despite much recent work this problem [JSA15, Z7,+ GKMI8, GLMI8, GKLWI8, ZYWG19, BJW19, DKKZ20, CKM20, LMZ20), obtaining a polynomial- time algorithm remains open. All known works take additional assumptions the unknown weights and coefficients or do not run in polynomial-time in all the important parameters. In fact, there are a number of lower bounds, both for restricted models of computation like correlational statistical queries [GGJ+20, 20, DKKZ20J as well as under various average-case assumptions [DV20, DV21J, that suggest that truly polynomial-
algorithm may be impossible to achieve.
In this work, we strengthen the learner by allowing it query access to the unknown network. That is, the learner may select an input of its choosing and receive the output value of the unknown network F(x). Our main result is the first polynomial-time time algorithm for learning one hidden layer ReLU networks with respect to Gaussian inputs when the learner is given query access:
Theorem 1.1. Let F(x) = Ei_ sto( (wi, x) -b:) with ||lill < R. 8; E {+1}, and < B. Given black-box access to F, there exists (randomized) algorithm that will output with probability least
"This work was supported in part by an NSF CAREER Award ICFF-145261 and NSF Large CCF-1565235. 'Supported by NSF awards AF-1909204, AF-1717896, and the NSF AI Institute for Foundations of Ma- chine Learning (IFML.. SSupoorted by NSF CAREER Award 1553605.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

1-8, 6, one hidden layer network F' such that E (((()) F((x)) S The algorithm has query complexity and running time that is polynomial in d, B, R, k. L/e,, and log(1/o).
In light of the aforementioned lower bounds [GGJ+20, 20, DKKZ20, DV20, DV21], Theorem 1.1 sug- gests there is separation between learning from random samples and learning from queries in the context of neural networks.
In addition to being naturally motivated challenge in computational learning theory, the question of learning neural networks from queries has also received strong interest from the security and privacy communities in light of so-called model extraction attacks [TJ* 16, MSDH19, PMG 17, JCB 20, RK20, JWZ20J. These attacks attempt to reverse-engineer neural networks found in publicly de- ployed real-world systems. Since the target network is publicly available, attacker therefore obtains black-box query access to the network - exactly the learning model we are working in. Of particular interest is the work of Carlini et al. [CJM20] (see also [JCB+20]), who gave several heuristics for learning deep neural networks given black-box access (they also empirically verified their results on networks trained on MNIST). Another relevant work is that of [MSDH19] which gave theoretical guarantees for the problem we study under quite strong separation/lineal indepen- dence assumptions on the weight vectors; in fact they are able to exactly recover the network, but in the absence of such strong assumptions this is impossible (see Section 1.2). Since these papers bear strong parallels with our techniques, in Section 1.2 we provide a more detailed description of why these approaches break down in our setting and highlight the subtleties that we address to achieve the guarantee of Theorem 1.1.
1.1 Our Approach
Here we describe our approach at a high level. Fix an unknown one hidden-layer network F(r) = 3: x) b.) with weight vectors w, RRd signs s; E {=1}. and bias terms 65 E R. Consider line L {zo + vJSER for 2o, v E Id and the restriction (lz(t) & F(zo + t. v) given
by
Flz(t) = Σ s,0 ((w,, mo) b, + t(ws, u)).
Note that as a univariate function, Flz (1) is a piecewise-linear function. We call point E R a critical point of Flz if the slope of the piccewise-linear function changes at Our starting point is that if we can identify the critical points of Fl.. then we can use estimates of the gradient of F those critical points estimate the weights of the hidden units in F. More concretely, suppose we have identified a critical point &; of Flz for a line L. Now, back in the d-dimensional space, if we look at a sufficiently small neighborhood of the point x' = zn + f. U, then the set of activated units around x' changes by exactly one (in fact, by this reasoning, for random L, F/z will have one unique critical point for each neuron in F. provided no two neurons are exact multiples of each other). We can exploit this to retrieve the w, 's and b,'s by finite differencing: for each such x', compute (F(x' + 6) F(x')/ [[]]] for several sufficiently small perturbations E Rd. and this will recover s,W;; (see Algorithm 2 and 4.9 below for the details). We can recover s,b; in a similar fashion (see Algorithm 1). We remark that the approach we have described appears to be quite similar to that of [CJM20, JCB* + 20, MSDH19].
However, the above description leaves out the following key interrelated challenges for getting prov- able guarantees for arbitrary networks:
1. How do we identify the critical points of Flr. for a given line L?
2. If make no assumptions on how well-separated the weight vectors are, is actually impossible to recover all of the weight vectors and biases in a bounded number of queries. Using the neurons that we do approximately recover, is it possible to piece them together to approximate F?
A rigorous solution to these issues turns out to be quite tricky and technically involved. For instance, what if some critical points are arbitrarily close to each other (imagine the piecewise linear func- tion being tiny peak of exponentially small in d width on the real line) on the line F).. In this case, identifying them would not be possible efficiently. We develop several structural results about cancellations in ReL.U networks (culminating in Lemma 3.9) that show that such a situation only

---

arises in degenerate cases where some sub-network of F contains cluster of many similar neurons (we formalize the notion of similarity in Definition 3.1). We show in Section 3 that much smaller networks can approximate these sub-networks, On the other hand, for pairs of neurons which are sufficiently far from each other, the critical points on a random line L will be well-separated.
With the structural results in hand, roughly speaking it suffices to identify one "representative" neu- ron for every cluster of similar neurons in F. To do this, we discretize L into intervals of equal length and look at differences between gradients/biases of F at the midpoints of these intervals. The key result leveraging our structural results is Theorem 4.8 which shows that the set of all such differ- ences comprises a rich enough collection of neurons that we can assemble some linear combination of them that approximates F. To find a suitable linear combination, we run linear regression on the features computed by these neurons (see Section 4.4).
1.2 Comparison to Previous Approaches
Our general approach of looking for critical lines along random restrictions of Fl is also the ap- proach taken in the empirical works of [CJM20, JCB 20] and in the theoretical work of [MSDH19], but we emphasize that there a variety of subtleties that arise because are interested in learning worst-case networks from queries. In contrast, the empirical works consider trained networks aris- ing in practice, while [MSDH19] makes strong assumption that the weight vectors w; are linearly independent and that they are angularly separated. Note that such assumptions cannot hold in the practically relevant setting where I' is overparameterized.
To give a sense for the issues that these existing techniques run up against when it comes to worst- case networks, imagine that the me--imensional piecewise linear function given by the restriction Flz were simply a "bump." that is, is zero over most of the line except in a small interval (a, a a +8. For instance, this would arise in the following example:
Example 1.2. Consider the one-dimennt minedmmesio one hidden layer network F R + R given by F(z) oe 1 a) + oz a- - 8) - (2x 2a - 8). This function looks like the zero function except over the interval (a, a + 83. where it looks like small "bump."
The proposal in the works mentioned above is to run a binary search to find a critical point. Namely, they initialize to some large enough interval [-T, 7] L and check whether the gradient at the left or right endpoint differs from the gradient at the midpoint mid = 0. If the former, then they restrict the search to [-r./mia] and recurse until they end up with a sufficiently small interval, at which point they return the midpoint of that interval as an approximation to critical point. The intuition is that n steps of binary search suffice to identify a critical point up to n bits of precision.*
It is clear, however, from the "bump" example that such a binary search procedure is doomed to fail: if the bump does not occur in the middle of the starting interval [-r, then the outset, we don't Ion't know which half to recurse on because the gradients at the endpoints and the gradient at the midpoint are all zero! Indeed, to locate the bump, is clear that we need query a number of points
which is at least inverse in the width of the bump to even find an input to the network with nonzero output.
We remark that this is in stark contrast to related active learning settings where the ability to query the function can sometimes yield exponential savings the dependence on 1/c (see e.g. [Han09])- Indeed, if we took the width of the bump to be of size poly(+) to make it e-far in square distance from the zero function, we would still need poly(1/e) rather than log(1/)), queries locate the bump and distinguish the funcction from the zero function.
The core reason binary search fails for arbitrary networks is that there can be many disjoint linear pieces of Fl which all have the same slope. Indeed, because the gradient of F at a given point is some linear combination of the weight vectors, if F is overparameterized so that there many linear dependencies among the weight vectors, it is not hard to design examples like Example 1.2 where there may be many repeated slopes on any given random restriction of F to line.
Apart from these technical issues that arise in the worst-case setting we consider and not in previous empirical or theoretical works on model extraction, we also emphasize that our results are the first
WWe remark that the refinement of binary search given in [CJM20, JCB for networks that arise in practice, but the issue that describe poses challenge for their technique well.
JCB+1C1 +20 can speed this up to O(1) steps
3

---

theoretical guarantees for learning general one hidden-layer ReLU networks with bias terms in any learning model, including PAC learning from samples. As will quickly become evident in the se- quel, biases introduce many technical hurdles in their own right. To our knowledge, the only other theoretical guarantees for learning networks with biases are the work of [JSA15] which considers certain activations with nonzero second/third-order derivatives, precluding the ReLU, and the recent work of [ATV21] which considers ReLU networks whose weight vectors are well-conditioned.
Remark 1.3. As discussed above, the "bump" construction in Example 1.2 shows that unlike in related active learning contexts, poly(1/c) dependence is necessary in our setting. In fact this example also tells us another somewhat counterintuitive fact about our setting. Naively, one might hope upgrade Theorem 1.1 by replacing the dependence on the scaling parameters R. B with one solely on the L2 norm of the function. To see why this is impossible, consider scaling the function in Example 1.2 by a factor of 5-1/2 to have unit L2 norm. To learn F, we have figure the location of the hump, but this requires 22 (6) queries, and ō can be taken to be arbitrarily small.
Limitations and Societal Impact The line of work learning neural networks from black-box access does pose a risk, for instance, that proprietary models offered via publicly-hosted APIs may be stolen by attackers who are only able interact with the models through queries. The attackers might then use the extracted parameters of the model to learn sensitive information about the data the model was trained on, or perhaps to construct adversarial examples. That being said, understanding why this query learning problem can be easy for theorists is the first step towards building provable safeguards ensure that hard for actual attackers. For instance, prove thformation-thcoretiic or computational hardness for such problems if appropriate levels and kinds of noise are injected into the responses to the queries. Furthermore, query complexity lower bounds can inform how many accesses an API should allow any given user.
conceivable that one can
2
Preliminaries
Notation We let gd-1 denote the unit sphere in Rd Let ej denote the j-th standard basis vector (u.e) in Rd. Given vectors u, v. let L(u, v) A arccos ||||||||||| Given a matrix M, let ||M and || denote the operator and Frobenius norms respectively. Given function à which is square- integrable with respect the Gaussian measure, we will use |[h]] to denote (z=A((oua)) [/(=))]1// Given a collection of indices S C Z, we say that i, E S are neighboring if there does not exist i <<&< < j for which E E S.
Definition 2.1. A neuron is pair (v,b) where E Rdd and b E R; it corresponds to the function x + ((v, x) - b), which we sometimes denote by ((v,,) -b..
Definition 2.2. Given a line L C Rdd parameterized by L = fro + t. vhER. and a function F: Rd - R, define the restriction of F to L. by (()(t) & F(Eo +t
Definition 2.3. Given a line L C. IRd and a restriction FlI of a piecewise linear function F; Rd E to that line, the critical points of F' are the points t which the slope of FlL changes.
We will need the following standard facts about the concentration of the norm and individual entries of Gaussian vector.
Fact 2.4. Given Gaussian vector h ~ NN, E), Pr where r is the rank of Σ.
[INI 2 O( (1lo/// + vlog(1/8))) s 6,
Fact 2.5. For covariance matrix Σ for all i E [m]] with probability at least 1 5. 5.
1R given h N), we have that |h/] x
O (VEr.
We will also need anti-connentration of the norm of a Gaussian vector and the individual entries of a random unit vector.
Lemma 2.6. There is an absolute constant C > 0 such that given any Gaussian vector h ~
Nu, Σ). Pr [IAi]] 2 / 21 -CV
Lemma 2.7. For random u E gd-1 Pr Pr|p0l <
5
200+0

---

3 ReLU Networks with Cancellations
In the following section we prove several general results about approximating one hidden-layer networks with many "similar" neurons by much smaller networks, deferring proofs to the supple- mentary material.
3.1 (A, aA) -looseessssss of Neurons
We first formalize notion of geodesic closeness between two neurons and record some useful properties. This notion is motivated by Lemma 4.4 where we study the critical points of random restrictions of one hidden-layer networks.
Definition 3.1. Given v. v' E R and b, H R, we say that (v,b) and (v', V) are (A, a,,a)-clos if the following two conditions are satisfied:
1. sin ((v, A
2. |ib' B'ul & a||e|||e||]
Note that this a measure of angular closeness between (v. b). (v',8) E Rd++1 For instance, if (v, b) (Dv", Xb*) and (v',b) b') (Xv", X for some (v" b²), then (v, b) and (v',b) are (0, 0)- close.
We first collect some elementary consequences of closeness. The following intuitively says that we scale two (A, a:) -ne-ooss to have similar norm, then their biases will be close.
Lemma 3.2. If (v, b) and (v', b') are (A, closse, and rr' w for v orthogonal to v', then 1/6 - - a x/]-
Note that when two neurons are (A, alloose their weight vectors are either extremely correlated or extremely anti-correlated. In fact, given a collection of neurons that are all pairwise close, they will exhibit the following "polarization" effect.
Lemma 3.3. Suppose < 22/2. If (V1,b1), bi)....... (uk. by) are all pairwise (A, a.)close for some
then there is partition [k] S₁ Li S2 for which (Vt, uz) 0 for any E S1,j E S1 and i S2.j E S2. and for which (V;, Uz) < for any E S1.j E S2 and E S2,j E St.
In the rest of the paper we will take A be small, so Lemma 3.3 will always apply. As such, will be useful to define the following terminology:
Definition 3.4. Given (V1, b,), (vR, bx) which are all pairwise-close, we will call the partition S1 S2 given in Lemma 3.3 the orientation induced by {(V,, b.)).
We note that (A, -llosennsssss satisfies the triangle inequality.
Lemma 3.5. If (u1, b2) and (22, by) are (A, cloose, and (vz, b2) and (va, by) are then (11, b1) and (Vz, by) are (A A' 2a + 2a/)- +2a))-close -close.
3.2 Merging Neurons
We prove that one hidden-layer network where all neurons are (A, ar)-oss to some neuron can be approximated by at most two neurons:
Lemma 3.6. [See supplementary material.] Given F(x) = Et= (wo( x) b.) for 8, E {+1} and (v*.b") E Rdd R for which (w;, bi) is a))lose to (v",b") b²) for all [k)), there exist coefficients at, a E IR for which
(F()) at o ((v" ,, x) - b²) - a-a Foll(- x) + +b))) < 0( +02))110011
E (O.A)
Furthermore, we have that
la |||0*|| |||00* < Σ || wwill
and
attb%,,aa <a Σ
Wwll + Σ bal.
5

---

Note that Lemma 3.6 requires the existence of neuron (v". b*) which is close to all neurons {(v,, h. In our algorithm, we will not have access to (v", b*) but rather to some linear combi- nation of the neurons (.), We show that provided this linear combination is not too small in norm, it will also be close to all the neurons {(0,, 6.)3.
Lemma 3.7. Suppose we have vectors U1..... Um, V² E RR biases bi...., bm b' E IR for which ev- ery (us, be) is (A, a.)-lloe to (v", b... Then for any 81,...., 8m. E {=1}, if we define - m i== 8:0;
and b Ex=1 8yb;, then (u, b) is (Am, o E, lelll//l//llte I/lell//oool .b)
This presents an issue however: what if the linear combination of neurons that we get access to in our eventual algorithm has small norm, in which case Lemma 3.7 is not helpful? It turns out this linear combination takes very specific form (see the vector in (I)), and argue that if it is indeed small, then the underlying network we are trying to approximate will be close to a linear function! Formally we show:
Lemma 3.8. Suppose b... bm) are pairwise (A,os)close, and let [m] Si U S2 denote the orientation induced by them (see Definition 3.4). Define B max;||6]|| and R &
max;||e/]| If signs 81,..., 8m E [ satisfy
Σ iES
8;09 Σ
swvill S (AR)//,
(I)
iES2
thenfor for the network F(x) - Ei 8:0 (Vis x) - b,)), there exists an affine linear function f(x) : Rd R for which
((a))-(xx)) (F()) S poly(k,, R) (a2 + 22/9)
(0.
where & a (w-, ,)- ba satisfies
|| $
and
|b*1 S Σ |bbll.
3.3 Putting Everything Together
Putting Lemmas 3.6, 3.7, and 3.8 together, we conclude that networks whose hidden units are pair- wise (A, aclloe can either be approximated by particular size-two network, or by some affine linear function:
Lemma 3.9. Suppose (vi, (ui,b))...., by.) are pairwise (A, ar)-close, and let [k] = Si U So denote the orientation induced by them (see Definition 3.4). Define 2 max,|[bil and 2 max,| ||:/]. Let , =11}.
Define F(x) E, (;o((vs, bb), 1² Eies, 8;U; Eies, 8.0 and b Eies, sibs Eies, stb,, At least one of the following holds:
1. There is affine linear function e 12d + foric 22/9).
which ||F poly(k, R, ()
2. There exist coefficients at a E for G(x) at "ato((u",x)) bb) a o((-u",x) b*) satisfies || - G|l² < poly(k, B) 2/5 a²a 4/99).
Proof. By assumption, every (us b)) is (A, -lllos to (V1, by). By Lemma 3.7 we get that for (u", b*) defined in the lemma statement, (v1, b1) (Ak, amR/ [mRR|ll""l)-ccoss clo- to (v*,b").
If |o0|| 2 (AR)2/9 then conclude that (0), bi) is (Ak, amA 2m/92/9900 2/9 to (v*, (b)) and by Lemma 3.6 we find that there is a choice of at a for which the function G defined in the lemma statement satisfies ||F - GIl2 & O 2/5 + a?m? A 4/9/14/9)) (note that we used || < E.loall < kR).
If ||0*|| < (AR)2/9, then by Lemma 3.8 we find that there is an affine linear E for which 1|F poly(k, R, B) 1/2 23/9).

---

4 Learning One Hidden Layer
In this section we give our algorithm for learning neural networks from queries. Throughout, we will suppose have black-box query access to some unknown one-hidden layer neural network
k
F(x)
8:0 (10r x) by);
where s; {+1), wa E Rd, bounds will be polynomial in these quantities, among others.
, b, E R. Define the quantities R a max;//u,]| and B & max;||b;l |b:l| our
4.1 Critical Points of One-Hidden Layer Networks
In this section, compute the critical points of restrictions of F and argue that they are far apart along random restrictions unless if the corresponding neurons were close to begin with (in the sense of Definition 3.1).
First, we formalize the notion of random restriction:
Definition 4.1. A Gaussian line L is random line in IRd formed as follows: sample To (O, and Haar-random Sd-1 and form the line L - {2o + t THEER.
Here we compute the critical points along restriction of F. Proposition 4.2. Given line L {rr t UJER, the restriction FlL(t) & F( + t. is given by
& (t) = Σ 8,0 ((w;, zo) - b; + t(ws,, u))
This function has critical points, namely t (wr for every i E [k:] (wi.e)
Proof. The critical points of Flg are precisely the points t which a neuron changes sign. So the erticial point associated to the i-th neuron is the for which (w,, - b; +tww;, e) = 0, from which the claim follows.
We can show that these critical points are not too large, unless the norm of the corresponding weight vector small. The reason for the latter caveat is that, e.g., if one took the one-dimensional neuron aeEz- b) for b fixed and - O, the at which it changes sign tends to oo).
Lemma 4.3. With probability at least 1 - 8 over the randomness of Gaussian line L, we have that |ta| S
A(Va+vlogl1 (o)(1/6)) l Vd Vlo((1/8) Vlog(k/8) for every critical point of F FlL-
wel
Fix separation parameter A >> 0 which we will tune in the sequel. We show that along Gaussian lines L., Fl, critical points are well-separated except for those corresponding to neurons which are (A, -ll-se
Lemma 4.4. There is an absolute constant c > 0 for which the following holds. Given Gaussian line L, with probability least 1- we have: for any pair of i. for which (wi, by) and (wy, (y)) are not
(A, cA (o//////(k///llk// the corresponding critical points are least Ω
A82
apart.
4.2 Line Search and Existence Theorem
At high level, algorithm works by searching along F Fl.. partitioning into small intervals, and computing differences between the gradients/biases The primary structural result must show is that there exists enough information in this set of differences to reconstruct F up to small error.
F at the midpoints of these intervals.
As will be working with partitions of lines, it will be convenient define the following notation:

---

Definition 4.5. Given line I. Rdd and finite interval I C RR corresponding segment I C I., let (T( denote the gradient of F at the midpoint of For mid E T. the midpoint of T, define (1( Flz(tmid) - (Fl (fmid) biid- Intuitively, this is the "y-intercept" of the linear piece of Flz that contains Eiid- When is clear from context, we will drop subseripts and denote these objects by (I) and b(I).
Definition 4.6. Given line L J.C. CCR. and length 8 > O, let {4, denote the critical points of Flr. and let G (s) S [b] (resp. GT (s)) denote the set of indices a S S for which t,t1 - t; 2 (resp.
t. 4-11 1 2 s). Let Gr,(r) Gī(r)
The following observation motivates Definition 4.6:
Observation 4.7. Given line L C RR,, let {4i} denote the critical points of FlL- Let I1..... Im be partition of some interval I into pieces of length r, and for i T let E(i) denote the index of the interval containing I. Then for any i E G(rr) (resp. i E G[((r)), I00)+1 is entirely contained within [4, li+1] (resp. Te(s)-1 is entirely contained within [4-1,4] (.). In particular, le(0)-1 and 1oaa+1 are linear pieces of Fl..
The following the main result of this section. At a high level, it says if partition random line in IEd into sufficiently small intervals and can compute the gradient of at the midpoint of each interval, then we can produce collection of neurons which can be used to approximate F.
Theorem 4.8. For any e, 8 > O, define
Ad2
r 0
(3)
h4 (vd+ vlog(k/0)
T - kr + k(Vd+ + (10g()))) + de (Vā+ /lg(118) Vlog(t/0)
(4)
8||ws|l
Partition the interval [] into intervals II,...,, Im of length r.
Let L be Gaussian line, and let S denote the set of all m(m 1) pairs (w, b) obtained by taking distinct i,j E [k] and forming (VL(I,) (I by (I.) bz(l))). There exist (=1]-valued coefficients (wES vector w", and b* R. for which
F
Σ awob o(ww,) :) (w" (w.
Set Ps.R,BLoog1//88 2/9
for R.. (1/g some absolute constant that is polynomially large in k, R, B, log((/)), Further- more, we have that
la
w|l
< RR
and
law,
S cAk? R (o////))))))))))))) kB
(5)
| S kR
and
b < kB
4.3 Gradient and Bias Oracles
It remains to implement oracles to compute by (T) and V VL for preseribed line L and interval I. is not clear how to do this for arbitrarily small intervals because for general networks there can be many arbitrarily close critical points, but we will only need do so for certain "nice" I suggested by Theorem 4.8.
To that end, first note that it is straightforward to form the quantities by (I) for intervals I entirely contained within linear pieces of F L: we formalize this in Algorithm
It remains to demonstrate how to construct V (.)... Intuitively one can accomplish this via "finite differencing." i.e. the gradient of a piecewise linear function F point x can be computed from queries by computing F(z+6)-F(z)) for several sufficiently small perturbations Rd and solving the linear system.
With priori precision estimates, we can similarly implement a gradient oracle, as formalized in Algorithm 2 and Lemma 4.9.

---

Algorithm 1: GETBIAS(L,
Input: Line C Rd, interval I = la, bj C Output: by (T) if 7 is entirely contained within linear piece of F
bmid +- midpoint of L.
yo (4
Flu(b) Flu(b)-Flas (o)
refurn you t mid
Algorithm GETGRADDENN((C,)) o)
Input: Rdd > 0 for which (6) holds
Output: VF(a) E RRd
for j E [d] do
Sample random unit vector 2; E gd-1
3
Uj - (F + (x2)) - F(x))/a.
LLtt w be the solution to the linear system ((w, = U/ he(d--
return w
Lemma 4.9. For any a > 0 and any x E Rdd for which
kw,, x) b, 2 al|wyll ll V E [A]]
GETGRADIENT(2, a) makes d queries F and outputs (z)
In order to use GETGRADIENT construct the vectors (I()). we require estimates for in Lemma 4.9. In the following lemma we show that with high probability over the randomness of L, an interval I completely lies within linear piece of Flz. then we can bound how small we must take to query the gradient of F at the midpoint of that interval. As is clear from the proof of Theorem 4.8 in the supplementary material, these are the only intervals that we need gradient and bias information from.
Lemma 4.10. Let be Gaussian line. With probability at least 1-ô ô over the randomness of L, the following holds: in the partition [- = -. in Theorem 4.8, for any It which entirely lies within a linear piece of Flz. GETGRADIENT(tmis a) correctly outputs V (IE).. where Imid the and
midpoint of the interval Ie C that corresponds to interval (where r defined in (3)).
S.r
4kv7++0kk (uv (lg(()/6)
Putting these ingredients together, we obtain the following algorithm, GETNEURONS for producing collection of neurons that be used approximate F.
We prove correctness of GETNEURONS in the following lemma:
Lemma 4.11. For any 5 > O, GETNEURONS(e, 8) makes poly(k, R, B, lo////olg////// queries and outputs a list S of pairs (w, b) for which there exist (+1]-valued coefficients ( (wo as well as a vector wi and scalar b" such that
F (w ,)) b*
Σ (w.b)ES
aw a(wu,)) - b) Sc.
4.4 Linear Regression Over ReLU Features
remains to show how combine the neurons produced by GETNEURONS to obtain a good ap- proximation to F. As Theorem 4.8 already ensures that some linear combination of them suffices, we can simply draw many samples (z, F(+)) for AO Id), form the feature vectors computed by the neurons output by GETNEURONS, and run linear regression on these feature vectors.
Formally, let S denote the set of pairs (w, b) guaranteed by Theorem 4.8. We will denote the w's by (w,) ) and the b's by (by). Consider the following distribution over feature vectors computed by the neurons in S:

---

Algorithm 3: GETNEURONS(E,
Input: Accuracy
confidence d 0
Output: List S of pairs (w, b) (see Theorem 4.8 for guarantee)
S 5++0) 0.
Sample Gaussian line L.
A +- B.gg(1 )8/2
// Theorem 4.8 // Lemma 4 10
6.r
a
4kvā-O (lggkkk))l)))))) (kg()
Define r, according to (3), (4).
Partition [-,, 7| into disjoint intervals ,,...., Im of length r.
for all j [ma] do
35 <- midpoint of the interval I C that corresponds to C R.
(r, t GETGRADIENT(2)... a).
10
(1,) + GETBIAS(L,
11
for all pairs of distinct i E [m] do
(v,, b,) + (VL(4)) -
-
12
if (Uj,bb satisfies the bounds in (5) then Add (1z,b) S.
14
15 return S.
Definition 4.12. Let D' denote the distribution over IR (||++++11 x RR of pairs (2,y) given by sampling NO, Id) and forming the vector 2 whose entries consist of all a ((ūr,z) by) as well as the entries of and the entry 1, and taking y to be F(z) for the ground truth network defined in (2).
We will also need to define a truncated version D':: let 'D denote conditioned on the norm of the [S] + to {S] d-th coordinates having norm at most M (1+tO( which happens with probability at least 1 5 over D
Our algorithm will be to sample sufficiently many pairs (2.y) y) from D' (by querying F on random Gaussian inputs) and ordinary least squares. This is outlined in LEARNFROMQUERING below.
Algorithm 4: LEARRFFROMQUEEIISSS 6)
Input: Accuracy
confidence 8>> 0
Output: One hidden-layer network F IRd + R for which ||F O(e)
S =(W + GETNEURONS(C, 5).
Draw samples (1..)),,... (Zn, Yn) from D
// Definition 4.12
Let T be the solution to the least-squares problem (7). Let denote the last entry of ह, and let w denote the vector given by the d entries of prior the last.
Form the network F(x) E3 ((0) x) - b,) + (w,
return F.
Formally, we show:
Theorem 4.13, Let S denote the list of pairs (w,.b,) output by GETNEURONS(e, 8). Sample (21, Vi)...., (Zn, from for n = poly(k. R. B, 1/c, log(1/6)). With probability at least O()) over the randomness of GETNECRONS and the samples, the following holds. Define
T 6 arg min
Σ E(1,22 y. W & VTTr k(R+
let denote the last entry of J. and let to denote the vector given by the d entries of ō prior to the last. Then the one hidden-layer network F(x) E, E,0 b,) (w. :) satisfies FF F < O(e).
10

---

References
[ATV2I] Pranjal Awasthi, Alex Tang, and Aravindan Vijayaraghavan. Efficient algorithms for learning 2epth-2 neural networks with general relu activations. arXiv preprint mxXiv21077.00209 2021.
[BJW19] Ainesh Bakshi, Rajesh Jayaram, and David P Woodruff. Learning two layer rectified neural networks in polynomial time. In Conference on Learning Theory, pages 195- 268. PMLR, 2019.
[CJM20] Nicholas Carlini, Matthew Jagielski, and llya Mironov. Cryptanalytic extraction of neu- ral network models. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology CRYPTO 2020 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, Part IIII, volume 12172 of Lecture Notes in Computer Science, pages 189-218. Springer, 2020.
[CKM20] Sitan Chen, Adam Klivans, and Raghu Meka. Learning deep relu networks is fixed parameter tractable, arXiv preprint arXiv:2009. 2020.
[DKKZ20] Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, and Nikos Zarifis. Algorithms and sq lower bounds for pac learning one-hidden-layer relu networks. In Conference on Learning Theory, pages 1514-1539, 2020.
[DV20] Amit Daniely and Gal Vardi. Hardness of learning neural networks with natural weights. arXiv preprint arXiv:2006.03117 2020.
[DV21] Amit Daniely and Gal Vardi. From local pseudorandom generators to hardness of learning. CORR, abs/2101.08300 2021.
[GGJ+20) Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. arXiv preprint arXiv:2006. 12011, 2020.
[GKLW18] Rong Ge, Rohith Kuditipudi, Zhize Li, and Xiang Wang. Learning two-layer neural networks with symmetric inputs. In International Conference on Learning Represen- tations, 2018.
[GKM18] Surbhi Goel, Adam R. Klivans, and Raghu Meka. Learning one convolutional layer with overlapping patches. In Jennifer G. Dy and Andreas Krause 0001, editors, JCML,, volume 80 of Proceedings of Machine Learning Research, pages 1778-1786. PMLR, 2018.
[GLMI8] Rong Ge, Jason D Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape design. In 6th International Conference on Learning Representations, ICLR 2018, 2018
[Han09] Steve Hanneke. Theoretical foundations of active learning. Carnegie Mellon Univer- sity, 2009.
[CB++00 Matthew Jagielski, Nicholas Carlini, David Berthelot, Alex Kurakin, and Nicolas Pa- pernot. High accuracy and high fidelity extraction of neural networks. In Srdjan Capkun and Franziska Roesner, editors, 29th USENIX Security Symposium, USENIX Security 2020, August 12-14, 2020, pages 1345-1362. USENIX Association, 2020.
[JSA15] Majid Janzamin, Hanie Sedghi, and Anima Anandkumar. Beating the perils of non- convexity: Guaranteed training of neural networks using tensor methods. arXiv, pages arXiv-1506, 2015.
[JW720] Rajesh Jayaram, David P. Woodruff, and Qiuyi Zhang. Span recovery for deep neural networks with applications to input obfuscation, 2020.
[LM720] Yuanzhi Li, Tengyu Ma, and Hongyang R. Zhang. Learning over-parametrized two- layer relu neural networks beyond ntk. CoRR, 0bs/2007.04596, 2020.
11

---

[MSDH19] Smitha Milli, Ludwig Schmidt, Anca D. Dragan, and Moritz Hardt. Model reconstruc- tion from model explanations. In FAT, pages 1-9. ACM, 2019.
[PMG 17] Nicolas Papernot, Patrick D. McDaniel, lan J. Goodfellow, Somesh Jha, Z. Berkay Ce- lik, and Ananthram Swami. Practical black-box attacks against machine learning. In Ramesh Karri, Ozgur Sinanoglu, Ahmad-Rez Sadeghi, and Xun Yi, editors, Proceed- ings of the 2017 ACM on Asia Conference on Computer and Communications Security, AsiaCCS 2017, Abu Dhabi, United Arab Emirates, April 2-6, 2017, pages 506-519. ACM, 2017.
[RK20] David Rolnick and Konrad P. Kording. Reverse-engineering deep relu networks. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 8178-8187. PMLR, 2020.
[6] Florian Tramèr, Fan Zhang 0022, Ari Juels, Michael K. Reiter, and Thomas Ristenpart. Stealing machine learning models via prediction apis. CoRR, abs/1 fess/609902943, 2016.
[ZSJ+ + 17] Kai Zhong, Zhao Song, Prateek Jain, Peter Bartlett, and Inderjit S Dhillon. Recovery guarantees for one one-hidden me-hidden-llaer neural networks. In Proceedings of the 34th Interna tional Conference on Machine Learning- Volume 70, pages
2017.
[ZYWG19] Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning one-hidden- layer relu networks via gradient descent. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3524-1534, PMLR, 2019.
12


Reviews:
[{"review_id": "vswlP5uxYi", "reviewer": "Reviewer_e3xE", "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. \n\nTheir 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$.", "questions": "", "limitations": "", "rating": 6, "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 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.\n\nThe 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.\n\nOther:\n1. $W$ changes to $R$ in the following sections.\n2. Instead of having bounds on the norm of the vectors and the parameters, wouldn't a bound on the $\\|F\\|_2$ norm suffice?\n3. Lemma 3.3 is difficult to parse.\n4. Line 203 $b^*+$ should be $b^*$\n5. I would suggest changing the structure of Theorem 4.8 to make it easier to parse.\n6. Algorithm 4 has broken references.\n7, Authors should clarify which of the previous work did parameter estimation vs function estimation.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work does not seem to have any negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "_eCO_CG38B3", "reviewer": "Reviewer_FZeD", "summary": "Present the first provably polynomial-time algorithm for learning unknown one-layer neural networks when given black-box access to the unknown network.", "questions": "", "limitations": "", "rating": 7, "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": "$\\textbf{Originality}$\n\nTo 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.\n\n$\\textbf{Quality}$\n\nThe theorems are clear and supported with sound proofs.\n\n$\\textbf{Clarity}$\n\nThe submission is clearly written and easy to follow.\n\n$\\textbf{Significance}$\n\nEfficiently 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "$\\textbf{Limitations}$\n\nThe 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.\n\n$\\textbf{Broader Impact}$\n\nThere 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.\n\n", "review_text": "", "extra_scores": {"ethical_concerns": "Yes, see $\\textbf{Broader Impact}$", "needs_ethics_review": "Yes", "ethics_review_area": ["Inappropriate Potential Applications & Impact  (e.g., human rights concerns)", "Responsible Research Practice (e.g., IRB, documentation, research ethics)"], "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "Ptu1rLv21wm", "reviewer": "Reviewer_ULd9", "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.\n\nThe 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.\n\nAt 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. ", "questions": "", "limitations": "", "rating": 8, "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": "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.\n\nThe 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. \n\nFinally, the paper could greatly benefit from an experimental section that implements the algorithm and evaluates it on synthetic and real-world data.\n\nMinor comments:\n- l.27-30: Please add the distributional assumption in the theorem statement\n- l.46-48: Please define x_0 and v (\\in \\R^d)\n\nSuggestions:\n- 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\n- l.124-125: N(0,I_d) perhaps add that this is WLOG, as we can centre + normalize the training data\n- 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 \n- 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 \n- Lemma 3.8: perhaps define B and R before \"If signs s_1,...\"\n- 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)?\n\nTypos:\n- l.143: \"the supplement\" -> \"the supplementary material\"\n- l. 169: \"satisfies triangle inequality\" -> \"satisfies the triangle inequality\"\n- l.203 typo \"+\" in the definition of b^*? \n- l.289: \"several sufficiently small\" -> \"for several sufficiently small\"\n- l.306: \"we prove correctness\" -> \"we prove the correctness\"\n- Algorithm 4: Definition and LS problem references are \"??\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "MKFwAtfaim4", "reviewer": "Reviewer_zwJ7", "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. \n\nThe 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.\n", "questions": "", "limitations": "", "rating": 7, "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 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.\n\nThe 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.\n\nExample 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.\n\nIn 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).\n\nLemma 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?\n\nSection 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*.\n\nMore comments:\n- Lemma 2.6: There exists C s.t. for every \\nu …\n- Lemma 2.7: t and c are introduced but not used.\n- Line 203 (and line 266 in the supplementary): “b* + =“.\n- Lemma 4.4: c is defined by not used.\n- Algorithm 4: “// Definition ??” and “problem (??)”.\n\nOverall, I think that the contribution is significant enough to merit acceptance. \n\n**Post rebuttal update**\nThank you for the response. After reading the other reviews and the responses, I maintain my recommendation for acceptance. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

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