Low extreme discrepancy points: sharp bounds, systematic optimization, and provable termination criteria
摘要
Quasi-Monte Carlo (QMC) methods are indispensable for high-dimensional integration, yet their efficiency hinges on the uniformity of point sets—so-called low-discrepancy points. These points are also fundamental in computer experiments, robust parameter design, machine learning, and graphics. Among discrepancy measures, the extreme discrepancy (EDisc) stands out: it is symmetric, computationally tractable, directly linked to QMC integration error, and achieves the highest relative improvement over other discrepancies in message-passing Monte Carlo optimization. However, EDisc suffers from the curse of dimensionality. This fundamental challenge makes sharp lower bounds and provable stopping criteria essential for practical design construction. Despite the importance of EDisc, no comprehensive analysis exists for high-dimensional symmetric balanced designs (HD-SBDs)—a fundamental class of experimental design. This paper fills that gap. We derive novel explicit analytical expressions and sharp lower bounds for EDisc in HD-SBDs, along with necessary optimality conditions. We prove that EDisc satisfies a row-difference structure that enables deterministic constructions—component orthogonal arrays, good lattice points, level addition, and level collapse—for arbitrary numbers of levels. For scenarios not covered directly, we adapt a systematic optimization method that uses the theoretical lower bounds as provable stopping criteria. Collectively, our results tell practitioners precisely when to stop searching and provide a complete toolkit for constructing optimal designs under the EDisc.