Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands
Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands
复制标题
高阶置乱数字网络实现平滑被积函数均方根误差的最优率
DOI：
10.1214/11-aos880
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
J. Dick
中科院分区：
文献类型：
--
作者：
J. Dick
我们研究了一种随机抽样技术，通过在一些采样点平均函数来近似积分$\int_{[0,1]^s}f(\mathbf{x})\,\mathrm{d}\mathbf{x}$。我们关注被积函数光滑的情况，这是统计学中经常出现的问题。近似误差的收敛速度取决于函数的平滑度$f$和采样技术。例如，对于方差有限的函数$f$，蒙特卡罗（MC）抽样产生了阶$N^{-1/2}$（其中$N$是样本数）的均方根误差（RMSE）的收敛性。随机化QMC （RQMC）是MC和拟蒙特卡罗（QMC）的结合，在被积函数有界变化的更强假设下实现了阶为$N^{-3/2+\varepsilon}$的RMSE。RQMC与局部对偶抽样的结合实现了二阶混合偏导数函数的RMSE的$N^{-3/2-1/s+\varepsilon}$阶（其中$s\ge1$为维数）收敛。一般来说，被积函数的额外平滑性并不能提高这些算法的收敛速度。另一方面，已知如果不增加被积函数的平滑性，就不可能提高收敛速度。本文介绍了一种新的RQMC算法，并证明了该算法实现了$N^{-\alpha-1/2+\varepsilon}$阶均方根误差（RMSE）的收敛性，只要被积项满足其在每个变量上具有高达$\alpha>1$阶的平方可积偏混合导数的强假设。已知的RMSE下界表明，对于具有这种平滑性的被积函数，一般不能提高收敛速度。给出了RMSE近似收敛于$N^{-5/2}$阶和$N^{-7/2}$阶的数值例子，并与理论上界保持一致。
We study a random sampling technique to approximate integrals $\int_{[0,1]^s}f(\mathbf{x})\,\mathrm{d}\mathbf{x}$ by averaging the function at some sampling points. We focus on cases where the integrand is smooth, which is a problem which occurs in statistics. The convergence rate of the approximation error depends on the smoothness of the function $f$ and the sampling technique. For instance, Monte Carlo (MC) sampling yields a convergence of the root mean square error (RMSE) of order $N^{-1/2}$ (where $N$ is the number of samples) for functions $f$ with finite variance. Randomized QMC (RQMC), a combination of MC and quasi-Monte Carlo (QMC), achieves a RMSE of order $N^{-3/2+\varepsilon}$ under the stronger assumption that the integrand has bounded variation. A combination of RQMC with local antithetic sampling achieves a convergence of the RMSE of order $N^{-3/2-1/s+\varepsilon}$ (where $s\ge1$ is the dimension) for functions with mixed partial derivatives up to order two. Additional smoothness of the integrand does not improve the rate of convergence of these algorithms in general. On the other hand, it is known that without additional smoothness of the integrand it is not possible to improve the convergence rate. This paper introduces a new RQMC algorithm, for which we prove that it achieves a convergence of the root mean square error (RMSE) of order $N^{-\alpha-1/2+\varepsilon}$ provided the integrand satisfies the strong assumption that it has square integrable partial mixed derivatives up to order $\alpha>1$ in each variable. Known lower bounds on the RMSE show that this rate of convergence cannot be improved in general for integrands with this smoothness. We provide numerical examples for which the RMSE converges approximately with order $N^{-5/2}$ and $N^{-7/2}$, in accordance with the theoretical upper bound.