Academic Press Library in Signal Processing

Chapter 14

Learning Theory

Ambuj Tewari* and Peter L. Bartlett^†,    ^*439 West Hall 1085 South University Ann Arbor, MI, USA,    ^†387 Soda Hall #1776 Berkeley, CA, USA, [e-mail], [e-mail]

Abstract

We present an overview of learning theory including its statistical and computational aspects. We start by giving a probabilistic formulation of learning problems including classification and regression where the learner knows nothing about the probability distribution generating the data. We then consider the principle of empirical risk minimization (ERM) that chooses a function from a given class based on its performance on the observed data. Learning guarantees for ERM are shown to be intimately connected with the uniform law ...