Robust high-dimensional integration using medians of coarsely scrambled Sobol' sequences

Section 1. Introduction.

• QMC uses low-discrepancy point sets, but boundary points such as the origin challenge integrands undefined at the boundary.Classical variation-based error results are typically formulated for integrands on [0, 1)^s.Source: §1 · p. 1
• Classical RQMC error bounds can grow exponentially in s, while general convergence rates do not exceed O(N^-3/2).RQMC randomization also yields unbiased estimates and statistical error assessment while avoiding boundary evaluations almost surely.Source: §1 · pp. 1–2
• Coarse scrambling applies randomization in a base determined by Sobol' generating polynomials, reducing the maximal gain coefficient from at least 2^s-1 to O(log s).The median trick combines independent RQMC estimates to reach rates beyond O(N^-3/2) without user-specified smoothness parameters.Source: §1 · p. 2

Section 3.1–3.4

• For L2 integrands, reduced GNS make the maximal gain coefficient uniformly bounded in s, giving RMSE O(N^-1/2) with a dimension-independent constant.The later Haar-space bounds are uniform in s when the integrand's ANOVA components satisfy the stated corollary assumptions.Source: §1 · p. 2

Section 3.2

• For Lp integrands with p in (1, 2), the median of R coarsely scrambled estimates achieves error O(N^-1+1/p) with high probability.The failure probability decays exponentially in R.Source: §1 · p. 2

Section 3.3–3.4

• For Haar wavelet integrands with alpha_p > 0, the median error is O(N^-alpha_p-1/2+epsilon), improving to O(N^-r-alpha_p-1/2+epsilon) for qualifying mixed derivatives.Both bounds hold for any epsilon > 0; their dimension-uniform versions require the respective ANOVA assumptions.Source: §1 · p. 2

2. Notation and background.

• The preliminaries fix finite-field, digit-vector, Lp, and mixed-derivative notation used in the later analysis.They also define componentwise vector inequalities and sparse b-adic expansions.Source: §2 · p. 3

2.1. Digital nets and block affine matrix scrambling.

• A generalized Niederreiter sequence uses pairwise-coprime base polynomials; coarse scrambling applies a block affine randomization in the base set by their degrees.The scrambled points are uniform on [0, 1)^s for each fixed input and lie in (0, 1)^s almost surely.Source: §2.1 · pp. 4–5

2.2. Walsh expansion and dual net.

• The Walsh functions form a complete orthonormal basis for L2, and the RMSE lemma expresses coarsely scrambled estimates through Walsh coefficients.The proof does not require pointwise convergence of the Walsh expansion, so it also applies to discontinuous integrands.Source: §2.2 · p. 5

2.3. Haar wavelet spaces.

• Haar wavelet spaces provide the regularity framework, with alpha_p = alpha - (1/p - 1/2)+ and the analysis assuming alpha_p > 0.The section introduces the median estimator based on reduced GNS for convergence analysis in these spaces.Source: §2.3 · p. 7, §3 · p. 7

3. Main results.

• Each coarsely scrambled estimate is unbiased, and the median RQMC estimator combines independent realizations.The median trick amplifies the probability of an accurate estimate.Source: §3 · p. 8

3.2. Error bounds for Lp integrands with p ∈(1, 2).

• For p ∈ (1, 2), the median estimator has a high-probability error bound for f ∈ Lp when S is a (log n)^(1+β)-reduced GNS with β > 0.The proof uses truncation purely as an analytical tool, never executing it in the algorithm.Source: §3.2 · p. 10

3.3. Error bounds for Hwav,α,s,p,q integrands.

• When α_p = α − (1/p − 1/2)_+ > 0, Haar wavelet integrands have high-probability error O(N^-α_p-1/2+ε), with a dimension-independent bound under suitable ANOVA conditions.The bound holds for every ε > 0; the dimension-independent result assumes conditions on the relative ANOVA component norms.Source: §3.3 · pp. 13–14

3.4. Error bounds for integrands with Hwav,α,s,p,q derivatives.

• For integrands with Hwav,α,s,p,q derivatives of order r ≥ 1, the section defines the derivative-based function space for weakly differentiable integrands.It treats either α = 0 and p = q = 2, or α_p > 0, where the space embeds into the mixed Sobolev space.Source: §3.4 · p. 15
• For nonzero f ∈ Hmix,r,α,s,p,q, Theorem 3.15 reports failure probability decaying exponentially in odd replicate count R when S is a (log n)^(1+β)-reduced GNS, β > 0, and δ ∈ (0, 1/8).Source: §3.4 · pp. 16–17
• The error bound is independent of s and m under the corollary’s stated ANOVA-weight condition.For every ε > 0, the bound scales as b^(r+α_p+1/2−ε)m δ^(r+α_p+1/2) times the integrand norm, with a constant independent of s and m.Source: §3.4 · p. 17
• The numerical comparison evaluates reduced and full coarse scrambling against linearly scrambled Sobol’, HRD, and Monte Carlo.The RQMC methods use medians of 15 randomized replicates with 2^m points each; Monte Carlo uses the mean of 15·2^m independent uniform samples.Source: §4 · p. 17

4.1. Smooth integrands.

• Reversing coordinate order leaves HRD and MC unchanged but degrades the Sobol-based methods, with LS losing its leading position.The more important coordinates are then assigned larger-degree base polynomials.Source: §4.1 · pp. 18–19, Figure 2 · p. 18

4.2. Nonsmooth integrands.

• For the three integrands, all four RQMC methods significantly outperform MC and achieve predicted convergence rates; the three Sobol’-based methods perform similarly, whereas HRD shows slightly larger errors.Source: §4.2 · p. 19

• Figure 3 plots RMSEs for g1, g2, and g3, with each value computed from 448 independent replicates.Source: Figure 3 · p. 20
• The Hankel random design has maximal gain coefficient 1, so the theorems hold with Cβ replaced by 1.Source: §5 · p. 20
• Coarsely scrambled Sobol’ sequences consistently outperform the Hankel random design when coordinates are ordered in descending importance.The authors link explaining this advantage to the equidistribution property of Sobol’ sequences.Source: §5 · p. 20
• Many low-frequency terms vanish by equidistribution and could be excluded from the union bound, but fully exploiting this remains future work.The threshold T_u used in the proof is conservative.Source: §5 · p. 20
• For f in Hwav,α,s,p,q, the probabilistic bound yields RMSE O(b^-(α_p+1/2−ε)m) when R ≥ 4α_p + 2.Mean absolute error bounds can be obtained analogously.Source: §5 · p. 20

• Conditioning on the random matrices reduces the proof to fixed M, after which the Walsh-polynomial case is established first.Source: Appendix A · p. 21
• For a Walsh polynomial, the integration error is a sum of Walsh coefficients weighted by scrambling terms and indicators of membership in the random dual net.Source: Appendix A · p. 21
• Orthonormality of the scrambling terms in L2(D) gives the squared-error expectation for Walsh polynomials.Source: Appendix A · p. 21
• Approximating a general L2 integrand by Walsh polynomials, using uniformity and Jensen’s inequality, and passing to the limit via Parseval proves the result.Source: Appendix A · p. 21

• For α_p > 0 and q ≤ 2, Jensen’s inequality with λ = q/2 ≤ 1 handles the norm comparison.Source: Appendix B · p. 22
• For α_p > 0 and q > 2, Hölder’s inequality handles the comparison; together the cases give (2.8).When p > 2, (2.6) supplies the norm inclusion needed for (2.7) in both cases.Source: Appendix B · p. 22

• For ℓ = 0, Q0 and P0 are the integration projection and Λ0 = {0}, so the claim is immediate.Source: Appendix C · p. 22
• For ℓ ≥ 1, Walsh functions in the stated index range lie in ker Pℓ−1 and ran Pℓ, establishing Wℓ ⊆ ran(Qℓ).Source: Appendix C · p. 22
• The inclusion is equality because both spaces have dimension b^ℓ − b^(ℓ−1); tensor products yield the multidimensional result.Source: Appendix C · p. 22

Appendix D. Proof of Lemma 3.13.

• The proof of Lemma 3.13 applies the one-dimensional estimate with b replaced by b1/c.Source: Appendix D · pp. 22–23
• The counting argument splits digit expansions into cases with at most r nonzero digits and with more, yielding a constant C0 depending on r and αp.For the latter case, it uses S(h) ≥ (r + αp)q + r and counts possible digit positions and values.Source: Appendix D · pp. 22–23
• For each fixed q, the proof counts choices for the first q digit positions and the remaining r nonzero positions, then sums over q.The resulting count is bounded using constants depending on r and c, completing the one-dimensional estimate.Source: Appendix D · p. 23

Appendix E. Proof of Lemma 3.14.

• The appendix generalizes [42, Theorem 2.5] to Sobolev space settings.Source: Appendix E · p. 24
• It defines iterated integrals of conjugate Walsh functions and proves a one-dimensional coefficient identity through repeated integration by parts.The multidimensional argument applies that identity successively, using almost-everywhere section regularity of mixed Sobolev functions.Source: Appendix E · pp. 24–25
• For almost every fixed set of other coordinates, the relevant sections and their derivatives belong to W^n,1, with weak derivatives given by sections of mixed partials.Source: Appendix E · p. 25
• The Walsh-block argument uses periodicity and piecewise constancy to show that the indicated Haar coefficients vanish, with orthogonality completing the conclusion.Source: Appendix E · pp. 25–27
• The proof of Lemma E.4 treats q > 2 separately and then enlarges its constant to cover q in [1, 2].For q > 2, it chooses z > 0 so that (1+z)^(1+q′)b^(-2q′αp) < 1.Source: Appendix E · pp. 27–29
• The proof of Lemma 3.14 splits upper parts into M ≤ T and M > T, counts admissible upper parts by M, and sums their contributions.For M ≤ T, it applies Lemma E.4 to blocks outside the specified set; for M > T, every such block lies outside it.Source: Appendix E · pp. 29–30
• After bounding the contributions, the proof sums over τu and obtains a bound with a sufficiently large constant Cr,αp,q.Source: Appendix E · p. 30

Appendix F. Proof of Corollary 3.16.

• The sum ψr,α,s,p,q,γ(m) is bounded by Cε,Υ,r,α,p,q b^εm, with the constant independent of s and m.Source: Appendix F · p. 31
• The proof sets x = (r + αp)m for m ≥ 0 and uses an expansion of En(x) in its bound.Source: Appendix F · p. 31
• The quantities are summable over all finite subsets u ⊆ N, which the proof uses to conclude finiteness of ψ′.Source: Appendix F · p. 31