Rank-1 lattice rules for multivariate integration in spaces of permutation-invariant functions: Error bounds and tractability
Provides theoretical guarantees for quasi-Monte Carlo methods in high-dimensional integration of symmetric functions, addressing a known bottleneck in computational mathematics.
The paper studies multivariate integration for permutation-invariant functions, deriving error bounds for rank-1 lattice rules and showing that under certain conditions the error can be bounded independently of dimension, achieving tractability with Monte Carlo rate O(n^{-1/2}) and optimal convergence rates O(n^{-λ/2}).
We study multivariate integration of functions that are invariant under permutations (of subsets) of their arguments. We find an upper bound for the $n$th minimal worst case error and show that under certain conditions, it can be bounded independent of the number of dimensions. In particular, we study the application of unshifted and randomly shifted rank-$1$ lattice rules in such a problem setting. We derive conditions under which multivariate integration is polynomially or strongly polynomially tractable with the Monte Carlo rate of convergence $O(n^{-1/2})$. Furthermore, we prove that those tractability results can be achieved with shifted lattice rules and that the shifts are indeed necessary. Finally, we show the existence of rank-$1$ lattice rules whose worst case error on the permutation- and shift-invariant spaces converge with (almost) optimal rate. That is, we derive error bounds of the form $O(n^{-λ/2})$ for all $1 \leq λ< 2 α$, where $α$ denotes the smoothness of the spaces. Keywords: Numerical integration, Quadrature, Cubature, Quasi-Monte Carlo methods, Rank-1 lattice rules.