Multi-Layer Perceptron

The model

For an input $x \in \mathbb{R}^{d_0}$, an $L$-layer MLP is

with weights $W_\ell \in \mathbb{R}^{d_\ell \times d_{\ell-1}}$, biases $b_\ell \in \mathbb{R}^{d_\ell}$, and element-wise activation $\sigma_\ell$. The output $h_L$ is interpreted as a regression target, a classification logit, or (after softmax) a probability vector.

Why a non-linearity is mandatory

If every $\sigma_\ell$ is the identity, then

a single affine map. Depth without non-linearity buys nothing. Even one layer of element-wise non-linearity unlocks universal approximation.

Backprop in one slide

For a scalar loss $\mathcal{L}$, define $\delta_\ell = \partial \mathcal{L} / \partial z_\ell$ where $z_\ell = W_\ell h_{\ell-1} + b_\ell$ is the pre-activation. Then

This is reverse-mode automatic differentiation specialized to a feed-forward DAG. Cost: one backward pass per loss, with the same asymptotic complexity as one forward pass [10].

Cybenko’s theorem (sigmoidal version)

A function $\sigma : \mathbb{R} \to \mathbb{R}$ is sigmoidal if $\sigma(t) \to 1$ as $t \to +\infty$ and $\sigma(t) \to 0$ as $t \to -\infty$. Cybenko proved [1]:

Let $\sigma$ be any continuous sigmoidal function and let $K \subset \mathbb{R}^d$ be compact. For any continuous $f : K \to \mathbb{R}$ and any $\epsilon > 0$, there exist a finite $N$, weights $w_j \in \mathbb{R}^d$, biases $b_j \in \mathbb{R}$, and coefficients $\alpha_j \in \mathbb{R}$ such that

$$\sup_{x \in K}\, \Bigl|\, f(x) \;-\; \sum_{j=1}^{N} \alpha_j\, \sigma(w_j^\top x + b_j) \,\Bigr| < \epsilon.$$

In words: a single hidden layer of finite width with a sigmoidal activation can uniformly approximate any continuous function on a compact set.

The proof is a Hahn-Banach plus Riesz representation argument: assume the closure of finite sums is not dense in $C(K)$, derive a non-zero signed measure that annihilates every $\sigma(w^\top x + b)$, then show that any sigmoidal $\sigma$ is discriminatory, contradicting the construction. The constructive content is hidden inside the contradiction; the bound $N$ is not given.

Hornik’s extension

Hornik 1991 [2] generalized the theorem in two directions:

1. The activation can be any non-constant, bounded, continuous function (not specifically sigmoidal).
2. The result extends from $C(K)$ to $L^p(\mu)$ for any finite measure $\mu$, with convergence in $L^p$ norm.

A polynomial activation cannot do this (the span of polynomials of bounded degree is finite-dimensional), which is why ReLU is fine (non-polynomial, piecewise-linear) but $\sigma(t) = t^2$ is not.

What the theorem does not say

Universal approximation is an existence statement. It is silent on:

• How wide $N$ must be. The required width can grow exponentially in the input dimension (curse of dimensionality).
• Whether SGD finds the approximating weights. Optimization is a separate problem.
• Generalization. Approximation is on the training data; test error needs additional assumptions (smoothness, margin, low intrinsic dimension).

This is the gap depth fills.

Telgarsky [3] constructed a family of functions on $[0, 1]$ that a deep ReLU network with $\Theta(k^3)$ layers and constant width can represent exactly, but any shallow network with two layers needs at least

to approximate within constant error. The idea is that ReLU networks with depth can implement repeated sawtooth folds: each layer doubles the number of linear pieces, so $L$ layers give $2^{L}$ pieces with $O(L)$ parameters, while a shallow net needs $\Omega(2^L)$ parameters to write the same number of pieces directly.

Concretely, the function $f_k$ is a triangle wave folded $k$ times. A 3-layer ReLU net of width 2 represents one fold; composition of $k$ such blocks is a $(2k+1)$-layer net with $O(k)$ parameters. Reproducing $f_k$ with a 2-layer net requires one hidden unit per linear piece, so $\Omega(2^k)$ units.

The takeaway: width and depth are not parameter-equivalent. Some functions are exponentially cheaper to express with depth, even if width alone is universal.

This complements universal approximation: depth is not strictly necessary in theory, but it is exponentially more efficient on the structured functions we actually want to learn (compositional, hierarchical, with shared sub-features) [11][12].

Setup

At initialization, treat the input $x$ to a layer as a random vector with zero mean and unit variance per coordinate, and treat the weights $W_{ij}$ as iid with mean zero and variance $\mathrm{Var}(W)$, independent of $x$. Look at one pre-activation:

so $\mathbb{E}[z_j] = 0$ and

For the pre-activation variance to equal the input variance we need

Glorot/Xavier (tanh)

For tanh, the activation acts approximately linearly near zero, so the same condition applies on the backward pass with $n_{\text{out}}$ in place of $n_{\text{in}}$. Glorot and Bengio [4] compromised between the two by averaging:

In practice this is sampled either as $W_{ij} \sim \mathcal{N}(0, 2/(n_{\text{in}} + n_{\text{out}}))$ or uniformly on $[-\sqrt{6/(n_{\text{in}} + n_{\text{out}})},\, \sqrt{6/(n_{\text{in}} + n_{\text{out}})}]$ (same variance).

He (ReLU)

ReLU kills half of the pre-activations: $\mathrm{Var}(\text{ReLU}(z)) \approx \tfrac{1}{2}\mathrm{Var}(z)$ when $z$ is symmetric around zero. To compensate, He et al. [5] doubled the variance:

Why it matters

Without variance preservation:

• Too small a variance: pre-activations shrink toward zero, gradients shrink with them, and the network is stuck.
• Too large: pre-activations explode, ReLU gradients become huge for the active half, training diverges.

He init is the default for ReLU/Leaky-ReLU/GELU networks today (torch.nn.init.kaiming_normal_); Xavier remains correct for tanh/sigmoid layers and is still used in attention’s softmax temperature.