Span Recovery for Deep Neural Networks with Applications to Input Obfuscation
Authors: Rajesh Jayaram
David P. Woodruff
Qiuyi Zhang
Venue:  (2020)
Keywords: Span recovery
low rank neural networks
adversarial attack

Abstract: The tremendous success of deep neural networks has motivated the need to better understand the fundamental properties of these networks, but many of the theoretical results proposed have only been for shallow networks. In this paper, we study an important primitive for understanding the meaningful input space of a deep network: span recovery. For $k<n$, let $\mathbf{A} \in \mathbb{R}^{k \times n}$ be the innermost weight matrix of an arbitrary feed forward neural network $M: \mathbb{R}^n \to  \mathbb{R}$, so $M(x)$ can be written as $M(x) = \sigma(\mathbf{A} x)$, for some network $\sigma: \mathbb{R}^k \to  \mathbb{R}$. The goal is then to recover the row span of $\mathbf{A}$ given only oracle access to the value of $M(x)$. We show that if $M$ is a multi-layered network with ReLU activation functions, then partial recovery is possible: namely, we can provably recover $k/2$ linearly independent vectors in the row span of $\mathbf{A}$ using poly$(n)$ non-adaptive queries to $M(x)$.  Furthermore, if $M$ has differentiable activation functions, we demonstrate that \textit{full} span recovery is possible even when the output is first passed through a sign or $0/1$ thresholding function; in this case our algorithm is adaptive. Empirically, we confirm that full span recovery is not always possible, but only for unrealistically thin layers. For reasonably wide networks, we obtain full span recovery on both random networks and networks trained on MNIST data. Furthermore, we demonstrate the utility of span recovery as an attack by inducing neural networks to misclassify data obfuscated by controlled random noise as sensical inputs. 


Published as a conference paper at ICLR 2020
SPAN RECOVERY FOR DEEP NEURAL NETWORKS WITH APPLI- CATIONS TO INPUT OBFUSCATION
Rajesh Jayaram
David Woodruff
Computer Science Department Carnegie Mellon University Pittsburgh, PA 15213, USA rkjayara@cs. cmu edu
Computer Science Department
Carnegie Mellon University Pittsburgh, PA 15213, USA dwoodruffcs cnu, edu
Qiuyi Zhang
Google Brain qi uuizzgoogll e com
ABSTRACT
The tremendous success of deep neural networks has motivated the need better understand the fundamental properties of these networks, but many of the theoretical results proposed have only been for shallow networks. meaningful input space of deep network: span recovery. For k < n. let A E R*x be the innermost weight matrix of an arbitrary feed forward neural network M I + R, so (x) can be written (xx) of (Azz), for some network : R* - R.. The goal is then to recover the row span of A given only oracle access to the value of M (x). We show that if M is a multi lalti-layere network with ReLU activation functions, then partial recovery is possible: namely, we can provably recover k/2 linearly independent vectors in the row span of A using poly(n) non-adaptive queries to (x)) Furthermore, if M has differentiable activation functions, possible even when the output is first passed through a sign or 0/1 thresholding function; in this case our algorithm is adaptive. Empirically, we confirm that full span recovery is not always possible, but only for unrealistically thin layers. For reasonably wide networks, we obtain full span recovery on both random networks and networks trained on MNIST data. Furthermore, we demonstrate the utility of span recovery as attack by inducing neural networks to misclassify data obfuscated by controlled random noise as sensical inputs.
this paper, we study an important primitive for understanding the
demonstrate that full span recovery is
1 INTRODUCTION
Consider the general framework in which we are given an unknown function f R + E. and we want to learn properties about this function given only access to the value f(x) for different inputs x. There are many contexts where this framework is applicable, such as blackhox optimization in which we are learning to optimize f(x) (Djolonga et al., 2013), PAC learning in which we are learning to approximate f(x (Denis, 1998), adversarial attacks in which we are trying to find adversarial inputs to f(x (Szegedy et al., 2013), or structure recovery in which we are learning the structure of f(x). For example in the case when f(x) is neural network, one might want to recover the underlying weights or architecture (Arora et al., 2014; Zhang et al., 2017). In this work, we consider the setting when f(x) (x) is neural network that admits a latent diw-demnniional structure, namely M(x) oAA)) where A Rxn is rank k matrix for some k < n, and a: R - IR is some neural network. In this setting, we focus primarily on the goal of recovering the row-span of the weight matrix A. We remark that all our results generalize in straightforward manner to the case when A is rank r < k.
Span recovery of general functions f f(x) (AA)), where g is arbitrary, has been studied in some contexts, and is used to gain important information about the underlying function f. By learning Span(A) (A), we in essence are capturing the relevant subspace of the input f; namely, behaves identically on I as does on the projection of onto the row-span of A. In statistics, this is known as effective dimension reduction or the multi-inder model Li (1991); Xia et al. (2002). Another important motivation for span recovery for designing adversarial attacks. Given the span of A, we compute the kernel of A, which can be used to fool the function into behaving incorrectly on inputs which are perturbed by vectors in the kernel. Specifically, if x a legitimate input correctly classified by f and y is a large random vector in the kernel of A, then x + y will be indistinguishable from noise but we will have f(x) = f(x v).

---

Published as a conference paper at ICLR 2020
Several works have considered the problem from an approximatton-theovetee standpoint, where the goal is to output hypothesis function f which approximates f well on a bounded domain. For instance, in the case that A E R is a rank matrix and g (.)) is a smooth function with bounded derivatives, Cohen et al. (2012) gives an adaptive algorithm to approximate f. Their results also give an approximation A to A, under the assumption that A is a stochastic vector (A; 2 0 for each i and E; A; = 1). Extending this result to more general rank k matrices A E TR Tyagi & Cevher (2014) and Fornasier et al. (2012) give algorithms with polynomial sample complexity to find approximations f to twice differentiable functions f. However, their results do not provide any guarantee that the original matrix A itself or a good approximation to its span will be recovered. Specifically, the matrix A used in the hypothesis function [(x) = 7( (r) of Tyagi & Cevher (2014) only has moderate correlation with the true row span of A, and always admits some constant factor error (which can translate into very large error in any subspace approximation).
Furthermore, all aforementioned works require the strong assumption that the matrix of gradients is well-conditioned (and full rank) in order to obtain good approximations f. In contrast, when ((x is a non-differentiable ReLU deep network with only mild assumptions on the weight matrices, we prove that the gradient matrix has rank at least k/2, which significantly strengthens wwwnneeooooooo..o recovery guarantees since we do not make any assumptions on the gradient matrix. Finally, Hardt& & Woodruff (2013) gives an adaptive approximate span recovery algorithm with poly (n) samples under the assumption that the function satisfies a norm- perm-preeerving condition, which is restrictive and need not (and does not) hold for the deep neural networks we consider here.
On the empirical side, the experimental results of Tyagi & Cevher (2014) for function approximation were only carried out for simple one-layer functions, such as the logistic function in one dimension (where A has rank i 1), and on linear functions g" (Ax + b). where y E R has i.i.d. Gaussian entries. Moreover, their experiments only attempted to recover approximations A A when A was orthonormal. In addition, Fornasier et al. (2012) experimentally considers the approximation problem for ff when f f(Ar) is a third degree polynomial of the input. This leaves an experimental gap understanding the performance of span recovery algorithms on non- smooth, multi-layer deep neural networks.
When f(x) is a neural network, there have been many results that allow for weight or architecture recovery under additional assumptions: however nearly all such results are for shallow networks. Arora et al. (2014) shows that layer- wise learning can recover the architecture of random sparse neural networks. Janzamin et al. (2015) applies tensor methods to recover the weights of a two-layer neural network with certain types of smooth activations and vector- valued output, whereas Ge et al. (2019); Bakshi et al. (2019) obtain weight recovery for ReLU activations. Zhang et al. (2017) shows that SGD can learn the weights of two-layer neural networks with some specific activations. There is also line of work for improperly two-layer networks, where the algorithm outputs an arbitrary hypothesis function which behaves similarly to the network under a fixed distribution (Goel et al., 2017; Goel & Klivans, 2019).
Learning properties of the network can also lead to so-called model extraction attacks or enhance classical adversarial attacks on neural networks (Jagielski et al., 2019). Adversarial attacks are often differentiated into two settings, the whitebox setting where the trained network weights are known the blackbox setting where the network weights are unknown but attacks can still be achieved on external information, such as knowledge of the dataset, training algorithm, network architecture, network predictions. Whitebox attacks are well-studied and usually use explicit gradients optimization procedures to compute adversarial inputs for various tasks such as classification and reinforcement learn- ing (Szegedy et al., 2013; Huang et al., 2017; Goodfellow et al., 2014). However, blackbox attacks are more realistic and it is clear that model recovery can enhance these attacks. The work of Paperoot et al. (2017) attacks practical neural networks upon observations of predictions of adaptively chosen inputs, trains a substitute neural network on the observed data, and applies whitebox attack on the substitute. This setting, nicknamed the practical blackbox setting (Chen et al., 2017), is what we work in, as we only observe adaptively chosen predictions without knowledge of the network architecture, dataset, or algorithms. We note that perhaps surprisingly, some of our algorithms are in fact entirely non-adaptive.
1.1 OUR CONTRIBUTIONS
In this paper, we provably show that span recovery for deep neural networks with high precision can be efficiently accomplished with poly(n) function evaluations, even when the networks have poly(n) layers and the output of the network is a scalar in some finite set. Specifically, for deep networks (x) g + IR with ReLU activation functions, we prove that we can recover a subspace V C Span(A) of dimension at least k/2 with polynomially many non-adaptive queries.' First, we use volume bounding technique to show that a ReLU network has sufficiently large pisce-wise linear sections and that gradient information can be derived from function evaluations. Next, by using a
We switch to the notation (x) instead of f(x) to illustrate that M (x)) is neural network, whereas (xx was used to represent general function with low-rank structure.
2

---

Published as a conference paper at ICLR 2020
novel combinatorial analysis of the sign patterns of the ReLU network along with facts in polynomial algebra, we show that the gradient matrix has sufficient rank to allow for partial span recovery.
Theorem 3.4 (informal) Suppose we have the network (())= = w" 6( 1 W W2 Wao(Az))... where A E B is rank k, & is the ReLU and W; E R are weight matrices, with k, possibly much smaller than k. Then, under mild assumptions, there is a non-adaptive algorithu that makes Okn log k) queries to Mxx) and returns in poly(n, -)-timee subspace V S span(A) of dimension at least k 2 with probability 1- 6.
We remark that span recovery of the first weight layer is provably feasible even in the surprising case when the neural network has many "bottleneck" layers with small (log(n)) width. Because this does not hold in the linear case, this implies that the non-linearities introduced by activations in deep learning allow for much more information to captured by the model. Moreover, our algorithm is von-adaptive, which means that the points at which M(x)) needs to be evaluated can be chosen in advance and span recovery will succeed with high probability. This has the benefit of being parallelizable, and possibly more difficult to detect when being used for an adversarial attack. In addition, we note that this result generalize to the case when A is rank r < k, in which setting our guarantee will instead be that we recover subspace of dimension at least _ contained within the span of A.
In contrast with previous papers, we do not assume that the gradient matrix has large rank; rather our main focus and novelty is to prove this statement under minimal assumptions. We require only two mild assumptions on the weight matrices. The first assumption is on the orthant probabilities of the matrix A, namely that the distribution of sign patterns of vector Ag, where g (O,0T,,) is not too far from uniform. Two examples of matrices which satisfy this property are random matrices and matrices with nearly orthogonal rows. The second assumption is a non-degeneracy condition on the matrices W., i, which enforces that products of rows of the matrices W; ; result in vectors with non-zero coordinates.
Our next result is to show that full span recovery is possible for thresholded networks M(x) with twice differentiable activation functions in the inner layers, when the network has 0/1 1 threshold function in the last layer and becomes therefore non-differentiable, i... (xx E {0. Since the activation functionn can be arbitrarily non-linear, our algorithm only provides an approximation of the true subspace Span(A), although the distance between the subspace we output and Span(A) can be made exponentially small. We need only assume bounds on the first and second derivatives of the activation functions, as well as the fact that we can find inputs E I" such that M (x) A 0 with good probability, and that the gradients of the network near certain points where the threshold evaluates to one are not arbitrarily small. We refer the reader to Section 4 for further details on these assumptions. Under these assumptions, we can apply a novel gradient- estimation scheme to approximately recover the gradient of M (z) and the span of A.
Theorem 4.3 (informal) Suppose we have the network M(x) = T()(A))), where T : R - {0, 13 is threshold function and a : IR- >> is a neural network with twice disserentiable activation functions, and such that M satisfies the conditions sketched above (formally defined in Section 4). Then there is an algorithm that runs in poly(N) time, making at most poly(N) queries to M (I), where N = poly(n, (n, k. log( (), log( )). and returns with probability 1 8 subspace V C Ie" of dimension k such that for any x E V, we have
Spant A 1) 2 (1 - e)|1=|12
where P Spann( ( is the orthogonal projection onto the span of A.
Empirically, we verify our theoretical findings by running our span recovery algorithms on randomly generated net- works and trained networks. First, we confirm that full recovery is not possible for all architectures when the network layer sizes are small. This implies that the standard assumption that the gradient matrix is full rank does not always hold. However, we see that realistic network architectures lend themselves easily to full span recovery both ran- dom and trained instances. We emphasize that this holds even when the network has many small layers, for example ReLU network that has 6 hidden layers with [784, 80, 40, 30, 20, 10) nodes, in that order, can still admit full span recovery of the rank 80 weight matrix.
Furthermore, we observe that we can effortlessly apply input obfuscation attacks after successful span recovery and cause misclassifications by tricking the network into classifying noise as normal inputs with high confidence. Specifically, we can inject large amounts of noise in the null space of A to arbitrarily obfuscate the input without changing the output of the network. We demonstrate the utility of this attack on MNIST data, where we use span recovery to generate noisy images that are classified by the network as normal digits with high confidence. We note that this veers away from traditional adversarial attacks, which aim to drastically change the network output with uudeelleu changes in the input. In our case, we attempt the arguably more challenging problem of drastically changing the input without affecting the output of the network.
3

---

Published as a conference paper at ICLR 2020
2 PRELIMINARIES
Notation For a vector x IR,, the sign pattern of r, denoted sign(z) (2) E {0, 1) is the indicator vector for the non- zero coordinates of x. Namely, sign(r); = 1f x; # 0 and sign(z); = 0 otherwise. Given a matrix A E Ruxm we denote its singular values as miin (A) = d minn(n.))
01 (A) T (A). The condition number of A is denoted x(A) Tmax (A) / min (A). We let I, E R=**" denote the n n identity matrix. For a subspace V C R", we write Py E R to denote the orthogonal projection matrix onto V. If E IR" and E E RRax is PSD matrix, we write N (i,, x) to denote the multi-variate Gaussian distribution with mean j and covariance Σ.
Gradient Information For any function f(x) g(Ar), note that Vf(z) = ATg(Ar) must be vector in the row span of A. Therefore, span recovery boils down to understanding the span of the gradient matrix as x varies, Specifically, note that if we can find points :1; ..s such that { (*+)))) are linearly independent, then the full span of A can be recovered using the span of the gradients. To our knowledge, previous span recovery algorithms heavily rely the assumption that the gradient matrix is full rank and in fact well-conditioned. Specifically, for some distribution D, it is assumed that H = Ja-D Vf(z) dr is a rank A matrix with a minimum non-zero singular value bounded below by a and the number of gradient function evaluations needed depends inverse polynomially in a. In contrast, in this paper, when (xx is a neural network, we provably show that H is a matrix of sufficienlly high rank or large minimum non-zero singular value under mild assumptions, using tools in polynomial algebra.
3 DEEP NETWORKS WITH RELU ACTIVATIONS
In this section, we demonstrate that partial span recovery is possible for deep ReL.U networks. Specifically, we consider neural networks (x): I + RR of the form
Mxx) = w" ( W (W Wad(Ar))...
where ((x); = max [ri. 0} is the RELU (applied coordinate wise to each of its inputs), and W, E R and w E RRk,, and A has rank k. We note that ky can be much smaller than k. In order to obtain partial span recovery, we make the following assumptions parameterized by a value y > 0 (our algorithms will by polynomial in 1/7):
Assumption 1: For every sign pattern S {0, 13 we have Pro..N(0.1.)) (ogen(((A))) = 5] 2 7/24.
Assumption 2: For any Si...., Sa + @ where S, S [ki], we have wT [[==((a))
R is entry-wise
non-zero. Here (W;)s, is the matrix with the rows $ S₁ set equal O. Moreover, we assume
Prg-N((.11) (g) = 0] < 2
8"
Our first assumption is an assumption on the orthant probabilities of the distribution Ag. Specifically, observe that Ag E R follows a multi-variate Gaussian distribution with covariance matrix AAT., Assumption 1 then states that the probability that a random vector (O, AA?) lies in certain orthant of I is not too far from uniform. We remark that orthant probabilities of multivariate Gaussian distributions are well-studied (see e.g., Miwa et al. (2003); Bacon (1963); Abrahamson et al. (1964)), and thus may allow for the application of this assumption to a larger class of matrices. In particular, we show it is satisfied by both random matrices and orthogonal matrices. Our second assumption is a non-degeneracy condition the weight matrices W, - namely, that products of w" with non-empty sets of rows of the W, result in entry-wise non-zero vectors. In addition, Assumption 2 requires that the network is non-zero with probability that not arbitrarily small, otherwise we cannot hope to find even a single with M (x) # 0.
In the following lemma, we demonstrate that these conditions are satisfied by randomly initialized networks, even when the entries of the W; are not identically distributed.
Lemma 3.1. If A E Rixn is an arbitrary matrix with orthogonal rows, or if n > 22kk) and A has entries that are drawn i.i.d. from some mub-Gaussion distribution DD with expectation O, unit variance, and constant sub- Gaussian norm | = supp21 P 10pp1p1/// 1/2 X(P) then with probability at least 1 - -k² A satisfies Assumption I with 2 1/2. Moreover, if the weight matrices w, W1, W Wa with W; E BBxxk41 have entries that are drawn independently (and possibly non-identically) from continuous symmetric distributions, and if ki 2 log( 5n ) each
16d
i E [d], then Assumption 2 holds with probability 1 6- 8.
3.1
ALGORITHM FOR SPAN RECOVERY
The algorithm for recovery is given in Algorithm 1. Our algorithm computes the gradient ( for different Gaussian vectors gi (0, 4R), and returns the subspace spanned by these gradients. To implement this procedure,
4

---

Published as a conference paper at ICLR 2020
Algorithm 1: Span Recovery with Non-Adaptive Gradients
Input: function M(x) : R -> RR, kt latent dimension, 7: probability parameter
Set r Ok (og()))>)
2 for = .......,00 do
Generate random Gaussian vector g' ~ In) Compute Gradient: 2 (g'
3
Lemma 3.2
end
return Span (2' (=1, ,=, 3..r,
we must show that it is possible to compute gradients via the perturbational method (i.e. finite differences), given only oracle queries to the network M. Namely, we firstly must show that if g (N, I,) then V. exists, and moreover, that V.M (z) exists for all æ E (g).). where (g) is a ball of radius centered at g. and e e some value with polynomial bit complexity which we can bound. To demonstrate this, we show that for any fixing of the sign patterns of the network, we can write the region of R which satisfies this sign pattern and is c-close to one of the (ddk) ReLU threshoids of the network as a linear program. We then show that the feasible polytope of this linear program contained inside a Euclidean box in R", which has one side of length e. Using this containment, we upper bound the volume of the polytope in R" which is close each ReLU, and union bound over all sign patterns and ReLUs to show that the probability that a Gaussian lands in one of these polytopes is exponentially small.
Lemma 3.2. There is an algorithm which, given g NO, Ik), with probability 1 1 exx(p-ndn for any constant 1 (over the randomness in g). computes (g) E IR" with (n) queries to the network, and in poly(n) runtime.
Now observe that the gradients of the network lie in the row-span of A. To see this, for given input R", let So(x) E IR* be the sign pattern of Φi Ax) E RR*, and more generally define Sz(x) E Rea via
Sz(x) sign o ( o W Wii1((.... Wad(Az)) ...))
Then (x = (w_ III. (W,) ) s)) which demonstrates the claim that the gradients lie in the row-span of A. Now define 2' Vgggg) where g" (O, I,.). and let Z be the matrix where the i-th row is equal to 2, We will prove that Z has rank at least k/2. To see this, first note that we can write Z = VA, where V is some matrix such that the non-zero entries in the i-th row are precisely the coordinates in the set S where S Sy(g") ) for any j 0, 0, 2,,, d and i = 1, 1,2....,7. T. We first show that V has rank at least ck for a constant > 0. To see this, suppose we have computed r gradients far, and the rank of V is less than ck for some 0 < 1/2. Now V E B is a fixed rank-ck matrix, so the span of the matrix can be expressed as a linear combination of some fixed subset of ck of its rows. We use this fact to show in the following lemma that the set of all possible sign patterns obtainable in the row span of V is much smaller than 2*. Thus gradient t1* with a uniform (or nearly uniform) sign pattern will land outside this set with good probability, and thus will increase the rank of Z when appended.
Lemma 3.3. Let V E B be a fixed al most rank ck matrix for S 1/2. Then the number of sign patterns S C [k] with at most k:/2 non-zeros spanned by the rows of V is at most 2 In other words, the set S S(V) = (sign(w) | w E Vi
span(V) nnz(ww < }) has size at most VE²
2/
Theorem 3.4. Suppose the network ((x) = w (W2 Wad(Ax)) Assumptions and 2. Then the algorithm given in Figure makes Okn log k (//)/7) queries M(x) and returns in poly(n, k, log(1/)) time subspace V S span(A) of dimension at least 2 with probability 1 8.
where 6 is the ReLU, satisfies
&
4 NETWORKS WITH THRESHOLDING ON DIFFERENTIABLE ACTIVATIONS
In this section, we consider networks that have threshold function at the output node, as is done often for classifica- tion. Specifically, let 7 {0, 1} be the threshold function: T T(x) 1 if 2 1, and r(z) = otherwise. Again,
we let A E B where ls < n. be the innermost weight matrix. The networks M R. - IR we consider are then of the form:
M(x) (W e
AlAx))...
where W, E X and each Φ; a continuous, differentiable activation function applied entrywise to its input. We will demonstrate that even for such functions with binary threshold placed at the end, giving us minimal information about the network, we can still achieve full span recovery of the weight matrix A, albeit with the cost of an 6- approximation to the subspace. Note that the latter fact is inherent, since the gradient of any function that is not linear
5

---

Published as a conference paper at ICLR 2020
in some ball around each point cannot be obtained exactly without infinitely small perturbations of the input, which we do not allow in our model.
We can simplify the above notation, and write (ar) = Wi (W202(... Ar)) and thus M(x) = (x)(
...), (Weeb(...@AA))).-
Our algorithm will involve building a subspace V C IE which is a good approximation to the span of A. At each step, we attempt to recover new vector which is very close to vector in Span(A), but which is nearly orthogonal to the vectors in V. Specifically, after building V. on an input x E R", we will query M for inputs M ((I,- - 2v)x). Recall that Pv is the projection matrix onto V. and Pv is the projection matrix onto the subspace orthogonal to V. Thus, it will help here to think of the functions M, a as being functions of x and not (I, Dv and so we define oy (z) (I Py)z), and similarly (x (z)v For the results of this section, make the following assumptions on the activation functions.
Assumptions:
R 2. Φ and 0 are L,-Lisschitz, meaning:
1. The function Ø; : : - R is continuous and twice differentiable, and (i( = O.
d2 d2r
sup =E dr (1( S Li,
sup ZER
(x(x)
S L,
3. The network is non-zero with bounded probability: for every subspace V C 1 of dimension dim < k. we have that Prg-W(o...) [ov 2 1] 2 y for some value 7 > O.
Gradients are not arbitrarily small near the boundary: for every subspace V C R of dimension dim (V) < k
Pr Pro.))(o...) V (cg)) 2 n, Vc > 0 such that oy (eg) = 1, and ov 2 1] 27
for some values 7 > 0, where V Vy (eg) is the directional derivative of σv in the direction g.
The first two conditions are standard and straightforward, namely Φ; is differentiable, and has bounded first and second derivatives (note that for our purposes, they need only be bounded in a ball of radius poly(n)). Since M(x) is a threshold applied to (z), the third condition states that it is possible to find inputs with non-zero network evaluation (z). Our condition is slightly stronger, in that we would like this to be possible even when æ is projected away from any k' < k dimensional subspace (note that this ensures that Az is non-zero, since A has rank k:).
The last condition simply states that if we pick a random direction g where the network is non-zero, then the gradients of the network are not arbitrarily small along that direction at the threshold points where o(c g) 1. Observe that if the gradients at such points are vanishingly small, then we cannot hope to recover them. Moreover, since M only changes value at these points, these points are the only points where information about can be learned. Thus, the gradients at these points are the only gradients which could possibly be learned. We note that the running time of our algorithms will be polynomial in (og(1))). and thus
even allow the gradient size 1) to be exponentially small.
4.1 THE APPROXIMATE SPAN RECOVERY ALGORITHM
We now formally describe and analyze our span recovery algorithm for networks with differentiable activation func- tions and 0/1 thresholding. Let K2 be the condition number of the i-th weight matrix W,, and let 5 > be a failure probability, and let 6 0 be precision parameter which will affect the how well the subspace we output will ap- proximate SA) Now fix N poly(n, k 1 E log(L.), Σ log(ks), log( log) log())) The running time and query complexity of our algorithm will be polynomial in N. Our algorithm for approximate span recovery is given formally in Algorithm 2.
Proposition 4.1. Let V C RRn be a subspace of dimension K' < k, and fix any cg > O. Then we can find vector x < 2eD in expected O(1/r + N 'log(1/es) (o)) time. Moreover, with probability 7/2 we have that
with 0 < σv (z) (x) > n// 4 and the tighter bound of 2on2 <ov(z) - 1 25g.
We will apply the above proposition input to the following Lemma 4.2, which is the main technical result of this section. Our approach involves first taking the point a from Proposition 4.1 such that ov (z) is close but bounded away from the boundary, and generating n perturbations at this point My (x + u.) for carefully chosen u, While we do not know the value of or (x + u.), we can tell for given scaling > if By (x + cu.) has crossed the boundary, since we will then have My (I + cu;) = Thus, we can estimate the directional derivative V,, by finding value c, via binary search such that ov (z + czuz) is exponentially closer to the boundary than (v().. In order for our estimate to be accurate, we must carefully upper and lower bound the gradients and Hessian of a near x,, and demonstrate that the linear approximation of o, at is still accurate at the point x + C.U4 where the boundary is crossed. Since each
6

---

Published as a conference paper at ICLR 2020
Algorithm 2: Span Recovery With Adaptive Gradients
V - 6, N poly(n, k y Σ (og(L;), Ei log(ns), log( )) log( ()), Iog(( (]): co 2 2-Poly(N)
2 for = ..... do Generate 9 ~ (0, (n) until (I,, Pv)g) =
4
Find a scaling a > 0 via binary search on values T(ov (ag)) such that x = og satisfies
601)2 2 (v) 1 < 2en-
> Proposition 4.1
5 Generate I1..... ~ (O In), and set u, = (g.2 x/ x/||>>| /=]l)=
6
For each E [n], binary search over values to find &; such that
- B ov + c.u)
where 5 = 2 N²
7 If any & satisfies [c]] 2 (10-3 N "e/n), restart from line 5 (regenerate the Gaussian g). Otherwise, define E _=x via B., uy, where B, is the i-th column of B. Define E R by b, 1/c.
8
Let y" be the solution to:
min vER"
11 B b5
Set U, = yy and V <- -Span vz).
end I1 return V
value of l/c, is precisely proportional to V a. (() (z), us), can then set up linear system approximately solve for the gradient Vo(x) (lines and of Algorithm 2).
Lemma 4.2. Fix any e, 8 > O, and let N be defined above. Then given any subspuce V C Re with dimension dim(V) k; and given E IR", such that con2-N N I <ov(x) - S 2co where co O(2-N' No /c) for sufficiently large constant = O(),,, and such that V > 122,, then with probability
2 N/n² we can find a vector Rn in expected NNly(N) time, such that |IP Span(A)"|l2 2 (1 ()lwllll and such that |Pvull2 S <cluu|2.
Theorem 4.3. Suppose the network M (xx) = ((o()))) satisfies the conditions described at the beginning of this section. Then Algorithm runs in poly(N) time, making at most poly(N) queries M(x), where N poly(n, k, b, Ei (og((T.),, Eiznlog (R:), log(z)) log(2), (o))log())) ()), and returns with probability 1 a subspace V C Rn" of dimension l such that for any x E V, we have [P (Span(A)= 2 (1 |2/12
5 EXPERIMENTS
Rank with GradientsRandom
Rank with GradientsRandomkda
Rank with GradientsMNIST
80
70
70
70
60
60
50
50
50
40
3 40
40
30
30
ley: 784-5-0-==[]
ley: 784-580-=1]
ley: 784--80->[]
20
bay: 784-280->16,,
20
lay: 784-380->16,,
20
lay: 784-5-80>11,
10
lay: 784->80->16, 2]
lay: 784->80->16. 3]
lay: 784--80-2166
ley: 784->80-=16, 2,
784:>80-=16, 3,
784- =[60002[6660000 4,
200
400
600
600
200
400
600
800
200
400
600
800
Danberr
Figure 1: Partial span recovery of small networks with layer sizes specified in the legend. Note that 784->80->(6.3 indicates a 4 layer neural network with hidden layer sizes 784, 80, 6, and 3, in that order. Full span recovery is not always possible and recovery deteriorates width decreases and depth increases.
7

---

Published as a conference paper at ICLR 2020
Rank with Gradiantskandom
Rank with GradiontskandomAks
Rank with GradiantssMNSI
70
70
60
50
50
3
lay: 784->80->11
tay: 784->80->11
30
lay: 784->80->11
lay: 784-=80->x100
lay: 784->80-=[10]
lay: 784-5-80=x140)
20
lay: 700-200-00-000 30]
20
lay: 740- 30]
20
lay: 784-=80==100 30]
lay:
3c,
lay: >(40,
lay:
lay: 784-280->(40,, 36, 20,
lay: 740. 30, 20,
lay: 784.2-80->140, 30, 20.
0 200
400
600
800
0
200
401
600
800
200
400
608
800
FRambrr Samp
Rarbor of Sample
Narbo Samplt
Figure 2: Full span recovery of realistic networks with moderate widths and reasonable architectures. Full recovery occurs with only 100 samples for a rank 80 weight matrix in all settings.
When applying span recovery for a given network, we first calculate the gradients analytically via auto-differentiation at fixed number of sample points distributed according to standard Gaussian. Our networks feedforward, fully-connected with ReLU units; therefore, as mentioned above, using analytic gradients as precise as using finite differences due piecewise linearity. Then, we compute the rank of the resulting gradient matrix, where the rank is defined to be the number of singular values that are above le-5 of the maximum singular value. In our experiments, we attempt to recover the full span of a 784-by-80 matrix with decreasing layer sizes for varying sample complexity, as specified in the figures. For the MNIST dataset, we use a size 10 vector output and train according to the softmax cross entropy loss, we only calculate the gradient with respect the first output node.
Our recovery algorithms are GradientsRandom (Algorithm 1), FradientsRandomAAde (Algorithm 2), and Gradients.M- NIST. GradientsRandom a direct application of our first span recovery algorithm and calculates gradients via pertur- bations at random points for random network. GradientsRandom. random network. Finally, GradientsMNIST an application GradientsRandom on a network with weights trained MNIST data. In general, note that the experimental outcomes very similar among all three scenarios.
uses our adaptive span recovery algorithm for
Pred 2 at 97%
Pred 0 at 99%
Pred at 99%
Pred 9 98%
Pred at 99%
Pred 7 99%
Pred at 99%
Pred 7 at 97%
2
9
9
7
20
20
20
22
20
Pred 97%
Pred 0 at 99%
Pred 99%
Pred 9 98%
Pred at 99%
Pred 7 99%
Pred at 99%
Pred 7 97%
20
10
10
Figure 3: Fooling ReLU networks into misclassifying noise as digits by introducing Gaussian noise into the null space after span recovery. The prediction of the network presented above the images, along with its softmax probability.
For networks with very small widths and multiple layers, we that span recovery deteriorates as depth increases, supporting our theory (see Figure 1). This holds both in the case when the networks are randomly initialized with Gaussian weights or trained on a real dataset (MNIST) and whether we use adaptive or non-adaptive recovery algo- rithms. However, we note that these small networks have unrcalistically small widths (less than 10) and when trained on MNIST, these networks fail to achieve high accuracy, all falling below 80 percent. The small width case there- fore only used to support, with empirical evidence, why our theory cannot possibly guarantee full span recovery under every network architecture.
For more realistic networks with moderate or high widths, however, full span recovery seems easy and implies real possibility for attack (see Figure 2). Although we tried variety of widths and depths, the results are robust to reasonable settings of layer sizes and depths. Therefore, we only present experimental results with sub-networks of
8

---

Published as a conference paper at ICLR 2020
network with layer sizes [784, 80, 40, 30, 20, 10]. Note that full span recovery of the first-layer weight matrix with rank 80 achieved almost immediately in all cases, with less than 100 samples.
On the real dataset MNIST, we demonstrate the utility of span recovery algorithms as an attack to fool neural networks to misclassify noisy inputs (see Figure 3). We train a ReLU network (to around 95 percent aceuracy) and recover its span by computing the span of the resulting gradient matrix. Then, recover the null space of the matrix and generate random Gaussian noise projected onto the null space. We see that our attack successfully converts images into noisy versions without changing the output of the network, implying that allowing full (or even partial) span recovery on a classification network can lead to various adversarial attacks despite not knowing the exact weights of the network.
ACKNOWLEDGMENT
The authors Rajesh Jayaram and David Woodruff would like to thank the partial support by the National Science Foundation under Grant No. CCF-1815840.

---

Published as a conference paper at ICLR 2020
REFERENCES
IG Abrahamson et al. Orthant probabilities for the quadrivariate normal distribution. The Annals of Mathematical Statistics, 35(4):1685-1703, 1964.
Sanjeev Arora, Aditya Bhaskara, Rong Ge, and Tengyu Ma. Provable bounds for learning some deep representations. In International Conference Machine Learning, pp. 1884599,70 2014.
Ralph Hoyt Bacon. Approximations to multivariate normal orthant probabilities. The Annals of Mathematical Statis- tics, 34(1):191-198, 1963. ISSN 00034851. URL http: /wwww jstor. .ertor.org/.o..... sttableee99129999
Ainesh Bakshi, Rajesh Jayaram, and David P Woodruff. Learning two layer rectified neural networks in polynomial time. In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Thirty-Second Conference Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. 195-268, Phoenix, USA, 25-28 Jun 2019. PMLR. URL http: / http::///rrcceeee httpp//ooeeeennnn///ee/ee .mlr... press/ /ve/ss/v/9/ bakshillllli. 19.. html.
Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order optimization based black- box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15-26. ACM, 2017.
Albert Cohen, Ingrid Daubechies, Ronald Vore, Gerard Kerkyacharian, and Dominique Picard. Capturing ridge functions in high dimensions from point queries. Constructive Approximation, 35(2):225 243, 2012.
Nicholas Cook et al. Lower bounds for the smallest singular value of structured random matrices. The Annals of Probability, 46(6):3442-3500, 2018.
François Denis. Pac learning from positive statistical queries. In International Conference on Algorithmic Learning Theory, pp. 112-126. Springer, 1998.
Josip Djolonga, Andreas Krause, and Volkan Cevher. High-dimensions gaussian process bandits. In Advances in Neural Information Processing Systems, pp. 1025-1033, 2013.
Massimo Fornasier, Karin Schnass, and Jan Vybiral. Learning functions of few arbitrary linear parameters in high dimensions. Foundations of Computational Mathematics, 12(2):229 262, 2012.
Rong Ge, Rohith Kuditipudi, Zhize Li, and Xiang Wang. Learning two-layer neural networks with symmetric inputs. In International Conference on Learning Representations, 2019.
Surbhi Goel and Adam R. Klivans. Learning neural networks with two nonlinear layers in polynomial time. In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. 1470-1499, Phoenix, USA, 25-28 Jun 2019. PMLR. URL battp://prcceedeee
mlr press 9999//99///// goeeolllee
html.
Surbhi Goel, Varun Kanade, Adam Klivans, and Justin Thaler. Reliably learning the relu in polynomial time. In Conference on Learning Theory, pp. 1004-1042, 2017.
lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 47X65:1412.6572, 2014.
H Tracy Hall, Leslie Hogben, Ryan Martin, and Bryan Shader. Expected values of parameters associated with the minimum rank of a graph. Linear Algebra and its Applications, 133(1):101-117, 2010.
Moritz Hardt and David P Woodruff. How robust are linear sketches to adaptive inputs? In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 121-130. ACM, 2013.
Sandy Huang. Nicolas Papernot, Ian Goodfellow, Yan Duan, and Picter Abbeel. Adversarial attacks on neural network policies. arXiv preprint arXiv:1702.02288, 2017.
Matthew Jagielski, Nicholas Carlini, David Berthelot, Alex Kurakin, and Nicolas Papernot. High-fidelity extraction of neural network models. arXiv preprint
2019.
Majid Janzamin, Hanie Sedghi, and Anima Anandkumar. Beating the perils of non-convexity: Guaranteed training of neural networks using tensor methods. arXiv preprint arXiv: arXiv:1506.08.. 1506.08463..,7 2015.
10

---

Published as conference paper at ICLR 2020
B. Laurent and P. Massart. Adaptive estimation of quadratic functional by model selection. Amn. Statist., 2805):1302 1338, 10 2000. doi: 105515999 URL https:
Ker-Chau Li. Sliced inverse regression for dimension reduction. Journal of the American Statistical Association, (414):316 327, 1991. ISSN 01621459. URL http:/ http::///wwwwww jator..sst...... httpe//tttgttabboototeeteeb.aaet aataablee22995555
Tetsuhisa Miwa, AJ Hayter, and Satoshi Kuriki. The evaluation of general non-centred orthant probabilities. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 65(1):223-234, 2003.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pp. 506-519. ACM, 2017.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.
Hemant Tyagi and Volkan Cevher. Learning non-parametric basis independent models from point queries via low-rank methods. Applied and Computational Harmonic Analysis, 37(3)3389-412, 2014. 2014
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv: 2010.
Yingcun Xia, Howell Tong, Wai Keungxs Li, and Li-Xing Zhu. An adaptive estimation of dimension reduction space. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 64(3):333-410, 2002.
Qiuyi Zhang, Rina Panigrahy. Sushant Sachdeva, and Ali Rahimi. Flectron-proton dynamics in deep learning. arXiv preprint arXiv: pp. 1-31, 2017.

---

Published as a conference paper at ICLR 2020
A MISSING PROOFS FROM SECTION 3
We first restate the results which have had their proofs omitted, and include their proofs subsequently.
Lemma 3.1 If E TR has orthogonal rows, or if a > 2(k-2) and A has entries that are drawn i.i.d. from some Sab-Gaussian distribution DD with expectation O, unit variance, and constant sub- gaub-gaussinn norm ||
supp21 p p1/2 (Ex~D|X(p)* /p then with probability at least - e-hh A satisfies Assumption wwith 7 2 1/2.
Moreover, if the weight matrices W1, W2,... Wa with W, E BRiiku+ have entries that are drawn independently (and possibly non-identically) from continuous symmetric distributions, and if his 2 loo( 8y for each i E [d]. then Assumption holds with probability 1 8.
Proof. By Theorem 5.58 of Vershynin (2010), if the entries A are drawn i.i.d. from some sub-Gaussian isotropic
distribution D over R" such that ||,|| v almost surely, then v CVT - m (m) S max (A) vn + CVk + t with probability at least - 2e -e for some constants c, C > 0 depending only on || Since the entries are i.i.d. with variance 1, it follows that the rows of A isotropic. Moreover, we can always condition
on the rows having norm exactly vn, and pulling out a positive diagonal scaling through the first Relu of Mx), and absorbing this scaling into Wd. It follows that the conditions of the theorem hold, and we have vn CVk S
mmin (A) T max (A) S /n + CVk with probability at least 1 e - for suitably large scaling of the constant C. Setting n > (1.2). ). it follows that k(A) < (1 + 1/(100k)), which holds immediately if A has orthogonal rows.
Now observe that Ag is distributed multi-variate Gaussian with co- co-variance A A, and is therefore given by the probability density function (pdf)
1 x (~ Ar
p'(x) = (2r) exp
Let p(x) = (27)=72 exp (- x) be the pdf of an identity covariance Gaussian A (0, 1R). We lower bound p((x)/((x)
for with ||=1| S 16k. In this case, we have
px(x)
( (TTATAD - -1x01()
exp
p(x)
det ATT(A2
1
2*(A)-+ - cxp
(1=:1/(1 + 1/(100k)) 1|=01
2
1
2*(A)** exp
- 1=/=11/11110)
(1)
2(1+ 2(1+1/ 1/(00)))) - cxp
2 (16/100)
2(1 + +1/(100k)) exp
(16/100)
21/2
Thus for any sign pattern S, Pr(sign(Ag) S | k) Pr(ssig((g) S | < k). Now
Pr(sign(g) g) S - and spherical symmetry of Gaussians, Pr (glsign(g) = S : |6 < k] 2-k and thus Prisign Ag) = S Ag
_ < k] > k Now ||Agll < 2|g 13 which is distributed as x" random variable with kedegress of freedom. By standard concentration results for x² distributions (Lemma 1 Laurent & Massart (2000)), we have Pr|llg|3 > 8k) < e 2k so Pr[]| 2 > 16k] < Prillel1 2 8k] < e 2k By a union bound,
Pr(sign(Ag) S : || 2 < k] 2 2 k-1 2k 7 = 1/4.
I2 which completes the proof of the first claim with
4
For the second claim, by an inductive argument, the entries in the rows i E Sj of the product W [T w)ss)
are drawn from a continuous distribution. Thus each column of W s, ( (W.=))(W.sss)) is non-zero with probability
1. It follows that (w. [ (W.)s.) ) is the inner product of a non-zero vector with vector w with continuous,
12

---

Published as a conference paper at ICLR 2020
independent entries, and is thus non-zero with probability 1. By a union bound over all possible non-empty sets S,. the desired result follows.
We now show that the second part of Assumption 2 holds. To do so, first let g ~ (O, T.). We demonstrate that Frw,.W...... W..g a.g (M) = 0] S 22/1100. Here the entries of the W,'s s are drawn independently but not necessar- ily identically from continuous symmetric distribution. To see this, note that can condition on the value of g. and condition at each step on the non-zero value of y/i =
Then, over the randomness of W, note that the inner product of row of W; and is strictly positive with probability at least 1/2, and so each coordinate of Wa Way is strictly positive independently with probability 2 1/2. It follows that @i (Wyk) is non probability at least - 2 R; Thus
non-zero zero with
Prw,, Wa Wa..., Waig [M(g + 0J 2 II
(1 - 2-ki)
1=1
(2)
87
2
16d
2 1 87/8
where the second inequality is by assumption. It follows by our first part that
Wa.... Wa.g (g) = 0] - 67/8
So by Markov's inequality,
Prw,, Wa.... B.....WW Wa Prg (M = 0j 2 7/8 8
Thus with probability - 5 over the choice of WI,..., Wd. we have Pr, (M = 0] S 7/8 as desired.
Lemma 3.2 There an algorithm which, given g ~ NO, Te), with probability e-exp_-n") for any constant >> (over the randomness in g), computes (g) E IR" with ((n) queries to the network, and in poly(n) running time.
Proof. Let = o W W411(.... (..6666...... ((xx) where & is the ReLU. If VM(g) exists, there is an e > O such that M is differentiable (g). We show that with good probability, if g (0, In) (or in fact, almost any continuous distribution), then M (g) is continuous in the ball (g) = {x E R" I gll2 E} for some e which we will now compute.
First, we can condition on the event that ||91 < (nd))0c, 10c, which occurs with probability at least 1 - exp(-(nd)) by concentration results for x2 distributions Laurent & Massart (2000). Now, fix any sign pattern S, S [k.] for the i-th We note that we can enforce the constraint that for an input x E RR, the sign pattern of M2(x)) precisely S,. To see this, note that after conditioning on a sign pattern for each layer, the entire network becomes linear. Thus each constraint that ((W:),.+ M Me+1 (x)) 2 0 or ((W.),,+, M (x)) < can be enforced as a linear combination of the coordinates of x.
layer Mz)x) o( W (o(..... (ő(Ar)..
and let S = S Sa+1).
Now fix any layer E [d + 1] and neuron j [ki], WLOG j E S. We now add the additional constraint that ((W)),,r M (x)) < 7), where = exp(- (poly(nn)) is a value we will later choose. Thus, we obtain a linear program with h: + Σd= k; constraints and variables. The feasible polytope P represents the set of input points which satisfy the activation patterns S and are y-close to the discontinuity given by the j-th neuron in the i-th layer.
We can now introduce the following non-linear constraint on the input that ||æ||| S (nd)) Let B = Bi ( (0) be the feasible region of this last constraint, and let P P B. We now bound the Lesbegue measure (volume) V(P*) of the region P. First note that V VP*) S V(P)), where V (P') is the region defined by the set of points which satisfy:
(y. x) 2 0 (y, x) < 1
(3)
| < (nd) 10c
where each coordinate of the vector y E R is linear combination of products of the weight matrices W., 2 i. One can see that the first two constraints for P' are also constraints for Pt and the last constraint precisely B, thus px c. p' which completes the claim of the measure of the latter being larger. Now we can rotate P' by the rotation
13

---

Published as a conference paper at ICLR 2020
which sends y - llull2-e1 E I= without changing the volume of the feasible region. The resulting region is contained in the region pd given by
5 Φ S n S (nd) 10c
(4)
Finally, note that p" CR" is Eucledian box with -1 side lengths equal to (nd) 10c and one side length of |lylln. and thus ((P") S [Ivll2n((dd) Now note we can assume that the entries of the weight matrices A, W Wi...., Wa are specified in polynomially many (in n)) bits, as if this were not the case the output (zr of the network would not have polynomial bit complexity, and could not even be read in poly(n) time. Equivalently, we can assume that our running time is allowed to be polynomial in the number of bits in any value of (z). since this is the size of the input to the problem. Given this, since the coordinates of were linear combinations of products of the coordinates of the weight matrices, and note that each of which is at most 2nd for some constant C' (since the matrices have polynomial bit-complexity), we have that P < 1/2 (nd) 10ne needed.
Now the pdf of a multi-variate Gaussian is upper bounded by 1, so Pr Prog~W(0.L.) by E E S V(P") S 112n (nd) 10nc It follows that the probability that a multivariate Gaussian g .N(0, satisfies the sign pattern S and rj close to the boundary for the j-th neuron in the i-th layer. Now since there are at most 2 I 2 < 2nd possible combinations of sign patterns S, it follows that the the probability that a multivariate Gaussian g E N I,) is vj close to the boundary for the j-th neuron in the i-th layer is at most 172" (ud)10ne2nd, Union bounding over each of the k; neurons in layer i, and then each of the d layers, it follows that g (N, In) is 17 close to the boundary for any discontinuity in (x) is at most 1 (nd)10ne+12rd Setting 7) S 2(nd)2ec+))2 2-="" it follows that with probability at least exp(-(nd))) the network evaluated at g (0, In) is at least 17 close from all boundaries (note that C' is known to us by assumption).
Now we must show that perturbing the point y by any vector with norm at most results in a new point g' which still has not hit one of the boundaries. Note that M (g) is linear in an open ball around g. so the change that can occur in any intermediate neuron after perturbing by some E I is at most || 12 I [| ll2, where || 2l2 is the spectral norm. Now since each entry in the weight matrix can be specified in polynomially many bits, the Frobenius norm of each matrix (and therefore the spectral norm), is bounded by 222 for some constant C. Thus
d
|| II W. S (n (n²2n ( p++1= =
2=1
and setting = n/B, it follows that (xx is differentiable in the ball (xx) as needed.
We now generate U1, U2, ...., Un (0, In), which are linearly independent almost surely. We set v; = 2 M. Since M (g) is ReLU network which is differentiable on (g)g), it follows that (() is a linear function on (g), and moreover U; (g) for each i [n]. Thus for any c we have Mig)-M(g
cd.
Vey (zr), thus we can compute V., (x) for each i E [n]. Finally, since the directional derivative is given by V., (x) = (VM(x), ca/l/u/]l2). and since Ul..... Un are linearly independent, we can set up a linear system to solve for V (x) exactly in polynomial time, which completes the proof.
Lemma 3.3 Let V E Brx be a fixed at most rank ck matrix for e S 1/2. Then the number sign patterns S C [ with most k/2 non-zeros spanned by the rows of V is at most 2* In other words, the set S(V) (sign(w) w e Vk'
(pan(V), nn)(ww) < }}} has size at most 2 Vi
Proof. Any vector w in the span of the rows of V can be expressed as linear combination of at most ck rows of V. So create a variable x; for each coefficient E [ck]] in this linear combination, and let S, (1x) be the linear function of the a/s which gives the value of the j-th coordinate of w. Then f(x) (fi (z)...... f((z)) ) is a k-tuple of polynomials, each in ck-variables, where each polynomial has degree 1. By Theorem 4.1 of Hall et al. (2010), it follows that the number of sign patterns which contain at most k/2 non-zero entries is at most ( ck
Setting c S 1/2, this is at
most (x/2) < Vie
Theorem 3.4 Suppoxe the network M(x) = w (WWWi@WW20 Wao(Ax) (Ax))...). where & is the ReLU, satisfies Assumption 1 and 2. Then the algorithm given in Figure I makes O(kn (og(k/))/>) queries to M(x) and returns in poly(n, k, 1/7, log(1/ (/)) --tmme time subspace V C span( of dimension at least & with probability 1 - 8.
14

---

Published as a conference paper at ICLR 2020
Proof. First note that by Lemma 3.2. we can efficiently compute each gradient (g using (n)) queries to the network. After querying for the gradient = (g'')) for r' S r independent Gaussian vectors g" E IR", we obtain the vector of gradients Z = V A gr' xk Now suppose that V had rank ck for some с S 1/2. Now consider the gradient V(g"*+1,, +1), which can be written as 2 = wT (W.))))) Diag(sign( (Ag" (Ag + Thus we can write 2''11 +1 = V where V E R is a row vector which will be appended to the matrix V to form new Z = VA E +R*++ after the (r' + 1)-th gradient is computed. Specifically, for any E [r]. we have: V,= = nD [I (Wa)) Diag(sign(Ag').
Let Ep4+1 be the event that M(g"++1) + O. It follows necessarily that, conditioned E,+,, have that sign Vr+1) = So The reason is as follows: if (gg + * 0, then we could not have S/ = for any j E {0, 1,,,...,,d dd. since this would result in M(g O. It follows that the conditions for Assumption 2 to apply hold, and we have that w² (IT2 (W sggg RR is entry-wise non-zero. Given this, it follows that the sign pattern
of
d II (WW))(+) s7411 Diag(sign(Ag'))
V P++ = w²
will be precisely 5% s5'+1 needed.
Now by Lemma 3.3, the number of sign patterns of ks-dimensional vectors with at most k/2 non-zero entries which are contained in the span of V is at most Vi. Let S be the set of sign patterns with at most k/2 non-zeros and such that for every S E S, S is not a sign pattern which can be realized in the row span of V. It follows that [S] 2 2 2 have Pr siign Ag" +1 E S, Ep+t| 2 7/8
2 12 so by Assumption 1, we have that Pr (iign(Ag" +1) E s] 2 7/4. By union bound, we
vI
Conditioned on (Ag" +1 E 5) and E,1 simultaneously, it follows that adding the row vector V to the matrix V will increase its rank by 1. Thus after (log(k//)//)) repetitions, the rank of V will be increased by at least with probability 1 - 5/k. By union bound, after after r = Olk (og(k/5)/7), V E Brxk will have rank at least k/2 with probability at least - 5, which implies that the same will hold for Z since rank(Z) 2 rank(V), which is the desired result.
B MISSING PROOFS FROM SECTION 4
Proposition 4.1 with
Let V R be subspace of dimension ke' < k. and fix any co > 0. Then we can find vector x
0 < (x) - S 260
in expected O log(L/eo) time. Moreover, with probability 7/2 we have that Vzov(z) n/4 4 and the tighter bound of
6072 N <ov(z) - -15 260
Proof. We begin by generating Gaussians I1.... and computing (g:).)) By Property 3 of the network assumptions, we need only repeat the process 1/y times until we obtain an input y (I,, Pv)g: with M(y) Mv = 1.
Since all activation functions satisfy Φ)(0)) = O, we know that ov(0 9:) = 0, and σv (gi) = 1. Since o is continuous, it follows that Vn, (c)- = (v g:) is a continuous function 1h : R + IR. By the intermediate value theorem, there
NN time O(N log(1 (g(()) exists a <1 1 such that ov (v g:) = 1. We argue we can find a with |e le- c²I S 6o2-N
To find we can perform binary search. We first try co = 1/2, and if gg. (co) O. we recurse into [1/2, 1], otherwise if &g. (Cu)
we recurse into [0, 1/2). Thus, we always recurse into an interval where V.g switches values. follows that we can find a with |c - c² S collgil122 2 in time O log([19
for some c* with
ov (c" = 1. Now observe that it suffices to binary search total of O(N log([le:]|2/ /oo) times, since 2 is upper bound on the Lipschitz constant of var which gives S (eg.) 1 S 6o- Now the expected running time to do this is (11/ + N log(llg, 1/112//2//// 220))), but since ||g.112 has Gaussian tails, the expectation of the maximum value of [| l| over
15

---

Published as a conference paper at ICLR 2020
1/r repetitions is ((log(//)))m), and thus the expected running time reduces to the stated bound, which completes the first claim of the Proposition.
For the second claim, note that V Vv gi) > 0 by construction of the binary search, and since ov > 0 = 1, Øy On log(1/?)) (see Lemma 1 Laurent & Massart (2000)), so by union bound both of these occur with probability 7/2. Now since II(c* - c)æll I co2 (after rescaling N by factor of log(I19:112) = O (log(n))), and since 2 is
by Property 4 with probability 7y we have that vy (g::) > 7). Now with probability 1 - 7/2,, we have that 1 1 <
also an upper bound on the spectral norm of the Hessian of by construction, it follows that V g..0v v (cg:) > n/2.
Now we set x. f cg:+cc02 g./ //ll///ll//)) First note that this increases oy (cz)- - by at most Eo. so (cz)) (cx))-11 -1 2eg. so this does not affect the first claim of the Proposition. But in addition, note that conditioned on the event in the prior paragraph, we now have that σy (x) > + 17622 -N The above facts can be seen by the fact that 2 is polynomially larger than the spectral norm of the Hessian of a, thus perturbing x by co2 additive in the direction of z will result in a positive change of at least / (1/44(e02 N) a. Moreover, by applying similar argument as in the last paragraph, we will have Vv (cr) > n/4 still after this update to T.
1 any 6, 6 > O, and let N == ==ooo(nn, hi 7: Ei= log(L)) I.), E log(ki), log( ()) log( log( Then given any subspace V C R with dimension dim(V) < ki and given I E RR, such that 60r)2 S ov - S 260 where co = O(2-N² /c) for a sufficiently large constant C O(1), and Vaov(x) > n/2, then with probability - 2N//2,, we can find a vector e E IR" in expected poly(N) time, such that
Lemma 4.2
[P Spon(A) 10l22 2 (1 -1)llu
and such that [|Puulla S e||u||22
Proof. We generate 91, 92. ................................ In (O, In), and set u, = 9.2 - 12/11 We first condition on the event that lIgell2 S N for all i, which occurs with probability 1- 2-N/n". Note Vu, (ov (x)] = w AT, Pv )us,, where w" V [a(A(T,, (In, - Py)))]" E RRt, which does not depend on u, Thus w" A (In. Pv) is a vector in the row span of A (T, Pv). We can write
My + cu.) = (lov(x) + cw A(I. Pv)u; + E(eu))
where E(cus) = O[ - Pv 12122320 = O(llcu:13 (12200) is the error term for the linear approximation. Note that the factor of N comes from the fact that the spectral norm of the Hessian of : R" + R can be bounded by II, KuL; < 2%, Fix some 8 > O. We can now binary search again, as in Proposition 4.1, with O(lo((N/3)) iterations over c, querying values My + cu;) find a value c = C2 > such that
1-8
S Mr(x + cu:) 1 B
so
1- (ov(x) caw" Aln. Pv)u: + E(c,u)) <
2 2- --Nee c))))) To see this, first note that by Proposition 4.1, we have (x) > n/4 with probability 7. We will condition on this occurring, and if it fails to occur we argue that we can detect this and regenerate x. Now conditioned on the above, we first claim that V Vv (x) 2 1/88 which follows from the fact that we can bound the angle between the unit vectors in the directions of u, and x by
We first claim that the 4, which achieves this value satisfies ||quull2 < (10-2-1))
cos (angle(u;, (u;, x)) = U1
(1-11/2221) (1 n/2 n/2-N/2)
|Tull2
|
N and since 2 is an upper bound on the spectral norm of the Hessian of a,, we have that Vv + cu.) > >n/8 +2 > n /10 for all e < 2 2N In other words, if H is the hessian of a. then perturbing by a point with norm O(c) S 2-22h 2N can change the value of the gradient by a vector of norm at most 22N | < 2-N, where Hll is the spectral norm of the Hessian. It follows that setting e = (10- 2-N co/n) is sufficient for σv (a + cu.) < 1, which completes the above claim.
along with the fact that we have (z) > 1 4. Since (ov < 2e0 < ~-
Now observe that if after binary searching, the property that c S (10 2- 2-Nco/') does not hold, then this implies that we did not have Vo(x)= > 11/4 /4 to begin with, so we can throw away this x and repeat until this condition does hold. By Assumption 4, we must only repeat 0(1/7) times in expectation in order for the assumption to hold.
Next, also note that we can bound e 2 2ng2-N/N /N, since 2 again is an upper bound on the norm of the gradient of and we know that ov - 1 > 2on2 -N Altogether, we now have that B(qu)) S cf22 < (10 2 2- ->eo/n)222
16

---

Published as a conference paper at ICLR 2020
We can repeat this binary search to find ej for different perturbations u1.... Uny and obtain the resulting C1, ...... Cu. such that for each i [xx] we have
1 1- ov (2) E(qu,, - 3, = c,u" (I, Pv)u,
where B; is the error obtained from the binary seach Ci, and therefore satisfies 13,1 S 2-N'c taking poly(NV iterations in the search. Now we know & and Ui so we can set up a linear system
min 1yy B 12
for an unknown y E R where the i-th column of B is given by B, = U, E R", and b, = 1/c for each i E [n]. First note that the set {u1, .2...., Un is linearly independent with probability 1, since {ur I, U2 2, Z...., ..., Un x) is just a set of Gaussian vectors. Thus has rank n, and the above system has a unique solution y²
"² " AC Pv), we obtain that for each i [n]]
Next, observe that setting
(I-ov(#))
1
1 E((cu)) - B
(BB)
Ci G ov (x)
Thus
1 B(qu,) Bi 2 1/2
) C: 1 - ov(r)
1 B 67 12 -
Σ
1
(10-2 2 N EN 2 22
2 N2 22-N2 6
)
3)
1/2
(5)
n
1- o- (x)
c
$ (2 Nyo
q(1 - (x))
Now setting 5" such that (y*) (B")²B = bet we have that cost of the optimal solution is 0, and l - b71l2 < (2-N)o(1) [-]- so I1(y* BI12 S (2 (20)) a[-o(a)) By definition of the minimum singular value of
B, it follows that I1y 5112 _ (2 N y0 {-] Now using the fact that B 2 G X where G is Gaussian matrix and X is the matrix with each row equal v, we can apply Theorem 1.6 of Cook et al. (2018), we have
min (B) 2 (2(2)))00), So -yy-- -ll2 < (2-N)0
Thus we have ||y" - (2-N)+ a[1-)(=))
and moreover note that | Z (z) (-
7
So we have that
8(1 (21)
(2 (2-N)0(1)
11y
ø11
c (x))
|7]|
1| 1|
$ (2 Nyo1)) c
(6)
$ (2 (2-NNorr)
< (2- (2-Noo11)
2-
Where the last inequality holds by taking C larger than some constant in the definition of co- Thus I1y Øll
2 2-N/2 thus I Øl1 < 2- 2-2-N/2
e +1ly" || after scaling N up by factor of log" (1/e). Thus by setting o = y", and observing that y is in the span of A, we ensure ||P (Pspan(A)ull 2 (1 - <) e)]lell2 as desired. For the final claim, note that if we had y = ÿ exactly, we would have [Pv'" = 0, since y is orthogonal to the subspace V. It follows that since |ly
1|2 1/
log"(1/e)
3 < ed I|y" 1|3. have [[, P Pv)y" 2 (1 <²) l|y" l| so by the Pythagorean theorem,
we have | | (L,,, Pv)y 11 < 21 as desired.
Theorem 4.3 Suppose the network M (ar) ((o()))) satisfies the conditions described at the beginning of this section. Then Algorithu runs in Poly(N) time, making at most poly(N) queries M (x), where N
17

---

Published as a conference paper at ICLR 2020
poly(n, k, 2, Di=loo((L)) Li, log(k;), log(( logg))) and returns with probability 1 - 5 a subspace
V C TR of dimension l such that for any x E V, we have
IP
Spont A 2 (1 ->/|///2
Proof. We iteratively apply Lemma 4.2, each time appending the output R" of the proposition to the subspace V C. In' constructed so far. WLOG we can assume v is unit vector by scaling it. Note that we have the property at any given point in time K' < k that V = Span(e1, ..... (xr) where each e; satisfies that || Spon(e 1//12 S c. Note that the latter fact implies that 01,- ULr are linearly independent. Thus at the end, we recover a rank l subspace
V (paa. Uk), with the property that |P Span())) (A) 02 12 2 (1 <)][v: for each E [K].
Now let V E R be the matrix with i-th column equal to U/- Fix any unit vector Va E V, where R is uniquely determined by x. Let V --=++ V V where V P (A) and
V and V = V V+ Then x = V+a+ V-a,
(1 P Span (A) 2))2212 S (I P Spant A) V all2 + (I P Spun(
V aal2
$ || (T,, P Spant A) V a|l2
(7)
V 1=22||aa|2
First note that by the construction of the vs s, each column of V has norm (e). thus | S ((vne).. Moreover, 1/ //22222 for each
since ||æ||2 1, follows that ||a||2 S (V). which we now bound. Since
E [k)]. we have
[all2 2
70
2 |1
IIn Span (0) (o1 1))
U;4; +
Σ Span vn 1 021il22
D (In P Span (panfvi (V (p )a,sll Σ 1=1
P
Span (1 1 U2ail12
(nn P Span foonfen-ae (t.. 11;;0 (s)]laal2z
1=1
1/2
(In P Spunf in (1....... )ua, )0; - (a)) Σ
(Un P Spanfer.....ti.11 Nasas112 + [({))||a|1
1=1
i=1
1/2
(In P
Spanf vi.... 1) )oaai - [aa]
1/2
(I, P Span 11.... 1)1;a,112
-(e))aal
1/2
Σ (1 -
v (1al12 - oc))laa13
2 (1 - (ae))l
(8)
Thus Jmin V) (1-01 0(e)) we have ||(T, P Span(A) (A) )oll( 5 |V (V] 22/Tc. By the Pythagorean
theorem: [|P (A) = [[, P A) | 2 1 O(ne²). Thus we can scale by factor of @ Vn) in the call to Lemma 4.2, which gives the desired result of |P (PSpan(A)) 2 2 1 -
18


Reviews:
[{"review_id": "BygwlnWNcB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper considers the problem of recovering the span of the latent variables of a neural network with various activation functions. More precisely, if we write a neural network as M(x) = f(Ax), for some neural network f, and a matrix A: R^{k x d} -> R^{k}, k << d, we wish to recover the row span of A. The authors consider ReLU activations -- in which case they can recover at least \"half\" of the row span with ~kd queries to M(x), and smooth activations -- in which case they can approximately recover the row span in poly(k,d) queries. The authors also consider (empirically) applications of these algorithms to \"input obfuscation\": namely generating samples which are effectively noise, but the network classifies them as \"structure\" (e.g. digits on MNIST). \n\nEvaluation: This is a strong submission. The paper is well written, easy to follow, and contains various interesting techniques, possibly for a wide audience in ICLR. For instance, the ReLU algorithm relies on the piecewise affine structure of ReLU nets to reduce calculating gradients to solving simple linear systems; it additionally cleanly characterizes how many \"sign patterns\" need to be seen to span most directions of the gradients of M. The differentiable activation case also has lots of neat tricks for dealing with non-linearity, and in particular how to find the right \"scaling\" of directions to move in to get new almost orthogonal information about the current estimate of the row span. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkgMU573cr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper is interesting to me in terms that it provides a systematic approach to generate adversarial samples for a given black-box neural network system. Though this is the side product of the paper.\n\nSome questions:\n1.\tFinding adversarial examples in this paper relies on finding the null space of Ax =0. This requires that input data is with a higher dimension than the span of A. I understand that the whole paper assumes that n>k where input is with dimension n and A is k by n. However, this restricts the application of the proposed adversarial attack as a general approach.\n2.\tWhen we are trying to recover the span of A, how can we judge if or not M(.) has differential activation functions? Which algorithm (1 or 2) should we try?\n3.\tDoes the theorem rely on the assumption that A is with rank k? In general, A^{k by n} does not guarantee to be with rank min(k,n). For example, people may use low-rank matrix factorization to approximate the weight of some layers during neural network training.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BketSBj2cB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies the problem of span recovery for deep neural networks, that is\nrecovering the space of inputs that affect the output of the network.\nThe authors propose two algorithm, one for the case of ReLU activations and one\nfor the case of differentiable activations, and theoretically prove that they can\nrecover the span under certain assumptions. They complement these results with\nexperiments on a simple model on MNIST.\n\nAt a high level, the algorithms rely on computing gradient information through\nfinite differences in order to recover direction in input space that the model\nis sensitive to. The assumptions are reasonable, mostly requiring that when\npassing random inputs through the model, the output varies sufficiently while\nthe gradients are sufficiently large with some probability. Given these\nassumptions, the algorithms maintain a subset of the span and iteratively find\ndirections in the input space that are not captured by the current subspace.\n\nOverall, the paper is well-written and addresses a fairly fundamental problem.\nThe solution presented is motivated and the analysis intuitive. However, I am\nnot fully convinced about the importance of studying span recovery in this \nsetting. In a white-box setting, we can just run SVD on the first layer. The\napplication to input obfuscation is fairly unconvincing since we already know\nhow to perform query-only adversarial attacks. Finally, I have a few questions\nabout the experimental results (see below). \n\nI thus recommend weak rejection at the moment but would be willing to\nreconsider based on the author response.\n\nSpecific comments:\n-- Algorithm 2 relies on the value of sigma when only tau(sigma) is available.\nThis should be clarified and the specific lemmas that allow this referenced.\n-- The first sentence of the experimental section is confusing. When is this\ncomputation performed? Based on the plot, the matrix is always full rank (80).\n-- More generally, how is the evaluation performed? Is the span returned \ncompared to the ground truth (via SVD)?\n-- I find it somewhat odd that it is possible to recover a rank 80 subspace with\n100 samples. After all, the subspace is described by 784 * 80 reals (which is\nalso the theoretical complexity O(n * k)) and we are only allowed input-output\nqueries.  Can the authors provide some intuition/clarification? Are these a 100\n_gradient_ computations?\n-- Can the authors provide additional details about how they compute gradients\nexperimentally (using finite differences)?\n-- Why are the input obfuscation experiments not performed with the subspace\nrecovered by the proposed algorithms? This would be necessary to argue that\npartial recovery actually leads to adversarial vulnerability.\n -- Denoting a neural network by sigma in the abstract and first intro paragraph\n is confusing (since sigma denotes the activations later).\n-- Prop 4.1: gradient needs a norm.\n\n\n##### Post-discussion update #####\n\nThank you for your response.\nI do agree that input obfuscation is somewhat different from adversarial attacks. It would be interesting to see if it has any applications to more realistic scenarios.\n\nTo be honest, I am somewhat disappointed to find out during the discussion that full gradient computation (i.e., not the proposed algorithm) was used for the empirical results. Most of the paper is focused on proving that finite differences are sufficient, yet the empirical results completely bypass this difficulty. I will thus keep my score the same.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJgdO8MJ5H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "** Summary\nThe paper studies how to recover the span of a NN from a limited number of queries. The problem belongs to the general question of how to reconstruct functions from black-box interaction and it may find application in obfuscation attacks where very large perturbations of the input do not affect the output. The main contribution of the paper is on the theoretical analysis of a simple non-adaptive and a more sophisticated adaptive algorithm. The main finding is that under mild conditions on the structure of the NN partial recovery is possible. The empirical validation show that in practice, it is often the case the full span recover is actually possible, as the structure and weights of common NN are \"friendly\" enough.\n\n** Evaluation\nWhile the content of the paper lies a bit off my expertise, my impression is that this is a solid technical and theoretical contribution.\n\nDetailed comments:\n1- Theoretical results: The properties proved in Thm.3.4 and 4.3 are quite powerful, showing that (partial/approximate) span recovery is possible with a relatively small amount of samples (of order of n*k, where n is the original input size and k is the size of the span), in a computationally efficient way (in particular for the non-adaptive algorithm), and for Relu NN or NN with differentiable layers and final threshold function. The main question is of course the validity of the assumptions needed to prove the theorems. Asm.1 and 2 are overall reasonable and they are very well supported by Lemma 3.1. The first two assumptions in page 6 are straightforward, while I'll less convinced of 3 and 4. In fact, they need to hold for any subspace V of any dimension smaller than k. I wonder whether the assumptions may become less and less likely as the size of the subspace decrease.\n2- The theorems and the paper are mostly well written but some parts may be clearer.\n3- Alg.1: the computation of the gradient is never really explained apart from the high-level lemma 3.2. While an actual algorithm is reported in the appendix, it would be better to have it explained already in the main text.\n4- Right after Lemma 3.2 it is said \"which demonstrates the claim\". I am not sure which claim it refers to.\n5- In alg.1 there is a parameter r which defines the number of queries of the algorithm. Thm 3.4 provides an upper bound on the number of queries needed and it does depend on k. Since k is initially unknown, how do you actually parameterize the algorithm? is there a stopping condition that can be tested?\n6- In Thm 3.4 it is said that the algorithm returns the subspace V in time that is polynomial in the main parameters of the problem. Yet, I'm not sure where such complexity comes from. In Alg.1 it seems like the subspace is the direct output of the algorithm, so the complexity is r times the cost of computing the gradient, which according to Lem3.2. is poly(n). Is this the way you finally obtain the complexity?\n7- One thing I'm doubtful about is the fact that the result in Thm 3.4 seems to be independent from the depth d and width k_i of the different layers. Some conditions may be implicit in the Asm.1 and 2, though. Furthermore, in the experiments it is clearly showed that thin NNs may make the support not recoverable. Could you please make such limit more explicit in the theory?\n8- In alg.4 I think lines 5-7 are just the way to execute line 4. Is that correct? If not, how do you execute line 4?\n9- In alg.4 line 8 and 9 are not easy to follow and they are not really discussed in the main text. Could you please clarify?\n10- The empirical validation is relatively simple but it illustrates quite well the theory. Still I wish the authors could report results that dig more in detail in the theoretical results showing how tight they are (e.g., in the dependency on n, k, and other factors). The current results provide just a hint on how accurate/informative the theory is.\n11- In the empirical result, it would be great to have a much more thorough validation of the difference between the non-adaptive and the adaptive algorithms. In the current results it seems like there is very limited difference.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a way to recover latent factors implicitly constructed by a neural net with black box access to the nets output. This can be useful for identifying possible adversarial attacks. The majority of reviewers agrees that this is a solid technical and experimental contribution.
Decision: Accept (Poster)