Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes two ideas for improving the performance of certified training.
The first idea is to use assign weight for each input based on the margin to the decision boundary.
The second idea is to use automatic scheduling of perturbation radius during training.
They show that using these two ideas leads to improved certified robustness on MNIST and CIFAR-10 datasets.

main_review: I think the weighting method is not presented that clearly in Section 3.1.
In particular, Equation 9 is quite confusing. Why can we just drop P'(x',y)/P(x,y) to get the final expression, isn't the whole point
that these two probabilities are quite different from each other (meaning the expression is not close to 1)?
Also how is final expression in Equation 9 any different from the standard loss from the beginning E_((x, y) ~ P) [l(f_\theta(x), y)]?
It seems to me that the only different is that the random variable has changed from x to x', but the overall expected loss should stay the same.

Final importance weighting that is used seems to be almost the same as the one used by Zeng et al., except that here we have
two hyperparameters alpha and gamma. Is this correct interpretation or there is some bigger difference between the two approaches?

Regarding auto-tuning of epsilon, prior work has already considered using larger epsilon to train the network,
so the key contribution here seems to be the algorithm presented in the Appendix C. As it is one of the key contributions of this work, it would make sense to put it
in the main paper, and not the appendix.

Final results seem somewhat underwhelming.
On MNIST the method improves 0.32% over the baseline, and on CIFAR-10 the improvement is 1.38%.
This seems quite small, but might be in the line with recent work in this field.
One question I had here is that your report the CROWN-IBP baseline to have verified error 68.35, but CROWN-IBP paper
reports 66.94. Could you explain where does the discrepancy come from?

Typos:

difition -> definition

examples with examples with -> examples with

the the ideal boundary -> the ideal boundary

linearly grows from 1 to 0.5 -> linearly decreases from 1 to 0.5

summary_of_the_review: I recommend rejection because the method itself is incremental over prior work and experimental results are only marginally better.
Furthermore, I think paper would benefit from another revision as some things should be written more clearly.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes bound-based weighted loss and epsilon auto-tuning to improve the performance of certifiable training. The insights of the improvements are mainly borrowed from well-developed adversarial training while they are customized for certifiable training considering bound margins provided bound propagation methods. The experimental results clearly show the improvements from individuals and the combination of the two methods.
main_review: Strength

1. Improving certifiable training performance is an important but very challenging task. The improvements are not marginal over IBP and CROWN-IBP compared to most of the recent papers.
2. The designs of the two methods are novel and reasonable. I like the examples in Section 3 which clearly illustrate the insights.

Weakness

1. Comprehensive experiments following CROWN-IBP would be necessary to fully demonstrate the performance of the methods. For instance, more model architectures should be evaluated. Also, 0.1 for MNIST and 2/255 for CIFAR10 are important baselines as well.
2. It would also be helpful to perform ablation studies for individual methods on CROWN-IBP besides IBP.
3. Despite the good results, I would not expect the proposed methods have a strong future impact enlightening further performance improvements since it is highly customized for the current stage and specific task. A discussion on limitations and future directions would be a plus.

Questions and comments

1. I am curious if applying the new methods on tighter relaxation like K&W [A, B], CROWN, or CROWN-IBP alone for certifiable training would improve the results or not?
2. A similar insight for improving certifiable training (CROWN-IBP) is proposed in [C] even though the eventual goal is slightly different. It would be helpful to at least mention it in the text.
3. Any specific reason for using "certification-based robust training" in the title instead of "certifiable training" which is a much more commonly used term?
4. Typo: Our bound-based method method, backed up by ...

[A] Provable defenses against adversarial examples via the convex outer adversarial polytope, ICML 2018

[B] Scaling provable adversarial defenses, NeurIPS 2018

[C] Adaptive Verifiable Training Using Pairwise Class Similarity, AAAI 2021
summary_of_the_review: Overall, I think the current version is a borderline paper. The proposed methods are new and the improvements shown in the paper are not that marginal compared to most of the related recent papers. However, the paper lacks comprehensive experiments to convincingly support the claims. If more consistent experimental results can be provided during rebuttal, I would vote for acceptance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a geometry-aware reweighting scheme and auto adjusted training adversarial budget to improve the performance of provably adversarial training. The intuition arises from the distance of the training examples to the decision boundary of the model.
main_review: **Strength**

The motivation of the algorithm is clear and easy to follow. The algorithm is general and easy to implement.

**Weakness**

1. [Theoretical Strength]
    * From my point of view, the bijection assumption in Theorem 1 is too strong and is disconnected with the practices. This is because the adversarial perturbations are defined as the "imperceptible" perturbations, so the perturbed input of one class should not cover the support of another class. The perturbation defined as the bijection mapping here changes the semantic meanings of the input for sure and should not be considered "imperceptible".
    * In the first paragraph of Section 3.1, the distribution P' should depends on the model parameters, because adversarial examples are generated specifically for a model. To be rigorous, the authors should point this out.

2. [Algorithm Design]
    * The sentence below Equation (12) is incorrect, because the margin itself is a bound. The margin defined in (12) is negative does not necessarily mean the input is adversarial vulnerable, it only means the current input cannot be certified robust.
    * The exponential of the margin does not imply the right hand side in formula (13). $s$ is defined as the ratio of the adversarial and clean conditional probability, which shows no connection to the IBP margin. In addition, the tightness of IBP margin differs from instance to instance.
    * The algorithm has too many additional hyper-parameters, including $\alpha$, $\gamma$ and $\epsilon_{I, maxoff}$. The authors should conduct ablation study to show how sensitive the performance is to these additional hyper-parameters and whether or not the optimal hyper-parameters are too sensitive to the task and model architectures. I believe this will greatly facilitate the practitioners.

3. [Experiments]
    * The strength of the baselines are questionable and the results of the baselines are not consistent with the previous works. For example, the Table 3 in the IBP paper (Ref[A]) shows the IBP certified error on MNIST ($\epsilon = 0.3$) is $8.21%$ and on CIFAR10 ($\epsilon = 8 / 255$) is $68.44%$; both are better than the baseline results shown in Table 2 and Table 3 of this paper. The CROWN-IBP results in the original paper (Ref[B]) on CIFAR10 ($\epsilon = 8 / 255$) is $66.94$ in their Table 3 and is better than the reported results in Table 5 of this paper. I agree that the training $\epsilon$ here is a bit different, but the authors should present the baseline results in their optimal hyper-parameters settings.

4. [Writing and Presentation]
    * Some claims in this paper is not correct. For example, in the last paragraph of page 1, the authors say the incomplete certifier provides looser bounds by convex adversarial polytope. This is not comprehensive, because some other incomplete certifier uses semidefinite programming (Ref[C]) or randomized smoothing (Ref[D]). Convex polytope is only one category of the incomplete certifiers.
    * The definition of formula (4) is wrong. We should use the lower bound for the true labels and the upper bounds for the rest.

Reference

Ref[A]: Gowal, S., Dvijotham, K., Stanforth, R., Bunel, R., Qin, C., Uesato, J., ... & Kohli, P. (2018). On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv:1810.12715.

Ref[B]: Zhang, H., Chen, H., Xiao, C., Gowal, S., Stanforth, R., Li, B., ... & Hsieh, C. J. (2019, September). Towards Stable and Efficient Training of Verifiably Robust Neural Networks. In International Conference on Learning Representations.

Ref[C]: Raghunathan, A., Steinhardt, J., & Liang, P. (2018, February). Certified Defenses against Adversarial Examples. In International Conference on Learning Representations.

Ref[D]: Cohen, J., Rosenfeld, E., & Kolter, Z. (2019, May). Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning (pp. 1310-1320). PMLR.
summary_of_the_review: Due to the concerns pointed above, I do not think the current manuscript is suitable for publication. However, I welcome the authors to clear my concerns in the rebuttal period. I will do a re-evaluation then.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes to integrate training data reweighting and sample-level perturbation budget tuning to improve relaxation-based robust training like IBP and CROWN-IBP. The overhead is small and the improvement of the certified accuracy is +1.38% on CROWN-IBP and +2.17% on IBP on CIFAR-10.
main_review: The paper mainly proposes two tactics: training data reweighting, and sample-level $\varepsilon$ tuning. The training data reweighting is backed up by theoretical justifications and intuitive explanations. The sample-level $\varepsilon$ tuning is relatively intuitive. Both tactics contribute to a better certified robust training approach.

Strengths:
- The proposed two tactics are novel and solid.
- The theoretical and empirical illustrations of the proposed method are insightful.
- Demonstrated by experimental results, the proposed method is effective. The relaxation-based training is hard to improve where recent work like CROWN-IBP, Auto-LiRPA, etc can only get 1%-3% improvements despite their complex techniques. This work is simple but has shown a similar level of improvement.

Weaknesses:
- The experimental evaluation is not comprehensive enough. The following results would be helpful if provided:

  - Experiments on more model architectures other than DM-Large to show generalizability.

  - Combine the proposed method with Auto-LiRPA [1], since Auto-LiRPA achieves a lower certified error compared with IBP and CROWN-IBP, e.g., 66.62% on CIFAR-10 against 8/255 $\ell_\infty$ perturbations.

  - Show running time statistics to quantitatively justify the small overhead of the proposed method.

  - Provide code for replicating the experiments, or provide a reproducibility statement.

  - How many times did you replicate the experiments? It would be good to report this number in the paper.

- Several writing issues as listed below.

Minor:
1. The paper title uses "certification-based" while the first sentence in the abstract uses "verification-based". Please make them consistent.
2. Section 1, first paragraph: FGSM were the very first approaches => was the very first approach.
3. Section 3.1: ${\mathbb{E}}\_{(\mathbf{x}',y) \sim P} [l(f_{\theta}(\mathbf{x}'), y)]$ => $\mathbb{E}\_{(\mathbf{x}',y)\sim P'} [l(f_{\theta}(\mathbf{x}'), y)]$
4. Example1: and vice versa for examples with examples with ′+′ label moving to the external arc => and vice versa for examples with ′+′ label moving to the external arc
5. Algorithm 1 in Appendix C: How does Algorithm 1 combine with the whole training pipeline? Is there any training process that optimizes the model weights at the end of each inside loop?

Suggestions:
1. It would be good to discuss randomized smoothing and related training (Cohen et al ICML 2019, Lecuyer et al S&P 2019, Salman et al NeurIPS 2019), Lipschitz-based robustness and related training (Tsuzuku et al NIPS 2018, Trockman et al ICML 2021) in related work. They also provide verifiable robustness.
2. It would be good to move the algorithm description in Appendix C to the main text, otherwise the hyperparameter $\varepsilon_{maxoff}$ shown in Section 4.2.2 has no formal definition.

Question:
When computing the sample weights, what $\varepsilon$ is used for IBP to compute the margin (Eq. 11)? Is it the original $\varepsilon$ or the auto-tuned $\varepsilon$? If it is former, I worry the IBP bound is too loose for hard samples with large original $\varepsilon$, where maybe smaller $\varepsilon$ could be better. If it is latter, the auto-tuned $\varepsilon$ may deviate too much from the original required $\varepsilon$, failing to precisely reflect the actual margin bound under the original required $\varepsilon$.

[1] Xu, Kaidi, et al. "Automatic perturbation analysis for scalable certified robustness and beyond." Advances in Neural Information Processing Systems 33 (2020).
summary_of_the_review: The proposed two tactics are backed up by intuitive but useful insights and shown effective for relaxation-based training. Therefore, the work would be inspirational to the community.
However, the current experimental evaluation is not comprehensive enough and lacks several important details, so it is a bit difficult to tell whether the approach is generally effective or not. Also, the presentation can be improved.
Given these concerns, I think the paper is marginally below the threshold. If more experimental details are provided during the discussion phase, I am happy to re-evaluate this paper.
review_title: null

Meta-review: The authors develop an approach to improve upon methods for training certifiably robust models. They propose an input dependent margin-based weighting and an automatically generated curriculum schedule and demonstrate improvements on training certifiably robust models on MNIST and CIFAR-10.

Reviewers agree that the paper makes interesting and novel contributions. However, the lack of novelty in the approach combined with the limited empirical gains make it difficult to justify acceptance. In particular, reviewers raise valid concerns on the quality of experiments comparing to prior work (in particular Crown-IBP (Zhang et al 2020) and COLT (Balunovic & Vechev 2020)) (in particular hyperparameter tuning, inability to recreate baseline results and unjustified claims that the prior art cannot run on GPU hardware). Further, even the gains demonstrated are marginal. 

Hence, I recommend rejection, but encourage the authors to revise the paper based on the feedback received.
Decision: Reject