From linear models to networks

The previous note ended with the strongest tool for tables: boosted trees, and stacking on top of them. Every model of the course so far takes its features as given. Least squares and logistic regression fit a linear function of them, kernels fix a nonlinear feature map in advance, and trees split on the columns someone prepared. That works when the columns already mean something, such as an income, an age or a count of purchases. It fails for raw signals. A single pixel, a single audio sample or a single token identity usually says little on its own, and for decades the useful features of images, sound and text were designed by hand: edge histograms, spectral coefficients, n-gram counts. A neural network learns the feature map from the data, together with the linear model on top of it, by the same gradient descent as before. This note builds the network from linear models, states what such networks can represent, and sets up their outputs and losses; the next note computes their gradients.

Notation. An input $x \in \mathbb R^d$. A network has layers $l = 1, \dots, L$ of widths $d_1, \dots, d_L$, with $d_0 = d$. Layer $l$ has a weight matrix $W_l \in \mathbb R^{d_l \times d_{l-1}}$ and a bias $b_l \in \mathbb R^{d_l}$; it computes the pre-activation $z_l = W_l h_{l-1} + b_l$ and the activation $h_l = \varphi(z_l)$, with $h_0 = x$ and an activation function $\varphi$ applied to each coordinate. The last layer has no activation: its output $f(x) = z_L$ is a prediction or a vector of logits. $\sigma(t) = 1/(1 + e^{-t})$ is the logistic sigmoid, and $\theta$ collects all weights and biases.

Why stacking linear layers is not enough#

The first idea is to compose linear maps. It gains nothing: two affine layers are one affine layer,

$$W_2 (W_1 x + b_1) + b_2 = (W_2 W_1)\, x + (W_2 b_1 + b_2),$$

and by induction so are any number of them. Depth without a nonlinearity adds parameters, not expressiveness: the stack is a linear model with weight matrix $W_L \cdots W_1$, whose rank is at most the smallest width, so a narrow layer can only restrict it.

A nonlinearity between the layers changes this. With one hidden layer,

$$f(x) = W_2\, \varphi(W_1 x + b_1) + b_2 ,$$

the output is a linear model applied to the features $h = \varphi(W_1 x + b_1)$, and those features are themselves learned.

Worked example: XOR. The four points $(0,0), (0,1), (1,0), (1,1)$ with labels $0, 1, 1, 0$ cannot be separated by a line. If $w_1 x_1 + w_2 x_2 + c > 0$ held exactly for the two points labelled 1, then $w_2 + c > 0$ and $w_1 + c > 0$, while $c \le 0$ and $w_1 + w_2 + c \le 0$. Adding the first two inequalities gives $w_1 + w_2 + c > -c \ge 0$, a contradiction. Two ReLU units, $\operatorname{ReLU}(t) = \max(0, t)$, are enough (Goodfellow, Bengio and Courville, 2016, section 6.1). Take $h_1 = \operatorname{ReLU}(x_1 + x_2)$, $h_2 = \operatorname{ReLU}(x_1 + x_2 - 1)$ and $f = h_1 - 2h_2$:

$x$	$x_1 + x_2$	$h_1$	$h_2$	$f$
$(0, 0)$	0	0	0	0
$(0, 1)$	1	1	0	1
$(1, 0)$	1	1	0	1
$(1, 1)$	2	2	1	0

In the hidden coordinates $(h_1, h_2)$ the inputs become $(0,0)$, $(1,0)$, $(1,0)$ and $(2,1)$. The two points of class 1 land on the same spot, and a line, such as $h_1 - 2h_2 = \tfrac12$, separates the classes. The hidden layer has made the problem linear.

The multilayer perceptron#

Stacking such layers gives the multilayer perceptron (MLP), also called a fully connected or feed-forward network:

$$\begin{aligned} z_l &= W_l h_{l-1} + b_l, \qquad h_l = \varphi(z_l), \qquad l = 1, \dots, L-1, \\ f(x) &= W_L h_{L-1} + b_L . \end{aligned}$$

Each hidden unit computes $\varphi(w^\top h + b)$ for one row $w$ of its weight matrix: a linear model of the previous layer followed by a fixed nonlinearity. With $\varphi = \sigma$, a hidden unit has the functional form of a logistic regression, a sigmoid of an affine function, and the network is a linear model on features of that form computed from features of that form. The analogy stops at the form: a hidden unit has no observed 0/1 target of its own, and its weights are trained jointly with the rest of the network.

In practice the network processes a mini-batch of $n$ examples at once, stored as the rows of $X \in \mathbb R^{n \times d}$. Then every layer is one matrix product, $Z_l = H_{l-1} W_l^\top + \mathbf 1 b_l^\top$, with $H_0 = X$ and the bias added to every row. PyTorch’s nn.Linear(d_in, d_out) stores its weight with shape (d_out, d_in), the shape of $W_l$ here, and computes x @ W.T + b.

Worked example: shapes. A classifier of $8 \times 8$ images of digits into 10 classes, with layer widths $64 \to 128 \to 64 \to 10$:

layer	weight $W_l$	bias $b_l$	parameters	output for a batch of 32
input				$32 \times 64$
1	$128 \times 64$	128	8,320	$32 \times 128$
2	$64 \times 128$	64	8,256	$32 \times 64$
3 (logits)	$10 \times 64$	10	650	$32 \times 10$

The network has $17{,}226$ parameters, almost all of them in the weight matrices; the count grows with the product of neighbouring widths.

Activation functions#

	$\varphi(t)$	$\varphi'(t)$	range	typical use
sigmoid	$\sigma(t) = \dfrac{1}{1 + e^{-t}}$	$\sigma(t)\,(1 - \sigma(t)) \le \tfrac14$	$(0, 1)$	output probabilities, gates
tanh	$\tanh t = 2\sigma(2t) - 1$	$1 - \tanh^2 t \le 1$	$(-1, 1)$	recurrent networks
ReLU	$\max(0, t)$	$1$ for $t > 0$, $0$ for $t < 0$	$[0, \infty)$	default for hidden layers
GELU	$t\, \Phi(t)$	$\Phi(t) + t\, \phi(t)$	$[-0.170, \infty)$	Transformers

Here $\Phi$ and $\phi$ are the distribution function and the density of the standard normal. Three properties matter:

• Saturation. The sigmoid and tanh flatten for large $\lvert t \rvert$, where their derivative is close to zero. A unit driven there passes almost no gradient back, and in a stack of sigmoid layers the sigmoid’s derivative contributes a factor of at most $\tfrac14$ per layer; the Generative Models course works this out.
• ReLU (Nair and Hinton, 2010; Glorot, Bordes and Bengio, 2011) has slope exactly 1 wherever it is active and is cheap to compute. Its weakness is the other side: a unit whose pre-activation is negative for every input gets zero gradient and never recovers, a “dead” unit.
• GELU (Hendrycks and Gimpel, 2016, section 2) multiplies $t$ by the probability $\Phi(t)$ that a standard normal variable is below it. It is a smooth ReLU that lets small negative values through: its minimum is $-0.170$ at $t = -0.752$. BERT and GPT-2 use it in the feed-forward part of each Transformer block.

The choice is less important than having a nonlinearity at all. The next section shows the one property that the universal approximation theorem for a single hidden layer requires of the activation: it must not be a polynomial. That is a condition of the theorem, not of every useful network.

What one hidden layer can represent#

Optional depth: the approximation theorems behind the key idea below, and what they leave open. The rest of the note does not depend on it.

The theorem. Let $\sigma$ be any continuous sigmoidal function, meaning $\sigma(t) \to 1$ as $t \to +\infty$ and $\sigma(t) \to 0$ as $t \to -\infty$. For every continuous function $g$ on the unit cube $[0,1]^d$ and every $\varepsilon > 0$ there are a number $N$ and parameters $\alpha_j, \beta_j \in \mathbb R$, $w_j \in \mathbb R^d$ such that

$$G(x) = \sum_{j=1}^{N} \alpha_j\, \sigma(w_j^\top x + \beta_j) \quad \text{satisfies} \quad \lvert G(x) - g(x) \rvert < \varepsilon \ \text{ for all } x \in [0,1]^d$$

(Cybenko, 1989, Theorem 2). $G$ is an MLP with one hidden layer of $N$ units and a linear output. Hornik (1991), Theorem 2, extends the statement to any continuous, bounded and nonconstant activation on any compact (closed and bounded) set, and Leshno et al. (1993), Theorem 1, settle it for unbounded activations such as the ReLU: for a locally bounded, piecewise continuous $\varphi$, one-hidden-layer networks approximate every continuous function uniformly on compact sets if and only if $\varphi$ is not a polynomial. A polynomial activation of degree $k$ fails because the network is then a polynomial of degree at most $k$ in $x$, whatever its width.

Worked example: ReLU units as a piecewise-linear fit. In one dimension the construction is explicit. Put knots $x_k = k/N$ on $[0, 1]$ and let $s_k$ be the slope of the straight segment from $(x_k, g(x_k))$ to $(x_{k+1}, g(x_{k+1}))$. The broken line through the points is

$$\hat g(x) = g(0) + \sum_{k=0}^{N-1} c_k\, \operatorname{ReLU}(x - x_k), \qquad c_0 = s_0,\ \ c_k = s_k - s_{k-1},$$

a network with one hidden layer of $N$ ReLU units: unit $k$ switches on at the knot $x_k$ and changes the slope by $c_k$. For $g(x) = \sin 2\pi x$ the largest error on $[0, 1]$ is $0.2105$, $0.0704$, $0.0188$ and $0.0048$ with $N = 4, 8, 16, 32$ units. Doubling the width divides the error by about 4, as the interpolation bound $\tfrac18 h^2 \max \lvert g'' \rvert$ with spacing $h = 1/N$ predicts.

What the theorem does not promise#

• A reasonable size. The theorem is about existence. Cybenko’s own summary (section 5) expects that most approximation problems need astronomical numbers of units, because of the curse of dimensionality met in the nearest neighbours note. The piecewise-linear construction tiles the input: with 16 knots per axis in $d = 10$ dimensions it needs $16^{10} \approx 1.1 \cdot 10^{12}$ cells. Whether far fewer units suffice depends on the function. Barron (1993) shows that for functions whose Fourier transform has a finite first moment $C_g$, $N$ sigmoidal units reach an integrated squared error of order $C_g^2/N$, with no dependence on the dimension, while any fixed set of $N$ basis functions cannot beat order $N^{-2/d}$ on that class.
• That training finds it. The weights exist; the loss as a function of them is not convex, and gradient descent may stop elsewhere. The XOR experiment below shows it happening.
• That a sample suffices. Approximating the true function and estimating it from $n$ noisy examples are different problems. A wide network can fit any training set, noise included, which is overfitting in its purest form.
• Anything outside the region. The guarantee holds on a compact set. Beyond the range of the training inputs a ReLU network simply continues linearly, which is rarely what the data would do there.

Depth versus width#

Optional depth: why depth can be exponentially more efficient than width, with an exact example. The rest of the note does not depend on it.

If one hidden layer is universal, why use many? Because composition is much more efficient than addition for some functions. A one-dimensional example makes this exact.

Worked example: the tent map. On $[0, 1]$ the network

$$g(x) = 2\operatorname{ReLU}(x) - 4\operatorname{ReLU}\big(x - \tfrac12\big)$$

is a tent: $g(x) = 2x$ for $x \le \tfrac12$ and $g(x) = 2 - 2x$ for $x \ge \tfrac12$, with values in $[0, 1]$. Composing it with itself, $g \circ g$, runs the tent twice up and down: 4 linear pieces. Each further composition doubles the count, so $g^{k} = g \circ \dots \circ g$ has $2^k$ pieces. As a network, $g^k$ has $k$ hidden layers of 2 ReLU units each (Telgarsky, 2016, Lemma 3.10).

A network with one hidden layer of $m$ ReLU units computes $c + \sum_{j=1}^m a_j \operatorname{ReLU}(w_j x + \beta_j)$ on a line. This is linear between the $m$ break points $-\beta_j / w_j$, so it has at most $m + 1$ pieces. To represent $g^k$ exactly it needs $m \ge 2^k - 1$ units: 31 against the deep network’s 10 for $k = 5$, and $1{,}048{,}575$ against 40 for $k = 20$.

Figure

Depth multiplies the number of linear pieces

The general statements behind the example: the number of linear regions of a ReLU network can grow exponentially with depth and only polynomially with width (Montúfar et al., 2014), and there are functions computed by deep narrow ReLU networks that no network with far fewer layers approximates unless it is exponentially wide (Telgarsky, 2016, Theorem 1.1). Depth lets later layers reuse what earlier layers computed. In image networks the early layers detect edges and later layers combine them into parts and objects, as the convolution section of the Generative Models course describes.

Depth has a price. Every layer multiplies the gradient by another factor, and deep stacks are harder to optimize than shallow ones; Training deep networks deals with that. Width also helps optimization: a wider network has many more ways to fit the data, and gradient descent finds one of them more reliably, as the next experiment shows.

A network learns its own features#

The XOR construction above was designed by hand. The same features come out of training. Take 200 points in four clusters around $(\pm 1, \pm 1)$, with class 1 where the signs differ, and a network with two tanh hidden units and a sigmoid output, trained by gradient descent (Adam, 300 full-batch steps) on the binary cross-entropy:

Figure

A network finds its own features for XOR

The trained network classifies all 200 points correctly. Its first hidden unit, $h_1 = \tanh(3.8x_1 + 3.2x_2 + 3.4)$, is negative only when both coordinates are negative: an OR. The second, $h_2 = \tanh(3.4x_1 + 3.4x_2 - 3.1)$, is positive only when both are positive: an AND. The output unit computes $\sigma(5.3h_1 - 5.4h_2 - 5.2)$, which is large exactly when the OR is on and the AND is off. Up to the smooth activation, these are the two features of the hand-made solution, found by fitting.

The optimization is not guaranteed, though. Training the same two-unit network from 10 random initializations, only 4 runs separate the classes; the other 6 stop at a poor solution with 65–75% accuracy. With four hidden units all 10 runs succeed. Extra width costs parameters and buys an easier optimization problem.

The same reading holds for any network: the last layer is a linear model on the features $h_{L-1}(x)$ computed by the layers below it. On the two-moons data of the Code section (1000 points, noise 0.2, half held out), logistic regression on the raw coordinates reaches a test accuracy of $0.848$, while a network $2 \to 16 \to 16 \to 1$ reaches $0.958$. Fitting a fresh logistic regression to the network’s 16 last-layer features also gives $0.958$: everything nonlinear happened in the feature map, and the classifier on top is the logistic regression of earlier notes.

Output layers and losses#

The output layer and the loss are chosen together, and the choice is the probabilistic one of the linear models: the network outputs the parameters of a distribution for $y$, and the loss is the negative log-likelihood, as derived in the maximum likelihood note.

task	output units	output activation	model for $y$	loss	PyTorch
regression	1 (or $k$)	none	$N(f(x), \sigma^2)$	squared error	MSELoss
two classes	1 logit	sigmoid	$\mathrm{Bernoulli}(\sigma(f(x)))$	binary cross-entropy	BCEWithLogitsLoss
$K$ classes	$K$ logits	softmax	$\mathrm{Categorical}(\operatorname{softmax} f(x))$	cross-entropy	CrossEntropyLoss
$K$ labels	$K$ logits	$K$ sigmoids	$K$ independent Bernoullis	sum of $K$ binary cross-entropies	BCEWithLogitsLoss

The binary row makes the last layer a logistic regression on $h_{L-1}$, and the two lower rows are the softmax and the one-vs-rest models of the multiclass note, now on learned features. With the softmax $p_k = e^{z_k} / \sum_j e^{z_j}$ and true class $y$, the cross-entropy is

$$-\log p_y = -z_y + \log \sum_{j=1}^{K} e^{z_j} .$$

Worked example. For the logits $z = (2, 1, -1)$, $e^z = (7.389, 2.718, 0.368)$ with sum $10.475$, so $p = (0.705, 0.259, 0.035)$. If the true class is the first, the loss is $-\log 0.705 = 0.349$; if it were the third, the loss would be $-\log 0.035 = 3.35$.

The PyTorch losses in the table take logits, not probabilities, and they compute $\log \sum_j e^{z_j}$ as $m + \log \sum_j e^{z_j - m}$ with $m = \max_j z_j$. For logits $(1000, 0)$ the naive $e^{1000}$ overflows, while the shifted form gives the loss exactly. Applying a sigmoid or softmax in the model and a loss on top of the probabilities loses this protection. The same softmax over a vocabulary is the output layer of every neural language model in the NLP course, and the Generative Models course explains why minimizing cross-entropy minimizes a KL divergence.

Convolutions: a constrained linear layer#

When the input has a grid structure, such as the pixels of an image, the samples of a sound or the tokens of a sentence, a fully connected first layer wastes parameters and ignores locality. A $32 \times 32$ colour image has $3072$ inputs; a fully connected layer producing a $32 \times 32$ map with 16 channels needs $3072 \times 16{,}384 \approx 50.3$ million weights. A convolution layer applies the same small kernel at every position instead: each output looks only at a neighbourhood (locality), and the kernel is shared across positions (weight sharing), so the same layer with $3 \times 3$ kernels has $16 \cdot 3 \cdot 9 + 16 = 448$ parameters. It is still a linear layer, with a weight matrix constrained to be sparse and repetitive, and everything in this note and the next applies to it. Its shapes, parameters and initialization are worked out in the Generative Models course, and the NLP course uses one-dimensional convolutions over the tokens of a text.

What changed#

	Linear models, kernels, boosting	Neural networks
Features	given, hand-made, or fixed by a kernel	learned by the hidden layers
Model	linear in fixed features, or a sum of trees	compositions of linear maps and nonlinearities
What it can represent	limited by the features	any continuous function on a bounded region, with enough units
Output and loss	sigmoid or softmax with cross-entropy, squared error	the same, as the last layer
Training	convex (linear, logistic) or greedy (trees)	nonconvex, by gradient descent through all layers

Limitations#

• Nonconvex training. Different initializations give different networks, and some runs fail, as the two-unit XOR network did in 6 of 10 runs. Results must be checked over seeds.
• Data and compute. A network has many parameters and needs many examples to estimate them. On typical tabular data of moderate size, tree ensembles still match or beat networks (Grinsztajn, Oyallon and Varoquaux, 2022); networks win where features must be learned from raw signals.
• Existence is not construction. The universal approximation theorem gives no width, no training procedure and no sample size.
• Many design choices. Depth, width, activation, initialization, learning rate and regularization all matter; the last note of this section collects the standard choices.
• Opaque features. A learned feature is a direction in a hidden layer, not a named column, which makes the model harder to explain than a tree or a linear model.

What you should remember#

• Linear layers compose to a linear layer; a nonlinearity between them is what makes depth useful.
• An MLP computes $h_l = \varphi(W_l h_{l-1} + b_l)$ with $W_l \in \mathbb R^{d_l \times d_{l-1}}$; the last layer is a linear model (logits) on learned features.
• ReLU is the default hidden activation, GELU its smooth version; sigmoid and tanh saturate.
• One hidden layer approximates any continuous function on a compact set iff the activation is not a polynomial (Cybenko, Hornik, Leshno et al.), but without a bound on the width, a guarantee of training or of generalization.
• Depth can be exponentially more efficient than width: $k$ layers of 2 ReLU units make $2^k$ linear pieces, one layer needs $2^k - 1$ units.
• Output layer and loss come from the likelihood: identity with squared error, sigmoid with binary cross-entropy, softmax with cross-entropy; pass logits to the loss.

Code#

Linear layers collapsing, XOR by hand, parameter counts, the softmax loss, features learned on two moons, ReLU interpolation and the tent map:

import numpy as np, torch
from torch import nn
from sklearn.datasets import make_moons
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import train_test_split

rng = np.random.default_rng(0)
relu = lambda z: np.maximum(z, 0)

# two linear layers are one linear layer: W2 (W1 x + b1) + b2 = (W2 W1) x + (W2 b1 + b2)
W1, b1, W2, b2, x = rng.normal(size=(4, 3)), rng.normal(size=4), rng.normal(size=(2, 4)), rng.normal(size=2), rng.normal(size=3)
print(np.allclose(W2 @ (W1 @ x + b1) + b2, (W2 @ W1) @ x + (W2 @ b1 + b2)))   # True

# XOR with two ReLU units: h = ReLU(x1 + x2, x1 + x2 - 1), output h1 - 2 h2
X = np.array([[0, 0], [0, 1], [1, 0], [1, 1]])
h = relu(X @ np.array([[1, 1], [1, 1]]) + np.array([0, -1]))
print(h.tolist(), (h @ np.array([1, -2])).tolist())   # [[0, 0], [1, 0], [1, 0], [2, 1]] [0, 1, 1, 0]

# parameters of a 64 -> 128 -> 64 -> 10 network
mlp = nn.Sequential(nn.Linear(64, 128), nn.ReLU(), nn.Linear(128, 64), nn.ReLU(), nn.Linear(64, 10))
print(sum(p.numel() for p in mlp.parameters()))   # 17226

# softmax and cross-entropy for the logits (2, 1, -1) when the true class is the first
z = torch.tensor([2.0, 1.0, -1.0])
print(torch.softmax(z, 0).numpy().round(3), round(nn.functional.cross_entropy(z[None], torch.tensor([0])).item(), 3))
# [0.705 0.259 0.035] 0.349

# two moons: logistic regression on (x1, x2) against a network 2 -> 16 -> 16 -> 1
Xm, ym = make_moons(1000, noise=0.2, random_state=0)
Xtr, Xte, ytr, yte = train_test_split(Xm, ym, test_size=0.5, random_state=0)
print(round(LogisticRegression().fit(Xtr, ytr).score(Xte, yte), 3))   # 0.848
torch.manual_seed(0)
body = nn.Sequential(nn.Linear(2, 16), nn.ReLU(), nn.Linear(16, 16), nn.ReLU())
head = nn.Linear(16, 1)
opt = torch.optim.Adam([*body.parameters(), *head.parameters()], lr=0.01)
Xt, yt = torch.tensor(Xtr, dtype=torch.float32), torch.tensor(ytr, dtype=torch.float32)
for step in range(1000):
    opt.zero_grad()
    loss = nn.functional.binary_cross_entropy_with_logits(head(body(Xt)).squeeze(1), yt)
    loss.backward()
    opt.step()
with torch.no_grad():
    Ftr, Fte = body(Xt).numpy(), body(torch.tensor(Xte, dtype=torch.float32)).numpy()
    acc = ((head(torch.tensor(Fte)).squeeze(1) > 0).numpy() == yte).mean()
# the network, and a fresh logistic regression on the network's 16 last-layer features
print(round(float(acc), 3), round(LogisticRegression(max_iter=1000).fit(Ftr, ytr).score(Fte, yte), 3))   # 0.958 0.958

# one hidden layer of N ReLU units interpolating sin(2 pi x) at N + 1 knots: the error falls like 1/N^2
f = lambda t: np.sin(2 * np.pi * t)
grid = np.linspace(0, 1, 10001)
for N in (4, 8, 16, 32):
    knots = np.linspace(0, 1, N + 1)
    slopes = np.diff(f(knots)) * N
    c = np.diff(slopes, prepend=0.0)
    approx = f(0) + relu(grid[:, None] - knots[:-1]) @ c
    print(N, round(float(np.abs(approx - f(grid)).max()), 4))
# 4 0.2105 | 8 0.0704 | 16 0.0188 | 32 0.0048

# depth: the tent map g(x) = 2 ReLU(x) - 4 ReLU(x - 1/2) composed k times has 2^k linear pieces
g = lambda t: 2 * relu(t) - 4 * relu(t - 0.5)
t = np.linspace(0, 1, 2**12 + 1)
for k in (1, 2, 3, 5):
    y = t.copy()
    for _ in range(k):
        y = g(y)
    slopes = np.round(np.diff(y) / np.diff(t), 6)
    print(k, 1 + int((slopes[1:] != slopes[:-1]).sum()))
# 1 2 | 2 4 | 3 8 | 5 32

Next#

A network is a composition of simple functions with thousands or millions of parameters, and fitting it by gradient descent needs the gradient of the loss with respect to every one of them at every step. Differentiating numerically would cost one forward pass per parameter. The next note shows how the chain rule, applied from the loss backwards through the computational graph, gives all of them for about the cost of a single forward pass.

References#

• G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals, and Systems, 2(4):303–314, 1989. Theorem 2 (one hidden layer is dense in $C([0,1]^d)$); section 5 (on the number of units).
• K. Hornik. Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2):251–257, 1991. Theorems 1 and 2.
• M. Leshno, V. Ya. Lin, A. Pinkus, S. Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural Networks, 6(6):861–867, 1993. Theorem 1.
• A. R. Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information Theory, 39(3):930–945, 1993.
• M. Telgarsky. Benefits of depth in neural networks. COLT, 2016. Theorem 1.1 (depth separation); Lemma 3.10 (the tent map as a ReLU network).
• G. Montúfar, R. Pascanu, K. Cho, Y. Bengio. On the number of linear regions of deep neural networks. NeurIPS, 2014.
• V. Nair, G. E. Hinton. Rectified linear units improve restricted Boltzmann machines. ICML, 2010.
• X. Glorot, A. Bordes, Y. Bengio. Deep sparse rectifier neural networks. AISTATS, 2011.
• D. Hendrycks, K. Gimpel. Gaussian error linear units (GELUs). arXiv:1606.08415, 2016. Section 2.
• L. Grinsztajn, E. Oyallon, G. Varoquaux. Why do tree-based models still outperform deep learning on typical tabular data? NeurIPS Datasets and Benchmarks Track, 2022.
• I. Goodfellow, Y. Bengio, A. Courville. Deep Learning. MIT Press, 2016. Section 6.1 (learning XOR), sections 6.2–6.4 (output units, hidden units, architecture and universal approximation).
• C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. Section 5.1 (feed-forward network functions).
• E. Sokolov et al. Машинное обучение (HSE), lecture notes, lecture 7: introduction to deep learning.