Finding Low Star Discrepancy 3D Kronecker Point Sets Using Algorithm Configuration Techniques
This work addresses the need for more uniformly distributed point sets in applications like experimental design and quasi-Monte Carlo integration, but it is incremental as it optimizes existing Kronecker constructions rather than introducing a new paradigm.
The authors tackled the problem of improving low star discrepancy point sets for fixed sizes, specifically for 3D Kronecker constructions, and achieved new state-of-the-art discrepancy values for sets of at least 500 points and across ranges of sizes using algorithm configuration techniques.
The L infinity star discrepancy is a measure for how uniformly a point set is distributed in a given space. Point sets of low star discrepancy are used as designs of experiments, as initial designs for Bayesian optimization algorithms, for quasi-Monte Carlo integration methods, and many other applications. Recent work has shown that classical constructions such as Sobol', Halton, or Hammersley sequences can be outperformed by large margins when considering point sets of fixed sizes rather than their convergence behavior. These results, highly relevant to the aforementioned applications, raise the question of how much existing constructions can be improved through size-specific optimization. In this work, we study this question for the so-called Kronecker construction. Focusing on the 3-dimensional setting, we show that optimizing the two configurable parameters of its construction yields point sets outperforming the state-of-the-art value for sets of at least 500 points. Using the algorithm configuration technique irace, we then derive parameters that yield new state-of-the-art discrepancy values for whole ranges of set sizes.