Module 5 of 14 · two to three weeks
Universal approximation is an existence statement over a compact set. It says nothing about parameter count, nothing about data, nothing about optimization, and nothing about inputs outside the set. This module states the neural operator theorems exactly, proves their shared construction in a setting where every step is checkable, derives the learning theory bound, and ends with a ledger of five error terms that people routinely add together without a licence.
One sentence from the JMLR paper's introduction gets quoted more than anything else in the field: "Neural operators are the only known class of models that guarantee both discretization-invariance and universal approximation" (p.3). It is accurate, and it is usually deployed as though it settled the question of whether these models work. It does not, and the clearest evidence for that is the paper's own accounting, which is franker than most of its readers.
Here is the relevant paragraph in full, from page 51, headed "Sources of Error". The authors say they study the error of approximating an operator from within a finitely parameterized class, and that it "can be driven to zero by increasing the number of parameters". Then: "In practice there will be two other sources of approximation error: firstly from the discretization of the data; and secondly from the use of empirical risk minimization over a finite data set... However we do not study these other two sources of error in this work. Furthermore we do not study how the number of parameters in our approximation grows as the error tolerance is refined. Generally, this growth may be super-exponential." And finally: "there is a potential source of error from the optimization procedure which attempts to minimize the empirical risk: it may not achieve the global minimum. Analysis of this error in the context of operator approximation has not been undertaken."
A subtlety needs pinning down, because an earlier draft of this page got it wrong. That paragraph says discretization error is not studied, while Theorem 8 in the same paper is a theorem about discretization. Both are true, and the reconciliation is the distinction between a limit and a rate. Theorem 8 proves the qualitative statement that the discretized model converges to its own continuum limit as \(L \to \infty\). It gives no bound on the error at any finite \(L\), and no dependence on anything. So the paper proves that discretization error vanishes and does not analyse its size, which is exactly the situation Lab 01 sits in: 0.0224 at 64 points and 0.0349 at 1024, both covered by the same theorem, with no theorem distinguishing them.
The paper adds one more caveat that this module takes seriously. Twice, on page 52 and again on page 58, it notes that its approximation theory reduces neural operators to a linear method and therefore "does not capture any benefits of nonlinear approximation" (research_notes/pdf-fno-jmlr.md:508-516). The construction proved below makes that visible: you can see the finite-dimensional subspace the output is confined to.
Definition 1 (p.8). A discrete refinement of \(D \subset \mathbb R^d\) is a nested sequence \(D_1 \subset D_2 \subset \cdots \subset D\) with \(|D_L| = L\), such that for every \(\epsilon > 0\) there is an \(L(\epsilon)\) with \(D \subseteq \bigcup_{x\in D_L}\{y : \|y-x\|_2 < \epsilon\}\). In words: the points eventually get everywhere.
Definition 3. For \(G : \mathcal A \to \mathcal U\), an \(L\)-point discretization \(D_L\), a map \(\hat G : \mathbb R^{Ld}\times\mathbb R^{Lm} \to \mathcal U\) and a compact \(K \subset \mathcal A\), the discretized uniform risk is \(R_K(G,\hat G,D_L) = \sup_{a\in K}\|\hat G(D_L, a|_{D_L}) - G(a)\|_{\mathcal U}\).
Definition 4 (p.9). A parametric class \(G : \mathcal A\times\Theta \to \mathcal U\) is discretization invariant if there are maps \(\hat G_L\) such that for every \(\theta\) and every compact \(K\), \(\lim_{L\to\infty}R_K\big(G(\cdot,\theta),\hat G_L(\cdot,\cdot,\theta),D_L\big) = 0\).
Theorem 8 (p.54). Let \(D\subset\mathbb R^d\) and \(D'\subset\mathbb R^{d'}\) be domains, let \(\mathcal A,\mathcal U\) be real-valued Banach function spaces on \(D,D'\) that embed continuously in \(C(\bar D),C(\bar D')\), and let \(\sigma_1,\sigma_2,\sigma_3\in C(\mathbb R)\). Then for any \(n\), the set \(\mathrm{NO}_n(\sigma_1,\sigma_2,\sigma_3;D,D')\), viewed as maps \(\mathcal A\to\mathcal U\), is discretization invariant. The proof, in Appendix E, is Riemann sums plus uniform convergence over compact sets.
Four things in that statement deserve to be read slowly, because each one is a place where the theorem is weaker than its reputation. The parameters are fixed first and the grid refines second, so the limit contains no retraining. The convergence is to \(G(\cdot,\theta)\), the model's own continuum limit, and \(G^\dagger\) does not appear anywhere in the statement. The embedding into \(C(\bar D)\) is what makes sampling meaningful at all, which is Module 0's Fact 1 arriving as a hypothesis. And there is no rate, so Lab 01's rise from 0.022 to 0.035 at unseen grids is not a counterexample to Theorem 8. The theorem promised that \(\hat G_L\) converges to \(G(\cdot,\theta)\), and \(G(\cdot,\theta)\) was itself fitted at \(L=64\).
Assumption 9 (p.55). \(D\) is a Lipschitz domain and \(\mathcal A\) is one of: \(L^{p_1}(D)\) with \(1\le p_1<\infty\); \(W^{m_1,p_1}(D)\) with \(m_1\in\mathbb N\); or \(C(\bar D)\). Assumption 10. \(D'\) is a Lipschitz domain and \(\mathcal U\) is one of: \(L^{p_2}(D')\) with \(m_2=0\); \(W^{m_2,p_2}(D')\) with \(m_2\in\mathbb N\); or \(C^{m_2}(\bar D')\) with \(m_2\in\mathbb N_0\).
Activation classes (p.52 to 54). \(\mathcal A_m\) contains the activations for which width-unbounded networks are dense in \(C^m\) on compacta, which by Pinkus (1999) is any non-polynomial \(C^m\) function. \(\mathcal A^L_m\) adds linear boundedness: ReLU is in \(\mathcal A^L_0\), ELU in \(\mathcal A^L_1\), tanh and sigmoid in all of them. \(\mathrm{BA}\) contains the activations whose networks can approximate the identity on compacta while staying globally bounded; ReLU is in \(\mathcal A^L_0\cap\mathrm{BA}\).
Theorem 11 (p.56). Under Assumptions 9 and 10, let \(G^\dagger:\mathcal A\to\mathcal U\) be continuous with \(\sigma_1\in\mathcal A^L_0\), \(\sigma_2\in\mathcal A_0\), \(\sigma_3\in\mathcal A_{m_2}\). Then for any compact \(K\subset\mathcal A\) and any \(0<\epsilon\le1\) there exist \(N\) and \(G\in\mathrm{NO}_N\) with \(\sup_{a\in K}\|G^\dagger(a)-G(a)\|_{\mathcal U}\le\epsilon\). If in addition \(\mathcal U\) is Hilbert, \(\sigma_1\in\mathrm{BA}\), and \(\|G^\dagger(a)\|_{\mathcal U}\le M\) for all \(a\in\mathcal A\), then \(G\) can be chosen with \(\|G(a)\|_{\mathcal U}\le 4M\) for all \(a\in\mathcal A\).
Theorem 12. The same conclusion with \(\mathcal A = C^{m_1}(\bar D)\), using \(m_1\)-th order neural operators \(\mathrm{NO}^{m_1}_N\), which receive derivatives up to order \(m_1\) as extra input channels. The extra channels are not a convenience: plain kernel integration cannot learn differentiation on this input class (p.54).
Theorem 13 (p.56 to 57). Let \(D'\) be Lipschitz, \(m_2\in\mathbb N_0\), Assumption 9 hold, \(\mu\) be a probability measure on \(\mathcal A\), and \(G^\dagger:\mathcal A\to H^{m_2}(D')\) be \(\mu\)-measurable with \(G^\dagger\in L^2_\mu\). With \(\sigma_1\in\mathcal A^L_0\cap\mathrm{BA}\), \(\sigma_2\in\mathcal A_0\), \(\sigma_3\in\mathcal A_{m_2}\), for any \(0<\epsilon\le1\) there exist \(N\) and \(G\in\mathrm{NO}_N\) with \(\|G^\dagger-G\|_{L^2_\mu} \le \epsilon\). Theorem 14 (p.57) is the \(C^{m_1}\) version. The proofs follow Lanthaler et al. 2021: cut down to a large compact set by Lusin's theorem, then use the decay of \(\mu\) outside it.
Theorems 11 and 13 belong together, because the trade between them is the trade every practitioner makes. Theorem 11 is worst case: it holds for every input in \(K\), and it buys that with compactness, which is a real restriction on the input set. Theorem 13 drops compactness entirely and holds for any measure, and it pays by measuring error in \(L^2_\mu\), an average. An \(L^2_\mu\) guarantee is compatible with arbitrarily bad behaviour on any set of small measure, so Theorem 13 says nothing whatsoever about any particular input you care about. The \(4M\) clause in Theorem 11 is the only statement in the whole set that constrains the model outside \(K\), and it constrains only the norm, not the error. And no theorem here bounds \(N\).
All the theorems above run on one three-stage construction (JMLR p.55, Figure 16): encode the input into \(\mathbb R^m\), map nonlinearly into \(\mathbb R^p\), decode those \(p\) numbers as coefficients against representers of \(\mathcal U\). Proving it in general needs the machinery of Assumptions 9 and 10. Proving it for Hilbert spaces needs only Module 0, and the hour it takes pays for itself, because you can then see precisely what the general theorem does and does not deliver.
Setting. \(X,Y\) separable Hilbert spaces with orthonormal bases \((e_j),(f_j)\); \(P_m,Q_p\) the orthogonal projections onto the first \(m\) and \(p\) basis vectors; \(E_m:X\to\mathbb R^m\), \(E_mu=(\langle u,e_j\rangle)_{j\le m}\); \(D_p:\mathbb R^p\to Y\), \(D_pc=\sum_{j\le p}c_jf_j\); \(G:X\to Y\) continuous; \(K\subset X\) compact.
Claim. For every \(\epsilon>0\) there are \(m,p\) and a continuous \(\psi:\mathbb R^m\to\mathbb R^p\) with \(\sup_{u\in K}\|G(u)-D_p\psi E_mu\|_Y < \epsilon\). A finite-dimensional universal approximator can then replace \(\psi\) on the compact set \(E_m(K)\) at the cost of one more \(\epsilon\).
Step 0: a compact set that contains the truncations. The trouble with truncating is that \(P_mu\) need not lie in \(K\), so uniform continuity on \(K\) is not enough. Let \(\tilde K\) be the closure of \(K\cup\bigcup_{m\ge1}P_m(K)\). Then \(\tilde K\) is compact. To see it, check total boundedness. Given \(\epsilon>0\), Module 0's Fact 3 rescue supplies an \(M\) with \(\sup_{u\in K}\|u-P_mu\|<\epsilon/2\) for all \(m\ge M\), and compactness of \(K\) supplies a finite \(\epsilon/2\)-net \(u_1,\dots,u_n\) of \(K\). For \(m\ge M\) and any \(u\in K\), \(\|P_mu-u_i\| \le \|P_mu-u\|+\|u-u_i\| < \epsilon\) for the nearest centre, so that one net covers every \(P_m(K)\) with \(m\ge M\), and it covers \(K\). The remaining sets \(P_1(K),\dots,P_{M-1}(K)\) are finitely many continuous images of a compact set, hence compact, each with its own finite \(\epsilon\)-net. The union of all these nets is finite and \(\epsilon\)-covers the whole union, so the union is totally bounded and its closure is compact in the complete space \(X\). \(\square\)
Proof of the claim. Three steps, each allotted \(\epsilon/3\).
Step 1, input truncation. \(G\) is continuous on the compact \(\tilde K\), hence uniformly continuous there, with some modulus \(\omega\) satisfying \(\omega(\eta)\to0\). By Fact 3, choose \(m\) with \(\sup_{u\in K}\|u-P_mu\|\le\eta\) where \(\eta\) is small enough that \(\omega(\eta)<\epsilon/3\). Both \(u\) and \(P_mu\) lie in \(\tilde K\), so \(\sup_{u\in K}\|G(u)-G(P_mu)\|_Y < \epsilon/3\).
Step 2, output truncation. \(P_m(K)\) is compact, so its continuous image \(G(P_m(K))\) is compact in \(Y\). Applying Fact 3 in \(Y\), choose \(p\) with \(\sup_{v\in G(P_mK)}\|v-Q_pv\|_Y<\epsilon/3\).
Step 3, the finite map. Define \(\psi:\mathbb R^m\to\mathbb R^p\) by \(\psi(c)=\big(\langle G(\textstyle\sum_jc_je_j),f_i\rangle\big)_{i\le p}\), continuous as a composition of continuous maps. By construction \(D_p\psi E_mu = Q_pG(P_mu)\), so \[\|G(u)-D_p\psi E_mu\| \le \|G(u)-G(P_mu)\| + \|G(P_mu)-Q_pG(P_mu)\| < \tfrac{2\epsilon}{3}.\] Finally \(E_m(K)\) is compact in \(\mathbb R^m\), so by Pinkus a ReLU network \(N_\theta\) exists with \(\sup_{c\in E_mK}|\psi(c)-N_\theta(c)|<\epsilon/3\), and \(\|D_p\|=1\) because \((f_j)\) is orthonormal. The three errors add to less than \(\epsilon\). \(\square\)
Now read the proof again for what it never mentions. The size of \(N_\theta\) depends on \(m\), on \(p\), on the modulus \(\omega\) and on Pinkus's theorem, and none of those is quantified anywhere; that is the parameter-count gap the paper admits on page 51. No sample of data appears at any point, so the finite-data error is untouched. The parameter \(\theta\) is asserted to exist, and nothing says an optimizer finds it. Off \(K\) the network is entirely unconstrained. And for general Banach spaces the argument needs an approximation property in place of an orthonormal basis, which is why Assumptions 9 and 10 list specific spaces and never say "a Banach space".
Why compactness is not removable, with a counterexample. Take \(X=Y\) a separable infinite-dimensional Hilbert space, \(G\) the identity, and \(K\) the closed unit ball, which by Module 0's Fact 2 is bounded and closed but not compact. Any model of the form \(D_p\psi E_m\) has its output inside the \(p\)-dimensional subspace \(V=\mathrm{span}(f_1,\dots,f_p)\). Pick a unit vector \(u\) orthogonal to \(V\), which exists because the space is infinite-dimensional. Then for every possible output \(v\in V\), \(\|u-v\|^2 = \|u\|^2+\|v\|^2 \ge 1\). So the supremum error over the ball is at least 1 for every \(m\), every \(p\) and every \(\psi\). No \(\epsilon < 1\) is reachable, and no amount of width helps.
That counterexample is also the "linear approximation" caveat made concrete. The obstruction is that the output lives in a fixed finite-dimensional subspace, not that the map \(\psi\) is too weak, and the fixed subspace is exactly what the paper means when it says the analysis reduces the model to a linear method. It is the same obstruction as the Kolmogorov \(n\)-width bound on DeepONet's trunk in Module 4.
Existence results say a good model is in the class. Rates say how big it has to be, and this is where the interesting split appears: the general answer is catastrophic, and the answer for specific PDEs is fine.
Kovachki, Lanthaler and Mishra (arXiv 2107.07562, research_notes/web-papers.md:385-448) give the FNO version of Theorem 11 and then the rates.
| Statement | Content |
|---|---|
| Theorem 2.5 | For continuous \(G:H^s(\mathbb T^d)\to H^{s'}(\mathbb T^d)\) and compact \(K\subset H^s\), for any \(\epsilon\) there is an FNO with \(\sup_K\|G(a)-N(a)\|_{H^{s'}}\le\epsilon\). Theorem 2.15 is the same for the computable pseudo-spectral \(\Psi\)-FNO, which needs \(s>d/2\). |
| Remark 3.1, Eq. 3.1 | The lower bound. For generic continuous Lipschitz operators the worst-case width grows like \(\epsilon^{-\epsilon^{-d/s}}\), super-exponential in \(1/\epsilon\). This is the "growth may be super-exponential" the JMLR paper cites on p.51. |
| Theorems 3.3, 3.4 (Darcy) | For \(a\in H^s(\mathbb T^d)\) with \(s>d/2+k\), the pseudo-spectral error is \(\lesssim N^{-(k-1)}\), and a \(\Psi\)-FNO attains it with width \(O(N^d)\) and depth \(O(\log(N^k/\epsilon))\). With \(N\asymp\epsilon^{-1/(k-1)}\) the network size grows poly-logarithmically in \(1/\epsilon\). |
| Theorem 3.5 (Navier-Stokes) | One pseudo-spectral step has error \(\lesssim \tau N^{-k}+O(\tau^2)\); over \(T/\tau\) steps the network needs width \(O(N^dd_v)\) and depth \(O((T/\tau)\log(N^k/\epsilon))\), still sub-log-linear in \(1/\epsilon\) when \(s>d/2+k\). |
The mechanism behind all three positive results is one idea, and it explains why they are stated per-PDE. An FNO layer can differentiate exactly in Fourier space, and its nonlinearity can produce the pointwise products a pseudo-spectral scheme needs. So an FNO can imitate a numerical method, layer by layer, and inherit that method's error analysis. The rate is then a property of the PDE and the scheme, not of the architecture. Lanthaler, Mishra and Karniadakis prove the twin statement for DeepONet: generic Lipschitz maps on \(m\) sensors need networks of size roughly \(\epsilon^{-m/2}\) (Remark 3.4), yet their pendulum, elliptic, parabolic and hyperbolic examples each get an algebraic rate \(\epsilon^{-\vartheta}\) with a finite, problem-specific \(\vartheta\) (:348-363). The four exponents were not extracted into the notes and must be read from that PDF if a page needs them.
The exam question, and its answer. Why do both papers prove rates for named PDEs instead of one blanket efficiency theorem? Because the escape from the curse of dimensionality is a property of the operator, not of the network. Smoothness and structure in \(G^\dagger\) are what make a small network sufficient; the architecture only has to be expressive enough to exploit them. A rate for Darcy therefore transfers to nothing. Module 10 makes the same point empirically: Helmholtz is where published transfer results also fail (research_notes/foundation.md:103-107).
The 2024 survey by Kovachki, Lanthaler and Stuart (arXiv 2402.15715) is the current inventory of what is still open: quantitative complexity outside the linear and holomorphic operator classes, no optimization theory at all, the linear-versus-nonlinear approximation question, and random features for operators (research_notes/web-papers.md:268-300). Where answers exist they are narrow. For linear operators the sample complexity is \(N\sim\epsilon^{-(\alpha+p)/(\alpha'+\min\{p-1/2,\,s\})}\) (Theorem 5.1); for holomorphic operators the best \(n\)-term rate is \(n^{1-1/p}\) in sup norm and is dimension-independent.
Every theorem so far assumed the right parameters exist. This section is about the parameters you actually get, which come from minimizing an average over \(n\) samples.
Risks. With \(a\sim\mu\), the population risk is \(R(\theta)=\mathbb E_{a\sim\mu}\|G_\theta(a)-G^\dagger(a)\|_Y^2\) and the empirical risk is \(\hat R_n(\theta)=n^{-1}\sum_{i\le n}\|G_\theta(a_i)-G^\dagger(a_i)\|_Y^2\).
Claim (excess risk of empirical risk minimization). Suppose the optimizer returns \(\hat\theta\) with \(\hat R_n(\hat\theta)\le\inf_\theta\hat R_n(\theta)+\tau\). Then for every \(\theta^*\), \[R(\hat\theta)-R(\theta^*) \;\le\; 2\sup_\theta|R(\theta)-\hat R_n(\theta)| \;+\; \tau .\]
Proof. Write \(\Delta = \sup_\theta|R(\theta)-\hat R_n(\theta)|\). Then \(R(\hat\theta)\le\hat R_n(\hat\theta)+\Delta\le\hat R_n(\theta^*)+\tau+\Delta\le R(\theta^*)+2\Delta+\tau\), where the middle step is the optimizer's guarantee and the outer two are the definition of \(\Delta\). \(\square\)
Reading the two terms. \(\tau\) is the optimization error and nothing in this course bounds it. \(\Delta\) is the statistical term, and it needs two ingredients. The loss must be bounded on the model class and on the support of \(\mu\), which is where Theorem 11's otherwise odd \(4M\) clause earns its place. And the model class must have controlled covering numbers; for DeepONet, Lanthaler et al. Section 5 obtain \(O(n^{-1/2})\) up to logarithms (research_notes/web-papers.md:364-366). Note that the DeepONet paper's measured generalization rate on the pendulum, \(n^{-1}\), is faster than that bound and is not explained by it, which is a gap and not a contradiction.
Distribution shift, stated as a theorem rather than a worry. Take a second measure \(\nu\) that charges a set of \(\mu\)-measure zero, for instance inputs carrying a Fourier mode the training measure never excites. Two operators that agree \(\mu\)-almost everywhere have identical population risk under \(\mu\) and identical empirical risk on every \(\mu\)-sample, while differing arbitrarily under \(\nu\). Empirical risk minimization has no preference between them, because it never sees a quantity that distinguishes them. This is Module 4's invisible bump raised to the level of measures, and it is the exact formal content of the sentence "transfer is conditional on distribution shift" that Module 10 has to defend.
Five terms. They are not interchangeable, they are not all bounded, and adding them requires an inequality that says you may.
| Term | What it measures | Controlled by | Theorem that bounds it |
|---|---|---|---|
| Observation or encoding | what \(m\) samples or \(L\) grid points fail to record about the input | sensor count, grid, input regularity, covariance decay | Lanthaler Thm 3.8 (a lower bound); JMLR Thm 8 (only as \(L\to\infty\)) |
| Representation | distance from \(G^\dagger\) to the best model in the class | architecture, \(k_{\max}\), width, depth | JMLR Thms 11 to 14 (existence only); KLM Thms 3.3 to 3.5 (rates, two PDEs) |
| Finite-data estimation | \(R(\hat\theta)-R(\theta^*)\) from \(n\) samples | \(n\), covering numbers, boundedness | the ERM bound above; Lanthaler Section 5 |
| Optimization | \(\hat R_n(\hat\theta)-\inf\hat R_n\) | the training run | none; JMLR p.51 says the analysis "has not been undertaken" |
| Discretization | \(\hat G_L(\cdot,\theta)\) against \(G(\cdot,\theta)\) | \(L\), quadrature, aliasing | JMLR Thm 8, qualitative only, no rate |
The one inequality you do have. On page 12 the paper splits the total error for a fixed \(\theta\):
\[\big\|\hat G_\theta(D_L,a|_{D_L}) - G^\dagger(a)\big\|_{\mathcal U} \;\le\; \big\|\hat G_\theta(D_L,a|_{D_L}) - G_\theta(a)\big\| \;+\; \big\|G_\theta(a)-G^\dagger(a)\big\|,\]
which separates discretization from approximation (research_notes/pdf-fno-jmlr.md:348-350). Note the words "for a fixed \(\theta\)". The two terms interact through \(\theta\), because the parameter that minimizes the second term at one \(L\) is not the parameter training produces at another \(L\). Lab 01 is that interaction in one table: a model fitted at \(L=64\) and evaluated at \(L=1024\) pays a fixed-amplitude grid-scale oscillation worth about 2.2 percent of the signal, which no single row of the ledger predicts.
21-1524.pdf; summaries at research_notes/pdf-fno-jmlr.md:317-323, :465-516.:348-350, :508-516, :705-711, :725-730.research_notes/web-papers.md:385-448.:311-381.:232-307.../labs/01_burgers/spectrum_b_m16.npz.You can now state each theorem with its hypotheses, prove the construction they share, produce a counterexample when a hypothesis is dropped, and name which of five error terms any given guarantee covers. The long test is a note; the short ones check the pieces.
With the page closed, write a five-page note answering three questions. What can a neural operator represent? What can a finite dataset identify? Which guarantees survive discretization? The note must contain explicit assumptions, at least one full derivation, and at least one counterexample per question. You have reached the intended level when you can defend it aloud.