Polynomial Uniform Convergence and Polynomial-Sample Learnability

TitlePolynomial Uniform Convergence and Polynomial-Sample Learnability
Publication TypeTechnical Report
Year of Publication1992
AuthorsBertoni, A., Campadelli P., Morpurgo A., & Panizza S.
Other Numbers782

In the PAC model, polynomial-sample learnability in the distribution dependent framework has been characterized in terms of minimum cardinality of epsilon-covers. In this paper we propose another approach to the problem by investigating the relationship between polynomial-sample learnability and uniform convergence, in analogy to what was done for the distribution free setting. First of all, we introduce the notion of polynomial uniform convergence, giving a characterization for it in terms of an entropic measure, then we study its relationship with polynomial- sample learnability. We show that, contrarily to what happens in the distribution independent setting, polynomial uniform convergence is a sufficient but not necessary condition for polynomial-sample learnability.

Bibliographic Notes

ICSI Technical Report TR-92-077

Abbreviated Authors

A. Beroni, P. Campadelli, A. Morpurgo, and S. Panizza

ICSI Publication Type

Technical Report