Polynomial Uniform Convergence of Relative Frequencies to Probabilities
Alberto Bertoni, Paola Campadelli, Anna Morpurgo, Sandra Panizza · 1991
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-ity of an event exceed a given positive e be at most 6 (0 0 such that M(n, t) = O(n/t!3). Applications to distribution-dependent PAC learning are discussed. 1