An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Authors: Thibaut Boissin
Franck Mamalet
Thomas Fel
Agustin Martin Picard
Thomas Massena
Mathieu Serrurier
Venue: ICML 2025 poster (2025)
Keywords: Machine Learning
Orthogonal convolutions
certifiable adversarial robustness
Lipschitz neural networks
Primary area: deep_learning->robustness
TL;DR: A method to construct scalable orthogonal convolutions that support striding, grouping, transposition and dilation.

Abstract: Orthogonal convolutional layers are valuable components in multiple areas of machine learning, such as adversarial robustness, normalizing flows, GANs, and Lipschitz-constrained models. Their ability to preserve norms and ensure stable gradient propagation makes them valuable for a large range of problems. Despite their promise, the deployment of orthogonal convolution in large-scale applications is a significant challenge due to computational overhead and limited support for modern features like strides, dilations, group convolutions, and transposed convolutions. In this paper, we introduce **AOC** (Adaptive Orthogonal Convolution), a scalable method that extends a previous method (BCOP), effectively overcoming existing limitations in the construction of orthogonal convolutions. This advancement unlocks the construction of architectures that were previously considered impractical. We demonstrate through our experiments that our method produces expressive models that become increasingly efficient as they scale. To foster further advancement, we provide an open-source python package implementing this method, called **Orthogonium**.

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Thibaut Boissin 12
Franck Mamalet
Thomas 3el Mathieu Serrurier
Agustin Martin Picard
Thomas Massena 42
Abstract
being prime candidate: such networks allowing the compu- tation of robustness certificates. Initially, researchers experi- mented with regularization techniques (Cisse al. 2017); however, constrained networks, especially those employing orthogonal layers, soon became central, as they provided the advantage of tighter certification bounds: The overall Lips- chitz constant of sequence of layers is typically estimated as the product of the individual layer constants; however, this bound is often loose, and computing the exact constant is NP-hard (Virmaux & Scaman 2018). (Anil et al. (019) shows that combining MaxMin activation with orthogonal layers makes the aforementioned bound tight. Beyond ro- bustness, orthogonal layers also play a key role in enhancing performance normalizing flows. Normalizing flows are generative models that transform simple distributions into complex ones via invertible mappings (Dinh et al. 2017 Rezende & Mohamed] 2015). Orthogonal convolutions enable these transformations with computable Jacobian determinant, thus improving training efficiency (Kingma & Dhariwal 2018) and forming the basis for invertible residual networks (Behrmann et al., 2019). Additionally, orthogonal layers stabilize training deep and recurrent neural networks (RNNs) by preserving gradient norms through time, essen- tial in capturing long-term dependencies in time-series, such as language and speech tasks (Kiani et al. 2022 Qi ct al.
Orthogonal convolutional layers are valuable com- ponents in multiple areas of machine learning. such as adversarial robustness, normalizing flows, GANs, and Lipschitz-coonsraineed models. Their ability to preserve norms and ensure stable gradi- ent propagation makes them valuable for large range of problems. Despite their promise, the deployment of orthogonal convolution in large- scale applications is a significant challenge due to computational overhead and limited support for modern features like strides, dilations, group convolutions, and transposed convolutions. In this paper, introduce AOC (Adaptive Orthogonal Convolution), a scalable method that extends the work of (Li et al. 2019), effectively overcoming existing limitations in the construction of orthog- onal convolutions. This advancement unlocks the construction of architectures that were previously considered impractical. We demonstrate through our experiments that our method produces expres- sive models that become increasingly efficient as they scale. To foster further advancement, we provide an open-source python package imple- menting this method, called Orthogonium)
2020 Bansal al. 2018). ) Lastly, in Wasserstein GANs (WGANs) (Arjovsky et al. 2017) orthogonality in both the discriminator and generator (Müller et al. 2019) supports stability and expressivity without requiring weight clipping or gradient penalties (Gulrajani et al., (2017), making es- sential for large-scale GAN training (Brock et al., [018] Miyato al. 2018). See Appendix A for detailed list of applications.
1. Introduction and Related Works
Orthogonal layers have become fundamental components in various deep learning architectures due to their unique math- ematical properties, which offer benefits across multiple applications. For instance, robustness against adversarial attacks can be achieved by managing a model's 's Lipschitz constant (Szegddy et al. 2014) - with 1 1-Lipschitz networks
Despite these benefits, extending orthogonality to convolu- tional layers remains challenging. The orthogonalization of large Toeplitz matrices-structures central to convolution- challenging to do without compromising its convolutional properties and is sometimes non-feasible (Achour al. 2022). Early approaches (Wang et al.) 2020 Qi et al. 2020 explored regularization, yet practical constraints led to the following solutions:
'Institut de Recherche Technologique Saint-Exupery, France IIII, France 'Kempner Institute, Harvard University, USA "Innovation & Research Division, SNCF, France. Correspondence to: Thibaut Boissin <thibaut.boissin saintxxperyy.com Franck Mamalet wfranck.mamaleed irt- saintexupery.com>>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Explicit Construction Methods, Building on (Xiao et al.

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Orthogonal
Equivalent
Kernel
Code
available
Change
Channels
Stride
Conv
Transpose
Groups
Dilation
Method
Size
BCОP
Li ct al.
2019)
k
2
X
SC-FAC
Su et al.
2022
k separable
2
ECO
Yu et al.
2022
Iw x In Tw x In
Cayley
Trockman & Kolter 2021
2
X
LOT
al.
2022)
In x In
X
X
ProjUNN-T
Kiani al. [2022)
In X In composed
SLL
Araujo et al. 2023)
X
Sandwich
Wang & Manchester 2023)
X
composed
AOL
Prach & Lampert 2022)
k
SOC
(Singla & Feizi| 20216)
k + (m
X
AOC
(Ours)
k
Table 1: Comparison of orthogonal convolution methods. A check mark (V) indicates full support for the feature, cross mark (X) indicates lack of support (in the implementation). and approximate symbol (#r) indicates partial support (emulation). Here, k denotes the kernel size, and La x Jn represents the input dimensions. The pip package of AOC provides an implementation supporting strides, dilations, group convolution and transposed convolution. This work also covers the conditions under which other methods could support those features.
2018), approaches like BCOP (Li et al. 2019), SC-Fac (Su ct al. 2022), and ECO YYu et al. 2022) construct orthogonal convolutions directly in the spatial domain. These methods maintain orthogonality but often lack flexibility in kernel
Le 2019) (grouped convolutions). On the other end, perfor- mance in certifiable adversarial robustness tied to model size and training duration (Prach et al., 2024). However, 1-Lipschitz constrained networks lack the usual scaling laws Prach & Lampert 2024), often requiring massive datasets even for small-scale problems (Hu et al. 2023). Developing an efficient and scalable method that supports modern fea- tures method could address both challenges simultaneously.
size control and do not support operations like striding and transposed convolutions.
Frequency Domain Approaches. Methods such as Cayley Convolution (Trockman & Kolter 2021). LOT (Xu et al. 2022], and ProjUNN-T (Kiani et al.) 2022) enforce orthog- onality by parameterizing kernels in Fourier space, albeit the cost of increased computational complexity and con- straints on spatial or grouped convolutions.
Our Contributions. In response to the limitations of existing methods, we introduce Adaptive Orthogonal Convolution (AOC), method that combines two existing approaches to construct convolution layers that address the following key constraints simultaneously while remaining efficient:
Composite Layer Techniques. Skew Orthogonal Convo- lutions (Singla & Feizi, 2021b) combine multiple convolu- tional layers to approximate orthogonality, resulting in an orthogonal block that uses convolutions.
AOC enforces strict orthogonality, allow- ing convolutional layers to retain essential properties across applications.
Orthogonal:
Mitigating vanishing gradients. In some cases, strict or- thogonality is relaxed. Leading layers that are 1-Lipschitz while mitigating vanishing gradients. This avoids the com-
putational demands of full orthogonalization (Prach & Lam
Explicit: In contrast frequency domain methods, AOC generates explicit convolution kernels in the spa- tial domain, allowing straightforward implementation in standard deep learning frameworks without special- ized operations or significant computational overhead.
pert 2022
Meunier et al. 2022 Araujo et al. 2023).
Despite their success in certifiable adversarial robustness, these methods have seen limited adoption in other fields. This is largely due to implementation limitations: current layers fail to support essential features like stride, groups, or dilation, which are critical for architectures such as U- Nets (Ronneberger et al., 2015). GANs (Goodfellow et al.] 2014). VAEs (Kingma 2013) (upsampling convolutions), dilated CNNs (Li et al. 2018) (dilation), and modern mod- els like ResNeXt (Xie al. 2017) and EfficientNet (Tan &
Flexible: Supporting a range of essential operations including striding, transposed convolutions for up- sampling, grouped convolutions, and dilation - AOC adapts effectively to modern neural network architec- tures.
Scalable: Designed for large-scale applications, our
2

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
implementation maintains efficiency, incurring only 10% slowdown compared to unconstrained models in realistic ImageNet IK (Deng et al. 2009) training setup.
the input tensor. We describe the convolution operation with three equivalent notations:
K xy I
(Kernel notation)
(I)
y = S.K.F
(Toeplitz notation)
(2)
To underscore the advantages of our method, we include comparative summary in Table highlighting support for key features across different methods. By combining orthog- onality, explicit construction, and flexibility, our approach seamlessly bridges theoretical rigor with practical efficiency in deep learning models. Beyond AOC, this work introduces a mathematical framework that unlocks improvements of other existing methods such as SOC, SLL, or Sandwich (See Appendix E. Our implementation is available in package called Orthogonium/ which also contains improved implementations of other existing meth- ods.
y = conv (2, stride = 8)
(Code notation)
Equation (1) defines the convolution operation with kernel
K and stride s applied on z. Equation ( highlights that this convolution is equivalent a linear operation defined by matrix product between Toeplitz matrix K. R har and a vector E E Resww, which is obtained by flattening The striding operation is represented by a masking diagonal matrix S. E R 4 xcshw with ones on the selected entries and zeros elsewhere. When s = 1, we have S = I, the identity matrix (with kernel I). Equation (3) shows these notations in pseudo-code form.
rigorously tested and
The paper is organized as follows: Section 2 outlines the three main aspects of AOC its core tools, kernel construc- tion, and scalable implementation. Section 3.2 presents an evaluation of the method's 's performance in terms of speed and expressive power. Finally, Section 4 discusses how our approach can enhance existing methods in the literature.
The Block- convolution, denoted as B T A, computes the equivalent kernel of the composition of two convolutional kernels, A and B, enabling their combined effect without performing each convolution separately.
Definition 2.1 (Block-convolution
(B& & A) *, x B (A k1 x)
(4)
S,(BA)z = (S,B)AA
(5)
2. An Adaptive scheme to build Orthogonal Convolution (AOC)
conv 8) conv (x. 1), s)
(6)
We will first recall the definition and properties of the Block- convolution in Section 2.1 This tool is used in Section 2.22 construct orthogonal kernels explicitly, with the support of modern convolution features. Finally, Section [.3] provides implementation details that allow the method scale.
This operator assumes that the number of input chan- nels of the second convolution B matches the num- ber of output channels of the first convolution A (condition denoted as A x B). Given A Remn x and B E Resxems xk2 then B @ A E (5x
()x +Af -1), The computation of
Block convolutoottn kernel weights is given by:
2.1. Core tool: Block-convolution
Gin -1 - k 119-165
k -1
Our approach builds upon three foundational papers: (Xiao
(B ② A) A)m,n,is
Σ
B Bm o Anmi-ri-s
et al. 2018). which generalized orthogonal initialization to convolution enable training networks with 10 000 lay-
5'=0
ers, though without addressing constrained training: (Su et al. 2022), which tackled this for separable convolutions:
where A is zero-padded, i.e., Ac,,is = 0ifi (0, k or j $ [0, Kg While a classic result, for completeness, we pro- vide the proof for ID convolution kernels in Appendix G This operator C, using matrix products between order tensors, should not be confused with standard convolution, which takes 4-dimensional tensor and a 3-dimensional in- put tensor. The complexity of these weight computations is
and (Li et al. 2019), which extended it to general 2D con- volutions. These works rely heavily on a tool known as Block-convolution. In this section, we review, clarify, and extend this mathematical framework.
Notations: We consider convolutional layers character- ized by c. the number of output channels; c;, the number of input channels; hn x k2, the kernel size; s, the stride parameter; 9. the number of groups; d the dilation rate For simplicity in the notation, we fix the group parameter to g = and d = 1 by default (all proofs hold for other values of g and d, see Section 2.2). Also, we assume circular padding in all proofs. The kernel tensor of the convolution is denoted K E Boxxx. xk, xk2, while z E RRox xhx denotes
2
O (CoCsCint Il (k2 k -1) necessitating an efficient p=1
implementation, detailed in Section 2.3
Block-convolution and Orthogonality: We will recall
the definition of an orthogonal convolution, using Eq. (5)
and the definition of an orthogonal matrix:
Initiially denoted by (Li et al. 2019 as
3

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Definition 2.2 (Orthogonal Convolution). A convolation defined by Eq. 22) is row/columm orthogonal iff:
the efficiency of modern neural network architectures, emu- lation is not viable option for computationally demanding scenarios.
(S,K) =I (row orthogonal)
(S.1)) II (column orthogonal)
The strategy of AOC. The core idea of our method is to combine several convolution kernels with an efficient implementation of the Block-convolution @ to build any type of orthogonal convolution. We mainly build upon two type of kernels: one that guarantees orthogonality for any kernel size (when orthogonality for any stride s. BCOP and SC-Fac (Li et al.) 2019: [S et al.) (2022). by leveraging Block-convolution @, are effective for the first kemel,, whereas other methods lack control over the kernel size. For the second kernel, RKO (Serrrierr et al. 202[) is the only viable option, as all other methods depend on stride emulation.
The type of orthogonality (row or column) is determined by the larger dimension of the matrix in the toeplitz nota- tion (Eq. (2)) When qgs² > Co. SeK is column orthogonal (Achour et al. 2022). When c₁s² = Co. S₂K is a square ma- trix, and the two conditions are equivalent. Unless explicitly stated, we will use the term orthogonal to refer to row (resp. column) orthogonal. Finally, when & = 1, the condition on the Toeplitz matrices is equivalent to K @ K (resp. KT K I). A formal definition of KT can be found in
1) and another that guarantees
Definition 2.6
Through this paper. we leverage the Block- convolutovottion prop- erty to compute implicitly the composition of convolutions. This operation preserves orthogonality when the following requirement is met:
Standard Orthogonal Convolution For standard orthog- onal convolutions with fixed kernel size, we rely on three main works (Xiao et al., 2018). (Li et al. 2019), and (Su) et al. 2022). In Appendix B we unify these works within a consistent notation framework, highlighting similarities and differences among their approaches to constructing stan- dard orthogonal convolutions (i.e., without stride, trans- position, grouping, or dilation). These methods primarily rely on constructing elementary blocks (1 1, 2, and 2 x 1 orthogonal convolutions) and assembling these blocks to create orthogonal convolutions of the desired size and shape. Briefly, both methods construct symmetric projec- tors (matrices such that N = N2 = NT and (T-N)= = (1 - N)² = (1 - N))). This property allows to construct orthogonal convolution whose kernel size is x 2 (resp.
Proposition 2.3 (Composition of Orthogonal Convolutions). The composition of two row orthogonal convolutions a row orthogonal convolution:
AA = I and BB =I AB(AB)* I
The same applies to two column orthogonal convolutions.
The proof is straightforward using the Toeplitz notation and matrix multiplications. Note that, the composition of a row orthogonal with column orthogonal convolution is, in general, not orthogonal. This will significantly influence the construction of AOC convolutions.
x 1).
Li et al. 2019 Xiao et al. 2018 chose compose (k1 1) 2 1 kernels Pi with (k: 1) x 2 kernels Qi and 1 x I
2.2. Construction of Strided, Transposed, Grouped, Dilated, Orthogonal Convolutions with AOC
kernel M to form a k1 x k2 kernel:
As mentioned previously, existing methods for explicit or- thogonal convolution construction face several challenges that hinder their scalability in modern CNNs. Frequency- domain approaches, for instance, require computing the FFT on input images, which becomes prohibitive for large im- age resolutions (e.g., 224x224 in ImageNet- 1 K). Methods like SOC, LOT, ECO, and Cayley (Singla & Feizi 2021b Xu et al. 2022 Yu et al. 2022 Trockman & Kolter 2021 handle cases where e f c, through inefficient padding or channel dropping, further limiting their practicality. Most of these methods also emulate striding, using a channel signifi-
K BBOP = (Pk-1 @ Qk-1)
M Ixl
pairs of 1x2 and 2x1 kernels
A detailed description of the BCOP method is provided in Fig. I with additional details in Appendices and G.3 for the proof of orthogonality. It is also worth noting that both approaches have the same number of parameters, which is lower than the number of parameters required to span all orthogonal convolutions. This is further discussed in Appendix F
reshaping method called InveribleDownSampphnn cantly increasing the computational cost compared to native striding (see Section 2.2). Beyond inefficiency, these limita- tions prevent the adoption of essential modern convolutional features such as strides, transposition, groups, and dilation. Since these features were specifically designed to enhance
Native Striding for Orthogonal Convolutions Classical convolutional networks use strided convolutions. However, most existing work on orthogonal convolutions does not sup- port stride directly, instead emulating striding via a reshap- ing operation (Shi et al. 2016): transforming the c, x II, x I tensor into 0:8 x In x Is tensor, followed by a non-strided
4

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Start with a 1x1 kernel
3) Combine kernels to reach the desired size
5) The resulting kernel can be used normally in the forward
Standard
K BCOP
M
Strided
1
K Kxoe
Transposed
(1x1) 9 + 8=1
(2x2) - 8-88
Grouped
(K- (k+1s) 9 0, s=1
Dilated
K RRKO
(kxc)
Sgr 5ma
(axs)
(2x2) c C.C, c,6=1
4) Construct extra
Q
kernel to support stride
2) Construct a 2x2 kerne using BCOP
BCOP
Figure I: AOC enables the construction of orthogonal kernels with customizable sizes and strides. By leveraging the @ operator, we can fuse kernels obtained from two existing methods, namely BCOP and RKO. With this approach, we can build orthogonal kernels that support native striding, effectively mitigating the drawbacks of the two base methods.
convolution. Unlike native striding, emulation increases the number of parameters of the convolution (s2 times more pa- rameters), which means constraining larger matrices. Since algorithms used for this tasks have cubic time complexity in the number of channels (Prach et al., 2024). emulation induces prohibitive cost for strided convolutions (s times slower). Beyond this limitation, emulated striding also pre- vents native implementation of transposed convolutions with stride (see Section 2.2). In this section, we propose method to construct orthogonal kernels that support native striding.
fusion results in an orthogonal convolution of kernel size 1y x k2 and stride
While the formulation (Eq. ( may seem straightforward, the order of composition and the choice of the internal channel size are crucial to preserve orthogonality.
Proposition 2.5 (Orthogonality strided AOC). The com- position of two kernels K Rexe, (xxxcxxx++--))x66 and KRKO E Rexxeesxs (Eq. ( with an internal channel size max(c;, [ yields orthogonal convolution with stride.
To our knowledge, only two works (Serrurier et al. 2021 2024) claim to use native stride. These rely on method referred to by (L et al., 2019) as Reshaped Kernel Orthogo- malization (RKO). This method involves reshaping the ker- nel KRKO E R x., xk, xk2 into a matrix K' E x. and orthogonaliziig it. In general, with the adequate multi- plicative factor, the resulting convolution is 1-Lipschitz but not orthogonal. In this work, factor is required when k = s to obtain orthogonal con- volution. This result can be carefully combined with BCOP (Section 2.2) to provide orthogonal convolutions of desired kernel size and stride.
The proof of Proposition relies on Proposition 2.3 which holds for strided convolutions applied to S.KRKO. is detailed in Appendix G.5). We prove that when min(c;, S S max(c; 3 ), the two matrices ÆCCCр and S,KRKo are ei- The
ther both row-orthogonal or both column-orthogen choice e = max(ci, [ maximizes the expressiveness of the parametrization while ensuring that the resulting con- volution is orthogonal. Note that the size of the KgCОP imposes the condition k: + 1 2 0. However, accord- ing to (Achour et al., 2022), orthogonal kernel exists when > k. Therefore, our approach encompasses all valid configurations of orthogonal convolutions.
prove that no additional
Proposition 2.4 (RKO gives orthogonal kernel when k = l2 s). When K' E Rookk is orthogonal, the convolution with the reshaped kernel KRKO E RCc xe; xkxk and a stride = is orthogonal.
Native Transposed Orthogonal Convolutions In addi- tion to the practical verification of orthogonality Def- inition 2.2 transposed convolutions are mostly used as learnable upscaling layers in architectures such as U- Net (Ronneberger et al. 2015) VAEs (Kingma) 2013 Van Den Oord et al. 2017). Even though some methods in Table can provide transposition for standard convolu- tion, none are applicable to strided convolutions due to their use of emulation via reshaping, as described in Section 2.2 Thus, AOC is the first method to support transposed orthog- onal convolutions with upscaling.
The proof of Proposition 2.4 relies on the introduction of permutation matrix on the inputs, and is given in Ap- pendix G.4, The proposed method, called AOC, combines the BCOP and RKO methods to construct a Strided Convo- lution with Arbitrary Kernel Size:
(8) As shown in Fig. I by choosing specific sizes for KBCOP E Rex, xkk+ +1-)) x Ths and KRKO Rexxxxxxx the
K AOC KRKO KECOP
5

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Yes
Kgcor
@
DOOO
def fast__ blck_.com n2, groups-1l:
**"compute m2wm1
n. n. k1 h2 #1 shape
nb. mb. 11. 12 #2 shape
Yea
BKD
f2
12 = torch. mn func Lional, conv2di
n kernels fused in log(n) iterations
al. a2, Troups-groups...
padding=:11 12
Cp
return r2. transpese
K KECO
No
Parsimonious
(a) Fast block convolution. We opti- mized the 2D convolution in order to com- pute the @ operator with maximum paral- lelism.
parametrization. The method can sometimes simplify to quicker equivalent parametrization.
(b) Parallelize BCOP iterations. By leveraging associativ- ity of @, we can compute the iteration in O log(n) steps using parallel associative scan.
Figure 2: Fast implementation of AOC. We achieve highly scalable parametrization thanks to optimizations at every level of our method: starting from the @ operator 2a to BCOP to our complete method It results in method with a lower overhead as scale increases.
For given convolution with stride defined by Eq. (2) the transposed convolution corresponds to the application of the transposed matrix (S,K.², inverting the role of e and Co- The resulting operation can be defined by the three notations:
considerations related to the preservation of orthogonal- ity under conditions such as stride, groups, and dilation. For instance, transposed strided convolutions can be effec- tively utilized in the upsampling layers of U-Net architec- tures (Ronneberger et al. (2015). They can also be employed to design invertible neural networks for Normalizing Flows (see Appendix G.10).
Definition 2.6 (Transposed Convolution). A transposed
convolution is defined as follows:
y = k *1
(9)
Native Grouped Orthogonal Convolutions: Most mod- emn CNNs grouped convolutions (Howard) 2017: Xie
g = (8,K) = KT
(10)
et al. 2017: Liu et al. 2022). Beyond its advantages in terms of parameters and computational efficiency, it makes AOC more efficient as its parametrization can be parallelized, sim- ilarly as (Gorbunov et al.] 2024, Liu et al.) 2024). Given group number 9, the kernel of a grouped convolution K E R 3 xkxk can be viewed as a stack of g kernels K; R Se Si xkxk, each constructed independently. Note that c, and e; must be multiple of y.
y = ConvTranspose & (x, stride
(11)
The code notation (Eq. (1]) corresponds to the implemen- tation in PyTorch parametrized by the original kernel K. The Eq. (10) corresponds to the transposition of the under- lying Toeplitz. matrix. The kernel notation (Eq. 9 can be viewed as a standard convolution with a transposed kernel and fractional striding. The kernel KT E xgoxxxxxkp x is obtained by transposing the channel dimensions (the first ones) and reversing the kernel ones (the last two). By using an orthogonal direct convolution K KAoc, this construction results in orthogonal transposed convolution. Although the definition and proof are straightforward, the practical application requires the explicit construction of a strided orthogonal convolution kernel (as detailed in Eq.
Proposition 2.8 (Grouped Orthogonal Convolution). grouped convolution composed of g kernels (Ki), is or- thogonal if and only if each individual convolution of kernel K; is orthogonal.
The proof of Proposition 2.8 is provided in Appendix G.7 and relies on the fact that the Toeplitz matrix of a grouped convolution is block diagonal. Note that when each kernel K, has a single channel c = Co = 1 that cannot be built with BCOP which requires c 2 2.
Proposition 2.7 (Transposed Orthogonal Convolution). The transposition of row orthogonal convolution is a column orthogonal convolution, and vice versa.
Co.
The proof is straightforward with the Toeplitz matrix tation, but is given for completeness in Appendix G.6] It is worth noting that, despite its apparent simplicity, Proposition [2.7 has important implications for practical implementation particularly concerning the direct use of torch. nn. conv transpose2d. Moreover, raises
Native Orthogonal Convolutions with Dilation: Intro- duced by (Yu & Koltun 2016), Dilation is an effective means to increase the receptive field of a convolution with- out increasing its number of parameters or its computational cost. In (Su et al., 2022), the authors stated in an appendix that "any filter bank that is orthogonal for standard convo-
6

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
lution is also orthogonal for a dilated convolution and vice versa." While this is mathematically accurate, it is essential to note that circular padding must be adjusted accordingly to remain within the scope of their theorem. Our method thus also supports orthogonal convolution with dilation. A description is given in Appendix G.8
compute the batched in parallel.
Efficient implementation. By examining Eq. (8). one observes that, depending the values of and k. the parametrization can be simplified to either KAoc = KECOP or A = KRKO- While BCOP is generally not suited for handling stride directly, we have identified specific cases- namely when C, < Co - where stride can indeed be applied directly to a BCOP kemnel (see Appendix (.9) without re- quiring the full parametrization. Although not proposed in (Li et al. 2019). this observation refines our overall charac- terization of BCOP's limitations with stride, showing that exceptions exist under certain conditions. The complete de- cision tree used in our implementation is shown in Fig. 2c with each branch's 's orthogonality proved in Appendices G.4 G.5 and
2.3. Efficient implementation of AOC
Beyond a mathematical framework that unlocks a more flex- ible use of orthogonal convolutions, we propose several design choices for an implementation that scales well to larger kernels, larger images and larger batch sizes. Al- though AOC includes the construction of BCOP and RKO kernels, our implementation improves the original ones at many stages. It results in an 8x reduction of the original overhead in realistic settings. The implementation of AOC and several additional layers described in Appendix E is pro- vided as an Open- Open-source library called OOtthooonium| Other implementation details and empirical testing are discussed in Appendices andd D
3. Evaluation and applications
In this section, we evaluate the expressiveness and scala- bility of AOC convolutions. To assess expressiveness, we require a benchmark that also accounts for the orthogonality property. We evaluate this within the framework of certi- fiable robustness using I-Lipschitz constrained networks, where enforcing orthogonality tightens Lipschitz estimation, improving robustness. AOC strictly represents 1-I.ipschitz networks. The
Fast implementation of the Block-convolution. To the best of our knowledge, the only differentiable implementa- tion of the BCOP method is available in the reference code (Li et al., 2019). However, since there is no cuda kernel available for Block-convolution, the authors relied on nested loops to perform all matrix multiplication to compute the resulting kernel. We propose an efficient and parallelized implementation with single operation. Inspired by (Wang ct al. 2020) and (Delattre et al. 2023), which aimed to compute A @ AT to prove orthogonality, we propose to replace the computation B @ A by convolution with zero padding between B and AT. This approach can also be seen as a specific case of convolutional einsum (Rabbani et al.] 2024). This operation can be rewritten by re-ordering the summation to use 2D convolution at its core. The strategy to use the 2D convolution to compute one output filter. Then, the batch dimension can be used to compute all output filters in parallel. The code is detailed in the Fig.
functions, crucial for Supschitz-constrainng overall Lipschitz constant of a sequence of layers is typically estimated as the product of the individual layer constants; however, this bound is often loose, and computing the ex- act constant is NP-hard (Virmaux & Scaman 2018). (Amil et al. 2019) shows that combining MaxMin activation with orthogonal layers makes the aforementioned bound tight. (Bartlett et al., 2017) showed that if f is a I-Lipschitz clas- sification function and is the label index, a lower bound on robustness radius in Le norm at x is:
f(x) max, fx);
V2
This certificate is independent of adversarial attacks, ensur- ing robustness remains unchanged even if new attacks arise. It is also computationally cheap and optimizable in loss function (Singla & Feizi 2022
Reducing time complexity of BCOP. Beyond the effi- cient parallelism of the @ operation, we propose to paral- lelize the whole kernel computation: the parametrization can be seen as the composition of many small kernels. Not only can those be created in parallel, but they can also be combined efficiently. As the @ is an associative operation (Proposition G.I], we can leverage the parallel associative scan (Zouzias & McColl 2023 Hillis & Steele Jr 1986) to parallelize the iterations of the original algorithm. The original 2+ (k- - s) sequential @ operations can then be done in Olog(k - s)) iterations (Fig. 2b). This is unlocked in practice if @ implementation supports batching. We propose to achieve this by using grouped Conv2d implementation: by concatenating 9 kernels and setting groups- = 9, we can
Hu et al. 2023).
To showcase AOC's expressiveness and scalability, we conduct experiments on CIFAR-10, a widely used bench- mark for certifiable robustness, and ImageNet, a large-scale dataset. We train two networks per task: one prioritizing accuracy-noted "AOC accurate" in Table and the other robustness-denoted "AOC robust"- -enabling thorough eval- uation. Finally, the training recipe of (Hu et al. (023) was used with original convolutions replaced by AOC, show- casing its expressiveness with extra data. This last recipe is denoted "AOC robust*". For scalability, we compare AOC's s computational overhead on a standard architecture, assessing its feasibility in large-scale applications.
7

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Provable Accuracy
with similar sizes and similar training cost their uncon- strained counterparts; The "AOC accurate" training config- uration (in Table 2 achieves more than 90% clean accuracy on CIFAR- 10 using less than 3M parameters, showing that AOC is expressive. This comes at the cost of 0% provable accuracy (certificates smaller than the radius = 36/255); regardless of its resilience to empirical adversarial attacks. Conversely, the AOC robust provides a high certifiable ac- curacy (64.3%), but lower clean accuracy (74% instead of 91.5%), illustrating the well-known accuracy-robustnes trade-off (Béthune et al., 2022). Finally, networks trained with AOC do not use normalization techniques such as batch normalization (loff & Szegedy 2015) or layer normaliza-
Acc- uracy
Trainable Parameters
Models
36
253
ВCOP
72.2
58.2
2.6M
GloRo 77.0
58.4
8.0M
Local-Lip-Bt
77.4
60.7
2.3M
Cayley Large
74.6
61.4
21.0M
CIFAR- 10
SOC 20
78.0
62.7
27.0M
SOC+ 20
76.3
62.6
27.0M
CPI. XI.
78.5
64.4
236.0M
AOL Largel
71.6
64.0
136.0M
SLL Small
71.2
62.6
41.0M
SLL Medium !
72.2
64.3
78.0M
tion (Ba et al. 2016).
SLL Larget
72.7
65.0
118.0M
SLL X- X-Largef
73.3
65.8
236.0M
Observation 2: Old methods become competitive with scale. Scaling the original BCOP network of (Li al. 2019) from 2.6M to 41.3M parameters makes this method competitive with more recent approaches (+6% on provable accuracy). This is especially notable as our experiments did not use techniques such as last layer normalization(Sing & Feizi 2022), certificate regularization (Singla & Feizi
Li-Resnets TM
82.1
70.1
49.0M
Li +
87.0
78.1
49.0M
AOC accurate
91.5
00.0
2.3M
AOC robust
74.0
64.3
41.3M
AOC robust*
85.3
75.0
46.3M
Li-Resnets 45.6
35.0
86.0M
2021b). DDPM augmentation (Hu al. 2023). This was possible only due to the fast implementation of AOC, which enables larger batch sizes and faster training.
Li- fi-Resnets++**
49.0
38.3
86.0M
AOC accurate
68.2
00.0
53.1M
AOC robust
42.1
26.3
53.1M
Observation 3: State of the art aligns with computational
budget. Our experiments align with the work of (Prach & Lampert 2024 Bubeck & Seilke 202I), who noted that ro- bust training does not have the same scaling laws as standard training: in order to obtain robustness, alongside accuracy and generalization, more data and larger architectures required by an order of magnitude greater than was is cur- rently being done. This explains why (Hu et al. (2023) used 4.5 million of images for their results on CIFAR-10, highlighting the need for scalable implementations that can handle this trend.
Table 2: AOC is competitive on small-scale datasets and enables affordable training on large-scale datasets. For both cifar-10 10 (top) and Imagenet-1K (bottom), we reported provable accuracy (accuracy guaranteed under any attack whose radius is 255 ) from respective papers. we evaluate models under two settings: one tailored for accuracy and another for robustness. denotes the use of extra data, Our networks are trained under two settings that use similar architectures but differ in their loss parameters (see Ap- pendix Hb. denotes nonorthogonal methods.
3.2. Scalability of AOC
3.1. Certifiable robustness with I-Lipschitz Networks.
As observed by (Prach et al. 2024), a slow implementation leads to increased training time and, consequently, lower per- formances in practical contexts. In this section, we demon- strate that AOC offers key advantage: its computational cost does not depend on the input size or shape, making it well-suited for large- scage-scale datasets, where handling large images is crucial. Although other methods may perform bet- ter on smaller datasets, they struggle to scale to widely used architectures like ResNet-34 (He et al., 2016), as shown in Table 3 On the other end, our method's low memory cost enables larger batch sizes, and since parameterization is batch-size independent, the overhead decreases batch size increases. Ultimately, this results in training time only 13% slower than its unconstrained counterpart. The detailed protocol detailed in Appendix H.I
Detailed architectures and training parameters are detailed in Appendix H We report in Table both the standard and provable accuracy and compare with previous methods. We will highlight the interest of AOC through the 3 following observations.
Observation 1: AOC allows construction of expressive I-Lipschitz networks. While AOC does not improve the ex- pressiveness of its original building blocks (namely [COP[T] its flexibility unlocks the construction of complex blocks as depicted in Fig. 5a Such a block permits the training of I-Lipschitz networks that achieve competitive performance
"proportion of samples with certificate greater than see Appendix for the reproduction of their results
8

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Name
Batch Size
Train Time (ms)
Train Memory (GB)
Test Time (ms)
Test Memory (GB)
Conv2D (ref)
128
137 (1.00x)
4.7 (1.00x)
50 (1.00x)
1.4 (1.00x)
AOC (ours)
128
239 (1.75x)
5.3 (1.15x)
53 (1.06x)
1.4 (1.02x)
BCOP
128
389 (2.85x)
8.6 (1.84x)
62 (1.25x)
1.5 (1.06x)
SOC
128
664 (4.86x)
12.8 (2.73x)
429 (8.55x)
1.8 (1.30x)
Cayley
128
584 (4.27x)
19.0 (4.07x)
247 (4.94x)
2.0 (1.45x)
Conv2D (ref)
256
284 (1.00)
(1.00))
(1.000)
2.7 (1.00x)
AOC (ours)
256
354 (1.25x)
9.8 (1.07x)
97 (1.06x)
2.7 (1.01x)
BCOP
256
624 (2.20x)
13.9 (1.53x)
135 (1.48x)
2.8 (1.03x)
Conv2D (ref)
512
550 (1,00x)
17.9 (1.00x)
172 (1.00x)
5.3 (1.00x)
AOC (ours)
512
622 (1.13x)
18.6 (1.04x)
176 (1.02x)
5,4 (1.01x)
BCOP
512
1116 (2.03x)
24.6 (1.38x)
256 (1.48x)
5.4 (1.02x)
Table 3: AOC benefits from scale. As demonstrated on ResNet-34, previous methods impose significant overhead when input images are large (224 x 224). In contrast, since our method's ' computational cost is independent of layer input size, its overhead decreases as batch size increases. Furthermore, the low memory overhead enables larger batches at scale.
4. Conclusion and Broader Impact
References
In this paper, we introduced AOC, method that combines two existing approaches in order to build orthogonal convo- lutions that support essential features such as stride, trans- position, groups, and dilation. Our results demonstrate that this layer is both expressive and scalable. Beyond its stan- dalone benefits, our framework enhances existing layers: In Appendix we integrate our method with SLL (Araujo et al. block, propose optimizations to reduce the memory foot- print of SOC (Singla & Feizi 2021a), and present strategy to make Sandwich layers (Wang & Manchester 2023) scal- able for convolutions. Besides, AOC, by unlocking features such as transposition, grouping, or dilation, paves the way for future work leveraging orthogonality varied architec- tures and applications, such upsampling convolutions for U-Nets (Ronneberger al. 2015), VAEs (Kingma 2013).
Achour, E. M., Malgouyres, F., and Mamalet, F. Existence, stability and scalability of orthogonal convolutional neu- ral networks. Journal of Machine Learning Research, 23 (347):1-56, 2022.
Anil, C., Lucas, J., and Grosse, R. Sorting out lipschitz function approximation. In International Conference on Machine Learning, pp. 291-301. PMLR, 2019.
2023 to build an efficient downsampling residual
Araujo, A., Havens, A. J., Delattre, B., Allauzen, A., and Hu, B. unified algebraic perspective on lipschitz neural networks. In The Eleventh International Conference on Learning Representations, 2023.
Arjovsky, M., Chintala, S., and Bottou, L. Wasserstein gen- erative adversarial networks. In International conference on machine learning, pp. 214-223. PMLR, 2017.
WGANs and Optimal transport (Arjovsky et al. 2017
Béthune 2024), or reduced complexity (Li et al. 2018 Xie
Ba, J. L., Kiros, J. R., and Hinton, G. E. Layer normal- ization. In Deep Learning Symposium at Advances in neural information processing systems, 2016.
et al. 2017). In support of further research and development,
we open sourced our implementation in the Orthogonium
library.
Bansal, N., Chen, X., and Wang, Z. Can we gain more from orthogonality regularizations training deep networks? Advances Neural Information Processing Systems, 31, 2018.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Bartlett, P. L.,, Foster, D. J., and Telgarsky, M. J. Spectrally-normmaiized margin bounds for neural net- works. Advances in neural information processing systems, 30, 2017.
Acknowledgement
This work was carried out within the DEEL project which is part of IRT Saint Exupéry and the ANITI AI cluster. The authors acknowledge the financial support from DEEL's Industrial and Academic Members and the France 2030 pro- gram Grant agreements nº 23-1ACL-0002.
Behrmann, J., Grathwohl, W., Chen, R. T., Duvenaud, D., and Jacobsen, J.-H. Invertible residual networks. In International conference on machine learning, pp. 573- 582. PMLR, 2019.
and n² A-N--
Béthune, L. Deep learning with Lipschitz constraints, PhD thesis, Université de Toulouse, 2024.

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Béthune, L., Boissin, T., Serrurier, M., Mamalet, F., Friedrich, C., and Gonzalez Sanz, A. Pay attention your loss: understanding misconceptions about lipschitz neural networks. Advances in Neural Information Processing Systems, 35:20077-20091 2022.
Delattre, B., Barthélemy, Q. and Allauzen, A. Spec- tral norm of convolutional layers with circular and zero paddings, arXiv preprint wwXv::2402.00240, 2024.
Deng. J., Dong, W., Socher, R., Li, L.-J., Li, K., and
Fei-Fei, L. Imagenet: A large-scale hierarchical image database. In IEEE conference on Computer Vision and Pattern Recognition, 2009.
Béthune, L.,, Massena, T., Boissin, T., Bellet, A., Ma- malet, F., Prudent. Y., Friedrich, C., Serrurier, M., and Vigouroux, D. DP-SGD without clipping: The lips- chitz neural network way. In International Conference on Learning Representations, 2024.
Ding, X., Zhang, X., Han, J., and Ding, G. Scaling up your kernels to 31x31: Revisiting large kernel design in CNNs. In IEEE/CVF conference on Computer Vision and Pattern Recognition, 2022.
Björck, A. and Bowie, C. An iterative algorithm for com- puting the best estimate of an orthogonal matrix. SIAM Journal on Numerical Analysis, 8(2):358-36) 364, 1971.
Dinh, L., Sohl-Dickstein, J., and Bengio, S. Density esti- mation using real nvp. In International Conference on Learning Representations, 2017.
Boroojeny, A. E., Telgarsky, M., and Sundaram, H. Spec- trum extraction and clipping for implicitly linear layers. In International Conference on Artificial Intelligence and Statistics, pp. 2971-29799 PMLR, 2024.
Fazlyab, M., Robey, A., Hassani, H., Morari, M., and Pap- pas, G. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in neural information processing systems. 32, 2019.
Boureau, Y.-L., Ponce, J., and LeCun, Y. A theoretical analysis of feature pooling in visual recognition. In International Conference on Machine Learning, 2010.
Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley. D., Ozair, S., Courville, A., and Bengio, Y. Generative Adversarial Nets. Advances in neural information processing systems, 2014.
Brock, A., Donahue, J., and Simonyan, K. Large scale gan training for high fidelity natural image synthesis. In International Conference on Learning Representations, 2018.
Gorbunov, M., Yudin, N., Soboleva, V., Alanov, A., Naumov, A., and Rakhuba, M. Group and shuffle: Efficient struc- tured orthogonal parametrization. Advances in neural information processing systems, 2024.
Bubeck, S. and Sellke, M. A universal law of robust- ness via isoperimetry. Advances in Neural Information Processing Systems, 2021.
Grishina, E., Gorbunov, M., and Rakhuba, M. Tight and efficient upper bound on spectral norm of convolutional layers. In European Conference on Computer Vision, pp. 19-34. Springer, 2024.
Cayley, A.
Sur quelques Propriétés des Déterminants Gauches, pp. 332-336. Cambridge Library Collection Mathematics. Cambridge University Press, 1846.
Cisse, M., Bojanowski, P., Grave, E., Dauphin, Y., and Usunier, N. Parseval networks: Improving robustness to adversarial examples. In International Conference on Machine Learning, pp. 854-863. PMLR, 2017.
Gulrajani, I., Ahmed, F,, Arjovsky, M., Dumoulin, V., and Courville, A. C. Improved training of wasserstein gans. Advances in neural information processing systems. 30, 2017.
Coddington, F. A., Levinson, N., and Teichmann, T. Theory of ordinary differential equations, 1956.
Hasannasab, M., Hertrich, J.. Neumayer, S., Plonka, G., Set- zer, S., and Steidl, G. Parseval proximal neural networks. Journal of Fourier Analysis and Applications, 26:1-31, 2020.
Combettes, P. L. and Pesquet, J.-C. Lipschitz certificates for layered network structures driven by averaged acti- vation operators. SIAM Journal on Mathematics of Data Science, 2(2):529-557, 2020.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In IEEE conference on Computer Vision and Pattern Recognition, 2016.
Defazio, A., Yang. X., Khaled, A. Mishchenko, K., Mehta, H., and Cutkosky, A. The road less scheduled. Advances in Neural Information Processing Systems, 2024.
Hertrich, J., Neumayer, S., and Steidl, G. Convolutional proximal neural networks and plug-and- play algorithms. Linear Algebra and its Applications, 631:203-222 2021.
Delattre, B., Barthélemy, Q., Araujo, A., and Allauzen, A. Efficient bound of lipschitz constant for convolutional layers by gram iteration. In International Conference on Machine Learning, pp. 7513-7532, PMLR, 2023.
Hillis, W. D. and Steele Jr, G. L. Data parallel algorithms. Communications of the ACM, (1112):117011111 1986.
10

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Howard, A. G. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint 2017.
Meunier, L., Delattre, B. J., Araujo, A., and Allauzen, A. A dynamical system perspective for lipschitz neu- ral networks. In International Conference Machine Learning, pp. 15484-15506 PMLR, 2022.
Hu, K., Leino, K., Wang. Z., and Fredrikson, M. A recipe for improved certifiable robustness. In International Conference on Learning Representations, 2023.
Miyato, T., Kataoka, T., Koyama, M., and Yoshida, Y. Spec- tral normalization for generative adversarial networks. In International Conference on Learning Representations. 2018.
loffe, S. and Szegedy, C. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448 456. pmlr, 2015.
Müller, J., Klein, R., and Weinmann, M. Orthogonal wasser- stein gans. arXiv preprint 11Xvv:191L.33066 2019.
Kiani, B., Balestriero, R., LeCun, Y., and Iloyd, S. projunn: efficient method for training deep networks with unitary matrices. Advances in Neural Information Processing Systems, 35: 1444- 2022.
Pauli, P., Wang, R., Manchester, I. R., and Allgöwer, F. Lipschitz- ID convolutional neural networks us- ing the cayley transform and the controllability gramian. IEEE Conference on Decision and Control, 2023.
Pauli, P., Gramlich, D., and Allgöwer. F. Lipschitz constant estimation for general neural network architectures using control tools. arXiv preprint arXiv:2405.00 125, 2024.
Kingma, D. P. Auto-encoding variational bayes. arXiv preprint 1r2iv:1312.6114, 2013.
Kingma, D. P. and Dhariwal, P. Glow: Generative flow with invertible 1xl convolutions. Advances in neural information processing systems, 31, 2018.
Perko, L. Differential equations and dynamical systems, volume 7. Springer Science & Business Media, 2013.
Prach, B. and Lampert, C. H. Almost-orthogonal layers for efficient general-purpose purpose lipschitz networks. In European Conference on Computer Vision, pp. 350-365. Springer, 2022.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images, 2009.
LaPlace, S. Théorie analytique des probabilités. Courcier, 1820. URL
Prach, B. and Lampert, C. H. Intriguing properties of robust classification. arXiv preprint arXiv:2412.04245, 2024.
Li, Q. Haque, S., Anil, C., Lucas, J.. Grosse, R. B., and Ja- cobsen, J. Preventing gradient attenuation in lipschitz constrained convolutional networks. Advances in neural information processing systems. 32, 2019.
Prach, B., Brau, F., Buttazzo, G., and Lampert, C. H. 1- Lipschitz layers compared: Memory speed and certifi- able robustness. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2024.
Li, Y., Zhang, X., and Chen, D. CSRNet: Dilated convolu- tional neural networks for understanding the highly con- gested scenes. In IEEE conference on Computer Vision and Pattern Recognition, 2018.
Qi, H., You, C., Wang, X., Ma, Y., and Malik, J. Deep isometric learning for visual recognition. In International conference machine learning, pp. 7824-7835. PMLR, 2020.
Liu, W., Qiu, Z., Feng, Y., Xiu, Y., Xue, Y., Yu, L.,, Feng, H., Liu, Z., Heo, J., Peng, S., et al. Parameter-efficient orthog- onal finetuning via butterfly factorization. In International Conference on Learning Representations, 2024.
Rabbani, T., Su, J., Liu, X., Chan, D., Sangston, G., and Huang, F. conv conv_einsum: A framework for represen- tation and fast evaluation of multilinear operations in convolutional tensorial neural networks. arXiv preprint arXiv:2401.03384, 2024.
Liu, Z., Mao, H., Wu, C.-Y., Feichtenhofer, C., Darrell, T., and Xie, S. A convnet for the 2020s. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 19976691986...1 2022.
Rezende, D. and Mohamed, S. Variational inference with normalizing flows. In International conference on machine learning, pp. 1530-1538. PMLR, 2015.
Massena, T., Andéol, L., Boissin, T., Friedrich, C., Mamalet, F., Serrurier, M., and Gerchinovitz, S. Efficient robust conformal prediction via lipschitz- lipschitz-bounded bounded networks. In International Conference on Machine Learning. PMLR, 2025.
Ronneberger, O., Fischer, P., and Brox, T. U-net: Con- volutional networks for biomedical image segmenta- tion. In Medical image computing and computer-assister Intervention-MICCO Springer, 2015.

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Sanyal, A., Torr, P. H., and Dokania, P. K. Stable rank normalization for improved generalization in neural networks and GANs. In International Conference Learning Representations, 2020.
conference machine learning, pp. 6105-6114. PMLR, 2019.
Trockman, A. and Kolter, J. Z. Orthogonalizing convolu- tional layers with the cayley transform. In International Conference on Learning Representations, 2021.
Sedghi, H., Gupta, V., and Long, P. M. The singular values of convolutional layers. In International Conference Learning Representations, 2018.
Trockman, and Kolter, Z. Patches are you need? Transactions on Machine Learning Research, 2024.
Senderovich, A., Bulatova, E.., Obukhov, A., and Rakhuba, M. Towards Practical Control of Singular Values of Convolutional Layers. Advances in Neural Information Processing Systems, 35:10918-10998 December 2022.
Van Den Berg, R., Hasenclever, L.., Tomczak, J. M., and Welling, M. Sylvester normalizing flows for variational in- ference. In 34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018, pp. 393-402. Association For Uncertainty Artificial Intelligence (AUAI), 2018.
Serrurier, M., Mamalet, F., González-Sanz, A., Boissin, T., Loubes, J.-M., and Del Barrio, F. Achieving robustness in classification using optimal transport with hinge regular- ization. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 505-514, 2021.
Van Den Oord, A., Vinyals, O., Neural discrete representation learning. Advances in neural information processing systems, 30, 2017.
Virmaux, A. and Scaman, K. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018.
Serrurier, M., Mamalet, F., Fel, T., Béthune, L., and Boissin, T. On the explainable properties of 1-lipschitz neural networks: An optimal transport perspective. Advances in Neural Information Processing Systems, 36, 2024.
Wang, J., Chen, Y., Chakraborty, R., and Yu, S. X. Orthogo- nal convolutional neural networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp- 11505-11515, 2020.
Shi, W., Caballero, J., Huszár, F., Totz, J., Aitken, A. P., Bishop, R., Rueckert, D., and Wang, Z. Real-time sin- gle image and video super-resolution using an efficient sub-pixel convolutional neural network. In Proceedings of the IEEE conference on computer vision and pattern recogmition, pp. 1874-1883, 2016.
Wang. R. and Manchester, I. Direct parameterization of lipschitz-bounded deep networks. In International Conference on Machine Learning, pp. 36093-361 10. PMLR, 2023.
Singla, S. and Feizi, S. Fantastic four: Differentiable and ef- ficient bounds on singular values of convolution layers. In International Conference on Learning Representations, 2021a.
Wang. Z., Hu, B., Havens, A. J., Araujo, A., Zheng, Y., Chen, Y., and Jha, S. On the scalability and memory effi- ciency of semidefinite programs for lipschitz constant es- timation of neural networks. In The Twelfth International Conference on Learning Representations, 2024.
Singla, S. and Feizi, S. Skew orthogonal convolutions. In International Conference on Machine Learning, pp. 9756-9766. PMLR, 2021b.
Xiao, L., Bahri, Y., Sohl-Dickstein, J., Schoenholz, S., and Pennington, J. Dynamical isometry and mean field theory of cnns: How to train 10,000-layer vanilla convo- lutional neural networks. In International Conference on Machine Learning, pp. 5393-5402, PMLR, 2018.
Singla, S. and Feizi, S. Improved techniques for deter- ministic 12 robustness. Advances in Neural Information Processing Systems, 15:16110-16144 2022.
Su, J., Byeon, W., and Huang, F. Scaling-up up diverse or- thogonal convolutional networks by a paraunitary frame- work. In International Conference Machine Learning, pp. 20546-205777 PMLR, 2022.
Xie, S., Girshick, R., Dollar, P., Tu, Z., and He, K. Ag- gregated residual transformations for deep neural net- works. In 2017 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 5987-5995. IEEE Computer Society, 2017.
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. Intriguing proper- ties of neural networks. In International Conference Learning Representations, 2014.
Xu, X., Li, L., and Li, B. Lot: Layer-wise orthogonal training on improving 12 certified robustness. Advances in Neural Information Processing Systems, 35:18904- 18915, 2022.
Tan, M. and Le, Q. Efficientnet: Rethinking model scal- ing for convolutional neural networks. In International
12

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Yang, Z., Feng, R., Zhang, H., Shen, Y., Zhu, K., Huang. L., Zhang, Y., Liu, Y., Zhao, D., Zhou, J., al. Lips- chitz singularities in diffusion models. In The Twelfth International Conference on Learning Representations, 2023.
Yu, F. and Koltu,, V. Multi-scale context aggregation by dilated convolutions, In ICLR, 2016.
Yu, T., Li, J., Cai, Y., and Li, Constructing orthogo- nal convolutions in an explicit manner. In International Conference Learning Representations, 2022.
Zouzias, A. and McColl, W. F. A parallel sean algorithm in the tensor core unit model. In European Conference on Parallel Processing, pp. 489-502. Springer, 2023.
13

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Contents
Introduction and Related Works
2
An Adaptive scheme to build Orthogonal Convolution (AOC)
Core tool: Block-convolution
2.2
Construction Strided, Transposed. Grouped, Dilated, Orthogonal Convolutions with AOC
2.3
Efficient implementation of AOC
Evaluation and applications
3.1
Certifiable robustness with 1-Lipschitz Networks.
8
3.2
Scalability of AOC
8
Conclusion and Broader Impact
Applications of orthogonal convolutions
15
BCOP and SC-Fac re-explained with our framework
16
Impact of the orthogonaliiattin scheme on AOC
17
Non exhaustive list of orthogonalization methods
17
C.I.I
QR Factorization via Modified Crram-Schmid)
17
C.1.2
Cayley Transform
18
C.1.3
Exponential Map
18
C.1.4
Cholesky Decomposition
18
C.1.5
Björck and Bowie
19
Impact on AOC
19
Empirical evaluation of the Lipschitz constant of our method
20
Using the content of this paper to improve SLL, SOC, and Sandwich
21
E.1
Improving skew orthogonal convolution (SOC)
22
Improving SDDP-hased Lipschitz Layers (SLL)
22
Improving Sandwich Layers
23
Extending Applicability other methods,
24
About the incomplete parametrization of BCOP and SC-fac
24
Understanding the Limitations of BCOP
24
Proofs
24
Proof of the @ property:
24
14

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
G.2
Recall of other properties
25
Proof of the construction of C C X orthogonal convolution
25
G.4
RKO kemnel with stride = k builds an orthogonal convolution
27
G.5
AOC convolutions are orthogonal
27
G.6
Transposed orthogonal convolutions
28
G.7
Grouped orthogonal convolutions
28
G.8
Dilated orthogonal convolutions
29
G.9
Conditions under which stride can be directly applied on BCOP
29
G.
10
Conditions of invertibility of AOC layers
30
Architecture and training details
30
H.I Scalability experiment
32
Reproducing the results from BCOP paper
33
A. Applications of orthogonal convolutions
Orthogonal layers have become fundamental components in various deep learning architectures due to their unique mathematical properties, which benefit multiple applications.
Provable Robustness with 1-Lipschitz Networks. Ensuring robustness against adversarial attacks is a critical challenge. Early work in this field (Szegedy et al.) 2014) identified a link between network's 's adversarial robustness and its Lipschitz constant, which led to the development of networks with a Lipschitz constant of one (1-Lipschitz networks). Initially, regularization techniques were used (Cisse et al. 2017), but interest in constrained networks quickly grew. Orthogonal layers, in particular, have inherent Lipschitz constant of one, they preserve the input norm through each transformation. This property is instrumental in achieving provable robustness by allowing for certified bounds the network's output perturbations in response to adversarial inputs (Anil et al. 2019). By controlling the network's sensitivity to input changes, orthogonal layers play a crucial role in building models resilient to adversarial manipulations. Besides robustness, Lipschitz- constrained networks have diverse applications: they are closely linked to WGANs and optimal transport (Arjovsky et al.. 2017 Béthune 2024), enable scalable differential privacy (Béthune et al. 2024), allow conformal prediction adversarial setting Massena et al. 2025), and prevent singularities in diffusion models Yang et al. 2023). Additionally, they guarantee the existence and uniqueness of solutions in classification (Béthune al. 2022 and flow-matching networks (Perko 2013
Coddington al. 1956).
Enhancing Performance in Normalizing Flows. Normalizing flows class of generative models that transform simple probability distributions into complex ones through series of invertible and differentiable mappings. Although they have different objectives, this domain intersects with the field of provable adversarial robustness. For instance, (Dinh) et al. 2017] Rezende Mohamed| (2013) employs a channel masking scheme, which was later used to emulate striding in Lipschitz layers designed for adversarial robustness. Separately, Lipschitz layers can be applied to build invertible residual networks (Behrmann et al., 2019). In both fields, orthogonal convolutions are essential, as they facilitate the construction of invertible transformations with tractable Jacobian determinants. The use of orthogonal layers ensures that the Jacobian determinant is constant or easily computable, simplifying likelihood estimation during training (Kingma & Dhariwal] 2018). This property enables efficient and stable training of normalizing flow models, leading to improved performance in density estimation and generative tasks.
Stabilizing Training in Deep and Recurrent Neural Networks. Training recurrent neural networks (RNNs) involves propagating gradients through time, which can lead to vanishing or exploding gradients due to the multiplicative nature of sequential weight applications. Orthogonal weight matrices in RNNs help preserve the gradient norm across time steps, By constraining recurrent weights to be orthogonal,
thus preventing degradation of the learning signal (Kiani et al. 2022
15

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
the network maintains consistent flow of information, enabling it to capture long-term dependencies more effectively, This stabilization is essential for tasks requiring understanding long-range dependencies in time series, such language modeling and speech recognition. These approaches also facilitate the training of very deep networks (Qi et al. 2020) with
improved generalization properties (Bansal et al. 2018).
Improving Stability in Wasserstein Generative Adversarial Networks. Generative Adversarial Networks (GANs) are powerful models for generating realistic data, but they often suffer from training instability. Wasserstein GANs (WGANs) (Arjovsky et al. 2017) address this issue by optimizing the Wasserstein distance between the real and generated data distributions. A key requirement for WGANs is that the discriminator (or critic) function must be Lipschitz continuous. Orthogonal layers naturally satisfy this Lipschitz condition, eliminating the need for techniques like weight clipping or gradient penalties (Gulrajani al. 2017), which can adversely affect training dynamics. By incorporating orthogonal convolutions into the discriminator, WGANs achieve more stable training (Miyato et al.) 2018 Müller et al.) 2019) and produce higher-quality generative results. Orthogonality has been integral to the successful scaling of GAN training (Brock ct al. 2018).
Extending the applicability of Proximal Neural Networks. Proximal Neural Networks (PNNs) offer a principled approach to designing and training deep architectures by drawing inspiration from optimization theory sppeciiccall proximal algorithms and o-averaged operators (Hasannasab et al.] 2020 Combettes & Pesquet 2020 A central insight in this framework is the emergence and enforcement of orthogonality in learned operators, which can improve network stability. (Hertrich et al., (02T)) proposes an extension to convolutional operators but notes that, for limited kemel sizes, optimizing on the manifold is challenging and instead relies on penalization, similar to (Wang et al. 2020). Using our method, AOC, and its transpose could overcome this limitation.
B. BCOP and SC-Fac re-explained with our framework
In this section, outline the key steps in constructing orthogonal convolutions using the BCOP (Fig. 1 SC-Fac methods within the framework established in the paper.
From Orthogonal Matrices to Orthogonal Co x x 1 x 1 Convolutions. A substantial body of research exists on building orthogonal matrices M E XR, One common approach involves applying a differentiable projection operator to an unconstrained weight matrix, yielding an orthogonal matrix such that M M or M M = 1. Various methods exist, including the Björck and Bowie orthogonalization scheme (Björck Bowie 197Ip, the exponential method (Singla & Feizi] 2021b), the Cayley method (Trockman & Kolter, 2021). and QR factorization Van Den Berg et al., 2018). An orthogonal matrix can easily be reshaped into convolution kernel with a 1 x 1 kernel M E Rex and such convolution is orthogonal if M is orthogonal. These convolutions are mainly used to change the number of channels (Fig. 1-1).
Building e X C X 1 x 2 Orthogonal Convolutions. Stacking two orthogonal 1 x 1 convolution kernels along their last dimensions" 4 leads to a 1 x 2 convolution, though it is generally not orthogonal. Authors of (Xiao et al. 2018 Su et al., 2022) noted that additional constraints are needed, proposing a half-rank symmetric projector to construct a 1 x 2 orthogonal convolution: from a column-orthogonal matrix M E Rex $ the matrix N = MM E Rexx is symmetric projector that satisfies:
N 2 NT and
(I-N) = - -I- N)² (I Ny²
These two matrices can be reshaped into e x 1x convolution kernels, and stacking them along the last dimension results in an orthogonal x c x 1 x convolution kernel:
P = stack( 1 NJ, axis = 1) + P c pT =
Similarly, stacking along the penultimate dimension, Q stack [N, I N) axis 2), results in orthogonal x e 2 xx1 1 kernel. Although already proven by previous work, proof of this can be found in Appendix G.3
From x 2 to k x 1z Orthogonal Convolutions. The three papers propose to build standard orthogonal convolutions by composing smaller kernels based on the following properties:
*Done in practice with torch.stack ( [K 1, K 2], axis--1) "This implies that 2 2. When is even, [$] used practice
16

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Using Block-convolution, we can represent the composition of 2 and 2 x kernel obtain kernel with any desired shape. The differences among the three approaches lie in the composition order: Authors of (Su et al., 2022) chose to compose (k1 - 1) 2 x kernels Pi. followed by 1 kernel M, and (k2 x 2 kernels Qi to form a k k2 kernel:
Ksc
Pki .....
P1
M @ Q1
+
Qk2-1
all Ix2 kernels
Ixl
all 2xl kemels
the other hand, authors of (Li el al. 2019 Xiao et al. 2018 alternated 2 x and x 2 kernels, ending with a x convolution:
K BCOP
(Pk- o Qk
....
(Pr
Q1
C
M
pairs of 1x2 and 2xl kernels
Ixl
Both approaches have incomplete parametrizations: the first is limited to separable convolutions, while the second shows counterexamples in the general 2D convolution case. However, both methods use the same number of parameters for a given kernel size. Building a complete parametrization of 2D convolutions remains an open question, discussed in Appendix [F] We thus base our work on the BCOP parametrization (Li et al. 2019) for two main reasons: (1) any 2 x convolution parametrizable by BCOP be represented with 3 kernel feasible solution given the trend toward larger kernels
(Trockman & Kolter 2024 Ding et al. 2022); (2) BCOP enables faster and less memory-intensive implementation (see
Section 2.3
unlocking larger networks that compensate for any potential expressiveness loss.
C. Impact of the orthogonalization scheme on AOC
In this section we will discuss on of the design choices for AOC: the orthogonalization procedure. Many approaches exists and we will describe the main approaches:
C.I. Non exhaustive list of orthogonalization methods
C.1.1. QR FACTORIZATION VIA MODIFIED TRAM-SCHMIDT
The QR factorization is obtained using the Modified Cram-Schhidtt (MGS) algorithm, as initially proposed in (LaPlace 1820). The MGS procedure follows the same fundamental computational steps the classical Gram-Schmidt method; however, it executes these steps in different order. In classical Gram-Schmidt, each iteration involves computing that includes all previously computed vectors. Conversely, the modified version corrects numerical errors at each step, leading to improved numerical stability.
Algorithm QR Factorization via Modified Gram-Schmidt
Require: W [ws]sejo.c-11 E RCxC
Ensure: W -RR, where Q O(C)) is an orthogonal matrix and R E ROxC is an upper triangular matrix.
1: procedure MODIFIED GR GRAM-SCHMIDT(WW)
2: u = w/, Vi E [0, -1]
> Initialize with a copy of W
3: for j E range(C) do
4:
TJ. || ll2
5:
Qj w w
6:
for A: E range(j + 1, C*) do
7:
rj of of
8:
wf = wf Tj
9:
end for end for
10:
return QR
end procedure
"As indicated in Definition 2.2 k and la parameters not affect row or column orthogonality
17

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
C.1.2. CAYLEY TRANSFORM
The Cayley transform Cayleyy (846) provides an alternative approach for constructing orthogonal matrices. It exploits
the bijective relationship between the special orthogonal matrices Q (i.e., orthogonal matrices with determinant +1) and skew-symmetrrc matrices A (satisfying A -A). The transformation is defined follows:
Q -))-A\++A7*
Q Q=
(12)
matrix A can be naively constructed as a skew-symmetrie matrix using:
A = M - M.
(13)
The extension of the Cayley transform to rectangular matrices is detailed in (Pauli et al. 2023) and is formalized in Algorithm 2
Algorithm 2 Cayley Transform Algorithm
Require: W E R MxC, where M > C
Ensure: W MxC an orthogonal matrix
procedure CAYLEY TRANSFORM(W)
2:
U.V W C,:], W[C .,:l
Partition W such that U E RCxC and V R(M-C)xC
3:
A = U - - VTV
Note: A is not strictly skew-symmetric
4:
B (I+A)-
5:
WI -B(I A)
> W E Rxx > W2 E R M M-C)xC CxxC
6:
We = BVV
7:
W [W1, W2]
P Concatenation yields W MxC
8: return W
9: end procedure
This approach involves matrix inversion, which can be computationally expensive, particularly for large matrices.
1.1.3. EXPONENTIAL MAP
The exponential map (Singla & Feizi 2021b) is another technique used to generate orthogonal matrices, leveraging the properties of skew-symmetric matrices. The matrix exponential of A is defined as:
exp(A)
(14)
h!
km0
For skew-symmetric matrix A, it can be shown that:
(eA)T=
(15)
Since the product of a matrix and its transpose is the identity matrix, this ensures that e is orthogonal.
In practice, numerical computations only approximate the exponential function by summing finite number of terms. Algorithm describes the Exponential Map with spectral normalization to prevent floating-point overflows.
This method parametrizes only the special orthogonal group. The proof follows from the determinant properties of matrix exponentiation.
1.4. CHOLESKY DECOMPOSITION
The Cholesky decomposition has also been employed for orthogonalization (Hu et al. 2023 Given a weight matrix M, we construct the covariance matrix:
C MMT
(16)
18

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Algorithm 3 Exponential Map Algorithm
Require: W E RCxe, P N (number of terms in the expansion)
Ensure: W E RCxc, an orthogonal matrix
1: procedure LIPSCHITZ EXPONENTIAL(W)
2: A W-WT
3:
À 1/
Spectral normalization
4:
W Lc., As Lc
5:
for j E range(1, p) do
A+ A1 x A
6:
x
7:
W- W + An
8:
end for
9:
return W
10:
end procedure
Since C' is positive semi-definite by construction, its Cholesky decomposition exists:
-LT..
(17)
Solving the triangular system LW = .M yields an orthogonal matrix W. To ensure the positive-defimiteness of C, a small positive perturbation is added before decomposition (Hu et al. 2023).
This method is computationally efficient, provided that numerical stability is carefully managed.
C.1.5. BJöRCK AND BOWIE
[Björck & Bowie 1971) proposed an iterative algorithm for computing the best orthogonal approximation of a given matrix.
This process relies solely on matrix multiplications:
W++1 = (1+ WWWWW, WW,,TW,, W.
This algorithm corresponds to the gradient descent of the regularization term |[WWT - 7|2 with a learning rate of B. The convergence radius is 1, determined by the spectral norm of W. To ensure numerical stability, our implementation applies spectral normalization to the matrix. Under these conditions, 3 can be increased to its theoretical maximum of 1. which accelerates convergence.
This specific setting allows for rapid convergence of the algorithm, requiring only 25 iterations, as demonstrated (Anil al. 2019). Additionally, our unit testing scheme reveals that the number of iterations can be reduced to 12 without significant loss of orthogonality. This is achieved through our efficient implementation of the power iteration method, which retains an estimate of the dominant eigenvector across iterations.
C.2. Impact on AOC
Since AOC extensively uses orthogonalization algorithms, it is reasonable to question the original choice made by LLi et al. 2019 Serrurier et al. 2024) to use the Björck and Bowie algorithm. Our implementation allows the use of multiple algorithms, with the currently implemented: exponential method, QR scheme, Björck and Bowic, and Cholesky method. We trained the same network as in (Li et al. 2019) with changing only the orthogonalization method, results are shown in Fig. We observed distinct groups of methods:
exponential: Although one of the most efficient methods, AOC use mainly rectangular matrices. This case was handled using padding, which made the method much slower and hindered optimization.
Björck and Bowie & QR: these methods perform similarly both in terms of speed and accuracy.
cholesky: is significantly faster in this setting but leads to a lower accuracy. The right graph shows that, in fine, advantages and drawbacks of this approach cancel each other out. However, our unit testing scheme has shown that
19

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
AOC does pass the unit tests described in Appendix D
with expected tolerance, needing relaxed tolerance of
5 10-2
2.6
2.6
exp
bjorck
2.5
2.5
cholesky
2.4
2.4
2.3
2.3
Train
Train
2.2
2.2
2.1
2.1
2.0
2.0
100
200
300
400
500
600
2500
5000
7500
10000
12500
15000
17500
Epoch
Runtime (seconds)
Figure Impact of the orthogonalization method AOC: in the same setup (Li al. 2019) observe that the orthogonalization precedure have significant impact the training time and training accuracy. Except from exponential method which suffers from limitations due to our way to handle non-square matrices, other methods shows similar performance given the same computation time.
Given these observations, sticked to the original choice of Björck and Bowie algorithm, is GPU and mixed precision compliant. Thanks unit-testing scheme, observed that once the matrix is constrained to be 1 1-Lipschitz, set = 0.5 (the maximum value for which convergence can be guaranteed). This allows to lower the number of iterations to 12 without affecting orthogonality.
D. Empirical evaluation of the Lipschitz constant of our method
Evaluating the Lipschitz constant of a network Beyond the creation of constrained layer, the evaluation of the Lipschitz constant of layer by itself active field: early work used fast Fourier transform evaluate lower bound of the Lipschitz constant of a convolutional layer with circular padding (Sedghi et al. 2018). This work was later improved with method that is quicker (Senderovich et al.) 2022), supports other types of padding (Grishina et al. (0024) or allows the extraction of a larger part of the spectrum (Boroojeny et al. 2024). The work of (Delattre et al. 2023) (Delattre et al. 2024)
allows us to compute certifiable upper bound efficiently under different types of padding. is worth recalling that inferring global Lipschitz constant a network given the Lipschitz constant of each layer an NP-Hard problem(Virmaux
VVirmuxx &
Scaman 2018). Then, (Pauli et al. 2024; Fazlyab et 2019 Wang al. 2024) aim tackle using SDP -emii-dffiitee programming) tools. Our work also contribute to this issue the orthogonal layer allows tighter product bound (ie.
bound using the product of the Lipschitz constant of each layer to evaluate the constant of the whole network).
The need for empirical evaluation of the Lipschitz constant of AOC. Despite the theoretical guarantees ensuring orthogonality in our construction, empirical checks are necessary to confirm implementation correctness. Such verification prevents two types of issues:
1. Checking of numerical instabilities: Issues arising from floating-point precision, such as those introduced by small epsilon values added to avoid division by zero.
2. Checking for implementation discrepancies: Differences between mathematical formalism and its translation to popular frameworks (c.g., SOC proofs assume circular padding, while its implementation uses zero padding).
Checking the orthogonality of a layer under stride, group, transposition, and dilation conditions. The numerical stability and the convergence of an orthogonal layer dependent on the training papee-paramtter:: mainly the number of
20

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
iterations used in most methods, but the learning rate and weight decay can also play a significant role. We then need an evaluation method that scales along with the convolution and that can be used the end of each training. On the other hand, as scalable methods can be imperfect, we also need a method that computes very precise bounds without making any assumptions on the layer parameters (like padding, or stride). In order to overcome this, we tested our layers with two distinct methods:
1. Explicit SVD Toeplitz Matrices: Using the impulse response approach, we construct the Toeplitz matrix for any padding and stride, allowing direct computation of singular values. This method, though accurate, is computationally expensive for large input images.
2. Product Bound for BCOP and RKO Kernels: methods, while the SVD of the reshaped RKO kernel is used for direct evaluation.
The upper bound for the BCOP kernel is computed using standard
Unit testing of the implementation. We used both of these two approaches in our unit tests. This enables us to ensure that the second method (which is faster and more scalable) is correct to check that our layer is effectively orthogonal. Also, our layer unlocks the use of the transposed convolution, which can used to compute directly the equation orthogonal layers:
(S,K))S,,1)* =I (row orthogonal)
convk (ConTTranspose stride s), stride = 8) =
Naturally, the other direction can also be verified for column orthogonal layers.
To follow the optimization depicted in Fig. 2c we tested each branch independently. For each branch, we tested multiple values for kernel size, stride, dilation, input channels, and output channels. For the kernel size, along with standard configurations of 3 3 and 5 X 5 kernels, we also covered cases for 1 x kernels and even-sized kernels. For input/output channels, covered various values and all the inequalities discussed in this paper (for instance when c, >> c2s²). We ran similar tests for transposed convolution. As the computation of the singular values using the explicit construction of the Toeplitz matrix is quite expensive, we used it on small 8 x 8 images, this is also a good way to check for padding issues, as the kernel size is not negligible with respect to the image size. All the checks over the singular values for both methods were done with a tolerance of le 1e-
Finally, we tested independently the properties of the Block-convolution and the batched Block-convolution.
This amounts to 1442 tests that have the following repartition:
block convolution: 640 tests
convolution: 418 tests
common configurations in CNN: 72 tests extended strided configurations: 150 tests
even kernel size: 24 tests
depthwise: 24 tests
kernel size stride: : 100 tests
conv transpose: 384 tests
RKO: 370 tests
This test bank was of precious use to confirm that all parameters can be combined together in practice. The total coverage of the library is 93%.
E. Using the content of this paper to improve SLL, SOC, and Sandwich
In this section, we will explore how the content of this paper can be used to improve existing layers from the state of the art.
21

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
E.1. Improving skew orthogonal convolution (SOC)
This method, introduced by (Singla & Feizi 2022) uses the fact that an exponential of a skew-symmetric matrix is orthogonal. The initial implementation builds skew- Akew-symmetric kernel and computes the exponential convolution. However, without proper tools to compute the exponential of a convolution kernel, this exponential was computed implicitly for each input by using the Taylor expansion of the exponential (see Eq. (T8).
Theorem E.1 (Explicit conv exponential). We can use Eq.
compute explicitly the exponential of kernel K:
K
K K Ø
x
(18)
11
K + K KOK +
Id K+
(19)
2!
31
Equation 19 shows that we can compute the exponential of a convolution kernel a single time, while the formulation in Eq. 188 needs to done for each input z. In other words, we can apply one conv instead nater convs. Note that the resulting kernel is then larger than the original one (as stated in Table D.. theory, this could unlock large speedups, but the gain is limited practice as the implementation of convolution layers optimized for small kernels and large images (Ding al. 2022). However, the original implementation requires the storage of Riter maps, whereas implementation only one. This, practice, unlocks larger networks and batch sizes.
Also, it is possible to handle change in the number of channels and striding using similar approach as AOC layers.
E.2. Improving SDP-based Lipschitz Layers (SLL)
Kore
K
Kpre K2
ReLU
Rel U
Kpre &Kppst
post
2KT
2K Kpost
Kyost
Figure 4: The @ can be used to enable s * 1 and c; + c, contigurations on SLL. The flexibility of the @ allows for operations resulting in a block with similar structure as the original ResNet block.
SLL layer for convolutions, proposed in (Araujo et al. 2023 is a I-Lipschitz layer defined as:
y = x 2K" * (o(K x b))
Note that in the original paper, the equation is noted with product of two matrices WT- 1, for convolutions represents toeplitz matrix, i.e. -
22

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
SLL layer does natively support neither strides nor changes in the channel size. We propose the to derive block, based SLL., that supports stride and G; + Co. and can replace the strided convolutions of the residual branch in architectures like ResNet.
A natural first step is to append a strided convolution after a SLL block. This layer, comUKpon o SLL, can then be fused in the SLL block thanks to Proposition G.2
K post *s (x 2K" (a(K * x b]))
= KK post *a 2(K post @ K") *s (o(K x
This allows to build a block based on SLL and that supports stride and channel changes. However, this creates an asymmetry between the convolution before the activation and the one after the activation (that has a larger kernel size).
We propose also to add second convolution before the SLL block, cootU SLL o conV allowing better control over the kernel size of each convolution:
y K post *s Kpre * x
2(K post @ K") *s (o(K Kpre * x. + b)))
=KK post @ pre)) Kg x
2 poost & K * (a((K & Kyre) * +
The proposed block is still a 1-Lipschitz layer (as a composition of I-Lipschitz and orthogonal layers), and support efficiently strides and changes kernel sizes. visual description is provided in Fig- 4 This approach more efficient than the explicit construction that uses 3 distinct convolutions, as kernels are merged once per batch, and intermediate activations of extra convolutions do not need to be stored backward. Typically, when K, Kpre and K post 2 x 2 convolutions, this results in residual block with two 3 x 3 convolutions in one branch and single 4 4 convolution (with stride 2) in the second. This is very similar to transition blocks found in typical residual networks.
E.3. Improving Sandwich Layers
Introduced by (Wang & Manchester 2023), this approach aims to construct I-Lipschitz network globally rather than constraining each layer independently. In practice, this can be done either by (i) adding constraints between layers (ii) creating layers that incorporate a non- non-lincarity internally (a.k.a. sandwich layers). However, sandwich layers require an orthogonal matrix at their core. For convolutional layers, this achieved by performing the orthogonalization of the layer in the Fourier domain, as described the method from (Trockman & Kolter 202I) and shown in their Algorithm
Algorithm 4 Sandwich convolutional layer (from WWng & Manchester 2023
Require: Iin E RPxxxa P ((x+x))xxxxxe e R
1: him < hhi))
2: V < d ), [ B + CayIey(FFT(P))
3: h t- v V2 1, i, ihinlliii
4: FFF(
(A) +))
5: Rounl (. 8, t- V2A ; é. 1h(.
6: hou FFT (hrutt
We can leverage AOC to construct the kernel of an orthogonal convolution, replacing the expensive operation performed in the Fourier domain. Thus, construct kernels, A and B, with appropriate constraints between the two and apply the rescaling and non-lincarity directly in pixel space:
ham T2A * Vo (V2V-1B+ him +
23

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
The use of the Fourier transform is costly for two reasons: first, it necessitates computation with complex values; and second, the cost of the operation depends the input size, which can be prohibitive in large-scale settings with 224 224 images. Consequently, our approach can make such layer more scalable.
E.4. Extending Applicability to other methods.
Beyond the previously discussed approaches that show meaningful opportunities for improvement, method can enhance wide range of orthogonal convolutional layers. Specifically, we can incorporate our framework into any alternative orthogonal layers, enabling native support for strides in those layers. Furthermore, our approach can unlock features such as grouped convolutions, transposed convolutions, and dilations, broadening its utility and adaptability.
F. About the incomplete parametrization of BCOP and SC-fac
As mentioned earlier, both BCOP and SC-Fac exhibit incomplete parametrization. BCOP has incomplete parametriza- tion for 2D convolutions, while SC-Fac offers complete parametrization but only for separable convolutions.
F.1. Understanding the Limitations of BCOP
The limitations of BCOP parametrization have significant implications for its in practical applications. Below, provide detailed discussion of the known limitations:
The authors presented a counterexample involving a 2 x convolution that is orthogonal but cannot be parametrized by BCOP. This highlights the incomplete nature of BCOP for parametrizing certain convolutional layers.
However, this counterexample can be parametrized by a 3 BCOP convolution, which suggests that increasing the kernel size can potentially address the issue of incomplete parametrization.
This does not imply that all 2 x 2 orthogonal convolutions can be parametrized using 3 BCOP convolutions, but it provides useful starting point. It indicates that while BCOP may struggle with certain cases smaller kernel sizes, increasing the kernel size could offer a pathway to improve coverage.
This problem is more complex than initially expected: the parametrization space of BCOP is disconnected. simple terms, the disconnected nature of the parametrization space means that certain transformations cannot be continuously reached from others within the same parametrization framework. Nevertheless, BCOP convolution with e channels can have connected component that represents all convolutions with c/2 channels. This property indicates that, although BCOP may not cover the entire space of orthogonal convolutions, it has subsets that can be effectively utilized for lower-dimensions problems.
Another noteworthy point is that the disconnected nature of the parametrization space could limit the efficiency of opti- mization algorithms that rely on continuous transformations during training. In practice, this means that certain optimal configurations may be reachable through gradient-based methods, which could hinder the overall performance of models employing BCOP convolutions.
The issue of incomplete parametrization can be mitigated by increasing the number of channels and kemee size, highlighting the need for a scalable approach to address the challenge effectively. Increasing the number of channels provides more degrees of freedom, which may help cover more of the orthogonal convolution space while increasing the kernel size expands the range of spatial features that can represented.
Research on the complete parametrization of orthogonal convolutions with controlled kernel sizes remains an open question, AOC could benefit from further improvements in this area.
G. Proofs
G.1. Proof of the @ property:
Although already shown previous papers (Li al. 2019). (iioo et al. 2018), we provide the proof in the ID case to help the reader understand the mechanism of the @ operator. Given a vector x E R Xw and two kernels E I X Xka and
Be E I X6 Xkg. We suppose that A is zero-padded, i.e., A if < 0 or i 2 KA-
24

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Proof.
y A J., such as,
Vej = Σ 4-11k-1
Σ
A
n=0 y'=0
2 B y (B A) 2, such as,
kn 11
2m,1
B Be.ey
-00
K=0
Gint
Kg-11
Ge -
B
y'=0
Cint kn-1
B AKk
P=
B Aah---a
(with -' +'
P=0
ka thn-1
A) Pkk
(direct formulation of (B A) * x)
with thus
Gine 1 kB -1
(B A) m.n,t
m,,nd
B
B...stAA...t Acm.ir
c=0
p=0
G.2. Recall of other properties
Two kernels A and B are said compatible for the B @ A operation when the number of input channels of the second convolution B matches the number of output channels of the first convolution. This condition is denoted as A B.
We present here several properties of the Block-convolution operator @:
Proposition G.1 (Associativityy. The @ operation is associative (given compatible kernels A A B and B X C):
A B 2 C*) (
Proposition G.2 (Bi-linearity). Given two convolutions A and B with the same channel sizes, third convolution C compatible with A and B (A X C. x C), and two scalars λ1 Ag R:
(AAA+AB)) A + C BBOC
Proposition G.3 (Non-Commutativity)) Even when A K B and B A hold, Block-comvolution is not commutative, as convolution composition is generally not commutative:
AB + BA - A
G.3. Proof of the construction c x с x 1 x orthogonal convolution
This proof was already presented in (L et al. 2019), but we include it here for the sake of completeness. Given a symmetric orthogonal projectors N E TRexe such as:
N 2 N and (T-N) = N
=I-
25

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Considering N and / N as Rexeexxx convolution kernels, we can build a convolution kernel P E |Rexexxx2 by:
P stack [N, I - NJ. axis -1)
For readability, we will write P = [N, 7 - Nj as a compact notation for the stacked kernels. We will prove that such a kernel P defines an orthogonal convolution. Since this convolution has no stride = 1, as stated in Section 2.2 this
equivalent
P = P + P
Proof. We can compute explicitly the resulting kernel for P Pd:
P + PT_
NN, I N @ -)", N
[ (I N)",NN + (1- NI
[N NN,,
[N -
2N N2, N N - N,N 2N 2N2 ,N N
1,0
The third line is the matrix application of the @ with two 2 kernels (Eq. application of the symmetric projector property.
The following lines are based on the trivial
Construction of symmetric projectors. Following the construction described in (Li et al. 2019) symmetric projectors N Rexe can be constructed based column-orthogona matrix No
R
given No E Rex such that No No = I
The matrices N = No and I - N are a symmetric projectors.
Proof. This proof was already presented in
Li et al. 2019), but we include it here for the sake of completeness.
N (N.NN)(NNNN))
No(NT No)
No.N
= NT
(1- N)2 -
- 2NoN2 + (NONN3)(NON33)
-NoN2
= =1 N N)T
26

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
G.4. RKO kernel with stride k builds orthogonal convolution
The RKO method considers convolution conv s) with a kernel K [Roxxxxxkk built by reshaping an orthogonal matrix K' E IR Kcq.k? The matrix K' can be obtained for instance by the Björck and Bowic orthogonalization scheme Id for column).
(Björck & Bowie 1971 and verifies K' K' Id for row orthogonality (resp. K K'
In the general case, the resulting convolution is orthogonal (Achour al. 2022. We prove that in the special case where the kernel and the stride are equal, the convæ(.. k) with stride = k is orthogonal.
Proof. Vx Roxxxx, where suppose that h, w multiple of have:
conv (I, k)h.a
Σ
K Feikk-
c=0
d'=0j'=0
c,k²
Σ
(K't)
where & E [Rckk 2. is defined by:
10 1.jh
Fo (1) 10
Since there is overlap between the receptive field of each output, Px. where the matrix P is permutation (similar an invertible downsampling with factor k), which is by definition orthogonal.
In the case of row orthogonality for K", we have:
conv (ConTrrccoaa x (I, stride k))
K)"(K'))*x
K'PPTK" KT
(P orthogonal)
K'K x
KK' is orthogonal)
G.S. AOC convolutions are orthogonal
The construction of our method consists in composing a BCOP kernel K BBOP E xoxxxxx-exx- followed by an RKO kernel KRKO E Xxxaxx As we already proved that each kernel is orthogonal, we know that
КBCOP KecopKEcor when e 2 c KT K KBcOr I when S
and that
(S, KRKO)(SS, KKKO)) = I when c c+
(8, KRKO)" (8, KRKO)= I when c 52 < co
27

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
We prove that with a correct choice of the internal dimension c, the strided AOC convolution with kernel K Aoc KRKO @ BCCOP is orthogonal.
Proof. As (the intermediate number of channels) is free parameter demonstrate that construction is orthogonal when the convolutions are either both row orthogonal, or both column orthogonal (Proposition 2.3) i.e when:
G 2 C and c 2 Co
(both row orthogonal)
s
or C < and
(both column orthogonal)
In the first case, when 2 o The resulting convolution (S, KRKO KBCор) is orthogonal for any c such as 3/ S
(S, Knko (Scor)(S. Knko Kncor)* = =(S, (RkoK)))BBCOF BCoPp(S KRKO)"
(KBCop is row orthogonal since
c G)
(RKK KRKO))
(S, KRKO row orthogonal since
Co
5c)
The maximum possible value for is c = C₁. The second case when e₁ S c & z can be proven the same way where the best choice is
co
G.6. Transposed orthogonal convolutions
The transposition row (resp. column) orthogonal convolution a column (resp. row) orthogonal. The proof direct by combining Definition 2.2 and Eq. (10).
Proof. Given row orthogonal convolution defined by S,K. ie such that (S,K))(,,K)* I. The transposed convolution is defined (S,AC)
We have ((S,)))""" = (S,K) = I
The transposed convolution is column orthogonal.
The same proof can be applied for column orthogonal convolutions.
G.7. Grouped orthogonal convolutions
A grouped convolution composed of g kernels (Ki), is orthogonal if and only if each individual convolution of kernel K; is orthogonal. We will suppose that the convolutions that c, S and without stride s = 1. The proof is equivalent for c; S co and stride 1.
Proof. The proof uses the fact that the Toeplitz matrix a grouped convolution is block diagonal.
K
0
0
K1
0
K
Suppose that each kernel IC; is row orthogonal (row is due the fact that Co S 03
6o
K.K. =I i..
8
28

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Ku
KT
K
0
K
0
KKT*
X
K
0
KuK
0
KIKT
0
0
K -
I
0
I
0
0
I
= I
Thus IC is row orthogonal.
Conversely, suppose thet K. is row orthogonal. The condition KXCT = I implies in the matrix multiplication above that Vi E [0,g K,K II
G.8. Dilated orthogonal convolutions
The proof of equivalence between orthogonality of dilated convolution and orthogonality of the same convolution without dilation given in (Su et al. 2022) using the equivalence in the spectral domain. Here we explicit the equivalence of convolution the spatial domain.
Given convolution of kernel Ka with a dilation d, and an input x E xxxx We have:
1-
coneR (x, dil d)n,ss
Σ
c=0 P=0j'=0
(Kaat)
Let define d2 reshaped inputs (X m E Rax vectorized vectors X Xm.a.
Where: X = Temmtiedntted We also define the
We thus write using ri mod d.rj j mod d. qi = [
k-1k-1 k-1 k-1
conux (2, dil d)).s.s
Σ
Kheai Xriri
e=0l
F=0+==0
conuk (Xrirr) dil 1)iggi
(XXrisr)) M
Thus the convolution with dilation is equivalent to the application of the convolution without dilation applied on a permutation of the input.
G.9. Conditions under which stride can be directly applied on BCOP
When o; > C. stride S, can be directly applied on top the BCOP kernel KBCOP (row orthogonal) without the need to construct the RKO kernel handle striding (as explained Proposition 2.5
29

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Proof. We first prove that S, is also row orthogonal: S, S.S² I. We can leverage the proof that RKO convolution is orthogonal when k As the identity be built with RKO kernel. Then (Definition 2.2 given that < ) This proves that S S = I.
show that (S.I)(S,I)² I
As S. and -всор are both row orthogonal, we can apply Proposition 2.3 to show that the strided convolution S,K.COP is also row orthogonal. The direct strided version of the convolution using the BCOP kernel is thus also row orthogonal. Li
G.10. Conditions of invertibility of AOC layers
As presented in Appendix A the invertibility of layers has a direct application in Normalizing Flows. The following recalls that strictly orthogonal convolutions are inherently invertible via the transposed convolution. Given the Eqs. and we have the equivalence:
y conva (z. stride = + y = S,KT
If the convolution is strictly orthogonal -i.e. the matrix S,K. is square- then Definition 2.2 implies that:
(S,KC)- = (S,K)²
Thus, the inverse of the convolution layer is the transposed convolution:
= (S,K)"' = x = ConvTranspose, x (y, stride = s).
For strided convolutions, strict orthogonality implies that Co c.s². This allows construct Normalizing Flows that reduce the spatial input dimensions by increasing the number of channels. Note that, this is not equivalent to applying an InvertibleDoonnSmmping operation before the convolution since the strided convolution kernel requires 8² fewer parameters. Note that AOC allow to extend invertibilty to grouped and/or dilated convolutions.
H. Architecture and training details
Layer Type
Output Shape
Config
Depthwise Convolution
GroupSort
Pointwise Convolution
Input
[3, 32, 32]
ha.h.w)
(2c, hoc.h, w)
(2c. h,
fc.h.wi
AOC
[256, 16, 16]
stride=2
Block (Repeated Residuals)
Residual Depthwise Block x 16
[256, 16, 16]
3x3 kernel
AvgPool2d
[256]
We can construct complex blocks. These blocks can roduce the number of parameters of our models, thanks to the flexibility of AOC. Lipschitz continuity is guaranteed when E [0. 1].
MaxMin
[256]
Fully Connected Layer
[10]
Figure 5: Architecture used for CIFAR-10 accurate setting. This architecture makes use of its flexibility to allow performance with a limited parameter count. Left, table of the global network architecture. Right, detail of he residual depthwise block.
All hyperparameters of the experiments are detailed in Table These parameters were not heavily tuned: the batch size set to large value, but limited it to 1024 to avoid training for too many epochs. This is due to the fact that robust networks seem to benefit more from more training steps rather than larger batch sizes. Once the batch size was set, the learning rate was tuned the following way: by training multiple times for 500 steps, the learning was increased until the accuracy at the end of these 500 steps was maximized, and the final learning rate was set to the largest values before the metrics plateaus.
For robust training, we must control three elements: accuracy, robustness, and generalization. As noted by (Prach Lampert) 2024 Béthune al. 2022). usual scaling laws do not embrace the fact achieving accuracy and robustness simultaneously comes the price of generalization. Which can be regained by using larger networks, more data augmentation, and longer train times. To control this phenomenon, we can tune the following 3 elements:
Loss parameters: Increasing the margin in the loss function helps improve training robustness, but reduces training
30

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Hyperparameter
CIFAR-10 Acc.
CIFAR-10 Rob.
ImageNet Acc.
ImageNet Rob.
Prach Lampert
2022
Prach & Lampert 2022)
Loss function
Cosine similarity
Cosine similarity
L552.
0.125)
1552,
0.125)
Optimizer
ScheduleFree Defazio et al.
2024
Learning rate
5 x 10
x 10
1 X 10
1 10
Batch size
1024
1024
512
512
Epochs
150
3000
Randaugment params
m=6, n=2
m=6, n=1
m=7, n=2
None scale 0.08
Random crop params
scale 0.25
scale = 0.5
scale 0.5
hardware
RTX 3080 x
RTX 4090 x
RTX 4090 x
RTX 4090 2
Table 4: Training Hy Hyperparameters for the Four 1-Lipschitz Networks. "Ace." refers to the high-accuracy setting, and "Rob." refers to the robust setting.
accuracy.
Model size: Increasing the model size generally improves training accuracy.
Data augmentation: Increasing data augmentation reduces training accuracy but can improve validation accuracy, especially when training accuracy is greater than validation accuracy.
The tuning process then works following these steps:
1. start with given architecture and a low margin 0
2. increase data augmentation until train accuracy goes below 100%. The model reached its maximum generalization for this margin.
3. increase the margin, increase the model size and number of epochs until reaches 100% training accuracy.
4. repeat steps 2. and until the desired robustness is achieved. The target margin is m = 3/2 V to match the parameters used by Araujo et 2023). In practical contexts, m should be set to m ev radius, I. the model's Lipschitz constant and the scaling factor applied the data (for instance when standard rescaling is performed) the /2 factor comes from the equation in Section 3.1
ab where the targeted robustness
This explains the drastic difference between standard and robust networks in terms of model sizes and training times.
Overview of the architectures used All the architectures used in this paper aims illustrate that despite its under- parametrization, AOC allows the construction of expressive architectures. All architectures only use AOC convolutions and standard blocks to ensure that performance can be attributed to the method. As underline in (Anil et al. 2019 it is the combination of orthogonal layer and MaxMin activations that permits the construction of networks with a tight estimation of their Lipschitz constant. We then use MaxMin activation in all of our architectures. The reader interested building I-Lipschitz networks that use ReLU activations can refer to the work (Araujo et al. 2023) and (Wang Manchester 2023
We describe interactions between AOC and these constructions in Appendix
Some of our architectures use skip connections, since those do construct 1-Lipschitz blocks, add a learnalee factor correctly ensure the I-Lipschitzness of the whole network. Given f1 a Lipschitz function and fo Lipschitz function, then f - fi + S2 is l + l2 Lipschitz. Then the function:
Q1 + f(22)) y
[a + |02
Lipschitz. This is also true when summing (z)(2) instead of f(azz), but the proposed approach allows to control the gradient flowing through f. Finally we set 01 to ensure better gradient propagation deep architectures.
31

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Output Shape
Layer Type
Config
Feature Extractor
3 x AOC
[128, 32, 32]
3x3 kernel
AOC
[256, 16, 16]
stride=2
3 AOC
[256, 16, 16]
3x3 kernel
AOC
[512, 8, 8]
stride=2
3 AOC
[512, 8, 8]
3x3 kernel
AOC
[1024, 4, 4]
stride=2
4 AOC
[1024, 4, 4]
Flatten
[8192]
Fully Connected
4 OrthogonalDense
[1024]
OrthogonalDense
[10]
Table 5: Architecture of the CIFAR-10 robust network. unlike other networks, this network has an architecture designed
to be similar to the original network from (Li et al. (2019) (with increased width and depth). It follows the original design choices (using circular padding and the absence of global pooling).
CIFAR-10 (Krizhevsky et al., 2009) The CIFAR-10 experiments used three distinct networks, the network tailored for accuracy is detailed in Fig. in this setting zero padding is used, with this padding, the layer is 1-Lipschitz and quasi-orthogonal (orthogonal everywhere except for the images border, see (Delattre et al. 2023 2024) for details). This architecture features a bloe inspired by (Trockman & Kolter 2024) which consists of a depthwise convolution that doubles the number of channels, followed by a MaxMin activation function (Anil et al., 2019) to enhance non-linearity, and a pointwise convolution that reduces the number channels. These layers are encapsulated within a skip connection featuring a learnable factor to ensure Lipschitz constant of 1. On the other hand, the robust network has an architecture designed to be as similar as possible to the networks used by (Li et al., 2019) which allows to show the impact of scale the results. The architecture is detailed in Table 5 Finally, the network of the AOC robust*; reuses the training recipe of (Hu et al., 2023) with the original convolutions replaced by AOC convolutions (which include downsampling convolutions). The residual connections were removed, and a constant value of 1.15 replaced the scalar factors. This resulted in a network with a tighter Lipschitz constant evaluation, which resulted in non-optimal training with original loss parameters (the training led to networks that were not accurate enough). Hence, the loss parameters were divided by 10 to make the network more accurate.
We tested the robust architecture in an accurate setting and vice versa, observed that the robust architecture under- performing in the accurate setting, plateauing at 85% of validation accuracy and 0% of certified robust accuracy. Similarly, the accurate architecture was underperforming in terms of robustness with only 47% of certified robust accuracy and 71 % of validation accuracy,
Imagenet-1K (Deng et al. 2009) The ImageNet- 1K experiment follows the hyperparameter configuration detailed in Table 4 The two architectures utilized in this study exhibit a high degree of similarity, with their structural differences illustrated Figure Table 6 Both architectures incorporate the fundamental block described in Section Fig. 5a
The primary distinction between the accurate and robust settings lies in the architectural modifications aimed at enhancing robustness. Specifically, the robust architecture employs L2- .2-normalized pooling (Boureau et al.) 2010) and cireular padding, both of which contribute to improved resilience against adversarial perturbations. Furthermore, inspired by (Trockman &
Kolter 2024), the convolutional blocks in the robust model utilize larger kernel sizes to capture broader spatial context.
H.1. Scalability experiment
Experiments were conducted on minimally modified ResNet-34 architecture, chosen for its compatibility with various orthogonal layers and its status as a standard benchmark for ImageNet training. The transition blocks were replaced by a single, strided convolution to maintain simplicity and ensure compatibility with existing orthogonal layers. For each method, we measured the average training and testing times over 100 batches and recorded peak memory consumption. Starting with a batch size of 1 128, we doubled the batch size incrementally until encountering an out-of-ment of-mmooryy error. Each method's
32

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Output
Layer Type
Config
Shape
Input
[224, 224]
Convolution Layer I
[112, 112]
5x5 kernel
Activation Layer
[112. 112]
MaxMin
Block
Residual Depthwise Block x 3
[56, 56]
5x5 kernel
Convolution Layer
[28, 28]
3x3 kernel
Block
Residual Depthwise Block x 3
[28, 28]
5x5 kernel
Convolution Layer
[14, 14]
3x3 kernel
Block 3
Residual Depthwise Block x 3
[14, 14]
5x5 kernel
Convolution Layer
[7, 7]
3x3 kernel
Block
Residual Depthwise Block x 3
[7, 7]
5x5 kernel
L2 Pooling
[1, 1]
3x3 kernel
Flatten
[2048]
Fully Connected Layer
[1000]
Table 6: Summary of our architecture used on Imagenet-1K.
performance was compared to a standard convolution baseline, with results reported as overhead percentages.
To ensure a fair comparison, the hyperparameters of SOC and Cayley were set to their default values. We adjusted the number of Björck iterations to the same values for BCOP and AOC. While originally set to 20 iterations, our unit testing scheme (see Appendix(D DD shows that 12 iterations are sufficient to ensure stable rank (Sanyal et al. (020) of 99.9% of the full rank. Finally, standard Conv2D is used with circular padding to evaluate the overhead induced by our parametrization rather than the overhead induced by the padding.
We did not include non-orthogonal methods such as AOL, SLL, CPL and RKO (Prach et al. 20024] Araujo et al., 2023 Meunier et al. 2022 Serrurier al. 202T) as those are expected to be faster than AOC that add a stronger constraint. The continuum between orthogonal and non-orthogonal methods could be explored by reducing the number of Björck and Bowie iterations. However, the correct way to explore this should be with experiment that grasp the main aspects of those methods: speed (time per batch), trainability (number of batches to reach certain accuracy) and performance (final accuracy/robustness). This is beyond the scope of this work, and the work of (Prach et al. 2024) is relevant track to explore this question.
I. Reproducing the results from BCOP paper
As mentioned earlier, AOC is built top of components like BCOP and RKO. Hence, any accuracy gain must come from the fact that our implementation allows larger networks and more training steps within the same compute budget. To illustrate this, we reproduced the baseline results from (Li et al.) 2019) and switched the implementation to ours. Results are shown in [ We can observe notable difference in performance between the original implementation and ours. This is due to the difference in the parametrization of strided convolutions: the original paper uses invertible downsampling to emulate striding followed by a standard convolution whose number input channels is multiplied by s², such convolution has a s² x more parameters than the proposed AOC strided convolution. This is accentuated by the specific small architecture used in BCOP paper (and reproduced in this experiment) which has 84% of the convolutional layers parameters that are located in strided convolutions.Alss. invertible down-sampling has 2 2 receptive field, which increases the global convolution' receptive field. However, when we remove the optimization depicted in Fig. Tig.2cJan [2d only resort to the parametrization described in Fig. [ the increase in the number of parameters results in improved results close to the results of the original paper. This observation is non-trivial since this modification not equivalent to the original implementation: instead of parametrizing a
C, x 4c x & x AOC parameterized one max(c;, (3) x C x s + k - s + and one c, x max(C;, ()) x s x
kernels which are much smaller.
33

---

An Adaptive Orthogonal Convolution Scheme for Efficient and Flexible CNN Architectures
Provable Accuracy
Acc- uracy
Models
36
205
BCOP Small net (original seeting)
72.2
58.26
AOC Small net (all optimizations)
62.3
49.18
AOC Small net (opt in Fig. 2 removed)
71.8
58.25
AOC Large net (all optimizations)
74.0
64.33
Table 7: Mitigating AOC limitations in small scale setting: as AOC uses less parameters for strided convolutions, this can impact its expressive power in small scale setting. However, by removing the optimization in Fig. 2c this increase the number parameters enough to correct this issue. Results from Table Saeeeeadde adddd for reference.
We recall that all the results of this paper were obtained with the optimization Fig. 2c version in the same context in Table and found, for batch size of 512, slowdown of 1.21 x in train time (instead of 1.13x) and notable increase in train memory consumption.
We evaluated the unoptimized
Finally, it is worth noting that the optimization depicted in Fig. 2c not affect the expressive power if we were able to parameterize the complete set of orthogonal convolutions.
34


Reviews:
[{"review_id": "d9ypPPVGxv", "reviewer": "Reviewer_yVT2", "summary": "This paper purposes a orthogonal CNN structure. Orthogonal convolution has been shown success in BCOP and RKO. Utilizing the property of the product of orthogonal matrices are still orthogonal (prop 2.3), this paper invents AOC in Eq. 8, which is the product of RKO and BCOP. A parallel computing technique (fig 2) is also proposed to significantly increase the performance (Tab 3). Comparing to existing works, this algorithm is also easily applied to striding, dilating, etc. I am not very familiar with the area so please point out when anything I say is incorrect.\n\n1. It seems to me the main method AOC is to simply attach a RKO layer to a BCOP layer. Although this idea seems straight forward, it has good performance shown in Tab 2. Do you have an intuition why it is so good?\n\n2. On CIfar 10, why the accuracies shown in Tab. 2 are so low? I imagine modern CNNs with several million parameters will easily reach >90% accuracy.\n\n3. Why AOC provable accuracy is 00.0 in Tab. 2? Is that a typo?\n\n4. Tiny suggestion: do you think it would be better if containing the number of parameters in Table 3 would be better? It seems although AOC has less number of parameters comparing to resnet (53.1M vs 86.0 M as shown in Tab. 2 for IN-1K), it requires longer time during inference in Tab. 3. Am I missing something?\n\nCurrently I would keep my rating at weak accept and I will keep trying to better understand this work during the discussion period. Looking forward to the reply from the authors!", "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": "We want to thank the reviewer for his review. We will provide additional information that we hope you to find relevant.\n\n**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.\n\n**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).\n\n**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.\n\nWe hope that these points will convince you of the paper's potential.", "claims_and_evidence": "-", "methods_and_evaluation_criteria": "-", "theoretical_claims": "-", "experimental_designs_or_analyses": "-", "relation_to_broader_scientific_literature": "-", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "-", "other_comments_or_suggestions": "-", "questions_for_authors": "-", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L1OfSibkhe", "reviewer": "Reviewer_dhMd", "summary": "This paper explores research on orthogonal convolutional layers and introduces AOC, a scalable method for constructing orthogonal convolutions. The authors provide a detailed introduction and implementation of their methodology, including the construction of strided, transposed, grouped, and dilated orthogonal convolutions using AOC. Experimental results demonstrate the effectiveness of the proposed framework.\n\n**update after rebuttal**\n\nThank you for your rebuttal. I will keep my score unchanged and remain positive about this paper.", "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": "We sincerely appreciate your thoughtful evaluation and the interest you've shown in our paper, particularly regarding its practical contributions.\n\nIn 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).\n\nBesides, 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).      \n\nWe hope this further clarifies the depth and originality of our contributions and reinforces your positive view of the paper’s potential impact.", "claims_and_evidence": "Please refer to Strengths And Weaknesses.", "methods_and_evaluation_criteria": "Please refer to Strengths And Weaknesses.", "theoretical_claims": "Please refer to Strengths And Weaknesses.", "experimental_designs_or_analyses": "Please refer to Strengths And Weaknesses.", "relation_to_broader_scientific_literature": "Please refer to Strengths And Weaknesses.", "essential_references_not_discussed": "Please refer to Strengths And Weaknesses.", "other_strengths_and_weaknesses": "**Strength**\n1. The research on Adaptive Orthogonal Convolution is both intriguing and highly practical. It makes a significant contribution to neural network architecture development and holds great potential for the research community.\n2. The paper is well-structured and easy to follow.\n3. The implementation of AOC is thorough, and the experimental results effectively demonstrate the significance of the proposed method.\n\n**Weakness**\n1. I guess there may be some criticisms regarding novelty (possibly?), as the paper leans more toward an implementation-oriented approach from my perspective. But for me, it's basically good enough. And it does provide additional information/knowledge to me. If the authors could offer a more in-depth and insightful analysis to meet the taste of academic community, it would further enhance the paper’s impact.", "other_comments_or_suggestions": "Please refer to Strengths And Weaknesses.", "questions_for_authors": "Please refer to Strengths And Weaknesses.", "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": "4BUOQ130Vw", "reviewer": "Reviewer_HsiT", "summary": "The paper proposed a new method to design scalable and versatile orthogonal convolutional layers. \n\nThis layer allows scaling further architecture composed of orthogonal layers; indeed, previous orthogonal layers lack common features of regular convolutional layers (strides, dilations, group convolutions, etc). \n\nThe so-called AOC layer encompasses those new features, theoretical demonstrations are provided to support those claims. Also, AOC relies on a faster implementation of block convolution, which makes the computational overhead close to a vanilla convolutional layer.\n\nThe utility of AOC layers is demonstrated on certified adversarial robustness tasks and computational time comparisons across various methods.", "questions": "", "limitations": "", "rating": 2, "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": "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.\n\nAbout the experiments:\n------------------------------\n\n- 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.\n- 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.\n- 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).\n- 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.\n\nAbout novelty:\n-------------------\n\nWe state clearly the novelty and difference with BCOP in Table 1. The bullet points in l82-l102 list the properties AOC achieves **simultaneously**.\n\nOur contributions are 3 fold:\n1. 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.\n2. 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)\n3. 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)\n\nAbout the writing:\n----------------------\n\n - Q0.a: Lipschitz/orthogonal constraints: We agree with suggestion to move the L380 in the introduction  and will use it to clarify the point.\n - 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.\n - 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.\n - l27: (Miyato et al., 2018) will be moved to l26.\n - 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.\n - L87: We agree that “mitigating vanishing gradient” is a more appropriate title for this paragraph. Thanks for the suggestion.\n - 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).\n\nQuestions:\n---------------\n\nQ1 [Batchnorm]: \nYes, 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.\n\nQ3 [invertible convolution layer]: In our framework, this demonstration becomes easy. Given\n\n$ 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)}$ \n\nIf the convolution is orthogonal (not row/column orthogonal), we have\n\n$(\\mathcal{S}_s\\mathcal{K})^{-1} = (\\mathcal{S}_s\\mathcal{K})^T \\quad \\text{(Def.2.2)}$ and then,\n\n$ \\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)}$", "claims_and_evidence": "All the claims in the paper are backed by clear and convincing evidence.", "methods_and_evaluation_criteria": "In the abstract, it is claimed that orthogonal convolutional layers are important blocks for adversarial robustness, normalizing flows, GANs, and Lipschitz-constrained models. \nHowever, in the experiments, only adversarial robustness tasks are considered. More diverse applications are welcome to demonstrate the use of  AOC and orthogonal property.", "theoretical_claims": "I checked the correctness of all proofs, and they seem correct.", "experimental_designs_or_analyses": "Experimental designs are valid for the adversarial robustness section, but more experience on other tasks is required (with application in normalizing flows and GANs as promised in the introduction or other tasks for orthogonal architecture).", "relation_to_broader_scientific_literature": "Certified robustness with Lispchitz networks still lags behind the empirical robustness obtained with the adversarial training method or randomized smoothing. Thus, work pushing boundaries in this direction is important.", "essential_references_not_discussed": "All references are correct, but maybe adding a reference on (Salman et al., 2019), which cast randomized smoothing network as Lipschitz network.", "other_strengths_and_weaknesses": "# Strengths\n\n## Reduced computational overhead\n\nThe implementation of AOC has been well optimized.\n\n## Training stability\n\nThe proposed method seems to achieve competitive accuracy on ImageNet (68.2%) without any batch norm.\n\n## Code base\nThe authors provided a code base that is clear and complete.\n\n\n# Weakness\n\n## Introduction\n\nl.45:  \"with 1-Lipschitz networks being a prime candidate (Anil et al., 2019) – an approach that requires the use of orthogonal layers\".\n$1$-Lipschitz network can be designed through the product upper bound and Lipschitz layers one particular case of 1-Lipschitz layer is orthogonal layers **but it is not the only solution** (Meunier et al.; 2022, Araujo et al.2023; Wang et al., 2023; Hu et al., 2023).\n\nl.27: \"Wasserstein GANs (WGANs)  [...] orthogonality in both the discriminator and generator (Miyato et al., 2018; [...]\"\nMaybe I did not understand well, but Miyato et al., 2018 proposed a spectral normalization technique and not orthogonalization.\nAlso, the Lipschitz constraint is only enforced on the discriminator in WGANs.\n\nl.38: \"Efficient orthogonalization of these structured matrices has theoretical importance, affecting generalization (Bethune et al., 2022)\"\nI don't see the **direct link** with efficient orthogonalization for layer and the work of Bethune et al., 2022.\nThe lipschitz constant of the neural network divided by the margin has been linked to reducing the generalization gap (Bartlett et al., 2017), but those considerations are independent of the implementation of Lipschitz layers and, in particular, orthogonal ones.\n\nl.87: \"Relaxed orthogonality approaches. In some cases, strict\northogonality is relaxed to mitigate vanishing gradients,\navoiding the computational demands of full orthogonaliza-\ntion (Prach & Lampert, 2022; Meunier et al., 2022; Araujo\net al., 2023)\"  here the approaches of (Meunier et al., 2022; Araujo\net al., 2023) do not rely on orthogonality and relaxed orthogonality. \n\nOverall, normalizing flows, GANs are much discussed in the introduction but do not appear later in the paper, and their mentioning in the Appendix is too superficial and lacks contribution to motivate AOC.\n\nAlso, the introduction feels a bit like a related work section, particularly the part on orthogonal convolutions, there is a back and forth between intro - related work - intro.\n\n## Section 2\n\nl.169: \"For the second kernel, RKO\n(Serrurier et al., 2021) is the only viable option, as all other\nmethods depend on stride emulation.\" RKO has been introduced in prior work by (Li et al., 2019), also redundant with l.219.\n\nl.171 : \"For standard orthogonal convolutions with a fixed kernel size, we rely on three\nmain works (Xiao et al., 2018), (Li et al., 2019), and (Su\net al., 2022).\" Redundant with  l.133.\n\nProp. 2.4 : It is row /column orthogonal as there is stride (not $\\ell_2$norm preserving) and not orthogonal $Q^\\top Q = Q Q^\\top = I$ ($\\ell_2$norm preserving).\n\n\n\n\n## Novelty\n\nIt should be stated clearly that the proposed AOC is an incremental update of BCOP and RKO (Li et al., 2019).\nThe contributions related to **Orthogonal**, **Explicit** are already developed by (Li et al., 2019) and cannot be claimed.\n\nOverall, the paper is a well-written review of orthogonal convolutional layers.\nHowever, I don't think combining two existing methods (RKO and BCOP) is a sufficiently novel contribution.\n\n## Experiments\n\n1) in table 2. Why not put ResNet18, which also has 0 % provable accuracy and compare with AOC ?\n\n\nl.380 : \"The overall Lipschitz constant of a sequence of layers is typically\nestimated as the product of the individual layer constants;\nhowever, this bound is often loose, and computing the ex-\nact constant is NP-hard (Virmaux & Scaman, 2018)\" in introduction.\n\nl.365: for certificate equation give reference.\n\n# References\n\nBartlett, P. L., Foster, D. J., & Telgarsky, M. J. (2017). Spectrally-normalized margin bounds for neural networks. Advances in Neural Information Processing Systems (NeurIPS).", "other_comments_or_suggestions": "l.20: a dot is missing \"finvertible residual networks (Behrmann et al., 2019) Additionally\"\n\nTable 1: BCOP (Li et al., 2019) not (Singal & Feizi, 2021)\n\nl.1465 : there is a dot alone.", "questions_for_authors": "## Questions\n\n### Q0)   \nIn the introduction, there is confusion between the Lipschitz constraint and the orthogonal constraint. Please modify it to better reflect that orthgonality is a subset of the Lipschitz constraint.\nAlso, in section 2, there is confusion between row/column orthogonal and orthogonal. \n\n### Q1) \nCan you confirm that you do not use any batch norm to obtain accuracy on ImageNet with AOC architecture (68.2%)? I think it should be discussed more in the paper as it is a good contribution. A related work on optimization without batch norm, gradient clipping could be a good add to the paper.\n\n### Q2) \nThe proposed method unlocks scalability with the AOC layer. Can you try to scale the capacity of models beyond what has been proposed yet for orthogonal CNNs (even Lipschitz CNNs)? In terms of depth and width. \nThe scaling law of robustness states that Lipschitz networks require a lot more parameters than regular networks to scale (Bubeck et al., 2021).\n\n### Q3) \nRegarding invertible networks for NF, is there a particular use of AOC possible to define the inverse of an orthogonal convolutional layer?\nIs there a link with transposed orthogonal convolution?\n\n### Q4) \nIn experiments, \"This is especially notable as our experiments did\nnot use techniques such as last layer normalization(Singla\n& Feizi, 2022), certificate regularization (Singla & Feizi,\n2021b), or DDPM augmentation (Hu et al., 2023).\" Can you test your method with those techniques to have a fair comparison with LiResNet and SOC? Reported certified accuracy on CIFAR-10 $64.3$% is way below the LiResNet SOTA ($78.1$%).\n\n### Q5) \nCan you provide tasks for normalizing flows and GANs or other applications of orthogonal networks that would highlight the AOC layer? \n\nI am willing to increase my score if my concerns were to be addressed.\n\n## References\n\nSebastien Bubeck and Mark Sellke. A Universal Law of Robustness via Isoperimetry.  Advances in Neural Information Processing Systems, 2021.", "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": "VuX36U3aM4", "reviewer": "Reviewer_BhA8", "summary": "The paper considers the problem of constructing convolutions which correspond to orthogonal operators. While the general approach is based on BCOP (Li et al. 2019), the authors extend this framework to certain variants of convolutions like stride, dilations, grouping and transposing and consider some aspects for reducing the computational cost. A numerical example for classification on CIFAR10 shows that these extensions can improve the expressiveness of orthogonal convolutional neural networks.", "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": "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.\n\nAbout experiments\n---------\n\n > What is accurate and robust AOC? Are only the architectures different or also the training?\n\nThe architectures, detailed in Appendix H, play a role in the accuracy/robustness tradeoff, but the main factor remains the loss: \n- The “robust” setting uses the scaled cross-entropy with margin (Prach et al.) to promote robustness.\n- 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). \n\nThis will be clarified in the main part of the manuscript (sect 3.1 l383).\n\n\n> Can you also construct an accurate/robust BCOP?\n\nThe “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. \n\n> Please include some SOTA non-orthogonal network as a reference to show the gap between orthogonal and non-orthogonal networks\n\nTable 2 includes some SOTA non-orthogonal networks, such as AOL, SLL, or Li-Resnet, that are non-orthogonal. \n\n\n> It would be good to compare the different convolution approaches with minimal differences in the rest of the hyperparameters…\n\nWe 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.\n\n\n\nAbout novelty and name of the method\n-----------\n\n> 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\n\nThe abstract indicates that “AOC  [is] a scalable method for constructing orthogonal convolutions, effectively\novercoming 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?\n\nIn 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**. \n\nAlso, besides the kernel construction, our contribution is 3 fold:\n- 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.\n- 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)\n- 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)\n\n\n> name of the method (adaptive orthogonal convolutions) a bit odd\n\nWe 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\n\nOthers\n------\n\n>   give a bit more intuition on some of the claims. For instance, Prop 2.4 \n\nWe appreciate the reviewer’s suggestion to provide more intuition. We will provide when possible in the main paper an intuition of the proof.\n\n> Proposition 2.7 is trivial. It basically states that the transposed matrix of a matrix with orthogonal columns has orthogonal rows\n\nWe 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.\n\nReference\n------\n\nWe 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.", "claims_and_evidence": "The claims are clear are sufficiently supported.", "methods_and_evaluation_criteria": "Methods and evaluation are feasible.", "theoretical_claims": "I only read the proofs, which are not stated to be contained already in the literature. The remaining ones seem to be correct, even though their are quite simple (the strengths of the paper are more in the modelling/conceptual part than in proving complicated theorems).", "experimental_designs_or_analyses": "The numerical setup is generally feasible to validate the claims of the paper. However, the description in the paper should be adjusted:\n\n- What is accurate and robust AOC? Are only the architectures different or also the training? Can you also construct an accurate/robust BCOP?\n\n- Please include some SOTA non-orthogonal network as a reference to show the gap between orthogonal and non-orthogonal networks\n\n- It seems like hyper-parameters and precise architectures play a massive role for the results. It would be good to compare the different convolution approaches with minimal differences in the rest of the hyperparameters...", "relation_to_broader_scientific_literature": "The general construction of orthogonal convolutions is taken from (Li et. al 2019, Xiao et al. 2018). The contributions of the paper are the extension to common variants of convolutions like stride, dilation, grouping.", "essential_references_not_discussed": "Many properties of orthogonal convolutions (matrix algebra/manifold property, orthogonal projections, an additional training algorithm etc.) were discussed in the paper:\n\nHertrich et al. \"Convolutional proximal neural networks and plug-and-play algorithms\", Linear Algebra and its Applications, 2021\n\nThis is highly relevant to the paper and should be discussed.", "other_strengths_and_weaknesses": "The main construction of the orthogonal convolutions in this paper is taken from the literature (Li et. al 2019, Xiao et al. 2018). However, the authors take care of all the variants of convolutions, which are used in literature. This includes stride, dilations, grouping and computational efficiency (and also transposed convolutions, but this part is a bit trivial). I consider this as a solid contribution. Additionally, the authors provide a PyTorch library for implementing their and several other orthogonal or 1-Lipschitz networks. Some weaknesses are listed below.\n\nIn summary, I would see the paper above the acceptance threshold, but I would wish that the authors reconsider their wording to describe their contribution more appropriately.\n\n## Weaknesses\n\n### Inaccurate names, abstract, introduction\n\n- I find the name of the method (adaptive orthogonal convolutions) a bit odd. Under adaptivity I would understand that the architecture adapts to the data/training process or whatever.\n\n- 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.\n\n### Other\n\n- It would be useful to give a bit more intuition on some of the claims. For instance, Prop 2.4 basically considers the setting where each pixel in the input image is covered exactly once from each kernel. This is one of the main reasons, why the orthogonality condition simplifies in this case.\n\n- Proposition 2.7 is trivial. It basically states that the transposed matrix of a matrix with orthogonal columns has orthogonal rows...", "other_comments_or_suggestions": "Please proofread the paper again and correct typos. Some examples:\n\n- line 196/197 left: missing spaces before references\n\n- line 212/213: \"convolutions kernel\" -> \"convolution kernels\"\n\n- line 1587: broken reference \"Table ??\"", "questions_for_authors": "see above.\n\n# After Rebuttal\n\nMany thanks to the authors for answering my questions and comments. I increased the score from 3 to 4.", "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: The paper received the following ratings: Weak accept, Accept, Weak reject, Accept. This paper proposes a scalable method for constructing orthogonal convolutions, combining BCOP and RKO methods. A parallel computing technique is proposed to improve performance significantly and supports additional functionalities such as stride and dilation. Experimental results showcase its effectiveness, including reduced parameter and computational overhead. Multiple weaknesses were also raised, including overstated novelty, limited theoretical guarantees, and scalability concerns. After the author-reviewer discussion, most reviewers agree that its practicality, good implementation, and accessible presentation, making a good contribution to neural network architecture research.
Decision: Accept (poster)