Constructing Orthogonal Convolutions in an Explicit Manner
Authors: Tan Yu
Jun Li
YUNFENG CAI
Ping Li
Venue: ICLR 2022 Poster (2022)

Abstract: Convolutions with orthogonal input-output Jacobian matrix, i.e., orthogonal convolution,  have recently attracted substantial attention.  A convolution layer with an orthogonal Jacobian matrix is 1-Lipschitz  in the  2-norm, making the output robust to the perturbation in input. Meanwhile, an orthogonal Jacobian matrix preserves the gradient norm in back-propagation, which is critical for stable training deep networks. Nevertheless,  existing orthogonal convolutions are burdened by high computational costs for preserving orthogonality.
In this work, we exploit the relation between the singular values of the convolution layer's  Jacobian and the structure of the convolution kernel.  To achieve orthogonality, we explicitly construct the convolution kernel for enforcing all singular values of the convolution layer's Jacobian to be $1$s.   After training,  the explicitly constructed orthogonal (ECO) convolution is constructed only once, and their weights are stored. Then,  in evaluation, we only need to load the stored weights of the trained  ECO convolution, and the computational cost of ECO convolution is the same as the standard dilated convolution. It is more efficient than the recent state-of-the-art approach, skew orthogonal convolution (SOC) in evaluation.    Experiments on CIFAR-10 and CIFAR-100  demonstrate that the proposed ECO convolution is faster than SOC in evaluation while leading to competitive standard and certified robust accuracies. 

Published as a conference paper at ICLR 2022
CONSTRUCTING ORTHOGONAL CONVOLUTIONS IN AN EXPLICIT MANNER
Tan Yu, Jun Li, Yunfeng Cai, Ping Li Cognitive Computing Lab Baidu Research
10900 NE 8th St. Bellevue. Washington 98004, USA (tanyu01, i jun 2, ca yunfeng, 1 piiiipiglll @ba du com
ABSTRACT
Convolutions with orthogonal input-output Jacobian matrix, i.e., orthogonal con- volution, have recently attracted substantial attention. A convolution layer with orthogonal Jacobian matrix is L-Lipschitz in the 2-norm, making the output robust to the perturbation in input. Meanwhile, an orthogonal Jacobian matrix preserves the gradient norm in back-propagation, which critical for stable train- ing deep networks. Nevertheless, existing orthogonal convolutions are burdened by high computational costs for preserving orthogonality. In this work, we exploit the relation between the singular values of the convolution layer's 's Jacobian and the structure of the convolution kernel. To achieve orthogonality, we explicitly construct the convolution kernel for enforcing all singular values of the convolu- tion layer's Jacobian be 1s. After training. the explicitly constructed orthogonal (ECO) convolutions are constructed only once, and their weights are stored. Then, in evaluation, we only need to load the stored weights of the trained ECO convo- lution, and the computational cost of ECO convolution is the same as the standard dilated convolution. It is more efficient than the recent state-of-the-att approach, skew orthogonal convolution (SOC) in evaluation. Experiments CIFAR-10 and CIFAR- demonstrate that the proposed ECO convolution is faster than SOC evaluation while leading competitive standard and certified robust accuracies.
INTRODUCTION
layer with an orthogonal input-output Jacobian matrix 1-Lipschitz in the 2-norm, robust to the perturbation in input. Mcanwhile, it preserves the gradient norm in back-propagating the gradient, which effectively overcomes the gradient explosion and attenuation issues in training deep neural networks. In the past years, many studies have shown that exploiting orthogonality of the Jaco- bian matrix of layers in neural networks can achieve provable robustness to adversarial attacks (Li al., 2019), stabler and faster training (Arjovsky et al., 2016; Xiao al., 2018), and improved generalization (Cogswell et al., 2016; Bansal et al., 2018; Sedghi et al., 2019).
In fully-connected layer y Wx where W Rout XCn is the weight matrix, the layer's input- output Jacobian matrix J äy just W. Thus, preserving the orthogonality of can be accom- plished through imposing the orthogonal constraint on W, which has been extensively studied in previous works (Mhammedi et al., 2017; Cissé et al., 2017; Anil al., 2019). In contrast, in a con- volution layer, the Jacobian matrix is no longer the weight matrix (convolution kernel). Instead, it the cireulant matrix composed of convolution kernel (Karami al., 2019; Sedghi et al., 2019). Thus, generally, simply constructing convolution. Achieving an orthogonal Jacobian matrix in the convolution layer is more challenging than that in fully-connected layer. It is plausibly straightforward expand the convolution kernel to the doubly block circulant Jacobian matrix and impose the orthogonal constraint. But it difficult to construct a Jacobian matrix that is both doubly block-circulant and orthogonal.
2x
orthogonal convolution kernel cannot achieve an orthogonal
Block Convolutional Orthogonal parameterization (BCOP) (Li et al., 2019) is one of the pioneering works for constructing the orthogonal convolution neural networks. It adopts the construction algo- rithm (Xiao et al., 2018) which decomposes 2-D convolution into a stack 1-D convolutions and thise orthogonal transformation. Trockman & Kolter (2021) maps the convolution kemnll

---

Published as a conference paper at ICLR 2022
and the feature tensor into the frequency domain using Fast Fourier Transform (FFT), and achieves the orthogonality of the Jacobian matrix through Cayley transform on the weight matrix in the fre- quency domain. They devise the convolution kernel of the same size the input feature map. which takes more parameters than standard convolution layers with a local reception field. Meanwhile, FFT maps the real-value feature map and the weight matrix into matrices of complex values, in- creasing the computational cost to 4 times its counterpart in the real-value domain. Meanwhile, the Cayley transform requires computing the matrix inverse, which not friendly for GPU computation. Recently, Skew Orthogonal Convolutions (SOC) (Singla & Feizi, 2021b) devises skew-s symmetric filter and exploits matrix exponential (Hoogeboom Jacobian matrix. But SOC is slow in evaluation since it needs to apply convolution filter multi- ple times sequentially on the feature map to obtain the Taylor expansion. Observing the efficiency limitations of the existing methods, in this work, we propose an explicitly constructed orthogonal (ECO) convolution, which is fast in both training and evaluation.
al., 2020) to attain the orthogonality of the
It is well known that the Jacobian matrix of a layer is orthogonal if and only if each of its singular values is Thus we convert the problem of ensuring the orthogonality of the Jacobian matrix into making every singular value 1. Based on the relation between the singular values of the Jacobian matrix for the convolution layer and the weight matrix of the convolution layer discovered by Sedghi al. (2019), we construct the convolution kernel so that it ensures every singular value of the Jacobian matrix to be 1. Compared with the recent state-of-the-art method, SOC (Singla & Feizi, 2021b) implicitly approximating orthogonal convolution by multiple times convolution operations, ours explicitly builds the orthogonal convolution. Thus, we can directly deploy the constructed orthogonal convolution in evaluation, taking the same computational cost as the standard convolution. It is more efficient than SOC with multiple times convolution operations in evaluation. Experiments on CIFARIO and CIFARI00 show that, in evaluation, taking less time, ours achieves competitive standard and robust accuracy compared with SOC.
2 RELATED WORK
Weight orthogonalization. In fully-connected layer, the Jacobian matrix is the weight matrix itself. Thus many efforts are devoted to orthogonalizing the weights. Early works exploit an or- thogonal weight initialization to speed up the training (Saxe al., 2014; Pennington et al., 2017) and build deep neural networks (Xiao et al., 2018). Recently, more efforts are devoted to exploiting the orthogonality in training. Some approaches propose "soft" constraints on the weights. For ex- ample, Bansal et al. (2018); Xiong et al. (2016) introduce mutual coherence and spectral restricted isometry as a regularization on the weight matrix. Parseval Networks (Cissé et al., 2017) adapts a regularizer to encourage the orthogonality of the weight matrices. However, these methods cannot guarantee the exact orthogonality of the weight matrix. Some approaches orthogonalize features during the forward pass. For example, Huang et al. (2018b) extends Batch Normalization (loffe & Szegedy, 2015) with ZCA; Huang et al. (2018a) solves a suboptimization problem to decorre- late features. These methods cannot avoid computationally expensive operations like SVD. Other approuches enforce orthogonality by the Riemannian optimization on the Stiefel manifold. For example, Casado & Murtinez-Rubio (2019) uses Pade approximation as an alternative exponential mapping to update the weight matrix on the Stiefel manifold. Li et al. (2020) uses an iterative Cayley transform to enforce weight matrix orthonormal. Anil et al. (2019) also attains orthogonal weights by orthogonal parameterization based on Björck orthonormalization (Björck & Bowie, 1971). Lastly, some approaches incorporate orthogonal constraint into the network archi- tecture. For example, Mhammedi et al. (2017) builds orthogonal layers in RNNs with householder reflections.
matrix
Orthogonal convolution. In a convolution layer, the Jacobian matrix is no longer the weight matrix. Thus, the lbove-mentionee weight orthogonalization methods cannot be trivially applied in convo- lution layers. Wang et al. (2020); Qi et al. (2020) encourage the orthogonality of the Jacobian matrix of convolution layers through a regularizer, but they cannot achieve the strict orthogonality and can- not attain the provable robustness. Block Convolutional Orthogonal parameterization (BCOP) (Li et al., 2019) is a pioneering work for enforcing the orthogonality of the Jacobian matrix of a convo- lution layer. It conducts parameterization of orthogonal convolutions by adapting the construction algorithm proposed by Xiao et al. (2018). But BCOP is slow in training. Trockman & Kolter (2021) applies the Cayley transform skew-symmetric convolution weight in the Fourier domain that
2

---

Published as a conference paper at ICLR 2022
the convolution recovered from the Fourier domain has orthogonal Jacobian matrix. Though it achieves higher efficiency in some applications than BCOP, is still significantly more costly than standard convolutional layers. Skew Orthogonal Convolution (Singla & Feizi, 2021b) achieves thogonal convolution through Taylor expansion of the matrix exponential. It faster than BCOP in training but slower in evaluation. In contrast, our method is efficient in both training and evaluation. Recently, Su et al. (2021) achieves orthogonal convolutions via paraunitary systems.
PRELIMINARY
Notation. For a matrix M. M[i j] denotes the element in the i-th row and the j-th column, M(i, denotes the i-th row and M[: denotes the j-th column. We the similar notation for indexing tensors. For n E N, [n] denotes the set of n numbers from O to n - 1, that is, {0, 1, We denote the function obtain the singular values by a+)). Let vec(-) denotes the function which unfolds matrix or higher-order tensor into vector. Let wi cxp(2ri/k) where i V-1. Let FA E kxk be matrix for the discrete Fourier transform (DFT) for k-element vectors and each entry of F& is defined F FE(p, q] w
-1
3.1 RELATION BETWEEN THE JACOBIAN MATRIX AND THE WEIGHT MATRIX
We denote the input tensor of convolution layer by X Rxxxx where is the spatial size, and is the number of input channels. We denote the convolution operation on X by conv (X),, where W E B4xxxexe size where k is the size of the reception field and k: is normally smaller than size of the input image, n. In this definition, we set the number of output channels identical to that of input channels. Meanwhile, we set the convolution stride as 1 and adapt the cyclic padding to make the output of the same size as the input.
We denote the output tensor by y E Rxxxxx and each element of y is obtained by [m), yIl, - Σ x + W...g.,
v1, E [c] [n]
rE(c] PE(M
Since the convolution operation is a linear transformation, there exists linear transformation M pnn"exa' exxncc which satisfics:
y = conv conv + vec(Y) = MMee(
(2)
To simplify illustration, W E R is normally expanded into W E Baxxxexe through zero- padding. We term W as the expanded convolution kernel. In W, only k²2²² elements are non-zero. Based on the above definition, we review the following theorem in Sedghi et al. (2019):
Theorem 1 (see Sedghi et al. (2019) Section 2.2). For any expanded convolution kernel W E R.xxxexx, let M is the matrix encoding the linear transformation of a convolution with W. For each p. g E [n] [n], let p(r.)) be the matrix computed by
Vs, [c] x [c],
p(n.0) [s, (F W Wh. s, (/.
(3)
Then
(M)- = U
o(P(x.))).
(4)
pE|n].gE[m]
The above theorem gives the relation between the singular values of the transformation matrix M and the expanded convolution W.
Theorem 2. For any W [B=Xnxxx,, the Jacobian matrix of the convolation layer, J, orthogonal if and only if Vp, q E [n] [n)), each singular value of the matrix p(p.4) is 1.
Proof. A real matrix is orthogonal if and only if each singular value is 1. Meanwhile, the Jacobian @vec(Y))
matrix J
8vec(x) M. Based on Theorem 1, each singular value of M is if and only
Vp, q E [n] [m). each singular value of the matrix (P.2) is 1, thus complete the proof.
3

---

Published as a conference paper at ICLR 2022
3.2 MATRIX ORTHOGONALIZATION
Carley transform. Orthogonal parameterization has been extensively studied in the previous works. Many works (Absil et al., 2008; Helfrich al., 2018; Maduranga al., 2019) utilize Cayley transform on skew-symmetric matrices (A = to obtain the orthogonal weight matrices. Cay- ley transform bijection between skew-symmetric matrices and orthogonal matrices without -1 cigenvalues. Specifically, it maps a skew-symmetric matrix A to an orthogonal matrix Q by
Q = -I- AI [|]++-++ A)-
(5)
Li et al. (2020) proposes an iterative approximation of the Cayley transform for orthogonally- constrained optimizers and achieves higher speed for training CNNs and RNNs.
Matrix exponential. Casado & Martínez-Rubee Rubio (2019) exploits the matrix exponential of the
skew-symmetre matrix for orthogonality. Specifically, if A is a skem-symeetric matrix, exp(A) is orthogonal. SOC (Singla & Feizi, 2021b) approximates exp(A) through Taylor series exp(A) A) R
(A) = EL A' and derives a bound on the approximation error:
||exp(A A) (T(l)l22 |
T!
where || -l1 is the spectral norm, the maximum singular value a matrix. Since the approximation error is bounded by | SOC adopts the spectral normalization A to make | ll small.
Orthogonality of convolution. In a fully-connected layer, its Jacobian matrix is the transpose of the weight matrix. Thus parameterization on the weight matrix through common orthogonal parameterization methods such as Cayley transform or matrix exponential of the skew-symmetric matrix. However, in a convolution layer, the Jacobian matrix is no longer the transpose of the weight matrix; hence we cannot just apply orthogonal parameterization on the weight matrix achieve orthogonality of the Jacobian matrix.
achieve orthogonality of the Jacobian matrix through orthogonal
3.3 LIPSCHITZNESS AND PROVABLY ROBUSTNESS
Lipschitz constant. A function ʃ Rm + R" is L-Lipschitz under the & norm iff [I/(x) f(y)ll2 < L||x - y112, v(x, E Rd x Ih" where L is positive constant. We define the smallest value of L satisfying L-Lipschitz for f as the Lipschitz constant of f. denoted by Lip(f). Given two Lipschitz continuous functions and g. the Lipschitz constant of the composition of them, Lip(f o g). is upper-bounded by the product of the Lipschitz constants of f and (Weaver, 2018):
Lip(f og) g) S Lip(f)
(7)
Thus, given a network n²-)) consisting of L layers, if the Lipschitz constant of each layer is 1, the Lipschitz constant of the whole network, Lip(n) is less than 1.
Provably robustness. Considering a neural network n²-) for c-class classification. Given an input with the ground-truth label y [c], the network generates c-dimensional prediction vector where the i-th item in nxx) denotes the confidence score for the class i. The margin of prediction for by n(.) is defined
nxx) = ...,,.., 8c]
(x) max(0, 8y maxi
As proved by Tsuzuku al. (2018) and Li et al. (2019), for network ni.)) with Lipschitz constant of L, x provably robustly classified by ni()) under perturbation with a fo-m of (,) that is,
V2L
Mn
arg max n(( + 6) = y, V|lo||a <
V2L
METHOD
Based on Theorem 2, achieve an orthogonal Jacobian matrix J for convolution layer, need to ensure that, Vp.g E [n] x [n). each singular value of the matrix p(P.0) is 1. When p(p-9) is real matrix, this condition is equivalent to the orthogonality of ((P-0) To simplify the notation, we assemble the matrices ((P.s) (p, g E [n] x [n]) into a tensor P E |Rexxxex such that Plp, 9, p(P-9), Based on the definition, we rewrite the transformation from W to p(7-0) in Eq. (3) into
Vs, L E [c] [c), Pla 8, F. W (. F
(10)
4

---

Published as a conference paper at ICLR 2022
Since F,, is the full-rank square matrix, the mapping from W to P is invertible. Thus, to achieve an orthogonal Jacobian matrix, we can directly construct orthogonal Plp. 9, :, (p. q E [n] x [rx] using Carley transform matrix exponential of skew-symmetrie matrices (introduced in Section 3.2) to make each singular value of them identical to 1. Then the convolution kernel weight W can be determined uniquely from the P through the inverse transformation in Eq. (10). Since F,, is the Discrete Fourier Transform (DFT) matrix, F. Wis s, f),, in Eq. (10) is equivalent to conduct- ing 2-dimensional DFT on W[i s, t.. Thus, we can recover i, s,t] through the inverse 2 2-dimensional DFT (IDFT2D) on the constructed orthogonal matrix P p,, s... That is,
Wh s, t| = 2D (Pl,, f)), Vs, E [c] x [c].
(11)
Based on Theorem 2, the Jacobian matrix of the convolution layer with the kernel W is orthogonal.
Nevertheless, the above approach has many drawbacks. First of all, for generally constructed P. the recovered expanded convolution kemnel W computed based on the inverse 2-dimensional DFT might contain n² non-zeros elements. It significantly increases the number of parameters in the convolution layer from k2222 to n²c². Meanwhile, the convolution with kernel W has a global reception field, which is also slower than the original convolution kernel with a local reception field. Besides, the above approach needs to compute n²² times matrix orthogonalization (Carley transform matrix exponential) of the input feature tensor, n and the input/out channel number c are not a small value, n² times orthogonalization e e matrices might be computationally expensive.
P(p. :, (p,q
E [n] [n]). Considering the spatial size
Thus, to achieve a high efficient orthogonal convolution, we devise a 2-dimensional periodic P. We set the period as k and assume is divisible by A. Specifically, P satisfies
P q, . Plp + i k q + k, V(p. a] E [A] [4] [..5] E x [n/k].
(12)
We define Po- = P [O:k, 0ck,;, E Rexxxexe, That is, P can be obtained by repeating Po by n/k x n/k times the first two dimensions. It has many benefits by the 2-dimensional periodic configuration. First of all, based on the property of DFT, the convolution kernel Wi:,;, obtained from an inverse 2D DFT on the 2-dimensional periodic :l s, on contains only 122 non-zero elements. That is, the number of non-zero elements in the recovered W is only k2 which is the same as the number of elements in original convolution kernel W with a local reception field of k x k size. Besides, the non-zero elements in W can be efficiently obtained. To be specific, we define Wo E xxxxxxxe obtained from Wol::t,s E IDFTT (Pol:. i, s, t)). Based on the property of DFT (Nussbaumer, 1981), W and Wo have the following relation:
/oll inn jek :. if 1% = and 5% 0,
(13)
Oexe
otherwise.
That is, we can obtain the non-zero elements of W E -Raxx through computing Wo E R taking only 222 times 2D FFT on ex matrices. Since P is periodic along the first two dimensions, to achieve orthogonal Jacobian matrix based Theorem 2, we only need to explicitly construct 222 orthogonal matrices Polp, g, : ((p.g) E [A] x [A:) to ensure that n² matrices Plp. g, i, :] ((p, q) E [n] x [n]) are orthogonal. As the recovered W j.. is non-zero only if 5% g = 0 and 5% n 0.
This property corresponds to the dilated convolution (Yu & Koltun, 2016). Specifically, using the relation between W and Wo in Eq. (13), the following equation holds:
Convw Couvw, (X, dilation =
(14)
That is, we can achieve the orthogonal convolution through a dilated convolution with the kernel Wo and the dilation n/k: Based on above analysis, the process of achieving the orthogonal convolution is decomposed into three steps:
1. Construct the orthogonal matrices Polp, g, :], V)p,g) E [K] X [k].
2. Recover Wol: ;, s, t) from Polis i, s, f] using inverse 2D DFT, V(s,t) E [c] x [c].
3. Conduct the dilated convolution using the recovered kernel Wo and the dilation n/k.
Below introduce the details in these three steps individually.
5

---

Published as a conference paper at ICLR 2022
Orthogonal parameterization for Pulp. i, This step be implemented by any matrix thogonalization approach such as Carley Transform on skem-symmetric matrix or matrix exponen- tial of the skew-symmetric matrix. By default, adopt the Taylor expansion for the exponential of the skew-symmetrie matrix proposed in SOC (Singla & Feizi, 2021b) in this step considering its simplicity and efficiency. To be specific, start from parameter tensor Po R*xxxcxe V (p, g) E [k] x [k], we compute
Polp.g;2,1] t Pulp. :. Polp.a..
T
Polp.g.4.1
Polp.q...1] +
(15)
Recall from Eq. (6) that the approximation error between exp(A) and the Taylor expansion Sa(A), ||exp(A) A) (2))) is bounded by ||AII That is, when ||A||2 < 1, it can achieve a good ap-
proximation. Thus, following SOC (Singla Feizi, 2021b), we conduct spectral normalization on
Polp, ;;:, so that ||exp(Polp. q;;;:]) E Palp.g.n 12 [|Po[ng.:.]]
x
Recover Wu from Po- v(s,t) E [c] x [c]. inverse 2D DFT is on Polss,s, s to obtain Wo
Wols;;,,4 = - & IDFT22 (Pol:,
(16)
As Wo the convolution kernel for the further convolution, make the convolution compatible with mainstream real-value convolutional neural networks, we should keep Wo real. Based on the property of DFT, for inverse 2D discrete Fourier transform, the output Y E RR purely real and only if the input X is conjugate-symmeet
that is, X(i X ()= (k-j)% for each (i,j) E [k] x [k:. Thus, to make Wo real, we need set J. == Pūl(k-i) (k- (k-j)%k.
: for each (i,j) [k] x [k). Since Po is real-value, we just need to set Poli.j.;.) and Pol(k- i)%kk, (k-j)%kk.. identical. Due to the conjugate-symmetry settings, among these x² matrices (Po :1 11 there are only L different matrices. L is (A² + 1)/2 when & is odd and (k² + 4)/2 when & is even. In the implementation, we encode all the information of Po through L e tensor Po. Then build Po from Po by mapping matrix I Rkxk,
Poli,j.4:] = [i..), E [M] [R).
(17)
Algorithm 1: The proposed efficient orthogonal convolution. training. the operations lines 1-14 are involved in orthogonal convolution. In contrast, in evaluation. only the operation in line 14 is conducted, the operations in lines 1-13 have been conducted before evaluation and the obtained W has been stored in the model for further evaluation.
Input: Input tensor X' Ruxaxe where is the number of input channels, the spatial size of the
convolution, k the parameter tensor Po E IR Lxexe (if & is odd, L is k else 1F44 Output: Output tensor y E paxaxe from conducting orthogonal convolution on X.
2
2
for all e [L] do
P Polú.;; -asll-Poliice :
: < SpectralNorm (oll;;;)
Po + ETo Polcodi
end
I ConstructMap(k) % construct the mapping matrix I e I Po = zeros(k, (k,, k, c, Wo zeros(k, k. c,
for all (i.j) E [M] [k] do
Polp, [.: Po i]
10 end
for all (s,t) E [c] do 12 Wol.i,s,t IDFT (Pols,,
end
14 y = Convw, dilatioinn = (Xdiilatio
n/k)
15 return y

---

Published as a conference paper at ICLR 2022
where I is mapping matrix, which maps a pair (i. E [K] x [k] to scalar / E [1, and it satisfies
[[i,j] I[(k- (k-))%A] v(i, j) E [k]] x [k].
(18)
The details of constructing the mapping matrix is provided in Algorithm of Appendix A.
Dilation convolution. In this step, we conduct the standard dilated convolution using the recovered kernel Wo obtained in Eq. (16) with a dilation n/ k on the input X and obtain the output y
We summarize the proposed model in Algorithm 1. In each training iteration, given batch of B samples, the lines 1-13 are only conducted once, and the obtained Wo is shared across B samples. After training, we store the computed Wo in line 12. In evaluation, we load the stored Wu and only compute the operation in line 14, which is just vanilla dilated convolution and thus is very efficient.
In the current configuration of Algorithm 1, set Po Polp. ;. Rexc to be real matrix. In fact, Polp, q, i, can also be complex matrix. To make the output of the proposed orthogonal convolu- tion compatible with existing mainstream real-value neural network, Wol:;;, i, IDFT2D Pol ,., j should be real matrix. That is, we should set Pol:: :, i. to be conjugate symmetric and Poli, j, is unnecessarily real. When considering Po(p, q, :] as a complex matrix, it makes the constructed orthogonal convolution kernel Wo more complete. Meanwhile, it brings more compu- tational cost in training. In Appendix B, we compare with using a complex Polp, q.
IMPLEMENTATION
Spectral normalization. For small approximation error from Taylor expansion, we conduct spectral normalization on Polp, q, ;, to make [|Po[p: q: :f:::]ll S 1. Following Miyato et (2018); Singla & Feizi (2021a:b), we use the power method to estimate the approximated spectral norm and then divide Polp, :, by the estimated spectral norm.
Padding. Following SOC (Singla & Feizi, 2021b), we use cyclic padding to substitute zero- padding since zero-padded orthogonal convolutions must be size 1 (see proof in Appendix D.2 of SOC (Singla & Feizi, 2021b)). To be specific, for dilated convolution of k x l size with a dilation d, we add d(k: 1)/2 paddings on each side in a cyclic manner.
Input and output channels. The proposed orthogonal convolution is devised under the condition that the number of channels in input is equal to that in output, that is, On = Cout = c. When en F Cout, following SOC (Singla & Feizi, 2021b), we additionally conduct the following operations:
1. if Cin > Couts we apply our orthogonal convolution with a kernel size of k: x x Gin X Cins generating the output with en channels. We only select the first Cout channels in the output.
2. if Cin < Cout. we use zero pad the input with Cout - Cin channels. Then we apply our orthogonal convolution with a kernel size of k X Cout Cout-
Strided convolution. Given an input E B a convolution with stride generates the output y E R X Our convolution is designed for I-stride convolution. For a more general s-stride convolution, we decompose it into a down--smpling module and an orthogonal convolution, following BCOP (Li et al., 2019) and SOC (Singla & Feizi, 2021b). Specifically, the down-sampling module adapts the invertible down-sampling (Maduranga et al., 2019), which simply reshapes the input feature map X' from paxxx... to R xem=² The invertible down-sampling decreases the spatial size of the feature map from ls le to k/s k/s and meanwhile strictly preserves the gradient norm. Then we conduct the proposed 1-stride orthogonal convolution on the reshaped X.
1-Lipschitz architecture. Following SOC (Singla Feizi, 2021b), we build a provably 1-Lipschitz network. The details of the architecture are given in Table 1. It consists of L. convolution layers in 5 blocks, and each block contains L/5 layers. By default, we only deploy the proposed ECO convolution in the last three blocks and keep the first two blocks as SOC. Each block consists of two groups of convolutions layers. The first group repeats L/5 - 1 convolutions layers with stride 1, and the second group contains single convolution layer with stride 2. Following SOC, MaxMin activation function (Anil et al., 2019) is added after each convolution layer. It has been implemented in the PaddlePaddt deep learning platform https: psp: //t////www www.:/wwwwpopppoo http://wwwppplllll//o paadlepadddddddleeoeo epaddl e. wrg.cc..
7

---

Published as a conference paper at ICLR 2022
Input
Output
Group
Group 2
Size
Size
Convolution
Repeats
Convolution
Repeats
Block 1
x
12 x 12
conv[3. 32, 1]
(L/5 1)
conv[3, 64, 2]
Block 2
12 x 12
6
conv[3, 64, 1]
(L/5
conv[3, 128, 2]
Block 3
6 x 6
3 x 3
conv[3, 128, 1]
(L/5- 1/5-11
conv[3, 256, 2]
1
Block 4
3
1 x 1
conv[3, 256, 1]
(L/5- conv[3, 512, 3]
1
Block 5
1 1
1
conv[l, 512, 1]
(L/5- conv [1, 1024, 1]
1
The configurations of the provably 1-Lipschitz architecture with L convolution layers. It consists of blocks. Each block contains two groups convolution layers. The first group contains (L/5 1) convolution layers of stride 1, and the second group contains single convolution layer of stride 2. The output size decreases to 1/2 after each block. conv [k. s] denotes the convolution with the kernel of spatial size k x k output channels stride The dilation of convolution layer n/k where n is the spatial size of the input, and is the spatial size of the convolution kernel.
Table 1:
EXPERIMENTS
Settings. The training is conducted single NVIDIA V100 GPU with 32G memory. Follow- ing Singla & Feizi (2021b). the training takes 200 epochs. The initial learning rate 0.1 when the number of convolution layers is larger than 25 and 0.05 otherwise, and decreases by factor of 0.1 at the 50th and the 150th epoch. We set the weight decay as 5e-4.
Evaluation metrics. We evaluate the performance proposed orthogonal convolution by two met- rics: standard recognition accuracy and the robust recognition accuracy. The standard recognition accuracy is the same that used in classic image classification. In contrast, the robust recognition accuracy is the accuracy under an le perturbation. As shown in Section 3.3, L-Lipschitz network has the robustness certificate when the f--ormm perturbation e is less than M,) /2.. Thus, for 1-Lipschitz we built based on the proposed ECO convolution has the robustness certificate as
CIFARIO
CIFARIO0
Conv. Type
Time per Epoch (s)
Model
Standard
Robust
Standard
Robust
Accuracy
Accuracy
Accuracy
Accuracy
ВCOP
70.48%
51.11%
39.19%
24.54%
49.6
LipConvnet-5
SOC
71.31%
52.11%
38.42%
23.68%
18.1
Ours
71.69%
52.36%
38.68%
23.86%
18.8
BCOP
70.79%
52.68%
39.28 29.29%
24.99%
73.0
LipConvnet-10
SOC
72.12%
54.72%
39.13%
25.01%
27.9
Ours
72.15%
54.57%
39.64%
24.83%
29.3
BCOP
70.48%
51.87%
37.93%
23.94%
86.2
LipConvnet-15
SOC
72.30%
55.34%
39.26%
24.76%
33.9
Ours
72.87%
55.20%
39 49.43%
24.74%
40.3
BCOP
69.99%
51.96%
36.37%
22.90%
116.8
LipConvnet-20
SOC
72.23%
55.45%
39.24%
25.29%
39.2
Ours
72.52%
55.41%
40.03%
25.36%
44.9
BCOP
68.84%
50.41%
33.04%
19.72%
138.5
LipConvnet-25
SOC
72.30%
55.34%
38.77%
24.05%
46.3
Ours
72.42%
55.32%
38.32%
24.04%
49.2
BCOP
69.77%
51.26%
30.95%
18.56%
150.2
LipConvnet-30
SOC
72.80%
55.71%
39.55%
25.42%
54.9
Ours
72.48%
55.46%
39.18%
24.41%
57.7
BCOP
68.61%
49.56%
27.75%
13.73%
166.6
LipConvnet-35
SOC
72.89%
55.71%
38.12%
24.32%
60.6
Ours
71.59%
54.76%
38.60%
24.14%
64.0
BCOP
67.64%
48.49%
27.09%
13.71%
180.3
LipConvnet-40
SOC
72.10%
55.33%
37.98%
23.63%
67.3
Ours
72.43%
56.08%
38. 24%
24.35%
70.9
Table 2: Comparisons among BCOP (Li et al., 2019), SOC (Singla Feizi, 2021b) and our ECO convolution on standard accuracy, robust accuracy, the time cost per epoch in training.

---

Published as a conference paper at ICLR 2022
(x,x)/V2 Following Li al. (2019) and Singla & Feizi (2021b), when testing the robust accuracy, we set the default norm of perturbation, e, as 36/255. In this case, the robust accuracy is the ratio of samples satisfyingMM,xx))) (x)/ 2 36/255.
Standard and robust recognition accuracy. Table compares the recognition accuracy of the pro- posed ECO convolution with BCOP (Li et al., 2019) and SOC (Singla & Feizi, 2021 on CIFARIO and CIFARIOG 100 datasets. As can observe from the table that our ECO convolution achieves competitive performance compared with BCOP and SOC in both standard and robust recognition accuracy. Specifically, on CIFAR-IO and CIFAR-100. when the number of convolution layers, L, is 5 or 40, ours outperforms both SOC and BCOP in standard and robust recognition accuracy.
A Ablaioon study on the dilated convolution. The dilation the proposed ECO convolution is n/k where n is the spatial size of the feature map and k is the spatial size of the convolution kernel. In an early convolution block, the feature map of large size, and thus the dilation of the convolution is large. We discover that the large dilation in early blocks deteriorate the recognition performance. We conduct an ablation study on the dilated convolution by fixing the first blocks as SOC and only use our SOC in the last 5 5 blocks in LipConvnet-5. As shown in Table 3, when we deploy our ECO convolution is the first one or two convolution blocks, the performance becomes worse considerably. Thus, only apply our ECO convolution in the last three convolution blocks, by default.
0
5
IO Standard
67.88%
70.97%
71.69%
71.64%
71.54%
71.31%
CIFARIO Robust
48.83%
51.66%
52.36%
52.55%
52.08%
52.11
CIFAR 10O Standard
31.35%
38.34%
38.68%
38.81%
38.82%
38.42%
CIFAR1ON 100 Robust
21.60%
23.40%
23.86%
24.02%
38.85%
23.68%
Table 3: Ablation on implementing the first blocks by SOC and the last I blocks by our ECO convolution. We use LipConvnet-5 model.
Training and evaluation time. As shown in the last column of Table 2, SOC is slightly more efficient than ECO convolution in training. It is because the dilation convolution in our ECO adds more padding, making the input feature map larger than that SOC. Meanwhile, as shown in Table 4, our ECO convolution is faster than SOC in evaluation. It is due that have already constructed the ECO convolution before evaluation. Thus, in evaluation, the computational cost of ECO convolution is the same as standard convolution. In contrast, SOC needs to take T times convolution operations per convolution layer, taking 7 times computational cost as standard training and T 10 in evaluation.
convolution. By default, SOC sets T
Model
LC-5
LC-10
LC-15
LC-20
LC-25
LC-30
LC-35
LC-40
SOC
0.162s
0.276s
0.373s
0.480s
0.587s
0.693s
0.774s
01.900s
ECO
0.106s
0.108s
0.116s
0.124s
0.130s
0.135s
0.142s
0.147s
Table 4: Comparisons between SOC (Singla & Feizi, 2021b) and our ECO convolution on the evaluation time on the third convolution block. LC denotes LipConvnet. In evaluation, set the batch size as 128 and the evaluation is conducted on a single V100 GPU.
7 CONCLUSION
This work investigates building the convolution layer with an orthogonal Jacobian matrix, which is 1-Lipschitz in the 2-norm and preserves the gradient. By exploiting the relation between the convolution kernel and the Jacobian matrix, we explicitly construct the convolution kernel to achieve the orthogonal convolution. The explicitly constructed orthogonal convolution (ECO) takes the exact computational cost as a standard dilated convolution in evaluation, which is more efficient than the existing state-of-the of-the-art method, SOC, approximating the orthogonal convolution through multiple times convolution operations. Our experiments on CIFAR- 10 and CIFAR- 100 show that our ECO achieves competitive standard and robust accuracy as SOC using much less evaluation time.

---

Published as a conference paper at ICLR 2022
REFERENCES
Pierre-Antoine Absil, Robert E. Mahony, and Rodolphe Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, 2008.
Cem Anil, James Lucas, and Roger B. Grosse Sorting out lipschitz function approximation. In Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 291-301, Long Beach, CA, 2019.
Martín Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks. In Proceedings of the 33nd International Conference on Machine Learning (ICML), pp. 1120-1128, New York City, NY, 2016.
Nitin Bansal, Xiaohan Chen, and Zhangyang Wang. Can we gain more from orthogonality regular- izations training deep cnns? In Advances in Neural Information Processing Systems (NeurIPS), pp. 4266 4276, Montréal, Canada, 2018.
Åke Björck and Clazett Bowie. An iterative algorithm for computing the best estimate of an orthog- onal matrix. SIAM Journal on Numerical Analysis, 8(2):358-36) 1971.
Mario Lezcano Casado and David Martinez-Rubio. Cheap orthogonal constraints in neural net- works: A simple parametrization of the orthogonal and unitary group. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 3794-3803, Long Beach, CA. 2019.
Moustapha Cissé, Piotr Bojanowski, Edouard Grave, Yann N. Dauphin, and Nicolas Usunier. Par- seval networks: Improving robustness adversarial examples. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning (ICML), pp- 854-863, Sydney, Australia, 2017.
Michael Cogswell, Faruk Ahmed, Ross B. Girshick, Larry Zitnick, and Dhruv Batra. Reducing over- fitting in deep networks by decorrelating representations. Proceedings of the 4th International Conference on Learning Representations (ICLR), San Juan, Puerto Rico, 2016.
Kyle Helfrich, Devin Willmott, and Qiang Ye. Orthogonal recurrent neural networks with scaled cayley transform. In Proceedings of the 35th International Conference on Machine Learning (ICML), pp. 1974-1983, Stockholmsmässan, Stockholm, Sweden, 2018
Emiel Hoogeboom, Victor Garcia Satorras, Jakub M. Tomezak, and Max Welling, The convolu- tion exponential and generalized sylvester flows. Advances in Neural Information Processing Systems (NeurIPS), virtual, 2020.
Lei Huang, Xianglong Liu, Bo Lang, Adams Wei Yu, Yongliang Wang, and Bo Li. Orthogonal weight normalization: Solution to optimization over multiple dependent stiefel manifolds in deep neural networks. Proceedings of the Thirty-Second Second AAAI Conference on Artificial Intelligence (AAAI), pp. 3271-3278, New Orleans, LA, 2018a.
Lei Huang, Dawei Yang, Bo Lang, and Jia Deng. Decorrelated batch normalization. In Proceedings of the 2018 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 791-800, Salt Lake City, UT, 2018b.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proceedings of the 32nd International Conference on Machine Learning (ICML), pp. 448-456 Lille, France, 2015.
Mahdi Karami, Dale Schuurmans, Jascha Sohl-Dickstein, Laurent Dinh, and Daniel Duckworth. Invertible convolutional flow. In Advances in Neural Information Processing Systems (NeurIPS), pp. 5636-5644, Vancouver, Canada, 2019.
Jun Li, Fuxin Li. and Sinisa Todorovic. Efficient riemannian optimization the stiefel manifold via the cayley transform. In Proceedings of the 8th International Conference on Learning Repre- sentations (ICLR), Addis Ababa, Ethiopia, 2020.
10

---

Published as a conference paper at ICLR 2022
Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger B. Grosse, and Honn-Ke Jacobsen. Preventing gradient attenuation in lipschitz constrained convolutional networks. In Advances in Neural Information Processing Systems (NeurIPS). pp. 55364-15376 Vancouver, Canada, 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In Proceedings of the 6th Interna- lional Conference on Learning Representations (ICLR), Vancouver, Canada, 2018.
Kehelwala D. G. Maduranga, Kyle E. Helfrich, and Qiang Ye. Complex unitary recurrent neural networks using scaled cayley transform. In Proceedings of the Thirty-Thirl AAAI Conference on Artificial Intelligence (AAAI), pp. 0228-4535, Honolulu, HI, 2019.
Zakaria Mhammedi, Andrew D. Hellicar, Ashfaqur Rahman, and James Bailey, Efficient orthogonal parametrisation of recurrent neural networks using householder reflections. In Proceedings of the 34th International Conference on Machine Learning (ICML), pp. 2401-2409 Sydney, Australia, 2017.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. Proceedings of the 6th International Conference on Learning Representations (ICLR), Vancouver, Canada, 2018.
Henri J Nussbaumer. The fast fourier transform. In Fast Fourier Transform and Convolution Algo- rithms, pp. 80-111. Springer, 1981.
Jeffrey Pennington, Samuel S. Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice. In Advances in Neural Information Processing Systems (NIPS), pp. 4785-4795, Long Beach, CA, 2017.
Haozhi Qi, Chong You, Xiaolong Wang. Yi Ma, and Jitendra Malik. Deep isometric learning for visual recognition. In Proceedings of the 37th International Conference on Machine Learning (ICML). pp. 7824-7835, Virtual Event, 2020.
Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynam- ics of learning in deep linear neural networks. In Proceedings of the 2nd International Conference on Learning Representations (ICLR), Banff, Canada, 2014.
Hanie Sedghi, Vineet Gupta, and Philip M. Long. The singular values of convolutional layers. In Proceedings of the 7th International Conference on Learning Representations (ICLR), New Orleans, LA, 2019.
Sahil Singla and Soheil Feizi. Fantastic four: Differentiable and efficient bounds on singular values of convolution layers. In Proceedings of the 9th International Conference on Learning Represen- tations (ICLR), Virtual Event, 2021a.
Sahil Singla and Soheil Feizi. Skew orthogonal convolutions. In Proceedings of the 38th Interna- tional Conference on Machine Learning (ICML), pp- 9766, Virtual Event, 2021b.
Jiahao Su, Wonmin Byeon, and Furong Huang. Scaling-up diverse orthogonal convolutional net- works with paraunitary framework. arXiv preprint arXiv:2/06.09/21, 2021.
Asher Trockman and J. Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. In Proceedings of the 9th International Conference on Learning Representations (ICLR), Virtual Event, Austria, 2021.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Sopschitz-marghh training: Scalable certifi- cation of perturbation invariance for deep neural networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 6542-6551, Montréal, Canada, 2018
Jiayun Wang. Yubei Chen, Rudrasis Chakraborty, and Stella X. Yu. Orthogonal convolutional neural networks. In Proceedings of the 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 11502-11512, Seattle, WA, 2020.
Nik Weaver. Lipschitz algebras. World Scientifie, 2018.
11

---

Published as a conference paper at ICLR 2022
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel S. Schoenholz, and Jeffrey Penning- ton. Dynamical isometry and a mean field theory of cmns: How to train 10, 000-layer vanilla convolutional neural networks. In Proceedings of the 35th International Conference on Machine Learning (ICML), pp. 5389-5398, Stockholmsmåssan, Stockholm, Sweden, 2018.
Wei Xiong, Bo Du, Lefei Zhang, Ruimin Hu, and Dacheng Tao. Regularizing deep convolutional neural networks with structured decorrelation constraint. In Proceedings of the IEEE 16th International Conference on Data Mining (ICDM), pp. 519-528, Barcelona, Spain, 2016.
Fisher Yu and Vladlen Koltun. Multi-scale context aggregation by dilated convolutions. In Proceed- ings of the 4th International Conference on Learning Representations (ICLR), San Juan, Puerto Rico, 2016.
12

---

Published as a conference paper at ICLR 2022
A CONSTRUCTING THE MAPPING MATRIX I
In Algorithm 2, we give the details of constructing the mapping matrix I.
Algorithm 2: Constructing the mapping matrix
Input: The spatial size of the convolution kernel, k. Output: The mapping matrix
I ze)
count = 0:
for all (i. E [k] [c] do
I 8) 8)k, (k- 1)%k = then
[[ count;
count = count + 1;
end else
[[, = [ 1)%k, (N: 5]%A];
end
end
12 return I
B COMPARISONS WITH THE COMPLEX SETTINGS
As we mentioned in Section 4, obtain real-value convolution kernel Wo. the entries in Po are unnecessarily real. We compare the performance when Po is constrained to be real as Algorithm and that when Po is complex tensor. As shown in Table 5, CIFAR-I0 benchmark, using complex Po. generally, it performs slightly better than its real counterpart on both standard accuracy and robust accuracy. The better performance is attributed construct more complete orthogonal convolution. It is worth noting that the computational cost of multiplication between complex matrices is four times that between real matrices of the same sizes. But the complex Po is only used for constructing the real orthogonal kernel Wo- After kernel construction, the computation cost of convolution is the same for the layer with complex Po and that with real Po. Thus, as shown in Table 5, the training time per epoch when using complex o is around times that using real Po. In evaluation, since we have constructed the real Wo from real or complex Po before evaluation, the computational cost is the same no matter Po is complex and real.
the fact that the complex setting can
Standard Accuracy
Robust
Accuracy
Training Time
Model LC-10
LC-15
LC-10
LC-15
LC-10
LC-15
Real 72.15%
72.87%
54.57%
55.20%
40.3
44.9
Complex 72.40%
72.98%
54.60%
55.53%
78.0
81.8
Table 5: Comparisons between the real and complex Po on CIFAR-10 dataset. I.C. is the abbrevia- tion for LipConvnet.
C COMPARISONS WITH THE STANDARD CONVOLUTION
Here, we compare the proposed orthogonal convolution with the standard convolution without or- thogonal constraint. To make a fair comparison, only replace the orthogonal convolution layers of LipConvnet-5 by the standard convolution and keep the other layers unfixed. Since the network built upon the standard convolution cannot preserve the I-Lipschitz property, cannot directly obtain the robust accuracy based on M,, as the original LipConvnet-S network. Thus, we utilize Projected Gradient Descent (PGD) attack (Madry et al., 2018) to obtain the robust accuracy upper
13

---

Published as a conference paper at ICLR 2022
CIFARIO
CIFARI00
Standard Accuracy
Robust Accuracy
Standard
Robust
Accuracy
Accuracy
Standard ECO
75. 75.21%
9.63%
45.62% 38.42%
7.31%
71.69%
52.36%
23.68%
Table 6: Comparisons with the standard convolution.
36 The results shown in Table 6. As bound under the distortion with the &z norm less than 255 shown in the table, on both CIFAR10 10 and CIFAR1O datasets, the network based on the standard con- volution achieves higher standard accuracy than the network based on our ECO convolution. In the meanwhile, ours achieves higher robust accuracy on both datasets under the same scale of distortion.
D TRUNCATED TAYLOR EXPANSION
Note that, the exact matrix exponential (Casado & Martínez-Rubio, 2019) exp( A) relies on singular value decomposition (SVD), which friendly for GPU computing platform. Thus, we adopt the truncated Taylor Expansion (Singla & Feizi, 2021b). (A) = Σ A' to approximate the exact a matrix exponential exp(A). The truncation error R = (A) Sy (A) satisfies
A T'
|||2 = (A) Sy(A))l
(19)
Below first compare the time cost in GPU platform using the exact matrix exponential exp(A)
and that based on the truncated Taylor Expansion Sy (A). To be specific, we implement exp(A simply based on the torch.matrix exp. We measure the time cost GPU using the function torch.cuda. Event and we set 7 10 in truncated Taylor Expansion (A). As shown in Table 7, the latency based on the truncated Taylor Expansion is significantly less than that based the exact matrix exponential.
Exact
Truncated
12.8ms
2.5ms
Table The latency of the exact matrix exponential and the truncated Taylor Expansion in a layer.
Then we show the scale of the average factual truncated error R. with respect to T. It is based on the trained LipConvnet-5 network built upon the proposed ECO convolution. By default, we set T 5 in training and T 10 in testing. As shown in Table 8, the scale of the truncation error relatively small when T is or 10. Meanwhile, we also show the influence the truncation error on the orthogonality of the convolution. Following Trockman & Kolter (2021), measure the orthogonality of convolution layer through [|veo(conv(2))]] 1, and a strict orthogonal convolution []voo(2)]l2
layer should satisfy
veo(conv(()))
1
(20)
[(ve(( (2)()
We estimate the deviation of the proposed ECO convolution from the strict orthogonal convolution through this measurement. As shown in Table 8, when is 5 or 10, the deviation of our ECO convolution from the strict orthogonal convolution is relative marginal.
2
3
5
10
R
0.48
0.16
0.04
0.008
0.001
0.0001
Vvee/oon/ X 2
0.12
0.019
0.0038
0.0004
0.0000
0.0000
|voc (x) lIa
Table 8: The scale of the average factual truncated error.
14


Reviews:
[{"review_id": "fxIarJLtMor", "reviewer": "Reviewer_6wTV", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Pro:\nThe authors propose a theoretically-motivated way of constructing orthogonal convolutions that achieves good robust performance on several benchmarks.\n\nIt has a big advantage on the testing speed over the previous state-of-the-art, SOC. I think this is an important step in this research direction.\n\nCons:\nThe proposed method is still limited to the 1-Lipschitz architecture. What is the challenge to extend the proposed method to more advanced architectures?\n\nComments:\n\nIn my opinion, it will be helpful to have another entry showing how ordinary convolution performs in table 2 and table 4. It may happen that the ordinary convolution will have higher standard accuracy, but by showing they are not robust at all, the advantage of the proposed method will be further highlighted.\n\nAnother line of enforcing orthogonal constraint in convolutional neural networks should also be discussed:\n[1] orthogonal convolutional neural networks. CVPR 2020\n[2] deep isometric learning for visual recognition. ICML 2020.", "summary_of_the_paper": "This paper studies how to construct orthogonal convolutional networks in an efficient way. To this end, this paper builds the connection between the DFT-transformed kernel with the common dilated convolution. During training, the forward pass can be done by a sequence of inverse DFT and dilated convolution. During testing, all the convolution kernels only need to be transformed once so that evaluation time is significantly reduced.", "summary_of_the_review": "I think this paper contributes a new idea in this field.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "enk5Fngf8e", "reviewer": "Reviewer_YtM2", "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": "Technical comments:\n\n- It is not clear to me why one needs to consider the *expanded* convolution kernel. In principle, the orthogonality of a convolutional kernel is independent of the size of the feature map that it is applied to. However, the construction of orthogonal convolution in the paper requires one to first expand the kernel to the size of the feature map that it is applied to, by padding zeros. My understanding that this expansion causes a lot of trouble that requires some intricate fixes, such as Eq. (12), (13), and (14), that greatly complicates the method.\n\n- Can the authors comment on the completeness of their parameterization for orthogonal convolution? Namely, does the parameterization contain the set of all orthogonal convolution, or just a subset? \n\n- In Eq. (3), it seems that $F_k$ should be $F_n$ since $\\mathcal{W}$ is of size $n \\times n$.\n\nExperiments:\n\n- Table 2: It could be good to add a baseline where no orthogonality is enforced. \n\n- Can the authors comment on why ECO produces significantly better performance than SOC, in Table 2? If both of them enforce strict orthogonality of convolution then shouldn't they be giving exactly the same accuracy (in principle)? BCOP is inferior probably because it only parameterizes a subset of all orthogonal convolution (or maybe the authors have other explanations?)\n\n- The caption of Table 3 says that it reports evaluation time, while the text says that it is the training time. Am I missing anything here?\n\n- The experiments only contain results with LipConvnet which are perhaps non-standard and have far worse performance than standard networks, such as ResNet. This makes it less convincing as to how important the method is for practice. Are there any results on standard networks? \n\nClarity:\n\n- \"simply constructing an orthogonal convolution kernel cannot achieve an orthogonal convolution\": Not sure what this mean. How is \"orthogonal convolution kernel\" different from \"orthogonal convolution\"? Actually, what do those two terms mean, exactly? \n\nOther comments:\n\n- While the paper argues that previous methods for enforcing orthogonality in convolutions, such as Trockman & Kolter '21 and Singla & Feizi '21, have computational issues, it fails to mention that there are earlier work [a] as well as more recent work [b] that are computationally more efficient. \n\n[a] Deep Isometric Learning for Visual Recognition, ICML 2020\n[b] Scaling-up Diverse Orthogonal Convolutional Networks with a Paraunitary Framework, 2021", "summary_of_the_paper": "This paper presents a method for enforcing strict orthogonality for convolutional layers. The method is based on considering the spectral domain, where the orthogonality of the 4D conv kernel (in spatial domain) is characterized as the orthogonality of 2D matrices, for which orthogonality can be enforced by existing techniques such as Carley transform. It is shown in experiments that this method is significantly faster than the recent skew orthogonal convolution (at ICML'21) method.", "summary_of_the_review": "This is a nicely written paper for enforcing orthogonality of convolutional kernels with a computationally efficient method. However, I find the experiments to be shallow relative to related works, and cannot fully justify the practical value of the proposed method. I also have some minor concerns on the technical approach, that hopefully can be clarified during rebuttal. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "ENmbTsrbmsj", "reviewer": "Reviewer_mniG", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "Overall, I think the idea in the paper is novel and elegant. However, there are a few aspects in the current draft that are not carefully developed/explained.\n\n1) The limitations of the proposed method. a) In previous approaches (BCOP, Cayley, SOC), the convolution kernel is orthogonal for ANY resolution. In contrast, the convolution kernel is orthogonal ONLY IF the resolution equals the product of filter size and dilation. b) As a result, the method limits the flexibilities of orthogonal convolutions --- for example, the method can not construct orthogonal convolutions for features with a prime-number resolution. While orthogonal convolutions are rarely used for different resolutions or prime-number resolution, I think the authors shall discuss these two limitations explicitly.\n\n2) \bReal frequency domain. The matrix P is the Fourier transform of the convolution kernel, which generally is complex-valued. Restricting to the real-valued matrix has two drawbacks. a) The filters must be even, i.e., the method cannot construct orthogonal convolutions that are asymmetric. b) The space of real orthogonal matrices is disconnected, and the matrix exponential can only cover one component SO(c). I don't see why the authors do not adopt unitary matrices, which do not suffer from these two drawbacks.\n\n3) Computation of matrix exponential. The paper uses truncated Taylor expansion instead of other more computation/memory efficient methods --- The SOC paper adopts truncated Taylor series because there is no efficient algorithm when A is a convolution instead of a matrix. Indeed, a cited article (Casado & Martínez-Rubio 2019) provides an exact and efficient algorithm to parameterize orthogonal/unitary matrices. However, using the current method, the authors will have to analyze how truncation error affects the exact orthogonality of the convolution kernel.\n\n4) Other minor issues. a) At the end of the second paragraph of the Introduction (Section 1), the authors write \"Straightforwardly, we can ...\". This is not correct. Even one can expand the kernel to a Jacobian matrix, it is not straightforward to construct a matrix that is both block-Toeplitz and orthogonal. b) In the second paragraph of the Implementation (Section 5), I think the padding will be proportional to the product of filter size and dilation instead of addition. c) The experiments only repeat the ones in SOC paper, which do not fully demonstrate the proposed method in other settings (e.g., Wasserstein estimation).", "summary_of_the_paper": "The paper proposes an economical method to construct orthogonal convolutions using dilated convolutions.", "summary_of_the_review": "In summary, I believe the idea in the paper is novel and promising. However, the authors have not thoroughly/carefully developed the picture (as explained above). Therefore, I suggest rejecting the paper for now --- but I look forward to upcoming revisions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4Yqiz6ZsJDV", "reviewer": "Reviewer_htXp", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Benefits\n-----------\n    \n- They show the link between singular vectors of the Jacobian of the convolutional layer and the convolutional kernel structure.\n- The evaluation time of the proposed convolutional layer coincides with the evaluation time of the standard layer.\n- They clearly describe how existing relative approaches differ from the proposed one.\n- They obtain analytical formulae that yield a nice three-step approach to construct orthogonal convolution.\n    \nDrawbacks\n--------------- \n- Longer training time for proposed ECO (Table 2)\n- Simple datasets \n- No black-box attacks\n    \n    \nSuggestions\n-----------------\n- Add schematic visualization for forward and backward pass.\n- Demonstrate results for more complex datasets (e.g. ImageNet)\n- Add loss curves to see if there are effects aka standard&robust accuracy trade-off (similar to what is happening during adversarial learning)", "summary_of_the_paper": "Summarizing the paper\n-------------------------------\n    \nThe paper proposes a method to construct a  convolutional layer with the orthogonal Jacobian matrix. Such a layer is 1-Lipschits: this property is an important one for building robust neural networks.\nThe authors conduct experiments on classification tasks using CIFAR10/CIFAR100 datasets. They report standard and robust accuracies, training, and evaluation time. They claim the proposed method outperforms existing state-of-the-art approaches.\n    \n", "summary_of_the_review": "Recommendation \n------------------------\nI recommend accepting the paper because the proposed method is new, addresses an important problem and empirically demonstrates its benefits.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the problem of how to construct orthogonal convolutional layers. It is known that a convolution layer is orthogonal if and only if its filters are obtained by certain Fourier operations on an orthogonal matrix. Previous work proposes to learn this orthogonal matrix, parameterized either through Cayley transform, or the exponential of a skew-symmetric matrix. This requires spectral computations with large matrices. The idea of this submission is to reduce the computational cost associated with this construction by letting this “core” matrix P be a periodic extension of a smaller orthogonal matrix P_0. Because of cancelations in the inverse DFT, this leads to sparse filters which can be implemented by dilated convolution. 

The review process generated a very detailed discussion between authors and reviewers, with several important clarifications. Reviewers generally found that the paper contributes a novel construction of orthogonal convolution layers, with better efficiency at test time. Remaining concerns held by some reviewers include the limitations vis previous constructions of orthogonal convolution layers, questions about the efficacy of use of a Taylor expansion, certain minor limitations of the experiments. After detailed interaction with the authors, the reviewers converged to a decision to accept, motivated by the novelties of the construction and its advantages for test-time efficiency.
Decision: Accept (Poster)