Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Authors: Bo-Han Lai
Pin-Han Huang
Bo-Han Kung
Shang-Tse Chen
Venue: ICML 2025 spotlightposter (2025)
Keywords: Certified robustness
Adversarial
Primary area: deep_learning->robustness
TL;DR: We propose a new orthogonal convolution and a novel loss function to enhance certified robustness.

Abstract: Lipschitz neural networks are well-known for providing certified robustness in deep learning. In this paper, we present a novel, efficient Block Reflector Orthogonal (BRO) layer that enhances the capability of orthogonal layers on constructing more expressive Lipschitz neural architectures. In addition, by theoretically analyzing the nature of Lipschitz neural networks, we introduce a new loss function that employs an annealing mechanism to increase margin for most data points. This enables Lipschitz models to provide better certified robustness. By employing our BRO layer and loss function, we design BRONet — a simple yet effective Lipschitz neural network that achieves state-of-the-art certified robustness. Extensive experiments and empirical analysis on CIFAR-10/100, Tiny-ImageNet, and ImageNet validate that our method outperforms existing baselines. The implementation is available at [GitHub Link](https://github.com/ntuaislab/BRONet).

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Bo-Han Lai" Pin-Han Huang"
Bo-Han Kung"
Shang-Tse Chen
Abstract
BRONet
Lipschitz neural networks are well-known for pro- viding certified robustness in deep learning. In this paper, we present a novel, efficient Block Re- flector Orthogonal (BRO) layer that enhances the capability of orthogonal layers constructing more expressive Lipschitz neural architectures. In addition, by theoretically analyzing the nature of Lipschitz neural networks, we introduce new loss function that employs an annealing mecha- nism to increase margin for most data points. This enables Lipschitz models to provide better certi- fied robustness. By employing our BRO layer and loss function, design BRONet simple yet effective Lipschitz neural network that achieves state-of-the-art certified robustness. Extensive experiments and empirical amalysis on CIFAR- 10/100, Imageee,,,,,, and ImageNet validate that our method outperforms existing baselines. The implementation is available at GitH-ub Link
LiResNet
80
Clean Accuracy (%)
SOC+ CRC
.CLL
78
SOC
LOT
76
236M
74
136M
,SL
83M
72
AOL
63
64
66
67
68
69
70
71
Certified Robust Accuracy (%)
Figure I. Visualization of model performance on CIFAR- 10. The circle size denotes model size.
in practice, these approaches cannot provide robustness guarantees and may fail against more sophisticated attacks. Certified defenses, unlike empirical ones, provide provable robustness by ensuring no adversarial examples exist within an Ep norm ball of radius centered on the prediction point.
1. Introduction
Although deep learning has been widely adopted in various fields (Wang et al. 2022 Brown al. 2020), it is shown to be vulnerable adversarial attacks (Szegedy al., 2014). This kind of attack crafts an imperceptible perturbation images (Goodrellow al. 2014) or voices (Carlini & Wag-
Certified defenses against adversarial attacks are broadly categorized into probabilistic and deterministic (Li et al. 2023) methods. Randomized smoothing (Cohen et al. 2019 Lecuyer al.] 2019 Yang al., 2020) is prominent prob- abilistic approach, known for its scalability in providing certified robustness, However, its reliance on extensive sam- pling substantially increases computational overhead during inference, limiting its practical deployment. Furthermore, the certification provided is probabilistic in nature.
ner 2018) to make Al systems make incorrect predictions. In light of this, many adversarial defense methods have been proposed to improve the robustness, which can be catego- rized into empirical defenses and certified defenses. Com- mon empirical defenses include adversarial training (Madry
al., 2018 Shafahi al. 2019 Wang al. 2023) and preprocessing based methods (Samangouei et al. 2018 Das
Conversely, deterministic methods, exemplified by inter- val bound propagation (Ehlers) 2017 Gowal et al. 2018
et al. 2018 Lee & Kim 2023). Although often effective
Equal contribution 'Department of Computer Science and Information Engineering, National Taiwan University, Taiwan. Correspondence to: Shang-Tse Chen <stchen
Mueller et al.) 2023 Shi al. 2022) and CROWN (Wang
et al. 2021 Zhang et al. 2022), efficiently provide deter- ministic certification. These methods aim to approximate the lower bound of worst-case robust accuracy to ensure deterministic robustness guarantees. Among various de- terministic methods, neural networks with Lipschitz con-
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
straints are able to compute the lower bound of worst-case robust accuracy with single forward pass, making them the most time-efficient at inference time. They are known as Lipschitz neural networks.
2. Preliminaries
2.1. Certified Robustness with Lipschitz Networks
Consider a function f I + R". The function is said to exhibit L-Lipschitz continuity under the ε--norm if there exists a non-negative constant L such that:
Lipschitz neural networks are designed to ensure that the entire network remains Lipschitz-bounded. This constraint limits the sensitivity of the outputs input perturbations, thus providing certifiable robustness by controlling changes in the logits. A promising approach to constructing Lip- schitz networks focuses on designing orthogonal layers, which inherently satisfy the 1-Lipschitz constraint. Further- more, these layers help mitigate the issue of vanishing gra- dients due to their norm- com-preseriing properties. Nonetheless, existing methods for constructing orthogonal layers remain computationally expensive, thus hindering their integration into more sophisticated neural architectures.
[l f(22))
L Lip(
sup Z1.
(I)
|| x2ll
where ||-|| represents the lg norm. This relationship indicates that any variation in the network's s output, measured by the norm, is limited to at most times the corresponding varia- tion in its input. This property effectively characterizes the network's 's stability and sensitivity input changes. Specifi- cally, under the f--norm, the Lipschitz constant is equivalent to the spectral norm of the function's 's Jacobian matrix.
In this work, we introduce the Block Reflector Orthogonal (BRO) layer, which outperforms state-of-the-art orthogo- nal layers in terms of computational efficiency as well as robust and clean accuracy. We utilize it to develop various Lipschitz neural networks, underscoring its utility across architectures. Building upon the BRO layer, we introduce BRONet, a new Lipschitz neural network exhibiting promis- ing results.
Assuming fx) are the output logits of a neural network, and denotes the target label. We say f(x) is certifiably robust with a certified radius e if arg max; f(r + 6); = / for all perturbations {5 ||o|| S e). Determining the certified radii is crucial for certifiable robustness and presents a signifi- cant challenge. However, in L-Lipschitz neural networks, can be easily calculated using = max(0, M2 where Mz(x) denotes the logit difference between the ground-truth class and the runner-up class in the network output. That is, My = f(z), ((r))-man m1 f(z) Tsuzuku
Moreover, we delve into Lipschitz neural networks, analyz- ing their inherent limited capability. Building on this analy- sis, we introduce novel loss function, the Logit Annealing loss, which is empirically shown to be highly effective for training Lipschitz neural networks. The certification results of the proposed method outperform state-of-the-an art methods with reasonable number of parameters, as Figure D shows.
et 2018 et al. 2019p.
2.2. Lipschitz Constant Control & Orthogonality
Obtaining the exact Lipschitz constant for general neural networks is known to be an NP-hard problem (Virmaux & Scamann 2018). However, there are efficient methods available for computing it on layer-by-layer basis. Once the Lipschitz constant for each layer is determined, the Lipschitz composition property allows for the calculation of the overall Lipschitz constant for the entire neural network. The Lipschitz composition property states that given two functions f and g with Lipschitz constants T.y and T.g. their composition h = g o f is also Lipschitz with a constant La S Ly Ly- We can use this property to upper-bound the Lipschitz constant of complex neural network f:
Our contributions are summarized as follows:
We propose a novel BRO method to construct orthogo- nal layers using low-rank parameterization. is both time and memory efficient, while also being stable during training by eliminating the need for iterative approximation algorithms.
The proposed BRO Layer improves certified robustness while reducing the resource demands of orthogonal layers, thereby expanding their applicability to more advanced architectures.
1
We construct various Lipschitz networks using the BRO method, including newly designed BRONet, which achieves state-of-the- thetth--rtttteee certified robustness.
== δi 01 o.... 0 Lip(f) S Lip( (2)
Thus, if the Lipschitz constant of each layer is properly regulated, robust certification can be provided. A key rele- vant property is orthogonality, characterized by the isometry property ||>r| = ||||| for given operator W. Encour- aging orthogonality is crucial for controlling the Lipschitz constant while preserving model expressiveness (Anil et al.) 2019). as it avoids gradient vanishing. An illustrative exam- ple the replacement of common element- wise activations,
Based our theoretical analysis, we develop novel loss function, the Logit Annealing loss, which is ef- fective for training Lipschitz neural networks via an annealing mechanism.
Through extensive experiments, we demonstrate the effectiveness of our proposed method on the CIFAR- 10/100, Tiny- ImageNet, and ImageNet datasets.
2

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
such ReLU, with MaxMin (Anil et al. 2019 Chernodub & Nowicki 2016) in the Lipschitz network literature. While both are I-Lipschitz, MaxMin demonstrates superior empir- ical performance for being gradient-non preserving.
by Fazlyab et al. (0199)
Lipschitz Regularization While the aforementioned meth- ods control Lipschitz constant by formulating constrained layers with guaranteed Lipschitz bound, Lipschitz regular- ization methods estimate the layer-wise Lipschitz constant via power iteration (Farnia et al. (011 and apply regulariza- tion to control it. [eino et al. (202T) employed a Lipschitz regularization term to maximize the margin between the ground truth and runner-up class in the loss function. HHu et al. 2023: 2024) further proposed new Lipschitz regular- ization method Efficiently Margin Maximization (EMMA), which dynamically adjust all the non non-ground-trung logits before calculating the cross-entropy loss.
3. Related Work
Orthogonal Layers Orthogonality in neural networks is eru- cial for various applications, including certified robustness via Lipschitz--aare based methods, GAN stability (Mäller al.] 2019). and training very deep networks with inherent gradi- ent preservation (Xiao et al. 2018). While some approaches implicitly encourage orthogonality through regularization or initialization (Qi et al. 2020; Xiao et al. 2018), explicit methods for constructing orthogonal layers have garnered significant attention, as evidenced by several focused studies in this area. Li et al. (2019) proposed Block Convolution Orthogonal Parameterization (BCOP), which utilizes an iterative algorithm for orthogonalizing the linear transfor- mation within a convolution. [Trockman & Kolter (2021) introduced a method employing the Cayley transformation where V is a skew-symmetric matrix. Similarly, [Singla & Feizi (222b) developed the Skew- Kle--Orthggona Convolution (SOC), employing an expo- nential convolution mechanism for feature extraction. Addi- tionally. Xu et al. (2022) proposed the Layer-wise Orthogo- nal training (LOTT, an analytical solution to the orthogonal Procrustes problem (Schönemann 1966), formulated as
4. BRO: Block Reflector Orthogonal Layer
In this section, we introduce the BRO layer, designed to provide certified robustness via low-rank orthogonal param- eterization. First, we detail the fundamental properties of our method. Next, we leverage the 2D-convolution theo- rem to develop the BRO convolutional layer. Finally, we conduct a comparative analysis of our BRO with existing state-of-the-art orthogonal layers.
W = (I - (I + V)-1,
4.1. Low-rank Orthogonal Parameterization Scheme
The core premise of BRO revolves around a low-rank or- thogonal parameterization, as introduced by the following proposition. A detailed proof is provided in Appendix [A.]]
W = -VVV") V This approach requires the Newton method to approximate the internal matrix square root. Yu et al. (2022) proposed the Explicitly Constructed Orthogo- nal Convolution (ECO) to enforce all singular values of the convolution layer's ' Jacobian to be one.
Proposition 1. Let V E Rmxn be matrix of rank and, without loss of generality, assume m 2 n. Then the parameterization W= - - VV satisfies the following properties:
Notably, SOC and LOT achieve state-of-the-art certi- fied robustness for orthogonal layers. Most matrix re- parameterization-oet
W is orthogonal and symmetric, i.e., WT W and WTW- =
methods can be easily applied for dense layers, such as Cayley, SOC, and LOT. A recently pro- posed orthogonalization method for dense layers is Cholesky (Hu et al. 2024). which explicitly performs QR decomposi- tion on the weight matrix via Cholesky decomposition.
2. W is an r--ank perturbation of the identity matrix, i.e it has eigenvalues equal - and m n eigenvalues equal to 1.
3.
W degenerates to the negative identity matrix when V is a full-rank square matrix.
Other 1-Lipschitz Layers A relaxation of isometry con- straints, namely, ||a||| < ||=]|, facilitates the development of extensions to orthogonal layers, which are 1-L-isschitz layers. |Pach & Lampert (2022) introduced the Almost Or- thogonal Layer (AOL), which is rescaling based parameter- ization method. Meanwhile, Meunier et al. (2022) proposed the Convex Potential Layer (CPL), leveraging convex poten- tial flows to construct 1 1-Lipschitz layers. Building on CPL, Araujo et al. (2023) presented SDP-based Lipschitz Lay- ers (SLL., incorporating AOL constraints for norm control.
This parameterization draws inspiration from the block re- flector (Dietrich) 1976. Schreiber & Parlett 1988), which is widely used in parallel QR decomposition and is also important in other contemporary matrix factorization tech- niques. This approach enables the parameterization of an orthogonal matrix derived from a low-rank unconstrained matrix, thereby improving computational efficiency.
Most recently. |Wang& & Manchester (2023) introduced the Sandwich layer, a direct parameterization that analytically satisfies the semidefinite programming conditions outlined
Building on the definitive property of the proposition above, we initialize the parameter matrix V as non-square to pre- vent it from degenerating into a negative identity matrix.
3

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
While the above discussion focuses weight matrices for dense layers, the same parameterization can also be applied to construct orthogonal convolution operations, both are linear transformations. However, significant difference arises because the BRO formulation requires an inverse convolution computation, which is difficult to solve in the spatial domain. This leads us to address the issue the Fourier domain. Furthermore, it is essential to note that directly orthogonalizing each convolution kernel does not result in an orthogonal convolution (Achour et al. 2022).
103e
35
SOC
SOC
LOT
LOT
1025
30
Runtime (sec)
1020
Memory (GB)
20
10ts
10
To introduce the BRO convolution, we begin by defining the process given an unconstrained kernel E Rexxxxx where each slicing V.s..j is defined as in Proposition I Define FFT: R + C* as the 2D Fourier transform operator and FFT-1: C= + **x* as its inverse, where x denotes the spatial dimensions, and the input will be zero-padded to x if the original shape is smaller. The 2D convolution theorem @ainn 1989) asserts that the circular convolution of two matrices in the spatial domain corre- sponds to their element- wise multiplication the Fourier domain. Extending this idea, [Trockman & Kolter (2021) demonstrates that multi-channel 2D circular convolution in the Fourier domain corresponds to performing batch of matrix-vector products. By orthogonalizing each of these matrices, the convolution operation becomes orthogonal. Leveraging this insight, we can perform orthogonal convo- lution as follows.
lnta
5
1093
# Laaers
Figure 2. Comparison of runtime and memory usage among SOC, LOT, and the proposed BRO.
with an observation of minor norm drop resulting from the removal of output padding, is provided in Appendix (A.4 For layers where the input dimension differs from the output dimension, we enforce the 1-Lipschitz constraint via semi- orthogonal matrices. For details about the semi-orthogonal layers, please refer to Appendix A.3
Let X FF)(X) and V. FFT(V), the convolu- tion output is then computed as Y FFT (Y)
4.2. Properties of BRO Layer
This section compares BRO to SOC and LOT, the state-of- the-art orthogonal layers.
W.,. Keiiig.,.. where W..i. and Ying V...s)) Vii. and i,j are the pixel indices. 2V.... (V...,.VV.... (V...., Note that the FFT is performed the spatial (pixel) dimen- sions, while the orthogonal multiplication is applied on the channel dimension.
Iterative Approximation- Both LOT and SOC utilize iterative algorithms for constructing orthogonal convolution layers. Although these methods' error bounds are theoret- ically proven to converge to zero, empirical observations suggest potential violations of the 1-Lipschitz constraint. Prior work (Béthune et al. 2022) has noted that SOC's construction may result in non- I-Lipschitz layers due to ap- proximation errors inherent in the iterative process involving finite number of terms in the Taylor expansion. Regarding LOT, observe numerical instability during training due to the Newton method for orthogonal matrix computation. Specifically, the Newton method breaks the orthogonality when encountering ill-conditioned parameters, even with the 64-bit precision computation recommended by the authors. An illustrative example is that using Kaiming initialization He al.) (015)) instead of identity initialization results in non-orthogonal layer. Detailed experiments provided in Appendix D.7 In contrast, the proposed BRO constructs orthogonal layers without iterative approximation, ensuring both orthogonality and robustness certification validity.
Proposition 2. Let X FFT(X) Cexaxs and V FFT(V) E CoxXxXxx the proposed BRO convolution Y = FFT--(Y), where Y...j = W..... and W...o =I
2. (V. V. (Vi.ae V V.a.yyy is a real, orthogonal multi- channel 2D circular convolution.
Importantly, the BRO convolution is 2D circular convo- lution that is orthogonal, as demonstrated by Proposition] 2 Furthermore, although the BRO convolution primarily in- volves complex number computations in the Fourier domain,
the output Y remains real. The detailed proof of Proposi- tion is provided in Appendix(A.2 A.2
Algorithm D details the proposed method, illustrating the case where the input and output channels are equal to Following Xu et al. (2022). we zero pad the input and pa- rameters to size + 2k', where 2 the extra padding to alleviate the circular convolution effect across edges. A discussion on the implementation of zero-padding, along
Time and Memory Efficiency LOT's internal Newton method requires numerous steps to approximate the square
4

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Algorithm 1 BRO Convolution Layer
1: Input: Tensor X E IRexexe, Kernel V E IRxxxxxx with n S c, k' = |k/2].
Di e is channel size.
2: Output: Tensor Y E RgComeXxxe the orthogonal convolution applied to X parameterized by V.
3: X := zero_perr___ Sali_pa(((( X, (W', M, ".kkkk k)) E gex(*+2("x(*+25)
4: Vpad -errr_ppp vero_pad(V, (0, 0,8 + 2k' S, + 2k' - k)) E TRoxnx(e22))x(++a))
5: X FFF(()md) Cex(++2k) (xxx(++2")x(+422"
6: V- == FFT(VRB) E (xxxxx(++2")((++++))
7: for all i,j E {l,.................... } do
8: Y.u.j == (7 2V. V. mid Vess.) VV V
D Apply our parameterization.
9: end for
10: Y == ==FFT-(())
11: Return R; real
> Extract the real part.
root of the kernel, significantly prolonging training time and increasing memory usage. Conversely, the matrix op- erations in BRO are less complex, leading to substantially less training time and memory usage. Moreover, the low- rank parametrization characteristic of BRO further alleviates the demand for computational resources. When comparing BRO to SOC, BRO has an advantage in terms of inference time, SOC requires multiple convolution operations to compute the exponential convolution. Figure shows the runtime per epoch and the memory usage during training. A detailed analysis and comparison of orthogonal layers, including Cayley, are provided in Appendix A.5
set. The empirical Rademacher complexity of H over set S =x1, f2,,,2,......... #2..... ................................ Fnl is given by:
(H) E.
sup NEW
o,h(zz)
(3)
1=1
where o; are independent Rademacher variables uniformly sampled from {-1, Next, we use the Rademacher com- plexity demonstrate that model with low capacity results in a greater lower bound for margin loss risk.
Theorem 1. Given a neural network f and a set S of size n, let ey denote the ramp loss (a special margin loss, see Appendix C (Barllett et al.) 2017.. Let F represent the hypothesis set of f. Define that:
Non-universal Orthogonal Parameterization While a sin- gle BRO layer is not a universal approximator for orthogonal layers, as established in the second property of Proposition]]] ! empirically demonstrate in Section 6.2 that the expres- sive power of deep neural networks constructed using BRO is competitive with that of LOT and SOC.
F, (x11(x)) + (M((((()) v)) fe F}; R+(1)== E.L(M(((Z)).))
(4)
(5)
Assume that Pe is the prediction error probability. Then, with probability - 5, the empirical margin loss risk (f) is lower bounded by:
5. Logit Annealing Loss Function
Singla et al. (2022) posited that cross-entropy (CE) loss inadequate for training Lipschitz models, as it fails to increase the margin. Thus, they integrated Certifi- cate Regularization (CR) with the CE loss, formulated as: LcE max(M 0), where My(x)= = f(x); max f is the logit margin between the ground-truth class f and the runmer-up class. 7 max(My (z),0) is the CR term and y is hyper- peramepar However, our investigation identifies several critical issues associated with the CR term, such discontinuous loss gradient and gradient domination. Refer to Appendix for details.
In(1/0)
R-()) 2 P. (F, - -31
(6)
2n
Furthermore, for the I.-Lipschitz neural networks, we in- troduce the following inequality to show that the model complexity is upper- upper-bounded by L.
Proposition 3. (Ledoux & Talagrand 2013) Let F. be the hypothesis set of the L-Lipschitz neural network f. and E, is the ramp loss with Lipschitz constant 1 1/T, for some T > O. Then, given a set S size n, we have:
Our insight reveals that Lipschitz neural networks inher- ently possess limited model complexity. which impedes empirical risk minimization. Here, we utilize Rademacher complexity to justify that the empirical margin loss risk (Bartlett al. 2017) is challenging to minimize with Lip- schitz neural networks. Let H. represent the hypothesis
Rs E,
sup
Σ os o fxx))
FEF
E2
sup
7
n fer
L
||
5

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Table Comparison of proposed method with previous works. The pertrbation budget e for certified accuracy chosen following the convention of previous works. 1 For fair comparison, no additional diffusion
diffusion-generatee generated synthetic datasets are used during training.
Clean Acc.
Certified Acc. (e)
Datasets
Models
#Param.
255
255
255
Cayley Large Trockman & Kolter 2021
21M
74.6
61.4
46.4
32.1
SOC-20 Singlo 2023
27M
76.3
62.6
48.7
36.0
LOTT20
et M22
18M
77.1
64.3
49.5
CPL XL
236M
78.5
64.4
48.0
33.0
AOL Large (Prch & Lampert 2022
136M
71.6
64.0
56.4
49.0
CIFAR-10
SOC-20+CRC Singla
2022
40M
79.1
66.5
52.5
38.1
SLL X-Large Araujo nl.
2025
236M
73.3
64.8
55.7
47.1
LiResNet (Hu et 2024
83M
81.0
69.8
56.3
42,9
BRONet-M
37M
80.5
68.9
56.3
42.7
BRONet-L
68M
81.0
70.2
57.1
43.0
BRONet-M (+LA)
37M
81.2
69.7
55.6
40.7
BRONet-L (+LA)
68M
81.6
70.6
57.2
42.5
Cayley Large Trockmon
21M
43.3
29.2
18.8
11.0
SOC-20
Singla et al. 2022
27M
47.8
34.8
23.7
15.8
LOT-20
18M
48.8
35.2
24.3
16.2
CPL XL Meunier et al.
2022
236M
47.8
33.4
20.9
12.6
AOL Large
(Pach Lampert
2012
136M
43.7
33.7
26.3
20.7
S0C-20+CRC Singla Feizi
2023
40M
51.8
38.5
27.2
18.5
CIFAR-108
SI.I. X-LLarge
Araujo nl.
2023
236M
47.8
36.7
28.3
22.2
Sandwich
Wang Manchester
2023
26M
46.3
35.3
26.3
20.3
LiResNet
Hu 2024
83M
53.0
40.2
28.3
19.2
BRONet-M
37M
53.3
40.0
28.3
19.2
BRONet-L
68M
53.6
40.2
28.6
19.2
BRONet-M (+LA)
37M
54.1
40.1
28.5
19.6
BRONet-L (+LA)
68M
54.3
40.2
29.1
20.3
LiResNet HH 2024
98M
47.3
35.3
25.1
16.9
ImageNet
BRONet BRONet (+LA)
86M
48.8
36.4
25.8
17.5
86M
49.3
37.6
27.9
19.6
This is also known as Ledoux-Talagrand contraction (Ledoux & Talagrand| 2013). In Lipschitz neural networks, the upper bound is typically lower than in standard net- works due to the smaller Lipschitz constant L, consequently limiting (FF
The term encourages large margin for every data point simultaneously, which unlikely since the risk has great lower bound. Due to the limited capacity of Lipschitz mod- els, we must design a mechanism that enables models to learn appropriate margins for most data points. Specifically, when a data point exhibits large margin, indicating further optimizing it less beneficial, its loss should annealed to allocate capacity for other data points. Based on this idea, we design a logit annealing mechanism to modulate the learning process, gradually reducing loss values of the large-margin data points. Consequently, we propose a novel loss function: the Logit Annealing (LA) loss. Let f(x) represent the logits output by the neural network, and let the one-hot encoding of the true label t. We define the LA loss as follows:
According to Theorem [ the empirical margin loss risk exhibits a greater lower bound (F,,) is low. It is im- portant to note that the risk of the CR term, i.e., CR loss risk, is exactly the margin loss risk decreased by one unit when 1/7. That is RCR(F) = R, (f) 1. This indi- cates that CR loss risk also exhibits greater lower bound. Thus, it is unlikely to minimize the CR term indefinitely if the model exhibits limited Rademacher complexity. Note that limited Rademacher complexity can result from a low Lipschitz constant or large sample set. This also implies that we cannot limitlessly enlarge the margin in Lipschitz networks, especially for large wol-world datasets. Detailed proof's can be found in Appendix C
LLA (z, y) -T(11 p log (pt).
where p softmax( =
(8)
6

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Table Improvements of LA and BRONet compared I. LitesNet using diffusion data augmentation. The hest results of each datasct are marked in bold. Performance improvements and degradations relative to the baseline are marked in green and red, respectively.
Certified Acc. (E)
Clean Acc.
Datasets
Methods
36
72 255
108
255
LiResNet
87.0
78.1
66.1
53.1
CIFAR-10
+LA
86.7 (-0.3)
78.1 (+0.0)
67.0 (+0.9)
54.2 (+1.1)
(+EDM 4M)
BRONe++LA
87.2 (+0.2)
78.3 (+0.2)
67.4 (+1.3)
54.5 (+1.4)
LiResNet
61.0
48.4
36.9
26.5
CIFAR-100 100 (+EDM IM)
+LA
61.1 (+0.1)
48.9 (+0.5)
37.5 (+0.6)
27.6 (+1.1)
BRONe++LA
61.6 (+0.6)
49.1 (+0.7)
37.7 (+0.8)
27.2 (+0.7)
LiResNet
50.9
38.4
27.6
18.9
ImageNet (+EDM2 2M)
+LA
51.0 (+0.1)
39.4 (+1.0)
29.2 (+1.6)
20.6 (+1.7)
BRONet+LA
52.3 (+1.4)
40.7 (+2.3)
30.3 (+2.7)
21.6 (+2.7)
The hyper-parameters temperature T and offset [ are
= =-36/255 36/255. On the ImageNet dataset, our method achieves state-of-the performance, highlighting its scalability. No- tably, BRONets attain these results with a reasonable num- ber of parameters. Additional results for the Tiny Imageeet experiments are provided in Appendix D.
adapted from the loss function in Prach & Lampert (2022) for margin training. The term (1 p,) referred to
the annealing mechanism, draws inspiration from the Fo- cal Loss (Lin et al. 2017). During training, the LA loss initially promotes moderate margin for each data point, subsequently annealing the data points with large margins as training progresses. Unlike the CR term, which encourages aggressive margin maximization, our method employs a bal- anced learning strategy that effectively utilizes the model's ss capacity, especially when it is limited. Consequently, the LA loss allows Lipschitz models to learn an appropriate margin for most data points. Appendix C provides more details on the LA loss.
6.2. Ablation Studies
Extra Diffusion Data Augmentation As demonstrated in previous studies (Hu et al., 2024, Wang al.) 2023). in- corporating additional synthetic data generated by diffusion models such as elucidating diffusion model (EDM) (Karras) et al. 2022) can enhance performance. We evaluate the effectiveness of our method in this setting, using synthetic datasets publicly released from Hu et al.) (2024); WWan et al.) (2023) for CIFAR-10 10 and CIFAR- 100, which contain post- filtered 4 million and 1 million images, respectively. For ImageNet, we generate 2 million 512x512 images using the script recommended by EDM2 with autoguidance (Kar ras et al. 2024b a). Table 2 presents the results, showing that combining LA and BRO effectively leverages these synthetic datasets enhance performance.
6. Experiments
In this section, we first evaluate the overall performance of our proposed BRONet against the l certified robustness baselines. Next, to further demonstrate the effectiveness of the BRO layer, we conduct fair and comprehensive evalua- tions on multiple architectures for comparative analysis with orthogonal and other Lipschitz layers in previous literature. Lastly, we present the experimental results and analysis on the LA loss. See Appendix B for implementation details.
Backbone Comparison As the improvements in the pre- vious work by Hu et al. (2024) primarily stem from us- ing diffusion-generant
synthetic datasets and architectural changes, we conduct a fair and comprehensive comparison of different Lipschitz convolutional layers using the default convo-
6.1. Main Results
LiResNet architecture (with Lipschitz-regulariin lutional layers), along with LA and diffusion-based data augmentation. The only modification is swapping out the convolutional backbone layers. It is important to note that for FFT-based orthogonal layers (excluding BRO), we must reduce the number of backhone layers to stay within mem- ory constraints. LOT has the fewest parameters due to its costly parameterization. With half-rank parameterization in BRO, the number of parameters for BRO, Cayley, and
We compare BRONet to the current leading methods in the literature. Figure T presents visual comparison on CIFAR-10. The circle size indicates the number of model parameters. Furthermore, Table detaails the clean accuracy, certified accuracy, as well as the total number of parame- ters. For reference, we present the results of the proposed BRONet both with and without the LA loss function. On CIFAR-10 and CIFAR- 100, our model achieves the best clean and certified accuracy with the Eg perturbation budget

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Table Comparison of clean and certified accuracy using different Lipschitz convolutional backhones. The hest results marked in bold. #Layers is the number of convolutional backbone layers, and #param. is the number of parameters in the constructed architecture.
Conv. Backbone
CIFAR-10 (+EDM)
CIFAR-106 10000-100 (+EDM)
#laaers
#Param.
Clean
36
72
108
Clean
72
108
255
255
255
255
255
255
LOT
59M
85.7
76.4
65.1
52.2
59.4
47.6
36.6
26.3
Cayley
6
68M
86.7
77.7
66.9
54.3
61.1
48.7
37.8
27.5
Cholesky
68M
85.4
76.6
65.7
53.3
59,4
47.4
36.8
26.9
SLL
12
83M
83.6
76.8
66.0
53.3
59.4
47.6
36.6
27.0
SOC
83M
86.6
78.2
67.0
54.1
60.9
48.9
37.6
27.8
Lip-reg
12
83M
86.7
78.1
67.0
54.2
61.1
48.9
37.5
27.6
BRO
12
68M
87.2
78.3
67.4
54.5
61.6
49.1
37.7
27.2
Table 4. Comparison of clean and certified accuracy with different orthogonal layers in LipConwNets (Depth-Widthl Instances marked with a dash (-) indicate out memory during training. The best results with each model are marked with bold.
CIFAR-100
Tiny-ImageNet
Model
D-W
Layer
Clean
36
72
108
Clean
36
72
108
255
SOC
47.5
34.7
24.0
15.9
38.0
26.5
17.7
11.3
(10-32)
LOT
49.1
35.5
24.4
16.3
40.2
27.9
18.7
11.8
BRO
48.6
35.4
24.5
16.1
39.4
28.1
18.2
11.6
LipConvNet (+LA)
SOC
48.2
34.9
24.4
16.2
38.9
27.1
17.6
11.2
(10-48)
LOT
49.4
35.8
24.8
16.3
BRO
49.4
36.2
24.9
16.7
40.0
28.1
18.9
12.3
SOC
48.5
35.5
24.4
16.3
39.3
27.3
17.6
11.2
(10-64)
LOT
49.6
36.1
24.7
16.2
BRO
49.7
36.7
25.2
16.8
40.7
28.4
19.2
12.5
LipConvNet constructed by BRO layers compares favor- ably to the other orthogonal layers. Furthermore, due the nature of its low-rank parametrization property, BRO layers require the fewest parameters and reasonable runtime. Detailed comparisons are provided in Appendix D.6
Table Ablation study on the components contributing to the improvement on the ImageNet dataset.
Clean Acc.
Certified Acc. (e)
LA Arch
BRO
72
108
255
255
255
Improvement on ImageNet Compared to LiResNet on ImageNet, we have made three key modifications: intro- ducing the BRO convolutional layers, incorporating the LA loss, and making architectural adjustment-repllccinn the 1-Lipschitz learnable downsampling layer with norm- preserving &g -orm pooling. Table Sablesspreeentt the ablation study on the components, demonstrating that the combina- tion of all three components yields the best performance.
x
x
47.3
35.3
25.1
16.9
/
X
x
47.8
36.6
26.7
18.7
/
48.8
37.1
26.8
18.8
/
49.3
37.6
27.9
19.6
Cholesky remain consistent, while SLL, SOC, and Lipschitz- regularized retain the original number parameters. The results in Table 3 indicate that BRO the optimal choice compared to other layers in terms of overall performance.
6.3. LA Loss Effectiveness
Table and illustrates the performance improvements achieved using the proposed LA loss. We also provide extensive ablation experiments in Appendix D.4 validate its effectiveness on LipConvNets. Our experiments show that the LA loss promotes a balanced margin, especially for models trained more challenging datasets.
LipConvNel Benchmark To further validate the effective- ness of BRO, we evaluate it on LipConvNets, a standard lightweight architecture widely used in the literature on orthogonal layers. Table 4 Iillustrates the certified robust- ness SOC, LOT, and BRO layers. is evident that the
8

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
7. Conclusion
Table 6. The statistics of certified radius distribution.
In this paper, we introduce a novel BRO layer that fea- tures low-rank parameterization and free from iterative approximations. As a result, it is both memory and time efficient compared to existing orthogonal layers, making it well-suited for integration into advanced Lipschitz ar- chitectures. Furthermore, comprehensive experimental re- sults have shown that BRO is one of the most promising orthogonal convolutional layers for constructing expressive Lipschitz networks. Next, we address the limited complex- ity issue of Lipschitz neural networks and introduce the Logit Annealing loss function to help models learn appropriate margins. Extensive experiments on CIFAR-10 10, CIFAR-100, Iiny-ImageNer, and ImageNet validate the ef- fectiveness of the proposed methods over existing baselines. Moving forward, the principles and methodologies this paper could serve as foundation for future research in certifiably robust network design.
Loss
Median
Variance
Skewness
CE
0,2577
0,0732
1.21
CE+CR
0,2750
0.1000
1,4843
LA
0,2840
0.0797
1.0539
0.7
Training
0.6
LA
CE
Certified accuracy
0.5
CE+CR
Test
0.4
LA
CE
0.3
CE+CR
0.2
0.1
A Acknowledgment
0.0
This work was supported in part by the National Science and Technology Council (NSTC) under Grants NSTC 1 113-
0.0
0.1
0.2
0.3
0.4 Radius
0.5
0.6
0.7
0.8
2222-E-002-004-MYY2 NSTC 113-2634-F-002-007, NSTC 113-2634 -01KKK and NSTC 113-2923-E-4 E--022- 010-MY2, as well as by the Featured Area Research Center Program within the Higher Education Sprout Project of the Ministry of Education (Grant 1339900933). In addition, we thank the National Center for Higghperffrmance Computing (NCHC) for providing computational and storage resources. We also appreciate the constructive comments received from anonymous reviewers, which substantially improved both the clarity and depth our presentation.
Figure 3. Certified accuracy with respect radius. The LA loss helps learn appropriate margin.
To demonstrate that the LA loss enables learning an appro- priate margin for most data points, we further investigate the certified radius distribution. Following Cohen et al. (2019), we plot the certified accuracy with respect to the radius on CIFAR-100 to visualize the margin distribution in Figure 3 The certified radius is proportional to the margin in Lips- chitz models. Thus, the x-axis and y-axis can be seen as margin and complementary cumulative distribution of data points, respectively (Lecuyer et al. 2019).
Impact Statement
This work aims to enhance the robustness and reliability of deep neural networks, ultimately contributing to the de- velopment trustworthy AI systems. Consequently, has the potential for positive societal impact. However, we also recognize two potential negative implications. The first con- cern is adversarial misuse. While this method improves the robustness and reliability of machine learning models, there is a risk that it could be exploited for malicious pur- poses. For example, more secure and robust models might be weaponized in applications such as surveillance systems or autonomous malicious agents. The second concern re- lates to resouree utilization. Although this method is more memory-efficient than other approaches, the overall com- putational and energy costs associated with large-scale de- ployment still need to be considered, particularly in cloud computing environments.
The results indicate that the number of data points with appropriate margins increases, which is evident as the red curve rises higher than the others at the radius between [0.0,0.00 Moreover, the clean accuracy, which corresponds to certified accuracy at zero radius, also observed to be slightly higher. This suggests that the LA loss does not compromise clean accuracy for robustness. To better charac- terize the annealing mechanism, we analyze the distribution of the certified radius across the data points, as shown in 6 Compared to CR, the LA loss reduces both the pos- itive skewness and variance of the distribution, indicating a rightward shift the peak and decrease in the dispersion of the radius. This suggests that LA loss helps mitigate the issue of overfitting to certain data points and improves the certified radius for most points. Additional experiments, including ablation studies on BRO rank and the LA loss, are presented in Appendix
9

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
References
ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), 2018.
Achour, E. M., Malgouyres, F., and Mamalet, F. Existence, stability and scalability of orthogonal convolutional neu- ral networks. Journal of Machine Learning Research (JMLR), 2022.
Dietrich, G. A new formulation of the hypermatrix householder-QU decomposition. Computer Methods in Applied Mechanics and Engineering, 9(3):273-222 1976.
Anil, C., Lucas, J., and Grosse, R. Sorting out Lipschitz function approximation. In International Conference on Machine Learning (ICML), 2019.
Dozat, T. Incorporating Nesterov momentum into Adam. International Conference on Learning Representations workshop (ICLR workshop), 2016.
Araujo, A., Havens, A. J., Delattre, B., Allauzen, A., and Hu, B. A unified algebraic perspective on Lipschitz neu- ral networks. In International Conference on Learning Representations (ICLR), 2023.
Ehlers, R. Formal verification of piece-wise linear feed- forward neural networks. In International Symposium on Automated Technology for Verification and Analysis (ATVA), 2017.
Bartlett, P. L., Foster, D. J.. and Telgarsky, M. J. Spectrally- normalized margin bounds for neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Engstrom, L., Ilyas, A., and Athalye, A. Evaluating and understanding the robustness of adversarial logit pairing. arXiv preprint 0rXiv://07) 10272, 2018
Béthune, L., Boissin, T., Serrurier, M., Mamalet, F., Friedrich, C., and Gonzalez Sanz, A. Pay attention to your loss: understanding misconceptions about Lipschitz neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Farnia, F., Zhang, J., and Tse, D. Generalizable adversar- ial training via spectral normalization. In International Conference on Learning Representations (ICLR), 2019.
Fazlyab, M., Robey, A., Hassani, H., Morari, M., and Pap- pas, G. Efficient and accurate estimation of Lipschitz constants for deep neural networks. In Advances in Neu- ral Information Processing Systems (NeurIPS), 2019.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., al. Language models are few-shot learners. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Goodfellow, I. J., Shlens, J., and Szegedy, C. Explain- ing and harnessing adversarial examples. arXiv preprint arXiv: MeXiv:/412..0 442.6572, 2014.
Carlini, N. and Wagner, D. Audio adversarial examples: Targeted attacks on speech-to-text. In IEFE security and privacy workshops (SPW), 2018.
Gowal, S., Dvijotham, K., Stanforth, R., Bunel, R., Qin, C., Uesato, J., Arandjelovic, R., Mann, T., and Kohli, P. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 10X0v:8110.121101 2018
Chen, T., Zhang, Z., Liu, S., Chang, S., and Wang, Z. Ro- bust overfitting may be mitigated by properly learned smoothening. In International Conference on Learning Representations (ICL.R, 2021.
He, K., Zhang, X.,
Ren, S., and Sun, J. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE Inter- national Conference on Computer Vision (ICCV), 2015.
Chernodub, A. and Nowicki, D. Norm-preserving orthogo- nal permutation linear unit activation functions (OPLU). arXiv preprint arxiv: 1604.02313, 2016.
Hu, E. J., Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, L., Chen, W. et al. Lora: Low-rank adaptation of large language models. In International Conference on Learn- ing Representations (ICLR), 2022.
Cohen, J., Rosenfeld, F., and Kolter, Z. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning (ICML), 2019.
Croce, F. and Hein, M. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-fiee free at- tacks. In International Conference on Machine Learning (ICML), 2020.
Hu, K., Zou, A., Wang, Z., Leino, K., and Fredrikson, M. Unlocking deterministic robustness certification on Im- agenet. In Advances in Neural Information Processing Systems (NeurIPS). 2023.
Das, N., Shanbhogue, M., Chen, S.-T., Hohman, F., Li, S., Chen, L.,, Kounavis, M. E.,, and Chau, D. H. Shield: Fast, practical defense and vaccination for deep learn- ing using jpeg compression. In Proceedings of the 24th
Hu, K., Leino, K., Wang, Z., and Fredrikson, M. A recipe for improved certifiable robustness. In The Twelfth Inter- national Conference on Learning Representations (ICLR), 2024.
10

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Jain, A. K. Fandamentals of digital image processing. Prentice- Hall, Inc., 1989.
Meunier, L., Delattre, B. J., Araujo, A., and Allauzen, A. A dynamical system perspective for Lipschitz neural net- works. In International Conference on Machine Learning (ICML), 2022.
Karras, T., Aittala, M., Aila, T., and Laine, Elucidating the design space of diffusion-based generative models. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- tions of machine learning. MIT press, 2018.
Karras, T., Aittala, M., Kynkäänniemi, T., Lehtinen, J., Aila, T., and Laine, S. Guiding a diffusion model with bad version of itself. In Advances in Neural Information Processing Systems (NeurIPS), 2024a.
Mueller, M. N., Eckert, F., Fischer, M., and Vechev, M. Certified training: Small boxes are all you need. In The Eleventh International Conference Learning Repre- sentations (ICLR), 2023.
Karras, T., Aittala, M., Lehtinen, J., Hellsten, J., Aila, T., and Laine, S. Analyzing and improving the training dynamics of diffusion models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2024b.
Müller, J., Klein, R., and Weinmann, M. Orthogonal wasser- stein gans, arXiv preprint arXiv: 1310000 2019.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., al. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Lecuyer, M., Atlidakis, V., Geambasu, R., Hsu, D., and Jana, S. Certified robustness to adversarial examples with differential privacy. 2019 IEEE Symposium on Security and Privacy (SP), 2019.
Prach, B. and Lampert, C. H. Almost-orthogont layers for efficient general-purpose Lipschitz networks. In Euro- pean Conference Computer Vision (ECCV), 2022.
Ledoux, M. and Talagrand, M. Probability Banach Spaces: isoperimetry and processes. Springer Science & Business Media, 2013.
Prach, B., Brau, F., Buttazzo, G., and Lampert, C. H. 1- Lipschitz layers compared: Memory, speed, and certifi- able robustness. arXiv preprint arXiv:2311.1688. 2023.
Lee, M. and Kim, D. Robust evaluation of adversarial purification. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), 2023.
Qi, H., You, C., Wang. X., Ma, Y., and Malik, J. Deep isometric learning for visual recognition. In International Conference on Machine Learning (ICML), 2020.
Leino, K., Wang, Z., and Fredrikson, M. Globally-robust neural networks. In International Conference on Machine Learning (ICML), 2021.
Samangouei, P., Kabkab, M., and Chellappa, R. Defense- gan: Protecting classifiers against adversarial attacks us- ing generative models. In International Conference on Learning Representations (ICLR), 2018.
Li, L., Xie, T. and Li, B. Sok: Certified robustness for deep neural networks. In 2023 IEEE symposium security and privacy (SP), 2023.
Schönemann, P. H. A generalized solution of the orthogonal procrustes problem. Psychometrika, 31(1):1-10, 1966.
Li, Q., Haque, S., Anil, C., Lucas, J., Grosse, R. B., and Jacobsen, J. Preventing gradient attenuation in Lips- chitz constrained convolutional networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Schreiber, R. and Parlett, B. Block reflectors: Theory and computation. SIAM Journal on Numerical Analysis, 25 (1:11992055. 1988.
Lin, T.-Y., Goyal, P., Girshick, R., Hc, K., and Dollar, P.
Shafahi, A., Najibi, M., Ghiasi, M. A., Xu, Z., Dickerson, J., Studer, C.,, Davis, L. S., Taylor, G., and Goldstein, T. Adversarial training for free! Advances in Neural Information Processing Systems (NeurIPS), 2019.
Focal loss for dense object detection. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2017.
Madry. A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. In International Conference on Learn- ing Representations (ICLR), 2018
Shi, Z., Wang, Y., Zhang, H., Kolter, J. Z., and Hsieh, C.-J. Efficiently computing local Lipschitz constants of neural networks via bound propagation. In Advances Neural Information Processing Systems (NeurIPS), 2022.
Mao, Y., Müller, M., Fischer, M., and Vechev, M. Con- necting certified and adversarial training. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
Singla, S. and Feizi, S. Fantastic four: Differentiable bounds on singular values of convolution layers. In International Conference on Learning Representations (ICLR), 2021 la

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Singla, S. and Feizi, S. Skew orthogonal convolutions. In International Conference Machine Learning (ICML), 2021b.
Xu, X., Li, L., and Li, B. LOT: Layer-wise orthogonal training on improving 12 certified robustness. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Singla, S. and Feizi, S. Improved techniques for determin- istic 12 robustness. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Yang, G., Duan, T., Hu, E., Salman, H., Razenshteyn, I., and Li, J. Randomized smoothing of all shapes and sizes. In International Conference Machine Learning (ICML), 2020.
Singla, S., Singla, S., and Feizi, Improved deterministic 12 robustness on CIFAR-10 10 and CIFAR-100, In Interna- tional Conference Learning Representations (ICLR), 2022.
Yu, T., Li, J., Cai, Y., and Li, P. Constructing orthogo- nal convolutions in an explicit manner. In International Conference on Learning Representations (ICLR), 2022.
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. Intriguing proper- ties of neural networks. In International Conference on Learning Representations (ICLR), 2014.
Zhang, H., Wang, S., Xu, K., Li, L.., Li, B., Jana, S., Hsich, C.-.. and Kolter, J. Z. General cutting planes for cuunddpropagation-bae
neural network verification. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Trockman, A. and Kolter, J. Z. Orthogonalizing convolu- tional layers with the Cayley transform. In International Conference on Learning Representations (ICLR), 2021.
Zhang, M., Lucas, J., Ba, J., and Hinton, G. Lookahead optimizer: steps forward, step back. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Tsuzuku, Y., Sato, I., and Sugiyama, M. Lipschitz-maree training: Scalable certification perturbation invariance for deep neural networks. In Advances in Neural Infor- mation Processing Systems (NeurIPS), 2018
Virmaux, A. and Scaman, K.
Lipschitz regularity of deep neural networks: analysis and efficient estimation. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Wang, C.-Y., Bochkovskiy, A., and Liao, H.-Y. M. Yolov7: Trainable bag-of- sets new state-of- the-art for real-time object detectors. arXiv preprint arXiv:2207.02666, 2022.
Wang, R. and Manchester, I. Direct parameterization of Lipschitz-bounde deep networks. In International Con- ference on Machine Learning (ICML), 2023.
Wang, S., Zhang, H.. Xu, K., Lin, X., Jana, S., Hsieh, C.JJ, and Kolter, Z. Beta-crown: Efficient bound propagation with per-neuron split constraints for neural network robustness verification. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Wang, Z., Pang. T., Du, C., Lin, M., Liu, W., and Yan, S. Better diffusion models further improve adversarial train- ing. In International Conference on Machine Learning (ICML), 2023.
Xiao, I.., Bahri, Y., Sohl-Dickstein, J., Schoenholz, S., and Pennington, J. Dynamical isometry and a mean field theory of cnns: How to train 10,000-layer vanilla convo- lutional neural networks. In International Conference on Machine Learning (ICML), 2018
12

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Appendix
Table of Contents
A BRO Layer Analysis
14
Proof of Proposition
14
Proof of Proposition
Implementation Details and Analysis Semi--rtmmmoaeeee Layer
A.4
The Implementation and Effect of Zero-palding
17
A.5
Complexity Comparison of Orthogonal Layers
Implementation Details
B.
Computational Resources
20
B
2
Architecture Details
20
B.3
Architecture and Rank-n n Configuration
23
B.4
LA Hyper-parameters
23
B.S
Detail
23
B.6
Detall
23
B.7
Details
23
B.
Detall
23
C Logit Annealing Loss Function
24
Proof of Theorem
24
CR Loss Risk
25
CR Issues
26
Annealing Mechanism
27
Additional Experiments
D.I Additional Iiny-ImageNet Results for Table
28
D.2
Empirical Robustness
28
D.3
BRO Rank-n Ablation Experiments
28
D.4
LA Ablation Experiments
29
D.5
Loss Hlperr-parameters Experiments
29
D.6
LipConwNet Ablation Experiments)
30
D.7
Instability of LOT Parameterization
30
Limitations
32
13

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
A. BRO Layer Analysis
A.1. Proof Proposition
Proposition 1. Let V E [R be a matrix of rank n, and, without loss of generality, assume m 2 n. Then the parameterization W =I =I-2V satisfies the following properties:
1. is orthogonal and symmetric, i.e., T = W and WTW = I.
2. is an n-rank perturbation of the identity matrix, ie.. it has n eigenvalues equal to -1 and m n eigenvalues equal
to
3. degenerates to the negative identity matrix when is a full-rank square matrix.
Proof. Assuming V is defined in Proposition 1 orthogonality of W, however, requires confirmation that the following condition is satisfied:
the symmetry of this parameterization is straightforward to verify. The
ww (I - VV -V
(I VV((VVV)=VV" -V20""))))))))"")
--VV(V"V)-VV" -NV
-" - +4V(1"1)-112 I.
Next, define {11, 02,
] as the set of column vectors of Let e; denote the i-th standard basis vector in R".
Then, have
Wo: VV(VVV
= U, VV(
VV
U VV -V("")-((VVVV) (VTV)e
2Ve.
= 20 = -tt-
(10)
For the vectors in the orthogonal complement of S, denoted by S {un+1, 2,42, Um we have
We; - -1-2V 2V- -
(11)
The equality holds because, for all v; S-, we have V U; 0.
Therefore, the eigenspace corresponding to eigenvalue -1 is spanned by S, while the eigenspace corresponding to eigenvalue 1 is spanned by S-L.
Assume V is full-rank square matrix, which implies that V is invertible, Thus:
W / - 2V VV
= I 2VV 2VV-
= - 2I
-I
(12)
Thus, the proof is complete.
14

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
A.2. Proof of Proposition 2
Before providing rigorous mathematical proof, we first outline the intuitive rationale. To demonstrate that BRO convolution is orthogonal, show that each component in the convolution pipeline is orthogonal. This pipeline comprises three orthogonal transformations:
1. Fourier Transform: Transforms the input from the spatial domain to the Fourier domain.
2. BRO Matrix Multiplications: Applies the Block Reflector Orthogonal (BRO) matrices in the Fourier domain.
3. Inverse Fourier Transform: Converts the output back to the spatial domain.
Consequently, the input undergoes sequence of orthogonal operations, ensuring norm preservation. Importantly, an essential part of the analysis is the application of the 2D convolution theorem, which establishes an equivalence between convolution in the spatial domain and pointwise multiplication in the Fourier domain.
Proposition 2. Let X = FFT(X) E Coxaxs and V FFT(V) E Cexaxaxs the proposed BRO convolution Y FFT where Y.J.j W.n..j X.3. and W..... -Vanas (Vi.n channel 2D circular convolution.
(Vans) - Ving is a real, orthogonal multi-
Proof. To establish the results Proposition 2, first present several supporting lemmas.
Lemma 1. (2D convolution theorem) Let X, W Rax and F E Rxxs i.e. the DFT is applied to the rows and columns of X. In addition, let the 2D circular convolution of X with W be convw (X) E Baxx, It follow that
s be the DFT matrix. Then, X FFT(X) FXF,
= FWF FXF FFonv (X)F,
where @ is the element-wise product.
Next, we introduce the multi-channels 2D circular convolution. Following Trockman & Kolter (202T), we flatten the four-dimension tensors into matrices facilitate the analysis. Let an input image with Gin input channels represent X R it can be vectorized into = [vec" vec (X",,) E geas", Similarly, the vectorized output vec"((Yeaa) (Yr Sauss Then, we have 2D circular convolution operation with C E Reaas Xcas such y = [vec" (Yi)...., vec"
that y = CX. Note that C has Cout X Gin blocks with size s2 x s².
Lemma 2. Trockman & Kolter 2021 Corollary A. 1) ) IfC E Re xc..² represents a 2D circular convolution with Gn input channels and Cout output channels, then it can be block diagonalized as
F CF Cin
D,
(13)
where F. Se,z (Te & (F F)), Se,z² is permutation matrix, In is the identity matrix of order k. and DD is block diagonal with 5² blocks of size Cout Cin. Note that & is the Kronecker product.
Lemma 3. Consider J E CP as unitary matrix. Define V and V such that V = JVJ", where V E Rex and V E CPPP. Let BR)(V) = VV(VVV)-VV be our parameterization Then,
BRO(V) JB)
(14)
Proof. Assume J and V are as defined in Lemma
Then
J'BRO(V) = JI 2V
- --20JJ/A711(00>>>>)>))((>>"
-2(78)("VV = - -22
BROO(V)
15

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
The equality (+) holds because
(\"v)
We begin the proof under the assumption that the number of input channels equals the number of output channels, i.c., Gin Cout According to Lemma the stacked weight matrix C E IR Coues Xene" can be diagonalized as follows:
C=
(15)
where F² and Fe are unitary matrices, and D is block diagonal matrix.
Note that since D is block diagonal, the BRO transformation of 'D can be expressed as:
(RO BR) @ BRO e .... BRO(D:*),
where ( denotes the direct sum. This is because each block Dj: for k = 1, s² is independently transformed by the BRO operation. Additionally, because the original weight matrix C is real, the BRO convolution BRO(C) remains real as well.
Applying Lemma] on Equation 13 we consider a real vectorized input X. The output of the BRO convolution is given by:
y BRO(C) = BRO())
(16)
This ensures that y/ is real. Consequently, Algorithm is guaranteed to produce a real output when given a real input X.
Finally, the orthogonality of the BRO convolution operation (RO(C) can be derived as follows. Since both F and Fe are unitary matrices (Trockman & Kolter 2021), and BRO(D) is unitary as well, the composition these unitary operations preserves orthogonality.
Thus, we have established that the BRO convolution operation, BRO(C), is both orthogonal and real, thereby completing the proof of Proposition 2
A.3. Implementation Details and Analysis of Semi-Orthogonal Layer
To derive the parameterization of semi cemioorthogonal matrices, we first construct an orthogonal matrix W and then truncate to the required dimensions. Specifically, for BRO convolution, let the input and output channel sizes be Gi and Couts respectively. Define с = max((Com Cout, Cnn. For each index and j, we parameterize V..a. Cexn as Wi.dd E Cexe, which is then truncated to W. W. E XCn
In the following, we provide the detailed analysis of semi-orthogonal BRO layers, which can be categorized into two types: dimension expanding layers and dimension reduction layers. To facilitate understanding, we begin with the dense version of BRO (a single 2D matrix).
For an expanding layer constructed with W E xd., where din < doat. it satisfies the condition WTW La.. Since the condition is equivalent to ensure that the columns are orthonormal, the norm of vector is preserved when projecting onto its column space, which means
W x|| = ||>||| for every x E Rdo,, thus, ensures I-Lipschitz property.
For a reduction layer constructed with W E Xdu,, where dm > douts satisfies the condition WW = Id... Unlike expanding layers, the columns of W reduction layers cannot be orthonormal due to the dimensionality constraint din dout- Consequently, we have the following relationship for every x E Rd,,, | < ||>||] The equality holds if lies entirely within the subspace spanned by the rows of W. In general, reduction layers do not preserve the norm of input vectors. However, they remain i-Lipschitz bounded, ensuring that the transformation does not amplify the input norm.
The same principles apply to BRO convolution. The primary difference between the dense and convolution versions of BRO layers arises from the dimensions they are applied to. Therefore, the results discussed for BRO dense layers also hold for BRO convolution layers. Figure 4 visualizes BRO convolution under three different dimensional settings, illustrating the behavior of channel-expandngg and channel-reduction operations in convolutional contexts.
16

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
W.igieJ X X
Y...
Cin
pixel
pixel
pixel
Cout
W...i
X ;
Y,..j
Cin Cout
X
Cin =
Cout
Cin <
Cout
X
Cin
=
Cout
Cin
>
Cout
X
Cin
Cout
Figure Visualization of BRO convolution for different cın and Cous-
A.4. The Implementation and Effect of Zero-padding
Following Xu et al. 2022), we apply zero-padding on images X E [Rexexs, creating Xpad E (1xx(=+2")x(=+21) before performing the 2D FFT. After applying FFT-1, we obtain Ypad E [B<x(++2""x(x==x2 from which the padded pixels are removed to restore the original dimensions of X, resulting in Y Rexaxs This approach leverages zero pero--adding to alleviate the effect of circular convolution across edges, which empirically improves performance. Note that the orthogonalized kernel will be a sparse s + 2 kernel with values propagated from the original size kernel. Since circular convolution applied to the entire image, including the zero-padded regions Xpad, these padded areas can acquire information from the central spatial region. As norm preservation only holds for || = ||xXpalll = ||apalll. removing pixels from pad will cause slight norm drop. Importantly, does not affect the validity of the certified results, neither zero sero-padding nor the removal of padded parts expands the norm or violates the I-Lipschitz bound.
For the BRONet architecture on ImageNet, we retain the padded regions in the output. Empirically, we found this beneficial, as it preserves more information from the feature map. We compensate for the resulting size increase by using a larger down- lown-sampling stride in the neck module. For other datasets, we remove the padded regions to keep the input and output feature maps the same size. Further architectural implementation details are provided in Appendix B
A.5. Complexity Comparison of Orthogonal Layers
In this section, we demonstrate the computational and memory advantages of the proposed method by analyzing its complexity compared to prior work. We use conventional notation from Prach et al. (2023). We focus on algorithmic complexity and required memory, particularly in terms of maltipyy-cccumlltte operations (MACs). The detailed complexity
comparison is presented in Table g
The analysis has two objectives: input transformation and parameter transformation. The computational complexity and memory requirements of the forward pass during training are the sum of the respective MACs and memory needs. The backward pass has the same complexity and memory requirements, increasing the overall complexity by a constant factor. In addition to theoretical complexity, we report the practical time and memory usage for different orthogonal layers under various settings Figure 5 and Figure
17

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Runtime (s=32, init=32, k=
Memory (s=32, init=32, k=3)
1040
BRO
BRO
S0C
SOC
1045
Cayley
Cayley
LOT
LOT
Runtime (sec)
Momory (GB)
1040
1045
104
1083
10
15
20
25
30
35
40
10
15
20
25
30
35
40
Layers
LLayers
Runtime (s=32, init=64, k=3)
Memory (s=32, init=64, k=3)
105a
BRO
SOC
40
SOC
1045
Cayley
Cayley
LOT
Rum (sed)
Memory (G8)
1040
1043
20
104a
1098
10
15
20
25
30
35
10
15
20
25
30
40
Layers
Layers
Runtime (s=64, 64, init=32, k=3)
Memory (s=64, init=32, k=3)
103e
40
50C
SOC
1045
Cayley
Cayley
30
Rumbini (sed)
3020
Memory (G8)
20
1045
10
104a
1095
20
25
Layers
LLayers
Runtime (s-32, init-32, k=5)
Memory (s- 32, k=
104g
BRO
BRO
35
1025
Cayley
Cayley
LOT
LOT
aumbin (sed)
Memory (GB)
102e
1045
15-
1040
109s
20
30
40
Layers
Layers
Figure 5. Demonstration of the runtime and memory consumption under different settings with LipConyNet architecture. The notation 8 denotes the input size, init denote the initial channel of the the entire model, and & denotes the kernel size. The batch sizes fixed 512 for all plots, and each value is the average over 10 iterations.
18

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
300
40
250
Memory (GB)
Time (sec)
200
30
150
100
10
50
32
48 Initial Channels
64
32
48
64
Initial Channels
BRO, 5 32
Cayley, s = 32
SOC, 32
LOT, S 32
BRO, s 64
Cayley, = 64 SOC, s = 64
BRO, s = 128
Cayley, 128
Figure 6. Demonstration of the runtime and memory consumption under different settings with LipConvNet architecture. For each line, we keep the input size s fixed while varying the initial channel. The batch sizes are at 512 all plots, and each value is the average over 10 iterations.
In the following analysis, we consider only dimension preserving layers, where the input and output channels are equal, denoted by c. Define the input size as 8 X 8 X c, the batch size as b, the kernel size as x k. the number of inner iterations of a method as I, and the rank-control factor for BRO as K, as listed in Table 7 To simplify the analysis, we assume > log2(s). Under the PyTorch (Paszke et al. 2019) framework, we can also assume that rescaling tensor by scalar and adding tensors do not require extra memory during pack-propagation.
Standard Convolution In standard convolutional layers, the computational complexity of the input transformation is C' = bs22 MACs, and the memory requirement for input and kernel are M = bsse and P = c2k2, respectively. Additionally, these layers do not require any computation for parameter transformation.
SOC For the SOC layer, t convolution iterations are required. Thus, the input transformation requires computation complexity and memory times that of standard convolution. For the parameter transformation, kernel re- re-parameterization needed to ensure the Jacobian of the induced convolution is skew-symmetric. During training, the SOC layer applies Fantastic Four (Singla & Feizi, 2021a) technique to bound the spectral norm of the convolution, which incurs cost of c² 2 The memory consumption remains the same standard convolution.
LOT The LOT layer achieves orthogonal convolution via Fourier domain operations. Applying the Fast Fourier Transform (FFT) to inputs and weights has complexities of Obbss log(s?)) and O(c2s² s² log(s?)), respectively. Subsequently, s² matrix orthogonalizations are required using the transformation V(V"V) (VT V-- $, The Newton Method is employed to find the inverse square root. Specifically, let Yo = VVVV and Zo = I, then Y; is defined as
1 y, (31 Z,Y)). Z411 = (31-Z,Y) Z,
Y
(17)
This iteration converges to (VTV)= Executing this procedure involves computing 4s2t matrix multiplications, requiring about cs MACs and cst memory. The final steps consist of performing 1 bs² matrix-vector products, requiring 2 bo MACs, well as the inverse FFT. Given our assumption that log(s²), the FFT operation is dominated by other operations. Considering the memory consumption, LOT requires padding the kernel from size of x A: k to c x X s requiring 6s26² memory. Additionally, we need to keep the outputs of the FFT and the matrix multiplications in memory, requiring about 4s2 cet memory each.
BRO Our proposed BRO layer also achieves orthogonal convolution via Fourier domain operations. Therefore, the input
19

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Table 7. Notation used in this section.
Notation
Description
batch size
k
kernel size
input/output channels
input size (resolution)
number of internal iterations factor for BRO
Table Computational complexity and memory requirements of different methods. We report multiply-accumulat operations (MACS)
well as memory requirements for batch size b, input size X kernel size & x & and number of inner iterations for SOC and LOT, rank-control factor x E [0, 1] for BRO. We denote the complexity and memory requirement standard convolution as C' bs? M bs and P k2 respectively.
Method
Input Transformations
Parameter Transformations
MACS O()
Memory
MACS O(-)
Memory O(-)
Standard
M
P
SOC
Ct
Mt
etet
P
LOT
bs
3M
4s2c²t
4s2ct
Caylcy
bs
2.5M
s²c²
1.5s²
BRO bs
2.5M
s²c²R
28²
transformation requires the same computational complexity as LOT. However, by leveraging the symmetry properties of the Fourier transform of a real matrix, we reduce both the memory requirement and computational complexity by half. During the orthogonalization process, only _ are addressed. The low-rank parameterization results in a complexity of approximately 5²c"xx k and memory usage of 1 _=²c². Additionally, we need keep the outputs of the FFT, the matrix inversion, and the matrix multiplications in memory, requiring about 2 memory each.
Cayley Like BRO, the Cayley layer achieves orthogonal convolution in the Fourier domain and leverages real-matrix symmetry to reduce the input-transformmaion memory. Thus, its input- couuuttransfommation complexity and memory match those of BRO. Its parameter-transe transoomatioon,,, however, has complexity s²c with memory usage of 2 Additionally, we need to keep the outputs the FFT, the matrix inversion, and the single matrix multiplications memory similarly demands about 2 each.
B. Implementation Details
In this section, we will detail our computational resources, the architectures of BRONet and LipConvNet, rank-n configura- tion, hyper-parameters used in LA loss, and experimental settings.
B.1. Computational Resources
Most of the experiments are conducted on a computer with an Intel Xeon Gold 6226R processor and 192 GB of DRAM memory. The GPU we used is the NVIDIA RTX A6000 (10,752 CUDA cores, 48 GB memory per card). For CIFAR-10 and CIFAR-100, we used a single A6000 card for training. For Tiny-ImageNer and diffusion data augmentation on CIFAR-10/100, we utilized distributed data parallel (DDP) across two A6000 cards for joint training. For the two ImageNet experiments in Table I they are conducted on an 8-GPU (NVIDIA H100) machine.
B.2. Architecture Details
The proposed BRO layer is illustrated in Figure 7 this paper, we mainly use the BRO layer to construct two different architectures: BRONet and LipConvNet. We will first explain the details of BRONet, followed by an explanation of
20

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
BRO conv.
FFT
BRO
FFT-1
W 1 - 2V VV
Figure 7. The proposed Block Reflector Orthogonal (BRO) convolution kernel, which is an orthogonal matrix, employs Fourier transfor- mation to simulate the convolution operation. This convolution is inherently orthogonal and thus 1-Lipschitz, providing guarantees for adversarial robustness.
BRO conv. block
BRO
MaxMin
LLN
conv.
x 5N
32x32x3 > 16x16x64 > 8x8x128 > > 1x1x1024
Figure 8. Following Trockman & Kolter (2021) Singla & Feizi 2021bb: Xu al. 2022 use the proposed orthogonal convolution
layer to construct the LipConvnet. This figure illustrates the LipConvnet-5, which cascades five BRO convolution layers. The activation function used is the MaxMin function, and the final layer is the last layer normalization (LLN).
LipConvNet constructed using the BRO layer.
design our architecture BRONet similar to SLL and LiResNet. consists of stem layer for image-to-feature conversion, several convolutional backbone blocks of same channel width for feature extraction, neck block for down-sampling and converting feature maps into flattened vectors, and multiple dense blocks followed by spectral normalized layer (Singla et al.) 2022). For non-linearity. MaxMin activation is used.
BRONet Architecture
Compared to LiResNet with Lipschitz-regullrizzd (Lip-reg) convolutional backbone blocks and SLL with SDP-based I-Lipschitz layers, BRO orthogonal backbone blocks stabilize the gradient norm due to the property of orthogonal layers. We keep the first few layers (the first stem layer for all datasets and six extra layers for ImageNet) in BRONet to be Lipschitzreegularized since we empirically find benefits the model training with more flexible Lipschitz control in the early layers.
Figure illustrates the details of the BRONet architecture, which is comprised of several key components:
This consists of an unconstrained convolutional layer that is Lipschiiz-regularrzze during training. The width W is the feature channel dimension, which is an adjustable parameter. For the ImageNet architecture, we extend the stem layer with six unconstrained repsaiitz-regulaarzed convolution layers of same channel width, which we empirically found beneficial for feature extraction.
Stem:
This segment consists of L BRO convolutional blocks with channel width W, each using A kernels and constrained to be 1-Lipschitz. Before applying BRO parameterization, we apply fixed identity residual re- parameterization to the unconstrained parameter V: + I VI. V, where / is the identity convolutional kernel and is learned scalar. This implementation is adapted from LiResNet (Hu et al. 2023 2024), which was designed as training trick for normalization- free networks. We also found it to be empirically effective in our setting.
Backbone:
Neck: This consists convolutional down-sampling layer followed by a dense layer, which reduces the feature dimension. For the convolutional layer, we follow LiResNet (Hu et al. 2024) to construct a 1-Lipschitz matrix with dimension (Cout: Ou k:2) and reshape it back to (Cout, Cmy k k). It important to note that while the reshaped kernel
21

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Lipschitz Regularized
32x32x3
conv. 5x5
Stem
16x16xW
MaxMin
Backbone
BRO conv. block
L
16x16xW
Conv. 4x4, Stride=4
4xW
Neck
Ortho. dense +MaxMin
1-Lipschitz
2048
Ortho. dense +MaxMMin
Dense
D
2048
LLN
Head
100
Figure 9. Following the LiResNet architecture (Leino 2021 Hu et al.
2023). we utilized the BRO layer to construct BRONet. The
parameters L, W, and D can be adjusted to control the model size.
differs from the orthogonal convolution described in BRO convolutional layer, remains 1 1-Lipschitz bounded due to being non-overlapping (stride kernel size k) (Tsuzuku et al. 2018). For the ImageNet architecture, we replace the learnable convolution layer with f--norm patch pooling, which a norm-presse cem--rrerrving nonlinear pooling layer that we found work better on the ImageNet benchmark. Furthermore, ImageNet zero-padding implementation (discussed in in(,.)) the output feature map size for each BRO convolutional layer increases. Consequently, we use larger down-sampling stride to keep the feature map the same size before flattened.
do not remove the 2 padded regions for the
Dense: D BRO or Cholesky-orthogonad (Hu al. 2024) dense layers with width 2048 are appended to increase the network's 's depth and enhance the model capability. The identity re-pat parameterrization that is used in the backbone is also applied here with L replaced by D.
Head: The architecture concludes with an LLN (Last Layer Normalization) layer (Singla et al. 2022). Note that we also use the LLN certification bound instead of Mr
We can use the W, L. and D to control the model size.
LipConyNet Architecture
This architecture utilized orthogonal neural networks such as SOC and LOT. The fundamental architecture, LipConwNet, consists of five orthogonal convolutional blocks, each serving down-sampling layer. The MaxMin or householder (Singla al. 2022) activation function is employed for activation, and the final layer is affine layer such LLN. Figure provides an illustration of LipConvNet. To increase the network depth, dimension-preservv
orthogonal convolutional blocks are added subsequent to each down-sampling block; thus, the depth remains a multiple of five.
We use the notation LipConwNet--dpthh-iiie width to describe the configurations. For example, LipConwNet- 10-32 indicates a network with 10 convolutional layers and an initial channel width of 32, consisting of five downsampling semi ommi-orthogona layers and five dimension dimension-preservingg orthogonal layers.
22

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
B.3. Architecture and Rank-n Configuration
As mentioned in Section 4.1 for BRO layers with dimension dout din m, we explicitly set the unconstrained parameter V to be of shape rank-n is presented in Appendix D.3
with > n to avoid the degenerate case. An ablation study on the effect of different choices of
BRONet
We set n = m/4 for the BRONet-M backbone and dense layers on CIFAR-10/100 and set n = m/8 for the BRONet on Tiny-ImageNet. For all other BRONet experiments, we use n = m/ for the BRO backbone and use Cholesky-orhoognaal dense layers. For CIFAR-10/100, BRONet is configured with LI2W512DS, and L6W512D4 for Tiny-ImageNe For the ImageNet architecture, BRONet is configured with L14W588D8, with six Lipschitz-reguulriizedd layers and eight BRO convolutional layers. Specific architecture details are presented in Appendix B.2
LipConvNet
For LipConvNet, we set n = m/8 for all experiments.
B.4. LA Hyper-parameters
Unless otherwise specified, the LA loss hyperparameters are set to T = 0.75, 5 = 2, and / = 5.0. For LipConvNet experiments, & is set to 2. These hyperparameters were selected based on an ablation study conducted on LipConwNer. Please see Appendix D.5 for details.
B.5. Table 1 Details
2024), we use NAdam (Dozat 2016) and the LookAhead Wrapper (Zhang et al. 2019) with an initial learning rate of 10 batch size of 256, and weight decay of 4 x 10-5, The learning rate follows a cosine decay schedule with linear warm-up during the first 20 epochs, and the model is trained for total of 800 epochs. We combine the LA loss with the EMMA (Hu al., 2023) method to adjust non-ground-truth logit values for Lipschitz regularization on the stem layer. The target budget for EMMA is set to 108/255 and offset for LA is set to & 2. For ImageNet experiments, the batch size is set to 1024, with EMMA target budget 72/255, and trained for total of 400 epochs. Weight decay is removed for the ImageNet setting as we empirically found it hurt model performance. To report the results of LiResNet (Hu) et al. 2024), we reproduce the results in the same setting without diffusion data augmentation for fair comparison. The experimental results are the average of three runs. For other basclines, results are reported as found in the literature.
Mainly following (Hu et al.
B.6. Table Details
In this table, we utilize diffusion-syythetii datasets pubicly available from (Hu et al. 2024 Wang et al. 2023) for CIFAR-10 and CIFAR-100, which contain 4 million and million images, respectively. Following (Hu ct al. 2024), we augment each 256 size minibateh with 1:3 real-to- -yytthhtiitt ratio, resulting in a total batch size of 1024. We have removed weight decay, as we observed it does not contribute positively to performance with diffusion-synthetic datasets. For the ImageNet dataset, we generate 2 million images using the best setting recommended EDM2 with autoguidance Karras al. (2024b a), and use batch size 512 augmented with 1:1 real-to-synthetic ratio, resulting in a total batch size of 1024. All other settings remain consistent with those in T
B.7. Table 3 Details
The settings consistent with those in Table 2 where we the default architecture of LiResNet (LI2W512D8), LA loss, and diffusion data augmentation. We replace the convolutional backbone for each Lipschitz layer.
B.8. Table 4 Details
Following the training configuration of Singla & Feizi (202 lb). we adopt the SGD optimizer with initial learning rate of
0.1, which is reduced by factor of 0.1 at the 50-th and 150-th epochs, over total of 200 epochs. Weight decay is set to 3 x 10-4, and a batch size of 512 is used for the training process. The architecture is initialized with initial channel sizes of 32, 48, and 64 for different rows in the table. The LA loss is adopted for training.
23

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
C. Logit Annealing Loss Function
In this section, we delve into the details the LA loss. Initially, we will prove Theorem [ which illustrates the lower bound of the empirical margin loss risk. Next, will visualize the LA loss and its gradient values. Additionally, we will discuss issues related the CR term used in the SOC and LOT frameworks. Lastly, we will thoroughly explain the annealing mechanism.
C.1. Proof of Theorem
Here, we explain Theorem ! which demonstrates how model capacity constrains the optimization of margin loss. The margin operation is defined as follows:
My f(x);
max fz) Eegh
(18)
This operation is utilized to formulate margin loss, which is employed in various scenarios to enhance logit distance and predictive confidence. The margin loss can be effectively formulated using the ramp loss (Bartlett et al., (017), which offers analytic perspective margin loss risk. The ramp loss provides linear transition between full penalty and penalty states. It is defined as follows:
0
if f(x), maxk f(x)+ 2 T, f(x), max f(z); $ 0, otherwise.
L, ramp (f, y.
1 f(x), maxesi f(a)x
We employ the margin operation and the ramp loss to define margin loss risk follows:
Rf) == Ef(r. ([(er..mm((M[[((). (M(((z).
(19)
R-(F) = Σ l (.(.
(20)
where Rf) denotes the corresponding empirical margin loss risk. According to Mohri et al. (2018) risk bound exists for this loss:
Lemma 4. (Mhrii et al. 2018 Theorem 3.3) Given a neural network f. let T denote the ramp loss. Let represent the function class of f, and let Rs(,) denote the Rademacher complexity. Assume that S is a sample of size n. Then, with probability 5, we have:
In(1/5)
R-(f) (R())
(21)
2n
Next, apply the following properties for the prediction error probability:
Pe = Pr max f(x); + v Pr(--M((2)) 0
(22)
[E((M((()),)) 9) 5
(23)
S Eler.ramp (M((rramp(M((()) (M(f(z)vv)) R-(s))
(24)
(25)
where P. is the prediction error probability. Assuming that the Pe is fixed but unknown, we can utilize Lemma and
equation 25 to prove Theorem T
In(1/))
R( - 2Fs((FF -22s(F))) 3/
(26)
2n
This suggests that the lower bound for the margin loss risk Rf) may be influenced by the complexity of the model.
24

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
LA
2
LA
4
CE
CE
0
CE CR
CE+CR
-2
4
6
-2
-
-10
-4
-12
0.0
0.2
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Pt
Pc
(a) Loss function
(b) Derivative of loss function
Figure 10. Comparison of three loss functions. The x-axis is pt. This figure displays curves representing the behavior the proposed LA loss, contrasted with cross-entropy loss and the Certificate Regularization (CR) term. We observe the discontinuous gradient of the CR term. Additionally, the gradient of the CR term tends to infinity as p: approaches one, leading to gradient domination and subsequently hindering the optimization of other data points. In contrast, the proposed LA loss employs different strategy, where the gradient value anneals as nears one. This prevents overfitting and more effectively utilizes model capacity to enhance learning across all data points.
C.2. CR Loss Risk
Next, we illustrate and prove the relationship between margin loss risk and the CR loss risk. Let the empirical CR loss risk be defined as follows:
Ron()) = 1 Σ m max(MM((ss)..)).)
(27)
Proposition 4. Let RoR(f) and (f) (f) be the empirical CR loss risk and margin loss risk, respectively. Assume that sup, (x, and 7 1/T. Then, RoR(f) R+(f) decreased by one unit:
=
(28)
Proof. (Proof for Proposition Consider two cases based on the value of M(x)):
When M(x) S O: the CR loss always zero and the ramp loss is always one. Thus, the distance between ROR (f) and (f) is one.
When M(x) > 0: The distance between the ramp loss and CR loss is:
Cr.ramp (M(mp)M(((x))....) + ( = M(xr) + +xM(x,,
=1+ - -
(29)
Therefore, the empirical CR loss risk can be rewritten as:
= - JM,, where
(30)
M4 = EmE(s)MMnn))) M(x:).
(31)
This equation simplifies to the one stated in Proposition
lif = 1/T.
25

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
0.2
CR Landscape Contour
0.128
3.08
CR
0.112
2.06
0.02
Direction 2
0.080
Value
0.064
Dondhan
0.033
-2
Direction
0.016
-3
0.000
Direction 1
(a) CR landscape
(b) CR landscape contour plot
Figure 11. CR Loss Landscape Analysis. This figure illustrates the loss landscape investigate the effects of the CR term. Notably, the CR term can suddenly become "activated" or "deactivated," which is vividly depicted in the landscape transitions. These abrupt changes contribute unstable optimization during training, potentially affecting the convergence and reliability of the model. Understanding this behavior is crucial for improving the training process of Lipschitz neural networks. Regarding the direction of loss landscape, we follow the setting [ngstrom
2018) and Chen et al. (2021) We visualize loss landscape function LCR(E (2, + wids + w2d2). where di signl ( LCR), d2 Rademacher (0.5), and w is the grid.
Conclusively, we demonstrate that the CR loss risk has lower bound as follows:
[n(1/8)
Ron(f) Pe 29 (F+)
-3
(32)
2n
When the complexity is limited, CR loss risk may exhibit great lower bound. Thus, enlarging margins using the CR term is less beneficial beyond certain point.
C.3. CR Issues
Recall that CE loss with CR term is formulated LCe - ma)( 0), where My(x) f(x); max f())& is the logit margin between the ground-truth class / and the runner-up class. We compare LA loss, CE loss, and the CE+CR loss with 0.5. Figure TO illuttrttes the loss values and their gradient values with respect to Pt, where Pt represents the softmax result of the target logit. When using CR term as the regularization for training Lipschitz models, we summarize the following issues:
(1). Discontinuous loss gradient: the gradient value of CR term P: 0.5 is discontinuous This discontinuity leads unstable optimization processes, shown in Figure 10 This indicates that, during training, the CR loss term may be "activated" or "deactivated." This phenomenon can be further explored through the loss landscape. Figure IT displays the CR loss landscape for the CR term, where it can be seen that the CR term is activated suddenly. The transition is notably sharp.
(2). Gradient domination: as approaches one, the gradient value escalates towards negative infinity. This would temper the optimization of the other data points in the same batch.
(3). Imbalance issue: our observations indicate that the model tends to trade clean accuracy for increased margin, suggesting possible imbalance in performance metrics.
26

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Training set
Test set
800
LA
LA
4000
CE
700
CE
CE+CR
CE+CR
600
3000
500
Number
400
300
1000
100
220
-1.
-1.0
-0.5
0.0 Margin
0.5
1.0
1.5
2.0
-2.0
-1.5
-1.0
-0.5
0.0
0.5
1.0
2.0
Margin
Figure 12. Histogram of margin distribution. The left histogram represents margin distribution obtained from the training set, while the right histogram shows margin distribution from the test set. The x-axis represents the margin values. These visualizations demonstrate that the LA loss helps the model learn better margins.
Table Additional results on Tiny-ImageNet. No additional diffusiion-gemerated synthetic datasets are used during training.
Clean Acc.
Certified Ace. (E)
Datasets
Models
#Param.
86 255
72
108
255
255
SLL X-Large (Arauju et al.
2023
1.1B
32.1
23.2
16.8
12.0
Sandwich (Wang Manchester
39M
33.4
24.7
18.1
13.4
ImageIm
LiResNet
2024
133M
40.9
26.2
15.7
8.9
BRONet
75M
40.5
26.9
17.1
10.1
BRONet (+LA)
75M
41.2
29.0
19.0
12.1
Therefore, instead of using the CR term to train Lipschitz neural networks, we design the LA loss to help Lipschitz models learn better margin values.
C.4. Annealing Mechanism
We can observe the annealing mechanism in the right subplot of Figure 10 The green curve is the gradient value of the LA loss. We can observe that the gradient value is gradually annealed to zero as the value approaches one. This mechanism limits the optimization of the large-margin data points. As mentioned previously, Lipschitz neural networks have limited capacity, so we cannot maximize the margin indefinitely. Since further enlarging the margin for data points with sufficiently large margin is less beneficial, we employ the annealing mechanism allocate the limited capacity for the other data points.
In addition, delve deeper into the annealing mechanism of the proposed LA loss function. As illustrated in Figure T2 train three different models using three loss functions, and we plot the histogram of their margin distribution. The red curve represents the proposed LA loss. Compared to CE loss, the proposed LA loss has more data points with margins between 0.4 and 0.8. This indicates that the annealing mechanism successfully improves the small-margin data points to appropriate margin 0.4 and 0.8.
Additionally, as the left subplot in Figure 12 illustrates, the margin exhibits an upper bound; no data points exceed value of
27

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Table 10. The clean, certified, and empirical robust accuracy of BRONet-M CIFAR-10, CIFAR-100 and Tmag-
Clean Acc.
Certified / AutoA (e)
Datasets
255
255
255
CIFAR-10
81.1
69.9 / 76.1
55.3
69.7
40.4 / 62.6
CIFAR-100
54.3
40.0
/ 47.3
28.7
41.0
19.4 / 35.5
Imageemaeeeet 41.0
29.2 / 36.3
19.7
31.7
12.3 / 27.5
2.0, even when larger y is used in the CR term.
This observation coincides with our theoretical analysis, confirming that the Lipschitz models cannot learn large margins due to its limited capacity.
Table 11, The clean accuracy, empirical accuracy against so advorsary, and certified accuracy on CIFAR-10.
Methods
Clean
to = 2/255
too = 8/255
Certified Acc.
STAPS
79.8
65.9
N/A
62.7 (lx 22/255)
SABR
79.5
65.8
N/A
62.6 (Exo = 22/255)
IBP
48.9
N/A
35.4
35.3 (fx = 8/255)
TAPS
49.1
N/A
34.8
34.6 (fxo = 8/255)
SABR
52.0
N/A
35.7
35.3 (Ex 8/255)
70.6 (f2 36/ 06/255)
BRONet-L
81.6
68.8
21.0
57.2 (f, = 72/255)
42.5 (f2 1255)
D. Additional Experiments
In this section, we present additional experiments and ablation studies.
D.1. Additional Tiny-ImageNet Results for Table
We present additional results on the Tiny-ImageNee dataset in Table The model configuration is described in Appendix B.3 and the training setting is consistent with CIFAR-10/100 in Table
D.2. Empirical Robustness
In addition to certified robustness, we can validate the empirical robustness of the proposed method. This further supports our robustness certificate. Theoretically, certified robust accuracy the lower bound for the worst-ease accuracy, while empirical robust accuracy is the upper bound for the worst-case accuracy. Thus, empirical robust accuracy must be greater than certified robust accuracy. We employ AutoAttack (Croce & Hein 2020) assess empirical robustness. The certified and empirical robust accuracy for different attack budgets are illustrated in Table 10 We observe that all empirical robust accuracy values for each budget are indeed higher than their corresponding certified accuracy. This indicates that the certification is correct under the Attack, and that the proposed method achieves strong empirical robustness without any expensive adversarial training examples. Furthermore, we also measure fo empirical robustness against fox AutoAttack on 100. The results are presented in Table II] and the baselines for foo certified defenses are from the literature (Mueller et al. 2023 Mao et al. 2023 Although not designed for lo certified robustness, our method shows competitive performance on the benchmark.
D.3. BRO Rank-n Ablation Experiments
As mentioned earlier, we can control the rank of V to construct the orthogonal weight matrix. In this paper, the matrix V of low rank. Considering the internal term V(VTV)-IV) in our method's ''s parameterization, the concept is similar that of
28

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Table 12. We compare the clean accuracy, certified aceuracy, and training time for different choices of for the unconstrained parameter V on CIFAR-I0 100 with BRONet L6W256D4 and L6W5 12D4. Time is calculated in minutes per training epoch.
L6W256D4
L6W512D4
Clean
36
72
108
Time
Clean
36
72
108
Time
255
255
255
255
265
255
m/8
51.6
39.2
28.3
19.5
0.66
52.8
40.2
28.6
20.3
1.57
m/4
52.8
39.5
27.9
19.7
0.73
54.0
40.2
28.3
19.3
1.92
m/2
53.4
39.0
27.3
18.5
0.94
54.1
39.7
27.7
18.6
2.82
3m/4
52.7
39.5
28.0
19.2
1.27
53.5
39.8
27.9
18.9
3,75
Table
improvement of with LipConvNer-10-32 on different datasets.
Datasets
Loss
Clean
36 255
72
108
255
CE
77.5
62.1
44.8
29.2
CIFAR-10
LA
76.9
63.4
47.2
32.6
CE
48.5
34.1
22.6
14.4
CIFAR-100
LA
48.6
35.4
24.5
16.1
CE
38.0
26.3
17.0
10.3
Tiny- ImageNteeNet
LA
39.4
28.1
18.2
11.6
LoRA (Hu et al. 2022). We further investigate the effect of different values of V. For the unconstrained m x n parameter V in the backbone and dense blocks of BRONet, we conduct experiments using different values. The clean and certified accuracy, as well as training time, on CIFAR-100 are presented Table 12 Different values of n result in slight variations in performance, with n = m/2 yielding the best results. Therefore, we choose n = m/4 for all IIFAR-1O/CIFAR experiments on BRONet-M, and n = m/2 for BRONet-L. and ImageNet. For Imag-em we set = m/8 to mitigate overfitting.
D.4. LA Loss Ablation Experiments
We verify the LA loss on LipConvNet constructed using BRO, LOT, SOC. Table 15 illustrates the improvement achieved by replacing the CE+CR loss, which is initially recommended for training LipConvNet. The results suggest that using the LA loss improves the performance of LipConvNet constructed with all orthogonal layers both CIFAR-100 and Tmng-Im
We also compare LA to CF on LipConvNet. Table 13 shows the results for LipConvNet constructed with BRO. Our results show that the LA loss encourages moderate margin without compromising clean accuracy. Notably, the LA loss is more effective on larger-scale datasets, suggesting that the LA loss effectively addresses the challenge of models with limited Rademacher complexity.
D.5. LA Loss Hyper-parameters Experiments
There are three tunable parameters in LA loss: temperature T, offset Ç, and annealing factor B. The first two parameters control the trade-off between accuracy and robustness, while the last one determines the strength the annealing mechanism. For the temperature and offset. we slightly adjust the values used Prach Lampert] (2022) to find a better trade-off position, given the differences between their network settings and ours. Specifically, we evaluated the temperature T {0.25, 0.5, 0, 75, 1.0), the offset & {0.5, 1.0, 1.5, 2.0, 2.5, 2.0,3.0) and the annealing factor 3 E (1,3,5 5, 7} with LipConyNet-10-33 on CIFAR-100. Based on the evaluation, all other LA experiments are set with T = 0.75. = 2.0, and = 5.0. For further LipConvNet experiments, the offset is set to ę = 2v2 due to an oversight in the implementation. As we have found these parameeesss to work well, we did not further finetune them for each architecture and datasets to save computational cost. One might consider further refine the paprrterrameters for better performance. Additionally, we present the results of LA loss with different 3 values for LipConvNet- 10 on CIFAR- 1100000000 in Table
29

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Table Experimental results LipConv.Net-00 on CIFAR-100 100 different values of 3 the loss.
B value
Clean
36
72
108
255
48.63
35.48
24.36
17.19
3
48.57
35.68
24.78
16.66
5
49.09
35.58
24.46
16.38
7
49.02
35.72
24.34
16.05
Random Initialized
Trained
Average Condition Number
10a
Average Condition Number
Max Condition Number
Max Condition Number
10a
Ideal Condition Number
Ideal Condition Number
Condition Number
204.2
89.3
102
10a
27.0
26.9
26.9
26.9
26.9
26.9
15.4
10.6
11.9
11.8
11.8
11.8
11.8
10a
10a
2.4
2.3
2.3
2.3
2.3
2.3
1.8
1.8
1.8
1.8
1.8
1.8
109
0
10
20
30
40
50
0
10
20
30
40
50
Number of Newton Iterations
Number of Newton Iterations
Figure 13. Plots of condition number parameterized matrix in Fourier domain. The left plot shows the condition number with randomly initialized parameters, whereas the right plot shows the condition number with trained parameters.
D.6. LipConvNet Ablation Experiments
More detailed comparison stem from Table are provided Table [5] demonstrating the efficacy of LA loss across different model architectures and orthogonal layers. Following the same configuration as Table we further investigate the construction of LipConvNet by conducting experiments with varing initial channels and model depths, detailed in Toble
D.7. Instability of LOT Parameterization
During the construction of the LOT layer, empirically observed that replacing the identity initialization with the common Kaiming initialization for cimension-preservvee layers causes the Newton method to converge to non-orthogonal matrix. We check orthogonality by computing the condition number of the parameterized matrix of LOT in the Fourier domain. For an orthogonal layer, the condition number should be close to one. However, even after five times the iterations suggested by the authors, the result for LOT does not converge to one. Figure illustrates that, even with 50 iterations, the condition number of LOT does not converge to one. The orange curve represents the case with Kaiming randomly initialized parameters, while the blue curve curve corresponds the case after few training epochs. Both exhibit significant gap compared to the ideal case, indicating that LOT may produce non-orthogonal layer.
30

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
Table 13. Comparison of clean and certified accuracy, training and inference time (seconds/epoch). and number of parameters with different orthogonal layers LipConvNet-10 10. Instances marked with dash (-) indicate out memory during training. In the Time column, we show the training time, and the inference time is in brackets. Time is calculated in minutes per training epoch.
Init. Width
CIFAR R-100
Tiny Imag-emaeNNet
Methods
Clean
36
72
108
Time
Clean
36
72
108
Time
255
SOC + CR
48.1
34.3
23.5
15.6
19.2
37.4
26.2
17.3
11.2
107.7
LA
47.5
34.7
24.0
15.9
(5.3)
38.0
26.5
17.7
11.3
(11.1)
32
LOT + CR
48.8
34.8
23.6
15.8
52.7
38.7
26.8
17.4
11.3
291.5
LA 49.1
35.5
24.4
16.3
(1.4)
40.2
27.9
18.7
11.8
(7.3)
BRO CR
48.4
34.7
23.6
15.4
17.3
38.5
27.1
17.8
11.7
98.6
LA 48.6
35.4
24.5
16.1
(0.9)
39.4
28.1
18.2
11.6
(4.6)
SOC + CR
48.4
34.9
23.7
15.9
35.4
38.2
26.6
17.3
11.0
199.3
LA
48.2
34.9
24.4
16.2
(8.7)
38.9
27.1
17.6
11.2
(20.3)
48
LOT CR
49.3
35.3
24.2
16.3
143.0
LA
49.4
35.8
24.8
16.3
(3.0)
BRO + CR
49.4
35.7
24.5
16.3
35.2
38.9
27.2
18.0
11.6
196.9
LA
49.4
36.2
24.9
16.7
(1.1)
40.0
28.1
18.9
12.3
(4.8)
SOC + CR
48.4
34.8
24.1
16.0
53.1
38.6
26.9
17.3
11.0
305.1
LA
48.5
35.5
24.4
16.3
(12.4)
39.3
27.3
17.6
11.2
(32.5)
64
LOT CR
49.4
35.4
24.4
16.3
301.8
LA
49.6
36.1
24.7
16.2
(5.8)
BRO + CR
49.7
35.6
24.5
16.4
64.4
39.6
27.9
18.2
11.9
355.3
LA
49.7
36.7
25.2
16.8
(1.6)
40.7
28.4
19.2
12.5
(4.9)
Table 16. The experiments conducted with varying initial widths and model depths using the CIFAR-100 and Tiny-ImageNet datasets. The model employed is LipConvNet.
Init. Width
CIFAR-100
-iny-ImageNet
Depth
Clean
36
72
108
Clean
36
72
108
255
255
255
255
255
255
49.04
35.06
24.19
16.06
39.28
27.47
18.23
11.47
5
48
49.60
35.80
24.63
16.20
40.12
27.79
18.36
11.92
64
49.97
36.21
24.92
16.45
40.82
28.26
18.76
12.31
48.62
35.36
24.48
16.11
39.37
28.06
18.16
11.58
10
49.39
36.19
24.86
16.68
39.98
28.12
18.86
12.27
64
49.74
36.70
25.24
16.80
40.66
28.36
19.24
12.48
32
48.59
35.51
24.42
16.28
39.20
27.66
18,08
11.84
15
48
49.37
36.50
24.93
16.81
39.87
27.96
18.49
12.11
49.91
36.57
25.26
16.81
40.38
28.73
18.78
12.52
32
48.62
35.68
24.66
16.57
38.74
27.23
17.75
11.67
20
48
49.26
36.09
24.91
16.62
39.63
27.88
18.49
12.07
64
49.60
36.47
25.24
17.09
39.77
28.03
18.53
12.17
31

---

Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss
E. Limitations
While our proposed methods have demonstrated improvements across several metrics, the results for large perturbations, such as 108/255, are less consistent. Additionally, the proposed LA loss requires extra hyperparameter tuning. In our experiments, the parameters were chosen based on LipConvNets trained on CIFAR-I00 without -iffueiio-synthetic augmentation (Appendix B.4), which may not fully align with different models and datasets. Furthermore, our methods are specifically designed for i2 certified robustness, and certifying against attacks like -orm introduces additional looseness. Lastly, although BRO addresses some limitations of orthogonal layers, training certifiably robust models on large datasets remains computationally expensive.
32


Reviews:
[{"review_id": "5CvNwYMLx3", "reviewer": "Reviewer_oDFR", "summary": "The paper proposes a new method to construct 1-Lipschitz neural networks, namely, the L2 norm Lipschitz constant for each layer is 1. A 1-Lipschitz network is very useful for guaranteeing the robustness of neural networks. The paper claims to outperform existing 1-Lipschitz network designs such as SOC and Cayley layers.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q: Regarding Table 1 Description**\n\nThank you for your feedback. Table 1 indeed presents the combined results with the LA loss, as stated in the Appendix. To ensure clarity, we will explicitly indicate this by adding a (+LA) notation in the revised version.\n\n---\n\n**Q: Fair Comparison of Different Parameterizations**\n\nWe understand your concerns about fairness in comparison. To clarify, our comparisons in Table 2 (LipConvNet Benchmark) and Table 4 (Backbone Comparison) are conducted under fair conditions, with all baselines incorporating the LA loss. To ensure transparency and avoid any confusion, we will explicitly state this in the table descriptions.\n\n---\n\n**Q: Regarding Low-rank parameterization**\n\nThe orthogonal matrix $W$ in BRO ($W=I-2V(V^TV)^{-1}V^T$) is consistently full-rank, and the trainable parameters $V$ are constrained to be low-rank to prevent $W$ from degenerating into a negative identity matrix, as shown in Proposition 1. To increase model capacity, experiments (Appendix D.1, Table 9) suggest that enlarging $W$ and setting $V$ to half its rank improve data fitting.", "claims_and_evidence": "The author claims that the proposed parametrization for 1-Lipschitz neural networks is efficient and outperforms existing methods. Experiments are conducted on multiple datasets, multiple perturbation epsilons, and multiple baseline methods.", "methods_and_evaluation_criteria": "The main method is based on the block reflector construction of orthogonal matrices. This construction is not discussed in prior works (under the context of 1-Lipschitz networks), although some techniques used are similar (e.g., the use of FFTs for orthogonal convolution). The authors also proposed to adjust the commonly used cross-entropy loss for 1-Lipschitz networks, inspired by its limited capacity to learn large margins.", "theoretical_claims": "Rademacher complexity is used to prove that the capacity of 1-Lipscitz network is limited and may not fit large margins well. The analysis is based on the standard learning theory approach, and inspires the development of the LA loss.", "experimental_designs_or_analyses": "The experimental design follows existing work in this field: clean accuracy and certified accuracy comparisons on a few datasets on different perturbation epsilons. Many baselines are included. The work in general performs well, although the improvements are relatively marginal and inconsistent in some settings.", "relation_to_broader_scientific_literature": "The design and creation of 1-Lipschitz network can be an important building block for creating neural networks with provable guarantees such as robustness and safety. In general, the techniques proposed by this may be valuable for the scientific community.", "essential_references_not_discussed": "Essential references are discussed and experimentally compared.", "other_strengths_and_weaknesses": "The main strength of the paper is the novel formulation of 1-Lipschitz neural network layer, and the adjusted cross-entropy loss for 1-Lipschitz training.\n\nMy biggest confusion is about the evaluation - reading the paper, it sounds like Table 1 includes BRO layers only and does not mention LA loss. However, appendix B.5 mentioned that LA loss is used in all BROnets models. The LA loss is a generic approach that can be applied to any 1-Lipschitz network approach - it does not require any special features of BRO. Technically, it can be added to any existing Lipschitz approach, and it is uncertain that in Table 1 the major improvements come from the BRO, or actually the LA loss. Especially there are many newly introduced hyperparameters, such as the rank and the logic annealing hyperparameters. It is possible that the LA loss is the main contributor and the BRO may not outperform existing parameterization in a fair setting, since it is not a universal approximation.\n\nTo support the claim that the “expressive power of deep neural networks constructed using BRO is competitive with that of LOT and SOC” (line 243), we hope to see Table 1 listing both BRO and BRO + LA loss numbers.", "other_comments_or_suggestions": "None", "questions_for_authors": "Unlike many prior works on orthogonal layers, the construction presented in this paper is low-rank. Is a low rank necessary for this parameterization? For the scenarios where we need more model capacity, how can we get a full-rank orthogonal matrix?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tq7izlYZ3K", "reviewer": "Reviewer_XtW5", "summary": "This paper introduces a new 1-Lipshitz layer using the Block Reflector Orthogonal (BRO) parameterization of low-rank orthogonal matrices for constructing image classifiers with certified robustness. In addition a new logit annealing loss function is developed to balance margin learning across data points, addressing the limited capacity issue inherent in Lipschitz networks. The resulting architecture, BRONet, is demonstrated to achieve state‐of‐the‐art l2 certified robustness on benchmarks including CIFAR‑10, CIFAR‑100, Tiny‑ImageNet, and ImageNet.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q: Regarding Theorem 1 and Proposition 3**\n\nThank you for your feedback. We will enhance the clarity of Theorem 1 by presenting its proof in a dedicated subsection. For Proposition 3, it is from (Ledoux and Talagrand 2013) and we will explicitly cite it in the statement for clarity.\n\n---\n\n**Q: Regarding Figure 2**\n\nWe appreciate the reviewer's curiosity. Indeed, 1-Lipschitz non-orthogonal layers could offer better computational efficiency but less competitive for certified robustness. As shown in Table 1, the large-scale SLL models do not achieve the same level of certified accuracy. This highlights the limitations of these layers when it comes to scaling for robustness.\n\n---\n\n**Q: The hyperparameters in the LA loss**\n\nWe selected the hyperparameters in the LA loss by testing them on LipConvNet-10-32 and applied the same values across all experiments. When used on other datasets and architectures, we found these hyperparameters to perform well. Therefore, we did not fine-tune them further in order to reduce computational cost.  In practical applications, users can further refine the hyperparameters using grid search or random search, which may lead to even better results.", "claims_and_evidence": "The paper claims significant gains in certified robustness and computational efficiency over prior methods (e.g., LOT, SOC) through the novel BRO layer and LA loss.\n\nTo my knowledge, the use of the block reflector parameterization has not  been used before for 1-Lipschitz layers.\n\nEvidence includes runtime and memory comparisons, as well as ablation studies showing marginal increases (around 1–2 percentage points) in certified accuracy.\n\nAlthough the improvements are modest, the architecture is technically sound and empirical evidence is quite thorough.", "methods_and_evaluation_criteria": "The main application of 1-Lipschitz layers is certified robustness of classifiers using a margin argument. \n\nThe method is evaluated on benchmarks for certified robustness of image classification problem with respect to the l2-norm perturbation threat model. Although this l2 threat model is not very practical as model for modeling adversarial attacks in images, it is widely studied in the certified robustness literature. Other common models such as l1 and l-infinity threat models are not addressed by this work.", "theoretical_claims": "The main theoretical claims of the architecture are based on well-established parameterizations of orthogonal matrices which I believe to be correct.\n\nThe risk bound derived in Theorem 1 and Proposition 3 seem to be correct and based on established results and are used to motivate the design of the logit-annealing (LA) loss. In particular it justifies the intuition that we should not maximize the margin uniformly in the presence of Lipschitz constraints. I think this is a good motivation for the LA loss.\n\nI do think the proof for Theorem 1 could be stated more clearly in a proof environment or in a subsection \"proof of Theorem 1\", I couldnt find a proof for Proposition 3 in the paper. Even if it is immediate from previous work (I assume its Ledoux and Talagrand 2013), its worth stating briefly. If its being cited from another paper, it would be better to cite the result explicitly.", "experimental_designs_or_analyses": "The experimental design is comprehensive, with comparisons across multiple architectures and datasets, including ablation studies that assess the effect of the LA loss.\n\nRegarding runtime shown in Figure 2, I would also be curious to compare the runtime and memory efficiency of methods which do not require matrix inversion in their forward pass such as AOL or SLL. They may not be as competitive for certified accuracy, but will scale better.", "relation_to_broader_scientific_literature": "The work builds on established concepts such as orthogonal parameterizations (e.g., via the Cayley transform) and Lipschitz network designs. The paper does a pretty good job of contextualizing and benchmarking many other relevant methods in literature (figure 1 is quite nice in this regard). Introducing the low-rank block reflector approach and a new loss function, which are valuable incremental contributions. Additionally, I can see the LA loss becoming a standard ablation in the area of certified robustness (I say ablation because sometimes the CR loss is still better).\n\nHowever, many other papers have pursued similar incremental improvements of certified robustness in these l2-norm threat models and the overall contribution is not paradigm shifting. Its not easy to make even small improvements in certified robustness, but I hope the community will begin to consider more realistic threat models as image classifiers with a clean accuracy of 50% are not very useful.", "essential_references_not_discussed": "I think they have covered the literature of 1-Lipschitz layers and certified robustness well.", "other_strengths_and_weaknesses": "Strengths:\n\nThe I think the low rank orthogonal architecture is a nice way to balance efficiency and performance, avoiding iterative schemes of SOC and LOT to perform matrix inversion.\n\nThe theoretical justification behind the LA loss is fairly interesting and seems to make improvements experimentally in most cases. I can see this loss being a common ablation in future works on certified robustness.\n\n\nWeaknesses:\n\nBRO still seems to have a significant computational overhead when computing the sparse matrix inverse that may limit its scalability.\n\nAlthough making even incremental improvement in certified l2 robustness (as many other papers have pursued) is challenging, there is not really anything paradigm shifting here. These parameterizations still perform very poorly on CIFAR100 and ImageNET clean accuracy, where 50% accuracy is far from acceptable in practice. I hope the community will begin to consider more realistic threat models and benchmarks as even the maximum l2 perturbation size considered $\\epsilon = 108/255$ can not saturate a single pixel.", "other_comments_or_suggestions": "None", "questions_for_authors": "How sensitive is the LA loss to hyperparameter settings across different architectures? It seems $\\beta=5$ is used in all benchmarks. I see in Table 14 that this is about optimal for CIFAR100, but it is generally best across the other datasets as well? How do you recommend tuning these parameters?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fHXbaIoZR8", "reviewer": "Reviewer_RtHN", "summary": "Lipschitz neural networks allow certified robustness without inference overhead; they are built by composing constrained layers. In this paper, the authors propose two improvements over the previous state of the art: they introduce a novel parametrization to construct orthogonal convolutions (BRO convolution), which aims to achieve a good performance/cost tradeoff thanks to a low rank parametrization that achieves orthogonalization without the need for an iterative algorithm. They also introduce a \"Logit annealing loss function\" that does not suffer the gradient issue of the previous losses.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q: Regarding Standardization and Certification**\n\nFor the BRONet/LiResNet experiments, the dataloader outputs data in the [0,1] range without any additional standardization or normalization, as could be confirmed by the dataset functions in the `bronet/tools/dataset/` folder. \nFor the LipConvNet experiments, the images are standardized in the dataloader, but the certification process has been adjusted to ensure that the reported budgets are correctly aligned with the [0,1] range. Specifically, as shown in line 202 of `lipconvnet/trainer/trainer.py`, `L = 1 / torch.max(std)`, which is then passed to `evaluate_certificates()` in line 265. \nWe appreciate your diligence in reviewing the implementations and believe this explanation resolves your concerns.\n\n---\n\n**Q: Regarding Scaling behavior and comparative analysis**\n\nWe provide new runtime and memory comparison plots for LipConvNet-20 via the anonymous links below. \n\n[Link 1](https://ibb.co/9mJntHvw)\n\n[Link 2](https://ibb.co/HfsKGXbN)\n\nThe x-axis represents the initial channels, while the y-axis shows runtime and memory consumption. The plots also include experiments with various input sizes, denoted by $s$. A missing dot indicates that an experiment encountered an out-of-memory error. The results demonstrate the scalability of BRO with respect to both channel and input size. We will include the figures in the next revision to help users select an adequate architecture. The experimental settings are consistent with those used in Figure 5 of the main paper.\n\nWe also include the results of Cayley layer in the revised Figure 2 via the below anonymous link.\n\n[Link 3](https://ibb.co/jYD2Gm1)\n\n---\n\n**Q: Regarding zero-padding**\n\nThank you for pointing this out. We will revise our description on line 214. For clarity, the current implementation reduces the effect of convolution across edges but does not fully eliminate it. Since zero-padding does not affect the validity of the certification, one may also consider applying it post-orthogonalization, albeit at an increased computational cost. We will include this note in the revision..  \n\n---\n\n**Q: Regarding the proof in A.1**\n\nWe apologize for the unclear notations and have revised them. For $\\mathcal{F}\\_c = S_{c, s^2} \\left(I\\_c \\otimes (F \\otimes F)\\right)$ (Line 754), $F$ is the DFT matrix, and $\\otimes$ is Kronecker product. \nRegarding Equation (13), it is a result from Trockman & Kolter (2020), showing that any 2D circular convolution operation can be block-diagonalized by a Fourier-related matrix $\\mathcal{F}.$\n\nAs for Equation (16), it is intended to explicitly demonstrate the orthogonality of BRO and its real-preserving property. The right-most term explicitly shows that the BRO convolution we use is orthogonal, as it consists of three unitary matrices. The middle term shows that $\\text{BRO}(C)$ is real if $C$ is real-valued, because that $\\text{BRO}(\\cdot)$ applied to a real matrix always produces a real matrix. As we parameterize $C$ in the real domain, the output of the BRO convolution is guaranteed to be real-valued.\n\n---\n\n**Q: Regarding parameterization for dense layers**\n    \nFor ConvNets, the computational cost is primarily dominated by convolution operations, so we did not find much advantage in swapping out the dense layers. That being said, it could be worth exploring in other architectures that rely more heavily on large dense layers and could benefit from the properties of orthogonal parameterizations.", "claims_and_evidence": "This paper's approach performs well on standard benchmarks. It improved the previous state of the art by a decent margin. (However, an absolute comparison is subject to questions; see Supplementary material section.)\n\nAbout LA loss: \nThanks to both theoretical and experimental work, the motivations behind LA loss are clear, and the experiments show a small but consistent improvement. This opens interesting perspectives about the properties of a good loss for robustness. Also, they explore the impact of the newly introduced hyper-parameter.\n\nAbout BRO:\nThe extensive experiments cover many facets, such as speed/memory, robustness performance, and numerous ablation studies. This consequent work could be more impactful with a presentation centered on the paper's central claims. (See Experimental Designs Or Analyses)", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "- ap A.4: although I agree with the reasoning, the padding must account for the fact that once a $k\\times k$ kernel is orthogonalized in frequency domain, its spatial domain equivalent is not a $k\\times k$ convolution anymore (it becomes an $s\\times s$ convolution). Under this light, the input should be padded with $s$ value instead of $k$ values.\n- Although the proof in A.1 is likely true, I did not understand the part showing that the parametrization results in real weights, especially since it is unclear how this conclusion is drawn from equation 16 ( line 792 ). An explanation of what $F$ and $\\bigotimes$ are could alleviate this issue (equation 13 and line 754).", "experimental_designs_or_analyses": "Experiments do not efficiently show that BRO reduces resource requirements. In particular, resource requirements might not correlate with the number of parameters, especially if  BRO is under-parametrized and based on FFT (which scales differently with respect to the number of channels and input size compared to usual convolution). The performance should be seen through a tradeoff between the number of parameters <-> performance <-> training cost.\n\nAlso, Cayley is missing in performance evaluation (Fig 2 and 5), which is surprising given the close proximity between the two methods (BRO can be seen as an under-parametrized version of Cayley).", "relation_to_broader_scientific_literature": "The paper situates itself well within the current literature, clearly identifying its unique contributions relative to existing methods.", "essential_references_not_discussed": "I did not noticed any missing essential references.", "other_strengths_and_weaknesses": "My main concern is the certificate correction discussed in the supplementary material. *I will raise my score if the authors show me the part of the code I may have missed or if their results have been corrected*. I think those results can be impactful even without the method being state-of-the-art.\nMy second main concern is about stating more clearly how the layer scales with respect to the number of channels, and input size, which would help a user select the adequate architecture.\n\nBesides these two issues, I think this paper can be impactful for two reasons:\n- it shows that under-parametrization can create a regime where the reduced resource cost can outweigh the reduced expressiveness.\n- a careful analysis of the loss's gradient can lead to more effective losses for robustness", "other_comments_or_suggestions": "typos:\n- l761 Proposition -> lemma\n- l753: define $F$ and $\\bigotimes$\n\nSuggestion:\n- figure 2 uses the number of layers as x axis. This is pretty uninformative about how the layer scale ( as expected, it shows a linear increase for both runtime and memory, which is displayed in log scale for runtime). Especially when the displayed layers scale very differently with respect to the image size. I do expect BRO > SOC for small inputs like 16x16, but expect the opposite for large inputs like 224x224 (explaining why BROnet starts with a stem of an unconstrained convolution with stride 7 in imagenet)", "questions_for_authors": "I'm curious about the use of BRO parametrization for dense layers (which seems implemented in your code). Does the gain in terms of runtime outweigh the under-parametrization ?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WauNVaMwFO", "reviewer": "Reviewer_8nWp", "summary": "Lipschitz neural networks are either trained or constructed such that their Lipschitz constant is small, enabling easy verification of the network to adversarial perturbations. Ways of obtaining networks with small Lipschitz constants include a) regularising the network at training time or b) designing layers which have a small Lipschitz constant by construction while maintaining expressiveness. This work introduces Block Reflector Orthogonal (BRO) layers which are a new type of orthogonal layer designed to have a Lipschitz constant of 1 using a new low-rank parameterisation. Such orthogonal layers are developed for both linear and convolutional operators. The authors further propose a new Logit Annealing (LA) loss for training Lipschitz neural networks which aims at balancing robustness considerations for different data points better by focusing on improving robustness for data points with a small margin. The evaluation on a number of datasets including the very large ImageNet shows that the new BRONet architecture outperforms existing approaches in terms of l2-certified and standard accuracy while being computationally efficient.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q: Regarding performance on large perturbations**\n\nBRONet indeed achieves the best performance on both clean and certified accuracy at $\\varepsilon = 36/255$, but is less consistent for larger perturbations $\\varepsilon$. Interestingly, we have observed that less expressive Lipschitz models tend to yield slightly higher certified accuracy at large $\\varepsilon$, but at the cost of lower clean accuracy and certified accuracy at smaller $\\varepsilon$. This tendency to fit only certain examples well to achieve large certified radii is not ideal, as our ultimate goal is to develop a robust model that maintains strong natural classification performance while simultaneously achieving favorable certified robustness as an additional benefit.\n\n---\n\n**Q: Selecting the rank**\n\nFor selecting the rank $n$, we recommend starting with $n = m/2$ and iteratively reducing it by half if needed, as supported by the experiments in Table 9. Intuitively, since $n$ determines the proportion of $+1$ and $-1$ eigenvalues in the orthogonal matrix $W$ (Proposition 1), an imbalanced distribution may reduce the diversity of $W$.\n\n---\n\n**Q: Hyperparameters in the LA loss**\n\nWe perform a hyperparameter grid serach around the values recommended by AOL (Prach & Lampert, 2022). Specifically, we evaluated the temperature $T \\in \\\\{ 0.25, 0.5, 0.75, 1.0 \\\\}$ and the offset parameter $\\xi \\in \\\\{ 0.5, 1.0, 1.5, 2.0, 2.5, 3.0 \\\\}$ with LipConvNet-10-32 on CIFAR-100.\nWhen used on other datasets and architectures, these hyperparameters performed very well, so we did not fine-tune them further to reduce computational cost. We will include this information in Appendix D.4 in the revision.\n\n---\n\n**Q: Regarding the statement \"unlock the potential...\"**\n\nWe agree with your observation. Our intent was to highlight that BRO provides a promising parameterization that enhances robustness while reducing resource requirements for orthogonal layers. This, in turn, improves their applicability in more advanced architectures. We will revise the sentence for clarity.\n\n---\n\n**Q: Performance in Table 1&4**\n\nFor Table 4, we present an ablation study on different Lipschitz layers. The improvements are relatively small because all methods incorporate the proposed LA loss, which already narrows performance differences across backbones. Since Lipschitz networks have long faced scalability issues, there are still few baselines in the literature for TinyImageNet and ImageNet. Nevertheless, we would like to emphasize that combining both BRO and LA leads to a notable improvement on these more challenging datasets, outperforming the state-of-the-art LiResNet.\n\n---\n\n**Q: Regarding typos**\n\nWe appreciate your effort in identifying the typos. We have revised them accordingly.\n\n---\n\n**Q: $\\ell_\\infty$-norm robustness**\n\nWe appreciate your suggestion and will include a brief discussion on the literature regarding $\\ell_\\infty$-norm robustness.\n\nAdditionally, we conduct empirical test against $\\ell_{\\infty}$ AutoAttack [1] on CIFAR-10, which we will provide it in the revision. The results for the $\\ell_{\\infty}$ certifed baselines are from the literature [2][3].\n\n| Method    | Clean     | Adv. Acc$\\ell_{\\infty}=2/255$ | Adv. Acc.$\\ell_{\\infty}=8/255$ | Certified Acc.                                           |\n| - | - | - | - | - |\n| STAPS $\\ell_{\\infty}=2/255$ | 79.75     | 65.91                            | N/A                              | 62.72 ($\\ell_{\\infty}=2/255$)                           |\n| SABR $\\ell_{\\infty}=2/255$  | 79.52     | 65.76                            | N/A                              | 62.57 ($\\ell_{\\infty}=2/255$)                           |\n| IBP $\\ell_{\\infty}=8/255$   | 48.94     | N/A                              | 35.43                            | 35.30 ($\\ell_{\\infty}=8/255$)                           |\n| TAPS $\\ell_{\\infty}=8/255$  | 49.07     | N/A                              | 34.75                            | 34.57 ($\\ell_{\\infty}=8/255$)                           |\n| SABR $\\ell_{\\infty}=8/255$  | 52.00     | N/A                              | **35.70**                        | 35.25 ($\\ell_{\\infty}=8/255$)                           |\n| BRONet-L (Ours)             | **81.57** | **68.76**                        | 21.02                            | 70.59, 57.15 , 42.53 ($\\ell_{2}=36/255,72/255,108/255)$ |\n\n[1] Croce, et al. \"Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks.\" International Conference on Machine Learning (ICML), 2020.\n\n[2] Mueller, et al.\"Certified training: Small boxes are all you need.\" International Conference on Learning Representations (ICLR), 2023.\n\n[3] Mao, et al. \"Connecting certified and adversarial training.\" Advances in Neural Information Processing Systems (NeurIPS), 2023.", "claims_and_evidence": "- The authors state that the BRO layers \"unlock the potential of applying orthogonal layers to more advanced architectures\". However, as far as I understand the paper they present an orthogonal formulation for dense and convolutional layers, both of which were already supported by other methods in the literature.\n- The authors claim that they achieve state-of-the-art performance on a number of datasets which is mostly supported by the experimental results. However, especially for CIFAR10 and CIFAR100 in Table 1 the gains of the proposed method seems relatively small when compared to the literature. For TinyImageNet and ImageNet, the gains compared to the baselines are larger, but it should be noted that significantly fewer baselines were run for these datasets. In Table 4 the performance gain when using the proposed BRO backbone is relatively small in most cases.\n- On large perturbations the performance of BRO seems to decline sharply (see Table 1), though this is acknowledged in the limitations section.", "methods_and_evaluation_criteria": "- Proposing layers with a small Lipschitz constant to obtain networks that are easier to certify is a well-known approach and therefore makes sense\n- The benchmark datasets are standard ones that are used in a variety of previous works. The fact that the authors run experiments on Imagenet is commendable, given the substantial resources that are required for this.", "theoretical_claims": "I checked the proofs for the orthogonality of both the dense and convolutional layers proposed in the work (Appendix A1 and A2) which appear to be the most important contribution of the work. These look correct to me and I couldn't find any issues with them. The theoretical claims made in the paper appear sound to me. I found the Rademacher-complexity-based argument that is used to motivate the logit annealing loss function somewhat difficult to understand, but the theoretical analysis is accompanied by a more intuitive motivation which I find convincing.", "experimental_designs_or_analyses": "The design of the experiments is sound, the approach is compared to all (to the best of my knowledge) relevant previous works on networks robust to perturbations in the $\\ell_2$ norm and the evaluation is conducted across a variety of datasets which are normally used in the certified training literature.", "relation_to_broader_scientific_literature": "The key contributions of the work, namely the BRO layer and the related network architectures, are related to a number of previous works on designing neural networks layers which exihibit small Lipschitz constants while also preserving sufficient expressivity. The BRO approach differs in that the layer itself is not a universal approximator, but the authors demonstrate that it is nevertheless expressive enough to outperform competing approaches in a number of cases. The orthogonal convolution layer introduced by the authors builds on a number of insights from the paper by Trockman and Kolter, but the specific parameterisation used for both the convolutional and the dense layers is novel.", "essential_references_not_discussed": "To the best of my knowledge, all relevant related works in the field of $\\ell_2$ robustness certification are discussed by the authors. There is also a large body of work on networks that are robust to $\\ell_\\infty$ perturbations (such as [1-3]) which could briefly be discussed. Other works in the field such as [4] also discuss these and the relation of their work on $\\ell_2$ robustness to $\\ell_\\infty$ robustness.\n\n[1] Mao, Y., Müller, M.N., Fischer, M. & Vechev, M. (2023) TAPS: Connecting Certified and Adversarial Training. doi:10.48550/arXiv.2305.04574.\n\n[2] Mueller, M.N., Eckert, F., Fischer, M. & Vechev, M. (2023) Certified Training: Small Boxes are All You Need. In: 1 February 2023 p. https://openreview.net/forum?id=7oFuxtJtUMH.\n\n[3] De Palma, A., Bunel, R., Dvijotham, K., Kumar, M. P., Stanforth, R., & Lomuscio, A. (2023). Expressive Losses for Verified Robustness via Convex Combinations. arXiv preprint arXiv:2305.13991.\n\n[4] Xu, X., Li, L. & Li, B. (2022) LOT: Layer-wise Orthogonal Training on Improving l2 Certified Robustness. Advances in Neural Information Processing Systems. 35, 18904–18915.", "other_strengths_and_weaknesses": "A weakness I noticed is that there are a number of parameters which need to be tuned, for example, the LA loss introduces three parameters and for the BRO layer the rank $n$ needs to be chosen. The authors seem to explicitly tune this parameter on some datasets (see Table 9) while choosing certain values for other datasets. For example, it was unclear to me how the authors arrived at choosing $n=\\frac{m}{2}$ for ImageNet but then at $n=\\frac{m}{8}$ for TinyImageNet. The fact that the values of $n$ that are used differ not only between different datasets, but also between different network architectures (see Appendix D2) raises some concerns about how easy it would be to choose this parameter in practice without having to conduct a number of tuning runs.\nThe tuning of the three hyperparameters that the LA loss introduces seems somewhat unclear to me, an ablation study for $\\beta$ is presented in Table 14 but for $T$ and $\\xi$ the authors state that they \"slightly adjust the values used in Prach & Lampert (2022) to find a better trade-off position\" - how this is done remains unclear.", "other_comments_or_suggestions": "Small typo: Line 68, right column: Assuming $f(x)$ is the output logits of a neural network --> Assuming $f(x)$ **are** the output logits of a neural network \n\nOverall, the paper is well-written. One thing I noticed is that articles are often omitted in places where they should be present. Some examples:\n- Line 90f: We construct various Lipschitz networks using BRO method --> We construct various Lipschitz networks using **the** BRO method\n- Line 308: the annealing mechanism, draws inspiration from Focal Loss --> the annealing mechanism, draws inspiration from **the** Focal Loss\n- Line 309: During training, LA loss initially promotes --> During training, **the** LA loss initially promotes\n- Line 315: Consequently, LA loss allows Lipschitz models to learn --> Consequently, **the** LA loss allows Lipschitz models to learn\nI did not write all of the cases in which this is done down, but to improve the reading flow it would be nice if the authors could do a round on the paper where they focus on eliminating these kinds of mistakes.", "questions_for_authors": "1. Could the authors share any insights they might have regarding the performance of BRO on large perturbations? I find it surprising that other methods would suddenly perform so much better than BRO on these.\n2. Do the authors have any heuristics or similar that they would use for selecting hyperparameters such as the rank $n$? How would they propose their training approach is used on new/unknown datasets or with modified variants of the BRONet architectures? \n3. Could the way in which $T$ and $\\xi$ were chosen be clarified by the authors?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces BRO layer that parameterizes a group of orthogonal (and thus Lipschitz-bounded) linear and convolutional layers. The paper also proposes logit annealing loss to encourage sufficiently large margins for more data points. When combined with diffusion-based data augmentation, BRONet achieves state-of-the-art certified L2 robustness on CIFAR10 and CIFAR100.

Most concerns were resolved after the discussion phase. All reviewers favor acceptance due to the solid contributions, but don't nominate for oral presentation due to some remaining concerns about the the small margin compared to baselines, the nontrivial computational overhead, and the limitations of the l2-certified robustness threat model.

Please make sure to address reviewers' comments in the camera-ready version. Specifically, please revise Table 1 according to the reviewer's comment to clarify the comparison with and without LA loss, fix the notation ambiguity in proof in A.1, and add runtime and memory comparison with Cayley.
Decision: Accept (spotlight poster)