# Convolutional Normalization: Improving Deep Convolutional Network Robustness
and Training

Sheng Liu, The first two authors contributed to this work equally. Center for
Data Science, New York University  Xiao Li  Center for Data Science, New York
University  Department of EECS, University of Michigan  Yuexiang Zhai
Department of EECS, UC Berkeley  Chong You  Department of EECS, UC Berkeley
Zhihui Zhu  Electrical and Computer Engineering, University of Denver  Carlos
Fernandez-Granda  Center for Data Science, New York University  Courant
Institute of Mathematical Sciences, New York University  Qing Qu  Department
of EECS, University of Michigan

###### Abstract

Normalization techniques have become a basic component in modern convolutional
neural networks (ConvNets). In particular, many recent works demonstrate that
promoting the orthogonality of the weights helps train deep models and improve
robustness. For ConvNets, most existing methods are based on penalizing or
normalizing weight matrices derived from concatenating or flattening the
convolutional kernels. These methods often destroy or ignore the benign
convolutional structure of the kernels; therefore, they are often expensive or
impractical for deep ConvNets. In contrast, we introduce a simple and
efficient “Convolutional Normalization” (ConvNorm) method that can fully
exploit the convolutional structure in the Fourier domain and serve as a
simple plug-and-play module to be conveniently incorporated into any ConvNets.
Our method is inspired by recent work on preconditioning methods for
convolutional sparse coding and can effectively promote each layer’s channel-
wise isometry. Furthermore, we show that our ConvNorm can reduce the layerwise
spectral norm of the weight matrices and hence improve the Lipschitzness of
the network, leading to easier training and improved robustness for deep
ConvNets. Applied to classification under noise corruptions and generative
adversarial network (GAN), we show that the ConvNorm improves the robustness
of common ConvNets such as ResNet and the performance of GAN. We verify our
findings via numerical experiments on CIFAR and ImageNet.

##  1 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.

Figure 1: Comparison between BatchNorm and ConvNorm on activations of
$k=1,\dots,C$ channels. BatchNorm subtracts and multiplies the activations of
each channel by computed scalars: mean $\mu$ and variance $\sigma^{2}$, before
a per-channel affine transform parameterized by learned parameters $\beta$ and
$\gamma$; ConvNorm performs per-channel convolution with precomputed kernel
$v$ to normalize the spectrum of the weight matrix for the convolution layer,
following with a channel-wise convolution with learned kernel $r$ as the
affine transform.

#### 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 [35, 28, 36, 37, 27, 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
translation-invariance 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.111Tight frame can be viewed as a generalization of orthogonality
for overcomplete matrices, which is also energy preserving. 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.

  * •

Improving network robustness. Although the ConvNorm operates on each output
channel separately, we show that it actually improves the overall layer-wise
Lipschitzness of the ConvNets. Therefore, as demonstrated by our experiments,
it has superior robustness performance against noise corruptions and
adversarial attacks.

  * •

Improving network training. We numerically demonstrate that the ConvNorm
accelerates training on standard image datasets such as CIFAR [44] and
ImageNet [45]. Inspired by the work [46, 40], 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 [43, 22] 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.222In
[29], the results are reported based on ResNet9, whereas our method can be
easily added to larger networks, e.g. ResNet18 and ResNet50. 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. The code of implementing our ConvNorm can be found online:

https://github.com/shengliu66/ConvNorm.

##  2 Preliminary

#### Review of deep networks.

A deep network is essentially a _nonlinear_ mapping
$f(\cdot):\mathbf{x}\mapsto\mathbf{y}$, which can be modeled by a composition
of a series of simple maps: $f(\mathbf{x})=f^{L-1}\circ\cdots\circ f^{1}\circ
f^{0}(\mathbf{x})$, where every $f^{\ell}(\cdot)\;(1\leq\ell\leq L)$ is called
one “layer”. Each layer is composed of a linear transform, followed by a
simple nonlinear activation function $\varphi(\cdot)$.333The nonlinearity
could contain BatchNorm [4], pooling, dropout [47], and stride, etc. More
precisely, a basic deep network of $L$ layers can be defined recursively by
interleaving linear and nonlinear activation layers as

$\displaystyle\mathbf{z}^{\ell+1}=f^{\ell}(\mathbf{z}^{\ell})=\varphi\circ\mathcal{A}^{\ell}(\mathbf{z}^{\ell})$
(1)

for $\ell=0,1,\ldots,L-1,$ with $\mathbf{z}_{0}=\mathbf{x}$. Here
$\mathcal{A}^{\ell}(\cdot)$ denotes the linear transform and will be described
in detail soon. For convenience, let us use $\mathbf{\theta}$ to denote all
network parameters in
$\left\\{\mathcal{A}^{\ell}(\cdot)\right\\}_{\ell=0}^{L-1}$. The goal of deep
learning is to fit the observation $\mathbf{y}$ with the output
$f(\mathbf{x},\mathbf{\theta})$ for any sample $\mathbf{x}$ from a
distribution $\mathcal{D}$, by learning $\mathbf{\theta}$. This can be
achieved by optimizing a certain loss function $\ell(\cdot)$, i.e.,

$\displaystyle\min_{\mathbf{\theta}\in\mathbf{\Theta}}\;L(\mathbf{\theta};\left\\{\left(\mathbf{x}^{i},\mathbf{y}^{i}\right)\right\\}_{i=1}^{m})\;:=\;\frac{1}{m}\sum_{i=1}^{m}\ell\left(f(\mathbf{x}^{i},\mathbf{\theta}),\mathbf{y}^{i}\right),$

given a (large) training dataset
$\left\\{\left(\mathbf{x}^{i},\mathbf{y}^{i}\right)\right\\}_{i=1}^{m}$. For
example, for a typical classification task, the class label of a sample
$\mathbf{x}$ is represented by a one-hot vector $\mathbf{y}\in\mathbb{R}^{k}$
representing its membership in $k$ classes. The loss can be chosen to be
either the cross-entropy or $\ell_{2}$-loss [48]. In the following, we use
$(\mathbf{x},\mathbf{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 $\mathbf{x}$ has $C$ channels, represented as

$\displaystyle\mathbf{x}\;=\;\left(\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{C}\right),$
(2)

where for 1D signal $\mathbf{x}_{k}\in\mathbb{R}^{m}$ denotes the $k$th
channel feature of $\mathbf{x}$.444If the data is 2D, we can assume
$\mathbf{x}\in\mathbb{R}^{m_{1}\times m_{2}}$. For simplicity, we present our
idea based on 1D signal. For the $\ell$th layer $(0\leq\ell\leq L-1)$ of
ConvNets, the linear operator
$\mathcal{A}^{\ell}(\cdot):\mathbb{R}^{C_{\ell}\times
m}\mapsto\mathbb{R}^{C_{\ell+1}\times m}$ in (1) is a convolution operation
with $C_{\ell+1}$ output channels,

$\displaystyle\mathbf{z}^{\ell+1}\;$
$\displaystyle=\;\left(\mathbf{z}_{1}^{\ell+1},\mathbf{z}_{2}^{\ell+1},\cdots,\mathbf{z}_{C_{\ell+1}}^{\ell+1}\right),$
$\displaystyle\mathbf{z}_{k}^{\ell+1}\;$
$\displaystyle=\;\varphi\left(\sum_{j=1}^{C_{\ell}}\mathbf{a}_{kj}^{\ell}\ast\mathbf{z}_{j}^{\ell}\right)\quad(1\leq
k\leq C_{\ell+1}),$

where $\ast$ denotes the convolution between two items that we will discuss
below in more detail. Thus, for the $\ell$th layer with $C_{\ell}$ input
channels and $C_{\ell+1}$ output channels, we can organize the convolution
kernels $\left\\{\mathbf{a}_{kj}\right\\}$ as

$\displaystyle\mathbf{A}^{\ell}\;=\;\begin{bmatrix}\mathbf{a}_{11}^{\ell}&\mathbf{a}_{12}^{\ell}&\cdots&\mathbf{a}_{1C_{\ell}}^{\ell}\\\
\mathbf{a}_{21}^{\ell}&\mathbf{a}_{22}^{\ell}&\cdots&\mathbf{a}_{2C_{\ell}}^{\ell}\\\
\vdots&\vdots&\ddots&\vdots\\\
\mathbf{a}_{C_{\ell+1}1}^{\ell}&\mathbf{a}_{C_{\ell+1}2}^{\ell}&\cdots&\mathbf{a}_{C_{\ell+1}C_{\ell}}^{\ell}\end{bmatrix}.$

#### Convolution operators.

For the simplicity of presentation and analysis, we adopt _circular_
convolution instead of linear convolution.555Although 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. For 1D signal, given a kernel
$\mathbf{a}\in\mathbb{R}^{n}$ and an input signal
$\mathbf{x}\in\mathbb{R}^{m}$ (in many cases $m\gg n$), a circular convolution
$\ast$ between $\mathbf{a}$ and $\mathbf{x}$ can be written in a simple
matrix-vector product form via

$\displaystyle\mathbf{y}\;=\;\mathbf{a}\ast\mathbf{x}\;=\;\mathbf{C}_{\mathbf{a}}\cdot\mathbf{x},$

where $\mathbf{C}_{\mathbf{a}}$ denotes a circulant matrix of (zero-padded)
$\mathbf{a}$,

$\displaystyle\mathbf{C}_{\mathbf{a}}\;:=\;\begin{bmatrix}{\mathrm{s}_{0}}\left[\mathbf{a}\right]&{\mathrm{s}_{1}}\left[\mathbf{a}\right]&\cdots&{\mathrm{s}_{m-1}}\left[\mathbf{a}\right]\end{bmatrix},$

which is the concatenation of all cyclic shifts
${\mathrm{s}_{k}}\left[\mathbf{a}\right]\;(0\leq k\leq m-1)$ of length $k$ of
the (zero-padded) vector $\mathbf{a}$. Since $\mathbf{C}_{\mathbf{a}}$ can be
decomposed via the discrete Fourier transform (DFT) matrix $\mathbf{F}$:

$\displaystyle\mathbf{C}_{\mathbf{a}}\;=\;\mathbf{F}^{*}\operatorname{diag}\left(\widehat{\mathbf{a}}\right)\mathbf{F},\quad\widehat{\mathbf{a}}\;=\;\mathbf{F}\mathbf{a},$
(3)

where $\widehat{\mathbf{a}}$ denotes the Fourier transform of a vector
$\mathbf{a}$. The computation of $\mathbf{a}\ast\mathbf{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.

##  3 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.

###  3.1 A warm-up study

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

$\displaystyle\mathbf{z}_{out}\;=\;\mathcal{A}_{L}(\mathbf{z})\;=\;\mathbf{a}\ast\mathbf{z}_{in},$
(4)

where $\mathbf{z}_{in}$ is the input signal, $\mathbf{a}$ is a single kernel,
and $\mathbf{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 $\mathbf{z}_{out}$
via _preconditioning_ eliminates bad local minimizers and dramatically
improves the optimization landscapes for learning the kernel $\mathbf{a}$. The
basic idea is to multiply a preconditioning matrix which approximates the
following form666In the work [46], they cook up a matrix by using output
samples
$\widetilde{\mathbf{P}}=\left(\frac{C}{m}\sum_{i=1}^{m}\mathbf{C}_{\mathbf{z}_{out}^{i}}(\mathbf{C}_{\mathbf{z}_{out}^{i}})^{\top}\right)^{-1/2}$.
When the input samples $\mathbf{z}_{in}^{i}$ are i.i.d. zero mean, it can be
showed that $\widetilde{\mathbf{P}}\approx\mathbf{P}$ for large $m$. For
ConvNets, we can just use the learned kernel $\mathbf{a}$ for cooking up
$\mathbf{P}$.

$\displaystyle\mathbf{P}\;=\;\left(\mathbf{C}_{\mathbf{a}}\mathbf{C}_{\mathbf{a}}^{\top}\right)^{-1/2}.$
(5)

As we observe

$\displaystyle\widetilde{\mathbf{z}}_{out}\;=\;\mathbf{P}\mathbf{z}_{out}\;=\;\underbrace{\left(\mathbf{C}_{\mathbf{a}}\mathbf{C}_{\mathbf{a}}^{\top}\right)^{-1/2}\mathbf{C}_{\mathbf{a}}}_{\mathbf{Q}(\mathbf{a})}\cdot\mathbf{z}_{in},$

the ConvNorm is essentially _reparametrizing_ the circulant matrix
$\mathbf{C}_{\mathbf{a}}$ of the kernel $\mathbf{a}$ to an _orthogonal_
circulant matrix
$\mathbf{Q}(\mathbf{a})=\left(\mathbf{C}_{\mathbf{a}}\mathbf{C}_{\mathbf{a}}^{\top}\right)^{-1/2}\mathbf{C}_{\mathbf{a}}$,
with $\mathbf{Q}\mathbf{Q}^{\top}=\mathbf{I}$. Thus, the ConvNorm is improving
the conditioning of the _vanilla_ problem and reducing the Lipschitz constant
of the operator $\mathcal{A}_{L}(\cdot)$ in (4). On the other hand, the
benefits of this normalization can also be observed in the frequency domain.
Based on (3), we have
$\mathbf{P}=\mathbf{F}^{*}\operatorname{diag}\left(\mathbf{v}\right)\mathbf{F}=\mathbf{C}_{\mathbf{v}}$
with
$\mathbf{v}=\mathbf{F}^{-1}\left(\left|\widehat{\mathbf{a}}\right|^{\odot-1}\right)$.
Thus, we also have

$\displaystyle\mathbf{Q}(\mathbf{a})=\mathbf{C}_{\mathbf{v}}\cdot\mathbf{C}_{\mathbf{a}}\;=\;\mathbf{C}_{\mathbf{v}\ast\mathbf{a}}=\mathbf{F}^{*}\operatorname{diag}(\widehat{\mathbf{g}}(\mathbf{a}))\mathbf{F},\quad\widehat{\mathbf{g}}(\mathbf{a})\;=\;\widehat{\mathbf{a}}\odot\left|\widehat{\mathbf{a}}\right|^{\odot-1},$

with $\odot$ denoting entrywise operation and
$\mathbf{g}=\mathbf{F}^{-1}\left(\widehat{\mathbf{a}}\odot\left|\widehat{\mathbf{a}}\right|^{\odot-1}\right)$.
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 $\mathbf{g}$ is effectively an _all-pass_ filter
with flat normalized spectrum
$\widehat{\mathbf{a}}\odot\left|\widehat{\mathbf{a}}\right|^{\odot-1}$.777An
all-pass filter is a signal processing filter that passes all frequencies
equally in gain, but can change the phase relationship among various
frequencies. 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.

###  3.2 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 $\ell$ ($1\leq\ell\leq 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 $\ell$. Given
$\mathbf{z}_{k,out}=\sum_{j=1}^{C_{I}}\mathbf{a}_{kj}\ast\mathbf{z}_{j,in}$,
the $k$-th output channel can be written as

$\displaystyle\mathbf{z}_{k,out}\;=\;\underbrace{\begin{bmatrix}\mathbf{C}_{\mathbf{a}_{k1}}&\mathbf{C}_{\mathbf{a}_{k2}}&\cdots&\mathbf{C}_{\mathbf{a}_{kC_{I}}}\end{bmatrix}}_{\mathbf{A}_{k}}\cdot\underbrace{\begin{bmatrix}{\mathbf{z}}_{1,in}\\\
{\mathbf{z}}_{2,in}\\\ \vdots\\\
{\mathbf{z}}_{C_{I},in}\end{bmatrix}}_{\mathbf{z}_{in}},$

with $C_{I}$ and $C_{O}$ being the numbers of input and output channels,
respectively. For each channel $k=1,\cdots,C_{O}$, we normalize the output by

$\displaystyle\boxed{\mathbf{P}_{k}\;=\;\left(\sum_{j=1}^{C_{I}}\mathbf{C}_{\mathbf{a}_{kj}}\mathbf{C}_{\mathbf{a}_{kj}}^{\top}\right)^{-1/2}=\left(\mathbf{A}_{k}\mathbf{A}_{k}^{\top}\right)^{-1/2},}$
(6)

so that

$\displaystyle\widetilde{\mathbf{z}}_{k,out}\;=\;\mathbf{P}_{k}\mathbf{z}_{k,out}\;=\;\underbrace{\left(\mathbf{A}_{k}\mathbf{A}_{k}^{\top}\right)^{-1/2}\mathbf{A}_{k}}_{\mathbf{Q}_{k}(\mathbf{A}_{k})}\cdot\mathbf{z}_{in}.$
(7)

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

$\displaystyle\mathbf{Q}_{k}(\mathbf{A}_{k})\;=\;\mathbf{P}_{k}\mathbf{A}_{k}\;=\;\begin{bmatrix}\mathbf{C}_{\mathbf{v}_{k}\ast\mathbf{a}_{k1}}&\cdots&\mathbf{C}_{\mathbf{v}_{k}\ast\mathbf{a}_{kC_{I}}}\end{bmatrix}$

with $\mathbf{P}_{k}=\mathbf{C}_{\mathbf{v}_{k}}$ and
$\mathbf{v}_{k}=\mathbf{F}^{-1}\left(\sum_{i=1}^{C_{I}}\left|\widehat{\mathbf{a}}_{ki}\right|^{\odot
2}\right)^{\odot-1/2}$; it can be efficiently implemented via FFT.

Here, as for multiple kernels the matrix $\mathbf{A}_{k}$ is _overcomplete_
(i.e., $\mathbf{A}_{k}$ is a wide rectangular matrix), we _cannot_ normalize
the channel-wise weight matrix $\mathbf{A}_{k}$ to exact orthogonal. However,
it can be normalized to _tight frame_ with
$\mathbf{Q}_{k}\mathbf{Q}_{k}^{\top}\;=\;\mathbf{I}$. This further implies
that we can normalize the spectral norm $\left\|\mathbf{Q}_{k}\right\|$ of the
weight matrix $\mathbf{Q}_{k}$ in each channel to unity (see Figure 2 (Left)).

Figure 2: Condition number for each channel (averaged over all channels)
(Left), and spectral norm for each layer (Right) on ResNet18 except for skip
connection layers. ConvNorm normalizes the channel-wise condition number to 1
and reduces the layer-wise spectral norm. We use the method in [51] to
calculate the singular values of the weight matrix.

Combining the operation for all the channels, the ConvNorm for each layer
overall can be summarized as follows:

$\displaystyle\widetilde{\mathbf{z}}_{out}\;=\;\begin{bmatrix}\mathbf{P}_{1}\mathbf{z}_{1,out}\\\
\vdots\\\
\mathbf{P}_{C_{O}}\mathbf{z}_{C_{O},out}\end{bmatrix}\;=\;\underbrace{\begin{bmatrix}\mathbf{Q}_{1}\\\
\vdots\\\ \mathbf{Q}_{C_{O}}\end{bmatrix}}_{\mathbf{Q}}\mathbf{z}_{in},$ (8)

that we normalize each output channel $k$ by different matrix
$\mathbf{P}_{k}$. The proposed ConvNorm has several advantages that we discuss
below.

###### Proposition 3.1

The spectral norm of $\mathbf{Q}$ introduced in (8) can be bounded by

$\displaystyle\left\|\mathbf{Q}\right\|\;\leq\;\sqrt{\sum_{k=1}^{C_{O}}\left\|\mathbf{Q}_{k}\right\|^{2}},$

that spectral norm of $\mathbf{Q}$ is bounded by the spectral norms of all the
weights $\left\\{\mathbf{Q}_{k}\right\\}_{k=1}^{C_{O}}$.

Proof We defer the proof to the Appendix A.3.

  * •

Efficient implementations. There are many existing results [41, 39, 29] 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, 42, 29], 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 [46, 40] 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.

###  3.3 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 $\left\\{\mathbf{P}_{k}\right\\}$ 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
$\mathbf{P}_{k}\cdot{\mathbf{z}}_{k,out}=\mathbf{C}_{\mathbf{v}_{k}}\cdot{\mathbf{z}}_{k,out}=\mathbf{v}_{k}\ast{\mathbf{z}}_{k,out}$
in (7) as follows:

$\displaystyle\overline{\mathbf{z}}_{k}\;=\;\mathbf{r}_{k}\ast\widetilde{\mathbf{z}}_{k,out}\;=\;\mathbf{r}_{k}\ast\mathbf{v}_{k}\ast{\mathbf{z}}_{k,out},$

where the extra convolutional kernel $\mathbf{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 $\mathbf{r}_{k}$ is an inverse kernel of
$\mathbf{v}_{k}$ (i.e., ${\mathbf{r}}_{k}\ast\mathbf{v}_{k}=\mathbf{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.

##  4 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 [43, 22], 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.888For experiments with ONI, we use learning rate
$0.01$ since the loss would be trained to NaN if with $0.1$. For experiments
on CIFAR-10, we run $120$ epochs and divide the learning rate by $10$ at the
$40$th and $80$th epochs; for CIFAR-100, we run $150$ epochs and divide the
learning rate by $10$ at the $60$th and $120$th epoch; for ImageNet,we run
$90$ epochs and divide the learning rate by $10$ at the $30$th and $90$th
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 [60] and ResNet18 [5]. We adopt Xavier uniform initialization
[61] which is the default initialization in PyTorch for all networks.

$\epsilon$ | Test Acc. | SN | BN | ONI | OCNN | ConvNorm
---|---|---|---|---|---|---
0 | Clean | 82.52 $\pm$ 0.22 | 82.13 $\pm$ 0.67 | 80.70 $\pm$ 0.14 | 82.90 $\pm$ 0.31 | 83.23 $\pm$ 0.25
$\frac{8}{255}$ | FGSM | 52.34 $\pm$ 0.33 | 51.72 $\pm$ 0.52 | 48.33 $\pm$ 0.16 | 52.49 $\pm$ 0.21 | 52.87 $\pm$ 0.24
PGD-10 | 45.68 $\pm$ 0.40 | 45.31 $\pm$ 0.29 | 42.30 $\pm$ 0.24 | 45.74 $\pm$ 0.13 | 46.12 $\pm$ 0.26
PGD-20 | 44.47 $\pm$ 0.37 | 44.04 $\pm$ 0.24 | 41.08 $\pm$ 0.30 | 44.53 $\pm$ 0.10 | 44.75 $\pm$ 0.30

Table 1: Comparison of ConvNorm to baseline methods under different gradient
based attacks. Models are robustly trained following the procedure in [62]
using a ResNet18 backbone. Experiments are conducted on CIFAR-10 dataset.
Results are averaged over $4$ random seeds.

Method | Average Queries | Attack Success rate (%)
---|---|---
SN | 2519.32 | 60.60
ONI | 2817.09 | 55.90
OCNN | 2892.81 | 54.50
ConvNorm | 2966.16 | 53.50

Table 2: Comparison of ConvNorm to baseline methods on SimBA black box attack.
The mean value of average queries (the higher, the better) and attack success
rate (the lower, the better) throughout $3$ runs are reported. Models are
trained using a ResNet18 backbone without BN layers.

###  4.1 Improved robustness

In this section, we demonstrate our method is more robust to various kinds of
adversarial attacks, as well as random label corruptions and small training
datasets.

#### Robustness against adversarial attacks.

Existing results [29, 43] show that controlling the layer-wise Lipschitz
constants for deep networks improves robustness against adversarial attack.
Since our method improves the Lipschitzness of weights (see Figure 2), we
demonstrate its robustness under adversarial attack on the CIFAR-10 dataset.
We adopt both white-box (gradient based) attack [57, 58] and black-box attack
[56] to test the robustness of our proposed method and other baseline methods.
The results are presented in Table 1 and Table 2. For the ease of
presentation, all technical details about model training and generation of the
adversarial examples are postponed to Appendix C.

In the case of gradient based attacks, we follow the training procedure
described in [62] to train models with our ConvNorm and other baseline
methods. We report the performances of the robustly trained models on both the
clean test dataset and datasets that are perturbed by Fast Gradient Sign
Method (FGSM) [57] and Projected Gradient Method (PGD) [58]. As shown in Table
1, our ConvNorm outperforms other methods in terms of robustness under white-
box attack while maintaining a good performance on clean test accuracy.

For black-box attack, we adopt a popular black-box adversarial attack method,
Simple Black-box Adversarial Attacks (SimBA) [56]. By submitting queries to a
model for updated test accuracy, the attack method iteratively finds a
perturbation where the confidence score drops the most. We report the average
queries and success rate after $3072$ iterations in Table 2. As we can see,
the ConvNorm resists the most queries, and that the SimBA has the lowest
attack success rate for ConvNorm compared with other baseline methods.

Noisy Label |  Data Scarcity
---|---
|
Figure 3: Test accuracy for noisy label (Left) and insufficient training data
(Right). Experiments are conducted on CIFAR-10 dataset using a ResNet18
backbone. Error bars corresponding to standard deviations over 3 runs.

#### Robustness against label noise and data scarcity.

It has been widely observed that overparameterized ConvNets tend to overfit
when label noise presents or the amount of training labels is limited [63, 64,
65, 66]. Recent work [67] 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.

  * •

_Robustness against data scarcity._ We test our method on training the network
with varying sizes of the training set, obtained by randomly sampling. The
results in Figure 3 (Right) show that our ConvNorm achieves on par performance
compared with baseline methods, and its performance stays high even when the
size of the training data is tiny (e.g., $4500$ examples).

###  4.2 Easier training on classification and GAN

CIFAR-10 (VGG16) |  CIFAR-10 (ResNet18) |  ImageNet (ResNet18)
---|---|---
|  |
Figure 4: ConvNorm accelerates convergence. VGG16 trained on CIFAR-10 (Left),
and ResNet18 (Middle) trained on CIFAR-10 and ImageNet (Right), with and
without ConvNorm or BatchNorm. We do not use data augmentation, weight decay,
or any other regularization in this experiment to isolate the effects of the
normalization techniques. Error bars correspond to min/max over 4 runs.

Finally, we compare training convergence speed for classification and
performances on GAN. Extra experiments on better generalization performance
and ablation study can be found in Appendix C.4.

#### 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. On CIFAR-10,
there is a wide performance 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.

Metric | SN | ONI | OCNN | Vanilla | ConvNorm
---|---|---|---|---|---
IS | 8.12 | 7.07 | 7.54 | 7.13 | 7.62
FID | 14.53 | 29.49 | 22.15 | 29.47 | 21.37

Table 3: Comparison of ConvNorm to baseline methods on GAN training. Inception
score (IS) (the higher, the better) and FID score (the lower, the better) of
ResNet with different normalizations. 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 ConvNorm 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.999The performance of GANs is highly sensitive to the
computational budget and the hyperparameters of the networks [75], and the
hyperparameters of SN is fine-tuned for CIFAR-10 while we use the same
hyperparameters as SN.

##  5 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.

## Acknowledgement

Part of this work was done when XL and QQ were at Center for Data Science,
NYU. SL, XL, CFG, and QQ were partially supported by NSF grant DMS 2009752. SL
was partially supported by NSF NRT-HDR Award 1922658. CY acknowledges support
from Tsinghua-Berkeley Shenzhen Institute Research Fund. ZZ acknowledges
support from NSF grant CCF 2008460. QQ also acknowledges support of Moore-
Sloan fellowship, and startup fund at the University of Michigan.

## References

  * [1] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” in Advances in neural information processing systems, pp. 1097–1105, 2012.
  * [2] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” arXiv preprint arXiv:1409.1556, 2014.
  * [3] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich, “Going deeper with convolutions,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1–9, 2015.
  * [4] S. Ioffe and C. Szegedy, “Batch normalization: Accelerating deep network training by reducing internal covariate shift,” in ICML, pp. 448–456, 2015\.
  * [5] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016.
  * [6] S. Xie, R. Girshick, P. Dollár, Z. Tu, and K. He, “Aggregated residual transformations for deep neural networks,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1492–1500, 2017.
  * [7] G. Huang, Z. Liu, L. Van Der Maaten, and K. Q. Weinberger, “Densely connected convolutional networks,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700–4708, 2017.
  * [8] L. Huang, J. Qin, Y. Zhou, F. Zhu, L. Liu, and L. Shao, “Normalization techniques in training dnns: Methodology, analysis and application,” arXiv preprint arXiv:2009.12836, 2020.
  * [9] J. L. Ba, J. R. Kiros, and G. E. Hinton, “Layer normalization,” arXiv preprint arXiv:1607.06450, 2016.
  * [10] D. Ulyanov, A. Vedaldi, and V. Lempitsky, “Instance normalization: The missing ingredient for fast stylization,” arXiv preprint arXiv:1607.08022, 2016\.
  * [11] Y. Wu and K. He, “Group normalization,” in Proceedings of the European conference on computer vision (ECCV), pp. 3–19, 2018.
  * [12] K. He, G. Gkioxari, P. Dollár, and R. Girshick, “Mask r-cnn,” in Proceedings of the IEEE international conference on computer vision, pp. 2961–2969, 2017.
  * [13] Y. Sun, X. Wang, Z. Liu, J. Miller, A. Efros, and M. Hardt, “Test-time training with self-supervision for generalization under distribution shifts,” in International Conference on Machine Learning, pp. 9229–9248, PMLR, 2020.
  * [14] T. Salimans and D. P. Kingma, “Weight normalization: A simple reparameterization to accelerate training of deep neural networks,” arXiv preprint arXiv:1602.07868, 2016.
  * [15] T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida, “Spectral normalization for generative adversarial networks,” arXiv preprint arXiv:1802.05957, 2018\.
  * [16] A. Araujo, B. Negrevergne, Y. Chevaleyre, and J. Atif, “On lipschitz regularization of convolutional layers using toeplitz matrix theory,” 2021.
  * [17] H. Qian and M. N. Wegman, “L2-nonexpansive neural networks,” in International Conference on Learning Representations, 2018.
  * [18] A. M. Saxe, J. L. McClelland, and S. Ganguli, “Exact solutions to the nonlinear dynamics of learning in deep linear neural networks,” arXiv preprint arXiv:1312.6120, 2013.
  * [19] J. Pennington, S. Schoenholz, and S. Ganguli, “The emergence of spectral universality in deep networks,” in International Conference on Artificial Intelligence and Statistics, pp. 1924–1932, 2018.
  * [20] L. Xiao, Y. Bahri, J. Sohl-Dickstein, S. Schoenholz, and J. Pennington, “Dynamical isometry and a mean field theory of cnns: How to train 10,000-layer vanilla convolutional neural networks,” in International Conference on Machine Learning, pp. 5393–5402, 2018.
  * [21] W. Hu, L. Xiao, and J. Pennington, “Provable benefit of orthogonal initialization in optimizing deep linear networks,” in International Conference on Learning Representations, 2020.
  * [22] H. Qi, C. You, X. Wang, Y. Ma, and J. Malik, “Deep isometric learning for visual recognition,” in International Conference on Machine Learning, pp. 7824–7835, PMLR, 2020.
  * [23] M. Arjovsky, A. Shah, and Y. Bengio, “Unitary evolution recurrent neural networks,” in International Conference on Machine Learning, pp. 1120–1128, 2016.
  * [24] E. Vorontsov, C. Trabelsi, S. Kadoury, and C. Pal, “On orthogonality and learning recurrent networks with long term dependencies,” in International Conference on Machine Learning, pp. 3570–3578, 2017.
  * [25] K. Helfrich, D. Willmott, and Q. Ye, “Orthogonal recurrent neural networks with scaled cayley transform,” in International Conference on Machine Learning, pp. 1969–1978, PMLR, 2018.
  * [26] M. Lezcano-Casado and D. Martınez-Rubio, “Cheap orthogonal constraints in neural networks: A simple parametrization of the orthogonal and unitary group,” in International Conference on Machine Learning, pp. 3794–3803, 2019.
  * [27] K. Jia, S. Li, Y. Wen, T. Liu, and D. Tao, “Orthogonal deep neural networks,” IEEE transactions on pattern analysis and machine intelligence, 2019.
  * [28] M. Cisse, P. Bojanowski, E. Grave, Y. Dauphin, and N. Usunier, “Parseval networks: Improving robustness to adversarial examples,” arXiv preprint arXiv:1704.08847, 2017.
  * [29] A. Trockman and J. Z. Kolter, “Orthogonalizing convolutional layers with the cayley transform,” in International Conference on Learning Representations, 2021.
  * [30] B. Liu, Y. Zhu, Z. Fu, G. de Melo, and A. Elgammal, “Oogan: Disentangling gan with one-hot sampling and orthogonal regularization.,” in AAAI, pp. 4836–4843, 2020.
  * [31] C. Ye, M. Evanusa, H. He, A. Mitrokhin, T. Goldstein, J. A. Yorke, C. Fermuller, and Y. Aloimonos, “Network deconvolution,” in International Conference on Learning Representations, 2020.
  * [32] A. Brock, J. Donahue, and K. Simonyan, “Large scale gan training for high fidelity natural image synthesis,” in International Conference on Learning Representations, 2018.
  * [33] A. Odena, J. Buckman, C. Olsson, T. B. Brown, C. Olah, C. Raffel, and I. Goodfellow, “Is generator conditioning causally related to gan performance?,” arXiv preprint arXiv:1802.08768, 2018.
  * [34] M. Atzmon, A. Gropp, and Y. Lipman, “Isometric autoencoders,” arXiv preprint arXiv:2006.09289, 2020.
  * [35] M. Harandi and B. Fernando, “Generalized backpropagation, Étude de cas: Orthogonality,” arXiv, 2016.
  * [36] N. Bansal, X. Chen, and Z. Wang, “Can we gain more from orthogonality regularizations in training deep cnns?,” in Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 4266–4276, Curran Associates Inc., 2018.
  * [37] G. Zhang, K. Niwa, and W. B. Kleijn, “Approximated orthonormal normalisation in training neural networks,” 2019.
  * [38] J. Li, F. Li, and S. Todorovic, “Efficient riemannian optimization on the stiefel manifold via the cayley transform,” in International Conference on Learning Representations, 2020.
  * [39] L. Huang, L. Liu, F. Zhu, D. Wan, Z. Yuan, B. Li, and L. Shao, “Controllable orthogonalization in training dnns,” 2020.
  * [40] Q. Qu, Y. Zhai, X. Li, Y. Zhang, and Z. Zhu, “Geometric analysis of nonconvex optimization landscapes for overcomplete learning,” in International Conference on Learning Representations, 2020.
  * [41] L. Huang, X. Liu, B. Lang, A. W. Yu, and B. Li, “Orthogonal weight normalization: Solution to optimization over multiple dependent stiefel manifolds in deep neural networks,” CoRR, vol. abs/1709.06079, 2017.
  * [42] Q. Li, S. Haque, C. Anil, J. Lucas, R. Grosse, and J.-H. Jacobsen, “Preventing gradient attenuation in lipschitz constrained convolutional networks,” Conference on Neural Information Processing Systems, 2019.
  * [43] J. Wang, Y. Chen, R. Chakraborty, and S. X. Yu, “Orthogonal convolutional neural networks,” 2019.
  * [44] A. Krizhevsky et al., “Learning multiple layers of features from tiny images,” 2009.
  * [45] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, et al., “Imagenet large scale visual recognition challenge,” International journal of computer vision, vol. 115, no. 3, pp. 211–252, 2015.
  * [46] Q. Qu, X. Li, and Z. Zhu, “A nonconvex approach for exact and efficient multichannel sparse blind deconvolution,” in Advances in Neural Information Processing Systems, pp. 4017–4028, 2019.
  * [47] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov, “Dropout: a simple way to prevent neural networks from overfitting,” The journal of machine learning research, vol. 15, no. 1, pp. 1929–1958, 2014\.
  * [48] K. Janocha and W. M. Czarnecki, “On loss functions for deep neural networks in classification,” arXiv preprint arXiv:1702.05659, 2017.
  * [49] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” Proceedings of the IEEE, vol. 86, no. 11, pp. 2278–2324, 1998.
  * [50] Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” nature, vol. 521, no. 7553, pp. 436–444, 2015.
  * [51] H. Sedghi, V. Gupta, and P. M. Long, “The singular values of convolutional layers,” arXiv preprint arXiv:1805.10408, 2018.
  * [52] K. Gregor and Y. LeCun, “Learning fast approximations of sparse coding.,” in ICML, pp. 399–406, 2010.
  * [53] V. Monga, Y. Li, and Y. C. Eldar, “Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing,” arXiv preprint arXiv:1912.10557, 2019.
  * [54] J. Nocedal and S. J. Wright, Numerical Optimization.  New York, NY, USA: Springer, second ed., 2006.
  * [55] X. Chen and K. He, “Exploring simple siamese representation learning,” arXiv preprint arXiv:2011.10566, 2020.
  * [56] C. Guo, J. Gardner, Y. You, A. G. Wilson, and K. Weinberger, “Simple black-box adversarial attacks,” in Proceedings of the 36th International Conference on Machine Learning, pp. 2484–2493, 2019.
  * [57] I. Goodfellow, J. Shlens, and C. Szegedy, “Explaining and harnessing adversarial examples,” in International Conference on Learning Representations, 2015.
  * [58] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu, “Towards deep learning models resistant to adversarial attacks,” in International Conference on Learning Representations, 2018.
  * [59] I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. C. Courville, and Y. Bengio, “Generative adversarial nets,” in NIPS, 2014.
  * [60] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” CoRR, vol. abs/1409.1556, 2015.
  * [61] X. Glorot and Y. Bengio, “Understanding the difficulty of training deep feedforward neural networks,” in AISTATS, 2010.
  * [62] A. Shafahi, M. Najibi, M. A. Ghiasi, Z. Xu, J. Dickerson, C. Studer, L. S. Davis, G. Taylor, and T. Goldstein, “Adversarial training for free!,” in Advances in neural information processing systems, vol. 32, 2019.
  * [63] C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna, “Rethinking the inception architecture for computer vision,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818–2826, 2016.
  * [64] D. Arpit, S. Jastrzębski, N. Ballas, D. Krueger, E. Bengio, M. S. Kanwal, T. Maharaj, A. Fischer, A. Courville, Y. Bengio, et al., “A closer look at memorization in deep networks,” in International Conference on Machine Learning, pp. 233–242, PMLR, 2017.
  * [65] M. Li, M. Soltanolkotabi, and S. Oymak, “Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks,” in International Conference on Artificial Intelligence and Statistics, pp. 4313–4324, PMLR, 2020.
  * [66] S. Liu, J. Niles-Weed, N. Razavian, and C. Fernandez-Granda, “Early-learning regularization prevents memorization of noisy labels,” Advances in Neural Information Processing Systems, vol. 33, 2020.
  * [67] W. Hu, Z. Li, and D. Yu, “Simple and effective regularization methods for training on noisily labeled data with generalization guarantee,” arXiv preprint arXiv:1905.11368, 2019.
  * [68] G. Patrini, A. Rozza, A. Krishna Menon, R. Nock, and L. Qu, “Making deep neural networks robust to label noise: A loss correction approach,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1944–1952, 2017.
  * [69] Z. Zhou, J. Liang, Y. Song, L. Yu, H. Wang, W. Zhang, Y. Yu, and Z. Zhang, “Lipschitz generative adversarial nets,” in ICML, 2019.
  * [70] I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. C. Courville, “Improved training of wasserstein GANs,” in Advances in neural information processing systems, pp. 5767–5777, 2017.
  * [71] N. Kodali, J. Abernethy, J. Hays, and Z. Kira, “On convergence and stability of GANs,” arXiv preprint arXiv:1705.07215, 2017.
  * [72] H. Petzka, A. Fischer, and D. Lukovnikov, “On the regularization of wasserstein GANs,” in International Conference on Learning Representations, 2018.
  * [73] T. Salimans, I. Goodfellow, W. Zaremba, V. Cheung, A. Radford, and X. Chen, “Improved techniques for training gans,” arXiv preprint arXiv:1606.03498, 2016.
  * [74] M. Heusel, H. Ramsauer, T. Unterthiner, B. Nessler, and S. Hochreiter, “GANs trained by a two time-scale update rule converge to a local nash equilibrium,” in Advances in neural information processing systems, pp. 6626–6637, 2017.
  * [75] M. Lucic, K. Kurach, M. Michalski, S. Gelly, and O. Bousquet, “Are GANs created equal? a large-scale study,” in Advances in neural information processing systems, pp. 700–709, 2018.
  * [76] C. Kong and S. Lucey, “Take it in your stride: Do we need striding in cnns?,” arXiv preprint arXiv:1712.02502, 2017.

The whole appendix is organized as follows.

  * •

In Appendix A, we introduce the basic notations that are used throughout the
paper and the appendix, and introduce the basic tools for analysis.

  * •

In Appendix B, we describe the implementation details of our ConvNorm,
including details for dealing with 2D convolutions, strides, paddings, and the
discuss about the differences between different types of convolutions.

  * •

In Appendix C, we describe the the experimental settings for Section 4 in
detail.

  * •

Finally, in Appendix D we conduct a more comprehensive ablation study on the
influence of different components of the proposed ConvNorm.

##  Appendix A Notations & basic tools

###  A.1 Notations

Throughout this paper, all vectors/matrices are written in bold font
$\mathbf{a}$/$\mathbf{A}$; indexed values are written as $a_{i},A_{ij}$. For a
matrix $\mathbf{A}\in\mathbb{C}^{m\times n}$, we use $\mathbf{A}^{\top}$ and
$\mathbf{A}^{*}$ to denote the transpose and conjugate transpose of
$\mathbf{A}$, respectively. We let $[m]=\left\\{1,2,\cdots,m\right\\}$. Let
$\mathbf{F}_{n}\in\mathbb{C}^{n\times n}$ denote a unnormalized $n\times n$
DFT matrix, with $\left\|\mathbf{F}_{n}\right\|=\sqrt{n}$, and
$\mathbf{F}_{n}^{-1}=n^{-1}\mathbf{F}_{n}^{*}$. In many cases, we just use
$\mathbf{F}$ to denote the DFT matrix. For any vector
$\mathbf{v}\in\mathbb{C}^{n}$, we use
$\widehat{\mathbf{v}}=\mathbf{F}\mathbf{v}$ to denote its Fourier transform,
and $\overline{\mathbf{v}}$ denotes the conjugate of $\mathbf{v}$. We use
$\ast$ to denote the _circular_ convolution with modulo-$n$:
$\left(\mathbf{v}\ast\mathbf{u}\right)_{i}=\sum_{j=0}^{m-1}v_{j}u_{i-j}$, and
we use $\circledast$ to denote the cross-correlation
$\mathbf{v}\circledast\mathbf{u}$ used in modern ConvNets.

###  A.2 Circular convolution and circulant matrices.

For a vector $\mathbf{v}\in\mathbb{R}^{n}$, let
$\mathrm{s}_{\ell}[\mathbf{v}]$ denote the cyclic shift of $\mathbf{v}$ with
length $\ell$. Thus, we can introduce the circulant matrix
$\mathbf{C}_{\mathbf{v}}\in\mathbb{R}^{n\times n}$ generated through
$\mathbf{v}\in\mathbb{R}^{n}$, that is,

$\displaystyle\mathbf{C}_{\mathbf{v}}=\begin{bmatrix}v_{1}&v_{n}&\cdots&v_{3}&v_{2}\\\
v_{2}&v_{1}&v_{n}&&v_{3}\\\ \vdots&v_{2}&v_{1}&\ddots&\vdots\\\
v_{n-1}&&\ddots&\ddots&v_{n}\\\
v_{n}&v_{n-1}&\cdots&v_{2}&v_{1}\end{bmatrix}=\begin{bmatrix}\mathrm{s}_{0}\left[\mathbf{v}\right]&\mathrm{s}_{1}\left[\mathbf{v}\right]&\cdots&\mathrm{s}_{n-1}\left[\mathbf{v}\right]\end{bmatrix}.$

Now the circular convolution can also be written in a simpler matrix-vector
product form. For instance, for any
$\mathbf{u},\;\mathbf{v}\in\mathbb{R}^{n}$, we have

$\displaystyle\mathbf{u}\ast\mathbf{v}=\mathbf{C}_{\mathbf{u}}\cdot\mathbf{v}=\mathbf{C}_{\mathbf{v}}\cdot\mathbf{u}.$

In addition, the cross-correlation between $\mathbf{u}$ and $\mathbf{v}$ can
be also written in a similar form of convolution operator which reverses one
vector before convolution with $\check{\mathbf{u}}\ast\mathbf{v}$, where
$\check{\mathbf{v}}$ denote a _cyclic reversal_ of
$\mathbf{v}\in\mathbb{R}^{m}$ (i.e.,
$\check{\mathbf{v}}=\left[v_{1},v_{m},v_{m-1},\cdots,v_{2}\right]^{\top}$).

###  A.3 Proof of Proposition 3.1

We restate Proposition 3.1 in Section 3 in the following.

###### Proposition A.1

The spectral norm of $\mathbf{Q}$ introduced in (8) can be bounded by

$\displaystyle\left\|\mathbf{Q}\right\|\;\leq\;\sqrt{\sum_{k=1}^{C_{O}}\left\|\mathbf{Q}_{k}\right\|^{2}},$

that spectral norm of $\mathbf{Q}$ is bounded by the spectral norms of all the
weights $\left\\{\mathbf{Q}_{k}\right\\}_{k=1}^{C_{O}}$.

Proof Suppose we have a matrix of the form
$\mathbf{Q}\;=\;\begin{bmatrix}\mathbf{Q}_{1}\\\ \vdots\\\
\mathbf{Q}_{C_{O}}\end{bmatrix}$, then by using the relationship between
singular values and eigenvalues,

$\displaystyle\sigma_{1}^{2}(\mathbf{Q})\;$
$\displaystyle=\;\lambda_{1}\left(\mathbf{Q}^{\top}\mathbf{Q}\right)\;=\;\lambda_{1}\left(\sum_{i=1}^{C_{O}}\mathbf{Q}_{i}^{\top}\mathbf{Q}_{i}\right)\;\leq\;\sum_{i=1}^{C_{O}}\lambda_{1}\left(\mathbf{Q}_{i}^{\top}\mathbf{Q}_{i}\right)=\sum_{i=1}^{C_{O}}\sigma_{1}^{2}(\mathbf{Q}_{i}).$

Thus, we have

$\displaystyle\sigma_{1}(\mathbf{Q})\;\leq\;\sqrt{\sum_{i=1}^{C_{O}}\sigma_{1}^{2}(\mathbf{Q}_{i})},$

as desired.

##  Appendix B Implementation details for Section 3

In the main paper, for the ease of presentation we only introduced and
discussed the high-level idea of the proposed ConvNorm, with few technical
details missing. Here, we discuss the implementation details of the ConvNorm
for ConvNets in practice. More specifically, Appendix B.1 provides the
pseudocode of ConvNorm with circular convolutions, which is easy for
presentation and analysis. It should be noted that modern ConvNets often use
cross-correlation instead of circular convolutions. Hence in Appendix B.2 and
Appendix B.3, we discuss in detail on how to deal with this difference in
practice. Additionally, in Appendix B.4 and Appendix B.5, we include other
implementation details, such as dealing with strides, and extensions from 1D
to 2D convolutions.

###  B.1 Algorithms

First of all, in Algorithm 1 we provide detailed pseudocode of implementing
the proposed ConvNorm in ConvNets for 2D input data, where the convolution
operations are based on circular convolutions. From our discussion in Section
3 , we can see that all the operations can be efficiently implemented in the
frequency domain via 2D FFTs.101010During evaluation, we use the moving
average of $\widehat{\mathbf{v}}_{k}$ during training, the momentum of the
moving average is obtained by a cosine rampdown function
$0.5\left(1+\text{cos}\left(\frac{\text{min}(\text{iter},40000)}{40000}\pi\right)\right)$,
where iter is the current iteration.

It should be noted that modern ConvNets often use cross-correlation rather
than the circular convolution. Nonetheless, we discuss the differences and
similarities between the two in the following. Based on this, we show how to
adapt Algorithm 1 to modern ConvNets (see Appendix B.2).

Algorithm 1 Pseudocode of the proposed ConvNorm in each layer of ConvNets with 2D inputs.  Require: $\mathbf{z}_{out}\in\mathbb{R}^{B\times C_{O}\times W\times H}$ | = convolution outputs with batchsize $B$, channels $C_{O}$, width $W$, and height $H$
---|---
Require: $\mathbf{a}\in\mathbb{R}^{C_{O}\times C_{I}\times k_{1}\times k_{2}}$ | = kernels for all output channels $C_{O}$, input channels $C_{I}$, and kernel size $k_{1}\times k_{2}$
Require: $\mathbf{r}\in\mathbb{R}^{C_{O}\times k_{1}\times k_{2}}$ | = $C_{O}$ trainable kernels for affine transform with the same size of $\mathbf{a}$
for $k$ in $[1,\dots,C_{O}]$ |  $\triangleright$ for each output channel
do
$\widehat{\mathbf{z}}_{k,out}\leftarrow$ FFT$(\mathbf{z}_{k,out})$ |  $\triangleright$ apply 2D Fast Fourier Transform (FFT) on convolution output
$\widehat{\mathbf{a}}_{k}\leftarrow\text{FFT}(\mathbf{a}_{k})$ |  $\triangleright$ apply 2D FFT on kernels
$\widehat{\mathbf{a}}_{k}\leftarrow$ `stop_gradient`$\left(\widehat{\mathbf{a}}_{k}\right)$ |  $\triangleright$ treating ${\widehat{\mathbf{a}}_{k}}$ as constants during back-propagation
$\widehat{\mathbf{v}}_{k}\leftarrow\left(\sum_{i=1}^{C_{I}}|\widehat{\mathbf{a}}_{ki}|^{\odot 2}\right)^{\odot-1/2}$ |  $\triangleright$ this is the 2D FFT of $\mathbf{v}_{k}$
$\widetilde{\mathbf{z}}_{k,out}\leftarrow\text{IFFT}\left(\widehat{\mathbf{z}}_{k,out}\odot\widehat{\mathbf{v}}_{k}\right)$ |  $\triangleright$ circularly convolve $\mathbf{z}_{out,k}$ with $\mathbf{v}_{k}$
$\bar{\mathbf{z}}_{k,out}\leftarrow\mathbf{r}_{k}\ast\widetilde{\mathbf{z}}_{k,out}$ |  $\triangleright$ learnable affine transformation with $\mathbf{r}_{k}$
endfor
return $\bar{\mathbf{z}}_{k,out}$ |  $\triangleright$ normalized convolution output

###  B.2 Dealing with convolutions in ConvNets

Throughout the main body of the work, our description and analysis of ConvNorm
are based on circular convolutions for the simplicity of presentations.
However, it should be noted that current ConvNets typically use _cross
correlation_ in each convolutional layer, which can be viewed as a variant of
the classical linear convolution with flipped kernels. Hence, to adapt our
analysis from circular convolution to cross-correlation (i.e., the typical
convolution used in ConvNets), we need to build some sense of
“equivalence”between them. Since linear convolution has a close connection
with both, we use linear convolution as a bridge to introduce the relationship
and thus find the “equivalence” between circular convolution and cross-
correlation. Based on this, we show how to adapt from circular convolution in
Algorithm 1 to the convolution used in modern ConvNets by simple
modifications.

#### Relationship among all convolutions.

In the following presentations, assume we have a signal
$\mathbf{x}\in\mathbb{R}^{n}$ and a kernel vector
$\mathbf{a}\in\mathbb{R}^{m}$ with $m\leq n$. We first discuss the connections
between linear convolution and the other two types of convolutions, and then
establish the equivalence between circular convolution and cross-correlation
upon the observed connections. Figure 5 demonstrates a simple example of the
connections.

  * •

Linear convolution & circular convolution. The (finite, discrete) linear and
circular convolution can both be written as

$\displaystyle\mathbf{y}\left(k\right)=\sum_{j=0}^{n-1}\mathbf{a}\left(k-j\right)\mathbf{x}\left(j\right).$

Despite the same written form, they differ in two ways: length and index. As
illustrated in Figure 5 (i), linear convolution doesn’t have constraints on
the input length and the result always has length $n+m-1$. In comparison,
circular convolution requires both the kernel $\mathbf{a}$ and the signal
$\mathbf{x}$ to share the same length. Therefore, as in Figure 5 (iii) and
(iv), we always reduce linear convolution to circular convolution by zero
padding both the kernel and the signal to the same length $n+m-1$, as shown in
the example in Figure 5 (iv). It should be noted that the reason for such
length difference is also rooted in their different indexing methods. In the
case of linear convolution, when indices fall outside the defined regions, the
associated entries are $0$, e.g., $\mathbf{a}\left(-1\right)=0$ and
$\mathbf{x}\left(3\right)=0$ as shown Figure 5 (i). On the other hand,
circular convolution uses the periodic indexing method, i.e.,
$\mathbf{a}\left(-j\right)=\mathbf{a}\left(m-j\right)$. For example, in Figure
5 (iii), $\mathbf{a}\left(-2\right)=\mathbf{a}\left(3-2\right)=4$.

  * •

Linear convolution & cross-correlation. As shown in Figure 5 (i) and (ii),
both linear convolution and cross-correlation operations apply the so-called
_sliding window_ of the kernel $\mathbf{a}$ to the signal $\mathbf{x}$, where
the sliding window moves to the right one step at a time when the stride
equals one. However, notice that cross-correlation uses a flipped kernel
compared with linear convolution. Another difference is in the length of the
output, where the output of a linear convolution is of length $n+m-1$, while
the output of cross-correlation is of length $n-m+1$. This is due to the fact
that the cross-correlation operation does not calculate outputs for out-of-
region indices (see the difference between Figure 5 (i) and (ii) for an
example). To sum up, a cross-correlation is equivalent to a kernel-flipped and
truncated linear convolution. Moreover, the amount of truncation is controlled
by the amount of zero-padding on the signal $\mathbf{x}$ in cross-correlation.
For example, in Figure 5 (ii), there is no zero-padding and hence the result
is equivalent to truncate the first and last elements from the result in
Figure 5 (i); but consider if we zero-pad the signal $\mathbf{x}$ by $1$
element on both sides in Figure 5 (ii), then the result would be identical
with Figure 5 (i). In general, we found that if we zero-pad the signal
$\mathbf{x}$ by $m-1$ elements on both sides, a cross-correlation is
equivalent to a kernel-flipped linear convolution without any truncation. We
will discuss more about dealing with zero-padding in Appendix B.3.

#### Adapting circular convolution to cross-correlation in ConvNets.

Thus, based on these connections discussed above, we could now establish the
“equivalence” between circular convolution and cross-correlation based on
their connections to linear convolution, and hence adapt the proposed ConvNorm
in Algorithm 1 with cross-correlations in ConvNets via the following steps:

  1. 1.

Zero pad both sides of $\mathbf{z}_{in}$ by $m-1$ elements to get
$\dot{\mathbf{z}}_{in}$.

  2. 2.

Perform the cross-correlation between the kernel $\mathbf{a}$ and the input
$\dot{\mathbf{z}}_{in}$ to obtain the output $\mathbf{z}_{out}$.

  3. 3.

Apply ConvNorm on the kernel $\mathbf{a}$ and the output $\mathbf{z}_{out}$ as
stated in Algorithm 1 to get result $\widetilde{\mathbf{z}}_{out}$.

  4. 4.

Delete the first and last $(m-1)/2$ elements of $\widetilde{\mathbf{z}}_{out}$
and return as the resulting output.

Here, Step $1$ and Step $2$ are to generate the output $\mathbf{z}_{out}$ that
is almost identical to what used in ConvNets, with the exception of zero-
padding in Step $1$ so that it is equivalent to a circular convolution with a
flipped kernel $\check{\mathbf{a}}$. Then in Step $3$, we perform ConvNorm on
the output $\mathbf{z}_{out}$ and kernel $\mathbf{a}$. Notice that there is no
need to flip the kernel in the above steps since as described in Algorithm 1,
we only need to calculate the magnitude spectrum of a kernel and the magnitude
spectrum remains consistent with a kernel flipping, i.e.,
$\left|\mathbf{F}\mathbf{a}\right|=\left|\mathbf{F}\check{\mathbf{a}}\right|$.
Finally, Step $4$ is to obtain the desired output with the correct spatial
dimension.

Figure 5: A 1D example to illustrate relationships among different kinds of
convolutions. (i), (ii), and (iii) show the operations of linear convolution,
cross-correlation (i.e., the “convolution” used in ConvNets), and circular
convolution, respectively. (iv) gives an example of emulating linear
convolution in a circular convolution manner. (i), (ii) indicates that cross-
correlation is essentially a linear convolution with a flipped-kernel and
truncation. Hence from (i), (ii), (iv), we find equivalence between cross-
correlation and circular convolution.

###  B.3 Dealing with zero-paddings in ConvNets

Here, we provide more explanations about the zero-padding and truncation used
in Appendix B.2. Zero-padding is an operation of adding $0$s to the data,
which is widely used in modern ConvNets primarily aimed for maintaining the
spatial dimension of the outputs for each layer. For example, a standard
stride-$1$ convolution in ConvNets between a kernel
$\mathbf{a}\in\mathbb{R}^{m}$ and a signal $\mathbf{z}_{in}\in\mathbb{R}^{n}$
with $n>m$ produces a output vector $\mathbf{z}_{out}$ of length $n-m+1$. To
make the output $\mathbf{z}_{out}$ the same length as the input signal
$\mathbf{z}_{in}$, a zero-padding of $\lfloor m/2\rfloor$ is often used (e.g.,
common in various architectures such as VGG[60], ResNet[5].111111$\lfloor
m\rfloor$ is the floor operation which outputs the greatest integer less than
or equal to $m$. To handle with such zero-padding in ConvNorm, based on the
relationship between cross-correlation and circular convolution established in
Appendix B.2, we truncate the output of ConvNorm to make its spatial dimension
align with the dimension of the input signal $\mathbf{z}_{in}$. More
specifically, after Step $3$ in Appendix B.2, the resulting
$\widetilde{\mathbf{z}}_{out}$ has length $n+m-1$, in Step $4$ we then
truncate the first and last $(m-1)/2$ elements from it to make it has length
$n$ as the input signal.

###  B.4 Dealing with stride-$2$

Stride nowadays becomes an essential component in modern ConvNets [5, 76]. A
stride-$s$ convolution is a convolution with the kernel moving $s$ steps at a
time instead of $1$ step in a standard convolution shown in Figure 5.
Mathematically, for the kernel $\mathbf{a}$ and the input $\mathbf{z}_{in}$,
the stride-$s$ convolution can be written as

$\displaystyle\mathbf{z}_{out}=\mathcal{D}_{s}\left[\mathbf{a}\circledast\mathbf{z}_{in}\right],$

where $\mathcal{D}_{s}[\cdot]$ is a downsampling operator that selects every
$s$th sample and discards the rest. Therefore, the main purpose of stride is
for downsampling the output in ConvNets, replacing classical pooling methods.
Hence for convolution with stride-$s$, the dimension of the output decreases
by $s$ times in comparison to that of the standard stride-$1$ output. For
example, if we do a stride-2 convolution on Figure 5 (ii), we will get the
result $\mathbf{y}=[10]$ where the result is sampled from the standard
stride-$1$ convolution output and its size is halved.

When enforcing weight regularizations, recent work often cannot handle strided
convolution [29]. This happens because it involves weight matrix inversion,
and the stride and the downsampling operator cause the weight matrix to be
non-invertible. In contrast, since our method does not involve computing full
matrix inversion and it operates on the outputs instead of directly changing
the convolutional weights, we could first take a step back to perform an
unstrided convolution, then use ConvNorm to normalize the output and finally
do the stride (downsampling) operation on the normalized outputs.

###  B.5 Dealing with 2D kernels

Although in the main body of the work, 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. For an
illustration, let us consider (6), we know that in 1D case the preconditioning
matrix for each channel can be written in the form of

$\displaystyle\mathbf{P}_{k}\;$
$\displaystyle=\;\left(\sum_{j=1}^{C_{I}}\mathbf{C}_{\mathbf{a}_{kj}}\mathbf{C}_{\mathbf{a}_{kj}}^{\top}\right)^{-\frac{1}{2}}$
$\displaystyle=\;\left(\sum_{j=1}^{C_{I}}\mathbf{F}^{*}\operatorname{diag}(\widehat{\mathbf{a}}_{kj})\mathbf{F}\mathbf{F}^{*}\operatorname{diag}(\overline{\widehat{\mathbf{a}}}_{kj})\mathbf{F}\right)^{-\frac{1}{2}}=\;\mathbf{F}^{*}\left(\left(\sum_{j=1}^{C_{I}}\left|\operatorname{diag}(\widehat{\mathbf{a}}_{kj})\right|^{\odot
2}\right)^{\odot-\frac{1}{2}}\right)\mathbf{F},$

so that the output after ConvNorm can be rewritten as,

$\displaystyle\mathbf{P}_{k}\mathbf{z}_{k}\;$
$\displaystyle=\;\mathbf{F}^{*}\left(\sum_{j=1}^{C_{I}}\left|\operatorname{diag}(\widehat{\mathbf{a}}_{kj})\right|^{\odot
2})^{\odot-\frac{1}{2}}\right)\mathbf{F}\mathbf{z}_{k}\;=\mathbf{F}^{-1}\left(\sum_{j=1}^{C_{I}}\left|\mathbf{F}(\mathbf{a}_{kj})\right|^{\odot
2}\right)^{\odot-\frac{1}{2}}\mathbf{F}(\mathbf{z}_{k}),$

where $\mathbf{F}(\cdot)$ and $\mathbf{F}^{-1}(\cdot)$ denote the 1D Fourier
transform and the 1D inverse Fourier transform, respectively. To extend our
method to the 2D case, we can simply replace the 1D Fourier transform in the
above equation by the 2D Fourier transform. As summarized in Algorithm 1, to
deal with 2D input data, we replace every 1D Fourier transform with 2D Fourier
transform, which can be efficiently implemented via 2D FFT.

##  Appendix C Experimental details for Section 4

In this part of appendix, we provide detailed descriptions for the choices of
hyperparameters of baseline models, and introduce the settings for all
experiments conducted in Section 4.

###  C.1 Computing resources, assets license

We use two datasets for the demonstration purpose of this paper: CIFAR dataset
is made available under the terms of the MIT license and ImageNet dataset is
publicly available for free to researchers for non-commercial use. We refer
the code of some work during various stages of our implementation for
comparison and training purposes, we list them as follows: the implementation
of ONI [39] is made available under the BSD-2-Clause license; the
implementation of OCNN [43] is made available under the MIT license; the
training procedure for Table 1 refers to the implementation of the work [62]
which is made available under the MIT license and the black-box attack SimBA
[56] implementation is made available under the MIT license. All experiments
are conducted using RTX-8000 GPUs.

###  C.2 Choice of hyperparameters for baseline methods

In Section 4, we compare our method with three representative normalization
methods, that we describe the hyperparameter settings of each method below.

  * •

OCNN. Since the best penalty constraint constant $\lambda$ for OCNN is not
specified in [43], we do a hyperparameter tuning on the clean CIFAR-10 dataset
for $\lambda\in\\{0.001,0.01,0.05,0.1,1\\}$ and picked $\lambda=0.01$ from the
best validation set accuracy.

  * •

ONI. In the work [39], the authors utilize Newton’s iteration to approximate
the inverse of the covariance matrix for the reshaped weights. In our
experiments, we adopt the implementation and use the default setting from
their Github page where the maximum iteration number of Newton’s method is set
to $5$. We use a learning rate $0.01$ for all ONI experiments, where we notice
that a large learning rate $0.1$ makes the training loss explode to NaN.

  * •

SN. In [15], the authors use the power method to estimate the spectral norm of
the reshaped weight matrix and then utilize the spectral norm to rescale the
weight tensors. For all SN experiments, we directly use the official PyTorch
implementation of SN with the default settings where the iteration number is
set to $1$.121212The authors of SN take advantage of the fact that the change
of weights from each gradient update step is small in the SGD case (and thus
the change of the singular vector is small as well) and hence design the SN
algorithm so that the approximated singular vector from the previous step is
reused as the initial vector in the current step. They notice that $1$
iteration is sufficient in the long run.

###  C.3 Experimental details for Section 4.1

#### Robustness against adversarial attacks.

For gradient-based attacks, we follow the training procedure described in [62]
to train models with our ConvNorm and other baseline methods.131313For OCNN in
the gradient-based attack experiment, we choose $\lambda=0.0001$ since we
found that this setting yields the best OCNN robust performance. Then we use
Fast Gradient Sign Method (FGSM) [57] and Projected Gradient Method (PGD) [58]
as metrics to measure the robust performance of the trained models. We note
that the FGSM attack is defined to find adversarial examples in one iteration
by:

$\displaystyle\mathbf{x}_{adv}=\mathbf{x}+\epsilon*\operatorname{sign}(\nabla_{\mathbf{x}}\ell(\mathbf{x},\mathbf{y},\mathbf{\theta}))$

where $\mathbf{\theta}$ represents the model; $\mathbf{y}$ is the target for
data $\mathbf{x}$ and $\epsilon$ denotes the attack amount of this iteration.
PGD attack is an iterative version of FGSM with random noise perturbation as
attack initialization. In this paper, we use PGD-$k$ to denote the total
iterative steps (i.e., $k$ steps) for the attack methods. Adversarial attacks
are always governed by a bound on the norm of the maximum possible
perturbation, i.e.,
$\left\|\mathbf{x}_{adv}-\mathbf{x}\right\|_{p}\leq\delta_{p}$. We use
$\ell_{\infty}$ norm to constrain the attacks throughout this paper (i.e.,
$p=\infty$). Specifically, we adopt the procedure in [62] by choosing $m=4$
(the times of repeating training for each minibatch) and FGSM step
$\epsilon=\frac{8}{255}$ during training. And we set the attack bound
$\delta_{\infty}=\frac{8}{255}$.

For the black-box attack SimBA [56], we first train ResNet18 [5] models for
ConvNorm and other baseline methods without BatchNorm on the clean CIFAR-10
training images using the default experimental setting mentioned in Section
4.141414We choose to not adding BatchNorm in the SimBA experiment because we
empirically observe that removing BatchNorm improves the performance of every
method. Then we choose the best model for each method according to the best
validation set accuracy. Finally, we apply each of the selected models on the
held-out test set and randomly pick $1000$ correctly classified test samples
for running SimBA attack. We compare the performances of the selected models
with pixel attack using a step size $\varepsilon=0.4$. Since images in the
dataset have spatial resolution $32\times 32$ and $3$ color channels, the
attack runs in a total of $3\times 32\times 32=3072$ iterations. We then
report the average queries and attack success rate after all $3072$ iterations
in Table 2.

#### Robustness against label noise.

The label noise for CIFAR-10 is generated by randomly flipping the original
labels. Here we show the specific definition. We inject the symmetric label
noise to training and validation split of CIFAR-10 to simulate noisily labeled
dataset. The symmetric label noise is as follows:

$\mathbf{y}=\left\\{\begin{array}[]{lr}\mathbf{y}^{GT}\text{ with the
probability of $1-r$},\\\ \text{random one-hot vector with the probability of
$r$},\\\ \end{array}\right.$

where $r\in[0,1]$ is the noise level. The models (using ResNet18 as backbones)
are trained on noisily labeled training set (45000 examples) under the default
experimental setting mentioned in Section 4. Max test accuracy is then
reported on the held-out test set.

#### Robustness against data scarcity

We randomly sample [10%, 30%, 50%, 70%] of the training data set CIFAR-10
dataset while keeping the amount of validation and test set amount unchanged.
The model is trained on sub-sampled training set using the default
experimental setting mentioned in Section 4. We report the accuracy on the
held out test set by evaluating the best model selected on the validation set
(obtained by randomly sampling 10% of the original training set).

Train |  Test
---|---
|
Figure 6: Adding ConvNorm before BatchNorm accelerates convergence and
improves performance. Train and test accuracy of ResNet18 trained on CIFAR-10
with and without ConvNorm or BatchNorm under default settings mentioned in
Section 4. Error bars correspond to min/max over 3 runs.

###  C.4 Generalization experiment and experimental details for Section 4.2

#### Improved performances on supervised learning.

Below we provide the generalization experiment and more detailed experiment
settings for fast training and generalization mentioned in Section 4.2. We use
the default training setting mentioned in the Setups of Dataset and Training
of Section 4 if not otherwise specified.

  * •

_Faster training._ In order to isolate the effects of normalization
techniques, we drop all regularization techniques including: data
augmentations, weight decay, and learning rate decay as we have mentioned in
the caption of Figure 4. For extra experiments on the same analysis when these
regularization techniques are included, please refer to Appendix D and the
results in Figure 6.

  * •

_Better generalization._ We use the default setting as we have mentioned in
the Setups of Dataset and Training of Section 4. All normalization methods are
evaluated under this setting. We demonstrate the test accuracy of our method
on CIFAR and ImageNet under standard settings. As shown in Table 4, although
only using ConvNorm results in slightly worse test accuracy against BatchNorm,
adding ConvNorm before standard BatchNorm layers can boost the performance
while maintaining fast convergence (see Figure 6). Additionally, we
investigate the influence of combining the affine transform and BatchNorm with
ConvNorm. Table 5 shows the results of our ablation study on the CIFAR-10
dataset. Both affine transform and batch norm provide an independent
performance boost.

Dataset | Backbone | vanilla | BatchNorm(BN) | ConvNorm | ConvNorm + BN
---|---|---|---|---|---
CIFAR-10 | ResNet18 | 91.58 $\pm$ 0.67 | 93.18 $\pm$ 0.16 | 92.12 $\pm$ 0.32 | 93.31 $\pm$ 0.17
CIFAR-100 | ResNet18 | 66.59 $\pm$ 0.72 | 73.06 $\pm$ 0.13 | 68.20 $\pm$ 0.27 | 73.38 $\pm$ 0.24
ImageNet | ResNet18 | / | 69.76 | - | 70.34

Table 4: Results on classification. Test accuracy on CIFAR-10, CIFAR-100, and
ImageNet validation sets. For each case, we compare different combinations of
ConvNorm and BatchNorm. Results of CIFAR-10 and CIFAR-100 are averaged over 4
random seeds, and "/" represents failed training.

|  | Batch Norm
---|---|---
|  | ✓ | ✗
Affine Transform | ✓ | 93.31 $\pm$ 0.17 | 92.12 $\pm$ 0.32
✗ | 93.18 $\pm$ 0.16 | 92.01 $\pm$ 0.21

Table 5: Ablation study. The influence of the affine transform and batch
normalization for classification on the CIFAR10 dataset is evaluated. The mean
test accuracy and its standard deviation are computed over three random seeds.

#### Training details for GAN

For GAN training, the parameter settings and model architectures for our
method follow strictly with that in [15] and its official implementation for
the training settings. More specifically, we use Adam
($\beta_{1}=0,\beta_{2}=0.9$) for the optimization with learning rate
$0.0002$. We update the discriminator $5$ times per update of the generator.
The batchsize is set to $64$. We adopt two performance measures, Inception
score and FID to evaluate the images produced by the trained generators. The
ConvNorm is added after every convolution layer in the discriminator of GAN.

##  Appendix D Additional experiments and ablation study

In this section, we perform a more comprehensive ablation study to evaluate
the influences of each additional component of ConvNorm on the tasks that we
conducted in Section 4. More specifically, we study the benefits of the extra
convolutional affine transform that we introduced in Section 3.3, as well as
an inclusion of a BatchNorm layer right after the ConvNorm.

#### Fast training and better generalization.

In Figure 4, we show that ConvNorm accelerates convergence and achieve better
generalization performance with or without BatchNorm when regularizations such
as data augmentation, weight decay, and learning rate decay are dropped during
training. Figure 6 shows that when these standard regularization techniques
are added, fast convergence of ConvNorm can still be observed (see the blue
curve with circles and the yellow curve with triangles).

| Label Noise Ratio
---|---
| 20% | 40% | 60% | 80%
ConvNorm + BN | 88.94 $\pm$ 0.36 | 85.88 $\pm$ 0.26 | 79.54 $\pm$ 0.73 | 69.26 $\pm$ 0.59
ConvNorm | 87.75 $\pm$ 0.13 | 84.16 $\pm$ 0.71 | 77.48 $\pm$ 0.26 | 54.11 $\pm$ 2.65
BN | 86.98 $\pm$ 0.12 | 81.88 $\pm$ 0.29 | 74.14 $\pm$ 0.56 | 53.82 $\pm$ 1.04
Vanilla | 85.94 $\pm$ 0.25 | 82.11 $\pm$ 0.52 | 76.75 $\pm$ 0.20 | 57.20 $\pm$ 0.71

Table 6: Adding ConvNorm and BatchNorm together makes a network more robust to
label noise. The influence of BatchNorm and ConvNorm for label noise on the
CIFAR-10 dataset is evaluated. The mean test accuracy and its standard
deviation are computed over three random seeds.

| Subset Percent
---|---
| 10% | 30% | 50% | 70%
ConvNorm + BN | 77.96 $\pm$ 0.11 | 87.66 $\pm$ 0.23 | 90.49 $\pm$ 0.17 | 90.71 $\pm$ 0.15
ConvNorm | 69.23 $\pm$ 0.94 | 83.93 $\pm$ 0.34 | 87.83 $\pm$ 0.21 | 89.85 $\pm$ 0.10
BN | 67.10 $\pm$ 2.59 | 84.24 $\pm$ 0.51 | 88.74 $\pm$ 0.73 | 90.41 $\pm$ 0.33
Vanilla | 67.56 $\pm$ 0.50 | 81.98 $\pm$ 0.78 | 86.57 $\pm$ 0.35 | 87.61 $\pm$ 0.86

Table 7: Adding ConvNorm and BatchNorm together helps improve data efficiency
The influence of BatchNorm and ConvNorm for data scarcity on the CIFAR-10
dataset is evaluated. The mean test accuracy and its standard deviation are
computed over three random seeds.

#### Robustness against label noise and data scarcity.

In Figure 3, we show that adding a BatchNorm layer after the ConvNorm can
further boost the performance against label noise and data scarcity compared
with combining other baseline methods with BatchNorm.

Here, to better understand the influence of each component, we study the
effects of ConvNorm and BatchNorm separately. When we only use the ConvNorm
without BatchNorm, from Table 6 and Table 7 we observe that in comparison to
vanilla settings ConvNorm improves the performance against label noise and
data scarcity for the most cases. In contrast, when only the BatchNorm is
adopted, the performance downgrades that it improves upon the vanilla setting
in some cases. Additionally, we notice that when we add $80\%$ of label noise
to the training data, combining ConvNorm and BatchNorm together provides the
best performance while using anyone alone would result in worse performance.

#### Comparasion with Cayley Transfrom [29].

As mentioned in Section 1, a very recent work [29] shares some common ideas
with our work in terms of exploring convolutional structures in the Fourier
domain. We note that the major difference between [29] and our work lies in
the trade-off between the degree of orthogonality enforced and the associated
computational burden. As shown in Table 8, we empirically compare the run time
for training one epoch of CIFAR-10 dataset on a ResNet18 backbone using
different methods. We observe that both our method and [29] requires more time
to train compared with the vanilla network. But since our ConvNorm explores
channel-wise orthogonalization instead of layer-wise as done in [29], ConvNorm
achieves faster training and [29] achieves more strict orthogonalization
compared to each other. Also, we note that in terms of scalability, our
ConvNorm could be adapted in larger networks such as ResNet50 and ResNet152,
while the same experiments could not be carried on for [29] due to the
limitation of our computational resources. Another important factor for
comparison is the adversarial robustness. Based on our preliminary results, we
found that ConvNorm has accuracy $46.12$ under PGD-10 attack, which
outperforms the result of Cayley transform $38.35$ under the same attack. But
we note that since the experiment settings in [29] are very different with
ours, this comparison is not entirely fair as we have not done a comprehensive
tuning for the Cayley transform method. We conjecture that with appropriate
parameters and settings, the Cayley transform method could achieve on-par or
even better results than ConvNorm since the more strict orthogonality
enforced.

| Vanilla | ConvNorm | Cayley transfrom
---|---|---|---
Training time (epoch) | 21s | 60s | 182s

Table 8: Training time per epoch for different methods The average training
time for one epoch of different weight normalization methods is evaluated.
Experiments are conducted CIFAR-10 dataset with a ResNet18 backbone.

#### Layer-wise condition number.

In Figure 2, we have shown that ConvNorm could improve the channel-wise
condition number and layer-wise spectral norm. In this section, we empirically
compare the layer-wise condition number of different normalization methods. We
note that we use the method described in [51] to estimate the singular values
and condition numbers of the actual convolution operators from each layer, not
the weight matrix. Here, we define a metric $\rho$ to quantify the average
ratio of the condition number of the vanilla method and other methods

$\displaystyle\rho:=\frac{1}{L}\sum_{l=1}^{L}\frac{\text{Condition number
(Vanilla)}}{\text{Condition number (Method}_{j}})$

for characterizing the improvement upon the vanilla method (the larger, the
better). From Table 9, we observe that our ConvNorm shows the best result in
terms of improvement of layer-wise condition number as compared with other
methods. We note that we did not compare with Cayley transform [29] because it
inherently enforces more strict orthogonality than our ConvNorm based on their
experiments, so we conjecture that Cayley transform could have better
condition number than our ConvNorm.

| SN | ONI | OCNN | ConvNorm
---|---|---|---|---
$\rho$ | 2.724 | 0.001 | 2.288 | 3.332

Table 9: Average layer-wise condition number ratio of vanilla method on top of
other methods The experiments are conducted on natural settings with the same
set of hyperparameter of Table 1.