Polynomial uniform convergence and polynomial-sample learnability

ABSTRACT

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⊂2^xn 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 &egr; is at most &dgr; (0 < &dgr; < 1), when the sample on which the frequency is evaluated has size polynomial in n, 1/&egr;, 1/&dgr;. Given at-sample(x1,…,xt), let Cn(t)(x1,…,xt) be the Vapnik-Chervonenkis dimension (VCdim) of the set (x1,…xt ∩ f | f e Fn and M(n,t) the expectation E(Cn(t)/t). The results we obtain are: 1. (Xn,Pn, Fn)n≥1 is polynomially uniformly convergent iff there exists &bgr; > 0 such that M(n,t)=O(n/t&bgr;). 2. The family {(Xn, Fn)}n≥1 is polynomially uniformly convergent for all probability distributions Pn on Xn iff VCdim(Fn) is bounded by a polynomial p(n) iff (Xn, Fn)≥1 is polynomial–sample learnable. 3. If (Xn, Pn, Fn) is polynomially uniformly convergent then (Xn, Pn, Fn)≥1 is polynomial–sample learnable, but there exist polynomial–sample learnable families (Xn, Pn, Fn)≥1 which do not satisfy the property of polynomial uniform convergence.

REFERENCES

• BeIt88: Gyora M. Benedek , Alon Itai, Learnability by fixed distributions, Proceedings of the first annual workshop on Computational learning theory, p.80-90, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• BeCaMoPa92: A. Bertoni, P. Campadelli, A. Morpurgo, S. Panizza. "Polynomial Uniform Convergence of Relative Frequencies to Probabilities". Advances in Neural Information Processing Systems d, Morgan Kaufmann, San Mateo, CA, (1992), 904-911.
• BlEhHaWa89: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• Pa91: S. Panizza. "Apprendimento PAC con distribuzione di probabilit/~ fissata". Test di Laurea, Universita degli studi di Milano (Italy), Dipartimento di Scienze dell'Informazione, A.A. 1990-91.
• Va84: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• VaCh71: V.N. Vapnik, A.Ya. Chervonenkis. "On the uniform convergence of relative frequencies of events to their probabilities''. Theory of Prob. and its Appl. 16 (2), (1971), 265-280.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Theory, Verification