Testing problems with sub-learning sample complexity
Michael S. Kearns, Dana Ron · 1998
We study the problem of determining, for a class of functions H, whether an unknown target function f is contained in H or is "far" from any function in H. Thus, in contrast to problems of learning, where we must construct a good approximation to f in H on the basis of sample data, in problems of testing we are only required to determine the existence of a good approximation.Our main results demonstrate that, over the domain [0, lld for constant d, the number of examples required for testing grows only as O(S~/~+' ) (where 6 is any small constant), for both decision trees of size s and a special class of neural networks with s hidden units.This is in contrast to the Q(s) examples required for learning these same classes.Our tests are based on combinatorial constructions demonstrating that these classes can be approximated by small classes of coarse partitions of space, and rely on repeated application of the well-known Birthday Paradox.Permission to make digital or hard copies of all or part ofthis work for pt~sonal or ch..sroot~ USC is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies hear this notice and the full citation on the first page.To copy