For probably approximately correct (PAC) learning theory, two notions of learnability are considered: Probably uniformly approximately correct (PUAC) learnability, and minimal empirical risk (MER) learnability. The relationship of these notions is studied, and the relationship to a “shrinking with” property is shown. Some sufficient conditions for PUAC (MER) are given, and some further properties of these learnability concepts are discussed.
Reviewer: Kurt Marti (Neubiberg/München)