Towards Generalized Certified Robustness with Multi-Norm Training
Authors: Enyi Jiang
David Shu Cheung
Gagandeep Singh
Venue: Accepted by TMLR ()

Abstract: Existing certified training methods can only train models to be robust against a certain perturbation type (e.g. $l_\infty$ or $l_2$). However, an $l_\infty$ certifiably robust model may not be certifiably robust against $l_2$ perturbation (and vice versa) and also has low robustness against other perturbations (e.g. geometric and patch transformation). By constructing a theoretical framework to analyze and mitigate the tradeoff, we propose the first multi-norm certified training framework \textbf{CURE}, consisting of several multi-norm certified training methods, to attain better \emph{union robustness} when training from scratch or fine-tuning a pre-trained certified model. Inspired by our theoretical findings, we devise bound alignment and connect natural training with certified training for better union robustness. Compared with SOTA-certified training, \textbf{CURE} improves union robustness to $32.0\%$ on MNIST, $25.8\%$ on CIFAR-10, and $10.6\%$ on TinyImagenet across different epsilon values. It leads to better generalization on a diverse set of challenging unseen geometric and patch perturbations to $6.8\%$ and $16.0\%$ on CIFAR-10. Overall, our contributions pave a path towards \textit{generalized certified robustness}.

Published in Transactions on Machine Learning Research (March/200)
Towards Generalized Certified Robustness with Multi-Norm Training
Enyi Jiang, David S. Cheung, Gagandeep Singh
University of Illinois at Jrbana-Champaipe daniiii,dddiidd,,, aigaaiddde..ggaaaeiiiiiiiiii..i.
Reviewed on OpenRevicw:
Abstract
Existing certified training methods can only train models to be robust against certain perturbation type (e.g. lo or 12). However, an lx certifiably robust model may not be certifiably robust against l2 perturbation (and vice versa) and also has low robustness against other perturbations (e.g. goometric and patch transformation).. By constructing a thcoretical framework to analyze and mitigate the (radeofT, we propose the first multi-norm certified training framework CURE, consisting of several multi-norm certified training methods, to attain better union robustness when training from scratch or fine-tuning a pre-trained certified model. Inspired by our theoretical findings, we devise bound alignment and connect natural training with certified training for better union robustness. Compared with SOTA-certifedd training, CURE improves union robustness to 32.0% on MNIST, 25.8% on CIFAR-10, and 10.6% on Tinylmagenet across different epsilon values. leads better generalization on a diverse set of challenging unseen geometric and patch perturbations to 6.8% and 16.0% CIFAR-10. Overall, our contributions pave path towards generalized certified robustness.
1
Introduction
While deep neural networks (DNNs) are widely deployed in various vision applications, they remain vulnerable to adversarial attacks [Goodfellow et al. 2014
Kurakin et al. 2018). Many empirical defenses (Madry et al.) 2017 Zhang et al.) 2019a Wang et al. 2023) against adversarial attacks have been proposed, however, they do not provide provable guarantces and remain vulnerable to stronger attacks. Hence, important to train DNNs be formally robust against adversarial perturbations. Various deterministic certified training methods
for specific perturbations (Mirman al. 2018 Gowal al. 2018 Zhang al. 2019b Balunović & Vechev
2020
Shi ct al. 2021 Müller al.) 2022; Yang et al. 2022 Hu ct al. 2023 2024 Mao et al.
2024b) (c.g.,
1o0, 12, and geometric transformations) have been proposed. However, those defenses mostly limited to
specific perturbation and cannot easily be generalized to other perturbation types (Yang et al. 2022 Chiang
lt al. 2020). Multi-norm attacks that examine models" robustness against lp norms simultaneously have
arisen in real-world settings such as cybersccurity Zhang et al.) (2024), video recognition Lo & Patel (2021)
and social media filtering Dai et al. (2024): is essential for building models that are robust across diverse 1 norms, to generalize better against other non-lp perturbations (Jiang Singh 2024
In this work, propose the first multi-norm Certified training for Union RobustnEss (CURE) framework, consisting of several multi-norm certified training methods. Inspired by SABR (Müller et al. 2022 use deterministic l2 defense that first finds the l2 adversarial examples in a slightly truncated 1o region and then propagates the smaller Too box using the IBP loss (Gowal el al. 2018). In Figure la we show that an Lo certified robust model may lack l2 certified robustness and vice versa: loo model only has 6.0% la robustness and ln model has 0% too robustness, which reveals the robustness tradcoff among different I, perturbations. Therefore, we first construct a thcoretical framework for binary classification analyze the tradeoff, from which we propose several methods based on multi-norm empirical defenses with different. loss

---

Published in Transactions on Machine Learning Research MMrchh2022
formulations (Tramer & Bonch 2019
Madaan al 2021: Croce & Hein 2022 Jiang & Singh 2024 Our
proposed methods successfully improve union and generalized certified robustness, shown in Table Figure and Table 3a
However, the aforementioned methods achieve sub-optimal union robustness since they do not exploit the in-depth connections between certified training for different Ip perturbations as well as natural training. Thus, we propose the following improvements. (1) Bound alignment: Inspired by the upper bound of theoretical analysis (Theorem 4.2 and previous work adversarial robustness ІJiang & Singh 2024). propose bound alignment method to mitigate the l4 tradeoff better. We regularize the distributions of output bound differences, computed with IBP, for 1g. 4 perturbations on the correctly certified subset as shown in Figure Ib In this way, we encourage the model to emphasize optimizing the samples that can potentially become certifiably robust against multi-norm perturbations. To achieve this, we use a KL loss to encourage the distributions of the 4, output bound differences on subset y to be close to each other for better union accuracy. (2) Gradient Projection: We find that there exist some useful components in natural training that can be extracted and leveraged to improve certified robustness (Jiang & Singh 2024). To achieve this, find and incorporate the layer-wise useful natural training components by comparing the similarity of the certified and natural training model updates. (3) Quick finc-tuning: Fine-tuning an 1p-robust model using bound aligmment quickly achieves superior multi-norm certified robustness. By addressing the 44- 4 tradeoff, bound alignment preserves more l robustness when fine-tuning with 4 perturbations, focusing on correctly certified samples. This technique enables efficient multi-norm robustness using pre-trained models with single lp robustness. Figure la shows that both scratch training (CURE-Scratch) and finetuning (CURE-Finetune) significantly enhance union robustness perhaps surprising side effect, improving union-certified robustness leads to stronger gencralized certified robustness by generalizing better to other geometric and patch transformations (Section 5.1 confirming that ip robustness is the bedrock for non-lp robustness (that non-f, perturbations may be modeled through lp- ep-bounded formulations) (Mangal et al. 2023
single-norm training. (4) Generalized robustness: As
Linf (0.5) LURE-Scratch
CURE Finelune
00.0
dy
Align via KL
Acc
{
Better Union Accuracy
Linf
L2
Union
Do not Contribute Union Accuracy
(a) 100 -1 tradeoff on CIFAR10 with 6oo 255 62 0.5. The X-axis represents I l2, and union robustness; different colors refer to different training methods.
(b) Bound alignment during training.
Figure 1: (a) loo - la tradeoff: Loo certified robust model may lack la certified robustness and vice CURE-Scratch (yellow) and CURE-Fineture (green) improve union robustness significantly. (b) We align the output bound differences for 4 perturbations on the correctly certified ly subset y to mitigate
l - l, tradeoff for better union robustness.
Main Contributions:
We design a thcoretical framework analyze the multi-norm cortified robustness tradcoff. Based on this, we propose three training methods, CURE-Joint, CURE-Max and with different loss formulations for better union and generalized certified robustness.
2

---

Published in Transactions on Machine Learning Research (March/20P)
Inspired by our theoretical findings, we introduce techniques including bound alignment, connecting natural training with certified training, and certified fine-tuning for better union robustness. CURF-Scratch and CURE-Finetune further facilitate our multi-norm certified training procedure and advance multi-norm robustness.
Compared with a SOTA certified training method (Müller et al. 2022), CURE improves union robustness up to 32.0% on MNIST, 25.8% on CIFAR-10, and 10.6% on Tinylmagenet. It improves robustness against unseen geometric and patch perturbations up to 0.6%, 8.5% on MNIST and 6.8%, 16% CIFAR-10.
2
Background
In this section, we provide the necessary background of neural network verification and certified training. Given samples {(ri, = from data distribution D, the input comprises images Rd with labels y E RR. The goal is to train a classifier f, parameterized by 0, to minimize loss function C R I + R over D.
2.1 Neural network verification
Neural network verification formally proves a network's robustness, with the provably robust samples defining the certified accuracy. Interval Bound Propagation (IBP) (Gowal al. 2018 Mirman al. 2018 simple yet effective method for verification. Tt over-approximates the input region (p),,,p))27 {2, 00), propagates 2 .... L1 (with linear layers Li and ReLU activations o), and verifies whether the reachable outputs classify correctly. Robustness is certified if the lower bound of the correct class exceeds the upper bounds of all others (Vi F 0, 2g < 0) (for more details, see Gowal
it layer by layer through the network f = Lj o 2
et al. (0188)
2.2 Training for robustness
A classifier is adversarially robust on an Ip-norm ball Bp(x, cp) = fx' E Rd 1| =zlpp S Scp) if it correctly classifies all points within this region, i.e., arg max f'(x') = y for all x' E Bp(x, Training for robustness is framed as a min-max optimization problem, defined for an Ip attack as:
min (Z
max f(f(x'),)) ('E
(1)
The inner maximization problem is often approximated through adversarial training (Madry et al, 2017 or certified training (Gowal et al., 2018 Müller et al., (022). However, such methods are typically tailored to specific p values, leaving networks vulnerable to other perturbations. To address this, prior work has only trained networks to be adversarially robust against multiple perturbations (4,, (2, Our focus is on training networks to be cerlifiably robust to multiple Ip perturbations.
2.3 Certified training
There two main categories of methods to train certifiably robust models: unsound and sound methods. Sound methods optimize rigorously defined upper bound of the inner maximization problem, ensuring provable robustness guarantees. In contrast, unsound methods give up this guarantee to have more precise approximation. IBP, sound method, optimizes the following loss function based on logit differences:
CIBP(I, U, coo) = In(1 + Σ the -
(2)
k
Also, state-of-the-art certified training methods SABR Muller et al. 2022), TAPs Mao al. 2024b). and CC/EXP/MTL-IB (Palma et al., (024) relax the robustness guarantee within the specification loss, but in practice, result in better standard and certified accuracy. Given small box size Too, SABR finds
3

---

Published in Transactions on Machine Learning Research (March/200)
adversarial example x' E (2, Too) and propagates small box region (x Teo) across all layers using TBP loss, expressed as:
L (2, U, coo, Too)
max x' (E, 7ox)
LIBP (z', , Too)
(3)
2.4 Evaluation metrics
Union certified accuracy (UCA), We focus on the union threat model A = (1 e2) 6so) which requires the DNN to be certifiably robust within the I, 12 and lo adversarial regions simultancously. Union accuracy is then defined as the robustness against Ag) for each æ; sampled from D. In this paper, similar to the prior works (Croce & Hein 2022), we use union accuracy as the main metric to evaluate the multi-norm certified robustness.
UCA ERDDD [1 A with bounds Oz, 2, Vi yi By: <0]],
where yi is the true label for sample Tú, and 1(-} is the indicator function.
Generalized certified robustness (GCR). 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. 2019 Yang et al. 2022), as well as patch attacks (Chiang
et al. 2020 Having perturbation sets (x) representing each translormation atlack lype j, define:
[ 1'1 (x,) with bounds 0,,0, Vi + ys, 0, o,: < 00]
GCR En,ND
where J is the total number of considered perturbation types.
3 Related Work
Neural network verification. We rely on deterministic verification techniques to evaluate robustness under multiple norms. Although exact verification is NP-complete and infeasible for large models (Katz et al. 2017), scalable relaxations such abstract interpretation (Singh et al. 2019) and convex optimization approaches (Wang al. 2021) make it possible to obtain sound, though sometimes conservative, certificates. These methods are widely used in certified training because they strike balance between tractability and rigor, enabling provable guarantees at scale. Our analysis of multi-norm certified training builds on this foundation, leveraging deterministic verification to provide stronger and more general robustness guarantecs.
Certified training. For los certified training, a widely-used method IBP Miiran et al. 2018 Gowal et al. 2018) minimizes sound over-approximation of the worst-case loss, calculated using the Box relaxation method. Wong et al. (2018) applics DeepZ (Singh et al. 2018) relaxations, estimating using Cauchy random projections. CROWN- N-IP iZhang et al.] 2019b) integrates efficient Box propagation with precise linear relaxation-based bounds during the backward pass to estimate the worst-case loss. Balunović & Vechev (2020) 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. Shh et al. (2021) proposes new weight initialization method for IBP, adds Batch Normalization (BN) each layer and designs regularization with a short warmup schedule. Besides this, SABR (Müller al.) 2022). TAPS (Mao al. 2024b), and others De Palma al. unsound improvements over IBP by connecting IBP to adversarial attacks and adversarial training. For le deterministic certified training, recent 2021 Xu et al. 2022 Hu et al. 2023: 2024) are based on Lipschitz-based cortification methods. They design specialized architectures under a particular lp norm, which do not naturally exlend to robustness under the diverse settings considered our work. To the best of our knowledge, CURE is the first deterministic framework for multi-norm certified robustness, compatible with diverse model architectures. In comparison to previous works, CURE is more general deterministic framework for multi-norm certified robustness.
(2022) Mao et al. 2023): : Balauca et al. (2024)
b Mao et al. (0224]]
works (Liino et al.
4

---

Published in Transactions on Machine Learning Research (March/2022
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.) 2017 Madry et al. 2017). Numerous works focus on improving robustness (Zhang
ct al. 2019a Carmon et al, 2019 Raghunathan et al., 2020 Wang et al.] 2020 Wu et al.) 2020 Gowal et al.
2020
Zhang et al. 2021: Debenedetti & Troncoso EPFL, 2022 Peng et al. 2023 Wang et al. 2023) against.
a single perturbation type while remaining vulnerable to other types. Tramer & Bonch (019); Kang et al.
(2099)
observe that robustness against lp attacks does not necessarily transfer other L attacks (g + p).
Previous studies (Tramer & Boneh 2019 Maini et al.) 2020: Madaan et al.) 2021 Croce & Hein 2022 Jiang &
Singh 2024) modified Adversarial Training (AT) to enhance robustness against multiple 1p attacks, employing
average-case (Tramer & Boneh 2019) , worst-case (Tramer & Boneh 2019 Maini et al.) [020] Jiang & SSing,
2024), and randon-sampled Madaan et al. 2021 Croce & Hein 2022 defenses. There are also works (Nandy
et al. 2020 Liu et al. 2020 Xu et al.) 2021 Xiao et al., 2022 Maini et al. 2022) that use preprocessing, ensemble methods, mixture experts, and stability analysis to solve this problem. For multi-norm certified robustness, Nandi et al. (2023) 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 generalized certified robustness.
4 CURE: multi-norm Certified training for Union RobustnEss
This section presents our multi-norm certified training (CT) framework CURE. We introduce our framework for binary classification to analyze the tradc-off between certified 1p and lg perturbations, inspired by previous work on the accuracy-robusttess trade-off (Zhang el al. 2019a). However, we nole our algorithus presented in this work are all multi-class, and the binary classification framework can be easily extended to the multi-class case Zhang et al. (2019a). Based on the theoretical analysis (Eq. 4 we propose three methods for multi-norm CT against 12, Loo perturbations using different loss formulations, serving as the base instantiations of our framework. We design new techniques to improve union-certified accuracy inspired by our theoretical findings.
Notations. We denote the sample instance as x E X, with the label y E {-1,+1} (binary classification), where C Rd is the instance space. D (1,, 1- is the dataset, where X = fz1,..., [n C X is the set of instances and Y (yI..... yn C [-1, is the set of corresponding labels. Let f X' + RR map instances to output values E (f1,,+1,, which can be paramcterized (e.g., by neural networks). We use (event), the 0-1 loss, as an indicator function that is 1 if an event happens and 0 otherwise. For any function (u), we use & to denote the inverse function. o(.) is used to denote the surrogate for the 0-1 loss function.
Robust, alignment and union error. To characterize the robustness of a score function f: - IR similar to SShhnidt et al.] (2018); Cullina et al. (2018); Bubeck et al. (2019), we define robust error under Eg) s.t. f(zz )y S 0}. We define R,(f) similarly to (f) for er perturbation, and without loss of generality, assume R+) 2 Rf),). Then, we introduce alignment error as the risk calculated by x E X that are robust against 4, attack but not robust against. lg attack: (flign(()= = Fle ( E (x, 6),, E (2, eg), s.t. f(x4)y > O and f(x))) S 0}. The union error is the risk calculated by x E X that are either not robust against ly or 4 attack. We have the following relationship of (f): Runion (f) = RT( + Raliga
the threat model of Eg perturbation: (f) == E L(x.))-D
(4)
Trade-off between lg.4, perturbations. Our study is motivated by the trade-off between by and 4, robust errors (Figure La], well as the accuracy-robustnes tradeoff analysis (Zhang et al. 2019ah. To illustrate, we provide two extreme cases in Figure 2. We define S, = {x/Err, E (z,x, s.t. f(z()y S 0, (I, E D} (define S, similarly). As shown in Table 3 we have (a) the lowest union accuracy of 0: when all instances in X can be successfully attacked by l or 4, norms yet no single instance can be attacked in both l and 4, we have a union error of 1; (b) the highest union accuracy of 1 R,: when the instances that are not robust against I, attack includes all instances that are not robust against lg attack, we have a union error R, A larger union error indicates a bigger lgp ly trade-off. Ranion is lower bounded by R,,-
5

---

Published in Transactions on Machine Learning Research (March/200)
S
S
S
Figure Comparisons of union errors of two extreme cases. Note that R, I Rumion S 1. larger union error has more severe 4 lp trade-off.
(a) Sg and Sr are disjoint and cover
(b) S. includes Sq
5, n. UAS, US
S.S.
Ralinn
R,
Figure 2: 11, trade-off visualization. Blue and purple points belong to S S X and S, X.
Ronson
R. (optimal)
4.1 Certified training for multiple norms
Eq. reveals that we need to minimize Ralign by not only training with one kind of adversarial examples xi since it will lead to a large Ralign with more instances not robust against 4 attack. To effectively combine the optimization of lg and 1, (g = 2. = oo) certified training, inspired by the work (Tramer & Bonch 2019 Croce & Hein 2022) on adversarial training for multiple norms, we propose the following
Madaan et al. 2021
methods:
1. CURE-Joint: optimizes Ltx and Li, together: it takes the sum of two worst-case IBP losses with tx and 12 examples using convex combination of weights with hyperparameter E [0,
Joiit = (1 -x) (2) Lr (1r, Us coo, Too) + a Lig (2, 62,
2. CURE-Max: compares Lı, and Li selecting the higher IBP loss as the worse-case outcome. This approach acts as a worst-case defense, accounting for adversarial examples with the highest IBP loss across multiple perturbation types. The max loss LMax is defined as:
Max
max max (2,00) P'E
CIBP BI Ep.
3. CURE-Random: randomly partitions batch of data (x.y) D into equal sized blocks (x1, y1) and (2). For (i), calculate the Lo worst-casc IBP loss Lt., with lx perturbations. For the other half (2), similarly, we get the la worst-case IBP loss by applying 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 $
Randomm (X1, (X1, coo, Too) + Li, (x2, Y2, 62, T2), where x = XI Ux2, = y1 Uy2
4.2 Unified and effective multi-norm certified training
The methods proposed above still 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 techniques to enhance the union robustness of CURE: (1) We derive an upper bound on the terms, which informs us to propose a bound alignment technique to mitigate the trade-off better, improving multi-norm robustness. (2) We analyze and connect certified and natural training to attain better union accuracy. (3) the first certified fine-tuning method to quickly improve union accuracy with pre-trained single-norm models (Table 1.
Bound aligument (BA). First, we aim to design tight upper bounds for different risk terms, leveraging the theory of classification-calbbaad more efficiently. First, maassificationccaibbuuu designed to approximate the 0-1 loss, making it computationally efficient for optimization while maintaining a meaningful relationship with the true error (Zhang et al. 2019ah. loss is classfication ensures that any decision rule inconsistent with the Bayes optimal classifier has strictly larger ø-risk of the loss function é. This property is crucial for achieving optimal classification performance, and examples
loss, which informs how to design methods to mitigate the 1, - 14 tradcoff
surrogate loss is a surrogate loss (f) = E (x (f (())))
if it

---

Published in Transactions on Machine Learning Research MMrch/2020
include hinge loss, logistic loss, and exponential loss. Here, show the binary IBP loss falls into this loss calegory.
Lemma 4.1. Binary IBP loss is a logistic loss in the classsficatioon surrogate loss family.
Proof. We have binary LImP (2, Mo ep) = In(1 + +)) i y, which is a logistic loss.
Upper bound. Our following analysis provides a performance guarantee for minimizing the surrogate loss. We introducc a transformation & of classffcationncalibaaa conjugale of function that lower bounds the gap between a modified entropy function (e.g., surrogate loss like cesss-etropy) and the standard Shannon entropy (Zhang et al.) 2019a). This gap quantifies how well the surrogate loss approximates the true 0-1 classification error. The function 1/ is used to bound the difference between the union risk Runion and the optimal risk under individual l, perturbations R, miny R,) It has desirable properties: & is non-decreasing, convex, continuous on [0, 1J, and satisfies (0(0) = 0. By Eq we have Runion (f) - R2 = (f( R2 + Ralign (f) & t (R,(() - ) + Rallgn(()) where the inequality holds because @ is constructed from a cetteeatttionaaibrattt loss (Bartlett et al. 2006).
losses. // : [0, 1 - [0, o0) defined as the convex
Theorem 4.2. Let (J) (x((()))) and R2 == miny RT(s). Under Assumption in Zhang et al. (2019d), with E taken over the data distribution, for any non-negative loss function such that Ø(U) 2 L, any measurable f: X + R, any probability distribution on X' x {+1), IBP output bound differences from f as (x)x T. 22yt + y) for I, perturbations, and any x > O, we have
Rumion()) R2 S 1 1 (Ro + (I)) S for dr (x)).
The proof is in Appendix A.1 which sheds light on how Algorithmically, we can extend the framework to the case of multi-class classifications by replacing é with a multi-class calibrated loss L(.--) (Zhang et al. 2019a), such as cross-entropy, which ensures that minimizers indicates that we need to align
further improve union-certified robustness.
of the surrogate risk align with those of the 0-1 loss. ((d((r) the distributions between output bound differences of two perturbations, so Theorem 4.2 has a tighter upper bound. Vi * y. o. S, means we need to regularize those bounds only on the correctly predicted 4 subsets (Definition 4.3 meaning the subset y for which the lower bound computed with IBP of the correct class is higher than the upper bounds of other classes. Our analysis (Thcorem 4.2 shows that the union-certified objective admits upper bound decomposable into per-norm margin terms, and that misalignment between these margin distributions exacerbates the f trade-off. Bound Alignment explicitly minimizes this mismatch, thereby tightening the upper bound on union error and preserving robustness across norms. In other words, aligning bound distributions reduces the variance between per-norm certification margins, preventing fine-tuning under one norm from disproportionately degrading another.
Definition 4.3 (Correctly Certified 4 Subset). At epoch e, given the perturbation size e, E R and model f, for batch of data (x, ~ D of size n, we have the output upper and lower bounds computed by IBP for 4 ponturbations. We define a function h for this procedure as h(x) {oj 2, where {o:) lick is a vector of bounds for all classes. Then, the correctly certified subset at the current step is defined as:
Vj E y with (x). and bounds (o, (ā.)ish Hish), we have Vi # yj. o S Lgg
For certified training, Gowal al. (018): Müller et al. (2022) optimize the model using bound differences (ō. 2, lick (y is the correct class). Inspired by Theorem 4.2 we align the bound differences - J. of 1, and 1g CT outputs with a batch of n samples, specifically on the correctly cortified 1ę subset 7. Specifically, for each batch of data yx ~ DD we denole the bounds differences after softmax normalization for two perturbations as dg and d,- Then, we select indices 7, according to Definition indices as ne S n. We compute a KL-divergence loss over this set of samples using K [dd/[[i]ldd (Eq. 5 Intuitively, we aim to encourage [n] and d,[7] distributions to become close each other, such that we gain more union robustness.
4.3 We denote the size of the
1 Th
CKL
d, d+bb log
(5)
1=1 1=
7

---

Published in Transactions on Machine Learning Research March/2029
Apart from the KL loss, add another loss term using Max-style approach in Eq. 6 since Max performs relatively well, as shown in Table [ We also consider combining with Random/Joint losses if they lead to a better performance. Our final loss LSerasch combines LK and MMa,, via hyper-parameter 1) as shown in Eq.
Laa
max PE p2 x' B',,
max CIBP(E, y: Cp. Tp)
(6)
Cseaatch = LMaax + 7 CKL
(7)
Integrate NT into CT. In the context of adversarial robustness, Jiang & Singh (2024) shows that there exist useful portion of model updates in natural training, which can be extracted and integrated into adversarial training to improve adversarial rosust Based on this, we propose a technique to integrate NT into CT, to enhance union-certified robustness. Specifically, for model p(r) at any epoch r, we examine the model updates of NT and CT over all samples from D. The models phl and pe") represent the results after one epoch of NT and CT, from the same initial model p(r), Then we compare the updates of the two In = pm - p(')) and 9e = pe p(()) For a specific layer I, by comparing dh and g we retain a portion of 2 according to their cosine similarity score (Fq Negative scores indicate that In does not contribute to certified robustness, so discard components with similarity scores < 0. The GP (Gradient Projection) operation, defined in 9. projects d.. towards g..
cos(g g.) - Ill
GP [cos(oh gb) gin cos(g ge) > 0 00
(8)
cos(gn g2) 5
Therefore, the total projected (uscful) model updates 9p coming from In could be computed as Eq. 10 We use M to represent all layers of the current model update. The expression UlEM concatenates the useful natural model update components from all layers. A hyper-parameter 33 is introduced to balance the contributions of It is important to note that this projection procedure is applied only after the aps-annea phase of certified training. The theoretical analysis of why connecting NT with CT works is discussed in Appendix A.2
9GP and Ic, as outlined in Eq [1]
9p = U GP si)
(10)
9p (1 B3 ge p(r+1) -p(r) 3.9
(11)
IEM
Quick certified fine-tuning. In adversarial robustness, Croce & Hein (2022) shows that public models can be made more robust with only the application of fine-tuning, which reduces the computational cost significantly compared with training from scratch. In this work, we propose the first fine-tuning certified multi-norm robustness scheme CURE-Finctune. Starting from single norm pre-trained model, perform the bound alignment lechnique by optimizing LSeratch for few epochs. Because of the l 4, tradeoff, certifiably finetuning a 4, pre-trained model on Lg perturbations reduces 4, robustness. Thus, we want to proserve more 1, robustness when doing cortified fine-tuning, which makes bound alignment useful here. By regularizing on the correctly certified 4, subset with Cscratch we can prevent losing more 4 robust when boosting ly robustness, which leads to better union accuracy. We note that to any single-none norm certifiably pre-trained models. As shown in Table [ we can obtain superior multi-norm certified robustness by performing quick fine-tuning pre-trained lo models.
can be adapted
5 Experiment
In this section, we present and discuss the results of union, geometric, and patch robustness, as well as ablation studics on hyper-parametors for MNIST, CIFAR-10, and TinyImagenct experiments. Other ablation studies, visualizations, and algorithms of CURE can be found in Appendix C and
Experimental Setup. For datasets, use MNIST (LeCun et al., 2010 and CIFAR-10 (Krizhessyy ct al. 2009) which both include 60K images with 50K and 10K images for training and testing, as well as Tiny Iet (Le & Yang, 2015) 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. loot Lx certified defense SABR (uülee et al., 2202). 2. l:: 12 cortified defense based on SABR, 3. CURE-Joint: take a weighted sum of l2, loo IBP losses. 4. CURE-Max: take the worst of 12, IBP losses. 5. CURE-Randoma randomly partitions the samples into two blocks, then applies the Joint loss with equal weights. 6. CURE-Scratch:
8

---

Published in Transactions on Machine Learning Research MMarch/2020
training from scratch with bound alignment and gradient projection techniques. 7. CURE-Finctune: robust fine-tuning with the bound alignment technique using 1x pre-trained models. We use 7-layer convolutional architecture CNN7, a standard architecture dMüller et al. 2022) for certified training. In Table 14 we compare our proposed lz defense with Hu et al. (2023). where we show our method outperforms the SOTA 1 deterministic certified defense on CIFAR-10. We choose similar hyperparameters and training spt as Müller et al. (222)) for So certified training. We select a 0.5, subselection ratio X₂ 1e-5, 5 8 0.5, and 7j 2.0 according our ablation study results in Section 5.2 and Appendix C For certified fine-tuning, we finetune 20% of the epochs of CURE-Scratch and are only performed on Lo models they generally have higher
robust errors. Full implementation details are in Appendix B
5.1 Main Results
Evaluation. We choose the common coo (,, values used in the literature Müller et al. 2022 Hu et al. 2023
to construct multi-norm regions. These include (E) - 1.0, 0.5, 6oo
0.1), (E: = 2.0, - 1.0, 6x
0.3)
for MNIST, (e1 = 0.5, 62 = 0.25, foo = 2. (e1 = 1.0,, = 0.5, 235 for CIFAR-10 and (<1 = 255 62
72
1 for Tiny ImageNe. We make sure the adversarial regions with sizes coo, E1 and E2 do not coe = 255
30
include each other. We report the clean accuracy, certified accuracy against 4, 22,22,0 perturbations, union accuracy, and individual/averan
certified robustness against geometric transformations attacks. Further, we alpha-beta. crown (Zhang al., 2018) for certification on l2, perturbations, FGV (Yang et al. 2022) for elficient certification of geometric transformations. and Chiang et al. (2020) for 2 x 2 patch attacks. Additional experiment results on CIFAR-100, varying epsilons for 1p norms where we show our methods generalize to a wide choice of epsilons and ablation studies can be found in Appendix C
well patch
Dalaset
(Coo: 62, c1)
Methods
Clesn
Loo
l2
Union
1o0
94.5
94.7
0.0
CURE-Joint
98.7
90.5
76.3
50.8
50.3
MNIST
(0.3, 1.0, 2.0)
CURE
CURE-Max Max
98.7
91.1
76.2
47.2
46.5
CURE-Raadon
98.7
90.5
76.3
50.8
50.3
CURE-Finetune
98.5
90.1
83.5
64.0
63.2
98.0
89.4
85.9
71.5
70.5
100
51.8
36.3
6.0
3.8
3.5
l2 78.6
0.0
56.5
75.8
0.0
CURE-Joint
51.3
23.9
34.0
38.6
21.4
CIFAR-10
0.5, 1.0)
CURE-
33.9
19.5
BURE-Raadon
28.9
28.0
CURE-Finetune CURR-Seratch
30.2
30.8
34.8
29.3
49.5
34.2
28.1
32.0
26.3
Loe
28.3
19.4
19.4
12.9
12.9
lg
36.2
2.9
30.6
23.5
2.9
CURE-Jolat
30.2
20.0
25.9
18.8
18.8
TinyImagnet
235 253
36
255
72
CURE-Max
29.6
21.8
23.5
18.2
18.2
CURE-Randon
30.5
25.9
28.2
23.5
23.5
CURE-Fiatune
28.1
21.2
21.8
18.2
16.6
CURE-Seratch
29.7
23.5
26.5
Table 1: Comparison of the clean accuracy, individual, and union certified accuracy (%). 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.
Union accuracy on MNIST, CIFAR-10, and Tinylmagenet with CURE framework. In Table show the results of clean accuracy and certified robustness against single and multi-norm with CURE MNIST, CIFAR-10, and TinyImagenct. CURE-Joint, CURE-Max, and CURE-Random usually yield better union robustness than l2 and lo certified training. Further, CURE-Scratch and CURE-Finetume consistently improve the union accuracy compared with other multi- norm methods with significant margins in most cases (20% for MNIST and 8% for CIFAR-10 experiments), showing the effectivencss of bound alignment and gradient projection techniques. Also, for quick fine-tuning, we show is possible quickly fine-tune loc robust model with good union robustness using bound alignment, achieving SOTA union

---

Published in Transactions on Machine Learning Research March/2028
Linf CURE-Max
RC()),(()) ((1).B(0.001)
Configs
R(10)
((2)))h(2)
Avg
Differeccs
Diftrrncess
Ise
27.8
33.2
23.3
28.1
lg
36.6
0.0
0.0
12.2
CURE-Joint
35.0
41.4
28.2
34.9
CURE-Max
33.7
39.0
2.5
5.0
7.5
0.0
2.5
5.0
7.5
CURE-Random
35.1
40.9
Classes
Classes
CURE-Scratch
34.2
39.6
24.9
32.9
Linf CURE-Scratch
L2 CURE-Scratch
Difforncees
Bound Differences
Figure 4: Comparison CURE against geometric transforma- tions for CIFAR-10 (e1 = 1.0, e2 = 0.5, to = 255 experiment.
We denote R(y) a rotation of +o degrees; (u(u and Tv(Aw) a translation of =Au pixels horizontally and =Av pixels verti- cally, respectively; Sc(A) a scaling of =1%; Sh(7) shearing of +7%; C(o:) contrast change of +a%; and B(3) brightness change of =3. CURE improves the geometric certified robust- ness compared with single norm Iraining. CURE-Scratch achieves the best average geometric transformation robustness,
Figure 5: CURE-Max and CURE-Scratch bound difference visualization. CURE- Scratch has a more similar bound distri- butions compared with CURE-Max.
accuracy MNIST and CIFAR-10 experiments. More results MNIST, CIFAR-10, and CIFAR-100 are available in Appendix C
Union accuracy on SST-2 dataset with BERT architectures. Beyond vision tasks, we further apply CURE to a BERT-based model for text classification on the SST-2 dataset, operating in the latent space. As shown in Table 2 CURF-SCRATCH achieves the strongest robustness against. both Text Fooler (Jin el al, 2020) and PWWS (Ren al.) 2019) attacks. Since full certification for large-scale language models such as BERT is currently infeasible, we follow prior work and strong empirical attacks as proxy for union robustness evaluation. These results provide additional evidence that CURE improves generalized robustness beyond vision settings.
Table 2: Robust accuracy (%) on SST-2 under strong empirical attacks.
Robust Acc
ccot
b2-cort
CURE-MAX CURE-SCRATCH
SST-2 (PWWS (Ren 2019
16.8
15.2
24.0
28.4
SST-2 (Text (Jin al. 2020))
9.4
10.0
15.6
17.6
Robustness against unseen geometric and patch transformations. Table g and Table 7 (in Appendix) compare CURE with single norm training against various geometric perturbations on MNIST and CIFAR-10 datasets. CURE outperforms single norm training on diverse geometric transformations (e.g., 6% for CIFAR-10 on average), leading to better generalized certified robustness. Also, CURE-Seratch has better geometric robustness than CURE-Max on both datasets, which reveals that bound alignment and gradient projection lead to better generalized certified robustness. In addition, in Table [a] we display the certified robustness of CURE compared with single-norm baselines against patch 2 x 2 attacks. Our framework outperforms related basclines with 8.5% for MNIST and 16.0% for CIFAR-10, showing better generalized certified robusiness. We hypothesize Ihat many non-lp perturbations can be approximated or parameterized using 1 bo-uoudded formulations, and improving 4p robustness enhances robustness to such transformations we find that CURE training achieves significantly higher bound overlap compared to single-norm models (Table 9). However, we also observe that geometrically robust model lacks multi-norm robustness, as shown in Table in Appendix.
10

---

Published in Transactions on Machine Learning Research (March/200)
Claan
Chon
Usioo
Clean
Usion
0.8200 028200.829..0000
51.5
50.5
48.2
073
3.542.334
0.40
023 6.102
16.55
000
T2D
toge
2.00
0.25
1.00
0.13
130
(b) ry weight for bound alignment.
(c) syper-paramen for GP.
(a) de: subselection ratio for lz.
Figure 6: Alabtion studies on A2, 7y and 3 hyper-parameters. According to the graphs choose d2 le-5 2.0 and B = 0.5.
5.2 Ablation Study and Discussions
Subselection ratio X. For Loo certified training, we use the same Ago as in Müller et al. (2022). For A2, in Figure 6a we show the 12 certified robustness using varying X2 E [O..... 1e-2 with 62 0.5. According to Figure 6a we choose X2 1e-5
Bound alignment (BA) hyper-parameter n7. We perform CIFAR-10 (Eoo 255 E2 0.5, 1.0)
s
experiments with 17 values in (0.5, 1.0, 1.5, 4.0). In Figure 6b the clean accuracy generally drops we have larger values, with union accuracy improving then dropping. We pick 17 2.0 with the best union accuracy for most experiments.
Gradient projection (GP) hyper-parameter B. Figure 6c displays the change of clean and union accuracy with choices of varying 3 values on CIFAR-10 (Eoo = 255 C2 = 0.5, 1 = 1.0). CURE-Scratch is generally insensitive 3 values. Thus, we choose 3 = 0.5 for the experiments.
Ablation study on BA and GP. In Table 3b we show the ablation study of BA and GP techniques on 8
255 C2 0.5, = 1.0) experiment. BA and GP improve union accuracy by 6.8% and 2.7%, demonstratting the individual effectiveness of our proposed techniques.
CIFAR-10 (ex
Methods
MNIST
CIFAR-10
1.0
68.9
0.0
Clean
[oc
12
4
Union
12
0.0
0.0
CURE-Joint
68.5
0.2
CURE-Ma -Mx
51.5
33.9
19.5
21.6
16.8
CURE-Max
65.8
0.1
+BA
50.2
33.8
25.4
27.9
23.6
CURE- RiRE-Random
+BA GP
49.5
32.0
CURE-Scratch 77.4
10.1
(b) Ablations on BA and GP.
(a) Robust accuracy against 2 2 patch attacks on MNIST (61
2.0, 62 c.0, 6.2 0.3) and CIFAR-10 (a1 253 255 6xe
265 datasets. Results show CURE significantly outperforms single-norm training.
Liick Visualization of bound differences. Figure 5 displays the bound differences fo, Jiji of one example that is improved by CURE-Scratch (sccond row), compared with the CURE-Max (first row), from the CIFAR-10 (Exo 255 62 0.5, 1.0) experiment. We use outputs from o, 3.C.RR..W For le perturbations (blue diagrams), CURE-Scratch consistently shows positive bound differences enabling robust union prediction, while CURE-Max has several negative ones (highlighted in red). The sccond-row distributions are more aligned than the first, showing that CURE-Scratch effectively aligns bound differences. This highlights the effectiveness of the bound alignment method. Additional visualizations are in Appendix C
Time cost of CURE. The extra training costs of GP are small, taking 6, 24, scconds using a single NVIDIA A40 GPU on MNIST, CIFAR-10, and TinyImageNet datasets (Table 16.. respectively. Compared with the total training cost of CURE-Scratch, it only accounts for 6% of the total cost.. For runtime
11

---

Published in Transactions on Machine Learning Research Mlarch/2020)
comparison of different methods with the same number of training epochs, we have complete runtime analysis (Table 15 in Appendix D for the MNIST experiment. CURE-Joint has the largest cost. among all methods. CURE-Scratch has a small extra time cost than CURE-Max, showing our proposed techniques have little additional cost.
Limitations. For l2 certified training, we use a loo box instead of l2 ball for bound propagation, which leads to more over-approximation and the potential loss of precision. Also, we notice drops in clean accuracy when training with CURE methods. BA and GP techniques lead to slight decrease in clean accuracy in experiments. Further, our work does not claim to achieve universal certified robustness, but takes a step toward it by showing that multi-norm training offers broader cortified robustness than single-norm or geometrie-certiffed models (Table 8).
Extension to other perturbation types. Our framework is not inherently limited to the l2- foo setting and can, in principle, be extended to & or other lp norms. The key requirement to identify the dominant tradeoff pairs between different lp threat models, which determines where robustness confliets arise and where alignment is most beneficial. As shown in prior work RAMP (Jiang & Singh, 2024) robustness tradeoffs are highly asymmetric across norms, and effective multi-norm training depends explicitly targeting these critical tradeoff directions rather than treating all norms uniformly. That said, l (and other ep) certified training currently requires substantial additional engineering effort. In practice, & certification involves looser bounds, higher computational cost, and less mature verification tooling compared to la and foor which makes large-scale multi-norm certified training significantly more challenging. These limitations are largely orthogonal to our framework and stem from the current state of certified verification methods. As ceritification techniques general lp norms continue to improve, we expect our approach to extend naturally to these settings.
5.3
Discussion
We note that several components of our framework are inspired by prior work in adversarial (empirical) robustness (Trmmer & Boneh 2019 Zhang et al. 2019a Madaan et al. 2021 Croce & Hein 2022 Jiang &
techniques are closely related to multi-objective optimization strategics commonly explored in adversarial training. These techniques are broadly applicable to robust learning, and our work builds upon these insights. At the same time, our framework is specifically developed in the context of certified robustness. In contrast to adversarial training methods that operate logits or adversarial examples, our approach leverages certified bounds produced by the perturbations the core optimization signal. As result, guarantees, rather than empirical robustness. Overall, while our method draws inspiration from prior robust training approaches, it adapts and extends these idcas to the certified setting by operating on certified bounds, leading to improvements in union-certified robust
Singh 2024 y. In particular, ideas such as joint training and gradient-basee
objective is to improve provable worst-case
6 Conclusion
We propose framework CURE with multi-norm certified training methods for better union robustness. We establish a theoretical framework to analyze the tradeoff between perturbations, which inspires us to 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 Tinylmagenet show that CURE significantly improves union accuracy and robustness against geometric and patch transformations, paving the path to generalized certified robustness.
7 Acknowledgement
We sincerely thank the anonymous reviewers and the action editor for their insightful comments and constructive suggestions. This work was supported by NSF Grants No. CCF-2238079, CCF-2316233, CNS-2148583, Google Research Scholar Award, and Open Philanthropy research grant.
12

---

Published in Transactions on Machine Learning Research MMarch/2020)
References
Stefan Balauca, Mark Niklas Müller, Yuhao Mao, Maximilian Baader, Marc Fischer, and Martin Vechev. Gaus- sian loss smoothing enables certified training with tight convex relaxations. arXiv preprint ar arXiv:2403.07095 2024.
Mislav Balunović and Martin Vechev. Adversarial training and provable defenses: Bridging the gap. In 8th International Conference on Learning Representations (ICLR (020)ui)) International Conference on Learning Representations, 2020.
Mislav Balunovic, Maximilian Baader, Gagandeep Singh, Timon Gehr, and Martin Vechev. Certifying geometric robustness of neural networks. Advances in Newral Information Processing Systems, 32, 2019.
Peter I. Bartlett, Michael Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101 2006.
Sébastion Bubock, Yin Tat. Lee, Eric Price, and Nya Razenshteyn. Adversarial examples from computational constraints. In International Conference on Machine Learning, pp. 831 840. PMLR, 2019.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy S Liang. Unlabeled data improves adversarial robustness. Advances neural information processing systems, 32, 2019.
Hanjie Chen and Yangfeng Ji. Adversarial training for improving model robustness? look at both prediction and interpretation. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pp. (0463-10477) 2022.
Ping-yeh Chiang, Renkun Ni, Ahmed Abdelkader, Chen Zhu, Christoph Studor, and Tom Goldstein. Certified defenses for adversarial patches. In International Conference on Learning Representations, 2020. URL https://
Francesco Croce and Matthias Hein. Adversarial robustness against multiple and single 1 p-treea models via quick fine-tuning of robust classifiers. In International Conference on Machine Learning, pp. 4436 4454. PMLR, 2022.
Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of adversaries. Advances in Neural Information Processing Systems, 31, 2018.
Sihui Dai, Chong Xiang, Tong Wu, and Prateek Mittal. Position paper: Beyond robustness against single 2024. URL https:///oi. org/10. /000 200.448550/rrkc arxvv 2405. 01349
attack types. CoRR,
Alessandro De Palma, Rudy Bunel, Krishnamurthy Dvijotham, M Pawan Kumar, and Robert Stanforth. Ibp regularization for verified adversarial robustness via branch-and-bound. arXio preprint arXi::2206.1477 14772, 2022.
Edoardo Debenedetti and Carmela. Troncoso EPFL. Adversarially robust vision transformers, 2022.
Tan J Goodfellow, Jonathon Shlens, and ian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 1cXii:1412.6511 2014.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXio preprint 1rXiv:1810.122 12715, 2018
Sven Gowal, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmect Kohli. Uncovering the limits of adversarial training against norm-bounded adversarial examples. arXiv preprint arXiv:2010.0880 2020.
Kai Hu, Klas Leino, Zifan Wang, and Matt Fredrikson. A recipe for improved certifiable robustness: Capacity and data. Xi preprinl or xxii:2310.02511 2023.
Kai Hu, Andy Zou, Zifan Wang, Klas Leino, and Matt Fredrikson. Unlocking deterministic robustness certification imagenet. Advances in Neural Information Processing Systems, 36, 2024.
13

---

Published in Transactions on Machine Learning Research (March/20P))
Enyi Jiang and Gagandoep Singh. Ramp: Boosting adversarial robustness against multiple Lp perturbations. Xrviv preprinl arXin:240.. 06827, 2024.
Di Jin, Zhijing Jin, Joey Tianyi Zhou, and Peter Szolovits. Is bert really robust?? a strong baseline for natural language attack on text classification and entailment. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 8018 8025, 2020.
Daniel Kang, Yi Sun, Tom Brown, Dan Hendrycks, and Jacob Steinhardt. Transfer between perturbation types. arXiv preprint arxiv: 01034, 2019.
of adversarial robustness
Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In Computer Aided Verification: 29th International Conference, CAV 2017, Heidelbery, Germany, July 24-28, 2017, Proceedings, Part I 30, pp. 97 117. Springer, 2017.
Hoki Kim. Torchattacks: A pytorch repository for adversarial attacks. ar preprint arXiv:2010.0195)
2020.
Diederik P Kingma. Adam: A method for stochastic optimization. ar preprint arXiv:1412.6800 2014.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Alexcy Kurakin, Ian J Goodfellow, and Samy Bengio. Adversarial examples in the physical world. In Artificial intelligence safely and securily, pp. 99 112. Chapman and Hall/CRC, 2018.
Ya Le and Xuan S. Yang. Tiny imagenet visual recognition challenge. 2015. URL https://ag semanticscholar org/ Cotp://CrpsSI::::aa. 166644790
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online].
Available: http://yann. http:yaan.leecuc.co lecun.com/exdiy /mnist, 2, 2010.
Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robust neural networks. In International Conference on Machine Learning, pp. 6222-6222. PMLR, 2021.
Aishan Liu, Shiyu Tang, Xianglong Liu, Xinyun Chen, Lei Huang, Zhuozhuo Tu, Dawn Song, and Dacheng Tao. Towards defending multiple adversarial perturbations via gated batch normalization. arXio preprinl 20x::0012.066.. 2020.
Shao-Yuar To and Vishal M Patel. Defending against multiple and unforeseen adversarial videos. IEFE Transactions Image Processing, 31:962-99 973, 2021.
Divyam Madaan, Jinwoo Shin, and Sung Ju Hwang. Learning to generate noise for multi-attack robustness. In International Conference on Machine Learning, pp. 7279 7289. PMLR, 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial atlacks. arXiv preprinl arXie: 1706 170.006666, 2017.
Pratyush Maini, Eric Wong, and Zico Kolter. Adversarial robustness against the union multiple perturbation models. In International Conference on Machine Learning, pp. 1600-650. PMLRR 2020.
Pratyush Maini, Xinyun Chen, Bo Li, and Dawn Song. Perturbation type calegorization for multiple adversarial perturbation robustness. In Uncertainty in Artificial Intelligence, pp. 1317-1327. PMLR, 2022.
Ravi Mangal, Klas Leino, Zifan Wang, Kai Hu, Weicheng Yu, Corina Pasareanu, Anupam Datta, and Matt Fredrikson. Is certifying ip robustness still worthwhile? arXiv preprint arXic:2310. 1.1:0033,,,,,,1, 2023.
Yuhao Mao, Mark Niklas Müller, Mare Fischer, and Martin Vechev. Understanding certified training with interval bound propagation. arXiv preprint arXiv:2306. 10426, 2023.
Yuhao Mao, Stefan Balauca, and Martin Vechev. Ctbench: A library and benchmark for certified training. Xiu preprint ar orXix22466.0440 2024a.
14

---

Published in Transactions on Machine Learning Research (March/200) /2026)
Yuhao Mao, Mark Müller, Mare Fischer, and Martin Vechev. Connecting certified and adversarial training. Advances in Newral Information Processing Systems, 36, 2024b.
Matthew Mirman, Timon Gehr, and Martin Vechev. Diffcrentiable abstract interpretation for provably robust neural networks. In International Conference on Machine Learning, pp- 3578 3586. PMLR, 2018.
Mark Niklas Müller, Franziska Eckert, Marc Fischer, and Martin Vechev. Certified training: Small boxes are all you need. arXiv preprint arXic:2210.0444 04871, 2022.
Soumalya Nandi, Sravanti Addepalli, Harsh Rangwani, and R Venkatesh Babu. Certified adversarial robustness within multiple perturbation bounds. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2298 2298-2305, 2023.
Jay Nandy, Wynne Hsu, and Mong Li Lec. Approximate manifold defense against multiple adversarial perturbations. In 2020 International Joinl Conference on Newral Networks (IJCNN), pp. 1-8. TEEE, 2020.
Alessandro De Palma, Rudy R Bunel, Krishnamurthy Dj Dvijotham, M. Pawan Kumar, Robert Stanforth, and Alessio Lomuscio. Expressive losses for verified robustness via convex combinations. In The Twelfth ?id=
International Conference on Learning Represendations, 2024. URL https::/ mZyZAwzKIM
ShengYun Peng, Weilin Xu, Cory Cornelius, Matthew Hull, Kevin Li, Rahul Duggal, Mansi Phute, Jason Martin, and Duen Horng Chau. Robust principles: Architectural design principles for adversarially robust cnns. Xiv preprint arXiv:2308.162: 2023.
Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John Duchi, and Percy Liang. Understanding and mitigating the tradcoff between robustness and accuracy. arXiv preprint X11:22002.00716, 2020.
Shuhuai Ren, Yihe Deng, Kun He, and Wanxiang Che. Generating natural language adversarial examples through probability weighted word saliency. In Proceedings of the 57th annual meeting of the association for computational linguistics, pp. 1097,1097, 2019.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adversarially robust generalization requires more data. Advances in newral information processing systems, 31, 2018.
Zhouxing Shi, Yihan Wang, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsich. Fast certified robust training with short warmup. Advances in Neural Information Processing Systems, 34:18335 18349, 2021.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. Advances in neural information processing systems, 31, 2018.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying neural networks. Proceedings of the ACM on Programming Languages, 3(POPI.) 2019.
Florian Tramer and Dan Boneh. Adversarial training and robustness for multiple perturbations. Advances in neural information processing systems, 32, 2019.
Florian Tramer, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Bonch, and Patrick McDaniel. Ensemble adversarial training: Attacks and defenses. arXiv preprint ar 1rxi::1775. 170,000400, 2017.
Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsich, and J Zico Kolter. Beta-crown: Efficient bound propagation with per-neuron split constraints for neural network robustness verification. Advances in Newral Information Processing Systems, 34:29909-29921, 2021.
Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma, and Quanquan Gu. Improving adversarial robustness requires revisiting misclassified examples. In ICLR, 2020.
Zekai Wang, Tianyu Pang, Chao Du, Min Lin, Weiwei Liu, and Shuicheng Yan. Better diffusion models further improve adversarial training. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 36246-36266 PMLR, 23-25 29 Jul 2023. URL https: htttps//ppooeeee http:///eooeees..../.o mlr press/v202// www.g2/wa/aad....mm html html
15

---

Published in Transactions on Machine Learning Research (March /2026)
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J Zico Kolter. Scaling provable adversarial defenses. Advances in Newral Information Processing Systems, 31, 2018.
Dongxian Wu, Shu-Tao Xia, and Yisen Wang. Adversarial weight perturbation helps robust generalization. Advances in Newral Information Processing Systems, 53:2958-2960 2020.
Jiancong Xiao, Zeyu Qin, Yanbo Fan, Baoyuan Wu, Jue Wang, and Zhi-Quan Luo. Adaptive smoothness-
weighted adversarial training for multiple perturbations with its stability analysis. arXiv preprint (XXi:22100005571 2022.
Kaidi Xu, Chenan Wang, Hao Cheng, Bhavya Kailkhura, Xue Lin, and Ryan Goldhahn. Mixture of robust experts (more): A robust denoising method towards multiple perturbations. arXio preprinl arXiv:2104.10586 2021.
Xiaojun Xu, Linyi Li, and Bo Li. Lot: Layer-wise orthogonal training on improving 12 certified robustness. Advances in Neural Information Processing Systems, 35:18904- 18915, 2022.
Rem Yang, Jacob Laurel, Sasa Misailovic, and Gagandeep Singh. Provable defense against geometric transformations. arXiv preprint arXiv:220..11177, 2022.
Hangsheng Zhang, Jiqiang Liu, and Jinsong Dong. Care: Ensemble adversarial robustness evaluation against adaptive attackers for security applications. arxie preprint arXiv:2401.11126, 2024.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference on machine learning, pp- 7472-768 147227482, PMLR, 2019a.
Huan Zhang, Tsui- Weng, Pin-Yt Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. Advances in Neural Information Processing Systems, 31:4939 4948, 2018. URL httpp::/arxxv..org/eaaaaa///
000.6.0860... pdf
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsich. Towards stable and efficient training of verifiably robust neural networks. arXiv preprint arXiv:1906.0631 2019b.
Jingfeng Zhang, Jianing Zhu, Gang Niu, Bo Han, Masashi Sugiyama, and Mohan Kankanhalli. Geometry- aware instance-reweighhee adversaria training. In International Conference Learning Representations, 2021. URL https:://openrevien http:://wwaaroeeeeeeoooooooaaaaa
16

---

Published in Transactions on Machine Learning Research Mlarch/2020)
A Proofs of the Theorems
In this section, we provide the proofs of the Theorems.
A.1 Proof of Theorem 4.2
Theorem 4.2 (restated). Let Ro(f)= ==E)((())) and R :=min Ro(f). Under Assumption 1 in Zhang et al. 2019a1, for any non-negative loss function @ such that o(0) 2 1, any measurable f X R, any probubilily distribulion on X x {+1}, IBP oulpul bound differences from f as dx(x) = T. 22 (i + v) for l perturbations, and any À > 0, we have.
R2 v 3/4 3 R2) + - R Runson
0 and f(z/)1 S 0) (o ((
W (Ro +E
max
2 (Ro()) (() 4
for d (z)).
Proof. By Eqn. equation Runioa (f) -
(f) - R₂ Ralign (f) < 3 2 (Rs ( + Ralign (f),
where the last incquality holds because we choose & as a clasiiictioon-calibrteed loss Bartlett et al. (2006) This leads to the first inequality.
Also, notice that
(g) and an S 0
s (1) of/c
E max
max
0))
(.... ((,i5)))))
E max max
E. max max (,EB,(L..)),EEBBBBCC.
(ld( S for (z)).
The last inequality holds because the adversarial loss is always upper-bounded by the IBP loss. Therefore, we get the second and third inequality in Theorem A.I
A.1.1 Multiclass extension
To characterize the robustness of score function f f:X -> RKK for K-class classification, define robust error under the threat model of ba perturbation:
Rg(f) = (a [ (3x, Bg(x, s.t. f(x))) I max f(x))))
Here, f(r), denotes the output logit for the true class y, and max f(z) is the maximum logit among all incorrect classes.
We define Rx(l) similarly to R,),), and without loss of generality, asume R,( 2 R.(S). Then, we introduce the alignment error as the risk calculated on x X that are robust against E, attack but not robust against Eg attack.
{ Are E B,(r,),, o E By(2, Cq): s.t. f(x)), > max (x()) and f(x()) S max (((r)s H
Ralign Rflign())= B(
We define union error the risk calculated on x E that are either not robust against l, or l, attack. We have the following relationship:
Ru)ion(J) R,) + Ratign (f)-
17

---

Published in Transactions on Machine Learning Research (March/2022
Theorem 4.2 (multiclass extension) Let Ra(f) := Ez(f(z), maxj#y fx)),) and R min, Rd Under the same assumpt ion as in binary classification, for any non-negative loss function & such that Φ(0) 2 1, any measurable f X + æk any probability distribution on X' x fl...., K}, and any À >>> 0, we have
Runion (5) - R2 S + (Ros - R2y) + Raligu (f)
s s (Ro() R2) + EE [at (1(2)-d((2)) 1(d (x) s o0]
where we define the certified margin gaps (following binary case) (x) max of - 06 dg(z)) (a) where og",, ofa) are the IBP lower and upper bounds over B, (z, ex), and similarly for by Note: d(x) S 0 indicates certified robustness while d(x) > 0 indicates not certified robust.
m o.4)) Qy
Proof. Ramion (/) - R2 = (,) - R + Ralign (f) v a (R,(() - R5) + Ralign (f); where the last inequality holds because we choose & as a inneification-caliraate loss for multiclass classification. This gives us the first inequality.
Now we bound (S). Define the margin for any point as m(x') = (x'), max (('')y The alignment. condition becomes = such that m(x²) and m(a²) s O.
Similar to binary classification,
Pr(3rr, E By E Bg : m(x²) > and m(x{) s 0]
< Pr E Br, E Bg m((x)) m(xr) S 0 and m(x;)) > 0]
[1m(a²)) # m(xx)) (mm(x)) > 03]
= EE max of (a,er)) (1,5o))))
{{ (m(e))m(x()) mlxx)) < 0f 1mm(x)) > 03]
= E
max of (z,er) ((,,e)))
A
② ( m(xx))
((m(tt)) ( lfm(z() > 0]]
S E
max
A
(x,,)(
dr (x) (1(()_d((0))
< 1 1
(z), 20]
A
A.2 Theory of connecting NT with CT
The proof for connecting NT with CT via gradient projection (GP) is very similar to what has been done in Jiang & Singh (2024), where authors analyse and compare the delta errors of two aggregation rules (standard training and training with GP). Delta errors are the indicators of convergences of different aggregation rules based on a mild assumption on the Lipschitz contimuity of loss function gradients. GP leads to a smaller Delta error, which means GP results in a better convergence. The only difference in connecting NT with CT is that we use a different loss function compared with adversarial training, which makes the proof almost the same. One can refer to Jiang & Singh (2024) for the more detailed proof of GP.
B More training details
Certified training for 1a robustness. We propose a new la deterministic certified training method, inspired by SABR Müller et al. (2022). For the specified eo and T2 values, we first generate adversarial examples by computing the gradient in the 1/ direction (Km) 2020). then truncating the perturbation to lic within a slightly reduced loo ball B (Ir, c T2). After that, we propagate a smaller box region B (x', T2) using the TBP loss. The loss we optimize can be formulated follows:
18

---

Published in Transactions on Machine Learning Research (March/20P)
Li (2,
max CIBP(Z', y. T2)
Training details. We mostly follow the hyper-parameter choices from Müller et al. (022 for CURE. We include weight initialization and warm-up regularization from Shi et al. (2021). Further, we use ADAM (Kingma 2014) with an initial learning rate of le-1, decayed twice with a factor of 0.2. For CIFAR-10, 2
we train 160 and 180 epochs for (e 255 E2 = 0.25) and (ex0 = 255 62 = 0.5), respectively. We decay the learning rate after 120 and 140, 140 and 160 epochs, respectively. For the Tinylmagenet experiment, we use the same setting as the CIFAR-10 (<x 255 <2 0.5) experiment. For the MNIST dataset, we train 70 epochs, decaying the learning rate after 50 and 60 epochs. For batch size, set 128 for CIFAR-10 and TinyImagenel and 256 for MNIST. For all experiments, we first perform one epoch of standard training. Also, we anneal Coo, from 0 to their final values with 80 epochs for CIFAR-10 and Tinylmagenet and 20 epochs for MNIST. We only apply GP after training with the final epsilon values. For cortification, we verify 1000 examples on MNIST and CIFAR-10, as well as 170 examples on TinyImagener The values of all hyperparameters can be found in Table 4
MNIST- small MNIST- large CIFAR-small ClFAR-large Imylmaeent
Ase
0.4
0.6
0.1
0.7
0.4
A2
1.00F-05
1.00F-05
1.00E-05
1.00F-05
1.00E-05
Learning rate
1.00E-04
1.00E-04
1.00E-04
1.00E-04
1.00E-04
LR decay ratio
0.2
0.2
0.2
0.2
0.2
Training epochs
70
70
160
180
180
Decay epochs
50, 60
50,
120,
140
140,
160
140,
160
Batch size
256
256
128
128
128
(CURE)
0.5
0.5
0.5
0.5
0.5
7 (CURE)
2.0
0.5
2.0
2.0
2.0
3 (CURE)
0.5
0.5
0.5
0.5
0.5
Table 4: Training specifications of our main experiments MNIST, CIFAR-10, and Tinylmagenet.
Certifications for evaluations on 1,, norms. We evaluated our trained models using a, CROWN (Zhang et al. 2018). Specifically, a, J.C-RROW employs an efficient linear bound propagation framework coupled with a branch-and-bound algorithm to certify the robustness neural networks against adversarial attacks. propagates bounds on network outputs layer-by-laee. These bounds are linear functions representing the range of potential values the network's output take under a given set of input constraints. In addition, the branch-and-bound algorithm systematically divides the input space into smaller regions (branching) and computes tighter bounds on each subregion. a, B.CROWW is versatile and supports various activation functions, including ReLU, sigmoid, and tanh, making it applicable to a wide range of neural network architectures. Also, it supports the cortification on different (p 1,2, oo) norms, which fits the goal of our CURE framework for multi-norm certified robustness.
C Other experiment results and ablation studies
Additional experiment on MNIST (cx = 0.1, = 61 = 1.0) and CIFAR-10 (cx 255 <2 = 0.25, é = 0.5). As shown in Table our CURE-Seratch method achieves higher union-certified accuracy on both MNIST and CIFAR-10 compared to all baseline methods. This demonstrates that training from scratch with our proposed multi-norm certified training framework not only consistently outperforms single-norm approaches.
Additional experiment on CIFAR-100 (Ex = 2/255, <2 = 0.25, 61 = 0.5). As shown in Table our CURE-Scratch method significantly improves union-cortified accuracy on the CIFAR-100 datasct compared all baseline methods. Specifically, CURE-Scratch reaches a union accuracy of 30.4%. outperforming CURF-Joint, CURF-MAX, and CURF-RRndom by substantial margins.
19

---

Published in Transactions on Machine Learning Research (March/200 (
Dataset
(Eoos E2, E1)
Methods Clean
660
l2
4
Union
1
99.2 97.0 96.5 95.0
94.9
l2
99.5
98.6 98.0
CURE-Joint
99.2 97.6 97.5
97.2
MNIST
(0.1, 0.5, 1.0)
CURE-Max
99.3 97.6 97.3 96.8
96.8
CURE-Random
99.2 97.1
96.9
BURR--inetuun
99.1 97.0 97.3 96.8
96.5
CURE-Scratch
99.2 97.5 98.0
97.5
1.0
79.2 60.3 67.3 75.9
60.3
l
82.1 5.8 81.7
5.8
CURE-Joint
79.4 56.2 68. 77.1
56.2
CIFAR-10 255
0.25, 0.5)
CURE-Max
77.6 60.0 69.3 75.2
60.0
CURE-Random
78.4 59.0 68.5
58.9
CURE-Finetume
78.0 59.7 68.2 75.9
59.7
CURE-Scratch
16.061.267.77...
61.2
Table Comparison of the clean accuracy, individual, and union certified accuracy (%). CURE consistently improves union accuracy compared with single-norm training with significant margins all datasets. CURE- Scratch and CURE-Finetunn outperform other methods in most cases.
Clean Linf (2/255) L2 (0.25) L1 (0.5) Union
Linf (2/255)
39.7
26.4
16.0
18.6
14.8
L2 (0.25)
54.3
2.4
37.4
47.4
2.4
CURE-Joint 42.5
28.0
26.8
32.4
26.0
CURE-MAX
40.7
26.8
22.8
29.4
22.6
CURE-Random
41.3
28.4
27.2
34.0
27.0
CURF-Scratch
40.4
30.6
31.4
36.2
30.4
Table 6: Multi-norm certified accuracy (%) on CIFAR100 dataset.
Robustness against geometric transformations on CIFAR-10. T the certified robustness against geometric transformations CIFAR-10. CURE outperforms the single-norm baselines with significant margins. Also, we notice that CURE-Scratch improves CURE-Max, which indicates the effectiveness of bound alignment and gradient projection.
CURE compares to models trained to be robust against geometric perturbations. To evaluate whether geometric robustness generalizes to multi-norm robustness, we conducted additional experiments
CIFAR-10 using (Eoo 2/255, e2 0.25, 61 0.5). We tested models trained with various geometric
R(5), (2)))))(
Configs
R(30) T2(2), C(5).B(0.01) C(2).
Avg
1oo
54.6
20.9
82.5
95.6 63.4
1
0.0
0.0
0.0
0.0 0.0
CURE-Joint
55.9
21.3
82.3
95.7 63.8
CURE-Mar 50.1
20.7
80.2
94.8 61.5
CURF-Randon 54.8
18.8
83.5
95.6 63.2
CURE-Scratch 51.0
24.3
85.5
95.1 64.0
Table 7: Comparison on CURE against geometric transformations for MNIST (e = 1.0, 0.3) experiment. CURE improves the generalized certified robustness significantly compared with single norm training.
20

---

Published in Transactions on Machine Learning Research (March/200)
CURE-scratch
30
Union Certified Robusiness
20
10
0.5
1.0
1.5
2.0
2.5
3.0
11 Eps
Figure 7: Ls, l2 and CURE-scratch trained on CIFAR-10 union certified robustness analysis with varying l epsilons.
transformations, including rotation R(p), translation Tu (Au),, T, (Av), scaling Sc(A), shearing Sh(n), contrast. C(a), and brightness B(3), where the values denote the perturbation magnitudes (e.g.. R(10) applies up to 110 rotation). As shown in the table below, models trained with geometric perturbations Yang et al. 2202 achieve substantially lower union certified accuracy (c.g., 21.5%) compared our CURE model (61.2%) This indicates that geometric robustness alone does not transfer well to multi-norm robustness, while approach offers strong generalization across diverse norm-bounded threats.
Method
to0
l2
Union
CGT: R(10) CGT: R(2), Sh(2)
1.6 22.8 38.0
1.6
32.2 22.8 38.0
18.1
CGT: Sc(1), R(1), C(1), B(0.001)
33.2 22.8 38.0
21.5
Ours
61.2 67.7 74.6 61.2
Table 8: Comparison of CGT
Yang et al. 2022 versus our CURE model on CIEAR-10.
Comparing bound overlap across models. In Table
compare single-norm and multi-norm trained models in terms of their bound overlap with CGT models. For fairness, we compute the maximum overlap across each batch and normalize the bound outputs. The results show that CURE-Scratch achieves substan- tially higher overlap than the too certified baseline, highlighting its stronger alignment and generalization across perturbation types.
1oo la and CURE-scratch trained on CIFAR-10 (cx 8/255, c2 = 0.5, 6 = 1.0) union certified robustness analysis with varying locs l2, and Ii epsilons. We evaluate the certified robustness of our trained l0, l2, and CURE-Scratch models across range of perturbation sizes under 4, l2, and loo norms. This comprehensive evaluation reveals that CURF-Scratch consistently outperforms the single-norm trained models across all tested settings. The results highlight the effectiveness of our approach in achieving strong multi-norm certified robustness. demonstrating that CURF-Scratch not only generalizes better across different. norms but also maintains superior certification performance under varying attack strengths.
The overlapping of Lx and balls. A reasonable misconception is that because Lo and ly balls contain overlap, training for robustness in one will sufficiently account. for the weakness in the other.
21

---

Published in Transactions on Machine Learning Research Mllrch/20200
Linf L2
CURE-acratch
30
Union Certfied Robustness
10
0.25
0.50
0.75
1.00
1.50
Eps
Figure 8: lxo, and CURE-scratch trained on CIFAR-10 union certified robustness analysis with varying l2 epsilons.
Linf L2
CURE-scratch
30
Union Certified Robusthess
10
2/255
4/255
8/255
12/255
16/255
linf
Figure 9: loo, l2 and CURE-scratch trained CIFAR-10 union certified robustness analysis with varying lx epsilons.
22

---

Published in Transactions on Machine Learning Research March/2026)
R(10) R(2), Sh(2) Se(1), R(1), C(1), B(0.001)
Linf
0.141
0.723
0.791
CURE-Scratch 0.277
0.789
0.892
Table 9: Comparison of multi-norm (CURE-Scratch) versus single-norm certified trained models on the bound overlap with the CGT model.
Besides choices of lee and la that completely overlap each other, the true regions successful attacks have a significant. mismatch across different norms.
To illustrate the mismatch between Lo and le regions, it suffices to show the existence of successful attacks that lie further enough from the original data input such that they are not covered by the other norm ball. We ran PGD 19968 times through a full testing run of naturally trained model in the MNIST setting (<xo = 0.1, = 0.5) with the following results:
% of lo attacks not in &e ball % of & atlacks not in foo ball
100.00% (9984/9984)
98.95% (9879/9988)
Table 10: Comparison of foo and & attack coverage.
Of course, PGD may not find the absolute strongest adversarial examples in each ball. That only makes the mismatch claim stronger, because if PGD can find adversarial examples outside the other norm's 's ball, more attacks almost certainly exist in those regions as well.
Comparison of 12 certified training and PGD training. Table 11 shows the la certified robustness comparison between certified training and PGD training. The results demonstrate that determiiist-corttifeed training greatly improves the certified robustness.
12 certified robustness MNIST- large CIFAR- CIFAR- large
Certified training
94.5
71.2
56.6
PGD training
74.3
23.3
10.2
Table 11: Comparison on la certified robustness between certified and PGD training.
Comparison on empirical robustness on SST-2 using BERT model. Moreover, our advances in certified robust also translate into strong empirical robustness on transformer-basel language models. As shown in Table [2] when applied to BERT model on the SST-2 dataset, CURE-SCRATCH consistently outperforms FLAT (Chen & Ji 2022 state-of-the-art empirical adversarial training method, under both PWWS and Fooler attacks. This result is particularly notable because CURF is designed around certified objectives rather than direct optimization against empirical attacks, yet it achieves substantially higher empirical robustness. These findings further indicate that our approach is not a straightforward or trivial adaptation of adversarial training techniques, but instead introduces optimization principles that generalize beyond the certified setting.
Hyper-parameter a for Joint certified training. As shown in Table 13 we test the changing of loo, l2, and union accuracy with different values in [0, 0.25, 0.5, 0.75, 1.0] on MNIST (Exo 0.1, 0.5) experiments. We observe that a 0.5 has the best union accuracy and is generally good choice for our experiments by balancing the two losses.
Comparison of l2 certified robustness on la deterministic certified training methods. In Table 14 we compare our proposed 12 certified defense with SOTA l2 certified defense Hu et al. (2023) on CIFAR-10 with e2 0.25 and 0.5. Hu al. (2023)'s model is Lipchitz model and thus can report the certified robust accuracy directly after forward pass, whereas CURE requires external certification procedure. The results
23

---

Published in Transactions on Machine Learning Research MMrchh2022
Table 12: Empirical robustness (%) on SST-2 for a BERT model under text attacks.
Robust Accuracy FLAT CCen & Ji 2022)
CURE-Scratch
SST-2 (PWWS) SST-2 (TextFooler)
14.6
28.4
12.4
17.6
0.0
0.5 0.75
1.0
Clean
99.2 99.2 99.3 99.2 99.5
1.0
97.7 97.7 97.597.2 2.0
l2
96.9 95.6 97.4 95.9 98.7
Union 96.9 95.6 97.1 95.8 2.0
Table 13: Ablation study on Joint training saper-parameter a.
show that proposed l2 deterministic certified training method improves over robustness by 2 4% compared with the SOTA method.
C2
0.25 0.5
Hu et al. (0023
69.5
52.2
Ours
71.2 56.6
Table 14: Comparison of la certified accuracy; our proposed 12 certified training consistently outperforms Hu
et al. 20223 by 4%.
More visualizations on bound differences. We plot the bound difference examples from alpha-beta-crown on MNIST, CIFAR-10, and Tinylmagenet datasets, where the negative bound differences are colored in red. As shown in Figure TO bound differences against loc and l2 perturbations colored in blue and green, respectively. CURE-Scratch produces all positive bound differences, leading unionly robust predictions; CURE-Max is not unionly robust due to some negative bound differences. Also, we observe that CURE-Scratel successfully brings l,, bound difference distributions close to each other compared with CURE-Max in many cases, which confirms the effectiveness of our bound alignment technique.
12 we compare CURF-Scratch (second row) with CURE-Max (first row), with
Linf CURE-Max
L2 CURE-Max
Linf CURE-Max
L2 CURE-Max
Bound Difference
Bound Differences
Bound Differences
15
Bound Differences
4
10
10.
2
0
2.5
5.0
2.5
5.0
7.5
2.5
5.0
7.5
2.5
5.0 Classes
7.5
Classes
Classes
Classes
Linf CURE-Scratch
L2 CURE-Scratch
Linf CURE-Scratch
L2 CURE-Scratch
Bound Differences
Bound Differences
6
Bound Differences
10
Differences
21
2.5
5.0
7.5
0.0
2.5
5.0
7.5
0.0
2.5
5.0
7.5
0.0
2.5
5.0
7.5
Classes
Classes
Classes
Classes
Figure 10: Bound difference visualizations on MNIST (Exo = 0.3, 1.0) experiments.
24

---

Published in Transactions on Machine Learning Research March/2024
Linf CURE-Maz Max
L2 CURE-Max
Linf CURE-Max
L2 CURE-Max
Bound Difference
Bound Differences
Bound Difference 65
7.5
Bound Difference es
4
2
2.5
0.0
0.0
2.5
5.0
7.5
0.0
2.5
5.0
7.5
2.5
5.0
7.5
2.5
5.0 Classes
7.5
Classes
Classes
Classes
Linf CURE-Scratch
L2 CURE-Scratch
Linf CURE-Scratch
L2 CURE-Scratch
Bound Differences
Bound Differences
Bound Differences
10
Bound Differences
10
5-
5-
2
0.0
2.5
5.0
7.5
0.0
2.5
5.0
7.5
0.0
2.5
5.0
7.5
0.0
2.5
5.0 Classes
7.5
Classes
Classes
Classes
Figure 11: Bound difference visnalizations on CIFAR-10 10 (Eoo
2
= 0.25) experiments.
255
Linf CURE-Max
L2 CURE-Max
Linf CURE-Max
L2 CURE-Max
Bound Differences
Bound Differences
2.
Bound Differences
2.
Bound Differences
2-
0-
1
0.0
2.5
5.0
7.5
0.0
2.5
5.0
7.5
0.0
2.5
5.0
7.5
0.0
2.5
5.0
7.5
Linf CURE-Scratch
L2 CURE-Scratch
Linf CURE-Scratch
L2 CURE-Scratch
Bound Differences
Bound Differences
Bound Differences
Differences
2
2-
2
1-
7.
0.0
2.5
5.0
7.5
0.0
2.5
5.0
7.5
0.0
2.5
5.0
7.5
0.0
2.5
5.0
7.5
Figure 12: Bound difference visualizations on CIFAR-10 (fx
8
<2 = 0.5) experiments.
255
D Runtime Analysis
This section provides the runtime per training epoch for all methods MNIST (ex = 0.1, 0.75) experiments and runtime per training epoch of CURE-Scratch with ablation studies on GP for MNIST, CIFAR10, and Imagentte experiments. We evaluate all the methods on single A40 Nvidia GPU with 40GB memory and the runtime is reported in seconds (s).
Runtime for different methods on MNIST experiments. In Table 15 we show the time in scconds (s) per training epoch for single norm training (1x and 12), CURE-Joint, CURE-Max, CURE-Random, CURE-Scratch, and CURE-Finetur methods. CURE-Fineture has relatively small 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 SeaB--Seratch/Finttuu
Runtime for CURE-Scratch on MNIST, CIFAR10, and Iiny-magenet datasets. In Table 16 we show the runtime per training epoch using CURE-Scratch on MNIST, CIFARI0, 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.
25

---

Published in Transactions on Machine Learning Research MMrchh2028
Methods
Runtime (s)
loc
89
82
CURE-Joint
155
CURE-Max
147
CURE-Random
101
CURF-Finetune
148
CURE-Scratch
153
Table 15: Runtime for all methods on MNIST (exo - 0.1, 62 0.5) experiment per epoch in seconds.
MNIST CIFAR-10 TinyImagani
w/o GP
148
390
952
with GP
154
414
1036
Table 16: Runtime for CURE-Scratch on MNIST, CIFAR1O, and Tinylmagenet datasets.
E
Algorithms
In this section, we present the algorithms of CURE framework. Algorithm [ fillustrates how to get propagation region for both and Loo perturbations. Algorithm CURE-Random, and CURE-Seratch/ SaarratchhFineetueee FFinetune, respectively. Algorithm 0 is the procedure of performing GP after epoch of natural and certified training (could be any of Algorithm
refer to algorithms of CURE--oint, CURE-Max,
Algorithm gel propagation region for Loo and la perturbations
Require: Neural network f. imput æ, label t, perturbation radius c, subselection ratio X, step size step number n, attack types E {1so, 12)
Ensure: Center x' and radius t of propagation region B (a')
(x. Ø) f- clamp((x - 6, 1x0+e7 -,,,),
// Get bounds of input region
+ X/2- (τ x))
// Compute propagation region size 7
z + Uniform (z.
// Sample PGD initialization
for 0.....
do
// Do PGD steps
if allack = 1xc then
Find examples with Lx gradient direction
- + x; + a sign ((=((())))) -ー + clamp(x)41 2, end
if attack = lz then
// Find examples with la gradient direction
(cE((()))))
_ + xf + VV (c)((()))))ll
8
(w x)
x . =
- clamp( x.
end if end for x' +- clamp(x; x + T,æ T)
// Ensure that (T(x') will lie fully in (x)
return x't,T
26

---

Published in Transactions on Machine Learning Research (March /202))
Algorithm CURE-Joint Training Epoch
Require: Neural network fa, training set (x, T), perturbation radius e2 and 6co: subselection ratio Xso and 22, learning rate 17, & regularization weight L,, loss balance factor a // Sample batches (X,T) (axx0 Too) f get pttppppptooo_roeeeeee region (attack = (/0))/// Refer to Algorithm [
for (x, = (zo, to) (æs, do
(#2g, 72) ) t get propagation region (atlack = 12) // Get box with midpoint x' 2/2 and radius Too 72
T (x'²)) t Box Too)
t (a%) - Box T2)
wwtuuupprboouud(ce BT (x'=a)
// Get upper bound uya un on logit differences
2 + get uuppe_bound(ffe. 8 (axh)
// based on IBP
losst_ + (cr("
losst, t foE(urg:t)
losse, t t get fi nfo
losStot + (1 a)
lossi + los81, + losse,
0 Volosstot
1/ Update model parameters 0
end for
Algorithm CURE-Max Training Epoch
Require: Neural network fe, training set (X, T), perturbation radius 62 and 6co; subselection ratio Aoo and X2, learning rate 77, & regularization weight l
for (x, f) = (æo, to) ... ts) do
// Sample batches (X,T)
(x'os Too) + get_ wwlppppgationrreggiieeae
(attack = 1/0) // Refer to Algorithm [
( (xg T2) t get wwwppaatiionneeeeeeeeepee
(attack = 12)
T (xxx) t Box Tox)
// Get box with midpoint x' x'2 and radius Too 72
Th (x/) + Box (ox(xx),72)
u [oe_upper_bouud( bound B (x'x))
// Get upper bound u u on logit differences
u - get_upper__ _uuuppr_bbouddfffo T (xb))
// based on IBP
loss + (cr("gg.t)
loss,, - Loe(u
lossMar max (loss) l08812)
// We select the largest [pe(2.00) loss for each sample
losse, + é get f (or
loss + loss + losse,
0 + Voloss
// Update model parameters 0
end for
27

---

Published in Transactions on Machine Learning Research (March /2026)
Algorithm CURE-Random Training Epoch
Require: Neural network fe, training (X,T), perturbation radius 62 and c subselection ratio Xso and X2, learning rate 77 &, regularization weight L for (x,t) (æo, to) (as,tt) tb) do
Sample batches (X,T)
(2), (11, (2) +- partition(2.
// Randomly partition inputs into two blocks
// Apply Algorithm ]
(x Too) - get ptt_ppooottoooregggggee (æ1, f1, attack = (20)
(0/) T2) + get pwwpppagaioonreeeeeeeee (I2, t2, attack = 12)
T (xxx)) Box oo Toc)
// Get box with midpoint x a22 and radius Too 72
T (a/2) Box 72)
u get_ ci__uuprrbbouddffe BT~ (x'x))
// Get upper bound uy un logit differences
u get cot__uppr_bbuuudd_e bou_dooudeeeee T (x²))
// based on IBP
loss + Lc
loss t fCE(U, (3))))
losst, t l get & norm(fo)
lossrot t loss1 - losst, + losse,
f 9+6 Volosstot
// Update model paramcters
end for
Algorithm CURE- SUURE-Scratch//ineete Training Epoch
Require: Neural network fe, training set X)T,, perturbation radius e2 and 660; subselection ratio Aoo and X2, learning rate 77, é, regularization weight e,, KL loss balance factor 7), mode E |Scratch, Finetune] for (z, (æo, to) ... (wr, do
// Sample batches (X,T)
(x' Too) get pwwppaptoponnnnmoom.p.ppa.pp..ep region (attack = (20) // Refer to Algorithml
(ah, 72) + gel propagation region (attack 12) // Get box with midpoint x'co xy and radius Too
Th (x<c) + (oox(='o,TTo))
T (x²) + Box(a1,, T2)
u + get_upper_ Sropper_boundffer (fe. BT (x'x))
// Get upper bound una u on logit differences
u + _uppr_ppr____ cas_uupp_bbbumeee upperrbbuudd(ff. fo, T (ar)))
// based on IBP
lossi_ + (cr(uuz,1)
losst, + LcE(u,,,t)
lossMar + max (losso lossi,)
1/ We select the largest (pe(2,00) loss for each sample
get losse, get L1 li
norm([o)
find correctly certified bg subset using Definition 4.3
IoSS +- (L((d(iillddrr)))
Eq.
5
loss +- Loss + loss + losse,
f +- f Volosstot
// Update model parameters 0
end for
28

---

Published in Transactions on Machine Learning Research (March /2026)
Algorithm GP: Connect CT with NT
1: Input: model fe, input images with distribution D, training rounds R, 8, natural training NT and certified training CT algorithms, perturbation radius 6oc and E2, subselection ratio Axo and X2, learning rate f) & regularization weight 4
2:
for 1,2,... R do 4: fn + N D)
fo CT( Eoo, E2, Aoc Λ2, 22,7,111 1,, ()
// Can be single-norn or any CURE training
6: compute In + Jn (r)
Dc t Se (()
7: compute 9p using Eq. 10
update f(r+1) using Eq. with 3 and ge
end for
10: Output: model fa-
29


Reviews:
[{"review_id": "Iv02aIQtBm", "reviewer": "Reviewer_rrbD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a deterministic certified training framework, CURE (Certified training for Union RobustnEss), to address the limitation that existing certified robustness methods are typically designed for a single ℓp norm and suffer from significant robustness trade-offs across different norms. The authors first develop a formal theoretical framework under the binary classification setting, where the union risk is decomposed into a single-norm robust error and an alignment error, revealing the intrinsic conflict underlying multi-norm certified robustness. Based on this analysis, the paper introduces three baseline multi-norm certified training strategies (CURE-Joint, CURE-Max, and CURE-Random), and further derives an upper bound that motivates several key techniques, including bound alignment, gradient projection that integrates natural and certified training, and a fast certified fine-tuning strategy. Experimental results demonstrate improved union certified accuracy as well as enhanced robustness to unseen geometric and patch perturbations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Strengths\n\n1.The paper clearly identifies the failure of single-norm certified models to generalize across different ℓp threat models, and convincingly motivates the need for multi-norm certified robustness.\n\n2.Rather than relying on purely empirical observations, the authors develop a formal risk decomposition and upper-bound analysis that exposes the underlying source of multi-norm robustness trade-offs, and these insights are directly reflected in the proposed training \nobjectives.\n\n3.Beyond reporting union certified accuracy, the paper evaluates robustness under a diverse set of geometric transformations and patch attacks, providing strong empirical support for the claim that multi-norm certified training improves generalized certified robustness.", "audience_yn": "Yes", "audience_explanation": "Weaknesses\n\n1.All experiments are conducted on a relatively shallow CNN architecture. While common in certified training literature, the lack of validation on deeper or more modern architectures limits the assessment of scalability.\n\n2.Although the proposed framework improves over baselines on harder datasets, the absolute certified accuracy remains low, which may limit its practical applicability in real-world scenarios.\n\n3.While the paper claims that the binary analysis can be naturally extended to the multi-class case, the main text does not provide a complete multi-class theoretical derivation and instead relies on existing results on classification-calibrated losses, which weakens the overall theoretical rigor.\n\n4.The method assumes that natural training gradients with positive cosine similarity to certified gradients are inherently beneficial, but this assumption is not supported by a rigorous theoretical justification.", "requested_changes": "Questions\n\n1.The gradient projection step discards all components with non-positive cosine similarity. Could this hard threshold remove potentially useful information that points in a different but complementary direction?\n\n2.The current framework mainly focuses on the union of ℓ2 and ℓ∞ threat models. How easily can the proposed approach be extended to ℓ1 or other ℓp norms?\n\n3.Since natural training gradients primarily aim to improve standard accuracy, while certified training often trades off clean accuracy for robustness, why does projecting certified gradients toward natural gradients improve certified robustness rather than merely clean performance?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QsTl1CukKl", "reviewer": "Reviewer_1ugF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Although this paper is innovative in the direction of multi-norm certification training and demonstrates effective results on multiple benchmarks, the current version has significant shortcomings in theoretical depth, experimental completeness, and methodological transparency, and its innovation does not meet the journal's requirements.", "claims_and_evidence_yn": "No", "claims_explanation": "1. Although the Bound Alignment technique is introduced in this paper, its core is to align two distributions using KL divergence. The theoretical section fails to clearly explain why the proposed Bound Alignment effectively alleviates the trade-off between different norms, lacking a theoretical explanation or visual analysis of the mechanism.\n\n2. The paper primarily compares with single-norm authentication methods, but does not adequately compare with existing multi-norm adversarial training methods such as TRADES, especially regarding authentication robustness.\n\n3. Regarding the improvement in generalization performance against geometric and block attacks, there is a lack of systematic comparison with authentication methods specifically targeting these attacks.\n\n4. The l∞ box approximation method used in l2 certification training does not adequately discuss the potential over-approximation error and its impact on the final results.", "audience_yn": "No", "audience_explanation": "1. The core method of this paper essentially combines the loss functions of single-norm authentication training methods. This multi-task learning or loss weighting approach has been widely explored in adversarial training. Applying it to authentication training can be seen as a natural and expected extension, rather than a conceptual breakthrough.\n\n2. Only a small dataset and a simple CNN architecture were used; the scalability of the method was not verified on larger datasets or more complex models.\n\n3. The paper contains numerous grammatical errors and unclear sentences, affecting readability. Tables such as Figures 5 and 6 lack sufficient explanation, making it difficult for readers to understand their connection to the core arguments.", "requested_changes": "N/A", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "deAFMTTYaF", "reviewer": "Reviewer_SLcB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes CURE, the first deterministic framework for multi-norm certified robustness. The authors (1) establish a theoretical analysis explaining tradeoffs between $\\ell_p$ certified perturbations, (2) introduce three base training strategies, (3) develop Bound Alignment to reduce cross-norm inconsistencies by aligning certified bound differences, (4) incorporate Gradient Projection to integrate beneficial natural training signals into certified training, and (5) design an efficient certified fine-tuning method for adapting single-norm certified models to multi-norm settings. Experiments on MNIST, CIFAR-10, and TinyImageNet demonstrate significant improvements in union-certified accuracy and better generalization to geometric and patch perturbations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper is technically sound, with rigorous mathematical formulations and proofs provided for key theorems that underpin the main claims.  The authors provide sufficient evidence, including extensive experiments and ablation studies, to support the effectiveness of their proposed method.", "audience_yn": "Yes", "audience_explanation": "The findings of this paper are likely to be of interest to the safety and robustness community.", "requested_changes": "1. The proposed method is not entirely grounded in certified robustness. Components such as CURE-Joint and Gradient Projection can be applied (might have been applied) in adversarial training settings. The only component that is tied to certified robustness is Bound Alignment; however, a variant of this idea might also be adapted to adversarial training by replacing certified bounds with logits.\n\n2. The paper does not explicitly align the $\\ell_1$ norm, yet still reports robustness against $\\ell_1$ attacks. This raises a natural question: could we explicitly align $\\ell_1$, $\\ell_2$, and $\\ell_\\infty$ during training? If so, should the alignment be performed using pairwise matching between every pair of norms, or by selecting an anchor norm $\\ell_p$ and aligning all other $\\ell_q$ norms to this reference?\n\n3. It would be helpful to understand the performance under $\\ell_0$ perturbations and on Vision Transformers (ViTs).", "broader_impact_concerns": "None", "additional_comments": "None", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)