Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy

Technical Summary: Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy

Problem Statement
The paper addresses the problem of determining the optimal polynomial tractability exponents for the inverse star discrepancy, denoted as $n^*(d, \varepsilon)$. This quantity represents the minimum number of points $N$ required in a $d$-dimensional unit cube $[0, 1)^d$ to achieve a star discrepancy $D^*_N(P) \le \varepsilon$.

Prior work established that $n^*(d, \varepsilon)$ depends linearly on the dimension $d$ and polynomially on $\varepsilon^{-1}$. Specifically, Heinrich, Novak, Wasilkowski, and Woźniakowski (2001) proved the upper bound $n^*(d, \varepsilon) \lesssim d \varepsilon^{-2}$, while Hinrichs (2004) established the lower bound $n^*(d, \varepsilon) \gtrsim d \varepsilon^{-1}$. While the linear dependence on $d$ was confirmed, the exact exponent of $\varepsilon^{-1}$ in the upper bound remained an open question: could the power 2 be reduced to a smaller value $p < 2$?

Methodology
The paper resolves this question by proving that the exponent 2 in the upper bound is optimal, even when allowing for arbitrary fixed polynomial dependence on the dimension. The core methodology involves:

1. Polynomial Regime Analysis: Instead of attempting to strengthen the lower bound uniformly for all $d$ and $\varepsilon$, the author analyzes the behavior of $n^*(d, \varepsilon)$ in specific "polynomial strips" where the dimension grows as a power of the inverse error, i.e., $d \asymp \varepsilon^{-\alpha}$ for $0 < \alpha < 1$.
2. Gram Matrix Construction: The proof utilizes a Gram-matrix argument. The author constructs a family of tensor products of a centered one-dimensional step function $h(t) = 3\mathbb{1}_{[0, 1/3)}(t) - 1/\sqrt{2}$.
   • These functions are chosen such that their tensor products over distinct coordinate sets are orthogonal with respect to the Lebesgue measure.
   • A small star discrepancy implies that the empirical inner products of these functions over the point set $P$ must be close to their theoretical Lebesgue inner products.
3. Trace-Rank Inequality: Evaluating these tensor functions at $N$ points generates a set of vectors in $\mathbb{R}^N$. The Gram matrix of these vectors is shown to have a large trace and a controlled trace of its square. By applying the elementary trace-rank inequality, $\text{rank}(G) \ge (\text{tr } G)^2 / \text{tr}(G^2)$, the author derives a lower bound on the rank, which corresponds to the number of points $N$.

Key Contributions and Results
The primary result is Theorem 1.1, which establishes a new lower bound for $n^*(d, \varepsilon)$ in the regime where $A\varepsilon^{-\alpha} \le d \le B\varepsilon^{-\alpha}$. Specifically, for any $0 < \alpha < 1$, there exist constants such that:
$$n^*(d, \varepsilon) \ge c_{\alpha, B} \, d \, \varepsilon^{-(2-\alpha)}$$
Along these strips, the right-hand side behaves as $\varepsilon^{-2}$.

This leads to Theorem 1.2, which defines the optimal polynomial tractability exponents:

• The accuracy exponent $p^* = \inf \{ p : n^*(d, \varepsilon) \le C d^q \varepsilon^{-p} \}$ is exactly 2.
• The dimension exponent $q^* = \inf \{ q : n^*(d, \varepsilon) \le C d^q \varepsilon^{-p} \}$ is exactly 1.

Consequently, the upper bound $n^*(d, \varepsilon) \le C d \varepsilon^{-2}$ provided by Heinrich et al. (2001) is individually optimal in both exponents.

Significance and Claims
The paper claims that the exponent 2 for $\varepsilon^{-1}$ cannot be improved, even if one permits an arbitrary fixed polynomial dependence on the dimension $d$. This resolves the gap between the previously known lower bound ($\varepsilon^{-1}$) and the upper bound ($\varepsilon^{-2}$) regarding the accuracy exponent.

The author notes several nuances regarding the scope of these results:

• Complementarity with Hinrichs: The new Gram-matrix bound is stronger than Hinrichs' bound ($d\varepsilon^{-1}$) specifically in the intermediate regime where $d$ grows polynomially with $\varepsilon^{-1}$ (i.e., $d \ll \varepsilon^{-1}$). However, for fixed dimensions or when $d \gg \varepsilon^{-1}$, Hinrichs' bound remains the stronger estimate.
• No Pointwise Improvement: The result does not imply a pointwise lower bound of $n^*(d, \varepsilon) \gtrsim d\varepsilon^{-2}$ for every pair $(d, \varepsilon)$. For fixed $d$, classical low-discrepancy constructions show that $n^*(d, \varepsilon)$ can be as low as $O(\varepsilon^{-1} (\log \varepsilon^{-1})^{d-1})$, which is $o(\varepsilon^{-2})$. The optimality of the exponent 2 is a property of the uniform polynomial tractability across all dimensions.
• Open Problem: While the exponents are determined to be optimal, the precise mixed dependence on $d$ and $\varepsilon$ within specific joint regimes (the exact constants and lower-order terms) remains an open problem.

In summary, the paper demonstrates that the Heinrich–Novak–Wasilkowski–Woźniakowski upper bound is tight in terms of its asymptotic exponents, confirming that the inverse star discrepancy cannot be computed with a rate better than $\varepsilon^{-2}$ in a uniform polynomial sense.