Publication Details
Title: Polynomial Uniform Convergence and Polynomial-Sample Learnability
Author: A. Beroni, P. Campadelli, A. Morpurgo, and S. Panizza
Group: ICSI Technical Reports
Date: November 1992
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-077.pdf
Overview:
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 Information:
ICSI Technical Report TR-92-077
Bibliographic Reference:
A. Beroni, P. Campadelli, A. Morpurgo, and S. Panizza. Polynomial Uniform Convergence and Polynomial-Sample Learnability. ICSI Technical Report TR-92-077, November 1992
Author: A. Beroni, P. Campadelli, A. Morpurgo, and S. Panizza
Group: ICSI Technical Reports
Date: November 1992
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-077.pdf
Overview:
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 Information:
ICSI Technical Report TR-92-077
Bibliographic Reference:
A. Beroni, P. Campadelli, A. Morpurgo, and S. Panizza. Polynomial Uniform Convergence and Polynomial-Sample Learnability. ICSI Technical Report TR-92-077, November 1992