The inverse of the star-discrepancy depends linearly on the dimension
From MaRDI portal
Publication:4522902
Let \(\text{disc}_\infty^* (\underline{t}_1,\dots, \underline{t}_n)\) denote the star-discrepancy of an \(n\)-element point set \(\omega\equiv \{\underline{t}_1,\dots, \underline{t}_n\} \subseteq [0,1]^d\) and let \(\text{disc}_\infty^* (n,d)= \inf_\omega \text{disc}_\infty^* (\underline{t}_1,\dots, \underline{t}_n)\). In the classical theory of irregularities of distribution various upper bounds for \(\text{disc}_\infty^* (n,d)\) are known for fixed \(d\). For instance, Roth's bound \(\text{disc}_\infty^* (n,d)= O(N^{-1} (\log)^{\frac{d-1}{2}})\) [with an implied \(O\)-constant depending on \(d\)] or R. Baker's refinement of Roth's bound. In the present paper the authors consider \(n\) and \(d\) as variables and prove the remarkable and very interesting upper bound \[ \text{disc}_\infty^* (n,d)\leq cd^{1/2} n^{-1/2} \quad\text{for all }n,d= 1,2,\dots, \] with an unknown multiplicative factor \(c\). Furthermore it is shown that the dependence on \(d\) cannot be improved. The proof follows from deep results of the theory of empirical processes. In particular, a result of Talagrand (1994) is used in combination with a result of \textit{D. Haussler} [J. Comb. Theory, Ser. A 69, 217-232 (1995; Zbl 0818.60005)] and some facts on the Vapnik-Cervonenkis dimension. Of course, the proof is non-constructive since it is probabilistic. Furthermore, the authors establish an explicit value for the constant \(c\) and obtain extensions to the \(L^p\)-discrepancy.
Recommendations
- The supremum norm of the discrepancy function: recent results and connections
- Dichotomy results for the \(L^1\) norm of the discrepancy function
- On lower bounds for the \(L_2\)-discrepancy
- Irregularities of distributions and extremal sets in combinatorial complexity theory
- Bounds and constructions for the star-discrepancy via \(\delta\)-covers
- Exact order of extreme \(L_p\) discrepancy of infinite sequences in arbitrary dimension
- Probabilistic discrepancy bound for Monte Carlo point sets
- DYADIC SHIFT RANDOMIZATION IN CLASSICAL DISCREPANCY THEORY
- Gaussian limits for discrepancies. I: Asymptotic results
- 1. On some recent developments in uniform distribution and discrepancy theory
Cited in
(92)- Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
- An algorithm to compute bounds for the star discrepancy
- Some open problems concerning the star-discrepancy
- Open problems for tractability of multivariate integration.
- Optimal jittered sampling for two points in the unit square
- Tractability properties of the weighted star discrepancy of the Halton sequence
- The minimal \(k\)-dispersion of point sets in high dimensions
- Tractability properties of the weighted star discrepancy of regular grids
- Point sets on the sphere \(\mathbb{S}^{2}\) with small spherical cap discrepancy
- On the inverse of the discrepancy for infinite dimensional infinite sequences
- Tractability properties of the discrepancy in Orlicz norms
- On an explicit lower bound for the star discrepancy in three dimensions
- A lower bound for the dispersion on the torus
- Secure pseudorandom bit generators and point sets with low star-discrepancy
- Discrepancy of stratified samples from partitions of the unit cube
- The VC-dimension of axis-parallel boxes on the torus
- On a partition with a lower expected \(\mathcal{L}_2\)-discrepancy than classical jittered sampling
- Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions
- On negative dependence properties of Latin hypercube samples and scrambled nets
- Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples
- Tractability results for the weighted star-discrepancy
- A lower bound for the discrepancy of a random point set
- On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence
- A nonlocal functional promoting low-discrepancy point sets
- Proof techniques in quasi-Monte Carlo theory
- Minimizing the \(L_{2}\) and \(L_{\infty}\) star discrepancies of a single point in the unit hypercube
- Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series
- A note on the existence of sequences with small star discrepancy
- Tractability properties of the weighted star discrepancy
- Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
- Bounds and constructions for the star-discrepancy via \(\delta\)-covers
- An elementary proof of a lower bound for the inverse of the star discrepancy
- The BMO-discrepancy suffers from the curse of dimensionality
- Quasi-Monte Carlo methods for high-dimensional integration: the standard (weighted Hilbert space) setting and beyond
- The supremum norm of the discrepancy function: recent results and connections
- Probabilistic star discrepancy bounds for double infinite random matrices
- The inverse of the star-discrepancy problem and the generation of pseudo-random numbers
- Some results on the complexity of numerical integration
- Discrepancy estimates for acceptance-rejection samplers using stratified inputs
- Correction of a proof in “A probabilistic result on the discrepancy of a hybrid-Monte Carlo sequence and applications”
- The weighted star discrepancy of Korobov’s p-sets
- DYADIC SHIFT RANDOMIZATION IN CLASSICAL DISCREPANCY THEORY
- Component-by-component construction of low-discrepancy point sets of small size
- Introducing Quasirandomness to Computer Science
- Asymptotic behavior of average L_p-discrepancies
- Irregularities of distributions and extremal sets in combinatorial complexity theory
- Probabilistic lower bounds for the discrepancy of Latin hypercube samples
- An upper bound of the minimal dispersion via delta covers
- On tractability of weighted integration over bounded and unbounded regions in ℝ^{𝕤}
- On strong tractability of weighted multivariate integration
- A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
- Improving a constant in high-dimensional discrepancy estimates
- A sharp discrepancy bound for jittered sampling
- Discrepancy of Digital Sequences: New Results on a Classical QMC Topic
- Discrepancy theory and quasi-Monte Carlo integration
- Calculation of discrepancy measures and applications
- Digital inversive vectors can achieve polynomial tractability for the weighted star discrepancy and for multivariate integration
- Entropy, Randomization, Derandomization, and Discrepancy
- Probabilistic discrepancy bound for Monte Carlo point sets
- The randomized complexity of indefinite integration
- Functions of bounded variation, signed measures, and a general Koksma–Hlawka inequality
- Intractability results for integration and discrepancy
- On the discrepancy of jittered sampling
- The curse of dimensionality for the \(L_p\)-discrepancy with finite \(p\)
- Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series
- On the information complexity for integration in subspaces of the Wiener algebra
- Covering numbers, dyadic chaining and discrepancy
- Bounds for the weighted L^p discrepancy and tractability of integration
- Tractability of sampling recovery on unweighted function classes
- Upper bound estimation of star discrepancy based on Hilbert space filling curve stratified sampling and its applications
- Hammersley point sets and inverse of star-discrepancy
- Tractability results for integration in subspaces of the Wiener algebra
- Constructing optimal star discrepancy sets
- New bounds for the extreme and the star discrepancy of double-infinite matrices
- Optimal algorithms for numerical integration: recent results and open problems
- On the expected \(\mathcal{L}_2\)-discrepancy of stratified samples from parallel lines
- The \(L_p\)-discrepancy for finite \(p>1\) suffers from the curse of dimensionality
- Conditions for tractability of the weighted L_p-discrepancy and integration in non-homogeneous tensor product spaces
- Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
- The L₁-Discrepancy with Nonnegative Weights Suffers from the Curse of Dimensionality
- Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy
- Bounded independence for the inverse star discrepancy
- Approximation of functions: optimal sampling and complexity
- Upper bounds for generalized L_p-discrepancy of random points
- The star discrepancy of a union of randomly digitally shifted Korobov polynomial lattice point sets depends polynomially on the dimension
- The star discrepancy of a union of randomly shifted Korobov lattice point sets depends polynomially on the dimension
- Minimal dispersion on the sphere
- The L\log L-Luxemburg Discrepancy for Nonnegative Weights Suffers from the Curse of Dimensionality
- Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
- On the tractability of multivariate integration and approximation by neural networks
- Tractability of quasilinear problems. I: General results
- An inequality for differences of distribution functions
This page was built for publication: The inverse of the star-discrepancy depends linearly on the dimension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4522902)
