Metric Entropy estimation using o-minimality Theory

Type: Preprint
Publication Date: 2015-01-01
Citations: 0
DOI: https://doi.org/10.48550/arxiv.1511.07098

Abstract

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).

Locations

  • arXiv (Cornell University)
  • DataCite API
Correction' should be added to Lemma  and Theorem . Correction' should be added to Lemma  and Theorem .
A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content. A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
We recast the problem of calculating Vapnik-Chervonenkis (VC) density into one of counting types, and thereby calculate bounds (often optimal) on the VC density for some weakly o-minimal, weakly quasi-o-minimal, … We recast the problem of calculating Vapnik-Chervonenkis (VC) density into one of counting types, and thereby calculate bounds (often optimal) on the VC density for some weakly o-minimal, weakly quasi-o-minimal, and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P"> <mml:semantics> <mml:mi>P</mml:mi> <mml:annotation encoding="application/x-tex">P</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-minimal theories.
numbers with exponentiation is model complete. When we combine this with Hovanskii's finiteness theorem [9], it follows that the real exponential field is o-minimal. In o-minimal expansions of the real … numbers with exponentiation is model complete. When we combine this with Hovanskii's finiteness theorem [9], it follows that the real exponential field is o-minimal. In o-minimal expansions of the real field the definable subsets of R' share many of the nice structural properties of semialgebraic sets. For example, definable subsets have only finitely many connected components, definable sets can be stratified and triangulated, and continuous definable maps are piecewise trivial (see [5]). In this paper we will prove a quantifier elimination result for the real field augmented by exponentiation and all restricted analytic functions, and use this result to obtain o-minimality. We were led to this while studying work of Ressayre [13] and several of his ideas emerge here in simplified form. However, our treatment is formally independent of the results of [16], [17], [9], and [13].
Abstract The empirical measure P n for independent sampling on a distribution P is formed by placing mass n −1 at each of the first n sample points. In this … Abstract The empirical measure P n for independent sampling on a distribution P is formed by placing mass n −1 at each of the first n sample points. In this paper, n ½ ( P n − P ) is regarded as a stochastic process indexed by a family of square integrable functions. A functional central limit theorem is proved for this process. The statement of this theorem involves a new form of combinatorial entropy, definable for classes of square integrable functions.
Abstract Every o-minimal expansion of the real field has an o-minimal expansion in which the solutions to Pfaffian equations with definable C 1 coefficients are definable. Abstract Every o-minimal expansion of the real field has an o-minimal expansion in which the solutions to Pfaffian equations with definable C 1 coefficients are definable.
A class 𝒮 of subsets of a set X is called a Vapnik-Cervonenkis class if the growth of the function Δ 𝒮 :r→ Sup {|A∩||A⊂X,|A|=r} is polynomial ; these classes … A class 𝒮 of subsets of a set X is called a Vapnik-Cervonenkis class if the growth of the function Δ 𝒮 :r→ Sup {|A∩||A⊂X,|A|=r} is polynomial ; these classes have proved to be useful in Statistics and Probability (see for example Vapnik, Cervonenkis [V.N. Vapnik, A.YA. Cervonenkis, Theor. Prob. Appl., 16 (1971), 264-280], Dudley [R.M. Dudley, Ann. of Prob., 6 (1978), 899-929]).
We study the Vapnik–Chervonenkis (VC) density of definable families in certain stable first-order theories. In particular, we obtain uniform bounds on the VC density of definable families in finite U-rank … We study the Vapnik–Chervonenkis (VC) density of definable families in certain stable first-order theories. In particular, we obtain uniform bounds on the VC density of definable families in finite U-rank theories without the finite cover property, and we characterize those abelian groups for which there exist uniform bounds on the VC density of definable families.