A memorization machine is a theoretical classification model that perfectly memorizes the training dataset, thereby always achieving an empirical error of $$0$$. However, this extreme flexibility means it completely fails to generalize to new, unseen data, performing no better than random guessing on the underlying population. Because this model class is excessively flexible, it serves as a primary counterexample demonstrating that uniform convergence cannot hold for all possible model classes.

Memorization Machine

Uniform convergence is a theoretical principle providing a guarantee that, with high probability, the empirical error rate for every classifier $$f$$ within a predefined model class $$\mathcal{F}$$ will simultaneously converge to its true population error rate. Specifically, it ensures that with a probability of at least $$1-\delta$$, no classifier's error rate in the class will be misestimated by more than a small margin $$\alpha$$.

Claude

The generalization gap is the mathematical difference between a model's empirical training error ($$R_	extrm{emp}$$) and its expected generalization error ($$R$$), expressed as $$R_	extrm{emp} - R$$. If a model achieves a training error of exactly zero, the generalization gap becomes precisely equal to the generalization error, meaning that further predictive progress can only be made by reducing this gap.

Generalization Gap

Dive into Deep Learning

Underfitting occurs when a model is insufficiently expressive to capture the underlying patterns in the training data. This situation is identified when both the training error and validation error are substantial, but the generalization gap ($$R_	extrm{emp} - R$$) between them remains small. Because the model fails to reduce the training error despite a small gap, overall predictive performance could likely be improved by utilizing a more complex model.

Underfitting

Overfitting occurs when a model performs significantly better on its training data than on validation or holdout data, resulting in a large generalization gap. This indicates that the model is overly complex and has begun to memorize noise rather than learning generalizable patterns. However, severe overfitting is not always inherently detrimental in deep learning; the best predictive models often exhibit this behavior. The primary goal is to drive the overall generalization error lower, meaning the gap is only problematic if it obstructs that goal.

Learn Before

Related

Learn After