16. Shallow Learning

Chapter PDF · Complete book

16.1 Multilayer Perceptrons¶

A multilayer perceptron (MLP) with one hidden layer has two trainable layers: a hidden layer and an output layer. Models with no hidden layer recover the linear predictors studied earlier. Deeper MLPs compose several layers; their derivatives are efficiently computed by the automatic differentiation methods of the multilayer-perceptron discussion.

16.1.1 Networks of Arbitrary Depth¶

We first define a network of arbitrary depth representing a map $f_\theta : \mathbb{R}^d \to \mathbb{R}^{d'}$.

Starting from $x_0=x\in\mathbb{R}^{d_0}=\mathbb{R}^d$, the network computes, for $s=0,\ldots,S-1$

where $W_s \in \mathbb{R}^{d_{s+1} \times d_s}$ and $b_s \in \mathbb{R}^{d_{s+1}}$. The output is $f_\theta(x)=x_S$, with $d_S=d'$ and parameters $\theta=((W_s,b_s))_{s=0}^{S-1}$. The final activation can be omitted to obtain a linear output layer.

The activation $\sigma$ is a nonlinear, nonpolynomial function applied componentwise: $\sigma(z) = (\sigma(z_i))_i$.

Common activations include the sigmoid functions

and the rectified linear unit (ReLU), $\sigma(r)=\max(r,0)$. Sigmoids are bounded, whereas ReLU is unbounded and does not saturate on the positive half-line: its derivative is one there and zero on the negative half-line. The positive 1-homogeneity of ReLU allows weights to be rescaled, which is useful in proofs that restrict their directions to a unit sphere. At zero, ReLU is not differentiable. Implementations choose a derivative convention, while mathematical arguments must account for the kink.

For increasing width to yield universal approximation at fixed depth, the activation $\sigma$ must be nonpolynomial. Otherwise, $f_\theta$ has degree at most $m^S$ for an activation of degree $m$ and fixed depth $S$, so increasing the width cannot produce a dense class of continuous functions.

The choice $\sigma=\mathrm{Id}$ remains useful for matrix factorization and supervised learning, but its input-output map is affine (linear when the biases vanish).

16.1.2 Two-layer MLPs¶

We now specialize to networks with one hidden layer and a linear output layer:

Here $\sigma$ is the activation, and the neuron parameters are $\theta_k = (u_k \in \mathbb{R}^{d'}, v_k \in \mathbb{R}^d, b_k \in \mathbb{R})$ for $k = 1, \dots, n$. We usually take $d'=1$ for simplicity, so the output is scalar.

In practice, neural networks are trained by gradient methods. For example, consider a quadratic loss

where $\rho$ is the joint distribution of the inputs and outputs. Taking $\rho$ to be the empirical distribution gives the training loss. Gradient descent, or its stochastic counterpart, updates the parameters by

Gradient computation

Omitting the biases $b_k$, the network has the matrix form $f_\theta(x) = U \sigma(V^\top x)$, where $U \in \mathbb{R}^{d' \times n}$ and $V \in \mathbb{R}^{d \times n}$. For a training set with $N$ observations, collect the inputs as the columns of $X = (x_i)_{i=1}^N \in \mathbb{R}^{d \times N}$ and the outputs as the columns of $Y=(y_i)_{i=1}^N\in\mathbb{R}^{d'\times N}$. Here $N$ counts observations and $n$ counts hidden neurons. All matrix norms and inner products in this computation are Frobenius norms and inner products. Omitting the constant factor $1/N$, training with squared loss gives

Set $Z := \sigma(V^\top X)$, the matrix obtained by applying the feature map $x \to \sigma(V^\top x)$ to the data. With these features fixed, training $U$ is the least-squares problem $\frac{1}{2}\|U Z - Y\|^2$, whose gradient is

Assume $\sigma$ is differentiable at the entries of $V^\top X$. To differentiate with respect to $V$, expand the objective in a perturbation $D$ and set $R := U \sigma(V^\top X) - Y$ and $S := \sigma'(V^\top X)$:

where $H=U[S\odot(D^\top X)]$, the product $A \odot B = (A_{i,j} B_{i,j})$ is coordinatewise, and

which leads to

For deeper networks, writing a fully expanded derivative becomes cumbersome and can duplicate computations. Backpropagation organizes the same chain rule into an efficient reverse pass.

16.2 $L^\infty$ Nonquantitative Universal Approximation¶

If $\sigma$ is a sigmoid function, George Cybenko’s theorem, later refined by Kurt Hornik, Maxwell Stinchcombe, and Halbert White, demonstrates that the functions $f_\theta$ can approximate any continuous function uniformly on a compact domain. Uniform approximation is stronger than the mean-square approximation used in the training loss (16.2).

The theorem establishes universal approximation by two-layer networks. It gives no quantitative bound on the number of neurons $n$ needed for accuracy $\varepsilon$, nor an efficient procedure for finding the parameters of $f_\theta$.

Cybenko [15] proved the result by duality. We present the more constructive argument of Hornik and collaborators, based on Stone–Weierstrass approximation by trigonometric functions. This density argument avoids relying on uniform convergence of Fourier partial sums, which need not hold for an arbitrary continuous function.

16.3 $L^2$ Quantitative Approximation (Barron’s Theorem)¶

We now study $L^2$ approximation, as measured by the loss (16.2). To isolate approximation error, assume noiseless observations $y=f(x)$ for a target $f$, with inputs $x$ distributed according to $\rho(x)$. We also assume that $\rho$ is supported in a ball of radius $R$.

Without additional regularity, no uniform approximation rate follows: the error can decay arbitrarily slowly. Barron introduced a function class for which the approximation rate has an exponent independent of the ambient dimension.

16.3.1 Barron Space¶

For an integrable function $f$, this section uses the following normalization of the Fourier transform at $\xi \in \mathbb{R}^d$:

The Barron space [1] is the class of functions for which the Fourier seminorm

is finite. Throughout this section, $f$ denotes its continuous Fourier-inversion representative, with the convention $f(x)=\int\hat f(\xi)e^{\mathrm{i}\langle \xi,\,x\rangle}\mathrm{d}\xi$. For integrable $f$, finiteness of the displayed seminorm ensures that $\hat f$ is integrable: it is bounded near the origin, and its first moment controls the tail. This representative matters when the sampling measure has atoms. Constants can be handled separately; $|f(0)|+|\!| f |\!|_B$ removes the ambiguity due to constants in the corresponding Fourier-measure space. This Fourier-defined class should be distinguished from activation-dependent Barron spaces. One has

which relates the Fourier seminorm to first-order regularity.

The following examples illustrate the seminorm and its dependence on the function class.

• Gaussians: for $f(x) = e^{- |\!| x |\!|^2/2}$, one has $|\!| f |\!|_B=\mathbb{E}|\!| Z |\!|\leqslant\sqrt d,\quad Z\sim\mathcal N(0,\mathrm{Id}_d)$

• Ridge functions: for $f(x)=\psi(\langle x,\,b\rangle+c)$, the Fourier transform may be a measure supported on a line rather than an integrable density. In the Fourier-measure extension of the seminorm,

  $$|\!| f |\!|_B\leqslant|\!| b |\!|\int_\mathbb{R}|u|\,|\hat\psi(u)|\mathrm{d}u.$$

  A sufficient condition is that $\psi$ is compactly supported and belongs to $C^{2,\delta}(\mathbb{R})$ for some $\delta>0$. Smoothness alone without decay is not enough for this Fourier integral.

• Sobolev functions: if $s>d/2+1$, the Cauchy–Schwarz inequality gives

  $$|\!| f |\!|_B\leqslant C(d,s)|\!| f |\!|_{H^s},\qquad |\!| f |\!|_{H^s}^2\mathrel{:=}\int_{\mathbb{R}^d}(1+|\!| \xi |\!|^2)^s|\hat f(\xi)|^2\mathrm{d}\xi.$$

  Indeed, $\int|\!| \xi |\!|^2(1+|\!| \xi |\!|^2)^{-s}\mathrm{d}\xi$ is finite precisely when $s>d/2+1$. For integer $s$, this squared Sobolev norm is equivalent, up to Fourier-normalization constants, to the sum of the squared $L^2$ norms of all weak derivatives of order at most $s$. This is a sufficient condition; the Fourier-measure class also contains ridge functions outside these ambient-space Sobolev classes.

16.3.2 Barron’s Theorem¶

The main result is as follows.

The exponent $1/2$ in the approximation rate does not depend on the dimension. The constant $|\!| f |\!|_B$ can still depend on it: the Gaussian example gives growth of order $\sqrt d$, whereas the bound for a fixed ridge profile depends on the ridge direction and profile.

16.3.3 Mean field representation.¶

Absorb a factor $n$ into the outer coefficients $u_k$ to express the same network as an average:

where $\theta = (\omega_k)_{k=1}^n$, $\omega_k = (u_k, v_k, b_k) \in \mathbb{R}^{d'} \times \mathbb{R}^{d+1}$ and $\varphi(x,\omega) := u \sigma(\langle v, x \rangle + b)$. Introducing the empirical measure:

this neural network can be expressed as an integral:

where $\Omega \subset \mathbb{R}^{d'} \times \mathbb{R}^{d+1}$ is the admissible parameter set. A uniform bound on $u$ will be essential for the approximation estimate.

The representation is linear in the measure $\mu$. It therefore extends naturally from empirical measures to general probability measures $\mu$.

We now restrict to scalar outputs, $d'=1$.

The Fourier condition yields a bounded dictionary representation in a closure sense. This distinction matters: the assumptions do not automatically provide an exact probability measure on finite sigmoid parameters.

For the next argument, write $g=f-f(0)$. First suppose $g=\Phi(\mu)$ exactly for a probability measure over this bounded dictionary. The same bound extends to $g$ in its closed convex hull by approximating $g$ arbitrarily closely before sampling.

16.3.4 Probabilistic proof¶

Draw independent parameters $\omega_1,\ldots,\omega_n$ with law $\mu$ and set $g_n=n^{-1}\sum_i\varphi_{\omega_i}$. In the Hilbert space $L^2(\rho)$, independence yields

Consequently at least one realization has squared error at most $M^2/n$. For a target in the closed convex hull, choose an average $g_\varepsilon$ with $|\!| g-g_\varepsilon |\!|\leqslant\varepsilon$ and apply the same argument. The resulting network has error at most $M/\sqrt n+\varepsilon$. Each outer coefficient has magnitude at most $M/n$, so their absolute sum is at most $M$. This proves the approximation theorem, including its coefficient bound.

16.3.5 Proof by optimization¶

A deterministic argument uses $n$ Frank–Wolfe steps and its $O(1/n)$ objective convergence rate.

For the centered target $g=f-f(0)$, minimize over probability measures $\mathcal{P}(\Omega)$:

where $\rho$ is the probability measure supported on $K$. This optimization problem is infinite-dimensional.

Ordinary network training instead restricts $\mu$ to an empirical measure and descends in the neuron parameters. This parameterization is nonconvex. Chizat and Bach relate suitable mean-field limits to Wasserstein gradient flows and prove global convergence under additional structural and initialization assumptions. Such results do not imply that every sufficiently wide finite network, initialized from an arbitrary density, avoids all nonglobal stationary points.

The deterministic approximation argument below uses convex optimization over measures. Its linear minimization oracle is a global optimization problem over a single neuron’s parameters and may itself be computationally difficult in high dimensions. Since the parameter domain need not be compact, exact oracle minimizers may fail to exist; approximate oracles or closure arguments then replace exact minimization.

First order variations.

We derive the algorithm by linearizing the objective on measures equipped with the total variation norm. The same construction applies to differentiable convex objectives on a Banach space.

We write integration as a pairing between a function and a measure:

Let $\mu+\varepsilon\eta$ be a small perturbation of $\mu$, where $\eta$ is a finite signed measure.

The first variation $\nabla E(\mu)$ represents the derivative through the expansion

Thus $\nabla E(\mu)$ represents the Fréchet derivative of $E$. For the present quadratic objective,

which expands to:

Rewriting this in terms of $\varphi$, we find:

It is a bounded function of $\omega$; continuity follows when the activation and parameterization are continuous.

Frank-Wolfe algorithm.

Frank–Wolfe minimizes a differentiable convex function over a convex subset of a Banach space:

Each step linearizes the objective $E(\mu)$.

Choose an initial measure $\mu_0$, for example a Dirac mass. At iteration $k$, update with step size $\tau_k$:

where $\nu_k^*$ minimizes the linearized objective:

This linear minimization step is called an oracle. On a finite parameter grid it amounts to comparing finitely many values. Over a continuous neuron parameter space $\Omega$, it is generally a nonconvex optimization problem.

Here $\mathcal{C} = \mathcal{P}(\Omega)$ carries the total variation norm $\|\mu\|_{\mathrm{TV}} = |\mu|(\Omega)$, the measure analogue of the $L^1$ norm.

In this special case, a key property of the algorithm is that the solution $\nu_k^*$ can be taken as a Dirac measure when the minimum over $\Omega$ is attained since, denoting $g_k := \nabla E(\mu_k)$,

This holds because for any $\nu \in \mathcal{P}(\Omega)$:

and equality is achieved when $\nu = \delta_{\omega_k^*}$. Therefore, if $\mu_0$ is initialized as a Dirac measure, each iteration of the algorithm ensures that $\mu_k$ remains a sum of at most $k+1$ Dirac masses.

Convergence Rate

The next theorem gives the Frank–Wolfe convergence rate.

In our case, $\|\cdot\|=\|\cdot\|_{\mathrm{TV}}$ is the total variation norm of measures. Bounded functions paired with these measures carry the supremum norm $\|\cdot\|_{\infty}$. Throughout this argument, $L^\infty$ denotes the pointwise supremum norm, so values at atoms are retained.

We first establish the quadratic upper bound implied by a Lipschitz gradient.

For the objective $E$ in (16.4), the proposition below gives $L\leqslant M^2$ with $M=2R\|f\|_B$. The total variation diameter of probability measures is $D=2$, and $\|f\|_B$ denotes the Barron seminorm of the target $f$.

For the centered target $g=f-f(0)$, Proposition 16.3 gives $\inf E=0$, even if the infimum is not attained by a measure on finite sigmoid parameters. The rate therefore concerns approximation of $g$.

When the linear oracle attains its minimum, Frank–Wolfe constructs a measure $\mu_k$ supported on at most $k+1$ points, with objective error

Thus each iteration adds at most one neuron and gives an $O(k^{-1/2})$ bound on the $L^2$ error. If the oracle is not attained, choosing an $O(1/k)$-accurate linear oracle adds an $O(1/k^2)$ term to the descent recurrence and preserves this order of approximation.