A Note on VC-Dimension and Measure of Sets of Reals

DOI10.1017/S096354830000434XzbMath0971.03042OpenAlexW2131581266MaRDI QIDQ2709844

Leonid Gurvits, Shai Ben-David

Publication date: 30 October 2001

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s096354830000434x

zbMATH Keywords

combinatorial complexityPAC learningLebesgue measure\(\sigma\)-idealsrandom eventclasses with infinite VC-dimensionideals over the reals

Mathematics Subject Classification ID

Computational learning theory (68Q32) Real- or complex-valued set functions (28A10) Descriptive set theory (03E15) Classes of sets (Borel fields, (sigma)-rings, etc.), measurable sets, Suslin sets, analytic sets (28A05) Baire category, Baire spaces (54E52) Extremal set theory (05D05) Probabilistic measure theory (60A10) Other combinatorial set theory (03E05)

Related Items

On ordinal VC-dimension and some notions of complexity