<p>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.</p>

CC BY-SA 4.0
2020-12-04T15:02:36.153Z
2020-12-04T15:02:36.153Z
user27182
<p>The fundamental theorem of statistical learning gives an equivalence between uniform convergence of the empirical risk to learning in the PAC framework.</p>
<p>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, ...?</p>
<p>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.)</p>
<p>Please provide references if you have them.</p>

CC BY-SA 4.0
2021-05-03T17:14:27.837Z
Uniform convergence means that the Empirical Risk Minimizer is a PAC learner.
Aryeh
CC BY-SA 4.0
2021-05-03T17:16:00.730Z
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.
Aryeh
CC BY-SA 4.0
2021-09-11T19:31:41.793Z
You should probably accept your own answer so this question stops showing up in the feed.
Aryeh
<reference-request><machine-learning><pac-learning>
Generalisations of the Fundamental Theorem of Statistical Learning to different tasks and losses
user27182
# Generalisations of the Fundamental Theorem of Statistical Learning to different tasks and losses

(Asked by: username_0 on 2020-12-04)

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.

**Tags:** reference-request, machine-learning, pac-learning

> **Comments:**
> **username_1**: Uniform convergence means that the Empirical Risk Minimizer is a PAC learner.  
> **username_1**: 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.  
> **username_1**: You should probably accept your own answer so this question stops showing up in the feed.  

---

## 1 answers

### Answer by username_0 on 2020-12-04. Score: 0 | Accepted answer

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.


---

