Orthogonalizing Convolutional Layers with the Cayley Transform
Authors: Asher Trockman
J Zico Kolter
Venue: ICLR 2021 Spotlight (2021)
Keywords: orthogonal layers
Lipschitz constrained networks
adversarial robustness

Abstract: Recent work has highlighted several advantages of enforcing orthogonality in the weight layers of deep networks, such as maintaining the stability of activations, preserving gradient norms, and enhancing adversarial robustness by enforcing low Lipschitz constants. Although numerous methods exist for enforcing the orthogonality of fully-connected layers, those for convolutional layers are more heuristic in nature, often focusing on penalty methods or limited classes of convolutions. In this work, we propose and evaluate an alternative approach to directly parameterize convolutional layers that are constrained to be orthogonal. Specifically, we propose to apply the Cayley transform to a skew-symmetric convolution in the Fourier domain, so that the inverse convolution needed by the Cayley transform can be computed efficiently. We compare our method to previous Lipschitz-constrained and orthogonal convolutional layers and show that it indeed preserves orthogonality to a high degree even for large convolutions. Applied to the problem of certified adversarial robustness, we show that networks incorporating the layer outperform existing deterministic methods for certified defense against $\ell_2$-norm-bounded adversaries, while scaling to larger architectures than previously investigated. Code is available at https://github.com/locuslab/orthogonal-convolutions.

Published as a conference paper at ICLR 2021
ORTHOGONALZZING CONVOLUTIONAL LAYERS WITH THE CAYLEY TRANSFORM
Asher Trockman
J. Zico Kolter
Computer Science Department Carnegie Mellon University ashert@cs. cmu edu
Computer Science Department Carnegie Mellon University & Bosch Center for AI zkol telttercss.co cmu. edu
ABSTRACT
Recent work has highlighted several advantages of enforcing orthogonality the weight layers of deep networks, such as maintaining the stability of activations, preserving gradient norms, and enhancing adversarial robustness by enforcing low Lipschitz constants. Although numerous methods exist for enforcing the orthogo- nality of fully-connected layers, those for convolutional layers are more heuristic in nature, often focusing penalty methods or limited classes of convolutions. In this work, we propose and evaluate an alternative approach to directly parameterize convolutional layers that are constrained to be orthogonal. Specifically, pose to apply the Cayley transform to skew-symmetric convolution in the Fourier domain, so that the inverse convolution needed by the Cayley transform can be computed efficiently. We compare our method to previous sipschitz-constraiiee and orthogonal convolutional layers and show that it indeed preserves orthogonal- ity to a high degree even for large convolutions. Applied to the problem of certified adversarial robustness, we show that networks incorporating the layer outperform existing deterministic methods for certified defense against ---norm--bundde ad- versaries, while scaling to larger architectures than previously investigated. Code is available at https: /tts:///gihhul com wwwccuslaboothhooonatt
pro-
ottp://rooooooooooooooooii.i.. convolutiooss
INTRODUCTION
Encouraging orthogonality in neural networks has proven to yield several compelling benefits. For example, orthogonal initializations allow extremely deep vanilla convolutional neural networks to be trained quickly and stably (Xiao et al., 2018; Saxe et al., 2013). And initializations that remain closer to orthogonality throughout training seem to learn faster and generalize better (Pennington et al., 2017). Unlike Lipschitz-constrained layers, orthogonal layers are et al., 2019), discouraging vanishing and exploding gradients and stabilizing activations (Rodríguez al., 2017). Orthogonality thus potential alternative batch normalization in CNNs and can help to remember long-term dependencies in RNNs (Arjovsky et al., 2016; Vorontsov et al., 2017). Constraints and penalty terms encouraging orthogonality can improve generalization in practice (Bansal et al., 2018; Sedghi et al., 2018 8). improve adversarial robustness by enforcing low Lipschitz constants, and allow deterministic certificates of robustness (Tsuzuku et al., 2018).
(Anil
Despite evidence for the benefits of orthogonality constraints, and while there are many methods to orthogonalize fully-connected layers, the orthogonalization of convolutions has posed challenges. More broadly, current Lipschit--constrained convolutions rely on spectral normalization and kernel reshaping methods (Tsuzuku et al., 2018), which only allow loose bounds and can cause vanishing gradients. Sedghi al. (2018) showed how clip the singular values of convolutions and thus enforce orthogonality, but relied on costly alternating projections to achieve tight constraints. Most recently, Li al. (2019) introduced the Block Convolution Orthogonal Parameterization (BCOP), which cannot express the full space of orthogonal convolutions.
In contrast to previous work, provide direct, expressive, and scalable parameterization of orthogonal convolutions. Our method relies on the Cayley transform, which well-known for pa- rameterizing orthogonal matrices in terms of skew-symmetric matrices, and can be easily extended to

---

Published as a conference paper at ICLR 2021
non-square weight matrices. The transform requires efficiently computing the inverse of particular convolution in the Fourier domain, which we show works well in practice.
We demonstrate that our Cayley layer is indeed orthogonal in practice when implemented in 32-bit precision, irrespective of the number of channels. Further, we compare it to alternative convolu- tional and Lipschitz-connstrained layers: deterministic certifiable robustness against an g--orr-bbundee adversary. Our layer provides state- of-the-art results on this task. We also demonstrate that the layers empirically endow considerable degree of robustness without adversarial training. Our layer generally outperforms the alternatives, particularly for larger architectures.
include them in several architectures and evaluate their
RELATED WORK
Orthogonality in neural networks. The benefits of orthogonal weight initializations for dynamical isometry, i.e., ensuring signals propagate through deep networks, are explained by Saxe et al. (2013) and Pennington et al. (2017), with limited theoretical guarantees investigated by Hu et al. (2020). Xiao et al. (2018) provided a method to initialize orthogonal convolutions, and demonstrated that it allows the training of extremely deep CNNs without batch normalization or residual connections. Further, Qi et al. (2020) developed a novel regularization term to encourage orthogonality throughout training and showed its effectiveness for training very deep vanilla networks. The properties of orthogonality can also help with remembering long-term term dependencies in RNNs, on which there has been much work (Helfrich al., 2018; Arjovsky et al., 2016).
One way to orthogonalize weight matrices is with the Cayley transform, which is often used in Riemannian optimization (Absil al., 2009). Helfrich et al. (2018) and Maduranga al. (2019) avoid vanishing/exploding gradients in RNNs using the scaled Cayley transform. Similarly, Lezcano- Casado & Martínez- Rubio (2019) use the exponential map, which the Cayley transform approximates. Liet al. (2020) derive an iterative approximation of the Cayley transform for optimizers and show it speeds the convergence of CNNs and RNNs. However, they merely orthog- onalize matrix obtained by reshaping the kernel, which is not the same as an orthogonal convo- lution (Sedghi et al., 2018). Our contribution is unique here in that we parameterize orthogonal convolutions directly, as opposed to reshaping kernels.
Bounding neural network Lipschitzness. Orthogonality imposes strict constraint on the I. Lipschitz constant, which itself comes with many benefits: Lower Lipschitz constants are associated with improved robustness (Yang et al., 2020) and better generalization bounds (Bartlett et al., 2017). Tsuzuku et al. (2018) showed that neural network classifications can be certified as robust to l norm-bounded perturbations given a Lipschitz bound and sufficiently confident classifications. Along with Szegedy al. (2013). they noted that the Lipschitz constant of neural networks can be bounded if the constants of the layers are known. Thus, there is substantial work on Lipschitz-constrainee and regularized layers, which review in Sec. 5. However, Anil et al. (2019) realized that mere Lipschitz constraints can attenuate gradients, unlike orthogonal layers.
There have been other ideas for calculating and controlling the minimal Lipschitzness of neural networks, e.g., through regularization (Hein & Andriushchenko, 2017), extreme value theory (Weng al., 2018), 8), or using semi-definite programming (Latorre et al., 2020; Chen et al., 2020; Fazlyab et al., 2019), but constructing bounds from tupschit-cconstraingg
layers is more scalable and ef- ficient. Besides Tsuzuku al. (2018)'s strategy for deterministic certifiable robustness, there are many approaches to deterministically verifying neural network defenses using SMT solvers (Huang et al., 2017; Ehlers, 2017; Carlini & Wagner, 2017), integer programming approaches (Lomuscio & Maganti, 2017; Tjeng& & Tedrake, 2017: Cheng et al., 2017), or semi-definite programming (Raghu- nathan et al., 2018). Wong et al. (2018)'s approach to minimize an LP-based bound on the robust loss is more scalable, but networks made from popschizz-constriiig still, as shown by Li et al. (2019) who outperform their approach. However, none of these methods yet perform well probabilistic methods (Cohen al., 2019).
components be more efficient
Consequently, orthogonal layers appear to be an important component to enhance the convergence of deep networks while encouraging robustness and generalization.
2

---

Published as a conference paper at ICLR 2021
3 BACKGROUND
Orthogonality. Since we are concerned with orthogonal convolutions, we review orthogonal matri- ces: A matrix Q E _ is orthogonal if Q" Q = QQ" = I. However, in building neural networks, layers do not always have equal input and output dimensions: more generally, a matrix U E gm*xn is I. Importantly, if m 2 n, then U is also norm -enn-rreervingg ||>Ø||2 = |0|| for all x E R". If m < n, then the mapping is merely non-expansive (a contraction), ie.. |U>2|22 S ||=|||2- A matrix having all singular values equal to is orthogonal, and vice versa.
semi-orthogonal if U I or UUT
Orthogonal convolutions. The same concept of orthogonality applies to convolutional layers, which also linear transformations. A convolutional layer conv RexxxX RRxaxx with = Cin = Cout input and output channels is orthogonal if and only if [|conv(X)]] ) = ||X | for all input tensors X E [exxxx; the notion of semi-orthogonality extends similarly for Gin * Cout- Note that orthogonalizing each convolutional kernel as in Lezcano-Casade & Martínez-Ruble (2019); Lezcano-Casate (2019) does not yield an orthogonal (norm- poom--presrrving convolution.
Lipschitzness under the l2 norm. A consequence of orthogonality is 1-Lipschitzness. A function f: R" + 1 is L-Lipschitz with respect the E norm iff fz) - f(y)ll2 S L - U/|2 for all U, E RR.. If T. is the smallest such constant for J. then it's called the Lipschitz constant of f. denoted by Li)(f). An useful property for certifiable robustness is that the Lipschitz constant of the com- position of f and g is upper-bounded by the product of their constants: Lip(f o g) < Lip(f) Lip()))))))) Since simple neural networks are fundamentally just composed functions, this allows us to bound their Lipschitz constants, albeit loosely. We can extend this idea to residual networks using the fact that Lip(f + g) S Lip(f) + Lip(g), which motivates using a convex combination in residual connections. More details can be found in Li et al. (2019); Szegedy et al. (2013).
Lipschitz bounds for provable robustness. we know the Lipschitz constant of the neural network, can certify that classification with sufficiently large margin is robust & perturbations below a certain magnitude. Specifically, denote the margin of a classification with label f as
My(x)- max(0, yr- max y:), 1fft
which can be interpreted as the distance between the correct logit and the next largest logit. Then the logit function f has Lipschitz constant L., and My > vLLe, then f'(x) is certifiably robust to perturbations (ō ||ō]|2 I c). Tsuzuku et al. (2018) and Li et al. (2019) provide proofs.
4 THE CAYLEY TRANSFORM OF A CONVOLUTION
Before describing our method, we first review discrete convolutions and the Cayley transform; then, we show the need for inverse convolutions and how to compute them efficiently in the Fourier domain, which lets us parameterize orthogonal convolutions via the Cayley transform. The key idea in our method that multi-channel convolution in the Fourier domain reduces to batch of matrix-vector products, and making each of those matrices orthogonal makes the convolution orthogonal. We describe our method in more detail in Appendix and provide a minimal implementation in PyTTrch in Appendix E.
An unstrided convolutional layer with Gn input channels and Cout output channels has a weight tensor W of shape I Xa, Xxxn and takes an input X of shape X produce an output Y of shape Rea Xuxn, i.e., convw 18exXxxx + R Xnxn, It is easiest to analyze convolutions when they are circular: if the kernel goes out of bounds of X, it wraps around to the other side- this operation can be carried out efficiently in the Fourier domain. Consequently, we focus on circular convolutions.
We define convw (X) as the circular convolutional layer with weight tensor W E R ReaaXe, Xe, applied to an input tensor X E Rew xxxn yielding an output tensor y = convw (X) E Reouxnxn Equivalently, we can view convw(X (X) as the doubly block-circulant matrix C' E Rewan xean corresponding to the circular convolution with weight tensor W applied to the unrolled input tensor vec vec.X E xx1 Similarly, we denote by convTy (X) the transpose CT of the same convolution, which can be obtained by transposing the first two channel dimensions of W and flipping each of the last two (kernel) dimensions vertically and horizontally, calling the result W', and computing conv (X). We denote conv (X) as the inverse of the convolution, i.e. with corresponding matrix C-1, which is more difficult efficiently compute.
3

---

Published as a conference paper at ICLR 2021
Now review how to perform convolution in the spatial domain. We refer pixel as Gin or Cout -iieensnnia slice of a tensor, like [:] Each of the n² (i,j) output pixels Y| i. are computed follows: for each
[Cout], compute Y[c, j, by centering the tensor W on the (i, pixel of the input and taking a dot product, wrapping around pixels of W that go out-of- bounds. Typically, W is zero except for k x k region of the last two (spatial) dimensions, which we call the kernel or the receptive field. Typically, convolutional layers have small kernels, e.g., k = 3.
Considering now matrices instead of tensors, the Cayley transform is a bijection between skew- symmetric matrices A and orthogonal matrices Q without -1 eigenvalues:
Q = - A)( + A)-
(2)
matrix skew-symmetric if A = -A and we can skew-symmelrize any square matrix B by computing the seemmeymmtriic part A = B B² The Cayley transform of such a skew-symmetric matrix is always orthogonal, which can be seen by multiplying Q by its transpose and rearranging.
We can also apply the Cayley transform to convolutions, noting they are also linear transformations that can be represented as doubly block circulant matrices. While it possible to construct the matrix C' corresponding to convolution convw and apply the Cayley transform to it, this is highly inefficient in practice: Convolutions can be easily skew nnew-symmetrized by computing convw (X) - conv T (X), but finding their inverse is challenging; instead, manipulate convolutions in the Fourier domain, taking advantage of the convolution theorem and the efficiency of the fast Fourier transform.
According to the 21) convolution theorem (Jain, 1989), the circular convolution of two matrices in the Fourier domain is simply their elementwise product. We will show that the convolution theorem extends multi-channel convolutions of tensors, in which case convolution reduces to a batch of complex matrix-vector products rather than elementwise products: inverting these smaller matrices equivalent inverting the convolution, and finding their kee--Hermitian part is equivalent to skew-symee seewsyymmtriizing the convolution, which allows us to compute the Cayley transform.
We define the 2D Discrete (Fast) Fourier Transform for tensors of order 2 as mapping FFT : R X Xm, x - C xm, xnxn defined by FFT(X) [81, .... d = F, X [1,, .... ir Fr for & E 1, ..... my and I E 1...., P' and r 2 0, where F, [t. = vn exp( 2 ) That is, we treat all but the last two dimensions as batch dimensions. We denote X = FFT(X) for tensor X.
Using the convolution theorem, in the Fourier domain the ch output channel the sum of the elemen- twise products of the on input and weight channels: that is, Y[c) = Ex_ W[c, k] @ X [k]. Equiva- lently, working in the Fourier domain, the (i.j)*h pixel of the et output channel is the dot product of the (7, j)th th pixel of the th weight with the (i. input pixel: [[., i,j] = W [c., i, 8|; (, From this, we can see that the whole (th Fourier-domain output pixel is the matrix-vector product
FCT ())) 4,5] = W|, i, x] [;, i.j).
This interpretation gives way to compute the inverse convolution as required for the Cayley transform, assuming Gin = Couti
FFT (X)) i, :
j.
(4)
Given this method to compute inverse convolutions, we can now parameterize orthogonal convo- lution with a skew-symmetric convolution through the Cayley transform, highlighted in Algorithm I: In line 1, we use the Fast Fourier Transform on the weight and input tensors. In line 4, we com- pute the Fourier domain weights for the skew-symmetric convolution (the Fourier representation is inverses required for FFT A+
thus the use of the conjugate transpose). Next, in lines 4-5 we compute the 4 (x)) and use them to compute the Cayley transform written as in line 6. Finally, we get our spatial domain result with the inverse FFT, which always exactly real despite working with complex matrices in the Fourier domain (see Appendix A).
4.1 PROPERTIES OF OUR APPROACH
It is important note that the inverse in the Cayley transform always exists: Because A is skew- symmetric, it has all imaginary eigenvalues, so + A has all nonzero eigenvalues and is thus nonsingular. Since only square matrices can be skew-symmetrized and inverted, Algorithm 1 only
4

---

Published as a conference paper at ICLR 2021
Algorithm 1: Orthogonal convolution via the Cayley transform.
Input: A tensor X E X and convolution weights W E X X with Gn = Cout- Output: A tensor Y ReaxXxxn the orthogonal convolution parameterized by W applied to X. W = =FFT(W) E CCanXcaxXX X == FXT C4*xxx
for i,j E 1, I...., // In parallel
do
Alii,i,]] == W[: 2, i|, Y[, = -1++ -,, [ii Y[iúj]] [...
end
return FFT FFT (Z).real
works for Gn = Cout but can be extended to the rectangular case where Cout 2 Gin by padding the matrix with zeros and then projecting out the first Gn columns after the transform, resulting in norm-preserving semi-orthogonal matrix; the case Gn 2 Cout follows similarly, but the resulting matrix is merely non-expansive. With efficient implementation in terms of the Schur complement (Appendix A.I, Eq. A22), this only requires inverting a square matrix of order min(Gin, Cout).
We saw that learning learnable scalar g and tensor V, as in weight normalization (Salimans & Kingma, 2016).
easier if we parameterized W in Algorithm by W gV/||V|| for
Comparison to BCOP. While the Block Convolution Orthogonal Parameterization (BCOP) can only express orthogonal convolutions with fixed k x k-sized kernels, Cayley convolutional layer can represent orthogonal convolutions with a learnable kernel size up to the input size, and it does this without costly projections unlike Sedghi et al. (2018). However, our parameterization as presented limited orthogonal convolutions without - eigenvalues. Hence, our parameterization incom- plete; besides kernel size restrictions, BCOP was also demonstrated to incompletely represent the space of orthogonal convolutions, though the details of the problem were unresolved (Li et al., 2019).
Our method can represent such orthogonal convolutions by multiplying the Cayley transform by fixed diagonal matrix with +1 entries (Gallier, 2006; Helfrich et al., 2018); however, we cannot optimize over the discrete set of such scaling matrices, so our method cannot optimize over all orthogonal convolutions, nor all special orthogonal convolutions. In our experiments, we did not find improvements from adding randomly initialized scaling matrices in Helfrich et al. (2018).
Limitations of our method. As our method requires computing an inverse convolution, is generally incompatible with strided convolutions; e.g., convolution with stride 2 cannot be inverted since it involves noninvertible downsampling. It is possible to apply our method to stride-2 convolutions by simultaneously increasing the number of output channels by 4x compensate for the 2x downsampling of the two spatial dimensions, though we found this to be computationally inefficient. Instead, we use the invertible downsampling layer from (Jacobsen et al., 2018) emulate striding.
The convolution resulting from our method is circular, which is the same as using the circular padding mode instead of zero padding in, e.g., Py PyTorch, and will not have large impact on performance subjects tend to be centered in images in the data set. BCOP (Li et al., 2019) and Sedghi et al. (2018) also restricted their attention to circular convolutions.
Our method is substantially more expensive than plain convolutional layers, though in most practical settings it is more efficient than existing work: We plot the runtimes of our Cayley layer, BCOP, and plain convolutions in a variety of settings in Figure 6 for comparison, and we also report runtimes in Tables and 5 (see Appendix C).
Runtime comparison Our Cayley layer does Cont FFTs on X matrices (i.e., the kernels padded to the input size), and Gn FFTs for each n n input. These have complexity OCiin log n) and OCouun? log n)) respectively. The most expensive step computing the inverse of n² square matrices of order c = min Cin C,ut), with complexity On222)) similarly to the method of Sedghi et al. (2018). We note like the authors that parallelization could effectively make this O(n² log + c²), and it is quite feasible in practice. As in Li et al. (2020), the inverse could be replaced with an iterative approximation, but did not find it necessary for our relatively small architectures.
5

---

Published as a conference paper at ICLR 2021
For comparison, the related layers BCOP and RKO (Sec. 5) take only O(c²) orthogonalize the convolution, and OSSN takes (nn (Li et al., 2019). In practice, we found our Cayley layer takes anywhere from 1/2x to 4x long BCOP, depending on the architecture (see Appendix C).
5 EXPERIMENTS
Our experiments have two goals: First, show that our layer remains orthogonal in practice. Second, we compare the performance of our layer versus alternatives (particularly BCOP) on two adversarial robustness tasks CIFAR-I0: We investigate the certifiable robustness against an (2-norm-bounded adversary using the idea of Lipschitz Margin Training (Tsuzuku et al., 2018), and then we look at robustness in practice against powerful adversary. We find that our layer is always orthogonal and performs relatively well in the robustness tasks. Separately, we show our layer improves on the Wasserstein distance estimation task from Li et al. (2019) in Appendix D.2.
For alternative layers, we adopt the naming scheme for previous work on sipschitz-constraing convolutions from Li et al. (2019), and we compare directly against their implementations. We outline the methods below.
RKO. A convolution can be represented as a matrix-vectoon product, e.g., using doubly block- circulant matrix and the unrolled input. Alternatively, one could stack each k x k receptive field, and multiply by the Cout X kn reshaped kernel matrix (Cisse et al., 2017). The spectral norm this reshaped matrix is bounded by the convolution's true spectral norm (Tsuzuku et al., 2018). Conse- quently, reshaped kernel methods orthogonalize this reshaped matrix, upper-bounding the singular values of the convolution by 1. Cisse al. (2017) created a penalty term based on this matrix; instead, like Li et al. (2019), we orthogonalize the reshaped matrix directly, called reshaped kernel orthog- onalization (RKO). They used iterative algorithm for orthogonalization (Björck & Bowie, 1971), )); for comparison, we implement RKO using the Cayley transform instead of Björck orthogonalization, called CRKO.
OSSN. A prevalent idea to constrain the Lipschitz constants of convolutions is to approximate the maximum singular value and normalize out: Miyato al. (2018) used the power method on the matrix W associated with the convolution, i.e., 8;+1 == W 8t, and mea se || //s,,//// s/lls Gouk al. (2018) improved upon this idea by applying the power method directly to convolutions, using the transposed convolution for WT, However, this one-sided spectral normalization is quite restrictive; dividing out dmar can make other singular values vanishingly small.
SVCM. Sedghi et al. (2018) showed how to exactly compute the singular values of convolutional layers using the Fourier transform before the SVD, and proposed a singular value clipping method. However, the clipped convolution can have an arbitrarily large kernel size, so they resorted to alternating projections between orthogonal convolutions and x k-kernel convolutions, which can be expensive. Like Li et al. (2019), we found that x 50 projections are needed for orthogonalization.
BCOP. The Block Convolution Orthogonal Parameterization extends the orthogonal initialization method of Xiao al. (2018). It differentiably parameterizes is x & orthogonal convolutions with an orthogonal matrix and 2(k 1) symmetric projection matrices. The method only parameterizes the subspace of orthogonal convolutions with k x k-sized kernels, but is quite expressive empirically. Internally, orthogonalization is done with the method by Björck & Bowie (1971).
Note that BCOP and SVCM are the only other orthogonal convolutional layers, and SVCM only for a large number of projections. RKO, CRKO, and OSSN merely upper-bound the Lipschitz constant of the layer by 1.
5.1 TRAINING AND ARCHITECTURAL DETAILS
Training details. For all experiments, we used CIFAR- 10 with standard augmentation, i.e., random cropping and flipping. Inputs to the model are always in the range [0, 1]: we implement normalization as layer for compatibility with AutoAttack. For each architecture/convolutioo
pair, we tried learning rates in {10-1 10 -4 10 10-3, 10-2, 20 10 }. choosing the one with the best test accuracy. Most often, 0.001 is appropriate. We found that piecewise triangular learning rate, used in top performers in the DAWNBench competition (Coleman et al., 2017), performed best. Adam (Kingma & Ba, 2014) showed significant improvement over plain SGD, and we used it for all experiments.

---

Published as a conference paper at ICLR 2021
256
3-+64 64
64 128
128
512 512
100
harre
Trunnng Trunngg
Tusms Tramiz
Trunts
Trantig
60
20
1-2e-
1+1e6
1-1eb
2+3ed
11sb
6-2e
1-3e5
1+2e-6
[Convtxip// [4l
/
[Convbol
[Conv00]::/PP Ptk
/Convielp//M4
(a)
(b)
(c)
(d)
(c)
Figure I: (Titles: Gin + Cout). Our layer remains orthogonal practice even for large convolutions (d, e), and is norm- corm-preserving when Cout > Gin (b, c); it is nonexpansive when Gin > Cout (a).
Loss function. Inspired by Tsuzuku et al. (2018), Anil et al. (2019) and Li et al. (2019) used multi-class hinge loss where the margin is the robustness certificate v2T.o- We corroborate their finding that this works better than cross-entropy, and similarly use cp = 0.5. Varying 6o controls a tradeoff between accuracy and robustness (see Fig. 5).
Initialization. We found that the standard uniform initialization in Py ToTchh performed well for our layer. We adjusted the variance, but significant differences required order-of-magnitude changes. For residual networks, we tried Fixup initialization (Zhang et al., 2019), but saw no significant improvement. We hypothesize this is due to (1) the learnable scaling parameter inside the Cayley transform, which changes significantly during training and (2) the dynamical isometry inherent with orthogonal layers. For alternative layers, used the initializations from Li al. (2019).
Architecture considerations. For fair comparison with previous work, we use the "large" network from Li et al. (2019), which first implemented in Kolter & Wong (2017)'s work on certifiable robustness. We also compare the performance of the different layers in a I-Lipschitz-constrainee version of ResNet9 (He et al., 2016) and WideRessNe10-10 (Zagoruyko & Komodakis, 2016). The architectures we could investigate were limited by compute and memory, as all the layers compared are relatively expensive. For RKO, OSSN, SVCM, and BCOP, we use Björck orthogonalization (Björck & Bowie, 1971) for fully-connected layers, as reported in Li et al. (2019); Anil et al. (2019). For our Cayley convolutional layer and CRKO, we orthogonalize the fully-comnected layers with the Cayley transform to be consistent with our method. We found the gradient-norm coreetttnoomm--eeeiiin GroupSort activation function from Anil et al. (2019) to be more effective than ReLU, and we used group size of 2, i.e. MaxMin.
Strided convolutions. For the LWLarge network, we used "invertible downsampling", which em- ulates striding by rearranging the inputs have 4x more channels while halving the two spatial dimensions and reducing the kernel size to [k/2] (Jacobsen et al., 2018). For the residual networks, simply used a version of pooling, noting that average pooling is still non-expansive when multi- plied by its kernel size, which allows us to use more of the network's capacity. We also halved the kernel size of the last pooling layer, instead adding another fully-connected layer; empirically, this resulted in higher local Lipschitz constants.
Ensuring L Lipschitz constraints. Batch normalization layers scale their output, so they can't be included in our J-Lipschitz-constrinnce architecture; the gradient- peeerm--peeevinngg properties of our layers compensate for this. We ensure residual connections are non-expansive by making them convex combination with a new learnable parameter a, i.e., g(z) ox(()) (1 a)x. for a E [0, 1]. To ensure the latter constraint, we use (a) We can tune the overall Lipschitz bound
given using the Lipschitz composition property, multiplying each of the layers by L //m
5.2 ADVERSARIAL ROBUSTNESS
For rectttiiable margin (z( greater than /2Le, where 36/255. For empirical defense, we use both vanilla projected gradient descent and AutoAttack by Croce & Hein (2020). For PGD, we use a = c/4.0 with 10 iterations. Within AutoAttack, based attacks provided no improvements. We report on e = 36/255 for consistency with et al. (2019) and previous work on deterministic certifiable robustness (Wong al., 2018). Additionally,
report the fraction of certifiable test points: i.e., those with classification
use both APGD-CE and APGD-DLR, finding the decision-

---

Published as a conference paper at ICLR 2021
WWTaree: Trained for provable robustness
Test Acc.
Cayley
BCОP
RKO
CRKO
OSSN
SVCM
.85-Cayley
Clean
75.33
75.114.37
74.47-.28
73.924.27
71.694.34
72.434.84
74.354.33
PGD
67.66=.31
67.29=.35
68.32=.22
68.03+.28
65.13+.10
66.43#.62
67.29+.52
36 AutoAttack
65.13=.48
64.62+.31
66.10-.26
65.95+.25
16 64.27+.67
65.00+.58
200
Certified
59.16=.36
58.29=.19
57.50=.17
57.48+.34
55.71 52.11
59.99=.40
Emp.Lip
0.740-.01
0.740=.02
0.667-.01
0.668+.01
0.716+.01 0.570+.02
0.648+.01
Table 1: Trained without normalizing inputs, mean/s.d. from 5 experiments reported. Our Cayley layer outperforms other methods in both test and & certifiable robust accuracy.
Cayley /KWLarge
BCOP/ KWLarge
RKO KWLarge
CRKO
KWLarge
100
90
80
20
logpllipschiz UB)
logglipichitzuuu UB)
pol.ipchizuup UB)
lopplippchkz US)
Figure 2: The provable robustness vs. clean accuracy tradeoff enabled by scaling the Lipschitz upper-bound for KWLarge.
we found it useful to report on empirical local Lipschitz constants throughout training using the PGD-like method from Yang al. (2020).
5.3 RESULTS
Practical orthogonality. We show that our layer remains very close to orthogonality in practice, both before and after learning. when implemented 32-bit precision. We investigated Cayley layers from one of our ResNet9 architectures, running them on random tensors to see if their norm is preserved, which is equivalent to orthogonality. We found that [|Conv(x)]]/ |a/|], the extent to which our layer is gradient norm preserving, is always extremely close to 1. We illustrate the small discrepancies, casily bounded between 0.99999 and 1.00001, Figure 1. Cayley layers which do not change or increase the number of channels are guaranteed to be orthogonal, which (b, c, d, e). Those which decrease the number of channels can only be non-expansive, and in fact the layer seems become slightly more corm-preserving after training (a). In short, our Cayley layer can capture the full benefits of orthogonality.
in practice for graphs
Certifiable robustness. We
layer and alternatives within the KWLarge architecture for a more direct comparison to previous work on deterministic certifable robustness (Li et al., 2019; Wong et al., 2018). As in (Li et al., 2019), we got the best performance without normalizing inputs, and can thus say that all networks compared here are at most 1 I-Lipschitz.
Our layer outperforms BCOP on this task (see Table 1), and is thus state-of-the-arr, getting on average 75.33% clean test accuracy and 59.16% certifiable robust accuracy against adversarial perturbations with norm less than 36/ 36/255. In contrast, BCOP gets 75. 11% test accuracy and 58. 29% certifiable robust accuracy. The reshaped kernel methods perform only a percent or two worse on this task, while the spectral normalization and clipping methods lag behind.
We assumed that layer is only meaningfully better than the other if both the test and robust accuracy are improved; otherwise, the methods may simply occupy different parts of the tradeoff curve. Since reshaped kernel methods can encourage smaller Lipschitz constants than orthogonal layers (Sedghi et al., 2018), we investigated the clean vs. certifiable robust accuracy tradeoff enabled by scaling the Lipschitz upper bound of the network, visualized in Figure/ 2. To that end, in light of the competitiveness RKO, we chose a Lipschitz upper-bound of 0.85 which gave our Cayley layer similar test accuracy; this allowed for even higher certifiable robustness of 59.99%. but lower test
8

---

Published as a conference paper at ICLR 2021
ResNet9
WideResNet10-10
Test Acc.
Cayley
ВСОP
RKO
CRKO
Cayley
BCOP
RKO
CRKO
Clean
81.70...1
80.72-.18
80.064.15
79.384.18
82.99
81.39
81.50 78.81
PGD
73.77=.19
73.27=.18
73.37=.12 72.52+.11
76.02
74.56
74.72
72.28
256
AutoAttack
71.17+.20
70.50-.06
71.01+.3 70.10=.07
73.16
71.86
72.24
69.97
Table 2: Empirical adversarial robustness for residual networks, mean and standard deviation for ResNet9 from 3 experiments. Cayley layers perform competitively on clean and robust accuracy.
accuracy of 74.35%. Overall, we were surprised by the similarity between the four lop-performing methods after scaling Lipschitz constants.
We were not able to improve certifiable accuracy with ResNets. However, it was useful increase the kernel size: we found 5 was an improvement in accuracy, while 7 and 9 were slightly worse. (Since our method operates in the Fourier domain, increases in kernel size incur no extra cost.) We also saw an improvement from scaling up the width of each layer of LWLarge, and our Cayley layer was substantially faster than BCOP as the width of Larae increased (see Appendix C)- Multiplying the width by 3 and increasing the kernel size to 5, we were able to get 61.13% certified robust accuracy with our layer, and 60.55% with BCOP.
Empirical robustness. Previous work has shown that adversarial robustness correlates with lower Lipschitz constants. Thus, we investigated the robustness endowed by our layer against & gradient-based adversaries. Here, got better accuracy with the standard practice of normalizing inputs. Our layer outperformed the others in ResNet9 and WideResNet10:: 10 architectures; results were less decisive for Large (see Appendix B). For the Nete we got 82.99% clean accuracy and 73.16% robust accuracy for e 36/255. For comparison, the state-of-the-art achieves 91.08% clean accuracy and 72.91% robust accuracy for e = 0.5 using ResNet50 with adversarial training and additional unlabeled data (Augustin et al., 2020). We visualize the tradeoff's for our residual networks Figure 3, noting that they empirically have smaller local Lipschitz constants than KWLarge. While our layer outperforms others for the default Lipschitz bound of 1, and is con- sistently slightly better than BCOP, RKO can perform similarly well for larger bounds. This provides some support for studies showing that hard constraints like ours may not match the performance of softer constraints, such as RKO and penalty terms (Bansal et al., 2018; Vorontsov et al., 2017).
CONCLUSION
In this paper, we presented new, expressive parameterization of orthogonal convolutions using the Cayley transform. Unlike previous approaches to Lipschitz-constrained convolutions, ours gives deep networks the full benefits of orthogonality, such as gradient norm preservation. We showed empirically that our method indeed maintains high degree of orthogonality both before and after learning, and also scales better to some architectures than previous approaches. Using our layer, were able to improve upon the state-of-the-art in deterministic certifiable robustness against an fg-norm-bounded adversary, and also showed that it endows networks with considerable inherent robustness empirically. While our layer offers benefits theoretically. involving orthogonalizing reshaped kernels were also quite effective for empirical robustness. Or- thogonal convolutions may only show their true advantage in gradient networks than we investigated. In light of our experiments scaling the Lipschitz. bound, we hy- pothesize that orthogonality, but insead the ability of layers such as ours to exert control over the Lipschitz constant, may be best for the robustness/accure expensive inverses using approximations or the exponential map, or compare various orthogonal and Lipschitz-constraing layers in the context of very deep networks.
observed that heuristics
preservation for deeper
tradeoff. Future work may avoid
ACKNOWLEDGMENTS
We thank Shaojie Bai, Chun Kai Ling, Eric Wong, and the anonymous reviewers for helpful feedback and discussions. This work was partially supported under DARPA grant number HR001 12020006.

---

Published as a conference paper at ICLR 2021
REFERENCES
P-A Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algorithms on matrix manifolds. Princeton University Press, 2009.
Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz function approximation. In International Conference on Machine Learning. pp. 291-301, 2019.
Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks, 2016.
Maximilian Augustin, Alexander Meinke, and Matthias Hein. Adversarial robustness on in- and out-distribution improves explainability, 2020.
Nitin Bansal, Xiaohan Chen, and Zhangyang Wang. Can we gain more from orthogonality regular- izations in training deep networks? Advances Neural Information Processing Systems, pp- 4261 1271- 2018.
Peter L Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally-normalized margin bounds for neural networks. Advances in Neural Information Processing Systems, pp. 6240-6249 2017.
Åke Björck and Clazett Bowie. An iterative algorithm for computing the best estimate of an orthogonal matrix. SIAM Journal on Numerical Analysis, 8(2):358 -364, 1971.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 20/7 ieee symposium on security and privacy (sp), pp. 39-57. IEEE, 2017.
Tong Chen, Jean B Lasserre, Victor Magron, and Edouard Pauwels. Semialgebraic optimization for lipschitz constants of relu networks. Advances in Neural Information Processing Systems, 33, 2020.
Chih Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. Maximum resilience of artificial neural networks. In International Symposium on Automated Technology for Verification and Analysis, pp. 251-268. Springer, 2017.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. arXiv preprint arXiv: / 1704.08877, 2017.
Jeremy M Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint arXiv: /0t2:::99000222 1902.02918 2019.
Cody Coleman, Deepak Narayanan, Daniel Kang, Tian Zhao, Jian Zhang, Luigi Nardi, Peter Bailís, Kunle Olukotun, Chris Ré, and Matei Zaharia. Dawnbench: An end-to-end deep learning bench- mark and competition. Training, 100(101): 2017.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-fiee free attacks. arXiv preprint arXiv:2003.00 01690, 2020.
Ruediger Ehlers. Formal verification of piece- piece-wise linear feed-forwan forwafo neural networks. In Interna- tional Symposium on Automated Technology for Verification and Analysis, pp. 269 286. Springer, 2017.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, pp. 11427-11438, 2019.
Jean Gallier. Remarks on the cayley representation of orthogonal matrices and on perturbing the diagonal of a matrix to make invertible. arXiv preprint math/0606320, 2006.
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael Cree. Regularisation of neural networks by enforcing lipschitz continuity. arXiv preprint arXiv:
2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
10

---

Published as a conference paper at ICLR 2021
Matthias Hein and Maksym Andriushchenko. Formal guarantees the robustness of classifier against adversarial manipulation. In Advances in Neural Information Processing Systems, pp- 2266-2276, 2017.
Kyle Helfrich, Devin Willmott, and Qiang Ye. Orthogonal recurrent neural networks with scaled cayley transform. In International Conference Machine Learning, pp. 1969-1978, 2018.
Wei Hu, Lechao Xiao, and Jeffrey Pennington. Provable benefit of orthogonal initialization in optimizing deep linear networks. In International Conference Learning Representations, 2020.
Xiaowei Huang, Marta Kwiatkowska, Sen Wang, and Min Wu. Safety verification of deep neural networks. In International Conference on Computer Aided Verification, pp. 3-29. Springer, 2017.
Jörn-Henrik Jacobsen, Arnold Smeulders, and Edouard Oyallon. i-revnet: Deep invertible networks. arXiv preprint arXiv: 802.07088 2018.
Anil K Jain. Fundamentals of digital image processing. Prentice-Hal) Hallc Inc., 1989.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXhv:1412.6980, 2014.
J Zico Kolter and Eric Wong. Provable defenses against adversarial examples via the convex outer adversarial polytope. arXiv preprint arXiv:1711.00833 1(2):3, 2017.
Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. arXiv preprini arXiv:2004008888 2020.
Mario Lezcan-LzzcaC Trivializations for gradient-based optimization on manifolds. arXiv preprint arXiv:990.09551,, 2019..
Mario Lezcano-Casado and David Martínez-Rubio. Cheap orthogonal constraints neural networks: A simple parametrization of the orthogonal and unitary group. arXiv preprint arXiv: arXiv:1901.00 1e01.0902888 2019.
Jun Li. Li Fuxin, and Sinisa Todorovic. Efficient riemannian Efficientrremmmmiin optimization on the stiefel manifold via the cayley transform. arXiv preprint arXiv:20022.0113,, 2020.
Qiyang Li. Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Jörn Morn-Herrik Jacobsen. Preventing gradient attenuation lipschitz constrained convolutional networks. In Advances in neural information processing systems, pp. 15390-15402, 2019.
Alessio Lomuscio and Lalit Maganti. An approach to reachability analysis for feed-forward relu neural networks. arXiv preprint /7Xiv: 2017.
Kehelwala DG Maduranga, Kyle Helfrich, and Qiang Ye. Complex unitary recurrent neural networks using scaled cayley transform. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4528-4535, 2019.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. arXiv preprint arXiv: /802.05/ 2018.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, nigh-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché-Buc, E. Fox, and R. Garnett (eds.). Advances in Neural Information Processing Systems 32, pp. 8024 8035. Curran Associates, Inc 2019.
Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice. Advances neural information processing systems, pp. 4785 4795-4795. 2017.

---

Published as a conference paper at ICLR 2021
Haozhi Qi, Chong You, Xiaolong Wang, Yi Ma, and Jitendra Malik. Deep isometric learning for visual recognition. In International Conference on Machine Learning. pp. 7824-7835. PMLR, 2020.
Aditi Raghunathan, Jacob Steinhardt, and Perey Liang. Certified defenses against adversarial exam- ples. arXiv preprint arXiv 11801.99344, 2018.
Pau Rodríguez, Jordi Gonzàlez, Guillem Cucurull, Josep M. Gonfaus, and Xavier Roca. Regularizing cnns with locally constrained decorrelations, 2017.
Tim Salimans and Durk P Kingma. Weight normalization: A simple reparametcriization to accelerate training of deep neural networks. In Advances in neural information processing systems, pp. 901- 909, 2016.
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. arXiv preprint
2013.
Hanie Sedghi, Vineet Gupta, and Philip Long. The singular values convolutional layers. arXiv preprint arXiv: 1805. 10408, 2018.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 2013.
Vincent Tjeng and Russ Tedrake. Verifying neural networks with mixed integer programming. arXiv preprint arXiv:
pp. 945-950, 2017.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certification of perturbation invariance for deep neural networks. In Advances in neural information processing systems, pp. 6541-6550, 2018.
Eugene Vorontsov, Chiheb Trabelsi, Samuel Kadoury, and Chris Pal. On orthogonality and learning recurrent networks with long term dependencies. arXiv preprint arXiv: http::/0200077777 2017.
Tsui-Wei Weng, Huan Zhang, Pin-Yu Chen, Jinfeng Yi, Dong Su, Yupeng Gao, Cho-Jui Hsieh, and Luca Daniel. Evaluating the robustness of neural networks: An extreme value theory approach. arXiv preprint 10t.:/001.1177 2018.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems, pp. 8400-8409, 2018.
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel S Schoenholz, and Jeffrey Penning- ton. Dynamical isometry and a mean field theory of cnns: How to train 10,000-layer vanilla convolutional neural networks. arXiv preprint 106.vv1806.05333, 2018.
Yao-Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Ruslan Salakhutdinov, and Kamalika Chaud- huri. A closer look at accuracy vs. robustness, 2020.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv ari:: 2016.
Fuzhen Zhang. The Schur complement and its applications, volume 4. Springer Science & Business Media, 2006.
Hongyi Zhang, Yann N Dauphin, and Tengyu Ma. Fixup initialization: Residual learning without normalization, arXiv preprint 1rXiv:1100.09922,,2 2019.
12

---

Published as a conference paper at ICLR 2021
A ORTHOGONALIZZIN CONVOLUTIONS THE FOURIER DOMAIN
Our method relies on the fact that multi-channel circular convolution can be block-diagonalized by suitable Discrete Fourier Transform matrix. We show how this follows from the 2D convolution theorem (Jain, 1989, p. 145) below.
Definition A.1. F2 is the DFT matrix for sequences of length nı; we drop the subscript when it can be inferred from context.
Definition A.2. We define convw(() as in Section 4; if Gin Cout 1, we drop the channel axes, i..., for X, W E [Raxn, the 2D circular convolution of X with W is convw (Xnv E R=**.
Theorem A.1. If R=²xx² represents a 2D circular convolution with weights W E R operating on a vectorized input vec(X) E R=*'1, with X E Rax", then it can be diagonalized as (F & F)C(F & F*) = D.
Proof. According to the 2D convolution theorem, we can implement a single-channe 2D circular convolution by computing the elementwise product of the DFT of the filter and input signals:
FWF FXF Fconvw (X)
(A1)
This elementwise product easier to work mathematically with we represent it as a diagonal- matrix-vector product after vectorizing the equation:
diag(veo(E-WF))) vec( =
(A2)
We can then rearrange this using vec( = (CT @ A) vec(B) and the symmetry of F:
diag(vec(FFF)))F @ vec (F @ F) vec(convw (X)).
(A3)
Left-multiplying by the inverse of and noting C vee( vec(convw (o)(ccoow(()))..)) we get the result
F 2 FF*FF
diag (vecg( (ec(FFF)) s F) = C (Fag(vec(FWFF) (F F)C(F* @ F*),
(A4)
which shows that the (doubly-block-ciculnn) matrix C is diagonalized by F F& F. An alternate proof can be found in Jain (1989, p. 150).
Now we can consider the case where we have 2D circular convolution C E: R xe." with Gn input channels and Cout output channels. Here, C has Cout Cin blocks, each of which is a circular convolution Cij E RRn xn? The input image vec = [vec?" XI,..., vec X E Remnxx1 where X; is the tth channel X.
T
Corollary A.1.1. IfC E R xean² represents a 2D circular convolution with Cn input channels and Cout output channels, then it can be block diagonalized Fe D, where Fo San" (Ie @ (F 8 F)), Sexz is a permutation matrix, Iy is the identity matrix of order k, and D is block diagonal with n² blocks of size Cout X Gin-
Proof. We first look at each of the blocks of C individually, referring to D as the block matrix before applying the S permutations, i.e., D ST
m DS cl n so that:
Duj = [[Lemr X (F F)) C (la, @ (F* x F')) = (F 3 (F" @ F*)
= diiagvvoo(FF)) (FW; FW;FF)), F)),
(AS)
where Wi are the weights of the (ij)th single-channel convolution, using Theorem A.1. That is, D a block matrix of diagonal matrices. Then, let Sa,b & be the perfect shuffle matrix that permutes the block matrix of diagonal matrices to block diagonal matrix. Sa.b can be constructed by subselecting rows of the identity matrix. Using slice notation:
Las(1 b. ab, :) las b ab;:)
Sabb
(A6)
(bb b ab,:).
13

---

Published as a conference paper at ICLR 2021
As example:
a 0
0 1
e 0
0
00000000
0
0000
0 0
0
0
000b
0
S2,1
0 1
$3,4
0 0
0 0
(A7)
m 0 n
D
0
k
0
0 0
W
0 0
Then, with the perfect shuffle matrix, we can compute the block diagonal matrix D as:
DST S S Cmin2 Seaun (Jem @ (F @ C (La, @ (F* F²)) S
F C.F D.
(A8)
The effect of left and right-multiplying with the perfect shuffle matrix is to create new matrix DD from D such that [Dali- = [Diyles. where the subscript inside the brackets refers to the 1tth diagonal block and the (ij) block respectively.
Remark. It is much more simple to compute (here wfft) tensor form given the convolution tensor:
weights W as Cout X Cin wfft- = fw) reshape cin, 2** permute(2, o, 1).
Definition A.3. The Cayley transform is a bijection between akew-Hermine matrices and unitary matrices; for real matrices, it is bijection between skew-symmetric and orthogonal matrices. We apply the Cayley transform to an arbitrary matrix by first computing its skew-Hermitian part: we define the function cayley Cm - C by cayley ()) (Im B B") (Im + B B²)-1
where we compute the Hew-Heemitiaan part of inline as B B". Note that the Cayley transform of real matrix is always real, i.e., Im(B) (B) a Lkee-syymmetie matrix.
Im(cayley| B)) 0, in which case B B B B"
We now note simple but important fact that we will use to show that convolutions are always exactly real despite manipulating their complex representations in the Fourier domain.
Lemma A.2. Say J m is unitary so that J I. and JBJ for B E mm and B E maxm Then cayley(B) (B) JC))
Proef. First note that B J implies BT B² (J Then
cayley(B) (3) = (T - B + )² + B²) = - JB-J JB Jパ
J[I - -B+ J(++B
J(T B
B-) B-)
J(I -
JJaally(B)))) (B)J"
(A9)
For the rest of this section, we drop the subscripts of F and when they can be inferred from context. Theorem A.3. When Gn = Cout c, applying the Cayley transform to the block diagonal matrix 'D results in real, orthogonal multi-channel 2D circular convolution:
cayley(C) = F F= (ayyeyy(D)
Proof. Note that F is unitary:
(A10) since S is permutation matrix and is thus orthogonal. Then apply Lemma A.2, where have J J= F*, B C, and B D, to see the result. Note that cC) is real because C is real; that is, even though we apply the Cayley transform to kkew-Hermitian matrices the Fourier domain, the resulting convolution real.
FF = S(I @ (F & FL) @ (F* @ FF)) = S = Ien
14

---

Published as a conference paper at ICLR 2021
Remark. While deal with akew-Hermitian matrices in the Fourier domain, are still effec- tively parameterizing the Cayley transform in terms of skew-symmetric matrices: as in the note in Lemma A.2, can that
C=F -C
(A11)
where C is real, D is complex, and C - CT is skew-symmetric (in the spatial domain) despite computing it with a skew-Hermitian matrix D" the Fourier domain.
Remark. Since D is block diagonal, only need to apply the Cayley transform (and thus invert) its n² blocks of size с c, which are much smaller than the whole matrix:
cayley(D) diaggcayley(Di))..... (ay
(A 12)
A.1 SEMI-ORTHOGONALL CONVOLUTIONS
In many cases, convolutional layers do not have Gn Couts in which they cannot be orthogonal. Rather, we must resort to enforcing semi-orthogonality. We can semi-orthogonalize convolutions using the same techniques as above.
Lemma A.4. Right-padding the multi-channel 2D circular convolution matrix C (from Cin Cout channels) with dn columns of zeros is equivalent to padding each diagonal block of the correspond- ing block-diagonal matrix D the right with d columns zeros:
CC Odn²] F diag([D)
Os)...., [D,> Oz])FF;
(A13)
where O2 refers to k columns of zeros and a compatible number of rows.
Proof. For a fixed column j, note that
[Dalis = 0 for all i, k = (Diglas = O for all i, < Cij =0 for all
(A14)
since Dig (F&F)),, (F*) only when Cij = Apply this for = Gin tintl
Gn +
Lemma A.S. Projecting out blocks of columns of C is equivalent to projecting out columns of each of the diagonal blocks D:
C Ldna
La ..... DN
Pa 0
F diag
Di
F
(A15)
0
Proof. This proceeds similarly to the previous lemma: removing columns of each of the n² matrices Di...., Dn, implies removing the corresponding blocks of columns of D. and thus of C.
Theorem A.6. C 2D multi-channel convolution with Gn S Cout, then letting d Cout Cin-
Tane
cayley ([C
0dm=l)
La cayley (D,,>
La 0s
F diag cayley ((D1
Oal)
0al)
F.
(A16)
0a
which is real 2D multi- chati-channel semi-orthogonal circular convolution.
Proof. For the first step, we use Lemma A.4 for right padding, getting
[C O F* diag([D Oa),..., [D, Oal)FF
(A17)
Then, noting that IC Oga²] is convolution matrix with Cin = Couts we can apply Theorem A.3 (and the following remark) get:
cayley (IC
Oan=]) = F diag (cayley ([D; 0a)) cayley (DD,> F.
(A18)
Since cayley ((C Ogm=l) is still real convolution matrix, we can apply Lemma A.5 to get the result.
15

---

Published as a conference paper at ICLR 2021
This demonstrates that them so that Gnn = Cout despite performing padding, the Cayley transform, and projections on complex matrices in the Fourier domain, we have shown that the resulting convolution is still real. In practice we do not literally perform padding nor projections; we explain how to do an equivalent but more efficient comptutation each diagonal block D2 C below.
semiiorthogonalize convolutions with Gin # Cout by first padding
Proposition A.7. We can efficiently compute the Cayley transform for semi-orthogonalizatin, ie., cayley (W Osl) [o when Cin S Cout by writing the inverse in terms of the Schur complement.
Proof. We can partition W E C X into its top part U E C and bottom part V E ((faa-)))X) and then write the padded matrix IW 0cca-cil C Cout
IW Ocamt - o 0l
(A19)
Taking the -kew-Hermittes part and applying the Cayley transform, then projecting, we get:
cayley (1V 8))
(Tem
1V 0] + (V
(Tem + -1 01
[
Tep
Jap U-U g
V
lew +0-
Ic,
(A20)
Fopst Sin
We focus on computing the inverse while keeping only the first Gin columns. We use the inversion formula noted Zhang (2006, p. 13) for block partitioned matrix M,
M
Ien
=
r Q 16
(M/S)
5 (--48-R((//S) -QS- [['00)
-(M/S)-IQS-
S R(M/S)
(M/S)
(A21)
H(M/S)
where we assume M takes the form of the inverse in Eq. A20, and M/S = PP-QS ---S-1 Ris the Schur complement. Using this formula for the first Gp columns of the inverse in Eq. A20, and computing the Schur complement Te, + U- - U + V cmn V, we find
cayley (lV 0)) = len -U+U"
V
(o (U,,tU-U+++""" [[-v -U-
-V
(Jan - UU+U" V
+V- -2V -U-,,,---U+~' -0-
E CCan XGnn
(A22)
which is semi-orthogonal and requires computing only one inverse of size Gin S Cout. Note that this inverse always exists because U U* skew-Hermin Hermitian, so it has purely imaginary eigenvalues, and VVV is positive semidefinite and has all real non-negative cigenvalues. That is, the sum Ic, +U - U + V*V has all nonzero eigenvalues and is thus nonsingular.
Proposition A.S. We can also compute onni-orthogonal convolutions when Cin 2 Cout using the method described above because cayley ([cr o1)² cayley ((6)).
Proof. We use that (A- = -AA))- and (I A)(1 + A) = (1+ A) (I A) to see
cayley (181)²² (1-1 101-11++10
(1- +111)) (r (I+18]
- -181) -1 (1 (1-181 181 + +111
= cayley (181²) cayley ([cr ol).
We have thus shown how to (semi-)ont Jotthooonalize real multi-channe 2D circular convolutions effi- (A23)
ciently in the Fourier domain. A minimal implementation of our method can be found in Appendix E. The techniques described above could also be used with other orthogonalization methods, or for cal- culating the determinants singular values of convolutions.
16

---

Published as a conference paper at ICLR 2021
B ADDITIONAL RESULTS
Cayley ResNet9
BCOP ResNet9
RKO / ResNet9
CRKO ReeNNtt9
101188
463
10
kgg.
Figure 3: The robustness/accuraccy tradeoff from changing the Lipschitz upper bound for ResNer9.
KWLarge: Trained for test & PGD accuracy
Test Acc.
Cayley
BCOP
RKO
CRKO
OSSN
SVCM
85-Cayley
Clean
79.87=.33
80.14-.32
79.65=.20
79.53+.22
78.66+.21
79.19+.30
79.55+.19
PGD
66.09-.47
65.31+.55
68.66-.20
68.55+.22
68.08+.20
68.35+,26
66.75+.34
36 AutoAttack
62.02-.60
60.634,72
65.164.14
65.40
64.901.17
64.921.15
62.671.32
255
Certified
38.67
36.92+.30
34.67+.32
35.87+.43
36.29+,65
29. 29.
41.97+.23
Emp.Lip
2.245a.04
2.272=.03
2.891=.02
1.8664.04
1.923+.06 1.698s.12 1.9994.03
Table Trained with normalizing inputs, mean and standard deviation from 5 experiments reported. The normalization layer increases the Lipschitz bound of the network to ~ 4.1, viz., CIFAR-10 standard deviation.
Cayley / KWLarge
BCOP /WLarge
RKO KWLarge
CRKO KWLarge
80
70
70
10
hggstieschitzz
Figure 4: Robustness vs. accuracy tradeoff from changing the Lipschitz upper bound for KWLarge.
For KWI Largree, our results on empirical robustness were mixed: while our Cayley layer outperforms BCOP in robust accuracy, the RKO methods overall more robust by around 2%, for only marginal decrease in clean accuracy. We note the lower empirical local Lipschitzness of RKO methods, which may explain their higher robustness: Figure 4 shows that the best choice of Lipschitz upper-bound for Cayley and BCOP layers may be less than for this architecture.
Cayley KWLarge
100
Tog:0Margin.co
Figure 5: Effect of varying 6o for Lipschitz margin training for K KWaaree.
17

---

Published as a conference paper at ICLR 2021
C
EMPIRICAL RUNTIMES
KWLarge Empirical Runtimes
Layer
Width Mult.
2
3
8
Test Acc.
75.97
76.97
76.94
76.80
78.28
Cayley
Certified
59.51
60.86
61.13
60.37
61.03
Avg. sec/Epocc
9.01
17.50
32.30
133.43
260.31
Test Acc.
75.28
75.81
76.35
76.55
BCOP
Certified
58.63
59.34
59.69
59.45
Avg. sec/Epooch
20.75
53.72
135.95
1050.61
Test Acc.
74.85
75.74
76.05
76.29
RKO
Certified
57.59
58.74
59.07
58.69
Avg. sec/Epoch
16.02
50.15
131,43
1034.96
Table 4: Here we multiplied the input channels and output channels of each layer of LLLage by width; we report on changes accuracy and average runtime per epoch (100 epochs). Width I was on Nvidia RTX 2080 Ti, while 2, 3, 6, and 8 were on Nvidia Quadro RTX 8000. In this case, we were unable scale BCOP to width 8 due to time and memory constraints. Generally, the wider networks may need more epochs to converge.
Avg. sec/Epoch
Architecture
Cayley
BCOP
RKO
Plain Conv.
Both Plain
ResNe19
43.92
48.04
45.73
14.56
13.27
10d
210.6
109.4
99.46
48.40
46.10
Table 5: Our Cayley layer not fast for residual networks, possibly because they have convo- lutions with more channels and also larger spatial dimension, which is multiplicative factor in our runtime analysis. This is especially true for the WideResNet. For plain conv, replaced the Cayley convolutional layer with a plain circular convolution, leaving the Cayley fully-connecte layers. For both plain, we also used plain fully-connected layers.
18

---

Published as a conference paper at ICLR 2021
Runtime Channels,
Runtime Channels,
82
Avg. (UMUU))
100
20
100
330
200
503
Channels (n
Charnels out)
(a)
Runtime vs. Spatial Size, Gi Cout =
Runtime vs. Spatial Size, Gn Cout 32
300
PAgg Iie (C300))
100
200
50
(c)
(d)
Runtime vs. Kernel Size, Cn Cout = 32, n 16
Runtime vs. # Output Channels, Gp. = =32, n 166
400
30
Avb mm (C310A)
300
100
5000
10
130
300
530
(Caz)
(e)
(f)
Figure 6: Our Cayley layer is particulaly efficient for inputs with small spatial dimension (width and height, ie., n) (see (a), (c)), large kernel size (see (e)), and cases where the number of input and output channels are not equal (Gn # Cout) (see (f)). For very large spatial size (image width and height) (see (d)), or the combination BCOP (Li et al., 2019) tends to be more efficient. Since convolutional layers in neural networks tend to decrease the spatial dimensionality while increasing the number of channels, and also often have unequal numbers of input and output channels, Cayley layer is often more efficient in practice. In all cases, orthogonal convolutional layers are significantly slower than plain convolutional layers.
relatively large spatial size and many channels (see (b)),
Each runtime was recorded using the autograd profiler in PyTorch (Paszke et al., 2019) by summing the CUDA execution times. The batch size was fixed at 128 for all graphs, and each data point was averaged over 32 iterations. We used Nvidia Quadro RTX 8000.
19

---

Published as a conference paper at ICLR 2021
D ADDITIONAL BASELINE EXPERIMENTS
D.I ROBUSTNESS EXPERIMENTS
LWLare
ResNet9
Test Acc.
CayleyBCOP
Test Acc.
Plain Conv.
CayleyBCOP
0
Clean
74.35-229
Clean
89.224.18
80.05-.20
PGD
66.91-.10
36 255
PGD
70.86=.06
72.58=.25
AutoAttack
64.36=.17
AutoAttack
68.201.10
69.90-.35
255
Certified
57.94=222
Emp.Lip
0.732-.01
Table 7: Additional baselines for ResNet9 trained for empirical adversarial robustness. Mean and s.d. over 3 trials.
Table 6: Additional baseline for LWLare trained for provable robustness. Mean and s.d. over trials.
The main competing orthogonal convolutional layer, BCOP (Li et al., 2019), uses Björck (Björck & Bowie, 1971) orthogonalization for internal parameter matrices; they also used their experiments for orthogonal fully-connected layers. Similarly to how replaced the method in RKO with the Cayley transform for our CRKO (Cayley RKO) experiments, we replaced Björck with the Cayley transform in BCOP and used Cayley linear layer for CayleyBCOP experiments, reported in Tables 6 and 7. We see slightly decreased performance over all metrics, similarly to the relationship between RKO and CRKO.
For additional comparison, we also report on a plain convolutional baseline in Table 7. For this model, we used plain circular convolutional layer and Cayley linear layer, which still imparts considerable degree of robustness. With the plain convolutional layer, the model gains a considerable degree of accuracy but loses some robustness. We did not report a plain convolutional baseline for the provable robustness experiments on KWLarge, as it would require a more sophisticated technique bound the Lipschitz constants of each layer, which outside the scope of our investigation.
D.2 WASSERSTEIN DISTANCE ESTIMATION
Cayley
BCOP
RKO
OSSN
Wasserstein Distance:
10.72
10.08
9.18
7.50
Table 8: For BCOP, RKO and OSSN, we report the best bound over all trials from the experiments in the repository containing BCOP's implementation (Li al., 2019). We one trial of the Wasserstein GAN experiment, replacing the BCOP and Björck layers with our Cayley convolutional and linear layers, and achieved a significantly tighter bound. We only report on experiments using the GroupSort (MaxMin) activation (Anil et al., 2019) and on the STL-10 dataset.
We repeated the Wasserstein distance estimation experiment from Li al. (2019), simply replacing the BCOP layer with our Cayley convolutional layer, and the Björck linear layer with our Cayley fully-connected layer. took the best Wasserstein distance bound from one trial each the four learning rates considered in BCOP (0.1, 0.01, 0.001, 0.0001); Table 8.
20

---

Published as a conference paper at ICLR 2021
E EXAMPLE IMPLEMENTATIONS
In PyTorch 1.8, our layer can be implemented as follows.
def cayley(M):
if len shape) = 2:
return [WyleyyW[Nonee [o]
cout, cin shappp
if > cout:
return (ayley(..transsp) transpose(1, 2)). traassposss(1,, 2)
U, V W[: :cin], W[:, cin:]
I torch. (cinn, Slype=R.dtype, device=W.devin [None, :] cononj transpose(1, inv torch. inverse A)
V.conj transpose(1,
return torch. cat ((inv @ (I A), -2 V 0 inv), axis=1)
class (ayleyConv(nn.Conv)
def ttaiffttmariixseef..tt n, s):
shift torch. arange(0, n) r(peat((n, 1))
shift shift s
return torch.exp(2j * np.pi * * shift / n
def forward(self, x):
cout, cin, -1 self weight. batches, n, shape
if not haslttr(self, "shift madiii"atrii");;
= (self. www.wit...tht........ - 1) // 2
self. self.shift.marre = self.fft_ folffffftshiftt..o. sshift_matrixnn
-s)[; (n//2 + 1)]
rreshape (n (n // 1), to.ot(x.coom device)
xfft Sarch.fft.rfft20x permuttee) 3, 1, \
reshape (n // 1), cin, batches) wfft = self.shift_matril
torch. fft. rfft. wsef. (n, n))
(couh, cin, n (n // 1)) permuteee, 0, 1) .).conj( () yfft (cayley(wfft) xfft) reshape //
cout, batches)
y torch, ifff..fftt permutee, 2, 0, 1))
if self.bis bias is not None:
+= : None, None]
return
To make the layer support stride-2 convolutions, have CayleyConv inherit from the following class instead, which depends on the einops package:
class StridedConv (nn. :onv2d)
def (selt,, *args, **wwarg)):
if "stride" in kwargs and kwargs["strides == 2: args lirg(args)
args[0]
args[0] 4x channels args [2] args[2] // //2 kernel_size; optional
args = tuple(args)
super (uper()__iitt.... itrr
kwargs)
downsample "b (w k1) (h k2)
(c k1 k2) h"
self.register_foor forrrffowwrdrrrre hook (lambda x:
einops. rx.1) downsample, k1=2, k2=2) A if
== (2, 2) else x[0])
More details on our implementation and experiments can be found at: https: //gi thub. wttpttt.cm..cuu....bbbb.o httpc///ccslllaa/oooogollllllll -ot.o convolutions.
21


Reviews:
[{"review_id": "mWlBZMYrzcJ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Comments after rebuttal**: Overall the authors have addressed many concerns in the latest version of the paper. In the current form, I have a much better impression of this work and thus raise my score to a point where I can recommend acceptance. In the following I add some after-rebuttal comment at the end of each item of my original review:\n\n## Summary:\nThis papers presents an application of the Cayley Transform to parameterizing a subset of orthogonal convolutional layers. As I understood, in contrast to other methods that orthogonalize the convolution by reshaping the kernel, the orthogonalization is performed in the frequency domain: the Cayley transform is applied to the kernel matrices corresponding to each pixel, after applying the FFT and then the output is recovered using the inverse FFT. Then it is shown empirically that this method preserves norms and that either this method or a combination of the Cayley transform and a method from a different paper (RKO) improves upon certified robustness (using the simple Lipschitz-margin bound). Some marginal gains on clean error are also reported.\n\n## Pros:\n**1. Quality: The empirical evaluation is good at comparing between baselines**, however it could be improved (see Cons).\n\n**2. Originality: It seems interesting and novel to do orthogonalization using the Cayley Transform in Fourier domain, as this seems to bypass limitations of other methods that have troubles trying to \"orthogonalize\" the matrix corresponding to the convolution**. The main issue is that such process usually returns a matrix that does not correspond to an actual convolution and this paper seems to avoid that issue altogether.\n\n**3. Significance: From experimental evaluation it seems that the proposed method is a strong candidate among other alternatives to orthogonal convolutional layers**. However it is also more expensive. **after-rebuttal:** the authors have added additional experiments and show that in practice their method can be as fast or faster than other baselines in certain scenarios.\n\n**4. Significance: It seems that the space of orthogonal transformations parameterized in the way proposed in this paper can be more expressive than previous work BCOP or RKO**. Although this could be clarified further by the authors.\n\n## Cons:\n**1. Clarity: after reading the paper multiple times, It is not clear to me if this is a heuristic argument or if we can prove that the output of the so-called \"Cayley Layer\" is indeed orthogonal**. That is, can we show a theorem like \"Let $f(x)$ be the output of the Cayley Layer (Algorithm 1), then $||f(x)\\|/ ||x|| = 1$ for all $x$.\" Is this true? does it make sense? It looks like experiments in figure 1 are trying to validate this empirically but I wonder if this formal result could be obtained. **after-rebuttal:** The authors make this more clear in sections 3 and 4.\n\n**2. Clarity: I feel that there are many terms thrown around without a clear definition, and it makes the arguments confusing.** In particular I am talking about the whole of section. I elaborate further:\n- First, skew-symmetry is defined for square matrices and then the term \"skew-symmetryze\" is for the transformation $f(A)=A-A^T$. So what does skew-symmetryze mean? if it means a function such that its ouput is skew-symmetric then it would be trivial to output any constant skew-symmetric matrix. The important thing about $f(A)=A-A^T$ is that it is in fact the orthogonal projection of $A$ onto the space of skew-symmetric matrix (modulo a factor of 1/2).\n- Then what does it mean to skew-symmetrize a convolution? here the authors use the notation $conv_{W}(x)$ which is not defined anywhere but I guess that it means the linear operator corresponding to the convolution with kernel $W$. but is this a single kernel matrix? I assume because otherwise what is $W^T$ in $\\text{conv}_{W^T}$ note that in the previous paragraph $W$ is defined as a tensor of higher rank=4 so its transpose is not defined!\n- In line with the previous, the vanilla way to \"skew-symmetryze\" $conv_W$ would be $conv_W - (conv_W)^T$. What is the relation with the expression $conv_W - conv_{W^T}$? In summary, I found this paragraph extremely confusing. **after-rebuttal:** The authors go over the definitions and now make more clear statements in section 4, which makes the argument more concise. The current version is more enlightening to the reader.\n\n**3. Clarity: I am confused by the two proposed methods CRKO and Cayley which I think are not properly highlighted**. In the \"Architecture considerations\" in page 6 what do you mean that “for our Cayley layer… we use the Cayley transform for consistency” what is the alternative? isn’t using the CT the whole point about CRKO and Cayley Layer? what is the difference between the Cayley Layer and CRKO? On a first read I thought they were the same(?) Looks like CRKO is RKO + Cayley transform but It would be good to clarify the differences\u0000\n\n**4. Significance: It is not clear how the method deviates in practice from using the orthogonal layer mentioned in the work of Lezcano-Casado (more precisely in the repo https://github.com/Lezcano/expRNN) where it is mentioned that their Orthogonal layer can also be used with CNNs. Why isnt that approach compared here?** Is it possible to compare to it? It looks like the issue might be again that the Cayley-transformed matrix might not correspond to a convolution, could the authors confirm or comment on this? **after-rebuttal:** This has been further clarified by the authors, the method mentioned does not provide orthogonal convolutions.\n\n**5. Significance. It is not clear how the methods and baselines improve over vanilla CNNs which should be included as a baseline, in my opinion, to understand the benefits of orthogonal layers (Table 1). Additionaly it is claimed that Cayley is state-of-the-art on clean test-accuracy and certified robustness. This is really debatable**, if clean test accuracy is the metric isn't adversarial training state of the art? I think it should also be included in Table 1. In any case the improvement over BCOP seems marginal. Additionaly, certified robustness is computed in a really limited way using the Lipschitz-margin bound whereas there are other methods that could certify better. So it is not clear what is the state-of-the-art claim and I believe this is over-stated. **after rebuttal**: I still believe the state-of-the-art claims are overstated because the authors do not compare to methods that certify robustness without resorting to Lipschitz continuity constraints. In my opinion, this should be downplayed and change to a more clear conclusion for example: among methods that certify robustness through the Lipschitz bound of CNNs using a per-layer regularization, our method achieves state-of-the art. this would be much closer to reality.\n\n**6. Clarity: I did not understand the difference between some baselines**: Given that BCOP and RKO both use the Bjorck-Bowie algorithm would it be possible to explain the difference between those two methods? **after rebuttal**: clarified by the authors.\n\n## Other comments\n1. Page 5. I think the issue with OSSN is that dividing by the largest singular value DOES NOT correspond to the projection onto the 1-ball corresponding to the spectral norm. That is actually achieved by clipping the singular values as in SVCM. Of course this works only for matrices without additional constrainst, which is precisely the problem SVCM has with the additional constraint that the matrix should correspond to a convolution.\n\n2. Final sentence in paragraph \"Strided convolutions\" (page 6): Typo: remove “used”\u0000 **after rebuttal:** fixed.\n\n3. In line 6 of algorithm 1 I believe there is a typo. Should it be $\\tilde{Y} - \\tilde{A} * \\tilde{Y}$ or am I missing something? **after rebuttal:** fixed.\n\n4. Missing references: In related work there is a discussion about methods controlling the Lipschitz constant of networks \"There have been other ideas for calculating and controlling the minimal Lipschitzness of neural networks...\" there are some other interesting works in this area that can potentially lead to better certified robustness than using the vanilla upper bounds like in Tsuzuku et. al. (2018) see\nhttps://openreview.net/forum?id=rJe4_xSFDB\nhttps://arxiv.org/abs/2002.03657 **after rebuttal:** missing references have been added.\n\nOverall, I think that this paper is valuable but some parts need to be improved to recommend acceptance. If some of these issues are adressed in a succint way then I would be willing to increase my score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "gb8fQovOfVz", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary \n**Objective:** attain orthogonal convolutions.\n\n**Approach:** use $conv_W(x)-conv_{W^T}(x)$ which is skew-symmetric together with the Cayley map. \n\n### Strengths\n**[+]** Using transposed convolutions to attain a \"skew-symmetric\" convolution is interesting.  \n\n**[+]** The paper constructs an orthogonal convolution instead of enforcing orthogonality on a reshaped kernel. This ensures properties like gradient norm preservation. I always thought the lack of this property was a major limitation of previous work. The paper address this limitation for for circular convolutions. \n\n### Weaknesses\n**[-]** The resulting convolution is circular. \n\n**[-]** They need invertibility which adds constraints on the convolutions stride and shape. \n\n**[-]** The author could be more explicitly outline the above limitations wrt expressiveness. \n\n### Recommendation: Acceptance 7\n**[+]** The paper address an important problem, and present the first \"real\" orthogonal convolution. \n\n**[-]** The orthogonal convolution is circular, and I think such limitations could be outlined more explicitly.  \n\nBefore discussion: *I was torn between 6 and 7. If the authors add a paragraph that explain limitations wrt circular convolution, stride and shape I'll be happy to change to 7. That said, I'll condition this statement on first re-evaluating my opinion based on the comments from the other reviews. It is possible I am being a bit too harsh here, but it is also possible the other reviewers caught something I did not.*\n\nThe authors addressed my concerns and it seems my co-reviewers didn't bring new concerns to light, so I increased my score to 7. \n\n### Questions and Concerns\n**All my questions was addressed by the authors before I submitted my review**. These questions, and their answers, should be visible to all other reviewers, the area chairs and the program committee. For completeness, I copied the questions below, please note they were already answered by the authors. \n\n---\nQuestion 1. Equation (3) and (4) use both $x$ and $X$. Is this a typo, and should both be $X$?\n\nQuestion 2. Equation (3) and (4) use $FFT:\\mathbb{R}^{n\\times n}\\rightarrow \\mathbb{C}^{n\\times n}$ on $X\\in \\mathbb{R}^{c_{in}\\times n \\times n}$ and $W\\in \\mathbb{R}^{c_{out}\\times c_{in} \\times n \\times n}$. Strictly speaking this is not well-defined, however, I suspect you just mean $FFT(X)[i, :, :]:=FFT(X[i, :, :])$. Is my suspicion correct?\n\nQuestion 3. You write *\"..., we see that the $(i, j)$'th Fourier domain output pixel is given by the matrix-vector product .. \"*. This reminded me of the periodic convolution section 3.2 from [0]. Is the the same, if not, what is the difference? \nI'm asking to make sure I understand your method. If it is the same, I believe your method can be summarized as done below. Please let me know if this is correct/wrong.\n\nThe periodic convolution $c(x)$ from [0] is invertible, which allows us to compute the inverse of the skew-symmetric operation $S(x)=c(x)-c^T(x)$. Since we can compute both $S(x)$ and its inverse, we can compute the Cayley transform of $S$ which is orthogonal. \n\nI want to emphasize that, if this is what you're doing, I do think it is novel.  \n\nQuestion 4. To compute the inverse used in the Cayley transform you rewrite the convolution operation to matrix-vector multiplication in Fourier space. To do this you utilize the convolution theorem which only works for circular convolutions. How does this effect the resulting orthogonal convolution? \n- (a) Does it have some circular behavior? \n- (b) Must the kernel size be equal to the input size, e.g., W.shape=(c_in, c_out, **n**, **n**) with X.shape=(c_in, **n**, **n**)?\n- (c) Must the convolution be unstrided?\n\nMaybe I missed it in the paper, but such restrictions were not entirely clear to me. \n\n---\n\n### Additional Feedback\nFix the typo and maybe emphasize broadcasting notation in equations (3) and (4) as previously discussed. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "LhHDQifOtlP", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "***Summary***\nThe paper uses the idea that a convolution on the Fourier space accounts just to a matrix-vector product. It then uses the Cayley map to parametrise the special orthogonal group, compute the action and send the tensor back using the inverse FFT. They test this idea in the context of certifiable robustness.\n\n***Comments***\n\n1) Page 3. \"Computing a dot product\".\nUsually the term \"dot product\" is used to refer to scalar products. It would be perhaps more reasonable to say that it performs a \"matrix-vector product\".\n\n2) Page 3. \"Typically, $W$ is zero except for a $k\\times k$ region, which we call the kernel or the receptive field.\".\nHere $W$ is the matrix version of the convolution. For this reason, $W$ is non zero in $k^2$ elements in every row of each matrix $W[:, :, i, j]$, not in a $k \\times k$ region. Although I might have misunderstood this...\n\n3) The operator $\\operatorname{conv}$ is not defined anywhere. In general, it would be very helpful to say where does each object live in page 3, as $W$ seems to be used as both an element of $\\mathbb{R}^{c_{out} \\times c_{in} \\times n \\times n}$ and later as a square matrix. This is quite confusing. See also 7)\n\n4) Page 3. Cite some standard reference where a formal statement of the convolution theorem is given.\n\n5) Page 3. Mention that $F_n^\\ast$ denotes the conjugate transpose.\n\n6) Eq. 3. Explain how are $x$ and $X$ related\n\n7) Similar to 3), $\\operatorname{FFT} \\colon \\mathbb{R}^{n \\times n} \\to \\mathbb{C}^{n \\times n}$, but in Algorithm 1) this is applied to tensors. In this particular case one can hint what is going on, but again, it is unnecessarily difficult to track what lives what conventions are being used when an operator is applied to a tensor. This should be made explicit somewhere.\n\n8) Page 4. \"However, it can be extended to all orthogonal convolutions by multiplying by a diagonal matrix with $\\pm 1$ entries (Gallier, 2006; Helfrich et al., 2018).\".\nThis is not true. The correct theorem says that \"for every $B \\in \\operatorname{O}(n)$ there exists a diagonal matrix $E$ with entries in $\\{ -1, 1 \\}$ such that $E\\operatorname{cay}(X) = B$ for some $X \\in \\operatorname{Skew}(n)$. Note that the matrix $E$ depends on the matrix $B$. As such, to cover the whole $\\operatorname{O}(n)$, (or $\\operatorname{SO}(n)$) one would have to optimise over this discrete set, which is not easy.\n\n9) Could the authors comment on how their method to parametrise non-square matrices via the Cayley transform relates to that used in the classical paper:\n\nZaiwen Wen and Wotao Yin. A feasible method for optimization with orthogonality constraints.Mathematical Programming, 142(1-2):397–434, 2013.\n\nNote that the standard method would account for lifting the problem from $\\operatorname{St}(n,k)$ to $\\operatorname{SO}{n}$, compute the Cayley map and then just take the first $k$ columns. Their method is slightly different. Is your method one of these two or is it different to both of them? I believe that this discussion should be in the main paper in the related work section.\n\n10) Just out of curiosity, how expensive is this method when compared with an unconstrained convolutional layer in wall-clock time?\n\n***Experiments***\n\nWhat is the reason for using Björck & Bowie (1971) to orthogonalise the layers in the other examples? This is a very bad way to do so which leads to some terrible dynamics. I believe that Cayley should be used throughout all the experiments. Could the authors report the results of the other methods while using Cayley also for them?\n\n***Conclusion***\n\nThis is a very strong paper, with a very nice application of orthogonalisation in the context of CNNs. I think that the presentation of the content in the paper is very good. The only thing I did find quite confusing is the lack of definitions in section 4. I would be happy to increase my score provided that the problems raised here are addressed, in particular that of the experiments.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "8O6NvQuedV", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper provides another parameterization for orthogonal convolutional layers using the Cayley transform, different from BCOP. To the best of my knowledge, this parameterization is novel. However, I have a few questions regarding the proposed method.\n\n(1) For 1D-convolutional layers, BCOP is a complete characterization. From the paper, the parameterization is not complete since the eigenvalues are all +1. While it is possible to multiply a diagonal matrix with either +1 or -1 entries, it is not clear such multiplication closes the gap. I am curious whether the composition is complete; otherwise, the proposed parameterization is strictly weaker than BCOP. \n\n(2) For 2D-convolutional layers, I believe both BCOP and the proposed method using the Cayley transform are incomplete. So I am curious whether the proposed parameterization is a proper superset of BCOP. Without the argument, it is vague to state the proposed method is more expressive than BCOP --- the better results could come from optimization instead of parameterization. That being said, the paper is still interesting if the proposed parameterization covers a different subset of all orthogonal 2D-convolutional layers (i.e., neither a superset nor a subset of BCOP). In this case, the authors need to characterize the difference between these two subsets. Which layer can be parameterized by Cayley transform but not BCOP, and vice versa?\n\nIf the authors can clarify the questions, I will definitely increase my score. Others are minor comments: \n\n(3) Comparing computational complexities for different methods, RKO, OSSN, SVCM, BCOP, and Cayley transform is desired.  \n\n(4) The BCOP includes the experiment of Wasserstein distance estimation. Empirically, it is better to show the proposed method is better than BCOP in various scenarios if a theoretical justification is too hard, if not impossible.\n\nThe questions above are well addressed in the response, and I would like to increase my score.  ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Very good paper: it proposes a novel parameterization of orthogonal convolutions that uses the Cayley transform in the Fourier domain. The paper discusses several aspects of the proposed parameterization, including limitations and computational considerations, and showcases it in the important application of adversarial robustness, achieving good results. The reviews are all very positive, so I'm happy to recommend acceptance.

Also, a big shout-out to the reviewers and to the authors for being *outstanding* during the discussion period. The reviewers engaged with the paper to a great depth, and the authors improved the paper considerably as a response. Well done to all of you.
Decision: Accept (Spotlight)