Active Testing Real-valued Functions

October 30, 2013

One motivation for property testing is that testing can provide a fast preprocessing step before learning. However, algorithms based on membership queries (i.e., the ability to query functions on arbitrary points) tend to query highly ambiguous or unnatural points that can be impossible for a human oracle to label. To address this, our earlier work on Active Testing introduced a more realistic model where the algorithm may query for labels only on points in a given (polynomial-sized) unlabeled sample drawn from some underlying distribution. In this new work, we discuss a recent generalization of this work to testing properties of real-valued functions. In particular, we have shown that it is possible to test piecewise constant functions, with d pieces, using a number of label queries independent of d. We also discuss extensions of this result to the more-general problem of testing piecewise degree-n polynomials, with d pieces, where again we have obtained that the number of label queries can be made independent of d. We will also discuss the problem of testing linearity in n dimensions.