Source-linked AI summary
The Quality of Lattice Sequences for Arbitrary Sample Size
Larysa Matiukha, Yuhan Ding, Fred J. Hickernell
TL;DR
When time limits or early termination prevent using preferred sample sizes, the paper develops error bounds for extensible lattice sequences at arbitrary n. It finds nearly O(n^-α) decay for n = λb^p and reports that optimal weights can further improve arbitrary-n cubature error.
Problem
Preferred sample sizes n = b^m may be unavailable under computational time budgets or early termination, motivating error bounds for arbitrary n.
Source: §1 · p. 2Method
The paper extends Pα bounds to arbitrary n and analyzes the related Hilbert-space quantity Pα,2, including cubature with optimal sample weights.
Source: §2 · p. 3, §5 · p. 14, §5.1 · p. 16Results
Nearly O(n^-α) decay is attainable for Pα when n = λb^p, and at α = 1 optimal weights yield smaller arbitrary-n Pα,2 than the full lattice with b^m < n.
Source: §6 · pp. 18–19Takeaways & Limitations
Sample sizes n = λb^p may still be useful when a full lattice is unavailable, and optimal weights can improve the cubature error bound for arbitrary n.
Source: §6 · pp. 18–19For α > 1, the general-n Pα upper bound has n power −1; the n = λb^p bound assumes λ is small, or its λ^(α−1) term may be substantial.
Source: §4 · p. 7
Abstract
from arXiv · showhide
Extensible lattices are a common choice of nodes for approximating multidimensional integrals by a sample mean, typically using sample sizes of the form $n = b^m$ for a prime base $b$ and non-negative integer $m$. However, a computational time budget or early termination due to hardware failure may prevent us from choosing the preferred number of samples. In this paper, we establish an upper bound on the figure of merit $P_\alpha$ for extensible lattice sequences \emph{with arbitrary $n$}, derived as a worst-case error in a Banach space setting. We show that although the upper bound on $P_\alpha$ can decay no faster than $\mathcal O(n^{-1})$ for general $n$, restricting $n$ to the form $n =\lambda b^p$, where $\lambda$ is a fixed integer, we can recover the optimal decay of nearly $\mathcal O(n^{-\alpha})$ as $p \to \infty$. We also investigate a related figure of merit, $P_{\alpha,2}$, arising as a worst-case error for Hilbert spaces of integrands. We obtain a theoretical upper bound on $P_{\alpha,2}$ in terms of $P_{\alpha}$ for equal sample weights and show numerically that optimal sample weights can improve the cubature error bound even further.
1. Introduction
The introduction motivates arbitrary sample sizes when time budgets or early termination prevent using preferred powers of the base. It frames extending existing extensible-lattice results to all positive n, with weaker bounds expected for general n.
1. Introduction
- Lattices approximate multidimensional integrals by sample means, and extensible lattices have good generating vectors for preferred sizes n = b, b^2, and so on.The introduction cites applications in quantitative finance, statistics, and physics.Source: §1 · p. 1
- Early termination or computational time budgets can prevent choosing sample sizes n = b^m.The paper aims to extend existing results to all positive n, while recognizing that general-n upper bounds will be somewhat worse than bounds for powers of the base.Source: §1 · p. 2
- The paper introduces Pα as a Banach-space worst-case error for arbitrary n, derives its upper bound, and studies Hilbert-space Pα,2 and optimal sample weights.Pα,2 is described as more amenable to calculation than Pα.Source: §1 · p. 2
2. Background
The background contrasts fixed-cardinality lattices with extensible sequences that retain previously generated points as sample size grows. It also reviews existing arbitrary-n error bounds and states the paper’s extensions.
2. Background
- A fixed-size lattice depends on n, so changing the sample size requires generating a new point set.A shift Δ may be added modulo 1 to the lattice points.Source: §2 · p. 2
- Extensible lattice sequences allow points to be added without discarding earlier ones, using the van der Corput sequence in base b.The generating vector h is a generalized integer, and the base is suppressed in the notation.Source: §2 · p. 2
- Figure 1 illustrates the first 64 points of a two-dimensional shifted extensible lattice, with the square becoming more uniformly filled as n increases.Compare the point distributions as the sequence grows.Source: Figure 1 · p. 3
- For arbitrary n, a prior Hilbert-space result bounds error by C log_b(n) n^-min(α,1) when full-lattice errors are bounded by C(b^m)^-α.The paper extends bounds on Pα to arbitrary n and derives a Hilbert-space bound without the additional logarithmic term for α > 1.Source: §2 · p. 3
3. Worst case error analysis for arbitrary n
This section extends traditional lattice error analysis to nodesets that are not full lattices. It defines a Banach-space worst-case error measure and develops bounds whose finite-sum treatment has a stated restriction.
3. Worst case error analysis for arbitrary n
- The analysis extends traditional error analysis to nodesets that are not full lattices and considers integrands with absolutely summable Fourier series.The section defines a Banach space using positive coordinate weights and uses α to denote integrand smoothness.Source: §3 · p. 4
- For an arbitrary point set, the worst-case error in approximating the integral by the sample mean is expressed using the Fourier-based error analysis.The analysis uses Hölder’s inequality; the error term vanishes for k = 0, and the integral vanishes for k ≠ 0.Source: §3 · p. 4
- For an extensible lattice with n = b^m, Pα has a simplified form based on the dual lattice with the origin removed.The dual lattice is defined by the congruence k^T h (mod b^m) = 0.Source: §3 · pp. 4–5
- For positive integer α, P_2α can be converted from an infinite sum to a finite Bernoulli-polynomial sum when n = b^m, but not when n ≠ b^m.The finite-sum conversion relies on an expansion of the even Bernoulli polynomials.Source: §3 · p. 5
- For preferred sizes n = b^m, an existing bound gives Pα no greater than a constant times b^-mα with logarithmic factors, for a generating vector h independent of m.The bound is stated for α > 1 and extends to m = 0 with modified logarithmic terms.Source: §3 · pp. 5–6
- The section closes by stating that the upper bound will next be extended to all positive n.Source: §3 · p. 6
4. The figure of merit Pα(h, γ, n, s) for n other than bm
For extensible lattices, the section bounds Pα for arbitrary sample sizes and shows how restricting n to fixed multiples of powers of the base improves the decay. Numerical experiments illustrate the bounds and examine Keister integration errors.
4. The figure of merit Pα(h, γ, n, s) for n other than bm
- For arbitrary positive integer n, Pα has an upper bound with power of n fixed at −1, using the same constant and logarithmic power as in the bound for n=b^m.The theorem assumes fixed integer base b≥2, smoothness parameter α>1, coordinate-weight vector γ∈[0,∞)∞, and ϵ>0.Source: §4 · p. 6
4.1. Proof of (10)
- The proof decomposes n into b-ary prefixes and bounds their Pα terms; the m=0 term limits the general-n bound to O(n^-1+δ).The argument uses the triangle inequality and sums the bounds for powers of the base.Source: §4.1 · pp. 7–9
4.2. Proof of (11)
- For n=λb^p with λ coprime to b, fixed λ recovers nearly O(n^-α) decay as p→∞; when λ/n stays bounded away from zero, decay matches the general-n case.Under a summability condition on coordinate weights, the upper bounds are independent of s.Source: §4 · p. 7, §4.2 · pp. 10–12
4.5. Numerical Experiments
- With α=2, the bound decays nearly O(n^-2) for powers of 2 and closer to O(n^-1) for arbitrary n; n=λ2^p, λ=1, 3, 5, 7, also gives nearly O(n^-2).The experiments also plot absolute errors for a six-dimensional Keister integral over all n≤2^15 and over the restricted sample sizes.Source: Figure 2 · p. 12, §4.5 · pp. 12–13, Figure 3 · p. 13
5. The Hilbert space setting with Pα,2 and optimal sample weights
The paper extends worst-case error analysis to a Hilbert space figure of merit that can be evaluated for arbitrary sample sizes, and derives results for unequal sample weights. The section establishes bounds and numerically finds that optimal weights improve the figure of merit relative to equal weights.
5. The Hilbert space setting with Pα,2 and optimal sample weights
- In the Hilbert space setting, Pα,2 has an exact finite-sum formula for arbitrary n, unlike the arbitrary-n Pα formula in the Banach space setting, which involves an irreducible infinite sum.The Hilbert space uses a weighted ℓ2 norm of Fourier coefficients rather than the Banach space's ℓ∞ norm.Source: §5 · pp. 14–15
5.1. Derivation of exact formulae involving arbitrary sample weights
- The optimal sample weights solve a minimization problem constrained to integrate constant functions exactly, and are given by wopt = K^-1 1/(1^T K^-1 1).Since K is Toeplitz, solving for the optimal sample weights costs O(sn + n^2).Source: §5.1 · p. 16
5.2. Error bounds in the Hilbert space setting
- Theorem 3 transfers the upper bounds from Theorems 1 and 2 to Pα,2; for α > 1, the corresponding result avoids an extra log(n) factor by inflating the leading constant.The cited earlier arbitrary-size bound includes a log(n) factor.Source: §5.2 · p. 17
5.3. Numerical results
- For n ≤ 2^12, P1,2 decays nearly as O(n^-1) under both optimal and equal sample weights; with optimal weights, values are consistently smaller and non-increasing.For n ≤ 2^7, ratios to the largest power-of-two sample size no greater than n remain at or below one with optimal weights; ratios to the smallest such size are greater than one but lower than with equal weights.Source: §5.3 · p. 17, Figure 6 · p. 17, Figure 7 · p. 18
6. Discussion and Future Work
For general n, Pα has a worse upper bound than for preferred sample sizes n = b^m, but n = λb^p can still achieve nearly O(n^-α) decay as p grows. Numerical experiments also show that optimal sample weights improve the cubature error comparison for arbitrary n, and the paper identifies further numerical and application settings to investigate.
6. Discussion and Future Work
- For n = λb^p with fixed integer λ, Pα's upper bound decays nearly as O(n^-α) as p → ∞, whereas the general-n bound is worse than for n = b^m.When λ/n stays bounded away from zero as n grows, the decay matches the general-n bound instead.Source: §6 · p. 18
- With α = 1, optimal sample weights give a smaller Pα,2 cubature error for arbitrary n than the full lattice of size b^m < n.The comparison concerns cases where the next full lattice is not attainable.Source: §6 · p. 19
- Future work could test arbitrary-n lattices on concrete integration problems and examine Pα and Pα,2 decay across a wider range of α values.Suggested applications include option pricing and other integration problems.Source: §6 · p. 19