Constructing Low Star Discrepancy Point Sets with Genetic Algorithms
Geometric discrepancies are standard measures to quantify the irregularity of distributions. They are an important notion in numerical integration. One of the most important discrepancy notions is the so-called \emph{star discrepancy}. Roughly speaking, a point set of low star discrepancy value allows for a small approximation error in quasi-Monte Carlo integration. It is thus the most studied discrepancy notion. In this work we present a new algorithm to compute point sets of low star discrepancy. The two components of the algorithm (for the optimization and the evaluation, respectively) are based on evolutionary principles. Our algorithm clearly outperforms existing approaches. To the best of our knowledge, it is also the first algorithm which can be adapted easily to optimize inverse star discrepancies.
Code (0)
등록된 구현이 없습니다.
Tasks
Numerical IntegrationSimilar Papers 제목 키워드 기반
LLM-Guided Evolutionary Program Synthesis for Quasi-Monte Carlo Design
Low-discrepancy point sets and digital sequences underpin quasi-Monte Carlo (QMC) methods for high-dimensional integration. We cast two long-standing QMC design problems as program synthesis and solve them with an LLM-gu…
Program SynthesisFinding Low Star Discrepancy 3D Kronecker Point Sets 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 optimizat…
Computing Star Discrepancies with Numerical Black-Box Optimization Algorithms
The $L_{\infty}$ star discrepancy is a measure for the regularity of a finite set of points taken from $[0,1)^d$. Low discrepancy point sets are highly relevant for Quasi-Monte Carlo methods in numerical integration and …
Numerical IntegrationThe Partition Principle Revisited: Non-Equal Volume Designs Achieve Minimal Expected Star Discrepancy
We study the expected star discrepancy under a newly designed class of non-equal volume partitions. The main contributions are twofold. First, we establish a strong partition principle for the star discrepancy, showing t…
Density estimation via mixture discrepancy and moments
With the aim of generalizing histogram statistics to higher dimensional cases, density estimation via discrepancy based sequential partition (DSP) has been proposed [D. Li, K. Yang, W. Wong, Advances in Neural Informatio…
Density Estimation