# Is there any practical application of knowing whether a concept class is PAC-learnable?

A concept class $$C$$ is PAC-learnable if there exists an algorithm that can output a hypothesis with probability at least $$(1-\delta)$$ (the "probably" part), and an error that is less than $$\epsilon$$ (the "approximately" part), in time that is polynomial in $$1/\epsilon$$, $$1/\delta$$, $$n$$ and $$|C|$$.

Tom Mitchell defines an upper bound for the sample complexity, $$m >= 1/\epsilon (ln(|H|) + ln(1/\delta))$$ for the finite hypotheses. Based on this bound, he classifies whether target concepts are PAC-learnable or not. For example, $$n$$ conjunction boolean literal concept class.

It seems to me that PAC-learnability seeks to act more like a classification of certain concept classes.

Are there any practical purposes for knowing whether a concept class is PAC-learnable?

• Seeing another way, a more useful formulation would be, whether the concept class is PAC learnable by your hypothesis class. Then you may play with your $H$. Also note PAC learnable is a very special case and it goes on to build on realistic cases like agnostic PAC, NUL, etc, etc. – DuttaA May 17 at 8:53
• but wouldn't determining whether the concept class is PAC learnable means going through the process that i described in the post ? – calveeen May 17 at 9:49