Pooling Operations

A pooling operation is a fixed, non-learned function applied independently to each channel of a feature map. It slides a window of size $k \times k$ across the map with some stride $s$, and at each window position outputs a single scalar computed from the values inside that window. The two dominant choices are:

• Max pooling: output the maximum value in the window.
• Average pooling: output the arithmetic mean of the values in the window.

Formally, given an input feature map $X \in \mathbb{R}^{H \times W}$ (one channel), a pooling window of size $k \times k$, and stride $s$, the output at position $(i, j)$ is

for max pooling, or

for average pooling. Unlike a convolutional layer, pooling has no weights and no bias — it is a deterministic, parameter-free reduction, applied independently and identically to every channel. This means pooling adds zero parameters to the model and requires no gradient computation with respect to any weight, only a gradient routing rule back to the input (described below). Two design choices matter: the window size $k$ (commonly $2\times 2$ or $3\times 3$) and the stride $s$. When $s = k$, windows tile the input with no overlap — the classic case, e.g. $2\times2$ pooling with stride $2$ exactly halves height and width. When $s < k$, windows overlap, giving smoother downsampling at the cost of more computation per output pixel (still $O(k^2)$ work per output, only the constant changes). Padding can be added if $H$ or $W$ is not evenly divisible by the stride, though many implementations simply crop leftover rows/columns instead. This entire mechanism builds directly on The Convolution Operation and Convolutional Layers and Parameter Sharing: pooling reuses the sliding-window scanning pattern of convolution but replaces the learned weighted sum with a fixed max or mean.

The forward pass of pooling is a direct generalization of the convolution sliding-window scan, but with the inner product replaced by max or average, and applied per-channel with no mixing across channels (unlike convolution, which can mix input channels via multi-channel filters).

Step-by-step, forward pass: 1. Fix window size $k$, stride $s$, and (optionally) padding $p$. 2. For each channel independently (pooling never combines channels): a. Slide a $k \times k$ window over the (possibly padded) feature map, moving $s$ pixels at a time in each spatial direction. b. At each window position, compute the max (or mean) of the $k^2$ values inside. c. Write that scalar to the corresponding position of the output map. 3. Stack the per-channel outputs — channel count is unchanged; only height and width shrink.

Step-by-step, backward pass (needed for backpropagation through a pooling layer):

• Max pooling: for each output position, the gradient flowing in is routed entirely to the input position that achieved the max in the forward pass; all other positions in that window receive zero gradient from this window. If a value contributed to multiple overlapping windows (stride $<$ window size), its gradients from each window are summed.
• Average pooling: for each output position, the incoming gradient is divided by $k^2$ and added equally to every position in the corresponding input window (again summing contributions from overlapping windows).

``` function POOL_FORWARD(X, k, stride, mode):

# X: input feature map, shape (C, H, W)

# k: window size, stride: step size, mode: "max" or "avg" C, H, W = shape(X) H_out = floor((H - k) / stride) + 1 W_out = floor((W - k) / stride) + 1 Y = zeros(C, H_out, W_out) ARGMAX = zeros(C, H_out, W_out, 2) # only needed for max mode's backward pass for c in 0 .. C-1: for i in 0 .. H_out-1: for j in 0 .. W_out-1: row0 = i stride col0 = j stride window = X[c, row0 : row0+k, col0 : col0+k] if mode == "max": Y[c, i, j] = max(window) ARGMAX[c, i, j] = index_of_max(window) + (row0, col0) # absolute coords else: # "avg" Y[c, i, j] = sum(window) / (k * k) return Y, ARGMAX # ARGMAX unused when mode == "avg"

function POOL_BACKWARD(dY, X_shape, ARGMAX, k, stride, mode):

# dY: gradient w.r.t. pooled output, shape (C, H_out, W_out) C, H_out, W_out = shape(dY) dX = zeros(X_shape) # same shape as original input for c in 0 .. C-1: for i in 0 .. H_out-1: for j in 0 .. W_out-1: if mode == "max": (r, col) = ARGMAX[c, i, j] dX[c, r, col] += dY[c, i, j] # route full gradient to the argmax else: # "avg" row0 = i stride col0 = j stride share = dY[c, i, j] / (k * k) for p in 0 .. k-1: for q in 0 .. k-1: dX[c, row0+p, col0+q] += share # spread equally return dX ``` Edge cases handled: (a) when $H$ or $W$ is not a multiple of the stride, `H_out`/`W_out` use `floor`, so trailing rows/columns that don't fill a full window are simply excluded (or the caller pads first); (b) ties inside a max window are broken by taking the first occurrence, a harmless convention as long as it's applied consistently in forward and backward; (c) overlapping windows (stride $<$ k) correctly accumulate (`+=`) rather than overwrite, since one input pixel can feed multiple output positions.

Time complexity. For an input of shape $C \times H \times W$, window size $k$, and stride $s$, the output has shape $C \times H_\text{out} \times W_\text{out}$ with $H_\text{out} = \lfloor (H-k)/s \rfloor + 1$ and similarly for $W_\text{out}$. Each output element requires scanning $k^2$ input values (finding a max or summing), so the total forward work is

When $s = k$ (the common non-overlapping case), $H_\text{out} \cdot W_\text{out} \approx HW / k^2$, so the total work simplifies to $O(CHW)$ — linear in the input size, independent of $k$, because every input pixel is visited exactly once regardless of window size. This is strictly cheaper than a convolution over the same footprint, since convolution's per-output cost is $O(k^2 \cdot C_\text{in} \cdot C_\text{out})$ (it also mixes channels with learned weights), while pooling's per-output cost is $O(k^2)$ with no channel mixing and no weight multiplications. The backward pass has identical asymptotic cost: max pooling revisits each stored argmax index once ($O(1)$ per output element after the argmax was cached), and average pooling redistributes each output gradient over its $k^2$ inputs, giving the same $O(C \cdot H_\text{out} \cdot W_\text{out} \cdot k^2)$ bound.

Space complexity. The output tensor requires $O(C \cdot H_\text{out} \cdot W_\text{out})$ storage. Max pooling additionally caches one argmax index per output element for use in backpropagation, adding another $O(C \cdot H_\text{out} \cdot W_\text{out})$ — the same order, so total memory overhead beyond the output itself is a small constant factor. There are zero learnable parameters, so pooling adds nothing to the model's parameter count or optimizer state (no momentum buffers, no gradient accumulators for weights).

Correctness of the reduction. The forward computation is correct by direct construction: it is defined as exactly the max or mean of the specified window, and the pseudocode implements that definition literally over all valid $(i,j)$ output coordinates, each mapped back to a unique, in-bounds input window (guaranteed by the `floor` in $H_\text{out}$, which discards any partial trailing window). The backward pass is correct because pooling, viewed as a function of its inputs, has a well-defined local gradient at (almost) every point:

• For average pooling, $Y = \frac{1}{k^2}\sum_{p,q} X_{p,q}$ is linear, so $\partial Y / \partial X_{p,q} = 1/k^2$ for every element in the window — exactly what the backward rule distributes.
• For max pooling, $Y = \max_{p,q} X_{p,q}$ has gradient $1$ with respect to whichever input attains the max and $0$ with respect to all others (a subgradient at ties, which the "first occurrence" convention resolves consistently). This is precisely the chain rule for the max function, so routing the full upstream gradient to the argmax and zero elsewhere reproduces $\partial \mathcal{L}/\partial X$ exactly.

When windows overlap ($s < k$), a single input element can lie in multiple windows; the accumulation (`+=`) in the backward pseudocode correctly sums its contribution from each window it participates in, which is required by the multivariable chain rule (total derivative = sum over all paths of influence).

The invariance argument. Approximate translation invariance follows from a simple counting fact: if the input is shifted by $\delta < s$ pixels (less than the stride) and the underlying "salient" activation (e.g., the largest response to a detected feature) stays within the same $k \times k$ window, the max-pooled output is identical for that window — the shift is entirely absorbed. More precisely, for max pooling, output $Y_{i,j}$ only changes if the shift moves the location of the maximum out of window $(i,j)$; for a strong, spatially compact feature (one dominant peak), small shifts usually leave the argmax inside the same window, especially as $k$ grows relative to $\delta$. Average pooling gives a softer version of the same guarantee: it computes a running local mean, so its output changes continuously and by an amount bounded by $\delta \cdot (\text{local gradient of intensity})$, rather than jumping discontinuously — the tradeoff is that a spurious small activation in a window shifts the average even if the true feature location moved only slightly, diluting sharp signals. Neither operation gives exact invariance for all shifts (a shift larger than $k$ or crossing a window boundary at the wrong moment does change the output), which is why the property is called approximate, and why deeper stacks of conv+pool layers are needed to build robustness to larger shifts.

Tradeoffs, honestly stated. Pooling is a lossy, non-invertible operation — information about exact location is permanently discarded, which can hurt tasks (like segmentation or detection) that need precise spatial localization; those architectures typically use skip connections or un-pooling tricks to partially recover it. Max pooling can be overly aggressive, ignoring the magnitude of non-maximal activations entirely, while average pooling can wash out sharp, sparse features by mixing them with background. Since pooling has no parameters, it cannot adapt to data — this is exactly why some modern architectures (Strided Convolutions, where applicable) replace pooling with a learned downsampling convolution, trading pooling's built-in invariance bias for flexibility.

Take a single-channel $4\times4$ feature map, $2\times2$ max pooling, stride $2$ (no overlap, no padding):

Following the forward algorithm: $H_\text{out} = W_\text{out} = \lfloor(4-2)/2\rfloor + 1 = 2$.

The corresponding average pooling output (same windows, mean instead of max):

Notice the smoothing: max pooling reports the strongest local signal (8, in the bottom-right, dominated by the corner value), while average pooling reports a moderated 5.5 — a real difference in what downstream layers "see."

Backward pass for max pooling. Suppose the loss gradient with respect to $Y_\text{max}$ arrives as

Using the cached argmax coordinates, route each entry to its single source pixel and zero everywhere else:

Check: entry $(1,1)=0.5$ matches the argmax of window $Y_{0,0}$; entry $(0,2)=-1.0$ matches the argmax of $Y_{0,1}$; entry $(3,0)=2.0$ matches the argmax of $Y_{1,0}$; entry $(2,3)=1.0$ matches the argmax of $Y_{1,1}$. Every other input pixel — including the "runner-up" values like $5$ at $(1,0)$ or $4$ at $(2,2)$ — receives exactly zero gradient, because they did not determine any output.

Backward pass for average pooling, using the same $dY$: each output gradient is divided by $k^2 = 4$ and spread over its whole window, e.g. window $(0,0)$ gets $0.5/4 = 0.125$ added to all four of its input cells $(0,0),(0,1),(1,0),(1,1)$. This produces a much less sparse $dX$ — every input pixel that contributed to any window receives a nonzero share, reflecting that average pooling treats all inputs in a window as equally responsible for the output.

Pooling's conceptual roots trace to biologically inspired vision models that predate modern deep learning by decades, long before GPUs made large CNNs practical. The idea of combining local feature detection with a spatial-averaging or max-like operation to gain positional tolerance appears explicitly in the Neocognitron, and was carried into trainable convolutional networks by Yann LeCun's group, whose LeNet architecture used subsampling (average-pooling-like) layers between convolutions to build the template for essentially every CNN that followed.

history 1980 — Kunihiko Fukushima's Neocognitron introduces a hierarchy of feature-detecting and spatially-pooling ("S-cell") layers. 1989 — LeCun and collaborators train convolutional networks with backpropagation, using subsampling layers between convolutions. 1998 — LeNet-5 formalizes the conv–pool–conv–pool–fully-connected pipeline for digit recognition. 2012 — AlexNet popularizes overlapping max pooling (stride smaller than window) at ImageNet scale. 2014 onward — Networks such as those using strided convolutions or global average pooling begin replacing or supplementing traditional pooling layers.

Pooling is embedded in nearly every classic image-processing pipeline built on convolutional networks: LeNet and the CNN Blueprint establishes the pattern of alternating convolution and pooling layers that shrink spatial resolution while convolutional filters grow their effective receptive field; AlexNet, VGG, and ResNet-style architectures all use max or average pooling at key downsampling points. Global average pooling, which pools an entire feature map down to a single number per channel, became a standard replacement for large fully connected classification heads, dramatically cutting parameter count and reducing overfitting in image classifiers. In object detection and semantic segmentation, pooling is used cautiously — architectures like U-Net pair pooling-based downsampling with explicit skip connections precisely to counteract the spatial information loss pooling causes. Beyond vision, pooling-like aggregation (max or mean over a set of feature vectors) underlies permutation-invariant architectures for point clouds and set-based data, and average pooling over time steps is a common way to summarize variable-length sequences in some recurrent and attention-based pipelines. Any system that must recognize a pattern regardless of its exact pixel location — face detectors, OCR engines, medical image classifiers — relies on pooling or its modern substitutes to achieve that robustness cheaply.

Ask the tutor: How does the choice between max pooling and average pooling change which features a downstream classifier ends up relying on?