A constraint on extensible quadrature rules

By Art B. Owen. 2014

14 citations recorded by the source corpus.

Here we consider integration methods with error bounded below by $$mn^{-\alpha }$$mn-α for a constant $$m>0$$m>0 and rate $$\alpha >1$$α>1. Suppose that simple averages along an extensible sequence have error at most $$Mn^{-\alpha }$$Mn-α for all $$n$$n in an infinite sequence of sample sizes $$n_1<n_2<\cdots $$n1<n2<⋯. The main result in this paper is a lower bound $$n_{k+1}/n_k\ge \rho $$nk+1/nk≥ρ where $$1<\rho <2$$1<ρ<2, so that the special sample sizes must grow at least geometrically. The bound $$\rho $$ρ increases with $$\alpha $$α and with $$m/M$$m/M. This result always rules out arithmetic sequences but never rules out sample size doubling. The same constraint holds in a root mean square error setting for any random sequence of points. Those random points need not be independent, nor uniformly distributed.

Subfields: Applied Mathematics, Computer Graphics and Computer-Aided Design, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computer Graphics and Computer-Aided Design

In Numerical Analysis

Citations in the corpus

Control functionals for Monte Carlo integration (2014, background): “s are required for sampling. (III) Super-root-nconvergence (for suciently regular f): The convergence rates of QMC and RQMC are well studied and can be super-root-n(at least on certain subsequences; Owen, 2015). Riemann sums can also achieve super-root-nrates, whilst numerical evidence suggests the ”
Control Functionals for Quasi-Monte Carlo Integration (2015, background): “MC integration achieves a root mean square error (RMSE) convergence rate of O(N−1/2) whereas QMC integration can in principle achieve a rate O(N−α/d) on specific geometric sequences {Nn}n=1 [24].”
Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guarantees (2015, background): “However these optimal rates can only hold on sub-sequences of sample sizes n, a consequence of the fact that all function evaluations are weighted equally in the estimator [24].”