Learning Theory and VC Dimension

Student seminar — Session 23

Focus¶

Computational learning theory at a survey level: PAC learning, hypothesis space capacity, VC dimension, and generalization bounds.

Reading (examples)¶

• Zaki & Meira, learning theory chapter

• Duda et al., relevant statistical learning sections

• Shalev-Shwartz & Ben-David, Understanding Machine Learning (selected sections)

Student tasks¶

• Define PAC learnability informally and formally

• Explain VC dimension and its role in model capacity

• Relate theory to bias–variance and empirical model selection

• Q&A and short discussion