Convolutional networks: filters, arithmetic, im2col and ResNet

Before this lesson: lesson 03 (backpropagation; the linear-layer rule $\bar W = A^\top G$) and lesson 05 (BatchNorm and residual connections). Helpful for the folded Fourier box: linear-algebra lesson 19 (circulant matrices and the DFT). Time: about 85 minutes, plus the notebook.

---

Why this matters #

A convolution layer builds one assumption into the network: a useful pattern is local, and it is useful at every position. This cuts the number of parameters by orders of magnitude and lets CNNs learn from less data on grids (images, audio, weather fields). ResNet, one of the most cited papers in science, is a stack of convolution blocks. In generative modelling, the autoencoder and the U-Net denoiser of latent diffusion models (Stable Diffusion) are convolutional ResNet blocks. In ML for science, a convolution with a fixed kernel is a finite-difference stencil, and U-Nets are a standard baseline for fields on grids. In interviews you are asked to compute shapes, parameter counts and receptive fields by hand, and sometimes to write the backward pass in NumPy.

1. Predict first #

2. The picture #

One dimension first #

Take a signal $x \in \mathbb{R}^n$ with one channel and a kernel of size $k = 3$, $w = (w_0, w_1, w_2)$. The layer computes

Each output is the dot product of $w$ with a window of three neighbouring inputs. The window slides by one position for each output.

Deep-learning libraries call this "convolution", but it is a cross-correlation: the kernel is not flipped. A true convolution flips the kernel: $y_i = \sum_u w_u x_{i-u}$. Because $w$ is learned, the flip does not matter for what a layer can represent. It does matter in the backward pass, as we will see.

As a matrix, $y = Tx$ with a banded matrix. For $n = 5$:

A matrix whose diagonals are constant is a Toeplitz matrix. Two ideas are visible in $T$:

• Locality: each row has only $k = 3$ nonzeros. Each output sees a small neighbourhood.
• Weight sharing: every row holds the same three numbers, shifted by one place. A dense layer $\mathbb{R}^n \to \mathbb{R}^n$ has $n^2$ parameters; this layer has $k$, whatever the length $n$.

Because every row is a shifted copy of the first row, shifting the input shifts the output. This is translation equivariance; section 3 makes it precise.

Filters on an image #

In 2-D the kernel is a small grid, for example $3\times3$. At each position $(i, j)$ the output is the sum of the kernel weights times the pixels under the window. The output image is a feature map: it is large where the window looks like the kernel.

Interactive figure: loading…

Read the edge-x kernel $\begin{pmatrix}-1&0&1\\-2&0&2\\-1&0&1\end{pmatrix}$ (the Sobel filter) as "right column minus left column". Where the brightness grows from left to right, the output is positive; where it falls, negative; where it is constant, the weights sum to 0 and the output is 0. A CNN does not get these kernels from us: it learns its kernels by gradient descent. The first layer of a trained image network learns edge and colour detectors that look much like these.

Many channels in, many channels out #

A colour image has $C_{\text{in}} = 3$ channels (red, green, blue), and hidden layers have tens to hundreds. One output channel uses one kernel of shape $C_{\text{in}} \times k \times k$: it looks at all input channels at once and adds everything up. A layer with $C_{\text{out}}$ output channels has $C_{\text{out}}$ such kernels, so the weights $W$ have shape $C_{\text{out}} \times C_{\text{in}} \times k_h \times k_w$ (PyTorch order).

For one input image $X$ of shape $C_{\text{in}} \times H_{\text{in}} \times W_{\text{in}}$, already zero-padded, with stride $s$ (the window moves $s$ pixels per output):

Here $o$ is the output channel, $(i, j)$ the output position, $c$ the input channel and $(u, v)$ the position inside the kernel. The sum runs over all input channels $c = 0, \dots, C_{\text{in}} - 1$ and all kernel positions $u = 0, \dots, k_h - 1$, $v = 0, \dots, k_w - 1$. ($W$ is the weight tensor; $W_{\text{in}}$ with a subscript is the input width.) Every output value is a dot product between one flattened kernel (length $C_{\text{in}} k_h k_w$) and one flattened patch of the input. Keep this sentence in mind: it is the whole idea of im2col in section 3.

3. Definitions and main results #

Arithmetic: output size, parameters, cost #

Notation along one spatial axis: input length $n$, kernel size $k$, stride $s$, zero padding $p$ on each side, and dilation $d$ (the distance between neighbouring kernel taps; $d = 1$ is an ordinary kernel, $d = 2$ skips every other pixel).

A dilated kernel covers $d(k - 1) + 1$ pixels. The padded input has $n + 2p$ pixels. The first window starts at 0, and each next window starts $s$ pixels later. The last window must end inside the padded input. Counting the windows gives the output size:

This is the formula of Dumoulin and Visin (Relationship 6, and Relationship 15 with dilation), and PyTorch uses it with the same floor. The floor means that pixels at the end that do not fill a whole window are dropped. "Same" padding: for odd $k$, $s = 1$, $d = 1$, the choice $p = (k-1)/2$ gives $o = n$.

Interactive figure: loading…

Parameters. A layer has $C_{\text{out}} C_{\text{in}} k_h k_w$ weights and $C_{\text{out}}$ biases:

The count does not depend on $H_{\text{in}}$ or $W_{\text{in}}$: the weights are shared over all positions. With $g$ groups (the channels are split into $g$ groups that do not mix), each output channel sees only $C_{\text{in}}/g$ input channels: $C_{\text{out}}(C_{\text{in}}/g)k_hk_w$ weights. A depthwise convolution has $g = C_{\text{in}}$: one kernel per channel.

Cost. A multiply-accumulate (MAC) is one multiplication and one addition. Each weight is used once at each output position, so one image costs

(divide by $g$ with groups). FLOPs $\approx 2\times$ MACs. Many papers, ResNet included, write "FLOPs" when they mean multiply-adds, so always say which one you mean. The parameters do not grow with the image size, but the cost does: it grows with the number of output positions.

Receptive field #

The receptive field of a unit is the set of input pixels that can change its value. Along one axis its size $r$ grows layer by layer. Let $j_l$ be the jump of layer $l$: the distance, in input pixels, between two neighbouring units of layer $l$. Strides multiply the jump. With $r_0 = 1$ and $j_0 = 1$ for the input:

So $j_{l-1} = \prod_{i<l} s_i$, the product of all earlier strides.

Why this is true.

1. A unit of layer $l$ reads $k_l$ units of layer $l-1$.
2. Neighbouring taps are $d_l$ units apart in layer $l-1$, which is $d_l j_{l-1}$ input pixels.
3. So the first and the last of these $k_l$ units are $d_l(k_l - 1) j_{l-1}$ input pixels apart.
4. Each of them sees $r_{l-1}$ input pixels. The union spans $r_{l-1} + d_l(k_l-1)j_{l-1}$ pixels.

Pooling layers count like convolutions (a $2\times2$ pool with stride 2 has $k = 2$, $s = 2$). This is the theoretical receptive field. The effective receptive field, where the gradient is large, is smaller and roughly Gaussian (Luo et al., 2016): pixels near the centre have many more paths to the unit than pixels at the edge.

Interactive figure: loading…

im2col: a convolution is one matrix product #

Every output value is (flattened kernel) $\cdot$ (flattened patch). So collect all patches as the columns of one matrix and all kernels as the rows of another.

• im2col ("image to columns") builds $\text{cols} = U(X)$ of shape $(C_{\text{in}} k_h k_w) \times (H_{\text{out}} W_{\text{out}})$: one column per output position, one row per kernel tap. Row $c\,k_hk_w + u\,k_w + v$ and column $i\,W_{\text{out}} + j$ hold $X[c, is + u, js + v]$. This is the layout of PyTorch's F.unfold.
• Reshape $W$ to $W_{\text{mat}}$ of shape $C_{\text{out}} \times (C_{\text{in}} k_h k_w)$: one row per output channel.

Then

$Y_{\text{mat}}$ has shape $C_{\text{out}} \times H_{\text{out}} W_{\text{out}}$, and reshaping it gives $Y$. Transpose both sides and you get the row form of this track (lesson 01): $Y_{\text{mat}}^\top = \text{cols}^\top W_{\text{mat}}^\top + \mathbf{1}b^\top$. This is a linear layer $Z = AW + \mathbf{1}b$ applied to $H_{\text{out}}W_{\text{out}}$ "examples", one per patch, all with the same weights. That is weight sharing, written as a matrix product.

Interactive figure: loading…

Memory cost. cols holds $C_{\text{in}} k_h k_w H_{\text{out}} W_{\text{out}}$ numbers, about $k_hk_w/s^2$ times the size of the input. For a $3\times3$ "same" convolution that is $9\times$: a $64\times56\times56$ fp32 input (0.8 MB) becomes 7.2 MB of columns, and 1.85 GB for a batch of 256. This is one reason GPU libraries such as cuDNN use implicit GEMM (the patches are built tile by tile and never stored), Winograd or FFT algorithms instead.

The backward pass #

Let $\bar Y = \partial\mathcal{L}/\partial Y$ be the upstream gradient (same shape as $Y$), as in lesson 03. We want $\bar W$, $\bar b$ and $\bar X$.

Theorem (backward pass of a convolution). Take stride 1, no padding, one image: $Y[o,i,j] = b[o] + \sum_{c,u,v} W[o,c,u,v]\,X[c,i+u,j+v]$. Then

where $\bar Y = 0$ outside its index range.

In matrix form: $\bar W_{\text{mat}} = \bar Y_{\text{mat}}\,\text{cols}^\top$, $\bar b = \bar Y_{\text{mat}}\mathbf{1}$, and $\bar X = \text{col2im}(W_{\text{mat}}^\top \bar Y_{\text{mat}})$. $\bar X$ is a "full" cross-correlation of $\bar Y$ (zero-padded by $k-1$ on each side) with the kernel rotated by $180°$ and with the two channel axes swapped: a transposed convolution.

Why this is true (intuition). In the forward pass, pixel $X[c,p,q]$ is used by every window that covers it, each time with a different weight. So its gradient collects one term from each of those windows. Think of each $\bar Y[o,i,j]$ as a "stamp": it puts a copy of the kernel, scaled by $\bar Y[o,i,j]$, onto the input grid at position $(i,j)$. Overlapping stamps add. The index $p - u$ (instead of $p + u$) is the flip: forward is a cross-correlation, so backward is a true convolution.

Proof of the theorem (six steps)

1. $b[o]$ enters every output of channel $o$ with coefficient 1, so $\bar b[o]$ is the sum of $\bar Y[o,\cdot,\cdot]$.
2. $W[o,c,u,v]$ multiplies $X[c,i+u,j+v]$ in output $(o,i,j)$ and nowhere else. Summing over all outputs gives $\bar W[o,c,u,v] = \sum_{i,j}\bar Y[o,i,j]\,X[c,i+u,j+v]$: the cross-correlation of the input with the output gradient.
3. Pixel $X[c,p,q]$ enters output $(o,i,j)$ exactly when $i + u = p$ and $j + v = q$, with weight $W[o,c,u,v]$. So $\bar X[c,p,q] = \sum_{o,u,v}\bar Y[o,p-u,q-v]\,W[o,c,u,v]$.
4. Substitute $u' = k_h - 1 - u$, $v' = k_w - 1 - v$ and pad $\bar Y$ with $k_h - 1$ rows and $k_w - 1$ columns of zeros on each side (call it $\bar Y_{\text{pad}}$). Then $\bar Y[o,p-u,q-v] = \bar Y_{\text{pad}}[o,p+u',q+v']$, and with $W_{\text{rot}}[c,o,u',v'] = W[o,c,k_h-1-u',k_w-1-v']$:

$$\bar X[c,p,q] = \sum_{o,u',v'} W_{\text{rot}}[c,o,u',v']\;\bar Y_{\text{pad}}[o,p+u',q+v'].$$

This is a cross-correlation of $\bar Y_{\text{pad}}$ with the rotated, channel-swapped kernel. Its output size is $H_{\text{out}} + k_h - 1 = H_{\text{in}}$, as it must be. 5. In matrix form, $Y_{\text{mat}} = W_{\text{mat}}\text{cols} + b\mathbf{1}^\top$ is a linear layer, so (lesson 03) $\bar W_{\text{mat}} = \bar Y_{\text{mat}}\text{cols}^\top$, $\bar b = \bar Y_{\text{mat}}\mathbf{1}$ and $\overline{\text{cols}} = W_{\text{mat}}^\top \bar Y_{\text{mat}}$. 6. $\text{cols} = U(X)$ is a linear map of $X$. The vector-Jacobian product of a linear map is its adjoint (linear-algebra lesson 15): $\langle UX, C\rangle = \langle X, U^\top C\rangle$. $U^\top$ is col2im: it sends every entry of a column back to the pixel it was copied from and adds the contributions, because a pixel lies in up to $k_hk_w$ patches. So $\bar X = \text{col2im}(W_{\text{mat}}^\top \bar Y_{\text{mat}})$. $\blacksquare$

The map $X \mapsto Y$ is linear in $X$, with some matrix $T$ (like the Toeplitz matrix of section 2). The theorem says $\bar X = T^\top \bar Y$. That is why the operator is called the transposed convolution. With stride $s$, first insert $s - 1$ zeros between the entries of $\bar Y$, then do the same full correlation. The transposed convolution is not an inverse, and col2im is not an inverse of im2col either: $\text{col2im}(\text{im2col}(X))$ multiplies each pixel by the number of patches that contain it. U-Net decoders use the same operator, with learned weights, to upsample (ConvTranspose2d).

Translation equivariance, and where it breaks #

Let $S_t$ shift a signal by $t$ positions: $(S_t x)_i = x_{i-t}$. A layer $f$ is equivariant to shifts if $f(S_t x) = S_t f(x)$: shifting the input shifts the output by the same amount. It is invariant if $f(S_t x) = f(x)$.

Stride 1 is equivariant on a circular (or infinite) domain. Proof in 1-D, indices taken mod $n$:

It breaks in three ways.

• Zero padding. Near the border the shifted input meets zeros instead of the pixels that "wrapped around", so equivariance holds only away from the border. Padding also lets a CNN learn absolute position: a unit can tell that it is near the border.
• Stride $s$. A strided layer is the stride-1 layer followed by keeping every $s$-th output: $\mathrm{conv}_s(x)_i = y_{si}$. Then $\mathrm{conv}_s(S_t x)_i = y_{si - t}$. If $t = sm$, this is $y_{s(i-m)} = (S_m\,\mathrm{conv}_s(x))_i$: the output shifts by $t/s$. If $t$ is not a multiple of $s$, the layer now keeps the other samples of $y$ (for $s = 2$: the odd ones instead of the even ones), and in general no shift of the old output matches. This is aliasing.
• Pooling. Max pooling gives some invariance to small shifts inside a window, but it also subsamples, so it has the same stride problem. A CNN becomes (approximately) invariant only through global pooling at the end.

Interactive figure: loading…

This answers question 3 of section 1: no. With stride 2, a one-pixel shift gives a different output, not a shifted one.

Convolution, circulant matrices and the Fourier transform

On a circular domain of length $n$, the 1-D layer $y_i = \sum_u w_u x_{(i+u) \bmod n}$ is $y = Cx$ with $C_{il} = w_{(l - i) \bmod n}$ (where $w_m = 0$ for $m \ge k$). The entries of $C$ depend only on $l - i$ (mod $n$): $C$ is a circulant matrix. By linear-algebra lesson 19 (Theorem 2), a linear map commutes with the cyclic shift $P$ exactly when it is circulant. So the linear, shift-equivariant maps on a periodic signal are exactly the circular convolutions. Equivariance is not an accident of convolutions; it characterizes them.

By Theorem 1 of the same lesson, every circulant is diagonalized by the DFT: $C = F^{-1}\operatorname{diag}(\hat c)F$. So a circular convolution is a product in Fourier space, and it costs $O(n\log n)$ with the FFT instead of $O(nk)$. That is the basis of FFT convolution for large kernels, and of the Fourier neural operator (FNO), which learns $\hat c$ directly for the lowest frequencies: a global kernel instead of a local one. In 2-D, a periodic convolution is a block-circulant matrix with circulant blocks, and the 2-D DFT diagonalizes it.

Pooling, $1\times1$ convolutions and global average pooling #

• Max pooling ($k\times k$ window, stride $s$) takes the maximum of each window, channel by channel. It has no parameters. Its backward pass sends each output gradient to the argmax of its window (the position of the maximum) and 0 to the other positions; with overlapping windows the contributions add. Average pooling takes the mean, so its gradient is spread evenly: $\bar y / k^2$ to each pixel of the window.
• Global average pooling averages each channel over all positions: $C\times H\times W \to C$. The classifier head after it then works for any input size.
• A $1\times1$ convolution applies the same linear map $\mathbb{R}^{C_{\text{in}}} \to \mathbb{R}^{C_{\text{out}}}$ at every pixel. It is a Linear layer over the channel axis, shared over positions. It changes the number of channels and mixes them cheaply ($C_{\text{out}}C_{\text{in}}$ weights).

ResNet blocks #

ResNet (He et al., 2016) is a stack of residual blocks $x \mapsto \mathrm{ReLU}(x + F(x))$ (lesson 05 explains why the identity path makes deep networks trainable).

• The basic block (ResNet-18 and ResNet-34): conv $3\times3$ → BN → ReLU → conv $3\times3$ → BN, plus the identity, then ReLU.
• The bottleneck block (ResNet-50, -101, -152): $1\times1$ ($256\to64$) → $3\times3$ ($64\to64$) → $1\times1$ ($64\to256$), each with BN, ReLU between them, plus the identity, then ReLU.

The bottleneck runs the expensive $3\times3$ convolution at a quarter of the width. Its weights: $256\cdot64 + 9\cdot64\cdot64 + 64\cdot256 = 69{,}632$. A basic block at 256 channels has $2\cdot9\cdot256\cdot256 = 1{,}179{,}648$, about $17\times$ more. The point of the paper: a bottleneck costs about as much as a basic block at 64 channels ($2\cdot9\cdot64\cdot64 = 73{,}728$ weights), so the network can be deeper and keep a wide (256-channel) residual stream at about the same cost.

When the shape changes (stride 2 and twice the channels), the shortcut is a strided $1\times1$ convolution, a projection shortcut. The original (v1) models put the stride in the first $1\times1$ convolution of the branch; torchvision's "v1.5" puts it in the $3\times3$ convolution. Pre-activation ResNets (He et al., 2016b) reorder each branch to BN → ReLU → conv, so the identity path carries no nonlinearity at all. This is the same idea as pre-LN transformers (lesson 05).

U-Net (Ronneberger et al., 2015) has an encoder that halves the resolution step by step (strided convolutions or pooling) and doubles the channels, and a decoder that doubles the resolution again with transposed convolutions (or upsampling followed by a convolution). Skip connections copy each encoder feature map to the decoder stage of the same resolution, where it is concatenated. So the decoder gets both the coarse context and the fine detail. Diffusion models and many ML-for-science models (weather, segmentation of microscopy images) use U-Nets.

Answers to section 1. (1) $3\cdot3\cdot64\cdot64 = 36{,}864$ weights (plus 64 biases), on any map size, because the weights are shared over positions. Only the cost grows: $56^2\cdot36{,}864 \approx 116$ million MACs, and four times that on $112\times112$. (2) A transposed convolution: a full cross-correlation of $\bar Y$ with the $180°$-rotated, channel-swapped kernel, equal to $\text{col2im}(W_{\text{mat}}^\top \bar Y_{\text{mat}})$.

4. Worked example #

(a) Shapes, parameters, MACs and receptive field #

Input $3\times32\times32$; all convolutions are $3\times3$ with bias.

Layer	Output	Parameters	MACs	$r$, $j$
conv $3\to16$, $s=1$, $p=1$	$16\times32\times32$	$16\cdot3\cdot9 + 16 = 448$	$32^2\cdot16\cdot27 = 442{,}368$	3, 1
conv $16\to32$, $s=2$, $p=1$	$32\times16\times16$	$32\cdot16\cdot9+32 = 4{,}640$	$16^2\cdot32\cdot144 = 1{,}179{,}648$	5, 2
max pool $2\times2$, $s=2$	$32\times8\times8$	0	—	7, 4
conv $32\to64$, $s=1$, $p=1$	$64\times8\times8$	$64\cdot32\cdot9+64 = 18{,}496$	$8^2\cdot64\cdot288 = 1{,}179{,}648$	15, 4

Step by step:

1. First conv: $o = \lfloor (32 + 2 - 2 - 1)/1\rfloor + 1 = 32$. $r_1 = 1 + 2\cdot1 = 3$, $j_1 = 1$.
2. Second conv: $o = \lfloor (32+2-2-1)/2\rfloor + 1 = \lfloor 15.5\rfloor + 1 = 16$. Each kernel has $16\cdot9 = 144$ weights, so MACs $= 16^2\cdot32\cdot144$. $r_2 = 3 + 2\cdot1 = 5$, $j_2 = 2$.
3. Pool: $o = \lfloor (16 - 1 - 1)/2\rfloor + 1 = 8$. $r_3 = 5 + 1\cdot2 = 7$, $j_3 = 4$.
4. Last conv: $o = 8$. $r_4 = 7 + 2\cdot4 = 15$.

The second and the last conv have the same MACs. The last one has 4 times fewer output positions ($8^2$ instead of $16^2$), but twice as many input channels and twice as many output channels.

(b) im2col and the backward pass by hand #

One channel, stride 1, no padding, $b = 0$:

The output is $2\times2$ ($o = 3 - 2 + 1 = 2$).

Forward. cols has one row per kernel tap $(u,v)$ in the order $(0,0),(0,1),(1,0),(1,1)$, and one column per output position $(i,j)$ in the order $(0,0),(0,1),(1,0),(1,1)$. Column 1 is the top-left patch $\begin{pmatrix}1&2\\0&1\end{pmatrix}$ read row by row: $(1, 2, 0, 1)$. All four:

$W_{\text{mat}}\text{cols}$, column by column: $1 - 0 + 2 = 3$; $2 - 1 + 6 = 7$; $0 - 2 + 2 = 0$; $1 - 1 + 2 = 2$. So $Y = \begin{pmatrix}3&7\\0&2\end{pmatrix}$.

Backward. Take $\bar Y = \begin{pmatrix}1&0\\0&-1\end{pmatrix}$, so $\bar Y_{\text{mat}} = (1, 0, 0, -1)$.

• $\bar W_{\text{mat}} = \bar Y_{\text{mat}}\text{cols}^\top$ = (column 1 of cols) $-$ (column 4 of cols) $= (1,2,0,1) - (1,3,1,1) = (0,-1,-1,0)$. So $\bar W = \begin{pmatrix}0&-1\\-1&0\end{pmatrix}$. Check with the formula: $\bar W[u,v] = X[u,v] - X[1+u,1+v]$; for example $\bar W[0,1] = X[0,1] - X[1,2] = 2 - 3 = -1$ ✓.
• $\bar X$ by stamping: $\bar Y[0,0] = 1$ stamps $+W$ at the top left, and $\bar Y[1,1] = -1$ stamps $-W$ at the bottom right:

The centre pixel $X[1,1]$ is in both patches, so it gets $2 + (-1) = 1$.

• The same result comes from the full correlation of $\bar Y$ (padded by one zero on each side) with $W_{\text{rot}} = \begin{pmatrix}2&-1\\0&1\end{pmatrix}$. For example $\bar X[0,0]$: the window at the top left of the padded $\bar Y$ is $\begin{pmatrix}0&0\\0&1\end{pmatrix}$, and its dot product with $W_{\text{rot}}$ is $1\cdot1 = 1$ ✓.

5. In code #

PyTorch checks the hand computation of example (b). F.unfold is im2col and F.fold is col2im.

import torch
import torch.nn.functional as F

x = torch.tensor([[1., 2, 0], [0, 1, 3], [2, 1, 1]]).reshape(1, 1, 3, 3).requires_grad_()
w = torch.tensor([[1., 0], [-1, 2]]).reshape(1, 1, 2, 2)    # (C_out, C_in, kh, kw)
y = F.conv2d(x, w)                        # cross-correlation, stride 1, no padding
print(y.reshape(2, 2).tolist())           # [[3.0, 7.0], [0.0, 2.0]]

cols = F.unfold(x, kernel_size=2)         # im2col: (N, C_in*kh*kw, H_out*W_out) = (1, 4, 4)
w_mat = w.reshape(1, -1)                  # (C_out, C_in*kh*kw)
print(torch.equal(w_mat @ cols, y.reshape(1, 1, 4)))   # True: conv = one matrix product

dy = torch.tensor([[1., 0], [0, -1]]).reshape(1, 1, 2, 2)
y.backward(dy)                            # autograd puts X̄ into x.grad
dw = (dy.reshape(1, 4) @ cols[0].T).reshape(2, 2)   # W̄ = Ȳ cols^T
dcols = w_mat.T @ dy.reshape(1, 1, 4)               # W^T Ȳ
dx_col2im = F.fold(dcols, (3, 3), kernel_size=2)    # col2im
dx_transposed = F.conv_transpose2d(dy, w)           # transposed convolution
print(dw.tolist())
# [[0.0, -1.0], [-1.0, 0.0]]
print(x.grad.reshape(3, 3).tolist())
# [[1.0, 0.0, 0.0], [-1.0, 1.0, 0.0], [0.0, 1.0, -2.0]]
print(torch.equal(x.grad, dx_col2im), torch.equal(x.grad, dx_transposed))
# True True

The arithmetic of example (a), the receptive field as the support of a gradient, the bottleneck count and the stride claim:

import torch
import torch.nn as nn
import torch.nn.functional as F

torch.manual_seed(0)
layers = [nn.Conv2d(3, 16, 3, padding=1), nn.Conv2d(16, 32, 3, stride=2, padding=1),
          nn.MaxPool2d(2, 2), nn.Conv2d(32, 64, 3, padding=1)]
h = torch.zeros(1, 3, 32, 32)
for layer in layers:
    c_in = h.shape[1]
    h = layer(h)
    params = sum(p.numel() for p in layer.parameters())
    macs = h[0].numel() * c_in * 9 if isinstance(layer, nn.Conv2d) else 0
    print(type(layer).__name__, tuple(h.shape[1:]), params, macs)
# Conv2d (16, 32, 32) 448 442368
# Conv2d (32, 16, 16) 4640 1179648
# MaxPool2d (32, 8, 8) 0 0
# Conv2d (64, 8, 8) 18496 1179648

# Receptive field = the pixels where the gradient of one output unit is nonzero.
# AvgPool has the same window as MaxPool, but its gradient reaches every pixel
# of the window (MaxPool's gradient reaches only the argmax).
probe = nn.Sequential(nn.Conv2d(1, 1, 3, padding=1), nn.Conv2d(1, 1, 3, stride=2, padding=1),
                      nn.AvgPool2d(2, 2), nn.Conv2d(1, 1, 3, padding=1))
for m in probe:
    if isinstance(m, nn.Conv2d):
        nn.init.constant_(m.weight, 1.0)
x = torch.zeros(1, 1, 64, 64, requires_grad=True)
probe(x)[0, 0, 8, 8].backward()
rows = (x.grad[0, 0].abs().sum(dim=1) > 0).nonzero()
print("receptive field:", int(rows.max() - rows.min() + 1))   # receptive field: 15

count = lambda m: sum(p.numel() for p in m.parameters())
bottleneck = nn.Sequential(nn.Conv2d(256, 64, 1, bias=False),
                           nn.Conv2d(64, 64, 3, padding=1, bias=False),
                           nn.Conv2d(64, 256, 1, bias=False))
basic = nn.Sequential(nn.Conv2d(256, 256, 3, padding=1, bias=False),
                      nn.Conv2d(256, 256, 3, padding=1, bias=False))
print(count(bottleneck), count(basic))   # 69632 1179648

# Shift equivariance on a circular domain:
# exact at stride 1; at stride 2 only for even shifts.
x, w = torch.randn(1, 1, 16, 16), torch.randn(1, 1, 3, 3)
conv = lambda t, s: F.conv2d(F.pad(t, (1, 1, 1, 1), mode="circular"), w, stride=s)
shift = lambda t, k: torch.roll(t, k, dims=-1)
print(torch.allclose(conv(shift(x, 1), 1), shift(conv(x, 1), 1), atol=1e-6))   # True
print(torch.allclose(conv(shift(x, 2), 2), shift(conv(x, 2), 1), atol=1e-6))   # True
err = min(float((conv(shift(x, 1), 2) - shift(conv(x, 2), k)).abs().max()) for k in range(8))
print(err > 0.1)                          # True: no shift of the output matches

6. Where it shows up #

• Architectures. ResNet; U-Net; ConvNeXt (depthwise $7\times7$ convolutions plus $1\times1$ "MLP" layers); MobileNet (depthwise separable convolutions); the autoencoder of latent diffusion (Stable Diffusion downsamples by 8 in each direction). The patch embedding of a vision transformer is a convolution with kernel size = stride = patch size (lesson 11).
• Sequences. 1-D convolutions over time: WaveNet (dilated causal convolutions, so the receptive field grows exponentially with depth) and the local convolution inside Mamba blocks. Linear time-invariant state-space models such as S4 (lesson 16) can be computed as one very long convolution.
• ML for science. A convolution with a fixed kernel is a finite-difference stencil: the 5-point Laplacian is $\frac{1}{h^2}\begin{pmatrix}0&1&0\\1&-4&1\\0&1&0\end{pmatrix}$. Because PyTorch correlates, the kernel $(-1, 0, 1)/(2h)$ in F.conv1d gives $+\partial_x$ (a true convolution would give the minus sign). On a global latitude–longitude grid, pad circularly in longitude only, F.pad(x, (1, 1, 0, 0), mode="circular"), so the network does not see a false border at the date line. PhaseNet (seismic phase picking) is a 1-D U-Net on three-component waveforms. The Fourier neural operator replaces the local kernel by a global one in Fourier space (see the folded box in section 3).

7. Common mistakes #

• Dropping the floor. A length-7 input with $k = 2$, $s = 2$ gives $\lfloor 5/2\rfloor + 1 = 3$ outputs; the last pixel is never used.
• Forgetting $C_{\text{in}}$ in the parameter count, or thinking that the count grows with the image size. It is $C_{\text{out}}(C_{\text{in}}k_hk_w + 1)$, whatever $H_{\text{in}}$, $W_{\text{in}}$.
• Mixing MACs and FLOPs. They differ by a factor of 2.
• Receptive field without the jump. Each layer adds $d_l(k_l - 1)$ times the product of the earlier strides, not just $k_l - 1$.
• "CNNs are translation invariant." Convolution layers are equivariant, and exactly so only at stride 1 and away from the borders. Strides alias. Invariance comes, approximately, from global pooling at the end.
• Assignment instead of addition in col2im or in the max-pool backward pass. Overlapping patches must add (np.add.at, not x[idx] = ...).
• Treating the transposed convolution as an inverse. It is the adjoint $T^\top$, not $T^{-1}$.

8. Check yourself #

1. A 1-D input of length 100 goes through a conv ($k=5$, $s=1$, $p=0$), then a conv ($k=3$, $s=2$, $p=1$). What are the output length and the receptive field?
   Answer

   $100 - 5 + 1 = 96$, then $\lfloor(96 + 2 - 3)/2\rfloor + 1 = 47 + 1 = 48$. Receptive field $1 + 4\cdot1 + 2\cdot1 = 7$: the stride of the second layer does not enter its own term.
2. Count the weights (no biases) of a depthwise separable convolution ($3\times3$ depthwise on 128 channels, then $1\times1$ from 128 to 256) and of a standard $3\times3$ convolution from 128 to 256.
   Answer

   $9\cdot128 + 128\cdot256 = 1{,}152 + 32{,}768 = 33{,}920$ against $9\cdot128\cdot256 = 294{,}912$: about $8.7\times$ fewer.
3. By how much does im2col inflate the input for a $3\times3$ "same" convolution at stride 1? At stride 2?
   Answer

   About $k_hk_w/s^2$: $9\times$ at stride 1, and about $9/4 = 2.25\times$ at stride 2.
4. Why does $\bar X$ need col2im and not an inverse of im2col?
   Answer

   The backward pass of a linear map is its adjoint, not its inverse: $\langle UX, C\rangle = \langle X, U^\top C\rangle$. $U^\top$ = col2im sends each column entry back to its pixel and adds the overlaps. A column matrix whose overlapping entries disagree is not im2col of any image, so there is no inverse to apply.
5. Why do three stacked $3\times3$ convolutions (as in VGG) beat one $7\times7$ convolution with the same $C$ channels in and out?
   Answer

   Same receptive field (7), but $3\cdot9C^2 = 27C^2$ weights instead of $49C^2$, and two extra nonlinearities in between.
6. A $2\times2$ max pool (stride 2) sees the window $\begin{pmatrix}1&5\\3&2\end{pmatrix}$, and the upstream gradient of its output is $0.4$. What gradient does each of the four pixels get? And with average pooling?
   Answer

   Max pool: $\begin{pmatrix}0&0.4\\0&0\end{pmatrix}$; all of it goes to the argmax (the 5). Average pool: $0.4/4 = 0.1$ to each pixel.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. What is the output size of a convolution with input $n$, kernel $k$, stride $s$, padding $p$, dilation $d$?

   Show answer

2. How many parameters does Conv2d(C_in, C_out, k) have, and does the count depend on the image size?

   Show answer

3. Give the receptive-field recursion.

   Show answer

4. Compute the receptive field of three stacked $3\times3$ convolutions with stride 1.

   Show answer

5. What does a deep-learning "convolution" compute, compared with a true convolution?

   Show answer

6. What are the shapes in im2col for one image?

   Show answer

7. What is the gradient of a convolution with respect to its input?

   Show answer

8. Why does stride 2 break shift equivariance for a one-pixel shift?

   Show answer

9. What does a $1\times1$ convolution compute?

   Show answer

10. Why does ResNet-50 use the bottleneck block ($1\times1$ 256→64, $3\times3$ 64→64, $1\times1$ 64→256)?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "Output shape and parameters of this layer?" — Use the floor formula and $C_{\text{out}}C_{\text{in}}k_hk_w + C_{\text{out}}$; say that the count is independent of $H$ and $W$.
• "Write conv2d forward and backward in NumPy." — im2col plus one matrix product; $\bar W = \bar Y\,\text{cols}^\top$, $\bar X = \text{col2im}(W^\top \bar Y)$ with np.add.at.
• "Why do transposed convolutions give checkerboard artifacts?" — The stamped kernels overlap unevenly when the kernel size is not divisible by the stride (Odena et al., 2016). A common fix is resize, then convolve.
• "Why the bottleneck block?" — The $3\times3$ convolution runs at a quarter of the width: about $17\times$ fewer weights than a basic block at the same outer width.
• "Is a CNN shift invariant?" — No. Its layers are equivariant at stride 1 (away from borders); strides alias. Global pooling at the end gives approximate invariance.
• "What limits im2col?" — Memory: about $k^2/s^2$ times the input. Libraries use implicit GEMM, Winograd or FFT.

10. Practice #

The notebook for this lesson runs in Colab (NumPy and a small PyTorch model on a CPU). It has five exercises, each with a check cell and a folded solution:

1. conv_output_size, conv_params and conv_macs, checked against nn.Conv2d.
2. im2col and conv2d_forward in NumPy, checked against F.unfold and F.conv2d.
3. col2im and conv2d_backward, checked against autograd and the adjoint identity.
4. receptive_field for a list of layers, checked against the support of a gradient.
5. equivariance_error: test shift equivariance for stride 1 and stride 2.

At the end, a demo trains a tiny CNN and an MLP with the same budget on the scikit-learn digits and tests both on shifted test images.

11. Watch and read #

Lecture 5 | Convolutional Neural NetworksStanford CS231n (2017) · Serena Yeung · 1 h 9 min

Filters, stride, padding, output sizes and parameter counts, with many pictures.

But what is a convolution?3Blue1Brown · 23 min

Convolution as sliding and adding, image kernels, and the link to the Fourier transform.

Lecture 9 | CNN ArchitecturesStanford CS231n (2017) · Serena Yeung · 1 h 18 min

AlexNet, VGG, GoogLeNet and ResNet; watch the part on ResNet and the bottleneck block.

• Simon J. D. Prince, Understanding Deep Learning (free PDF): ch. 10 (§10.1 invariance and equivariance, §10.2–10.3 1-D and 2-D convolution, §10.4 downsampling, upsampling and transposed convolution) and §11.5 (ResNet and bottleneck blocks).
• Stanford CS231n notes, Convolutional Neural Networks: "Convolutional Layer" (with "Implementation as Matrix Multiplication") and "ConvNet Architectures".
• Dumoulin and Visin, A guide to convolution arithmetic for deep learning: ch. 2 (output sizes), ch. 4 (transposed convolution) and §5.1 (dilation).
• He, Zhang, Ren and Sun, Deep Residual Learning for Image Recognition: §3.3 and "Deeper Bottleneck Architectures" in §4.1 (Fig. 5).
• Ronneberger, Fischer and Brox, U-Net.
• Luo, Li, Urtasun and Zemel, Understanding the Effective Receptive Field in Deep Convolutional Neural Networks.
• Odena, Dumoulin and Olah, Deconvolution and Checkerboard Artifacts (Distill).