Efficiently Learning One Hidden Layer Neural Networks From Queries
Year: 2021

Abstract:
Model extraction attacks have renewed interest in the classic problem of learning neural networks from queries. This work gives the first polynomial-time algorithm for learning one hidden layer neural networks provided black-box access to the network. 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 running time that is polynomial in all parameters that 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 the first with fully polynomial-time guarantees of efficiency for worst-case networks (in particular our algorithm succeeds in the overparameterized setting).

heading: 1 Introduction
text: The problem of learning neural networks given random labeled examples continues to be a fundamental algorithmic challenge in machine learning theory. There has been a resurgence of interest in developing algorithms for learning one hidden layer neural networks, namely functions of the form F (x) = ∑k i=1 siσ(〈wi, x〉 − bi) where wi ∈ Rd, si ∈ {±1}, bi ∈ R are the unknown parameters. Here we consider the ubiquitous setting where σ is the ReLU activation, the input distribution on x is Gaussian, and the goal is to output a ReLU network F ′ with E[(F (x)− F ′(x))2] ≤ . Despite much recent work on this problem [JSA15, ZSJ+17, GKM18, GLM18, GKLW18, ZYWG19, BJW19, DKKZ20, CKM20, LMZ20], obtaining a polynomial-time algorithm remains open. All known works take additional assumptions on 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, DKKZ20] as well as under various average-case assumptions [DV20, DV21], that suggest that a truly polynomial-time 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 x of its choosing and receive the output value of the unknown network F (x). Our main result is the first polynomial-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) = ∑k i=1 siσ(〈wi, x〉−bi) with ‖wi‖2 ≤ R, si ∈ {±1}, and bi ≤ B. Given black-box access to F , there exists a (randomized) algorithm that will output with probability at least
∗This work was supported in part by an NSF CAREER Award CCF-1453261 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). ‡Supported by NSF CAREER Award CCF-1553605.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
1 − δ, a one hidden layer network F ′ such that Ex∼N (0,Id)[(F (x) − F ′(x))2] ≤ . The algorithm has query complexity and running time that is polynomial in d,B,R, k, 1/ , and log(1/δ).
In light of the aforementioned lower bounds [GGJ+20, DKKZ20, DV20, DV21], Theorem 1.1 suggests there is a separation between learning from random samples and learning from queries in the context of neural networks.
In addition to being a 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, JWZ20]. These attacks attempt to reverse-engineer neural networks found in publicly deployed real-world systems. Since the target network is publicly available, an 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/linear independence 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.

heading: 1.1 Our Approach
text: Here we describe our approach at a high level. Fix an unknown one hidden-layer network F (x) =∑k i=1 siσ(〈wi, x〉 − bi) with weight vectors wi ∈ Rd, signs si ∈ {±1}, and bias terms bi ∈ R. Consider a line L = {x0 + t · v}t∈R for x0, v ∈ Rd and the restriction F |L(t) , F (x0 + t · v) given by
F |L(t) = k∑ i=1 siσ (〈wi, x0〉 − bi + t〈wi, v〉) .
Note that as a univariate function, F |L(t) is a piecewise-linear function. We call a point t ∈ R a critical point of F |L if the slope of the piecewise-linear function changes at t. Our starting point is that if we can identify the critical points of F |L, then we can use estimates of the gradient of F at those critical points to estimate the weights of the hidden units in F . More concretely, suppose we have identified a critical point ti of F |L for a line L. Now, back in the d-dimensional space, if we look at a sufficiently small neighborhood of the point x′ = x0 + ti · v, then the set of activated units around x′ changes by exactly one (in fact, by this reasoning, for a random L, F |L 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 wi’s and bi’s by finite differencing: for each such x′, compute (F (x′+ δ)−F (x′))/‖δ‖, for several sufficiently small perturbations δ ∈ Rd, and this will recover siwi (see Algorithm 2 and 4.9 below for the details). We can recover sibi 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 provable guarantees for arbitrary networks:
1. How do we identify the critical points of F |L for a given line L? 2. If we make no assumptions on how well-separated the weight vectors are, it 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 function being a tiny peak of exponentially small in d width on the real line) on the line F |L. In this case, identifying them would not be possible efficiently. We develop several structural results about cancellations in ReLU networks (culminating in Lemma 3.9) that show that such a situation only
arises in degenerate cases where some sub-network of F contains a 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” neuron 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 differences 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).

heading: 1.2 Comparison to Previous Approaches
text: Our general approach of looking for critical lines along random restrictions of F |L is also the approach taken in the empirical works of [CJM20, JCB+20] and in the theoretical work of [MSDH19], but we emphasize that there are a variety of subtleties that arise because we are interested in learning worst-case networks from queries. In contrast, the empirical works consider trained networks arising in practice, while [MSDH19] makes a strong assumption that the weight vectors wi are linearly independent and that they are angularly separated. Note that such assumptions cannot hold in the practically relevant setting where F is overparameterized.
To give a sense for the issues that these existing techniques run up against when it comes to worstcase networks, imagine that the one-dimensional piecewise linear function given by the restriction F |L were simply a “bump,” that is, it is zero over most of the line except in a small interval [a, a+δ]. For instance, this would arise in the following example:
Example 1.2. Consider the one-dimensional one hidden layer network F : R→ R given by F (x) = σ(x− a) + σ(x− a− δ)− σ(2x− 2a− δ). This function looks like the zero function except over the interval [a, a+ δ], where it looks like a 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 [−τ, τ ] in L and check whether the gradient at the left or right endpoint differs from the gradient at the midpoint tmid = 0. If the former, then they restrict the search to [−τ, tmid] 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 a critical point. The intuition is that n steps of binary search suffice to identify a critical point up to n bits of precision.4
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 [−τ, τ ], then at the outset, we don’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, it is clear that we need to 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 on the dependence on 1/ (see e.g. [Han09]). Indeed, if we took the width of the bump to be of size poly( ) to make it -far in square distance from the zero function, we would still need poly(1/ ), rather than log(1/ ), queries to 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 F |L 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 are 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 a 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
4We remark that the refinement of binary search given in [CJM20, JCB+20] can speed this up to O(1) steps for networks that arise in practice, but the issue that we describe poses a challenge for their technique as well.
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 sequel, 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/ ) dependence is necessary in our setting. In fact this example also tells us another somewhat counterintuitive fact about our setting. Naively, one might hope to 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 δ−3/2 to have unit L2 norm. To learn F , we have to figure out the location of the bump, but this requires Ω(1/δ) queries, and δ can be taken to be arbitrarily small.
Limitations and Societal Impact The line of work on 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 to 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 to ensure that it is hard for actual attackers. For instance, it is conceivable that one can prove information-theoretic 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.

heading: 2 Preliminaries
text: Notation We let Sd−1 denote the unit sphere in Rd. Let ej denote the j-th standard basis vector in Rd. Given vectors u, v, let ∠(u, v) , arccos ( 〈u,v〉 ‖u‖‖v‖ ) . Given a matrix M , let ‖M‖op and ‖M‖F denote the operator and Frobenius norms respectively. Given a function h which is squareintegrable with respect to the Gaussian measure, we will use ‖h‖ to denote Ex∼N (0,Id)[h(x)2]1/2. Given a collection of indices S ⊆ Z, we say that i, j ∈ S are neighboring if there does not exist i < ` < j for which ` ∈ S. Definition 2.1. A neuron is a pair (v, b) where v ∈ Rd and b ∈ R; it corresponds to the function x 7→ σ(〈v, x〉 − b), which we sometimes denote by σ(〈v, ·〉 − b). Definition 2.2. Given a line L ⊂ Rd parameterized by L = {x0 + t · v}t∈R, and a function F : Rd → R, define the restriction of F to L by F |L(t) , F (x0 + t · v). Definition 2.3. Given a line L ⊂ Rd and a restriction F |L of a piecewise linear function F : Rd → R to that line, the critical points of F are the points t ∈ R at which the slope of F |L changes.
We will need the following standard facts about the concentration of the norm and individual entries of a Gaussian vector.
Fact 2.4. Given Gaussian vector h ∼ N (0,Σ), Pr [ ‖h‖ ≥ O(‖Σ1/2‖op( √ r + √ log(1/δ))) ] ≤ δ,
where r is the rank of Σ. Fact 2.5. For covariance matrix Σ ∈ Rm×m, given h ∼ N (0,Σ) we have that |hi| ≤ O (√ Σi,i √ log(m/δ) ) for all i ∈ [m] with probability at least 1− δ.
We will also need anti-concentration 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 ∼ N (µ,Σ), Pr [ ‖h‖ ≥ √ ν‖Σ‖1/2F ] ≥ 1− C √ ν.
Lemma 2.7. For random v ∈ Sd−1, Pr [ |v1| < δ
2 √ d+O( √ log(1/δ))
] ≤ δ.

heading: 3 ReLU Networks with Cancellations
text: 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 supplementary material.

heading: 3.1 (∆, α)-Closeness of Neurons
text: We first formalize a 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′ ∈ Rd and b, b′ ∈ R, we say that (v, b) and (v′, b′) are (∆, α)-close if the following two conditions are satisfied:
1. |sin∠(v, v′)| ≤ ∆
2. ‖bv′ − b′v‖ ≤ α‖v‖‖v′‖.
Note that this is a measure of angular closeness between (v, b), (v′, b′) ∈ Rd+1. For instance, if (v, b) = (λv∗, λb∗) and (v′, b′) = (λ′v∗, λ′b∗) 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 if we scale two (∆, α)-neurons to have similar norm, then their biases will be close.
Lemma 3.2. If (v, b) and (v′, b′) are (∆, α)-close, and v = γv′ + v⊥ for v⊥ orthogonal to v′, then |γb′ − b| ≤ α‖v‖.
Note that when two neurons are (∆, α)-close, 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 ∆ < √
2/2. If (v1, b1), . . . (vk, bk) are all pairwise (∆, α)-close for some α > 0, then there is a partition [k] = S1 t S2 for which 〈vi, vj〉 ≥ 0 for any i ∈ S1, j ∈ S1 and i ∈ S2, j ∈ S2, and for which 〈vi, vj〉 < 0 for any i ∈ S1, j ∈ S2 and i ∈ S2, j ∈ S1.
In the rest of the paper we will take ∆ to be small, so Lemma 3.3 will always apply. As such, it will be useful to define the following terminology:
Definition 3.4. Given (v1, b1), . . . , (vk, bk) which are all pairwise-close, we will call the partition S1 t S2 given in Lemma 3.3 the orientation induced by {(vi, bi)}.
We note that (∆, α)-closeness satisfies the triangle inequality.
Lemma 3.5. If (v1, b1) and (v2, b2) are (∆, α)-close, and (v2, b2) and (v3, b3) are (∆′, α′)-close, then (v1, b1) and (v3, b3) are (∆ + ∆′, 2α+ 2α′)-close.

heading: 3.2 Merging Neurons
text: We prove that a one hidden-layer network where all neurons are (∆, α)-close to some neuron can be approximated by at most two neurons:
Lemma 3.6. [See supplementary material.] Given F (x) = ∑k i=1 siσ(〈wi, x〉 − bi) for si ∈ {±1} and (v∗, b∗) ∈ Rd × R for which (wi, bi) is (∆, α)-close to (v∗, b∗) for all i ∈ [k], there exist coefficients a+, a− ∈ R for which
E x∼N (0,Id)
[( F (x)− a+σ(〈v∗, x〉 − b∗)− a−σ(〈−v∗, x〉+ b∗) )2] ≤ O(k2(∆2/5 + α2))‖v∗‖2. Furthermore, we have that
|a+|‖v∗‖, |a−|‖v∗‖ ≤ ∑ i ‖wi‖ and |a+b∗|, |a−b∗| ≤ α ∑ i ‖wi‖+ ∑ i |bi|.
Note that Lemma 3.6 requires the existence of a neuron (v∗, b∗) which is close to all neurons {(vi, bi)}. In our algorithm, we will not have access to (v∗, b∗) but rather to some linear combination of the neurons {(vi, bi)}. We show that provided this linear combination is not too small in norm, it will also be close to all the neurons {(vi, bi)}. Lemma 3.7. Suppose we have vectors v1, . . . , vm, v∗ ∈ Rd, biases b1, . . . , bm, b∗ ∈ R for which every (vi, bi) is (∆, α)-close to (v∗, b∗). Then for any s1, . . . , sm ∈ {±1}, if we define v , ∑m i=1 sivi
and b , ∑m i=1 sibi, then (v, b) is (∆m,α ∑ i‖vi‖/‖v‖)-close to (v∗, 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 a very specific form (see the vector in (1)), and we 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 (v1, b1), . . . , (vm, bm) are pairwise (∆, α)-close, and let [m] = S1 t S2 denote the orientation induced by them (see Definition 3.4). Define B , maxi‖bi‖ and R , maxi‖vi‖. If signs s1, . . . , sm ∈ {±1} satisfy
‖ ∑ i∈S1 sivi − ∑ i∈S2 sivi‖ ≤ (∆R)2/9, (1)
then for the network F (x) , ∑ i siσ(〈vi, x〉−bi), there exists an affine linear function `(x) : Rd → R for which E
x∼N (0,Id)
[ (F (x)− `(x))2 ] ≤ poly(k,R,B) · (α1/2 + ∆2/9)
where ` , 〈w∗, ·〉 − b∗ satisfies
‖w∗‖ ≤ ∑ i ‖vi‖ and |b∗| ≤ ∑ i ‖bi‖.

heading: 3.3 Putting Everything Together
text: Putting Lemmas 3.6, 3.7, and 3.8 together, we conclude that networks whose hidden units are pairwise (∆, α)-close can either be approximated by a particular size-two network, or by some affine linear function:
Lemma 3.9. Suppose (v1, b1), . . . , (vk, bk) are pairwise (∆, α)-close, and let [k] = S1tS2 denote the orientation induced by them (see Definition 3.4). Define B , maxi‖bi‖ and R , maxi‖vi‖. Let s1, . . . , sm ∈ {±1}. Define F (x) = ∑ i siσ(〈vi, x〉 − bi), v∗ = ∑ i∈S1 sivi − ∑ i∈S2 sivi, and b ∗ = ∑ i∈S1 sibi −∑
i∈S2 sibi. At least one of the following holds:
1. There is an affine linear function ` : Rd → R for which ‖F−`‖2 ≤ poly(k,R,B)·(α1/2+ ∆2/9).
2. There exist coefficients a+, a− ∈ R for whichG(x) , a+σ(〈v∗, x〉−b∗)−a−σ(〈−v∗, x〉+ b∗) satisfies ‖F −G‖2 ≤ poly(k,R,B) · (∆2/5 + α2∆−4/9).
Proof. By assumption, every (vi, bi) is (∆, α)-close to (v1, b1). By Lemma 3.7 we get that for (v∗, b∗) defined in the lemma statement, (v1, b1) is (∆k, αmR/‖v∗‖)-close to (v∗, b∗).
If ‖v∗‖ ≥ (∆R)2/9, then we conclude that (v1, b1) is (∆k, αm∆−2/9R7/9)-close to (v∗, b∗), and by Lemma 3.6 we find that there is a choice of a+, a− for which the function G defined in the lemma statement satisfies ‖F − G‖2 ≤ O(k4R2(∆2/5k2/5 + α2m2∆−4/9R14/9)) (note that we used ‖v∗‖ ≤ ∑ i‖vi‖ ≤ kR).
If ‖v∗‖ ≤ (∆R)2/9, then by Lemma 3.8 we find that there is an affine linear ` for which ‖F −`‖2 ≤ poly(k,R,B) · (α1/2 + ∆2/9).

heading: 4 Learning One Hidden Layer
text: In this section we give our algorithm for learning neural networks from queries. Throughout, we will suppose we have black-box query access to some unknown one-hidden layer neural network
F (x) , k∑ i=1 siσ(〈wi, x〉 − bi), (2)
where si ∈ {±1}, wi ∈ Rd, bi ∈ R. Define the quantities R , maxi‖wi‖ and B , maxi‖bi‖; our bounds will be polynomial in these quantities, among others.

heading: 4.1 Critical Points of One-Hidden Layer Networks
text: In this section, we 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 a random restriction: Definition 4.1. A Gaussian line L is a random line in Rd formed as follows: sample x0 ∼ N (0, Id) and Haar-random v ∈ Sd−1 and form the line L , {x0 + t · v}t∈R.
Here we compute the critical points along a restriction of F .
Proposition 4.2. Given a line L = {x0 + t · v}t∈R, the restriction F |L(t) , F (x0 + t · v) is given by
F |L(t) = k∑ i=1 siσ (〈wi, x0〉 − bi + t〈wi, v〉) .
This function has k critical points, namely t = − 〈wi,x0〉−bi〈wi,v〉 for every i ∈ [k].
Proof. The critical points of F |L are precisely the points t at which a neuron changes sign. So the crticial point associated to the i-th neuron is the t for which 〈wi, x0〉−bi+t〈wi, v〉 = 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 is small. The reason for the latter caveat is that, e.g., if one took the one-dimensional neuron σ( z − b) for b fixed and → 0, the z at which it changes sign tends to∞). Lemma 4.3. With probability at least 1 − δ over the randomness of Gaussian line L, we have that |ti| . k( √ d+ √ log(1/δ)) δ‖wi‖ + k (√ d+ √ log(1/δ) )√ log(k/δ) for every critical point ti of F |L.
Fix a separation parameter ∆ > 0 which we will tune in the sequel. We show that along Gaussian lines L, F |L’s critical points are well-separated except for those corresponding to neurons which are (∆, α)-close. Lemma 4.4. There is an absolute constant c > 0 for which the following holds. Given Gaussian line L, with probability at least 1− δ we have: for any pair of i, j for which (wi, bi) and (wj , bj) are not
(∆, c∆ √ log(k/δ))-close, the corresponding critical points are at least Ω (
∆δ2 k4 (√ d+ √ log(k/δ) ))-
apart.

heading: 4.2 Line Search and Existence Theorem
text: At a high level, our algorithm works by searching along F |L, partitioning L into small intervals, and computing differences between the gradients/biases of F at the midpoints of these intervals. The primary structural result we must show is that there exists enough information in this set of differences to reconstruct F up to small error.
As we will be working with partitions of lines, it will be convenient to define the following notation:
Definition 4.5. Given line L ⊂ Rd and finite interval I ⊆ R corresponding to a segment I ⊂ L, let ∇L(I) denote the gradient of F at the midpoint of I. For tmid ∈ R the midpoint of I , define bL(I) , F |L(tmid) − (F |L)′(tmid) · tmid. Intuitively, this is the “y-intercept” of the linear piece of F |L that contains tmid. When L is clear from context, we will drop subscripts and denote these objects by ∇(I) and b(I). Definition 4.6. Given line L ⊂ Rd and length s > 0, let {ti} denote the critical points of F |L, and let G+L(s) ⊆ [k] (resp. G − L (s)) denote the set of indices a ≤ i ≤ b for which ti+1 − ti ≥ s (resp. ti − ti−1 ≥ s). Let G∗L(r) , G + L(r) ∩G − L (r).
The following observation motivates Definition 4.6: Observation 4.7. Given line L ⊂ Rd, let {ti} denote the critical points of F |L. Let I1, . . . , Im be a partition of some interval I into pieces of length r, and for ti ∈ I let `(i) denote the index of the interval containing I . Then for any i ∈ G+L(2r) (resp. i ∈ G − L (2r)), I`(i)+1 is entirely contained within [ti, ti+1] (resp. I`(i)−1 is entirely contained within [ti−1, ti]). In particular, I`(i)−1 and I`(i)+1 are linear pieces of F |L.
The following is the main result of this section. At a high level, it says if we partition a random line in Rd into sufficiently small intervals and can compute the gradient of F at the midpoint of each interval, then we can produce a collection of neurons which can be used to approximate F . Theorem 4.8. For any , δ > 0, define
r , O  ∆δ2 k4 (√ d+ √ log(k/δ) )  (3)
τ , kr + Θ
( k( √ d+ √ log(1/δ))
δ‖wi‖ + k
(√ d+ √ log(1/δ) )√ log(k/δ) ) . (4)
Partition the interval [−τ, τ ] into intervals I1, . . . , Im of length r. Let L be a Gaussian line, and let S denote the set of all m(m − 1) pairs (w, b) obtained by taking distinct i, j ∈ [k] and forming (∇L(Ii) − ∇L(Ij), bL(Ii) − bL(Ij)). There exist {±1}-valued coefficients {aw,b}(w,b)∈S , vector w∗, and b∗ ∈ R for which∥∥∥∥∥∥F − ∑ (w,b)∈S aw,b · σ(〈w, ·〉 − b)− 〈w∗, ·〉 − b∗ ∥∥∥∥∥∥ ≤ + Pk,R,B,log(1/δ) ·∆2/9.
for Pk,R,B,log(1/δ) some absolute constant that is polynomially large in k,R,B, log(1/δ). Furthermore, we have that
‖aw,b · w‖ ≤ kR and |aw,b · b| ≤ c∆k2R √ log(k/δ) + kB (5)
‖w∗‖ ≤ kR and |b∗| ≤ kB

heading: 4.3 Gradient and Bias Oracles
text: It remains to implement oracles to compute bL(I) and ∇L(I) for prescribed line L and interval I . It 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 to do so for certain “nice” I as suggested by Theorem 4.8.
To that end, first note that it is straightforward to form the quantities bL(I) for intervals I entirely contained within linear pieces of F |L; we formalize this in Algorithm 1. It remains to demonstrate how to construct ∇L(I). Intuitively one can accomplish this via “finite differencing,” i.e. the gradient of a piecewise linear function F at a point x can be computed from queries by computing F (x+δ)−F (x)δ for several sufficiently small perturbations δ ∈ R
d and solving the linear system.
With a priori precision estimates, we can similarly implement a gradient oracle, as formalized in Algorithm 2 and Lemma 4.9.
Algorithm 1: GETBIAS(L, I) Input: Line L ⊂ Rd, interval I = [a, b] ⊂ R Output: bL(I) if I is entirely contained within a linear piece of F |L 1 tmid ← midpoint of I . 2 y0 ← F |L(tmid). 3 s← F |L(b)−F |L(a)b−a . 4 return y0 − s · tmid
Algorithm 2: GETGRADIENT(x, α) Input: x ∈ Rd, α > 0 for which (6) holds Output: ∇F (x) ∈ Rd 1 for j ∈ [d] do 2 Sample random unit vector zj ∈ Sd−1. 3 vj ← (F (x+ αzj)− F (x))/α. 4 Let w be the solution to the linear system {〈w, zj〉 = vj}j∈[d]. 5 return w
Lemma 4.9. For any α > 0 and any x ∈ Rd for which |〈wi, x〉 − bi| ≥ α‖wi‖ ∀ i ∈ [k], (6)
GETGRADIENT(x, α) makes d queries to F and outputs ∇F (x).
In order to use GETGRADIENT to construct the vectors ∇L(I), we require estimates for α in Lemma 4.9. In the following lemma we show that with high probability over the randomness of L, if an interval I completely lies within a linear piece of F |L, 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 L be a Gaussian line. With probability at least 1−δ over the randomness of L, the following holds: in the partition [−τ, τ ] = I1∪· · ·∪Im in Theorem 4.8, for any I` which entirely lies within a linear piece of F |L, GETGRADIENT(tmid, α) correctly outputs ∇L(I`), where xmid is the midpoint of the interval I` ⊂ L that corresponds to interval I` ⊂ R and α = δ·r
4k √ d+O(k √ log(k/δ))
(where r is defined in (3)).
Putting these ingredients together, we obtain the following algorithm, GETNEURONS for producing a collection of neurons that can be used to approximate F .
We prove correctness of GETNEURONS in the following lemma: Lemma 4.11. For any , δ > 0, GETNEURONS( , δ) makes poly(k, d,R,B, 1/ , log(1/δ)) queries and outputs a list S of pairs (w, b) for which there exist {±1}-valued coefficients {aw,b}(w,b)∈S as well as a vector w∗ and a scalar b∗ such that∥∥∥∥∥∥F − 〈w∗, ·〉 − b∗ − ∑ (w,b)∈S aw,b · σ(〈w, ·〉 − b)
∥∥∥∥∥∥ ≤ .

heading: 4.4 Linear Regression Over ReLU Features
text: It remains to show how to combine the neurons produced by GETNEURONS to obtain a good approximation to F . As Theorem 4.8 already ensures that some linear combination of them suffices, we can simply draw many samples (x, F (x)) for x ∼ N (0, 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̂j} and the b’s by {b̂j}. Consider the following distribution over feature vectors computed by the neurons in S:
Algorithm 3: GETNEURONS( , δ) Input: Accuracy > 0, confidence δ > 0 Output: List S of pairs (w, b) (see Theorem 4.8 for guarantee) 1 S ← ∅. 2 Sample Gaussian line L. 3 ∆← ( /Pk,R,B,log(1/δ))9/2. // Theorem 4.8 4 α← δ·r
4k √ d+O(k √ log(k/δ)) . // Lemma 4.10
5 Define r, τ according to (3), (4). 6 Partition [−τ, τ ] into disjoint intervals I1, . . . , Im of length r. 7 for all j ∈ [m] do 8 xj ← midpoint of the interval Ij ⊂ L that corresponds to Ij ⊂ R. 9 ∇̂L(Ij)← GETGRADIENT(xj , α).
10 b̂L(Ij)← GETBIAS(L, Ij). 11 for all pairs of distinct i, j ∈ [m] do 12 (vj , bj)← (∇̂L(Ii)− ∇̂L(Ij), b̂L(Ii)− b̂L(Ij)). 13 if (vj , bj) satisfies the bounds in (5) then 14 Add (vj , bj) to S.
15 return S .
Definition 4.12. LetD′ denote the distribution over R|S|+d+1×R of pairs (z, y) given by sampling x ∼ N (0, Id) and forming the vector z whose entries consist of all σ(〈ŵj , x〉 − b̂j) as well as the entries of x and the entry 1, and taking y to be F (x) for the ground truth network F defined in (2).
We will also need to define a truncated version of D′: let D denote D′ conditioned on the norm of the |S|+1 to |S|+d-th coordinates having norm at mostM , √ d+O( √ log(1/δ), which happens with probability at least 1− δ over D′.
Our algorithm will be to sample sufficiently many pairs (z, y) from D′ (by querying F on random Gaussian inputs) and run ordinary least squares. This is outlined in LEARNFROMQUERIES below.
Algorithm 4: LEARNFROMQUERIES( , δ) Input: Accuracy > 0, confidence δ > 0 Output: One hidden-layer network F̃ : Rd → R for which ‖F − F̃‖ ≤ O( )
1 S = {(ŵj , b̂j)} ← GETNEURONS( , δ). 2 Draw samples (z1, y1), . . . , (zn, yn) from D // Definition 4.12 3 Let ṽ be the solution to the least-squares problem (7). Let b̃ denote the last entry of ṽ, and
let w̃ denote the vector given by the d entries of ṽ prior to the last. 4 Form the network F̃ (x) , ∑ j ṽjσ(〈ŵj , x〉 − b̂j) + 〈w̃, ·〉 − b̃. 5 return F.
Formally, we show:
Theorem 4.13. Let S denote the list of pairs (ŵj , b̂j) output by GETNEURONS( , δ). Sample (z1, y1), . . . , (zn, yn) from D for n = poly(k,R,B, 1/ , d, log(1/δ)). With probability at least 1−O(δ) over the randomness of GETNEURONS and the samples, the following holds. Define
ṽ , arg min ‖v‖≤W n∑ i=1 (〈v, zi〉 − yi)2, for W , √ τ/r + k(R+B), (7)
let b̃ denote the last entry of ṽ, and let w̃ denote the vector given by the d entries of ṽ prior to the last. Then the one hidden-layer network F̃ (x) , ∑ j ṽjσ(〈ŵj , x〉 − b̂j) + 〈w̃, ·〉 − b̃ satisfies ‖F − F̃‖ ≤ O( ).

Review summaries:
The paper considers the problem of learning depth-2 ReLU networks w.r.t. Gaussian inputs, where the learner has query (black-box) access to the target network. The problem of learning depth-2 networks (without queries) has been extensively studied in recent years. All known efficient algorithms require assumptions on both the input distribution and the network’s weights (e.g., that the weights matrix has full rank). Moreover, the known efficient algorithms for depth-2 ReLU networks do not handle bias terms. In this paper the authors give a first efficient algorithm for learning depth-2 ReLU networks with bias w.r.t. the Gaussian distribution using black-box access. There are no assumptions on the weights, except for having a bounded norm. The motivation for the problem is two-fold: (1) the model of PAC learning with membership queries is well-studied and natural; (2) there is an interest in model-extraction attacks in the security and privacy communities. Prior works on model-extraction either gave algorithms without theoretical guarantees, or efficient algorithms under strong assumptions.   The proposed algorithms follows the following ideas. For a random line L consider the restriction of the target network F. This restriction is a piecewise linear univariate function, such that each critical point corresponds to a neuron in F. This property can be exploited in order to recover the neurons. However, there are some major issues to overcome in order to implement this idea efficiently. For example, since we do not have any assumptions on the weights, then the critical points might be very close to each other. The authors solve this issue by showing that this situation occurs only if there is a cluster of similar neurons, in which case we can replace them with a small sub-network and do not have to recover all the neurons in the cluster. 

In this work, the authors study the problem of learning one hidden layer neural network with ReLU activations with $k$ neurons. Their objective is to output a ReLU network $F'$, such that $\|F-F'\|_2^2\leq \epsilon$, where $F$ is the unknown network. They assume that the underlying distribution is Gaussian, and that they have query access to the network. A query is a function of the form $q(x)=F(x)$, that is given an $x$, the query returns the value of $F(x)$. In this work, the only assumption is that $F(x)$ is bounded with respect to the $\|\cdot\|_2$. Other works have required either the vectors $\vec w$ to be linear independent or the weights to be non-negative. The assumptions are required in general, as linear independence is required for parameter estimation, and there exists Statistical Queries hardness on getting $\|F-F'\|_2^2\leq \epsilon$ using polynomial many queries without the assumption of non-negative weights. By assuming a more powerful model with queries they overcome the hardness.   Their algorithm restricts $F$ to a random line $L$ and then uses queries to estimate approximations to the gradients and get the critical points (points where a neuron is activated, i.e., changes sign) of $F$ restricted to the line $L$, and then they can estimate the $w_i$, and the $b_i$. One problem of this approach is that fails if some neurons are close to each other. To overcome this, the authors prove that if some neurons are close to each other, then they can be approximate by a linear combination of at most two neurons. The algorithm uses polynomial samples and queries with respect the parameters $d,max\|w\|,max(b),1/\epsilon,k$.

This paper provides a polynomial-time algorithm for learning neural networks (NN) with one hidden layer through queries. The result holds for NN with bounded weights and biases under Gaussian distributions.  The authors define a notion of closeness between neurons that allows strong assumptions on the weights (which were used in prior work and didn't translate to the overparametrized setting) to be dropped. Indeed, if a set of neurons are "close" enough, they can be approximated by two neurons or a linear function. This allows the learning algorithm to efficiently represent the target NN, which could be overparametrized.  At a high level, the algorithm recovers neurons by sampling a Gaussian line, separating it into suitably small intervals and computing the gradient (through queries) at their midpoints to recover the neurons' weight vectors.