0
$\begingroup$

I've started reading more about statistical learning theory, specifically this paper right here and I cannot understand the following part:

It turns out the conditions required to render empirical risk minimization consistent involve restricting the set of admissible functions. The main insight of VC (Vapnik-Chervonenkis) theory is that the consistency of empirical risk minimization is determined by the worst case behavior over all functions f ∈ F that the learning machine could choose. We will see that instead of the standard law of large numbers introduced above, this worst case corresponds to a version of the law of large numbers which is uniform over all functions in F

The part that is in bold is what I do not get. This part specifically: "Consistency of ERM is determined by the worst case behavior over all functions in function space F, that learning machine could choose". What is exactly meant by the worse case behavior? I tried looking into VC theory and could not find the answer.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

What is considered in VC theory is about the bound of error between empirical risk and real expected risk. Hence, the worst-case function is when the difference between these two risks is maximized.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Simple enough, I was thinking too much about this. Thank you. $\endgroup$
    – Stefan Radonjic
    Apr 8, 2020 at 17:01
  • $\begingroup$ @StefanRadonjic my pleasure. $\endgroup$
    – OmG
    Apr 8, 2020 at 17:16
  • $\begingroup$ btw, what does it mean to UNIFORMLY BOUND difference between empirical and true risk over a family of classifiers? @OmG $\endgroup$
    – Stefan Radonjic
    Apr 8, 2020 at 17:51
  • $\begingroup$ @StefanRadonjic means "uniform convergence" here. $\endgroup$
    – OmG
    Apr 8, 2020 at 18:00

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.