Learning to Create is as Hard as Learning to Appreciate.
David Xiao · 2010
We explore the relationship between a natural notion of “learning to create ” (LTC) studied by Kearns et al. (STOC ’94) and the standard PAC model of Valiant (CACM ’84), which can be thought of as a formalization of “learning to appreciate”. Our main theorem states that “if learning to appreciate is hard, then so is learning to create”. More formally, we prove that if there exists a concept class for which PAC learning with respect to efficiently samplable input distributions is hard, then there exists another (possibly richer) concept class for which the LTC problem is hard. We also show that our theorem is tight in two senses, by proving that there exist concrete concept classes for which PAC learning is hard but LTC is easy, and by showing that it is unlikely our main theorem can be improved to the case of PAC learning with respect to unsamplable input distributions. 1