Table of Contents

🎓 Intended learning outcomes

At the end of this lesson, students are expected to:

• Understand and use the terminology from learning theory
• Be able to define and explain risk $R$
• Understand and be able to define what a hypothesis and hypothesis class is
• Be able to define and explain Empirical Risk and Empirical Risk Minimization
• Relate Bayes error, approximation error, estimation error, and excess error
• Explain what it means for a hypothesis to be PAC-learnable, and define sample complexity
• Understand and explain the fundamental theorem of PAC learning and what it implies
• Understand and be able to define VC dimension and relate it to PAC learning, and explain what shattering is
• Explain how adding data or expressivity to the model influences PAC-learnability
• Understand the bias-variance tradeoff, how it arises from the definition of risk, and relate it to overfitting and underfitting
• Describe the no free lunch theorem