Optimizing Kernel Discrepancies via Subset Selection
This work addresses the challenge of improving sampling efficiency in numerical integration for researchers in computational mathematics and statistics, representing an incremental advancement by building on existing optimization techniques.
The paper tackles the problem of selecting low-discrepancy subsets for quasi-Monte Carlo methods by extending subset selection to kernel discrepancies, resulting in an algorithm that efficiently generates samples for uniform and general distributions with known densities.
Kernel discrepancies are a powerful tool for analyzing worst-case errors in quasi-Monte Carlo (QMC) methods. Building on recent advances in optimizing such discrepancy measures, we extend the subset selection problem to the setting of kernel discrepancies, selecting an m-element subset from a large population of size $n \gg m$. We introduce a novel subset selection algorithm applicable to general kernel discrepancies to efficiently generate low-discrepancy samples from both the uniform distribution on the unit hypercube, the traditional setting of classical QMC, and from more general distributions $F$ with known density functions by employing the kernel Stein discrepancy. We also explore the relationship between the classical $L_2$ star discrepancy and its $L_\infty$ counterpart.