PAC-Bayesian Spectrally-Normalized Bounds for Adversarially Robust Generalization

Summary

This work tries to develop a PAC-Bayesian spectrally-normalized robust generalization bound.

Strengths

This work tries to understand robustness from theoretical perspective.

Weaknesses

1. unclear definitions: second line in Eq. (4) $\mathbf{x}(\mathbf{w})=\arg \inf_{\left\|\mathbf{x}-\mathbf{x}^{\prime}\right\| \leq \epsilon} g_{\mathbf{w}}(\mathbf{x})$ (I guess it's $\mathbf{x}(\mathbf{w})=\arg \inf_{\left\|\mathbf{x}-\mathbf{x}^{\prime}\right\| \leq \epsilon} g_{\mathbf{w}}(\mathbf{x'})$) $\mathbf{x}(\mathbf{w}')=\arg \inf_{\left\|\mathbf{x}-\mathbf{x}^{\prime}\right\| \leq \epsilon} g_{\mathbf{w}'}(\mathbf{x})$ $\inf_{\left\|\mathbf{x}-\mathbf{x}^{\prime}\right\| \leq \epsilon} g_{\mathbf{w}}(\mathbf{x})$ etc 2. Assumptions are not clearly described before theorem 1: What are the conditions on $B$ and $\gamma$ for your theorem? E.g., Neyshabur et al. (2017b) assumes $\mathcal{X}_{B, n}=[ \mathbf{x} \in \mathbb{R}^n \quad | \quad ||\mathbf{x}||_2 \leq B ]$ and $\mathbb{P}_\mathbf{u} [\max_\mathbf{x} | f_\mathbf{w+u}(\mathbf{x})-f_\mathbf{w}(\mathbf{x}) |_\infty<\frac{\gamma}{4} ] \geq \frac{1}{2}$ (or $\ell_2$ norm). 3. Miss citation for Line 482. 4. What is $||W_i-W_i||$? 5. Please provide the details from Eq. (10) to Eq. (11). 6. As claimed in the contribution: **without any additional assumption**, **as tight as**, **how to obtain a robust generalization bound**. My concerns are: **Does this bound provide new information for us?** In my opinion, for (middle or large) DNNs, PAC-Bayes is not a tight bound but may provide inspiration for us to get a better generalization model. For the bound of this work, it just replaces $B$ with $B+\epsilon$. To me, it simply implies that $||\mathbf{x}||_2\le B$ (clean data), $||\delta||_2\le \epsilon$ (attack radius) thus $||\mathbf{x}+\delta||_2\le B+\epsilon$ (adversarial data), but it holds no significant meaning. For the above reasons, I think this work should be rejected.

Questions

ref Weaknesses

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

ref Weaknesses

Summary

This paper improves previous PAC-Bayesian bounds on robust generalization. The previous bound in Farnia et al. (2018) has a term that is not bounded, and this work provides a bound to that term using the Lipschitzness of feed-forward ReLU networks. The basic idea is that coordinate-wise Lipschitzness preserves under L-inf perturbation.

Strengths

I am quite familiar with this field and spent 3 hours reviewing this paper. Though I do not closely follow the robust generalization line of research, I believe that this work could be helpful to people working in the same direction. The overall framework is very clear and the results are intuitive and easy to understand. Though there are some confusing parts in some sections and the writing can still be improved, overall this looks like a nice paper and should make it to NeurIPS. The overall framework is clean, and the proofs are easy to read. I quickly checked all the proofs, and they look good to me. I am not 100% sure that all proofs are sound, but even if there are small errors, they should be fixable because the results are very intuitive.

Weaknesses

My only concern is that the significance of this work might not be obvious to a person who is not very familiar with this field. This work is addressing a very specific issue in a previous theorem, and while this issue is important, I think the authors should clarify more about why it is important, what is the main challenge and how this paper fixes it, right at the beginning of the paper. Right now I would say that those things are quite scattered. For example, the main challenge is in Section 6.2. I think the authors could include the following in the intro: - What is the main issue in the previous PAC-Bayes bounds? - Why is it difficult to fix this issue? - What additional assumptions does this work make in order to fix this issue? - What is the main technical contribution in the proof of this work? As someone very familiar with learning theory and adversarial robustness, I can find the answers to these questions easily in the paper. However, if the authors want to appeal this work to a more general audience, I suggest them rearrange the paper a little bit, and discuss these questions in the intro.

Questions

See above. **Post rebuttal note:** I have read the rebuttal and other reviews. I prefer to keep my score.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

Limitations are not discussed.

Summary

In this work, authors use PAC-Bayesian bound to characterize the generalization gap of adversarial robustness. Their work is mostly based on the bound derived from (Neyshabur et al., 2017b) so the resulting bound is valid for a deterministic model.

Strengths

The major contribution from this work is the new PAC-Bayesian bound for adversarial robustness. The bound works for both Lp and non-Lp cases on both feed-forward networks and ResNets. Authors also compare their bounds with existing ones that only target specific attacks, and show their bounds are more generic. I appreciate the paper’s contribution of the bound (but I do have a question regarding the tightness of the bound which I will elaborate in the next part). The paper has pushed the use of PAC-Bayesian theories to scenarios beyond standard generalization.

Weaknesses

The first weakness of the paper is probably that this newly derived bound largely relies on the work from Neyshabur et al., which has been phrased as an advantage of Theorem 1 being tight at least as Neyshabur et al.’s. However, this might be misleading as I believe the correct description would be when $\epsilon=0$ Theorem 1 reduces to Theorem 2 so they are as tight as each other. I am not sure I understand what does it mean for Theorem 1 and 2 to be equally tight when $\epsilon > 0$? Do you mean that what is in the big O notation is around the same magnitude? However, I do not see the value of $p$ (in $\ell_p$) plays any role in the new bound and the paper talks about the general $\ell_p$ robustness, thus I assume the bound works in any $\ell_p$ space. I hereby have the following question, if the bound is p–norm-agnostic, how come it is equally tight for all $p$? Does this bound simply characterize the robustness of the model in the largest ($\ell_\infty$) perturbation ball for a given $\epsilon$? If that is the case, perhaps the derived bound is pretty loose for $\ell_2$ perturbations. Can you elaborate more here (and in the paper) about the tightness of the bound for different $p$. Another weakness is the empirical study to demonstrate the tightness of the bound in Table 1. This table is poorly captioned because I do not know how these models are trained, what architectures are used, what $\epsilon$ and attack techniques are used to report the numbers. Also, what does $\infty$ means for Theorem 3? Does this mean the assumption about gradient norm in Theorem 3 does not hold? Do you have experiments about the gradient norms? Moreover, I think it might be useful to use more models and more statistically significant numbers to show the proposed bound is tighter, like the measurement done in this paper [1]. [1] Jiang, Y., Neyshabur, B., Mobahi, H., Krishnan, D., & Bengio, S. (2019). Fantastic Generalization Measures and Where to Find Them. ArXiv, abs/1912.02178.

Questions

I do not have further questions. I think the theoretical contribution is incremental so it may further increase my score if more empirical evaluations are conducted.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

It might be nice to include such a paragraph.

Summary

This paper provides a tighter bounds for robust generalization compared to previous results and as tight as standard generalization.

Strengths

1. The paper studies an important topic on adversarial robustness and provide a tighter bound with detailed theoretical analysis. 2. The paper is well-written and the conclusions are sound as far as I understand (I didn't check the proof in Appendix).

Weaknesses

* As the paper is an improvement on Farnia et al. (2018), thus the technical novelty is less significant. * The authors should explain why a tighter upper bound is insightful for the robustness community. In my understanding, the robust generalization bound is usually used to explain which factor affects the robust generalization, or why robust generalization is worse than standard generalization. The authors should discuss more on the implications from the new result.

Questions

Please see the weaknesses part.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

There is no discussion on limitations.

Post Rebuttal

Thanks for the response. I have read the response. The response looks good but I believe that the authors still need some revision for the paper to make the presentation clearer. I'll keep my rating.

Thanks for the response.

Thanks for the response. We have updated the paper based on the comments and questions.

response

I thank authors for their careful reply. As the typos in the equation (definition) destroyed my patience to carefully review this paper, I only spent an hour checking most mathematical parts. I have to say, the current version is very unfriendly to a general reader in the community. All in all, I think the current manuscript has its merits but also obvious flaws, I sit on the fence for this paper.