$L_2$-approximation using randomized lattice algorithms

Abstract

We propose a randomized lattice algorithm for approximating multivariate periodic functions over the $d$-dimensional unit cube from the weighted Korobov space with mixed smoothness $\hat{I}\pm >1/2$ and product weights ${\hat{I}}_1^3,{\hat{I}}_2^3,\dots \in [0,1]$. Building upon the deterministic lattice algorithm by Kuo, Sloan, and Woźniakowski (2006), we incorporate a randomized quadrature rule by Dick, Goda, and Suzuki (2022) to accelerate the convergence rate. This randomization involves drawing the number of points for function evaluations randomly, and selecting a good generating vector for rank-1 lattice points using the randomized component-by-component algorithm. We prove that our randomized algorithm achieves a worst-case root mean squared $L_2$-approximation error of order $M^{-\hat{I}\pm (2\hat{I}\pm +1)/(4\hat{I}\pm +1)+\epsilon }$ for an arbitrarily small $\epsilon >0$, where $M$ denotes the maximum number of function evaluations, and that the error bound is independent of the dimension $d$ if the weights satisfy $\sum_{j=1}^\infty γ_j^{1/α} < \infty$. Our upper bound converges faster than a lower bound on the worst-case $L_2$-approximation error for deterministic rank-1 lattice-based approximation proved by Byrenheid, Kämmerer, Ullrich, and Volkmer (2017). We also show a lower error bound of order $M^{-\hat{I}\pm /2-1/2}$ for our randomized algorithm, leaving a slight gap between the upper and lower bounds open for future research.

major revision, 23 pages