Covering Numbers for Real-Valued Function Classes

We find tight upper and lower bounds on the growth rate for the covering numbers of functions of bounded variation in the L 1 metric in terms of all the relevant constants. We also find upper and lower bounds on covering numbers for general function classes over the family of L 1 (dP ) metrics, in terms of a scale-sensitive combinatorial dimension of the function class. 1 Introduction Covering numbers have been studied extensively in a variety of literature dating back to the work of Kolmogorov [10, 12]. They play a central role in a number of areas in information theory and statistics, including density estimation, empirical processes, and machine learning (see, for example, [4, 16, 8]). Let F be a subset of a metric space (X ; ae). For a given ffl ? 0, the metric covering number N (ffl; F ; ae) is defined as the smallest number of sets of radius ffl whose union contains F . (We omit ae if the context is clear.) We first find bounds on the covering numbers of functions of bounded va..