Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

Convolutional Networks in Depth

Weight sharing, receptive fields and equivariance.

Why convolution, of all linear maps? Because it is the only one that treats every position alike: any linear layer that commutes with translations is a convolution. That one fact explains weight sharing, gives convolutions a Fourier diagonalization and fast algorithms, and frames today's questions about which symmetries to build in and which to learn.

What you’ll learn

  • Prove that a linear map on signals commutes with all translations if and only if it is a convolution, and state the group-equivariant generalization.
  • Diagonalize convolutions with the discrete Fourier transform, and compare the costs of direct, FFT, Winograd and depthwise-separable convolution.
  • Compute theoretical receptive fields, including dilations, and explain why effective receptive fields are roughly Gaussian and grow only like the square root of depth.
  • Explain how striding and pooling break shift equivariance through aliasing, and weigh built-in inductive bias against data and scale.

Convolution is forced by translation equivariance

DerivationProof
  1. ((Stx)∗h)[r]=∑kx[k−t] h[r−k]=∑k′x[k′] h[(r−t)−k′]=(x∗h)[r−t]=(St(x∗h))[r]\big((S_tx)*h\big)[r]=\sum_kx[k-t]\,h[r-k]=\sum_{k'}x[k']\,h[(r-t)-k']=(x*h)[r-t]=\big(S_t(x*h)\big)[r]

    (⇐\Leftarrow) Convolution commutes with shifts, by a change of summation index:

  2. Tx=∑kx[k] T(Skδ0)=∑kx[k] Sk(Tδ0)=∑kx[k] SkhTx=\sum_kx[k]\,T(S_k\delta_0)=\sum_kx[k]\,S_k(T\delta_0)=\sum_kx[k]\,S_kh

    (⇒\Rightarrow) Expand xx in impulses, x=∑kx[k] δkx=\sum_kx[k]\,\delta_k, use linearity, and note that δk=Skδ0\delta_k=S_k\delta_0:

  3. (Tx)[r]=∑kx[k] h[r−k]=(x∗h)[r],Trk=h[r−k](Tx)[r]=\sum_kx[k]\,h[r-k]=(x*h)[r],\qquad T_{rk}=h[r-k]

    Read off entry rr using (Skh)[r]=h[r−k](S_kh)[r]=h[r-k]: this is the convolution. Uniqueness follows by applying both sides to δ0\delta_0.

So weight sharing is not a design choice added on top of equivariance: for linear maps it is equivariance. Locality, a kernel supported on a small window, is a separate assumption, the prior that nearby pixels matter most. Per pair of channels, a general linear map on nn positions has n2n^2 weights, an equivariant one nn, and a local equivariant one k≪nk\ll n.

The theorem generalizes. For a group GG acting on the domain, the linear maps equivariant to GG are group convolutions, (f∗ψ)(g)=∑h∈Gf(h) ψ(h−1g)(f*\psi)(g)=\sum_{h\in G}f(h)\,\psi(h^{-1}g), with suitably constrained kernels when the group also acts on the feature channels. Cohen & Welling (2016) built CNNs equivariant to rotations by 90∘90^\circ and reflections, and Kondor & Trivedi (2018) proved that for compact groups, equivariance forces a generalized convolution form. Steerable and spherical CNNs, and graph networks equivariant to node permutations, follow the same pattern.

Check your understanding

How many free parameters does a linear, translation-equivariant map on signals of length nn (circular boundary) have, and how many if it is also local with a window of kk entries?

  1. n2n^2 and k2k^2
  2. nn and kk
  3. 11 and 11
  4. n(n+1)/2n(n+1)/2 and kk
Show the answer

B. nn and kk

A circulant matrix is determined by its first column h=Tδ0h=T\delta_0: nn numbers. Locality forces hh to vanish outside a window of kk entries. For a layer from CinC_{\text{in}} to CoutC_{\text{out}} channels on n×nn\times n images, that is CinCoutn2C_{\text{in}}C_{\text{out}}n^2 weights if merely equivariant, and CinCoutk2C_{\text{in}}C_{\text{out}}k^2 if also local.

The Fourier view and the cost of convolution

Shifts commute with one another, so they share eigenvectors: the Fourier modes eω[r]=e2πiωr/n\mathbf e_\omega[r]=e^{2\pi i\omega r/n}, with Steω=e−2πiωt/n eωS_t\mathbf e_\omega=e^{-2\pi i\omega t/n}\,\mathbf e_\omega. Every map that commutes with all shifts is diagonal in the same basis, which is the convolution theorem:

x∗h^[ω]=x^[ω] h^[ω],x^[ω]=∑r=0n−1x[r] e−2πiωr/n,T=F−1diag⁡(h^) F\widehat{x*h}[\omega]=\hat x[\omega]\,\hat h[\omega],\qquad\hat x[\omega]=\sum_{r=0}^{n-1}x[r]\,e^{-2\pi i\omega r/n},\qquad T=F^{-1}\operatorname{diag}(\hat h)\,F
The DFT matrix FF diagonalizes every circulant matrix at once, and h^\hat h is the layer's frequency response: the equivariant linear layers are exactly the Fourier multipliers.

The diagonalization also gives fast algorithms. For an n×nn\times n image and a k×kk\times k kernel, direct convolution costs about n2k2n^2k^2 multiply-adds per pair of channels, while FFTs cost O(n2log⁡n)\order{n^2\log n} whatever kk is, which wins for large kernels. Networks mostly use 3×33\times3 kernels, for which minimal-filtering algorithms are better: Winograd's F(2×2,3×3)F(2\times2,3\times3) computes a 2×22\times2 tile of outputs with (2+3−1)2=16(2+3-1)^2=16 multiplications instead of 36, a 2.25-fold saving, at the price of extra additions and some loss of numerical accuracy (Lavin & Gray, 2016).

LayerMultiply-adds per output positionWeights
Standard k×kk\times k convolutionk2CinCoutk^2C_{\text{in}}C_{\text{out}}k2CinCoutk^2C_{\text{in}}C_{\text{out}}
Pointwise (1×11\times1) convolutionCinCoutC_{\text{in}}C_{\text{out}}CinCoutC_{\text{in}}C_{\text{out}}
Depthwise k×kk\times k (one filter per channel)k2Cink^2C_{\text{in}}k2Cink^2C_{\text{in}}
Depthwise-separable (depthwise, then pointwise)Cin(k2+Cout)C_{\text{in}}(k^2+C_{\text{out}})Cin(k2+Cout)C_{\text{in}}(k^2+C_{\text{out}})
Biases omitted. Depthwise-separable layers (Sifre, 2014; Chollet, 2017; MobileNets, Howard et al., 2017) factor spatial filtering from channel mixing.
Predict before you look

A 3×33\times3 convolution maps 256 channels to 256 channels. By what factor does a depthwise-separable replacement cut its multiply-adds?

Show the answer

8.7

The cost ratio is Cin(k2+Cout)k2CinCout=1Cout+1k2=1256+19≈0.115\frac{C_{\text{in}}(k^2+C_{\text{out}})}{k^2C_{\text{in}}C_{\text{out}}}=\frac1{C_{\text{out}}}+\frac1{k^2}=\frac1{256}+\frac19\approx0.115, about 8.7 times fewer. For many output channels the saving approaches k2=9k^2=9. The price is a more constrained layer, usually offset by adding channels or depth.

Receptive fields: theoretical and effective

The theoretical receptive field is a worst case: it counts every pixel with any influence. Luo, Li, Urtasun & Zemel (2016) measured the effective receptive field, the map of ∣∂y/∂xu∣\abs{\partial y/\partial x_{\mathbf u}} showing how strongly each input pixel affects a central output. It is roughly Gaussian and fills only a fraction of the theoretical field.

DerivationWhy the effective field is Gaussian, with width growing like the square root of depth
  1. ∂y∂x=w∗w∗⋯∗w⏟L times\frac{\partial y}{\partial x}=\underbrace{w*w*\cdots*w}_{L\ \text{times}}

    Take a linear network of LL stride-1 layers that all convolve with the same nonnegative kernel ww, normalized so that ∑uw[u]=1\sum_uw[u]=1, with mean offset μ\mu and variance σ2\sigma^2. Backpropagating an impulse from one output convolves it with ww once per layer:

  2. ∂y∂xu ≈ N(Lμ, Lσ2) evaluated at u\frac{\partial y}{\partial x_{\mathbf u}}\ \approx\ \mathcal N\big(L\mu,\ L\sigma^2\big)\ \text{evaluated at }\mathbf u

    That is the distribution of a sum U1+⋯+ULU_1+\dots+U_L of independent offsets with Ul∼wU_l\sim w, which by the central limit theorem approaches a Gaussian:

  3. effective widththeoretical width∼σL(k−1) L=O(L−1/2)\frac{\text{effective width}}{\text{theoretical width}}\sim\frac{\sigma\sqrt L}{(k-1)\,L}=\order{L^{-1/2}}

    So the effective width grows like σL\sigma\sqrt L while the theoretical width grows like (k−1)L(k-1)L. Luo et al. extend the argument to random weights and nonlinearities, and observe that training, downsampling and dilation all enlarge the effective field.

Classification needs invariance, not equivariance. Networks get it by a final global average pool, which is exactly shift-invariant on a circular grid, or by downsampling until little spatial extent remains. Where the object sits in the image is then ignored, which is the intended inductive bias.

Aliasing and the limits of built-in symmetry

Strided convolutions and pooling are equivariant only to shifts by multiples of the total stride. A stride-ss layer samples its output every ss pixels, and any frequency content above half the new sampling rate aliases, so a one-pixel shift of the input can change the downsampled features substantially. Azulay & Weiss (2019) showed that the predictions of modern CNNs can change under shifts of a single pixel, and Zhang (2019) restored much of the stability by low-pass filtering before each downsampling, as classical signal processing prescribes.

Think first The 1-D signal 1,0,1,0,…1,0,1,0,\dots is downsampled by 2, before and after a one-pixel shift, in three ways: max pooling over pairs, plain subsampling (keep every second sample), and blurring with [12,12][\tfrac12,\tfrac12] before subsampling. What comes out?

Max pooling over the pairs [1,0][1,0] or [0,1][0,1] gives all ones both times, stable here by luck. Plain subsampling gives 1,1,1,…1,1,1,\dots before the shift and 0,0,0,…0,0,0,\dots after: the highest frequency, above the new Nyquist limit, aliases to a constant whose value depends on the phase. Blurring first gives 12,12,…\tfrac12,\tfrac12,\dots either way, the idea behind anti-aliased pooling.

How much does built-in structure buy? For images, a lot when data are scarce. Vision transformers, with almost no spatial prior, trail CNNs when trained on ImageNet alone but match or beat them after pretraining on hundreds of millions of images (Dosovitskiy et al., 2021), and a convolutional network modernized with transformer-era design choices and training recipes matches them again (ConvNeXt; Liu et al., 2022). Theory offers one sharp example: Li, Zhang & Arora (2021) built a task that a convolutional network learns from O(1)\order{1} samples, while any algorithm equivariant to orthogonal transformations of the input, a class that includes fully connected networks trained by gradient descent from Gaussian initialization, needs Ω(d2)\Omega(d^2) samples in dimension dd.

Key takeaways

  • A linear map commutes with all translations iff it is a convolution with h=Tδ0h=T\delta_0, a circulant matrix: weight sharing is equivariance, and locality is a separate prior. For compact groups, equivariance likewise forces group convolutions.
  • The DFT diagonalizes every convolution, giving O(n2log⁡n)\order{n^2\log n} FFT methods for large kernels; for 3×33\times3 kernels Winograd's F(2×2,3×3)F(2\times2,3\times3) saves a factor 2.25 in multiplications, and depthwise-separable layers cut the cost by the factor 1/Cout+1/k21/C_{\text{out}}+1/k^2.
  • Theoretical receptive fields grow as 1+∑ldl(kl−1)∏i<lsi1+\sum_ld_l(k_l-1)\prod_{i<l}s_i; effective ones are roughly Gaussian with width proportional to L\sqrt L, a shrinking fraction of the theoretical field.
  • Strides and pooling keep equivariance only for shifts by multiples of the stride, and aliasing makes CNNs sensitive to one-pixel shifts. How much built-in symmetry is worth, relative to data and scale, is an open empirical question.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Which of these linear maps on RZn\R^{\Z_n}, with circular indexing, commutes with every shift?

  1. x↦x[0]⋅1x\mapsto x[0]\cdot\mathbf 1, broadcasting the first entry
  2. x↦(x[r]−x[r−1])rx\mapsto(x[r]-x[r-1])_r, the discrete difference
  3. x↦(r x[r])rx\mapsto(r\,x[r])_r, multiplication by position
  4. x↦(x[−r])rx\mapsto(x[-r])_r, the reversal
Show the answer

B. x↦(x[r]−x[r−1])rx\mapsto(x[r]-x[r-1])_r, the discrete difference

The difference is convolution with the kernel h=δ0−δ1h=\delta_0-\delta_1, so it commutes with shifts. Broadcasting x[0]x[0] singles out a position, multiplication by rr is a diagonal rather than circulant matrix, and reversal satisfies RSt=S−tRRS_t=S_{-t}R instead.

Question 2

For a single-channel n×nn\times n image and a k×kk\times k kernel, when does FFT-based convolution beat the direct method in multiplications, roughly?

  1. Always, since FFTs are fast
  2. When k2k^2 exceeds a constant times log⁡n\log n, that is, for large kernels
  3. Only for k=1k=1
  4. Never, because the FFT needs complex arithmetic
Show the answer

B. When k2k^2 exceeds a constant times log⁡n\log n, that is, for large kernels

Direct convolution costs about n2k2n^2k^2; the FFT route costs O(n2log⁡n)\order{n^2\log n} for the transforms plus n2n^2 pointwise products, independent of kk. Large kernels favor the FFT; for 3×33\times3 kernels direct and Winograd methods win, which is why libraries choose the algorithm layer by layer.

Question 3

A stack of LL stride-1 3×33\times3 convolutions has a theoretical receptive field of width 2L+12L+1. By the central-limit argument, how does the width of its effective receptive field grow?

  1. Like 2L+12L+1 as well
  2. Like log⁡L\log L
  3. It stays at 3
  4. Like L\sqrt L
Show the answer

D. Like L\sqrt L

The backpropagated influence of the input pixels is the LL-fold convolution of one kernel's weight profile, the distribution of a sum of LL independent offsets: approximately Gaussian, with standard deviation proportional to L\sqrt L. Effective fields therefore fill a shrinking fraction, O(1/L)\order{1/\sqrt L}, of the theoretical ones.

Question 4

Why can a CNN with stride-2 layers change its prediction when the input shifts by one pixel, despite convolution's equivariance?

  1. Because convolution is not equivariant at all
  2. Because ReLU is not shift-equivariant
  3. Because downsampling preserves equivariance only for shifts by multiples of the stride, and high-frequency content aliases
  4. Because the classifier head memorizes pixel positions
Show the answer

C. Because downsampling preserves equivariance only for shifts by multiples of the stride, and high-frequency content aliases

Keeping every second sample commutes with shifts by 2, not by 1. Frequencies above the new Nyquist limit fold into lower ones, so a one-pixel shift can change the subsampled features. Low-pass filtering before subsampling restores much of the stability.

Further reading

  • T. Cohen & M. Welling, "Group equivariant convolutional networks," ICML (2016).
  • R. Kondor & S. Trivedi, "On the generalization of equivariance and convolution in neural networks to the action of compact groups," ICML (2018).
  • W. Luo, Y. Li, R. Urtasun & R. Zemel, "Understanding the effective receptive field in deep convolutional neural networks," NeurIPS (2016).
  • A. Lavin & S. Gray, "Fast algorithms for convolutional neural networks," CVPR (2016).
  • I. Goodfellow, Y. Bengio & A. Courville, Deep Learning, ch. 9 (MIT Press, 2016).