2015/11/23 by Alf Onshuus, Onshuus, Alf, Adolfo J. Quiróz +1
Computer Science · Mathematics · #FOS: Mathematics #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Statistical Methods and Inference #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.1511.07098
openalex publication_date 2015/11/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is shown how tools from the area of Model Theory, specifically from the Theory of o-minimality, can be used to prove that a class of functions is VC-subgraph (in the sense of Dudley, 1987), and therefore satisfies a uniform polynomial metric entropy bound. We give examples where the use of these methods significantly improves the existing metric entropy bounds. The methods proposed here can be applied to finite dimensional parametric families of functions without the need for the parameters to live in a compact set, as is sometimes required in theorems that produce similar entropy bounds (for instance Theorem 19.7 of van der Vaart, 1998).