We sincerely appreciate the detailed proof verification, the interest you've shown in our paper, and the evaluation towards acceptance. We answer the main weaknesses raised in your review, and hope this can help you to increase your score.

About experiments

What is accurate and robust AOC? Are only the architectures different or also the training?

The architectures, detailed in Appendix H, play a role in the accuracy/robustness tradeoff, but the main factor remains the loss:

• The “robust” setting uses the scaled cross-entropy with margin (Prach et al.) to promote robustness.
• The “accurate” setting uses Cosine similarity, chosen for its scale invariance. (Bethune 2021) showed the standard cross-entropy contains a term that promotes robustness (as softmax is not scale invariant).

This will be clarified in the main part of the manuscript (sect 3.1 l383).

Can you also construct an accurate/robust BCOP?

The “BCOP accurate” leads to the same accuracy as the “AOC accurate” on Cifar-10, since as stated l405 “AOC does not improve the expressiveness of its original building blocks (namely BCOP)”, and was thus not reported. The BCOP robust on Cifar10 is equivalent to the first line of Table 2. However, note that the BCOP method cannot scale on the Imagenet dataset.

Please include some SOTA non-orthogonal network as a reference to show the gap between orthogonal and non-orthogonal networks

Table 2 includes some SOTA non-orthogonal networks, such as AOL, SLL, or Li-Resnet, that are non-orthogonal.

It would be good to compare the different convolution approaches with minimal differences in the rest of the hyperparameters…

We made the choice to compare the published version for each method since the optimal architecture can be different. An empirical comparison of previous methods was already done by (Pratch et al.). The authors chose to use a fixed budget of 24 GPU hours, Since AOC is much faster than BCOP, It is expected to outperform BCOP in their comparison.

About novelty and name of the method

The authors overstate (or rather misstate) their contributions a bit. In abstract and introduction, the authors write, they would introduce a new method. Instead they should rather present their contribution as it is: The introduction of stride, dilation, grouping etc. to BCOP

The abstract indicates that “AOC [is] a scalable method for constructing orthogonal convolutions, effectively overcoming these limitations [i.e. strides, dilations, group, convolutions, and transposed convolutions]”, we don’t understand what in this sentence “overstates” the contribution? Could you please clarify?

In the introduction, we state clearly the novelty and difference with BCOP in Table 1. The bullet points in l82-l102 list the properties AOC achieves simultaneously.

Also, besides the kernel construction, our contribution is 3 fold:

• The method itself. Despite the method's apparent simplicity, the work to achieve this is non-trivial: as discussed in the paper, the construction requires multiple criteria to be orthogonal, and its proof requires numerous results to be complete.
• A mathematical framework that allows one to navigate between three aspects of the convolutions seamlessly: its kernel tensor, its Toeplitz matrix, and its pytorch code. This makes many results simple to prove and extends beyond AOC (Appendix E shows how we can improve SLL, SOC, and Sandwich in nontrivial ways)
• An efficient implementation that makes the usual slowdown negligible. That is packaged in an open-source library. This library also centralizes and improves multiple existing methods (as stated in Appendix E)

name of the method (adaptive orthogonal convolutions) a bit odd

We understand the concern of the reviewer , we use the word ‘adaptive’ in the sense that it can be adjusted to the layer modern features. We were thinking about Flexible Orth Conv , but the acronyms is often understood as Free-Of-Charge

Others

give a bit more intuition on some of the claims. For instance, Prop 2.4

We appreciate the reviewer’s suggestion to provide more intuition. We will provide when possible in the main paper an intuition of the proof.

Proposition 2.7 is trivial. It basically states that the transposed matrix of a matrix with orthogonal columns has orthogonal rows

We acknowledge that the mathematical framework we introduced makes the proof of this proposition trivial. However, it has implications regarding practical implementation (direct use of torch.nn.conv_transpose_2d) and orthogonality under stride, groups and dilation. For instance, as indicated l251, transposition of stride convolution could be used in upsampling layers of U-Nets.

Reference

We would like to thank the reviewer for the pointer on (Hertrich et al.), which we missed as we focused on reparametrization methods. We totally agree with its relevance.

We would like to thank the reviewer for his comprehensive review. We sincerely appreciate the effort put into it and hope our response will be at the same level. We organized our answers into 4 sections that cover the various questions and remarks.

About the experiments:

• Q5) GANs and normalizing flows: We also believe that AOC can be impactful for GANs/NF; however, the training competitive GAN/NF deserves its own 9 pages and are let for future works as indicated in the conclusion. In L375, we explained our choices to evaluate AOC. These experiments were done to support two claims: 1. AOC is expressive, and 2. AOC is the most viable option for training large-scale orthogonal CNNs.
• Q2) Thank you for the relevant reference. The scalability of AOC is first demonstrated In Table 2 as AOC is the only method to successfully train an orthogonal CNN on Imagenet-1K. Moreover Table 3 shows the low memory consumption and low overhead which are key for further scaling of orthogonal networks.
• Q4) In Table 2, we took the number from (Hu et al. 2023, “A recipe for…”) instead of (Hu et al.2023, “Unlocking …”). We apologize for the issue, and these numbers will be updated. AOC tested with similar techniques as (Hu et al. 2023) achieves 74.85% of certified robust accuracy with a network that has half the width of LiResnet (the width was set to 256 instead of 512 to obtain results within the rebuttal period).
• Why we did not put ResNet18 in Table 2: We chose to display only Lipschitz-constrained networks (i.e. that offer robustness certificates) to avoid losing the reader.

About novelty:

We state clearly the novelty and difference with BCOP in Table 1. The bullet points in l82-l102 list the properties AOC achieves simultaneously.

Our contributions are 3 fold:

1. The method itself. Despite the method's apparent simplicity, the work to achieve this is non-trivial: as discussed in the paper, the construction requires multiple criteria to be orthogonal (and a special attention on the choice of channel dimensions and the order of convolution composition), and its proof requires multiple results to be complete.
2. A mathematical framework that allows one to navigate between three aspects of the convolutions seamlessly: its kernel tensor, its Toeplitz matrix, and its pytorch code. This makes many results simple to prove and extends beyond AOC (Appendix E shows how we can improve SLL, SOC, and Sandwich in nontrivial ways)
3. An efficient implementation that makes the usual slowdown negligible. That is packaged in an open-source library. This library also centralizes and improves multiple existing methods (as stated in Appendix E)

About the writing:

• Q0.a: Lipschitz/orthogonal constraints: We agree with suggestion to move the L380 in the introduction and will use it to clarify the point.
• Q0.b: For ease of reading, we use “orthogonal” to refer to “row/column orthogonal” depending on the shape. We state “row/column” when this information is important. It will be clarified in L161.
• L45: orthogonal refers to (Anil et al. 2019) and not to the global 1-Lip approach. This will be clarified by moving “(Anil et al. 2019) an approach that requires the use of orthogonal layers.” to line 12.
• l27: (Miyato et al., 2018) will be moved to l26.
• L38: We cited this theoretical paper to balance the citations of (Wang et al., 2020; Qi et al., 2020) that are more empirical. We agree that the link is indirect since the generalization bounds assume 1-Lipschitz networks constructed using the product bound and not orthogonal layers. It can be removed if the reviewer considers this misleading.
• L87: We agree that “mitigating vanishing gradient” is a more appropriate title for this paragraph. Thanks for the suggestion.
• L365: We cited (Anil et al. 2019) for its direct application to certifiable robustness, but we agree with the relevance of (Bartlett et al. 2017).

Questions:

Q1 [Batchnorm]: Yes, all our networks are trained without batch normalization (in the line of (Xiao et al., 2018)). This is especially true for our imagenet results. We agree this is We agree this is important to highlight in the paper.

Q3 [invertible convolution layer]: In our framework, this demonstration becomes easy. Given

$y = \text{conv}_{K}\text{(x, stride=s)} \quad \Longleftrightarrow \quad \bar{y} = (\mathcal{S}_s\mathcal{K})\bar{x} \quad \text{(Eq.2-3)}$

If the convolution is orthogonal (not row/column orthogonal), we have

$(\mathcal{S}_s\mathcal{K})^{-1} = (\mathcal{S}_s\mathcal{K})^T \quad \text{(Def.2.2)}$ and then,

$\bar{x} = (\mathcal{S}_s \mathcal{K})^T \bar{y} \quad \Longleftrightarrow \quad x = \text{ConvTranspose}_K\text{(y, stride=s)} \quad \text{(Def 2.6)}$

We sincerely appreciate your thoughtful evaluation and the interest you've shown in our paper, particularly regarding its practical contributions.

In addition to the implementation-oriented aspects that you seem to highly appreciate, we would like to highlight the theoretical novelty of our work: The proposed mathematical framework provides a unified perspective over three key aspects of convolutions that allows the theoretical proofs of the orthogonality for five distinct types of convolution operations (classic, dilated, strided, group, transpose).

Besides, we would like to emphasize that, due to the constraint of orthogonal convolution (such as the existence described in Achour et al. 2022, or proposition 2.3), the choice of channel dimensions and the order of convolution composition are both non-trivial and essential to ensure orthogonality (which is another contribution of this paper).

We hope this further clarifies the depth and originality of our contributions and reinforces your positive view of the paper’s potential impact.

We want to thank the reviewer for his review. We will provide additional information that we hope you to find relevant.

About 1. While AOC does not improve the expressiveness of its original building blocks, its flexibility unlocks the construction of complex blocks as depicted in Fig. 5a. Given a fixed compute budget, AOC allows the training of larger architectures for more steps, (thanks to our fast implementation, which is also our contribution). This ultimately leads to improved performances.

About 2&3. Certifiable robustness gives guarantees for any possible adversarial attack. However, multiple works have shown a tradeoff between robustness and accuracy. This tradeoff is responsible for the low accuracies found in this field. “AOC accurate” lines show that our networks are as expressive as unconstrained networks when the training does not optimize certified robustness. This leads to 0.0% certified robustness (even if empirical attacks may not achieve this 0% score).

About 4. Although the authors dubbed their network as “liresnets” their architecture significantly differs from the usual resnets (as our network). Given these differences, we chose to stick to a known architecture (Resnet34) in Table 3 to ensure a fair comparison.

We hope that these points will convince you of the paper's potential.