Venue: ICLR 2018 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The work claims a measure of robustness of networks that is attack-agnostic. Robustness measure is turned into the problem of finding a local Lipschitz constant which is given by the maximum of the norm of the gradient of the associated function. That quantity is then estimated by sampling from the domain of maximization and observing the maximum value of the norm out of those samples. Such a maximum process is then described by the reverse Weibull distribution which is used in the estimation.

The paper closely follows Hein and Andriushchenko (2017). There is a slight modification that enlarges the class of functions for which the theory is applicable (Lemma 3.3). As far as I know, the contribution of the work starts in Section 4 where the authors show how to practically estimate the maximum process through back-prop where mini-batching helps increase the number of samples. This is a rather simple idea that is shown to be effective in Figure 3. The following section (the part starting from 5.3) presents the key to the success of the proposed measure. 

This is an important problem and the paper attempts to tackle it in a computationally efficient way. The fact that the norms of attacks are slightly above the proposed score is promising, however, there is always the risk of finding a lower bound that is too small (zeros and large gaps in Figure 3). It would be nice to be able to show that one can find corresponding attacks that are not too far away from the proposed score.

Finally, a minor point: Definition 3.1 has a confusing notation, f is a K-valued vector throughout the paper but it also denotes the number that represents the prediction in Definition 3.1. I believe this is just a typo.

Edit: Thanks for the fixes and clarification of essential parts in the paper.

review_title: Critical problem and important claims, with experimental justification.

final_score: rating: 7: Good paper, accept
review_content: Summary
========

The authors present CLEVER, an algorithm which consists in evaluating the (local) Lipschitz constant of a trained network around a data point. This is used to compute a lower-bound on the minimal perturbation of the data point needed to fool the network.

The method proposed in the paper already exists for classical function, they only transpose it to neural networks. Moreover, the lower bound comes from basic results in the analysis of Lipschitz continuous functions.


Clarity
=====

The paper is clear and well-written.


Originality
=========

This idea is not new: if we search for "Lipschitz constant estimation" in google scholar, we get for example
Wood, G. R., and B. P. Zhang. "Estimation of the Lipschitz constant of a function." (1996)
which presents a similar algorithm (i.e., estimation of the maximum slope with reverse Weibull).


Technical quality
==============

The main theoretical result in the paper is the analysis of the lower-bound on \delta, the smallest perturbation to apply on
a data point to fool the network. This result is obtained almost directly by writing the bound on Lipschitz-continuous function
 | f(y)-f(x) | < L || y-x ||
where x = x_0 and y = x_0 + \delta.

Comments:
- Lemma 3.1: why citing Paulavicius and Zilinskas for the definition of Lipschitz continuity? Moreover, a Lipschitz-continuous function does not need to be differentiable at all (e.g. |x| is Lipschitz with constant 1 but sharp at x=0). Indeed, this constant can be easier obtained if the gradient exists, but this is not a requirement.

- (Flaw?) Theorem 3.2 : This theorem works for fixed target-class since g = f_c - f_j for fixed g. However, once g = min_j f_c - f_j, this theorem is not clear with the constant Lq. Indeed, the function g should be 
g(x) = min_{k \neq c} f_c(x) - f_k(x).
Thus its Lipschitz constant is different, potentially equal to
L_q = max_{k} \| L_q^k \|, 
where L_q^k is the Lipschitz constant of f_c-f_k. If the theorem remains unchanged after this modification, you should clarify the proof. Otherwise, the theorem will work with the maximum over all Lipschitz constants but the theoretical result will be weakened.

- Theorem 4.1: I do not see the purpose of this result in this paper. This should be better motivated.


Numerical experiments
====================

Globally, the numerical experiments are in favor of the presented method. The authors should also add information about the time it takes to compute the bound, the evolution of the bound in function of the number of samples and the distribution of the relative gap between the lower-bound and the best adversarial example.

Moreover, the numerical experiments look to be realized in the context of targeted attack. To show the real effectiveness of the approach, the authors should also show the effectiveness of the lower-bound in the context of non-targeted attack.


#######################################################

Post-rebuttal review
---------------------------

Given the details the authors provided to my review, I decided to adjust my score. The method is simple and shows to be extremely effective/accurate in practice.

Detailed answers:

1) Indeed, I was not aware that the paper only focuses on one dimensional functions. However, they still work with less assumption, i.e., with no differential functions. I was pointing out the similarities between their approach and your: the two algorithms (CLEVER and Slope) are basically the same, and using a limit you can go from "slope" to "gradient norm".
In any case, I have read the revision and the additional numerical experiment to compare Clever with their method is a good point.

2) " Overall, our analysis is simple and more intuitive, and we further facilitate numerical calculation of the bound by applying the extreme value theory in this work. "
This is right. I am just surprised is has not been done before, since it requires only few lines of derivation. I searched a bit but it is not possible to find any kind of similar results. Moreover, this leads to good performances, so there is no needs to have something more complex.

3) "The usual Lipschitz continuity is defined in terms of L2 norm and the extension to an arbitrary Lp norm is not straightforward"
Indeed, people usually use the Lipschitz continuity using the L2norm, but the original definition is wider.
Quickly, if you have a differential, scalar function from a space E -> R, then the gradient is a function from space E to E*, the dual of the space E.
Let || . || the norm of space E. Then, || . ||* is the dual norm of ||.||, and also the norm of E*.
In that case, Lipschitz continuity writes
f(x)-f(y) <= L || x-y ||, with L >= max_{x in E*} || f'(x) ||*
In the case where || . || is an \ell-p norm, then || . ||* is an \ell-q norm; with 1/p+1/q = 1.

If you are interested, there is a clear and concise explanation in the introduction of this paper: Accelerating the cubic regularization of Newton’s method on convex problems, by Yurii Nesterov.

I have no additional remarks for 4) -> 9), since everything is fixed in the new version of the paper.


review_title: The authors present an "attack-independent" method for evaluating the robustness of a network. The idea is interesting, but the theoretical is very weak.

final_score: rating: 7: Good paper, accept
review_content: In this work, the objective is to analyze the robustness of a neural network to any sort of attack.

This is measured by naturally linking the robustness of the network to the local Lipschitz properties of the network function. This approach is quite standard in learning theory, I am not aware of how original this point of view is within the deep learning community.

This is estimated by obtaining values of the norm of the gradient (also naturally linked to the Lipschitz properties of the function) by backpropagation. This is again a natural idea.
review_title: Interesting point of view on analysis of robustness

Meta-review: This paper proposes a new metric to evaluate the robustness of neural networks to adversarial attacks. This metric comes with theoretical guarantees and can be efficiently computed on large-scale neural networks.

Reviewers were generally positive about the strengths of the paper, especially after major revisions during the rebuttal process. The AC believes this paper will contribute to the growing body of literature in robust training of neural networks.  
Decision: Accept (Poster)