An Exact Poly-Time Membership-Queries Algorithm for Extracting a Three-Layer ReLU Network
Authors: Amit Daniely
Elad Granot
Venue: ICLR 2023 poster (2023)
Keywords: Learning With Queries
ReLU Networks
Model Extraction

Abstract: We consider the natural problem of learning a ReLU network from queries, which was recently remotivated by model extraction attacks. In this work, we present a polynomial-time algorithm that can learn a depth-two ReLU network from queries under mild general position assumptions. We also present a polynomial-time algorithm that, under mild general position assumptions, can learn a rich class of depth-three ReLU networks from queries. For instance, it can learn most networks where the number of first layer neurons is smaller than the dimension and the number of second layer neurons.

These two results substantially improve state-of-the-art: Until our work, polynomial-time algorithms were only shown to learn from queries depth-two networks under the assumption that either the underlying distribution is Gaussian (Chen et al. (2021)) or that the weights matrix rows are linearly independent (Milli et al. (2019)). For depth three or more, there were no known poly-time results.

Published as a conference paper at ICLR 2023
AN EXACT POLY-TIME MEMBERSHIP-QUERES AL- GORITHM FOR EXTRACTING A THREE-LAYER RELU NETWORK
Amit Daniely
School of Computer Science and Engineering, The Hebrew University and Google Research Tel-Aviv Menieeyymai yêmai
ami dan el
huj ac.i.ac.il
Elad Granot
School of Computer Science and Engineering, The Hebrew University elad. grwnotrattt..mmooooooooooo.o.. @mail. huji aaaa....... ac..cc..
ABSTRACT
We consider the natural problem of learning a ReLU network from queries, which recently remotivated by model extraction attacks. In this work, present polynomial-time algorithm that can learn a depth-two ReLU network from queries under mild general position assumptions. We also present polynomial-time al- gorithm that, under mild general position assumptions, can learn a rich class depth-three ReLU networks from queries. For instance, it can learn most net- works where the number of first layer neurons is smaller than the dimension and the number of second layer neurons.
These two results substantially improve state-of-the-art. Until our work, polynomial-time algorithms were only shown learn from queries depth-two networks under the assumption that either the underlying distribution is Gaussian (Chen et al. (202T)) or that the weights matrix rows are linearly independent (Milli et al. (2019) For depth three or more, there were no known poly-time results.
INTRODUCTION
With the growth of neural-network-batee applications, many commercial companies offer machine learning services, allowing public use of trained networks black-box. Those networks allow the user to query the model and, in some cases, return the exact output of the network to allow the users to reason about the model's output. Yet, the parameters of the model and its architecture are considered the companies' intellectual property, and they do not often wish to reveal it. More- over, sometimes the training phase uses sensitive data, and as demonstrated /Zhang et al. (2220). inversion attacks can expose those sensitive data to one who has the trained model.
Nevertheless, the model still vulnerable membership query attacks even as a black box. recent line of works (Tramer al. (2016), (Shi et al. (2017), Milli et al. (2019), |Rolnick & Körding (2020). Carlini et al. (2020). Fornasier et al. (2021) ) showed either empirically or theoretically that using reconstruct some hidden models. Thcoretical work includes Chen ctt al. (2021) that proposed a novel algorithm that, under the Gaussian distribution, can approximate two-layer model with ReLU activation in guaranteed polynomial time and query complexity without any further assumptions on the parameters. Likewise, Milli et al. (2019) has shown how to exactly extract the parameters of depth-two networks, assuming that the weight matrix has indepen- dent rows (in particular, the number of neurons is at most the input dimension). Our work extends their work by showing:
specific set of queries,
1. A polynomial time and query complexity algorithm for exact reconstruction of a two-layer neural network with any number of hidden neurons, under mild general position assump- tions; and

---

Published as a conference paper at ICLR 2023
2. A polynomial time and query complexity algorithm for exact reconstruction of three- layer neural network under mild general position assumptions, with the additional as- sumptions that the number of first layer neurons is smaller than the imput dimension and the assumption that the second layer has non-zero partial derivatives. The last assumption is valid for most networks with more second layer neurons than first layer neurons.
The mild general position assumptions are further explained in section 3.3 However, we note that the proposed algorithm will work any two-layer neural network except for a set with zero Lebesgue measure. Furthermore, will work in polynomial time provided that the input weights are slightly perturbed (for instance, each weight is perturbed by adding uniform number in 1 4) At a very high level, the basis of our approach is to find points in which the linearity of the network breaks and extract neurons by recovering the affine transformations computed by the network near these points. This approach was taken by the previous theoretical papers Milli et al. (2019; Chen et al. (222)) and also in the empirical works of Carlini et al. (2020); Jagielski et al. 2019). In order to derive our results, we add several ideas to the existing techniques, including ability to distinguish first from second layer neurons, which allows us to deal with three-layer networks, as well as the ability to reconstruct the neurons correctly in general depth-two networks with any finite width in a polynomial time, without assuming that the rows are independent.
RESULTS
We next describe our results. Our results will assume general position assumption quantified by a parameter E (0, 1), and a network that satisfies our assumption with parameter 5 will be called 8 5-regular. This assumption is defined in section (3.3. We note, however, that slight perturbation of the network weights, say, adding to each weight a uniform number in [-2-4, 2 2-1), guarantees that w.p. 1 2-2 the network will be ò-regular with ō that large enough to guarantee polynomial time complexity. Thus, 6-regularity is argued to be mild general position assumption. Throughout the paper, we denote by Q the time takes to make single query.
2.1 DEPTH TWO NETWORKS
Consider 2-layer network model given by
M(x)
Σ u (w,, x) + bj)
(I)
where ((x)= x = max (z. 0) is the ReLU function, and for any j [d1], wy E R by E R, and " E R. We assume that the wy 's, the bj's 's and the uy's, along with the width d1, are unknown to the user, which has only black box access to M(x),, for any x E Rdd We do not make any further assumptions on the network weights, rather than ō-regularity.
Theorem 1. There an algorithm that given an oracle access to a 8-regular network as in equa- tion reconstructs it using O ((d2 (og(1/5) + dzd) Q + ddd:) time and O (d1 log(1 (188) + d,d) queries.
We note that by reconstruction we mean that the algorithm will find d' and weights wh...., ... w'g E
Rd, by.... 1/ E R, and uh...., u'z E IR such that
Ya E ERR, M(x) (wb. x)) + b/ Σ ugjo ((w), + b3)
We will also prove a similar result for the case that the algorithm is allowed to query the network just on points in R4. but the other hand, equation equation 2 needs to be satisfied just for e RQ. This case essential for reconstructing depth-three networks, and we will call it the R4 -esttiiiete case.
Theorem 2. In the Re, restrictdd case there is algorithu that given oracle access 8- reconstructs it using O ((ddz (1/8) + d,d) Q + d& time
regular network as in equation [ and O (dd, log(1/8) + d) queries.
2

---

Published as a conference paper at ICLR 2023
2.2
DEPTH THREE NETWORKS
Consider a 3-layer network given by
M(x) = (u, ((Voo(VVWaa +b)
where W& E Rd xd, b E R4, V E Rdaaxd, c Rd, u E Rd and Φ is the ReLU function defined wlse We assume W. V, u, b, e, along with d1 and d2, unknown to the user, which have only black box access to M(r) for any a E R Besides 8-regularity we will assume that (i) dj I d and that (ii) the top layer has non-zero partial derivatives: For the second layer function F: IR R given by F(x)= (u, (VV c)) we assume that for any æ E R and j E [di], the derivative of F in the direction of eهك) and e()) not zero. We note that d2 large compared to d1 (d2 > 3.5d, would be enough) this assumption is valid for most choices of u, V and (see theorem 5
Theorem There is an algorithm that given an oracle access a ô-regular network as in equation 2 with d, < d and top layer with non-zero partial derivatives, reconstruct it using poly(d, d1, d2, log(1/)) time and queries.
By reconstruction we mean that the algorithm will find d', d2 E N. weights oy...., E Ri, co...., ca E RR ui...., u/ag E R. as well as a matrix W' E R4 xd and a vector d' E R such that
Vx Rd, M(x) = (o/ & (W'x + 6 ugo ((o),
tg)
2.3 NOVELTY OF THE RECONSTRUCTIONS
Having an exact reconstruction is an essential task for extracting a model. While approximate re- constructions, such as in Chen et al. (202T), may mimic the output of the extracted network, they cannot reveal information on the architecture, like the network's width. Moreover, an approximated reconstruction can be viewed as regression task. For example, the work of Shi et al. (2017) used Naive Bayes and SVM models to predict the network's output. An exact reconstruction requires building new tools, as we provide in this work.
Exploring the non-linearity parts of a network can offer information on the relations between the weights of neuron up to multiplicative factor. Specifically, the sign of neuron is missing. Indeed: for the j th neuron both (w,, by) and (-w,, -b,) have the property of breaking the linearity of M(x)) the same values of To achieve the global signs of all the neurons, one requires either to restrict the width of the network (as in Milli et al.] (2019) or to use brute-force over all possible combinations (as in Carlini al. 2020) and Rolnick & Körding (2020)). We bypass this challenge by allowing reconstruction up to an affine transformation and using the fact that for all æ E Rd.
(w. .)) b o (ww æ)) + b) o(- (w. .)) b).
This bypass allows the reconstruction of a network with any finite width in a polynomial time.
Another technical novelty of the paper is algorithm that can identify whether a neuron belongs to the first or the second layer. This allows us to handle a second hidden layer after peeling the first layer.
3 PROOFS
3.1 NOTATIONS AND TERMINOLOGGY
We denote by e!)) (........ e (d) the standard basis of Rd and by B(x, d) the open ball around x E Rd Idd and R denote by Aw,b the affine function Aw,,s = yef || yl the
with radius 8 O. For
(w, æ²) + b. For point E Rd and set A C IRd distance between x and A. Given subspace P,, A Gaussian in P is Gaussian vector in Rd whose density function is supported in P. We say that it is standard if the projection of x on any line in that passes through E E[x] has variance of 1.
denote by d(æ,
3

---

Published as a conference paper at ICLR 2023
(x)
critical hyperplane
X 8-critical point
x 8-general point
X
Figure illustration one-dimensional piecewise linear function M - RR.
The state of negative, or zero). The state of a network on a point a E IRd a description of the states of all neurons æ. Similarly, the state of the first layer at æ E Rd is description of the state of all first layer neurons at æ.
point Rd is the sign of the input of that neuron (either positive,
The angle between a hyperplane P with normal vector and line {ta: + y E RR (or just vector * 0) is defined as 2 12) Likewise, the distance between two hyperplanes P1,P²
with normal vectors n2 respectively, is given by P(F == / ) We say that hyperplane is 5-general if its angle with all the d axes is at least 5. A hyperplane is general if it is ò-general for some > 0 (equivalently, it not parallel to any axis).
3.2 PIRCEWISE LINEAR FUNCTIONS
Let f R + R be piecewise linear, with finitely many pieces. A general point is a point æ E Rd such that exists a neighborhood around æ for which f affine in that neighborhood. Furthermore, we say that the point a E Rd is a d-general point if f is affine in B(x,, 8). Complementarily, critical point is point a E Rdd such that for every > 0, an affine hyperplane P. whose intersection with the set of critical points is of dimension d 1. For a critical hyperplane P. we say that point a e Rd is PP-critical if critical and x P. Figure 3.2 illustrates the above definitions for the one-dimensional input case.
not affine in (a 8). A critical hyperplane
Note that there are finitely many critical hyperplanes for any piecewise linear function, that any eritical point belongs to at least critical hyperplane, and eriticciaiaa points belong to exactly one critical hyperplane. We will call such points non-degenerate. Furthermore, we will say that critical point is --non-degenerate if exactly one critical hyperplane intersects with (xx,
For the function M computed by network such as equation or equation 3 we note that for any j E [d1], the hyperplane F, = {æ (w,, x) + by 0} is a critical hyperplane. In this case, say that P corresponds to the jith neuron, and vice-verse. Also, if æ is critical point, then at least one of the neurons is in critical state (i.e., its input 0). In this case, we will say that æ is critical point of that neuron.
We next describe few simple algorithms related to piecewise linear functions that we will use frequently. Their correctness is given in section D of the appendix; here we briefly sketch the idea behind it.
3.2.1 RECONSTRUCTION OF AN AFFINE FUNCTION
We note that if æ is e-general point of function f, then one can reconstruct the affine function f computes over B2x é) with queries in ((x,e) and (dQ) time. Algorithm reconstructs the desired affine function.
By most, all except whose dimension is d
4

---

Published as a conference paper at ICLR 2023
3.2.2 RECONSTRUCTION OF CRITICAL POINTS IN ONE DIMENSION
We say that a piecewise linear one dimensional function f R + I is ò-nice if: (1) All its critical points are in (- 2) (-6, 6), (2) each piece is of length at least 6, (3) there are no two pieces that
share the same affine function, and (4) all the points in the grid 2-[leea(2/62) Z are -g-eneral..
Given a S-nice function, algorithm recovers the left-most critical point in the range (a, 1/6), if such point exist, using O (1og(1/88) ()) time. In short, the algorithm works similar binary search, where each iteration splits the current range into two halves and keeps the left half if and only if affine.
Algorithm FIND (6, a): Single critical point reconstruction
Input: Parameter 8 < 1, black box access ó-nice f - IR, and left limit a E (-3
Output: The left most critical point of f in (a, 1/8).
Set F 3. R =
2: for .....: [log (2/62)
3: If #2+0R < or AFFINE, z1) AFFINE,: (f. (2+2R) set ZL 22+2R Else, set
RR = 214TR
4: end for
5: Let AL AFFINE,> (f, xL) and AR = 3FFINE,2 (f, Af = Ar then return "no critical points in (a, 1/5)". Else, return the point for which Ar (1 (n(
With algorithm we can reconstruct all the critical points of f in a given range (a, C (-1/8, in O (k log[1/6 (1/)) time, where k is the number of critical points in (a, b). Indeed, algorithm to find the left-most critical point Iı in (a, 6), then the one on its right and so until there are no more critical points in (a, b).
invoke
3.2.3 RECONSTRUCTION OF A CRITICAL HYPERPLANE
Let Rd IR be piecewise linear function. Assume that is ô-non-degenerate P-eritical point. 1 22 E (ax, 5) are two points on opposite sides of P. then IP is the null space of A - -A2, where AI, Ag are the affine functions computed by near x; and Ø2. Algorithm therefore reconstructs P in (dQ) time.
3.2.4 CHECKING CONVEXITY/CONCANITY IN A Ó-NON-DEGENERATE CRITICAL POINT
Let f: Rd + R be piecewise linear function. Assume that x a non-degenerate P-critical point. As P is the intersection of exactly two affine functions, then f necessarily convex concave in B(x, 5). Furthermore, for any unit vector e that is not paralle to IP, we have that f is convex in (x 8) if and only if is convex in [x òe, æ + de), in which case the slope of f + f(æ + te) in [-ô, 0j is strictly smaller then its slope in [0, 6]. Algorithm 4 therefore determine if convex or concave in ((x, )) in O(Q) time.
3.2.5 DISTINGUISH 6 G-ENEERL POINT FROM C-NON-DEGENERATT CRITICAL POINT
Let f R R be piecewise linear function. Assume that is either -egen-degenerate P-eritical point or an e-general point. Then by the definitions, for any unit vector e that is not parallel to TP. is critical if and only if the slope of f(x 1e) is different in the segments [-c, 0] and [0, c)- Algorithm therefore determine if æ is critical in (()) time.
3.3 GENERAL POSITION ASSUMPTION
We say that a two-layers network as in equation T is 5-regular the conditions for the inputs of algorithms 2 are met for the network and for any critical point that lies on the standard axes. For a three-layer network, as in equation? 3 we also require that the above apply to the sub-network defined by the top two layers. A two- and three-layers network is called regular if it is 8-regular
By parallel we that the vector orthogonal the hyperplane's normal.

---

Published as a conference paper at ICLR 2023
Algorithm 2 AFFINE, (f,
Algorithm 4 IS CONVEX Óf
Affine map reconstruction from e-general point
Checking convexity/concavity
Input: Black box access to a piecewise linear f:R" R² + R, parameter e > 0, and an e-general point E Rd
Input: Black box access piecewise linear f
Rd - R. parameter > 0, a d-non-degenerate P-critical point æ E R for general P
Output: Vector w E R and b E R such that Vy B(xr,), (w)) f(y)
Output: Is æ convex in f at ((x,
f(=+-)()))-((a)) f(x)
1: Return Wi- = ) and (f(z) - Ed Ziml f(xtcel))) ((()))(()))))))
then
Return "convex"
3: else
Return "coneave"
Algorithm FIND
FIND_HP(IF HP (f, 8,
5: end if
Reconstruction of a critical hyperplane
Algorithm 5 IS GENERAL(f,
Input: Black box access to piecewise linear f: R, a parameter å > O, a ô-non-degenerate
_d_ -
Distinguish general point from critical point
P-critical point
Id for 5-general IP Output: w E Rd and E such that P = fx
Input: Black box access to piecewise linear f Rd R, parameter e >> 0, point æ that
Aw.b(a:) = 0}
is either e-general e-non-degenerate P-critical point for general P Output: Is x general?
1: Set = (6/2)²
2: Using algorithm
2 obtain (Wi, b1)
1: f( = f(x)
AFFINE, (J, x 2) and (wz,
then
AFFINE, (J, x ()
2: Return "general", else return "critical" end if
3:
Return w W1 W2 and b bj by
for some 8 0. A network is in general position if it is regular, and for three-layer networks, as equation 3 we also require to be surjective and that the top-layer will not have zero partial derivatives. A formal definition for 8-regular network is given in section A of the appendix. Here we want to state sufficient conditions that ensure the regularity and general position of network. The proofs are given in section A of the appendix.
Lemma 1. The set of non-regular neural networks as equation 7 and equation have a zero Lebesgue measure.
Let M be neural network as in equation ! or equation 3 Let q be the number of neurons in the network, and let M be an upper bound on the absolute value of the weights. For each weight in the network, add uniform element in 1-2-4, 4.2-4.. Then, the noisy network M' is 8-regular for >> such that log(1/5) = poly MM)) with probability of 1 -2
Lemma 2.
Lemma 3. For general three-layers network as in equation 3 if S d then W is surjective with probability 1.
Lemma 4. For general three-layers network as in equation non-zero partial derivatives with probubility 1 -o(1).
3.5d S d2 then the top layer has
We note that the assumptions in section A may seem lengthy. The keen reader may notice overlaps between some of them and might suggest approaches to avoid others, for example, by adding ran- domization to the queries. Yet, we keep them is for the fluency of reading, to emphasize the main concepts of the extraction. As training a network in practice begins from a random initialization, very likely for the network be found in regular position after the learning phase. Therefore, we took the freedom to ignore unlikely positions instead of combining them under a very restrictive rule.
3.4 RECONSTRUCTION OF DEPTH Two NETWORK SKETCH PROOF OF MIIEOREMSAAMT
Recall that our goal is to recover depth-two network in the form of equation equation We will assume without loss of generality that the u. is's are in (+1), as any neuron + uo((w, .)) calculates the same function æ + -u d([/u/w x) + (u(6), as ReLU is positive homogeneous function.

---

Published as a conference paper at ICLR 2023
Our algorithm will first find critical point for each neuron. For regular network, each critical hyperplane intersects the axis Re()) exactly once, so we can reconstruct such set of critical points by invoking algorithm on the function ł + M(te!!))
We next reconstruct single neuron corresponding to given critical point æ. For simplicity, assume that æ is a 8-critical point of the j'th neuron. Using algorithm B we find an affine function A such that A Aw, by A bb, Then, to recover uj, note that if u, 1 then M(x) is strictly convex in (a, 5) as the function ny (wD, at) + b2) is convex. Similarly, if uj -1 then M(rr) is strictly concave in (ax,0 5). Thus, we recover uy using using algorithm
Finally, note that (()())) is either (((w; æ) + bj) or Φ0 (wrg. æ) + b2) (w,, σ)) - by- Hence. u,)(A(z)) equals to u, (Arr,,), by (æ)) up to an affine map. The approach is detailed in Algorithm
Algorithm 6 Recover depth-two network
Input: Parameter 5 and black box access to 6-regular network M as in equation I
Output: Weights such that for all æ; M(x) = Aoj (2x) + Ex= u/ (Awt, (a))
1: Use repeatedly FIND 1DDDDCP(dA)) (C, + M(te(")),) -) to find all the critical points on the axis {te(
E [R} (see section 3.2 Denote these points by 21...., Rm.
2: for i. = 1, 1...... do
3: Compute (w', b8) = FIND FIND_HP (MM, x.).).
4: If IS CONVEX(M. 6, x:)) "convex" then set ul = 1. Else, set u/ --1. -1
5: end for
6: Cale (w') 16) = AFFINE, (ær - M(xx) Ei
C uno of xx) for random x' e Rd.
7: Return the function x ++ Awg. / (x) EE 1/ (Ano (2)).
The following theorem proves the correctness of algorithm 6 and implies theorem I The proof is given in section of the appendix. Theorem 4. Algorithm 0
reconstruct a 8-regular network in time O ((log(1/6) + d)d, + dd,.).
3.4.1 SKETCH PROOF OF THEOREM 2
Our algorithm for reconstruction of depth-two networks can be easily modified to work in the R4- restricted setting, with the difference that order to reconstruct a 8-critical point for each neuron (step algorithm 6). we will need to search in the range (o. }) e( for all i E [d]. as a critical hyperplane of given neuron might not intersect with e Because of this change, each neuron might be discovered several times (up to times), and we will need an additional step that combines neurons with the same affine map (up to sign). For the particular case where the neuron has no critical points on the positive orthant, one can ignore it without affecting equation equation 2 for all [
These changes will result in a total runtime of O(dd, log(1/6)Q) instead of Odd log(1/6))) for step 1, O(dd, Q) instead of Oddd, Q) for the loop, and Odfdd" ) for combining similar neurons. The total runtime will therefore be ((log(1/5) + dddd, Q + ddd)). formal proof given in section B of the appendix.
3.5 RECONSTRUCTION DEPTH THREE NETWORK SKETCH PROOF OF THEOREM
Recall that our goal is to recover 8-regular network of the form
M(x) (u, o V VW æ + 6) + c)).
We denote by w, the jth row of W and assume without loss of generality that it is of unit norm, as any neuron of the form æ + ((w + b) can be replaced by + ||w|| (
40 Th | +
6
Likewise, and similar to our algorithm for reconstruction of depth-two networks, we will assume that d2
The algorithm will be decomposed into four steps described the following four subsections. In the first step, will extract set of critical hyperplanes that contains all the critical hyperplanes

---

Published as a conference paper at ICLR 2023
that correspond to first layer neuron. In the second step, will prune this list and will be left with a list that contains precisely the critical hyperplanes that correspond to a first layer neuron. In the third step, we will use this list to recover the first layer. Once the first layer is recovered, as the fourth step, we recover the second layer via a reduction to the problem of recovering a depth-two network.
3.5.1 EXTRACTING A SET CONTAINING THE CRITICAL HYPERPLANES OF THE FIRST LAYER
For the first step, we find a list = (301, PI), (20m; Pm)) of pairs such that:
For each k, Pa is critical hyperplane of M and is ò-non-degenerate critical point whose critical hyperplane is IPx
The list contains all the critical hyperplanes of first-layer neurons
We find those points using Algorithm 3 Note that m = (di1d) (e.g. Telgarsky (2016)) Let
Pi....,IP.. fP. be the critical hyperplanes corresponding to these points, found using Algorithm Finally, lemma below, together with 6-regularity implies that every hyperplane that corresponds to first layer neuron intersects ( exactly once, and this intersection point is 6-non-degenerate
P-critical point.
3.5.2 IDENTIFYING FIRST LAYER CRITICAL HYPERPLANES
The next step is take the list I, = { (a), (zm: P Pm)} from the previous step, verify all the planes corresponding to first-layer neurons and remove all the other hyperplanes. The idea behind this verification is simple: If IP corresponds to neuron in the first layer then any point in P is critical point of .M (see lemma 8). On the other hand, if IP corresponds to neuron in the second layer, then not all its points are critical for .M. Moreover, intersections with hyperplanes from the first layer change the input for the second layer neurons, hence creating new piece that replaces P.. Thus, in order to verify IP corresponds to first layer neuron, we will go over all the hyperplanes Ps E L, and for each of them, will find a point x' E IP that is the opposite side of I& (relative to x) and will check if it is critical. If it is not critical for one of the hyperplanes, not correspond to a first layer neuron. If all the points that we have examined are critical, even for Ps corresponded to a first layer neuron, then w' is critical, which means that IP must correspond to first layer neuron.
know that I' does
Algorithm 7 implements this idea. There is one caveat that we need to handle: The examined point has to be generic enough in order to test whether it is critical or not using algorithm [5] To make sure that the point is general enough, we slightly perturb it. The correctness of the algorithm follows from lemmas TO and beloo.. Due to the perturbations, the algorithm has success probability of
at least 1 2 over the choice of x' for each hyperplane and at least 2-d for all hyperplanes. Each step in the for-loop takes (dd) operations. As the list size is ((1 the total running time over all hyperplanes is O ddh.d.)).
3.5.3 IDENTIFYING DIRECTIONS
Since the rows in W are assumed to have a unit norm, the list the critical hyperplanes of the first-layer neurons, obtained in the previous step, determines the weights up to sign. In order to recover the correct sign of (t²; b1), we can simply do the following test: Choose point æ such that wiæ+ b, 0, and query the network in the points x + ez, x cz, for small c, where e Rd is unit vector that has the property that is orthogonal to iz LD but i0 z > 0. If we assume that W is right invertible, then such a exists, as wT, Wd, are linearly independent.
Let (a) be the output of the first layer given some point then:
(wi1, x + 6z) by (W2, x + Ez) + b2
(w1, x)) (w2, x)
(w1, (2)
+b2
+b2
out(æ + Ex)=
=ou((2) + +e(wi, 2) e1))
(pa x + 62) bag
(wa, m))
+ +ba,
8

---

Published as a conference paper at ICLR 2023
Algorithm 7 Identifying whether a critical hyperplane corresponds to the first layer
Input: A Black box access to a ò-regular network MM. as in equation 3 list L
(x), (Zm:Pm)) of pairs described in section 3.5.1 and pair (æ, P) L Output: Does P correspond to a first layer neuron?
1: Choose 8' small enough such that 22(d) (2) 6'v2
2-
m
2: Choose R > 0 large enough such that e
3: for any k E [m]] such that P. * TP do
4: Choose point E P such that z and are separated by PR. and d(z,P) >
5: Choose standard Gaussian Z in P whose mean is z
6: IS [S_GEMERAL(MM, 8', 2), return "P is not a first-layer critical hyperplane"
7: end for
8: Return "P a first-layer critical hyperplanc"
Therefore, when moving from æ to either + 62 or x: cz, only the first neuron changes, and after the ReLU activation function, only the positive direction will return a different value. Hence, in order to have the correct sign can do the following: If M(x) + M(x + ez) then keep (w),,
Else, replace with (-w1, -.). We repeat this method for all the neurons j E [d1].
The above method fails in the special case where both V Volou(( + + S 0 and V Voloul(æ <z)) < O, which occur if the partial derivatives of the top-layer are zero at o(x + ez) and Φ(x - cz). As we showed on section 3.3 this is not expected the second layer is wide enough.
The runtime of this step is Oddd Q) to find z need to do Gram-Schmidt, which takes (dfd), and additional two queries to find the sign.
3.5.4 RECONSTRUCTION OF THE TOP TWO LAYERS
After having the weights of the first layer at hand, and since W assumed to be right invertible, we can directly access the sub-network defined by the top two layers. Namely, given æ E IR4, we can find z E gd such that
x (ø [w b..)..... (wa, + ba,))
e.g., by taking W- b) where W-1 is right inverse of W. Now, .M22) is precisely the value of the top layer on the input æ, and the problem boils down to the problem of reconstructing depth two network the R restricted case, which already solved.
Now, the cost of a query to the second layer Q plus the cost of computing 2, which is O(d,) )
There is also an asymptotically negligible cost of (dfdd) for computing W-1, 1. The runtime of this step is therefore O(llog(1/5) + dijdids dQ + dd1) + dzd)).
4 DISCUSSION AND SOCIAL IMPACT
This work continues set of empirical and theoretical results, showing that extracting a ReLU net- work given membership queries possible. Here we prove that two- and three-layer model extrac- tion can be done in polynomial time. Our nonrestrictive assumptions make it feasible to construct fully connected network, a convolutional network, and many other architectures.
For practical use, our approach suffers several limitations. First, two- and three-layer networks are too shallow practice. Second, exact access the black-box network may not be feasible prac- tice. As the number of output bits is bounded, numerical inaccuracies may affect the reconstruction, especially when d is very small. that regard, our work is mostly theoretical in nature, showing that reconstruction is provably achievable.
Yet, this work raises practical social concerns regarding the potential risks of cembershipp-ueeiae attacks. Extracting the exact parameters and architecture will allow attackers to reveal proprictary information and even construct adversarial examples. Therefore, uncovering those risks and creating conversation ways protect against them essential.

---

Published as a conference paper at ICLR 2023
As empirical evidence shows, believe it is possible to prove similar results with even fewer assumptions for deeper models and more complex architectures. Furthermore, might be interesting to investigate the methods of this paper when restrict the queries and the outputs up machine precision. We leave those challenges for future works.
ACKNOWLEDGMENTS
This research supported by ISF grant 2258/19, and ERC grant 101041711
REFERENCES
M. Anthony and P. Bartlet. Neural Network Learning: Theoretical Foundations. Cambridge Uni- versity Press, 1999.
Nicholas Carlini, Matthew Jagielski, and Ilya Mironov. Cryptanalytic extraction of neural net- work models. In Lecture Notes in Computer Science, volume 12172 LNCS, pp. 189-218, 2020. ISBN 9783030568764. doi:
URL http::/arxiv.cr
abs/2000 04884
Sitan Chen, Adam R Klivans, and Raghu Meka. Efficiently Learning Any One Hidden Layer ReLU Network From Queries. In NeurIPS, 2021.
Massimo Fornasier, Timo Klock, and Michael Rauchensteiner. Robust and Resource- Efficcient Iden- tification of Two Hidden Layer Neural Networks. Constructive Approxittion,,,,,, 2021. ISSN 0176- 4276. doi: 10. (007/50033650021-955550
URL hRl.httt:://axxi..crrre 9907. 00485
Matthew Jagielski, Nicholas Carlini, David Berthelot, Alex Kurakin, and Nicolas Papernot. High Accuracy and High Fidelity Extraction of Neural Networks. 2019. URL http:://axiv.
orq/abs/1900 1909, 01838
Smitha Milli, Ludwig Schmidt, Anca D. Dragan, and Moritz Hardt. Model Reconstruction from Model Explanations. Proceedings of the Conference on Fairness, Accountability, and Trans- parency FAT* '19, pp. 1-9, New York, New York, USA, jul 2019. ACM Press. ISBN URL htt.:: http://wwwwv.rraa/////aaa/////// 051 05185http://dl acm. http:://w.....aooo....ttataaaaa/ http:///wwaa...ooooaa.ooooooooaa 3267662
9781450361255, doi: 10. 10.1145/328755002227555
David Rolnick and Konrad Körding. Reverse-engineering deep relu networks. In 37th Interna- tional Conference Machine Learning, ICMI, 2020, volume PartF16814, pp. 8148-8157, oct 2020. ISBN 9781713821 Utt.htttpp//arx....rro/////
00744
Yi Shi, Yalin Sagduyu, and Alexander Grushin. How to steal machine learning classifier with deep learning. 2017 IEEE International Symposium on Technologies for Homeland Security, HST 2017, 2017. doi:
Matus Telgarsky. benefits of depth in neural networks. In Conference Learning Theory, pp- 1517-1539, 2016.
Florian Tramer, Fan Zhang, Ari Juels, Michael K. Reiter, and Thomas Ristenpart. Stealing Machine Learning Models via Prediction APIs. USENIX Security Symposium, 2016. ISSN 00414131. URL attpss://www usenix http://wwww....eoooooooooaee/aaa techni ca sessi
Yuheng Zhang, Ruoxi Jia, Hengzhi Pei, Wenxiao Wang, Bo Bi, and Dawn Song. The secret revealer:
Generative model-inversion attacks against deep neural networks. Proceedings of the IEEE Com- puter Society Conference Computer Vision and Puttern Recognition, pp. 250-258, nov 2020. ISSN 10636919. doi: 10.11999CVP442200.222000000
URL http: /tt::////xxvvvia/ wwtpxiiiorrg/bs...oo
1911.00 07135
10

---

Published as a conference paper at ICLR 2023
A REGULAR NETWORKS
Definition 1. A neural network is called 8-regular if satisfies the following requirements:
1. For each E [d]. the piecewise linear function t +> MMtell) is ò-nice as defined in section
3.2.2
2. Any critical point in the axes (tel : R is 5-non-degenerate
3. Each critical hyperplane corresponds single neuron.
4. The distance between each pair of critical hyperplanes least
5. The angle between any critical hyperplane and an axis is at least 5. Lee, all critical hyper- planes are ö- ö-general.
6. Each critical hyperplane IP corresponding to second layer neuron also corresponds to a single first layer state. That is, the state of the first layer is the same for any P-critical point.
7. In the case of depth-three networks, we assume that the above conditions also apply to the sub-network defined by the top two layers.
While the definition above is lengthy, most of the requirements overlap, and we detailed them sep- arately for ease of analysis. The following lemma shows that a regular network expected from random network. As untrained network begins from random initialization, it is very likely to be found in some random position after the learning phase. However, we note that some post- processing methods, like weights-pruning, may affect the general position assumption; such cases should be given specific care and are not in the scope of this paper.
Lemma 5. Let & be the set of networks as in equation 1 and equation 3 that violate at least one of the above:
1. For each [d], the piecewise linear function & M(te is nice.
2. Any critical point in the axes (te( t R] is non-degenerate.
3. Each critical hyperplane corresponds single neuron.
4. The distance between each pair of critical hyperplanes non-zero.
5. All critical hyperplanes are general.
6. Each non-zero critical hyperplane P corresponding to second layer neuron also corre- sponds to a single first layer state.
7. In the case of depth-three networks, we assume that the above conditions also apply to the sub-network defined by the top two layers.
Then S has zero Lebesgue measure.
Proof. It is enough to show that each the above has a zero measure, as a finite sum of sets with zero measure has zero measure.
The demand of a specific point æ E Rdd to be critical requires some critical hyperplane P such that P.. This imposes linear constraint the set of all such possible hyperplanes and reduces their degree of freedom. Any subspace with dimension < d has zero Lebesgue measure in Rd which
Remember that we assign (non-degenerate) critical point to neuron if value at that neuron, before the ReLU function, is 0. A point æ corresponds to the ith neuron in the first layer if (w. x) + b. O, and corresponds the jthh neuron in the second layer if (ei, 6(Wa + b)) + Cj = 0. A critical hyperplane corresponds some neuron if there is non-empty open set g C TP where each E S corresponds to that

---

Published as a conference paper at ICLR 2023
is also the case of all the possible hyperplanes containing æ. As corollary, the set of hyperplanes that contains the points of (1 E has also zero measure, 2 is sparse in R.
6
As another corollary, once fixing a plane P., the set of planes collides with exactly on the i'th axis, i [d]. is of zero measure well, which is the case where critical point on one of the axes to be degenerate. Even a more degenerate case is where two neurons have the same hyperplane, which means both neurons have exactly the same parameters up to factor. Obviously, this case has zero measure in IR which implies that with probability 1, a finite set of hyperplanes have a non-zero distance between each other. If we consider the points on the i'th axis, { E IR (az, e - -}. as hyperplane itself, then it is easy to see that non con-general hyperplane also has zero measure.
For a one-dimensional function to be nice, one must require that no two pieces share the same affine function. For functions of t + M(tel()), there are no two neurons whose i'th parameters are the same. Indeed, the opposite case, where two neurons share the exact same parameters, has a zero measure in IR.
As for depth-three networks, all the above is valid for the sub-network defined by the top layer. Moreover, we can consider the first-layer state as an affine transformation for the second layer's neurons. Therefore, in order for second-layer critical hyperplane IP to span two first-layer states, there must be two second-layer neurons that have the same parameters up to an affine transformation whose uniquely defined by the parameters of the first layer. As the set of all those affine transforma- tions is finite, this imposes a finite set of possible constraints, and each has a zero measure.
The following two lemmas state the effect of a small perturbation over 5.
Lemma 6. Let M be a two-layers neural network as in equation 7 Let q be the number of neurons in the network, and let M be an upper bound on the absolute value of the weights. For each weight in the network, add a uniform element in [-2-d, 2 2-4,, and denote the the noisy network by M'. Then:
1. For each i E [d], all critical points of the piecewise linear function M(tell) are in (-) \ (-6,8) with probability 1 pi = dyō(M 1)2d-1
2. For each i [d]. each piece in the piecewise linear function + M(te()) of length at least N with probability 1 - = =1 d2d 926(M + 1).
3. For each i E [d], all the points in the grid 2 2-1022(218211 5
Z of the piecewise linear function
t + M(tell) are 52---nneee -eneral with probability 1 - Ps = 1 -ddg..
4. Any critical point in the axes (te() :t E is 5-non-degenerate with probability 1 - P4 =
1 - (2 + 1)2d-1
5. The distance between each pair of critical hyperplanes is at least 8 with probability 1-p5 (M + 122d++1
1 Vdd(
6. The angle between any critical hyperplane and any axis is at least 8 with probability P6 = 1 - -dg2d
Proof. Let the ith axis to be {te(() :t E RR. Denote by Wyys as the ith element of wy and by Wh, Wyss + Ij,s to be the noisy value of Wyss where Ij,s U([22-1, 222 2 2-).. Similarly, let
by = b, + sy to be the noisy value of bj. where sy ~ U([-2-1 2 2-d)). Then the jth neuron has critical point on the ith axis when (e()) = (0) where Ij.a =
by Note that from lemma 5 we
have almost surely that oo < 44,4 < 20.
1. For each E [d] and j E (4). note that w S M + 2- < M + 1. Given a E (0, 2-), we have that:
P([W/d > a) 2 > a)
a 2-d
=
12

---

Published as a conference paper at ICLR 2023
Now, with probability a22+1 we have that both by setting 6(M + 1):
|Wyal
and |bţ] a, and therefore,
by
M +
1 6"
8 M+1 +1
5,d
W',
To make the above valid for every i e [d] and [q]. use the union bound to get
an overall probability - P1 where:
p S dgood+1= = d + 1)22+1
2. Assume the weights were perturbed in the following order: First, W is perturbed. Sec- ond, the bias of the first neuron, b1, is defined, which sets its critical points with the axes,
I..1..... : Ltdd As for the second neuron, we can ask what is the probability for b2 to have critical point that is 8-close to critical point of the first neuron. That is, for some E [d].
(- b2 b2 (1,,--8,1, + +6)
p (12,s B(l,,,,)) =
W2.1
(12 E (-W2, + b2, (1,, 8) 9bb))
s dw, S 2d (MM +1)
and using the union bound,
p (3i [d]. l2 E B( 8)) S d2 + +).
Now, let us continue with the perturbation, and for the jth neuron, that the probability to intersect with any of the balls with radius 8 around l1,4...., 4-1. i E [d], is at most
(j 1)d248(M 1).
Finally, the probability that all the pieces for all [d] are of length least is p2 with:
Σ - 12-2) + +1 - d2 + 1).
P2
j=2
3. Fix W and some [d]. Note that for the jth neuron, 4 is uniform in As L bounded, intersects with the grid at most 2 2
by-2 2 b +2
[2|6
Myss
times. Therefore, for all the points in the grid to be -g-geneall, means that segment of length 25 should not contain critical point. As t,, is uniform, the probability of avoid- ing that segment is therefore:
28 [
1 [og (2/6")1 1 36
where the last inequality follows for 8 <
Overall, we get that the points in the grid are -2-general with probability 1 1 -P3. where
Ps = 3dgö.
4. Let IPj the critical hyperplane defined by the jth neuron. The distance between P3 and critical point (0)) & +
(w (0)) + bbyz
[c., + by + +sy
D(P,, 4..)
|wyll
Vd(M +1)
As Sj is symmetric that (R,, by + s;
distribution around 0, we have with probability > |syl and with probability 1 a2d-1 have that
13

---

Published as a conference paper at ICLR 2023
If wet Svd(M + 1) then using the union bound W by + sj |sy) we get:
(3i E [d],] $ k. s.t. D(P,, 4.) 50 = dg² 1 2
s PMM
p4-
Note that if e is far from every other critical hyperplane with at least 8, then it is ô-non-degenerate. Therefore, all the critical points on the axes are ò-non-degenerate with probability 1 P4-
5. For any unit vector e we have that at least one of the coordinates of absolute value at least 1/vd. Thus, p ((w', e) 5'
2nd 2-4
8' and (w, e)² S ||
12 (1n, e²)² <
Va vi
5'2-d ||/|1 Va w.p. at least 1 8'. It follows that (w.e)) TwI
5'2-1
8'2-
I 1
S 1 v Vdd(M+13
Vdll
w.p. least 1 8'. Taking roots get that least - 8', the distance is least
8'2-d
Hence, w.p.
Thee
M+
8"2-d
8'2
2v
2 2V
Hence, we get for each pair of critical hyperplanes a distance of at least w.p. 1 - p5
1 Vdd + 1)22d+1
6. The angle between the jth neuron and the axis {te(() : IR. equals to e())
w- The probability for this to be at least 8 is
p( yul 5) 2 p((ryal 8) =
2-d
Using the union bound, we have that the probability for each neuron and each axis to have angle of at least ô is 1 pc, where ps dqø2d.
Lemma 7. Let M be three-layers neural network in equation 3 Let be the number of neurons in the network, and let M be an upper bound on the absolute value of the weights. For each weight in the network, add a uniform element [-2 2 2-4), and denote the the noisy network by M'. Then:
1. For each i E [d], all critical points of the piecewise linear function + M(le!)) are in (-) ( (-8,8) with probability 1- 8dM8 + 2222++1
2. For each i [d], each piece the piecewise linear function + M(te(1) is of length at least 8 with probability P2 11 d2d 5(dM2 1222222 +2)
3. For each i E [d], all the points in the grid 2 2- E of the piecewise linear function 8
M(tte() are 82 --nnerral with probability 1 Ps 1 - 3dq² 8.
4. Any critical point in the axes (te()) :t R) is S-non-deegeenee with probability 1 P4
1 2/1ggt 'ddM2 + 2)
5. The distance between each pair of critical hyperplanes is at least with probability 1-ps
1 8g* Vdd(dM2 2dd+1
6. The angle between any critical hyperplane and any axis is at least 8 with probability
= 1 1-d1-g2200 dg2 82
7. In the case of depth-three networks, assume that the above conditions also apply the sub-network defined by the top two layers with probability 1 - P7 where p7 is the sum of the probabilities of lemma
14

---

Published as a conference paper at ICLR 2023
Proof. Lemma tells us that each non-zero critical hyperplane P corresponding second layer neuron also corresponds to a single first layer state almost surely. Therefore, given E [d]. we can consider the q' critical points that intersect with the ith axis q' first-layer neurons, where each second neuron is multiplied by an affine transformation that is the current state of the first neurons. As each first layer neuron intersects with the axis most once, and each second layer neuron intersects with the axis at most 91 times, where 91 is the number of first layer neurons, we can bound o' by q' S q².
Furthermore, given critical hyperplane P corresponding to a second layer neuron j. denote by (W', by)) the state of that first layer (which is the same as (W', b') as defined in the proof of Lemma 6 except to some zero rows due to ReLU), That is, P = {o (wy. Wax) + (ey. bς) + Cj = 0} which can be viewed locally as pscudo-neuron with parameters ((W))*
( Uy +(, bp) + o2) that
are each bounded in magnitude by M' I dM² + 1.
1. Applying the above to lemma 6 we get:
P1 S dg' (MM + 1)24+1 s dg2 + 2)2a+1
2. Applying the above to lemma we get:
P2 S d2 d2 8(M + +1) S 48dM2 + +2).
3. Applying the above to 6 we get:
Ps S 3dg's d S 3dd2
4. Applying the above to lemma 6 we get:
p4 d 2 8(M' 1)2 < d
a(dM 2 + g/
2)2
5. Note that the maximal possible number of critical hyperplanes is at most h q², in- teractions between each first-layer neuron and a second-layer neuron may cause a single hyperplane. Therefore, get:
Ps = 5122 V dd(M'' + + S <0g*V Vdd(dd + 2)
6. Applying the above to lemma 6 we get:
p6 S dg' 82 < d
7. Let Pl, Pa. Po, Ps as defined on lemma 6 As the number of neurons in the second layer is at most q, using the union bound we get: p7 Ei=1 Pt.
In the rest of the section, we prove lemmas stated in section 3.3
Proof. (of lemma I The proof follow from lemma the number of critical hyperplanes is finite.
5 and the fact that the number of neurons - henne,,
Proof. (of lemma 2 From lemma 1 we have that the perturbed network M' is regular almost surely. This implies that it 8-regular for some 8 > 0, As the number of neurons finite.
Fix a 8 > 0. For two-layer networks, lemma 6 bounds the probability to dispose one of the restric- tions of ő-regular network. Let pi,... Ps as in lemma then, using the union bound, we get that the network is 5-regular with probability of at least P where
Pi p2 + pa + p4 + P5 + Ps
dgd(M 1)2 d2 90 1) + 3dqō
+ ((M + -1)2 _d² 2 ddd(M + 1 ddg2d
<00 + 1)3
15

---

Published as a conference paper at ICLR 2023
Therefore, if we choose ó (10(M d) will get the requested bound.
For three-layer networks, let PI..... Pr as in lemma then, using the union bound, we get that the network is ö-regular with probability of least 1 where
p' = P2 +
dg + +2' + 2) + 2 2)20-1 54 Vd'Vdd + 2] + do 02 + 10(M + 1)2"2"
20(dM + +)) 2/2
Therefore, if we set = (20(dM² + 2 we will get the requested bound.
Proof. (of lemma Let W Rdidd random matrix, where each element is drawn independent of the other, and define by w, its j'th row, j E [d]. Also, let r min [d, d1}. Note that W has full rank with probability 1, where by full rank we mean that rank (W) = min d1, d1} = r. Indeed, consider drawing at random the jth row, for j S r after fixing the first 1 rows. In order of that row to be dependent in Wi.... w then w, must fall in subspace whose dimension is at most j 3 r, which has zero Lebesgue measure in r-dimensional space.
Therefore, if d1 I then r = d1 and has a rank dj with probabilty 1. The Rank nullity theorem then implies that the image of W is d1 didmeesiionnll space, and thus W is surjective.
Proof. (of lemma 4 The proof follows from Theorem 5 If we set 3.5d d2 get probability of:
+1
ed2
(3.5e) d1+1
3.5e
di d0000 1.
3.5e
2d
23.5d,
23.5
B PROOF OF THE MAIN THEOREMS
Proof. (of theorem below.
The correctness of the theorem follows from the correctness of theorem
Proof. (of theorem 4 We will assume without loss of generality that the u, 's are in {+1}, as any neuron + uo(((u (w, x) + b) calculates the same function a positive homogeneous function.
1 (ww//, æ) + lu(b). ReLU
Let S = (xI,..., } be the list of points found using FIND CP in algorithm 6 Our general assumption is that all the critical points on the line (Re(1) are on the range (- +) (1)) Hence, from the correctness of lemma 13 we guarantees that all the critical points on the line (e( are in S. We claim that for each æ E there is exactly one critical hyperplane P with x E P. and Assume by contradiction that one of the above is false. If & TP for all the critical hyperplanes, then æ is not a critical point, which contradicts lemma 13 If [ n PP = 0 this means that P does not intersect with e assumption. Finally, [S o IP| > this means that intersects with (1)), which means IP is not affine. Therefore, each neuron is represented by unique critical point E S.
e!)) i.e., parallel to this axis, which contradict our general position
Let æ be a critical point of the j'th neuron, and (w', ( FIND_HP(A) 8, a). From lemma 14 get that either (w,.b;) (w', ./) or (w', 6') (-w', bb)). To recover Uj. note that if uy then M(x) is strictly convex in (Bx,8) 8) the function ( æ) + b,). Similarly, if uty = -1 then M(x) is strictly concave in B(x, 5). Thus, using algorithm 4 will be able determine uy correctly.
of the affine function Mz and the convex
16

---

Published as a conference paper at ICLR 2023
Let C C [d1] be the set of neurons assigned to an incorrect sign. Then, for all R
df
M(x) Σ 2 (1o) x) + b,) = Σ
njd ((wy, x) + bb)) - uz ((w0; x) - bj)
jEC
=>
" ((ung x) + bz)
jEC
which is an affine transformation and can be recovered successfully at the last stage of the algorithm.
As for the time and query complexity, step I takes O (d1 log(1/6)Q) (see section 3.2). Since each neuron correspond to single critical point, we have that m d1. Thus the loop in step 2 makes d1 iterations. The cost of each iteration is O(dQ). Hence, the total cost of the loop is O(didQ). Finally, to perform step 6 we need to make d queries to M which cost O(d)), and also d evaluations of Ei= uá ( which cost djd each. The total runtime therefore O (d1 log(1/6)Q + didQ + dQ + ddd)= =0 (d1 log(1/6) + di d1dQ + ded1).
L
Proof. (of theorem
Denote the output of the j'th neuron before the activation by M,( =
wzz 1x2+b. by.
Let 1 22 E RQ be two points such that exactly neuron E [d,] changed its state (i.e. changed from active to inactive, or vice versa) in the segment [a),, x22 := {Aar + (1 - A) : À E [0, I]].
Moreover, assume that neuron changes its state in neighborhoods of æ and 222 so that the change in the state happens in the interior of [21. We note that finding such a pair of points ø 22 can be done by considering a ray {(p) := pe()), and seeking a critical point á of the (one dimensional) function N L. Under our general position assumptions, for some j E [d]. there is such p in IR, and it can be found efficiently. Given such a p. and again under our general position assumptions, we can take 2 E(p E) and x2 = t(p e), for small enough c.
We will explain next how given such two points, we can reconstruct the j'th neuron, to an affine function. First, the reconstruction of uj simple. Indeed, in the segment [2], M'(x) b,) is affine, as no neuron, except the j'th neuron, changes its mode. Hence, M(x) = u,,(( x + b,) + M'(x:) a sum of an affine function and the j thth neuron. In particular, it is convex iff the j 'th neuron is convex iff u, = 1. Hence, reconstruct ūj only need to check the restriction of N to Ø2] is convex or concave.
M(x) - u wzæ u
We next explain how to reconstruct an affine map A such that ((A(z)) (M))()) is affine.Let A1,4, Rdd + I be the affine maps computed by the networks in the neighborhoods of a and 22 respectively. Note that it is straight forward to reconstruct A, from the set ((xx),M(a) + ee1).... M(r; + rea), for small enough e. We have that A == A1 Ag is either N, or -N,- Hence, we have that ((A()) is either (xM) or ((-M)(x)) = ((M((z) M2(x).
After removing all the neurons, are left with affine map that can be reconstructed easily using (d) queries as explained above, and the full reconstruction of the network is complete.
Proof. (of theorem 3) Recall that our goal is to recover a 8-regular network of the form
M(x) (u, o (Vo(Wa> + b) + c))-
We denote by w, the jth row of W and assume without loss of generality that it is of unit norm, as any neuron of the form æ + (((w,x)) x)) + b) can be replaced by + ||w]| | (( [ + |
6
Likewise, and similar to our algorithm for reconstruction of depth-two networks, we will assume that {=1]d>.
The first step of the algorithm would be to find a list
I. = { (mn, Pi),... (mm pmn)
of pairs such that
17

---

Published as a conference paper at ICLR 2023
For each k, P& is critical hyperplane of M and 24 is ó-non-degenere critical point whose critical hyperplane is Ik
The list contains all the critical hyperplanes of first-layer neurons
For that we will use repeatedly FIND_CP(O, + M(tell)),)) to find all the critical points on the axis {te("); t E }R (see section 3.2). similar to our algorithm for reconstructing depth two networks. Denote those set of points by assumption, guarantee that for each critical hyperplane IP that corresponds to first-layer neuron, [PP S||| = 1, and that all the points in S are --non-degenerate. Then, using algorithm 3 we will find the critical hyperplane P& for each point æy; E S.
{æ1,..., Fm) Lemma 13 along with the general position
For the runtime, note that m (2) (e.g. Telgarsky (0016), the critical points can be found in time O (d1 log(1 ()) as explained in section 3.2.2 and each hyperplane iP can be efficiently
found via (d) queries near æ; as explained in section 3.2.3 The total running time of this step is therefore O (d d2 log log(1/ + di d2dQ)).
The second step is to take the list L (30), II), Pi)..... (2m. Pm)) and remove all the points that don't correspond first-layer neurons. After that, the list will contain precisely the critical hyper- planes of the neurons in the first layer. In order to do so, it is enough to efficiently decide, given the list L, whether a given hyperplane IP is critical hyperplane of neuron in the first layer. The idea behind this verification is simple: If P corresponds to a neuron in the first layer then any point in F a critical point of M (see lemma 8). Indeed, suppose that P is critical at IP for a first layer neuron h(x) = of wx + b). We have that I is the null space of the affine input to h in the proximity of P. But the input to h the same affine function in the proximity of every point E Rd Thus, for every E I&d is a critical point for h with P as its critical hyperplane. On the other hand, if TP corresponds to a neuron the second layer, then not all its points are critical for M: Indeed, suppose that we start from x E IP, which is critical for M and start to move inside IP until one of the neurons in the first layer changes its state. Then we will reach a point in x' E P. which is not critical for M, as, by our general position assumption, IP corresponds to a single first layer state. Thus, in order to verify if P corresponds to first layer neuron, we will go over all the hyperplanes PR E L,, and for each of them, will find a point x' IP that is the opposite side of P& (relative to æ) and will check if is critical. If it is not critical for one of the hyperplanes, we know that P does not correspond to a first layer neuron. If all the points that we have examined are critical, even for P. corresponding to a first layer neuron, then x' critical, which means that TP must correspond a first layer neuron.
Algorithm| 7 implements this idea. There is one caveat that we need to handle: The examined point has to be generic enough in order to test whether is critical or not using algorithm [5] To make sure that the point is general enough, we slightly perturb it. The correctness of the algorithm follows from lemmas 10 and II Indeed, if P corresponds to a first layer neuron, then lemma I0 implies all the
that each test in the for loop will fail w.p. at least 1 m² Thus, w.p. at least 1 - tests will fail, and the algorithm will reach step 8 and will correctly output that "P is a first-layer critical hyperplane." In the case that P corresponds to second layer neuron, lemma [I implies that once we will reach an iteration in which P& corresponds to a first layer neuron, the test in step 6 will succeed w.p at least critical hyperplane." All in all, it follows that the algorithm will output the correct output w.p. at least 1 m for every hyperplane P. Thus, w.p. least 1 2-d it will output the correct answer for all hyperplanes.
2-d
2nd m., in which case the algorithm will correctly output "P is not a first-layer
As for runtime, note that each step in the for-loop takes OdQ).. As the list size is Odd12)), the total running time over all hyperplanes is O(ddddQ)
Since the rows in W are assumed to have unit norm, the list of the critical hyperplanes of the first-layer neurons, obtained in the previous step, determines the weights up to sign. Namely, we can reconstruct list
L = = (101, by)................. (w.a, bar))
18

---

Published as a conference paper at ICLR 2023
that define precisely the neurons on the first layer, up sign. For the third step, it, therefore, remains to recover the correct signs (note that this process is only required for inner layers and avoidable for the top layer, explained above).
In order to recover the correct sign of (ui1,
simply do the following test: Choose point such that ih æ + b = 0, and query the network in the points x + <2, x <z, for small 6, where E Rd is unit vector that has the property that is orthogonal to ubz ........ Wt, but uh 2 >> 0. If we assume that W is right invertible, then such a exists, as w1,. Wd, are linearly independent.
Now, when moving from x to either + cz or a cz, the value of all the neurons in the first layer, possibly except the one that corresponds to (w01, b1), does not change. As for the neuron that corresponds to (t,) b1), if its real weights are indeed (w,1, b1). then its value changes when we move from æ to æ + ez but not when we move from æ to æ ez. On the other hand, if its real weights are (-w1, -b1). then the value changes when we move from x to ez but not when we move from æ to x + ez. Hence, in order to have the correct sign we can do the following: If .M(x) j MMx + Ez) then keep (wi,, b1). Else, replace it with (-wi, -b1). This test works because of the above discussion, together with the assumption that the second layer has non-zero partial derivatives; therefore, we can guarantee that either æ +
will show change in the values of M. More on the non-zero partial derivatives assumption, see section E
The runtime of this step is Odfdd + d)Q). Indeed, to find x, need to do Gram-Schmidt, which takes ddf After that, all that is needed is two queries. We need to do this for each first layer neuron, the total runtime is Oddd d,Q).
For the fourth step, we shall recover the values of the top layer up to an affine transformation. After having the weights of the first layer hand, and since W is assumed to be right invertible, we can directly access the sub-network defined by the top two layers. Namely, given Rdd can find RRd such that
x (Ø (w + bi.,..... (wr, 2 + ba,)) W W-'(x
e.g., by taking the value of the top layer on the input æ. Hence, the problem of reconstructing the top two layers boils down to the problem of reconstructing depth two network in the -restriccte case, which its correctness is given in theorem 2
b) where W-1 is right inverse of W. Now, M(z) is precisely
The cost of query to the second layer is Q plus the cost of computing x. which is O(d1). There also an asymptotically negligible cost of (dddd) for computing W The runtime of this step is therefore O((log(1/0 (1)) di dQ + dd1) d)))).
C PROOFS OF LEMMAS
Lemma 8. Let IP be a critical hyperplane corresponding to a first layer neuron. Then, any point in P is critical for M.
Proof. W.l.o.g. P corresponns to the neuron o(w + b)). Let æ5 E IP and let e be unit vector that is orthogonal to W2,.... Wd, and such that (w1, e) > 0. Such e exists as we assume that Wi...., Ws, are independent.
Consider the function f(t) = MMx0 + te). We claim that is not linear in any neighborhood of 0, which implies that 2o is critical. Indeed, for all > 1, + ó(w,(xn + te) + 6,) is constant, as e is orthogonal to wi As for i = t +> o(w,((n) + tt) + by) is the zero function for S O, as in this case wi (æo te) + by < wi by = 0. Hence, the left derivative of at 0 is 0. On the other hand, for t > 0, ((w))(0 + te) + bi) = wi + te) + bi twie. Hence, the right derivative of g(l) = <(W(n) + (e) + b) is (wm, e)) Now, it is assumed that the derivative of F(z) uø(Vz + c) in the direction of e1)) is not zero. Hence, the right derivative of f(t) (()( is not zero. All in all we have shown that the right derivative of f at is different from the left derivative, which implies that f is not linear in any neighborhood of 0.
19

---

Published as a conference paper at ICLR 2023
Lemma 9. Let Pi,P2 be hyperplanes such that D(F1,, 2 6. Let P1 and let x be standard Gaussian P1 with mean æ. Then p (d(x, P2) S aa S
V2a
Proof. W.l.ogg. we can assume that P1 and IP2 contain the origin. Let n2 be the normal of P2. We have that d(x, P2) = (x, n2)l. Now (x, n2)
(x, n2 - proje, n22) + (x, (x, proje, n2)
=
xEP:
(x, projr, 122)
(x x, projp: n2) + (x, proje, n2)
Hence (x, n2)) is Gaussian with mean μ (x, proje, n2) and variance x² 2 Hence,
2V [ e ( di 6v
2a
2a
p(x E [-aa,
8V
Lemma 10. Let be a hyperplane that corresponds a first layer neuron. Let æ E IP and let be a standard Gaussian in IP with mean æ. Then X is 8' --non-degenerate critical point of w.p. at least
1 - 22 +d2) 8' v
Proof. By lemma 8 x is critical w.p. It is therefore enough to show that w.p. at least 1 2d())+ d'v2 the distance of from every critical hyperplane other than IP is at least 8'. Indeed,
by lemma 9 and the fact that there are at most (d1 + d2)2d < 22(d++d2) critical hyperplanes, the probability that the distance from x one of the critical hyperplane less than 8' at most 22( +d2) 6'v2
8VT
Lemma 11. Let P be a hyperplane that corresponds to second layer neuron. Let 21 critical point with P as its critical hyperplane. Let P1 be hyperplane that corresponds to first layer neuron. Let 22 E be another point and assume that an and 22 are of opposite sides of P1. Let x be standard Gaussian in IP with mean x2. Then x is 8' o'-general w.p. at least 1 22(d++d2) 82v22 (diag P1)
P be
8V7
Proof. As in the proof of lemma T0 the probability that the distance from x to one of the critical hyperplanes other than IP is less than 8' is at most 22())+d2) 8' /2 It is therefore remains show that
8/7"
(dlleg.F)) 3 o')
the probability that x -'-close to on of P's critical points at most e
Denote by nı the normal of PI. We first note that there Indeed, the state of the first layer is different than the state at æ2, as the neuron corresponding to P1 changes its state. As is assumed that each second layer critical hyperplane corresponds neuron and single first layer state, it follows that there are no P-critical points in x2 's side of PP. therefore enough bound the probability that is 8' -cloee œ1 side of P1, which is same as the probability that (x I2, n1) 2 d(z2, P1) 8'. Finally, (x 22, n21) is a centered Gaussian (aies --)
P-eritical points in æ2 's side of P1-
single
with variance < 1. Hence, p((x T2, ni 2 d(2r2, P.) 5') S
D CORRECTNESS OF THE ALGORITHMS
Lemma 12. Algorithm reconstructs the correct affine transformation at an e-general point æ Rd
Proof. Note that for any y e Id with ||y|| S e we have.
f(x + 9) = f(x) + d
f(x + ee f(x)
yi-
e
20

---

Published as a conference paper at ICLR 2023
Hence, for every [xx, e) we have
[(z) f + (z =x))
d
f( + -f(x)
+ f(x)+
Σ
(zs xi)
==1
(1())
f(x + (ell)) - f(xr)
d
f(x + (e(e)))) - f(x))
24
25.
As f is affine at 2, we therefore get:
w: f(x + e) - f(æ)
d
f(x + eEl") f(x) It
and b=
[(xx
Σ
1=1
Lemma 13. Algorithm| returns the left most critical point of a S-nice one-dimensional fue-dimensionaalunctoono function f in the range (a, 1/6).
Proof. Let xx is the left-most critical point in (a, 1/8). Throughout the algorithm's execution, we have that Fy < <x < In, as in each iteration, we choose the left half of the segment unless this half is affine (and therefore cannot have critical point). As start with segment of size 2/8 and split it two halves at each iteration, after [log,(2/83) the final step, have that zy is in the left-most piece, while Ia is in the piece that is adjacent to the left-most piece. Therefore, x² is the point at the intersection of those two affine functions. no critical point is in (a, 1/5), then the segment affine and we get that A, = AR-
iterations we left with Jr - Iœl < Hence, in
Finally, note that all the points Tn and anter during the execution the algorithm are in the grid 2 (1002(2/82)) E and therefore 8 -g-general.
L
Lemma 14. Algorithm returns critical hyperplane of 5-non-degenerate critical point a E Rdd assuming the hyperplane is 8 general.
Proof. Let us assume that æ is a d-critical point of the j'th neuron. We will reconstruct the j'th neuron in two steps.
The first step is find an affine function A such that Am,,,, or = -An, Let M( : M(x)) uyj(( (w),( + by). Note that M' is affine in [a 8). as no neuron other than the j'th one changes its state (xx, 5). We have that in B(x, 5) on one side of æ's critical hyperplane the network computes M' (x) and on the other hand it computes M'(x) + u, ((w,, a:) + by). Thus, to extract Aw, up to sign, we can simply compute the affine functions computed by the network both sides of the z's critical hyperplane, and subtract them.
2. The second step is recover uj. To this end, we note that if uy 1 then M(x) is strictly convex in B(x, d) as the sum of the affine function M'(x) and the convex function u, u, æ) by). Similarly, u, = then M(x) is strictly concave B(x, 8). Thus, to recover uy we will simply check the convexity of M in B(x, 8) using algorithm
Finally, note that (AA())) is either of d(ww, æ) + by) ol ol(w, x) + b,) (w, x) by- Hence, (,)(A())) is either u ( æ) + by) or u,o((w), x) + by) - u, u, x) u,b,. In particular, ugo(A (Ax)) equals to u.o(Amp (x)) up affine map.
21

---

Published as a conference paper at ICLR 2023
E
ON THE NON-ZERO PARTIAL DERIVATIVES ASSUMPTION
Consider ReLU network
M(x)
Σ
u u +by)
(4)
j=1
and assume that for any j. My # 0 (otherwise the corresponding neuron can be dropped). We have that
Am
d1
(a)
Σ j=1
dz.
Now, if the weights are random, say that the wy's are independent random variables such that wy (i) has a continuous distribution, then w.p. 1, we have that for every non-zero vector 2 E {0, 1]d1, it holds that
di
Σ
(t) #0
and hence B.M (x: * O, unless the vector A(x) == (w) x + bi.... Wd x + ba, is the negative Se. orthant R It follows the non-zero partial derivatives assumption holds, provided if and only the affine map A maps the positive orthant Rd to the complement of the negative orthant Rdd The following lemma shows that if d1 > d. then this is often the case.
Lemma 15. Assume that the pairs (w,,bz) bj) independent and symmetric then
d+1
p (A(RR) Rdi +0) S
2d1
Proof. We first note that the number of orthants that has non-negative intersection with A(R²) is exactly the number of functions in the class
H = {j [di] + sign(=(())
A(R*))
Since A(Rd) is an affine space of dimension most d, /f has VC dimension most d + 1 (e.g. Anthony & Bartlet (1999)). Hence, by the Sauer-Shelah lemma (again, Anthony & Bartlel (999))
d1
cdj d
H
t=0
Finally, since the (w,, by)'s and symmetric, the probability that A(IR)) intersects IR is the same as the probability that it intersects any other orthant. Since there are 2d orthants, and A(Rd) intersects
(1 dil
at most edi d+1 of them, it follows that (A(R)) + v) s 24.
All all we get the following corollary:
Theorem 5. Assume that the pairs (wiybj) bz) are independent, symmetric, and has continuous marginals, w.p. 1
(dd 221
we have that aM dz, (x) + ffror all Rdd and E [d]
2
*That is, for all E [dz], the distributions of (ın,, by) and (-mny by) are the same.
22


Reviews:
[{"review_id": "SK6K7elfLq", "reviewer": "Reviewer_qJaS", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper considers the problem of learning a ReLU network from queries, which was recently remotivated by model extraction attacks. Assuming $\\delta$-regular networks, the authors present a polynomial-time algorithm that can learn a depth-two ReLU network from queries and a polynomial-time algorithm that, with some additional assumptions, can learn a rich class of depth-three ReLU networks from queries. \n", "summary_of_the_review": "This paper provides insightful results on designing algorithms for recovery of 2 or 3 layer neural networks, generalizing the previous results on this line of works. However, there are many assumptions, e.g. $\\delta$-regular networks, imposed on the networks to guarantee the success of the proposed algorithms. Experiments or validation of the assumptions on practical neural networks are missing, which makes it hard to judge the practical value of the proposed algorithms. \n", "strength_and_weaknesses": "Strength\n\n- The authors provide a polynomial-time query complexity algorithm for exact recovery of a two-layer neural networks with some general position assumptions.\n- Additionally, an algorithm that can identify whether a neuron belongs to the first or the second layer is provided that is used in designing an algorithm for the recovery of a three-layer ReLU activated neural networks.\n- The paper is well-written and organized in general and clearly conveys the main concepts and ideas for the recovery algorithms.\n\nWeakness\n\n- The proposed algorithms assume $\\delta$-regular networks, satisfying 7 conditions from Definition 1, which are purely characteristics of the network itself, independent from either training dataset or learning algorithm. What is missing here is whether neural networks trained with gradient descent from random initialization can indeed be $\\delta$-regular networks with high probability in practice. After training a simple 2 or 3 layer ReLU activated neural networks with some public datasets, can the authors indeed find that the conditions are well satisfied without the artificial weight perturbations?\n- The authors provide a key concept in generalizing the recovery algorithm from 2-layer to 3-layer neural networks by identifying whether a neuron belongs to the first or the second layer. What is the main technical hurdle in extending the similar idea to networks with more depth? This discussion point is missing.\n- Even though this work has value in theory as the authors argued, I think the algorithm should work in practice in recovering simple 2 or 3 layer neural networks. But, no experiment is provided by the author to judge the practical value of the proposed algorithms. Is there any reason one cannot actually use the proposed algorithm in real neural networks? Is it due to the strict assumptions imposed on the neural networks or the computational complexity?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "4lS5ExhvIcd", "reviewer": "Reviewer_3xMF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "", "summary_of_the_paper": "This paper considers the problem of reconstructing a small-depth ReLU network with queries. They give results for depth 2 and depth 3 networks under some general position assumptions (and additional assumptions for depth 3). They solve the exact reconstruction problem where the goal is to reconstruct the parameters of the original network.\n\n ", "summary_of_the_review": "The paper is strong in terms of the technical results it proves. The motivation is a little weak. I lean towards reject, but would not object to accepting it if the paper has an enthusiastic backer. ", "strength_and_weaknesses": "The problem they solve is arguably rather far from the motivating context of reconstructing networks via attacks for at least a couple of reasons:\n- The bound on the depth.\n- The general position assumption. \nIt is for instance natural to have many nodes that apply some threshold to say $\\sum x_i$. This would not be covered by their result. \n\nAlso it seems that the general position assumptions are necessitated by formulating the problem as an exact recovery problem as oppose dot functional recovery. The authors claim that exact recovery is essential for the motivating task of model extraction. I am not sure if I agree. If one can reconstruct a network that is equivalent to a large DNN by observing its behavior, why does it matter that the architecture is different?\n\nIt is a little unclear what the ultimate goal here would be. It is not clear if reconstruction algorithms for larger constant depths will shed light on the problem of how to reconstruct a real world neural net. Also, if the goal is to protect the IP of whoever designs the  neural net, perhaps negative results saying certain architectures are hard to reconstruct are more relevant?\n\nOn the other hand, their results are technically quite interesting and non-trivial, and are likely to generate followup work. I would not be opposed to accepting it for this reason, even if I am myself not very excited by the problem.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "3iadK5vYNy", "reviewer": "Reviewer_vJNj", "summary": "", "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": "", "summary_of_the_paper": "\nThis work considers the problem of exactly recovering ReLU networks using\nmembership queries, i.e., by having access to the exact output of the network\nfor any chosen input.  They give algorithms that can reconstruct 2 and 3 layer\nReLU networks in polynomial time under some assumptions on the weights of the\nnetworks.\n\nIn particular, for 2-layer networks, this work shows that it is possible to\nlearn a network that is equivalent to the target network (in the sense that\nthe paper).  For 3-layer networks, they require additionally that the width of\nthe first layer is larger than the dimension of the input and that the top layer\nhas non-vanishing derivatives.  This work gives the first poly-time algorithm\nthe paper). \n\n", "summary_of_the_review": "\nThis work presents efficient algorithms for exact reconstruction of shallow\nneural networks (up to 3-layers) using membership queries.  This work gives the\nfirst polynomial time algorithm for reconstructing 3-layer networks and in this\nsense, I believe it is a good first step toward deeper models.  Although I am not\nconvinced that exact reconstruction is the right direction (especially for\ndeeper models), I think the results of this work are above the threshold\nfor ICLR and I am leaning toward acceptance.\n", "strength_and_weaknesses": "Strengths\n\n1. The paper gives the first polynomial-time algorithm for reconstructing\n3-layer networks using membership queries.  The main challenge in\nreconstructing 3-layer networks is identifying whether a critical hyperplane\ncomes from the first or second hidden layer (Algorithm 7).  The authors then\nreduce this to reconstructing 2-layer networks.\n\nWeaknesses\n\n1. The reconstruction results require many assumptions (as the authors also\nadmit) (see Definition 1 of regular networks).  Fortunately, the authors show\nthat a (much easier to parse) sufficient condition is that the weights of the\nnetwork are perturbed by adding small uniform noise.  Still, it seems that at\nleast some of the assumptions are not necessary (even for exact recovery) and\nare tailored to make the analysis easier. \n\n2. I am not convinced that asking for exact network recovery is the ``right''\ngoal as it inherently leads to unnatural and perhaps impractical (especially\nfor deeper networks)  assumptions, e.g., having the exact output of the model\nwith zero error tolerance.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster