Convolutional neural networks (CNN)

The operation#

What deep learning calls convolution is technically cross-correlation — the kernel is not flipped. For input $X$, kernel $K$ of size $k_h \times k_w$, and output $Y$:

$$ Y[i, j] = \sum_{m=0}^{k_h - 1} \sum_{n=0}^{k_w - 1} X[i + m,\; j + n] \cdot K[m, n] $$

Since $K$ is learned, the flip is absorbed into the learned parameters and the distinction has no practical consequence.

With $C_{\text{in}}$ input channels and $C_{\text{out}}$ filters:

$$ Y[c_{\text{out}}, i, j] = b[c_{\text{out}}] + \sum_{c=0}^{C_{\text{in}}-1} \sum_{m} \sum_{n} X[c,\, i \cdot s + m,\; j \cdot s + n] \cdot K[c_{\text{out}}, c, m, n] $$

Where $s$ is the stride. Each filter spans the full channel depth, so a "3x3 filter" on RGB input is really a $3 \times 3 \times 3$ tensor.

Output size#

$$ H_{\text{out}} = \left\lfloor \frac{H_{\text{in}} + 2P - D(k - 1) - 1}{S} \right\rfloor + 1 $$

Where $P$ is padding, $S$ is stride, $k$ is kernel size, and $D$ is dilation. With $D = 1$ this reduces to the familiar $\lfloor (H + 2P - k)/S \rfloor + 1$.

Same padding requires $P = \lfloor (k-1)/2 \rfloor$ at $S = 1$, which is why odd kernel sizes dominate — an even kernel cannot pad symmetrically.

Cost#

For one conv layer:

• Parameters: $C_{\text{out}} \cdot C_{\text{in}} \cdot k_h \cdot k_w + C_{\text{out}}$ — independent of input resolution.
• FLOPs: $\approx 2 \cdot H_{\text{out}} W_{\text{out}} \cdot C_{\text{out}} C_{\text{in}} k_h k_w$ — strongly dependent on resolution.

That split explains a common surprise: doubling image resolution leaves the parameter count unchanged while quadrupling compute.

Depthwise separable convolution (Chollet, 2017, Xception; Howard et al., 2017, MobileNets) factorises the operation into a per-channel spatial convolution followed by a $1 \times 1$ pointwise convolution, cutting cost by a factor of:

$$ \frac{1}{C_{\text{out}}} + \frac{1}{k^2} $$

For $k=3$ and $C_{\text{out}} = 256$, that is roughly a $9\times$ reduction — the basis of every mobile vision architecture.

Receptive field#

The receptive field is the region of input influencing one output unit. Stacking layers with kernel size $k_l$ and stride $s_l$:

$$ r_{l} = r_{l-1} + (k_l - 1) \prod_{i=1}^{l-1} s_i $$

Two stacked $3\times3$ convolutions give a $5\times5$ receptive field using $2 \cdot 9 C^2 = 18C^2$ parameters, against $25C^2$ for a single $5\times5$ — fewer parameters, plus an extra non-linearity. This argument, from Simonyan and Zisserman (2015), VGG, is why $3\times3$ became the standard kernel.

Luo et al. (2016), Understanding the effective receptive field, show the effective receptive field is Gaussian-weighted and substantially smaller than the theoretical one, growing as $O(\sqrt{L})$ rather than $O(L)$.

Equivariance, and its limits#

Convolution is equivariant to translation: $f(T_{\delta} x) = T_{\delta} f(x)$ for a shift $T_\delta$. Adding global pooling yields approximate invariance.

Three honest caveats:

• Strided convolution and pooling break exact equivariance by violating the Nyquist criterion. Zhang (2019), Making convolutional networks shift-invariant again, shows a one-pixel shift can change predictions, and fixes it with anti-aliased downsampling.
• Convolution is not equivariant to rotation or scale. Those must be learned from augmented data, or built in explicitly (Cohen and Welling, 2016, Group equivariant CNNs).
• Zero padding leaks absolute position information, so networks are less translation-invariant than the theory suggests (Islam et al., 2020).

Architectural lineage#

Residual connections are the single most important entry. Before ResNet, deeper networks performed worse on the training set — an optimisation failure, not overfitting. The identity shortcut $y = \mathcal{F}(x) + x$ gives gradients a path with derivative exactly $1$, and depth became trainable.

CNNs versus vision transformers#

ViTs (Dosovitskiy et al., 2021) overtook CNNs on large-scale benchmarks, but the comparison is frequently misreported. ViTs lack the locality and translation-equivariance priors that CNNs build in, so they need far more data or heavy augmentation to match them. Liu et al. (2022), A ConvNet for the 2020s, show a modernised CNN matches Swin Transformer at equal compute — evidence that much of the reported gap came from training recipes rather than architecture.

CNNs remain the better choice for small datasets, high-resolution dense prediction, and edge deployment.

What to learn next#

• Image classification — putting a CNN to work on a real task.
• Object detection — finding where things are, not only what they are.
• Vision transformers — the architecture that challenged the CNN.