Source-linked AI summary
Quasi-Monte Carlo Beyond Hardy-Krause II: $(1 + \varepsilon)n$ Samples Suffice
Ekene Ezeunala, Agastya Vibhuti Jha, Haotian Jiang
TL;DR
Bansal and Jiang’s beyond-Hardy–Krause integration guarantee left open whether it could be achieved with only eO_d(n) samples and time. This paper replaces transference with online Haar-thinning variants; (1 + ε)n samples suffice for that guarantee and for low-discrepancy point sequences.
Problem
The open gap was whether Bansal and Jiang’s beyond-Hardy–Krause integration guarantee could be achieved with only eO_d(n) samples and time.
Source: §1 · p. 4Method
The paper replaces transference with uniformly shifted and linear-feedback online Haar-thinning, using symmetry to establish uncorrelated low-order Haar discrepancies.
Source: §1.1 · p. 4, §1.2.1 · p. 5Results
(1 + ε)n i.i.d. samples suffice for the beyond-Hardy–Krause guarantee and low-discrepancy sequences that match the best explicit sequence bound up to a log n factor.
Source: §1.1 · pp. 4–5Takeaways & Limitations
The results show online Haar-thinning can address both integration error and point-sequence discrepancy under a near-linear sample budget.
Source: §1.1 · pp. 4–5The linear-feedback rule’s total vote weights may make its rejection probability invalid, but martingale analysis keeps it within [0, ε] with high probability.
Source: §1.2.4 · p. 7
Abstract
from arXiv · showhide
Numerical integration studies how well one can estimate the integral of a function $f$ over $[0,1)^d$ using $n$ sample points. The two classical methods, Monte Carlo (MC) and quasi-Monte Carlo (QMC), have complementary strengths and weaknesses, and a fundamental question is to design an approach that combines the benefits of both. Recently, building on the transference principle in discrepancy theory, Bansal and Jiang~\cite{BJ25a} gave a randomized QMC method that bridges MC and QMC guarantees using only i.i.d.\ samples. Their method also goes beyond the classical Koksma--Hlawka inequality: it achieves integration error $\widetilde{O}_d(\sigma_{\mathsf{SO}}(f)/n)$, where the smoothed-out variation $\sigma_{\mathsf{SO}}(f)$ can be substantially smaller than the Hardy--Krause variation that governs the classical bound. However, their algorithm requires $n^2$ i.i.d.\ samples as input, and this quadratic blowup is inherent to any method based on the transference principle. In this work, we bypass the quadratic blowup: for any constant $\varepsilon > 0$, we show that $(1+\varepsilon)n$ i.i.d.\ samples suffice to both obtain the beyond-Hardy--Krause guarantee of~\cite{BJ25a}, resolving an open problem posed there, and to produce low-discrepancy point sequences. Our algorithms are variants of the online Haar-thinning method of Dwivedi, Feldheim, Gurel-Gurevich, and Ramdas~\cite{DFG+19}.
1 Introduction
The paper replaces quadratic-sample transference with online Haar-thinning variants: with (1 + ε)n samples, they obtain a beyond-Hardy–Krause integration guarantee and low-discrepancy point sequences. The analysis uses uncorrelated Haar discrepancies to improve both integration-error and star-discrepancy bounds.
1 Introduction
- Monte Carlo offers random-sample flexibility but converges slowly, whereas QMC can converge faster yet may perform poorly for fast-varying functions and requires a fixed point set.QMC’s classical bound depends on Hardy–Krause variation, which can be much larger than the standard deviation for some functions.Source: §1 · p. 3
1.3 Further Related Work
- Point sequences require every prefix to have low star discrepancy, unlike point sets designed for one fixed n; the best known sequence bound is O_d(log^d n).The paper situates these constructions within work on point sets, sequences, and their numerical-integration applications.Source: §1 · p. 3, §1.3 · p. 7
1.1 Our Results
- (1 + ε)n i.i.d. samples suffice for the beyond-Hardy–Krause guarantee, while a separate algorithm produces low-discrepancy point sequences matching the best explicit sequence bound up to a log n factor.Both algorithms are online and never discard two consecutive samples.Source: §1.1 · pp. 4–5
1.2 Overview
- The overview presents online Haar-thinning variants as the alternative that achieves both the Bansal–Jiang integration guarantee and an improved star-discrepancy bound using (1 + ε)n samples.The variants are uniformly shifted for integration and linear-feedback for point sequences.Source: §1.1 · pp. 4–5, §1.2 · p. 5
1.2.1 The Bansal–Jiang QMC Method
- The Bansal–Jiang method uses transference to turn n^2 samples into n sets, but any transference-based method requires an initial pool of at least Ω(n^2) to bound its integration error by O(1/n).The paper instead considers online thinning, which processes samples as they arrive and decides whether to retain or discard each one.Source: §1.2.1 · p. 5, §1.2.2 · p. 6
1.2.2 The Haar-Thinning Strategy
- Haar-thinning’s rejection rule gives each Haar function negative drift O_ε(1/ℓ^d); from (1 + ε)n samples it retains n and achieves star discrepancy O_{d,ε}(log^{2d+1} n).This recovers the classical QMC error bound via the Koksma–Hlawka inequality.Source: §1.2.2 · p. 6
1.2.3 Beyond-Hardy–Krause via Uncorrelation of Haar Discrepancies
- Distinct low-order Haar discrepancies are uncorrelated despite their overlap; symmetry establishes this property, which supplies cancellation for the beyond-Hardy–Krause bound.A uniformly random shift lets the analysis pass from Haar–Besov control to smoothed-out variation.Source: §1.2.3 · pp. 6–7
1.2.4 Achieving Lower Star Discrepancy via Online Thinning
- Uncorrelation lets Haar discrepancies in an anchored-box decomposition add in an ℓ2 manner, improving the star-discrepancy bound to O_{d,ε}(log^{3d/2+1} n).The standard Haar-thinning strategy still falls short of the O_d(log^{d+1} n) target, so the paper introduces linear feedback.Source: §1.2.4 · p. 7
2 Preliminaries
The preliminaries establish the Haar and discrepancy notation and connect a shift-averaged Haar–Besov seminorm to smoothed-out variation. The online thinning framework retains samples through rejection sampling and bounds its oversampling.
2 Preliminaries
- The Haar functions form an orthogonal basis, and the paper uses projections onto functions up to or above a level ℓ.The notation Π≤ℓ and Π>ℓ also denotes the corresponding orthogonal projections; Nℓ is the size of Π≤ℓ.Source: §2 · p. 8
- The shift-averaged squared Haar–Besov seminorm is equivalent to the squared smoothed-out variation, which the analysis uses as a black-box translation of its Haar-basis bound.The Haar–Besov seminorm is central to the analysis, while σSO is introduced in.Source: §2 · pp. 8–9
- Anchored boxes define the star-discrepancy setting, while grid boxes have edges on a dyadic grid and continuous discrepancy is defined for measurable sets.Anchored boxes have the form [0, x1) × ··· × [0, xd).Source: §2 · p. 9
2.1 The (1 + ε)-Thinning Framework
- At each online-thinning step, rejection sampling selects a retained point with density μt, while the framework prevents consecutive rejections.The strategy starts with an empty set and uses a target density bounded between 1 − ε/2 and 1 + ε/2.Source: §2.1 · p. 9
- With high probability, an (1 + ε)-online thinning strategy uses at most (1 + 2ε)n samples, with failure probability at most exp(−Ω(εn)).The framework's proposition gives an at-most (1 + O(ε))n bound with high probability; the proof states the sharper threshold and failure probability.Source: §2.1 · p. 9
3 QMC Beyond Hardy–Krause via (1 + ε)n Samples
This section presents a uniformly shifted Haar-thinning approach that uses (1 + ε)n i.i.d. uniform samples to select n points with high probability for functions with finite σSO, and analyzes its error through low- and high-order Haar components. It bounds the high-order component using the scale of its basis functions and orthogonality.
3 QMC Beyond Hardy–Krause via (1 + ε)n Samples
- For any constant ε in (0, 1), the algorithm selects n samples from (1 + ε)n i.i.d. uniform inputs with high probability for every L2 function with finite σSO.It is online, never discards two consecutive samples, and processes each sample in O_d(log^d n) time; the section’s simpler proof uses a log^{2d} n factor, while log^d n is obtainable by combining with Section 4.Source: §3 · p. 10, §3.3 · p. 15
3.1 The Uniformly-Shifted Haar-Thinning Algorithm
- A uniform random shift converts error analysis for the shifted algorithm into an average over shifts of the unshifted Haar-thinning error on shifted functions.The shifted sample stream remains i.i.d. uniform, and the expected error is then bounded using the shift-averaged equivalence to σSO.Source: §3.1 · p. 11
3.2 Low-Order Haar Discrepancies Are Uncorrelated
- Distinct low-order Haar discrepancies are uncorrelated at every step; an involutive symmetry preserves the thinning distribution while flipping one discrepancy’s sign and leaving the other unchanged.The argument also yields a second-moment bound for each low-order Haar discrepancy, used in the low-order error analysis.Source: §3.2 · pp. 11, 14
3.3 Proof of Theorem 1.2
- The proof splits the shifted function’s integration error into low- and high-order Haar components, bounds them separately, and averages over the random shift to obtain Theorem 1.2’s error bound.The algorithm’s online, nonconsecutive-discard, sample-count, and per-sample time guarantees are verified as part of the theorem proof.Source: §3.3 · pp. 14–15
3.4.1 Bounds on the Low-Order Component
- The low-order error is controlled through a quadratic form of the discrepancy second-moment matrix, using uncorrelation and second-moment bounds.The component bounds are expressed in terms of the Haar–Besov seminorm.Source: §3.3 · p. 15, §3.4.1 · p. 16
3.4.2 Bounds on the High-Order Component
- For the high-order component, the target-density increments are orthogonal to Haar functions of order greater than ℓ, yielding the orthogonality-of-increments lemma.This part begins the high-order bound by setting h to the high-order Haar projection of g.Source: §3.4.2 · p. 16
- Every Haar term in Π>ℓg has a coordinate scale j_i ≥ ℓ + 1, giving its tensor basis function squared L2 norm at most 2^-ℓ.Orthogonality of the Haar basis and the definition of ∥g∥B are then used to bound ∥Π>ℓg∥2; the proof combines this with ε < 1 and ℓ = ⌈10 log2 n⌉.Source: §3.4.2 · p. 17
4 A (1 + ε)-Thinning Strategy for Od(logd+1 n) Star Discrepancy
This section develops an online Haar-thinning algorithm that uses (1 + ε)n samples to obtain low star discrepancy. Linear feedback and concentration bounds for Haar discrepancies support the guarantee.
4 A (1 + ε)-Thinning Strategy for O_d(log^{d+1} n) Star Discrepancy
- The section’s algorithmic goal is a low-star-discrepancy point sequence from only (1 + ε)n samples.The theorem also states that the algorithm is online, never discards two consecutive samples, and spends eO_{d,ε}(1) time per sample.Source: §4 · p. 17
4.1 The Linear-Feedback Haar-Thinning Algorithm
- Replacing the sign feedback with the Haar discrepancies themselves gives proportional negative drift, provided the target density remains within the thinning condition.The condition is |Φ_t(x)| ≤ B.Source: §4.1 · p. 18
4.2 Concentration for Linear Functions of Haar Discrepancies
- Linear combinations of Haar discrepancies are controlled by expressing them as centered martingale increments and applying Freedman’s inequality after bounding their quadratic variation and increments.The concentration lemma applies to every step, vector a, and ξ ≥ 0.Source: §4.2 · pp. 18–20
4.3 Wrapping Things Up
- With high probability, (1 + ε)n i.i.d. samples yield n retained points with star discrepancy O_{d,ε}(log^{d+1} n).The guarantee follows by bounding grid-box discrepancies and extending them to anchored boxes by approximation.Source: §4 · p. 17, §4.3 · pp. 21–22