Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: The paper studies the problem of span recovery for deep neural networks, that is
recovering the space of inputs that affect the output of the network.
The authors propose two algorithm, one for the case of ReLU activations and one
for the case of differentiable activations, and theoretically prove that they can
recover the span under certain assumptions. They complement these results with
experiments on a simple model on MNIST.

At a high level, the algorithms rely on computing gradient information through
finite differences in order to recover direction in input space that the model
is sensitive to. The assumptions are reasonable, mostly requiring that when
passing random inputs through the model, the output varies sufficiently while
the gradients are sufficiently large with some probability. Given these
assumptions, the algorithms maintain a subset of the span and iteratively find
directions in the input space that are not captured by the current subspace.

Overall, the paper is well-written and addresses a fairly fundamental problem.
The solution presented is motivated and the analysis intuitive. However, I am
not fully convinced about the importance of studying span recovery in this 
setting. In a white-box setting, we can just run SVD on the first layer. The
application to input obfuscation is fairly unconvincing since we already know
how to perform query-only adversarial attacks. Finally, I have a few questions
about the experimental results (see below). 

I thus recommend weak rejection at the moment but would be willing to
reconsider based on the author response.

Specific comments:
-- Algorithm 2 relies on the value of sigma when only tau(sigma) is available.
This should be clarified and the specific lemmas that allow this referenced.
-- The first sentence of the experimental section is confusing. When is this
computation performed? Based on the plot, the matrix is always full rank (80).
-- More generally, how is the evaluation performed? Is the span returned 
compared to the ground truth (via SVD)?
-- I find it somewhat odd that it is possible to recover a rank 80 subspace with
100 samples. After all, the subspace is described by 784 * 80 reals (which is
also the theoretical complexity O(n * k)) and we are only allowed input-output
queries.  Can the authors provide some intuition/clarification? Are these a 100
_gradient_ computations?
-- Can the authors provide additional details about how they compute gradients
experimentally (using finite differences)?
-- Why are the input obfuscation experiments not performed with the subspace
recovered by the proposed algorithms? This would be necessary to argue that
partial recovery actually leads to adversarial vulnerability.
 -- Denoting a neural network by sigma in the abstract and first intro paragraph
 is confusing (since sigma denotes the activations later).
-- Prop 4.1: gradient needs a norm.


##### Post-discussion update #####

Thank you for your response.
I 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.

To 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.
review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: 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.

Some questions:
1.	Finding 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.
2.	When 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?
3.	Does 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.

review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: 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). 

Evaluation: 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. 
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: ** Summary
The 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.

** Evaluation
While the content of the paper lies a bit off my expertise, my impression is that this is a solid technical and theoretical contribution.

Detailed comments:
1- 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.
2- The theorems and the paper are mostly well written but some parts may be clearer.
3- 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.
4- Right after Lemma 3.2 it is said "which demonstrates the claim". I am not sure which claim it refers to.
5- 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?
6- 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?
7- 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?
8- 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?
9- 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?
10- 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.
11- 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.
review_title: Official Blind Review #3

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)