Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies some adversarial examples in random ReLu networks, where a smaller perturbation generates a negative label.

The main result of the paper is some theorems. and the main technique used in the paper is mostly some inequality manipulation and concentration. I cannot check all the derivations, but the main results, i.e. the constants are convincible to me.


main_review: My major concern comes from the applicability of the property it studies. A network with random weights can hardly be associated with any machine learning applications. I can get the point that due to technical difficulty. It is hard to analyze in general, but I think the paper should mention the difference between the random network and a trained network, e.g. if the network is trained, the constants in theorem 1.1. will increase or decrease?


limitations_and_societal_impact: The experients are ignored in the paper. I get it as common in this field. But still, at least the paper improves upon previous theoretical papers, e.g. it claims that " the minimal width up to some point in the network determines scales and sensitivities of mappings computed up to that point", the authors are encouraged to design an experiment to verify, even without verifying the magnitudes of constants in the theorem.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper analyzes multi-layer random ReLU networks, and shows theoretical evidence that for constant depth networks with a variety of widths, adversarial examples must necessarily exist. They prove this result based on the key idea that such random networks are nearly linear, and that establishing smoothness accounts for the network’s nonlinearity. Further, they show that adversarial examples will not exist if the depth grows too large.
main_review: Overall, this paper appears original, has a significantly improved result compared to prior work (extending from 2-layer networks to general constant-depth networks), and is presented in a very clear fashion. The intuition behind each step of the proof is carefully presented in the introductory section, and various proof techniques, such as analyzing the bottleneck layer, are discussed. The proof itself, as well as the key intuitions behind each step of the proof, are also presented in a clear and understandable fashion (there are a lot of important details in the proofs too, which I did not go over carefully). All in all, I would recommend an accept.

I have some suggestions and questions for the authors.
1) Spelling/Grammar - gaussian and euclidean should be capitalized. Heoffding should be Hoeffding.
2) Does the proof still hold when the output dimension is not a single real output? What if it’s a k-dimensional output (e.g. if there are k logits)?
3) This is not necessary, as I believe that the theory presented is an important contribution by itself, but what future experiments (L90) would you suggest to determine if randomly initialized trained networks retain this nearly linear behavior? For example, Lemma 2.2 relies on the gradient being bounded away from 0, but this would probably not be true for a trained neural network, right?


UPDATE: After reading the author response, I will keep my score of Accept, as I still feel that this is an interesting paper.
limitations_and_societal_impact: No. With that said, it is a purely theoretical paper, so I do not believe there is too much for the authors to discuss here.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: EDIT: I will be keeping my (positive) score.

The paper studies robustness properties of ReLU networks that have random weights. The main finding is that random ReLU nets of constant depth are susceptible to adversarial examples for every input vector. The main theorem relies on some conditions about the widths in the networks' layers. To complement this result, the authors show that in the large depth regime, such a result cannot hold.

The paper builds on prior work and  their main result generalizes results of Daniely and Schacham (2020) for networks with rapidly decreasing width and results of Bubeck et al (2021) for two-layer networks. Some ideas and intuition come actually from prior works: 
the main goal is to demonstrate the existence of an adversarial example near input x,  and to do this for a function f, it turns out that it suffices to show the smoothness property: see (1) . This "smoothness" property is not in the common sense of the word "smooth" function, but basically says that for a deep ReLU network with random parameters and a high-dimensional input vector
x, there is a relatively large ball around x where f satisfies this smoothness property. 

The main result is Theorem 1.1 that proves how taking a small step away from a point x in the direction of the gradient can flip the sign of the evaluated function f at x thus corresponding to an adversarial example. The most interesting condition is that the min depth of the net $d_\min \ge c_1(\log d_\max)^{c_2} \log 1/\delta$.

The authors also prove a converse result to justify why their results could only be true in the constant depth regime. This complementary result is given in Theorem 3.1 which shows that when depth grows polynomially in the input dimension d, the function computed by a random ReLU network can essentially be constant, which rules out the possibility of adversarial examples.

For theorem 1, an important aspect of the architecture of the network that allows for adversarial examples or not, depends crucially on the width of the narrowest layer before layer j—that  is "the bottleneck layer" for layer j as the authors call it. This width determines the dimension of the image at layer j of a ball in the input space. In proving bounds on gradients and function values that hold uniformly over pairs of nearby vectors x and y, this dimension—the width of the bottleneck layer—dictates the size of a discretization that is a crucial ingredient in their proof.




main_review: TL;DR: interesting paper with very nice result on adversarial examples for constant depth ReLU nets

The reviewer finds the paper both technically and conceptually very interesting. It provides a plausible explanation for the abundance of adversarial examples in modern neural nets by giving theory on how such examples would arise. They state a simple property on the gradients that would be sufficient for the existence of attacks and then the authors try to understand how this property would appear in NN. The main result is on constant depth neural nets but the authors complement this by saying the once we allow depth to increase, there can be cases where NN compute functions close to constant hence they don't suffer from adv. examples.

I think the paper is very well-motivated given the lack of understanding for adv. examples and provides a nice set of ideas that will likely be used in future works.


TYPO IN THEOREM 1: sign of f(x) -- I think the authors meant to put sign in front of f

QUESTION to the authors: One might have expected that when the depth is allowed to grow more, then this would lead to even more adversarial examples?  Maybe a naive rationale for this has to do with the lipschitzness of the network that could potentially map x+dx far away from x. My understanding is that because of the randomness in the network, one can avoid adversarial examples as the authors show. But one question that comes to mind is why is it that deep networks in practice tend to suffer from attacks? Is there some difference in the way the initialization or optimization procedures are done?
limitations_and_societal_impact: none
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies how adversarial examples arise in constant depth ReLU networks with independent Gaussian parameters. The main results of the paper is Theorem 1.1 which determines how the width of different network layers affect the probability of the existence of adversarial examples. Overall, the most important takeaway is that smoothness (or the absence of adversarial examples) requires networks that are polynomially (in the number of input dimensions) deeper and/or wider.
main_review: The paper is well-written and mathematically heavy. While the math seems to work out (I haven't thoroughly gone through every equation), I found no discussion about the proposed theorem.

1) The abstract is unclear. Aside from stating that "adversarial examples arise in these [ReLU] networks [with independent Gaussian parameters] because the functions that they compute are very close to linear", it is difficult to understand what the main theorem implies.

2) The rest of the paper is just as uninformative. I understand what the proof states and that it is a generalization of the results from Daniely and Schacham (2020) and Bubeck et al. (2020), but it is unclear what it implies. A thorough discussion on the implications of the theorem would be welcome (beyond the single paragraph listed after the proof).

3) The related work is missing. Some of it is sprinkled through the paper, but it is again quite difficult to judge the significance of this work without a dedicated section. How does this work relate to empirical work like [MMS+18] or [QMG+19]? How does it relate to over-parametrization and generalization?

4) Finally, for my own understanding, Theorem 3.1. roughtly states that one needs a depth of at least d^3 while Bubeck and Selke (2021) state that "smooth interpolation requires d times more parameters" (where d is the number of inputs dimensions). Can the authors comment on the difference and complementary of the results?
limitations_and_societal_impact: I haven't found any discussion about the limitations and/or societal impact. Maybe the authors can highlight some of those in the rebuttal.
review_title: null

Meta-review: The paper studies adversarial examples in ReLU networks with independent gaussian parameters. Reviewers were generally happy with the results of the paper. In particular, authors' responses in the rebuttal period helped clarify some concerns. Overall, I think the paper is above the accept threshold. 
Decision: Accept (Poster)