Unlocking Deterministic Robustness Certification on ImageNet
Authors: Kai Hu
Andy Zou
Zifan Wang
Klas Leino
Matt Fredrikson
Venue: NeurIPS 2023 poster (2023)
Keywords: adversarial robustness
ImageNet
Lipschitz-based certification
ResNet
adversarial examples
ML security
TL;DR: We introduce a novel residual network architecture, LiResNet, and EMMA loss to facilitate it for scaling up deterministic robustness certification to ImageNet-scale datasets.

Abstract: Despite the promise of Lipschitz-based methods for provably-robust deep learning with deterministic guarantees, current state-of-the-art results are limited to feed-forward Convolutional Networks (ConvNets) on low-dimensional data, such as CIFAR-10. 
This paper investigates strategies for expanding certifiably robust training to larger, deeper models.
A key challenge in certifying deep networks is efficient calculation of the Lipschitz bound for residual blocks found in ResNet and ViT architectures.
We show that fast ways of bounding the Lipschitz constant for conventional ResNets are loose, and show how to address this by designing a new residual block, leading to the *Linear ResNet* (LiResNet) architecture.
We then introduce *Efficient Margin MAximization* (EMMA), a loss function that stabilizes robust training by penalizing worst-case adversarial examples from multiple classes simultaneously.
Together, these contributions yield new *state-of-the-art* robust accuracy on CIFAR-10/100 and Tiny-ImageNet under $\ell_2$ perturbations.
Moreover, for the first time, we are able to scale up fast deterministic robustness guarantees to ImageNet, demonstrating that this approach to robust learning can be applied to real-world applications.

Unlocking Deterministic Robustness Certification on ImageNet
Kai Hu
Andy Zou Carnegie Mellon University Pittsburgh, PA 15213 andyzou@cmu edu
Carnegie Mellon University Pittsburgh, PA 15213 kaihu@andrew cmu. edu
Zifan Wang
Klas Leino
Matt Fredrikson
Center for AI Safety San Francisco, CA 94111
Carnegie Mellon University Pittsburgh, PA 15213 kleino@cs.. cmu. edu
Carnegie Mellon University Pittsburgh, PA 15213 mfredrik0cs cmu edu
zifan0safe.. ai
Abstract
Despite the promise of Lipschitz-basedd methods for provably-robust deep learning with deterministic guarantees, current state-of-the-art results are limited to feed- forward Convolutional Networks (ConvNets) low-dimensional data, such CIFAR-10. This paper investigates strategies for expanding certifiably robust training larger, deeper models. A key challenge in certifying deep networks is efficient calculation of the Lipschitz bound for residual blocks found in ResNet and VIT architectures. We show that fast ways of bounding the Lipschitz constant for conventional ResNets are loose, and show how to address this by designing a new residual block, leading to the Linear ResNer (LiResNet) architecture. We then introduce Efficient Margin MAximization (EMMA), loss function that stabilizes robust training by penalizing worst-case adversarial examples from multiple classes simultaneously. Together, these contributions yield new sfate-of-the- thre-arr robust accuracy on CIFAR- 10/100 and Tiny-ImageNet under & perturbations. Moreover, for the first time, we are able to scale up fast deterministic robustness guarantees ImageNet, demonstrating that this approach to robust learning can applied real-world applications. Our code is publicly available GitHub!"
1 Introduction
Deep neural networks have been shown to be vulnerable well-crafted tiny perturbations, also known as adversarial examples [19]45] 45). Methods for achieving provably-robust inference-thar is, predictions that are guaranteed be consistent within corm-bounded e-ball around an input-are desirable in adversarial settings, as they offer guarantees that hold up against arbitrary perturbations. Thus, The focus of this paper is to train network that can certify its predictions within an e-ball.
Over the last few years, a wide body of literature addressing robustness certification has emerged 6 33
18 24 26
46 48 52.. To date, the methods that achieve the best certified performance are derived from randomized smoothing (RS) [6]; however, this approach has two main draw bbcks. First, it provides only probabilistic guarantee, which may generate false positive claim around 0.1% of the time [6]: by contrast, deterministic certification may be preferred in safety-critical applications, e.g., malware detection and autonomous driving. Additionally, RS requires significant
29
32
43
Cooee available httt::///gthaub.cc///uka////////
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

computational overhead for both evaluation and certification this limitation is severe enough that RS methods are typically evaluated on % subset of the ImageNet validation set for timing concerns.
38
Because of the highly non-linear boundaries learned by a neural network, deterministically certifying the robustness of its predictions usu- ally requires specialized training procedures that regularize the network for efficient certification, as post-hoc certification is either too expen- sive 127 44 or too imprecise [8], particularly as the scale of the model being certified grows.
VR4 (%)
34
BCOP
30
Cayley
SOC
LiResNet (Ours)
16
28
34
The most promising such approaches-inn terms of both certified accuracy and efficiency- perform certification using Lipschitz bounds. For this to work, the learning procedure must impose Lipschitz constraints during training, ei- ther through regularization (32) or orthogonal- ization [ 48.. While Lipschitz- ipschitz-based based certifi- cation is efficient enough to perform robustness certification scale (e.g., on ImageNet) prin- ciple, it imposes strict regularization that makes training large models difficult, especially as it challenging to maintain tight Lipschitz bounds for very deep models. As a result, state-of-the-art (deterministically) certified robustness is currently still achieved using relatively small feed-forward Convolutional Networks (ConvNets). At the same time, recent work has suggested that robust learning requires additional network capacity 4 30), leaving the plausibility of deterministic certification for realistic applications using small ConvNet architectures in question.
Number Layers
Figure Plot of VRA-the
the % of points where the model is both correct and certifiably robust-
against the depth of the model. We compare our proposed architecture with BCOP [33, SOC [43
and Cayley layers [48] on CIFAR-100, finding our architecture scales more favorably to deeper nets.
See Appendix [B for plot implementation details.
The goal of this work is to scale up certifiable robustness training from ConvNets to larger, deeper architectures, with the aim of achieving higher Verifiable Robust Accuracy (VRA) the percentage of points on which the model is both correct and certifiably robust. By realizing gains from more powerful architectures, we show it is possible to obtain non-trivial certified robustness on larger datasets like ImageNet, which, to our knowledge, has not yet been achieved by deterministic methods. GloRo Nets (32). leading certified training
Our results stem chiefly from two key innovations approach First, we find that the residual branches used in conventional ResNet and ViT architectures might not be good fit for Lipschitz-basee based certification; instead, we find the key ingredient is to use linear residual path (Figure 2ah forming what we refer to as a LiResNer block. The motivation for this architecture development iS covered in depth in Section 3
Second, we find that the typical loss function used by GloRo Nets the literature may be suboptimal at pushing the decision boundary far away from the input in learning settings with large numbers of classes. Specifically, the standard GloRo loss penalizes possible adversarial examples from a single class at once (corresponding to the closest adversarial example), while we find robust model can be more efficiently obtained by regularizing against adversarial examples from all possible classes at once, particularly when there are many classes. We thus propose Efficient Margin MAximizatiin (EMMA) loss for GloRo Nets, which simultancously handles possible adversarial examples from any class. More details on the construction and motivation behind EMMA loss are provided in Section 4
Using the LiResNet architecture and EMMA loss, we are able to (1) scale up deterministic robustness guarantees to ImageNet for the first time, and (2) substantially improve VRA on the benchmark datasets used in prior work. In particular, as examplified in Figure [ in contrast to the existing architectures that achieve no gains in VRA when going deeper, LiResNet demonstrates an effective use of the increasing capacity to learn more robust functions.
We choose GloRo Nets in particular because they involve the least run- au-tiime and memory overhead compared other leading certification methods, e.g., orthogonalization.

---

To summarize our contributions: (1) we introduce LiResNet, a ResNet architecture using a linear residual branch that better fits the Lipschitz-bars based certification approach for training very deep networks; and (2) we propose EMMA loss to improve the training dynamics of robust learning with GloRo Nets. a result, we achieve the new state-of-the-art VRAs on CIFAR-10 (70.1%), CIFAR- 100 (41.5%), Tiny-ImageNet (33.6%) and ImageNet (35.0%) for moonddbounded perturbations with radius e = 36/255. More importantly, to the best of our knowledge, for the first time we are able to scale up deterministic robustness guarantee ImageNet, demonstrating the promise, facilitated by our architecture, of obtaining certifiably robust models in real-world applications.
2 Background
We are interested in certifying the predictions of a network F(x) arg max; (1r) that classifies an input x E Ied into m classes. We use the uppercase F(x:) Rd - [m]] to denote the predicted class and the lowercase f(xx) R2 + IR" for the logits. A certifier checks for whether e-local robustness (Definition[]) ( holds for an input æ.
Definition (e-Local Robustness). A network F(z) is e-locally robust at an imput æ w.r.t norm, Va' Rd || =1| S = F(x') F(x)).
|| ||+
Existing certifiers are either probabilistic (i.e., guaranteeing robustness with bounded uncertainty) or deterministic (i.e., returning a certificate when a point is guaranteed to be robust). We focus on the latter in this paper and consider the l norm if not otherwise noted.
I Lipschitz-based Certification. Certifying the robustness of prediction can be achieved by check- ing if the margin between the logit of the predicted class and the others is large enough that no other class will surpass the predicted class on any neighboring point in the e-ball. To this end, many prior works rely on calculating the Lipschitz Constant K (Definition 2 the model to bound the requisite margin.
Definition 2 (K-Lipschitz Function). A function h : Rd R" is K--Lischitzz w.r.t S C R and norm, || 1l. if Vx, x' E (. h(=')ll S K
| [ 100-21p z'|1.
Here, K is the maximum change of a function's output for changing the input S. Notice that is sufficient to use a local Lipschitz Constant Klocal of the model, i.e., S = {x' I| - x|| S <) in Definition 2 to certify robustness (55). However, a local bound often computationally expensive and may need bounded activation in training [24 Alternatively, one compute global Lipschitz Constant Kgiobal. i.c. S = Rd in Definition and leverage the relation Kglobal 2 Kiocal to certify any input at any radius e. A global bound is more efficient at test time for certification because it only needs to be computed once and can be used for any input at any e However, an arbitrary global bound can be vacuously large and thus not useful for positive certification.
GloRo Nets. Among leading approaches that tighten the global Lipschitz constant during training for the purpose of certification 42 43 (48), GloRo, proposed by Leino et al. [32], is unique in that it naturally incorporates Lipsehitz regularization into its loss rather than imposing direct constraints on the Lipschitz constant of each layer. As a result, it is more resource- -fficcceen,, and thus has the best potential to scale up to large-scale networks with high-ddmensional inputs. GloRo computes the global Lipschitz constant, Kj of the logit margin between the predicted class, j, and every other class, by taking the product of the Lipschitz constant of each constituent layer. Next, suppose the Lipschitz. constant of the model until the penultimate layer is K;-1, and use we as the hd column of the top layer's weight matrix; then GloRo computes a logit score fi of an artificial class, which we will refer to as I.
f (1 max((() + +e eKai) where K5= = ||wr will K.-1-
(1)
*#
Then, the so-called GloRo Net outputs F(x) = j when (x) (x), or F(x) 1 otherwise.
Thus, by design, whenever the GloRo Net does not output 1, its prediction is guaranteed to be robust.
Furthermore, when the network is trained for certification with the global bound, the global bound has the same certification potential as the local bound 32
3

---

LiResNet
Stem
Conv & MinMax
Inconsistency of the Threatening Class
80
Tiny-Imagenet (200 classes)
70
CIFAR-100
(100 classes)
Backbone
60
CIFAR-10
(10 classes)
50
MinMax
40
x L
30
Neck
Affine Flatten
20
Head
Dense w/ LLN
Training Epoch
(b)
Figure 2: (a) An illustration of the LiResNet Architecture. (b) Plot of the percentage of instances each epoch during training for which the threatening class (the one with the second-highest logit value) differs compared to the previous epoch (on the same instance). Numbers are reported on three datasets with 10, 100, and 200 classes using GloRo LiResNet with GloRo TRADES loss.
Robustness Needs More Capacity. Despite the fact that robust and correct predictions, i.e., VRA=100% is achievable for many standard datasets (55), the state-of-the the-hhhartt art VRAs (which are achieved using Lipschitz-
certification) are far away from realizing this goal. Recent works have emphasized the role of network capacity in learning robust classifiers, suggesting lack of capacity may factor in this shorteoming, beyond the more obvious fact that Lipschitz--bsed certification is conservative and may falsely flag robust points. Bubeck and Sellke 4 showed that a smooth (and thus robust) decision boundary requires times more parameters than learning non-smooth one, where d is the ambient data dimension. In addition, to rightly certify robust boundary with Lipschitz-ban approaches, Leino (30) demonstrated the need for extra capacity to learn smooth level curves around the decision boundary, which are shown to be necessary for tight certification.
Robust Residual Blocks. Prior work 22 has introduced residual connections, which have proven effective for scaling network depth. Residual connections have since become of the building blocks for Transformer networks (51). High-capacity ResNets and Vision Transformers (ViT) [14] outperform basic ConvNets in terms of clean accuracy (i.e., ignoring robustness) on major research datasets, but similar success has not been observed for VRAs. For example, several papers find
ResNets have lower VRAs CIFAR-10 compared ConvNets 42 48
while no paper has reported
VRAs on common vision datasets with ViTs. These empirical findings are seemingly at odds with the capacity arguments raised in the literature, however this may be due unfavorable training dynamics of current approaches. This work aims to investigate the reasons behind this discrepancy to capture the potential of residual connections. Our primary focus the residual connection (to skip convolutions) in ResNets; however, the implications of this work include paving the way for future work on certifying other types of residual connections, e.g. skipping attention in Transformers.
Linear-Residual Networks
The GloRo approach can easily adapted from a ConvNet architecture to a ResNet architecture by simply adjusting how the Lipschitz constant is computed where the residual and skip paths meet. Consider conventional residual block r(x) given by r(xr) = x + g(x),, where the residual branch, g. is a small feed forward network, typically with 2-3 convolutional/linerr layers paired with nonlinear activations. The Lipschitz constant, K,, of r(z), with respect the Lipschitz constant, Kg. of (a)) upper-bounded by K, < 1 Kg-

---

Thus, typical estimation of the residual block's Lipschitz constant is 1 + Kg. However, this is loose estimation. To see this, let u = arg m |r(=)]//[|=l and observe that the bound only tight if and r(u) point in the sume direction in the representation space. This is presumably unlikely to happen, as random vectors are almost orthogonal in high-dimensional space with high probability. Thus, using 1 + g as the Lipschitz constant of r(x) is unlikely to be tight even if K2 is tight.
The LiResNet Architecture As discussed, the standard residual block is fundamentally challeng- ing to obtain a tight Lipschitz bound on. Thus, we propose to use a Linear Residual Block:
Vinear (a) + Conv(z)
Since Tinear (ar) is still linear transformation of x. can easily compute the equivalent convolution which has the same output as Mlnnear (z.). For example, consider a convolution layer with W E (22k++ (2ko where (2kg + 1) is the kernel size and n is the number of channels and zero padding kn- The weights of the equivalent convolution are then W + A where Alka, kn, i, 1 for all i E (1, n and all other entries are set to zero. Thus, the Lipschitz constant of Tiinear can be efficiently estimated using the power method [16]. Nonlinearity of the network is then obtained by adding nonlinear activations (e.g., MinMax [I] to the outputs of each residual block. By stacking multiple linear residual blocks (with interjecting activations), and including stem, neck, and head, we obtain the Linear ResNet (LiResNet) architecture, illustrated in Figure 2a
A Note on the Power of LiResNet. It is worth noting that, despite the apparent simplicity of linear residual blocks, the LiResNet architecture is surprisingly powerful. First, although fiinar can be parameterized a single convolution, linear residual blocks are meaningfully different from convolutional layers. Specifically, linear residual blocks contain residual connections which facilitate better gradient propagation through the network. As an analogy, convolutional layers can be parameterized as dense layers that share certain weights (and zero others out), but convolutions provide meaningful regulation not captured in a standard dense layer. Similarly, linear residual blocks provide meaningful regularization that improves training dynamics, especially in deep models.
Second, while the linearity of linear residual blocks may seem to limit the expressiveness of the LiResNet architecture, this intuition is perhaps misleading. A useful analogy is to think of ResNet with fixed number of total layers, where we vary the number of layers per block. On one extreme end, all the layers are in single block, resulting in a simple CNN architecture. A typical ResNet has block size of 2 or 3; and, while adding more blocks imposes regularization that could reduce the model's 's expressiveness, this is not generally considered a disadvantage for ResNets, since the residual connections admit much deeper models, which ultimately makes up for any capacity that would be lost. LiResNets can be seen as the other extreme end, where each block has a single layer. While this entails further regularizaiton the same principle holds pertaining to the depth of the model.
A Note on Transformer- Architectures. Because Transformer-basee models also consist of many residual blocks, e.g., skip connections in the multi-head self-attention modules, we have experi- mented if the proposed linear residual block helps to certify Transformer- models. Our primary finding is, while the linear residual block tightens the Lipschitz constant of the skip connection, the attention module is another (bigger) bottleneck for certifying Transformers. Namely, self-attention is not a Lipschitz function (28], which is incompatible with Lipschitz-based certification approaches. Recent works 9 28 provide few Lipschitz-continen
alternatives for attention modules, none of which are found to have competitive certifiable robustness compared to LiResNets in our experiments. Thus, the evaluation part of this paper (Section 5) will mainly focus on comparing LiResNets with prior work, while our experiments with Transformer- based models will be included in Appendix ffor reference in future work.
4 Efficient Margin Maximization
Using the LiResNet architecture, we are able to train far deeper models. However, we observe that the GloRo cross-entropy loss (and the GloRo TRADES loss variant) used by Leino et al. [32, which we will refer to as standard GloRo loss, becomes inefficient as the number of classes the dataset increases. Standard GloRo loss minimizes the logit score of the 1. class (i.e. fi in Eq. which only affects one margin-namely the one between the predicted class and the threatening class (the one with the sccondhiighest logit value) at each iteration. To see this, we show in Figure
5

---

iteration t
iteration
Standard Gloro Training
Y1
Y/
1
logits=
V2..3
Gloro-EMMA Training
3/1
39
y/2
61 54
logits
Figure Comparison between the standard GloRo loss and our proposed GloRo EMMA loss (Definition 3). The standard GloRo loss constructs L class to push the nearest decision boundary away while EMMA adds the perturbations to all rest classes (i.e. considering class the ground truth) to efficiently push all boundaries away. Another difference is that EMMA uses the adaptive é; instead of in the training. At iteration + 1, the network using EMMA loss already robust while standard GloRo loss may take more iterations to become robust.
that the standard GloRo loss largely focuses on the decision boundary between classes and at iteration t, even though class 2 is also competitive but slightly less so than class 3. Furthermore, the possibilitty arises that the threatening class will alternate between competing classes leading to a sort of "whacc-a-molle" game during training.
Indeed, find this phenomenon be increasingly common the number of classes grows. Figure[b]showw shows the fraction of instances at each epoch for which the threatening class differs from in the preceding epoch. In the initial 100 epochs, more than 30% instances from Tiny-ImageNet (containing 200 classes) have different threatening classes at each each iteration, while the same number for CIFAR-10 is only about 10%. At best, this contributes making training with many classes less efficient, and at worst, it halts progress as work in one epoch is undone by the next.
To address this problem, propose new loss function known as the Efficient Margin Maximization (EMMA) loss (Definition 3 and we consequently refer to this method as GloRo (EMMA). Conceptu- ally, the EMMA loss function adds the maximum possible margin to each non-ground-truth class. This margin is defined as the maximum gain a given logit can achieve over the ground truth logit within the current largest b,-ball.
Formally, suppose Ji denotes the logit of class and Ky the margin Lipschitz between class and label defined in Equation We can express the radius of the current largest certifiable f -bll for a class relative to the ground-truth -uuth class as Kg, This value is determined by their logit margin over the Lipchitz constant of this margin, shown in Equation 2
fy(x) f((z) if i o and 0 otherwise.
Vi, (x))
Taking into account that the expected robust radius is formulate EMMA loss follows. Definition 3 (Efficient Margin MAximization (EMMA) loss). Suppose the radius of the current ball the model F can certify robustness respects to ground truth class over class i is kx(x)) as in Equation
define EMMA loss for data (æ, y) as follows,
exp (x))
fEMMA = log Σ. exp (x) + K
and é = clip value no (r,)),,
When using EMMA loss, the actual radius which we require the model to certify robustness at each iteration is ē for the margin between class and y. It's important to note that if the model still

---

Table 1: Comparing the proposed architecture LiResNet using the proposed loss EMMA against baseline methods. Verifiablly Robust Accuracy (VRA) is the percentage of test points on which the model is both correct and certifiablly robust so higher VRA is better. An & &a-ball with radius of 36/255 is used for all experiments following the conventions in the literature. "+DDPM" means use DDPM generators [36] to augment the training set (no external data used).
Dataset
Method
Architecture
Specification
#Param. (M)
Clean (%)
VRA (%)
BCOP
33
ConvNet
6C2F
2
75.1
58.3
GloRo 82
ConwNet
6C2F
60.0
Local-Lip
24
ConvNet
6C2F
77.4
60.7
Cayley [88
ConvNet
4C3F
75.3
59.2
CIFAR-I0
SOC (HH+CR) 45
ConvNet
LipConv-20
27
76.4
63.0
CPL. 35
ResNet
XL.
236
78.5
64.4
SL.L
ResNet
236
73.3
65.8
GloRo EMMA (ours)
LiResNet
6L128W
GloRo EMMA (ours)
LiResNet
12L512W
81.3
66.9
DDPM
LiResNet
121,512W
49
82.1
70.1
BCOP 3
ConvNet
6C2F
45.4
31.7
Cayley
ConvNet
4C3F
45.8
31.9
SOC (HI[+CR)
ConvNet
LipConv-20
34.8
CIFAR-I00
LOT
ConvNet
LipConv-20
49.2
35.5
SLL 2
ResNet
XI.
236
46.5
36.5
GloRo EMMA (ours)
LiResNet
6L128W
5
52.1
36.3
GloRo + EMMA (ours)
LiResNet
12L512W
49
55.2
38.3
DDDM
LiResNet
12L512W
55.5
41.5
GloRo 62
ConvNet
8C2F
35.5
22,4
Local-Lip Net
24
ConvNet
8C2F
36.9
23.4
Timy-ImageNet
SLL 2
ResNet
XL
236
32.1
23.2
GloRo EMMA (ours)
LiResNet
6L128W
5
40.8
29.0
GloRo + EMMA (ours)
LiResNet
12L512W
30.6
+ +DDM
LiResNet
12L512W
46.7
33.6
ImageNet
GloRo EMMA (ours)
LiResNet
12L,88W
86
45.6
35.0
predicts class i over the ground truth class (i.e., fz(x) < fa(x) thus [x) < 0), we clip é to 0 and EMMA loss reduces non-robust cross-entropy loss (for class i). In this case, the training focuses on improving clean accuracy first. As the training progresses, & may grow to the same magnitude as the expected radius c. Once this happens, we shift the model's s focus towards certifying other instances, rather than continuously increasing the robust radius for a.
As an implementation detail, need stop the gradient back-propagation from é,, i.e., treat as a constant during optimization. Otherwise, the denominator term fi(r) + K is just fy (x) and the logit for class removed from the computation graph of the loss.
Notice that EMMA introduces a dynamic adjustment to the robust radius using é. This allows the strength of the robustness regularization adapt in accordance with the training progress. Specifically, FMMA initially encourages the model to make correct predictions when é = O, then gradually shifts the model towards making more robust predictions as é; balancing the standard accuracy and robustness perhaps also agrees with the design TRADES (for adversarial training) [59] and its GloRo counterpart [32 Further discussion this point is included in Appendix
The idea of
Notice also that the proposed EMMA loss only affects the training step, so we still use Equation Too construct the 1 logit to certify the local robustness during inference, as proposed by Leino et al.
Evaluation
In this section, we provide an empirical evaluation LiResNet and EMMA loss in comparison to certifiably robust training approaches in prior works. We begin by comparing the best VRAs we achieve against the best VRAs reported in the literature Section 5.1 Next, Section 5.2 we run head-to-head comparisons between EMMA and the standard GloRo losses as an ablation study to measure the empirical benefits of EMMA loss. Section 5.3 presents experiments on networks of different depths, to shed light the unique depth scalability of the LiResNet architecture. In

---

Appendix F) we dive deeper into the ImageNet results, providing another novel observation regarding the impact of the number of classes on VRA.
The models in our evaluation either follow the architecture choices of prior work, or belong to a family of LiResNet architectures shown in Figure 2a Because the stem, neck, and head essentially fixed in our LiResNet architectures, we refer to a particular architecture variation by the number of backbone blocks, L, and the number of input/output channels, W. in convolution layers of each backbone. For example, 6L128W refers to LiResNet with 6 linear residual blocks with 128 channels each. Other architecture specifications can be found in Appendix B
5.1 Improved VRA with LiResNet
We compare GloRo LiResNets trained with EMMA loss with the following baselines from the literature: GloRo Nets with ConvNet architecture and cros-enttopy/TRADESS loss [2], BCOP [3), Cayley 48), Lic Net [24], and SOC with Householder and Certification Regularization (HH+CR) [43, CPL (55] and SLL 2 which are selected for having been shown to surpass other and Ann-ImmgeNet using & perturbations with = 36/255, the standard datasets and radii used in prior work. Additionally, we demonstrate the scalability of GloRo LiResNets by training on and certifying ImageNet. We report the clean accuracy, VRA, and the model size (by # of parameters) in Table Further details on training are in Appendix [B]
approaches. We experiment on CIFAR-10/10
On CIFAR-10/100 and Inngeee,,,,,t we find that small LiResNet, 6L is able to match or outperform all baselines. This architecture is about 40x smaller than the larges(" and highest- performing baseline model (SLL), but comes close to the same accuracy CIFAR- 1IFAR-10/100 and outperforms on Tiny- Imagenet. Our larger LiResNet (12L512W) surpasses all prior approaches, setting the state-of-thes are VRAs (without DDPM augmentation) 66.9%, 38.3% and 30.6% on CIFAR-10, 10, CIFAR-101 100 and Iiny-ImaeeNet, respectively.
Recent work on promoting empirical robustness has found that augmenting the training set with examples generated by Denoising Diffusion Probabilistic Models (DDPMs) 23 36 can further boost the empirical robust accuracy [20]. Thus, we also experiment to see if the same success can be found for certifiable robustness. DDPMs are trained with the training set, so the generated images do not leak information of the test set and do not use external data. Additional rows with "+DDPM" in Table show that with this augmentation method we further improve VRAs to 70.1 1%, 41.5% and 33.6% CIFAR- 10, CIFAR-100 100 and Tiny ImageNet, respectively (further details in Appendix H.. Because diminishing returns have been observed for improving empirical robustness when augmenting the training set of ImageNet with DDPM data [20], we did not use DDPM for LiResNet on ImageNet.
Scaling to ImageNet with GloRo. There is no theoretical limitation to the other approaches
considered in our evaluation that limit us from training them on ImageNet; however, practical resource constraints prevent us from training until convergence with non-Gloka approaches. For example, baselines using orthogonalized kernels-egg. Cayley, BCOP, and SOC-do not easily fit into memory with 224 x 224 x images, and local Lipschitz. computation- e.g. Local-Lipp Net-is both time and memory intensive. To the best of our knowledge, we are the first to report the VRA on ImageNet with a deterministic robustness guarantee and the first to calculate that VRA using the entire validation set, in contrast to the prior work which only evaluates 1% [25 39 40 or 2% (5) of the validation set using Randomized Smoothing 6 (also because of efficiency concerns).
5.2 Improved VRA with EMMA
This section demonstrates the empirical gains obtained by switching the typical loss used with standard GloRo losses-i.c. i.c. GloRo cross-entropy (CE) and GloRo TRADES-10 EMMA. For both ConvNets and LiResNets, we experiment on CIFAR-IO, CIFAR-100 and Timy-Im and report
"We observe that the SLL XL models have ofders-of-magnitue more parameters than the other baselines, coming from non-standard architecture with many wide dense layers. When use the 12L512W architecture but with the LiResNet layers replaced with SLL layers, we find the performance is much lower (59.5% VRA on CIFAR-10 and 30.2% VRA on CIFAR-IOW -00), suggesting that the primary factor in performance for SLL XL is the large number of parameters rather than the approach to bounding the Lipschitz constant of the residual layers. Capacity has been shown to be an important factor for obtaining high VRA with Lipschitz-basee approaches (30)
8

---

Architecture
dataset
TRADES
EMMA
Dutuset
ConvNet
ResNet
LiResNet
CIEAR-IH
58.8
59.2
6
64.0
60.3
65.5
ConvNet
CIFAR-100
34.0
35.0
CIFAR-10
59.2
60.0
Tiny ImageNet
26.6
27.4
60.1
66.6
CIEAR-10
66.2
66.3
33.5
LiResNet
CIFAR-100
37.3
37.8
CIFAR-100
12
35.0
33.5
37.8
Tiny-Imagent ImageNet
28.8
30.3
18
33.6
38.0
(a)
(b)
Table 2: (a) VRA performance (%) of ConvNet and LiResNet three datasets with different loss functions. (b) VRA (%) performance on LIFAR-10/LL with different architectures (L is the number of blocks in the model backbone). We use EMMA loss for Gloro training. All models in this table use 256 channels the backbone. value of x indicates that training was unable to converge.
VRAs Table 2a
The ConvNets we use are modified from the baseline 6C2F architecture used by Leino et al. [32 to have the same (wider) channel width as our 6L256W architecture, which is why we achieve higher VRAs than originally reported in (32] The remaining implementation details and
the clean accuracy of each model can be found in Appendix C
We see in Table 2a that the performance gain from switching TRADES EMMA becomes clear when the number of classes increases from 10 (CIFAR-10) 10) to 200 miny-lmagenet). This observation aligns with our hypothesis used to motivate EMMA loss, discussed in Section 4 namely, that the rotating threatening class phenomenon observed during training (see Figure 2b may contribute to suboptimal learning.
5.3 Going Deeper with LiResNet
As depicted in Figure I from the introduction, the VRA obtained using GloRo LiResNets scales well as the depth of the model increases, while prior work has failed to further improve the best achievable VRA through additional layers. To further validate that the ability successfully go deeper primarily comes from the structural improvement of linear residual branch in the LiResNet architecture-a20 opposed to being advantage of the framework, GloRo, itself-we run head-to- head comparisons on CIFAR-IC 10 and CIFAR- of GloRo Nets using (1) feed-forward ConvNet architecture, (2) a conventional ResNet architecture, and (3) LiResNet architecture. We train all three architectures with EMMA loss at three different depths. We report VRAs of these models in Table 2b (implementation details are given in Appendix D)
We see in Table 26 that very deep ConvNets may not be able to converge even on small-scale datasets like CIFAR-10 and CIFAR- 1000 Moreover, the VRA of both ConvNets and conventional ResNets do not benefit from the increasing network depth-in fact performance decreases as the network is made significantly deeper. By contrast, LiResNet is the only architecture under the same conditions that benefits from more layers, showing its unique promise for scalability. In Appendix [D] we include more results with even deeper LiResNets on CIFAR-I0, CIFAR-100 and Tiny-ImageNet.
6 Related Work and Discussion
Tightening Lipschitz Bound.
Work closely related to enhancing VRA with architectural redesign includes the use of orthogonalized convolutions 35
42 48 (4], which are I-Lipschitz by construc- tion. similar vein, we introduce the linear residual branch to solve the overestimation of Lipschitz Constant in the conventional ResNet. Our linear residual layer compares favorably to orthogonalized layers with few key advantages. Specifically, although there no technical limitation that would prevent from using orthogonalized convolutions in LiResNets, GloRo regularization performs better in our experiments, and is significantly less expensive than training with orthogonalized kernels.
The LiResNet block is re-parameterization of a convolution layer, to make it trainable at large depth. Prior to this work, there are seveval studies use the same technique: DiracNet [58), ACB [II. RepVGG (12), RepMLP [3]. etc. Our work has different motivations
Model Re-parameterizattion

---

from these works, which use re parammteeriiaiionn to achieve better optimization loss landscapes. Our work follows a similar approach to obtain tighter estimates of Lipschitz bounds.
Towards Certifying Transformers. Although our current experiments (see Appendix I indicate that Vision cerrffommmrs-ttizzzttiii linear residual blocks and Lipschitz-attentionn p 28 do not yield VRAs comparable to those of LiResNets, we conjecture this discrepancy primarily arises from the loose Lipschitz upper-bounds inherent to most Lipschitz-attention mechanisms, in contrast the exact Lipschitz constants of convolutions in LiResNets. To fully harness the potential of the linear residual block, future work should focus on rightening the Lipschitz bound for Lipschitz- attention.
Randomized Smoothing. As opposed to the deterministic robustness guarantee focused on in this work, probabilistic guarantees, based Raondmized Smoothing (RS) [6) have been long studied at ImageNet-scale [5, 25 39 40 Despite RS's reported higher certification results on ImageNet compared GloRo LiResNet for the same E, it has two primary limitations. First, RS can provide false positive results, where adversarial examples are given robustness certificates. This, in many real-world security and financial contexts, can be untenable, even 0.1 % false positive rate (FPR). Additionally, the computational cost of RS- -S-based certification is orders of magnitude higher than Lipschitz-baseer certification-tt certify one instance with FPR=0.1 %6 RS requires 100,000 extra inferences, and this number increases exponentially for lower FPR [6]. This resource-conseee cesource- nature of RS-based certification limits the type of applications one can deploy it in. Even in academic research, methods on certifying ImageNet with RS only report results using 1% of the validation images (i.e. 500 images) 22 39 40]; however, with the sipschitz-basee approach employed in our work, we can certify the entire validation set (50,000 images) in less than one minute.
Limitations for Robust Classification. The development of EMMA and empirical studies on class numbers' impact on VRA highlight the challenge of scaling robustness certification to real- world datasets. One challenge is that an increasing number of classes places increasing difficulty on improving VRA; we provide more details on this in Appendix [F) In addition, ambiguous or conflicting labels can further exacerbate the issue, indicating a possible mismatch between the data distribution and the objective of categorical accuracy, especially in its robust form. A number of mislabeled images have been identified in ImageNet 37 37, raising obstacles for robust classification. In addition, real-world images often contain multiple semantically meaningful objects, making robust single-label assignment problematic and limiting the network's learning potential unless alternate objectives (e.g., robust top-k accuracy (31 and robust segmentation [7 are pursued.
7 Conclusion
In this work, we propose a new residual architecture, LiResNet, for training certifiably robust neural networks. The residual blocks of LiResNet admit tight Lipshitz bounds, allowing the model to scale much deeper without over-regularizztion. To stabilize robust training on deep networks, we introduce Efficient Margin Maximization (EMMA). a loss function that simultancously penalizes worst-case adversarial examples from all classes. Combining the two improvements with GloRo training, we achieve new state-of-the-art robust accuracy on CIFAR- 10/100 and Tiny-ImageNet under se--nomm-bunddee perturbations. Furthermore, our work is the first to scale up deterministic robustness guarantees to ImageNet, showing the potential for large scale deterministic certification.
Broader Impact
Machine learning's 's vulnerability adversarial manipulation can have profound societal implications. especially in applications where robust and reliable AI systems are paramount. This work is an important step towards increasing the robustness of neural networks to adversarial attacks, and more broadly, towards ensuring the trustworthiness of Al systems. Our ability to scale up fast deterministic robustness guarantees ImageNet- a dataset more reflective of the complexity and diversity of real-world images-indien indicates that our approach to robust learning can be applied to practical, real- world applications. Nevertheless, while these advancements are promising, they also emphasize the need for ongoing vigilance and research in the face of increasingly sophisticated adversarial attacks. Ensuring that Al systems are robust and trustworthy will remain a critical task as these technologies continue to permeate society.
10

---

Acknowledgements
The work described in this paper has been supported by the Software Engincering Institute under its FFRDC Contract No. FA8702-15-D-0002 with the U.S. Department of Defense, as well as DARPA and the Air Force Research Laboratory under agreement number FA8750-15-2-00277
References
[1] Cem Anil, James Lucas, and Roger Gross. Sorting out Lipschitz function approximation. In ICML, 2019.
[2] Alexandre Araujo, Aaron J Havens, Blaise Delattre, Alexandre Allauzen, and Bin Hu. A unified algebraic perspective on lipschitz neural networks. In ICIR, 2023.
[3] Lucas Beyer, Olivier J Hénaff, Alexander Kolesnikov, Xiaohua Zhai, and Aäron van den Oord. Are we done with imagenet? arXiv preprint arXiv:2006.07159 2020.
[4] Schastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. In NIPS, 2021.
[5] Nicholas Carlini, Florian Tramer, J Zico Kolter, al. (certified!!) adversarial robustness for free! arXiv preprint a/Xiv:2206. 2022.
[6] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In ICML, 2019.
Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of ReL.U networks via maximization of linear regions. AISTATS, 2019.
[8] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with a reduced search space. CVPR Workshop. 2020.
[9] George Dasoulas, Kevin Scaman, and Aladin Virmaux. Lipschitz normalization for self-attention layers with application graph neural networks. In ICML.
[10] Terrance DeVries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint /708v 04552, 2017.
[11] Xiaohan Ding, Yuchen Guo, Guiguang Ding, and Jungong Han. Acnet: Strengthening the kemee skeletons for powerful cnn via asymmetric convolution blocks. In ICCV, 2019.
[12] Xiaohan Ding, Xiangyu Zhang, Ningning Ma, Jungong Han, Guiguang Ding, and Jian Sun. Repvgg: Making vtg-style convnets great again. In CVPR, 2021.
[13] Xiaohan Ding, Honghao Chen, Xiangyu Zhang, Jungong Han, and Guiguang Ding. Repmipnet: Hierarchi- cal vision mlp with re-parameterizee locality. In CVPR, 2022.
[14] Alexey Dosovitskiy. Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn. Xiaohua Zhai Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. ICLR 2021, 2020.
[15] Timothy Dozat. Incorporating nesterov momentum into adam. 2016.
[16] Farzan Farnia, Jesse Zhang, and David Tse. Generalizable adversarial training via spectral normalization. In ICLR, 2019.
[17] Mare Fischer, Maximilian Baader, and Martin Vechev. Scalable certified segmentation via randomized smoothing. In ICMI, 2021.
[18] Aymeric Fromherz, Klas Leino, Matt Fredrikson, Bryan Parno, and Corina Pásäreanu. Fast geometric projections for local robustness certification. In ICLR, 2021.
[19] lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy, Explaining and harnessing adversarial examples, 2015.
[20] Sven Gowal, Sylvestre-Alvise Rebuffi, Olivia Wiles, Florian Stimberg, Dan Andrei Calian, and Timothy Mann. Improving robustness using generated data. In NIPS, 2021.
[21] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in I hour. arXiv preprint arXiv 026777 2017.

---

[22] In CVPR. 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition.
[23] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. NIPS, 33:6840-66555 2020.
[24] Yujia Huang, Huan Zhang, Yuanyuan Shi, J. Zico Kolter, and Anima Anandkumar. Training certifiably robust neural networks with efficient local lipschitz bounds. In NIPS, 2021.
[25] Jongheon Joong, Sejun Park, Minkyu Kim, Heung-Chang Lee, Do-Guk Kim, and Jinwoo Shin. Smoothmix: Training confidenco-calibrated smoothed classifiers for certified robustness. NIPS, 2021.
[26] Matt Jordan, Justin Lewis, and Alexandros G. Dimakis. Provable certificates for adversarial examples: Fitting a ball in the union of polytopes. In NIPS, 2019.
[27] Guy Katz, Clark W. Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. In International Conference on Computer-Aided Verification (CAV), 2017.
[28] Hyunjik Kim, George Papamakarios. and Andriy Mnih. The lipschitz constant of self-attention. In ICML, 2021.
[29] Sungyoon Lee, Jaewook Lee, and Saerom Park. Cipschitz-certiffbble certifiable training with a tight outer bound. In NIPS, 2020.
[30] Klas Leino, Limitations of piecewise lincarity for efficient robustness certification. arXiv preprint arXiv:2301.0888 088442 2023.
[31] Klas Lcino and Matt Fredrikson. Relaxing local rohustness. In NIPS, 2021.
[32] Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robust neural networks. In ICML, 2021.
[33] Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Joem-Henrik Jacobsen. Prevent- ing gradient attenuation in lipschitz constrained convolutional networks. In NIPS, 2019.
[34] Tlya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts, arXiv preprint 1608. 2016.
[35] Laurent Meunier, Blaise Delatre, Alexandre Araujo, and Alexandre Allauzen. A dynamical system perspective for Lipschitz neural networks. In ICML, 2022.
[36] Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In ICML, 2021.
[37] Curtis G Northcutt, Anish Athalye, and Jonas Mueller. Pervasive label errors in test sets destabilize machine learning benchmarks. arXiv preprint arXiv:2103.14749 2021.
[38] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, perforrrrfrmncc deep learning library. NIPS, 2019.
[39] Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Schastien Buheck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. NIPS, 32, 2019.
[40] Hadi Salman, Mingjie Sun, Greg Yang. Ashish Kapoor, and J Zico Kolter. Denoised smoothing: A provable defense for pretrained classifiers. NIPS, 2020.
[41] Jie Shao, Kai Hu, Changhu Wang. Xiangyang Xue, and Bhiksha Raj. Is normalization indispensable for training deep neural network? NIS, 2020.
[42] Sahil Singla and Soheil Feizi. Skew orthogonal convolutions. In JCML, 2021.
[43] Sahil Singla, Surbhi Singla, and Soheil Feizi. Improved deterministic 12 robustness on cifar-10 10 and cifar- 100. In ICLR, 2022.
[44] Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with principled adversarial training. In ICLR, 2018
[45] Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, lan J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
12

---

[46] Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In ICLR, 2019.
[47] Hugo Touvron, Piotr Bojanowski. Mathilde Caron, Matthieu Cord, Alaaeldin El-Nouby, Edouard Grave, Gautier Izacard, Armand Joulin, Gabriel Synnaeve, Jakob Verbeek, et al. Resmlp: Feedforward networks image classification with data-efficient training. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2022.
[48] Asher Trockman and J Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. In ICLR, 2021.
[49] Yusuke Tsuzuku, Issei Sato, Masashi Sugiyama. Lipschitz margin training: Scalable certification of perturbation invariance for deep neural networks. In NIPS, 2018.
[50] Vijay Vasudevan, Benjamin Caine, Raphael Gontijo-oppes Sara Fridovich Keil, and Rebecca Roelofs. When does dough become a bagel? analyzing the remaining mistakes on imagenet. arXiv preprint arXiv:2205.04590 04596, 2022.
[51] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. NIPS, 2017.
[52] Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In ICML, 2018.
[53] Xiaojun Xu, Linyi Li, Yu Cheng. Subhabrata Mukherjee, Ahmed Hassan Awadallah, and Bo Li. Certifiably robust transformers with I-lipschitz self-attention.
[54] Xiaojun Xu, Linyi Li, and Bo Li. Lot: Layer-wise orthogonal training on improving 12 certified robustness. arXiv preprint arXiv:2210.1 1620, 2022.
[55] Yao-Yun Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Russ R. Salakhutdinov, and Kamalika Chaudhuri. closer look at accuracy vs. robustness. In NIPS, 2020.
[56] Weihao Yu, Mi Luo, Pan Zhou, Chenyang Si, Yichen Zhou, Xinchao Wang, Jiashi Feng, and Shuicheng Yan. Metaformer is actually what you need for vision. In CVPR, 2022.
[57] Sangdoo Yun, Scong Joon Oh, Bycongho Hco, Dongyoon Han, Junsuk Choe, and Sanghyuk Chun. Re-labeling imagenet: From single to multi-labels, from global to localized labels. In CVPR, 2021.
[58] Sergey Zagoruyko and Nikos Komodakis. Diracnets: Training very deep neural networks without skip- connections, arXiv preprint arXiv: 100.00888,,,88 2017.
[59] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoreti- cally principled trade-off between robustness and accuracy. In JCML, 2019.
[60] Hongyi Zhang, Yann N Dauphin, and Tengyu Ma. Fixup initialization: Residual learning without normalization. ICLR, 2019.
[61] Michael Zhang, James Lucas, Jimmy Ba, and Geoffrey E Hinton. Lookahead optimizer: k steps forward, I step back. NIPS, 2019.
13

---

A Discussions on EMMA Loss
One important aspect of EMMA loss is the dynamic adjustment to the robustness radius for each class when determining the loss. The robust radius used in EMMA is instead of the radius c that used at run time. By the definition of EMMA, 0 S غ S c and ? is 0 if the model is not labeling the input correctly. ? grows as the model becomes more robust at the corresponding input. As result, when the model not sufficiently robust the input, EMMA uses < с and imposes milder Lipschitz regularization. On the other hand, if using fixed margin, the loss function turns out to be:
fx(x)
Élxxd = - loog (.(x)))KK
(3)
This bears similarities to Lipschitz Margin loss, which has been used in prior work for certified train- ing [49], although Lipschitz Margin loss typically uses V2eK, which gives a looser approximation than directly using the Lipschitz constant for each margin, i.e., Kyi- The fixed margin loss (ixed in Equation 3 penalizes the Lipschitz-adjusee classes. Therefore, this loss function imposes stronger regularization on the Lipschitz constant of the model than EMMA loss, and limits the model capacity more. We find that models trained with the fixed margin loss require weaker data augmentation However, this can instead lead to robust overfitting. The gap between clean accuracy and VRA is notably higher for models trained with the fixed margin loss, and the overall performance is worse compared to models trained with the dynamic margin loss, i.e., EMMA loss.
margin between the ground truth class and all other
smaller training to avoid underfitting.
B Implementation Details for Table
B.1 Training details
The input resolution is 32 for CIFARI0/100, 64 for Tiny-ImageNet and 224 for ImageNet respectively. We apply the following data augmentation CIFAR datasets: random cropping, RandAugment [8], random horizontal flipping. For Tiny-ImageNet, we find this dataset is easy to overfit and add an extra Cutout [0] augmentation. For data augmentation hyper- prper-parameters. we use the default PyTorch setting.
Dataset details
Platform details Our experiments were conducted on an 8-GPU (Nvidia A100) machine with 64 CPUs (Intel Xeon Gold 6248R). Each experiment on CIFAR 10/10//1000 and Tiny-ImageNet takes one GPU and each experiment on ImageNet takes GPUs. Our implementation is based on PyTorch [8]
Training details On the first 3 datasets, all models are trained with the NAdam 15 with the Lookahead optimizer wrapper [6] with batch size of 256 and learning rate of 10 for 800 epochs. We use a cosine learning rate decay [34] with linear warmup [21] in the first 20 epochs. On ImageNet, we only change the batch size 1024 and training epochs to 400.
During training, we schedule the training e to ramp up from small values and slightly overshoot the test epsilon. Let the total number of epochs be T and the test certification radius be c, we use
Erain (t) =min
min(
2t
T 1) x 1.9 +.1 e,
36/255.
at epoch I. As a result, ((rain(() (4) begins at 0.1e and increases linearly to 2e before arriving halfway through the training. Later, éuain remains 2e to the end.
B.2 Model architecture details
Model stem is used to convert the input images into feature maps. On CIFAR10/100, we use convolution with kernel size 5, stride 2, and padding 2, followed by MinMax activation as the stem. On Tiny ImageNet, we use convolution with kernel size 7, stride 4, and padding 3, followed by a MinMax activation as the stem. On ImageNet, we follow the ViT-like patching [14] and use convolution with kernel size 14, stride 14, and padding 0, followed by MinMax activation as the stem. Thus the output feature map size from the stem layer 16 16 for all datasets. The number of filters used in the convolution is equal to the model width W.
14

---

Table 3: Clean accuracy and VRA performance (%) of ConvNet and LiResNet three datasets with different loss functions
loss
TRADES
EMMA
Clean (%)
VRA (%)
Clean (%)
VRA (%)
CIFAR-10 (e 36/255, 10 classes)
ConvNet LiResNet
71.7
58.8
72.5
59.2
79.6
66.2
80.4
66.3
CIFAR-100 (e 36/255, 100 classes)
ConvNet LiResNet
53.4
34.0
50.6
35.0
57.8
37.3
54.2
37.8
Tiny-ImageNet (c 36/255, 200 classes)
ConvNet 42.2
26.6
40.0
27.4
LiResNet
45.8
28.8
43.6
30.0
Model backbone used to transform the feature maps. is a stack of L LiResNet blocks followed by the MinMax activation, i.e., (LiResNet block + MinMax) x L. We keep the feature map resolutions and the number of channels constant in the model backbone. We find some tricks in normalization- free residual network studies [41 60 can improve the performance of our LiResNet our method also normalization- residual network. Specifically, we add an affine layer 3 that applies channel-wise learnable multipliers to each channel of the feature map (similar to the affine layer of batch normalization) and scaler of 1/v 1/vL. to the residual branch where L is the number of blocks:
y = x
(Cnnv(z)
VL
Model neck is used to convert the feature maps into a feature vector. our implementation, the model neck is layer network. The first layer is convolution layer with kernel size 4, stride 4, and padding O, followed by a MinMax activation. The number of input channels is the model width W and the number of output channels is 2W. Then we reshape the feature map tensor into vector. The second layer is dense layer with output dimension d where d = 2048 for the three small datasets CIFAR10/100 and ImagelmageNet) and d 4096 for ImageNet.
Model head is used to make classification predictions. We apply the last layer normalization (LLN)
proposed by 43 the head.
B.3
Metric details
We report the clean accuracy, i.e., the accuracy without verification on non-adversarial inputs and the verified-robust accuracy (VRA), i.e., the fraction points that are both correctly classified and certified robust. Our results averaged over 5 runs for CIFAR10/100 and TinylmageNet and runs for ImageNet.
C Details for Table 2a
In Table 2a we use an L12W256 configuration, i.c., the backbone has 12 blocks and the number of filters 256. For ConvNet, the only difference is that the LiResNet block is replaced by a convolution of kernel 3, stride I, and padding I. All other settings are the same. Table 3is is more detailed version of Table 2a with the clean accuracy.
D Details for Table 2b
In Table 2b we use the configuration of W256, i.e., the number of channels in the backbone is 256. The only difference between conventional ResNet and LiResNet is the block. The block for
15

---

Table 4: Clean accuracy and VRA (%) performance on CIFAR- 10/100 with different architectures (L is the number of blocks in the model backbone). We use EMMA loss for Gloro training. x stands for not converging the end.
Dataset
L
ConvNet
ResNet
LiResNet
Clean
VRA(%)
Clean (%)
VRA(%)
Clean (%)
VRA(%)
77.9
64.0
74.2
60.3
79.9
65.5
10
12
72.5
59.2
74.0
60.0
80.4
66.3
18
X
x
73.9
60.1
81.0
66.6
51.8
36.5
48.4
33.5
53.6
37.2
CIFAR-100
12
50.6
35.0
48.1
33.5
54.2
37.8
18
X
x
48.2
33.6
54.3
38.0
Table 5: Clean accuracy and VRA (%) performance of LiResNet of different depths (L is the number of blocks the model backbone).
L
CIFARIO
CIFARIOK 100
Tiny- Iiny-ImaeeNet
Clean %)
VRA(%)
Clean (%)
VRA(%)
Clean(%)
VRA(%)
79.9
63.5
53.6
37.2
43.1
29.8
12
80.4
66.3
54.2
37.8
43.6
30.3
18
81.0
66.6
54.3
38.0
43.9
30.6
24
81.2
66.8
55.0
38.2
44.2
30.7
30
81.3
66.9
54.9
38.4
44.2
30.6
36
81.2
66.9
55.0
38.3
44.3
30.4
conventional ResNet is
y = x (SConn(Mnnaax(Coon
where B is the affine layer. We find use zeros to initialize / works the best for conventional ResNet. The number of input and output channels of the two convolution layers are the same that of the LiResNet block. Table is is more detailed version of Table 2b with clean accuracy.
E Details for Figure I
We make LiResNet further deeper and study how network depth influences the performance on CIFAR-10/100 and ImageNet. Table shows the clean accuracy and VRA of LiResNet (with EMMA loss) on three datasets. All models use a W256 configuration, i.e., the number of convolutional channels 256. On 1EFAR-10/104 the VRA performance of the LiResNet generally improves with the performance remains with the increase of depth.
depth. On
Figure compares the VRA performance of LiResNet with some existing method for verification robustness on CIFAR-100 (i.e., the 5th of Ta.le The numbers of these methods are taken from their hest-reported configurations. The VRA performance of these methods degrades certain depths, limiting the maximum model capacity of the methods.
F
Number of Classes vs. VRA
Despite the fact that EMMA loss improves the ability of GloRo Nets to handle learning problems with many classes, datasets with large number classes still stand out as particularly difficult for certified training. In principle, a data distribution with less classes is not guaranteed to have more separable features than more classes and CIFAR-100 are confortably in the high 90's despite the large difference in the number of classes. However, training certifiably robust model with many classes appears more difficult in practice (as observed, e.g., by the large performance gap between CIFAR-10 and CIFAR-1ON To test this
the state-of-the-are clean accuracy for both CIFAR-10
16

---

Standard (Clean)
Gloro Net (Clean)
Gloro (VRA)
50
40
30
20
10
600
Number of classes
Figure 4: Plot of LiResNet performance on subsets of ImageNet with different number of classes
with = 1
Table 6:
VRA (%) of LiResNet of different widths (W).
W
CIFAR- 10
CIFAR-100
Tiny- ImageNet
64
64.6
36.5
28.7
128
65.6
37.5
29.8
256
66.3
37.8
30.0
512
66.9
38.3
30.6
observation further, we provide empirical study on various class-subsets of ImageNet study the relationship between the number of classes and VRA.
We randomly shuffle the 1000 classes of ImageNet and select the first 100 k classes, where & E [10], to build a series of subsets for training and testing. For each value k, we train a GloRo LiResNet with EMMA loss (e 1) and report the clean accuracy and VRA (at 1) on the test set. For reference, we also train standard (i.e., not robust) LiResNet with Cross Entropy and report its clean accuracy the test The final results Compared to the clean accuracy of a standard model, increasing the number classes leads to steeper drop in both the VRA and the clean accuracy of the robustly trained models. Specifically, while the performance of the standard model differs only by 10% between a 100-class subset and the full ImageNet, the performance of the GloroNet (both clean accuracy and VRA), drops by 30%.
shown in Figure 4 with additional details in Appendix F
These results add weight to the observation that, even when mitigated by EMMA loss, large numbers of classes present particular challenge for certifiably robust learning. This may arise from the need to learn a 2e-margin between all regions with different labels, which becomes progressively more challenging boundaries between growing number of classes become increasingly difficult push off the data manifold.
G Going Wider with LiResNet
study how network width (i.e., the number of channels in the model backbone) can influence the performance of LiResNet on CIFAR-10, CIFAR-100 and Imay-Im Table 6 shows the results. All models use a I.12 configuration. Unlike the network depth, increasing the width can stably improve the model performance within certain range.
17

---

H Extra data from DDPM
We use codes from the improved DDPM 36 to train generative models on CIFARIO, C0 and Iny-ImmgeNet. The models are only trained on the training set of each dataset and no external data is used. We use the recommended hyper- parameerreettrrs from [6) and the models are conditional, i.e. generated samples are with labels. We generate million samples for each dataset.
During the training of Gloro Net, we sample 256 samples from the original dataset and 256 samples from the generated data for each batch. Due to the large total number of generated data, we do not need strong data augmentation on the generated data. Compared to the original dataset, do not use the Rugment augmentation for the generated data. All other settings are the same for the original dataset and the generated data.
I Certifiable Robustness with Transformers
Transformers-based models [51] have been shown to surpass existing convolution networks on major language tasks. To fully utilize the power of Transformer layers, and Vision Transformers 14 chunk images as small patches to convert one image as a sequence of patches, which is used as input to Transformer-basee network. A Transformer layer is a combination of self-attention blocks (SA) and feed-forward layers (FFN). Between the blocks, layer normalization layers are added to increase the stability of the learning. Because in this paper we mainly focus on certifying vision models, we will simplify refer Vision Transformers Transformers in the rest of this section.
Mon-Liipehitz Operations Transformers. The fundamental challenge of certifying Trans- formers' prediction on images with Lipschitz-based approaches arises from the many modules in Transformer layer are not supschitz-continuonn
i.e. SA and Layer Normalization. One can simplify remove normalization layers from Transformer layer but this may lead to serious performance degradation [56]. On the other hand, SA is also not Lipschitz because of the softmax calculation taken over the attention scores. Recent work focuses on designing Lipschitz-continuuu alternatives for SAs, which includes OLSA 33 and 1.2MHAA [28]. Another idea is to use spatial MI.P 47 that calculates static "attention weights" they are bounded by construction.
Replacing with Linear Residual Connections. In terms of FFN, it is a standard residual block and thus suffers from the same problem identified in Section 3 Namely, the overall Lipschitz constant of FFN can be loose because of the skip connection. We therefore replace a standard FFN in a Transformer layer with our linear residual connection tighten its Lipschitz bound.
Certifying Transformers. Our discussion above has shown that to certify the robustness of Transformer-based models, one needs to remove non-Lipschizz-coniiuuus operations replace them with Lipschitz-continuous alternatives. We will refer to a Transformer-basee model modified to only contain Lipschitz-continuous operations as Lipschitz Transformers. We conduct experiments on CIFARIO and CIFAR 100 and provide VRAs of Lipschitz Transformers with different linear operations. That is, for the SA block, we replace it either with an OLSA or a spatial MLP. For the FFN layer. we can optionally it to our linear residual connection and will denote this modified FFN as LiFFN. We use the 252 configuration and Table 7 shows the results.
As shown in Table 7 all variants of Lipschitz Transformers do not outperform LiResNets (with the same configuration.. The combination of "Spatial MLP" and "LiFFN" performs the best among all variants of transformers. This architecture is also most aligned with the motivation of this paper- aoper-using using linear operations for the weights to obtain tight Lipschitz constant estimation.
Results.
In conclusion, Transformers have potential applicability in Lipschitz--asedd robustness certification; however, their performance leaves much be desired. This inadequacy stems primarily from two limitations. Firstly, layer normalization layers are nonviable, and secondly, the SA and FFN blocks struggle to attain a tight estimation of the Lipschitz constant. Although our work sheds light on how to tightening the Lipschitz bound for FFN with LiFFN, the current Lipschitz alternatives for SAs are not tight enough further promote the robustness of Transformers.
18

---

Table 7: VRAs (%) measured with different variants of Lipschitz Transformers. As reference for the state-of-the-art performance for convolutional networks, we include our LiResNet results from Table 1
dataset
replacement for SA
replacement for FFN
VRA(%)
Spatial MLP
LiFFN
63.3
CIFAR1O
Spatial MLP
FFN
62.6
OLSA
FFN
56.6
LiResNet-L122566
66.9
Spatial MLP Spatial MLP
LiFFN
36.5
CIFAR100
FFN
33.7
OLSA
FFN
28.4
LiReNNe--12W256
38.3
19


Reviews:
[{"review_id": "jB67htRFaY", "reviewer": "Reviewer_xiEp", "summary": "This paper aims to scale up deterministic certified robustness to deeper neural networks (ResNet) and more complicated datasets (ImageNet). To this end, the authors proposed a new residual block named LiResNet and a new loss function named Efficient Margin Maximization. The proposed method achieves the state of the art results on various benchmarks.", "questions": "Is there any normalization layer in the LiResNet architecture? There seems to be none in Figure 2(a). It is a bit surprising the it can scale so well in depth without any normalization layers.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper is very well written and easy to follow. Each design choice is well motivated and thorough experiments demonstrated the effectiveness of the proposed methods.\n- The proposed LiResNet architecture is a simple but effective technique to bypass the difficulty in certifying ResNet. Experiments also showed its scalability to deeper networks. \n- The new loss is well motivated by the experiment finding that the inconsistency of the threatening classes increases when number of classes increases.\n- Comprehensive experiments on various datasets have shown the effectiveness of the proposed methods and established new state-of-the-art.", "weaknesses": "- Despite the effectiveness of LiResNet in certified robustness, it may be still less expressive and scalable than the actual ResNet. It would be good to discuss the limitation of the LiResNet architecture: what do we sacrifice by \"linearizing\" the skipping connection?\n- The new proposed loss is well motivated, but it seems that in the experiment there is no ablation study on it. It'd be good to include Gloro + LiResNet but without EMMA to show the improvement of EMMA compared to the Gloro loss.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for their valuable comments. Our answers to your questions are below.\n\n> Despite the effectiveness of LiResNet in certified robustness, it may be still less expressive and scalable than the actual ResNet. It would be good to discuss the limitation of the LiResNet architecture: what do we sacrifice by \"linearizing\" the skipping connection?\n\nIt still remains an open question if a LiResNet is meaningfully less expressive than a conventional ResNet. Here we provide some results comparing LiResNet and ResNet on ImageNet classification, which show that LiResNet is capable of achieving similar performance of a ResNet and a VGG-Net around the similar network depth. We follow the standard training settings to train classification models on ImageNet.\n\n\n|                  | number of layers | Top 1 accuracy |\n|------------------|------------------|----------------|\n| LiResNet         |       18         |     73.3%      |\n| VGG [1]              |       19         |     74.2%      |\n| ResNet [2]          |       18         |     69.8%      |\n\nPerhaps a good way of thinking about this is the following: suppose we fix the number of convolutions in a network, but vary how many are placed inside each residual block. At one extreme, all the convolutions are in a single block, so we essentially have a ConvNet. On the other end, we have a LiResNet, with only one convolution per block (a traditional ResNet would usually have two or three). While the additional skip connections can be seen as additional constraints on the function learned by the model, it seems clear most of the expressiveness comes from the depth of the backbone regardless of the block size. In this view, the ConvNet is the most expressive, but we rarely worry that a ResNet has insufficient capacity by comparison, because the skip connections ultimately allow us to train a deeper network that wouldn’t be possible with a ConvNet.\n\n\n> The new proposed loss is well motivated, but it seems that in the experiment there is no ablation study on it. It'd be good to include Gloro + LiResNet but without EMMA to show the improvement of EMMA compared to the Gloro loss.\n\nWe include an ablation study for the loss in Table 2 (a), where we compare EMMA and the TRADES loss (proposed by Leino et al [3] as the default loss in their work). The results are most notable on the tasks with more classes, as hypothesized.\n\n> Is there any normalization layer in the LiResNet architecture? There seems to be none in Figure 2(a). It is a bit surprising that it can scale so well in depth without any normalization layers.\n\nYes, as perceived by the reviewer LiResNets is a normalization-free architecture. In fact, to the best of our knowledge, several works [3, 4, 5] in training certifiable robust models end up with not using any normalization layers. There are a few reasons. Firstly, one of the widely-used layers, layer normalization, is not Lipschitz-continuous so it does not fit into Lipschitz-based methods. Secondly, there are diminishing returns in using batch normalization from our experiments and from other papers [3, 4]. The following paragraph provides some explanations for the choice of normalization-free.\n\nWhile the reason for this is not 100% clear to the community, there is a large body of work on normalization-free methods, and some work suggests that gradient norm preservation (GNP) may play a similar role as compared to normalizations. GNP has been found as a fundamentally important building block for certifying networks and can be realized by using MinMax or GroupSort activations [6]. It may help to stabilize the internal activations by stabilizing gradients. Besides GNP, there is another line of work studying parameter initializations in order to realize normalization-free [7, 8]. Their insights result in some specific ways of initializing the residual block detailed in the Appendix B2. \n\n\n\n[1] Simonyan et al., Very Deep Convolutional Networks for Large-Scale Image Recognition, ICLR 2015.\n\n[2] He et al., Deep Residual Learning for Image Recognition, CVPR 2016.\n\n[3] Leino et al., Globally-Robust Neural Networks, ICML 2021.\n\n[4] Trockman et al., Orthogonalizing Convolutional Layers with the Cayley Transform, ICLR 2021.\n\n[5] Huang et al., Training certifiably robust neural networks with efficient local Lipschitz bounds, NeurIPS 2021.\n\n[6] Anil et al. Sorting out Lipschitz function approximation, ICML 2019.\n\n[7] Shao et al. Is normalization indispensable for training deep neural network, NeurIPS 2020.\n\n[8] Zhang et al. Fixup Initialization: Residual Learning Without Normalization. ICLR 2018.\n\n"}, {"review_id": "UovyPS9Sim", "reviewer": "Reviewer_diKy", "summary": "- The paper investigates Lipschitz-based Certification of neural networks.\n- Authors aim to certify ResNets by extending the techniques from GLORO.\n- Authors note that it is difficult to come up with a tight approximation of the residual block\n- So authors replace the non-linear residual block to a linear block. They are then able to adapt GLORO results\n- Authors add the non-linearities after the linear residual block.", "questions": "- Regarding the clean accuracy, why is it higher than the baselines? \n- Can you compare the numbers with networks of the same size?\n- This will explain whether having such a network (as opposed to usual ResNet) is useful more broadly.\n\n", "limitations": "Yes, limitations are discussed well.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Good writing\n- The paper is well written. I could follow all the sections in one pass.\n- Authors have now also added sections discussing transformers and complications with verifying them.\n\n2. Thorough experiments\n- A wide range of experiments are conducted on various datasets.\n- The experimental results look decent.\n- I have a question regarding the clean accuracy, which I have added in the questions section.\n\n3. Good problem\n- Certifying residual blocks is definitely worth doing.\n- As authors mentioned, residual connections are also used in Transformers.", "weaknesses": "1. about the effectiveness of LiResNet\n- Main trouble in verification comes from the non-linearity. It feels natural that removing non-linearities will make things easier. The authors are not really verifying the resnet as such.\n- If $x + conv(x)$ can be written as a conv layer, then are you really verifying residual connections or just verifying a linear layer?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for their valuable comments. Our answers to your questions are below.\n\n> Main trouble in verification comes from the non-linearity. It feels natural that removing non-linearities will make things easier. The authors are not really verifying the ResNet as such. \n\nWe would like to highlight that main issue with the Lipschitz-based approaches on conventional ResNet is not originated from the **nonlinearity** of the module – it comes from bounding the addition of the residual branch and the skip connection $y = x + f(x)$, which is a linear part in a ResNet block. The Lipschitz upper-bound of such a linear combination, $Lip(f+g)\\leq Lip(f) + Lip(g)$, is shown to be loose in the paper and motivates our design of linear residual block. The characterization that we are “not verifying ResNet” is inaccurate, given that LiResNets consist of the classic skip connections that enable gradients to flow back to the deeper part of the model without vanishing issues, which is the defining feature of a “ResNet” architecture; though of course, the LiResNet architecture is a specific innovation that achieves desirable properties not shared with a traditional ResNet architecture. \n\n> If  x + conv(x) can be written as a conv layer, then are you really verifying residual connections or just verifying a linear layer? \n\nWe are verifying the entire network, not just a linear layer. Moreover, because the LiResNet blocks are the equivalent of x + conv(x), **these layers do contain residual connections, hence why the LiResNet is a residual network. It is merely a reparameterization technique to write these layers as a convolution**; however, _this does not justify saying that this makes it just a convolutional network_, as the reparameterization acts as a constraint on which convolutions will be learned. This is exactly analogous to how a convolutional layer can be written as a dense layer, while clearly a convolutional network is not the same as a dense network in any meaningful way. Our ablation study (LiResNet vs. ConvNet) shows that this reparameterization indeed has better training properties than directly training a ConvNet.\n\n> Regarding the clean accuracy, why is it higher than the baselines?\n\nWe would appreciate it if the reviewer specifies which result (e.g. in which table) is referred to in the question. If the question is pretty general, we argue that it is that LiResNets facilitate a better trade-off between expressiveness (depth) and tight Lipschitz bounds, allowing us to learn a robust function with less overregularization; thus the clean accuracy is also higher.\n\n\n> Can you compare the numbers with networks of the same size?\n\nIn our ablation studies, we do compare the numbers with networks of the same size. When compared with previous work, it is hard to compare with exactly the same size since the backbone is different. In Table 1, we compare our results with the best reported results from previous work. Specifically, to compare with SLL, the current state of the art result, our method achieves better VRA with a much smaller model size (in terms of parameters), which shows the effectiveness of our method. See the following table for comparing VRAs under eps=36/255 between ours and SLL summarized from our paper.\n\n|  Models           | Model Size | CIFAR-10 | CIFAR-100 | Tiny-Imagenet |\n|-------------|------------|----------|-----------|---------------|\n| LiResNet L12W512    | 49M        | 70.1     | 41.5      | 33.6          |\n| SLL Small   | 41M        | 62.6     | 34.7      | 19.5          |\n| SLL X-Large | 263M       | 65.8     | 36.5      | 23.2          |\n\nHere is a comparison of training speed. Our largest model and the smallest SLL model (SLL Small) have a close training throughput while the largest SLL model is 4.5 times slower than our LiResNet.\n\n|                                | SLL Small | SLL X-Large | LiResNet L12W512 | \n|--------------------------------|-------|-------------|----------|\n| Training speed (images/second) |  3943 |     813     |   3805   |\n\n\n\n"}, {"review_id": "kf4I53lyNj", "reviewer": "Reviewer_jf6o", "summary": "This paper proposes Linear ResNet (LiResNet) and Efficient Margin Maximization (EMMA) loss for scalable training of provably robust deep neural network classifiers. With these two contributions, this work is able to achieve SOTA deterministic VRA on medium-to-large classification tasks.", "questions": "**Question 1** : Power method is used throughout training to estimate the global Lipschitz constant. How many iterations of power method is used at each step of training? How tight is the Lipschitz constant estimate?\n\n**Question 2** : It is widely known that there is an accuracy-robustness trade-off. TRADES offers a hyper-parameter to control that trade-off. Would it be possible to control the trade-off for EMMA as well? How does the accuracy-robustness pareto frontier for LiResNet+EMMA compare to other methods?", "limitations": "Discussed in Section 6.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The paper is clearly written.\n- The proposed method demonstrates strong empirical performance.", "weaknesses": "I am willing to raise the score by 1 or 2 points if the authors answer my questions satisfactorily.\n\n**Weakness 1 : Ambiguity regarding the scalability of LiResNets.**\n- The authors do not exactly pinpoint why LiResNets are scalable. In Table 2 (b), the authors show VRA  of ConvNets, ResNets, and LiResNets at various depths. Then, the authors just describe the table as-is, without any further discussion or analysis. Why do ConvNets diverge? Is it because of vanishing or exploding gradients? Why do ResNets have lower VRA than LiResNets? Is it because LiResNets enable tighter Lipschitz constant estimation? Is it because LiResNets allow faster convergence to optima? If there are multiple factors at work, how much does each factor contribute to the final VRA?\n\n**Weakness 2 : Hand-wavy logic regarding the rotating threatening class phenomenon and EMMA.**\n- Section 5.2, line 282, \"rotating threatening class phenomenon observed during training may contribute to suboptimal training.\" --> Table 2 (a) only shows VRA before and after applying EMMA. How do we know whether performance gain comes because EMMA prevents the rotating threatening class phenomenon? Only a hand-wavy explanation in Section 4, line 209-215 is given. I would appreciate a more rigorous theoretical or experimental analysis of EMMA.\n\n**Concern 1 : Representation power of LiResNets.**\n- I get that LiResNet can admit tighter Lipschitz constant estimation. However, how scalable is LiResNet compared to ResNet in terms of clean accuracy when trained with cross entropy? Doesn't using linear residual blocks reduce the representation power of ResNets? If LiResNets have less representation power than ResNets, wouldn't we eventually have to return to ResNets when we have better training techniques and aim for even higher VRA?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The authors do not exactly pinpoint why LiResNets are scalable ... Why do ConvNets diverge? Is it because of vanishing or exploding gradients? \n\nYes, it is because of exploding gradients. Even for standard (non-robust) cross entropy training, ConvNets with 18 layers perform worse than ResNets. The task of certificate robustness is more difficult than standard cross entropy training since the training objective has a strong regularization from the network Lipschitz estimation, making the training of ConvNets even more difficult.\n\n> Why do ResNets have lower VRA than LiResNets? Is it because LiResNets enable tighter Lipschitz constant estimation? ... If there are multiple factors at work, how much does each factor contribute to the final VRA?\n\nThere might be other factors behind why LiResNets enjoy higher VRA than ResNets, but the tighter Lipschitz bounds is definitely the dominating one. The Lipschitz constant lower bound for a conventional ResNet is much larger than the actual Lipschitz constant of the network, thus much of the model’s expressiveness is wasted. You can think of it as though a ResNet is trained to be robust at a much larger noise radius, but we can still only verify at a small noise radius. This also means ResNets will suffer greatly from overregularization during certified training. In our experiments, ResNets have converged when we report their VRAs so we suspect the convergence speed is not a major factor. More discussion on ResNet vs. LiResNet performance is included in our updated paragraph above.\n\n> Section 5.2, line 282, \"rotating threatening ...\" --> Table 2 (a) only shows VRA before and after applying EMMA. How do we know whether performance gain comes because EMMA prevents the rotating threatening class phenomenon? .... I would appreciate a more rigorous theoretical or experimental analysis of EMMA.\n\nThanks for pointing out there might be missing steps in our reasoning line. By plotting the percentage of samples that the penalized non-label logits change in two consecutive epochs, Figure 2b locates the **rotating threatening class (RTC)** issue in the existing GloRo training with TRADES loss. **We run the same experiment with EMMA loss and plot the result .** Please check Figure 1 in the attached PDF file in the global rebuttal section.  We found that RTC happens to less training points if using EMMA loss, compared to TRADES loss. We hereby empirically validate that EMMA loss helps to reduce the times of having RTCs during training, mitigating the suboptimal issue raised in the paper. The mitigation of RTC is expected for GloRo Nets to converge smoothly and faster to achieve higher VRA, which is later evidenced by Table 2(a). Taking Figure 2b and Table 2 from the paper and the new plot (Figure 1 attached in the PDF) comparing EMMA loss and TRADES loss, we demonstrate an empirical correlation between the mitigation of RTC and the improvement of VRA. We will also clarify this reasoning line in the writing. \n\n> How scalable is LiResNet compared to ResNet in terms of clean accuracy when trained with cross entropy? Doesn't using linear residual blocks reduce the representation power of ResNets? \n\nIt is not clear that a LiResNet is meaningfully less expressive than a traditional ResNet. Here we provide some results comparing LiResNet and ResNet on ImageNet classification, which show that LiResNet is capable of achieving similar performance of a ResNet and a VGG Net around the similar network depth. \n\n|                  | number of layers | Top 1 accuracy |\n|------------------|------------------|----------------|\n| LiResNet         |       18         |     73.3%      |\n| VGG              |       19         |     74.2%      |\n| ResNet           |       18         |     69.8%      |\n\n> How many iterations of the power method is used at each step of training? How tight is the Lipschitz constant estimate?\n\nWe use 10 iterations during training. We empirically verified the tightness of our Lipschitz constant estimation of the entire network by optimizing |f(x) - f(y)|/|x - y| w.r.t x and y on the network f. Here are the results of our trained LiResNet models on 4 datasets, which show that the upper bound is fairly tight. “UB” (upper bound) is our Lipschitz constant estimation and “LB” is the lower bound from maximizing |f(x) - f(y)|/|x - y|.\n \n|    | ImageNet | CIFAR-10 | CIFAR-100 | Tiny-ImageNet |\n|----|----------|----------|-----------|---------------|\n| LB |   1.12   |  53.35   |   12.95   |     7.16      |\n| UB |   1.54   |  59.03   |   14.03   |     7.73      |\n\n> It is widely known that there is an accuracy-robustness trade-off. TRADES offers a hyper-parameter to control that trade-off. Would it be possible to control the trade-off for EMMA as well? \n\nYes, we can manage this trade-off. For example, we can use a weighted sum of EMMA loss and cross entropy loss: CE-loss + k * EMMA-loss for some hyper-parameter k. To make our method simpler, we only present EMMA loss in the paper.\n\n> How does the accuracy-robustness pareto frontier for LiResNet+EMMA compare to other methods?\n\nIt is hard to compare the pareto optimal of our method and other methods theoretically. However, we want to emphasize an important difference between our work and other works like CPL and SLL. While these methods enforce the Lipschitz Constant's regulation by imposing constraints on the weights, we opt to regulate it through the loss function, like in Leino et al. (2021). This method of regularizing Lipschitz constants with the loss has a potential advantage: it enables the learning of robust models with various Lipschitz constants. Should 1-Lipschitz Nets prove to be the optimal choice for certified robustness within certain data distributions, our models retain the ability to learn such functions. In our empirical evaluations from Table 1, our method is better than the SoTA (CPL and SLL) in both clean accuracy and VRA with a smaller model size.\n"}, {"review_id": "1njHFQtbr9", "reviewer": "Reviewer_YimP", "summary": "This paper addresses the issue of certified accuracy with deterministic approaches by utilizing the Lipschitz property of neural networks. The authors propose a novel layer called LiResNet, which enables easy computation of the Lipschitz constant. Additionally, they introduce a new loss function called Efficient Margin Maximization (EMMA), that stabilizes robust training by simultaneously penalizing worst-case adversarial examples from all classes. Finally, the authors conduct experiments on CIFAR-10/100, Tiny-ImageNet, and ImageNet datasets, demonstrating that their approach achieves state-of-the-art results in certified accuracy under $\\ell_2$ perturbations and $\\epsilon = 36/255$.\n", "questions": "The authors have combined many different techniques and tricks to achieve their certified robustness. An ablation study would be interesting to identify those that increase the certified robustness.\n\n- What is the performance of the author's architecture with an SLL layer that is 1 Lipschitz?\n- What is the performance of the author's architecture with the loss from [3]? How does the EMMA loss improve the VRA? \n\nThe authors added some tricks for better training: the epsilon scheduler presented in Appendix B1 and the normalization trick presented in Appendix B2. \n- How does the epsilon scheduler affect the final certified accuracy?\n- How does the normalization trick affect the final certified accuracy?\n\n- What is the certified accuracy for other perturbation thresholds? (e.g. $72/255$, $108/255$, $1$ to allow comparison with other work)\n\n[3] Tsuzuku et al., Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks, NeurIPS 2018", "limitations": "The authors discussed the limitation of robust classification.", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper is clear and well-written. \n- Improving certified accuracy with deterministic approaches is clearly an important problem and the improvement over state-of-the-art is impressive. \n", "weaknesses": "While the experimental results are good and interesting. The paper suffers from overclaiming important contributions and not discussing important related works. \n\n1. **Overclaim on Lipschitz Residual layer**: The claim that the paper is the first to propose a Lipschitz Residual layer is incorrect. The CPL layer [1], and more recently the SLL layer [2], are two previous works that have introduced a 1-Lischitz _Residual_ layer with ReLU activation. The authors mention these two papers in the related work without discussing their contribution. The authors should discuss these works.\n\n2. **On the efficiency and tightness of the approach**: In the abstract, the authors have written: \"We show that fast ways of bounding the Lipschitz constant for conventional ResNets are loose, and show how to address this by designing a new residual block\"\n- **On the efficiency of the approach**: I don't see how the approach is more efficient than previous works, since the authors just use the power iteration (verified in the code provided in the supplementary material as this is not mentioned in the paper or the appendix). The power iteration has been used in three previous works [3, 4, 1]. We can also note that the authors use a power iteration with 10 iterations (default value in the code) while [3,4,1] showed that using only 1 iteration was sufficient and more efficient. Therefore, I don't see how the author’s approach is \"more efficient\" than previous work.\n- **On the tightness of the bound**: It is true that the value of the Lipschitz constant of LiResNet is tighter than the one from a Residual Layer with nonlinearity, in fact, the power iteration computes the _exact_ Lipschitz of LiResNet, since LiResNet is a _linear_ layer -- the PM computes the Lipschitz of the map $x \\mapsto (I + W) x$. Computing the Lipschitz of a Residual layer with a nonlinearity leads to a looser bound, because the nonlinearity allows for a lower Lipschitz. The authors should clarify this. \n\n3. **On the new EMMA loss**. The Efficient Margin MAximization (EMMA) loss introduced in the paper is very similar to the one provided by [3]. The authors discuss the difference between their loss and the one from [3] in Appendix A, arguing that the main difference is the use of the _Lipschitz constant for each margin_ while [3] uses the _global Lipschitz constant_ (I believe this paragraph deserves to be in the main paper). This is true, however, the use of the Lipschitz constant for each margin has been proposed twice before [5, 6] (the last layer normalization reduces to the same Lipschitz), therefore, the EMMA loss is a simple combination of two known approaches. \n\n4. **On the experiments**: Table 1 presents results only for the perturbation level of $\\epsilon = 36/255$. The authors should present results for a multitude of values to show the overall robustness of their approach (or make a graph with certified accuracy vs \\epsilon). A large body of work [1, 2, 6, 7, 8, 9, 10] has presented the certified robustness of their model for at least 3 or 4 perturbation thresholds. I would like to see the same comparison. In Table 2, the authors talk about \"VRA performance (%)\". What does VRA performance (%) mean? Again the authors should provide VRA with respect to a specific perturbation and not assert that the overall robustness of a model can be computed with only one single perturbation threshold. \n\n**Conclusion**: The paper feels like a patchwork of several existing ideas and looks more like engineering work than research work. The paper has combined the work of [3] and [5,6] for the loss, used the same algorithm (power iteration) as [3,4,1] to compute the Lipschitz, and proposed a new linear layer that seems to have good properties. They used several tricks (epsilon scheduler presented in Appendix B1, normalization trick presented in Appendix B2) without ablation study. With all this, they showed that it is possible to improve the certified accuracy for $\\epsilon = 36/255$ and managed to achieve very good certified accuracy on ImageNet, which has not been done before. I find the results of this paper interesting because I think the overall problem is interesting and important, but I think the paper (in its current form) has little impact on the topic of certified accuracy with deterministic approaches. To improve the research value of the paper, the authors should provide a comprehensive ablation study and explain how and why these different techniques, when combined together, significantly improve certified accuracy. \n\n[1] Meunier et al., A Dynamical System Perspective for Lipschitz Neural Networks ICML 2022  \n[2] Araujo et al., A Unified Algebraic Perspective on Lipschitz Neural Networks, ICLR 2023  \n[3] Tsuzuku et al., Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks, NeurIPS 2018  \n[4] Farnia et al., Generalizable Adversarial Training via Spectral Normalization, ICLR 2019  \n[5] Leino et al., Globally-Robust Neural Networks, ICML 2021  \n[6] Singla et al. Improved deterministic l2 robustness on CIFAR-10 and CIFAR-100, ICLR 2022  \n[7] Trockman et al., Orthogonalizing Convolutional Layers with the Cayley Transform, ICLR 2021  \n[8] Singla et al, Skew Orthogonal Convolutions, ICML 2021  \n[9] Prach et al., Almost-Orthogonal Layers for Efficient General-Purpose Lipschitz Networks, ECCV 2022  \n[10] Huang et al., Training certifiably robust neural networks with efficient local Lipschitz bounds, NeurIPS 2021  \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> On the efficiency of the approach\n\nPerhaps *efficient calculation* in the following sentence from the Abstract causes some degree of misunderstanding: \n\n“A key challenge in certifying ResNets is efficient calculation of the Lipschitz bound for residual blocks.”\n\nWe would like to revise it as, “A key challenge in certifying ResNets is **efficiently calculating a _tight_ Lipschitz bound for residual blocks.**”\n\nWe are not claiming that using the power method is our contribution. The power method is more efficient than orthogonalization, which is relatively expensive, and used by a lot of prior work. However, as we point out, power iteration is not sufficient to provide _tight_ bounds on _traditional_ residual blocks. Our primary contribution is to identify the source of the problems faced by residual blocks, and propose a new design for residual blocks that achieves the necessary properties to avoid these pitfalls. Taken together, our proposed LiResNet architecture can be seen as _enabling_ efficient and tight bound-calculating with the power method, as the same results cannot be achieved using the same efficient bounds without our architecture (see the comparison of ResNet to LiResNet).\n\nWe will comment more on the computational cost in the author comment.\n\n> On the tightness of the bound\n\nIt is correct to say PM computes the an **exact** Lipschitz bound for $x+Wx$ if one uses the reparameterization trick to directly compute $Lip(I+W)$ instead of using the upper-bound $1+Lip(W)$, which is often used in conventional ResNet blocks. Thanks for the suggestion and we will make this point clearer in writing.\n\nAdditionally, we would like to share more results to showcase how switching from the conventional ResNet to LiResNet increases the tightness of the bounds:\n\nWe compare the empirical lower-bound of the Lipschitz Constant, obtained by maximizing |f(x) - f(y)|/|x - y| w.r.t randomly initialized $x$ and $y$ till convergence for a network $f$. Here are results when $f$ is a LiResNet or a ResNet trained on CIFAR-10. “UB” (upper bound) is our Lipschitz constant estimation and “LB” is the lower bound from maximizing |f(x) - f(y)|/|x - y|.\n\n|          | LB    | UB    | LB / UB |\n|----------|-------|-------|---------------------|\n| LiResNet | 53.35 | 59.03 | 0.90                |\n| ResNet   | 23.93 | 101.4 | 0.24                |\n\nFrom this table, we see that LiResNet can have a much tighter Lipschitz constant estimation than conventional ResNet. \n\n> On the new EMMA loss\n\nEMMA could be considered simple, but our proposal is not the result of trivially combining existing works. LMT has existed for a long time but has not been shown to perform well. Few following studies have used this loss function. Our paper chronicles a progressive evolution of methodologies leading up to the SoTA VRA, transitioning from LMT to EMMA. We have discovered that by using the LC of the margin and adjusting epsilon dynamically, there are consistent and incremental improvements in certifiable robustness. By delving into the training dynamics and observing how the second highest classes—termed as the “threatening classes”—rotate throughout iterations, we've pinpointed a suboptimal aspect in the TRADES loss function. Furthermore, we illustrate why EMMA is especially advantageous for problems with a larger number of classes, where existing loss functions like TRADES can grapple with the phenomenon portrayed in Figure 2b. We hope that the intricacies and depth of our exploratory efforts in training certified robustness aren't overshadowed by the apparent simplicity of the technique we advocate for.\n\n> What is the performance of the author's architecture with an SLL layer that is 1 Lipschitz?\n\nWe take the reviewer’s suggestion to replace linear residual blocks with SLL residual blocks and leave everything else the same (i.e. the whole network still has 12 convolution layers with 512 channels and 2 dense layers of 2048 neurons). We train both models in the same way (without any epsilon scheduler, DDPM, and etc.) and report the VRAs for a list of radii as suggested by the reviewer. For SLL models, we tried the models with 1) their default settings and 2) our optimization settings and reported the best VRAs. Here are our results on CIFAR-10/100 (other results will be in the revision of the paper):\n\n|           | epsilon | Using LiResNet Block | Using SLL Block  |\n|-----------|---------|----------------------|------------------|\n|           |  36/255 |   66.1               | 59.5             |\n| CIFAR-10  |  72/255 |   54.1               | 50.6             |\n|           | 108/255 |   45.2               | 42.2             |\n|           |  36/255 |   37.5               | 30.2             |\n| CIFAR-100 |  72/255 |   27.9               | 22.1             |\n|           | 108/255 |   22.1               | 16.5             |\n\n\n\n> How does the epsilon scheduler affect certified accuracy?\n\nNote that all of our ablation studies use the same epsilon scheduler setting. Thus, the difference between the VRAs of TRADES/ConvNet and EMMA/LiResNet in Table 2 reflects a difference that cannot be accounted for by the epsilon scheduler. On our largest model L12W512, turning the scheduler on introduces 0.4% VRA improvement on CIFAR-10.\n\n> How does the normalization trick affect certified accuracy?\n\nWe follow the same setting from [1, 2], which is a widely used method for normalization-free methods. Please note that this method is also applied by SLL (the diagonal scaling matrix q in Equation 8 from SLL paper). Again, all of our ablation studies use this same setting. On our largest model L12W512, using the normalization-free methods can introduce 0.8% VRA improvement on CIFAR-10.\n\n[1] Shao et al. Is normalization indispensable for training deep neural network, NeurIPS 2020\n\n[2] Zhang et al. Fixup Initialization: Residual Learning Without Normalization. ICLR 2018"}]

Author rebuttal:
We thank all reviewers for their valuable reviews. Here we respond to some questions that more than one reviewer are interested. 

- Expressiveness of LiResNet in standard training 

 We train LiResNet on ImageNet in the standard cross entropy setting and find that LiResNet is capable of achieving similar performance of a ResNet and a VGG-Net around the similar network depth. We follow the standard training settings to train classification models on ImageNet. Table 1 in the attached PDF shows the comparison with ResNet 18 and VGG 19.

- Comparison with prior work of the same size

When compared with previous work, it is hard to compare with exactly the same size since the backbone is different. In Table 1, we compare our results with the best reported results from previous work. Table 2 in the attached PDF shows the comparison of LiResNet and SLL (which is the current state of the art). SLL small has the similar model size and training speed with our largest LiResNet L12W512 while SLL X-Large is 4 times bigger and 4.5 times slower than our model. Our method can still outperform SLL X-Large under eps=36/255. The training speed is obtained using the official codes from SLL and the exact setting from the SLL paper.  All experiments are conducted on the same 4-GPU machine.

We further compare with SLL in a more fair setting (thanks Reviewer YimP for the motivation). We simply replace our proposed LiResNet block with SLL layer and use the same backbone setting: 12 convolutions with 512 channels and 2 linear layers with 2048 dimensions. In this comparison, our method and SLL has the same model size. Table 3 shows the comparison on CIFAR10 and CIFAR100 under different epsilons, and our proposed LiResNet block performs constantly better.  In this comparison, we do not use epsilon scheduling as Reviewer YimP wondered. For SLL models, we tried the models with 1) their default settings and 2) our optimization settings and reported the best VRAs. 


Meta-review: All reviewers agree that the studied problem is important and the experiments are thorough, though some reviewers have concerns on the expressiveness of LiResNets. The paper deserves acceptance. However, please revise the paper accordingly and address the reviewers' concerns in the camera-ready version.
Decision: Accept (poster)