{
  "id": "1010.3162",
  "version": "v1",
  "published": "2010-10-15T13:39:05.000Z",
  "updated": "2010-10-15T13:39:05.000Z",
  "title": "Uniform convergence of Vapnik--Chervonenkis classes under ergodic sampling",
  "authors": [
    "Terrence M. Adams",
    "Andrew B. Nobel"
  ],
  "comment": "Published in at http://dx.doi.org/10.1214/09-AOP511 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)",
  "journal": "Annals of Probability 2010, Vol. 38, No. 4, 1345-1367",
  "doi": "10.1214/09-AOP511",
  "categories": [
    "math.PR"
  ],
  "abstract": "We show that if $\\mathcal{X}$ is a complete separable metric space and $\\mathcal{C}$ is a countable family of Borel subsets of $\\mathcal{X}$ with finite VC dimension, then, for every stationary ergodic process with values in $\\mathcal{X}$, the relative frequencies of sets $C\\in\\mathcal{C}$ converge uniformly to their limiting probabilities. Beyond ergodicity, no assumptions are imposed on the sampling process, and no regularity conditions are imposed on the elements of $\\mathcal{C}$. The result extends existing work of Vapnik and Chervonenkis, among others, who have studied uniform convergence for i.i.d. and strongly mixing processes. Our method of proof is new and direct: it does not rely on symmetrization techniques, probability inequalities or mixing conditions. The uniform convergence of relative frequencies for VC-major and VC-graph classes of functions under ergodic sampling is established as a corollary of the basic result for sets.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-10-15T13:39:05.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "uniform convergence",
      "vapnik-chervonenkis classes",
      "ergodic sampling",
      "complete separable metric space",
      "result extends existing work"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1010.3162A"
    }
  }
}