  One of the motivations for property testing of boolean functions is the idea
that testing can serve as a preprocessing step before learning. However, in
most machine learning applications, it is not possible to request for labels of
fictitious examples constructed by the algorithm. Instead, the dominant query
paradigm in applied machine learning, called active learning, is one where the
algorithm may query for labels, but only on points in a given polynomial-sized
(unlabeled) sample, drawn from some underlying distribution D. In this work, we
bring this well-studied model in learning to the domain of testing.
  We show that for a number of important properties, testing can still yield
substantial benefits in this setting. This includes testing unions of
intervals, testing linear separators, and testing various assumptions used in
semi-supervised learning. In addition to these specific results, we also
develop a general notion of the testing dimension of a given property with
respect to a given distribution. We show this dimension characterizes (up to
constant factors) the intrinsic number of label requests needed to test that
property. We develop such notions for both the active and passive testing
models. We then use these dimensions to prove a number of lower bounds,
including for linear separators and the class of dictator functions.
  Our results show that testing can be a powerful tool in realistic models for
learning, and further that active testing exhibits an interesting and rich
structure. Our work in addition brings together tools from a range of areas
including U-statistics, noise-sensitivity, self-correction, and spectral
analysis of random matrices, and develops new tools that may be of independent
interest.
