2010/07/17 by Terrence Adams, Andrew B. Nobel, Adams, Terrence M. +1 · 2 citations
Computer Science · Economics, Econometrics and Finance · Mathematics · #60F15 (primary) #60G10 #62G05 (secondary) #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Machine Learning and Algorithms #Mathematical Dynamics and Fractals #Probability (math.PR) #Statistical Methods and Inference #Statistics Theory (math.ST) #Stochastic processes and financial applications
paper · pdf · doi:10.48550/arxiv.1007.2964
openalex publication_date 2010/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let F be a family of Borel measurable functions on a complete separable\nmetric space. The gap (or fat-shattering) dimension of F is a combinatorial\nquantity that measures the extent to which functions f in F can separate finite\nsets of points at a predefined resolution gamma > 0. We establish a connection\nbetween the gap dimension of F and the uniform convergence of its sample\naverages under ergodic sampling. In particular, we show that if the gap\ndimension of F at resolution gamma > 0 is finite, then for every ergodic\nprocess the sample averages of functions in F are eventually within 10 gamma of\ntheir limiting expectations uniformly over the class F. If the gap dimension of\nF is finite for every resolution gamma > 0 then the sample averages of\nfunctions in F converge uniformly to their limiting expectations. We assume\nonly that F is uniformly bounded and countable (or countably approximable). No\nsmoothness conditions are placed on F, and no assumptions beyond ergodicity are\nplaced on the sampling processes. Our results extend existing work for i.i.d.\nprocesses.\n