Understanding Certified Training with Interval Bound Propagation

We thank the reviewer for their interesting questions, which we address below, and are happy to hear that they believe both the problem we work on as well as our novel results to be of interest to the community.

Q1. Given that tightness does not directly imply robustness, why is the notion of tightness, introduced in this work, useful beyond the standard IBP loss? Further, does it yield any different trends than (inverse) IBP loss?

As this question is the Reviewer’s main concern, we break it down into multiple sub-questions and address them individually:

Q1.1: Does a low IBP loss imply robustness?
Not necessarily. For example, if the minimal logit difference to the runner-up class is 0, we can obtain a robust cross-entropy loss of $log(2)=0.7$, which is lower than the losses typically achieved with IBP training [1]. Similarly, as we scale the final layer weights towards 0, the IBP loss converges to $log(K)$, which is less than the IBP loss at initialization (see the new Figure 15) but will hurt certified training. Finally, networks trained with SABR often have a 10x larger IBP loss than IBP-trained networks, while actually being more robust (see Figure 10 in Müller et al. [1]). We thus conclude that a small IBP loss is neither necessary nor sufficient for robustness, and state-of-the-art SABR-trained networks in fact exhibit very high IBP losses.

Q1.2: Does the initialization of Shi et al., 2021 [2] improve certified training performance by reducing IBP loss (at initialization)?
We want to highlight that while Shi et al.’s initialization reduces IBP loss at initialization (although the first epoch (for CIFAR-10) does not use an IBP loss), they mostly prevent gradient explosions during the epsilon annealing phase of the training schedule thus allowing for much faster annealing and training schedules (see their Section 3.2.1). In fact, just using their initialization without additional regularizers can even hurt final performance (see their Table 4).

Q1.3: Do tightness and inverse IBP loss exhibit similar trends with width, depth, and perturbation magnitude?
No. In the new Figure 15 in Appendix D.4, we compare tightness and inverse BP loss over different depths and widths at initialization (using the de facto standard initialization by Shi et al. [2]) and observe opposite trends. The inverse IBP loss increases slightly with depth and stays roughly constant with width, while tightness decreases by multiple orders of magnitude in both cases. This is generally expected, as Shi et al.’s [2] initialization aims to keep the box size constant throughout the network. We have further computed the IBP loss for the settings and networks considered in Figure 7 using either a constant or the same epsilon as for training and evaluating the certified accuracy (Figure 16). We find the inverse IBP loss depends strongly on the epsilon used for evaluation. When using the same epsilon as for training (which we believe to be the most natural choice), we observe the largest inverse IBP losses for the smallest perturbation magnitudes, decreasing as perturbation magnitudes increase. This is the exact opposite of what we observe for tightness. In summary, inverse IBP loss shows completely different trends over architecture choices and (training) perturbation magnitudes. We have thus established the complementarity of tightness and the (inverse) IBP loss.

Q1.4: What is the value of the tightness metric as an analysis tool?
Tightness is the (to the best of our knowledge) first metric to consider the ratio of optimal and relaxed bound sizes in neural network verification. This allows us to directly quantify how strongly regularized a network is (or would need to be) for (IBP) certifiability and what methodological choices dominate this regularization strength. In contrast to the IBP loss, tightness disentangles robustness from accuracy. This is of particular importance as regularization for robustness, in particular higher tightness, often reduces accuracy, making their interaction hard to analyze. This perspective is, e.g., key to the interpretation of the results in Figure 5, suggested by Theorem 3.10, and leads to our architectural modifications that yield state-of-the-art results (Table 1). See also our answer to Q2 for concrete insights into, e.g., the mechanisms behind SABR training.

References:
[1] Müller et al. "Certified training: Small boxes are all you need." ICLR 2023
[2] Shi et al. "Fast certified robust training with short warmup." NeurIPS 2021

We thank the reviewer for their interesting questions and thoughtful suggestions. We are encouraged to hear that they consider our work to be both relevant and novel. Below, we address their remaining questions.

Q1. Can you discuss the implications of the (strong) assumptions (DLNs and Gaussian weight distributions) made during the theoretical analysis?

First, we want to highlight that the definitions of propagation invariance and bound tightness (Lemma 3.3 and Definition 3.6) do not assume a Gaussian weight distribution. Only our results on tightness at initialization make this assumption. There, however, it agrees well with commonly used initialization schemes, which draw weights from a Gaussian distribution. Second, while we do assume (local) linearity for many of our theoretical results, we want to highlight that ReLU networks are locally linear and thus behave linearly for infinitesimally small perturbation magnitudes. Even at the typically considered perturbation magnitudes, as few as 1% of ReLUs are unstable, leading to empirically small approximation errors (see Figure 2 and the new Figure 13). As we empirically validate all our results on ReLU networks and even generalize some of them theoretically to this setting (see Corollary A.2), we believe the insights obtained under the assumption of local linearity to be valuable and likely to generalize.

Q2. Can you discuss the generality of the empirical support of your theoretical findings given that some experiments are conducted for only one dataset and network architecture?

As most of our experiments involve sweeps over either architectures or perturbation magnitudes and certification with a precise neural network verifier, they can be quite compute-intensive. We have thus focused on what we believe to be the most informative and interesting settings, using the popular CNN7 (which yields state-of-the-art results in most settings) when trying to demonstrate performance improvements and a smaller CNN3 when computing exact bounds using MILP or aiming to certify PGD trained networks, which would be intractable for larger architectures. In addition, we confirm key results across multiple training methods and datasets (see below), e.g., while the results in Figure 6 already constitute a new state-of-the-art, we confirm it on CIFAR-10 in Table 1, where we also observe strict improvements on multiple state-of-the-art training methods. We have added new results (Figures 13 and 14) to the appendix confirming the results previously established in only one setting (Figures 2 and 9). Below, we provide an overview of results and settings we considered.

If the reviewer believes any results to still be insufficiently established, we are more than happy to conduct additional experiments to address this.

Approximation error between local (Definition 3.6) and true tightness: CNN3 on MNIST for 5 perturbation magnitudes (Figure 2). Now additionally for CIFAR-10 (Figure 13)

Tightness at initialization (Lemma 3.7 and Corollary 3.8, rigorous theoretical results): 11 architectures based on CNN7 on CIFAR-10, although this is mostly dataset and completely perturbation magnitude independent, as we consider the network at initializtion (Figure 3).

Low dimensional embedding and reconstruction (Theorem 3.10, rigorous theoretical results): 19 toy datasets constructed from projections of multivariate standard Gaussians (Figure 4).

Effect of depth on trained networks: 6 architectures derived from CNN7 for CIFAR-10 at $\epsilon=2/255$ (Figure 5).

Effect of width on trained networks: 6 architectures derived from CNN7 for CIFAR-10 at $\epsilon=2/255$ (Figure 5) and 3 training methods, two width factors, and 2 datasets (all using state-of-the-art networks as baseline) (Table 1 and Figure 6), now extended to 3 datasets and 5 perturbation magnitudes.

Effect of perturbation magnitude on trained networks (Theorem 3.9): 8 perturbation magnitudes and 3 training methods for CNN3 and CIFAR-10 (Figure 7). 2 Perturbation magnitudes and 5 training methods for a state-of-the-art architecture from prior work (Table 2).

Regularization strength at same perturbation magnitude: 2 training methods with 4 regularization strengths each for CNN7 on CIFAR-10 (Figures 8 and 12).

Perturbation magnitude vs propagation region size: SABR training with 3 different lambda and 6 perturbation region sizes each for a CNN3 on CIFAR-10 (Figure 9), now also for MNIST (Figure 14).

References:
[1] Müller et al. "Certified training: Small boxes are all you need." ICLR 2023
[2] Shi et al. "Fast certified robust training with short warmup." NeurIPS 2021
[3] Mao et al. "Connecting Certified and Adversarial Training." NeurIPS 2023
[4] Singh et al. "An abstract domain for certifying neural networks." POPL 2019

We thank the reviewer for their interesting questions and thoughtful suggestions. We are encouraged to hear that they consider our work to be well-motivated and our experiments comprehensive. Below, we address their remaining questions.

Q1. Can you add more intuitions for the theoretical results you prove, e.g., Theorem 3.9?
While many of the proofs are quite technical, the results are intuitive, we have thus focused on providing intuitions on the results rather than the proof techniques.
For example, the proof of Theorem 3.9 uses a first-order Taylor approximation (in perturbation magnitude) of the robust risk to show that the gradient change $R(\epsilon + \Delta \epsilon) - R(\epsilon)$ with increasing $\epsilon$ is aligned with the tightness gradient. We then sum over many perturbation magnitude increments $\Delta \epsilon$, and use the linearity of the inner product to obtain that $R(\epsilon) - R(0)$ is also aligned with the tightness gradient. As we let $\Delta$ go against 0, we obtain our result.
The best intuition we can give is that every increase of the perturbation magnitude makes the gradient more aligned with tightness.

Q2. Can you provide more details on the experimental setup? For example, the setting of Fig. 3 remains unclear.
Of course! We have added the key details for every experiment (in particular for Figures 2, 3, and 9) to the main text. However, as we consider a large number of training methods and multiple datasets, each with different (default for these methods) hyperparameters, we defer additional details to Appendix C (almost one page) due to space constraints.

Q3. Why is the certified accuracy decreasing as $\epsilon$ increases in the middle part of Figure 7?
In Figure 7, we vary the $\epsilon$ used for both training and testing. Thus, the certified accuracy in the middle of Figure 7 is w.r.t. larger perturbation magnitudes as $\epsilon$ increases, which makes it a strictly harder task. Thus two effects come together. First, standard accuracy decreases (Figure 7 left) as networks are more heavily regularized for these larger perturbation magnitudes (see increases in tightness in Figure 7 right). Second, for the same network, every sample that is robust at $\epsilon$ is also robust at $\epsilon’ < \epsilon$ but not vice versa, thus certified accuracy is always monotonically decreasing with perturbation magnitude (for a fixed network).

Q4: Can you provide a more detailed explanation of your results on the robustness accuracy trade-off and in particular how your results on tightness relate to certified accuracy?
Yes. We argue along the following lines: To achieve high certified accuracies, certified training is required*. Empirically, IBP-based training methods have proven the most successful, yielding state-of-the-art results in every setting [1,2,3]. However, training with IBP increases tightness (Theorem 3.9), which induces strong regularization (Theorem 3.4), which in turn leads to reduced accuracy. We thus provide an explanation for the robustness accuracy trade-off for IBP-based training methods, which are practically the most relevant group of certified training methods.

*We note that while the combination of a relatively small network (CNN3) and a complete verifier (MN-BaB) yields comparatively high certified accuracies for the PGD-trained network in Figure 7, especially at small perturbation magnitudes, certified training methods are required for state-of-the-art performance (which require larger networks).

We hope to have been able to address the reviewer's concerns, are happy to answer any follow-up questions, and look forward to their reply.

References:
[1] Müller et al. "Certified training: Small boxes are all you need." ICLR 2023
[2] Mao et al. "Connecting Certified and Adversarial Training." NeurIPS 2023
[3] De Palma et al. "Expressive Losses for Verified Robustness via Convex Combinations." arXiv 2023

We thank the reviewer for their insightful questions, which we address below and are encouraged to hear that they acknowledge our results to be interesting and novel.

Q1. Why does a lower tightness lead to higher accuracy in Figure 5? And why is increasing depth worse than increasing the width if less tightness is desirable?
At initialization, both higher width and depth decrease tightness significantly (see Figure 3). Then, IBP-based training increases tightness (Theorem 3.9), inducing (strong) regularization in the process (Theorem 3.4). The larger this increase in tightness, the stronger the induced regularization. As (IBP-)trained networks exhibit roughly similar tightness across depths and widths (compared to those at initialization), smaller tightness at initialization requires stronger regularization to reach this level (see the updated Figure 5). If this increase in regularization dominates the increase in capacity, we achieve worse goodness of fit (training set robust accuracy) and thus performance. This is what we observe in Figure 5, tightness increases much more over training for large depth than for large width, indicating stronger regularization, explaining the worse certified accuracy. So less tightness is only a positive sign (of less regularization) after IBP-training.

Q2. Can you relate your results to those of Wang et al. [1] which conclude that there are diminishing improvements with increasing width in IBP training?
First, we want to highlight that we already cite Wang et al. [1] in our related work section. Their work considers the convergence of IBP training in the over-parameterized setting for small perturbation magnitudes with high probability and finds that sufficient width is required to achieve zero training loss with high probability. In this setting, the required width increases inversely proportional to the square of the non-convergence probability (for very small perturbation magnitudes). However, while this can be seen as diminishing “improvements” of convergence probability with increasing width, we observe diminishing improvements in test set certified accuracy, a fundamentally different metric. Further, the work of Wang et al. [1] is limited to 10x smaller perturbations than we consider (see e.g. their Figure 1).

Q3. Can you highlight the potential improvements to certified training enabled by your analysis?
We believe that tightness can become a valuable practical and theoretical analysis tool for designing and understanding new certified training methods, as it allows measuring the regularization strength induced by IBP-based training. For example, we demonstrate in Figure 9 that tightness and thus regularization strength are dominated by the size of the propagation region instead of the permissible perturbation magnitude, providing deep insights into the success of SABR [2]. Further, it provides a promising new angle to theoretically investigate IBP-based training. Finally, our theoretical results directly predicted architectures yielding improvements over the previous state-of-the-art (see Table 1 and Figure 6).

We hope to have been able to address all the reviewer's concerns, are happy to answer any follow-up questions they might have, and are looking forward to their reply.

References:
[1] Wang et al. "On the convergence of certified robust training with interval bound propagation." ICLR 2022
[2] Müller et al. "Certified training: Small boxes are all you need." ICLR 2023