Speaker
Description
While higher-dimensional settings are of greater practical interest, classical Quasi-Monte Carlo constructions often lose their effectiveness: number-theoretic properties become less correlated with uniformity, and state-of-the-art optimization-based approaches suffer from exploding algorithmic complexity or degrading objective functions.
To address these limitations, we propose a concept of direct sum: a high dimensional uniformly distributed set or sequence constructed from lower dimensional low discrepancy components. Examples include classical Sobol and Halton sequences or concatenations of MC and QMC rules. This unifying concept immediately suggests a route for extending state-of-the-art low dimensional constructions to higher dimensions.
We develop two such extensions. First, a genetic algorithm that searches for optimal permutations of Niederreiter's optimal 1D sets [1]; the resulting sets demonstrate superior uniformity in terms of star discrepancy for dimensions up to d=10 and are extensible-in-dimension -- new coordinates can be added without recomputing existing ones. Second, simple yet effective heuristics to extend state-of-the-art Kritzinger sequence [2] to higher dimensions by concatenating permuted or independently generated copies; the heuristics drastically reduce computational cost with only a minor loss of quality.
Our central insight is that low-discrepancy sets and sequences assembled from lower-dimensional components can achieve distribution properties that are in no way inferior to those obtained through direct high-dimensional optimization.
[1] H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 1992.
[2] R. Kritzinger, ``Uniformly distributed sequences generated by a greedy minimization of the L2 discrepancy.'' Moscow Journal of Combinatorics and Number Theory, vol.11, no.3, pp.215--236, 2022.
