A sufficient condition for polynomial distribution-dependent learnability Original Research Article

We investigate upper bounds on the sample-size sufficient for ‘solid’ learnability with respect to a probability distribution. Extending analysis of Ben-David et al. (1989, 1995) and Bendek and Itai (1991) we obtain a sufficient condition for feasible (polynomially bounded) sample-size bounds for distribution-specific (solid) learnability.