Polynomial Uniform Convergence of Relative Frequencies to Probabilities

We define the concept of polynomial uniform convergence of relative frequencies to probabilities in the distribution-dependent context. Let Xn {O, l}n, let Pn be a probability distribution on Xn and let Fn C 2X,. be a family of events. The family {(Xn, Pn, Fn)}n l has the property of polynomial uniform convergence if the probability that the maximum difference (over Fn) between the relative frequency and the probabil(cid:173) ity of an event exceed a given positive e be at most 6 (0 6 1), when the sample on which the frequency is evaluated has size polynomial in n,l/e,l/b. Given at-sample (Xl, ...,Xt), let C t)(XI, ...,Xt) be the Vapnik-Chervonenkis dimension of the family {{x}, ...,xtl n f I f E Fn} and M(n, t) the expectation E(C t) It). Applications to distribution-dependent PAC learning are discussed.