Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
From MaRDI portal
Publication:876814
DOI10.1016/j.jco.2004.01.001zbMath1234.11101OpenAlexW2083171368MaRDI QIDQ876814
Publication date: 30 April 2007
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jco.2004.01.001
Approximate quadratures (41A55) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Numerical integration (65D30) Irregularities of distribution, discrepancy (11K38) Tilings in (n) dimensions (aspects of discrete geometry) (52C22) Continuous, (p)-adic and abstract analogues (11K41)
Related Items (36)
Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions ⋮ The weighted star discrepancy of Korobov’s $p$-sets ⋮ Correction of a proof in “A probabilistic result on the discrepancy of a hybrid-Monte Carlo sequence and applications” ⋮ Probabilistic Star Discrepancy Bounds for Double Infinite Random Matrices ⋮ Entropy, Randomization, Derandomization, and Discrepancy ⋮ The Inverse of the Star-Discrepancy Problem and the Generation of Pseudo-Random Numbers ⋮ The curse of dimensionality for the \(L_p\)-discrepancy with finite \(p\) ⋮ Some Results on the Complexity of Numerical Integration ⋮ An elementary proof of a lower bound for the inverse of the star discrepancy ⋮ Component-by-component construction of low-discrepancy point sets of small size ⋮ Asymptotic behavior of average \(L_p\)-discrepancies ⋮ Discrepancy of Digital Sequences: New Results on a Classical QMC Topic ⋮ Irregularities of Distributions and Extremal Sets in Combinatorial Complexity Theory ⋮ Probabilistic Lower Bounds for the Discrepancy of Latin Hypercube Samples ⋮ Tractability properties of the weighted star discrepancy of the Halton sequence ⋮ Covering numbers, dyadic chaining and discrepancy ⋮ The minimal \(k\)-dispersion of point sets in high dimensions ⋮ A note on the existence of sequences with small star discrepancy ⋮ Probabilistic discrepancy bound for Monte Carlo point sets ⋮ Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples ⋮ Tractability properties of the discrepancy in Orlicz norms ⋮ A lower bound for the dispersion on the torus ⋮ Tractability results for the weighted star-discrepancy ⋮ A lower bound for the discrepancy of a random point set ⋮ Tractability properties of the weighted star discrepancy ⋮ Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy ⋮ The randomized complexity of indefinite integration ⋮ Algorithmic construction of low-discrepancy point sets via dependent randomized rounding ⋮ On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence ⋮ A nonlocal functional promoting low-discrepancy point sets ⋮ On the discrepancy of jittered sampling ⋮ A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy ⋮ The VC-dimension of axis-parallel boxes on the torus ⋮ Bounds and constructions for the star-discrepancy via \(\delta\)-covers ⋮ Discrepancy Theory and Quasi-Monte Carlo Integration ⋮ Proof techniques in quasi-Monte Carlo theory
Cites Work
- Unnamed Item
- Sequences, discrepancies and applications
- Ecole d'été de probabilités de Saint-Flour XII - 1982
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
- Some open problems concerning the star-discrepancy
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- The inverse of the star-discrepancy depends linearly on the dimension
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
This page was built for publication: Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy
