The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension

Dimensionally unbounded problems are frequently encountered in practice, such as in simulations of stochastic processes, in particle and light transport problems and in the problems of mathematical finance. This paper considers quasi-Monte Carlo integration algorithms for weighted classes of functions of infinitely many variables, in which the dependence of functions on successive variables is increasingly limited. The dependence is modeled by a sequence of weights. The integrands belong to rather general reproducing kernel Hilbert spaces that can be decomposed as the direct sum of a series of their subspaces, each subspace containing functions of only a finite number of variables. The theory of reproducing kernels is used to derive a quadrature error bound, which is the product of two terms: the generalized discrepancy and the generalized variation.

Tractability means that the minimal number of function evaluations needed to reduce the initial integration error by a factor is bounded by for some exponent and some positive constant . The -exponent of tractability is defined as the smallest power of in these bounds. It is shown by using Monte Carlo quadrature that the -exponent is no greater than 2 for these weighted classes of integrands. Under a somewhat stronger assumption on the weights and for a popular choice of the reproducing kernel it is shown constructively using the Halton sequence that the -exponent of tractability is 1, which implies that infinite dimensional integration is no harder than one-dimensional integration.

     

方差缩减技巧与拟蒙特卡罗方法

"拟蒙特卡罗方法"是蒙特卡罗方法的确定性变形。方差缩减技巧被广泛用于提高蒙特卡罗方法的效率。本文探讨这此些技巧的确定性变形用于"拟随机"情形以减小变差（提高"拟蒙特卡罗方法"的效率的）的可能性。构造了一系列对某一函数集会精确成立的"拟随机"积分公式。     

Good Lattice Rules in Weighted Korobov Spaces with General Weights

We study the problem of multivariate integration and the construction of good lattice rules in weighted Korobov spaces with general weights. These spaces are not necessarily tensor products of spaces of univariate functions. Sufficient conditions for tractability and strong tractability of multivariate integration in such weighted function spaces are found. These conditions are also necessary if the weights are such that the reproducing kernel of the weighted Korobov space is pointwise non-negative. The existence of a lattice rule which achieves the nearly optimal convergence order is proven. A component-by-component (CBC) algorithm that constructs good lattice rules is presented. The resulting lattice rules achieve tractability or strong tractability error bounds and achieve nearly optimal convergence order for suitably decaying weights. We also study special weights such as finite-order and order-dependent weights. For these special weights, the cost of the CBC algorithm is polynomial. Numerical computations show that the lattice rules constructed by the CBC algorithm give much smaller worst-case errors than the mean worst-case errors over all quasi-Monte Carlo rules or over all lattice rules, and generally smaller worst-case errors than the best Korobov lattice rules in dimensions up to hundreds. Numerical results are provided to illustrate the efficiency of CBC lattice rules and Korobov lattice rules (with suitably chosen weights), in particular for high-dimensional finance problems.     

On scrambled Halton sequences

Halton's low discrepancy sequence is still very popular in spite of its shortcomings with respect to the correlation between points of two-dimensional projections for large dimensions. As a remedy, several types of scrambling and/or randomization for this sequence have been proposed. We examine empirically some of these by calculating their L_∞- and L₂-discrepancies (D^* resp. T^*), and by performing integration tests.Most investigated sequence types give practically equivalent results for D^*, T^*, and the integration error, with two exceptions: random shift sequences are in some cases less efficient, and the shuffled Halton sequence is no more efficient than a pseudo-random one. However, the correlation mentioned above can only be broken with digit-scrambling methods, even though the average correlation of many randomized sequences tends to zero.     

On a simple quasi-Monte Carlo approach for classical ultimate ruin probabilities

This note discusses a simple quasi-Monte Carlo method to evaluate numerically the ultimate ruin probability in the classical compound Poisson risk model. The key point is the Pollaczek–Khintchine representation of the non-ruin probability as a series of convolutions. Our suggestion is to truncate the series at some appropriate level and to evaluate the remaining convolution integrals by quasi-Monte Carlo techniques. For illustration, this approximation procedure is applied when claim sizes have an exponential or generalized Pareto distribution.     

The Haar wavelet characterization of weighted Herz spaces and greediness of the Haar wavelet basis

In this paper we consider the Haar wavelet on weighted Herz spaces. Our weight class, whose name is Ap-dyadic local, is the one defined by the first author (2007). We shall investigate the class of Ap-dyadic weights in connection with the maximal inequalities. After obtaining the properties of weights in the first half of the present paper, we consider the Haar wavelet on weighted Herz spaces in the latter half. We shall show that the Haar wavelet basis is an unconditional basis. We also show that the Haar wavelet is not greedy except for the trivial case, that is, the Haar wavelet is greedy if and only if the Herz space under consideration is a weighted Lp space.     

Fast convergence of quasi-Monte Carlo for a class of isotropic integrals

We consider the approximation of -dimensional weighted integrals of certain isotropic functions. We are mainly interested in cases where is large. We show that the convergence rate of quasi-Monte Carlo for the approximation of these integrals is . Since this is a worst case result, compared to the expected convergence rate of Monte Carlo, it shows the superiority of quasi-Monte Carlo for this type of integral. This is much faster than the worst case convergence, , of quasi-Monte Carlo.

     

TRACTABILITY OF MULTIVARIATE INTEGRATION PROBLEM FOR PERIODIC CONTINUOUS FUNCTIONS

The authors study the tractability and strong tractability of a multivariate integration problem in the worst case setting for weighted l-periodic continuous functions spaces of d coordinates with absolutely convergent Fourier series.The authors reduce the initial error by a factor ε for functions from the unit ball of the weighted periodic contin- uous functions spaces.Tractability is the minimal number of function samples required to solve the problem in polynomial in ε~(-1)and d.and the strong tractability is the pres- ence of only a polynomial dependence in ε.This problem has been recently studied for quasi-Monte Carlo quadrature rules.quadrature rules with non-negative coefficients. and rules for which all quadrature weights are arbitrary for weighted Korobov spaces of smooth periodic functions of d variables.The authors show that the tractability and strong tractability of a multivariate integration problem in worst case setting hold for the weighted periodic continuous functions spaces with absolutely convergent Fourier series under the same assumptions as in Ref.[14]on the weights of the Korobov space for quasi-Monte Carlo rules and rules for which all quadrature weights are non-negative.The arguments are not constructive.     

Periodization strategy may fail in high dimensions

We discuss periodization of smooth functions f of d variables for approximation of multivariate integrals. The benefit of periodization is that we may use lattice rules, which have recently seen significant progress. In particular, we know how to construct effectively a generator of the rank-1 lattice rule with n points whose worst case error enjoys a nearly optimal bound C _d,p n ^−p . Here C _d,p is independent of d or depends at most polynomially on d, and p can be arbitrarily close to the smoothness of functions belonging to a weighted Sobolev space with an appropriate condition on the weights. If F denotes the periodization for f then the error of the lattice rule for a periodized function F is bounded by C _d,p n ^−p ∣∣F∣∣ with the norm of F given in the same Sobolev space. For small or moderate d, the norm of F is not much larger than the norm of f. This means that for small or moderate d, periodization is successful and allows us to use optimal properties of lattice rules also for non-periodic functions. The situation is quite different if d is large since the norm of F can be exponentially larger than the norm of f. This can already be seen for f = 1. Hence, the upper bound of the worst case error of the lattice rule for periodized functions is quite bad for large d. We conjecture not only that this upper bound is bad, but also that all lattice rules fail for large d. That is, if we fix the number of points n and let d go to infinity then the worst case error of any lattice rule is bounded from below by a positive constant independent of n. We present a number of cases suggesting that this conjecture is indeed true, but the most interesting case, when the sum of the weights of the corresponding Sobolev space is bounded in d, remains open.      

Optimal graphs for chromatic polynomials

Let F(n,e) be the collection of all simple graphs with n vertices and e edges, and for G∈F(n,e) let P(G;λ) be the chromatic polynomial of G. A graph G∈F(n,e) is said to be optimal if another graph H∈F(n,e) does not exist with P(H;λ)?P(G;λ) for all λ, with strict inequality holding for some λ. In this paper we derive necessary conditions for bipartite graphs to be optimal, and show that, contrarily to the case of lower bounds, one can find values of n and e for which optimal graphs are not unique. We also derive necessary conditions for bipartite graphs to have the greatest number of cycles of length 4.     

On sub-polynomial lower error bounds for quadrature of SDEs with bounded smooth coefficients

In recent work of Hairer, Hutzenthaler and Jentzen, [11 Hairer, M., Hutzenthaler, M., and Jentzen, A., 2015. Loss of regularity for Kolmogorov equations. Ann. Probab. 43:468–527.[Crossref], [Web of Science ®] , [Google Scholar]], a stochastic differential equation (SDE) with infinitely differentiable andbounded coefficients was constructed such that the Monte Carlo Euler method for approximation of the expected value of the first component of the solution at the final time converges but fails to achieve a mean square error of a polynomial rate. In this article, we show that this type of bad performance for quadrature of SDEs with infinitely differentiable and bounded coefficients is not a shortcoming of the Euler scheme in particular but can be observed in a worst case sense for every approximation method that is based on finitely many function values of the coefficients of the SDE. Even worse we show that for any sequence of Monte Carlo methods based on finitely many sequential evaluations of the coefficients and all their partial derivatives and for every arbitrarily slow convergence speed there exists a sequence of SDEs with infinitely differentiable and bounded by one coefficients such that the first-order derivatives of all diffusion coefficients are bounded by one as well and the first order derivatives of all drift coefficients are uniformly dominated by a single real-valued function and such that the corresponding sequence of mean absolute errors for approximation of the expected value of the first component of the solution at the final time can not converge to zero faster than the given speed.     

A quasi-Monte Carlo data compression algorithm for machine learning

We introduce an algorithm to reduce large data sets using so-called digital nets, which are well distributed point sets in the unit cube. These point sets together with weights, which depend on the data set, are used to represent the data. We show that this can be used to reduce the computational effort needed in finding good parameters in machine learning algorithms. To illustrate our method we provide some numerical examples for neural networks.     

Expected Residual Minimization Method for Stochastic Variational Inequality Problems

This paper considers a stochastic variational inequality problem (SVIP). We first formulate SVIP as an optimization problem (ERM problem) that minimizes the expected residual of the so-called regularized gap function. Then, we focus on a SVIP subclass in which the function involved is assumed to be affine. We study the properties of the ERM problem and propose a quasi-Monte Carlo method for solving the problem. Comprehensive convergence analysis is included as well. This work was supported in part by SRF for ROCS, SEM and Project 10771025 supported by NSFC.