Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Summary:

This paper uses results from distributional robustness to provide bounds of p-norm-constrained adversarial risk which depend on the Lipschitz constant of the underlying classifier. The bulk of the paper focuses on sample-efficient mechanisms to approximate the Lipschitz constants of kernel methods so that a constraint on this Lip constant can be enforced during training. Empirically, the kernel methods are compared to existing deep learning approaches and are shown to be competitive at this scale.

Overview:

This is a technical paper which draws on theoretical results in Kernel methods, distributional robustness, and numerical approximation. I have been unable to verify the correctness of results from all of these areas but to the best of my knowledge the results seem reasonable. Despite the technical depth, the paper is well-written and largely easy to follow.

1) In section 3.1 you should emphasize the threat model more clearly. Distributional robustness may provide tools to evaluate very general forms of adversarial risk but in this work only the p-norm ball threat model is considered. This is a fine restriction and theoretical statements are made correctly but this does not encompass all forms of adversarial risk.

2) I had a hard time understanding Figure 1. The adversarial risk (Eqn 3) is upper-bounded by the variable-radius risk (Eqn 4 LHS) but Figure 1 shows that the adversarial risk of radius $r$ may permit larger perturbations than the variable-radius risk. Could you please explain how this Figure should be interpreted? The caption and main-text description of the Figure are very slim.

3) I like Figures 2 and 3 as they clearly highlight the benefits of both DRR and the proposed approximations in this work. This paper already presents thorough theoretical analysis but a further analysis into the conditions required for $\lambda_{max}(G^T G)$ to guarantee tighter bounds on the Lipschitz constant would be a valuable addition.

4) Unfortunately I was unable to follow the analysis in Section 4.1 due to a lack of prior knowledge. To my understanding, the per-dimensional product factorization allows cheap exact computation of the off-diagonal elements of $G^T G$. This means that only the diagonal elements need be computed by the Nystr\"om approximation. However, I cannot see intuitively how this prevents the sample complexity from scaling with the dimensionality (the number of diagonal elements still grows with $d$).

5) The experimental set-up is mostly standard with the exception that the CIFAR-10 robustness is measured with respect to a learned representation. This is a reasonable setting for validating the theoretical contributions of this work but is not a realistic interpretation of the adversarial threat model considered. The Lipschitz constant of the embedding function (the pre-trained ResNet) is not known and will likely lead to vacuous bounds (for robustness with respect to the input-space).

6) The deep learning experiments utilize the Parseval networks regularization scheme. What is the regularization constant ($\beta$) used for this method? Typically, a small $\beta << 1$ value is chosen which enables easier learning but prevents the Lipschitz constant from being tightly enforced during training. Is the final Lipschitz constant upper-bound computed from the learned weight matrices to ensure that the orthogonality constraint is not violated?

7) There is some disparity between the experimental results presented and the theory in the paper. In particular, this paper explores methods to provide robustness certificates to Lipschitz bounded classifiers but does not compute and validate these certificates empirically.

8) The gradient visualizations were surprising to me. The Par-MaxMin model has interpretable gradients in that the target class is visible through the gradients. However, for the Gauss-Lip model the gradients seem to only depend on the images current class and are suggestive of a form of gradient obfuscation. It may be useful to visualize "large perturbation" adversarial examples for the Gauss-Lip classifier --- what characteristics do these images have? Similarly, one could generate so-called "Distal Adversarials" which are generated by sampling random noise and optimizing them towards a target class. Does the Gauss-Lip model generate realistic looking images or is noise classified accurately?

9) Overall, the experiments seem sufficient to conclude that the Gauss-Lip model is a promising approach to adversarial learning. It is not clear how this method could be scaled to high dimensional data (while there are more obvious avenues for the deep learning alternatives).


Minor:

- In Theorem 1 statement, "If additionally if $\ell_f$ is convex".
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: Through the lens of Distributional Robust Risk (DRR), this work draws a link between adversarial robustness and Lipschitz constant regularisation. The authors first provide an upper bound of the DRR (with a Wasserstein ball as the ambiguity set) in terms of the true risk and the Lipschitz constant of the loss function under the current model. They show that the standard adversarial risk can be upper bounded by the DRR, emphasizing that the Lipschitz constant regularised loss can be used as a proxy for adversarially robust training.

The authors then apply this idea to kernel methods and aim to minimise the true risk under a Lipschitz constant constraint. By using a bound between the Lipschitz constant and the largest eigenvalue of the Gram matrix, and by approximating the Gram matrix using Nystrom approximation, they express the Lipschitz constant constraint as a convex constraint. In the case of multiplicative kernels, this approach is shown to be efficient when only using a polynomial number of sample points for the Nystrom approximation.

This method is tested on 3 standard datasets and is shown to outperform state-of-the-art deep learning based approaches over a wide range of perturbation in both l_2 and l_infinity norm. 

I have concerns about the novelty of the two main contributions of this work, which are Theorems 1 and 2:
* Theorem 1 is a direct implication of Kantorovich duality, well known in optimal transport.
* Theorem 2 is a rewriting of Proposition 3.1 in [1], which is not cited.

My second concern is that the value of n (number of sample points used in Nystrom approximation) has not been specified for the presented experiments (unless I missed it). This is an important parameter to specify since the algorithm requires to invert an n by n matrix when applying Nystrom approximation, and scalability is usually the main criticism to kernel methods.

When comparing the methods, would it be possible to estimate the Lipschitz constants of the models trained by the various algorithms ? This would enable to observe the true effect of the methods on the Lipschitz constant.

Due to these two concerns above, I tend to reject this submission.

A few comments about clarity:

* It would help to provide the full kernel method algorithm (with more detail than Algorithm 1 in Appendix), e.g., explicit the convex constraint on gamma when training the SVM.

* epsilon notation is used both for the accuracy in the Lipschitz constraint (as in Theorem 3) and the adversarial perturbation (as in equation 3 or Figures 4 and 5). In page 7, paragraph 'Attacks', delta is used once for denoting the perturbation, but epsilon is reused just after. More consistency in the notation would be greatly appreciated.

* It is not clear in the main text that L is a bound on the gradient norms at sample points. It is made clearer in the appendix, so one sentence from the appendix should be added to the main text.


Typos:
* p.6 top: "and analogously for ...(x_1^a,.)" instead of '(x_1^b,.)'

[1] Distributionally Robust Deep Learning as a Generalization of Adversarial Training, M. Staib, S. Jegelka, NIPS, 2017
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: In this paper, the authors propose a distributional robust risk minimization method using Lipschitz regularization and give an approach to approximate the Lipschitz constant for product kernels efficiently.

My major concerns are as follows.
1. The result in Theorem 1 is similar to Theorem 3 in [1]. The authors use McShane–Whitney extension theorem [2] to generalize the previous result, which is a trivial derivation.
2. Although the proposed method is theoretically applicable for a wide class of models, it is hard to use in practice, since the Lipschitz constant is too hard to compute exactly. To address the problem, the authors give an approach to approximate the Lipschitz constant for product kernels efficiently. However, the applicability of the method is still limited if it can be used only for product kernels.
3. In the abstract, the authors claim that this paper resolves the previous methods' limitations for deep neural networks. However, there is no corresponding theoretical analysis.
4. Some notations are confusing. For example, in the second paragraph on Page 3, there are two different sets denote $cost_c$; in the definition of $cost_c(\mu,\nu)$, the meaning of the symbol $\Pi$ is unclear; in Theorem 2, the symbol $|\cdot|$ is not defined.

[1] Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial  training. In International Conference on Learning Representations (ICLR), 2018.
[2] Iosif Petrakis. Mcshane-Whitney extensions in constructive analysis. arXiv preprint arXiv:1804.06757, 2018.
review_title: Official Blind Review #2

Meta-review: This works relates adversarial robustness and Lipschitz constant regularization. After the rebuttal period reviewers still had some concerns. In particular it was felt that Theorem 1 could likely be deduced from known results in optimal transport, and it would be nice to make this connection explicit. There were still concerns about scalability. The authors are encouraged to continue with this work, considering the above points in future revisions.

Decision: Reject