Polynomial uniform convergence and polynomial-sample learnability
Alberto Bertoni, Paola Campadelli, Anna Morpurgo, Sandra Panizza · 1992
In this work we study the relationship between PAC learning and the property of uniform convergence. We define the concept of polynomial uniform convergence of relative frequencies to probabilities in the distribution–dependent context. Let Xn = (0,1)n, let Pn be a probability distribution on Xn and let Fn⊂2xn be a class of events. The family {(Xn, Pn, Fn)}n≥1 is said to be polynomially uniformly convergent if, for all n, the probability that the maximum difference (over Fn) between the relative frequency and probability of an event exceed a given positive ε is at most δ (0 < δ < 1), when the sample on which the frequency is evaluated has size polynomial in n, 1/ε, 1/δ. Given at-sample(x1,…,xt), let Cn(t)(x1,…,xt) be the Vapnik-Chervonenkis dimension (VCdim) of the set (x1,…xt ∩ f | f ϵ Fn and M(n,t) the expectation E(Cn(t)/t). The results we obtain are: