Convolution, Recurrence and Normalisation

Equivariance as the defining property of convolution, the Fourier view, the vanishing-gradient computation for RNNs, and the LSTM gating equations derived from it.

Deep LearningAdvanced⏱ 3 hours13 min readconvolutionequivariancefouriercnnrnn

6 problems →

AssumesApproximation Theory and Backpropagation

Convolution is forced by equivariance

DefinitionDiscrete convolution

For signals on $\Z_n$ (cyclically indexed),

(k * x)[i] = \sum_{j\in\Z_n} k[j]\,x[i-j] .

Let $T_s$ denote the shift $(T_sx)[i] = x[i-s]$ .

TheoremTranslation-equivariant linear maps are exactly convolutions

Let $A:\R^{\Z_n}\to\R^{\Z_n}$ be linear. Then

A T_s = T_s A \quad\text{for all } s\in\Z_n \qquad\Longleftrightarrow\qquad Ax = k*x \ \text{ for some } k .

Key idea

Convolution is not a clever choice of architecture; it is the only linear map commuting with translation. So a designer who wants translation equivariance has no freedom at all in the linear part — the weight sharing in a CNN is a theorem, not a heuristic. This is the template for the whole geometric-deep-learning programme: fix a symmetry group, and the equivariant linear maps are forced. Cohen and Welling carry this out for rotations and reflections.

TheoremConvolution theorem

Let $\hat x[\omega] = \sum_i x[i]e^{-2\pi\i\omega i/n}$ be the discrete Fourier transform. Then

\widehat{k*x}[\omega] = \hat k[\omega]\,\hat x[\omega].

Equivalently: the Fourier basis diagonalises every convolution operator simultaneously, with eigenvalues $\hat k[\omega]$ .

PropositionReceptive field growth

Stacking $L$ convolutions of kernel size $k$ with stride $1$ gives receptive field $1 + L(k-1)$ — linear in depth. Using dilation $2^{\ell}$ at layer $\ell$ gives receptive field $1+(k-1)(2^L-1)$ — exponential in depth.

Pooling and stride have the same effect by a different mechanism: they reduce spatial resolution so that a fixed kernel covers a larger fraction of the original input. Note that pooling also destroys equivariance and replaces it with approximate invariance — a max over a window is unchanged by small shifts within the window, which is what is wanted at the output but not in the middle.

Recurrence and the vanishing gradient

DefinitionVanilla RNN

h_t = \rho\big(W h_{t-1} + Ux_t + b\big),\qquad t=1,\dots,T,

with output $\hat y = g(h_T)$ and loss $\mathcal{J}$ .

PropositionThe RNN gradient is a product of recurrent Jacobians

\frac{\partial\mathcal{J}}{\partial h_1} = \left(\prod_{t=2}^{T} \diag\big(\rho'(z_t)\big)W^\top\right)\frac{\partial\mathcal{J}}{\partial h_T},

where $z_t = Wh_{t-1}+Ux_t+b$ . Consequently

\left\|\frac{\partial\mathcal{J}}{\partial h_1}\right\|_2 \le \big(\norm{\rho'}_\infty\norm{W}\big)^{T-1}\left\|\frac{\partial\mathcal{J}}{\partial h_T}\right\|_2 .

If $\norm{\rho'}_\infty\norm W<1$ the gradient vanishes exponentially in $T$ ; if $\sigma_{\min}(W)\norm{\rho'}>1$ it explodes.

Key idea

For $\tanh$ , $\norm{\rho'}_\infty = 1$ , so stability requires $\norm W \approx 1$ exactly — a measure-zero condition. Either the gradient dies and the network cannot learn dependencies beyond a few dozen steps, or it explodes and training diverges. Gradient clipping addresses the explosion (it bounds the step, at the cost of biasing the direction); nothing about a vanilla RNN addresses the vanishing.

PropositionThe LSTM cell state has an additive path

The LSTM equations are

\begin{aligned} f_t &= \sigma(W_f[h_{t-1},x_t]+b_f) &&\text{(forget)}\\ i_t &= \sigma(W_i[h_{t-1},x_t]+b_i) &&\text{(input)}\\ o_t &= \sigma(W_o[h_{t-1},x_t]+b_o) &&\text{(output)}\\ \tilde c_t &= \tanh(W_c[h_{t-1},x_t]+b_c) &&\text{(candidate)}\\ c_t &= f_t\odot c_{t-1} + i_t\odot\tilde c_t &&\text{(cell state)}\\ h_t &= o_t\odot\tanh(c_t). &&\text{(hidden state)} \end{aligned}

Along the cell-state path,

\frac{\partial c_t}{\partial c_{t-1}} = \diag(f_t), \qquad\text{so}\qquad \frac{\partial c_T}{\partial c_1} = \diag\left(\prod_{t=2}^{T}f_t\right)

(ignoring the indirect dependence through $h_{t-1}$ ). With $f_t \approx 1$ this product is $\approx1$ for any $T$ .

Key idea

Compare the two propositions. In a vanilla RNN the gradient is a product of matrices $W^\top$ , whose norm is generically $\ne1$ and cannot be controlled per time step. In an LSTM the cell-state gradient is a product of diagonal matrices with entries in $(0,1)$ , and each entry is learned. Setting $f_t\approx1$ gives an identity path — the "constant error carousel" of the original paper — so the network can learn which information to preserve and for how long. The gating is not a heuristic addition; it is the minimal modification that turns an uncontrollable matrix product into a controllable scalar one.

The GRU makes the same move with fewer parameters, coupling the input and forget gates:

h_t = (1-z_t)\odot h_{t-1} + z_t\odot\tilde h_t ,

so the Jacobian along the state path is $\diag(1-z_t)$ . Residual connections in a transformer are the same idea again with the gate fixed at $1$ : $\partial(x+F(x))/\partial x = I + \partial F/\partial x$ .

Normalisation

DefinitionBatch and layer normalisation

For a pre-activation $z$ , both compute $\hat z = \gamma\odot\frac{z-\mu}{\sqrt{\sigma^2+\eps}}+\beta$ ; they differ in what the statistics are computed over:

Batch norm: $\mu,\sigma^2$ per feature, averaged over the batch. Depends on other examples; requires running statistics at inference.
Layer norm: $\mu,\sigma^2$ per example, averaged over features. Independent of the batch, which is why it is used in transformers and in any setting with variable-length sequences or batch size one.
RMS norm: layer norm without mean subtraction, $\hat z = \gamma\odot z/\sqrt{\overline{z^2}+\eps}$ .

PropositionNormalisation makes the layer scale-invariant in its weights

If $\hat z = (Wx - \mu)/\sigma$ with $\mu,\sigma$ the empirical mean and standard deviation of $Wx$ , then replacing $W$ by $cW$ for $c>0$ leaves $\hat z$ unchanged. Consequently the gradient with respect to $W$ satisfies

\nabla_{cW}\mathcal{J} = \frac1c\nabla_W\mathcal{J}\Big|_{W} ,

so the effective step size scales as $1/\norm W^2$ relative to the direction of $W$ .

This is a genuine and often-overlooked consequence: with normalisation, the norm of a weight matrix has no effect on the function, only on the effective learning rate. Weight decay in a normalised network therefore acts purely as a learning-rate schedule, which explains several otherwise puzzling empirical observations about the interaction of weight decay and learning rate.

Empirical observationWhy batch normalisation helps is not settled

Empirical observation — a regularity seen in experiments. No theorem on this page establishes it in general.

Batch norm reliably accelerates training and permits larger learning rates. The original explanation — that it reduces "internal covariate shift" — has been directly challenged.

What this does not say

Santurkar et al. ran the decisive experiment: they injected non-zero-mean, time-varying noise after batch norm layers, deliberately restoring covariate shift, and the training speed-up persisted. So covariate shift reduction is not the mechanism, or at least not the whole one.

Their proposed alternative is that batch norm makes the loss landscape smoother, with smaller and more predictable gradient and Hessian norms along the training path, which permits larger stable steps. They provide supporting measurements and some analysis in restricted settings. Other proposed mechanisms include the scale-invariance effect above and an implicit regularisation from batch noise.

The state of knowledge: batch norm works, the original explanation is wrong, and there are several partial explanations with supporting evidence and no consensus. This is a good example of a case where the engineering is far ahead of the theory, and of why it is worth labelling such claims as empirical rather than presenting a plausible story as established.

Problems

Translation-equivariant linear maps are convolutionsProof · Intermediate · 30 min Convolution diagonalises in the Fourier basisProof · Intermediate · 30 min Receptive field growth with depth and dilationNumerical · Beginner · 15 min The RNN gradient is a repeated matrix productProof · Intermediate · 30 min The LSTM cell-state JacobianProof · Advanced · 30 min Normalisation makes weights scale-invariantProof · Advanced · 30 min

References

PaperYann LeCun and collaborators (1989). Backpropagation Applied to Handwritten Zip Code Recognition
PaperSepp Hochreiter and Jürgen Schmidhuber (1997). Long Short-Term Memory
PaperRazvan Pascanu, Tomas Mikolov and Yoshua Bengio (2013). On the difficulty of training Recurrent Neural Networks
PaperSergey Ioffe and Christian Szegedy (2015). Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
PaperShibani Santurkar, Dimitris Tsipras, Andrew Ilyas and Aleksander Mądry (2018). How Does Batch Normalization Help Optimization?
PaperTaco S. Cohen and Max Welling (2016). Group Equivariant Convolutional Networks

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

TheoremTranslation-equivariant linear maps are exactly convolutionsproof includedEquivariance is not a property convolution happens to have; it characterises convolution completely.
TheoremConvolution theoremproof includedConvolution becomes pointwise multiplication in the Fourier basis, which diagonalises every convolution at once.
PropositionReceptive field growthproof includedStacked convolutions grow the receptive field linearly, dilation grows it exponentially.
PropositionThe RNN gradient is a product of recurrent Jacobiansproof includedBackpropagation through time multiplies the same matrix T times, so the gradient decays or explodes exponentially in the sequence length.
PropositionThe LSTM cell state has an additive path with Jacobian equal to the forget gateproof includedGating replaces a matrix product by a product of scalars in (0,1), which is what makes long-range gradients survivable.
Empirical observationWhy batch normalisation helps is not settledThe original internal-covariate-shift explanation has been challenged; smoothing of the loss landscape is the leading alternative.

Problems (6)

All problems

Convolution is forced by equivariance

Recurrence and the vanishing gradient

Normalisation

Problems

References

Results stated on this page

Problems (6)

Papers that use this mathematics