Source-linked AI summary
Analysis of the Generalization Error: Empirical Risk Minimization over Deep Artificial Neural Networks Overcomes the Curse of Dimensionality in the Numerical Approximation of Black-Scholes Partial Differential Equations
Julius Berner, Philipp Grohs, Arnulf Jentzen
TL;DR
The paper asks whether ERM over deep neural networks can approximate high-dimensional Kolmogorov-equation solutions without the curse of dimensionality. It combines neural-network approximation with statistical-learning generalization bounds and proves curse-free guarantees under affine coefficients and suitable initial values. The analysis establishes polynomial scaling in dimension and inverse accuracy for both hypothesis-class size and training samples, while leaving ERM optimization cost outside its scope.
Problem
Provably approximating Kolmogorov-equation solutions on full hypercubes in high dimensions remained out of reach, while generic deep-learning architectures lack guaranteed unseen-data performance.
Method
The paper reformulates terminal-solution approximation as a statistical learning problem and combines clipped ReLU approximation with covering-number-based generalization analysis.
Results
The analysis proves that ERM achieves the desired approximation with hypothesis-class size and training-sample count scaling polynomially in d and ε^-1 under the stated conditions.
Takeaways & Limitations
ERM over deep neural-network hypothesis classes overcomes the curse of dimensionality for linear Kolmogorov equations with affine coefficients and suitable initial values.
Takeaways & Limitations
The analysis does not consider the computational cost of solving the nonsmooth, nonconvex ERM problem.
Abstract
from arXiv · showhide
The development of new classification and regression algorithms based on empirical risk minimization (ERM) over deep neural network hypothesis classes, coined deep learning, revolutionized the area of artificial intelligence, machine learning, and data analysis. In particular, these methods have been applied to the numerical solution of high-dimensional partial differential equations with great success. Recent simulations indicate that deep learning-based algorithms are capable of overcoming the curse of dimensionality for the numerical solution of Kolmogorov equations, which are widely used in models from engineering, finance, and the natural sciences. The present paper considers under which conditions ERM over a deep neural network hypothesis class approximates the solution of a $d$-dimensional Kolmogorov equation with affine drift and diffusion coefficients and typical initial values arising from problems in computational finance up to error $\varepsilon$. We establish that, with high probability over draws of training samples, such an approximation can be achieved with both the size of the hypothesis class and the number of training samples scaling only polynomially in $d$ and $\varepsilon^{-1}$. It can be concluded that ERM over deep neural network hypothesis classes overcomes the curse of dimensionality for the numerical solution of linear Kolmogorov equations with affine coefficients.
1. Introduction.
The paper addresses high-dimensional approximation of Kolmogorov-equation solutions on full hypercubes, where conventional discretization methods suffer from exponential complexity. It analyzes deep-learning ERM and proves curse-free approximation under affine coefficients and suitable initial values.
- 1. Introduction: Standard PDE discretization methods have computational complexity that grows exponentially with dimension.Monte Carlo methods avoid this curse for evaluating the solution at a single point, but not generally on a full hypercube.
- 1.1. Problem statement: Provably approximating Kolmogorov-equation solutions on full hypercubes in high dimensions had remained out of range.The paper specifically considers approximation of Fd(T, ·) on [u, v]^d, including dimensions much larger than 100.
- 1.3. Kolmogorov equations as learning problem: The paper reformulates numerical approximation on [u, v]^d as a statistical learning problem and applies ERM over deep neural-network hypothesis classes.The target solution is connected to the risk minimizer through the Feynman–Kac representation, while training uses sampled data and empirical risk minimization.
- 1.4. Contribution: Affine drift and diffusion coefficients preserve neural-network approximability of relevant initial values during Kolmogorov evolution.This includes the Black–Scholes equation and supports ReLU-network approximation of the terminal solution without the curse of dimensionality.
- 1.4. Contribution: The proof combines neural-network approximation, Feynman–Kac-based Monte Carlo construction, covering-number estimates, and generalization bounds.The analysis also derives parameter-magnitude bounds and uses Lipschitz properties of the network-realization operator.
- 1.4. Contribution: The joint analysis of approximation and generalization errors establishes that the required network size and training-sample count avoid exponential dependence on dimension.The result applies to relevant options including basket call, basket put, call-on-max, and call-on-min problems.
2. Results in statistical learning theory.
This section develops a statistical-learning framework for ERM over bounded, clipped ReLU-network classes and derives generalization bounds using covering numbers. The results connect approximation quality, network complexity, and required training samples, with polynomial dimension dependence when approximation is polynomial.
- Statistical learning problem: The statistical-learning setup uses bounded inputs and labels, i.i.d. samples, risk minimization, and compact neural-network hypothesis classes.Inputs lie in [u, v]^d, labels in [−D, D], and the empirical risk is minimized over a compact class.
- Statistical learning problem: The bias-variance decomposition separates the error into approximation error from the hypothesis class and generalization error from finite samples.The regression function minimizes the population risk, while the best hypothesis-class approximation contributes the bias term.
- Generalization bounds: Covering numbers control generalization by measuring how many radius-r balls are needed to cover a compact hypothesis class.Uniform boundedness and risk Lipschitz continuity enable covering-number estimates combined with Hoeffding’s inequality and a union bound.
- Generalization bounds: Theorem 2.4 gives a probabilistic generalization-error bound for compact uniformly bounded hypothesis classes.The bound applies to ERM over H under the stated statistical-learning and covering-number settings.
- Neural-network hypothesis classes: Clipped ReLU networks provide uniformly bounded hypothesis classes suitable for ERM, while clipping can itself be represented by a small neural network.The clipping construction ensures the boundedness required by Theorem 2.4 without leaving conventional neural-network classes.
- Neural-network hypothesis classes: Combining approximation and covering-number results shows that approximation without the curse of dimensionality implies generalization without the curse of dimensionality.The required training-sample count inherits polynomial dependence when suitable network approximations and parameter bounds exist.
3. Applications for the numerical approximation of high-dimensional PDEs.
This section reformulates high-dimensional Kolmogorov-equation approximation as a learning problem and establishes neural-network approximation and ERM generalization results under affine coefficients. The resulting hypothesis-class and sample-complexity bounds are free of the curse of dimensionality.
- Assumptions: The setting assumes affine drift and diffusion coefficients, bounded initial values, and neural-network approximability of the initial-value family.The solution is taken as the unique, at most polynomially growing viscosity solution.
- Kolmogorov equation as learning problem: The terminal solution value F_d(T, ·) can be restated as a statistical learning problem using uniformly distributed inputs and labels generated from the SDE solution.The reformulation is formalized in Lemma 3.2.
- Neural-network approximation: The terminal solution can be approximated by hypothesis classes consisting of clipped ReLU networks.The construction uses a specified architecture and bounded parameter magnitudes.
- Proof strategy: Affine coefficients permit a representation S_x^d(T) = Mx + N, supporting Monte Carlo-based approximation arguments for the terminal solution.The proof samples independent copies of (M, N) and analyzes the resulting mean squared error through bias and variance.
- Generalization and ERM: Theorem 3.4 and Corollary 3.5 establish neural-network generalization and ERM results whose relevant complexity and sample requirements do not suffer from the curse of dimensionality.The corollary states the result in compact polynomial form.
- Application: The theory yields the introductory pricing result for high-dimensional European put options.The paper derives this application after establishing the preceding approximation and generalization results.
Appendix A. Proofs.
Appendix A contains proofs and additional material omitted from the main text.
- Appendix A provides proofs and supplementary material that are not included in the main text.
A.1. Measurability of the empirical target function.
This appendix section establishes measurability of the empirical regression function, enabling its use in generalization-error bounds.
- The empirical regression function must be measurable to support bounding the generalization error.
- Compactness of the hypothesis class and continuity of empirical risk allow a measurable selector of empirical-risk minimizers.The Measurable Maximum Theorem supplies the selector.
- B(Z) denotes the Borel σ-algebra of a topological space Z.
- The risk functional is continuous and measurable, so compositions of measurable functions establish the required measurability claims.
A.2. Bias-variance decomposition.
The appendix analyzes approximation through a bias-variance decomposition and connects the stochastic representation to the target L2 error.
- The argument uses the tower property of conditional expectation together with the preceding decomposition to establish the stated estimates.
- The mean squared error is decomposed into the sum of squared bias and variance.
- Applying the relevant estimate with the empirical-risk minimizer completes the lemma's proof.
A.3. Bound on the generalization error.
The section bounds generalization error by covering the hypothesis class and controlling deviations of empirical quantities from their expectations. The proof applies probability inequalities to establish the theorem.
- A.3. Bound on the generalization error.: The argument combines assumptions, monotonicity, subadditivity, measurability, and the complement rule to prove the theorem.The final step plugs in the definition of N.
- A.3. Bound on the generalization error.: The proof covers the hypothesis class with balls centered at selected functions f1, f2, …, fN.The covering construction ensures that every function belongs to one of the balls.
- A.3. Bound on the generalization error.: For fixed f ∈H, the proof defines random variables Ei and applies Hoeffding’s inequality to them.The variables are used to control deviations for sampled data.
A.4. Clipped neural networks are standard neural networks.
The section shows that clipped neural network hypothesis classes can be represented within standard neural network classes. This is established using a neural-network representation of the clipping function and composition.
- A.4. Clipped neural networks are standard neural networks.: “Clipped” neural network hypothesis classes are subsets of corresponding “non-clipped” classes.This is the section’s stated stronger structural claim.
- A.4. Clipped neural networks are standard neural networks.: Lemma A.2 represents the clipping function as a neural network under Setting 2.5.The proof uses a case distinction to establish the representation.
- A.4. Clipped neural networks are standard neural networks.: Corollary A.3 embeds clipped networks into standard networks by extending the architecture with layers of widths 2, 2, and 1.The representation uses composition without changing parameter magnitudes.
A.5. Lipschitz continuity of the realization map.
The section establishes Lipschitz control for the realization map by comparing partial network parametrizations and their errors. The resulting bound directly implies Theorem 2.6.
- A.5. Lipschitz continuity of the realization map.: The resulting estimate directly implies Theorem 2.6.The passage states that the theorem follows from the established bound.
- A.5. Lipschitz continuity of the realization map.: The proof compares realizations associated with parameters θ and η by setting r := ∥θ −η∥∞.It introduces partial parametrizations, realization functions, and partial errors across network layers.
- A.5. Lipschitz continuity of the realization map.: Induction bounds intermediate magnitudes using ms ≤R∥a∥∞ms−1 + R.The bound is established for every layer index s.
A.6. Covering numbers of neural network hypothesis classes.
The section constructs a finite parameter cover for the neural network hypothesis class. Parameters are selected so every admissible parameter lies within distance ∆ of one selected center.
- A.6. Covering numbers of neural network hypothesis classes.: A finite collection of parameters θ1, θ2, …, θN covers Pa,R within ∞-norm distance ∆.The construction then invokes Theorem 2.6 and the nonexpansiveness of clipD.
A.7. Kolmogorov equation as learning problem.
The section proves a lemma using the Feynman–Kac formula for viscosity solutions of Kolmogorov equations. Mollification and dominated convergence establish the required claim for measurable sets.
- The proof starts from the Feynman–Kac formula for viscosity solutions of Kolmogorov equations.
- For a measurable set A, the indicator function is mollified by convolution with a smooth family gε.
- The proof constructs a continuous bounded path functional from the mollified indicator evaluated at the initial point and a Gaussian density at the terminal point.
- Almost-everywhere recovery of the indicator and dominated convergence complete the argument as ε tends to zero.
A.8. Neural network approximation result for solutions of Kolmogorov equations.
The section develops auxiliary representations for affine-coefficient SDE solutions and neural-network compositions, then combines them in the proof of the main approximation theorem. The construction uses random affine representations and a neural network whose parameters are controlled by the auxiliary lemmas.
- Representation of SDE solutions: An affine-coefficient SDE solution is represented using random matrix and vector variables.
- Representation of SDE solutions: The representation lemma establishes moment estimates for the random affine representation and its associated quantities.
- Neural-network composition: Averages of neural networks composed with different affine functions can be represented by a single neural network with bounded parameter count and size.
- Neural-network composition: The composition lemma constructs network parameters by combining copies of the original network within a larger parametrization.
- Proof of Theorem 3.3: Theorem 3.3 fixes the dimension and target error, samples independent random affine representations, and defines the resulting neural-network construction.
- Proof of Theorem 3.3: The proof uses an expectation bound to select a realization satisfying the required estimate, then applies the composition lemma to complete the theorem.