  There are many high dimensional function classes that have fast agnostic
learning algorithms when assumptions on the distribution of examples can be
made, such as Gaussianity or uniformity over the domain. But how can one be
confident that data indeed satisfies such assumption, so that one can trust in
output quality of the agnostic learning algorithm? We propose a model by which
to systematically study the design of tester-learner pairs
$(\mathcal{A},\mathcal{T})$, such that if the distribution on examples in the
data passes the tester $\mathcal{T}$ then one can safely trust the output of
the agnostic learner $\mathcal{A}$ on the data.
  To demonstrate the power of the model, we apply it to the classical problem
of agnostically learning halfspaces under the standard Gaussian distribution
and present a tester-learner pair with combined run-time of
$n^{\tilde{O}(1/\epsilon^4)}$. This qualitatively matches that of the best
known ordinary agnostic learning algorithms for this task. In contrast, finite
sample Gaussianity testers do not exist for the $L_1$ and EMD distance
measures. A key step is to show that half-spaces are well-approximated with
low-degree polynomials relative to distributions with low-degree moments close
to those of a Gaussian.
  We also go beyond spherically-symmetric distributions, and give a
tester-learner pair for halfspaces under the uniform distribution on
$\{0,1\}^n$ with combined run-time of $n^{\tilde{O}(1/\epsilon^4)}$. This is
achieved using polynomial approximation theory and critical index machinery.
  We also show there exist some well-studied settings where
$2^{\tilde{O}(\sqrt{n})}$ run-time agnostic learning algorithms are available,
yet the combined run-times of tester-learner pairs must be as high as
$2^{\Omega(n)}$. On that account, the design of tester-learner pairs is a
research direction in its own right independent of standard agnostic learning.
