Enhancing Certified Robustness via Block Reflector Orthogonal Layers

Q: Inconsistent performance gains in BRONet as the perturbation budget increases?

Thank you for your valuable suggestions and response. Ideally, we aim to build a model with state-of-the-art certified robustness with the constraint that it must maintain high clean accuracy. In this work, we focus on developing models that can achieve better margins for most data points. However, improving robustness to larger perturbations without compromising clean accuracy or robustness for smaller perturbations remains a challenge for future work.

Q: Has the BRO method been evaluated on larger datasets or tasks beyond classification to assess its scalability and generalization?

Thank you for your insightful question. While BRO has not yet been evaluated on more complex datasets or applied to tasks beyond classification, exploring its potential in these areas is an intriguing direction for future research. Given that certified robustness have been utilized in various computer vision tasks, BRO presents a strong candidate for providing competitive certified robustness in these domains. We believe that such extensions may facilitate the practical application of our method and hope that our results lay the foundation for future research on this topic.

Q: Regarding reporting statistics

Thank you for your suggestions. Following prior works [1][2], we chose to report the average of three runs. Although BRO mitigates some of the resource requirements compared to other orthogonal layers, training a certified robust model remains expensive and can take several days given our computational resources, even on a smaller-scale dataset such as CIFAR-10.

Overall, we observed that the standard deviations are sufficiently small compared to the improvements in clean and certified accuracy at $\varepsilon = 36/255$ (+0.6, +0.8). For reference, the standard deviations for the CIFAR-10 experiments in Table 1 is as follows: 0.035, 0.020, 0.359, and 0.191 for clean and certified accuracies across budgets $\varepsilon = 36/255, 72/255, 108/255$, respectively.

In future revisions, we plan to conduct additional runs and report the confidence intervals to strengthen the results further.

[1] Hu et al. "A Recipe for Improved Certifiable Robustness." International Conference on Learning Representations (ICLR), 2024.

[2] Araujo et al. "A Unified Algebraic Perspective on Lipschitz Neural Networks." International Conference on Learning Representations (ICLR), 2023.

Q: The orthogonality of BRO convolution

We apologize for any statements and typos that may have obscured the orthogonality of BRO convolution, we have addressed them in the revised version.

First, we defined $W_{\text{Conv}}$ as

where $I_{\text{Conv}}$ represents the convolution identity kernel.

Our approach builds upon prior works, such as Cayley and LOT, based on the key idea that multi-channel convolution in the Fourier domain can be reduced to a batch of matrix-vector products. By ensuring that each of these matrices is orthogonal, the convolution operation itself becomes orthogonal.

The following pipeline serves as a constructive proof for the orthogonality of BRO convolution:

1. Fourier Transform: Apply the Fourier transform to both the parameters and the input.
2. BRO Matrix Multiplications: Perform BRO matrix multiplications in the Fourier domain.
3. Inverse Fourier Transform: Apply the inverse Fourier transform to obtain the output.

Each transformation in this pipeline is orthogonal. Specifically, we compute

and $\\tilde{W}\_{:,:,i,j}=I - 2\\tilde{V}\_{:,:,i,j}(\\tilde{V}\_{:,:,i,j}^* \\tilde{V}\_{:,:,i,j})^{-1}\\tilde{V}\_{:,:,i,j}^*$ for each pixel index $i$ and $j$. This process demonstrates that $X$ undergoes a series of orthogonal operations, thereby preserving the norm of $X$ through BRO convolution. We have rephrased the statements from lines 200 to 215 and revised Algorithm 1 to enhance clarity and precision.

To further verify that BRO convolution is orthogonal, follwoing Cayley, we conduct some empirical test on the value of $\lVert \text{BRO}(x) \rVert / \lVert x \rVert$ for a trained BRO convolution layer. The following table show the statistics of 1000 forward of random generated input $x$.

Q: Why do we need FFT and the convolution theorem?

BRO convolution, $W_{\text{Conv}} = I_{\text{Conv}} - 2V \circledast (V^{\top} \circledast V)^{-1} \circledast V^{\top}$, involves an inverse convolution term $(V^{\top} \circledast V)^{-1}$, which is difficult to compute it in the original spatial domain. Using the Fourier transform and the convolution theorem allows us to compute this efficiently.

Q: Question about $c'_\text{in}$ in Algorithm 1

We would like to firstly clarify that $c_\text{in}'$ represents the low-rank dimension of the unconstrained parameter $V \in \mathbb{R}^{c_\text{out} \times c_\text{in}' \times k \times k}$, which is not the same as those (with number of dimension $c_\text{in}$ and $c_\text{out}$) used to perform convolution on the input.

Since orthogonalization is applied to the channel dimensions, we intentionally initialize the input channels of the parameter kernel to be fewer than the actual input channels to align with the design of the BRO dense layer. That's why we argue $c_\text{in}' \leq c_\text{in}$. This is the key feature that makes BRO convolution to be low-rank parameterized. Notably, after parameterization, the channel dimensions of $W$ reverts to the actual number of channels.

For improved readability, we have updated the notations by redefining $c_\text{in}$ and $c_\text{out}$ as the unified notation $c$ and the low-rank dimension as $n$.

Q: Question about the semi-orthogonal case

For the BRO dense layer, given an unconstrained matrix $V\in\mathbb{R}^{m \times n}$, the resulting parameterized matrix $W\in\mathbb{R}^{m \times m}$ will be truncated via $W[:d_{\text{out}},:d_{\text{in}}]\in\mathbb{R}^{d_{\text{out}} \times d_{\text{in}}}$, where $d_{\text{in}}$ and $d_{\text{out}}$ represent the input and output dimension, and $m=\max(d_{\text{out}}, d_{\text{in}})$.

For the BRO convolutional case, since orthogonalization is performed along the channel dimensions, a similar truncation approach is applied to the channel dimensions.

Q: Question about Equation 14 in the proof of Proposition 2

The condition for the equation to hold is satisfied.

Note that for invertible matrices with $A, B \in \mathbb{C}^{m \times m}$, $(ABA^*)^{-1} = (A^*)^{-1} B^{-1} A^{-1}$.

Thus, we have

Q: Regarding LA and CR

While training Lipschitz models, we observed that the logit margin would saturate, further improvement becomes challenging. To explain this phenomenon, we derived Theorem 1 and Proposition 3. These results show that Lipschitz models inherently struggle to minimize margin risk. To address this, we propose LA to dynamically controls the logit margin of individual data points during training. Data points with large margins are gradually annealed. While we acknowledge that this design is heuristic, it effectively ensures that all data points achieve a fair and appropriate logit margin. We will fully state the CR loss and compare it with LA.

Q: Extending Table 2 Experiments

Thank you for your question. We have conducted new experiment for CIFAR-10+EDM under this setting, and the results are as follows:

We observed that using the BRO backbone enhances performance. However, similar to the baseline LiResNet, BRONet with LA does not show improvements in clean or $\varepsilon=36/255$ certified accuracy in the CIFAR-10+EDM scenario. This may be because the learning dynamics with an abundance of diffusion-synthetic images (80 times more than real images, with a 1:3 real-to-synthetic ratio in each batch) are less impacted by the challenges discussed in the LA section. Moreover, the LA hyperparameters were initially selected on LipConvNet without incorporating diffusion-synthetic images, which could result in suboptimal alignment with the current setting.

Dear Reviewer,

Thank you for your valuable feedback. We have revised the paper accordingly, making updates to Section 4.1, Proposition 2, and Appendix A.2. Additionally, we have added Appendices A.3 and A.4 to clarify specific techniques employed in the BRO convolution.

Q: Regarding Proposition 2

The original Proposition 2 was used to prove that, despite BRO convolution being performed in the Fourier domain (involving complex numbers), the output remains real.

For enhanced clarity, we have moved the original Proposition 2 to Appendix A.2, where it is now stated as Lemma 3, and introduced a new Proposition 2 to demonstrate that the BRO convolution is orthogonal while ensuring a real output.

Q: Explicit Proof for Orthogonality

Explicit proof for Proposition 2 is added in Appendix A.2 to demonstrate that the BRO convolution is orthogonal. The proof is based on the idea that BRO convolution applies a sequence of orthogonal operations to the vectorized input, thereby ensuring its orthogonality.

Lastly, for the circular convolution identity kernel $I_{\text{Conv}}$, as the matrix and vector multiplications are performed along the channel dimensions instead of pixel dimensions, the matrix $\text{FFT}(I_{\text{Conv}})_{:,:,i,j}$ is indeed equivalent to $I$ in the Fourier domain for every pixel index $i$ and $j$.

Q: Empirical Error Gap on Orthogonality

Our analysis reveals that the slight norm drop is caused by numerical errors and the zero-padding trick used in lines 2 and 3 of Algorithm 1, followed by the removal of padded pixels in line 8. Following LOT [1], we apply zero-padding on images $X$, creating $X_{\text{pad}}$, before performing the 2D $\text{FFT}$. After applying $\text{FFT}^{-1}$, we obtain $Y\_{\\text{pad}}$, from which the padded pixels are removed to restore the original dimensions of $X$. This approach leverages zero-padding to avoid circular convolution across edges, which empirically improves performance [1]. However, norm preservation only holds for $||X||=||X\_{\text{pad}}||=||Y\_{\text{pad}}||$. Consequently, removing pixels from $Y_{\text{pad}}$ causes the slight norm drop. Importantly, it does not affect the validity of the certified results, as neither zero-padding nor the removal of padded parts expands the norm or violates the 1-Lipschitz bound.

We have incorporated this clarification into lines 236 to 240 and a detailed discusssion in Appendix A.4 of the revised paper. Additionally, for reference, we provide the empirical test for $\lVert \text{BRO}(x) \rVert / \lVert x \rVert$ when zero-padding is omitted:

Q: On the Semi-orthogonal Case for BRO Convolution

As previously explained, truncation occurs along the channel dimensions: For each pixel index $i$ and $j$, where $c = \max(c_{\text{out}}, c_{\text{in}})$, we parameterize $\tilde{V}\_{:,:,i,j} \in \mathbb{C}^{c \times n}$ as $\tilde{W}\_{:,:,i,j} \in \mathbb{C}^{c \times c},$ then truncate it to $\tilde{W}\_{:c_{\text{out}},:c_{\text{in}},i,j} \in \mathbb{C}^{c_{\text{out}} \times c_{\text{in}}}$.

We have now explicitly include this in line 244 to 247 of the revised paper, and discuss how semi-orthogonal affect orthogonality in Appendix A.3.

Q: Regarding CR and LA

We sincerely apologize for the oversight. In the initial version of the paper, we introduced the CR formula, $\mathcal{L}_{\mathrm{CE}} - \gamma \mathrm{ReLU}(\mathcal{M}_f(x))$, at the beginning of Section 6 (Line 312). To improve clarity, we have now reintroduced $\mathcal{M}_f(x)$ here, which was originally defined at the end of Section 2.1. Additionally, to enhance readability and ease of reference, we have restated the CR term before discussing it in Appendix C.2.

Thank you for your valuable comments. We have made every effort to revise the paper for enhanced clarity. Please let us know if there are any additional concerns or issues that require our attention.

[1] Xu et al. "LOT: Layer-wise Orthogonal Training on Improving l2 Certified Robustness." Advances in Neural Information Processing Systems (NeurIPS), 2022.

Q: The limitation of our approach.

The main limitation of the BRO layer design is that it can only tightly certify against $\ell_2$-norm attacks. Although, with some relaxation, the certification could potentially generalize to other norms, the resulting certification may lack tightness and become less effective. For the LA loss, the need for hyperparameter tuning introduces further challenges. We will explicitly acknowledge these limitations in the paper.

Q: Comparison with certified defense methods beyond Lipschitz approaches.

To the best of our knowledge, we have listed out all the competitive deterministic $\ell_2$ certified defense methods.

There are other certified defense methods that aim to provide robust guarantees with respect to different norms. For instance, Interval Bound Propagation (IBP) was originally designed for $\ell_\infty$-norm defenses. Though IBP can also perform relaxation and provide $\ell_2$-norm certified robustness, the $\ell_2$-norm guarantees it offers are generally loose[5]. Therefore, we did not include these comparisons in our paper.

However, we can compare the empirical robustness of those different methods. For reference, we tested our model on CIFAR-10 against the standard AutoAttack[6] with perturbation budgets of $\ell_{\infty}=2/255$ and $8/255$. Note that our method is designed for certifying against the $\ell_{2}$-norm based attacks, whereas the reported IBP-based baselines are designed for the $\ell_{\infty}$ attacks. The baseline results are reported from the literature[7][8].

Another approach to achieving $\ell_2$ certified robustness is randomized smoothing. However, unlike Lipschitz networks, its certification is inherently probabilistic and not directly comparable, so we did not focus on comparing with it.

[1] Yu et al. "Constructing orthogonal convolutions in an explicit manner." International Conference on Learning Representations (ICLR), 2022.

[2] Xu et al. "LOT: Layer-wise Orthogonal Training on Improving l2 Certified Robustness." Advances in Neural Information Processing Systems (NeurIPS), 2022.

[3] Kanai et al. "One-vs-the-rest loss to focus on important samples in adversarial training." International Conference on Machine Learning (ICML), 2023.

[4] Ding et al. "MMA Training: Direct Input Space Margin Maximization through Adversarial Training."International Conference on Learning Representations (ICLR), 2020.

[5] Li et al. "Sok: Certified robustness for deep neural networks." 2023 IEEE symposium on security and privacy (SP), 2023.

[6] Croce, et al. "Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks." International Conference on Machine Learning (ICML), 2020.

[7] Mao, et al. "Connecting certified and adversarial training." Advances in Neural Information Processing Systems (NeurIPS), 2023.

[8] Mueller, et al."Certified training: Small boxes are all you need." International Conference on Learning Representations (ICLR), 2023.

Q: Have BRO be tested on larger datasets like ImageNet?

Training a model on ImageNet is beyond the scope of our current computational resources. For reference, the ImageNet experiments for LiResNet (Hu et al., 2023&2024) reportedly required 8 A100 GPUs, while a single training run would take over two weeks on our current GPU devices. We believe our extensive experiments on CIFAR-10, CIFAR-100, TinyImageNet, and CIFAR-10/100+EDM sufficiently demonstrate the effectiveness of our proposed method.

Q: How sensitive is the method to the choice of rank in BRO and how should practitioners select it?

In summary, for practical applications, we recommend starting with half rank $n = m / 2$. This recommendation stems from the fact that the variable $n$ controls the ratio of $+1$ to $-1$ eigenvalues in the orthogonal matrix $W$, as illustrated in Proposition 1. Intuitively, a predominance of either $+1$ or $-1$ eigenvalues could negatively impact the diversity of $W$. Additionally, we have provided an empirical demonstration of how the selection of rank affects performance in Table 9.

Q: Comparison between LA and other margin-based losses.

In the context of training Lipschitz neural networks, CE+CR emerges as the most effective loss function for enhancing margins, as supported by several existing studies[1][2]. During this work's development, we also explored other margin-based loss functions, such as OVR[3] and MMA[4], integrating them into the training procedure. However, their performance consistently fell short compared to CE+CR. Consequently, our primary comparison focuses on the performance of LA against CE+CR.

Q: The potential for large and complex models, such as foundation models.

Thank you for the insightful suggestion. Extending our method to large-scale foundation models is indeed an intriguing direction, and we consider it an important avenue for future research. Recent studies have also begun to investigate the Lipschitz continuity of more complex models [1]. Developing a Lipschitz foundation model with certified robustness could have significant implications, and we hope our research provides a solid foundation for future advancements in this area.

Q: Non-universal orthogonal approximation for BRO.

To assess the potential negative impacts arising from BRO's non-universal orthogonal approximation property, we conducted an experiment on the MNIST dataset using the simplest possible setting: a linear model. Since the model's capacity is directly tied to the linear orthogonal matrices that BRO can represent in this setting, the experiment aims to determine whether BRO's performance deteriorates due to this inherent property.

The experiment consists one single-layer comparison (utilizing a single BRO/LOT linear layer).

Note that LOT is a universal orthogonal approximator. While BRO exhibits weaker representation ability than LOT in a single-layer setting, it achieves comparable or even favorable accuracies. We suggest that this may be attributed to optimization bias or other factors influencing the learning dynamics, which outweight the disadvantages of the non-universal approximation orthogonal property. In conclusion, the non-universal orthogonal approximation property does not make BRO less competitive compared to other methods.

The experiment details are provided as follows.

Q: The choice of activation & Lipschitz constant

The Lipschitz constant of common element-wise activations depend on its maximum slope, which would affect the Lipschitz constant of the entire networks. For example, ReLU is 1-Lipschitz as the maximum slope is one. However, most of them are not norm-preserving, which can lead to gradient norm vanishing[2] when training Lipschitz networks. In the $\ell_2$ certified robustness literature, the MaxMin activation is a popular choice.

[1] Castin et. al. "How Smooth Is Attention?." International Conference on Machine Learning (ICML), 2024.

[2] Cem Anil et al. "Sorting out Lipschitz function approximation." International Conference on Machine Learning (ICML), 2019.

We sincerely thank you for your positive feedback and recognition. We deeply appreciate the time and effort you dedicated to providing constructive comments.

Q: Comparison with Cayley

In Figure 2, we compare LipConvNet with the most recent methods, SOC and LOT, as Cayley has either been omitted in recent literature[1] or reported to be less competitive[2]. A more detailed discussion of Cayley follows: Although Cayley performs two fewer matrix multiplications than BRO, it does not benefit from the low-rank parameterization property. When comparing the runtime and memory consumption of Cayley and BRO in the setting of Figure 2, the results are similar. However, in the LiResNet-like architecture, which uses convolution layers with a large channel width (as seen in Table 3 experiments), BRO's low-rank parameterization provides a clear advantage. To fit within memory constraints, the number of Cayley layers must be reduced, whereas BRO operates efficiently under these conditions. In conclusion, BRO is more favorable for architectures with convolutional backbones that feature large channel widths.

Q: Simplify the experiments

Thank you for your valuable suggestion. We will work on reorganizing the experimental sections to enhance readability.

Q: The reported results of LiResNet

The observed difference with the original work is due to diffusion-generated synthetic data augmentation.

For Table 1, we want to fairly compare the baselines in the literature that does not use extra diffusion data augmentation. We reproduce and report results without diffusion data augmentation, as detailed in the Table 1 caption.

For Table 2 and 3, we include experiments with diffusion data augmentation (CIFAR-10/100+EDM) to verify the effectiveness of our methods in this setting. For CIFAR-10, we use the original synthetic dataset pubicly-released by Hu et al. (2024); for CIFAR-100, where the original synthetic dataset is unavailable, we rely on the dataset released from Wang et al. (2023)[3].

Compared to the reported results in Hu et al. (2024), a small performance gap is observed in the CIFAR-100+EDM setting due to the unavailability of the original synthetic dataset. However, since both works follow similar procedure to generate synthetic images using EDM, the comparison results should be valid in supporting the effectiveness of our proposed approach.

Q: Table 1 update

Thank you for pointing out the erratum in the latest arXiv version of SLL, we have updated Table 1 accordingly.

Q: Is limitation of BRO at large radius due to the parameterization of the loss?

As shown in our experiments, our method achieves the best performance for both clean accuracy and certified accuracy at $\varepsilon = 36/255$ but less consistent for larger perturbations. Adjusting the loss function, such as aggressively using CR or increasing the offset in LA, could enhance performance for larger perturbations. However, this often comes at the cost of clean accuracy and performance at smaller $\varepsilon$ budgets.

This tendency to fit only certain examples well to achieve large certified radii is not ideal, and we aim to mitigate this issue. Our ultimate goal is to develop a robust model that maintains its natural classification ability while simultaneously achieving favorable certified robustness as an additional benefit.

Interestingly, we empirically observed that less expressive Lipschitz models tend to achieve slightly higher certfied accuracy at larger perturbation levels, as they collapse to fit specific data examples well. This improvement, though, also comes at the cost of lower clean accuracy and reduced performance at smaller $\varepsilon$ budgets.

Q: ImageNet Results Availability

Training any model on ImageNet is prohibitively expensive for our current resources. For reference, the ImageNet experiments of LiResNet (Hu et al. 2023&2024) are reported to be conducted with 8 A100s, and a single training run would require more than two weeks with 2 RTX A6000s. We believe that our comprehensive experiments on CIFAR-10, CIFAR-100, TinyImageNet, and CIFAR-10/100+EDM are able to demonstrate the effectiveness of our proposed method.

[1] Xu et al. "LOT: Layer-wise Orthogonal Training on Improving l2 Certified Robustness." Advances in Neural Information Processing Systems (NeurIPS), 2022.

[2] Singla et al. "Improved deterministic l2 robustness on CIFAR-10 and CIFAR-100." International Conference on Learning Representations (ICLR), 2022.

[3] Wang et al. "Better diffusion models further improve adversarial training." International Conference on Machine Learning (ICML), 2023.