Deep neural network expressivity for optimal stopping problems
- URL: http://arxiv.org/abs/2210.10443v1
- Date: Wed, 19 Oct 2022 10:22:35 GMT
- Title: Deep neural network expressivity for optimal stopping problems
- Authors: Lukas Gonon
- Abstract summary: An optimal stopping problem can be approximated with error at most $varepsilon$ by a deep ReLU neural network of size at most $kappa dmathfrakq varepsilon-mathfrakr$.
This proves that deep neural networks do not suffer from the curse of dimensionality when employed to solve optimal stopping problems.
- Score: 2.741266294612776
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This article studies deep neural network expression rates for optimal
stopping problems of discrete-time Markov processes on high-dimensional state
spaces. A general framework is established in which the value function and
continuation value of an optimal stopping problem can be approximated with
error at most $\varepsilon$ by a deep ReLU neural network of size at most
$\kappa d^{\mathfrak{q}} \varepsilon^{-\mathfrak{r}}$. The constants
$\kappa,\mathfrak{q},\mathfrak{r} \geq 0$ do not depend on the dimension $d$ of
the state space or the approximation accuracy $\varepsilon$. This proves that
deep neural networks do not suffer from the curse of dimensionality when
employed to solve optimal stopping problems. The framework covers, for example,
exponential L\'evy models, discrete diffusion processes and their running
minima and maxima. These results mathematically justify the use of deep neural
networks for numerically solving optimal stopping problems and pricing American
options in high dimensions.
Related papers
- Sample Complexity of Neural Policy Mirror Descent for Policy
Optimization on Low-Dimensional Manifolds [75.51968172401394]
We study the sample complexity of the neural policy mirror descent (NPMD) algorithm with deep convolutional neural networks (CNN)
In each iteration of NPMD, both the value function and the policy can be well approximated by CNNs.
We show that NPMD can leverage the low-dimensional structure of state space to escape from the curse of dimensionality.
arXiv Detail & Related papers (2023-09-25T07:31:22Z) - Sharp Lower Bounds on Interpolation by Deep ReLU Neural Networks at
Irregularly Spaced Data [2.7195102129095003]
Deep ReLU neural networks can interpolate values at $N$ datapoints which are separated by a distance $delta$.
We show that $Omega(N)$ parameters are required in the regime where $delta$ is exponentially small in $N$.
As an application we give a lower bound on the approximation rates that deep ReLU neural networks can achieve for Sobolev spaces at the embedding endpoint.
arXiv Detail & Related papers (2023-02-02T02:46:20Z) - When Expressivity Meets Trainability: Fewer than $n$ Neurons Can Work [59.29606307518154]
We show that as long as the width $m geq 2n/d$ (where $d$ is the input dimension), its expressivity is strong, i.e., there exists at least one global minimizer with zero training loss.
We also consider a constrained optimization formulation where the feasible region is the nice local region, and prove that every KKT point is a nearly global minimizer.
arXiv Detail & Related papers (2022-10-21T14:41:26Z) - Understanding Deep Neural Function Approximation in Reinforcement
Learning via $\epsilon$-Greedy Exploration [53.90873926758026]
This paper provides a theoretical study of deep neural function approximation in reinforcement learning (RL)
We focus on the value based algorithm with the $epsilon$-greedy exploration via deep (and two-layer) neural networks endowed by Besov (and Barron) function spaces.
Our analysis reformulates the temporal difference error in an $L2(mathrmdmu)$-integrable space over a certain averaged measure $mu$, and transforms it to a generalization problem under the non-iid setting.
arXiv Detail & Related papers (2022-09-15T15:42:47Z) - Solving parametric partial differential equations with deep rectified
quadratic unit neural networks [38.16617079681564]
In this study, we investigate the expressive power of deep rectified quadratic unit (ReQU) neural networks for approximating the solution maps of parametric PDEs.
We derive an upper bound $mathcalOleft(d3log_2qlog_2 (1/ epsilon) right)$ on the size of the deep ReQU neural network required to achieve accuracy.
arXiv Detail & Related papers (2022-03-14T10:15:29Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
We consider the problem of quantizing a linear model learned from measurements.
We derive an information-theoretic lower bound for the minimax risk under this setting.
We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
arXiv Detail & Related papers (2022-02-23T02:39:04Z) - {\epsilon}-weakened Robustness of Deep Neural Networks [9.183179469739194]
This paper introduces a notation of $varepsilon$-weakened robustness for analyzing the reliability and stability of deep neural networks (DNNs)
We prove that the $varepsilon$-weakened robustness decision problem is PP-complete and give a statistical decision algorithm with user-controllable error bound.
We also show its potential application in analyzing quality issues.
arXiv Detail & Related papers (2021-10-29T13:27:01Z) - The Separation Capacity of Random Neural Networks [78.25060223808936]
We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability.
We quantify the relevant structure of the data in terms of a novel notion of mutual complexity.
arXiv Detail & Related papers (2021-07-31T10:25:26Z) - Deep neural network approximation of analytic functions [91.3755431537592]
entropy bound for the spaces of neural networks with piecewise linear activation functions.
We derive an oracle inequality for the expected error of the considered penalized deep neural network estimators.
arXiv Detail & Related papers (2021-04-05T18:02:04Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.