Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy

DOI10.1016/J.JCO.2004.01.001zbMATH Open1234.11101OpenAlexW2083171368MaRDI QIDQ876814FDOQ876814

Authors: Aicke Hinrichs 

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

Recommendations

• Bounds and constructions for the star-discrepancy via \(\delta\)-covers
• The star number of coverings of space with convex bodies
• Covering numbers, dyadic chaining and discrepancy
• On countable star-covering properties
• scientific article; zbMATH DE number 1126974
• Bounds for covering numbers
• On exact coverings of the integers
• Countability and star covering properties
• On the Hadwiger numbers of starlike disks
• Remarks on countability and star covering properties

zbMATH Keywords

discrepancycovering numbersVapnik-Červonenkis classes

Mathematics Subject Classification ID

Numerical integration (65D30) Approximate quadratures (41A55) Irregularities of distribution, discrepancy (11K38) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Tilings in (n) dimensions (aspects of discrete geometry) (52C22) Continuous, (p)-adic and abstract analogues (11K41)

Cites Work

• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Title not available (Why is that?)
• Sequences, discrepancies and applications
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• The inverse of the star-discrepancy depends linearly on the dimension
• Ecole d'été de probabilités de Saint-Flour XII - 1982
• Some open problems concerning the star-discrepancy

Cited In (38)

• Probabilistic star discrepancy bounds for double infinite random matrices
• The minimal \(k\)-dispersion of point sets in high dimensions
• On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence
• Tractability properties of the discrepancy in Orlicz norms
• Tractability properties of the weighted star discrepancy
• Irregularities of Distributions and Extremal Sets in Combinatorial Complexity Theory
• Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions
• Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
• Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples
• Low-discrepancy point sets for non-uniform measures
• Asymptotic behavior of average \(L_p\)-discrepancies
• Covering numbers, dyadic chaining and discrepancy
• A lower bound for the dispersion on the torus
• A lower bound for the discrepancy of a random point set
• The randomized complexity of indefinite integration
• Probabilistic discrepancy bound for Monte Carlo point sets
• On the discrepancy of jittered sampling
• A note on the existence of sequences with small star discrepancy
• The VC-dimension of axis-parallel boxes on the torus
• The weighted star discrepancy of Korobov’s $p$-sets
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• Correction of a proof in “A probabilistic result on the discrepancy of a hybrid-Monte Carlo sequence and applications”
• Probabilistic Lower Bounds for the Discrepancy of Latin Hypercube Samples
• Proof techniques in quasi-Monte Carlo theory
• Discrepancy theory and quasi-Monte Carlo integration
• Bounds and constructions for the star-discrepancy via \(\delta\)-covers
• An elementary proof of a lower bound for the inverse of the star discrepancy
• A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
• Bounds for the average \(L^p\)-extreme and the \(L^\infty\)-extreme discrepancy
• Component-by-component construction of low-discrepancy point sets of small size
• 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\)
• Entropy, Randomization, Derandomization, and Discrepancy
• Some results on the complexity of numerical integration
• Tractability properties of the weighted star discrepancy of the Halton sequence
• Discrepancy of Digital Sequences: New Results on a Classical QMC Topic
• A nonlocal functional promoting low-discrepancy point sets
• Tractability results for the weighted star-discrepancy

This page was built for publication: Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q876814)