Session III.5 - Information-Based Complexity
Wednesday, June 21, 14:30 ~ 15:00
Randomized lattice rules
Dirk Nuyens
KU Leuven, Belgium - This email address is being protected from spambots. You need JavaScript enabled to view it.
It was shown in Kritzer, Kuo, Nuyens and Ullrich (2019) that randomized lattice rules can achieve the near optimal randomized error for integration, which is half an order better than the deterministic one, in the Korobov space. This randomized lattice rule algorithm picks a random prime in the range $(n/2, n]$ and then randomly selects a ``good generating vector'' for that prime. In Dick, Goda and Suzuki (2022) it was later shown that one can construct this generating vector by a randomized component-by-component construction algorithm.
In joint work, Kuo, Nuyens and Wilkes (2023+), we show that the generating vector can be pre-determined and hence only require randomness for selecting the random prime from $(n/2, n]$. We show a component-by-component algorithm which can construct a vector in time $O(d \, n^4 / \log(n))$ which is only $\log(n)$ more expensive than calculating the actual randomized error for the final rule. In a modification, Wilkes and Nuyens (2023+), we show that also for $0 \lt \alpha \le 1/2$ a pre-determined vector is able to achieve the near optimal randomized error where the algorithm randomly picks the prime and a shift.
Joint work with Laurence Wilkes (KU Leuven, Belgium) and Frances Y. Kuo (UNSW Sydney, Australia).