MIT 6.7960 — Lecture 3

Approximation Theory

These are the important questions we will be answering during this lecture.

Approximation. What is the best $\hat{\mathcal{R}}(\theta^*)$ (empirical risk) we can achieve with our model?
Optimization. How good is our learning algorithm at minimizing $\hat{\mathcal{R}}(\theta)$ (empirical risk)?
Generalization. How different is $\hat{\mathcal{R}}(\theta)$ (empirical risk) from $\mathcal{R}(\theta)$ (true risk)?

… and I realize that I have no reason to be here, because this lecture covers the exact same content as:

The “Neural Network Universal Approximation” section of Lecture 12 of 6.790.
The “Neural Network Depth” section of Lecture 13 of 6.790.
The “Estimation Error Bounding” section of Lecture 10 of 6.790.

This class offers a little more detail on the “Universal Approximation” theorem; it provides a (very non-rigorous) proof sketch of:

Theorem. (Universal Approximation) Suppose $g \colon [0, 1]^d \to \mathbb{R}$ is an $L$ -Lipschitz function. Then for any $\epsilon > 0$ , there exists a 3-layer ReLU network $f$ with $O((L/\epsilon)^d)$ units such that:

\int_{[0, 1]^d} |f(\mathbf{x}) - g(\mathbf{x})| \, \mathrm{d}\mathbf{x} \leq 2 \epsilon.

Actually, no, turns out 6.790 said this already, too. I'm leaving.