Introduction

In the past decade, Convolutional Neural Networks (ConvNets) have achieved phenomenal success in many machine learning and computer vision applications [1][2][3][4][5][6][7]. Normalization is one of the most important components of modern network architectures [8]. Early normalization techniques, such as batch normalization (BatchNorm) [4], are cornerstones for effective training of models beyond a few layers. Since then, the values of normalization for optimization and learning is extensively studied, and many normalization techniques, such as layer normalization [9], instance normalization [10], and group normalization [11] are proposed. Many of such normalization techniques are based on estimating certain statistics of neuron inputs from training data. However, precise estimations of the statistics may not always be possible. For example, BatchNorm becomes ineffective when the batch size is small [12], or batch samples are statistically dependent [13].

Weight normalization [14] is a powerful alternative to BatchNorm that improves the conditioning of neural network training without the need to estimate statistics from neuron inputs. Weight normalization operates by either reparameterizing or regularizing the network weights so that all the weights have unit Euclidean norm. Since then, various forms of normalization for network weights are proposed and become critical for many tasks such as training Generative Adversarial Networks (GANs) [15] and obtaining robustness to input perturbations [16,17]. One of the most popular forms of weight normalization is enforcing orthogonality, which has drawn attention from a diverse range of research topics. The idea is that weights in each layer should be orthogonal and energy-preserving. Orthogonality is argued to play a central role for training ultra-deep models [18][19][20][21][22], optimizing recurrent models [23][24][25][26], improving generalization [27], obtaining robustness [28,29], learning disentangled features [30,31], improving the quality of GANs [32,33], learning low-dimensional embedding [34], etc. Exploiting convolution structures for normalization. Our work is motivated by the pivotal role of weight normalization in deep learning. In the context of ConvNets, the network weights are multi-dimensional (e.g., 4-dimensional for a 2D ConvNet) convolutional kernels. A vast majority of existing literature [27,28,[35][36][37][38][39] imposes orthogonal weight regularization for ConvNets by treating multi-dimensional convolutional kernels as 2D matrices (e.g., by flattening certain dimensions) and imposing orthogonality of the matrix. However, this choice ignores the translationinvariance properties of convolutional operators and, as shown in [22], does not guarantee energy preservation. On the other hand, these methods often involve dealing with matrix inversions that are computationally expensive for deep and highly overparameterized networks.

In contrast, in this work we introduce a new normalization method dedicated to ConvNets, which explicitly exploits translation-invariance properties of convolutional operators. Therefore, we term our method as Convolutional Normalization (ConvNorm). We normalize each output channel for each layer of ConvNets, similar to recent preconditioning methods for convolutional sparse coding [40]. The ConvNorm can be viewed as a reparameterization approach for the kernels, that actually it normalizes the weight of each channel to be tight frame.foot_0 While extra mathematical hassles do exist in incorporating translation-invariance properties, and it turns out to be a blessing, rather than a curse, in terms of computation, as it allows us to carry out the inversion operation in our ConvNorm via fast Fourier transform (FFT) in the frequency domain, for which the computation complexity can be significantly reduced.

Highlights of our method. In summary, for ConvNets our approach enjoys several clear advantages over classical normalization methods [41][42][43], that we list below:

• Easy to implement. In contrast to weight regularization methods that often require hyperparameter tuning and heavy computation [41,43], the ConvNorm has no parameter to tune and is efficient to compute. Moreover, the ConvNorm can serve as a simple plug-and-play module that can be conveniently incorporated into training almost any ConvNets. [40,46], our high-level intuition is that the ConvNorm improves the optimization landscape that optimization algorithms converge faster to the desired solutions.

Related work. Besides our work, a few very recent work also exploits the translation-invariance for designing the normalization techniques of ConvNets. We summarize and explain the difference with our method below.

• The work [22,43] derived a similar notion of orthogonality for convolutional kernels, and adopted a penalty based method to enforce orthogonality for network weights. These penalty methods often require careful tuning of the strength of the penalty on a case-by-case basis. In contrast, our method is parameter-free and thus easier to use. Our method also shows better empirical performance in terms of robustness. • Very recent work by [29] presented a method to enforce strict orthogonality of convolutional weights by using Cayley transform. Like our approach, a sub-step of their method utilizes the idea of performing the computation in the Fourier domain. However, as they normalize the whole unstructured weight matrix, computing expensive matrix inversion is inevitable, so that their running time and memory consumption is prohibitive for large networks. 3 In contrast, our method is "orthogonalizing" the weight of each channel instead of the whole layer, so that we can exploit the convolutional structure to avoid expensive matrix inversion with a much lower computational burden. In the meanwhile, we show that this channel-wise normalization can still improve layer-wise Lipschitz condition. Organizations. The rest of our paper is organized as follows. In Section 2, we introduce the basic notations and provide a brief overview of ConvNets. In Section 3, we introduce the design of the proposed ConvNorm and discuss the key intuitions and advantages. In Section 4, we perform extensive experiments on various applications verifying the effectiveness of the proposed method. Finally, we conclude and point to some interesting future directions in Section 5. To streamline our presentation, some technical details are deferred to the Appendices.

Preliminary

Review of deep networks. A deep network is essentially a nonlinear mapping f (•) : x → y, which can be modeled by a composition of a series of simple maps:

where every f (•) (1 ≤ ≤ L) is called one "layer". Each layer is composed of a linear transform, followed by a simple nonlinear activation function ϕ(•).foot_2 More precisely, a basic deep network of L layers can be defined recursively by interleaving linear and nonlinear activation layers as

for = 0, 1, . . . , L -1, with z 0 = x. Here A (•) denotes the linear transform and will be described in detail soon. For convenience, let us use θ to denote all network parameters in A (•)

L-1 =0 . The goal of deep learning is to fit the observation y with the output f (x, θ) for any sample x from a distribution D, by learning θ. This can be achieved by optimizing a certain loss function (•), i.e.,

given a (large) training dataset x i , y i m i=1 . For example, for a typical classification task, the class label of a sample x is represented by a one-hot vector y ∈ R k representing its membership in k classes. The loss can be chosen to be either the cross-entropy or 2 -loss [48]. In the following, we use (x, y) to present one training sample.

An overview of ConvNets. The ConvNet [49] is a special deep network architecture, where each of its linear layer can be implemented much more efficiently via convolutions in comparison to fully connected networks [50]. Because of its efficiency and popularity in machine learning, for the rest of the paper, we focus on ConvNets. Suppose the input data x has C channels, represented as

where for 1D signal x k ∈ R m denotes the kth channel feature of x.foot_3 For the th layer (0 ≤ ≤ L-1) of ConvNets, the linear operator

where * denotes the convolution between two items that we will discuss below in more detail. Thus, for the th layer with C input channels and C +1 output channels, we can organize the convolution kernels {a kj } as

Convolution operators. For the simplicity of presentation and analysis, we adopt circular convolution instead of linear convolution. 6 For 1D signal, given a kernel a ∈ R n and an input signal x ∈ R m (in many cases m n), a circular convolution * between a and x can be written in a simple matrix-vector product form via

where C a denotes a circulant matrix of (zero-padded) a,

which is the concatenation of all cyclic shifts s k [a] (0 ≤ k ≤ m -1) of length k of the (zero-padded) vector a. Since C a can be decomposed via the discrete Fourier transform (DFT) matrix F :

where a denotes the Fourier transform of a vector a. The computation of a * x can be carried out efficiently via fast Fourier transform (FFT) in the frequency domain. We refer the readers to the appendix for more technical details.

Convolutional Normalization

In the following, we introduce the proposed ConvNorm, that can fully exploit benign convolution structures of ConvNets. It can be efficiently implemented in the frequency domain, and reduce the layer-wise Lipschitz constant. First of all, we build intuitions of the new design from the simplest setting. From this, we show how to expand the idea to practical ConvNets and discuss its advantages for training and robustness.

A warm-up study

Let us build some intuitions by zooming into one layer of ConvNets with both input and output being single-channel,

where z in is the input signal, a is a single kernel, and z out denotes the output before the nonlinear activation. The form ( 4) is closely related to recent work on blind deconvolution [46]. More specifically, the work showed that normalizing the output z out via preconditioning eliminates bad local minimizers and dramatically improves the optimization landscapes for learning the kernel a.

The basic idea is to multiply a preconditioning matrix which approximates the following form 7

As we observe 6 Although there are slight differences between linear and circulant convolutions on the boundaries, actually any linear convolution can be reduced to circular convolution simply via zero-padding. 7 In the work [46], they cook up a matrix by using output samples

. When the input samples z i in are i.i.d. zero mean, it can be showed that P ≈ P for large m. For ConvNets, we can just use the learned kernel a for cooking up P .

•z in , the ConvNorm is essentially reparametrizing the circulant matrix C a of the kernel a to an orthogonal circulant matrix Q(a) = C a C a -1/2 C a , with QQ = I. Thus, the ConvNorm is improving the conditioning of the vanilla problem and reducing the Lipschitz constant of the operator A L (•) in (4).

On the other hand, the benefits of this normalization can also be observed in the frequency domain.

Based on (3), we have

. Thus, we also have

with denoting entrywise operation and g = F -1 a | a| -1 . Thus, we can see that:

• Although the reparameterization involves matrix inversion, which is typically expensive to compute, for convolution it can actually be much more efficiently implemented in the frequency domain via FFT, reducing the complexity from O(n 3 ) to O(n log n). • The reparametrized kernel g is effectively an all-pass filter with flat normalized spectrum a | a| -1 .foot_4 From an information theory perspective, this implies that it can better preserve (in particular, high-frequency) information of the input feature from the previous layer.

ConvNorm for multiple channels

So far, we only considered one layer ConvNets with single-channel input and output. However, recall from Section 2, modern deep ConvNets are usually designed with many layers; each typical layer is constructed with a linear transformation with multiple input and output channels, followed by strides, normalization, and nonlinear activation. Extension of the normalization approach in Section 3.1 from one layer to multiple layers is easy, which can be done by applying the same normalization repetitively for all the layers. However, generalizing our method from a single channel to multiple channels is not obvious, that we discuss below.

In [40], the work introduced a preconditioning method for normalizing multiple kernels in convolutional sparse coding. In the following, we show that such an idea can be adapted to normalize each output channel, reduce the Lipschitz constant of the weight matrix in each layer, and improve training and network robustness. Let us consider any layer (1 ≤ ≤ L) within a vanilla ConvNet using 1-stride, and take one channel (e.g., k-th channel) of that layer as an example. For simplicity of presentation, we hide the layer number . Given z k,out = C I j=1 a kj * z j,in , the k-th output channel can be written as

with C I and C O being the numbers of input and output channels, respectively. For each channel k = 1, • • • , C O , we normalize the output by

Thus, we can see the ConvNorm is essentially a reparameterization of the kernels {a kj } C I j=1 for the k-th channel. Similar to Section 3.1, the operation can be rewritten in the form of convolutions

; it can be efficiently implemented via FFT.

Here, as for multiple kernels the matrix A k is overcomplete (i.e., A k is a wide rectangular matrix), we cannot normalize the channel-wise weight matrix A k to exact orthogonal. However, it can be normalized to tight frame with Q k Q k = I. This further implies that we can normalize the spectral norm Q k of the weight matrix Q k in each channel to unity (see Figure 2 (Left)). Combining the operation for all the channels, the ConvNorm for each layer overall can be summarized as follows:

that we normalize each output channel k by different matrix P k . The proposed ConvNorm has several advantages that we discuss below. Proposition 3.1 The spectral norm of Q introduced in (8) can be bounded by

that spectral norm of Q is bounded by the spectral norms of all the weights {Q k } C O k=1 . Proof We defer the proof to the Appendix A.3.

• Efficient implementations. There are many existing results [29,39,41] trying to normalize the whole layerwise weight matrix. For ConvNets, as the matrix is neither circulant nor block circulant, computing its inversion is often computationally prohibitive. Here, for each layer, we only normalize the weight matrix of the individual output channel. Thus similar to Section 3.1, the inversion in (6) can be much more efficiently computed via FFT by exploiting the benign convolutional structure. • Improving layer-wise Lipschitzness. As we can see from Proposition 3.1, although ConvNorm only normalized the spectral norm of each channel, it can actually reduce the spectral norm of the whole weight matrix, improving the Lipschitzness of each layer; see Figure 2 (Right) for a numerical demonstration on ResNet18. As extensively investigated [28,29,42], improving the Lipschitzness of the weights for ConvNets will lead to enhanced robustness against data corruptions, for which we will demonstrate on the proposed ConvNorm in Section 4.1. • Easier training and better generalization. For deconvolution and convolutional sparse coding problems, the work [40,46] showed that ConvNorm could dramatically improve the corresponding nonconvex optimization landscapes. On the other hand, from an algorithmic unrolling perspective for neural network design [52, 53], the ConvNorm is analogous to the preconditioned or conjugate gradient methods [54] which often substantially boost algorithmic convergence. Therefore, we conjecture that the ConvNorm also leads to better optimization landscapes for training ConvNets, that they can be optimized faster to better solution qualities of generalization. We empirically show this in Section 4.2.

Extra technical details

To achieve the full performance and efficiency potentials of the proposed ConvNorm, we discuss some essential implementation details in the following.

Efficient back-propagation. For ConvNorm, as the normalization matrix in ( 6) is constructed from the learned kernels, it complicates the computation of the gradient in back-propagation when training the network. Fortunately, we observe that treating the normalization matrices {P k } as constants during back-propagation usually does not affect the training and generalization performances, so that the computational complexity in training is not increased. We noticed that such a technique has also been recently considered in [55] for self-supervised learning, which is termed as stop-gradient.

Learnable affine tranform. For each channel, we include an (optional) affine transform after the normalization

where the extra convolutional kernel r k is learned along with the original model parameters. The idea of including this affine transform is analogous to including a learnable rescaling in BatchNorm, which can be considered as an "undo" operation to make sure the identity transform can be represented [4].

The difference between our affine transform and BatchNorm is that we apply channel-wise convolutions instead of simple rescaling (see Figure 1). Note that when r k is an inverse kernel of v k (i.e., r k * v k = 1), the overall transformation becomes an identity. The effectiveness of affine transform is demonstrated in the ablation study in Appendix C.4.

Dealing with stride and 2D convolution. There are extra technicalities that we briefly discuss below. For more details, we refer the readers to Appendix B.

• Extension to 2D convolution. Although we introduced the ConvNorm based on 1D convolution for the simplicity of presentations, it should be noted that our approach can be easily extended to the 2D case via 2D FFT. • Dealing with stride. Strided convolutions are universal in modern ConvNet architectures such as the ResNet [5], which can be viewed as downsampling after unstrided convolution. To deal with stride for our ConvNorm, we first perform an unstrided convolution, normalizing the activations using ConvNorm and then downsampling the normalized activations. In comparison, the method proposed in [29] is incompatible with strided convolutions.

Experiments & Results

In this section, we run extensive experiments on CIFAR and ImageNet, empirically demonstrating two major advantages of our approach: (i) it improves the robustness against adversarial attacks, data scarcity, and label noise corruptions [56][57][58], and (ii) it makes deep ConvNets easier to train and perform better on problems such as classification and GANs [59]. The rest of this section is organized as follows. First, we introduce baseline methods for comparisons, and describe the setups of network architectures, datasets, and training. In Section 4.1 and Section 4.2, we demonstrate the effectiveness of our approach on robustness and training, respectively.

Baseline methods for comparisons. We compare our method with three representative methods.

• Spectral normalization (SN). For each layer of ConvNets, the work [15] treats multi-dimensional convolutional kernels as 2D matrices (e.g., by flattening certain dimensions) and normalizes its spectrum (i.e., singular values). It estimates the matrix's maximum singular value via a power method and then uses it to normalize all the singular values. As we discussed in Section 1, the method does not exploit convolutional structures of ConvNets. • Orthogonalization by Newton's Iteration (ONI). The work [39] whitens the same reshaped matrices as SN, so that the reshaped matrices are reparametrized to orthogonality. However, the method needs to compute full inversions of covariance matrices, which is approximated by Newton's iterations. Again, no convolutional structure is utilized. • Orthogonal ConvNets (OCNN). Few methods that exploit convolutional structures are [22,43],

which enforce orthogonality on doubly block circulant matrices of kernels via penalties on the loss.

Here, we compare with [43].

Setups of dataset, network and training. For all experiments, if not otherwise mentioned, CIFAR-10 and CIFAR-100 datasets are processed with standard augmentations, i.e., random cropping and flipping. We use 10% of the training set for validation and treat the validation set as a held-out test set. For ImageNet, we perform standard random resizing and flipping. For training, we observe our ConvNorm is not sensitive to the learning rate, and thus we fix the initial learning rate to 0.1 for all experiments.foot_5 For experiments on CIFAR-10, we run 120 epochs and divide the learning rate by 10 at the 40th and 80th epochs; for CIFAR-100, we run 150 epochs and divide the learning rate by 10 at the 60th and 120th epoch; for ImageNet,we run 90 epochs and divide the learning rate by 10 at the 30th and 90th epochs. The optimization is done using SGD with a momentum of 0.9 and a weight decay of 0.0001 for all datasets. For networks we use two backbone networks: VGG16 shows that normalizing the weights enforces certain regularizations, which can improve generalization performance against both label noise and data scarcity. Since our method is essentially reparametrizing and normalizing the weights, we demonstrate the robustness of our approach under these settings on CIFAR-10 with ResNet18 backbone.

• Robustness against label noise. Following the scheme proposed in [68], we simulate noisy labels by randomly flipping 20% to 80% of the labels in the training set. As shown in Figure 3 (Left), our method outperforms the others on most noisy rates by a hefty margin when the noise level is high. Improved training on supervised learning. We test our method on image classification tasks with two backbone architectures: VGG16 and ResNet18. We show that ConvNorm accelerates the convergence of training. To isolate the effects of the normalization layers for training, we train on CIFAR-10 and ImageNet without using any augmentation, regularization, and learning rate decay.

In Figure 4, we show that adding ConvNorm consistently results in faster convergence, stable training (less variance in accuracy), and superior performance. CIFAR-10, there is a wide gap after the first few iterations of training: 1000 iterations of training with ConvNorm lead to generalization performance comparable to 8000 iterations of training using BatchNorm. In the case of standard settings where data augmentation, regularization and learning rate decay are added, we notice that using ConvNorm and BatchNorm together also yield better test performances compared to only using BatchNorm (See Appendix C.4 for details). Besides the convergence speed of training, the exact training time for different methods is another important factor for measuring the efficiency of such methods. To this end, we empirically compare the training time for different methods and report the results in Appendix D and Table 8. Improved performance for GANs. It has been found that improving the Lipschitz condition of the discriminator of GAN stabilizes its training [69]. For instance, WGAN-GP [70] demonstrates that adding a gradient penalty (1-GP) regularization to enforce the 1-Lipschitzness of the discriminator stabilizes GAN training and prevents mode collapse. Subsequent works [71, 72] using variants of the 1-GP regularization also show their improvement in GAN. Later on, [15] further reveals the performance of GAN can be significantly improved if the spectral norm (Lipschitz condition) of the discriminator network is strictly enforced to 1. As shown in Figure 2, the proposed ConvNorm also controls the Lipschitz condition of ConvNets. Therefore, we expect our method to also ameliorates the performance of GAN. For each pair of model and method, we generate 50k images 10 times and compute the mean of IS.

To demonstrate the effectiveness of the Con-vNorm on GAN, we compare it with other baseline methods introduced previously. In our experiments, we adopt the same settings and architecture suggested in [15] without any modification, and we use the inception score (IS) [73], and FID [74] score for quantitative evaluation.

As shown in Table 3, our ConvNorm achieves the second-best performance to SN.foot_6

Discussions & Conclusion

In this work, we introduced a new normalization approach for ConvNets, which explicitly exploits translation-invariance properties of convolutional operators, leading to efficient implementation and boosted performances in training, generalization, and robustness. Our work has opened several interesting directions to be further exploited for normalization design of ConvNets: (i) although we provided some high-level intuitions why our ConvNorm works, theoretical justifications are needed;

(ii) as our ConvNorm only promotes channel-wise "orthogonality", it would be interesting to utilize similar ideas to efficiently normalize the layerwise weight matrices by exploiting convolutional structures. We leave these questions for future investigations.