The study of proving performance guarantees for learning algorithms, usually in a supervised learning setting (also in self-supervised learning, but this is a stupid category).
We have a class , a set of functions which map the feature space to a label space , which we’ll assume is some subset of . Our algorithm sees training data (usually drawn iid from some distribution, but occasionally the distribution is more complicated) and chooses a function (via empirical risk minimization, say).
From here, there are several questions we might want to answer.
The first is, naturally, how good is ? That is, how well does generalize to unseen data? <ore formally, how close is the empirical risk of to the true risk (see statistical decision theory)? PAC bounds are the most common way to answer this question. This usually leads to bounds which depend on some notion of the complexity of the class , such as VC dimension or Rademacher complexity. Another way to answer this question is via PAC-Bayes bounds, which is a Bayesian take (sort of) on traditional PAC bounds. Here, the generalization gap is bounded in terms of some divergence.
The second is, how close is to the best function , the one that has the lowest risk. This question is usually answered by uniform convergence bounds in the following way. We want to bound where is the risk. Write
Term (ii) is , since is chosen to minimize empirical risk. Since is independent of the data, term (iii) can be handled via normal concentration inequalities (it’s simply the deviation between the sum of random variables and their mean). Then for term (i) we turn to a uniform convergence bound, since is highly data-dependent.