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: https://doi.org/10.1007/s10915-021-01718-2

Further Information
Venue:
ESI Boltzmann Lecture Hall
Associated Event:
Computational Uncertainty Quantification: Mathematical Foundations, Methodology & Data (Thematic Programme)
Organizer(s):
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)