英文标题：
《Beating the curse of dimensionality in options pricing and optimal
  stopping》
---
作者：
David A. Goldberg and Yilun Chen
---
最新提交年份：
2018
---
英文摘要：
  The fundamental problems of pricing high-dimensional path-dependent options and optimal stopping are central to applied probability and financial engineering. Modern approaches, often relying on ADP, simulation, and/or duality, have limited rigorous guarantees, which may scale poorly and/or require previous knowledge of basis functions. A key difficulty with many approaches is that to yield stronger guarantees, they would necessitate the computation of deeply nested conditional expectations, with the depth scaling with the time horizon T.   We overcome this fundamental obstacle by providing an algorithm which can trade-off between the guaranteed quality of approximation and the level of nesting required in a principled manner, without requiring a set of good basis functions. We develop a novel pure-dual approach, inspired by a connection to network flows. This leads to a representation for the optimal value as an infinite sum for which: 1. each term is the expectation of an elegant recursively defined infimum; 2. the first k terms only require k levels of nesting; and 3. truncating at the first k terms yields an error of 1/k. This enables us to devise a simple randomized algorithm whose runtime is effectively independent of the dimension, beyond the need to simulate sample paths of the underlying process. Indeed, our algorithm is completely data-driven in that it only needs the ability to simulate the original process, and requires no prior knowledge of the underlying distribution. Our method allows one to elegantly trade-off between accuracy and runtime through a parameter epsilon controlling the associated performance guarantee, with computational and sample complexity both polynomial in T (and effectively independent of the dimension) for any fixed epsilon, in contrast to past methods typically requiring a complexity scaling exponentially in these parameters.
---
中文摘要：
高维路径相关期权定价和最优停止的基本问题是应用概率和金融工程的核心。现代方法通常依赖于ADP、模拟和/或对偶，具有有限的严格保证，这可能扩展性很差和/或需要先前的基函数知识。许多方法的一个关键困难是，为了产生更有力的保证，它们需要计算深度嵌套的条件期望，并随时间范围T进行深度缩放。我们通过提供一种算法来克服这一基本障碍，该算法可以在保证的近似质量和原则上要求的嵌套水平之间进行权衡，不需要一组好的基函数。受网络流连接的启发，我们开发了一种新的纯双重方法。这导致最优值表示为无穷和，其中：1。每个项都是一个优雅的递归定义的下确界的期望；2、前k个术语只需要k个嵌套级别；和3。在第一个k项处截断会产生1/k的误差。这使我们能够设计一个简单的随机算法，其运行时间有效地独立于维度，而不需要模拟底层进程的样本路径。事实上，我们的算法完全是数据驱动的，因为它只需要模拟原始过程的能力，并且不需要关于底层分布的先验知识。我们的方法允许通过控制相关性能保证的参数epsilon在精度和运行时间之间进行优雅的权衡，对于任何固定的epsilon，计算和样本复杂性都是T中的多项式（并且有效地独立于维数），而过去的方法通常需要在这些参数中按指数缩放复杂性。
---
分类信息：

一级分类：Mathematics        数学
二级分类：Probability        概率
分类描述：Theory and applications of probability and stochastic processes: e.g. central limit theorems, large deviations, stochastic differential equations, models from statistical mechanics, queuing theory
概率论与随机过程的理论与应用：例如中心极限定理，大偏差，随机微分方程，统计力学模型，排队论
--
一级分类：Computer Science        计算机科学
二级分类：Data Structures and Algorithms        数据结构与算法
分类描述：Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
涵盖数据结构和算法分析。大致包括ACM学科类E.1、E.2、F.2.1和F.2.2中的材料。
--
一级分类：Mathematics        数学
二级分类：Optimization and Control        优化与控制
分类描述：Operations research, linear programming, control theory, systems theory, optimal control, game theory
运筹学，线性规划，控制论，系统论，最优控制，博弈论
--
一级分类：Quantitative Finance        数量金融学
二级分类：Computational Finance        计算金融学
分类描述：Computational methods, including Monte Carlo, PDE, lattice and other numerical methods with applications to financial modeling
计算方法，包括蒙特卡罗，偏微分方程，格子和其他数值方法，并应用于金融建模
--
一级分类：Quantitative Finance        数量金融学
二级分类：Mathematical Finance        数学金融学
分类描述：Mathematical and analytical methods of finance, including stochastic, probabilistic and functional analysis, algebraic, geometric and other methods
金融的数学和分析方法，包括随机、概率和泛函分析、代数、几何和其他方法
--

---
PDF下载：
-->