Error Exponent in Agnostic PAC Learning
This work addresses the theoretical analysis of learning algorithms for researchers in statistical learning theory, providing a novel criterion to assess performance in scenarios like knowledge distillation, though it is incremental as it builds on existing PAC frameworks.
The paper tackles the problem of analyzing the convergence rate in agnostic PAC learning by introducing the error exponent from information theory, finding an improved distribution-dependent error exponent for binary classification under stability assumptions, which shows that agnostic learning can achieve the same exponential error probability decay as realizable learning.
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.