倒向随机微分方程的多级逼近

在第3.3节中，误差分析使我们能够校准多级算法的数值参数，并将其复杂性与替代算法进行比较。3.1初步介绍本节介绍了普通最小二乘回归（OLS）来近似多级方案中的条件期望算子。我们将在通用但通用的定义3.1 forOLS的基础上，简洁地表达我们的算法。OLS承认一个基本理论（见命题3.11），该理论支持第3.3节中的一般（无分布）但严密的误差分析。2018年7月3日14:28 12定义3.1（普通最小二乘回归）。为了我，我≥ 1和概率空间（~Ohm,~F，~P）和（Rl，B（Rl），ν），设为a~FB（Rl）-可测的Rl值函数，使得S（ω，·）在L（B（Rl），ν）中表示＠P-a.e.ω∈~Ohm, K是L（B（Rl），ν）的线性子空间，由一些（有限或可数）确定的Rl值函数集{pk（.）：K≥ 1}. 在（闭包Kof）空间K中，S关于ν的最小二乘近似是（~P×ν-a.e.）唯一的，~FB（Rl）-可测函数？（ω，·）：=arg infφ∈KZ |φ（x）-S（ω，x）|ν（dx）=arg minφ∈\'KZ|φ（x）-S（ω，x）|ν（dx）。（18） 我们这么说是吗？求解OLS（S，K，ν）。另一方面，假设νM=M-1PMm=1δX（m）是（Rl，B（Rl））上的离散概率测度，其中δxis是X和X（1）上的狄拉克测度，X（M）：~Ohm → 这是i.i.d.随机变量。为了一个FB（Rl）-可测的Rl值函数sω、 X（m）（ω）< ∞ 对于anym和∧P-a.e.ω∈~Ohm, 空间K中S关于v的最小二乘逼近（~P-a.e.）唯一，~FB（Rl）-可测量的功能？（ω，·）：=arg infφ∈KMMXm=1 |φX（m）（ω）- sω、 X（m）（ω）|.

（19） 我们这么说是吗？求解OLS（S，K，νM）。为了解释要解决的计算障碍，让我们首先使用定义3.1，将（AX）（ii）中给出的马尔科夫函数表示为涉及OLS的算法。算法1。通过设置y（0）（·）：=Φ（·），y（0）（·）：=E[Φ（X（0））]和Tz（0）（·）：=E[重量Φ（X（0））]进行初始化。递归地求k≥ 1，假设（y（k）-1） （·），z（k）-1） （·））已经计算过，设置y（k）k（·）=Φ（·），对于任何i∈ {0，…，2k-1} ，设kl为空间L（B（Rd），Po（X（k）i）-1.（Rl）>）代表l∈ andy（k）i（·）解OLS（S（k）Y，i（x，\'x，w），k，νk）for（k）Y，i（x，\'x，w）：=Φ（xk）-主键-1.-1j=α（i）+1z（k）-1） j（\'xj）（w2j+w2j+1），z（k）i（·）为（k）z，i（x，\'x，w）求解OLS（S（k）z，i（x，\'x，w），Kq，νk）：=wi（k） 我S（k）Y，i（x，\'x，w）- y（k）i（xi）,（20） 对于x=（x，…，xk）∈ R（2k+1）×d，\'x=（\'x，…，\'xk）-1) ∈ R（2k）-1+1）×d，w=（w，…，wk-1) ∈ Rk×q，和作为（X（k）定律的νkb，X（k）k，X（k）-1), . . . , X（k）-1） k-1.W（k），W（k）k-1).定义的直觉3.1。在上面的算法1中，我们使用的是关于（理论）定律的定义3.1，而不是经验度量（如算法2）。这里，l=（2k+1）×d+2k×q和l=1（分别为q）。函数S（·）由S（k）Y，i（·）（分别为S（k）Z，i（·））给出，这是确定性的，因此不需要概率空间（~Ohm,这里。最后，度量ν是马尔可夫链X（k）的伸缩律和布朗增量W（k），即ν=νk。这种形式的算法1实际上是不可实现的，但说明了两个计算问题，2018年7月3日14:28 13我们将用下面第3.2节中的经验最小二乘回归算法来克服这两个问题：首先，线性空间k（分别为。

Kq）通常是有限维的，这对于实际计算是不可行的；第二，积分（18）的一般实际计算通常受到阻碍，因为定律νkma不能以显式形式提供。3.2完全可实现的算法为了避免回归到可能的有限维空间和算法1中的kqa，我们对预先确定的（用户定义的）有限维子空间进行回归，定义为有限组基函数的线性跨度：定义3.2（有限维近似空间）。每k≥ 1和我∈ {0，…，2k- 1} 定义了维数为K（K）Y，i（分别为K（K）Z，i）的有限维函数线性空间KY，k，i:=span{pY，k，i，1，…，pY，k，i，KY，k，i}→ R s.t.E[|pY，k，i，j（X（k）i）|]+∞,KZ，k，i:=span{pZ，k，i，1，…，pZ，k，i，KZ，k，i}→ Rqs。t、 E[|pZ，k，i，j（X（k）i）|]+∞.这些近似空间的最小误差表示为dt（Y，k）1，i:=infφ∈K（K）Y，K，iEh |φ（X（K）i）-y（k）i（X（k）i）|i，T（Z，k）1，i:=infφ∈K（K）Z，K，iEh |φ（Xi）-z（k）i（Xi）|i.为了避免与某些（计算上不可访问的）定律νi有关的积分，如在算法1中，下一个算法2将使用模拟来通过经验度量来近似它。定义3.3（模拟和经验测量）。为了k≥ 0，生成Mk≥ 1个独立副本（模拟）Ck:={(W（k，m），X（k，m），X（k-1，m）：m=1，马氏链轨迹的Mk}和布朗增量(W（k），X（k），X（k）-1)). 用ν（k）M表示Ck模拟的经验概率测量，即ν（k）M=mkxm=1δ（X（k，M），。。。，X（k，m）k，X（k）-1，m），。。。，X（k）-1，m）k-1.W（k，m），。。。，W（k，m）k-1).用X（m）表示马尔可夫链X（k，m），X（k）的轨迹的串联-1，m）和布朗增量W（k，m），即X（m）：=（X（k，m），X（k，m）k，X（k）-1，m），X（k）-1，m）k-1.W（k，m）。

, W（k，m）k-1).模拟的符号和假设。每一个都会形成一个模拟云。在不丧失通用性的情况下，我们假设Mk≥ max0≤我≤2k-1K（k）Y，i∨K（K）Z，i.此外，让模拟云（Ck:K≥ 0）可以独立生成。所有云都定义在一个概率空间中(Ohm（M） ，F（M），P（M））。为了构造支持我们算法分析的概率空间，我们简单地扩展了之前的概率空间支持(W（k），X（k））k≥0，它作为任何单个模拟的通用元素，通过传递到usualproduct空间（“”Ohm,\'F，\'P）=(Ohm, F、 P） (Ohm（M） ，F（M），P（M））。为了简化记法，我们写P（resp.E）而不是“P（resp.E）”。2018年7月3日14:28 14在续集中，我们将经常使用条件作用，仅针对特定的模拟云进行整合，而不是采取全球预期；下面的σ-代数将用于此。定义3.4。每k≥ 0和我∈ {0，…，2k- 1} 定义σ-代数F(*)k:=σ（Ck，…，C），F（M）k，i:=F(*)K-1.∨ σ（X（k，m）j，X（k）-1，m）α（j）：1≤ M≤ 米，1≤ J≤ i） 让E(*)k[·]（分别为E（M）k，i[·]）是关于F的条件期望(*)k（分别为F（M）k，i）。现在，我们可以制定一个完全可实现的算法：算法2。通过设置y（0，M）（·）=Φ（0，M）（·）=MMXm=0Φ（X（0，M））和z（0，M）（·）=MMXm=0Φ（X（0，M））进行初始化k的W（0，m）T递归≥ 1：假设（y（k）-1，M）（·），z（k）-1，M）（·））已经计算过。设置y（k，M）N（·）：=Φ（·），并且，对于每个i∈ {0, . . .

，2k- 1} ，首先计算y（k，M）i（·），然后计算z（k，M）i（·），如下所示：y（k，M）i（·）：=TCyψ（k，M）Y，i（·）z（k，M）i（·）=TCz，k，iψ（k，M）Z，i（·）, （21）当边界Cyand Cz，k，i来自推论2.3时，截断函数TC（·）来自第1节。ψ（k，M）Y，i（·）解OLS（S（k，M）Y，i（x，\'x，w），k（k）Y，i，ν（k）M），S（k，M）Y，i（x，\'x，w）：=Φ（xk）-K-1.-1Xj=α（i）+1z（k）-1，M）j（\'xj）（w2j+w2j+1），ψ（k，M）Z，i（·）解OLS（S（k，M）Z，i（x，\'x，w），k（k）Z，i，ν（k）M），S（k，M）Z，i（x，\'x，w）：=wi（k） 我S（k，M）Y，i（x，\'x，w）- y（k，M）i（xi）,（22）对于x=（x，…，xk）∈ R（2k+1）×d，\'x=（\'x，…，\'xk）-1) ∈ R（2k）-1+1）×d，w=（w，…，wk-1) ∈ Rk×q.定义的直觉3.1。在上面的算法2中，我们显然处于定义3.1的经验测量设置中。这里l=（2k+1）d×（2k）-1+1）d×2kq，每米∈ {1，…，Mk}，rl值随机变量X（m）是定义3.3中给出的马尔可夫链和布朗增量的轨迹。νMis经验测度ν（k）M.概率空间Ohm,~F，~P）是(Ohm, F（M），P），即空间生成所有样本云{Ck:k≥ 0}. 随机函数S（·）是依赖样本的函数S（k，M）Y，i（·）（分别是S（k，M）Z，i（·）），这显然是F(*)K-1. B（Rl）-可测量。算法2中OLS的实际计算使用数值线性代数[25]。2018年7月3日14时28分153.3误差分析在本节中，我们确定算法2’E（k）：=max0的全局误差的上界≤我≤2k-1’E（Y，k，i）+k-1Xi=0’E（Z，k，i）（k） i（23）在每一个等级k上≥ 0，对于E（Y，k，i）给出的局部误差项：=E[|Y（k）i（X（k）i）- y（k，M）i（X（k）i）|]和‘E（Z，k，i）：=E[| Z（k）i（X（k）i）- z（k，M）i（X（k）i）|]。

为了做到这一点，必须找到误差项SE（Y，k，i）：=E[MkPMkm=1 | Y（k）i（X（k，m）i）的上界-y（k，M）i（X（k，M）i）|]，E（Z，k，i）：=E[MkPMkm=1 | Z（k）i（X（k，M）i）-z（k，M）i（X（k，M）i）|]（24）得益于提案3.5中的关系（类似于[24，提案4.10]）：提案3.5。每k∈ {0，…，κ}和i∈ {0，…，2k- 1} ，我们有E（Y，k，i）≤ 2E（Y，k，i）+2028（k（k）Y，i+1）Cylog（3Mk）Mk，\'E（Z，k，i）≤ 2E（Z，k，i）+2028（k（k）Z，i+1）qCz，k，ilog（3Mk）Mk；我们记得Cy=CΦ和Cz，k，i=CX/（T）- t（k）i）（1-θ） /2来自推论2.3。由于y（k，M）i（·）和z（k，M）i（·）是用样本X（k，M）i来计算的，它们也被用在经验范数中，在E（y，k，i）和E（z，k，i）的期望值内，我们的分析的一个重要目标是找到这些项的上界；命题3.5允许我们从E（Y，k，i）和E（Z，k，i）中计算出E（Y，k，i）和E（Z，k，i）的上限，并根据基函数的数量、模拟的数量、时间网格和几乎确定的边界Cz，k，i进行校正。结果表明，校正项与估计的误差项（Z，k，i）到ln（Mk）项的顺序相同；见定理3.7和3.9。因此，修正项对全局误差收敛速度的影响基本上与E（Y，k，i）和E（Z，k，i）的影响相同。命题3.5的证明类似于[24，命题4.10]的证明，因为后者只涉及几乎确定的边界和可测性的一般集中（[24，命题4.9]）。因此，我们在这里没有提供证据，只是参考了那篇论文。

命题3.5中的修正项被解释为由于用于构造（y（k，m）（·）、z（k，m）（·））的云与用于经验范数的样本之间的相互依赖性而产生的误差。在随后的分析中，可以方便地使用以下随机规范符号：；这些表格是随机的，因为它们的值取决于定义3.3中的样本，并且没有采取全球预期。定义3.6。让我们来看一看：Ohm（M） X路→ R或Rqbe F（M） B（Rd）-可测量。每k≥ 2018年7月3日14:28 16∈ {0，…，2k- 1} ，定义随机标准k，i，∞:=ZRd|||Po（X（k）i）-1（dx）和kаkk，i，M:=MiMiXm=1 |а（X（k，M）i）|。标准的k·kk，我，∞利用X（k）i定律，而k·kk，i，m利用样本{X（k，m）i:m=1，…，Mk}的经验测量。实际上，错误项（24）可以写为（Y，k，i）=E[ky（k）i（·）- y（k，M）i（·）kk，i，M]和E（Z，k，i）=E[kz（k）i（·）- z（k，M）i（·）kk，i，M]。此外，根据塔楼定律，\'E（Y，k，i）：=E[ky（k）i（·）-y（k，M）i（·）kk，i，∞] 和¨E（Z，k，i）=E[kz（k）i（·）-z（k，M）i（·）kk，i，∞].我们得到了本文的主要结果，算法2的误差传播。基于不同的假设提出了两个定理。这两个定理的证明非常相似，因为它们基于一种常见的误差分解技术。因此，我们同时证明它们，并解释证明的不同之处；证据很长，并推迟到第3.4节。定理3.7。除一般假设外，还假设任意时间点t的（AX）∈ π（k）∩π（k）属于两个时间网格π（k）和π（k），对于一些k，k，它认为X（k）i=X（k）j≥ 0，我∈ {0, . . .

，2k- 1} ，误差项E（Y，k，i）的上界为4×2-kK（k）Y，iδMk3CX+（2+q）+2K（k）Y，iMkk-1.-1Xj=α（i）+1z（k）-1） j（·）-z（k）-1，M）j（·）∞（k）-1） j+T（Y，k）1，i（25），误差项E（Z，k，i）以12δk（k）Z，i（2+5T1）为界-θ） CxMk（T- t（k）i）1-θ+4δ（2+q）K（K）Z，iCXcXMk+2K（K）Z，i（k） iMkny（k）i（·）-y（k，M）i（·）∞+K-1.-1Xj=α（i）+1z（k）-1） j（·）-z（k）-1，M）j（·）∞（k）-1） jo+T（Z，k）1，i（26）备注。如果X（k）可以被视为X的有限维边缘，假设（AX）是非常有效的，前提是这些边缘是封闭形式的，比如（几何）布朗运动。例如，如果使用Euler格式计算X（k），则可以计算一个最大水平，比如说，通过在下一个时间网格π（κ）上运行一次Euler格式，并为每个k只选择与π（k）相关的值，就可以获得X（k）≤ κ. 我们注意到，对于OREM 3.9，该假设是不必要的。备注3.8。上述定理3.7中的误差范围不容易应用，因为它似乎难以量化规范中的术语|∞更明确地说；这些规范比用于量化误差E（·，k，i）的规范更强，我们对它们没有精确的估计。似乎很难在一般情况下替代这种强范数的使用，参见[5]，他们在2018年6月3日14:28 17使用一般基函数时使用相同的范数获得估计。

然而，我们可以将绝对y和z边界算法2插入（25,26），以获得误差（y，k，i）的粗略上界≤ T（Y，k）1，i+16×2-kK（k）Y，iMk 8（CX）∨ CΦ）TθK（K）Y，iθMk，E（Z，K，i）≤ T（Z，k）1，i+16（2+T1-θ） K（K）Z，icX（T- t（k）i）1-θMk+8（CX∨ CΦ）（1+Tθ-1） K（K）Z，我（k） iMk。这是我们假设的“最坏情况”误差估计y（k）-1） j（·）-y（k）-1，M）j（·）∞和z（k）-1） j（·）-z（k）-1，M）j（·）∞是最大的。我们使用该估计值与通常的最小二乘多步前向动态规划（LSMDP）方案[24]进行了粗略比较，即使用k级修正项的算法2- 1.回忆。每k≥ 0和我∈ {0，…，2k- 1} ，LSMDPalgorithm（当使用相同的时间网格和相同的基函数时）的相应误差估计为EMDP（Y，k，i）≤ T（Y，k）1，i+CΦk（k）Y，iMkand EMDP（Z，k，i）≤ T（Z，k）1，i+CΦk（k）Z，i（k） iMk。（27）我们看到基函数K（K）·，i的数量依赖于时间增量（k） 尽管常数可能会有所不同，但多层模式和MDP模式的模拟次数是相同的。在这个设置中，这两种算法对于这些参数中的每一个的行为可能是相同的。然而，我们强调，这是一个相当粗略的“最坏情况”，其中z（k）的近似值-1） 就像绝对先验界限所允许的那样糟糕。现在我们转向另一个极端，一个“最佳情况”场景，其中|·|∞-术语可以忽略不计；通过研究（25,26），我们发现这些术语抵消了时间增量的负面影响（k） 我。

这会导致“最佳情况”错误估计SEBEST（Y，k，i）≤ T（Y，k）1，i+16×2-kK（k）Y，iMkand Ebest（Z，k，i）≤ T（Z，k）1，i+2K（k）Z，icXMk，特别是激励了对（k） i，不再出现在Denominator中。备注3.8尽管其数量性质粗糙，但作为多级算法和LSMDP算法之间的首次比较，令人鼓舞。对于更精确的陈述来说，一个主要的障碍是，错误界限是在具有一般基础的环境中根据非常强的规范给出的。Wenext为特定的基础选择提供了与LSMDP更精确的比较。定理3.9。除一般假设外，假设（AK）基函数是指示函数，即p·，k，i，j:=1A·，k，i，jon不交集A·，k，i，j；此外，还存在δ≥ 1使得P（X（k）i∈ A·，k，i，j）≥ 1/（δK）。2018年7月3日14:28每18公里∈ {1，…，κ}，i∈ {0，…，2k- 1} ，误差项E（Y，k，i）的上界为4×2-kK（k）Y，iδMk3CX+（2+q）+2K（k）Y，iδMkk-1.-1Xj=α（i）+1′E（Z，k）- 1，j）（k）-1） j+T（Y，k）1，i（28），误差项E（Z，k，i）以12δk（k）Z，i（2+5T1）为界-θ） CxMk（T- t（k）i）1-θ+4δ（2+q）K（K）Z，iCXcXMk+T（Z，K）1，i+2K（K）Z，iδ（k） iMk8qCXTθ-1.（k） icX+-E（Y，k，i）+2kq-ln（2）k-1.-1Xj=α（i）+1′E（Z，k）- 1，j）（k）-1） j. （29）假设（AK）将被满足，例如，如果集合A·，k，i，J在度量P下具有相等的概率1/k（因此δ=1）o （X（k）i）-1.此外，如果X（k）i是一个密度φX（X），它在紧致a上从下到零有界 因此P（X（k）i∈ Hj）≥ 貂皮∈AφX（X）RHJ1DX适用于所有Hj机组 A、 所以把A分成集合A·，k，i，j，满足RA·，k，i，j1dx=const/k（k）·，如果所有j=1，K（K）·，我将形成一个满足（AK）的基。评论让我们注意到，定理3.7与定理3.9的不同之处在于后者不需要重新计算（AX），并且使用了比|·更弱的范数|∞.