  Statistical learning theory and the Probably Approximately Correct (PAC)
criterion are the common approach to mathematical learning theory. PAC is
widely used to analyze learning problems and algorithms, and have been studied
thoroughly. Uniform worst case bounds on the convergence rate have been well
established using, e.g., VC theory or Radamacher complexity. However, in a
typical scenario the performance could be much better. In this paper, we
consider PAC learning using a somewhat different tradeoff, the error exponent -
a well established analysis method in Information Theory - which describes the
exponential behavior of the probability that the risk will exceed a certain
threshold as function of the sample size. We focus on binary classification and
find, under some stability assumptions, an improved distribution dependent
error exponent for a wide range of problems, establishing the exponential
behavior of the PAC error probability in agnostic learning. Interestingly,
under these assumptions, agnostic learning may have the same error exponent as
realizable learning. The error exponent criterion can be applied to analyze
knowledge distillation, a problem that so far lacks a theoretical analysis.
