Source-linked AI summary
The curse of dimensionality for geometric $L_1$-discrepancies with nonnegative weights
Josef Dick
TL;DR
The paper addresses open L1-discrepancy endpoint cases by proving deterministic lower bounds for arbitrary nonnegative weights. A normalized product-kernel argument turns a uniform one-dimensional square-root-affinity gap into dimension-dependent bounds, establishing the curse of dimensionality in all three geometries.
Problem
The normalized L1 star, extreme, and periodic cases remained open, while random-point analysis did not prove a deterministic lower bound.
Source: §1 · p. 2Method
Results
The normalized star, extreme, and periodic L1-discrepancies with nonnegative weights, and their equal-weight subclasses, suffer from the curse of dimensionality.
Source: §2.4 · p. 4Takeaways & Limitations
The same elementary product-kernel argument resolves all three L1 endpoint cases for arbitrary nonnegative node weights.
Source: §1 · p. 2
Abstract
from arXiv · showhide
We prove that the normalized star, extreme, and periodic $L_1$-discrepancies with arbitrary nonnegative weights suffer from the curse of dimensionality. A single elementary lemma is used in all three cases: after normalizing the target and every one-dimensional kernel to probability densities, a uniform square-root-affinity gap tensorizes over the coordinates. For every $d\in \mathbb{N}$ and $0<\varepsilon<1$, the normalized information complexities have lower bounds of the form \[ \frac{(1-\varepsilon)^2}{1+\varepsilon}\,q^d, \] with \[ q_{\mathrm{star}}=\frac12+\frac1{\sqrt3},\qquad q_{\mathrm{ext}}=\frac{75(9+4\sqrt2)}{784},\qquad q_{\mathrm{per}}=\frac{25}{16}. \] All three constants are larger than one. The argument uses only nonnegativity, product integration, the elementary inequalities for the square root, and Cauchy--Schwarz.
1 Introduction
The paper addresses open L1-discrepancy endpoint cases with a deterministic lower-bound argument for arbitrary nonnegative node weights. Its product-kernel method yields exponential lower bounds across the star, extreme, and periodic settings.
1 Introduction
- Geometric discrepancy measures how well a finite weighted set reproduces volumes of prescribed test boxes, and its inverse asks how many nodes achieve a fixed reduction from the empty rule.The normalized formulation follows a standard approach in information-based complexity.Source: §1 · p. 1
- Average-case estimates alone do not determine the dimension dependence of optimal deterministic discrepancy complexity.The paper focuses on normalized information complexity as dimension varies.Source: §1 · p. 2
- The star, extreme, and periodic L1 cases were identified as open, and random-point analysis did not itself establish a deterministic lower bound.The paper resolves these endpoint cases for arbitrary nonnegative node weights.Source: §1 · p. 2
- A uniform one-dimensional square-root-affinity bound below one tensorizes across coordinates to give explicit exponential lower bounds.The proof normalizes the target and each one-dimensional kernel to probability densities.Source: §1 · p. 2
- The argument allows arbitrary nonnegative coefficients, but its square-root step does not extend to signed weights.The coefficient sum need not equal one; the same lower bounds therefore include equal-weight point sets.Source: §1 · p. 2
2 Discrepancies and normalized information complexity
The section sets out the weighted-rule setting and defines normalized information complexity relative to the empty rule. The main theorem establishes the curse of dimensionality for all three L1 geometries, including equal-weight rules.
2 Discrepancies and normalized information complexity
- A weighted rule with at most N terms uses nodes in [0, 1)^d and nonnegative coefficients; repeated nodes and zero coefficients are allowed.Equal-weight rules require each coefficient to be 1/N.Source: §2 · p. 3
2.3 Periodic discrepancy
- The periodic box parametrization by starting point and length is equivalent to the endpoint parametrization and preserves Lebesgue measure.The change of variables is justified by translation invariance on the circle and Fubini’s theorem.Source: §2.3 · p. 3
2.4 Minimal errors and the curse of dimensionality
- The curse of dimensionality is defined by an exponential lower bound in dimension for some fixed error tolerance, and the paper’s estimates give it for every fixed tolerance.The estimates apply for all sufficiently large dimensions.Source: §2.4 · p. 4
- The normalized star, extreme, and periodic L1-discrepancies with nonnegative weights, and their equal-weight subclasses, suffer from the curse of dimensionality.The theorem gives the same three bounds for the equal-weight class.Source: §2.4 · p. 4
3 An elementary product-kernel lower bound
The abstract argument converts a uniform one-dimensional affinity gap into a lower bound for sums of product kernels. It normalizes the target and kernels, then uses nonnegativity and product integration to control relative L1 accuracy.
3 An elementary product-kernel lower bound
- The proof normalizes the target measure and each kernel with positive mass to probability densities.The kernel density is defined relative to the target measure.Source: §3 · p. 4
- A uniform upper bound below one on one-dimensional affinity yields a dimension-dependent lower bound for nonnegative sums of product kernels.The lemma provides the shared abstract argument for the geometric applications.Source: §3 · pp. 4–5
- Relative L1 accuracy controls the normalized mass of the kernel sum, while the one-dimensional affinity bound multiplies across coordinates.The argument uses product integration and a square-root moment.Source: §3 · p. 5
- The square-root estimate for a nonnegative finite sum, followed by Cauchy–Schwarz, supplies the bound for the product-kernel sum.The proof also uses the elementary inequality relating |1 − √z| to |1 − z|.Source: §3 · p. 6
- The argument does not cover signed sums because it relies on nonnegativity in the square-root step and mass control.Terms of zero coefficient or zero kernel mass may be deleted without loss for the stated lower bound.Source: §3 · p. 6
4 The three one-dimensional affinity bounds
The three applications reduce to geometry-specific one-dimensional affinity calculations. Their resulting uniform bounds provide the common input to the product-kernel argument.
4.1 Star boxes
- The star-box application uses target h(t) = t and indicator kernels for intervals [0, x).The proof transforms the affinity expression and analyzes its maximum by differentiation.Source: §4.1 · pp. 6–7
4.2 Extreme boxes
- The extreme-box kernels have zero mass at the endpoints, so the affinity calculation is defined for 0 < z < 1.The kernel is the indicator of u ≤ z < v on the domain u ≤ v.Source: §4.2 · p. 7
- For extreme boxes, the two nonnegative factors in the affinity expression are maximized at z = 1/2.The proof uses symmetry and concavity of the integral factor, along with z(1 − z) ≤ 1/4, before evaluating an elementary double integral.Source: §4.2 · p. 8
4.3 Periodic boxes
- For periodic boxes, the calculation indexes each interval by its starting point and length; at fixed z and length ℓ, the admissible starts form a circle interval of length ℓ.This measure calculation supplies the periodic affinity identity.Source: §4.3 · p. 8
5 Proof of the main theorem
The proof reduces the three discrepancy variants to L1 distances involving product kernels, applies a common affinity bound to individual rules, and passes to the infimum.
5 Proof of the main theorem
- The star discrepancy equals ∥H_d−G∥L1, with initial error I_d=2^-d.The proof uses the star-specific h and k_x from Section 4.1.Source: §5 · p. 9
- The extreme discrepancy equals ∥H_d−G∥L1, with initial error I_d=6^-d.The proof uses the extreme-specific h and k_z from Section 4.2.Source: §5 · p. 9
- The periodic discrepancy equals ∥H_d−G∥L1, with initial error I_d=2^-d.The proof uses the periodic-specific h and k_z from Section 4.3.Source: §5 · p. 9
- After deleting zero coefficients and zero-mass product kernels, the proof applies Lemma 3.1 with the three affinity bounds, then passes from individual rules to the infimum.The product-kernel form of the discrepancy integrand is used in all three cases.Source: §5 · p. 9
- For each discrepancy, q_C>1 yields N_C,1^+(ε,d)≥c^d for any 1<c<q_C once d is sufficiently large.The proof establishes that each number in (5.2) exceeds one.Source: §5 · p. 9
Declaration of generative AI use
J. D. used ChatGPT during exploratory development, literature search, and preparation of the exposition and LaTeX source; the authors take responsibility for the paper’s contents.
Declaration of generative AI use
- J. D. used ChatGPT during exploratory development and literature search.Source: Declaration of generative AI use · p. 10
- ChatGPT was also used to prepare the exposition and LaTeX source.Source: Declaration of generative AI use · p. 10
- The authors take full responsibility for the mathematical arguments, calculations, references, and conclusions.Source: Declaration of generative AI use · p. 10