Lec 03. Approximation Theory

Overview

The lecturer introduces the universal function approximation property of neural networks, frames the central design question of depth versus width, and presents a three‑part learning framework (approximation, optimization, generalization). Motivating examples—including a non‑linearly separable 2‑D dataset and the pathological Weierstrass function—illustrate the need to formalize when a network family can approximate a target function within a chosen error tolerance. The segment introduces a specific error bound for approximating a target function with a three‑layer ReLU network, explains the geometric setting of a unit hyper‑cube, defines key notation (n, ε, Lipschitz constant), and highlights the exponential dependence of required neurons on dimension and error tolerance. The instructor also outlines the proof strategy beginning with a one‑dimensional reduction.

Chapter breakdown

Key points

• 00:22Prompted discussion on whether to increase the width or the depth of a neural network architecture.
• 05:12Presented the Weierstrass (nowhere‑differentiable) function as a pathological example to motivate questions about neural network expressivity.
• 09:34Presents Lipschitz continuity: a function g is L‑Lipschitz if |g(x+Δx)‑g(x)| ≤ L·|Δx| for every x and Δx.
• 14:45States a universal approximation result: any L‑Lipschitz function on the d‑dimensional hyper‑cube can be approximated within any error tolerance by a three‑layer ReLU network of sufficient width.
• 18:14The theorem is presented mainly as an illustrative example; its primary purpose is to show a concrete proof technique rather than to claim a deep result.
• 23:11Three‑step strategy: (1) approximate with 1‑D rectangles, (2) extend to multi‑dimensional hyper‑rectangles, (3) show a two‑layer network can represent a hyper‑rectangle.
• 27:36Inverting the bound gives the required number of strips: n ≥ L ⁄ ε (up to a constant factor).
• 31:00To achieve an approximation error of ε for a d‑dimensional function, we need on the order of L·ε⁻ᵈ hyper‑rectangles.
• 36:14For a finite number of strips (rectangles) the Lipschitz constant is used to bound the approximation error, rather than taking a limit as the number of strips → ∞.
• 39:34The constant C is sent to infinity to make the ReLU slopes arbitrarily steep, turning the approximate hyper‑rectangle into an exact indicator.
• 43:05Neuron count analysis shows the construction requires 4 · d neurons per hyper‑rectangle, leading to the “4d” term in the size bound.
• 48:05Listed other universal approximators: polynomials, random feature models, and even programming languages (e.g., Python programs).
• 52:30Advantages of wide networks include parallelism, richer feature representations, and easier training/optimization.
• 56:13Defines piecewise‑linear functions and introduces the notion of a “kink” as a discontinuity in the derivative.
• 01:01:10Applying a ReLU to a function can at most double its number of kinks because each linear segment can be split into at most two linear pieces.
• 01:06:23An upper bound is not enough; a constructive example using a small ReLU “triangle” network shows the bound can be attained through composition.
• 01:08:36This illustrates depth separation: deep networks can represent certain functions that shallow ones can only approximate with astronomically larger width.
• 01:12:10Deciding whether to increase width or depth for efficient LLM training is an open, practical problem with no clear-cut answer.
• 17:34Depth separation shows that deeper networks can represent certain compositional functions with far fewer neurons than shallow networks.
• 81:01Even when using a universal transformer architecture, the initial preprocessing layer is modality‑specific (2‑D patches for images, spectrogram‑like representations for audio).

Key terms

• Universal function approximator — A neural network architecture capable of approximating any continuous function on a compact domain given sufficient width (or depth).
• Approximation — The existence question: does a network within a chosen architecture family represent the desired function?
• Optimization — The process of adjusting model parameters to minimize a loss function, typically using gradient‑based methods.
• Generalization — The ability of the found network to perform well on data it has not seen during training.
• Depth vs. Width — Trade‑off between stacking many layers (depth) and using many neurons per layer (width) to increase model capacity.
• ReLU — Rectified Linear Unit, an activation function defined as f(x)=max(0,x), which makes networks piecewise linear.
• Linear separator — A hyperplane that divides the input space into two half‑spaces, used by a single‑layer perceptron.
• Fractal function — A function exhibiting self‑similarity at every scale, often defined recursively.
• Epsilon (ε) — A small positive number representing the allowable approximation error.
• Multi‑layer Perceptron (MLP) — A feed‑forward neural network consisting of multiple fully‑connected layers.
• L‑infinity norm — The maximum absolute value of a function over its domain; here used as an error metric max_x |f(x)‑g(x)|.
• L1 norm (integral norm) — The integral of the absolute value of a function over its domain; here used as error ∫|f(x)‑g(x)|dx.
• Lipschitz continuity — A property of a function g for which there exists a constant L such that |g(x)‑g(y)| ≤ L·|x‑y| for all x, y.
• RMS norm — Root‑mean‑square norm of a vector: √( (1/d) Σ_i x_i² ), giving a non‑dimensional size measure.
• ReLU network — A neural network whose activation functions are rectified linear units, which introduce piecewise linearity and kinks.
• universal approximation theorem — A result stating that a sufficiently wide single‑hidden‑layer neural network can approximate any continuous function on a compact set arbitrarily well.
• hyper cube — A d‑dimensional geometric figure formed by the Cartesian product of the interval [0,1] in each coordinate direction.
• hyper cuboid — A generalized rectangle in d dimensions where each side may have a different length; a scaled version of a hyper‑cube.
• ReLU MLP — A multilayer perceptron whose hidden units use the rectified linear unit activation function σ(x)=max(0,x).
• three‑layer network — A feed‑forward network consisting of three weight matrices and two ReLU activation layers (the final layer is linear).
• Lipschitz constant — A number L such that |f(x)-f(y)| ≤ L·‖x-y‖ for all x,y in the domain; measures how quickly a function can change.
• ε (epsilon) — A small positive tolerance used to quantify the allowed approximation error.
• dimension dependence — How the resources (e.g., number of neurons) required for approximation grow as a function of the input dimension d.
• rectangle approximation — Representing a function as a sum of piecewise‑constant blocks (rectangles) over a partition of the domain.
• hyper‑rectangle — A multi‑dimensional analogue of a rectangle; the Cartesian product of intervals in each input dimension.
• indicator function — A function 𝟙_A(x) that equals 1 if x∈A and 0 otherwise, used to describe each rectangle’s support.
• L¹ error — The integral of the absolute difference between the target function and its approximation over the domain.
• two‑layer network — A neural network with one hidden layer (typically with ReLU activations) and an output layer, capable of representing piecewise‑linear functions.
• strip — A single one‑dimensional rectangle (interval) used in the construction of the piecewise approximation.
• ε‑approximation — An approximation whose maximum absolute error does not exceed ε.
• scaling constant C — A parameter multiplied to the inputs of ReLUs to increase the slope of the piecewise‑linear segments; letting C→∞ sharpens the transition.
• constant C — A scaling parameter that is taken to infinity to sharpen the piecewise‑linear transition of a ReLU.
• α_i (alpha_i) — Coefficients that weight each hyper‑rectangle in the final linear combination.
• network depth — Number of hidden layers; the construction results in a three‑layer ReLU network.
• neuron count 4d — Total number of neurons needed per hyper‑rectangle: four per dimension, multiplied by the dimension d.
• Universal Function Approximation (UFA) — The property of a model class (e.g., neural networks) to represent any continuous function on a compact domain to arbitrary accuracy given sufficient parameters.
• Overfitting — When a model fits the training data too closely, capturing noise rather than the underlying pattern, leading to poor generalization on new data.
• Stone‑Weierstrass Theorem — A classic result stating that any continuous function on a compact space can be uniformly approximated by polynomial (or more generally, algebraic) functions.
• Barron’s Theorem — A result showing that shallow (typically three‑layer) neural networks can approximate functions with bounded spectral complexity using a number of units that does not grow exponentially with dimension.
• Taylor Series — An infinite sum of polynomial terms derived from a function’s derivatives at a point, used to locally approximate smooth functions.
• Compositionality — The property of a function that can be decomposed into a hierarchy of simpler functions, enabling efficient representation by deep networks.
• Parallelization — The ability to execute many operations simultaneously, often leveraged by wide neural network layers to utilize modern GPU/TPU hardware efficiently.
• Depth separation — Theoretical results showing that certain functions can be represented compactly by deep networks but require exponentially more neurons in shallow networks.
• Piecewise linear — A function composed of multiple linear segments joined together, each valid on a sub‑domain.
• Kink — A point where the derivative of a piecewise‑linear function changes abruptly; i.e., a breakpoint between linear regions.
• Parallelism — The ability to compute many neurons or operations simultaneously, a natural advantage of wide layers.
• layer — A collection of neurons that perform a linear transformation followed by an activation function.
• width — The number of neurons (or units) in a given layer of a neural network.
• depth — The number of hidden layers stacked between the input and the output.
• composition — Applying one function to the result of another, denoted f∘g.
• upper bound — A theoretical maximum that a quantity cannot exceed.
• kinks — Points where a piecewise linear function changes slope, often arising from ReLU activations.
• MLP — Multi‑Layer Perceptron, a feedforward neural network with one or more hidden layers.
• triangle function — A simple piecewise linear function shaped like an isosceles triangle, used as a building block in the depth separation example.
• compute — Computational resources, often measured in floating‑point operations (flops), required to train or infer from a model.
• loss — A metric that quantifies the difference between a model’s predictions and the true values.
• Scaling law — Empirical relationship between model performance and training resources such as number of parameters or training steps.
• Embedding parameters — Learned vectors that map discrete inputs (e.g., tokens) to continuous space before feeding into the main model.
• Confounder — An uncontrolled variable that influences both the independent and dependent variables, potentially biasing experimental conclusions.
• Learning‑rate schedule — The predefined plan for adjusting the learning rate during training, which can influence convergence and final performance.
• Transformer — A neural network architecture based on self‑attention mechanisms that can process sequential data without recurrence.
• Pre‑processing layer — The initial part of a model that converts raw input (e.g., pixels or audio waveforms) into a format suitable for the main architecture.
• Patch representation — A technique for images where the picture is divided into small, fixed‑size squares (patches) that are linearly embedded before feeding into a transformer.
• Sequential structure — An ordering of data points where the position in the sequence carries meaning, typical for text or audio signals.
• Data‑hungry — Describing models that require large amounts of labeled data to achieve good performance.
• Model family — A group of related model architectures that share core design principles (e.g., convolutional networks, recurrent networks, transformers).
• Approximator — In machine learning, a function learned by a model that approximates the true underlying mapping from inputs to outputs.

← All MIT OpenCourseWare course notes