Q: In Table 1, standard IBP on CIFAR-10 (2/255) has natural accuracy 48.05% and certified accuracy 37.69%; in Table 3, the two reported numbers are 54.92% and 45.36%. Is this solely because CNN5 is better than CNN3? Why not always use a bigger model, e.g., CNN7?

The discrepancy between results in Tables 1 and 3 is indeed caused by a difference in network size and capacity. Specifically, CNN3 has ~5k parameters for MNIST and ~7k parameters for CIFAR-10, while CNN5 has 166k parameters for MNIST and 281k parameters for CIFAR-10. In general, using larger models improves performance and for this reason, we experimented with RGS on CNN5, as we were not able to scale PGPE to this architecture. Moreover, our results in Table 3 also show that further increasing network capacity (from CNN5 to CNN5-Large) also improves performance. Unfortunately, our best-performing method on this architecture (DP-RGS) is unable to scale to the SOTA architecture CNN7 because of memory constraints: training even with DeepPoly-GRAD on CNN7, with a batch size of 1 requires ~100GB of VRAM memory and even using high-end GPUs, the training time would be prohibitively large. Note that adding RGS would only increase the training time by a factor of 2, while using the same amount of memory, thus the main bottleneck comes from the expensive DeepPoly relaxation.

Q: Could you also add RGS results in Table 1?

Sure. We added results for RGS in Table 1 in the revised manuscript.

Q: DeepPoly-GRAD achieves 90.04% certified accuracy on MNIST (0.1) in Table 1; in Table 2 this number is only 68.47%. Is this an error?

We would like to thank the reviewer for the insightful observation. We have checked our data and found there was an error in collecting this number, and the correct number for Table 2 is 82.04%. Note that this corrected number does not alter any of the observations and claims made with respect to this table. The other numbers have been carefully rechecked to avoid other potential number collection errors. This has been fixed in the revised manuscript.

Q: Is it correct that you are only changing the training loss of the model, but you are not changing the way of certifying the model?

Yes. GLS is a modification to the training loss, thus the certification procedure remains the same. In particular, we use MN-BaB, one of the SOTA complete certification algorithms, throughout this work.

References

[1] Lee et al., Towards better understanding of training certifiably robust models against adversarial examples.

[2] Jovanovic et al., On the Paradox of Certified Training.

We are happy to hear that Reviewer $\Rx$ finds our paper easy to read and understand. In the following, we address all concrete questions raised by Reviewer $\Rx$.

Q: Is the only novelty of this submission combining existing things together, thus incremental?

The main novelty of this study is a solution regarding the paradox of certified training. We acknowledge that the concept of GLS and the related algorithms, PGPE and RGS, have been developed by previous works. However, these concepts and algorithms have not yet been known to be effective against the paradox of certified training. We note that this paradox is considered strongly problematic [1,2], but yet no effective solution is found despite many reasons identified. Therefore, the significance of this study is to show that GLS simultaneously addresses all identified reasons behind the paradox of certified training, both theoretically (Theorem 3.1) and empirically (through extensive evaluation with PGPE and RGS).

Q: Performance-wise, the best PGPE numbers are worse than IBP-GRAD in large perturbation settings. Does DP-PGPE work simply because optimizing with the PGPE algorithm makes IBP worse? Is the improvement achieved in small perturbation settings trivial? Is there any evidence that the proposed method works in practice?

While DeepPoly-PGPE does not outperform IBP-GRAD in large perturbation settings, the method’s efficacy cannot be attributed simply to PGPE making IBP worse. We note that the goal of our experiment in Table 1 is not to show that PGPE is the best method one should use for certified training. Instead, Table 1 demonstrates that tight relaxations, such as DeepPoly, can achieve better results than loose relaxations, like IBP, when the undesired optimization barriers related to DeepPoly are mitigated by GLS algorithms such as PGPE. The optimization power of PGPE is clearly lowered because of only estimating low-rank gradients, therefore the results of IBP-PGPE are always lower than IBP-GRAD, since IBP benefits less from the theoretical properties of GLS (IBP is continuous and more smooth than tight relaxations, etc.). More importantly, the advantages of GLS instantiated by PGPE outweigh the disadvantages of low-power optimization when training with tight relaxations such as DeepPoly, resulting in better performance for DeepPoly-PGPE compared to DeepPoly-GRAD, which is the main goal.

The performance improvements obtained by PGPE + DeepPoly in Table 1 are not very substantial, and we attribute this to (1) the weak optimization power of PGPE and (2) the limited capacity of the networks used. We note that Table 1 represents a proof-of-concept for the promise of GLS to solve the paradox, while in Table 3 we show that RGS, a much stronger optimization algorithm, applied to much larger networks (CNN5 is two orders of magnitude larger than CNN3) also achieves more substantial improvements over IBP-GRAD and even SOTA grad-based methods.

While our PGPE experiments mostly serve as an empirical validation of the theoretical insight that GLS has the potential to solve the paradox of certified training, our findings also show two main benefits of the PGPE with potential practical applicability: (1) PGPE can be used to train networks using even tighter relaxations that produce non-differentiable loss surfaces, further improving performance (Table 2) and (2) when the trained network has a size comparable to the population size used in PGPE, the problem with low-rank gradient optimization fades and PGPE shows improved performance (Table 7 in Appendix). These benefits cannot be used for large-scale practical applications such as computer vision and language processing, but could still enhance both the accuracy and robustness of small-scale networks deployed in safety-critical environments such as medical devices and aircraft control.

Q: Could you apply RGS to CROWN-IBP on CNN7?

Sure, we added new experimental results in Appendix D1.

We show that CROWN-IBP-RGS improves over CROWN-IBP-GRAD on CNN7, consistent with our previous result that GLS improves tight relaxations, but we also observe that more future work is required for the use of BatchNorm layers. This is because RGS creates multiple perturbed copies of the original network, thus BatchNorm, in its original form, does not combine naturally with RGS. We also observe that the trends are similar to those observed for the CNN5 architecture, so we would expect the same generalization for DeepPoly training, although it is too costly to run on CNN7. The results showcase that the promise of using GLS for certified training with tighter relaxations also scales to SOTA architectures.

Q: What do Italic numbers mean in Table 3?

In Table 3, Italic numbers represent the SOTA results obtained on CNN7, reported by [1]. They represent the best that the current IBP-based methods can achieve. We note that these results are based on a model architecture that is more than 10 times larger than CNN5-L reported in Table 3. We have also clarified this in the revised manuscript.

Q: DP-RGS is not formally defined. Is this DeepPoly-RGS?

Yes, this means DeepPoly-RGS. We have changed all instances of DP-RGS to DeepPoly-RGS in the revised manuscript for clarity.

References

[1] Mao et al., CTBENCH: A Library and Benchmark for Certified Training

[2] Shi et al., Fast Certified Robust Training with Short Warmup

[3] Mueller et al., Certified Training: Small Boxes are All You Need

[4] Mao et al., Connecting Certified and Adversarial Training

[5] De Palma et al., Expressive Losses for Verified Robustness via Convex Combinations

[6] Jovanovic et al., On the Paradox of Certified Training

[7] Xu et al., Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond

We are happy to hear that Reviewer $\Rd$ considers our studied problem important, the proposed method well-motivated and the empirical results on small perturbation settings impressive. We are particularly encouraged by the positive opinions from Reviewer $\Rd$. In the following, we address all concrete questions raised by Reviewer $\Rd$.

Q: Could you discuss large perturbation settings in the main text rather than appendix? Why is the performance of tight relaxations still worse than IBP even after applying GLS on large perturbation settings?

Yes. We now highlight the conclusions of the large perturbation settings experiments from the appendix in the main text (see line 484). We note that the results table and a more detailed discussion are still included in the appendix due to the page limit.

Indeed, DeepPoly-RGS and DeepPoly-PGPE are still worse than IBP-GRAD in large perturbation settings despite significant improvement in small perturbation settings, e.g., CIFAR $\epsilon=2/255$. While the real reasons are not yet identified, we propose a few speculative hypotheses next. First, RGS and PGPE are off-the-shelf solvers and minimally revised here, they may not fully exploit the strength of GLS, and there may exist more effective GLS methods. For example, PGPE has weaker optimization capability when the number of parameters to optimize is high (Table 6), although it can optimize non-differentiable relaxations (Table 2). In this regard, more effective GLS methods need to be developed in future work. Second, large perturbation settings may require more regularization to generalize well. This is partially supported by the fact that none of the SOTA IBP-based methods significantly improves over IBP in large perturbation settings [1]. In this regard, more insights towards the inconsistency between small and large perturbation settings need to be developed in future work.

Q: Line 425-426 states that DeepPoly bounds now yield the best certified accuracy across all settings. How should this be interpreted?

We note that this statement is to compare different relaxations under the same optimization algorithm, PGPE. This is because different optimization algorithms have different optimization capabilities, thus different relaxations cannot be directly compared when optimized with different optimization algorithms (discussed in Section 4.1). The main goal of Table 1 (the study related to this statement) is to show that after mitigating all the problems identified (non-smoothness, etc.), tight relaxations (DeepPoly) can get better results than loose relaxations (IBP) with the same optimization algorithm (PGPE), thus resolving the paradox of certified training in this case, rather than directly supporting that DeepPoly-PGPE is uniformly better than IBP-GRAD (which is only established in small perturbation settings). The key implication is that if more powerful GLS optimization algorithms are developed in the future, DeepPoly has the potential to exceed IBP even in large perturbation settings. We will make this logic more clear in the revised manuscript.

Q: Line 418 states that across all these settings IBP dominates the other methods (CROWN-IBP). Is this in conflict with the original CROWN-IBP paper, which shows it is better than IBP?

They are not in conflict, because IBP has been significantly improved by [2]. Specifically, [2] proposes special initialization and regularization to improve IBP, while CROWN-IBP benefits less from these specialized training tricks [2]. The community [3,4,5] has been using this improved version of IBP, and refers to it as IBP as well, which is also adopted by our paper. In addition, [6] finds that for small networks, IBP performs better than CROWN-IBP even without these tricks, while the original CROWN-IBP paper uses a large network. Therefore, both our and the original paper are correct.

Q: Could you provide a comparison with CROWN-IBP in Table 3?

Yes. We have added CROWN-IBP-RGS results in the table for the CNN5 architecture on MNIST and CIFAR and TinyImageNet. We observe that CROWN-IBP-RGS is better than CROWN-IBP-GRAD in these settings, similar to the case of DeepPoly, as expected.

We note that due to limited time and resources, for TinyImageNet we only run the Loss-Fusion [7] version of CROWN-IBP. This version is a lot cheaper (2x IBP cost) compared to normal CROWN-IBP due to the large number of classes in the TinyImageNet dataset (200 classes meaning ~200x IBP cost). We will also add results for the normal CROWN-IBP in the final manuscript.

Q: The current introduction is more work-related. Could the authors provide a more detailed introduction about certified robustness?

Sure. While the current introduction provides sufficient background on certified training which is the focus of our work, it does not elaborate on the general certified robustness which does not directly affect understanding of this work, due to page limit. We will incorporate a more detailed introduction to the general certified robustness in the appendix.

Q: What is the meaning of the terms "soundness" and "sensitivity"? Should they be explicitly defined in the paper?

Soundness is a textbook term in certification. A certification is sound if and only if the certified property holds in reality. Sensitivity is defined by [2] to be the degree of the output polynomial quotient, i.e., $P(x) / Q(x)$, where $P(x)$ and $Q(x)$ are polynomials. Such a definition is overly obfuscated and complex, only covers a special function family, and serves as a convenient theoretical proxy in [2]. This is why we replace it with a more friendly and general metric, termed deviation from convexity, as both analyze the optimization difficulty. We will add a formal definition of them in the appendix for interested readers.

Q: Could you give additional references or explanations for the statement "While CROWN-IBP is not strictly more or less precise than either IBP or DeepPoly"?

Yes. This is established by [2] and we will reference them in this statement. Intuitively, this is because DeepPoly is not strictly more precise than IBP, thus CROWN-IBP which adds a DeepPoly component is not strictly more precise than IBP and vice-versa.

In practice even though [2] shows that CROWN-IBP is on average more precise than IBP, there are cases when the result of propagating the same input region using CROWN-IBP neither includes nor is included in the propagation obtained by IBP. The same is true for DeepPoly.

Q: Could you include precise definitions for “adversarial attack” and “adversarial robustness” in contrast with “certified robustness”?

Yes. The revised manuscript includes more precise definitions for these terms.

Q: Are paragraph titles "Training for Robustness" and "Adversarial Training" in Section 2.1 redundant?

Indeed, the paragraph titles are slightly overlapping. We have fixed this in the revised manuscript.

Q: Could you provide more experimental details about Figure 1 as it does not specify dataset and architecture?

Figure 1 is an easy-to-understand version of Table 1, presented in the introduction section, without overwhelming experimental details. These numbers are based on CNN3 networks evaluated on MNIST with $\epsilon=0.1$. We have specified this in the revised manuscript.

Q: Could you provide results regarding the standard deviations of performance over multiple runs?

Most of our experiments regarding DeepPoly training are very expensive, requiring multiple days on 8 GPUs, which makes providing standard deviation results practically infeasible.

Comment

We thank Reviewer $\Rv$ for their valuable suggestions on our writing. We have addressed all concrete writing problems raised by Reviewer $\Rv$. If Reviewer $\Rv$ has additional questions regarding writing, we are happy to further address them.

References

[1] Wen and Ma, How Does Sharpness-Aware Minimization Minimize Sharpness?

[2] Jovanovic et al., On the Paradox of Certified Training

We are happy to hear that Reviewer $\Rv$ considers our work to be novel and agrees that we study a very important problem. In the following, we address all concrete questions raised by Reviewer $\Rv$.

Q: The proofs are not fully rigorous. Could the authors provide a better structure and formalization in the proof?

We have completely rewritten the full proof. The new proof features the following improvements: (1) it extends the original proof from 1-dimension to d-dimension; (2) using the fact that GLS is equivalent to Gaussian convolution, it avoids explicit integral, improving readability; (3) notations are defined clearly at the beginning of the proof, avoiding potential confusion; (4) it uses a better proxy (named deviation from convexity) for non-convexity than sharpness, by directly measuring how non-convex a function is; (5) it reasons more explicitly, e.g. the existence of the $n$-th derivative is now shown explicitly, and all computations are rolled out explicitly. If Reviewer $\Rv$ further finds something unclear in the new proof, we are happy to address them.

Q: GLS brings in computational complexity, especially with PGPE, while performance benefits are marginal. What is the value of GLS (PGPE)?

PGPE and RGS are studied in this paper as concrete optimization algorithms with GLS features. They demonstrate the potential of GLS algorithms in resolving the paradox of certified training. While the current algorithms are not fully satisfying, e.g., PGPE has significant computation overhead, they successfully prove that GLS can mitigate the paradox of certified training, and have resolved it already in small perturbation settings. In this regard, they are a preliminary but successful step towards a long-known but unsolved problem. Further, RGS, as another instantiation of GLS, has significantly less overhead and scales better than PGPE. However, PGPE has its own benefits, as it allows training with non-differentiable relaxations (Table 2). Therefore, we believe both algorithms are worth discussing, and both strengthen our key conclusion: GLS can resolve the currently identified reasons of the paradox of certified training.

Q: What is the connection between sharpness-aware minimization (SAM) and GLS?

SAM algorithm as used in [1] is fundamentally different from GLS. This is because GLS takes the expectation of neighborhood loss rather than the worst-case loss; in fact, SAM is closer to adversarial training with FGSM rather than GLS. In particular, SAM does not resolve the discontinuity problem, while GLS provably solves it (Theorem 3.1). To see this, consider the threshold function $I(x>0)$ and an initial $x_0=0.1$. Any single-point gradient-based methods (including SAM) will only get zero gradients, and thus cannot optimize it. Therefore, while it is likely that GLS has the benefit of reduced sharpness as well, GLS enjoys fundamentally different benefits from SAM.

To confirm this empirically, we apply SAM to IBP and DeepPoly training. Specifically, we update the parameters with gradients computed based on the adversarially perturbed network $w^\prime = w + \rho \times \nabla_w L / \|\nabla_w L\|_2$. We train with IBP and DeepPoly on MNIST $\epsilon=0.1$ with the same CNN3 architecture used in the paper. The results are shown as follows, all networks certified with MN-BaB:

We observe that for a correctly chosen hyperparameter ($\rho = 0.01$), SAM does indeed improve performance for IBP and DP. While SAM performs better than PGPE for this very shallow network, as expected from our previous theoretical analysis, it does not address the paradox. In particular, IBP-SAM still performs better than DP-SAM uniformly for every choice of $\rho$. While combining SAM with PGPE or other certified training methods might thus constitute an interesting future direction, it does not explain the reranking of approximation methods we observe for PGPE and RGS (DP-PGPE > IBP-PGPE and DP-RGS > IBP-RGS vs IBP-SAM > DP-SAM). We therefore conclude that the sharpness-aware aspect of GLS is not (solely) responsible for its effectiveness in resolving the paradox of certified training. We also incorporate this discussion in the revised manuscript (see Appendix D4).