On the optimization of discrepancy measures

2025/08/06 by Clément, François, Kirk, Nathan, Owen, Art B. +1 · 2 citations
#FOS: Mathematics #Numerical Analysis (math.NA) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2508.04926

Abstract

Points in the unit cube with low discrepancy can be constructed using algebra or, more recently, by direct computational optimization of a criterion. The usual L_∞ star discrepancy is a poor criterion for this because it is computationally expensive and lacks differentiability. Its usual replacement, the L₂ star discrepancy, is smooth but exhibits other pathologies shown by J. Matoušek. In an attempt to address these problems, we introduce the average squared discrepancy which averages over 2^d versions of the L₂ star discrepancy anchored in the different vertices of [0,1]^d. Not only can this criterion be computed in O(dn²) time, like the L₂ star discrepancy, but also we show that it is equivalent to a weighted symmetric L₂ criterion of Hickernell's by a constant factor. We compare this criterion with a wide range of traditional discrepancy measures, and show that only the average squared discrepancy avoids the problems raised by Matoušek. Furthermore, we present a comprehensive numerical study showing in particular that optimizing for the average squared discrepancy leads to strong performance for the L₂ star discrepancy, whereas the converse does not hold.

Citations

• Low Stein Discrepancy via Message-Passing Monte Carlo
• Improving Efficiency of Sampling-based Motion Planning via Message-Passing Monte Carlo
• Constructing Optimal L_∞ Star Discrepancy Sets
• Star Discrepancy Subset Selection: Problem Formulation and Efficient Approaches for Low Dimensions
• Enhancing accuracy of deep learning algorithms by training with\n low-discrepancy sequences
• Optimal point sets for quasi-Monte Carlo integration of bivariate periodic functions with bounded mixed derivatives
• A generalized discrepancy and quadrature error bound

Cited by

• Optimizing Kernel Discrepancies via Subset Selection
• Neural Low-Discrepancy Sequences

Related

• Constructing Optimal L_∞ Star Discrepancy Sets
• Low-discrepancy point sets for non-uniform measures
• Point sets with optimal order of extreme and periodic discrepancy
• The inverse of the star discrepancy of a union of randomly digitally shifted Korobov polynomial lattice point sets depends polynomially on the dimension
• The inverse of the star-discrepancy problem and the generation of pseudo-random numbers