Extreme $L_p$ discrepancy, numerical integration and the curse of dimensionality
This work clarifies the computational tractability of extreme $L_p$ discrepancy, a measure of point set distribution irregularity, for researchers working on numerical integration and high-dimensional problems.
This paper establishes a dual integration problem whose worst-case error is equivalent to the extreme $L_p$ discrepancy of the integration nodes. Through this, the authors demonstrate that the extreme $L_p$ discrepancy is subject to the curse of dimensionality for all $p \\in (1, \\infty)$.
The classical notion of extreme $L_p$ discrepancy is a quantitative measure for the irregularity of distribution of finite point sets in the $d$-dimensinal unit cube. In this paper we find a dual integration problem whose worst-case error is exactly the extreme $L_p$ discrepancy of the underlying integration nodes. Studying this integration problem we show that the extreme $L_p$ discrepancy suffers from the curse of dimensionality for all $p \in (1,\infty)$. It is known that the problem is tractable for $p=\infty$; the case $p=1$ stays open.