$L_2$-approximation using randomized lattice algorithms

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 $\alpha >1\mathrm{/}2$ and product weights ${\gamma }_1,{\gamma }_2,\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^{-\alpha (2\alpha +1)\mathrm{/}(4\alpha +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}^{\mathrm{\infty }}{\gamma }_j^{1\mathrm{/}\alpha }<\mathrm{\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^{-\alpha \mathrm{/}2-1\mathrm{/}2}$ for our randomized algorithm, leaving a slight gap between the upper and lower bounds open for future research.