Source-linked AI summary
The $L\log L$-Luxemburg Discrepancy for Nonnegative Weights Suffers from the Curse of Dimensionality
Josef Dick, Friedrich Pillichshammer
TL;DR
The paper asks how the L log L-Luxemburg discrepancy fits into the tractability picture for discrepancy measures. It studies normalized discrepancy with arbitrary nonnegative weights and proves that the required number of points grows exponentially with dimension, including for equal-weight quasi-Monte Carlo rules.
Problem
How the L log L-Luxemburg discrepancy behaves with respect to the curse of dimensionality and tractability had not yet been added to the overall picture for discrepancies with nonnegative weights.
Source: §1 · p. 2Method
Results
Takeaways & Limitations
The curse-of-dimensionality result also applies to the classical equal-weight quasi-Monte Carlo discrepancy.
Source: §2 · p. 4The proof requires nonnegative weights; the corresponding problem for signed weights remains open.
Source: §2 · p. 4
Abstract
from arXiv · showhide
We study the normalized discrepancy in the Luxemburg norm generated by $\Phi(s)=s\log(1+s)$. For arbitrary nonnegative quadrature weights, we prove that the associated information complexity suffers from the curse of dimensionality: for every $\varepsilon\in(0,1)$, there exist constants $c_\varepsilon>0$ and $d_0=d_0(\varepsilon)\in\mathbb{N}$ such that \[N_{\Phi,+}(\varepsilon,d)\ge c_{\varepsilon} d^{-1}(1.07735\ldots)^d \qquad \mbox{for all } d\ge d_0. \] The result therefore also applies to equal-weight quasi-Monte Carlo rules.
1 Introduction
This introduction places discrepancy research in the information-based complexity perspective and extends the tractability picture to the L log L-Luxemburg norm. The paper's main result is exponential growth in the required number of points, even with arbitrary nonnegative weights.
1 Introduction
- The paper considers the generalized discrepancy for points with corresponding real weights; equal weights a_k = 1/N give the classical local discrepancy used in quasi-Monte Carlo.The generalized discrepancy uses an indicator that selects points whose components are all below the corresponding coordinates of t.Source: §1 · p. 1
- Discrepancy is obtained by taking a norm of the discrepancy function, with Lp norms the most commonly studied choice.Other norms also appear in the literature and applications.Source: §1 · p. 2
- Finite-p Lp-discrepancies suffer from the curse of dimensionality, whereas L∞-discrepancy is polynomially tractable for nonnegative weights.The introduction situates these results in the information-based complexity perspective, which studies the inverse discrepancy as dimension and the prescribed relative error vary.Source: §1 · p. 2
- For every fixed ε in (0, 1), the required number of points for L log L-Luxemburg discrepancy grows exponentially with dimension, even for arbitrary nonnegative weights.The result extends the tractability picture to this norm.Source: §1 · p. 2
2 L log L-Luxemburg norm discrepancy – the main result
The section defines L log L-Luxemburg discrepancy and its normalized information complexity, then proves curse-of-dimensionality behavior for nonnegative weights. The result also applies to equal-weight QMC rules and to integration in the associated space.
2 L log L-Luxemburg norm discrepancy – the main result
- The paper uses an Orlicz norm generated by a Young function to define its L log L-Luxemburg discrepancy.The discrepancy is defined for point sets with corresponding real weights; the initial discrepancy is the discrepancy of the empty set.Source: §2 · pp. 2–3
- Discrepancy-integration duality identifies worst-case integration error in the anchored Sobolev–Orlicz space with discrepancy, including their initial errors.For nonnegative weights, the resulting normalized integration information complexity equals the discrepancy information complexity.Source: §2 · pp. 3–4
- The normalized information complexity is the minimum node count needed to reduce the discrepancy to at most ε times the initial discrepancy.The complexity is considered for nonnegative weights and QMC weights, with QMC weights a subclass of nonnegative weights.Source: §2 · p. 4
- Theorem 2.2 establishes curse-of-dimensionality behavior for normalized L log L-Luxemburg discrepancy with nonnegative weights, and the result also covers equal-weight QMC rules.The theorem is stated for every ε in (0, 1), with constants allowed to depend on ε.Source: §2 · p. 4
- The proof relies essentially on nonnegative weights, while the corresponding question for signed weights remains open.Nonnegativity permits a positive-mixture representation and a subadditivity estimate.Source: §2 · p. 4
3 Luxemburg-norm preliminaries and the initial discrepancy
The preliminaries establish basic properties of the Luxemburg norm and characterize the initial discrepancy. They also obtain the asymptotic scale of the normalization used in that characterization.
3 Luxemburg-norm preliminaries and the initial discrepancy
- The Luxemburg norm of a bounded measurable function that is not almost everywhere zero is the unique K0 > 0 for which ρΦ(f/K0) = 1.For K ≥ ∥f∥Φ, the modular satisfies ρΦ(f/K) ≤ 1.Source: §3 · p. 5
- Every measurable f on [0, 1]^d satisfies ∥f∥L1 ≤ κ∥f∥Φ, where κ is the positive solution of κ log(1 + κ) = 1.The paper gives κ = 1.239977887....Source: §3 · p. 5
- For every p > 1, a constant Cp > 0 bounds ∥f∥Φ by Cp∥f∥Lp for measurable f on the unit cube.The proof is deferred to the Appendix.Source: §3 · p. 5
4 The proof of Theorem 2.2
The proof converts small normalized discrepancy into a lower bound on a fractional moment, then compares that bound with what N nonnegative-weight atoms can achieve. The comparison yields an exponential lower bound on the required number of nodes.
4 The proof of Theorem 2.2
- Small normalized discrepancy gives a dimension-independent positive lower bound on Eνd[Z^1/2] over volume-typical boxes.The proof localizes to boxes whose volume is typical under νd.Source: §4 · pp. 8–10
- Each anchored-box atom loses a fixed factor per coordinate in its fractional moment, while a mixture of N atoms gains at most a factor N^1/2.The proof uses nonnegative weights and compares the two moment bounds.Source: §4 · pp. 8, 10
- The argument adapts methods from [4] with greater technical detail because the L log L-Luxemburg norm is more complicated.Source: §4 · p. 8
- For every N-point set P with corresponding nonnegative weights A and normalized L log L-Luxemburg discrepancy at most ε, the lower bound holds, with cε := b2(1 + 2κεc0)−1 > 0.The constants b and d1 are independent of the particular nodes and weights.Source: §4 · pp. 8, 11
Discrepancy-integration duality
The section establishes a duality between discrepancy and numerical integration error in the anchored Sobolev–Orlicz space. A norming function attains the bound, yielding equality between the integration error and discrepancy norm.
Discrepancy-integration duality
- The proof uses the Orlicz–Hölder inequality and its sharpness via a norming function.The displayed inequality is sharp for the function and its associated norming function.Source: Discrepancy-integration duality · pp. 11–12
- The integration error is written as L(f) = I(f) − QP,A(f), with η equal to Lebesgue measure minus the weighted point-mass measure.Source: Discrepancy-integration duality · p. 13
- The discrepancy-integration duality is attained by a function f* whose integration error equals the norm of the upper anchored local discrepancy.Its derivative is the signed norming function corresponding to that discrepancy, with complementary Luxemburg norm equal to one.Source: Discrepancy-integration duality · pp. 12–13
Embeddings
The section proves that the L log L-Luxemburg norm is controlled by Lp norms for every p > 1. Its proof bounds the Young function by a power with exponent min(p, 2).
Embeddings
- For every p > 1, ∥f∥Φ ≤ Cp∥f∥Lp for measurable f on [0, 1]^d.The proof sets r = min(p, 2) and bounds Φ(t) by cr t^r for t ≥ 0.Source: Embeddings · p. 14