Constructive Deep ReLU Neural Network Approximation

Joost Opschoor (ETH Zürich)

May 31. 2022, 15:15 — 16:00

We propose an efficient, deterministic algorithm for constructing exponentially convergent deep neural network (DNN) approximations of multivariate, analytic maps f : [-1, 1]^K → ℝ. We address in particular networks with the rectified linear unit (ReLU) activation function. Similar results and proofs apply for many other popular activation functions. The algorithm is based on collocating f in deterministic families of grid points with small Lebesgue constants, and by a-priori (i.e., “offline”) emulation of a spectral basis with DNNs to prescribed fidelity.

Assuming availability of N function values of a possibly corrupted, numerical approximation g of f in [-1, 1]^K and a bound on ∥f -g∥_{L^∞([-1,1]^K)}, we provide an explicit, computational construction of a ReLU DNN which attains accuracy ε (depending on N and ∥f -g∥_{L^∞([-1,1]^K)}) uniformly, with respect to the inputs. For analytic maps f : [-1, 1]^K → ℝ, we prove exponential convergence of expression and generalization errors of the constructed ReLU DNNs. Specifically, for every target accuracy ε ∈ (0, 1), there exists N depending also on f such that the error of the construction algorithm with N evaluations of g as input in the norm L^∞([-1, 1]^K; ℝ) is smaller than ε up to an additive data-corruption bound ∥f - g∥_{L^∞([-1,1]^K)} multiplied with a factor growing slowly with 1∕ε and the number of non-zero DNN weights grows polylogarithmically with respect to 1∕ε. The algorithmic construction of the ReLU DNNs which will realize the approximations, is explicit and deterministic in terms of the function values of g in tensorized Clenshaw–Curtis grids in [-1, 1]^K. We illustrate the proposed methodology by a constructive algorithm for (offline) computations of posterior expectations in Bayesian PDE inversion.

Joint work with Lukas Herrmann and Christoph Schwab:

Further Information
ESI Boltzmann Lecture Hall
Associated Event:
Computational Uncertainty Quantification: Mathematical Foundations, Methodology & Data (Thematic Programme)
Clemens Heitzinger (TU Vienna)
Fabio Nobile (EPFL Lausanne)
Robert Scheichl (U Heidelberg)
Christoph Schwab (ETH Zürich)
Sara van de Geer (ETH Zürich)
Karen Willcox (U of Texas, Austin)