# Computing Star Discrepancies with Numerical Black-Box Optimization Algorithms

arXiv: https://arxiv.org/abs/2306.16998 · HTML: https://mlsanity.com/paper/2306.16998/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2023.

## Built on by (most cited first, 3 of 3)

- [Exploring Exploration in Bayesian Optimization](https://mlsanity.com/paper/2502.08208/) (2025)
- [Message-Passing Monte Carlo: Generating low-discrepancy point sets via Graph Neural Networks](https://mlsanity.com/paper/2405.15059/) (2024)
- [LLM-Guided Evolutionary Program Synthesis for Quasi-Monte Carlo Design](https://mlsanity.com/paper/2510.03650/) (2025)

## Abstract (arXiv)

The L∞ 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 several other applications. Unfortunately, computing the L∞ star discrepancy of a given point set is known to be a hard problem, with the best exact algorithms falling short for even moderate dimensions around 8. However, despite the difficulty of finding the global maximum that defines the L∞ star discrepancy of the set, local evaluations at selected points are inexpensive. This makes the problem tractable by black-box optimization approaches. In this work we compare 8 popular numerical black-box optimization algorithms on the L∞ star discrepancy computation problem, using a wide set of instances in dimensions 2 to 15. We show that all used optimizers perform very badly on a large majority of the instances and that in many cases random search outperforms even the more sophisticated solvers. We suspect that state-of-the-art numerical black-box optimization techniques fail to capture the global structure of the problem, an important shortcoming that may guide their future development. We also provide a parallel implementation of the best-known algorithm to compute the discrepancy.