Overview: Learning Theory and Generalisation

Every model built so far in this unit has been justified by an intuitive story — "more flexible models fit the training data better, but risk overfitting." This topic makes that story precise. It answers three questions stated explicitly in CS229's own learning-theory notes: can the bias/variance trade-off be formalised mathematically? Why should doing well on a training set say anything about performance on new data? And are there conditions under which a learning algorithm's success can be actually proven, not just empirically observed? The answers — via two simple probability lemmas, extended first to finite and then to infinite hypothesis classes — are, in Vapnik's VC-dimension theorem, "many would argue, the most important theorem in all of learning theory."