0
$\begingroup$

The fundamental theorem of statistical learning gives an equivalence between uniform convergence of the empirical risk to learning in the PAC framework.

I have only seen this stated in the case of binary classification with the 0-1 loss. Does a result of this form hold in more general settings? For example: margin-based classification rules, regression, multi-class classification, ...?

Another statement of this question could be: under what circumstances does uniform convergence of the empirical risk imply PAC learning? (I am most interested in this direction of implication.)

Please provide references if you have them.

$\endgroup$
3
  • $\begingroup$ Uniform convergence means that the Empirical Risk Minimizer is a PAC learner. $\endgroup$
    – Aryeh
    May 3 at 17:14
  • $\begingroup$ I take issue with your characterization of the "fundamental theorem of statistical learning". For classification, it states the equivalence of PAC learnability and finite VC-dimension. $\endgroup$
    – Aryeh
    May 3 at 17:16
  • 1
    $\begingroup$ You should probably accept your own answer so this question stops showing up in the feed. $\endgroup$
    – Aryeh
    Sep 11 at 19:31
0
$\begingroup$

Turns out the answer is yes and can be found in Part 3 (eg chapter 19) of Neural Network Learning: Theoretical Foundations, by Anthony and Bartlett.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.