Testing Problems with Sublearning Sample Complexity

摘要

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, 1]d for constant d, the number of examples required for testing grows only as O(s1/2+δ) (where δ 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 Ω(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.