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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Uniform convergence means that the Empirical Risk Minimizer is a PAC learner. $\endgroup$
    – Aryeh
    May 3, 2021 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, 2021 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, 2021 at 19:31

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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