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
() Convolution commutes with shifts, by a change of summation index:
() Expand in impulses, , use linearity, and note that :
Read off entry using : this is the convolution. Uniqueness follows by applying both sides to .
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 positions has weights, an equivariant one , and a local equivariant one .
The theorem generalizes. For a group acting on the domain, the linear maps equivariant to are group convolutions, , with suitably constrained kernels when the group also acts on the feature channels. Cohen & Welling (2016) built CNNs equivariant to rotations by 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.
How many free parameters does a linear, translation-equivariant map on signals of length (circular boundary) have, and how many if it is also local with a window of entries?
- and
- and
- and
- and
Show the answer
B. and
A circulant matrix is determined by its first column : numbers. Locality forces to vanish outside a window of entries. For a layer from to channels on images, that is weights if merely equivariant, and if also local.
The Fourier view and the cost of convolution
Shifts commute with one another, so they share eigenvectors: the Fourier modes , with . Every map that commutes with all shifts is diagonal in the same basis, which is the convolution theorem:
The diagonalization also gives fast algorithms. For an image and a kernel, direct convolution costs about multiply-adds per pair of channels, while FFTs cost whatever is, which wins for large kernels. Networks mostly use kernels, for which minimal-filtering algorithms are better: Winograd's computes a tile of outputs with multiplications instead of 36, a 2.25-fold saving, at the price of extra additions and some loss of numerical accuracy (Lavin & Gray, 2016).
| Layer | Multiply-adds per output position | Weights |
|---|---|---|
| Standard convolution | ||
| Pointwise () convolution | ||
| Depthwise (one filter per channel) | ||
| Depthwise-separable (depthwise, then pointwise) |
A 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 , about 8.7 times fewer. For many output channels the saving approaches . 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 showing how strongly each input pixel affects a central output. It is roughly Gaussian and fills only a fraction of the theoretical field.
Take a linear network of stride-1 layers that all convolve with the same nonnegative kernel , normalized so that , with mean offset and variance . Backpropagating an impulse from one output convolves it with once per layer:
That is the distribution of a sum of independent offsets with , which by the central limit theorem approaches a Gaussian:
So the effective width grows like while the theoretical width grows like . 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- layer samples its output every 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 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 before subsampling. What comes out?
Max pooling over the pairs or gives all ones both times, stable here by luck. Plain subsampling gives before the shift and after: the highest frequency, above the new Nyquist limit, aliases to a constant whose value depends on the phase. Blurring first gives 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 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 samples in dimension .
Key takeaways
- A linear map commutes with all translations iff it is a convolution with , 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 FFT methods for large kernels; for kernels Winograd's saves a factor 2.25 in multiplications, and depthwise-separable layers cut the cost by the factor .
- Theoretical receptive fields grow as ; effective ones are roughly Gaussian with width proportional to , 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.
Which of these linear maps on , with circular indexing, commutes with every shift?
- , broadcasting the first entry
- , the discrete difference
- , multiplication by position
- , the reversal
Show the answer
B. , the discrete difference
The difference is convolution with the kernel , so it commutes with shifts. Broadcasting singles out a position, multiplication by is a diagonal rather than circulant matrix, and reversal satisfies instead.
For a single-channel image and a kernel, when does FFT-based convolution beat the direct method in multiplications, roughly?
- Always, since FFTs are fast
- When exceeds a constant times , that is, for large kernels
- Only for
- Never, because the FFT needs complex arithmetic
Show the answer
B. When exceeds a constant times , that is, for large kernels
Direct convolution costs about ; the FFT route costs for the transforms plus pointwise products, independent of . Large kernels favor the FFT; for kernels direct and Winograd methods win, which is why libraries choose the algorithm layer by layer.
A stack of stride-1 convolutions has a theoretical receptive field of width . By the central-limit argument, how does the width of its effective receptive field grow?
- Like as well
- Like
- It stays at 3
- Like
Show the answer
D. Like
The backpropagated influence of the input pixels is the -fold convolution of one kernel's weight profile, the distribution of a sum of independent offsets: approximately Gaussian, with standard deviation proportional to . Effective fields therefore fill a shrinking fraction, , of the theoretical ones.
Why can a CNN with stride-2 layers change its prediction when the input shifts by one pixel, despite convolution's equivariance?
- Because convolution is not equivariant at all
- Because ReLU is not shift-equivariant
- Because downsampling preserves equivariance only for shifts by multiples of the stride, and high-frequency content aliases
- 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).