Function Approximation

Paul Schrimpf

2026-03-11

Introduction

Function Approximation

\[ \def\R{{\mathbb{R}}} \def\Er{{\mathrm{E}}} \def\argmin{\mathrm{arg}\min} \]

• Target: \(f_0:\R^d \to \R\)
  • Expensive to compute
• Given \(\{x_i, f_0(x_i) \}_{i=1}^n\), approximate \(f_0(x)\) by \(\tilde{f}(x)\) for \(\tilde{f} \in \mathcal{F}_k\)
  • Class of approximating function \(\mathcal{F}_k\)
  • Want \(\Vert f_0 - \tilde{f} \Vert\) to be small

Approximating Classes

• Classical:
  • Polynomials
  • Trigonometric series
  • Splines
  • Local averages / kernel regression
• Modern:
  • Radial basis functions
  • Trees
  • RKHS / Kriging / Gaussian process regression
  • Neural networks

Example: dynamic programming

• Dynamic programming: \[ V(x) = \max_a u(a,x) + \beta \Er[V(x') | x, a] \]
  • \(x\) continuous
• Value function iteration:
  • Pick grid \(x_1,..., x_n\)
  • Initial guess \(\tilde{V}_0\)
  • Maximize \(V_1(x_i) = \max_a u(a,x) + \beta \Er[\tilde{V}_0(x') | x , a]\)
  • Set \(\tilde{V}_1 \approx V_1\), repeat

Example: non parametric regression

• Observe \[ y_i = f_0(x_i) + \epsilon_i \]
• Estimate \[ \hat{f}_n \in \argmin_{f\in \mathcal{F}_k} \frac{1}{n} \sum_i (y_i - f(x_i))^2 \]
• Typically, \[ \Vert f_0 - \hat{f}_n \Vert^2 = \underbrace{\Vert f_0 - \tilde{f} \Vert^2}_{\text{approximation error}} + \underbrace{\Vert \tilde{f} - \hat{f}_n \Vert^2}_{\text{variance}} \]

I say “typically” because one has to be careful about what these norms are to get a results along these lines.

Approximation Error Bounds

• Guarantees of the form \[ \sup_{f_0 \in \mathcal{F}_0 } \min_{\hat{f} \in \mathcal{F}_k} \Vert f_0 - \hat{f} \Vert_{\mathcal{V}} \leq g(n,k) \]
  • \(\mathcal{V}\) some vector space of functions, \(\mathcal{F}_0 \subseteq \mathcal{V}\), \(\mathcal{F}_k \subseteq \mathcal{V}\)
  • Usually \(\lim_{n,k \to \infty} g(n,k) = 0\)
• Quality of approximation depends on
  • restrictions on \(\mathcal{F}_0\)
  • \(\mathcal{F}_k\) that is a good match for \(\mathcal{F}_0\)
• \(\Vert \cdot \Vert_{\mathcal{V}}\) might not be norm of interest in applications, so might also want e.g. \(\Vert \cdot \Vert_{L^q(P(x))} \leq C \Vert \cdot \Vert_{\mathcal{V}}\)

Theory

Polynomials as Universal Approximators

• Stone–Weierstrass theorem if \(f_0 \in C(X)\) for a compact set \(X \subset \R\), then \(\forall \epsilon>0\), \(\exists\) polynomial \(p\) s.t. \[ \Vert f_0 - p \Vert_\infty < \epsilon \]

Polynomials

• Let \(P_n\) be polynomials of order \(n\)
• Jackson’s theorem (Jackson (1912) and later refinements) if \(f \in C^s[-1,1]\) \[ \inf_{p \in P_n} \Vert f - p \Vert_{\infty} \leq \underbrace{\left( \frac{\pi}{2} \right)^s \prod_{j=n - s + 1}^{n+1} \frac{1}{j}}_{C(s) n^{-s}} \Vert f^{(s)} \Vert_\infty \]
  • An existence result, but does not tell how to find optimal \(p\)
  • In interpolation, achieving minimum requires careful choice of \(\{x_i\}_{i=1}^n\)

Polynomials

• Lagrange interpolation problem
• Given \(\{x_i, f(x_i)\}_{i=1}^n\), find \(p_{n-1} \in P_{n-1}\) such that \(p_{n-1}(x_i) = f(x_i)\)
• If \(f \in C^n[-1,1]\) \[ |f(x) - p_{n-1}(x) | \leq \frac{\Vert f^{(n)} \Vert_\infty}{n!}\prod_{i=1}^n(x - x_i) \]

• Choose \(x_i\) to minimize \(\Vert \prod_{i=1}^n(x - x_i) \Vert\)
  • Chebyshev polynomials interpolation

Other Series Estimators

• Belloni et al. (2015) and reference therein
• For smooth series, \(f_0:\R^d \to \R\), \(s\)-times differentiable, \[ \min_{\tilde{f} \in \mathcal{F}_k} \Vert f_0 - \tilde{f} \Vert \leq C k^{-s/d} \]
• Splines of order \(s_0\), \[ \min_{\tilde{f} \in \mathcal{F}_k} \Vert f_0 - \tilde{f} \Vert \leq C k^{-\min\{s,s_0\}/d} \]

The constant \(C\) is not really constant, but \(k^{-s/d}\) is the dominant term

Reproducing Kernel Hilbert Space

• Iske et al. (2018) chapter 8
• Especially useful in multi-dimensional settings
• Mairhuber-Curtis theorem implies \(\mathcal{F}_k\) should depend on \(\{x_i\}_{i=1}^n\) when \(d \geq 2\)

From Kernel to Hilbert Space (Moore-Aronszajn theorem)

• Kernel \(k(\cdot,\cdot): \R^d \times \R^d \to \R\) continuous, symmetric, and positive definite \[ \sum_{i=1}^n \sum_{j=1}^n c_i k(x_i,x_j) c_j \geq 0 \forall c, x \in \R^n \]
• Construct an associated inner-product space \[ \mathcal{K}^{pre} = \mathrm{span}\{ \sum_{j=1}^m c_j k(x_j, \cdot): c_j \in \R, x_j \in \R^d, m \in \mathbb{N}\} \] with inner product defined by \[ \langle k(x,\cdot), k(y,\cdot) \rangle_{\mathcal{K}} = k(x,y) \] completion of \(\mathcal{K}^{pre}\) is a Hilbert space

RKHS Facts

• \(\langle k(x,\cdot), f \rangle_{\mathcal{K}} = f\)
• \(\mathcal{K} \subset C(\R^d)\)

From Hilbert Space to Kernel

• If \(\mathcal{H}\) is a Hilbert space and \(f \to f(x)\) is bounded for all \(x\), then \(\mathcal{H}\) is an RKHS

Interpolation in RKHS

• Given \(\{x_i, f(x_i)\}_{i=1}^n\), there is unique \(\tilde{f} \in S_X \equiv \{ \sum_{i=1}^n c_i k(x_i, \cdot) \}\) such that \(\tilde{f}(x_i) = f(x_i)\)

• \(\tilde{f}\) solves \[ \min_{g \in \mathcal{K}} \Vert g \Vert_{\mathcal{K}} \, s.t. \, g(x_i) = f(x_i) \text{ for } i=1,...,n \]

Mercer’s theorem and feature maps

• Given another Hilbert space \(\mathcal{W}\), \(\Phi: \R^d \to \mathcal{W}\) is a feature map for \(k\) if \[ k(x,y) = \langle \Phi(x), \Phi(y) \rangle_\mathcal{W} \]
  • E.g. \(\mathcal{W} = \mathcal{K}\) and \(\Phi(x) = k(x,\cdot)\)
• Given measure \(\mu\), define \(T: L^2(\mu) \to L^2(\mu)\) by \[ T(f)(x) = \int k(x,y) f(y) d\mu(y) \]

Mercer’s theorem and feature maps

• Mercer’s theorem gives existence of Eigen decomposition, \[ T(f)(x) = \sum_{i=1}^\infty \lambda_i \phi_i(x) \langle \bar{\phi_i}, f \rangle_{L^2(\mu)} \] and \[ k(x,y) = \sum \lambda_i \phi_i(x) \bar{\phi_i}(y) \]
• Feature map \(k(x,y) = \langle (\sqrt{\lambda_i} \phi_i(x))_{i=1}^\infty, (\sqrt{\lambda_i} \phi_i(y))_{i=1}^\infty \rangle_{\ell^2}\)
• Link between inner product and norm in \(\mathcal{K}\) and in \(L^2(\mu)\)

RKHS as Universal Approximator

• Micchelli, Xu, and Zhang (2006) or summary by Zhang (2018)
• Given \(f \in C(Z)\), \(Z \subset \R^d\) and compact, can elements of \(\mathcal{K}\) approximate \(f\) in \(\Vert\cdot\Vert_\infty\)?
• Let \(K(Z) = \overline{\mathrm{span}}\{k(\cdot,y): y \in Z\} \subseteq C(Z)\)
• Let \(\Phi\) be feature map for \(k\) associated with \(\mu\) with \(supp(\mu) = Z\)
• Dual space of \(C(Z)\) is set of Borel measures on \(Z\), \(B(Z)\) with \[ \mu(f) = \int_Z f d\mu \]

RKHS as Universal Approximator

• Map \(B(Z)\) into \(\mathcal{K}^* = \mathcal{K}\) by \[ \langle U(\mu), h \rangle_{\mathcal{K}} = \langle \int_Z \Phi(x)(\cdot) d\mu(x), h \rangle_{\mathcal{K}} = \int_Z \langle \Phi(x), h \rangle_{\mathcal{K}} d\mu(x) \]
• \(U\) is bounded
• \(K(Z)^\perp = \mathcal{N}(U)\), i.e. universal approximation iff \(\mathcal{N}(U) = \{0\}\).
  • iff \(\overline{\mathrm{span}}\{ \langle \Phi(x), \gamma_i \rangle_\mathcal{K} : \gamma_i \text{ basis for } \mathcal{K} \} = C(Z)\)
• Radial kernels are universal approximators \[ k(x,y) = \int e^{-t\Vert x-y\Vert^2} d\nu(t) \]

RKHS approximation rate

• Bach (2024) chapter 7
• If \(k\) is translation invariant and \(f\) is \(s\) times differentiable, \[ \inf_{f \in \mathcal{K}} \Vert f - f_0 \Vert_{L^2(\mu)} + \lambda \Vert f \Vert_{\mathcal{K}} \approx O(\lambda^{s/r_k}) \] where \(r_k\) depends on \(k\) and need \(r_k > d/2 > s\) (if \(s \geq r_k\), then \(f_0 \in \mathcal{K}\) and can do better)
• If sample \(x_i \sim \mu\) and interpolate \[ \hat{f} = \argmin_{f \in \mathcal{K}} \frac{1}{n}\sum_{i=1}^n (f_0(x_i) - f(x_i) )^2 + \lambda \Vert f \Vert_{\mathcal{K}} \] then \(\Vert \hat{f} - f_0 \Vert_{L^2(\mu)} \approx O(n^{-s/r_k})\)
  • if \(f_0 \in \mathcal{K}\), \(O(n^{-1/2})\)

Neural Networks

• Bach (2024)

Example

Target Function

using Symbolics

flowprofits_expr = begin
    @variables m
    @variables k, l, ω, pm, py
    production(k,l,m) = k^(2//10)*l^(4//10)*m^(3//10)
    #ρ = 5
    #rts = 9//10
    #ces(k,l,m) = (k^ρ + l^ρ + m^ρ)^(rts/ρ)
    profits(k,l,m,ω,pm,py) = py*exp(ω)*p
    mstar = symbolic_solve(Symbolics.derivative(profits,m) ~ 0, m)
    build_function(profits(k,l,mstar,ω,pm,py), k,l,ω,pm,py)
end

Target Function

import NaNMath
function flowprofits_f(k, l, ω, pm, py)
    begin
        (+)((*)((*)(-1, pm), (NaNMath.pow)((/)((*)((*)((*)((*)(3//10, (NaNMath.pow)(k, 1//5)), (NaNMath.pow)(l, 2//5)), py), (exp)(ω)), pm), 10//7)), (*)((*)((*)((*)((NaNMath.pow)(k, 1//5), (NaNMath.pow)(l, 2//5)), py), (NaNMath.pow)((/)((*)((*)((*)((*)(3//10, (NaNMath.pow)(k, 1//5)), (NaNMath.pow)(l, 2//5)), py), (exp)(ω)), pm), 3//7)), (exp)(ω)))
    end
end

flowprofits_f(1.0, 2.0, 0.0, 1.0, 1.0)

0.6209037596469107

Fit on Random Inputs

using Surrogates, ForwardDiff
nfit = 100
ntest = 3*30
# x = [k, l, ω]
lb = [0.01, 0.01] #, -3.0]
ub = [10.0, 10.0] #, 3.0]
pm = 1.0
py = 1.0
ω = 0.0
f0 = x->flowprofits_f(x..., 0.0, 1., 1.)
x = Surrogates.sample(nfit, lb, ub, SobolSample())
xtest = Surrogates.sample(ntest, lb, ub, HaltonSample())
y = f0.(x)
ytest = f0.(xtest);

Radial Basis

using LinearAlgebra
radial = RadialBasis(x,y,lb,ub, scale_factor=1.0)
function errorreport(model, xtest, f0; grad=true)
    ntest = length(xtest)
    println("L2 error ≈ $(norm(model.(xtest) - f0.(xtest))/sqrt(ntest))")
    if grad
        println("Grad L2 error ≈ $(Float64(norm([ForwardDiff.gradient(x->(model(Tuple(x)) - f0(x)), [xi...]) for xi in xtest])/sqrt(ntest)))")
    end
end
errorreport(radial, xtest, f0)

L2 error ≈ 0.04165104832851626
Grad L2 error ≈ 0.18073829719828227

Radial Basis

using Plots
function plotapprox(f0, fapp, lb, ub, xfit; np=25)
    xp = range(lb[1],ub[1], np)
    yp = range(lb[2],ub[2], np)
    p1 = surface(xp, yp, (x, y) -> f0([x y]), title="f0")
    #scatter!([x[1] for x in xfit], [x[2] for x in xfit], f0.(xfit), marker_z = f0.(xfit), title="f0")
    p2 = surface(xp, yp, (x, y) -> fapp([x y]), title="Approximation")
    #scatter!([x[1] for x in xfit], [x[2] for x in xfit], fapp.(xfit), marker_z = fapp.(xfit))
    err = surface(xp,yp,(x,y)->(fapp([x y]) - f0([x y])), title="Error")
    scatter!([x[1] for x in xfit], [x[2] for x in xfit], fapp.(xfit) - f0.(xfit), marker_z = fapp.(xfit)-f0.(xfit))
    return(p1,p2, err)
end
plot(plotapprox(f0,radial,lb,ub,x)...)

Polynomial

using PolyChaos
degree = 6
poly = PolynomialChaosSurrogate(x,y, lb, ub, orthopolys=orthopolys = MultiOrthoPoly([GaussOrthoPoly(degree) for j in 1:length(lb)], degree))
errorreport(poly, xtest, f0)
plot(plotapprox(f0,poly,lb,ub,x)...)

L2 error ≈ 0.011665545466997445
Grad L2 error ≈ 0.06956349932360786

RKHS (Kriging)

kriging = Kriging(x,y, lb, ub)
errorreport(kriging, xtest, f0)
plot(plotapprox(f0,kriging,lb,ub,x)...)

L2 error ≈ 0.008356664875980503
Grad L2 error ≈ 0.05927530111376265

RKHS (AbstractGP)

using SurrogatesAbstractGPs

GP = SurrogatesAbstractGPs.GP(0.0, SurrogatesAbstractGPs.KernelFunctions.ScaledKernel(
  SurrogatesAbstractGPs.KernelFunctions.SqExponentialKernel(), 0.1
))
gp = Surrogates.AbstractGPSurrogate(x,y, gp=GP, Σy=0.0)
errorreport(gp, xtest, f0)
plot(plotapprox(f0,gp,lb,ub,x)...)

L2 error ≈ 0.050650337373694405
Grad L2 error ≈ 0.22084593281506665

Other Packages

• There are many!

NaturalNeighbours

• NaturalNeighbours.jl

import NaturalNeighbours as NN
itp = NN.interpolate(x,y)
piecewiselinear=x->itp(x...;method=NN.Triangle())
errorreport(piecewiselinear, xtest, f0; grad=false)
plot(plotapprox(piecewiselinear,gp,lb,ub,x)...)

L2 error ≈ 0.03822210306195987

References

Bach, Francis. 2024. Learning Theory from First Principles. MIT Press. https://www.di.ens.fr/~fbach/ltfp_book.pdf.

Belloni, Alexandre, Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. 2015. “Some New Asymptotic Theory for Least Squares Series: Pointwise and Uniform Results.” Journal of Econometrics 186 (2): 345–66. https://doi.org/https://doi.org/10.1016/j.jeconom.2015.02.014.

Iske, Armin et al. 2018. Approximation Theory and Algorithms for Data Analysis. Springer. https://link.springer.com/book/10.1007/978-3-030-05228-7.

Jackson, Dunham. 1912. “On Approximation by Trigonometric Sums and Polynomials.” Transactions of the American Mathematical Society 13 (4): 491–515. http://www.jstor.org/stable/1988583.

Micchelli, Charles A., Yuesheng Xu, and Haizhang Zhang. 2006. “Universal Kernels.” Journal of Machine Learning Research 7 (95): 2651–67. http://jmlr.org/papers/v7/micchelli06a.html.

Zhang, Thomas. 2018. “Reproducing Kernel Hilbert Spaces.” https://thomaszh3.github.io/writeups/RKHS.pdf.