Towards Universal Certified Robustness with Multi-Norm Training

## Abstract

Abstract Existing certified training methods can only train models to be robust against a certain perturbation type (e.g. l ∞ subscript 𝑙 l_{\infty} italic_l start_POSTSUBSCRIPT ∞ end_POSTSUBSCRIPT or l 2 subscript 𝑙 2 l_{2} italic_l start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ). However, an l ∞ subscript 𝑙 l_{\infty} italic_l start_POSTSUBSCRIPT ∞ end_POSTSUBSCRIPT certifiably robust model may not be certifiably robust against l 2 subscript 𝑙 2 l_{2} italic_l start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT perturbation (and vice versa) and also has low robustness against other perturbations (e.g. geometric transformation). To this end, we propose the first multi-norm certified training framework CURE , consisting of a new l 2 subscript 𝑙 2 l_{2} italic_l start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT deterministic certified training defense and several multi-norm certified training methods, to attain better union robustness when training from scratch or fine-tuning a pre-trained certified model. Further, we devise bound alignment and connect natural training with certified training for better union robustness. Compared with SOTA certified training, CURE improves union robustness up to 22.8 % percent 22.8 22.8\% 22.8 % on MNIST, 23.9 % percent 23.9 23.9\% 23.9 % on CIFAR-10, and 8.0 % percent 8.0 8.0\% 8.0 % on TinyImagenet. Further, it leads to better generalization on a diverse set of challenging unseen geometric perturbations, up to 6.8 % percent 6.8 6.8\% 6.8 % on CIFAR-10. Overall, our contributions pave a path towards universal certified robustness .

## 1 Introduction

Though deep neural networks (DNNs) are widely deployed in various vision applications, they remain vulnerable to adversarial attacks (Goodfellow et al., ; Kurakin et al., ). Though many empirical defenses (Madry et al., ; Zhang et al., ; Wang et al., ) against adversarial attacks have been proposed, they do not provide provable guarantees and remain vulnerable to stronger attacks. Therefore, it is important to train DNNs to be *formally* robust against adversarial perturbations. Various works (Mirman et al., ; Gowal et al., ; Zhang et al., ; Balunović and Vechev, ; Shi et al., ; Müller et al., ; Hu et al., , ; Mao et al., ) on deterministic certified training against $l_{\infty}$ and $l_{2}$ perturbations have been proposed. However, those defenses are mostly limited to a certain type of perturbation and cannot easily be generalized to other perturbation types (Yang et al., ). Certified robustness against multiple perturbation types is essential because this better reflects real-world scenarios where adversaries can use multiple $l_{p}$ perturbations. Also,  Mangal et al. () argue that $l_{p}$ robustness is the bedrock for non-$l_{p}$ robustness. In this work, we also show that training with multi-norm robustness can lead to stronger *universal certified robustness* by generalizing better to other perturbation types such as geometric transformations (Section 5.1).

To this end, we propose the first multi-norm Certified training for Union RobustnEss (CURE) framework, consisting of a new $l_{2}$ deterministic certified training defense and several multi-norm certified training methods. Inspired by SABR (Müller et al., ), our $l_{2}$ defense first finds the $l_{2}$ adversarial examples in a slightly truncated $l_{2}$ region and then propagates the smaller $l_{\infty}$ box using the IBP loss (Gowal et al., ). For multi-norm certified training, we propose several methods based on multi-norm empirical defenses (Tramer and Boneh, ; Madaan et al., ; Croce and Hein, ). Our proposed methods successfully improve both the union and universal certified robustness, as illustrated in Table 1,  2, and  3.

However, the aforementioned methods achieve sub-optimal union robustness since they do not exploit the connections between certified training for different $l_{p}$ perturbations as well as natural training. In Figure 1(a), we show that an $l_{\infty}$ certified robust model may lack $l_{2}$ certified robustness and vice versa: $l_{\infty}$ model only has $5.4\%$ $l_{2}$ robustness and $l_{2}$ model has $0\%$ $l_{\infty}$ robustness. Thus, mitigating the tradeoff between $l_{2}$ and $l_{\infty}$ certified training is crucial. For given values of $\epsilon_{q}$ and $\epsilon_{r}$, we compare $l_{q}$ and $l_{r}$ robustness, where $l_{q}$ trained model has lower robustness against its own perturbation $l_{q}$ (e.g. $l_{\infty}$ certifiably trained model (blue) in Figure 1(a)). We observe that the $l_{q}$ robustness is the bottleneck for attaining better union accuracy when training a model from scratch. Thus, as shown in Figure 1(b), at a certain epoch during training, we find the subset of input samples $\gamma$ that IBP (Gowal et al., ) proves robustly classified with respect to the $l_{q}$ perturbations. We then propose a new bound alignment method to regularize the distributions of output bound differences, computed with IBP, for $l_{q},l_{r}$ perturbations on the correctly certified subset $\gamma$. In this way, we encourage the model *emphasize optimizing* the samples that can potentially become certifiably robust against multi-norm perturbations. Specifically, we use a KL loss to encourage the distributions of the $l_{q},l_{r}$ output bound differences on subset $\gamma$ to be close to each other for better union accuracy. Also, we find that there exist some useful components in natural training that can be extracted and leveraged to improve certified robustness (Jiang and Singh, ). To achieve this, we find and incorporate the layer-wise useful natural training components by comparing the similarity of the certified and natural training model updates. Last but not least, we show it is possible to quickly fine-tune an $l_{p}$ robust model to have superior multi-norm certified robustness using bound alignment. Due to the $l_{q}-l_{r}$ tradeoff, bound alignment effectively preserves more $l_{q}$ robustness when fine-tuning with $l_{r}$ perturbations, by focusing on the correctly certified subset. Additionally, this technique is useful for quickly attaining multi-norm robustness using wider and diverse model architectures pre-trained with single $l_{p}$ certified robustness. In Figure 1(a), we show that training from scratch (CURE-Scratch) and fine-tuning (CURE-Finetune) significantly improves union robustness compared with single norm training.

Figure: (a) $l_{\infty}-l_{2}$ tradeoff on CIFAR10 with $\epsilon_{\infty}=\frac{8}{255},\epsilon_{2}=0.5$. The X-axis represents $l_{\infty}$, $l_{2}$, and union robustness; different colors refer to different training methods.
Refer to caption: x1.png

Main Contributions: Our main contributions are as follows:

- •
We propose a new $l_{2}$ deterministic certified training defense without relying on specific model architecture choices, as well as propose multiple methods (CURE-Joint, CURE-Max, CURE-Random) for multi-norm certified training with better union and geometric certified robustness.
- •
We devise techniques including bound alignment, connecting natural training with certified training, and certified fine-tuning for better union robustness. CURE-Scratch and CURE-Finetune further facilitate the multi-norm certified training procedure and advance multi-norm robustness.
- •
Compared with SOTA single-norm training method (Müller et al., ), CURE improves union robustness up to $22.8\%$ on MNIST, $23.9\%$ on CIFAR-10, and $8.0\%$ on TinyImagenet. Further, it improves robustness against diverse unseen geometric perturbations up to $0.6\%$ on MNIST and $6.8\%$ on CIFAR-10, paving the way to universal certified robustness.

Our code is available at [https://github.com/uiuc-focal-lab/CURE](https://github.com/uiuc-focal-lab/CURE).

## 2 Related Work

Neural network verification. We consider deterministic verification methods that analyze a neural network by abstract interpretation (Gehr et al., ; Singh et al., , ), optimization via linear programming (LP) (De Palma et al., ; Wang et al., ; Müller et al., ), mixed integer linear programming (MILP) (Tjeng et al., ; Singh et al., ), and semidefinite programming (SDP) (Raghunathan et al., ; Dathathri et al., ). Many of them are *incomplete* methods, sacrificing some precision for better scalability since the neural network verification problem is generally NP-complete (Katz et al., ). In our work, we analyze multi-norm certified training using deterministic and incomplete verification methods.

Certified training. For $l_{\infty}$ certified training, a widely-used method IBP (Mirman et al., ; Gowal et al., ) minimizes a sound over-approximation of the worst-case loss, calculated using the Box relaxation method.  Wong et al. () applies DeepZ (Singh et al., ) relaxations, estimating using Cauchy random projections. CROWN-IBP (Zhang et al., ) integrates efficient Box propagation with precise linear relaxation-based bounds during the backward pass to estimate the worst-case loss.  Balunović and Vechev () consists of a verifier that aims to certify the network using convex relaxation and an adversary that tries to find inputs causing verification to fail.  Shi et al. () proposes a new weight initialization method for IBP, adds Batch Normalization (BN) to each layer and designs regularization with a short warmup schedule. Besides this, SABR (Müller et al., ) and TAPS (Mao et al., ) are unsound improvements over IBP by connecting IBP to adversarial attacks and adversarial training. For $l_{2}$ deterministic certified training, recent works (Xu et al., ; Hu et al., , ) are based on Lipschitz-based certification methods. They design specialized architectures for $l_{2}$ certified robustness, which is not naturally robust against $l_{\infty}$ perturbations. In Table 5, we show our $l_{2}$ certified defense has better $l_{2}$ robustness compared with Hu et al. () on CIFAR-10. To the best of our knowledge, CURE is the first deterministic framework for multi-norm certified robustness, compatible with diverse model architectures.

Robustness against multiple perturbations. Adversarial Training (AT) usually employs gradient descent to discover adversarial examples and incorporates them into training for enhanced adversarial robustness (Tramèr et al., ; Madry et al., ). Numerous works focus on improving robustness  (Zhang et al., ; Carmon et al., ; Raghunathan et al., ; Wang et al., ; Wu et al., ; Gowal et al., ; Zhang et al., ; Debenedetti and Troncoso—EPFL, ; Peng et al., ; Wang et al., ) against a *single* perturbation type while remaining vulnerable to other types. Tramer and Boneh (); Kang et al. () observe that robustness against $l_{p}$ attacks does not necessarily transfer to other $l_{q}$ attacks ($q\neq p$). Previous studies (Tramer and Boneh, ; Maini et al., ; Madaan et al., ; Croce and Hein, ; Jiang and Singh, ) modified Adversarial Training (AT) to enhance robustness against multiple $l_{p}$ attacks, employing average-case (Tramer and Boneh, ), worst-case (Tramer and Boneh, ; Maini et al., ; Jiang and Singh, ), and random-sampled (Madaan et al., ; Croce and Hein, ) defenses. There are also works (Nandy et al., ; Liu et al., ; Xu et al., ; Xiao et al., ; Maini et al., ) that use preprocessing, ensemble methods, mixture of experts, and stability analysis to solve this problem. For multi-norm certified robustness,  Nandi et al. () study the certified multi-norm robustness with probabilistic guarantees. They apply randomized smoothing, which is expensive to compute in nature, making it impractical for real-world applications. Our work in contrast to these works, proposes the first *deterministic* certified multi-norm training for better multi-norm and universal certified robustness.

## 3 Background

In this section, we provide the necessary background for CURE. We consider a standard classification task with samples $\{(x_{i},y_{i})\}_{i=0}^{N}$ drawn from a data distribution $\mathcal{D}$. The input consists of images $x\in\mathbb{R}^{d}$ with corresponding labels $y\in\mathbb{R}^{k}$. The objective of standard training is to obtain a classifier $f$ parameterized by $\theta$ that minimizes a loss function $\mathcal{L}:\mathbb{R}^{k}\times\mathbb{R}^{k}\rightarrow\mathbb{R}$ over $\mathcal{D}$.

### 3.1 Neural network verification

Neural network verification is used to formally prove the robustness of a neural network. The portion of the samples that can be proved robust is called *certified accuracy*. Box or interval bounded propagation (Gowal et al., ; Mirman et al., ) (IBP) is a simple yet effective verification method. Essentially, IBP calculates an over-approximation of the network’s reachable set by propagating an over-approximation of the input region $B_{p}(x,\epsilon_{p}),p\in\{2,\infty\}$ through the network, and then verifies whether all reachable outputs result in the correct classification. For instance, we consider a network $f=L_{j}\circ\sigma\circ L_{j-2}\circ\ldots\circ L_{1}$, with linear layers $L_{i}$ and ReLU activation functions $\sigma$. We then propagate $B_{p}(x,\epsilon_{p})$ layer by layer (see Gowal et al. (); Mirman et al. () for more details). For the output $o=\{\overline{o}_{i},\underline{o}_{i}\}_{i=0}^{i<k}$, the lower bound of the correct class should be higher than the upper bounds of other classes ($\forall i\in[0,k),i\neq y,\overline{o}_{i}-\underline{o}_{y}<0$) to be provably robust.

### 3.2 Training for robustness

A classifier is adversarially robust on an $l_{p}$-norm ball $B_{p}(x,\epsilon_{p})=\{x^{\prime}\in\mathbb{R}^{d}:\|x^{\prime}-x\|_{p}\leq
\epsilon_{p}\}$ if it classifies all points within the adversarial region as the correct class. That is, $f(x^{\prime})=y$ for all perturbed inputs $x^{\prime}\in B_{p}(x,\epsilon_{p})$. Training for robustness is formulated as a min-max optimization problem. Formally, the optimization problem against a specific $l_{p}$ attack can be expressed as follows:

$$ $\min_{\theta}\mathbb{E}_{(x,y)\sim{\mathcal{D}}}\left[\max_{x^{\prime}\in B_{p }(x,\epsilon_{p})}\mathcal{L}(f(x^{\prime}),y)\right]$ (1) $$

The inner maximization problem is impossible to solve exactly. Thus, it is often under or over-approximated, referred to as adversarial training (Madry et al., ; Tramèr et al., ) and certified training (Gowal et al., ; Müller et al., ), respectively. Further, the optimization described above is specific to certain $p$ values and tends to be vulnerable to other perturbation types. To address this, previous research has introduced various methods to train networks adversarially robust against multiple perturbations ($l_{1}$, $l_{2}$, and $l_{\infty}$) simultaneously. In our work, we concentrate on how to train networks to be *certifiably* robust against multiple $l_{p}$ ($l_{2}$, $l_{\infty}$) perturbations.

### 3.3 Certified training

There are two main categories of methods to train certifiably robust models: unsound and sound methods. On the one hand, IBP, a sound method, optimizes the following loss function based on logit differences:

$$ $\mathcal{L}_{\text{IBP}}(x,y,\epsilon_{\infty})=\ln(1+\sum_{i\neq y}e^{ \overline{o}_{i}-\underline{o}_{y}})$ $$

On the other hand, the state-of-the-art certified training methods SABR (Müller et al., ) and TAPs (Mao et al., ), sacrifice some soundness to get a more precise approximation, resulting in better standard and certified accuracy. To achieve this, SABR finds an adversarial example $x^{\prime}\in B_{\infty}(x,\epsilon_{\infty}-\tau_{\infty})$ and propagates a smaller box region $B_{\infty}(x^{\prime},\tau_{\infty})$ using the IBP loss, which can be expressed as follows:

$$ $\mathcal{L}_{l_{\infty}}(x,y,\epsilon_{\infty},\tau_{\infty})=\max_{x^{\prime} \in B_{\infty}(x,\epsilon_{\infty}-\tau_{\infty})}\mathcal{L}_{\text{IBP}}(x^{ \prime},y,\tau_{\infty})$ $$

Our extensions of multi-norm certified training are based on SABR.

### 3.4 Union certified accuracy and universal certified robustness

Union certified accuracy. We focus on the union threat model $\Delta=B_{2}(x,\epsilon_{2})\cup B_{\infty}(x,\epsilon_{\infty})$ which requires the DNN to be *certifiably* robust within the $l_{2}$ and $l_{\infty}$ adversarial regions simultaneously. Union accuracy is then defined as the robustness against $\Delta_{(i)}$ for each $x_{i}$ sampled from $\mathcal{D}$. In this paper, similar to the prior works (Croce and Hein, ), we use union accuracy as the main metric to evaluate the multi-norm *certified* robustness.

Universal certified robustness. We measure the generalization ability of multi-norm certified training to other perturbation types, including rotation, translation, scaling, shearing, contrast, and brightness change of geometric transformations (Balunovic et al., ; Yang et al., ). We define the average certified robustness across these adversaries as universal certified robustness.

## 4 CURE : multi-norm C ertified training for U niversal R obustn E ss

In this section, we present our multi-norm certified training framework CURE. First, we introduce a new deterministic $l_{2}$ certified training defense. Building on this, we propose several methods for multi-norm certified training against $l_{2}$, $l_{\infty}$ perturbations, which serve as the base instantiations of our framework. After that, we design new techniques to improve union-certified accuracy. We note that the techniques inside CURE are applicable to $l_{1}$ perturbations as well.

### 4.1 Certified training for multiple norms

Certified training for $l_{2}$ robustness. We propose a new deterministic certified training method against $l_{2}$ adversarial perturbations, inspired by SABR Müller et al. (). For the specified $\epsilon_{2}$ and $\tau_{2}$ values for $l_{2}$ certified training, we first search for the *$l_{2}$* adversarial examples using standard $l_{2}$ adversarial attacks (Kim, ) $x^{\prime}\in B_{2}(x,\epsilon_{2}-\tau_{2})$ in the slightly truncated $l_{2}$ ball. After that, we propagate a smaller box region $B_{\infty}(x^{\prime},\tau_{2})$ using the IBP loss. The loss we optimize can be formulated as follows:

$$ $\mathcal{L}_{l_{2}}(x,y,\epsilon_{2},\tau_{2})=\max_{x^{\prime}\in B_{2}(x, \epsilon_{2}-\tau_{2})}\mathcal{L}_{\text{IBP}}(x^{\prime},y,\tau_{2})$ $$

Certified training for multi-norm ($l_{2}$ and $l_{\infty}$) robustness. Based on the work (Tramer and Boneh, ; Madaan et al., ; Croce and Hein, ) on adversarial training for multiple norms, to combine the optimization of $l_{2}$ and $l_{\infty}$ certified training, we propose the following methods:

1. CURE-Joint: optimizes $\mathcal{L}_{l_{\infty}}$ and $\mathcal{L}_{l_{2}}$ together:

$$ $\mathcal{L}_{Joint}=(1-\alpha)\cdot\mathcal{L}_{l_{\infty}}(x,y,\epsilon_{ \infty},\tau_{\infty})+\alpha\cdot\mathcal{L}_{l_{2}}(x,y,\epsilon_{2},\tau_{2})$ $$

From the adversarial example perspective, it takes the sum of two worst-case IBP losses with $l_{\infty}$ and $l_{2}$ examples using a convex combination of weights with hyperparameter $\alpha\in[0,1]$.

2. CURE-Max: compares the values of $\mathcal{L}_{l_{2}}$ and $\mathcal{L}_{l_{\infty}}$ and takes the one with a worse (higher) IBP loss. It can be viewed as a *worst-case* defense since it considers the worst-case adversarial examples with higher IBP losses generated by the multiple perturbation types. The max loss $\mathcal{L}_{Max}$ is shown as:

$$ $\mathcal{L}_{Max}=\max_{p\in\{2,\infty\}}\max_{x^{\prime}\in B_{p}(x,\epsilon_ {p}-\tau_{p})}\mathcal{L}_{\text{IBP}}(x,y,\epsilon_{p},\tau_{p})$ $$

3. CURE-Random: randomly partitions a batch of data $(\mathbf{x},\mathbf{y})\sim\mathcal{D}$ into equal sized blocks $(\mathbf{x}_{1},\mathbf{y}_{1})$ and $(\mathbf{x}_{2},\mathbf{y}_{2})$. For $(\mathbf{x}_{1},\mathbf{y}_{1})$, we calculate the $l_{\infty}$ worst-case IBP loss $\mathcal{L}_{l_{\infty}}$ with $l_{\infty}$ perturbations. For the other half $(\mathbf{x}_{2},\mathbf{y}_{2})$, similarly, we get the $l_{2}$ worst-case IBP loss by applying $l_{2}$ perturbations. After that, we optimize the Joint loss of these two with equal weights, as shown below. In this way, we reduce the time cost of propagating the bounds and generating the adversarial examples by $\frac{1}{2}$.

$$ $\mathcal{L}_{Random}=\mathcal{L}_{l_{\infty}}(\mathbf{x}_{1},\mathbf{y}_{2}, \epsilon_{\infty},\tau_{\infty})+\mathcal{L}_{l_{2}}(\mathbf{x}_{2},\mathbf{y} _{2},\epsilon_{2},\tau_{2}),\text{where }\mathbf{x}=\mathbf{x}_{1}\cup\mathbf{ x}_{2},\mathbf{y}=\mathbf{y}_{1}\cup\mathbf{y}_{2}$ $$

### 4.2 Improved multi-norm certified training

The methods proposed above are suboptimal as they fail to fully explore the relationship between worst-case IBP losses across different perturbations, certified training (CT), and natural training (NT). To address this, we introduce the following improvements to enhance the union robustness of CURE: (1) We identify a tradeoff between $l_{2}$ and $l_{\infty}$ perturbations and propose a bound alignment technique to mitigate this, improving multi-norm robustness. (2) We analyze and connect certified and natural training to attain better union accuracy. (3) To facilitate the procedure for multi-norm robustness with pre-trained single norm models, we propose the first certified fine-tuning method, demonstrating its ability to quickly improve union accuracy using CURE (Table 1).

Bound alignment (BA) for better union robustness. As shown in Figure 1(a) and Table 1, an $l_{\infty}$ certifiably robust model usually has low $l_{2}$ certified robustness and vice versa, which reveals that there exists a tradeoff between $l_{2}$ and $l_{\infty}$ certified robustness. To this end, we investigate the $l_{q}-l_{r}$ tradeoff, which provides important intuitions for the design of bound alignment. For given values of $\epsilon_{\infty}$ and $\epsilon_{2}$, we aim to achieve good union robustness when performing multi-norm training from scratch on a model $f$. We denote $A_{u}$ as the optimal union accuracy we can get with multi-norm training. Further, we define and compare the best possible $l_{q},l_{r}$ robustness ($A_{q}$ and $A_{r}$ with Definition 4.1) with $l_{q}$ and $l_{r}$ certified defenses. In practice, we use our $l_{\infty}$ and $l_{2}$ certified defenses to approximate $A_{q}$ and $A_{r}$.

###### Definition 4.1 ( $l_{p}$ robustness $A_{p}$ ) .

Given an $\epsilon_{p}\in\mathbb{R}$ value, we define $l_{p}$ robustness, denoted as $A_{p}$, which is the final certified robustness against $l_{p}$ perturbations for a model that is fully trained using the best $l_{p}$ certified training strategy.

Without the loss of generality, we assume $A_{q}\leq A_{r}$. In other words, we select $q$ and $r$ values $\in\{\infty,2\}$ based on the empirical values we get for $A_{q}$ and $A_{r}$ using our $l_{\infty}$ and $l_{2}$ certified defenses. $A_{u}$ is upper bounded by $A_{q}$ since in the most ideal case, the model is robust against $l_{q}$ and $l_{r}$ perturbations on the same set of images with union accuracy $A_{u}=A_{q}$. Thus, to obtain better union accuracy, the goal is to have $A_{u}\rightarrow A_{q}$. How do we achieve this? Generally speaking, given a randomly initialized model $f$, we want it to *focus on optimizing* the samples which can potentially be *robust towards both* when training from scratch. Here, we take a closer look at a single training step of $f$’s optimization. During this step, we find the correctly certified $l_{q}$ subset $\gamma$ of $f$ (Definition 4.2), meaning the subset $\gamma$ for which the lower bound computed with IBP of the correct class is higher than the upper bounds of other classes.

###### Definition 4.2 (Correctly Certified $l_{q}$ Subset) .

At epoch $e$, given the perturbation size $\epsilon_{q}\in\mathbb{R}$ and model $f$, for a batch of data $(\mathbf{x},\mathbf{y})\sim\mathcal{D}$ with size $n$, we have the output upper and lower bounds computed by IBP for $l_{q}$ perturbations. We define a function $h$ for this procedure as $h(\mathbf{x})=\{\overline{\mathbf{o}}_{j},\underline{\mathbf{o}}_{j}\}_{j=0}^{
j<n}$ , where $\mathbf{o}=\{o_{i}\}_{i=0}^{i<k}$ is a vector of bounds for all classes. Then, the correctly certified subset $\gamma$ at the current step is defined as:

$$ $\forall j\in\gamma\text{ with }(\mathbf{x}_{j},\mathbf{y}_{j})\text{ and bounds }\{\overline{\mathbf{o}}_{j}=\{\overline{o}_{i}\}_{i=0}^{i<k}, \underline{\mathbf{o}}_{j}=\{\underline{o}_{i}\}_{i=0}^{i<k}\},\text{ we have }\forall i\neq y_{j},\overline{o}_{i}\leq\underline{o}_{y_{j}}.$ $$

Since $A_{q}$ serves as the upper bound of $A_{u}$, similarly, $\gamma$ can be regarded as the subset of inputs that are *more likely* to be optimized for both $l_{q}$ and $l_{r}$ robustness. For certified training, people usually optimize the model using bound differences $\{\overline{o}_{i}-\underline{o}_{y}\}_{i=0}^{i<k}$ ($y$ is the correct class). Therefore, for better union robustness $A_{u}$, we align the bound differences $\{\{\overline{o}_{i}-\underline{o}_{y}\}_{i=0,i\neq y}^{i<k}\}_{j=0}^{j<n}$ of $l_{r}$ and $l_{q}$ certified training outputs, specifically on the correctly certified $l_{q}$ subset $\gamma$. Specifically, for each batch of data $(\mathbf{x},\mathbf{y})\sim\mathcal{D}$, we generate predicted bounds $h(\mathbf{x},q)=\{\overline{\mathbf{o}}_{qj},\underline{\mathbf{o}}_{qj}\}_{j=
0}^{j<n}$ and $h(\mathbf{x},r)=\{\overline{\mathbf{o}}_{rj},\underline{\mathbf{o}}_{rj}\}_{j=
0}^{j<n}$. We denote their bounds differences after softmax normalization as $d_{q}=\{\{\overline{o}_{qi}-\underline{o}_{qy}\}_{i=0,i\neq y}^{i<k}\}_{j=0}^{
j<n}$ and $d_{r}=\{\{\overline{o}_{ri}-\underline{o}_{ry}\}_{i=0,i\neq y}^{i<k}\}_{j=0}^{
j<n}$. Then, we select indices $\gamma$, according to Definition 4.2. We denote the size of the indices as $n_{c}$. We compute a KL-divergence loss over this set of samples using $KL(d_{q}[\gamma]\|d_{r}[\gamma])$ (Eq. 2). Intuitively, we want to make $d_{r}[\gamma]$ and $d_{q}[\gamma]$ distributions close to each other, such that we gain more union robustness by regularizing the model to optimize more on the subset of examples which potentially brings $A_{u}\rightarrow A_{q}$.

$$ $\mathcal{L}_{KL}=\frac{1}{n_{c}}\cdot\sum^{n_{c}}_{i=1}\sum^{k}_{j=0}d_{q}[ \gamma[i]][j]\cdot\log\left(\frac{d_{q}[\gamma[i]][j]}{d_{r}[\gamma[i]][j]}\right)$ (2) $$

Apart from the KL loss, we add another loss term using a Max-style approach in Eq. 3, since Max has relatively good performance and small computational cost, as shown in Table 1 and Table 6. $\mathcal{L}_{Max}$ is the worst-case loss between $l_{r},l_{q}$ certified training with IBP. Our final loss $\mathcal{L_{\text{Scratch}}}$ combines $\mathcal{L}_{KL}$ and $\mathcal{L}_{Max}$, via a hyper-parameter $\eta$ in Eq. 4.

$$ $\mathcal{L}_{Max}=\max_{p\in\{2,\infty\}}\max_{x^{\prime}\in B_{p}(x,\epsilon_ {p}-\tau_{p})}\mathcal{L}_{\text{IBP}}(x,y,\epsilon_{p},\tau_{p})$ (3) $$

$$ $\mathcal{L_{\text{Scratch}}}=\mathcal{L}_{Max}+\eta\cdot\mathcal{L}_{KL}$ (4) $$

Integrate natural training (NT) into certified training (CT).
In the context of adversarial robustness,  Jiang and Singh () shows that there exist some useful components in natural training, which can be extracted and properly integrated into adversarial training to get better adversarial robustness. We propose a technique to integrate NT into certified training (CT), to enhance union-certified robustness.
To effectively connect NT with CT, we analyze the training procedures of the two. Specifically, for model $f^{(r)}$ at any epoch $r$, we examine the model updates of NT and CT over all samples from ${\mathcal{D}}$. The models $f_{n}^{(r)}$ and $f_{c}^{(r)}$ represent the results after one epoch of natural training and certified training using $\mathcal{L_{\text{Scratch}}}$, respectively, both beginning from the same initial model $f^{(r)}$. Then we compare the natural updates $g_{n}=f_{n}^{(r)}-f^{(r)}$ and certified updates $g_{c}=f_{c}^{(r)}-f^{(r)}$. Our goal is to identify useful components from $g_{n}$ and incorporate them into $g_{c}$ for better certified robustness. For a specific layer $l$, comparing $g_{n}^{l}$ and $g_{c}^{l}$, we retain a portion of $g_{n}^{l}$ according to their cosine similarity score (Eq.5). Negative scores indicate that $g_{n}^{l}$ does not contribute to certified robustness, so we discard components with similarity scores $\leq 0$. The GP (Gradient Projection) operation, defined in Eq.6, projects $g_{c}^{l}$ towards $g_{n}^{l}$.

$$ $\cos(g_{n}^{l},g_{c}^{l})={g_{n}^{l}\cdot g_{c}^{l}\over\|g_{n}^{l}\|\|g_{c}^{ l}\|}$ (5) $$

$$ $\small\mathbf{GP}(g_{n}^{l},g_{c}^{l})=\begin{cases}\cos(g_{n}^{l},g_{c}^{l}) \cdot g_{n}^{l},&\cos(g_{n}^{l},g_{c}^{l})>0\\ 0,&\cos(g_{n}^{l},g_{c}^{l})\leq 0\end{cases}$ (6) $$

Therefore, the total projected (useful) model updates $g_{p}$ coming from $g_{n}$ could be computed as Eq. 7. We use $\mathcal{M}$ to represent all layers of the current model update. The expression $\bigcup_{l\in\mathcal{M}}$ concatenates the useful natural model update components from all layers. A hyper-parameter $\beta$ is introduced to balance the contributions of $g_{GP}$ and $g_{c}$, as outlined in Eq.8. It is important to note that this projection procedure is applied only after certified training with the full epsilon value.

$$ $g_{p}=\bigcup_{l\in\mathcal{M}}\mathbf{GP}(g_{n}^{l},g_{c}^{l})$ (7) $$

$$ $f^{(r+1)}=f^{(r)}+\beta\cdot g_{p}+(1-\beta)\cdot g_{c}$ (8) $$

Quick certified fine-tuning of single-norm pre-trained classifiers for multi-norm robustness. In practice, as the model architectures and datasets become larger, multi-norm certified training from scratch becomes more expensive. Also, there are many pre-trained models available with single norm certified training. In adversarial robustness,  Croce and Hein () shows it is possible to obtain state-of-the-art multi-norm robustness by fine-tuning a pre-trained model for a few epochs, which reduces the computational cost significantly. In this work, we propose the first fine-tuning certified multi-norm robustness scheme CURE-Finetune. Starting from a single norm pre-trained model, we perform the bound alignment technique by optimizing $\mathcal{L}_{\text{Scratch}}$ for a few epochs. Because of the $l_{q}-l_{r}$ tradeoff, certifiably finetuning a $l_{q}$ pre-trained model on $l_{r}$ perturbations reduces $l_{q}$ robustness. Thus, we want to preserve more $l_{q}$ robustness when doing certified fine-tuning, which makes bound alignment useful here. By regularizing on the correctly certified $l_{q}$ subset with $\mathcal{L}_{\text{Scratch}}$, we can prevent losing more $l_{q}$ robustness when boosting $l_{r}$ robustness, which leads to better union accuracy. We note that CURE-Finetune can be adapted to any single-norm certifiably pre-trained models. As shown in Table 1, compared with other methods, we can quickly obtain a superior multi-norm certified robustness by performing fine-tuning on pre-trained $l_{\infty}$ models for a few epochs.

###### Definition 4.1 ( l p subscript 𝑙 𝑝 l_{p} italic_l start_POSTSUBSCRIPT italic_p end_POSTSUBSCRIPT robustness A p subscript 𝐴 𝑝 A_{p} italic_A start_POSTSUBSCRIPT italic_p end_POSTSUBSCRIPT ) .

###### Definition 4.2 (Correctly Certified l q subscript 𝑙 𝑞 l_{q} italic_l start_POSTSUBSCRIPT italic_q end_POSTSUBSCRIPT Subset) .

## 5 Experiment

In this section, we present and discuss the results of union robustness, geometric robustness, and ablation studies on hyper-parameters for MNIST, CIFAR-10, and TinyImagenet experiments. Other ablation studies, visualizations, and algorithms of CURE can be found in Appendix B and D.

Experimental Setup.  For datasets, we use MNIST (LeCun et al., ) and CIFAR-10 (Krizhevsky et al., ) which both include $60$K images with $50$K and $10$K images for training and testing, as well as TinyImageNet (Le and Yang, ) which consists of 200 object classes with 500 training images, 50 validation images, and 50 test images per class. We compare the following methods: 1. $l_{\infty}$: SOTA $l_{\infty}$ certified defense SABR (Müller et al., ), 2. $l_{2}$: our proposed $l_{2}$ certified defense, 3. CURE-Joint: take a weighted sum of $l_{2},l_{\infty}$ IBP losses. 4. CURE-Max: take the worst of $l_{2},l_{\infty}$ IBP losses. 5. CURE-Random: randomly partitions the samples into two blocks, then applies the Joint loss with equal weights. 6. CURE-Scratch: training from scratch with bound alignment and gradient projection techniques. 7. CURE-Finetune: robust fine-tuning with the bound alignment technique using $l_{\infty}$ pre-trained models. We use a 7-layer convolutional architecture CNN7 similar to prior work (Müller et al., ) for models. In Table 5, we compare our proposed $l_{2}$ defense with Hu et al. (), where we show our method outperforms the SOTA $l_{2}$ deterministic certified defense on CIFAR-10. We choose similar hyperparameters and training setup as Müller et al. () for $l_{\infty}$ certified training. We select $\alpha=0.5$, $l_{2}$ subselection ratio $\lambda_{2}=1e^{-5}$, $\beta=0.8$, and $\eta=2.0$ according to our ablation study results in Section 5.2 and Appendix B. For robust fine-tuning, we finetune $20\%$ of the original epochs from scratch. More implementation details are in Appendix A.

Evaluation. We choose the common $\epsilon_{\infty},\epsilon_{2}$ values used in the literature (Müller et al., ; Hu et al., ) to construct multi-norm regions. These include $(\epsilon_{2}=0.5,\epsilon_{\infty}=0.1),(\epsilon_{2}=1.0,\epsilon_{\infty}=0
.3)$ for MNIST, $(\epsilon_{2}=0.25,\epsilon_{\infty}=\frac{2}{255}),(\epsilon_{2}=0.5,\epsilon
_{\infty}=\frac{8}{255})$ for CIFAR-10 and $(\epsilon_{2}=\frac{36}{255},\epsilon_{\infty}=\frac{1}{255})$ for TinyImageNet. We make sure the adversarial regions with sizes $\epsilon_{\infty}$ and $\epsilon_{2}$ do not include each other. We report the clean accuracy, certified accuracy against $l_{2},l_{\infty}$ perturbations, union accuracy, and individual/average certified robustness against geometric transformations. Further, we use alpha-beta crown (Zhang et al., ) for certification on $l_{2},l_{\infty}$ perturbations and FGV (Yang et al., ) for efficient certification of geometric transformations.

### 5.1 Main Results

**Table 1: Comparison of the clean accuracy, as well as individual, and union certified accuracy ($\%$) for different multi-norm certified training methods. CURE consistently improves union accuracy compared with single-norm training with significant margins on all datasets. CURE-Scratch and CURE-Finetune outperform other methods in most cases.**
| Dataset | ($\epsilon_{\infty}$, $\epsilon_{2}$) | Methods | Clean | $l_{\infty}$ | $l_{2}$ | Union |
| --- | --- | --- | --- | --- | --- | --- |
|  |  | $l_{\infty}$ | 99.2 | 97.7 | 96.9 | 96.9 |
|  |  | $l_{2}$ | 99.5 | 2.0 | 98.7 | 2.0 |
|  | (0.1, 0.5) | CURE-Joint | 99.3 | 97.5 | 97.4 | 97.1 |
|  |  | CURE-Max | 99.3 | 97.5 | 97.5 | 97.4 |
|  |  | CURE-Random | 99.2 | 96.9 | 96.7 | 96.6 |
|  |  | CURE-Scratch | 99.0 | 97.3 | 97.5 | 97.2 |
|  |  | CURE-Finetune | 99.1 | 96.9 | 97.5 | 96.9 |
| MNIST |  | $l_{\infty}$ | 99.0 | 91.0 | 64.5 | 62.9 |
|  |  | $l_{2}$ | 99.4 | 0.0 | 63.0 | 0.0 |
|  | (0.3, 1.0) | CURE-Joint | 98.7 | 89.8 | 78.3 | 75.7 |
|  |  | CURE-Max | 98.7 | 91.1 | 76.2 | 74.8 |
|  |  | CURE-Random | 98.6 | 90.2 | 78.9 | 77.0 |
|  |  | CURE-Scratch | 98.0 | 89.4 | 85.9 | 83.9 |
|  |  | CURE-Finetune | 98.6 | 90.0 | 90.0 | 85.7 |
|  |  | $l_{\infty}$ | 79.4 | 59.7 | 67.8 | 59.7 |
|  |  | $l_{2}$ | 82.3 | 5.6 | 71.2 | 5.6 |
|  | ($\frac{2}{255}$, 0.25) | CURE-Joint | 80.2 | 57.3 | 69.7 | 57.3 |
|  |  | CURE-Max | 77.7 | 59.6 | 68.2 | 59.6 |
|  |  | CURE-Random | 78.9 | 57.5 | 68.3 | 57.5 |
|  |  | CURE-Scratch | 76.9 | 60.9 | 67.8 | 60.9 |
|  |  | CURE-Finetune | 78.0 | 59.7 | 68.2 | 59.7 |
| CIFAR-10 |  | $l_{\infty}$ | 51.0 | 36.1 | 5.4 | 5.4 |
|  |  | $l_{2}$ | 73.3 | 0.0 | 56.6 | 0.0 |
|  | ($\frac{8}{255}$, 0.5) | CURE-Joint | 52.1 | 22.1 | 30.5 | 20.0 |
|  |  | CURE-Max | 51.5 | 33.9 | 19.5 | 18.8 |
|  |  | CURE-Random | 52.4 | 28.4 | 30.5 | 24.3 |
|  |  | CURE-Scratch | 49.5 | 34.2 | 28.1 | 27.3 |
|  |  | CURE-Finetune | 40.2 | 30.2 | 30.8 | 29.3 |
|  |  | $l_{\infty}$ | 28.3 | 20.1 | 24.6 | 16.1 |
|  |  | $l_{2}$ | 36.1 | 2.5 | 29.7 | 2.5 |
| TinyImagnet | ($\frac{1}{255}$, $\frac{36}{255}$) | CURE-Joint | 29.4 | 22.6 | 24.6 | 22.6 |
|  |  | CURE-Max | 28.8 | 22.1 | 24.6 | 22.1 |
|  |  | CURE-Random | 30.1 | 22.1 | 24.6 | 22.1 |
|  |  | CURE-Scratch | 28.1 | 24.1 | 25.1 | 24.1 |
|  |  | CURE-Fintune | 27.9 | 19.1 | 23.1 | 19.1 |

Union accuracy on MNIST, CIFAR-10, and TinyImagenet with CURE framework. In Table 1, we show the results of clean accuracy and certified robustness against single and multi-norm with CURE on MNIST, CIFAR-10, and TinyImagenet. We observe that CURE-Joint, CURE-Max, and CURE-Random usually result in better union robustness compared with $l_{2}$ and $l_{\infty}$ certified training. Further, CURE-Scratch and CURE-Finetune consistently improve the union accuracy compared with other multi-norm methods with significant margins in most cases ($10\%$ for MNIST ($\epsilon_{\infty}=0.3,\epsilon_{2}=1.0$), $3-10\%$ for CIFAR-10 ($\epsilon_{\infty}=\frac{8}{255},\epsilon_{2}=0.5$), and $2\%$ for TinyImagenet experiments), showing the effectiveness of bound alignment and gradient projection techniques. Also, for quick fine-tuning, we show it is possible to quickly fine-tune a $l_{\infty}$ robust model with good union robustness using bound alignment, achieving SOTA union accuracy on MNIST ($\epsilon_{\infty}=0.3,\epsilon_{2}=1.0$) and CIFAR-10 ($\epsilon_{\infty}=\frac{8}{255},\epsilon_{2}=0.5$) experiments.

Robustness against geometric transformations. Table 2 and Figure 3 compare CURE with single norm training against various geometric perturbations on MNIST and CIFAR-10 datasets. For both experiments, CURE outperforms single norm training on diverse geometric transformations ($0.6\%$ for MNIST and $6\%$ for CIFAR-10 on average), leading to better *universal certified robustness*. Also, CURE-Scratch has better geometric robustness than CURE-Max on both datasets, which reveals that bound alignment and gradient projection lead to better universal certified robustness.

**Table 2: Comparison on CURE against geometric transformations for MNIST experiment. We denote R$(\varphi)$ a rotation of $\pm\varphi$ degrees; Tu$(\Delta u)$ and Tv$(\Delta v)$ a translation of $\pm\Delta u$ pixels horizontally and $\pm\Delta v$ pixels vertically, respectively; Sc$(\lambda)$ a scaling of $\pm\lambda\%$; Sh$(\gamma)$ a shearing of $\pm\gamma\%$; C$(\alpha)$ a contrast change of $\pm\alpha\%$; and B$(\beta)$ a brightness change of $\pm\beta$. CURE improves the average robustness compared with single norm training with better geometric certified robustness. Also, CURE-Scratch achieves the best average geometric transformation robustness.**
| Configs | R(30) | Tu(2),Tv(2) | Sc(5),R(5),<br>C(5),B(0.01) | Sh(2),R(2),Sc(2),<br>C(2),B(0.001) | Avg |
| --- | --- | --- | --- | --- | --- |
| $l_{\infty}$ | 54.6 | 20.9 | 82.5 | 95.6 | 63.4 |
| $l_{2}$ | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 |
| CURE-Joint | 55.9 | 21.3 | 82.3 | 95.7 | 63.8 |
| CURE-Max | 50.1 | 20.7 | 80.2 | 94.8 | 61.5 |
| CURE-Random | 54.8 | 18.8 | 83.5 | 95.6 | 63.2 |
| CURE-Scratch | 51.0 | 24.3 | 85.5 | 95.1 | 64.0 |

Figure: Figure 2: Comparison on CURE against geometric transformations for CIFAR-10 experiment. CURE improves the universal certified robustness significantly compared with single norm training.
Refer to caption: x3.png

Figure: (a) $\lambda_{2}$: subselection ratio for $l_{2}$.
Refer to caption: x4.png

### 5.2 Ablation Study

Subselection ratio $\lambda$. For $l_{\infty}$ certified training, we use the same $\lambda_{\infty}$ as in Müller et al. (). For $l_{2}$ subselection ratio $\lambda_{2}$, in Figure 4(a), we show the $l_{2}$ certified robustness using varying $\lambda_{2}\in[1e^{-5},5e^{-5},5e^{-3},1e^{-2}]$ with $\epsilon_{2}=0.5$. Both clean and $l_{2}$ accuracy improves when we have smaller $\tau_{2}$ values. Based on the results, we choose $\tau_{2}=1e^{-5}$ for our experiments.

Bound alignment (BA) hyper-parameter $\eta$. We perform CIFAR-10 ($\epsilon_{\infty}=\frac{8}{255},\epsilon_{2}=0.5$) experiments with different $\eta$ values in $[0.5,1.0,1.5,2.0,4.0]$. In Figure 4(b), we observe that the clean accuracy generally drops as we have larger $\eta$ values, with union accuracy improving then dropping. We pick $\eta=2.0$ with the best union accuracy for the experiments.

Gradient projection (GP) hyper-parameter $\beta$. Figure 4(c) displays the sensitivity of clean and union accuracy with different choices of $\beta$ values on CIFAR-10 ($\epsilon_{\infty}=\frac{2}{255},\epsilon_{2}=0.25$) experiments. CURE-Scratch is generally insensitive to varying $\beta$ values. We choose $\beta=0.8$ for the experiments to be relatively the best.

Ablation study on BA and GP. In Table 3, we show the ablation study of BA and GP techniques on the MNIST ($\epsilon_{\infty}=0.3,\epsilon_{2}=1.0$) experiment. BA and GP improve union accuracy by $2\%$ and $7\%$ respectively, demonstrating the individual effectiveness of our proposed techniques.

**Table 3: Ablations on BA and GP.**
|  | Clean | $l_{\infty}$ | $l_{2}$ | Union |
| --- | --- | --- | --- | --- |
| CURE-Max | 98.7 | 91.1 | 76.2 | 74.8 |
| +BA | 98.6 | 91.0 | 78.2 | 76.5 |
| +BA + GP | 98.0 | 89.4 | 85.9 | 83.9 |

Visualization of bound differences. Figure 3 displays the bound differences $\{\underline{o}_{y}-\overline{o}_{i}\}_{i=0,i\neq y}^{i<k}$ of one example that is improved by CURE-Scratch (second row), compared with the CURE-Max (first row), from the CIFAR-10 ($\epsilon_{\infty}=\frac{8}{255},\epsilon_{2}=0.5$) experiment with $q=\infty,r=2$. We use the outputs from alpha-beta-crown. For $l_{2}$ perturbations (blue diagrams), we demonstrate that CURE-Scratch exhibits all positive bound differences, whereas CURE-Max shows several negative bound differences (highlighted in red), leading to a robust union prediction. Additionally, we observe that the distributions in the second row are more aligned than those in the first row. CURE-Scratch effectively aligns the bound difference distributions when the model is robust against $l_{q}$ perturbations, bringing the distributions closer together. This demonstrates the effectiveness of the bound alignment method. Additional visualizations are available in Appendix 5.

### 5.3 Discussions

Time cost of CURE. The extra training costs of GP are small, taking $6,24,82$ seconds using a single NVIDIA A40 GPU on MNIST, CIFAR-10, and TinyImageNet datasets (Table 7), respectively. Compared with the total training cost of CURE-Scratch, it only accounts for $\sim 6\%$ of the total cost. For runtime comparison of different methods, we have a complete runtime analysis (Table 6) in Appendix C for the MNIST experiment. We observe that CURE-Joint has around two times the cost of other methods. CURE-Finetune has the smallest time cost per epoch, which shows the efficiency of our proposed techniques.

Limitations. For $l_{2}$ certified training, we use a $l_{\infty}$ box instead of $l_{2}$ ball for bound propagation, which leads to more over-approximation and the potential loss of precision. Also, we notice drops in clean accuracy in both training from scratch and fine-tuning with CURE methods. In some cases, union accuracy improves slightly but clean accuracy and single $l_{p}$ robustness reduce. Both BA and GP techniques lead to a slight decrease in clean accuracy on experiments of three datasets. There is no negative societal impact of this work.

## 6 Conclusion

We propose the first framework CURE with a new $l_{2}$ deterministic certified defense and multi-norm training methods for better union robustness. Further, we devise bound alignment, gradient projection, and robust certified fine-tuning techniques, to enhance and facilitate the union-certified robustness. Extensive experiments on MNIST, CIFAR-10, and TinyImagenet show that CURE significantly improves both union accuracy and robustness against geometric transformations, paving the path to universal certified robustness.

## Appendix A More training details

We mostly follow the hyper-parameter choices from Müller et al. [] for CURE. We include weight initialization and warm-up regularization from Shi et al. []. Further, we use ADAM [Kingma, ] with an initial learning rate of $1e^{-4}$, decayed twice with a factor of 0.2. For CIFAR-10, we train 160 and 180 epochs for $(\epsilon_{\infty}=\frac{2}{255},\epsilon_{2}=0.25)$ and $(\epsilon_{\infty}=\frac{8}{255},\epsilon_{2}=0.5)$, respectively. We decay the learning rate after 120 and 140, 140 and 160 epochs, respectively. For the TinyImagenet experiment, we use the same setting as $(\epsilon_{\infty}=\frac{8}{255},\epsilon_{2}=0.5)$. For the MNIST dataset, we train 70 epochs, decaying the learning rate after 50 and 60 epochs. For batch size, we set 128 for CIFAR-10 and TinyImagenet and 256 for MNIST. For all experiments, we first perform one epoch of standard training. Also, we anneal $\epsilon_{\infty},\epsilon_{2}$ from 0 to their final values with 80 epochs for CIFAR-10 and TinyImagenet and 20 epochs for MNIST. We only apply GP after training with the final epsilon values. For certification, we verify $1000$ examples on MNIST and CIFAR-10, as well as $199$ examples on TinyImagenet.

## Appendix B Other ablation studies

Hyper-parameter $\alpha$ for Joint certified training. As shown in Table 4, we test the changing of $l_{\infty}$, $l_{2}$, and union accuracy with different $\alpha$ values in $[0,0.25,0.5,0.75,1.0]$ on MNIST $(\epsilon_{\infty}=0.1,\epsilon_{2}=0.5)$ experiments. We observe that $\alpha=0.5$ has the best union accuracy and is generally a good choice for our experiments by balancing the two losses.

**Table 4: Ablation study on Joint training hyper-parameter $\alpha$.**
| $\alpha$ | 0.0 | 0.25 | 0.5 | 0.75 | 1.0 |
| --- | --- | --- | --- | --- | --- |
| Clean | 99.2 | 99.2 | 99.3 | 99.2 | 99.5 |
| $l_{\infty}$ | 97.7 | 97.7 | 97.5 | 97.2 | 2.0 |
| $l_{2}$ | 96.9 | 95.6 | 97.4 | 95.9 | 98.7 |
| Union | 96.9 | 95.6 | 97.1 | 95.8 | 2.0 |

Comparison of $l_{2}$ certified robustness on $l_{2}$ deterministic certified training methods. In Table 5, we compare our proposed $l_{2}$ certified defense with SOTA $l_{2}$ certified defense Hu et al. [] on CIFAR-10 with $\epsilon_{2}=0.25$ and $0.5$. The results show that our proposed $l_{2}$ deterministic certified training method improves over $l_{2}$ robustness by $2\sim 4\%$ compared with the SOTA method.

**Table 5: Comparison of $l_{2}$ certified accuracy: our proposed $l_{2}$ certified training consistently outperforms Hu et al. [] by $2\sim 4\%$.**
| $\epsilon_{2}$ | 0.25 | 0.5 |
| --- | --- | --- |
| Hu et al. [] | 69.5 | 52.2 |
| Ours | 71.2 | 56.6 |

More visualizations on bound differences. We plot the bound difference examples from alpha-beta-crown on MNIST, CIFAR-10, and TinyImagenet datasets, where the negative bound differences are colored in red. As shown in Figure 5, 6, 7, 8, 9, we compare CURE-Scratch (second row) with CURE-Max (first row), with bound differences against $l_{\infty}$ and $l_{2}$ perturbations colored in blue and green, respectively. CURE-Scratch produces all positive bound differences, leading to unionly robust predictions; CURE-Max is not unionly robust due to some negative bound differences. Also, we observe that CURE-Scratch successfully brings $l_{q},l_{r}$ bound difference distributions close to each other compared with CURE-Max in many cases, which confirms the effectiveness of our bound alignment technique.

Figure: Figure 5: Bound difference visualizations on MNIST ($\epsilon_{\infty}=0.3,\epsilon_{2}=1.0$) experiments.
Refer to caption: x7.png

Figure: Figure 6: Bound difference visualizations on CIFAR-10 ($\epsilon_{\infty}=\frac{2}{255},\epsilon_{2}=0.25$) experiments.
Refer to caption: x9.png

Figure: Figure 7: Bound difference visualizations on CIFAR-10 ($\epsilon_{\infty}=\frac{8}{255},\epsilon_{2}=0.5$) experiments.
Refer to caption: x11.png

Figure: Figure 8: Bound difference visualization on TinyImagenet ($\epsilon_{\infty}=\frac{1}{255},\epsilon_{2}=\frac{36}{255}$) experiments.
Refer to caption: x13.png

Figure: Figure 9: Bound difference visualization on TinyImagenet ($\epsilon_{\infty}=\frac{1}{255},\epsilon_{2}=\frac{36}{255}$) experiments.
Refer to caption: x14.png

## Appendix C Runtime Analysis

This section provides the runtime per training epoch for all methods on MNIST $(\epsilon_{\infty}=0.1,\epsilon_{2}=0.75)$ experiments and runtime per training epoch of CURE-Scratch with ablation studies on GP for MNIST, CIFAR10, and TinyImagenet experiments. We evaluate all the methods on a single A40 Nvidia GPU with 40GB memory and the runtime is reported in seconds (s).

Runtime for different methods on MNIST experiments. In Table 6, we show the time in seconds (s) per training epoch for single norm training ($l_{\infty}$ and $l_{2}$), CURE-Joint, CURE-Max, CURE-Random, CURE-Scratch, and CURE-Finetune methods. CURE-Finetune has the smallest training cost compared with other methods and CURE-Joint has the highest time cost (around two times of other methods) per epoch. The results indicate the efficiency of training with CURE-Scratch/Finetune.

**Table 6: Runtime for all methods on MNIST $(\epsilon_{\infty}=0.1,\epsilon_{2}=0.5)$ experiment per epoch in seconds.**
| Methods | Runtime (s) |
| --- | --- |
| $l_{\infty}$ | 182 |
| $l_{2}$ | 165 |
| CURE-Joint | 320 |
| CURE-Max | 155 |
| CURE-Random | 190 |
| CURE-Finetune | 148 |
| CURE-Scratch | 154 |

Runtime for CURE-Scratch on MNIST, CIFAR10, and TinyImagenet datasets. In Table 7, we show the runtime per training epoch using CURE-Scratch on MNIST, CIFAR10, and TinyImagenet datasets with and without GP operations. We see that the GP operation’s cost is small compared with the whole training procedure, accounting for around $6\%$ of the whole training time.

**Table 7: Runtime for CURE-Scratch on MNIST, CIFAR10, and TinyImagenet datasets.**
|  | MNIST | CIFAR-10 | TinyImagenet |
| --- | --- | --- | --- |
| w/o GP | 148 | 390 | 952 |
| with GP | 154 | 414 | 1036 |

## Appendix D Algorithms

In this section, we present the algorithms of CURE framework. Algorithm 1 illustrates how to get propagation region for both $l_{2}$ and $l_{\infty}$ perturbations. Algorithm 2, 3,  4, 5 refer to algorithms of CURE-Joint, CURE-Max, CURE-Random, and CURE-Scratch/Finetune, respectively. Algorithm 6 is the procedure of performing GP after one epoch of natural and certified training (could be any of Algorithm 2, 3,  4, 5).

Figure: Algorithm 1 get_propagation_region for $l_{\infty}$ and $l_{2}$ perturbations

Figure: Algorithm 2 CURE-Joint Training Epoch

Figure: Algorithm 3 CURE-Max Training Epoch

Figure: Algorithm 4 CURE-Random Training Epoch

Figure: Algorithm 5 CURE-Scratch/Finetune Training Epoch

Figure: Algorithm 6 GP: Connect CT with NT

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: N/A
soundness: 2
strengths: 1.This paper showed a new unified adversarial training method for certified robustness.

2.The experimental results demonstrates the effiectiveness of the proposed method.
summary: Current certified training methods only make models robust to specific perturbation types, but fail to provide robustness across multiple perturbation types simultaneously. The authors propose CURE, a novel multi-norm certified training framework that enhances robustness across different perturbations by combining deterministic defenses with multi-norm certified training techniques. CURE achieves up to 23.9% improvement in union robustness and better generalization on unseen transformations, marking a step toward universal certified robustness.
weaknesses: 1.The new loss proposed in this paper appears to be merely an adaptation of the unified loss used in general adversarial training, which significantly detracts from the originality and contribution of this work.

2.The unified loss considers only the l2 and l infty cases, which, from the reviewer's perspective, falls short of guaranteeing universal certified robustness. The authors should include results across a wider range of lp norms to substantiate this claim.

3.The authors do not provide a theoretical analysis demonstrating how the proposed loss function contributes to improved universal certified robustness.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: See above.
soundness: 2
strengths: The proposed method shows that using gradient propagation and bound alignment can result in good performance wins on multi-norm certified robustness as well as on geometric perturbations.

Plenty of evaluations of multi norm certified accuracy, on L-inf, L-2 and geometric transformations -- on a few vision datasets with documented settings.

All hyper-parameters are given in the appendix and pseudo-code, which should make the method more reproducible.
summary: The paper introduces the CURE framework -- a selection of related methods for training certifiably robust models. The introduced methods are derived from SABR (Muller et al.).

The paper proposes gradient projection and bound alignment techniques for improving certified robustness against multi-norm norm bounded perturbations as well as geometric perturbations -- while conducting evaluations on vision tasks (CIFAR-10, MNIST and TinyImagenet) with small networks.
weaknesses: The main issue is the scope and clarity of contributions of the paper.

One of the main contributions is claimed to be a method for L2 certified training. The paper is replacing a (hyper-)box with a (hyper-)sphere in the SABR method, without any analysis or theoretical justification. This is a baseline, not a new methods.

The three variants of CURE: Joint, Max, Random are also claimed contributions. These methods just naturally arise from having different methods for dealing with L2 and L-inf norm bounded perturbations. So, they also naturally seem to be baselines.

CURE-Finetune applies CURE-Scratch on a different base model (i.e. a pre-trained one) with some other small changes. It does not seem to be a different method, so there is little need for a new name.

Overall, it is a bit confusing that "CURE" is a "framework". It seems that the paper would be much clearer if it would separate out the actual contributions and focus on them: bound alignment, gradient projection and changes needed for fine-tuning -- and disentangle/isolate and ablate all those components individually (table 3 seems to do this, at a very small scale).


Other issues include:

- Very confusing notation overall. For example, what is "A_u \rightarrow A_q" in line 283. Also, equation 2 looks very clumsy (could the indices be subscripts/superscripts/etc.?). Many equations do not seem to be needed at all; equation 7 takes a union of parameters and 8 shows a linear combination; etc.

- Irrelevant definitions (4.1 and 4.2) and an extreme amount of mathematical notation for concepts that could really be explained much more clearly with just words (all of section 4 could be written in half the space). Note that there is no theoretical justification given, not proofs, bounds, analysis, etc.

- Confusing terminology: "certified update", line 329; "certifiably fine-tuning", line 353; etc.

The paper definitely has some good parts, but in the current state, without a major re-write, I cannot recommend acceptance.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 3
questions: Ref Weaknesses.

The current manuscript does not meet ICLR's bar for several fundamental reasons. The core contribution—balancing losses across different norms in certified training—appears incremental without substantial theoretical innovation. Critical questions remain unaddressed: the paper lacks theoretical justification for why this multi-norm framework is specifically effective in certified training, as opposed to general adversarial training; there are so many "logical" problems in Sec. 4.2.  Moreover, there is insufficient analysis demonstrating how the proposed method theoretically guarantees improvements in certified robustness. The absence of formal analysis of certified robustness significantly weakens the paper's contribution to the field.
soundness: 2
strengths: This work is well-written and easy to understand. The certified robustness issue is significant, but it would benefit substantially from more rigorous formal analyses of certified robustness.
summary: This paper introduces CURE, a certified training framework that advances the state-of-the-art in multi-norm robustness certification. The framework's key innovation is twofold: it presents the deterministic l2-norm certified training defense and develops comprehensive multi-norm certified training methodologies.
weaknesses: This work is not self-consistant, e.g., it lacks technical details regarding the implementation of the IBP loss computation, particularly in deriving the lower and upper bounds. 

The work appears to be a straightforward adaptation of multi-norm adversarial training ideas to certified training, without providing deeper (theoretical) insights. A rigorous analysis explaining why this framework is specifically effective for certified training would significantly strengthen the contribution. The current version seems not interesting. Could authors provide a theoretical justification for why this approach can improve certified robustness?

The paper notably lacks computational complexity analysis. Given the typically high computational demands of certified training methods, this omission is particularly significant.

The experiments could be more comprehensive, particularly in comparison with recent advances in adversarial training with DDPM-generated data. ref https://github.com/wzekai99/DM-Improves-AT.  I guess DDPM-data can also help to improve certified robustness.

Rough definition: Could authors provide formal definitions in 4.1 and 4.2? 

The logical relationship in lines 282-284 requires clarification regarding necessary or sufficient conditions. E.g., in the worst case, A_u = A_q = 0, does it mean optimizing A_u->A_q will reach the worst?

In my opinion, the most ideal case is A_u = A_q = 100\%. Why optimizing A_u->A_q is better than optimizing A_u -> 100\%?

Given a specific training set, I guess the ideal case may not satisfy A_u = A_q. Could authors prove that the ideal case must satisfy A_u = A_q given any training set drawn from an unknown data distribution?

Even though a model is optimized to A_u = A_q, how to prove it is the best over the current training set?

Line 297-298: Since A_q serves as the upper bound of A_u, similarly, $\gamma$ can be regarded as... Why $\gamma$ can be??? Please justify "more likely". I cannot find the logic/causality here.

---

confidence: 5
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Is it possible to include geometric perturbations in the training framework?
2. The results of CURE on MNIST + Translation transformation are unexpectedly low. Do you have any insights on why this happens? Do you also have results for CIFAR-10? 
3. It is not very clear when GP is applied during training. Appendix A states *We only apply GP after training with the final epsilon values*. Does this mean GP is applied after the eps-annealing phase?
4. Would it be possible to obtain a similar effect to Bound Alignment if we just give samples from $\gamma$ a higher weight for the $L_r$ loss?
5. The learning rate is reported as 1e-4, but SABR uses 5e-4. Is this a writing mistake or a deliberate change?
soundness: 3
strengths: The paper addresses a challenge that was (to the best of my knowledge) not addressed before. The proposed multi-norm certified training methods improve performance over previous SOTA methods that don’t use multi-norm certified training. Training certifiably robust networks jointly for multiple perturbation types seems like a promising approach toward universally robust models.

The paper is well-written and easy to follow. There are plenty of experimental results, and the insights gained from this work are valuable.
summary: The paper explores the connection between certified training with multiple perturbation regions. The authors propose a framework for joint training with multiple variants and incremental improvements. The proposed method improves the union certified accuracy and also generalizes to certified robustness with respect to different geometric transformations that were not specifically used during training.
weaknesses: * Even if $L_2$ and $L_\infty$ perturbations are generally studied in this field, given the claim of universality, it would be interesting to have some discussion about other perturbation types (certification and/or training attempts).
* The $L_2$ certified training method proposed suffers from a significant drop in natural accuracy that can only be mitigated by using a very small value for $\lambda_2$, which becomes very close to just using Adversarial Training instead. I would like to see some results obtained by using AT (equivalent to $\lambda_2 = 0$). I suspect the main cause for this to be the complex interaction between the propagated $L_\infty$ box as a proxy for $L_2$ robustness. Consider this simple case: we have a data point $x$ which is a $n^2$ dimensional point ($n=28$ for MNIST, $n=32 \sqrt 3$ for CIFAR). We want to train for robustness in a $L_2$ ball with radius \epsilon, using subselection rate $\lambda$. The algorithm searches for an adversarial example ($x+\delta$) inside the $L_2$ ball with radius $\epsilon(1-\lambda) = \epsilon - \tau$ and then propagates the $L_\infty$ ball with radius $\tau$ centered in $x+\delta$. Consider the case when $\delta = 1 \cdot (\epsilon-\tau)/n$ (all values of $\delta$ are the same and $||\delta|| =\epsilon-\tau$ ). Let $\beta = 1 \cdot \tau$. Then the point $\tilde x =  x + \delta + \beta$ is the most distant point from $x$ that is contained within the $L_\infty$ ball that is being propagated. The $L_2$ distance between $\tilde x$ and $x$ is $||\delta + \beta|| = \epsilon - \tau + n \tau = \epsilon + (n-1) \tau = \epsilon (1 + (n-1) \lambda)$. For a seemingly normal value of $\lambda = 0.1$ (the value used by SABR for CIFAR-10 $\epsilon=2/255$) this distance can be $4$ to $6$ times larger than $\epsilon$, which will introduce a lot of unnecessary regularization, explaining why you had to resort to much smaller values for $\lambda_2$. It would be interesting to analyze some other options/strategies for constructing the $L_\infty$ box in this case as it is very likely that this would further improve the results.
* The Bound Alignment procedure seems complex and not perfectly motivated. It is not clear why we want to align the bounds for the two perturbations. It is also not very clear if the alignment of the bounds is computed based on the small Box obtained after the adversarial attack during training. Definition 4.2 seems to imply that you use the bounds for the whole eps-Ball, but Algorithm 5 shows that loss_KL is computed for the bounds of the small box.

**Minor points**
* For reproducibility it would be nice to have a paragraph or table with all hyperparameters needed for experiments. For example, there are no given values for the $\lambda_\infty$ subselection rate. Instead, they are just cited to be the same as SABR. 
* It would be nice to have a short description of how the certification methods used for evaluation work in different scenarios as readers might not be familiar with all of them.
* Figures about bound alignment (3,5,6,7,8,9) are not very expressive and it is not easy to draw conclusions based on them. Also, I don’t understand what should be the difference between Fig 8 and 9. I think they show different test samples, but this should be more clearly stated in the text.